周雪松

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

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

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

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

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

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

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

(1)

從第一個等式開始,每個等式都減去最后一個等式,得到等式:

(2)

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

(3)

(4)

(5)

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

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

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

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

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

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

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

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

第二步:測量和每個鄰居節(jié)點之間的距離,并估計計算誤差

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

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

(6)

然后我們有

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

(7)

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

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

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

(8)

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

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

(9)

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

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

(10)

方差估計σ定義為:

(11)

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

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

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

(12)

將以上公式對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ù)來選擇鄰居節(jié)點對(i,j),以使給需要計算位置的節(jié)點(x,y)帶來最小估計誤差。

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

(17)

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

(18)

并且使用第三個鄰居節(jié)點,來判斷唯一的節(jié)點坐標(biāo)(x,y)。

而這個節(jié)點(x,y)的估計誤差(σx,σy)為:

(19)

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

第四步 利用選擇好的鄰居節(jié)點的位置信息和距離,來計算位置和估計誤差

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

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

圖3 基于RSSI的距離估計

(20)

其中,

(21)

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

圖4 基于兩個相鄰節(jié)點坐標(biāo)的位置計算

圖5 基于第三節(jié)點的距離來識別位置

(22)

3 仿真計算

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

圖6 100個節(jié)點隨機分布在100 m*100 m的區(qū)域中

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

圖7 平均位置誤差

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

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

4 結(jié)束語

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