Design And Simulation Of Approximate Algorithms For Connected Dominating Set In Wireless Sensor Networks

Wireless Sensor Network(WSN), carrying a variety of sensors, is a brand-newplatform which can real-time monitor and collect information of the objects inmonitored area. The information acquired by sensors is uploaded to the sink nodes byWSN in order to realize the target’s surveillance and tracking. So WSN is the focus ofresearch.Because of lacking infrastructure, wireless sensor network doesn’t have goodsolution for network management and routing. On the other hand the sensor nodeshave very limited power. Therefore it is necessary to construct a virtual backbone asan infrastructure for improving utilization of resources and optimizing networkperformance. In mathematics the construction of virtual backbone equal to find theminimal connected dominating set(MCDS) in a Graph. The solution of MCDSproblem has been proved NP hard problem. This paper is studied from the aspects ofdominating set. Specific work as follows:1) The paper discusses the network architecture, composition, characteristics andapplication of WSN. By introducing thoughts of virtual backbone consisted ofconnected dominating sets. The existing CDS algorithms are also illustrated.2) By introducing some basic knowledge of graph theory, the topology of WSNabstracted unit disk graph is described based on the knowledge of graph theory.3) Connectivity of the graph is analysed from two aspects of coverage andco-nnection of the graph. Firstly the thesis compares coverage with connection of thegraph. Secondly from the aspect of the threshold launch radius and the nu-mber ofneighbor nodes, the connectivity probability of the graph is analysised throughestablish corresponding model. Finally simulation experiments are accomplished fromtwo aspects.4) The definitions and properties of connected dominating sets are given. Theexisting classic connected dominating sets algorithms are discussed in this paper.5) From two aspects of dealing with multiple nodes and acquiring less points of2-hop dominating sets, respectively we provide the connected dominating setsconstructing algorithm GCDS and2-hop dominating sets algorithm2-GCDS. GCDS baseded on greedy algorithm judges two or three nodes state other than many CDSalgorithms of dealing with a node every.2-DSGA algorithms consist of three parts ofconnecting2-hop neighbor nodes, finding two-hop dominating sets of graph, pruningthe redundant nodes of the dominating sets.The paper analyses the time complexity oftwo algorithms. The theoretical analysis and the simulation experiments show that theresults obtained by the two algorithms is excellent, especially the time price of DSGAalgorithm is less.