動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)的改進(jìn)蒙特卡羅定位算法*

朱海平，于紅丞，鐘小勇，余錢紅

(華中科技大學(xué)，數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢 430074)

對于無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)來說，節(jié)點(diǎn)自定位是網(wǎng)絡(luò)提供的基本服務(wù)之一。在許多應(yīng)用中，不包含傳感器節(jié)點(diǎn)位置信息的感知數(shù)據(jù)是沒有意義的，例如:軍事目標(biāo)追蹤［1］、防火監(jiān)測［2］、礦井探測［3］等。如何實(shí)現(xiàn)高效、高精度的節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)的研究熱點(diǎn)之一。

許多學(xué)者提出了不同的定位方法，包括Cricket定位系統(tǒng)［4］，質(zhì)心定位算法，DV-HOP 定位算法［5］，APIT 定 位 算 法［6］，凸 規(guī) 劃 定 位 算 法［7］，MDSMAP［8］，它們都是針對于靜態(tài)無線傳感器網(wǎng)絡(luò)的定位方法。然而，在很多實(shí)際應(yīng)用中，傳感節(jié)點(diǎn)是處在運(yùn)動(dòng)中的，這些定位系統(tǒng)和定位算法只能通過頻繁反復(fù)的計(jì)算來實(shí)現(xiàn)移動(dòng)節(jié)點(diǎn)定位。因此，受移動(dòng)節(jié)點(diǎn)動(dòng)態(tài)特性的影響，靜態(tài)定位算法的定位精度會降低，并且能量消耗增加、計(jì)算時(shí)間增長。

為實(shí)現(xiàn)一般網(wǎng)絡(luò)環(huán)境下移動(dòng)節(jié)點(diǎn)的定位，Hu和Evans提出了一種叫做MCL(Monte Carlo Localization)的動(dòng)態(tài)傳感器網(wǎng)絡(luò)定位算法［9］。該算法基于蒙特卡羅算法，利用節(jié)點(diǎn)的移動(dòng)特性來改善定位效果，克服了靜態(tài)定位算法在動(dòng)態(tài)定位中的局限性，取得了較好的定位精度。在MCL算法的基礎(chǔ)上，一些學(xué)者提出了MCB［10］、RSS-MCL［11］、MMCL［12］等定位算法。

1 蒙特卡羅定位算法

MCL是在考慮了節(jié)點(diǎn)的移動(dòng)特性的基礎(chǔ)上，專門為動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)而設(shè)計(jì)的。其核心思想是利用一系列的加權(quán)樣本來估計(jì)節(jié)點(diǎn)位置的后驗(yàn)概率密度分布，并不斷迭代更新樣本集合。

在文獻(xiàn)［9］中，定義了移動(dòng)節(jié)點(diǎn)，并且把時(shí)間離散化為一個(gè)時(shí)間序列。由于一個(gè)傳感節(jié)點(diǎn)可能離開它目前的位置，這就需要在每個(gè)時(shí)間段對它進(jìn)行重定位。基于移動(dòng)趨勢和觀察數(shù)據(jù)，在每個(gè)時(shí)間段，將會獲得一系列的樣本，根據(jù)這些樣本將可以估計(jì)出節(jié)點(diǎn)的位置。MCL定位算法的定位過程如下:

在定位算法初始化時(shí)，節(jié)點(diǎn)并沒有位置先驗(yàn)數(shù)據(jù)。于是，就在部署區(qū)域隨機(jī)選擇L0={，…，}等N個(gè)樣本設(shè)定為節(jié)點(diǎn)可能位置集合。初始化之后，就進(jìn)行如下兩個(gè)重復(fù)步驟:預(yù)測和過濾。

預(yù)測:在t時(shí)刻，根據(jù)可能的移動(dòng)趨勢和先前時(shí)間步可能的位置集合Lt－1生成Lt。從Lt－1中選定一個(gè)位置，以此設(shè)定出以為中心，以節(jié)點(diǎn)最大速度vmax為半徑的樣本區(qū)域，然后在樣本區(qū)域中隨機(jī)地獲得新樣本。

過濾:根據(jù)從一跳錨節(jié)點(diǎn)和二跳錨節(jié)點(diǎn)獲得的新的節(jié)點(diǎn)信息來過濾新樣本集合Lt，并將無效樣本從Lt中移除。

過濾之后的樣本數(shù)可能比期望的要少。于是，將重新進(jìn)行預(yù)測和過濾，更新樣本集合，直到采集到足夠多的樣本。最后利用這些樣本，加權(quán)求平均，估算出節(jié)點(diǎn)位置。

MCL算法也存在一定的不足，其中最大的問題就是計(jì)算量巨大。MCL算法需要大量的樣本來估計(jì)可能位置的后驗(yàn)概率密度，造成了計(jì)算資源的浪費(fèi)。

MCL定位算法為動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)的定位提供了一種新的思路。基于MCL，Baggio和Langendoen［10］提出了 MCB(Monte Carlo boxed)定位算法。MCB通過錨節(jié)點(diǎn)盒子和樣本盒子來減小樣本區(qū)域，提高了定位精確度和效率。與MCL相比，MCB平均提高定位準(zhǔn)確度30%，減少處理時(shí)間93%，提高覆蓋范圍22%。

2 改進(jìn)蒙特卡羅定位算法

在MCL算法中，樣本區(qū)域只是和節(jié)點(diǎn)運(yùn)動(dòng)趨勢進(jìn)行了綁定，這就造成需要選擇和過濾的樣本數(shù)目非常巨大，從而過多地占用節(jié)點(diǎn)的計(jì)算資源，增加能量消耗，定位的精確度也相對較低。因此，可以通過一種減小取樣樣本區(qū)域的方法來優(yōu)化MCL。

2.1 RSSI測距模型

在實(shí)際環(huán)境中，發(fā)送器和接收器之間的射頻信號將隨著通信距離的增加而逐漸衰減。射頻信號的傳播會受到多路徑(Multi-Path)、非視距(NLOS)等諸多因素的影響，衰減量也會因傳輸環(huán)境的不同而發(fā)生變化［13］。在考慮到這些因素的情況下，信號傳播可以按照對數(shù)正態(tài)分布進(jìn)行建模。在建模方面，Shadowing模型可以精確地描述實(shí)際信號傳播，并且已經(jīng)應(yīng)用于許多定位系統(tǒng)中［14－15］。本文將采用Shadowing模型進(jìn)行信號傳輸?shù)慕！hadowing模型表示如下:

其中dij表示節(jié)點(diǎn)i和j之間的距離；d0表示參考距離；Pij表示在傳輸距離為dij時(shí)，節(jié)點(diǎn)i接收到的從節(jié)點(diǎn)j發(fā)出的信號強(qiáng)度(dBm)；P0表示在傳輸距離為d0時(shí)，節(jié)點(diǎn)接收到的信號強(qiáng)度(dBm)；η是和環(huán)境有關(guān)的衰減因子；ξ～N(0，σ2)，σ和多路徑有關(guān)。

在等式(1)中，ξ通常不予考慮，于是簡化如下:

在式(2)中，d0典型值設(shè)定為1 m，P0和η可以在實(shí)際環(huán)境測量得到或者取實(shí)驗(yàn)觀察值和。于是進(jìn)一步簡化如下:

根據(jù)式(3)，距離估計(jì)值可以由RSSI值Pij進(jìn)行計(jì)算:

2.2 改進(jìn)定位算法設(shè)計(jì)

本節(jié)將利用移動(dòng)信息和RSSI測距值來構(gòu)建樣本區(qū)域，以改進(jìn)蒙特卡羅定位算法。

在改進(jìn)算法中，RSSI測距值用于估算移動(dòng)節(jié)點(diǎn)與它的一跳錨節(jié)點(diǎn)及二跳錨節(jié)點(diǎn)之間的距離。傳感節(jié)點(diǎn)只能探測到射頻距離r內(nèi)的錨節(jié)點(diǎn)，于是在引進(jìn)RSSI測距值的情況下，對于給定移動(dòng)節(jié)點(diǎn)i，如果它有一跳錨節(jié)點(diǎn)j，那么它們之間的距離估測值rij可以定義為rij=min(，r)；如果它有二跳錨節(jié)點(diǎn)k和一跳鄰節(jié)點(diǎn)h(能夠監(jiān)聽到二跳錨節(jié)點(diǎn)k)，那么移動(dòng)節(jié)點(diǎn)i和二跳錨節(jié)點(diǎn)k之間的距離rik可以定義為。然后就可以利用距離估測值rij來確定樣本區(qū)域。

改進(jìn)算法的主要處理過程包括三方面內(nèi)容:樣本區(qū)域構(gòu)建、取樣、過濾。首先是構(gòu)建樣本區(qū)域，從中選取樣本，然后對樣本進(jìn)行過濾，最后用這些過濾后樣本的加權(quán)平均值來估測節(jié)點(diǎn)位置。這種算法是基于先驗(yàn)樣本和錨節(jié)點(diǎn)估測距離來構(gòu)建樣本區(qū)域的。但是，在某些情況下，會缺少錨節(jié)點(diǎn)或者先驗(yàn)樣本，改進(jìn)算法會根據(jù)實(shí)際情況使用不同的信息來構(gòu)建樣本區(qū)域。

在改進(jìn)算法中，初始樣本區(qū)域定義為部署區(qū)域。在沒有錨節(jié)點(diǎn)和先驗(yàn)樣本的情況下，部署區(qū)域就會被當(dāng)做樣本區(qū)域。

如果錨節(jié)點(diǎn)存在，就會利用移動(dòng)節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離估測值來限制樣本區(qū)域。當(dāng)移動(dòng)節(jié)點(diǎn)i監(jiān)聽到錨節(jié)點(diǎn)j時(shí)，即可測量到RSSI值。根據(jù)RSSI值，計(jì)算移動(dòng)節(jié)點(diǎn)i和錨節(jié)點(diǎn)j之間的距離rij，并以此限定出一塊中心在錨節(jié)點(diǎn)j、邊長為2rij的正方形區(qū)域。同理，處理移動(dòng)節(jié)點(diǎn)的所有一跳錨節(jié)點(diǎn)和二跳錨節(jié)點(diǎn)，就能得到多個(gè)正方形區(qū)域。它們的重疊的區(qū)域就是新的樣本區(qū)域，如圖1所示。

圖1 錨節(jié)點(diǎn)限定樣本區(qū)域

在先驗(yàn)樣本存在的情況下，先驗(yàn)樣本和本節(jié)點(diǎn)的移動(dòng)信息被用來限制樣本區(qū)域。由于樣本區(qū)域中的每個(gè)樣本具有一致性，可以從先驗(yàn)樣本Lt－1中選擇樣本作為一個(gè)樣例。對于動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，最大移動(dòng)速度是恒值vmax。所以移動(dòng)節(jié)點(diǎn)在下一時(shí)刻所有可能位置都會落在以為中心，以vmax為半徑的圓形區(qū)域中。為了方便計(jì)算和取樣，可使用中心在、邊長為2vmax的正方形區(qū)域進(jìn)行替代，從而限定出新的樣本區(qū)域，如圖2所示。

圖2 移動(dòng)信息限定樣本區(qū)域

如果兩者都存在，在錨節(jié)點(diǎn)限定的基礎(chǔ)上，繼續(xù)用先驗(yàn)樣本進(jìn)行限定。

通過上述方法，可計(jì)算出所構(gòu)建的矩形樣本區(qū)域的坐標(biāo)范圍(xmin，xmax)和(ymin，ymax)。在仿真中，樣本區(qū)域會出現(xiàn)xmin＞xmax或ymin＞ymax的情況，可將它看作一個(gè)虛擬區(qū)域以獲取坐標(biāo)范圍(xmin，xmax)和(ymin，ymax)。利用這些坐標(biāo)，就能很容易的獲得新的樣本。由于RSSI測距不會很精確，樣本區(qū)域也是一個(gè)近似區(qū)間，于是需要對樣本進(jìn)行過濾。取樣和過濾步驟重復(fù)進(jìn)行直到樣本數(shù)達(dá)到要求或者操作次數(shù)達(dá)到最大重復(fù)次數(shù)。

改進(jìn)算法的實(shí)現(xiàn)如下:

假定用于計(jì)算的最大樣本數(shù)目N是恒值，定位部署平面區(qū)域定義為{(x，y)|0≤x≤xrange，0≤y≤yrange}，其中xrange和yrange為給定值。Ot設(shè)為時(shí)間t時(shí)段的錨節(jié)點(diǎn)集合；Lt設(shè)為時(shí)間t時(shí)段的樣本位置集合；At設(shè)為時(shí)間t時(shí)段的樣本區(qū)域。

(1)初始化

在初始條件下，沒有先驗(yàn)樣本L－1，于是構(gòu)建初始樣本區(qū)域A0:

其中xmin=0；xmax=xrange；ymin=0；ymax=yrange；

取樣:

(2)節(jié)點(diǎn)定位處理過程

從樣本區(qū)域At中隨機(jī)取出樣本并用新的觀察數(shù)據(jù)Ot對它們進(jìn)行過濾。

其中，在樣本區(qū)域構(gòu)建方面:用xmin，xmax，ymin，ymax來約束樣本區(qū)域。

(xj，yj)是參考錨節(jié)點(diǎn)j的坐標(biāo)；n是能夠監(jiān)聽到的錨節(jié)點(diǎn)的總數(shù)；rij是移動(dòng)節(jié)點(diǎn)i和參考錨節(jié)點(diǎn)j之間的距離估測值。

其中，在過濾方面:從設(shè)定的樣本中去除無效樣本。假定r是射頻距離，St設(shè)為時(shí)間t時(shí)段的一跳錨節(jié)點(diǎn)；Tt設(shè)為時(shí)間t時(shí)段的二跳錨節(jié)點(diǎn)；d(，s)錨節(jié)點(diǎn)s和樣本之間距離估測值。

3 算法仿真分析

3.1 仿真方案

由于改進(jìn)算法同MCL算法、MCB算法都是啟發(fā)于蒙特卡羅算法，三者有一定相似之處，本方案將對三者進(jìn)行分析比較。

在仿真方案中，假定將320個(gè)傳感節(jié)點(diǎn)隨機(jī)放置的500 m×500 m的矩形區(qū)域中。在這些傳感節(jié)點(diǎn)中，有32個(gè)錨節(jié)點(diǎn)。這些錨節(jié)點(diǎn)具有確切的位置信息，而其他移動(dòng)傳感節(jié)點(diǎn)位置信息未知。假定所有的傳感節(jié)點(diǎn)都有相同的射頻距離r，定義為50 m。一個(gè)節(jié)點(diǎn)能夠監(jiān)聽到射頻范圍內(nèi)的其他節(jié)點(diǎn)并且相互之間能夠直接進(jìn)行通信，這就表示節(jié)點(diǎn)能夠判斷其他節(jié)點(diǎn)是否在射頻距離r內(nèi)，并且可以利用RSSI來測量距離。RSSI測距模型已經(jīng)在§2.1中給出。等式(4)中，參數(shù)、設(shè)定為實(shí)驗(yàn)觀察值，設(shè)定如下:=26.5=40

為了仿真動(dòng)態(tài)節(jié)點(diǎn)，假定所有節(jié)點(diǎn)都服從附有最大速度vmax的隨機(jī)路點(diǎn)運(yùn)動(dòng)模型(random waypoint model，RWP)。在這種模型中，各個(gè)節(jié)點(diǎn)在到達(dá)目的地之前，各個(gè)時(shí)間段的移動(dòng)速度都會小于最大速度vmax。在每個(gè)順次時(shí)間步中，節(jié)點(diǎn)先被定位，然后服從隨機(jī)路點(diǎn)運(yùn)動(dòng)模型進(jìn)行移動(dòng)，每個(gè)定位步驟必須要在一個(gè)時(shí)間單元中完成。在仿真方案中，設(shè)定一個(gè)時(shí)間單元為1 s，樣本數(shù)目N=50。對MCL和MCB算法仿真設(shè)定類同。

3.2 定位誤差

定位誤差是指節(jié)點(diǎn)實(shí)際位置和估算位置之間的距離差。在動(dòng)態(tài)網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動(dòng)特性影響定位，因此不同時(shí)刻定位誤差不同。本方案模擬仿真了前50個(gè)時(shí)間步下的定位誤差。當(dāng)節(jié)點(diǎn)最大運(yùn)行速度為10 m/s，即vmax=0.2r時(shí)，仿真結(jié)果如圖3所示。

圖3 定位精度

蒙特卡羅算法通過挖掘先驗(yàn)信息來定位當(dāng)前節(jié)點(diǎn)，其定位精度會隨時(shí)間變化而提高。圖3表明，MCL、MCB和改進(jìn)算法在開始時(shí)間段內(nèi)定位精度迅速提高；但是在一段時(shí)間后，定位誤差會在一個(gè)最小值附近上下浮動(dòng)。圖1也表明，相較于MCL和MCB，改進(jìn)算法的定位誤差在絕大部分時(shí)間步內(nèi)都是最小的。在仿真條件vmax=0.2r下，改進(jìn)算法的定位精度要比MCL算法高35% ～60%，平均高47%。

3.3 最大運(yùn)行速度

節(jié)點(diǎn)的最大運(yùn)行速度被用作區(qū)域半徑來預(yù)測節(jié)點(diǎn)位置。一方面，最大運(yùn)行速度值越大，預(yù)測區(qū)域就越大；另一方面，節(jié)點(diǎn)移動(dòng)越快，監(jiān)聽到的錨節(jié)點(diǎn)就越多，過濾掉的無效位置也越多。兩方面的原因使得最大運(yùn)行速度會對定位精度產(chǎn)生很大的影響。最大運(yùn)行速度對各種算法定位誤差的影響如圖4所示。

圖4 最大運(yùn)行速度的影響

圖4表明，在最大速度從0.1r增加到0.4r過程中，改進(jìn)算法的定位誤差隨之減小；之后最大速度的增加使得定位誤差有所增加。MCL和MCB算法的定位誤差變化趨勢和改進(jìn)算法的變化趨勢相似。但是它們的定位誤差相較于改進(jìn)算法總是稍大。由圖4可得，改進(jìn)算法的定位誤差比MCL算法低20% ～56%，平均33%。

3.4 錨節(jié)點(diǎn)密度

錨節(jié)點(diǎn)密度是指在一跳傳輸范圍內(nèi)的平均錨節(jié)點(diǎn)數(shù)目。當(dāng)錨節(jié)點(diǎn)密度增加時(shí)，定位精度也隨之提高。由于錨節(jié)點(diǎn)成本較高，定位算法在錨節(jié)點(diǎn)密度低時(shí)也需要有足夠的定位精度。

圖5表明了不同錨節(jié)點(diǎn)密度下，不同定位算法平均定位誤差的變化。當(dāng)錨節(jié)點(diǎn)密度提高時(shí)，所有定位算法的定位誤差都會減小。當(dāng)錨節(jié)點(diǎn)密度小于1時(shí)，改進(jìn)算法的定位誤差總會比MCL和MCB算法的定位誤差小。

圖5 錨節(jié)點(diǎn)密度的影響

4 總結(jié)

針對于動(dòng)態(tài)無線傳感器網(wǎng)絡(luò)，本文提出了一種基于蒙特卡羅算法的改進(jìn)定位算法。這種算法利用RSSI測距來限制樣本區(qū)域，取得了相對較好的定位效果。仿真表明，在不同速度及錨節(jié)點(diǎn)密度的情況下，改進(jìn)算法較其他算法而言能夠取得更好的定位精度。此外，這種算法減少了無效的取樣處理，可以降低傳感節(jié)點(diǎn)計(jì)算能量消耗。因此，在優(yōu)化蒙特卡羅定位算法方面，限制樣本區(qū)域的可行性較好。

［1］唐克，謝保軍，盧金星.基于蒙特卡羅的無線傳感器網(wǎng)絡(luò)戰(zhàn)場目標(biāo)定位模型［J］.兵工自動(dòng)化，2011，30(4):31－35.

［2］朱斌，譚勇，黃江波.基于ZigBee無線定位技術(shù)的安全監(jiān)測系統(tǒng)設(shè)計(jì)［J］.計(jì)算機(jī)測量與控制，2010，18(6):1247－1252.

［3］張燦明，周孟然，陳君蘭，等.ZigBee定位技術(shù)在瓦斯監(jiān)測系統(tǒng)中的應(yīng)用［J］.煤炭技術(shù)，2011，30(3):105－106.

［4］Smith A，Balakrishnan H，Goraczko M，et al.Tracking Moving Devices with the Cricket Location System［C］//Proceedings of the 2nd International Conference on Mobile Systems，Applications，and Services，Boston，2004:190－202.

［5］石為人，賈傳江，梁煥煥.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］.傳感技術(shù)學(xué)報(bào)，2011，24(1):83－87.

［6］Cheng W，Li J，Li H.An Improved APIT Location Algorithm for Wireless Sensor Networks［J］.Advances in Electrical Engineering and Automation，2012，139:113－119.

［7］Doherty L，Pister K S J.Convex Position Estimation in Wireless Sensor Networks［C］//Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，Anchorage，2001，3:1655－1663.

［8］Yi S，Ruml W，Zhang Y，et al.Localization from Mere Connectivity［C］//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking ＆ Computing，Maryland，2003:201－212.

［9］Hu L，Evans D.Localization for Mobile Sensor Networks［C］//Proceedings of the 10th Annual International Conference on Mobile Computing and Networking，Pennsylvania，2004:45－47.

［10］Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Networks［J］.Lecture Notes in Computer Science，2006，4325(11):317－328.

［11］Yu Q，Wang W，Qin Z，Mao Y，et al.RSS-Based Monte Carlo Nodes Localization in Wireless Ad-Hoc Networks［C］//Proceedings of the International Conference on Communications，Circuits and Systems，Milpitas，2009:217－221.

［12］Yi J，Yang S，Cha H.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，2007:163－171.

［13］方震，趙湛，郭鵬，等.基于RSSI測距分析［J］.傳感技術(shù)學(xué)報(bào)，2007，20(11):2526－2530.

［14］Bahl P，Padmanabhan V N.RADAR:An In-Building RF-Based User Location and Tracking System［C］//Proceeding of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies，Tel Aviv，2000，2:775－784.

［15］Xu J，Liu W，Lang F，et al.Distance Measurement Model Based on RSSI in WSN［J］.Wireless Sensor Network，2010，2(8):606－611.