基于协作中继的高吞吐量机会网络路由算法

摘  要： 基于Barter机制的机会网络路由算法在数据分组交易过程中存在的僵局问题，导致网络吞吐量降低，为此，提出一种基于协作中继的路由算法（Routing Algorithm based on Cooperative Relays，RACR），在Barter机制中采用协作中继机制，引入多方交易激活数据分组的单向传递，同时优化分组删除的判定条件，对分组交易僵局问题加以有效解决，从而提高网络吞吐量，降低数据分组端到端时延。仿真结果表明，与现有的Barter路由算法和DT(Direct Transmission) 路由算法相比，RACR路由算法的网络吞吐量提高了7.9%以上，分组平均端到端时延则至少降低了8.5%。

    关键词： 机会网络；以物易物；博弈论；协作中继；路由算法

    中图分类号： TN92；TP393.04

    文献标识码： A

    DOI：10.16157/j.issn.0258-7998.2017.05.030


    中文引用格式： 任智，王中永，张勇. 基于协作中继的高吞吐量机会网络路由算法[J].电子技术应用，2017，43(5)：123-126.

    英文引用格式： Ren Zhi，Wang Zhongyong，Zhang Yong. A high-throughput routing algorithm for opportunistic networks based on cooperative relays[J].Application of Electronic Technique，2017，43(5)：123-126.

0 引言

    机会网络[1-2]是一种不需要在源节点和目的节点之间存在完整链路、利用节点移动带来的相遇机会实现通信的时延和分裂可容忍的无线自组织网络，在军事、灾难救助以及偏远野外地区等领域有着广泛的应用。目前，机会网络的研究是基于节点具有良好的协作性，然而，由于机会网络中节点的资源有限，为节约资源，节点都存在一定的自私性，自私节点通常会拒绝为其他节点转发消息，这种自私行为势必会严重影响机会网络正常的路由和数据转发功能，从而导致网络性能退化。

    目前，国内外对于含自私节点的机会网络的研究已经取得了一些成果，人们提出了各种激励机制来激励节点协作[3-7]，尤其是近年来越来越多地采用了经济学方法中的博弈理论[4-6]。基于Barter机制的算法是一类典型的基于博弈论的机会网络路由算法，该算法基于互惠机制，博弈双方互相交换彼此感兴趣或者具有潜在价值的消息。BUTTYAN L等[4]提出了Barter机制，主要用于激励网络中自私节点对自己不感兴趣分组的“存储-携带-转发”。LIN C S等[5]提出了基于Barter机制的针对对等网络(P2P)流媒体系统中自私节点的机制。ZHANG C等[6]结合信誉机制中虚拟货币交易的特点改进了原始Barter机制，提出了一种全新的激励范式C4，但未考虑分布式网络中节点的自私性。由上可知，现有基于Barter机制的路由算法仍然是仅考虑两两节点间进行的交易，未考虑分组交易存在的僵局问题，有进一步改善的需要。

    本研究基于上述研究成果，并在文献[4]的基础上，提出了一种全新的角度——基于协作中继的博弈模型，对归一化时间内的机会网络吞吐量及时延进行了分析，仿真实验证实了本模型的有效性。

1 网络模型与问题描述

1.1 系统描述

    设任一含自私节点的机会网络中，自私节点只转发自己感兴趣的数据分组。BUTTYAN L等[4]提出任何分组都有其潜在价值，当前不感兴趣的分组将来可用来交换感兴趣的分组。在Barter机制中，节点感兴趣的分组初始价值量为1，不感兴趣的分组初始价值量是自身采取的博弈策略Si={S1，S2，…，Sm}（0＜Si＜1）。部分变量定义如表1所示。

tx5-b1.gif

1.2 机会网络的博弈模型

    含自私节点的机会网络中节点具有自私而有理性的特点，在模型方面与传统的机会网络有所不同，故作出如下定义。

    定义1 博弈模型：机会网络的博弈模型为G=[V，{Si}，{πi}]；其中，节点集合V={v1，v2，…，vn}，n>1，即为博弈参与者；策略集合Si={S1，S2，…，Sm}，1≤m≤n(n-1)，表示节点对自己不感兴趣分组与感兴趣分组的比值；收益函数?仔i(S1，S2，…，Sm)表示网络中参与者采取策略后网络的实际吞吐量。

    定义2 数据分组属性：含自私节点的机会网络中，数据分组主要有两种属性：分组兴趣属性ζ(0<ζ<<1)与分组价值折扣属性(见式(3))。

    定义3 实际吞吐量模型：实际吞吐量Gi(0≤Gi(t)≤1)是节点i在每个归一化时间内成功传递分组获得的累计价值，节点i的该值可以在一个理想的情况下表示为：

tx5-gs1-2.gif

tx5-gs3-5.gif

    在RACR中，博弈参与者的收益只依赖于其选择的博弈策略，且博弈参与者在其策略空间中选取惟一确定的策略进行博弈，因此，这个博弈有对称的纯策略均衡解。

    综上分析可知，不难判断一个策略组合{s′}是否是纳什均衡。对任意参与者i(i∈V)，若i采取背叛策略能够获得更多的收益，则{s′}不是纳什均衡。由于参与者具有相同的收益函数，若{s′}是参与者i的最优策略，则{s′}也是其他参与者的最优策略。

1.3 问题描述

    (1)僵局问题：由于交易的公平性要求，分组交换由可交换数目小的一方决定，进行等量交换。若一个节点有分组需要转发，对方节点无该节点需要的分组或无足够分组与前者交换，将导致网络陷入僵局，造成网络等待时延，称之为“僵局问题”。

    (2)现有的Barter机制在数据分组交易过程中存在冗余交互操作。

    (3)根据现有Barter机制，价值量达到某一阈值的消息就简单丢弃，然而，这样很可能删除即将到达目的地址的分组，增大了消息传输时延。

2 RACR算法

    本文提出一种基于协作中继的高吞吐量机会网络路由算法——RACR。RACR算法采用引入协作中继节点的转发方式，对分组交易僵局问题加以有效解决，并重新设计满足协作中继的分组交易过程，引入多方交易以激活数据分组的单向传递，从而削减数据分组传递次数。同时，对价值量小于阈值的分组先判断其目的地址是否是邻居节点，从而提高分组传送成功率，降低数据分组传输时延。

2.1 RACR算法新机制

2.1.1 协作中继

    RACR算法针对现有Barter路由算法分组交易过程中的交易僵局问题，引入协作中继机制加以解决。考虑如下网络场景：假设节点u、v已完成两两之间的交易或节点u、v不存在相应的分组交易，若节点v仍有节点u需要而不能与之交易的分组。同时，节点u、v收到共同的邻居节点w广播的目的地址为v的分组索引，若节点w在节点v与w、u与w两两交易完成后，节点u、v根据节点w的分组索引计算发现节点w仍有节点v需要的分组，同时节点u也有节点w需要的分组。

    协作中继节点的选取思路为：当网络出现上述情况时，如图1(a)所示，根据Barter算法的原理，消息交易将陷入僵局。图1(b)表示RACR算法的分组交易示意图，如果网络出现上述情况，则节点w将会向节点v发送一个额外分组，节点v收到节点w发送的额外分组后会给节点u发送一个额外分组。最后，节点u给节点w需要的一个额外的分组。若存在能满足以上描述条件的节点，即是协作中继节点。

tx5-t1.gif

2.1.2 分组传递次数削减

    RACR算法引入多方交易以激活数据分组的单向传递，对数据分组的传递次数进行削减。考虑如下网络场景：节点u、v和w在同一通信范围内，节点u需要通过节点v交易获取节点v中的分组，节点v需要获取节点u中的分组用来交换节点w中的分组，同时节点u也有节点w需要的分组。

    分组传递次数削减思路为：当网络出现上述情况时，如图1（a）所示，在Barter路由算法中，中间节点v进行一次分组交换需要收、发2个分组才能完成交易。如图1（b）所示，在RACR算法中，首先发现节点间存在上述关系的节点向需要自身数据分组的节点发送一个数据分组，收到该额外分组的理性节点进行相同的操作，最后完成一个公平的交易。则RACR算法的中间节点v仅需要收、发1个分组，从而实现分组传递次数的削减，减少数据分组的冗余交互操作。

2.1.3 分组删除判定优化

    原始Barter路由算法中，节点对价值小于分组删除阈值的数据分组采取简单的丢弃策略。然而，虽然删除的分组价值量小，但很有可能即将到达分组的目的节点。在RACR算法中，节点对价值量低于删除阈值的分组，首先判断该分组的目的地址是否为该节点的邻居节点，若是则发起新的分组交易，否则直接删除该分组。这样在不影响网络开销的前提下，提高网络吞吐量，同时降低传输时延。

2.2 RACR算法操作

    RACR算法主要操作步骤如下：

    (1)节点u、v相遇，按Barter机制两两之间交易完毕。此时，若节点v仍有节点u需要而不能与之交易的分组，则进行步骤(2)，否则结束；

    (2)节点u、v收到公共邻居节点w发送的分组索引，根据节点w的分组索引计算判断节点w是否符合协作中继节点的要求。若符合，则进行步骤(3)，否则结束；

    (3)若节点u通过计算，最先获知协作中继节点w的参与情况。节点u向节点w发送一个节点w需要的分组，节点w收到u发送的分组后，立即向节点v发送一个节点v需要的分组。同理，节点v向节点u发送一个u需要的分组。

3 仿真

3.1 仿真环境

    本文使用OPNET软件作为仿真平台，选取Barter算法[4]和DT算法[8]作为比较对象，在相同仿真条件下分析比较它们的网络吞吐量、时延等性能。主要仿真参数设置如表2所示。

tx5-b2.gif

3.2 仿真结果及分析

    (1)归一化网络吞吐量

    由图2可知，与DT算法和Barter算法相比，RACR算法在网络吞吐量上提高了7.9%以上。主要原因是：①采用协作中继机制，从而选取合适的协作中继节点，对分组交易僵局问题加以有效解决；②对价值量小于删除阈值的分组首先判断其目的地址是否为邻居节点，若是则发起新的分组交易，从而提高网络吞吐量。

tx5-t2.gif

    (2)分组平均端到端时延

    由图3可知，RACR算法的分组平均端到端时延低于DT和Barter算法。主要原因是：①RACR算法通过引入协作中继节点，解决了交易的僵局问题，有效地减少网络等待时延；②分组传递次数削减机制通过引入多方交易以激活数据分组的单向传递，从而加快数据分组的交换，缩短数据分组交换的时延。

tx5-t3.gif

    (3)归一化控制开销

    由图4可知，RACR算法能够明显减少归一化控制开销。开销减少的原因主要是RACR协议引入协作中继节点，提高了消息的交付率，减少了消息在网络中的传输的平均跳数。同时，优化了分组交易机制，削减了分组交换次数，减少了消息交易过程中的额外开销，从而降低归一化控制开销。

tx5-t4.gif

    (4)分组传送成功率

    由图5可知，与DT算法和Barter算法相比，RACR算法显著提高了分组传送成功率。主要原因是：①引入协作中继节点，增加了分组交易机会；②优化分组删除判定机制，删除缓存消息之前先判断其目的地址是否是其邻居节点，若是则重新发起分组交易，从而提高了数据分组传送成功率。

tx5-t5.gif

4 结束语

    本文通过深入研究博弈理论在含有自私节点的机会网络的应用，提出了一种基于协作中继的高吞吐量机会网络路由算法RACR。RACR算法通过在Barter机制中采用协作中继机制并引入多方交易以激活数据分组的单向传递，同时优化分组删除的判定条件。仿真结果显示，与DT路由算法和Barter路由算法相比，RACR算法能够更加有效地促使含自私节点的机会网络进行数据分组交易，从而增加网络吞吐量，降低数据分组端到端时延。

感谢楼主分享