WSNs中基于RSSI優(yōu)化的節(jié)點定位算法研究

(淮陰工學院 自動化學院,江蘇 淮安 223003)

無線傳感網(wǎng)絡 (Wireless Sensor Networks，WSNs)[1-2]是由大量的微型、具有通信能力的傳感節(jié)點組成。目前，WSNs已廣泛應用于健康醫(yī)療服務、環(huán)境監(jiān)測等應用，而估計傳感節(jié)點的位置是WSNs應用的基礎。

目前，根據(jù)定位機制的不同，可將定位算法劃分為與距離無關(Range-Free)和距離相關(Range-Based)的定位算法。前者是依據(jù)網(wǎng)絡的連通性估計未知節(jié)點位置，如最短路徑 (Shortest Path,SP)定位算法、質(zhì)心定位算法、跳距矢量(Distance Vector-Hop,DV-Hop)算法等[3]。而后者是先依據(jù)測量的距離或角度信息，然后再結(jié)合最小二乘、三邊測量法等計算未知節(jié)點的位置。經(jīng)典的測距算法有：基于到達時間(Time of Arrival,TOA)[4]、基于接收信號強度指標RSSI[5]、基于到達角度[6]、基于到達時間差(Different Time of Arrival,TDOA)[7]。

由于RSSI測距無需額外硬件設備，被廣泛應用于低成本、低開銷的無線傳感網(wǎng)絡，成為室內(nèi)定位研究的熱點。然而，基于RSSI測距算法普通存在較大的測距誤差。原因在于：無線信號容易受到傳輸環(huán)境的影響。為此，研究人員提出了不同的對RSSI值進行修正的算法。例如，文獻[8]利用高斯分布優(yōu)化RSSI值。而文獻[9]引用粒子濾波算法優(yōu)化測距，但也增加了一定的運算量。此外，文獻[9]和文獻[10]分別引用加權均值、卡爾曼濾波優(yōu)化RSSI值。

為此，基于RSSI改進的混合蛙跳的定位算法(Modifying RSSI Ranging-Based Shuffled Frog Leaping Localization Algorithm,MRSSI-SFL)。MRSSI-SFL算法先多次測量同一點的RSSI值，再利用正態(tài)分布優(yōu)化RSSI值。然后，利用加權質(zhì)心定位算法估計未知節(jié)點位置，并據(jù)此位置設置搜索區(qū)域，最后利用混合蛙跳算法優(yōu)化未知節(jié)點的位置。實驗數(shù)據(jù)表明，提出的MRSSI-SFL定位算法可有效降低定位誤差。

1 RSSI測距原理

由于成本低，RSSI測距被廣泛應用。RSSI測距利用所接收的無線信號強度的衰減來估計收/發(fā)間的距離。然而，無線信道存在較多的不穩(wěn)定因素以及多徑效應，導致信號強度的衰減與距離的關系存在波動。針對此情況，選擇基于對數(shù)-常態(tài)分布的自由空間損耗模型作為無線信號傳播模型。

首先，建立自由空間損耗模型：

PL(d0)=32.44+10nlgd0+10nlgf

(1)

式中，d0、n分別為傳播距離、傳輸路徑衰減因子；f為信號頻率。

而對數(shù)-常態(tài)分布模型可表述為

PL(d)=PL(d0)+10nlg(d/d0)+ζn

(2)

式中，PL(d)為傳輸距離d時的路徑損耗，而PL(d0)為當d0=1 m時的路徑損耗；ζn為零均值的高斯變量函數(shù)。

結(jié)合式(1)和式(2)，從相離距離為d的節(jié)點所接收的信號RSSI:

RSSI=Psend+Pamplify-PL(d)

(3)

式中，Psend、Pamplify分別為發(fā)射功率、天線增益。

2 MRSSI-SFL

所提出的MRSSI-LM定位算法先多次測量RSSI值，并利用正態(tài)分布函數(shù)優(yōu)化的RSSI值進行測距。隨后，利用加權質(zhì)心算法設定搜索區(qū)域，最后利用混合蛙跳迭代算法優(yōu)化未知節(jié)點位置。整個定位過程如圖1所示。

圖1 定位框圖

2.1 基于正態(tài)分布測距

由于無線環(huán)境具有多變特性，僅利用單一測量的RSSI值估算距離存在較大誤差。為此，需要多測量同一個發(fā)射點的RSSI值。MRSSI-SFL算法對同一個地點多次測量，然后利用正態(tài)分布計算閾值。假定RSSI1，RSSI2，…，RSSIm表示RSSI的總體樣本，相應地，rssi1，rssi2，…，rssim表示對應的樣本觀測值。據(jù)此，可建立似然函數(shù):

(4)

式中，μ、σ2分別為均值、方差。

對式(4)兩邊取μ、σ2偏導數(shù)，可得方程組：

(5)

通過求解式(5)可得μ、σ2的最大似然估計值為

(6)

通過上述過程，便能得到正態(tài)分布的均值和方差。最后將RSSI代入式(3)就能實現(xiàn)測距。

2.2 基于質(zhì)心加權的初始解

通過2.1節(jié)獲取距離信息后，再選擇離未知節(jié)點最近的3個錨節(jié)點。然后，以未知節(jié)點到3個錨節(jié)點的距離為半徑，以錨節(jié)點坐標為圓心畫3個圓。3個圓的重疊部分表示未知節(jié)點可能在的區(qū)域，如圖2所示。

圖2 加權質(zhì)心算法示意圖

(7)

式中，ωa=1/(Db+Dc)、ωb=1/(Da+Dc)、ωc=1/(Db+Da)為3個交點的權重。以(x,y,z)為中心，以h為搜索空間的內(nèi)切球半徑構成搜索空間：

(8)

為了提高了定位精度，利用(x,y,z)建立青蛙種群的活動區(qū)域，即搜索空間。

2.3 基于混合蛙跳的位置優(yōu)化

混合蛙跳算法是通過仿效青蛙種群搜索食物的過程，進而完成尋優(yōu)。此過程包括種群信息交換、子群內(nèi)部交流?；旌贤芴惴▽崿F(xiàn)步驟如下[12]。

(1) 建立初始種群，種群中候選解個數(shù)為P。

(2) 設置適應度函數(shù)，并將P只青蛙按適應值進行排序，且從小至大排列。

適應度函數(shù)的定義為

(9)

(10)

式中，di為測量距離；k表示與未知節(jié)點連通的錨節(jié)點個數(shù)。

式(9)中的f(x,y,z)表示誤差之和，誤差越小，定位越準確，其定義為

(11)

(3) 分組。將種群依據(jù)交替原則劃分為m個子群。

(4) 子群搜索。按順序搜索每個子群，直到滿足子群內(nèi)的搜索次數(shù)。搜索過程如下：

① 先確定最差、最好的青蛙。假定Xb、Xw表示所有子群中最好的青蛙、最差的青蛙。而Xg表示種群的最好青蛙。

② 對最差的青蛙Xw進行更新：

D=C×rand()×(Xg-Xw)+(1-C)×rand()×(Xb-Xw)

(12)

newXw=oldXw+D,Dmin≤D≤Dmax

(13)

式中，C為權重系數(shù)，初值為1，并不斷更新，如式(14)所示：

(14)

其中Ne、F為子群搜索次數(shù)、子群每搜索次數(shù)。

③ 用種群最好的青蛙Xg替換Xb，隨后，重新計算式(12)～式(14)。

(5) 混合子群。完成了m個子群優(yōu)化后，就回到步驟②，重新排序。

(6) 檢測是否滿足迭代次數(shù)K,否則就返回步驟(3)。

整個定位流程如圖3所示。首先參數(shù)初始化，包括候選解個數(shù)P、子群個數(shù)m、全局信息交換次數(shù)為K、子群內(nèi)搜索次數(shù)Ne。然后，測量RSSI，并進行優(yōu)化，再進行測距，并利用加權質(zhì)心算法估計未知節(jié)點的位置，再設置搜索區(qū)域。隨后，構建初始種群，再計算每種群的適應度函數(shù)。然后，依據(jù)混合蛙跳優(yōu)化未知節(jié)點的位置。

圖3 算法流程圖

3 仿真實驗及分析

為了更好地分析MRSSI-LM算法的定位性能，利用Matlab建立仿真平臺?？紤]1000 m×1000 m×1000 m的正方體區(qū)域，且在此區(qū)域內(nèi)隨機部署N=300個傳感節(jié)點，其中錨節(jié)點比例為ρ。即錨節(jié)點數(shù)Manchors=N×ρ,且0<ρ<1。節(jié)點通信半徑R=100 m。此外，青蛙子群數(shù)為50個，且每個子群內(nèi)的青蛙數(shù)為35只。子群內(nèi)部搜索次數(shù)Ne=50、全局交換信息的次數(shù)K=100。

為了更好地分析MRSSI-SFL的定位性能，選擇基于RSSI的加權質(zhì)心定位算法(RSSI+加權質(zhì)心)作為參照，并進行性能比較，包括定位誤差率和定位覆蓋率。定位誤差率定義為

(15)

3.1 實驗1

本次實驗分析節(jié)點總數(shù)對定位誤差率的影響，其中ρ=0.3。每次實驗獨立重復10次，取平均值作為實驗數(shù)據(jù)，如圖4所示。

從圖4可知，定位誤差隨節(jié)點總數(shù)的增加而呈下降趨勢，但存在一定的波動。相比于RSSI+加權質(zhì)心算法，提出的MRSSI-SFL算法的精度得到有效提高。當節(jié)點數(shù)較大時，定位誤差率下降了6%；而當節(jié)點數(shù)較小時，定位誤差率下降至2%。原因在于：MRSSI-SFL算法通過優(yōu)化RSSI值，提高了測距精度，同時利用混合蛙跳算法優(yōu)化了定位精度。此外，節(jié)點數(shù)的增加有利于測距信息的提高，進而降低了定位誤差。

圖4 定位誤差率

3.2 實驗2

本次實驗分析錨節(jié)點數(shù)對平均定位誤差的影響。節(jié)點總數(shù)300，錨節(jié)點數(shù)從30增加到150，實驗數(shù)據(jù)如圖5所示。

從圖5可知，錨節(jié)點數(shù)的增加降低了平均定位誤差。原因在于：錨節(jié)點數(shù)越多，獲取的測距信息越準確，這有利于定位精度的提高。與RSSI+加權質(zhì)心算法相比，提出的MRSSI-SFL算法的平均定位誤差得到有效控制，并且隨錨節(jié)點數(shù)的增加而提高。例如，當錨節(jié)點數(shù)達到150時，MRSSI-SFL算法的平均定位誤差比RSSI+加權質(zhì)心算法下降近9%。

圖5 錨節(jié)點數(shù)對平均定位誤差的影響

3.3 實驗3

最后，建立實驗分析錨節(jié)點數(shù)對MRSSI-SFL算法的覆蓋率的影響，其中節(jié)點總數(shù)為300，R=100 m、錨節(jié)點數(shù)從30增加到150變化，每次實驗獨立重復10次，取平均值作為最終的實驗數(shù)據(jù)，如圖6所示。

從圖6可知，錨節(jié)點數(shù)的增加有利于定位覆蓋率的提高，當錨節(jié)點數(shù)達到150時，RSSI+加權質(zhì)心和MRSSI-SFL算法的定位覆蓋率均達到0.9。在錨節(jié)點數(shù)整個變化區(qū)間，MRSSI-SFL算法的定位覆蓋率略高于RSSI+加權質(zhì)心。這也說明，MRSSI-SFL定位算法在估計未知節(jié)點位置時，對錨節(jié)點的分布要求較低。

圖6 錨節(jié)點數(shù)對定位覆蓋率的的影響

3.4 實驗4

本小節(jié)用運行時間數(shù)據(jù)分析算法的復雜度，如表1所示。從表1可知，提出的MRSSI+SFL算法的運行時間略高于RSSI+加權質(zhì)心算法，約0.07 s。這說明，MRSSI+SFL算法在提高定位精度的同時，并沒有加大算法的復雜度。

表1 算法的運行時間

4 結(jié)束語

針對WSNs的傳感節(jié)點問題，提出基于RSSI改進的混合蛙跳的定位算法(MRSSI-SFL)。MRSSI-SFL先優(yōu)化RSSI值，提高測距數(shù)度。然后，再利用加權質(zhì)心定位算法估計未知節(jié)點位置，并將此位置作為蛙跳算法迭代的初始值，通過迭代，提高未知節(jié)點位置的精度。實驗數(shù)據(jù)表明，提出的MRSSI-SFL算法相比RSSI+加權質(zhì)心算法，其定位精度得到有效提高，也提高了定位覆蓋率。后期，將進一步優(yōu)化定位算法，降低算法的復雜度。