三維水下無線傳感器網(wǎng)絡(luò)覆蓋方法*

吳克啟， 鄭潤高， 王忠思

(1.海軍士官學(xué)校 信息技術(shù)系，安徽 蚌埠 233012； 2.海軍士官學(xué)校 教保處，安徽 蚌埠 233012)

0 引 言

水下無線傳感器網(wǎng)絡(luò)(underwater wireless sensor networks，UWSNs)是當(dāng)前國內(nèi)外無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)領(lǐng)域的前沿技術(shù)和研究熱點(diǎn)[1,2]。

目前，大多數(shù)關(guān)于傳感器網(wǎng)絡(luò)覆蓋問題的研究都是在二維平面上考慮的，基于二維和陸上環(huán)境的WSNs覆蓋需將目標(biāo)監(jiān)測區(qū)域抽象成二維平面多邊形，然后分析二維平面上的點(diǎn)覆蓋、區(qū)域覆蓋或柵欄覆蓋[3～5]。但隨著WSNs在不同應(yīng)用場景、領(lǐng)域和需求的研究，如在礦井、山嶺、水下、太空等三維(3D)的環(huán)境下，這種忽略高度的二維平面模型已經(jīng)不再適用，必須要在三維環(huán)境中進(jìn)行分析和建模，對(duì)空間進(jìn)行拓展以構(gòu)建三維模型。

本文針對(duì)UWSNs節(jié)點(diǎn)的覆蓋問題提出了三維網(wǎng)絡(luò)模型與最優(yōu)部署模型有效提高了網(wǎng)絡(luò)覆蓋率。

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

1.1 三維網(wǎng)絡(luò)模型

本文研究UWSNs的部署和覆蓋問題，傳感器節(jié)點(diǎn)采用水下固定錨節(jié)點(diǎn)，節(jié)點(diǎn)一旦被部署后不能水平移動(dòng)，只能在垂直方向上任意沉降，監(jiān)測區(qū)域?yàn)槟澈Ｓ蛩乱粋€(gè)長方體區(qū)域F(L×W×H)。節(jié)點(diǎn)感知模型為布爾模型，節(jié)點(diǎn)感知半徑為Rs，通信半徑為Rt。在初始階段，有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)。

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

傳感器節(jié)點(diǎn)的覆蓋模型拓展到三維空間以球形表示，這種覆蓋模型與三維空間內(nèi)的球堆積問題一致。在最密堆積中，許多相同半徑球并置，使其空間利用率達(dá)到最大。

圖1 面心立方格

圖2 三維覆蓋最優(yōu)部署結(jié)構(gòu)

按照以上空間劃分法，推導(dǎo)出節(jié)點(diǎn)數(shù)目計(jì)算公式為

(1)

式中N為實(shí)現(xiàn)完全覆蓋時(shí)需要部署的最少節(jié)點(diǎn)個(gè)數(shù);L，W，H分別為覆蓋區(qū)域的長、寬、高;Rs為節(jié)點(diǎn)感知半徑;[m]為不小于m的最小整數(shù)。

2 基于加權(quán)二分圖完美匹配的節(jié)點(diǎn)選擇與沉降

2.1 二分圖完美匹配模型

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

(2)

滿足以下條件

(3)

式中D=[dij]M×N為距離評(píng)價(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，在距離評(píng)價(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；否則，未指派。且條件限定于解矩陣的每行只能有1個(gè)1，每列只能有1個(gè)1，即1個(gè)理想圖案位置只分配1個(gè)隨機(jī)部署節(jié)點(diǎn)。

2.2 節(jié)點(diǎn)選擇與沉降算法

3 基于聚類算法的覆蓋空洞檢測和修復(fù)方法

3.1 覆蓋空洞檢測

經(jīng)匈牙利算法進(jìn)行節(jié)點(diǎn)指派和沉降后，由于沉降節(jié)點(diǎn)不可能正好在理想圖案位置，總會(huì)存在一定的距離偏差，影響了整體的覆蓋效果，會(huì)存在覆蓋空洞。一般來說，隨機(jī)節(jié)點(diǎn)個(gè)數(shù)M大于完全覆蓋所需最少節(jié)點(diǎn)數(shù)N，即存在冗余節(jié)點(diǎn)。為提高網(wǎng)絡(luò)覆蓋率，考慮利用冗余節(jié)點(diǎn)進(jìn)行覆蓋空洞修復(fù)。對(duì)于覆蓋空洞的檢測，本文提出基于三維泰森圖(3D-Voronoi)晶胞結(jié)構(gòu)的覆蓋空洞檢測算法。

按照文獻(xiàn)[10]對(duì)空間點(diǎn)集Voronoi圖的海量構(gòu)造及生成方法在MATLAB中繪制水下三維區(qū)域內(nèi)由理想部署點(diǎn)形成的三維泰森圖如圖3所示，在空間內(nèi)部，晶胞體呈現(xiàn)規(guī)則的正十二面體，處于區(qū)域邊界的晶胞會(huì)被邊界分割呈現(xiàn)新的形狀。

圖3 部署節(jié)點(diǎn)的三維泰森圖與覆蓋效果

當(dāng)節(jié)點(diǎn)分配指派算法執(zhí)行后，由于指派節(jié)點(diǎn)水平方向上坐標(biāo)的偏差導(dǎo)致出現(xiàn)了不規(guī)則的晶胞體形狀，部分晶胞體頂點(diǎn)遠(yuǎn)離晶核以及其他節(jié)點(diǎn)，則會(huì)出現(xiàn)覆蓋空洞。本文中覆蓋空洞的檢測基于三維泰森圖晶胞體頂點(diǎn)完成，考察其頂點(diǎn)是否被任一部署節(jié)點(diǎn)覆蓋，如果沒有，則記為空洞點(diǎn)。圖4給出了節(jié)點(diǎn)覆蓋球、泰森晶胞和覆蓋空洞點(diǎn)示意，圖中球體為節(jié)點(diǎn)覆蓋球，多面體為節(jié)點(diǎn)泰森晶胞體，晶胞上的頂點(diǎn)為覆蓋空洞點(diǎn)。

圖4 節(jié)點(diǎn)覆蓋球、泰森晶胞和覆蓋空洞點(diǎn)示意

3.2 覆蓋空洞修復(fù)

要實(shí)現(xiàn)對(duì)覆蓋空洞的修復(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)的步驟如下：

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

2)對(duì)所有的空洞點(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 仿真實(shí)驗(yàn)與結(jié)果分析

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

仿真實(shí)驗(yàn)基于MATLAB 7.10.0(2010a)實(shí)現(xiàn)。算法性能評(píng)估以網(wǎng)絡(luò)覆蓋率和連通度為主要指標(biāo)。仿真數(shù)據(jù)采用20次以上實(shí)驗(yàn)計(jì)算所得的平均值，實(shí)驗(yàn)中所用參數(shù)為：網(wǎng)絡(luò)覆蓋區(qū)域F為500 m×500 m×200 m,隨機(jī)部署節(jié)點(diǎn)數(shù)M為150～500,傳感器感知半徑Rs為50 m，傳感器通信半徑Rt為80～100 m，理想部署節(jié)點(diǎn)數(shù)N由式(1)計(jì)算。在仿真實(shí)驗(yàn)中，對(duì)比文獻(xiàn)[11]算法(基于2D-voronoi的節(jié)點(diǎn)深度調(diào)節(jié)算法，記為Voronoi)。本文提出的基于二分圖最佳指派的沉降算法記為BipGraph算法，指派后進(jìn)行覆蓋空洞修復(fù)的算法記為OptBipGraph算法。

4.2 實(shí)驗(yàn)結(jié)果與性能分析

圖5給出了節(jié)點(diǎn)的三維部署，其中左圖為3種算法的三維泰森圖，右圖為3種算法的節(jié)點(diǎn)三維覆蓋效果，從圖中部署節(jié)點(diǎn)的分布來看，本文提出的算法節(jié)點(diǎn)部署后分布更加均勻，節(jié)點(diǎn)空間覆蓋效率更高。

圖5 傳感器節(jié)點(diǎn)三維部署

圖6(a)給出了3種算法網(wǎng)絡(luò)覆蓋率性能(CovRatio)在不同部署節(jié)點(diǎn)數(shù)目(the number of nodes)下的變化情況。可以看出，3種算法覆蓋率均隨部署節(jié)點(diǎn)數(shù)目的增加而增大，其中Voronoi算法性能最差。但隨著部署節(jié)點(diǎn)數(shù)目的增多，當(dāng)M>380時(shí)，Voronoi算法性能優(yōu)于BipGraph算法，這是因?yàn)锽ipGraph算法只部署了理想圖案位置個(gè)數(shù)的節(jié)點(diǎn)，即只沉降部署了N個(gè)節(jié)點(diǎn)，部分冗余節(jié)點(diǎn)并未參與網(wǎng)絡(luò)覆蓋，故最終其覆蓋率曲線趨于平緩。在幾種算法中，本文提出的OptBipGraph算法性能最好，覆蓋率相較于Voronoi算法提高達(dá)15 %。圖6(b)、圖6(c)比較了隨機(jī)部署策略(Random)、Voronoi,OptBipGraph 3種算法的網(wǎng)絡(luò)連通度(GaintTreRatio)性能。從圖(b)可以看出，網(wǎng)絡(luò)連通度隨部署節(jié)點(diǎn)數(shù)目增加而增大，當(dāng)節(jié)點(diǎn)數(shù)目大于200時(shí)，連通度均能達(dá)到95 %以上，當(dāng)節(jié)點(diǎn)數(shù)目大于400時(shí)，連通度均能達(dá)到100 %。從圖6(c)可以看出，網(wǎng)絡(luò)連通度隨節(jié)點(diǎn)通信半徑的增加而增大，當(dāng)節(jié)點(diǎn)通信、感知半徑比Rt/Rs≥1.7時(shí)，網(wǎng)絡(luò)連通度均能達(dá)到95 %以上。Rt/Rs≥2時(shí)，網(wǎng)絡(luò)連通度均達(dá)到100 %。總體上，幾種算法的網(wǎng)絡(luò)連通度性能差異并不大，相比較而言，Voronoi算法在網(wǎng)絡(luò)連通度性能方面略微優(yōu)于OptBipGraph算法，而Random隨機(jī)部署方法性能最差。

圖6 CovRatio和GaintTreRatio性能比較

5 結(jié) 論

本文針對(duì)水下無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋問題，在對(duì)覆蓋區(qū)域進(jìn)行最優(yōu)化網(wǎng)格劃分的基礎(chǔ)上，得出三維空間無線傳感器節(jié)點(diǎn)部署的理想坐標(biāo)點(diǎn)，利用二分圖最佳指派算法，將水面大量隨機(jī)節(jié)點(diǎn)一對(duì)一的分配給理想部署點(diǎn)，并將冗余節(jié)點(diǎn)用于覆蓋空洞的修復(fù)，采用基于三維泰森多面體晶胞結(jié)構(gòu)的覆蓋空洞檢測算法和空洞點(diǎn)集聚類算法部署冗余節(jié)點(diǎn)，以優(yōu)化水下無線傳感器網(wǎng)絡(luò)的覆蓋。仿真結(jié)果表明:與已有的水下三維傳感器網(wǎng)絡(luò)部署算法相比，在保證網(wǎng)絡(luò)連通度性能相當(dāng)?shù)那闆r下，本文提出的算法明顯提升了傳感器網(wǎng)絡(luò)的覆蓋率，性能提升達(dá)到15 %以上。