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

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

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

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

1 問(wèn)題與假設(shè)

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

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

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

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

(1)

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

(2)

定義2覆蓋率[18]

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

a=As/A

(3)

定義3平均移動(dòng)距離[19]

(4)

定義4密集度

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

(5)

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

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

2.1 算法涉及的虛擬作用力

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

(6)

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

②區(qū)域邊界對(duì)節(jié)點(diǎn)的斥力

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

(7)

(8)

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

(9)

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

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

(10)

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

2.2 虛擬力參數(shù)

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

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

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

(11)

(12)

(13)

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

(14)

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

(15)

ωa=Dth-dij

(16)

2.3 距離閾值

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

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

(17)

圖2 距離閾值分析圖

2.4 算法偽代碼

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

表1IVFA-B算法的偽代碼

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

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

表2 仿真實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

圖8 總的移動(dòng)距離隨節(jié)點(diǎn)數(shù)目變化

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

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

圖7 平均移動(dòng)距離隨節(jié)點(diǎn)數(shù)目變化

4 總結(jié)

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