基于图论冲突图理论的感知无线电频谱资源分配算法

基于图论冲突图理论的感知无线电频谱资源分配算法

0动态频谱分配算法感觉广播技术（conomicformulationcollaborationtechnology）是近年来的一种新兴的光谱共享技术。相比传统的使用授权频带的资源分配方式,感知无线电技术提出了一种利用频谱资源的全新的解决思路,它能够依靠人工智能的支持,感知无线通信环境,动态检测和有效地利用“频谱空洞”(空闲频谱),理论上允许在时间、频率以及空间上进行多维的频谱复用,从而最大限度地利用潜在的频谱资源,提高频谱使用效率。动态频谱资源分配是CR技术实现的关键之一,目前已有一些文献提出了CR的动态频谱分配算法。Peng和Zheng等人提出的标签机制将动态频谱分配问题归纳成一个对CSGC图的染色问题,已广泛应用到动态资源分配问题上。对感知无线电频谱分配问题的研究可以分为集中式和分布式2种算法。传统的算法采用集中式控制,但是由于CR的异构性和动态性,集中式方法并不实际,于是提出了不需要任何中心控制器的分布式方法。文献基于用户间通过协作交换信息来补偿不断增加的干扰级的考虑,提出一种异步分布式定价方案。研究表明,采用分布式结构的感知无线电在异构环境下具有更好的适应能力,但是用户之间的协作会导致协作延迟。文献以昆虫巢群中的自适应任务分配模型为基础,提出了一种基于生物启发的频谱分配算法。由于无需用户之间的协作,避免了由于协作而产生的切换延迟。基于需求的算法在标签算法上增加了对感知用户随时间改变的频谱需求的支持,在每个感知用户对频谱的需求随着时间的变化而变化并且为有限值的情况下,该算法能保证较好的公平性和提供较高的分配效率。最近文献利用历史占用信息来研究自适应空闲频谱检测获得好的效果。通过研究发现,历史分配信息同样有助于改进CR的动态频谱分配性能。鉴于其在资源分配方面的良好性能,本文以基于需求算法为基础,在资源分配时增加了对历史分配信息的考虑,提出了一种新的分配准则:按照二级用户获得的频谱资源占总分配资源的比例进行资源分配,如果用户在历史分配中获得资源较多,即所占比例越大,在下次分配中遵从一种比例公平原则,则标签值越小。这样可以防止某些信道特性较好的用户占用较多信道而使一些信道出现零分配的情况。仿真表明改进的算法在总带宽、收敛性和公平性都有较好的表现。1动态频谱资源分配算法假设频谱环境变化缓慢,用户可以快速适应环境,执行分配。因此,在一次分配执行的很小时隙内,可以将网络看成固定拓扑,R和r分别是主用户和二级用户的干扰半径。为了建模动态频谱资源分配问题,将某时刻感知网络的结构转化为一个无向冲突图G=(V,L,E)来实现资源的无冲突分配:V表示图中的节点,代表网络中的感知用户;L代表每个节点的颜色列表,即可用信道;E代表图中的一条无向边。若两个二级用户之间的距离小于干扰范围2r,就认为它们相邻,或者说相互冲突,此时两个二级用户不能同时使用一个信道,它们之间有一条边相连。主用户和二级用户之间也有一个干扰范围2R,决定二级用户是否可以使用主用户的信道。图1是一个冲突图的例子。在模型中,设网络二级用户数量为N(二级用户可以是一段传输链路或者广播接入点),空闲频谱资源被划分为M个完全相互正交的信道,为简便起见假设所有的信道都相同(信道容量都为1),算法同样可以扩展到信道不同的情况。每个感知节点都能采用有效的方式感知到它能使用的空闲信道,并能利用任何它所感知到的空闲信道进行通信。1)可用信道矩阵L={ln,mln,m∈{0,1}}N×M,表示每个用户可以使用的信道情况。例如:若用户n可以使用频谱m,则ln,m=1,否则为0。2)信道增益矩阵B={bn,m}N×M,其中bn,m代表用户n在信道m上获得的最大带宽。6)饱和度矩阵sn为在当前分配情况下用户获得信道与其需求之比。动态频谱资源分配的2个主要目标就是保证效率和公平性。结合上面的定义,我们用(1)式来描述分配结果的性能。系统总带宽为分配公平性1采用文献提出的公平性指数分配公平性2公平性1侧重描述各个用户获取资源的差异,资源在用户中分布的越平均,分配值越接近1,算法的公平性越好;公平性2侧重描述用户对资源需求的满足度,用户获得资源越接近需求,算法性能越好。2基于历史信息的需求度准则在分布式环境下,网络不存在中心节点,假设网络中每个感知用户都能够可靠感知当前的位置信息、需求矩阵,并通过和邻居节点合作交换当前的分配信息,自行决定获取资源。基于历史分配信息的改进算法增加了对用户过去获取资源方面的考虑,定义σn为用户n的资源占用比例系数,表示用户当前获得的信道资源占已分配总资源的比例我们采用系数σn改进已有的算法,在每次计算标签值时都引入代表历史分配信息的资源占用比例系数σn,制定新的分配规则如下:规则A基于历史信息的最小邻居数准则(5),(6)式中:ln表示用户n的可用信道列表;Gn,m代表和用户n同时使用信道m时发生冲突的用户n的邻居数量,定义在规则A中,用户的标签值由最小邻居数Gn,m和系数σn共同决定。由表达式可知,σn越大,也就是用户当前获得的信道资源占总分配的比例越大,那么用户的标签值越小,下次分配中获得资源的可能性越小。这样可以有效避免单一感知用户占用过多信道。当有两条不同信道拥有相同的标签值时,用户任意选择一条信道通信。规则B基于历史信息的需求度准则规则C基于历史信息的最小邻居需求度准则规则B和C在计算标签值时都考虑了用户的需求和历史分配情况,避免将多余的资源分配给那些对信道没有需求或者需求较小的用户,造成资源浪费。3种规则都在每次分配时选取邻居数最小的信道进行分配,这样可将对邻居感知用户的影响降到最低。如果在某次计算中,2个节点的标签值一样,将选取饱和度更小的那个节点进行分配。算法的具体实现步骤如下:1)每个感知用户节点根据资源分配时的侧重点选择合适的分配规则(例如用户侧重获得最大的系统带宽可选择规则A,侧重公平性2可以选择规则B),并确定每次分配的信道数量。用户计算自己的标签值后,通过广播通知周围的邻居节点自己的标签值。2)所有邻居用户在收到来自感知用户的消息后,将自己的标签值发送给感知用户。感知用户经过比较,若自己的标签值在周围的邻居用户中是最大的,用户获得该信道,将它从自己的本地可用信道列表中删除,并将该信道被占用的消息广播给邻居用户。这里每个感知用户一次可以获得多个信道。3)每个用户节点收集来自邻居节点的信道占用信息后,删除已分配的相应信道并更新本地可用信道列表,之后重新计算自己的标签值。这个过程被重复执行直到所有节点用户的信道列表为空或者所有用户的需求都被满足,算法结束。3网络拓扑的性能分析假设在一个10×10范围内的无噪声环境下,随机放置一些主用户和感知用户,每个主用户随机选择2条信道进行通信,每个感知用户所需信道数量随机并且不大于总信道数量。为方便分析算法性能,假设感知用户每次需求10条以上的信道。仿真采用Matlab软件,设置主用户数量为4,感知用户数量为20,主用户和感知用户的干扰距离均为2,总信道数量为20,为求得总带宽和迭代次数的折衷,我们假设每个用户可以分配的最大信道数量为14,然后对20次随机生成的网络拓扑进行了仿真,结果见图2—5。图2—5给出了规则A,B,C与原算法在系统总带宽、公平性及迭代次数等几方面的性能比较,新的规则A,B,C明显改善了原算法的性能。由图2,规则A,B,C都提高了原算法的带宽。采用规则C可将合作最大化网络公平性规则带宽提高23%,规则A相比合作最大化带宽规则提高了8%,由于基于需求的算法本身已经包含了过去的分配信息,故规则B改善不大,但仍有约5%的提高。公平性1侧重评估用户获取信道的公平性,用户获得的资源越平均,公平性越好。从图3可知,规则A比原算法在公平性1方面至少提高了17%,规则C提高了5%,规则B基本与原算法持平。在公平性2方面,如图4所示,规则B的性能最好,规则C略低于规则B,规则A最低。在分布式环境下,算法的收敛性是衡量性能的标准之一。图5显示的20次随机拓扑中A,B,C规则的平均迭代次数分别为15,5,3。可见规则B和C的收敛性较好,尤其是规则C,相比A在收敛性上提高了350%以上。4算法的n系数及其收敛性本文提出了基于历史分配信息的动态频谱分配算法,并对算法在系统总带宽,公平性和收敛性方面的性能进行了研究。仿真结果表明,改进的算法相比原算法在系统带宽和公平性方面都有提升,并且规则A,B,C在3种性能指标上各有侧重点。规则A在系统带宽和公平性1方面表现最好;规则B,C则在公平性2和收敛性上要优于规则A。σn系数可以应用到其他标签法则中改善分配性能。3)用户需求矩阵D={dndn∈{0,1,2,…}}N,dn表示用户n所需要的信道容量。由于我们假设所有信道容量相同,因此dn也可表示成用户n所需要的信道数量。4)干扰矩阵C={cn,k,mcn