机会网络中基于陌生节点的竞争转发策略

刘 慧，钱育蓉，张振宇，杨文忠

(1.新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046； 2.新疆大学 软件学院，新疆 乌鲁木齐 830046)

0 引 言

机会网络[1]的消息转发过程实质上是，当源节点携带信息随机游走，此时消息存在缓存中，根据消息转发策略寻找最优的中继节点，从而使得每一次寻找的中继节点当作下一跳转发节点，直到遇到目的节点，消息转发成功为止[2,3]。机会网络的实际应用较广，由于不需要端到端的设备辅助通信，机会网络能很好适应拓扑变化的场景，其中最具特殊性的是它可以适应严峻的环境并进行通信，大大提高了机会网络在实际应用中的有效性，例如野生动物数据收集、智能交通、深海网络等[4,5]。

机会网络主要的数据转发模式为 “存储—携带—转发”，因此选择节点，让消息在节点间合理转发、提高交付率，是当前研究的热点之一。针对此问题，目前学者研究基于消息冗余、节点相遇概率、节点自私性策略等提出了相应的算法[6]。目前已有Epidemic[8]、spray-wait[9]、prophet[10]、peopleRank[11]等算法，主要目的是提高机会网络中数据的交付率和降低延时。Epidemic[8]算法的核心思想是：整个机会网络中消息的转发采用洪泛机制，当源节点携带信息和其它节点相遇时，直接复制转发缓存的消息，直到遇到目的节点。其主要优点是在网络资源不受限和缓存充足的情况下大大提高了消息的交付率，降低了传输延迟，但是此方法让整个网络中产生大量的副本消息，使得网络资源浪费。研究学者开始提出通过选择最优节点进行消息的转发，从而控制网络的开销。spray-wait[9]算法在消息转发过程中分了两个阶段。第一阶段是spray阶段，节点相遇时消息以复制转发的方式在网络中扩散，对消息副本数量设置阈值，当到达阈值时进行wait阶段，在此阶段消息不再进行复制转发，只有遇到目的节点才进行转发。该算法通过两个阶段控制消息副本，降低路由开销。prophet[10]算法提出一种转发概率策略，通过评估消息被节点成功投递的概率预测出下一跳节点该如何选择。该算法核心思想是：根据两个相遇的节点更新预测值，选择最优的预测值节点，依据估计的预测值判断是否进行消息转发，从而控制消息副本的扩散和网络开销。

但还面临着如下问题，在机会网络环境中数据转发过程需要消耗大量节点的资源[7]，由于节点的资源受限，使得自私节点产生自私行为拒绝相遇转发信息，最终导致整个网络性能降低，如何选择一种数据转发策略使得节点积极参与转发是当下研究热点。

Bubble Rap[12]算法核心思想是在整个机会网络中依据社区的划分选择当前社区中节点活跃度最高的节点进行消息的转发，从而提高消息的交付率。针对机会网络数据转发过程中节点的自私行为，文献[13,14]引入经济学中的博弈论，引入短期收益和长远收益的概念，设计合理的奖惩机制，促使节点积极参与转发从而提高网络的性能。随后的研究者们考虑到节点的社会属性，提出节点陌生性的概念，OP[16]算法和STRON[15]算法在设计过程中考虑了节点的弱关系属性，即节点的陌生性，并通过数据集进行了仿真，仿真结果经分析发现陌生人对数据的转发起到加速作用，但未考虑当整个网络资源有限的情况下陌生节点在加速数据转发过程中存在节点的自私性行为。文献[17]综合考虑了机会网络中节点的介数中心性、节点之间的关系强度、节点的相似性、节点陌生性等，提出一种综合节点社会属性的转发算法，综合节点的社会属性选择最优下一跳节点，从而提高消息的交付率和减少延迟。但未着重考虑节点陌生性是否影响整个网络的缓存和资源问题。文献[18]提出一种基于陌生人的转发的BSIF算法，该算法综合考虑了机会网络中边缘节点的属性，通过定义节点的陌生性，计算节点的陌生值并通过加权激励陌生人促进数据转发，但未考虑陌生节点在整个网络中所占比例数是否影响整个网络的消息交付率。

本文在BSIF算法的基础上着重分析节点属性中节点的陌生性，在整个转发过程中携带陌生属性的节点所占的比例是否影响整个网络资源。本文的BSCP算法通过设置陌生节点在整个网络中所占的比例，设计陌生节点的竞争策略，使得在数据进行机遇转发过程中选择合适的陌生节点进行数据转发，该算法重点分析了消息转发过程中利用节点的属性制定相应的转发策略，其算法首先对节点的陌生值进行排序，其次通过竞争策略让陌生节点自身评估(包括缓存空间、能量等)，决定是否参与竞争，从而减少陌生节点的自私性，提高数据的转发率，减低网络开销和延迟。

1 网络模型与问题描述

1.1 机会网络模型

本文把机会网络中的陌生节点定义为[17]：短接触时间和低相遇次数，陌生节点在整个网络中可以随机定义，且符合整个网络中节点的运行状态。机会网络模型做如下假设：①节点定义[17]：n∈N，N={N0,N1…,Nn-1}，其中n表示移动节点，N表示节点总数；②陌生节点定义[17]：m∈M，M={M0,M1…,Mm-1}，其中m表示移动的陌生节点，M表示陌生节点总数；③陌生节点信任度：在整个机会网络环境中假设陌生节点不具备自信性，即均可信任并符合策略就进行转发；④网络组定义：NG={NG1,NG2,…，NGw}且NGw=NG，其中NG表示消息传递过程中的节点网络组。整个机会网络环境下，结合节点的相遇性和社会性，设Ni∈NG且Mi∈M，基于陌生节点转发的网络组如图1所示。

图1 基于陌生节点转发的网络组

在整个机会网络模型中，对不同的节点属性进行了网络组的划分，MG代表陌生节点的网络组，SG代表具有其它社会属性的节点网络组。当进行消息转发的过程中，源节点携带消息尽量避免在同一组内进行转发，这样有利于提高消息的投递率和成功率。初始阶段节点携带信息转发过程中很大概率寻找陌生节点进行转发，并假设陌生节点无自私属性；后期通过激励策略由陌生节点携带信息转发时，要通过陌生值的排序，这样有效提高了网络资源和缓存的利用率，让整个网络不会因为副本消息的增多产生冗余和拥塞[19]。

1.2 定义和假设

定义1 陌生节点自身评价标准：本文算法假设相遇转发以理想状态为主，即尽量使陌生节点进行消息转发，当陌生节点参与转发时自身会进行评价计算总效益I，其中陌生节点活跃度用Di，陌生节点与普通节点关系强度F(i，j)，陌生节点剩余能量比En，则节点自身评价指标I=Di+F(i，j)+En。

假设1：本文机会网络环境下的陌生节点都存在数据转发能力。

假设2：本文机会网络环境下的陌生节点，对于消息的转发处于理想状态，只要计算完成自身效益就存在竞争转发的思想。

假设3：本文机会网络环境下陌生节点和正常转发节点并存，且陌生节点存在自私性，当节点自身资源受限存在不足的情况下会出现自私拒发消息的情况，出现此情况即可启动竞争转发策略，使得节点的转发行为可控。

1.3 问题描述

在整个机会网络模型中，如何确定陌生节点所占的比例以及如何界定陌生节点转发的能力是至关重要的一步。通过陌生节点在整个环境中的比例情况和消息生命周期的阈值做以下问题描述：

(1)当出现边缘陌生节点情况时，即在数据转发过程中陌生节点所占比例少于总节点的10%，可直接参与转发不进行竞争；

(2)当陌生节点在整个环境中所占比例大于10%且小于50%时，根据自身的评价标准和节点的最大陌生值，决定是否参与竞争，但考虑到消息传递的生命周期不易过长则设置阈值为0.5，否则多个节点参与竞争会影响整个网络的时延；

(3)当陌生节点在整个环境中所占比例大于50%且小于90%时，根据自身的评价标准和节点的最大陌生值，决定是否参与竞争，消息传递生命周期阈值为最大值1；

(4)当网络不存在节点陌生值排序的情况下，节点无序发送会导致数据包碰撞，增大网络开销；

(5)节点移动过程中，同时计算普通节点和陌生节点的相遇概率，本文假设陌生节点m和其它节点的相遇概率为P(m，i)，则最低相遇概率的节点为Min(Pm)，消息转发成功时，网络针对源节点给予转发节点效用报酬为U，则对于陌生节点m的价值量为Um=U·P(mi,d)+U。

2 竞争策略

当在整个机会网络环境中，陌生节点的比例达到竞争策略的要求时，设计合理的竞争策略是本算法第二步关键之处。合理的竞争策略可以有效激励陌生节点参与转发的同时控制消息的转发生命周期，大大提高网络的性能。以下的竞争策略主要围绕问题描述为主进行展开：

(1)当整个网络中陌生节点所占总节点数量小于10%时，不考虑节点是否参与竞争，假设理想状态下节点会主动积极参与数据的转发，陌生节点所占比例小于10%的数据转发如图2所示。

图2 陌生节点所占比例小于10%的数据转发

(2)当陌生节点在整个环境中所占比例大于10%且小于50%时，首先通过节点的自身评价决定是否参与竞争，且对其陌生性进行排序，其次使用竞争策略激励陌生节点参与数据的转发，为了控制整个消息传递的生命周期设置TTL的阈值为0.5，目的是提高网络性能，陌生节点所占比例大于10%且小于50%的数据转发如图3所示。

图3 陌生节点比例大于10%且小于50%的数据转发

(3)当陌生点在整个环境中所占比例大于50%且小于90%时，首先通过节点的自身评价决定是否参与竞争，且对其陌生性进行排序，其次使用竞争策略激励陌生节点参与数据的转发，因为整个过程需要周期，所以设置TTL的阈值为1，陌生节点所占比例大于50%且小于90%时的数据转发如图4所示。

图4 陌生节点比例大于50%且小于90%的数据转发

3 BSCP算法

BSCP算法提出一种基于节点陌生性的竞争策略，着重分析陌生节点在整个机会网络环境中所占的比例对消息投递率的影响，同时考虑加入竞争策略激励节点参与转发，从而提高数据的转发速率，降低延迟。

3.1 节点陌生性及最大陌生值

在整个OPPNET中节点的陌生性和计算最大陌生值为重要的第一步，本文引用文献[17]中对陌生人的定义，其中通过节点间的相遇次数和相遇时间评价节点是否具有陌生性的重要因素，假设随机变量Xi为相遇次数，Yi为相遇时间。E(Xi)为Xi相遇次数的平均值，E(Yi)为Yi相遇时间的平均值。即示例如下

(1)

(2)

其中当E(Xi)、E(Yi)满足如下示例[17,18]

(3)

本文在第1.2节定义和假设部分已经假设整个OPPNET中的陌生节点都处于理想状态，则在数据转发过程中和节点其它社会属性相比，陌生节点会自发参与数据转发过程，为了避免陌生节点所占比例太大造成拥塞，首先对参与竞争的陌生性进行排序，找出最大陌生值[17]示例如下

(4)

其中，i节点在消息转发过程中遇到的陌生人数量定义为Sij，消息转发的次数定义为Conij。在消息生命周期内节点的陌生值定义为Rs。

3.2 陌生节点自身评价指标

本文在整个机会网络环境下，消息的转发受陌生节点自身评价指标影响。其中包括陌生节点活跃度、陌生节点和普通节点的关系强度、陌生节点剩余能量，综合3点才能计算在一个消息转发生命周期内消息的效用值。

(1)陌生节点活跃度：在整个网络对数据进行转发的过程中节点活跃度越高，参与转发的积极性就越大，从而数据的交付率就越高。本文中陌生节点的活跃度为随机游走的速率，首先设置总时间序列为T，划分为η个时间片，且每个时间间隔为λ，那么第t个时间间隔为ηt(t<λ)，设

Si={v1,v2,v3…vn}为在T的时间片η内节点的相遇集合，相应的，Si(ηλ)为在第λ个时间间隔内节点i与其它节点相遇的集合，则第λ-1个时间间隔内节点i的相遇节点集合为Si(ηλ-1)，因此陌生点活跃度定义如下，其公式如下所示[9]

(5)

(2)陌生节点与普通节点关系强度：根据文中1.2节中的定义与假设，在整个网络处于理想状态下，陌生节点本身具有转发性，当在进行数据的转发过程中选择下一跳节点是重点步骤，当陌生节点和下一跳节点关系强度越强则说明通过下一跳节点到达目的节点的概率就越高，因此由陌生节点的定义得出，在时间间隔ηt内，陌生节点Mi与节点Nj之间的关系强度F(i,j)(ηt)示例如下

(6)

(3)陌生节点剩余能量：当数据转发过程中对陌生节点进行选择时，首先要评估陌生节点自身指标，但是能量在整个指标中占很大比重，因此假设陌生节点M在任意时刻t的剩余能量表示为Em(t)，陌生节点的最大能量和剩余能量设为Emax和Ecurs示例如下

(7)

3.3 陌生节点竞争算法

本文设置陌生节点的比例，在下一跳节点进行消息转发过程中针对不同的陌生节点所占比例情况，制定不同的竞争策略。主要是因为每个消息都有生命周期TTL和转发阈值，只有设置不同的陌生节点转发策略，才能提高转发效率[19]。因此提出在竞争过程中加入利益递减函数进行激励，则利益递减函数示例所示

(8)

其中，V(F,ti)表示陌生节点在消息转发生命周期TTL中参与竞争获得的利益递减函数，在每一次的消息转发中如果大于TTL则终止转发。即可得出陌生节点在一个消息转发生命周期内的效用值示例如式(9)所示

(9)

3.4 算法描述

BSCP算法首先在整个OPPNET中找出陌生节点，通过判断陌生节点在整个网络中所占的比例，结合陌生节点活跃度等条件进行自身节点评价，通过竞争策略计算出最大陌生值并进行排序，从而在一定阈值范围内进行数据的转发。其详细步骤如下：

(1)寻找整个OPPNET网络中的陌生节点；

(2)计算陌生节点的陌生值；

(3)判断陌生节点在网络中所占比例；

(4)根据陌生节点自身评价标准进行评价(活跃度、关系强度、剩余能量)；

(5)通过竞争策略计算最大陌生节点；

(6)在节点所占比例范围内和消息转发周期阈值内继续数据的转发；

(7)直到消息从源节点转发到目的节点，算法终止。

BSCP算法

(1) Upon meeting up node j do selectMj//寻找陌生节点

(2) for any message m ini’s buffer do //将转发的消息放入缓存

(3) if md==jthen

(4) deliver Msg (m), remove(m) //直接遇到目的节点则完成转发移除消息

(5) else ifm∈Mjthen //重新选择陌生节点

(6) computeUmandI//计算陌生节点评价指标

(7) computeDi(ηt) andF(i,j)(η t)//计算陌生节点活跃度和关系强度

(8) compareEmaxandEcurs//计算陌生节点剩余能量Ecurs

(9) compareEm(t)

(10) find(Max(Rs)) //计算陌生节点最大陌生值

(11) if Util(mi) < Util(mj) or (a stranger of the destination or meet centrility of destination in TTL)//在消息生命周期内转发

and in >TTL delete Msg(m) //超过阈值丢弃消息

then

(12) forwarding Msg(m) //完成消息的转发

(13) end if

(14) if a stranger meets a high stranger with high Util(m) untill destination //到达目的节点完成数据的转发

then

(15) remove(m) //从整个缓存中移除消息

(16) end if

(17) end if

(18) end if

(19)end for

4 仿真实验分析

为了验证算法的有效性，本文通过ONE[20,21]仿真软件对BSCP算法进行仿真，并与STRON、BSIF及Epidemic算法进行比较，且对仿真结果进行分析。

4.1 仿真参数设置

本文中BSCP与Epidemic、STRON及BSIF这3个算法通过设置相同仿真参数，对结果进行分析对比，仿真参数见表1。

表1 仿真参数设置

4.2 评价标准

(1)消息交付率。其中指到达目的节点的消息数与所有源节点发送的消息数之比。

(2)路由开销。指从源节点到目的节点所有路径开销的总和。

(3)平均延迟。指到达目的节点的数据分组的平均耗时。

(4)网络吞吐量。指在单位时间内成功到达目的节点消息的比特数。

4.3 仿真结果分析

本文在4.2节中详细阐述关于机会网络中数据转发的路由策略的主要评价指标。本文主要从消息交付率、路由开销、平均延迟3个指标进行分析。

(1)按照消息交付率、路由开销以及平均延迟作为评价指标，在节点数量相同情况下对各算法进行比较分析。

从图5得知，当随着网络中节点数量增多，本文BSCP算法显示了较好的消息交付率，通过节点数量的增多，陌生节点比率增加，选择的竞争策略发挥最大作用从而提高了消息交付率。

图5 节点数量相同情况下的交付率

如图6所示，仿真初始BSCP算法和 BSIF算法平均延迟相对较高，因为通过竞争策略选择下一跳节点花费时间。通过在整个网络环境中设置陌生节点的比率，随着节点数量的增加陌生节点的比率上升，最终本文的BSCP算法平均延迟低于BSIF算法。

图6 节点数量相同情况下的平均延迟

由图7趋势图显示，网络中消息副本量增加使得Epidemic算法趋于比较高的路由开销，但本文BSCP算法对节点的转发设置了阈值，因此在控制消息副本数增加的同时减少了网络的路由开销。

图7 节点数相同情况下的路由开销

(2)按照消息交付率、路由开销以及平均延迟作为评价指标，在缓存空间相同情况下对各算法进行比较分析。

从图8中可以看出，各算法的交付率随着缓存大小的增加而增加，但本文BSCP算法显示了较好的性能，因为始终选择下一跳节点为陌生节点，所以整个网络缓存空间比较大，因而不存在由于缓存空间的不足消息被丢弃的概率，增加了消息交付率。

图8 缓存相同情况下的交付率

如图9所示，随着缓存大小的增加，本文BSCP算法拥有相对较低的平均延迟，但略高于BSIF算法。

图9 缓存相同情况下的平均延迟

由图10趋势图显示，节点在携带信息在机会网络中随机游走时产生大量的副本，因此缓存大小是算法仿真重要的因素，因为它直接影响整个网络的路由开销。本文BSCP算法和其它经典算法相比在仿真开始阶段路由开销高，原因是陌生节点的竞争策略在低缓存空间有一定的局限性。随后当缓存大小增加，通过陌生节点竞争策略最优选择中继节点减少了消息转发次数，降低了消息副本，从而路由开销在30 MB大小以后减少。

图10 缓存相同情况下的路由开销

(3)按照消息交付率、路由开销以及平均延迟作为评价指标，在运行时间相同情况下对各算法进行比较分析。

图11显示本文BSCP算法不但保持较好的消息交付率，而且也均衡了整个网络的缓存空间。主要原因是随着运行时间的增加，各算法交付率会随即上升，但消息的转发需要占用缓存空间，随着缓存空间的消耗，消息的丢失率会提高。

图11 相同运行时间下的消息交付率

如图12趋势图所示，在相同运行时间下，本文所提出的BSCP算法的平均延迟在刚开始阶段略高于STRON算法，随着运行时间的增加有着较大的浮动，随后趋于稳定。

图12 相同运行时间下的平均延迟

如图13趋势所示，在相同运行时间下，随着运行时间的增加，本文所提出的方法的路由开销明显低于Epidemic、BSIF及STRON，并且趋于稳定。

图13 相同运行时间下的路由开销

通过实验仿真分析验证在节点数量、缓存大小、运行时间相同的情况下比较BSCP算法和Epidemic、BSIF、STRON算法，发现本文BSCP算法在整个消息转发过程中交付率、路由开销比其它算法良好，但是在平均延迟方面存在不足，主要原因为竞争策略的过程需要耗时。

5 结束语

本文针对机会网络中中继节点选择问题，从节点属性出发，以选择节点边缘属性的角度进行分析，提出BSCP算法，该算法基于机会网络节点的陌生人属性，提出一种基于陌生人的竞争性转发策略。此策略通过节点的属性计算节点的陌生值，设计陌生节点的竞争策略，验证了不同比例的陌生节点促进数据的转发，提高数据交付率和减少延迟。仿真结果表明，与几种现有的典型转发算法相比，本文的BSCP算法在保证了较低的传输时延和较高的传输成功率的基础上，有效地降低了网络传输开销。使用真实数据集进行验证以及结合K-MEANS聚类算法探讨陌生节点社区的划分以及精准预测下一跳节点进行有效数据转发将是下一步的研究工作。