具有穩健性的無線傳感器網絡定位算法

宋 偉，樊孝明，王 玫

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

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

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

1 傳統定位算法

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

圖1 極大似然估計法示意圖

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

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

測距值的表達式

式中:di為測量距離值;dit為真實距離值;ei為測距誤差，通常可以認為是標準差很小，均值為0的正態分布;ni為非視距誤差，通常可以認為是服從具有正均值和較大方差的正態分布［6］。可見，非視距誤差是影響定位精度的主要因素。

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

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

這導致了以下做法，即設

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

求出的即為測量值的算數平均值。

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

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

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

3 算法與仿真

3.1 算法描述

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

1)如果有m個信標節點，1個未知節點，進行定位最少需要3個信標節點，所以m個節點就有種組合，設=k。

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

3)再用最小一乘法分別求出橫坐標與縱坐標的中位數。對x1，x2，x3，…，xk與y1，y2，y3，…，yk分別進行最小一乘法，即找出了x1，x2，x3，…，xk與y1，y2，y3，…，yk的中位數。

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

3.2 實驗仿真

為體現CMLS算法的效果，將本文算法與CHEN提出的RWGH［5］算法以及傳統的LS算法進行比較。因為算法的效果不僅與測量噪聲與非視距誤差有過，還與節點的分布有關，所以設在50 m×50 m的區域平均分布生7個點，(21.34，25)，(30，20)，(38.66，25)，(38.66，35)，(30，40)，(21.34，35)，(30，30)，其中(30，30)是未知節點的真實位置，其余為信標節點。未知節點與信標節點的真實距離為d1t=d2t=d3t=d4t=d5t=d6t=10 m。根據式(6)，設測距誤差滿足ei～N(0，0.52)，定位精度用均方根誤差(RMSE)來評價

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

圖2 1/6的信標節點包含NLOS誤差情況下的均方根誤差比較

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

表1 RWGH與CMLS算法LS運算量的對比

但是也要指出，在6個信標節點中，如果出現2個或多個信標節點到未知節點之間有非視距誤差時，此算法的性能將顯著下降，如圖3所示。

圖3 2/6的信標節點包含NLOS誤差情況下的均方根誤差比較

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

4 結論

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

［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］陳希孺.數理統計學簡史［M］.長沙:湖南教育出版社，2002.

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

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