一種無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞的修復(fù)方法

張 蕾，錢 峰

（銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 銅陵244000）

1 引 言

由于嵌入式系統(tǒng)技術(shù)在近幾年快速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)（WSN）已成為最重要的研究領(lǐng)域之一。覆蓋率是無(wú)線傳感器網(wǎng)絡(luò)有效的重要度量指標(biāo)。根據(jù)Paikh等提出的理論：[1]傳感器網(wǎng)絡(luò)的覆蓋率為100%是不可能的，當(dāng)覆蓋率≧70%時(shí)，網(wǎng)絡(luò)才有效。針對(duì)如何保持一個(gè)良好的網(wǎng)絡(luò)覆蓋率，許多方法陸續(xù)被提出，其中不少方法需要移動(dòng)傳感器節(jié)點(diǎn)。文獻(xiàn)[2]中提出了VFA，方法中假設(shè)每個(gè)傳感器節(jié)點(diǎn)之間存在引力和斥力。如果任何兩個(gè)節(jié)點(diǎn)太近，斥力會(huì)將它們分開，反之，引力會(huì)拉近它們。VFA會(huì)使網(wǎng)絡(luò)拓?fù)涓拥木猓枰泄?jié)點(diǎn)知道其位置。由于方法中所有節(jié)點(diǎn)的感知半徑被假定為固定的，所以能量低的節(jié)點(diǎn)會(huì)快速耗盡其能量。EVFA[4]是VFA的分布式版本，這意味著剩余能量高的節(jié)點(diǎn)比低的節(jié)點(diǎn)有更大的感知半徑。能有效地利用網(wǎng)絡(luò)中的能量資源，延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。

2 問(wèn)題描述和系統(tǒng)模型

2.1 覆蓋空洞

當(dāng)傳感器網(wǎng)絡(luò)中某一節(jié)點(diǎn)因其本身能量耗盡或被破壞而失效，導(dǎo)致網(wǎng)絡(luò)原有的覆蓋區(qū)域缺失或者數(shù)據(jù)無(wú)法送達(dá)基站的現(xiàn)象，稱為 “覆蓋空洞”（coverage holes）現(xiàn)象。覆蓋空洞直接導(dǎo)致網(wǎng)絡(luò)覆蓋率下降，也會(huì)給一些應(yīng)用帶來(lái)很多問(wèn)題。如在醫(yī)療中，我們會(huì)使用實(shí)時(shí)傳感器來(lái)監(jiān)控病人身體的健康情況，如果傳感器失效，將失去病人的病情信息。

在諸如VFA的方法中，當(dāng)某個(gè)節(jié)點(diǎn)失效，基站會(huì)給網(wǎng)絡(luò)中每個(gè)活動(dòng)節(jié)點(diǎn)計(jì)算出一個(gè)新的位置，然后移動(dòng)傳感器節(jié)點(diǎn)修復(fù)覆蓋漏洞。因?yàn)橐苿?dòng)節(jié)點(diǎn)需要耗費(fèi)大量的能量，本文提出一個(gè)有效的方法來(lái)修補(bǔ)覆蓋空洞，是網(wǎng)絡(luò)保持一個(gè)良好的覆蓋率。

2.2 系統(tǒng)模型

假設(shè)無(wú)線傳感網(wǎng)絡(luò)系統(tǒng)由一個(gè)基站和多個(gè)傳感器節(jié)點(diǎn)構(gòu)成，基站負(fù)責(zé)收集來(lái)自所有傳感器節(jié)點(diǎn)發(fā)送來(lái)的數(shù)據(jù)，我們采用文獻(xiàn)[2，4]中的概念，假設(shè)節(jié)點(diǎn)間存在虛擬力，利用節(jié)點(diǎn)間的虛擬力可以保證移動(dòng)節(jié)點(diǎn)間的合作。因?yàn)槟芰康南拗?，每個(gè)節(jié)點(diǎn)采用多跳的方式傳輸包，因?yàn)閱翁鴤鬏斂赡芤馁M(fèi)更多的能量。傳感器的感知模型為圓盤模型。

本文的方案基于以下假設(shè)：

1.基站是固定的，所有傳感器節(jié)點(diǎn)均可移動(dòng)；

2.所有傳感器節(jié)點(diǎn)通過(guò)GPS或其他定位機(jī)制知道自己的位置信息；

3.所有傳感器節(jié)點(diǎn)都可調(diào)整自己的感知范圍和通信范圍。最大的感知半徑（RS）設(shè)為20m，最大的通信半徑（RC）設(shè)為40m。

圖1 節(jié)點(diǎn)g即將失效前

3 無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)

3.1 節(jié)點(diǎn)間信息的交換

為了減少修復(fù)覆蓋空洞所需移動(dòng)節(jié)點(diǎn)的數(shù)目，我們將每個(gè)傳感器節(jié)點(diǎn)的通信范圍劃分成3個(gè)區(qū)間：-π/6到 π/2之間的區(qū)域?yàn)閰^(qū)間 1，π/2到-5π/6之間的區(qū)域?yàn)閰^(qū)間2，-5π/6到-π/6之間的區(qū)域?yàn)閰^(qū)間3。然后對(duì)各區(qū)間分別計(jì)算其每個(gè)鄰居節(jié)點(diǎn)的ED_value。

其中，d為節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的距離。節(jié)點(diǎn)會(huì)選擇該區(qū)間鄰居節(jié)點(diǎn)中ED_value值最大的節(jié)點(diǎn)作為節(jié)點(diǎn)在這個(gè)區(qū)間的指定節(jié)點(diǎn)。

最初，每個(gè)節(jié)點(diǎn)在其通信半徑內(nèi)通過(guò)廣播hello消息包獲得鄰居節(jié)點(diǎn)的相關(guān)信息。一個(gè)Hello消息包含如下信息：節(jié)點(diǎn)id，節(jié)點(diǎn)位置，剩余能量和到基站的距離，鄰居節(jié)點(diǎn)及距其距離的列表，各區(qū)間所指定的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)通過(guò)hello消息包記錄來(lái)自鄰居節(jié)點(diǎn)的信息。節(jié)點(diǎn)間信息交換完成后，每個(gè)節(jié)點(diǎn)選擇距基站距離最小的鄰居節(jié)點(diǎn)作為其向基站傳輸數(shù)據(jù)包的下一跳。

當(dāng)hello包完成交換后，節(jié)點(diǎn)將知道其是否被其鄰居節(jié)點(diǎn)選擇為指定節(jié)點(diǎn)，這些信息被記錄在它們各自的表中。網(wǎng)絡(luò)完成部署后，每個(gè)節(jié)點(diǎn)開始工作并向基站傳送數(shù)據(jù)包。每個(gè)節(jié)點(diǎn)也將定期廣播hello包用于維護(hù)網(wǎng)絡(luò)拓?fù)洹?/p>

3.2 節(jié)點(diǎn)的移動(dòng)

當(dāng)某個(gè)傳感器節(jié)點(diǎn)能量即將耗盡，即向其3個(gè)區(qū)間所指定的節(jié)點(diǎn)發(fā)送cover_request消息通知它們覆蓋其工作區(qū)域。計(jì)算每個(gè)指定節(jié)點(diǎn)需要移動(dòng)的距離為：

dist(i)為該節(jié)點(diǎn)與鄰居節(jié)點(diǎn)i的距離，k為所有3個(gè)區(qū)間指定節(jié)點(diǎn)的數(shù)目（1≤k≤3）。average_energy為所有指定節(jié)點(diǎn)能量的均值。如果鄰居節(jié)點(diǎn)沒有定期收到來(lái)自于節(jié)點(diǎn)g的hello消息，它將假定節(jié)點(diǎn)g已經(jīng)死亡，將計(jì)算移動(dòng)距離并自動(dòng)移向目標(biāo)位置。

圖1中，經(jīng)過(guò)信息交換階段后，節(jié)點(diǎn)g分別選擇a，b，d作為其3個(gè)區(qū)間的指定節(jié)點(diǎn)，因?yàn)檫@3個(gè)節(jié)點(diǎn)分別在其所在區(qū)間的ED_value最大。如果節(jié)點(diǎn)g即將死亡，其向3個(gè)區(qū)間的指定節(jié)點(diǎn)發(fā)送coverrequest消息，這些節(jié)點(diǎn)收到消息后將各自計(jì)算移動(dòng)距離并移向目標(biāo)位置。

3.3 增大感知半徑

節(jié)點(diǎn)在收到cover_request消息并移動(dòng)到目標(biāo)位置后，它將擴(kuò)大其感知半徑以覆蓋死亡節(jié)點(diǎn)的范圍。新的感知半徑由初始感知半徑加上移動(dòng)距離，這樣使得原有的區(qū)域仍然能覆蓋。圖2顯示了節(jié)點(diǎn)g死亡后的拓?fù)?，?jié)點(diǎn)a，b和d移動(dòng)到一個(gè)新的位置并且擴(kuò)大他們的感知半徑。節(jié)點(diǎn)a，b和d再次通過(guò)廣播hello消息獲取其鄰居節(jié)點(diǎn)的相關(guān)信息。

圖2 節(jié)點(diǎn)g死亡后

4 仿真實(shí)驗(yàn)

利用JAVA編寫程序模擬我們的仿真環(huán)境，假定網(wǎng)絡(luò)100個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在大小為100m*100m的方形區(qū)域內(nèi)，所有的節(jié)點(diǎn)均可移動(dòng)，傳感器節(jié)點(diǎn)的初始能量在150J到3000J的范圍內(nèi)。離基站越近的節(jié)點(diǎn)擁有越多的能量，因?yàn)殡x基站越近其負(fù)載越大，依式（3）計(jì)算節(jié)點(diǎn)能量消耗。

α和 β是兩個(gè)調(diào)整參數(shù)。Rs為感知半徑，Rc為通信半徑，l為數(shù)據(jù)包大小，固定為512byte，實(shí)驗(yàn)中我們假設(shè)各節(jié)點(diǎn)接收能耗為一固定值0.205j，節(jié)點(diǎn)移動(dòng)每米消耗能量為27.96j。通過(guò)仿真實(shí)驗(yàn)，對(duì)本文提出的方法與VFA與EVFA在3個(gè)方面的性能進(jìn)行比較，分別是覆蓋率，剩余能量，連接節(jié)點(diǎn)的數(shù)目。

圖3顯示的3種方法的網(wǎng)絡(luò)覆蓋率。因?yàn)楦采w率在0到300個(gè)時(shí)間單位下沒有變化，我們僅顯示300個(gè)時(shí)間單位后的結(jié)果。當(dāng)節(jié)點(diǎn)開始失效，覆蓋率開始下降。在這里，我們只統(tǒng)計(jì)那些與基站仍然保持連接的節(jié)點(diǎn)數(shù)目?？梢钥吹?，當(dāng)VFA與EVFA得覆蓋率下降很快時(shí)，我們的方法仍然能保持好的覆蓋率。EVFA中的傳感器節(jié)點(diǎn)可根據(jù)其能量調(diào)整感知半徑，故其覆蓋率有時(shí)會(huì)小于VFA。

圖5 連接基站節(jié)點(diǎn)數(shù)量

5 結(jié)束語(yǔ)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)因能量耗盡或環(huán)境破壞而失效導(dǎo)致產(chǎn)生覆蓋空洞的現(xiàn)象，本文提出了1種解決辦法，基本思想是選擇最多3個(gè)ED_value值最大的節(jié)點(diǎn)，通過(guò)節(jié)點(diǎn)移動(dòng)并擴(kuò)大其感知半徑來(lái)修復(fù)覆蓋空洞。通過(guò)仿真實(shí)驗(yàn)表明了改方法能保證較好的網(wǎng)絡(luò)覆蓋率，延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。

圖4顯示網(wǎng)絡(luò)剩余能量。本文的方法比VFA與EVFA有更高的能量剩余，因?yàn)樵谶@兩種方案中，當(dāng)節(jié)點(diǎn)死亡時(shí)，所有的傳感器節(jié)點(diǎn)都可能移動(dòng)，這需要消耗大量的能量。而本文的方法最多只需要移動(dòng)3個(gè)節(jié)點(diǎn)。

圖5中可以看出本文的方法比VFA與EVFA能保持更多的節(jié)點(diǎn)連接，因?yàn)楣?jié)點(diǎn)花很多的能量在移動(dòng)上，所有死亡的更快。

[1]Parikh S，Vokkarane V M，Liudong X，Kasilingam D.Node-ReplacementPoliciestoMaintainThreshold-CoverageinWireless Sensor Networks[C].Proceedings of 16th International Conference on Computer Communications and Networks，2007:760-765.

[2]Zou Y，Chakrabarty K.Sensor deployment and target localization based on virtual forces[C].in Proc.IEEE INFOCOM Conference，2003:1293-1303.

[3]Zhang S，Liu Y，Pu J，Xiao Z，Zhang X.An Enhanced Coverage Control Protocol for Wireless Sensor Networks[C].Hawaii International Conference on System Sciences，2009:1-7.

[4]Younghwan Yoo，Agrawal D P，Mobile Sensor Relocation to Prolong the Lifetime of Wireless Sensor Networks[C].IEEE Vehicular Technology Conference，2008:193-197.