链路稳定的Ａｄ Ｈｏｃ网络组播路由协议

刘　琳

摘 要：Ad Hoc网络中，组播路由协议具有广泛的应用前景。但由于网络拓扑的变化，设计具有可靠数据传输能力的组播路由协议比较困难。综合考虑Ad Hoc网络中节点的移动性和节点能量对路由稳定性的影响，选取具有较高性能的链路，使得路由具有较好的稳定性。仿真结果证明，与MAODV协议相比，设计的路由协议明显提高了数据投递率，并大大降低了丢包数。

关键词：Ad Hoc网络；组播路由协议；稳定性；生存时间

中图分类号：TP393文献标识码：B

文章编号：1004-373X(2009)03-007-04

Stable Link Multicast Routing Protocol for Ad Hoc Network

LIU Lin

(School of Electronic Information Engineering,Beijing University of Science and Technology,Beijing,100083,China)

Abstract：In Ad Hoc network,multicast has a wide range of applications.But it is hard to design a reliable routing protocol for the change of topology.On considering the mobility and energy of nodes in Ad Hoc network,this paper proposes a new stable routing protocol,which selects better performance link to make routes stable.The simulation results indicate that it has a higher packet delivery ratio,lower dropped packets than MAODV.

Keywords：Ad Hoc network；multicast routing protocol；stability；life time

0 引 言

Ad Hoc网络终端具有路由功能,是由一组带有无线收发装置的可移动节点组成的一个多跳的临时性自治系统。Ad Hoc网络不依赖于任何基础固定设施，不相邻的节点间进行通信需要中间节点中继。由于网络中的节点可以任意移动，所以网络拓扑是动态变化的。Ad Hoc网络具有独立组网能力，以及自组织性、无中心、动态性、易于铺设等特点，因而被广泛应用于紧急救援、道路交通、军事战场、偏远野外和探险等临时信息系统的建设［1-3］，成为当今的一个研究热点。

路由协议的设计大多着眼于最小跳数路由的研究，即需要通信的源节点和目的节点在选择路由时，选择利用最少数量的中间节点中继就可以到达的路径。由于Ad Hoc网络采用无线通信，并且网络中的通信终端可以自由移动，因此通信能力受到节点移动性、节点能量和通信范围等的影响较大。这就造成了无线链路频繁断裂的可能。当一条路径上的任何一个链路断裂时，这一路径就必须找到另一条可用的链路来恢复连接，或者断裂路径被新发现的另一路径所代替［4］。这些重路由操作大大消耗了有限的网络资源和节点能量，从而极大地降低了网络的通信性能。因此设计一个选择稳定路径的路由协议，尽量减少重路由操作，具有非常重要的意义。

目前也出现了一些对稳定路由的研究,文献［5］利用一种权重的思想进行稳定路由的选择，文献［6］利用GPS定位获得节点位置的思想进行稳定路由的选择，文献［7］利用预测路由生存时间的方法来选择稳定路由。这些都只考虑到节点的移动对路由稳定性的影响，并没有考虑节点能量对稳定性的影响。由于Ad Hoc网络中，节点能量是有限的，一旦能量耗尽，节点将无法工作，使得两节点间的链路断裂，整条路由就会失效。因此考虑路由的稳定性必须考虑能量的影响。

1 链路稳定性模型

在Ad Hoc网络中，整条路由是由两个节点间的链路组成的，因此考虑路由的稳定性，需要选择具有稳定性的链路。两个节点间链路的稳定性主要由两个因素来决定：节点间的距离和节点的能量。信号的强度与信号的传输距离有关，所以链路连接需要两个节点间的距离小于节点信号的有效传输距离。节点的可利用能量越多，在数据发送过程中才能保证路由不会因能量的消耗而失效。

1.1 节点间距离

假设在Ad Hoc网中所有节点的有效传输距离相同，均为R，节点的信号传输能力一致，信号的强度仅与信号的传输距离有关。所以在某一时刻，链路保持连接只需要两个节点之问的距离小于节点信号的有效传输距离R。在移动自组织网中，节点不是固定的，而是可以自由移动的。两节点在这一时刻处在有效传输距离内，在下一时刻可能已经移出这一距离范围。因此，不能用某一时刻的节点间距作为衡量指标。链路保持连接的时间越长，这条链路才能越稳定。

文献［8］提出通过GPS获得移动节点的位置、运动速度和运动方向对链路可能保持连接的时间LET(Link Expiration Time)进行了预测。设某时刻节点i，j可以直接通信，(xi,yi)，(xj,yj)分别为它们的位置坐标，用vi，vj分别表示两节点的速度，用θi，θj分别表示两节点的方向，则节点i，j保持连接的时间预测公式为：

Tij=(a2+c2)R2－(ad－bc)2－(ab+cd)a2+c2

(1)

其中:a=vicos θi－vjcos θj，b=xi－xj，c=visin θi－vjsin θj，d=yi－yj。

1.2 节点能耗

Ad Hoc网络中的节点不仅能看作数据传输的终端，而且可作为路由器来帮助超出传输范围的终端交换数据时进行中继。Ad Hoc网的一个重要问题是活动的节点是能量受限的。目前考虑到能量问题的路由协议并不多。MTPR(The Minimum Total Transmission Power Routing)［9］提出最小化传输中需用的能量，但是它并没有考虑到剩余节点的能量，不能延长每个节点的生存时间。MMBCR(The Min-Max Battery Cost Routing)［10］考虑到了剩余节点的能量问题，它比较每条路由剩余能量最小的节点，选择这些节点中具有最大能量的节点所在路由，但是它却没有考虑到整体的能量消耗问题。

在实际应用中，自组织网中节点通信能量的开销要远远大于数据计算的能量开销，因此可以主要考虑节点在通信时的能量消耗。根据文献［11］提出的模型：

Ec=a•size+ΔE

(2)

其中：Ec表示节点消耗的能量;a为发送单位数据所需消耗的能量;size为数据包的大小;ΔE为节点其他情况下的能量消耗。

从(2)式可以看出能量的消耗与数据传输的大小成线性关系。数据的传输存在发送和接收两种状态，在这两种状态下所消耗的能量不同，设节点初始能量为E0，由(2)式可得节点i的剩余能量：

Ei =E0-Eci=

E0-(ri • sizeri+si•sizesi +ΔEi)

(3)

其中：Eci表示节点已消耗的能量，ri表示节点i接收单位数据消耗的能量，sizeri是节点i接收数据包的大小，si表示节点i发送单位数据消耗的能量，sizesi是节点i发送数据包的大小。

可以看出，每个节点根据自己的数据包的发送和接收就可以得到自己的剩余能量，这样可以节省网络中节点能量信息的传递，节省了开销。

1.3 组播路由稳定性指标设计

由于节点间距和节点能量均对路由稳定性产生影响，因此可以采用通用加权的思想将两者结合起来。设节点i为节点j的下游节点，它们之间的链路为Lij，将由式(1)和式(3)得到的链路生存时间Tij及下游节点i的能量作为链路Lij的稳定性指标，设为Wij，将两个指标的权值分别设为aij和bij，其中aij+bij=1，则该指标为：

Wij=aijTij+bijEi

(4)

Wij值越大，说明Lij稳定性越好。当Tij很小，而Ei很大时，由式(4)得出的结果可能也会符合要求，为避免这样的结果，将上式的权值公式用相乘的形式来写：

Wij = TijaijEibij

(5)

由式(5)得到的Wij只要有一项指标为零，不论其余的指标有多大，得到的总指标都将为零，这样可以避免由式(4)带来的极端情况。将式(5)两端取对数，得到：

lg Wij=Tijlg aij+Eilg bij

此式又成为通用加权公式的形式。因此链路Lij的稳定性指标Wij可用式(5)得到的公式表示。

2 LSMRP路由协议

路由是由两个节点间的链路组成的，将上面得到的链路稳定性指标设计到组播路由协议中，该协议称为LSMRP(Link Stability for Multicast Routing Protocol)。LSMRP是按需驱动的组播树路由协议。

2.1 组播树的创建

组播树的创建过程如下：

(1) 每个组播组有一个组长，负责维护和更新本组的序列号，并定期用Group Hello包向全网广播该组序列号。节点通过发送RREQ-J发起加入组播组请求。如果该节点的组长表中有该组的项目，RREQ-J以单播发送给该组的组长；否则，RREQ-J以广播发送。接收到RREQ-J的节点在组长列表中检查是否有该组的项目，如果没有，节点将RREQ-J的组地址以及RREQ的源地址记录入组长列表。每个RREQ-J包都包含发送该包节点的位置信息，每个接收到RREQ-J包的节点通过计算W值，对链路进行稳定性判断。将W与预先设定好的门限值V进行比较，若W≥V就认为该条链路是稳定的，建立到源节点的反向链路，并将RREQ-J重新广播，否则就认为该条链路不稳定，丢弃该包。

(2) 收到RREQ-J的组播树成员向源节点单播发送RREP-J以回复加入请求。 RREP-J沿RREQ-J传输时建立的反向路径传送。RREP-J传输时，沿途节点在组播路由表中创建对应该组的项目，并把上游节点设置成将RREP-J转发给它的邻居节点。

(3) 源节点在发送完RREQ-J等待一段时间后，通常会接收到多个RREP-J。源节点选择具有最大序列号和最小跳数的路径，并向下游节点单播发送MACT-J。MACT-J沿RREP-J传播时建立的正向路径传输。所有接收到MACT-J的节点在组播路由表中设置下游节点，这样一个更新的组播树就建立好了。

如果源节点在重试若干次加入请求后仍然没有接收到回复，说明该组播组在网络上不存在或者不可达。源节点成为新组的组长，并负责维护该组的信息。

2.2 组播树的维护

(1) 若非叶节点想离开组播组，则需要作为树成员保留。若叶节点要离开组播组，它首先将组播路由表中对应该组的路由项删除，并向上游链路发送MACT-P通知上游节点它要离开组播树。接收到MACT-P的上游节点将退出组播树的下游节点从组播路由表中删除。如果上游节点删除自己的下游节点后成为叶节点且不是组成员，该节点也向上游节点发送MACT-P退出组播组。上述的过程会重复进行直到达到一个组成员或者非叶节点。

(2) 由于节点的移动以及能量的消耗，每条链路的W是变化的。因此每隔一段时间，链路的下游节点就对链路稳定性进行重新判断，若发现W

由于多次局部重建，会导致组播树是一个非最优树，因此每隔一段时间要由源节点重新发起一个路由发现过程，以连接到组播树上。

3 仿真分析

为了评测LSMRP协议的性能，使用NS-2［12,13］仿真工具对其性能进行模拟研究，并与Ad Hoc网络中典型的组播路由协议MAODV［14］进行比较。

3.1 仿真环境设置

在800×800单位的平面区域，随机布置50个节点，仿真时间为100 s，数据包大小为512 B，节点平均移动速度分别为1 m/s，5 m/s，10 m/s，15 m/s，20 m/s和25 m/s，研究节点不同的移动速度下丢包数和投递率的变化。为了防止仿真中极端环境的影响，每个不同速度，产生多个场景环境，记录所得数据的平均值。

3.2 仿真结果及其分析

图1为丢包数随节点移动速度的变化。可以看到，随着节点移动速度的增大，MAODV和LSMRP的丢包数均增大。这是因为节点速度变大,网络的拓扑变化也加快了。在相同移动速度下，LSMRP明显比MAODV的丢包数少，而且速度越大，丢包数差值越大。这是因为，LSMRP在建立路由前对链路的性能进行比较，选出具有较高连接性的链路，可大大降低丢包数。

图1 丢包数的比较结果

图2为投递率随节点移动速度的变化。可以看到，当节点移动速度低于5 m/s时，两种协议的投递率都保持在80%以上，但当移动速度加快时，MAODV的投递率急速下降，当移动速度高于15 m/s时，它的投递率不能达到70%。而LSMRP协议在节点移动速度为25 m/s时，投递率仍能高于70%。这是因为LSMRP在路由选择上对链路生存时间和节点能量进行了综合考虑，并且及时的链路修复保证了它较高的投递率。

4 结 语

LSMRP是一种考虑路由稳定性的组播路由协议。它综合考虑了节点移动以及节点能量对路由稳定性的影响，所选路径能够维持较长时间的连接以及传输数据的节点具有较高的能量，并且采用在链路断裂前进行修复的机制。仿真结果证明，LSMRP能够降低网络丢包数，并且提高了数据传输的可靠性。每条链路选择了具有较优性能的稳定链路，因此延长了路由生存时间，从而延长了网络生存时间。

图2 投递率的比较结果

该协议在路由建立时，会对链路性能进行比较，会增加网络时延，对于有快速数据传输要求的网络不适应。另外，在链路未断而即将断裂时就会进行路由修复，会对资源和节点能量造成浪费。因此还需在路由修复上进行改进。

参考文献

［1］Magnus Frodigh,Per Johansson.Wireless Ad Hoc Networking-The Art of Networking without a Network ［J］.Ericsson Review,2000(4):248-262.

［2］Ljubica B,Levente B,Srdjan C,et al.Self-organization in Mobile Ad Hoc Network:The Approach of Terminodes ［J］.IEEE Communication Magazine,2001,39(6):166-174.

［3］IETF Secretariat.Mobile Ad Hoc Networks［EB/OL］.http://www.ietf.org/html.charters/manet- charter.html.IETF,2000.

［4］Wang Jianxin，Deng Shuguang,Chen Songqiao,et al.A Route Recovery Method Based on Anycast Policy in Mobile Ad Hoc Networks［J］.Journal of China Institute of Communications，2003，24(10):172-176.

［5］Nen-Chung Wang,Jhu-Chan Chen.A Stable On-demand Routing Protocol for Mobile Ad Hoc Networks with Weight-based Strategy［J］.IEEE PDCAT,2006(12):166-169.

［6］Wu Zhengyu,Song Hantao,Jiang Shaofeng,et al.A Grid-based Stable Routing Algorithm in Mobile Ad Hoc Networks［J］.IEEE AMS,2007(3):181-186.

［7］Chunyen Hsu,Jeanlien C Wu.Finding Stable Routes in Mobile Ad Hoc Networks［J］.IEEE AINA,2004(2):424-427.

［8］William Su，Sungju Lee，Mario Gerla.Mobility Prediction and Routing in Ad Hoc Wireless Networks［J］.International Journal of Network Management，2001(11)：3-30.

［9］Scott K,Bambos N.Routing and Channel Assignment for Low Power Transmission in PCS［A］.Proc.of IEEE Int′l Conf.Universal Personal Comm..1996(2):498 - 502.

［10］Singh S,Woo M,Raghavendra C S.Power-Aware Routing in Mobile Ad Hoc Networks［A］.Proc.of the Fourth Ann.ACM/IEEE Int′l Conf.Mobile Computing and Networking.1998(12):181-190.

［11］Feeney L,Nilsson M.Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment［A］.Proc.of IEEE INFOCOM.2001(3):1 548-1 557.

［12］于斌，孙斌，温暖，等.NS2与网络模拟［M］.北京:人民邮电出版社，2007.

［13］NS by Example ［EB/OL］.http://nile.wpi.edu/NS/.

［14］Royer E M,Perkins C E.Multicast Ad Hoc On-demand Distance Vector Routing［Z］.Internet Draft,2000.

作者简介 刘 琳 女,1981年出生,硕士研究生。主要研究方向为Ad Hoc网络中基于组播的稳定性路由。

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