基于蒙特卡洛方法的移動傳感網(wǎng)節(jié)點定位優(yōu)化算法

梅 舉，陳 滌*，辛 玲

(1.山東大學信息科學與工程學院濟南250199;2.濟寧國家半導體及顯示產(chǎn)品質(zhì)量監(jiān)督檢驗中心，山東濟寧272000)

在無線傳感器網(wǎng)絡(luò)的許多應(yīng)用中，節(jié)點的位置信息都是至關(guān)重要的。在大多數(shù)情況下，傳感器節(jié)點所采集的數(shù)據(jù)信息，如果脫離了節(jié)點的位置信息，將會變得沒有意義，例如，需要知道森林火災(zāi)的現(xiàn)場位置，戰(zhàn)場上敵方車輛運動的區(qū)域，天然氣管道泄露的具體地點等。無線傳感器網(wǎng)絡(luò)中的節(jié)點常常是隨機布撒的，對于上述這些問題，傳感器節(jié)點必須首先通過定位知道自身的地理位置信息，這是進一步采取措施和做出決策的基礎(chǔ)。

無線傳感器網(wǎng)絡(luò)根據(jù)測距方式的不同分為range-based和range-free兩種定位方式，也就是基于測距和無需測距兩類。通常的測距技術(shù)主要有:接收信號強度指示RSSI(Received Signal Strength Indicator)，到達時間TOA(Time of Arrival)，到達時間差TDOA(Time Difference of Arrival)，到達角度 AOA(Angle of Arrival)。位置未知的節(jié)點在得到與錨節(jié)點之間的距離信息后，采用三邊測量法或者極大似然估計法等方法，可以計算出自身的位置。rangebased定位精度較高，但是傳感器節(jié)點依賴于專門的硬件設(shè)備，成本較高，而range-free定位無需距離或者角度信息，受環(huán)境影響較小，硬件成本低，適合大規(guī)模的傳感器網(wǎng)絡(luò)，因此也是目前受到普遍關(guān)注的定位機制［1－5］。典型的距離無關(guān)的定位算法有質(zhì)心定位、DV-Hop、APIT、凸規(guī)劃、MDS-MAP 等。

目前的無線傳感器網(wǎng)絡(luò)節(jié)點定位研究，大多都是針對靜態(tài)WSN的，即節(jié)點保持靜止不動的無線傳感器網(wǎng)絡(luò)類型［6－9］。但是在實際環(huán)境中，傳感器節(jié)點處于運動狀態(tài)的移動WSN應(yīng)用十分廣泛，比如在目標跟蹤中，要對不斷移動的目標進行實時的定位［10－11］。同時，傳感器節(jié)點位置的移動能擴大其監(jiān)測的范圍，能夠克服靜態(tài)WSN中有節(jié)點死亡時會帶來監(jiān)聽區(qū)域真空的現(xiàn)象，節(jié)點的移動性使網(wǎng)絡(luò)能夠更好的發(fā)現(xiàn)事件并觀測事件，能為傳感器節(jié)點提供更好的通信質(zhì)量［12］。對于移動WSN節(jié)點定位的研究相對不足，而且絕大多數(shù)針對靜態(tài)WSN定位的方法在移動WSN中并不適用，現(xiàn)在對移動WSN的定位研究已經(jīng)成為一個研究熱點［13］。

1 移動WSN定位研究的相關(guān)工作

目前對于移動WSN的定位研究，最具代表性的是基于統(tǒng)計方法的定位，主要通過使用序列蒙特卡洛方法(粒子濾波)對節(jié)點可能存在的位置進行采樣和濾波，并用濾波得到的粒子估計出節(jié)點的位置，這也是移動WSN定位研究的一個熱點方向，經(jīng)典的算法主要有 MCL［14］、MCB［15］、MMCL［16］、MSL［17］、range-based-MCL［18］等。

MCL算法是由Hu和Evans提出來的移動WSN中距離無關(guān)的節(jié)點定位算法，該算法第一次將蒙特卡洛方法引入到移動WSN的節(jié)點定位中來，取得了比較理想的效果，節(jié)點的定位精度非但沒有因為節(jié)點的移動特性受到破壞，反而利用移動性提高了定位精度，并減小了定位的代價。該算法的研究結(jié)果表明，序列蒙特卡洛方法能夠有效的應(yīng)用于移動WSN的節(jié)點定位中。MCL算法采用了粒子濾波方法，過程比一般的定位算法更復雜一些，文獻［14］詳細介紹和討論了MCL算法。

在MCL算法的基礎(chǔ)上，Baggio A等人改進提出了MCB(Monte-Carlo Localization Boxed)算法，如圖1所示，待定位節(jié)點首先通過接收到的錨節(jié)點信息得到一個錨節(jié)點覆蓋區(qū)域——錨盒子，即圖1中陰影區(qū)域，然后根據(jù)上一時刻的采樣粒子和節(jié)點自身的運動狀態(tài)得到采樣盒子，如圖2中陰影區(qū)域所示，其中l(wèi)t－1表示節(jié)點在上一時刻的采樣粒子，Vmax為節(jié)點的最大運動速率，這里假設(shè)節(jié)點的運動服從隨機行走模型RWP模型［19］，即節(jié)點的運動方向和速率未知，但是知道節(jié)點的最大運動速率，所以可以得到以上一時刻采樣粒子lt－1為圓心，以Vmax為半徑的運動圓來預測節(jié)點的位置，這個運動圓與錨盒子的交集就是最后的采樣盒子。經(jīng)過這樣一個過程，就把采樣區(qū)域限制在一個采樣盒子里，提高了采樣成功率，節(jié)約了計算量，大大節(jié)省了定位時間，提高了定位精度，性能比MCL算法有了較大的改善。

圖1 MCB錨盒子

圖2 MCB采樣盒子

本文提出的 TSBMCL(Temporary Seed Based Monte Carlo Localization)算法，延用了MCB算法的蒙特卡洛盒思想，通過篩選出定位情況較好的節(jié)點作為臨時錨節(jié)點，來輔助其他節(jié)點進行定位，從而實現(xiàn)全網(wǎng)節(jié)點的定位精度的優(yōu)化，效果十分顯著，下面具體介紹一下本算法。

2 TSBMCL算法詳述

在移動無線傳感器網(wǎng)絡(luò)的節(jié)點定位過程中，有的節(jié)點會收到較多的錨節(jié)點信息，并具有相對較小的采樣錨盒子，有的節(jié)點則收到較少的錨節(jié)點信息，甚至收不到錨節(jié)點的信息，從而導致定位誤差較大或者不能進行位置估計。針對移動WSN中普遍存在的這種現(xiàn)象，本文提出了一種提高移動無線傳感器網(wǎng)絡(luò)節(jié)點定位精度的方法，即基于臨時錨節(jié)點的蒙特卡洛定位方法——TSBMCL算法。臨時錨節(jié)點，指的是自身定位精度較高而被臨時用作錨節(jié)點的普通節(jié)點。節(jié)點在定位過程中不會知道自身的定位誤差，但是可以通過一定的評判規(guī)則，將定位條件優(yōu)等的節(jié)點篩選出來，這部分節(jié)點的定位精度也是最高的，可以充當臨時錨節(jié)點，來優(yōu)化其他節(jié)點的定位條件。因此，算法的核心思想是通過一定的評判標準選出定位精度高的節(jié)點，并將這部分節(jié)點用作臨時錨節(jié)點，來協(xié)助其他節(jié)點進行定位，從而實現(xiàn)全網(wǎng)節(jié)點定位精度的優(yōu)化。

TSBMCL算法，包括臨時錨節(jié)點的選舉產(chǎn)生過程，以及臨時錨節(jié)點協(xié)助其他節(jié)點進行定位的過程。

臨時錨節(jié)點的產(chǎn)生過程，具體步驟為:

Step 1:網(wǎng)絡(luò)中的所有錨節(jié)點(即seed節(jié)點)在全網(wǎng)中洪泛自己的信息，這個被洪泛的數(shù)據(jù)幀包括(Xseed，Yseed)，IDseed，TTL，其中(Xseed，Yseed)表示錨節(jié)點的坐標值，IDseed表示該錨節(jié)點的序號，TTL是最大洪泛跳數(shù)，初始值設(shè)置為2.

Step 2:網(wǎng)絡(luò)中待定位的普通節(jié)點(即node節(jié)點)在收到錨節(jié)點的洪泛信息之后，記錄錨節(jié)點的坐標值和序號，如果TTL為2，則將其置為1并轉(zhuǎn)發(fā)，如果TTL為1，則將其置零不再轉(zhuǎn)發(fā)，從而保證錨節(jié)點的信息只被轉(zhuǎn)發(fā)兩次。

Step 3:錨節(jié)點信息洪泛完畢，所有node節(jié)點利用MCB算法中的方法得到自己的錨盒子anchor box，并根據(jù)錨盒子面積Sanchorbox，二跳以內(nèi)錨節(jié)點數(shù)Nnos，計算本node能否成為臨時錨節(jié)點的判斷權(quán)值TA，

其中，r為節(jié)點的通信半徑;Ns為網(wǎng)絡(luò)中錨節(jié)點的個數(shù);S為監(jiān)測區(qū)域的面積;Sd為錨節(jié)點密度，表示一跳通信半徑以內(nèi)的平均錨節(jié)點數(shù);Srefer為參照錨盒子面積，節(jié)點的錨盒子面積Sanchorbox將與之進行比對;α為校正因子，調(diào)整該參數(shù)可以設(shè)置參照錨盒子面積Srefer的縮放比例。

Step4:TA值低于1的節(jié)點暫時不進行自身定位，TA值高于1的節(jié)點采用MCB算法進行定位，并成為臨時錨節(jié)點，向周圍洪泛自身信息，內(nèi)容包括，IDnode，TTL。其中表示node的定位位置，IDnode表示該node的序號，TTL為最大洪泛跳數(shù)，初始值設(shè)置為2，洪泛方式與錨節(jié)點相同。洪泛過程完畢以后，TA值低于1的節(jié)點，如果沒有收到臨時錨節(jié)點的信息，則依據(jù)原來的錨節(jié)點信息使用MCB算法進行定位，如果收到臨時錨節(jié)點信息，則使用該信息進行定位。

臨時錨節(jié)點協(xié)助TA值低于1的節(jié)點定位的過程，分為以下步驟:

Step 1:設(shè)待定位node在(t－1)時刻的粒子集為，在 t時刻收到 n 個臨時錨節(jié)點信息后，通過以下公式確定臨時錨節(jié)點盒子，

其中β為校準半徑的調(diào)整因子，通過調(diào)整β的大小，可以調(diào)整rred的取值。

同時，該待定位node的錨節(jié)點盒子通過MCB算法得到，設(shè)為(xs_min，xs_max，ys_min，ys_max)，則該 node的最終錨盒子定義為下式，如圖3所示，

從而得到采樣盒子如下，

圖3 臨時錨節(jié)點覆蓋圖

Step 2:對采樣粒子進行濾波，濾波公式為，

其中ot表示觀測信息，S是一跳錨節(jié)點的集合，T是兩跳錨節(jié)點的集合，STA是一跳臨時錨節(jié)點的集合，TTA是兩跳臨時錨節(jié)點的集合，d(lt，s)是采樣粒子lt與(臨時)錨節(jié)點的歐幾里德距離。

濾波完成以后，如果粒子數(shù)不足所需要的數(shù)目N，則進行重采樣，并重復濾波過程，直到達到采樣數(shù)N或者達到最大采樣次數(shù)為止。

整個TSBMCL算法的流程如圖4所示。

圖4 TSBMCL算法流程圖

3 仿真結(jié)果與分析

在仿真實驗中，所有傳感器節(jié)點被隨機布撒在500 m×500 m的矩形區(qū)域中，通信半徑r為100 m，所有傳感器節(jié)點，包括普通節(jié)點和錨節(jié)點，均采用隨機行走模型(RWP)［19］，RWP模型是移動WSN最常見的運動模型之一，該模型中，節(jié)點在每一運動時刻隨機選擇運動速率和運動方向，且節(jié)點不知道自身的運動速率和方向，但是知道自身的最大運動速率為Vmax，方向為360°任意選擇，根據(jù)表1的參數(shù)，對TSBMCL與MCB兩種算法用MATLAB仿真50次求平均值。

表1 仿真參數(shù)設(shè)置

首先來驗證臨時錨節(jié)點的遴選公式是否正確可行，圖5顯示，臨時錨節(jié)點的定位誤差要比其他節(jié)點小得多，這說明式(3)能夠有效的選出定位效果最好的部分節(jié)點，并將它們用來協(xié)助其他節(jié)點進行定位。

圖5 臨時錨節(jié)點與其他節(jié)點的定位誤差對比

網(wǎng)絡(luò)中全部節(jié)點的定位誤差對比情況如圖6所示，TSBMCL算法對MCB算法的優(yōu)化效果是十分明顯的，整體定位精度提高了34%。

圖6 全網(wǎng)節(jié)點在兩種方法下的誤差對比

臨時錨節(jié)點個數(shù)的統(tǒng)計結(jié)果如圖7所示，平均每一次定位產(chǎn)生31個臨時錨節(jié)點。

圖7 臨時錨節(jié)點產(chǎn)生數(shù)量

利用臨時錨節(jié)點信息協(xié)助定位的節(jié)點稱為受助節(jié)點，這部分節(jié)點在全網(wǎng)所有節(jié)點中所占的比例如圖8所示，平均每一次定位有72%的節(jié)點受到協(xié)助，可見，TSBMCL的優(yōu)化范圍是非常大的。

圖8 節(jié)點優(yōu)化比例

錨節(jié)點密度變化情況下的定位誤差曲線如圖9和圖10所示，在錨節(jié)點密度Sd從0.5向5過渡的過程中，TSBMCL算法的定位精度始終高于MCB算法。圖10反映出TSBMCL算法定位精度比MCB算法提高的比例，精度提高的比例最大可達34%，最低也在10%以上。之所以圖10會呈現(xiàn)出先升后降的趨勢，是因為在錨節(jié)點密度非常小的時候，由于網(wǎng)絡(luò)中的錨節(jié)點太少，節(jié)點都很難獲得足夠好的錨節(jié)點信息，所以產(chǎn)生的臨時錨節(jié)點也非常少，對網(wǎng)絡(luò)定位優(yōu)化的貢獻不足，所以優(yōu)化效果較差。當錨節(jié)點密度增大時，網(wǎng)絡(luò)中有越來越多的節(jié)點定位情況變好而成為臨時錨節(jié)點，并協(xié)助其他節(jié)點進行定位，所以對網(wǎng)絡(luò)的優(yōu)化效果更顯著;但是當錨節(jié)點密度在3以上時，隨著錨節(jié)點密度繼續(xù)增大，網(wǎng)絡(luò)中所有節(jié)點的定位情況都越來越好，MCB算法與TSBMCL算法的差距也在逐漸縮小，但TSBMCL算法在定位精度上始終比MCB算法提高20%以上。

節(jié)點密度變化情況下的定位誤差曲線如圖11和圖12所示，隨著節(jié)點密度的增大，TSBMCL算法對MCB算法的優(yōu)化效果越顯著，在Nd大于10時，定位精度提高的比例超過20%，當節(jié)點密度在40以上時，TSBMCL比MCB的定位精度提高了接近50%。

圖9 錨節(jié)點密度變化情況下的誤差對比

圖10 錨節(jié)點密度變化情況下的定位精度提高比例

圖11 節(jié)點密度變化情況下的誤差對比

圖12 節(jié)點密度變化情況下的定位精度提高比例

4 結(jié)束語

本文提出的TSBMCL算法，首先通過節(jié)點計算自身的權(quán)值來遴選出臨時錨節(jié)點，并使用臨時錨節(jié)點來協(xié)助其他節(jié)點進行定位，間接地增加了網(wǎng)絡(luò)中錨節(jié)點的密度，從而優(yōu)化了全網(wǎng)節(jié)點的定位效果，在定位精度上比MCB算法有了較大的提高。作為一種距離無關(guān)的定位算法，對硬件要求不高，能夠滿足低成本高精度的移動WSN的定位要求。

［1］ Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Kluwer J.Telecommun.Syst，2003，22(1):267－280.

［2］ He T，Huang C，Blum B M，et al.Range-free Localization Schemes for Large Scale Sensor Networks［C］//Proceedings of The 9th annual international conference on Mobile computing and networking，San Diego，CA，2003:81－95.

［3］ Liu C，Wu K.Performance Evaluation of Range-Free Localization Methods for Wireless Sensor Networks［C］//Proceedings of The 24th IEEE International Performance，Computing，and Communications Conference，Phoenix，Arizona，2005:59－66.

［4］ Liu Jicheng，Wang Wenxiu，Shang Yintong.An Improving Localization Algorithm for Wireless Sensor Networks Based on DV-Hop［C］//Proceedings of the International Conference on Measurement，Information and Control，Harbin，2012(1):511－515.

［5］ Hu Tianyou.A Range-free Wireless Sensor Networks Localization Algorithm［C］//Proceedings of The 2nd International Conference on Engineering and Industries，Korea，2011:54－58.

［6］ Liu C，Wu K，He T.Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator［C］//Proceedings of IEEE Int’l Conf.Mobile Ad-Hoc and Sensor Systems(MASS)，F(xiàn)ort Lauderdale，USA，2004:516－518.

［7］ Sheu J P，Chen P C，Hsu C S.A Distributed Localization Scheme for Wireless Sensor Networks with Improved Grid-Scan and Vector-Based Refinement［J］.IEEE Transactions on Mobile Computing，2008，7(9):1110－1123.

［8］ 丁江鵬，陳曙.一種基于跳數(shù)比的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學報，2009，22(12):1823－1827.

［9］ 朱博，陳曙.一種無線傳感器網(wǎng)絡(luò)質(zhì)心定位改進算法［J］.傳感技術(shù)學報，2010，23(6):868－872.

［10］ Sheu J P，Hu W K，Lin J C.Distributed Localization Scheme for Mobile Sensor Networks［J］.IEEE Transactions on Mobile Computing，2010，9(4):516－526.

［11］ Isaac Amundson，Xenofon D Koutsoukos.A Survey on Localization for Mobile Wireless Sensor Networks［C］//Proceedings of the 2th International Workshop on Mobile Entity Localization and Tracking in GPS-less Environments，Orlando，2009:235－254.

［12］ Mrityunjay Singh，Monika sethi，Niranjan Lal，et al.A Tree Based Routing Protocol for Mobile Sensor Networks(MSNs)［J］.International Journal on Computer Science and Engineering，2010，2(1S):55－60.

［13］ Zhang Shigeng，Cao Jiannong，Chen Lijun，et al.Accurate and Energy-Efficient Range-Free Localization for Mobile Sensor Networks［J］.IEEE Transactions on Mobile Computing，2010，9(6):897－910.

［14］ Hu L，Evans D.Localization for Mobile Sensor Networks［C］//Proceedings of the 10th International Conference on Mobile Computing and Networking，Philadelphia，USA，2004:45－57.

［15］ Baggio A，Langendoen K.Monte-Carlo Localization for Mobile Wireless Sensor Networks［J］.Journal of Ad Hoc Networks，2006，6(5):718－733.

［16］ 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.

［17］ Rudafshani M，Datta S.Localization in Wireless Sensor Networks［C］//Proceedings of the 6th International Symposium on Information Processing in Sensor Networks，Cambridge，MA，USA，2007:51－60.

［18］ Dil B，Dulman S，Havinga P.Range-based Localization in Mobile Sensor Networks［C］//Proceedings of Wireless Sensor Networks-Third European Workshop，Zurich，Switzerland，2006，3868(LNCS):164－179.

［19］ Camp T，Boleng J，Davies V.A Survey of Mobility Models for Ad Hoc Networks Research［J］.Journal of Wireless Communications and Mobile Computing，2002，2(5):483－502.