雙學習率自適應的Q路由算法

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

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

1 引言

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

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

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

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

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

2 相關工作

基于強化學習的路由算法

1)Q-routing

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

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

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

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

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

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

2)Full Echo Q-routing

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

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

3 自適應學習率機制

3.1 學習率背景

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

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

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

3.2 雙學習率自適應機制

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

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

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

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

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

圖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較高，從而保證了算法較高的收斂速度和較低的峰值延遲.而隨著學習的進行，網絡延遲不斷下降，使得底數小于1，指數遠大于1，因此做到了ηe的快速下降，達到了我們降低延遲抖動的目的，圖1中DALRQ echo rate曲線就是公式(7)所代表的學習率變化曲線.但由于輪詢階段始終有ηe≤η，算法的收斂速度受其影響，仍出現了一定程度的下降.考慮到調整學習率有加速算法收斂的作用，下面為轉發階段增加調整學習率的機制來加速算法收斂.

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

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

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

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

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

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

4 雙學習率自適應的Q路由算法

本文提出的雙學習率自適應Q路由算法DALRQ-routing，根據網絡延遲和TD-error來調整節點的學習率以達到減少延遲抖動的目的.本算法采用了上一節提出的雙學習率自適應機制DLRAM，兩種學習率分別用于輪詢階段和轉發階段.

算法描述

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

表1 符號解釋Table 1 Symbolic interpretation

5 實驗與結果分析

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

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

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

圖3 基準網絡拓撲Fig.3 Network topology used as a benchmark

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

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

1)中低負載

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

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

2)高負載

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

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

3)變化負載

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

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

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

圖9 各種網絡負載下的延遲均方差Fig.9 Delay standard deviation under various network loads

6 結束語

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