基于Q學習的Ad Hoc網絡路由協議的改進與研究?

劉 芬 隋天宇 王葉群

（1.西南通信研究所 成都 610041）（2.空軍工程大學 西安 710038）

1 引言

移動Ad-Hoc網絡是一種節點可以自由移動通信的無線網絡，建網形式比較靈活多變，網絡配置也比較方便，成本低廉［1］。由于Ad-Hoc網絡自身特點和外界條件的約束，要求路由協議具有較好的自適應性、穩定性和確保通信質量。

現有的Ad-Hoc網絡路由協議從路由探索的角度可分為表驅動型和按需型兩大類。表驅動型路由協議主要有OLSR、FSR、DSDV等，按需型路由協議主要有DSR、AODV、TORA等，本文以AODV協議的思想為例進行改進和探索。文獻［2］提出的一種將Q學習方法依靠鄰近節點提供的局部網絡信息進行迭代并更新的動態算法。文獻［3］根據Q值的變化調整路由生存時間和hello包的發送周期，以便減小網絡的路由控制開銷。文獻［4］提出了一種高效節能的多路徑傳輸的辦法提高端到端的鏈路可靠性，本文擬融合Q算法應用在延長生命期的同時采用備用路徑的想法平衡網絡負載從而提高網絡性能［5］。

2 Q學習的多路徑路由協議

2.1 多徑路由建立過程

源節點廣播RREQ分組開始路由尋找過程，最短路徑上的中間節點維護多條和其他路徑沒有交點的路徑，這條路徑稱之為備用路徑［6］，具體操作是在分組發送過程中，將節點消耗能量消耗過大的路徑進行分流和權衡，采用備用路徑進行數據包的分流或者通信。文獻［7～8］中表明多徑并行傳輸路徑可用帶寬對吞吐量的影響比較大，利用Q學習算法提高帶寬的利用率。

2.2 Q學習路由協議框架建構

Q學習方法是強化學習中采用逐步迭代的方式逼近最優解的方法，目標是達到需要的狀態并獲取最高收益［9］。

文獻［10］提供了一種Q學習算法在車載Ad Hoc網絡中的應用，啟發式Q學習算法可以解決文獻中算法收斂過慢的問題。

基于路由協議建立的Q值更新公式如式（1）所示［11］：

其中，Qs( )d,x表示節點s選擇鄰居節點x作為下一跳節點，將分組轉發到目的節點d的Q值，Γ(x)表示節點x的鄰居集合，α為學習率，R為獎勵值，若鄰居節點x恰好是目的節點d，那么R=1，否則R=0，γx為動態折扣率。

步驟1 源節點廣播RREQ分組：

源節點需要向目的節點發送數據包，發起路徑尋找，向網絡中廣播RREQ分組，并記錄下本次的發送時間。

步驟2 中繼節點轉發RREQ包：

由中間節點進行轉發，整個過程中要加入一個時延避免擁塞，若找到目的節點，則直接回復RREP分組，并記錄轉發時間，盡可能多地尋找可用路徑。

步驟3 更新網絡的路由信息：

當RREP分組傳播到源節點的時候，更新路由表信息。

步驟4 計算并啟發最優下一個節點［12］：

在路徑尋找過程中，將最小的時延作為反饋信息沿對應路徑原路返回源節點，計算到達目的節點的總時延，如式（2）所示。

Delay( s,d,x)表示從源節點s，經過的下一跳節點為x，將分組傳輸到目的節點d的時延。時延最短，路徑最優，用a*表示。

定義啟發函數Hs( d,x)，從而啟發當前節點選擇當前最優下一節點，并更新相應的Q值。定義，如式（3）所示。

其中，Qs(d,x)表示s通過下一跳節點x到達目的節點d的Q值，y∈mΓ(asx)Qs(d,y)表示點s的所有鄰居節點中到達目的節點的最高Q值。η是一個很小的正實數，取值0.01。

步驟5 源節點根據Q學習路由更新網絡的路由生存期：

Q學習算法根據時延估計值評估當前的網絡路徑來設置路徑的生存壽命，用Qs描述網絡的穩定性，用Quns描述網絡的不穩定性，根據歸一化的端到端時延估計值γ更新網絡值，如式（4）所示。

其中t代表當前時刻。

整個過程中根據圖1的流程進行路由壽命的增加或者減少。

圖1 路由壽命更新

步驟6 路由維護：

由于本文的改進協議是按需型協議，考慮業務量和負載超量的情況或者備用路徑無法使用的情況，原鏈路中斷的情況，當前節點發送一個分組，內容有擁塞節點的地址以及隊列長度，方便備用路徑的節點解決處理擁塞問題。為了保證通信更好地進行，引入Q學習的目標函數G［13］：為

式 一（5跳）中平均L f時為延當，前T估r是計 丟得系 包統后的等平待均重丟傳包的率時，間。節點根據自己的情況進行學習，G表現了網絡當前狀態的趨勢，G越小，網絡回報越好。

2.3 路由協議性能指標體系

為了分析路由協議性能的好壞，可以通過一些指標來直觀地描述出一種路由協議的優劣。常見的性能指標如下：吞吐量為單位時間內傳送的數據量，越大越好；路由建立開銷越小越好；平均端到端時延就是所有成功傳送分組時延的平均數［14］，時延越小越好；目的節點應用層所丟棄的分組數目與源節點應用層所發送的分組數目的比值是分組丟棄率。

3 路由協議實驗結果分析

本文使用NS3通過對網絡整體吞吐量、分組丟包概率、端到端的平均時延、路由建立開銷［15］等參數的性能進行計算機仿真，具體的網絡環境如表1所示。

表1 仿真參數配置

為了討論路由生存時間對路由協議性能的影響，使用優化后的路由協議，仿真的網絡環境設置與表1相同，發包速率選取每秒6個包和10個包，節點移動速率為10m/s。

圖2 路由生存周期與路由協議指標關系圖

總的來說，圖2表明隨著路由生存周期的延長，網絡的端到端時延和吞吐量變化趨勢不是特別明朗，在路由壽命為5s的情況下，端到端的平均時延最小，11s之后整體平均時延呈下降趨勢；在路由壽命為5s時，吞吐量最大，11s之后，吞吐量是上升趨勢。

選取初始路由生存周期為5s，參數發包速率為10個/s進行之后的仿真。在不同的節點移動速度下，網絡中的分組丟棄概率如圖3（a）所示，多路徑協議能夠有效地改善分組丟棄情況，但是隨著節點移動速度的增加，網絡拓撲結構的多變，分組丟棄的概率變大。

節點移動速率與端到端的平均時延的關系如圖3（b）所示，節點的移動速度越來越快，網絡拓撲隨之變化，路由的鏈路存在因為更新速率加快，尋找的頻率增加，優化之后的協議縮短了分組的傳送距離，提高了建立路徑的概率。

圖3 節點移動速率與路由協議性能關系圖

節點的移動速率與吞吐量的關系如圖3（c）所示，相比于傳統的AODV協議來說，多條路徑發送的原理雖然能避免碰撞和浪費等問題，但是降低了信道的利用率，導致吞吐量下降，分組丟棄概率的降低補償了吞吐量，移動速率差距大，補償效果越好。

節點移動速率與路由建立開銷之間的關系如圖3（d）所示，路由生存時間越大，路由尋找過程的頻率就會越低，路由開銷就越低，Q學習通過提高網絡的穩定性，增加端到端的可靠性，降低開銷。

4 結語

在網絡需求和網絡流量日益增長的今天，對路由的智能性要求也提高了，本文在按需AODV協議的思想基礎上，將啟發式Q學習算法應用在路徑尋找和路徑選擇的過程中，傳統Q學習算法應用在路由壽命調整中，詳細描述了整個路由操作的過程，備用路徑則是在發生網絡拓撲變化，原網絡鏈路等情況下，進行臨時通信作用，改進后的路由協議優化了網絡性能，降低路由控制開銷，避免了持續性的網絡擁塞，然后使用NS3網絡對相關的路由協議參數進行了仿真，直接驗證了備用路徑思想和Q學習方法在路由協議運行過程中的優勢。