容延容断网络路由技术

ISSN 1000-9825，CODEN RUXUEW Journal ofSoftware，Vo1．21，No．1，January 2010，PP．119—132 doi：10．3724／SP．J．10O1．2O10．03689 ◎by Institute ofSoftware．the Chinese Academy ofSciences．All rights reserved 容延容断网络路由技术 苏金树，胡乔林 ，赵宝康，彭 伟 (国防科学技术大学 计算机学院，湖南 长沙 410073) Routing Techniques on Delay／Disruption Tolerant Networks SU Jin—Shu， HU Qiao-Lin ， ZHAO Bao—Kang， PENG Wei (School ofComputer，National University ofDefense Technology，Changsha 410073，China) +Corresponding author：E—mail：huqiaolin@nudt．edu．cn．http：／／www．nudt．edu．cn E-mail：jos@iseas．ac．cn http：／／www．jos org．ca Tel／Fax：+86．．10．．62562563 su JS，Hu QL，Zhao BK，Peng W．Routing techniques Oil delay／disrupti0n tolerant networks．Journal of Software，2010，21(1)：119—132．http：／／www．jos．org．on／1000—9825／3689．htm Abstract： In the recent years，as a new emerging network architecture，Delay~Disruption Tolerant Networks (DTNs)have received extensive attention and are widely investigated．Since the major application scenarios of DTN are extremely particular routing protocols designed for the traditional networks are not suitable for DTN ． Therefore，numerous routing protocols have been proposed for DTN．In this paper,the formulation issues of DTN routing protocols are firstly studied，and the classification concerns are then proposed for those protocols．Thereafter ， this paper focuses on analyzing and comparing existing representative DTN routing protocols ． Finally,current research status and the existing problems about DTN routing protocols are summarized，the key issues and future trends in DTN routing are pointed out． Key words： delay／disruption tolerant network；network architecture；routing protocol；routing mechanism 摘 要： 作为一种新型的体 系结构，容延容断网-~-(delay／disruption tolerant network，简称 DTN)~年来得到了广泛 的研究与应用．由于其面·J告的应用环境极为特殊，传统网络的路由无法适用于 DTN，各种针对 DTN 的路由技术 相继提了出来．在对 DTN路由进行形式化分析以后，提出了路由技术的分类，然后着重分析并比较了当前一些 较为重要的路由技术的核心路由机制和特点．最后总结DTN路由技术的研究现状以及存在的问题，指出未来路由研 究 的重点． 关键词： 容延／容断网络：网络体系结构：路由协议：路由机制 中图法分类号：TP393 文献标识码：A TCP／IP协议栈为 Internet的巨大成功发挥了基础性的关键作用．IP协议很好地屏蔽 了网络异构性，但同 时，TCP／IP对于底层传输协议也存在许多的假设 ， ．例如：收发节点之间必须存在持续的端到端的路径：任意收 发节点对之间的 RTT较小且相对一致；通信链路误码率及丢包率低；应用程序无须考虑通信性能等等．然而，近 ·Supported by the National Natural Science Foundation of China under Grant No．90604006(国家自然科学基金)；the National High-Tech Research and Development Plan of China under Grant No．2008AA01A325(国家高技术研究发展计划(863))；the National Basic Research Program ofChina under Grant No．2009CB320503(国家重点基础研究发展计；~1J(973)1 Received 2009·-03-·02；Accepted 2009-07．-07 120 Journal ofSoftware软件学报 Vo1．21，No．1，January 2010 年来许多新兴网络无法满足以上假设条件，包括野生动物监测传感网络l3】、移动车载网(VANET) J、星际网络 fIPN)[ 、战术通信网[ 、口袋交换网[ 、水下传感器网【 、空间光通信网[ 、乡村通信网络f10]等新型网络不断 涌现出来，这些网络中可能由于节点稀疏、高速移动性、交替活跃，或者出于安全原因而实施无线电静默⋯J，或 者遭受恶意攻击等造成 网络问歇性的连接．这些网络具备非常鲜明的特点：在路径和链路特征上具有高延迟、 低数据率，可能不存在稳定的端到端的连接；在网络体系结构上缺乏交互性；端系统资源有限，寿命有限，低 占空 比操作，因此，这类网络通常也被称为“挑战网络(challenged networks)”lJ ． TCP／IP协议在这种“挑战网络”环境中的性能会出现急剧恶化，导致传统的BGP,OSPF等路 由协议无法正常 运行f"]．Ad Hoc网络路由仍然遵循“存在完整的端到端路径”的假设，AOD DSR等路由协议也难以应用于“挑 战网络”中．对于反应式路由协议，由于节点移动减少了路径持续时间，其吞吐率接近于 0ll制．即使对以上协议进 行修改也难以从根本上解决以上问题．为此，IRTF在星际网~(IPNRG) 】的基础上成立了“容延网络研究组 (Delay Tolerant Network Research Group)”【 j，DARPA也提出了容断网络(disruption tolerant network)⋯J，侧重解 决通信链路频繁中断情况下网络的通信问题，消除由于信道受到干扰、屏蔽等引起的消息丢失，将其作为其 GIG 的重要组成部分．本文将以上网络都简称为 DTN(delay／disruption tolerant network)．同时值得注意的是，未来随 着移动计算的普及，通过 WIFI，802．11等访问 Intemet，连接间断也可能是一种正常现象，下一代互联网络必须考 虑对网络新技术的支持I】 ．Clark认为，需要对现有的“高带宽延迟”网络进行补充【l7】．近年来，DTN 也引起了 Sigcomm，Infocom，Mobicom等重要会议的关注．2007年，NASA决定正式采用容延／容断网络(DTN)作为“用于间 断连通网络传送数据的新协议”．在美国网络与信息技术研发计划 NITRD[”】中明确指出，NSF，NSA，DARPA， OSD，NASA 等机构将对 DTN 网络进行资助，以开发相关协议和算法．然而，目前我国对于 DTN 网络的研究还 较少． 目前，国际上对于 DTN 的研究主要集中于体系结构、路 由、拥塞控制、安全隐私、应用支持等问题，而 DTN网络的特点使得传统有线网络和 Ad Hoc网络路 由协议不能有效地应用于 DTN，DTN网络路由技术成为 其中的重点与热点[191，研究人员努力提出适合于各种 DTN应用场景下的路由协议．本文对 DTN网络路由进行 了形式化分析并加以分类，详细分析了当前主要路由技术的特点以及核心机制，指出了未来的研究机制与发展 趋势，为 DTN路由协议的进一步研究提供参考． 1 DTN路由相关术语 DTN体系结构上放松了 TCP／IP的假设条件，使其能够容忍中断以及长延迟，并互联异构网络．DTN通过在 传输层上叠加了 Bundle层形成了一种重叠网体系结构[1,20,21】．路由机制上采取了“存储一携带一转发”或“存储一等 待一转发”的模式，也因此引入了一些特定的术语和机制 (1)束(bundle)[211：Bundle有时也称为消息，是 DTN中的基本数据单元，长度可变．Bundle叠加于传输层之上， 如图 1所示．Bundle从体系结构上表现出汇聚层适配器的作用，其次，Bundle的消息转发实际上是实现多个报文 存储聚合并进行传输，以降低对端到端连接的需求，数据在传输过程中能够存储在各 DTN 节点中，当连接断开 的时候，Bundle仅需要从邻近的存储节点进行传输，通常使用逐跳确认机制来保证可靠性与安全性． (2)接触(contact)：contact表示一次通信机会，即两个节点之间存在一条可以通信的连接．将 DTN 网络表示 为有向图 G=( )，接触可以用四元组(8，t，c， 表示，其中，eEVxv,t表示为边 e上能够用于传输数据 的时间问隔，c 为非负实数，表示边e的容量，d表示边e上的传输延迟．在实际网络中，t是有限变量，如果te(0，o。)且连续，则称其 为持久连接；如果 ，离散但却表现出一定的周期性，则称其为可预测间歇性连接：如果 ，完全随机，则称其为机会 主义连接． (3)保管传输L2 (custody transfer)：DTN网络中的部分节点具有持久存储器，保管传输的语义是指从发送者 到接收者的这条路径上，将可靠传输的责任逐跳地递交到下一个节点．即当消息从节点 A传递到节点 时，节点 必须确保将消息传递到 目标节点或者消息超时丢弃，或者将保管传输的责任委托给下一个节点 c，否则不能 删除该消息．使用保管传输机制的同时给 DTN路由也带来了特殊的挑战，即有限存储资源的管理和使用． 苏金树 等：容延容断网络路由技术 121 APPs I ▲ APPs 强蠹簿l 、 ＼麓蘩强 甏强萋 矗 臻曩 -＼跨 鬣 ； 鬻l |嚣 簇蠹强 §j t | | | | l 蚓 | de ≮ ∞蠹 |骛 幽≤ m 臻E簿r≯嘲 吣、鏊萎＼ 臻 鬣≈ 馨霪 鬣强鬻簿臻§ 、 呲鞲§l TCPuDPI Storage i TCPUDPl Tc UDP I I l l T {po“ yc Tf po州aye P l - ● Net、善。rk 1fdyer jetwork I y。 I P l }P MAC l I MAC I - Li~k layer ILink laver MAC l I I { PHY I l PHY l PIIY Phy~cal1ayer I]hysica1 1ayer I I D DTN outer l DTN gatewa厂一 一 r DTNhost Region A (TCP／IP region) 2 DTN路由形式化与分类 Region B (Non TCP／IP region) Fig．1 DTN transfer and bundle layer 图 1 DTN传输和束层 形式化是 DTN路由研究的重要基础，一些研究人员对此进行了一定的探索，包括使用 自动机理论【2 、演化 图[24,25]、概率图I26]等．对于 DTN形式化而言，其最大的挑战来 自于链路连接、数据传输速率等都会随着时间变 化的特征．因此，需要对传统的图论进行扩展，增加时间维度，将 DTN 网络表示为与时间相关的网络． 定义 1．时间相关网络．DTN网络拓扑可能随着时间而发生变化，其拓扑表示为 G(f)=( )， f))，其中， 分 别表示网络节点和边，t为非负时问变量，E(f)={(“，v)：“，v∈ f)，R(u，v)在时间段t能够通信}．如果Vt1，t2，G(t1)=G(f2)， 则该网络称为完全连接静态网络；如果3T使得 G( 1)一G( 2)，其中， [f1， ]，则 G( 为不稳定连接 网络．此时，网络中 节点对在某个时间段仍然存在一条端到端的路径． 定义2．时间演化网络．给定时间相关网络 G( )以及时间序列 其中，T=to， ⋯．， 不影响语义的情况下，使用 0，1，．．．， 表示时间序列)，ti表示将时间离散化后的时间段，即ti=[f ，相，且任意的f ≥ff_l，随着时间序列 T动态添加、 删除边 g，此时，边E是时间t的函数，从而可以产生子拓扑图序列 Gs 6=Gl，G2⋯．，Gb如果【J =G(f)，则称 EG(f)=(G( ，G ，7)为动态演化网络，其中，EE。=U Ei， =U ， ．该类型网络进一步放松了连接性的限制，即 网络中任意节点对之间可能并不存在一条完整的端到端路径，这也是一般 DTN网络的表现形式． 定义 3．时间路径．对于时间演化网络 EG(f)，由于链路的间歇性连接，造成传统的路由机制不可用，但这并不 代表消息在这种间歇性连接环境下永远不能进行数据分发．随着时间的推移，不同的链路连接 、断开，如果这种 连接子图序列互相重叠，那么节点对之间可能存在“时问上的路径”．将任意节点对 “，v之间的路径path(u，v)表示 为有序三元组序列 path(u，v) (( ， 1，t1)， l，X2，f2)，⋯， ，v，f )，其中，XieM,tf< 表示时间不能回退． f，x川，t川)表示 节点而与x川在时间段 tf+】接触，序列中每个元组表示一跳，其路径长度为该序列总跳数．对于任意的源节点 和 目的节点 d，消息成功路由的条件为：从起始时刻 t1开始，存在序Y0((s， t)， 1， 2，t2)，．．．， f，d， )，f ．此时，DTN 网络采取“存储．携带．转发”或“存储．等待．转发”的模式可 以将消息传输到目的节点． 定义 4．路由机制．传统网络路由难以适用于 DTN，DTN 路由通常采用消息复制、先验知识、网络编码、 概率估计等机制． 定义 5．路由目标．与传统 Intemet以最小跳数、最短路径为路 由目标不同，DTN中不同的应用场景可能具 有不同的目标，主要有最小化传输延迟、最大化消息分发概率以及最小化缓冲、网络带宽和能量消耗等目标． 定义 6．路 由算法：在给定 s,d，t 的情况下，根据路 由目标的要求选择路 由机制，DTN路由算法求解可行的时 问路径，并且按照路由目标找出最佳路径，比如最小延迟路径．j艮明显，由于在某些 DTN 环境中难以获得完整的 拓扑子序列，甚至在有些环境下是不可能的，造成找到这样的一条“时间路径”实际上是困难的，DTN路由通常存 122 Journal of Software软件学报 Vo1．21，No．1，January 2010 在不精确性．文献[231E明，在 DTN中，即使不存在端到端路径，无先验知识、采用多消息副本机制的情况下也能 够进行数据传输：同时也能够在具有先验知识、采用单副本的情况下进行数据传输． 由于当前 DTN 网络的特征各不相同，其 DTN路由目标、路由机制等也各不相同，因此，目前尚无统一的分 类方式．根据上面的形式化分析，可以根据 DTN网络结构特征、路由目标和路由机制等方法进行分类： (1)按照 DTN 网络中所有节点是否同构，DTN路由可 以分为基础设施辅助的路由以及无基础设施的路由 技术．具有基础设施辅助路由主要是为了对 DTN恶劣环境予以缓解、补偿，通过部署特定的固定、移动基础设 施以增强网络的连接特性，从而辅助路由：无基础设施的路由通常认为网络中所有节点均为同构的； (2)根据不同的路由优化 目标，还可以分为最小延迟、最大化数据分发概率的路由协议等； f3)根据路由机制中是否使用先验知识，可以分为具有先验知识确定性的、基于模型的、无先验知识的机 会主义路由算法．使用先验知识的确定性路由主要利用确定的连接信息、移动模式、流量模式等做出路由决策； 基于模型的路 由主要是基于移动模型、社会网络模型，以增强路 由性能；对于难 以获得先验知识，其网络连接呈 现出机会主义特征，最直接的路由算法包括直接传输和传染模式．为了在这两种极端的情景下对延迟以及资源 消耗加以折衷，主要采取的方法是控制洪泛、基于历史信息、基于效用等方法； (4)根据路由机制中特定消息在网络中存在的副本数量，可以分为单副本和多副本路 由．在单副本路由中， 在任何给定时问点，网络中仅有～个节点携带该消息副本，携带该消息副本的节点称为“保管节点”．当前“保管 节点”将消息副本转发到合适的下一跳，其下一跳节点将成为“保管节点”，最终消息将传输到目的节点．多副本 路由技术即对于同一个消息进行复制产生多个副本，并且每个副本将独立地进行转发决策，以降低延迟； (5)根据路由是否采用编码，分为基于编码的路 由与非编码的路由．严格说来，基于纠删码、网络编码并不能 称为路由技术，而主要是为了增强数据传输的可靠性、健壮性． 在实际的 DTN路 由研究与应用中，由于 DTN面临的环境恶劣，为了提高数据传输概率或者其他路由目标， 许多路由技术同时使用了上述多种机制，比如同时利用先验知识、多副本等方法．第 3节将按照如图 2所示的 分类框架分析当前主要的单播路由技术． Fig．2 Taxonomy of routing techniques for DTN 图 2 DTN路由技术分类 3 DTN的主要路由技术分析 通过对当前 DTN路由技术的研究，本文按照图 2所示的分类方法选取了其中较为重要的一些单播路由技 术，对其特点、核心路 由机制进行了分析． 3．1基础设施辅助路由 通过在 DTN 网络中增加特殊的受控节点或者改变受控节点的移动轨迹，可以改善网络延迟、网络容量等 性能，这种方法一定程度地利用了先验知识． Burns等人[27,28]考虑 了一种假设状况，在普通网络节点的移动不能满足性能需求的时候，引入移动 Agent作 为 DTN 网络的额外参与者．提出了根据网络带宽、延迟等多目标要求对 Agent的移动进行控制，以优化 DTN 网络的性能．Baneoee等人则了一种用于 DTN网络 中的特殊节点 Throwboxes[29,301，该节点具有远程邻居发 苏金树 等：容延容断网络路由技术 123 现和数据传输两层结构，通过在移动 DTN网络的热点区域中部署静态的 Throwboxes，为 DTN节点对之间创造 更多的接触通信机会，以降低网络延迟． 与Burns等人的工作类似，Zhao等人【 】提出消息摆渡路由MF(message ferrying)方法，MF使用了称为摆渡 节点的可控特殊移动节点，摆渡节点部署在特定的区域并且负责普通节点之间的消息传输，节点和摆渡节点均 可以发起先验式的移动请求，在节点发起消息摆渡请求的 NIMF(node．initiated MF)路由框架中，摆渡节点按照 预定的路由线路移动并与其他节点接触，由于节点具有摆渡节点先验知识，当节点有消息传递时可以主动接近 摆渡节点的线路，从而将消息传递给摆渡节点，节点的轨迹控制机制决定 了它主动地与摆渡节点进行通信的时 间．在摆渡节点发起的消息摆渡请求框架 FIMF(ferry．initiated MF)中，当节点需要接收或者发送消息时，普通节 点通过长距离无线电向摆渡节点发送服务请求，摆渡节点将根据服务请求主动改变其移动轨迹，进入普通节点 的短距离无线通信范围以进行消息交换．通过使用 NIMF和FIMF,节点之间能够通过摆渡节点中继而进行远距 离消息传输． Zhao等人I弛】对使用单个摆渡节点的 MF方法进行扩展，提出了使用多个摆渡节点在静态网络中进行路由． 在静态网络仅使用 m(m>1)个摆渡节点的场景中，其路由设计实质上等价于 TSP问题．其近似求解算法框架分为 3个阶段：在第 1阶段中，每个普通节点将被分配给某个特定摆渡节点，该摆渡节点将会负责这个普通节点的消 息传输任务：在第 2个阶段中，每个摆渡节点将会基于所负责的节点的位置和流量负载信息计算其摆渡路线．在 前两个阶段中，算法主要集中于最小化延迟需求；在第 3阶段中，调整摆渡路线，使其满足带宽需求．Zhao等人提 出了4种摆渡路由算法，即单路 由算法 SIRA(single．route algorithm)、多路由算法 MURA(multi．route algorithm)、 节点中继算法 NRA(node relaying algorithm)、摆渡节点中继算法 FRa(ferry relaying algorithm)．通过模拟发 现，MURA能够取得最好的性能，而 FRA性能最差． 由于消息摆渡的方法假定普通节点是静态的或者节点之 间预先知道对方的移动模式，并且通常还需要长 距离无线通信系统，然而在节点随机移动的网络中，上述假设不成立，为此，Muhammad等人针对普通节点与摆渡 节点之间的无法协作的场景，提出了优化路线点的路由方法 OPWP(optimizedway—points)[ ]．设二维空间为 ，路 线点候选集合为 C，摆渡节点选择的路线点集合为 R， { ，seR}表示摆渡节点在对应的路线点集合等待时 间，y，表示摆渡节点的移动速度，r表示普通节点和摆渡节点的通信距离，则 ，W,vr,r}将指定摆渡节点的路由 线路，其路由问题转变成为求解有序点集合的问题，以满足摆渡节点与普通节点的接触概率闽值，并最小化摆渡 节点的等待时问之和． 3．2 先验知识路由 在诸如深空通信 的卫星网络、具有确定调度的车载网络中，节点可以具有网络所有先验知识，比如节点缓 冲队列大小、确定性移动模式等．利用这些知识，将很大程度地提 高路 由协议的性 能．这类路由技术的主要思想 是将影响协议、网络拓扑的时间相关因素转化，进而利用经典的路由算法． Jain等人p 4l最早提出了基于先验知识的单副本路由算法，并且考虑了具有不同知识级别的单播路 由协议． 将消息定义为四元组(src，dst，time，size)，分别表示为源、 目的节点、消息产生时间、消息大小，它可利用的知识 包括链路连接信息统计、节点之间连接信息、每个节点缓冲队列 占用信息、通信需求信息，从而将路由问题归 结为多重货物流的问题，路由目标就是为所有的消息计算最小延迟路径．利用连接统计信息提出了最小期望延 迟算法 MED(minimum expected delay)，算法将链路平均延迟作为链路上开销，使用了修改的 Dijkstra’S算法求 解；通过利用节点之间的连接信息，提 出了最早分发算法 ED(earliest delivery)，其链路开销是基于等待时间的时 变开销，同样利用了Dijkstra’S算法的变种求解；通过利用节点队列 以及节点之间的链路信息，提出了基于全局队 列的最早分发算法 EDAQ(earliest delivery with all queue)；~N果综合利用全部的信息，则其路由可以表示为 LP(1inear program)线性求解．通过理论分析以及模拟实验表明，所应用的先验信息越多，其路由效率也越高． Merugu等人认为难 以获取 Jain 所假设的信息，提 出了一种在节 点移动模式确定情况下的空时图[35] (space—time graph)路由框架．与传统的基于下一跳的路由表不同，空时图路由通过增加时间维度构造空时 (space—time)路 由表，路 由表中记录了目标地址以及消息到达时间点的下一跳，从该路 由表可以选择下一跳和未 124 Journal ofSoftware软件学报 Vo1．21，No．1，January 2010 来的邻居，如图 3所示．然后构造如图 4所示的空时图，从而将时变网络转换成为经典的“静态网络”问题，并利用 动态规划和类似于 Dijkstra’S最短路径的算法求解节点对之间的最短路径，即最小化端到端的消息分发延迟． Destination Forwarding table n0de O 卜 l t Carty1 Carty 0 Forward H Forward H Fig．3 Space—Time routing table 图 3 空时路由表 n ^ n ^ fl fl 』【vj ．Time』1 J I J|，f{ J 1 ⋯ f 1 f } i f { 『 #目 二二 脚 ．_— f 】f f Spacell !J f d 。 。 ‘ Fig．4 Shortest path from v1 to Vk in space—time graph 图 4 空时图中 v 到 Vk的最短路径 类似于空时图路由，Fischer[ 】针对可预知的移动性将时间维度进行离散化，即认为时变网络中的一个特定 时间间隔 明内网络拓扑是静态的，并以一个拓扑快照 Si=(tf，Gi)来表示，其中tf表示时间段，G 表示在时间段 ti 的网络连通图，从而整个网络的拓扑可以表示为一个静态的网络拓扑快照序列 (So ．)，通过拓扑信息管理协 议，使得每个节点存储并且维护一个网络拓扑快照序列．这个拓扑快照序列类似于 OSPF(open shortest path first) 中的链路状态 LSDB(1ink．state database)，在此基础上，提出了一种基于链路状态的路由协议的PLSR(predictable link—state routing)． 3．3 基于模型的路由 虽然绝大多数 DTN 网络先验知识难 以获得，然而有些 DTN 网络中节点移动、接触具有一定的规律性，比 如节点移动可能服从移动模型、社会模型等，利用这些不精确的规律进行辅助路由，也能提高路由性能． Leguay等人提出了 MobySpace[37,38J~由框架，利用节点的移动模型构造高维的欧氏空间，比如提取移动模 式的特征，利用关于节点之间接触的历史信息，其接触集合形成一个高维度的虚拟空间，而每个接触都表示为多 维空间的一个轴．如果两个节点具有相似的接触集合以及相似的接触频率，那么这两个节点将会在欧氏空间中 距离较近：如果节点之问具有相同的接触集合但其频率不同，那么在空间上相对较远．同样，如果节点访问特定 的位置能够被追踪，那么移动模式能够描述为节点访问特定位置的频率，在此场景中，每个轴表示一个位置，轴 上的距离表示在该位置找到某节点的概率．如果两个节点以相同的概率访问相同的位置，那么这两个节点最有 可能互相接触．MobySpace能够将特定的移动模式映射到欧氏宅间，消息 以多跳方式传输到与 目标节点欧氏距 离更小的中继节点，直至消息传输完成． Liu等人提出了RCM(routing in Cclic MobiSpace)t 1的路由算法，该算法主要基于这样的发现：许多DTN网 络中的节点移动具有一定的循环模式，这表明，如果两个节点在上一个循环中的某时问段接触，那么在下一个循 环中相同时间段再次接触的概率将会很高．这种循环移动可以模型化为概率时间一空间图．将时间维离散化以 后，消除了时间维度，从而将概率时间一空间图转换成为概率状态空间图，从而可以利用马尔可夫决策过程计算 节点之间的期望最小延迟EMD(expected minimum delay)．RCM算法更加细粒度地利用循环移动的特征，更为准 确地估计节点之间的分发延迟，以较小的资源消耗获得了较好的性能． Brendan等人提出了 MV(meetings and visits)[ 路由算法，MV通过学习节点的移动模式，即节点之间的接 触概率以及节点访问特定地点的概率，以辅助路由和缓冲资源分配．MV 路由将消息发送给具有更高分发概率 的节点．Burgess等人对MV路由算法进行扩展，提出了MaxProp[ 。】路由算法，利用路径历史信息对消息按照优先 级排序转发消息，并且在网络内泛洪 ACK(acknowledgement) 移除网络中过时的信息．模拟结果表明，该方法能 够提高消息分发概率． 同时，研究人员也发现许多DTN网络的接触模型与社会网络模型具有一定的相似性．Paolo等人针对 DTN 中发布／订阅模式的应用，提出了 SocialCast[ 路由框架，主要是利用社会网络模型和对移动模型的观察进行预 测以识别最佳的中继．该路 由基于这样一个现实：如果节点属于同一个组织，则可能会互相移动到很远，然而经 苏金树 等：容延容断网络路由技术 125 过很长的时间，断开以后，最终会再次相遇，这个特征可用于基于兴趣的路由决策过程中．SocialCast路由主要分 为兴趣分发、中继选择 、消息发布 3个阶段．在兴趣分发阶段，每个节点向自己的 1跳内邻居广播其兴趣；在中 继选择阶段，通过卡尔曼滤波的方法计算节点对特定兴趣的效用值，并选择最大效用值的节点作为中继；在消息 分 发阶段，针 对订 阅以及效用 函数再 次评估消 息 内容，消息将 转发到兴 趣节 点或者最佳 的 中继节 点．同 样，SimBet路由[ ]同样也使用社会网络分析技术在 DTN 网络中转发消息，该路由利用了社会网络中呈现出小 世界现象，一些节点由于其连通度较高，从而可 以当作“桥节点”以辅助路由．Pan等人提出了基于社会 网络的 BUBBLE[ 】路由算法，该算法主要利用社会 网络 中的团体性和集中性现象，源节点首先根据全局等级信息将消 息发送到具有更高集中度的节点，直到该节点与 目标节点又属于同一团体，在同一团体内部再根据本地等级信 息将消息转发到 目标节点． 3．4 机会主义路 由 部分 DTN网络中其节点移动不可预测、调度信息无法预知等，呈现出机会主义的特征，造成难 以决定到达 目标节点的路径．在这种网络环境下，最直接的路由机制包括直接传输、传染路 由，同时还采取 了多种方法对这 两种极端情景下的延迟以及存储、带宽资源消耗加以折衷． 3．4．1 直接传输与传染路由 直接传输是指源节点或者移动某个中继节点携带消息，直到进入 目的节点的通信范围．比如 Data Mulel4引， 这种路 由降低了类似泛洪的路由算法带来的大量的资源需求，然而 由于没有充分利用网络的连接机会，从而带 来了非常大的端到端延迟． Vahdat等人提出了传染路~h(epidemic routing)[ ，即每个节点不进行路 由决策，而将消息泛洪给 自己所有 的邻居节点．其具体工作原理如下：网络 中产生的每一个消息都以节点标识符键值进行哈希后存储，并维护摘要 矢量 SV(summary vector)以标识哈希表中的每一项的“有”或“无”．当节点 ， 进入通信范围连接以后，数据通信 过程由 3个阶段完成：(1)节点 向 发送 自己的 ；(2)B收到 后与 自己维护的 SV8进行 比较，并判断哪 些数据未被 自己存储，并且发送 + 给 ；(3)A根据请求发送数据给 ．实验结果表明，如果所有的节点都 能够充分移动，传染路 由能够几乎将所有的数据都正确分发，从而克服传统路 由协议 由于有限的连通性而不能 分发任何消息的缺点．由于传染路由穷举 了所有的可能的传输路径，能够保证在带宽、缓冲空问没有竞争的情 况下找到最短的路径，但是消耗资源严重，而且在现实的场景中，能量、带宽、缓冲等资源可能缺乏而造成资源 竞争，传染路由性能会严重降级． Small等人提出了共享信息基站模型 SWIM(shared wireless infostation mode1) ，SWIM 是用以收集鲸鱼 信息的移动传感器网络，该模型也使用了传染路由算法，与传染路由的区别仅在于任意一个基站都可以作为 目 标节点，而传染路 由中对于给定的报文仅有一个 目标节点．SWIM 允许将消息扩散到整个网络中的移动节点，因 此降低了延迟，但同时也增加了容量以及能量的资源消耗． 3．4．2 启发式路由 针对直接传输和传染路由的两种极端情况，许多研究人员提出了一些启发式算法，以在减少资源开销的同 时，提高传染路由算法的性能．这些方法可 以分为限制副本数量、基于历史信息、概率估计、预测 、效用等方 法，在利用这些启发信息进行转发决策的同时，会得到近似于传染路由的延迟，而资源消耗则大幅降低． Brenton等人提 出了一种简单计数协议路 由协议[ 】以限制消息副本数量．其基于这样一个现象：对于给定 消息的M 如果该消息携带比率较大，即含有消息 M 的节点 n与整个网络的节点数 Ⅳ比较接近，则 n的继续增大 实际上没有很明显的效果．对于包含消息 的中继节点维持两个计数器 和 ，分别表示估计包含消息 的节 点数量 、估计不包含消息 M 的节点数量．为 n 和 nd设定两个阂值 C和 D，如果节点发现 nc>e将对消息 M 进行 复制：如果 nd>_D，那么将会丢弃该消息．该协议降低了传染路由协议的开销，并且具有简单、健壮的特点． Erramillideng等人提出了委托转发(delegation forwarding)路 由【 】以限制消息副本数量．其基本思想是借鉴 了概率中的“雇员机制”，即如果需要从 Ⅳ个节点中选取一个最佳中继节点 ，可以采取对前 个节点进行观察， 从 M 中选择最佳节点 6的机制，理论上 b将会非常接近 口，同时较大幅度地降低了开销．通过对实际数据的分析 126 Journal ofSoftware软件学报 Vo1．21，No．1，January 2010 表明，该委托转发路由方法能够取得与其他路由协议近似的性能，同时降低了开销． zebraNet[3]是收集野生斑马信息的移动传感器网络，该系统提出了基于历史信息的路由方法，即以节点过 去成功的将消息直接传输到基站的概率作为路由决策的信息，具有高概率值的节点意味着节点更有可能将数 据传输到基站，当两个节点接触时，消息将传递给具有更高概率的节点． Jones等人通过观察节点之问接触的历史信息，使用消息到达下一跳估计需要等待的时间作为边度量标准， 从而提出了一种基于Epidemic的链路状态协议[ ．使用Epidemic方式以分发全局拓扑总结知识，对于消息的分 发仍然采用单副本的方法．然而，基于链路状态协议的不足之处在于每个节点必须存储整个网络拓扑路 由表，而 实际上综合多个节点上的拓扑信息非常复杂． PROPHET(probabilistic routing protocol using history of encounters and transitivity)[51]是一种基于概率估计 的路由，与传染路由盲 目地向所有邻居节点转发消息不同，概率路由中的每个节点将会估计到达 目的节点的概 率．PROPHET在每个节点a上为每个已知 目的节点b估计一个预测分发概率值 P 表示从节点a到节点b的 成功分发概率，当节点 口和 b接触的时候，根据公式更新其分发概率： )= a +(1一 )× 其他情况 ,b)oid 下按照 )= × 对 P(咖)进行衰减，其 中，PⅢ ∈[0，1]表示初始常量．所有 的 P( )初始化时都设置为 Pinit．rE[0，1]表示衰减因子，k表示节点a和b上一次接触以后所经过的时间．同时，节点之间预测分发概率值P( ) 也具有传递性，如果 a,b经常接触，而 b,c也经常接触，这就意味着如果将消息传递到 口，那么节点c将是一个好的 中继节点．此时， 将按照公式更新： )= ) +(1一 ) )× × )× ， 其中，脓 示传递性影响因子．但在一般情况下，该概率算法性能依赖于节点的移动模型，PROPHET在组移动模 型中性能较好． CAR(context—aware routing)[ 】是一种使用上下文信息进行预测的路 由协议，将同步和异步的报文分发机制 结合在一起．同步机制指的是，在到达 目的节点的端到端路径时，使用原有路由协议转发报文．当不存在端到端 路径时，节点通过综合上下文信息，比如主机位置、主机移动模式、能量等．假设节点上下文信息属性集合为 ， ，．．．， )，其中 表示该属性可能值的集合 是 的特定值．将这些属性联合得到其效用值 ( ，X2，．．．， )= 月 ∑U ( )，其中， 为属性 的效用函数，其效用函数采用卡尔曼滤波方法加以预测，并选取具有最大效用值的节 l=1 点作为候选节点，以增加消息成功分发概率． Spyropoulos提出了基于效用的、单副本路由决策协议，即“搜索聚焦(seek andfocus)”路由协议l5 咳协议假 设每个节点都维护一个定时器，用以记录上次接触以后的时间，这个时间值可以包含相对位置信息，通过当前信 息以及对未来连接的预测进行本地转发决策，并以此决定下一跳．首先，当前消息保管者 以一定的概率 ∈(O，1) 将消息传递给邻居节点，为了防止消息在两个节点之问反复震荡，限制其中一个节点接收到消息以后，在给定的 时间间隔内不允许将消息发送回上一跳，这种随机路由算法可 以高效地找到朝向目标节点的方向；然后，利用节 点定时器记录的相对位置信息，更小的定时器值意味着节点之间更小的距离．利用这些定时器定义效用函数以 指示一个节点将消息分发到其他节点的效用，从而建立基于梯度的路由框架，用 于将消息分发到目的节点，这个 框架将尝试最大化基于 目的的效用函数．令t(7)表示节点 f，，从上次接触以后所经过的时间，节点 i为其他节点维 护一个效用函数 (．)， (．)随着 (．)而递减．如果节点 产生一个到达 目的节点 D的消息，节点 成为 的中继 的充要条件是 )> (D)+ ，即消息需要传递到具有更高效用的节点． 基于效用的单副本的路由协议降低了资源的消耗，但带来了较大的延迟．在某些 DTN 网络中，最小化延迟 和最小化消息丢失率也是需要优先考虑的，Spyropoulos对搜索聚焦路由协议进行扩展，提出了两个限制副本数 量的多副本的喷射(spray) ]路由协议：喷射等待(spray and wait)$ll喷射聚焦(spray and focus)路由协议．喷射等 待路由协议将路 由过程分为喷射和等待两个阶段，喷射阶段实际上是一种基于 邻居的泛洪，源节点将 个消 息副本独立地分发给 三个中继节点；在等待阶段， 个中继节点执行直接传输，即仅将消息传输到 目标节点．如果 节点限制在较小的移动范围或者移动具有很强的关联性，则喷射等待路由协议的性能将会有所下降．为了克服 苏金树 等：容延容断网络路由技术 127 这个 问题，喷射聚焦路 由协议对其进行改进，即在聚焦阶段使用了文献[53]中基于效用的路由协议，使消息转发 给具有更高效用的节点．为了优化喷射路由协议，作者进一步讨论了 值的选择，以及将 个消息快速分发的方 法等，并分析了喷射等待路 由协议延迟上界． RAPID(resource allocation protocol for intentional DTN)["J也一种面向特定优化 目标的、基于效用的路 由协 议，其主要思想是，通过由应用显式的指定路 由目标，将路 由目标转换成为每个消息的效用．即在给定的有限带 宽中，决定对哪些消息进行复制可以优化一个特定的路 由目标．RA PID协议主要包括带内控制信道、RA PID选 择算法 、推理算法 3个模块．RAPID首先使用带 内控制信道，用于节点之间交换网络状态元信息，其元信息主要 是从历史接触中收集得到，包括消息副本的数量、节点之间接触的期望时间、分发延迟估计信息等；选择算法 决定在到达 目的节点之前，哪些消息叮以进行机会主义复制，令 表示消息 i对于路由目标的效用， 表示通过 复制报文 f而增加 的效用值，S 表示消息的大小，选择算法将根据资源 的限制，优先对其边 际效用(marginal utility)oWi／s 较大的消息进行 复制 ；推理算法用 于推断在给定路 由 目标的情 况下消息 的效用 ．通 过实验证 明，RAPID即使使用部分的、不准确的元信息，与现有的方法相比，仍能明显地改善特定的路 由指标的性能． 3．5 编码路由 严格来说，基于编码的路由并不是真正的路由技术，其所使用的各种编码方法实质上是对 DTN 问断连接特 性、无线信道等予以补偿的机制，町以与其他路由协议联合使用，以提高数据分发概率等路由指标． Wang[ ]使用 了纠删码和多路径的方法增强数据分发的可靠性．纠删码的基本思想是：将原始消息 M 按照 因子 r进行复制，算法将产生 n(n=Mxr／b)个同等大小的编码块．那么，接收方只要接收到任意(1+国 6个编码块， 消息即可被重构，其中，徙 与算法相关的常量．在简单 的多副本路 由中，消息将会传递给 ，个中继节点，而采用纠 删码将产生kr(k>_l，依赖于纠删码算法)个 同等大小的编码块并发送给 个中继节点．由于基于纠删码的路由采 用 了更多的中继节点，而这 个中继中只要有多于 k个节点具有更低的延迟，那么与多副本路 由相比，基于纠删 码的路由将降低延迟的上界． Jain[571对纠删码路由进一步分析，考虑了 DTN 网络中链路失效、路径选择错误等情况．假设消息复制因子 r，链路之间存在 n条相互独立的可行路径，对于每条路径 f，路径 i上的消息分配比例为 ，路径 i上将所分配的消 息发送到目标节点的比例为 S，路径 i上成功分发数据概率为P 那么 目标节点将可以接收 葺 数量的编码 块．为了使 目标节点能够接收到超过 1／r数量的消息，需要对编码块进行优化分配到多条路径上．Jain针对路径失 效为 Bernoulli(0．1)、高斯分布的场景进行了研究．在路径失效的概率服从 Bernoulli(0—1)分布的场景下，路径失 效将造成经过这条路径上的所有消息丢失，在 Bernoulli(0-1)的情况下，其编码块分配到多路径的问题归结为一 个具有NPhard的混合整数规划问题，且实验发现，仅当pxr>4／3时，将消息编码成更多的块才能提高数据分发概 率；在路径失效服从高斯分布的场景下，经过该路径上的消息将 以一定的概率恢复，其最大消息发送概率等价于 最大化夏普比率(Sharpe—ratio)，从而可以利用经济学中的投资组合理论进行近似求解． Boudec等人【5 则提 出基于网络编码的概率路由算法．每个消息中包含编码向量，当中继节点接收到消息 后，中继节点并不是简单地转发消息，而是将已经接收到的消息进行线性组合编码产生一个新的消息，按照转发 因子 d转发给邻居节点，如果 d