机会网络下基于信任机制的改进Epidemic算法

2017-09-08张光华庞少博杨耀红陈振国

网络与信息安全学报 2017年8期

张光华，庞少博，杨耀红，陈振国

（1. 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071；2. 河北科技大学信息科学与工程学院，河北石家庄 050000；3. 华北科技学院河北省物联网数据采集与处理工程技术研究中心，河北三河 065201）

张光华1,2，庞少博2，杨耀红2，陈振国3

针对Epidemic算法导致机会网络拥塞引发的路由可靠性问题，提出一种基于信任机制的改进Epidemic算法。通过构建节点之间的信任机制，提供具有足够可信度的节点作为消息的下一跳转发节点，使消息进行有限规模的泛洪传播。仿真实验结果和分析表明，改进后的Epidemic算法避免了泛洪机制引发的网络拥塞问题，并且在路由可靠性和传输性能上有一定的提高。

机会网络；网络拥塞；信任机制；Epidemic算法

1 引言

微型计算机和智能传感器技术的发展推动着网络形态的转变，为摆脱只有建立端到端的通信路径才能实现网络通信的制约，提出了机会网络[1,2]（opportunistic network）的概念。机会网络属于间歇式连通网络，通信节点使用“存储−携带−转发”的路由模式，通过节点移动带来的相遇机会逐跳实现通信，具有间接性连通、传输延迟大、错误率高等特点。机会网络降低了对通信基础设施的依赖，目前广泛应用在手持设备组网、物联网下的车载网络[3]等方面。机会网络中的关键技术有节点移动建模、网络内信息处理和路由算法[4]等。其中，最为经典的一种机会路由算法是Epidemic算法[5]，该算法基于泛洪机制，消息源节点将数据分组复制给与之相遇的每一个节点，以“传染病”的传播方式将消息接力传递至目的节点。Epidemic算法在理论上具有最大传输成功率和最小传输延迟，但在无限泛洪策略下，数据间不断发生碰撞抢夺有限的资源反而降低了机会网络的传输性能。本文在Epidemic算法的基础上，通过构建机会路由的信任机制，为节点如何选择可靠的下一跳转发节点提供方法，控制Epidemic算法进行有限度的泛洪传播，从而优化机会路由传输性能，提高机会路由可靠性。

2 相关工作

相比拓扑稳定的网络模式，机会网络路由算法面临更大的挑战。按照路由算法是否需要借助额外信息辅助可将路由算法分为零信息型和信息辅助型[6]。Epidemic算法属于基于复制策略的零信息型数据转发策略，这种路由算法设计思路直观、易于实现，但也存在路由开销大、可扩展性较差等问题。在Epidemic算法基础上衍生了大量的其他算法，文献[7]提出一种具备自停止策略的Epidemic算法，分析网络节点的移动模型和同步时间模型，避免数据分组抵达目的节点后仍然在网络中蔓延，提高路由算法的效率并节约路由开销。文献[8]提出一种通过时延约束对节点数据分发进行调度控制的策略，在节点状态满足最大时延要求的同时最大限度地减小能量消耗，并通过数学手段做进一步分析，在相同时延要求下节省能量。文献[9]通过优化节点的缓存，在最佳的持续时间内将消息转发至另一节点，降低网络负担，提高路由算法的性能。文献[10]使用马尔可夫链分析Epidemic路由在一维稀疏双线性ad hoc网络中的应用，减少消息时延和复制数量，佐证路由算法的正确性。文献[11]提出一种具备自适应调整的n-Epidemic路由协议，监测节点周围环境的能量水平确定复制数量，即参数n，通过能量水平进行自适应调整，降低网络能耗延长网络使用寿命。文献[12]对延迟容忍网络中Epidemic路由算法进行能量消耗上的改进，基于能量感知的方法优化路由策略的能量消耗，节省路由开销。文献[13]提出一种有限传染的数据分发机制，对网络中的数据副本进行控制，并在此基础上提出一种能量平衡方案以提高网络效率。文献[14]提出DTN网络中最佳能量感知的Epidemic路由，通过对能量的感知改善路由策略的性能，节省路由开销。

以上工作将零信息型的Epidemic算法转化为信息辅助型路由算法。文献[7～11]通过引入调度控制策略，控制消息复制数量，避免网络拥塞，但是引入这些策略后机会路由被人为地进行了控制，忽视了机会网络中节点的自主选择性。文献[12～14]通过感知周围其他节点的能量，进行相应的调整，降低网络能耗，但仅通过能量感知的方式关注节点的能量情况，不能全面地评价节点的转发能力和路由性能。因此，这些工作不能达到简单有效地改进Epidemic算法的目的。本文提出一种基于信任机制的改进Epidemic算法，通过建立信任机制，简单有效地区分网络中节点属性，为消息如何选择下一跳转发节点提供依据，避免泛洪策略引发的网络拥塞，提高路由算法的传输性能，增加路由算法的可靠性。

3 信任机制

Epidemic算法采用泛洪的转发方式传递消息，携带消息的源节点将消息复制给其遇到的每一个中间节点，中间节点无条件地接收并转发这些数据分组。中间节点因其自身剩余存储空间和能量的限制，具备的转发能力不尽相同，一些重要程度不高的消息占据节点的存储空间，消耗节点的能量，阻碍重要消息的传递，降低了网络的使用效率。理论情况下，增加携带数据分组的节点数量，可以有效地增加与消息目的节点相遇的机会，提高消息的传输成功率。而实际情况下，使用Epidemic算法不能使节点充分利用自身资源进行有效的数据分组转发，导致自身资源浪费的同时，影响机会网络的通畅。为避免网络拥塞导致的路由传输性能下降，在路由算法中引入一种交易机制，为消息源节点选择可信度较高的下一跳节点提供方法，为区别Epidemic算法，本文提出的基于交易机制的改进Epidemic算法命名为r-Epidemic算法。

3.1 相关定义

机会路由不具备稳定的拓扑结构，消息传至目的节点前并不清楚完整的传输路径。在这种传输特性下，综合影响机会路由传输性能的因素，制定了一种交易机制。将机会网络中消息的传递过程虚拟为商品的交易过程，首先由消息的发起者即源节点对消息进行定价，具有充足购买能力的中间节点获得转发消息的机会，携带消息继续进行移动，获得消息的中间节点可继续对消息进行定价，获得更多的收益和转发机会。以下对交易机制中出现的概念和计算方法进行定义。

定义1 将机会网络中消息的传递过程虚拟为商品交易过程，将消息虚拟为具有交易价值的商品，定义信任值为虚拟交易中的货币，信任值是度量消息价值的唯一依据，信任值为可数常数，且可能出现负数，节点信誉值范围不做限制，并赋予节点初始信任值为100。

定义2 消息的价值分为初始价值和二次价值，源节点对消息进行初始定价，定价依据是消息的重要程度；其他中间节点可对消息进行二次定价，二次定价的目的是为了避免携带消息的中间节点不能与目的节点相遇而导致自身价值的损失。

定义3 影响消息传递价值的主要因素是消息的剩余生存时间Tr，消息的生存周期Tmax由源节点确定，当Tr=Tmax时消息具有最大的传递价值，随着Tr的减少，消息的传递价值也减小。

定义4 影响中间节点转发消息的主要因素为节点剩余存储空间Sr和剩余能量Er，剩余存储空间Sr影响节点能否正常复制转发消息，剩余能量影响节点可转发次数，两者共同决定了节点在消息传输过程中获得的价值。

以上几个定义规定了影响消息价值和节点获益的因素，为信任机制的构建提供了前提条件，在通过构建信任机制改进Epidemic算法的研究中，构建信任机制的核心算法是关键，以下定义信任机制中的相关算法。

定义5 使用字母V代表消息的价值，消息的初始定价Vout如式(1)所示。

二次定价与初始定价的唯一区别是引入了消息剩余生存时间的影响，二次定价一般发生在中间节点成功买入消息一段时间后仍未与消息目的节点相遇的情况，中间节点需要主动降低消息的价值，即节点降低转发消息的价值门槛，使更多的节点参与消息转发中，增加消息与目的节点相遇的概率，避免自身的信任值损失。

3.2 工作流程

r-Epidemic算法沿用原Epidemic算法采用泛洪机制的相关特点，引入了可受信任的交易机制对泛洪进行约束，在特定范围内进行有限度的泛洪，避免数据碰撞导致网络拥塞，降低机会路由的开销，增加数据传输效率，提高机会网络的顽健性。r-Epidemic算法工作流程如图1所示。

图1 r-Epidemic算法消息转发流程

4 博弈分析

前文叙述了r-Epidemic算法的工作机制，现将非主要因素简化并将交易过程转化为一个博弈对局过程，依据博弈[15]三要素原则，博弈的参与人是路由中参与消息转发的节点；供博弈参与人博弈的策略为能否满足复制消息的条件并据此选择是否参与消息转发；博弈中参与者的支付即节点的信任值收益。消息传输过程中，节点不能同时了解其他节点的获益情况，并根据与携带消息节点相遇的顺序进行序贯决策，因此节点间的博弈是不完全信息动态博弈。r-Epidemic算法中的序贯博弈可表示为一个以源节点为根节点的博弈树，中间节点是树中的决策节点，末端节点则是消息的目的节点。从根节点至末端节点构成一条完整的路由，由于不是所有与源节点相遇的中间节点都能成功完成交易，故此时的博弈树不能成为一棵满树。在r-Epidemic算法中定义了中间节点可进行二次定价，因此树中的中间节点可以成为新的根节点，即树的一枝又可以看成一棵以携带消息的中间节点为根节点的新树，成为博弈的子博弈。作为决策节点希望获得更多的利益，损失利益会减少获得转发消息的机会，故决策节点会在自身能力范围内尽可能地参与竞价获取转发机会，同时获得转发机会的节点也会花费自身的价值储备，因此也担负价值损失的风险。为了规避风险决策节点，要创造更多的转发机会，这就增加了机会路由传输的成功率。

在r-Epidemic算法中，节点在不同的条件下会获得不同的收益，且与转发的次数相关。利用消息的价值公式可以改写节点在转发过程中的收益总量Vin，如式(3)所示，式(3)中n代表中间节点转发消息的次数，N代表最大的转发次数。

节点的收益矩阵如表1所示。

表1 节点收益

相比未获得转发机会，中间节点在获得转发机会时收获较多的收益，因此机会网络中的节点具备的信任值成为决定节点生存和发展的必要条件，且在转发价值较高的消息过程中可以收获更多的收益，故节点会更倾向于转发价值较高的消息，但是由于机会网络节点移动的不确定性和r-Epidemic算法的交易规则，获得转发机会的节点也面临利益损失的威胁，即高收益的同时也面临高风险。因此，此时节点会出现不同的信任值情况，这为遴选不同信任值的节点作为消息的下一跳转发节点提供了可能，同时由于源节点对转发节点的信任值要求，不符合信任值要求的转发节点被遗弃，同时被遗弃的转发节点可以通过转发信任值要求较低的消息积累自身的信任值储备。这为消息有选择地在有限范围内进行受控的泛洪传播提供了可能，这是r-Epidemic算法相比Epidemic算法有所优化的地方，且这种方法简单、易操作。

5 仿真实验与结果分析

通过对r-Epidemic算法的博弈分析，相比基于泛洪机制的Epidemic算法，r-Epidemic算法通过以虚拟交易为基础的信任机制，为消息如何选择下一跳转发节点提供了方法，控制消息进行有限度的泛洪传播，这在减少机会网络的路由开销、提高机会路由的传输效率、增加机会网络的可靠性上是有帮助的。在仿真实验部分采用机会网络常用的ONE平台[16]，模拟携带有智能传输设备的各型车辆行驶于城市中的场景，通过不同算法在传输成功率、传输时延、路由开销上的差别进行定量分析。同时，选取了经典的Epidemic、Direct Delivery和First Contact等算法与r-Epidemic算法进行性能上的对比，仿真界面如图2所示。

图2 仿真界面

仿真实验中设置的参数如表2所示。

表2 相关参数

5.1 路由开销

路由开销是在一定时间内节点转发的数据分组的数量，路由的开销越高，则网络中数据分组数量越多，数据分组发生碰撞的机会越大，消耗的节点能量越多。路由开销大会影响机会路由的传输流畅性，引发网络拥塞，增加网络运行压力。Epidemic算法最致命的弊端即路由开销过大导致的网络拥塞，r-Epidemic算法改进的最主要目的就是在相对不损耗过多传输成功率的前提下降低机会路由的开销，几种算法在路由开销上的对比如图3所示。

图3 路由开销对比

相比基于泛洪机制的Epidemic算法的路由开销，r-Epidemic算法的路由开销有明显下降，但仍然高于其他几种算法，这是因为r-Epidemic算法并未完全抛弃泛洪机制，而是对原Epidemic算法的优化，控制节点进行有限的泛洪传播。在当前情况下，由于路由开销过大引发网络拥塞的概率已降低40%左右。

5.2 传输时延

传输时延是数据分组从源节点到达目的节点所需的时间，传输时延越小则路由的传输效率越高，缩小传输时延可以提高消息的时效性，同时可以释放资源用于其他消息传输，提高机会网络的使用效率，几种路由算法传输时延上的对比如图4所示。

图4 传输时延对比

r-Epidemic算法的传输时延高于Epidemic算法10%左右，但两者都低于其他路由算法，相比于Epidemic算法，r-Epidemic算法在降低40%的路由开销的同时，传输时延提高了10%。而且，当仿真实验在理想情况下进行，并不能完全仿真泛洪传播条件下引发网络拥塞对传输时延的影响，因此r-Epidemic算法在传输时延这一性能指标上是可以被接受的。

5.3 传输成功率

传输成功率指在一定时间内成功到达目的节点的数据分组总数和源节点发出的需传输数据分组总数之比，传输成功率是确定路由模型正确转发数据分组到目的节点的重要指标，是评价路由算法性能的最重要因素，几种算法在传输成功率上的对比如图5所示。

随着节点数量的增多，r-Epidemic算法的传输成功率趋于稳定在50%左右，在机会网络特殊的传输方式下属于较高水平，相比于Epidemic算法有很大的提升。节点数量越多，由Epidemic算法导致的网络拥塞现象越严重，对传输成功率的影响越大。

图5 传输成功率对比

综合r-Epidemic算法和Epidemic算法在上述3项性能指标上的对比，对原有Epidemic算法优化后的r-Epidemic算法，仍然延续了泛洪机制的一些特点，但是相比于Epidemic算法，r-Epidemic算法在路由开销上降低了40%，在传输时延上增加了10%，同时在传输成功率上有较大的提升。因此，引入信任机制的r-Epidemic算法在整体的路由性能上相比于原Epidemic算法有较大的改进，相比极端的路由算法在性能上做了一定的折中，传输性能更加稳定和可靠，规避了路由可能出现的安全风险。

6 结束语

结合机会网络的特点，本文提出一种Epidemic算法的改进方案。将消息的传输过程虚拟为商品交易过程，使消息成为具有交易价值的商品，具有足够购买能力的节点才能获取消息转发机会，为机会路由如何选择转发时机和下一跳节点提供了方法，并控制消息进行有限度的泛洪传播。实验结果表明，优化后的r-Epidemic算法整体的路由性能和可靠性要明显优于原算法。

[1] PELUSI L, PASSARELLA A, CONTI M. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine, 2006, 44(11):134-141.

[2] BOLDRINI C, LEE K, ÖNEN M, et al. Opportunistic networks[J]. Computer Communications, 2014, 48(14):1-4.

[3] WU Q W,LIU Q Z,ZHANG L, et al. A trusted routing protocol based on GeoDTN plus Nav in VANET[J]. China Communications, 2014, 11(s2):166-174.

[4] XIONG Y P, SUN L M, NIU J W, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1): 124-137.

[5] TEERAPONG C, WORRAWAT N, SUMET P. An efficient spreading epidemic routing for delay-tolerant network[C]//The 13th IEEE Annual Consumer Communications & Networking Conference (CCNC). 2016:473-476.

[6] MA H D, YUAN P Y, ZHAO D. Research progress on routing problem in mobile opportunistic networks[J]. Journal of Software, 2015, 26(3): 600-616.

[7] CHEN Z S, CHEN C. Self-stopping epidemic routing in cooperative wireless mobile sensor networks[C]//The IEEE 12th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob). 2016:1-7.

[8] HEEJUNG B, JUNGMIN S. Node scheduling control inspired by epidemic theory for data dissemination in wireless sensor-actuator networks with delay constraints[J].IEEE Transactions on Wireless Communications,2016,15(3): 1794-1807.

[9] AHMED E O, KHALID R, MOHAMED E K, et al. Optimal content caching for epidemic routing in delay tolerant networks[C]// International Conference on Wireless Networks and Mobile Communications (WINCOM). 2016:220-224.

[10] SUN H F, SONG L L. Performance analysis of epidemic routing in 1-d linear sparse VANETs[J]. IEEE Communications Letters, 2016, 20(10): 2087-2090.

[11] ZHANG F, WANG X M, LIN Y G, et al. Adaptive adjustments of n-Epidemic routing protocol for opportunistic networks[C]//2015 IEEE International Conference on Progress in Informatics and Computing (PIC). 2015:487-491.

[12] BHED B B. Improving energy consumption of epidemic routing in delay tolerant networks[C]//The 10th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS). 2016:278-283.

[13] GUO D, CHENG G, ZHANG Y, et al. Data distribution mechanism over opportunistic networks with limited epidemic[J]. China Communications,2015,12(6): 154-163.

[14] SOHEIL E, KHOUZANI M, SASWATI S,et al. Optimal energy-aware epidemic routing in DTNs[J].Transactions on Automatic Control, 2015, 60(6): 1554-1569.

[15] ZHANG Y X, HE J S, ZHAO B, et al. A privacy protection model base on game theory[J]. Chinese Journal of Computers, 2016, 39(3): 615-627.

[16] TETSUYA O,DONALD E, EVJOLA S, et al. A simulation system based on one and SUMO simulators: performance evaluation of direct delivery, epidemic and energy aware epidemic DTN protocols[C]//The 18th International Conference on Network-Based Information Systems. 2015: 418-423.

Improved Epidemic algorithm based on trust mechanism in opportunistic networks

ZHANG Guang-hua1,2, PANG Shao-bo2, YANG Yao-hong2, CHEN Zhen-guo3

（1. State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, China; 2. College of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang 050000, China; 3. Hebei Engineering Technology Research Center for IOT Data Acquisition & Processing, North China Institute of Science and Technology, Sanhe 065201, China)

Aiming at the problem of routing reliability caused by Epidemic algorithm, an improved Epidemic algorithm based on trust mechanism was proposed. Through the establishment of trust mechanism between nodes, this mechanism can provide sufficient trusted nodes as the next hop node of message forwarding, and can promote that the Epidemic algorithm performs the limited scope of flooding under the constraint of trust mechanism. Simulation results and analysis show that the improved Epidemic algorithm can avoid the network congestion caused by flooding mechanism, and the reliability of routing and transmission performance are improved to some extent.

opportunistic network, network congestion, trust mechanism, Epidemic algorithm

s: The National Natural Science Foundation of China (No.61572255), The China Postdoctoral Science Foundation (No.2015M582622), The University Scientific Research Foundation of Hebei Province (No.YQ2014036, No.QN2017062), The Technology Research and Development Program of Hebei Province (No.15210338, No.15210703)

TP393

10.11959/j.issn.2096-109x.2017.00187