小波變換預測移動節點定位算法*

徐澤坤，單志龍

（華南師范大學計算機學院，廣州510631）

小波變換預測移動節點定位算法*

徐澤坤，單志龍*

（華南師范大學計算機學院，廣州510631）

針對無線傳感器網絡移動節點定位精度不高的問題，提出一種基于小波變換預測的移動節點定位算法。根據歷史運動軌跡通過小波變換預測節點當前位置，精確采樣區域，應用自適應采樣方法減少采樣次數，通過加權濾波增大高質量樣本點以及降低低質量樣本點對定位結果的影響，提高定位精度。仿真結果表明，在錨節點數目、通信半徑、最大樣本點數目等條件變化的情況下，該算法與傳統算法相比提高了定位精度，在低錨節點密度環境下表現出良好的效果。

無線傳感器；移動定位；小波變換；運動預測；蒙特卡羅

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.04.017

無線傳感器網絡［1］是由大量具有無線通信功能的傳感器節點通過自組織方式形成的網絡系統，廣泛地應用在實時追蹤、軍事偵測、森林火災偵測等領域。其中，定位技術是無線傳感器網絡的關鍵技術，如何實現高準確率、高效的定位技術一直是無線傳感器網絡領域的研究熱點。

根據定位機制，無線傳感器網絡定位算法可分為基于測距技術和基于非測距技術兩大類。基于測距技術的算法需要測量節點與節點之間的距離或角度，需要額外的硬件支撐，例如接受信號強度（RSSI）、信號到達時間（TOA）［2］、信號到達時間差（TDOA）［3］等。基于非測距技術的算法根據節點的連通性和多跳路由信息交換實現節點定位，如DV-Hop算法［4］、APIT算法［5］、質心算法［6］，定位成本更低。但是，受移動環境下節點拓撲結構動態變化的影響，上述算法在移動定位中表現不佳。

針對節點的移動性，Hu［7］等首次將序列蒙特卡羅法引入到無線傳感器定位，提出了適用于移動節點的蒙特卡羅定位MCL（Monte Carlo Localization）算法。Baggio［8］等在MCL算法的基礎上提出了蒙特卡羅盒MCB（Monte Carlo Localization Boxed）算法，通過定義錨盒和采樣盒提高采樣成功率和定位精度。單志龍［9］等利用灰度預測推算待定位節點下一時刻的可能位置區域，同時通過限制性線性交叉操作生成新的樣本點，減少采樣次數。Adnan［10］等提出了負約束（negative constraint）的概念，排除非鄰居錨節點通信范圍內的區域，縮小了采樣區域。王潔［11］等利用遺傳交叉思想加速樣本生成，同時通過減少采樣區域提高樣本質量。Wang［12］等根據節點前后時刻拓撲結構的變化優化采樣區域，提高定位精度。

上述算法在低錨節點密度環境定位誤差均較大，針對此問題，本文提出了基于小波變換預測的移動節點定位 WPL（Wavelet Transform Prediction Localization）算法。該算法利用小波變換對待定位節點歷史運動軌跡作平穩化處理，結合AR模型預測節點位置，根據采樣盒面積自適應采集樣本點，從而提高定位精度。仿真結果表明，本文算法在低錨節點密度環境下表現出良好的效果。

1　MCB算法分析

MCB算法在預測階段引入了錨盒和采樣盒。假設待定位節點在當前時刻接收到n個一跳錨節點，錨節點 j的坐標表示為（xj，yj），則錨盒Boxt=｛（xmin，ymin）；（xmax，ymax）｝的左下角坐標為（xmin，ymin），右上角坐標為（xmax，ymax），其中:

r是節點通信半徑，當錨節點j是二跳錨節點時，用2r代替r。

采樣盒構建完成后，在采樣區進行采樣，然后對采集到的樣本點進行濾波。根據待定位節點當前時刻收到的觀察信息，丟棄不在一跳錨節點和二跳錨節點通信范圍內的樣本點。然后進入重采樣階段，重新在采樣區采集樣本點，再進行濾波，直到通過濾波條件的有效樣本點數目達到給定的最大樣本點數。最后，計算樣本點的均值作為待定位節點當前時刻的估計位置。

MCB算法引入了錨盒和采樣盒，縮小了采樣區域，顯著地提高了采樣成功率以及降低了定位能耗。然而，MCB算法仍然存在一些缺陷:①在錨節點稀疏的情況下，采樣區域仍然非常大，定位誤差大；②最大樣本點數目固定，在采樣區域較小的情況下，大量的樣本點無助于提高定位精度，反而浪費內存和計算開銷；③僅僅利用了節點當前時刻和上一時刻的信息，并沒有利用到對定位精度提高有幫助的節點歷史運動軌跡；④過濾后所得的樣本點全部賦予一樣的權值，沒有利用樣本點之間的差異提高定位精度。

2　WPL算法

WPL算法通過小波變換預測估算待定位節點的運動狀況，進一步縮小采樣區域，提高定位精度；采用自適應采樣，在保障定位準確率的情況下，降低定位能耗，延長網絡壽命；根據樣本點的位置賦予不同的權值，降低低質量樣本點對定位結果的影響，提高定位精度。

2.1小波變換預測

無線傳感器的運動軌跡在短時間內可以看作是平滑連續的，當前時刻位置與前幾個時刻位置有關，可以利用前幾個時刻的位置信息預測節點當前時刻位置，因此，節點的歷史運動軌跡可以看作是一個基于位置的時間序列｛xt-n，xt-n+1，…，xt-1｝。傳統的時間序列預測模型有ARMA模型［13］、AR模型［14］等。AR（n）模型可表示為:

其中，xt-1，xt-2，…，xt-n為時間序列前n個時刻的值；φ1，φ2，…，φn為表示xt依賴于過去程度的自回歸系數；αt為滿足均值為0、方差為的正態分布隨機干擾項；n為模型的階數。

AR模型適用于平穩時間序列預測，然而現實中的時間序列通常是非平穩的時間序列，因此，對時間序列建立AR（n）模型前，須進行平穩化處理。常用的平穩化處理方法是差分操作，然而，差分處理會在濾掉時間序列變化相對緩慢趨勢項的同時，把低頻部分平穩的隨機序列信息也過濾掉。本文使用小波變換對時間序列作平穩化處理，通過小波變換，把一個非平穩的時間序列分解為多個較平穩的高頻信號和一個比原序列平滑的低頻信號，從而把趨勢項分離到單獨一層。

根據小波變換理論，小波變換擁有“變焦”的能力。伸縮因子較大時，分解得到原始信號的低頻信息部分；伸縮因子較小時，分解得到原始信號的高頻信息部分。低頻信號也被稱為近似信號，表示信號的整體走勢，對應著最大的尺度系數。高頻信號也被稱為細節信號，可看成噪聲或隨機擾動，對應著小波系數。

小波分解的實質是將一組包含多種分辨率的信號分解到不同的信息子空間［15］，得到不同分辨率的信號。分解后的信號在頻率成分上比原始信號單一，能從原始信號中分離出周期項、隨機項、趨勢項等，對信號具有平滑作用，分解后得到的信號在平穩性上得到了很大的提高。

基于多分辨率分析的Mallat算法［16］是小波分解和重構的常用算法，但對原始信號進行分解時，不能在時間尺度上建立直觀關系，不具有時移不變性。而多孔小波變換算法［17］把長度為N的時間序列經過分解后長度仍然為N，在各個分辨率上的時間點可以直接建立聯系，具有時移不變性。因此，本文采用多孔小波變換算法。設輸入的時間序列為x（t），通過離散低通濾波器h可得到尺度系數:

根據多孔小波變換的性質，可通過尺度系數獲得細節系數:

原時間序列經過p次小波分解后可用集合｛d1，d2，…，dp，cp｝表示，其中dj（j=1，2，…，p）為各分辨率下的細節信號，cp為近似信號。三層多孔小波分解的示意圖如圖1所示，h（z2j）表示在濾波器h的任意兩點間插入2j-1個0得到的濾波器的z變換［18］。

圖1　三層多孔小波分解示意圖

細節信號和近似信號重構后得到原始信號，即

本文采用Haar小波作為小波基函數，使用h= （1/2，1/2）作為低通濾波器。這種選擇的優點在于節省計算量，并且在任意時間點t，都不需要使用t以后的數據計算小波系數和尺度系數，此特點適用于實時的在線計算。為節省計算量，使用h=（1/2，1/2）作為低通濾波器。

因此，基于Haar的多孔小波變換的尺度系數和小波系數的計算公式為:

小波分解的次數會對預測精度造成影響，分解次數少，則近似信號序列不夠平滑，沒有小波分解的效果；分解次數多，則各細節信號序列在預測中產生的誤差會累積到最終的預測結果上。一般分解3層～5層即可。

在WPL算法的初始化階段，每個待定位節點根據MCB算法計算前幾個時刻的位置，并放入歷史運動軌跡序列。如圖2所示，當序列長度超過3時，進入WPL算法的預測階段。對歷史運動軌跡序列插值后進行Haar多孔小波分解，得到多個較為平穩的細節序列和一個平滑的近似序列，分別對各個序列建立AR模型并預測得到下一時刻的值，最后將各序列進行小波重構，得到待定位節點當前時刻位置的預測值

圖2　小波變換預測示意圖

判斷待定位節點當前時刻位置的預測值p是否滿足以下條件:

其中，S1t和S2t分別為待定位節點在t時刻一跳和兩跳錨節點的集合，d（p，s）為預測位置到錨節點的距離。

Sd表示錨節點密度，nd表示錨節點個數，A表示當前定位區域的面積。

若不滿足，則仍然使用原來的采樣盒作為采樣區域。

2.2自適應采樣

MCB算法在任何情況下均采用固定的樣本數目。然而在錨節點密度較高時，錨盒的面積較小，小采樣區域里的大量樣本點并不能提高定位精度，反而浪費內存和計算開銷［19］。在保障定位精度的情況下，如何減少采樣次數，是減少節點能耗，延長網絡壽命的關鍵。因此，WPL算法在采樣階段，針對當前時刻錨節點稠密或稀疏的不同情況，每個待定位節點根據錨盒的面積大小動態地調整采樣數目。待定位節點當前時刻的樣本數目N為:

其中，MaxNum為最大樣本點數，SAnchor為錨盒面積的大小，SThreshold為閾值。通常情況下，每個待定位節點能接收到至少一個錨節點，故SThreshold設為4r2，相當于一個錨節點形成的錨盒面積。

2.3加權濾波

樣本點根據式（8）的條件濾波，不滿足濾波條件的樣本點被淘汰，剩下的樣本點進入加權階段。

設以待定位節點上一時刻位置lt-1為起點，當前時刻位置預測值p為終點的向量為V；以lt-1為起點，樣本點i的位置為終點的向量為Ui。待定位節點在短時間內運動狀態發生較大變化的幾率較小，故在WPL算法的加權階段，根據向量V與向量Ui之間的夾角θ的大小賦予樣本點不同的權值。第i個樣本點的權值為:

針對不同樣本點賦予不同的權值，能夠降低低質量樣本點對定位結果的影響，使定位精度更高。所有樣本點加權后，須進行歸一化處理，第i個樣本點的歸一化權值為:

2.4位置估計

若濾波后的樣本點數目不足N個，則進入重采樣階段，再次進行采樣及濾波加權操作，直至樣本點數目達到N個。待定位節點在t時刻的估計位置為:

3　仿真分析

算法仿真實驗在MATLAB 2015平臺下進行，并與MCB算法進行對比。所有傳感器節點被隨機分布在250 m×250 m的仿真區域。默認的仿真參數為:節點總數CN=250，錨節點數目CA=15，通信半徑r=25 m，網絡中所有節點均移動，節點最大運動速度Vmax=10 m/s，最大樣本點數SN=30。在一次仿真中，每個節點取20個周期定位，迭代運行20次，取其平均定位誤差作為仿真結果。

節點移動采用高斯-馬爾可夫移動模型（Gauss-Markov Mobility Model）［20］，節點當前時刻的速率和方向取決于上一時刻的速率和方向以及一個隨機擾動值，沒有突然停止或大角度轉向等缺點，更接近于實際運動。高斯-馬爾可夫移動模型的定義如下:

其中，vt和dt分別是節點在t時刻的速率和方向，v-和d-分別是速率和方向的平均值。α是調整節點運動隨機程度的參數，若α=1，節點做線性運動，若α=0，節點則做完全隨機運動。γv，γd是服從高斯分布的隨機變量。

節點在t時刻的位置為:

節點平均定位誤差的計算公式為:

其中，（xi，yi）為節點的估計位置，（x，y）為節點的真實位置。

如圖3所示，對兩種算法的待定位節點在20個時間周期內的定位誤差結果進行了對比，仿真參數為默認參數。在定位的前3個時間周期，WPL算法處于初始化階段，采用與MCB相同的算法進行定位，由于缺乏先驗信息，二者的定位誤差都比較大。隨著時間的推移，待定位節點在移動過程中收到了更多的觀測信息，定位誤差逐漸下降并達到穩定狀態。在定位的第4個時間周期，WPL算法初始化完畢，進入WPL定位階段，采用小波變換預測、自適應采樣和濾波加權方法定位，定位精度得到較大幅度的提升。相對MCB算法，WPL算法定位精度提高13%～27%，平均提高16%。

圖3　定位周期與定位誤差關系圖

錨節點數目是影響定位精度的重要條件，場景中的錨節點越多，待定位節點收到的觀測信息越多，采樣盒的面積越小，定位精度越高，而在濾波階段可用的約束條件也越多，直接影響著樣本點質量。MCB算法定位精度依賴于所接收到的錨節點數目，在低錨節點密度的環境下，采樣盒面積較大，濾波約束條件少，定位誤差較大。WPL算法根據歷史軌跡預測待定位節點當前時刻的位置，把采樣盒面積控制在一定范圍內，有助于提高定位精度。如圖4所示，在其他參數為默認仿真參數的情況下，WPL算法定位精度與MCB算法相比平均提高15%，在低錨節點數目的環境下效果尤為明顯，達到27%。

圖4　錨節點數目與定位誤差關系圖

通信半徑也是影響定位精度的重要因素，節點通信半徑增大，意味著待定位節點接收到的一跳和二跳錨節點數目增多，得到更多的觀測信息，能更有效地排除無效粒子。如圖5所示，WPL算法比MCB算法平均提高定位精度約 11%，最高提高15%。這是因為WPL算法更充分地利用了觀測信息和歷史軌跡信息，在濾波加權對樣本點進項加權，能增大高質量樣本點和減少低質量樣本點對定位結果的影響。但增大通信半徑將增加節點能耗，縮短網絡壽命，在實際應用中應對定位精度和節點能耗作一個平衡。

圖5　通信半徑與定位誤差關系圖

圖6表示最大樣本點數目與平均定位誤差之間的關系。當最大樣本點數目較少時，定位誤差隨著最大樣本點數目的增加而快速下降。而當最大樣本點達到一定數目時，定位誤差趨于穩定，最大樣本點數目繼續地增加并沒有導致定位誤差太多的下降，原因在于采樣盒里過量的樣本點并不能提高定位精度，反而浪費計算能耗，縮減節點壽命。因此，選擇合適的最大樣本點數目也是實際應用中的一個重要參數。MCB算法在最大樣本點達到30個左右時定位誤差趨于穩定，而WPL算法由于使用自適應采樣，實際采樣的樣本點數會比最大樣本點數目少，定位誤差在最大樣本點數目大約為40個時趨于穩定。

圖6　最大樣本點數目與定位誤差關系圖

采樣盒面積的大小影響著定位誤差與采樣成功率。WPL算法引入了小波變換預測，構建了預測約束區域，能有效地縮小采樣盒的面積。圖7給出了不同錨節點數目情況下WPL算法與MCB算法采樣盒面積的對比，相對于MCB算法，WPL算法的采樣盒面積平均小12.5%，最高小19%。

圖7　錨節點數目與采樣盒面積關系圖

定位時間是指算法完成一次定位的耗時，是衡量算法能耗的重要指標。WPL算法引入的小波變換預測增大了計算量，而預測約束區域縮小了采樣盒面積，以及自適應采樣方法的應用則能減小計算量。如圖8所示，WPL算法的定位時間比MCB算法總體上略多，但兩者差距并不明顯，在可接受的范圍內。

圖8　錨節點數目與定位時間的關系圖

4　總結

本文提出了一種針對無線傳感器網絡移動節點的定位算法，通過小波變換對節點歷史軌跡進行預測，縮小采樣區域，并根據采樣盒面積自適應采樣，通過對樣本點加權濾波，增大高質量樣本點對定位結果的影響，提高了定位精度。仿真結果表明，在不同定位參數的情況下，WPL算法的定位精度均有不同程度的提高，在錨節點數目較少時對比尤為明顯，在低錨節點密度的網絡環境下更具有優勢。

［1］ 孫利民，李建中，陳俞.無線傳感器網絡［M］.北京:清華大學出版社，2005:4-45.

［2］ Guvenc I，Chong C C.A Survey on TOA Based Wireless Localization and NLOS Mitigation Techniques［J］.IEEE Communications Surveys&Tutorials，2009，11（3）:107-124.

［3］ Vankayalapati N，Kay S，Ding Q.TDOA Based Direct Positioning Maximum Likelihood Estimator and the Cramer-rao Bound［J］. IEEE Transactions on Aerospace&Electronic Systems，2014，50 （3）:1616-1635.

［4］ 方旺盛，雷高祥.基于節點RSSI值與臨界RSSI比例的跳數修正和跳距重估的DV-HOP算法［J］.傳感技術學報，2015（8）: 1244-1248.

［5］ Liu J，Wang Z，Yao M，et al.VN-APIT:Virtual Nodes-Based Range-Free APIT Localization Scheme for WSN［J］.Wireless Networks，2015:1-12.

［6］ Liang S C，Liao L H，Lee Y C，et al.Localization Algorithm Based on Improved Weighted Centroid in Wireless Sensor Networks［J］. Journal of Networks，2014，9（1）:183-189.

［7］ Hu L，Evans D.Localization for Mobile Sensor Networks［C］// Wireless Communication，2004:45-57.

［8］ Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Networks［J］.Ad Hoc Networks，2008，6（5）: 718-733.

［9］ 單志龍，劉蘭輝，張迎勝，等.一種使用灰度預測模型的強自適應性移動節點定位算法［J］.電子與信息學報，2014，（6）: 1492-1497.

［10］Adnan T，Datta S，Maclean S.Efficient and Accurate Sensor Network Localization［J］.Personal&Ubiquitous Computing，2014，8 （4）:821-833.

［11］王潔，王洪玉，高慶華，等.一種適用于移動傳感器網絡的增強型蒙特卡羅定位跟蹤算法［J］.電子與信息學報，2010，32: 864-868.

［12］Wang Z，Wang Y，Ma M，et al.Efficient Localization For Mobile Sensor Networks Based on Constraint Rules Optimized Monte Carlo Method［J］.Computer Networks，2013，57（14）:2788-2801.

［13］滿海鷗，龍書林，肖定邦，等.基于多分辨率分析的硅微陀螺隨機漂移時間序列建模［J］.傳感技術學報，2012，25（8）:1107-1111.

［14］徐科，徐金梧，班曉娟.基于小波分解的某些非平穩時間序列預測方法［J］.電子學報，2001，29（4）:566-568.

［15］單亞峰，孫璐，付華，等.基于小波包和RBF神經網絡的瓦斯傳感器故障診斷［J］.傳感技術學報，2015，28（2）:278-283.

［16］鐘麗輝，魏貫軍.基于Mallat算法的小波分解重構的心電信號處理［J］.電子設計工程，2012，20:57-59.

［17］王風宇，云曉春，申偉東.基于小波變換的網絡流量在線預測模型［J］.高技術通訊，2006，12:1220-1225.

［18］郝保峰.基于小波多孔變換的多傳感器多目標跟蹤航跡關聯算法研究［D］.太原:太原理工大學，2011.

［19］Sheu J P，Hu W K，Lin J C，et al.Distributed Localization Scheme for Mobile Sensor Networks［J］.IEEE Transactions on Mobile Computing，2010，9（4）:516-526.

［20］Camp Tracy，Boleng Jeff，Davies Vanessa，et al.A Survey of Mobility Models for Ad Hoc Network Research［J］.Wireless Communications and Mobile Computing，2002，2（5）:483-502.

徐澤坤（1991-），男，碩士研究生，主要研究方向為無線傳感器網絡；

單志龍（1976-），男，博士，教授，碩士生導師，主要研究方向為物聯網、無線傳感器網絡、無線通信網絡等，zhilongshan@ gmail.com。

A Localization Algorithm Based on Wavelet Transform Prediction for Mobile Nodes*

XU Zekun，SHAN Zhilong*
（School of Computer Science，South China Normal University，Guangzhou 510631，China）

In order to solve the shortcoming of localization accuracy in mobile wireless sensor networks，a localization algorithm based on wavelet transform prediction for mobile nodes is proposed in this paper.To get a more accurate sampling area，wavelet transform prediction is used to predict the current location of the node according to the historical trajectory.And adaptive sampling method is also applied here to reduce the times of sampling.Besides，to further improve the localization accuracy，weighted filtering is used in the filtering process，which will increase the weight of high-quality nodes and decrease the low-quality ones.Compared with traditional algorithm，the proposed algorithm has good performance in situations of different number of anchor nodes，communication radius，and maximum sample size，especially in situations of low density of the anchor nodes.

wireless sensor networks；mobile localization；wavelet transform；motion prediction；monte carlo

TP393

A

1004-1699（2016）04-0566-06

項目來源:國家自然科學基金項目（61370003）；廣東省自然科學基金項目（2015A030313395）；廣東省科技計劃項目（2013B040401014）

2015-10-28修改日期:2016-01-07