Maximizing Lifetime of Connected-Dominating-Set in Cognitive Radio Networks

Abstract : 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.
Type de document :
Communication dans un congrès
Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.316-330, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_25〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01531957
Contributeur : Hal Ifip <>
Soumis le : vendredi 2 juin 2017 - 11:23:15
Dernière modification le : mercredi 21 février 2018 - 14:46:02
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 07:40:39

Fichier

978-3-642-30054-7_25_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Zhiyong Lin, Hai Liu, Xiaowen Chu, Yiu-Wing Leung, Ivan Stojmenovic. Maximizing Lifetime of Connected-Dominating-Set in Cognitive Radio Networks. Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.316-330, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_25〉. 〈hal-01531957〉

Partager

Métriques

Consultations de la notice

71

Téléchargements de fichiers

15