無線傳感器網絡定位技術的研究

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

(1.貴州大學 a.現代制造技術教育部重點實驗室，b.貴州省大數據產業發展應用研究院，貴陽 550025; 2.中國海洋大學 工程學院，山東 青島 266100)

·計算機技術應用·

無線傳感器網絡定位技術的研究

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

(1.貴州大學 a.現代制造技術教育部重點實驗室，b.貴州省大數據產業發展應用研究院，貴陽 550025; 2.中國海洋大學 工程學院，山東 青島 266100)

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

節點定位； 無線網絡； 模擬退火法； 距離修正

0 引 言

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

1 定位基礎原理

選用對數-正態分布模型，設環境中有n個移動點，m個參考點，共N個節點。n個移動點坐標參數向量T=[Tx，Ty]，其中Tx= [x1，x2,…,xn]，Ty=[y1，y2,…,yn]。在節點a和b之間距離為d時接收功率Pab的分布可以表示為：

(1)

(2)

(3)

(4)

(5)

圖1 定位結構原理圖

2 RSSI定位技術優化

2.1 無線信號的傳輸模型

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

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

(6)

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

(7)

式中：Xδ是均值為0的高斯隨機變量；P(d0)為d=1 m時接收到的信號強度[8]。根據上式可得各點接收功率為：

RSSI=P+G-P(d)

(8)

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

圖2 RSSI值的變化曲線

2.2 卡爾曼初步濾波優化

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

(9)

式中：X(k/k-1)為預測結果；X(k-1/k-1)為k時刻最優狀態估算值；Yk為現在狀態的控制量，其值此時為0；Vk/k-1和E為系統參數，是矩陣；RX(k|k-1)是與之對應的X( k|k-1)的協方差，為k時對下一時刻誤差估計的方差矩陣；P為系統噪聲，表示為

(10)

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

2.3 改進模擬退火算法的優化

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

(1) 成本函數。表示移動點當前估計坐標的符合情況，其值越小越符合實際：

(11)

(12)

在增加距離修正系數的基礎上，定義新的約束條件：

(13)

加入約束條件，可以減小移動點的可行域。因為優化的結果即要使計算距離與測量值盡量吻合，所以要使定位結果滿足下式：

(14)

則引入罰函數的構造條件，新生成的成本函數為：

(15)

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

(2) 新解的更新。解指的是所有移動點估算坐標的集合，在當前解中，隨機選擇節點i，然后沿方向θ移動距離L，此時i得到一個新坐標。將節點i的當前估算坐標用新坐標代替，其余節點保持不變，此時可得新解。為了優化搜索范圍，當控制參數t逐漸減少時，L也會減少：

(16)

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

(17)

(18)

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

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

(19)

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

(20)

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

(21)

(22)

Ei為在狀態i時的成本函數，則系統處在狀態i的概率，即退火算法找到一個解i∈s的概率為：

(23)

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

(24)

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

(25)

(26)

式中：sji表示ti下的第j個節點的解值。采用局部更新方式進行退火更新，直至極值空間不連續，并對獲得的解迭代演算，如果解空間光滑，則停止迭代。基于改進退火定位算法的運算步驟如下：

步驟2 隨機選擇一個移動點，根據式(17)得該點新坐標。

步驟3 由式(15)計算新解和當前解的成本函數，并計算差值ΔE。

步驟4 根據規則，決定是否接受新解。如果不接受，解集合不變；如果接受，則更新解集合中擾動點坐標[16]。如果樣本坐標值sj滿足

則更新當前解si；j=j+1，重復步驟4至滿足條件。

步驟6 當達到終止條件時，算法終止。t改變一次表示一次迭代，L與t同步。此時的解即為所有移動點的估算坐標的解集合。

2.4 迭代結果統計

在二維區域內隨機布置多個參考點和移動點，假設移動點與參考點間的測量距離誤差服從高斯分布。分別采用2種算法，設置溫度初始參數T=1.0，c=0.96，迭代次數為退火算法搜索的最大次數，在測距誤差為6%的條件下，取迭代次數為100進行定位實驗，結果如圖3所示。可以看出，當迭代次數大于50次時，曲線趨于緩和，綜合考慮定位節點的能耗、成本和精度，最大迭代次數可選擇為50次。

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

3 實驗結果驗證

3.1 定位實驗結果與分析

分別用傳統的最小二乘法和優化后退火定位法對節點多次定位，并統計多次平均誤差，對誤差進行比較。實驗場景設置為25 m×25 m，通信半徑為15 m，參考節點數為8個，移動點為15個，對每個移動點多次測量求均值，實驗結果如圖4、5所示。

圖4 實驗環境二維圖

圖5 定位結果統計圖

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

表1 實驗結果分析表

3.2 不同連通度下誤差分析

網絡連通度可看做網絡通信范圍的大小，通信范圍越大，連通度越好，能檢測到的節點越多。在連通度較低時達到較高的精度和減小連通度對誤差的影響是定位的重要研究方向。在實驗環境布置12個參考點，15個移動點，通信半徑R=10 m，計算移動點坐標，重復測量，獲得多次誤差結果并對誤差統計，比較以下3種算法的性能。由圖6可知，改進的退火算法受連通度影響更小，在連通度較小時即可獲得較高精度。

3.3 不同算法的定位覆蓋率

在定位中，能定位出的節點數占所有移動節點的比例為定位覆蓋率。在實驗環境下，移動點個數為15個，參考點數目改變，3種不同算法覆蓋率變化如圖7所示。可以看出，隨著參考節點比例增加，現有的RSSI算法的覆蓋率也會增加，但變化較緩慢；而改進的退火算法在參考點數較少時就能覆蓋全部，減少了系統的復雜程度。

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

圖7 參考點比例對覆蓋率的影響

4 結 語

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

[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] 閆明明,郭 濤,鮑愛達.基于ARM的無線溫度傳感器網絡設計[J].實驗室研究與探索,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].傳感技術學報, 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及其在測距中的應用[J].實驗室研究與探索，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] 劉志華, 陳家興, 陳霄凱.無線傳感器網絡中序列定位新算法的研究[J] .電子學報, 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

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

卞國龍(1989-)，男，山東濰坊人，碩士生，主要研究方向為機械自動化，制造物聯。

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

黃海松(1977-)，女，貴州大方人，博士，教授，博士生導師，主要研究方向為制造業信息化，先進制造技術。

TP 391

A

1006-7167(2017)06-0122-06