Research On Control Partition Problem In Wireless Sensor Network

Wireless sensor networks (WSNs) offer a wealth of capabilities in interacting with the physical world by collecting, transmitting, and processing data from the environment and responding accordingly. Recent years have witnessed a tremendous amount of research in the field of wireless sensor networks due to their numerous real-world applications, such as military monitoring, environmental and habitat monitoring, fire detection, object tracking, industrial and agricultural control, dangerous area domination, and so on. WSNs have been paid great attention in both industrial field and academic field and become one of the hot topics in the research of computer science.In WSNs, finding a dominating set is generally used as virtual backbone. The dominating set forms a hierarchical topology to be used as a communication layer. Thus the nodes in the dominating set transmit data, simplifying the topology of the network and greatly reducing the transmission of redundant information. While the dominators in the dominating set produce too much extra overheads such as gathering, processing and forwarding data information. Moreover, sensor nodes usually are charged with battery whose energy is limited and placed one-time, which makes it impossible for a second charging. Thus, the dominators deplete energy faster than other nodes in the network and then the networks lifetime is shortened.Domatic partition problem is to find several disjoint dominating sets, and then a sleep scheduling is formed by rotating every dominating set to balance the energy consumption and prolong the lifetime of the networks. According to the type of the dominating set, domatic partition problem can be divided into three types:k-domatic partition (k-DP), domatic partition (DP) and connected domatic partition (CDP). This paper resoulves three open questions on them, and respectively presents a constant-factor approximation algorithm, with the simulations demonstrating the correctness and feasibility.Firstly, this paper studies the open problem on k-DP. We propose a k-DP algorithm with a constant approximation factor by uniform partition based on clustering in unit disk graphs, using connectivity information only. Then, this paper studies the DP. We propose a division of a cell structure which contains the cluster partition and clique partition. Based on the cell structure, we propose a constant-factor approximation algorithm for DP using the property of the skyline disks in unit disk graphs. The algorithm not only can be efficiently implemented in the local model but also in the congest model. Finally, this paper studies the open problem on CDP. Based on the cell structure, we first find a domatic partition using connectivity information only, and then extend it into a connected domatic partition. In the end, we propose a local schedule of connected dominating sets in CDP to prolong the lifetime of the network.In conclusion, this paper studies three types of domatic partition and has some value and significance in the academic research of the domatic partition problem in WSNs.