無線傳感器網(wǎng)絡(luò)節(jié)點自適應(yīng)加權(quán)定位算法

劉 政

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

無線傳感器網(wǎng)絡(luò)節(jié)點自適應(yīng)加權(quán)定位算法

劉 政

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

為了提高無線傳感器網(wǎng)絡(luò)節(jié)點定位精度，提出一種自適應(yīng)加權(quán)定位算法。首先將距離加權(quán)因子拆分為獨立加權(quán)因子，為獨立加權(quán)因子匹配修正系數(shù)，修正系數(shù)根據(jù)測距距離做自適應(yīng)調(diào)整，最后驗證獨立加權(quán)因子的自適應(yīng)修正系數(shù)與基于接收信號強度的測距距離的數(shù)學(xué)關(guān)系。仿真試驗結(jié)果表明，在同等測距誤差前提下，獨立加權(quán)因子的自適應(yīng)修正能夠顯著降低平均定位誤差，提高定位精度。

無線傳感器網(wǎng)絡(luò)(WSN) 定位算法 加權(quán)質(zhì)心 修正系數(shù) 接收信號

0 引言

節(jié)點定位是無線傳感器網(wǎng)絡(luò)的一項關(guān)鍵技術(shù)[1-3]，從定位手段上看，目前的定位算法主要基于測距和非測距。測距是通過測量節(jié)點間的距離或角度信息，使用三邊測量、三角測量或最大似然估計[4]計算節(jié)點位置。常用的測距技術(shù)有：接收信號強度指示[5]、到達時間差、到達角度等。非測距不需要距離和角度信息，根據(jù)網(wǎng)絡(luò)連通性[6]等信息來實現(xiàn)定位。常用的非測距技術(shù)有質(zhì)心算法[7]、近似三角形內(nèi)點測試算法[8]等。

關(guān)于節(jié)點定位的研究已有一些成果，文獻[9]先用極大似然估計對定位節(jié)點進行粗略估計，再用加權(quán)質(zhì)心求精；文獻[10]對信標節(jié)點通信交集區(qū)域構(gòu)成的三角形求質(zhì)心；文獻[11]根據(jù)節(jié)點距離的遠近，增加加權(quán)系數(shù)來調(diào)整加權(quán)影響力；文獻[12]～[13]先建立信號傳播模型，再離散劃分定位區(qū)域,并用高斯擬合求精。本文提出一種自適應(yīng)調(diào)整距離加權(quán)的定位算法，該算法實現(xiàn)原理簡單，整體開銷較小，能夠滿足WSNs低功耗的需求。

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

如果用多個信標節(jié)點定位未知節(jié)點，該未知節(jié)點一定處于多個信標節(jié)點的感知信號交集。三邊測量法如圖1所示，若采用三邊測量法計算，前提必須保證三個信標節(jié)點的感知圓圈相交于一點(定位節(jié)點)。

圖1 三邊測量法示意圖Fig.1 Schematic diagram of the trilateration measurement

存在下列公式：

(1)

由此可以得到未知節(jié)點D的坐標為：

圖2 加權(quán)質(zhì)心示意圖Fig.2 Sketch map of the weighted centroid

根據(jù)未知節(jié)點D到信標節(jié)點B1、B2的測距距離，得到距離與坐標的數(shù)學(xué)模型：

(2)

(3)

(4)

(5)

加權(quán)質(zhì)心為每一個測距坐標增加了距離加權(quán)，通過加權(quán)因子來體現(xiàn)各個信標節(jié)點對質(zhì)心坐標決定權(quán)的大小，并利用加權(quán)因子來體現(xiàn)各信標節(jié)點對質(zhì)心位置的影響程度。

由式(5)可知，將距離之和的倒數(shù)作為加權(quán)因子，僅反映出質(zhì)心三角形中未知節(jié)點和兩個信標節(jié)點總的距離關(guān)系，顯然沒有區(qū)分不同距離的信標節(jié)點影響力。

2 自適應(yīng)加權(quán)調(diào)整

通常情況下，兩個信標節(jié)點與未知節(jié)點的實際距離不可能完全一致，離未知節(jié)點越近的信標節(jié)點獲得的距離加權(quán)越大，離未知節(jié)點越遠的信標節(jié)點獲得的距離加權(quán)越小。在算法中應(yīng)該體現(xiàn)信標節(jié)點對未知節(jié)點的離散化加權(quán)影響，故拆分距離加權(quán)是算法改進的切入點。

拆分式(5)中的加權(quán)因子：

(6)

差異化距離加權(quán)的影響力，為式(6)增加加權(quán)修正系數(shù)K。

(7)

式(5)修正為式(8)：

(8)

加權(quán)修正系數(shù)K受到當前信標節(jié)點與未知節(jié)點距離差異的影響。從式(8)抽取任意一個信標節(jié)點Bs(x,y)，分析加權(quán)修正系數(shù)K的變化對定位效果的影響。

(9)

式中：Pi,s(x,y)為信標節(jié)點Bs(x,y)對未知節(jié)點Di(x,y)的定位影響力。衡量影響力的變化可以通過計算Pi,s(x,y)對K求導(dǎo)的正負性判斷。

3 算法流程

無線傳感器網(wǎng)絡(luò)節(jié)點自適應(yīng)加權(quán)定位算法流程如下。

① 信標節(jié)點周期性發(fā)送節(jié)點ID、自身位置信息P。

④ 未知節(jié)點選擇集合ωΒ中RSSI值排在前三的信標節(jié)點構(gòu)成如圖1或圖2所示的鄰居質(zhì)心三角形。如果不滿足，則選擇RSSI值排在第四的信標節(jié)點，以此類推直到滿足圖1或圖2的鄰居質(zhì)心三角形。加權(quán)修正系數(shù)K從1開始遞增，由式(8)計算得到一組未知節(jié)點位置坐標群。

⑤ 計算平均定位誤差，找到誤差最小時對應(yīng)的加權(quán)修正系數(shù)K。

⑥ 利用加權(quán)修正定位式(8)重新計算坐標，完成定位。

4 仿真結(jié)果與分析

在Matlab環(huán)境中，對改進算法進行仿真分析。為了更貼近實際環(huán)境，在測試中我們設(shè)置仿真區(qū)域為50m×50m大小的平面區(qū)域，50個未知節(jié)點的位置隨機分布，20個信標節(jié)點均勻隨機分布，節(jié)點的通信半徑為20m。信標節(jié)點感知未知節(jié)點的測距誤差為0～20%中的一個隨機數(shù)。

4.1RSSI值與測距距離的擬合

在實際的試驗中，我們設(shè)定1m、5m、10m、15m、20m作為參考測量距離點，在每個距離點通過RSSI測距100次，求出平均值作為RSSI值。統(tǒng)計實際測量中的RSSI數(shù)據(jù)和距離，確定實際環(huán)境中的RSSI測距傳輸函數(shù)[12]。

RSSI(d)=-39.86-10×2.17×lgd

(10)

然后對這些數(shù)據(jù)按照對數(shù)常態(tài)分布模型進行最小二乘法擬合，擬合曲線如圖3所示。

圖3 RSSI與測距距離擬合曲線Fig.3 Fitting curve of RSSI and ranging distance

4.2 修正系數(shù)對定位誤差的影響

為驗證改進算法性能，將本文改進定位、質(zhì)心定位、加權(quán)質(zhì)心的定位誤差進行比較。定位誤差指的是通過定位計算得到未知節(jié)點的估計位置與實際位置的偏差。這種偏差可以用兩者之間的歐氏距離除以節(jié)點的通信半徑來衡量，利用平均定位誤差來衡量定位算法的優(yōu)劣。

在同一網(wǎng)絡(luò)環(huán)境下重復(fù)試驗100次，每次試驗都將所有節(jié)點重置，并對100次測距誤差求均值。

節(jié)點定位誤差計算如式(11)所示：

(11)

對N個未知節(jié)點的定位誤差求平均，得到平均定位誤差為：

(12)

平均定位誤差與修正系數(shù)示意圖如圖4所示。

圖4 平均定位誤差與修正系數(shù)示意圖Fig.4 Average locating error and correction factor

觀察圖4中的加權(quán)修正系數(shù)K的變化對平均定位誤差造成的影響，可以看出，改進算法的平均定位誤差明顯優(yōu)于基本質(zhì)心和加權(quán)質(zhì)心。

4.3 信標分布密度對定位誤差的影響

信標節(jié)點密度是WSNs定位的重要參數(shù), 信標節(jié)點數(shù)量的增減會直接影響定位精度。若算法性能要求苛刻，需配置更多數(shù)量的信標節(jié)點，但是會直接導(dǎo)致WSNs的應(yīng)用成本大幅度提高，限制其大范圍的推廣。所以這里仿真驗證信標節(jié)點分布密度對定位誤差的影響，為檢驗本文改進算法的最優(yōu)性能，取K=1.9，分析未知節(jié)點的鄰居信標節(jié)點數(shù)量對平均定位誤差的影響。定位誤差與信標節(jié)點個數(shù)示意圖如圖5所示。

圖5 定位誤差與信標節(jié)點個數(shù)示意圖Fig.5 Locating error and number of beacon nodes

5 結(jié)束語

本文在加權(quán)質(zhì)心定位原理基礎(chǔ)上，將距離加權(quán)因子拆分成獨立加權(quán)因子，并為距離加權(quán)因子匹配修正系數(shù)K，K在自適應(yīng)調(diào)整中找到最小定位誤差。該算法不存在多維度矩陣的運算和復(fù)雜的迭代計算，可以滿足傳感器網(wǎng)絡(luò)中對位置精度要求不太苛刻的需求。下一步的改進思路：建立信標節(jié)點對未知節(jié)點RSSI測距值與加權(quán)系數(shù)動態(tài)選擇的數(shù)學(xué)模型，根據(jù)RSSI值大小動態(tài)劃分定位中心區(qū)域和邊緣區(qū)域，嘗試獲取中心區(qū)域和邊緣區(qū)域的分區(qū)域加權(quán)系數(shù)動態(tài)選擇計算模型。

[1] Jonathan B,Adam M.Localization in sensor networks[M].Handbook of Sensor Networks:Algorithms and Architectures.USA:Wiley-Interscience,2005:277-310.

[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] 溫立.無線傳感器網(wǎng)絡(luò)定位技術(shù)研究[D].上海：復(fù)旦大學(xué),2008:34-37.

[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(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] 韓江洪,祝滿拳,馬學(xué)森，等.基于RSSI的極大似然與加權(quán)質(zhì)心混合定位算法[J].電子測量與儀器學(xué)報,2013,27(10):937-943.

[10]丁恩杰,喬欣,常飛,等.基于RSSI的WSNs加權(quán)質(zhì)心定位算法的改進[J].傳感器與微系統(tǒng),2013,32(7):53-56.

[11]胡詠梅,張歡.一種改進的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J].計算機工程與科學(xué),2012,34(2)：45-49.

[12]陶志勇,路筍.基于ZigBee的修正加權(quán)質(zhì)心定位算法研究與實現(xiàn)[J].計算機應(yīng)用與軟件,2014,31(1)：123-126.

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

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

Adaptive Weighted Locating Algorithm for Wireless Sensor Network Nodes

In order to enhance the node locating accuracy for wireless sensor network, the adaptive weighted locating algorithm is proposed. Firstly, the distance weighting factor is split into independent weighting factors, and the correction coefficients are matched for independent weighting factors, the correction coefficients are adapted in accordance with the distance measured, finally the mathematical relationship between the adaptive correction coefficient of the independent weighing factor and the distance measured based on

signal strength is verified. The result of simulation experiment shows that under the same level of distance measuring error, the adaptive correction of the independent weighing factor can reduce the average locating error significantly for improving the locating accuracy.

Wireless sensor network(WSN) Locating algorithm Weighted centroid Correction coefficient Received signal

國家自然科學(xué)基金資助項目(編號：61202007)；

廣西教育廳科研基金資助項目(編號：201106LX718)；

桂林航天工業(yè)學(xué)院基金資助項目(編號：YJ1302)。

TP393

A

10.16086/j.cnki.issn1000-0380.201506001

修改稿收到日期：2014-12-04。

作者劉政(1981-)，男，2007年畢業(yè)于桂林理工大學(xué)檢測技術(shù)與自動化裝置專業(yè)，獲碩士學(xué)位，講師；主要從事無線傳感器網(wǎng)絡(luò)、智能儀器方面的研究。