劉 政

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

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

劉 政

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

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

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

0 引言

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

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

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

如果用多個(gè)信標(biāo)節(jié)點(diǎn)定位未知節(jié)點(diǎn)，該未知節(jié)點(diǎn)一定處于多個(gè)信標(biāo)節(jié)點(diǎn)的感知信號(hào)交集。三邊測(cè)量法如圖1所示，若采用三邊測(cè)量法計(jì)算，前提必須保證三個(gè)信標(biāo)節(jié)點(diǎn)的感知圓圈相交于一點(diǎn)(定位節(jié)點(diǎn))。

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

存在下列公式：

(1)

由此可以得到未知節(jié)點(diǎn)D的坐標(biāo)為：

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

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

(2)

(3)

(4)

(5)

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

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

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

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

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

(6)

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

(7)

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

(8)

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

(9)

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

3 算法流程

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

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

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

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

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

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

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

4.1RSSI值與測(cè)距距離的擬合

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

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

(10)

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

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

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

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

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

節(jié)點(diǎn)定位誤差計(jì)算如式(11)所示：

(11)

對(duì)N個(gè)未知節(jié)點(diǎn)的定位誤差求平均，得到平均定位誤差為：

(12)

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

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

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

4.3 信標(biāo)分布密度對(duì)定位誤差的影響

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

圖5 定位誤差與信標(biāo)節(jié)點(diǎn)個(gè)數(shù)示意圖Fig.5 Locating error and number of beacon nodes

5 結(jié)束語(yǔ)

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

[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ú)線傳感器網(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].電子測(cè)量與儀器學(xué)報(bào),2013,27(10):937-943.

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

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

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

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

[14]黨小超,李小艷.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位加權(quán)校正模型[J].計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(編號(hào)：61202007)；

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

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

TP393

A

10.16086/j.cnki.issn1000-0380.201506001

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

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