机会网络中考虑缓存的路由算法

摘 要：机会网络是一种通过节点移动建立通信链路的无线自组织网络，一般通过消息复制的路由策略传递信息。但该方式将导致链路中存在大量消息副本，对节点缓存形成巨大压力，造成网络拥塞。针对该情况，结合Prophet算法，充分考虑节点缓存对链路状态及传输概率的影响，设计限制消息最大副本数量与及时删除节点缓存中不必要数据包的缓存管理机制，同时在Prophet算法中考虑了缓存比因素。仿真结果表明，该算法可以有效提高消息投递率，降低网络消耗。

关键词：机会网络;Prophet算法;缓存区管理;拥塞控制

DOI：10. 11907/rjdk. 182515 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2019）007-0080-04

Buffer Aware Routing Algorithm for Opportunistic Network

CHEN Wei-jie

（School of Optical-Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai 200093，China）

Abstract：The opportunistic network is a wireless ad hoc network that establishes a communication link through node movement. Generally， the information is transmitted through a routing policy that uses message replication. This method results in a large number of message replicas in the link， which puts tremendous pressure on the node cache and causes network congestion. Aiming at this situation， combined with the Prophet algorithm， we fully considered the influence of the node cache on the link state and the transmission probability. Two mechanisms for buffer management are designed， including limiting the maximum number of copies of the message and deleting the node cache in time. The data packet is considered in the Prophet algorithm. The simulation results show that the algorithm can effectively improve the delivery rate of the message and reduce the network consumption.

Key Words：opportunistic network;Prophet algorithm;buffer management;congestion control

作者简介：陈伟洁（1995-），女，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为无线网络和机会路由。

0 引言

如何在不需要提前建立端到端链路的情况下，利用设备的移动性快速形成自组织网絡，达到在网络中进行消息传递的目标，是目前无线自组织网络研究中的热点。在紧急情况下，经常会遇到原有链路被破坏，需要通过现有设备建立一条新链路的情况，如何在该情况下进行有效的数据传输是目前需要解决的一个难题。为此，研究人员结合MANET（Mobile and Ad Hoc Network）与DTN[1]（Delay-tolerant Network）的特点，提出机会网路（Opportunistic Network）的概念[2]。机会网络是一种不需要源节点与目的节点之间存在一条完整链路，而是通过节点移动过程中形成的相遇机会建立通信的自组织网络。机会网络相对于传统网络表现出更好的适应性，更加符合自组织网络的要求，因此近年来引起国内外研究者的广泛关注，并开展了大量应用研究，如在灾难发生的紧急状况下构建自组织网络[3]，以及可用于观察海洋生物种群[4]与监察自然环境下放牧系统 [5]的移动自组织网络等。由于机会网络是以“存储—携带—转发”的路由机制模式开展工作的，在该模式下要求网络提供节点的可靠性保证，节点在未选取好下一跳转发节点时，中间节点不能丢弃数据[6-7]。当网络中的大量数据需要被传输时，节点的缓存利用率较高，易造成网络拥塞，影响数据正常传输。因此，在机会网络中，拥塞控制是保证网络稳定性与可靠性的关键因素。

机会网络中针对拥塞控制情况有以下两种解决方法：①限制消息副本数量，避免生成不必要的数据包。消息在链路中一般采用消息复制方式传输给下一跳节点，对于未对消息副本进行合理控制的路由算法而言，在消息传输过程中，网络中会存在大量消息副本，因而极大地影响了网络性能[7]。针对该问题，文献[8]、[9]提出限制消息副本数量的路由机制，以减少因生成大量不必要数据包对网络造成的压力;②及时删除不必要的数据包。当网络中的数据包已传输成功或不需要传输时，数据包若还滞留在节点缓存中，易造成节点缓存溢出，不仅导致数据无法得到及时传输，更极大地浪费了网络资源。因此，针对不必要的数据包，可以使用DLR、DL、DOA、DY等删包方式进行处理[9-10]。

为避免出现网络拥塞状况，保证网络即使在高吞吐量的环境中也能正常传输数据是本文的研究重点。Prophet（Probabilistic Routing Protocol Using History of Encounters and Transitivity）算法通过比较节点之间的相遇概率，选择是否将消息转发给中间节点。该工作机制可大幅减少网络中的副本数量，但没有完全考虑到消息副本数量对节点缓存的影响。本文结合Prophet算法特点，提出控制消息副本数量以及考虑节点剩余缓存以避免拥塞的机制，从而有效提高消息投递率。

1 相关工作

机会网络中的节点是具有移动性且不稳定的，源节点与目的节点之间不存在一条已连接好的端到端的路径，即使在链路断开的情况下，也可以实现消息的逐跳转发，并成功传输消息。因此，其可以看成是具有一般DTN网络特征的无线自组织网络，更加符合自组织网络的需求[11-12]。

目前，基本的机会路由算法可以分为两大类[13]：基于复制的路由算法与基于效用的路由算法。基于复制的路由算法是通过复制消息副本传输数据，在网络中形成多消息存储的路由策略，典型路由算法有Epidemic算法等[9];基于效用的路由算法以一个效用值为衡量标准，为中间转发节点的选取提供参考因素。本文讨论的Prophet算法即是根据节点之间的转发概率筛选节点，进行数据转发[10]。

在基于复制与基于效用的经典算法中，未考虑到消息副本数量过多对节点缓存的影响，导致网路性能下降，因此具有一定局限性[11-12]。Prophet是一种基于概率转发的路由算法，节点在选择下一跳节点时会根据相遇概率传输消息，节点之间的概率在相遇时升高，分开时则随着时间延长而降低。Prophet算法的工作机制是只要遇到比自己传输概率大的节点则会复制一个消息副本给对方。基于效用的转发方式虽然在一定程度上控制了消息的转发副本数，但还没有减少不必要消息对节点缓存的影响。当节点接收新消息时，会判断自己是否有足够的缓存区，如果缓存区不够，则根据消息在缓存区的时间长短删除数据包，在缓存区中时间越长的数据包越容易被删除。因此，需要设置一个消息的生存期时间以控制消息生命长短，以便于删除不必要的数据包。

传统Prophet算法是通过比较相遇节点与目的节点的概率值决定是否将消息传输给相遇节点，假设a、b两点相遇，a、b两节点的概率值通过式（1）进行更新。

[P（a，b）=P（a，b）old+（1-P（a，b）old）*Pinit] （1）

[P（a，b）=P（a，b）old*γk]        （2）

式中，[Pinit]是预先设置的两节点之间的初始概率，γ是老化因子，γ∈[0，1]，k表示距离上一次更新的时间长度。

Prophet算法的概率还具有传递性，即a节点与b节点经常接触，b节点与c节点也经常接触，则节点b可作为节点a和节点c消息转发的中间节点，节点a、b、c的传递概率可按照公式（3）进行更新。

[P（a，c）=P（a，c）old+（1-P（a，c）old）*P（a，b）*P（b，c）*β] （3）

式中，β是一个常数，β∈（0，1），其决定了消息经过中间节点传递后对整体数据传输成功概率的影响。

虽然Prophet算法中概率的传递性可以有效减少数据广播引起的拥塞现象，但一旦拥塞现象发生，会极大地影响算法性能。如图1所示，若节点a、b与节点b、c都可以经常保持连接，根据Prophet算法的传递性，b节点即可作为a、c节点传输链路上的中间节点，并保持较高的投递率，但若b节点的缓存此时正处于拥塞状态，a、c节点链路上的数据包则无法正常转发。所以即使Prophet算法根据概率值的传递性选取了最好的中间转发节点，但若未考虑到中间节点的缓存情况，则无法合理地发挥该算法优点。如果此时a节点将消息转发给b节点，该消息则会溢出，否则a节点只能将消息保存在本地中，等待下一个合适节点进行转发。

图1 节点b在拥塞状态下的链路

2 Prophet算法改进

虽然Prophet算法根据概率效用值选择转发节点的工作机制已在一定程度上减轻了网络中的拥塞情况，但仍未考虑节点缓存对算法性能的影响。机会网络是一个以“存储—携带—转发”模式工作的自组织网络，一个节点如果处于链路中的关键位置，则其需要转发的消息更多，而消息数量及大小与该节点缓存情况密切相关。如果节点缓存情况可以得到有效管理，则会提高消息传输的成功率。在网络中，消息数量及大小都是随机的，但节点缓存却是固定的，只有对节点缓存情况进行有效控制，才能保证后续消息得到正常转发[11]。

2.1 节点缓存比

本文不仅针对节点缓存提出了有效的管理机制，還添加了缓存比效用因素，即算法在基于相遇概率选择转发节点基础上，同时考虑了节点缓存情况，选择转发成功率较高与缓存压力较小的节点作为转发节点。该方法能更加有效地避免拥塞现象产生，增加数据包投递率。节点缓存比定义如下：

[R=i=1nmi*SiBtotal]          （4）

式中，[mi]表示消息数量，[Si]表示消息大小，[Btotal]表示节点缓存大小。

2.2 节点缓存管理机制

本文提出的控制节点缓存数据包数量的管理机制主要包括以下两方面：

（1）限制消息在传输过程中的最大副本数。由于Prophet算法在传输消息时是通过复制消息副本的方式工作的，没有限制消息的最大副本数，当消息在网络中传递且数量足够多时，可以推测该消息已成功传输，此时再复制该消息副本无疑将给网络带来更大压力。因此，为每一个消息设置最大副本数量，当达到该上限时则停止复制消息，可以减少网络冗余。

（2）及时删除已传输成功的消息。已传输成功的数据包在网络中是无用的，并且会极大地占用缓存。其不一定是长期滞留在缓存中的老数据包，也可能是新包传输成功，但未被及时删除。及时删除已传输成功的数据包可以有效改善缓存情况，减少资源浪费。

3 路由算法设计

本文提出的改进Prophet算法的核心思想在于控制节点缓存区，包括限制消息最大副本数目与及时删除网络中不必要的数据包。针对以上两点操作可以有效降低缓存区压力，保证节点不会因缓存区溢出导致消息无法正常传输。在此基础之上，Prophet算法在选择转发节点时进一步考虑了缓存比因素，其改进算法步骤如下：

（1）a、b节点通过移动进入彼此通信范围，建立连接。

（2）两节点交换彼此在本地保存的与链路中其它节点的传递概率。

（3）根据式（2）计算节点a、b的传递概率，并考虑此时节点b缓存比Rb的情况。

（4）节点a中有传输到目的节点s的消息，但该消息并不存在于节点b中，此时比较P（a，s）与P（b，s）*Rb大小，若P（a，s）

4 实验仿真与性能分析

4.1 实验仿真设置

本文使用仿真工具ONE[12]（Opportunistic Network Environment Simulator）对改进算法进行实验分析及性能比较，验证本文提出的改进算法是否可以有效改善网络性能、解决拥塞情况。

本文模拟了一些经典场景下节点移动的消息传递情况，如学校、社区及工作区，这些场景的节点移动范围都存在一定规律性，但节点移动速度和方向是随机的。采用移动模型模拟这些移动场景，实验参数如表1所示。

表1 仿真配置参数

在上述场景下，本文分别对原Prophet算法、改进后的Prophet算法和Epidemic算法从网络性能的3个方面进行比较，分别是传输成功率、网络开销和传输延迟，比较在节点数量逐渐增加时网络性能的差异。

4.2 仿真结果与分析

本文对原Prophet算法、改进后的Prophet算法和Epidemic算法在不同节点数量时表现出的网络性能进行测试，仿真结果如图2-图4所示。

图2 传输成功率与节点数量关系

在图2中，随着节点数量的增加，由于原Prophet算法和Epidemic是通过复制消息的方式在网络中传输的，节点数量较多会增加节点之间的接触概率，导致消息副本在网络中的数量不断增加。当缓存溢出时，消息则无法得到正常传输。改进后的Prophet算法考虑到了缓存情况，假设节点缓存已经溢出，则该节点不会被选为下一跳节点，而是寻找其它适合的节点进行传递，使消息可以正常传输。

图3 网络开销与节点数量关系

在图3中，随着节点数量的增加，改进后的Prophet算法由于对缓存进行了管理，避免了消息在转发时选择缓存使用率高的节点，从而降低了算法开销，所以其网络开销一直保持在一个较低水平。但其它两个算法都是基于消息复制的路由算法，随着网络中消息副本的数量不断增多，并且没有解决节点缓存问题，因此易造成网络拥塞，增加网络开销。

图4 传输延迟与节点数量关系

在图4中，改进Prophet算法在传输时间上多于其它两种算法，主要是因为改进Prophet算法控制了网络中的消息副本数量，从而减少了与目的节点的相遇机会，在一定程度上也增加了消息传输到目的节点的时间，所以传输过程中比其它两个在网络中消息副本较多的算法花费时间更多。还有一个原因是在没有找到合适的转发节点时，节点会将消息保存在本地，直到遇到合适的下一跳节点才开始传输，从而导致传输延迟。

5 结语

本文分析了机会网络中存在的消息冗余情况，提出了设置消息最大副本数量与及时删除不必要数据包的节点缓存管理机制，并在Prophet算法基础上考虑了缓存比因素，设计了一个考虑节点缓存的改进Prophet算法。仿真结果表明，在相同条件下，改进算法相比于原Prophet算法及Epidemic算法，具有更高的消息投递率，可以有效防止网络拥塞情况发生，提高网络吞吐量。

参考文献：

[1] FALL K. A delay-tolerant network architecture for challenged Internets[C]. Conference on applications，technologies，architectures，and protocols for computer communication，2003：27-34.

[2] DAVIES E. DTN-the state of the art[EB/OL]. http：//www.n4c.eu/Download/n4c-wp2-012-state-of-the-art-101.pdf，2009.

[3] LILIEN L，GUPTA A，YANG Z. Opportunistic networks for emergence applications and their standard implementation framework[C]. Proceedings of 2007 IEEE International Conference on Wireless and Mobile Computing，Networking and Communications.IEEE，2007：588-593.

[4] SMALL T，HAAS Z J. The shared wireless info station model：a new ad hoc networking paradigm[C]. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking&Computing. ACM，2003：233-244.

[5] JUANG P，OKI H，YONG W，et al. Energy-efficient computing for wildlife tracking[J]. ACK Sigops Operation Systems Review，2002，36（10）：96-107.

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

[7] PUNEET K B，SHIPRA S，VANDANA D. Comparative analysis of reactive and proactive protocol of mobile ad-hoc network[J]. International Journal on Computer Science and Engineering，2012，4（7）：1281-1288.

[8] SPYROPOULOS T，PSOUNIS K， RAGHAVENDRA C S. Spray and wait： an efficient routing scheme for intermittently connected mobile networks[C]. Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking. New York， USA： ACM Press， 2005.

[9] NELSON S C， BAKHT M， KRAVETS R. Encounter based routing in DTNs[J]. Mobile Computing and Communications Review， 2009，13（1）： 56-59.

[10] LINDGREN A， PHANSE K S. Evaluation of queuing policies and forwarding strategies for routing in intermittently connected networks[C]. Proceedings of IEEE COMSWARE06，IEEE Press，2006.

[11] DAVIS J A， FAGG A H， LEVINE B N. Wearable computers as packet transpor mechanisms in highly partitioned ad-hoc networks[C]. Proceedings of the 5th IEEE International Symposium on Wearable Computers， USA： IEEE Press， 2001.

[12] MOTA VFS，CUNBA FD，MACDO DF，et al.Protocols，mobility models and tools in opportunistic networks：a survey[J]. Computer Communication，2014，48：5-19.

[13] QIANG Z，JING Y，MINGHUI W.Formal taxonomy research on opportunistic networks[C]. Proceeding of the 2nd IEEE International Conference on Broadband Network&Multimedia Technology，2009：854-857.

[14] HSU CJ，LIU HI，SEAH WKG. Opportunistic routing-a review and the challengers ahead[J]. Computer Networks，2011，55（15）：3592-3603.

[15] BECKER V D.Epidemic routing for partially connected ad hoc network [R]. Durhan，NC：Duke University，2000.

[16] HUANG T，LEE C，CHEN L. PRoPHET+：an adaptive PRoPHET-based routing protocol for opportunistic network[C]. 24th IEEE International Conference on Advanced Information Networking and Application，2010：112-119.

[17] 任智，黃勇，陈前斌. 机会网络路由协议[J]，计算机应用，2010，30（3）：723-728.

[18] 段鹏瑞，马华东，罗红. 基于梯度的DTN路由算法[J]. 北京邮电大学学报，2011，34（2）：63-66.

[19] SHEN J，ZHENG W. An improvement of buffer scheme for delay tolerant network[J]. International Journal of Future Generation Communication&Network，2013，6（4）：263-271.

[20] KERANEN A. Opportunistic network environment simulator [R]. Helsinki：Helsinki University of Technology，2008.

（责任编辑：黄 健）