基于队列敏感性的无线接入网络拥塞控制算法

1、基于队列敏感性的无线接入网络拥塞控制算法文章编号:1001-9081(2012)01-0123-04doi:10.3724/spj.1087.2012.00123摘要:由于无线接入网络存在强非线性、大时延 以及随机链路丢包等因素，导致经典主动队列管理 (aqm)算法在实际控制时存在队列收敛速度慢、响应 时间长等问题。通过分析随机指数标记(rem)算法在无 线接入网中的特点，在原先rem价格模型的基础上对 其进行了改进，以队列误差的平方项来克服价格对队 列变化不敏感的缺陷，从而提出了一种基于队列敏感 性的无线接入网络拥塞控制算法，并利用单神经网络 对其参数进行了优化。最后，通过ns2仿真平台对所

2、 提算法与rem> pi算法进行对比，实验表明所提算法 拥有队列收敛快、鲁棒性强的优点。?关键词:无线接入网络；拥塞控制；主动队列管 理；随机指数标记；单神经元?中图分类号:tp393.07文献标志码:aabstract: since the wireless access network is subject to the effects of strong nonlinearity, large delay and random link loss, the classical active queue management (aqm) has the problems of slo

3、w con verge nee rate and long resp onse to queue in the actual control process by analyzing the characteristics of ran dom exp on ential marki ng (rem) algorithm in the wireless access network, this paper proposed a new congestion control method of wireless access network based on sensitive queue, w

4、hich improved the original price model of rem and overcame the in sensitivity of price to the change of queue size moreover, a single neuron was utilized to optimize the parameters finally, the proposed algorithm was compared with rem, pi on ns2 simulation platform. the simulation results show that

5、the proposed algorithm has fast con verge nee and strong robustnesskey words: wireless access network; congest:ion control; active queue management (aqm); random exponential marking (rem); single neuron0引言？近年来，无线接入网络的迅猛发展，使得网络拥 塞控制问题遇到了新的挑战。虽然在过去几十年里对 有线网络中的拥塞控制问题人们做了很多的研究，如 redfrandom early detecti

6、on) 1、pl(proportional-lntegral) 2、随机指数标记(random exponential marking, rem) 3、avq 4 (adaptive virtual queue)等。但由于无线接入网络运行中存在非 线性、时延大以及随机链路丢包等因素，使得经典主 动队列管理(active queue management, aqm)在实际 控制过程中有队列收敛速度慢、响应时间长等种种问 题。？rem算法的一个显著优点就是无论网络环境如何变化，队列长度稳态值都不会受到影响，链路利用率 也能保持较高水平而不变，但其过渡到稳态时的性能 却值得研究和改进。如文献5提出了

7、一种基于加强 型价格的随机指数标记(enhanced price-based rem, eprem)算法，在价格中引入流量变化率来加强对网 络拥塞的检测能力，但是队列过渡是否应该为“过渡”？ 请明确时间没有大的变化；文献6考虑了时延对算 法性能的影响，在价格中加入时延项来得到较为精确的拥塞精确度，能有效降低发送端不必要的重传，但 对队列控制的效果没有给出必要的分析；文献7提 出了一种基于速率的随机指数标记(rate-based exponential aqm, reaqm)算法，但只着重于降低丢 包概率，没有涉及队列的控制；文献8在价格中引 入积分项，并直接将价格作为标记概率，但参数的整 定较

8、rem更为困难；文献9采用自适应神经元的 方法在线调整参数，而没有对价格本身进行研究和分 析。?本文根据rem算法在无线接入网中的运行特点, 设计了 一种基于队列敏感性的随机指数标记(sensitive queue-based rem,sqrem)方法，其特点包括:1)在 rem 原先的基础上对价格进行改进，使其对路由中队列长 度的变化更为敏感，从而获得更快的响应时间以及更 好的队列收敛度;2)利用单神经元对改进后的价格参 数进行在线优化，从而获得更好的响应速度。通过ns2 网络仿真平台验证了该算法在响应时间、收敛度上都 优越于rem算法。？1 sqrem算法?rem的拥塞决策机制由两方面来衡

9、量：一是瞬时 队列与期望队列的差值；二是报文的到达速率与链路 带宽的差值。？两者加权形成价格pr,再由价格来决 定路由标记概率p。价格pr和概率p可描述为：？pr?rem?(t+l)=pr?rem?(t)+? 丫 (x(t) c?i+ a (q(t)-q?*)?p?rem?=1- 4)?-pr?rem?(t)? (1)? 其中：a >0和丫0是加权系数，pr(t)为价格,q(t) 是瞬时队列大小，q?*是期望队列大小，x(t)为报文到 达速率，c?i为链路带宽大小。？根据文献10对式(1)中的丢包概率p作泰勒展 开可以转化为式(2)： ?p?rem?=a?pr?rem?(t)-05?(a

10、?pr?rem?(t)?2+?(a?pr?rem?(t)?3/6+？其中 a=?ln? (b,因为 a?pr?rem?(t)?l,舍去 高次分量后可以将丢包概率近似地看作与链路上的价 格成正比。?通过上面的分析可以看到，rem算法是一个简化后的线性模型，根据价格来调整队列，但由于价格模 型本身的缺陷，它基于这样一个思想：假设网络参数 在足够长时间内不发生变化(如用户数量等)，算法就 能够收敛到最优值，这已不能适应如今复杂多变的网 络环境，这在文献口中做了细致的研究。文献12 也通过大量的仿真实验得出结论，rem在遇到网络环 境变化时队列调整时间过长，且队列在到达期望值之 前波动较为剧烈，这一现

11、象在无线接入网络中更为突 出。？aqm算法的一个主要目标是队列在 网络环境变化时能及时恢复到期望值附近，避免剧烈 的抖动。因此，针对rem算法在无线接入网中队列响 应慢、收敛度差等缺点，本文设计了一种启发式的基 于队列敏感性的随机指数标记（sqrem）算法，通过 在价格中引入误差的平方项，使路由中队列的变化能 更及时地反映到价格中。当网络中有突发数据流产生 的时候，误差平方的急速变大使价格快速升高，路由 通过主动丢包使瞬时队列能够快速地降到期望值附近。 同时，为了避免丢包概率对队列变化过分地敏感，以致 于队列剧烈抖动并对算法的稳定性造成影响，因此， 本文只采用误差平方，而不采用更高次项。？?更

12、改后的价格更新公式如下：？ pr?sqrem?(t+l)= pr?sqrem?(t)+ y (a (q(t) q?*)?2•?sgn?(q(t) q?*)+x(t) c?i) ?+(3)?其中?sgn?(x)是符号函数。？根据路由中队列长度的实际情况，价格更新公式 如?式：?pr?sqrem?(t+l)=?pr?sqrem?(t)+ y (x(t)c?i+? a (q(t) q?*)?2) ?+, q(t)2q?*?pr?sqrem?(t+l)= pr?sqrem?(t)+ y (x(t)- c?i ? a (q(t) q?*)?2) ?+, q(t)o； w?l(k)、w

13、?2(k)为加 权系数。本文采用?hebb?学习规则来实现加权系数的 在线优化，学习规则如下：？w?i(k+l)=w?i(k)+ h v?i(k)(7)?其中：h >0,为学习速率；v?i(k)为递进信号，米 用监督?hebb?学习算法：?v?i(k)=e(k)pr?sqrem?(k)x?i(k)(8)?其中e(k)=q(k) q?*为队列误差。为保证算法收敛性，对加权系数进行规范化处理：?i=w?i(k)/(z 2i=lw?i(k) (9)?从而得到最终的价格更新公式(10)： ?pr?sqrem?(t)=pr?sqrem?(t-l)+ 入(?l(k)x?l(k)?sgn?(x?l)+

14、?2(k)x?2(k)(10)?2算法性能分析?为验证sqrem算法在无线接入网中的性能，本文 使用ns-2.34仿真软件对该算法进行分析。仿真网络 采用如图2所示的哑铃型拓扑结构，？由n个有线发 送端、n个无线接收端、？一个基站以及一个路由r组 成，发送端与路由之间的链路带宽为10?mbps,时延 为10?ms,路由r与基站之间的瓶颈链路带宽设置为 0.5?mbps,传输延时为10?ms,路由缓存设置成150个 数据包路由缓存为150?pkts是否可以用中文来描述， 请明确。，无线接收端共享2?mbps的wlan带宽， mac协议为ieee?802.11o ?在仿真过程中，有线节点 （源端）

15、向对应的无线节点（接收端）发送大量的tcp数据, 平均分组大小为?l?000?bo ?实验1tcp连接数固定时瞬时队列长度比较。？ 首先，分析引入平方项后的rem算法（sqrem'） 和传统rem两种算法的性能，sqrem'与rem的设 置相同的参数，？即丫 =0.001, a =0.1, <=1.001,期 望队列长度q?*=60?pkts?包。设定n分别为20, 30,40, 50时，队列长度变化如图3所示。从图3中可以 看出，在实验开始阶段，路由中的队列呈直线上升趋 势,但相比较?rem?算法而言，?sqrem?/能够更快 地趋向实验所设置的期望队列长度q?*=60

16、?pkts?包 可以这样书写吗？，且稳定度更高。？?图3不同tcp连接数时rem与sqrem'的队列 长度比较(?y =0.001, a =0.1, 4)=1.001?)因“包”不 是国际上通用单位，根据出版规范，不能用作单位， 所以现在将图中的纵坐标的名称改为''瞬时队列包数”? 是否符合表达？请明确。若不符合，请给出一个准确 的纵坐标名称。从定性的角度来分析sqrem'与rem有更好的 收敛速度，更好的稳态性能。对图3经过定量化处理后， 表1给出了定量后的两种算法的比较。？队列过渡时间是指队列达到稳定所需时间，队列 过渡时间可以衡量aqm算法的动态性能。从表

17、1可 以看出，在相同网络参数下，sqrem'的过渡时间都 比rem小，且随着tcp连接数的增大，rem算法所需 的队列过渡时间也就越长，尤其是在?n?=50的情况下, 在仿真的160?s内没有达到稳定值，而sqrem'算法 的过渡时间始终在30-40?s,这与之前分析的一致，sqrem'算法有着更快的响应速度。？队长标准差可以衡量aqm算法的稳态性能。从表1可以看岀，在相同网络参数下，sqrem'比rem 有着更小的标准差，且随着tcp连接数的增大，rem 算法的队长标准差逐渐变大，说明队列抖动趋于剧烈, 但sqrem'算法的每包队长标准差始终在1923

18、,说 明sqrem'算法有着更好的稳定性。？虽然sqrem'较传统rem算法有不小的进步， 但由于参数配置问题，队列控制难以得到更好的效果。 sqrem用单神经元进行参数优化，算法主要参数设置 如下：？入=1, n ?l = 150, h ?2 = 50, ?在不同 tcp 连接数下的队列长度如图4所示。？比较图3、4,用单神经元优化后的sqrem比 sqrem'能快速地稳定在期望值附近，且队列稳定性 更高，收敛速度更快。？实验2负载突然变化时瞬时队列长度比较。？在现实网络中，负载变化是最常见的情况，也是 验证算法性能的重要途径。本实验中，初始tcp连接 数为 20,在

19、?40?s、?80?s、120?s 时，各加入 10 个 tcp 连接数，比较sqrem和rem、pi等算法在网络负载 突变的处理能力，仿真时间为?160?s, ?队列变化情况如图5所示。？图5(a)、(b)分别是rem和pi算法 随网络环境变化时路由中的队列长度变化情况，由图 可见，在网络中有突发数据流进入时，rem、pi的队 列都会发生剧烈抖动，需要一个过渡时间才会回到稳 定值。图5(c)是sqrem的队列变化情况，在突发数据 流时，队列长度没有明显的变化，能更好地适应网络 环境的变化。？3结语?rem算法在无线接入网中存在着收敛缓慢、稳定性差等缺点，针对这种情况，本文提出了 sqrem算

20、法，它利用误差的平方控制路由队列长度，并用单神经元 优化参数。通过ns2仿真实验表明，sqrem比rem、 pi算法有更好的收敛效果，更好的鲁棒性。？参考文献:?1floyd ?s,? jacobson ?v.? random early detectiongateways for congestion avoidanee j ieee/acm transactions on networking,1993, 1(4)： 397-413.?2hollot c v, misra v, towsley d, et al. on designing improved controllers for

21、aqm routers supporting tcp flows c / proceedings of the twentieth annu al joi nt con fere nee of the ieeecomputer and communications societies piscataway:ieee press, 2001：1726-1734.?3athuraliya s, low s h, u v h, et al. rem: active queue man ageme nt j i eee network magazi me, 2001, 15(3):48-53.?4ku

22、nniyur s, srikant r. an adaptive virtual queue (avq) algorithm for active queue management j ieee/acm transactions on networking, 2004, 12(2): 286-299.汪浩,牛玉刚基于加强型价格的随机指数标记算法j华东理工大学学报：自然科学版，2009,35(3)：4-53.魏星光，刘渊改进的aqm在拥塞机制中的应用策略j 计算机工程与应用，2010, 46(4)： 83-86.?7wang ?jun,? song ?min,?yang ?houjun.? ?rate-based? active queue manage