高效率的小规模Ad Hoc组播路由协议

摘 要：Ad Hoc网络中，组播路由协议具有广泛的应用前景。但由于网络拓扑的变化和节点能量的限制，设计具有高效传输能力的组播路由协议比较困难。通过综合比较表驱动路由协议与按需路由协议的优缺点，并且考虑Ad Hoc网络中节点的移动性以及路由发现与路由维护的方法对传输效率的影响，在无状态组播路由的基础上，使用表驱动与按需路由驱动相结合的路由方法，提出一种新的组播路由协议，使传输效率有较高的提升。

关键词：自组网; 组播路由协议; 传输效率; 按需驱动

中图分类号：TN915-34文献标识码：A

文章编号：1004-373X(2011)01-0007-04

An Efficient Multicast Routing Protocol in Small Scale Ad Hoc Network

LIU Xiao-pei, LI Ying, ZHANG Hao, XU Shu

(Chongqing Communication University, Chongqing 400035, China)

Abstract： The multicast routing protocol has a wide application in Ad Hoc network. It is hard to design a multicast routing protocol with high efficient and transmission capability for the change of topology. On considering the mobility, discovery and maintenance of routing in Ad Hoc network, a new efficient routing protocol based on the stateless multicast routing protocol is proposed to improve the transmission efficiency.

Keywords： Ad Hoc; multicast routing protocol; transmission efficiency; on-demand driven routing

0 引 言

Ad Hoc网络终端具有路由功能，是由一组带有无线收发装置的可移动节点组成的一个多跳的临时性自治系统。因其具有独立自组网能力以及无中心、动态性、易于铺设等特点被广泛应用于紧急救援、道路交通、军事战场、偏远野外和探险等临时信息系统建设，成为当今的一个研究热点［1-2］。

基于Ad Hoc的组播路由协议有多种分类方法，┮话悛把它们按组播传输结构可分为树状组播路由协议、栅格状组播路由协议、混合性组播路由协议和无状态组播路由协议。在小规模的Ad Hoc网络中，无状态组播路由协议因其独特的性能和特点得到众多研究人员的关注和认可。

无状态组播路由协议是基于这样一种考虑：基于树和基于网格的组播路由协议都需要进行路由树或网格的创建和维护，Ad Hoc网络频繁的拓扑变化导致这种过程的开销非常大。为了减少这种开销，无状态的组播路由采用组播发送者集中管理组播成员关系的方法，在分组的报头中显式的列出组播的接收者，中间节点不需要维护动态的组播路由信息。无状态的组播路由主要用于小规模的组播，并由单播路由协议根据分组的报头转发到各个接收者。

1 DDM协议

DDM［3］(Differentail Destination Multicast)是┮恢知典型的无状态组播路由协议，它由组播发送者负责对成员的管理。当节点加入组播组时，利用单播路由，发送JOIN消息到组播发送者，JOIN消息包括组播的ID号，加入节点的ID号，发送者的ID号。组播发送者接收到JOIN后，将加入节点的ID号加入成员列表中，加入节点就成了一个组播发送者的接收成员。

成员列表的更新是发送节点主动完成的。发送成员在数据分组中周期地捎带一个查询标志，接收成员通过单播一个JOIN信息来响应发送成员的“查询”。当一个成员需要退出组播分组时，显式地发送一个LEAVE消息。

DDM议的关键技术是基于组播接收成员的转发报头计算与编码，DDM采用差分编码。它的控制包有四种类型，即JOIN,ACK,LEAVE和RSYNC。┣叭种控制分组用于成员控制算法，RSYNC用于节点与其上游节点的组播成员列表同步。DDM的包格式如图1所示。其包格式分数据包和控制包，数据包主要包括DDM报头和有效负荷。

图1 DDM的包头格式

每一个DDM块对应一个下游邻居。DDM块包括有期望的接收者、DDM块类型、DDM块序列号。有┤种类型的DDM块：空(Empty)块、刷新(Refresh)块、差分(Difference)块，简便记为E,R,D。在无线广播网络中，到不同邻居节点的DDM块可能汇聚到一个分组中，以减少传输次数。

DDM的包头中需要转发的信宿节点的集合称作FS。在组播的源节点，FS和成员列表是一致的。在其他节点，FS是所有上游邻居节点FS的并集。节点到达FS中的信宿节点的路径是不同的，根据转发的┫乱惶，可将FS中的信宿节点划分为不同的子集，成为方向子集DS。每个DS对应一个下游邻居节点。┟扛霆DS还包括一个强制刷新标志，用于转发组的同步。节点在接到数据包以后，首先比较序列号，如果已经处理过，则丢弃该包，并根据DDM快的期望接收节点，定位自己的DDM块。如果是R块，则创建新的FS，如果是D块，则更新FS，FS=∪FS。

当采用差分编码时，在DDM块中仅包含节点的差分列表，因此保持上游节点的FS表与下游节点的DS表的一致性是十分重要的，DDM用序列号来维护表的同步。每个DDM块都有一个序列号，来标记上游节点FS表的序列号为，每发一个分组序列号加1，发E块时不变。当节点检测到序列号不连续时，就发送一个RSYNC消息到相应的上游节点，接收到RSYNC的节点根据发RSYNC消息的节点的ID定位将发送DDM相应的分组DSS，并更新列表，从而使列表同步。

2 对DDM的分析和扩展

评价一个协议好坏的标准有很多，其中数据传输效率是很重要的一条。在Ad Hoc环境中，能量和带宽是有限的，怎么样在一定的时间里用尽可能少的能量传输尽可能多的数据，一直是人们努力实现的技术。DDM是一个适用于规模小、移动速度快的Ad Hoc环境，但从DDM的包格式来看，其控制部分在整个包中占了很大比例，这将严重影响协议的传输效率。一般情况下，按需路由协议的包头都带有大量控制信息；表驱动的路由协议则需要大量的控制信息。

表驱动路由协议又称为主动式的路由协议，该路由协议试图维护网格中各个节点到其余所有节点的最新路由信息，所有路由信息保持一致。每个节点都维护┮徽弄或几张到网络中其他节点的信息表，当网络拓扑结构发生变化时，节点通过交互信息来实时地维护网络路由表。在表驱动协议中，由于每个节点需要实时地维护路由信息，这样在网络规模较大、拓扑变化较快的环境中，大量拓扑信息更新消息会占用过多的信道资源，使得系统效率下降。按需路由协议是只有在节点有数据要发送时，才激活路由发现机制寻找到达目的地的路由，很多控制信息加在数据包上，减轻了网络负担，灵活性、健壮性较好，但其包格式的控制部分占比例太大，影响传输效率［4］。

为了保持协议的传输效率和健壮性，可以取长补短，使用表驱动和按需驱动两种方式相结合的协议。即组播路由的发现和维护使用按需驱动的方式，而传输组播数据包则用表驱动的方式。这里提出一种同样适用于规模小，移动速度快的Ad Hoc环境的新的组播路由协议EDDM。

3 EDDM组播路由协议

EDDM(Efficient Differentail Destination Multicast)是一种靠单播链路来进行分发的组播协议，它是使用按表驱动和按需驱动混合的一种高传输效率的组播协议。它内嵌的单播协议也是DSR协议。

3.1 EDDM的包格式

EDDM主要有JOIN,REQ,ACK,DATA,LEAVE和RSYNC六种包格式，其中，JOIN,REQ,ACK,LEAVE和RSYNC是控制包，它们的包格式是DSR格式，如JOIN的包格式，如图2所示。JOIN,REQ,LEAVE是用来维护和发现路由的，RSYNC是用来同步数据包的。这些包中含有部分控制信息，包头相对较长。

图2 JOIN包的格式

DATA包是数据包，它的格式相对就简单多了。为了提高传输效率，EDDM的数据包不包含控制信息，控制信息都写在节点内部的表中，其格式如图3所示。

图3 DATA包的格式

3.2 组播路由的发现和维护

EDDM的路由维护和管理是由组播的发送者来实施的。其过程如下：

(1) 想加入组播的节点通过向源节点单播一个JOIN消息来加入组播组，源节点收到JOIN消息后，把发送JOIN的节点加入组播组然后单播REQ消息给请求的节点。

(2) 中间节点在收到JOIN消息后，就认为自己是组播的转发节点，并记下JOIN消息的上一个节点、下一个节点以及JOIN消息的发送节点，从而建立了┮恢华组播链路。

(3) 组播源节点周期性的组播确认信息REQ，当成员节点收到REQ后，将回复JOIN消息。

(4) 如果组播成员节点在规定的时间内没有收到REQ消息，那么它将继续周期性的发送JOIN消息，直到得到源节点的回应。

(5) 如果某条链路在数据转发的过程中发生断链，那么发现断链的节点将使用单播的形式发送RSYNC消息给与本链路相关的各个目的节点。目的节点收到RSYNC消息后将重启单播寻路机制，然后向源节点发送JOIN消息，从而达到维护路由的目的。

(6) 如果某个目的节点想退出组播组，则发送LEAVE消息给源节点，那么沿途所有收到LEAVE消息的中间节点都会取消针对退出的目的节点的数据转发。源节点如果在规定的时间内没有收到某个成员的JOIN消息，也没收到LEAVE消息，会将该节点从组播成员中删除。而中间节点如果在一定的时间内（这个时间设定为刷新时间的2倍）没有收到经过它的JOIN消息，则认为自己不再是中间节点，不再转发数据。

3.3 EDDM数据包的转发

当源节点广播数据包时，源节点和目的节点之间已经通过发送JOIN消息和REQ消息建立起了组播路由。组播路由表是独立于单播路由表的，它只是从靠JOIN消息中解读出有用的信息保存在JION所经过的节点的表中。

(1) 当一个中间节点收到一个组播数据包，先检查是不是收到过同样的包，如果以前收到过则销毁。

(2) 如果第一次收到这个包，则检查这个包经过的上一个节点号和它的组播号并将他们跟自己的组播路由表对比，看其是否与自己相关如果不相关则销毁。

(3) 如果这个数据包与自己相关，则立即给上游邻节点发送ACK消息并广播数据包，然后等待下游邻节点的ACK消息。

(4) 如果在规定的时间内没有收到下游邻节点的ACK消息，则认为该处断链。

4 仿真与分析

为了评测EDDM协议的性能，使用NS2仿真工具对其性能进行模拟研究，并与经典组播协议ODMRP进行比较。网络中节点通信半径最大为250 m，信道能力为2 Mb/s，节点的无线传输模型选Two-Ray Ground传输模型，仿真过程中每个组播组中仅有一个信号源发送数据；仿真时间为400 s，节点移动速度为2~20 m/s。节点在1 000 m×1 000 m的矩形平面空间中进行随机运动移动。

本实验针对ODMRP和EDDM的数据包传输效率进行了仿真比较，比较结果如图4所示。从图中可以看到，组播成员节点相对较少的情况下，EDDM的数据包传输效率明显优于ODMRP。但随着成员节点个数的增多，其性能逐渐下降,说明EDDM的扩展性不强。在这里没有从仿真中严格比较DDM和EDDM在数据传输效率方面的优劣，但给出了EDDM和ODMRP的比较。在成员节点数目较少的情况下，他的数据传输效率都优于ODMRP，但这种优势也都随着组播成员个数的增多而变小。

图4 EDDM和ODMRP的数据包传输率比较结果

从传输单个数据包的角度来看，EDDM的效率与DDM的效率相比差别很大。现在设DDM的源节点周围有m个下游节点(也就是说第一次转发的数据包中需要带m个DS块)，设每个DS块中有n个目的节点，m和n的最小值为1，每个段按最小8位，x为数据大小，гDDM的数据部分占总大小比例为

图5 DDM和EDDM数据部分在数据包中的比例

5 结 语

EDDM是一种使用于小规模的高效组播路由协议。它从无状态组播路由协议延伸而来，是一种树状结构的协议，但其状态结构的组织非常松散，类似于无状态的组播结构。该协议充分考虑了表驱动与按需路由驱动的优缺点，是从实际应用出发，使用二者相结合的方式形成的一种高效数据传输协议。从各个方面的比较来看，EDDM确实有效地保证了在小规模、高速度Ad Hoc网络中的高效数据传输。

参 考 文 献

［1］郭永洪,李光胜,毛启容,等.Ad Hoc网络组播路由协议研究现状、问题和方向［J］.计算机应用及软件,2006,23(4):8-10,65.

［2］孙宝林,李腊元,李相棚.移动Ad Hoc网络多播路由协议的研究进展［J］.计算机工程与应用,2004,40(32):139-143.

［3］JI Lu-sheng, CORSON M Soctt. Explicit multicasting for mobile Ad Hoc network[J]. Mobile Networks and Applications, 2003,8(1): 535-549.

［4］郑少仁,王海涛.Ad Hoc网络技术［M］.北京：人民邮电出版社,2004.

［5］LEE S, SU W, GERLA M. On-demand multicast routing protocol(ODMRP)[C]// Proceedings of IEEE WCNC′99. New Orleans, LA: IEEE, 1999: 1298-1302.

［6］LUO Jun-hai,YE Dan-xia. A survey of multicast routing protocol for mobile Ad Hoc networks ［C］// IEEE Communications Surveys & Tutorials.[S.l.]: IEEE, 2009, 11(1): 78-91.

［7］KALIAPERUMAL B, EBENEZER A, Jeyakumar. Adaptive core-based scalable multicasting networks ［J］. Proc. IEEE INDICON, 2005, 29(3): 198-202.

［8］SOON Y O, PARK J S, GERLA M. E-ODMRP: enhanced ODMRP with motion adaptive refresh ［J］. Proc. ISWCS, 2005, 49(17): 211-217.

［9］YUYao,ZHOUYu. Impact of Interference on multicast throughput over Ad Hoc Networks［R］. Fifth International Joint Conference on INC,IMS and IDC, 2009.

［10］TIAN Ke, ZHANG Bao-xian. Destination-driven on-demand multicast routing protocol for wireless Ad Hoc networks ［R］. IEEE Communication Society subject matter expert for publication in the IEEE ICC, 2009.

作者简介：

刘晓培 男，1981年出生，硕士研究生。主要研究方向为Ad Hoc网络组播研究。

李 颖 男，博士,副教授,硕士生导师。主要研究方向为 Ad Hoc网络。

张 豪 男，1986年出生，硕士研究生。主要研究方向为自组网组播协议研究。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文