基于虛擬力的WSN節(jié)點(diǎn)優(yōu)化部署算法

李翠然， 謝健驪， 張昌西， 張華衛(wèi)

(1. 蘭州交通大學(xué) 電子信息工程學(xué)院， 甘肅 蘭州 730070;2. 蘭州交通大學(xué) 光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室， 甘肅 蘭州 730070； 3. 徐州地鐵運(yùn)營(yíng)有限公司， 江蘇 徐州 221000)

無線傳感器網(wǎng)絡(luò)WSN (Wireless Sensor Network)以其監(jiān)測(cè)精度高和覆蓋區(qū)域廣等特點(diǎn)，被廣泛應(yīng)用于戰(zhàn)場(chǎng)數(shù)據(jù)收集、工業(yè)和環(huán)境監(jiān)測(cè)等領(lǐng)域。由于WSN節(jié)點(diǎn)感知范圍有限，為保證整個(gè)區(qū)域都在監(jiān)測(cè)范圍之內(nèi)，需要確定適當(dāng)?shù)腤SN覆蓋策略。

在WSN覆蓋策略研究中，采用虛擬力算法可使節(jié)點(diǎn)以較短的移動(dòng)距離快速完成在覆蓋區(qū)域的分散部署，有效降低了網(wǎng)絡(luò)能耗。文獻(xiàn)[1]給出了虛擬力的基本概念，即人造引力場(chǎng)中的“引力”和“斥力”，其合力導(dǎo)致引力場(chǎng)中的機(jī)器人產(chǎn)生相應(yīng)的運(yùn)動(dòng)。在文獻(xiàn)[2]提出的節(jié)點(diǎn)部署策略中，虛擬粒子用來表征節(jié)點(diǎn)，通過對(duì)虛擬場(chǎng)域中大量粒子的受力分析使粒子達(dá)到受力平衡的穩(wěn)定狀態(tài)。文獻(xiàn)[3-4]提出了一種虛擬力算法VFA (Virtual Force Algorithm)，該算法中的節(jié)點(diǎn)以隨機(jī)部署方式進(jìn)行初始分布，根據(jù)對(duì)節(jié)點(diǎn)的受力分析可獲知節(jié)點(diǎn)的下一步運(yùn)動(dòng)軌跡，從而完成節(jié)點(diǎn)在覆蓋區(qū)域內(nèi)的部署。然而，該算法可能存在的缺陷是：節(jié)點(diǎn)受力平衡是局部性事件而非全局性，這會(huì)使節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)呈現(xiàn)出非均勻分布；相關(guān)權(quán)重因子在節(jié)點(diǎn)位置更新預(yù)測(cè)中的取值往往是預(yù)設(shè)的經(jīng)驗(yàn)值，導(dǎo)致節(jié)點(diǎn)在受力平衡時(shí)依然存在較大的覆蓋漏洞；節(jié)點(diǎn)的能耗主要由節(jié)點(diǎn)自身的移動(dòng)及其在移動(dòng)過程中與其他節(jié)點(diǎn)的碰撞導(dǎo)致，由此引起節(jié)點(diǎn)間能耗的不均衡。

為克服以上缺陷，本文提出一種優(yōu)化的虛擬力節(jié)點(diǎn)部署算法WVFA，基于布爾感知模型和三角形網(wǎng)格劃分，以最小化區(qū)域邊緣處節(jié)點(diǎn)的冗余覆蓋面積、實(shí)現(xiàn)覆蓋區(qū)域內(nèi)部的無縫覆蓋為優(yōu)化目標(biāo)，通過對(duì)節(jié)點(diǎn)的受力分析推算出節(jié)點(diǎn)距離區(qū)域邊緣處的歐氏距離，并將前一時(shí)刻節(jié)點(diǎn)所受虛擬力作為位置更新權(quán)重代入節(jié)點(diǎn)位置更新預(yù)測(cè)方程，從而縮小節(jié)點(diǎn)間的能耗差距、實(shí)現(xiàn)WSN的優(yōu)化部署。

1 節(jié)點(diǎn)感知模型及其分布

1.1 節(jié)點(diǎn)感知模型

在VFA算法和本文算法中，WSN節(jié)點(diǎn)被看作是具有相互作用力的帶電微粒。節(jié)點(diǎn)間產(chǎn)生相應(yīng)的引力或斥力，是由節(jié)點(diǎn)間距離與某一給定閾值的大小比較決定的。算法的基本假設(shè)條件為：WSN節(jié)點(diǎn)的位置信息可通過GPS設(shè)備獲知；節(jié)點(diǎn)配備全向傳感器，感知數(shù)據(jù)可來自任意方向；節(jié)點(diǎn)具有一定的移動(dòng)性；節(jié)點(diǎn)感知模型為布爾模型。

在2D監(jiān)測(cè)區(qū)域內(nèi)，令節(jié)點(diǎn)S和目標(biāo)點(diǎn)t的位置坐標(biāo)分別為(Sx,Sy)和(tx,ty)，節(jié)點(diǎn)感知半徑為rs，則目標(biāo)點(diǎn)t被節(jié)點(diǎn)S感知到的概率為[5-6]

( 1 )

式中：d(S,t)為節(jié)點(diǎn)S和目標(biāo)點(diǎn)t之間的歐氏距離，可表示為

( 2 )

圖1(a)和圖1(b)分別給出了節(jié)點(diǎn)S的布爾感知模型和目標(biāo)點(diǎn)t的感知概率分布。

1.2 節(jié)點(diǎn)的理想分布

圖1 布爾感知模型和不同rs下的感知概率

圖2 3種網(wǎng)格劃分方式

在監(jiān)測(cè)區(qū)域邊緣處，以無縫覆蓋為目標(biāo)的節(jié)點(diǎn)部署方式見圖3。

圖3 邊緣處的節(jié)點(diǎn)冗余覆蓋示例

令N為監(jiān)測(cè)區(qū)域邊緣處的節(jié)點(diǎn)數(shù)目，則其冗余覆蓋面積為

( 3 )

對(duì)S/N求導(dǎo)可使區(qū)域邊緣處的冗余覆蓋達(dá)到最小，于是可得

( 4 )

2 節(jié)點(diǎn)受力分析

2.1 節(jié)點(diǎn)間作用力

根據(jù)已有文獻(xiàn)和前文分析，相鄰節(jié)點(diǎn)間的距離為rs是保證監(jiān)測(cè)區(qū)域無縫覆蓋的充要條件。節(jié)點(diǎn)Si和Sj之間的作用力Ftij可表示為

( 5 )

( 6 )

以監(jiān)測(cè)區(qū)域內(nèi)的5個(gè)節(jié)點(diǎn)為例，節(jié)點(diǎn)間的相互作用力見圖4(a)。圖4中，節(jié)點(diǎn)S1，S2，S3，S4和S5所受的合力分別為Ft1=Ft1，2+Ft1，3+Ft1，4，F(xiàn)t2=Ft2，1+Ft2，3，F(xiàn)t3=Ft3，1+Ft3，2+Ft3，4，F(xiàn)t4=Ft4，1+Ft4，3和Ft5=0。各節(jié)點(diǎn)在其合力作用下產(chǎn)生運(yùn)動(dòng)-受力分析，經(jīng)多次運(yùn)動(dòng)后各節(jié)點(diǎn)達(dá)到穩(wěn)定狀態(tài)，其所處位置見圖4(b)。圖中，除節(jié)點(diǎn)S5的位置未發(fā)生變化外，節(jié)點(diǎn)S1、S2和S3以及節(jié)點(diǎn)S1，S3和S4分別構(gòu)成正三角形。在實(shí)際監(jiān)測(cè)區(qū)域內(nèi)，節(jié)點(diǎn)分布一般較為密集，節(jié)點(diǎn)S5這種情況出現(xiàn)的概率極低，可不用考慮。

圖4 節(jié)點(diǎn)間作用力和達(dá)到的穩(wěn)定位置

2.2 區(qū)域邊緣對(duì)節(jié)點(diǎn)的作用力

( 7 )

節(jié)點(diǎn)i所受合力為

( 8 )

圖5(a)為節(jié)點(diǎn)S1受到的邊緣離散點(diǎn)作用力。圖5中，S1所受合力為Fn1=Fn1，3+Fn1，4+Fn1，5。節(jié)點(diǎn)S1在其合力作用下產(chǎn)生運(yùn)動(dòng)-受力分析，多次運(yùn)動(dòng)

圖5 離散點(diǎn)的作用力和節(jié)點(diǎn)移動(dòng)后的穩(wěn)定位置

后達(dá)到穩(wěn)定狀態(tài)的位置見圖5(b)。可見，在WSN網(wǎng)絡(luò)中，節(jié)點(diǎn)Si所受作用力由2部分構(gòu)成：Fti和Fni，表示為

( 9 )

3 節(jié)點(diǎn)移動(dòng)與位置更新

考慮到節(jié)點(diǎn)移動(dòng)與其能耗之間的關(guān)聯(lián)，為降低節(jié)點(diǎn)間的能耗差異，本文將節(jié)點(diǎn)前一時(shí)刻受到的虛擬力作為更新權(quán)重代入節(jié)點(diǎn)位置更新計(jì)算中，則節(jié)點(diǎn)Si在t步的移動(dòng)距離di(t)和位置更新Si-new(t)分別為

(10)

(11)

式中：u為平衡權(quán)重(0≤u≤1)，它與達(dá)到覆蓋要求的迭代次數(shù)相關(guān)；Fi(t)為節(jié)點(diǎn)Si在t步時(shí)所受合力；Si-ini(t)為節(jié)點(diǎn)Si初始位置；stepMax為節(jié)點(diǎn)Si最大移動(dòng)步長(zhǎng)。

由此，給出基于虛擬力的WSN節(jié)點(diǎn)優(yōu)化算法WVFA的流程圖見圖6。

圖6 WSN節(jié)點(diǎn)優(yōu)化算法WVFA流程圖

圖7所示為WSN節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)的初始分布。圖8為不同迭代次數(shù)時(shí)的節(jié)點(diǎn)分布，由圖8可看出，當(dāng)?shù)螖?shù)達(dá)到50時(shí)，節(jié)點(diǎn)位置基本維持不變，說明網(wǎng)絡(luò)已處于穩(wěn)定狀態(tài)。圖9(a)表示節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)的運(yùn)動(dòng)軌跡，圖9(b)表示網(wǎng)絡(luò)覆蓋率隨迭代次數(shù)的變化趨勢(shì)。

圖7 監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)的初始分布

圖8 不同迭代次數(shù)下的節(jié)點(diǎn)位置

圖9 節(jié)點(diǎn)運(yùn)動(dòng)軌跡和網(wǎng)絡(luò)覆蓋率性能

4 仿真結(jié)果

為仿真比較本文提出的WVFA算法與VFA算法[3]、CBS算法[11]、HLVFA算法[12]的網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)能耗等性能，相關(guān)仿真參數(shù)見表1。

表1 主要仿真參數(shù)

圖10為不同的權(quán)重u對(duì)網(wǎng)絡(luò)覆蓋率的影響。表2為不同u值時(shí)的節(jié)點(diǎn)平均移動(dòng)距離davg、節(jié)點(diǎn)移動(dòng)距離的標(biāo)準(zhǔn)差σ以及網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)時(shí)的覆蓋率?？梢钥闯觯琖VFA算法的收斂速度隨著u值的增大逐漸變得緩慢，而不同的u值對(duì)穩(wěn)定狀態(tài)下的網(wǎng)絡(luò)覆蓋率影響甚微。此外，隨著u值的增加，davg與σ的值減小。這說明，從降低節(jié)點(diǎn)能耗和縮小節(jié)點(diǎn)間能耗差異的優(yōu)化目標(biāo)出發(fā)，WVFA算法應(yīng)選取較大的u值。

圖10 WVFA算法中不同的權(quán)重u和網(wǎng)絡(luò)覆蓋率之間的關(guān)系

表2 不同權(quán)值u對(duì)應(yīng)的WVFA算法中的參數(shù)值

為了對(duì)比算法性能，需要對(duì)VFA算法中的相關(guān)參數(shù)進(jìn)行優(yōu)化設(shè)置。圖11(a)和圖11(b)分別給出了參數(shù)dth、ωr與網(wǎng)絡(luò)覆蓋率之間的關(guān)系。由圖11(a)可以看出，當(dāng)dth=2rs時(shí)，網(wǎng)絡(luò)覆蓋率最大；由圖11(b)可知，當(dāng)ωr=2 500時(shí)，網(wǎng)絡(luò)覆蓋率最大。因此，VFA算法中的參數(shù)dth和ωr將分別取為2rs和2 500。

圖12(a)、圖12(b)分別為迭代次數(shù)和節(jié)點(diǎn)數(shù)目的變化對(duì)4種算法的網(wǎng)絡(luò)覆蓋率性能影響。由圖12(a)可知，WVFA算法收斂速度較慢，這是由于該算法縮小了節(jié)點(diǎn)的受力范圍，從而使節(jié)點(diǎn)的單次移動(dòng)步長(zhǎng)較小。此外，還可看出，WVFA算法在穩(wěn)定狀態(tài)時(shí)的網(wǎng)絡(luò)覆蓋率性能最優(yōu)。由圖12(b)可看出，4種算法的覆蓋率均隨著節(jié)點(diǎn)數(shù)目的增加呈增高趨勢(shì)，WVFA算法的網(wǎng)絡(luò)覆蓋率最高。

圖13(a)、圖13(b)分別為節(jié)點(diǎn)數(shù)目與參數(shù)davg和σ之間的關(guān)系?？梢钥闯觯琖VFA算法的davg值最小，同時(shí)該算法具有較小的σ值。綜合來看， WVFA算法在降低節(jié)點(diǎn)能耗和縮小節(jié)點(diǎn)間能耗差異方面具有較優(yōu)的性能。

圖11 VFA的閾值dth和斥力系數(shù)ωr對(duì)網(wǎng)絡(luò)覆蓋率的影響

圖12 迭代次數(shù)和節(jié)點(diǎn)數(shù)目對(duì)網(wǎng)絡(luò)覆蓋率的影響

圖13 不同節(jié)點(diǎn)數(shù)目下的節(jié)點(diǎn)移動(dòng)距離的平均值和標(biāo)準(zhǔn)差

5 結(jié)束語

本文提出了一種基于虛擬力的WSN節(jié)點(diǎn)優(yōu)化部署算法WVFA。仿真結(jié)果表明：WVFA算法在穩(wěn)定狀態(tài)時(shí)的網(wǎng)絡(luò)覆蓋率最高；WVFA算法的davg值為最小，同時(shí)該算法具有較小的σ值。因此，提出的優(yōu)化部署算法能夠在較低節(jié)點(diǎn)能耗條件下使網(wǎng)絡(luò)覆蓋率性能獲得較大提高，實(shí)現(xiàn)了WSN的節(jié)能優(yōu)化部署。