Research On Control Set Construction Algorithms In Wireless Networks

In recent years, wireless network has been widely used in various applications with the development of wireless communication technology and equipment. While the wireless devices typically communicate with each other by local broadcast which creates a large amounts of information redundancy and wastes lots of energy. How to reduce the information redundancy and save energy is one of the most important problems to be considered during the designing process of wireless network protocol. To some sense, this problem determines the quality of service of the wireless network. Topology control can solve this problem effectively. Therefore, it is necessary to design effective topology control protocol. Topology control is to say, construct a sub-graph with some properties (e.g., connectivity, thin, low interference and so on) in an undirected graph associated with a wireless network. In topology control, one of the most important approaches is to construct dominating set (DS), especially connected dominating set (CDS).Based on a large amounts of researches and analyses of the present DS and CDS construction algorithms, we first design BMDS algorithm, BCDS algorithm and BCDSC algorithm under discrete beep model, where discrete beep model is an extremely rigorous local broadcast model depending only on carrier sensing, and it describes an anonymous broadcast network where the nodes do not need unique identifiers and have no knowledge about the topology of the network. And then, we give the DSS_MIS and DSS_CDS algorithm under SINR model, where SINR model is a more realistic interference model which accounts for interference generated by all nodes in the network. Absolutely, we analyze these algorithms respectively from the theoretical point.This thesis consists of five chapters. The first chapter simply introduces the background, status and the value of our research; the second chapter classifies and summarizes the current algorithms for dominating set and analyzes some classical algorithms. In the third chapter, we propose a distributed minimum dominating set construction algorithm under beep model with constant approximation ratio (BMDS) at first, which is a greedy scheme based on local domination degree (local domination degree is the number of the non-dominated neighbors of a node). And then, we design a maximal independent set (MIS) construction algorithm and a weakly CDS (WCDS) construction algorithm. Based on these two algorithms, we propose a CDS construction algorithm under beep model (BCDS). What's more, another novel algorithm for CDS construction is proposed with collision under beep model (BCDSC). A self-stabilizing system is a fault tolerant system that can tolerate and recover from transient faults with out external intervention. A wireless network, as a distributed system, usually faces a complex environment (topology changes frequently). Thus, self-stabilization becomes a basic request for protocol design in wireless networks. In order to ensure that the self-stabilizing algorithms can be applied to actual scenarios, interference is one of the most important challenges to be considered. Chapter four deals with both self-stabilizing and interference problems. Based on the plane division and coloring, we give a distributed self-stabilizing maximal independent set construction algorithm (DSS_MIS) under SINR model, then improve this algorithm and obtain a distributed self-stabilizing connected dominating set construction algorithm (DSS_CDS) finally. We summarize this thesis in chapter five and look forward to the future research work.