无线Mesh网络中基于链路负载估算的拥塞控制策略

夏汉铸+刘辉元

摘 要： 针对无线Mesh网络的网络特性，提出了一种基于链路负载估算的拥塞控制策略LLECC。LLECC算法计算有效链路带宽和链路负载估算确定RED算法中的调整因子，通过调整因子调整RED算法中的参数从而实现动态的对无线网络拥塞控制。详细讨论了LLECC算法的实现过程和相关参数的计算方法，通过仿真分析验证了该算法对无线Mesh网络性能的提高。

关键词： 无线Mesh网络； 有效链路带宽； 链路负载估算； 拥塞控制； RED算法

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2014）03?0027?04

Congestion control strategy based on link load estimation in wireless mesh networks

XIA Han?zhu1， LIU Hui?yuan2

（1. Department of Information Engineering， Zhongshan Torch Polytechnic， Zhongshan 528436， China； 2. Chongqing School of Industry， Chongqing 400043， China）

Abstract： Aiming at the network characteristics of wireless Mesh networks （WMNs）， an LLECC congestion control strategy based on link load estimation is proposed， which estimates the tuning factor of RED algorithm by calculating the available link bandwidth and link loads. The parameters in RED algorithm are adjusted by tuning factor to realize dynamic wireless network congestion control. The realization process of LLECC algorithm and computing method of parameters are discussed in detail. Through the analysis and simulation， it is proved that the LLECC algorithm can increase the performance of the wireless Mesh networks.

Keywords： wireless Mesh networks； available link bandwidth； link load estimation； congestion control； RED algorithm

0 引 言

随着网络技术的发展和应用，用户对网络的带宽、移动性和可靠性要求越来越高。无线Mesh网络WMN[1?3]（Wireless Mesh Networks）融合了WLAN网络和Ad hoc网络的技术特点，希望为用户提供可靠的高速宽带无线网络服务。多信道WMN允许多个不重叠的信道可以同时传输数据，这样就能满足无线Mesh网络对带宽资源的要求。

在WMN中，移动节点独立的争用无线网络资源，不考虑其他移动节点的实际状态，这样就会导致某一节点往无线网络中大量发送数据，可能导致无线网络拥塞的情况出现[4?7]。一旦无线网络出现拥塞，势必导致无线网络中大量的数据丢失和重传，严重影响无线网络的网络性能。而高层的拥塞控制策略（如TCP中的滑动窗口）无法满足无线Mesh网络拥塞控制的要求，无线网络中移动节点的拥塞控制策略就变得极为重要。

RED算法[8?10]是有线网络中拥塞控制的一种有效手段，RED算法采用低通滤波器模型来计算平均队长，支持突发业务，使得路由器处理算法实现的更为合理，避免了路由器因根据变化的实际队列长度而不断地变更处理方法，该算法因其具有较低的时延，较高的吞吐量和较好的公平性而被广泛采用。它通过在拥塞即将发生时丢弃部分数据，能够有效地避免全局同步，体现了对突发业务流的公平性。在无线Mesh网络中，由于网络中的各节点动态变化导致可使用的网络资源变化，而在RED算法中的预先设置的参数[wq，][minth，][maxth，][Pmax]不能与网络资源的变化同步，这样势必导致RED算法无法满足提高无线网络性能的目的。

本文对RED算法进行了详细的分析，对WMN中的有效链路带宽和链路负载估算的重要性进行了分析，提出了一种基于链路负载估算的拥塞控制策略LLECC（Link?Load?Estimation?based Congestion Control）。LLECC算法通过对WMN中的链路带宽和链路负载估算值动态地调整RED算法中的[minth，][maxth，][Pmax]三个参数实现网络中的动态拥塞控制。从该策略的实现过程和仿真结果来看，LLECC可以对WMN的拥塞程度做出相应的速率控制策略，而且能够提高无线网络的性能和不同业务的QoS保证。

1 RED算法

RED算法的基本思想是通过监测路由器输出端口队列的平均长度来探测拥塞，采用相关的策略使队列溢出导致丢包之前采用一定的丢包策略保证队列不溢出，降低发送数据速度，从而缓解网络拥塞。RED是基于FIFO队列调度策略的，只是丢弃正进入路由器的数据包。RED算法的目的是最小化数据包丢失率和排队延迟，避免对突发业务的不公平和全局同步现象。RED算法主要分两部分：一是计算平均队列长度；一是标记丢弃分组的概率，并对新到达的分组按照标记丢弃分组概率对该分组进行丢弃或排队处理。

RED算法采用低通滤波器模型来计算平均队列长度，突发业务对队列的长度会导致队列长度的短期增加，不会过大的影响平均队列长度。

[avg=（1-wq）avg+wqQ]

即：

[avg=avg+wq（Q-avg）] （1）

式中：avg为平均队列长度；[wq]为权值；[Q]为当前队列长度。

当一个分组到达队列[Q]时，通过计算标记丢弃概率来决定该分组被丢弃的可能性。

当[avgminth，][Pd]=0，该分组不被丢弃，直接进入到队列中；

[当minthavgmaxth，Pd=Pmax（avg-minth）（maxth-avg），]到达分组以[Pd]概率丢弃；

当[avgmaxth，][Pd]=1，该分组将直接被丢弃。

2 LLCEE拥塞控制策略

在无线Mesh网络中，由于用户的移动性、网络链路质量及网络拥塞水平等因素导致在无线网络环境下的拥塞控制策略极为复杂。LLCEE拥塞控制算法通过对WMN中的链路带宽和链路负载估算值动态地调整RED算法中的[minth、][maxth、][Pmax]三个参数实现网络中的拥塞控制。

2.1 LLCEE算法实现

LLCEE拥塞控制算法通过4个过程来实现无线网络的拥塞控制：计算链路的有效带宽；对本节点的链路负载进行估算；通过以上2个计算结果确定调整因子[α；]通过调整因子[α]值确定RED算法中的参数[minth、][maxth、][Pmax]实现本移动节点的拥塞控制。本算法的实现过程如图1所示，伪代码如下：

初始化参数：

α=0 ALBW=[i=1nBWi] LL=0

经过ΔT时间间隔

用公式（1）计算 有效链路带宽

用公式（2）计算 链路负载估算

用公式（3）计算 调整因子

用公式（4）计算 minth，maxth，Pmax

时刻t，某一分组到达每一队列：

if avg≤minth Pd=0

else if （minth≤avg≤maxth） 计算Pd

else Pd=1

根据Pd决定该分组插入队列或丢弃

图1 LLCEE算法流程图

（1） 有效链路带宽的计算

在多信道无线Mesh网络中，由于节点的移动性和设备的差异性等因素的影响导致无线信道的实际有效带宽与系统表明的标准带宽存在一定的差异（如由于网络信号的衰减导致信号传输出现误码），而无线网络中拥塞控制策略必须准确的知道本节点实际可用带宽资源，也就是有效链路带宽（Available Link BandWidth，ALBW）。LLECC策略就是通过对变化的无线网络链路通过虚拟化量化的方式计算出该移动节点的实际有效链路的带宽。

某一移动节点的有效链路带宽是该节点所有输出链路中的每一条输出链路标准带宽LBWi与带宽因子[βi]的乘积之和：

[ALBW=iβi×LBWi] （1）

其中[βi=ΔT成功传输的分组数ΔT传输总分组数，]由该链路的实际传输状态决定。

（2） 链路负载估算

LLECC策略通过链路负载估算计算出该节点实际可能的链路负载，具体计算方法如下：

[φ（s，d）=（s，d）pl（s，d）P（s，d）×B（s，d）]

式中：[pl（s，d）]表示节点对[（s，d）]间通过本节点链路[L]的路径数；[P（s，d）]表示节点对[（s，d）]通过本节点链路[L]的总路径数，[B（s，d）]表示节点对[（s，d）]之间的业务流量；[φ（s，d）]表示节点对[（s，d）]间通过本节点链路[L]的实际业务流量。

[LL=φ（s，d）] （2）

式中LL表示通过本节点的实际估算流量。通过以上2个公式就可对通过本节点的实际可能负载进行估算。链路负载估算取决于本节点采用的路由算法，通过路由算法可计算出通过某一无线链路的负载。但本算法适应于任何路由协议（如采用最短路径协议，[P（s，d）]=1，[pl（s，d）]=1或0；如采用负载均衡协议[P（s，d）]=实际路径数，[pl（s，d）]=通过本节点的链路数）。

（3） 调整因子

通过计算的有效链路带宽和链路负载估算就可以确定RED算法的调整因子：

[α=LLALBW] （3）

（4） RED参数的确定

确定RED算法的参数：

当[α1，][minth，][maxth]不变，[Pmax=α?Pmax；]

当[α>1，][minth=][α?minth，][maxth=α?maxth，Pmax=α?Pmax；]

（4）

通过确定的RED参数对移动节点中的数据进行拥塞控制。

2.2 LLCEE算法讨论

LLCEE算法主要用于解决无线Mesh网络由于节点的变化引起链路状态变化所带来可用网络资源变化，动态调整RED算法中的拥塞控制参数实施拥塞控制。为使LLCEE算法更适合解决无线网络的拥塞问题，需注意一下几点：

（1） 有效链路带宽ALBW。在无线网络中物理层包括多种传输技术（如：定向天线、智能天线、TDM、FDM、OFDM等），网络中每一个链路的传输带宽各不相同；同时在无线网络中无线信号存在多种衰减，致使节点距离和移动性成为影响节点间可靠传输的重要因素，导致该信道的实际可利用的带宽下降。LLECC算法通过[ΔT]时间间隔内正确传输的数据比例带宽因子[βi]作为衡量该信道可用带宽惟一依据，能反映该信道的实际情况。同时[ΔT]时间间隔设置不宜太长（无法及时反映信道现状）或太短（易受瞬时干扰的影响，不利于系统稳定），可以根据网络管理员的偏好设定，建议在0.1～1 s之间取值。