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

admin

　　容断网络(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的责任范围内。

　　OS-multicast(On-demandSituation-awareMulticasting)是在DTBR的基础上发展起来的。该算法包括5个部分： (1)成员管理：若节点欲加入组播组群，可以通过广播带有成员生存时间的组群参加消息(Group Join Message／GJM)向网络注册。例如，节点i欲在时间段[tsi，tei]参加组播服务，组播源接收到其发出的GJM后，将该节点添加到Lm中。 (2)束存储：每个DTN节点都有一个有限大小的缓存。接收到的束暂时保存在缓冲器中，然后根据接收策略，对束进行转发或剔除处理。如果缓冲器有溢出，当一个束到达时，缓冲器将删除队列中头一个缓存的束；如果所有目的接收节点都接收到该束的拷贝时，DTN节点将删除其缓存的束；否则对其缓存。 (3)转发状态维护：每个束都具有自己的转发状态，包含—个上游链表Lu(记录束转发经过的所有节点)和一个未解决的列表Lp(包含当前组播树的目的接收节点)。初始化后，Lp中包含所有的目的接收节点，Lu标记为空。组播会话过程中，Lp通过复制Lm中的相关目的接收节点信息来更新。 (4)消息转发：当一个束产生后，组播源通过寻访知识库反馈得到通往有效接受节点的所有路径。这些路径形成一个静态网格，源节点将根据当前的网络的状况，删掉一些不可利用的链路，或增加一些有效的链路，更新静态网格，得到一个动态的网格。组播源将根据该动态网格建立组播树。 (5)束传输：DTN节点周期性地查看缓存，检查是否能够对缓存束实现进一步转发，如果通往Lp中接收节点的路径存在则转发束，并更新相应的Lp信息。

　　OS-multicast是针对DTBR的不能很好地动态利用当前可行路径的缺陷而提出的改进算法。但OS-multicast采用了类似于DSR的路由决策算法，假定诸如链路状态、网络拓扑等能很好地被获知，而这种假定存在一定的局限性；而且，DTNs网络环境下的节点密度比较稀疏，这种基于网格建立组播树的路由创建方法，适用性不强。

　　CAMR(Context-Aware Multicast Routing)是基于节点密度的自适应的组播路由算法，它主要利用了网络一些额外的信息，如节点的位置、节点的速度等来进行路由选择。该协议包括5个组成部分： (1)节点密度估计：DTN节点使用常规的传输能量周期性地广播邻居发现消息，当另—个DTN节点监听到该消息并满足一定的延时条件下，反馈一个邻居应答消息，应答消息包括该节点的一些信息(如节点身份、节点位置、节点速率等)以及一跳邻居节点的信息(身份、接触概率、位置、速率等)。因此每个DTN节点可估计其相邻节点的数目，用nd来表示。当nd小于门限k时，节点将设立一个稀疏接触标志。 (2)两跳邻居接触概率估计：只要DTN节点ni能够接收到来自邻居节点nj的相邻应答消息，两跳接触概率就被设置为1，若ni不能接收到nj的相邻应答消息，则将接触概率降低到一个因子，β(因为相邻发现消息已经进行了周期性广播，因此总存在一个合适的β因子)。(3)路由发现：当不存在任何通向目的接收节点的路径，源节点将启动路由发现过程，在广播路由请求消息之前，节点会检查是否存在任何稀疏接触标志存在。若存在有稀疏接触标志，则启用高功率传输机制，否则使用常规功率的消息传输机制。 (4)路由维护：CAMR采用保管传输的一些特性进行路由维护，当DTN节点ni收到下游节点nj的保管确认(custodian acknowledgment)后，节点ni将删除其缓存保管束。若由于节点的移动，组播分支中断，则DTN节点通过广播路由请求或通过自身节点移动，进行路由修复。 (5)数据传输：每个传输的束都包含一些额外的头文件(如接收节点的身份)，它决定了束传输的目的接收节点。如果支持CAMR机制的中间转发节点为一分支节点，则其要对束进行拷贝；如果中间转发节点采用了高功率的路由发现机制，则其将充当一个摆渡(ferry)节点，进行数据转发。

　　CAMR突破了传统网络的路由发现机制，采用的路径发现过程具有很好的性能，更适合DTNs网络的特性，因此组播路由性能较为理想。但它假定节点的移动可以被控制，需要一定的应用技术来支持。另外，CAMR结合利用了高功率的组播传输和消息摆渡(message ferrying)机制，提高了组播分组传输比率。但CAMR仍然需要依赖一定的网络知识进行路由发现过程和对网络节点移动的控制。

　　EMR(Epidemic Multicast Routing)将Vahdat和Becker的Epidemic算法的设计思想引入到容断网络的组播路由中。每—个节点的缓存中保存要传送的数据(束)，并为数据的集合建立名为SV(summary vector)的索引(该索引指明了数据传送的目的节点)，当两个节点“接触” (彼此进入对方的无线通信范围)时交换彼此的SV。节点根据对方的SV遍历自己的SV，并借此判断自己的缓存中是否保存有对方的数据，而后节点向对方发送数据请求信息。随着节点之间的不断“接触”，数据会从源节点开始像病毒(epidemic)那样传播到网络中的其他节点，从而实现源节点到目的接收节点之间的数据通信。

　　这种组播方法实现简单，由于支持多条路径，所以可靠性较高。但由于数据交换频繁，对节点的缓存要求较高且网络开销较大，只有在少量数据包的情况下，路由的效率高。

　　EBMR(Encounter Based Multicast Routing)是在Prophet基础上发展而来的。Prophet算法充分利用相遇或投递转移的历史信息，为每个节点估算将数据成功转发到目的节点的概率，即到达概率，节点只会将数据转发给比自己到达概率高的节点；在数据转发过程中，节点之间还要交换彼此的SV及节点中缓存的到达概率信息，用来更新下一节点的到达概率。EBMR对Prophet作了一些改进： (1)如果下一节点的到达概率(delivery predictability)大于设定的门限值(Pthresh)，上游节点就会向该下游节点转发束；如果没有找到合适的下一跳节点，该节点缓存束信息，直到等待时间(wait timer),到达极限值。 (2)在边界溅的节点，首先启动定向天线进行邻居节点发现，若发现失败，则启动另一个全方位天线。 (3)允许组播源节点选择多个下一跳节点执行发往同一个接收节点的数据传输。

　　EBMR不依赖于任何路由发现过程，属于一种基于概率的组播路由算法。这种组播路由算法，有比较广的适用范围。但是在邻居节点发现过程中，使用的天线装置会消耗一定的能量(一般为电池能量)，在DTNs这种资源受限网络中，该算法显得不可取。

　　3 组播路由算法性能比较与分析

　　表1对组播路由性能进行了比较。其中，消息域：算法在选定参与转发数据的节点时，所必须知道的拓扑图的信息范围；缓存：算法是否提高了网络数据转发速度，可以减少网络节点存储空间；节点定位：算法是否对节点采用位置定位，确定每个节点具体位置；数据汇集：算法是否具有冗余数据处理能力。

　　可以看出，基于知识的组播路由算法比基于概率的算法的数据汇聚能力要强，因为它通过建立组播树减少了一些冗余的数据传输，但其鲁棒性及扩展性相对较差；基于概率的组播路由算法不需要维护任何网络拓扑信息以及一些网络的额外知识，实现比较简单，但在数据转发过程中会造成环路现象，带来一定的网络开销。当节点相对比较集中或者节点密度较大时，使用基于知识的组播路由算法通过建立组播树，能够得到更好的路由效率；而当节点较为稀疏或节点的位置变化较为剧烈时，基于概率的路由算法可获得更好的路由效率。

　　以上2种组播路由算法各有优势。需要指出的是，DTNs组播路由算法是一个比较新的研究领域，前景广阔。本文对DTNs组播路由算法的分析描述，为其进一步的研究提供了一定的参考。