Research On The Construction Algorithm Of Wireless Network Connected Dominating Set Based On SINR Model

With the continuous development of wireless communication technology,wireless networks have been widely used in a variety of application fields,such as military,medical treatment,environment and so on.However,the shortcomings of wireless networks limit the performance of the network,such as energy waste,information redundancy and so on.The efficient technology to solve these problems is topology control.Connected dominating set is a representative technology for topology control in wireless networks.It facilitates the realization of many work,such as broadcasting,routing,data collection and so on.Based on the analysis and research of the existing connected dominating set algorithms,this thesis studies the CDS construction algorithms under SINR(Signal-to-Interference-plus-NoiseRatio)model.In recent years,most of the work uses simple graph-based models or distance-based interference models to study CDS construction problems.In this regard,few articles have studied physical interference model(SINR model).The SINR model is a model that takes into account the cumulative interference and is close to the reality of the natural environment.This thesis is divided into five chapters.Chapter 1 introduces the research background,significance and research status.Chapter 2 classifies and summarizes some of the existing connected dominating set algorithms,and analyzes some of the classic constructive algorithms.In Chapter 3,a self-stabilizing connected dominating set algorithm(DS_CDS-1)is proposed,which divides the nodes in the network into different grids.It contains two phases.Form a MIS in the first phase,and connect the MIS nodes into a CDS through the neighboring nodes in the adjacent grid,we can prove that we can obtain a CDS with self-stabilization and a constant approximate factor.However,chapter 3 does not consider the optimization factors of connected dominating set.In order to further solve the problem of connected dominating set in SINR model,chapter 4 introduces the construction of connected dominating set algorithm with self-stabilization and bounded diameter in the SINR model(DS_CDS-2).Compared with the algorithm in the third chapter,this algorithm lessens the constant approximate factor of CDS,decreases the time complexity,and proves the upper bound of the diameter for CDS.Chapter 4simplifies the SINR model by the corresponding assumptions to analyze and compute more conveniently,when analyzing the SINR constraints.In order to further optimize the algorithm's authenticity,we design the self-stabilizing distributed algorithm again for CDS construction in chapter 5(DS-CDS-3).In this chapter,we continue to focus on the two important performanceindicators,density and the diameter of CDS,and obtain the corresponding research results.As far as we know,this is the asymptotically optimal self-stabilizing result of density and diameter for the distributed algorithm of CDS construction.In the sixth chapter,the thesis is summarized and the future work is forecasted.