容断网络中的组播路由算法研究

容断网络(DTNs／Disruption Tolerant Networks)最早是由Kevin Fall 2005年在MILCOM上提出的，它是针对网络频繁发生分离以及网络节点间断性连接的网络场景而提出的一种新型的网络，由架构在原有网络(如ad hoc网络)上的特殊节点(即DTN节点)组成。在容断网络中，DTN节点间断性链接，每个DTN节点兼备主机和路由器2种功能，节点间的链路呈机会性、可预测性、周期或非周期性。主要有以下特性：路径和链路方面特性--高延迟、低数据速率、频繁间断、长排队时间；网络结构方面特性--为不同的网络提供了互操作性和安全性；端系统方面特性--节点的寿命有限、占空比较低、资源受限(如节点存储、处理能力有限)。

　　容断网络组播是DTN节点之间一到多或者多到的数据传输方式。随着通信网络的发展以及通信研究领域的深入，一方面，组播技术已经成为容断网络研究中的一种关键的技术，例如在军事战场中，利用组播技术可以将控制中心的命令快速、可靠地发送到各个现场指挥基地，并实现士兵之间的有关战场周边环境信息的共享；在灾难营救过程中，通过组播技术，可以快速地实现营救工作者之间共享伤者有关的信息以及现场可能存在的一些潜在危险。另一方面，组播路由能够提高网络的资源利用率，降低通信成本，节约带宽。因此，如何根据容断网络的特点，设计有效的组播路由算法，是当前的-个研究热点。

　　国外的一些学者致力于容断网络中的组播技术的研究，并取得了较为丰硕的成果。但其研究还处在一个起步的阶段，到目前为止，还没有一种比较成熟的组播路由算法能够很好地解决DTNs这种特殊网络场景下的数据通信。

　　1 容断网络组播路由算法分类

　　传统的ad hoc网络根据多播路由协议在寻路机制和路由结构上的不同，将组播路由算法分为3大类：基于树的组播路由、基于网格的组播路由、混合的组播路由。由于独特的网络环境，传统的组播路由算法分类已不适用于容断网络。为此，我们给出一种新的分类方法，依据寻路路由机制的不同，将容断网络组播路由算法分为2大类：基于知识的组播路由算法和基于概率的组播路由算法。

　　基于知识的组播路由算法依据一定的网络知识作出路由选择，这些网络知识主要涉及到网络拓扑、节点间的连通模式、节点的地理位置信息、节点的运动时刻表等等。并且基于知识的组播路由算法假定：网络能够预先发现一定的相关网络知识；然后根据近似Dijkstra算法(它是传统的Dijkstra最短路径算法的推广，根据网络具体的约束，如带宽、时延要求等选择最佳路径)计算出最佳的路径，从而决定消息的转发。

　　基于概率的组播路由算法不依赖于任何预先获知的相关网络知识，组播节点首先估算自身的到达概率(成功将数据发送到目的接收节点的概率)，然后和下一跳节点的到达概率相比较，再决定数据是否要进行转发。该算法的基本思想是只要数据在网络中随机分布的时间足够长，数据最终都能发送到目的节点。

　　2 基于容断网络的组播路由算法分析

　　U-Multicast：(Multiple-unicast-based Multicast)是实现组播的最简单算法，它通过使用多个从源节点到目的节点的单播服务来实现组播数据传输。工作过程为4个步骤： (1)对于每个目的节点，源节点通过寻访下部的网络收集到该目的节点的历史端到端的路径，然后选择一条最小开销的路径，进行逐跳转发，并在转发前检查该路径当前是否可用； (2)如果该路径当前可用，将通过该路径把组播束(DTNs扣基本数据传输单位)的拷贝发送到下一跳； (3)如果该路径当前不可用，则将缓存束拷贝，等待链路可利用的下一时刻，或者一个新的数据传输机会； (4)每个DTN节点，收到束拷贝后都会按照上面的步骤对数据进行转发。

　　该算法的束拷贝是在源节点处完成的，有多少个目的接收节点，源节点就要发送多少个束拷贝，这样其路由效率较低。由于容断网络采用无线信道进行数据传输，其节点间的链路、可用带宽和缓存等资源都是非常有限的，因此需要有效的组播服务来支持这些应用。

　　ST-Multicast(Static-tree-based Multicast)是基于静态树的组播路由算法，基本思想是：当组播会话开始时，源节点通过寻访下部网络，获得完整的网络拓扑信息或者链路的概要信息，查找到节点间的历史路径信息，然后根据这些信息，创建当前通向目的接收节点的最小开销的组播树，并沿着新创建的树，对束进行转发。

　　DTBR(Dynamic Tree-Based Routing)是基于动态树的组播路由算法，每个中继节点都要计算自己的组播树。首先，源节点寻访下部网络(通常在下部网络中存在一种网络知识库，告知节点有关的网络拓扑信息)，获得多跳的网络拓扑信息或链路概要信息，计算组播树，然后束拷贝沿着该树进行转发；当下一跳节点接收到该束的拷贝时，该节点会仿照上面的方法，重新计算自己的组播树，进行束拷贝转发，直到目的接收节点。在组播会话过程中，上游节点在向下游节点转发束拷贝的同时，也为下游的节点分派了束拷贝的接收列表，下游节点只能按照该接收列表将束拷贝转发到相应的节点。

　　DTBR在一定程度上减少了冗余的交通负荷，但却丢失了一些传输连路可利用机会。如图1所示：节点1负责束5的转发，节点2负责束6的转发，节点3负责束7的转发，如果2-6的链路在传输过程中突然被中断，即使存在一条通向目的接收节点6的链路：1-4-6，节点6仍然不能接收到束拷贝，因为束6的转发不在节点1的责任范围内。