王旭吾，盧坤

(1.湖北汽車工業(yè)學院 科技學院，湖北 十堰442002；2.哈爾濱工程大學，黑龍江 哈爾濱 150001)

無線傳感器網絡中基于幾何方法的覆蓋洞檢測

王旭吾1，盧坤2

(1.湖北汽車工業(yè)學院 科技學院，湖北 十堰442002；2.哈爾濱工程大學，黑龍江 哈爾濱 150001)

提出了一個基于幾何方法的覆蓋洞檢測算法，用以在網絡運行過程中找出覆蓋洞，仿真結果表明：此算法在能量消耗和檢測時間方面優(yōu)于TBRA算法。

無線傳感器網絡；覆蓋洞；覆蓋洞檢測

0 引言

近年來，隨著微電子控制系統(tǒng)、嵌入式處理器和無線通信技術的快速發(fā)展，使得無線傳感器網絡得到越來越廣泛的應用，也成為當前最熱門的研究領域之一。無線傳感器網絡由大量的傳感器節(jié)點構成，每個傳感器節(jié)點具有監(jiān)測、處理或者傳送環(huán)境信息的功能。無線傳感器網絡的應用包括棲息地和環(huán)境監(jiān)測、森林火災檢測、戰(zhàn)場監(jiān)視、智能空間和工業(yè)診斷等［1］。其中在安全和軍事上的應用總是需要目標區(qū)域能夠被網絡完整的覆蓋［2］。在無線傳感器網絡中，由于節(jié)點的隨機部署、節(jié)點能量的過早耗盡以及惡劣環(huán)境中部分網絡被1破壞，都會導致在網絡中形成覆蓋洞。覆蓋洞的出現(xiàn)會影響網絡現(xiàn)有的覆蓋率和連通性，從而影響網絡的服務質量。因此，在無線傳感器網絡中檢測和修復覆蓋洞，是網絡服務質量的一個重要組成部分［3］。

無線傳感器網絡的覆蓋可分為3種類型：無限制覆蓋，無障礙覆蓋，掃描覆蓋［4］。在這 3種類型中，無限制覆蓋著重于目標區(qū)域的覆蓋范圍最大化，適用于大多數(shù)的監(jiān)控應用。

無線傳感器網絡中的覆蓋問題，通常被稱為k-覆蓋問題［5］。k-覆蓋的意思是感知區(qū)域內的每一個點至少被k個傳感器覆蓋，其中k是一個預定義的非負整數(shù)。文獻［4］介紹了一種算法，通過計算感知圓域的重疊區(qū)域，來分析覆蓋問題。WSN應用中更常見的問題涉及一個特殊情況，即k=1。本文中只針對于這一種情況，即感知區(qū)域內的每個點至少被一個傳感器節(jié)點覆蓋。

目前大多數(shù)覆蓋洞檢測算法是集中式的，Wang［6］基于現(xiàn)有計算幾何中的Voronoi圖原理實現(xiàn)了覆蓋洞檢測，文獻［7］中提出了一個無線傳感器網絡中基于覆蓋率的洞檢測方法，文獻［8］中使用連接信息來識別邊界節(jié)點，Rao［9］則采用了虛擬坐標的方式實現(xiàn)覆蓋洞的測定，這些方法都需要整個網絡的概述。然而，隨著傳感器節(jié)點的數(shù)目明顯變大，這些算法將變得非常費時。因此，對于大型網絡，必須采用分布式的洞檢測方法，它可以把網絡分成更小的子網絡，并同時處理這些子網絡，從而確定覆蓋洞。在分布式算法中，網絡中的每一個傳感器節(jié)點能夠進行一些有限的計算，來確定該節(jié)點是否是一個洞邊界節(jié)點。然后用戶可以很容易地通過收集洞邊界節(jié)點的信息，來確定覆蓋洞。

1 相關工作

1.1 網絡模型

假設無線傳感器網絡中隨機分布有N個傳感器節(jié)點，目標區(qū)域是矩形區(qū)域。假設每個傳感器節(jié)點具有唯一的ID，且具有等同的感知和通信能力，其感知范圍和通信范圍分別是以r和R為半徑的圓域，且R=2r［10］。傳感器節(jié)點知道自己的地理位置［11］，并向其通信半徑范圍內的鄰居節(jié)點周期性的廣播其位置信息。節(jié)點在收到新的信息后，就會更新其內存里鄰居的位置信息。由于節(jié)點是隨機部署的，假設任意3個節(jié)點的感知圓交于一點的概率為0。此外，沒有2個節(jié)點部署在同一點，且每個節(jié)點至少有2個鄰居。

同時假設通信模式是二進制的，即傳感器節(jié)點在通信半徑R的圓域內能被檢測出，反之不能被檢測出；感知模式是二進制的，這意味著在感知半徑r圓域內的區(qū)域能被覆蓋，反之不能被覆蓋。

1.2 網絡模型

定義1：感知圓與感知圓域 傳感器節(jié)點可以檢測到其感知半徑內任一點的信息，那么節(jié)點感知半徑內的區(qū)域就稱為傳感器的感知圓域，其邊界就是感知圓。

定義2：覆蓋洞 無線傳感器網絡中某個連通的區(qū)域如果不被任何傳感器節(jié)點的感知圓域覆蓋，那么這個區(qū)域就是一個覆蓋洞。如圖1所示，陰影部分是一個覆蓋洞。

定義3：洞邊界 假設網絡中的覆蓋洞都不在監(jiān)測區(qū)域的邊界上，那么每一個覆蓋洞都與被覆蓋區(qū)域有分界線，此分界線稱之為洞邊界。

圖1 覆蓋洞

定義4：洞邊界節(jié)點 網絡中每個洞邊界都是由多條弧線構成，其中每條弧線都屬于某個傳感器節(jié)點的感知圓，那么這些對應的傳感器節(jié)點就稱為洞邊界節(jié)點。如圖2所示，洞H1的洞邊界的弧線分別屬于節(jié)點S1～S9的感知圓，那么節(jié)點S1～S9就是H1的洞邊界節(jié)點。一個節(jié)點可以是多個覆蓋洞的洞邊界節(jié)點，如圖2所示，節(jié)點S6分別是H1和H2的洞邊界節(jié)點。

定義5：感知圓缺口 每個洞邊界節(jié)點的感知圓上，屬于洞邊界的那一段弧未被任何節(jié)點的感知圓域覆蓋，就稱為感知圓缺口，如圖2所示，逆時針弧ab就是節(jié)點S2的一個感知圓缺口。

定義6：洞邊界交點 無線傳感器網絡中，如果存在2個洞邊界節(jié)點互為鄰居，那么這2個節(jié)點的交點至少有1個不被這2個節(jié)點之外的第3個節(jié)點的感知圓域覆蓋，則稱這樣的交點為洞邊界交點。如圖2所示，點a、b就是2個洞邊界交點。

圖2 洞邊界節(jié)點

由無線傳感器網絡的覆蓋條件可知，如果網絡中存在覆蓋洞，那么它肯定是由洞邊界節(jié)點圍成的。而圍成覆蓋洞的洞邊界節(jié)點肯定存在感知圓缺口。那么，找出網絡中所有的感知圓缺口，就能確定網絡中的洞邊界節(jié)點，進而就能判定網絡中的覆蓋洞。

2 覆蓋洞檢測算法

2.1 感知圓缺口的判定

在無線傳感器網絡中，為了保證節(jié)點間通信和對監(jiān)測區(qū)域的覆蓋，相鄰節(jié)點間的距離需小于通信半徑R。此時，兩節(jié)點的感知圓會產生2個交點，每個節(jié)點的感知圓都有一段弧被另一個節(jié)點的感知圓域覆蓋。假設每個傳感器節(jié)點都知道自己和其鄰居節(jié)點的坐標，那么，通過幾何方法，節(jié)點可以計算出每個鄰居的感知圓域對其感知圓的覆蓋，進而就能得到每個節(jié)點是否有感知圓缺口。

定義7：覆蓋區(qū)間 如圖3所示，網絡中一個節(jié)點S1的感知圓被其鄰居節(jié)點S2的感知圓域覆蓋，被覆蓋的部分是一條圓弧m，圓弧的2個端點分別為點A，B。不失一般性，假設A，m，B按逆時針方向相連，以節(jié)點S1的位置為原點建立直角坐標系。以X軸正方形為0弧度，X軸正方向逆時針到S1A，S1B的最小弧度角分別為a，b，那么區(qū)間［a，b］就稱為節(jié)點S2對節(jié)點S1的覆蓋區(qū)間。

圖3 覆蓋區(qū)間

算法1覆蓋區(qū)間計算算法

Step1：輸入節(jié)點S1、S2的位置坐標（x1，y1）、（x2，y2）；

Step2：分別列出以（x1，y1）、（x2，y2）為圓心，r為半徑的圓的方程，組成方程組，解出方程組的2組解（p1，q1）、（p2，q2），并計算

如果ni＞0，則

如果ni＜0，則

如果ni=0，那么當mi＞0時，ki=0，mi＜0時，ki=π；

Step4：計算 k4=min（k1，k2），k5=max（k1，k2），如果k4＜k3＜k5，那么a=k4，b=k5；否則，a=k5，b=k4+2π；

Step5：輸出［a，b］即為節(jié)點 S2對節(jié)點 S1的覆蓋區(qū)間。

對于網絡中的某一個節(jié)點S0，其鄰居分別為S1，S2，...，Sn，這些鄰居對S0的覆蓋區(qū)間分別為［a1，b1］，［a2，b2］，...，［an，bn］。 那么，節(jié)點 S0的邊界圓上未被這些區(qū)間的并集包含的區(qū)間就是未被覆蓋的區(qū)間，這樣就確定了感知圓缺口。

算法2感知圓缺口判定算法

Step1：任意選擇一個節(jié)點作為源節(jié)點S0；

夕陽透過玻璃窗，使整個房子變成了暖調子，爐上飄著煙，兩老正忙著把拉長的面一片一片地揪下來，扔進飄著肉香的鍋里。才讓抽著煙，給我們講述他和張偉的故事。此時此刻我只有一個心愿，回去一定要幫他找到張偉。

Step2：創(chuàng)建節(jié)點 S0的鄰居節(jié)點列表 L=｛S1，S2，...，Sn｝；

Step3：計算鄰居Si對S0的覆蓋區(qū)間 ［ai，bi］，如果存在s，t，使得as≤at且bs≥bt，則把節(jié)點St從鄰居列表L中刪除。L中剩下的節(jié)點，bmax=max（bi），若bmax＞bi+2π，則從L中刪掉Si。把L中剩下的節(jié)點按照對應的ai從小到大排序，得到一個新的列表L1={T1，T2，...，Tm}，其中節(jié)點Tj對應的覆蓋區(qū)間為［aj，bj］；

Step4：依次判斷不等式

的正確性，當不等式不成立時，說明存在感知圓缺口［bj，aj+1］，其對應的2個順時針鄰居分別為 Tj，Tj+1。最后判斷bm≥a1+2π的正確性，不等式如果不成立，則存在感知圓缺口，當bj＜2π時，缺口為［bj，a1+2π］，否則缺口為［bj-2π，a1］，對應的2個順時針鄰居分別為Tm，T1；

Step5：輸出存在感知圓缺口的節(jié)點S0，它的感知圓缺口［m1，n1］，［m2，n2］，...［mk，nk］，以及缺口分別對應的成對順時針鄰居節(jié)點［R1，T1］，［R2，T2］，...［Rk，Tk］。

2.2 覆蓋洞檢測算法

通過感知圓缺口判定算法，網絡中的節(jié)點可以分布式的判定自己是否有感知圓缺口。有感知圓缺口的節(jié)點肯定是洞邊界節(jié)點，找出網絡中所有的洞邊界節(jié)點后，檢測覆蓋洞的思想如下：以一個洞邊界節(jié)點為初始節(jié)點，對于它的一個感知圓缺口對應的成對順時針鄰居，后面的那個鄰居就是下一跳洞邊界節(jié)點。然后再找這個節(jié)點的成對順時針鄰居，保證前一個鄰居是上一跳的洞邊界節(jié)點，那么后一個鄰居就是下一跳洞邊界節(jié)點。重復這個過程，直到回到初始節(jié)點。

Step1：通過算法2確定網絡中所有的洞邊界節(jié)點，放入列表 L={S1，S2，...，Sn}，假設節(jié)點 Si最多只有3個感知圓缺口，對應的成對順時針鄰居分別為［Ria，Tia］，［Rib，Tib］，［Ric，Tic］，缺口數(shù)量不到3個時按順序出現(xiàn)；

Step2：創(chuàng)建覆蓋洞列表L1，初始為空，R為當前的洞邊界節(jié)點，S為當前的順時針成對鄰居的后一個。令R=S1并將S1放入L1，T=T1a；

Step3：找出Si=T，將Si放入L1。找出Rij=R，則令T=Tij，R=Si；

Step4：重復Step3直至T=S1。此時列表L1中的元素就是順時針圍成一個覆蓋洞的洞邊界節(jié)點。

重復利用算法3，當所有的洞邊界節(jié)點都被放入覆蓋洞列表，就檢測出了網絡中所有的覆蓋洞。

3 仿真結果

為了評估所提出覆蓋洞檢測算法的性能，利用Matlab7.0進行了仿真實驗。在200m×200m的區(qū)域內，部署600個節(jié)點，感知半徑r為5 m，通信半徑R為10 m，覆蓋洞數(shù)量分別為1，2，3，4，5，6，7，8時，與文獻［8］中的TBRA算法在數(shù)據(jù)包開銷和仿真時間方面進行了比較。實驗結果如圖4所示，結果表明，當覆蓋洞的數(shù)量較多時，此算法在能量消耗和檢測時間方面都優(yōu)于TBRA算法。

圖4 不同算法的實驗結果比較

4 結論

提出了一個基于幾何方法的覆蓋洞檢測算法，以在網絡運行過程中找出覆蓋洞。首先通過幾何方法計算節(jié)點的鄰居對其的覆蓋區(qū)間，識別有感知圓缺口的節(jié)點，從而可以確定網絡中所有的洞邊界節(jié)點，再找出所有洞邊界節(jié)點的相鄰情況，就可以檢測出網絡中的覆蓋洞。

［1］I.Akyildiz，W.Su，Y.Sankarasubramaniam，E.Cayirci. Wireless sensor networks:a survey［J］.Computer Networks，2002，39（4）：393-422.

［2］Meguerdichian.S，Koushanfar.F，Potkonjak.M，Srivastava.M.B.Coverage problems in wireless ad-hoc sensor networks［C］.Proc.INFOCOM 2003，2003：1380-1387.

［3］Martínez.J，Garcí.A，Corredor.I，López.L，Hernández. V，Dasilva.A.QoS in wireless sensor networks:survey and approach［C］.Proc.IEEE/ACM EATIS 2007，2007：1-8.

［4］Huang.C，Tseng.Y.The coverage problem in a wireless sensor network［C］.Proc.WSNA′03，2003：115-121.

［5］Habib.M.A，and Sajal.K.D.On computing conditional fault-tolerance measures for k-covered wireless sensor networks［C］.Proc.MSWiM 2006，2006：309-316.

［6］Wang.G，Cao.G，and La.Porta.T.Movement-assisted sensor deployment.Proceedings of the IEEE Conference on Computer Communications［C］.Hong Kong，China，2004：2469-2479.

［7］Shakkottai S，Srikant R and Shroff N.Unreliable sensor grids:Coverage，connectivity and diameter［C］.Proceedings of the IEEE Conference on Computer Communications.San Francisco，USA，2003：1073-1083.

［8］Y.Wang，J.Gao and J.S.B.Mitchell.Boundary Recognition in Sensor Networks by Topological Methods［C］. Proc.of MobiCom 2006，2006：122-133.

［9］Rao.A，Ratnasamy.S，Papadimitriou.C，Shenker.S，Stoica.I.Geographic routing without location information［C］.Proceedings ofthe 9th AnnualInternational Conference on Mobile Computing and Networking，SanDiego，CA，USA，2003：96-108.

［10］蘇瀚，汪蕓.傳感器網絡中無需地理信息的空洞填補算法［J］.計算機學報，2009，32（10）：158-170.

［11］B.Karp，H.T.Kung.Greedy Perimeter Stateless Routing for Wireless Networks ［C］.Proc.ACM/IEEE International Conference on Mobile Computing and Networking［C］.USA，Aug，2000:243-254.

Coverage Hole Detection in Wireless Sensor Networks Based on Geometric Method

Wang Xuwu1,Lu Kun2
（1.Science and Technology College,Hubei University of Automotive Technology,Shiyan 442002,China; 2.Harbin Engineering University,Harbin 150001,China）

A coverage hole detection algorithm based on the geometric method was presented to identify the coverage holes in network running.The simulation results show that the proposed algorithm is superior to TBRA algorithm in terms of the energy consumption and detection time.

wireless sensor networks;coverage holes;coverage holes detection

TP212；TP393

A

1008－5483（2014）01－0059－04

2014-02-26

王旭吾（1984-），女，湖北武漢人，碩士，主要從事應用數(shù)學方面的研究。

10.3969/j.issn.1008-5483.2014.01.0015