Research On Connected Dominating Set For Topology In Wireless Sensor Networks

The construction of topological structure is one of the critical issues in wirelesssensor networks. Recently, virtual backbones based on connected dominating set and itsvariants have been widely studied. They have great significance to improve the routingperformance and prolong the life time of network. And they also could provide effectivetracking information for navigating the mobile node in network, However, in unit diskgraphs, computing the minimum connected dominating set and its variants—-efficientconnected dominating set, minimum vertex cover set and so on are NP-hard, so theresearchers mostly focus on designing polynomial time algorithm to find correspondingapproximation solutions.According to the related work and proposed research methods, in this paper we firstlypresent an approximation algorithm for the (3,2)-efficient connected dominating set in unitdisk graphs. Using grid partition and shifting strategy, for any sufficiently small>0, thisalgorithm could compute an approximation solution whose size is related with the input.We prove the correctness of this algorithm and show that its running time is polynomial.Secondly, without requiring the geometric representation, in growth bounded graphs withbounded degree constraint we design the polynomial time (1+)-approximation algorithmsfor the minimum vertex cover problem and minimum weighted vertex cover problem,where>0. We prove the correctness of these algorithms and show that their running timeis polynomial. At last, based on-efficient connected dominating set, we build a pathplanning infrastructure for the mobile node in wireless sensor networks. And by trackingthe static nodes as temporary targets in the path planning infrastructure, we introduce apath planning algorithm. This infrastructure not only transmits information as a networkbackbone, but also updates the path which has been computed by our algorithm to ensureits effectiveness and guarantee a constant ratio of navigation overhead. Simulation resultsshow that the mobile node can accomplish navigating to the destination by communicating with the static sensor nodes and tracking them. Compared with the existing algorithm, theefficiency of navigation has a valid improvement.