第22卷第6期重庆邮电大学学报(自然科学版 2010年12月Journalof Chongqing University of Pωts and Telecommunications( Natural Science Edition) DOI: 10. 3979/j. issn. 1673-825X. 2010. 06. 013 基于博弈论的认知无线电的频谱负载平衡蔚承英，包杰(重庆邮电大学通信与信息、工程学院，重庆400065) 摘要:为了提高频谱资源的使用效率并在分布环境下支持。oS，提出认知元线电系统中基于博弈论的频谱负载平衡算法。通过构造支付函数，建立了负载平衡问题的非合作博弈数学模型，利用最佳响应求得纳什均衡解，根据各分配请求的。而要求应用均衡战略来调整资源分自己，以达到频谱利用最优化的目的。仿真表明:该算法可以在避免干扰的情况下有效地利用带宽资源，实现负载均衡;算法的收敛性也得到验证。关键词:认知元线电;博弈论;纳什均衡;负我平衡;最佳响应中图分类号:TN925文献标识码:A文章编号:1673-825X(20JO )06-0761-05 Load balaociog algorithm io cogoitive radio systems based 00 game theory WEI Cheng-ying, BAO Jie (Schoo\ of Communication and Information Engineerin草，ChongqingUn versity of Posts and Te\ecommunications, Chongqing 400065 ,P. R. China) Abstract: To irnprove effieiency of speetrum usage and supporting of QoS in distributed environment, speetrum load ba›lancing algorithrn based on the game theory was proposed. The non-eooperation game model was established by designing payoff function. NASH equilibrium solution was calculated through best reply. Based on QoS requirement of allocation de›mands source alloeation was done imposing equilibrium strategies for optirnality speetrurn usage. Simulation results show it can utilize the bandwidth effieiently, and achieve the balance of load. Converge of algorithm is verified. Key words: cognitive radio; game theoηnash equilibrium; load balancing; best reply 要工作于共享频段，认知系统的频谱分配必然o 51 是灵活、动态的。频谱负载平衡是基于媒体接人控随着无线通信的不断发展，对频谱资源的需求制(mediumaccess control, MAC )的方法，其日的是也相应增长，导致频谱资源日益紧张。另一方面，已提高频谱资源的使用效率并在分布环境下支持分配的频谱资源利用率不足;由此，认知元线电。而。当包含认知系统在内的多个无线系统在至少(cognitive radio)应运而生O认知无线电是一个智能以下一个域中共享时:空域、时域、频域、码域，频i普兀线通信系统，可以感知周围环境，进而标识特定时负载平衡协调并最优化地使用频谱资源[2]。频i普间和空间上未使用的频谱资源，据此调整系统参数负载平衡的结果，是在考虑各共存系统。oS限制的以适应环境变化，在不干扰其他用户的情况下利用情况下，均衡共享资源的负载。应用频谱负载平衡空闲频谱资源。当多个相同或不同系统共享频谱后，增加了共存系统的总吞吐量，并提高新接入网络时，如何相互协调避免干扰，实现。oS支持是认知的认知系统的接入可能;最终整个共享频谱的利用系统面临的关键问题之一[IJ率增加。频谱负载平衡思想来源于信息论的注水原理，这里从博弈论的角度去实现。针对负载平衡问题，文献[3J研究了认知系统收稿臼期:2009-12-18修订日期:2010-09-10基金项目:重庆市科委自然科学基金(CSTC,2009AB2088) 与WiFi( wireless fidelity)系统共存时负载平衡的基Foundation Item: The Natural Scienec Foundation Project of CQ 本架构。文献[4J提出了异构无线网络的负载平衡CSTC( CSTC ,2009AB2088)
.762. 重庆邮电大学学报(自然科学版)第22卷的网络结构，并把它归结为一个最优化问题并给出总分配时长的比例。利用上述符号，频谱负载平衡相应算法。文献[5J提出了具有多主能力的认知终问题表述为设备j寻找分配比例Sjì使自身分配的目端的基于最优化方法的负载平衡算法。本文针对多标函数最优O个认知系统间的频谱共享问题，提出基于非合作博在假设设备是"自私"情况下，上述问题可看做弈的负载平衡解决方案O设备间的一个非合作博弈。这个非合作频谱负载平衡博弈由m个参与人即m个设备、战略和基于战略1 认知系统的频谱负载平衡问题组合的偏好组成。每个设备的偏好用期望效用函考虑网络由多个认知系统组成，或认知系统与数一设备的日标函数表示，所谓"自私"是指每个设受权系统共存。第一种情况频谱负载平衡用于直接备都想最优化自己的目标函数。向量鸟=(Sjj,SJ2’ 协调多个认知系统机会频谱接入，第二种情况用于…，Sjn)称作用户j,j = 1，…冽的负载平衡战略。协调认知系统的二次频谱使用。为了简单起见，只向量S= (Sj，酌'". . ，sm)称为负载平衡博弈的战略研究频谱负载平衡在时域单→频段的应用情况:多组合。频谱负载平衡从博弈论的角度讲就是每个设备选择最优战略以最大化自己的偏好。个系统共享一个TDMA形式的信道。受权系统的分配被看做固定分配，不能被干扰。所有申请资源所有设备在时隙i中共占据时长为z勺吼，因分配的认知系统都应用频谱负载平衡来均衡资源分此，时隙i中的未占用时间为配，其分配围绕在固定分配周围。系统分配的可预测性使构成网络的不能直接通信的不同系统间协调F,(s) =μ; -L勺吼(1) 成为可能。为此，假设所有的系统都能观察到信道(1)式中，Sji伊J表示设备l分配在i时隙中占据的时的分配状况，分配基于固定的帧结构，这种周期性出间长度。现的帧就为不同系统间协调构建了一个平台O为了实现负载平衡每个设备j必须计算出勺以一帧中包括n个时隙，所有系统都知道时隙的使未占用时间Fi(s)最大，且满足约束条件长度。在分布环境下，时隙长度也可以通过所观察到的占据每个时隙开始部分的分配的自动纠错功能Sji抖，L sF = 1 , L Sji'Pj运μι(i=l，...，n)识别。每个申请资源分配的认知系统每帧应用一次(2) 频谱负载平衡技术，于是频谱负载平衡问题最终就最大化时隙i的未占用时间Fi(s)等价于最小转变为把一帧中的n个时隙分配给m个认知系统;化Ls/Fi(s) ，因此，对所有时隙最优化就意味着并且满足以下约束条件:一个时隙内的分配总和不能超过时隙长度，且可用于分配的时隙总长可以满(3)式最小化足所有认知系统的请求。因此每帧，每个系统在考鸟(S)=三飞(3) 虑除固定分配之外的可用时隙长度的基础上，要根i=lμι-lZSJPl 据其QoS需求得到相应时隙的分配比例，目标是使最终每个设备的目标就是选择合适的战略s以所有时隙具有均衡的负载水平。为了简便起见，下使支付函数Dj(s)最小化。设备j的决策与其他设面把认知系统称为设备O备的负载平衡决策有关。因此，D/s)是战略组合 问题的数学描述及模型的函数。考虑整个网络信道一帧有n个时隙被受权设备 纳什均衡和m个认知设备共享。μ;(i = 1，…，n)表示每个时纳什均衡是非合作频谱负载均衡博弈解的一般隙的长度，矶(j= 1，…，m)表示每个认知设备分配概念，它是一个战略组合sν*= (忖s请求需占据的时间长度。设备面临的问题是如何在于每一个设备j，s/是给定其他设备选择情况下该n个时隙中安排自己的分配请求伊J以使自身的目标设备的最优战略O换句话说，一个设备的均衡战略函数即频谱利用最优oSj,( 0运SF运1，立与i= 1)表是在其他设备战略给定条件下的最佳响应，所对应示设备j的分配在i时隙中所占据的时长占设备j的支付函数最小。由于支付函数连续、凸的和单调
.763 . 第6期蔚承英，等:基于博弈论的认知无线电的频谱负载平衡递增，博弈的纳什均衡存在且唯一[6]( L:=川-'P)/(三:IJZ) 本文通过最佳响应函数得到纳什均衡解。首先第5步:对1,. . . ，k则Sjì←(叫一t求解设备j的最佳响应战略sf，在其他设备战略给#J句J定条件下，它可以通过最小支付函数得到。叫=队一第6步:给每个时隙安排设备j的分配请求Sji矶，L Ski'Pk是时隙i对设备l而言的可用分配时间，j =1, ,m 0 要得到均衡分配，先在给定其他设备战略基础于是计算设备j的最佳响应战略问题转变为计算拥上由最佳响应算法得到设备l的战略，接下来还需有n个时隙和一个分配请求时长为矶的设备构成用一个迭代算法周期性地更新每个设备的战略，最的系统分配的最优战略，最终演变为最优化问题终博弈达到均衡。minD/s) (4) 频谱负载均衡算法并满足(2)式的约束条件。每个设备在每次迭代中执行以下步骤。若时隙按可用时间的降序排列(叫二三民二2…~第1步:接收包含所有其他设备当前战略的信息。P;n)，上述最优化问题的解s/为第2步:若信息表示终止，则广播终止信息并退r1 Ił(,; 三:I叫一列其出，否则执行第3步。111伺|以-~Ji;→1，若::::::::l运马= ~飞唱"L二1伊:) 第3步:调用最佳响应算法更新设备j的战略。第4步:检查是否达到预定的误差标准。因为lO 若马运"三n整个博弈模型达到那什均衡后，每个设备都不会更(5) 改战略，整个系统处于均衡状态。是否达到误差标而巧是满足下列不等式的最大值o准ε可通过三:l|DJI-1)-DJ(l)|<ε来判断，l表示j/l; 三:=l叫一饵运(6)迭代的次数OL~=，M 第5步:广播更新战略和误差标准。得到设备j的最佳响应战略，通过反复迭代，逐当网络参数改变时，旧的均衡格局被打破，重新个修改设备的战略直至网络分配达到均衡。开始周期性的执行该算法。算法执行在每帧的协调2 频谱负载平衡算法时期，并假设每个设备在开始当前帧的分配前己接收到了其他设备的分配。信息的广播可以通过小区网根据上述负载平衡问题的数学分析可知，要得络中的基站或AdHoc网络中的广播算法实现l7]到m个设备的负载平衡战略，先必须得到设备j的最佳响应战略，然后通过循环迭代得到最终的纳什3仿真均衡解。最佳响应战略由最佳响应算法实现，纳什仿真用Matlab实现。仿真参数的设置如下:网均衡战略通过频谱负载均衡算法求得。络由4个在相同位置共享频谱的设备组成，其中设 最佳晌应算法备l为受权系统，其分配为固定分配。设备2，3，4输入:时隙的可用分配长度川，品，…，ι，设备J为认知系统，使用频谱负载平衡来均衡负载。仿真的请求分配长度吼;输出分配比例勺，与，…，与;该采用固定帧结构，一帧包含4个时隙。归一化的吞算法的流程如下O吐量代表在一帧中设备共享容量的情况[8]它为一初始化kn; 个设备在一帧的所有分配时长总和与帧长的比值。第1步:先求得时隙的可用分配时间μ'i;设备2分配请求占归一化容量的;设备3分配请求占归一化容量的;设备4的分配请求是变第2步:根据可用时间把时隙降序排列叫注μ~化的，在第25帧到50帧之间请求分配且占归一化..注μ'n'容量的。时隙的最大归一化负载容量为，剩第3步:(汇=1以-'P)/(汇=IJIlJ赋给变量t;余未分配容量可以提供给其他认知系统和受权系统第4步:当t法而时，与←O，k←k-1,t 使用。所有设备都遵从最大归一化负载容量，当一
.764. 重庆邮电大学学报(自然科学版)第22卷个时隙内的总分配超过最大归一化负载容量后设备 终止分配。连续观察网络分配的75帧。几个特定帧的4个时隙的分配请求状况和实际 观察到的分配情况如图1-2所示。图l描述了实际观察到的应用频谱负载平衡的3个认知设备的归一主化吞吐量。由图1看出，3个设备基本都实现了相应20 40 60 80 啦vi的分配请求。在设备共享过程中发生的特定事件都图1频谱负载平衡所观察到的归一化吞吐量用数字在图l中标出，相应的分配模式如图2所示。Fig. 1 Observed throughput of spectrum load balancing z-m』CE2552 4 h帧o(实际分配)a帧o(请求分自己)c帧iMC{冗』Czz。只』咽slols slots d帧26e帧75图2应用频谱负载平衡后帧0，1，26，75的实际分配情况 Real allocation state at frames 0,1,26,75 by used spectrum load halcancing 在初始帧帧0，对应图l标注①的位置，其分衡，在均衡情况下没有设备会选择均衡战略以外的配请求和实际观察到的分配状况分别见图2a-2b。战略，即所谓背离。均衡维持到直至新的分配请求设备1，2，3相应的分配请求之间没有协调，导致第出现，平衡被打破为止。一个时隙过载;于是时隙一的实际分配结果是缩短若认知系统工作于垂直频谱共享方式二次使用了设备2的分配并终止了设备3的分配，相应地设频谱，如果受权用户在某时段要独占使用某一频段，备2，3的吞吐量小于分配请求。应用频谱负载平衡可以把该频段的所有时隙的可用分配时间设为0，后，在帧1分配请求得到协调，2个设备都实现了所避免认知设备接入，从而实现了对受权用户的保护。请求的吞吐量O接下来进行算法的收敛性验证。首先将频谱负第4个设备在帧25开始传送，分配申请占到归载平衡算法的负载均衡战略组合S(O)0 ，相对应一化容量的，对应图1标注②的位置。该请求的算法称为LP_1o算法LP_2中均衡战略组合的初再次导致分配请求之间的不协调，使一些时隙过载，值定义为SJZ(O)←μz/(ZK=lnμk)，此初值意味着时所观察到的吞吐量小于请求的。在设备2，3，4隙分配与时隙资源大小成正比。图3为2种算法的应用频谱负载平衡，3个设备重新分布了它们的分收敛性比较，由图3可知，LP_2算法的收敛性明显配在帧26达到均衡。同样的情况还发生在帧50，好于LP1算法，原因是后一种初值设置更接近均设备4终止传送时，对应图1中标注③的位置。分衡点，需要的迭代次数约少一半，更少于基于注水原配呈现持续状态从博弈论的角度称为达到纳什均理的频谱负载平衡算法。
.765 第6期蔚承英，等:基于博弈论的认知无线电的频谱负载平衡[3] ISHIZU K, HARADA H. A Load-balancing Framework 250 LB_I一骨一LB 2--<> for Cognitive Wireless Network to Coexist with Legacy 200 WiFi Systems [ C J/ / IEEE 69th Vehicl出rTechnology 卖主, Conference. Barcelona, Spain: IEEE, 2009: 1-5. 运150a 半份'[ 4 J HA Jeounglak, KIM Jiyeon, KIM Jin-up. Dynamic Load 克1l AUV们 υbalancing Architecture in Hetergeneous Wireless Network ，。ιs Environment [ C J/ / Communications and Information e 50 Technology, 2009. ISCIT 2009. 9th International Symposi›10 15 20 25 30 um on. South Korea IEEE, 2009: 248-253. 设各数[5] FIUN S, HARADA H, HASEGA W A, et al. QoS-Guar›图3算法的收敛性anteed Load-Balancing Dynamic Spectrum Access Algo›Fig. 3 Convergence of algorithms rithm [ C] / / Personal, Indoor and Mobile Radio Commu›nications 2008. PIMRC 2008. France: IEEE, 2008: 1-6. 4结论[ 6 ] ORDA A, ROM R, SHIMKIN N. Competitive routing in 本文基于非合作博弈论提出了一种应用于认知multiuser communication networks [ J ] . IEEE/ ACM 系统的频谱负载平衡算法，在考虑各认知系统。05Trans, 1993,1 (5) :510-521. 要求的基础上，最优化的使用频谱资源;并在受权用[7] WU Jie, DAI Fei. A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks[ C]// 23rd IEEE 户需要时，适时释放资源避免干扰。仿真表明:纳什International Conference on Distributed Computing Sys›均衡解给所有设备提供了一种最优分配方案。从上tems(ICDCS’03). Rhode Island: IEEE, 2003: 460-468. 述分析过程可看出，频谱负载平衡不但可用于单频[8] BERLEMANN 1. Distributed Quality-of-Serv ce Support 率信道，也可用于多频率信道或频域。 n Cognit ve Radio Networks: [ D J. Aachen Germany: 参考文献:Cha r of Communication Networks, RWTH Aachen Un ›versity, 2006. [1] MANGOLD S, ZHONG Z, CHALLAPAU K, et al. Chou. Spectrum agile radio: r剧lioresource measurements for op›作者简介:portunistic spectrum usa吕e[C]// IEEE Global Telecommu›蔚承英(1973-)，女，山西人，讲师，硕士研nications Conference 2(阳(GLOBECOM’04 ). Dall拙，四:究生，主要研究方向为通信与信息系统。IEEE，2仪)4:到-mail: weìchengying一@163. como [2 J FISCHER S, PETROV A M, M..AH"" NEN P, et a1. Dis›tributed load balancing algorithm for adaptive channel al›location for Cognitive Radios [ C J/ / Proc. 2nd Conference on Cogn tive Radio Oriented Wireless Networks and Com›包杰(1950-)，男，重庆人，教授，硕士研究munications ( CrownCom). Orlando, USA: IEEE, 2007: 生导师，主要研究方向为宽带通信网。508-513. (编辑:刘勇)
