基于隊列敏感性的無線接入網(wǎng)絡(luò)擁塞控制算法

1、基于隊列敏感性的無線接入網(wǎng)絡(luò)擁塞控制算法文章編號:1001-9081(2012)01-0123-04doi:10.3724/spj.1087.2012.00123摘要:由于無線接入網(wǎng)絡(luò)存在強非線性、大時延 以及隨機鏈路丟包等因素，導致經(jīng)典主動隊列管理 (aqm)算法在實際控制時存在隊列收斂速度慢、響應(yīng) 時間長等問題。通過分析隨機指數(shù)標記(rem)算法在無 線接入網(wǎng)中的特點，在原先rem價格模型的基礎(chǔ)上對 其進行了改進，以隊列誤差的平方項來克服價格對隊 列變化不敏感的缺陷，從而提出了一種基于隊列敏感 性的無線接入網(wǎng)絡(luò)擁塞控制算法，并利用單神經(jīng)網(wǎng)絡(luò) 對其參數(shù)進行了優(yōu)化。最后，通過ns2仿真平臺對所

2、 提算法與rem> pi算法進行對比，實驗表明所提算法 擁有隊列收斂快、魯棒性強的優(yōu)點。?關(guān)鍵詞:無線接入網(wǎng)絡(luò)；擁塞控制；主動隊列管 理；隨機指數(shù)標記；單神經(jīng)元?中圖分類號: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引言？近年來，無線接入網(wǎng)絡(luò)的迅猛發(fā)展，使得網(wǎng)絡(luò)擁 塞控制問題遇到了新的挑戰(zhàn)。雖然在過去幾十年里對 有線網(wǎng)絡(luò)中的擁塞控制問題人們做了很多的研究，如 redfrandom early detecti

6、on) 1、pl(proportional-lntegral) 2、隨機指數(shù)標記(random exponential marking, rem) 3、avq 4 (adaptive virtual queue)等。但由于無線接入網(wǎng)絡(luò)運行中存在非 線性、時延大以及隨機鏈路丟包等因素，使得經(jīng)典主 動隊列管理(active queue management, aqm)在實際 控制過程中有隊列收斂速度慢、響應(yīng)時間長等種種問 題。？rem算法的一個顯著優(yōu)點就是無論網(wǎng)絡(luò)環(huán)境如何變化，隊列長度穩(wěn)態(tài)值都不會受到影響，鏈路利用率 也能保持較高水平而不變，但其過渡到穩(wěn)態(tài)時的性能 卻值得研究和改進。如文獻5提出了

7、一種基于加強 型價格的隨機指數(shù)標記(enhanced price-based rem, eprem)算法，在價格中引入流量變化率來加強對網(wǎng) 絡(luò)擁塞的檢測能力，但是隊列過渡是否應(yīng)該為“過渡”？ 請明確時間沒有大的變化；文獻6考慮了時延對算 法性能的影響，在價格中加入時延項來得到較為精確的擁塞精確度，能有效降低發(fā)送端不必要的重傳，但 對隊列控制的效果沒有給出必要的分析；文獻7提 出了一種基于速率的隨機指數(shù)標記(rate-based exponential aqm, reaqm)算法，但只著重于降低丟 包概率，沒有涉及隊列的控制；文獻8在價格中引 入積分項，并直接將價格作為標記概率，但參數(shù)的整 定較

8、rem更為困難；文獻9采用自適應(yīng)神經(jīng)元的 方法在線調(diào)整參數(shù)，而沒有對價格本身進行研究和分 析。?本文根據(jù)rem算法在無線接入網(wǎng)中的運行特點, 設(shè)計了 一種基于隊列敏感性的隨機指數(shù)標記(sensitive queue-based rem,sqrem)方法，其特點包括:1)在 rem 原先的基礎(chǔ)上對價格進行改進，使其對路由中隊列長 度的變化更為敏感，從而獲得更快的響應(yīng)時間以及更 好的隊列收斂度;2)利用單神經(jīng)元對改進后的價格參 數(shù)進行在線優(yōu)化，從而獲得更好的響應(yīng)速度。通過ns2 網(wǎng)絡(luò)仿真平臺驗證了該算法在響應(yīng)時間、收斂度上都 優(yōu)越于rem算法。？1 sqrem算法?rem的擁塞決策機制由兩方面來衡

9、量：一是瞬時 隊列與期望隊列的差值；二是報文的到達速率與鏈路 帶寬的差值。？兩者加權(quán)形成價格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是加權(quán)系數(shù)，pr(t)為價格,q(t) 是瞬時隊列大小，q?*是期望隊列大小，x(t)為報文到 達速率，c?i為鏈路帶寬大小。？根據(jù)文獻10對式(1)中的丟包概率p作泰勒展 開可以轉(zhuǎn)化為式(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算法是一個簡化后的線性模型，根據(jù)價格來調(diào)整隊列，但由于價格模 型本身的缺陷，它基于這樣一個思想：假設(shè)網(wǎng)絡(luò)參數(shù) 在足夠長時間內(nèi)不發(fā)生變化(如用戶數(shù)量等)，算法就 能夠收斂到最優(yōu)值，這已不能適應(yīng)如今復(fù)雜多變的網(wǎng) 絡(luò)環(huán)境，這在文獻口中做了細致的研究。文獻12 也通過大量的仿真實驗得出結(jié)論，rem在遇到網(wǎng)絡(luò)環(huán) 境變化時隊列調(diào)整時間過長，且隊列在到達期望值之 前波動較為劇烈，這一現(xiàn)

11、象在無線接入網(wǎng)絡(luò)中更為突 出。？aqm算法的一個主要目標是隊列在 網(wǎng)絡(luò)環(huán)境變化時能及時恢復(fù)到期望值附近，避免劇烈 的抖動。因此，針對rem算法在無線接入網(wǎng)中隊列響 應(yīng)慢、收斂度差等缺點，本文設(shè)計了一種啟發(fā)式的基 于隊列敏感性的隨機指數(shù)標記（sqrem）算法，通過 在價格中引入誤差的平方項，使路由中隊列的變化能 更及時地反映到價格中。當網(wǎng)絡(luò)中有突發(fā)數(shù)據(jù)流產(chǎn)生 的時候，誤差平方的急速變大使價格快速升高，路由 通過主動丟包使瞬時隊列能夠快速地降到期望值附近。 同時，為了避免丟包概率對隊列變化過分地敏感，以致 于隊列劇烈抖動并對算法的穩(wěn)定性造成影響，因此， 本文只采用誤差平方，而不采用更高次項。？?更

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)是符號函數(shù)。？根據(jù)路由中隊列長度的實際情況，價格更新公式 如?式：?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)為加 權(quán)系數(shù)。本文采用?hebb?學習規(guī)則來實現(xiàn)加權(quán)系數(shù)的 在線優(yōu)化，學習規(guī)則如下：？w?i(k+l)=w?i(k)+ h v?i(k)(7)?其中：h >0,為學習速率；v?i(k)為遞進信號，米 用監(jiān)督?hebb?學習算法：?v?i(k)=e(k)pr?sqrem?(k)x?i(k)(8)?其中e(k)=q(k) q?*為隊列誤差。為保證算法收斂性，對加權(quán)系數(shù)進行規(guī)范化處理：?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算法在無線接入網(wǎng)中的性能，本文 使用ns-2.34仿真軟件對該算法進行分析。仿真網(wǎng)絡(luò) 采用如圖2所示的啞鈴型拓撲結(jié)構(gòu)，？由n個有線發(fā) 送端、n個無線接收端、？一個基站以及一個路由r組 成，發(fā)送端與路由之間的鏈路帶寬為10?mbps,時延 為10?ms,路由r與基站之間的瓶頸鏈路帶寬設(shè)置為 0.5?mbps,傳輸延時為10?ms,路由緩存設(shè)置成150個 數(shù)據(jù)包路由緩存為150?pkts是否可以用中文來描述， 請明確。，無線接收端共享2?mbps的wlan帶寬， mac協(xié)議為ieee?802.11o ?在仿真過程中，有線節(jié)點 （源端）

15、向?qū)?yīng)的無線節(jié)點（接收端）發(fā)送大量的tcp數(shù)據(jù), 平均分組大小為?l?000?bo ?實驗1tcp連接數(shù)固定時瞬時隊列長度比較。？ 首先，分析引入平方項后的rem算法（sqrem'） 和傳統(tǒng)rem兩種算法的性能，sqrem'與rem的設(shè) 置相同的參數(shù)，？即丫 =0.001, a =0.1, <=1.001,期 望隊列長度q?*=60?pkts?包。設(shè)定n分別為20, 30,40, 50時，隊列長度變化如圖3所示。從圖3中可以 看出，在實驗開始階段，路由中的隊列呈直線上升趨 勢,但相比較?rem?算法而言，?sqrem?/能夠更快 地趨向?qū)嶒炈O(shè)置的期望隊列長度q?*=60

16、?pkts?包 可以這樣書寫嗎？，且穩(wěn)定度更高。？?圖3不同tcp連接數(shù)時rem與sqrem'的隊列 長度比較(?y =0.001, a =0.1, 4)=1.001?)因“包”不 是國際上通用單位，根據(jù)出版規(guī)范，不能用作單位， 所以現(xiàn)在將圖中的縱坐標的名稱改為''瞬時隊列包數(shù)”? 是否符合表達？請明確。若不符合，請給出一個準確 的縱坐標名稱。從定性的角度來分析sqrem'與rem有更好的 收斂速度，更好的穩(wěn)態(tài)性能。對圖3經(jīng)過定量化處理后， 表1給出了定量后的兩種算法的比較。？隊列過渡時間是指隊列達到穩(wěn)定所需時間，隊列 過渡時間可以衡量aqm算法的動態(tài)性能。從表

17、1可 以看出，在相同網(wǎng)絡(luò)參數(shù)下，sqrem'的過渡時間都 比rem小，且隨著tcp連接數(shù)的增大，rem算法所需 的隊列過渡時間也就越長，尤其是在?n?=50的情況下, 在仿真的160?s內(nèi)沒有達到穩(wěn)定值，而sqrem'算法 的過渡時間始終在30-40?s,這與之前分析的一致，sqrem'算法有著更快的響應(yīng)速度。？隊長標準差可以衡量aqm算法的穩(wěn)態(tài)性能。從表1可以看岀，在相同網(wǎng)絡(luò)參數(shù)下，sqrem'比rem 有著更小的標準差，且隨著tcp連接數(shù)的增大，rem 算法的隊長標準差逐漸變大，說明隊列抖動趨于劇烈, 但sqrem'算法的每包隊長標準差始終在1923

18、,說 明sqrem'算法有著更好的穩(wěn)定性。？雖然sqrem'較傳統(tǒng)rem算法有不小的進步， 但由于參數(shù)配置問題，隊列控制難以得到更好的效果。 sqrem用單神經(jīng)元進行參數(shù)優(yōu)化，算法主要參數(shù)設(shè)置 如下：？入=1, n ?l = 150, h ?2 = 50, ?在不同 tcp 連接數(shù)下的隊列長度如圖4所示。？比較圖3、4,用單神經(jīng)元優(yōu)化后的sqrem比 sqrem'能快速地穩(wěn)定在期望值附近，且隊列穩(wěn)定性 更高，收斂速度更快。？實驗2負載突然變化時瞬時隊列長度比較。？在現(xiàn)實網(wǎng)絡(luò)中，負載變化是最常見的情況，也是 驗證算法性能的重要途徑。本實驗中，初始tcp連接 數(shù)為 20,在

19、?40?s、?80?s、120?s 時，各加入 10 個 tcp 連接數(shù)，比較sqrem和rem、pi等算法在網(wǎng)絡(luò)負載 突變的處理能力，仿真時間為?160?s, ?隊列變化情況如圖5所示。？圖5(a)、(b)分別是rem和pi算法 隨網(wǎng)絡(luò)環(huán)境變化時路由中的隊列長度變化情況，由圖 可見，在網(wǎng)絡(luò)中有突發(fā)數(shù)據(jù)流進入時，rem、pi的隊 列都會發(fā)生劇烈抖動，需要一個過渡時間才會回到穩(wěn) 定值。圖5(c)是sqrem的隊列變化情況，在突發(fā)數(shù)據(jù) 流時，隊列長度沒有明顯的變化，能更好地適應(yīng)網(wǎng)絡(luò) 環(huán)境的變化。？3結(jié)語?rem算法在無線接入網(wǎng)中存在著收斂緩慢、穩(wěn)定性差等缺點，針對這種情況，本文提出了 sqrem算

20、法，它利用誤差的平方控制路由隊列長度，并用單神經(jīng)元 優(yōu)化參數(shù)。通過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.汪浩,牛玉剛基于加強型價格的隨機指數(shù)標記算法j華東理工大學學報：自然科學版，2009,35(3)：4-53.魏星光，劉淵改進的aqm在擁塞機制中的應(yīng)用策略j 計算機工程與應(yīng)用，2010, 46(4)： 83-86.?7wang ?jun,? song ?min,?yang ?houjun.? ?rate-based? active queue manage