WSN中一種基于RSSI的移動節點改進定位算法*

黃海輝，李龍連

（重慶郵電大學 信息與通信工程，重慶400065）

WSN中一種基于RSSI的移動節點改進定位算法*

黃海輝，李龍連

（重慶郵電大學 信息與通信工程，重慶400065）

移動無線傳感器網絡的節點定位算法中，基于RSSI的MCL定位算法利用接收信號強度的對數正態模型對定位的預測和濾波過程進行了改進，改善了定位性能，但是仍存在計算量較大、功耗較大等不足。因為物體的運動狀態不會發生突變，因而可以利用前幾個時刻的軌跡，預測當前時刻的運動參數。采用Hermite插值法，對當前時刻的運動軌跡作了很好的預測。仿真結果表明，該算法與傳統的算法相比，減小了采樣范圍，提高了采樣準確率，從而提高定位精度，降低功耗。

無線傳感器網絡；節點定位；埃爾米特插值；蒙特卡洛；信號接收強度指標

0　引言

在無線傳感器網絡的關鍵支撐技術中[1]，定位技術是極其重要的組成部分，在其應用領域內，事件發生的位置信息是傳感器節點監測消息中的重要信息，沒有節點位置信息的感知數據是毫無意義的[1]。

無線傳感器網絡的定位算法根據節點間的測距要求，主要分為距離相關和距離無關兩大類[2]。典型的距離相關的測距算法主要有：RSSI、TOA、TDOA、AOA等，分別利用三邊測量法、三角測量法、極大似然估計法、最小二乘法等來進行節點定位；典型的距離無關算法主要有：質心算法、DV-HOP、MDS-MAP、APIT等。為提高定位精度，適宜采用距離相關的算法。在距離相關的幾種測距算法中，通過表1可以看出：基于RSSI的定位算法具有成本低、容易實現等優點，在對定位精度不高的情況下得到了廣泛的應用。另外，目前很多傳感器節點都提供測量信號發射功率的功能，可以在節點廣播消息包的同時完成RSSI測量值的獲取，并且這種定位算法無需額外的硬件支持和復雜的數據處理，也不會增加通信開銷，能有效減少節點的硬件成本和能量消耗，適用于無線傳感器網絡。

表1　基于距離的各種測距算法的優缺點

近十年來，WSN獲得快速發展，人們研究的對象不僅僅針對靜態WSN，而且漸漸地關注動態網絡的節點定位技術，這樣的要求就使得靜態定位算法在移動環境下就變得無效了。經典的WSN移動節點定位算法主要有：MCL[3]、MCB[4]、MSL和MSL*[5]、MMCL[6]、rang-based-MCL[7]、RSS-MCL[8]、OTMCL[9]等。

弗吉尼亞大學的Hu和Evans首次提出了將蒙特卡洛定位算法應用于移動無線傳感網絡節點定位中[3]，其提高了定位精度，減少了定位開銷；針對MCL采樣效率低的問題 Baggio A和Langendoen K提出了蒙特卡洛盒子定位（Monte Carlo Localization Boxed，MCB）算法[4]；約克大學的Rudafshani M和Datta S提出了移動和靜態傳感網絡定位算法MSL和 MSL*算法[5]；Dil B提出的Range-based-MCL[7]算法為基于距離的移動WSN定位，通過利用未知節點與錨節點之間的距離信息，可以濾波得到更精確的位置樣本，提高了定位精度。特別需要指出的是，Wang[8]等人將MCL和RSSI定位算法相結合，提出了基于RSSI的MCL定位算法，利用接收信號強度的對數正態模型對定位的預測和濾波過程進行了改進，改善了定位性能。

上述算法中，基于RSSI的MCL定位算法效果良好，在定位技術的研究和實際運用方面都有很大的意義，但存在計算量較大、無運動預測性等不足。因此，本文在文獻[3]和文獻[8]的基礎上，對移動無線傳感器網絡節點定位進行了深入研究，提出了一種基于RSSI的改進蒙特卡羅定位算法RSSI-IMCL。事實上，節點在運動過程中的運動參數一般不會突變，且基于RSSI的MCL算法沒有考慮運動預測問題，因而可以利用前幾個時刻的軌跡，預測當前時刻的運動參數，減小采樣范圍，提高采樣準確率，從而提高定位精度，降低節點功耗。

1　基于RSSI的改進MCL算法

本文提出的算法是對基于RSSI的蒙特卡洛算法的一種改進，基本思想與經典MCL和基于RSSI的MCL算法相似。即首先建立與描述該問題有相似性的概率模型，然后對模型進行隨機模擬或統計抽樣，再利用所得的結果求出特征量的統計值作為原問題的近似解，并對解的精度作出某些估計。

1.1RSSI模型

一般的RSSI通信模型都認為網絡中各節點為各向同性，例如自由空間傳播模型、雙射線模型、哈他模型等皆為各向同性，這類模型皆是按照式（1）的框架建立的模型。

自由空間傳播是電波在真空中無阻擋視距傳播的一種理想狀態。其模型可以表示為式（2）：

式(2)中，Lfs為傳輸損耗，d為節點距離，k為路徑衰減因子，一般取值為2，頻率單位以MHz計算。

在實際傳輸過程中，多徑現象不可避免，信號在傳輸時可能被一些障礙物吸收，或是發生反射、散射或衍射。這時我們可以采用不規則無線電模型來模擬實際應用環境，該模型在不同方向的路徑損耗是不同的。圖1表示的是自由模型和不規則電模型下RSSI值的比較。不規則電模型公式為式（3）：

式(3)中，Pr(d)為接收功率，Pt為發送功率，PL(d0)為參考距離時的路徑損耗。

圖1　自由模型和不規則電模型下RSSI值的比較

1.2基于RSSI的MCL算法

蒙特卡洛定位其實就是一個粒子濾波算法，每一個定位時刻都被分為了預測和更新兩部分。在預測階段，根據節點速度信息和在上一定位時刻的粒子集確定采樣區域，并隨機采樣得到粒子；在濾波階段，根據收到的錨節點信息，對預測階段的粒子進行篩選，濾除不符合觀測條件的，并用滿足濾波條件的粒子的均值來估計節點的位置，如果濾波得到的粒子數沒有達到定位所需的粒子數，則執行重采樣和濾波過程，直到得到足夠數量的粒子或者達到最大采樣次數為止。

以下三個步驟詳細說明了基于RSSI的MCL算法的定位過程。假設整個無線網絡中，有一個未知的移動節點和M個位置已知的錨節點隨機分布在整個區域中。

（1）預測階段

在預測階段，傳感器節點需要根據前一時刻的粒子集Lt-1和運動模型確定當前時刻的粒子集Lt。假設節點按照隨機行走模型（RWP）進行移動，該模型中，節點在任何時刻都不知道自己的運動速度和方向，僅僅知道自身的最大運動速率為 vmax，方向為360°任意選擇。那么轉移分布p(mk|mk-1)便形成了一個以mk-1為圓心，以 vmax為半徑的圓。表示如式（4）

在MCL算法的預測階段，基于前一時刻位置對當前時刻位置進行預測，節點可能的位置從上述的圓形區域隨機采樣獲得，該圓形區域就是采樣區域。

（2）濾波階段

在濾波階段，節點將根據新的觀測信息，將不符合網絡連通度條件的位置樣本濾除掉。如果樣本滿足濾波條件，則概率分布為1，否則為0。如果滿足濾波條件的粒子數達到了定位所需數量，則將這些粒子取均值作為節點的估計位置；如果粒子數不足，則重復預測和濾波過程，直到得到足夠數量的粒子或達到最大采樣次數為止。在MCL算法中，為方便計算，選擇狀態轉移概率密度函數為重要性函數，則每一時刻粒子的重要性權值可通過下列方法遞歸計算：

式(5)為預測階段，節點可以在前一時刻可能位置的基礎上預測當前時刻的可能位置。式(6)為更新階段，節點可以根據接收到的觀測信息更新當前時刻的粒子權值。然后用式(7)對權值進行歸一化，從而可以用一組帶權值的樣本集(，)來估計節點位置的后驗概率分布。

（3）重采樣階段

計算當前的位置需要重復進行預測和更新，將不可避免地出現粒子退化現象。因此需要重采樣，將權重值小的樣本淘汰，將權重值大的保留，用式（8）定義有效粒子數 Neff，當 Neff小于設定的門限值 Nthreshold時，就需要進行重采樣。

基于RSSI的MCL算法相比于經典的MCL算法，較大幅度地提高了定位精度，取得了良好的效果，但計算量較大，節點功耗過快，需要改進。

1.3基于RSSI的改進MCL算法

針對基于RSSI的MCL算法的不足，本文提出了一種基于RSSI的改進MCL算法。在基于RSSI的MCL算法的預測階段，k時刻的位置概率分布只與k-1時刻的位置及速度有關，沒有考慮k-1時刻之前的運動情況的影響，本文采用基于歷史軌跡的運動預測機制來提高先驗概率的準確性，也就是意味著可能更高的定位精度和可能更少的迭代次數，從而降低節點的功耗。

Newton插值法和 Lagrange插值法雖然構造比較簡單，但是存在插值曲線在節點處有尖點、不光滑、插值多項式在節點處不可導等缺點，因此本文選擇Hermite插值法。一般，Hermite插值多項式Hk(x)的次數k如果太高會影響收斂性和穩定性稱為 runge現象。本文中，就采用前兩個時刻的位置信息，因此不會出現runge現象。

設 f(x)在節點 x0、x1處的函數值為 y0、y1，在節點 x0、x1處的一階導數值為，兩個節點最高可用3次 Hermite多項式H3(x)作為插值函數。H3(x)應滿足的插值條件為。設H3(x)的插值基函數H3(x)=a0h0(x)+a1h1(x)+a2h2(x)+a3h3(x)，即。

希望該函數與Lagrange和 Newton插值一樣簡單，重新假設：

在算法預測階段，利用歷史軌跡，提高了當前位置預測的準確性，減小了采樣范圍，提高了采樣準確率，從而降低節點功耗。

2　仿真分析

仿真實驗使用MATLAB進行，該仿真實驗是在一個14 m×10 m的矩形平面區域進行的。信標節點隨機地分布在平面區域內，其位置是固定不變的且坐標是已知的；未知節點方向和速度大小都隨機移動，且其移動速度不會超過設定的最大速度。網絡中使用的參數設定如下：節點的最大移動速度取 10 m/s，信標節點和未知節點的通信半徑相等且都取3 m。

圖2和3顯示的是MCL定位算法和基于RSSI改進的定位算法的定位仿真圖，可以看出，改進的算法定位的軌跡更接近實際軌跡，定位精度有明顯的提高。

圖2　MCL定位算法仿真圖

圖3　基于RSSI的改進MCL定位算法仿真圖

定位誤差用于描述定位結果的精確程度，本文用到的定位誤差的定義如下：

其中，(xi，yi)為未知節點的實際位置，為用算法估計出來的坐標位置。如圖4可知，隨著時間的推移，定位次數的增加，定位誤差也在減小。

圖4　定位誤差與定位次數的仿真圖

3　結論

本文對基于RSSI的蒙特卡洛無線傳感定位算法進行了深入研究，并在此基礎上提出了一種基于RSSI的改進蒙特卡洛定位算法。該算法在定位精度、計算量、對錨節點密度的要求和對粒子樣本集的要求等性能都有所提升，且通過仿真實驗證明該算法在移動的WSN中是一個高效的定位算法。

[1]馮硯毫，曾孝平，江禹生.無線傳感器網絡節點定位技術研究[D].重慶：重慶大學，2011.

[2]黃俊霖，楊剛.基于 RSSI分級的 WSN節點定位算法研究[D].西安：西安電子科技大學.2013.

[3]Hu Lingxuan，EVANS D.Localization for mobile sensor networks[C].Proc of the 10th Annual International Conference on Mobile Computing and Networking(Mobicom04)，Philadelphia，Pennsylvania：USA，2004：45-57.

[4]BAGGIO A，LANGENDOER K.Monte carlo iocalization for mobile wireless sensor networks[C].Proceedings of the 2nd International Conference on Mobile Ad-hoc and Sensor Networks(MSN′06)，Dec 13-15，2006，Hong Kong，China. LNCS 4325.Berlin，Germany：Springer-Verlag，2006：718-733.

[5]RUDAFSHANI M，DATTA S.Localization in wireless sensor networks[C].Information Processing in Sensor Networks，2007.IPSN 2007.6th International Symposium on，pp. 51，60，25-27 April 2007.

[6]Yi Jiyoung，Won YangSung，Cha Hojung.Multi-hop-based Monte Carlo Localization for Mobile Sensor Networks[C]. Proceedings of The 4th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，San Diego，California，USA，2007：163-171.

[7]DIL B，DULMAN S，HAVINGA P.Range-based localization in mobile sensor networks[J].Wireless Sensor Networks，2006：164-179.

[8]WANG W D，ZHU Q X.RSS-based Monte Carlo localization for mobile sensor networks[J].Communications，IET，2008，2(5)：673-681.

[9]MARTINS M H T，CHEN H，SEZAKI K.OTMCL：Orientation tracking-based Monte Carlo localization for mobile sensor networks[C].Proceedings of the 6thInternational Conference on Networked Sensing Systems(INSS)，2009：1-8.

[10]李偉，丁勇，于春娣，等.一種基于 RSSI的改進蒙特卡羅定位算法[J].計算機應用與軟件，2013(12)：280-283.

An improved localization algorithm based on RSSI in WSN

Huang Haihui，Li Longlian
（Chongqing University of Posts and Telecommunications，Information and Communication Engineering，Chongqing 400065，China）

Among the localization algorithms for mobile wireless sensor network nodes,the RSSI-based MCL location algorithm using the

signal strength of the lognormal model improved prediction and filtering process oflocalization,and also improved positioning performance.However,there are still large amount of calculation and large power consumption,etc.Because the movement state of the object is not a mutation,it is possible to use the first few moments of the trajectory and the motion parameters of the current time could be predicted.This paper uses a Hermite interpolation method,the trajectory of the current moment made a good prediction.Simulation results show that compared with the conventional the algorithm,the sampling range is reduced，the sumpling accuracy is improved，and then the localization accurary is improved，the power consumption of the nodes is reduced.

wireless sensor network；localization；hermite monte carlo algorithm；

signal strength indication

TP393

A

0258-7998(2015)01-0086-04

10.16157/j.cnki.0258-7998.2014061902241

國家自然科學基金項目（61171190）

2014-06-03)

黃海輝(1969-)，男，主要研究方向：物聯網和 3D圖像處理。

李龍連(1989-)，女，碩士研究生，主要研究方向：無線傳感器網絡。