水下傳感器網(wǎng)絡節(jié)點部署算法*

朱飛,王忠思,姚琦

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

0 引言

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

1 國內(nèi)外研究現(xiàn)狀

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

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

圖1 海底聯(lián)合戰(zhàn)術(shù)監(jiān)視網(wǎng)絡拓撲圖Fig.1 Network topology of undersea joint tactical surveillance

國內(nèi)相關(guān)研究機構(gòu)和高校也已開始著手對水下通信進行研究。近年來，經(jīng)過眾多研究人員的不懈努力，出現(xiàn)了一批重要的研究成果[8]。

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

2 網(wǎng)絡模型與最優(yōu)部署

2.1 網(wǎng)絡模型

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

2.2 三維覆蓋最優(yōu)部署模型

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

2.3 最小節(jié)點數(shù)計算

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

(1)

(2)

(3)

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

3.1 總體方案

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

圖2 空間對稱格結(jié)構(gòu)的Voronoi劃分Fig.2 Voronoi tessellation Via cubic lattice structures

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

3.2圖案節(jié)點選擇PNS

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

(4)

滿足以下條件：

xij={0,1},

(5)

(6)

(7)

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

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

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

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

圖4 網(wǎng)絡連通度修復算法圖例Fig.4 Network connectivity the restoration

的一個圖例。

3.4 覆蓋空洞修復算法CHR

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

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

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

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

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

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

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

第3步：計算K個簇的z軸質(zhì)心；

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

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

4 仿真評估

4.1 仿真環(huán)境與參數(shù)設置

4.2 仿真結(jié)果與分析

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

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

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

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

圖8 幾種算法的網(wǎng)絡連通度比較Fig.8 Network connectivity comparison

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

5 結(jié)束語

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