基于图论着色模型的频谱分配研究.pdf
- 文档编号:18633563
- 上传时间:2023-08-23
- 格式:PDF
- 页数:3
- 大小:163.84KB
基于图论着色模型的频谱分配研究.pdf
《基于图论着色模型的频谱分配研究.pdf》由会员分享,可在线阅读,更多相关《基于图论着色模型的频谱分配研究.pdf(3页珍藏版)》请在冰点文库上搜索。
摘要:
认知无线电是可以感知外界通信环境的智能通信系统,其中的频谱分配技术是解决现在频谱资源匮乏、提高频谱利用率的一项热门研究。
该文首先对认知无线电系统中基于图论着色的频谱分配模型及其数学符号描述进行介绍;然后对图论着色中的几种算法进行了详细研究并比较总结;最后简单阐述了现存的问题及其未来的发展趋势。
关键词:
认知无线电;图论着色模型;频谱分配中图分类号:
TN911文献标识码:
A文章编号:
1003-0107(2011)01-0018-03Abstract:
Cognitiveradioisaintelligentcommunicationsystemthatcanperceiveexternalcommunicationenvironment,inwhichthespectrumallocationtechnologysolutionisapopularresearchthatcansolvethequestionofspectrumresourcedepletion、improve-mentoffrequencyutilization.Thispaperfirstlyintroducethecognitiveradiosystembasedonthespectrumallocationofgraphcolor-ingmodelandmathematicalsymbolsdescriptions;Thenthealgorithmsofgraphcoloringarestudiedandcompared;Finallyexpoundstheexistingproblemsandthefuturetrendofdevelopmentbriefly.Keywords:
CognitiveRadio;GraphColoringModel;SpectrumAllocationCLCnumber:
TN911Documentcode:
AArticleID:
1003-0107(2011)01-0018-03基于图论着色模型的频谱分配研究SurveyonSpectrumAllocationBasedonGraphColoringModelTheory杨铁军,刘娟,司春丽(河南工业大学信息科学与工程学院,河南郑州450001)YangTie-jun,LiuJuan,SiChun-li(CollegeofInformationScienceandEngineering,HenanUniversityofTechnology,HenanZhengzhou450001)1引言在无线通信技术不断发展的今天,人们对它的需求也在不断增长。
当前的通信资源变得日益紧张,频谱资源的缺乏成为无线应用过程中面临的一个关键问题。
但是大量研究表明,分配给用户的频谱资源存在着不同程度的闲置,基于这个问题,提出了认知无线电技术1,它动态适应环境并以见缝插针的方式复用已授权用户,增加通信中的带宽,有效地缓解了频谱资源紧张的现状。
其中的频谱分配技术不仅解决了频谱资源紧张、利用率低的问题,而且在尽量避免干扰的同时提高了系统的容量、效率和传输可靠性2。
认知无线电网络中带宽、可用信道数量和位置都是随时间变化的,因此传统网络中的频谱分配方法不完全适用。
要实现完全的频谱分配受到很多政策标准的限制,本文研究的图论着色是一门经典的优化理论,在满足限制的同时还考虑了网络的资源分配情况。
图论着色模型中,认知用户择机使用授权用户的频谱,因此认知用户的可用频谱受到授权用户状态、位置及覆盖范围的影响,具有空时变化的特性。
利用此理论根据不同的准则,就可以提出相应的认知无线电系统中的频谱分配算法。
2基于图论着色的频谱分配模型在分布式网络中,图论着色的频谱分配模型将认知无线电用户构成的网络拓扑抽象成图G(V,E,L)3,如图1所示,也是认知无线电网络和授权网络的共存网络。
假定两种网络共用信道结合为channel=A,B,C,授权用户(主用户)I,II,III,IV分别占用信道A,B,C,C;虚线圆内代表的是每个授权用户的干扰范围。
在这些范围内,认知用户与授权用户不能使用相同的信道。
例如,认知用户1在授权用户I的范围之内,不能使用信道A,因此其可用信道集合为channel1=B,C。
其他认知用户的可用信道确定同样如此。
图1中的顶点表示认知用户,边表示一对顶点之间存在着干扰,也就是说,如果两个顶点之间存在一条边,那么这两个顶点代表的用户就不能够使用同一频段。
此外,把每个顶点与一个集合相联系,这个集合代表该顶点所在区域内可以使用的频谱资源,用颜色L表示每一段频谱资源。
在后面将交替使用频谱和信道。
实际中授权用户不断变化,导致认知用户可用信道集合也在变化。
为使问题得到简化,我们在研究频谱分配的过程中假定授权用户的使用信道是不变的。
图1认知无线电系统的图论着色模型专业测试roTestingP182011第01期测试测量技术下面简单地介绍一下在图论着色模型下的几个数学符号。
(1)认知用户顶点集合V:
顶点V=Vn,n=1,2,N表示所有认知用户的集合,V=N表示网络中认知用户的总数目。
(2)可用信道状态矩阵L:
L=ln,mln,m(0,1)NM,ln,m=1表示认知用户n可以使用信道m;ln,m=0表示认知用户n不能使用信道m。
根据授权用户占用信道情况的不同,每一个认知用户的可用信道集合也不相同。
(3)干扰矩阵C:
C=cijcij(0,1)NN,cij=1表示用户i和j同时使用一个信道会有干扰;cij=0表示用户i和j同时使用一个信道不会有干扰出现。
(4)效用矩阵B:
B=bnmbnm0NM表示认知用户n使用信道m时所获得的效益权重。
bnm=表示认知用户n使用信道m时获得效用权重为;bnm=0表示信道m对认知用户n来说不可用。
(5)无干扰的频谱分配矩阵A:
A=anmanm(0,1)NM,anm=1,表示信道m被分配给了用户n;否则anm=0。
矩阵A必须满足下面的限制条件:
cij=1=aim+ajm1,A0i,jN,0mM也就是说,如果两个认知用户之间存在干扰,则它们不能使用同一信道。
3基于图论着色模型的几种频谱分配算法3.1列表着色算法根据图论着色模型,在开放式频谱介入无线网络中提出了基于列表着色的频谱分配算法3。
其目标是获得最大的频谱利用率,文献里的目标函数定义为:
maxsNi=1Kk=1Sik其他一些需要满足的约束条件有:
sikliksiksjkeij=0sik=0,1其中,sik表示信道的分配矩阵S中的元素。
在列表着色算法的范围内,有三种算法:
分布式贪婪算法、分布式公平算法和分布式随机算法。
这三种算法是根据不同的目标而定义的。
分布式贪婪算法以实现信道最大化利用率为目标,导致了分配不均的问题;分布式公平算法则主要侧重频谱分配的公平性,但网络中节点及频谱较多时将会有较大的通信开销;分布式随机算法旨在减少通信开销,使系统的性能得到提高。
3.2颜色敏感的图论着色算法列表着色算法事实上是一种理想情况,该算法未考虑频谱效益差异性和干扰频谱的差异性。
针对这些不足,提出了颜色敏感的图论着色算法4。
该算法考虑了频谱效益差异性和干扰频谱的差异性,而且还分析了不同分配技术下的不同之处。
相比列表着色算法,它明显减少了干扰,还使网络的吞吐量得到提高。
它通过对频谱分配的多次迭代,实现了系统带宽的最大利用或最大比例公平性。
该算法的几个频谱分配的最优效益函数为:
(1)最大化带宽总和(MSB)它以系统达到最大的频谱效益为目标,数学表达式为:
maxAN,MN-1n=0M-1m=0anmbnm表达式的含义是频谱分配给系统带来的最大带宽总和。
(2)最大化最小带宽(MMB)它以最大化受限用户的频谱利用率为目标,数学表达式为:
maxAN,MminnNM-1m=0anmbnm它的含义是频谱分配使获得最小带宽的用户的带宽最大化。
以上两式中,N、M分别代表认知用户和频谱数,anm表示系统分配矩阵中的元素,取值为0或1,bnm表示认知用户n使用信道m时所得到的效用。
N,M为满足条件的无干扰分配矩阵A的集合。
(3)最大比例公平性(MPF)它以最大化每个认知用户间的公平性为目标,表达式为:
maxAN,MN-1n=0log10(M-1m=0anmbnm)以上效益函数对应的准则都有协作式和非协作式两种。
协作式准则综合考虑了对临近节点的干扰冲突,而非协作式准则则未考虑对其他用户产生的干扰。
3.3分布式局部议价算法实际的认知无线电网络拓扑结构是实时改变的,而颜色敏感的图论着色算法主要用于固定拓扑的无线电系统。
在网络拓扑不断变化时,需要重新计算网络的分配方案,造成巨大的通信开销。
基于此问题,提出了分布式局部议价算法5,它在原来信息和现在信息的基础上,对局部做出微小补偿就可以完成频谱的分配,这样一来,通信开销就显著减少了。
在网络拓扑结构发生改变,分布式局部议价算法对局部做出细小改变并补偿后,使原有的最优解重新达到最优。
假定原有最优分配矩阵为ANM,当一个新的认知用户进入网络,则当前分配矩阵变为ANM,两个矩阵的关系如下:
ANM=ANM1nN-1,1mM-10n=N+1,1mM-1当一个主用户i进入网络中,希望使用频段m0。
此时,在主用户的干扰范围内的认知用户要及时退出该频段,分配矩阵关系变为:
ANM=ANM其他0m=m0,nNbr(i)式中,Nbr(i)表示受到主用户i干扰影响的所有认知用户的集合。
19参考答案:
一、单项选择题1.D2.A3.B4.B5.C6.A7.D8.B二、多项选择题1.ACD2.ACD3.AD4.BCD博士案例答案“4面临的问题及未来的发展趋势目前,认知无线电技术的应用越来越广泛。
其中,频谱分配技术能够有效地解决频谱资源的紧张,使得频谱得到合理的分配。
基于图论着色模型的频谱分配中,列表着色算法未考虑系统分配中频谱效益的差异性和干扰的差异性;颜色敏感的图论着色算法虽然克服了列表着色算法中的不足,但是随着用户数和频谱数的增多,其运算量过大,会给系统带来巨大的通信开销;分布式局部议价算法是从用户数的角度来研究,可以降低通信的开销,它利用前一次的分配信息,只对局部变动做出改变来进行频谱分配,如果前一次的分配结果不是最优,将会导致本次分配结果的恶化。
无论在哪种频谱分配模型中,频谱分配问题的主要目标都是在避免干扰的同时能够最大化系统的利用率、信道容量和兼顾公平性,并且降低通信开销、缩短分配时间。
因此,这些目标就成了未来认知无线电频谱分配问题所研究的重点和方向。
5结论本文主要讨论了基于图论着色模型的频谱分配,对其中的列表着色算法、颜色敏感的图论着色算法、分布式局部议价算法进行了详细的分析,并简单阐述了这几种算法所面临的问题及未来发展趋势所向。
参考文献:
1周小飞,张宏纲.认知无线电原理及应用M.北京:
北京邮电大学出版社,2007.2MitolaIII.CognitiveRadioforFlexibleMobileMultimediaCommu-nicationsJ.inPro.6thIEEEInternationalWorkshoponMobileMul-timediaCommunications,SanDiego,CA,15-17,Nov.1999,pp.3-10.3WeiWang,XinLiu.List-coloringbasedChannelAllocationforOpen-SpectrumWirelessNetworksJ.theIEEEVehicularTech-nologyConference(VTC),1
(1):
690-694.4H.Zheng,C.Peng.Collaborationandfairnessinopportunisticspec-trumaccessJ.IEEEICC2005,vol.5,May2005,PP.3132-3136.5L.Cao,H.Zheng.Distributedspectrumallocationvialocalbargain-ingJ.IEEEsensorandAhHOCCommunicationsandNetworks(SECON)2005.Sep.PP.475-486.专业测试roTestingP20
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 着色 模型 频谱 分配 研究