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

陳萬志，張洋，李曌成

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

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

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

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

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

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

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

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

1 引言

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

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

2 傳統(tǒng)MCL算法

2.1 MCL算法描述

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

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

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

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

2.2 MCL算法分析

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

圖2 過濾階段示意圖

3 DV-MCL算法

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

（1）初始化階段

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

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

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

（2）預(yù)測(cè)階段

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

圖3 信標(biāo)節(jié)點(diǎn)廣播分組的傳播過程

其中hAlt、hBlt和hClt分別代表信標(biāo)節(jié)點(diǎn)A、B、C與t時(shí)刻未知節(jié)點(diǎn)間的最小跳數(shù)；由圖3可知，t時(shí)刻未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的實(shí)際距離小于或等于估計(jì)距離（因?yàn)橛猛ㄐ虐霃阶鳛槊刻嚯x會(huì)帶來測(cè)距誤差，一般會(huì)使估計(jì)距離略大于實(shí)際距離），因此lt以信標(biāo)節(jié)點(diǎn)A、B、C為圓心，dAlt、dBlt和dClt為半徑的三個(gè)圓內(nèi)，即lt一定在圓A、B、C的相交區(qū)域內(nèi)；再由圖1可知，lt也一定在以t-1時(shí)刻的位置lt-1為圓心，最大運(yùn)動(dòng)速度vmax為半徑的圓中，故lt一定在四個(gè)圓的相交區(qū)域內(nèi)，如圖4中的陰影區(qū)域所示。

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

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

（3）過濾階段

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

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

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

圖5 DV-MCL算法流程圖

4 性能仿真及分析

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

4.1 定位精度

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

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

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

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

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

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

圖7 最大運(yùn)動(dòng)速度與節(jié)點(diǎn)定位誤差間的關(guān)系

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

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

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

4.2 采樣次數(shù)

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

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

5 結(jié)束語

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

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

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

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

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

[5]劉輝亞，徐建波.無線傳感器網(wǎng)絡(luò)分布式的移動(dòng)節(jié)點(diǎn)定位研究[J].計(jì)算機(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é)點(diǎn)選擇模型的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào)，2011，24（2）：264-268.

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

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

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

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

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

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

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

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

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