Research on Directional Path Coverage Enhancement Algorithm of Multiple Objects in 3D Underwater Mobile Sensor Networks*

ZHANGMeiYan，CAIWenYu，ZHOU LiPing

(1.Department of Electrical Engineering，Zhejiang Water Conservancy and Hydropower College，Hangzhou 310018，China; 2.School of Electronics and Information，Hangzhou Dianzi University，Hangzhou 310018，China)

Research on Directional Path Coverage Enhancement Algorithm of Multiple Objects in 3D Underwater Mobile Sensor Networks*

ZHANGMeiYan1，CAIWenYu2*，ZHOU LiPing1

(1.Department of Electrical Engineering，Zhejiang Water Conservancy and Hydropower College，Hangzhou 310018，China; 2.School of Electronics and Information，Hangzhou Dianzi University，Hangzhou 310018，China)

Collaborative tracking ofmultiplemoving targets inmobile 3D underwater sensor networks remains to be a conundrum;therefore，this paper presents a distributed multi－target path coverage enhancement algorithm to be directed against above problem.Underwater sensor nodes are assumed to bemobile due to ocean current and the detective targets have the ability of autonomousmobility in practicalmobile 3D underwater sensor networks.Themovement law of underwater sensor nodes and multiplemoving targets comply with Meandering Current Mobilitymodels and Random Walkmobilitymodel based on probability respectively.In our algorithm，themaximal path coverage ratio of multi－target trajectory paths is achieved by the collaborative decision－making within the two－hop neighbor nodes.The directional coverage orientations is decided with the objective tomaximize path coverage ratio，moreover，the coverage ratio standard deviation of different target trajectory paths remains to be as small as possible.Finally，the effectiveness of distributed coverage enhancement algorithm is verified by MATLAB simulation and the results proved significantly improvement ofmulti－target path coverage ratio.

underwater sensor networks;mobile sensor networks;3D sensor networks;directional coverage; objects tracking

隨著海洋資源勘探、海洋生物開發、海洋環境觀測、海底入侵檢測等技術需求的不斷發展，水下傳感器網絡［1，2］逐漸成為了無線傳感器網絡領域中的一個研究熱點，很多研究者認為水下傳感器網絡是未來海洋監測技術的主要方式。相比較于傳統的無線傳感器網絡，水下傳感器網絡具有近乎苛刻的條件限制:傳輸帶寬小、網絡延時大、拓撲結構易變、節點價格昂貴等。因此，很多陸地無線傳感器網絡的研究成果基本上無法直接應用于水下傳感器網絡，水下傳感器網絡技術的研究面臨著巨大的挑戰，還存在很多未解決的理論問題。本文就基于水下傳感器網絡的多目標覆蓋與追蹤技術［3］進行研究。

水下傳感器網絡中傳感器節點部署在三維立體空間內，每個節點會隨著水流的移動而運動，網絡拓撲結構并不固定，因此可稱為三維水下移動傳感網。具有運動能力的水下移動目標穿越監測區域時，要求三維水下移動傳感網絡能實時監測移動目標的穿越特征，同時追蹤移動目標的運動軌跡，因此必須盡可能提高移動路徑的覆蓋效率。由于傳感器節點對于移動目標的檢測往往不可能是全視角的，只能在有限的角度范圍內檢測目標，因此屬于有向覆蓋［4］。相比較于傳統的無線傳感器網絡，本文所研究的三維水下移動傳感網具有三大特殊性:三維立體感知、節點隨機移動、目標覆蓋有向，這些特殊屬性決定了三維水下移動傳感網中有向路徑覆蓋問題的研究具有創新點，傳統研究很難直接應用于本文所研究的目標對象，因此對水下傳感網這個特殊形式的研究具有一定的創新性。本文假設傳感器節點可以在若干個覆蓋方向內選擇轉動，研究如何協同地進行目標移動路徑中傳感器節點有向覆蓋方向的優化選取，使得多個運動目標的整個運動路徑被三維水下移動傳感器網絡所監測到的概率最大。

無線傳感器網絡日益應用于真實三維場景監測，基于三維感知模型的水下傳感器網絡屬于典型的三維傳感器網絡，三維立體傳感器網絡相比較二維平面傳感器網絡，并不是簡單地增加了一個維度，而要考慮到更多的約束條件［5］。目前關于傳感器網絡的覆蓋控制算法多假設傳感器節點是靜態的，所提出改善網絡覆蓋性能的方法都是優化調整有向節點感知方向［6］，而水下傳感器網絡受海流作用是一個移動傳感網。海洋中水流的運動受鹽度、風向、溫度、地質輪廓、暗礁等很多因素影響，近年來也有一些關于水流運動模型的研究，相關綜述見文獻［7］。一般而言，海流運動接近于一種隨機過程，精確地獲取水流動模型并不是一件容易的事情。而且，不同地區的海流運動特征并不一致，文獻［8］對此作了詳細的介紹。對于水下傳感器網絡的應用而言，如何實現水下移動節點之間的協作感知，實現有效地對運動目標進行持續性追蹤覆蓋［3］，是近幾年來的一個研究熱點。文獻［9－10］從信號分析與處理的角度闡述了目標追蹤的優化處理過程，并沒有考慮到目標是否被覆蓋到，而移動目標的一定覆蓋率保證是目標實現可能追蹤的必要條件。本文假設用于水下運動目標檢測與追蹤的水下傳感器節點只具有向覆蓋能力。水下傳感器節點的目標探測能力往往也具有方向性，因此屬于有向覆蓋。傳統的有向覆蓋研究假定傳感器節點位置保持不變，某一時刻傳感器節點的感知方向可以優化目標進行調整。陶丹等［11］人在方向可調感知模型的基礎上，提出了基于虛擬勢場的路徑覆蓋增強算法，有向傳感器網絡路徑覆蓋增強算法對應的是對連續路徑上的離散軌跡點進行覆蓋，對于連續路徑，每個一定間隔選取一個軌跡點，從而連續路徑覆蓋的問題就轉化為離散運動軌跡點的覆蓋，文獻［5］也提出了一種新型的多目標有向覆蓋機制，但是以上研究都沒有綜合考慮節點和目標的移動性。如何針對水下傳感器網絡這一特殊的研究對象，實現多運動目標追蹤的前提——提高路徑覆蓋增強，是本文的研究目標。

1 網絡模型定義

1.1 相關定義

本文假設水下傳感器網絡部署在三維空間內，傳感器節點會隨著水流在三維空間內緩慢移動，因此稱為水下三維移動傳感網。本文假設每個傳感器節點的感知范圍是有向的，而且有向覆蓋傳感器節點不具有自主運動能力，但是具有切換覆蓋方向的能力。三維空間內存在若干個運動目標，具有一定的運動軌跡。水下三維移動傳感器網絡的目標是最大限度地覆蓋追蹤到多個水下移動目標，由于水下傳感器節點往往只有有限的角度范圍內才能監測到目標，所以本文研究的問題歸屬于多目標有向路徑覆蓋問題——在所有傳感器節點隨水流緩慢移動的前提下，多個移動目標具有特定的三維運動軌跡，如何實時調度各個傳感器節點的覆蓋方向，以達到目標的移動路徑被盡量多的傳感器節點所覆蓋。本文后續需要用到各類符號的相關定義如表1所示。

表1 符號定義

1.2 有向路徑覆蓋模型

水下傳感器節點的三維有向覆蓋模型(3-D Directional Coverage Model)指水下傳感器節點的感知范圍是一個以節點P＜X，Y，Z＞為球心、半徑Rmax為其最大有向感知半徑、夾角為α的球頂錐體(Spherical Cone)區域，有向覆蓋球頂錐體中心線向量V→—p的矢量角度為〈θxy，θz〉，如圖1所示。因此，每個水下有向傳感器節點模型都可以用一個六元組N＜X，Y，Z，Rmax，α，〈θxy，θz〉＞來表示，分別表示每個有向感知節點的三維中心位置坐標，最大有向感知半徑，感知視角(Field of View，FoV)及三維感知方向角。

圖1 三維有向感知節點模型

定義1有向覆蓋:若目標O被節點N＜X，Y，Rmax，α，〈θxy，θz〉＞有向覆蓋，則意味著O到N的距離小于Rmax，且向量的方向位于(+α/ 2］。的水平面角度θxy從X軸正半軸為0開始，逆時鐘方向選擇逐漸變大，最后以2π結束，θxy∈［0，2π)的垂直面角度θz從Z軸正半軸為0開始，順時鐘方向選擇逐漸變大，最后以2π結束，θz∈［0，2π)。

1.3 節點移動模型

本文假設水下傳感器節點隨水流的移動模型遵從Meandering Current Mobility(MCM)［12－13］模型，如圖2所示。由于水下傳感器節點自身配重決定了其離底高度，或者離地高度由海底重物或浮標固定不變，相比較水流在水平方向的運動幅度，垂直方向上的運動可以忽略［14－15］，因此二維的MCM模型完全可以適用水下三維移動傳感網。

水下傳感器節點的移動軌跡可以用求解漢密爾頓常微分方程來獲取:

其中，流函數

B(t)=A+εcos(ωt)，綜合考慮了洋流和漩渦的作用。根據參考文獻［16］，取如下典型值:A=1.2，c= 0.12，k=2π/7.5，ω=0.4，ε=0.3。

圖2 Meandering Current Mobility運動模型中流函數

1.4 目標運動軌跡

水下目標運動路徑的可預測性是一個非常有用的屬性，本文假設AUV等水下移動目標的運動軌跡采用基于概率的Random Walk移動模型。Random Walk是一種無記憶的運動模型，當前運動的速度與方向與上一時刻無關，基于概率的Random Walk是Random Walk算法的有記憶改進，基于前一時刻用－1表示、當前時刻用0來表示，下一時刻用1來表示，P(a，b)表示從狀態a到狀態b的轉換概率。假設水下移動目標的三維運動軌跡彼此獨立，因此有如下狀態轉移圖(圖3)。

圖3中，三維坐標的狀態轉換矩陣如下公式:

圖3 狀態轉移圖

本文假設三維方向每維的坐標狀態轉換矩陣相同，取如下典型值:

1.5 最優化模型

定義2目標軌跡路徑有向覆蓋——目標軌跡路徑有向覆蓋是一個時變函數Fc(t)，隨著目標沿著軌跡運動，每個離散時刻運動目標被是否被有向覆蓋的函數，函數值為該目標被傳感器節點有向覆蓋的數量，最大值為N。

定義3多目標軌跡路徑有向覆蓋——多個目標運動軌跡路徑有向覆蓋的時變函數集合{(t)i=1，2，3，…}。

定義4目標軌跡路徑有向覆蓋率——以路徑中T為全部軌跡點數，運動目標路徑被覆蓋的軌跡點數與全部軌跡點數之間的比值。

定義5多目標軌跡路徑有向覆蓋率平均值與方差——多個目標軌跡有向覆蓋率的平均值與標準方差。如果平均值越大則表明多目標被有向路徑覆蓋的情況越好，如果標準方差值越小則表明每個目標被有向路徑覆蓋越均勻。

多目標路徑有向覆蓋的優化模型如下所示:在水下三維移動傳感網傳感器節點特定的移動模型條件下，多個運動目標沿著各自的運動模型軌跡移動，水下有向傳感器節點通過協同調度各自的有向覆蓋方向，達到多目標軌跡路徑有向覆蓋率平均值最大，并使多目標軌跡路徑有向覆蓋率標準方差盡量小。

假設存在如下變量ωpi:

?i=1…N，j=1…B，p=1…W，t=1，…，T(6)那么多目標有向路徑覆蓋增強的優化模型可表示為:

其中約束條件為:

2 多目標路徑有向覆蓋增強算法

針對大規模的三維水下移動傳感網，路徑覆蓋算法要求通信代價小和收斂速度快，本文根據運動目標的路徑軌跡模型設計了一種分布式的多目標路徑有向覆蓋增強算法。本文假設三維水下移動傳感網中所有傳感器節點是同構的，具有相同的感知半徑和感知角度，也都能了解自身的位置信息和覆蓋方向。在路徑覆蓋過程中，傳感器節點不具有自身位置的主動調整能力，只能通過旋轉來調整傳感器節點的感知方向。

對于目標移動路徑的覆蓋，只有傳感器節點與軌跡之間的距離小于傳感器有向覆蓋半徑才能生效，如圖4所示，因此本文算法中需調整覆蓋方向的傳感器節點都限制在路徑軌跡的2倍有向感知最大距離區域內。對路徑上某個軌跡點兩個傳感器節點同時能夠覆蓋，但是鄰近的軌跡點卻沒有任何傳感器節點對其進行覆蓋，這種現象導致局部最小而無法實現感知方向的優化，最終路徑上軌跡點的總覆蓋率不高。如圖4所示，對于路徑軌跡點R1，傳感器節點N1和N2此時的方向都能實現有向覆蓋，但是對于路徑軌跡點R2，傳感器節點N2必須旋轉方向才能覆蓋，否則路徑軌跡點R2就變成覆蓋孤點;同樣，對于路徑軌跡點R3，傳感器節點N3此時的方向能實現有向覆蓋，但是卻無法覆蓋路徑軌跡點R4，路徑軌跡點R4就變成覆蓋孤點。

圖4 路徑有向覆蓋增強算法示例

本文研究的多目標路徑有向覆蓋增強算法運行于路徑軌跡2倍感知距離范圍內所有傳感器節點集合。集合中的每個傳感器節點通過Beacon消息交互，收集其兩跳鄰居節點的覆蓋方向數據，每個節點根據自身收集到的覆蓋方向數據，計算出自身每個方向的效用函數值，效用函數值表示有向節點覆蓋某個目標或目標集合時，有向節點對路徑覆蓋質量的貢獻。算法偽代碼如圖5所示，其中定義的效用函數值表明:如果節點某一方向所覆蓋的目標數占其兩跳鄰居比例數越大，該方向的效用函數值越大，節點優先選擇該方向，最終在兩跳鄰居節點范圍內實現協同優化調度。

圖5 多目標有向路徑覆蓋增強算法

3 仿真與分析

3.1 仿真設置

本文利用Matlab仿真軟件，通過一系列仿真實驗分析和驗證本文提出算法的有效性，對比多目標路徑有向覆蓋增強算法與傳感器節點隨機選擇工作方向的隨機覆蓋兩種算法的性能。由于目前三維水下移動傳感網的多目標有向路徑覆蓋研究沒有已公開的成熟研究成果，所以本文的驗證過程只能跟隨機算法進行性能比較。仿真場景設置如下:N=100個傳感器節點和B=3個運動目標隨機分布在500 m×500 m×500 m覆蓋區域內，B=3個運動目標的初始位置都是覆蓋區域的中心(250 m，250 m，250 m)，節點感知半徑為50 m，有向覆蓋球頂錐體覆蓋角α為90°，有向覆蓋球頂錐體中心線向量—的水平面角度θxy從X軸正半軸為0開始，逆時鐘方向選擇逐漸變大，最后以2π結束，θxy∈［0，2π);—的垂直面角度θz從Z軸正半軸為0開始，順時鐘方向選擇逐漸變大，最后以2π結束，θz∈［0，2π)。為了簡單起見，本文假設每個傳感器。多個目標運動模型和傳感器節點移動模型如上文所述，假定路徑軌跡點位置信息已通過其他方式獲取，路徑軌跡點間隔為10 m，仿真總周期數為T=50。為了剔除本文算法仿真結果的隨機因素，所有仿真結果都是20次模擬實驗的平均抽樣結果。

3.2 仿真結果

圖6為本文仿真設置的場景圖，N=100個傳感器節點和B=3個運動目標隨機分布在500 m×500 m×500 m區域內，節點感知半徑為50 m的球型覆蓋情況。圖7為本文仿真設置的節點移動軌跡圖，遵從Meandering Current Mobility模型，圖8為3個運動目標路徑軌跡圖，遵從基于概率的Random Walk移動模型。本文算法的主要驗證指標采用上文定義的目標軌跡路徑有向覆蓋率，表2為多目標路徑有向覆蓋增強算法性能的比較結果，本文算法在統計結果上明顯優于隨機有向覆蓋機制(隨機有向覆蓋機制的路徑覆蓋率均值為0.72，多目標路徑有向覆蓋增強算法的路徑覆蓋率均值為0.84)，但是多目標軌跡路徑有向覆蓋率方差改進效果不明顯(隨機有向覆蓋機制和多目標路徑有向覆蓋增強算法的路徑覆蓋率的方差都是0.06)。這是由于本文算法并沒有以多個移動目標路徑覆蓋率的均衡性為優化目標，而要考慮多個目標路徑均衡性必須從全局對網絡拓撲結構進行集中式考慮。

圖6 仿真設置場景示例

圖7 節點移動軌跡圖(T=0，10，40，50)

表2 路徑有向覆蓋性能比較

圖8 運動目標路徑軌跡圖

4 總結

本文研究了水下傳感器網絡中一種多目標路徑有向覆蓋增強算法:傳感器網絡范圍內水下多個運動目標沿著各自的運動模型軌跡移動，節點通過協同調度各自的有向覆蓋方向，達到多目標軌跡路徑有向覆蓋率平均值最大，并使多目標軌跡路徑有向覆蓋率標準方差盡量小。本文提出的多目標路徑有向覆蓋增強算法屬于分布式算法，每個傳感器節點只需在其兩跳鄰居節點內進行消息交互和覆蓋方向遴選。最后通過仿真分析比較，驗證了本文提出的算法可以提高路徑的覆蓋性能。下一步工作將繼續完善三維移動水下傳感器網絡模型，提出性能更優和代價更小的分布式多目標追蹤算法。

［1］Akyildiz I F，Pompili D，Melodia T.Underwater Acoustic Sensor Networks:Research Challenges［J］.Ad Hoc Networks，2005，3 (2):257－279.

［2］鄭君杰，李延斌，尹路，等.水下傳感器網絡系統架構與體系結構研究［J］計算機科學，2013，40(6A):251－254.

［3］周圣賢.水下傳感器網絡目標跟蹤算法研究［D］.浙江大學，2013.

［4］陶丹，馬華東.有向傳感器網絡覆蓋控制算法［J］.軟件學報，2011，22(10):2317－2334.

［5］張寶利，于峰崎，張足生.一種能量有效的三維傳感器網絡覆蓋控制算法［J］.傳感技術學報，2008，22(2):258－263.

［6］張美燕，蔡文郁.無線視頻傳感器網絡有向感知K覆蓋控制算法研究［J］.傳感技術學報，2013，26(5):728－733.

［7］Caruso A，Paparella F，Vieira L，etal.The Meandering CurrentMobility Model and Its Impact on Underwater Mobile Sensor Networks［C］//Proc IEEE Infocom，Phoenix，AZ，USA，2008:1－8.

［8］Luo Ji，Wang Dan，Zhang Qian.On the Double Mobility Problem forWater Surface Coveragewith Mobile Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23(1): 146－159.

［9］Kelli A C Baumgartner，Silvia Ferrari，Anil V Rao.Optimal Control of an Underwater Sensor Network for Cooperative Target Tracking［J］.IEEE Journal of Oceanic Engineering，2009，34(4):678－697.

［10］Gokhan Isbitiren，Ozgur B Akan.Three－Dimensional Underwater Target Tracking with Acoustic Sensor Networks［J］.IEEE Transactions on Vehicular Technology，2013，60(8):3897－3906.

［11］陶丹，馬華東，劉亮.視頻傳感器網絡中路徑覆蓋增強算法研究［J］.電子學報，2008，36(7):1291－1296.

［12］Pedlosky J.Ocean Circulation Theory［M］.Heidelberg:Springer－Verlag，1996.

［13］Samelson R M，Wiggin S.Lagrangian Transport in Geophysical Jets and Waves.The Dynamical Systems Approach，ser.Interdisciplinary Applied Mathematics［M］.Springer－Verlag，2006，31.

［14］Bower A S.A Simple Kinematic Mechanism for Mixing Fluid Parcels Across a Meandering Jet［J］.JPhys Ocean，1991，21(1):173－180.

［15］Samelson R M.Fluid Exchange Across a Meandering Jet［J］.J Phys Ocean，1992，22(4):431－440.

［16］Tolety V.Load Reduction in Ad Hoc Networks Using Mobile Servers［D］.Master’s thesis，Colorado School of Mines，1999.

張美燕(1983－)，女，講師，從事無線傳感網絡、新型能源技術、物聯網技術等研究，主持浙江省自然科學基金1項，參與浙江省廳級項目多項。近年來發表論文20余篇，被三大索引收錄近10篇，申請發明專利6項;

蔡文郁(1979－)，男，博士，副教授，主要從事無線通信、物聯網、無線傳感網及嵌入式技術研究。主持和參與國家自然科學基金2項、浙江省自然科學基金1項、國家863計劃項目1項、國家海洋局公益項目1項、浙江省重大科技專項1項，橫向課題10余項。近五年發表論文30余篇，被三大索引收錄20余篇，申請專利及軟著30余項，授權20余項，dreampp2000@163.com。

三維水下移動傳感網多目標有向路徑覆蓋增強機制研究*

張美燕1，蔡文郁2*，周麗萍1

(1.浙江水利水電學院電氣工程系，杭州310018;2.杭州電子科技大學電子信息學院，杭州310018)

水下傳感網中實現多個移動目標的協同追蹤任是一個技術難題，針對這個問題論文提出了一種分布式的多目標有向路徑覆蓋增強算法。在實際的三維水下傳感網中，水下傳感器節點會隨著水流運動而移動，被追蹤的目標具有自主行動能力。假設移動規律遵從Meandering CurrentMobility模型，多個運動目標沿著基于概率的Random Walk移動模型軌跡運動。在論文提出的算法中，覆蓋運動路徑的傳感器節點通過兩跳鄰居節點范圍內的水下傳感器節點協同決策來實現最大化路徑覆蓋，通過調整水下傳感器節點自身的有向覆蓋方向達到多目標軌跡路徑有向覆蓋率平均值最大，并使多目標軌跡路徑有向覆蓋率標準方差盡量小。最后論文通過MATLAB軟件仿真來驗證分布式覆蓋增強算法的有效性，能夠顯著提高多個移動目標的路徑覆蓋率。

水下傳感網;移動傳感網;三維傳感網;有向覆蓋;目標追蹤

TP393

A

1004－1699(2014)01－0100－07

2013－07－10修改日期:2013－11－08

C:7230

10.3969/j.issn.1004－1699.2014.01.019

項目來源:國家自然科學基金項目(61102067);浙江省自然科學基金項目(LQ12F03006);水聲通信與海洋信息技術教育部重點實驗室(廈門大學)開放課題項目;浙江省重中之重學科“海洋機電裝備技術”開放基金項目