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

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

1 引言

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

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

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

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

2 問題描述

2.1 前提假設(shè)

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

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

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

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

圖1 空洞示意

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

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

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

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

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

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

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

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

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

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

證明 假設(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)點(diǎn)且q∈(Du∩Dv∩Dw∩Dx)。根據(jù)題設(shè)?q∈cv∩cw且滿足q∈Du，則q為內(nèi)點(diǎn)且滿足q∈(Du∩Dv∩Dw)。若根據(jù)本文算法移動圓u，則內(nèi)點(diǎn)p永遠(yuǎn)會處于某個圓的范圍中，其覆蓋度一定大于其他內(nèi)點(diǎn)，而q不滿足q∈(Du∩Dv∩Dw)。證畢。

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

定理1 若圓v、w 在圓u形成的覆蓋弧滿足Su,w?Su,v，那么圓w產(chǎn)生的內(nèi)點(diǎn)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)點(diǎn)p均有p∈Du覆蓋，其產(chǎn)生的內(nèi)點(diǎn)也為覆蓋內(nèi)點(diǎn)即存在內(nèi)點(diǎn)p滿足p?Dv。證畢。

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

圖5 覆蓋弧性質(zhì)

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

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

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

證明 由覆蓋弧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)點(diǎn)p有p∈(Dw∪Dv)。證畢。

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

3 算法描述

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

3.1 移動方向

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

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

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

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

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

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

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

3.2 SOI算法與計(jì)算移動距離

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

當(dāng)一個節(jié)點(diǎn)u被空洞探測算法計(jì)算為空洞邊緣節(jié)點(diǎn)時(shí)，運(yùn)行下述算法(SR=r)。

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

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

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

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

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

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

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

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

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

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

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

u和v滿足Ss,u∩Ss,v≠NULL ，則u和v的交點(diǎn)為s的內(nèi)點(diǎn)，設(shè)其交點(diǎn)為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)點(diǎn)。確定最佳內(nèi)點(diǎn)后，進(jìn)行算法最后一步，移動空洞邊緣節(jié)點(diǎn)至最佳位置。

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

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

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

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

4.1 仿真實(shí)驗(yàn)設(shè)置

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

覆蓋問題是無線傳感器網(wǎng)絡(luò)的重要研究問題。在前期的研究工作中，主要依靠在無線傳感器網(wǎng)絡(luò)中布置大量冗余節(jié)點(diǎn)來解決完全覆蓋的問題。本文針對傳感器網(wǎng)絡(luò)覆蓋問題，證明了網(wǎng)絡(luò)覆蓋中幾個基于覆蓋性質(zhì)的定理。基于這些定理，以及在沒有地理信息的支持下，針對密集分布的無線傳感器網(wǎng)絡(luò)中空洞修復(fù)問題，提出了空洞修復(fù)算法SOI。該算法計(jì)算出空洞邊緣節(jié)點(diǎn)的移動方向和空洞邊緣節(jié)點(diǎn)移動的最佳位置，通過移動減小節(jié)點(diǎn)感知圓之間冗余面積擴(kuò)大節(jié)點(diǎn)的覆蓋面積，以此實(shí)現(xiàn)傳感器網(wǎng)絡(luò)中的空洞修復(fù)。實(shí)驗(yàn)表明，該算法在節(jié)點(diǎn)密集分布時(shí)移動所有的空洞邊緣節(jié)點(diǎn)以較小的移動距離獲得良好的空洞修復(fù)性能。本文的下一步工作重點(diǎn)是在沒有地理信息系統(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ò)中無需地理信息的空洞填補(bǔ)算法[J]. 計(jì)算機(jī)學(xué)報(bào). 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.