無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)算法綜述

田曉光

(河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475000)

0　引言

無線傳感器網(wǎng)絡(luò)（WirelessSensor Networks,WSN）對人類的生活和生產(chǎn)方式帶來巨大的變革，被認(rèn)為是21世紀(jì)最重要的技術(shù)之一。無線傳感器網(wǎng)絡(luò)由微機(jī)電系統(tǒng)的支持發(fā)展而來，是一種分布式傳感網(wǎng)絡(luò)，其具有大規(guī)模、動(dòng)態(tài)性、自組織、以數(shù)據(jù)為中心等特點(diǎn)，被廣泛應(yīng)用于軍事國防、醫(yī)療健康、智能家居等各個(gè)方面[1]。覆蓋質(zhì)量是無線傳感器網(wǎng)絡(luò)應(yīng)用中最重要的問題。評價(jià)傳感器網(wǎng)絡(luò)覆蓋質(zhì)量的一個(gè)重要指標(biāo)是節(jié)點(diǎn)覆蓋率[2]，如果節(jié)點(diǎn)覆蓋率過低會導(dǎo)致網(wǎng)絡(luò)中出現(xiàn)覆蓋空洞，造成數(shù)據(jù)監(jiān)測不準(zhǔn)確，更為嚴(yán)重的可能會導(dǎo)致對目標(biāo)區(qū)域監(jiān)測數(shù)據(jù)錯(cuò)誤。

無線傳感器網(wǎng)絡(luò)常被用于緊急救援、空間探索、軍事應(yīng)用等特殊環(huán)境。由于應(yīng)用環(huán)境特殊，傳感器節(jié)點(diǎn)常被隨機(jī)布撒于目標(biāo)區(qū)域，并通過自組織形成網(wǎng)絡(luò)。因此惡劣的環(huán)境、節(jié)點(diǎn)能量耗盡以及動(dòng)物入侵等因素的影響都有可能造成節(jié)點(diǎn)死亡，從而導(dǎo)致網(wǎng)絡(luò)中會出現(xiàn)某些區(qū)域未被任何節(jié)點(diǎn)感知，形成覆蓋空洞。若不及時(shí)修復(fù)就可能引起節(jié)點(diǎn)通訊受阻、網(wǎng)絡(luò)數(shù)據(jù)監(jiān)測不準(zhǔn)確等問題[3]，嚴(yán)重的還有可能引起網(wǎng)絡(luò)癱瘓。為了保證網(wǎng)絡(luò)正常運(yùn)行，需要對網(wǎng)絡(luò)中出現(xiàn)的覆蓋空洞采取合適的修復(fù)策略，以保證網(wǎng)絡(luò)覆蓋質(zhì)量，維持網(wǎng)絡(luò)正常運(yùn)行。

1　無線傳感器網(wǎng)絡(luò)特點(diǎn)

相比于一般網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)一般都應(yīng)用于人類無法到達(dá)甚至危險(xiǎn)的區(qū)域。無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的位置一般是固定不變的，只有極少數(shù)節(jié)點(diǎn)需要移動(dòng)。一般情況下通過隨機(jī)部署節(jié)點(diǎn)，利用節(jié)點(diǎn)自組織形成網(wǎng)絡(luò)。無線傳感器網(wǎng)絡(luò)還具有以下顯著特點(diǎn)。

⑴ 規(guī)模巨大。通常無線傳感網(wǎng)絡(luò)在運(yùn)行的時(shí)候?yàn)榱吮ＷC覆蓋質(zhì)量一般要求網(wǎng)絡(luò)部署時(shí)一定要保證網(wǎng)絡(luò)中節(jié)點(diǎn)具有一定的冗余，因此網(wǎng)絡(luò)在部署初期需要部署大量的傳感器節(jié)點(diǎn)，這樣既減少了網(wǎng)絡(luò)對單個(gè)傳感器節(jié)點(diǎn)的依賴，同時(shí)也保障了網(wǎng)絡(luò)的健壯性。雖然要求網(wǎng)絡(luò)中具有一定的節(jié)點(diǎn)冗余，但并不是冗余越大越好，因?yàn)楣?jié)點(diǎn)冗余過大不僅會造成監(jiān)測成本過高而且會導(dǎo)致后期維護(hù)成本增大。

⑵ 動(dòng)態(tài)性。動(dòng)態(tài)性是指在網(wǎng)絡(luò)中節(jié)點(diǎn)增加或去除都有可能改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。在無線傳感器網(wǎng)絡(luò)運(yùn)行的過程中，由于節(jié)點(diǎn)能量耗盡等其他因素的影響可能導(dǎo)致節(jié)點(diǎn)死亡造成網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)的改變。新增傳感器節(jié)點(diǎn)到網(wǎng)絡(luò)中同樣會導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化，因此網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)并不是一成不變的。

⑶ 自組織。在監(jiān)測區(qū)域內(nèi)，一般都是隨機(jī)部署大量傳感器節(jié)點(diǎn)，由于節(jié)點(diǎn)沒有其他網(wǎng)絡(luò)可依賴，其通過自組織形成網(wǎng)絡(luò)，并以多跳的方式傳送和轉(zhuǎn)發(fā)數(shù)據(jù)。

⑷ 以數(shù)據(jù)為中心。無線傳感器網(wǎng)絡(luò)以數(shù)據(jù)為導(dǎo)向，當(dāng)用戶指定監(jiān)測目標(biāo)，網(wǎng)絡(luò)會通過節(jié)點(diǎn)協(xié)作的方式監(jiān)測用戶感興趣的目標(biāo)屬性值，然后通過節(jié)點(diǎn)轉(zhuǎn)發(fā)將數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)，再由匯聚節(jié)點(diǎn)將數(shù)據(jù)通過衛(wèi)星等發(fā)送到計(jì)算機(jī)，經(jīng)計(jì)算機(jī)分析后將數(shù)據(jù)展現(xiàn)給用戶。

⑸ 相互協(xié)作執(zhí)行任務(wù)。無線傳感器從部署到執(zhí)行都是由多個(gè)傳感器節(jié)點(diǎn)共同參與完成的，在數(shù)據(jù)轉(zhuǎn)發(fā)階段傳感器節(jié)點(diǎn)需要互相通信，然后數(shù)據(jù)經(jīng)過多個(gè)傳感器節(jié)點(diǎn)以多跳的方式將數(shù)據(jù)轉(zhuǎn)發(fā)到匯聚節(jié)點(diǎn)。

2　覆蓋空洞修復(fù)算法分析

針對無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)問題國內(nèi)外眾多專家學(xué)者作了大量研究，也提出了很多開創(chuàng)性的算法思想，主要分為以下三類。

⑴ 基于幾何計(jì)算。核心思想是在保證網(wǎng)絡(luò)中節(jié)點(diǎn)冗余度的前提下，找出傳感器網(wǎng)絡(luò)中覆蓋空洞的最佳修復(fù)位置并修復(fù)。文獻(xiàn)[4-8]都是基于節(jié)點(diǎn)的位置在網(wǎng)絡(luò)中構(gòu)建幾何關(guān)系，確定空洞的最佳修復(fù)點(diǎn)，最終根據(jù)修復(fù)點(diǎn)的位置新增正常節(jié)點(diǎn)，達(dá)到修復(fù)覆蓋空洞的目的。文獻(xiàn)[4]在監(jiān)測區(qū)域內(nèi)隨機(jī)部署傳感器節(jié)點(diǎn)并在節(jié)點(diǎn)感知范圍相同的前提下，提出分析近似算法。計(jì)算隨機(jī)部署節(jié)點(diǎn)的感知覆蓋率，并表示具有覆蓋重疊區(qū)域的任何兩個(gè)傳感器節(jié)點(diǎn)的頂點(diǎn)之間存在的邊緣，主要是近似至少一個(gè)感測節(jié)點(diǎn)覆蓋的感測區(qū)域的比例，并給定二維泊松過程中每單位面積的預(yù)期節(jié)點(diǎn)數(shù)目，通過幾何圖形的性質(zhì)得到近似概率。該算法可以指導(dǎo)節(jié)點(diǎn)的部署，并在后期網(wǎng)絡(luò)出現(xiàn)覆蓋空洞時(shí)，指導(dǎo)節(jié)點(diǎn)修復(fù)。文獻(xiàn)[6]提出基于Voronoi覆蓋洞修復(fù)算法（EECHS），隨機(jī)部署的節(jié)點(diǎn)將監(jiān)測區(qū)域劃分為若干Voronoi，將劃分后Voronoi分割為若干三角形并結(jié)合相鄰節(jié)點(diǎn)生成的Voronoi找到覆蓋空洞的位置，然后連接節(jié)點(diǎn)與相鄰公共邊兩端點(diǎn)形成一個(gè)夾角，在夾角平分線上找到最優(yōu)空洞修復(fù)點(diǎn)。

雖然該算法可以較好的修復(fù)覆蓋空洞，但該算法復(fù)雜程度較高且修復(fù)后節(jié)點(diǎn)冗余較大。文獻(xiàn)[7]針對節(jié)點(diǎn)失效或死亡造成的網(wǎng)絡(luò)覆蓋空洞，提出在網(wǎng)絡(luò)部署時(shí)為每個(gè)傳感器節(jié)點(diǎn)設(shè)置一個(gè)能量閾值，當(dāng)網(wǎng)絡(luò)運(yùn)行過程中某個(gè)節(jié)點(diǎn)的能量低于設(shè)定的閾值時(shí)，該節(jié)點(diǎn)向匯聚節(jié)點(diǎn)發(fā)出信號，匯聚節(jié)點(diǎn)認(rèn)為發(fā)出信號節(jié)點(diǎn)的所有鄰居都為覆蓋空洞的邊界點(diǎn)，然后在低于能量閾值節(jié)點(diǎn)的覆蓋范圍內(nèi)找出冗余節(jié)點(diǎn)，該節(jié)點(diǎn)即為覆蓋空洞修復(fù)點(diǎn)。文獻(xiàn)[8]針對修復(fù)空洞問題提出最佳節(jié)點(diǎn)匹配算法（BFNP），該算法前提是在網(wǎng)絡(luò)部署初期部署部分惰性節(jié)點(diǎn)即未激活節(jié)點(diǎn)，當(dāng)某惰性節(jié)點(diǎn)符合修復(fù)空洞要求時(shí)激活該節(jié)點(diǎn)。當(dāng)網(wǎng)絡(luò)管理者發(fā)現(xiàn)網(wǎng)絡(luò)中由于節(jié)點(diǎn)死亡等原因造成節(jié)點(diǎn)失效時(shí)，檢測網(wǎng)絡(luò)中是否存在覆蓋空洞，如果存在覆蓋空洞則以覆蓋空洞邊緣為邊界，根據(jù)距離查詢空洞最近處未被激活的節(jié)點(diǎn)，激活該節(jié)點(diǎn)來達(dá)到修復(fù)覆蓋空洞的目的。

⑵ 移動(dòng)節(jié)點(diǎn)輔助。在傳感器網(wǎng)絡(luò)中全部使用移動(dòng)節(jié)點(diǎn)，實(shí)現(xiàn)節(jié)點(diǎn)以移動(dòng)最短的距離最大程度地修復(fù)覆蓋空洞。文獻(xiàn)[9-11]為了使節(jié)點(diǎn)移動(dòng)距離最小，全部采用移動(dòng)節(jié)點(diǎn)修復(fù)覆蓋空洞。這樣雖然能較好地控制節(jié)點(diǎn)移動(dòng)的距離，但網(wǎng)絡(luò)部署花費(fèi)過高、運(yùn)行代價(jià)過大。文獻(xiàn)[9]基于集群式的分布網(wǎng)絡(luò)提出虛擬力算法，網(wǎng)絡(luò)部署初期將傳感器節(jié)點(diǎn)隨機(jī)部署在監(jiān)測區(qū)域并根據(jù)虛擬力算法中的排斥力將節(jié)點(diǎn)均勻分開，以達(dá)到監(jiān)測區(qū)域被最大程度覆蓋的目的。當(dāng)網(wǎng)絡(luò)中出現(xiàn)覆蓋空洞時(shí)，根據(jù)算法中的吸引力和排斥力，控制節(jié)點(diǎn)移動(dòng)方向，將節(jié)點(diǎn)移動(dòng)至最佳修復(fù)位置。由于移動(dòng)節(jié)點(diǎn)的移動(dòng)距離有限，為了使移動(dòng)節(jié)點(diǎn)用最少的能量消耗去最大程度地修復(fù)覆蓋空洞，文獻(xiàn)[11]提出了基于移動(dòng)節(jié)點(diǎn)的動(dòng)態(tài)修復(fù)算法（DCM），該算法中網(wǎng)絡(luò)對節(jié)點(diǎn)的決策和移動(dòng)完全自治，不需要外界干預(yù)，網(wǎng)絡(luò)控制部分傳感器節(jié)點(diǎn)，以確定的位置移動(dòng)實(shí)現(xiàn)對網(wǎng)絡(luò)覆蓋最大化。

⑶ 靜動(dòng)節(jié)點(diǎn)混合部署。部署網(wǎng)絡(luò)時(shí)在靜態(tài)傳感器節(jié)點(diǎn)中加入一定量的移動(dòng)節(jié)點(diǎn)，當(dāng)需要修復(fù)網(wǎng)絡(luò)覆蓋空洞時(shí)，采用移動(dòng)節(jié)點(diǎn)修復(fù)覆蓋空洞并以最小的移動(dòng)代價(jià)修復(fù)網(wǎng)絡(luò)覆蓋空洞，也在一定程度上降低了后期網(wǎng)絡(luò)維護(hù)成本。文獻(xiàn)[12-14]都是基于移動(dòng)節(jié)點(diǎn)和混合節(jié)點(diǎn)組成的混合網(wǎng)絡(luò)修復(fù)覆蓋空洞。假設(shè)覆蓋空洞已經(jīng)存在且位置已知，文獻(xiàn)[12]提出基于移動(dòng)節(jié)點(diǎn)的覆蓋空洞修復(fù)算法（PATT），該算法將已知覆蓋空洞連接成多邊形，三個(gè)相鄰頂點(diǎn)將多邊形劃分為若干三角形，為保證新增節(jié)點(diǎn)最大程度地覆蓋三角形所在的空洞區(qū)域，在三角形邊的中垂線上計(jì)算出移動(dòng)節(jié)點(diǎn)的最佳修復(fù)位置，然后將修復(fù)后的節(jié)點(diǎn)加入到網(wǎng)絡(luò)中。依據(jù)此算法將覆蓋空洞采用三角形逐步貼片的方式使覆蓋空洞逐步變小，直至達(dá)到滿意的修復(fù)效果。但是如果完全修復(fù)覆蓋空洞，所消耗的移動(dòng)節(jié)點(diǎn)較多，網(wǎng)絡(luò)復(fù)雜度較高。文獻(xiàn)[13]基于文獻(xiàn)[12]提出基于距離的無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)算法，將已確定修復(fù)位置的移動(dòng)節(jié)點(diǎn)加入傳感器網(wǎng)絡(luò)中，然后將覆蓋空洞邊緣連接成多邊形，連接不相鄰多邊形的兩個(gè)頂點(diǎn)并找出多邊形中兩頂點(diǎn)連線最長的線段，說明該線段上存在修復(fù)覆蓋空洞的最佳位置，根據(jù)文獻(xiàn)[12]計(jì)算多邊形中三個(gè)相鄰頂點(diǎn)形成三角形邊的中垂線，計(jì)算該中垂線，求出多邊形中不相鄰兩頂點(diǎn)連線的最長線段的交點(diǎn)，該交點(diǎn)即為移動(dòng)節(jié)點(diǎn)最佳修復(fù)位置。該算法相較于文獻(xiàn)[12]減少了移動(dòng)節(jié)點(diǎn)的數(shù)目，在一定程度上使網(wǎng)絡(luò)復(fù)雜度降低。文獻(xiàn)[14]提出基于探測率的覆蓋空洞修復(fù)策略。依據(jù)節(jié)點(diǎn)探測模型，在監(jiān)測區(qū)域內(nèi)所有點(diǎn)的探測概率連續(xù)，探測過程中若探測概率達(dá)到最低值則說明該點(diǎn)是需要修復(fù)的位置，然后在該位置放置一虛擬節(jié)點(diǎn)，直到探測完成。探測完成后將移動(dòng)節(jié)點(diǎn)移到虛擬節(jié)點(diǎn)的位置即最佳修復(fù)點(diǎn)。該算法在保證網(wǎng)絡(luò)最大覆蓋的同時(shí)，也控制了移動(dòng)節(jié)點(diǎn)的移動(dòng)距離和節(jié)省了節(jié)點(diǎn)的資源。

3　結(jié)束語

無線傳感器網(wǎng)絡(luò)具有對外界環(huán)境感知能力，是由若干個(gè)傳感器節(jié)點(diǎn)自組織形成網(wǎng)絡(luò)，通過多跳的方式發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)。當(dāng)某個(gè)或某些傳感器節(jié)點(diǎn)因能量耗盡或其他因素造成節(jié)點(diǎn)死亡，可能會出現(xiàn)網(wǎng)絡(luò)覆蓋空洞從而導(dǎo)致網(wǎng)絡(luò)發(fā)送或轉(zhuǎn)發(fā)數(shù)據(jù)異常，因此當(dāng)網(wǎng)絡(luò)中出現(xiàn)覆蓋空洞時(shí)需進(jìn)行及時(shí)的修復(fù)。

文本介紹了無線傳感器網(wǎng)絡(luò)的特點(diǎn)以及出現(xiàn)覆蓋空洞的主要原因，并針對傳感器網(wǎng)絡(luò)空洞修復(fù)問題詳細(xì)介紹了幾類覆蓋空洞修復(fù)算法并作必要分析。文中算法大部分都采用MATLAB理想環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，未考慮算法在實(shí)際應(yīng)用中溫度、濕度等環(huán)境因素的影響，如何在考慮環(huán)境因素的條件下也能達(dá)到理想的修復(fù)效果也是未來研究的重點(diǎn)。

參考文獻(xiàn)(References):

[1]楊璽.面向?qū)崟r(shí)監(jiān)測的無線傳感器網(wǎng)絡(luò)[M].人民郵電出版社,2010.

[2]Wei An,Nan Qu,et al.Coverage hole problem under sensing topology in flat wirelesssensornetworks[J].WirelessCommunications andMobileComputing,2016.10:578-589

[3]Surjit S,Rajeev M S.Some Aspects of Coverage Awareness inWirelessSensorNetworks[J].Procedia Computer Science,2015.10:160-165

[4]Xiaoyun Li,David K.Coverage Properties of the Target Area in Wireless Sensor Networks[J].IEEE Transactions on Information Theory,2012.58(1):430-437

[5]LINJW,CHENYT.Improvingthecoverageof randomized schedul-ing in wireless sensor networks[J].IEEE Transactions on WirelessCommunications,2008.7(1):4807-4812

[6]趙春江,無華瑞,劉強(qiáng)等.基于Voronoi的無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J].通信學(xué)報(bào),2013.9:115-122

[7]包旭,巨永鋒.面向節(jié)點(diǎn)失效的無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)算法[J].計(jì)算機(jī)測量與控制,2011.19(6):1516-1518

[8]胥楚貴,鄧曉衡,鄒豪杰.無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)策略[J].傳感技術(shù)學(xué)報(bào),2010.23(2):256-259

[9]ZOU Y,CHAKRABARTY K.Sensor deployment and targetlocalization based on virtual forces[A].INFOCOM2003[C],2003.1293-1303

[10]WANG G,CAO G,PORTA T.Movement-assisted sensordeploy-ment[J].IEEETransaction onMobile Computing,2006.5(6):640-652

[11]SEKHA A,MANOJ B,MURTHY C.Dynamic coverage maintenancealgorithms for sensor networks with limited mobility[A].Proceedingsof the 3rd IEEE Int'l Conf on Pervasive Computing and Communica-tions[C].Kauai,Island,2005:51-60

[12]王良民,李菲,秦穎.基于移動(dòng)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)覆蓋洞修復(fù)方法[J].通信學(xué)報(bào),2011,32(4):1-8.

[13]韓春延.基于距離的無線傳感器網(wǎng)絡(luò)覆蓋洞修復(fù)算法[J].傳感器與微系統(tǒng),2013.32(4):91-94

[14]黃月,吳成東,張運(yùn)洲,等.基于移動(dòng)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2012.33(2):165-168