基于博弈理论的无线自组织网增强协作模型研究

李添泽武穆清李沛哲廖文星马 伟（北京邮电大学信息与通信工程学院 北京 100876）（网络与体系架构与融合北京市重点实验室 北京 100876）（中国科学院信息工程研究所 北京 100093）

基于博弈理论的无线自组织网增强协作模型研究

李添泽①②武穆清①②李沛哲①②廖文星①②马 伟*③
①（北京邮电大学信息与通信工程学院 北京 100876）②（网络与体系架构与融合北京市重点实验室 北京 100876）③（中国科学院信息工程研究所 北京 100093）

为了解决无线自组织网络中转发节点因自身能量与存储空间限制而拒绝协作的自私性问题，该文从分析数据包源节点与转发节点的收益与开销特性出发，基于虚拟货币的奖励机制，结合博弈理论提出无线自组织网络增强协作模型。该模型将网络协作问题转化为数据包转发路径中多转发节点与源节点收益的博弈均衡问题，在保障双方利益的基础上提出最优的激励方式，促进通信协作的进行。另外，为最大化网络生存时间与避免拥塞，该模型对转发节点的电量与存储空间状态做了相应的约束。

无线自组织网；自私性；增强协作；博弈；虚拟货币

1 引言

无线自组织网络是一种采用无线通信方式、动态组网的移动性对等网络，具有快速部署、动态组网、高抗毁性等优点，在军事通信、抗震救灾、工业控制等方面具有广阔的应用前景。无线自组织网络的各种网络协议都是以各节点积极参与通信协作为前提的，然而在实际应用中由于网络节点能量限制、内存限制或其他资源的限制等因素而拒绝协作的现象大有存在，如果网络中有 10%～40%的节点不参与协作，那么网络的平均吞吐量将降低16%～40%［1，2］。因此加强节点间的协作一直是无线自组织网络中研究的热点，目前主要有基于惩罚的机制和基于博弈的激励机制两种方法［3］。前者的基本思想是通过观察和监控节点的合作行为并对不合作的节点进行惩罚，从而保证所有节点都能积极合作。Watchdog方法［1］，CONFIDANT算法［4］，CORE机制［5］和Pathrater机制［6］均属于此类方法。基于博弈的激励机制主要是应用博弈论的相关知识，增强节点之间的合作转发。随着博弈论被应用于无线网络［711］-该方案得到了广泛的关注。Ad hoc VCG［12］是通过激励中间节点给出它们转发所需的真实成本，从而实现转发策略。文献［13］提出钱包与改进的购买方式，文献［14］提出Sprite方案，即建立可信的结算中心来计算各个节点发送数据包时留下的收据。文献［15］将经济学上的委托代理引入无线自组织网络，提出了基于虚拟货币的激励模型。文献［16～19］分析了博弈理论对增强节点协作的作用，文献［20］研究了基于演化博弈机制的物理层安全协作方法，文献［21～24］研究了基于声誉的增强节点协作的作用，文献［25，26］研究了竞价理论在促进节点协作中的应用。

本文结合博弈论的相关理论与虚拟货币的机制，建立基于节点收益最大化的增强合作模型。首先分析了在数据包转发过程中源节点与转发节点的收益情况，转发节点消耗自身资源为源节点提供满足一定性能要求的数据转发服务，同时获得源节点支付的虚拟货币，源节点获得服务并支付相应的虚拟货币。该模型对转发节点剩余能量、剩余存储空间做了合理约束以最大化网络生存时间并减少拥塞的发生，转发节点的服务能力因素以保证源节点对服务质量的需求。

2 博弈论模型

2.1 收益分析

本模型基于虚拟货币机制，源节点发送数据时需要向转发节点支付一定量的虚拟货币作为报酬。假设节点具有趋利性，对事件做出反应前会对收益与付出的代价进行权衡。数据发送过程中，源节点的收益是数据得以传送，代价是为转发节点提供一定的虚拟货币。转发节点的收益是转发数据获得的虚拟货币，代价是消耗自身能量与存储空间。目的节点是信息的接收方，其只需要接收到达的信息即可，不需要为信息接收支付货币，在本模型中不对目的节点进行讨论。

为了定量分析转发节点的自私特性，本文提出努力程度的概念，其反映节点对转发数据的积极程度。假设转发节点的努力程度主要影响其所能提供的带宽与转发效率等因素，而转发时延等因素与节点努力程度无关。数据在传送的过程中，一般要经过多次转发才能成功到达目的节点，对于转发路径中的某个节点i，假设其转发时延为 ti，节点其努力程度为 ai，其产出函数为

f（ai，ti）表示转发节点i在努力程度 ai转发时延为 ti时带来的产出；θi～ N（0，σ）表示由不确定性因素带来的产出。

在数据包转发路径中，转发节点i的电量状态用ei表示，已用存储空间状态用 mi表示，初始电量状态用表示，初始存储空间状态用 m表示，则转发节点i自身状态可表示为 （ei， mi，e，m。节点i参与转发行为时自身的消耗为

g（ai）表示节点i努力程度为 ai时所产生的消耗； h（ei，m）是节点的机会消耗。

假设该过程中源节点为该转发节点i支付的报酬为

α为转发节点的固定性收入，β为对转发节点提供服务的激励强度。在整个转发的过程中转发节点获得的净收益为

本模型中转发节点的努力程度ia越高收益iG越大，同时付出的代价iS也越高，转发节点的协作过程中有收益也有付出，其净收益取决于收益与付出的大小，即该转发过程有一定的风险。本模型利用节点的风险偏好情况来表示其参与协作的热情。在转发的过程中假设节点都是风险规避的，为了描述节点对风险的偏好程度，本模型引入效用函数的概念［13］，即

其中r为转发节点的风险规避量，r ＞ 0，r =0，r ＜0分别代表节点是风险厌恶者，风险中性者与风险偏好者。x为转发节点的实际收入，其服从均值为w，方差为 σ的正态分布，即 x ～N（w，σ）。

中等值效用

在本模型中 x= PGi= Gi- Si，则转发节点实际收益的期望为

转发节点实际收益的方差为

转发节点中等值效用为

其中 （1/2）rβ2σ为转发节点风险成本。

假设数据包从源节点传送到目的节点的过程中有n个转发节点，对于源节点s其获得的收益为

数据包传输过程中源节点s所需支付的虚拟货币总量的期望为

源节点的净收益的期望为

2.2模型建立

节点机会消耗随剩余电量情况及存储空间使用情况的变化如图1所示，图中为剩余电量占初始电量的比例，为已用存储空间占初始存储空间的比例，由图可见剩余电量越少、已用存储空间越大节点机会消耗便越大。节点机会消耗的等高线如图2所示，规定，在实际中设定0=20h ，则转发节点可行的状态区间如图 3所示，即节点i可作为转发节点的条件为其状态处在可行的状态区间中。

（2）服务质量约束：根据不同业务的要求，数据转发路径中的节点需要提供满足一定质量要求的服务，假设源节点对转发节点努力程度要求为 A0，路径时延要求为 T0，则

（3）转发节点参与约束：为使节点i参与所设计的激励机制，则节点i获得效用的期望必须不小于其不参与该激励机制的机会效用，即

（4）转发节点激励相容约束：该约束指节点i参与激励机制的条件下，所选择行动的效用不小于选择其他行动的效用，即

（5）最大效用约束：发报方在满足以上约束条件的可行机制中，选择最大化自己效用的函数，即

综合以上分析，无线自组织网络中数据包传送的最优激励模型如式（20）所示。

图1 机会消耗图

图2 机会消耗等高线图

图3 机会消耗约束下节点可行状态区间

3 模型求解与分析

在源节点传送数据包的过程中，假设转发路径中共有n各个节点，对于传输路径中任选的某个转发节点i，设定：

努力程度为ia时的消耗设定为：

将式（14）、式（21）、式（22）代入式（20）可得：

对式（23）求导并令其导数为零，即

假设节点i为努力程度最小的节点，即 amin=min（a1，a2，…， an）=ai，对于节点 j（j ≠ i）有

当aj≥ ai时节点j的收益随 aj的增大而减小，故 aj合理的取值为 aj= ai，有

将式（26）代入式（20）并求解，可得：

转发节点i的期望产出为

转发节点i的期望收益为

源节点s的期望收益为

源节点s的期望支出为

转发节点i的确定性等值效用为

综合考虑各指标的重要程度以及收支的平衡关系，模型中的各个变量设定为并假设路径中有5个转发节点，将以上数值代入式（20），求解便可得到最优的激励方式以及源节点与转发节点的期望收益。图4，图5，图 6分别为激励强度β，节点努力程度a，转发节点的固定性收入α随节点对风险偏好程度r的变化关系。

由图4可知，源节点的激励强度β随转发节点对风险偏好程度的增强（r由大到小）而变大，由图6可知固定支付货币量α随转发节点对风险偏好程度的增强而减弱，故对于风险爱好者可以减少固定支付而增大激励强度。同时结合图4，图 5可知转发节点努力程度与源节点激励强度有相同的递增趋势。

表1为r取-0.2，-0.1，0，0.1，0.2等不同值时模型的应用结果。分析可知，源节点的激励强度β随转发节点的不合作程度而依次上升，0.14→0.16→0.20→0.25→0.33，在此激励条件下转发节点的努力程度也随之上升0.71→0.83→1.00→1.25→1.67，相应的转发节点的期望收益减少了一半，31.22→14.44，这会使转发节点从风险偏好者转变为风险厌恶者，即在确保收益的情况下节点更积极地参与通信协作。

4 结束语

本文基于博弈理论提出了一种促进无线自组织网络中自私节点参与通信协作的激励模型，探讨了在满足源节点业务质量需求的情况下如何以最小代价促使网络中的节点参与协作。一方面源节点需要得到满足业务质量要求的服务，而其拥有的虚拟货币数量有限，不能支付过高的报酬，另一方面转发节点能量、存储空间、带宽等资源有限，其提供服务的条件是获得足够的报酬。本模型基于博弈理论对数据传输过程中源节点与转发节点的收益情况进行分析，综合考虑两者的净收益情况提出最优激励方案。

本文首次提出基于数据传输全路径多转发节点的激励模型，符合无线自组织网络中数据包转发的实际状况。另外考虑转发节点能量与存储空间有限等特点，本模型设定了合理的约束机制，在一定程度上延长网络寿命并避免网络拥塞的发生。

图4 节点激励强度与风险偏好程度的关系

图5 节点努力程度与 风险偏好程度的关系

图6 节点固定性收入与其 风险偏好程度r的关系

表1 模型应用结果

［1］ Marti S and Giuli T J. Mitigating routing misbehavior in mobile Ad hoc networks［C］. MibiCOM 2000， USA， Boston，2000: 255-265.

［2］ Michiardi P and Molva R. Simulation-based analysis of security exposures in mobile Ad hoc networks［C］. Proceedings of European Wireless Conference， Firenze， Italy，2002: 275-281.

［3］ Malnar M Z and Neskovic N J. An analysis of performances of multi-channel routing protocol based on different link quality metrics［C］. International Conference on Telecommunications in Modern Satellite， Cable and Broadcasting Services， Nis，Serbia， 2011: 737-740.

［4］ Buchegger S and Boudec J Y L. Performance analysis of the Confidant protocol: cooperation of nodes-fairness in dynamic Ad-hoc networks［C］. MobiHOC， Lausanne， Switzerland， 2002: 226-236.

［5］ Michiardi P and Molva R. A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks［C］. Conference on Communications and MultimediaSecurity， Portoroz， 2002: 107-121.

［6］ 汪洋， 林闯， 李学林， 等. 基于非合作博弈的无线网络路由机制研究［J］. 计算机学报， 2009， 32（1）: 54-68. Wang Yang， Lin Chuang， Li Xue-lin， et al.. Non-cooperation game based research on routing schemes for wireless networks［J］. Chinese Journal of Computers， 2009， 32（1）: 54-68.

［7］ Akkarajitsakul K. Game theoretic approaches for multiple access in wireless networks: a survey［J］. IEEE Communications Surveys and Tutorials， 2012， 13（3）: 372-395.［8］ Brown D R and Fazel F. A game theoretic study of energy efficient cooperative wireless networks［J］. Journal of Communications and Networks， 2011， 13（3）: 266-276.

［9］ Alizadeh Y， Sabaei M， and Tavallaie O. Game theoretic modeling of joint topology control and forwarding in MANET based on local information［C］. Computational Intelligence and Communication Networks （CICN）， Mathura， India， 2013: 510-515.

［10］ Sarkar S and Datta R. A game theoretic model for stochastic routing in self-organized MANETs［C］. Wireless Communications and Networking Conference （WCNC），Shanghai， China， 2013: 1962-1967.

［11］ Rong C. Cooperative game based relay vehicle selection algorithm for VANETs［C］. Communications and Information Technologies （ISCIT）， Seoul， Korea， 2014: 30-34.

［12］ Anderegg L and Eidenbenz S. Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents［C］. International Conference on Mobile Computing and Networking， California， USA， 2003: 245-259.

［13］ Buttyan L and Hubaux J P. Enforcing service availability in mobile Ad hoc WANs［C］. MobiHOC， Boston， USA， 2000: 87-96.

［14］ Zhong S， Chen J， and Yang Y R. Sprite: a simple cheat proof credit-base system for mobile ad hoc networks［C］. INFOCOM，San Francisco， USA， 2003: 1987-1997.

［15］ 郑慧芳， 蒋挺， 周正. MANET增强合作模型的理论研究［J］.北京邮电大学学报， 2008， 31（10）: 21-24. Zheng Hui-fang， Jiang Ting， and Zhou Zheng. Theoretical study with the model for MANET cooperation enforcement［J］. Journal of Beijing University of Posts and Telecommunications， 2008， 31（10）: 21-14.

［16］ Akkarajitsakul K， Hossain E， and Niyato D. Coalition-based cooperative packet delivery under uncertainty: a dynamic Bayesian coalitional game［J］. IEEE Transactions on Mobile Computing， 2013， 12（2）: 371-385.

［17］ Li Z and Shen H. Game-theoretic analysis of cooperation incentive strategies in mobile Ad hoc networks［J］. IEEE Transactions on Mobile Computing， 2012， 11（8）: 1287-1303.

［18］ Naserian M and Tepe K. Dynamic probabilistic forwarding in wireless Ad hoc networks based on game theory［C］. Vehicular Technology Conference （VTC Spring）， Seoul， Korea， 2014: 1-5.

［19］ 张华鹏， 张宏斌. 基于重复博弈的Ad hoc网络合作转发模型［J］. 电子与信息学报， 2014， 36（3）: 703-707. Zhang Hua-peng and Zhang Hong-bin. Cooperative forwarding model based on repeated game in Ad hoc networks［J］. Jourenal of Electronics & Information Technology， 2014， 36（3）: 703-707.

［20］ 黄开枝， 洪颖， 罗文宇. 基于演化博弈机制的物理层安全协作方法［J］. 电子与信息学报， 2015， 37（1）: 193-197. Huang Kai-zhi， Hong Ying， and Luo Wen-yu. A method for physical layer security cooperation based on evolutionary game［J］. Journal of Electronics & Information Technology，2015， 37（1）: 193-197.

［21］ Tang Chang-bing， Li Ang， and Li Xiang. When reputation enforces evolutionary cooperation in unreliable MANETs［J］. IEEE Transactions on Cybernetics， 2014， PP（99）: 1-1.

［22］ Safaei Z， Sabaei M， and Torgheh F. An efficient reputation-based mechanism to enforce cooperation in MANETs［C］. Application of Information and Communication Technologies， Venice， Italy， 2009: 1-6.

［23］ Sengathir J， Manoharan R， and Kumar R. Markovian process based reputation mechanisms for detecting selfish nodes in MANETs: A survey［C］. Advanced Computing （ICoAC），Madras， India， 2013: 217-222.

［24］ 蒋小杰， 芮兰兰， 郭少勇， 等. 一种基于信誉的移动自组网区分服务激励机制［J］. 电子与信息学报， 2012， 29（7）: 1299-1303. Jiang Xiao-jie， Rui Lan-lan， Guo Shao-yong， et al.. A Reputation-based service differentiated incentive mechanism for MANETs［J］. Journal of Electronics & Information Technology， 2012， 29（7）: 1299-1303.

［25］ Liu L， Guo Y， and Yin L. Analyzing asking/bidding price in dynamic game for cooperative authentication［C］. Computer Communications Workshops （INFOCOM WKSHPS），Toronto， Canada， 2014: 165-166.

［26］ Liu Li-cai， Yin Li-hua， Guo Yun-chuan， et al.. Bargaining-based dynamic decision for cooperative authentication in MANETs［C］. Trust， Security and Privacy in Computing and Communications （TrustCom）， Beijing，China， 2014: 212-220.

李添泽： 男，1987年生，博士生，研究方向为无线自组织网络网络协议及通信网理论.

武穆清： 男，1964年生，教授，博士生导师，研究方向为宽带网络理论与信息处理.

李沛哲： 男，1990年生，博士生，研究方向为电网通信技术.

Ad hoc Network Cooperation Enforcement Model Based on Game Theory

Li Tian-ze①②Wu Mu-qing①②Li Pei-zhe①②Liao Wen-xing①②Ma Wei③
①（School of Information and Communication Engineering， Beijing University of Posts and Telecommunications， Beijing 100876， China）②（Beijing Key Laboratory of Network System Architecture and Convergence， Beijing 100876， China）③（Institute of Information Engineering， Chinese Academy of Sciences， Beijing 100093， China）

In order to solve the selfishness problem that forwarding nodes in the wireless ad hoc network refuse to cooperation due to the limit of energy and storage space， a wireless ad hoc network cooperation enhancement model combined with the game theory is proposed， which is based on the incentive mechanism of virtual currency，analysis the benefit and overhead characteristics of the source nodes and forwarding nodes. In this model， the network cooperation problem is transformed into a game equilibrium problem about the benefit of source node and forwarding nodes in the data forwarding path， promoting the cooperation of communication. Furthermore， in order to avoid the congestion and maximizing network lifetime， the model makes some certain constraint about the energy and storage space for the forwarding nodes.

Ad hoc network； Selfishness； Cooperation enforcement； Game theory； Virtual currency

The Director Funds of Laboratory of Network System Architecture and Convergence （2015BKL-NSAC-ZJ-06）

TP393.08

A

1009-5896（2015）12-2802-06

10.11999/JEIT150356

2015-03-25；改回日期：2015-08-28；网络出版：2015-11-01

*通信作者：马伟mawei@iie.ac.cn

网络体系架构与融合北京市重点实验室主任基金（2015BKL-NSAC-ZJ-06）