王 軍，孫小玲，程 勇

（1.南京信息工程大學(xué) 計算機與軟件學(xué)院，江蘇 南京 210044；2.南京信息工程大學(xué)網(wǎng)絡(luò)信息中心，江蘇 南京 210044）

三維無線傳感器網(wǎng)絡(luò)K重覆蓋機制研究*

王 軍1，2，孫小玲1，程 勇2

（1.南京信息工程大學(xué) 計算機與軟件學(xué)院，江蘇 南京 210044；2.南京信息工程大學(xué)網(wǎng)絡(luò)信息中心，江蘇 南京 210044）

針對傳感器節(jié)點在三維監(jiān)測區(qū)域中隨機分布覆蓋效率低下，并且不能達(dá)到關(guān)鍵區(qū)域重覆蓋的問題，本文使用空間填充多面體，分別從確定性覆蓋和隨機覆蓋兩個方面，提出理想狀態(tài)下覆蓋冗余率最低和空間密度值最低的節(jié)點分布策略。首先將監(jiān)測區(qū)域分為多個以傳感器節(jié)點的傳感半徑為外接球直徑的多面體，然后將傳感器節(jié)點放置在多面體的頂點或是外接球重疊區(qū)域中，最后理論分析出同構(gòu)節(jié)點分布的最佳位置。實驗仿真表明，在相同覆蓋重數(shù)的情況下，截角八面體的覆蓋冗余率和空間密度值最低。

三維無線傳感器網(wǎng)絡(luò)；K重覆蓋；截角八面體；魯洛四面體；覆蓋冗余率；空間密度

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由多個傳感器節(jié)點、匯聚節(jié)點和終端組成并協(xié)作感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)的各種環(huán)境參數(shù)或監(jiān)測對象信息，然后將邏輯上的信息轉(zhuǎn)化為現(xiàn)實物理信息。覆蓋問題是無線傳感器網(wǎng)絡(luò)研究的熱點問題之一，其目的是用盡可能少的傳感器節(jié)點和能量來完成對目標(biāo)區(qū)域的監(jiān)測。目前對于在二維平面上覆蓋控制的研究比較成熟，但是在實際應(yīng)用中，絕大多數(shù)情況下需要在三維監(jiān)測區(qū)域中放置傳感器節(jié)點，為了在保證網(wǎng)絡(luò)連通的情況下有較高的覆蓋率，某些關(guān)鍵區(qū)域需要放置多個傳感器節(jié)點來保證采集數(shù)據(jù)的準(zhǔn)確性。

1 相關(guān)工作

無線傳感器網(wǎng)絡(luò)K重覆蓋主要是研究傳感器節(jié)點位置布置的問題，目前的研究主要集中在二維平面[1-4]，然而實際應(yīng)用中通常需要在三維空間中部署傳感器節(jié)點，因此本文研究的是三維空間中傳感器K重覆蓋的問題。

三維空間K重覆蓋，按照監(jiān)測區(qū)域的應(yīng)用要求可分為整個監(jiān)測區(qū)域的K重覆蓋和關(guān)鍵區(qū)域的K重覆蓋。文獻[5]提出基于空間鑲嵌的三維無線傳感器網(wǎng)絡(luò)K覆蓋機制，從覆蓋冗余率、節(jié)點度兩個方面，比較得出截角八面體是最佳的填充單元。該文獻還提出了解決空洞覆蓋的算法和相鄰填充單元協(xié)作修復(fù)算法，進一步延長了網(wǎng)絡(luò)的生命周期。文獻[6]提出了一種基于概率和網(wǎng)絡(luò)最壞情況覆蓋的三維傳感器網(wǎng)絡(luò)節(jié)點K覆蓋方法，該方法與原基于概率的K覆蓋方法比較，能用較少的節(jié)點滿足相同的覆蓋度。文獻[7]主要研究的是在三維空間中利用規(guī)則多面體的填充特點，并計算了單位節(jié)點最大的有效體積，根據(jù)最小體積計算方法得到了目標(biāo)區(qū)域保持充分覆蓋且相鄰節(jié)點相連接時所需要的最少節(jié)點數(shù)，最終得到最優(yōu)的填充多面體。文獻[8]利用魯洛四面體來實現(xiàn)三維目標(biāo)區(qū)域的K重覆蓋，估算出相應(yīng)的最小傳感器節(jié)點的空間密度，并且證明了一個魯洛四面體區(qū)域如果至少包含K個傳感器則能保證該魯洛四面體區(qū)域被K重覆蓋。

2 覆蓋機制

2.1 問題定義

2.1.1 假設(shè)條件

(1)無線傳感器網(wǎng)絡(luò)始終是連通的；

(2)節(jié)點一旦部署后，位置基本保持不變，即節(jié)點移動距離與節(jié)點感知半徑或通信半徑相比可以忽略；

(3)相對于節(jié)點感知半徑而言，監(jiān)控區(qū)域足夠大，區(qū)域邊界效應(yīng)可以忽略；

(4)網(wǎng)絡(luò)監(jiān)測目標(biāo)區(qū)域是長、寬、高均為L的立方體。

2.1.2 感知模型

節(jié)點的感知模型采用布爾感知模型（即0-1感知模型）。假設(shè)在三維空間中有一個傳感器節(jié)點 nodei(xi，yi，zi)，空間中任意一個探測點 p(x，y，z)，則節(jié)點和探測點間的歐氏距離為：

節(jié)點的感知半徑為Rs。采用布爾感知模型可知探測點p被傳感器節(jié)點nodei覆蓋的概率為：

從式(1)可以看出，若傳感器節(jié)點 nodei與探測點 p之間的歐氏距離小于傳感器節(jié)點的感知半徑Rs則能被覆蓋，否則不能。

2.1.3 K覆蓋的定義

給定一個傳感器節(jié)點集合S，節(jié)點感知半徑Rs和監(jiān)測區(qū)域A，如果A中每個點都被S中的至少K個傳感器所覆蓋，則整個監(jiān)測區(qū)域被K重覆蓋。

2.1.4 覆蓋冗余率和空間密度

空間覆蓋冗余率：

式(2)中，Vall表示傳感器節(jié)點覆蓋的總體積，Vtarget表示覆蓋的有效體積。

空間密度：

式(3)中，K表示覆蓋重數(shù)，V單元表示單個多面體的體積。

2.1.5 形式化定義

綜合2.1.4中公式的定義，本文覆蓋問題定義如下：

式(4)中，在目標(biāo)區(qū)域體積一定的前提下，為了得到最小的覆蓋冗余率，需要得到所有傳感器節(jié)點的最小覆蓋體積，即用最少的傳感器節(jié)點覆蓋目標(biāo)檢測區(qū)域。式（5）中，在覆蓋重數(shù)一定的情況下，需要使覆蓋單元的體積最大才能得到最小的空間密度。在用最小的覆蓋冗余率和最小的空間密度的情況下用最少的傳感器節(jié)點來達(dá)到覆蓋的目的，從而最大程度減少節(jié)點部署數(shù)目，節(jié)約成本。

2.2 確定性覆蓋下的重覆蓋

2.2.1 幾種覆蓋方式冗余度的比較

(1)將三維目標(biāo)監(jiān)測區(qū)域劃分為多個無縫堆砌的多面體，傳感器節(jié)點的傳感半徑為多面體填充單元的外接球直徑。具體做法是將傳感器節(jié)點放置在空間填充多面體的頂點上，保證多面體能被完全覆蓋。

(2)計算覆蓋冗余度來選擇最佳的覆蓋方案：

冗余率：

其中，n表示每個頂點相連的填充單元個數(shù)，V表示單個填充單元的體積，N表示填充單元頂點的個數(shù)。

(3)比較立方體、六角棱柱、截角八面體的覆蓋冗余率

①立方體由8個頂點、6個正方形和12條邊組成，在填充空間時，每個頂點可以與8個立方體（包括自身的立方體）相連，則立方體的邊長，立方體的體積。

②六角棱柱有12個頂點、2個正六邊形、6個矩形和18條邊組成，在填充空間時，每個頂點可以與6個六棱柱相連，令正六邊形的邊長為a，矩形的邊長為，則邊長，六角棱柱的體積為。

③截角八面體由24個頂點、8個正方形、6個正六邊形和36條邊組成，在填充空間時，每個頂點可以與4個截角八面體相連，令正方形和正六邊形的邊長為a，則，截角八面體體積是。

由式(6)覆蓋冗余率可知，單個填充單元體積 V越大，CRR越小，所以可以看出截角八面體是最佳的選擇。

2.2.2 最優(yōu)覆蓋時填充單元個數(shù)

令三維空間每個維度上所需要的截角八面體的個數(shù)為m，填充整個空間所需要的截角八面體的數(shù)量為M，L表示目標(biāo)區(qū)域的邊長。

首先根據(jù)目標(biāo)區(qū)域的大小和傳感器節(jié)點的感知半徑，通過式(8)和式(9)計算填充目標(biāo)區(qū)域所需截角八面體的個數(shù)，然后將節(jié)點均勻地放置在截角八面體的頂點上，隨機選取K個節(jié)點進入工作狀態(tài)，從而實現(xiàn)網(wǎng)絡(luò)的K重覆蓋。

2.3 隨機覆蓋下的K重覆蓋

2.3.1 隨機覆蓋的方法

采用隨機節(jié)點覆蓋策略，隨機均勻地將適量的傳感器節(jié)點以及少量的匯聚節(jié)點部署在目標(biāo)監(jiān)測區(qū)域內(nèi)。傳感器節(jié)點的數(shù)量可以根據(jù)目標(biāo)區(qū)域的大小A、傳感器節(jié)點的傳感半徑Rs和覆蓋重數(shù)K大致的算出來：

為了提高目標(biāo)監(jiān)測區(qū)域覆蓋率，應(yīng)該在目標(biāo)檢測區(qū)域部署大于n個傳感器節(jié)點，一般部署N個節(jié)點：n＜N≤2n。所有傳感器節(jié)點的初始狀態(tài)都為工作狀態(tài)，并向匯聚節(jié)點發(fā)送各自的位置信息。為了確保目標(biāo)區(qū)域的K重覆蓋，將目標(biāo)區(qū)域劃分為若干個無縫堆砌的多面體，只要各個多面體均被K個傳感器完全覆蓋，則能保證整個目標(biāo)監(jiān)測區(qū)域被K重覆蓋。如果只是在各個多面體內(nèi)部放置K個以多面體外接球直徑為傳感半徑的傳感器節(jié)點，傳感器節(jié)點的空間密度為：

因此這樣會造成節(jié)點過度的冗余。為了減小不必要的冗余，本文的方法是使多面體外接球重疊部分中的傳感器節(jié)點保持工作狀態(tài)，其余節(jié)點休眠，這樣重疊區(qū)域中的每個傳感器節(jié)點可以保證至少兩個多面體被覆蓋，傳感器節(jié)點的空間密度最大為：

這樣會很大程度上減小節(jié)點密度。各種多面體的重疊區(qū)域如圖1和圖2所示。

2.3.2 幾種覆蓋方式空間密度的比較

(1)立方體的 6個面都是等大的正方體，所以 6個面上都有等大的重疊區(qū)域，假設(shè)一個立方體各個面上重疊區(qū)域中工作節(jié)點的個數(shù)分別為 a1，a2，…，a6，其中 a1+…+ a6=K，所以：

圖1 立方體外接球的重疊區(qū)域

圖2 六棱柱外接球的重疊區(qū)域

(2)六棱柱是由6個矩形和2個正六邊形組成，假設(shè)6個矩形面的重疊區(qū)域中工作節(jié)點的個數(shù)分別為：a1，…，a6，兩個正六邊形面的重疊區(qū)域中工作節(jié)點的個數(shù)分別為：b1，b2，。其中，a1+…+a6+b1+b2=K。所以，如果填充多面體是六棱柱，則傳感器節(jié)點的空間密度為：

(3)截角八面體是由 8個正方形、6個正六邊形，假設(shè)8個正方形面的重疊區(qū)域中工作節(jié)點的個數(shù)分別為：a1，…，a8，6個正六邊形面的重疊區(qū)域中工作節(jié)點的個數(shù)分別為：b1，…，b6。其中，a1+…+a8+b1+…+b6=K。所以，如果填充多面體是截角八面體，則傳感器節(jié)點的空間密度為：

2.3.3 魯洛四面體

為了和 2.3.2中幾種常見多面體比較空間密度值，下面介紹一個比較特殊的多面體，魯洛四面體（Reuleaux tetrahedra）。

圖3中，四個球體中心連線所構(gòu)成的邊構(gòu)成一個正四面體，四個球體交集構(gòu)成的形體叫做魯洛四面體，表示為RT(r)。根據(jù)文獻[8]，如果監(jiān)測區(qū)域中任何魯洛四面體中含有不少于K個傳感器節(jié)點，則該網(wǎng)絡(luò)的感知覆蓋重數(shù)可保證為K。魯洛四面體的體積公式：

圖3 魯洛克斯四面體

三維區(qū)域中完全K重覆蓋的最小傳感器節(jié)點密度為：

連接魯洛四面體四個頂點組成的是一個規(guī)則的正四面體，如圖4，該正四面體的體積為：

圖4 正四面體

可以看出魯洛四面體的4個邊緣（魯洛四面體減去正四面體）的體積為：

每個邊緣的體積為：

兩個魯洛四面體疊加在一起的情況如圖5，則這兩個魯洛四面體的體積為：

圖5 重疊的兩個魯洛四面體

可以計算出填充多面體是魯洛四面體時，傳感器節(jié)點的空間密度為：

然而實際應(yīng)用中，不可能把一個三維區(qū)域完全分解成多個魯洛四面體相互疊加，并使魯洛四面體與該三維目標(biāo)區(qū)域邊界相近。因此，需要部署稍微多些傳感器節(jié)點以保證在包含邊界區(qū)域在內(nèi)的所有監(jiān)測區(qū)域范圍內(nèi)均實現(xiàn)K重覆蓋。

3 隨機部署中工作節(jié)點選擇機制

3.1 模型的描述

節(jié)點的覆蓋策略：node〈i，j，state〉，0≤i≤M，0≤j≤24，state=-1，0，1，其中i表示填充單元的編號，j表示節(jié)點所在填充單元的頂點編號，M表示填充單元總數(shù)，state表示節(jié)點狀態(tài)，-1表示節(jié)點剩余能量低于工作閾值而處于失效狀態(tài)，0表示節(jié)點處于休眠狀態(tài)，1表示節(jié)點處于工作狀態(tài)。

3.2 選擇流程

(1)首先將三維目標(biāo)區(qū)域A劃分為若干個多面體A= (A1，A2，A3，…，AN)，N為多面體的個數(shù)，相鄰多面體的外接圓相交，第一個多面體和它鄰近的多面體的外接球的重疊區(qū)域表示為 S1=(a11，a12，…，a1n)，n為相鄰多面體面的個數(shù),所有的重疊區(qū)域可以表示為 S=(S1，S2，…，SN)。

(2)初始狀態(tài)下各個傳感器節(jié)點處于工作狀態(tài)，每個傳感器節(jié)點向Sink節(jié)點發(fā)送各自的位置信息。

(3)如果有傳感器節(jié)點落在多面體 Ai的重疊區(qū)域 Si中，統(tǒng)計區(qū)域 Si中傳感器節(jié)點的個數(shù) numi。

(a)如果 numi＞K，休眠 K-numi個傳感器節(jié)點和多面體內(nèi)部不重疊區(qū)域的傳感器節(jié)點；

(b)如果 numi＜K，在多面體內(nèi)部選擇 numi-K個傳感器節(jié)點為工作節(jié)點，其余節(jié)點進入休眠狀態(tài)。

(4)如果i＜N，轉(zhuǎn)(3)；否則，節(jié)點選擇完畢。

3.3 空洞修復(fù)策略

因為節(jié)點能量有限，有些節(jié)點會失效，需要一個填充單元內(nèi)部的空洞自修復(fù)。具體做法是：

(1)節(jié)點正常工作所需的能量閾值為 Emin，計算覆蓋監(jiān)測區(qū)域所需填充單元的個數(shù)為M；

(2)每隔時間間隔T，對監(jiān)測區(qū)域中傳感器節(jié)點的state進行重新檢測：若第 i個多面體中第 j個節(jié)點的state為 1且剩余能量 E＜Emin，則該節(jié)點進入失效狀態(tài)，令state=-1且；

(6)若i＜M，轉(zhuǎn)（3）；否則，自修復(fù)完畢。

4 仿真結(jié)果

本文利用MATLAB仿真軟件對比了以立方體、六棱柱、截角八面體，魯洛四面體為填充多面體的三維目標(biāo)監(jiān)測區(qū)域，確定性部署中覆蓋冗余率和隨機部署中傳感器節(jié)點空間密度。

圖6 覆蓋冗余率CRR

4.1 確定性部署中覆蓋冗余度的比較

圖6是確定性部署中覆蓋冗余度的比較，傳感器節(jié)點被確定放置在每個填充多面體的頂點處。從中可以看出覆蓋重數(shù)K較小時，以截角八面體為填充多面體的目標(biāo)區(qū)域的覆蓋冗余率最低，隨著覆蓋重數(shù)的增加，以幾種多面體填充的目標(biāo)監(jiān)測區(qū)域的覆蓋冗余率都有大幅度增加并且目標(biāo)區(qū)域的覆蓋冗余率都趨于相近。

4.2 隨機部署中傳感器節(jié)點的空間密度的比較

圖7是隨機部署中傳感器節(jié)點的空間密度的比較，傳感器節(jié)點被隨機部署在三維目標(biāo)監(jiān)測區(qū)域中，將目標(biāo)監(jiān)測區(qū)域劃分為若干個多面體，使部署在各個多面體外接球重疊部分的傳感器節(jié)點成為工作節(jié)點。從圖中可以看出截角八面體的傳感器節(jié)點的空間密度最小，隨著覆蓋重數(shù)的增加，各個多面體對應(yīng)的目標(biāo)區(qū)域的傳感器節(jié)點的空間密度也隨之增加，立方體對應(yīng)的傳感器節(jié)點的空間密度增加最快，截角八面體最慢，可以看出截角八面體對應(yīng)目標(biāo)區(qū)域傳感器節(jié)點的空間密度最低，所以截角八面體是最佳的選擇。

圖7 傳感器節(jié)點空間密度spd

4.3 改進的空洞修復(fù)策略

圖8是隨機布置節(jié)點后，假設(shè)覆蓋重數(shù)為2時一般的空洞修復(fù)算法與改進后的空洞修復(fù)算法比較，可以看出改進后的策略修復(fù)成功的次數(shù)高于一般的空洞修復(fù)策略。

圖8 一般空洞修復(fù)與改進后修復(fù)策略修復(fù)成功次數(shù)比較

5 結(jié)論分析

針對三維無線傳感器網(wǎng)絡(luò)K重覆蓋的問題，本文分別從確定性覆蓋和隨機覆蓋兩個方面來研究。在確定性覆蓋中，分別以立方體、六棱柱和截角八面體作為填充單元，把節(jié)點部署在各填充單元的頂點并以填充單元的外接球直徑為傳感半徑，通過比較覆蓋冗余度，得出截角八面體是最佳的選擇。在隨機覆蓋中，先將節(jié)點隨機部署在三維目標(biāo)區(qū)域中，然后根據(jù)選擇工作傳感器節(jié)點的機制，使一些節(jié)點進入激活狀態(tài)，其余節(jié)點進入休眠狀態(tài)，最后比較了傳感器節(jié)點的空間密度值。實驗顯示，截角八面體是最佳選擇。提出了隨機部署中選擇工作傳感器節(jié)點的機制和改進的空洞修復(fù)協(xié)議。下一步工作將研究在本文提出的隨機部署中，工作節(jié)點的選擇機制。即隨著節(jié)點能量的消耗，針對網(wǎng)絡(luò)覆蓋空洞，提出一些空洞修復(fù)的優(yōu)化算法。

[1]FEI X，BOUKERCHE A，YU R.A pomdp based K-coverage dynamic scheduling protocol for wireless sensor networks[J]. GLOBECOM 2010，2010 IEEE Global Telecommunications Conference，2010：1-5.

[2]韓志杰，吳志斌，王汝傳.新的無線傳感器網(wǎng)絡(luò)覆蓋控制算法[J].通信學(xué)報，2011，32（10）.

[3]SIMON G，MOLN?R M，G?NCZY L，et al.Dependable kcoverage algorithms for sensor networks[C].Instrumentation and Measurement Technology Conference Proceedings，2007. IMTC 2007.IEEE.IEEE，2007：1-6.

[4]MAO X，LIU Y，TANG S，et al.Finding best and worst kcoverage paths in multihop wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems，2013，24(12)：2396-2406.

[5]王興偉，蔡凌，黃敏.基于空間鑲嵌的三維無線傳感器網(wǎng)絡(luò) k覆蓋機制[J].小型微型計算機系統(tǒng)，2014，35(3).

[6]王麗，苗鳳娟，陶柏睿，等.一種改進的無線傳感器網(wǎng)絡(luò)三維K覆蓋控制方法[J].河南理工大學(xué)學(xué)報：自然科學(xué)版，2014，33(3)：333-338.

[7]鐘永信，黃建國，韓晶.三維傳感器網(wǎng)絡(luò)部署、覆蓋和連接問題研究[J].控制與決策，2011，26(10)：1447-1451.

[8]Ammari H M，Das S K.A study of k-coverage and measures of connectivity in 3D wireless sensor networks[J].Computers，IEEE Transactions on，2010，59(2)：243-257.

[9]Nazrul Alam，Haas.Coverage and connectivity in threedimensional networks[J].Eprint Arxiv：cs/0609069，2006.

Research on K-coverage mechanism for 3-D wireless sensor networks

Wang Jun1，2，Sun Xiaoling1，Cheng Yong2
(1.Department of Computer＆Software，Nanjing University of Information Science＆Technology，Nanjing 210044，China；2.Network Information Center，Nanjing University of Information Science＆Technology，Nanjing 210044，China)

For the problem that the coverage efficiency of the sensor nodes which are randomly distributed in the three-dimensional monitoring area is low,and the critical area can not reach K-coverage.This article uses polyhedrons to fill an area，Respectively, use the deterministic coverage and random coverage to propose the best node distribution strategy,which can reach the lowest value of coverage redundancy rate and spatial density under ideal conditions.First,the monitoring area is divided into a plurality of polyhedrons,the ball diameter of a polyhedron is the sensing radius of the working sensor nodes.Then,put the sensor nodes on the vertices of a polyhedron or in the overlapping area of the polyhedrons'circumscribed sphere.Finally,according to theory,analyze the optimum deployment of the nodes in three-dimensional sensor networks.The simulation showed that,in the case of the same coverage degree K,the coverage redundancy rate and spatial density of truncated octahedron is the lowest.

3-D wireless sensor networks；K-coverage；truncated octahedron；reuleaux tetrahedron；coverage redundancy rate；spatial density

TP393.02

A

10.16157/j.issn.0258-7998.2015.11.040

王軍，孫小玲，程勇.三維無線傳感器網(wǎng)絡(luò)K重覆蓋機制研究[J].電子技術(shù)應(yīng)用，2015，41(11)：144-148.

英文引用格式：Wang Jun，Sun Xiaoling，Cheng Yong.Research on K-coverage mechanism for 3-D wireless sensor networks[J]. Application of Electronic Technique，2015，41(11)：144-148.

2015-07-01)

王軍（1970-），男，碩士，教授，主要研究方向：無線傳感器網(wǎng)絡(luò)覆蓋控制、物理信息融合。

國家自然科學(xué)基金資助項目(61402236，61373064)；江蘇省農(nóng)業(yè)氣象重點實驗室開放基金資助（KYQ1309）；江蘇省“六大人才高峰”項目(2013-DZXX-019)，江蘇省產(chǎn)學(xué)研前瞻性聯(lián)合研究項目（BY2014007-2）；公益性行業(yè)（氣象）科研專項（GYHY201106037）

孫小玲（1990-），通信作者，女，碩士，學(xué)生，主要研究方向：無線傳感器網(wǎng)絡(luò)覆蓋控制，E-mail：1183313568@qq. com。

程勇（1980-），男，博士，高級工程師，主要研究方向：無線傳感器網(wǎng)絡(luò)路由協(xié)議。