基于最大加权独立集的频谱分配算法

J4 ›› 2012, Vol. 34 ›› Issue (6): 158-162.

基于最大加权独立集的频谱分配算法

刘玉涛1,2,宋志群1,谭学治2

（1.中国电子科技集团公司第五十四研究所，河北石家庄 050081;2.哈尔滨工业大学通信技术研究所，黑龙江哈尔滨 150080）

收稿日期:2011-11-15 修回日期:2012-04-20 出版日期:2012-06-25 发布日期:2012-06-25
基金资助:
中国博士后科学基金资助项目（20110490988）;国家自然科学基金资助项目（61071104）

Spectrum Allocation Algorithm Based on Maximum Weighted Independent Set

LIU Yutao1,2,SONG Zhiqun1,TAN Xuezhi2

(1.The 54th Research Institute of CETC,Shijiazhuang 050081;2.Communication Research Center,Harbin Institute of Technology,Harbin 150080,China)

Received:2011-11-15 Revised:2012-04-20 Online:2012-06-25 Published:2012-06-25

摘要/Abstract

摘要：

Technology,Harbin 150080,China)〖WT〗〖ST〗〖JZ)〗〖HT5H〗摘〓要：〖HT5K〗动态频谱接入技术允许认知用户接入未授权的频谱，可以有效地提高频谱资源的利用率。频谱分配算法的时间开销和公平性是算法优劣的主要评价标准。本文从图论着色模型出发，构建了着色算法的评价体系及优化目标。针对用户间的公平性与分配的时间开销问题，在极大独立集的基础上提出了基于加权最大独立集的着色算法，获得了接近于最优的用户公平性，且该算法的时间开销等于信道数，与认知用户的数目无关。仿真分析验证了算法的正确性。

关键词: 认知无线电, 频谱分配, 图论, 效用, 独立集

Abstract:

The dynamic spectrum access technology can achieve nearoptimal spectrum utilization by allowing cognitive users sense and utilize available spectrum opportunistically. Time overhead and fairness are part of the key evaluation criteria for the spectrum allocation algorithms, and a naive spectrum assignment can lead to significant unfairness and system overhead. In this paper, based on graph coloring model, the evaluation system and optimization goals are established. From the maximal independent set, a novel graph coloring algorithm based on maximum weighted independent set (MWIS) is proposed. Theory and simulation analysis show that through MWIS algorithm we can obtain the nearoptimal total spectrum utility and fairness, and the time overhead for this algorithm is equal to the number of channels, which is far below the CSGC algorithm.

Key words: cognitive radio;spectrum allocation;graph theory;utility;independent set

刘玉涛1,2,宋志群1,谭学治2. 基于最大加权独立集的频谱分配算法[J]. J4, 2012, 34(6): 158-162.

LIU Yutao1,2,SONG Zhiqun1,TAN Xuezhi2. Spectrum Allocation Algorithm Based on Maximum Weighted Independent Set[J]. J4, 2012, 34(6): 158-162.

[1]	张策1，伊文敏2，白睿1，盛晟1，徐早辉1，高天翼1，王瞰宇1，苏嘉尧1. SRGM下失效数据集效用与验证分析[J]. 计算机工程与科学, 2020, 42(06): 1012-1020.
[2]	浦蓉, 邵剑飞, 胡常礼, 曲坤. 基于优化上界的高平均效用项集垂直挖掘算法[J]. 计算机工程与科学, 2020, 42(05): 931-937.
[3]	何登平1，2，3，何宗浩1,2，李培强1,2. 基于Spark的并行化高效用项集挖掘算法[J]. 计算机工程与科学, 2019, 41(10): 1723-1730.
[4]	蔡晨1,2，罗可1,2 . 融合BTM和图论的微博检索模型[J]. 计算机工程与科学, 2019, 41(08): 1512-1518.
[5]	何登平1,2,3，何宗浩1,2. 基于R-list的Top-K高效用项集挖掘算法[J]. 计算机工程与科学, 2019, 41(07): 1318-1324.
[6]	张云蕾，刘开华，马永涛，李洋. 基于多频段传感器辅助认知无线电网络的高能效传感器调度算法[J]. 计算机工程与科学, 2017, 39(08): 1438-1443.
[7]	林雪松1，杨万清1，夏元斗1，程松2. 基于认知的智能电网家域接入控制网络非合作博弈功率控制算法比较研究[J]. 计算机工程与科学, 2016, 38(12): 2529-2535.
[8]	龙敏，吴靓. 认知无线电网络中安全的协作频谱检测算法[J]. 计算机工程与科学, 2016, 38(10): 2045-2050.
[9]	刘觉夫，杨将，王建旭，胡静. 基于拍卖理论和高斯过程回归学习的频谱分配算法[J]. J4, 2016, 38(05): 914-920.
[10]	杨高明1，方贤进1，陆奎1，王静2. 面向函数依赖的隐私保护研究[J]. J4, 2015, 37(11): 2154-2161.
[11]	宋威，吉红蕾，李晋宏. 一种高效用项集并行挖掘算法[J]. J4, 2015, 37(03): 422-428.
[12]	孔得凯，吴克宇，韩方景，韩方剑. 认知无线电网络中基于信道跳频序列的异步交汇算法研究[J]. J4, 2014, 36(10): 1872-1879.
[13]	陈小惠，徐晶，刘威，程文青. 可变频宽无线网络中信道频谱分配与链路调度[J]. J4, 2014, 36(09): 1656-1661.
[14]	刘升1，陈志刚1,邝祝芳2. 认知无线电中结合差异性的免疫克隆优化频谱分配算法[J]. J4, 2014, 36(09): 1672-1677.
[15]	林选伟，吴谨. 基于交互式图论的目标边缘检测算法[J]. J4, 2014, 36(08): 1571-1575.