容迟/容断网络路由技术研究

樊秀梅 李 杨

摘要:容迟/容断网络(DTN)由于其长延迟、高误码率及频繁断路等网络特性不满足互联网较短传输延迟、低误码率及存在端到端路径的基本假设,传统Internet体系结构和协议无法直接用于DTN。DTN路由机制可以按照连接的确定性分为确定性路由和随机性路由。确定性路由主要有基于树的路由、时空路由和修正的最短路径路由等方法;随机性路由主要有流行性路由、基于历史消息的路由、基于模型的路由、可控移动路由和基于编码的路由。DTN在游牧计算、军事战场通信、紧急营救及灾后重建方面具有广泛应用前景。

关键词:容迟/容断网络;路由;编码;应用

Abstract: Since Delay/Disruption Tolerant Networks (DTNs) have long delay, high bit-error rate and frequent disconnection, it cannot meet the essential hypothesis of the Internet. Therefore, the traditional Internet architecture and protocols cannot be directly used for DTNs. The DTN routing mechanisms can be classified into deterministic routing and stochastic routing. The deterministic DTN routing algorithms include tree-based routing, space-time routing and amendatory shortest path routing, while the stochastic DTN routing algorithms are epidemic routing, history-based routing, model-based routing, controllable mobility routing and erasure-coding based routing. DTNs can be applied into nomadic computing, military communications, emergence rescue and post-disaster reconstruction, with a big prospect of extensive application.

Key words: delay/disruption tolerant network; routing; coding; application

1 DTN体系结构

Internet已成功地在全世界得到应用,现有的网络架构、通信模式和网络协议在正常情况下对互联网的使用来说是充足且高效的。然而,在某些没有固定网络基础设施的地区和情况下,网络往往是分离的,因此不能保证提供持续、稳定的连接。此外,这些环境中的网络设备常受限于其自身的发射范围、处理能力、存储空间和电源供给。在这种环境中,传统的网络协议往往不再适合。

从军事、深太空通信,到各种无线异构网络和游牧计算都产生了不同的网络服务需求。这些网络中,由于无线传输范围、移动速度、网络分离、异构底层网络、重大灾难或恶意攻击等原因可能形成长延迟、高链路误码率、路径频繁断开等特性,我们将具有这类特性的网络称为容迟/容断网络(DTN)[1]。

容迟网络的特点可以归纳为:具有较高相异性;频繁遭到网络分割;承受经常性的中断和失败;不对称、较长和可变的数据速率;网络设备受限于能量、带宽、存储/内存和成本。由于DTN无法满足Internet基本假设(如较短传输延迟、低误码率及存在端到端路径),故不能直接应用Internet的现行体系结构和许多协议[2]。

DTN体系结构的具体分层形式如图1所示。

由于DTN环境的多样性和网络状况天生的不确定性,使得DTN在体系结构、协议设计、网络互操作、安全、管理以及稳定性等方面的设计变得极具挑战性。DTN将会是未来的活跃研究领域,研究DTN的基础理论与关键技术具有重大的科学和社会意义。我们应该抓住这一历史机遇,在DTN研究领域积极开展研究工作,使之成为中国研究新一代网络的重点与取得原创性成果的突破口。

2 DTN路由机制

DTN路由的主要目的是最大化报文传输成功率。与传统有线和无线网络不同,DTN中网络延时大、拓扑经常变化、节点分布较稀疏、通常没有稳定的端到端链路。由于DTN网络拓扑结构的动态特性,链路的中断可能比连接更加频繁,在某段时间内可能不存在端到端的路径,因此有效的DTN路由需要结合异步路由方式,但这种路由方法在现有无线网络中很少研究。

Jain等人首次明确提出了DTN路由的主要问题和表达形式[3]。他们认为DTN路由就是确定信息如何在端到端之间通过一个随时间变化的连通图,且这种动态性是可以预先知道的。按照路由策略可以将DTN路由分为洪泛和转发两大类;也可以按照连接的确定性分为确定性路由和随机性路由。

2.1 确定性路由

确定性路由方案假定将来的移动和连接是可预测的,也就是整个网络的拓扑结构事先已知,主要包括:基于树的路由、时空路由和修正的最短路径路由。这类路由需要太多的网络知识(包括节点的移动规律、通信机会、网络拓扑等)。确定性连接的所有算法中,在消息真正传输之前,需要确立端到端的路径。

(1)基于树的路由

洪泛策略把报文的多个拷贝传送到一些节点,这些节点被称为“中继点”。中继点存储报文,直到其可以和目的点相连[4]。最早的DTN路由算法都归于这一类。但洪泛算法浪费了大量资源,为了提高性能,又进一步提出了直接连接、两跳转播、基于树的洪泛等。

(a)直接连接

这个策略只在源点和目的点之间有直接连接时,才会在链路上传输数据。这种策略不需要网络信息,在移动节点和指定网关上采用此策略可以增加网络的吞吐量,减少开销。

(b)两跳转播

源点首先向n个中继点发送拷贝,源点和中继点都有拷贝发往目的点。由于网络中有n +1个拷贝,所以消耗了更多的资源点,通过调整拷贝的数目,可以减少资源点的消耗。这种策略和直接连接都有一个限制条件:如果n +1个节点均连接不到目的,那么报文将不会被传输。

(c)基于树的洪泛

这种方法是对两跳转播的扩展。中继点的集合构成了从源点开始的一棵树,所以被称为基于树的洪泛。两跳转播可以被看作是深度为1的树。如果节点之间按连接的概率独立且相等,这种方法将是最优的。不像直接连接和两跳转播那样,基于树的洪泛在传输报文的时候,中间可以经过多跳,但是设置参数相对麻烦。

(2)时空路由

时空路由[5]考虑的是一种新型无线网络下的路由问题。在这里无线网络彼此之间是分隔的,通过携带消息的节点不停地运动来与其他的网络分区进行通信。由于在源节点和目的节点之间缺少一条持续的路径,导致了传统移动自组织网络的路由协议不适合于此种网络。在转发给下一个可选节点之前,需要根据节点运动的空间轨迹和时间(包括一个节点携带消息的概率)来确定其路径。在这种存储—转发式的网络中,确定这样的时空路径是一个关键性的问题。在此类网络中,无论是基于限定性的时间区间内还是基于周期性的节点无限性运动,大多数网络节点的移动性都是可以预见的。时空路由研究一种时空路由体系结构,以一种可预测的节点运动来影响此类网络。通过构建时空路由表,在当前和将来预期的邻居节点中选择下一跳节点。不同于传统的路由表,时空路由表使用目的节点位置和消息到达的时间来确定其下一跳节点;基于移动性节点的时空图形拓扑模型,设计出Floyd-Warshall算法来计算这些时空路由表,以期尽量减少在间歇性的网络无连接情况下端到端的传输延迟。仿真和性能观测结果表明使用最小的网络资源得到了较高的性能增益。

2.2 随机性路由

随机性路由方案假定网络是动态的、不确定的,主要有流行性路由,基于历史消息的路由,基于模型的路由,可控移动路由和基于编码的路由。这类路由不需要太多的网络知识就能进行路由,但是它在网络中产生了太多的复制,容易占用网络资源。其中SPRAY和WAIT[6]、SOLAR-HUB[7]、CAR[8]是具有代表性的多副本路由算法。

(1)流行性路由

Vahdat和Becker提出了一种用于时断时续网络的路由协议,称为流行性路由[9]。这种协议依赖于流行性算法理论:当两个节点连接时,它们互相发送缓存中已有的报文列表,以使消息最终传输到目的端。各个主机可以缓存消息,即使当前没有到达目的端的路径,消息也会被缓存在主机中。这些消息的索引,称为报文列表,被保存在节点中。当两个节点相遇时,它们交换各自的报文列表。交换之后,每个节点就知道另外一个节点是否拥有它没有的消息。如果没有,该节点就向那个节点请求消息。这就意味着,只要缓冲区有空间,消息就会在节点相遇时,像某种传染病一样在网络中传播,并彼此“传染”。

(2)基于历史消息的路由

Philo Juang等人提出一种基于单跳信息方式的历史消息路由[10]:统计每个节点和接收消息基站(目标节点)的通信机会,并利用这些历史信息计算出量度值。当一个节点要发消息时,在与其有通信机会的节点中找出那些量度值较高的节点,并将消息复制过去,这样可使消息沿着一个越来越接近基站的方向传递。这种方法是一种坡度路由的方法,等级越高的节点在基站附件活动越频繁,同时和基站的通信的机会越多,但其中存在“慢启动”问题。特别是在大规模网络环境中,与源节点有通信机会的中继可能都离目标节点比较远,很可能没有和目标节点通信的机会,因此不可能有很高的成功率使其被选为中继。这样,源节点或其他中继在转发给下一跳时很难做出正确的判断,需要根据消息转发历史记录来做出智能的决策。

(3)基于模型的路由

随机性路由方案都假设节点的移动是随机的,没有任何的规律。然而在现实世界中,节点的移动都遵循一定的知识模式,例如行人在路上行走,车辆在公路上移动,卫星沿轨道运转等。一旦其移动模式被确定下来,即可知道哪些中继与目标节点有更高的通信机会。基于模型的路由[11]使用移动节点的世界模型来选择较好的中继,而无需在网络中大量复制消息。

(4)可控移动路由

移动Ad Hoc网络(MANET)提供快速部署和自我配置的网络容量恢复,其拥有许多关键性应用,如战场,灾害救济和广域遥感。可控移动路由[12]研究在稀疏节点MANET中网络中断一定时间下的高效率数据传输问题。以往的方法依靠的是使用远程通信或者已知的节点移动性,这会导致节点有限电池的迅速消耗和较低的数据传输率以及较大的延迟。可控移动路由通过信息摆渡(MF)的方法解决这一问题。信息摆渡是一种辅助移动的方法,采用了一系列称为信息渡轮(或短期渡轮)的特殊移动节点,在节点调度区提供通信服务。通过引入节点移动的非随机性概念,并利用这种非随机性以协助转发数据。研究取决于渡轮和节点初始前向运动的两种MF变化。该设计利用移动性提高了数据的传输性能、降低了节点的能量消耗,并在多种不同的网络环境下验证了其性能优越性。

(5)基于编码的路由

基于编码的方案主要是基于网络编码[13]和基于删除编码(EC)[14]。基于网络编码的路由是由Widmer等人提出,它的基本思想是对转发的数据包应用网络编码进行编码产生新的数据包和相应的编码向量,编码向量与数据包一起传输,当收到足够数量的数据包以后,目的节点就能解码,恢复出原数据包。基于网络编码的路由能以很小的开销向网络中的节点以较高的概率发送消息,特别适用于受限网络环境。网络编码比概率路由更好地利用节点的移动性,即使在极限情况下,如有较大的丢包率的稀疏网络,节点休眠时间较长的网络,在这些情况下概率路由效率较低。基于EC的路由思想是对消息进行删除编码,并将产生的编码块分布在大量的中继上传输。每次中继只传输消息的一部分而不是整个消息的一个副本。这样分片传输可以控制每比特消息的传输开销。EC方案能使用固定的开销提供好的延迟保证,消除了由于不好的转发选择导致的大延迟,对于链路失效有更好的健壮性。

尽管针对DTN的特殊性已经提出了一些相关路由方案,但仍存在很多问题:

(a)现有路由算法的消息转发模式单一:往往不能根据网络和节点自身资源的使用情况自动调节转发频率;消息转发频繁,浪费网络资源;稀少,增加延迟。

(b)现有的异步路由算法大多只采用逐跳式的数据传递模式:没有充分利用网络中的“部分连通路径”进行多跳转发;在节点密度频繁变化的网络中无法取得更好的性能。

(c)只有平面路由解决方案:针对三维移动容迟网络,如水下网络传输延时大、信道质量差、节点能耗高的特点,需要研制出适用于三维无线移动容迟/容断网络特点的路由方案。

3 DTN的应用及发展

由于DTN不要求固定的数据包传输和及时交付,不同需求的应用正好可以从中获益。对于无固定网络结构或者经常发生网络分割的情况,DTN尤其有用。DTN具有广泛应用前景,最初设计DTN的主要目的是用于行星间和深太空通信。例如,当在火星轨道上飞行的人造卫星飞行到火星的背面时,由于被火星遮档,就无法与地球实现连通。此外,正在研究的通信场景包括:

解决无线电覆盖或运动造成的中断,加强移动游牧服务。

机会移动自组织网络(战场通信、紧急救灾等)。

无线基站稀疏部署(多跳、格状网)。

极遥远地区的网络接入。

发展中国家、乡村网络接入(缺少基础设施,无法承受卫星通信价格)。

采用瞬间高带宽的数据传输设备收集传感器网络数据。

3.1 游牧计算

移动计算[15]是随着移动通信、互联网、数据库、分布式计算等技术的发展而兴起的新技术。移动计算技术将使计算机或其他信息智能终端设备在无线环境下实现数据传输及资源共享。它的作用是将有用、准确、及时的信息提供给任何时间、任何地点的任何客户。这将极大地改变人们的生活方式和工作方式。

移动计算是一个多学科交叉、涵盖范围广泛的新兴技术,是当前计算技术研究中的热点领域,并被认为是对未来具有深远影响的四大技术方向之一。

3.2 车载KisokNet

调度者在公用电话亭与网关之间来回运动。网关具有Wi-Fi网络接口、存储能力,以及与Internet的持续连接。网关收集来自调度者的数据,存储到存储器中,然后再通过代理上传到Internet。一个区域可能有不止一个网关。调度者可以是公交车、出租车、摩托车以及火车。它们都经过公用电话亭和Internet网关。调度者具有车载蓄电池可以供电的单板计算机,这种计算机具有20～40 Gbit/s的存储空间以及一个Wi-Fi网络接口。它们与它们经过的kiosk控制器以及Internet网关通信。

3.3 军事战场通信

在战场上,军事人员和作战车辆都配有传感器和移动通信设备。当传统的通信方法被破坏或在电子干扰攻击环境下,使用DTN可从某一领土收集和传达信息。因此,命令、控制和通信(C3)仍然可以通过DTN执行[16]。

3.4 紧急营救/灾后重建

紧急救援和救灾任务时,很可能得不到任何可用的通信基础设施。然而,救援人员可以依靠DTN来交流至关重要的信息,并通过控制台协调救援和恢复工作。例如,考虑以下情况:一组洞穴登山被困在蜿蜒的深洞内,常规的通信方式如卫星和手机一无是处。然而,通信可以通过救援人员的移动通信设备和多个中继点(战略部署好的)建立。

4 结束语

由于DTN网络拓扑结构的动态特性,链路的中断可能比连接更加频繁,在某段时间内可能不存在端到端的路径,因此充分利用链路的间歇性、可预测性、能量层次和存储空间等特征设计合理有效的DTN机制成为DTN应用的关键条件。

尽管在相关研究方面已取得进展,但仍存在一些关键问题有待解决,如:由于DTN异步通信特点,信息需要存储在某些节点,并等待时机进行转发,如何快速有效地选择存储转发节点;相对于传统的二维DTN,三维DTN的拓扑控制问题难度增加、计算复杂度成倍增加、现实物理结构复杂,如何在三维网络下有效控制拓扑和设计路由算法;如何在DTN环境下有效解决网络编码的优化结构和自适应编码选择,设计适合DTN的网络编码;如何针对DTN环境下的确认困难和资源有限问题,建立拥塞与可靠性、路由机制和移动模型的关系,进行拥塞控制;如何针对DTN这类特殊开放系统中的节点自私问题建立适应DTN环境的博弈模型和相应的对自私行为的控制方法。

5 参考文献

[1] FALL K, FARRELL S. DTN: An architectural retrospective [J]. IEEE Journal on Selected Areas in Communications, 2008,26(5): 828-836.

[2] FALL K, DEMMER M. Delay/disruption tolerant networking[C]// Proceedings of 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobIHoc06), May 22-25, 2006, Florence, Italy. New York, NY,USA:ACM,2006.

[3] JAIN S, FALL K, PATRA R. Routing in a delay tolerant network [C]// Proceedings of Conference on Applications, Technologies, Architectures and Protocols for Computer Communication(SIGCOMM04), Aug 30-Sep 3,2004, Portland, OR, USA. New York, NY,USA: ACM, 2004:145-158.

[4] HANDOREAN R, GILL C, ROMAN G C. Accommodating transient connectivity in ad hoc and mobile settings[C]//Proceedings of the 2nd International Conference on Pervasive Computing, Apr 21-23, 2004, Vienna, Austria.2004: 305-322.

[5] MERUGU S, AMMAR M, ZEGURA E, et al. Routing in space and time in networks with predictable mobility [R]. GIT-CC-04-7. Atlanta, GA,USA: Georgia Institute of Technology,2004.

[6] SPYROPOULOS T, PSOUNIS K, RAGHAYENDRA C. Efficient routing in intermittently connected mobile networks: The multiple-copy case [J]. ACM/IEEE Transactions on Networking, 2008,16(1):77-90.

[7] GHOSH J, WESTPHAL C, NGO H, et al. Bridging intermittently connected mobile ad hoc networks (ICMAN) with sociological orbits [C/OL]//25th IEEE International Conference on Computer Communications(INFOCOM06), Apr 23-29,2006, Barcelona, Spain. [2009-07-19]. http:// people.nokia.net/cedric/Paper/INFOCOM_ ABSTRACT_SOLAR.pdf.

[8] MUSOLESI M, HAILES S, MASCOLO C. Adaptive routing for intermittently connected mobile ad hoc networks [C]//Proceedings of IEEE 6th International Symposium on a World of Wireless, Mobile and Multimedia Networks(WoWMoM05):Vol 1, Jun 13-16, 2005, Taormina, Italy. Piscataway, NJ,USA: IEEE, 2005:183-189.

[9] VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks [R]. CS-2000-06. Durham, NC, USA: Department of Computer Science, Duke University, 2000.

[10] JUANG P, OKI H, WANG Y, et al. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet[C]// Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS02), Oct 5-9, 2002, San Jose CA,USA. New York, NY,USA:ACM, 2002.

[11] CHEN Z D, KUNG H T, VLAH D. Ad hoc relay wireless networks over moving vehicles on highways[C]//Proceedings of 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computingin(MOBIHOC 01), Oct 4 - 5, 2001,Long Beach, CA, USA. New York, NY,USA:ACM, 2001:247-250.

[12] ZHAO W, AMMER M, ZEGURA E. A message ferrying approach for data delivery in sparse mobile ad hoc networks [C]// Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc04), May 24-26, 2004, Roppongi, Japan. New York, NY, USA, ACM, 2004:187-198.

[13] WIDMER J, BOUDEC J L. Network coding for efficient communication in extreme networks [C]//Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM05), Aug 22-26, 2005, Philadelphia,PA, USA. New York, NY,USA:ACM, 2005: 284-291.

[14] WANG Y, JAIN S, MARTONOSI M, et al. Erasure-coding based routing for opportunistic networks[C]//Proceedings of Conference on Applications, Technologies,Architectures, and Protocols for Computer Communications (SIGCOMM05), Aug 22-26, 2005, Philadelphia,PA, USA. New York, NY,USA:ACM, 2005:229-236.

[15] KLEINROCK L. Nomadic computing[EB/OL]. [2009-06-12]. http://www.cs.ucla.edu/~lk/PS/paper199.pdf..

[16] HALVARDSSON M, LINDBERG P. Reliable group communication in a military mobile ad hoc network [R/OL]. [2009-08-15]. http://www.vxu.se/msi/forskn/exarb/2004/04006.pdf. 2004.

收稿日期:2009-08-06

樊秀梅,北方交通大学通控系博士毕业,清华大学计算机系博士后出站,现为北京理工大学教授,主要研究领域为计算机网络与无线网络的路由技术及下一代移动互联网QoS技术。

李杨,北京理工大学计算机科学技术学院在读博士生,主要研究领域为容迟网络、路由交换与调度。