基于AUVs的水下移動無線傳感器網絡愈合算法

梁文輝，董 強，何 明，陳秋麗，丁晨璐

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

1.解放軍理工大學 指揮信息系統學院，南京210007

2.解放軍61345 部隊

3.解放軍理工大學 第六十三研究所，南京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 引言

水下移動無線傳感器網絡（Mobile Underwater Wireless Sensor Networks，MUWSNs）應用于水下復雜環境，傳感器易受水下生物、水流等外力因素影響發生位置遷移；且傳感器長期受海水腐蝕及浮游生物的附著，逐漸降低靈敏度，易出現節點失效[1]。為推動MUWSNs在水下重要領域應用，高效、合理的拓撲愈合算法至關重要[2]。

目前，針對MUWSNs 拓撲愈合方面的研究成果很少，文獻[3]提出拓撲愈合算法TCS-CA，通過恢復失效節點單跳鄰居間可達性來實現拓撲自愈，但該算法適用于地面無線傳感器網絡，在MUWSNs 中并不適合；文獻[4]針對無線傳感器網絡中出現的覆蓋洞區域，通過播撒第二代節點的方式修復覆蓋洞區域，但播撒的隨機性不能完全保證覆蓋洞區域能夠獲得足夠數量用于修復的新節點；文獻[5]利用已知網絡拓撲的幾何規則，賦予失效節點在離開前決定其鄰居節點移動行為的能力，但這對失效節點提出了很高的要求，較難實現；文獻[6]引入AUV 節點，提出基于滿Steiner 樹問題的拓撲愈合算法，但未對失效節點發現和AUV 選擇等問題做具體的研究，且該方法基于二維平面，難以應用在水下三維環境中。

針對上述問題，本文提出一種基于自主式水下航行器（AUV）[7-9]的MUWSNs 愈合算法，充分考慮水流對MUWSNs 網絡拓撲的影響，構建水下實體移動模型，利用AUVs的自主移動性對MUWSNs失效拓撲進行愈合。

2 網絡建模及問題描述

2.1 網絡建模

在目標監測區域D中，不均勻地分布了M個需監測的目標事件，在區域D中部署N個傳感器節點和K個AUV 節點，傳感器與AUV 均為全向感知，最大感知半徑分別為rs與，最大通信半徑分別為rc與。為便于研究和計算，傳感器和AUV 均采用布爾感知模型。假設初始MUWSNs 網絡拓撲中傳感器節點在目標監測區域D中完成了非均勻部署，網絡全局連通，整個網絡對目標事件集的覆蓋率達到90%以上；AUVs 分布密度與傳感器節點分布密度相匹配[10]。受水下外力因素影響，會出現節點故障或網絡失效，則需AUVs 進行拓撲愈合。

將MUWSNs拓撲抽象為一個三維空間的無向圖，傳感器節點si的鄰居集合為Λ(si)，鄰居節點數為Nneigh(si)，感知半徑為rs(si)，覆蓋范圍為Nsensor(si)={ej|d(ej,si)≤rs(si),j=1,2,…,m}；si能量為e(si)，失效節點標記為sf，對失效節點進行替代的AUV標記為af，AUV速度為VAUV。

為便于模型分析，給出符合實際應用的假設：

假設1水下傳感器節點具備輔助定位系統，能夠知道自身位置及鄰居節點位置，并通過信息交互獲取鄰居節點的鄰居集合Λ(si)。

假設2AUV 可直接通過水面基站與其他AUV 進行通信，并獲取其他AUV 的位置信息。

假設3在整個目標監測任務執行過程中，AUV 能量為+∞，其信息感知收發以及位置移動產生的能耗忽略不計。

假設4K＜＜N，由于AUV造價較高，因此部署數量遠少于水下傳感器節點部署數量。

假設5，并且AUV 能按需在最大值范圍內調節感知半徑和通信半徑的大小。

假設6在AUV 愈合過程中不會發生新失效。

2.2 水下實體移動建模

水下實體包括監測區域內事件、傳感器以及AUVs，水下實體會隨著水流和漩渦等水體流散情況產生運動，從而引起MUWSNs 拓撲的動態變化。水流的運動不是完全隨機的過程，結合一種適合流動類型廣泛的水流運動模型[11-12]來構建水下實體移動模型，可更準確地模擬MUWSNs真實運行狀態。

對于不可壓縮的水流來說，其運動可近似為在二維平面內。在流體力學中，這是一個通用的假設[13]。

用ψ表示二維水流運動場，采用式（1）所示的水流噴射模型來描述水流運動情況：

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

水下實體在水流場ψ內的運動受兩個方向的速度場δ=(u,v)影響，用式（2）表示：

u表示向東的速度場，v表示向北的速度場。用拉格朗日法來描述水下實體在X、Y方向的運動速度，得到式（3）的Hamiltonian 方程：

從上述水下實體移動模型可以看出，坐標為(x,y,z)的水下實體經過時間t后，隨水流移動到了位置(x+x′×t,y+y′×t,z)處。對于X、Y坐標相同但Z坐標不同的水下實體，是以相同模式運動的。

3 算法設計

3.1 預處理階段

（1）AUVs分配

水中AUVs分布密度與傳感器分布密度相匹配。發生拓撲失效時，為使距離最近的AUV 實施愈合，需對每個AUV分配一定規模的傳感器，對ai∈A來說，所負責的傳感器集合表示為Γ(ai)，并且有Γ(ai)∩Γ(aj)=?,(j≠i)。

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

①?ai∈A，向通信范圍內的傳感器節點發送報文invite_msg（IDi，Counter），IDi為ai的身份標識，Counter為計數器，記錄報文傳遞次數，若傳感器節點總數為N，Counter 初始值設為N-1，報文每傳遞1 次，Counter 減1，減至0 時，報文失效。

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

圖1 AUV 節點分配消息傳遞流程

③執行Counter=Counter-1，si給鄰居集合中其他傳感器節點轉發invite_msg(IDi,Counter)，它們在收到該報文后，按②中方式處理。

④重復②、③至計數器Counter變為0，報文失效，不再進行傳遞，此時ai分配完畢。

（2）傳感器分組

為便于消息的傳遞和失效節點的發現，預先對已部署的傳感器進行編號并分組，用二元組（SID，GID）表示傳感器節點自身編號和所在組號。

①在已部署的傳感器節點中隨機選擇節點si編為1 號，ID 標記為（1，1），1 號為GID1 組的組長。

②若si的鄰居節點數為Nneigh(si)，則Λ(si)中的節點依次編號為2,3,…,Nneigh(si)+1，相應的ID 設置為(2,1),(3,1),…,(Nneigh(si)+1,1)。

③1號節點編組完成后，向2號節點發送編組指令報文group_msg(Nneigh(si)+1)，報文中攜帶了目前已編最大號數Nneigh(si)+1，假設2 號節點為sj，其Λ(sj)中有k個節點已編號并分在了組GID1 中，故對剩余Nneigh(sj)-k個未編號節點進行編號。

④2 號節點完成編組后，向其組長1 號節點發送finish_msg(Nneigh(sj)+Nneigh(si)-k+1) 編組完成報文，攜帶了目前最大編號信息，1 號節點收到后，向3 號節點group_msg(Nneigh(sj)+Nneigh(si)-k+1)編組指令報文，3號節點開始編組。

⑤依次進行，直到所有傳感器節點編組完畢。

3.2 失效感知階段

失效感知階段是要及時發現失效位置并告知相應AUV。節點失效情況具體分為兩種：

（1）節點編號不同與所在組號，即SID ≠GID

①此類傳感器節點以Interval為時間周期向其組長發送簽到報文sign_msg（AUV_flag），包含了自身所屬AUV 的標識AUV_flag。

②若X組組長si在計時器Timer1內未收到組員sj的簽到報文，則向全網發起對sj的尋找報文seek_msg(sj,si)，該報文攜帶了si和sj的ID。

③網絡中節點收到seek_msg(sj,si)后，若不是節點sj，則繼續轉發，若sj收到該報文，則向si返回feedback_msg（new_GID），包含sj所在新組的GID，si在收到feedback_msg（new_GID）后在組成員列表及鄰居集合Λ(si)中將sj刪除；若Timer2 內si未收到feedback_msg（new_GID）報文，則證明sj處已發生了拓撲失效，si向sj原所屬的AUV發送愈合請求報文recovery_msg（sj，Λ(sj)），且si在組成員列表及鄰居集合Λ(si)中刪除sj。

（2）本節點即為所在組組長，即SID=GID，另外，編組調整后也可能出現此類節點

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

②若其所屬AUV節點ai在Timer1內未收到s1的簽到報文，則ai向全網發起對s1的尋找報文seek_msg(s1,ai)，該報文攜帶了s1和ai的ID。

③若在計時器Timer2 內s1收到了seek_msg(s1,ai)，則向ai返回報文feedback_msg（new_GID），s1及其原鄰居節點調整鄰居集合Λ及編組；若在計時器Timer2 內未找到s1，則證明s1處發生了拓撲失效，ai將主動進行愈合。

3.3 移動愈合階段

當AUV 獲取了失效位置信息及失效節點鄰居集合信息后，選擇距失效位置最近的AUV 立即移動進行拓撲愈合，保證移動到失效位置耗時最短。

移動愈合階段具體過程如下：

（1）移動位置計算。AUV 節點af發現失效節點sf后，用公式（4）計算sf鄰居集合Λ(sf)中所有節點的中心位置Lcenter，然后af向Lcenter移動

Lj為節點sj的位置，Nneigh(sf)為sf鄰居節點數。

（2）AUV 功率調整。af移動到中心位置Lcenter后，由于AUV 信號發送功率和接收靈敏度比普通傳感器高很多，可進行適當減小，降低能耗，保證sf所有鄰居通信，完成拓撲愈合。

（3）后續處理。當af完成了對失效拓撲的愈合后，向水面基站發送愈合完成消息，水面基站收到該消息后，將af從AUVs 集合A中刪除，并重新進行預處理，將集合A中剩余AUVs 重新分配，并以af作為1 號節點重新對傳感器進行編組。

4 仿真與性能分析

采取Monte Carlo實驗，進行100輪仿真。在400 m×400 m×400 m 的水下監測區域，隨機布置50 個目標事件，用20 個互通的傳感器完成對目標事件90%以上的覆蓋，部署5 個AUVs。當出現拓撲失效，AUVs 均已用于愈合時，1 次仿真結束。

實驗中模型所用參數如表1、表2 所示。

表1 網絡模型實驗參數

表2 水下實體移動模型實驗參數

實驗環境部署情況如圖2 所示。

圖2 水下目標監測區域部署情況

采用基于AUVs 的MUWSNs 拓撲愈合算法的情況（簡稱AUV-Healing）與不采用愈合算法的情況（簡稱NO-Healing）進行比較。

圖3 顯示了兩種情況下MUWSNs 的連通性，左圖中AUV-Healing 曲線縱坐標基本一直維持在1 處，即使拓撲失效使連通性變為0，也會迅速被AUV 愈合，連通性恢復為1；而右圖中的NO-Healing 曲線，當拓撲失效后，連通性將長期處于0，網絡不會主動進行愈合，圖中大約46 min 時NO-Healing 曲線又變為1，那是因為傳感器節點受水流影響移動過程中無意間恢復了網絡連通，但很快又失效。

圖3 網絡連通性比較

為觀察傳感器通信半徑對MUWSNs拓撲可靠性的影響，將傳感器通信半徑分別設置為30 m、60 m、90 m，在水下實體移動模型影響下進行100輪重復實驗，每輪實驗運行100 min，統計拓撲失效發生次數，結果如圖4所示。

圖4 拓撲失效次數與節點通信半徑的關系

從圖中可以看出，傳感器通信半徑越大，MUWSNs拓撲發生失效的次數越少，當rc=90 m 時，對于每輪實驗來說，失效發生次數已非常少，僅有的一些失效可能是由于傳感器節點移動超出目標監測區域范圍而造成的。

5 結束語

MUWSNs所處的水下環境為其賦予了動態演化性，拓撲愈合算法是提高MUWSNs 可靠性的重要手段[14-15]。本文對已有的幾個拓撲愈合算法進行了歸納總結，分析了它們的局限性，提出了一種基于AUVs 的MUWSNs愈合算法，并構建了水下實體移動模型，針對水下實體移動引起的拓撲失效，AUVs 能夠及時感知并進行快速愈合，極大地提高了MUWSNs 可靠性。仿真實驗證明了本文所提愈合算法的正確性和有效性，具備廣泛的應用價值。

[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] 劉林峰，吳家皋，鄒志強，等.面向節點失效問題的無線傳感器網絡拓撲自愈算法[J].東南大學學報，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] 劉林峰，劉業.基于滿Steiner 樹問題的水下無線傳感器網絡拓撲愈合算法研究[J].通信學報，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] 何明，梁文輝，陳國華，等.水下移動無線傳感器網絡拓撲[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.