,,

(1.南瑞集團(tuán)有限公司(國(guó)網(wǎng)電力科學(xué)研究院有限公司)，南京 211106; 2.北京科東電力控制系統(tǒng)有限責(zé)任公司，北京 100192)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議負(fù)責(zé)確定源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的優(yōu)化路徑以及沿優(yōu)化路徑正確轉(zhuǎn)發(fā)數(shù)據(jù)[1]。面向固定匯聚節(jié)點(diǎn)的路由方法已經(jīng)得到了廣泛的研究，由于能耗均衡的需求和移動(dòng)設(shè)施的普及，在大量應(yīng)用中需要采用移動(dòng)匯聚節(jié)點(diǎn)對(duì)監(jiān)測(cè)區(qū)域的數(shù)據(jù)進(jìn)行采集[2-4]，所設(shè)計(jì)的路由機(jī)制需要適應(yīng)由于匯聚節(jié)點(diǎn)移動(dòng)帶來的網(wǎng)絡(luò)狀態(tài)的不斷變化[2]。傳感器節(jié)點(diǎn)的能量限制要求路由方法考慮節(jié)約能量和均衡能耗以延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間；由于傳感器節(jié)點(diǎn)具備有限的資源和通信帶寬，路由算法應(yīng)該簡(jiǎn)單高效，占用盡可能少的計(jì)算、存儲(chǔ)和通信資源；路由過程同時(shí)需要對(duì)數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性和投遞率等服務(wù)質(zhì)量進(jìn)行優(yōu)化[5]。

近年來，國(guó)內(nèi)外研究者對(duì)移動(dòng)匯聚節(jié)點(diǎn)的研究進(jìn)行了很大關(guān)注[2]。文獻(xiàn)[6]研究了雙層數(shù)據(jù)發(fā)布(TTDD)協(xié)議，通過將無(wú)線傳感器網(wǎng)絡(luò)分割為多個(gè)單元實(shí)現(xiàn)向多個(gè)移動(dòng)匯聚節(jié)點(diǎn)的數(shù)據(jù)傳輸；然而，當(dāng)網(wǎng)絡(luò)數(shù)據(jù)傳輸率增大時(shí)，TTDD的開銷會(huì)變得非常大，因此其更適用于低負(fù)載和網(wǎng)絡(luò)流量的場(chǎng)景。文獻(xiàn)[7]提出了基于分簇的路由方法，簇頭節(jié)點(diǎn)聚合時(shí)空關(guān)聯(lián)數(shù)據(jù)并將其轉(zhuǎn)發(fā)至合適的終端節(jié)點(diǎn)，終端節(jié)點(diǎn)作為代理節(jié)點(diǎn)位于移動(dòng)匯聚節(jié)點(diǎn)的軌跡附近；然而，基于代理的方法會(huì)帶來很大的時(shí)延，且成本較高，對(duì)分簇的假定也不適用于無(wú)線傳感器網(wǎng)絡(luò)的一般應(yīng)用場(chǎng)景。文獻(xiàn)[8]提出了一種基于地理位置的服務(wù)和路由方法。每當(dāng)鏈路狀況發(fā)生改變時(shí)，匯聚節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都會(huì)更新位置信息，該路由方法假定所有傳感器節(jié)點(diǎn)都具備定位單元，頻繁的位置更新也增加了路由的開銷。

上述路由方法自適應(yīng)性不足，為使路由方法適應(yīng)快速變化的網(wǎng)絡(luò)狀況，很多研究集中在了強(qiáng)化學(xué)習(xí)技術(shù)的應(yīng)用[9]。為提升網(wǎng)絡(luò)狀態(tài)變化時(shí)的路由效率，Boyan和Littman首次將強(qiáng)化學(xué)習(xí)技術(shù)應(yīng)用到數(shù)據(jù)包的路由問題中，并提出了一種Q-路由方法[10]。由于強(qiáng)化學(xué)習(xí)具有簡(jiǎn)單性、自適應(yīng)性和魯棒性等特征[11]，非常適用于無(wú)線傳感器網(wǎng)絡(luò)的路由問題[12]。文獻(xiàn)[13]基于強(qiáng)化學(xué)習(xí)方法提出了一種多播路由框架以高效的處理具有多個(gè)移動(dòng)匯聚節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)路由過程中的多播和移動(dòng)性問題。上述方法適用于匯聚節(jié)點(diǎn)低速到中速的移動(dòng)場(chǎng)景。文獻(xiàn)[14]基于強(qiáng)化學(xué)習(xí)技術(shù)提出了一種適用于移動(dòng)AD Hoc網(wǎng)絡(luò)的主動(dòng)路由協(xié)議，該方法可以最大化節(jié)點(diǎn)生存時(shí)間和快速適應(yīng)由于節(jié)點(diǎn)移動(dòng)帶來的網(wǎng)絡(luò)拓?fù)渥兓?；該方法針?duì)移動(dòng)AD Hoc網(wǎng)絡(luò)并且假定所有的節(jié)點(diǎn)都具備GPS設(shè)備，不適用于無(wú)線傳感器網(wǎng)絡(luò)的一般應(yīng)用場(chǎng)景。

可見，強(qiáng)化學(xué)習(xí)是處理無(wú)線傳感器網(wǎng)絡(luò)路由問題中節(jié)點(diǎn)移動(dòng)性和自適應(yīng)性的有效方法。針對(duì)當(dāng)前方案不具備通用性和不能充分支持無(wú)線傳感器網(wǎng)絡(luò)高度自適應(yīng)性的不足，需要綜合考慮時(shí)延、投遞率和網(wǎng)絡(luò)生存時(shí)間等多個(gè)指標(biāo)以獲取最優(yōu)的網(wǎng)絡(luò)性能。本文提出一種基于強(qiáng)化學(xué)習(xí)的支持移動(dòng)匯聚節(jié)點(diǎn)的自適應(yīng)路由方法(learning based routing supporting mobile sink, LRMS)。建立路由問題基于強(qiáng)化學(xué)習(xí)的模型，并設(shè)計(jì)綜合考慮跳數(shù)、鏈路質(zhì)量和能量分布的獎(jiǎng)賞函數(shù)對(duì)無(wú)線傳感器網(wǎng)絡(luò)的時(shí)延、投遞率以及生存時(shí)間進(jìn)行優(yōu)化。理論和仿真評(píng)估驗(yàn)證了LRMS在無(wú)線傳感器網(wǎng)絡(luò)面向移動(dòng)匯聚節(jié)點(diǎn)自適應(yīng)路由問題中的可行性和優(yōu)越性。

1 路由模型建立

Q學(xué)習(xí)(Q-Learning, QL)[15]由Watkins在1989年提出，是馬爾科夫環(huán)境下的模型無(wú)關(guān)的強(qiáng)化學(xué)習(xí)方法，對(duì)傳感器節(jié)點(diǎn)的計(jì)算和存儲(chǔ)資源有著中等的要求[11]，可用于解決無(wú)線傳感器網(wǎng)絡(luò)的路由問題[12]。在給定策略π下，Q學(xué)習(xí)的每個(gè)狀態(tài)/行動(dòng)(st,at)都會(huì)對(duì)應(yīng)一個(gè)Q值函數(shù)Qπ(st,at)用于表示在狀態(tài)st下采取行動(dòng)at的累計(jì)獎(jiǎng)賞情況。Q值用于評(píng)價(jià)特定狀態(tài)下采取某個(gè)行動(dòng)的優(yōu)劣。

在Q學(xué)習(xí)中，agent可以通過不斷試錯(cuò)和有延遲的獎(jiǎng)賞獲得最優(yōu)的行動(dòng)策略。Q學(xué)習(xí)算法的核心是通過迭代更新Q值以獲取最優(yōu)的行動(dòng)策略，更新過程定義如下式所示。

Q(st,at)←Q(st,at)(1-α)+

(1)

1.1 基于Q學(xué)習(xí)的路由模型

假定無(wú)線傳感器網(wǎng)絡(luò)由p個(gè)傳感器節(jié)點(diǎn)和一個(gè)移動(dòng)匯聚節(jié)點(diǎn)組成。在每個(gè)節(jié)點(diǎn)內(nèi)實(shí)現(xiàn)基于Q學(xué)習(xí)的路由算法，將節(jié)點(diǎn)將要發(fā)送或轉(zhuǎn)發(fā)的數(shù)據(jù)包作為agent，通過Q表的查詢選擇具備最大Q值的路徑將數(shù)據(jù)傳輸?shù)絽R聚節(jié)點(diǎn)。路由模型中Q學(xué)習(xí)的狀態(tài)、行動(dòng)、Q值以及Q值的更新過程分別定義如下。

(1)狀態(tài)：V={v1,v2,…,vp}為無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的集合，S={s1,s2,…,sp}為agent狀態(tài)的集合。當(dāng)數(shù)據(jù)包在第i個(gè)節(jié)點(diǎn)vi時(shí)，相關(guān)的數(shù)據(jù)包狀態(tài)為si。

(2)行動(dòng)：Vi={v1,v2,…,vk}為傳感器節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合，各鄰居節(jié)點(diǎn)對(duì)應(yīng)的狀態(tài)集合為Si={s1,s2,…,sk}。則定義agent在狀態(tài)si下可采取的行動(dòng)集合為Ai={a1,a2,…,ak}，其中aj∈Ai表示將數(shù)據(jù)包從si轉(zhuǎn)發(fā)至鄰居節(jié)點(diǎn)sj，當(dāng)采取行動(dòng)aj之后，agent狀態(tài)轉(zhuǎn)為sj。

(3)Q值：Q值代表在各狀態(tài)下采取每個(gè)行動(dòng)的優(yōu)劣，當(dāng)數(shù)據(jù)包狀態(tài)為si時(shí)，行動(dòng)aj對(duì)應(yīng)的Q值為Q(si,aj)，表示通過采取行動(dòng)aj將數(shù)據(jù)包從si轉(zhuǎn)發(fā)至sj的質(zhì)量。

(4)Q值更新：為避免學(xué)習(xí)率過低帶來的延遲，將學(xué)習(xí)率α設(shè)置為1以加速學(xué)習(xí)過程。當(dāng)從sj接收到獎(jiǎng)賞信息后，狀態(tài)/行動(dòng)(si,aj)的Q值將按以下公式進(jìn)行更新。

(2)

1.2 獎(jiǎng)賞函數(shù)設(shè)計(jì)

獎(jiǎng)賞函數(shù)需要考慮時(shí)延、投遞率以及能耗均衡等優(yōu)化目標(biāo)以獲取最優(yōu)的整體網(wǎng)絡(luò)性能。時(shí)延主要由數(shù)據(jù)包從源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)經(jīng)過的跳數(shù)決定，能耗均衡可以由各節(jié)點(diǎn)剩余能量的分布決定，數(shù)據(jù)傳輸?shù)耐哆f率則直接受鏈路質(zhì)量的影響，鏈路質(zhì)量可以通過接收信號(hào)強(qiáng)度(RSS)計(jì)算得到。因此，獎(jiǎng)賞函數(shù)需要考慮剩余跳數(shù)、剩余能量以及RSS三個(gè)指標(biāo)。

當(dāng)數(shù)據(jù)包通過采取行動(dòng)aj從si傳遞到sj時(shí)，環(huán)境對(duì)狀態(tài)/行動(dòng)(si,aj)的獎(jiǎng)賞r(aj)為sj對(duì)si的即時(shí)反饋。獎(jiǎng)賞函數(shù)設(shè)計(jì)如下：

r(aj)=w1·H(sj)+w2·E(sj)+w3·L(sj)

(3)

其中:H(sj)、E(sj)和L(sj)分別為剩余跳數(shù)、剩余能量和RSS的歸一化值，w1、w2和w3為對(duì)應(yīng)的權(quán)重。H(sj)、E(sj)和L(sj)的定義如下：

(4)

Hrem(sj)為節(jié)點(diǎn)sj中記錄的距離匯聚節(jié)點(diǎn)的剩余跳數(shù)，Hmax(sj)為無(wú)線傳感器網(wǎng)絡(luò)中的最大可能跳數(shù)。均方根可避免H(sj)取值過小以拉低獎(jiǎng)賞函數(shù)的總值。Eres(sj)和Einit(sj)分別為節(jié)點(diǎn)sj的剩余能量和初始能量，所有節(jié)點(diǎn)具有相同的初始能量Einit(sj)。PRx(sj)為sj的RSS，單位為dBm。由于無(wú)線傳感器網(wǎng)絡(luò)的通信協(xié)議為短距離通信協(xié)議，其傳輸功率較低，同時(shí)由于路徑損耗的存在，PRx(sj)的值為負(fù)數(shù)。因此，RSS的絕對(duì)值越小，說明信號(hào)強(qiáng)度越大，鏈路質(zhì)量越好。Pmin為RSS可能取得的最小值，單位為dBm。此處，將傳感器節(jié)點(diǎn)的接收靈敏度設(shè)置為-100 dBm，可知RSS的實(shí)際取值必大于-100。將Pmin設(shè)置為-200 dBm以避免L(sj)的取值過小。

2 基于強(qiáng)化學(xué)習(xí)的路由方法設(shè)計(jì)

2.1 報(bào)文結(jié)構(gòu)設(shè)計(jì)

路由信息更新及數(shù)據(jù)傳輸都有賴于攜帶用戶數(shù)據(jù)以及獎(jiǎng)賞信息的報(bào)文交換。通用報(bào)文結(jié)構(gòu)如圖1所述，包括包頭和載荷。包頭可分為3個(gè)區(qū)域：報(bào)文信息域，獎(jiǎng)賞信息域，路由信息域。載荷區(qū)域?yàn)榭蛇x區(qū)域，包含報(bào)文所攜帶的應(yīng)用層用戶數(shù)據(jù)，通常為傳感器節(jié)點(diǎn)采集的參數(shù)或控制命令。

圖1 報(bào)文結(jié)構(gòu)

2.2 路由表初始化

為滿足應(yīng)用的實(shí)時(shí)性，傳感器節(jié)點(diǎn)到移動(dòng)匯聚節(jié)點(diǎn)的初始路徑必須在很短的時(shí)間內(nèi)建立。然而，當(dāng)直接應(yīng)用無(wú)模型的Q學(xué)習(xí)時(shí)，由于需要對(duì)每個(gè)狀態(tài)進(jìn)行頻繁的隨機(jī)搜索，Q值收斂速度非常慢，會(huì)造成路由建立初始階段的較大時(shí)延，不能滿足應(yīng)用的實(shí)時(shí)性需求。因此，此處采用匯聚節(jié)點(diǎn)聲明為每個(gè)狀態(tài)/行動(dòng)建立初始Q值從而快速建立初始路徑。

在初始階段，傳感器節(jié)點(diǎn)中存儲(chǔ)的所有Q值均初始化為0，匯聚節(jié)點(diǎn)的最大Q值初始化為1。當(dāng)匯聚節(jié)點(diǎn)進(jìn)入無(wú)線傳感器網(wǎng)絡(luò)范圍，會(huì)立即發(fā)送廣播到整個(gè)網(wǎng)絡(luò)的控制包作為節(jié)點(diǎn)聲明過程。經(jīng)過初始化和匯聚節(jié)點(diǎn)聲明，各節(jié)點(diǎn)會(huì)建立到匯聚節(jié)點(diǎn)的初始路徑。

2.3 選擇最優(yōu)路徑

傳感器節(jié)點(diǎn)存儲(chǔ)一個(gè)Q表以記錄對(duì)應(yīng)每個(gè)鄰居節(jié)點(diǎn)的Q值，下一跳節(jié)點(diǎn)可以通過查表操作得到。如圖2示，{s1,s2,…,sk}為節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)的集合，{a1,a2,…,ak}為節(jié)點(diǎn)si可以采取的行動(dòng)的集合，每個(gè)行動(dòng)對(duì)應(yīng)一個(gè)鄰居節(jié)點(diǎn)。對(duì)應(yīng)于sj的Q值是Q(si,aj)。當(dāng)算法收斂，具備最大Q值的行動(dòng)將會(huì)被選擇為最優(yōu)的行動(dòng)。由于傳感器節(jié)點(diǎn)對(duì)每個(gè)鄰居節(jié)點(diǎn)都保持一個(gè)Q值，當(dāng)網(wǎng)絡(luò)狀況發(fā)生變化時(shí)，可以在不同的路徑之間實(shí)現(xiàn)快速轉(zhuǎn)換。

由于傳感器節(jié)點(diǎn)對(duì)正確接收到的數(shù)據(jù)包進(jìn)行確認(rèn)，確認(rèn)包的頭部包含獎(jiǎng)賞信息用以更新源節(jié)點(diǎn)中對(duì)應(yīng)的Q值。在數(shù)據(jù)傳輸過程中，參與發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)都會(huì)實(shí)時(shí)更新其Q表以及路由信息。數(shù)據(jù)傳輸過程中Q表的動(dòng)態(tài)更新可以進(jìn)一步保證LRMS的自適應(yīng)性和處理不斷變化的網(wǎng)絡(luò)環(huán)境。

圖2 據(jù)Q表選擇最優(yōu)路徑

2.4 移動(dòng)性管理

通過不斷學(xué)習(xí)網(wǎng)絡(luò)環(huán)境的變化，可從本質(zhì)上支持匯聚節(jié)點(diǎn)的移動(dòng)性，Q值會(huì)在學(xué)習(xí)過程中根據(jù)獎(jiǎng)賞函數(shù)進(jìn)行不斷更新。然而，由于匯聚節(jié)點(diǎn)的高速移動(dòng)，同時(shí)由于學(xué)習(xí)延遲的存在，在學(xué)習(xí)到最新路徑之前，當(dāng)前路徑可能會(huì)很快變得不再適用。因此，僅僅通過在線學(xué)習(xí)和隨機(jī)探索不能處理由于匯聚節(jié)點(diǎn)高速移動(dòng)帶來的網(wǎng)絡(luò)結(jié)構(gòu)快速變化。

為保證傳感器節(jié)點(diǎn)路由信息的快速更新，在匯聚節(jié)點(diǎn)中采用周期性的洪泛機(jī)制。移動(dòng)匯聚節(jié)點(diǎn)以間隔TFlood發(fā)送廣播到整個(gè)網(wǎng)絡(luò)的控制包。由于在控制包中含有獎(jiǎng)賞信息，每次洪泛過程中，所有節(jié)點(diǎn)都將更新其關(guān)于匯聚節(jié)點(diǎn)的路由信息。這樣，每個(gè)節(jié)點(diǎn)的路由表會(huì)根據(jù)最新的匯聚節(jié)點(diǎn)信息實(shí)現(xiàn)更新。在動(dòng)態(tài)的網(wǎng)絡(luò)中需要更短的洪泛周期TFlood，然而，頻繁的洪泛廣播會(huì)消耗更多的能量和產(chǎn)生更大的開銷。因此，需要設(shè)置合理的TFlood值以得到網(wǎng)絡(luò)開銷和反應(yīng)速度之間平衡。

除周期性洪泛，由于路徑損耗RSS與各節(jié)點(diǎn)之間距離直接相關(guān)[16]，當(dāng)匯聚節(jié)點(diǎn)距離較遠(yuǎn)時(shí)，RSS將會(huì)變小，對(duì)應(yīng)于匯聚節(jié)點(diǎn)的Q值會(huì)隨著距離的增大而變小。當(dāng)匯聚節(jié)點(diǎn)靠近時(shí)，對(duì)應(yīng)于匯聚節(jié)點(diǎn)的Q值會(huì)隨著距離的減小而增大。因此，匯聚節(jié)點(diǎn)的移動(dòng)性可以通過RSS檢測(cè)得到，并通過Q值的更新使數(shù)據(jù)包更加傾向于通過距離匯聚節(jié)點(diǎn)較近的節(jié)點(diǎn)傳送，從而進(jìn)一步保證匯聚節(jié)點(diǎn)移動(dòng)時(shí)數(shù)據(jù)包的可靠傳輸。

3 路由算法評(píng)估驗(yàn)證

3.1 算法理論分析

3.1.1 收斂性分析

Watkins和Dayan對(duì)Q學(xué)習(xí)的收斂性有如下證明：只要每個(gè)狀態(tài)下的所有行動(dòng)都被采樣，而且每個(gè)行動(dòng)/值都為離散表示，Q學(xué)習(xí)就會(huì)以概率1收斂[17]。假定無(wú)線傳感器網(wǎng)絡(luò)有p個(gè)傳感器節(jié)點(diǎn)和1個(gè)移動(dòng)匯聚節(jié)點(diǎn)，任一傳感器節(jié)點(diǎn)的單跳鄰居節(jié)點(diǎn)最多有k個(gè)，為使路由算法收斂，所有傳感器節(jié)點(diǎn)要采取的行動(dòng)數(shù)量最多為(p+1)×k次。本算法中，匯聚節(jié)點(diǎn)聲明和周期性洪泛過程采取的行動(dòng)總數(shù)為(p+1)×k，且所有可能行動(dòng)都被采樣，可保證路由收斂。

3.1.2 開銷分析

3.1.3 存儲(chǔ)和計(jì)算需求

每個(gè)傳感器節(jié)點(diǎn)需建立一個(gè)Q表用以存儲(chǔ)所有可能的行動(dòng)及其對(duì)應(yīng)的Q值，每個(gè)行動(dòng)和值分別用16比特的字來表示。對(duì)于有k個(gè)鄰居的傳感器節(jié)點(diǎn)來說，Q表所需的存儲(chǔ)量為32×k比特。獎(jiǎng)賞信息存儲(chǔ)需求為48比特。因此，傳感器節(jié)點(diǎn)總存儲(chǔ)需求為(32×k+48)比特。傳感器節(jié)點(diǎn)需要執(zhí)行計(jì)算操作以選擇路徑和更新Q值，選擇路徑所需的計(jì)算量是O(k)，更新Q值所需的基本運(yùn)算操作數(shù)量為常數(shù)，其計(jì)算需求為O(1)。綜上，LRMS中選擇路徑和更新Q值的總計(jì)算需求為O(k)。

根據(jù)以上分析，路由算法需要極小的存儲(chǔ)和計(jì)算資源，適用于存儲(chǔ)和計(jì)算資源受限的無(wú)線傳感器節(jié)點(diǎn)。

3.2 仿真環(huán)境設(shè)計(jì)

采用OMNeT++仿真環(huán)境評(píng)估路由性能。傳感器節(jié)點(diǎn)以復(fù)合模塊的形式實(shí)現(xiàn)，在應(yīng)用層中周期性的產(chǎn)生數(shù)據(jù)包以模擬傳感器節(jié)點(diǎn)的信息采集；在網(wǎng)絡(luò)層采用本文所述基于Q學(xué)習(xí)的路由算法為數(shù)據(jù)包選擇優(yōu)化路徑；MAC層和物理層采用符合IEEE 802.15.4標(biāo)準(zhǔn)的協(xié)議規(guī)范；在物理層加入能耗模型以模擬射頻模塊不同動(dòng)作的能量消耗。

無(wú)線傳感器網(wǎng)絡(luò)的仿真參數(shù)如表1所示。應(yīng)用層中以3 s為周期生成常規(guī)數(shù)據(jù)包，默認(rèn)的學(xué)習(xí)率和折扣因子分別設(shè)置為1.0和0.5；匯聚節(jié)點(diǎn)的洪泛周期為1 s；獎(jiǎng)賞函數(shù)中剩余跳數(shù)、剩余能量以及鏈路質(zhì)量的權(quán)重分別設(shè)置為-1.0、0.1和0.3；默認(rèn)的傳感器節(jié)點(diǎn)數(shù)量為16個(gè)；默認(rèn)的匯聚節(jié)點(diǎn)移動(dòng)速度為20 m/s；單次運(yùn)行的仿真持續(xù)時(shí)間為1 000 s。

表1 無(wú)線傳感器網(wǎng)絡(luò)的仿真參數(shù)設(shè)置

采用平均跳數(shù)、能量分布以及投遞率3個(gè)指標(biāo)評(píng)估算法性能。平均跳數(shù)用于評(píng)估數(shù)據(jù)包的時(shí)延，投遞率用于評(píng)估數(shù)據(jù)傳輸?shù)目煽啃?，能量分布用各?jié)點(diǎn)平均功耗的標(biāo)準(zhǔn)差表示，用于評(píng)估網(wǎng)絡(luò)生存時(shí)間。

3.3 算法性能評(píng)估

將3個(gè)指標(biāo)的仿真結(jié)果均歸一化到[0,1]范圍之內(nèi)。平均跳數(shù)和能量分布的歸一化值由各仿真結(jié)果分別除以其最大值得到，由于投遞率本身就在[0,1]范圍之內(nèi)，可以直接作為歸一化值使用。

圖3 不同網(wǎng)絡(luò)規(guī)模下的性能

圖3為傳感器節(jié)點(diǎn)數(shù)量以步長(zhǎng)4在12～32之間變化時(shí)的性能?？梢?，平均跳數(shù)和能量分布隨著網(wǎng)絡(luò)規(guī)模的增大而成比例的增大，這是由于源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的路徑長(zhǎng)度會(huì)隨著網(wǎng)絡(luò)規(guī)模的增大而變長(zhǎng)；投遞率的減小并不明顯。可見，LRMS具有很好的可擴(kuò)展性，并且在不同的網(wǎng)絡(luò)規(guī)模下均取得了較好的性能。

圖4分析了匯聚節(jié)點(diǎn)速度以步長(zhǎng)5 m/s在5～30 m/s之間變化時(shí)對(duì)網(wǎng)絡(luò)性能的影響?？梢?，隨著匯聚節(jié)點(diǎn)速度的增加，平均跳數(shù)和能量分布的改變不明顯，投遞率有輕微減??；即使速度達(dá)到30 m/s時(shí)仍然保持了較好的性能?？梢?，LRMS可適應(yīng)較高的匯聚節(jié)點(diǎn)速度。

圖4 不同匯聚節(jié)點(diǎn)速度下的性能

3.4 算法對(duì)比分析

為驗(yàn)證算法的優(yōu)越性，在不同的網(wǎng)絡(luò)規(guī)模和匯聚節(jié)點(diǎn)速度下對(duì)無(wú)線傳感器網(wǎng)絡(luò)的平均跳數(shù)、能量分布和投遞率進(jìn)行對(duì)比。在OMNeT++中實(shí)現(xiàn)樹狀路由(tree based routing, TBR)[18]以進(jìn)行對(duì)比分析，兩種路由協(xié)議采用相同的網(wǎng)絡(luò)參數(shù)以及初始化過程以保證對(duì)比的公平性。

圖5 不同網(wǎng)絡(luò)規(guī)模下的平均跳數(shù)

圖6 不同網(wǎng)絡(luò)規(guī)模下的能量分布

圖7 不同網(wǎng)絡(luò)規(guī)模下的投遞率

圖5～7為不同網(wǎng)絡(luò)規(guī)模下兩種方法的平均跳數(shù)、能量分布以及投遞率的對(duì)比。由圖5可知，隨著網(wǎng)絡(luò)規(guī)模的增大，兩種算法的平均跳數(shù)會(huì)成比例的增大，LRMS具備更小的時(shí)延。圖6說明，隨著網(wǎng)絡(luò)規(guī)模的增大，兩種方法的能量分布均有所增大，LRMS增長(zhǎng)速度比樹狀路由小，且LRMS的能量分布總是低于樹狀路由；說明LRMS能保證更為均衡的能耗和更長(zhǎng)的網(wǎng)絡(luò)生存時(shí)間。圖7說明，隨著網(wǎng)絡(luò)規(guī)模的增大，兩種方法的投遞率均有所降低，LRMS在不同的網(wǎng)絡(luò)規(guī)模下均具備更高的投遞率，說明了數(shù)據(jù)傳輸?shù)目煽啃?。綜上，基于LRMS的路由能夠更好的適應(yīng)變化的網(wǎng)絡(luò)規(guī)模。

如圖8～10所示為匯聚節(jié)點(diǎn)在不同速度下兩種方法的平均跳數(shù)、能量分布以及投遞率的對(duì)比。圖8說明，匯聚節(jié)點(diǎn)的速度變化對(duì)兩種算法的平均跳數(shù)影響不大，LRMS的平均跳數(shù)比樹狀路由的小。圖9說明，當(dāng)匯聚節(jié)點(diǎn)速度小于5 m/s時(shí)，兩種算法的能量分布相差不大，隨著匯聚節(jié)點(diǎn)速度的增大，樹狀路由的能量分布會(huì)急劇變壞，而LRMS則受匯聚節(jié)點(diǎn)速度的影響較小，說明LRMS具有更加均衡的能耗和更長(zhǎng)的網(wǎng)絡(luò)生存時(shí)間，且能夠更好的適應(yīng)匯聚節(jié)點(diǎn)速度的增大。圖10說明，當(dāng)匯聚節(jié)點(diǎn)速度小于10 m/s時(shí)，樹狀路由的投遞率比LRMS要好。隨著匯聚節(jié)點(diǎn)速度進(jìn)一步增大，樹狀路由的投遞率會(huì)急劇減小，而LRMS則只有輕微的降低；當(dāng)匯聚節(jié)點(diǎn)速度超過

圖8 不同匯聚節(jié)點(diǎn)速度下的平均跳數(shù)

圖9 不同匯聚節(jié)點(diǎn)速度下的能量分布

圖10 不同匯聚節(jié)點(diǎn)速度下的投遞率

20 m/s時(shí)，LRMS的投遞率相比樹狀路由具有非常明顯的優(yōu)勢(shì)。因此，LRMS可以更好地適應(yīng)匯聚節(jié)點(diǎn)速度的增大，更能適應(yīng)由于匯聚節(jié)點(diǎn)快速移動(dòng)帶來的網(wǎng)絡(luò)狀況的快速變化。

4 結(jié)論

為實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)面向移動(dòng)匯聚節(jié)點(diǎn)的數(shù)據(jù)傳輸，本文提出一種基于強(qiáng)化學(xué)習(xí)的支持移動(dòng)匯聚節(jié)點(diǎn)的自適應(yīng)路由方法(LRMS)?；赒學(xué)習(xí)建立路由模型作為L(zhǎng)RMS的基礎(chǔ)，設(shè)計(jì)了一種綜合的獎(jiǎng)賞函數(shù)以對(duì)路由過程中的時(shí)延、投遞率以及能耗均衡等多個(gè)性能指標(biāo)進(jìn)行優(yōu)化。通過不斷的學(xué)習(xí)網(wǎng)絡(luò)狀態(tài)，LRMS可以本質(zhì)上支持匯聚節(jié)點(diǎn)的移動(dòng)性。理論分析表明LRMS具備快速收斂、低開銷、存儲(chǔ)計(jì)算需求低等特點(diǎn)，適用于能量和資源受限的傳感器節(jié)點(diǎn)。仿真結(jié)果表明，LRMS能夠保證包括時(shí)延、能耗均衡以及投遞率在內(nèi)的多個(gè)性能指標(biāo)；通過與樹狀路由的對(duì)比分析，證明了LRMS方法的優(yōu)越性。

[1] Garca Villalba L J, Sandoval Orozco A L, Trivio Cabrera A, et al. Routing Protocols in Wireless Sensor Networks[J]. Sensors, 2009, 9(11): 8399-8421.

[2] Francesco M D, Das S K, Anastasi G. Data collection in wireless sensor networks with mobile elements: a survey[J]. ACM Transactions on Sensor Networks, 2011, 8(1), 7: 1-31.

[3] Tan C G, Xu K, Wang J X, et al. A sink moving scheme based on local residual energy of nodes in wireless sensor networks [J]. Journal of Central South University of Technology, 2009, 16(2): 265-268.

[4] Khan A W, Abdullah A H, Anisi M H, et al. A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks[J]. Sensors, 2014, 14(2): 2510-2548.

[5] Carballido Villaverde B, Rea S, Pesch D. InRout-A QoS aware route selection algorithm for industrial wireless sensor networks[J]. Ad Hoc Networks, 2012, 10(3): 458-478.

[6] Luo H, Ye F, Cheng J, et al. TTDD: two-tier data dissemination in large-scale wireless sensor networks[J]. Wireless Networks, 2005, 11(1-2): 161-175.

[7] Konstantopoulos C, Pantziou G, Gavalas D, et al. A Rendezvous-Based Approach Enabling Energy-Efficient Sensory Data Collection with Mobile Sinks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(5): 809-817.

[8] Li X, Yang J, Nayak A, et al. Localized Geographic Routing to a Mobile Sink with Guaranteed Delivery in Sensor Networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(9): 1719-1729.

[9] Hasan A. A. Al-Rawi, Ming Ann Ng, Kok-Lim Alvin Yau. Application of reinforcement learning to routing in distributed wireless networks: a review[J]. Artificial Intelligence Review, 2013(1): 1-36.

[10] Boyan J A, Littman M L. Packet Routing in Dynamically Changing Networks: A Reinforcement Learning Approach[J]. Advances in Neural Information Processing Systems, 1994, 6: 671-678.

[11] Kulkarni R V, Forster A, Venayagamoorthy G K. Computational Intelligence in Wireless Sensor Networks: A Survey[J]. IEEE communications surveys and tutorials, 2011, 13(1): 68-96.

[12] Guo W, Zhang W. A survey on intelligent routing protocols in wireless sensor networks[J]. Journal of Network and Computer Applications, Feb. 2014, 38: 185-201.

[13] Forster A, Murphy A L. Froms: A failure tolerant and mobility enabled multicast routing paradigm with reinforcement learning for WSNs[J]. 2011, 5(9): 940-965.

[14] Macone D, Oddi G, Pietrabissa A. MQ-Routing: Mobility-, GPS- and energy-aware routing protocol in MANETs for disaster relief scenarios[J]. Ad Hoc Networks, 2013, 11(3): 861-878.

[15] Watkins C J C H. Learning from delayed rewards[D]. Ph.D. thesis, Cambridge University, Cambridge, England, 1989.

[16] Li X. Collaborative Localization with Received-Signal Strength in Wireless Sensor Networks[J]. IEEE Transactions on Vehicular Technology[J]. 2007, 56(6): 3807-3817.

[17] Watkins C J C H, Dayan P. Q-learning[J]. Machine Learning, 1992, 8(3-4): 279-292.

[18] Qiu W Z, Skafidas E, Hao P. Enhanced tree routing for wireless sensor networks[J]. Ad Hoc Networks, 2009, 7(3): 638-650.