0 引言

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

1 相關工作

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

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

2 覆蓋機制

　　2.1 問題定義

　　2.1.1 假設條件

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

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

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

　　(4)網絡監測目標區域是長、寬、高均為L的立方體。

　　2.1.2 感知模型

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

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

　　2.1.3 K覆蓋的定義

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

　　2.1.4 覆蓋冗余率和空間密度

　　空間覆蓋冗余率：

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

　　空間密度：

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

　　2.1.5 形式化定義

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

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

　　2.2 確定性覆蓋下的重覆蓋

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

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

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

　　冗余率：

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

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

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

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

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

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

　　2.2.2 最優覆蓋時填充單元個數

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

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

　　2.3 隨機覆蓋下的K重覆蓋

　　2.3.1 隨機覆蓋的方法

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

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

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

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

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

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

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

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

　　2.3.3 魯洛四面體

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

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

　　三維區域中完全K重覆蓋的最小傳感器節點密度為：

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

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

　　每個邊緣的體積為：

　　V3=V2/4≈0.076R

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

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

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

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

3 隨機部署中工作節點選擇機制

　　3.1 模型的描述

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

　　3.2 選擇流程

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

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

　　(3)如果有傳感器節點落在多面體Ai的重疊區域Si中，統計區域Si中傳感器節點的個數numi。

　　(a)如果numi>K，休眠K-numi個傳感器節點和多面體內部不重疊區域的傳感器節點；

　　(b)如果numi<K，在多面體內部選擇numi-K個傳感器節點為工作節點，其余節點進入休眠狀態。

　　(4)如果i<N，轉(3)；否則，節點選擇完畢。

　　3.3 空洞修復策略

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

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

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

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

4 仿真結果

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

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

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

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

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

　　4.3 改進的空洞修復策略

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

5 結論分析

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

參考文獻

　　[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] 韓志杰，吳志斌，王汝傳.新的無線傳感器網絡覆蓋控制算法[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] 王興偉，蔡凌，黃敏.基于空間鑲嵌的三維無線傳感器網絡k覆蓋機制[J].小型微型計算機系統，2014，35(3).

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

　　[7] 鐘永信，黃建國，韓晶.三維傳感器網絡部署、覆蓋和連接問題研究[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.