陳萬志，張洋，李曌成

1.遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧葫蘆島 125105

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

縮小采樣區(qū)域的蒙特卡羅移動節(jié)點定位算法

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

1.遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧葫蘆島 125105

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

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

無線傳感器網(wǎng)絡(luò)；蒙特卡羅定位；移動節(jié)點；采樣區(qū)域

1 引言

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

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

2 傳統(tǒng)MCL算法

2.1 MCL算法描述

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

圖1 MCL的采樣區(qū)域

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

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

2.2 MCL算法分析

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

圖2 過濾階段示意圖

3 DV-MCL算法

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

（1）初始化階段

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

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

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

（2）預(yù)測階段

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

圖3 信標節(jié)點廣播分組的傳播過程

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

圖4 DV-MCL算法的采樣區(qū)域

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

（3）過濾階段

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

當(dāng)未知節(jié)點運動到下一時刻位置，重復(fù)上述預(yù)測和過濾階段，直到未知節(jié)點不再運動為止，定位結(jié)束。

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

圖5 DV-MCL算法流程圖

4 性能仿真及分析

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

4.1 定位精度

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

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

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

圖6 網(wǎng)絡(luò)連通度與節(jié)點定位誤差間的關(guān)系

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

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

圖7 最大運動速度與節(jié)點定位誤差間的關(guān)系

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

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

圖8 信標節(jié)點個數(shù)與節(jié)點定位誤差間的關(guān)系

4.2 采樣次數(shù)

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

圖9 最大運動速度與節(jié)點采樣次數(shù)間的關(guān)系

5 結(jié)束語

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

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

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

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

[4]衛(wèi)開夏，田金鵬，王克謙.無線傳感網(wǎng)絡(luò)DV-Hop定位改進算法[J].傳感技術(shù)學(xué)報，2010，23（12）：1820-1823.

[5]劉輝亞，徐建波.無線傳感器網(wǎng)絡(luò)分布式的移動節(jié)點定位研究[J].計算機工程與應(yīng)用，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]李敏，羅挺，徐華.一種基于參考節(jié)點選擇模型的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報，2011，24（2）：264-268.

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

[9]朱海平，于紅丞，鐘小勇，等.動態(tài)無線傳感器網(wǎng)絡(luò)的改進蒙特卡洛定位算法[J].傳感技術(shù)學(xué)報，2012，25（9）：1284-1288.

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

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

[12]梅舉，陳滌，辛玲.基于蒙特卡洛方法的移動傳感網(wǎng)節(jié)點定位優(yōu)化算法[J].傳感技術(shù)學(xué)報，2013，26（5）：689-694.

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

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

[15]彭保，顧學(xué)邁，丁博.動態(tài)傳感器網(wǎng)絡(luò)中距離相關(guān)的蒙特卡洛定位算法[J].科學(xué)技術(shù)與工程，2008，8（18）：5301-5303.

[16]魏葉華，李仁發(fā)，羅娟，等.基于動態(tài)網(wǎng)格劃分的移動無線傳感器網(wǎng)絡(luò)定位算法[J].計算機研究與發(fā)展，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會員，研究領(lǐng)域為人工智能、計算機過程控制、物聯(lián)網(wǎng)應(yīng)用等；張洋（1989—），女，在讀碩士研究生，研究領(lǐng)域為無線傳感網(wǎng)絡(luò)、計算機過程控制等；李曌成（1937—），男，助工，研究領(lǐng)域為計算機控制及電氣安全。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