雙學習率自適應(yīng)的Q路由算法

沙鑫磊，白光偉，張 杰，趙文天，沈 航，2(南京工業(yè)大學計算機科學與技術(shù)學院，南京286)

2(南京大學計算機軟件新技術(shù)國家重點實驗室，南京210093)E-mail:shaxinlei@njtech.edu.cn

1 引言

最近，隨著聯(lián)網(wǎng)移動設(shè)備數(shù)量不斷增加，以及異構(gòu)、無線通信網(wǎng)絡(luò)基礎(chǔ)設(shè)施方面的巨大進步，互聯(lián)網(wǎng)流量出現(xiàn)了大幅增長.網(wǎng)絡(luò)流量的快速增長，給通信網(wǎng)絡(luò)帶來了巨大的壓力，導致了資源配置和管理的問題，影響了用戶的消費質(zhì)量(QoE).這主要是因為網(wǎng)絡(luò)仍然在幾十年前設(shè)計的路由框架上運行.事實上，隨著網(wǎng)絡(luò)的不斷發(fā)展，有效的網(wǎng)絡(luò)流量控制，如路由方法，已經(jīng)成為了當前一個關(guān)鍵的挑戰(zhàn).現(xiàn)有網(wǎng)絡(luò)中使用的路由協(xié)議大都基于傳統(tǒng)的路由策略距離矢量或鏈路代價［10-12］計算源到目的地的最短路徑.在傳統(tǒng)路由策略下，最短路徑上的節(jié)點會比其它節(jié)點承受更多的負載，易出現(xiàn)鏈路擁塞、丟包、網(wǎng)絡(luò)延遲增大等情況.此外，當擁塞、丟包等情況再次出現(xiàn)時，傳統(tǒng)的路由策略通常不會從它們以往的經(jīng)驗(擁塞，延遲等)中學習，仍然會做出同樣的路由決策(選擇最短路徑)，加劇網(wǎng)絡(luò)性能的下降.因此，有必要以一種智能的方式來學習這些經(jīng)驗，以應(yīng)對現(xiàn)在大規(guī)模增長的網(wǎng)絡(luò)流量.

近年來，隨著機器學習技術(shù)的興起，強化學習也被應(yīng)用到了自適應(yīng)路由算法的研究當中，其中具有代表性的是Q-routing［2］算法.它在網(wǎng)絡(luò)狀態(tài)動態(tài)變化(網(wǎng)絡(luò)負載變化、網(wǎng)絡(luò)拓撲變化)的情況下表現(xiàn)十分出色.基于Q-routing算法，研究人員陸續(xù)提出了很多改進算法.Littman等人［3］在節(jié)點進行路由決策前增加了輪詢操作，加快了節(jié)點與節(jié)點間的信息交換，從而降低了初始化階段峰值延遲，加速了算法的收斂.但頻繁的輪詢操作也引發(fā)了高負載狀態(tài)下延遲抖動的問題.Kumar等人［6］借鑒 Dual Reinforcement Learning［13］為 Q-routing 增加了反向探索的機制，大大提高了算法的收斂速度.Choi等人［7］針對負載降低時算法不能學習到新的最優(yōu)策略問題設(shè)計了一種具有記憶和恢復機制的Q-routing算法，它記錄學習過程中的最佳經(jīng)驗(下一跳選擇)，并間歇性預(yù)測流量趨勢以選擇恢復最佳經(jīng)驗.Hoceini等人［8］先依據(jù)路徑跳數(shù)選出前K條最短路徑，縮小Q-routing的決策空間后再進行路由決策，大大提高了算法的收斂速度和初始化階段的峰值延遲.

現(xiàn)有文獻主要對收斂速度和初始化階段峰值進行了深入研究，并形成了完善的算法體系結(jié)構(gòu)，但是忽略了高負載情況下的延遲抖動問題.但作為實時傳輸應(yīng)用的QoS指標，延遲抖動的重要性是不可忽略的.文獻［9］提出的AQFE方法通過調(diào)節(jié)輪詢學習率來消除抖動，但學習率受到調(diào)整后，出現(xiàn)了算法收斂速度下降和初始化階段延遲峰值上升等問題.

針對上述缺陷，本文提出了一種雙學習率自適應(yīng)的Q路由算法DALRQ-routing(Double Adaptive Learning Rate Q-routing).本文首先探索了AQFE算法的缺陷并據(jù)此改進了輪詢階段學習率自適應(yīng)的方法，減小了學習率調(diào)整對算法收斂速度和初始化階段峰值延遲的不利影響.然后，在轉(zhuǎn)發(fā)階段，我們基于TD-error設(shè)計了另一種學習率自適應(yīng)方法.通過雙學習率自適應(yīng)機制，算法達到了在保持高收斂速度和低初始化階段峰值延遲的基礎(chǔ)上減少延遲抖動的目標.

本文其余部分安排如下:第二部分介紹了強化學習在路由算法中的應(yīng)用;第三部分詳細描述了本文提出的雙學習率自適應(yīng)機制;第四部分給出了算法的具體描述;第五部分是仿真實驗和結(jié)果分析;第六部分進行了總結(jié).

2 相關(guān)工作

基于強化學習的路由算法

1)Q-routing

Q-routing算法(即Q路由算法)基于無模型的強化學習方法Q learning［5］.Q-routing以最小化端到端延遲為目標進行路由決策.它是一種分布式路由算法，網(wǎng)絡(luò)中每個節(jié)點都是agent，每個agent都基于本地信息進行路由決策.

Q-routing中，狀態(tài)s表示網(wǎng)絡(luò)中的一個目的地節(jié)點.動作a表示當前節(jié)點x為轉(zhuǎn)發(fā)數(shù)據(jù)包到目的地節(jié)點s選擇的下一跳節(jié)點.節(jié)點x會計算它每個狀態(tài)-動作對(s，a)，即目的地-下一跳鄰居節(jié)點對的Q值Qx(s，a)，并將所有Q值存入一張Q表中.Qx(s，a)表示從當前節(jié)點x出發(fā)，并以a節(jié)點作為下一跳節(jié)點傳輸數(shù)據(jù)包到目的地節(jié)點s的端到端延遲.每次x節(jié)點通過鄰居節(jié)點a轉(zhuǎn)發(fā)數(shù)據(jù)包到目的地節(jié)點s后都會更新對應(yīng)的Q值Qx(s，a)，更新公式如下:

Qx(s，a)=(1 － η)Qx(s，a)+ η·［r(s，a)+tas］ (1)其中，0≤η≤1是學習率，r(s，a)是x節(jié)點執(zhí)行轉(zhuǎn)發(fā)獲得的即時獎勵，計算公式如下:

公式(2)中qx表示節(jié)點x上的隊列延遲，dxa表示x節(jié)點與下一跳節(jié)點a之間的傳輸延遲.

公式(1)中的tax表示節(jié)點a與目的地節(jié)點s間的端到端延遲，其計算公式如下:

其中N(a)是節(jié)點a的鄰居節(jié)點的集合.

2)Full Echo Q-routing

Full Echo Q-routing算法［3］是 Q-routing的擴展算法.它在節(jié)點進行路由決策前執(zhí)行了輪詢操作(echo)，即當數(shù)據(jù)包到達節(jié)點x時，x首先通過獨立信道向所有鄰居節(jié)點發(fā)出輪詢請求，每個鄰居節(jié)點在收到請求后回復其至x節(jié)點的估計延遲t，x節(jié)點利用所有收到的t值更新其Q表.輪詢的操作加快了節(jié)點間信息的交換速度，因此大大提高了算法的收斂速度，降低了算法在初始化學習階段延遲峰值.

但輪詢操作在加速算法收斂的同時也引入了新的問題:高負載情況下算法十分不穩(wěn)定，即延遲抖動的問題.由于持續(xù)的輪詢操作，算法收斂后仍保持頻繁的信息交換，一旦拓撲中存在多條瓶頸鏈路，算法就會在幾條瓶頸鏈路的決策中不斷振蕩，極大的增加了算法的不穩(wěn)定性.

3 自適應(yīng)學習率機制

3.1 學習率背景

在機器學習中，監(jiān)督學習通過定義一個模型，并根據(jù)訓練集數(shù)據(jù)估計最優(yōu)參數(shù).梯度下降法(Gradient Decent)是一個廣泛被用來最小化模型誤差的參數(shù)優(yōu)化方法.梯度下降法通過多次迭代，并在每一步中最小化代價函數(shù)來估計模型的參數(shù)，參數(shù)更新規(guī)則如公式(4)所示:

其中wj是舊模型參數(shù)，是新模型參數(shù)，F(xiàn)是代價函數(shù)，F(xiàn)(wj)/wj是 wj的一階導數(shù)，η 是學習率.學習率 η(0≤η≤1)表示更新值的權(quán)重系數(shù)，即模型參數(shù)每次更新的步長.如果η偏大，前期有加速學習的作用，但后期迭代過程會振蕩以至發(fā)散;若η偏小，則模型參數(shù)的有效更新太小，收斂速度相當慢.因此在機器學習領(lǐng)域，學習率參數(shù)的調(diào)節(jié)一直是一個重要的研究課題.

與梯度下降法相似的是，強化學習的狀態(tài)動作值函數(shù)在更新過程中，也利用學習率控制值函數(shù)每次更新的步長，如公式(1)中的η.通常，若學習率η偏大，算法學習速度較快但不穩(wěn)定易發(fā)生抖動.反之若η偏小，算法收斂速度較慢但表現(xiàn)的很穩(wěn)定，因此在強化學習中學習率也是平衡學習速度和穩(wěn)定性的重要參數(shù).但在現(xiàn)有的基于強化學習的自適應(yīng)路由算法中，每個節(jié)點上的學習率η都是相同且固定的，鑒于學習率的重要性，我們參考機器學習中的學習率衰減理論［1，13，14］，針對Full Echo Q-routing算法設(shè)計了一種雙學習率自適應(yīng)機制DLRAM(Double Learning Rate Adaptive Method).我們將包轉(zhuǎn)發(fā)過程中的輪詢操作獨立為輪詢階段，其余部分作為轉(zhuǎn)發(fā)階段，即將算法的執(zhí)行過程分為輪詢階段和轉(zhuǎn)發(fā)階段.DLRAM 機制中每個節(jié)點擁有三種學習率η、ηt和ηe，其中η為基準學習率，ηt和ηe則根據(jù)節(jié)點的學習程度動態(tài)調(diào)節(jié).ηe用于輪詢(echo)階段Q函數(shù)的更新，ηt用于轉(zhuǎn)發(fā)(transfer)階段Q函數(shù)的更新.

3.2 雙學習率自適應(yīng)機制

輪詢階段，我們以降低輪詢操作帶來的延遲抖動為目的調(diào)整學習率.參照AQFE［9］算法，我們使用網(wǎng)絡(luò)延遲來描述節(jié)點的學習程度.若網(wǎng)絡(luò)延遲較高，表示節(jié)點的學習程度較低，此時應(yīng)增大ηe.若網(wǎng)絡(luò)延遲較低，代表節(jié)點的學習程度較高，通常意味著網(wǎng)絡(luò)性能越來越好，此時應(yīng)減小ηe的值.這種調(diào)節(jié)輪詢學習率的方式能夠減少輪詢操作帶來的延遲抖動.原AQFE方法中學習率ηe根據(jù)公式(5)進行調(diào)整:

其中Test是平均延遲的估計值，Tmax是平均延遲最大值的估計值，η是預(yù)設(shè)的基準學習率參數(shù)，k為預(yù)設(shè)參數(shù)(只能取接近0的值，例如0.01，否則算法沒有降低抖動的作用).

考慮到這是一個分布式路由算法，無法獲取全局的延遲信息，這里采用每個節(jié)點上的局部信息來估計平均延遲:

其中D是x節(jié)點可達的目的地節(jié)點的集合，nD是集合D的大小，Nx是x鄰居節(jié)點的集合.Tmax是當前節(jié)點上 Test中的最大值.

為探索AQFE算法出現(xiàn)收斂速度慢和峰值延遲上升等問題的原因，我們在高網(wǎng)絡(luò)負載情況下收集了AQFE算法與DALRQ-routing算法執(zhí)行過程中某結(jié)點上ηe學習率變化數(shù)據(jù)，并繪制成學習率隨時間變化的曲線，如圖1所示.其中直線Basicη為目前Q-routing算法及其變種常用的基準學習率，一般取固定值0.5.圖1中代表AQFE算法的ηe學習率曲線始終處在極低的水平，而學習率作為影響算法收斂速度的重要參數(shù)，初始化階段過低的學習率必然會導致算法收斂速度下降.此外，我們在高網(wǎng)絡(luò)負載情況下收集了AQFE算法在不同基準學習率η下的延遲值，并繪制了延遲隨時間變化的曲線，如圖2所示.不難發(fā)現(xiàn)，η越高，算法收斂速度越快，初始化階段的峰值延遲越低.綜合圖1和圖2，我們得出結(jié)論:初始化階段學習率過低導致了AQFE算法出現(xiàn)收斂速度下降和峰值延遲上升等問題.

圖1 AQFE算法與DALRQ-routing算法echo階段學習率的比較Fig.1 Comparison of echo learning rate between AQFE algorithm and DALRQ-routing algorithm

基于上述缺陷，我們將學習率ηe的更新公式修改如公式(7)所示:

在初始化階段的前期，延遲處于上升期，Test趨向于Tmax，因此都趨向于1，ηe始終保持在基準學習率η(η一般取0.5).即初始化階段學習率ηe較高，從而保證了算法較高的收斂速度和較低的峰值延遲.而隨著學習的進行，網(wǎng)絡(luò)延遲不斷下降，使得底數(shù)小于1，指數(shù)遠大于1，因此做到了ηe的快速下降，達到了我們降低延遲抖動的目的，圖1中DALRQ echo rate曲線就是公式(7)所代表的學習率變化曲線.但由于輪詢階段始終有ηe≤η，算法的收斂速度受其影響，仍出現(xiàn)了一定程度的下降.考慮到調(diào)整學習率有加速算法收斂的作用，下面為轉(zhuǎn)發(fā)階段增加調(diào)整學習率的機制來加速算法收斂.

圖2 不同η下AQFE算法平均延遲的比較Fig.2 Comparison of average delay of AQFE algorithm under differentη

由于輪詢階段輪詢操作密集，學習率偏大會引起延遲抖動，我們始終令ηe＜η.但在轉(zhuǎn)發(fā)階段不存在頻繁的輪詢操作，也就不需要刻意抑制學習率.轉(zhuǎn)發(fā)階段的學習率自適應(yīng)是僅以加快收斂速度為目標的，因此輪詢階段的學習率自適應(yīng)方法在轉(zhuǎn)發(fā)階段并不適用.考慮到Q-learning是一種時序差分方法，在每一步執(zhí)行后我們都可以計算出TD-error，它實時反應(yīng)了估計Q值和實際Q值的誤差.Q-learning中TD-error計算方法如公式(8)所示:

在初始學習階段，由于估計Q值并不準確，TD-error通常較大.隨著學習的進行，算法趨于收斂，TD-error趨向于0，因為這時估計Q值比較準確.在算法學習過程中，TD-error總是不斷變化的，可以基于TD-error值調(diào)增學習率以調(diào)整Q表更新速度，加快收斂.我們基于指數(shù)移動平均(EMA)方法定義了節(jié)點的學習的程度D，并使用這個學習程度D來調(diào)節(jié)學習率ηt.每個節(jié)點在s狀態(tài)(s即目的地節(jié)點)下的學習程度D(s)更新規(guī)則如公式(9)所示:

其中0≤ω≤1是權(quán)重系數(shù)，δ表示當前TD-error值，D(s)初始值為0.每個狀態(tài)下D(s)的最大值被存為Dmax(s).基于公式(9)計算出的結(jié)果，輪詢階段根據(jù)公式(10)調(diào)整學習率ηt.

算法在初始化階段，TD-error較大，因此學習率ηt較高，學習速度較快.隨著學習的進行，TD-error不斷減小，ηt也不斷衰減，最終算法收斂.

輪詢階段的學習率自適應(yīng)避免了輪詢操作導致的延遲抖動問題，同時降低了學習率調(diào)整對算法收斂速度和初始化延遲峰值的影響.轉(zhuǎn)發(fā)階段的學習率自適應(yīng)加速了算法的收斂.通過雙學習率自適應(yīng)機制，算法達到了在保持高收斂速度和低初始化階段峰值延遲的基礎(chǔ)上減少延遲抖動的目的.

4 雙學習率自適應(yīng)的Q路由算法

本文提出的雙學習率自適應(yīng)Q路由算法DALRQ-routing，根據(jù)網(wǎng)絡(luò)延遲和TD-error來調(diào)整節(jié)點的學習率以達到減少延遲抖動的目的.本算法采用了上一節(jié)提出的雙學習率自適應(yīng)機制DLRAM，兩種學習率分別用于輪詢階段和轉(zhuǎn)發(fā)階段.

算法描述

整個算法分為輪詢(Echo)和轉(zhuǎn)發(fā)(Transfer)兩個階段，算法啟動時初始化每個節(jié)點的Q表的所有項為0.當一個packet到達某個節(jié)點時，首先進入輪詢階段，節(jié)點通過獨立信道向所有鄰居節(jié)點發(fā)出請求，獲取該節(jié)點與每個鄰居節(jié)點間的延遲信息，然后利用所有鄰居節(jié)點反饋的延遲值更新本節(jié)點Q表.接下來進入轉(zhuǎn)發(fā)階段，節(jié)點查看Q表并選擇當前狀態(tài)s下Q值最低的鄰居節(jié)點作為下一跳選擇;隨后，節(jié)點執(zhí)行轉(zhuǎn)發(fā)操作，并存儲下一跳節(jié)點反饋的reward信息;下一步，更新轉(zhuǎn)發(fā)學習率ηt并利用此學習率更新本節(jié)點Q表;最后更新輪詢學習率ηe.具體如算法1所示.其中參數(shù)見表1.

表1 符號解釋Table 1 Symbolic interpretation

5 實驗與結(jié)果分析

為了驗證我們的路由算法能在保持高收斂速度和低初始化峰值延遲的基礎(chǔ)上，減少算法收斂后的延遲抖動，我們進行了仿真實驗.下面將介紹實驗環(huán)境，然后針對實驗結(jié)果進行分析.

我們在一臺配置為Intel Core i7 4790處理器，4核8線程，主頻為3.6GHz;GTX1080顯卡，顯存為16GB，顯存頻率為11100MHz;32GB RAM;256GB固態(tài)硬盤(SSD)的主機上運行Windows10系統(tǒng)，使用python語言進行編程.實驗中我們使用了一個基準網(wǎng)絡(luò)拓撲，如圖3所示.

該實驗拓撲為一個不規(guī)則網(wǎng)格網(wǎng)絡(luò)，由Boyan和Littman［2］在他們的實驗中首次使用，后作為基于強化學習的路由算法的基準實驗拓撲.圖3中的網(wǎng)絡(luò)由左右兩個網(wǎng)絡(luò)連接而成，鏈路20-21與鏈路32-33為瓶頸鏈路，易發(fā)生擁塞.本實驗中，位置上數(shù)據(jù)包的源節(jié)點和目的節(jié)點對的生成都是隨機的.時間上數(shù)據(jù)包的產(chǎn)生符合參數(shù)為λ的泊松分布，這個λ表示單位仿真時間內(nèi)網(wǎng)絡(luò)中產(chǎn)生數(shù)據(jù)包的數(shù)目，即網(wǎng)絡(luò)負載.例如，λ=1.0表示網(wǎng)絡(luò)中每個仿真時間隨機產(chǎn)生1個數(shù)據(jù)包，即低網(wǎng)絡(luò)負載情況，λ=3.0表示網(wǎng)絡(luò)中每個仿真時間產(chǎn)生3個數(shù)據(jù)包，這就是高網(wǎng)絡(luò)負載情況.每個節(jié)點上的數(shù)據(jù)包存儲在一個先進先出(FIFO)隊列中.在數(shù)據(jù)包達到一個節(jié)點后，節(jié)點會移除它隊列頭的數(shù)據(jù)包，檢查數(shù)據(jù)包的目的地，由本節(jié)點上路由決策agent選擇合適的鄰居節(jié)點執(zhí)行轉(zhuǎn)發(fā)任務(wù).當鄰居節(jié)點收到數(shù)據(jù)包后，若這個節(jié)點是是數(shù)據(jù)包的目的地節(jié)點，則移除網(wǎng)絡(luò)中的這個數(shù)據(jù)包.否則，將其添加到自己的隊列尾部.

圖3 基準網(wǎng)絡(luò)拓撲Fig.3 Network topology used as a benchmark

數(shù)據(jù)包延遲定義為數(shù)據(jù)包從源節(jié)點上產(chǎn)生到抵達目的地節(jié)點并移除所花費的時間.延遲以仿真時間為單位.平均數(shù)據(jù)包延遲按200仿真時間的時間間隔計算，是在這個時間間隔內(nèi)到達目的地節(jié)點的數(shù)據(jù)包延遲的平均值.我們利用延遲指標來評價路由算法的性能.

實驗中將本文提出的DALRQ-routing算法與Full Echo Q-routing算法和AQFE算法進行比較.在Full Echo Q-routing實驗過程中學習率η我們使用了原文的η=0.5.在AQFE實驗過程中學習率η我們使用了原文的η=0.7，為加快收斂過程，預(yù)設(shè)參數(shù)k取0.05.DALRQ-routing實驗過程中基準學習率η取值為0.5，輪詢階段學習率ηe按照公式(7)更新，包轉(zhuǎn)發(fā)階段學習率ηt按照公式(10)更新，公式(10)中權(quán)重系數(shù)ω取 0.2.

1)中低負載

圖4 中等網(wǎng)絡(luò)負載下算法平均延遲的比較(λ=2.5)Fig.4 Comparison of average delay under low and medium network load(λ =2.5)

圖4 表示網(wǎng)絡(luò)負載λ=2.5情況下的網(wǎng)絡(luò)延遲曲線.其中DALRQ-routing算法與Full Echo Q-routing算法表示的延遲曲線幾乎重合，說明兩者性能相近.AQFE算法在3400仿真時間后收斂，收斂速度遠慢于前兩者，且初始化階段(收斂前的階段)的峰值延遲極大.由于網(wǎng)絡(luò)負載較低，F(xiàn)ull Echo Q-routing算法收斂后并未出現(xiàn)明顯的延遲抖動.考慮到AQFE算法的峰值延遲過大，影響了我們對DALRQ-routing算法與Full Echo Q-routing算法收斂后抖動情況的觀察，圖4內(nèi)嵌的子圖為不包含AQFE算法的延遲曲線.從子圖不難看出，盡管在中低負載情況下Full Echo Q-routing算法收斂后只有輕微的延遲抖動，但DALRQ-routing算法仍然表現(xiàn)出了更好的穩(wěn)定性.

2)高負載

圖5和圖6分別表示網(wǎng)絡(luò)負載λ=3.0和λ=3.5情況下的網(wǎng)絡(luò)延遲曲線.其中圖5內(nèi)的子圖不包括AQFE算法的延遲曲線.從兩張圖中可以看出在高網(wǎng)絡(luò)負載情況下，F(xiàn)ull Echo Q-routing算法收斂后均出現(xiàn)了嚴重的延遲抖動抖動情況.對比圖5與圖6可以發(fā)現(xiàn)隨著網(wǎng)絡(luò)負載的增大，延遲抖動情況也越來越突出.但在同等網(wǎng)絡(luò)負載條件下DALRQ-routing算法仍能在保持高收斂速度和低初始化峰值延遲的基礎(chǔ)上減少延遲抖動，提高算法的平穩(wěn)性.

圖5 高網(wǎng)絡(luò)負載下算法平均延遲的比較(λ=3.0)Fig.5 Comparison of average delay under high network load(λ =3.0)

圖6 高負載下算法平均延遲的比較(λ=3.5)Fig.6 Comparison of average delay under high load(λ =3.5)

圖7 和圖8分別表示網(wǎng)絡(luò)負載λ=3.0和λ=3.5情況下的網(wǎng)絡(luò)延遲的分布情況，它收集了每種算法在15000仿真時間內(nèi)檢測到的延遲并將其繪制成每種算法延遲值的分布圖，橫向表示延遲區(qū)間，縱向表示每個延遲區(qū)間的延遲值對應(yīng)的頻數(shù)。其中最高的柱形對應(yīng)算法收斂時的延遲區(qū)間。兩幅圖中DALRQ-routing算法和AQFE算法代表的分布圖中柱形個數(shù)均較少，說明兩種算法的延遲值分布比較集中，算法收斂后的波動較小，而Full Echo Q_routing算法的分布圖中柱形較多，且圍繞著延遲最低的柱形(高度最高的柱形)，這說明了該算法最終收斂于一個低延遲值，但收斂后算法在低延遲值附近發(fā)生了劇烈的延遲抖動，以至于對應(yīng)延遲值的頻數(shù)不斷增加.

3)變化負載

圖7 高網(wǎng)絡(luò)負載下算法平均延遲分布(λ=3.0)Fig.7 Distribution of average delay under high network load(λ =3.0)

為直觀地衡量算法收斂后的延遲抖動情況，我們收集了三種算法在不同網(wǎng)絡(luò)負載下15000仿真時間內(nèi)收斂后的延遲值數(shù)據(jù)，將其刻畫為延遲均方差曲線，如圖9所示.圖中代表Full Echo Q_routing算法延遲均方差的曲線一直位于其他兩種算法的上方，并且當網(wǎng)絡(luò)處于高負載水平時，延遲均方差急劇上升，算法處于極不穩(wěn)定的狀態(tài).而DALRQ_Routing算法與AQFE算法在各種網(wǎng)絡(luò)負載條件下收斂后的延遲均方差都能維持在一個較低的水平，即算法收斂后十分平穩(wěn)，能明顯得減少延遲抖動.

圖8 高網(wǎng)絡(luò)負載下算法平均延遲的分布(λ=3.5)Fig.8 Distribution of average delay under high network load(λ =3.5)

圖9 各種網(wǎng)絡(luò)負載下的延遲均方差Fig.9 Delay standard deviation under various network loads

6 結(jié)束語

本文提出了一種自適應(yīng)學習率的Q路由算法DALRQ-routing，該算法的核心思想是在輪詢階段根據(jù)網(wǎng)絡(luò)延遲調(diào)整echo學習率，減少輪詢操作造成的延遲抖動.在轉(zhuǎn)發(fā)階段，根據(jù)TD-error調(diào)整transfer學習率，進一步提高算法的收斂速度.通過這種雙學習率自適應(yīng)的機制來降低延遲抖動，加速算法收斂.最后仿真結(jié)果表明，DALRQ-routing算法可以在保持高收斂速度和低初始化階段峰值延遲的基礎(chǔ)上減少延遲抖動，提高網(wǎng)絡(luò)穩(wěn)定性.