張 蕾，錢 峰

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

1 引 言

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

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

2.1 覆蓋空洞

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

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

2.2 系統(tǒng)模型

假設(shè)無線傳感網(wǎng)絡(luò)系統(tǒng)由一個基站和多個傳感器節(jié)點構(gòu)成，基站負(fù)責(zé)收集來自所有傳感器節(jié)點發(fā)送來的數(shù)據(jù)，我們采用文獻(xiàn)[2，4]中的概念，假設(shè)節(jié)點間存在虛擬力，利用節(jié)點間的虛擬力可以保證移動節(jié)點間的合作。因為能量的限制，每個節(jié)點采用多跳的方式傳輸包，因為單跳傳輸可能要耗費更多的能量。傳感器的感知模型為圓盤模型。

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

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

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

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

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

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

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

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

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

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

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

3.2 節(jié)點的移動

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

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

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

3.3 增大感知半徑

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

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

4 仿真實驗

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

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

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

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

5 結(jié)束語

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

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

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

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