單志龍,黃 恒,項(xiàng) 婉

1(華南師范大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510631)2(華南師范大學(xué) 網(wǎng)絡(luò)教育學(xué)院,廣州 510631)

1 引 言

無(wú)線傳感器網(wǎng)絡(luò)[1]所提供的服務(wù)經(jīng)常需要附加一定的位置信息才有其實(shí)際效用,例如環(huán)境監(jiān)測(cè)[2]中須同時(shí)報(bào)告異常及其發(fā)生的地點(diǎn),才能使異常得到迅速和準(zhǔn)確的處理.目前,雖然GPS定位技術(shù)較為成熟,但成本、功耗和非視距影響等因素限制了其在一些場(chǎng)景中的應(yīng)用,例如在地下室里,GPS信號(hào)會(huì)受到遮蔽干擾等.針對(duì)這些特定的場(chǎng)景,質(zhì)心定位[3]算法、DV-Hop定位[4]算法、APIT定位[5,6]算法等一系列定位算法被提出.

無(wú)線傳感器網(wǎng)絡(luò)定位算法的分類[7]有多種,依據(jù)是否需要測(cè)量距離可分為測(cè)距算法和非測(cè)距算法,依據(jù)定位信息是否需要匯集到一個(gè)中心進(jìn)行處理可分為分布式算法和集中式算法,依據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)是否移動(dòng)可分為動(dòng)態(tài)定位算法和靜態(tài)定位算法.Hu和Evans提出的MCL[8]算法是一種非測(cè)距、分布式和動(dòng)態(tài)的定位算法,該算法為無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)定位提供了新的思路,克服了文獻(xiàn)[3-6]對(duì)網(wǎng)絡(luò)拓?fù)渥兓牟贿m應(yīng)性,能在連續(xù)的節(jié)點(diǎn)移動(dòng)定位過(guò)程中降低能耗、減少累計(jì)誤差和提高位置取得的響應(yīng)速度.

當(dāng)前,國(guó)內(nèi)外學(xué)者對(duì)MCL算法的改進(jìn)主要集中在以下幾個(gè)方面:如何預(yù)測(cè)節(jié)點(diǎn)下一時(shí)刻的速度、如何縮小采樣區(qū)域以及如何減小累積誤差.針對(duì)節(jié)點(diǎn)運(yùn)動(dòng)預(yù)測(cè),利用插值法[9,10]、最小二乘曲線擬合[11]、航位推測(cè)[12]、灰度預(yù)測(cè)[13]、小波變換預(yù)測(cè)[14]等,對(duì)節(jié)點(diǎn)下一時(shí)刻的速度和方向進(jìn)行預(yù)測(cè),提高采樣效率.針對(duì)縮小采樣區(qū)域,主要的方法有構(gòu)建錨盒和采樣盒[15,16]以提高采樣成功率,提出負(fù)約束概念[17]排除非鄰居錨節(jié)點(diǎn)通信范圍內(nèi)的采樣區(qū)域,構(gòu)建RSSI測(cè)距模型[18]限制采樣區(qū)域,結(jié)合APIT算法[19]縮小采樣區(qū)域等.針對(duì)累積誤差修正,采用基于爬山策略的混合粒子群優(yōu)化算法[20]減小定位整體誤差.

但是,大部分學(xué)者對(duì)MCL算法在障礙物較多的定位場(chǎng)景中的適應(yīng)性研究較少.針對(duì)這一問(wèn)題,本文把障礙物抽象成節(jié)點(diǎn),構(gòu)建數(shù)學(xué)模型模擬障礙物對(duì)錨節(jié)點(diǎn)信號(hào)遮蔽的影響,通過(guò)對(duì)節(jié)點(diǎn)待定位前后錨節(jié)點(diǎn)信息的對(duì)比和兩者位移關(guān)系的限定,恢復(fù)被遮蔽干擾信號(hào)的錨節(jié)點(diǎn)對(duì)樣本濾波的作用,以此提高M(jìn)CL算法在障礙物環(huán)境中的定位精度.

2 MCL算法分析

MCL算法的核心在于通過(guò)重要性采樣的迭代更新,利用離散的加權(quán)樣本去估計(jì)節(jié)點(diǎn)位置的后驗(yàn)概率密度分布.算法主要步驟包括預(yù)測(cè)階段和樣本過(guò)濾階段,具體定位流程如下:

1.初始化采樣.待定位節(jié)點(diǎn)在算法初始化時(shí)沒(méi)有位置的歷史數(shù)據(jù),只能在節(jié)點(diǎn)部署平面內(nèi)隨機(jī)采集N個(gè)樣本.初始化后,算法重復(fù)預(yù)測(cè)和樣本過(guò)濾步驟.

2.預(yù)測(cè)階段.以待定位節(jié)點(diǎn)t-1時(shí)刻的有效樣本為圓心,vmax為半徑作圓,在圓內(nèi)采集樣本,預(yù)測(cè)其在t時(shí)刻的位置.

3.樣本過(guò)濾階段.以待定位節(jié)點(diǎn)在t時(shí)刻觀察到的錨節(jié)點(diǎn)信息為條件,濾除不滿足條件的采集樣本.

4.重采樣和位置計(jì)算.采集的樣本被過(guò)濾后,如果數(shù)目不滿足預(yù)設(shè)的值,進(jìn)行重采樣.否則取樣本集的質(zhì)心為未知節(jié)點(diǎn)的估計(jì)位置.

MCL算法及其大多數(shù)改進(jìn)算法均未考慮障礙物的影響,而現(xiàn)實(shí)場(chǎng)景中障礙物的出現(xiàn)會(huì)引起信號(hào)的衰減,進(jìn)而降低算法的定位精度,因此有必要研究如何檢測(cè)障礙物并有效降低障礙物對(duì)定位的影響.

3 障礙物對(duì)錨節(jié)點(diǎn)信號(hào)遮蔽的數(shù)學(xué)建模

為便于理解障礙物對(duì)錨節(jié)點(diǎn)信號(hào)傳播的影響,同時(shí)構(gòu)建算法的仿真環(huán)境,本節(jié)就障礙物對(duì)錨節(jié)點(diǎn)信號(hào)的影響進(jìn)行建模.

將無(wú)線傳感器網(wǎng)絡(luò)中的障礙物抽象成與錨節(jié)點(diǎn)s和待定位節(jié)點(diǎn)p一樣的節(jié)點(diǎn)b,b∈B,B為障礙物集合.取b影響范圍參數(shù)為W,記錨節(jié)點(diǎn)s與待定位節(jié)點(diǎn)p的歐幾里得距離為L(zhǎng),φ為高斯噪聲,以W+φ為寬和L+φ為長(zhǎng)構(gòu)成一個(gè)矩形區(qū)域,如圖1所示,只要b進(jìn)入該矩形區(qū)域,則s成為p無(wú)法檢測(cè)到信號(hào)的盲節(jié)點(diǎn).

圖1 障礙物影響區(qū)域Fig.1 Area affected by obstacles

記錨節(jié)點(diǎn)s的坐標(biāo)為(xs,ys)、待定位節(jié)點(diǎn)p的坐標(biāo)為(xp,yp)、障礙物節(jié)點(diǎn)b的坐標(biāo)為(xb,yb),s與p的質(zhì)心c的坐標(biāo)為(xc,yc).設(shè)s與p確定的直線為l.

1)l與x軸垂直.障礙物影響區(qū)域?yàn)橹本€(1)所圍成的矩形區(qū)域,如圖1(a)所示.滿足(2)式,則對(duì)于p,s的信號(hào)被遮蔽.

(1)

?b∈B,|xb-xc|≤(W+φ)/2∧|yb-yc|≤(L+φ)/2

(2)

2)l與y軸垂直.障礙物影響區(qū)域?yàn)橹本€(3)所圍成的矩形區(qū)域,如圖1(b)所示.滿足(4)式,則對(duì)于p,s的信號(hào)被遮蔽.

(3)

?b∈B,|xb-xc|≤(L+φ)/2∧|yb-yc|≤(W+φ)/2

(4)

(5)

(6)

(7)

障礙物影響區(qū)域?yàn)橹本€(7)所圍成的矩形區(qū)域,如圖1(c)所示.滿足(8)式,則對(duì)于p,s的信號(hào)被遮蔽.

(8)

4 BDMCL算法

在無(wú)線傳感器網(wǎng)絡(luò)中,記節(jié)點(diǎn)的最大運(yùn)動(dòng)速度為vmax,節(jié)點(diǎn)接收信號(hào)的半徑為R,若節(jié)點(diǎn)在移動(dòng)時(shí)不考慮信息的收發(fā)延遲,則BDMCL算法的定位流程如下:

4.1 初始化采樣

4.2 預(yù)測(cè)采樣

(9)

4.3 找出盲節(jié)點(diǎn)

若p在以s為圓心R為半徑的圓內(nèi),則稱s為p的一跳錨節(jié)點(diǎn);若p在以s為圓心R到2R之間的圓環(huán)內(nèi),則稱s為p的二跳錨節(jié)點(diǎn).

圖2 錨節(jié)點(diǎn)與待定位節(jié)點(diǎn)的位移關(guān)系Fig.2 Displacement relation between anchor and node

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

4)此外一個(gè)錨節(jié)點(diǎn)從pt-1的通信范圍外變成pt的一跳或二跳錨節(jié)點(diǎn),由于pt沒(méi)有其歷史信息,即使是被遮蔽了信號(hào)后被檢測(cè)出來(lái)也沒(méi)有充當(dāng)指紋的作用.而錨節(jié)點(diǎn)從pt-1的一跳錨節(jié)點(diǎn)通信范圍移動(dòng)到pt的2R范圍外,則由(17)式所排除,且其無(wú)法對(duì)pt的預(yù)測(cè)樣本起到有效的正約束作用.

4.4 樣本過(guò)濾

(18)

4.5 位置計(jì)算

5 仿真分析

本文利用MATLAB平臺(tái),通過(guò)障礙物對(duì)錨節(jié)點(diǎn)信號(hào)遮蔽的數(shù)學(xué)模型構(gòu)建算法運(yùn)行的場(chǎng)景,對(duì)BDMCL算法進(jìn)行仿真實(shí)驗(yàn).待定位節(jié)點(diǎn)和錨節(jié)點(diǎn)移動(dòng)模型為模擬運(yùn)動(dòng)軌跡更為平滑的Markov Waypoint Mobility Model[21],障礙物移動(dòng)模型為模擬運(yùn)動(dòng)軌跡更為隨機(jī)的Random Waypoint Mobility Model[21].若無(wú)特別說(shuō)明,節(jié)點(diǎn)與障礙物均隨機(jī)部署且自由運(yùn)動(dòng).仿真實(shí)驗(yàn)的默認(rèn)參數(shù)設(shè)置見(jiàn)表1.

表1 仿真實(shí)驗(yàn)?zāi)J(rèn)參數(shù)
Table 1 Default parameters of simulation

參 數(shù)實(shí)驗(yàn)?zāi)J(rèn)取值節(jié)點(diǎn)部署區(qū)域大小Xrang×Yrang=500×500待定位節(jié)點(diǎn)數(shù)cn=200錨節(jié)點(diǎn)數(shù)sn=200障礙物節(jié)點(diǎn)數(shù)bn=200節(jié)點(diǎn)無(wú)線電傳播半徑R=50障礙物影響寬度W=5節(jié)點(diǎn)最大運(yùn)動(dòng)速度vmax=20有效樣本集樣本總數(shù)N=50定位周期step=20

仿真實(shí)驗(yàn)中每個(gè)待定位節(jié)點(diǎn)取20個(gè)連續(xù)的定位周期的均值作為仿真實(shí)驗(yàn)結(jié)果,記待定位節(jié)點(diǎn)的估計(jì)位置坐標(biāo)為p(x,y),其真實(shí)位置坐標(biāo)為p0(x0,y0),節(jié)點(diǎn)的位置坐標(biāo)誤差e的計(jì)算如式(19),e越小表明算法對(duì)節(jié)點(diǎn)位置坐標(biāo)的估計(jì)越準(zhǔn)確.

(19)

文獻(xiàn)[9]提出的MCL改進(jìn)算法IMCL(Improved MCL)是利用牛頓插值多項(xiàng)式對(duì)待定位節(jié)點(diǎn)的運(yùn)動(dòng)速度和方向作預(yù)測(cè),以提高M(jìn)CL算法采樣的針對(duì)性.為驗(yàn)證新算法性能,本文對(duì)MCL、IMCL和BDMCL三個(gè)算法的定位周期、障礙物數(shù)目、節(jié)點(diǎn)運(yùn)動(dòng)速率和定位耗時(shí)的影響進(jìn)行仿真實(shí)驗(yàn).

1)定位周期

在20個(gè)定位周期中,待定位節(jié)點(diǎn)會(huì)出現(xiàn)收不到錨節(jié)點(diǎn)信號(hào)或采樣失敗的情況,從而造成節(jié)點(diǎn)定位誤差的增加.BDMCL算法能對(duì)盲節(jié)點(diǎn)信號(hào)進(jìn)行恢復(fù),使得無(wú)錨節(jié)點(diǎn)信號(hào)次數(shù)與采樣失敗次數(shù)的均值較低.如圖3所示,BDMCL無(wú)錨節(jié)點(diǎn)信號(hào)平均次數(shù)比MCL低44.50%,比IMCL低30.50%;采樣失敗平均次數(shù)比MCL低19.00%,比IMCL低4.50%.

由于BDMCL在障礙物環(huán)境的定位場(chǎng)景中利用盲節(jié)點(diǎn)信息加強(qiáng)了對(duì)預(yù)測(cè)樣本的過(guò)濾作用,因而能夠提高定位精度,如圖4所示.在一個(gè)高度動(dòng)態(tài)的定位場(chǎng)景中,由于待定位節(jié)點(diǎn)第一步無(wú)法依托歷史信息,三種算法定位誤差以及定位耗時(shí)均比較大,到了第二步,定位誤差與定位耗時(shí)迅速收斂趨穩(wěn).經(jīng)計(jì)算BDMCL比MCL誤差平均低8.26%,比IMCL低10.10%.

2)障礙物數(shù)目

自由移動(dòng)的障礙物數(shù)目發(fā)生變化時(shí)對(duì)定位誤差也會(huì)產(chǎn)生一定的影響.如圖5所示,障礙物數(shù)目的增加對(duì)定位耗時(shí)的影響較小,但障礙物的隨機(jī)運(yùn)動(dòng)對(duì)BDMCL的影響較小,其平均定位誤差比MCL低6.15%,比IMCL低16.69%.由于障礙物對(duì)定位精度的影響較為隨機(jī),BDMCL并未全線比MCL算法誤差低,但誤差最多僅高0.05R,誤差的方差為0.0013,比MCL的0.0113和IMCL的0.007低.

3)節(jié)點(diǎn)運(yùn)動(dòng)速率

節(jié)點(diǎn)運(yùn)動(dòng)速率增大,待定位節(jié)點(diǎn)和錨節(jié)點(diǎn)指紋的相對(duì)位移關(guān)系變得不穩(wěn)定,造成錨節(jié)點(diǎn)指紋與當(dāng)前錨節(jié)點(diǎn)信息沖突,導(dǎo)致采樣失敗,造成定位誤差的增大.如圖6所示,BDMCL平均定位誤差比MCL低10.64%,比IMCL低10.31%.

圖3 待定位節(jié)點(diǎn)無(wú)錨節(jié)點(diǎn)信號(hào)與采樣失敗平均次數(shù)Fig.3 Average times of noSignal and noSample

圖4 定位周期與定位誤差的關(guān)系Fig.4 Relationship between positioning period and positioning accuracy

圖5 障礙物數(shù)目與定位誤差的關(guān)系Fig.5 Relationship between the obstacles and positioning accuracy

圖6 節(jié)點(diǎn)運(yùn)動(dòng)速率與定位誤差的關(guān)系Fig.6 Relationship between the velocity and positioning accuracy

4)定位耗時(shí)

BDMCL算法的采樣方式與MCL算法一致,因此其定位耗時(shí)與MCL算法基本持平.而IMCL算法沒(méi)有利用上一時(shí)刻的有效樣本進(jìn)行預(yù)測(cè)采樣,牛頓插值多項(xiàng)式的預(yù)測(cè)在vmax較大時(shí)誤差較大,導(dǎo)致采樣耗時(shí)較大.如圖7所示,BDMCL定位耗時(shí)比MCL高0.70%,比IMCL低44.70%.IMCL算法不適應(yīng)于高度動(dòng)態(tài)的定位場(chǎng)景.

5)障礙物固定且均勻分布

障礙物隨機(jī)部署和移動(dòng)時(shí),BDMCL算法具有較好的性能表現(xiàn).為分析障礙物均勻固定分布時(shí),BDMCL算法是否依然能取得優(yōu)勢(shì),本文也對(duì)障礙物固定且均勻分布的場(chǎng)景進(jìn)行了實(shí)驗(yàn).結(jié)果顯示,BDMCL算法依然能有效利用盲節(jié)點(diǎn)的信息,取得比其余兩種算法更好的定位精度.如圖8所示,BDMCL定位誤差平均比MCL低17.60%,比IMCL低14.91%.由于障礙物固定且均勻分布,減少了隨機(jī)部署和移動(dòng)的干擾,因此固定部署時(shí),BDMCL定位誤差比隨機(jī)部署更低.

6 結(jié) 論

MCL算法是適用于無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)定位算法,該文討論了MCL算法在障礙物環(huán)境中的一種適應(yīng)性解決方案.通過(guò)構(gòu)建數(shù)學(xué)模型模擬障礙物對(duì)錨節(jié)點(diǎn)信號(hào)遮蔽干擾的影響,提出以待定位節(jié)點(diǎn)前后錨節(jié)點(diǎn)信息的對(duì)比和兩者位移關(guān)系的限定的方法,恢復(fù)被遮蔽干擾信號(hào)的錨節(jié)點(diǎn)對(duì)其樣本濾波的作用,以此提高M(jìn)CL算法在障礙物環(huán)境中的定位精度.通過(guò)實(shí)驗(yàn)仿真對(duì)比,該文提出的BDMCL算法在障礙物較多的場(chǎng)景中能以較小的時(shí)間代價(jià)取得更好的定位精度.