張俏薇， 陳俊杰

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

0 引 言

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

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

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

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

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

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

(1)

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

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

(2)

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

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

U=[u1,u2,…,un]

(3)

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

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

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

(4)

(5)

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

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

(6)

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

傳感器節(jié)點(diǎn)ui的運(yùn)動(dòng)速度為

vi=aiti

(7)

在相同的時(shí)間間隔中，節(jié)點(diǎn)的運(yùn)動(dòng)距離di正比于加速度ai的值

(8)

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

vi=max_step

(9)

傳感器節(jié)點(diǎn)ui的速度值，即為每次迭代節(jié)點(diǎn)的移動(dòng)步長(zhǎng)μi

μi=vi

(10)

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

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

文獻(xiàn)[5]根據(jù)sigmoid函數(shù)提出了改變步長(zhǎng)因子μ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)隨之減小，且減小的幅度由小變大?？蓪?shí)現(xiàn)對(duì)傳統(tǒng)虛擬力算法缺陷的彌補(bǔ)，在收斂達(dá)到一定程度后，使最終結(jié)果趨于穩(wěn)定。

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

表1 仿真實(shí)驗(yàn)參數(shù)

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

q=sum/K

(12)

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

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

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

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

μL(t)=aLt+bL

(13)

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

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

μQ(t)=aQt2+bQ

(14)

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

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

(15)

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

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

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

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

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

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

圖4 覆蓋率變化過(guò)程對(duì)比

性能指標(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ù)的變步長(zhǎng)虛擬力算法達(dá)到覆蓋率最優(yōu)時(shí)迭代次數(shù)不是最少，穩(wěn)定性與線性函數(shù)和二次函數(shù)變步長(zhǎng)相比略差一點(diǎn)，但其覆蓋效果最好。與傳統(tǒng)虛擬力算法相比，覆蓋率均值提高了4.23 %，覆蓋率最優(yōu)值提高了1.52 %，穩(wěn)定性提高了95.05 %。基于sigmoid函數(shù)的變步長(zhǎng)虛擬力算法在保證收斂速度的同時(shí)，有效提高了覆蓋率，并且極大地提高了后期穩(wěn)定性。

4 結(jié) 論

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

參考文獻(xiàn):

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

[2] 毛科技，徐 慧，方 凱，等.基于虛擬力的WSNs路由協(xié)議設(shè)計(jì)與實(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] 覃景繁,歐陽(yáng)景正.一種新的變步長(zhǎng)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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)虛擬力部署方法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(11):3356-3358.

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