机会网络自私节点的Bertrand博弈与激励机制研究

吴 青，曾 锋

中南大学 计算机学院，长沙 410000

1 引言

随着手机终端和无线技术的发展，机会网络[1]日益成为了大家关注的热点。机会网络是由无线自组织网络和延迟容忍网络[2]演化而来的新型网络。在传统的无线网络中，消息传送的源节点和目的节点之间至少需要有一条完整的通信链路存在。然而，在真实的网络环境中，由于随时可能发生网络中断，不能保证源节点和目的节点之间存在持久的通信链路。机会网络与传统网络不同的是机会网络中源节点和目的节点之间不需要一条完整的通信链路，节点之间转发消息通常是基于节点移动产生的机会性的接触。机会网络采用一种“存储-携带-转发”的路由方式来进行数据交换。也就是说，如果节点没有找到合适的中继节点，消息将会存储在节点的内存中，节点会携带着消息移动，直到遇到合适的中继节点，消息才会被转发。

机会网络中数据传输成功主要基于节点之间的协作，因此，数据传输的前提是路由中的中间节点都愿意转发数据包。但是在许多应用中，作为机会网络节点的移动设备，由人携带，其处理能力、存储空间、电池电量和等资源都是有限制的，节点很可能倾向于选择自私行为。它们可能只想接收感兴趣的消息，拒绝接收对它们没有用但对其他节点有益的消息。如果节点都是理性的，节点将会显示出自私性，为节省自己的资源而不会为其他节点转发消息。文献[3]的研究工作表明节点的自私行为严重损害了机会网络中数据传输的性能。但是，节点是理性的，只要有利可图即可参与合作转发消息，因此可通过相关利益激励节点从而提高网络的整体性能。

目前，机会网络中的激励机制主要分三类，分别是针锋相对（TFT）激励机制[4]、声誉激励机制[5-6]和虚拟货币激励机制[7]。TFT机制的主要思想是利用博弈论根据互惠原则构建模型，节点转发给其他节点的数据量与从其他节点接收到的数据量相同。在实际网络环境中，由于业务不对称，很难在TFT 激励机制中实现良好的性能。在声誉激励机制中，系统记录每个节点的历史协作行为，并且给每个节点提供声誉值以评估它是否是自私的。此外，声誉值动态变化，参与消息转发的节点会获得声誉值的增加，声誉激励机制会选择具有较高声誉值的节点来转发消息。然而，声誉机制无法区分高信任度节点，导致对节点的激励能力不足。在货币激励机制中，源节点必须向转发消息的中间节点支付虚拟货币，需要第三方管理，并且节点没有差别定价方案。

如上所述，这三种类型的激励机制在激励节点参与消息转发方面均存在不足之处。本文运用博弈论和虚拟货币分析节点之间的交互，提出一种基于Bertrand博弈的激励机制。通过定义博弈参与者的效用函数，找到各方最佳策略，分析定价策略找到唯一的纳什均衡，这个纳什均衡点会让每个节点都获得最大效用。与已有研究工作不同，本文对参与节点实行两阶段的激励。由于节点中的消息传输包括两个阶段，即从其他节点接收消息的阶段和把消息转发给其他节点的阶段，因此应鼓励每个节点不仅要从源节点接收消息，还要将消息转发给其他节点。本文的工作提升了节点参与消息转发的积极性，提高了数据传输的性能，且避免了只接收消息不转发消息的丢包行为。

2 相关工作

许多学者对机会路由进行了广泛的研究，提出了各种类型的消息转发方法和路由算法，目的是提高数据传输速率，同时降低网络开销。

经典的Epidemic[8]路由算法泛洪的向身边的每一个节点传递消息，也就是说源节点只要遇到下一跳节点就会把消息传出去，不考虑网络开销。理论上，Epidemic路由算法有很高的传递率，但是带来的网络开销也很高。经典的Direct[9]路由要求源节点把数据存储到内存，遇到目的节点后才传递给目的节点，也就是说遇到任何下一跳节点都不转发，直到遇到目的节点，才把消息转发给目的节点。Direct路由算法虽然有很低的网络开销，但是传递率也很低。基于Epidemic和Direct路由算法，出现了许多有效的路由算法[10-12]，这些算法在消息传递成功率和网络开销之间进行权衡，在某些情况下具有良好的性能。然而这些传统的路由算法都基于一个完美的假设，即网络中所有的节点都会主动转发消息给其他节点，不会拒绝转发消息。但在真实的网络环境中，作为机会网络节点的移动设备由人携带，由于存储空间、电池电量和其他资源的约束，节点往往是自私的。在Epidemic 路由中，如果所有节点都是自私的，则Epidemic路由方案会变成Direct路由。

机会网络中节点自私问题最近引起了许多研究者的关注。在文献[13]中，探索了节点合作对经典路由算法的影响，如Epidemic、Two-Hop，Binary Spray and Wait[14]等，提出了一种简单的激励机制，定义了协作度来提高三种路由算法的有效性，发现节点之间的协作度可以影响网络的传输率。在文献[15]中，提出了一种使用公平定价机制来激励节点的拍卖激励机制，将定价过程建模为拍卖博弈。该博弈能够实现贝叶斯纳什均衡，其中每个中间节点的利润可以最大化。在文献[16]中，提出一种基于博弈论的多功能激励机制，叫Multicent，该机制不仅激励节点参与消息传递，而且鼓励节点遵循既定的规则实现期望的行为目标。在文献[17]中，从博弈论的角度提出了一种激励机制，它将个体自私和社会自私结合起来，提高机会网络的性能。这个机制将两个节点之间的消息传输映射为Rubnistein-Stahl 三次讨价还价博弈，利用虚拟货币构建合适的价格函数，考虑节点资源和节点之间的社会关系进行数据传输。该机制主要的缺点是带来数据传输能耗高，延迟大。在文献[18]中，提出了基于Stackelberge 博弈模型机制（SEIR），给予中继节点最好的奖励以消除中继节点的自私行为。为了避免节点的虚拟报价，提出了一种讨价还价博弈，但这会导致一些资源的损失，从而导致高延迟和高消耗。在文献[19]中，提出了一种基于博弈的激励策略（GIS），该策略利用基于二人交易的三次议价模型，允许源节点根据博弈得出的最优价格直接支付中间节点，不需要第三方。在文献[20]中，基于双方拍卖提出一种叫CANCMDA 的机制。该机制解决网络阻塞和节点自私的问题，双方拍卖交易过程是一个贝叶斯均衡。但是，该机制只适用于单拷贝路由。在文献[21]中，提出了一种叫NISOVCM 机制，设计了一种透支虚拟货币机制，以节点消息转发能力作为担保，解决虚拟货币不足和虚假报价问题。当消息交易无法完成一次完成时，交易双方将根据资源状态和财富状况进行第二次讨价还价来抑制双方之间的虚假报价。但是，该机制不能有效改善网络的消息传输成功率。在文献[22]中，基于声誉机制建立了动态模型，为社交网络服务中的信息共享明确了激励机制。在文献[23]中，设置了一个奖励机制，这个奖励是设置预期交付成本的最小数量，奖励仅给予作为第一个将消息传递到目的地的中继节点。

上述激励机制一定程度激励了节点参与消息传递。然而，对一个节点来说，消息传输有两个阶段，首先从发送节点（源节点）处接收消息，然后携带着消息在移动中机会性地将消息转发给其他节点。如果某些节点只接收消息，而拒绝转发消息，则可能导致消息丢失。由于上述机制都是一阶段的消息传递激励，节点不能最大限度被激励，两阶段激励机制将更好地激励节点参与消息传递，提高传递成功率。在已有工作的基础上，本文设计了一种激励机制，运用博弈论分析节点合作行为，找到节点参与消息传递的最佳策略，对节点进行两阶段激励，鼓励每个节点不仅从源节点接收消息，且将消息转发给其他节点。

3 系统模型

本文提出了一种基于Bertrand 博弈的激励机制（Bertrand Game-based Incentive mechanism，BGI），激励自私节点参与机会网络中的消息传递。BGI 包括节点之间交互的定义，以及参与消息传递节点的奖励机制和定价机制。本文把消息传输的过程类比为市场中货物的交易，假设携带消息的节点是买方，中继节点是卖方，卖方为买方转发消息获得收益，源节点需要从中继节点处购买服务用于消息传送。

3.1 交易模型

在机会网络中，假设节点的数量是n，节点集合是N={1,2,…,n}。节点可以携带多个消息，节点不仅可以是消息的源节点，而且可以是另一个消息的目的节点，它还可以在消息传输中充当中继节点。但是，在同一时间，节点只能转发一条消息给其他的节点。在图1所示的模型中，消息发送方称为源节点，准备接收和转发消息的节点称为中继节点。另外，模型中会有一个兑换点，机会网络中固定的基站、服务器，以及移动中的管理节点均可担当模型中的兑换点。源节点发送消息之后，可以去兑换点获取应得的虚拟货币。

图1 源节点和中继节点的交易过程

在本文的模型中，源节点和中继节点之间的交互有这几个步骤：第一步，源节点把转发请求广播给周围节点，源节点附近的节点都是候选中继节点，候选节点接收到源节点的请求后会考虑是否为源节点转发消息。第二步，对于准备为源节点转发消息的节点，它们以转发消息的成本回应源节点，并且不同的节点可能具有不同的成本。第三步，源节点把转发消息的价格回复给候选节点，不同候选节点收到的价格可能是不同的，但源节点需要制定一个合适的价格吸引中继节点转发更多的消息。第四步，根据源节点给定的价格，每个中继节点会制定转发计划，决定为源节点转发多少条消息，这个计划不仅影响中继节点的效用，也会影响源节点的效用。最后，源节点把消息传送给中继节点，并以虚拟货币形式给予中继节点报酬。

在消息传输中，参与者应该从源节点处接收消息，然后将消息转发给其他节点。为了最大限度地鼓励节点，本文对每个节点提供两阶段激励，也就是说，节点可以分别从接收和转发消息中分别获得奖励。源节点可以从兑换点处获得转发的每条消息c的虚拟货币的奖励。中继节点接收消息的奖励来自源节点。一旦中继节点接收到消息，它将成为下一轮消息传输中的源节点，它要找到其他节点并把消息转发出去，重复此过程，直到最终目的节点收到消息。

本文将源节点和中继节点之间的交互建模为商品交易过程，并基于博弈论分析交互双方的最佳策略，即源节点给出最佳价格，中继节点确定最佳转发数量，这个机制激励更多节点参与消息传输并实现自身利益最大化。对于在博弈中充当买方的源节点，它们期望给中继节点转发消息的价格尽可能低，这样源节点可少付出。然而，作为服务销售商，中继节点期望更高的价格并转发更多的消息，因为它们可以获得更多的奖励。因此，对于转发消息定价，较高的价格将导致对源节点的奖励较少，但对中继节点的奖励较多，双方之间存在利益的博弈，下面本文将讨论如何定价会让双方都满意。

3.2 效用函数

从源节点和中继节点的交易模型可知，如果源节点给的价格大于中继节点传递消息的成本，中继节点将会执行它的服务计划。对源节点来说，它必须考虑中继节点的成本以及它们可以转发的消息数量，并确定一个合适的价格，这个合适的价格可以吸引节点传递更多的消息，同时自己的效用也最大。中继节点效用受它们决定接收的消息数量的影响。但是，节点接收的消息越多，成本就越高。因此，中继节点的效用将在一定程度上饱和。

假设中继节点j从源节点i接收到ai个消息。中继节点j的效用函数定义为等式（1），并将源节点i的效用函数定义为等式（2）：

式中，Uj代表中继节点j的效用，pj代表中继节点j从源节点i处收到一条消息的价格，cj代表中继节点转发一条消息的成本，b是饱和系数。

源节点i的效用是将消息转发给中继节点j的奖励，并且转发的消息越多，效用就越大。因此，源节点的效用跟转发消息的数量是成正比，在等式（2）中，c是系统参数，需要满足c>pj，这意味着任何源节点转发一条消息的价格是一样的。

3.3 成本的真实性证明

在源节点和中继节点之间的交互中，中继节点需要向源节点发送转发消息的成本。从长远来看，中继节点会反馈转发消息的实际成本给源节点。如果中继节点j所给的成本是虚假的，则中继节点的效用并不是最大的，这在数学上可以证明。假设中继节点给源节点的是一个虚假的成本，源节点回报的价格是，根据等式（1），中继节点的虚假效用用等式（3）来表示：

对于节点j转发消息的真实成本cj，真实价格和效用分别是pj和Uj，比较Uj和，可以得到等式（4）：

3.4 二阶段激励机制

一个节点成功传输消息需要两个阶段：第一个阶段是该节点作为中继节点从源节点处接收消息；第二个阶段是该节点成为源节点把收到的消息转发给其他节点。从BGI 节点交易模型以及节点的效用函数中可以看出，中继节点只要接收源节点发送的消息，中继节点j会从源节点收获到每一消息pj的虚拟货币奖励。为最大化收益，中继节点考虑发送成本将选择一个合适的接收消息数量，接收到消息后会获得一定的虚拟货币，所得的效用可从等式（1）得出。这从接收消息阶段激励了节点在资源允许的前提下，尽可能多接收消息，以实现利益最大化。

中继节点j收到消息后将成为所收到消息的源节点，在下一轮消息传输中，节点j选择合适的中继节点把消息转发出去，节点j因为成功把消息转发给下一跳节点可以从兑换点处获得每一消息c的虚拟货币作为奖励。源节点的效用跟所转发的消息数量成正比，效用可从等式（2）得到。源节点想要获得更大的收益就会传递更多的消息出去，这就从转发消息这一方面鼓励了节点传递消息。

节点可以分别从接收和转发消息两个阶段中分别获得奖励。由于节点是理性的，节点会理性的选择参与BGI二阶段激励机制。节点是理性的，节点在接收到消息后，由于转发消息有利可图，因此自私节点一定会把接收到的消息转发出去以最大化收益。可见，二阶段激励机制可以避免节点收到消息后为节点资源后又把消息丢弃的行为，可以降低丢包率。

4 基于博弈论的定价分析

在本文模型中，为了最大化效用，源节点需要最佳定价策略，与之相应的中继节点需要最佳的服务计划。本文基于Bertrand[24]博弈建模分析源节点与中继节点之间的交互。

在Bertrand 博弈中，源节点是买方，需要购买中继节点的转发服务。中继节点是卖方，提供转发服务给源节点，转发消息是商品。如果商品的需求量给定，源节点可以基于中继节点的成本计算出最合适的价格，这个价格会让源节点得到的利润最大。如果源节点给的价格比中继节点的成本低，则中继节点将不会参与源节点的消息传递。对于中继节点来说，源节点的价格给定后，他们会决定为源节点转发多少消息数量来最大化自己的收益。下文将分析双方的最佳策略，并得到博弈中的纳什均衡[25]。

纳什均衡是每个参与者的策略对其他参与者策略的最优反应，即双方在对方给定的策略下不愿意调整自己的策略。纳什均衡是一种策略组合，因此每个参与者的策略同时是对其他参与者策略的最佳回应。本文将证明每位参与者的最佳回应是独一无二的。在源节点的策略价格基础上，中继节点会制定消息传送计划（即它们愿意为源节点传送的消息数量）以获得最大效用。本文可以通过效用函数获取到中继节点的消息传送计划。

基于源节点的价格策略，中继节点将制定策略，该策略是最大化效用的服务计划。中继节点j的效用函数是等式（1），可以得到Uj的第一阶导数式（5）：

Uj的二阶导数为式（6）：

由于b>0，Uj的二阶导数是负数，因此Uj是一个严格的凸函数。因此令Uj的一阶导数等于0，可以得到Uj的最大点ai，见式（7）：

如上式所示，中继节点在价格和成本给定的情况下，最合适的转发数量是，这个值可以最大化中继节点的效用。

把等式式（7）代入式（2）中，可以得到源节点的效用，如式（8）所示：

对Pi进行一阶求导，如式（9）所示：

Pi的二阶导数用式（10）表示：

由于b>0，Pi的二阶导数是负数，因此，Pi是一个严格的凸函数，Pi有一个最大值，令一阶导数等于0，可以得到最佳的价格pj，这个值可以最大化源节点i的效用。

从以上的分析可知，源节点i和中继节点j之间的博弈将会达到一个纳什均衡点，意味着源节点i最好的策略是给中继节点j的价格，中继节点j最好的策略是为源节点i传递的消息数量。

5 模拟仿真

为了验证BGI 激励机制的有效性，本文在ONE[26]模拟器中进行了模拟实验。在模拟实验中，使用了Infocom5、Infocom6、Cambridge和Intel这四个真实数据集进行了实验模拟，数据集的具体信息如表格1 所示。在模拟仿真中，每一个节点都以一个0.5～1.5 m/s的速度移动。每3 000～4 000 s就会有一个产生500 KB大小的消息，以及4 500 m×3 400 m 的地形尺寸。系统参数c和饱和系数b分别是10、1/2。

表1 四个数据集的仿真参数

5.1 性能指标

本文实验选择消息传递率，开销率和平均延迟这三个因素来验证激励机制的效果。

传递率是消息成功到达目的节点的总数与实际创建的消息数量之比。

开销率是指网络中全部中继的消息数（relayed_number）减去成功转发消息数（delivered_number），然后再与成功转发到目的节点的消息数之比。在数学上，可以定义为：

平均延迟是从消息产生到成功交付所花时间的平均值。

5.2 仿真场景

总所周知，存在的路由算法都是基于节点之间合作的。本文运行Epidemic路由算法，通过调整自私节点的数量来评估提出的激励机制的性能。考虑下面这几种场景：

（1）Epidemic+没有自私节点(E+N)。在Epidemic路由的背景下，没有任何自私节点，每个节点都会自发的转发消息。

（2）Epidemic+自私节点 (E+S)。在Epidemic 路由的背景下，加上自私节点。自私节点会拒绝接收其他节点传递过来的消息，不参与消息传递。通过调整自私节点的数量，观察实验结果。

（3）Epidemic+自私节点 +BGI(E+S+BGI) 。在Epidemic 的背景下，加入自私节点，再加上BGI 激励机制，调整自私节点的数量，观察实验结果。理论上，节点会被BGI激励机制激励，从而参加消息传递。

（4）Epidemic+自私节点+Reputation(E+S+R)。在Epidemic的基础上，添加自私节点，再加上Reputation激励机制，观察实验结果。

5.3 实验分析

如图2～5 所示，E+S中，没有加入激励机制，随着自私节点数量的增多，交付率急剧下降。当自私节点比率为0 时，相当于每一个节点都是正常节点，网络中没有自私节点，就是经典的Epidemic路由协议。当自私节点不断的增多，自私节点比率为1 的情况下，没有中继节点愿意传递消息，仅仅只有源节点不断移动碰到该消息的目的节点，才把消息传递给目的节点，也就成了经典的Direct路由协议。

图2 Intel数据集中传递率随着自私节点数量的变化

图3 Infocom6数据集中传递率随自私节点数量的变化

图4 Infocom5数据集中传递率随自私节点数量的变化

图5 Cambridge数据集中传递率随自私节点数量的变化

仿真结果显示自私节点严重影响传递效率，如果加入BGI 机制，节点是理性的，它会为了自身的利益，考虑跟其他节点合作，传递率会逐渐上升。由于E+N中没有考虑自私节点，因此E+N的性能仅呈现为零自私节点的情况。从图2～5可以看出，当网络中存在自私节点时，BGI 机制具有较高的传递速率，并且具有与E+N几乎相同的传递速率，这表明了BGI激励机制的有效性。与E+S+R相比，BGI 机制的平均交付率提高了31.4%。

随着自私节点数量的增加，与开销相关的仿真结果如图6～9 所示。由于自私节点不参与消息转发，因此E+S中的开销会随着自私节点数量的增加而减少。但是，在E+S+R和E+S+BGI 中，自私节点会被激励参与消息转发，因此E+S+R和E+S+BGI 中的开销会跟随着自私节点的数量的增加而增加，E+S+BGI的消耗比E+N稍低。

图6 Intel数据集中开销率随自私节点数量的变化

图7 Infocom6数据集中开销率随自私节点数量的变化

图8 Infocom5数据集中开销率随自私节点数量的变化

图9 Cambridge数据集中开销率随自私节点数量的变化

随着自私节点数量的增加，与平均延迟相关的仿真结果如图10～13 所示。从仿真结果可以看出，因为BGI机制能够激励更多的自私节点去为其他节点转发消息，相对于E+S和E+S+R来说，BGI有更低的延迟。跟E+S和E+S+R比较，BGI分别平均低11.8%和9.7%。BGI具有与E+N几乎相同的平均延迟，E+N是没有任何自私节点的情况。

图10 Intel数据集中平均延迟随自私节点数量的变化

图11 Infocom6数据集中平均延迟随自私节点数量的变化

图12 Infocom5数据集中平均延迟随自私节点数量的变化

图13 Cambridge数据集中平均延迟随自私节点数量的变化

从消息传递率可以看出，BGI激励所有节点参与传递，但是传递率并没有与E+N一样高，这是因为中继节点会选择合适的消息数量最大化自己的利益，这个合适的数量可能小于源节点本身的消息数量，这样会有少量消息不会从源节点处传递出去。可以从等式（7）中看出，合适的消息数量与饱和系数b有关，通过调节饱和系数得到不同的情况。下面，本文分析在Infocom5数据集中饱和系数b对BGI机制的影响，Infocom6以及其他数据集中有类似的表现，限于篇幅，本文仅以Infocom5数据集来展示参数b的影响。

从图14中可看出，饱和系数越小，传递率越高。从等式（7）中可以看出，合适数量与饱和系数b成反比。b越小，中继节点的合适数量越大，源节点可以把更多的消息传递给中继节点，E+S+BGI 的传递率则会增高。从图15 可以看出饱和系数b对E+S+BGI 消耗率的影响，E+S+BGI 消耗率随着饱和系数b的增加而减少。从图16 中可以看出饱和系数对E+S+BGI平均延迟的影响，饱和系数越大，平均延迟越高。

图14 Infocom5数据集中传递率随饱和系数的变化

图15 Infocom5数据集中开销率随饱和系数的变化

图16 Infocom5数据集中平均延迟随饱和系数的变化

6 结束语

本文定义了源节点和中继节点之间的交易步骤以及效用函数，基于Bertrand博弈建模分析源节点与中继节点的交互过程，源节点给定中继节点传递消息的价格，基于该价格，中继节点确定所传递的消息数量。在源节点和中继节点的博弈中，存在一个唯一的纳什均衡，使得双方效用都是最好的。仿真结果表明，本文所提激励机制可以促进自私节点之间的协作，提高路由算法在传递速率和延迟方面的性能。与基于声誉的激励机制相比，BGI机制能使消息传递成功率提高31.4%、平均时延降低9.7%。