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

（太原理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西太原 030024）

0 引言

無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）在環(huán)境監(jiān)控、交通管理、智能建筑等領(lǐng)域有著廣泛的應(yīng)用，在這些實(shí)際應(yīng)用中，覆蓋控制是其首要關(guān)注的問(wèn)題［1］。為了使WSNs完成目標(biāo)監(jiān)測(cè)和信息獲取的任務(wù)，必須保證傳感器節(jié)點(diǎn)能有效地覆蓋被監(jiān)測(cè)的區(qū)域或目標(biāo)。WSNs的覆蓋完整度是服務(wù)質(zhì)量的重要度量指標(biāo)［2］。但是隨著網(wǎng)絡(luò)的持續(xù)運(yùn)行，傳感器節(jié)點(diǎn)可能因?yàn)槟芰亢谋M或者惡劣的目標(biāo)區(qū)域環(huán)境破壞而死亡，使得網(wǎng)絡(luò)的覆蓋區(qū)域缺失，形成覆蓋盲區(qū)。同時(shí)由于每個(gè)傳感器節(jié)點(diǎn)的感知半徑和通信半徑是固定的，當(dāng)節(jié)點(diǎn)隨機(jī)部署時(shí)，也可能產(chǎn)生覆蓋盲區(qū)，嚴(yán)重影響網(wǎng)絡(luò)的性能。因此，當(dāng)網(wǎng)絡(luò)中出現(xiàn)覆蓋盲區(qū)時(shí)，應(yīng)立即檢測(cè)尋找，以保持WSNs的感知、通信等服務(wù)質(zhì)量。

目前，針對(duì)WSNs覆蓋盲區(qū)發(fā)現(xiàn)已有一些解決方案提出。Wang G等人［3］使用voronoi圖發(fā)現(xiàn)覆蓋盲區(qū)，使用移動(dòng)節(jié)點(diǎn)去修復(fù)覆蓋盲區(qū)，該算法適用于隨機(jī)部署的WSNs，但是移動(dòng)節(jié)點(diǎn)需要消耗大量的能量。Ghrist R［4］和Silva V D［5］將代數(shù)拓?fù)渲械耐{(diào)理論應(yīng)用到盲區(qū)檢測(cè)中，但是該算法是一種集中式算法，計(jì)算量較大，不適合于大規(guī)模的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)有n個(gè)傳感器節(jié)點(diǎn)時(shí)，算法的時(shí)間復(fù)雜度為O（n5）。Buchart J T［6］首先建立 WSNs的通信連接圖，再使用最大單純復(fù)形把通信連接圖轉(zhuǎn)換成一個(gè)二維的單純復(fù)形，提出基于這種網(wǎng)絡(luò)模型的覆蓋盲區(qū)的檢測(cè)算法。Kanno J等人［7］使用代數(shù)拓?fù)淙ソ鞲衅鞴?jié)點(diǎn)的通信拓?fù)鋱D，該算法可以應(yīng)用于傳感器節(jié)點(diǎn)的坐標(biāo)未知的WSNs，尤其針對(duì)包含移動(dòng)節(jié)點(diǎn)和靜態(tài)節(jié)點(diǎn)的混合型的WSNs。Xin Yue等人［8］根據(jù)WSNs的覆蓋盲區(qū)由邊界弧包圍，提出一種檢驗(yàn)邊界節(jié)點(diǎn)和邊界弧的算法，進(jìn)而檢測(cè)到覆蓋盲區(qū)。Corke P［9］等人提出一種路徑密度算法（path density algorithm，PDA），該算法根據(jù)傳感器節(jié)點(diǎn)周圍的路徑密度檢測(cè)覆蓋盲區(qū)，檢測(cè)正確率較高，但是節(jié)點(diǎn)能量消耗較大。

基于上述研究基礎(chǔ)，本文對(duì)覆蓋盲區(qū)的發(fā)現(xiàn)作進(jìn)一步研究，提出了一種基于幾何圖形的分布式覆蓋盲區(qū)發(fā)現(xiàn)算法，每個(gè)傳感器節(jié)點(diǎn)并發(fā)的執(zhí)行該算法，根據(jù)相關(guān)的幾何理論檢測(cè)出整個(gè)網(wǎng)絡(luò)的覆蓋盲區(qū)和邊界節(jié)點(diǎn)。

1 定義與假設(shè)

1．1 基本定義

定義1 感知范圍相交的2個(gè)節(jié)點(diǎn)A，B互為鄰居節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)A，B之間的距離dA，B≤Rc，節(jié)點(diǎn)A，B互為1跳鄰居節(jié)點(diǎn)［10］;當(dāng)Rc＜dA，B＜2Rc，節(jié)點(diǎn)A，B互為 2 跳鄰居節(jié)點(diǎn)。

1．2 基本假設(shè)

1）傳感器節(jié)點(diǎn)同構(gòu)，即各個(gè)傳感器節(jié)點(diǎn)都具有相同的計(jì)算能力、通信能力和初始能量，并且時(shí)間同步;

2）傳感器節(jié)點(diǎn)能夠獲取自身的位置信息，并且都有唯一的ID號(hào);

3）節(jié)點(diǎn)的通信半徑Rc是感知半徑Rs的2倍;

4）傳感器節(jié)點(diǎn)采用圓盤(pán)布爾覆蓋模型［11］，即節(jié)點(diǎn)的感知范圍是以該節(jié)點(diǎn)為圓心，感應(yīng)半徑Rs的圓。

2 基于幾何圖形的盲區(qū)發(fā)現(xiàn)算法

2．1 理論基礎(chǔ)

定理1 當(dāng)節(jié)點(diǎn)與其2個(gè)鄰居節(jié)點(diǎn)構(gòu)成一個(gè)銳角三角形或者直角三角形，并且三角形的外接圓半徑R≤Rs，在該節(jié)點(diǎn)附近沒(méi)有覆蓋盲區(qū);反之，當(dāng)R＞Rs，在該節(jié)點(diǎn)附近有覆蓋盲區(qū)。

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

定理2 當(dāng)節(jié)點(diǎn)與其2個(gè)鄰居節(jié)點(diǎn)構(gòu)成一個(gè)鈍角三角形，并且三角形的外接圓半徑R≤Rs，在該節(jié)點(diǎn)附近沒(méi)有覆蓋盲區(qū);反之，當(dāng)R＞Rs，并且三角形的外接圓圓心Z不被其他傳感器節(jié)點(diǎn)覆蓋，在該節(jié)點(diǎn)附近有覆蓋盲區(qū)。

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

2．2 算法描述

基于上述定理，本文提出一種基于幾何圖形的WSNs覆蓋盲區(qū)發(fā)現(xiàn)算法，該算法是分布式算法，在每一個(gè)傳感器節(jié)點(diǎn)上并發(fā)執(zhí)行。算法的具體描述如下:

2．2．1 數(shù)據(jù)結(jié)構(gòu)

Ai和Aj為鄰居節(jié)點(diǎn);

N為節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合;

Nt為縱坐標(biāo)大于等于節(jié)點(diǎn)坐標(biāo)的鄰居節(jié)點(diǎn)集合;

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

Nb為縱坐標(biāo)小于節(jié)點(diǎn)坐標(biāo)的鄰居節(jié)點(diǎn)集合;

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

2．2．2 算法流程

1）隨機(jī)選擇任何一個(gè)節(jié)點(diǎn)X，其坐標(biāo)為（a，b）;

2）找出該節(jié)點(diǎn)X的1跳、2跳鄰居節(jié)點(diǎn)，作為集合N;

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

4）把集合Nt中的元素按照橫坐標(biāo)升序排列，構(gòu)成新的集合Ntx;

5）從Ntx找出2個(gè)節(jié)點(diǎn)Ai和Aj，其中，Ai橫坐標(biāo)小于Aj的橫坐標(biāo);

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

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

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

{if（R≤Rs）在X周圍沒(méi)有覆蓋盲區(qū);

else 在X周圍有覆蓋盲區(qū);}

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

{if（R≤Rs）在X周圍沒(méi)有覆蓋盲區(qū);

else{檢查Z是否被其他傳感器節(jié)點(diǎn)覆蓋;

10）if（Z被其他傳感器節(jié)點(diǎn)覆蓋）

在X周圍沒(méi)有覆蓋盲區(qū);

else在X周圍有覆蓋盲區(qū);

}∥endelse

}∥endif

11）令Nt=Nt－{Ai};

}while（Ntx≠?）

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

13）把集合Nb中的元素按照橫坐標(biāo)降序排列，構(gòu)成新的集合Nbx;

14）從Nbx找出2個(gè)節(jié)點(diǎn)Ai和Aj，其中Ai橫坐標(biāo)大于Aj的橫坐標(biāo);

15）對(duì)以上2個(gè)節(jié)點(diǎn)Ai和Aj執(zhí)行操作類似步驟（6）到步驟（11），直至集合Nbx為空。

3 算法仿真與性能評(píng)估

3．1 算法有效性驗(yàn)證

為驗(yàn)證上述算法的有效性，在Windows XP上采用Matlab 7．0作為實(shí)驗(yàn)平臺(tái)實(shí)現(xiàn)上述算法。仿真參數(shù)如表1。

表1 仿真參數(shù)列表Tab 1 Sheet of simulation parameters

仿真在二維正方形1000 m×1000 m的實(shí)驗(yàn)區(qū)域進(jìn)行，100個(gè)傳感器節(jié)點(diǎn)在該區(qū)域內(nèi)隨機(jī)部署，如圖1所示。

圖1 節(jié)點(diǎn)的隨機(jī)分布圖Fig 1 Random distribution diagram of nodes

通過(guò)在每個(gè)傳感器節(jié)點(diǎn)并發(fā)地運(yùn)行上述的WSNs的覆蓋盲區(qū)發(fā)現(xiàn)算法，能夠發(fā)現(xiàn)監(jiān)控區(qū)域中得覆蓋盲區(qū)，并且檢測(cè)到覆蓋盲區(qū)的邊界節(jié)點(diǎn)。如圖2所示，在1 000 m×1000 m的監(jiān)控區(qū)域中，有4個(gè)覆蓋盲區(qū)，使用上述的算法，可以檢測(cè)到17個(gè)覆蓋盲區(qū)的邊界節(jié)點(diǎn)，并且用加粗標(biāo)出。

圖2 覆蓋盲區(qū)和邊界節(jié)點(diǎn)的檢測(cè)Fig 2 Detection of coverage blind spots and boundary nodes

3．2 算法性能評(píng)估

為評(píng)估本文算法的性能，選取文獻(xiàn)［9］中的路徑密度算法（PDA）作為比較對(duì)象，采用Matlab 7．0作為仿真平臺(tái)實(shí)現(xiàn)以上2種算法，在能量消耗方面對(duì)2種算法的性能進(jìn)行比較與分析。在1000 m×1000 m的監(jiān)控區(qū)域中，隨機(jī)部署傳感器節(jié)點(diǎn)個(gè)數(shù)為{200，400，600，800，1 000}，節(jié)點(diǎn)的感知半徑為40 m，通信半徑為80 m，其他仿真參數(shù)與表1相同，仿真結(jié)果如圖3所示。圖3反映的是本文算法與PDA在檢測(cè)覆蓋盲區(qū)時(shí)節(jié)點(diǎn)消耗能量的對(duì)比情況。從實(shí)驗(yàn)結(jié)果可以看出:隨著網(wǎng)絡(luò)中覆蓋盲區(qū)個(gè)數(shù)的增加，平均節(jié)點(diǎn)能量消耗也增加;相比較于PDA，本文算法的平均節(jié)點(diǎn)能量消耗較小，這是因?yàn)楸疚乃惴ㄅ卸ü?jié)點(diǎn)附近是否存在覆蓋盲區(qū)時(shí)算法復(fù)雜度低，消耗的節(jié)點(diǎn)能量較少。

圖3 平均節(jié)點(diǎn)能量消耗比較Fig 3 Comparison of average energy consumption of sensor nodes

4 結(jié)論

針對(duì)WSNs中覆蓋盲區(qū)的問(wèn)題，本文提出了一種基于幾何圖形的分布式覆蓋盲區(qū)發(fā)現(xiàn)算法，根據(jù)簡(jiǎn)單而有效的幾何規(guī)則判定是否存在覆蓋盲區(qū)。仿真實(shí)驗(yàn)結(jié)果表明:該算法能夠有效地檢測(cè)覆蓋盲區(qū)和邊界節(jié)點(diǎn)，并且能有效降低節(jié)點(diǎn)的平均能量消耗，延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期，性能優(yōu)于PDA。下一步研究的重點(diǎn)是在檢測(cè)到覆蓋盲區(qū)和邊界節(jié)點(diǎn)之后，如何修復(fù)覆蓋盲區(qū)，從而進(jìn)一步地提高網(wǎng)絡(luò)的服務(wù)質(zhì)量。

［1］ 趙 旭，雷 霖，代傳龍．無(wú)線傳感器網(wǎng)絡(luò)的覆蓋控制［J］．傳感器與微系統(tǒng)，2007，26（8）:62 －65．

［2］ 張鼎興，徐 明，唐文勝．無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自調(diào)度冗余覆蓋算法［J］．傳感器與微系統(tǒng)，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］張紅武，王宏遠(yuǎn)，豐洪才．一種無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)的分布式最優(yōu)覆蓋算法［J］．小型微型計(jì)算機(jī)系統(tǒng)，2010，31（1）:17－21．

［11］蔣 丹．無(wú)線傳感器網(wǎng)絡(luò)覆蓋盲區(qū)的發(fā)現(xiàn)與修復(fù)方法研究［D］．沈陽(yáng):東北大學(xué)，2008．