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

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

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

?

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

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

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

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

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

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

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

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

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

1.1節(jié)點模型

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

1.2信道模型

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

2　MRL-MPRP協(xié)議

2.1協(xié)議工作機制

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

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

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

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

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

(1)

(2)

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

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

(3)

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

(4)

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

3　仿真實驗及結(jié)果分析

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

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

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

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

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

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

高、低2個優(yōu)先級數(shù)據(jù)包的投遞成功率曲線如圖3所示。由圖3可以看出,在仿真過程中,高優(yōu)先級數(shù)據(jù)包的投遞成功率逐漸增大,而低優(yōu)先級數(shù)據(jù)的投遞成功率則變化不大,統(tǒng)計意義上來說,略有提高;且高優(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)生間隔時間之間的關(guān)系如圖4所示。

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

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

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

4　結(jié)　論

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

[1]王文光,劉士興,謝武軍.無線傳感器網(wǎng)絡(luò)概述[J].合肥工業(yè)大學(xué)學(xué)報(自然科學(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)機制的自組網(wǎng)多路徑路由協(xié)議[J].通信學(xué)報,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強化學(xué)習(xí)的多站點CSPS系統(tǒng)的協(xié)作Look-ahead控制[J].自動化學(xué)報,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é)基金資助項目(61174186;61374158;71231004;51274078);教育部新世紀(jì)優(yōu)秀人才計劃資助項目(NCET-11-0626)和高等學(xué)校博士學(xué)科點專項科研基金資助項目(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)師.