梁文輝，董 強(qiáng)，何 明，陳秋麗，丁晨璐

LIANG Wenhui1，2,DONG Qiang1,HE Ming1,CHEN Qiuli1,DING Chenlu3

1.解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，南京210007

2.解放軍61345 部隊(duì)

3.解放軍理工大學(xué) 第六十三研究所，南京210007

1.College of Command Information Systems,PLA Science and Technology University,Nanjing 210007,China

2.61345 Troops,PLA,China

3.The 63rd Research Institute,PLA Science and Technology University,Nanjing 210007,China

1 引言

水下移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)（Mobile Underwater Wireless Sensor Networks，MUWSNs）應(yīng)用于水下復(fù)雜環(huán)境，傳感器易受水下生物、水流等外力因素影響發(fā)生位置遷移；且傳感器長(zhǎng)期受海水腐蝕及浮游生物的附著，逐漸降低靈敏度，易出現(xiàn)節(jié)點(diǎn)失效[1]。為推動(dòng)MUWSNs在水下重要領(lǐng)域應(yīng)用，高效、合理的拓?fù)溆纤惴ㄖ陵P(guān)重要[2]。

目前，針對(duì)MUWSNs 拓?fù)溆戏矫娴难芯砍晒苌?，文獻(xiàn)[3]提出拓?fù)溆纤惴═CS-CA，通過(guò)恢復(fù)失效節(jié)點(diǎn)單跳鄰居間可達(dá)性來(lái)實(shí)現(xiàn)拓?fù)渥杂撍惴ㄟm用于地面無(wú)線傳感器網(wǎng)絡(luò)，在MUWSNs 中并不適合；文獻(xiàn)[4]針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中出現(xiàn)的覆蓋洞區(qū)域，通過(guò)播撒第二代節(jié)點(diǎn)的方式修復(fù)覆蓋洞區(qū)域，但播撒的隨機(jī)性不能完全保證覆蓋洞區(qū)域能夠獲得足夠數(shù)量用于修復(fù)的新節(jié)點(diǎn)；文獻(xiàn)[5]利用已知網(wǎng)絡(luò)拓?fù)涞膸缀我?guī)則，賦予失效節(jié)點(diǎn)在離開(kāi)前決定其鄰居節(jié)點(diǎn)移動(dòng)行為的能力，但這對(duì)失效節(jié)點(diǎn)提出了很高的要求，較難實(shí)現(xiàn)；文獻(xiàn)[6]引入AUV 節(jié)點(diǎn)，提出基于滿Steiner 樹(shù)問(wèn)題的拓?fù)溆纤惴?，但未?duì)失效節(jié)點(diǎn)發(fā)現(xiàn)和AUV 選擇等問(wèn)題做具體的研究，且該方法基于二維平面，難以應(yīng)用在水下三維環(huán)境中。

針對(duì)上述問(wèn)題，本文提出一種基于自主式水下航行器（AUV）[7-9]的MUWSNs 愈合算法，充分考慮水流對(duì)MUWSNs 網(wǎng)絡(luò)拓?fù)涞挠绊?，?gòu)建水下實(shí)體移動(dòng)模型，利用AUVs的自主移動(dòng)性對(duì)MUWSNs失效拓?fù)溥M(jìn)行愈合。

2 網(wǎng)絡(luò)建模及問(wèn)題描述

2.1 網(wǎng)絡(luò)建模

在目標(biāo)監(jiān)測(cè)區(qū)域D中，不均勻地分布了M個(gè)需監(jiān)測(cè)的目標(biāo)事件，在區(qū)域D中部署N個(gè)傳感器節(jié)點(diǎn)和K個(gè)AUV 節(jié)點(diǎn)，傳感器與AUV 均為全向感知，最大感知半徑分別為rs與，最大通信半徑分別為rc與。為便于研究和計(jì)算，傳感器和AUV 均采用布爾感知模型。假設(shè)初始MUWSNs 網(wǎng)絡(luò)拓?fù)渲袀鞲衅鞴?jié)點(diǎn)在目標(biāo)監(jiān)測(cè)區(qū)域D中完成了非均勻部署，網(wǎng)絡(luò)全局連通，整個(gè)網(wǎng)絡(luò)對(duì)目標(biāo)事件集的覆蓋率達(dá)到90%以上；AUVs 分布密度與傳感器節(jié)點(diǎn)分布密度相匹配[10]。受水下外力因素影響，會(huì)出現(xiàn)節(jié)點(diǎn)故障或網(wǎng)絡(luò)失效，則需AUVs 進(jìn)行拓?fù)溆稀?/p>

將MUWSNs拓?fù)涑橄鬄橐粋€(gè)三維空間的無(wú)向圖，傳感器節(jié)點(diǎn)si的鄰居集合為Λ(si)，鄰居節(jié)點(diǎn)數(shù)為Nneigh(si)，感知半徑為rs(si)，覆蓋范圍為Nsensor(si)={ej|d(ej,si)≤rs(si),j=1,2,…,m}；si能量為e(si)，失效節(jié)點(diǎn)標(biāo)記為sf，對(duì)失效節(jié)點(diǎn)進(jìn)行替代的AUV標(biāo)記為af，AUV速度為VAUV。

為便于模型分析，給出符合實(shí)際應(yīng)用的假設(shè)：

假設(shè)1水下傳感器節(jié)點(diǎn)具備輔助定位系統(tǒng)，能夠知道自身位置及鄰居節(jié)點(diǎn)位置，并通過(guò)信息交互獲取鄰居節(jié)點(diǎn)的鄰居集合Λ(si)。

假設(shè)2AUV 可直接通過(guò)水面基站與其他AUV 進(jìn)行通信，并獲取其他AUV 的位置信息。

假設(shè)3在整個(gè)目標(biāo)監(jiān)測(cè)任務(wù)執(zhí)行過(guò)程中，AUV 能量為+∞，其信息感知收發(fā)以及位置移動(dòng)產(chǎn)生的能耗忽略不計(jì)。

假設(shè)4K＜＜N，由于AUV造價(jià)較高，因此部署數(shù)量遠(yuǎn)少于水下傳感器節(jié)點(diǎn)部署數(shù)量。

假設(shè)5，并且AUV 能按需在最大值范圍內(nèi)調(diào)節(jié)感知半徑和通信半徑的大小。

假設(shè)6在AUV 愈合過(guò)程中不會(huì)發(fā)生新失效。

2.2 水下實(shí)體移動(dòng)建模

水下實(shí)體包括監(jiān)測(cè)區(qū)域內(nèi)事件、傳感器以及AUVs，水下實(shí)體會(huì)隨著水流和漩渦等水體流散情況產(chǎn)生運(yùn)動(dòng)，從而引起MUWSNs 拓?fù)涞膭?dòng)態(tài)變化。水流的運(yùn)動(dòng)不是完全隨機(jī)的過(guò)程，結(jié)合一種適合流動(dòng)類型廣泛的水流運(yùn)動(dòng)模型[11-12]來(lái)構(gòu)建水下實(shí)體移動(dòng)模型，可更準(zhǔn)確地模擬MUWSNs真實(shí)運(yùn)行狀態(tài)。

對(duì)于不可壓縮的水流來(lái)說(shuō)，其運(yùn)動(dòng)可近似為在二維平面內(nèi)。在流體力學(xué)中，這是一個(gè)通用的假設(shè)[13]。

用ψ表示二維水流運(yùn)動(dòng)場(chǎng)，采用式（1）所示的水流噴射模型來(lái)描述水流運(yùn)動(dòng)情況：

B(t)=A+εcos(ωt)用于調(diào)制曲流寬度；A為平均曲流寬度，ε為調(diào)制振幅，ω為調(diào)制頻率，k為單位長(zhǎng)度曲流數(shù)目，c為曲流向下游移動(dòng)的相速度。

水下實(shí)體在水流場(chǎng)ψ內(nèi)的運(yùn)動(dòng)受兩個(gè)方向的速度場(chǎng)δ=(u,v)影響，用式（2）表示：

u表示向東的速度場(chǎng)，v表示向北的速度場(chǎng)。用拉格朗日法來(lái)描述水下實(shí)體在X、Y方向的運(yùn)動(dòng)速度，得到式（3）的Hamiltonian 方程：

從上述水下實(shí)體移動(dòng)模型可以看出，坐標(biāo)為(x,y,z)的水下實(shí)體經(jīng)過(guò)時(shí)間t后，隨水流移動(dòng)到了位置(x+x′×t,y+y′×t,z)處。對(duì)于X、Y坐標(biāo)相同但Z坐標(biāo)不同的水下實(shí)體，是以相同模式運(yùn)動(dòng)的。

3 算法設(shè)計(jì)

3.1 預(yù)處理階段

（1）AUVs分配

水中AUVs分布密度與傳感器分布密度相匹配。發(fā)生拓?fù)涫r(shí)，為使距離最近的AUV 實(shí)施愈合，需對(duì)每個(gè)AUV分配一定規(guī)模的傳感器，對(duì)ai∈A來(lái)說(shuō)，所負(fù)責(zé)的傳感器集合表示為Γ(ai)，并且有Γ(ai)∩Γ(aj)=?,(j≠i)。

圖1 演示了AUVs分配時(shí)的消息傳遞流程：

①?ai∈A，向通信范圍內(nèi)的傳感器節(jié)點(diǎn)發(fā)送報(bào)文invite_msg（IDi，Counter），IDi為ai的身份標(biāo)識(shí)，Counter為計(jì)數(shù)器，記錄報(bào)文傳遞次數(shù)，若傳感器節(jié)點(diǎn)總數(shù)為N，Counter 初始值設(shè)為N-1，報(bào)文每傳遞1 次，Counter 減1，減至0 時(shí)，報(bào)文失效。

②傳感器節(jié)點(diǎn)si收到invite_msg（IDi，Counter）報(bào)文后，查詢自身屬性中的AUV_flag標(biāo)識(shí)，若AUV_flag=Null，則修改為AUV_flag=IDi，即si加入集合Γ(ai)，并向ai發(fā)送回復(fù)報(bào)文reply_msg(si)；若AUV_flag ≠Null，表明si已加入Γ(aj),(j≠i)。

圖1 AUV 節(jié)點(diǎn)分配消息傳遞流程

③執(zhí)行Counter=Counter-1，si給鄰居集合中其他傳感器節(jié)點(diǎn)轉(zhuǎn)發(fā)invite_msg(IDi,Counter)，它們?cè)谑盏皆搱?bào)文后，按②中方式處理。

④重復(fù)②、③至計(jì)數(shù)器Counter變?yōu)?，報(bào)文失效，不再進(jìn)行傳遞，此時(shí)ai分配完畢。

（2）傳感器分組

為便于消息的傳遞和失效節(jié)點(diǎn)的發(fā)現(xiàn)，預(yù)先對(duì)已部署的傳感器進(jìn)行編號(hào)并分組，用二元組（SID，GID）表示傳感器節(jié)點(diǎn)自身編號(hào)和所在組號(hào)。

①在已部署的傳感器節(jié)點(diǎn)中隨機(jī)選擇節(jié)點(diǎn)si編為1 號(hào)，ID 標(biāo)記為（1，1），1 號(hào)為GID1 組的組長(zhǎng)。

②若si的鄰居節(jié)點(diǎn)數(shù)為Nneigh(si)，則Λ(si)中的節(jié)點(diǎn)依次編號(hào)為2,3,…,Nneigh(si)+1，相應(yīng)的ID 設(shè)置為(2,1),(3,1),…,(Nneigh(si)+1,1)。

③1號(hào)節(jié)點(diǎn)編組完成后，向2號(hào)節(jié)點(diǎn)發(fā)送編組指令報(bào)文group_msg(Nneigh(si)+1)，報(bào)文中攜帶了目前已編最大號(hào)數(shù)Nneigh(si)+1，假設(shè)2 號(hào)節(jié)點(diǎn)為sj，其Λ(sj)中有k個(gè)節(jié)點(diǎn)已編號(hào)并分在了組GID1 中，故對(duì)剩余Nneigh(sj)-k個(gè)未編號(hào)節(jié)點(diǎn)進(jìn)行編號(hào)。

④2 號(hào)節(jié)點(diǎn)完成編組后，向其組長(zhǎng)1 號(hào)節(jié)點(diǎn)發(fā)送finish_msg(Nneigh(sj)+Nneigh(si)-k+1) 編組完成報(bào)文，攜帶了目前最大編號(hào)信息，1 號(hào)節(jié)點(diǎn)收到后，向3 號(hào)節(jié)點(diǎn)group_msg(Nneigh(sj)+Nneigh(si)-k+1)編組指令報(bào)文，3號(hào)節(jié)點(diǎn)開(kāi)始編組。

⑤依次進(jìn)行，直到所有傳感器節(jié)點(diǎn)編組完畢。

3.2 失效感知階段

失效感知階段是要及時(shí)發(fā)現(xiàn)失效位置并告知相應(yīng)AUV。節(jié)點(diǎn)失效情況具體分為兩種：

（1）節(jié)點(diǎn)編號(hào)不同與所在組號(hào)，即SID ≠GID

①此類傳感器節(jié)點(diǎn)以Interval為時(shí)間周期向其組長(zhǎng)發(fā)送簽到報(bào)文sign_msg（AUV_flag），包含了自身所屬AUV 的標(biāo)識(shí)AUV_flag。

②若X組組長(zhǎng)si在計(jì)時(shí)器Timer1內(nèi)未收到組員sj的簽到報(bào)文，則向全網(wǎng)發(fā)起對(duì)sj的尋找報(bào)文seek_msg(sj,si)，該報(bào)文攜帶了si和sj的ID。

③網(wǎng)絡(luò)中節(jié)點(diǎn)收到seek_msg(sj,si)后，若不是節(jié)點(diǎn)sj，則繼續(xù)轉(zhuǎn)發(fā)，若sj收到該報(bào)文，則向si返回feedback_msg（new_GID），包含sj所在新組的GID，si在收到feedback_msg（new_GID）后在組成員列表及鄰居集合Λ(si)中將sj刪除；若Timer2 內(nèi)si未收到feedback_msg（new_GID）報(bào)文，則證明sj處已發(fā)生了拓?fù)涫?，si向sj原所屬的AUV發(fā)送愈合請(qǐng)求報(bào)文recovery_msg（sj，Λ(sj)），且si在組成員列表及鄰居集合Λ(si)中刪除sj。

（2）本節(jié)點(diǎn)即為所在組組長(zhǎng)，即SID=GID，另外，編組調(diào)整后也可能出現(xiàn)此類節(jié)點(diǎn)

①此類節(jié)點(diǎn)（這里用s1指代）以Interval為周期向其所屬AUV 節(jié)點(diǎn)ai發(fā)送sign_msg(s1,Λ(s1))簽到報(bào)文，攜帶s1位置信息和鄰居集合信息。

②若其所屬AUV節(jié)點(diǎn)ai在Timer1內(nèi)未收到s1的簽到報(bào)文，則ai向全網(wǎng)發(fā)起對(duì)s1的尋找報(bào)文seek_msg(s1,ai)，該報(bào)文攜帶了s1和ai的ID。

③若在計(jì)時(shí)器Timer2 內(nèi)s1收到了seek_msg(s1,ai)，則向ai返回報(bào)文feedback_msg（new_GID），s1及其原鄰居節(jié)點(diǎn)調(diào)整鄰居集合Λ及編組；若在計(jì)時(shí)器Timer2 內(nèi)未找到s1，則證明s1處發(fā)生了拓?fù)涫?，ai將主動(dòng)進(jìn)行愈合。

3.3 移動(dòng)愈合階段

當(dāng)AUV 獲取了失效位置信息及失效節(jié)點(diǎn)鄰居集合信息后，選擇距失效位置最近的AUV 立即移動(dòng)進(jìn)行拓?fù)溆?，保證移動(dòng)到失效位置耗時(shí)最短。

移動(dòng)愈合階段具體過(guò)程如下：

（1）移動(dòng)位置計(jì)算。AUV 節(jié)點(diǎn)af發(fā)現(xiàn)失效節(jié)點(diǎn)sf后，用公式（4）計(jì)算sf鄰居集合Λ(sf)中所有節(jié)點(diǎn)的中心位置Lcenter，然后af向Lcenter移動(dòng)

Lj為節(jié)點(diǎn)sj的位置，Nneigh(sf)為sf鄰居節(jié)點(diǎn)數(shù)。

（2）AUV 功率調(diào)整。af移動(dòng)到中心位置Lcenter后，由于AUV 信號(hào)發(fā)送功率和接收靈敏度比普通傳感器高很多，可進(jìn)行適當(dāng)減小，降低能耗，保證sf所有鄰居通信，完成拓?fù)溆稀?/p>

（3）后續(xù)處理。當(dāng)af完成了對(duì)失效拓?fù)涞挠虾螅蛩婊景l(fā)送愈合完成消息，水面基站收到該消息后，將af從AUVs 集合A中刪除，并重新進(jìn)行預(yù)處理，將集合A中剩余AUVs 重新分配，并以af作為1 號(hào)節(jié)點(diǎn)重新對(duì)傳感器進(jìn)行編組。

4 仿真與性能分析

采取Monte Carlo實(shí)驗(yàn)，進(jìn)行100輪仿真。在400 m×400 m×400 m 的水下監(jiān)測(cè)區(qū)域，隨機(jī)布置50 個(gè)目標(biāo)事件，用20 個(gè)互通的傳感器完成對(duì)目標(biāo)事件90%以上的覆蓋，部署5 個(gè)AUVs。當(dāng)出現(xiàn)拓?fù)涫?，AUVs 均已用于愈合時(shí)，1 次仿真結(jié)束。

實(shí)驗(yàn)中模型所用參數(shù)如表1、表2 所示。

表1 網(wǎng)絡(luò)模型實(shí)驗(yàn)參數(shù)

表2 水下實(shí)體移動(dòng)模型實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)環(huán)境部署情況如圖2 所示。

圖2 水下目標(biāo)監(jiān)測(cè)區(qū)域部署情況

采用基于AUVs 的MUWSNs 拓?fù)溆纤惴ǖ那闆r（簡(jiǎn)稱AUV-Healing）與不采用愈合算法的情況（簡(jiǎn)稱NO-Healing）進(jìn)行比較。

圖3 顯示了兩種情況下MUWSNs 的連通性，左圖中AUV-Healing 曲線縱坐標(biāo)基本一直維持在1 處，即使拓?fù)涫惯B通性變?yōu)?，也會(huì)迅速被AUV 愈合，連通性恢復(fù)為1；而右圖中的NO-Healing 曲線，當(dāng)拓?fù)涫Ш?，連通性將長(zhǎng)期處于0，網(wǎng)絡(luò)不會(huì)主動(dòng)進(jìn)行愈合，圖中大約46 min 時(shí)NO-Healing 曲線又變?yōu)?，那是因?yàn)閭鞲衅鞴?jié)點(diǎn)受水流影響移動(dòng)過(guò)程中無(wú)意間恢復(fù)了網(wǎng)絡(luò)連通，但很快又失效。

圖3 網(wǎng)絡(luò)連通性比較

為觀察傳感器通信半徑對(duì)MUWSNs拓?fù)淇煽啃缘挠绊?，將傳感器通信半徑分別設(shè)置為30 m、60 m、90 m，在水下實(shí)體移動(dòng)模型影響下進(jìn)行100輪重復(fù)實(shí)驗(yàn)，每輪實(shí)驗(yàn)運(yùn)行100 min，統(tǒng)計(jì)拓?fù)涫Оl(fā)生次數(shù)，結(jié)果如圖4所示。

圖4 拓?fù)涫Т螖?shù)與節(jié)點(diǎn)通信半徑的關(guān)系

從圖中可以看出，傳感器通信半徑越大，MUWSNs拓?fù)浒l(fā)生失效的次數(shù)越少，當(dāng)rc=90 m 時(shí)，對(duì)于每輪實(shí)驗(yàn)來(lái)說(shuō)，失效發(fā)生次數(shù)已非常少，僅有的一些失效可能是由于傳感器節(jié)點(diǎn)移動(dòng)超出目標(biāo)監(jiān)測(cè)區(qū)域范圍而造成的。

5 結(jié)束語(yǔ)

MUWSNs所處的水下環(huán)境為其賦予了動(dòng)態(tài)演化性，拓?fù)溆纤惴ㄊ翘岣進(jìn)UWSNs 可靠性的重要手段[14-15]。本文對(duì)已有的幾個(gè)拓?fù)溆纤惴ㄟM(jìn)行了歸納總結(jié)，分析了它們的局限性，提出了一種基于AUVs 的MUWSNs愈合算法，并構(gòu)建了水下實(shí)體移動(dòng)模型，針對(duì)水下實(shí)體移動(dòng)引起的拓?fù)涫?，AUVs 能夠及時(shí)感知并進(jìn)行快速愈合，極大地提高了MUWSNs 可靠性。仿真實(shí)驗(yàn)證明了本文所提愈合算法的正確性和有效性，具備廣泛的應(yīng)用價(jià)值。

[1] Heidemann J，Stojanovic M，Zorzi M.Underwater sensor networks：Applications，advances and challenges[J].Philosophical Transactions on the Royal Society A，2012，370：158-175.

[2] Blouin S.Intermission-based adaptive structure estimation of wireless underwater networks[C]//Proceedings of the 10th IEEE International Conference on Networking，Sensing and Control（ICNSC），April 2013，2013：130-135.

[3] 劉林峰，吳家皋，鄒志強(qiáng)，等.面向節(jié)點(diǎn)失效問(wèn)題的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)渥杂惴╗J].東南大學(xué)學(xué)報(bào)，2009，39（4）：695-699.

[4] Wang L，Guo Y，Zhan Y.Security topology control method for wireless sensor networks with node-failure tolerance based on self-regeneration[J].Eurasip Journal of Wireless Communications and Networking，2010，16：1-11.

[5] Sekha A，Manoj B，Murthy C.Dynamic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility[C]//Proceedings of the 3rd IEEE Int’1 Conf on Pervasive Computing and Communications，Kauai，Island，2005，51-60.

[6] 劉林峰，劉業(yè).基于滿Steiner 樹(shù)問(wèn)題的水下無(wú)線傳感器網(wǎng)絡(luò)拓?fù)溆纤惴ㄑ芯縖J].通信學(xué)報(bào)，2010，31（9）：30-37.

[7] Erol-Kantarci M，Mouftah H T，Oktug S.A survey of architectures and localization techniques for underwater acoustic sensor networks[J].IEEE Commun Surv Tutor，2011，13（3）：487-502.

[8] Liu Linfeng，Liu Ye，Zhang Ningshen.A complex network approach to topology control problem in underwater acoustic sensor networks[J].IEEE Transactions on Parallel and Distributed Systems，2013（1）：1-12.

[9] Caraivan M C，Dache V，Sgarciu V.Common Framework model for multi-purpose underwater data collection devices deployed with remotely operated vehicles[C]//Proceedings of the 7th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems：Technology and Applications，Berlin，Germany，12-14 September，2013：849-854.

[10] Caraivan M，Dache V，Sgarciu V.Simulation scenarios for deploying underwater safe-net sensor networks using remote operated vehicles：Offshore exploration constructions models and sensor deployment methods[C]//Proceedings of the 19th International Conference on Control Systems and Computer Science，2013：419-424.

[11] Caruso A，Paparella，Vieira LFM，et al.The meandering current mobility model and its impact on underwater mobile sensor networks[C]//Proc of INFOCOM 2008.Piscataway，NJ：IEEE，2008：221-229.

[12] Jafri M R，Ahmed S，Javaid N，et al.AMCTD：Adaptive mobility of courier nodes in threshold-optimized DBR protocol for underwater wireless sensor networks[C]//Proceedings of the 8th International Conference on Broadband，Wireless Computing，Communication and Applications，Compiegne，2013：93-99.

[13] 何明，梁文輝，陳國(guó)華，等.水下移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)鋄J].控制與決策，2013，28（12）：1761-1770.

[14] Cao Jiabao，Dou Jinfeng，Dong Shunle.Design and development of heterogeneous underwater sensor networks[C]//Proceedings of the IEEE 9th International Conference on Mobile Ad-hoc and Sensor Networks（MSN），2013：425-430.

[15] Manjula R B，Sunilkumar S M.Coverage optimization based sensor deployment by using PSO for antisubmarine detection in UWASNs[C]//Proceedings of Ocean Electronics（SYMPOL），2013：15-22.