Distributed Wireless Sensor Network Connected Dominating Set Construction Method Research

WSN (Wireless Sensor Network) is one of the most valuable emerging disciplines in the21st century. WSN can be used to monitor environment in real-time, collect and analysis all kinds of efficient information in the WSN monitoring area, and the sensor data can be transferred to the task management node through WIFI, GPRS, mobile data network or any other wireless technology, so as to monitor and react to the changes of situations of monitoring targets. WSN has many advantages such as wide monitoring area and great ability to adapt to the environment, and the nodes of which are also easy to deploy, so WSN technology has been paid more and more attentions no matter in the military, commercial or civil field. Recently, constructing WSN Virtual Backbone efficiently is a hot topic in the research field of WSN.As the sensor nodes of WSN with small size are usually deployed in a very vast area, so their management and maintenance are very troublesome. Constructing an efficient virtual backbone can extend the network work time and reduce maintenance cost by a software approach. The mainly content of this paper is constructing the virtual backbone network by calculating CDS (Connected Dominating Set) with the optimal performance. Calculating the minimum Connected Dominating Sets has been proven to be a NP complete problem, so heuristic method is often used to calculate approximatively the optimal solution as the most common means. There are two kinds of CDS algorithm:Centralized Algorithm and Distributed Algorithm. Because of the dynamic characteristics of WSN, the centralized algorithm is difficult to adapt to the real-time changes of the networks, so the distributed algorithm is usually adopted. In this paper, two optimization distributed algorithms about calculating CDS are proposed: MI-LCDS (Multi-Initiator Layer Based CDS Construction Algorithm) and FNDB (A Forward1-hop neighbor Information set Based Distributed algorithm for Virtual Backbone).MI-LCDS puts forward a network layer model based on multi-source nodes. First, algorithm picks up several source nodes according to the scale of the network. And the source nodes divide their own area into several layers respectively, then calculate the CDS of each layer in a distributed way. Finally, link the CDSs of all source nodes through the bridge nodes, and get the CDS of the whole network. The time complexity of MI-LCDS algorithm is O(△2), and△is the average degree of the nodes.FNDB only use1-hop neighbor information, achieve the forwarding set B(v) of each node after obtaining the boundary intersection points set, and then work out the CDS by selecting dominated nodes from B(v) through the dyeing method. The simulation results show that, the extra information of FNDB is about equal to the size of the CDS, and the converge time of FNDB is about equal to the network diameter of WSN.