TY - GEN
T1 - Maximizing lifetime of connected-dominating-set in cognitive radio networks
AU - Lin, Zhiyong
AU - LIU, Hai
AU - CHU, Xiaowen
AU - LEUNG, Yiu Wing
AU - Stojmenovic, Ivan
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012
Y1 - 2012
N2 - Connected-dominating-set (CDS) is a representative technique for constructing a virtual backbone of wireless networks. Most of existing works on CDS aim at minimizing the size of the CDS, i.e., constructing the minimum CDS (MCDS), so as to reduce the communication overhead over the CDS. However, MCDS may not work well in cognitive radio networks (CRNs) where communication links are prone to failure due to the unpredictable activities of primary users. A MCDS without consideration of stochastic activities of primary users easily becomes invalid when the primary users reclaim the licensed spectrum. In this work, we assume that the activities of primary users follow the exponential distribution. Our problem is to maximize the lifetime of the CDS while minimizing the size of the CDS, where the lifetime of a CDS is defined as the expected duration that the CDS is maintained valid. We show that the problem is NP-hard and propose a three-phase algorithm. Our basic idea is to apply a pruning-based approach to maximize the lifetime of the CDS. Given a CRN, we prove that our algorithm can compute a CDS such that i) the lifetime of the CDS is maximized (optimal); and ii) the size of the CDS is upper-bounded. To the best of our knowledge, it is the first time in the literature that CDS in CRNs is studied and an effective algorithm is proposed.
AB - Connected-dominating-set (CDS) is a representative technique for constructing a virtual backbone of wireless networks. Most of existing works on CDS aim at minimizing the size of the CDS, i.e., constructing the minimum CDS (MCDS), so as to reduce the communication overhead over the CDS. However, MCDS may not work well in cognitive radio networks (CRNs) where communication links are prone to failure due to the unpredictable activities of primary users. A MCDS without consideration of stochastic activities of primary users easily becomes invalid when the primary users reclaim the licensed spectrum. In this work, we assume that the activities of primary users follow the exponential distribution. Our problem is to maximize the lifetime of the CDS while minimizing the size of the CDS, where the lifetime of a CDS is defined as the expected duration that the CDS is maintained valid. We show that the problem is NP-hard and propose a three-phase algorithm. Our basic idea is to apply a pruning-based approach to maximize the lifetime of the CDS. Given a CRN, we prove that our algorithm can compute a CDS such that i) the lifetime of the CDS is maximized (optimal); and ii) the size of the CDS is upper-bounded. To the best of our knowledge, it is the first time in the literature that CDS in CRNs is studied and an effective algorithm is proposed.
KW - cognitive radio networks
KW - connected-dominating-set
KW - lifetime
UR - http://www.scopus.com/inward/record.url?scp=84861675907&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-30054-7_25
DO - 10.1007/978-3-642-30054-7_25
M3 - Conference proceeding
AN - SCOPUS:84861675907
SN - 9783642300530
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 316
EP - 330
BT - NETWORKING 2012 - 11th International IFIP TC 6 Networking Conference, Proceedings
T2 - 11th International IFIP TC 6 Networking Conference, NETWORKING 2012
Y2 - 21 May 2012 through 25 May 2012
ER -