Design And Analysis Of The Algorithm For Constructing Wireless Network Connectivity Dominating Set

Unlike traditional cellular communication networks,no physical backbone infrastructure is installed in wireless ad hoc networks.Nodes communicate with each other by flooding broadcasts,which will generate lots of message delays and collisions,even trigger the broadcast storms,resulting in the increase of energy consumption and the reduction of the lifetime of network.Communicating through a Virtual Backbone Network(VBN)in wireless networks can effectively solve obove problems.Constructing a Connected Dominating Set(CDS)in graph theory is one of the major methods to formulate a VBN.Based on the introduction of the current status and performance indicators of the CDS constructing algorithms,it is found that the size of CDS is not the only goal pursued in all wireless networks.For example,the links between nodes with speed breakdown easier in mobile ad hoc networks,so more attention needs to be paid to the lifetime of the CDS.In addition,compared with the traditional graph model(protocol model)that only considers local interference,the physical interference model(Signal-to-Interference-plus-Noise-Ratio,SINR)portrays an actual network environment.It considers the global interference problem and reflects the accumulative and fading nature of wireless interference.Based on the above two issues,this thesis studies the construction algorithm of CDS with long lifetime in mobile ad hoc networks and the construction algorithm of CDS based on the SINR model in wireless networks.The main works and contributions of this thesis are as follows:(1)This thesis improve the lifetime of CDS in mobile ad hoc networks from two aspects.Firstly,the original network is "upgraded" by deleting the unstable links,which was depends on the condition that the ratio of the Euclidean distance between the nodes and their communication range is less than the fixed parameter?;Then,nodes with a low moving speed are preferred to be selected as CDS nodes.Once a node becomes a CDS node,all its neighbors have been explored and stored in a queue and have the opportunities to participate in the next iteration.All the explored nodes are arranged in non-decreasing speed.When the explored node has at least one neighbor that has not been explored,the node will be added to the CDS.This process continues until there are no unexplored nodes in the network.Compared with the traditional CDS constructions based on the degree,this thesis constructs a CDS with long lifetime,which has been confirmed by the theoretical analysis and simulation.(2)This thesis designs an algorithm D-CDS to construct a CDS based on the physical interference model in general wireless networks.First,the network is divided into hexagonal grids with the same side length,and each grid is called a cell.To avoid collisions,we introduce physical carrier sensing.The algorithm D-CDS consists of two phases.The first phase is the leader election phase,and a leader is selected for each cell.In the second phase,the connectors are selected to connect the leaders obtained in the first phase to form a CDS of the network.The second phase mainly includes three sub-stages,which are intra-cell learning,extra-cell learning,and connector selection.The leaders obtain the information of neighbors in the same cell through intra-area learning,and share these information with them;nodes learn the information of neighbors in different cells through extra-cell learning.Finally,some nodes are selected as connectors to reduce the number of connected components,and some of them are deleted according to the minimum rule to obtain a CDS with few nodes.This thesis proves the feasibility and correctness of the algorithm D-CDS under the SINR model through theoretical analysis.At the same time,the time complexity of the algorithm is better than the existing algorithms,and it can obtain a CDS with a constant approximate ratio.