劉 政

(桂林航天工業(yè)學(xué)院自動化系,廣西 桂林 541004)

?

基于權(quán)重動態(tài)離散模型的WSNs定位算法*

劉 政*

(桂林航天工業(yè)學(xué)院自動化系,廣西 桂林 541004)

針對測距誤差和距離權(quán)重對定位誤差的影響,提出一種離散距離權(quán)重動態(tài)修正的定位算法。算法首先分區(qū)域獲取動態(tài)路徑損耗指數(shù),建立接收信號強(qiáng)度測距簡化數(shù)學(xué)模型,抑制接收信號強(qiáng)度測距誤差。然后將靜態(tài)距離權(quán)重因子離散化,為離散距離權(quán)重匹配動態(tài)權(quán)重系數(shù),并在劃定的動態(tài)取值范圍內(nèi)尋找最優(yōu)權(quán)重系數(shù),權(quán)重系數(shù)與接收信號強(qiáng)度正相關(guān)?；贛ATLAB平臺仿真結(jié)果表明,與其他算法相比,該算法能夠較好地抑制接收信號強(qiáng)度測距的誤差影響,顯著降低平均定位誤差,提高定位精度。

無線傳感器網(wǎng)絡(luò);定位算法;離散權(quán)重;動態(tài)路徑損耗指數(shù)

無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)是由大量的靜止或移動的傳感器節(jié)點(diǎn)以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò)。由于節(jié)點(diǎn)的通信能力和計(jì)算能力有限,節(jié)點(diǎn)之間的傳感信息需要各個節(jié)點(diǎn)協(xié)作感知和計(jì)算,并將該信息在WSNs中共享,而節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)的一項(xiàng)關(guān)鍵技術(shù)[1-3],目前的定位算法從定位手段上看主要有兩大類:基于測距和非測距?；跍y距是通過測量節(jié)點(diǎn)間的距離或角度信息,使用三邊測量、三角測量或最大似然估計(jì)定位法[4]計(jì)算節(jié)點(diǎn)位置。常用的測距技術(shù)有:接收信號強(qiáng)度指示RSSI[5](Received Signal Strength Indication)、到達(dá)時(shí)間TOA(Time Of Arrive)、到達(dá)時(shí)間差TDOA(Time Difference Of Arrival)和到達(dá)角度AOA(Angle Of Arrival)等,非測距則不需要距離和角度信息,根據(jù)網(wǎng)絡(luò)連通性等信息來實(shí)現(xiàn)節(jié)點(diǎn)定位。常用的非測距技術(shù)有質(zhì)心算法[6]、近似三角形內(nèi)點(diǎn)測試APIT(Approximate Point-in-Iriangulation Test)算法[7]、DV-hop算法[8]等。針對WSNs定位技術(shù)的研究已經(jīng)有一些成果,文獻(xiàn)[9]運(yùn)用高斯噪聲模擬路徑衰減指數(shù)誤差,根據(jù)信號強(qiáng)度對信標(biāo)節(jié)點(diǎn)設(shè)定權(quán)重,抑制距離較遠(yuǎn)的信標(biāo)節(jié)點(diǎn)的測距誤差;文獻(xiàn)[10]結(jié)合余弦定理,利用原有的信標(biāo)節(jié)點(diǎn)定位信息構(gòu)造出虛擬靜態(tài)信標(biāo)節(jié)點(diǎn),優(yōu)化信標(biāo)節(jié)點(diǎn)數(shù)量;文獻(xiàn)[11]通過分析接收信號強(qiáng)度的變化規(guī)律,利用均值和權(quán)重來降低環(huán)境因素對接收信號強(qiáng)度的影響;文獻(xiàn)[12]以RSSI出現(xiàn)在區(qū)間每個距離點(diǎn)下的概率為權(quán)重對區(qū)間中的所有距離進(jìn)行加權(quán)求和,建立能量和距離之間的映射關(guān)系;文獻(xiàn)[13]統(tǒng)計(jì)RSSI測距和靜態(tài)權(quán)重定位的實(shí)驗(yàn)數(shù)據(jù),找出定位區(qū)域離散劃分范圍,提出高斯擬合動態(tài)權(quán)重定位算法。本文在已有研究基礎(chǔ)之上,提出一種抑制RSSI測距誤差的離散權(quán)重修正定位算法。算法結(jié)合傳播路徑損耗模型和對數(shù)-常態(tài)分布模型推算出RSSI與信標(biāo)節(jié)點(diǎn)、待定位節(jié)點(diǎn)間距的簡化計(jì)算模型,并對靜態(tài)距離權(quán)重進(jìn)行改進(jìn),強(qiáng)化較近距離信標(biāo)影響力,弱化較遠(yuǎn)距離信標(biāo)影響力,最終降低測距誤差,提高定位精度。改進(jìn)算法實(shí)現(xiàn)原理簡單,不存在多維度矩陣的運(yùn)算和復(fù)雜的迭代計(jì)算。

1 動態(tài)路徑損耗指數(shù)的RSSI測距

信道的長距離衰落特性服從對數(shù)正態(tài)分布,受多徑衰減、背景噪聲和信標(biāo)節(jié)點(diǎn)分布離散性影響,利用自由空間無線電傳播路徑損耗模型結(jié)合對數(shù)-常態(tài)分布模型計(jì)算信號傳輸?shù)穆窂綋p耗更具合理性。

自由空間無線電傳播路徑損耗模型:

Loss=32.4+10n×lg(d)+10n×lg(f)

(1)

式中:Loss:信號傳輸d距離后的路徑損耗;d:距信標(biāo)節(jié)點(diǎn)的距離(單位:m);n:信號損耗系數(shù),通常取2～4;f:傳輸信號的頻率(單位:MHz)。

對數(shù)-常態(tài)分布模型如下:

PL(d)=PL(d0)+10n×lg(d/d0)+Xσ

(2)

式中:PL(d):信號傳輸d距離的路徑損耗;d0:近地參考距離;PL(d0):信號傳輸d0距離后的路徑損耗;n:路徑損耗指數(shù),范圍在2～4之間;Xσ:平均值為0的高斯分布隨機(jī)變數(shù),標(biāo)準(zhǔn)差范圍在4～10之間。

取d0=lm代入式(1)來計(jì)算Loss得到PL(d0)。

待定位節(jié)點(diǎn)收到信標(biāo)節(jié)點(diǎn)的信號強(qiáng)度:

RSSI(d)=Pt-PL(d)

(3)

式中:RSSI(d):接收信號強(qiáng)度(單位:dBm);Pt:發(fā)射信號功率(單位:dBm);PL(d):路徑損耗。

綜合式(1)～式(3),經(jīng)過IEEE 802.15.4簡化的RSSI測距計(jì)算[14]:

(4)

式(4)的RSSI測距計(jì)算是基于路徑損耗指數(shù)為常數(shù)的前提,但是如果區(qū)域環(huán)境變化影響較大,那么節(jié)點(diǎn)所處不同位置的路徑損耗指數(shù)也不相同,利用式(4)計(jì)算的RSSI測距誤差較大。為了彌補(bǔ)這種誤差,可通過計(jì)算鄰居信標(biāo)節(jié)點(diǎn)間的RSSI值,先求出當(dāng)前區(qū)域內(nèi)的路徑損耗指數(shù)。

將信標(biāo)節(jié)點(diǎn)B1收到鄰居信標(biāo)節(jié)點(diǎn)B2、B3的RSSI值代入式(3):RSSI(dB1B2)=Pt-PL(d0)-10n×lg(dB1B2/d0)+Xσ

RSSI(dB1B3)=Pt-PL(d0)-10n×lgdB1B3/d0)+Xσ

(5)

由于信標(biāo)節(jié)點(diǎn)的位置已知,故它們之間的間距dB1B2、dB1B3可以精確得到。

(6)

通過將式(5)中的RSSI(dB1B2)和RSSI(dB1B3)相減,得到路徑損耗指數(shù)的算式:

(7)

將式(7)代入式(4),得到動態(tài)路徑損耗指數(shù)的RSSI測距算式:RSSI(d)=

(8)

2 改進(jìn)定位算法

2.1 加權(quán)質(zhì)心定位原理

圖1 加權(quán)質(zhì)心原理

用3個信標(biāo)節(jié)點(diǎn)B1,B2,B3與待定位節(jié)點(diǎn)D的不同距離作為權(quán)重因子對其質(zhì)心定位,得到近似位置Pi(x,y)。

(9)

2.2 離散權(quán)重動態(tài)修正定位

拆分式(9)中的權(quán)重因子:

(10)

為了能夠調(diào)節(jié)距離權(quán)重影響程度,在式(10)基礎(chǔ)上增加權(quán)重系數(shù)K。

(11)

將式(11)代回式(9)得到修正式(12)。

(12)

由于權(quán)重系數(shù)K的取值能夠調(diào)節(jié)距離權(quán)重,所以和測距距離有直接關(guān)系。從式(12)抽取任意一個信標(biāo)節(jié)點(diǎn)Bs(x,y),利用最小函數(shù)值原理找出權(quán)重系數(shù)K的取值趨勢。

(13)

式中:Pi,s(x,y)表示信標(biāo)節(jié)點(diǎn)Bs(x,y)對待定位節(jié)點(diǎn)Di(x,y)的定位影響力。

(14)

(15)

(16)

文獻(xiàn)[13]將定位區(qū)域劃分為0.5 m×0.5 m的小方塊單元,并對各個單元的離散權(quán)重系數(shù)進(jìn)行統(tǒng)計(jì),發(fā)現(xiàn)離散權(quán)重系數(shù)主要分布在1.5～2.0之間,比例達(dá)到80%以上,并且隨著區(qū)域的擴(kuò)大,權(quán)重系數(shù)為1.5的比例降低,權(quán)重為2.0的比例增長。借鑒文獻(xiàn)[13]的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果,取權(quán)重系數(shù)K值范圍在1～3.5之間,這種取值特點(diǎn)可以將定位區(qū)域進(jìn)行粗分而不會降低太多的定位精度。

3 算法流程

①信標(biāo)節(jié)點(diǎn)周期性發(fā)送包含節(jié)點(diǎn)ID、自身位置信息P的數(shù)據(jù)。②待定位節(jié)點(diǎn)在收到信標(biāo)節(jié)點(diǎn)數(shù)據(jù)后統(tǒng)計(jì)RSSI值和信標(biāo)節(jié)點(diǎn)位置信息P,對來自同一個信標(biāo)節(jié)點(diǎn)的多次RSSI值先進(jìn)行卡爾曼濾波再求均值作為最終RSSI值。③將RSSI值從大到小排序,建立RSSI集合RSSI={RSSIB1,RSSIB2,…,RSSIBn},取前3個作為鄰居信標(biāo)節(jié)點(diǎn),計(jì)算鄰居信標(biāo)節(jié)點(diǎn)間的RSSI值,利用式(7)得到當(dāng)前區(qū)域內(nèi)的路徑損耗指數(shù)n,代入式(8)得到RSSI測距距離。④利用高斯擬合函數(shù)對步驟⑤得到的距離進(jìn)行過濾修正。⑤將從RSSI集合中選擇的鄰居信標(biāo)節(jié)點(diǎn)構(gòu)成如圖1所示的質(zhì)心三角形,如果不滿足,則選擇RSSI集合的第4個元素對應(yīng)的信標(biāo)節(jié)點(diǎn),以此類推直到滿足質(zhì)心三角形。權(quán)重系數(shù)K在1～3.5之間選擇,再由式(12)計(jì)算得到一組待定位節(jié)點(diǎn)位置坐標(biāo)群。⑥由式(18)計(jì)算K分布在1～3.5之間對應(yīng)的平均定位誤差,K遞增幅度0.1,找到誤差最小對應(yīng)的權(quán)重系數(shù)K值。⑦根據(jù)步驟⑥得到的K值,利用式(12)重新計(jì)算坐標(biāo),完成修正定位。

圖2 硬件平臺

4 實(shí)驗(yàn)結(jié)果與分析

4.1 RSSI(d)與d的高斯擬合

采用TI公司的CC2530作為WSNs定位節(jié)點(diǎn)(北京博創(chuàng)智聯(lián)公司生產(chǎn)),2個待定位節(jié)點(diǎn),10個信標(biāo)節(jié)點(diǎn),共12個節(jié)點(diǎn),如圖2所示。

設(shè)定1 m、5 m、10 m、15 m、20 m、25 m作為參考測量距離點(diǎn),在每個距離點(diǎn)通過RSSI測距100次,利用式(8)算出一組RSSI(d)數(shù)據(jù)。再利用高斯擬合函數(shù)[13]對這組數(shù)據(jù)做高斯擬合修正處理,濾除一部分干擾數(shù)據(jù),降低測距誤差,如圖3所示。

圖3 RSSI與測距距離的高斯擬合

(17)

式中:d0和A是與距離和RSSI值有關(guān)系的待定系數(shù),m為待定位節(jié)點(diǎn)接收到RSSI數(shù)據(jù)的信標(biāo)節(jié)點(diǎn)個數(shù)。

圖4為采用高斯擬合與均值擬合的誤差比較,結(jié)果表明,待定位節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離在10m到20m之間的誤差波動較小,小于10m或大于20m的誤差波動較大,整體上來看,高斯擬合對近距離的RSSI測距修正效果要明顯優(yōu)于均值擬合。

圖4 擬合效果比較

利用MATLAB7.0進(jìn)行仿真實(shí)驗(yàn),網(wǎng)絡(luò)參數(shù)設(shè)置:50個待定位節(jié)點(diǎn)和20個信標(biāo)節(jié)點(diǎn)隨機(jī)分布50m×50m的平面區(qū)域,節(jié)點(diǎn)的通信半徑為20m。性能評價(jià)指標(biāo)為平均定位誤差,在同一網(wǎng)絡(luò)環(huán)境下重復(fù)試驗(yàn)100次,對100次測距誤差求均值。

歸一化平均定位誤差:

(18)

4.2 不同權(quán)重系數(shù)的定位結(jié)果比較

如圖5所示,當(dāng)權(quán)重系數(shù)K從1向3.5變化過程中,改進(jìn)算法的平均定位誤差有了明顯的變化,當(dāng)權(quán)重系數(shù)K為1時(shí)誤差最大,達(dá)到28.1%,當(dāng)權(quán)重系數(shù)K增加到1.9時(shí),誤差最低,僅為12.7%,這是一個逐漸降低的過程。當(dāng)權(quán)重系數(shù)K大于1.9,誤差逐漸升高?；炯訖?quán)質(zhì)心和靜態(tài)加權(quán)質(zhì)心的定位誤差始終保持為31.3%和28.1%,這是因?yàn)檫@兩種算法沒有權(quán)重系數(shù)的動態(tài)調(diào)節(jié)。

圖5 平均定位誤差與修正系數(shù)

4.3 不同信標(biāo)節(jié)點(diǎn)個數(shù)的定位結(jié)果比較

信標(biāo)節(jié)點(diǎn)個數(shù)的多少反應(yīng)了當(dāng)前WSNs中信標(biāo)節(jié)點(diǎn)的分布密度,設(shè)定:初始信標(biāo)節(jié)點(diǎn)個數(shù)從3個遞增到12個,測距誤差為25%。

如圖6所示,隨著信標(biāo)節(jié)點(diǎn)數(shù)量的增加,3種算法的定位誤差都有一定程度的下降,基本加權(quán)質(zhì)心的平均定位誤差從29.2%下降到23.9%,靜態(tài)權(quán)重質(zhì)心從22.5%下降到17.4%,改進(jìn)算法從13.5%下降到9.05%。信標(biāo)節(jié)點(diǎn)數(shù)量從3個增加到8個,定位誤差下降明顯,信標(biāo)節(jié)點(diǎn)數(shù)量從8個繼續(xù)增加到12個,定位誤差下降趨勢已經(jīng)不明顯,信標(biāo)節(jié)點(diǎn)數(shù)量的增加對減小平均定位誤差的作用逐漸弱化。

圖6 信標(biāo)節(jié)點(diǎn)個數(shù)與定位誤差

4.4 不同測距誤差的定位結(jié)果比較

測距誤差直接影響到節(jié)點(diǎn)間距離測量值的準(zhǔn)確度,進(jìn)而會影響到定位結(jié)果的準(zhǔn)確度。為了方便衡量測距誤差對定位誤差的影響,取測距誤差在5%～35%范圍之間變化。

從圖7實(shí)驗(yàn)結(jié)果可知,隨著測距誤差的增大,3種算法的平均定位誤差都隨之增加,這是因?yàn)闇y距誤差的增加使得距離權(quán)重誤差影響加大,造成定位精度下降。當(dāng)測距誤差從5%增加到35%,基本加權(quán)質(zhì)心的平均定位誤差從17.5%增加到39.1%,靜態(tài)權(quán)重質(zhì)心從13.4%增加到27.5%,改進(jìn)算法從9.1%增加到17.9%,相比較,改進(jìn)算法抑制測距誤差影響的效果最好。

圖7 測距誤差與定位誤差

5 結(jié)論

本文利用動態(tài)路徑損耗指數(shù)的RSSI(d)測距簡化數(shù)學(xué)模型和高斯擬合修正,抑制RSSI測距誤差,離散化靜態(tài)距離權(quán)重,并為距離權(quán)重匹配動態(tài)權(quán)重系數(shù)。該算法不需要節(jié)點(diǎn)之間進(jìn)行復(fù)雜的協(xié)調(diào)過程,算法復(fù)雜度也只比質(zhì)心算法略有增加,具有良好的可擴(kuò)展性,可以滿足傳感器網(wǎng)絡(luò)中對位置精度要求不太苛刻的應(yīng)用。下一步的改進(jìn)思路:根據(jù)RSSI的衰減程度,為每一個不同距離的信標(biāo)節(jié)點(diǎn)分配獨(dú)立的權(quán)重系數(shù),建立RSSI(d)與K、λ的精確數(shù)學(xué)模型。

[1]Rudafshni M,Datta S. Localization in Wireless Sensor Networks[C]//Information Processing in Sensor Networks(IPSN),2007:51-60.

[2]Arampatzis T,Lygeros J,Manesis S. A Survey of Applications of Wireless Sensors and Wireless Sensor Networks[C]//Proceedings of the 2005 IEEE International Symposium on,Mediterrean Conference on Control and Automation,2005:719-724.

[3]Akyildiz I,Su W,Sankarasvbramaniam Y. A Survey on Sensor Networks[J]. IEEE Communications Magazine,2011,40(8):102-l14.

[4]朱登科. 基于RSSI的無線傳感器網(wǎng)絡(luò)測距和定位技術(shù)研究[D]. 長沙:國防科技大學(xué),2010.

[5]Luthy K A,Grant D,henderson T C. Leveraging RSSI for Robotic Reapair of Disconnected Wireless Sensor Networks[C]//2007 IEEE International Conference on Robotics and Automation. Rome,Italy,2007:10-14.

[6]Nirupama B,John H,Deborah E. GPS less Low Cost Out Door Localization for Very Small Devices[J]. IEEE Personal Communications(S1070-9916),2000,7(5):28-34.

[7]Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems(S1572-9451),2003,22(1/4):267-280.

[8]He T,Huang C,Blum B M,et al. Range Free Localization Schemes for Large Scale Sensor Networks[C]//ACM International Conference on Mobile Computing and Networking(MobiCom). San Diego,California,USA:ACM Press,2003:81-95.

[9]陶金龍,康志偉,駱堅(jiān). 基于RSSI測距的加權(quán)概率定位算法[J]. 電子測量與儀器學(xué)報(bào),2014,28(10):1123-1129.

[10]于海存,石為人,冉啟可,等. 基于虛擬靜態(tài)錨節(jié)點(diǎn)的加權(quán)質(zhì)心定位算法[J]. 傳感技術(shù)學(xué)報(bào),2013,26(9):1276-1283.

[11]方震,趙湛,郭鵬. 基于RSSI測距分析[J]. 傳感技術(shù)學(xué)報(bào),2007,20(11):2526-2530.

[12]王緩緩,宮娜娜. 基于距離區(qū)間概率加權(quán)的RSSI測距方法[J]. 電子科技大學(xué)學(xué)報(bào),2013,42(6):862-868.

[13]詹杰,劉宏立,劉述鋼,等. 基于RSSI的動態(tài)加權(quán)定位算法研究[J]. 電子學(xué)報(bào),2011,39(1):82-88.

[14]黨小超,李小艷. 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位加權(quán)校正模型[J]. 計(jì)算機(jī)應(yīng)用,2012,32(2):355-358.

Localization Algorithm for Wireless Sensor Networks(WSNs) Based on Dynamic Discrete Weighted Model*

LIUZheng*

(Department of Automation,Guilin University of Aerospace Technology,Guilin Guangxi 541004,China)

Aiming at the effects of range error and distance weighted on positioning error,a locating algorithm based on dynamic correction of discreet distance weighted is proposed. Firstly,the algorithm accesses the dynamical path loss exponent based on regional division,establishes the simplified mathematical model of RSSI range,and suppresses the RSSI measurement error. Then the static distance weighted factors are discretized and the dynamic weighted coefficient of discreet distance weighted is matched,meanwhile the optimal weighted coefficient within the dynamic scope is searched,weighted coefficient and RSSI has positive correlation. Simulation results based on MATLAB platform shows that this algorithm can decrease the influence of RSSI measurement error compared with other algorithms. The algorithm significantly reduces the average position error,and enhances the positioning accuracy.

wireless sensor network;location algorithm;discreet weighting;dynamic path loss exponent

劉 政(1981-),男,講師,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò),智能儀器,davidbetty@163.com,liuz@guat.edu.cn。

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(61202007);廣西教育廳科研項(xiàng)目(201106LX718);桂林航天工業(yè)學(xué)院基金項(xiàng)目(YJ1302)

2014-09-26 修改日期:2014-12-10

C:7230

10.3969/j.issn.1004-1699.2015.03.024

TP393

A

1004-1699(2015)03-0437-06