基于權重動態離散模型的WSNs定位算法*

劉 政

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

?

基于權重動態離散模型的WSNs定位算法*

劉 政*

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

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

無線傳感器網絡;定位算法;離散權重;動態路徑損耗指數

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

1 動態路徑損耗指數的RSSI測距

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

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

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

(1)

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

對數-常態分布模型如下:

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

(2)

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

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

待定位節點收到信標節點的信號強度:

RSSI(d)=Pt-PL(d)

(3)

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

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

(4)

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

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

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

(5)

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

(6)

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

(7)

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

(8)

2 改進定位算法

2.1 加權質心定位原理

圖1 加權質心原理

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

(9)

2.2 離散權重動態修正定位

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

(15)

(16)

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

3 算法流程

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

圖2 硬件平臺

4 實驗結果與分析

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

采用TI公司的CC2530作為WSNs定位節點(北京博創智聯公司生產),2個待定位節點,10個信標節點,共12個節點,如圖2所示。

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

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

(17)

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

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

圖4 擬合效果比較

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

歸一化平均定位誤差:

(18)

4.2 不同權重系數的定位結果比較

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

圖5 平均定位誤差與修正系數

4.3 不同信標節點個數的定位結果比較

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

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

圖6 信標節點個數與定位誤差

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

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

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

圖7 測距誤差與定位誤差

5 結論

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

[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的無線傳感器網絡測距和定位技術研究[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]于海存,石為人,冉啟可,等. 基于虛擬靜態錨節點的加權質心定位算法[J]. 傳感技術學報,2013,26(9):1276-1283.

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

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

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

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

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