縮小采樣區域的蒙特卡羅移動節點定位算法

陳萬志，張洋，李曌成

1.遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島 125105

2.渤海裝備遼河重工有限公司，遼寧盤錦 124010

縮小采樣區域的蒙特卡羅移動節點定位算法

陳萬志1，張洋1，李曌成2

1.遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島 125105

2.渤海裝備遼河重工有限公司，遼寧盤錦 124010

針對無線傳感器網絡中移動節點定位問題，提出一種適用于未知節點移動而信標節點固定的改進蒙特卡羅定位算法，充分利用信標節點與未知節點間的測距誤差來縮小采樣區域，提高采樣效率。仿真結果表明，改進算法在信標節點密度、連通度和節點最大運動速度等不同情況下均能提高定位精度，減少采樣次數和計算量，延長網絡的生存周期。

無線傳感器網絡；蒙特卡羅定位；移動節點；采樣區域

1 引言

無線傳感器網絡（Wireless Sensor Network，WSN）是由大量的傳感器節點組成的自組織的網絡，是許多學科高度交叉的學科，可以用于許多惡劣且不適應人類工作的環境。事件發生的位置或獲取信息的節點位置是傳感器節點監測消息中的重要信息，沒有位置信息的監測數據往往毫無意義，因此對于WSN來說，傳感器節點的位置信息至關重要。因此，傳感器網絡節點定位技術的研究已成為WSN的研究熱點和難點[1-5]。

根據定位過程中是否需要測距把定位技術分為基于測距的定位技術（TOA、TDOA、AOA和RSSI）和與測距無關的定位技術（質心定位、DV-Hop、Amorphous和APIT）兩大類；以上算法均適用于固定節點定位。隨著WSN技術的發展，出現了移動節點，2004年Virginia大學的HU Lingxuan等首次將用于機器人定位的蒙特卡羅算法（Monte Carlo Localization，MCL）應用在WSN移動節點定位中；隨后許多學者就此提出探討研究[6-16]，文獻[6]提出一種單一移動輔助種子節點的MA-MCL算法；文獻[7-8]提出采用運動預測模型提高移動節點的定位精度；文獻[9]將MCL與RSSI算法相結合提高采樣效率；文獻[10]將最小二乘法與MCL算法相結合推算未知節點在下一時刻可能的位置區域實現快速抽樣和樣本過濾；文獻[11]提出迭代蒙特卡羅定位算法實現在信標節點數較少的情況下提高定位的準確度；文獻[12]提出在移動WSN中節點間互相優化定位方法，精確鎖定節點位置區域，提高采樣效率和定位精度；文獻[13]提出基于模糊理論的改進蒙特卡羅移動節點定位算法，在縮短定位時間的同時提高定位精度；文獻[14]提出一種蟻群算法和MCL相結合的算法，在信標節點比例低的情況下提高定位精度；文獻[15]提出一種距離相關的蒙特卡羅（DRMCL）算法來提高定位精度；文獻[16]針對定位節點和參考節點隨機運動的網絡模型提出基于動態網格劃分的蒙特卡羅定位算法，在定位精度、計算開銷、能耗等方面都具有較好的性能。上述算法在一定程度上解決了傳統MCL算法在WSN應用中的一些不足。

2 傳統MCL算法

2.1 MCL算法描述

MCL算法主要有預測和過濾兩個階段。其中預測階段主要實現對未知節點在以t-1時刻的位置lt-1為圓心，最大運動速度vmax為半徑的圓中，如圖1所示，隨機抽取N個樣本組成樣本集合

圖1 MCL的采樣區域

過濾階段主要實現對傳感器節點根據t時刻接收到的一跳和兩跳信標節點信息，把不滿足過濾條件的采樣位置濾掉，其過濾條件如式（1）所示。

其中s1是未知節點在t時刻的一跳信標節點，S1是未知節點在t時刻的一跳信標節點集合，s2是未知節點在t時刻的兩跳信標節點，S2是未知節點在t時刻的兩跳信標節點集合，d(，s1)代表t時刻第i個樣本與一跳信標節點間的歐幾里德距離，d(，s2)代表t時刻第i個樣本與兩跳信標節點間的歐幾里德距離，r為節點通信半徑。也就是說，如果采樣樣本與一跳信標節點間的距離小于等于r，則該樣本符合過濾條件，如圖2（a）所示，反之則刪除此樣本；如果采樣樣本與兩跳信標節點之間的距離大于r且小于等于2r，則該樣本符合過濾條件，如圖2（b）中陰影部分所示，反之則刪除此樣本。若過濾后留下的樣本數小于N，則在采樣區域循環預測和過濾兩個階段，直到留下的樣本數為N。

2.2 MCL算法分析

傳統MCL算法在預測階段采集許多樣本，在過濾階段要對樣本逐個進行篩選，必然導致計算量較大，若過濾后樣本數少于N，則還要循環預測和過濾階段，這樣會使計算量變得更大；其原因在于有許多樣本落在了位置后驗密度值較小的區域中，而這些樣本對估計未知節點位置的作用非常小，最終導致采樣成功率降低；如果能夠減小采樣區域，則采集位置后驗密度較大的樣本自然能夠很好解決上述問題。

圖2 過濾階段示意圖

3 DV-MCL算法

通過傳統MCL算法分析和文獻檢索，擬提出一種縮小采樣區域方法實現對MCL算法的改進，稱為DV-MCL算法。其主要思路是：首先用DV-Hop算法求未知節點初始位置；然后利用未知節點與信標節點間的測距誤差對移動未知節點在t時刻的位置區域進行限定，從而縮小了傳統MCL算法的采樣區域，提高了采樣成功率和定位精度，減少了計算量和能耗，延長了網絡生存周期。具體DV-MCL算法過程描述如下：

（1）初始化階段

由于未知節點在此時尚未移動，所以網路的拓撲結構沒有發生變化，因此可以把此時的移動未知節點看作固定未知節點，故用DV-Hop定位算法確定未知節點的初始位置。具體過程為：首先信標節點廣播自身的位置信息到整個網絡，所有節點記錄到每個信標節點的最小跳數；其次，信標節點根據式（2）估算出平均每跳距離HopSizei；

其中(xi，yi)，(xj，yj)分別為信標節點i和j的坐標，hj是信標節點i與j(j≠i)之間的跳數；然后，再根據式（3）求出信標節點i和未知節點l0間的距離dil0；

其中hil0為信標節點i和未知節點l0之間的跳數；最后，選擇距未知節點l0最近的三個信標節點的位置信息，根據三邊測量法求出未知節點l0的坐標(xl0，yl0)。

（2）預測階段

首先要確定采樣區域；當未知節點運動到t時刻，設通信半徑為r，t時刻未知節點的位置為lt，信標節點首先廣播自身位置信息，如圖3所示，未知節點記錄到所有信標節點的最小跳數；選出距未知節點跳數最少的三個信標節點A、B、C，分別用式（4）～（6）求出它們之間的估計距離dAlt、dBlt和dClt。

圖3 信標節點廣播分組的傳播過程

其中hAlt、hBlt和hClt分別代表信標節點A、B、C與t時刻未知節點間的最小跳數；由圖3可知，t時刻未知節點與信標節點之間的實際距離小于或等于估計距離（因為用通信半徑作為每跳距離會帶來測距誤差，一般會使估計距離略大于實際距離），因此lt以信標節點A、B、C為圓心，dAlt、dBlt和dClt為半徑的三個圓內，即lt一定在圓A、B、C的相交區域內；再由圖1可知，lt也一定在以t-1時刻的位置lt-1為圓心，最大運動速度vmax為半徑的圓中，故lt一定在四個圓的相交區域內，如圖4中的陰影區域所示。

圖4 DV-MCL算法的采樣區域

其次，在采樣區域中隨機選擇N個樣本組成樣本集合L。

（3）過濾階段

由式（1）濾除不符合條件的采樣樣本，記錄留下的樣本數。若此時留下的樣本數少于N，則重復進行采樣和過濾直至留下的樣本數為N。最后根據式（7）求出lt的坐標(xlt，ylt)。

當未知節點運動到下一時刻位置，重復上述預測和過濾階段，直到未知節點不再運動為止，定位結束。

DV-MCL算法流程圖如圖5所示。

圖5 DV-MCL算法流程圖

4 性能仿真及分析

本文在Matlab R2013b環境下，將MCL算法、文獻[8]的改進算法和DV-MCL算法在定位精度和采樣次數兩方面進行仿真對比。

4.1 定位精度

場景1在100 m×100 m的正方形區域內，隨機布置100個傳感器節點，其中40個信標節點，60個未知節點，最大運動速度vmax設定為2 m/s，采樣個數N為100，定位誤差e用式（8）求出。

其中(x′lt，y′lt)是未知節點在t時刻的真實位置，(xlt，ylt)是未知節點在t時刻的估計位置，r為通信半徑。

圖6反映了第k個未知節點在不同網絡連通度下的定位誤差。由圖6可知三種算法的定位誤差均隨著網絡連通度增大而減小；在相同網絡連通度下，DV-MCL算法的定位誤差遠小于MCL算法和文獻[8]的改進算法。

圖6 網絡連通度與節點定位誤差間的關系

場景2在100 m×100 m的正方形區域中，隨機布置100個傳感器節點，其中40個信標節點，60個未知節點，采樣個數N為100，通信半徑r為20 m。

圖7為節點最大運動速度與定位誤差的關系。由圖7可知三種算法的定位誤差均隨著vmax增加而變大，但DV-MCL算法變化較緩慢，其原因為DV-MCL算法的采樣區域為圖4中的陰影部分，隨著vmax的增大，采樣區域最大為圓A、B、C的相交處，與MCL算法和文獻[8]的改進算法相比，采樣區域減小的同時采樣成功率提高了，故DV-MCL算法的曲線與MCL算法和改進算法的曲線相比較平滑，vmax對DV-MCL算法的定位誤差影響較小；且在相同vmax情況下，DV-MCL算法的定位誤差小于MCL算法和文獻[8]的改進算法。

圖7 最大運動速度與節點定位誤差間的關系

場景3在100 m×100 m的正方形區域中，隨機布置100個未知節點，采樣個數N為100，通信半徑r為20 m，最大運動速度為2 m/s，信標節點的個數從20～120依次增加。

圖8反映出信標節點個數與節點定位誤差的關系。由圖8可知隨著信標節點個數的增加，三種算法的定位誤差均下降且總體來講DV-MCL算法的定位誤差要小于其他兩種算法。原因在于隨著信標節點增加，過濾條件會更準確，定位誤差就會逐漸減小；同時改進算法隨著信標節點數增加，在預測階段能夠選出更好的信標節點參與定位。

圖8 信標節點個數與節點定位誤差間的關系

4.2 采樣次數

圖9反映了場景2中，最大運動速度與節點采樣次數間的關系。從圖9可知三種算法的采樣次數都隨著vmax增大而增加，但DV-MCL算法的增加幅度較小，當vmax達到一定程度時，DV-MCL算法的采樣次數逐漸穩定；在相同vmax的條件下，DV-MCL算法的采樣次數比MCL算法和改進算法的采樣次數少。

圖9 最大運動速度與節點采樣次數間的關系

5 結束語

在用固定節點定位算法求出移動未知節點初始位置的同時，提出了一種縮小采樣區域的方法對原MCL算法進行改進。經仿真可知，通過DV-Hop算法求未知節點的初始位置，可以提高初始位置的準確性；在較小的采樣區域中采樣，可以提高采樣成功率，減少采樣次數和計算量，確保了算法效率，同時延長了網絡生存周期，增加了定位精度；算法適用于未知節點移動而信標節點固定的WSN網絡。

[1]孫立民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005：135-136.

[2]唐鷺，洪月華，伍華健.無線傳感器網絡節點定位綜合算法[J].計算機工程與應用，2010，46（4）：86-88.

[3]黃曉利，王福豹，段渭軍，等.基于在線校正的無線傳感器網絡定位算法[J].計算機工程與應用，2008，44（6）：133-135.

[4]衛開夏，田金鵬，王克謙.無線傳感網絡DV-Hop定位改進算法[J].傳感技術學報，2010，23（12）：1820-1823.

[5]劉輝亞，徐建波.無線傳感器網絡分布式的移動節點定位研究[J].計算機工程與應用，2010，46（1）：72-76.

[6]Teng Guodong，Zheng Kougen，Dong Wei.MA-MCL：Mobile-Assisted Monte Carlo Localization for Wireless Sensor Networks[J].International Journal of Distributed Sensor Networks，2011，2011.

[7]李敏，羅挺，徐華.一種基于參考節點選擇模型的無線傳感器網絡定位算法[J].傳感技術學報，2011，24（2）：264-268.

[8]黃梅根，常新峰.一種基于蒙特卡羅的無線傳感器網絡移動節點定位算法研究[J].傳感技術學報，2010，23（4）：562-565.

[9]朱海平，于紅丞，鐘小勇，等.動態無線傳感器網絡的改進蒙特卡洛定位算法[J].傳感技術學報，2012，25（9）：1284-1288.

[10]劉志華，李改燕，劉曉爽.基于最小二乘法的蒙特卡洛移動節點定位算法[J].傳感技術學報，2012，25（4）：541-544.

[11]董齊芬，俞立，陳友榮，等.移動無線傳感網中的迭代蒙特卡羅定位算法研究[J].傳感技術學報，2010，23（12）：1803-1808.

[12]梅舉，陳滌，辛玲.基于蒙特卡洛方法的移動傳感網節點定位優化算法[J].傳感技術學報，2013，26（5）：689-694.

[13]李建坡，時明，謝巖，等.一種基于模糊理論的蒙特卡洛移動節點定位算法[J].計算機應用與軟件，2013，30（12）：147-150.

[14]王培東，祁春莉.一種改進的節點定位方法[J].計算機應用與軟件，2012，29（8）：242-244.

[15]彭保，顧學邁，丁博.動態傳感器網絡中距離相關的蒙特卡洛定位算法[J].科學技術與工程，2008，8（18）：5301-5303.

[16]魏葉華，李仁發，羅娟，等.基于動態網格劃分的移動無線傳感器網絡定位算法[J].計算機研究與發展，2008，45（11）：1920-1927.

CHEN Wanzhi1,ZHANG Yang1,LI Zhaocheng2

1.School of Electronics and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China
2.China Petroleum Liaohe Equipment Company,Panjin,Liaoning 124010,China

In response to the problem of mobile node position for WSN,an improved MCL algorithm for mobile unknown node and fixed beacon node is proposed.Sampled area is reduced to improve the sampling efficiency by using the ranging error of beacon node and unknown node sufficiently.The simulation results show that the improved algorithm can improve the localization accuracy,reduce the number of sampling and computation,and prolong the network life cycle in different conditions of the beacon node density,connectivity and the maximum velocity of node.

Wireless Sensor Network（WSN）;Monte Carlo Localization（MCL）;mobile nodes;sampled area

A

TP393

10.3778/j.issn.1002-8331.1403-0363

CHEN Wanzhi,ZHANG Yang,LI Zhaocheng.Monte Carlo localization algorithm for mobile node by reducing sampled area.Computer Engineering and Applications,2014,50（21）：106-110.

陳萬志（1977—），男，在讀博士，副教授，CCF會員，研究領域為人工智能、計算機過程控制、物聯網應用等；張洋（1989—），女，在讀碩士研究生，研究領域為無線傳感網絡、計算機過程控制等；李曌成（1937—），男，助工，研究領域為計算機控制及電氣安全。E-mail：chenwanzhi@lntu.edu.cn

2014-03-25

2014-05-10

1002-8331（2014）21-0106-05

CNKI出版日期：2014-07-02，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1403-0363.html