无线网络的博弈论应用

徐许亮 张明铭

摘 要： 本文针对无线网络中自私节点的不协作行为，结合博弈理论建立了无线网络的合理性假设，在此基础上提出了一个促使自私节点协作纳什均衡的分析框架。

关键词： 无线网络 博弈论 节点协作

无线网络是由一组带有无线收发装置的自主性设备通过无线信道连接而成的自治系统。网络中的路由发现和分组转发等服务不是通过专用的路由设备完成，而是通过普通节点（PDA、笔记本电脑、传感器、车载电台等设备）的共同协作来完成。由于无线节点的功率有限，通信半径较小，因此与传输范围之外的节点通信时，需要中间节点的转发。但是，在没有统一管理机构控制的无线网络中，节点间的协作却不能保证。如民用型无线网络，在这样的网络中，每个用户独自控制设备（即网络中的节点），不受他人的管理与监督；并且这样的网络一般没有一个共同的目标或任务[1]。此外，节点协助其他节点时要消耗自己有限的资源，如电源能量、CPU处理时间等，因此一些节点为了保存更多的资源来满足自身通信的需求，它们会拒绝提供路由发现服务、拒绝转发其他节点的分组等。

因此，如何激励无线网络中的自私节点协作是一个需待解决的问题。博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。因此利用博弈理论的研究无线网络中自私节点的协作及其激励方法是一种行之有效的办法[2]。

一、无线网络的合理性假设

利用博弈理论对无线网络中自私节点的协作行为进行研究，首先要建立无线网络的博弈理论模型，但是在建立模型之前，还要对无线网络进行适当的理论分析与处理。因此本文首先建立无线网络如下合理性假设：

（1）网络中存在n个节点，且都是理性且自私的。（理性且自私是指节点不会自愿提供分组转发等服务，并始终将能够最大化自身效益的策略作为最佳策略）；

（2）时间T被分隔成为时间槽T1，T2，T3，...，Tn，节点在每个时间槽内完成一次会话；

（3）無线网络是一个多跳网络，即不在彼此的传输范围内的两个节点进行通信时，需要借助其他节点的转发；

（4）在整个会话过程中路由没有失效，节点也没有出现故障；

（5）所有会话中，分组最终到达目的节点所经过的平均跳数为M，整个网络的转发负载是均衡分布的；

（6）任何节点在接收和发送（包括转发）分组时都要消耗有限的资源。与之相比，节点在处理分组时的资源消耗可以忽略不计；

（7）所有分组长度相同，节点发送一个分组时所消耗的资源相等，节点接收一个分组时所消耗的资源相等。

二、节点协作纳什均衡的分析框架

根据以上的假设，我们可以将任何两个节点之间的一次会话看做是一次博弈。如果两个节点之间仅仅进行一次会话，我们称之为一次性博弈，如果两个节点之间进行两次或两次以上的会话，我们称之为重复博弈。在重复博弈中，任何一个节点做出的策略选择都会影响博弈的结果，同时也会对下次的会话产生直接的影响。

目前，针对无线网络中节点协作的研究大致可分为外在、内在两种角度。前者通过引入虚拟货币和声誉值等外部机制来迫使节点协作，而后者则通过分析和利用利益驱动的本质对节点决策行为的影响来引导合作[3]。无线网络中，自私节点的不协作行为虽然能够增加自己的生存时间，却大大降低了网络的性能及网络寿命。因此，无线网络中自私节点之间一次性博弈的结果与囚徒困境的纳什均衡相似，而这不是一个全局满意的结果。因为重复博弈可以使囚徒摆脱相互不合作的困境，实现一个令人满意的纳什均衡，所以对自私节点重复博弈的纳什均衡进行研究，能够从内在的角度出发在本质上提高无线网络中自私节点的协作性。

用博弈论研究无线网络中节点协作的纳什均衡时，必须先建立无线网络的相关模型，然后利用模型进行相应的分析。而一个完善的节点协作的纳什均衡分析框架应该包含以下几个部分：

（1）分析单阶段博弈中节点协作的纳什均衡；

（2）分析重复博弈中采用经典策略（包括冷酷策略、礼尚往来策略、单步触发策略等）时节点协作的纳什均衡及条件；

（3）对重复博弈中不同策略的纳什均衡条件进行比较。

首先，利用博弈论知识对第一部分进行了研究，建立了无线网络中包转发策略的分析模型，对合作和非合作策略下取得纳什均衡的条件进行了分析，结果表明在非协同性的网络中需要增加激励机制以加强节点协作；其次，提出了一个改进型的礼尚往来策略，通过分析得出自私节点采用此策略时系统可以达到一个相对稳定的纳什均衡点；最后，分析了单阶段博弈和重复博弈中采用经典策略时节点协作的纳什均衡及其条件。

综合以上内容，可得出一个比较完善的纳什均衡分析框架，具体描述如下：首先要提出一个节点协作的博弈理论模型，利用该模型对单阶段博弈（即一次性博弈）中节点协作的纳什均衡进行一次分析；其次分别构建重复博弈中节点采取冷酷策略、礼尚往来策略、单步触发策略和完全协作策略时的概率模型，接着分析重复博弈中节点采用以上几个策略时协作的纳什均衡条件；最后再对不同策略的纳什均衡条件进行比较，得到重复博弈中激励自私节点协作的最佳策略。

参考文献：

[1]L. Buttyan and J.-P. Hubaux，Stimulating Cooperation in Self-organizing Mobile Ad Hoc Networks[J].In ACM/Kluwer Mobile Networks and Applications，vol.8，no.5，pp.579-592，Oct. 2003.

[2]Seredynski， M&Bouvry P.Evolution of cooperation in Ad Hoc Networks under Game Theoretic Model[C].Proceedings of the 4th ACM international workshop on Mobility management and wireless access.Terromolinos，Sqain，2006：126-130.

[3]陆音，石进等.基于重复博弈的无线自组网络协作增强模型[J].软件学报，19（3），2008：756-768.