劉 宏， 張子揚， 魏浩鵬

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

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

劉 宏， 張子揚， 魏浩鵬

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

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

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

0 引 言

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

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

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

1 SDANMCB定位算法介紹

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

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

(1)

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

q=αAanchorbox/iR2,

(2)

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

1.1 采樣階段

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

i=1,2,…,n,

(3)

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

(4)

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

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

(5)

1.2 濾波階段

根據(jù)粒子濾波條件去除無效的樣本點。如式(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é)點的1跳和2跳錨節(jié)點集合，C1，C2為代表節(jié)點的1跳和2跳虛擬錨節(jié)點集合，d(lA,s1)為樣本lA與1跳錨節(jié)點s1之間的距離，d(lA,c1)為樣本點lA與1跳虛擬錨節(jié)點c1之間的距離,d(lA,s2)表示樣本點lA與2跳錨節(jié)點s2之間的距離，d(lA,c2)表示樣本點lA與2跳虛擬錨節(jié)點c2之間的距離。

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

1.3 位置估計

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

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

(7)

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

2 仿真實驗與分析

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

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

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

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

圖5 定位精度隨節(jié)點運動速度變化圖Fig 5 Diagram of change of localization precision with node moving speed

3 結(jié) 論

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

圖6 采樣次數(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)化的蒙特—卡羅移動節(jié)點定位算法[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] 梅 舉, 陳 滌, 辛 玲.基于蒙特—卡洛方法的移動傳感網(wǎng)節(jié)點定位優(yōu)化算法[J].傳感技術(shù)學(xué)報, 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é)基金資助項目(61163063)

TP 393

A

1000—9787(2014)08—0131—03

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