NLOS無線環(huán)境中運用最優(yōu)化原理的定位算法

，， ，,

(1.浙江工業(yè)大學 信息工程學院，浙江 杭州 310023；2.東南大學 移動通信國家重點實驗室，江蘇 南京 210096)

近幾年來，無線定位技術已經(jīng)成為了物聯(lián)網(wǎng)中一項非常熱門的研究內(nèi)容，并且得到了較大的發(fā)展[1].現(xiàn)有定位技術中主要針對測量距離和測量角度這兩類參量展開研究[2-3]：包括到達時間(Time of arrival, TOA)[4]、到達時間差(Time difference of arrival, TDOA)[5-6]、接收信號強度(Received signal strength, RSS)[7]、到達角(Angle of arrival, AOA)以及它們的混合參量TOA/AOA和TDOA/AOA等[8-9].但是無論定位算法采用何種參量，它都會受到兩種誤差影響.其一是測量誤差，一般假設其為具有較小標準差的零均值高斯變量[10]，在傳統(tǒng)的視距傳輸(LOS)定位中，這是主要的誤差源.而對于城市無線通信，信號傳播過程中折射和反射等現(xiàn)象引起的非視距(Non-line of sight, NLOS)誤差具有更大的數(shù)值，并已成為無線定位最主要的誤差.在實際的GSM網(wǎng)絡中，NLOS誤差可以達到500～700 m[11]，同時其統(tǒng)計分布無法進行精確建模，從而要在定位中消除NLOS誤差極為困難.綜上，NLOS誤差的抑制已經(jīng)成為無線定位算法實用化的關鍵.

目前，主要存在三類非視距誤差抑制的定位算法.第一類是試圖對非視距誤差進行精確建模，然后根據(jù)所建模型來估計移動終端(MS)的位置[12-13].由于實際中很難得到一個精確的非視距模型用于描述復雜多變的傳輸環(huán)境，這一類算法難以廣泛應用.第二類算法認為LOS傳輸?shù)幕居袆e于NLOS傳輸?shù)幕?，因而可以?jù)此將NLOS基站識別出來，最后只利用LOS基站進行位置估計[14-15].此類算法需要實際環(huán)境中存在一定數(shù)目的LOS基站，而且NLOS基站識別的虛警率無法控制，因此定位精度難以確保.第三類算法嘗試對測量距離或者中間估計量進行加權，權值來源于基站和終端之間幾何關系以及代數(shù)關系.該類算法最典型的就是以殘差為代價函數(shù)，以真實距離和測量距離之間的關系為約束條件，建立最優(yōu)化問題，終端的位置估計可以通過解決該問題來獲得[16-18].這一類算法的優(yōu)點在于無論MS處于何種環(huán)境，總是可以將其位置估計出來，但是缺點也是顯然的，它的估計精度并不是非常高.筆者選擇第三類方法作為研究方向，為此從傳統(tǒng)的LLOP算法出發(fā)，通過模型轉化將它修正為一個二次規(guī)劃最優(yōu)化問題.其中最優(yōu)化的目標函數(shù)定義為距離殘差，而約束條件通過真實距離和測量距離之間的關系以及真實位置和可行域之間的關系來確定，最終通過標準的二次規(guī)劃實現(xiàn)移動終端的位置估計，這一過程區(qū)別于傳統(tǒng)的定位算法，計算機仿真表明所提出的算法在NLOS環(huán)境下明顯優(yōu)于其它定位算法.

1 LLOP定位原理

LLOP定位算法利用測距為參數(shù)建立一系列的方程組[19]，其幾何意義就是求得以各個基站為圓心，以測距為半徑的幾個圓的兩兩相交線，所有相交線的交點就是MS的位置，如圖1虛線所示.

圖1 LLOP定位原理圖

圖1中假設(x,y)為待估的MS位置，(Xi,Yi)為已知的第i個基站坐標(基站數(shù)量為M個)，則MS和第i個基站之間的距離為

(1)

對式(1)兩邊分別進行平方，易得

(2)

(3)

式(3)現(xiàn)在僅有M-1條方程.進一步把式(3)改寫成矩陣形式，可以得到

Y=AX

(4)

其中

這里X代表MS的真實位置信息，其估計值可以利用最小二乘(Least square,LS)算法[20-21]求得

(5)

2 運用最優(yōu)化理論的抗NLOS定位算法

2.1 目標函數(shù)

在實際傳播環(huán)境中，NLOS的存在會使得距離的測量要遠遠大于真實的距離，假設測量距離為di，那么它和ri之間的關系為

ri=αidi

(6)

其中αi為處于0～1之間的某個數(shù).如果把式(6)代入到式(3)中，就能夠得到

(7)

同樣，可以把式(7)轉變成矩陣形式

Y1Y2=AX

(8)

其中

顯然如果αi的取值能夠通過某種方式獲得，那么就可以得到X的LS解為

(9)

根據(jù)式(9)，定位精度就取決于能否獲得合適的αi取值，這可以通過解最優(yōu)化問題實現(xiàn).首先我們定義最優(yōu)化的目標函數(shù)為

(10)

(11)

其中K=[K1-K2,K1-K3,…,K1-KM]T.

2.2 約束條件

約束條件就是目標參數(shù)需要遵循的幾種規(guī)則，而最優(yōu)化算法就是在這些符合約束條件的可選點中找出使目標函數(shù)達到預期值的最優(yōu)解.所提出算法的約束條件主要有兩種，第一種可以根據(jù)前人文獻[16]的參量取值界限思想推廣得到.首先定義向量V的下限Vmin

(12)

圖2 基站-移動臺的幾何拓撲

第二個約束條件可以從圖2中觀察得到：由于在NLOS環(huán)境中，MS和BS之間的距離必然小于測量距離，因此MS必然位于幾個圓的公共區(qū)域，我們可以稱MS可能出現(xiàn)的區(qū)域為可行域(Feasible region,FS)，即圖中A，B，C，D幾個點包圍的弧形區(qū)域，那么第二個約束條件可以表示為

MS坐標∈可行域

(13)

基于可行域的特性，可以把此約束條件重寫成

(14)

其中

2.3 最優(yōu)化問題

根據(jù)2.1和2.2小節(jié)的分析，我們可以把NLOS環(huán)境中的權值搜索問題轉變?yōu)榻庖粋€最優(yōu)化問題，該最優(yōu)化問題如下：

(15)

式(15)可以用標準二次規(guī)劃算法[22]求解，在得到向量V的最優(yōu)解之后，將其代入到式(9)就能夠得到MS的最優(yōu)位置估計.

3 仿真分析

基于上述仿真參數(shù)，所提出的算法將和TDOA兩次ML算法(TSML)[23]、LLOP算法以及CLS算法[24]進行比較，仿真結果中的nBS指參與定位的基站為n個.每個仿真獨立運行1 000次，所有的仿真均在MATLAB 7.0下完成.

3.1 NLOS誤差對定位精度的影響

由于MAX的大小必然影響各定位算法的精度，因此將測試NLOS誤差極限值MAX的變化對各算法的影響.假設MAX的大小為100～600 m之間，間隔為100 m，基站數(shù)目為5個.

圖3 NLOS對各算法RMSE的影響

圖3給出了各個算法均方根誤差(Root mean square error, RMSE)的對比，可以發(fā)現(xiàn)：所有算法的精度都隨著NLOS誤差的MAX變大而降低，而與筆者算法相比TSML，LLOP和CLS算法，精度的下降更緩慢.可見所提出算法比其他算法穩(wěn)定.另外，當NLOS誤差的MAX為180 m時，所提出算法的精度要略低于CLS算法，而在其他情況下，該算法的精度都是最高的.

3.2 基站數(shù)目對定位精度的影響

假設參與定位的基站分別有3，4，5個，MAX的值為400 m，這里各算法的精度將以概率的累積分布函數(shù)(Cumulative distribution function, CDF)表示，結果如圖4所示.

圖4 基站數(shù)目對各算法CDF的影響

從圖4的概率CDF結果可以看出:所提出算法總體而言是要優(yōu)于其他算法，尤其參與定位的基站數(shù)目較多時，而BS數(shù)目的增加對于其他算法的性能改善明顯小于筆者算法.

3.3 LOS-BS對定位精度的影響

顯然LOS基站的存在與否也會對定位精度產(chǎn)生影響，因此非常有必要對此進行仿真分析.假設基站數(shù)目為5，LOS基站數(shù)目分別為0，1，2個，MAX為400 m.仿真結果如圖5所示.

圖5 LOS基站數(shù)目對各算法精度的影響

從圖5可以看到：如果LOS-BS數(shù)目非0，所提出算法的精度可以明顯提高，且在對比的算法中表現(xiàn)最佳，特別是把LOS-BS數(shù)目為2時的情況和不存在LOS-BS數(shù)目的時候進行比較，就能看出它們的顯著差別.因而可以預見，當存在更多LOS-BS時，所提出算法的精度將變得更高.而對于另外幾種傳統(tǒng)算法而言，LOS-BS的存在對定位精度的改善十分有限.

綜上所述，在定位精度上，所提出算法要優(yōu)于傳統(tǒng)的定位算法.而且基站數(shù)目的增加會使得該算法的精度顯著上升.同時LOS基站的存在會使可行域的范圍縮小，還會使算法的定位精度進一步上升.

5 結 論

非視距誤差是無線定位研究中的一個難點，它的存在會顯著降低傳統(tǒng)算法的定位精度，因而必須對其影響進行抑制甚至移除.在對傳統(tǒng)NLOS抑制算法的研究基礎上提出了一種新型的基于最優(yōu)化理論的NLOS抑制定位算法，該算法通過把LLOP定位模型轉換為最優(yōu)權值的搜索問題，進而用二次規(guī)劃解決這一最優(yōu)化問題，從而顯著改善了定位性能，在仿真對比中優(yōu)于其他算法.另外BS數(shù)目增加或者存在LOS-BS，筆者算法的定位精度將進一步提高，而傳統(tǒng)算法的精度則沒有明顯變化.

本文得到了東南大學移動通信國家重點實驗室開放課題(2010D06)的資助.

參考文獻：

[1]呂彩忠,李煒,廖小輝.GPS測量在公路控制網(wǎng)建設中的應用[J].浙江工業(yè)大學學報,2012,40(2):178-182.

[2]XU E, DING Z, DASGUPTA S. Source localization in wireless sensor networks from signal time-of-arrival measurements[J]. IEEE Transactions on Signal Processing,2011,59(6):2887-2897.

[3]CAFFERY J J, STUBER G L. Subscriber location in CDMA cellular networks[J]. IEEE Trans Veh Tech,1998,47(2):406-416.

[4]CHAN Y T, HANG Y C, CHINH P C. Exact and approximate maximum likelihood localization algorithms[J]. IEEE Transactions on Vehicular Technology,2006,55(1):10-16.

[5]ZHANG H, YU M, CUI X, GULLIVER T A. An improved Taylor series based location algorithm for IEEE 802.15.4a channels[C]//2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing. Victoria, BC, Canada: IEEE,2011:499-503.

[6]SMITH J O. Closed-form least-squares source location estimation from range-difference measurements[J]. IEEE Transactions on Acoustics Speech and Signal Processing,1987,25(8):1223-1225.

[7]YAN Y. Efficient convex optimization method for underwater passive source localization based on RSS with WSN[C]//2012 IEEE International Conference on Signal Processing, Communication and Computing. Hongkong: IEEE,2012:171-174.

[8]LEE Y S. A study on the performance of wireless localization system based on AOA in WSN environment[C] //2011 Third International Conference on Intelligent Networking and Collaborative Systems. Fukuoka, Japan: IEEE,2011:184-187.

[9]ZHANG V Y, WONG A K, WOO K T, et al. Hybrid TOA/AOA-based mobile localization with and without tracking in CDMA cellular networks[C]//2010 IEEE Wireless Communications and Networking Conference. Sydney, Australia: IEEE,2010:1-6.

[10]CHAN Y T, TSUI W Y, SO H C, et al. Time-of-arrival based localization under NLOS conditions[J]. IEEE Transactions on Vehicular Technology,2006,55(1):17-24.

[11]SILVENTOINEN M, RANRALAINEN T. Mobile station emergency locating in GSM [C] // 1996 IEEE International Conference on Personal Wireless Communication. New Delhi, India: IEEE,1996:232-238.

[12]AL-JAZZAR S, CAFFERY J J, YOU H R. A scattering model based approach to NLOS mitigation in TOA location systems[C]// 2002 IEEE Vehicular Technology Conference, Birmingham, UK: IEEE,2002:861-865.

[13]AL-JAZZAR S, CAFFERY J J. ML and Bayesian TOA location estimators for NLOS environments[C] // 2002 IEEE Vehicular Technology Conference. Birmingham, UK: IEEE,2002:856-860.

[14]GUVENC I, CHONG C C, WANTANABLE F, INAMURA H. NLOS identification and weighted least squares localization for UWB systems using multipath channel statistics[J]. EURASIP Journal on Advances in Signal Processing,2008,36(1):1-14.

[15]CONG L, ZHUANG W H. Non-line-of-sight error mitigation in mobile location[J]. IEEE Transaction on Wireless Communications,2004,4(2):560-573.

[16]VENKATRAMAN S, CAFFERY J J, YOU H R. A novel TOA location algorithm using LOS range estimation for NLOS environments[J]. IEEE Transaction on Vehicular Technology,2004,53(5):1515-1524.

[17]KHAJEHNOURI N, SAYED A H. A non-line-of-sight equalization scheme for wireless cellular location[C] // 2003 IEEE International Conference on Acoustics, Speech and Signal Processing. Hongkong: IEEE,2003:549-552.

[18]CHEN P P, A non-line-of-sight error mitigation algorithm in location estimation[C]//1999 IEEE Wireless Communications and Networking Conference. New Orleans, LA, USA: IEEE,1999:316-320.

[19]CAFFERY J J. A new approach to the geometry of TOA location[C]//2000 IEEE Vehicular Technology Conference. Boston, Ma USA: IEEE,2000:1943-1949.

[20]王理同.帶隨機線性約束的最小二乘估計的相對效率[J].浙江工業(yè)大學學報，2012,40(3):352-354.

[21]許曉輝,王炳忠,劉志.基于最小二乘法的二維條碼圖像傾斜校正方法[J].浙江工業(yè)大學學報，2008,36(3):250-253.

[22]龔純,王正林.精通MATLAB最優(yōu)化計算[M].1版.北京：電子工業(yè)出版社，2009.

[23]CHAN Y T, HO K. A simple and efficient estimator for hyperbolic location [J]. IEEE Transaction on Signal Processing,1994,42(8):1905-1915.

[24]WANG X, WANG Z, ODEA B. TOA-based location algorithm reducing the errors due to non-line-of-sight propagation [J]. IEEE Transactions on Vehicular Technology,2003,52(1):112-116.