張立國馬 鵬 金 梅 范美常 劉宇浩

?

基于RSSI測距的三維無線傳感網(wǎng)絡(luò)螢火蟲定位算法的研究①

張立國②馬 鵬 金 梅 范美常 劉宇浩

(燕山大學(xué)河北省測試計量技術(shù)與儀器重點實驗室 秦皇島 066004)

研究了三維空間無線傳感器網(wǎng)絡(luò)(WSN)未知節(jié)點的定位。針對目前三維空間無線傳感網(wǎng)絡(luò)定位算法精度低的問題，提出一種基于接收信號強度指示(RSSI)測距的螢火蟲定位的算法。該算法首先利用RSSI進行測距，建立信號強度隨傳播距離衰減的模型，然后在已知一定數(shù)量的錨節(jié)點的情況下，通過螢火蟲算法尋找目標(biāo)函數(shù)最優(yōu)值，進而對未知節(jié)點進行定位。仿真驗證結(jié)果表明，該定位算法相比其他算法定位精度有很大提高，在30m×30m×30m的空間內(nèi)定位誤差僅為0.59m。

無線傳感網(wǎng)絡(luò)(WSN)，三維空間，接收信號強度指示(RSSI)，螢火蟲算法(FA)

0 引 言

無線傳感網(wǎng)絡(luò)(wireless sensor networks, WSN)節(jié)點位置對整個網(wǎng)絡(luò)的應(yīng)用有重要影響，因此節(jié)點定位技術(shù)在無線傳感網(wǎng)絡(luò)中有著舉足輕重的地位。迄今為止無線傳感網(wǎng)絡(luò)的定位方法大都針對二維空間，而在實際應(yīng)用中網(wǎng)絡(luò)節(jié)點主要分布在三維空間，因而較好的三維空間定位方法有著良好的發(fā)展前景。節(jié)點定位不但要考慮定位精度，而且要考慮定位成本和復(fù)雜度。目前國內(nèi)外針對此問題提出了多種算法。例如胡偉等人提出了一種基于四面體質(zhì)心迭代的三維近似三角形內(nèi)點測試(approximate point-in-triangle test, APIT)定位算法[1]，該算法雖提高了節(jié)點覆蓋率，減小了計算量，但是實驗過程較為復(fù)雜，不容易實現(xiàn)；印第安大學(xué)的Zhang等提出了一種Landscape-3D定位算法[2]，此方法節(jié)點間無需通訊，減小了功耗，但其存在即時迭代過程計算量大，LA裝置在移動過程中要嚴格保持同步等缺點；Zhang等[3]利用粒子群優(yōu)化(particle swarm optimization，PSO)算法進行節(jié)點定位，但此算法容易陷入局部最優(yōu)且計算比較復(fù)雜。此外還有多種測距和定位算法[4]以及DV-Hop定位算法和改進的混合蛙跳算法[5]。

本研究采用接收信號強度指標(biāo)(received signal strength indicator, RSSI)方法實現(xiàn)測距，并且對所測數(shù)據(jù)進行統(tǒng)計加權(quán)處理來減小環(huán)境等因素造成的測量誤差，建立起距離與信號強度之間精確的衰減模型，然后用螢火蟲算法對未知節(jié)點進行定位，并且與傳統(tǒng)的四邊測量算法[6]以及交叉粒子群算法[7]和遺傳算法[8]進行對比，結(jié)果表明，螢火蟲算法的定位精度明顯高于四邊測量算法、交叉粒子群算法和模擬退火算法，并且四點定位分八次測量再取均值的方法誤差最小，定位精度最優(yōu)。

1 RSSI測距

1.1 RSSI測距原理

無線信號傳輸過程中，信號強度會隨著距離的增大而衰減。因此，接收信號強度指示(RSSI)測距原理是將信號強度的衰減轉(zhuǎn)變成信號的傳播距離，利用信號強度的衰減與傳播距離之間的函數(shù)關(guān)系來估測傳播距離[9，10]。

通常信號衰減模型采用對數(shù)——常態(tài)分布模型來獲得距離信息，但在實際測量時，通常將上述模型轉(zhuǎn)換為陰影模型，如下式所示：

RSSI=-10n×lgd+A

(1)

式中，RSSI為接收信號強度，單位為dBm；n為衰減因子，其值與環(huán)境有關(guān)；d為接收端與發(fā)射端之間的距離，單位為m；A為信號傳播單位距離時接收到的信號強度，顯然，A與n的值決定了RSSI與d的大小。

1.2 數(shù)據(jù)的統(tǒng)計加權(quán)

由于RSSI測量結(jié)果容易隨環(huán)境變化而產(chǎn)生誤差，因此有必要對測量數(shù)據(jù)進行加權(quán)處理以減小其誤差[11]。

本文提出了一種利用測量中值對數(shù)據(jù)進行統(tǒng)計加權(quán)處理的方法。設(shè)每組數(shù)據(jù)測量次數(shù)為n，然后將數(shù)據(jù)按照從小到大順序排列，因此數(shù)據(jù)中值定義如下式所示：

(2)

MRSSI即為測量中值，再求出各個RSSI值和測量中值之間的方差，如下式所示：

Di=(RSSIi-MRSSI)2

(3)

為了避免方差為零，進行加權(quán)系數(shù)處理，Pi為加權(quán)系數(shù)，用下式表示：

(4)

對加權(quán)系數(shù)進行求和處理，F(xiàn)i為歸一化加權(quán)系數(shù)，用下式表示：

(5)

由式(3)、(4)、(5)可以看出，測得的RSSI值與測量中值MRSSI相差越大，加權(quán)系數(shù)Fi的值越小，即所占比重越?。划?dāng)RSSI值與MRSSI值相等時，加權(quán)系數(shù)Fi值最大，此時RSSI值被賦予最大權(quán)重。

此方法的優(yōu)點在于以測量中值為基礎(chǔ)計算權(quán)值，將包含粗大誤差結(jié)果的RSSI值賦予很小的權(quán)值，累加時可以忽略，這樣既沒有簡單的刪掉粗差數(shù)據(jù)，又能濾除一部分粗大信號，使得RSSI測距方法能夠適應(yīng)更加復(fù)雜的環(huán)境。

2 螢火蟲算法

2.1 螢火蟲算法簡介

螢火蟲算法(firefly algorithm,FA)是由劍橋?qū)W者Yang在2009年提出的一種基于生物群智能的隨機優(yōu)化算法[12]，隨后應(yīng)用在尋優(yōu)問題上，并能夠成功尋找到函數(shù)最優(yōu)解。

2.2 螢火蟲算法實現(xiàn)定位

螢火蟲之間均可以相互吸引，且由亮度低的向亮度高的靠近，發(fā)光強度由目標(biāo)函數(shù)決定[13,14]。

(6)

f(x, y, z)=

(7)

(8)

程序執(zhí)行步驟如下：

步驟1：獲取錨節(jié)點與未知節(jié)點間距離。

步驟2：初始化螢火蟲種群，在指定范圍內(nèi)隨機分布螢火蟲。

步驟3：計算目標(biāo)函數(shù)值，目標(biāo)函數(shù)越優(yōu)，則自身亮度越高，螢火蟲所處位置越好。

步驟4：比較螢火蟲之間的發(fā)光亮度，更新螢火蟲位置產(chǎn)生新解，如果迭代次數(shù)到達設(shè)定值，跳至步驟6。

步驟5：計算目標(biāo)函數(shù)值，跳至步驟4。

步驟6：輸出結(jié)果，程序結(jié)束。

3 實驗分析

3.1 RSSI測距

測距實驗采用TI公司生產(chǎn)的CC2530開發(fā)板來實現(xiàn)測量兩節(jié)點之間的RSSI值。一般情況下，無線傳感網(wǎng)絡(luò)部署地區(qū)大多數(shù)在戶外進行，因此本實驗也選擇在戶外測取數(shù)據(jù)。實驗一共測得50m內(nèi)的RSSI值，由于距離較短時衰減變化比較明顯，當(dāng)距離較遠，到達一定程度時，衰減變化不大，因此前30m每隔1m測量一次，后20m每隔4m測量一次。實驗硬件和測量現(xiàn)場如圖1、圖2所示。

圖1 zigbee CC2530硬件開發(fā)板

圖2 測量現(xiàn)場圖

實驗時，每個位置測量30組數(shù)據(jù)，然后按照上述方法對數(shù)據(jù)進行統(tǒng)計加權(quán)處理，得到表1所示的數(shù)據(jù)。

表1 距離-RSSI值數(shù)據(jù)表

將所得數(shù)據(jù)帶入式(1)，利用最小二乘法求出A與n的值為：A=-31.1949，n=2.5552，因此得到RSSI值與距離d之間的關(guān)系如下所示：

RSSI=-10×2.5552×lgd-31.1949

(9)

得到的原始數(shù)據(jù)和擬合曲線如圖3所示。

圖3 擬合曲線圖

由圖3擬合曲線圖可以看出，得到的擬合曲線基本上和原數(shù)據(jù)點一致，并且擬合曲線斜率隨著距離的增大而減小，說明RSSI值在距離較短階段變化十分明顯，而隨著距離的增加，斜率變小，擬合曲線趨于平緩，RSSI值也趨于穩(wěn)定。圖4是相對誤差圖，從圖4可以看出，原始數(shù)據(jù)和得到的擬合曲線上的數(shù)據(jù)，誤差基本上都在5%以內(nèi)。因此采用上述統(tǒng)計中值加權(quán)的處理方法，能夠有效地減小誤差，適應(yīng)環(huán)境變化。

圖4 相對誤差圖

使用zigbeeCC2530節(jié)點進行測距實驗。該方法簡單，成本低廉，利用干電池能夠工作半年以上，并且經(jīng)過仿真驗證，精度較高，因此，用此方法進行測距實驗?zāi)軌蛟谳^低成本的情況下，獲得較高的精確度，是一種很不錯的定位測距方法。

3.2 螢火蟲算法定位

由于高度受限，太高的地方無法進行節(jié)點設(shè)置，因此本實驗在30m×30m×3m的長方體區(qū)域內(nèi)進行，如圖5所示。實驗現(xiàn)場圖如圖6、圖7所示。

圖5 實驗節(jié)點設(shè)置圖

圖6 節(jié)點高度設(shè)置圖

圖7 現(xiàn)場整體布局圖

表2 定位數(shù)據(jù)表

首先協(xié)調(diào)器節(jié)點與電腦相連，建立無線傳感器網(wǎng)路，隨后，作為終端發(fā)射信號的未知節(jié)點和作為路由器的8個錨節(jié)點打開，開始加入網(wǎng)絡(luò)。未知節(jié)點發(fā)射信號，8個錨節(jié)點接收信號，將自己接收到的信號強度傳遞給協(xié)調(diào)器節(jié)點并在電腦上顯示[15]。

本文先選取A、E、F、H 4個點(選取點的原則為4點不共面，且未知節(jié)點在4點所構(gòu)成的區(qū)域內(nèi))對未知節(jié)點N進行定位，將螢火蟲數(shù)量設(shè)置為30，迭代次數(shù)為200，用MATLAB仿真的效果如圖8所示。

圖8 螢火蟲初始分布圖

圖9 螢火蟲最終分布圖

接下來，用8個錨節(jié)點共同為未知節(jié)點定位，本次將螢火蟲數(shù)量設(shè)置為60，迭代次數(shù)設(shè)置為300，仿真效果圖如圖10所示。

圖10 螢火蟲初始分布圖

圖11 螢火蟲最終分布圖

3.3 對比實驗分析

依據(jù)上述仿真實驗，當(dāng)錨節(jié)點個數(shù)分別設(shè)置為4,5,6,7,8時(每個錨節(jié)點只利用一次，一起進行定位；當(dāng)錨節(jié)點個數(shù)取8時，區(qū)別于上述8組四個節(jié)點平均值的方法)，螢火蟲定位算法與交叉粒子群算法和遺傳算法相比較，如圖12所示。

從圖12可以看出，螢火蟲算法相比于這兩種智能算法有著更精確的定位精度，將8組4個節(jié)點螢火蟲定位算法與傳統(tǒng)的四邊定位算法加入對比，得到的比較結(jié)果如表3所示。

圖12 三種算法對比圖

算法名稱錨節(jié)點數(shù)定位坐標(biāo)定位誤差(m)四邊測量定位法4(12.15,15.55,0.95)3.09交叉粒子群算法8(15.34,18.72,1.07)1.62遺傳算法8(15.28,18.16,2.23)1.88單次四個節(jié)點螢火蟲定位算法4(15.31,21.13,1.19)1.42八個節(jié)點螢火蟲定位算法8(15.12,21.26,2.4)1.23八組四個節(jié)點螢火蟲定位算法平均值8(15.07,20.57,2.13)0.59

經(jīng)比較，采用8組四個節(jié)點螢火蟲定位算法平均值，不但充分利用上了全部8個錨節(jié)點，并且定位精度要遠遠高于傳統(tǒng)的四邊定位算法以及交叉粒子群算法和遺傳算法的智能算法，相比于單次四個節(jié)點螢火蟲定位方法和八個節(jié)點螢火蟲定位方法，能夠有效地將定位誤差控制在1 m以內(nèi)，因此效果最好。

4 結(jié) 論

本文主要提出了一種基于三維空間無線傳感網(wǎng)絡(luò)的螢火蟲定位算法，打破了二維空間定位算法的局限性。該算法首先用RSSI方法對錨節(jié)點和未知節(jié)點之間進行測距，得到穩(wěn)定的擬合曲線，然后利用加權(quán)算法處理誤差，最后在此基礎(chǔ)上利用測距結(jié)果使用螢火蟲算法對未知節(jié)點進行定位。經(jīng)過仿真驗證，該算法相比于傳統(tǒng)的四邊定位算法以及交叉粒子群算法和遺傳算法，在定位精度上有了很大的提高，在30m×30m×3m的空間內(nèi)定位誤差僅為0.59m，對于分布在三維空間上的無線傳感網(wǎng)絡(luò)節(jié)點的定位具有很好的理論和實際意義。

[ 1] 胡偉, 朱西平, 文紅等. 基于四面體質(zhì)心迭代的三維 APIT 定位算法研究.傳感技術(shù)學(xué)報, 2013, 26(10): 1432-1436

[ 2] Zhang L, Zhou X, Cheng Q. Landscape-3D: a robust localization scheme for sensor networks over complex 3D terrains.Local Computer Network, 2006, 31st: 239-246

[ 3] Zhang Z, Cui H. Localization in 3D sensor networks using stochastic particle swarm optimization. Wuhan University Journal of Natural Sciences, 2012, 17(6): 544-548

[ 4] Dalce R, Val T, Bossche A. Comparison of indoor localization systems based on wireless communications. Wireless Engineering and Technology, 2011, (2):240-256

[ 5] 馮晨, 張玲華. 改進混合蛙跳算法在無線傳感網(wǎng)定位中的應(yīng)用. 計量學(xué)報, 2013, 34(004): 360-365

[ 6] 文舉, 金建勛, 袁海. 一種無線傳感器網(wǎng)絡(luò)四邊測距定位算法. 傳感器與微系統(tǒng), 2008, 27(5): 108-110

[ 7] 王俊, 李樹強, 劉剛. 無線傳感器網(wǎng)絡(luò)三維定位交叉粒子群算法. 農(nóng)業(yè)機械學(xué)報, 2014, 45(5): 233-238

[ 8] 王金鑫, 賴旭芝, 吳敏. 基于遺傳算法的三維無線傳感器網(wǎng)絡(luò)定位新算法. 高技術(shù)通訊, 2008, 18(6): 579-584

[ 9] 徐世武, 王平. ZigBee 技術(shù)中基于 RSSI 測距的定位算法研究.單片機與嵌入式系統(tǒng)應(yīng)用, 2012, 12(1): 1-3

[10] Zhu X, Feng Y. RSSI-based algorithm for indoor localization. Communications and Network, 2013, 5(02): 37-42

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

[12] Yang X S. Firefly algorithms for multimodal optimization.Stochastic algorithms: foundations and applications. Springer Berlin Heidelberg, 2009. 169-178

[13] 高偉明. 螢火蟲算法的研究與應(yīng)用：[碩士學(xué)位論文]. 蘭州：蘭州大學(xué), 2013. 18-22

[14] 王吉權(quán), 王福林. 螢火蟲算法的改進分析及應(yīng)用. 計算機應(yīng)用, 2014, 34(9): 2552-2556

[15] 王瑛輝, 石理碧, 孫堅. 基于 ZigBee 技術(shù)的無線傳感器網(wǎng)絡(luò)在能源計量系統(tǒng)中的應(yīng)用. 計量技術(shù), 2013, 11: 30-32

Research on a firefly localization algorithm based on RSSI ranging for 3D wireless sensor networks

Zhang Liguo, Ma Peng, Jin Mei, Fan Meichang, Liu Yuhao

(Measurement Technology and Instrumentation Key laboratory of Hebei Province,Yanshan University, Qinhuangdao 066004)

The techniques of localizing the unknown nodes of 3D wireless sensor networks (WSN) were studied. Aiming at the problem of low localization accuracy of current localization algorithms for 3D wireless sensor networks, a firefly localization algorithm based on the ranging using received signal strength indication (RSSI) for 3D wireless sensor networks was proposed. The algorithm uses RSSI to measure the signal-propagating distance and models the attenuation of signal strength with the signal-propagating distance, and then, uses the firefly algorithm to find the optimal value of the objective function to locate unknown nodes under the condition that a certain number of anchor nodes are known. The simulation results showed that the localization accuracy of the new localization algorithm was greatly higher than current algorithms, and its localizing error in the space of 10m×10m×10m was just 0.59m.

wireless sensor network (WSN), three-dimensional, received signal strength indication (RSSI), firefly algorithm (FA)

①河北省自然科學(xué)基金(F2015203392)和秦皇島市科技計劃(201502A043)資助項目。

2015-10-20)

10.3772/j.issn.1002-0470.2016.01.001

②男，1978年生，博士，副教授；研究方向：慣性導(dǎo)航，三維立體重構(gòu)及智能信號處理；聯(lián)系人，E-mail: zlgtime@163.com(