錨節(jié)點(diǎn)稀疏環(huán)境下蒙特
--卡羅盒定位算法*

劉 宏， 張子揚(yáng)， 魏浩鵬

(江西理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，江西 贛州 341000)

錨節(jié)點(diǎn)稀疏環(huán)境下蒙特
--卡羅盒定位算法*

劉 宏， 張子揚(yáng)， 魏浩鵬

(江西理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，江西 贛州 341000)

提出一種適用于錨節(jié)點(diǎn)稀疏環(huán)境下的蒙特—卡羅盒定位(SDANMCB)算法。算法在定位過程中將定位精度高的節(jié)點(diǎn)轉(zhuǎn)換為虛擬錨節(jié)點(diǎn)來輔助其他待定位節(jié)點(diǎn)進(jìn)行定位；同時(shí)根據(jù)采樣箱的面積和附近錨節(jié)點(diǎn)數(shù)量調(diào)整定位所需要的樣本數(shù)；濾波后根據(jù)樣本的后驗(yàn)分布調(diào)整樣本權(quán)重。仿真結(jié)果表明：算法在定位精度、采樣效率上都有明顯提升,并且在錨節(jié)點(diǎn)密度較低時(shí)定位效果有較大改善。

無線傳感器網(wǎng)絡(luò)； 錨節(jié)點(diǎn)； 蒙特—卡羅； 采樣優(yōu)化

0 引 言

在無線傳感器網(wǎng)絡(luò)(WSNs)的實(shí)際應(yīng)用中，節(jié)點(diǎn)經(jīng)常處于移動(dòng)的狀態(tài)，網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)之間約束關(guān)系不斷地發(fā)生變化,如何在移動(dòng)WSNs中實(shí)現(xiàn)節(jié)點(diǎn)高效、高精度定位是WSNs的研究熱點(diǎn)之一[1]。

對(duì)于節(jié)點(diǎn)的移動(dòng)性研究,Hu L等人將移動(dòng)機(jī)器人定位中廣泛應(yīng)用的蒙特—卡羅定位 (Monte-Carlo localization，MCL)改進(jìn)成適用于WSNs的定位方法[2]，但當(dāng)錨節(jié)點(diǎn)密度較低時(shí)，算法的采樣效率會(huì)大幅下降；之后有學(xué)者提出的蒙特—卡羅盒 (Monte-Carlo boxed，MCB)算法[3]在采樣時(shí)期引入錨節(jié)點(diǎn)信息來鎖定采樣區(qū)域，以期提升采樣的效率；文獻(xiàn)[4]引入運(yùn)動(dòng)軌跡模型來優(yōu)化采樣區(qū)，對(duì)樣本的權(quán)值進(jìn)行優(yōu)化，通過曲線擬合優(yōu)化節(jié)點(diǎn)的采集區(qū)域，減少了采樣次數(shù)，使得定位準(zhǔn)確性有所提升。但是算法需要節(jié)點(diǎn)前3個(gè)時(shí)刻位置數(shù)據(jù)，導(dǎo)致內(nèi)存空間擴(kuò)大；文獻(xiàn)[5]根據(jù)節(jié)點(diǎn)測(cè)距信息的誤差會(huì)使節(jié)點(diǎn)的通信半徑很難一致這一問題，通過將DV-Hop和MCL結(jié)合多跳方式來解決這一問題。但由于網(wǎng)絡(luò)中節(jié)點(diǎn)時(shí)刻移動(dòng)著，因此,多跳會(huì)降低定位精度；文獻(xiàn)[6]考慮到待定位節(jié)點(diǎn)周圍的錨節(jié)點(diǎn)數(shù)量并不相同，而這種差異性最終會(huì)導(dǎo)致節(jié)點(diǎn)的定位精度不同，針對(duì)這一現(xiàn)象提出一種基于臨時(shí)錨節(jié)點(diǎn)的蒙特—卡羅定位方法,通過虛擬錨節(jié)點(diǎn)來輔助待定位節(jié)點(diǎn)進(jìn)行定位。相較于MCB算法，該算法對(duì)節(jié)點(diǎn)的定位精度有所提升。

針對(duì)上述問題，本文提出一種適用于錨節(jié)點(diǎn)稀疏環(huán)境下的蒙特—卡羅盒(SDANMCB)定位算法，在定位中通過閾值選出定位精度好的節(jié)點(diǎn)來輔助其他節(jié)點(diǎn)定位，實(shí)現(xiàn)節(jié)點(diǎn)間的相互優(yōu)化。根據(jù)采樣箱面積和錨節(jié)點(diǎn)數(shù)量調(diào)整定位所需樣本數(shù)；在粒子濾波階段后，根據(jù)樣本后驗(yàn)分布調(diào)整樣本權(quán)重，進(jìn)一步提升節(jié)點(diǎn)定位精度。

1 SDANMCB定位算法介紹

SDANMCB定位算法基本思想是：在采樣階段，同樣考慮到不可能所有節(jié)點(diǎn)周圍分布著一定數(shù)量的錨節(jié)點(diǎn)，可以將已定位二跳內(nèi)鄰居節(jié)點(diǎn)設(shè)置為虛擬錨節(jié)點(diǎn)來輔助定位，間接提升網(wǎng)絡(luò)內(nèi)錨節(jié)點(diǎn)密度；同時(shí)引進(jìn)擴(kuò)張系數(shù)，通過適當(dāng)放大虛擬錨節(jié)點(diǎn)的通信距離，減小虛擬錨節(jié)點(diǎn)自身定位誤差帶來的影響。通過采樣面積的大小調(diào)整所需樣本數(shù)；通過離子濾波條件過濾無效樣本。最后在位置估計(jì)時(shí)根據(jù)樣本值與虛擬錨節(jié)點(diǎn)之間的距離來設(shè)置相應(yīng)的權(quán)值，通過計(jì)算出待定位節(jié)點(diǎn)的參考位置。具體如下：

首先選擇定位精度較高的移動(dòng)節(jié)點(diǎn)為虛擬錨節(jié)點(diǎn)：網(wǎng)絡(luò)內(nèi)待定位節(jié)點(diǎn)根據(jù)2跳范圍內(nèi)的錨節(jié)點(diǎn)數(shù)量i、錨盒子面積Aachorbox來判斷是否滿足成為虛擬錨節(jié)點(diǎn)的條件，閾值可根據(jù)式(1)計(jì)算確定

(1)

式中 nd為全網(wǎng)絡(luò)內(nèi)錨節(jié)點(diǎn)數(shù)量，R為節(jié)點(diǎn)通信半徑，A為整個(gè)檢測(cè)區(qū)域面積，Sd為錨節(jié)點(diǎn)密度，φ為樣本優(yōu)化因子。若待定位節(jié)點(diǎn)計(jì)算的Q值小于閾值1時(shí)，暫不定位，當(dāng)待定位節(jié)點(diǎn)的Q值大于閾值1時(shí)，采用MCB算法進(jìn)行定位，并將其設(shè)定為虛擬錨節(jié)點(diǎn)。當(dāng)全網(wǎng)絡(luò)內(nèi)滿足Q值的節(jié)點(diǎn)完成定位后，其余未達(dá)到Q值的待定位節(jié)點(diǎn)再進(jìn)行定位。由于已定位的節(jié)點(diǎn)做為虛擬錨節(jié)點(diǎn)存在定位誤差，因此,需將虛擬錨節(jié)點(diǎn)的通信距離適度擴(kuò)張，引入擴(kuò)張系數(shù)q，使其坐標(biāo)更接近節(jié)點(diǎn)真實(shí)位置。q值根據(jù)式(2)確定

q=αAanchorbox/iR2,

(2)

式中 α為樣本校正因子，優(yōu)化q值的選取。選定虛擬錨節(jié)點(diǎn)后，再對(duì)其他節(jié)點(diǎn)定位。

1.1 采樣階段

待定位節(jié)點(diǎn)根據(jù)收到的錨節(jié)點(diǎn)和虛擬錨節(jié)點(diǎn)信息通過式(3)確定其錨盒子

i=1,2,…,n,

(3)

式中 xi,yi為節(jié)點(diǎn)收到的虛擬錨節(jié)點(diǎn)和錨節(jié)點(diǎn)Si的坐標(biāo)，當(dāng)Si為1跳錨節(jié)點(diǎn)時(shí)，g=1，h=0；Si為一跳虛擬錨節(jié)點(diǎn)時(shí)，g=1，h=1；當(dāng)Si是2跳錨節(jié)點(diǎn)時(shí)，g=2，h=0；Si為二跳虛擬錨節(jié)點(diǎn)時(shí)，g=2，h=1。將錨盒子結(jié)合節(jié)點(diǎn)在lt時(shí)刻的位置根據(jù)式(4)構(gòu)建采樣盒

(4)

圖1 SDANMCB定位算法采樣區(qū)域Fig 1 Sampling area of SDANMCB localization algorithm

在MCL和MCB以及其他改進(jìn)算法中，均是采集固定的樣本數(shù)N個(gè)，但多數(shù)情況下，由于節(jié)點(diǎn)通信范圍內(nèi)錨節(jié)點(diǎn)數(shù)目不同其采樣區(qū)域也不同。當(dāng)節(jié)點(diǎn)周圍錨節(jié)點(diǎn)數(shù)量較多，其采樣區(qū)域減小，在這種情形下，可采集少量樣本數(shù)即可得出精確的定位值，而不必因?yàn)镹值未到，重復(fù)采樣，浪費(fèi)節(jié)點(diǎn)耗能。在此，可根據(jù)式(5)確定采樣數(shù)

(5)

1.2 濾波階段

根據(jù)粒子濾波條件去除無效的樣本點(diǎn)。如式(6)所示

filter(lA)=(?s1∈S1,d(lA,s1)≤R)∩

(?c1∈C1,d(lA,c1)≤R+q)∩

(?s2∈S2,R

(?c2∈C2,R+q

(6)

式中 S1,S2為節(jié)點(diǎn)的1跳和2跳錨節(jié)點(diǎn)集合，C1，C2為代表節(jié)點(diǎn)的1跳和2跳虛擬錨節(jié)點(diǎn)集合，d(lA,s1)為樣本lA與1跳錨節(jié)點(diǎn)s1之間的距離，d(lA,c1)為樣本點(diǎn)lA與1跳虛擬錨節(jié)點(diǎn)c1之間的距離,d(lA,s2)表示樣本點(diǎn)lA與2跳錨節(jié)點(diǎn)s2之間的距離，d(lA,c2)表示樣本點(diǎn)lA與2跳虛擬錨節(jié)點(diǎn)c2之間的距離。

濾波階段后若達(dá)不到所需采樣數(shù)Nf，則重復(fù)采樣和濾波步驟，直至達(dá)到采樣數(shù)。

1.3 位置估計(jì)

獲得滿足定位要求的樣本數(shù)后，對(duì)節(jié)點(diǎn)lA的位置進(jìn)行計(jì)算。在本算法中，由于適當(dāng)增加了虛擬錨節(jié)點(diǎn)的通信距離，因此，在位置估計(jì)時(shí)可將待定位節(jié)點(diǎn)根據(jù)與虛擬錨節(jié)點(diǎn)的距離賦予不同的權(quán)值，如圖2所示：l1,l2為待定位節(jié)點(diǎn)，c為C1集合內(nèi)的虛擬錨節(jié)點(diǎn)，由圖可知l1在c的通信半徑R內(nèi)，而l2在c的通信半徑R與R+q之間，l1相較l2更符合真實(shí)后驗(yàn)分布，由此l1所占樣本權(quán)重比例高于l2。以此推理，當(dāng)c為C2集合內(nèi)的虛擬錨節(jié)點(diǎn)時(shí)，后驗(yàn)分布區(qū)間變換為2R與2R+q之間。

圖2 樣本與虛擬信標(biāo)節(jié)點(diǎn)距離示意圖Fig 2 Diagram of distance between sample and virtual beacon nodes

(7)

通過各參考值及其對(duì)應(yīng)權(quán)重，便可計(jì)算出待定位節(jié)點(diǎn) 的參考位置。

2 仿真實(shí)驗(yàn)與分析

選用MCL-simulater[2]作為仿真工具，節(jié)點(diǎn)隨機(jī)分布在500m×500m區(qū)域內(nèi), 區(qū)域內(nèi)不包含任何障礙物，節(jié)點(diǎn)總數(shù)320個(gè),錨節(jié)點(diǎn)數(shù)量32個(gè)， 節(jié)點(diǎn)傳輸模型為理想的圓，DOI=0，其通信半徑R均為50m,校正因子(φ，α，ε)=(1,1,1)，采樣數(shù)N=50，節(jié)點(diǎn)在運(yùn)動(dòng)速率[0,vmax]內(nèi)按照隨機(jī)路點(diǎn)運(yùn)動(dòng)模型(randomwaypointmodel，RWP)[7]運(yùn)動(dòng)，vmas=50m/s定位周期為1s。對(duì)MCL,MCB,SDANMCB定位算法進(jìn)行20次仿真求平均值。

由圖3看出，在整個(gè)時(shí)間段內(nèi)，SDANMCB定位算法相較于MCL，MCB算法錨節(jié)點(diǎn)密度定位精度提升了23 %以上。由圖4可看出,當(dāng)Sd小于1時(shí)，本算法定位精度大大超過MCL和MCB算法，隨著錨節(jié)點(diǎn)密度提高，算法定位誤差減小，本算法由于虛擬錨節(jié)點(diǎn)數(shù)量的增加，其定位誤差仍比MCL和MCB算法誤差小。圖5表明:當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)速度很慢時(shí)，本文算法定位精度比MCL和MCB算法有較明顯的提高，隨著節(jié)點(diǎn)運(yùn)動(dòng)速度的增大，定位誤差增加，但本文算法定位誤差仍比MCB，MCL算法低。圖6中MCL，MCB，SDANMCB三種算法40s內(nèi)平均采樣次數(shù)分別為260,204,122，SDANMCB算法采樣次數(shù)相較于MCL,MCB算法大幅降低。

圖3 定位精度隨時(shí)間變化圖Fig 3 Diagram of change of localization precision with time

圖4 定位精度隨錨節(jié)點(diǎn)密度變化圖Fig 4 Diagram of change of localization precision with anchor node density

圖5 定位精度隨節(jié)點(diǎn)運(yùn)動(dòng)速度變化圖Fig 5 Diagram of change of localization precision with node moving speed

3 結(jié) 論

本文提出了一種適用于SDANMCB定位算法。仿真結(jié)果表明:SDANMCB定位算法與MCL，MCB算法相比，定位精度明顯提升，采樣次數(shù)有效降低，同時(shí)在錨節(jié)點(diǎn)密度較低時(shí)定位效果有較大改善，滿足WSNs低功耗運(yùn)行的要求。

圖6 采樣次數(shù)隨時(shí)間變化圖Fig 6 Diagram of change of sampling frequency with time

[1] Erol-Kantarci M, Mouftah H T, Oktug S.A survey of architectures and localization techniques for underwater acoustic sensor networks[J].Communications Surveys & Tutorials, IEEE, 2011, 13(3):487-502.

[2] Hu L, Evans D.Localization for mobile sensor networks[C]∥Proceedings of the 10th annual International Conference on Mobile Computing and Networking,ACM, 2004: 45-57.

[3] Baggio A,Langendoen K.Monte-Carlo localization for mobile wire-

less sensor networks[J].Ad Hoc Networks,2008,6(5):718-733.

[4] 孫 燕, 尚軍亮, 劉三陽.基于采樣優(yōu)化的蒙特—卡羅移動(dòng)節(jié)點(diǎn)定位算法[J].系統(tǒng)工程與電子技術(shù), 2010,32(9):2001-2004.

[5] Yi J, Yang S, Cha H.Multi-hop-based Monte-Carlo localization for mobile sensor networks[C]∥2007 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON’07,IEEE, 2007:162-171.

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

[7] Harri J, Filali F, Bonnet C.Mobility models for vehicular Ad Hoc networks: A survey and taxonomy[J].Communications Surveys & Tutorials, IEEE, 2009, 11(4): 19-41.

Monte-Carlo boxed localization algorithm for sparse anchor nodes environment*

LIU Hong, ZHANG Zi-yang, WEI Hao-peng

(School of Electrical Engineering and Automation, Jiangxi University of Science and Technology,Ganzhou 341000, China)

Propose a sparse distributed anchor node Monte-Carlo boxed(SDANMCB) localization algorithm,which transfer node with high positioning precision to virtual anchor node to assist other nodes for localization;according to area of sampling box and neighbour anchor node amounts to adjust sample numbers needed for positioning;after filtering,adjust weight of samples according to posterior distribution of sample.Simulation results show this algorithm has obvious improvement in localization precision, sampling efficiency,and in low anchor node density,localization effect has great improvement.

wireless sensor networks(WSNs);anchor node;Monte-Carlo;sampling optimization

10.13873/J.1000—9787(2014)08—0131—03

2014—05—28

國家自然科學(xué)基金資助項(xiàng)目(61163063)

TP 393

A

1000—9787(2014)08—0131—03

劉 宏(1968-),男，江西萍鄉(xiāng)人,教授，碩士生導(dǎo)師,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。