(淮陰工學(xué)院 自動(dòng)化學(xué)院,江蘇 淮安 223003)

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

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

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

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

1 RSSI測(cè)距原理

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

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

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

(1)

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

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

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

(2)

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

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

RSSI=Psend+Pamplify-PL(d)

(3)

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

2 MRSSI-SFL

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

圖1 定位框圖

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

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

(4)

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

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

(5)

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

(6)

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

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

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

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

(7)

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

(8)

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

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

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

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

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

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

(9)

(10)

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

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

(11)

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

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

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

② 對(duì)最差的青蛙Xw進(jìn)行更新：

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

(12)

newXw=oldXw+D,Dmin≤D≤Dmax

(13)

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

(14)

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

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

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

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

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

圖3 算法流程圖

3 仿真實(shí)驗(yàn)及分析

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

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

(15)

3.1 實(shí)驗(yàn)1

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

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

圖4 定位誤差率

3.2 實(shí)驗(yàn)2

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

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

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

3.3 實(shí)驗(yàn)3

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

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

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

3.4 實(shí)驗(yàn)4

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

表1 算法的運(yùn)行時(shí)間

4 結(jié)束語

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