一种机会网络节点重复博弈模型

宋蔓蔓，张振宇，杨文忠，张珍

新疆大学信息科学与工程学院，乌鲁木齐 830046

一种机会网络节点重复博弈模型

宋蔓蔓，张振宇，杨文忠，张珍

新疆大学信息科学与工程学院，乌鲁木齐 830046

在资源受限的机会网络中，节点在转发过程中所表现出的自私行为将严重影响网络性能。针对这一问题，建立基于认错机制的“礼尚往来”策略的节点重复博弈模型。节点考虑到将来的利益，迫于对惩罚的恐惧而参与转发。通过该策略，节点协作可以使网络性能达到最优。仿真结果表明，节点间的相互协作增强，在自私节点较多时也能保证较好的网络性能。

机会网络；节点协作；认错机制；重复博弈

1 概述

机会网络[1]是一种不需要源节点和目的节点之间存在完整链路，利用节点移动带来的相遇机会实现通信的自组织网络。由于节点的移动性，在机会网络中很难维持端到端的连通，消息从源节点传递到目的节点，通常需要中间节点的存储、携带和转发才能完成消息的传送。

由于转发消息会消耗节点有限的资源，如缓存、能量等，节点为了维护自己的资源拒绝与其他节点协作。文献[2]把机会网络中只享受信息资源服务而不为系统做贡献的节点称为自私节点。节点的自私行为将导致网络性能严重下降[2-4]。因此促进节点间的协作成为机会网络的一个关键问题。

目前，促进节点协作的方法主要分为基于信誉、基于声誉和博弈论三类方法。基于信誉的方法[5]基本思想是：节点为另一个节点转发消息将获取一定的信誉，这些信誉是从发送方（或目的地）扣除。这个方法实现时需要在每个节点上添加防篡改硬件，从而可以正确地增加或扣除一个节点的信誉。基于声誉的方法[6]记录节点过去的行为，帮助节点区分和选择有较高声誉的、从而愿意帮助其他节点转发的节点，这样可以得到较好的网络性能。现有检测机制的不准确性是声誉系统应用的主要障碍。

本文在机会网络中存在自私节点的情况下，建立了基于认错机制的“礼尚往来”策略（Adm it-Tit-for-Tat，ATFT）的重复博弈模型，节点会相互协作，可以使网络性能达到最优。

2 基于ATFT策略的重复博弈模型

重复博弈是指阶段博弈重复进行（有限次或无限次）构成的博弈过程，是一种特殊的博弈[7]。由于其他参与人过去行动的历史是可以观测的，因此在重复博弈中，每个参与人可以使自己在每个阶段的策略选择依赖于其他参与人过去的行为。

由于网络节点当前消息转发策略行为选择会影响其他节点的策略选择，在重复博弈理论的基础上，通过将网络节点之间交互抽象成重复的多阶段动态博弈，并且使用纳什均衡这一概念对利益冲突环境中节点理性行为所导致的稳定局势进行预测。当节点根据其他节点行为始终选择对自己最有利的协作策略时，便构成了网络中的一个纳什均衡。这一整体网络状态的意义在于激励一致性：此时，任何节点均不会产生自私企图，因为这将降低节点的整体收益。重复博弈的分析视角为我们从节点自身角度来引入相应的协作促进机制，同时考察耐心因素对其理性响应的影响提供了便利。

ATFT策略的基本思想是节点第一次总是协作，之后节点i根据对方的上次策略进行决策。即如果对方选择不协作，节点i也选择不协作来进行惩罚。在经过若干次惩罚之后，对方意识到必须主动转发来向i认错，否则惩罚将无限执行下去，对方一旦认错，i必须原谅。

2.1 阶段博弈

为分析方便，本文做出如下假设：

（1）网络中存在N个节点，N={1，2，…，n}。

（2）所有消息的大小相同，发送、转发单个消息时每个中继节点的花费相同。

（3）整个机会网络运行时间由一系列离散的时隙t构成(t1，t2，…，tn)，并且单一时隙长度足以保证每个消息均能抵达目的节点。

（4）由于本文研究的是消息转发时节点之间的相互协作，假设消息丢失的主要原因是网络中节点的不合作行为。

（5）每次博弈都遵循相同的规则和过程。

假设节点i加入到消息传输中，节点的一个消息被成功转发的收益为Bi，转发一个消息的花费为Coi。根据ATFT策略，综合考虑对手上一次的策略以及网络花费，决定节点i下一阶段的策略，得出节点i的效用函数为：

其中-i表示节点i的对手；S-i={C-i，NC-i}表示节点-i的策略空间，其中C表示合作，NC表示拒绝合作。节点i的策略选择可表示为f(S-i)；b-i表示节点i接收到传输请求的概率；ai表示节点i转发消息的概率。

由于资源有限，节点为了减少资源消耗会拒绝转发消息。如果网络中所有的节点均选择这样的策略，网络中消息的传输成功率将会是0，由式（1）可知此时节点效用值最大，所有的节点达到纳什均衡状态，但是网络中不存在任何协作转发。这一稳定状态显然并不符合预期。

2.2 重复博弈模型

由2.1可知，如果节点间的交互只进行一次，博弈的结局与囚徒困境相似，所有节点选择不协作策略形成了单阶段博弈唯一的纳什均衡。但是在节点的生命周期中很少只有一次博弈过程，它可以在不同的时刻与不同的对手加入不同的博弈过程。在网络中一个节点在一次博弈中作为消息携带者，但是下一刻就可能在另一个博弈中充当消息接收者。因此加强节点间的相互协作需要建立一个重复博弈模型[8]。

假设重复博弈过程已经执行了T次，节点知道过去T-1次对手的行为。通过用贴现因子δ∈（0，1）来描述效用函数的话，节点的总效用值可表示为：

Ui（t）表示节点i在时刻t的效用值。δ表示节点对未来利益的重视程度，δ越大，节点越注重长远利益，δ越小，节点越注重眼前利益。当T=∞时，以上博弈过程可视为无限次重复博弈过程[9]，记作G(∞)，则节点i的平均效用值为：

2.3 ATFT策略

假设自私节点的自私周期是y，则惩罚周期也为y，每个节点维护一个集合，保存相互交互过的节点i及交互节点拒绝与此节点协作的次数Nui。基本思想是：如果节点-i拒绝帮助节点i转发消息，节点i将(-i，Nu-i)中Nu-i的值加1；一旦节点-i帮助i转发，i将(-i，Nu-i)中Nu-i的值清零。以节点i向-i请求转发为例，ATFT策略的具体步骤：

（1）如果节点-i是自私节点，转向步骤（2），若不是，转向步骤（6）。

（2）节点-i查看自己是否在集合中存储了(i，Nui)，若未存储（说明两个节点首次交互），由于节点首次总是协作，-i帮助i转发，并在集合中添加(i，0)，节点i在集合中添加(-i，0)，转向（8），否则转向（3）。

（3）-i查看集合中的Nui是否小于y，若小于转向（5）。

（4）-i意识到由于自身的自私行为，节点i已经对自己做出y次惩罚，因此主动帮助转发来认错。节点i在收到-i的认错之后，必须原谅，因此将(-i，Nu-i)中Nu-i清零。

（5）节点-i为了自身利益的最大化，仍拒绝转发，i将(-i，Nu-i)中Nu-i值增加1。

（6）若节点-i不是自私节点，查看是否存储了(i，Nui)，若未存储，-i帮助i转发，节点i在集合中添加(-i，0)，否则转向（7）。

（7）-i查看集合中保存的Nui是否为零，若为零，帮节点i转发，i(-i，Nu-i)中Nu-i清零；若不为零，则拒绝为节点i提供转发服务，i将(-i，Nu-i)中Nu-i加1。

图1 节点对未来利益重视程度对网络性能的影响(y=2)

（8）交互结束。

在博弈过程中可以发现，一旦节点-i选择自私，那么它将采取持续自私的策略。这是因为如果一次自私能够让节点-i额外获益，那么在惩罚结束之后，节点-i会面临相同的策略选择。采用ATFT策略时，网络中节点的效用函数为：

若博弈过程中节点i协作的效用大于自私行为的效用，它将毫不犹豫地选择协作，并在下一次博弈时采取持续协作的策略。也就是说，为了打消节点i采取自私行为的念头，必须保证其持续协作时的收益不小于重复自私行为的收益，这一条件可用式（5）表示：

由于节点都是理性的，只有式（5）不成立时才会自私。存在δ满足上式，使节点避免自私行为，协作是节点的最优策略，而且节点没有足够的动机偏离这一决策。因此式（5）即为节点采取ATFT策略时最佳纳什均衡的条件。

3 仿真及分析

本文采用仿真工具The ONE 1.4.0[10]分析本文所建立模型的有效性。采用真实城市街区图，200个节点随机分布在4 500 m×3 400 m的区域内，移动速度为1～3 m/s；节点间的通信范围半径为10 m；节点缓存大小均为10 MB；消息的大小为500 KB。

首先通过实验分析了节点对未来利益重视程度对协作效果的影响。然后分析了惩罚周期y对协作性的影响。最后与已有的博弈模型对比，并给出了仿真结果。

3.1 节点对未来利益重视程度对协作性的影响

图1给出了当惩罚周期y=2时，在机会网络中存在不同比例的自私节点时在不同贴现因子取值下，对Epidem ic算法传输成功率和平均延迟的影响。图1（a）中传输成功率随δ增加而明显提高，图1（b）中网络平均延迟随δ增加而降低。随着节点对未来利益重视程度的增长，自私节点会主动选择认错，因此整个网络的协作性随自私节点对未来利益的重视而得到了改善，进而传输成功率会随之增加，网络平均延迟相应减少。

3.2 惩罚周期对协作性的影响

图2表示在贴现因子σ=1时，在机会网络中存在不同比例的自私节点时在不同惩罚周期取值下，对Epidem ic算法传输成功率的影响。在一定范围内，增加y将有助于提高网络协作程度。但是如果y过大，即惩罚周期过长，超过了本实验仿真过程中节点的最大相遇次数，在惩罚周期内自私节点拒不认错，致使网络性能下降。所以y值的选取需要根据网络特定情况而定。

图2 参数y对传输成功率的影响

3.3 自私节点比例对协作性的影响

分别模拟Epidem ic[11]、PROPHET[12]和Spray and Wait[13]三种算法在使用ATFT策略前后自私节点占节点总数的10%，20%，…，80%时对网络中传输成功率的影响，并且与这三种算法使用冷酷策略（Grim Strategy，GS）[14]和GTFT[15]时的传输成功率进行对比。仿真结果如图3所示。

图3 传输成功率

Epidem ic算法复制消息并转交给所遇到的所有节点，中间节点若不存在自私节点，负责转发的中继节点能及时把消息转交给下一个中继节点，最大程度上传递消息，所以消息递交率比较高。自私节点比例增加时，中继节点丢弃消息而不是尽最大努力转发，因此成功率随之降低。PROPHET算法是基于概率策略的，由于自私节点声称自己不会遇到其他节点，即传输概率为0，节点转发消息时根本不会选择此类节点，因此随着网络中自私节点数目的增多，可用节点的数目随之减少，消息传输成功率随之降低。网络中自私节点数目较少时，Spray and Wait算法传输成功率最高，但随着自私节点数目的增加，成功率明显降低。这是由于Spray阶段，源节点中的部分消息被扩散到邻居节点，若Wait阶段并未发现目的节点，那么中继节点通过直接传输的方式把消息传送到目的节点，因此随着自私节点数目的增多，Spray阶段消息被抛弃的几率也随之增加，成功率随之降低。

使用GS策略之后，由于自私节点首次是合作的，因此当自私节点较少时，传输成功率要高于上述情况；但是由于网络中任何一个节点的一次不协作将会导致永远的不协作，在自私节点比例增加时，传输成功率明显下降。

使用ATFT策略之后，由于引入了认错机制，自私节点出于对惩罚的恐惧，每次收到传输请求时都会考虑自私行为带来的后果，因此在自私节点逐渐增多的情况下Epidem ic、PROPHET和Spray and Wait三个算法均能保持平稳的传输成功率，优于未使用ATFT策略的情况。GTFT仅考虑了历史收益对节点决策的影响，没有考虑其将来获利的期望。但是使用ATFT策略节点考虑了未来利益，导致节点在博弈过程中进行自我约束，并且提高了传输成功率。

4 结束语

本文建立基于认错机制的“礼尚往来”策略的节点重复博弈模型。利用节点对将来利益的重视来胁迫它参与转发协作。仿真结果表明，该模型使节点间的相互协作大大增强，网络性能随之提高。

[1]Pelusi L，Passarella A，Conti M.Opportunistic networking：data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine，2006，44（11）：134-141.

[2]Chiou C，Chen L.Poster abstract：an evaluation study of routing reliability in opportunistic networks[C]//Proceedings of the 9th ACM International Symposium on Mobile Ad hoc Networking and Computing.Hong Kong：ACM，2008：455-456.

[3]Panagakis A，Vaiosand A，Stavrakakis L.On the effects of cooperation in DTNs[C]//Proceedings of COMSWARE，2007：1-6.

[4]Marti S，Giuli T，Lai K.Mitigating routing misbehavior in mobile Ad hoc networks[C]//Proceedings of ACM MOBICOM’00.New York，USA：ACM Press，2000.

[5]Zhu Haojin，Lin Xiaodong，Lu Rongxing，et al.SMART：A secure multilayer credit-based incentive scheme for delay-tolerant networks[J].IEEE Trans on Vehicular Technology，2009，58（8）：4628-4639.

[6]Zhang Sihai，Qiu Hongyang，Liu Yuan，et al.Evolutionary reputation model for node selfishness resistance in opportunistic networks[C]//Concurrency and Computation：Practice and Experience，Forthcoming，2011.

[7]Osborne M J，Rubinstein A.A course in game theory[M]. Cambridge：M IT Press，1994.

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

[9]Ratliff J.Sampler F T.Great introductory notes to the Folk Theorem[N/OL]（1996）.http：//www.virtualperfeetion. com/gametheory5.3.FolkTheorem Sampler.1.0.pdf.

[10]TKK/COMNET.Project page of the ONE simulator[EB/OL]. http：//www.netlab.tkk.fi/tutkimus/dtn/theone，2008.

[11]Apoorva J，Konstantinos P.Performance analysis of epidemic routing under contention[C]//Proc of the 2006 International Conference on Wireless Communications and Mobile Computing.[S.l.]：ACM Press，2006.

[12]Lindgren A，Doria A，Schelen O.Probabilistic routing in intermittently connected networks[J].Lecture Notes in Computer Science，2004，3126：239-254.

[13]Spyropoulos P K，Raghavendra C S.Spray and wait：al efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of ACM SIGCOMM Workshop on Delay-tolerant Networking，Philadelphia，New York，2005：252-259.

[14]张维迎.博弈论与信息经济学[M].上海：上海人民出版社，1996：31-81.

[15]Srinivasan V，Nuggehalli P.Cooperation in wireless ad hoc networks[C]//Proc of the IEEE INFOCOM 2003. Washington：IEEE Computer Society，2003：808-817.

SONG Manman,ZHANG Zhenyu,YANG Wenzhong,ZHANG Zhen

College of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

In opportunistic networks with limited resources,the performance of network is seriously affected by selfish behavior of the nodes during the packet forwarding.To solve this problem,the paper establishes a repeated-game model of node cooperation based on a admit mechanism of“Tit-For-Tat”strategy.The nodes consider the long-term interests and participate in forwarding forced by the fear of punishment.By using the strategy,cooperation of nodes in the network can make the network performance to achieve optimal.The simulation results show that the mutual cooperation of nodes is enhanced and the performance of the network can be guaranteed when more selfish nodes exist in network.

opportunistic networks;node cooperation;admit mechanism;repeated game

A

TP393

10.3778/j.issn.1002-8331.1209-0185

SONG Manman,ZHANG Zhenyu,YANG Wenzhong,et al.Repeated-gam e model of node cooperation in opportunistic networks.Computer Engineering and Applications,2014,50（16）：86-89.

国家自然科学基金（No.61262089）；新疆大学博士科研启动基金资助项目（No.BS110127）。

宋蔓蔓（1987—），女，主研方向：机会网络；张振宇（1964—），男，副教授，主研方向：对等网络，机会网络；杨文忠（1971—），男，副教授，主研方向：无线网络组播路由；张珍（1988—），女，主研方向：机会网络。E-mail：songman0534@126.com

2012-09-18

2012-11-14

1002-8331（2014）16-0086-04