Connected Dominating Set Construction And Maintenance Algorithms,

Wireless sensor network is composed by many sensors with wireless sending and receiving devices. It is a multi-hop with no center network, and built at anytime, at anywhere, fast and infrastructureless. A typical sensor node is composed by sensing system, processing system, wireless communicating system and energy supplying system. Sensing system is for collecting data from the environment; processing system is for local data processing and preserving; wireless communicating system is for data transporting; and energy supplying system is for supplying the energy needed for the mission.In the wireless networks, sensor nodes are in charge of not only the communication, but also routing. However, the routing based on flooding could arouse the broadcast storm, and waste the network resources. Due to the dynamic variation of the topology of the network structure, and the limitation of the multi-hop communication and resources, the design of reasonable routing becomes a challenge issue. Thus, many researchers propose a method to build a backbone to realize the stability and efficiency by classiyfing the networks. Constructing the virtual backbone could classify the nodes in the network and it is also an application of CDS in the graph theory. By this method we could restrict the routing to the virtual backbone composed by CDS. The sender sends messages through the CDS to the nearest dominator then to the destination.Based on the theory of CDS, this paper lucubrates the traditional methods for constructing the CDS and proposes an improved constructing method. Firstly we construct a MIS, then choose the connecting nodes according to the two-hop information. Finally, achieve a CDS. There are four factors we use to measure the efficiency of the algorithm:approximation, locality, time complex and message complex, and stability. Theoretical analysis and simulation results show that compared with the traditional algorithm, our algorithm could create a much less backbone network and a smaller approximation 6.906.In recent years, the algorithms for the complex environment, better fault tolerance, stronger k-connected and m-dominated are proposed. Howerer, most of these algorithms must rebuild the kmCDS in the face of the node mobile which undoubtedly increases the cost. Therefore, we proposed a kmCDS maintaining algorithm for mobile networks. After the kmCDS built by traditional algorithm, this algorithm could maintain the kmCDS after the nodes in the network move.