一種優化WSNs節點部署的變步長虛擬力算法*

張俏薇， 陳俊杰

(東南大學 儀器科學與工程學院，江蘇 南京 210096)

0 引 言

無線傳感器網絡[1](wireless sensor networks,WSNs)節點的初始部署通常為隨機部署，導致覆蓋率較低，產生監測空洞。為解決該問題，需調整節點的部署位置，以降低監測空洞和節點部署冗余。虛擬力[2]算法因其實現簡單、應用靈活、優化效果明顯等優點，成為目前移動傳感器節點部署的主要優化方法之一。

國內外對基于虛擬力算法的覆蓋策略進行了許多研究。劉軍[3]針對現有虛擬力算法中存在覆蓋效率和覆蓋率不統一的問題，提出了利用傳感器節點感知扇形區域質心點間的斥力調節感知方向，利用虛擬力和覆蓋冗余度共同控制傳感器的轉動。Brust M R等人[4]考慮到保證無人機航拍的三維覆蓋率時的定位困難，借鑒分子幾何學中電子對圍繞中心原子安排自身位置的思想，提出了一種基于虛擬力算法的自動定位3D簇算法。Khoufi I等人[5]針對復雜假設條件下的應用場景，設計了一種躲避障礙的虛擬力算法，可以避免節點震蕩的問題，并可以在分配機制下檢測到節點部署結果。Li Y等人[6]提出了一種均衡能量的虛擬力算法，引入了一種均勻度函數的評估函數評估WSNs節點部署分布的均勻性，實現了以較少的能耗達到節點部署的高覆蓋率和高度均勻性。前述研究并未考慮到虛擬力算法后期穩定性差這一缺陷，而穩定性差會降低覆蓋效率，影響實際應用效果，增加部署成本。

最小均方(least mean square,LMS)自適應濾波算法具有計算量小、易于實現且對信號的統計特性具有穩健性等優點而得到廣泛應用[7]。本文借鑒LMS自適應濾波函數中基于sigmoid函數的變步長函數，對傳統虛擬力算法的步長函數進行了改進。仿真實驗表明：改進算法可以在維持傳統虛擬力算法優越性的基礎上，改善后期穩定性差、穩態誤差大的缺點，保證了部署效果的有效性。

1 節點感知模型

本文采用0—1圓盤感知模型。假設WSNs監測區域S為二維平面的矩形，離散化為K個網格，每個網格采用網格點進行描述。每個網格的面積為1，單位化后，使得監測區域定義為一個由許多網格點組成的集合

C={a(x1,y1),a(x2,y2),…,a(xK,yK)}

(1)

式中K為網格點的數目，需要根據監測區域的目標和測量精度要求確定。

為了研究的針對性，本文設定感知半徑為一合適常量r。假設每一傳感器節點s放置于位置(xs,ys)，對于任一點d，位置為(xd,yd)，s～d的歐氏距離為l(s,d)，d點被s點監測到的概率與傳感器節點感知半徑r的關系為[8]

(2)

2 基于sigmoid函數的變步長虛擬力算法

在監測區域，將n個移動傳感器節點隨機分布在L×W的大面積目標區域，記為集合U

U=[u1,u2,…,un]

(3)

在該監測區域建立坐標系，使區域的4頂點坐標分別為(100,100)，(L+100,100)，(W+100,100)，(L+100,W+100)，節點ui坐標(xi,yi)，i=1,2,3,…，感知半徑為rp。在此坐標系下構成的WSNs中，初始節點分布不均勻，覆蓋率低。

傳統虛擬力算法[9]中，假設傳感器節點之間，節點與網絡格點之間存在著力的作用，使節點運動。該模型假定[9]：1) 所有節點都是可移動的；2) 所有節點具有全向傳感器，且其感知區域是一個以節點為圓心的圓形；3) 所有節點的位置信息是可知的；4) 所計算出的移動方案可以有效執行；5) 所有節點的質量相同。

每個節點ui可能受到3種力的作用：來自邊界的斥力FiB；來自網格節點的引力FiD；來自其他節點uj的引力或斥力Fij。Fij大小由兩個節點ui與uj之間的距離決定。設置距離閾值為dmax，節點ui所受到的合力Fi為

(4)

(5)

式中dij為節點ui與節點uj之間的歐氏距離；αij為從節點ui到節點uj的方向角；ta和tr分別為引力和斥力的系數，當兩個節點之間的距離小于閾值dmax時，受到斥力；大于閾值時，受到引力；等于閾值時，受到的力為0。

根據牛頓力學定律，節點受力后，會產生加速度

(6)

式中ai為傳感器節點ui的加速度;mi為傳感器節點ui的質量。

傳感器節點ui的運動速度為

vi=aiti

(7)

在相同的時間間隔中，節點的運動距離di正比于加速度ai的值

(8)

根據傳統虛擬力算法的實現過程可知，理想情況下，如果2個節點之間的距離十分近，會產生非常大的斥力，導致節點移動速度較快。但在實際應用中，每個節點的移動速度有最高速度限制，且速度值vi通常為常數，即

vi=max_step

(9)

傳感器節點ui的速度值，即為每次迭代節點的移動步長μi

μi=vi

(10)

可知傳統方法易導致迭代效果達到了最佳后，繼續迭代，后期穩定性下降。因此，需要對步長選取進行調整。

根據文獻[10]的分析，改進的LMS算法的步長函數調整方式如下：在初始收斂階段，步長應較大，以便有較快的收斂速度和對時變系統的跟蹤速度，在算法收斂后，應保持很小的調整步長以達到很小的穩態誤差，獲得較好的穩定性。步長的變化趨勢應隨時間或者迭代次數的增加而減少，減小的幅度應越來越大，直至最后趨近于0。

文獻[5]根據sigmoid函數提出了改變步長因子μi的設想：μi為e(t)的sigmoid函數

(11)

式中α為控制sigmoid函數的常數，決定曲線上升的速度；β為控制sigmoid函數取值范圍的常數；t為迭代次數；e(t)為每次迭代的誤差，即每次迭代的覆蓋空洞率。μ(t)與e(t)的函數曲線如圖1所示。

圖1 e(t)與μ(t)的關系曲線

可知，隨著e(t)減小，μ(t)隨之減小，且減小的幅度由小變大。可實現對傳統虛擬力算法缺陷的彌補，在收斂達到一定程度后，使最終結果趨于穩定。

3 仿真實驗與結果分析

通過仿真實驗驗證算法對提高傳統虛擬力算法后期穩定性的有效性，并對算法性能進行對比分析，包括收斂性能、覆蓋率。通過引入基于sigmoid變步長函數對節點的移動速度進行干預，提高了節點后期的覆蓋效果的穩定性，同時提高了迭代前期的收斂速度。并與線性函數變步長和二次函數變步長算法進行了對比分析。仿真實驗參數設置如表1所示。

表1 仿真實驗參數

根據傳感節點感知模型和監測區域的建立，任意一個無線傳感器節點均可以部署到任何一個被劃分的網格點上，實現監測區域覆蓋率量化，用比值q表示評價WSNs節點部署性能優劣的目標函數，即

q=sum/K

(12)

式中sum為被覆蓋的網絡點數；K為總網絡點數。

本文設計了3種變步長的函數進行對比分析，分別為線性函數、二次函數和基于sigmoid函數的變步長函數。

仿真初始階段，傳感器節點隨機分布于監測區域。分別在傳統的虛擬力算法、線性函數變步長的虛擬力算法、二次函數變步長的虛擬力算法和基于sigmoid函數變步長的虛擬力算法的作用下，分別進行位置更新。

定義線性變步長的虛擬力算法的步長函數為

μL(t)=aLt+bL

(13)

式中aL，bL分別為線性函數的參數。

定義二次函數變步長的虛擬力算法的步長函數為

μQ(t)=aQt2+bQ

(14)

式中aQ，bQ分別為二次函數的參數。

定義sigmoid函數變步長的虛擬力算法的步長函數為

(15)

式中aS，bS分別為基于sigmoid函數變步長函數的參數。

各自選取最優參數，進行仿真實驗。

傳統虛擬力算法仿真結果如圖2所示。線性函數變步長、二次函數變步長和基于sigmoid函數變步長的虛擬力算法仿真結果如圖3所示。

圖2 傳統虛擬力作用情況

圖3 變步長函數覆蓋情況

如圖4所示，傳統虛擬力算法后期的覆蓋率數據不穩定。線性變步長的虛擬力算法可以加快收斂速度，用了比較少的迭代次數即達到了最佳覆蓋率，效果比傳統虛擬力算法好很多。二次函數變步長的虛擬力算法，收斂速度較傳統虛擬力算法快，但其不穩定性較傳統虛擬力算法更大；可以明顯看出：基于sigmoid函數的變步長虛擬力算法的收斂速度最快，迭代效果最佳，后期結果的穩定性提高。4種函數性能指標如表2所示。

圖4 覆蓋率變化過程對比

性能指標傳統函數線性函數二次函數基于sigmoid函數覆蓋率最優值/%94．4595．3695．3595．89迭代次數89．0054．00115．0087．00覆蓋率最差值/%92．7994．8394．6995．09均值91．7295．1095．0595．60方差值0．04440．00150．00160．0022

可知：雖然基于sigmoid函數的變步長虛擬力算法達到覆蓋率最優時迭代次數不是最少，穩定性與線性函數和二次函數變步長相比略差一點，但其覆蓋效果最好。與傳統虛擬力算法相比，覆蓋率均值提高了4.23 %，覆蓋率最優值提高了1.52 %，穩定性提高了95.05 %。基于sigmoid函數的變步長虛擬力算法在保證收斂速度的同時，有效提高了覆蓋率，并且極大地提高了后期穩定性。

4 結 論

提出了變步長改進的虛擬力算法。在建立的監測模型基礎上，通過借鑒LMS自適應濾波算法中變步長函數，研究了線性函數、二次函數和基于sigmoid函數的變步長虛擬力算法對覆蓋效果的改進情況。通過仿真結果比較發現，基于sigmoid函數變步長的改進算法效果最好，與傳統虛擬力算法相比，在保證收斂速度的同時，極大地提高了后期階段的數據穩定性。

參考文獻:

[1] 李雙明，武慶威.采用RSSI提高無線傳感器網絡定位精度的算法[J].無線電工程，2015,45(2)：8-10.

[2] 毛科技，徐 慧，方 凱，等.基于虛擬力的WSNs路由協議設計與實現[J].傳感器與微系統，2017,47(12)：98-101.

[3] 劉 軍.基于虛擬力算法的 WMSNs覆蓋研究[J].傳感器與微系統,2016,35(11):74-76.

[5] Khoufi I,Minet P,Laouiti A.OA-DVFA:A distributed virtual forces-based algorithm to monitor an area with unknown obstacle-s[C]∥IEEE Consumer Communications & Networking Confe-rence,IEEE,2016:1036-1041.

[6] Li Y,Zhang B,Chai S.An energy balanced-virtual force algo-rithm for Mobile-WSNs[C]∥IEEE International Conference on Mechatronics and Automation,IEEE,2015:1779-1784.

[7] 覃景繁,歐陽景正.一種新的變步長LMS自應用濾波算法[J].數據采集與處理,1997,12(3):171-174.

[8] Zou Y,Chakrabarty K.Sensor deployment and target localization based on virtual forces[C]∥The Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,INFOCOM 2003,IEEE Societies,IEEE,2003:1293-1303.

[9] 張 濤,余翔宇,藍俊健,等.改進的無線傳感器網絡節點虛擬力部署方法[J].計算機應用研究,2015,32(11):3356-3358.

[10] 孟小猛. 自適應濾波算法研究及應用[D].北京:北京郵電大學,2010.