無線傳感器網(wǎng)絡(luò)中基于幾何方法的覆蓋洞檢測(cè)

王旭吾，盧坤

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

無線傳感器網(wǎng)絡(luò)中基于幾何方法的覆蓋洞檢測(cè)

王旭吾1，盧坤2

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

提出了一個(gè)基于幾何方法的覆蓋洞檢測(cè)算法，用以在網(wǎng)絡(luò)運(yùn)行過程中找出覆蓋洞，仿真結(jié)果表明：此算法在能量消耗和檢測(cè)時(shí)間方面優(yōu)于TBRA算法。

無線傳感器網(wǎng)絡(luò)；覆蓋洞；覆蓋洞檢測(cè)

0 引言

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

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

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

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

1 相關(guān)工作

1.1 網(wǎng)絡(luò)模型

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

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

1.2 網(wǎng)絡(luò)模型

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

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

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

圖1 覆蓋洞

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

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

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

圖2 洞邊界節(jié)點(diǎn)

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

2 覆蓋洞檢測(cè)算法

2.1 感知圓缺口的判定

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

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

圖3 覆蓋區(qū)間

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

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

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

如果ni＞0，則

如果ni＜0，則

如果ni=0，那么當(dāng)mi＞0時(shí)，ki=0，mi＜0時(shí)，ki=π；

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

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

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

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

Step1：任意選擇一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)S0；

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

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

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

Step4：依次判斷不等式

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

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

2.2 覆蓋洞檢測(cè)算法

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

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

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

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

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

重復(fù)利用算法3，當(dāng)所有的洞邊界節(jié)點(diǎn)都被放入覆蓋洞列表，就檢測(cè)出了網(wǎng)絡(luò)中所有的覆蓋洞。

3 仿真結(jié)果

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

圖4 不同算法的實(shí)驗(yàn)結(jié)果比較

4 結(jié)論

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

［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］蘇瀚，汪蕓.傳感器網(wǎng)絡(luò)中無需地理信息的空洞填補(bǔ)算法［J］.計(jì)算機(jī)學(xué)報(bào)，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-），女，湖北武漢人，碩士，主要從事應(yīng)用數(shù)學(xué)方面的研究。

10.3969/j.issn.1008-5483.2014.01.0015