WMNs中基于重复博弈的机会路由激励机制研究

吴 军，莫伟伟，印新棋，白光伟

南京工业大学 计算机科学与技术学院，南京 211816

1 引言

无线Mesh网络（WMNs）是动态地自组织、自配置的分布式无线接入网络。WMNs由Mesh路由器（mesh routers）和客户端节点（client nodes）两种类型节点组成[1]，在混合结构的WMNs中，Mesh路由器移动性较小，构成WMNs的骨干结构；而无线Mesh客户端节点中具有大量移动节点，其中多数节点仍然有能源、带宽等限制，本文的策略正是针对混合结构无线Mesh网络中的移动客户端节点，此外，本文的研究前提是面向任意时刻总是连通的无线多跳网络[2]。

机会路由[3]利用了无线网络的广播特性。网络中节点覆盖范围内的邻居节点都参与监听接收，均有机会加入转发候选集，通过多跳转发完成数据传输。其中，ExOR是典型机会路由协议。相对于传统路由协议，采用机会路由协议具有更大的吞吐量。理论上网络中的节点均是理性节点，愿意参与合作转发。但是在实际应用中，移动节点可能来自很多方面，由于该节点性能、能源等原因，节点表现出自私性，尤其是拒绝为其他节点转发，但是其仍然使用网络发送与接收数据包。这种不参与合作转发的自私节点将会极大降低机会路由的性能。

本文针对机会路由中的节点的自私行为，从能量、成功转发概率以及收益方面考虑，定义一种度量邻居节点合作水平的合作度评估函数，并建立基于合作度评估函数的宽容针锋相对策略节点重复博弈模型（Cooperation degree Generous Tit-for-Tat，CGTFT）。模拟实验表明该机制能够有效抑制节点自私行为，激励节点参与合作转发，提高网络性能。

2 相关研究

针对机会路由的相关研究主要有：文献[3]提出的ExOR以及文献[4]中SOAR协议都是将无线信道的广播特性利用到路由转发中；Biswas等人文中最早提出机会路由概念，利用转发候选集来提高网络吞吐量。文献[5]中提出MORE协议，将网络编码结合到机会路由中，进一步改善了网络吞吐量。本文的路由算法基于ExOR协议，提出的机会路由重复博弈激励机制。

针对机会路由中的节点不合作与自私行为，当前研究主要有以下几种解决方法：文献[6]中采用的基于声誉的方法激励自私节点，声誉方法需要根据节点的历史交易行为，综合考虑直接信誉以及第三方信息对节点行为作出最终判断，目前声誉机制中监测的不准确性是主要问题。在文献[7]中运用VGG机制鼓励节点汇报转发所需要的真实成本，还给予一定的额外报酬，实现对自私节点的激励，该策略的局限是需要单独第三方执行清算运算。文献[8]中，提出节点公平竞价激励机制来激励网络中自私节点，并且模型化竞价过程为一个竞价博弈，存在贝叶斯纳什均衡使博弈达到平衡。

本文主要针对机会路由中节点自私问题，设计邻居节点合作度评估函数，并结合宽容针锋相对思想[9]，建立CGTFT重复博弈策略，激励网络中节点参与合作。通过重复博弈策略，迫使邻居节点考虑未来收益，积极参与合作转发，从而提高网络的性能。

3 机会路由中节点自私性分析

在机会路由利用广播特性进行路由发现阶段，网络中节点通过信息交互获得其邻居节点以及相应的链路情况。此时，自私节点为了避免转发邻居数据包，会有多种策略来使自己逃避转发工作。根据节点的行为，自私节点分为以下几类[10-11]：（1）节点参与网络服务，但是不愿转发数据包。典型策略是丢弃来自其他节点的数据包或者延迟至空闲期转发。节点不参与转发工作将会节省大量能量。（2）不参与路由服务，在ExOR路由协议中，自私节点阻止网络把自己作为中继节点，自私节点可以直接忽视其他节点的路由请求，不参与链路状态应答。

上述不合作的自私行为将导致机会路由候选集中节点减少，网络吞吐量下降。所以需要一种机制来激励邻居节点参与合作转发。

4 基于合作评估函数的CGTFT策略

4.1 时隙博弈与重复博弈

首先作如下假设：

（1）网络中节点均为理性自私节点。

（2）网络为离散时间模型，每个时隙t内均为一次博弈过程，博弈策略相同。

（3）整个网络G有N个节点随机分布，且节点仅有有限能量，初始能量为Ei。

（4）假设传输数据包传输失败主要是节点的自私和不合作所致。

数据从源节点S发送至目的节点D，需要一个或多个中间节点概率性转发。假设节点 j根据自身情况决定对数据包是转发还是丢弃，节点i将给予r的奖励来激励节点 j转发数据，同时节点 j付出s能源来完成转发。上述情况中，时隙博弈相当于囚徒困境，节点在博弈中追求利益最大化，最终选择(0,0)策略达到纳什均衡。时隙博弈收益和策略见表1。

表1 博弈收益和策略

机会路由中，每个节点由于能源等限制，趋向于不参与合作，选择自私，单次博弈无法激励自私节点。实际网络中，所有节点都周期性选择策略，这样对于所有节点，形成无限重复博弈；当博弈结束时间无法预期，节点将评估其采取的策略对其将来收益的影响。

假设一个节点接受转发概率为 f,f=0表示拒绝转发，f=1表示接受所有转发请求。任意一个节点用i表示，则-i表示博弈对方节点。若时隙tn节点收益为：

则重复博弈收益函数为：

当经过重复博弈后，网络中节点都趋向合作，采取合作策略，接受转发请求，则节点i重复博弈后的收益函数为：

4.2 合作度评估函数

由于机会路由中移动节点动态拓扑及链路的不确定性，数据会传输失败及重传。定义节点i成功转发数据包为pis(t)，接收数据包为 pir(t)，则该节点时隙t时数据包成功转发概率为：

在面对节点的路由请求时，自私节点在博弈时有下列倾向：其一，自私节点更愿意选择转发成功率高以及能量高的邻居节点作为备选节点来转发数据包。其二，邻居节点的合作水平与其获得的效益相关，获得的效益越大，那么其接受请求的概率也越高。为了选出趋向合作的下一跳节点，本文定义合作度评估函数（以下简称合作度），见公式（5）：

4.3 基于合作度评估函数的CGTFT策略

针锋相对TFT[12]是重复博弈的一个典型策略。思想如下：博弈双方节点i和 j，在某一时隙节点i的策略总是参照上一个时隙对方节点 j采用的策略；若 j选择转发，i也选择转发策略，若 j拒绝，i亦拒绝。该策略中，节点一旦进入惩罚期，无法恢复合作状态。而GTFT策略是在TFT策略的基础上添加遗忘因子g来帮助节点恢复合作。

本文结合合作度评估函数与GTFT思想，建立CGTFT博弈激励策略，以邻居节点的合作度作为博弈判断的标准。在博弈中，添加遗忘因子g到策略中，使节点具有恢复合作机制，模型化基于合作度评估函数的CGTFT策略如下所示，其中表示邻居节点的合作度评价函数，m=[(1 -p)g]且假定为偶数：

当网络中每个节点均采用CGTFT策略，若节点i单方面改变其接受请求概率，则其合作度评估函数也会随之改变，令节点合作度评估函数为 p，那么其对手节点根据CGTFT策略做出响应：（1）对节点行为轻微程度的偏离，p≥1-g，将会容忍，其正常转发数据；（2）对节点行为偏离程度较大的节点，p＜1-g，定义为不合作，其对手将会调整合作度至 p+g。表2为单次不合作的博弈策略。

表2 CGTFT单次不合作博弈策略

根据公式（2）得，CGTFT策略中单次不合作时，节点i收益函数：

经过CGTFT策略激励后，重复博弈趋向合作平衡时需满足：

因为g＞0且0＜δ＜1，上式可转换为：

因为上式两括号内多项式均大于0，所以CGTFT激励策略激励节点达到合作平衡的条件是：

假设机会路由中所有节点均遵从CGTFT博弈激励策略，若符合平衡临界条件r/s＞H，节点i以任意概率接受请求，0＜p＜1，那么节点单方面改变获得的收益都小于采取合作获得的收益，最终节点将趋向于选择合作，达到纳什均衡，起到抑制自私行为的目的。

在CGTFT策略中，在满足该策略平衡临界条件下，遗忘因子g的降低以及贴现因子δ的增加都有利于抑制自私行为，从而促使各节点趋向于合作。证明如下：在公式（8）中，对ECGTFT求g偏导，在r,s,p,δ等参数不变情况下，降低g导致ECGTFT增加，即自私行为受到惩罚将增加；对ECGTFT求δ偏导，在r,s,p,g等参数不变情况下，增加δ导致ECGTFT的增加，即采取自私行为所受惩罚增大。在CGTFT中，除了贴现因子δ外，遗忘因子g对自私行为所受惩罚有重要影响，g的大小影响节点采取自私行为后恢复合作状态所需要的单阶段博弈次数，g越小，恢复合作所需要的博弈次数越多，遭受的惩罚期越长。

4.4 基于合作度评价函数的CGTFT博弈算法

本文的博弈算法是网络中数据包发送节点与邻居节点之间，通过CGTFT策略进行两两博弈的过程，博弈的判断标准是本文提出的邻居节点合作度评价函数，网络中所有节点都将周期性地选择策略，整体上看，形成一个重复博弈的过程。其算法的具体流程描述如下所示[13-14]：

（1）初始化参数。

（2）源点向邻居节点广播发送路由请求，以及评估各邻居节点的合作度。

（3）对比ExOR候选集中所有节点的合作度，将合作度低于阈值 pthreshold节点排除出候选集，然后选取ETX值最大的节点为下一跳转发节点。

（4）对于该节点采取何种行为，根据本文的CGTFT策略可知，该源点即对手在上个时隙合作度是 p，若p≥1-g，则容忍行为偏离，执行转发策略，并跳转（6）。

（5）若 p＜1-g，则定义该节点为自私节点，下个时隙该节点的对手节点将采取 p+g的合作度执行策略，后面过程重复CGTFT策略。

（6）重复（2）到（6）步骤，直到数据到达目的节点，算法结束。

5 仿真实验分析

本文运用NS2进行仿真实验，其中MAC层协议采用IEEE802.11协议[15]。机会路由ExOR协议中节点随机分布，节点都遵循相同的博弈策略。网络中节点运动按照Random Waypoint Model方式移动。规定在网络生命周期内，节点进入惩罚期，节点可能由于能量耗尽或者过于自私原因，在本文的CGTFT策略激励下，节点仍然无法重建，恢复合作，定义该节点死亡。其他仿真参数如表3所示。

表3 仿真参数

本文选择的性能评价指标是网络生命周期的节点数变化情况、网络总能耗变化情况以及不同比例自私节点情况下的吞吐量变化情况。

为了证实本文提出的CGTFT策略对节点自私行为的激励效果，本文仿真了r/s=4,g=0.01,δ=0.6时策略性能比较[16]。图1说明的是随着博弈轮数的增加，网络生命周期中的节点数变化情况。从图1可知，随着博弈轮数的增加，本文的CGTFT重复博弈策略的节点死亡数低于囚徒困境（TFT）策略，尤其在博弈前期，TFT策略中死亡节点增速明显高于本文的CGTFT策略。原因有两个：其一，本文在合作度评估函数中具有能量模型，剩余能量对节点的合作度评估有较大的影响，避免能耗不均衡和部分节点能量快速耗尽，一定程度上延长了节点生命时间。其二，本文CGTFT策略中提供合作重建机制，其策略中具有遗忘因子g，节点进入惩罚期后，经过一定周期，节点会恢复合作。

图1 网络生命周期

图2说明的是网络总能量消耗情况。从图2可知，与TFT策略相比，本文CGTFT策略下的能耗增加总体比较平缓，并且总能耗也低于前者。这是因为在本文的邻居节点合作度评估函数的定义中，考虑了成功转发率以及能量因素，在路由选择时，节点会选择合作度高的节点转发，一方面其成功转发率高，减少传输失败再重传的能耗；另一方面能量模型可以均衡节点能源消耗，尽量避免节点能耗过低导致的传输失败，继而再重传的耗能。

图2 网络总能耗

图3给出的是在不同比例自私节点情况下，网络吞吐量累计分布情况。从100个节点中随机选取匹配发送节点和目的节点，统计发送数据包100次的结果，仿真比较以下三种情况的吞吐量累计分布：ExOR协议没添加激励策略时，网络中分别存在20%和40%自私节点的吞吐量分布情况以及添加本文提出的CGTFT激励策略时的吞吐量分布情况。仿真重复实验5次，最终结果取平均值。如图3所示，当自私节点比例增加到40%。曲线左移，吞吐量较低，所占比例明显增多。而当加入本文的CGTFT激励机制后，节点选择合作度较高的节点来转发。CGTFT激励策略下网络吞吐量和20%和40%自私节点时候相比，较高吞吐量所占比例有明显提升；其中，在CGTFT激励策略下，超过90%的链路吞吐量达到52数据包每秒。而无激励时吞吐量分别为30和41个包每秒，主要因为合作度高的节点转发成功率较高，而且均衡节点能量消耗，整体上提高了网络性能。

图3 吞吐量累计分布

6 总结

本文提出了一种基于邻居节点合作度评估函数的CGTFT重复博弈模型。对于网络中的理性节点，从节点剩余能量，成功转发概率角度设计了合作度评估函数概念，然后通过CGTFT重复博弈策略进行博弈，对网络中参与合作转发的节点给予一定收益，对自私不合作节点给予一定周期的惩罚，并添加了遗忘因子，对进入惩罚期的节点进行合作重建。仿真表明，该激励机制能够有效迫使网络中自私节点参与合作，提高吞吐量以及网络性能。

：

[1]Akyildiz I F，Wang X.A survey on wireless mesh networks[J].IEEE Communications Magazine，2005，43（9）.

[2]田克，张宝贤，马建，等.无线多跳网络中的机会路由[J].软件学报，2010，21（10）：2542-2553.

[3]Biswas S，Morris R.ExOR：opportunistic multi-hop routing for wireless networks[J].ACM Special Interest Group on Data Communication，2005，35（4）：133-144.

[4]Rozner E，Seshadri J，Mehta Y，et al.SOAR：Simple Opportunistic Adaptive Routing protocol for Wireless Mesh Networks[J].IEEE TransactionsonMobileComputing，2009，8（12）：1622-1635.

[5]Chachulski S，Jennings M，Katti S，et al.Trading structure for randomness in wireless opportunistic routing[J].ACM Special Interest Group on Data Communication，2007，37（4）：169-180.

[6]Chen K，Nahrstedt K.iPass：an incentive compatible auction scheme to enable packet forwarding service in MANET[C]//InternationalConferenceonDistributedComputing Systems，2004：534-542.

[7]Anderegg L，Eidenbenz S.Ad hoc-VCG：a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents[C]//InternationalConference on Mobile Computing and Networking，2003：245-259.

[8]Han Z，Pandana C，Liu K J，et al.A self-learning repeated game framework for optimizing packet forwarding networks[C]//Wireless Communications and Networking Conference，2005：2131-2136.

[9]Wu F，Gong K，Zhang T，et al.COMO：a game-theoretic approach for joint multirate opportunistic routing and forwarding in non-cooperative wireless networks[J].IEEE Transactions on Wireless Communications，2015，14（2）：948-959.

[10]Dapeng Q U，Wang X，Huang M，et al.Selfish node detection and incentive mechanism in mobile P2P networks：selfish node detection and incentive mechanism in mobile P2P networks[J].Journal of Software，2014，24（4）：887-899.

[11]Zhang K，Wang R，Qian D，et al.AIM：an auction incentive mechanism in wireless networks with opportunistic routing[C]//Computational Science and Engineering，2010：28-33.

[12]Srivastava V，Neel J，Mackenzie A B，et al.Using game theory to analyze wireless ad hoc networks[J].Communications Surveys&Tutorials，2005，7（4）：46-56.

[13]Wu F，Chen T，Zhong S，et al.A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks[J].IEEE Transactions on Wireless Communications，2013，12（4）：1573-1583.

[14]Froushani M H，Khalaj B H，Vakilinia S，et al.A novel approach to incentive-based cooperation in wireless ad hoc networks[C]//international Conference on Telecommunications，2011：78-83.

[15]Yan L，Hailes S，Capra L，et al.Analysis of packet relaying models and incentive strategies in wireless ad hoc networkswithgametheory[C]//AdvancedInformation Networking and Applications，2008：1062-1069.

[16]Sun Yuxing.On incentive strategies for trust recommendations in wireless ad hoc networks with probability game[J].Computer Science，2011，38（4）：65-71.