标题：Domatic partition in homogeneous wireless sensor networks
作者：Yu, Jiguo; Zhang, Qingbo; Yu, Dongxiao; Chen, Congcong; Wang, Guanghui
作者机构：[Yu, Jiguo; Zhang, Qingbo; Chen, Congcong] Qufu Normal Univ, Sch Comp Sci, Rizhao 276826, Shandong, Peoples R China.; [Yu, Jiguo] Key Lab Intelligen 更多
通讯作者地址：[Yu, JG]Qufu Normal Univ, Sch Comp Sci, Rizhao 276826, Shandong, Peoples R China.
来源：JOURNAL OF NETWORK AND COMPUTER APPLICATIONS
关键词：Wireless sensor networks (WSNs); Domatic partition (DP); Domatic number;; Clustering; Skyline disk; Congest model
摘要：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. (C) 2013 Elsevier Ltd. All rights reserved.