Maximizing Lifetime of Connected-Dominating-Set in Cognitive Radio Networks
Maximizing Lifetime of Connected-Dominating-Set in Cognitive Radio Networks
复制标题
DOI：
10.1007/978-3-642-30054-7_25
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Zhiyong Lin;Hai Liu;Xiaowen Chu;Y. Leung;I. Stojmenovic
中科院分区：
文献类型：
--
作者：
Zhiyong Lin;Hai Liu;Xiaowen Chu;Y. Leung;I. Stojmenovic
连接支配集（CDS）是构建无线网络虚拟骨干网的代表性技术。大多数现有的CDS工作旨在最小化CDS的大小，即构造最小CDS（MCDS），以减少CDS上的通信开销。然而，MCDS 在认知无线电网络 (CRN) 中可能无法很好地工作，因为在认知无线电网络中，由于主要用户的不可预测的活动，通信链路很容易出现故障。当主要用户收回许可频谱时，不考虑主要用户随机活动的MCDS很容易失效。在这项工作中，我们假设主要用户的活动遵循指数分布。我们的问题是最大化 CDS 的生命周期，同时最小化 CDS 的大小，其中 CDS 的生命周期定义为 CDS 保持有效的预期持续时间。我们证明该问题是 NP 困难的，并提出了一种三相算法。我们的基本想法是应用基于修剪的方法来最大化 CDS 的生命周期。给定一个 CRN，我们证明我们的算法可以计算 CDS，使得 i) CDS 的生命周期最大化（最优）； ii) CDS 的大小是有上限的。据我们所知，这是文献中首次研究 CRN 中的 CDS 并提出有效的算法。
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.