基于虛擬力的WSN節點優化部署算法

李翠然， 謝健驪， 張昌西， 張華衛

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

無線傳感器網絡WSN (Wireless Sensor Network)以其監測精度高和覆蓋區域廣等特點，被廣泛應用于戰場數據收集、工業和環境監測等領域。由于WSN節點感知范圍有限，為保證整個區域都在監測范圍之內，需要確定適當的WSN覆蓋策略。

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

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

1 節點感知模型及其分布

1.1 節點感知模型

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

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

( 1 )

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

( 2 )

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

1.2 節點的理想分布

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

圖2 3種網格劃分方式

在監測區域邊緣處，以無縫覆蓋為目標的節點部署方式見圖3。

圖3 邊緣處的節點冗余覆蓋示例

令N為監測區域邊緣處的節點數目，則其冗余覆蓋面積為

( 3 )

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

( 4 )

2 節點受力分析

2.1 節點間作用力

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

( 5 )

( 6 )

以監測區域內的5個節點為例，節點間的相互作用力見圖4(a)。圖4中，節點S1，S2，S3，S4和S5所受的合力分別為Ft1=Ft1，2+Ft1，3+Ft1，4，Ft2=Ft2，1+Ft2，3，Ft3=Ft3，1+Ft3，2+Ft3，4，Ft4=Ft4，1+Ft4，3和Ft5=0。各節點在其合力作用下產生運動-受力分析，經多次運動后各節點達到穩定狀態，其所處位置見圖4(b)。圖中，除節點S5的位置未發生變化外，節點S1、S2和S3以及節點S1，S3和S4分別構成正三角形。在實際監測區域內，節點分布一般較為密集，節點S5這種情況出現的概率極低，可不用考慮。

圖4 節點間作用力和達到的穩定位置

2.2 區域邊緣對節點的作用力

( 7 )

節點i所受合力為

( 8 )

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

圖5 離散點的作用力和節點移動后的穩定位置

后達到穩定狀態的位置見圖5(b)。可見，在WSN網絡中，節點Si所受作用力由2部分構成：Fti和Fni，表示為

( 9 )

3 節點移動與位置更新

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

(10)

(11)

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

由此，給出基于虛擬力的WSN節點優化算法WVFA的流程圖見圖6。

圖6 WSN節點優化算法WVFA流程圖

圖7所示為WSN節點在監測區域內的初始分布。圖8為不同迭代次數時的節點分布，由圖8可看出，當迭代次數達到50時，節點位置基本維持不變，說明網絡已處于穩定狀態。圖9(a)表示節點在監測區域內的運動軌跡，圖9(b)表示網絡覆蓋率隨迭代次數的變化趨勢。

圖7 監測區域內節點的初始分布

圖8 不同迭代次數下的節點位置

圖9 節點運動軌跡和網絡覆蓋率性能

4 仿真結果

為仿真比較本文提出的WVFA算法與VFA算法[3]、CBS算法[11]、HLVFA算法[12]的網絡覆蓋率和節點能耗等性能，相關仿真參數見表1。

表1 主要仿真參數

圖10為不同的權重u對網絡覆蓋率的影響。表2為不同u值時的節點平均移動距離davg、節點移動距離的標準差σ以及網絡達到穩定狀態時的覆蓋率。可以看出，WVFA算法的收斂速度隨著u值的增大逐漸變得緩慢，而不同的u值對穩定狀態下的網絡覆蓋率影響甚微。此外，隨著u值的增加，davg與σ的值減小。這說明，從降低節點能耗和縮小節點間能耗差異的優化目標出發，WVFA算法應選取較大的u值。

圖10 WVFA算法中不同的權重u和網絡覆蓋率之間的關系

表2 不同權值u對應的WVFA算法中的參數值

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

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

圖13(a)、圖13(b)分別為節點數目與參數davg和σ之間的關系。可以看出，WVFA算法的davg值最小，同時該算法具有較小的σ值。綜合來看， WVFA算法在降低節點能耗和縮小節點間能耗差異方面具有較優的性能。

圖11 VFA的閾值dth和斥力系數ωr對網絡覆蓋率的影響

圖12 迭代次數和節點數目對網絡覆蓋率的影響

圖13 不同節點數目下的節點移動距離的平均值和標準差

5 結束語

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