2009 IEEE 34th Conference on Local Computer Networks
Download PDF

Abstract

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.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles