自组网环境中的组播路由协议

关于组播路由协议的研究是自组网研究中的一个突出问题。本文将说明自组网中组播协议研究所面临的主要问题，并将简单介绍和分析当前已提出的一些自组网组播协议。

----在典型的自组网环境中，网络主机通过群组协作来完成一项预定的任务。因此，组播在自组网中扮演了一个重要角色。图1绘出了自组网中的一个组播数据发送过程。

Internet中的组播协议包括组治理协议IGMP和组播路由协议（DVMRP、MOSPF、PIM等）。IGMP负责本地路由器到直接与它相连的子网的组播分组的发送，并不关心路由器间或跨越中间网络的组播分组转发。组播路由协议则完成路由器间和跨网络的组播分组的转发任务。

----在目前研究较多的单跳的、基于蜂窝模型的无线网络中，主机到基站只有一跳，相当于在同一子网中，所以不必考虑组播路由的问题，只需实现组治理协议。然而，由于自组网是一种多跳的无线网络，每个节点都兼有主机和路由器的功能，所以组播路由协议就必不可少。

----然而，用于静态网络的组播协议（例如，距离矢量组播路由协议(DVMRP）、组播开放最短路径优先协议（MOSPF）、基于核心树的组播协议（CBT）和协议无关的组播协议（PIM））在自组网中不能很好地运行，因为在动态的自组网中，分发树结构轻易被破坏并且必须因连接变化而调整。此外，分发树通常需要一个全局的路由结构，诸如链路状态或距离矢量。由持续的拓扑结构变化而引发的节点间路由矢量或链路状态表的频繁交换，产生了额外的信道和处理开销。鉴于自组网自身的特点，一些针对自组网的组播路由协议相继提出。下面我们就简单介绍并比较一种比较有代表性的自组网路由协议。

几种典型组播路由协议

----组播路由算法的一种常见的思路是在群组成员之间构造一棵分发树。组播数据在这颗分发树上传播，所有接收者都能收到。在自组网中，这仍是一个基本思路。自组网中还有一些组播算法试图利用更多的路由信息以获得更好的可靠性或数据传送性能。这些路由信息构成了节点之间的网格，所以这些方法称为基于“网格”的组播路由协议。

----AMRoute

----MRoute（Adhoc Multicast Routing）是一个基于树的组播协议。它利用单播通道提供组成员之间的连接，创建一棵双向的共享分发树。AMRoute 协议分为两个过程。第一个过程为构造网格。第二个过程为在网格基础上形成共享分发树。两个过程可以同时进行。

----【第一个过程】开始时，网格是由一个个独立的网段组成，每个网段由一个组成员承担核心的角色。每个核心利用扩展环搜索法周期性地扩散JOIN REQ分组来发现其他网段上的本组成员。当A成员节点收到来自B的JOINREQ分组时，A用JOINACK分组回答并将B作为同组邻居节点。B收到JOINACK分组后，也将A作为它的同组邻居。其中A和B还将采用分布式的核心选举算法决策谁将保留核心地位。这个不同网段的合并过程不断进行，最终将形成一个网格，网格上的每个节点对应于一个群组成员节点，有一个逻辑核心负责成员信息和网格结构。

----【第二个过程】核心周期性地传送 TREECREATE分组给本组邻居用以建立共享树，其中每个TREECREATE分组可以被唯一标识。当A成员节点收到一个非重复的来自B的TREECREATE分组后，它将其转发到所有其他网格链路上。假如收到了来自C的重复的TREECREATE分组，将沿接收链路返回一个TREECREATENAK分组。C收到TREECREATENAK分组后，将标记 C→A的链路为网格链路而不是树链路。想离开组的节点向邻居发送JOINNAK，退出所在的网格，并不再转发任何组播数据分组。如图2所示。

AMRoute的要害特征是它利用虚拟网格链路建立组播树。因此，当网络拓扑结构改变时只要树成员之间通过网格链路的路径仍然存在，树就不需要作调整。非成员不转发数据分组并且不需要支持任何组播协议。这样，仅仅树上的成员节点引入了处理和存储开销。这个开销主要是：每个节点需要周期性地“广播”JOINREQ 分组，核心需要周期性地“广播”TREECREATE分组，以及“广播”分组传播和中间节点处理“广播”分组所需的开销。这里的“广播”是指组成员节点通过底层的单目标分组传输实现在虚拟网格上广播的过程。AMRoute依靠于底层的单播协议维护组成员节点之间的连接，任何单播协议都可应用。协议主要的缺点是它存在暂时性的回路并且当节点移动时树结构得不到优化。

----ODMRP

----按需组播路由协议（ODMRP，On-Demand Multicast Routing PRotocol）使用基于网格的方法。它创建一个节点的网格，组播分组在该网格中扩散，以提供路径冗余性。ODMRP的一个基本思想是通过按需的方式获得路径信息。

----与按需的单播路由协议相似，协议由请求阶段和回答阶段组成。当源节点有组播数据发送，但没有路径或成员信息时，它们扩散一个JOIN-DATA 分组。当一个节点收到一个非重复的JOIN-DATA，它保存上游节点ID并再广播该分组。假如这个节点同时是组播接收者，它就构造一个JOIN-TABLE，并广播给邻居。

----JOIN-TABLE包含了该节点到各个源节点的反向路径的下一跳节点的ID。当邻居节点收到这个JOIN-TABLE时，假如它的ID和JOIN-TABLE中的某个下一跳节点的ID匹配，该节点将意识到它是在到源节点的路径上，因此是转发群组的一部分。然后它构造并广播自己的JOIN-TABLE。这样，JOIN-TABLE就被每一个转发群组成员转播直到它通过最短路径到达组播源节点。这个过程构造或更新了从源节点到接收节点的路径并且建立了一个节点的网格，即转发群组。组播发送者通过周期性发送JOIN-DATA 来刷新成员关系信息并更新路由信息。

----当传送组播数据时，假如当前节点是转发节点并且收到的分组是不重复的，节点将转发这些数据。由于所有的转发节点都中继数据，当主路径由于节点的移动而失效时，冗余路径有助于数据的递交。另一个ODMRP的独特属性是它的单播能力。ODMRP不仅能和任何单播路由协议并存，还能有效地起到一种单播路由协议的作用。这样，配置了ODMRP的网络就不再需要一个独立的单播协议了。

----在拥有GPS（全球定位系统）的网络环境中，ODMRP 还能利用运动猜测来适应节点的移动。通过利用GPS所支持的位置和运动信息，ODMRP 可以估算路径的过期时间，接受者可以选择有效时间最长的路径作回答。使用运动猜测的方法，源节点可以在预计路径失效时重新选择路径。这样，在节点移动方面，协议会更有弹性。

----AMRIS

----利用递增序号的自组网路由协议（AMRIS，Ad hoc Muticast Routing protocol utilizing Increasing idnumberS）是一个基于共享分发树的组播路由协议。网络中的每个节点分配一个组播会话成员ID号（msm-id），该ID号的大小将用于指导组播数据的流向。

----开始时，一个被称为会话节点（Sid）的特定节点根据群组会话需要广播一个NEWsession分组。通过广播该分组，建立一个从会话节点向外辐射状msm-id递增的分层逻辑结构，该结构类似于网格的概念。具体过程如下：NEW- SESSION分组包含会话节点的msm-id，邻居节点收到该分组后，就计算它们自己的msm-id，取值要大于分组中指定的那个。然后，节点将分组中的msm-id用它们自己的替换后继续转发NEW-SESSION分组。

----一个节点可以通过发送JOINREQ来加入一个组播会话，并因此形成一个新的或加入一个已存在的共享分发树。具体过程如下：节点A在具有比自己更小的msm-id的潜在父亲节点列表中选择一个节点，比如节点B，并向其发送一个单目标JOIN-REQ分组。B接收到JOIN-REQ后，假如它已经加入了该组播会话，就送回一个 JOIN-ACK分组。否则，它发送一个JOIN-REQ.PASSIVE给它的潜在父亲。假如A接收 JOIN-ACK失败或在发送了JOIN-REQ之后收到一个JOIN-NAK，它就执行“枝叶重构” （ Branch ReconstrUCtion，BR）过程。BR过程的作用就是在共享分发树发生变化的时候局部地动态修复分发树。它采用扩展环搜索算法使得本节点成功地加入已有的共享分发树，从而加入组播会话。

----每个群组节点需要周期性地广播信标消息（beacon）给它的邻居。信标消息包含节点id、msm-id、成员关系状态、登记的父亲和孩子的id以及它们的msm-id。AMRIS协议通过信标机制监测链路失效。假如在一个给定的时间间隔内没有接收到邻居节点发送的信标，节点就认为邻居已经移出了通信范围。假如先前的邻居是一个父亲节点，该节点必须给一个新的潜在父亲节点发送JOINREQ以重新加入会话中。假如此节点加入任务失败或没有合格的邻居存在，它将执行“枝叶重构”（ Branch Reconstruction， BR）过程。

----数据转发通过树中的节点完成。每个节点只对来自登记的父亲或孩子节点的组播数据分组才进行转发。假如树链路损坏，分组将丢失直到树被重新构造为止。像ODMRP一样，AMRIS也不需要独立的单播路由协议。

----CAMP

----借助核心的网格协议（CAMP，CoreAssisted Mesh Protocol）通过创建一个共享的网格结构支持组播，它需要底层单播路由协议的支持。CAMP 将网络中的节点分为双工成员、单工成员和非成员。双工成员是组播网格的完全成员，既发送又接收；而单工成员紧紧向其他群组成员发送组播数据；非成员不参与组播数据的传送。

----CAMP的基本思想是设置若干“核心”节点，普通节点通过向“核心”发送JOINREQUEST来加入群组。这样能够起到限制JOINREQUEST 分组的流量的作用。然后，接收节点再根据单播路由信息来优化。

----具体地说，CAMP包括网格创建和维护两个阶段。一个想加入组播网格的节点首先判定它是否有已经是网格成员的邻居。假如有，此节点通过一个 CAMPUPDATE声明其成为一个成员。否则，此节点或者发送一个JOINREQUEST给一个群组“核心”，或者尝试通过扩展环搜索的方法找到一个成员节点。任何双工成员都可以用一个JOIN-ACK响应。

----接收节点周期性地审查它的分组缓存区，判定作为接收分组来源的邻居节点是否是在到源节点的反向最短路径上。假如不是，此节点将沿反向最短路径给源节点发送一个HEARTBEAT或PUSHJOIN消息。这个过程保证了网格包含从所有接受者到所有发送者的反向最短路径。CAMP依靠于底层的单播路由协议，并要求单播路由协议能够在有限的时间内给出到所有目的节点的正确距离。基于BellmanFord算法的路由协议不能用于CAMP。CAMP也需要作一定的扩展才能用于按需的单播路由协议。

几种协议的比较

----下表总结了这几种组播路由协议的要害特征。

AMRoute

----在简单性和发送节点个数的可扩展性方面给出了一定的承诺。然而，单向链路的存在妨碍了可靠的数据递交。当移动性更强的时候这个问题就更严重。AMRoute的其他缺点是存在回路、树的效率较差。针对AMRoute的可能的改进是在选择树枝时考虑可达性信息。使用这种方法，单向链路的影响就会减小。另外，给协议增加一点可适应性（例如，周期性发送TREECREATE）可建立更优化的树。最重要的是，必须应用一种防止回路的机制来提高AMRoute的效率。

----ODMRP

----通过构造网格提供冗余路径，从而增强了协议对节点移动的可靠性。当网络高度移动时，协议不产生额外开销，因为没有因链路断开而引发任何控制分组。然而，当存在大量组播发送节点时，协议可能会承受过多的控制开销。对大群组的可扩展性必须增强。

----AMRIS

----AMRIS的性能对移动性和网络负载很敏感。性能较差的主要原因是控制分组的数量和信标的大小。信标分组将会引起一些分组碰撞，在更密集的网络中，性能会变得更差。我们认为使用类似于CAMP的信标机制会改进AMRIS的性能。假如只有当一个给定期间内没有分组传输时才发送信标，节点信息仍然能够传递给邻居节点，同时信标传送的数量就能减少。另外Sid的选择会影响树的外形并且可能影响它的性能。关于Sid选择算法的研究将有助于改进AMRIS。

----CAMP

----当群组增大时具有良好的控制分组数量的可扩展性。因为JOINREQUEST当到达一个网格成员时就停止扩散，所以当节点数量和群组成员数增加时，CAMP不会引起组播更新分组的指数增长。然而，当节点移动时，在网络收敛性和控制分组数量增长等方面的表现上，它是依靠于单播路由协议的。

----研究表明，基于网格的协议在移动场景中的性能明显比基于分发树的协议要好。在基于分发树的协议中，当路径由于节点移动而失效时，分组必须被缓存或丢弃直到树被重建。另一方面，面对节点移动和链路断开，网格中的冗余路径为数据递交提供了可选择的路径。当主路径正在重构时，数据分组仍然能到达目的节点。