利用移動內點來修復傳感器網絡空洞的算法

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

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

1 引言

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

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

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

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

2 問題描述

2.1 前提假設

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

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

2.2 相關術語

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

圖1 空洞示意

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

圖2 空洞邊緣節點，鄰居節點示意

定義3 空洞內點。根據內點定義，在特殊情況下如果A為空洞邊緣節點，那么P3為空洞內點。

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

定義5 空洞邊緣鄰居。在傳感器網絡中如果有2個節點互為鄰居節點，并且這2個節點為空洞邊緣節點，則稱這2個節點互為空洞邊緣鄰居。

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

表1 相關符號定義

圖3 覆蓋弧

對于覆蓋弧，有如下性質。

性質1 覆蓋弧Su,v與Su,w相交，當且僅當μu,w+μu,v＞2×∠v, u, w。

性質2 覆蓋弧Su,w?Su,v，當且僅當μu,w≥μu,v+2×∠v, u, w。

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

性質4 覆蓋弧Su,x?Su,w∩Su,v，當且僅當滿足以下條件：

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 問題描述及相關性質

在空洞修復過程中，本文采用移動空洞邊緣節點的方式進行空洞修復。通過不斷移動空洞邊緣節點減少網絡中感知圓的重疊面積，擴大網絡覆蓋面積，最終達到消除覆蓋空洞的目標。在空洞修復過程中，引入以下準則：1)移動節點不會使其鄰居節點產生新的未覆蓋弧；2)移動節點必須減少覆蓋空洞的面積。由于節點是隨機布置的，每個節點的感知圓與周圍鄰居節點的感知圓不規則相交，產生若干重疊的感知區域，在節點移動的過程中，需要遵循上面提出的2個準則。

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

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

圖4 復雜網絡中的拓撲結構

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

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

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

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

證明 3個圓u、v、w的覆蓋范圍為Du、Dv、Dw，所形成的覆蓋弧為Su,v、Su,w且滿足Su,w?Su,v。假設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所產生的內點p均有p∈Du覆蓋，其產生的內點也為覆蓋內點即存在內點p滿足p?Dv。證畢。

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

圖5 覆蓋弧性質

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

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

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

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

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

3 算法描述

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

3.1 移動方向

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

圖6 節點移動方向的確定

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

如圖7所示，S為空洞邊緣節點，A、B為S鄰居節點，且A、B恰為S空洞邊緣節點（在SOI算法中A、B為覆蓋弧序列中，2個相鄰但覆蓋弧不相交的節點），做AB的垂線經過S且指向S的向量，根據2.3節已知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 空洞邊緣節點移動軌跡

3.2 SOI算法與計算移動距離

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

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

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

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

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

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

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

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

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

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

圖8 計算內點距空洞邊緣節點距離，s為空洞邊緣節點，u和v為隊列中滿足條件節點

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

計算內點與空洞邊緣節點距離的算法實現：

u和v滿足Ss,u∩Ss,v≠NULL ，則u和v的交點為s的內點，設其交點為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＞這即是所求的最佳內點。確定最佳內點后，進行算法最后一步，移動空洞邊緣節點至最佳位置。

圖9 移動空洞邊緣節點S至S '

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

4 仿真實驗

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

4.1 仿真實驗設置

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

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

4.2 實驗結果分析

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

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

圖11 節點移動前后覆蓋比率

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

圖12 無線傳感器節點數量與空洞面積的關系

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

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

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

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

圖14 SOI算法和VHR算法移動節點數量對比

本文算法是基于二維空間的，也可以將其擴展到三維空間，這樣計算內點就擴展為計算空間球體相交的弧切面，SOI算法的目標也可以演變為讓多個傳感器節點的弧切面相交即可。這里覆蓋內點的概念也可以擴展到空間中的面，進一步討論三維空間中的覆蓋問題。

5 結束語

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

[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] 蘇瀚，汪蕓. 傳感器網絡中無需地理信息的空洞填補算法[J]. 計算機學報. 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.