基于改進(jìn)單神經(jīng)元梯度學(xué)習(xí)的無(wú)線網(wǎng)絡(luò)主動(dòng)隊(duì)列管理

戚愛(ài)春,徐 磊

(1.上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院,上海 200444;2.南京中興力維軟件有限公司動(dòng)環(huán)與智能運(yùn)維產(chǎn)品開(kāi)發(fā)部,南京 211153)

主動(dòng)隊(duì)列管理(active queue management,AQM)是鏈路算法的重點(diǎn)內(nèi)容,也是主要的研究熱點(diǎn).文獻(xiàn)[1]提出了三區(qū)域隨機(jī)早期檢測(cè)(three-section random early detection,TRED)算法,以便實(shí)現(xiàn)時(shí)延及網(wǎng)絡(luò)負(fù)載吞吐量之間的均衡.Ko 等[2]提出了fairness-aware delaycontrolled 主動(dòng)隊(duì)列管理技術(shù),實(shí)現(xiàn)對(duì)基于802.11 s 的網(wǎng)絡(luò)的性能優(yōu)化.與源端控制算法不同,鏈路算法主要考慮的是中間節(jié)點(diǎn)的情況,考慮到現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)中網(wǎng)絡(luò)節(jié)點(diǎn)眾多的特點(diǎn),鏈路算法的優(yōu)越性更加明顯[3].

但是隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大,特別是無(wú)線局域網(wǎng)(wireless local area network,WLAN)、無(wú)線網(wǎng)狀網(wǎng)絡(luò)(wireless mesh network,WMN)等網(wǎng)絡(luò)類型的增加,網(wǎng)絡(luò)的服務(wù)質(zhì)量令人堪憂,傳統(tǒng)的擁塞控制算法已經(jīng)無(wú)法滿足用戶需求[4].于是,為了滿足不斷提高的主動(dòng)隊(duì)列管理需求,很多先進(jìn)的控制理論被應(yīng)用到AQM 中,如模糊控制[5]、信息壓縮[6]、模型預(yù)測(cè)控制[7].

人工神經(jīng)網(wǎng)絡(luò)是通過(guò)對(duì)神經(jīng)元系統(tǒng)處理事務(wù)的過(guò)程進(jìn)行深入研究得到的,并以計(jì)算機(jī)為媒介展現(xiàn)出來(lái).人工神經(jīng)網(wǎng)絡(luò)具有自適應(yīng)、自學(xué)習(xí)、分布并行式處理等優(yōu)勢(shì),不僅被生物學(xué)家看作研究生物現(xiàn)象的工具,還被工程師作為解決非線性時(shí)變復(fù)雜系統(tǒng)的新方法,如今已被廣泛應(yīng)用于各個(gè)領(lǐng)域[8].考慮到無(wú)線局域網(wǎng)絡(luò)是非線性、多變且復(fù)雜的系統(tǒng)[9],相比于有線網(wǎng)絡(luò),在網(wǎng)絡(luò)擁塞控制方面存在著諸多挑戰(zhàn).此外,由于主動(dòng)隊(duì)列管理算法主要應(yīng)用于傳統(tǒng)有線網(wǎng)絡(luò),很少應(yīng)用于無(wú)線網(wǎng)絡(luò),針對(duì)這一現(xiàn)象,本工作首先描述傳統(tǒng)有線網(wǎng)絡(luò)TCP/AQM 數(shù)學(xué)模型,然后結(jié)合無(wú)線局域網(wǎng)絡(luò)的特性,對(duì)傳統(tǒng)模型進(jìn)行改進(jìn),得到適用于無(wú)線局域網(wǎng)絡(luò)的TCP/AQM數(shù)學(xué)模型.

在傳統(tǒng)的主動(dòng)隊(duì)列管理算法中,大部分控制輸入均為網(wǎng)絡(luò)的瞬時(shí)隊(duì)列長(zhǎng)度,而瞬時(shí)隊(duì)列長(zhǎng)度只能反映當(dāng)前的網(wǎng)絡(luò)擁塞狀況,忽略了下一時(shí)刻網(wǎng)絡(luò)的擁塞發(fā)展趨勢(shì).考慮到網(wǎng)絡(luò)擁塞的真正原因是數(shù)據(jù)包到達(dá)鏈路的速率高于當(dāng)前的網(wǎng)絡(luò)帶寬,本工作以此為出發(fā)點(diǎn),增加數(shù)據(jù)包到達(dá)速率作為AQM 算法的輸入量,用來(lái)反映下一時(shí)刻網(wǎng)絡(luò)擁塞的持續(xù)狀態(tài),從而提出基于單神經(jīng)元梯度學(xué)習(xí)[10]的AQM 改進(jìn)算法,即改進(jìn)單神經(jīng)元梯度學(xué)習(xí)(improves single neuron gradient learning,ISNGL)算法.本算法通過(guò)梯度學(xué)習(xí)算法動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)參數(shù),并在原算法的收斂速度和穩(wěn)定性方面加以改進(jìn),使得控制效果進(jìn)一步提升.

1 系統(tǒng)描述

1.1 研究對(duì)象及數(shù)學(xué)模型

本工作主要研究對(duì)象是無(wú)線局域網(wǎng)絡(luò).考慮TCP 的加性增加、乘性減少和隊(duì)列長(zhǎng)度的動(dòng)態(tài)特性,Zheng 等[11]提出了如下TCP/AQM 數(shù)學(xué)模型,

式中:W(t)表示TCP 在t 時(shí)刻的擁塞窗口;P(t)表示路由器丟包率；τ(t)表示往返時(shí)間;Tp為傳輸延時(shí);q(t)表示t 時(shí)刻的隊(duì)列長(zhǎng)度;N(t)表示網(wǎng)絡(luò)負(fù)載數(shù)量;C(t)表示瓶頸鏈路的容量;上行鏈路和下行鏈路的丟包率Pul=Pdl=γ ?1.

假設(shè)在同一時(shí)刻,發(fā)送端、路由器和接收端之間只有一個(gè)鏈路成功,再結(jié)合無(wú)線局域網(wǎng)絡(luò)的特性,對(duì)原有模型進(jìn)行修改,得到以下非線性微分方程:

假設(shè)在上述模型中,網(wǎng)絡(luò)負(fù)載N(t) 和瓶頸鏈路容量C(t) 分別為常數(shù)N 和C,對(duì)平衡點(diǎn)(W0,q0,P0)采用小信號(hào)法進(jìn)行局部線性化和Laplace 變換得到如下傳遞函數(shù):

于是,由無(wú)線局域網(wǎng)絡(luò)數(shù)學(xué)模型可以得到控制系統(tǒng)框圖如圖1 所示.

圖1 TCP/AQM 控制系統(tǒng)Fig.1 TCP/AQM control system

由于實(shí)際無(wú)線網(wǎng)絡(luò)的非線性、時(shí)延、參數(shù)多變等問(wèn)題會(huì)導(dǎo)致無(wú)線TCP/AQM 數(shù)學(xué)模型不夠精確,為此需要設(shè)計(jì)一個(gè)具有動(dòng)態(tài)學(xué)習(xí)能力的控制器,以提高實(shí)際情況中隊(duì)列長(zhǎng)度的收斂性和收斂速度(見(jiàn)圖2).

圖2 動(dòng)態(tài)學(xué)習(xí)TCP/AQM 控制系統(tǒng)Fig.2 Dynamic learning TCP/AQM control system

1.2 單神經(jīng)元AQM 控制器

單神經(jīng)元AQM 控制器以瞬時(shí)隊(duì)列長(zhǎng)度q(t)與期望隊(duì)列長(zhǎng)度qref的誤差q(t)?qref作為第一輸入,以數(shù)據(jù)包到達(dá)速率x(t)與鏈路帶寬C 的差值x(t)?C 作為第二輸入,則可以得到單神經(jīng)元的輸入為e(t)=[e1(t),e2(t)]=[q(t)?qref,x(t)?C].為了采用梯度學(xué)習(xí)算法來(lái)影響輸出,本工作為單神經(jīng)元的輸入加上動(dòng)態(tài)調(diào)整的網(wǎng)絡(luò)參數(shù)w(t)=[w1(t),w2(t)]T,則單神經(jīng)元的總輸入為

由于無(wú)線局域網(wǎng)絡(luò)的數(shù)學(xué)模型是非線性的,需要為神經(jīng)網(wǎng)絡(luò)引入非線性因素,使其擁有任意逼近任何非線性函數(shù)的能力.于是,使用激活函數(shù)激活神經(jīng)元,考慮到存在符號(hào)問(wèn)題,選擇與Sigmoid 函數(shù)屬性相類似的Tanh 函數(shù),則神經(jīng)元的輸出為

丟棄概率為

綜上所述,單神經(jīng)元AQM 控制器框圖如圖3 所示.

圖3 單神經(jīng)元AQM 控制器Fig.3 Single neuron AQM controller

下面采用梯度學(xué)習(xí)算法動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)參數(shù)w(t).首先,定義系統(tǒng)的目標(biāo)函數(shù)E(t)為

為使隊(duì)列長(zhǎng)度趨于穩(wěn)定,需要使式(7)取最小值,于是經(jīng)反向傳播學(xué)習(xí),系統(tǒng)網(wǎng)絡(luò)參數(shù)w(t)為

式中:η為學(xué)習(xí)速率.為了計(jì)算梯度方向,可將梯度方向擴(kuò)展為

考慮到無(wú)線網(wǎng)絡(luò)的非線性和不確定性,無(wú)法直接計(jì)算出?q(t)/?y(t)的值,于是采用q(t)和y(t)變化值的符號(hào)函數(shù)來(lái)代替,

接下來(lái)計(jì)算y(t)對(duì)z(t)的偏導(dǎo)數(shù),得到

于是網(wǎng)絡(luò)參數(shù)w(t)調(diào)整為

1.3 控制器改進(jìn)

雖然單神經(jīng)元控制器相比于傳統(tǒng)AQM 控制器在動(dòng)態(tài)調(diào)節(jié)、控制效果等方面均具有優(yōu)越性,但是依然存在一些不足.

(1) 平坦區(qū)域收斂速度慢.

由于激活函數(shù)采用的是Tanh函數(shù),當(dāng)z(t) →+∞或z(t) →?∞時(shí),f(z(t)) →1 或f(z(t))→?1,這導(dǎo)致f(z(t))′≈0,即進(jìn)入了平坦區(qū)域.而由式(11)和(12)可知,此時(shí)無(wú)論如何改變學(xué)習(xí)速率η,權(quán)值的調(diào)整效果將不再顯著,最終導(dǎo)致收斂速度變慢.

(2) 學(xué)習(xí)時(shí)間較長(zhǎng).

由于采用梯度學(xué)習(xí)算法進(jìn)行參數(shù)動(dòng)態(tài)調(diào)整,在學(xué)習(xí)的過(guò)程中,梯度的下降方向一直朝著最快的方向.然而,相對(duì)于網(wǎng)絡(luò)這種實(shí)時(shí)多變系統(tǒng),誤差值一直都在變化,缺少前期知識(shí)的累積,想要達(dá)到最優(yōu)值就需要多次學(xué)習(xí),這樣往往會(huì)增加單神經(jīng)元的學(xué)習(xí)時(shí)間.

針對(duì)上述不足,對(duì)單神經(jīng)元控制器作出以下改進(jìn).

(1) 設(shè)置帶有位移參數(shù)的新激活函數(shù).

由式(11)和(12)可知,當(dāng)學(xué)習(xí)速率η 一定時(shí),激活函數(shù)的導(dǎo)數(shù)值越大,權(quán)值的調(diào)整效果越明顯.于是設(shè)置帶有位移參數(shù)的新激活函數(shù)為

式中:a 為位移參數(shù);σ 為界限值,通常σ 的值比較小.

從改進(jìn)后的方法可知,當(dāng)目標(biāo)函數(shù)的變化值小于σ,即進(jìn)入平坦區(qū)域時(shí),使用帶有位移參數(shù)的激活函數(shù)可以使控制器加速越過(guò)平坦區(qū)域;當(dāng)處于陡峭區(qū)域時(shí),依舊使用原來(lái)的激活函數(shù).這樣處理有效緩解了平坦區(qū)域權(quán)值調(diào)整效果不佳的問(wèn)題,從而提高了參數(shù)收斂的速度.

(2) 增加權(quán)值調(diào)整動(dòng)量.

針對(duì)梯度學(xué)習(xí)算法總是沿著最陡梯度下降,缺少知識(shí)積累的問(wèn)題,本工作引入增加權(quán)值調(diào)整動(dòng)量的改進(jìn)方法.在考慮本次誤差調(diào)整的梯度方向外,增加上次的調(diào)整梯度,使原本沿最陡梯度方向調(diào)整改為沿誤差曲面的平均方向調(diào)整,并不斷累加調(diào)整動(dòng)量,為后續(xù)學(xué)習(xí)提供知識(shí)積累,縮短學(xué)習(xí)時(shí)間.于是權(quán)值調(diào)整公式為

式中:β(t)?w(t)為權(quán)值調(diào)整動(dòng)量;β(t)為動(dòng)量系數(shù),通常0<β(t)<1.

在實(shí)際網(wǎng)絡(luò)中,當(dāng)誤差逐漸變小并接近期望值時(shí),說(shuō)明誤差修正的方向是正確的;反之,當(dāng)誤差逐漸變大并偏離期望值時(shí),說(shuō)明誤差修正的方向是錯(cuò)誤的.為了使權(quán)值調(diào)整動(dòng)量更加精確,考慮到并非所有的梯度方向都是完全正確的,本工作將權(quán)值調(diào)整動(dòng)量中的動(dòng)量系數(shù)進(jìn)行動(dòng)態(tài)變化,并采用模糊控制來(lái)動(dòng)態(tài)調(diào)整.

設(shè)模糊控制的輸入值為q(t)與qref的誤差值變化de(t)以及目標(biāo)函數(shù)的變化dE(t),

將系統(tǒng)輸入值de(t)和dE(t)的模糊區(qū)域設(shè)為[–4.5,4.5],將模糊集劃分為7 個(gè)子集,分別為負(fù)大(NB)、負(fù)中(NM)、負(fù)小(NS)、零(Z)、正小(PS)、正中(PM)和正大(PB).隸屬度函數(shù)采用高斯型,

式中:ci和bi分別為隸屬度函數(shù)的中間點(diǎn)和寬.

在t 時(shí)刻,模糊控制的輸出為K(t),則其模糊集也劃分為7 個(gè)子集,分別為非常小(TS)、很小(VS)、小(S)、中(M)、大(B)、很大(VB)、非常大(TB),對(duì)應(yīng)的論域?yàn)閧a1,a2,a3,a4,a5,a6,a7},其中ai(i=1,2,···,7)為相應(yīng)的值.

假設(shè)模糊規(guī)則之間的關(guān)系是局部的,于是建立如下模糊規(guī)則:

這里通過(guò)max-min 復(fù)合運(yùn)算合成規(guī)則,則模糊規(guī)則如表1 所示.

表1 模糊規(guī)則Table 1 Fuzzy rules

通過(guò)重心法去模糊得到輸出,則神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)速率為

這樣,權(quán)值調(diào)整動(dòng)量將以準(zhǔn)確的動(dòng)量系數(shù)進(jìn)行動(dòng)態(tài)附加,改進(jìn)了誤差修正方向,同時(shí)為后續(xù)學(xué)習(xí)提供了知識(shí)積累,縮短了學(xué)習(xí)時(shí)間.

需要說(shuō)明的是,本工作考慮了上行鏈路和下行鏈路的丟包率遠(yuǎn)小于1 的情況.考慮到TCP 的穩(wěn)定性,當(dāng)丟包率接近1 時(shí),會(huì)導(dǎo)致發(fā)包率增加且網(wǎng)絡(luò)更早地進(jìn)入擁塞狀況.此時(shí),本工作所提出的方法仍然可行,為簡(jiǎn)要起見(jiàn),略去相應(yīng)結(jié)果.

2 仿真與分析

為了驗(yàn)證ISNGL 算法的性能,利用網(wǎng)絡(luò)模擬軟件NS2 對(duì)算法進(jìn)行仿真研究.在NS2 中,搭建如圖4 所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).

圖4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.4 Structure of network topology

圖4 中:BS(base station)為基站;R0 和R1 分別為無(wú)線域和有線域路由器;Src1～Srcn為數(shù)據(jù)發(fā)送的源端,這里源端數(shù)量為20 個(gè);Dst 為數(shù)據(jù)接收端.Dst 和R1 之間的鏈路帶寬為10 Mbit/s,時(shí)延為10 ms;BS 與R1 之間的瓶頸鏈路帶寬為10 Mbit/s,時(shí)延為20 ms.設(shè)上下鏈路的丟包概率為0.01,傳輸?shù)臄?shù)據(jù)包大小為500 bytes,最大隊(duì)列長(zhǎng)度為300 packets,期望隊(duì)列長(zhǎng)度為100 packets.仿真時(shí)間為240 s.

對(duì)于ISNGL 算法,設(shè)置參數(shù)a1=0.4,a2=0.6,a3=0.65,a4=0.7,a5=0.75,a6=0.8,a7=1.0,a=2.0,σ=2.5,w1=0.000 005 601 9,w2=0.000 002 654.

實(shí)驗(yàn)一:為了驗(yàn)證ISNGL 算法在維持瞬時(shí)隊(duì)列長(zhǎng)度穩(wěn)定性方面的性能,將ISNGL 與其他算法進(jìn)行對(duì)比,則隊(duì)列長(zhǎng)度變化如圖5 所示.由于無(wú)線路由器先要與基站進(jìn)行鏈接,所以源端的數(shù)據(jù)在幾秒鐘以后才開(kāi)始傳輸.

瞬時(shí)隊(duì)列長(zhǎng)度是鏈路緩存區(qū)中等待分組轉(zhuǎn)發(fā)的數(shù)據(jù)包的數(shù)量,在AQM 算法中是檢測(cè)網(wǎng)絡(luò)擁塞的重要指標(biāo).從圖5 可以看出,ISNGL 算法在隊(duì)列長(zhǎng)度穩(wěn)定性方面要優(yōu)于其他算法.由于設(shè)置了帶有位移參數(shù)的新激活函數(shù)并增加了權(quán)值調(diào)整動(dòng)量,相較于以往的SNGL 算法,ISNGL 算法隊(duì)列長(zhǎng)度的收斂速度提高,學(xué)習(xí)時(shí)間縮短.因此實(shí)驗(yàn)結(jié)果驗(yàn)證了ISNGL 算法的有效性.

圖5 ISNGL 算法和其他算法的瞬時(shí)隊(duì)列長(zhǎng)度Fig.5 Instantaneous queue length of ISNGL algorithm and other algorithms

實(shí)驗(yàn)二:為了驗(yàn)證ISNGL 算法對(duì)突發(fā)數(shù)據(jù)流的適應(yīng)性,考慮如圖6 所示的實(shí)驗(yàn),n 為源端開(kāi)始數(shù)量.

由圖6 可見(jiàn),當(dāng)網(wǎng)絡(luò)中出現(xiàn)突發(fā)性數(shù)據(jù)流時(shí),瞬時(shí)隊(duì)列長(zhǎng)度會(huì)有明顯的抖動(dòng),而當(dāng)網(wǎng)絡(luò)中的數(shù)據(jù)流減少時(shí),瞬時(shí)隊(duì)列的長(zhǎng)度同樣也會(huì)抖動(dòng),但是沒(méi)有數(shù)據(jù)流增加時(shí)的抖動(dòng)程度大.即便有明顯抖動(dòng),ISNGL 算法還是能夠在較短的時(shí)間內(nèi)將隊(duì)列長(zhǎng)度收斂于期望值附近.當(dāng)網(wǎng)絡(luò)負(fù)載穩(wěn)定時(shí),隊(duì)列長(zhǎng)度也能夠保持相對(duì)穩(wěn)定,這說(shuō)明ISNGL 算法在網(wǎng)絡(luò)中出現(xiàn)爆發(fā)性增減數(shù)據(jù)流時(shí)有較好的適應(yīng)性.

圖6 動(dòng)態(tài)負(fù)載下的瞬時(shí)隊(duì)列Fig.6 Instantaneous queue under dynamic loads

3 結(jié)束語(yǔ)

本工作針對(duì)傳統(tǒng)AQM 算法忽略下一時(shí)刻網(wǎng)絡(luò)擁塞發(fā)展趨勢(shì)的問(wèn)題,引入數(shù)據(jù)包到達(dá)速率作為輸入量,提出了基于單神經(jīng)元梯度學(xué)習(xí)的AQM 改進(jìn)算法.首先介紹了單神經(jīng)元梯度學(xué)習(xí)的原理,從中分析其在收斂速度和學(xué)習(xí)時(shí)間方面的不足,提出了帶有位移參數(shù)的激活函數(shù)和融合模糊控制的權(quán)值調(diào)整動(dòng)量項(xiàng)的改進(jìn),使算法在控制效果上得到進(jìn)一步提高.NS2 仿真結(jié)果表明,相比于常見(jiàn)的AQM 算法,ISNGL 算法可以更好地將瞬時(shí)隊(duì)列長(zhǎng)度收斂于期望值附近,穩(wěn)定性更高;同時(shí),ISNGL 算法對(duì)于突發(fā)數(shù)據(jù)流也具有較強(qiáng)的適應(yīng)性,而且在大延時(shí)或動(dòng)態(tài)變化的環(huán)境下也能夠迅速調(diào)整網(wǎng)絡(luò)參數(shù),控制效果顯著.