基于最小傳播誤差的室內(nèi)定位方法研究

周雪松

(江蘇自動(dòng)化研究所,江蘇 連云港 222061)

目前,位置感知已經(jīng)成為許多無(wú)線(xiàn)網(wǎng)絡(luò)應(yīng)用的一個(gè)重要特征,包括位置跟蹤、映射、定位路由、覆蓋管理、協(xié)同信號(hào)處理等[1-2]。例如,基于位置的路由協(xié)議,路由和數(shù)據(jù)轉(zhuǎn)發(fā)都是基于地理位置的。如果節(jié)點(diǎn)的位置能夠更精確地定位,網(wǎng)絡(luò)的數(shù)據(jù)傳輸將會(huì)更加有效。

然而,由于成本和能量限制,并非所有節(jié)點(diǎn)都可能具有可靠的位置信息源，例如GPS接收器。需要與衛(wèi)星時(shí)鐘精確同步的每個(gè)節(jié)點(diǎn)的GPS解決方案都不適合大規(guī)模無(wú)線(xiàn)網(wǎng)絡(luò)[3]。 因此,位置系統(tǒng)通常通過(guò)全球定位系統(tǒng)(GPS)或人工布局將一些信息分布到網(wǎng)絡(luò)中的其他地方,然后通過(guò)計(jì)算節(jié)點(diǎn)的陽(yáng)極位置來(lái)計(jì)算其通信范圍,并在鄰域有足夠的錨節(jié)點(diǎn)[4]。

在大多數(shù)情況下,領(lǐng)域沒(méi)有足夠的錨節(jié)點(diǎn)。當(dāng)錨節(jié)點(diǎn)數(shù)量較少時(shí),例如平均少于三個(gè)通信范圍內(nèi)的錨節(jié)點(diǎn)時(shí),傳統(tǒng)方法無(wú)法正常工作[5-6]。在實(shí)際應(yīng)用中,由于項(xiàng)目成本,可用于支持室內(nèi)定位的節(jié)點(diǎn)數(shù)量并不多。因此,當(dāng)少量錨節(jié)點(diǎn)存在時(shí),需要一種室內(nèi)定位方法。本文提供了一種新的位置方法來(lái)估計(jì)位置,通過(guò)選擇最小估計(jì)誤差傳播的有用鄰居(錨節(jié)點(diǎn)和正規(guī)節(jié)點(diǎn))?？紤]到這些節(jié)點(diǎn)的移動(dòng)性,算法可以動(dòng)態(tài)地利用節(jié)點(diǎn)記錄的信息,而不需要過(guò)度交換數(shù)據(jù)或算法信息。根據(jù)所選擇的位置和來(lái)自鄰居的誤差估計(jì)信息,新到達(dá)節(jié)點(diǎn)可以計(jì)算自己的位置和誤差估計(jì)信息并將其廣播到具有較少錨節(jié)點(diǎn)的鄰域。

1 傳統(tǒng)最大似然估計(jì)方法

當(dāng)通信范圍內(nèi)的錨節(jié)點(diǎn)的數(shù)量大于2時(shí),可以使用最大似然估計(jì)(MLE)的方法來(lái)估計(jì)該未知節(jié)點(diǎn)的位置。 具體程序如下。

假設(shè)有n(n>2)個(gè)錨節(jié)點(diǎn),坐標(biāo)依次為(x1,y1),(x2,y2),…(xn,yn), 它們到未知節(jié)點(diǎn)P(x,y)的距離是d1,d2,…dn,于是,我們有等式:

(1)

從第一個(gè)等式開(kāi)始,每個(gè)等式都減去最后一個(gè)等式,得到等式:

(2)

可以使用矩陣表達(dá)式AX=b表示,其中:

(3)

(4)

(5)

當(dāng)n=3時(shí),定位常用的另外一種方法是最大似然估計(jì)的三邊法。

另一種常見(jiàn)的方法是n=3的MLE例子。然而,在最大似然估計(jì)方法僅僅當(dāng)錨節(jié)點(diǎn)數(shù)量小于3時(shí)才能夠工作。當(dāng)錨節(jié)點(diǎn)的數(shù)量不足或分布不均勻時(shí),傳統(tǒng)的最大似然估計(jì)法無(wú)法工作。

2 基于誤差估計(jì)的最小化誤差傳播定位方法

本文提出一種新的定位方法,它通過(guò)選擇有用的鄰節(jié)點(diǎn)并以最小誤差的原則來(lái)估算位置。依據(jù)本文的一個(gè)實(shí)例,提供一種定位算法,包括收集每個(gè)鄰居節(jié)點(diǎn)的位置信息;測(cè)量待定位節(jié)點(diǎn)和每個(gè)鄰居節(jié)點(diǎn)之間的距離,并估計(jì)誤差;根據(jù)鄰居節(jié)點(diǎn)的位置信息,選擇具有最小傳播估計(jì)誤差的節(jié)點(diǎn);利用選擇好的鄰居節(jié)點(diǎn)的位置和距離,來(lái)計(jì)算位置并估計(jì)誤差。本文提出了當(dāng)已知的錨節(jié)點(diǎn)數(shù)量受限時(shí)的一種定位新方法。新節(jié)點(diǎn)將根據(jù)它和鄰居節(jié)點(diǎn)的傳播誤差最小原理,來(lái)計(jì)算它位置。

圖1 基于傳播誤差最小原理的錨節(jié)點(diǎn)數(shù)量受限時(shí)的定位流程圖

第一步:收集每個(gè)鄰居節(jié)點(diǎn)的位置信息

開(kāi)始的時(shí)候,該節(jié)點(diǎn)發(fā)送MEPLE定位請(qǐng)求,相鄰節(jié)點(diǎn)將返回它們的位置信息(如圖2所示)。此位置信息包括:估計(jì)的位置坐標(biāo)(x,y)和這些坐標(biāo)的估計(jì)誤差(σx,σy)。這里,對(duì)于每個(gè)錨節(jié)點(diǎn)來(lái)說(shuō),坐標(biāo)估計(jì)誤差為零。而對(duì)于尚未執(zhí)行MEPLE計(jì)算的節(jié)點(diǎn),位置信息被設(shè)置為NULL。

圖2 從鄰居節(jié)點(diǎn)收集位置信息

第二步:測(cè)量和每個(gè)鄰居節(jié)點(diǎn)之間的距離,并估計(jì)計(jì)算誤差

許多測(cè)量距離的技術(shù)已經(jīng)被提出,如到來(lái)角(AOA)方法,到達(dá)時(shí)間方法(TOA),到達(dá)時(shí)間差方法(TDOA)和接收信號(hào)強(qiáng)度方法(RSSI)等技術(shù)。這里,我們?nèi)SSI方法作為例子來(lái)說(shuō)明該步驟。首先,節(jié)點(diǎn)將測(cè)量每個(gè)鄰居節(jié)點(diǎn)k的RSSI值RSSIk;然后,該節(jié)點(diǎn)使用距離和功率之間的映射公式來(lái)計(jì)算估計(jì)距離。

Pr(dBm)=A-10·n·lgr

(6)

然后我們有

d=ρ(RSSIk)=10(A-RSSIk)/(10·n)

(7)

其中A是在1米距離時(shí)收到信號(hào)強(qiáng)度,d是距離發(fā)送者的長(zhǎng)度,n為信號(hào)傳播常量,也叫傳播指數(shù)。同時(shí),這里有一個(gè)距離d的估計(jì)誤差,假設(shè)它的測(cè)量誤差為σ(RSSIk),我們就可以由統(tǒng)計(jì)信息得到這個(gè)值。

第三步:從鄰居節(jié)點(diǎn)的位置信息中,選擇具有最小傳播估計(jì)誤差的節(jié)點(diǎn)

當(dāng)收集并計(jì)算來(lái)自鄰居節(jié)點(diǎn)的位置信息(x,y,d,σx,σy,σd)后,在所有的鄰居節(jié)點(diǎn)中,選擇一個(gè)具有最小估計(jì)傳播誤差的鄰居節(jié)點(diǎn)對(duì)Pair(i,j)。具體而言,我們選擇的鄰居節(jié)點(diǎn)對(duì)滿(mǎn)足:

(8)

其中Γ函數(shù)定義為:

Γ(xi,yi,di,σxi,σyi,σdi,xj,yj,dj,σxj,σyj,σdj)=σ2=

(9)

函數(shù)Γ的具體計(jì)算和理論分析如下:

位置估計(jì)誤差(σx,σy)可以通過(guò)如下計(jì)算:

(10)

方差估計(jì)σ定義為:

(11)

從方程中,我們可以看到,定位的估計(jì)誤差(σx,σy)來(lái)自三部分組成,具體到一個(gè)鄰居節(jié)點(diǎn)i(xi,yi,di):

現(xiàn)在,我們將解釋如何計(jì)算這些影響因素:

我們有兩個(gè)鄰居的定位信息,那就是:

(12)

將以上公式對(duì)x進(jìn)行偏微分,我們可以得到:

(13)

求解該方程,我們可以得到:

(14)

用同樣的方法,取y和d的偏微分方程,分別可得:

(15)

(16)

現(xiàn)在,我們給出函數(shù)Γ(xi,yi,di,σxi,σyi,σdi,xj,yj,dj,σxj,σyj,σdj)的定義。并利用此函數(shù)來(lái)選擇鄰居節(jié)點(diǎn)對(duì)(i,j),以使給需要計(jì)算位置的節(jié)點(diǎn)(x,y)帶來(lái)最小估計(jì)誤差。

Γ(xi,yi,di,σxi,σyi,σdi,xj,yj,dj,σxj,σyj,σdj)=σ2=

(17)

最后,我們使用選定的鄰居節(jié)點(diǎn)對(duì)(xi,yi,di)和(xj,yj,dj)作為數(shù)據(jù)源,來(lái)計(jì)算方程組:

(18)

并且使用第三個(gè)鄰居節(jié)點(diǎn),來(lái)判斷唯一的節(jié)點(diǎn)坐標(biāo)(x,y)。

而這個(gè)節(jié)點(diǎn)(x,y)的估計(jì)誤差(σx,σy)為:

(19)

因此,新節(jié)點(diǎn)的位置信息是x,y,σx,σy。

第四步 利用選擇好的鄰居節(jié)點(diǎn)的位置信息和距離,來(lái)計(jì)算位置和估計(jì)誤差

在第三步中,我們已經(jīng)選擇好鄰居節(jié)點(diǎn)對(duì)Pair(i,j)。使用此節(jié)點(diǎn)序列對(duì)的定位信息,可以計(jì)算出一個(gè)新節(jié)點(diǎn)的估計(jì)位置和估計(jì)誤差。

我們?nèi)匀辉谶@里使用的RSSI距離測(cè)量方法，如圖3所示。

圖3 基于RSSI的距離估計(jì)

(20)

其中,

(21)

解方程，我們可以得到兩個(gè)對(duì)稱(chēng)的節(jié)點(diǎn)的位置，如圖4所示。使用第三鄰居節(jié)點(diǎn)的距離信息，我們可以識(shí)別，如圖5所示，其中一個(gè)是真正的節(jié)點(diǎn)位置，簡(jiǎn)單表示為:

圖4 基于兩個(gè)相鄰節(jié)點(diǎn)坐標(biāo)的位置計(jì)算

圖5 基于第三節(jié)點(diǎn)的距離來(lái)識(shí)別位置

(22)

3 仿真計(jì)算

本節(jié)給出一些性能評(píng)估,以比較提出的MEPLE解決方案與傳統(tǒng)的MLE方法。仿真在100個(gè)獨(dú)立隨機(jī)生成的圖上運(yùn)行,如圖6所示。

圖6 100個(gè)節(jié)點(diǎn)隨機(jī)分布在100 m*100 m的區(qū)域中

圖7說(shuō)明了現(xiàn)有MLE方法和MEPLE方法中常規(guī)節(jié)點(diǎn)的平均位置誤差(以米為單位)。據(jù)觀(guān)察,估計(jì)誤差與錨節(jié)點(diǎn)的數(shù)量成反比增長(zhǎng)。 當(dāng)錨節(jié)點(diǎn)數(shù)量較少時(shí),如10～20之間時(shí),MEPLE的性能優(yōu)于MLE,平均估計(jì)誤差減少50～80%,平均估計(jì)誤差小于5 m。 隨著錨節(jié)點(diǎn)數(shù)量增加到30個(gè)以上,MLE算法可以與所提出的MEPLE算法密切相關(guān)。 這是因?yàn)樵趥鬏敺秶鷥?nèi),將會(huì)有更多的附近錨節(jié)點(diǎn)可用于MLE計(jì)算。 在大多數(shù)情況下,這些錨節(jié)點(diǎn)與MEPLE方法選擇的節(jié)點(diǎn)相同,因此性能差異很小。

圖7 平均位置誤差

每個(gè)常規(guī)節(jié)點(diǎn)的位置估計(jì)誤差的累積分布函數(shù)(CDF)曲線(xiàn)如圖8所示。這里,總節(jié)點(diǎn)的10%被設(shè)置為錨節(jié)點(diǎn)。從圖中可以看出,采用MEPLE方法,對(duì)于80%以上的用戶(hù),位置估計(jì)誤差小于5 m; 而對(duì)于MLE,只有60%的用戶(hù)估算誤差低于5 m。 對(duì)于MEPLE,最大估計(jì)誤差為22 m,只有4%的用戶(hù)誤差超過(guò)10 m; 對(duì)于MLE,20%的用戶(hù)誤差超過(guò)10 m,大約10%的用戶(hù)由于附近缺乏錨節(jié)點(diǎn)而無(wú)法計(jì)算其位置。

圖8 累積分布函數(shù)(CDF)定位估計(jì)誤差

4 結(jié)束語(yǔ)

為了估計(jì)未知節(jié)點(diǎn)的位置,本文描述了MLE的當(dāng)前方法。提出了一種利用MEPLE選擇有價(jià)值鄰居(錨節(jié)點(diǎn)和規(guī)則節(jié)點(diǎn))估計(jì)位置的新方法。 根據(jù)仿真結(jié)果,MEPLE總體上優(yōu)于MLE,尤其是當(dāng)錨節(jié)點(diǎn)數(shù)量較少(如10到20)時(shí),MEPLE平均可以減少50-80%的估計(jì)誤差。 未來(lái)的工作將會(huì)采用MEPLE實(shí)驗(yàn)方法進(jìn)行研究。