基于Kuhn-M unkres算法保证认知用户QoS的动态频谱分配

叶培青，李 莉，周小平，陈小丹

（上海师范大学信息与机电工程学院，上海 200234）

基于Kuhn-M unkres算法保证认知用户QoS的动态频谱分配

叶培青，李 莉，周小平，陈小丹

（上海师范大学信息与机电工程学院，上海 200234）

本算法采用图论方法解决认知无线网络动态频谱分配（DSA）问题.首先，根据认知用户的服务质量（QoS）以及空闲信道的状态，分别为认知用户和信道划分优先权.然后，提出一种新的计算方式预计认知用户使用信道可获得的带宽效益.最后，将划分优先权后的认知用户、信道建立二分图，将带宽效益作为图的权重.在兼顾考虑认知用户的带宽效益和频谱利用率的前提下，使用Kuhn-Munkres算法将信道分配给认知用户.实验仿真结果表明，本算法可以同时优化带宽效益和频谱利用率，在认知用户等待分配信道时间方面也能取得较好服务质量要求.

动态频谱分配；Kuhn-Munkres算法；优先权

0 引 言

认知无线电被认为是解决有限的频谱资源利用率不高问题的主要技术之一.动态频谱分配是认知无线电的一项关键技术.基于频谱池原理［1］的动态频谱分配研究主要集中在带宽效益和／或频谱利用率方面.802.22是首个提出将认知无线电技术应用到数字电视的工作组.为满足现实无线通信的技术需求，802.22工作组针对认知无线电技术制定了几个标准：在IEEE802.11a标准中，无线局域网的产品在物理层应该能提供54 Mbps的传输速率；在IEEE802.11n标准中，要提供600 Mbps的传输速率.在IEEE802.22标准中建议，无线区域网每条信道的传输速率要达到22 Mbps.这几类标准均对传输速率提出了要求，在可用频谱资源有限的前提下，提高带宽效益和频谱利用率是增大传输速率的一个解决方法.但是带宽效益和频谱利用率受到媒体接入控制和物理层开销的限制［2］，比如认知用户之间的相互竞争和干扰造成信道不可用，路径损耗降低了总带宽效益等.目前国内外已有一些关于带宽效益和频谱利用率的优化算法提出：

Swami等在文献［3］中提出了一种利用图论分配信道的算法，首次提出了将认知用户和信道综合考虑的想法.具体为：首先根据每条信道可以承受的传输功率给信道分配优先权，然后根据吞吐量和误码率对认知用户划分优先权，最后利用匈牙利算法扩大增广路径的方法以增多分配的认知用户的信道数.该文(匈牙利算法）可以提高频谱的利用率，但是不能提高带宽效益.

Im等在文献［4］中提出基于信噪比干扰管理机制的贪婪算法来完善动态频谱分配的算法.用干扰管理机制来解决基站(BSs）之间的干扰.该文(贪婪算法）可以取得局部带宽效益的最大值.在限制干扰后，该文算法也可以提高频谱利用率，但是信噪比的门限很难确定.因为信噪比的门限在不同的传输环境里是不同的.所以，该算法只能应用在特定的传输场合.

Xu等在文献［5］中将吞吐量作为带宽效益，并提出了一种有效的信道再分配机制.文献［5］的实验仿真结果表明，将认知用户和信道结合考虑可以在带宽效益和频谱利用率方面取得更好的效果.

本算法以提高带宽效益和频谱利用率为主要目标，综合上述已有算法的优点和不足，采用集中式网络结构，设计了一种结合考虑认知用户和信道的基于图论的动态频谱分配，给出一种新的计算方式来估计信道的带宽效益.本算法可以应用在无线区域网(WRAN）环境下.WRAN是面向无线宽带(远程）接入，面向独立分散、人口稀疏的区域.WRAN网络内数据传输距离可以比较远，与市区相比传输时受其他无线电干扰小.WRAN的应用环境决定了使用无线区域网通信的用户传输数据时间长短的差异较大，并且数据传输时路径损耗相对简单的特点.本算法主要根据这两个特点设计，用于提高动态频谱分配中带宽效益和频谱利用率问题，保证认知用户的QoS要求.

1 基于认知用户QoS划分优先权

在多用户传输场景中，认知用户在环境干扰、传输距离、发送数据量等方面各不相同，对认知用户分类，找到合适的信道，以提高认知用户可以获得的带宽效益.假设当前有M个认知用户申请发送数据.

1.1 划分策略

将认知用户发送数据时需要占用信道的时间作为认知用户QoS要求.认知用户优先权的划分基于认知用户QoS要求，M个认知用户传输数据的平均时间作为划分的门限值.

设第i(1≤i≤M）个认知用户需要发送数据包的个数为Numi，每个数据包包含的固定比特数为I，数据传输速率为R(Mbps），数据传输的信道带宽B(MHz）；发送信号的传输距离di(km）.在不计干扰情况下，第i个用户需要的传输时间可表示为式(1）：

所有认知用户发送数据的平均传输时间如式(2）：

若ti＜，划分认知用户i的优先权为CR0，若ti≥，划分认知用户i的优先权为CR1.优先权为CR1的认知用户比优先权为CR0的认知用户需要发送更多的数据或者更长的传输距离，所以优先权为CR1的认知用户占用信道的时间长于优先权为CR0的认知用户.规定CR1的优先级高于CR0.

1.2 认知用户的优先权管理

优先权为CR1的认知用户所需的传输时间较长.为了保证所有认知用户的带宽效益，优先权为CR1的认知用户需要比优先权为CR0的认知用户更好的信道.因此频谱管理应该基于这样的策略：

a） 缩短认知用户竞争信道的等待时间；

b） 保证对所有认知用户的公平性；

c） 单个认知用户不会长时间占用信道.

2 信道的优先权分配

信道优先权的划分是基于可用信道状态及传输路径损耗.

2.1 可用信道状态

将频谱池中空闲频谱划分为N个相互正交的频带，每一条带宽为B的频带对应1条信道.频谱池中的信道k(1＜k＜N）有2个相邻信道，定义3种可用信道状态，记为j：j＝ 1，表示认知用户只能使用当前信道k；j＝ 2，表示认知用户能使用当前信道k以及相邻信道(k-1）或(k＋1）；j＝ 3，表示认知用户能使用信道(k-1）、k和(k＋1）.

在所受背景噪声相同的情况下，根据香农定理，信道能够传输的最大信息速率正比于带宽大小.在可用信道状态j＝3时，可以发送更多的数据量，承受更大的发送功率.规定：当把信道k分配给1个认知用户，是指把信道k和相邻的可用信道一起分配给认知用户，表示为认知用户使用信道kj，j表示可用信道数，j＝ 1， 2，3.

2.2 传输路径损耗

Hata模型通常用于路径损耗的建模.可以证明：用Hata模型建模时传输距离是影响路径损耗的主要原因，频带内载频的不同对路径损耗影响比较小，为简便计算，本算法认为路径损耗只由传输距离决定.

2.3 信道优先权分配

在集中式网络结构中，设基站的覆盖半径为D，将它划分为( 0，D／3）、(D／ 3，2D／3）、(2D／ 3，D）3块.在IEEE 802.22标准中，基站的覆盖半径为40～100 km.记在这3个范围内，信号距离基站的平均半径为Dm，m∈｛ 1， 2，3｝.

设L(di）表示认知用户i发送信号在传输距离为di时的路径损耗，S／N0是接收端处的信噪比.认知用户i使用信道kj的带宽效益定义为：

用βjm表示信号传输距离为平均半径Dm、分别在3种可用信道状态j∈｛ 1， 2，3｝下的带宽效益，即βjm＝j×B×log2(1＋S／N0）／L(Dm），可计算3×3＝9个带宽效益，表示认知用户在不同信道状态数和不同平均传输距离下获得的带宽效益.

根据βjm值的大小，取3个大的βjm所对应的可用信道优先权划分为T1，3个小的βjm所对应的可用信道优先权划分为T0.规定T1的优先权高于T0.

中间剩下的3个βjm对应的那部分信道被分配为优先权T0和T1.当优先权为CR1的认知用户数多于优先权为T1的信道数时，该3个βjm所对应的这部分信道作为优先权为T1的信道，反之，作为优先权为T0的信道.这样的信道优先权管理可以灵活地为不同优先权的认知用户分配信道，增大认知用户可以获得的总带宽效益.

3 Kuhn-Munkres算法实现信道分配

目标是同时提高带宽效益和频谱利用率，在认知用户等待分配信道时获得更好的QoS要求.

建立图G＝(S，C，B）.其中，S(1×M）表示申请发送数据的认知用户矩阵，每一个元素表示1个认知用户；C(1×N）表示频谱池中空闲的授权信道矩阵，每一个元素表示1条空闲信道.B(M×N）表示效益矩阵，每一个元素bi，kj可以用公式(3）计算获得，表示认知用户i使用信道k和相邻信道后获得的带宽效益.图G是对一次分配情况的描述，图G包括申请发送数据的认知用户数、空闲信道数以及认知用户使用信道后可以获得的带宽效益，以便于用图论的方法解决实际的频谱分配问题.用矩阵A(M×N）表示图G的分配矩阵.矩阵A是针对图G所反应的认知用户、信道以及带宽效益情况，采用动态频谱分配算法后表明哪一条信道分配给哪一个认知用户的矩阵.

Kuhn-Munkres(KM）算法可以获得在完备匹配下的最大权分配.完备匹配是指将信道全部分配给认知用户.最大权分配是指权重最大，指在分配信道后所有认知用户可以获得的带宽效益和最大.

在获得带宽效益方面，优先权为T1的信道要优于优先权为T0的信道.为了缩短认知用户传输数据时占用信道的时间和其他申请发送数据的认知用户等待分配信道的时间，规定优先权为CR1的认知用户只能使用优先权为T1的信道，优先权为CR0的认知用户可以使用多余的优先权为T1的信道和优先权为T0的信道.在一次分配管理中，使用KM算法将优先权为T1的信道分配给优先权为CR1的认知用户，再将多余的优先权为T1的信道和优先权为T0的信道分配给优先权为CR0的认知用户.表达式(4）和(5）代表了本动态频谱分配算法要取得的目标.

B＿benefit表示M个认知用户的带宽效益和.C＿fairness表示频谱利用率，是被分配信道和空闲信道的比值.ai，k表示分配矩阵A的任意元素.ai，k∈｛ 0，1｝代表分配结果.当ai，k＝1时，表示信道k分配给认知用户i；当ai，k＝0时，表示信道k不分配给认知用户i.bi，kj表示认知用户i被分配信道k和相邻信道后可以获得的带宽效益.在图论中，1条信道只能被分配给1个认知用户.所以，通过KM算法，认知用户之间在发送数据时不会相互干扰.

4 基于KM算法的动态频谱分配步骤

在集中式网络结构中，基站接收来自主用户和认知用户的信息：当前有M个认知用户申请发送数据，N条空闲信道，每一个认知用户要传输的距离和发送数据包的个数.

步骤1 优先权划分：

根据接收到的信息，基站分别对认知用户和信道分配优先权.

步骤2 频谱管理规定：

规定优先权为CR1的认知用户只能使用优先权为T1的信道，优先权为CR0的认知用户可以使用多余的优先权为T1的信道和优先权为T0的信道.

步骤3 最优化分配：

在频谱分配过程中，兼顾带宽效益和频谱利用率.利用最优分配KM算法将空闲的信道分配给认知用户，获得分配矩阵.

5 仿真分析

本算法讨论在无线区域网(WRAN）环境下的动态频谱分配，部分仿真参数设置如表1所示.本算法按照IEEE802.22标准对WRAN的相关规定，带宽取值为22 MHz，基站的覆盖范围取值为100 km.

在仿真中，比较了贪婪算法、基于KM算法实现的动态频谱分配和文献［3］提出的基于匈牙利算法实现的动态频谱分配.图1是对3种算法的带宽效益比较.在频谱池信道数多于认知用户数的前提下，随着认知用户数增多，3种算法下带宽效益都增大.图1中，贪婪算法是在没有干扰的前提下做的仿真，获得局部最大的带宽效益.匈牙利算法是可以获得最大匹配的算法，但是不能获得最大的带宽效益.仿真可得，本算法在带宽效益方面可以接近贪婪算法.

图1 3种算法的带宽效益比较

表1 仿真参数设置

但在认知用户数为15时，本算法的带宽效益有所下降，匈牙利算法在认知用户数为14和19时，带宽效益也有所下降.主要是因为不同认知用户在使用相同的信道传输不同的距离时，会获得不同带宽效益.在公式(3）中清楚地表示距离会影响路径损耗，路径损耗会影响带宽效益.本文作者介绍的KM算法要在带宽效益和频谱利用率之间取得平衡，算法会牺牲带宽效益来提高频谱利用率.但是对于贪婪算法，在不考虑干扰的前提下，带宽效益是随着认知用户数的增加而增大的.

图2是在频谱利用率方面对3种算法进行的比较.本算法和匈牙利算法在频谱利用率方面都能接近1.因为KM算法能获得在完备匹配下的最大权分配.匈牙利算法和KM算法都是基于干扰图的，1条信道只能分配给1个认知用户.采用贪婪算法分配，由于认知用户之间为竞争获得最大带宽效益，多个用户使用同1条信道，干扰过大反而造成信道不可用，所以贪婪算法的频谱利用率不高.

图3是认知用户在等待接入信道的时间比较图.在本算法中，由于优先权为T1的信道可以发送更多的数据，再根据第四章步骤2中的规定，优先权为CR1的认知用户占用带宽效益更高的信道，优先权为CR1的认知用户不会长时间得占用信道，其他的认知用户也不会长时间地等待分配可用信道.所以本算法在认知用户等待分配可用信道的时间方面要少于其他2种算法，保证了认知用户的QoS.文献［3］提出了对不同优先权的认知用户的排队机制.这样的安排也可以缩短认知用户的等待时间，但是不排除1个认知用户会分配到带宽效益不好的信道，则该认知用户占用信道的时间就会增长，造成其他认知用户长时间等待可用的信道.

图2 3种算法的频谱利用率比较

6 结 论

本算法是基于图论KM算法实现的动态频谱分配.在带宽效益和频谱利用率的约束下，本算法取得了两者的平衡和优化.本算法的带宽效益接近贪婪算法，频谱利用率接近1.

在信道分配过程中，当认知用户数多于空闲信道数时，本算法可以一直循环执行直到所有的信道被分配完成.本次分配中未得到分配的认知用户等待下一次分配.当基站发现有主用户需要通信时，认知用户必须马上退出属于该主用户的授权信道.该认知用户需要等待下一次分配新的空闲可用信道.在图论中，1条信道只能被分配给1个认知用户.但是如果1条信道能被分配给多个用户，这将极大地提高频谱利用率.但随之而来产生一个新的问题：多个认知用户使用同一条信道必定会有干扰，这是必须处理的问题.在未来的研究中，动态频谱分配的研究可以深入考虑干扰管理，已有部分文章对此进行了讨论［6-7］，这也是下一阶段可以努力的方向.

［1］ WEISST A，JONDRAL FK.Spectrum pooling：an innovative strategy for the enhancementof spectrum efficiency［J］.IEEE Radio Communications， 2004，42（3）：S8-14.

［2］ FITZEK FH P，KATZM D.Cognitive wireless networks［M］.Berlin：Springer，2007.

［3］ SWAMR S，GHOSH C，DHEKNE R P，et al.Graph Theoretic approach to qos-guaranteed spectrum allocation in cognitive radio networks［C］.Texas：IEEE，Performance Computing and Communications Conference IPCCC 2008 IEEE International，2009.

［4］ IM S，KANG Y，KIM W，et al.Dynamic spectrum allocation with efficient SINR-Based interference management［C］.San Francisco：IEEE，Vehicular Technology Conference（VTC Fall），2011.

［5］ XU D，JUNG E，LIU X.Efficient and fair bandwidth allocation in multichannel cognitive radio networks［J］.IEEE transactions onmobile computing， 2012，11（8）：1372-1385.

［6］ AINWAIMIG，ARSHAD K，MOESSNER K.Dynamic spectrum allocation algorithm with interferencemanagement in displaced networks［C］.Istanbul：IEEE，Wireless Communications and Mobile Computing Conference（IWCMC）2011 7th International，2011.

［7］ YANG J，FEIZM Z.Bipartite graph based dynamic spectrum allocation for wirelessmesh networks［C］.Beijing：IEEE，Distributed Computing SystemsWorkshops 2008 ICDCS’08 28th International Conference，2008.

Dynam ic spectrum allocation based on Kuhn-M unkres algorithm to guarantee cognitive users′QoS

YE Peiqing，LI li，ZHOU Xiaoping，CHEN Xiaodan
(College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China）

Based on the graph theory，this paper studies the problem about the dynamic spectrum allocation(DSA）in the cognitive radio networks.First，priorities are assigned for the cognitive users based on their Quality of Service(QoS），and for the channels based on the state of the idle channels，respectively.Then a new method is proposed to estimate the bandwidth efficiency that the cognitive users could getwhen using the channels.Finally，a bipartite graph is established for the prioritized cognitive users and prioritized channels.The weight of the bipartite graph is the bandwidth efficiency.With consideration of cognitive user bandwidth efficiency and spectrum utilization as a premise，Kuhn-Munkres algorithm is used to assign channels to the cognitive users. The experiment results show that the proposed algorithm can optimize the bandwidth and the spectrum utilization at the same time.It can also achieve better QoS requirements in terms of the waiting time for allocating the channels to the cognitive users.

dynamic spectrum allocation；Kuhn-Munkres algorithm；priority.

TN 929.5

A

1000-5137(2013）02-0137-06

（责任编辑：包震宇）

2012-11-22

上海市教育委员会科研创新项目(12ZZ126）；上海师范大学重点学科(DZL156）

叶培青(1987-），女，上海师范大学信息与机电工程学院硕士研究生；李 莉(1962-），女，上海师范大学信息与机电工程学院教授.