王桐,龔續(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ī)制,改善了投遞成功率。
水下傳感器網(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ò)模型
水下無(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ì)。
在經(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ò)生命周期。
強(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)移矩陣:
強(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ì)。
在節(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。
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é)在下文中給出。
在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í)延。
算法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 本文基于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ù) 由于算法收斂速度可以反映路由算法的性能,本文首先對(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ì)比 本文針對(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)境。3 算法仿真與結(jié)果分析
3.1 仿真環(huán)境
3.2 結(jié)果分析
4 結(jié)論