基于重复博弈的Ad hoc网络合作转发模型

张华鹏 张宏斌

(苏州大学计算机科学与技术学院 苏州 215006)

1 引言

Ad hoc网络是一种无需基础设施支持的自组织网络，网络的功能通过节点间合作实现。在实际的网络中，由于节点存在自私性使得它们为了保存能量而不愿参加与己无关的数据转发活动。经研究发现，节点的自私行为不仅严重降低网络整体性能，而且威胁网络安全[1]。因此，在一些领域的Ad hoc网络应用中，设计促进网络中节点合作的策略机制变得十分关键。

Ad hoc网络中的合作激励机制分为两类：基于信用的机制和基于信誉的机制。基于信用的机制[26]-将经济学中的激励手段应用到 Ad hoc网络中，但该类机制需要使用防更改硬件或第3方信任机构，这影响了该类机制的推广应用。在基于信誉的机制中[1,713]-，节点观察其它节点的行为，并根据信誉推断网络中的自私节点。

对于基于信誉的机制，可以使用博弈模型分析节点间的交互并给出相应的均衡策略[7,8,14,15]。文献[7]运用合作博弈模型对节点间交互进行建模，但节点在选择策略时需进行复杂的信息交换，消耗的能量较多。针对该问题，文献[8]采用非合作博弈模型分析节点间的交互。非合作博弈模型不仅不需要节点间交换信息，而且能够很好地反应Ad hoc网络节点的困境：是为了增加自身的信誉值选择合作还是为了节省能量选择不合作。文献[8]使用完美信息重复博弈模型分析节点间的交互，并给出满足子博弈完美均衡的策略组合。然而在Ad hoc网络中，由于无线信道容易受到干扰等特点，大多数情况下节点掌握的信息是不完美信息。针对该问题，文献[15]采用不完美信息重复博弈模型分析节点间的交互，并给出对应的序贯均衡策略。但该文献使用简单的触发机制构造序贯均衡策略，当观测误差较大时，网络的合作率较低。

本文在文献[15]的基础上，给出了不完美信息下另一种满足序贯均衡的策略组合。与文献[15]中的机制相比，本文使用贝尔曼方程构造策略，避免使用对观测误差非常敏感的触发机制，提高了不完美信息环境下网络的合作率。

2 不完美信息重复博弈

2.1 博弈模型

假定Ad hoc网络中的节点可以使用watchdog[1]等机制观察其它节点的行为。由于无线信道的特点，节点的观察存在误差，故节点掌握的信息是不完美信息。将一段时间内网络中任意一对节点之间的交互看作一轮两人静态博弈 G。因此可以使用不完美信息重复博弈模型(,,)GΓδ λ分析Ad hoc网络中任意一对节点间的交互，其中δ为贴现因子，说明了该对节点继续博弈的概率，λ为观测误差。

对于重复博弈Γ，博弈双方为网络中的任意一对节点，记为i和j。在单轮博弈G中，博弈双方同时从行为空间A={F,D}选择行为，F为转发对方数据包，D为丢弃对方数据包；并观察对方的行为，f为观察到对方的转发行为，d为观察到对方的丢包行为，令Ω={f, d}。由watchdog等机制的原理可知：对于对方的转发行为F，博弈者依概率1-λ观察到f，依概率λ观察到d；对于对方的丢包行为D，博弈者仅能观察到d。博弈者的转发行为F消耗节点资源，对方转发自身数据包时节点会获得利益，假定数据包的价值大于转发行为的成本，归一化后的收益矩阵如图1所示。图中。假定表示在第t轮博弈中节点i的收益，那么节点i在重复博弈Γ中的收益为

图1 博弈G中的收益矩阵

2.2 序贯均衡

对于不完美信息重复博弈，序贯均衡[16]不仅满足一致性，而且满足序贯理性，即对于博弈双方的信念以及所有可能到达的信息集[17]，每个博弈方的策略都是针对其他博弈方策略的最佳对策。因此满足序贯均衡的激励机制比满足纳什均衡的机制有更好的稳定性和适用性。

定义 1 称s=(si,sj)为无显著偏离(no observable deviation[18])的策略组合。若对于每一个博弈者i，其任何一个没有到达的信息集可以且仅可以通过博弈者i本身偏离策略si到达。

定理 1 对于不完美信息无限次重复博弈Γ，若纳什均衡策略 s为无显著偏离的策略组合，且 s在博弈Γ中没有到达的信息集上也构成纳什均衡策略，那么s是博弈Γ的序贯均衡策略。证明见文献[18]。

2.3 已有模型分析

文献[15]使用不完美信息重复博弈分析节点间交互，并提出满足序贯均衡的策略机制。文献[15]在构造策略时使用两种连续策略：触发策略Fσ和背叛策略Dσ。

触发机制对观察误差比较敏感，若节点的观察结果在t轮之前不全为f，那么在t轮之后的博弈中始终选择背叛行为 D。因此，在观察误差较大的环境中，该类机制的合作率较低。本文采用基于贝尔曼方程的序贯均衡策略所采取方法并不是“触发机制”而是针对背叛策略，采取一定程度忍耐方式，从而抵消文献[15]中由于观测误差导致合作率不高的结果出现。第5节进一步分析该类机制，并通过仿真比较两种序贯均衡策略的性能。

3 序贯均衡策略

3.1 构造策略

图2 节点策略构造流程图

图2描述节点策略的构造。初始化阶段，节点根据网络确定收益矩阵中的参数g, l，初始化参数t,k, t=0, k=0，并计算出数列。在第t轮博弈中，节点首先确定自身的行为：以概率mk选择合作行为F；以概率1-mk选择不合作行为D。在每一轮博弈结束时，节点观察对方的行为：若观察到对方选择合作行为(即)，将观察到对方连续不合作次数归零(k = 0)；若观察到对方选择不合作行为(即)，则k = k +1。构造策略s的关键是如何确定，使得对方在任何博弈点选择F行为和D行为获得的总收益相等。

节点策略构造算法如表1所示。

表1 节点策略构造算法

在首轮博弈中(t = 0, k = 0)，节点“友好”地选择转发行为；节点观察到对方的转发行为时，同样选择转发行为。根据对方选择转发行为F和丢包行为D时(对方)所得收益，可得贝尔曼方程：

解该方程得

更一般的情况，当节点连续k (k ＆gt; 0)次观察到对方的丢包行为时，根据对方选择转发行为和丢包行为时(对方)所得收益，可得贝尔曼方程：

解该方程可得

3.2 策略分析

由s可知，在首轮博弈中，节点j选择转发行为F，因此i可以通过偏离si到达所有信息集。假定在第t(t ＆gt; 0)轮博弈中，节点j选择转发行为的概率是mk。若mk= 0，那么节点i可以通过在第t -1轮博弈中选择F行为使得mk＆gt; 0，因此在第t轮博弈中i可以通过偏离策略 si到达所有的信息集。综上所述，节点i可以通过偏离策略si到达任何信息集。j与i采用相同策略，因此j也可以通过偏离sj到达任何信息集，s无显著偏离。 证毕

证明 对于策略s*，任何一个节点i(j)单独偏离策略其总收益不会增加，因此*s是博弈Γ的纳什均衡策略。因为在博弈的任何阶段，任意一个博弈者i(j)偏离策略其总收益不会增加，因此*s在没有到达的信息集上也是纳什均衡策略。由引理1及定理1可知，*s是无限次重复博弈Γ的序贯均衡策略。

证毕

图3是mk随k的变化趋势，参数l = 3, g = 2,δ=0.99, λ=0.03。从图3中可以看出，随着连续观察到对方丢包次数的增加(k的增加)，节点选择转发行为的概率(mk)逐渐降低，最终趋于稳定值 m。从式(8)可以看出，博弈者i的对手收益也是随着自身丢包行为次数增加而减少。博弈者 i也以较低的概率m选择转发行为F。由于博弈对称特性，博弈者i丢包行为次数将随之增加，也会导致博弈者i的收益减少。最后双方将会在一个较低的转发行为概率值mk=m范围内达到平衡。但不会出现mk=0的情形。若对方始终选择丢包行为，博弈者 i以较低的概率m选择转发行为F，降低了节点的损失。若对方为正常节点，由于信息的不完美性导致节点(连续)观察到丢包行为，博弈者i以较大概率mk试图与对方恢复合作，提高了网络的合作率。

4 仿真

图3 mk 与 k 的关系

在仿真中，本文给出基于贝尔曼方程的序贯均衡策略，与文献[15]中的序贯均衡策略进行比较。对于文献[15]中的模型，为了获得更好的收益，文献[15]将重复博弈Γ分割为N个重复博弈NGΓ。

从合作率、平均收益和对不同网络环境的适应性3个方面考察两种序贯均衡策略的性能。仿真模拟了 4种类型的策略，S*为本文给出的序贯均衡策略；S'为文献[15]中的策略；Sc为合作策略，节点始终选择转发行为F; Sd为背叛策略，节点始终选择丢包行为D。

图4为分别使用策略S*和S'时，网络的合作率、平均收益随观察误差的变化曲线。实验参数为：g =2,l = 2, δ=0.99。对于策略S'，作者使用简单的触发机制构造该策略，触发机制对观察误差非常敏感。因此，随着观察误差的增加，网络的合作率、节点的平均收益迅速降低。对于策略S*，当观察出现误差时，节点以一定的概率恢复合作，提高了网络的合作率和节点的平均收益。仿真结果表明，网络采用策略S*时，合作率、平均收益与观察误差呈现出近似的线性关系。随着观察误差的增加，合作率、平均收益没有显著下降。

图5反映了在不同的网络环境中，使用策略S*,S'和Sc时节点的平均收益。实验参数为：g = 2, l =2, δ= 0.99, λ= 0.03。对于策略Sc，节点始终选择转发行为 F，随着网络中自私节点比例的增加，节点的收益快速下降。策略S*在面对自私节点时，以概率m选择转发行为F，一定程度上减少了损失。策略S'使用了触发机制，如果观察到自私节点的丢包行为 d，那么节点在之后的博弈中始终选择不合作行为D。因此策略S'收到的影响最低。

5 结论

一种有效的合作激励机制可以防止节点自私行为的发生。本文应用不完美信息重复博弈模型分析Ad hoc网络中节点的交互，使用贝尔曼方程构造满足序贯均衡的合作激励机制。与已有的序贯均衡相比，本文给出的序贯均衡策略避免使用触发机制，提高在不完美信息环境下的性能。仿真结果表明，本文给出的序贯均衡策略不仅提高了网络的合作率和节点的平均收益，而且提高了机制的适应性。

图4 合作率和平均收益与参数λ的关系

图5 节点的平均收益随自私节点所占比例的变化

[1] Marti S, Giuli T J, Lai K, et al.. Mitigating routing misbehavior in mobile ad hoc networks[C]. Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCom’00), Boston, MA, 2000: 255-265.[2] Mahmoud M M E A and Shen X. FESCIM: fair, efficient, and secure cooperation incentive mechanism for multihop cellular networks[J]. IEEE Transactions on Mobile Computing, 2012,11(5): 753-766.

[3] Zhong S, Chen J, and Yang Y R. Sprite: a simple, cheat-proof,credit based system for mobile ad-hoc networks[C].Proceedings of the IEEE INFOCOM,03, San Francisco, CA,2003: 1987-1997.

[4] Cutillo L A, Molva R, and Önen M. PRICE: privacy preserving incentives for cooperation enforcement[C]. World of Wireless, Mobile and Multimedia Networks (WoWMoM),San Francisco, California, USA, 2012: 1-9.

[5] Kaushik R and Singhai J. Modspirite: a credit based solution to enforce node cooperation in an ad-hoc network[J].International Journal of Computer Science Issues, 2011,8(2/3): 295-302.

[6] Mahmoud M E and Shen X M. Credit-based mechanism protecting multi-hop wireless networks from rational and irrational packet drop[C]. Global Telecommunications Conference, Waterloo, Canada, 2010: 1-5.

[7] Saad W, Han Z, Debbah M, et al.. A distributed coalition formation framework for fair user cooperation in wireless networks[J]. IEEE Transactions on Wireless Communications,2009, 8(9): 4580-4593.

[8] Milan F, Jaramillo J J, and Srikant R. Achieving cooperation in multihop wireless networks of selfish nodes[C]. Workshop on Game Theory for Networks (GameNets 2006), Pisa, Italy,2006: 3-3

[9] Michiardi P and Molva R. Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[C]. Proceedings of the Communications and Multimedia Security Conference (CMS’02), Portoroz,Slovenia, 2002: 107-121.

[10] Buchegger S and Le Boundec J Y. Performance analysis of the CONFIDANT protocol (cooperation of nodes: fairness in dynamic ad-hoc networks)[C]. Proceedings of the International Symposium on Mobile Ad Hoc Networking ＆amp;Computing (MobiHoc‘02), Lausanne, Switzerland, 2002:226-236.

[11] 许智君, 胡琪, 张玉军, 等. MANET 网络激励节点协作的信任评估路由协议[J]. 通信学报, 2012, 33(7): 27-35.

[12] Charilas D E, Georgilakis K D, and Panagopoulos A D.ICARUS: hybrid incentive mechanism for cooperation stimulation in ad hoc networks[J]. Ad Hoc Networks, 2012,10(6): 976-989.

[13] Yu K and Chen X B. Analysis of reputation-based incentive mechanisms in Ad hoc networks[C]. Internet Conference on Software Engineering and Service Science (ICSESS). Beijing,China, 2012: 333-336.

[14] Jaramillo J J and Srikant R. A game theory based reputation mechanism to incentivize cooperation in wireless Ad hoc networks[J]. Ad Hoc Networks, 2010, 8: 416-429.

[15] Ji Z, Yu W, and Liu K J R. A belief evaluation framework in autonomous MANETs under noisy and imperfect observation:vulnerability analysis and cooperation enforcement[J]. IEEE Transactions on Mobile Computing, 2010, 9(9): 1242-1254.

[16] Kreps D M and Wilson R. Sequential equilibria[J].Econometrica: Journal of the Econometric Society, 1982,50(4): 863-894.

[17] Osborne M J. A course in game theory[M]. Cambridge, Mass.:MIT Press, 1994: 1-353.

[18] Kandori M and Matsushima H. Private observation,communication and collusion[J]. Econometrica, 1998, 66(3):627-652.