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

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

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

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

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

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

1.1 節(jié)點感知模型

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

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

( 1 )

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

( 2 )

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

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

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

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

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

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

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

( 3 )

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

( 4 )

2 節(jié)點受力分析

2.1 節(jié)點間作用力

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

( 5 )

( 6 )

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

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

2.2 區(qū)域邊緣對節(jié)點的作用力

( 7 )

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

( 8 )

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

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

后達到穩(wěn)定狀態(tài)的位置見圖5(b)?？梢姡赪SN網(wǎng)絡(luò)中，節(jié)點Si所受作用力由2部分構(gòu)成：Fti和Fni，表示為

( 9 )

3 節(jié)點移動與位置更新

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

(10)

(11)

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

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

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

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

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

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

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

4 仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

圖13 不同節(jié)點數(shù)目下的節(jié)點移動距離的平均值和標準差

5 結(jié)束語

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