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

Spectrum Allocation Algorithm Based on Maximum Weighted Independent Set

作　　者：刘玉涛[1,2] 宋志群[1] 谭学治[2] 

机构地区：[1]中国电子科技集团公司第五十四研究所,河北石家庄050081 [2]哈尔滨工业大学通信技术研究所,黑龙江哈尔滨150080

出　　处：《计算机工程与科学》2012年第6期158-162,共5页Computer Engineering & Science

基　　金：中国博士后科学基金资助项目(20110490988);国家自然科学基金资助项目(61071104)

摘　　要：动态频谱接入技术允许认知用户接入未授权的频谱,可以有效地提高频谱资源的利用率。频谱分配算法的时间开销和公平性是算法优劣的主要评价标准。本文从图论着色模型出发,构建了着色算法的评价体系及优化目标。针对用户间的公平性与分配的时间开销问题,在极大独立集的基础上提出了基于加权最大独立集的着色算法,获得了接近于最优的用户公平性,且该算法的时间开销等于信道数,与认知用户的数目无关。仿真分析验证了算法的正确性。The dynamic spectrum access technology can achieve near-optimal spectrum utilization by allowing cognitive users sense and utilize available spectrum opportunistically. Time overhead and fair- ness 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 colo ring 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 pro- posed. Theory and simulation analysis show that through MWIS algorithm we can obtain the near-opti- mal 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.

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

分 类 号：TN929.5[电子电信—通信与信息系统]