基于密集度的虛擬力節(jié)點部署算法*

滕志軍,張 力,郭力文,呂金玲(東北電力大學(xué)信息工程學(xué)院,吉林 吉林 132012)

近年來,具有高度的靈活性和集成功能多樣化的可移動無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)在軍事偵察、環(huán)境監(jiān)測以及防爆救災(zāi)等領(lǐng)域得到廣泛的應(yīng)用[1-4]。而移動傳感器網(wǎng)絡(luò)節(jié)點的初次部署通常為隨機(jī)拋撒,很難實現(xiàn)對監(jiān)測區(qū)域的覆蓋需求,因此采用適合的節(jié)點部署算法進(jìn)行再部署以滿足應(yīng)用需求[5-7]。

目前,關(guān)于節(jié)點部署算法已有大量的研究成果,包括基于計算幾何理論的相關(guān)算法,如基于Delaunay、Voronoi 等網(wǎng)格劃分分析方法[8];集中式算法,如遺傳算法、蟻群算法、粒子群算法等;以及基于虛擬力的節(jié)點部署算法[9-10]。文獻(xiàn)[11]首次提出基于虛擬力的節(jié)點自主部署算法VFA(Virtual Force Algorithm),并分別考慮了二元感知模型以及概率感知模型。文獻(xiàn)[12]在傳統(tǒng)VFA的基礎(chǔ)上考慮了監(jiān)控區(qū)域的目標(biāo)特性,節(jié)點不僅受到節(jié)點間的相互作用力外還受到目標(biāo)位置的引力作用。文獻(xiàn)[13]引入了“引力線”的概念,構(gòu)建了節(jié)點與引力線之間的斥力以此減少了節(jié)點的能量消耗,縮短了部署時間。文獻(xiàn)[14]將傳統(tǒng)VFA的動態(tài)部署分成簇間和簇內(nèi)兩個階段以此改善VFA中出現(xiàn)的簇間干涉,節(jié)點受力均衡的問題。文獻(xiàn)[15]結(jié)合計算幾何重新定義了節(jié)點間的鄰接關(guān)系,從而保證了區(qū)域的覆蓋質(zhì)量。文獻(xiàn)[16]在VFA的思想上,針對同構(gòu)節(jié)點、異構(gòu)節(jié)點、非規(guī)則區(qū)域等各種應(yīng)用場合,研究了基于粒子均衡的移動傳感器網(wǎng)絡(luò)覆蓋,取得了較好的覆蓋效果和網(wǎng)絡(luò)生命周期。

但現(xiàn)有基于虛擬力的節(jié)點部署算法對虛擬力模型的相關(guān)參數(shù)研究相對較少,在無法判斷隨機(jī)部署的情況下,僅僅根據(jù)經(jīng)驗值設(shè)置虛擬力模型的相關(guān)參數(shù),對部署效果產(chǎn)生了一定的影響。因此,本文提出基于密集度的虛擬力節(jié)點部署算法IVFA-B(Intensity-based Virtual Force Algorithm with Boundary Forces)采用公式推導(dǎo)的方式優(yōu)化虛擬力相關(guān)參數(shù),并定義了節(jié)點的密集度以此來選擇虛擬力模型中的最優(yōu)距離閾值,通過仿真實驗證明了IVFA-B算法對提高網(wǎng)絡(luò)覆蓋質(zhì)量的有效性。

1 問題與假設(shè)

假設(shè)在A×B監(jiān)測區(qū)域內(nèi)隨機(jī)拋撒N個移動傳感器節(jié)點。節(jié)點的感知半徑均為Rs,通信半徑均為Rc,并滿足Rc≥2Rs。節(jié)點感知模型均采用布爾感知模型,并對無線傳感器網(wǎng)絡(luò)參數(shù)進(jìn)行如下假設(shè):①每個傳感器節(jié)點均具有充足的能量,并與移動執(zhí)行器相結(jié)合,可以在監(jiān)測區(qū)域內(nèi)移動到最佳位置;②每個傳感器節(jié)點都可以通過GPS或者其他的相關(guān)定位算法獲取到自身的位置信息和自身與其鄰居節(jié)點間的位置關(guān)系;③每個傳感器節(jié)點可以感知并獲取在其通信半徑范圍內(nèi)其他傳感器節(jié)點的位置。

相關(guān)定義如下:

定義1布爾感知模型[17]

傳感器節(jié)點si(xi,yi)以自身坐標(biāo)(xi,yi)為圓心,以感知半徑Rs作為感知區(qū)域半徑構(gòu)成其最大感知范圍,即為布爾感知模型。二維平面內(nèi)任意一點p(x,y)與傳感器節(jié)點si之間的歐式距離記為

(1)

若d(si,p)≤Rs,則點p(x,y)被覆蓋,節(jié)點si對點p的感知概率為1,否則為0,公式如下:

(2)

定義2覆蓋率[18]

傳感器節(jié)點已經(jīng)覆蓋的區(qū)域面積大小As與監(jiān)測區(qū)域的總面積大小A之比為覆蓋率,記為a,定義為:

a=As/A

(3)

定義3平均移動距離[19]

(4)

定義4密集度

節(jié)點的密集度代表其所在區(qū)域的密集程度,公式如下:

(5)

式中:N為si的鄰居節(jié)點個數(shù),din為鄰居節(jié)點sn到si的距離。對于一個節(jié)點來說,它的相鄰節(jié)點個數(shù)越多,它與相鄰節(jié)點之間的距離越小,該節(jié)點的密集度越大,則表明這個節(jié)點所在區(qū)域越密集。

2 基于密集度的虛擬力節(jié)點部署算法

2.1 算法涉及的虛擬作用力

①節(jié)點間的相互作用力

(6)

式中:dij表示節(jié)點si與節(jié)點sj之間的歐氏距離,αij表示節(jié)點si到節(jié)點sj線段的方向角,ωa/ωb分別表示虛擬力引力/斥力系數(shù),Dth表示節(jié)點間距離閾值,Rc表示節(jié)點的通信半徑。

②區(qū)域邊界對節(jié)點的斥力

dib表示節(jié)點si與區(qū)域邊界之間的歐式距離。節(jié)點與區(qū)域邊界的安全距離為dth/2。如果dib大于節(jié)點與區(qū)域邊界的安全距離,則不存在斥力作用;如果dib小于節(jié)點與區(qū)域邊界的安全距離,則表達(dá)式如下

(7)

(8)

③節(jié)點所受虛擬力合力

(9)

式中:k表示si的鄰居節(jié)點數(shù)目。

無線傳感器節(jié)點在虛擬力Fi作用的約束下,將按照以下方式從原有位置P(xiold,yiold)移動到目標(biāo)位置P(xinew,yinew)。

(10)

式中:Fx和Fy分別表示在x軸和y軸方向上傳感器所受力的投影,Fxy表示傳感器所受到的合力,Maxdis表示傳感器單次移動的最大距離。

2.2 虛擬力參數(shù)

在傳統(tǒng)虛擬力節(jié)點部署算法中,wa,wb分別表示虛擬力引力參數(shù)和斥力參數(shù)。由于數(shù)目較少的鄰居節(jié)點之間存在斥力作用,數(shù)目較多的非鄰居節(jié)點之間存在引力作用,為使節(jié)點達(dá)到平衡狀態(tài),從而將斥力參數(shù)設(shè)置地遠(yuǎn)大于引力參數(shù)。但在事先無法判定隨機(jī)部署狀態(tài)的情況下,僅僅根據(jù)經(jīng)驗值設(shè)置一個較大的斥力參數(shù)和一個較小的引力參數(shù),不能達(dá)到很好的覆蓋效果。為此,本文給出一種解決方案,通過對節(jié)點進(jìn)行受力分析,從而推導(dǎo)出ωa與ωb的關(guān)系式。

如圖1所示,對節(jié)點si進(jìn)行受力分析。

圖1 極端節(jié)點分析圖

(11)

(12)

(13)

當(dāng)節(jié)點si受力平衡,達(dá)到穩(wěn)定狀態(tài)時,

(14)

由于區(qū)域邊界對節(jié)點同樣為排斥力,區(qū)域邊界斥力參數(shù)為ωr,最終得到引力/斥力參數(shù)的表達(dá)式為:

(15)

ωa=Dth-dij

(16)

2.3 距離閾值

通過分析經(jīng)典虛擬力模型,得出距離閾值可以調(diào)節(jié)傳感器節(jié)點間的相互作用力屬性。而距離閾值的設(shè)置不僅與節(jié)點感知半徑有關(guān),也與鄰居節(jié)點分布之間有著密切的聯(lián)系。同時,節(jié)點的相鄰節(jié)點數(shù)和與其相鄰節(jié)點的距離共同影響監(jiān)測區(qū)域內(nèi)節(jié)點分布的密集程度。因此,判斷節(jié)點所在區(qū)域的密集程度可以通過衡量每個節(jié)點的相鄰節(jié)點數(shù)目以及與相鄰節(jié)點間的距離來判斷。

圖2為2組不同的環(huán)境設(shè)置條件下的距離閾值設(shè)置分析圖。圖2(a)覆蓋率a<1,表明節(jié)點沒有完全覆蓋整個監(jiān)測區(qū)域,故距離閾值設(shè)置為兩個節(jié)點的感知半徑之和。圖2(b)覆蓋率a≥1,表明節(jié)點足夠覆蓋整個監(jiān)測區(qū)域,最佳部署為正三角形部署,因此距離閾值的設(shè)置如式(17)。

(17)

圖2 距離閾值分析圖

2.4 算法偽代碼

基于上述分析,本文通過合理設(shè)置虛擬力相關(guān)參數(shù)并且利用節(jié)點的密集度選擇最佳距離閾值,從而提出了基于密集度的虛擬力節(jié)點部署算法(IVFA-B),該算法可以更好地實現(xiàn)全局的覆蓋優(yōu)化,并提高了虛擬力算法性能。算法實現(xiàn)的偽代碼如表1所示。

表1IVFA-B算法的偽代碼

3 仿真結(jié)果與性能分析

圖3顯示了4種算法對35個節(jié)點的部署情況,其中圖3(a)為網(wǎng)絡(luò)中節(jié)點的初始分布情況,初始覆蓋率為65.4%。圖3(b)為應(yīng)用VFA算法的節(jié)點分布情況,節(jié)點分布有所提高,但可以看出部分節(jié)點移出到邊界外。圖3(c)為應(yīng)用文獻(xiàn)[15]中算法的節(jié)點分布情況,該算法不僅考慮到了區(qū)域的邊界條件而且重新定義了節(jié)點的鄰接關(guān)系,因此提高了一定的覆蓋率。圖3(d)為應(yīng)用文獻(xiàn)[16]中算法的節(jié)點分布情況,網(wǎng)絡(luò)覆蓋率達(dá)到90%。圖3(e)為應(yīng)用本文IVFA-B算法的節(jié)點分布情況,節(jié)點分布變得相對均勻,網(wǎng)絡(luò)覆蓋率百分比也提高到91.3%。

表2 仿真實驗參數(shù)

圖3 網(wǎng)絡(luò)覆蓋圖

圖4 覆蓋率隨迭代次數(shù)變化

圖4表示在相同條件下分別運行VFA、文獻(xiàn)[15-16]以及本文提出的IVFA-B算法,網(wǎng)絡(luò)覆蓋率的變化情況。在前40次迭代中,4種算法的覆蓋率均有較大幅度的提高,其中IVFA-B與初始覆蓋率相比提高了24個百分點,并高于其他3種算法。在40次迭代之后,IVFA-B對覆蓋率的優(yōu)化效果減慢,但仍有提高的空間,并逐漸趨于平穩(wěn),而其他3種算法的優(yōu)化性能已經(jīng)趨于平緩。

圖5 平均移動距離隨迭代次數(shù)變化

圖5比較了隨迭代次數(shù)變化,4種算法節(jié)點平均移動距離的變化情況。隨著迭代次數(shù)的不斷增加,節(jié)點部署情況逐漸穩(wěn)定,因此節(jié)點的移動距離不斷減小,但I(xiàn)VFA-B的減小程度始終高于其他3種虛擬力算法。

圖6比較了隨節(jié)點數(shù)目的變化,VFA、文獻(xiàn)[15-16]以及IVFA-B算法網(wǎng)絡(luò)覆蓋率的變化情況。隨著節(jié)點數(shù)目的增加,4種算法的覆蓋率均不斷增加,但I(xiàn)VFA-B的覆蓋效果始終高于其他3種算法。當(dāng)節(jié)點數(shù)目在30～45左右時,IVFA-B的優(yōu)勢較明顯,當(dāng)節(jié)點數(shù)目大于45時,覆蓋率相差不大。

圖8 總的移動距離隨節(jié)點數(shù)目變化

由于節(jié)點能量的消耗主要集中在移動上,因此把節(jié)點的移動距離作為網(wǎng)絡(luò)能量消耗的衡量指標(biāo)。圖7和圖8比較了隨節(jié)點數(shù)目的變化,4種算法的節(jié)點平均移動距離和總移動距離的變化情況。由于節(jié)點數(shù)目不斷增加,4種算法的平均移動距離和總的移動距離均不斷增加,但I(xiàn)VFA-B與其他3種算法相比增加的更緩慢。這是因為IVFA-B算法采用了具有一定適用性的虛擬力參數(shù)并且通過節(jié)點密集度選擇最佳距離閾值,減小了節(jié)點的移動距離,在保證網(wǎng)絡(luò)覆蓋率的同時也節(jié)約了能量的消耗。

圖6 覆蓋率隨節(jié)點數(shù)目變化

圖7 平均移動距離隨節(jié)點數(shù)目變化

4 總結(jié)

基于密集度的虛擬力節(jié)點部署算法在傳統(tǒng)虛擬力節(jié)點部署算法的基礎(chǔ)上,結(jié)合公式推導(dǎo)對虛擬力參數(shù)進(jìn)行優(yōu)化設(shè)置,彌補(bǔ)了在無法判斷隨機(jī)部署的情況下,根據(jù)經(jīng)驗值設(shè)置相關(guān)參數(shù)影響覆蓋效果的不足。并引入節(jié)點密集度的概念,通過密集度選擇虛擬力模型中調(diào)節(jié)傳感器節(jié)點間的相互作用力屬性的最優(yōu)距離閾值,實現(xiàn)節(jié)點的均勻分布。通過實驗驗證表明,相比VFA、文獻(xiàn)[15-16]中改進(jìn)的虛擬力算法,本文所提出的部署算法在網(wǎng)絡(luò)覆蓋率和節(jié)點能耗方面具有明顯的優(yōu)勢。今后將進(jìn)一步研究有障礙物的情況下算法的適應(yīng)性及相應(yīng)改進(jìn)策略。