基于消息反饋與強(qiáng)化學(xué)習(xí)的節(jié)能路由算法

王桐，龔續(xù)，常遠(yuǎn)，薛書鈺，陳奕霏

1.哈爾濱工程大學(xué) 信息與通信工程學(xué)院, 黑龍江 哈爾濱 150001

2.哈爾濱工程大學(xué) 先進(jìn)船舶通信與信息技術(shù)工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室, 黑龍江 哈爾濱 150001

3.國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心 黑龍江分中心, 黑龍江 哈爾濱 150028

隨著人類對(duì)海洋資源越發(fā)重視，水下無(wú)線傳感器網(wǎng)絡(luò) (underwater wireless sensor network, UWSN)正在成為水聲環(huán)境領(lǐng)域方向的熱點(diǎn)研究問(wèn)題，在水環(huán)境監(jiān)測(cè)、海洋數(shù)據(jù)收集、海底勘探、災(zāi)害預(yù)警等方面具有重要的應(yīng)用[1?2]。針對(duì)無(wú)人看守但需要長(zhǎng)期采集水下信息的使用場(chǎng)景，傳感器網(wǎng)絡(luò)的能量消耗成為亟待解決的問(wèn)題。

UWSN由若干傳感器節(jié)點(diǎn)組成，用以監(jiān)測(cè)水下環(huán)境。實(shí)驗(yàn)數(shù)據(jù)表明，電磁波在水中傳播的衰減極大，故水下環(huán)境中多采用聲波進(jìn)行通信[3]。受水下環(huán)境影響，傳感器節(jié)點(diǎn)可能在水流作用下發(fā)生位置偏移，導(dǎo)致整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化。此外，水下節(jié)點(diǎn)一經(jīng)部署，就難以對(duì)節(jié)點(diǎn)能量進(jìn)行補(bǔ)充。隨著傳感器網(wǎng)絡(luò)不斷工作，部分節(jié)點(diǎn)可能因能量耗盡成為空節(jié)點(diǎn)[4]。因?yàn)橐陨显?，關(guān)于UWSN的研究重點(diǎn)正逐步偏向具有更長(zhǎng)網(wǎng)絡(luò)生命、更高能量效率 的路由協(xié)議。Wahid等[5]在基于深度信息的水下路由算法 (depth-based routing, DBR)[6]的基礎(chǔ)上進(jìn)行改進(jìn)，提出了EEDBR(energy-efficient depth-based routing)協(xié) 議 ，以深度信息為切入點(diǎn)，考慮節(jié)點(diǎn)之間的深度差值、節(jié)點(diǎn)剩余能量等信息篩選參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)。該協(xié)議雖然在路由效率上效果顯著，但仍存在能量的多余開(kāi)銷、網(wǎng)絡(luò)生命周期短的問(wèn)題。Hu等[7]基于強(qiáng)化學(xué)習(xí)的思想，在Q-Learning的基礎(chǔ)上設(shè)計(jì)基于強(qiáng)化學(xué)習(xí)的能量有效生命周期感知路由協(xié)議 (energy-efficient and lifetime-aware routing protocol based on reinforcement learning, QELAR)，將路由問(wèn)題建模為滿足馬爾可夫性質(zhì)的強(qiáng)化學(xué)習(xí)任務(wù)，整個(gè)網(wǎng)絡(luò)通過(guò)學(xué)習(xí)環(huán)境和評(píng)估動(dòng)作值函數(shù)篩選轉(zhuǎn)發(fā)節(jié)點(diǎn)。該方法可有效均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗，但單純考慮節(jié)點(diǎn)能量因素導(dǎo)致路由效率降低，且對(duì)數(shù)據(jù)包發(fā)送失敗的情況沒(méi)有很好的處理，算法的消息投遞率偏低。

本文基于強(qiáng)化學(xué)習(xí)對(duì)水下路由協(xié)議進(jìn)行研究，提出一種新的基于反饋消息的能量有效水下路由協(xié)議 (energy-efficient routing based on message feedback and reinforcement learnin, EERFQ)。 該 協(xié)議在QELAR的研究上新增了節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度作為衡量節(jié)點(diǎn)存在空路由風(fēng)險(xiǎn)的指標(biāo)，在考慮剩余能量信息的基礎(chǔ)上增加對(duì)深度信息的權(quán)重并重新設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，在保證整個(gè)網(wǎng)絡(luò)能量均衡的前提下，優(yōu)化了傳輸時(shí)延并延長(zhǎng)了水下網(wǎng)絡(luò)聲明周期。此外，針對(duì)消息轉(zhuǎn)發(fā)中轉(zhuǎn)發(fā)失敗的情況，設(shè)計(jì)基于反饋信息的消息重傳機(jī)制，改善了投遞成功率。

1 模型描述

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

水下傳感器網(wǎng)絡(luò)仿真應(yīng)盡可能貼近實(shí)際用途，研究表明，三維水下環(huán)境中節(jié)點(diǎn)的移動(dòng)特征表現(xiàn)為在水平方向隨機(jī)移動(dòng)，但垂直方向位置基本無(wú)變化[8]。本文采用的水下三維環(huán)境仿真模型如圖1所示。整個(gè)水下無(wú)線傳感器網(wǎng)絡(luò)中存在一個(gè)產(chǎn)生有效數(shù)據(jù)的源節(jié)點(diǎn)(source)與有效消息最終送達(dá)的目的節(jié)點(diǎn)(sink)，其余節(jié)點(diǎn)均為中繼節(jié)點(diǎn)，中繼節(jié)點(diǎn)擁有有限的初始能量，且具備轉(zhuǎn)發(fā)和接收消息包的能力。在水下環(huán)境中，節(jié)點(diǎn)受洋流作用移動(dòng)，難以獲取準(zhǔn)確的三維位置信息，但節(jié)點(diǎn)深度信息可以輕易得到[9]。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有唯一的標(biāo)識(shí)(node ID)，源節(jié)點(diǎn)產(chǎn)生的每個(gè)數(shù)據(jù)包也有唯一標(biāo)識(shí)(packet ID)。每當(dāng)目的節(jié)點(diǎn)接收到由源節(jié)點(diǎn)產(chǎn)生的攜帶有效數(shù)據(jù)的消息包，視為消息投遞成功。

圖1 水下傳感器網(wǎng)絡(luò)模型

1.2 能量模型

水下無(wú)線傳感器網(wǎng)路中節(jié)點(diǎn)行為可分為監(jiān)聽(tīng)、發(fā)送、接收等動(dòng)作，不同動(dòng)作對(duì)應(yīng)的能量消耗也是不同的。本文中所有節(jié)點(diǎn)具備統(tǒng)一的初始能量且在整個(gè)網(wǎng)絡(luò)生命周期內(nèi)中不會(huì)得到補(bǔ)充，節(jié)點(diǎn)之間的通信采用Thorp傳播模型[10]。節(jié)點(diǎn)發(fā)送一個(gè)傳輸時(shí)延為Tp的數(shù)據(jù)包消耗的能量為

式 中： λt為節(jié) 點(diǎn)的發(fā) 射功率 系數(shù)， 通常 取0.001；P0為節(jié)點(diǎn)接收數(shù)據(jù)包的最低功率；x為數(shù)據(jù)包需要傳輸?shù)木嚯x；A(f,x)是與消息發(fā)送方式、傳輸距離及頻率有關(guān)的物理量衰減模型，可表示為

式中：k是能量擴(kuò)展系數(shù)（圓柱形擴(kuò)展k為1，球形擴(kuò)展k為2，實(shí)際仿真采用k為1.5），k與頻率f有關(guān)。吸收系數(shù) α (f)根據(jù)Thorp表達(dá)式得到：

節(jié)點(diǎn)融合1個(gè)數(shù)據(jù)包的能耗表示為

式中 λr為接收能耗系數(shù)，通常也取0.001。

由式(1)和式(2)可知，節(jié)點(diǎn)收發(fā)數(shù)據(jù)包消耗的能量與數(shù)據(jù)包的傳輸時(shí)間和通信距離呈正相關(guān)，即水下通信網(wǎng)絡(luò)中節(jié)點(diǎn)通信距離越遠(yuǎn)，節(jié)點(diǎn)能耗就越大?；诮?jīng)典水下傳感器能量模型，中繼節(jié)點(diǎn)在路由過(guò)程中的主要能量開(kāi)銷在消息的發(fā)送、接收以及監(jiān)聽(tīng)3個(gè)動(dòng)作上，節(jié)點(diǎn)在處理數(shù)據(jù)時(shí)的能量損耗通常忽略不計(jì)。

2 協(xié)議描述

在經(jīng)典的水下路由協(xié)議中多采用基于跳數(shù)或能量消耗的最短路徑算法來(lái)實(shí)現(xiàn)算法低延遲、高能量效率的需求。利用強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)的水下路由算法可以通過(guò)綜合考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的剩余能量、深度信息及歷史轉(zhuǎn)發(fā)成功率等信息計(jì)算獎(jiǎng)勵(lì)函數(shù)，從而選擇合適的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，在兼顧轉(zhuǎn)發(fā)跳數(shù)與分組投遞率的同時(shí)達(dá)到整個(gè)網(wǎng)絡(luò)能量均衡，從而延長(zhǎng)網(wǎng)絡(luò)生命周期。

2.1 基于強(qiáng)化學(xué)習(xí)的水下路由狀態(tài)空間

強(qiáng)化學(xué)習(xí)主要關(guān)注智能體如何在環(huán)境中采取不同的行為，目的是最大限度地提高累計(jì)回報(bào)[11]。水下傳感器網(wǎng)絡(luò)中，攜帶數(shù)據(jù)包的節(jié)點(diǎn)向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的過(guò)程滿足馬爾可夫性，因此可以將這樣的路由問(wèn)題建模成滿足馬爾可夫性質(zhì)的強(qiáng)化學(xué)習(xí)任務(wù) (markov decision process, MDP)。

強(qiáng)化學(xué)習(xí)框架如圖2所示，智能體通過(guò)與環(huán)境交互不斷改進(jìn)策略從而對(duì)不同的狀態(tài)進(jìn)行動(dòng)作決策。在RL問(wèn)題中，處于狀態(tài)si下的智能體Agent經(jīng)過(guò)動(dòng)作aj到達(dá)狀態(tài)sj的概率為，而獎(jiǎng)勵(lì)函數(shù)表示環(huán)境對(duì)Agent從狀態(tài)si采取動(dòng)作aj到達(dá)狀態(tài)sj的期望回報(bào)。在水下路由過(guò)程中，節(jié)點(diǎn)對(duì)下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇至關(guān)重要。將強(qiáng)化學(xué)習(xí)過(guò)程映射到水下路由模型中，通過(guò)不斷地交互與試錯(cuò)，轉(zhuǎn)發(fā)節(jié)點(diǎn)最終可以選出最優(yōu)的轉(zhuǎn)發(fā)路徑。

圖2 強(qiáng)化學(xué)習(xí)框架

本文定義整個(gè)水下傳感器網(wǎng)絡(luò)為一個(gè)系統(tǒng)，系統(tǒng)狀態(tài)定義與單個(gè)數(shù)據(jù)包有關(guān)：假設(shè)網(wǎng)絡(luò)中存在n個(gè) 節(jié)點(diǎn)，其中n1持有數(shù)據(jù)包，與數(shù)據(jù)包相關(guān)的系統(tǒng)狀態(tài)定義為s1。節(jié)點(diǎn)n1將數(shù)據(jù)包轉(zhuǎn)發(fā)到節(jié)點(diǎn)n2的動(dòng)作定義為a2。所有與傳感器網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)相關(guān)的狀態(tài)和動(dòng)作組成狀態(tài)集S與動(dòng)作集A。

在t時(shí)刻從狀態(tài)st采取動(dòng)作時(shí)收到的行為終端反饋表示為

強(qiáng)化學(xué)習(xí)的目的是獲取盡可能多的累計(jì)獎(jiǎng)勵(lì)的策略，對(duì)于水下路由這種需要不斷與環(huán)境交互的持續(xù)性任務(wù)，累計(jì)獎(jiǎng)勵(lì)也被稱為回報(bào)，它的定義如下：

式中 γ為折扣因子，它的作用是保證回報(bào)不會(huì)發(fā)散至無(wú)無(wú)窮大，折扣因子處于[ 0 ,1)的范圍內(nèi)。Q-Learning中定義在 π策略下在狀態(tài)s采取動(dòng)作a時(shí)得到的預(yù)期回報(bào)為

狀態(tài)s在 π策略下的值Value的最優(yōu)解表示為

由式(3)和式(4)得到在最低限度采取行動(dòng)并遵循最優(yōu)策略所能得到的預(yù)期報(bào)酬為

以迭代來(lái)近似表示

式中 α 為學(xué)習(xí)率，取值范圍在 [0 ,1)，若取值為0則表示將不會(huì)學(xué)習(xí)到任何新的東西。我們借助 α來(lái)模擬學(xué)習(xí)過(guò)程中更新Q值的速率。

在水下傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的轉(zhuǎn)發(fā)并不總是成功的，定義從狀態(tài)sn成功轉(zhuǎn)移到狀態(tài)sm的概率為，則相應(yīng)的轉(zhuǎn)移失敗概率為 1 ?。對(duì)于狀態(tài)s1得到如下?tīng)顟B(tài)轉(zhuǎn)移矩陣：

2.2 獎(jiǎng)勵(lì)函數(shù)及分析

強(qiáng)化學(xué)習(xí)問(wèn)題中，智能體與環(huán)境的交互均作用于獎(jiǎng)勵(lì)函數(shù)，本文算法在設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)時(shí)從節(jié)點(diǎn)轉(zhuǎn)發(fā)的跳數(shù)、能量消耗、數(shù)據(jù)包傳輸方向3個(gè)方面入手，在保障數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)盡可能少、端到端時(shí)延盡可能低的情況下，均衡網(wǎng)絡(luò)節(jié)點(diǎn)能量損耗，延長(zhǎng)網(wǎng)絡(luò)整體生命周期。

考慮節(jié)點(diǎn)sn將消息包轉(zhuǎn)發(fā)給節(jié)點(diǎn)sm的情況。在消息包轉(zhuǎn)發(fā)成功的情況下，將對(duì)狀態(tài)動(dòng)作對(duì)(sn,am)的瞬時(shí)獎(jiǎng)勵(lì)函數(shù)定義為

每當(dāng)節(jié)點(diǎn)轉(zhuǎn)發(fā)消息時(shí)，它將消耗一定的能量，占用信道帶寬。在多跳傳輸?shù)穆酚删W(wǎng)絡(luò)中，額外的轉(zhuǎn)發(fā)次數(shù)還將增加消息到達(dá)目的地的時(shí)延。設(shè)置固定的懲罰因數(shù)g用以約束節(jié)點(diǎn)的行為。即參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)將持續(xù)受到固定的懲罰，在這種情況下，節(jié)點(diǎn)為了保證盡可能大，將被迫選擇相對(duì)短的路徑到達(dá)目的地從而減小路由延遲。

由于基于貪婪策略的Q-Learning總是選取q值最大的動(dòng)作，導(dǎo)致節(jié)點(diǎn)傾向于在轉(zhuǎn)發(fā)次數(shù)最少的情況下將消息發(fā)送到目的節(jié)點(diǎn)。實(shí)際上在節(jié)點(diǎn)的感知范圍內(nèi)，如果僅考慮單一因素，將導(dǎo)致節(jié)點(diǎn)學(xué)習(xí)過(guò)程中能耗過(guò)多、V值收斂速度緩慢等問(wèn)題。式(5)中的系數(shù) β可以決定深度決策因子D(·)在對(duì)獎(jiǎng)勵(lì)函數(shù)的影響。系數(shù) β越大，節(jié)點(diǎn)在轉(zhuǎn)發(fā)時(shí)會(huì)傾向選擇地理位置更高的節(jié)點(diǎn)。這與水下無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際需求是相符的。水下無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)深度信息是容易獲取的。因此定義深度決策因子為

式中：dsn與dsm分 別為節(jié)點(diǎn)sn、sm的深度，Rmax為節(jié)點(diǎn)的最大傳輸半徑。 此外，出于傳感器網(wǎng)絡(luò)能量均衡的目的，還希望節(jié)點(diǎn)在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)優(yōu)先選擇剩余能量較高的節(jié)點(diǎn)，通過(guò)這樣的方式延長(zhǎng)網(wǎng)絡(luò)整體生命周期。 能量決策因子C(·)定義為

通過(guò)定義可知，獎(jiǎng)勵(lì)函數(shù)中D(·)的范圍為[?1,1]，C(·)的范圍為 [0 ,1]?？梢酝ㄟ^(guò)調(diào)整瞬時(shí)獎(jiǎng)勵(lì)函數(shù)中的固定獎(jiǎng)勵(lì)與各項(xiàng)系數(shù)來(lái)平衡3種因素在決策時(shí)的重要性。在3項(xiàng)因素中，固定成本比較重要，它可以大大減少節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的跳數(shù)。但實(shí)際上基于多跳的繞行方案更有利于節(jié)省能量。本文設(shè)置固定懲罰因數(shù)g=1，能量決策系數(shù) α1=0.5，深度決策系數(shù) β =0.1。

若消息轉(zhuǎn)發(fā)失敗，瞬時(shí)獎(jiǎng)勵(lì)定義為

此處將系數(shù) α1、 α2的值統(tǒng)一為0.5。

長(zhǎng)期回報(bào)公式定義為

根據(jù)長(zhǎng)期回報(bào)公式定義，不論轉(zhuǎn)發(fā)行為成功與否，智能體收到的即時(shí)獎(jiǎng)勵(lì)總是小于0，意味著節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)行為時(shí)總是收到負(fù)值獎(jiǎng)勵(lì)。

2.3 節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度

在節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)行為時(shí)，需要對(duì)下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)進(jìn)行決策?？紤]一種消息轉(zhuǎn)發(fā)失敗的情況。當(dāng)前攜帶消息的節(jié)點(diǎn)為sn，它的鄰居節(jié)點(diǎn)為集合S，當(dāng)前節(jié)點(diǎn)sn經(jīng)過(guò)決策選擇下一跳消息轉(zhuǎn)發(fā)節(jié)點(diǎn)為sm。 若出于某種原因，此次轉(zhuǎn)發(fā)失敗，消息未能成功轉(zhuǎn)發(fā)到節(jié)點(diǎn)sm，在下次進(jìn)行決策時(shí)，需要將這樣的失敗傳輸記錄納入決策因素。因此設(shè)計(jì)節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度因素F，節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度可以近似反映節(jié)點(diǎn)參與下一跳轉(zhuǎn)發(fā)的適宜程度。以節(jié)點(diǎn)sm為例進(jìn)行說(shuō)明，定義節(jié)點(diǎn)sm節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度為Fm，表達(dá)式為

式中：Dm為節(jié)點(diǎn)sm鄰居節(jié)點(diǎn)中處于更高位置的節(jié)點(diǎn)比例，Nm用來(lái)反映節(jié)點(diǎn)sm的鄰居節(jié)點(diǎn)稠密程度。隨著數(shù)據(jù)包的交換，每個(gè)節(jié)點(diǎn)維護(hù)自己鄰居節(jié)點(diǎn)的節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度。 ηm表示節(jié)點(diǎn)sm歷史消息轉(zhuǎn)發(fā)成功率。

式中：nhigher、ntotal分別為節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中深度信息小于當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)個(gè)數(shù)與鄰居節(jié)點(diǎn)總數(shù)，fACK與ftotal分別為該節(jié)點(diǎn)所有轉(zhuǎn)發(fā)過(guò)程中收到的對(duì)應(yīng) A CK 消息數(shù)量與嘗試轉(zhuǎn)發(fā)的總次數(shù)，Rmax為節(jié)點(diǎn)最大通信范圍。顯然，一個(gè)節(jié)點(diǎn)擁有越多的鄰居節(jié)點(diǎn)，它的候選下一跳節(jié)點(diǎn)數(shù)量就越多，我們希望消息的轉(zhuǎn)發(fā)過(guò)程具備自下而上的方向性，因此鄰居節(jié)點(diǎn)中處于更高位置的節(jié)點(diǎn)數(shù)量越多，參與轉(zhuǎn)發(fā)的優(yōu)勢(shì)越大。此外，如果一個(gè)節(jié)點(diǎn)在轉(zhuǎn)發(fā)過(guò)程中總是失敗，將會(huì)削弱它的優(yōu)勢(shì)，所以將節(jié)點(diǎn)的歷史消息轉(zhuǎn)發(fā)成功率也納入?yún)⒖?。引入?jié)點(diǎn)轉(zhuǎn)發(fā)適宜度后長(zhǎng)期回報(bào)定義為

根據(jù)式(6)和式(7)，節(jié)點(diǎn)的轉(zhuǎn)發(fā)適宜度F的范圍在 [0 ,1)，因此下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度越大，此次轉(zhuǎn)發(fā)行為受到的懲罰越小。所有sink以外參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)總是收到負(fù)值獎(jiǎng)勵(lì)，因而Vvalue總是負(fù)值，而sink節(jié)點(diǎn)的Vvalue總是整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中最大的，設(shè)其值為0。

2.4 數(shù)據(jù)包設(shè)計(jì)

EERFQ算法的路由過(guò)程中信息交互主要由有效消息的轉(zhuǎn)發(fā)和控制信息的交換兩部分組成。有效信息的轉(zhuǎn)發(fā)是水下無(wú)線傳感器網(wǎng)絡(luò)的主要任務(wù)。源節(jié)點(diǎn)產(chǎn)生的有效信息經(jīng)由傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)之間多次轉(zhuǎn)發(fā)，最終抵達(dá)目的節(jié)點(diǎn)的過(guò)程。控制信息的交換是指發(fā)生在轉(zhuǎn)發(fā)過(guò)程中的節(jié)點(diǎn)間信息交換。控制信息的交換與實(shí)際有效信息無(wú)關(guān)，是各節(jié)點(diǎn)通過(guò)數(shù)據(jù)包的報(bào)頭信息維護(hù)自身鄰居節(jié)點(diǎn)的行為。

在EERFQ中，消息包格式如圖3所示。消息包主要由消息包相關(guān)信息、上一跳節(jié)點(diǎn)信息與實(shí)際有效載荷3部分組成。

圖3 數(shù)據(jù)包格式

數(shù)據(jù)包相關(guān)項(xiàng)說(shuō)明：

1）Packet_Type表示當(dāng)前消息包的功能。用來(lái)區(qū)分當(dāng)前消息包是否承擔(dān)有效載荷。

2）Packet_Sequence_ID，消息包序列號(hào)，對(duì)具體數(shù)據(jù)包起辨識(shí)作用。

3）Destination_Address，消息包最終被送達(dá)的目的節(jié)點(diǎn)。目的節(jié)點(diǎn)由產(chǎn)生消息的源節(jié)點(diǎn)指定，通常，在整個(gè)水下無(wú)線傳感器網(wǎng)絡(luò)的生存周期中都不會(huì)改變。

在節(jié)點(diǎn)對(duì)消息進(jìn)行轉(zhuǎn)發(fā)時(shí)，會(huì)將本身的一部分信息添加在消息包中起到信息交換的作用，其中包括：

1）Sender_Node_ID，轉(zhuǎn)發(fā)當(dāng)前消息包的節(jié)點(diǎn)ID，在整個(gè)傳感器網(wǎng)絡(luò)中唯一。

2）Vvalue，節(jié)點(diǎn)當(dāng)前Vvalue。

3）Residual_Energy，轉(zhuǎn)發(fā)當(dāng)前消息包的節(jié)點(diǎn)剩余能量。

4）Node_Depth，此節(jié)點(diǎn)的深度信息。假設(shè)水下無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)容易獲取自身的深度信息。

5）Forwarding_Factor，節(jié)點(diǎn)的轉(zhuǎn)發(fā)適宜度因子。下文將給出具體定義。

6）Next_hop_Node，轉(zhuǎn)發(fā)此消息包的下一跳節(jié)點(diǎn)。

當(dāng)節(jié)點(diǎn)監(jiān)聽(tīng)并收到數(shù)據(jù)包時(shí)，將根據(jù)數(shù)據(jù)包中攜帶的報(bào)頭信息更新其鄰居節(jié)點(diǎn)相關(guān)信息?；诒疚闹刑岢龅南⒅貍鳈C(jī)制，Next_hop_Node字段在重傳過(guò)程中可能存在不止一個(gè)節(jié)點(diǎn)信息，更多細(xì)節(jié)在下文中給出。

2.5 基于消息反饋的重傳機(jī)制

在Lu等[12]提出的EDORQ算法中，給出了一種對(duì)陷入空節(jié)點(diǎn)的數(shù)據(jù)包的挽救措施，即以廣播數(shù)據(jù)包的方式使數(shù)據(jù)包脫離空節(jié)點(diǎn)。這種方法可以起到挽救數(shù)據(jù)包的作用，但廣播的方式將大量消耗節(jié)點(diǎn)能量占用網(wǎng)絡(luò)資源。本文在此基礎(chǔ)上提出基于消息反饋的數(shù)據(jù)包重傳機(jī)制。節(jié)點(diǎn)成功接收到包含有效載荷的數(shù)據(jù)包時(shí)，廣播一個(gè)針對(duì)此數(shù)據(jù)的控制包。因?yàn)榭刂瓢话行?shù)據(jù)，所以體量非常小，傳輸時(shí)間短，并不占用過(guò)多的網(wǎng)絡(luò)資源，卻可以通知上一跳節(jié)點(diǎn)消息已被成功送達(dá)，保證消息的有效傳遞。

如圖4所示，節(jié)點(diǎn)n1經(jīng)過(guò)決策嘗試將數(shù)據(jù)包發(fā)送給節(jié)點(diǎn)n2，但某些原因?qū)е麓舜伟l(fā)送失敗，經(jīng)過(guò)一定等待時(shí)間后n1仍未能收到由n2成功接收當(dāng)前數(shù)據(jù)包的反饋，此時(shí)觸發(fā)數(shù)據(jù)包重傳機(jī)制。圖5(a)和圖5(b)分別描述了節(jié)點(diǎn)轉(zhuǎn)發(fā)成功與轉(zhuǎn)發(fā)失敗2種不同情況時(shí)的處理邏輯。第1次嘗試重傳時(shí)，除節(jié)點(diǎn)n2以外，節(jié)點(diǎn)n1從它的所有候選節(jié)點(diǎn)中選擇下一跳適宜度僅次于節(jié)點(diǎn)n2的節(jié)點(diǎn)n3。

圖4 消息轉(zhuǎn)發(fā)示意

圖5 消息重傳邏輯

隨著重傳的嘗試次數(shù)增多，每次節(jié)點(diǎn)都多指定一個(gè)節(jié)點(diǎn)作為下一跳，直到某次傳輸成功，收到某個(gè)節(jié)點(diǎn)接收成功的反饋信息，或者到達(dá)最大重傳嘗試次數(shù)Ttrans_max。若重傳嘗試成功，當(dāng)前發(fā)送節(jié)點(diǎn)立即更新下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度F，并根據(jù)重傳嘗試次數(shù)不同，削減接收失敗節(jié)點(diǎn)的轉(zhuǎn)發(fā)適宜度。若此次轉(zhuǎn)發(fā)以失敗告終，則當(dāng)前攜帶數(shù)據(jù)包的節(jié)點(diǎn)大概率陷入了路由空洞。成為空節(jié)點(diǎn)的原因多種多樣，可能是能量不足，可能是由于移動(dòng)性到達(dá)了周圍鄰居節(jié)點(diǎn)的感知盲區(qū)，也可能僅僅是通信質(zhì)量不好造成的誤判。改進(jìn)的消息重傳機(jī)制一定程度上占用了更多帶寬，但可以大大提高消息轉(zhuǎn)發(fā)效率，減少消息端到端時(shí)延。

2.6 EERFQ 算法流程

算法1是路由算法節(jié)點(diǎn)轉(zhuǎn)發(fā)過(guò)程偽代碼。當(dāng)節(jié)點(diǎn)監(jiān)聽(tīng)到一個(gè)數(shù)據(jù)包p時(shí)，首先根據(jù)數(shù)據(jù)包的發(fā)送方信息更新發(fā)送節(jié)點(diǎn)信息。然后判斷該數(shù)據(jù)包是否攜帶有效消息，如果是控制包，那么僅更新鄰居節(jié)點(diǎn)信息，然后直接丟棄該數(shù)據(jù)包。如果數(shù)據(jù)包攜帶有效信息，該節(jié)點(diǎn)首先針對(duì)此數(shù)據(jù)包廣播反饋消息，然后進(jìn)行虛擬計(jì)算，并更新自身維護(hù)的鄰居節(jié)點(diǎn)的Vvalue。當(dāng)前節(jié)點(diǎn)選出最適合轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn)后，將更新數(shù)據(jù)包的報(bào)頭信息并進(jìn)行轉(zhuǎn)發(fā)，同時(shí)等待此數(shù)據(jù)包的反饋信息。此過(guò)程中如果接收到針對(duì)此數(shù)據(jù)包的反饋信息證明下一跳節(jié)點(diǎn)已成功接收，節(jié)點(diǎn)更新鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)適宜度等信息。若傳輸失敗，則啟動(dòng)失敗重傳，直到消息包成功轉(zhuǎn)發(fā)或重傳次數(shù)超出最大限制。

算法1節(jié)點(diǎn)轉(zhuǎn)發(fā)

輸入:節(jié)點(diǎn)監(jiān)聽(tīng)消息包p

輸出:下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)m；附帶了當(dāng)前節(jié)點(diǎn)信息的消息包p

1）if Packet_Type = 0 // 如果數(shù)據(jù)包p不攜帶有效消息

2）根據(jù)p中報(bào)頭消息更新鄰居節(jié)點(diǎn)信息

3）更新上一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度

4）丟棄p

5）else

6）廣播針對(duì)數(shù)據(jù)包p的反饋消息

7）更新節(jié)點(diǎn)Vvalue

8）T_trans ← 1//初始化重傳次數(shù)

9）計(jì)算鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度，選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)m

10）更新數(shù)據(jù)包p//將自身節(jié)點(diǎn)信息附加到數(shù)據(jù)包中

11）向節(jié)點(diǎn)m轉(zhuǎn)發(fā)數(shù)據(jù)包p

12）if 未收到當(dāng)前p的反饋消息do

13）消息重傳函數(shù)()

14）end if

15）if 收到p反饋消息 then

16）更新對(duì)節(jié)點(diǎn)m轉(zhuǎn)發(fā)適宜度

17）end if

18）ifT_trans =T_trans_max do

19）廣播數(shù)據(jù)包p，鄰居節(jié)點(diǎn)更新信息

20）丟棄數(shù)據(jù)包p

21）end if

22）end if

數(shù)據(jù)包重傳過(guò)程偽代碼如算法2所示。若重傳次數(shù)到達(dá)最大限制，則認(rèn)為轉(zhuǎn)發(fā)失敗，節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播當(dāng)前數(shù)據(jù)包p并告知鄰居節(jié)點(diǎn)更新對(duì)當(dāng)前節(jié)點(diǎn)的轉(zhuǎn)發(fā)適宜度。這種做法可以幫助路由過(guò)程中繞過(guò)存在空洞風(fēng)險(xiǎn)的節(jié)點(diǎn)，從而增加路由效率。節(jié)點(diǎn)在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)的算法復(fù)雜度為與文獻(xiàn)[13]提出的算法復(fù)雜度類似，與節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)和網(wǎng)絡(luò)規(guī)模有關(guān)。

算法2消息重傳

輸入:當(dāng)前數(shù)據(jù)包p;下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)m;重傳次數(shù)T_trans

輸出:嘗試轉(zhuǎn)發(fā)次數(shù)T_trans

1） whileT_trans

2）等待單位轉(zhuǎn)發(fā)時(shí)間T_wait

3）更新對(duì)節(jié)點(diǎn)m1轉(zhuǎn)發(fā)適宜度

4）根據(jù)鄰居節(jié)點(diǎn)列表另尋適合轉(zhuǎn)發(fā)的節(jié)點(diǎn)m2

5）更新數(shù)據(jù)包p

6）向節(jié)點(diǎn)m1，m2轉(zhuǎn)發(fā)數(shù)據(jù)包p//每次重傳，都多指定一個(gè)下一跳目的節(jié)點(diǎn)

7）T_trans += 1

8）end while

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

3.1 仿真環(huán)境

本文基于NS-3網(wǎng)絡(luò)仿真模擬器，在其提供的uan模塊基礎(chǔ)上實(shí)現(xiàn)本文算法仿真分析驗(yàn)證。仿真中設(shè)置中繼節(jié)點(diǎn)移動(dòng)速度為1 m/s，移動(dòng)模型為RandomWalk2dMobilityModel；網(wǎng)絡(luò)中源節(jié)點(diǎn)與目的節(jié)點(diǎn)各一個(gè)，分別固定在網(wǎng)絡(luò)邊界底層與頂層中央位置，源節(jié)點(diǎn)以1 個(gè)/s速率產(chǎn)生數(shù)據(jù)包，通過(guò)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，當(dāng)目的節(jié)點(diǎn)接收到數(shù)據(jù)包視為成功傳輸。網(wǎng)絡(luò)規(guī)模隨固定網(wǎng)絡(luò)邊界中節(jié)點(diǎn)數(shù)量變化而變化，定義100~300為稀疏規(guī)模，300~500為中等規(guī)模，500個(gè)節(jié)點(diǎn)以上為密集型網(wǎng)絡(luò)。各項(xiàng)參數(shù)設(shè)置見(jiàn)表1。

表1 仿真參數(shù)

3.2 結(jié)果分析

由于算法收斂速度可以反映路由算法的性能，本文首先對(duì)算法的收斂性進(jìn)行分析；接下來(lái)對(duì)協(xié)議的性能進(jìn)行評(píng)估，分析不同策略的算法在不同網(wǎng)絡(luò)規(guī)模的投遞成功率；分析節(jié)點(diǎn)平均能量利用率受網(wǎng)絡(luò)規(guī)模變化的影響；最后對(duì)中等網(wǎng)絡(luò)規(guī)模下不同算法從投遞成功率、路由效率和網(wǎng)絡(luò)生命周期3個(gè)方面對(duì)比分析。節(jié)點(diǎn)平均轉(zhuǎn)發(fā)次數(shù)指路由過(guò)程中數(shù)據(jù)包被轉(zhuǎn)發(fā)的平均次數(shù)。

定義節(jié)點(diǎn)平均能量利用率為

3.2.1 算法收斂性分析

根據(jù)EERFQ算法模型，目的節(jié)點(diǎn)的V值始終保持整個(gè)水下無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)中的最大值0。路由過(guò)程中，各節(jié)點(diǎn)轉(zhuǎn)發(fā)行為都將收到負(fù)值獎(jiǎng)勵(lì)，由于源節(jié)點(diǎn)距離目的節(jié)點(diǎn)最遠(yuǎn)，因此其V值收斂所需時(shí)間最長(zhǎng)。如圖6中曲線顯示，在發(fā)送數(shù)據(jù)包的起始階段，源節(jié)點(diǎn)V值快速下降，在發(fā)送約30~40個(gè)數(shù)據(jù)包后趨于穩(wěn)定，這意味著源節(jié)點(diǎn)路由在發(fā)送數(shù)據(jù)包過(guò)程中找到從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的轉(zhuǎn)發(fā)路徑。在后續(xù)過(guò)程中V值始終保持減少的趨勢(shì)，這是因?yàn)檗D(zhuǎn)發(fā)行為始終收到固定的負(fù)值獎(jiǎng)勵(lì)，導(dǎo)致V值存在下降趨勢(shì)。在轉(zhuǎn)發(fā)過(guò)程中V值存在小幅度波動(dòng)變化，這是在轉(zhuǎn)發(fā)過(guò)程中，需要考慮剩余能量、節(jié)點(diǎn)深度等因素為了使能量均勻分布，節(jié)點(diǎn)在轉(zhuǎn)發(fā)時(shí)放棄最短路徑，選擇轉(zhuǎn)發(fā)次數(shù)更多的路徑，此外還存在消息的傳輸故障重新轉(zhuǎn)發(fā)等情況。以上情況導(dǎo)致的轉(zhuǎn)發(fā)繞路行為將導(dǎo)致V值暫時(shí)增大，但隨著發(fā)送數(shù)據(jù)包的增多，V值存在始終減少的趨勢(shì)。

圖6 源節(jié)點(diǎn) V 值收斂過(guò)程

3.2.2 算法性能對(duì)比分析

本文將EERFQ算法與DBR、QELAR共3種算法在性能上仿真分析對(duì)比。首先是分析不同網(wǎng)絡(luò)規(guī)模下，發(fā)送相同數(shù)量數(shù)據(jù)包與相同網(wǎng)絡(luò)規(guī)模下發(fā)送不同數(shù)量的數(shù)據(jù)包這2種情況下3種算法的差異。

結(jié)果如圖7所示。圖7 (a)顯示了在相同網(wǎng)絡(luò)規(guī)模下3種不同的路由協(xié)議分組投遞率隨網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)變化受到的影響。發(fā)現(xiàn)3種算法在節(jié)點(diǎn)數(shù)較少的場(chǎng)景下分組投遞率并不高，但隨著節(jié)點(diǎn)數(shù)量的增加逐漸上升到穩(wěn)定水平。這是因?yàn)樵诰W(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量較少時(shí)，節(jié)點(diǎn)轉(zhuǎn)發(fā)路徑較為單一，遇到數(shù)據(jù)包轉(zhuǎn)發(fā)失敗的情況時(shí)將難以應(yīng)對(duì)。圖7(b)描述了在中等網(wǎng)絡(luò)節(jié)點(diǎn)的情況下，3種路由協(xié)議的分組投遞率指標(biāo)隨轉(zhuǎn)發(fā)數(shù)據(jù)包的增加變化的趨勢(shì)：隨著轉(zhuǎn)發(fā)數(shù)據(jù)包個(gè)數(shù)的增加，3種算法的分組投遞率一開(kāi)始可以維持在一定水平，后來(lái)逐漸減少。其中DBR算法的衰減迅速，這是由于隨著網(wǎng)絡(luò)中轉(zhuǎn)發(fā)次數(shù)的增多，一些節(jié)點(diǎn)頻繁參與轉(zhuǎn)發(fā)，沒(méi)有足夠剩余能量參與后續(xù)轉(zhuǎn)發(fā)行為，導(dǎo)致了投遞成功率的降低。

圖7 不同條件下分組投遞率變化

圖8描述了3種算法的節(jié)點(diǎn)平均能量利用率變化趨勢(shì)。由于EERFQ與QELAR算法在節(jié)點(diǎn)的能量均衡方面切入，因此節(jié)點(diǎn)平均能量利用率保持在較高水平，而DBR算法雖然未做能量均衡處理，但參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)很多，因此也保持一定的節(jié)點(diǎn)平均能量利用率。由圖9可知，同等條件下的3種路由算法中，EERFQ與QELAR算法投遞成功率相近，較DBR提升約32%；DBR算法僅以深度信息為依據(jù)，轉(zhuǎn)發(fā)過(guò)程中存在較多冗余數(shù)據(jù)，消耗大量節(jié)點(diǎn)能量，因而網(wǎng)絡(luò)生命周期較短。相比之下，EERFQ與QELAR算法轉(zhuǎn)發(fā)過(guò)程中引入剩余能量信息作為轉(zhuǎn)發(fā)依據(jù)，使得路由過(guò)程中節(jié)點(diǎn)能量保持相對(duì)均衡，獲得了更長(zhǎng)的網(wǎng)絡(luò)生命周期，EERFQ較QELAR算法網(wǎng)絡(luò)生命周期延長(zhǎng)約 15%，較 DBR延長(zhǎng)約 35%；而 EERFQ算法在轉(zhuǎn)發(fā)過(guò)程中引入了深度信息作為轉(zhuǎn)發(fā)參考依據(jù)，因此獲得了更高的路由效率，較QELAR路由效率提高約15%，較DBR提高約27%。

圖8 不同算法節(jié)點(diǎn)平均能量利用率

圖9 算法綜合性能對(duì)比

4 結(jié)論

本文針對(duì)水下無(wú)線傳感器網(wǎng)絡(luò)中存在的節(jié)點(diǎn)能量消耗不均衡和網(wǎng)絡(luò)生命周期較短的問(wèn)題，將強(qiáng)化學(xué)習(xí)與水下無(wú)線傳感器路由問(wèn)題結(jié)合，提出了一種基于強(qiáng)化學(xué)習(xí)與消息反饋機(jī)制的能量均衡路由算法。通過(guò)綜合考慮鄰居節(jié)點(diǎn)的深度、剩余能量及歷史轉(zhuǎn)發(fā)成功率等信息，重新設(shè)計(jì)了直接獎(jiǎng)勵(lì)函數(shù)；通過(guò)節(jié)點(diǎn)轉(zhuǎn)發(fā)適宜度因子，節(jié)點(diǎn)可以篩選出疑似空洞節(jié)點(diǎn)，保障了消息的投遞率；對(duì)于數(shù)據(jù)包轉(zhuǎn)發(fā)失敗的情況，改進(jìn)了節(jié)點(diǎn)重傳機(jī)制，在占用更少網(wǎng)絡(luò)帶寬的情況下對(duì)陷入空節(jié)點(diǎn)的數(shù)據(jù)包進(jìn)行挽救。仿真表明EERFQ算法可以有效適應(yīng)中等網(wǎng)絡(luò)規(guī)模下的傳感器網(wǎng)絡(luò)，并在保持較高分組投遞率和路由效率的前提下，有效均衡網(wǎng)絡(luò)整體能耗，延長(zhǎng)網(wǎng)絡(luò)整體生命周期，更適用于水下無(wú)線傳感器網(wǎng)絡(luò)需要長(zhǎng)期工作的使用場(chǎng)景。下一步考慮對(duì)算法獎(jiǎng)勵(lì)函數(shù)更進(jìn)一步擴(kuò)展，考慮應(yīng)用于規(guī)模更為稀疏的水下傳感器網(wǎng)絡(luò)，從節(jié)點(diǎn)行為出發(fā)，設(shè)計(jì)節(jié)能性能更好的方案以應(yīng)用于動(dòng)態(tài)性更強(qiáng)的水下環(huán)境。