利用移動內(nèi)點來修復(fù)傳感器網(wǎng)絡(luò)空洞的算法

楊凱，劉全，張書奎,2，李瑾，翁東良

(1. 蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；2. 南京大學(xué) 計算機軟件新技術(shù)國家重點實驗室，江蘇 南京 210093)

1 引言

無線傳感器網(wǎng)絡(luò)是當(dāng)前研究的熱點，通過向目標(biāo)區(qū)域部署大量價格低廉、具有移動、感知和通信能力的傳感器節(jié)點構(gòu)成的無線傳感器網(wǎng)絡(luò)，可廣泛應(yīng)用于軍事、交通、醫(yī)療和救災(zāi)等領(lǐng)域。隨著電子技術(shù)的不斷發(fā)展，傳感器節(jié)點的功能不斷增強，體積不斷縮小，使得利用無線傳感網(wǎng)絡(luò)完成對某一區(qū)域的監(jiān)測成為可能。但是由于節(jié)點部署不均勻、環(huán)境外力影響或電量耗盡等因素而產(chǎn)生感知區(qū)域大型空洞，影響感知信息的精確性或降低通信的效率。因此，如何探測這些空洞區(qū)域，并對之進行修復(fù)成為傳感器網(wǎng)絡(luò)研究的重要內(nèi)容之一。

空洞修復(fù)算法包括2部分：空洞探測和空洞修補。在空洞探測方面，文獻(xiàn)[1]提出一種使用Voronoi圖來發(fā)現(xiàn)空洞。文獻(xiàn)[2]提出了 K覆蓋(K-coverage)算法，使用計算幾何中覆蓋弧的相關(guān)性質(zhì)進行空洞探測。在空洞探測中很少研究以地理信息作為輔助[3～6]。在空洞進行修復(fù)時，借助地理信息較多。文獻(xiàn)[7～9]中，作者利用網(wǎng)格對傳感器網(wǎng)絡(luò)進行劃分，部分文章使用地理信息進行空洞修復(fù)。文獻(xiàn)[10]使用節(jié)點之間洪泛信息方式對空洞進行探測，只需要節(jié)點之間的相對位置。文獻(xiàn)[3]使用移動節(jié)點獲得不精確位置信息。文獻(xiàn)[4～6]使用相互通信方式來確定節(jié)點位置，同樣需要地理信息、GPS等設(shè)備的支持，對于大規(guī)模傳感器網(wǎng)絡(luò)來說成本昂貴，并且空洞修復(fù)問題本身就是一個NP問題， 使用地理信息僅僅將解決問題的精度提高，仍不能得到最優(yōu)解。本文不借助地理信息，通過傳感器節(jié)點所具有的感知、通信功能來獲得不精確定位信息，利用這些不精確的地理信息確定空洞區(qū)域，并作為修復(fù)空洞的基礎(chǔ)。

針對空洞修復(fù)問題，可有多種方式。文獻(xiàn)[3]通過向傳感器網(wǎng)絡(luò)添加新的節(jié)點來完成空洞修復(fù)，并且提出了算法修復(fù)原則：1)加入新節(jié)點不會使空洞分裂；2)加入新節(jié)點至少能消除一段覆蓋弧。文獻(xiàn)[11]提出了一種移動空洞邊緣節(jié)點以減小空洞面積的算法VHR(vector based hole recovery)，該算法基于一種假設(shè)條件，即密集分布的無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點具有一定的移動能力，網(wǎng)絡(luò)初始化時分布節(jié)點所形成的空洞面積較小，也是非連續(xù)的，VHR算法借助GPS提供的地理信息確定空洞邊緣節(jié)點向空洞方向移動，在不改變已有覆蓋的前提下縮小空洞面積，但是該算法只能應(yīng)用于某些特定形狀的空洞而且需要借助GPS，能量消耗較大。文獻(xiàn)[5]提出一種使用Voronoi圖作為解決空洞覆蓋的方法，該方法重新布置傳感器網(wǎng)絡(luò)的節(jié)點，最大效率利用節(jié)點覆蓋，使用Voronoi圖對傳感器節(jié)點進行迭代計算，但該方法需要節(jié)點之間精確的地理信息和額外的GPS設(shè)備。

本文提出一種不需要地理信息的基于移動的空洞修復(fù)算法SOI(search optimistic inner)，以文獻(xiàn)[4,5,11]中節(jié)點可以具有一定的移動能力為理論支持，其中文獻(xiàn)[3]移動部分節(jié)點用于覆蓋空洞邊緣節(jié)點未覆蓋弧，文獻(xiàn)[3]移動空洞邊緣節(jié)點朝空洞方向移動，文獻(xiàn)[4]移動節(jié)點以填補失效節(jié)點的感知范圍。本文通過移動一些特殊節(jié)點，達(dá)到使感知范圍覆蓋整個目標(biāo)區(qū)域的目的。在空洞探測階段，使用文獻(xiàn)[2]中的K-coverage算法進行探測，若目標(biāo)區(qū)域為完全覆蓋，算法的后續(xù)部分不進行，否則進入空洞修復(fù)階段。SOI算法與文獻(xiàn)[11]相比，雖然修復(fù)的精度有所降低，但不需要增加GPS設(shè)備，實施代價較小。與文獻(xiàn)[3]相比，SOI算法不需要增加新節(jié)點，只需要移動部分節(jié)點就可以完成修復(fù)工作，盡管算法要求具有移動能力的節(jié)點提高了網(wǎng)絡(luò)構(gòu)建代價，但算法過程中移動節(jié)點數(shù)量和移動距離較小，其代價也是可以接受的。本文主要貢獻(xiàn)如下： 1)提出基于移動的空洞修復(fù)準(zhǔn)則，并引入相關(guān)定理；2)提出基于移動內(nèi)點的空洞修復(fù)算法SOI。該算法在沒有精確的地理信息時，尋找空洞邊緣節(jié)點的最佳位置，最終通過移動完成修復(fù)工作。

2 問題描述

2.1 前提假設(shè)

無線傳感器網(wǎng)絡(luò)中，每一個節(jié)點都有唯一標(biāo)識號(ID)，節(jié)點之間都可以正確地標(biāo)識自身。每個節(jié)點都可以感知某一區(qū)域并與相鄰節(jié)點進行通信，假定其感知和通信范圍都為圓形，其感知圓與通信圓的半徑分別為SR與TR。假定TR ≥ 2 ×SR (相關(guān)證明由Bejeranp Y完成)，這樣網(wǎng)絡(luò)的連通問題就等價為覆蓋問題，一個K覆蓋的網(wǎng)絡(luò)一定是連通的。另外，傳感器網(wǎng)絡(luò)中傳感器節(jié)點沒有精確的地理信息，邊界區(qū)域的節(jié)點都能夠正確標(biāo)識自身，不會將監(jiān)測區(qū)域的邊界誤判為空洞。同時，由于節(jié)點是隨機分布，假定3個節(jié)點的感知圓相交于同一點的概率為0，并且沒有任意2個傳感器節(jié)點位于同一個位置。

目前，大多數(shù)空洞修復(fù)的研究都是以網(wǎng)絡(luò)連通為前提，且覆蓋空洞是閉合的。本文同樣是基于網(wǎng)絡(luò)連通的，但對于空洞是否閉合沒有特定的要求。本文假定每個節(jié)點都具有一定的移動能力，在目標(biāo)區(qū)域隨機分布節(jié)點后，通過節(jié)點的有限移動，每個節(jié)點可以獲得其鄰居節(jié)點的位置信息。以這些信息為基礎(chǔ)，運行空洞探測算法可以有效探測出覆蓋空洞位置與大小。由于研究的復(fù)雜性，本文只關(guān)注覆蓋空洞修復(fù)問題，空洞探測方面使用文獻(xiàn)[2]中K覆蓋算法來探測空洞大小和位置。

2.2 相關(guān)術(shù)語

定義1 空洞邊緣交點。如果2個節(jié)點都是空洞邊緣節(jié)點，且它們之間互為鄰居節(jié)點，那么這2個節(jié)點感知范圍相交，處于空洞相交區(qū)域的節(jié)點為空洞邊緣交點。在圖1中P1為A節(jié)點與B節(jié)點的空洞交點，P2為B節(jié)點和C節(jié)點的空洞交點。

圖1 空洞示意

定義2 內(nèi)點。如果若干個節(jié)點都是鄰居節(jié)點，那么一個傳感器感知范圍內(nèi)的一點(不在該傳感器感知范圍的邊緣上)是其他2個傳感器感知區(qū)域的交點，則該交點稱為內(nèi)點。幾何學(xué)上的定義是：3個圓U、V、W其半徑為r，若P∈(Cv∩Cw)，P滿足P∈Du，d( p, u)＜r則P為圓U內(nèi)點。在圖2中P3是傳感器節(jié)點C和B的感知區(qū)域的交點，并且P3處于傳感器A的感知范圍內(nèi)。

圖2 空洞邊緣節(jié)點，鄰居節(jié)點示意

定義3 空洞內(nèi)點。根據(jù)內(nèi)點定義，在特殊情況下如果A為空洞邊緣節(jié)點，那么P3為空洞內(nèi)點。

定義4 空洞邊緣弧。相鄰的空洞邊緣交點通過圓弧相連，節(jié)點感知區(qū)域邊緣上連接空洞邊緣交點的圓弧稱為空洞邊緣弧。

定義5 空洞邊緣鄰居。在傳感器網(wǎng)絡(luò)中如果有2個節(jié)點互為鄰居節(jié)點，并且這2個節(jié)點為空洞邊緣節(jié)點，則稱這2個節(jié)點互為空洞邊緣鄰居。

在本文中有如表1所示的符號。

表1 相關(guān)符號定義

圖3 覆蓋弧

對于覆蓋弧，有如下性質(zhì)。

性質(zhì)1 覆蓋弧Su,v與Su,w相交，當(dāng)且僅當(dāng)μu,w+μu,v＞2×∠v, u, w。

性質(zhì)2 覆蓋弧Su,w?Su,v，當(dāng)且僅當(dāng)μu,w≥μu,v+2×∠v, u, w。

性質(zhì)3 覆蓋弧Su,w∩Su,v≠NULL ，且Su,w?Su,v，Su,v?Su,w。

性質(zhì)4 覆蓋弧Su,x?Su,w∩Su,v，當(dāng)且僅當(dāng)滿足以下條件：

1) ∠v,u,x+∠x,u,w=∠v,u,w；

2) μu,x/2＜μu,v/2+∠v,u,x；

3) μu,x/2＜μu,w/2+∠w,u,x。

2.3 問題描述及相關(guān)性質(zhì)

在空洞修復(fù)過程中，本文采用移動空洞邊緣節(jié)點的方式進行空洞修復(fù)。通過不斷移動空洞邊緣節(jié)點減少網(wǎng)絡(luò)中感知圓的重疊面積，擴大網(wǎng)絡(luò)覆蓋面積，最終達(dá)到消除覆蓋空洞的目標(biāo)。在空洞修復(fù)過程中，引入以下準(zhǔn)則：1)移動節(jié)點不會使其鄰居節(jié)點產(chǎn)生新的未覆蓋??；2)移動節(jié)點必須減少覆蓋空洞的面積。由于節(jié)點是隨機布置的，每個節(jié)點的感知圓與周圍鄰居節(jié)點的感知圓不規(guī)則相交，產(chǎn)生若干重疊的感知區(qū)域，在節(jié)點移動的過程中，需要遵循上面提出的2個準(zhǔn)則。

利用移動節(jié)點來修復(fù)空洞，其本質(zhì)是移動空洞邊緣節(jié)點至某一位置使該節(jié)點的感知圓恰好經(jīng)過內(nèi)點，即節(jié)點的感知圓和其2個鄰居節(jié)點相交于一點。這樣節(jié)點間的冗余面積減小，節(jié)點覆蓋面積增大。然而，由于節(jié)點分布的隨機性，一個節(jié)點必然含有多個內(nèi)點，需要從這些內(nèi)點之中選擇出一個作為移動后3個感知圓的交點。

簡單網(wǎng)絡(luò)模型中空洞邊緣節(jié)點S的內(nèi)點是有限的，從中選擇一個距離S最遠(yuǎn)的內(nèi)點，移動S，使S與其鄰居節(jié)點相交于該內(nèi)點即可完成空洞修復(fù)。但是由于傳感器節(jié)點是隨機分布的，S中內(nèi)點位置非常復(fù)雜，不能簡單的從中選擇出一個距離S最遠(yuǎn)的內(nèi)點。如圖4所示，若S為空洞邊緣節(jié)點，A、B、C都是S的鄰居，由2.2節(jié)定義可知P1、P2、P3、P4為S的內(nèi)點，按照現(xiàn)有的方法，選擇距S最遠(yuǎn)的內(nèi)點P1作為移動的內(nèi)點，那么移動之后，雖然S與A、B、C的重疊面積減小了，但沒有減至最小，S可以再次移動。但是再次移動的計算過程極其繁瑣，而且移動之前必須使用空洞探測算法確定新產(chǎn)生的空洞。這里，關(guān)于內(nèi)點可以有以下所述性質(zhì)。

圖4 復(fù)雜網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)

引理1 如果一個圓的某個內(nèi)點也是其他圓的內(nèi)點，那么該內(nèi)點的覆蓋度大于同一圓的其他內(nèi)點。

證明 假設(shè)有4個圓u、v、w、x，其圓周為Cu、Cv、Cw、Cx，并令SR=R，從條件可得?p∈cv∩cw，dp,v=dp,w=R 且p∈cu∩cx，p為內(nèi)點且q∈(Du∩Dv∩Dw∩Dx)。根據(jù)題設(shè)?q∈cv∩cw且滿足q∈Du，則q為內(nèi)點且滿足q∈(Du∩Dv∩Dw)。若根據(jù)本文算法移動圓u，則內(nèi)點p永遠(yuǎn)會處于某個圓的范圍中，其覆蓋度一定大于其他內(nèi)點，而q不滿足q∈(Du∩Dv∩Dw)。證畢。

根據(jù)引理1，空洞邊緣節(jié)點中選擇被其他節(jié)點覆蓋的內(nèi)點作為移動的定位點，并不能使空洞邊緣節(jié)點與其鄰居節(jié)點的重疊面積最小(因為移動后的內(nèi)點的覆蓋度仍大于其他內(nèi)點)。因此在選擇內(nèi)點時應(yīng)該排除這一類特殊的內(nèi)點，這里使用覆蓋弧的性質(zhì)來解決這一問題，并且本文把這一類空洞邊緣節(jié)點的內(nèi)點并且也是其鄰居節(jié)點的內(nèi)點稱為覆蓋內(nèi)點。如圖4所示，P1、P2、P4都是覆蓋內(nèi)點，以其中之一作為移動的定位點都會使移動算法修復(fù)空洞失敗。

定理1 若圓v、w 在圓u形成的覆蓋弧滿足Su,w?Su,v，那么圓w產(chǎn)生的內(nèi)點p滿足p?Dv。

證明 3個圓u、v、w的覆蓋范圍為Du、Dv、Dw，所形成的覆蓋弧為Su,v、Su,w且滿足Su,w?Su,v。假設(shè)p1、p2∈Du∩Dv且du,p1=du,p2=R 。q1、q2∈Du∩Dw且du,q1=du,q2=R ，由Su,w?Su,v可知在Du上，故可得(Du∩Dw)?(Du∩Dv)，那么由Du∩Dw所產(chǎn)生的內(nèi)點p均有p∈Du覆蓋，其產(chǎn)生的內(nèi)點也為覆蓋內(nèi)點即存在內(nèi)點p滿足p?Dv。證畢。

根據(jù)定理1，在進行內(nèi)點選擇過程中節(jié)點會產(chǎn)生如圖5(c)的情況，那么此時應(yīng)具體去考慮此種狀況。如果Su,x?Su,w∪Su,v，v、w、x 3個感知圓相交，x產(chǎn)生的內(nèi)點可能會被v和w所覆蓋，那么要進行下一步判斷，這里對x分為如下2種情況。

圖5 覆蓋弧性質(zhì)

1) 如果Sx,w∩Sx,v=NULL，那么x所產(chǎn)生的內(nèi)點均被覆蓋；

2) 如果Sx,w∩Sx,v≠NULL，那么x不是覆蓋內(nèi)點。

定理2 在圓u中若存在Su,x?Su,w∩Su,v，且Sx,w∩Sx,v≠NULL ，則x在u中的內(nèi)點均被覆蓋。

證明 由覆蓋弧Su,v、Su,w、Su,x可得cu∩cv產(chǎn)生的弧為，cu∩cw產(chǎn)生的弧為，cu∩cx產(chǎn)生的弧為，由Su,x?Su,w∪Su,v可知。由Sx,w∩Sx,v≠NULL ，可知Sx,w與Sx,v覆蓋弧是連續(xù)的，并且則 ?p∈(cu∩cx)均有p∈(Dw∪Dv)，根據(jù)定理1的結(jié)論(cu∩cx)?(cu∩cw)∪(cu∩cv)，所以x產(chǎn)生的內(nèi)點p有p∈(Dw∪Dv)。證畢。

結(jié)合引理1、定理1和定理2可以逐步剔除已經(jīng)被覆蓋的內(nèi)點，最后從剩下的內(nèi)點中選擇出一個距離空洞節(jié)點最遠(yuǎn)的作為最佳內(nèi)點。本文提出了一個尋找最佳內(nèi)點的算法（SOI）。

3 算法描述

本文提出了一種利用移動內(nèi)點來修復(fù)空洞的算法，其中包括節(jié)點移動方向和內(nèi)點選擇算法。由于算法沒有精確的地理信息，需要使用一種特殊的方式來確定節(jié)點移動方向。每一個節(jié)點在確定自己是空洞邊緣節(jié)點時都會自動運行該算法，通過計算移動方向和移動距離將自身移動到新的位置。

3.1 移動方向

本文通過移動空洞邊緣節(jié)點修復(fù)空洞，首先應(yīng)確定空洞邊緣節(jié)點的移動方向，這里節(jié)點選擇朝未被覆蓋的弧方向移動，能夠減少空洞的面積。如圖6(a)所示節(jié)點S為空洞邊緣節(jié)點，P1、P2為空洞邊緣交點，弧為節(jié)點S的未覆蓋弧，做向量、則+得到向量，由圖6(a)可知指向未覆蓋弧中點且朝向空洞的方向，沿著移動無線傳感器節(jié)點S必然會減小空洞的面積，使得S與其鄰居A、B的傳感圓的重疊面積縮小。需要指出的是，在確定移動方向時，可能存在例外情況，如圖6(b)所示，通過計算空洞邊緣節(jié)點S與鄰居所形成的空洞邊緣交點、的向量和，得到一個向量，但不能把作為節(jié)點移動的方向，因為沿移動只能加大空洞邊緣節(jié)點與其鄰居節(jié)點的重疊面積，相反地應(yīng)采用為節(jié)點移動方向。

圖6 節(jié)點移動方向的確定

移動節(jié)點的目的是減小空洞面積，從移動的本身來看移動增大了空洞邊緣節(jié)點未覆蓋的弧長，最終會使得盡可能多的節(jié)點感知圓相交于同一點。本文2.1節(jié)中提到3個傳感器節(jié)點的感知圓相交于同一點的概率為0，并且任意2個傳感器節(jié)點都不會位于同一個位置，本文算法的本質(zhì)是移動空洞邊緣節(jié)點使節(jié)點與其鄰居節(jié)點相交于同一點。由于無線傳感器網(wǎng)絡(luò)中節(jié)點是隨機分布的，沒有精確的地理信息，故使用向量是不現(xiàn)實的。本文提出一個不精確的移動軌跡作為空洞邊緣節(jié)點的移動方向。

如圖7所示，S為空洞邊緣節(jié)點，A、B為S鄰居節(jié)點，且A、B恰為S空洞邊緣節(jié)點（在SOI算法中A、B為覆蓋弧序列中，2個相鄰但覆蓋弧不相交的節(jié)點），做AB的垂線經(jīng)過S且指向S的向量，根據(jù)2.3節(jié)已知A、B的位置A（ds,a,qa）、B（ds,b,qb） 計算出S的移動軌跡為：

1) 如果cos∠SAB＞0，移動軌跡σs=-θA+∠SAB+2k×π；

2) 如果cos∠SAB＜0，移動軌跡σs=-θA-∠SAB+2k ×π，且

圖7 空洞邊緣節(jié)點移動軌跡

3.2 SOI算法與計算移動距離

在這一部分中，算法從空洞邊緣節(jié)點內(nèi)部選擇一個內(nèi)點作為移動的終點，并計算節(jié)點移動的距離。根據(jù)2.3節(jié)中內(nèi)點性質(zhì)提出了一個選擇最佳內(nèi)點的算法（SOI算法）。

當(dāng)一個節(jié)點u被空洞探測算法計算為空洞邊緣節(jié)點時，運行下述算法(SR=r)。

Step1 掃描u周圍鄰居節(jié)點構(gòu)造一個分割弧隊列Qall，Qall中成員為逆時針遍歷的鄰居節(jié)點。

Step2 遍歷Qall，刪除每一個x當(dāng)且僅當(dāng)覆蓋弧Su,x?Su,v(v、x為隊列中任意鄰居節(jié)點標(biāo)記)。

Step3 遍歷Qall，刪除每一個x當(dāng)且僅當(dāng)覆蓋弧Su,x?Su,w∪Su,v且Sx,v∩Sx,u≠NULL，這樣得到一個隊列。

Step5 從Qn中取相鄰2個節(jié)點n1、n2令ni=n1，nj=n2。

Step6 若覆蓋弧Su,i∩Su,j=NULL 保存i和j，此時i和j為空洞鄰居節(jié)點，計算節(jié)點移動的方向σm。ni=nj，nj=nj+1，轉(zhuǎn)向Step6，否則轉(zhuǎn)向Step7。

Step7 計算ni、nj感知圓產(chǎn)生的交點o距u的距離，并選擇其中較小的值Li,j保存，令ni=nj，nj=nj+1，如果nj=n1轉(zhuǎn)向Step8，否則轉(zhuǎn)向Step7。

Step8 選擇出max(Li,j)，并保留產(chǎn)生該交點的2個無線感知器節(jié)點ni，nj的相關(guān)信息。

Step9 以max(Li,j)，σm為條件根據(jù)圖8所示，計算出節(jié)點在移動方向上移動的距離L。

圖8 計算內(nèi)點距空洞邊緣節(jié)點距離，s為空洞邊緣節(jié)點，u和v為隊列中滿足條件節(jié)點

在上述算法中，逆時針掃描每一個空洞邊緣節(jié)點的鄰居節(jié)點，根據(jù)內(nèi)點性質(zhì)，剔除產(chǎn)生覆蓋內(nèi)點的鄰居節(jié)點，剩下的內(nèi)點組成一個隊列Qn。計算Qn中節(jié)點產(chǎn)生的內(nèi)點，選擇其中距離空洞邊緣節(jié)點最遠(yuǎn)的內(nèi)點為最佳內(nèi)點。這樣算法能同時滿足空洞修復(fù)的2個準(zhǔn)則，不會產(chǎn)生新的空洞，也能夠使節(jié)點冗余面積最小。接下來是算法計算節(jié)點移動距離。

計算內(nèi)點與空洞邊緣節(jié)點距離的算法實現(xiàn)：

u和v滿足Ss,u∩Ss,v≠NULL ，則u和v的交點為s的內(nèi)點，設(shè)其交點為o。ds,u、ds,v、du,v已知，且du,o=dv,o=r 。由三角法則得

由于

由式(1)～式(4)可以求出

ds,o有2個值取ds,o＜r即可，Lu,v=ds,o，最后取max(Li,j)，并求出o的相對于s的位置＜ds,o,θs,o＞這即是所求的最佳內(nèi)點。確定最佳內(nèi)點后，進行算法最后一步，移動空洞邊緣節(jié)點至最佳位置。

圖9 移動空洞邊緣節(jié)點S至S '

算法表明，節(jié)點的移動限制在1跳的距離內(nèi)。而且節(jié)點的移動沒有影響現(xiàn)存覆蓋，沒有對初始時節(jié)點的覆蓋度產(chǎn)生影響，所以算法并未對原始覆蓋產(chǎn)生影響。設(shè)空洞邊緣節(jié)點的數(shù)量為n，則算法時間復(fù)雜度為O( n2)，在修復(fù)過程中空洞邊緣節(jié)點按ID順序依次進行修復(fù)，能夠快速收斂。盡管在修復(fù)過程中空洞邊緣節(jié)點不可能全部移動到最佳位置，但經(jīng)實驗證明在密集網(wǎng)絡(luò)中，它仍然能夠到達(dá)1覆蓋。

4 仿真實驗

本節(jié)討論SOI空洞修復(fù)算法的性能，使用節(jié)點移動的總距離和修復(fù)空洞所占面積的百分比來評估算法性能，同時與文獻(xiàn)[3]中VHR算法進行比較。VHR算法采用移動節(jié)點的方式，將空洞邊緣節(jié)點沿著向量方向移動一定距離，逐漸縮小覆蓋空洞面積。其中向量由邊界缺口點來決定，只有缺口點向量的角度小于π時節(jié)點才能移動，而節(jié)點移動距離由鄰居節(jié)點和協(xié)作節(jié)點共同決定。該算法能夠保證在不會破壞已有覆蓋的條件下，盡可能縮小空洞面積。

4.1 仿真實驗設(shè)置

仿真實驗采用C++完成算法，算法在一個400×400的矩形區(qū)域中隨機部署n個傳感器節(jié)點，節(jié)點的感知半徑為20(其傳輸半徑為40)，節(jié)點的個數(shù)隨實驗的進行不斷變化。為了簡化問題，仿真實驗并沒有實現(xiàn)節(jié)點通信的下層MAC協(xié)議，也沒有關(guān)注節(jié)點在通信和移動過程中所產(chǎn)生的能量消耗，而是通過空洞修復(fù)算法中節(jié)點移動的總距離來衡量算法過程中的能量消耗。在算法過程中，首先對目標(biāo)區(qū)域隨機分布的節(jié)點進行空洞探測（使用Bejeranp Y的K-corerage算法），如果節(jié)點為空洞邊緣節(jié)點則保存其ID，否則檢測下一個節(jié)點?？斩刺綔y結(jié)束后，空洞邊緣節(jié)點按照 ID順序依次進行修復(fù)，待所有節(jié)點執(zhí)行完畢后算法終止。

在SOI算法中，空洞邊緣節(jié)點按ID順序進行移動，節(jié)點的移動只會對周圍空洞鄰居節(jié)點的修復(fù)產(chǎn)生影響并不會擴大到整個網(wǎng)絡(luò)，并且在節(jié)點密集分布的網(wǎng)絡(luò)中有限幾個節(jié)點的移動會完全修復(fù)空洞，使得其他空洞節(jié)點運行SOI算法時在計算移動軌跡時自動退出，并不影響算法有效性。

4.2 實驗結(jié)果分析

為了說明空洞修復(fù)算法中節(jié)點的移動方向，標(biāo)記出節(jié)點的移動方向。圖10(a)中顯示的是n=30時，節(jié)點隨機分布所形成的拓?fù)浣Y(jié)構(gòu)。為了使實驗更為完整，設(shè)定傳感區(qū)域邊緣的節(jié)點不參與空洞修復(fù)，以避免移動區(qū)域邊緣節(jié)點產(chǎn)生新的空洞。圖 10(b)是運行修復(fù)算法時，每個空洞邊緣節(jié)點的移動方向，圖中箭頭為修復(fù)算法中節(jié)點的移動軌跡。由于SOI修復(fù)算法中沒有精確的地理信息支持，只能通過2個空洞邊緣鄰居與空洞邊緣節(jié)點共同確定節(jié)點移動方向，這種移動方向是不精確的，但后續(xù)實驗表明，在節(jié)點密集分布的網(wǎng)絡(luò)中這種粗糙的移動可以獲得不錯的效果。

如圖11所示，本文分析了在目標(biāo)區(qū)域中分布不同數(shù)量的節(jié)點時，運行空洞修復(fù)算法前后覆蓋區(qū)域占目標(biāo)區(qū)域的百分比。初始時，目標(biāo)區(qū)域的覆蓋率隨著分布節(jié)點數(shù)量的增多不斷提高。移動前后目標(biāo)區(qū)域覆蓋比率的變化表明修復(fù)后覆蓋區(qū)域明顯擴大，并且隨著節(jié)點數(shù)量增多傳感區(qū)域的覆蓋面積增大，空洞面積相應(yīng)減小，使用SOI修復(fù)算法的效果也越好。在節(jié)點數(shù)量較少時可移動的節(jié)點數(shù)量很少，導(dǎo)致移動后空洞修復(fù)效果不明顯。隨著節(jié)點數(shù)量增加，可移動節(jié)點也增多，使用移動修復(fù)的效果也更明顯。與 VHR算法相比，在密集網(wǎng)絡(luò)中 SOI算法的性能稍好于VHR算法，并且SOI算法不需要精確地理信息，算法適應(yīng)性要好于VHR算法。

圖11 節(jié)點移動前后覆蓋比率

圖12顯示了無線傳感器節(jié)點數(shù)量與空洞面積之間的關(guān)系。可以看出，節(jié)點數(shù)量越大，產(chǎn)生空洞的面積越小。在實驗過程中，因為節(jié)點是隨機分布的，所以在節(jié)點數(shù)量相同的條件下，每次實驗中所產(chǎn)生的空洞也有差異，這里的空洞是 10次實驗的結(jié)果取平均值。該圖表明，在實際應(yīng)用中，有限區(qū)域內(nèi)密集布置的無線傳感器網(wǎng)絡(luò)所形成的空洞面積比率很小，這樣空洞修復(fù)算法僅僅只需要移動有限節(jié)點就可以完成對目標(biāo)區(qū)域的完全覆蓋，可以確保無線傳感器網(wǎng)絡(luò)中節(jié)點能量不會因為移動消耗大量的能量。

圖12 無線傳感器節(jié)點數(shù)量與空洞面積的關(guān)系

本文提出的修復(fù)算法是基于節(jié)點移動，所以空洞修復(fù)算法中節(jié)點移動總距離是考查修復(fù)算法的重要條件。在無線傳感器網(wǎng)絡(luò)中，節(jié)點的能量是有限的，移動會消耗傳感器節(jié)點大量能量，一旦網(wǎng)絡(luò)中的節(jié)點因為移動消耗過多的能量，必然會產(chǎn)生新的空洞。因此，為了延長節(jié)點在無線網(wǎng)絡(luò)中的生存時間，平衡網(wǎng)絡(luò)中的負(fù)載，算法需要盡可能地減少移動所產(chǎn)生的能量消耗即減少移動式空洞修復(fù)算法中節(jié)點移動的距離。由于在空洞修復(fù)算法中，不同的修復(fù)算法之間因為修復(fù)的方式不同，很難比較各種方法的優(yōu)越性，因此本文中只與同為移動式的VHR算法進行比較。圖13中詳細(xì)描述了在節(jié)點數(shù)目不同的情況下，SOI修復(fù)算法移動傳感器節(jié)點的總距離與 VHR算法移動距離之間的比較。從圖中可以看到，節(jié)點數(shù)目越大所需要移動的距離越小，因此上文中提到的修復(fù)算法的有效性得到證實。

圖13 SOI算法與VHR算法移動距離對比

如圖13所示，節(jié)點數(shù)量較少時，SOI移動距離要大于VHR，這是因為在節(jié)點稀疏分布的網(wǎng)絡(luò)中，與 VHR算法相比，SOI算法中每一個非邊界的空洞邊緣節(jié)點都參與移動，并且SOI算法不考慮移動節(jié)點與1跳范圍內(nèi)的協(xié)作節(jié)點之間的關(guān)系，也沒有使用向量來精確表示移動方向，大多數(shù)節(jié)點的移動距離比VHR算法大。但是當(dāng)節(jié)點數(shù)量超過800時SOI修復(fù)算法移動的距離要小于VHR算法。這是因為在密集網(wǎng)絡(luò)中，SOI修復(fù)算法的特點是盡可能地去移動節(jié)點，減少無線傳感器節(jié)點之間重疊面積，而 VHR算法中節(jié)點更多地考慮保持與協(xié)作節(jié)點之間的距離和精確地移動，所以在這種情況下，SOI算法僅僅需要移動幾個節(jié)點就可以完成空洞修復(fù)任務(wù)，此時SOI算法移動節(jié)點的距離要小于VHR算法。

如圖14所示，在修復(fù)空洞時，與VHR算法相比SOI算法需要移動更多的節(jié)點。在VHR算法中，只有向量夾角為銳角的節(jié)點才能移動，而SOI算法大部分非邊界區(qū)域的空洞邊緣節(jié)點都可以移動，所以 SOI算法中可移動的節(jié)點數(shù)量要明顯大于 VHR算法。盡管如此，由于SOI算法所選擇的移動方向是粗糙的，在稀疏網(wǎng)絡(luò)中，SOI算法的移動距離要明顯大于 VHR算法?？斩葱迯?fù)過程中，移動節(jié)點需要消耗一定能量，但如圖14所示SOI算法移動節(jié)點的數(shù)量遠(yuǎn)小于節(jié)點總數(shù)量，移動總距離也較小，并且網(wǎng)絡(luò)中的每個節(jié)點不需要額外的 GPS設(shè)備，故該算法雖然消耗一定能量，但從整體上來說也是可以接受的。

圖14 SOI算法和VHR算法移動節(jié)點數(shù)量對比

本文算法是基于二維空間的，也可以將其擴展到三維空間，這樣計算內(nèi)點就擴展為計算空間球體相交的弧切面，SOI算法的目標(biāo)也可以演變?yōu)樽尪鄠€傳感器節(jié)點的弧切面相交即可。這里覆蓋內(nèi)點的概念也可以擴展到空間中的面，進一步討論三維空間中的覆蓋問題。

5 結(jié)束語

覆蓋問題是無線傳感器網(wǎng)絡(luò)的重要研究問題。在前期的研究工作中，主要依靠在無線傳感器網(wǎng)絡(luò)中布置大量冗余節(jié)點來解決完全覆蓋的問題。本文針對傳感器網(wǎng)絡(luò)覆蓋問題，證明了網(wǎng)絡(luò)覆蓋中幾個基于覆蓋性質(zhì)的定理?；谶@些定理，以及在沒有地理信息的支持下，針對密集分布的無線傳感器網(wǎng)絡(luò)中空洞修復(fù)問題，提出了空洞修復(fù)算法SOI。該算法計算出空洞邊緣節(jié)點的移動方向和空洞邊緣節(jié)點移動的最佳位置，通過移動減小節(jié)點感知圓之間冗余面積擴大節(jié)點的覆蓋面積，以此實現(xiàn)傳感器網(wǎng)絡(luò)中的空洞修復(fù)。實驗表明，該算法在節(jié)點密集分布時移動所有的空洞邊緣節(jié)點以較小的移動距離獲得良好的空洞修復(fù)性能。本文的下一步工作重點是在沒有地理信息系統(tǒng)的支持下提高修復(fù)稀疏網(wǎng)絡(luò)的精確度。

[1] WANG G, CAO G, LA P T. On solving coverage problems in a wireless sensor network using voronoi diagrams[A]. Proceedings of the International Workshop on Internet and Network Economics(WINE)[C].HongKong, 2005. 584-593.

[2] BEJERANP Y. Simple and efficient k-coverage verification without locatioan information[A]. Proceedings of the IEEE Conference on Computer Communications[C]. Phoenix, 2008. 291-295.

[3] 蘇瀚，汪蕓. 傳感器網(wǎng)絡(luò)中無需地理信息的空洞填補算法[J]. 計算機學(xué)報. 2009, 32(10): 1957-1970.SU H, WANG Y. A self-healing algorithm without location in sensor networks[J]. Chinese Journal of Computers, 2009, 32(10): 1957-1970.

[4] SEKHAR A, MANOJ B S. Dynamic coverage maintenance algorithms for sensor networks with limited mobility[A]. Proceedings of the Pervasive Computing and Communications[C]. Hawaii, 2005.

[5] LI X, DAVID H. Distributed coordinate-free hole recovery[A]. Proc of GLOBECOM[C]. Beijing, 2006. 189-194.

[6] YOU J, LIECKFELDT D. Context-aware geographic routing for sensor networks with routing holes[A]. Proceedings of the Wireless Communications and Networking Conference[C]. Budapest, 2009. 1-6.

[7] BOYD, ALAN W. On the selection of connectivity-based metrics for wsns using a classification of application behavior sensor networks[A].Proceedings of the Ubiquitous, and Trustworthy Computing(SUTC)[C]. California, 2010.

[8] FYS L, CHIU P L. A near-optimal sensor placement algorithm to achieve complete coverage/discrimination in sensor networks[J]. IEEE Communications Letters, 2005, 9(1):43-45.

[9] NITIN K, DIMITRIOS G. Sensor network coverage restoration[J].CITESEER, 2008, 10(12): 21-24.

[10] KUN Y H, JANG P S. Hole detection and boundary recognition in wireless sensor networks[A]. Proceedings of the Indoor and Mobile Radio Communications[C]. Mannheim, 2009. 72-82.

[11] PRASAN K, JANG Z T. Vector method based coverage hole recovery in wireless sensor[A]. Proceedings of the Communication Systems and Networks (COMSNETS)[C]. Bangalore, 2010. 1-9.