基于贪婪覆盖集的MANET自适应组播路由算法研究.doc

基于贪婪覆盖集的MANET自适应组播路由算法研究
摘 要：MANET所具有的分布式、多跳、自组织、动态拓扑、时变信道、资源受限等特点，使得传统的有线网和有中心无线网络的路由算法和协议无法在MANET中直接应用，为此需要根据MANET的特点设计专门的组播路由算法和协议。结合基于Mesh和基于树形转发结构两类MANET组播路由的优点，提出一种基于贪婪覆盖集（Greedy Set Cover）的MANET组播路由算法ADMMR（Adaptive Distributed MANET Multicast Route based on Greedy Set Cover），节点可以动态地、分布式计算各自的转发列表，根据转发列表进行组播数据的转发，节省有限的带宽，减少信道冲突，降低网络负载，提高算法的总体性能。最后运用OPNET验证了该算法的有效性。
关键词：MANET 组播 自适应 分布式 ADMMR
An adaptive multicast routing for MANET based on Greedy Cover Set
Abstract：These special characteristics such as distributed, multi-hop, self-organizing, dynamic topology, time-variant channels, and limited resources etc make the traditional routing algorithms and protocols for wired networks and centered wireless networks can’t be used in mobile ad hoc networks directly. So the appropriative multicast routing algorithms and protocols for mobile ad hoc networks must be designed. In the paper, Combining merits between the Mesh-based and the Tree-based MANET multicast protocol, we proposed ADMMR protocol (Adaptive Distributed Multicast Route based on Greedy Set Cover), whose node can computes forward list dynamically and distributed. This mechanics can save the limited bandwidth, decrease the channel collision and reduce the total overhead of the MANET. At last, the ADMMR is validated by OPNET。
Key words：MANET Multicast Adaptive Distributed ADMMR

6

1、引 言
移动Ad Hoc网络(Mobile Ad Hoc Network——MANET)是一个复杂的分布式系统，它由能自由移动和动态地自组织成任意网络的无线节点组成，使人员和设备在没有固定基础设施的地方无缝地连接成网络或连接到因特网。传统的基于有线网络的组播路由协议都无法直接应用到MANET网络中。在MANET技术的研究中，组播路由协议是个相对较新的领域，20世纪90年代以来，研究者相继提出了一系列的MANET网络组播路由协议[1]，如组播自组网按需距离矢量路由协议MAODV[3](Multicast Ad Hoc On-Demand Distance Vector Routing Protocol)、按需组播路由协议ODMRP[4](On-Demand Multicast Routing Protocol)、核心辅助的网格协议CAMP[5](Core Assisted Mesh Protocol)、向前转发组组播协议FGMP[6]Forwarding Group Multicast Protocol)、使用递增标号的组播路由协议AMRIS[7](Ad Hoc Multicast Routing Protocol Utilizing Increasing ID Numbers)、位置引导的树构造算法LGT[8](Location Guided Tree Construction Algorithm)、差异目标组播路由协议DDM[9]（Differential Destination Multicast）等。不同类型的组播路由协议具有其自身的优缺点，适应于不同的网络环境。MANET网络组播路由存在的问题不能通过某一种组播路由协议完全解决，同时由于MANET网络应用还需要将固定网络和移动环境结合起来进行综合应用，因此MANET网络环境中的组播应用还需要进行更加深入的研究[2]。
本文研究MANET中的组播路由协议[10][14]，通过分析基于树形转发结构组播路由协议和基于Mesh的组播路由协议的特性，提出基于贪婪覆盖集的MANET组播路由算法ADMMR（Adaptive Distributed MANET Multicast Route based on Greedy Set Cover），综合以上两类MANET组播路由的优点来提高总体性能，最后通过OPNET对其性能进行分析和验证[12][13]。
2、基于贪婪覆盖集的MANET组播路由算法ADMMR
基于贪婪覆盖集的MANET组播路由算法ADMMR，首先由核心节点发起构造基于Mesh的组播组，然后根据近似最小覆盖集的算法GreedySetCover()构造转发结构并转发组播数据，即每个Mesh成员节点通过近似最小覆盖集的算法GreedySetCover()计算转发列表（即最小覆盖集），然后只向转发列表中的节点转发组播数据包，再由转发列表中的节点重复这种操作，直至覆盖所有的组播组成员节点。ADMMR算法主要内容如下：
2.1核心节点的选取
MANET中每个组播组有一个逻辑核心节点，是负责新成员的发现、创建和维护Mesh转发结构。核心节点不是预设的，也不是固定的，能根据网络的连接性及成员关系变化而调整。核心节点的主要工作是管理组播组，所有组播数据并不由核心节点进行转发，而是在发往核心节点的途中被Mesh成员收到，然后由Mesh成员节点通过转发列表在Mesh范围内进行转发。
核心节点的选取流程如下：
step1 当接收节点想要加入组播组时，先确认自己是否收到过组播通告，如收到过组播组的通告，则不参加核心节点的选取，且当前核心节点保持不变。
step2 未收到过组播组通告的节点则把自己当作核心节点，开始周期性的向它的邻居节点传送组播报告，并在组播通告中设置至核心节点的距离标记为0。
step3 节点只转发从某邻居节点收到的具有最高ID的组播通告。
step4 最终各个相连的节点中只有一个核心节点。如果一个节点比组播组接收端的其它都早，那它将成为组播组的核心节点。如果N个节点同时加入，具有最高ID的节点在一段有限时间内成为核心节点。
step5 当网络分区时，核心节点的选取将发生在不包含核心节点的网络分区，之前核心节点所在的网络分区的核心节点将保持不变。当节点探测到分区后，将重复以前的加入组播组或参与核心节点的选取的过程。
2.2组播通告和连通表
ADMMR算法中只有一种单一的控制消息――组播通告。组播通告中包含了各种控制字段如序列号、组播组ID、核心节点ID、父节点域等参数。同一个核心节点发送的组播通告中最新的组播通告具有最高的序列号。通过组播通告中包含的信息，节点可以完成核心节点的选取，维护（组播组外）发送节点至组播组的单播路由，通告节点加入、退出组播组，建立组播组转发结构。
自认为是核心节点的接收节点周期性的广播组播通告。当组播通告穿越整个网络，将在每个节点上建立一张网络连通表。连通表存储一条或多条通往核心节点的路由信息，通过连通表节点可以建立组播组转发结构，从发送节点路由组播数据包到接收节点。节点储存来自所有邻居节点的组播通告中的数据，最新的组播通告覆盖序列号低的组播通告，节点在连通表中只保存关于组播组的最新组播通告信息，包括收到组播通告的时间，来自哪个邻居节点等等。同时节点根据连通表的表项生成自己的组播通告，利用组播通告，传输1跳邻居中属于Mesh成员的节点信息，通过Mesh转发结构中1跳邻居节点信息，节点便可以获取Mesh转发结构中的所有2跳邻居节点信息。当有多个组播组存在时，节点就为每个组播组保留一张连通表，节点收集合计所有最新的组播通告，并在每个组播通告的间歇周期性广播。
2.3 Mesh转发结构的建立
通过组播通告在整个网络中洪泛，移动节点会根据通告信息各自建立连通表。初始情况下，接收节点刚开始先将它发送的组播通告中Mesh成员编码置1，非接收端节点设置Mesh成员编码为0。当非接收端节点在它们的连通表中至少有一个Mesh子节点时，它们将认为自己也是Mesh成员并增加Mesh成员编码为2。非接收端节点连通表中的邻居节点满足以下条件时为Mesh子节点：（1）Mesh成员编码大于0（2）表中的邻居节点到达核心的距离大于非接收端节点本身至核心的距离。（3）收到与该项相关的通告在组播通告时间间歇内 (保证邻居节点依然存在)。
如果节点有一个Mesh子结点，因此它成为Mesh成员，意味着它在接收端和核心节点之间的最短路径上。初始情况下，所有的接收节点把自己作为Mesh成员节点，并将发送的组播通告中把节点类型设置为Mesh成员节点。移动节点何时产生、发送组播通告，主要取决于当前时间点上移动节点的状态。当移动节点测到Mesh成员状态发生变化时，如核心节点发生变化，或收到一个最新的组播通告，或首次发现一个新的子结点，或丢失了子结点等，都将触发移动节点重新发送新的组播通告。
2.4贪婪覆盖集算法
采用贪婪算法计算节点两跳邻居节点的支配集，并应用到组播包在Mesh范围内的转发过程中，以最少的转发次数转发组播数据包。贪婪覆盖集算法GreedySetCover()递归的选择一跳邻居节点以覆盖尽可能多的两跳邻居节点，重复这种选举过程直至覆盖所有的两跳邻居节点。
如图1所示，用N(u)代表节点u的一跳邻居节点集(包括节点u)，N(N(u))代表N(u)的一跳邻居节点集(也就是节点u的两跳邻居节点集)。节点v收到来自u的消息后，选取最少数目的节点转发数据包以覆盖整个N(N(u))。由于节点u是先前的转发节点，N(u)中的节点已经收到过数据包，而同时属于N(v)的那些节点将再次收到数据包。因此，节点v需要从节点集B(u，v)=N(u) - N(u)∩N(v)中计算自己的转发表F(u，v)，以覆盖U(u，v)=N(N(v)) – N(u)∪N(v)中的节点。在贪婪覆盖集算法中，选取具有最多邻居节点的节点，将其加入到支配集中，并从原图中移除该节点以及与该点连接的所有边。然后在图中的剩下部分重复执行以上操作，直到图中没有移动节点或边留下。
u
v
N(u)
N(v)
N(N(u))
N(N(v))

图1 邻居节点集
Fig.1 Set of the neighbor node
贪婪覆盖集算法GreedySetCover()的计算过程如下：
F(u，v) = [， ，…，] 满足：B(u，v) satisfying
转发表F(u，v)的计算过程即不断在B(u，v)中选择节点，且在U(u，v)中具有最多未被覆盖节点数，其中，Z是U(u，v)的子集，表示已被覆盖的节点；表示Vi在U(u，v)中的邻节点集；K是的集合。具体步骤如下：
step 1:Let F(u，v)=[] (empty list)，Z = (empty set)，and K = ∪ ，where = N(vi ) ∩U (u，v) for B(uv)
step 2:Do
step 3:Find the set whose size is maximum in K
step 4:F(u，v) = F(u，v) || ，Z = Z ∪ ，K = K –，and = - ，for all ∈ K
step 5:Until no new node is added to Z = U(u，v)
step 6:return F(u，v)
由GreedySetCover()算法可知，循环体最多执行min{|V|，|E|}次，而循环体内的贪心选择语句最多执行|V|次。删除与v关联的边最多执行|E|次，显然GreedySetCover()算法是一个多项式时间算法。
2.5组播数据包的转发
组播数据包从发送节点到目的节点经过两个阶段，第一阶段：当发送端发送一个组播数据包时，将数据包封装在一个单播数据包内，单播的目的地址设置为其父节点。节点收到封装数据包同样向其父节点进行转发。通过这种方式封装的数据包以单播的形式一跳一跳的向核心节点移动；第二阶段：当数据包到达Mesh成员节点时，Mesh成员节点从单播包中取出组播数据包，根据GreedySetCover()计算自己的转发列表F(u，v)，并向转发列表中的节点进行转发。Mesh成员节点收到数据包后，一般会先对数据包的来源进行判断，然后决定或者丢弃数据包、或调用贪婪覆盖集算法计算自己的转发列表，通过转发列表进行组播数据的转发。Mesh成员节点转发数据包的算法如下：
Step1:节点v收到来自协议栈上层传输层的组播数据包时，计算自己的转发列表F(*，v)，并将自己得转发列表F(*，v)附加到组播数据包中，最后随组播数据包一起发送。
Step2:节点v收到来自Mesh成员u的组播数据包，首先查看其转发列表F(*，v)：
①若节点v包含在F(*，v)中时，则节点v通过贪婪覆盖集算法计算自己的转发列表F(u，v)，附加到组播数据包中，然后根据F(u，v)转发组播数据包，其转发列表F(u，v) 随组播数据包一起发送。
②若节点v不包含在F(*，v)中时，直接丢弃数据包。
Step3:节点v收到来自非Mesh成员节点的组播数据包时，计算自己的转发列表F(*，v)，附加到组播数据包中，然后根据F(*，v)进行转发，其转发列表F(u，v) 随组播数据包一起发送。
3、算法的仿真
使用OPNET Modeler[11]对MANET组播路由协议进行仿真分析。在仿真试验中，采用传输成功率(Packet Deliver Ratio)、协议控制开销（Control Overhead）、协议总开销（Total Overhead）等指标来衡量不同算法的性能。为了通过实验看到在不同的负载和不同的网络拓扑变化频率下ODMRP、MAODV和ADMMR这三种路由算法的性能选择了表1所示仿真参数进行实验设置。为保证仿真实验的公平性，每次仿真试验设置5个不同的种子值（seed），仿真过程中所有的计时器均设置为3秒。
试验一：mobility=0，5，10，15，20；（m/s）
试验二：traffic load=1，5，10，25，50；（pkts/sec）
试验三：member=5，10，20，30，40；
表1 仿真参数表
Table 1 Terms of parameters in simulation
Simulator
OPNET Modeler 11.0
Total Nodes
50
Simulation Time
100s
Simulation Area
1000m×1000m
Node Placement
Random
Mobility
Random Way-point
Pause Time
10s
Min-Max Vel.
0 – 20m/s
Transmission Power
15dbm
Channel Capacity
2Mbps
Mac Protocol
IEEE 802.11
Data Source
MCBR
Num. of pkts. sent per src.
1000
通常对于MANET组播路由算法，影响其性能的三个主要因素为节点的移动性、（发送端）负载大小以及组播组的规模。本文主要从这三个方面分析ADMMR组播路由算法的性能变化，并与MAODV和ODMRP（分别代表两种不同组播转发结构的MANET组播路由算法）的仿真结果进行对比分析，验证ADMMR组播路由算法的先进性。
l 移动性
图2反映了ADMMR、ODMRP和MAODV在不同移动性场景下，传输成功率、协议控制开销、协议总开销的仿真结果。

图2 移动性影响
Fig. 2 Mobility influence
从图2中可以观察到以下规律：①在节点移动缓慢的情况下，MAODV的总开销较低传输成功率较高，这主要得益于树形转发结构的转发高效性。但随着节点的移动越来越快时MAODV的传输成功率出现了很大的波动，在拓扑频繁变化的情况下，树形转发结构的重构导致了传输成功率的不稳定性；导致了整体性能的下滑。②ADMMR的传输成功率无论何时均高于ODMRP，并且在节点移动越快而导致拓扑频繁变化时，其传输成功率一直高于MAODV和ODMRP。算法总开销低于MAODV和ODMRP，表现出很好的适应性。
负载量
图3反映了ADMMR、ODMRP和MAODV在不同网络负载条件下，传输成功率、协议控制开销、协议总开销的仿真结果。

图3 负载量影响
Fig 3 Traffic load influence
表3中可以看出：①组播数据包较小时，MAODV的传输成功率较高。组播数据包不断增大时，ADMMR的传输成功率高于MAODV和ODMRP；②ADMMR的传输成功率无论何时均高于ODMRP，这是由于ADMMR在Mesh中进行组播数据包的转发是有限转发，减少了信道冲突，提高了传输成功率；③ADMMR的控制开销始终低于MAODV和ODMRP，而整体开销一直介于MAODV和ODMRP之间，表现出良好的平衡性。
l 组规模
图4反映了ADMMR、ODMRP和MAODV在不同的组规模下，传输成功率、协议控制开销、协议总开销的仿真结果。
从图4中可以看出，ADMMR在MANET组播组规模大于20的网络环境下，传输成功率表现出较好的性能；并且ADMMR算法控制开销依然低于MAODV和ODMRP的控制开销，而算法整体开销处于MAODV和ODMRP之间。

图4 组规模影响
Fig 4 Members influence
通过实验可以得出以下结论：基于贪婪覆盖集的MANET组播路由算法ADMMR在传输成功率、降低控制开销和降低网络负载等方面相对于MAODV和ODMRP算法有着明显的改进和优势，也证明了该算法确实可以适应网络拓扑的动态变化，提高转发效率，减少信道冲突，降低控制开销。由此确定ADMMR算法的适用于拓扑变化频繁、网络负载大、组播成员多的应用场景。
4、结语
MANET组播路由算法自提出以来，还处在不断的改进与完善之中。算法的改进主要考虑到MANET自身的特点：拓扑结构变化、能量有限、信道容量等等，有针对性的解决了一些问题，提高了网络的性能。今后，关于MANET组播路由算法还有以下几个方面值得研究：支持单向信道、路由安全、可扩展性和QoS组播路由等方面。随着新一代互联网络技术的不断发展，高性能网络技术在信息技术飞速发展的今天越来越显示出强大的生命力，组播方面的研究将会出现一些新的研究热点。
参 考 文 献
[1] Katia Obraczka, GeneTsudik. Multicast Routing Issues in Ad Hoc Networks[C] International Conference on Universal personal Communications, ICUPC'98, IEEE 1998，751~756
[2] Zygmunt J Hasa and Siamak Tabrizi. On Some Challenges and Design Choices in Ad Hoc Communication. IEEE MILCOM'98, October,1998
[3] E.M.Royer, C.E.Perkins.Multicast Operation of the Ad Hoc On-Demand Distance Vector Routing Protocol. Proceedings of ACM/IEEE MOBICOM' 99, Seattle, WA, Aug, 1999，207~218
[4] S.J. Lee, M. Gerla, and Chian, “On-demand multicast routing protocol，” in Proceedings of WCNC, September 1999.
[5] J.J.Garcia Luna Aceves，E.L.Madruga. The Core-Assisted Mesh Protocol. IEEE JSAC, Aug 1999:1380~1394
[6] Ching-Chuan Chiang, Mario Gerla, Lixia Zhang. Forwarding Group Multicast Protocol (FGMP) for Multihop, Mobile careless Networks. Baltzer Cluster Computing，1998.1 (2):187~196
[7] C W Wu,Y C Tay.AMRIS:A Multicast Protocol for Ad Hoc Wireless Networks[C]. Proceedings IEEE MILCOM'99，Atlantic City, 1999:5~29
[8] J.J.Garcia Luna Aceves，E.L.Madrga. A multicast routing protocol for Ad-Hoc networks. In: Bharat Doshi，eds. Proceedings of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) New York, NY，USA，the IEEE Computer and Comm-unications Societies，1999:784~792
[9] Lusheng Ji, M. Scott Corson.Differential Destination Multicast-A MANET Multicast Routing Protocol for Small Groups.In Proceedings of INFOCOM[C], 2001，1192~1201
[10] S.J. Lee, et-al, “A performance comparison study of ad hoc wireless multicast rotocols,” in Proceedings of IEEE INFOCOM, Tel Aviv, Israel, March 2000
[11] 王文博，张金文.OPNET Modeler与网络仿真.人民邮电出版社，2003，1~250
[12] R. Vaishampayan and J.J. Garcia-Luna-Aceves, Efficient and Robust Multicast Routing in Mobile Ad Hoc Networks , Proc. IEEE MASS 2004: The 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Fort Lauderdale, Florida, October 25-27, 2004
[13] S.K. Das, B.S. Manoj, and C.S. Ram Murthy, “A dynamic core based multicast routing protocol for ad hoc wireless networks,” in Proceedings of the ACM MobiHoc, June 2002
[14] C-K Toh. Ad Hoc Mobile Wireless Networks: Protocol and Systems, 2002.