基于Q-learning 的分布式自適應(yīng)拓?fù)浞€(wěn)定性算法

黃慶東，石斌宇，郭民鵬，袁潤(rùn)芝，陳 晨

(西安郵電大學(xué)通信與信息工程學(xué)院信息與通信技術(shù)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)中心 西安 710121)

移 動(dòng) 自 組 織 網(wǎng) 絡(luò)(mobile Ad hoc networks,MANET)是由移動(dòng)節(jié)點(diǎn)組成復(fù)雜分布式系統(tǒng)。移動(dòng)節(jié)點(diǎn)可以自由和動(dòng)態(tài)地自組織成臨時(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來傳輸每個(gè)節(jié)點(diǎn)收集到的信息。MANET 的特點(diǎn)是有限的存儲(chǔ)資源、處理能力以及高度移動(dòng)性。在網(wǎng)絡(luò)中，移動(dòng)節(jié)點(diǎn)可以動(dòng)態(tài)地加入或離開網(wǎng)絡(luò)，導(dǎo)致了頻繁和難以預(yù)測(cè)的拓?fù)涓淖?，加重了網(wǎng)絡(luò)任務(wù)的復(fù)雜程度，降低了網(wǎng)絡(luò)通信質(zhì)量。由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不斷變化[1-2]，無線鏈路在高速移動(dòng)環(huán)境中經(jīng)常發(fā)生斷裂，如何保持通信鏈路的持續(xù)性成為一個(gè)巨大挑戰(zhàn)。因此，在臨時(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息交互過程中選擇穩(wěn)定聯(lián)接鏈路節(jié)點(diǎn)進(jìn)行傳輸對(duì)于鏈路聯(lián)接的持續(xù)性有重要意義。

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

本文將接收信號(hào)強(qiáng)度與強(qiáng)化學(xué)習(xí)方法結(jié)合，每個(gè)分布式節(jié)點(diǎn)通過鄰居節(jié)點(diǎn)的信號(hào)強(qiáng)度值進(jìn)行分布式強(qiáng)化學(xué)習(xí)，自適應(yīng)劃分區(qū)間邊界分級(jí)處理，形成直接決策區(qū)間和自適應(yīng)強(qiáng)化學(xué)習(xí)區(qū)間，對(duì)不同環(huán)境下節(jié)點(diǎn)的聯(lián)接狀態(tài)進(jìn)行分級(jí)判斷以及實(shí)時(shí)更新學(xué)習(xí)。經(jīng)過不斷學(xué)習(xí)每個(gè)節(jié)點(diǎn)得到最優(yōu)聯(lián)接策略表，根據(jù)策略表中的值預(yù)測(cè)和判斷下一狀態(tài)的鄰居節(jié)點(diǎn)聯(lián)接情況，解決了綜合因素對(duì)鏈路穩(wěn)定性的影響。

1 理論基礎(chǔ)及模型

1.1 鏈路穩(wěn)定性概念

為了說明鏈路穩(wěn)定性研究在移動(dòng)自組織網(wǎng)絡(luò)中的重要性，通過圖1 所示場(chǎng)景進(jìn)行簡(jiǎn)要說明。從圖1 中可以觀察到，移動(dòng)自組織網(wǎng)絡(luò)包含4 個(gè)節(jié)點(diǎn)A，B，C，D。節(jié)點(diǎn)A 需要向D 發(fā)送數(shù)據(jù)包，所以節(jié)點(diǎn)A 廣播路由請(qǐng)求分組并發(fā)現(xiàn)要發(fā)送數(shù)據(jù)包到D 必須經(jīng)過節(jié)點(diǎn)B 或C。此時(shí)節(jié)點(diǎn)B 正迅速遠(yuǎn)離A 和D 節(jié)點(diǎn)，而節(jié)點(diǎn)C 緩慢向A 移動(dòng)。如果節(jié)點(diǎn)A 選擇B 作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，由于B 的移動(dòng)性，(A,B)鏈路不穩(wěn)定，很容易斷開。由于C 是緩慢向A 節(jié)點(diǎn)移動(dòng)，所以在傳輸?shù)倪^程中(A, C)鏈路相比(A, B)將會(huì)有更長(zhǎng)的時(shí)間保持良好穩(wěn)定聯(lián)接。A 選擇C 作為下一跳傳輸節(jié)點(diǎn)轉(zhuǎn)發(fā)到D，更有助于信息的可靠網(wǎng)絡(luò)傳輸。通過上述場(chǎng)景可以看出，根據(jù)平均聯(lián)接有效時(shí)長(zhǎng)選擇最穩(wěn)定的路徑可以避免未來鏈路失效，從而改善路由。

由于每個(gè)節(jié)點(diǎn)具有移動(dòng)性，作為最短路徑的一條鏈路可能在聯(lián)接建立之后迅速斷開。中斷的鏈路會(huì)導(dǎo)致路由服務(wù)質(zhì)量下降。因此，在MANET 中節(jié)點(diǎn)之間構(gòu)建相對(duì)穩(wěn)定的拓?fù)渎?lián)接可以避免鏈路故障，很大程度上改善了網(wǎng)絡(luò)通信服務(wù)質(zhì)量。

1.2 強(qiáng)化學(xué)習(xí)基本模型

強(qiáng)化學(xué)習(xí)算法是一類經(jīng)典的在線機(jī)器學(xué)習(xí)算法，智能體根據(jù)環(huán)境狀態(tài)輸入，通過與環(huán)境交互得到反饋獎(jiǎng)賞來選擇當(dāng)前環(huán)境狀態(tài)的最佳動(dòng)作[7]。強(qiáng)化學(xué)習(xí)系統(tǒng)主要包括5 個(gè)部分：環(huán)境、狀態(tài)s、動(dòng)作a、 獎(jiǎng)勵(lì) r和智能體(Agent)。強(qiáng)化學(xué)習(xí)以“嘗試”的方式進(jìn)行學(xué)習(xí)和強(qiáng)化，并形成好的動(dòng)作策略。整個(gè)系統(tǒng)的框架如圖2 所示。

強(qiáng)化學(xué)習(xí)是由仿生學(xué)習(xí)、自動(dòng)控制等理論發(fā)展而來，其基本原理是：如果Agent 的某個(gè)行為策略導(dǎo)致環(huán)境正的獎(jiǎng)勵(lì)(強(qiáng)化信號(hào))，則此行為策略便會(huì)加強(qiáng)，反之減弱。Agent 的目標(biāo)是在每個(gè)離散狀態(tài)學(xué)習(xí)最優(yōu)策略使期望獎(jiǎng)賞最大化。

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

式中， α為學(xué)習(xí)率， 0< α<1； γ為獎(jiǎng)勵(lì)折扣因子，0<γ<1； aj為當(dāng)前動(dòng)作，為策略在狀態(tài)上對(duì)應(yīng)的最大Q 值動(dòng)作； si為當(dāng)前狀態(tài)；為 si執(zhí)行動(dòng)作aj后轉(zhuǎn)移到的狀態(tài)；為在狀態(tài) si下執(zhí)行動(dòng)作aj后轉(zhuǎn)移到狀態(tài)得到的獎(jiǎng)勵(lì)值；表示狀態(tài)下所有狀態(tài)動(dòng)作對(duì)中最大Q 值，代表當(dāng)前策略取得的新狀態(tài)最好預(yù)期值對(duì)當(dāng)前策略Q 值計(jì)算的影響。

強(qiáng)化學(xué)習(xí)應(yīng)用到MANET 中，多數(shù)情況下是解決動(dòng)態(tài)情況下找尋最短路徑的問題和解決QoS 問題[8-10]。本文在強(qiáng)化學(xué)習(xí)的基礎(chǔ)上結(jié)合移動(dòng)自組織網(wǎng)絡(luò)中節(jié)點(diǎn)之間信息交互時(shí)攜帶的RSSI 值，提出了自適應(yīng)拓?fù)浞€(wěn)定性算法尋找穩(wěn)定鏈路聯(lián)接。

2 基于Q-learning 的分布式自適應(yīng)拓?fù)浞€(wěn)定性算法

基于Q-learning 的分布式自適應(yīng)拓?fù)浞€(wěn)定性算法是由強(qiáng)化學(xué)習(xí)Q-learning 算法與自適應(yīng)區(qū)間更新算法兩種方法結(jié)合產(chǎn)生一種預(yù)測(cè)周圍移動(dòng)鄰居節(jié)點(diǎn)拓?fù)浞€(wěn)定聯(lián)接的算法。該方法利用強(qiáng)化學(xué)習(xí)思想建立模型，通過實(shí)時(shí)處理當(dāng)前節(jié)點(diǎn)接收到的鄰居節(jié)點(diǎn)RSSI 值進(jìn)行強(qiáng)化學(xué)習(xí)，并對(duì)此鄰居節(jié)點(diǎn)的鏈路聯(lián)接狀態(tài)進(jìn)行預(yù)測(cè)，每個(gè)節(jié)點(diǎn)都維護(hù)一張狀態(tài)Q 值矩陣表以及一個(gè)自適應(yīng)學(xué)習(xí)區(qū)間，根據(jù)RSSI值來分區(qū)間判斷當(dāng)前鏈路質(zhì)量，算法的結(jié)構(gòu)框圖如圖3 所示。

圖3中，如果當(dāng)前節(jié)點(diǎn)接收到某個(gè)鄰居節(jié)點(diǎn)RSSI 值處于自適應(yīng)區(qū)間 [a,b]內(nèi)，則執(zhí)行Q-learning算法進(jìn)行聯(lián)接狀態(tài)預(yù)測(cè)；若處于自適應(yīng)區(qū)間外，則執(zhí)行聯(lián)接狀態(tài)直接決策。自適應(yīng)區(qū)間 [a,b]的邊界依據(jù)直接決策失誤情況進(jìn)行上、下邊界的區(qū)間擴(kuò)展調(diào)節(jié)。通過兩種方法的結(jié)合可以提高判決效率，提升算法判決精度，從而使預(yù)測(cè)模型更加高效、快速適應(yīng)環(huán)境的變化做出準(zhǔn)確狀態(tài)判斷。

2.1 自適應(yīng)區(qū)間更新算法結(jié)構(gòu)

自適應(yīng)區(qū)間更新算法服務(wù)于Q-learning 算法，為其提供更適合的強(qiáng)化學(xué)習(xí)區(qū)間范圍。本文假設(shè)節(jié)點(diǎn)發(fā)射功率為0 dBm，考慮環(huán)境等因素影響，節(jié)點(diǎn)間穩(wěn)定聯(lián)接臨界強(qiáng)度值為?77 dBm。初始化區(qū)間[a,b]中 上界 a與 下界 b的值都等于?77 dBm，這樣形成3 個(gè) 區(qū) 間 [0, a)、 [a, b]、 (b, ?∞)。 區(qū) 間 [a, b]為Qlearning 算法學(xué)習(xí)區(qū)間，進(jìn)行強(qiáng)化學(xué)習(xí)決策；區(qū)間外 [0,a)、 (b, ?∞)進(jìn)行狀態(tài)的直接決策。隨著算法執(zhí)行，區(qū)間 [a,b]的值不斷更新，進(jìn)行區(qū)間擴(kuò)展。自適應(yīng)區(qū)間更新及決策算法流程如下：

1) 設(shè)定初始的閾值 dwin=?77 dBm，節(jié)點(diǎn)根據(jù)當(dāng)前采集到某鄰居節(jié)點(diǎn)的RSSI，當(dāng)大于閾值判定為穩(wěn)定聯(lián)接狀態(tài) s1，小于閾值判定為非穩(wěn)定聯(lián)接狀態(tài) s2。 狀態(tài)變量 s表示節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的聯(lián)接狀態(tài)，表示為：

2) 當(dāng)前節(jié)點(diǎn)根據(jù)其鄰居節(jié)點(diǎn)的RSSI，按照式(2)進(jìn)行狀態(tài)判定，作為下一時(shí)刻節(jié)點(diǎn)與此鄰居節(jié)點(diǎn)聯(lián)接狀態(tài)的預(yù)測(cè)s?；假設(shè)下一時(shí)刻信號(hào)強(qiáng)度為RSSI′，又根據(jù)式(2)判定下一時(shí)刻實(shí)際聯(lián)接狀態(tài)為s′， 若，則根據(jù)情況調(diào)整區(qū)間 [a,b]，初始狀態(tài)a=b=?77 dBm。按照流程1)判定出錯(cuò)時(shí)，若a RSSI，則 調(diào) 整b=RSSI。直接決策調(diào)整邊界公式表示為：

3) 直接決策：按照式(2)進(jìn)行狀態(tài)直接決策，在直接決策區(qū)間 [0,a)內(nèi) ，直接判決為 s1狀態(tài)；在直接決策區(qū)間 (b, ?∞)內(nèi) ，直接判決為 s2狀態(tài)。

4) 節(jié)點(diǎn)根據(jù)每一鄰居節(jié)點(diǎn)前后時(shí)刻接收信號(hào)強(qiáng)度值，按照式(2)進(jìn)行決策區(qū)間邊界調(diào)整；按照流程3)進(jìn)行直接決策區(qū)間的狀態(tài)判定；而對(duì)于直接決策區(qū)間外的自適應(yīng)區(qū)間 [a,b]，按照Q-learning 算法進(jìn)行強(qiáng)化學(xué)習(xí)和狀態(tài)決策，并對(duì)Q 值矩陣進(jìn)行持續(xù)更新。

5) 不同時(shí)刻，節(jié)點(diǎn)按照流程2)～流程4)鄰居節(jié)點(diǎn)接收信號(hào)強(qiáng)度進(jìn)行邊界循環(huán)更新和狀態(tài)決策。

該算法可以異步分布式執(zhí)行，網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)獨(dú)立按照上述算法進(jìn)行自主學(xué)習(xí)決策。每個(gè)節(jié)點(diǎn)對(duì)其各鄰居節(jié)點(diǎn)進(jìn)行聯(lián)接狀態(tài)穩(wěn)定關(guān)系判定，最終由穩(wěn)定聯(lián)接狀態(tài)的鄰居節(jié)點(diǎn)構(gòu)成此節(jié)點(diǎn)的穩(wěn)定鄰居集。由相互穩(wěn)定聯(lián)接的節(jié)點(diǎn)形成移動(dòng)無線自組織網(wǎng)絡(luò)的穩(wěn)態(tài)拓?fù)洹?/p>

2.2 Q-learning 算法結(jié)構(gòu)

基于Q-learning 的分布式自適應(yīng)拓?fù)浞€(wěn)定性算法中，每一個(gè)移動(dòng)節(jié)點(diǎn)可以視為一個(gè)Agent，這樣整個(gè)網(wǎng)絡(luò)的動(dòng)態(tài)變化都可認(rèn)為是一個(gè)分布式多Agent 協(xié)作系統(tǒng)。對(duì)于每個(gè)Agent，假設(shè)其環(huán)境狀態(tài)集為S ，動(dòng)作集為A， 獎(jiǎng)賞函數(shù)為，動(dòng)作選擇策略為 π(si,aj)。根據(jù)Q-learning 算法基本結(jié)構(gòu)描述如下：

1) 狀態(tài)集S ：由離散的狀態(tài)構(gòu)成。狀態(tài)定義為：

式中， s1狀態(tài)為根據(jù)當(dāng)前接收到某鄰居節(jié)點(diǎn)RSSI，節(jié)點(diǎn)與某鄰居節(jié)點(diǎn)處于穩(wěn)定聯(lián)接狀態(tài)； s2狀態(tài)為根據(jù)當(dāng)前接收到某鄰居節(jié)點(diǎn)RSSI，與某鄰居節(jié)點(diǎn)處于非穩(wěn)定聯(lián)接狀態(tài)。

2) 動(dòng)作集 A：每個(gè)Agent 可以采取的動(dòng)作分為預(yù)判穩(wěn)定聯(lián)接狀態(tài)和預(yù)判非穩(wěn)定聯(lián)接狀態(tài)兩個(gè)類型。動(dòng)作集定義為：

式中， a1為 預(yù)判穩(wěn)定狀態(tài)； a2為預(yù)判非穩(wěn)定狀態(tài)。

表1 獎(jiǎng)勵(lì)函數(shù)值表

根據(jù)表1 分析，可以得到獎(jiǎng)賞函數(shù)定義式：

4) 動(dòng)作選擇策略 π(si,aj)：Q-learning 算法的策略選擇決定了Agent 怎樣去平衡探索和開發(fā)之間的問題。Agent 通過探索可以持續(xù)學(xué)習(xí)發(fā)現(xiàn)更優(yōu)的策略；通過開發(fā)選擇轉(zhuǎn)向期望狀態(tài)最佳動(dòng)作。本文算法選擇 ε?貪心策略來確定最優(yōu)動(dòng)作，每次選擇Q 值最大的動(dòng)作。即：

5) 更新Q 值函數(shù)：綜合動(dòng)作、獎(jiǎng)勵(lì)值的設(shè)計(jì)，根據(jù)式(1)的方法進(jìn)行函數(shù)的更新。

3 仿真與結(jié)果分析

為了驗(yàn)證算法有效性和穩(wěn)定性，通過Python仿真環(huán)境設(shè)計(jì)了3 組實(shí)驗(yàn)來研究本文所提出算法的性能。為了能夠更加真實(shí)地建立MANET 中節(jié)點(diǎn)運(yùn)動(dòng)的隨機(jī)性以及各個(gè)節(jié)點(diǎn)之間速度以及運(yùn)動(dòng)方向的隨機(jī)性模型，在仿真場(chǎng)景的設(shè)計(jì)中采用了MANET中經(jīng)典的運(yùn)動(dòng)模型—隨機(jī)游走移動(dòng)模型[11](random walk mobility model, RWM)來驗(yàn)證本文算法性能。

實(shí)驗(yàn)設(shè)定在150×150 m2的網(wǎng)絡(luò)區(qū)域內(nèi)生成移動(dòng)節(jié)點(diǎn)，每個(gè)移動(dòng)節(jié)點(diǎn)選擇隨機(jī)的方向運(yùn)動(dòng)、隨機(jī)的運(yùn)動(dòng)時(shí)間、隨機(jī)的停頓時(shí)間，實(shí)驗(yàn)中設(shè)定節(jié)點(diǎn)數(shù)目為15 個(gè)且每個(gè)節(jié)點(diǎn)之間的運(yùn)動(dòng)互不影響。表2所示為仿真實(shí)驗(yàn)的系統(tǒng)參數(shù)。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

根據(jù)上述的仿真參數(shù)設(shè)定，將本文算法應(yīng)用到RWM 移動(dòng)模型中進(jìn)行算法的有效性測(cè)試。仿真中設(shè)定RSSI 的測(cè)量模型為自由空間傳播模型[12]，計(jì)算公式如下：

式中，Loss 是傳播損耗，單位為dB，與傳輸路徑有關(guān)；d 是距離，單位為km，f是工作頻率，單位為MHz。假設(shè)各個(gè)節(jié)點(diǎn)發(fā)射信號(hào)為窄帶信號(hào)，工作頻率為2 400 MHz，并且發(fā)射功率為0 dBm 時(shí)，可以得到 RS SI=?Loss，根據(jù)節(jié)點(diǎn)的最大通信距離d=0.07時(shí) 計(jì)算得到RSSI 值為 ?7 7 dBm。考慮電磁波在空氣中的損耗，設(shè)定了可以穩(wěn)定聯(lián)接的臨界值為 ?7 7 dBm。

在算法開始執(zhí)行前，設(shè)定初始的學(xué)習(xí)迭代次數(shù)為200 輪、通過學(xué)習(xí)200 輪之后得到策略表以及強(qiáng)化學(xué)習(xí)區(qū)間，對(duì)測(cè)試數(shù)據(jù)進(jìn)行100 輪預(yù)測(cè)來計(jì)算準(zhǔn)確率，將100 輪預(yù)測(cè)的聯(lián)接狀態(tài)結(jié)果與節(jié)點(diǎn)在實(shí)際移動(dòng)過程中各個(gè)節(jié)點(diǎn)聯(lián)接狀態(tài)進(jìn)行統(tǒng)計(jì)平均，計(jì)算出每個(gè)節(jié)點(diǎn)在100 輪預(yù)測(cè)過程中的準(zhǔn)確率。

圖5 為仿真環(huán)境都相同的情況下，分別設(shè)定不同學(xué)習(xí)率α 為0.1、0.5、0.7 的準(zhǔn)確率值對(duì)比圖。

根據(jù)圖5 中不同學(xué)習(xí)率 α對(duì)準(zhǔn)確率的影響曲線分析可知，當(dāng)學(xué)習(xí)率 α的取值為0.1 時(shí)所有節(jié)點(diǎn)的準(zhǔn)確率值均維持在95%左右，并且各個(gè)節(jié)點(diǎn)之間的預(yù)測(cè)準(zhǔn)確率變化值相差不大，整個(gè)曲線變化比較平緩；而在學(xué)習(xí)率 α取值為0.5 或0.7 時(shí)準(zhǔn)確率比0.1 時(shí)均有所下降，并且各個(gè)節(jié)點(diǎn)的預(yù)測(cè)準(zhǔn)確率相差變大，曲線的變化程度較明顯。出現(xiàn)該現(xiàn)象是由于在執(zhí)行本文算法進(jìn)行預(yù)測(cè)的過程中，節(jié)點(diǎn)主要根據(jù)鄰居節(jié)點(diǎn)過去運(yùn)動(dòng)經(jīng)驗(yàn)來判斷下一傳輸時(shí)刻聯(lián)接的狀態(tài)程度，如果學(xué)習(xí)率 α增大將增大Agent 的探索過程則對(duì)節(jié)點(diǎn)的運(yùn)動(dòng)經(jīng)驗(yàn)的取值變小，從而導(dǎo)致節(jié)點(diǎn)的預(yù)測(cè)錯(cuò)誤的幾率增加。但是在不同學(xué)習(xí)率α的影響下準(zhǔn)確率維持在0.8～0.95，從而證明算法的穩(wěn)定性。因此，在接下來的實(shí)驗(yàn)過程中均選取學(xué)習(xí)率α 為0.1 作為本文算法中的參數(shù)。

為了證明算法的有效性，通過在RWM 模型中分別應(yīng)用本文提出的基于Q-learning 的分布式自適應(yīng)拓?fù)浞€(wěn)定性算法與通過強(qiáng)化學(xué)習(xí)算法直接得到策略表來判斷穩(wěn)定聯(lián)接次數(shù)比較。實(shí)驗(yàn)設(shè)定兩次仿真環(huán)境均相同的情況下，分別統(tǒng)計(jì)測(cè)試數(shù)據(jù)100 輪中每個(gè)節(jié)點(diǎn)預(yù)測(cè)聯(lián)接狀態(tài)的準(zhǔn)確次數(shù)率。

根據(jù)圖6 所示，本文提出的基于Q-learning的分布式自適應(yīng)拓?fù)浞€(wěn)定性算法的準(zhǔn)確率比單獨(dú)使用Q 學(xué)習(xí)算法的準(zhǔn)確率整體提高了30%左右，故本文算法在預(yù)測(cè)的準(zhǔn)確率方面明顯優(yōu)于單獨(dú)使用Q 學(xué)習(xí)算法，其原因是各個(gè)Agent 通過自適應(yīng)的強(qiáng)化學(xué)習(xí)區(qū)間的不斷更新將每次的學(xué)習(xí)變化范圍擴(kuò)大，自適應(yīng)區(qū)間外直接判斷聯(lián)接狀態(tài)，自適應(yīng)區(qū)間內(nèi)隨著不斷的強(qiáng)化學(xué)習(xí)經(jīng)驗(yàn)的積累做出更加精確地預(yù)測(cè)，提升算法的性能。兩種算法的比較也說明本文算法的有效性。

圖7 為通過隨機(jī)的抽取某一輪預(yù)測(cè)過程中單個(gè)節(jié)點(diǎn)預(yù)測(cè)得到的網(wǎng)絡(luò)拓?fù)渎?lián)接關(guān)系，與圖8 的節(jié)點(diǎn)在實(shí)際運(yùn)動(dòng)過程中的真實(shí)聯(lián)接關(guān)系進(jìn)行比較。實(shí)驗(yàn)仿真環(huán)境與上述兩個(gè)實(shí)驗(yàn)相同，仿真中實(shí)際聯(lián)接穩(wěn)定的閾值設(shè)定為 dwin=?77 dBm，根據(jù)設(shè)定閾值判斷穩(wěn)定聯(lián)接鄰居節(jié)集。

根據(jù)圖7 中處于1 號(hào)節(jié)點(diǎn)通信范圍內(nèi)的節(jié)點(diǎn)集合為{4,9,10,13,15}，在預(yù)測(cè)穩(wěn)定拓?fù)渎?lián)接過程中，生成的聯(lián)接關(guān)系集合為{4,10,13,15}，預(yù)測(cè)出9 號(hào)節(jié)點(diǎn)不能在下一傳輸時(shí)刻穩(wěn)定聯(lián)接。通過預(yù)測(cè)拓?fù)渎?lián)接關(guān)系與圖8 真實(shí)拓?fù)渎?lián)接關(guān)系比較表明，預(yù)測(cè)結(jié)果與真實(shí)聯(lián)接關(guān)系相一致。強(qiáng)化學(xué)習(xí)的過程中每個(gè)Agent 都會(huì)對(duì)其他節(jié)點(diǎn)的運(yùn)動(dòng)特性有累積性的學(xué)習(xí)，不會(huì)因?yàn)楣?jié)點(diǎn)處于通信范圍內(nèi)判斷為穩(wěn)定聯(lián)接鏈路，Agent 會(huì)根據(jù)節(jié)點(diǎn)當(dāng)前的運(yùn)動(dòng)狀態(tài)以及策略表中學(xué)習(xí)得到的經(jīng)驗(yàn)來有效避免在短時(shí)間內(nèi)可能會(huì)快速斷開的鏈路聯(lián)接，所以9 號(hào)節(jié)點(diǎn)在預(yù)測(cè)過程中被判斷非穩(wěn)定聯(lián)接狀態(tài)。

4 結(jié) 束 語

本文通過研究MANET 中移動(dòng)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)拓?fù)溆绊?，提出了基于?qiáng)化學(xué)習(xí)的分布式自適應(yīng)算法。算法中每個(gè)節(jié)點(diǎn)通過對(duì)其他節(jié)點(diǎn)運(yùn)動(dòng)特性學(xué)習(xí)得到下一傳輸時(shí)刻穩(wěn)定聯(lián)接的鄰居集合，通過穩(wěn)定聯(lián)接集合預(yù)測(cè)移動(dòng)節(jié)點(diǎn)之間網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定聯(lián)接關(guān)系，可以更好地適應(yīng)網(wǎng)絡(luò)拓?fù)渥兓ANET 中穩(wěn)定的拓?fù)渎?lián)接關(guān)系很大程度上改善了路由選擇，同時(shí)也提高了網(wǎng)絡(luò)通信服務(wù)質(zhì)量。實(shí)驗(yàn)結(jié)果表明，基于Q-learning 的分布式自適應(yīng)拓?fù)浞€(wěn)定性算法高效穩(wěn)定且準(zhǔn)確度高，能夠有效地實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)渎?lián)接的穩(wěn)定性選擇。