基于拥塞控制的无线路由算法研究

浦倩云，吴锡生

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



基于拥塞控制的无线路由算法研究

浦倩云，吴锡生

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

因网络通信量大而导致的网络拥塞，是制约网络性能的主要因素。提出的拥塞控制路由算法(CCRA)根据节点跳数、缓存占用率和缓存占用趋势的关系，并结合相关函数，得到计算拥塞标志值和链路代价的函数，从而得到一种改进的最佳路径路由算法，同时使用基于备份路由和时间动态设置定时器的局部路由策略调整局部拥塞。仿真结果表明，改进的路由算法，减轻了网络的拥塞状态，缩短了网络的传输时延，提高了分组成功投递率。

无线传感器网络；拥塞控制；路由算法；备份路由

0　引　言

无线传感器网络中，终端覆盖范围有限，两个相距较远无法直接通信的节点，可借助其它节点进行分组转发[1-2]，节点的缓存[3-4]、网络的拓扑结构及采用的路由协议等，是造成网络拥塞的主要原因，因而研究一种有效解决无线传感器网络拥塞的方法具有重要的意义。文献[5-6]从拓扑结构方面，分析了导致网络拥塞的原因，提出通过增加或删除节点和链路来缓解网络拥塞。该方法的实施会改变拓扑结构，可行性不高。文献[7-8]采用了多径路由机制，当网络拥塞时，将数据包从不同的“下一跳”转发出去，以缓解网络拥塞。但此算法在计算链路代价时仅考虑了网络的静态特征或动态特征，不能保证选路时达到全局最优。目的节点序列距离矢量DSDV(destination sequenced distance vector)算法是一种基于最短路径优先算法的路由协议，它具有无环路、收敛速度快等特点，但它的算法得到的路径总是“最优路径”，导致数据包总是沿着“最优路径”发送。当网络中各个最优路径有部分重叠时，会产生某些链路被频繁使用，以至其负载过大而导致网络局部拥塞。文献[9]提出了一种基于加权路由策略的拥塞控制机制，将节点的介数作为节点连接边的权重，按加权网络最短路径路由传输数据包。它采用区域中心节点近似估算法计算介数，降低了介数计算的复杂度。文献[10]提出了一种拥塞预知路由算法(CPRA)，通过周期性检测队列缓冲区的占用率(BOR)，来判断链路是否有可能会发生拥塞，当BOR达到某个阈值时，认为链路有可能发生拥塞，此时结合局部拓扑结构与链路状态计算备用路由，当BOR达到另一阈值时，启用备用路由。文献[9-10]都需计算全局路由表，仅适用于有线网络。文献[11] 提出了一种基于BA网络的局部路由策略，基本思想是在数据包转发过程中,将邻居节点的度和发送能力以一定比例加和得到的值作为权值,根据权值大小选择下一站点，但是只考虑了局部网络状态。I-DSDV[12]通过在路由表中增加参数‘type’来标记当前条目是有效还是无效。当节点检测到链路断裂时，节点先在一跳范围内广播并寻找重建链路，如果寻找失败且此时被广播节点没有分组要经过该节点发送至对应目的节点，则等待下一周期更新重建路由，否则，立即重播无效的路由信息。Imp-DSDV协议[13]维护且更新一个所有可到达目的节点的备份路由表。当链路断裂时，通过备份路由表，节点可快速找到到达目的节点的有效路由。但是文献[12-13]都只考虑了链路断裂对网络性能的影响，没有考虑到节点拥塞对网络性能的影响。为解决该不足，本文在研究现有路由算法的基础上，提出了一种拥塞控制路由算法(CCRA)。该算法根据节点跳数、缓存占用率和缓存占用趋势的关系，得到一种改进的最佳路径路由算法，并使用基于备份路由的局部路由策略解决局部拥塞。仿真结果表明，改进的路由算法，减轻了网络的拥塞状态，降低了网络的传输时延，同时提高了分组成功投递率。

1　拥塞控制路由协议队列模型分析与改进

1.1节点负载

现有无线路由协议在计算路由的过程中，大都以时延和跳数等因素作为计算链路代价的依据。由于没有考虑链路和节点的拥塞状态，导致无法避开拥塞的链路和节点，从而导致部分链路和节点出现拥塞。如果在路由选择前能通过拥塞检测预知到链路和节点的拥塞并避开，就能有效减少传输过程中的拥塞，提高分组成功投递率。

一般用节点缓冲区待发送数据包个数与缓冲区最大容量的比值(即缓冲区占用率buffer occupation rate，BOR)来衡量节点的拥塞程度，但缓冲区占用率仅代表某一时刻的占用率，不能准确预测节点将来的拥塞状态，为此本文使用缓冲区占用率和堆积率一起来度量节点拥塞程度。

定义1：堆积率(accumulation rate，AR)为单位时间进入节点数据包的个数和流出节点数据包个数的差值与缓冲区最大容量的比值。如果堆积率大于或等于0，说明数据包到达的速度大于或等于流出的速度，AR值越大，出现拥塞的可能性越大。

定义2：拥塞度(congestion degree，CD)为预测节点拥塞的度量，其值可用式(1)表示：

CDi(t)=BORi(t)+ARi(t)

(1)

约束条件为：

其中，BORi表示节点i的缓冲区占用率，0

(2)

1.2链路代价模型

定义3：链路代价(road weight，RW)为转发数据包所要付出代价的衡量，其值用式(3)表示：

RWij(t)=metricij+CUj×CDj(t)

(3)

式中，RWij为将数据包从节点i转发到邻节点j所要付出的代价。

假设源节点到目的节点的路径表示为P(s→d)=a1,a2,…,an，此路径的总代价为：

(4)

式中，metricsd为节点s到节点d的跳数。选择使RWsd(t)值最小的路径作为更新路由，这样周期更新路由时即可避开拥塞节点。由式(3)可知，当节点处于空闲阶段时公式的第二项为0，路由选择结果与DSDV相同，当节点出现拥塞时公式的第二项会根据网络中节点的拥塞状态确定“最短路径”，以确保算法始终选择全局最优路径。

2　局部拥塞路由策略的改进

当网络中有节点发生拥塞时，为提高网络的分组成功投递率，可以将节点中的数据分流。为此，本文提出一种基于备份路由表的局部拥塞控制路由策略。这需为每个节点创建一张备份路由表，备份路线遵循以下规则：

(1)备份路线有无效和有效两个状态。

(2)无效备份路线的跳数为无限大。

(3)有效备份路线的序列号应与相应主路线的序列号相同，而代价应不小于相应主路线的代价，且下一跳应与相应主路线的不同。确保备份路线是无循环的。

(4)起初，所有备份路线都是有效的。

(5)如果接收到的路由更新的序列号与相应主路线的序列号相同，而代价不小于相应主路线的代价，且下一跳与相应主路线的不同，且当其序列号与备份路线的序列号相同，而代价不大于相应备份路线的代价，则相应的备份路线更新。

(6)如果主路线被备份路线代替，则备份路线设为无效。

例如：当节点C的拥塞标志CU大于4时，则进行以下操作：

(1)节点C中有一个来自节点B要转发到节点D的分组，节点C向节点B发送拥塞信息并设置一个定时器。

(2) 节点B接收到拥塞信息，查询主路由表并用备份路线代替下一跳节点为节点C目的节点为节点D的主路线。然后将备份路线的跳数设成无限大，将新的主路线的序列号设置为比旧的主路线的序列号大1(奇数序列号)。

(3)如果定时时间到时节点C还处在拥塞状态，则重复上述步骤。当节点C的拥塞标志CU等于0时，节点C发送以自己为目的节点的更新包。

本文对定时器时间的设置采用动态设置方式。节点队列被填满的时间由缓冲区占用率BOR和堆积率AR共同决定，其关系如式(4)所示：

BORi(t+ΔT)=BORi(t)+ARi(t)×ΔT

(5)

式中，BORi(t+ΔT)为节点i在时间间隔ΔT之后缓冲区的占用率，当BORi(t+ΔT)>θ2时，表示在时间间隔ΔT之后节点i的缓冲区会进入CS阶段，当BORi(t+ΔT)>1，表示在时间间隔ΔT之后节点i的缓冲区会进入丢包阶段。

当节点CU>4时，完成第一次发送拥塞信息之后，根据BOR和AR的值计算定时器检测的时间间隔，其值如式(6)所示：

(6)

式中，Ti(t)为定时器检测的时间间隔，(1-BORi(t))是节点缓存区的剩余大小，ARi(t)是节点缓冲区的堆积率。

当节点C检测到其与邻节点D之间的链路断裂时，它将作以下操作：

(1)节点C查询主路由表并用备份路线代替下一跳节点为节点D的任意主路线。然后将备份路线的跳数设成无限大。

(2)节点C将新的主路线的序列号设置为比旧的主路线的序列号大1(奇数序列号)。

(3)节点C广播主路由表中跳数为无限大或奇数序列号的路线。

每个接收到来自节点C的路由更新包，且包中包含到节点D的跳数为无限大的路线更新的节点，则做以下操作：

如果节点有到节点D的主路线且其下一跳为节点C，则：

(1)用备份路线替代主路线，然后将备份路线的跳数设为无限大。

(2)将新的主路线的序列号设置为比旧的主路线的序列号大1(奇数序列号)。

(3)节点广播主路由表中跳数为无限大或奇数序列号的路线。

否则

(1)如果节点有到节点D的主路线且它的下一跳不是节点C，则将其序列号设置为比旧的主路线的序列号大1(奇数序列号)。

(2)节点广播主路由表中跳数为无限大或奇数序列号的路线。

3　拥塞控制路由改进算法描述

根据第2节提出的链路代价模型，计算节点发送数据包的全局路由，同时当节点发生拥塞时，用第3节提出的局部拥塞路由控制策略，在节点将拥塞时用备份路线代替主路线，从而得到本文提出的拥塞控制路由算法(Congestion Control Routing Algorithm，CCRA)。CCRA算法的具体过程如下：

输入：节点集合，阈值θ1、θ2

BEGIN

初始化θ1、θ2

for节点iin nodes、

节点i利用式(4)计算到各个可到达节点目的节点的链路代价

end for

while有数据包Packet需要转发时 do

入队Packet，查询节点i的网卡队列

if (CU==0)

转发队列中的数据包

if 上次定时器检测时CU大于4

发送以节点i为目的节点的路由更新包，序列号加2

if(0

转发队列中数据包

if (CU>4)

通知Packet的上一跳节点，启用备份路由，并设置定时器

end while

END

4　实验结果及分析

本文使用NS2.35进行实验。模拟网络有100个节点随机分布在1 000×1 000的平面区域。MAC层使用信道带宽为2 Mb/s的IEEE 802.11 MAC协议。节点传输范围250 m。仿真时间400 s。流动模型使用Random-Waypoint；在此模型中，当仿真开始时每个节点都静止pause-time秒。然后随机选择一个目的地且以一个分布在0～maximum之间的速度匀速向该目的地前进。到达目的地后，再次静止pause-time秒，然后随机选择另一个目的地并按前述方法继续前进，重复上述行为直至仿真结束。本文的运动模型由9个不同的pause-time：0,50,100,150,200,250,300,350,400和一个最大速度(20 m/s)生成。流量源采用CBR，其数据包大小为512个字节，通信模式采用20个数据源，数据源开始的时间均匀分布在0～5 s之间。

(1)DSDV、文献[11-12]和本文算法(CCRA)，在源节点每秒发送1个分组(即网络未拥塞)时的分组成功投递率平均值和端到端延迟平均值情况如图1和图2所示。

图1　分组成功投递率随节点移动率变化曲线(1/s)

图2　端到端延迟随节点移动率变化曲线(1/s)

由图1、图2可知，当源节点每秒发送1个分组且未拥塞时，文献[11-12]和本文算法在pause-time≤150时，比DSDV的分组成功投递率高的多，其后差不多，这是因为前三者都有应对链路断裂的机制；而当pause-time≥200时，由于网络中节点的移动时间大幅减少而网络的负载又较小，链路断裂对网络中数据的传输影响大幅减小，且DSDV本身拥有周期更新路由的能力，故而四种比较算法结果接近。而DSDV、文献[12]和本文算法的端到端的延迟基本一样，这是因为当链路断裂时，Imp-DSDV和CCRA能根据备份路由表快速找到到达目的节点的有效路线。

(2)DSDV、文献[11-12]和本文算法(CCRA)在源节点每秒发送10个分组(即网络拥塞)时的分组成功投递率平均值和端到端延迟平均值情况如图3和图4所示。

图3　分组成功投递率随节点移动率变化曲线(10 /s)

图4　端到端延迟随节点移动率变化曲线(10个/s)

由图3可知，当网络发生拥塞时，文献[11-12]比DSDV的表现要好，但是本文算法的表现最好。当pause-time很小时，DSDV同时受到链路断裂和节点拥塞的影响，所以表现很差；而文献[11-12]减轻了链路断裂的影响，所以表现比DSDV稍好；而本文算法同时减轻了链路断裂和节点拥塞的影响，所以表现最好。随着pause-time逐渐增大，链路断裂的影响逐渐减小，DSDV、文献[11-12]的表现逐渐相近；因存在一个周期内每个节点的备用路由只有一个的限制，在网络非常拥堵的情况下，已启用过的备份路由无法二次使用，故会影响到最后的分组成功投递率。但即使如此，因本文算法减轻了拥塞的影响，在本组实验中仍能将分组成功投递率提高到65%。仿真结果表明本文算法能减轻网络的拥塞状态，减少丢包，提高分组成功投递率。

由图4可知，本文算法的端到端延迟比DSDV和文献[11-12]的小，这是因为当网络局部发生拥塞时，本文算法采用备份路线转发分组，减少了分组排队产生的时延，大大降低了端到端的时延。

(3)在现实情况下，节点移动并不会出现很极端的情况，故本文将DSDV、文献[11-12]和本文算法(CCRA)在pause-time为350s时的分组成功投递率平均值进行比较，结果如图5所示。

图5　分组成功投递率随发送分组数变化曲线

由图5可知在暂停时间固定为350 s时，DSDV、文献[11-12]随着发送分组从1到10增加，分组成功投递率逐渐降低到近50%，而本文算法可使分组成功投递率维持在65%以上，说明本文的全局和局部拥塞策略能有效缓解网络中节点的拥塞，提高分组成功投递率。

5　结　语

本文结合队列模型、全局路由策略和局部路由策略三个方面进行研究，针对网络拥塞问题，提出了拥塞控制路由算法(CCRA)，以克服DSDV的陈旧路由问题并提高节点拥塞时网络的表现，该算法通过周期性地检测节点的拥塞程度，并反馈给路由模块，路由模块以节点缓冲区的拥塞情况为依据，采用全局和局部路由相结合的策略处理路由。局部路由策略利用备份路由表重建路由，以减少因链路断裂和节点拥塞导致的分组丢失。仿真结果表明，本文算法CCRA能减少因节点拥塞而产生的丢包，提高分组成功投递率。

[1]TAN S, LI X, DONG Q. Trust based Routing Mechanism for Securing OSLR-based MANET[J]. Ad Hoc Networks,2015,30(1):84-98.

[2]Prabha R, Ramaraj N. An Improved Multipath MANET Routing using Link Estimation and Swarm Intelligence[J]. Eurasip Journal on Wireless Communications & Networking,2015,2015(1)：1-9.

[3]Khan K, Zaman R U, Reddy K A, et al. An Efficient DSDV Routing Protocol for Wireless Mobile Ad Hoc Networks and Its Performance Comparison[C]// Computer Modeling and Simulation,2008. EMS′08. Second UKSIM European Symposium. Liverpool,England,UK:IEEE,2008:506-511.

[4]LIU T, LIU K. Improvements on DSDV in Mobile Ad Hoc Networks[C]//Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference. Shanghai, China: IEEE, 2007:1637-1640.

[5]HUANG W, ZHOU T W S. An Efficient Strategy for Enhancing Traffic Capacity by Removing Links in Scale-Free Networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2010, 2010(4):577-611.

[6]HUANG W, ZHOU T W S. Effective Strategy of Adding Nodes and Links for Maximizing the Traffic Capacity of Scale-Free Network[J]. Chaos,2010,20(3):233-271.

[7]Cevher S, Ulutas M, Hokelek I. Performance Evaluation of Multiple Routing Configurations[C] //In: Proceedings of the 21st Signal Processing and Communications Applications Conference(SIU). Haspolat,Turkey:IEEE,2013:1-4.

[8]CHEN K C, LIN S Y, HUANG H S, et al. Traffic-Balanced Topology-Aware Multiple Routing Adjustment for Throttled 3D NOC Systems[C]//Proceedings of the 2012 IEEE Workshop on Signal Processing Systems. Quebec City,QC,Canada: IEEE Computer Society,2012:120-124.

[9]刘伟彦, 刘斌. 基于加权路由策略的复杂网络拥塞控制研究[J]. 系统工程理论与实践, 2015, 4(04):1063-1068.

LIU Wei-yan, LIU Bin. Study on Congestion Control for Complex Network based on Weighted Routing Strategy[J]. Systems Engineering Theory & Practice, 2015, 4(04):1063-1068.

[10]段小龙,郭承青,闫健恩等.基于拥塞预知的路由算法研究[J]. 高技术通讯,2014,11(11):1140-1146.

DUAN Xiao-long,GUO Cheng-qing, YAN Jian-en, et al. Research on a Congestion Perception Routing Algorithm[J]. Chinese High Technology Letters, 2014, 11(11):1140-1146.

[11]孙雅倩, 张达敏, 曾成等.BA网络中一种基于节点动态权值的局部路由策略[J].通信技术, 2015,48(11):1275-1279.

SUN Ya-qian, ZHANG Da-min, ZENG Cheng, et al. A Local Routing Strategy based on Nodes Dynamic Weights in BA Networks[J]. Communications Technology, 2015, 48(11):1275-1279.

[12]LIU T,LIU K. Improvements on DSDV in Mobile Ad Hoc Networks[C]//Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference. Shanghai,China:IEEE,2007:1637-1640.

[13]LU J,ZHANG B,HAN G, et al. A New Improvement on DSDV[C]//Wireless Communications, Networking and Mobile Computing (WiCOM), 2011 7th International Conference. Wuhan,China:IEEE,2011:1-4.

浦倩云(1991—)，女，硕士研究生，主要研究方向为传感器网络和控制系统；

吴锡生(1959—)，男，教授, 硕士研究生导师，主要研究方向为图像处理，模式识别和智能控制。

National Natural Science Foundation of China (No.61103223); Joint Innovation Fund Project of Jiangsu Province (No.BY2013015-35)

Wireless Routing Algorithm based on Congestion Control

PU Qian-yun, WU Xi-sheng

(School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China)

Network congestion caused by large network traffic is the main factor in restricting network performance. The proposed CCRA (Congestion Control Routing Algorithm), according to the relation of between node hop, cache occupancy and cache occupancy trend, and in combination with the correlation function, obtains the function for calculating the value of congestion flag and link cost, thus acquiring a modified optimal path routing algorithm. Meanwhile, the local routing strategy based on backup routing and timer with dynamic time setting is applied to adjusting the local congestion. Simulation results indicate that the modified routing algorithm could ease the network congestion status,reduce the network transmission delay and improve the packet delivery ratio.

wireless sensor network; congestion control; routing algorithm; backup routing

10.3969/j.issn.1002-0802.2016.03.012

2015-10-16；

2016-02-06Received date:2015-10-16；Revised date：2016-02-06

TP393

A

1002-0802(2016)03-0312-06

国家自然科学基金(No.61103223)；江苏省产学研联合创新资金项目(No.BY2013015-35)