無線傳感器網絡中覆蓋盲區發現算法*

高 昊，王慶生，馮秀芳，史躍飛

（太原理工大學計算機科學與技術學院，山西太原 030024）

0 引言

無線傳感器網絡（wireless sensor networks，WSNs）在環境監控、交通管理、智能建筑等領域有著廣泛的應用，在這些實際應用中，覆蓋控制是其首要關注的問題［1］。為了使WSNs完成目標監測和信息獲取的任務，必須保證傳感器節點能有效地覆蓋被監測的區域或目標。WSNs的覆蓋完整度是服務質量的重要度量指標［2］。但是隨著網絡的持續運行，傳感器節點可能因為能量耗盡或者惡劣的目標區域環境破壞而死亡，使得網絡的覆蓋區域缺失，形成覆蓋盲區。同時由于每個傳感器節點的感知半徑和通信半徑是固定的，當節點隨機部署時，也可能產生覆蓋盲區，嚴重影響網絡的性能。因此，當網絡中出現覆蓋盲區時，應立即檢測尋找，以保持WSNs的感知、通信等服務質量。

目前，針對WSNs覆蓋盲區發現已有一些解決方案提出。Wang G等人［3］使用voronoi圖發現覆蓋盲區，使用移動節點去修復覆蓋盲區，該算法適用于隨機部署的WSNs，但是移動節點需要消耗大量的能量。Ghrist R［4］和Silva V D［5］將代數拓撲中的同調理論應用到盲區檢測中，但是該算法是一種集中式算法，計算量較大，不適合于大規模的網絡，當網絡有n個傳感器節點時，算法的時間復雜度為O（n5）。Buchart J T［6］首先建立 WSNs的通信連接圖，再使用最大單純復形把通信連接圖轉換成一個二維的單純復形，提出基于這種網絡模型的覆蓋盲區的檢測算法。Kanno J等人［7］使用代數拓撲去建立傳感器節點的通信拓撲圖，該算法可以應用于傳感器節點的坐標未知的WSNs，尤其針對包含移動節點和靜態節點的混合型的WSNs。Xin Yue等人［8］根據WSNs的覆蓋盲區由邊界弧包圍，提出一種檢驗邊界節點和邊界弧的算法，進而檢測到覆蓋盲區。Corke P［9］等人提出一種路徑密度算法（path density algorithm，PDA），該算法根據傳感器節點周圍的路徑密度檢測覆蓋盲區，檢測正確率較高，但是節點能量消耗較大。

基于上述研究基礎，本文對覆蓋盲區的發現作進一步研究，提出了一種基于幾何圖形的分布式覆蓋盲區發現算法，每個傳感器節點并發的執行該算法，根據相關的幾何理論檢測出整個網絡的覆蓋盲區和邊界節點。

1 定義與假設

1．1 基本定義

定義1 感知范圍相交的2個節點A，B互為鄰居節點。當節點A，B之間的距離dA，B≤Rc，節點A，B互為1跳鄰居節點［10］;當Rc＜dA，B＜2Rc，節點A，B互為 2 跳鄰居節點。

1．2 基本假設

1）傳感器節點同構，即各個傳感器節點都具有相同的計算能力、通信能力和初始能量，并且時間同步;

2）傳感器節點能夠獲取自身的位置信息，并且都有唯一的ID號;

3）節點的通信半徑Rc是感知半徑Rs的2倍;

4）傳感器節點采用圓盤布爾覆蓋模型［11］，即節點的感知范圍是以該節點為圓心，感應半徑Rs的圓。

2 基于幾何圖形的盲區發現算法

2．1 理論基礎

定理1 當節點與其2個鄰居節點構成一個銳角三角形或者直角三角形，并且三角形的外接圓半徑R≤Rs，在該節點附近沒有覆蓋盲區;反之，當R＞Rs，在該節點附近有覆蓋盲區。

證明:以銳角三角形為例，直角三角形的證明類似。分3種情況討論:1）節點與2個1跳鄰居節點構成銳角三角形，則外接圓圓心Z一定位于該銳角三角形內，外接圓半徑R≤Rs，外接圓圓心Z一定被這些節點覆蓋，因此，存在著共同感知區域，這3個傳感器節點之間不存在覆蓋盲區。2）節點與2個2跳鄰居節點構成銳角三角形，當外接圓半徑R≤Rs，則在3個節點之間一定存在著共同感知區域，不存在覆蓋盲區;當外接圓半徑R＞Rs，則在3個節點之間沒有共同感知區域，外接圓圓心Z一定在這3個傳感器節點的覆蓋范圍之外，存在著覆蓋盲區。3）節點與一個1跳鄰居節點和一個2跳鄰居節點構成銳角三角形，證明方法與第二種情況類似。證畢。

定理2 當節點與其2個鄰居節點構成一個鈍角三角形，并且三角形的外接圓半徑R≤Rs，在該節點附近沒有覆蓋盲區;反之，當R＞Rs，并且三角形的外接圓圓心Z不被其他傳感器節點覆蓋，在該節點附近有覆蓋盲區。

證明:分3種情況討論:1）節點與2個1跳鄰居節點構成鈍角三角形，當外接圓半徑R≤Rs，則外接圓半徑R一定在其中一個傳感器的節點的覆蓋范圍之內，外接圓圓心Z一定被這些節點所覆蓋，因此，在這3個節點之間不存在覆蓋盲區;反之，當R＞Rs，則外接圓圓心Z在這3個傳感器節點的覆蓋范圍之外，如果Z沒有被其他任何傳感器節點覆蓋，則在節點附近有覆蓋盲區。2）節點與2個2跳鄰居節點構成鈍角三角形，當節點所在的角是銳角，并且R≤Rs，則外接圓圓心Z一定在其中一個傳感器節點的感知范圍內，即這3個節點之間不存在覆蓋盲區;當節點所在的角是鈍角，并且R＞Rs，則外接圓圓心Z一定在傳感器節點的感知范圍外，即3個節點之間存在覆蓋盲區;當節點所在的角是鈍角，必然存在外接圓半徑R＞Rs，則外接圓圓心Z在這3個傳感器節點的覆蓋范圍之外，如果Z沒有被其他任何傳感器節點覆蓋，則在節點附近有覆蓋盲區。3）節點與一個1跳鄰居節點和一個2跳鄰居節點構成鈍角三角形，證明方法與第二種情況類似。證畢。

2．2 算法描述

基于上述定理，本文提出一種基于幾何圖形的WSNs覆蓋盲區發現算法，該算法是分布式算法，在每一個傳感器節點上并發執行。算法的具體描述如下:

2．2．1 數據結構

Ai和Aj為鄰居節點;

N為節點的鄰居節點集合;

Nt為縱坐標大于等于節點坐標的鄰居節點集合;

Ntx為將集合Nt中的元素按照橫坐標的升序排列后的集合;

Nb為縱坐標小于節點坐標的鄰居節點集合;

Nbx為將集合Nb的元素按照橫坐標降序排列后的集合。

2．2．2 算法流程

1）隨機選擇任何一個節點X，其坐標為（a，b）;

2）找出該節點X的1跳、2跳鄰居節點，作為集合N;

3）從集合N中選取縱坐標≥b的元素，組成集合Nt;

4）把集合Nt中的元素按照橫坐標升序排列，構成新的集合Ntx;

5）從Ntx找出2個節點Ai和Aj，其中，Ai橫坐標小于Aj的橫坐標;

6）計算△XAiAj的外接圓圓心Z和外接圓半徑R;

7）判定△XAiAj的形狀（銳角三角形、直角三角形、鈍角三角形）;

8）if（△XAiAj是銳角或者直角三角形）

{if（R≤Rs）在X周圍沒有覆蓋盲區;

else 在X周圍有覆蓋盲區;}

9）if（△XAiAj是鈍角三角形）

{if（R≤Rs）在X周圍沒有覆蓋盲區;

else{檢查Z是否被其他傳感器節點覆蓋;

10）if（Z被其他傳感器節點覆蓋）

在X周圍沒有覆蓋盲區;

else在X周圍有覆蓋盲區;

}∥endelse

}∥endif

11）令Nt=Nt－{Ai};

}while（Ntx≠?）

12）從集合N中選取縱坐標＜b的元素，組成集合Nb;

13）把集合Nb中的元素按照橫坐標降序排列，構成新的集合Nbx;

14）從Nbx找出2個節點Ai和Aj，其中Ai橫坐標大于Aj的橫坐標;

15）對以上2個節點Ai和Aj執行操作類似步驟（6）到步驟（11），直至集合Nbx為空。

3 算法仿真與性能評估

3．1 算法有效性驗證

為驗證上述算法的有效性，在Windows XP上采用Matlab 7．0作為實驗平臺實現上述算法。仿真參數如表1。

表1 仿真參數列表Tab 1 Sheet of simulation parameters

仿真在二維正方形1000 m×1000 m的實驗區域進行，100個傳感器節點在該區域內隨機部署，如圖1所示。

圖1 節點的隨機分布圖Fig 1 Random distribution diagram of nodes

通過在每個傳感器節點并發地運行上述的WSNs的覆蓋盲區發現算法，能夠發現監控區域中得覆蓋盲區，并且檢測到覆蓋盲區的邊界節點。如圖2所示，在1 000 m×1000 m的監控區域中，有4個覆蓋盲區，使用上述的算法，可以檢測到17個覆蓋盲區的邊界節點，并且用加粗標出。

圖2 覆蓋盲區和邊界節點的檢測Fig 2 Detection of coverage blind spots and boundary nodes

3．2 算法性能評估

為評估本文算法的性能，選取文獻［9］中的路徑密度算法（PDA）作為比較對象，采用Matlab 7．0作為仿真平臺實現以上2種算法，在能量消耗方面對2種算法的性能進行比較與分析。在1000 m×1000 m的監控區域中，隨機部署傳感器節點個數為{200，400，600，800，1 000}，節點的感知半徑為40 m，通信半徑為80 m，其他仿真參數與表1相同，仿真結果如圖3所示。圖3反映的是本文算法與PDA在檢測覆蓋盲區時節點消耗能量的對比情況。從實驗結果可以看出:隨著網絡中覆蓋盲區個數的增加，平均節點能量消耗也增加;相比較于PDA，本文算法的平均節點能量消耗較小，這是因為本文算法判定節點附近是否存在覆蓋盲區時算法復雜度低，消耗的節點能量較少。

圖3 平均節點能量消耗比較Fig 3 Comparison of average energy consumption of sensor nodes

4 結論

針對WSNs中覆蓋盲區的問題，本文提出了一種基于幾何圖形的分布式覆蓋盲區發現算法，根據簡單而有效的幾何規則判定是否存在覆蓋盲區。仿真實驗結果表明:該算法能夠有效地檢測覆蓋盲區和邊界節點，并且能有效降低節點的平均能量消耗，延長整個網絡的生命周期，性能優于PDA。下一步研究的重點是在檢測到覆蓋盲區和邊界節點之后，如何修復覆蓋盲區，從而進一步地提高網絡的服務質量。

［1］ 趙 旭，雷 霖，代傳龍．無線傳感器網絡的覆蓋控制［J］．傳感器與微系統，2007，26（8）:62 －65．

［2］ 張鼎興，徐 明，唐文勝．無線傳感器網絡節點自調度冗余覆蓋算法［J］．傳感器與微系統，2009，28（3）:24 －29．

［3］ Wang G，Cao G，Porta L．Movement-assisted sensor deployment［C］∥Proceedings of the 23rd Annual Joint Conference of IEEE Computer and Communications Societies，2004．

［4］ Ghrist R，Muhammad A．Coverage and hole-detection in sensor networks via homology［C］∥Proceedings of the 4th International Symposium on Information Processing in Sensor Networks，2005:254－260．

［5］ Silva V D，Ghrist R．Homological sensor networks［J］．Notices of the American Mathematical Society，2007，54（1）:10 －17．

［6］ Buchart J T．Detecting coverage holes in wireless sensor networks［D］．Louisiana:Louisiana Tech University，2008．

［7］ Kanno J，Buchart J G，Selmic R R，et al．Detecting coverage holes in wireless sensor networks［C］∥Proceedings of the 17th Mediterranean Conference on Control and Automation，2009:452 －457．

［8］ Xin Yue，Zhang Zhenjiang，Liu Yun．A coverage hole detecting algorithm in wireless sensor networks［J］．Journal of Convergence Information Technology，2011，6（9）:159 －168．

［9］ Corke P，Peterson R，Rus D．Finding holes in sensor networks［C］∥Proceedings of the Workshop on Omniscient Space:Robot Control Architecture Geared Toward Adapting to Dynamic Environments at ICRA，2007．

［10］張紅武，王宏遠，豐洪才．一種無線傳感器網絡目標的分布式最優覆蓋算法［J］．小型微型計算機系統，2010，31（1）:17－21．

［11］蔣 丹．無線傳感器網絡覆蓋盲區的發現與修復方法研究［D］．沈陽:東北大學，2008．