基于極坐標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋盲區(qū)發(fā)現(xiàn)算法*

邢冬平， 段 富, 樊茂森

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

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)的覆蓋問題是無(wú)線傳感器網(wǎng)絡(luò)需要解決的基本問題之一[1]。所謂的覆蓋問題，即指特定的目標(biāo)監(jiān)測(cè)區(qū)域是否被無(wú)線傳感器充分覆蓋和處于完全監(jiān)視之下。產(chǎn)生覆蓋問題的原因主要來(lái)自以下幾個(gè)方面：1)無(wú)線傳感器大都通過隨機(jī)的形勢(shì)部署的，導(dǎo)致部分監(jiān)測(cè)區(qū)域沒有傳感器，產(chǎn)生覆蓋盲區(qū)；2)傳感器在使用的過程中損毀，能量耗盡等[2]造成的使用過程中的失效，產(chǎn)生覆蓋盲區(qū)作為衡量無(wú)線傳感器網(wǎng)絡(luò)質(zhì)量的重要參考，覆蓋盲區(qū)直接影響網(wǎng)線傳感網(wǎng)絡(luò)的收集數(shù)據(jù)的可靠性、完整性。因此，當(dāng)網(wǎng)絡(luò)中出現(xiàn)覆蓋盲區(qū)時(shí)，應(yīng)立即檢測(cè)到，以保持無(wú)線傳感器網(wǎng)絡(luò)的完整性、可靠性[3]。

當(dāng)前針對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋盲區(qū)發(fā)現(xiàn)的研究，許多研究者提出了一些檢測(cè)方法。Kanno J等人[4]先建立的通信連接圖，再用最大單純復(fù)形把通信連接圖轉(zhuǎn)換成為一個(gè)二維的單純復(fù)形，進(jìn)行對(duì)網(wǎng)絡(luò)中的覆蓋盲區(qū)進(jìn)行檢測(cè)。Dong D等人[5]利用代數(shù)拓?fù)淙ソ鞲衅鞴?jié)點(diǎn)的通信拓?fù)鋱D，該算法適用于包含移動(dòng)節(jié)點(diǎn)和靜態(tài)節(jié)點(diǎn)的混合型的無(wú)線傳感器網(wǎng)絡(luò)。Xin等人[6]依據(jù)無(wú)線傳感器網(wǎng)絡(luò)的覆蓋空洞由邊界弧包圍，提出了一種通過計(jì)算出邊界弧和邊界節(jié)點(diǎn)的位置，檢測(cè)到了網(wǎng)絡(luò)中的覆蓋盲區(qū)的算法。然而這些算法的代價(jià)都太大，特別是當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)過多時(shí)，整個(gè)網(wǎng)絡(luò)的通信代價(jià)和能量消耗都非常大。Ma Hwa-chun等人[7]提出一種以單個(gè)節(jié)點(diǎn)為中心，通過該節(jié)點(diǎn)與相鄰節(jié)點(diǎn)構(gòu)成的三角形進(jìn)行覆蓋盲區(qū)檢測(cè)的理論方法，并證明了該方法可行性。

本文在上述理論研究的基礎(chǔ)上，進(jìn)一步研究，提出一種基于極坐標(biāo)進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)盲區(qū)檢測(cè)的分布式算法。

1 問題描述

在無(wú)線傳感器網(wǎng)絡(luò)中由于初期采取隨機(jī)部署或者使用的路由算法不佳、環(huán)境惡劣等因素，而使節(jié)點(diǎn)失效，進(jìn)而使無(wú)線網(wǎng)絡(luò)中存在覆蓋盲區(qū)，如圖1所示。

圖1 空洞示意圖

圖1矩形區(qū)域是需要被傳感器檢測(cè)的目標(biāo)區(qū)域，灰色的部分是未被任何傳感器節(jié)點(diǎn)所覆蓋的目標(biāo)區(qū)域稱為覆蓋盲區(qū)。

本文的傳感器網(wǎng)絡(luò)采用靜態(tài)網(wǎng)絡(luò)模型，即所有節(jié)點(diǎn)都為靜態(tài)節(jié)點(diǎn)。每一個(gè)節(jié)點(diǎn)都具有通過定位服務(wù)獲得在部署區(qū)域邊界以內(nèi)的位置和坐標(biāo)，并能感知相鄰節(jié)點(diǎn)的坐標(biāo)。節(jié)點(diǎn)的最大通信半徑Rc是最大感知半徑Rs的2倍[8]。

2 理論基礎(chǔ)

2.1 極坐標(biāo)理論

在一個(gè)平面內(nèi)選定一點(diǎn)X和任一射線XO為極軸,則平面上任一點(diǎn)P在極坐標(biāo)系中的坐標(biāo)可以表示為P(ρ,θ)，其中,ρ為點(diǎn)X到點(diǎn)P的直線距離，θ為XO到XP的角度。本文使用極坐標(biāo)系來(lái)表示選定的節(jié)點(diǎn)與它相鄰節(jié)點(diǎn)的關(guān)系，并按極角的大小進(jìn)行排序。如果列表中存在極角相同的多個(gè)點(diǎn)，則只保留極徑較小的一個(gè)點(diǎn)。

如圖2所示，參考節(jié)點(diǎn)X有鄰居節(jié)點(diǎn)A,B,C,D,E,F,G,H,J,K,L,M。采用極坐標(biāo)表示后，按極角升序排列將得到有序列表L1={F,E,D,C,B,A,M,L,K,J,H,G,F} 。

圖2 節(jié)點(diǎn)分布圖

2 2 基于相鄰節(jié)點(diǎn)的幾何判定理論

Ma Hwa-chun等人[7]提出了關(guān)于選定節(jié)點(diǎn)的覆蓋盲區(qū)的幾何判定理論，并進(jìn)行了詳細(xì)的論證。具體地，當(dāng)選定節(jié)點(diǎn)與其2個(gè)鄰居節(jié)點(diǎn)構(gòu)成三角形且三角形的外接圓半徑R≤RS，則在該節(jié)點(diǎn)附近沒有覆蓋盲區(qū)；反之，當(dāng)R>RS或三角形的外接圓圓心Z不被其他傳感器節(jié)點(diǎn)覆蓋，則在該節(jié)點(diǎn)附近有覆蓋盲區(qū)。

2.3 三角形外接圓的計(jì)算

(1)

(2)

外接圓圓點(diǎn)Z在極坐標(biāo)系中的坐標(biāo)為(R，θZ),其中,θZ的計(jì)算公式如下

(3)

式中θ，L為節(jié)點(diǎn)B，C中極角較小的節(jié)點(diǎn)。

3 算法描述

在上述理論的基礎(chǔ)上，本文提出一種基于極坐標(biāo)表示的無(wú)線傳感器網(wǎng)絡(luò)覆蓋盲區(qū)的發(fā)現(xiàn)算法，該算法是分布式的算法，節(jié)點(diǎn)之間可并行執(zhí)行。算法的具體描述如下：

1) 隨機(jī)選取任何一個(gè)參考節(jié)點(diǎn)X，其平面直角坐標(biāo)為(a,b)。

2)找出該參考節(jié)點(diǎn)的所有與節(jié)點(diǎn)X的距離小于RS的節(jié)點(diǎn)，作為集合N。

3)對(duì)集合N中的所有元素求關(guān)于X的參考極坐標(biāo)位置并按極角大小排列生成列表L,對(duì)L進(jìn)行加工形成列表L1。

4) 從L1中選取兩點(diǎn)Ai和Aj，其中,i

a.If(△XAiAj的外接圓半徑R≤RS)節(jié)點(diǎn)X附近沒有覆蓋盲區(qū);

b.elseif(△XAiAj外接圓圓心Z被其他傳感器節(jié)點(diǎn)覆蓋)節(jié)點(diǎn)x附近沒有覆蓋盲區(qū);

c.else節(jié)點(diǎn)x附近有覆蓋盲區(qū)。

5)令L1=L1-{Ai}，重復(fù)步驟(4),直到列表L1為空。

4 仿真實(shí)驗(yàn)驗(yàn)證算法的有效性與性能

4.1 算法有效性驗(yàn)證

為了驗(yàn)證算法的有效性，將用計(jì)算機(jī)仿真軟件對(duì)現(xiàn)實(shí)傳感器無(wú)線網(wǎng)絡(luò)進(jìn)行模擬仿真。本文仿真實(shí)驗(yàn)采用的計(jì)算機(jī)硬件平臺(tái)為計(jì)算機(jī)：Thinkpad E420 EBC；處理器：Inter(R)Core(TM)i5—2430M CPU @2.40 GHz；安裝內(nèi)存(RAM)：6.00 GB；操作系統(tǒng)：Win 7旗艦版 64位操作系統(tǒng)；仿真軟件是Matlab 7.12。實(shí)驗(yàn)參數(shù)如下：網(wǎng)絡(luò)規(guī)模為100 m×100 m;感知半徑為10 m;通信半徑為20 m；節(jié)點(diǎn)個(gè)數(shù)為100個(gè)；數(shù)據(jù)包傳遞的能量消耗2 J；數(shù)據(jù)包接收的能量消耗為1 J。

在二維平面100 m×100 m的正方形區(qū)域內(nèi)，隨機(jī)部署100個(gè)傳感器節(jié)點(diǎn)在該區(qū)域內(nèi)，如圖3所示。

圖3 節(jié)點(diǎn)的隨機(jī)分布圖

在每個(gè)傳感器節(jié)點(diǎn)上并行的運(yùn)行算法上述漏洞檢測(cè)算法，可以成功監(jiān)測(cè)到目標(biāo)區(qū)域內(nèi)存在的覆蓋空洞，并成功監(jiān)測(cè)到這些覆蓋空洞的邊界節(jié)點(diǎn)。如圖4所示，在100 m×100 m的目標(biāo)區(qū)域內(nèi)存在4個(gè)覆蓋空洞，使用的算法可以檢測(cè)到全部26個(gè)邊界節(jié)點(diǎn)，用加粗線標(biāo)出。

圖4 覆蓋盲區(qū)和邊界節(jié)點(diǎn)的檢測(cè)

4.2 算法性能評(píng)估

為了驗(yàn)證本算法的性能，本文選取文獻(xiàn)[5]中算法為參照算法，在Matlab仿真環(huán)境下，比較了2種算法發(fā)現(xiàn)覆蓋盲區(qū)的效率。每種情況下分別進(jìn)行多次運(yùn)算，取其時(shí)間平均值，得到的結(jié)果如圖5所示：

圖5 不同算法下盲區(qū)發(fā)現(xiàn)時(shí)間表比較

從圖5中對(duì)比可看出:在相同盲區(qū)數(shù)量的前提下，本文算法的盲區(qū)發(fā)現(xiàn)的平均時(shí)間要少于文獻(xiàn)[5]中的算法。該結(jié)果即表明了本算法的可靠性，同時(shí)也體現(xiàn)了分布式算法的優(yōu)越性,提高了覆蓋盲區(qū)的發(fā)現(xiàn)效率。

5 結(jié) 論

由于傳感器初始分布的不均勻，且在使用過程中傳感器自身原因和惡劣環(huán)境的影響，傳感器覆蓋盲區(qū)的出現(xiàn)不可避免。通過上述實(shí)驗(yàn)，驗(yàn)證本算法不僅能找到覆蓋盲區(qū)，而且能找出覆蓋盲區(qū)所有邊界節(jié)點(diǎn)。檢測(cè)無(wú)線傳感網(wǎng)絡(luò)的覆蓋盲區(qū)，不僅為了確定傳感網(wǎng)絡(luò)的可用性，當(dāng)檢測(cè)出盲區(qū)后，如何找到一種合適的方法去修補(bǔ)盲區(qū)或者使用更好的傳感器節(jié)點(diǎn)的分布算法[10]，將是下一步研究的重點(diǎn)。

參考文獻(xiàn):

[1] Trajcevski G,Avci B,Zhou F,et al.Motion trends detection in wireless sensor networks[C]∥2012 IEEE 13th International Conference on Mobile Data Management (MDM),2012:232-237.

[2] 邢冀鵬.無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)覆蓋算法研究[D].武漢：華中科技大學(xué),2008.

[3] 劉麗萍,王 智,孫優(yōu)賢.無(wú)線傳感器網(wǎng)絡(luò)部署及其覆蓋問題研究[J].電子與信息學(xué)報(bào),2006,28(9):1752-1757.

[4] Kanno Jinko ,Buchart Jack G,Selmic Rastko R,et al.Detecting coverage holes in wireless sensor networks[C]∥Proceedings of 17th Mediterranean Conference on Control and Automation,2009:452- 457.

[5] Dong D,Liao X,Liu K,et al.Distributed coverage in wireless Ad Hoc and sensor networks by topological graph approaches[J].IEEE Transactions on Computers,2012,61(10):1417-1428.

[6] 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.

[7] Ma Hwachun ,Sahoo Prasan Kumar ,Chen Yenwen.Computational geometry based distributed coverage hole detection protocol in wireless sensor network[J].Journal of Network and Computer applications,2011,34:1743-1756.

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