课程报告-认知无线电中的频谱定价博弈

1、课程报告认知无线电中基于博弈论的动态频谱共享方法1.引言认知无线电（Cognitive Radio，CR）技术首次由Joseph Mitola在其博士论文1中提出。CR可以智能化的通过学习感知无线环境变化并且能够自适应地调整自身内部的通信机制，打破了传统静态固定频谱分配模式的瓶颈，被业内学者认为是“解决无线网络中频谱资源利用率低下问题的最佳方案”2。在无线通信领域中，移动蜂窝网络中可利用图论中的着色算法(Graph Coloring Algorithm, GC)来进行资源的规划和管理。这同样适用于CRN，由于地理空间位置的差异性导致CR用户间可用频谱具有一定差异性，这种差异性可被等效为图论中的

2、“色数”，而CR用户之间干扰可被等效为“边”，因应用此GC理论可以分析研究CRN中的频谱分配问题6。博弈论(Game Theory)又称为对策论，最初主要应用于经济学相关领域中，研究多个决策主体之间行为具有相互作用时，各个决策主体如何根据所掌握的自身能力的认知做出有利于己方决策的理论。其相关理论现已被应用于无线频谱资源的管理，例如接入控制、速率控制7、功率控制89等、无线协议的规划以及频谱的动态共享10。文献11中利用囚徒困境模型研究了CRN中两个CR用户相互竞争情况下的频谱共享问题，并给出了相应的纳什均衡(Nash Equilibrium, NE)，虽然NE是一个稳定的解，系统整体收益在NE

3、时通常不是最优。文献12建立了基于信干比的效用函数，提出了一种基于纳什协商的分布式功率控制算法。在CRN中，CR用户之间存在着频谱的竞争问题，PU用户之间亦存在竞争关系。文献13研究了拍卖机制来解决认知无线电网络中的频谱共享问题，提出了一种多卖家步进拍卖模型，频谱拥有者作为拍卖人，CR用户作为竞拍人，理论分析表明拍卖最终结果近似可以达到全局最优，由于频谱拥有者之间以及CR用户之间无需信息交互，信令开销可以被有效地节省。文献14-18中研究了授权用户服务者在保证主用户网络中用户的QoS时“有偿”出租频谱给次级网络服务者，讨论了授权用户服务者间以及用户服务者与SU之间的频谱定价博弈问题。深入研究分

4、析了Cournot模型、Bertrand模型下的NE，并且给出了分布式条件下的授权用户服务者的频谱价格更新策略。竞争性博弈时的NE系统整体的收益不是最优。其他相关的最新论文可以参见19-21。2. 基于Bertrand模型的频谱共享算法2.1博弈模型根据FCC的建议，认知无线电系统可以使用电视广播频段的空闲频谱，在这一频段内主要有两种类型的授权用户系统：电视系统和无线话筒系统。授权用户服务者以竞争的方式出租给次级网络基站，它们掌握着一定频谱的数量，可等效视为经济学中的寡头市场。Bertrand模型最适合应用在授权用户服务者之间的博弈中，如何确定频谱的出租价格是最为关键的。本文首先研究授权用户服

5、务者互相竞争获得市场份额的Bertrand博弈模型，授权用户服务者i各自独立服务Mi个授权接入点；此外，授权用户服务者i以每单位频谱pi的价格将空闲频谱出租给次级网络基站(Secondary Base Station, SBS)或者次级接入点(Access Point, AP)，SU之间可以共享次级BS中频谱资源。图1 两个授权用户服务者网络博弈模型2.2Bertrand价格博弈SBS的效用函数可以表示为如下二次效用形式22：其中表示不同授权用户服务者所提供的频带大小组成的向量，为对应的单位频谱价格，表示第i个授权用户服务者提供频带上次级用户的频谱利用率，表示频谱可替代因子，该参数和市场竞争激

6、烈程度正相关。为了便于分析，本文仅讨论授权用户服务者为2的情形，即N=2；采用式中次级BS的二次效用函数的依据在于：(1)二次凹的效用函数可以便于描述随着传输速率的增加用户的满意度趋近于饱和的特性，这种类型的函数被广泛用来量化尽力服务(Best-effort)用户的满意度，通常用户满意度为分配频带参数有关的函数；(2)二次效用函数的微分可以得到线性的需求函数(Demand Function)，非常便于问题的处理和分析；(3)可以很好描述频谱质量和次级用户对于频谱偏好的影响(频谱替代因子)。次级用户的数据传输采用自适应调制方式，可以灵活根据信道状况来改变发射信号调制方式(信道质量较好时采用高阶调

7、制，反之采用低阶调制)，其频谱效率可以通过下式近似计算23：其中为接收端信噪比，BERtar为次级用户给定的误比特率要求。频谱需求函数(Demand Function)为：可以得到授权用户服务者网络1和2的频谱需求为：授权用户服务者i的收益函数可以表示为：其中表示授权用户服务者中授权接入点所需频谱带宽，是授权接入点个数，c1和c2为两常数，表示授权用户服务者网络中频谱效率。授权用户服务者i的支付由三部分组成，一部分来自于次级BS租用频谱的支付 ，一部分来自于主用户授权连接的费用，还有一部分是由于相当于次级BS租用部分频谱对主用户连接的QoS的影响。上述Bertrand博弈模型的博弈的三要素可以

8、表示为：参与者(Player)为授权用户服务者网络1和2，参与者策略(Strategy)为单位频谱价格，相应的支付(Payoff)可以用式表示。得到如下关于p1和p2的线性方程组(Best Response of Best Response)：BR为：当所有系统参数已知，联立以上方程组且存在唯一解时可得纳什均衡(Nash Equilibrium, NE)：其中：该均衡解若存在必须满足非负约束。当博弈双方无法观察到对方的当前策略以及对方的支付的增益时，双方只能根据效用函数边际变化进行价格调整时(需要授权用户服务者与SBS进行信息交互)出于授权用户系统自私和理性，它们以最大化自身利润为目的，所以根

9、据t次迭代的边际效用的变化可以得出t+1次迭代的信道出租价格：其中表示速率调整参数，,表明授权用户服务者系统的边际效应，可由下式近似，其中为很小的偏移量，仿真中取值为。图2. Bertrand价格博弈价格更新模型示意2.3稳定性分析对于动态博弈而言，稳定性十分重要，可以通过对雅克比矩阵的特征值来分析动态博弈的稳定性。特征值可以表示为：当且仅当雅克比矩阵的特征值都位于复单位圆内，该动态博弈才是稳定的，即。2.4重复博弈扩展合谋的达成文献16研究了在分布式条件下，由于授权用户服务者由于无法直接观察到对方竞价，只能通过需求函数的反馈动态更新自己的频谱价格，从而达到NE。但是NE并不是一个有效的解，合

10、作比竞争往往能够获得更大的整体收益。使得整体收益最大的最优价格的求解可转化如下优化问题：中的最优解为。民间定理：设G为一个完全信息静态博弈， 表示G的纳什均衡，表示任意可实现支付。如果对于任意i都成立，而足够接近于1，那么无限重复博弈一定存在一个子博弈完美纳什均衡，各博弈方的平均支付为 。贴现系数表明了将未来收益折算到当前收益的比例参数，当贴现系数较小时反应了局中人不太看重未来利益，也不惧怕对方在未来阶段所采取的报复手段，在这种情况下无穷重复博弈也就不能提高原来博弈的均衡。而当贴现因子较大时，局中人看重未来的收益，理性的局中人不会为了一次性的眼前利益而去激怒其他博弈方，导致长期利益受损失。无限

11、次重复博弈的子博弈仍然是无限次重复博弈，当所给定的触发策略在整个博弈中构成纳什均衡时，在每个子博弈中必然也构成纳什均衡，因此为子博弈完美纳什均衡。将频谱共享可以扩展为无限重复博弈，根据民间定理，合适的贴现系数 (折扣因子)可以促使合谋的形成，打破竞争引起的囚徒困境。在无限重复博弈中，触发策略的设置尤为关键，下面考虑两种不同的触发策略进行对比分析：(1)触发策略1:博弈的一方在博弈的另一方采取合作策略时会一直采取合作策略作为奖励；而一旦对方采用偏离策略时，下一阶段将采用“冷酷”策略即永久采用NE作为报复。博弈双方始终合作时，参与者i的收益为：其中为贴现率，体现了参与者的耐心和对未来收益的重视程度

12、。若参与者i偏离合作后，整体收益为：其中，为NE对应的支付。博弈参与方合作维持的条件为：分布式情形下的动态价格调整和类似，可以求得：图3. 分布式合作价格博弈中参与者价格更新示意对于给定的贴现率水平，所能支持的最低具有稳定性的频谱定价是多少？基于此，给出触发策略2。(2)触发策略2：第一阶段的价格定位，在阶段t，如果t-1阶段的价格为时，继续执行该定价，否则执行。 其中，为NE对应的支付。博弈参与方合作维持的条件为： (3)触发策略3：(降低贴现因子的约束，“胡萝卜加大棒”)博弈的参与者在第一阶段均采用合作策略。当博弈进行到第t阶段，如果t-1阶段的参与者的策略组合为，则第i个参与者仍然采用；

13、如果第t-1阶段的策略组合为时，第i个参与者采用，否则采用。上述策略表明如果其中一方与自己始终保持同步调时采取奖励，如果对方与自己步调不一致时，采取惩罚措施，当双方步调恢复一致时在下一阶段重新恢复合作，从而可以在贴现因子较小的时候双方达成高效率的均衡。由于这种惩罚不是永久性的，为了能够约束对方的行为，必须使得惩罚策略下对应的收益低于Bertrand收益。当第一阶段参与方i偏离时，其得到的收益为，下一阶段的收益为若要始终保持合作，第一阶段偏离的好处需要小于第二阶段的惩罚带来的损失，即满足：上式表明可以通过设置来放松对贴现系数的约束。最有威胁的约束在于在对方惩罚措施的条件下，自己所能获得的最大收益

14、仍然会低于NE收益，这表明该策略不是空洞威胁。2.5 纳什讨价还价-公平性合作定义：纳什讨价还价解(Nash Bargaining Solution, NBS)一个NBS满足下列6个公理：(1)个体理性；(2)可行性；(3)Pareto最优；(4)独立于无关选择；(5)线性变换无关;(6)对称性。公理(1)、公理(2)和公理(3)是明显的，它们定义了一个讨价还价集。个体理性说明任意一个解x*，都有x*d。可行性是指解在支付区域内。Pareto最优是指在讨价还价问题中，如果存在2个结果，其中一个结果对于两位局中人都严格优于另一结果，则处于严格劣势的结果一定不是讨价还价解的结果。Pareto最优隐

15、含了博弈双方不会选择协议不可达点。公理(4)、公理(5)和公理(6)称作公平性的公理。公理(4)是指如果较大集合的讨价还价解定义在一个较小的域内，则扩展域对解没有影响；公理(5)是指讨价还价解和不可达点经过线性变换调整后讨价还价解仍然不变；公理(6)说明了如果博弈双方有相同的不可达点和效用函数，则他们有相同的效用。授权用户服务者可以通过协商的方式实现合作从而达到Pareto最优，本文的博弈问题经验证满足以上6条公理，存在唯一的函数最大化谈判问题中各自所得收益与破裂点的差的乘积，其形式如下： 其中表示谈判破裂点，进一步可以参考文献24考虑不同授权用户服务者具有不同优先级(谈判力)的场景，即可建模

16、为如下问题：其中wi表示相应的优先级参数，满足，可以兼顾收益的公平性。可以等价为以下凸问题：其Lagrange对偶函数可以表示为：其中为Lagrange乘子，上述问题的最优解可通过KKT条件由其对偶问题解求得。图4. 分布式Nash讨价还价中参与者价格更新示意2.6 模型的再扩展该问题为一个开放性问题，模型可以结合实际中的基站能耗因素将原有的授权用户服务者的支付函数进行相应合理地修改扩展，而目前鲜有文献将这部分因素考虑其中。在实际的网络中，授权用户服务者的能量消耗构成了其成本的主要部分，现有蜂窝网中通用的EARTH能耗模型主要将基站的能耗分为静态功耗和动态功耗两部分25，动态功耗主要和服务的主

17、用户数量有关，而静态的功耗占据了能量消耗的大部分。当授权用户服务者负载较轻时(授权接入点带来的收入低于成本消耗时)，可以考虑采取休眠机制，将区域内主用户数移交给相邻的其他授权用户服务者而支付给其一定费用，而将自身频谱全部出租给次级网络服务者获得一定收入。3. 仿真分析表1 实验仿真参数取值参数取值授权用户服务者频谱宽度WiWi=20 (MHz)授权接入点所需频谱宽度( MHz)次级用户目标误码率BERtar=10-4加权参数c1=c2=2实验1：频谱质量对于纳什均衡点的影响图5. 最佳响应示意图 图6. 授权服务提供商最佳响应函数假定两个授权服务者中的授权用户数量均为10(即Mi=10，若不特

18、加说明授权用户连接数量均为10)，且信道的即频谱(信道)质量相同，速率调整参数，频谱可替换因子设置为v=0.4，其他相应系统参数如表1所示。图5中给出了授权服务者P2的频谱价格分别为0.5、1.5和2.5时，授权服务者P1的不同定价策略对其收益的影响，图5中的红色圆圈的位置为P1在P2的频谱价格给定时的BR。图6中给出了不同信道质量条件下P1和P2的最佳响应函数，根据纳什均衡的定义可知其为最佳响应的最佳响应，即对应了参与者的最佳响应函数的交点，随着信道质量逐渐变好最终达到NE时双方的频谱定价也会随之增加。实验2：分布式条件下授权服务者的频谱价格动态调整以及速率调整参数的影响 (a)M1=10,

19、 M2=14 (b)M1=M2=10图7.调整速率对于收敛的影响图8. 时，P1价格分岔图(Bifurcation diagram)图7中给出了授权服务提供商中的不同授权用户数量对于纳什均衡点的影响，以及反映了不同速率调整参数的对于收敛速度的影响。图7(a)中M1=10, M2=14，当选用这个较大的速率调整参数时价格调整速度快于参数为的情形，但是价格调整的抖动更加明显，稳定性差。图7(b)给出了M1= M2=10时授权服务提供商P1的动态价格调整图，由于在所给定的系统参数条件下，授权服务提供商P1和授权服务提供商2完全对称，所以图7(b)中仅给出了授权服务提供商P1的曲线。图8中固定研究调整

20、的取值对授权服务提供商P1频谱定价的影响。当的取值大于0.7左右时，P1的频谱定价出现分岔，表明此时动态博弈并不稳定。实验3：分布式条件下授权服务者的频谱价格动态调整以及速率调整参数的影响3-1：触发策略1图9给出了合谋时授权服务提供商P1的动态价格调整图()，图10给出了对应收益的对比。由于原来的竞争双方具有了集体理性，所以最终的频谱定价高于NE时的定价，这也随之带来了如图10所对应的更高收益。图11同样反映了合作时和竞争时系统总收益的对比示意，表明合作时可以达到Pareto最优解。图9 合谋时授权服务提供商1的动态价格调整 图10 系统总收益对比 图11 合作时收益和竞争时NE对应的系统总

21、收益的对比图12 三种价格随频谱可替代因子v的变化图 图13 折扣因子下界随频谱可替代因子v的变化图在双方达成协议时，双方都会采用最优价格策略实现整体的收益最大化，但是其中的一方仍然可能发生定价偏离使得自己的收益最大化，此时仍然采用协议的最优价格策略的一方将会蒙受损失，但其将会在下一阶段采用触发策略进行报复。图12中给出了最优定价、NE对应的价格以及偏离价格(其中一方在另一方保持最优定价时的最佳响应所对应的价格)随着频谱可替代因子v的变化图，v的增大与竞争的激烈程度是正相关的，所以竞争越激烈，NE对应的定价就越低。图13给出了折扣因子的下界随着频谱可替代因子v的变化图，当竞争激烈化后，要使得双

22、方能够达成协议则必须对未来阶段的收益足够重视，需要满足较大的贴现率。3-2：触发策略2：给定贴现率条件下支撑的最大收益图14 合作收益随贴现率的变化图图14中给出了低水平合作时的个人收益随着贴现率变化曲线，图中红线位置对应Pareto最优，随着贴现率的增加，收益也随着增加，当贴现率达到满足触发策略1的要求所对应的下界时，策略2和策略1等价。实验4：Nash讨价还价模型下，授权服务者的优先级对频谱定价和收益的影响 图15不同定价策略的总体收益(w1=w2=0.5) 图16不同定价策略的总体收益(w1=0.8，w2=0.2) 图17频谱价格动态调整图 图18收益动态调整曲线图15给出了Nash讨价

23、还价模型下的可行集合(w1=w2=0.5)以及对应的NBS，其取值和合谋时几乎一致，表明了NBS具有Pareto最优性。图15中给出了可行集合所对应的区域，用绿色虚线做出了标识。图16中给出了授权服务提供商具有不同优先级(w1=0.8，w2=0.2)时的NBS，此时优先级较高的一方的定价更低可以占有更多的市场份额，在收益分配上体现出了公平性。图17和图18中不同优先级条件下，授权服务提供商频谱定价和收益的动态调整图，这也印证了优先级高的一方的话语权更大，其收入的分配是比例公平的。需要指出的是，初始点的设置对收敛有影响，必须保证初始点的位置必须处于可行集合之内。实验5：Nash讨价还价模型下系统

24、稳定性分析图19中给出了Nash讨价还价模型下不同的速率调整参数对于系统稳定性的影响，图中蓝线表示出了对应于Nash讨价还价稳定区域和不稳定区域的边界；红色区域为系统稳定区域，表明该区域内的速率参数组合可以最终实现NBS。可以发现该区域对应的速率调整参数取值较小，这主要是对应图14中的可行集合范围较小，所以如果一旦选择较大的速率调整参数容易导致误入不可行集合之外导致不能收敛到NBS。图19 Nash讨价还价时系统稳定性分析(w1=w2=0.5)4. 结论本文将CRN中的授权服务提供商视为频谱交易市场中的经济寡头，通过向次级基站出租频谱获得收益，利用Bertrand模型进行了博弈分析。并且讨论了

25、纳什均衡以及分布式条件下授权服务提供商的价格更新策略；但是由于NE并不是Pareto最优，通过将其扩展到无穷博弈促使合谋的形成，分析了三种不同的触发策略的影响；同时对纳什讨价还价时授权服务提供商的合作进行了分析，其中讨论了授权服务提供商具有不同优先级对于博弈的影响。参 考 文 献1 J. Mitola III. Cognitive radio: an integrated agent architecture for software defined radio D.Sweden:Royal Institute of Technology (KTH), 2000.2 S. Haykin. Co

26、gnitive radio:brain-empowered wireless communications J.IEEE Journal on Selected Areas in Communications, 2005, 23(2):201220.3 魏急波，王彬，赵海涛.认知无线网络：关键技术与研究现状J.通信学报,2011,32(11):147-158.4 A. Baker,S. Ghosh, A. Kumar, etal. LDPC Decoder a Cognitive Radio Perspective for NeXt Generation (XG) CommunicationJ

27、. IEEE Circuits and Systems Magazine. 2007, 7(3): 24-375 T. A. Weiss, F. K. Jondral. Spectrum Pooling: An Innovative Strategy for the Enhancement of Spectrum Efficiency. IEEE Radio Communications. 2004, 22(3): 8-146 C. Peng, H. Zheng, B. Y. Zhao. Utilization and Fairness in Spectrum Assignment for O

28、pportunisticJ.Spectrum Access. Mobile Networks and Applications. 2006,11(4): 555-5767 H. Lin, M. Chatterjee, S.K. Das, et al. An Integrated Admission and Rate Control Framework for Competitive Wireless CDMA Data Networks Using Non-cooperative GamesJ.IEEE Transactionson Mobile Computing. 2005, 4(3):

29、243-2588 T. Alpcan, T. Basar, S. Dey. A Power Control Game based on Outage Probabilities for Multi-Cell Wireless Data NetworksJ. IEEE Transactions on Wireless Communications. 2006, 5(4): 890-8999 K. Hamdi, Z. Wei, K. B. Letaief. Power Control in Cognitive Radio Systems based on Spectrum Sensing Side

30、 InformationC. 2007 15th IEEE Workshop on Local and Metropolitan Area Networks, LANMAN 2007. Princeton, IEEE CS, 2007: 7-1210 M. Xie, W. Zhang, K. K. Wong. A Geometric Approach toImprove Spectrum Efficiency for CognitiveRelay Networks. J.IEEE Transactions on Wireless Communications, 2010, 9(1): 268-

31、281.11 田峰,杨震.基于囚徒困境的认知无线电竞争频谱共享分析J.南京邮电大学学报(自然科学版). 2008, 28(3): 1-612 杨春刚,李建东.认知网络中基于纳什议价解的功率控制方法J. 北京邮电大学学报. 2009, 32(3): 77-8113 徐友云,高林.基于步进拍卖的认知无线网络动态频谱分配J.中国科学技术大学学报. 2009, 39(10): 1064-106914 D. Niyato, E. Hossain, Z. Han. Dynamics of Multiple-Seller and Multiple-Buyer Spectrum Trading in Cogn

32、itive Radio Networks: A Game-Theoretic Modeling ApproachJ.IEEE Transactions on Mobile Computing. 2009,8(8): 1009-1022.15 D. Niyato, E Hossain.Market-Equilibrium, Competitive, and Cooperative Pricing for Spectrum Sharing in Cognitive Radio Networks Analysis and ComparisonJ.IEEE Transactions on Wirele

33、ss Communications,2008, 7(11): 4273-4283.16 D. Niyato, E Hossain. Competitive spectrum sharing in cognitive radio networks: a dynamic game approachJ. IEEE Transactions on Wireless Communications, 2008, 7(7): 2651-2660.17 D. Niyato, E Hossain., L Le. Competitive spectrum sharing and pricing in cognit

34、ive wireless mesh networksC IEEE Wireless Communications and Networking Conference( WCNC 2008), 2008: 1431-1435.18 D. Niyato, E Hossain., Competitive pricing for spectrum sharing in cognitive radio networks: Dynamic game, inefficiency of nash equilibrium, and collusionJ. IEEE Journal on Selected Area