基于時(shí)序蒙特卡洛的WSN節(jié)點(diǎn)定位算法*

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

（1.蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州730070；2.光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室，蘭州730070）

基于時(shí)序蒙特卡洛的WSN節(jié)點(diǎn)定位算法*

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

（1.蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州730070；2.光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室，蘭州730070）

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

無線傳感器網(wǎng)絡(luò)；時(shí)序排列；蒙特卡洛定位；定位算法

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

1 相關(guān)工作

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

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

2 MCL基本原理

在WSN監(jiān)測區(qū)域內(nèi)隨機(jī)部署P個(gè)目標(biāo)節(jié)點(diǎn)和M個(gè)錨節(jié)點(diǎn)。目標(biāo)節(jié)點(diǎn)具有以下特征：節(jié)點(diǎn)是隨機(jī)運(yùn)動的；每個(gè)節(jié)點(diǎn)運(yùn)動模型是獨(dú)立的；節(jié)點(diǎn)具有相同的屬性。針對單個(gè)目標(biāo)節(jié)點(diǎn)，MCL算法主要通過預(yù)測和過濾兩個(gè)階段來實(shí)現(xiàn)定位，MCL算法流程圖如圖1。

圖1 MCL算法流程圖

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

初始位置：目標(biāo)節(jié)點(diǎn)沒有其相關(guān)位置的任何信息，因此在給定部署區(qū)域內(nèi)隨機(jī)選取N個(gè)樣本點(diǎn)作為位置樣本集

t時(shí)刻：

式中，d(lt,lt-1)為節(jié)點(diǎn)在t時(shí)刻和t-1時(shí)刻所處位置的歐幾里得距離。可見，隨著節(jié)點(diǎn)最大移動速度Vmax的增大，對應(yīng)的采樣區(qū)域范圍亦會擴(kuò)大，這樣便增大了定位誤差。若加入節(jié)點(diǎn)運(yùn)動模型的相關(guān)信息，根據(jù)運(yùn)動模型來縮小采樣區(qū)域，便會提高采樣效率，減小定位誤差。

圖2 MCL采樣區(qū)域

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

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

圖3 一跳、二跳錨節(jié)點(diǎn)約束區(qū)域

經(jīng)過一次過濾后剩余的有效采樣點(diǎn)數(shù)量不足以達(dá)到定位條件，便要在采樣區(qū)域內(nèi)進(jìn)行重新采集并重復(fù)過濾過程，直至有效樣本數(shù)達(dá)到設(shè)定數(shù)目為止。

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

3 TSMCL定位算法原理

3.1 TSMCL實(shí)現(xiàn)過程

基于時(shí)序的MCL定位算法主體思想是：在WSN中，錨節(jié)點(diǎn)周期性的向周圍發(fā)射掃描波，目標(biāo)節(jié)點(diǎn)在接收到至少3個(gè)不同錨節(jié)點(diǎn)發(fā)射來的信號時(shí)，便進(jìn)入預(yù)測階段。錨節(jié)點(diǎn)所發(fā)射的掃描波每到達(dá)一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)就立即進(jìn)行反饋。錨節(jié)點(diǎn)根據(jù)所反饋回信息時(shí)間的長短來對周圍節(jié)點(diǎn)進(jìn)行排序。

圖4 單個(gè)錨節(jié)點(diǎn)A掃描的采樣區(qū)域

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

圖5所示為錨節(jié)點(diǎn)A與錨節(jié)點(diǎn)B共同掃描的過程。通過錨節(jié)點(diǎn)B在t時(shí)刻的掃描波反饋序列：AQC，可判斷出：目標(biāo)節(jié)點(diǎn)Q在以錨節(jié)點(diǎn)B為圓心，以節(jié)點(diǎn)A、B間的距離為半徑的圓外；且在以B為圓心，以B、C間的距離為半徑的圓內(nèi)。由錨節(jié)點(diǎn)A、B預(yù)測的目標(biāo)節(jié)點(diǎn)Q在t時(shí)刻的采樣區(qū)域范圍如圖中陰影區(qū)域。

圖5 2個(gè)錨節(jié)點(diǎn)A、B掃描的采樣區(qū)域

圖6所示為3個(gè)錨節(jié)點(diǎn)A、B、C共同掃描的過程。通過錨節(jié)點(diǎn)C在t時(shí)刻的掃描波反饋時(shí)序排列為：QAB，則可判定：目標(biāo)節(jié)點(diǎn)Q在以錨節(jié)點(diǎn)C為圓心，以節(jié)點(diǎn)C、A間的距離為半徑的圓內(nèi)。根據(jù)3個(gè)錨節(jié)點(diǎn)得到的時(shí)序排列便構(gòu)成一個(gè)陰影區(qū)域，它表示目標(biāo)節(jié)點(diǎn)Q在t時(shí)刻位置信息的采樣范圍。

圖6 3個(gè)錨節(jié)點(diǎn)A、B、C共同掃描的采樣區(qū)域

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

令錨節(jié)點(diǎn)A、B、C的坐標(biāo)分別為（xA，yA），（xB，yB）和（xC，yC），錨節(jié)點(diǎn)A與B，A與C，B與C間的距離分別為r1，r2和r3，（X，Y）為陰影區(qū)域（見圖6）內(nèi)的節(jié)點(diǎn)坐標(biāo)。于是可得

在TSMCL算法中，采樣區(qū)域的縮小與反饋時(shí)序確定出的圓環(huán)數(shù)目有關(guān)。令節(jié)點(diǎn)Q在t-1時(shí)刻的位置存在于錨節(jié)點(diǎn)與其他兩個(gè)錨節(jié)點(diǎn)組成的圓環(huán)內(nèi)的圓環(huán)數(shù)目為h，則不規(guī)則陰影區(qū)域的頂點(diǎn)數(shù)k滿足

由于兩個(gè)圓的交點(diǎn)最多有兩個(gè)，但只有一個(gè)是陰影區(qū)域內(nèi)的頂點(diǎn)，因此需要剔除采樣陰影區(qū)域外的頂點(diǎn)。在圖6中，令4個(gè)頂點(diǎn)1，2，3，4的坐標(biāo)值分別為：

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

圖7 初始采樣區(qū)域

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

于是，外接矩形對角線上的兩個(gè)頂點(diǎn)E和F的坐標(biāo)值（x矩1min，y矩1min）和（x矩1max，y矩1max）為

以EF為對角線構(gòu)造的矩形即為目標(biāo)節(jié)點(diǎn)Q可能的初始采樣區(qū)域R1。

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

以HI為對角線構(gòu)造的矩形即為目標(biāo)節(jié)點(diǎn)Q的最終采樣區(qū)域R。

圖8 TSMCL算法的最終采樣區(qū)域

接下來是預(yù)測和過濾階段。每個(gè)采樣點(diǎn)都是在預(yù)測區(qū)域內(nèi)隨機(jī)生成的，預(yù)測過后，采樣點(diǎn)便進(jìn)入過濾階段。TSMCL算法的采樣點(diǎn)預(yù)測和過濾可分別表示為

預(yù)測：

過濾：

在預(yù)測階段先采集N個(gè)樣本點(diǎn)，過濾后將不符合條件的采樣點(diǎn)濾除，剩余的有效樣本數(shù)目將少于N。當(dāng)有效樣本數(shù)未達(dá)到規(guī)定值時(shí)，便重復(fù)預(yù)測和過濾階段，直到采集到足夠多的有效樣本。

3.2 TSMCL算法步驟

Step1：錨節(jié)點(diǎn)將自身信息傳遞給其周圍的1跳和2跳鄰居錨節(jié)點(diǎn)；

Step2：判斷目標(biāo)節(jié)點(diǎn)是否具備定位條件（目標(biāo)節(jié)點(diǎn)能否接收到至少3個(gè)一跳錨節(jié)點(diǎn)信息），若滿足條件，轉(zhuǎn)Step3，否則等待一段時(shí)間繼續(xù)判斷；

Step3：根據(jù)目標(biāo)節(jié)點(diǎn)的1跳鄰居錨節(jié)點(diǎn)收集到的反饋時(shí)序信息，構(gòu)建初始采樣區(qū)域R1；

Step4：將R1與MCL采樣區(qū)域R2（取決于目標(biāo)節(jié)點(diǎn)在t-1時(shí)刻的位置和節(jié)點(diǎn)最大移動速度Vmax）交疊，形成目標(biāo)節(jié)點(diǎn)Q的最終采樣區(qū)域R；

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

Step7：當(dāng)所采集的有效樣本數(shù)目達(dá)到規(guī)定值時(shí)，則轉(zhuǎn)Step8，否則轉(zhuǎn)Step5；

Step8：計(jì)算目標(biāo)節(jié)點(diǎn)在t時(shí)刻的位置，本次定位結(jié)束；轉(zhuǎn)Step2開始下一時(shí)刻的定位。

4 仿真實(shí)驗(yàn)

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

定位算法的優(yōu)劣常用平均定位誤差δ來評估，它被定義為：節(jié)點(diǎn)估計(jì)位置(xi,yi)與實(shí)際位置(Xi,Yi)的歐氏距離與節(jié)點(diǎn)通信半徑的比值：

圖9 節(jié)點(diǎn)分布示意圖

4.1 錨節(jié)點(diǎn)密度與平均定位誤差的關(guān)系

錨節(jié)點(diǎn)密度是網(wǎng)絡(luò)中錨節(jié)點(diǎn)個(gè)數(shù)占節(jié)點(diǎn)總數(shù)的比率。圖10所示為錨節(jié)點(diǎn)密度對節(jié)點(diǎn)平均定位誤差的影響。由圖可看出，隨著錨節(jié)點(diǎn)密度的增加，三種定位算法的定位誤差均有不同程度的減小。這是因?yàn)?，錨節(jié)點(diǎn)密度越大，目標(biāo)節(jié)點(diǎn)所接收到的觀測信息越多，三種定位算法的定位精度均有所改善。TSMCL算法是通過目標(biāo)節(jié)點(diǎn)周圍的一跳鄰居錨節(jié)點(diǎn)實(shí)施的定位，若錨節(jié)點(diǎn)密度增大，其周圍的一跳鄰居錨節(jié)點(diǎn)數(shù)量也會增加，因此它的定位誤差最小。

圖10 錨節(jié)點(diǎn)密度對定位誤差的影響

4.2 節(jié)點(diǎn)最大速度Vmax與平均定位誤差的關(guān)系

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

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

4.3 算法采樣次數(shù)

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

圖12 算法采樣次數(shù)分析

5 結(jié)語

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

［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］夏少波，朱曉麗，鄒建梅.基于跳數(shù)修正的DV-Hop改進(jìn)算法［J］.傳感技術(shù)學(xué)報(bào)，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］鄧成玉，王宇崢，谷曉英，等.基于細(xì)菌覓食算法和跳段校正的無線傳感器網(wǎng)絡(luò)定位算法［J］.燕山大學(xué)學(xué)報(bào)，2014，38（6）：544-555.

［7］劉士興，黃俊杰，劉宏銀，等.基于多通信半徑的加權(quán)DV-Hop定位算法［J］.傳感技術(shù)學(xué)報(bào)，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］劉偉榮，何云.物聯(lián)網(wǎng)與無線傳感器［M］.北京：電子工業(yè)出版社，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］劉志華，李改燕，劉曉爽.基于最小二乘法的蒙特卡洛移動節(jié)點(diǎn)定位算法［J］.傳感技術(shù)學(xué)報(bào)，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］朱紅松，孫利民.無線傳感器網(wǎng)絡(luò)技術(shù)發(fā)展現(xiàn)狀［J］.中興通訊技術(shù)，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］董齊芬，俞麗，陳友榮，等.移動無線傳感網(wǎng)中的迭代蒙特卡洛定位算法研究［J］.傳感技術(shù)學(xué)報(bào)，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-），男，漢族，遼寧沈陽人，蘭州交通大學(xué)碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)、無線通信技術(shù)，1064816535@qq.com；

李翠然（1975-），女，漢族，山西黎城人，蘭州交通大學(xué)教授，博士生導(dǎo)師，主要研究方向?yàn)殍F路無線通信、無線傳感網(wǎng)、移動自組網(wǎng)技術(shù)，licr@mail.lzjtu.cn；

謝健驪（1972-），男，漢族，甘肅隴西人，蘭州交通大學(xué)副教授，碩士生導(dǎo)師，主要研究方向?yàn)殍F路無線通信、認(rèn)知無線電、移動自組網(wǎng)技術(shù)，xiejl@mail.lzjtu.cn；

梁櫻馨（1992-），女，漢族，甘肅蘭州人，蘭州交通大學(xué)碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署、無線通信技術(shù)。

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

項(xiàng)目來源：國家自然科學(xué)基金項(xiàng)目（61261014）；光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室（蘭州交通大學(xué)）開放課題項(xiàng)目（KFKT2016-2）；甘肅省自然科學(xué)基金項(xiàng)目（148RJZA037）

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