容迟网络中基于复制策略的单播路由算法研究

王欣

（青岛远洋船员职业学院 山东 青岛 266071）

容迟网络或者容延网络（Delay/DisruptionTolerantNetworks，DTN）是近年来无线网络领域内的一个研究热点，泛指部署在极端环境下由于节点的移动或者能量调度等原因而导致节点间只能间歇性进行通信甚至长时间处于中断状态的一类网络。与基于TCP/IP协议簇的Internet网络和传统的无线传感网络不同，DTN是端到端存储转发网络体系结构，并且涉及的网络环境多样，且具有间歇连接，频繁割裂，时延极高，非对称的数据速率，较高的误码率等特点，故传统的路由算法在DTN中不再适用。DTN路由算法研究正是希望使得这种拓扑结构随时间动态变化的网络信息交换更为有效、可靠。正因为具有这些特点，DTN的应用涵盖了除了Internet之外的许多网络。DTN最初主要应用于星际网络和军事网络，之后又被应用于乡村网络，野生动物监控与追踪网络，以及移动Ad hoc网络等。

如何做出正确高效的路由选择一直是无线网络领域内的关键技术和主要研究课题。由于传输链路的时变性和不确定性使得容迟网络中的路由研究是一项挑战性的课题，因此设计可靠有效的容迟网络路由算法来提高网络连接性、降低能量消耗和时延、增加消息投递率就成为容迟网络研究的一个核心问题。DTN的路由算法方面的研究越来越受到国内外学者的重视，文中将对基于复制策略的单播路由算法进行了研究讨论。

1 基于复制策略的单播路由算法介绍

根据路由策略的不同，单播路由可以分为基于复制策略、基于转发策略、以及常用于移动传感网络中的节点控制类型。在基于复制策略的路由算法中，源节点或者中继节点在转发消息时向与之关联的多个邻居节点复制该消息。在某一时刻，网络中有该消息的多个副本在传输，这种方法是通过提高消息的冗余度来增加端到端消息传输的成功率。复制策略中分为基于洪泛，基于概率，基于调度（优先级），基于编码4种类型。

1.1 基于洪泛（路由扩散/Flooding Strategy）策略

1.1.1 传染病 （Epidemic）路由算法

著名的传染病（Epidemic）路由算法是其中的一个代表性算法，该算法模仿生物环境中传染性病毒的传播方式，体现在DTN中，每个节点维护一个消息总结向量，当两个节点能够连接时通过交换消息向量来彼此交换缺少的消息。经过一段时间，网络中的每个节点将收到所有的消息。传染病路由算法本质上是基于洪泛策略（flooding）的，优点是不需要额外的拓扑控制信息，同时可以取得高的消息投递率和低的端到端时延，无需对链路状态进行预测与估计，实施起来较为简单。缺点是网络中存在大量的冗余副本将导致节点能耗增加和缓存溢出，进而导致网络的资源利用率低和整体运行效能低下，该算法主要适用于缓存和带宽充足的场景。

1.1.2 一跳传输（Single Hop Transmission）路由算法

与其它路由算法相比，基于一跳的路由算法是将信息从源节点传送到目的节点最简单的方法。当源节点与目的节点建立连接时，源节点立刻把信息传送给目的节点。当源节点和目的节点之间只有一跳的距离时，这种策略既简洁又有效。在这种策略中，不存在中继的冗余信息。其优点是只需要消耗很少的资源，然而这种算法最大的缺点就是时延较大，并且信息传输成功的概率较低。Frenkiel R.H.和Badrinath B.R.提出了一种基于一跳传输的感染机制，利用这种方法可以增加无线网络的信息传输量，并且降低传输开销。在ad hoc网络中使用一跳传输策略，节点的移动性会增加传输能力。

1.2 基于概率（历史预测）的路由算法

基于历史预测策略的路由算法是为了克服基于复制策略中消息复制的盲目性而提出的，通过消息历史传输的成功概率进行估算和比较，选择到达目的节点概率更高的中继节点。通过这种有选择性的复制消息，避免生成低效传输的消息副本，提高网络的资源利用率。基于概率（历史预测）的复制策略又可分为基于一跳和基于端到端两种。

1.2.1 基于一跳的复制策略

1）PROPHET 路由算法

PROPHET（Probabilistic Routing Protocol Using History of Encounters and Transitivity）路由算法是基于历史预测策略的典型代表，利用节点间的相遇的历史信息和传递性来选择下一跳节点。该算法定义一个称之为投递预测值（Delivery Predictability）的指标来描述节点之间成功传输消息的概率。与传染病路由算法相比，每当两个节点A和B相遇时，除了要交换向量，还需要交换投递预测值只有当B到达目的节点的投递预测值大于A时，A才向B复制消息。

2）CAR路由算法

CAR （Context-aware Adaptive Routing）是一种混合式路由算法，该算法根据传输可能性选择中间转发节点。其中传输可能性由节点通过环境信息（Context Information）合成，包括节点连通性变化的频率和当前节点能量等因素。当源节点和目的节点之间存在端到端路径时，该算法使用同步路由转发数据，但若网络中无端到端路径，则选择使用异步路由来传输数据。为了能准确有效地估计和更新路由表中的传输可能性，该算法使用滤波技术预测节点的环境信息变化。

1.2.2 基于端到端的复制策略

1）MV路由算法

MV（Meetings and Visits）则利用节点间的相遇概率来描述消息传输的成功概率，任意两个节点间的相遇概率作为这对节点的传输概率，在此基础上通过递归的方式计算多跳传输的成功概率。两个节点相遇时，交换各自的消息以及传输概率信息，通过比较，节点仅向传输概率更高的中继节点复制消息。与基于复制策略的路由算法相比，基于历史预测策略的路由算法由于在选择中继节点时更有目标性和针对性，因此可以取得更高的消息投递率和网络资源利用率。

2）ORWAR路由算法

ORWAR （OpportunisticRoutingwith Window-Aware Replication）路由协议算法，其主要目标是减少资源消耗以及降低传输时的信息丢失率，减少零散的消息片段。当节点移动到传输范围之外时，若此时传输操作仍在进行着，零散消息片段的数目就会增加。ORWAR计算了每次连接能够被传输的数据总字节数，该做法有利于更有效的利用有限的带宽。然而为了在网络系统中部署ORWAR路由算法，每个节点都需要具有测量传递速度以及传递方向的能力，该方法目前只有在设备配有GPS系统时，才具有可行性。

1.3 基于调度（优先级）的路由算法

该算法最核心的思想是对束赋予优先级，并按照优先级的高低择优传递信息。该算法需要使用针对传输和删除操作的优先级函数。在洪泛传递信息时，该算法使用一些参数来对信息的优先级进行评估。其中某些参数用于评估信息从当前节点传送到目的节点的开销等。

1）基于优先级的传染病路由算法 （Prioritized epidemic routing）

该算法的核心思想是给每一个叫做“束”（bundle）的信息指派一个优先级。对信息的传输和删除操作是由优先级函数控制的。信息的洪泛策略是基于估计信息的优先级而进行的，某些参数被用于评估从当前节点到目的节点的开销，或是连接的出现和消失的时间等。相比传统的传染病路由算法，该算法能够结合网络中的拓扑知识信息，更合理有效的利用网络中有限的资源，缺点是由于引入了优先级函数，增大了每个节点的计算开销。

2）MaxProp 算法

在使用该策略的情境下，网络中的节点往往是城市中的公交车，它们具有较高的相遇概率，故在实施算法的过程中，城市的环境也被纳入考虑范围之内。MaxProp算法通过交换信息来获知节点的未来行为，并利用总的开销来筛选到目的节点的最优路径。MaxProp算法将缓冲操作分为两部分，在第一阶段中，算法会基于信息经过的节点跳数，将其从跳数少到跳数多增序排序。第二阶段是将信息按照开销从高到低排序。缓冲区资源在使用中，两方面都要纳入考虑。

1.4 基于编码的路由算法

基于擦除码（Eraser Code）的路由算法也可以认为是基于复制策略的一种，它基于这样的原理：源节点对消息进行分块，然后这些分块以某个大于1的常数因子进行复制转发，当目的节点收到这些分块中的一定比例时即可重构源消息。

基于网络编码（Network Coding）的路由算法。该算法在基于概率的路由算法的基础上，引入线性网络编码技术来降低算法的代价。仿真实验结果表明，在一个稀疏部署的移动网络中，特别是在节点具有较高的丢包率时，引入网络编码技术以后，路由算法的性能提升尤为明显。

2 路由算法策略比较

在复制策略中，大量的相同信息的拷贝将被创建，这些拷贝将会被传输给中继结点。中继节点接受这些拷贝，并将其存储在自身的缓存中。当这些中继节点和目标节点建立连接时，拷贝才会被传输到目的结点，并且中继节点将传送过去的信息的缓存清空。在DTN早期的算法研究工作中，这种策略经常被路由算法的设计者和研究者们使用。在某些移动传感网络中，节点的移动具有随机性，此时，这种路由策略往往能够有效的利用结点本身的这种随机移动性，从而有效的将信息传送到目的节点。信息的大量复制是增加传输成功概率的有效手段，使用这些协议并不需要预先获知任何关于整个网络的连接状态或知识。本文重点比较基于洪泛和基于编码的路由策略。

基于洪泛策略的路由算法实现起来较为简单，该类算法的优点是：1）不需依赖对链路状态的估计；2）若节点的资源充足，则该种策略下的路由算法可以较为快速的实现信息的传递与转发，从而减小传输的时延，以及消息传递成功的概率。该类算法的缺点是：节点之间在传输报文时，拥有大量的冗余报文，增加了网络传输负载。

基于编码的方法，一般是将信息在源节点分块，待其传输到目的节点，再将其重组。其优点是：提高了系统传输吞吐量。与基于其他3种策略的路由算法相比较，基于该策略的路由算法在网络负载相同的情况下具有较低的传输时延。由于分组和编码，在一定程度上有助于在网络拥塞的情况下抗击丢包。缺点是：编解码操作会带来一定的能量消耗。编解码操作较为复杂。信息块的拆分策略，目前无较好方案。

3 结束语

通过对容迟网络路由算法相关的文献，特别是近几年来的主要研究成果进行研究总结发现目前的路由协议缺乏多项评估指标的综合考虑，往往在个别指标上性能优越，但无法优化多项指标，网络整体性能难以获得极大的提升。因此需要利用新的分析工具研究容迟网络路由，同时考虑多个设计目标进行优化，建立基于多目标优化的高效路由协议.例如，以节点能量消耗、时延、传输率为目标，进行多目标决策，设计出最优路由协议。

[1]张龙，周贤伟，王建萍，等.容迟与容断网络中的路由协议[J].软件学报，2010，21（10）:2554-2572.

ZHANG Long，ZHOU Xian-wei，WANG Jian-ping，etal.Routing protocols for delay and disruption tolerant networks[J].Journal of Software，2010，21（10）:2554-2572.

[2]Vahdat A，Becker D.Epidemic routing for partially-connected AdHoc networks[R].Duke University，Tech.Rep.:CS-2000-06，2000.

[3]Groenevelt R，Nain P，Koole G.The message delay in mobile ad hoc networks[J].Elsevier Journal of Perform-ance Evaluation，2005，62（1-4）:210-228.

[4]Jain S，Demmer M，Patra R，et al.Using redundancy to cope with failures in a delay tolerant networks[C]//In:Proc.of the ACM SICOMM 2005，2005:109-120.

[5]周晓波，卢汉成，李津生，等.AED:一种用于DTN的增强型Earliest-Delivery算法[J].电子与信息学报，2007，29（8）:1687-1694.

ZHOU Xiao-bo，LU Han-cheng，LI Jin-sheng，et al.AED:advanced earliest-delivery algorithm used in DTN[J].Journal of Electronics&InformationTechnology，2007，29（8）:1687-1694.

[6]Lindgren A.Probabilistic routing in intermittently connected networks[J].Mobile Computing and Communications Review，2003，7（3）:19-26.

[7]刘舒拉.基于博弈论的无线传感器网络路由算法研究[J].现代电子技术，2011（9）：45-47.

LIU Shu-la.Game-theory based routing algorithms for wireless sensor network[J].Modern Electronics Technique，2011（9）：45-47.

[8]杨眉，李忠科，王忠.基于OWL-S语义栅格运动目标信息快速分发技术[J].电子科技，2012（7）：6-9，14.

YANG Mei，LI Zhong-ke，WANG Zhong.The research on rapidly distribution of moving target information based on OWL-S semantic grid[J].Electronic Science and Technology，2012（7）：6-9，14.