Construction Algorithm Of Connected Dominating Sets In WSN

Due to Wireless Sensor Network(WSN)has the characteristics of low power consumption,self-organization,and multi-hop,it is widely used in many fields,such as medical and health,defense military,and environmental monitoring.At present,WSN has attracted the attention of researchers.Especially,the virtual backbone network as the network routing management has become one of the hot research topics.The method of constructing a virtual backbone network in WSN by using Connected Dominating Set(CDS)in graph theory to construct a hierarchical network has been widely used.However,the nodes in the WSN have the defects of insufficient energy and low processing and storage capacity.Therefore,how to balance the node energy to extend the life cycle of the network as much as possible has become the focus of research.In this paper,a centralized algorithm for improved energy-Balance Connected Dominating Set(IEB-CDS)is proposed to construct the connected dominating set by research and summary of the existing connected dominating set construction algorithm.It considers several factors that affect the network cycle of the virtual backbone network to construct the node weight formula,including the one-hop and two-hop neighbor nodes of the node,the remaining energy and energy thresholds.The IEB-CDS is implemented in three phases.At the first stage,nodes with larger weights are selected to construct an independent set.the second stage,nodes with larger weights are selected as connecting nodes to connect independent nodes.the last stage,check if all nodes are dominated.Simulation experiments and related analysis show that the IEB-CDS not only can obtain a small connected dominating set,but also effectively balance the node energy of the whole network and extend the network lifetime.The algorithm proposed above is studied in the undirected graph,and each node has the same transmission range.However,in practice,most network links are asymmetric due to differences in power and function,and the transmission range of all nodes is not necessarily equal.Aiming at this problem,this paper proposes a method(is named to D-SCDS)of constructing Strongly Connected Dominating Set(SCDS)in directed graph based on IBE-CDS.It considers global network information,uses the weight formula to calculate the node weight,and selects the nodes with larger weights to construct the strong connected dominating set.The results of simulation show that the SCDS with energy balance,small scale and long lifetime is constructed by using D-SCDS.