基于Q-learning 的分布式自適應拓撲穩定性算法

黃慶東，石斌宇，郭民鵬，袁潤芝，陳 晨

(西安郵電大學通信與信息工程學院信息與通信技術國家級實驗教學中心 西安 710121)

移 動 自 組 織 網 絡(mobile Ad hoc networks,MANET)是由移動節點組成復雜分布式系統。移動節點可以自由和動態地自組織成臨時網絡拓撲結構來傳輸每個節點收集到的信息。MANET 的特點是有限的存儲資源、處理能力以及高度移動性。在網絡中，移動節點可以動態地加入或離開網絡，導致了頻繁和難以預測的拓撲改變，加重了網絡任務的復雜程度，降低了網絡通信質量。由于網絡拓撲結構的不斷變化[1-2]，無線鏈路在高速移動環境中經常發生斷裂，如何保持通信鏈路的持續性成為一個巨大挑戰。因此，在臨時網絡拓撲結構信息交互過程中選擇穩定聯接鏈路節點進行傳輸對于鏈路聯接的持續性有重要意義。

為了增強網絡的性能因素，目前最有效方法是通過節點的移動特性來預測網絡中鏈路聯接的穩定性程度和網絡拓撲結構。文獻[3]提出了基于自適應神經模糊系統來預測節點的運動軌跡，根據預測得到的軌跡來選擇鏈路節點進行傳輸。文獻[1]通過收集節點的接收信號強度指示(received signal strength indication, RSSI)，將 其 進 行 深 度 學 習 訓練，預測節點的運動軌跡。文獻[4-5]通過深度學習或機器學習方法對節點的位置進行預測或進行鏈路質量預測來選擇最短可靠路徑進行信息傳輸。文獻[6]提出一種基于接收信號強度選擇穩定路徑的方法，根據一段時間內節點接收信號強度平均值將鏈路分為強聯接和弱聯接兩類，設定閾值選擇某一閾值內的鏈路進行路由傳輸。上述算法在研究方法上不盡相同，但都存在一定的局限性。現有的預測鏈路穩定性的算法中，大多都是僅考慮節點相對移動性，或僅采集節點某個時期的運動參數，而這些參數不能及時反映節點移動特性的變化，沒有考慮對鏈路穩定性的綜合影響。通常在預測節點的未來移動性時需大量的測量數據以及控制信息，這些因素會形成巨大開銷造成網絡擁塞，降低網絡性能。在預測過程中節點移動特性是假設不變的，然而在實際的網絡中這些情況都會實時變化，算法不能很好地自適應環境變化。因此，本文提出一種基于強化學習的分布式自適應拓撲穩定性方法，通過對網絡中各個鄰居節點接收信號強度值自適應學習，得到每個節點對未來鏈路穩定性和拓撲結構的判斷依據，提升網絡性能。

本文將接收信號強度與強化學習方法結合，每個分布式節點通過鄰居節點的信號強度值進行分布式強化學習，自適應劃分區間邊界分級處理，形成直接決策區間和自適應強化學習區間，對不同環境下節點的聯接狀態進行分級判斷以及實時更新學習。經過不斷學習每個節點得到最優聯接策略表，根據策略表中的值預測和判斷下一狀態的鄰居節點聯接情況，解決了綜合因素對鏈路穩定性的影響。

1 理論基礎及模型

1.1 鏈路穩定性概念

為了說明鏈路穩定性研究在移動自組織網絡中的重要性，通過圖1 所示場景進行簡要說明。從圖1 中可以觀察到，移動自組織網絡包含4 個節點A，B，C，D。節點A 需要向D 發送數據包，所以節點A 廣播路由請求分組并發現要發送數據包到D 必須經過節點B 或C。此時節點B 正迅速遠離A 和D 節點，而節點C 緩慢向A 移動。如果節點A 選擇B 作為轉發節點，由于B 的移動性，(A,B)鏈路不穩定，很容易斷開。由于C 是緩慢向A 節點移動，所以在傳輸的過程中(A, C)鏈路相比(A, B)將會有更長的時間保持良好穩定聯接。A 選擇C 作為下一跳傳輸節點轉發到D，更有助于信息的可靠網絡傳輸。通過上述場景可以看出，根據平均聯接有效時長選擇最穩定的路徑可以避免未來鏈路失效，從而改善路由。

由于每個節點具有移動性，作為最短路徑的一條鏈路可能在聯接建立之后迅速斷開。中斷的鏈路會導致路由服務質量下降。因此，在MANET 中節點之間構建相對穩定的拓撲聯接可以避免鏈路故障，很大程度上改善了網絡通信服務質量。

1.2 強化學習基本模型

強化學習算法是一類經典的在線機器學習算法，智能體根據環境狀態輸入，通過與環境交互得到反饋獎賞來選擇當前環境狀態的最佳動作[7]。強化學習系統主要包括5 個部分：環境、狀態s、動作a、 獎勵 r和智能體(Agent)。強化學習以“嘗試”的方式進行學習和強化，并形成好的動作策略。整個系統的框架如圖2 所示。

強化學習是由仿生學習、自動控制等理論發展而來，其基本原理是：如果Agent 的某個行為策略導致環境正的獎勵(強化信號)，則此行為策略便會加強，反之減弱。Agent 的目標是在每個離散狀態學習最優策略使期望獎賞最大化。

強化學習中Q-learning 算法由于其較好的算法性能，被廣泛研究和使用。其狀態集 S由集合{s1,s2,···,si,···} 組成，動作集 A由 {a1,a2,···,aj,···}組成。不同狀態動作對 (si, aj)對 應Q 值矩陣i 行 j列的元素，狀態動作集對應的Q 值可表示為Q 值矩陣。分布式強化學習時，每個節點獨立訓練學習，并保持一個Q 值矩陣不斷學習更新。定義評估函數 值 Qt(si,aj)為 Agent 在 t時 刻 狀 態 si下 選 取 動 作aj計算獲得的Q 值，其中 si∈ S ， aj∈A ，并且在下一狀態選取最優動作的折扣獎勵累積值。在Qlearning 算法不斷的學習過程中，每個網絡節點的Agent 通過遞歸的方式不斷更新該節點Q 值，以獲得最大的長期累積獎勵，最終可以得到預期目標下此節點的最佳學習策略。各個節點的Q 值更新函數為[7]：

式中， α為學習率， 0< α<1； γ為獎勵折扣因子，0<γ<1； aj為當前動作，為策略在狀態上對應的最大Q 值動作； si為當前狀態；為 si執行動作aj后轉移到的狀態；為在狀態 si下執行動作aj后轉移到狀態得到的獎勵值；表示狀態下所有狀態動作對中最大Q 值，代表當前策略取得的新狀態最好預期值對當前策略Q 值計算的影響。

強化學習應用到MANET 中，多數情況下是解決動態情況下找尋最短路徑的問題和解決QoS 問題[8-10]。本文在強化學習的基礎上結合移動自組織網絡中節點之間信息交互時攜帶的RSSI 值，提出了自適應拓撲穩定性算法尋找穩定鏈路聯接。

2 基于Q-learning 的分布式自適應拓撲穩定性算法

基于Q-learning 的分布式自適應拓撲穩定性算法是由強化學習Q-learning 算法與自適應區間更新算法兩種方法結合產生一種預測周圍移動鄰居節點拓撲穩定聯接的算法。該方法利用強化學習思想建立模型，通過實時處理當前節點接收到的鄰居節點RSSI 值進行強化學習，并對此鄰居節點的鏈路聯接狀態進行預測，每個節點都維護一張狀態Q 值矩陣表以及一個自適應學習區間，根據RSSI值來分區間判斷當前鏈路質量，算法的結構框圖如圖3 所示。

圖3中，如果當前節點接收到某個鄰居節點RSSI 值處于自適應區間 [a,b]內，則執行Q-learning算法進行聯接狀態預測；若處于自適應區間外，則執行聯接狀態直接決策。自適應區間 [a,b]的邊界依據直接決策失誤情況進行上、下邊界的區間擴展調節。通過兩種方法的結合可以提高判決效率，提升算法判決精度，從而使預測模型更加高效、快速適應環境的變化做出準確狀態判斷。

2.1 自適應區間更新算法結構

自適應區間更新算法服務于Q-learning 算法，為其提供更適合的強化學習區間范圍。本文假設節點發射功率為0 dBm，考慮環境等因素影響，節點間穩定聯接臨界強度值為?77 dBm。初始化區間[a,b]中 上界 a與 下界 b的值都等于?77 dBm，這樣形成3 個 區 間 [0, a)、 [a, b]、 (b, ?∞)。 區 間 [a, b]為Qlearning 算法學習區間，進行強化學習決策；區間外 [0,a)、 (b, ?∞)進行狀態的直接決策。隨著算法執行，區間 [a,b]的值不斷更新，進行區間擴展。自適應區間更新及決策算法流程如下：

1) 設定初始的閾值 dwin=?77 dBm，節點根據當前采集到某鄰居節點的RSSI，當大于閾值判定為穩定聯接狀態 s1，小于閾值判定為非穩定聯接狀態 s2。 狀態變量 s表示節點與鄰居節點的聯接狀態，表示為：

2) 當前節點根據其鄰居節點的RSSI，按照式(2)進行狀態判定，作為下一時刻節點與此鄰居節點聯接狀態的預測s?；假設下一時刻信號強度為RSSI′，又根據式(2)判定下一時刻實際聯接狀態為s′， 若，則根據情況調整區間 [a,b]，初始狀態a=b=?77 dBm。按照流程1)判定出錯時，若a RSSI，則 調 整b=RSSI。直接決策調整邊界公式表示為：

3) 直接決策：按照式(2)進行狀態直接決策，在直接決策區間 [0,a)內 ，直接判決為 s1狀態；在直接決策區間 (b, ?∞)內 ，直接判決為 s2狀態。

4) 節點根據每一鄰居節點前后時刻接收信號強度值，按照式(2)進行決策區間邊界調整；按照流程3)進行直接決策區間的狀態判定；而對于直接決策區間外的自適應區間 [a,b]，按照Q-learning 算法進行強化學習和狀態決策，并對Q 值矩陣進行持續更新。

5) 不同時刻，節點按照流程2)～流程4)鄰居節點接收信號強度進行邊界循環更新和狀態決策。

該算法可以異步分布式執行，網絡中各個節點獨立按照上述算法進行自主學習決策。每個節點對其各鄰居節點進行聯接狀態穩定關系判定，最終由穩定聯接狀態的鄰居節點構成此節點的穩定鄰居集。由相互穩定聯接的節點形成移動無線自組織網絡的穩態拓撲。

2.2 Q-learning 算法結構

基于Q-learning 的分布式自適應拓撲穩定性算法中，每一個移動節點可以視為一個Agent，這樣整個網絡的動態變化都可認為是一個分布式多Agent 協作系統。對于每個Agent，假設其環境狀態集為S ，動作集為A， 獎賞函數為，動作選擇策略為 π(si,aj)。根據Q-learning 算法基本結構描述如下：

1) 狀態集S ：由離散的狀態構成。狀態定義為：

式中， s1狀態為根據當前接收到某鄰居節點RSSI，節點與某鄰居節點處于穩定聯接狀態； s2狀態為根據當前接收到某鄰居節點RSSI，與某鄰居節點處于非穩定聯接狀態。

2) 動作集 A：每個Agent 可以采取的動作分為預判穩定聯接狀態和預判非穩定聯接狀態兩個類型。動作集定義為：

式中， a1為 預判穩定狀態； a2為預判非穩定狀態。

表1 獎勵函數值表

根據表1 分析，可以得到獎賞函數定義式：

4) 動作選擇策略 π(si,aj)：Q-learning 算法的策略選擇決定了Agent 怎樣去平衡探索和開發之間的問題。Agent 通過探索可以持續學習發現更優的策略；通過開發選擇轉向期望狀態最佳動作。本文算法選擇 ε?貪心策略來確定最優動作，每次選擇Q 值最大的動作。即：

5) 更新Q 值函數：綜合動作、獎勵值的設計，根據式(1)的方法進行函數的更新。

3 仿真與結果分析

為了驗證算法有效性和穩定性，通過Python仿真環境設計了3 組實驗來研究本文所提出算法的性能。為了能夠更加真實地建立MANET 中節點運動的隨機性以及各個節點之間速度以及運動方向的隨機性模型，在仿真場景的設計中采用了MANET中經典的運動模型—隨機游走移動模型[11](random walk mobility model, RWM)來驗證本文算法性能。

實驗設定在150×150 m2的網絡區域內生成移動節點，每個移動節點選擇隨機的方向運動、隨機的運動時間、隨機的停頓時間，實驗中設定節點數目為15 個且每個節點之間的運動互不影響。表2所示為仿真實驗的系統參數。

表2 實驗參數設置

根據上述的仿真參數設定，將本文算法應用到RWM 移動模型中進行算法的有效性測試。仿真中設定RSSI 的測量模型為自由空間傳播模型[12]，計算公式如下：

式中，Loss 是傳播損耗，單位為dB，與傳輸路徑有關；d 是距離，單位為km，f是工作頻率，單位為MHz。假設各個節點發射信號為窄帶信號，工作頻率為2 400 MHz，并且發射功率為0 dBm 時，可以得到 RS SI=?Loss，根據節點的最大通信距離d=0.07時 計算得到RSSI 值為 ?7 7 dBm。考慮電磁波在空氣中的損耗，設定了可以穩定聯接的臨界值為 ?7 7 dBm。

在算法開始執行前，設定初始的學習迭代次數為200 輪、通過學習200 輪之后得到策略表以及強化學習區間，對測試數據進行100 輪預測來計算準確率，將100 輪預測的聯接狀態結果與節點在實際移動過程中各個節點聯接狀態進行統計平均，計算出每個節點在100 輪預測過程中的準確率。

圖5 為仿真環境都相同的情況下，分別設定不同學習率α 為0.1、0.5、0.7 的準確率值對比圖。

根據圖5 中不同學習率 α對準確率的影響曲線分析可知，當學習率 α的取值為0.1 時所有節點的準確率值均維持在95%左右，并且各個節點之間的預測準確率變化值相差不大，整個曲線變化比較平緩；而在學習率 α取值為0.5 或0.7 時準確率比0.1 時均有所下降，并且各個節點的預測準確率相差變大，曲線的變化程度較明顯。出現該現象是由于在執行本文算法進行預測的過程中，節點主要根據鄰居節點過去運動經驗來判斷下一傳輸時刻聯接的狀態程度，如果學習率 α增大將增大Agent 的探索過程則對節點的運動經驗的取值變小，從而導致節點的預測錯誤的幾率增加。但是在不同學習率α的影響下準確率維持在0.8～0.95，從而證明算法的穩定性。因此，在接下來的實驗過程中均選取學習率α 為0.1 作為本文算法中的參數。

為了證明算法的有效性，通過在RWM 模型中分別應用本文提出的基于Q-learning 的分布式自適應拓撲穩定性算法與通過強化學習算法直接得到策略表來判斷穩定聯接次數比較。實驗設定兩次仿真環境均相同的情況下，分別統計測試數據100 輪中每個節點預測聯接狀態的準確次數率。

根據圖6 所示，本文提出的基于Q-learning的分布式自適應拓撲穩定性算法的準確率比單獨使用Q 學習算法的準確率整體提高了30%左右，故本文算法在預測的準確率方面明顯優于單獨使用Q 學習算法，其原因是各個Agent 通過自適應的強化學習區間的不斷更新將每次的學習變化范圍擴大，自適應區間外直接判斷聯接狀態，自適應區間內隨著不斷的強化學習經驗的積累做出更加精確地預測，提升算法的性能。兩種算法的比較也說明本文算法的有效性。

圖7 為通過隨機的抽取某一輪預測過程中單個節點預測得到的網絡拓撲聯接關系，與圖8 的節點在實際運動過程中的真實聯接關系進行比較。實驗仿真環境與上述兩個實驗相同，仿真中實際聯接穩定的閾值設定為 dwin=?77 dBm，根據設定閾值判斷穩定聯接鄰居節集。

根據圖7 中處于1 號節點通信范圍內的節點集合為{4,9,10,13,15}，在預測穩定拓撲聯接過程中，生成的聯接關系集合為{4,10,13,15}，預測出9 號節點不能在下一傳輸時刻穩定聯接。通過預測拓撲聯接關系與圖8 真實拓撲聯接關系比較表明，預測結果與真實聯接關系相一致。強化學習的過程中每個Agent 都會對其他節點的運動特性有累積性的學習，不會因為節點處于通信范圍內判斷為穩定聯接鏈路，Agent 會根據節點當前的運動狀態以及策略表中學習得到的經驗來有效避免在短時間內可能會快速斷開的鏈路聯接，所以9 號節點在預測過程中被判斷非穩定聯接狀態。

4 結 束 語

本文通過研究MANET 中移動節點對網絡拓撲影響，提出了基于強化學習的分布式自適應算法。算法中每個節點通過對其他節點運動特性學習得到下一傳輸時刻穩定聯接的鄰居集合，通過穩定聯接集合預測移動節點之間網絡拓撲的穩定聯接關系，可以更好地適應網絡拓撲變化。MANET 中穩定的拓撲聯接關系很大程度上改善了路由選擇，同時也提高了網絡通信服務質量。實驗結果表明，基于Q-learning 的分布式自適應拓撲穩定性算法高效穩定且準確度高，能夠有效地實現網絡拓撲聯接的穩定性選擇。