水下傳感器網絡節點部署算法*

朱飛,王忠思,姚琦

(海軍士官學校 信息通信系，安徽 蚌埠 233012)

0 引言

水下無線傳感器網絡(underwater wireless sensor networks，UWSN)在海洋環境監測、災害預防、資源勘探等民用領域和水下戰術監視、入侵監測、武器偵察定位等軍事領域有著廣闊的應用前景，已經得到世界各國研究機構的極大關注[1]。我國擁有1.8萬km大陸海岸線、1.4萬km島嶼海岸線和300萬km2的管轄海域面積，海洋漁業資源、礦業資源豐富，是我國國民經濟發展的重要源泉[2]。近海3條海上交通線，是我國海上軍事、經濟運輸的大動脈，是海軍溝通各主要基地，實施戰役編隊機動的戰役通道[3]。因此，構建我國重要海區通道的三維監視網絡進行海洋監測偵察、信息搜集，對于確保我國海洋權益、經濟利益、國防安全具有十分重要的戰略意義。

1 國內外研究現狀

最早開展UWSN研究的國家是美國，早在20世紀50年代，美國就在大西洋和太平洋中投入大量經費建設了一個龐大的水聲監測系統(sound surveillance system，SOSUS)，以實施海洋監測[4]和海洋戰術監視。作為美國比較成功的水下網絡之一的美國海軍海網(Seaweb)水下聲學網絡是目前應用較早的具有典型代表意義的水下傳感器網絡項目，美國海軍主要將其用于沿海區域的警戒，這種可布放的自主分布系統能夠實現命令、控制、通信和導航功能，在反潛戰和反水雷領域具有良好的應用效果。此外，日本的地球區域實時監測計劃ARENA、歐洲的海洋氣象監測網絡ESONET、蒙特利海灣研究所MBARI建立的海洋生化監測系統LOBO和海洋監測系統MOOS、北太平洋中鋪設的有纜繩海洋監測系統NEPTUNE工程和設在紐約西長島南部的前沿分析觀測網絡和遙測系統FRONT等[5-7]，目標都是通過UWSN實現海洋多學科、多要素的綜合研究，這些項目的研究和應用為我們提供了重要的參考和借鑒意義。

隨著UWSN研究的興起，許多廠商開始研制并生產水下節點，如澳大利亞DSPComm公司的AquaNetwork系列產品，美國的Teledyne Benthos水聲通信設備，英國的微型水下聲學調制解調器等。目前，Tritech微型水下聲學調制解調器通信距離可以達到500 m，數據傳輸速率為40 bit/s。圖1給出了海底聯合戰術監視網絡的拓撲圖，由水下傳感器節點、水下通信調制解調器、無線通信數據鏈、艦船、飛機和衛星構成一個完整的三維立體網絡，實現對水下入侵目標的監測，特別是對于安靜型潛艇的探測具有重要的戰術價值。

圖1 海底聯合戰術監視網絡拓撲圖Fig.1 Network topology of undersea joint tactical surveillance

國內相關研究機構和高校也已開始著手對水下通信進行研究。近年來，經過眾多研究人員的不懈努力，出現了一批重要的研究成果[8]。

在UWSN的許多應用中，除使用自帶動力系統的機動節點，如水下機器人、自主航行器(autonomous underwater vehicle，AUV)和水下滑翔機(underwater glider，UG)之外，一般均采用水下固定錨節點，進而實現諸如重要戰略通道監視(柵欄覆蓋)、重要海區監視(面覆蓋)和水下監視定位(三維覆蓋)等功能。固定節點的部署方式主要有受控部署和隨機部署2種[9]。在受控部署中，通過計算得出滿足某些條件的特定位置，再將傳感器節點部署于這些特定位置上，這種部署需要進行人工干預以使得節點準確的進入特定位置，其部署效率往往較低。隨機部署一般是使用飛機、艦艇或潛艇將大量節點拋灑在監測水域，爾后這些節點通過錨固定在海底或者通過纜繩連接在水面浮標，從而擴展到水下不同深度實現三維覆蓋。本文研究水下固定節點隨機部署策略的最優化部署方案。

2 網絡模型與最優部署

2.1 網絡模型

節點一旦被部署后不能水平移動，只能在垂直方向上任意沉降，監測區域為某海域水下一個長方體區域F(L×W×H)。節點感知模型為布爾模型，節點感知半徑為Rs，通信半徑為Rc。在初始階段，有M個節點被隨機部署于監測區域二維水面，隨后，這些節點會被錨固定在海底，節點所處深度由連接錨與節點間的纜繩長度所決定。節點在隨機布放后能通過自身的定位系統獲知自身坐標，并傳送給中心節點。

2.2 三維覆蓋最優部署模型

在二維平面中傳感器節點的覆蓋模型是以圓形表示的，而將其拓展到三維空間則是以球形表示，這種覆蓋模型與三維空間內的球堆積問題相一致。球堆積問題[9](sphere packing problem，SPP)是指在已知的空間中找到球最密集的放置方式，一些常見的球堆積結構如簡單立方格、體心立方格和面心立方格已經被廣泛研究和應用，圖2給出了空間對稱格結構的泰森圖劃分[10]。可以看出，簡單立方格結構對于空間的三維泰森圖劃分是立方體，而體心立方格結構和面心立方格結構對于空間的三維泰森圖劃分則分別是截頂八面體和菱形十二面體。

2.3 最小節點數計算

按照以上空間劃分法，令L，W，H分別為覆蓋區域在x，y，z軸方向上的長度;Δx，Δy，Δz分別為節點在x，y，z軸方向上的間距；[m]表示不小于m的最小整數;Rc為節點通信半徑。則完全覆蓋三維區域F(L×W×H)的最小節點數N可由式(1)計算，式(2)中Nt為體心立方格結構部署方案最少節點數，式(3)中Nm為面心立方格結構部署方案最少節點數。

(1)

(2)

(3)

3 基于圖案模型的節點沉降部署算法

3.1 總體方案

本文提出基于理想圖案模型的節點沉降部署方法，分為3步：第1步初始化階段，主要是完成節點的隨機部署和初始拓撲構造，根據節點感知半徑和通信半徑計算最小節點數以及理想圖案位置坐標(圖案計算DPC)，然后將水面隨機部署節點與理想圖案位置一對一的進行匹配(圖案節點選擇PNS)，并保證沉降節點與理想圖案位置的水平距離偏差總和最小。第2步連通度修復階段，本文提出“插入調整法(NCR-IA)”、“調整法(NCR-A)”2種算法，以保證匹配節點沉降到水下區域后仍然能構成一個連通的網絡。第3步覆蓋空洞修復階段，本文提出的覆蓋空洞修復算法CHR[11]，在連通度保證的同時，使得網絡覆蓋率最大化。圖3給出了基于圖案模型的節點沉降部署算法流程。

圖2 空間對稱格結構的Voronoi劃分Fig.2 Voronoi tessellation Via cubic lattice structures

圖3 基于圖案模型的節點沉降部署算法流程Fig.3 Flowchart of Nodes sinking algorithm via pattern model

3.2圖案節點選擇PNS

圖案節點選擇采用加權二分圖完美匹配方法，將水面大量隨機部署節點(子集A)基于距離權值一對一的分配給區域內的理想圖案位置(子集B)，實現“N項目”與“N目標”的最佳匹配。對該目標分配問題進行建模，現設子集A中隨機節點個數為M，子集B中圖案位置(最少節點數)為N，則目標分配問題的模型可以描述為

(4)

滿足以下條件：

xij={0,1},

(5)

(6)

(7)

式中：D=(dij)M×N為距離評價矩陣，dij為第j個隨機節點距離第i個理想部署點的水平歐式距離。

因為錨節點在垂直方向的高度可以根據需要任意調節，因此節點沉降后其垂直方向上的距離差Δz=0，在距離評價矩陣中只考慮隨機部署節點與理想部署位置的水平歐式距離。令X=(xij)M×N為節點目標分配的解矩陣，當xij值為1時，表示隨機部署節點i指派給理想部署位置j，否則，未指派。條件(6)限定解矩陣的每一行只能有一個1，即一個隨機部署節點只指派一個理想圖案位置，條件(7)限定解矩陣的每一列只能有一個1，即一個理想圖案位置只分配一個隨機節點。

3.3 連通度修復算法NCR-A和NCR-IA

待上述匹配節點沉降至水下后，為檢查和修復網絡連通度，首先需要找出N個沉降節點哪些構成連通的網絡，哪些相互之間不連通。采用圖論中適用于遍歷和搜索樹或圖數據結構的廣度優先算法[12](breadth-first search，BFS)找出匹配節點中不連通的網絡分區，即子網S1，S2，…，Sn，然后對其進行連通度修復。圖4給出本文網絡連通度修復算法

圖4 網絡連通度修復算法圖例Fig.4 Network connectivity the restoration

的一個圖例。

3.4 覆蓋空洞修復算法CHR

一般來說，隨機節點個數M大于完全覆蓋所需最少節點數N，即存在冗余節點。為提高網絡覆蓋率，考慮利用冗余節點進行覆蓋空洞修復。對于覆蓋空洞的檢測和修復，本文提出基于三維泰森圖(3D-Voronoi)晶胞結構的覆蓋空洞檢測方法和基于K-means聚類算法的覆蓋空洞修復方法。

首先，三維泰森圖的定義如下：設P={p1,p2,…,pn}?R3是三維空間的n個點，d={p,pi}為空間任一點p和pi之間的歐式距離，將由V(pi)=∩j≠i{p∈R3|d(p,pi)

要實現對覆蓋空洞的修復，需要將冗余節點沉降到覆蓋空洞的位置。設節點指派后的冗余節點個數為M-N，令其等于K，則空洞點集H的聚類個數為K，聚類簇的質心位置為冗余節點的沉降位置。由于空洞點集的密集程度與該區域空洞點的大小之間存在一定的相關性，即一般來說空洞點密集的地方覆蓋空洞也較大。鑒于以上特征，冗余節點可以指派到覆蓋空洞點集的簇心位置，由于部署節點只能在初始部署位置的垂直方向沉降，因此K個聚類簇的簇心只能是簇成員的z軸質心。使用K-means聚類算法得到K個沉降坐標的步驟如下：

圖5 部署節點的三維泰森圖與覆蓋效果圖Fig.5 3D-Voronoi of deployment nodes and the coverage effect

圖6 節點覆蓋球、泰森晶胞和覆蓋空洞點示意圖Fig.6 An illustration of coverage sphere, voronoi cell, uncovered vertexes

第1步：隨機賦予K個剩余節點一個z坐標，聯合其水平坐標，作為K個初始簇心；

第2步：對所有的空洞點計算其到每個簇心的距離，并聚類到距離最近的簇心；

第3步：計算K個簇的z軸質心；

第4步：迭代2～3步直至每個簇中點集成員不再發生變化，算法結束。

得到的K個簇的簇心位置即為冗余節點的沉降位置，冗余節點沉降后能夠盡量多地覆蓋空洞點，從而實現覆蓋空洞的修復。

4 仿真評估

4.1 仿真環境與參數設置

4.2 仿真結果與分析

圖7比較了幾種算法的網絡覆蓋率。從圖7a)可以看出，網絡覆蓋率隨節點數目增加而增大，但趨勢會逐步放緩。RANDOM方法保證了節點在目標區域的均勻分布，因此，其性能稍微優于CACC算法，而與URSA算法相當。需要注意的是，MCOA算法作為一種通過全局搜索節點最佳沉降位置的窮舉算法，在網絡覆蓋率性能上始終保持最優，但是該算法的時間復雜度很大。從圖7b)可以看出，在部署節點數目不變的情況下，網絡覆蓋率隨節點通信半徑增加而增大，但趨勢會逐步放緩，而RANDOM方法和MCOA算法保持不變，這是因為該2種方法的部署不保證網絡連通度，而本文提出的算法和CACC算法、URSA算法均需要保證網絡的全連通，當節點通信半徑增加時，這些算法會增加節點距離以減少節點間的覆蓋重疊區域，因此，網絡覆蓋率會隨節點通信半徑增大而增加。綜合兩圖來看，在保證網絡連通度的前提下，本文提出的算法與CACC算法和URSA算法相比，網絡覆蓋率性能提高平均達8%～9%和3%～4%。

圖8比較了幾種算法的網絡連通度。從圖中可以看出，對于RANDOM和MCOA算法，無論是增加部署節點數量還是增大節點通信半徑，都對網絡連通度的提高有幫助。而本文提出的算法和CACC算法、URSA算法均能保證網絡的全連通，連通度達到100%。

表1給出了幾種算法的時間復雜度，μ表示算法的執行周期均值，σ表示方差，節點通信半徑Rc=70 m。MCOA算法作為一種窮舉算法，在每次迭代中均需要重復計算網絡覆蓋率，因此耗費了大量時間。本文提出的算法時間復雜度稍微大于CACC和URSA算法，這是因為在連通度修復階段，可能需要進行一些迭代找出修復節點所處的最佳深度。但總體來看，本文算法和CACC算法、URSA算法，時間復雜度均處于同一數量級，明顯低于MCOA算法。

圖7 幾種算法的網絡覆蓋率比較Fig.7 Network coverage ratio comparison

圖8 幾種算法的網絡連通度比較Fig.8 Network connectivity comparison

表1 仿真實驗中的參數設置Table 1 Comparison of the complexity of different algorithms

5 結束語

本文研究了連通度保證下的水下傳感器網絡三維覆蓋優化問題。針對水下固定錨節點一經部署，水平坐標無法改變的問題，提出了基于圖案模型的節點選擇與沉降三步解決方案。仿真結果表明，提出的算法在保證網絡連通度的情況下，具有更好的網絡覆蓋率性能，與集中式算法相比，能有效降低算法的時間復雜度。該方法研究的初衷雖然是解決水下監視網絡三維覆蓋問題，分析可知，其可推廣到礦山、森林、國土邊界、太空等任何一個三維空間實施有效的監視覆蓋，進而實現偵察定位、預警探測、災害預防等軍民應用領域。