具有穩(wěn)健性的無線傳感器網(wǎng)絡(luò)定位算法

宋 偉，樊孝明，王 玫

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林541004)

位置信息往往是許多無線傳感器網(wǎng)絡(luò)應(yīng)用的前提［1］。近年來，超寬帶(UWB)、chirp線性調(diào)頻(CCS)技術(shù)廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)的定位，IEEE 802.15.4a就規(guī)定了這兩種信號(hào)作為物理層［2］，利用信號(hào)的波達(dá)時(shí)間來測量信標(biāo)節(jié)點(diǎn)與位置節(jié)點(diǎn)之間的距離。在測距精度、抗多徑干擾上都有很好的表現(xiàn)。但是非視距(NLOS)誤差還是一個(gè)影響定位精度的主要問題，關(guān)于非視距誤差，Venkatesh和Buehrer提出了一種基于線性優(yōu)化的算法，此算法的假設(shè)條件是對(duì)測距值中是否包含非視距誤差已經(jīng)做出了鑒別，這在實(shí)際應(yīng)用中往往難以實(shí)現(xiàn)［3］。因?yàn)殛P(guān)于非視距的鑒別，通常是通過大量的統(tǒng)計(jì)實(shí)現(xiàn)的，Wylie就基于包含非視距誤差的測距值比不包含的測距值的標(biāo)準(zhǔn)差大，提出將實(shí)測的測距值的標(biāo)準(zhǔn)差與視距環(huán)境時(shí)的標(biāo)準(zhǔn)差進(jìn)行比較，在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)通常體積、電池能量都很有限，進(jìn)行多次測量求標(biāo)準(zhǔn)差，勢(shì)必消耗大量的能量［4］。CHEN提出一種殘差加權(quán)算法，通過不同的組合分別求出目標(biāo)節(jié)點(diǎn)的位置，再根據(jù)與測距值的殘差來進(jìn)行加權(quán)，對(duì)非視距誤差有一定的抑制作用，缺點(diǎn)是計(jì)算量太大，在能量有限的無線傳感器網(wǎng)絡(luò)中同樣不適用［5］。

本文基于最小一乘法思想，提出一種組合中位最小二乘定位(Combination Median Least Squares)算法，在少數(shù)未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間出現(xiàn)非視距誤差時(shí)，有很好的抑制作用。

1 傳統(tǒng)定位算法

傳統(tǒng)的基于距離的定位算法一般采用極大似然估計(jì)法(Maximum Likelihood Estimation)［3］，如圖1，已知1，2，3等n個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(x1，y1)，(x2，y2)，(x3，y3)，…，(xn，yn)，它們到節(jié)點(diǎn)D的距離分別為d1，d2，d3，…，dn，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x，y)，那么存在

圖1 極大似然估計(jì)法示意圖

這是一個(gè)非線性方程組，把x2+y2作為一個(gè)未知項(xiàng)，方程組可以化為一個(gè)線性方程，此線性方程表示式為AX=B，其中v=x2+y2，且

此線性方程一般用線性最小二乘法，有確定的解的形式

測距值的表達(dá)式

式中:di為測量距離值;dit為真實(shí)距離值;ei為測距誤差，通?？梢哉J(rèn)為是標(biāo)準(zhǔn)差很小，均值為0的正態(tài)分布;ni為非視距誤差，通?？梢哉J(rèn)為是服從具有正均值和較大方差的正態(tài)分布［6］?？梢姡且暰嗾`差是影響定位精度的主要因素。

2 最小二乘法與最小一乘法比較

最小二乘法產(chǎn)生于1795年，18歲的高斯應(yīng)用最小二乘法準(zhǔn)確地預(yù)測了神谷星(Ceres)的運(yùn)行軌道［7］。最小二乘最簡單的解釋方式就是算數(shù)平均，設(shè)要對(duì)一個(gè)未知量α做估計(jì)，觀察了n次，結(jié)果分別是x1，x2，x3，x4，…，xn，估計(jì)真值為b，設(shè)殘差

這導(dǎo)致了以下做法，即設(shè)

找出b，使L(b)得最小值，利用求導(dǎo)取最小值

求出的即為測量值的算數(shù)平均值。

最小二乘法在數(shù)據(jù)不存在異常值的情況下有很好的效果，但最小二乘法對(duì)超出量很敏感［8］。如果有一種方法對(duì)超出量不敏感，即說這種方法具有穩(wěn)健性。于此相對(duì)，波斯維奇在1760年提出了最小一乘法，他在測量子午線的時(shí)候，提出了最小一乘準(zhǔn)則。與最小二乘準(zhǔn)則不同，最小一乘準(zhǔn)則是使殘差的絕對(duì)值的和最小即

式(10)取最小值，在一維的情況下便是測量值的中位數(shù)med［9］。

舉個(gè)簡單的例子，比如要求一只籃球隊(duì)的平均年齡，假設(shè)分別為(20，21，22，25，30，31，19)，如果按照最小二乘準(zhǔn)則，平均年齡為27，根據(jù)最小一乘準(zhǔn)則，得出中位數(shù)22，但如果出現(xiàn)了超量值，比如說球隊(duì)中有兩個(gè)教練，年齡為60與65，根據(jù)最小二乘準(zhǔn)則，平均年齡為32，根據(jù)最小一乘準(zhǔn)則，得出中位數(shù)為25，明顯，這個(gè)值更符合人們對(duì)這只球隊(duì)年齡的認(rèn)識(shí)。有人做過實(shí)驗(yàn)，大量測量數(shù)據(jù)用最小二乘法與最小一乘法分別擬合一條直線，最小一乘法更加符合人眼的直觀印象。所以說，最小一乘法有更好的穩(wěn)健性。最小一乘法比最小二乘法誕生更早，但由于計(jì)算上的問題無法得以解決，所以直到1950年提出了線性規(guī)劃的方式求解以及電子計(jì)算機(jī)的出現(xiàn)，才一定程度上解決了最小一乘法的計(jì)算問題。

3 算法與仿真

3.1 算法描述

根據(jù)最小一乘法對(duì)超量誤差的抑制以及計(jì)算上的困難，提出一種組合中位最小二乘(Combination Median Least Squars)算法，仿真證明，在有少量非視距誤差存在的情況下，對(duì)非視距誤差有顯著的抑制效果。CMLS算法有以下步驟:

1)如果有m個(gè)信標(biāo)節(jié)點(diǎn)，1個(gè)未知節(jié)點(diǎn)，進(jìn)行定位最少需要3個(gè)信標(biāo)節(jié)點(diǎn)，所以m個(gè)節(jié)點(diǎn)就有種組合，設(shè)=k。

2)每一種組合用線性最小二乘法計(jì)算出一個(gè)坐標(biāo)值，k組定位結(jié)果為(x1，y1)，(x2，y2)，(x3，y3)，…，(xk，yk)。

3)再用最小一乘法分別求出橫坐標(biāo)與縱坐標(biāo)的中位數(shù)。對(duì)x1，x2，x3，…，xk與y1，y2，y3，…，yk分別進(jìn)行最小一乘法，即找出了x1，x2，x3，…，xk與y1，y2，y3，…，yk的中位數(shù)。

這樣就把一些包含非視距誤差的組合所定出的點(diǎn)排除在外。根據(jù)中位數(shù)可知，只要有超量誤差的數(shù)量不超過總量的一半，最后的取值一定還是在沒受到超量誤差影響的值中，所以不會(huì)影響到所得的結(jié)果。

3.2 實(shí)驗(yàn)仿真

為體現(xiàn)CMLS算法的效果，將本文算法與CHEN提出的RWGH［5］算法以及傳統(tǒng)的LS算法進(jìn)行比較。因?yàn)樗惴ǖ男Ч粌H與測量噪聲與非視距誤差有過，還與節(jié)點(diǎn)的分布有關(guān)，所以設(shè)在50 m×50 m的區(qū)域平均分布生7個(gè)點(diǎn)，(21.34，25)，(30，20)，(38.66，25)，(38.66，35)，(30，40)，(21.34，35)，(30，30)，其中(30，30)是未知節(jié)點(diǎn)的真實(shí)位置，其余為信標(biāo)節(jié)點(diǎn)。未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的真實(shí)距離為d1t=d2t=d3t=d4t=d5t=d6t=10 m。根據(jù)式(6)，設(shè)測距誤差滿足ei～N(0，0.52)，定位精度用均方根誤差(RMSE)來評(píng)價(jià)

針對(duì)固定長度的NLOS誤差來仿真，做1 000次仿真求RMSE，設(shè)d3中有非視距誤差，仿真結(jié)果如圖2所示。

圖2 1/6的信標(biāo)節(jié)點(diǎn)包含NLOS誤差情況下的均方根誤差比較

可以發(fā)現(xiàn)組合中位最小二乘法(Combination Median Lesat Squares，CMLS)比傳統(tǒng)的最小二乘法(Least Squares，LS)以及RWGH算法在針對(duì)非視距誤差有顯著的抑制作用。RWGH算法雖然在一定程度上也有效，但是根據(jù)非視距誤差的增大，效果變得不穩(wěn)定，而CMLS算法一直有很好的表現(xiàn)。RWGH與CMLS均需要進(jìn)行多個(gè)LS運(yùn)算，但CMLS所需要的運(yùn)算量要少于RWGH，對(duì)比見表1，而且RWGH還需要進(jìn)行殘差加權(quán)，更增加了運(yùn)算量。

表1 RWGH與CMLS算法LS運(yùn)算量的對(duì)比

但是也要指出，在6個(gè)信標(biāo)節(jié)點(diǎn)中，如果出現(xiàn)2個(gè)或多個(gè)信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)之間有非視距誤差時(shí)，此算法的性能將顯著下降，如圖3所示。

圖3 2/6的信標(biāo)節(jié)點(diǎn)包含NLOS誤差情況下的均方根誤差比較

如圖3顯示，6個(gè)信標(biāo)節(jié)點(diǎn)中有兩個(gè)測距值出現(xiàn)NLOS誤差時(shí)，RWGH與CMLS算法性能均不能滿意。需要說明的是，CMLS算法在有6個(gè)信標(biāo)節(jié)點(diǎn)時(shí)，3個(gè)1組，將有20種組合，如果一個(gè)信標(biāo)節(jié)點(diǎn)出現(xiàn)非視距誤差，將污染=10組定位數(shù)據(jù)，剛好是所有數(shù)據(jù)的一半。根據(jù)最小一乘法取中位數(shù)的思想，在20個(gè)橫坐標(biāo)或縱坐標(biāo)中取中位數(shù)，只要被污染的數(shù)據(jù)不超過總量的一半，就可以抑制這些超量誤差對(duì)最后結(jié)果的影響。比如13個(gè)信標(biāo)節(jié)點(diǎn)的測量值中包含2個(gè)非視距誤差時(shí)，將污染120組數(shù)據(jù)，而總共有286組數(shù)據(jù)。18個(gè)信標(biāo)節(jié)點(diǎn)中3個(gè)非視距誤差污染的測量值時(shí)，將污染256組數(shù)據(jù)，而總數(shù)有816組數(shù)據(jù)。這些情況下都可以很好地抑制非視距誤差。

4 結(jié)論

通過分析傳統(tǒng)的最小二乘法與NLOS誤差之間的關(guān)系，提出了CMLS算法。該算法不需要鑒別非視距誤差是否存在，更不需要對(duì)測量值進(jìn)行加權(quán)，只需一次測距，就可以在少量存在非視距誤差的情況下很好地抑制非視距誤差。此算法與定位系統(tǒng)的物理層無關(guān)，可以應(yīng)用在蜂窩無線定位等其他基于距離的定位系統(tǒng)中。此算法還避免了最小一乘法計(jì)算困難的缺點(diǎn)。

［1］KIM Y J，GOVINDAN R，KARP B，et al.Geo-graphic routing made practical［C］//Proc.NSDI’05.Berkeley，CA，USA:USENIX Association，2005:217-230.

［2］IEEE P802.15.4a/D4，Wireless medium access control(MAC)and physical layer(PHY)specifications for low-rate wireless personal area networks［S］.2006.

［3］VENKATESH S，BUEHRER R M.A linear programming approach to nlos error mitigation in sensor networks［C］//Proc.IPSN’06.New York，NY，USA:ACM，2006:301-308.

［4］WYLIE M P，HOLTZMAN J.The non-line-of-sight problems in mobile location estimation［C］//Proc.IEEE Int.Conf.Universal Personal Communications.［S.l.］:IEEE Press，1996:827-831.

［5］CHEN P C.A non-line-of-sight error mitigation algorithm in location estimation［C］//Proc.Wireless Communication and Networking Conference.Piscataway:IEEE Press，1999:316-320.

［6］WYLIE M P，HOLTZMAN J.The non-line-of-sight problems in mobile location estimation［C］//Proc.5th IEEE International Conference on Universal Personal Communications.［S.l.］:IEEE Press，1996:827-831.

［7］陳希孺.數(shù)理統(tǒng)計(jì)學(xué)簡史［M］.長沙:湖南教育出版社，2002.

［8］GONIN R，MONEY A H.Nonlinear lp-norm estimation［M］.New York，NY，USA:Marcel Dekker，Inc.，1989.

［9］李仲來.最小一乘法介紹［J］.數(shù)學(xué)通報(bào)，1992(2):42-45.