基于多树的移动自组织网多播路由协议*

梁 潘，冯朝胜

(1.成都航空职业技术学院 汽车工程系，四川 成都610100；2.四川师范大学 计算机学院，四川 成都 610101)

基于多树的移动自组织网多播路由协议*

梁 潘1，冯朝胜2

(1.成都航空职业技术学院 汽车工程系，四川 成都610100；2.四川师范大学 计算机学院，四川 成都 610101)

由于移动节点能量耗尽严重影响了移动自组织网(MANET)路由性能，有效地使用移动节点的能量是非常重要的。为此，提出基于多树的移动自组织网多播路由协议(MTMR)。MTMR协议先计算移动节点能量，将能量低于门限值的节点不参与路由。然后，将参与路由的节点构建不同的树，源节点通过这些树向目的节点传输数据，从而实现多播路由。仿真结果表明，提出的MTMR协议有效地提高了数据传输率，降低了端到端传输时延。

移动自组织网；路由协议；多播；树；能量

0 引言

目前，移动自组织网MANET(Mobile Ad Hoc Network)成为无线网络研究的一个热点。构建MANET的主要目的是通过一群带有无线收发装置的移动节点组成一个临时性、无基础设施的移动网络[1]，该网络具有临时性、多跳路由等特点。

在MANET中，由于节点的通信范围受限，需要多跳方式向其他节点传输数据，并且节点随机移动，网络拓扑变化频繁，这使得在MANET中建立稳定、可靠的路由协议成为一项挑战性的工作。为此，研究人员针对MANET的路由协议进行了大量的研究工作，提出不同策略的路由协议[2-6]。

通常，MANET中的源节点需要向多点传输数据，即一点对多点，就采用了多播(Multicasting)。由于多播是向多个节点传输同样的数据，降低了通信消耗，包括链路带宽以及传输时延。依据路由协议的特性，可将现有的多播路由(multicast routing)协议分为基于树形(tree-based)路由协议[7]、基于 mesh路由协议[8-9]以及混合路由协议。

基于树路由协议在源节点至目的节点间建立树型拓扑。典型的基于树路由协议如自组织多播路由协议AMR(Ad Hoc Multicast Routing)、多播按需距离矢量路由协议MAODV(Multicast Ad Hoc on demand Distance Vector)[10]、可靠多播RM(Reliable Multicast)。而基于mesh的多播路由协议在两节点间建立多条路径，即使链路失败，也没有必要重新计算mesh结构，典型的有CAMP(Core-Assisted Mesh Protocol)、按需组播 ODM（On-Demand Multicast）以及DCMP(Dynamic Core based Multicast)路由协议。

尽管基于mesh路由协议能够在源节点至目的节点间建立多条路径，但是这是以能量消耗为代价的。然而，在MANET中，每个节点的能量是受限的。在设计路由协议时，应考虑节点的能量受限的特性。因为一旦节点能量耗尽，链路就断裂，缩短了网络寿命，必然会引用数据传输中断，增加了数据传输时延，降低了数据传输的效率。

为了最大化网络寿命，应以最小的能量消耗实现有效的数据传输。为此，研究人员也提出面向节点能量消耗的路由协议，如最小传输功率 MTP(Minimum Total Transmission Power)路由[11]、最小-最大电池消耗 MMBC (Min-Max Battery Cost)路由[12]以及可选择的最大-最小传输能量CMMBC(Conditional Max-Min transmission Battery Capacity)路由[13]。

为此，本文考虑节点能量信息，并利用树型拓扑以及多播路由特性，提出基于树的能量感知的多播路由MTMR(Energy of node Tree-based Multicast Routing)协议。MTMR协议首先节点考虑节点的能量，若节点能量小于门限值，则不允许该节点参与数据转发。然后，将节点构建3种不同树，源节点依据这3种树向目的节点传输数据包，提高了数据传输效率。

1 能量消耗模型

MTMR协议考虑了节点的传输能量信息，节点在传输、转发以及接收数据时，均需消耗自身能量。无线电能量消耗主要由两部分组成：运行电子元器件、功率放大器所消耗的能量和接收器所消耗的能量。为了在两节点间传输q bit的数据信息，且两节点间的距离为 d，消耗的能量为：

其中，Eelec表示运行发射器或接收器固定的能量消耗，Efrris表示自由空间传播模型单位功率放大器的能量消耗。

相应地，对于接收q bit的数据包，消耗的能量：

节点依据式(1)或式(2)计算自己剩余能量。

2 MTMR协议

MTMR协议是属于能量感知协议，提高了多播路由的稳定性，同时引用基于多树路由协议的理念，进而提高数据传输的效率。为此，假定网络内所有节点随机划分为三类，分别为组 1(Group-1)、组 2(Group-2)、组 3 (Group-3)。相应地，利用 Group-1、Group-2、Group-3节点分别构建3种树Tree-1、Tree-2、Tree-3。

此外，每节点保持两个表：邻居表(Neighbouring table)和多播路由表(Multicast routing table)。节点通过周期地交互Hello消息建立邻居表。邻居表用于保存邻居节点的信息，包括邻居节点的ID、位置信息。多播路由表用于保存传输数据的路径，格式如图1所示。

图1 多播路由表格式

其中，Source_ID、Destination_ID分别标识源节点、目的节点。Route_class用于标识路由组Group-1、Group-2、Group-3。Route_class=1、2、3分别代表Group-1、Group-2、Group-3。Next_node表示用于转发数据的下一跳节点。

2.1 路由发现过程

当源节点需要向目的节点发送数据包时，就向邻居节点广播路由请求RREQ(Route Request)控制包。RREQ控制包内包含源节点、目的节点以及路径信息（Path Information）等。

当节点接收了RREQ控制包，就将自己剩余能量E与门限值 Eth进行比较，如果大于 Eth，就存储 RREQ，并重播RREQ，致使RREQ控制包传输得更远。同时，将自己的ID加入到RREQ控制包的路径区域（Path Information）。

接收了控制包RREQ时，就将用于向源节点转发路由回复控制包RREP(Route Reply Packet)，RREP控制包携带了、源节点、目的节点、返回路径（Reverse Path Information）、Route_Class。其中，Reverse Path Information记载了传输RREP的路径信息。

2.2 控制包传输过程

邻居节点不断向目的节点转发RREQ控制包，直到目的节点接收。当目的节点接收到不同树的RREQ控制包后，目的节点将沿着该树向源节点传输回复RREP控制包。数据传输如图2所示。

接收到RREQ控制包后，目的节点P、Q、R将这3个树的最后一跳节点作为传输RREP的上级节点，如图2(b)所示。节点P、Q、R选择I作为TREE-1的上级节点、H作为TREE-2的上级节点以及J作为TREE-3的上级节点。图2(c)显示了基于多树的数据传播过程。

图2 MTMR协议的数据传输示意图

3 性能分析

3.1 仿真参数

利用网络仿真软件 NS2.3.5构建仿真平台[14]。考虑1 000 m×1 000 m仿真区域，20～80个移动节点随机分布于仿真区域。同时，选择random way point作为移动模型，每个节点随机地选择移动方向，移动速度从 1～25 m/s间选择。节点的通信范围为150 m。此外，随机选择移动节点作为源节点和目的节点。数据包的大小225 B。仿真时间为10 000 s。

在分析仿真数据时，考虑的场景：移动节点的速度为20 m/s，移动节点数从 20～80变化；考察端到端传输时延、数据包丢失率传输率以及控制路由开销作为评估路由协议的性能指标。

3.2 数值分析

为了更充分地分析MTMR协议性能，选用AODV进行同步仿真，并进行性能比较。选择AODV协议作为参考，原因在于：AODV是经典的按需路由协议，其也是采用RREQ控制包发现路由。在路由发现阶段，当源节点需要向目的节点传输数据时，源节点先广播路由请求RREQ控制包，含有目的节点地址、广播 ID以及遍历的跳数。接收到RREQ数据包后，邻居节点检查自己是否有至目的节点的路由，如果有，就向源节点回复RREP控制包；否则，邻居节点就转播RREQ。图3描述了AODV协议RREQ和RREP的传输过程。

图3 RREQ/RREP的传输过程

(1)某场景路由性能

图4(a)所示，MTMR的端到端传输时延比AODV下降了33.928%。图4(b)所示，MTMR的数据包丢失率下降了55.655%。图4(c)显示MTMR和AODV归一化的路由开销，这说明MTMR在提高端到端传输时延、数据包丢失率时，并没有增加路由负担。

(2)能量性能分析

本次实验分析与节点能量相关的网络稳定时长和网络寿命。其中，稳定时长等于从网络初始开始计算第一节点失效时所经历的时间。而网络寿命数值等于网络内最后一个节点失效时所经历的时间，时间越长，网络寿命越长。

表1列举了10次测试的实验数据。从表1可知，AODV、CAMP、DCMP和 MTMR协议的稳定时长分别为 969 s、1 355 s、1 432 s和1 717 s，而网络寿命分别为5 535 s、5 673 s、8 638 s和8 640 s。这些数据表明，提出的MTMR协议能够有效地延长稳定时期，扩展网络寿命。

图4 某场景的路由性能

4 总结

本文针对移动自组织网络移动节点能量受限问题，提出基于树的能量感知的多播路由MTMR协议。MTMR协议首先利用无线电能量消耗模型，计算移动节点的剩余能量。若移动节点的剩余能量小于门限值，则不参与路由，降低了因节点能量耗尽而中断路由的概率。同时，MTMR协议引用树，源节点依据3种树实现多播路由。仿真结果表明，提出的MTMR协议在端到端传输时延、数据包丢失率以及路由开销性能方面有显著的提高。

表1 稳定时期和网络寿命列表

[1]BALLARDIE T，FRANCIS P，CROWCROFT J.Core based trees(CBT)[J].ACM SIGCOMM Computer Communication Review，2013，23(4)：85-95.

[2]DAS S K，MANOJ B S，MURTHY C S R.A dynamic core based multicast routing protocol for ad hoc wireless networks[C].In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing，2012：24-35.

[3]WU C W，TAY Y C，TOH C K.Ad hoc multicast routing protocol utilizing increasing id-numbers(AMRIS)functional specification.Internet draft[J].IETF MANETWorking Group，2012，3(4)：32-39.

[4]CHIANG C C，GERLA M，ZHANG L.Forwarding group multicast protocol(FGMP)for multihop,mobile wireless networks[J].Cluster Computing，2012，1(2)：187-196.

[5]GARCIA-LUNA-ACEVES J J，MADRUGA E L.The coreassisted mesh protocol[J].IEEE Journal on Selected Areas in Communications，2011，17(8)：1380-1394.

[6]WANG N C.Power-aware dual-tree-based multicast routing protocol for mobile ad hoc networks[J].IET Communications，2012，6(7)：724-732.

[7]Sun Baolin，Li Layuan.On the reliability of MAODV in ad hoc networks[J].In IEEE International Symposium on Microwave，Antenna，Propagation and EMC Technologies for Wireless Communications，2005，23(2)：1514-1517.

[8]XIE J，TALPADE R R，MCAULEY A，et al.AMRoute：ad hoc multicast routing protocol[J].Mobile Networks and Applications，2012，7(6)：429-439.

[9]CALVERT K L，ZEGURA E W，DONAHOO M J.Core selection methods for multicast routing[C].In Proceedings of Fourth International IEEE Conference on Computer Communications and Networks，2009：638-642.

[10]GUI C，MOHAPATRA P.Efficient overlay multicast for mobile ad hoc networks[C].In proceedings of IEEE Wireless Communications and Networking Conference(WCNC)，2013：1118-1123.

[11]SINHA P，SIVAKUMAR R，BHARGHAVAN V.MCEDAR：Multicast core-extraction distributed ad hoc routing[C].In Proceedings of IEEE Wireless Communications and Networking Conference，2009：1313-1317.

[12]SINGH S，WOO M，RAGHAVENDRA C S.Power-aware routing in mobile ad hoc networks[C].In Proceedings of the 4 Annual ACM/IEEE International Conference on Mobile Computing and Networking，2008：181-190.

[13]TOH C K，COBB H，SCOTT D A.Performance evaluation of battery-life-aware routing schemes for wireless ad hoc networks[C].In Proceedings of IEEE International Conference on Communications，2010：2824-2829.

[14]KIM B，LEE D，CHOI T.Performance evaluation for Modbus/TCP using Network simulator NS3[C].2015 IEEE Region 10 Conference，2015：1-6.

Multi-tree-based multicast routing protocol in MANET

Liang Pan1，Feng Chaosheng2
(1.Automotive Engineering，Chengdu Aeronautic Polytechnic，Chengdu 610100，China；2．School of Computer Science，Sichuan Normal University，Chengdu 610101，China)

It is very important to use energy efficiently,since that mobile Ad Hoc network routing performance has been affected by energy depletion of mobile node.Therefore,the energy of mobile node tree-based multicast routing(MTMR)protocol is proposed in this paper.In MTMR,firstly,energy of mobile node is computed,and compared with the threshold,nodes that its energy is less than threshold is not allowed to routing,then rest mobiles are divided into three trees.Source node transmits data to destination by these trees,and the multicast routing protocol is done.Simulation results show that the proposed MTMR protocol can improve the data transmission rate,reduce the end to end delay.

mobile Ad Hoc network；routing protocol；multicast；tree；energy

TN914

A

10.16157/j.issn.0258-7998.2016.11.025

梁潘，冯朝胜.基于多树的移动自组织网多播路由协议[J].电子技术应用，2016，42(11)：95-98.

英文引用格式：Liang Pan，Feng Chaosheng.Multi-tree-based multicast routing protocol in MANET[J].Application of Electronic Technique，2016，42(11)：95-98.

2016-05-10)

梁潘（1978－）,男，副教授，硕士，主要研究方向：人工智能与网络安全。

国家自然科学基金项目(61373163)

冯朝胜（1971－），男，教授，博士后，硕士生导师，主要研究方向：云计算机、网络与数据安全。