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

王 軍，孫小玲，程 勇

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

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

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

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

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

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

0 引言

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

1 相關(guān)工作

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

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

2 覆蓋機(jī)制

2.1 問題定義

2.1.1 假設(shè)條件

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

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

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

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

2.1.2 感知模型

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

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

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

2.1.3 K覆蓋的定義

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

2.1.4 覆蓋冗余率和空間密度

空間覆蓋冗余率：

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

空間密度：

式(3)中，K表示覆蓋重?cái)?shù)，V單元表示單個(gè)多面體的體積。

2.1.5 形式化定義

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

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

2.2 確定性覆蓋下的重覆蓋

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

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

(2)計(jì)算覆蓋冗余度來(lái)選擇最佳的覆蓋方案：

冗余率：

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

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

①立方體由8個(gè)頂點(diǎn)、6個(gè)正方形和12條邊組成，在填充空間時(shí)，每個(gè)頂點(diǎn)可以與8個(gè)立方體（包括自身的立方體）相連，則立方體的邊長(zhǎng)，立方體的體積。

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

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

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

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

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

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

2.3 隨機(jī)覆蓋下的K重覆蓋

2.3.1 隨機(jī)覆蓋的方法

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

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

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

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

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

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

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

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

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

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

2.3.3 魯洛四面體

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

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

圖3 魯洛克斯四面體

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

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

圖4 正四面體

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

每個(gè)邊緣的體積為：

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

圖5 重疊的兩個(gè)魯洛四面體

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

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

3 隨機(jī)部署中工作節(jié)點(diǎn)選擇機(jī)制

3.1 模型的描述

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

3.2 選擇流程

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

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

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

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

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

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

3.3 空洞修復(fù)策略

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

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

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

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

4 仿真結(jié)果

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

圖6 覆蓋冗余率CRR

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

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

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

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

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

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

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

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

5 結(jié)論分析

針對(duì)三維無(wú)線傳感器網(wǎng)絡(luò)K重覆蓋的問題，本文分別從確定性覆蓋和隨機(jī)覆蓋兩個(gè)方面來(lái)研究。在確定性覆蓋中，分別以立方體、六棱柱和截角八面體作為填充單元，把節(jié)點(diǎn)部署在各填充單元的頂點(diǎn)并以填充單元的外接球直徑為傳感半徑，通過(guò)比較覆蓋冗余度，得出截角八面體是最佳的選擇。在隨機(jī)覆蓋中，先將節(jié)點(diǎn)隨機(jī)部署在三維目標(biāo)區(qū)域中，然后根據(jù)選擇工作傳感器節(jié)點(diǎn)的機(jī)制，使一些節(jié)點(diǎn)進(jìn)入激活狀態(tài)，其余節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，最后比較了傳感器節(jié)點(diǎn)的空間密度值。實(shí)驗(yàn)顯示，截角八面體是最佳選擇。提出了隨機(jī)部署中選擇工作傳感器節(jié)點(diǎn)的機(jī)制和改進(jìn)的空洞修復(fù)協(xié)議。下一步工作將研究在本文提出的隨機(jī)部署中，工作節(jié)點(diǎn)的選擇機(jī)制。即隨著節(jié)點(diǎn)能量的消耗，針對(duì)網(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ú)線傳感器網(wǎng)絡(luò)覆蓋控制算法[J].通信學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò) k覆蓋機(jī)制[J].小型微型計(jì)算機(jī)系統(tǒng)，2014，35(3).

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

[7]鐘永信，黃建國(guó)，韓晶.三維傳感器網(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ú)線傳感器網(wǎng)絡(luò)K重覆蓋機(jī)制研究[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ú)線傳感器網(wǎng)絡(luò)覆蓋控制、物理信息融合。

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

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

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