基于博弈论的多跳认知无线网络协作路由算法刘觉夫;王建旭;王作航【摘要】For the problem of routing selection with selfish nodes in multi-hop cognitive radio network, a duplicate data forwar-ding cooperative game model was established based on evolutionary game theory, the effective incentive mechanism of selfish nodes was designed, which made the whole network reach the state that all nodes had good collaboration.On this basis, accor-ding to the different utility functions of primary and secondary users, a distributed multi-hop cognitive radio network cooperative routing algorithm was proposed.Results of simulation show that the algorithm can improve the throughput of the primary user effectively, increase the opportunity of secondary user accessing to the licensed spectrum.%针对存在自私节点的多跳认知无线网络路由选择问题,建立一个重复数据转发合作博弈模型,借鉴演化博弈理论,设计有效的自私节点激励机制,让整个网络达到拥有良好协作性的状态.根据主次用户不同的效用函数,提出一种分布式的多跳认知无线网络协作路由算法.仿真结果表明,该算法能有效提高主用户的吞吐量,增加次级用户使用授权频谱机会.【期刊名称】《计算机工程与设计》【年(卷),期】2017(038)005【总页数】7页(P1136-1141,1166)【关键词】认知无线网络;合作博弈;自私节点;激励机制;路由选择【作者】刘觉夫;王建旭;王作航【作者单位】华东交通大学信息工程学院,江西南昌 330013;华东交通大学信息工程学院,江西南昌 330013;华东交通大学信息工程学院,江西南昌 330013【正文语种】中文【中图分类】TP393FCC的研究报告指出，静态的分配策略是导致频谱资源利用率低下的重要原因[1]。
Mitola和Maguire提出具有参数、资源动态重配置能力的认知无线电概念[2]。
认知无线电能显著提高网络的性能和环境适应性，成为提高频谱资源利用率的一项关键技术。
认知无线网络中次级用户(SU)共享授权频谱方式通常有3种[3]，分别为Overlay频谱共享、Underlay频谱共享和Interweave频谱共享模式。
在Overlay频谱共享模式中，为了提高通信数据的传输速率，主用户(PU)通常会选择适当的次级用户协助自己进行数据传输，同时主用户分配一定的频谱资源供次级用户使用。
在本文中，次级用户采取Overlay模式共享授权频带。
当主用户选择次级用户作为中继节点传输数据时，这要求通信路径的各次级用户具有良好的协作性。
然而，网络中的节点由于受自身处理能力、存储空间等各种资源的限制，往往表现出一定的自私性，而自私节点通常不愿为其它节点提供通信服务，这势必会影响通信的正常路由和网络的整体功能。
有关研究表明，当无线网络中自私节点的比例达到10%～40%时，网络系统的整体吞吐量将下降16%～32%[4]。
因此，在讨论多跳认知无线网络路由时，节点的自私行为不容忽视。
本文在多跳认知无线网络中，建立网络通信数据重复转发的合作博弈模型，根据演化博弈制定有效的激励机制，使网络系统达到具有良好协作性的状态，然后设计一种多跳认知无线网络协作路由算法。
该算法能有效提高主用户吞吐量，并增加次级用户使用授权频谱的机会。
在多跳认知无线网络中，存在主用户网络和次级用户网络两类网络，其模型如图1所示。
假设系统中主用户有M个传输进程，即M个主用户发送方PT和M个主用户接收方PR，记作{{PT1,PR1},{PT2,PR2},…,{PTM,PRM}}。
次级用户网络包含N个次级用户，记作R={SU1，SU2，…，SUN}。
在Overlay频谱共享模式下，次级用户可以在不影响主用户通信的前提下使用授权频谱。
在多跳认知无线网络中，当所有的次级用户都具有良好协作性时，主用户通常以两种方式传输通信数据，一种是直接传输，如图1中的{PT1,PR1}，另一种是借助次级用户间接传输通信数据，如图1中的{PT2,PR2}和{PT3,PR3}。
在一次通信过程中主用户只能以直接或者间接传输通信数据。
目前，关于认知无线网络合作通信模式通常有三阶段TDMA模式[5,6]、时间联合频谱分配模式[7]和两阶段TDMA模式[8-10]。
本文采用两阶段TDMA合作通信模式。
假设主用户和次级用户以半双工的作为各自的工作模式，两阶段的合作模式如图2所示。
图2中，W指主用户的授权频带带宽，每个时隙为T。
假设在PTi-PRi通信路由中的次级用户数目为ni。
每个时隙的分配方案如下：主用户在第一阶段将通信数据发送给第一跳中继节点，第一阶段的时隙长度为；次级用户在第二阶段依次传输主用户的数据和次级用户自己的数据，第二阶段的时隙长度为。
设定各用户间的信道状况是独立的高斯随机变量。
在每一个通信时隙内信道状态不发生变化，而在时隙间发生变化。
假设主发送方PTi以直接传输的方式传输数据的发射功率为PSiDi，即用户PTi-PRi传输数据的功率为PSiDi。
次级用户传输主用户PTi-PRi数据传输功率为PRjDi，次级用户SUj传输自己数据给相应的次级用户SUk的传输功率为PRjRk。
PSiDi、PRiDi和PRjRk满足如下关系：PSiDi≤PPM,PRiRk<PPM和PRjDi+PRjRk<PSM，式中PPM为主用户最大传输功率,PSM是次级用户的最大传输功率。
主用户PTi和PRi间的信道增益为hSiDi，主用户PTi和次级用户SUj间的信道增益为hSiRj，次级用户SUj和主用户PRi间的信道增益为hRjDi，次级用户SUj和SUk间的信道增益为hRjRk。
根据香浓定理，在合作式的认知无线网络中，两个节点间的传输速率为当主用户以协作中继的方式传输数据时，协作通信路由中链路的通信速率为针对网络节点自私性问题，基于演化博弈理论，本文设计一种条件合作策略来激励节点进行相互合作。
对激励机制模型做出如下假设：(1)博弈的参与者：认知无线网络中的N个次级用户。
所有的次级用户节点进行对称博弈，即所有的参与博弈的次级用户节点拥有相同的博弈策略和收益矩阵。
(2)策略空间：参与博弈的次级用户拥有3个策略，分别为一直合作策略(ALLC)、一直不合作策略(ALLD)和基于条件合作策略(CC)。
ALLC认知节点在博弈的任何阶段都采取合作策略，ALLD认知节点在博弈的任何阶段都采取不合作策略，CC认知节点会根据博弈对象的特征选择不同的策略，该类认知节点会与采取ALLC策略或CC策略的节点合作，而拒绝为采取ALLD策略的认知节点服务。
认知节点采用CC策略的成本为CCC。
(3)收益矩阵：由于博弈策略有3个，因此收益矩阵为一个3×3的矩阵，记为A=[aij]。
元素aij表示采取i策略的节点与采取j策略的节点博弈后节点i的收益。
根据Worker-Consumer模型[11]，可得依据Taylor and Jonker提出的动态复制因子模型，假设在合作式多跳认知无线网络中采取ALLC策略、ALLD策略和CC策略的次级用户比例分别为x1,x2,x3，这里x1+x2+x3=1。
因此，在任一时刻的节点策略分布比例可以记作X=(x1,x2,x3)。
不同策略的节点存在比例是节点收益的直观反映。
动态演化博弈过程的描述工具是复制者动态因子方程，它是一个能描述某个策略在全体策略中所占比例随时间变化的非线性微分方程。
该方程如下策略i的期望收益种群的平均收益复制动态方程根据上述分析，可以分别计算出各策略的动态复制方程。
ALLC策略的复制动态方程ALLD策略的复制动态方程CC策略的复制动态方程演化理论的基本原则：任何非最优的策略最终都会被排除掉[12]。
因此，类似于一般博弈，演化博弈用演化稳定策略描述稳定状态。
有关研究表明对于用于拥有N个节点的网络系统，当基于条件合作的成本和节点策略变化的概率趋近于零时，网络会收敛到采取策略CC和策略ALLC的状态[11]。
根据该结论，得到如下定理：定理当条件合作策略的成本和网络中节点策略变化的概率趋于零时，ALLD策略是激励机制唯一的纳什均衡。
即对于任何混合采取ALLC策略,AALD策略和CC策略的网络系统最终会收敛到只有采取ALLC策略的状态。
证明：假设博弈者有n个策略，那么收益矩阵为一个n×n矩阵，记作A=[aij]。
如果对于任意的i≠k有akk>aik，那么策略k是一个严格纳什均衡；如果对于任意i有akk>aik，那么策略k是一个纳什均衡。
由收益矩阵，对于ALLD策略有a22>a12和a22>a32，满足演化稳定策略的定义，因此ALLD是演化稳定策略，同时也是严格的纳什均衡。
纳什均衡和演化稳定策略给出了策略空间中某个策略优于其它策略的条件。
根据以上分析，可以得出如下结果：(1)当通信网络中只存在采取ALLC策略和ALLD策略的节点，节点经过一段时间动态演化博弈，系统最终收敛到只有采取ALLD策略节点的稳定状态；当通信网络中只有采取ALLC策略和CC策略的节点，节点经过一段时间动态演化博弈，系统最终收敛到只有采取ALLC策略节点的稳定状态。
(2)当网络中只存在采取ALLD策略和CC策略的节点时，如果采取CC策略节点的比例x3满足时，节点经过一段时间的动态演化博弈，网络节点将选择CC策略，但是由于存在节点策略的变化，网络将收敛到节点都采取ALLD策略的稳定状态；如果采取CC策略节点的比例x3满足时，节点经过一段时间的动态演化博弈，网络将收敛到节点都采取ALLD策略的稳定状态。
基于上述激励机制，设计合理的条件合作成本能让认知无线网络中的所有的次级用户节点都具有良好协作性。
在此基础上，讨论多跳认知无线网络中一种基于图[13]的分布式路由算法。
