Cds-based Topology Control Algorithm For Wireless Network Research

In the wireless networks, nodes undertake the tasks of information communication and routing. However, the routing based on flooding could arouse the broadcast storm, and waste the network resources. And due to the limited node energy, the topology structure of the network dynamically changes. Therefore, the development of the reasonable mechanisms of routing and topology control becomes an important research issue. Many researchers propose to construct a virtual network base station to organize the network in a hierarchical structure, in order to achieve the scalability and efficiency of the wireless network. The virtual network base station is called a virtual backbone network. A virtual backbone can be used as a spine for routing in a network. The nodes which are responsible for routing are limited to the nodes in the backbone, greatly reducing the routing overhead, and effectively controlling the network topology.This paper adopts the technology of connected dominating set (CDS) to construct a virtual backbone network. It is an important way to build a hierarchical topology, thereby prolonging the network lifetime, and is the focus of research at home and abroad. A CDS of a graph G corresponding to a wireless network is a subset S of G, such that each node in the graph is either in S or has at least a neighbor node in S, and the induced sub-graph G[S] formed by the set is connected. CDSs have been used as the basic structure for the MAC, multicast/broadcast, location-based routing, energy conservation, resource discovery protocol, etc.This paper uses a CDS as the theoretical basis for the research, and carefully studies, analyzes and summarizes the traditional methods and hot spot on the construction of connected dominating sets. This paper also designs and develops the algorithms for connected dominating set with different natures under different network models. In the study process, we use the theoretical analysis of mathematics, graph theory and the collection of simulation data to guarantee the correctness of the results in theory and the feasibility in practice. This paper includes six chapters. The first chapter analyzes the current study situation and deficiencies, and finds out our current study direction. The second chapter has a simple overview of the existing algorithms for constructing CDSs (such as network models, algorithm types, and typical algorithmic ideas). Meanwhile, this chapter points out our research content-based on different network models to develop the constructive algorithms for CDSs. In the third chapter, based on the neighborhood of nodes, a local algorithm to find a minimum connected dominating set in the unik disk graph is proposed. To copy with the change of topology caused by moving nodes, a local repair algorithm is proposed. In the fourth chapter, the antenna model is used in a wireless network. Thus, the network can be modeled as a directed graph to construct a directional connected dominating set. In fifth chapter, inspired by the cooperative communication model, we extend the dominant capability of nodes. And based on this extension, we develop three novel algorithms for constructing weakly connected dominating sets in the network. Both theoretical analysis and simulations demonstrate the correctness and superiority of the algorithms. Finally, the sixth chapter summarizes this paper, and presents the future work.