洪 峰,劉 旭,易東云
(國防科學(xué)技術(shù)大學(xué)理學(xué)院,湖南 長沙410073)
無線傳感器網(wǎng)絡(luò) WSN(Wireless Sensor Network)是由大量廉價(jià)傳感器節(jié)點(diǎn)通過自組織形式組成的網(wǎng)絡(luò)系統(tǒng)。由于無線傳感器網(wǎng)絡(luò)組成的分布式系統(tǒng)廣泛而潛在的應(yīng)用前景,包括用于國防監(jiān)控、環(huán)境監(jiān)測、礦區(qū)救險(xiǎn)以及醫(yī)療和交通等各種領(lǐng)域,吸引了很多研究者的研究興趣[1~5]。無線傳感器的一個(gè)顯著特點(diǎn)是體積小、能耗較低,通過大量的傳感器組成密集型的大規(guī)模網(wǎng)絡(luò)去完成特定的任務(wù)。覆蓋是衡量其工作性能的重要指標(biāo),通過研究傳感器覆蓋問題可提高傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量。當(dāng)網(wǎng)絡(luò)部署完畢后,如何評(píng)價(jià)或動(dòng)態(tài)監(jiān)測傳感器網(wǎng)絡(luò)對(duì)目標(biāo)區(qū)域的覆蓋性能是一個(gè)基本但亟待解決的問題[6,7]。由于受到價(jià)格成本和自身體積的限制,傳感器節(jié)點(diǎn)的事件處理能力、通信帶寬以及電源能量等資源極為有限。因此,研究在有限的信息條件下,快速有效地確定傳感器網(wǎng)絡(luò)對(duì)目標(biāo)區(qū)域的覆蓋情況具有重大意義。
本文考慮區(qū)域覆蓋問題,給定一個(gè)區(qū)域,要求在任意時(shí)刻傳感器網(wǎng)絡(luò)可監(jiān)控到該區(qū)域的所有子區(qū)域。區(qū)域覆蓋往往出現(xiàn)在氣候監(jiān)測、森林防火等應(yīng)用場景中[8]。區(qū)域覆蓋的典型特征是有明確的邊界,以森林火災(zāi)監(jiān)測為例,可以假設(shè)邊界節(jié)點(diǎn)是固定的,而內(nèi)部節(jié)點(diǎn)則由于動(dòng)物移動(dòng)等干擾會(huì)出現(xiàn)一定的位置偏差。因此,其內(nèi)部區(qū)域的覆蓋往往存在不確定性,需要實(shí)時(shí)快速確定覆蓋漏洞。本文考慮簡單傳感器,針對(duì)特定的檢測任務(wù)配備了相應(yīng)的感知原件,同時(shí),每個(gè)傳感器以一定的頻率和周圍節(jié)點(diǎn)通信。為簡單起見,可假設(shè)通信距離和感知半徑成一定比例關(guān)系,滿足三角形覆蓋條件,即按照通信距離兩兩相鄰的三個(gè)傳感器可以完全覆蓋其連線圍成的三角形區(qū)域。據(jù)此我們可以利用拓?fù)浞椒焖倥卸▊鞲衅鞯母采w情況,可以從硬件設(shè)計(jì)上略去傳感器的地理信息裝置,如GPS定位儀。由于維持和交流額外的地理信息需要專門的硬件模塊支持,且消耗有限的能源[9],因此無需地理信息的漏洞檢測算法有助于簡化傳感器設(shè)計(jì),提高系統(tǒng)可靠性和降低制造成本。
無線傳感器網(wǎng)絡(luò)的布局及覆蓋問題的研究在國內(nèi)外引起了極大的研究興趣,現(xiàn)將簡要介紹與本文相關(guān)內(nèi)容。
文獻(xiàn)[6]結(jié)合區(qū)域封閉性和計(jì)算幾何的相關(guān)知識(shí)來解決無線傳感器網(wǎng)絡(luò)覆蓋度判定問題。文獻(xiàn)[8]利用貪心算法和幾何理論研究了優(yōu)化覆蓋問題,通過節(jié)點(diǎn)狀態(tài)調(diào)度機(jī)制轉(zhuǎn)換提高節(jié)點(diǎn)覆蓋性能,同時(shí)減少能量消耗。虛擬力算法[10]把每個(gè)節(jié)點(diǎn)看作一個(gè)虛擬的帶電粒子,用物理學(xué)原理對(duì)節(jié)點(diǎn)布局,使網(wǎng)絡(luò)覆蓋區(qū)域最大化。在全局占領(lǐng)映射圖[11]中,每一個(gè)節(jié)點(diǎn)都能知道全局或局部的占領(lǐng)映射圖,據(jù)此進(jìn)一步可以得到Voronoi圖和Delaunay三角剖分圖兩類算法[4,5,12]。該方法的不足之處在于對(duì)傳感器節(jié)點(diǎn)的感知能力的要求較高,且覆蓋檢測涉及繁復(fù)的幾何計(jì)算。文獻(xiàn)[13]利用不相交覆蓋集連續(xù)重組方法對(duì)覆蓋區(qū)域重新劃分的方式研究冗余覆蓋的降低,以減少能量消耗。文獻(xiàn)[14]研究了如何減少簇頭節(jié)點(diǎn)失效對(duì)覆蓋的影響,利用pLEACH算法對(duì)覆蓋區(qū)域進(jìn)行合理劃分,然后在每個(gè)區(qū)域內(nèi)選擇簇頭節(jié)點(diǎn),以有效地延長網(wǎng)絡(luò)生命周期。文獻(xiàn)[15]研究了基于邊界收縮的虛擬力算法,用于傳感器網(wǎng)絡(luò)的自動(dòng)布局。
上述方法在計(jì)算覆蓋情況時(shí)的共同特點(diǎn)是利用節(jié)點(diǎn)的準(zhǔn)確位置,通過計(jì)算幾何的方法探測覆蓋盲區(qū),具有較高的計(jì)算復(fù)雜度。此外,傳感器節(jié)點(diǎn)需要提供精確的地理信息,而地理位置信息的獲取需要節(jié)點(diǎn)裝備GPS定位設(shè)備或者部署大量用于定位的信標(biāo)節(jié)點(diǎn),在一定程度上增加了設(shè)計(jì)及制造成本。
拓?fù)鋽?shù)據(jù)分析[16]是將拓?fù)涔ぞ哂糜跀?shù)據(jù)分析和處理的一項(xiàng)技術(shù),它主要對(duì)數(shù)據(jù)內(nèi)蘊(yùn)的拓?fù)涮匦越?,通過代數(shù)拓?fù)涞氖侄谓沂緮?shù)據(jù)的本質(zhì)結(jié)構(gòu)。傳感器網(wǎng)絡(luò)的覆蓋問題可以抽象為一個(gè)拓?fù)鋽?shù)據(jù)分析問題,將覆蓋漏洞檢測等價(jià)于網(wǎng)絡(luò)拓?fù)涞囊痪S代數(shù)同調(diào)群的計(jì)算問題。
假定傳感器的探測半徑為rc,通信半徑為rb,且滿足rc≥rb/3。此時(shí)任意三個(gè)傳感器A、B和C,只要滿足兩兩距離小于rb,則它們圍成的三角形區(qū)域?qū)⒈煌耆采w,如圖1所示。
Figure 1 Theory of triangle coverage圖1 三角形區(qū)域覆蓋原理
這個(gè)事實(shí)可以簡單證明如下:不妨設(shè)rb≥BC≥AB≥AC ?,F(xiàn)以BC為弦,以BC中垂線A點(diǎn)所在一側(cè)距離BC為3/3BC 的O點(diǎn)為圓心作圓,此時(shí)有 ∠BOC= ∠BOM = 120°,其中M是BC中垂線延長后與圓O的交,如圖2所示。以下證明A點(diǎn)將被圓O覆蓋。否則,A點(diǎn)一定在圓O外。
由于AB≥AC ,此時(shí)AB一定與圓O交于圓弧MC上的某點(diǎn),不妨設(shè)為D點(diǎn)。此時(shí)一定有 ∠BOD ≥ ∠BOM = 1 20°,因 此BD≥BC ,導(dǎo)致AB≥BC ,這與rb≥BC≥AB≥AC 矛盾。
Figure 2 Diagrammatic sketch of proving圖2 證明示意圖
于是,以A、B和C為圓心,以BO 為半徑的三個(gè)圓的并將完全覆蓋三角形ABC。而BO=論。有了上述結(jié)果,我們就無需考慮三個(gè)節(jié)點(diǎn)的詳細(xì)相對(duì)位置,測量它們的兩兩距離即可判定它們對(duì)三角形區(qū)域的覆蓋情況。
以森林防火問題為例,由于森林有固定的邊界,本文也假設(shè)傳感器網(wǎng)絡(luò)探測區(qū)域的邊界是固定的。首先,邊界上部署了相鄰距離不超過rb的若干個(gè)傳感器,這樣邊界上的傳感器可以互相通信。然后,在探測區(qū)域內(nèi)部隨機(jī)地或者規(guī)則地部署傳感器,傳感器節(jié)點(diǎn)為頂點(diǎn),兩個(gè)傳感器能夠互相通信則構(gòu)成邊。若整個(gè)探測區(qū)域被邊長不超過rb的三角形所剖分,則整個(gè)區(qū)域?qū)⒈煌耆采w,即沒有覆蓋盲區(qū)。若某個(gè)節(jié)點(diǎn)不能正常工作,則無法與其他能與之通信的節(jié)點(diǎn)構(gòu)成邊,這樣就可能會(huì)出現(xiàn)覆蓋盲區(qū)。設(shè)網(wǎng)絡(luò)的通信拓?fù)鋱D為G,由于傳感器的通信半徑為rb,只需檢查G是否全由三角形張成即可,這樣完全省去了計(jì)算幾何的處理過程,大大提升了計(jì)算速度。
由于三角形可以自然地?cái)U(kuò)張為一個(gè)二維的Vietoris-Rips復(fù)形[17,18],因此可以通過計(jì)算 網(wǎng)絡(luò)通信關(guān)系拓?fù)涞亩A單純同調(diào)群[12]的生成元的個(gè)數(shù)來判斷G對(duì)目標(biāo)區(qū)域的覆蓋情況。簡單地說,一階單純同調(diào)群的生成元的個(gè)數(shù)就是覆蓋漏洞的個(gè)數(shù)。如果G的一階單純同調(diào)群的生成元的個(gè)數(shù)大于零,便可以立即判斷傳感器網(wǎng)絡(luò)存在覆蓋盲區(qū)。文獻(xiàn)[18]給出了一般情況下的單純同調(diào)群的生成元的計(jì)算方法,這里使用的是它的一個(gè)特例。
應(yīng)用如上的方法利用Java進(jìn)行仿真實(shí)驗(yàn)。我們做了四組實(shí)驗(yàn),分析以隨機(jī)、正方形網(wǎng)格、三角形網(wǎng)格以及規(guī)則的方式部署傳感器節(jié)點(diǎn)的網(wǎng)絡(luò)覆蓋情況。按照網(wǎng)格的方式部署的傳感器初始時(shí)刻能夠完全覆蓋關(guān)注區(qū)域,正如實(shí)際檢測時(shí)可能遇到的情況一樣,隨后對(duì)初始部署位置進(jìn)行一定的擾動(dòng),這時(shí)傳感器的相對(duì)位置發(fā)生一定的變化,有可能出現(xiàn)覆蓋漏洞,然后用本文方法進(jìn)行漏洞檢測,快速生成結(jié)果。
為簡單起見,假設(shè)探測區(qū)域是邊長為100m的正方形區(qū)域,盡管我們的方法對(duì)區(qū)域的形狀并不敏感。設(shè)節(jié)點(diǎn)的感知半徑為rb。
在邊界固定生成40個(gè)傳感器節(jié)點(diǎn)(即邊界上每隔10m有一個(gè)傳感器),第一組實(shí)驗(yàn)在正方形區(qū)域內(nèi)部隨機(jī)部署100個(gè)傳感器節(jié)點(diǎn),第二組隨機(jī)部署200個(gè)傳感器節(jié)點(diǎn),如表1所示。
Table 1 Blind zone detection of random distribution表1 隨機(jī)部署傳感器網(wǎng)絡(luò)的漏洞檢測
從表1中可以看出,由于節(jié)點(diǎn)的分布不規(guī)則、不均勻,隨機(jī)部署的傳感器網(wǎng)絡(luò),很容易出現(xiàn)覆蓋盲區(qū)。而且還可以看出,隨著傳感器節(jié)點(diǎn)數(shù)目的上升,覆蓋盲區(qū)得到明顯的改善;隨著感知半徑的增加,覆蓋盲區(qū)也會(huì)呈現(xiàn)減少趨勢(shì),直至消失。
按照正方形網(wǎng)格部署傳感器網(wǎng)絡(luò),網(wǎng)格間隔為10m,一共可部署121個(gè)傳感器節(jié)點(diǎn),如圖3所示。
Figure 3 Square distribution圖3 正方形網(wǎng)格部署
隨后給予不同程度的擾動(dòng),給每個(gè)點(diǎn)的坐標(biāo)加入隨機(jī)擾動(dòng)。第一組擾動(dòng)為零,第二組和第三組的擾動(dòng)量分別為1m和2m,所產(chǎn)生的影響如表2所示。
Table 2 Blind zone detection of square distribution表2 正方形網(wǎng)格部署的傳感器網(wǎng)絡(luò)漏洞檢測
因?yàn)楣?jié)點(diǎn)的間隔為10m,則當(dāng)rb<10時(shí),無擾動(dòng)的情況下傳感器無法形成網(wǎng)絡(luò),是121個(gè)孤立的節(jié)點(diǎn);當(dāng)rb= 1 0 2時(shí),無擾動(dòng)的網(wǎng)格部署恰好完全覆蓋目標(biāo)區(qū)域。因此,當(dāng)rb=14時(shí),小于上述臨界值,恰好有100個(gè)覆蓋漏洞,盡管每個(gè)漏洞的規(guī)模很小。于是,當(dāng)增加少許的擾動(dòng)后,擾動(dòng)越大,覆蓋漏洞數(shù)反而越少,但這是以若干較大的漏洞的出現(xiàn)為代價(jià)的。
用等邊三角形對(duì)目標(biāo)區(qū)域做完全剖分,三角形邊長為10m,共部署149個(gè)傳感器節(jié)點(diǎn)。由于是在固定的正方形區(qū)域內(nèi),我們保證區(qū)域內(nèi)部的點(diǎn)均構(gòu)成等邊三角形,而將那些本應(yīng)在區(qū)域外部的點(diǎn)置于邊界上,如圖4所示。
Figure 4 Triangle distribution圖4 三角形網(wǎng)格部署
此時(shí)傳感器密度高于正方形網(wǎng)格部署。隨后給予和正方形網(wǎng)格部署時(shí)類似的擾動(dòng),所產(chǎn)生的影響如表3所示。
Table 3 Blind zone detection of triangle distribution表3 三角形網(wǎng)格部署的傳感器網(wǎng)絡(luò)漏洞檢測
當(dāng)感知半徑為9m時(shí),除邊界上的一些點(diǎn)外,大部分點(diǎn)均為孤立節(jié)點(diǎn)。因?yàn)槿切尉W(wǎng)格的邊長是10m,所以當(dāng)感知半徑為10m時(shí),無擾動(dòng)的一組恰好完全覆蓋目標(biāo)區(qū)域,而對(duì)于1m擾動(dòng)的情況,出現(xiàn)了17個(gè)漏洞,即覆蓋盲區(qū),對(duì)于2m擾動(dòng)的情況,直接將覆蓋區(qū)域分成了兩個(gè)不連通的區(qū)域。
前三組實(shí)驗(yàn)驗(yàn)證了本文所提方法的有效性:在探測距離沒有達(dá)到部署設(shè)定的臨界值時(shí),大部分傳感器都是孤立的節(jié)點(diǎn),當(dāng)探測距離等于臨界值時(shí),恰好完全覆蓋整個(gè)探測區(qū)域;加入擾動(dòng)之后,傳感器的位置發(fā)生變化,可能會(huì)出現(xiàn)覆蓋盲區(qū),本文提出的方法快速地檢測出了盲區(qū),并且符合實(shí)際的情況。
本小節(jié)針對(duì)4.2節(jié)和4.3節(jié)所述的規(guī)則部署區(qū)域,人為地去掉某些傳感器來模擬實(shí)際中傳感器失效的情況,以驗(yàn)證利用單純同調(diào)群是否能夠快速地檢測出漏洞。對(duì)于正方形和三角形網(wǎng)格部署,在恰好完全覆蓋的情況下,隨機(jī)刪除5個(gè)、10個(gè)、20個(gè)傳感器節(jié)點(diǎn),檢驗(yàn)該方法能否快速且正確地檢測出漏洞,所得結(jié)果如表4所示。
Table 4 Blind zone detection after deleting nodes表4 刪除節(jié)點(diǎn)后的漏洞檢測
由表4可以看出,當(dāng)去掉某些傳感器節(jié)點(diǎn)時(shí),傳感器網(wǎng)絡(luò)出現(xiàn)漏洞。本文所提方法確實(shí)探測到了漏洞的存在,且探測時(shí)間均小于1s。我們隨后將去掉的傳感器節(jié)點(diǎn)的各網(wǎng)絡(luò)以圖像的方式呈現(xiàn),發(fā)現(xiàn)圖像中顯示的漏洞個(gè)數(shù)與應(yīng)用本文所提方法計(jì)算所得的漏洞個(gè)數(shù)是一致的。
針對(duì)簡單傳感器網(wǎng)絡(luò)的覆蓋問題,本文提出了一種快速判定方法,它僅僅假設(shè)傳感器節(jié)點(diǎn)的通信半徑和探測半徑滿足一定的比例關(guān)系即三角形覆蓋條件,則可根據(jù)通信拓?fù)溲杆倥卸▊鞲衅骶W(wǎng)絡(luò)對(duì)目標(biāo)區(qū)域的覆蓋情況。證明了三角形覆蓋條件的必要性,并用仿真實(shí)驗(yàn)驗(yàn)證了所提方法的有效性。該方法不需要知道傳感器節(jié)點(diǎn)的完整地理信息,從而大大降低了對(duì)傳感器設(shè)計(jì)和制造的要求,并有利于提高傳感器的能效和網(wǎng)絡(luò)可靠性。
[1] Chen Lin-xing.Technology and application of wireless sensors network[M].Beijing:Electronic Industry Publisher,2009.(in Chinese)
[2] Ma Zu-chang,Sun Yi-ning,Mei Tao.Summary of wireless sensors network[J].Journal of China Institute of Communications,2004,25(4):114-124.(in Chinese)
[3] Tamboli N,Younis M.Coverage-aware connectivity restoration in mobile sensor network[J].Journal of Network and Computer Applications,2010,33(4):363-374.
[4] Lu Ke-zhong,Chen Guo-liang,F(xiàn)eng Yu-hong.Approximate algorithm of the minimum relaying nodes of wireless sensors network[J].Chinese Science:Information Science,2010,40(11):1473-1482.(in Chinese)
[5] Carbunar B,Grama A.Redundancy and coverage detection in sensor networks[J].ACM Transactions on Sensor Networks,2002,2(1):94-128.
[6] Fan Gao-jun,Jin Shi-yao.An algorithm for evaluating the coverage degrees of the wireless sensor network with arbitrary sensing areas[J].Computer Engineering & Science,2010,32(10):12-15.(in Chinese)
[7] Tao Dan,Ma Hua-dong,Liu Liang.A virtual potential field based coverage-enhancing algorithm for directional sensor networks[J].Journal of Software,2007,18(5):1152-1163.(in Chinese)
[8] Wang Wei,Lin Feng,Zhou Ji-liu.Research progress on coverage problem in wireless sensor networks[J].Application Research on Computer,2010,27(1):32-35.(in Chinese)
[9] Liu Ming,Cao Jian-nong,Zheng Yuan,et al.Analysis for multi-coverage problem in wireless sensor networks[J].Journal of Software,2007,18(1):127-136.(in Chinese)
[10] Khatib Q.Real-time obstacle avoidance for manipulators and mobile robots[J].International Journal of Robotics Research,1986,5(1):90-98.
[11] Liu Ben-yuan,Towsley D.A study of the coverage of large scale sensor networks[C]∥Proc of 2004IEEE International Conference on Mobile Ad-Hoc and Sensor System,2004:475-483.
[12] Xu Peng-fei,Chen Zhi-gang,Deng Xiao-heng.Distributed Voronoi coverage algorithm in wireless sensor networks[J].Journal of Communication,2010,31(8):16-25.(in Chinese)
[13] Zhang H,Hou J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Wireless Ad Hoc and Sensor Networks:An International Journal,2005,1(1-2):89-123.
[14] Gao Tie-gang,Niu Wei-wei.A cluster head election algorithm based on the coverage of nodes[J].Computer Engineering &Science,2011,33(5):1-8.(in Chinese)
[15] Zhang Ying,Guo Peng,Zhou Zong-yi.Research on the coverage algorithms for mobile sensor networks[J].Computer Engineering & Science,2008,30(2):81-83.(in Chinese)
[16] Carlsson G.Topology and data[J].Bulletin(New Series)of the American Mathematical Society,2010,46(2):255-308.
[17] Chambers E W,de Silva V,Erickson J,et al.Vietoris-rips complexes of planar point sets[J].Discrete Comput Geom,2010,44(1):75-90.
[18] Zomorodian A.Computational topology[M]∥Algorithms and Theory of Computation Handbook.Second Edition,2009.
附中文參考文獻(xiàn):
[1] 陳林星.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京:電子工業(yè)出版社,2009.
[2] 馬祖長,孫怡寧,梅濤.無線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào),2004,25(4):114-124.
[4] 陸客中,陳國良,馮禹洪.無線傳感器網(wǎng)絡(luò)最小中繼節(jié)點(diǎn)問題的近似算法[J].中國科學(xué):信息科學(xué),2010,40(11):1473-1482.
[6] 范高俊,金士堯.任意感知模型的傳感器網(wǎng)絡(luò)覆蓋度判定算法[J].計(jì)算機(jī)工程與科學(xué),2010,32(10):12-15.
[7] 陶丹,馬華東,劉亮.基于虛擬勢(shì)場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].軟件學(xué)報(bào),2007,18(5):1152-1163.
[8] 王偉,林鋒,周激流.無線傳感器網(wǎng)絡(luò)覆蓋問題的研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2010,27(1):32-35.
[9] 劉明,曹建農(nóng),鄭源,等.無線傳感器網(wǎng)絡(luò)多重覆蓋問題分析[J].軟件學(xué)報(bào),2007,18(1):127-136.
[12] 徐鵬飛,陳志剛,鄧曉衡.無線傳感器網(wǎng)絡(luò)中的分布式Voronoi覆蓋控制算法[J].通信學(xué)報(bào),2010,31(8):16-25.
[14] 高鐵杠,牛偉偉.一個(gè)基于節(jié)點(diǎn)覆蓋的簇頭選舉算法[J].計(jì)算機(jī)工程與科學(xué),2011,33(5):1-8.
[15] 張穎,郭鵬,周宗儀.移動(dòng)傳感器網(wǎng)絡(luò)覆蓋算法研究[J].計(jì)算機(jī)工程與科學(xué),2008,30(2):11-83.