一种基于重复博弈的可容错的ad hoc网络节点合作策略

谭　冕，何世彪，宋　波，杨　刚，张　晖

(1.重庆通信学院，重庆 400035；2.后勤工程学院，重庆 401331)



一种基于重复博弈的可容错的ad hoc网络节点合作策略

谭冕1，2，何世彪1，宋波1，杨刚1，张晖1

(1.重庆通信学院，重庆 400035；2.后勤工程学院，重庆 401331)

摘要：针对无线ad hoc网络中节点在数据转发阶段可能的自私行为，利用博弈理论从静态进行分析，以相邻节点对为研究对象，在重复博弈的情况下分析了针锋相对策略的脆弱性，提出了一种改进的针锋相对策略，在理论上证明了改进策略的激励性。改进策略可以容忍一定程度的网络故障，并在故障发生后使节点重新回到合作状态。仿真结果证明，改进策略对网络故障的容忍度较好，有效地促使节点合作，得到较高的网络收益，同时也降低了自私节点的收益。

关键词：无线ad hoc网络；完美信息博弈；针锋相对；自私节点；网络故障

0引言

无线ad hoc网络具有无中心、自组织、多跳等特点，数据的传递需要节点之间的合作才能保证成功。通常，理性的节点受到自身资源的限制，可能采取损害网络性能的行为。显而易见，即便只存在少量自私节点的无线自组网系统，也会极大降低网络的整体性能。

对抑制节点的自私性，文献[1]提出了严厉针锋相对策略并分别用静态和动态博弈对节点的自私行为进行建模，从群体的角度出发，用演化博弈模型解释节点由于畏惧惩罚从自私行为转向合作行为的过程。文献[2]提出了一种基于重复博弈并通过激励节点参与数据的转发过程，进而保证全局的高收益。通过仿真证明，文献中的惩罚机制可以对节点起到激励作用，并且通过对稳定性的分析可以证明机制的有效性。文献[3]提出了一种增强的基于信誉值的针锋相对模型，经过仿真证明可以鼓励理性的节点参加合作，而不是只依靠惩罚措施。文献[4]运用博弈论的方法分析了网络中自私节点之间的相互作用，并将合作的过程建模为进行无限重复的博弈过程，用最差行为的针锋相对(worst behavior tit-for-tat，WBTFT)策略来监视其它节点的行为，对表现最差的节点采取措施。由于理性的节点恐惧惩罚措施，故策略有效地促使节点合作。文献[5]构建了一种基于P2P(peer to peer)网络环境的增强的针锋相对(enhancing tit-for-tat，ETFT)策略，节点通过执行严格的针锋相对策略惩罚自私节点。文献[6-8]介绍了后文的对比策略，这些策略通过降低自私节点收益的角度抑制节点的自私性，维护网络性能。

上述研究都是基于网络无故障的情况，如果网络故障引起了节点数据传输的失败，相邻节点间相互惩罚，会使它们进入不稳定的状态，进而降低网络性能。为此本文对针锋相对(tit-for-tat, TFT)策略进行分析，提出一种能够容忍不频发的网络故障和降低自私节点收益的改进策略，在内容上拥有判断期和惩罚期，并在惩罚期结束后宽恕自私节点，尽可能地维护网络的稳定。

1系统模型

本文将着重研究相邻节点间的关系，如果网络中所有相邻节点都处于合作状态[7]，那么建立的网络也处于合作的状态，现做如下假设。

1)系统时间是由一系列的离散时隙t构成，时隙的长度足够完成数据的传输，且时隙内的路由和连接性不变。

2)当前网络中存在N个理性的节点，每个时隙各节点都要给它的相邻节点发送一定数据，也要为其转发一定的数据。

3) 所有的数据长度一样。如图1所示，如果源节点i发给目的节点r的数据被邻居节点j转发，那么节点i就会得到b的收益，由于节点j转发节点i的数据就会有-c的收益(其中b，c大于0，且b>c)。当相邻的节点对(i,j)进行博弈时，若都选择合作策略(即节点双方的数据都被对方转发)，则收益为(b-c)。若都选择不合作策略，则收益为0。当节点i选择合作策略，而节点j选择不合作策略，可知节点i获得-c的收益，而节点j获得b的收益。

4)网络是静态的，因为考察的是相邻节点对的关系，所以网络的动态与否并不影响本文的研究。具体分析如下：假设网络是动态的，t1时隙相邻节点对(i,j)处于各自的通信范围内，t2时隙不在通信范围内，t3时隙又处于通信范围内。但对节点i,j而言，它们的收益仅取决于彼此之间数据的交互。节点双方的历史策略都会被保存，并不会因为节点的离开与否而重新计算。为分析方便起见，特假设网络是静止的。

图1　节点转发模型Fig.1　Forwarding node model

2重复博弈的节点收益

由于单阶段博弈的纳什均衡解不理想，故引入重复博弈概念。节点历史行为会对后续的博弈阶段造成影响，所以相邻节点对的多次交互将不是相互独立的单阶段博弈，而形成重复策略转发博弈。

(1)

本文假设每个时隙相邻节点之间都会完成一次数据交互，故按照时隙计算节点的收益。

当相邻节点完全合作，则节点i的收益为

(2)

3改进的针锋相对策略

3.1针锋相对策略的脆弱性分析

针锋相对策略是一个用于解决囚徒困境的有效策略，会根据博弈对手的策略来制定自己下一步的策略。

TFT策略的模型为

(3)

由于网络存在的各种故障问题而导致中继节点转发数据出现丢包现象，或由于节点的理性而选择不合作策略，这将会影响节点之间的合作。例如节点i在第2个时隙出现了不合作，如(4)式所示，节点策略如同交替的数列一般，可能会引起网络的混乱。其中C代表合作，D代表不合作。

(4)

如果节点i在第3个时隙又出现了不合作，那么节点之间就陷入了死循环，并大幅度降低节点的收益，对网络造成极大的危害，具体如(5)式所示。

(5)

3.2MTTFT策略的描述

尽管TFT策略对自私节点有一定的威慑性，但其容错性较差，很可能因为故障的原因影响到节点的判断，甚至对网络造成不良影响。为改变这种情况，本文提出改良的可容错的针锋相对(mend-tolerancetit-for-tat，MTTFT)策略，其具有一定的宽容性。执行流程如下。

1)初始期：节点一开始都是合作的状态。

2)判断期：期间内需要回顾相应节点的历史策略记录[9]。当节点i的合作次数比不合作次数要多，则被认为具有合作性。邻居节点j选择合作策略，否则节点j选择不合作策略。

3)惩罚期：节点执行Thd个时隙的TFT策略，并在策略开始时选择合作态度。

4)遗忘期：惩罚时期结束后，节点遗忘掉对方博弈节点的不合作行为，重新返回阶段1)。

根据上述期间的描述，策略的宽容性主要体现在判断期和遗忘期，它们的结合是对TFT策略容错性较差的改进。

其伪代码如下

begin

parametersinitialization；

forttoTdo

获得当前节点序号n；

forntoNdo

得到邻居节点数nb并编号；

fornntonbdo

当前邻居节点序号nn；

获得获取邻居节点之前时刻与当前节点的合作状态lstates；

ifdec=1then

if前k个时刻合作次数大于k/2then

阶段计时器加1如果节点发生故障或者节点是自私节点且产生自私行为则不转发，否则转发；

else

进入TFT阶段，dec=2，清空阶段计时器，若当前节点发生了故障则不转发，否则转发；

endif

endif

ifdec=2then

if阶段计时器th>=Thdthen

dec=1且清空阶段计时器，节点发生了故障则不转发，否则转发；

else

阶段计时器加1，节点发生故障或者自私行为或邻居节点上个时隙不转发则不转发，否则转发；

endif

endif

endfor

更新对当前邻居节点的合作状态state；

endfor

计算网络中各个节点的收益；

endfor

end

3.3改进策略的激励性

1)定理1(纳什定理)：无论是混合策略还是纯策略，每个有限的策略形式博弈都具有纳什均衡。

此定理说明所有有限策略空间的策略式博弈都有纳什均衡的存在。由上述定理可知MTTFT策略存在纳什均衡，证明见文献[10]。

2)MTTFT策略中，在没有网络故障的存在，2个正常的节点由于没有外在的激励可以改变状态，初始的合作状态将会维持下去。

3)当2个相邻节点同时出现网络故障的时候，由于进入惩罚期节点的第一个时隙都被设置为合作的态度，并且同时处于针锋相对的策略，那么节点双方始终采取合作的态度直到惩罚期结束。即使在惩罚期仍有故障发生的时候，由于遗忘期的存在，在惩罚期间结束后双方会恢复到初始合作状态。

4)当不考虑网络故障时，仅讨论自私节点利用策略的宽容性获取额外利益的情况。假设k为奇数，即是说自私节点最多可以采取(k+1)/2次的不合作行为就会进入惩罚期，且当自私节点了解策略并意图取得最大收益时，必然是合作行为和自私行为交替出现。此时若连续2个自私行为出现的话，节点将进入惩罚期，若需维持判断期，诚实节点的收益为

(6)

如果Uj≥0，那么节点的收益可以接受，故有(7)式成立：

(7)

5)当节点进入惩罚期的时候，可以用定理2说明其稳定性。

定理2[11]在无限重复的博弈中，如果一个自私节点不能通过单次的不合作行为来增加自身的效益(用U1SD表示)，那么它多次的不合作行为也不能增加其效益(用UnSD表示)，UC表示节点合作产生的效益，有

(8)

通过判断背叛节点采取单次背叛行为的收益是否比合作的收益大，可知一个节点是否有偏离惩罚期策略的动机。

根据前文假设，节点i单次背叛行为所获得的利益为

(9)

根据(2)式，节点i合作所获得的收益为

(10)

(11)

所以有

(12)

所以，理性的节点在争锋相对策略期间合作获得的收益大于背离该策略，没有单方面改变自身策略的动机。综上有MTTFT策略收敛，并趋向于一个稳态，从而整个重复博弈处于纳什均衡状态。

4仿真分析

4.1对比策略

为更好地分析改进策略，将以下5种策略作为对比策略。

1)针锋相对策略(TFT)：前文已有相关介绍，不再赘述。

2)理想合作策略(IDEAL)：所有节点在任何时刻都会采取合作的态度，在仿真实验2中引入，观察网络中节点阶段收益可能得到的理想最大值。在仿真实验4中引入，作为MTTFT策略对自私节点的惩罚的对比策略。

3)冷酷触发策略(grimtrigger,GT)：在博弈中常用的触发策略，GT策略将会孤立网络中的自私节点，并极大地打击存在的自私行为。当与节点j博弈的节点i在第二个时隙选择了不合作，那么节点j在余下的时隙都会选择不合作。其表现为

(13)

4)慷慨的针锋相对策略(generoustit-for-tat,GTFT)：在遭受背叛的时候，会有一个容忍时间，在容忍期之后会对背叛节点实施一段时间的TFT策略作为惩罚，惩罚期间结束之后选择遗忘背叛行为，重新选择合作。

5)宽恕的针锋相对策略(tit-for-tatwithforgiveness,TFTF)：是在经历对方的一个不合作行为后，节点以一个小概率m(0

对比策略与改进策略在相同的网络环境中实现，并对网络节点收益数值进行比较。

4.2仿真实验及分析

理论分析后，将用仿真实验验证MTTFT策略的性质。仿真实验共分为4组，分别考察故障率、网络节点数目、节点的自私性对网络节点收益的影响。

本小节中的阶段总收益为网络中所有节点当前时隙的收益之和。网络总收益是将阶段总收益代入(1)式进行加权求和得到。节点的平均收益为当前类型的节点收益求和再除以当前类型的节点数。

仿真参数如下所示：b=8，c=2，Rm=100，Re=20，N=50，k=5，Thd=10，Th=20，m=0.1，δ=0.9，仿真语言为MATLAB。仿真实验的参数部分来自于文献[12]，仿真场景设置为100m×100m及网络节点数为50等。b，c，δ等数值的取值需要满足文中3.3节中的激励证明条件和系统模型中的条件③，并参考了文献[13]和文献[14]的相关内容。例如若满足(7)式、(12)式，则b，c，δ的取值在这个范围内即可，具体赋值也可为b=6，c=2，δ=0.8。m，Thd等数值主要从文献[15]中得到，检测概率P=1来自文献[16]。

需要说明的是，为研究方便起见特假设只要节点出现不合作行为，就一定会被邻居节点发现，即检测率P=1。仿真实验1，2，3的网络节点都是诚实节点，网络存在故障。仿真实验4的网络节点既有自私节点也有诚实节点，不考虑网络故障。

实验1考察各种策略随着故障率的变化，各自网络总收益的对比。

此时故障率为1%到5%，T=500，统计五种策略在T个时隙内的总收益。其结果如图2所示，可知不同故障情况下执行MTTFT策略和GTFT策略的节点仍可以保持良好的收益，而TFTF策略、TFT策略和GT策略会受到故障带来的较大影响，尤其是GT策略。

图2　各种策略在不同故障率下的总收益对比Fig.2　Total payoff comparison of various strategiesunder different failure rates

实验2考察不同策略下，故障率的变化对节点阶段总收益的影响。

图4　故障率为5%时策略的阶段总收益对比Fig.4　Stage payoff comparison of various strategiesunder 5% failure rates

我们选择一个较小故障1%和一个较大故障5%进行对比，并追踪150个时隙内策略的阶段收益。如图3和图4所示，面对不同的故障，MTTFT策略都能够保持平稳的收益，与理想值相差不大。而TFTF策略和GTFT策略会受到较大的波动，但仍会趋于一个稳定的数值，而TFT策略和GT策略由于没有恢复机制，所以阶段收益持续走低，并不能在一个具体的数值上保持相对稳定的状态。

实验3考察不同策略下，节点数目N的变化对网络总收益的影响。

此时故障率为1%，节点数目分别为30，40，50，T=500。为了较好地观察结果，设定通信半径Re=40，并统计五种策略在时隙内的总收益。其结果如图5所示，随着总节点数目的增加，网络总收益都随之增加，但其总收益的数值大小仍是MTTFT>GTFT>TFTF>TFT>GT。

实验4考察不同合作概率下，MTTFT策略对自私节点的惩罚度，并引入IDEAL策略进行对比。

实验1，2，3都为网络节点处于故障的情况下讨论的，证明了MTTFT策略对故障有较好的宽容性，但自私节点可能会利用这种宽容性来获得不正当收益。为了更好地观察MTTFT策略对自私节点自私性的抵抗能力，设置T=100，自私节点数量为15，自私节点的合作概率为0.7。图6的节点执行MTTFT策略，而图7为节点采用理想合作策略的对比图。对比图6和图7可知执行MTTFT策略的节点会对自私节点进行惩罚，降低其平均收益。

图5　节点数目变化对总收益的影响Fig.5　Total payoff comparison under differentnodes’ numbers

图6　自私节点和诚实节点的平均收益对比1Fig.6　Comparison of average payoff betweenthe selfish nodes and honest nodes 1

图7　自私节点和诚实节点的平均收益对比2Fig.7　Comparison of average payoff betweenthe selfish nodes and honest nodes 2

5结束语

Ad hoc网络是未来无线通信发展的重点[17]，不需要昂贵的基础设施就能自适应连接，但缺乏中心控制也就意味着用户的个体行为将会对网络性能造成深远的影响。本文基于传统的TFT策略提出了改进，并通过仿真实验从网络节点收益的角度来证明MTTFT策略具有一定的容错性，不会因为偶尔的故障导致节点间出现死循环的情况，并在一定程度上遏制了自私节点的自私性，优于其它对比策略。

参考文献：

[1]闻英友, 赵博, 赵宏. 基于博弈理论的移动自组网激励机制研究[J]. 通信学报, 2014, 35(4): 44-52.

WEN Yingyou, ZHAO Bo, ZHAO Hong. Study on game-based incentive mechanism of mobile ad hoc network[J]. Journal on Communications, 2014, 35(4): 44-52.

[2]郭晶晶, 马建峰, 李琦, 等. 基于博弈论的移动自组织网络的信任管理方法[J]. 通信学报, 2014, 35(11): 50-58.GUO Jingjing, MA Jianfeng, LI Qi, et al. Game theory based trust management method for mobile ad hoc networks[J]. Journal on Communications, 2014, 35(11): 50-58.

[3]Al D A, OTROK H, MIZOUNI R, et al. Enhanced Reputation-based Tit-for-Tat Strategy for Collaborative Social Applications [C] //Interactive Collaborative Learning, 2013 International Conference on.[s.l.]: IEEE, 2013: 192-197.

[4]NIU B,ZHAO H V,JIANG H.A cooperation stimulation strategy in wireless multicast networks[J].Signal Processing,IEEE Transactions on,2011,59(5):2355-2369.

[5]PENG D, LIU W, LIN C, et al. Enhancing tit-for-tat strategy to cope with free-riding in unreliable p2p networks [C] //Internet and Web Applications and Services, Third International Conference on. New York:IEEE, 2008: 336-341.

[6]徐占洋. 基于博弈激励的移动自组织网络关键技术研究[D]. 南京：南京邮电大学, 2013.

XU Zhanyang. Key Thchnology Research in Mobile Ad Hoc Network Base on Game Theory[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2013.

[7]王锐,朱青林,钱德沛,等.一种可容错的覆盖网节点合作激励策略[J].电子学报,2010,38(2):327-332.

WANG Rui, ZHU Qinglin, QIAN Depei, et al. A Faul-t Tolerant Cooperation Incentive Strategy for Overlay Network Nodes[J]. ACTA ELECTRONICA SINICA, 2010, 38(2): 327-332.

[8]SUN L, ZHANG L, WANG Y. The research on tit-for-tat strategy in network evolution [C] //Control and Decision Conference, 2009. CCDC'09. Chinese:IEEE, 2009: 4190-4194.

[9]AL D A, MIZOUNI R, OTROK H, et al. Game theoretical analysis of collaborative social applications [C] //Collaborative Computing: Networking Applications and Worksharing, 2012 8th intemational Conference on. Pittsburgn: IEEE, 2012: 628-634.

[10] MACKENZIE A B,DASILVA L A.Game theory for wireless engineers[M].New York：Morgan and Claypool, 2006.[11] TOOTAGHAJ D Z, FARHAT F, PAKRAVAN M R, et al. Game-theoretic approach to mitigate packet dropping in wireless Ad-hoc networks [C] //Consumer Communications and Networking Conference(CCNC). New York: IEEE, 2011: 163-165.

[12] 张健. 基于博弈论的移动 Ad Hoc 网络节点合作策略研究[D]. 杭州：浙江工业大学, 2013.

ZHANG Jian. Research on Mobile Ad Hoc Network Node Cooperation Strategy Based on Game Theory[D]. Hangzhou: Zhejiang University of Technology, 2013.

[13] 孙玉星, 赵燕飞, 李娅, 等. 基于概率博弈的无线自组网信任推荐激励策略的研究[J]. 计算机科学, 2011, 38(4): 65-71.

SUN Yuxing, ZHAO Yanfei, LI Ya, et al. On Incentive Strategies for Trust Recommendations in Wireless Ad Hoc Networks with Probability Game[J]. Computer Science, 2011, 38(4): 65-71.

[14] 王博, 黄传河, 杨文忠, 等. Ad Hoc 网络中基于惩罚机制的激励合作转发模型[J]. 计算机研究与发展, 2011, 48(3): 398-406.

WANG Bo, HUANG Chuanhe, YANG Wenzhong, et al. An Incentive-Cooperative Forwarding Model Based on Punishment Mechanism in Wireless Ad Hoc Networks[J]. Journal of Computer Research and Development, 2011, 48(3): 398-406.

[15] 何世彪，吴乐华，胡中豫.无线网络中的博弈论[M].北

京：国防工业出版社，2016.

HE Shibiao, WU Lehua, HU Zhongyu. Game Theory for Wireless Networks[M]. Beijing: National Defense Industry Press, 2016.

[16] 陆音, 石进, 谢立. 基于重复博弈的无线自组网络协作增强模型[J]. 软件学报, 2008, 19(3): 755-768.

LU Yin, SHI Jin, XIE Li. Repeated-Game Modeling of Cooperation Enforcement in Wireless Ad Hoc Network[J]. Journal of Software, 2008, 19(3): 755-768.

[17] 聂志,刘静,甘小莺, 等. 移动Ad Hoc网络中机会路由转发策略的研究[J]. 重庆邮电大学学报：自然科学版,2010,(4):421-425，449.

NIE Zhi, LIU Jing, GAN Xiaoying, et al. A relay node selection technique for opportunistic routing in mobile Ad Hoc networks[J]. Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition,2010,04:421-425，449.

A fault-tolerant node cooperation strategy of ad hoc network based on repeated game

TAN Mian1,2, HE Shibiao1, SONG Bo1, YANG Gang1, ZHANG Hui1

(1.Chongqing Communication Institute, Chongqing 400035, P.R. China; 2.Logistical Engineering Institute, Chongqing 401331, P.R. China)

Abstract:According to possible selfish behaviors of wireless ad hoc network nodes showed during the process of data transforming and analyzing from static state based on game theory, this paper regards neighboring nodes as the researched object, and analyzes the fragility of Tit-for-Tat strategy in the repeated game. This paper proposes an improved Tit-for-Tat strategy, and proves incentive of improved strategy theoretically. This improved strategy can tolerate a certain degree of network failure, and can restart nodes into cooperation status again after failure happened. The simulation results show that the improved strategy has a better network fault tolerance compared with several other strategies, prompts node cooperation more effectively, gets higher node payoffs, reduces the interests of selfish nodes.

Keywords：wireless ad hoc network； perfect game theory；tit-for-tat；selfish nodes；network failure

DOI：10.3979/j.issn.1673-825X.2016.03.010

收稿日期：2015-04-28

修订日期：2016-06-07通讯作者：谭冕304365049@qq.com

基金项目：重庆市自然科学基金资助项目(cstc2014jcyjA40051)

Foundation Item：The Natural Science Foundation Project of CQ CSTC(cstc2014jcyjA40051)

中图分类号：TN92

文献标志码：A

文章编号：1673-825X(2016)03-0342-07

作者简介：

谭冕(1989-)，男，重庆人，博士研究生。主要研究方向无线自组网。E-mail:304365049@qq.com。

(编辑：张诚)