WSNs中基于RSSI優化的節點定位算法研究

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

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

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

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

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

1 RSSI測距原理

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

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

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

(1)

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

而對數-常態分布模型可表述為

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

(2)

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

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

RSSI=Psend+Pamplify-PL(d)

(3)

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

2 MRSSI-SFL

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

圖1 定位框圖

2.1 基于正態分布測距

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

(4)

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

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

(5)

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

(6)

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

2.2 基于質心加權的初始解

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

圖2 加權質心算法示意圖

(7)

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

(8)

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

2.3 基于混合蛙跳的位置優化

混合蛙跳算法是通過仿效青蛙種群搜索食物的過程，進而完成尋優。此過程包括種群信息交換、子群內部交流。混合蛙跳算法實現步驟如下[12]。

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

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

適應度函數的定義為

(9)

(10)

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

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

(11)

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

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

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

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

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

(12)

newXw=oldXw+D,Dmin≤D≤Dmax

(13)

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

(14)

其中Ne、F為子群搜索次數、子群每搜索次數。

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

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

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

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

圖3 算法流程圖

3 仿真實驗及分析

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

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

(15)

3.1 實驗1

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

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

圖4 定位誤差率

3.2 實驗2

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

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

圖5 錨節點數對平均定位誤差的影響

3.3 實驗3

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

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

圖6 錨節點數對定位覆蓋率的的影響

3.4 實驗4

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

表1 算法的運行時間

4 結束語

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