机会网络中基于信誉度惩罚的重复博弈模型

赵宇红 包凤莲,2 王静宇

1(内蒙古科技大学信息工程学院 内蒙古 包头 014010)2(包钢集团第三职工医院 内蒙古 包头 014010)

0 引 言

机会网络[1]是一种在源与目的节点间不存在完整通信链路，通过节点间的机会相遇来完成通信的网络。机会网络采用“存储—携带—转发”的路由模式，实现节点间间歇性连接通信，这显然需要节点间的相互协作。然而，节点受到自身资源、安全、隐私保护等方面的约束而表现出理性倾向，即节点追求收益的最大化。而某些节点一味追求保护与提升自身利益，拒绝或较少为其他节点提供服务，此时节点可称为自私节点，自私节点的行为将严重影响网络性能[2]。

目前，解决节点自私性问题的主要方法为激励机制。国内外常用的激励机制分为基于虚拟货币、基于声誉和基于博弈论这三类。然而，机会网络的移动性、拓扑的动态变化、间歇性连接的特点给以上激励机制带来很大挑战。在基于声誉的激励机制中，较难实现监测下一跳节点的转发行为。在基于虚拟货币的激励机制中，无法保证实时地与第三方认证进行交互和结算。在基于博弈论的激励机制中，现有的研究中给出很多策略来激励双方以促进节点间更好的合作，但是，其惩罚策略对节点并无区分性，激励效果不好。

针对上述问题，本文设计了一种基于信誉度惩罚(TTFT)博弈模型，用于机会网络的节点协作激励。在所构建的博弈模型中，博弈双方根据网络环境中节点的信誉度来动态调整惩罚周期来进行策略博弈，以期获得模型的收益最大化。

1 相关工作

文献[3]提出一种典型的基于声誉的激励机制。该模型通过Watchdog[4]监测工具完成节点行为的监测，通过声誉值的比较来激励节点协作。Watchdog用来监测、记录邻居节点的行为数据，并计算节点间的声誉值。通过将其与所设定的阈值比较来决定是否通信，该模型不但增加了硬件需求，同时也没有考虑节点共谋攻击的问题。文献[5]利用博弈论分析移动自组织网络中激励节点间的协作，该首先在2个节点间建立数据转发博弈，对模型提出精炼纳什均衡，进一步求出最优数据转发策略，提出了依据信誉度的协作激励策略。文献[6]提出一种解决自私节点的策略，通过非合作理论来完成对邻居节点的自私行为研究。在文献[7]中，综述了因节点的自私行为给无线网络带来的问题，特别是利用博弈论对节点的非合作行为进行了分析和研究。文献[8]对节点的不协作行为设计惩罚机制，进而抵消了节点从不协作行为中获取的收益，该模型对节点的行为主要采用本地监测机制，但由于机会网络的间歇移动特性导致该模型的激励效果不好。文献[9]提出一种基于惩罚机制的重复博弈模型，强调信任在P2P网络中的重要性，通过信任值的大小来设置惩罚周期，但是该模型没有对信任值的获取给出说明。文献[10]提出了一种基于惩罚策略的博弈模型，利用一个节点为网络中其他节点提供转发服务时获取的收益大于节点采取不协作策略时的收益，求得激励一致性条件。但该模型的惩罚策略没有进一步对节点的不协作行为给予处理，即对节点的不协作行为没有给予适度的惩罚。

2 基于信誉度惩罚策略的博弈模型

针对节点自私性的问题，目前所提出的基于惩罚策略的博弈论激励机制没有考虑到积累的历史信息对节点将来行为的影响。本文在惩罚策略中引入节点的信誉度，通过节点间的信誉度来定义节点的惩罚周期，区分不同信誉累积节点的不同惩罚程度。本文首先给出博弈的假设条件：

(1) 理性节点：机会网络中的节点以个体利益最大化为目标。

(2) 机会网络G=(V,E)由理性节点构成，G为连通图，V={i,j,k,…}为节点集合，E为链路集合，节点间的通信链路为双向。

(3) 本文讨论的是节点消息转发时自私性问题，消息丢失的主要原因为节点间的“不协作”行为。

(4) 机会网络运行的时间由一系列离散的时隙t构成，一个时隙为一个博弈阶段。在任一时隙内，单阶段博弈可能随时产生，并且单一时隙长度保证每个消息可传送到目的节点。

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

2.1 基于信誉度的惩罚策略

有效地选择转发节点对于保障机会网络这样具备移动性、间歇连接性的网络的传输成功率及改善传输延迟是非常重要的，节点的连接能力、合作表现、所完成的连接量这些信息作为转发节点的选择依据是客观且准确的，本节中定义节点的信誉度来量化节点的这些历史行为，并提出基于信誉度的惩罚策略来解决节点的自私性问题。为解决在机会网络中节点间存在的自私性问题，在本节中定义信誉度的相关概念和基于信誉度的惩罚策略。

2.1.1信誉度的相关概念

本文采用2-hop Ack[11]机制来监控节点的转发行为。基于以上监测到的行为数据，提出节点信誉度来度量节点的历史行为，并进一步定义了交互的连通度和满意度来量化这些行为，节点的信誉度通过综合这两个分量来获得。

信誉度是描述节点历史行为的信息积累。信誉度用C来表示，C∈[0,1]。

(1)

(2)

信誉度Ci,j表示节点i对j的信誉评价，其计算方法如下：

(3)

式中：α∈[0,1]。α是衡量连通度和满意度的权重因子，其值的选取对信誉度的大小有很重要的影响，动态调节了连通能力与协作表现在信誉度中的比重，本文提出一种基于自适应滤波的方法[12]来确定α取值。其设计原则为：当前阶段节点的信誉度应尽可能接近在最后的信誉度更新阶段所得到的平均信誉度，与针对所有通信范围内的节点信誉值来实现，这是体现动态系统的最新演化效应，其计算方法如下：

(4)

(5)

当MSE′(α)=0时，可以得到α的解：

(6)

通过式(6)求得α的最佳值，从而可获得节点信誉度。由于节点的信誉度源自对节点的历史行为的量化，是对节点的过去行为的一种体现。因此，当节点采取“不协作”的方式时，根据以往信誉度的不同对其进行不同程度的惩罚，惩罚策略一方面可以激励节点为取得未来收益而协作，也会因为历史行为表现所引起的不同惩罚力度而激励节点在未来为积累更高的信誉而采取更积极且高质量的协作。

2.1.2惩罚策略

信誉度体现节点历史行为，当节点采取“不协作”行为时，其邻居节点会根据信誉度的不同采取不同程度“处罚”，该“处罚”是通过惩罚周期来体现的。 惩罚周期T的计算方法如下：

T=f(C)+1

(7)

基于信誉度的惩罚策略(TTFT)，其实施过程可描述如下：

(1) 在节点(i,j)可监测条件下，节点在第一个博弈阶段(t=1)选择策略为(转发，转发)。

(2) 在t>1博弈阶段，如果节点j在t-1博弈阶段选择不转发，此时节点i计算节点j的信誉度，基于惩罚度转换函数计算节点惩罚周期T，在t阶段后，j受到邻居节点的惩罚。

(3) 在惩罚周期T内，邻居节点拒绝为j转发消息，但是节点j必须无偿为邻居节点转发消息，直至惩罚周期结束；在惩罚期内，若节点j不接受惩罚并且继续不转发消息，则将其惩罚周期设置为无限。

(4) 在惩罚周期结束后，节点j与网络中其他节点继续正常转发数据。

2.2 无限重复报文转发博弈

单阶段博弈过程可表示为一个三元组，Π={P,S,u}，其中博弈参与人集合为P={i,j}，i与j为相遇节点；节点的策略空间为S={Si,Sj}，其策略为(转发(S)，不转发(US))两种；节点的效用函数为u={ui,uj}，并且节点的转发收益大于损耗收益。

根据博弈论的画线法[13]论证，该单阶段博弈模型与“囚徒困境”相似，此博弈模型的纳什均衡为(不转发，不转发)，但这一稳定状态显然无法支持机会网络通信。由于机会网络中节点间的通信是一种长期且动态变化的过程，单阶段博弈显然不符合节点的长期活跃需求。所以，基于网络的时序演化可将单阶段博弈扩展为重复博弈，为强化节点的未来收益，在重复博弈模型引入贴现因子δ，δ体现了节点对未来收益的期望。

具体博弈模型结构如下。

无限重复博弈：设Π为单阶段博弈，机会网络中节点间长期报文转发的交互过程是阶段博弈Π的不断重复，并且在每次阶段博弈开始前，博弈参与人在Π(∞,δ)中的收益等于各阶段收益现值之和Ui，其计算如下：

(8)

根据式(8)得到的收益矩阵如表1所示。

表1 无限重复博弈模型收益矩阵

下面，我们来计算并分析节点采取不同策略时的收益。为了便于分析节点收益的大小，假设节点在每个时隙t内发送的消息数量相同。根据上述的定义可知，若节点i在当前博弈阶段选择了“不转发”策略，那么其预期收益有如下两种情况：

(9)

(10)

(11)

为激励理性节点采取“合作”策略，需要确保其选择“转发”策略时所得收益要大于选择“不转发”策略时的收益，所以必须同时满足：

(12)

当节点采用基于信誉度的惩罚策略时，式(12)可求得重复博弈的纳什均衡为(转发,转发)。由于传统重复博弈无法动态呈现其演化过程。因此，下一节将使用演化博弈理论来分析网络中节点动态演化的过程，阐述节点由不转发策略向转发策略转变的过程，并进一步分析该模型的稳定性。

3 基于演化博弈论的节点协作分析

3.1 构建并求解演化博弈模型

由于机会网络中的节点同时发送和接收报文。假设整个网络中节点分为两类：转发和不转发节点。节点双方的策略集合均为(转发(TTFT)，不转发(NS))。每个节点通过其他节点的选择策略来调整自身策略以便获取最大收益。在表示节点收益时，将TTFT和NS策略分别简写为TT和N，收益矩阵如表 2 所示。

表2 演化博弈模型的收益矩阵

根据收益的贴现计算方法计算收益为式(13)-式(15)。

(13)

(14)

(15)

假设网络中转发行为节点比例为ω，则不转发行为节点比例为1-ω。期望收益矩阵可以计算：

(1) 转发节点的期望收益为：

φs=ωU(TT,TT)+(1-ω)U(TT,N))

(2) 不转发节点的期望收益为：

φN=ωU(N,TT)+(1-ω)U(TT,TT)

(3) 根据(1)和(2)节点的期望收益,可求得整体网络的平均收益为：

ω(1-ω)U(TT,N)+ω(1-ω)U(N,TT)

(16)

根据式(16)可构造协作节点的复制动态方程：

(17)

式(17)阐述演化博弈模型的动态过程，令F(ω)=0，当U(N,TT)≠0时方程的解为：ω1=0，ω2=1；当U(N,TT)=0时，对于任意ω∈[0,1]都为方程的解。

3.2 基于信誉度惩罚策略的稳定性分析

虽然ω1=0、ω2=1都是F(ω)=0的解，但根据微分方程稳定性原理可知：只有F′(ω)<0得到的解才具有稳定性。下面分别对纳什均衡解的稳定性进行分析。

1) 在F(ω)=0时，任意ω∈[0,1]为其纳什均衡的解，并且恒有F′(ω)=0。因此，ω∈[0,1]都是动态稳定均衡解，此时复制动态方程的动态演化相位图如图1所示。

图1 ω∈[0,1]时的动态演化相位图

2) 在F(ω)=0，当U(N,TT)≠0时，ω1=0、ω2=1为纳什均衡解，当F′(ω)=(1-2ω)U(N,TT)可求得：

图2 ω1=0时动态演化相位图

(2) 当U(N,TT)>0，可知F′(ω1=0)>0，F′(ω2=1)<0，因此，ω2=1为唯一的演化稳定策略。

图3 ω2=1时动态演化相位图

综上所述，在重复博弈过程中，节点的自私行为将逐渐转化为协作行为。由演化博弈的稳定性可知，即使网络中自私节点比例较多，经过TTFT惩罚策略的多次博弈后，其自私节点将演化成合作节点，促进节点间的协作，达到博弈模型的纳什均衡，从而使网络系统达到稳定状态。

4 仿真实验

为验证本文所提出的TTFT模型的有效性，采用ONE[14]模拟器来仿真实验。模拟实验的数据集为Infocom2006；节点间监测通信范围为10 m；移动速度为0.5～2.5 m/s；数据的大小为1 024 KB；节点缓存大小均为15 MB。实验中为模拟无限博弈模型，在有限次博弈中未指定结束时间，为保障结果的可重现及稳定性，实验数据均进行了50组，取平均结果。

首先，利用2-hop Ack算法确定节点是否具有自私性以及自私节点所占比例。接下来，设定该实验采用的路由协议Epidemic[15]，实验分别分析了贴现因子δ和惩罚周期T对协作性的影响。最后，在常用路由协议中，将本文提出模型与现有常用博弈模型对比，并给出了仿真结果。

(1) 节点的贴现因子δ对协作行为的影响。合作收益及博弈双方的贴现因子是影响协作机制演化的关键因素。图4显示了传输成功率和平均延迟随贴现因子δ变化的情况。

(a) 传输成功率的对比

(b) 平均延迟的对比图4 贴现因子对网络性能的影响

(2) 惩罚周期T对协作行为的影响。图5是在δ=1、不同比例自私节点情况下，节点间消息传输的成功率。在惩罚周期T=4时，节点间的传输成功率最高，激励效果最好。即在一定的惩罚范围内，增加T将有利于提高网络转发率。但若惩罚周期T过长，即其周期长度超过实验中节点间相遇次数的最大值，会导致网络整体性能下降。因此，网络传输中还需要根据自身信誉度来适应具体的T值。

图5 不同惩罚周期T下网络节点传输成功率对比

(3) 惩罚机制对协作行为的影响。机会网络中，根据节点间不同的转发策略，目前常用的路由算法可分为基于冗余的算法和基于效用的算法，其代表分别为Epidemic和Prophet[16]。Epidemic算法中每个节点将需传送的消息保存在缓存中，当两节点相遇的时候交换彼此的缓存内容。Prophet算法通过节点间相遇的历史信息来计算与目的节点相遇概率，选择概率高的节点为下一跳转发的节点。为验证惩罚策略对协作激励的影响以及在不同路由协议中的适用性，节点在无任何惩罚策略、冷酷策略[13](Grim Strategy，GS)、针锋相对策略[17](Tit For Tat strategy，TFT)和本文的信誉度惩罚策略TTFT进行了传输仿真实验。图6显示在不同自私节点比例和不同惩罚策略下节点传输成功率的对比。

(a) Epidemic路由协议与不同惩罚策略

(b) Prophet路由协议与不同惩罚策略图6 传输成功率对比

Epidemic路由算法是将消息传递给与其相遇的所有节点，故该算法的成功传输率较高。但随着自私节点比例的增多，节点中“不转发”行为增加，所以其成功传输率也减少。Prophet算法是基于概率的转发，由于自私节点的不合作行为，致其传输概率较低，因此随着自私节点的增多，其传输成功率将减少。

当自私节点所占比例增大时，节点间的协作次数越来越少，表现为传输成功率在下降，但是不使用任何惩罚策略情况下，成功率最低。在网络中使用GS策略后，节点首次选择是合作的，故当自私节点数量较少时，传输成功率较高。但当网络中的节点选择不转发策略时，则会导致以后永不转发节点。故在自私节点比例增多时，传输成功率明显下降。在使用TFT后由于该机制中引入惩罚机制，理性节点为增多节点未来的收益，会考虑其自私行为带来的不利影响，故其传输成功率相较前者有所提高。在使用本文提出的TTFT惩罚机制后，随着自私节点所占比例的增加，相对GS、TFI策略，TTFT提高传输成功率的效果更好。这是由于TTFT模型的惩罚周期是根据影响节点收益多少的信誉度来设置，具有区分性和动态性，所以其呈现的协作效果更好。

5 结 语

机会网络中的节点因自身的处理能力低、存储空间有限和电池容量小等原因，节点表现出自私性。因此，激励自私节点转发消息成为提高节点传输成功率和降低网络延迟的关键问题。本文定义了信誉度对节点历史行为进行度量，并提出基于信誉度的惩罚策略的重复博弈模型。一方面利用不同信誉度实施不同程度的惩罚，另一方面，利用节点对未来收益的期望，而激励了节点积极参与协作转发。通过演化博弈分析证明了基于信誉度惩罚策略TTFT的演化稳定性，仿真表明，该模型可以激励节点协作，提高网络传输性能。