Algorithm Design And Analysis Of Connected Dominating Set Problem In Wireless Network

Wireless networks have the characteristics of self-organization and multi-hop routing.Devices in the network communicate by means of message transmission,which will result in a large amount of redundant data and have the risk of network storms.As one of the most important ways to implement topology control in wireless networks,connected dominating set can simplify the network routing table,save energy,and feature high efficiency and convenience.Connected dominating set attracts the attention of many researchers at home and abroad.With the development of wireless network application,further research on the connected dominating sets is required.This thesis has carried out in depth and meticulous research on the problem of connected dominating set in wireless networks.The main research contents and achievements are as follows:In this thesis,the characteristics of wireless networks are briefly introduced.The summary and classification of the existing connected dominating set algorithms are followed.Based on that,the algorithms for constructing connected dominant set under the graph model and the SINR(Signal-to-Interference-plus-Noise-Ratio)model are analyzed.Then,according to these two network models,two distributed algorithms for constructing connected dominating sets are designed.Under the graph model,a two-stage algorithm MISD-ODC for constructing a connected dominating set is proposed.In the first stage,the algorithm MISD constructs a maximal independent set according to the degree of the node.In the second stage,the concept of the Opt-Degree connection is put forward.The algorithm ODC joins the nodes in the Opt-Degree connection to join the maximal independent set to obtain the connected node set.The algorithm has achieved good results in terms of time complexity and the size of connected dominating set.The theoretical analysis proves that the time complexity of the algorithm MISD-ODC is O(9))where n is the total number of nodes in the network.The simulation experiment verifies that the algorithm MISD-ODC effectively reduces the size of connected dominating set.Under the SINR model,a node scheduling scheme is designed.In this scheme,the network is divided into hexagonal cells,all cells are colored,and nodes in the same color cells are scheduled to be transmitted in each time slot.According to the strict theoretical analysis,this method successfully solves the problem of interference existing in the network.According to the results of network partitioning,an algorithm DECE is proposed to construct the connected dominating set.This study first selects a dominating set by using the dominators selection algorithm DE,and then designs the connectors selection algorithm CE.In this way,the dominators in the adjacent cells are connected to each other.The algorithm is independent of the location of the nodes.The time complexity of constructing the connected dominating set is O(?),and the approximate ratio is 56opt+28,where ? is the maximum node degree,and opt is the size of minimum connected dominating set.This algorithm outperforms existing algorithms for constructing connected dominating set under the SINR model in terms of its approximation ratio.