無線傳感器網絡多柵欄覆蓋構建算法研究*

楊 濤，慕德俊

(西北工業大學自動化學院，西安 710072)

0 引言

覆蓋問題是無線傳感器網絡配置首先面臨的基本問題，它決定著一個無線傳感器網絡的工作性能。柵欄覆蓋較全覆蓋模型，更加符合實際應用中長時間、無間斷工作的需要，已成為無線傳感器網絡的研究熱點之一[1－3]。

已有工作主要基于隨機部署的靜態傳感器網絡對監控區域實施單柵欄覆蓋，存在兩個問題：1)由于部署的隨機性，傳感器網絡中可能存在空隙，或隨著時間延續，網絡中出現死節點的弱區域，使得入侵者可能通過監控區域而不被檢測到;2)隨機部署時，監控區域內會散布大量節點，而單柵欄覆蓋只選取其中一部分，這就造成節點冗余浪費。

文中針對帶狀監控區域內隨機部署的無線傳感器網絡，研究如何通過分治算法高效的構建k－覆蓋的問題。主要研究工作包括：1)形式化定義了傳感器節點k－覆蓋的條件，確保在監控區域中，入侵者穿越路徑至少被一個傳感器節點覆蓋;2)提出了區域多柵欄覆蓋構建算法DPA。實驗表明該算法與傳統的多邊形柵欄構筑算法相比，構筑柵欄數目超出30%，并降低了通信開銷和計算復雜度，延長了網絡的工作壽命。

1 網絡模型和問題描述

1.1 網絡模型

傳感器網絡N，是一組傳感器節點的集合，它們被隨機布置于大小為A的二維模型環境中，假設這個二維環境是一個帶狀區域，這個帶狀區域有4條邊界，兩條水平的，兩條豎直的，其中寬度為w，長度為l，A2d=l×w，見圖1，則可以假設每個傳感器節點隨機泊松分布在區域A中，設數量為N(A)的傳感器以參數為na分布，則得到：

圖1 傳感器部署帶狀區域

用u來代表一個傳感器節點，設每一個傳感器節點的感應半徑為rs，當傳感器節點u與監測區域的任意點p的歐式距離小于傳感半徑rs時，則點p被覆蓋。

1.2 問題描述

監測的帶狀區域的每一個點都被覆蓋的模型叫做全覆蓋模型。在帶狀區域中，僅在水平方向部署傳感器的模型叫做柵欄覆蓋模型。當入侵者的入侵軌跡經過k個傳感器節點感應區域時，稱之為k－覆蓋。一個覆蓋區域的所有入侵路徑都最少經過k個傳感器節點的感應區域，就稱該覆蓋支持k－覆蓋。如圖2所示。

圖2 覆蓋模型

圖3 帶狀區域沒有被柵欄覆蓋因為存在一條無覆蓋突破路徑

在文獻[1]中發現柵欄覆蓋對于全覆蓋有一定的局限性，例如，在一段長約500km，寬度為50m的帶狀區域中，通過全局柵欄覆蓋定義，仍存在一條近似于帶狀區域寬度的無覆蓋穿越路徑，稱之為突破路徑，如圖3所示。

Ai等人提出L本地化柵欄覆蓋的概念用于解決此問題，將帶狀區域分成若干長度為L的片段，每一個L長度片段內實現柵欄覆蓋，則該片段內的每一條路徑就實現了覆蓋[4]。Liu.等人提出強柵欄覆蓋的概念解決此問題，提出了在帶狀區域的豎直方向上建立柵欄，保證每一條路徑在穿越時都至少經過一條豎直方向的柵欄，這樣就實現了所有穿越路徑的柵欄覆蓋[5]。

這兩種方法在一定程度上都能解決這個問題，但本地化的算法對傳感器能量消耗過大，不利于延長網絡壽命。在豎直方向上建立柵欄的強柵欄覆蓋又不能保證豎直柵欄正好建立在兩個漏洞點中間。所以文中將提出利用多柵欄構筑算法實現多柵欄切換，加強覆蓋質量的方法。

2 柵欄覆蓋的基本條件

一般無線傳感器網絡的配置是由飛機等在空中隨機播撒傳感器節點，所有的傳感器節點就會在帶狀監測區域內部的一條線段上隨機分布。假設這個線段為[0，L]，把它分為N個片段，每一個片段的長度為傳感器感應半徑的兩倍2rs，即N=L/2rs。

在兩個相鄰的片段i和i+1中，片段i中的最右端節點A的位置為X1，片段i+1中的最左端節點B的位置為X2，需要以下條件保證傳感器全覆蓋，如圖4所示。

1)每個長度為2rs的片段內都必須有一個傳感器節點u。

2)當相鄰傳感器節點距離大于等于兩個感應半徑即2rs≤X2－ X1＜ 3rs時，在[X1+rs，X2－ rs]，即區域CD中至少有一個傳感器節點。

3)當相鄰傳感器節點距離大于等于3倍感應半徑即3rs≤X2－ X1＜ 4rs時，在[X1+2rs，X2－ rs]即區域FD或者[X1+rs，X2－2rs]即區域CE內至少有一個傳感器節點。

圖4 片段i全覆蓋的條件(1＜i＜N)

假設BCOV(α)是該區域被覆蓋的概率，Yi代表i片段被傳感器全覆蓋，P(Yi)表示事件Yi發生的概率，當片段長度為2rs時，可以得到P(Yi|Y1∩Y2…，并且事件 Yi和Y1…Yi－2是相互獨立的。所以：

把圖4中填充區域的CE、FD分成無數個長度為Δθ的小片段，無線傳感器節點以參數為λ的泊松分布配置在區域中，由離散逼近可以得到：

將式(3)～式(5)代入式(2)就可以得到P(Y1∩Y2…∩YN)的值。

3 多柵欄構筑算法

3.1 分治算法

在滿足以上覆蓋條件的基礎上，就可以進行多柵欄構筑。同時，將覆蓋區域分為若干個小的片段區域，就可以有效降低整個網絡的能量開銷，增大網絡的使用壽命。在水平與豎直方向分別構筑柵欄，比傳統的多邊形覆蓋算法(PMI)更有效。

區域分割的機制如圖5所示，先通過傳感器節點上的GPS模塊獲得各節點的地理位置信息，然后在與帶狀區域的延伸方向上選取豎直方向的傳感器節點，并把他們相連，形成圖6中的豎直構筑區，該豎直構筑區是隨機產生的，其余的節點即在水平方向上互連，形成水平構筑區。

圖5 分離后的多柵欄覆蓋圖

3.2 DPA算法描述

由上節中討論的分治算法思想，可以知道多柵欄構筑算法DPA在能夠獲知網絡全局信息的中心簇頭節點上運行，中心節點可以通過選舉等方式確定。通過分割覆蓋區域的方式，整個網絡的信息延遲、通信開銷和計算消耗都明顯降低。對于連通網絡G(V，E)，其網絡開銷和構筑柵欄的計算復雜度分別是O(|V||E|)和O(|V|3)。如果帶狀覆蓋區域被分為n個小區域，則每個區域的節點不多于 |v|/n，則它們的通信開銷就是O(|V|2/n2)算法復雜度為O(|V|3/n3)。

District Partition Algorithm(DPA)Require：Many Sensors are deployed in the belt region Ensure：Different barrier in the belt region，barrieri;The work time of barrieri，ti.1：Invoke the Edmond-Karp algorithm to find a maximum flow from s to t in G(N).2：Deleting all value of vertices with 0 from G(N).3：Choosing sensors from far left in the deployed belt，which means the sensors are connecting with node s.4：Connecting the neighbor sensors one by one until the sensor is connecting with node t.The neighbor sensors location must to the right of prior sensor.5：Collecting the GPS information of sensors in a barrier and calculating the average vertical value to differentiate the barriers.Then different barrier are constructed.6：Sort these barriers by descending order ofrest energy.Then get the rest energy sequence sq1，sq2...，sqi 7：We denote the work time of barrierias ti.Then t1sq1∑n i=1sqi= t2sq2∑n i=1sqi= t3sq3∑n i=1sqi=…= tisqi∑n i=1sqi If t1is the work time of barrier1，then the work time of barrier s2t2ist1sq1 sq3…8：return ti ;

4 仿真實驗

為了驗證上述方法的真實有效性，文中利用Matlab進行仿真實驗。在實驗中，設定部署區域長度為7000m，寬度為1000m。布置一定數量的傳感器節點，可以看到文中使用的區域分割法(DPA)構筑柵欄比傳統的多邊形柵欄構筑方式IPM更加有效。如圖6。

當泊松分布參數由0.001到0.05。傳感器感應半徑為100m到200m。通過仿真實驗與式(3)～式(5)推導出來的結果進行比較得出，分析公式能夠很好的指導實際仿真結果。實際結果如圖7所示。其中 x軸為泊松分布參 λ的值，y軸為覆蓋率。

圖6 多柵欄構筑

圖7 泊松分布參數與覆蓋率關系圖

當節點數量不斷增加時，DPA算法可以根據傳感器節點剩余能量決定各條柵欄的工作時長，可以有效延長系統的工作時間。圖8中的參考值是部署4500個節點時，傳感器網絡工作的時長T，縱坐標為通過DPA算法構筑的多柵欄網絡的工作時長與T的比率。可以看出通過DPA算法構筑的多柵欄有效延長了網絡的工作時間。

圖8 DPA構筑多柵欄的網絡壽命

5 結論

柵欄覆蓋是無線傳感器網絡覆蓋的一種更高效的模型。已有研究工作主要針對單柵欄覆蓋。文中研究如何改進單柵欄覆蓋的質量，更高效的實現k柵欄覆蓋的問題，提出了DPA算法。將監控區域分割成多個子區域，分別進行柵欄構筑，最終連接所有區域，實現高效可靠的覆蓋。實驗表明，DPA可以構筑更多柵欄，并且可以有效的延長網絡的工作壽命。

[1]S Kumar，T H Lai，A Arora.Barrier coverage with wireless sensors[C]//Proc.of ACM MobiCom，Cologne，2005：284－298.

[2]Bai XL，Yun ZQ，Xuan D，et al.Deploying four-connectivity and full-coverage wireless sensor networks[C]//Proc.of the IEEE INFOCOM，2008：296－300.

[3]I F Akyildiz，T Melodia，K R Chowdhury.A survey on wireless multimedia sensor networks[J]Computer Networks Journal，2007，51(4)：921－960.

[4]Ai Chen，S Kumar，T H Lai.Designing localized algorithms for barrier coverage[C]//Proc.of ACM MobiCom，2007：63－74.

[5]Liu BY，Dousse O，Wang J，et al.Strong barrier coverage of wireless sensor networks[C]//Proc.of the 9th ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing(Mobihoc)，2008：411－420.

[6]Balister P，Bollobas B，Sarkar A，et al.Reliable density estimates for coverage and connectivity in thin strips of finite length[C]//Proc.of the 13th Annual ACM Int’l Conf.on Mobile Computing and Networking(MobiCom)，2007：75－86.

[7]Jren-Chit Chin，Yu Dong，Wing-Kai Hon，et al.Detection of intelligent mobile target in a mobile sensor network[J].IEEE/ACM Transactions on Networking，2010，18(1)：41－52.

[8]何欣，桂小林，安健.面向目標覆蓋的無線傳感器網絡確定性部署方法[J].西安交通大學學報，2010，44(6)：6－15.