DTN多播路由算法研究.doc

DTN多播路由算法研究 黄勇萍1秦芳远2叶佳宁3黄樑昌4 （1.广西民族师范学院数学与计算机科学系，广西崇左532200；2.南方医科大学网络中心，广东广州510515；3.广东省地震局，广东广州510070；4.中国电信广西公司，广西南宁530015） 【摘要】DTN是从具有延时容忍特性的一类网络中抽象出来的，高延迟、间歇性连接、资源受限等特点给传输协议的设计带来了巨大的挑战。多播服务支持一组用户的数据分发，许多潜在的DTN应用是基于多播方式的，利用多播技术能够提高网络的资源利用率，降低通信成本，节约带宽。首先对DTN及其多播技术进行概述，分析DTN的特点以及DTN多播服务技术应用与发展；其次，深入研究DTN多播路由算法，对现有DTN多播路由算法进行综合比较分析；最后，展望未来进一步的研究工作。 关键词dtn；路由；算法；多播 基金项目：广西民族师范学院xx年度资助项目(XYYBxx023)；xx年度广西高校科学技术研究项目（LXxx457）。 作者简介：黄勇萍（1985），女，汉族，广西藤县人，工学硕士，讲师，研究方向为计算机网络。 前言 DTN是延迟容忍网络(DelayTolerantNetwork)1的简称，由K.Fall等科学家于xx年在ICIR会议上提出来的。是从具有延时容忍特性的一类网络中抽象出来的，最初对星际因特网IPN(Inter-PlaNetwork)2项目的研究，把节点间的长延时、高不对称性和间歇性连接作为主要的场景加以考虑。多播服务支持一组用户的数据分发，许多潜在的DTN应用是基于多播方式的（例如军事战场、灾难营救过程），通过多播技术，能够提高网络的资源利用率，降低通信成本，节约带宽。多播技术在因特网和移动自组网中已有深入广泛的研究。但是对于DTN，由于频繁网络断开的特性使得DTN中的多播成为一个难题。网络设计者若把适用于Inter中多播路由（例如MOSPF和DVMRP）或adhoc网络中的多播路由（例如AMRoute和ODMRP）直接应用于DTN环境，将面临很大的障碍和挑战。因此，DTN多播需要新的定义和路由设计，本文针对DTN的特点，对DTN的多播路由算法进行论述。 DTN概述 当前，Inter在互连全球异构的网络上取得了巨大的成功，TCP/IP协议已成为互连网络的事实标准。但是随着计算机技术，微电子技术的发展以及军事和其他领域研究的需要，越来越多的新型网络开始出现，如陆地移动网络、外来媒体网络、军事无线自组织网络和无线传感网络等。这些受限网络中存在共同的特点：高延迟、低数据率、间歇性连接、缺少端到端路径、能量和存储受限，给传统的基于TCP/IP协议的端到端通信的Inter技术带来严峻的挑战。为了使这些受限网络可以和现有的因特网互联，并改善网络的传输性能。K.Fall等科学家于xx年在ICIR会议上提出了延迟容忍网络(DelayTolerantNetwork，DTN)的架构。 不同于现有的网络，DTN的主要特征表现为：高延迟、低数据率、连接中断频繁以及较长的排队时间等。对DTN来说，传输率可能是比较小的，延迟相对来说却比较大，上行和下行的数据率很大程度上不对称的。在一些特殊的情况下，单向链路的可能性也是存在的，如在军用中同一些需要隐蔽的装备进行通信。同时，在DTN中，连接中断频繁，而且中断的原因也不一定全都是由于出错导致的。尤其是在无线移动网络中，连接中断的原因主要节点的运动和低占空比操作。在一些传统的分组网络中，消息的排队时间经常对整个延时起决定性作用的。但在这些网中，排队时间通常是非常短的，一般都远远小于1秒钟。而且，当下一个节点无法连接时，数据包就会丢失。相比之下，DTN的连接断开情况比较常见，节点的排队时间相对而言比较大，有可能达到几个小时甚至几天。3 DTN多播服务技术应用与发展 多播服务支持一组用户的数据分发。随着通信网络的发展以及通信研究领域的深入，许多潜在的DTN应用是基于多播方式的，例如在军事战场中，利用多播技术可以将控制中心的命令快速、可靠地发送到各个现场指挥基地，实现士兵之间的有关战场周边环境信息的共享；在灾难营救过程中，通过多播技术，可以快速地实现营救工作者之间共享伤者有关的信息以及现场可能存在的一些潜在危险。4另一方面，利用多播技术能够提高网络的资源利用率，降低通信成本，节约带宽。多播技术在因特网和移动自组网中已有深入广泛的研究。但是对于DTN，由于频繁网络断开的特性使得DTN中的多播成为一个难题。网络设计者若把适用于Inter中多播路由（例如MOSPF和DVMRP）或adhoc网络中的多播路由（例如AMRoute和ODMRP）直接应用于DTN环境，将面临很大的障碍和挑战。首先，在DTN多播消息传输过程中，保持多播结构（树形或者是网状结构）的连通性是困难的。第二，由于DTN自身的特点，多播结构不断发生变化而引起中断从而导致消息传输时发生频繁失败或大的端到端延迟。第三，传统多播路由方案的设计是基于网络连通性较好的假设，而这种假设在DTN环境中是不可能的。所以，DTN多播不仅要求新的多播定义，而且带来了路由设计的新问题。 DTN多播路由 现有的DTN多播路由算法从大的方向看，可以大致分为域内多播路由算法和域间多播路由算法。 .1域内多播路由算法 域内多播是指在属于同一个管理域内进行一组用户的数据分发。目前，主要的DTN域内多播路算法，根据寻路路由机制的不同，大概可分为2类:基于知识的多播路由算法和基于概率的多播路由算法。4（1）基于知识的多播路由算法主要有：U-Multicast(Unicast-basedMulticast)是一种基于单播的简单的DTN多播路由算法，它通过使用多个从源节点到目的节点的单播服务来实现组播数据传输；ST-Multicast(Static-tree-basedMulticast)是一种基于静态树的多播路由算法；DTBR(DynamicTree-BasedRouting)是一种基于动态树的多播路由算法，每个中继节点都要计算自己的多播树；OS-multicast(On-demandSituation-awareMulticasting)是在DTBR的基础上发展起来的。针对DTBR的不能很好地动态利用当前可行路径的缺陷而提出的改进算法；CAMR(Context-AwareMulticastRouting)是基于节点密度的自适应的多播路由算法，它主要利用了网络一些额外的信息，如节点的位置、节点的速度等来进行路由选择。（2）基于概率的多播路由算法主要有：EMR(EpidemicMulticastRouting)将Vahdat和Becker的Epidemic算法的设计思想引入到容断网络的多播路由中；EBMR(EncounterBasedMulticastRouting)是在Prophet基础上发展而来的。Prophet是一种采用相遇或投递转移的历史信息，为每个节点估算将数据成功转发到目的节点的概率，即到达概率，节点只会将数据转发给比自己到达概率高的节点。在转发策略上，EBMR对Prophet作了一些改进:如果下一跳节点的到达概率(deliverypredictability)大于设定的门限值，上游节点就会向该下游节点转发消息；如果没有找到合适的下一跳节点，该节点缓存束信息，直到等待时间(waittimer)到达极限值。 基于知识的多播路由算法依据一定的网络知识做出路由选择，这些网络知识主要涉及到网络拓扑、节点间的连通模式、节点的地理位置信息、节点的运动时刻表等等。并且基于知识的多播路由算法假定:网络能够预先发现一定的相关网络知识。所以其鲁棒性及扩展性相对较差。比较适用于节点相对比较集中或者节点密度（下转第112页）（上接第85页）较大的情况。基于概率的多播路由算法不需要维护任何网络拓扑信息以及一些网络的额外知识，实现比较简单，而当节点较为稀疏或节点的位置变化较为剧烈时，基于概率的路由算法仍可获得较好的路由效果。EBMR不依赖于任何路由发现过程，属于一种基于概率的多播路由算法。这种多播路由算法，有比较广的适用范围。 .2域间多播路由算法 在不同管理域间进行一组用户的数据分发叫做域间多播。目前，关于容迟网络路由的研究大部分集中在单域即域内消息传递的问题上。然而，许多实际应用场景，特别在发展中区域，往往需要在多域间进行信息传递。目前，实现域间通信的多播路由算法主要有：SHIM是一种可扩展（scalable）的分等级的域间多播路由方案。在SHIM中，组长（域头）形成高层（upperlayer），各个组除组长外其余的节点形成低层（lowerlayer）。多播源节点发送消息包到它的组长，然后由组长分发要发送的数据包给所有包含兴趣接收点的组的组长。该方案的主要缺点是它利用DTBR或者OS-Multicast作为域内多播路由方案。因为DTBR或者OS-Multicast采用类似于DSR的路由决策算法进行组长之间的路由发现，所以，这两者方案在节点密度比较稀疏DTN环境下，适用性不强。基于摆渡的域间多播（FBIMR）：FBIMR借助于特定的叫“摆渡”的节点完成域与域之间的消息通信5，而域内节点间的通信则采用增加冗余消息复制的基于相遇（EBMR2）的多播方案。该机制采用“摆渡”节点在域与域之间中转数据，可以有效避免过多的能量损耗和网络资源负担，但需要预先规划节点运动路径或要求节点移动可控。 总结 DTN是一种新型的无线网络体系结构，至力于解决频繁间断网络中的数据通讯问题。许多潜在的DTN应用是基于多播方式的，由于DTN高延迟、间歇性连接、资源受限等特点，其多播技术需要新的定义和路由设计。本文对DTN多播路由算法目前的研究进展进行论述，综合分析了目前存在的DTN多播路由算法，在这基础上，将进一步深入研究，设计更合理有效的路由算法。 参考文献 FallK.Adelay-tolerantworkarchitectureforchallengedIntersJ.In:Proc.ofthexxConf.onApplications，Technologies，Architectures，andProtocolsforComputerCommunications.Karlsruhe:ACM，xx:27-34. AkyildizIF，AkanB，ChenC，Fa