动态频谱分配的连通分支并行处理

覃玉荣 胡虹梅

（广西大学计算机与电子信息学院，广西 南宁 530004）

引 言

认知无线电是有效解决当前频谱资源紧缺问题的最佳方案［1-2］。为适应快速时变的认知无线电环境，动态频谱分配是必然要求。如何快速无干扰地分配频谱资源，是认知无线电频谱分配算法研究的关键。

图论着色模型是目前国内外动态频谱分配研究的热点模型之一，其特点是将认知无线电用户所组成的网络拓扑结构抽象成图，则频谱分配问题可转化为对图的着色研究。2005年，有学者在IEEE车载技术会议（VTC）上提出了避免干扰的List-Coloring频谱分配算法，研究目标为最大化系统频段分配数［3］。同年5月，其他学者在IEEE Communica-tions提出了颜色敏感的图论着色（CSGC）算法［4］，该算法考虑干扰和频带的差异性，以不同效益函数为分配目标来提高频谱利用率。2010年，Zhang Beiwei等在频谱分配过程中引入群智能技术，探究系统带宽收益与认知用户接入公平性之间的均衡［5］。此外，还有学者提出了局部议价算法，基于服务需求的分配算法等［6-11］。

目前国内外基于图论着色模型算法的基本特点是:在频谱分配过程中，按照效益目标函数逐次分配频段给满足条件的某单个认知用户，因此，存在时间开销过大瓶颈问题。有学者采用频谱并行分配（SAP）算法，即同时分配正交频带以尝试缩短分配的循环周期，在一定程度上缩短了系统的频谱分配时间开销［12］。但该方法分配频谱时仍然依次考虑整个系统中的认知用户，这是制约系统频谱分配速率有效提高的一个重要因素。

为有效解决上述瓶颈问题，引入连通分量理论，结合并行原理，提出了一种基于图论着色模型的快速频谱分配新方法:将系统拓扑图分解为无干扰的连通分支，用某种图论算法并行处理各连通分支的频谱分配，使多个无干扰的用户同时获取频谱，在保证原算法系统收益不变的基础上，大大提高了整个系统的频谱分配速率，能够有效解决目前基于图论模型的分配算法时间开销过大问题。利用所提的连通分支并行处理方法对SAP算法进行实例应用探讨。

1.连通分支并行方法

1.1 频谱分配的图论基本原理

频谱分配图论着色模型将认知用户的频谱分配问题抽象成图G=（V，E，S）对顶点的着色问题。其中顶点集合V= ｛vn｜n=1，2，…，N｝表示网络中的所有认知用户；边集E表示网络中各顶点之间的干扰约束关系，若vn和vk有边相连，表示认知用户vn和vk同时使用相同频带时会产生干扰；可选颜色列表S表示各认知用户的可用频谱集合。

在无向图中，如果从顶点vn存在到达顶点vk的路径，则称顶点vn和vk连通［13］。对应于连通关系，存在着图G 的顶点集分划 ｛V1，V2，…，VW｝，使得图G中任意两个顶点vn和vk连通当且仅当vn和vk属于同一个分块Vw（1≤w≤W）。子图G（Vi）中任意两个顶点都是连通的，并且子图G（Vi）中的顶点和G（Vj）的顶点（i≠j）绝不会连通，则子图G（Vi）是拓扑图G的极大连通子图，称为图G的连通分支。

认知无线电通信网络系统中干扰是相互的，若vn使用某频带m会对vk产生干扰，则vk使用频带m也会对vn产生干扰，因此系统的干扰拓扑图是一个无向图，根据连通性原理可以将其分解成多个连通分支。

1.2 连通分支的求解

假设C= ｛cn，k｜cn，k∈ ｛0，1｝｝N×N是无向图G 的布尔邻接矩阵，其矩阵元素cn，k=1，当且仅当顶点vn与顶点vk之间有直接相连的边。邻接矩阵反映了拓扑图G的所有信息，可以从中判定图的连通性质。根据图的连通性原理，设计连通分支的求解步骤为:

第一步:根据图的邻接矩阵，计算传递闭包矩阵= （C+I）∧N

第二步:计算图的连通矩阵CMN×N= ｛cmi，j｜cmi，j∈ ｛0，1｝｝N×N，当且仅当c+i，j≠0时cmi，j=1，表示（i，j）之间有路径相连通。

第三步:求构造矩阵DM，其第i行包含了顶点vi所连通的所有顶点名称，根据构造矩阵可计算出各连通分支包含的顶点以及相应的连通子图。

1.3 连通分支并行处理的提出

在认知无线电网络中，连通分支可以反映认知用户之间的干扰约束关系，分属于不同连通分支的认知用户之间不会存在直接或者间接的干扰约束，对某个连通子图的着色不会影响其他子图的着色。因此，提出连通分支并行处理方法:同时为W 个连通分支分配频谱资源，以提高算法的收敛速度。

处理流程如图1所示。

图1 连通分支并行处理流程图

连通分支并行处理方法的性能特点:

1）通用性强。从图1可知:系统总拓扑图G的分解于分配频谱前完成，故可用不同的分配算法同时为各连通分支分配频谱资源，这些算法包括现有图论模型下的List-Coloring算法、CSGC算法、SAP算法等。该处理方法能结合不同的图论算法来有效分配频谱。

2）系统带宽收益较大。设各连通分支对应的最优分配矩阵分别为A1，A2，…，AW，由于各连通分支内的频谱分配是独立进行的，相互之间不会产生任何干扰，因此，系统总拓扑的最优分配矩阵A与（A1，A2，…，AW）T等价，即 A= （A1，A2，…，AW）T.采用该方法分配频谱不会造成系统带宽收益的损失。

3）时间开销较小。利用该方法，在每次的分配循环中都可以同时对图G的W 个连通子图完成一次频谱分配，频谱分配的时间开销取决于各连通分支所需分配时间的最大值，所有分支完成分配的时间开销为T连通=，远小于顺序分配W 个连通子图所需要的时间T总=Tw.其中，Tw为连通分支G（Vw）分配频谱的时间开销。

2.连通分支并行方法应用实例

以SAP算法为研究对象，探讨连通分支并行方法的实例应用，验证其有效性。假设在研究区域的一个分配周期内，认知系统的网络拓扑保持不变，空闲频谱资源可分成一系列正交子频带，频带间无干扰。SAP算法基于CSGC研究多个正交子频带的同时分配，一定程度上提高了频谱分配的收敛速度。

基于SAP算法的连通分支并行处理应用实例的基本原理是:依据系统内认知用户之间的干扰拓扑图G，按照连通分支求解算法得到图G的各个连通分支G（Vw），1≤w ≤W，对于每个连通分支G（Vw），根据SAP算法的效益函数和分配准则并行分配频谱资源。

算法流程如图2所示。

该实例算法包含双重并行:第一，连通分支的并行。由于对某个连通分支内的认知用户分配频谱时不会对其他分支造成干扰，因此，各连通分支内的频谱分配可以同时实施；第二，频带的并行。对单个连通分支而言，M个正交子频带可以并行分配给该连通分支内的认知用户，相互之间无干扰影响。这样，每次循环至多能同时对图G的W 个顶点完成一次资源分配，分配的收敛时间为单个连通分支完成分配所需时间的最大值，而SAP算法每次循环只能对图G的一个顶点完成一次频谱分配，其时间开销为系统总拓扑完成分配所需要的时间，即各个连通分支完成分配所需时间的总和。因此，基于SAP算法的连通分支并行处理应用实例分配频谱的时间开销远小于原SAP算法，进一步有效提高了频谱分配的收敛速度。

图2 算法流程图

3.仿真结果与分析

现对SAP算法和以SAP算法为研究对象的连通分支并行处理应用实例（以下简称连通分支算法）进行MATLAB仿真。采用的分配准则为协作式最大化系统带宽总和（CMSB）准则和非协作式最大化系统带宽总和（NMSB）准则［12］。仿真参数如表1、表2所示。为检验算法的准确性，仿真结果取1000次随机拓扑下频谱分配结果的均值。

表1 仿真参数

表2 频带效益等级

3.1 时间开销

为简化比较，假设每次分配循环的执行时间为t，则算法的时间开销为总的分配循环次数乘以t.图3是SAP算法与连通分支算法各自时间开销占CSGC算法时间开销的比例，从图中可以看出，连通分支算法的比例曲线显著低于SAP算法，表明连通分支算法的时间开销低于SAP算法。

图3 频谱分配时间开销

3.2 系统收益

算法带来的系统带宽收益用系统在一个分配周期内的带宽总收益（单位为10kbit／period）来衡量，可表示为·bn，m，仿真结果如图4所示。从图中可以看出，在CMSB、NMSB准则下，两种算法的系统带宽收益均重合为一条曲线，说明连通分支算法得到的系统带宽总收益与SAP算法的收益相同。

以上仿真结果表明:基于SAP算法的连通分支并行处理应用实例的系统效益与原SAP算法相同，但是却进一步显著降低了频谱分配的时间。

图4 系统带宽总收益

该应用实例的探究结果表明:通过并行处理连通分支实现时间开销降低的方法是快速有效的，且能够保证算法原有的系统效益。

4.结 论

采用并行原理与图论连通分量理论，提出了一种基于连通分支并行处理的快速频谱分配新方法，有效解决了目前动态频谱分配图论算法普遍存在时间开销过大的瓶颈问题。该方法能结合不同的图论算法来有效分配频谱资源，其特点是在一次分配过程中，同时并行处理多个连通分支内的认知用户，在不影响系统原有效益的前提下，大大缩短了整个系统频谱分配的时间。最后以图论的SAP算法为研究对象，对所提出的连通分支并行处理方法进行了应用验证。仿真结果表明:采用连通分支并行处理方法的SAP算法，其系统效益与原SAP算法一致，但显著降低了频谱分配的时间开销，更加适应快变的认知无线电环境。

［1］MITOLA J，GERALD Q，MAGUIR J R.Cognitive radio:making software radios more personal［J］.IEEE Personal Communications，Aug，1999:13-18.

［2］王 超，刘 涛，杜利平，等.一种新的认知无线电主用户信号识别方法［J］.电波科学学报，2009，24（6）:1119-1123.WANG Chao，LIU Tao，DU Liping，et al.A new method for recognizing the primary user in cognitive radio［J］，Chinese Journal of Radio Science，2009，24（6）:1119-1123.（in Chinese）

［3］WANG Wei，LIU Xin.List-coloring based channel allocation for open-spectrum wireless networks［C］／／The 62nd IEEE Vehicular Technology Conference.［s.n.］:May 2005，1:690-694.

［4］ZHENG Haitao，PENG Chunyi.Collaboration and fairness in opportunistic spectrum access［C］／／IEEE International Conference on Communication.［s.n］:May 2005，5:3132-3136.

［5］ZHANG Beiwei，HU Kunyuan，ZHU Yunlong.Spectrum allocation in cognitive radio networks using swarm intelligence［C］／／Second Intenational Conference on Communication Software and Networks，2010.Feb.2010:8-12.

［6］CAO L，ZHENG H.Distributed spectrum allocation via local bargaining［C］／／IEEE Sensor and Ad Hoc Communications and Networks 2005，Sept.2005:475-486.

［7］PENG Chunyi，ZHENG Haitao ZHAO Ben Y..Utilization and fairness in spectrum assignment for opportunistic spectrum access［J］.Mobile Networks and Applications，May 2006，11（4）:555-576.

［8］HE Shibiao，ZHANG Xinchun，GE Lijia，et al.Research of dynamic spectrum allocation based on service demand［C］／／2010Second International Conference on Networks Security Wireless Communications and Trusted Computing，June 2010，2:348-351.

［9］ZHANG Jianwu，ZHAO Qi，ZOU Jingyuan.Advanced graph-coloring spectrum allocation algorithm for cognitive radio［C］／／2009International Conference on Wireless Communications，Networking and Mobile Computing，Sep.2009:1-4.

［10］GE Yang，SUN Jun，SHAO Shixiang，et al.An improved spectrum allocation algorithm based on proportional fairness in cognitive radio networks ［C］／／IEEE International Conference on Communication Technology（ICCT），Dec.2010:742-745.

［11］樊 路，刘玉涛，谭学治，等.认知无线电中基于极大独立集的频谱分配算法［J］，科学技术与工程，2009，9（16）:4645-4648.FAN Lu，LIU Yutao，TAN Xuezhi，et al.Spectrum allocation algorithm based on maximal independent set in cognitive radio networks［J］.Science Technology and Engineering，Aug.2009，9（16）:4645-4648.（in Chinese）

［12］廖楚林，陈 劼，唐友善，等.认知无线电中的并行频谱分配算法［J］.电子与信息学报，2007，29（7）:1608-1611.LIAO Chulin，CHEN Jie，TANG Youxi，et al.Parallel algorithm of spectrum allocation in cognitive radio［J］.Journal of Electronics＆Information Technology.2007，29（7）:1608-1611.（in Chinese）

［13］徐俊明.图论及其应用［M］.第2版.合肥:中国科学技术大学出版社，2004.8.

［14］廖楚林.认知无线电系统的频谱分配算法研究［D］.成都:电子科技大学硕士学位论文，2007.