卞國龍， 黃海松， 王安憶， 魏 琴

(1.貴州大學(xué) a.現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，b.貴州省大數(shù)據(jù)產(chǎn)業(yè)發(fā)展應(yīng)用研究院，貴陽 550025; 2.中國海洋大學(xué) 工程學(xué)院，山東 青島 266100)

·計(jì)算機(jī)技術(shù)應(yīng)用·

無線傳感器網(wǎng)絡(luò)定位技術(shù)的研究

卞國龍1a， 黃海松1a， 王安憶2， 魏 琴1b

(1.貴州大學(xué) a.現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，b.貴州省大數(shù)據(jù)產(chǎn)業(yè)發(fā)展應(yīng)用研究院，貴陽 550025; 2.中國海洋大學(xué) 工程學(xué)院，山東 青島 266100)

提出了一種新的接收信號(hào)強(qiáng)度指示(RSSI)定位修正算法。該算法采用改進(jìn)的退火算法對極大似然估計(jì)處理后的距離進(jìn)行優(yōu)化，有效解決在實(shí)際環(huán)境中遇到的一些問題，使算法更符合實(shí)際。同時(shí)，能有效降低運(yùn)算的復(fù)雜度，并排除具有特征相似性的一些奇異點(diǎn)，提高精度。依據(jù)鄰近節(jié)點(diǎn)間的距離，分析前后兩組估計(jì)坐標(biāo)間的關(guān)系，用目標(biāo)函數(shù)判斷兩組解的優(yōu)劣，由退火思想只接受比前一組優(yōu)的新解進(jìn)行迭代循環(huán)，可以得到一組移動(dòng)點(diǎn)的估計(jì)坐標(biāo)。將滿足條件的移動(dòng)點(diǎn)看做參考點(diǎn)，重復(fù)運(yùn)算, 直至沒有移動(dòng)點(diǎn)可以升為參考點(diǎn)為止, 輸出最終結(jié)果。實(shí)驗(yàn)結(jié)果表明, 改進(jìn)的算法有效可行，且定位精度和穩(wěn)定性有明顯的提高，是一種可行的節(jié)點(diǎn)定位方案。

節(jié)點(diǎn)定位； 無線網(wǎng)絡(luò)； 模擬退火法； 距離修正

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)技術(shù)得到了廣泛應(yīng)用[1]。定位技術(shù)是WSNs技術(shù)的重要研究方向，定位算法的研究已成為當(dāng)前的熱點(diǎn)方向?，F(xiàn)有的定位算法從定位手段上分為基于測距(range based)和非測距(range-free)兩大類[2]?；跍y距的算法需要節(jié)點(diǎn)有測距功能，利用節(jié)點(diǎn)間距離或角度信息，使用三角定位、三邊定位或極大估計(jì)等方法計(jì)算節(jié)點(diǎn)位置，主要算法有接收信號(hào)強(qiáng)度指示 (Received Signal Strength Indicator，RSSI)、基于到達(dá)時(shí)間 (TOA)、基于到達(dá)時(shí)間差 (TDOA)等；后者通過網(wǎng)絡(luò)的連通性定位，主要有質(zhì)心算法等[3]。由于目前的傳感器都有RSSI值讀取功能，可以通過RSSI算法計(jì)算節(jié)點(diǎn)距離，但RSSI值易受環(huán)境干擾，和通信半徑相比，測距的絕對誤差有時(shí)會(huì)達(dá)到40%。三邊定位算法是由移動(dòng)點(diǎn)測得與周圍3個(gè)參考點(diǎn)的距離，分別作3個(gè)圓，在理想情況下3圓交于一點(diǎn)，通過幾何計(jì)算可得移動(dòng)點(diǎn)坐標(biāo)，但由于噪聲的存在使得3個(gè)圓不能交于一點(diǎn)[4]。本文提出了RSSI 距離修正算法，在圓不相交的情況下提高定位的準(zhǔn)確性。同時(shí)針對移動(dòng)曲線受客觀因素影響導(dǎo)致不平緩，使準(zhǔn)確性和穩(wěn)定性受到影響等問題，引入一種改進(jìn)的模擬退火算法(Simulated Annealing，SA)來對估算出的位置坐標(biāo)信息處理。退火算法是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)的全局優(yōu)化算法，再通過距離修正進(jìn)行誤差補(bǔ)償[5]。通過實(shí)驗(yàn)證明該方法確實(shí)可行并能提高定位精度。

1 定位基礎(chǔ)原理

選用對數(shù)-正態(tài)分布模型，設(shè)環(huán)境中有n個(gè)移動(dòng)點(diǎn)，m個(gè)參考點(diǎn)，共N個(gè)節(jié)點(diǎn)。n個(gè)移動(dòng)點(diǎn)坐標(biāo)參數(shù)向量T=[Tx，Ty]，其中Tx= [x1，x2,…,xn]，Ty=[y1，y2,…,yn]。在節(jié)點(diǎn)a和b之間距離為d時(shí)接收功率Pab的分布可以表示為：

(1)

(2)

(3)

(4)

(5)

圖1 定位結(jié)構(gòu)原理圖

2 RSSI定位技術(shù)優(yōu)化

2.1 無線信號(hào)的傳輸模型

常用的模型有自由空間模型、對數(shù)-正態(tài)分布模型和哈它模型等。自由空間模型可表示為：

P(d)=32.4+10lgd+10nplgf

(6)

式中：d為接收點(diǎn)與發(fā)射點(diǎn)間距離；P(d)為距離d后的信號(hào)損耗，dB；np為路徑損耗指數(shù)；f為發(fā)射頻率，MHz。由于節(jié)點(diǎn)性能的分散性和環(huán)境的復(fù)雜性，在自由空間模型下誤差會(huì)較大，對數(shù)-正態(tài)分布模型更符合實(shí)際：

(7)

式中：Xδ是均值為0的高斯隨機(jī)變量；P(d0)為d=1 m時(shí)接收到的信號(hào)強(qiáng)度[8]。根據(jù)上式可得各點(diǎn)接收功率為：

RSSI=P+G-P(d)

(8)

式中：G為天線增益；P為發(fā)射功率，dB。通過接收到RSSI值和式(7)～(8)可計(jì)算距離d，從而實(shí)現(xiàn)定位。

圖2 RSSI值的變化曲線

2.2 卡爾曼初步濾波優(yōu)化

本文采用卡爾曼濾波(Kalman Filtering，KF)算法對RSSI值進(jìn)行初步處理，以減少誤差[9]。KF是通過消除噪聲影響后，用前一時(shí)刻的估算值和現(xiàn)在時(shí)刻的觀測值來更新狀態(tài)變量，以最小均方誤差來尋求遞推估計(jì)的計(jì)算方法。X表示RSSI值，KF算法分為預(yù)測狀態(tài)階段和修正估計(jì)階段兩部分。預(yù)測狀態(tài)階段為：

(9)

式中：X(k/k-1)為預(yù)測結(jié)果；X(k-1/k-1)為k時(shí)刻最優(yōu)狀態(tài)估算值；Yk為現(xiàn)在狀態(tài)的控制量，其值此時(shí)為0；Vk/k-1和E為系統(tǒng)參數(shù)，是矩陣；RX(k|k-1)是與之對應(yīng)的X( k|k-1)的協(xié)方差，為k時(shí)對下一時(shí)刻誤差估計(jì)的方差矩陣；P為系統(tǒng)噪聲，表示為

(10)

式中：Wk為k+1時(shí)的預(yù)測估算值；Gk為增益矩陣，能夠?qū)崟r(shí)更新；Mk為系統(tǒng)測量參數(shù)，是預(yù)測矩陣。每次Gk和R(k/k)通過前一時(shí)刻的值更新，通過遞歸估計(jì)直至達(dá)到收斂效果[11]。KF算法實(shí)時(shí)性好，當(dāng)模型參數(shù)的系統(tǒng)狀態(tài)比較穩(wěn)定時(shí)，能減少由噪聲疊加引起RSSI值偏離，濾波后的RSSI值更穩(wěn)定。

2.3 改進(jìn)模擬退火算法的優(yōu)化

模擬退火算法常用來解決最優(yōu)化問題，其基本思路原理為：將固體加熱至高溫，然后逐漸冷卻，加熱時(shí)，固體粒子隨溫度升高變的無序，內(nèi)能增加；冷卻時(shí)粒子逐漸變得有序，在每個(gè)時(shí)刻都達(dá)到平衡，最后在常溫下內(nèi)能最小[12]。將退火算法的原理應(yīng)用于定位中，得到基于模擬退火的定位算法。將內(nèi)能模擬為成本函數(shù)E，溫度T模擬為控制參數(shù)t。對于t的每次取值，都比較新舊解的成本函數(shù)，以決定是否接受新解，經(jīng)過大量解變換后，可得最終解。

(1) 成本函數(shù)。表示移動(dòng)點(diǎn)當(dāng)前估計(jì)坐標(biāo)的符合情況，其值越小越符合實(shí)際：

(11)

(12)

在增加距離修正系數(shù)的基礎(chǔ)上，定義新的約束條件：

(13)

加入約束條件，可以減小移動(dòng)點(diǎn)的可行域。因?yàn)閮?yōu)化的結(jié)果即要使計(jì)算距離與測量值盡量吻合，所以要使定位結(jié)果滿足下式：

(14)

則引入罰函數(shù)的構(gòu)造條件，新生成的成本函數(shù)為：

(15)

式中：R為懲罰因子。如果測量誤差超過平均誤差，則所求解遠(yuǎn)離正確值，此時(shí)要加大懲罰使其向可行解靠近。

(2) 新解的更新。解指的是所有移動(dòng)點(diǎn)估算坐標(biāo)的集合，在當(dāng)前解中，隨機(jī)選擇節(jié)點(diǎn)i，然后沿方向θ移動(dòng)距離L，此時(shí)i得到一個(gè)新坐標(biāo)。將節(jié)點(diǎn)i的當(dāng)前估算坐標(biāo)用新坐標(biāo)代替，其余節(jié)點(diǎn)保持不變，此時(shí)可得新解。為了優(yōu)化搜索范圍，當(dāng)控制參數(shù)t逐漸減少時(shí)，L也會(huì)減少：

(16)

式中：L為步長，隨迭代次數(shù)增加而減小，L>0；c為縮放系數(shù)，0

(17)

(18)

式中：eij為單位方向矢量，eij=(Qi-Qj)/Dij，Qi、Qj為節(jié)點(diǎn)i與j的坐標(biāo)；集合I為節(jié)點(diǎn)距小于通信半徑r的節(jié)點(diǎn)集合，I={j|dij

(3) 控制參數(shù)t的變化表示為：

(19)

式中：t為控制參數(shù)，隨迭代次數(shù)增加而減小，t>0；t0為初始控制參數(shù)；j為迭代次數(shù)；z為衰減系數(shù)，0

(20)

式中：aveΔE為ΔE>0時(shí),ΔE的平均值，其值為aveΔE=VΔE/NΔE。設(shè)初始L0=1，VΔE0=0，NΔE0=0，VΔE為ΔE>0時(shí)ΔE值之和，NΔE為ΔE>0的次數(shù)。

(21)

(22)

Ei為在狀態(tài)i時(shí)的成本函數(shù)，則系統(tǒng)處在狀態(tài)i的概率，即退火算法找到一個(gè)解i∈s的概率為：

(23)

由上式可知,得到的概率分布函數(shù)為平穩(wěn)分布。H0(t)為歸一化因子，可由下式求得：

(24)

由準(zhǔn)則可知，在迭代中不僅接受使成本函數(shù)變優(yōu)的值，還有概率接受使其變差的值，由此可以擴(kuò)大初始搜索范圍。隨著t減小，搜索范圍也變小，使新解保持在全局最優(yōu)附近[15]。同時(shí)在設(shè)置條件閾值的基礎(chǔ)上，通過局部更新，對解空間進(jìn)行搜索，保留下式中S1的有效解，新解空間需滿足下式：

(25)

(26)

式中：sji表示ti下的第j個(gè)節(jié)點(diǎn)的解值。采用局部更新方式進(jìn)行退火更新，直至極值空間不連續(xù)，并對獲得的解迭代演算，如果解空間光滑，則停止迭代?；诟倪M(jìn)退火定位算法的運(yùn)算步驟如下：

步驟2 隨機(jī)選擇一個(gè)移動(dòng)點(diǎn)，根據(jù)式(17)得該點(diǎn)新坐標(biāo)。

步驟3 由式(15)計(jì)算新解和當(dāng)前解的成本函數(shù)，并計(jì)算差值ΔE。

步驟4 根據(jù)規(guī)則，決定是否接受新解。如果不接受，解集合不變；如果接受，則更新解集合中擾動(dòng)點(diǎn)坐標(biāo)[16]。如果樣本坐標(biāo)值sj滿足

則更新當(dāng)前解si；j=j+1，重復(fù)步驟4至滿足條件。

步驟6 當(dāng)達(dá)到終止條件時(shí)，算法終止。t改變一次表示一次迭代，L與t同步。此時(shí)的解即為所有移動(dòng)點(diǎn)的估算坐標(biāo)的解集合。

2.4 迭代結(jié)果統(tǒng)計(jì)

在二維區(qū)域內(nèi)隨機(jī)布置多個(gè)參考點(diǎn)和移動(dòng)點(diǎn)，假設(shè)移動(dòng)點(diǎn)與參考點(diǎn)間的測量距離誤差服從高斯分布。分別采用2種算法，設(shè)置溫度初始參數(shù)T=1.0，c=0.96，迭代次數(shù)為退火算法搜索的最大次數(shù)，在測距誤差為6%的條件下，取迭代次數(shù)為100進(jìn)行定位實(shí)驗(yàn)，結(jié)果如圖3所示?？梢钥闯觯?dāng)?shù)螖?shù)大于50次時(shí)，曲線趨于緩和，綜合考慮定位節(jié)點(diǎn)的能耗、成本和精度，最大迭代次數(shù)可選擇為50次。

圖3 退火算法的迭代變化曲線

3 實(shí)驗(yàn)結(jié)果驗(yàn)證

3.1 定位實(shí)驗(yàn)結(jié)果與分析

分別用傳統(tǒng)的最小二乘法和優(yōu)化后退火定位法對節(jié)點(diǎn)多次定位，并統(tǒng)計(jì)多次平均誤差，對誤差進(jìn)行比較。實(shí)驗(yàn)場景設(shè)置為25 m×25 m，通信半徑為15 m，參考節(jié)點(diǎn)數(shù)為8個(gè)，移動(dòng)點(diǎn)為15個(gè)，對每個(gè)移動(dòng)點(diǎn)多次測量求均值，實(shí)驗(yàn)結(jié)果如圖4、5所示。

圖4 實(shí)驗(yàn)環(huán)境二維圖

圖5 定位結(jié)果統(tǒng)計(jì)圖

由定位結(jié)果計(jì)算，可得兩種算法的定位誤差如表1所示。通過分析實(shí)驗(yàn)結(jié)果可得改進(jìn)后退火算法比基于最小二乘法的RSSI算法更具有精確性。

表1 實(shí)驗(yàn)結(jié)果分析表

3.2 不同連通度下誤差分析

網(wǎng)絡(luò)連通度可看做網(wǎng)絡(luò)通信范圍的大小，通信范圍越大，連通度越好，能檢測到的節(jié)點(diǎn)越多。在連通度較低時(shí)達(dá)到較高的精度和減小連通度對誤差的影響是定位的重要研究方向。在實(shí)驗(yàn)環(huán)境布置12個(gè)參考點(diǎn)，15個(gè)移動(dòng)點(diǎn)，通信半徑R=10 m，計(jì)算移動(dòng)點(diǎn)坐標(biāo)，重復(fù)測量，獲得多次誤差結(jié)果并對誤差統(tǒng)計(jì)，比較以下3種算法的性能。由圖6可知，改進(jìn)的退火算法受連通度影響更小，在連通度較小時(shí)即可獲得較高精度。

3.3 不同算法的定位覆蓋率

在定位中，能定位出的節(jié)點(diǎn)數(shù)占所有移動(dòng)節(jié)點(diǎn)的比例為定位覆蓋率。在實(shí)驗(yàn)環(huán)境下，移動(dòng)點(diǎn)個(gè)數(shù)為15個(gè)，參考點(diǎn)數(shù)目改變，3種不同算法覆蓋率變化如圖7所示?？梢钥闯觯S著參考節(jié)點(diǎn)比例增加，現(xiàn)有的RSSI算法的覆蓋率也會(huì)增加，但變化較緩慢；而改進(jìn)的退火算法在參考點(diǎn)數(shù)較少時(shí)就能覆蓋全部，減少了系統(tǒng)的復(fù)雜程度。

圖6 不同連通度下的定位誤差

圖7 參考點(diǎn)比例對覆蓋率的影響

4 結(jié) 語

通過對智能優(yōu)化算法在定位中的應(yīng)用進(jìn)行研究，用組合優(yōu)化的方法對定位問題進(jìn)行了分析。RSSI算法是無線定位中成本較低且普遍使用的方法，但易受干擾。研究分析了引起誤差的環(huán)境因素，該算法首先利用RSSI算法收集節(jié)點(diǎn)間的信息和距離估計(jì)，并優(yōu)選參考點(diǎn)，采用模擬退火法和極大似然法有效結(jié)合，在極大似然法的基礎(chǔ)上引入退火算法求初始解，增加初值的準(zhǔn)確性，有效解決了精度受其他客觀因素影響的問題。最后通過實(shí)驗(yàn)分析各種因素的影響并進(jìn)行比較，結(jié)果顯示無論是定位精度還是執(zhí)行時(shí)間都有所提高。下一階段將研究測距誤差對算法的影響及其改進(jìn)策略。

[1] Vempaty A, Ozdemir O, Agrawal K,etal.Localization in wireless sensor networks:Byzantines and mitigation techniques[J].IEEE Journal and Magazines, 2013, 61(6):1495-1508.

[2] Yu F C, Hu G M, Park S,etal. Quorum based sink location service for irregular wireless sensor networks[J]. Computer Communications, 2012, 35(12): 1422-1432.

[3] Redondi A, Chirico M, Borsani L.An integrated system based on wireless sensor networks of patient monitoring, localization and tracking[J].AD Hoc Networks, 2013, 11(1):39-53.

[4] Ahmed N, Rutten M, Bessell T,etal. Detection and tracking using particle-filter-based wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2010,9(9):1332-1345.

[5] 閆明明,郭 濤,鮑愛達(dá).基于ARM的無線溫度傳感器網(wǎng)絡(luò)設(shè)計(jì)[J].實(shí)驗(yàn)室研究與探索,2014,33(3): 105-108.

[6] Kim S W,Lee J M,Lee J H.Distributed network localization for wireless sensor networks[J].Applied Mathematics &Information Sciences, 2012, 6(3):1109-1115.

[7] Deshpande N，Grant E.Target Localization and autonomous navigation using wireless sensor networks-a pseudogradient algorithm approach[J].IEEE Systems Journal，2014，8(1): 93-103.

[8] 李牧東,熊 偉,梁 青.基于人工蜂群改進(jìn)算法的無限傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào), 2013,26(2):241-245.

[9] Guillermo Molina, Enrique Alba. Location discovery in wireless sensor networks using metaheuristics[J]. Applied Soft Computing, 2011, 11(1): 1223-1240.

[10] 郭小軍. LM567及其在測距中的應(yīng)用[J].實(shí)驗(yàn)室研究與探索，2007，26(10): 22-23.

[11] Subhan F,Hasbullah H,Rozyyev A,etal.Handover in Bluetooth networks using signal parameters[J]. Information Technology Journal，2011，10(5): 965-973.

[12] Vecchio M, Lopez V R, Marcelloni F.A two-objective evolutionary approach based on topological constraints for node localization in wireless sensor networks [J].Applied Soft Computing,2012, 12(7):1891-1901.

[13] Güney E, Aras N, Kuban A,etal. Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks[J]. Computers Operations Research, 2012, 39(7): 1530-1539.

[14] 劉志華, 陳家興, 陳霄凱.無線傳感器網(wǎng)絡(luò)中序列定位新算法的研究[J] .電子學(xué)報(bào), 2010, 38(7):1552-1556.

[15] Fang S,Wang C.A Dynamic hybrid projection approach for improved Wi-Fi location fingerprinting[J].Vehicular Technology,IEEE Transactions on,2011,60(3):1037-1044.

[16] France S L, Carroll J D, Xiong H. Distance metrics for high dimensional nearest neighborhood recovery: compression and normalization[J].Information Sciences, 2012, 184(1): 92-110.

Research on Localization Technology of Wireless Sensor Networks

BIANGuolong1a,HUANGHaisong1a,WANGAnyi2,WEIQin1b

(1a. Key Laboratory of Advanced Manufacturing Technology, Ministry of Education; 1b. Guizhou Big Data Industry Research Institute, Guizhou University, Guiyang 550025, China; 2. College of Engineering, Ocean University of China, Qingdao 266100, Shandong, China)

The research of the current wireless location algorithms generally has exist the problems of low positioning accuracy and high computational complexity. A new RSSI location algorithm is proposed in this paper. The improved annealing algorithm is used to optimize the distance of the maximum likelihood estimation. It can effectively solve some of the problems encountered in the actual environment and make the algorithm more practical. At the same time, it can effectively reduce the complexity of computing. It rules out some singular points with characteristic similarity, which can improveso that the accuracy is improved. Based on the distance between adjacent nodes, the relationship between the two sets of estimated coordinates is analyzed. They can judge the advantages and disadvantages of the two sets of solutions with the objective function. By Because the annealing algorithm only accepts a previous group optimizational point to implement iteration, it can get the estimated coordinates of a set of mobile points, and can find the mobile point which meets the conditions as a reference point. Then the operation is repeated until no moving point can be raised as a reference point, and the final result is outputted. The experimental results show that the improved algorithm is effective and feasible. The positioning accuracy and stability are obviously improved. It is a feasible node localization scheme.

node localization; wireless network; simulated annealing method; distance correction

2016-08-21

國家自然科學(xué)基金項(xiàng)目(51475097)；國家科技支撐計(jì)劃項(xiàng)目(2014BAH05F01)；貴州省科技基金項(xiàng)目(黔科合J字[2015]2043)；貴州省科技支撐計(jì)劃(黔科合GZ字[2015]3034);貴州省基礎(chǔ)研究重大專項(xiàng)(黔科合JZ字[2014]2001)

卞國龍(1989-)，男，山東濰坊人，碩士生，主要研究方向?yàn)闄C(jī)械自動(dòng)化，制造物聯(lián)。

Tel.：18302639061;E-mail:1099205144@qq.com

黃海松(1977-)，女，貴州大方人，博士，教授，博士生導(dǎo)師，主要研究方向?yàn)橹圃鞓I(yè)信息化，先進(jìn)制造技術(shù)。

TP 391

A

1006-7167(2017)06-0122-06