一種基于多Agent強(qiáng)化學(xué)習(xí)的無線傳感器網(wǎng)絡(luò)多路徑路由協(xié)議

喬　陽,　唐　昊,　程文娟,　江　琦,　馬學(xué)森

(1.合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院,安徽 合肥　230009; 2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥　230009)

?

一種基于多Agent強(qiáng)化學(xué)習(xí)的無線傳感器網(wǎng)絡(luò)多路徑路由協(xié)議

喬陽1,唐昊1,程文娟2,江琦1,馬學(xué)森2

(1.合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院,安徽 合肥230009; 2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥230009)

文章研究了無線傳感器網(wǎng)絡(luò)中存在的多條最短路徑路由選擇問題。將無線傳感器網(wǎng)絡(luò)看作多Agent系統(tǒng),采用強(qiáng)化學(xué)習(xí)理論,提出了一種基于多Agent強(qiáng)化學(xué)習(xí)的無線傳感器網(wǎng)絡(luò)多路徑路由協(xié)議MRL-MPRP(Multi-agent Reinforcement Learning based Multiple-path Routing Protocol)。該協(xié)議綜合考慮了所要發(fā)送數(shù)據(jù)的優(yōu)先級、節(jié)點(diǎn)間的鏈路質(zhì)量以及節(jié)點(diǎn)數(shù)據(jù)緩沖隊(duì)列的擁堵情況,為不同優(yōu)先級的數(shù)據(jù)選擇出當(dāng)前網(wǎng)絡(luò)狀況下最優(yōu)的路徑進(jìn)行數(shù)據(jù)的傳輸。仿真結(jié)果表明了該協(xié)議在降低網(wǎng)絡(luò)平均端—端延時(shí)、提升數(shù)據(jù)包成功投遞率方面的有效性。

無線傳感器網(wǎng)絡(luò);多路徑路由協(xié)議;多Agent系統(tǒng);強(qiáng)化學(xué)習(xí)

無線傳感器網(wǎng)絡(luò)是一種面向任務(wù)的網(wǎng)絡(luò),在環(huán)境監(jiān)測、電力系統(tǒng)監(jiān)控、地震監(jiān)測等應(yīng)用中,節(jié)點(diǎn)所采集到的數(shù)據(jù)重要性各不相同,一些異常數(shù)據(jù)(如溫度過高)通常反映了被監(jiān)控系統(tǒng)所出現(xiàn)的反常現(xiàn)象,需要確保能夠及時(shí)、準(zhǔn)確地傳送至控制中心,對延時(shí)、數(shù)據(jù)投遞成功率等網(wǎng)絡(luò)性能都提出了較高的要求[1-2]。在傳統(tǒng)的多路徑路由協(xié)議中,一些算法通過在最短路徑上傳輸優(yōu)先級較高的異常數(shù)據(jù),而在其他非最短路徑上傳輸優(yōu)先級較低的常規(guī)數(shù)據(jù)從而滿足不同數(shù)據(jù)對傳輸性能的要求[3-4]。文獻(xiàn)[5-7]也提出了幾種多路徑路由協(xié)議以保證網(wǎng)絡(luò)在傳輸數(shù)據(jù)時(shí)的服務(wù)質(zhì)量。

然而,由于無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)是通過自組織的方式相互連接的,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有高度動(dòng)態(tài)性,對某些節(jié)點(diǎn)的數(shù)據(jù)傳輸而言,網(wǎng)絡(luò)中可能同時(shí)存在多條跳數(shù)相同的最短路徑。受節(jié)點(diǎn)部署位置、傳輸干擾以及事件觸發(fā)頻率等環(huán)境因素的影響,這些路徑的鏈路狀況和擁堵情況具有差異性,其在傳輸數(shù)據(jù)時(shí)的服務(wù)質(zhì)量也各不相同。因此,需要根據(jù)網(wǎng)絡(luò)的實(shí)時(shí)動(dòng)態(tài)從多條最短路徑中為不同類型的數(shù)據(jù)尋找出相應(yīng)的最優(yōu)路徑進(jìn)行數(shù)據(jù)的傳輸,尤其是那些優(yōu)先級較高的實(shí)時(shí)數(shù)據(jù)。

針對上述問題,本文提出了一種基于多Agent強(qiáng)化學(xué)習(xí)的無線傳感器網(wǎng)絡(luò)多路徑路由協(xié)議MRL-MPRP (Multi-agent Reinforcement Learning based Multiple-path Routing Protocol)。將無線傳感器網(wǎng)絡(luò)看作1個(gè)多Agent系統(tǒng),網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都是1個(gè)具有獨(dú)立學(xué)習(xí)能力的智能體 (Agent),節(jié)點(diǎn)在路由選擇時(shí),考慮所發(fā)送數(shù)據(jù)的優(yōu)先級、與各鄰居節(jié)點(diǎn)之間的鏈路質(zhì)量以及各鄰居節(jié)點(diǎn)數(shù)據(jù)緩沖隊(duì)列長度等網(wǎng)絡(luò)實(shí)時(shí)信息。同時(shí),采用強(qiáng)化學(xué)習(xí)理論,將高優(yōu)先級數(shù)據(jù)的路由選擇過程建模為Markov決策過程,并引入基于分布式值函數(shù)的Q學(xué)習(xí)算法求解最優(yōu)路徑,通過節(jié)點(diǎn)間的局部信息交互實(shí)現(xiàn)全局最優(yōu)。

1　網(wǎng)絡(luò)模型

1.1節(jié)點(diǎn)模型

將節(jié)點(diǎn)采集到的數(shù)據(jù)和接收到的數(shù)據(jù)統(tǒng)稱為到達(dá)節(jié)點(diǎn)的數(shù)據(jù),分為高、低2個(gè)優(yōu)先級。同時(shí),假設(shè)節(jié)點(diǎn)自身采集的數(shù)據(jù)是隨機(jī)到達(dá)的,高、低優(yōu)先級數(shù)據(jù)的到達(dá)間隔分別服從參數(shù)為λ1和λ2的指數(shù)分布,數(shù)據(jù)包大小均為C。假設(shè)每個(gè)節(jié)點(diǎn)均配備一個(gè)緩沖隊(duì)列,用于存放到達(dá)節(jié)點(diǎn)的數(shù)據(jù),隊(duì)列的容量為M,數(shù)據(jù)放入緩沖隊(duì)列后等待傳輸,若數(shù)據(jù)到達(dá)時(shí)緩沖隊(duì)列已滿,則丟棄相應(yīng)的數(shù)據(jù)包。隊(duì)列中的數(shù)據(jù)按照“先進(jìn)先出”原則發(fā)送,即發(fā)送順序與優(yōu)先級無關(guān)。

1.2信道模型

在數(shù)據(jù)傳輸時(shí),對于衰落信道而言,信號通過無線信道后,其幅值是隨機(jī)的,假設(shè)節(jié)點(diǎn)接收到的瞬時(shí)信噪比(signal-to-noise ratio,SNR)A呈指數(shù)分布。令0=A0

2　MRL-MPRP協(xié)議

2.1協(xié)議工作機(jī)制

在上述網(wǎng)絡(luò)模型下,考慮一個(gè)有N個(gè)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò),假設(shè)節(jié)點(diǎn)的路由表中已保存到終端節(jié)點(diǎn)的所有最短路徑。當(dāng)節(jié)點(diǎn)i的數(shù)據(jù)緩沖隊(duì)列不為空,即節(jié)點(diǎn)i有通信需求時(shí)則啟動(dòng)路由發(fā)現(xiàn)機(jī)制,具體過程如下:

若所要發(fā)送的數(shù)據(jù)優(yōu)先級為高,則向其路由表中保存的所有下一跳鄰居節(jié)點(diǎn)(在文中均指最短路徑上的下一跳節(jié)點(diǎn))組播路由請求包RREQ。鄰居節(jié)點(diǎn)收到RREQ消息后,會根據(jù)接收信號強(qiáng)度,計(jì)算自身與發(fā)送節(jié)點(diǎn)之間的鏈路質(zhì)量,同時(shí)讀取自身的緩沖隊(duì)列長度,然后向節(jié)點(diǎn)i發(fā)送路由應(yīng)答信息包RREP,并在RREP消息中附上上述鏈路質(zhì)量和緩沖隊(duì)列長度。發(fā)送節(jié)點(diǎn)i在收到所有鄰居節(jié)點(diǎn)回送的RREQ消息后,根據(jù)自身與各鄰居節(jié)點(diǎn)之間的鏈路質(zhì)量、鄰居節(jié)點(diǎn)的隊(duì)列長度做出決策,從鄰居節(jié)點(diǎn)中選擇符合要求的1個(gè)作為下一跳節(jié)點(diǎn),并發(fā)送數(shù)據(jù)。若發(fā)送數(shù)據(jù)的優(yōu)先級為低,節(jié)點(diǎn)從路由表中隨機(jī)挑選1個(gè)鄰居作為下一跳節(jié)點(diǎn)。

鄰居節(jié)點(diǎn)j在收到節(jié)點(diǎn)i發(fā)送的數(shù)據(jù)后,若緩沖隊(duì)列不為滿,則將數(shù)據(jù)包放入隊(duì)列,并向節(jié)點(diǎn)i發(fā)送確認(rèn)字符(ACK)消息;若隊(duì)列已滿,則丟棄相應(yīng)的數(shù)據(jù)包,并向節(jié)點(diǎn)i發(fā)送否定確認(rèn)(NACK)消息;若節(jié)點(diǎn)i在一段時(shí)間后既未收到ACK也未收到NACK消息,則認(rèn)為數(shù)據(jù)包在傳輸過程中丟失,重新發(fā)送數(shù)據(jù)包直至收到確認(rèn)信息(ACK、NACK)或者達(dá)到最大重傳次數(shù)為止,此時(shí)認(rèn)為當(dāng)前數(shù)據(jù)包的發(fā)送已完成。隨后,節(jié)點(diǎn)i會檢查自身的緩沖隊(duì)列,若隊(duì)列中有數(shù)據(jù)包,則進(jìn)入下一數(shù)據(jù)包的路由選擇過程；否則,節(jié)點(diǎn)i一直等待直到下一個(gè)數(shù)據(jù)包到達(dá)。

2.2數(shù)學(xué)建模

對高優(yōu)先級數(shù)據(jù)的路由選擇過程,采用多Agent強(qiáng)化學(xué)習(xí)理論來實(shí)現(xiàn),將其建立為一個(gè)馬爾可夫決策過程(Markov decision process,MDP)模型[9]。并引入基于分布式值函數(shù)的Q學(xué)習(xí)算法來求解最優(yōu)路徑,通過僅與通信范圍內(nèi)的鄰居節(jié)點(diǎn)進(jìn)行局部信息交互實(shí)現(xiàn)全局最優(yōu)[10]。節(jié)點(diǎn)i第n次高優(yōu)先級數(shù)據(jù)路由選擇的MDP過程可定義如下。

(1)

(2)

其中,chj表示節(jié)點(diǎn)i選擇節(jié)點(diǎn)j為下一跳節(jié)點(diǎn),并發(fā)送數(shù)據(jù)。

(3) 代價(jià)函數(shù)。若被選節(jié)點(diǎn)j成功收到節(jié)點(diǎn)i發(fā)送的數(shù)據(jù)包,則會在回送的ACK消息中附上數(shù)據(jù)到達(dá)節(jié)點(diǎn)j的時(shí)刻。節(jié)點(diǎn)i根據(jù)ttx=tarrival-tleaving計(jì)算該高優(yōu)先級數(shù)據(jù)包傳輸所經(jīng)歷的延時(shí),其中tleaving為數(shù)據(jù)包離開節(jié)點(diǎn)i的時(shí)刻。節(jié)點(diǎn)i在一次高優(yōu)先級數(shù)據(jù)傳輸中的立即代價(jià)定義如下:

(3)

(4)Q值更新。節(jié)點(diǎn)i在獲得立即代價(jià)后,使用基于分布式值函數(shù)的Q學(xué)習(xí)算法更新當(dāng)前狀態(tài)-行動(dòng)對的Q值,更新公式為:

(4)

其中,α為學(xué)習(xí)率;γ為折扣因子;ω(i,j)為節(jié)點(diǎn)i從被選節(jié)點(diǎn)j獲得的長遠(yuǎn)代價(jià)的權(quán)重;ω(i,i′)為節(jié)點(diǎn)i從其他鄰居節(jié)點(diǎn)獲得的長遠(yuǎn)代價(jià)的權(quán)重。

3　仿真實(shí)驗(yàn)及結(jié)果分析

本文以O(shè)MNET++4.0作為實(shí)驗(yàn)仿真平臺,驗(yàn)證所提出的MRL-MPRP協(xié)議對網(wǎng)絡(luò)性能的影響。假設(shè)45個(gè)節(jié)點(diǎn)隨機(jī)分布在200 m×200 m的區(qū)域內(nèi),網(wǎng)關(guān)節(jié)點(diǎn)處于區(qū)域的中心,節(jié)點(diǎn)的通信距離為50 m。其他主要仿真參數(shù)設(shè)置如下:仿真時(shí)間t=1 600 s,數(shù)據(jù)包大小C=100 bit,隊(duì)列容量M=4,鏈路狀態(tài)數(shù)H=3,傳輸速率Rtx=100 kb/s,傳輸功率Ptx=4 mW,高、低優(yōu)先級數(shù)據(jù)包到達(dá)間隔λ1、λ2均為15 ms。

高、低2個(gè)優(yōu)先級數(shù)據(jù)包的平均傳輸端—端延時(shí)如圖1所示。由圖1可以看出,隨著仿真的運(yùn)行,高優(yōu)先級數(shù)據(jù)包的平均傳輸端—端延時(shí)呈下降趨勢,至仿真結(jié)束時(shí),其延時(shí)比仿真初始階段下降約15%,而低優(yōu)先級數(shù)據(jù)包的平均端—端延時(shí)則在仿真過程中無明顯變化,且其波動(dòng)相對較大。這說明所提出的MRL-MPRP協(xié)議可以有效減少高優(yōu)先級數(shù)據(jù)的傳輸延時(shí)。

網(wǎng)絡(luò)中的節(jié)點(diǎn)在一跳傳輸中成功發(fā)送1個(gè)高、低優(yōu)先級數(shù)據(jù)包所需重傳的平均次數(shù)如圖2所示。

圖1　高、低優(yōu)先級數(shù)據(jù)包平均傳輸端—端延時(shí)

圖2　節(jié)點(diǎn)成功發(fā)送1個(gè)數(shù)據(jù)包所需重傳次數(shù)

從圖2可以看出,隨著仿真的進(jìn)行,所選節(jié)點(diǎn)成功發(fā)送高優(yōu)先級數(shù)據(jù)包所需重傳的次數(shù)逐漸降低,且最終的值明顯低于低優(yōu)先級數(shù)據(jù)。這是因?yàn)镸RL-MPRP協(xié)議在發(fā)送高優(yōu)先級數(shù)據(jù)優(yōu)先級時(shí),考慮節(jié)點(diǎn)之間的鏈路質(zhì)量,在鏈路質(zhì)量較好的路徑中傳輸數(shù)據(jù)可以有效提高數(shù)據(jù)包發(fā)送成功的概率,因此其失敗重傳的次數(shù)會降低。

高、低2個(gè)優(yōu)先級數(shù)據(jù)包的投遞成功率曲線如圖3所示。由圖3可以看出,在仿真過程中,高優(yōu)先級數(shù)據(jù)包的投遞成功率逐漸增大,而低優(yōu)先級數(shù)據(jù)的投遞成功率則變化不大,統(tǒng)計(jì)意義上來說,略有提高;且高優(yōu)先級數(shù)據(jù)的投遞成功率明顯高于低優(yōu)先級數(shù)據(jù),最終約高出10.4%。這說明所提出的MRL-MPRP協(xié)議可以有效提高高優(yōu)先級數(shù)據(jù)包的投遞成功率。

高優(yōu)先級數(shù)據(jù)包的投遞成功率與數(shù)據(jù)包產(chǎn)生間隔時(shí)間之間的關(guān)系如圖4所示。

圖3　高、低優(yōu)先級數(shù)據(jù)包投遞成功率對比曲線

圖4　不同到達(dá)間隔時(shí)間下高優(yōu)先級數(shù)據(jù)包投遞成功率

從圖4可以看出,在每個(gè)間隔時(shí)間下,仿真結(jié)束時(shí)的投遞成功率都比仿真開始時(shí)有一定程度的提升,最高可提升12% 左右(間隔50 ms時(shí))。這說明所提出的MRL-MPRP協(xié)議對不同流量強(qiáng)度的網(wǎng)絡(luò)均有不同程度的適應(yīng)性。

4　結(jié)　論

本文研究了無線傳感器網(wǎng)絡(luò)的多條最短路徑尋優(yōu)問題,將無線傳感器網(wǎng)絡(luò)作為一個(gè)多Agent系統(tǒng),提出了一種基于多Agent強(qiáng)化學(xué)習(xí)的多路徑路由協(xié)議MRL-MPRP。若發(fā)送的是高優(yōu)先級數(shù)據(jù),協(xié)議綜合考慮發(fā)送節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間鏈路的質(zhì)量以及鄰居節(jié)點(diǎn)隊(duì)列中數(shù)據(jù)包數(shù)量等影響路徑質(zhì)量的因素,將路由選擇過程建模為Markov決策過程,并使用分布式值函數(shù)算法求解當(dāng)前網(wǎng)絡(luò)狀況下的最優(yōu)路徑。若發(fā)送的是低優(yōu)先級數(shù)據(jù),則在路由表中隨機(jī)選擇一條最短路徑發(fā)送。仿真結(jié)果表明，該協(xié)議能夠有效降低高優(yōu)先級數(shù)據(jù)包的端—端延時(shí)、提高數(shù)據(jù)包投遞成功率,且對不同流量強(qiáng)度的網(wǎng)絡(luò)均有一定的適用性。

[1]王文光,劉士興,謝武軍.無線傳感器網(wǎng)絡(luò)概述[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,33(9):1416-1419,1437.

[2]MITCHELL R,CHEN I R.A survey of intrusion detection in wireless sensor network applications[J].Computer Communications,2014,42:1-23.

[3]RADI M,DEZFOULI B,BAKAR K.Multipath routing in wireless sensor networks:survey and research challenges[J].Sensors,2012,12(1):650-685.

[4]KOGA Y,SUGIMOTO C,KOHNO R.Congestion control routing protocol using priority control for ad-hoc networks in an emergency[C]//12th International Conference on ITS Telecommunications,Taipei,Taiwan,2012:45-49.

[5]ZHANG Y J,YAN T,TIAN J.TOHIP:a topology-hiding multipath routing protocol in mobile ad hoc networks[J].Ad Hoc Networks,2014,21:109-122.

[6]公維冰,陽小龍,張敏.基于細(xì)胞適應(yīng)機(jī)制的自組網(wǎng)多路徑路由協(xié)議[J].通信學(xué)報(bào),2014,35(6):56-63.

[7]CHANAK P,BANERJEE I.Energy efficient fault-tolerant multipath routing scheme for wireless sensor networks[J].The Journal of China Universities of Posts and Telecommunications,2013,20(6):42-48.

[8]SADEGHI P,KENNEDY R,RAPAJIC P.Finite-state Markov modeling of fading channels:a survey of principles and applications[J].IEEE Signal Processing Magazine,2008,25(5):57-80.

[9]唐昊,萬海峰,韓江洪.基于多Agent強(qiáng)化學(xué)習(xí)的多站點(diǎn)CSPS系統(tǒng)的協(xié)作Look-ahead控制[J].自動(dòng)化學(xué)報(bào),2010,36(2):289-296.

[10]SHIRAZI G N,KONG P Y,THAM C K.Distributed reinforcement learning frameworks for cooperative retransmission in wireless networks[J].IEEE Transactions on Vehicular Technology,2010,59(8):4157-4162.

(責(zé)任編輯張淑艷)

A multiple-path routing protocol in wireless sensor network based on multi-agent reinforcement learning

QIAO Yang1,TANG Hao1,CHENG Wenjuan2,JIANG Qi1,MA Xuesen2

(1.School of Electric Engineering and Automation, Hefei University of Technology, Hefei 230009, China; 2.School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

In this paper, the optimal route selection problem in the case of several shortest paths with the same hops in wireless sensor networks is considered. A multi-agent reinforcement learning based multiple-path routing protocol(MRL-MPRP) is proposed by regarding wireless sensor network as a multi-agent system. In MRL-MPRP, the sensor node takes the priority of the transmitting data, link quality and congestion of different neighbors into consideration so as to select an optimal route for sending different types of data. The simulation results show that the proposed protocol effectively reduces the end-to-end delay and increases the packet delivery ratio.

wireless sensor network; multiple-path routing protocol; multi-agent system; reinforcement learning

2015-03-13；

2015-04-30

國家自然科學(xué)基金資助項(xiàng)目(61174186;61374158;71231004;51274078);教育部新世紀(jì)優(yōu)秀人才計(jì)劃資助項(xiàng)目(NCET-11-0626)和高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20130111110007)

喬陽(1990-),男,安徽淮北人,合肥工業(yè)大學(xué)碩士生;

唐昊(1972-),男,安徽廬江人,博士,合肥工業(yè)大學(xué)教授,博士生導(dǎo)師;

10.3969/j.issn.1003-5060.2016.07.007

TP181;TP212.9

A

1003-5060(2016)07-0896-04

程文娟(1970-),女,安徽懷寧人,博士,合肥工業(yè)大學(xué)教授,碩士生導(dǎo)師.