一種優(yōu)化WSNs節(jié)點部署的變步長虛擬力算法*

張俏薇， 陳俊杰

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

0 引 言

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

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

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

1 節(jié)點感知模型

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

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

(1)

式中K為網(wǎng)格點的數(shù)目，需要根據(jù)監(jiān)測區(qū)域的目標(biāo)和測量精度要求確定。

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

(2)

2 基于sigmoid函數(shù)的變步長虛擬力算法

在監(jiān)測區(qū)域，將n個移動傳感器節(jié)點隨機(jī)分布在L×W的大面積目標(biāo)區(qū)域，記為集合U

U=[u1,u2,…,un]

(3)

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

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

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

(4)

(5)

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

根據(jù)牛頓力學(xué)定律，節(jié)點受力后，會產(chǎn)生加速度

(6)

式中ai為傳感器節(jié)點ui的加速度;mi為傳感器節(jié)點ui的質(zhì)量。

傳感器節(jié)點ui的運動速度為

vi=aiti

(7)

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

(8)

根據(jù)傳統(tǒng)虛擬力算法的實現(xiàn)過程可知，理想情況下，如果2個節(jié)點之間的距離十分近，會產(chǎn)生非常大的斥力，導(dǎo)致節(jié)點移動速度較快。但在實際應(yīng)用中，每個節(jié)點的移動速度有最高速度限制，且速度值vi通常為常數(shù)，即

vi=max_step

(9)

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

μi=vi

(10)

可知傳統(tǒng)方法易導(dǎo)致迭代效果達(dá)到了最佳后，繼續(xù)迭代，后期穩(wěn)定性下降。因此，需要對步長選取進(jìn)行調(diào)整。

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

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

(11)

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

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

可知，隨著e(t)減小，μ(t)隨之減小，且減小的幅度由小變大?？蓪崿F(xiàn)對傳統(tǒng)虛擬力算法缺陷的彌補(bǔ)，在收斂達(dá)到一定程度后，使最終結(jié)果趨于穩(wěn)定。

3 仿真實驗與結(jié)果分析

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

表1 仿真實驗參數(shù)

根據(jù)傳感節(jié)點感知模型和監(jiān)測區(qū)域的建立，任意一個無線傳感器節(jié)點均可以部署到任何一個被劃分的網(wǎng)格點上，實現(xiàn)監(jiān)測區(qū)域覆蓋率量化，用比值q表示評價WSNs節(jié)點部署性能優(yōu)劣的目標(biāo)函數(shù)，即

q=sum/K

(12)

式中sum為被覆蓋的網(wǎng)絡(luò)點數(shù)；K為總網(wǎng)絡(luò)點數(shù)。

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

仿真初始階段，傳感器節(jié)點隨機(jī)分布于監(jiān)測區(qū)域。分別在傳統(tǒng)的虛擬力算法、線性函數(shù)變步長的虛擬力算法、二次函數(shù)變步長的虛擬力算法和基于sigmoid函數(shù)變步長的虛擬力算法的作用下，分別進(jìn)行位置更新。

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

μL(t)=aLt+bL

(13)

式中aL，bL分別為線性函數(shù)的參數(shù)。

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

μQ(t)=aQt2+bQ

(14)

式中aQ，bQ分別為二次函數(shù)的參數(shù)。

定義sigmoid函數(shù)變步長的虛擬力算法的步長函數(shù)為

(15)

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

各自選取最優(yōu)參數(shù)，進(jìn)行仿真實驗。

傳統(tǒng)虛擬力算法仿真結(jié)果如圖2所示。線性函數(shù)變步長、二次函數(shù)變步長和基于sigmoid函數(shù)變步長的虛擬力算法仿真結(jié)果如圖3所示。

圖2 傳統(tǒng)虛擬力作用情況

圖3 變步長函數(shù)覆蓋情況

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

圖4 覆蓋率變化過程對比

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

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

4 結(jié) 論

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

參考文獻(xiàn):

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

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

[3] 劉 軍.基于虛擬力算法的 WMSNs覆蓋研究[J].傳感器與微系統(tǒng),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自應(yīng)用濾波算法[J].數(shù)據(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] 張 濤,余翔宇,藍(lán)俊健,等.改進(jìn)的無線傳感器網(wǎng)絡(luò)節(jié)點虛擬力部署方法[J].計算機(jī)應(yīng)用研究,2015,32(11):3356-3358.

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