Algorithms For Connected Dominating Sets In Sensor Networks

Topology control is one of key technologies in wireless sensor networks, based on minimum connected dominating set (MCDS) of graph theory, constructing a hierarchical network which has a virtual backbone is a common approach of topology control, but the MCDS problem of graph theory is NP-complete.In a simple undirected finite graph, to solve the MCDS problem is equivalent to solve the maximum leaves spanning tree (MLST) problem. In this thesis, based on the minimum degree of circuit, an approximate algorithm for MLST, namely MDRST (Minimum-Degree Related Spanning Tree), was proposed. MDRST determines neighbors by comparing the degree of vertices, it can induce a spanning tree with many leaves through removing an edge which one vertex's degree is minimal from each circuit in original graph .MDRST is a centralized algorithm, and its time complexity is O (N~2).In order to implement a distributed algorithm for MCDS problem, a spanning graph structure MDRSG (Minimum-Degree Related Spanning Graph) which is base on the minimum degree of triangle or quadrangle circuit was presented. Contrast to MDRST that eliminate all loops of original graph, MDRSG only removes edges from triangle or quadrangle loops. MDRSG can be constructed by a distribute algorithm with polynomial time complexity, and each vertex in original graph needs neighbor-lists of 1-hop neighbors and degree information of 2-hop neighbors when MDRSG being constructed.The thesis applied MDRSG to topology controlling in wireless sensor networks, implemented a method that combined MDRSG and relative neighborhood graph (RNG) to conquer the disadvantage that MDRSG is not planar and MDRSG does not take edges' weight into account. The method found a connected dominating set by MDRSG firstly, and then organized the nodes in dominating set formed a planar backbone network by RNG secondly; all the dominated nodes selected a nearest neighbor node in dominating set connected to backbone network. The topology structure formed by the method is hierarchical and planar, and could adjust locally as also.