0 引言

　　在無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵支撐技術(shù)中[1]，定位技術(shù)是極其重要的組成部分,，在其應(yīng)用領(lǐng)域內(nèi),，事件發(fā)生的位置信息是傳感器節(jié)點(diǎn)監(jiān)測(cè)消息中的重要信息，沒(méi)有節(jié)點(diǎn)位置信息的感知數(shù)據(jù)是毫無(wú)意義的[1],。

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

　　近十年來(lái),，WSN獲得快速發(fā)展,，人們研究的對(duì)象不僅僅針對(duì)靜態(tài)WSN，而且漸漸地關(guān)注動(dòng)態(tài)網(wǎng)絡(luò)的節(jié)點(diǎn)定位技術(shù),，這樣的要求就使得靜態(tài)定位算法在移動(dòng)環(huán)境下就變得無(wú)效了,。經(jīng)典的WSN移動(dòng)節(jié)點(diǎn)定位算法主要有：MCL[3]、MCB[4],、MSL和MSL*[5],、MMCL[6]、rang-based-MCL[7],、RSS-MCL[8],、OTMCL[9]等。

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

　　上述算法中，基于RSSI的MCL定位算法效果良好,，在定位技術(shù)的研究和實(shí)際運(yùn)用方面都有很大的意義,，但存在計(jì)算量較大、無(wú)運(yùn)動(dòng)預(yù)測(cè)性等不足,。因此,，本文在文獻(xiàn)[3]和文獻(xiàn)[8]的基礎(chǔ)上，對(duì)移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位進(jìn)行了深入研究,，提出了一種基于RSSI的改進(jìn)蒙特卡羅定位算法RSSI-IMCL,。事實(shí)上，節(jié)點(diǎn)在運(yùn)動(dòng)過(guò)程中的運(yùn)動(dòng)參數(shù)一般不會(huì)突變,，且基于RSSI的MCL算法沒(méi)有考慮運(yùn)動(dòng)預(yù)測(cè)問(wèn)題,，因而可以利用前幾個(gè)時(shí)刻的軌跡，預(yù)測(cè)當(dāng)前時(shí)刻的運(yùn)動(dòng)參數(shù),，減小采樣范圍，提高采樣準(zhǔn)確率,，從而提高定位精度,，降低節(jié)點(diǎn)功耗。

1 基于RSSI的改進(jìn)MCL算法

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

　　1.1 RSSI模型

　　一般的RSSI通信模型都認(rèn)為網(wǎng)絡(luò)中各節(jié)點(diǎn)為各向同性,，例如自由空間傳播模型,、雙射線模型、哈他模型等皆為各向同性,，這類(lèi)模型皆是按照式（1）的框架建立的模型,。

　　接收信號(hào)強(qiáng)度=發(fā)送功率-路徑損耗+信號(hào)衰退(1)

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

　　[Lfs]=32.44-10klgd+10klgf(2)

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

　　在實(shí)際傳輸過(guò)程中，多徑現(xiàn)象不可避免,，信號(hào)在傳輸時(shí)可能被一些障礙物吸收,，或是發(fā)生反射、散射或衍射,。這時(shí)我們可以采用不規(guī)則無(wú)線電模型來(lái)模擬實(shí)際應(yīng)用環(huán)境,，該模型在不同方向的路徑損耗是不同的。圖1表示的是自由模型和不規(guī)則電模型下RSSI值的比較,。不規(guī)則電模型公式為式（3）：

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

　　1.2 基于RSSI的MCL算法

　　蒙特卡洛定位其實(shí)就是一個(gè)粒子濾波算法，每一個(gè)定位時(shí)刻都被分為了預(yù)測(cè)和更新兩部分,。在預(yù)測(cè)階段,，根據(jù)節(jié)點(diǎn)速度信息和在上一定位時(shí)刻的粒子集確定采樣區(qū)域，并隨機(jī)采樣得到粒子,；在濾波階段,，根據(jù)收到的錨節(jié)點(diǎn)信息，對(duì)預(yù)測(cè)階段的粒子進(jìn)行篩選,，濾除不符合觀測(cè)條件的,，并用滿足濾波條件的粒子的均值來(lái)估計(jì)節(jié)點(diǎn)的位置，如果濾波得到的粒子數(shù)沒(méi)有達(dá)到定位所需的粒子數(shù),，則執(zhí)行重采樣和濾波過(guò)程,，直到得到足夠數(shù)量的粒子或者達(dá)到最大采樣次數(shù)為止。

　　以下三個(gè)步驟詳細(xì)說(shuō)明了基于RSSI的MCL算法的定位過(guò)程,。假設(shè)整個(gè)無(wú)線網(wǎng)絡(luò)中,，有一個(gè)未知的移動(dòng)節(jié)點(diǎn)和M個(gè)位置已知的錨節(jié)點(diǎn)隨機(jī)分布在整個(gè)區(qū)域中。

　?。?）預(yù)測(cè)階段

　　在預(yù)測(cè)階段,，傳感器節(jié)點(diǎn)需要根據(jù)前一時(shí)刻的粒子集Lt-1和運(yùn)動(dòng)模型確定當(dāng)前時(shí)刻的粒子集Lt。假設(shè)節(jié)點(diǎn)按照隨機(jī)行走模型（RWP）進(jìn)行移動(dòng),，該模型中,，節(jié)點(diǎn)在任何時(shí)刻都不知道自己的運(yùn)動(dòng)速度和方向，僅僅知道自身的最大運(yùn)動(dòng)速率為vmax,，方向?yàn)?60°任意選擇,。那么轉(zhuǎn)移分布p(mk|mk-1)便形成了一個(gè)以mk-1為圓心，以vmax為半徑的圓,。表示如式（4）

　　在MCL算法的預(yù)測(cè)階段,，基于前一時(shí)刻位置對(duì)當(dāng)前時(shí)刻位置進(jìn)行預(yù)測(cè),，節(jié)點(diǎn)可能的位置從上述的圓形區(qū)域隨機(jī)采樣獲得，該圓形區(qū)域就是采樣區(qū)域,。

　?。?）濾波階段

　　在濾波階段，節(jié)點(diǎn)將根據(jù)新的觀測(cè)信息,，將不符合網(wǎng)絡(luò)連通度條件的位置樣本濾除掉,。如果樣本滿足濾波條件，則概率分布為1,，否則為0,。如果滿足濾波條件的粒子數(shù)達(dá)到了定位所需數(shù)量，則將這些粒子取均值作為節(jié)點(diǎn)的估計(jì)位置,；如果粒子數(shù)不足,，則重復(fù)預(yù)測(cè)和濾波過(guò)程，直到得到足夠數(shù)量的粒子或達(dá)到最大采樣次數(shù)為止,。在MCL算法中,，為方便計(jì)算，選擇狀態(tài)轉(zhuǎn)移概率密度函數(shù)為重要性函數(shù),，則每一時(shí)刻粒子的重要性權(quán)值可通過(guò)下列方法遞歸計(jì)算：

　　式(5)為預(yù)測(cè)階段,，節(jié)點(diǎn)可以在前一時(shí)刻可能位置的基礎(chǔ)上預(yù)測(cè)當(dāng)前時(shí)刻的可能位置。式(6)為更新階段,，節(jié)點(diǎn)可以根據(jù)接收到的觀測(cè)信息更新當(dāng)前時(shí)刻的粒子權(quán)值,。然后用式(7)對(duì)權(quán)值進(jìn)行歸一化，從而可以用一組帶權(quán)值的樣本集來(lái)估計(jì)節(jié)點(diǎn)位置的后驗(yàn)概率分布,。

　　（3）重采樣階段

　　計(jì)算當(dāng)前的位置需要重復(fù)進(jìn)行預(yù)測(cè)和更新,，將不可避免地出現(xiàn)粒子退化現(xiàn)象,。因此需要重采樣，將權(quán)重值小的樣本淘汰,，將權(quán)重值大的保留,，用式（8）定義有效粒子數(shù)Neff，當(dāng)Neff小于設(shè)定的門(mén)限值Nthreshold時(shí),，就需要進(jìn)行重采樣,。

　　基于RSSI的MCL算法相比于經(jīng)典的MCL算法，較大幅度地提高了定位精度,，取得了良好的效果,，但計(jì)算量較大，節(jié)點(diǎn)功耗過(guò)快,，需要改進(jìn),。

　　1.3 基于RSSI的改進(jìn)MCL算法

　　針對(duì)基于RSSI的MCL算法的不足,，本文提出了一種基于RSSI的改進(jìn)MCL算法。在基于RSSI的MCL算法的預(yù)測(cè)階段,，k時(shí)刻的位置概率分布只與k-1時(shí)刻的位置及速度有關(guān),，沒(méi)有考慮k-1時(shí)刻之前的運(yùn)動(dòng)情況的影響，本文采用基于歷史軌跡的運(yùn)動(dòng)預(yù)測(cè)機(jī)制來(lái)提高先驗(yàn)概率的準(zhǔn)確性,，也就是意味著可能更高的定位精度和可能更少的迭代次數(shù),，從而降低節(jié)點(diǎn)的功耗。

　　Newton插值法和Lagrange插值法雖然構(gòu)造比較簡(jiǎn)單,，但是存在插值曲線在節(jié)點(diǎn)處有尖點(diǎn),、不光滑、插值多項(xiàng)式在節(jié)點(diǎn)處不可導(dǎo)等缺點(diǎn),，因此本文選擇Hermite插值法,。一般，Hermite插值多項(xiàng)式Hk(x)的次數(shù)k如果太高會(huì)影響收斂性和穩(wěn)定性稱(chēng)為runge現(xiàn)象,。本文中,，就采用前兩個(gè)時(shí)刻的位置信息，因此不會(huì)出現(xiàn)runge現(xiàn)象,。

　　設(shè)f(x)在節(jié)點(diǎn)x0,、x1處的函數(shù)值為y0、y1,，在節(jié)點(diǎn)x0,、x1處的一階導(dǎo)數(shù)值為，兩個(gè)節(jié)點(diǎn)最高可用3次Hermite多項(xiàng)式H3(x)作為插值函數(shù),。H3(x)應(yīng)滿足的插值條件為H3(x0)=y0,、H3(x1)=y1、設(shè)H3(x)的插值基函數(shù)H3(x)=a0 h0(x)+a1 h1(x)+a2 h2(x)+a3 h3(x),，即H3(x)=ai hi(x),。

　　希望該函數(shù)與Lagrange和Newton插值一樣簡(jiǎn)單，重新假設(shè)：

　　由上式(11)中的 (x1)=0可知,，x1是(x)的二重零點(diǎn),，可設(shè)(x)=(x-x1)2(ax+b)，由(x0)=1,、(x0)=0可知：

　　繼而可得?琢0(x),。

　　類(lèi)似可得

　　將式(13)、(14),、(15),、(16)代入H3(x)=a0 h0(x)+a1 h1(x)+a2 h2(x)+a3 h3(x)中，得：

　　在算法預(yù)測(cè)階段,，利用歷史軌跡,，提高了當(dāng)前位置預(yù)測(cè)的準(zhǔn)確性,，減小了采樣范圍，提高了采樣準(zhǔn)確率,，從而降低節(jié)點(diǎn)功耗,。

2 仿真分析

　　仿真實(shí)驗(yàn)使用MATLAB進(jìn)行，該仿真實(shí)驗(yàn)是在一個(gè)14 m×10 m的矩形平面區(qū)域進(jìn)行的,。信標(biāo)節(jié)點(diǎn)隨機(jī)地分布在平面區(qū)域內(nèi),，其位置是固定不變的且坐標(biāo)是已知的；未知節(jié)點(diǎn)方向和速度大小都隨機(jī)移動(dòng),，且其移動(dòng)速度不會(huì)超過(guò)設(shè)定的最大速度,。網(wǎng)絡(luò)中使用的參數(shù)設(shè)定如下：節(jié)點(diǎn)的最大移動(dòng)速度取10 m/s，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的通信半徑相等且都取3 m,。

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

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

　　其中,，(xi,，yi)為未知節(jié)點(diǎn)的實(shí)際位置，(x,，y)為用算法估計(jì)出來(lái)的坐標(biāo)位置,。如圖4可知，隨著時(shí)間的推移,，定位次數(shù)的增加,，定位誤差也在減小。

3 結(jié)論

　　本文對(duì)基于RSSI的蒙特卡洛無(wú)線傳感定位算法進(jìn)行了深入研究,，并在此基礎(chǔ)上提出了一種基于RSSI的改進(jìn)蒙特卡洛定位算法,。該算法在定位精度、計(jì)算量,、對(duì)錨節(jié)點(diǎn)密度的要求和對(duì)粒子樣本集的要求等性能都有所提升，且通過(guò)仿真實(shí)驗(yàn)證明該算法在移動(dòng)的WSN中是一個(gè)高效的定位算法,。

參考文獻(xiàn)

　　[1] 馮硯毫,，曾孝平，江禹生.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D].重慶：重慶大學(xué),，2011.

　　[2] 黃俊霖,，楊剛.基于RSSI分級(jí)的WSN節(jié)點(diǎn)定位算法研究[D].西安：西安電子科技大學(xué).2013.

　　[3] Hu Lingxuan，EVANS D.Localization for mobile sensor networks[C].Proc of the 10th Annual International Confer-ence 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 Commun-ications and Networks，San Diego,，California,，USA，2007：163-171.

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

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

　　[9] MARTINS M H T,，CHEN H，SEZAKI K.OTMCL：Orienta-tion tracking-based Monte Carlo localization for mobile sensor networks[C].Proceedings of the 6th International Con-ference on Networked Sensing Systems (INSS),，2009：1-8.

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