基于測距和灰狼優化的無線傳感器網絡定位算法*

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

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

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

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

1 定位算法模型建立

1.1 RSSI信號衰減模型

采用對數-常態分布[5]無線信號傳播模型:

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

(1)

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

(2)

1.2 未知節點初步定位估計

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

1.2.1 定位數學模型建立

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

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

區域1:P位于3個信標節點A、B、C構成的三角形△ABC區域內;

區域2:P位于∠BAC包含的區域除去△ABC區域剩余的區域及∠BAC對頂角包含的區域內;

區域3:P位于∠ACB包含的區域除去△ABC區域剩余的區域及∠ACB對頂角包含的區域內;

區域4:P位于∠ABC包含的區域除去△ABC區域剩余的區域及∠ABC對頂角包含的區域內。

圖1 節點區域分布圖

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

圖2 節點定位模型示意圖

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

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

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

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

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

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

區域3即將區域2的A換成C,B換成A,C換成B。區域4即將區域2的A換成B,B換成C,C換成A。即區域3和區域4的求法和區域2相同。設直線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)的最小值對應的坐標作為改進灰狼算法的初始值,i的取值為1～4。

(16)

2 改進灰狼優化算法

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

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

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

(17)

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

(18)

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

A=2a·r1-a

(19)

C=2·r2

(20)

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

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

(21)

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

(22)

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

本文對灰狼優化算法的改進如下:

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

②針對收斂因子進行改進。灰狼優化算法在搜索過程中是非線性變化的,收斂因子a隨迭代次數線性遞減策略不符合實際優化搜索過程。

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

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

(23)

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

(24)

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

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

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

(25)

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

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

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

(26)

利用改進灰狼算法對未知節點P的估計坐標值優化的方法是:

步驟1:初始化,t=0,t為當前迭代次數,N為種群大小。若k≥N,則根據適應度值從小到大選取前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:計算每個位置的適應度函數值。

(27)

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

步驟3:搜索位置更新。灰狼的獵捕階段。根據式(19)～式(22)、式(25)更新位置。

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

步驟5:若t>tmax,tmax為最大迭代次數,停止搜索,否則轉至步驟2.

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

基于LOGGWO的定位步驟如下:

步驟1:在網絡拓撲中隨機分布100個傳感器節點,包含信標節點和n個未知節點;

步驟2:將未知節點接收到的信標節點的信號強度轉化成距離值;

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

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

步驟5:初始化種群,對未知節點尋優定位。

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

(28)

(29)

若i≠n,i=i+1,跳轉至步驟3。

4 仿真

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

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

圖3 通信半徑R=30 m時,平均定位誤差 與信標節點比例關系比較圖

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

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

圖5 未知節點定位誤差比較圖

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

圖6 未知節點定位誤差比較圖

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

圖7 未知節點定位誤差比較圖

5 結束語

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