蒯振然，王少尉

(南京大學(xué) 電子科學(xué)與工程學(xué)院， 江蘇 南京 210023)

移動自組織網(wǎng)絡(luò)(Mobile Ad hoc NETwork，MANET)是一種無基礎(chǔ)設(shè)施、由移動通信節(jié)點(diǎn)組成的無線網(wǎng)絡(luò)，具有組網(wǎng)靈活、配置方便和抗毀性強(qiáng)等特點(diǎn)[1]。由于節(jié)點(diǎn)的通信范圍有限，源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的通信經(jīng)過中間節(jié)點(diǎn)的多跳路由完成。然而，在一些動態(tài)場景下，節(jié)點(diǎn)的移動性使得拓?fù)浣Y(jié)構(gòu)頻繁變化，傳統(tǒng)的路由協(xié)議需要不斷地計(jì)算端到端的路由來保證數(shù)據(jù)的傳輸，缺乏對動態(tài)網(wǎng)絡(luò)的自適應(yīng)能力，而簡單的洪泛機(jī)制會產(chǎn)生大量開銷[2-3]。因此，研究針對MANET動態(tài)特性的具備自適應(yīng)性和可靠性的路由方式，有重要的理論和應(yīng)用價(jià)值。

最早將強(qiáng)化學(xué)習(xí)應(yīng)用于MANET路由的工作見諸文獻(xiàn)[4]，文中提出的Q-Routing算法使用了強(qiáng)化學(xué)習(xí)的經(jīng)典Q-Learning框架，將衡量路徑優(yōu)劣的權(quán)值置于每個節(jié)點(diǎn)維護(hù)的Q表中，根據(jù)Q表選擇下一跳節(jié)點(diǎn)，傳回的確認(rèn)字符(ACKnowledge character，ACK)用來更新Q表以選擇更好的路由。文獻(xiàn)[5]則根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)的度來調(diào)整強(qiáng)化學(xué)習(xí)的學(xué)習(xí)速率，更高的節(jié)點(diǎn)度對應(yīng)更高的學(xué)習(xí)速率，從而使用更少的時(shí)間來探測網(wǎng)絡(luò)的真實(shí)狀態(tài)。

在強(qiáng)化學(xué)習(xí)算法收斂到最優(yōu)路由的過程中會伴隨著吞吐率的損失，在高度動態(tài)的場景下，這種損失會使信息的傳遞效率降低，所以上述方法并不能直接應(yīng)用于對信息完整性要求較高的情況。文獻(xiàn)[6]提出從節(jié)點(diǎn)的廣播消息獲得鄰居節(jié)點(diǎn)的Q值，通過這種方式減少探索網(wǎng)絡(luò)狀態(tài)所需的時(shí)間，降低算法在學(xué)習(xí)過程中的性能損失。文獻(xiàn)[7]提出通過隨機(jī)輪詢鄰節(jié)點(diǎn)的自適應(yīng)Q-routing，用于防止數(shù)據(jù)包回傳，該方法提高了路由在高負(fù)載條件下的穩(wěn)定性。文獻(xiàn)[8]提出了基于強(qiáng)化學(xué)習(xí)的智能魯棒路由(Smart Robust Routing，SRR)算法，對每個節(jié)點(diǎn)，使用置信度來衡量鄰居節(jié)點(diǎn)的可靠性。當(dāng)網(wǎng)絡(luò)狀態(tài)相對穩(wěn)定時(shí)，使用結(jié)合置信度的Q-routing方法進(jìn)行路由，而節(jié)點(diǎn)移動導(dǎo)致網(wǎng)絡(luò)狀態(tài)不穩(wěn)定時(shí)，則以一定概率使用廣播的方式確保將信息傳到目的節(jié)點(diǎn)，這種方式加快了在網(wǎng)絡(luò)狀態(tài)不穩(wěn)定時(shí)路由的收斂速率，并保證了系統(tǒng)的吞吐率。然而，廣播機(jī)制增加了路由開銷。并且在Q值和置信度一直動態(tài)變化的情況下，按照統(tǒng)一度量選擇下一跳節(jié)點(diǎn)，會有陷入路由環(huán)路的情況，使重復(fù)包檢測機(jī)制進(jìn)行丟包處理。

本文研究了MANET中的路由問題，對SRR算法的局限性做出改進(jìn)，提出了一種基于強(qiáng)化學(xué)習(xí)的分步路由算法，通過結(jié)合強(qiáng)化學(xué)習(xí)路由Q-Routing和利用Q值篩選符合路由目標(biāo)節(jié)點(diǎn)的方式，使節(jié)點(diǎn)更傾向于選擇提升MANET網(wǎng)絡(luò)性能的路由，保障數(shù)據(jù)包到達(dá)率。在篩選出的節(jié)點(diǎn)基礎(chǔ)上，結(jié)合置信度實(shí)現(xiàn)在網(wǎng)絡(luò)條件較差時(shí)只向部分節(jié)點(diǎn)廣播，在提升路由可靠性的同時(shí)，降低了網(wǎng)絡(luò)的路由開銷。

1 強(qiáng)化學(xué)習(xí)路由框架

Qt+1(xt,at)=(1-αt)Qt(xt,at)+

(1)

式中，αt∈(0,1]是學(xué)習(xí)速率。式(1)代表以αt的速率用估計(jì)的累積獎賞對當(dāng)前的累積獎賞進(jìn)行更新[9]。在與環(huán)境交互的過程中，隨著Q表的更新，Q值會逐漸接近于真實(shí)的累積獎賞，智能體在各種狀態(tài)下會趨向于選擇最優(yōu)的動作。

1.1 Q-Routing

本節(jié)將介紹文獻(xiàn)[4]如何將MANET路由問題歸約到Q-learning算法的框架下，并具體說明在強(qiáng)化學(xué)習(xí)框架下所采用的獎賞與更新方式。對每個節(jié)點(diǎn)，可以將其看作智能體，每個節(jié)點(diǎn)只有在數(shù)據(jù)包到達(dá)節(jié)點(diǎn)時(shí)，才需要轉(zhuǎn)發(fā)，所以只存在一種需要做動作的狀態(tài)。節(jié)點(diǎn)需轉(zhuǎn)發(fā)數(shù)據(jù)包至鄰居節(jié)點(diǎn)，最終目的地是目的節(jié)點(diǎn)。

假設(shè)發(fā)送端可以檢測發(fā)出數(shù)據(jù)包和接收到ACK之間的往返時(shí)延(Round Trip Time，RTT)，可以將其作為節(jié)點(diǎn)選擇下一跳節(jié)點(diǎn)的獎賞。以Q-Learning算法為框架，讓每個節(jié)點(diǎn)m維護(hù)一個元素?cái)?shù)目為其鄰居節(jié)點(diǎn)數(shù)量的Q表。表中的每一項(xiàng)為Qm(d,n)，代表選擇鄰居節(jié)點(diǎn)n作為下一跳節(jié)點(diǎn)的情況下，在到達(dá)目的節(jié)點(diǎn)d前的總RTT。該數(shù)值可以一定程度上體現(xiàn)節(jié)點(diǎn)的端到端時(shí)延性能，可以將最小化總RTT作為Q-Routing的目標(biāo)。

Qm,t+1(d,n)=(1-αt)Qm,t(d,n)+

(2)

式中，等號右邊第一項(xiàng)代表Q值的原始值，第二項(xiàng)可以代表Q值的更新部分，TRTT,t是第t次傳輸返回的RTT，αt∈(0,1]是第t次更新的學(xué)習(xí)速率，代表了Q值更新信息所占的權(quán)重。隨著估計(jì)值接近真實(shí)值，αt通常隨著更新次數(shù)減小，為了使Q值收斂，將把αt的取值與置信度的取值相聯(lián)系。當(dāng)更新次數(shù)增加到j(luò)次時(shí)，經(jīng)過迭代，對于節(jié)點(diǎn)m，對應(yīng)鄰節(jié)點(diǎn)為n的Q值為：

(3)

式中，Qm,0(d,n)是節(jié)點(diǎn)m對應(yīng)于鄰節(jié)點(diǎn)n的初始Q值。從等號右邊第二項(xiàng)可以看出，Q值更新信息距離當(dāng)前時(shí)刻越近，賦予的權(quán)重越高，對Q值的估計(jì)也因此越容易跟蹤網(wǎng)絡(luò)的變化。

1.2 置信度

網(wǎng)絡(luò)中每個節(jié)點(diǎn)同樣維護(hù)一個置信度表，每一項(xiàng)為Cm(d,n)，代表節(jié)點(diǎn)m選擇鄰居節(jié)點(diǎn)n作為下一跳節(jié)點(diǎn)的情況下，能到達(dá)目的節(jié)點(diǎn)d的可信度，其中Cm(d,n)∈[0，1]。

當(dāng)數(shù)據(jù)包被轉(zhuǎn)發(fā)時(shí)，更新過程[5]為：

Cm,t+1(d,n)=(1-η)Cm,t(d,n)

(4)

節(jié)點(diǎn)m接收節(jié)點(diǎn)n的ACK后，更新過程為：

(5)

圖1 置信度更新過程Fig.1 Process of updating confidence factors

其中，η是置信度更新的學(xué)習(xí)速率，代表置信度更新信息所占權(quán)重。然而，ACK包存在延遲的情況，即在節(jié)點(diǎn)m發(fā)射端TX接收到接收端RX相應(yīng)的ACK包之前，又轉(zhuǎn)發(fā)了k個數(shù)據(jù)包，如圖1所示。因?yàn)椴煌瑫r(shí)刻的ACK影響是不同的，例如k=4時(shí)，前兩個數(shù)據(jù)包轉(zhuǎn)發(fā)失敗，后兩個數(shù)據(jù)包轉(zhuǎn)發(fā)成功意味著通信鏈路條件變好。因此僅使用式(4)、式(5)更新并不能反映類似的變化。于是將數(shù)據(jù)包轉(zhuǎn)發(fā)成功時(shí)更新過程改為：

式中，(1-η)k是對接收到的置信度更新信息根據(jù)延遲的結(jié)果進(jìn)行縮放處理。文獻(xiàn)[8]證明了式(5)與式(6)在更新次數(shù)足夠多的情況下是趨向于相等的，因此成功轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，采用式(6)對置信度進(jìn)行更新。

置信度值除了用來選擇更加可靠的節(jié)點(diǎn)，還用來在接收到ACK而未更新置信度之前，調(diào)整Q-Routing學(xué)習(xí)速率αt[10]。

(7)

目的是在鄰居節(jié)點(diǎn)置信度更高，或當(dāng)前節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包前的置信度更低時(shí)，對鄰居節(jié)點(diǎn)返回的Q值在更新時(shí)賦予更高的權(quán)重。

2 分步路由選擇算法

為了保證路由可靠性的同時(shí)，降低路由開銷，提出了分步路由選擇算法，使用Q-Routing和置信度結(jié)合來進(jìn)行路由，目標(biāo)是最小化總RTT。源節(jié)點(diǎn)s發(fā)送和中間節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，先結(jié)合Q表和置信度表選出下一跳節(jié)點(diǎn)，根據(jù)該節(jié)點(diǎn)的置信度來選擇是廣播還是直接轉(zhuǎn)發(fā)數(shù)據(jù)包至該節(jié)點(diǎn)。

在選擇下一跳節(jié)點(diǎn)時(shí)，結(jié)合Q-Routing算法和置信度來進(jìn)行選擇，本文考慮的選擇度量為SCQ=Qm(d,n)[1-Cm(d,n)]，目標(biāo)是選擇Q值較小、可信度較高的下一跳節(jié)點(diǎn)。然而，節(jié)點(diǎn)的移動性導(dǎo)致節(jié)點(diǎn)的Q值和置信度會變化，僅基于該度量進(jìn)行下一跳節(jié)點(diǎn)的選擇，會增大選擇不符合路由目標(biāo)節(jié)點(diǎn)的概率，甚至陷入路由環(huán)路，從而增加路由開銷。為了提升節(jié)點(diǎn)選擇的容錯率，先篩選出符合路由目標(biāo)的節(jié)點(diǎn)。設(shè)節(jié)點(diǎn)m的鄰居節(jié)點(diǎn)數(shù)量為N，設(shè)節(jié)點(diǎn)Q表中的Q值按數(shù)值大小排序，即Qm(d,a1)

第一步選擇Q表中比例為λ、Q值最小的鄰居節(jié)點(diǎn)子集Nc，大小為「λN?，該集合表示為：

Nc={a1,a2,…,a「λN?}

(8)

第二步從Nc中選擇度量SCQ最小的節(jié)點(diǎn)。

(9)

先基于Q值進(jìn)行選擇也是為了減小在置信度未收斂時(shí)，對路由開銷帶來的負(fù)面影響。因?yàn)樵诖_定了下一跳節(jié)點(diǎn)n*之后，SRR算法根據(jù)置信度確定是否需要進(jìn)行廣播來保證路由可靠性。而SRR算法以廣播的方式進(jìn)行傳輸在增加了路由開銷的條件下可以保證數(shù)據(jù)包到達(dá)率的性能，所以為了保留可靠性，并降低路由開銷，提出的分步路由算法將數(shù)據(jù)包廣播給在節(jié)點(diǎn)選擇階段篩選出的最符合路由目標(biāo)的鄰居節(jié)點(diǎn)子集Nc，而是否進(jìn)行廣播的概率則根據(jù)置信度計(jì)算，可以表示為：

pU=ε+(1-ε)[1-Cm(d,n*)]

(10)

由式(10)看出：置信度接近0時(shí)，節(jié)點(diǎn)進(jìn)行廣播的概率更大；置信度接近1時(shí)，廣播的概率應(yīng)當(dāng)減小并趨于ε。在節(jié)點(diǎn)發(fā)送數(shù)據(jù)包或拓?fù)涓淖兊某跗冢眯哦戎挡粔蚋?，就會有更高的概率選擇廣播的方式傳輸，Q值和置信度值也會更快地更新，而且在轉(zhuǎn)發(fā)初期或網(wǎng)絡(luò)拓?fù)涓淖兂跗?，Q表未收斂時(shí)，廣播的方式也使路由的可靠性得到了保障。

所有收到廣播數(shù)據(jù)包的節(jié)點(diǎn)，都需要傳回ACK，包含其自身的節(jié)點(diǎn)序列號、下一跳節(jié)點(diǎn)的Q值和置信度等信息。

(11)

目的是在拓?fù)渥兓瘯r(shí)能及時(shí)更新鄰居節(jié)點(diǎn)信息。盡管有部分鄰居節(jié)點(diǎn)并未在篩選的集合Nc中，但是如果判斷為廣播數(shù)據(jù)包，仍然需要傳回ACK，使廣播節(jié)點(diǎn)掌握鄰居節(jié)點(diǎn)的信息。

當(dāng)根據(jù)廣播數(shù)據(jù)包的ACK更新信息時(shí)，并不像SRR算法一樣保存Q表和置信度表中所有節(jié)點(diǎn)的信息，而是選擇刪除表中不再是鄰居節(jié)點(diǎn)的信息。若仍為鄰居節(jié)點(diǎn)，則按照規(guī)則更新Q值和置信度，新的鄰居節(jié)點(diǎn)將對應(yīng)Q值設(shè)為表中其余節(jié)點(diǎn)Q值的均值，置信度則設(shè)為1以縮短收斂時(shí)間。若不需要進(jìn)行廣播，節(jié)點(diǎn)就根據(jù)選擇的下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)后根據(jù)式(4)更新置信度。目的是在拓?fù)渥兓绊懙铰酚蓵r(shí)，更新節(jié)點(diǎn)本地信息。在轉(zhuǎn)發(fā)成功，下一跳節(jié)點(diǎn)接收到數(shù)據(jù)包后，發(fā)送的ACK數(shù)據(jù)包包括了所選下一跳節(jié)點(diǎn)n*的Q值和置信度以及相關(guān)節(jié)點(diǎn)信息。接收ACK的節(jié)點(diǎn)，則由ACK包含的信息根據(jù)式(7)、式(2)、式(6)更新αt、Q值和置信度。

所有數(shù)據(jù)包傳輸?shù)倪^程都采用了重復(fù)包檢測機(jī)制，如圖2所示。當(dāng)出現(xiàn)路由環(huán)路時(shí)，接收包的節(jié)點(diǎn)進(jìn)行丟包處理，如果只是廣播的包的復(fù)制，進(jìn)行丟包處理，但會傳回ACK，以提供確認(rèn)該路由可用的信息來更新置信度。分步路由選擇算法的步驟如算法1所示。

(a) 形成路由環(huán)路(a) Traverse a routing loop

(b) 重復(fù)包到達(dá)(b) Arrival of duplicate packets圖2 重復(fù)數(shù)據(jù)包檢測Fig.2 Duplicate packet detection

算法1 分步路由算法

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

本節(jié)給出了提出的分步路由選擇算法的仿真結(jié)果。將仿真的場景設(shè)置在1000 m×600 m的矩形區(qū)域，源節(jié)點(diǎn)和目的節(jié)點(diǎn)設(shè)為靜止，分別位于區(qū)域600 m寬邊的中間位置。中間節(jié)點(diǎn)數(shù)為30，在矩形區(qū)域內(nèi)均勻分布，節(jié)點(diǎn)的移動速度在[0 m/s,30 m/s]內(nèi)均勻分布，方向在[0,2π]范圍內(nèi)均勻分布，以當(dāng)前方向和速率持續(xù)的時(shí)間也在仿真時(shí)間內(nèi)均勻分布，如果持續(xù)的時(shí)間結(jié)束，或者超出仿真區(qū)域范圍，則重新分配速度、方向和持續(xù)時(shí)間，節(jié)點(diǎn)通信的范圍為300 m。仿真模擬了從源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包到目的節(jié)點(diǎn)的過程。源節(jié)點(diǎn)以每秒10個1500 Byte數(shù)據(jù)包的速率發(fā)送數(shù)據(jù)，即速率為120 kbit/s，置信度更新參數(shù)η=0.3。隨著Q值和置信度更新，置信度接近于1，此時(shí)根據(jù)Q值和置信度已經(jīng)可以確保路由的可靠性，參數(shù)ε過高會增加廣播概率，進(jìn)而增加路由開銷，因此選取ε=0.05。

圖3比較了在不同λ情況下，300 s內(nèi)平均路由開銷與數(shù)據(jù)包到達(dá)速率的比值。該比值用來體現(xiàn)不同λ對路由開銷和數(shù)據(jù)包到達(dá)率的整體影響。路由開銷則使用網(wǎng)絡(luò)中所有鏈路的數(shù)據(jù)速率總和來衡量?？梢钥闯?，當(dāng)λ值較高，接近于1時(shí)，廣播時(shí)目標(biāo)為所有鄰節(jié)點(diǎn)，這大大增加了路由開銷；當(dāng)λ值較低時(shí)，路由初期無法盡快更新Q值與置信度信息，降低路由可靠性。通過比較，確定λ=0.4，此時(shí)，為了保障數(shù)據(jù)包到達(dá)速率而付出的路由開銷要遠(yuǎn)小于對所有節(jié)點(diǎn)進(jìn)行廣播的方式。

將提出的分布路由算法(StepWise Routing，SWR)與SSR算法和開放最短路徑優(yōu)先(Open Shortest Path First，OSPF)路由[11]相比較，來分析不同算法對路由開銷與數(shù)據(jù)包到達(dá)速率的影響。仿真中，以目的節(jié)點(diǎn)的數(shù)據(jù)速率來衡量數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)的成功率，并且以網(wǎng)絡(luò)中所有鏈路的數(shù)據(jù)速率來衡量系統(tǒng)的路由開銷。

圖4比較了在300 s內(nèi)不同路由方法在目的節(jié)點(diǎn)的吞吐率；圖5則比較了對應(yīng)的路由開銷。從圖5中可以看出，OSPF路由擁有的路由開銷更低，但是對目的節(jié)點(diǎn)來說，數(shù)據(jù)包到達(dá)率不夠穩(wěn)定，因?yàn)楣?jié)點(diǎn)的移動會改變拓?fù)浣Y(jié)構(gòu)，使得以O(shè)SPF的方式路由的成功率降低。基于強(qiáng)化學(xué)習(xí)的SRR算法相對于OSPF算法提升了路由的穩(wěn)定性，數(shù)據(jù)成功傳輸率平均增加了70%，平均丟包率僅有1.6%，相對地，也增加了1倍以上的路由開銷。

圖3 路由開銷與數(shù)據(jù)包到達(dá)速率比值Fig.3 Ratio of routing overhead to packet delivery rate

圖4 數(shù)據(jù)包到達(dá)速率仿真結(jié)果Fig.4 Results of packet delivery rate

圖5 路由開銷仿真結(jié)果Fig.5 Results of routing overhead

所提出的SWR算法在數(shù)據(jù)成功傳輸率上接近SRR算法，平均丟包率為4%，而平均路由開銷在0～40 s時(shí)相對于SRR算法稍高，原因是路由開始時(shí)置信度尚未收斂，SWR廣播的節(jié)點(diǎn)數(shù)量較少，廣播次數(shù)多，開銷較大。40 s之后相對于SRR降低30%，平均開銷降低了23%。因?yàn)樵诼酚蓵r(shí)，SWR算法基于Q值篩選出節(jié)點(diǎn)集合的方式再選擇，所以避免了在直接結(jié)合置信度的選擇中選擇較差的節(jié)點(diǎn)；同時(shí)，即便選擇廣播，也利用了路由時(shí)篩選出的節(jié)點(diǎn)信息，從而減少無益于到達(dá)目的節(jié)點(diǎn)的路由選擇。

4 結(jié)論

本文研究了MANET中的路由問題，基于強(qiáng)化學(xué)習(xí)提出了分步路由算法。通過結(jié)合強(qiáng)化學(xué)習(xí)路由Q-Routing和利用Q值篩選符合路由目標(biāo)節(jié)點(diǎn)的方式，使節(jié)點(diǎn)更傾向于選擇提升MANET網(wǎng)絡(luò)性能的路由，保障數(shù)據(jù)包到達(dá)率。在篩選出的節(jié)點(diǎn)基礎(chǔ)上，結(jié)合置信度實(shí)現(xiàn)在網(wǎng)絡(luò)條件較差時(shí)只向部分節(jié)點(diǎn)廣播，在提升路由可靠性的同時(shí)，降低了網(wǎng)絡(luò)的路由開銷。仿真結(jié)果表明：和傳統(tǒng)OSPF路由相比，以少量的路由開銷為代價(jià)，數(shù)據(jù)傳輸成功率提升了70%；和基于強(qiáng)化學(xué)習(xí)的SRR算法相比，數(shù)據(jù)傳輸成功率相差僅2.4%的情況下，路由開銷降低了23%。