适用于WSNs的拥塞自适应多径路由算法

施利利, 卢先领

(江南大学 物联网工程学院,江苏 无锡 214122)

适用于WSNs的拥塞自适应多径路由算法

施利利, 卢先领

(江南大学 物联网工程学院,江苏 无锡 214122)

针对无线传感器网络(WSNs)数据汇聚特性易导致网络拥塞的问题，结合改进AOMDV协议的多径建立、选择机制的缺陷，提出一种拥塞自适应的多径路由算法。新协议首先引入相关因子模型建立相互干扰度最小的路径集；其次建立路径拥塞信息采集、更新机制，并利用HELLO消息传递。最终源节点通过实时感知路径拥塞信息，自适应选择低拥塞路径来避免拥塞。仿真结果表明：改进的协议显著提高了分组投递速率，降低了端对端时延。

无线传感器网络； 拥塞避免； 多径路由； 相互干扰度

0 引 言

在无线传感器网络(WSNs)中，多对一汇聚的传输方式导致网络极易产生拥塞[1]。提高网络资源利用率的同时尽量避免拥塞一直是网络设计者追求的目标之一。因此，研究具有拥塞控制功能的路由协议具有重要意义。与单径路由相比，多径路由能平衡网络负载，减少网络拥塞，提高网络整体性能。但传统的多径路由通常只使用主路径发送分组，仅当主路径失效时才启用备份路由。这种路由选择机制不仅没有充分发挥出备份路径的作用，且易导致备份路径的过时失效；同时，多径的建立过程没有考虑降低路径之间的干扰，在某一时刻，多条路径同时处于拥塞区域的概率就增大。

国内外针对现有多径路由协议不足的研究中，提出了大量的改进方案。在路由发现方面，文献[2]通过监听信道忙和闲的比例来判断节点的拥塞，并以此作为是否继续广播RREQ消息的依据来实现网络的负载均衡。ZD-AOMDV[3]考虑多径路由之间干扰严重，提出建立区域不相交路径机制来降低路径之间的相互影响。MAOMDV-LB[4]根据缓存队列长度来判别是否允许路由经过该节点，以均衡网络中节点的负载。在路由选择方面，文献[5]选择剩余能量最多的路径进行分组传递，以实现能耗均衡。文献[6,7]基于接收信号强度指示值选择路径，降低了因路由失效引发的路由发现频率。文献[8]指出因拥塞导致大量数据包的丢失和重传不仅浪费节点的能量，而且导致更高的端对端延时和数据包丢失。而上述改进方案很少以此为出发点。

为了减轻WSNs中的网络拥塞，本文对AOMDV的路由发现和路由选择机制做出改进，提出了一种拥塞自适应的多径路由算法。新算法最多只允许源节点维护3条可用路径，以此来降低一定量的路由开销；其次，当网络产生局部拥塞时，源节点能避开拥塞区域选择低拥塞区域路径来减轻网络拥塞。

1 AOMDV协议概述

AOMDV[9]协议旨在发现多条无回环、不相交路径，当

源节点需要发送数据且无可用路由时，广播RREQ消息启动路由发现机制。由于RREQ以泛洪方式传播，每个中间节点会收到多个相同的RREQ消息副本。AOMDV充分利用这些RREQ消息，检查每一个接收到的RREQ消息来建立可利用的反向路径。同时，利用源节点序列号和广播跳数保证路径无回环和不相交，规则伪码如下：

if(本地目地序列号

更新序列号，清空路由列表，建立新的反向路径；

}

else if((本地目地序列号=RREQ消息节点序列号)

and(本地广播跳数>RREQ广播跳数)){

选择具有最小跳数的路径插入路径列表。

}

当中间节点建立起反向路径之后，检查是否有到达目的节点的前向路径；如果存在，则生成RREP消息，并沿着反向路径发送给源节点，同时建立起对应的前向路径。当目的节点接收到了RREQ消息，首先同样建立起反向路径，但与中间节点不同的是，目的节点对所有邻居节点发送过来的RREQ消息都会产生一次RREP路由回复消息。中间节点在收到RREP消息之后，若是检查并选择未被利用的反向路径对应的节点作为RREP下一跳传输对象，则生成链路不相交路径；若是只允许节点转发一次RREP消息，则生成节点不相交路径。

2 自适应多径路由算法

2.1 算法原理

AOMDV协议可建立链路不相交或节点不相交路径，但没有考虑降低这些路径间的干扰性。为此，首先引入相关因子模型来建立低干扰度的多路径，同时为了降低路由维护的开销，只保留1条主路径和最多2条备份路径。其次，改进AOMDV路由选择机制，把路径上节点拥塞度的最大值作为本路径拥塞值，并利用HELLO消息周期性广播机制，传递、更新路径的拥塞值信息。最终源节点会收到实时的路径拥塞值，并以此来自适应选择路由。规则伪码如下：

if(没有到达目的节点的路由)

启动路由发现过程；}∥和AOMDV协议相同

if(存在单条路径到达目的)

{选择该路径传输数据；}

else{

if(主路径不拥塞)

{选择主路径传输数据；}

else if(存在不拥塞的备份路径)

{选择低拥塞的备份路径传输数据；}

else{选择主路径传输数据；

}

为实现上述自适应多径路由算法需对路由表和RREP数据包进行相应的扩展。在路径列表中添加cr和cg域，其中,cr存储路径相关因子值，cg存储路径拥塞值。在RREP分组中添加rp_f位和rp_cr,rp_cg字段。rp_f为主路径标志位，当目的节点进行第一次回复RREP消息，就对此RREP消息rp_f位置1，表示该路径为主路径。rp_cr记录路径相关因子值。rp_cg记录路径拥塞信息并通过HELLO消息传递，但HELLO消息即是跳数为1的特殊RREP消息，所以,也在这里添加。

2.2 多径建立

2.2.1 相关因子模型

在无线网络中，所有节点共享同一无线信道，不同路径之间存在相互干扰。如图1(a)中的路径S-A-B-D和S-E-F-D，当A向B传输数据时，由于F在A的传输范围内，F也能收到此数据分组。因此，在A向B发送数据的过程中，F如果要发送或接收数据(非A发送)，都会发送冲突，导致A和E的动作都失败。因此，即使是节点不相交路径，路径之间也可能存在干扰。为了量化地描述出路径之间的干扰程度，引入相关因子[10]：

定义1 2条节点不相交路径的相关因子C：由2条节点不相交路径中的节点组成的拓扑图中，相关因子就是2个端点分属于2条节点不相交路径的边的条数。

如图1(a)中的2条路径S-A-B-D和S-E-F-D，其中有4条链路：(A，E),(A,F),(B,E)和(B,F)，它们有一个共同点：一个节点在路径S-A-B-D上，一个节点在路径S-E-F-D上，因此,这2条节点不相交路径的相关因子就为4。而图1(b)无分属上述2条路径的边，因此,相关因子为0。显然,相关因子越大，路径之间的干扰就越大。因此，路径之间的相关因子值越小，其干扰也就越小。

图1 节点不相交路径的相关因子Fig 1 Relevant factor of node-disjoin paths

2.2.2 低干扰度路径建立

在AOMDV路由回复阶段，RREP消息从目的节点沿反向路由进行传递，其他无关邻居节点不会参与转发RREP消息。因此，选择RREP消息的个数作为相关因子的参数。为了节约能量，除产生网络拥塞，其他情况选择最短路径来进行数据传输。因此,通过延时回复RREP消息策略来确保对最短路径优先回复，并以该路径为参照，找出与之干扰较小的备份路径。协议路由发现过程，如图2。

图2 路由建立过程Fig 2 Establish process of routing

1)当源节点需发送数据且无可用路由时，发起路由请求，RREQ消息向目的节点扩散，并建立起反向路由(该过程与原AOMDV协议相同),如图2(a)，(b)。

2)在目的节点接收到第一个RREQ请求消息后延时t秒,以确保收到足够多的邻居节点RREQ消息。同时为了避免建立过长的路径，必须保证t值不能太大。

3)选择最短跳数路径优先回复RREP消息，并将rp_f置1。如图2(b),(c)，选择路径d3进行优先回复，图中标记为RREP_1。

4)依次对其他路径进行RREP回复，并在路由回复过程中，计算对应路径上节点接收到RREP_1消息个数的总和，作为本路径与最优路径的相关因子值。如图2(c)节点E,F都检测到了节点G的RREP_1消息。

5)选择相关因子值最小的2条路径作为备份路径,如图2(d)，选择S-G-D为主路径，S-A-B-C-D和S-H-I-J-D为备份路径。

2.3 路径拥塞判定与更新规则

2.3.1 拥塞判定规则

当一条路径上某个节点产生了拥塞，就说明该路径产生了拥塞。检测拥塞的最简单方法就是监视节点缓存队列长度，考虑在WSNs中，频繁的短时数据流造成即时队列长度的震荡，使用平均队列长度来代替，即

queue_sizeave(n+1)=w×queue_sizeave(n)+(1-w)queue_size(n+1).

(1)

其中， queue_size(n)为第n次迭代时节点队列长度，w为权值系数。w越大，平均队列长度越能反应当前队列的变化；反之，对当前队列反应越不敏感。但此方法不能准确地指示WSNs的拥塞。因此，结合信道繁忙比率cb[11]来联合检测，cb的计算公式如下

(2)

其中，pi为空闲的退避时间的概率，ps为一次成功传输的概率，pc为在同一退避时间内2次并发传输的概率，Ts为一次成功传输的平均时间，Tcol为产生碰撞的平均时间，σ为空闲退避时间的长度。

信道繁忙比率是指在时间间隔内，信道因为成功传输数据或者碰撞引起的忙碌状态时间与总时间的比值，可对网络拥塞提供早期的预警。对于不同的网络场景和活动的节点的数量来说，最优的信道利用率几乎相同，一般为95 %[8]。设置信道利用率阈值Bth，当cbBth时，则认为信道被过度利用。

基于上述分析，节点拥塞判定规则如下：

If((cb>Bth‖(cq>Qth))

{cg=0xFFFF}∥节点产生拥塞

else{cg=queue_sizeave}∥节点无拥塞

其中，cq=queue_sizeave/queue_s,queue_s为节点总队列大小，cq为队列占用比，Qth为队列占用阈值。

路径拥塞判定规则：只要该路径上的任一节点产生拥塞，即判定该路径拥塞。

2.3.2 路径拥塞更新规则

活动路由中节点会周期性的发送HELLO消息，每个节点在发送HELLO消息之前更新自己的拥塞值，并将更新的路径拥塞值添加到HELLO消息的rp_cg域中。对于每个节点发送的HELLO消息，其所有邻居节点都能接收到，为了不干扰到其他路径的拥塞信息，规定在所有接收HELLO消息的邻居节点中，只有以HELLO消息源节点为路由下一跳的节点才会对应更新其路径拥塞信息，其他邻居节点则视其为单纯的HELLO消息。当节点接收到新的路径拥塞信息，就更新对应的路径拥塞值，并在节点准备广播HELLO消息之前，检测本节点的拥塞度并与收到的最新路径拥塞值进行比较，选出较大值作为本轮最终的路径拥塞值。

3 仿真与分析

3.1 仿真环境

主要仿真参数：拓扑大小为1 000m×1 000m；仿真时间为300s；节点数为50个；CBR对数为5，10，15，20，25；发送速度为5包/s；MAC层协议为IEEE802.11；仿真模型为Random-Way-Point。

利用NS2.34软模拟了一个有50个节点的网络，节点随机分布在1000m×1000m的区域中，每个节点的最大传输范围为250m。为了验证协议运行参数队列占用阈值Qth和队列权值系数w对网络性能的影响，实验首先对参数Qth和w分别取值，观察2个参数的变化对网络丢包率和端对端时延的影响。其次，通过改变随机产生的CBR连接对数来模拟不同拥塞度的网络场景，与AOMDV协议在分组投递率和平均端对端延时性能上进行了比较。其中CBR连接的源节点为随机选择，但目的节点始终是Sink节点。为了降低其他因素对拥塞度的影响，规定发送速率恒为5包/s，每个数据包大小为512bytes。

3.2 仿真结果分析

1)设定CBR连接对数为15，观察参数Qth和w对网络性能的影响，如图3、图4所示。当将w固定，且Qth设置过小时，节点只能存储短队列数据，尽管端对端延时较小，但导致丢包率很大；随着Qth的增大，节点丢包率降低，但超过一定值后，丢包率又开始增大，这是由于长队列及对无线信道的竞争导致数据包容易产生延时丢包，并导致端对端延时也迅速提高。参数w的变化，对感应网络拥塞的灵敏度影响很大。对当w设置过小，如w=0.002时，节点对网络拥塞度的反应不灵敏，导致节点队列缓存易处于满队列状态，端对端延时时间增长。但w设置也不能过大，如当w=0.02时，节点对网络拥塞度过于灵敏，使节点很容易处于拥塞状态，尤其当队列占用阈值越小时，节点对分组数据存储能力越弱，导致大量分组数据被直接丢弃。通过多次实验比较得出，当队列占用阈值设为总队列长度的75 %，且w= 0.01时，改进的算法能较好地降低丢包率，减少端对端时延。

图3 网络丢包率比较Fig 3 Comparison of network packets loss

图4 端对端时延比较Fig 4 Comparison of end-to-end delay

2)改进协议的2个参数分别设为：Qth=75 %，w=0.01，结果如图5、图6所示。从图中可以看出:随着CBR连接对的增加，二种协议的分组投递率都随之下降，平均端对端时延增大。这是由于CBR连接对的增加使信道竞争变的激烈并导致网络产生了拥塞。改进后协议在网络产生拥塞时获得了较高的分组投递率和较低的端对端时延，这是因为在改进后的协议中源节点一旦检测到主路径产生拥塞，选择了低拥塞的备份路径来避免网络拥塞。同时当CBR连接对大于20时，改进后协议性能也迅速下降，此时网络负荷已经大于网络最大的吞吐能力，因此，通过单纯的流量调度已不能解决问题，此时必须通过降低源节点速率或者进行分组丢弃来控制拥塞。

图5 分组投递率比较Fig 5 Comparison of grouping delivery ratio

图6 端对端时延比较Fig 6 Comparison of end-to-end delay

4 结 论

针对WSNs的汇聚特性易引发网络拥塞，提出了一种拥塞自适应的多径路由算法。改进算法保留了原AOMDV协议的优点，同时充分考虑了无线链路的干扰特性，建立起相互干扰最小的多径集，并利用HELLO消息传递更新路径拥塞信息，最终通过选择低拥塞路径进行数据传输来提升网络的性能。仿真的结果也表明:改进的协议在网络产生局部拥塞时，能有效地通过选择低拥塞区域路径来减轻网络拥塞，同时提高了网络分组投递率、减少了网络时延。

[1] 孙利民,周新运.无线传感器网络的拥塞控制技术[J].计算机研究与发展,2008,45(1):3-72.

[2] Wannawilai P,Sathitwiriyawong C.AOMDV with sufficient bandwidth aware[C]∥2010 IEEE 10 th International Conference on Computer and Information Technology(CIT)：IEEE,2010:305-312.

[3] Javan N T,Kiaeifar R,Hakhamaneshi B,et al.ZD-AOMDV:A new routing algorithm for mobile Ad-Hoc networks[C]∥Eighth IEEE/ACIS International Conference on Computer and Information Science,ICIS 2009:IEEE,2009:852-857.

[4] Narayan D G,Nivedita R,Kiran S,et al.Congestion adaptive multipath routing protocol for multi-radio wreless mesh network-s[C]∥2012 International Conference on Radar, Communication and Computing(ICRCC):IEEE,2012:72-76.

[5] Sharma S,Agarwal P,Jena S K.Energy aware multipath routing protocol for wireless sensor networks[M]∥Computer Networks & Communications(NetCom).New York:Springer,2013:753-760.

[6] Mallapur S V,Terdal S.Enhanced Ad Hoc on demand multipath distance vector routing protocol[J].International Journal of Computer Science and Information Security,2010,7(3):166-170.

[7] Chintawar A,Chatterjee M,Vidhate A.AOMDV-APLP:An enhanced algorithm with accessibility and link breakage predic-tion[C]∥Proceedings of the International Conference & Workshop on Emerging Trends in Technology,ACM,2011:841-845.

[8] Hsu Y P,Feng K T.Cross-layer routing for congestion control in wireless sensor networks[C]∥Radio and Wireless Symposium,IEEE,2008:783-786.

[9] Periyasamy P,Karthikeyan E.Performance evaluation of AOMDV protocol based on various scenario and traffic patterns[J].International Journal of Computer Science,Engineering and Applications(IJCSEA),2012,1(6):33-48.

[10] Wu K,Harms J.Performance study of a multipath routing method for wireless mobile Ad Hoc networks[C]∥Proceedings of Ninth International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems,IEEE,2001:99-107.

[11] Zhai H,Chen X,Fang Y.Improving transport layer performance in multihop Ad Hoc networks by exploiting MAC layer informa-tion[J].IEEE Transactions on Wireless Communications,2007,6(5):1692-1701.

Congestion adaptive multipath routing algorithm for WSNs

SHI Li-li, LU Xian-ling

(College of Internet of Things,Jiangnan University,Wuxi 214122,China)

Aiming at problem that wireless sensor networks(WSNs)data gathering features easy lead to network congestion,a congestion adaptive multipath routing algorithm is proposed,combined with improving defect of mechanism of multipath establish and selection of AOMDV.Firstly,relevant factor mode is introduced in the new agreement to build a path set with minimal mutual interference；secondly,establish path congestion information collection,update mechanism,and use the HELLO message to transmit.Eventually source node adaptively selects the lower congestion path to avoid congestion by real-time sense path congestion information.Simulation results show that the improved protocol can effectively improve packet delivery and reduce end-to-end delay.

WSNs; congestion avoidance; multipath routing; mutual interference

10.13873/J.1000—9787(2014)08—0141—04

2014—01—13

TP 393

A

1000—9787(2014)08—0141—04

施利利(1989-),男,江苏启东人,硕士研究生,主要研究方向为无线传感器网络拥塞控制。