基于RSSI的灰狼優(yōu)化差分修正質(zhì)心定位算法

高 棟， 胡黃水， 王宏志， 余學(xué)帆

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

0 引 言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network， WSN)是由眾多體積小、低成本、功耗低的傳感器節(jié)點通過無線通信技術(shù)相互聯(lián)系而形成的網(wǎng)絡(luò)[1],已被運用到眾多領(lǐng)域，而能夠確定采集數(shù)據(jù)的準(zhǔn)確位置作為傳感器網(wǎng)絡(luò)基本功能之一也顯得尤為重要。

基于RSSI的定位算法是無線傳感器網(wǎng)絡(luò)定位算法中應(yīng)用比較廣泛的一種，也是研究的熱點之一[2]。而智能優(yōu)化算法在質(zhì)心計算的基礎(chǔ)上，通過群體尋優(yōu)思想為未知節(jié)點坐標(biāo)的求解提供了另一種思路。常見的群體智能優(yōu)化算法有遺傳算法、粒子群算法、蟻群算法[3-5]。這些群體智能優(yōu)化算法可以提高定位精度，相比而言，灰狼智能優(yōu)化算法(Grey Wolf Optimization, GWO)具有更好的優(yōu)化穩(wěn)定性和準(zhǔn)確性[6];文獻(xiàn)[7]提出用比例差分的方法對RSSI測距進(jìn)行修正，并且利用卡爾曼濾波法除去信號中的噪聲，以獲得更加精確的距離值;文獻(xiàn)[8]提出一種自適應(yīng)優(yōu)化粒子群的WSN定位算法，通過適應(yīng)度函數(shù)得到粒子適應(yīng)值，然后根據(jù)粒子適應(yīng)值調(diào)節(jié)慣性權(quán)重與學(xué)習(xí)因子，同時使用異步變化法改進(jìn)學(xué)習(xí)因子，但該算法難以解決跳出局部極值點問題;文獻(xiàn)[9]提出一種基于RSSI無線傳感器網(wǎng)絡(luò)改進(jìn)加權(quán)質(zhì)心算法，將距離比例模型引入錨節(jié)點圓中，以解決補(bǔ)位帶來的誤差累積;文獻(xiàn)[10]提出一種鯨魚優(yōu)化算法改進(jìn)的加權(quán)質(zhì)心算法，利用鯨魚優(yōu)化算法的快速收斂、不易陷入局部最優(yōu)等優(yōu)勢對加權(quán)質(zhì)心算法定位結(jié)果進(jìn)行優(yōu)化。

根據(jù)以上文獻(xiàn)方法，文中提出一種基于RSSI的灰狼優(yōu)化差分修正質(zhì)心定位算法(RSSI-based Gray Wolf Optimization Differential Correction Centroid Location Algorithm， GWO-RDCCL)，算法分為質(zhì)心估計以及節(jié)點定位兩個階段。在質(zhì)心估計階段通過無線通信模型構(gòu)建信標(biāo)節(jié)點與未知節(jié)點的距離公式，并由此計算信標(biāo)節(jié)點所對應(yīng)的質(zhì)心坐標(biāo)，通過差分修正因子對質(zhì)心坐標(biāo)進(jìn)行修正;在節(jié)點定位階段，將質(zhì)心坐標(biāo)作為灰狼優(yōu)化算法的初始值，縮小算法的搜索空間，以實現(xiàn)對未知節(jié)點的精確定位，并通過仿真實驗證明。

1 灰狼優(yōu)化算法

灰狼優(yōu)化算法由Seyedali Mirjalili等[6]提出，灰狼族群社會等級劃分如圖1所示。

圖1 灰狼社會等級劃分

族群內(nèi)的每個社會等級的權(quán)利、分工等都各不相同，處于最頂端階層的是α狼，它是整個族群的領(lǐng)導(dǎo)者，決定著狼群的休息地點、休息時間以及狩獵等日常活動。位于社會等級第二階層的是β狼，主要負(fù)責(zé)將α狼的命令以及決策傳達(dá)給其它階層的灰狼，幫助α狼統(tǒng)領(lǐng)下屬階層的灰狼，如果α狼年老或者死去，β狼是最有機(jī)會成為新的α狼。位于社會等級第三階層的是δ狼，主要負(fù)責(zé)偵查、狩獵等，此外，還有放哨狼、年老狼等，位于社會等級第四階層的是ω狼，在族群中的等級最低，但也是族群中不可缺少的，它可以有效減少族群內(nèi)部矛盾和維持族群內(nèi)的穩(wěn)定結(jié)構(gòu)。算法的優(yōu)化過程是由α狼、β狼、δ狼主導(dǎo)的，而ω狼跟隨主導(dǎo)的灰狼尋找最優(yōu)的結(jié)果。

1.1 搜捕過程

灰狼在狩獵的時候，從追蹤獵物到逐漸包圍獵物，灰狼位置移動方式如下：

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

(1)

X(t+1)=Xp(t)-A·D,

(2)

式中：t----迭代次數(shù);

X(t)----灰狼當(dāng)前位置;

XP(t)----被攻擊獵物位置;

D----灰狼與獵物距離。

A與C為系數(shù)向量，計算公式為：

A=2a·r1-a,

(3)

C=2·r2,

(4)

式中：r1,r2----隨機(jī)向量，取值范圍為[0,1];

a----收斂因子，其值隨著算法迭代的次數(shù)而從2線性遞減為0。

1.2 獵殺過程

在獵殺的過程中，主要是α狼、β狼、δ狼主導(dǎo)的，而ω狼會根據(jù)α狼的位置Xα、β狼的位置Xβ、δ狼的位置Xδ來更新自己的位置，其位置更新為

(5)

(6)

式中：X1----ω狼向α狼靠近的距離和方向;

X2----ω狼向β狼靠近的距離和方向;

X3----ω狼向δ狼靠近的距離和方向;

X(t+1)----ω狼在下一時刻的位置。

2 GWO-RDCCL算法

2.1 質(zhì)心差分修正

由于在現(xiàn)實環(huán)境中存在許多影響信號傳輸?shù)囊蛩兀@些因素都會使信號衰減，未知節(jié)點接收的信號強(qiáng)度存在波動，影響距離測量的準(zhǔn)確性，導(dǎo)致最終定位的結(jié)果精度不高。為提高數(shù)據(jù)可靠性，需要對未知節(jié)點接收的RSSI進(jìn)行預(yù)處理，使處理后的數(shù)值為第i個信標(biāo)節(jié)點RSSI的均值與RSSI的中值和的一半，公式為

(7)

式中：RSSIi----第i個信標(biāo)節(jié)點的RSSI預(yù)處理結(jié)果;

由處理后的RSSI測量未知節(jié)點與信標(biāo)節(jié)點的距離，將前三個距離構(gòu)建的三角形的質(zhì)心作為未知節(jié)點的參考節(jié)點[11]，通過參考節(jié)點與信標(biāo)節(jié)點的位置關(guān)系計算差分修正因子對質(zhì)心坐標(biāo)進(jìn)行修正，以提高定位精度。

將未知節(jié)點收到的RSSI值計算的距離升序排序，取前三個 {D1,D2,D3}，其對應(yīng)的信標(biāo)節(jié)點為A1、A2、A3，以節(jié)點為圓心，對應(yīng)距離為半徑畫圓，可得到三個圓的重合區(qū)域，質(zhì)心算法原理如圖2所示。

圖2 質(zhì)心算法原理

其中,重合區(qū)域的交點分別為O1、O2、O3，交點O1(xo1,yo1)的坐標(biāo)由下式可求,

(8)

同時,根據(jù)式(8)分別求出O2(xo2,yo2),O3(xo3,yo3)。并連接三個點得到△O1O2O3，然后通過下式求出其質(zhì)心M1(xm1,ym1)的坐標(biāo)，通過上述步驟可以求出其他質(zhì)心坐標(biāo)M2(xm2,ym2)，M3(xm3,ym3)，…，Mk(xmk,ymk)，k=n-2。

(9)

由于信標(biāo)節(jié)點A1、A2、A3離未知節(jié)點最近，則其質(zhì)心M1與未知節(jié)點的誤差相對于其他質(zhì)心更小，將得到的第一個質(zhì)心M1作為參考節(jié)點計算差分修正因子對質(zhì)心進(jìn)行修正。由下式計算差分修正因子δ,

(10)

式中：di----信標(biāo)節(jié)點與未知節(jié)點的距離;

d1i----信標(biāo)節(jié)點與質(zhì)心M1的距離。

利用差分修正因子對原質(zhì)心進(jìn)行修正，修正公式為

(11)

2.2 灰狼優(yōu)化質(zhì)心

假設(shè)未知節(jié)點O收到n個信標(biāo)節(jié)點的信號，按上文的質(zhì)心差分修正計算方法可以求出k(k=n-2)個質(zhì)心，質(zhì)心坐標(biāo)分別為M1(xm1,ym1),M2(xm2,ym2)，M3(xm3,ym3)，…，Mk(xmk,ymk)，k=n-2。將這k個質(zhì)心作為灰狼優(yōu)化算法的初始值，通過灰狼優(yōu)化算法估計未知節(jié)點的坐標(biāo)。假設(shè)灰狼優(yōu)化算法的族群數(shù)量為N，如果質(zhì)心數(shù)量k≥N，則通過質(zhì)心對應(yīng)的測量距離從小到大按順序選擇N個質(zhì)心作為灰狼群體的初始值；如果質(zhì)心數(shù)量k

(12)

式中：d----質(zhì)心M1與未知節(jié)點O的測量距離;

r----隨機(jī)數(shù)，取值范圍為[0,1]。

通過灰狼算法優(yōu)化質(zhì)心來估計未知節(jié)點坐標(biāo)的步驟為：

1)種群初始化。設(shè)置初始迭代次數(shù)t=0，設(shè)置種群大小N，如果k≥N，則根據(jù)質(zhì)心所對應(yīng)的三角形的排序取前N個作為灰狼種群的初始值，將M1(xm1,ym1),M2(xm2,ym2)，…，Mi(xmi,ymi)，…，MN(xmN,ymN)賦值給灰狼個體(xm1(t),ym1(t)),(xm2(t),ym2(t))，…，(xmi(t),ymi(t)),…，(xmN(t),ymN(t))，i取值為[1，N]；如果k

2)計算每個灰狼個體的適應(yīng)度函數(shù)值

(13)

式中：O=xm1(t)-xmj(t);

P=ym1(t)-ymj(t);

(xmj(t),ymj(t))----第j個灰狼個體的坐標(biāo);

dij----灰狼i與j的距離。

將灰狼個體的適應(yīng)度值按照升序排序，排在首位定義為α狼，排在第二位的定義為β狼，排在第三位的定義為δ狼。

3)更新灰狼位置。在灰狼攻擊階段，通過式(5)、式(6)更新灰狼的位置。

4)重新計算每個灰狼個體的適應(yīng)度函數(shù)，按照適應(yīng)度函數(shù)排序更新α、β、δ的位置，并且迭代次數(shù)t=t+1。

5)tmax為迭代次數(shù)閾值，如果t≤tmax，則跳轉(zhuǎn)至2)；如果t>tmax，則停止搜索。

3 算法步驟

1)無線傳感器網(wǎng)絡(luò)初始化。將傳感器節(jié)點隨機(jī)布設(shè)在目標(biāo)區(qū)域內(nèi)，信標(biāo)節(jié)點周期性廣播信號，信號包含其自身的ID及坐標(biāo)等信息；

2)未知節(jié)點接收到多個信標(biāo)節(jié)點信號，并將各組RSSI值進(jìn)行預(yù)處理。然后通過傳播損耗模型計算到信標(biāo)節(jié)點的距離，將距離從小到大排序，并建立距離與信標(biāo)節(jié)點的映射。按順序逐次取三個距離值及對應(yīng)的信標(biāo)節(jié)點，構(gòu)建重合區(qū)域，計算重合區(qū)域的交點以及交點的質(zhì)心；

3)通過前三個距離的質(zhì)心M1計算差分修正因子，然后運用差分修正因子對其他質(zhì)心進(jìn)行差分修正；

4)將得到的k(k=n-2)個質(zhì)心作為灰狼優(yōu)化算法的初始值，將其坐標(biāo)賦值給灰狼個體；

5)通過灰狼優(yōu)化算法獲取未知節(jié)點位置，迭代至預(yù)設(shè)次數(shù)閾值。

算法流程如圖3所示。

圖3 算法流程

4 仿真分析

為了驗證GWO-RDCCL算法性能[12-13]，在50 m*50 m的矩形區(qū)域內(nèi)隨機(jī)放置100個節(jié)點，其中30%的節(jié)點為未知節(jié)點。預(yù)設(shè)灰狼算法的種群規(guī)模為30，算法的最大迭代次數(shù)為300。從節(jié)點通信半徑、信標(biāo)節(jié)點密度兩個方面對GWO-RDCCL算法、GWO定位算法以及加權(quán)質(zhì)心定位算法進(jìn)行對比分析。

信標(biāo)節(jié)點密度與平均定位精度的關(guān)系如圖4所示。

圖4 信標(biāo)節(jié)點密度與平均定位精度的關(guān)系

由圖4可知，逐漸增加信標(biāo)節(jié)點密度，使得更多的未知節(jié)點數(shù)據(jù)被收集，因此，平均定位誤差在逐漸降低。

GWO-RDCCL算法的平均定位誤差始終低于其他兩種算法，表明文中通過灰狼優(yōu)化改進(jìn)差分修正質(zhì)心方法的有效性。當(dāng)信標(biāo)節(jié)點密度大于35%后，平均定位誤差的變化較小，當(dāng)信標(biāo)節(jié)點密度為50%，平均定位誤差為0.096。

節(jié)點通信半徑與平均定位精度的關(guān)系如圖5所示。

圖5中信標(biāo)節(jié)點密度為35%時，隨著通信半徑變化對平均定位誤差的影響。當(dāng)通信半徑減小時，信標(biāo)節(jié)點可通訊范圍減小，同時可覆蓋的未知節(jié)點較少，平均定位誤差較大，逐漸增大節(jié)點通信半徑，三種定位算法的平均定位誤差逐漸降低，并且GWO-RDCCL算法明顯優(yōu)于其他兩種定位算法，當(dāng)通信半徑為30時，GWO-RDCCL算法的平均定位精度為0.092，GWO定位算法為0.124，加權(quán)質(zhì)心定位算法為0.16。

圖5 節(jié)點通信半徑與平均定位精度的關(guān)系

5 結(jié) 語

介紹一種基于RSSI的灰狼優(yōu)化差分修正質(zhì)心定位算法(RSSI-based Gray Wolf Optimization Differential Correction Centroid Location Algorithm， GWO-RDCCL)，在初步估計未知節(jié)點的位置階段，通過對處理后接收信號強(qiáng)度計算測量距離，構(gòu)建三角形來計算質(zhì)心作為未知節(jié)點的初步定位；在精確定位階段采用灰狼優(yōu)化算法來優(yōu)化質(zhì)心實現(xiàn)對未知節(jié)點的定位。通過初步定位縮小最優(yōu)解的搜索空間，減少了算法的計算量，也提高了算法收斂的速度。仿真實驗表明，GWO-RDCCL算法同等條件下相比于常用的定位算法，在一定程度上提高了定位精度。