基于測距和灰狼優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法*

段亞青,王華倩,喬學工*

(1.太原理工大學信息與計算機學院,太原 030024;2.華北電力大學電氣與電子工程學院,北京 102206)

無線傳感器網(wǎng)絡(luò)[1]WSN(Wireless Sensor Networks)是一種由大量部署在預(yù)定區(qū)域內(nèi)的傳感器節(jié)點組成的自組織網(wǎng)絡(luò),可以對部署區(qū)域進行監(jiān)控,實時給用戶傳回有效信息。節(jié)點定位技術(shù)是WSN的關(guān)鍵基礎(chǔ)技術(shù)之一[2],廣泛的應(yīng)用在醫(yī)療衛(wèi)生、火災(zāi)監(jiān)控、環(huán)境檢測等方面,越來越多的應(yīng)用對定位精度提出了更高的要求。位置信息是對網(wǎng)絡(luò)中突發(fā)事件進行事前預(yù)警、事中決策以及事后處理的前提。

節(jié)點定位技術(shù)分類標準有很多種方法,其中基于測距定位技術(shù)和非測距定位技術(shù)是最常用的分類標準。接收信號強度指標RSSI(Received Signal Strength Indicator)是一種基于測量距離的定位算法,它利用信號在傳播過程中的衰減強度來計算未知節(jié)點和信標節(jié)點之間的距離,再利用三邊測量法計算未知節(jié)點的坐標,RSSI測距無需額外硬件[3],成本低、能耗低、實現(xiàn)簡單,所以基于RSSI的節(jié)點定位算法是一個研究熱門。智能算法為許多無法直接使用數(shù)學方法求解的優(yōu)化問題提供了新的解決思路,為了提高定位精度,研究學者將智能算法應(yīng)用在節(jié)點定位算法中。在文獻[4]中,提出了模擬退火定位算法,即將模擬退火算法用于節(jié)點定位算法當中,這是在早期嘗試把定位問題轉(zhuǎn)化為優(yōu)化問題的研究之一,但該方法計算量大且定位精度不高。文獻[5]中提出了IRSSI測距方法,對未知節(jié)點進行定位,為了使節(jié)點坐標更加準確,采用粒子群算法進行后期優(yōu)化。文獻[6]中針對經(jīng)典DV-Hop定位算法第3 階段計算未知節(jié)點位置存在較大誤差的問題,提出一種基于改進粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)定位方法,將定位問題轉(zhuǎn)化成未知節(jié)點坐標的優(yōu)化問題,采用改進粒子群算法進行坐標優(yōu)化。文獻[7]提出了一種基于帶有動態(tài)擾動項粒子群的無線傳感器網(wǎng)絡(luò)定位算法,一定程度上加快了算法收斂速度,提高了節(jié)點定位精度。將群體智能算法應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點定位中,可以提高定位精度[8-9],較為著名的有粒子群算法、遺傳算法、蟻群算法等,但群體智能算法存在易陷入局部最優(yōu)的缺陷,Mirjalili等人提出了一種新的群體智能算法——灰狼優(yōu)化算法(GWO)[10],GWO算法已被證明在求解精度和穩(wěn)定性上明顯優(yōu)于粒子群算法、差分進化算法、引力搜索算法。因此本文提出一種基于測距和改進灰狼優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法。定位分為兩個階段,粗略定位階段和精確定位階段。在粗略定位階段建立了基于3個信標節(jié)點的定位數(shù)學模型,本文對未知節(jié)點進行初步定位估計時應(yīng)用了公邊比例定理,該方法相比三邊測量法,降低了計算階數(shù),二次式變?yōu)橐淮问?簡化了計算;在精確定位階段使用改進灰狼算法優(yōu)化未知節(jié)點坐標值,灰狼優(yōu)化算法在搜索過程中是非線性變化的,基本灰狼優(yōu)化算法中收斂因子a是隨迭代次數(shù)線性遞減的,不符合實際優(yōu)化搜索過程,因此本文提出一種基于對數(shù)遞減策略的非線性動態(tài)變化收斂因子。仿真表明,本文算法具有較高的定位精度,并且具有對測距誤差魯棒性強的優(yōu)點。

1 定位算法模型建立

1.1 RSSI信號衰減模型

采用對數(shù)-常態(tài)分布[5]無線信號傳播模型:

PL(d)=PL(d0)-10nlg(d/d0)+Xσ

(1)

式中:d為未知節(jié)點與參考節(jié)點之間的距離;d0為參考距離,通常取值為1m。PL(d)、PL(d0)分別為在傳播距離為d和d0時的接收信號功率;當d0=1m時,PL(d0)=55 dBm。n為路徑損耗系,一般與環(huán)境相關(guān),取值為2～5;Xσ為均值為0,標準差為σ的高斯隨機變量,表示環(huán)境等因素對測距誤差的影響。n和Xσ的值是適應(yīng)本實驗環(huán)境下通過多次實驗選取確定的,在不同的實驗環(huán)境下需要重新設(shè)定。對式(1)兩邊同時取對數(shù),可以得到RSSI值與距離d之間的關(guān)系,可以表述為RSSI(d)=δ0-10nlgd+Xσ其中,RSSI(d)為未知節(jié)點收到的距離為d的信標節(jié)點的RSSI信號強度,δ0=10lgPr(d0)表示信號傳播距離為d0時接收信號功率。根據(jù)式(2)將信號強度值轉(zhuǎn)化成距離值:

(2)

1.2 未知節(jié)點初步定位估計

建立定位數(shù)學模型,利用該模型對未知節(jié)點進行初步定位估計,計算未知節(jié)點的坐標,通過距離差判別法獲取未知節(jié)點坐標。

1.2.1 定位數(shù)學模型建立

未知節(jié)點接收到至少3個不共線信標節(jié)點的位置信息才能通過三邊測量法進行自身位置估計。借鑒此思想建立通過3個信標節(jié)點的坐標,獲取未知節(jié)點坐標的定位數(shù)學模型。

如圖1所示,A、B、C是3個信標節(jié)點,P是未知節(jié)點,其位置均隨機分布,P點相對3個信標節(jié)點構(gòu)成的△ABC其分布存在4種情況:

區(qū)域1:P位于3個信標節(jié)點A、B、C構(gòu)成的三角形△ABC區(qū)域內(nèi);

區(qū)域2:P位于∠BAC包含的區(qū)域除去△ABC區(qū)域剩余的區(qū)域及∠BAC對頂角包含的區(qū)域內(nèi);

區(qū)域3:P位于∠ACB包含的區(qū)域除去△ABC區(qū)域剩余的區(qū)域及∠ACB對頂角包含的區(qū)域內(nèi);

區(qū)域4:P位于∠ABC包含的區(qū)域除去△ABC區(qū)域剩余的區(qū)域及∠ABC對頂角包含的區(qū)域內(nèi)。

圖1 節(jié)點區(qū)域分布圖

3個信標節(jié)點求未知節(jié)點坐標的解法示意圖,如圖2所示。

圖2 節(jié)點定位模型示意圖

設(shè)A、B、C是3個信標節(jié)點,P為未知節(jié)點,設(shè)P的坐標是(xp,yp),A′是直線PA與直線BC的交點、B′是直線AC與直線BP的交點、C′是直線BC與直線PC的交點。3個信標節(jié)點到P的測量距離分別是LAP、LBP、LCP。kBC是直線BC的斜率。下列式子中的G1、G2、G3為區(qū)域系數(shù),與P點所在區(qū)域有關(guān)。

①當P位于區(qū)域1時,公邊比例定理可得:

由直線PA與直線BC交于A′,有:

(3)

則A′點的坐標可以表示為:

(4)

直線PB與直線AC交與B′,有:

(5)

則B′點的坐標可以表示為:

(6)

直線PC與直線AB交于C′,有:

(7)

則C′點的坐標可以表示為:

(8)

②當P位于區(qū)域2時,公邊比例定理可得:

直線PA與直線BC交于A′,有:

(9)

則A′點的坐標可以表示為:

(10)

同理直線PB與直線AC交與B′,有:

(11)

則B′點的坐標可以表示為:

(12)

同理直線PC與直線AB交于C′,有:

(13)

則C′點的坐標可以表示為:

(14)

區(qū)域3即將區(qū)域2的A換成C,B換成A,C換成B。區(qū)域4即將區(qū)域2的A換成B,B換成C,C換成A。即區(qū)域3和區(qū)域4的求法和區(qū)域2相同。設(shè)直線AA′與直線BB′的交點為(xp1,yp1),直線AA′和直線CC′的交點為(xp2,yp2),直線BB′和直線CC′的交點為(xp3,yp3)。

1.2.2 距離差判別法

(15)

分別計算(xp1,yp1)、(xp2,yp2) 、(xp3,yp3)、(xp4,yp4)的距離差值d,取d(i)的最小值對應(yīng)的坐標作為改進灰狼算法的初始值,i的取值為1～4。

(16)

2 改進灰狼優(yōu)化算法

為了從數(shù)學上對狼的社會等級進行建模,在設(shè)計GWO時,將最佳的解決方案視為alpha(α),因此,第2個和第3個最佳解決方案被分別視為beta(β)和delta(δ),剩下的候選方案視為omega(ω),在GWO算法中狩獵(優(yōu)化)是由α、β和δ引導(dǎo)的,ω跟隨其他3種狼。

灰狼群狩獵過程的第1步是灰狼群接近并包圍獵物。其數(shù)學表達為:

D=|C·XP(t)-X(t)|

(17)

X(t+1)=XP(t)-A·D

(18)

式中:t表示當前迭代的次數(shù),XP是獵物的位置,X(t)是灰狼的位置。D表示包圍步長。A和C為系數(shù)向量,分別由式(19)和式(20)計算得出:

A=2a·r1-a

(19)

C=2·r2

(20)

r1和r2是[0,1]之間的隨機向量;收斂因子a為控制參數(shù),隨著迭代次數(shù)從2線性遞減到0。

在獵捕階段,其他ω灰狼個體根據(jù)α的當前位置Xα、β的當前位置Xβ和δ的當前位置Xδ來更新各自的位置,由式(21)和式(22)表示,式(21)表示ω灰狼朝向α、β、δ灰狼的前進步長和方向:

(21)

X(t+1)=(X1+X2+X3)/3

(22)

最后,攻擊階段,在此階段根據(jù)A和C的值來控制探索和開發(fā)過程。在迭代過程中,收斂因子a是逐漸減小的,A的波動范圍隨著a的減小而減小,A是[-a,a]內(nèi)的一個隨機值,當|A|≤1時,灰狼群向著獵物攻擊,以實現(xiàn)局部搜索,當|A|>1,灰狼群體遠離獵物,以加強算法的探索能力實現(xiàn)全局搜索。從式(20)可以看出C在整個迭代過程中都是一個隨機量,C的隨機性是為了隨機的強化或弱化獵物在定義的距離方程中的影響,并且在最后的迭代過程中一直加強搜索,可以避免陷入局部最優(yōu)。

本文對灰狼優(yōu)化算法的改進如下:

①灰狼優(yōu)化算法的初始化種群個體是隨機產(chǎn)生的,在一定程度上不能保證初始化種群的多樣性,導(dǎo)致優(yōu)化結(jié)果精度不高。本文算法的初始點是由定位數(shù)學模型計算出的初步定位結(jié)果以及離未知節(jié)點最近的信標節(jié)點的坐標產(chǎn)生,縮小了可行解空間,減小了計算量,同時加快了收斂速度。

②針對收斂因子進行改進?；依莾?yōu)化算法在搜索過程中是非線性變化的,收斂因子a隨迭代次數(shù)線性遞減策略不符合實際優(yōu)化搜索過程。

文獻[11]提出了基于余弦函數(shù)(記為COSGWO)和二次函數(shù)(記為2GWO)的非線性動態(tài)變化收斂因子更新方法,更新公式為式(23)、式(24),仿真結(jié)果表明優(yōu)于基本GWO,且基于余弦函數(shù)和二次函數(shù)的收斂因子非線性動態(tài)變化效果接近。

at=(ainitial-afinal)×cos(t/tmax)

(23)

at=ainitial-(ainitial-afinal)×(t/tmax)2

(24)

式中:ainitial和afinal分別是a的初始值和終值,t為當前迭代次數(shù),tmax為最大迭代次數(shù)。

算法要求:在前期有較高的全局搜索能力以得到合適的位置,找到合適的位置后,a值能迅速減小進入局部搜索以加快收斂速度,在后期要求有較高的局部開發(fā)能力,以提高算法收斂精度。本文提出一種基于對數(shù)遞減策略的非線性動態(tài)變化收斂因子更新公式:

at=ainitial-μ×(ainitial-afinal)×logtmaxt

(25)

式中:ainitial和afinal分別是a的初始值和終值。μ是對數(shù)調(diào)整因子,0<μ<1稱為對數(shù)壓縮因子,算法的搜索范圍相對上移;μ>1稱為對數(shù)膨脹因子,算法的搜索范圍相對下移。μ=1,最后a收斂于afinal,本文中μ=1。μ越小,a遞減越慢,在算法的后期可以進行更精細的局部搜索。在實際應(yīng)用中,對不同的優(yōu)化問題可以適當?shù)恼{(diào)整μ的值。

3 基于改進灰狼優(yōu)化(LOGGWO)的定位算法

設(shè)P點可以接收到m個信標節(jié)點的信號,將m個信標節(jié)點以3個不共線的為一組分組,假設(shè)一共有k組。通過第1部分的數(shù)學模型可以計算出k個P點的坐標值,分別是(xP1,yP1),…,(xPk,yPk)。這k個坐標值即LOGGWO算法的部分初始值,通過算法尋優(yōu)得到未知節(jié)點P的優(yōu)化坐標。設(shè)改進灰狼優(yōu)化算法的種群大小為N。若k≥N,則選用根據(jù)適應(yīng)度值從小到大選取前N個作為初始值;若k

(26)

利用改進灰狼算法對未知節(jié)點P的估計坐標值優(yōu)化的方法是:

步驟1:初始化,t=0,t為當前迭代次數(shù),N為種群大小。若k≥N,則根據(jù)適應(yīng)度值從小到大選取前N個作為初始值將(xP1,yP1),(xP2,yP2),…,(xPi,yPi),…,(xPN,yPN)賦值給(xW1(t),yW1(t)),…,(xWi(t),yWi(t)),…,(xWN(t),yWN(t)),i的取值為1～N;若k

步驟2:計算每個位置的適應(yīng)度函數(shù)值。

(27)

式中:(xj,yj)是第j個信標節(jié)點的坐標,dij是灰狼i與信標節(jié)點j之間的距離,m是可以與i相互通信的信標節(jié)點數(shù),所以j的取值是1～m。將個體按適應(yīng)函數(shù)值從小到大排序,排在第1位的個體設(shè)為alpha(α),排在第2位的個體設(shè)為beta(β),排在第3位的個體設(shè)為delta(δ)。

步驟3:搜索位置更新?；依堑墨C捕階段。根據(jù)式(19)～式(22)、式(25)更新位置。

步驟4:計算適應(yīng)度函數(shù),更新α、β、δ個體的位置,令t=t+1。

步驟5:若t>tmax,tmax為最大迭代次數(shù),停止搜索,否則轉(zhuǎn)至步驟2.

LOGGWO算法的時間復(fù)雜度計算如下:計算種群中每個個體的適應(yīng)度值的時間復(fù)雜度為O(N),N為種群規(guī)模;個體位置更新操作的時間復(fù)雜度為O(N2+klogn);群體循環(huán)迭代的時間復(fù)雜度為O(N2),所以,LOGGWO算法的時間復(fù)雜度為O(N2)。

基于LOGGWO的定位步驟如下:

步驟1:在網(wǎng)絡(luò)拓撲中隨機分布100個傳感器節(jié)點,包含信標節(jié)點和n個未知節(jié)點;

步驟2:將未知節(jié)點接收到的信標節(jié)點的信號強度轉(zhuǎn)化成距離值;

步驟3:計算第i(i的取值為1～n)個未知節(jié)點可以接收到信標節(jié)點的個數(shù),記作m,若m<1,則此未知節(jié)點無法定位,跳轉(zhuǎn)至步驟6;若0

步驟4:將第i個未知節(jié)點可以接收到的m個信標節(jié)點分組,每3個不共線的信標節(jié)點為一組,假設(shè)一共有k組,運用本文提出的數(shù)學模型計算出該未知節(jié)點的坐標:(xW1,yW1),…,(xWk,yWk)。

步驟5:初始化種群,對未知節(jié)點尋優(yōu)定位。

步驟6:若i=n,算法結(jié)束,計算定位誤差:其中EROi表示每個未知節(jié)點的定位誤差;平均定位誤差用節(jié)點通信半徑歸一化后的相對定位誤差表示,EROAVE表示平均定位誤差,(xR(i),yR(i))和(xE(i),yE(i))分別表示第i個未知節(jié)點的實際坐標和估計坐標,n表示未知節(jié)點總數(shù)。

(28)

(29)

若i≠n,i=i+1,跳轉(zhuǎn)至步驟3。

4 仿真

為了驗證算法的有效性,本文采用MATLAB進行仿真。在邊長為100 m的正方形區(qū)域隨機分布100個傳感器節(jié)點,其中包含信標節(jié)點,本文所用算法的種群規(guī)模均為30,最大迭代次數(shù)均為300,通信半徑為30 m,信標節(jié)點所占比例為30%,RSSI信號衰減模型中的Xσ的標準差取值為8。與同類COSGWO算法[11]、GWO算法相比較來驗證本文對灰狼算法改進方法的有效性,并與已有的定位算法DPSO[12]和基于測距的三邊定位算法相比較,驗證本文定位算法的有效性。

從圖3可以看出,隨著信標節(jié)點數(shù)的增加,平均定位誤差降低,這是因為信標節(jié)點數(shù)目增加使網(wǎng)絡(luò)中未知節(jié)點的鄰居信標節(jié)點數(shù)目增加,未知節(jié)點可以獲得更多的位置參考信息,定位誤差減小。本文定位算法平均定位誤差始終保持最小,表明本文改進算法優(yōu)于其他定位算法,驗證了本文灰狼算法改進方法的有效性以及本文定位算法的有效性。信標節(jié)點的成本比較高,信標節(jié)點的數(shù)量直接影響整個網(wǎng)絡(luò)的成本。本文定位算法當信標節(jié)點所占比例大于30%以后,平均定位誤差變化趨于平緩,在相同定位誤差下,本文算法需要的信標節(jié)點的數(shù)目較少,能有效的節(jié)省網(wǎng)絡(luò)成本。

圖3 通信半徑R=30 m時,平均定位誤差 與信標節(jié)點比例關(guān)系比較圖

從圖4可以看出,隨著通信半徑的增加,網(wǎng)絡(luò)連通性提高,所以各算法的平均定位誤差均降低,本文定位算法平均定位誤差始終保持最小,優(yōu)于其他算法。可以看出在相同的定位誤差下,本文算法所需要的通信半徑最小,通信半徑越小,能耗越小,在同等條件下,本文算法可以節(jié)約能耗,延長網(wǎng)絡(luò)壽命,降低網(wǎng)絡(luò)維護成本。

圖4 信標節(jié)點所占比例為30%時,平均定位誤差 與通信半徑關(guān)系比較圖

圖5 未知節(jié)點定位誤差比較圖

圖5和圖6是基于改進灰狼優(yōu)化定位算法、基于COSGWO定位算法、基于GWO定位算法的未知節(jié)點定位誤差對比圖。仿真條件是:圖5中RSSI的Xσ的標準差取值為4,圖6中RSSI的Xσ的標準差取值為8,信標節(jié)點所占比例為30%,通信半徑為30 m。圖5和圖6都是由仿真50次后的平均值得到的結(jié)果圖?？梢钥闯?本文定位算法相比基于COSGWO的定位算法和基于GWO的定位算法定位精度更高。Xσ高斯隨機噪聲,表示環(huán)境等因素對測距誤差的影響,均值為0,標準差為σ,測距誤差會隨著標準差σ的增加而增大,對比圖5和圖6可以看出隨著σ增大(測距誤差的增大),未知節(jié)點定位誤差整體增大,但本文算法未知節(jié)點定位誤差整體依舊保持最小,精度依然很高,可見本文定位算法對測距誤差的抗干擾能力更強,具有更高的實用性。

圖6 未知節(jié)點定位誤差比較圖

圖7是本文定位算法與已有的文獻[12]提出的DPSO定位算法和基于測距的三邊定位算法的未知節(jié)點定位誤差對比圖。仿真條件是:RSSI的Xσ的標準差取值為8,信標節(jié)點所占比例為30%,通信半徑為30 m。圖7是由仿真50次后的平均值得到的結(jié)果圖。從圖中可以看出本文定位算法未知節(jié)點的平均定位誤差最低,優(yōu)于DPSO定位算法和基于測距的三邊定位算法。本文定位算法在粗略定位階段建立定位數(shù)學模型,是一種基于測距的未知節(jié)點坐標估計方法,本文定位數(shù)學模型均為一次等式,和三邊測量法相比,降低了計算階數(shù),簡化了計算。

圖7 未知節(jié)點定位誤差比較圖

5 結(jié)束語

本文提出了一種基于測距和改進灰狼優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法,在初步定位階段提出了一種定位數(shù)學模型,實現(xiàn)對未知節(jié)點的初步定位估計;在精確定位階段用具有較強平衡局部搜索和全局搜索能力的灰狼優(yōu)化算法進行尋優(yōu)定位。本文中灰狼算法的初始化搜索種群是初步定位估計值,縮小了可行解空間,減小了計算量,同時加快了收斂速度;并將收斂因子a非線性化,更符合實際優(yōu)化搜索過程,能動態(tài)平衡局部搜索和全局搜索能力。仿真實驗表明,本文算法相比一些已有定位算法,有效提高了定位精度,同等條件下,降低了網(wǎng)絡(luò)成本,節(jié)省能耗,可延長網(wǎng)絡(luò)壽命,并且具有對測距誤差魯棒性強的優(yōu)點。