0 引言

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

1 相關工作

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

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

2 覆蓋機制

　　2.1 問題定義

　　2.1.1 假設條件

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

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

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

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

　　2.1.2 感知模型

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

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

　　2.2 確定性覆蓋下的重覆蓋

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

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

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

　　冗余率：

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

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

　?、倭⒎襟w由8個頂點、6個正方形和12條邊組成，在填充空間時，每個頂點可以與8個立方體（包括自身的立方體）相連，則立方體的邊長a=Rs/3，立方體的體積V=a3=R/9。

　?、诹抢庵?2個頂點、2個正六邊形、6個矩形和18條邊組成，在填充空間時，每個頂點可以與6個六棱柱相連，令正六邊形的邊長為a，矩形的邊長為a，則邊長a=Rs/6，六角棱柱的體積為V=R/4。

　?、劢亟前嗣骟w由24個頂點、8個正方形、6個正六邊形和36條邊組成，在填充空間時，每個頂點可以與4個截角八面體相連，令正方形和正六邊形的邊長為a，則a=Rs/10，截角八面體體積是V=4R/25。

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

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

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

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

　　2.3 隨機覆蓋下的K重覆蓋

　　2.3.1 隨機覆蓋的方法

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

　　為了提高目標監(jiān)測區(qū)域覆蓋率，應該在目標檢測區(qū)域部署大于n個傳感器節(jié)點，一般部署N個節(jié)點：n<N≤2n。所有傳感器節(jié)點的初始狀態(tài)都為工作狀態(tài)，并向匯聚節(jié)點發(fā)送各自的位置信息。為了確保目標區(qū)域的K重覆蓋，將目標區(qū)域劃分為若干個無縫堆砌的多面體，只要各個多面體均被K個傳感器完全覆蓋，則能保證整個目標監(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ū)域，假設一個立方體各個面上重疊區(qū)域中工作節(jié)點的個數(shù)分別為a1，a2，…，a6，其中a1+…+a6=K，所以：

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

　　(3)截角八面體是由8個正方形、6個正六邊形，假設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)絡的感知覆蓋重數(shù)可保證為K。魯洛四面體的體積公式：

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

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

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

　　每個邊緣的體積為：

　　V3=V2/4≈0.076R

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

　　V4=2V(R)-2V3≈0.692R

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

　　然而實際應用中，不可能把一個三維區(qū)域完全分解成多個魯洛四面體相互疊加，并使魯洛四面體與該三維目標區(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)首先將三維目標區(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 空洞修復策略

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

　　(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且M=M-1；

　　(6)若i<Ｍ，轉(zhuǎn)（3）；否則，自修復完畢。

4 仿真結(jié)果

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

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

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

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

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

　　4.3 改進的空洞修復策略

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

5 結(jié)論分析

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

參考文獻

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

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

　　[3] SIMON G，MOLN?魧R M，G?魻NCZY L，et al.Dependable k-coverage 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 k-coverage paths in multihop wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems，2013，24(12)：2396-2406.

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

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

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

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

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