0 引言

    机会网络^[1]是一种不需要源节点和目的节点之间存在完整的路径，采取“储存-携带-转发”的路由模式并利用节点移动性带来的相遇机会实现通信的时延和分裂可容忍网络^[2]。在实际中，由于节点自身资源的有限性，为保护自身资源，节点会表现出自私行为。针对机会网络中节点的自私性问题具体分为两类：基于惩罚与基于奖励。

    基于惩罚机制的路由算法主要集中于基于TFT策略的路由算法。TFT^[3]策略，即在博弈开始阶段，各节点都是以协作转发策略进行博弈，之后当前节点采用对方节点在上一次博弈过程中采取的策略。

    基于奖励机制的路由算法主要以基于虚拟货币的路由算法为主。GIS机制^[4]中买卖双方轮番出价，但必须在三轮之后终止，即对于第三次的出价，另一方必须接受。该机制能够刺激自私节点的合作并减少多次博弈中因博弈过程引起的消耗。GSCP^[5]机制是一种基于概率路由的节点议价博弈机制，该机制假设消息对于节点的价值量与节点到达目的地址的概率成正比，消息从价值量低的节点卖出并由价值量高的节点进行购买，最终消息到达目的节点。

1 网络模型与问题描述

1.1 网络模型

    定义1 （消息价值量）节点移动过程中，消息对于节点的价值量跟节点与该消息的目的地址的相遇概率成正相关，假设P_i，d为节点i能够将消息m传送到目的地址d的概率，ω为消息的初始价值量，V为消息m对于博弈参与节点i的价值量，其值为V=ω·P_i，d。

    定义2 （买卖模型）若节点B想要获得节点S中的消息m，会向S发送购买请求，并制定出购买价格x，若在价格x下，S的效益值为正，则S同意B的出价，并将m发送给B；否则买卖双方进行下一轮议价博弈，直至达成协定或通信中断。 

1.2 问题描述

    在研究中发现现有的基于议价博弈的机会网络算法存在下列问题：

    (1)现有的GSCP算法在单次博弈中只有当双方的收益都不小于0时双方才会达成交易并采取交易成功策略，没有考虑卖方在数据包买入时可能已经获利，这降低了博弈双方交易的达成率以及采取交易成功策略的比率。

    (2)节点在进行数据包转发前，需要先交换SV-DP消息:当两个节点相遇，DP列表交互完成后，收到DP列表的节点能得知双方节点到其他节点的相遇概率；此时，若该节点到SV中某些数据包的目的节点的相遇概率高于相遇节点，则相遇节点不会求购此数据包，现有机制会将该类数据包的摘要加入SV并发给相遇节点，产生了数据包摘要的冗余。

    (3)数据包交易的过程中存在冗余的控制消息。在现有相关文献中数据包在两节点之间交易时，请求购买数据包的求购消息需要由买方节点单独发给卖方节点。经过研究发现，求购消息的源、目的节点与SV消息的源、目的节点相同，因此可以将SV-DP消息合并在一起进行发送，从而减小网络开销。

    (4)在数据包交互过程中，节点无法通过控制消息(包括hello消息及SV消息)得知数据包的TTL字段值，导致节点有可能购买生命期字段值为1的数据包，从而导致不必要的转发开销和操作。

2 EORB算法

    为了解决现有基于议价博弈的机会网络路由算法中存在的以上问题，本文提出了一种高效的机会网络路由算法——EORB(Efficient Opportunistic network Routing algorithm based on Bargaining game)，采用自适应精简数据包摘要、自适应合并SV-DP消息和求购消息、综合考虑买卖收益的博弈策略等机制。

2.1 EORB算法新机制

2.1.1 自适应精简数据包摘要

    本文提出“自适应精简数据包摘要”，它的基本原理如下：节点在往SV-DP或 DP-SV-BUY消息中装入数据包之前判断数据包的生命期字段的值是否大于1，且本节点与数据包中的目的节点的相遇概率是否小于相遇节点到数据包中目的节点的相遇概率，若是，则当前节点将该数据包的摘要装入SV-DP或 DP-SV-BUY消息，从而避免装入无用的数据包摘要，消除了因此而带来的冗余控制信息。

2.1.2 自适应合并SV-DP和求购消息

    现有的机会网络概率路由算法中，相遇节点在有消息进行交互的过程如图1所示，此交互过程存在信令冗余的问题。

    针对此问题，本文提出“自适应合并SV-DP消息和求购消息”，它的基本原理如下：

    在SV-DP消息交互阶段的操作中，当前节点在收到对方的SV-DP消息后，根据对方SV列表中消息的目的地址、对方概率列表中到该目的地址的概率及本节点概率列表中到该消息目的地址的概率来判断是否购买该消息。

    若购买该消息，则计算该消息在博弈均衡下的最优价格，在向对方节点发送本节点的SV列表消息时，将需要购买的消息加入SV列表后面，形成新的DP-SV-BUY消息格式，并将该消息的目的地址设置为对该消息的报价。对方节点在接收到DP-SV-BUY消息后，可以提取出对应的购买消息。DP-SV-BUY消息格式如图2所示，其改进后消息的交互流程如图3所示。

2.1.3 综合考虑买卖收益的博弈策略

    针对问题(4)，本文提出了“综合考虑买卖收益的博弈策略”的新机制，该新机制基本原理如下。

    当卖方节点与目的节点相遇概率和买方节点与目的节点相遇概率的差值产生的效益可以抵消博弈过程中的发送与接收损耗时，由买方节点根据子博弈均衡的最优价格向卖方节点提出报价。

    否则，当产生效益不足以抵消博弈过程中的发送与接收损耗时，买方节点下调报价，新报价为自身效益为0时对应的价格，卖方节点根据判断买进该消息的效益值与此次买方提出的新报价下的效益值的和是否大于0来决定是否接受该报价，若大于0，则接受，否则拒绝接受该报价。该机制在保证本节点综合效益值（买进与卖出）不小于0的前提下，使博弈双方交易成功的概率得到提高，进而加快了消息的转发速率，降低了消息到达目的节点的时延。

2.2 EORB算法操作

    EORB算法操作步骤如下：

    (1)节点S、B进入彼此通信范围，通过邻居发现得知彼此能进行信息交互。

    (2)节点S将SV列表及概率列表消息组成的SV-DP消息发送给节点B，若当前节点S的SV-DP消息中没有跳数为1的消息时，节点S直接向相遇节点B发送自身的SV-DP消息；若当前节点S的SV-DP消息中存在跳数为1的消息且该消息的目的地址不是此次相遇节点B，则将SV列表中的该消息对应的摘要从列表中删除，然后发送SV-DP消息。

    (3)节点B收到节点S的SV-DP消息后，首先按照步骤(2)中相同的操作对自身消息进行处理，同时利用对方SV-DP消息判断：若节点B与缓存中消息m的目的节点的相遇概率高于节点S，则从自身SV列表中将消息m对应的摘要删除；然后利用对方SV-DP消息中每个摘要消息的目的地址、对方概率列表中到目的地址的概率及本节点概率列表中到该消息目的地址的概率判断是否购买该消息。若购买该消息，则计算该消息在博弈均衡下的最优价格，在向对方节点发送本节点的SV消息时，将需要购买的消息加入SV-DP消息中，并将该消息的目的地址设置为对该消息的报价，组合成DP-SV-BUY消息。

    (4)节点S接收到节点B的DP-SV-BUY消息后，进行SV列表检索对比，若存在与自身SV源地址与消息标号相同的消息，则表明是求购该消息，并且目的地址的值是对该消息的报价，节点S通过综合考虑买进与卖出的收益总和值判断是否接受该报价。

    (5)节点S接受节点B的报价后，发送对应的消息给节点B。

    (6)节点B收到所购买的消息后，生成带有自身签名的交易凭条并发送给节点S。

    (7)节点S收到交易凭条后，若之后与交易清算中心相遇(CCC)，则向CCC递交交易凭条，CCC根据凭条向交易双方账户进行扣费与充值。

2.3 性论分析

    引理1： 与GSCP算法相比，EORB算法的消息转发率更高。

    在GSCP中，买卖双方在博弈过程中效益值计算公式以及博弈均衡的最优报价为：

式中，V_i表示消息m对节点i的价值量，c_i(r)表示第r轮博弈对于节点i的开销，u_i表示节点i的效益，T(m)表示传输消息m的开销，P(m)表示接收消息m的开销，x表示消息交易价格。只有u_B和u_S都不小于0时，消息才能从卖方节点传递到买方节点，假设u_B和u_S不小于0的概率分别为P_b和P_s，则此次博弈消息的转发概率为：

    在EORB算法中，买方节点在u_B不小于0时会同意购买该消息，而卖方会综合买进该消息后获得的效益u_b及此次卖出的效益u_S和值u_t，若u_t不小于0，则卖方节点同意卖出该消息。由于u_b恒为正值，假设u_t不小于0的概率为P_t，u_S小于0而u_t不小于0的概率为P_s1，则此次博弈消息的转发概率为：

    由式(3)和式(4)可知P_n>P，EORB算法的消息转发率更高，即得证。

    引理2： EORB算法的控制开销低于GSCP算法及HLPR-MG^[6]算法。

    假设网络中有m个消息，节点发送一次消息的能耗值为δ，消息由源节点到目的节点的平均跳数为ETX，节点携带每个消息的平均能耗为ε，消息传输的时间为τ，则在GSCP算法中完成消息的传送所需要的总能耗E_GSCP及时延T_GSCP为：

    而在EORB算法中完成消息的传送所需的总能耗及时延为：

    可知E_EORB<E_GSCP，T_EORB<T_GSCP，得证。

    引理3： 采用“自适应精简数据包摘要”机制能降低SV交互阶段的开销。

    假设网络中节点携带的消息个数均值为m，消息中跳数已经降为1且相遇节点非消息的目的节点的个数均值为n（n<m），单位长度的SV列表（指SV列表中只含有一个消息摘要）传输过程所需要的能耗为ε，则未采用“自适应精简数据包摘要”的机制中，当前节点在与其他节点进行SV交互时所消耗的能量为：

    采用“自适应精简数据包摘要”的机制中，当前节点在与其他节点进行SV交互时所消耗的能量为：

    可知，E_new<E_orig，得证。           

3 仿真参数与统计量

3.1 仿真参数

    本文具体仿真参数如表1所示。

3.2 仿真结果与分析

    (1)控制开销

    从图4可以看出，EORB算法的控制开销在每个场景中均低于其他两种算法。主要原因是：①自适应地精简SV消息的内容，使得控制消息的长度得到降低；②自适应合并SV-DP消息和求购消息机制使得控制消息的个数得到降低。

    (2)网络吞吐量

    从图5可以看出，EORB算法的网络吞吐量更大。这主要源自于：①综合考虑买卖效益的博弈策略使得买卖双方达成交易成功的概率得到提高；②自适应合并SV-DP消息和求购消息机制使得控制消息的个数得到降低，减少了无效的控制消息交互。

    (3)平均端到端时延

    从图6中可以看出，EORB算法具有较低的平均端到端时延。这是由于：①综合考虑买卖效益使得买卖双方交易成功率得到提高；②自适应合并SV-DP消息和求购消息使得控制消息个数降低，控制消息的交互过程得到减少。  

    (4)消息到达率

    从图7算法对比可知，EORB算法在消息传送成功率上有所提升。这是因为：①综合考虑买卖效益的博弈策略使得买卖双方达成交易成功的概率得到提高，提高了消息到达的成功率；②自适应合并SV-DP消息和求购消息机制使得控制消息的个数得到降低，控制消息的交互过程得到减少，有利于提高消息的到达率。

4 结束语

    本文针对现有基于议价博弈的机会网络路由算法开销过大与交易成功率不高的问题，提出了一种高效的机会网络路由算法——EORB。该算法采用自适应精简数据包摘要、自适应合并SV-DP消息和求购消息、综合考虑买卖收益的博弈策略等机制，加速了消息的转发速率，提高了消息的到达率，减少了消息的平均时延，并降低了系统的开销。

参考文献

[1] 熊永平，孙利民，牛建伟，等.机会网络[J].软件学报，2009，20(1)：124-137.

[2] STAVROULAKI V，TSAGKARIS K，LOGOTHETIS M，et al.Opportunistic networks[J].IEEE Vehicular Technology Magazine，2011，6(3)：52-59.

[3] SHEVADE U，SONG H，QIU V，et al.Incentive-aware routing in DTNS[C].Proceeding of the IEEE International Conference on Network Protocols，Orland，USA，2008：238-247.

[4] 刘期烈，候鹏翔.机会网络中激励节点检测策略研究[J].重庆邮电大学学报（自然科学报），2015，27(2)：266-272.

[5] WU F，CHEN T，ZHONG S，et al.A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks[J].IEEE Transactions on Wireless Communications，2013，12(4)：1573-1583.

[6] 任智，索建伟，刘文朋，等.基于多方议价博弈的机会网络高吞吐量低开销概率路由算法[J].通信学报，2015，36(6)：2015129.

作者信息:

任  智，康  健，徐兆坤

（重庆邮电大学 通信与信息工程学院，重庆400065）