Research On Connected Dominating Set Construction Algorithm In Cognitive Radio Network

Wireless spectrum is one of the most precious resources for wireless networks. With the fast growth of wireless networks, the unlicensed spectrum resource is more and more crowed, while the utilization of the licensed spectrum is relatively lower. People proposed Cognitive Radio Networks(CRNs) to improve the utilization of the licensed wireless spectrum. A CRN is a group of Unlicensed Users(or Cognitive Users, CUs) with licensed cognitive radio, which can get on well with Licensed Users(or Primary Users, PUs) in the same geographic area. PUs can active randomly and access licensed spectrum at any time according to their requirements. Each user in CRNs is equipped with cognitive radio, which admits CUs detecting whether there exist any idle licensed channels and change their operating parameters according to sensing results. CUs can access the idle channels without causing interference to PUs. Corresponding CUs must vacate all the related channels and move to another channels to avoid causing interference to PUs once these channels are reclaimed by PUs for their transmissions. The relative location of a CU to a PU varies with time due to the unpredictable activities of PUs. Therefore, the set of available channels(spectrum availability) for a CU dynamically changes along with the variations of time and space. We hope to apply the mature technologies and algorithms in traditional wireless networks to CRNs on account of the special advantages of the CRNs.Traditional wireless networks exploit virtual backbones to prolong the network lifetime, which inspired us try to construct virtual backbones in CRNs. It is a representative technique to make use of a connected dominating set(CDS) constructing a virtual backbone of wireless network to realize topology control, thereby prolonging the lifetime of a network. Connected dominating set has been used as the basic structure for the MAC, multicast/broadcast, location-based routing,energy conservation, resource discovery protocol, etc. Therefore, constructing CDSs with different natures in CRNs is particularly important. In this thesis, we study the problem of constructing CDSs with different natures in CRNs. However, the network becomes invalid easily due to dynamic activities of PUs. Thus, it poses new challenges in constructing CDSs of different natures in CRNs.This thesis uses connected dominating set in CRNs as the theoretical basis for the research,and carefully studies, analyzes and summarizes the traditional and existing methods and hot spot(such as current study situation, network models, algorithm types, and typical algorithmic ideas)on the construction of connected dominating sets. Then we design and develop the algorithms for connected dominating set in CRNs with different natures and performances. We adopt theoretical analysis of mathematics, graph theory to guarantee the correctness of the results in theory andthe feasibility in practice. In the third chapter, based on the theory of Breadth-first Search(BFS),two diameter-limited connected dominating set(CDS) algorithms are proposed in the UDG,which constrain the path length of message delivery and decrease the energy consumption. In the fourth chapter, we use the idea of edge-weight-maximum with first priority to choose the dominators and design a three-phased centralized algorithm to achieve three sub-targets. In the process of the CDS construction, we utilize greedy strategy to construct CDS with maximum lifetime in cognitive radio networks(CRNs). In fifth chapter, inspired by the definition of the convex hull, we design a distributed algorithm to construct a CDS with maximum lifetime,which improves the success probability of channel switching by choosing the node pairs with the most common available channels as dominators to increase the lifetime of the CDS. Theoretical analysis demonstrates the correctness and superiority of the algorithms. Currently, the study of connected dominating sets in a cognitive radio network is still the focus of the research community. In this thesis, the first chapter analyzes the current study situation and deficiencies,and finds out our current study direction. The sixth chapter summarizes this thesis, and presents the future work.