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

劉 政

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

?

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

劉 政*

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

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

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

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

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

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

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

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

(1)

式中:Loss:信號傳輸d距離后的路徑損耗;d:距信標節(jié)點的距離(單位: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的高斯分布隨機變數(shù),標準差范圍在4～10之間。

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

待定位節(jié)點收到信標節(jié)點的信號強度:

RSSI(d)=Pt-PL(d)

(3)

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

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

(4)

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

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

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

(5)

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

(6)

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

(7)

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

(8)

2 改進定位算法

2.1 加權質心定位原理

圖1 加權質心原理

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

(9)

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

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

(15)

(16)

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

3 算法流程

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

圖2 硬件平臺

4 實驗結果與分析

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

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

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

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

(17)

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

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

圖4 擬合效果比較

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

歸一化平均定位誤差:

(18)

4.2 不同權重系數(shù)的定位結果比較

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

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

4.3 不同信標節(jié)點個數(shù)的定位結果比較

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

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

圖6 信標節(jié)點個數(shù)與定位誤差

4.4 不同測距誤差的定位結果比較

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

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

圖7 測距誤差與定位誤差

5 結論

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

[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)絡測距和定位技術研究[D]. 長沙:國防科技大學,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]陶金龍,康志偉,駱堅. 基于RSSI測距的加權概率定位算法[J]. 電子測量與儀器學報,2014,28(10):1123-1129.

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

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

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

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

[14]黨小超,李小艷. 無線傳感器網(wǎng)絡節(jié)點定位加權校正模型[J]. 計算機應用,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-),男,講師,主要研究方向為無線傳感器網(wǎng)絡,智能儀器,davidbetty@163.com,liuz@guat.edu.cn。

項目來源:國家自然科學基金項目(61202007);廣西教育廳科研項目(201106LX718);桂林航天工業(yè)學院基金項目(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