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

(華中科技大學，數(shù)字制造裝備與技術(shù)國家重點實驗室，武漢 430074)

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

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

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

1 蒙特卡羅定位算法

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

在文獻［9］中，定義了移動節(jié)點，并且把時間離散化為一個時間序列。由于一個傳感節(jié)點可能離開它目前的位置，這就需要在每個時間段對它進行重定位?；谝苿于厔莺陀^察數(shù)據(jù)，在每個時間段，將會獲得一系列的樣本，根據(jù)這些樣本將可以估計出節(jié)點的位置。MCL定位算法的定位過程如下:

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

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

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

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

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

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

2 改進蒙特卡羅定位算法

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

2.1 RSSI測距模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

改進算法的實現(xiàn)如下:

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

(1)初始化

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

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

取樣:

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

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

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

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

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

3 算法仿真分析

3.1 仿真方案

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

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

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

3.2 定位誤差

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

圖3 定位精度

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

3.3 最大運行速度

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

圖4 最大運行速度的影響

圖4表明，在最大速度從0.1r增加到0.4r過程中，改進算法的定位誤差隨之減?。恢笞畲笏俣鹊脑黾邮沟枚ㄎ徽`差有所增加。MCL和MCB算法的定位誤差變化趨勢和改進算法的變化趨勢相似。但是它們的定位誤差相較于改進算法總是稍大。由圖4可得，改進算法的定位誤差比MCL算法低20% ～56%，平均33%。

3.4 錨節(jié)點密度

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

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

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

4 總結(jié)

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

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

［2］朱斌，譚勇，黃江波.基于ZigBee無線定位技術(shù)的安全監(jiān)測系統(tǒng)設(shè)計［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］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］.傳感技術(shù)學報，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ù)學報，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.