Algorithm Design And Analysis Of Connected Control Set In Wireless Network

With the applications of wireless network in home automation, traffic control, medical care, environmental monitoring, battlefield detection, agriculture and other aspects, the finite energy of nodes have become the bottleneck problem of network lifetime, since the network nodes are powered by batteries. Therefore, for increasing the lifetime of the whole network in the detection area, we should save node energy consumption as much as possible. However, that the nodes communicate with neighbors through broadcasting messages will cause a lot of information redundancy. Which not only will lead to fail of the transmission of information, but also greatly cause enegy consumption of nodes. In order to reduce the redundancy of information and reduce the energy consumption of nodes in the network, the most simple and effective method is to establish the virtual backbone network in the network. Up till the present moment, some classic algorithms for constructing connected dominating set(CDS) in wireless network mostly contained two phases. In the first phase, a maximal independent set(MIS) is constructed. The second phase is to select some connectors from V\MIS to join MIS and to make all nodes in the MIS connect.In this thesis, some classic algorithms for CDS are studied and analyzed firstly. Afterwards, the distributed algorithm LDDS and CT for constructing CDS in united disk graph(UDG) are proposed. Later, we propose a centralized algorithm CMDS, that is the centralized version of algorithm LDDS. And we propose a centralized connecting algorithm CMCDS for connecting all nodes in MDS that obtained by algorithm CMDS. Afterwards, for general graph, we obtain a lower bound for optimal MCDS, that is. Which verified that for arbitrary connected dominating set, the approximation ratio is satisfied that. Finally, we propose distributed algorithms Asyn_BFS、COF、CMIS、ACP、ACHC、PMIS and the global connected algorithm for obtaining a relatively superior CDS.This thesis contains six chapters. The first chapter introduces the research background, significant and the performance indexes of CDS construction. The second chapter is simply to classify and summarize the current algorithms for construction of CDS and simply analyzes some of algorithms. In the third chapter, we design an approximation distributed algorithm for constructing minimum connected dominating algorithm(MCDS). Firstly, we propose a distributed algorithm LDDS to obtain a MDS. The algorithm is to select a pair of nodes as the elements of MDS based on maximum number of adjacent edges of a link. When there exists a node v such that all neighbors of nodes in the set N(v) are belonging to N(v), then node v is added to MDS directly. Afterwards, we propose an algorithm CT for constructing a Connecting Tree that is to connect all nodes in MDS and ensure the number of connectors as little as possible. In the forth chapter, we propose a centralized version algorithm CMDS for algorithm LDDS and propose a centralized algorithm CMCDS for connecting all nodes in MDS, where the algorithm CMCDS can ensure the least of the number of connectors for connecting all nodes in MDS. Chapter five proposes a distributed algorithm for obtaining a CDS in general graph. We first propose an algorithm Asyn_BFS to get a BFS tree. Afterwards, we obtain a forest based on the size of degrees of nodes by algorithm COF. And we propose an algorithm CMIS for obtaining a local MIS in each tree of forest. Later, each tree is divided into |MIS| clusters by algorithm ACP and algorithm ACHC is to connect all cluster heads in each tree for obtaining a local CDS. Afterwards, we propose an algorithm PMIS for pruning all redundancy nodes in local CDS. Finally, the global connected algorithm is to connect all local CDS for obtaining the global CDS. We summarize the thesis in chapter six and look forward to the future research work.