基于時序蒙特卡洛的WSN節點定位算法*

田浩杉，李翠然*，謝健驪，2，梁櫻馨

（1.蘭州交通大學電子與信息工程學院，蘭州730070；2.光電技術與智能控制教育部重點實驗室，蘭州730070）

基于時序蒙特卡洛的WSN節點定位算法*

田浩杉1，李翠然1*，謝健驪1，2，梁櫻馨1

（1.蘭州交通大學電子與信息工程學院，蘭州730070；2.光電技術與智能控制教育部重點實驗室，蘭州730070）

針對無線傳感器網絡（WSN）中的移動節點定位問題，提出了一種將反饋時間序列與蒙特卡洛相結合的定位算法TSMCL（Feedback Time Series-Based Monte Carlo）。該算法基于目標節點1跳范圍內的鄰居錨節點（至少3個）反饋信號的先后順序，構建了節點可能的初始采樣區域R1，并以區域R1與蒙特卡洛采樣區域R2的重疊區作為新的采樣區域R，以進一步縮小采樣范圍、提高采樣效率。仿真結果表明：與蒙特卡洛定位算法相比，提出的TSMCL算法能夠減少約38%的定位誤差，尤其當節點移動速度較高時，算法的收斂速度也得到了顯著提升。

無線傳感器網絡；時序排列；蒙特卡洛定位；定位算法

無線傳感器網絡WSN（Wireless Sensor Net?works）是指傳感器節點以多跳、自組織的形式組成的一個無線通信系統［1］。大量的微型傳感器部署在所要監測的區域內，傳感器節點對感興趣的目標進行觀測并獲取其信息報告給觀察者，從而實現了對監測區域的監控。對WSN的研究主要側重于三個方面：網絡節點部署、網絡能耗和節點定位。本論文是針對移動節點的定位展開研究，正所謂沒有位置信息檢測的消息是沒有意義的［2］。WSN節點定位可以根據是否需要距離的測量分為基于測距（range-based）定位算法和無需測距（range-free）定位算法兩大類。在節點定位的研究初期，主要采用基于測距的手段［3］。它根據錨節點和目標節點之間的相對位置和角度直接測量二者的距離，再由所得到的信息通過三邊測量法，三角測量法以及極大似然估計等算法進行具體定位。非測距類定位算法則是憑借網絡的連通度信息來估計出錨節點與目標節點間的距離，然后根據估計的距離來進行定位。目前非測距類定位算法有DV-Hop算法［4-5］、質心算法、APIT算法等。與基于測距的算法相比，非測距類算法的網絡生存能力強，無需額外的硬件設備，更適合大規模無線傳感器網絡的應用［6-7］。但是，這些方法大多沒有考慮節點的移動性。伴隨著節點能夠在監測區域內移動，使得移動WSN在事件的監測上有其固有的優勢并已經得到日益廣泛的應用，比如在列車定位中，要對不斷移動的目標進行實時的定位，了解列車的位置信息。由此可見，對于移動WSN的定位研究現如今已成為一個熱點方向［8］。

1 相關工作

針對移動WSN中節點的定位，早在2004年蒙特卡洛定位MCL（Monte-Carlo Location）算法便被從機器人定位中引入到了移動WSN中，雖然MCL定位算法拋開了節點移動性的干擾，甚至節點移動速度越大定位精度越高，但是該算法的采樣成功率很低并且容易出現粒子退化的問題［9］。近年來很多學者對其進行了改進，文獻［10］提出了蒙特卡洛盒子定位MCB（Monte-CarloLocation Boxed）算法，通過錨箱（Anchor Box）和采樣箱（Sample Box）來縮小采樣區域從而提高采樣效率。但是當觀測模型分布在錨箱的比重很小時，采樣的成功率仍然很低［11-12］。文獻［13］提出了動態靜態網絡節點定位MSL（Mobile and Stat?ic Sensor Network Location）算法，該算法利用了鄰居節點中定位精度較高的節點來輔助定位，但其計算過程非常復雜，通信耗能也比較大。文獻［14］將DVHop引入到了MCL定位中提出了多跳蒙特卡洛定位MMCL（Multi-hop-based Monte-Carlo Localization）算法，該算法充分利用了錨節點的信息，在低錨節點密度的網絡中能表現出良好的定位性能。上述算法從不同角度對MCL算法進行了改進，但是在網絡拓撲變化比較頻繁的高速移動網絡環境下，上述算法的穩定性和網絡生存性則存在一定的性能缺陷。

本文是在MCL定位算法的基礎上引入了一種錨節點對反饋回信號的時間長短進行排序的方法來縮小待定位節點采樣區域。主要思想是：WSN的每個錨節點將自身信息（坐標，ID號等）傳遞給其周圍的一跳和兩跳鄰居錨節點并以數據包形式保存。錨節點周期性發射掃描波信號，目標節點在接收到其周圍至少3個一跳鄰居錨節點信息時，即可實施定位。錨節點發射的信號每觸碰到一個節點，該節點便進行反饋，錨節點對反饋信號的時間進行排序，即反饋時間短的離錨節點近，反饋時間長的離錨節點遠。由3個鄰居錨節點根據反饋時間得到了一個采樣區域。TSMCL算法通過該采樣區域與MCL采樣區域的交集，優化并縮小了節點采樣區域，提高了采樣效率和定位精度。

2 MCL基本原理

在WSN監測區域內隨機部署P個目標節點和M個錨節點。目標節點具有以下特征：節點是隨機運動的；每個節點運動模型是獨立的；節點具有相同的屬性。針對單個目標節點，MCL算法主要通過預測和過濾兩個階段來實現定位，MCL算法流程圖如圖1。

圖1 MCL算法流程圖

在MCL算法中，時間被分割成等長的時間段，令t={1,2,3,…}表示離散的時間，同時假設Vmax為節點的最大移動速度。

初始位置：目標節點沒有其相關位置的任何信息，因此在給定部署區域內隨機選取N個樣本點作為位置樣本集

t時刻：

式中，d(lt,lt-1)為節點在t時刻和t-1時刻所處位置的歐幾里得距離?？梢?，隨著節點最大移動速度Vmax的增大，對應的采樣區域范圍亦會擴大，這樣便增大了定位誤差。若加入節點運動模型的相關信息，根據運動模型來縮小采樣區域，便會提高采樣效率，減小定位誤差。

圖2 MCL采樣區域

②過濾階段：根據節點在t時刻所接收到的由一跳鄰居錨節點和二跳鄰居錨節點發來的觀測信息對采樣點進行篩選，把不符合要求的點過濾掉。令S為目標節點的1跳錨節點集，T為其2跳錨節點集，r為錨節點的通信半徑，l為采樣粒子，s代表錨節點。對于采樣點l的過濾條件可表示為：

符合約束條件的采樣區域如圖3（a）和圖3（b）所示。

圖3 一跳、二跳錨節點約束區域

經過一次過濾后剩余的有效采樣點數量不足以達到定位條件，便要在采樣區域內進行重新采集并重復過濾過程，直至有效樣本數達到設定數目為止。

MCL算法雖然在一定的程度上解決了粒子在運動狀態下的定位問題，但是該算法由于采樣區域較大，導致采樣效率不高，采樣的成功率很低。隨著迭代次數的增加，粒子退化現象變得嚴重?；诖?，論文著手通過縮小采樣區域的方法來提高采樣效率，從而提高節點定位精度。

3 TSMCL定位算法原理

3.1 TSMCL實現過程

基于時序的MCL定位算法主體思想是：在WSN中，錨節點周期性的向周圍發射掃描波，目標節點在接收到至少3個不同錨節點發射來的信號時，便進入預測階段。錨節點所發射的掃描波每到達一個節點，該節點就立即進行反饋。錨節點根據所反饋回信息時間的長短來對周圍節點進行排序。

圖4 單個錨節點A掃描的采樣區域

圖4給出了單個錨節點A的掃描過程。假設錨節點A、B、C為目標節點Q的一跳鄰居節點。于是可以得到，錨節點A在t時刻的掃描波反饋信息時序排列為：QBC，即說明目標節點Q在以錨節點A為圓心，以節點A、B之間的距離為半徑的圓內。

圖5所示為錨節點A與錨節點B共同掃描的過程。通過錨節點B在t時刻的掃描波反饋序列：AQC，可判斷出：目標節點Q在以錨節點B為圓心，以節點A、B間的距離為半徑的圓外；且在以B為圓心，以B、C間的距離為半徑的圓內。由錨節點A、B預測的目標節點Q在t時刻的采樣區域范圍如圖中陰影區域。

圖5 2個錨節點A、B掃描的采樣區域

圖6所示為3個錨節點A、B、C共同掃描的過程。通過錨節點C在t時刻的掃描波反饋時序排列為：QAB，則可判定：目標節點Q在以錨節點C為圓心，以節點C、A間的距離為半徑的圓內。根據3個錨節點得到的時序排列便構成一個陰影區域，它表示目標節點Q在t時刻位置信息的采樣范圍。

圖6 3個錨節點A、B、C共同掃描的采樣區域

理論上分析，若參與掃描的目標節點的1跳鄰居錨節點數量越多，得到的反饋時序排列信息就會越全面，由這些時序信息構建的陰影采樣區域便會越小，有利于提高節點的采樣效率和樣本采集的準確性。然而，錨節點數目的增多會導致定位算法復雜度急劇增加，因此論文中以3個錨節點為例來分析TSMCL算法的定位過程。

令錨節點A、B、C的坐標分別為（xA，yA），（xB，yB）和（xC，yC），錨節點A與B，A與C，B與C間的距離分別為r1，r2和r3，（X，Y）為陰影區域（見圖6）內的節點坐標。于是可得

在TSMCL算法中，采樣區域的縮小與反饋時序確定出的圓環數目有關。令節點Q在t-1時刻的位置存在于錨節點與其他兩個錨節點組成的圓環內的圓環數目為h，則不規則陰影區域的頂點數k滿足

由于兩個圓的交點最多有兩個，但只有一個是陰影區域內的頂點，因此需要剔除采樣陰影區域外的頂點。在圖6中，令4個頂點1，2，3，4的坐標值分別為：

由式（5）～式（8），可求得各頂點坐標為(x11,y11)和(x12,y12)；(x21,y21)和 (x22,y22)；(x31,y31)和(x32,y32)；(x41,y41)和 (x42,y42)。根據式（3）的約束條件對其進行篩選以過濾掉陰影區域以外的交點，于是得到采樣陰影區域內的各頂點坐標，記為(x′1,y′1)，(x′2,y′2)，(x′3,y′3)和(x′4,y′4)。通過錨節點信息所確定的初始采樣區域為不規則圖形，因此用該圖形的外接矩形表征初始采樣區域R1，見圖7。

圖7 初始采樣區域

為確定陰影區域的外接矩形，首先在統一坐標系下做各參考圓的外接正方形。根據式（3）的約束方程判斷其各邊是否經過或相切于陰影區域。在圖7中，經過或相切于陰影區域的直線有三條，可表示為：

于是，外接矩形對角線上的兩個頂點E和F的坐標值（x矩1min，y矩1min）和（x矩1max，y矩1max）為

以EF為對角線構造的矩形即為目標節點Q可能的初始采樣區域R1。

已有MCL算法是以目標節點在t-1時刻的位置為圓心，以節點最大移動速度Vmax為半徑做圓，將此圓的外接正方形看作目標節點t時刻位置的可能區域，記為蒙特卡洛采樣區域R2。在TSMCL算法中，我們以蒙特卡洛采樣區域R2與初始采樣區域R1的交疊區域作為新的樣本采樣區域R，見圖8中的網狀陰影區域。由圖8可看出，R為一個矩形，其對角線上的兩個頂點H和I的坐標值（x矩2min，y矩2min）和（x矩2max，y矩2max）可寫為

以HI為對角線構造的矩形即為目標節點Q的最終采樣區域R。

圖8 TSMCL算法的最終采樣區域

接下來是預測和過濾階段。每個采樣點都是在預測區域內隨機生成的，預測過后，采樣點便進入過濾階段。TSMCL算法的采樣點預測和過濾可分別表示為

預測：

過濾：

在預測階段先采集N個樣本點，過濾后將不符合條件的采樣點濾除，剩余的有效樣本數目將少于N。當有效樣本數未達到規定值時，便重復預測和過濾階段，直到采集到足夠多的有效樣本。

3.2 TSMCL算法步驟

Step1：錨節點將自身信息傳遞給其周圍的1跳和2跳鄰居錨節點；

Step2：判斷目標節點是否具備定位條件（目標節點能否接收到至少3個一跳錨節點信息），若滿足條件，轉Step3，否則等待一段時間繼續判斷；

Step3：根據目標節點的1跳鄰居錨節點收集到的反饋時序信息，構建初始采樣區域R1；

Step4：將R1與MCL采樣區域R2（取決于目標節點在t-1時刻的位置和節點最大移動速度Vmax）交疊，形成目標節點Q的最終采樣區域R；

Step5：在區域R中，隨機抽取足夠的樣本N；Step6：通過式（18）和式（19）判斷樣本集中的每個樣本是否有效，若無效則丟棄該樣本；

Step7：當所采集的有效樣本數目達到規定值時，則轉Step8，否則轉Step5；

Step8：計算目標節點在t時刻的位置，本次定位結束；轉Step2開始下一時刻的定位。

4 仿真實驗

實驗在Intel（R）Core（TM）i5-2450M CPU，主頻2.50 GHz、2.50 GHz，4 GB內存平臺，Matlab7.0仿真環境中進行的。實驗中構建一個500 m×500 m的無障礙監測區域，在該區域內隨機部署80個固定位置的錨節點。令錨節點的通信半徑為r=50 m，各個錨節點都具有測距和判斷其他節點是否在其通信范圍內的能力［15］。目標節點的移動基于Random Way?point模型［16］，它們在監測區域內相互獨立、以[0,Vmax]的速度隨機運動。圖9所示為監測區域內，各個錨節點和目標節點在某一時刻的位置信息。

定位算法的優劣常用平均定位誤差δ來評估，它被定義為：節點估計位置(xi,yi)與實際位置(Xi,Yi)的歐氏距離與節點通信半徑的比值：

圖9 節點分布示意圖

4.1 錨節點密度與平均定位誤差的關系

錨節點密度是網絡中錨節點個數占節點總數的比率。圖10所示為錨節點密度對節點平均定位誤差的影響。由圖可看出，隨著錨節點密度的增加，三種定位算法的定位誤差均有不同程度的減小。這是因為，錨節點密度越大，目標節點所接收到的觀測信息越多，三種定位算法的定位精度均有所改善。TSMCL算法是通過目標節點周圍的一跳鄰居錨節點實施的定位，若錨節點密度增大，其周圍的一跳鄰居錨節點數量也會增加，因此它的定位誤差最小。

圖10 錨節點密度對定位誤差的影響

4.2 節點最大速度Vmax與平均定位誤差的關系

圖11給出了隨節點Vmax的變化，三種定位算法的平均定位誤差變化趨勢。從圖中可看出，隨著Vmax的增大，三種定位算法的平均定位誤差的差異性逐漸縮小。Vmax是在定位過程中的兩個階段影響定位精度的。首先是預測階段，采樣區域與Vmax相關，Vmax的增加會導致采集樣本的準確度下降，這對三種定位算法的影響是一樣的；另一方面，在TSMCL算法中的每個定位時間段內，Vmax越大，目標節點能夠接收到的觀測信息就會越多，從而具有較小的定位誤差。

圖11 最大速度對定位誤差的影響

4.3 算法采樣次數

圖12給出了節點的移動速度與三種定位算法的采樣次數之間的關系。對于MCL算法：當目標節點移動速度較小時，能夠接收到的有效采樣信息的概率較大，需要的采樣次數較少，但當速度較小時，由于探測到的錨節點信息量并不充足，可能會導致定位失?。浑S著節點移動速度的增加，以最大移動速度為半徑所構建的采樣區域會隨之變大，采樣失敗率也隨之提高，所需要的采樣次數就會增加。對于MCB算法，由于采樣箱的建立縮小了采樣區域，使得它的采樣次數比MCL有所減少。TSMCL算法由于利用了目標節點1跳范圍內的鄰居錨節點信息構建采樣區域，并與MCL采樣區域相交疊以縮小采樣范圍，提高了采樣效率，有效降低了采樣次數。

圖12 算法采樣次數分析

5 結語

隨著無線傳感器網絡的飛速發展，節點定位技術也占據著重要地位。本文以MCL算法原理為基礎，提出了一種基于目標節點的1跳鄰居錨節點的反饋時序采樣機制，即TSMCL算法。該算法雖然在構建采樣區域時消耗了一些能量，但它極大程度地縮小了有效采樣區域，提高了采樣效率，減少了過濾時間。仿真實驗證明，相比MCL和MCB，文中的TSMCL算法在不同錨節點密度和不同節點移動速度下具有較低的定位誤差，定位精度有所提高。

［1］Hai-Yan Shi，Wan-Liang Wang，Ngai-Ming Kwok，et al.Game Theory for Wireless Sensor Networks：A Survey［J］.Sensors，2012，12（7）：9055-9097.

［2］Rabacy J M，Ammer M J，de Silva J L Jr，et al.Picorodio Supports Ad Hoc Ultra-Low Power Wireless Networking［J］.Computer，2000，33（7）：42-48.

［3］Yusuke W，Takamasa H，Hirozumi Y，et al.Accurate Positioning of Mobile Phones in a Crowd Using Laser Range Scanners［C］//2013 IEEE 9th International Conference on Wireless and Mobile Computing，2013：430-435.

［4］ZeKavat B.Handbook of Position Location：Theory，Practice and Advance［M］.NJ：Wiley&Sons，2012：359-395.

［5］夏少波，朱曉麗，鄒建梅.基于跳數修正的DV-Hop改進算法［J］.傳感技術學報，2015，28（5）：757-762.Xia Shaobo，Zhu Xiaoli，Zou Jianmei.The Improved DV-Hop Algorithm Based on Hop Count［J］.Chinese Journal of Sensors and Actuators，2015，28（5）：757-762.

［6］鄧成玉，王宇崢，谷曉英，等.基于細菌覓食算法和跳段校正的無線傳感器網絡定位算法［J］.燕山大學學報，2014，38（6）：544-555.

［7］劉士興，黃俊杰，劉宏銀，等.基于多通信半徑的加權DV-Hop定位算法［J］.傳感技術學報，2015，28（6）：883-887.Liu S X，Huang J J，Liu H Y，et al.An Improving DV-Hop Algo?rithm Based on Multi Communication Radius［J］.Chinese Journal of Sensors and Actuators，2015，28（6）：883-887.

［8］劉偉榮，何云.物聯網與無線傳感器［M］.北京：電子工業出版社，2013：141.

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

［10］Baggio A，Langendoen K.Monte Carlo Localization for Wireless Sensor Networks［C］//Proc of 2nd Int’l Confon Mobile Adhoc and Sensor Networks（MSN 2006）.Hong Kong Springer Verlag，2006：718-733.

［11］劉志華，李改燕，劉曉爽.基于最小二乘法的蒙特卡洛移動節點定位算法［J］.傳感技術學報，2012，25（4）：541-544.Liu Zhihua，Li Gaiyan，Liu Xiaoshuang.Monte-Carlo Mobile Node Localization Algorithms Based on Least Squares Method［J］.Chinese Journal of Sensors and Actuators，2012，25（4）：541-544.

［12］朱紅松，孫利民.無線傳感器網絡技術發展現狀［J］.中興通訊技術，2009，15（5）：1-5.

［13］Rudafshani M，Datta S.Localization in Wireless Sensor Networks［C］//Proceedings of the 6th International Symposium on Informa?tion Processing in Sensor Networks，Cambridge，MA，USA，2007：51-60.

［14］Yi Jiyong，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.

［15］董齊芬，俞麗，陳友榮，等.移動無線傳感網中的迭代蒙特卡洛定位算法研究［J］.傳感技術學報，2010，23（12）：1803-1809.Dong Qifen，Yu Li，Chen Yourong，et al.Iterative Monte Carlo Localization for Mobile Wireless Sensor Networks［J］.Chinese Journal of Sensors and Actuators，2010，23（12）：1803-1809.

［16］Camp T，Boleng J V.Davies：A Survey of Mobility Models for Ad Hoc Network Research［C］//WirelessCommunicationsand Mobile Computing，v2，n5，August，2002：483-502.

田浩杉（1992-），男，漢族，遼寧沈陽人，蘭州交通大學碩士研究生，主要研究方向為無線傳感器網絡節點定位技術、無線通信技術，1064816535@qq.com；

李翠然（1975-），女，漢族，山西黎城人，蘭州交通大學教授，博士生導師，主要研究方向為鐵路無線通信、無線傳感網、移動自組網技術，licr@mail.lzjtu.cn；

謝健驪（1972-），男，漢族，甘肅隴西人，蘭州交通大學副教授，碩士生導師，主要研究方向為鐵路無線通信、認知無線電、移動自組網技術，xiejl@mail.lzjtu.cn；

梁櫻馨（1992-），女，漢族，甘肅蘭州人，蘭州交通大學碩士研究生，主要研究方向為無線傳感器網絡節點部署、無線通信技術。

Node Localization Algorithm for WSN Based on Time Sequence Monte Carlo*

TIAN Haoshan1，LI Cuiran1*，XIE Jianli1，2，LIANG Yingxin1
（1.School of Electronics and Information Engineering，Lanzhou Jiao tong University，Lanzhou 730070，China；2.Key Laboratory of Opto-Technology and Intelligent Control Ministry of Education，Lanzhou 730070，China）

A new node localization algorithm is proposed for WSN（Wireless Sensor Network），which combines the feedback time series with the Monte Carlo localization，named as TSMCL.The possible initial sampling region of the target node，R1is determined by the feedback time order from no less than three anchor nodes，which are the one-hop neighbors of the target node.In order to shrink the sampling region and improve the sampling efficiency，the final sampling region R is limited to the overlapped area of R1and Monte Carlo sampling region（R2）.Simulation results demonstrate that compared with Monte Carlo localization，the proposed TSMCL algorithm reduce the posi?tioning error up to 38%or so，and meanwhile，the convergence speed is improved significantly，especially for high mobility.

WSN；chronological sequence；MCL；localization algorithm

TP393

A

1004-1699（2016）11-1724-07

EEACC：6150P 10.3969/j.issn.1004-1699.2016.11.016

項目來源：國家自然科學基金項目（61261014）；光電技術與智能控制教育部重點實驗室（蘭州交通大學）開放課題項目（KFKT2016-2）；甘肅省自然科學基金項目（148RJZA037）

2016-05-07 修改日期：2016-06-27