###
Journal of Software:2012.23(1):122-139

认知无线电网络频谱分配与协作集划分算法
杨威,班冬松,梁维发,窦文华
(国防科学技术大学 计算机学院,湖南 长沙 410073;Research School of Computer Science, Australian National University, Canberra, ACT 0200, Australia)
Algorithms for Joint Spectrum Allocation and Cooperation Set Partition in Cognitive Radio Networks
YANG Wei,BAN Dong-Song,LIANG Wei-Fa,DOU Wen-Hua
(School of Computer, National University of Defense Technology, Changsha 410073, China;Research School of Computer Science, Australian National University, Canberra, ACT 0200, Australia)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 4011   Download 3692
Received:October 18, 2010    Revised:July 01, 2011
> 中文摘要: 针对协作认知无线电网络中较为复杂的多主用户与多次级用户共存场景,提出联合频谱分配与协作集划分问题,并将该问题形式化描述为整数0-1 非线性规划问题,证明其是NP-hard 的.首先,设计了集中式的遗传算法 CGA(centralized genetic algorithm)对问题求解,对该算法进行齐次有限马尔可夫链建模并对其全局收敛性进行了分析;随后,提出了一种包含两阶段的分布式遗传算法DGA(distributed genetic algorithm),包括基于最小支配集的分簇与频谱预分配阶段和簇间协作集协商与簇内适应值精化阶段.此外,还提出一种快速收敛的DGA 算法(fast-convergent DGA,简称FDGA)缩短分布式算法运行时间.仿真实验结果表明,根据能反映出算法性能的适应值结果对各算法进行比较:(1) 小规模网络下CGA 获得的解平均为通过穷举算法得到的最优值的92%;(2) 随着网络规模的扩大,由于CGA 搜索空间增大,DGA,FDGA 在达到相同停机条件时获得的适应值比CGA 提高约20%;(3) 与DGA 相比,FDGA 虽能得到与DGA 相近的结果,但却大大缩短了算法收敛的时间,更适应于大规模网络应用.
Abstract:The coexistence of multi-primary users and multi-secondary users in cooperative cognitive radio networks motivate the study to propose a joint spectrum allocation and cooperation set partition problem, which so far has not been addressed before. The problem is formulated as a 0-1 integer non-linear programming model. Due to its NP-hardness, the study proposes a suboptimal Centralized Genetic Algorithm (CGA) to show its convergence by modeling it as a homogeneous finite Markov chain. The study then extends CGA to a fully Distributed Genetic Algorithm (DGA) that consists of two phases. The core techniques include a minimum dominate set based cluster partition, a spectrum pre-allocation algorithm in phase 1, and an inter-cluster cooperation set negotiation and cluster fitness refinement algorithm in phase 2. A Fast-Convergent DGA (FDGA) is also devised to reduce the system configuration time. Extensive experiments by simulations demonstrate that in terms of the fitness that reflects the performance of the proposed algorithms: (1) CGA is shown to perform as well as 92% of the optimal solution by brutal search under small network sizes; (2) As the network size increases, due to the massive search space CGA has to deal, DGA and FDGA instead outperform CGA with 20% on average when achieving the same algorithm termination condition; (3) FDGA delivers similar results as DGA while reducing the configuration time significantly, which is more suitable for large-scale networks.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60603061, 60903223) 国家自然科学基金(60603061, 60903223)
Foundation items:
Reference text:

杨威,班冬松,梁维发,窦文华.认知无线电网络频谱分配与协作集划分算法.软件学报,2012,23(1):122-139

YANG Wei,BAN Dong-Song,LIANG Wei-Fa,DOU Wen-Hua.Algorithms for Joint Spectrum Allocation and Cooperation Set Partition in Cognitive Radio Networks.Journal of Software,2012,23(1):122-139