Efficient Connected Dominating Set Construction with Maximum Lifetime in the Cognitive Radio Networks

摘要

Connected dominating set (CDS) is the most representative technology for constructing a virtual backbone in wireless networks and plays an important role in wireless applications including broadcasting, routing and so on. In a cognitive radio networks, the lifetime and efficiency are two important indices for measuring CDS algorithms due to the random activities of primary users (PUs). However, to the best of our knowledge, the existing algorithms for CDS construction in CRNs ignore the execution effectiveness instead of lifetime. In this paper, we propose a four-phase distributed algorithm to maximize the lifetime of CDS while guaranteeing the effectiveness of the algorithm. The proposed algorithm terminates in O(N3log N) timeslots, which is more effective than that of O(N4).