Maximizing the lifetime of wireless sensor networks through domatic partition

摘要

Distributing sensing and data gathering tasks to a dominating set is an attractive choice in wireless sensors networks since it helps prolong network lifetime by engaging such a subset of nodes for these tasks and letting other nodes go into energy-efficient sleep mode. Because they are busy all the time for sensing, processsing, and transmitting data, nodes in the dominating set quickly run out of energy. One possible way to overcome this situation is to find a number of dominating sets among the nodes of the network and use them one by one iteratively. In this paper, we investigate the problem of finding the maximum number of disjoint dominating sets called the domatic partition problem in unit disk graphs. Although the domatic partition problem is NP-hard in general graphs, it is unknown whether the same is true for unit disk graphs. However, we present an algorithm towards solving this problem (approximately) together with experimental results and give a conjecture based on our results about the maximum number of disjoint dominating sets in unit disk graphs.