Domatic partition in homogeneous wireless sensor networks

摘要

In wireless sensor networks, rotating dominating sets periodically is an important technique, for balancing energy consumption of nodes and hence maximizing the lifetime of the networks. This technique can be abstracted as the domatic partition problem, which partitions the set of nodes in networks into disjoint dominating sets. Through rotating each dominating set in the domatic partition periodically, the energy consumption of nodes can be greatly balanced and the lifetime of the network can be prolonged. In order to solve the domatic partition problem, we present a Cell Structure which is constructed as follows. Firstly, the network is divided into clusters, and then a clique is constructed in each cluster. Based on the Cell Structure, we propose a new constant-factor approximation algorithm for domatic partition using the property of the skyline of uniform radius disks. The algorithm is called distributed nucleus algorithm (DNA). In addition, we show that DNA can be implemented in constant rounds in the congest model.