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

吳克啟， 鄭潤高， 王忠思

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

0 引 言

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

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

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

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

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

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

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

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

圖1 面心立方格

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

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

(1)

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

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

2.1 二分圖完美匹配模型

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

(2)

滿足以下條件

(3)

式中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；否則，未指派。且條件限定于解矩陣的每行只能有1個1，每列只能有1個1，即1個理想圖案位置只分配1個隨機部署節(jié)點。

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

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

3.1 覆蓋空洞檢測

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

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

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

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

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

3.2 覆蓋空洞修復

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

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

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

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

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

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

4 仿真實驗與結果分析

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

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

4.2 實驗結果與性能分析

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

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

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

圖6 CovRatio和GaintTreRatio性能比較

5 結 論

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