朱飛,王忠思,姚琦

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.3 最小節(jié)點(diǎn)數(shù)計(jì)算

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

(1)

(2)

(3)

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

3.1 總體方案

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

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

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

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

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

(4)

滿足以下條件：

xij={0,1},

(5)

(6)

(7)

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

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

3.3 連通度修復(fù)算法NCR-A和NCR-IA

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

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

的一個(gè)圖例。

3.4 覆蓋空洞修復(fù)算法CHR

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

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

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

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

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

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

第2步：對所有的空洞點(diǎn)計(jì)算其到每個(gè)簇心的距離，并聚類到距離最近的簇心；

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

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

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

4 仿真評估

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

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

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

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

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

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

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

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

5 結(jié)束語

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