一種基于二階錐規(guī)劃的新時差定位算法

金家保,張 頌,楊景曙

(1.解放軍電子工程學院信息系,合肥 230037;2.總參陸航研究所,北京 101121)

一種基于二階錐規(guī)劃的新時差定位算法

金家保1,張 頌2,楊景曙1

(1.解放軍電子工程學院信息系,合肥 230037;2.總參陸航研究所,北京 101121)

針對傳統(tǒng)時差定位算法在量測噪聲較大情況下定位性能不佳的缺點,提出了一種基于二階錐規(guī)劃的新時差定位算法。該算法通過凸松弛和引入懲罰項,將難以求解的用戶位置最大似然估計問題轉(zhuǎn)換為一個易于求解的二階錐規(guī)劃問題,并將松弛問題的最優(yōu)解作為用戶位置的初始估計,利用傳統(tǒng)的泰勒級數(shù)展開法得到最終定位結(jié)果。仿真給出了不同基站數(shù)目及量測噪聲下算法的定位性能。仿真結(jié)果表明,在量測噪聲較大的情況下,新算法的定位精度仍可以逼近理論克拉美羅下限,而且算法中懲罰因子的選取范圍易于確定。

到達時差;定位算法;最大似然估計;泰勒級數(shù)展開;二階錐規(guī)劃;懲罰因子

1 引 言

隨著移動通信技術(shù)的迅速發(fā)展,無線定位技術(shù)已經(jīng)成為第三代移動通信系統(tǒng)所必須具備的業(yè)務(wù),而基于用戶位置的各種應(yīng)用也成為最具發(fā)展?jié)摿Φ臄?shù)據(jù)業(yè)務(wù)之一[1]。移動通信定位根據(jù)定位采用的信息不同,可以分為到達信號能量定位法、到達時間(Time of Arrival,TOA)定位法、到達時差(Time Difference of Arrival,TDOA)定位法。由于TDOA定位法不要求移動臺與基站之間的時間嚴格同步,能應(yīng)用于各種移動通信系統(tǒng),且定位精度較高,因而受到廣泛關(guān)注。

在時差定位問題中,由于TDOA量測值與目標位置之間的非線性關(guān)系,使得即使在高斯量測噪聲的情況下,也難以得到目標位置的最大似然估計。因此,時差定位算法主要集中于求解目標位置的近似最優(yōu)解,常用的時差定位算法可以分為閉式解法和迭代解法兩種?；谔├占墧?shù)(Taylor)展開的迭代算法[2]具有較高的定位精度,但需要一個接近真實位置的初始估計值以避免算法收斂到局部最優(yōu)解處。閉式解法不需要初始位置估計值,也不存在收斂問題,且計算量較小,但定位精度較差。常見的閉式解法主要有球面插值法(SI)[3]、LCLS方法[4-5]、兩步加權(quán)最小二乘法(Chan算法[6])等。其中,Chan算法在量測噪聲較小的情況下具有較高的定位精度,但隨著量測噪聲的增大或幾何布局不佳時,該算法的定位性能將急劇下降。為了克服Chan算法和Taylor法各自的缺點,文獻[7]提出了一種基于Chan算法和Taylor法的組合定位方法,即首先通過Chan算法得到初始用戶位置,然后將其作為Taylor法的初始迭代點求解出最終的用戶位置。雖然這種組合方法有效地提高了定位精度,但當Chan算法得到的初始用戶位置誤差較大時,會導(dǎo)致后續(xù)迭代無法收斂;另外,當參與定位的基站個數(shù)等于3時,Chan算法將求解不出用戶初始位置,從而使得這種組合定位算法完全失效。

近年來,隨著凸優(yōu)化理論的發(fā)展和成熟,凸優(yōu)化[8]在信號處理領(lǐng)域的應(yīng)用也得到了人們的廣泛關(guān)注,基于凸優(yōu)化的定位算法也陸續(xù)被提出,但這些方法往往是針對TOA定位問題的。本文針對移動用戶的TDOA定位問題,提出了一種基于二階錐規(guī)劃(Second Order Cone Programming,SOCP)[9]松弛的定位算法,該算法通過凸松弛以及引入懲罰項,將難以求解的非線性非凸最大似然估計問題轉(zhuǎn)換為易于求解的凸優(yōu)化問題,并將其最優(yōu)解作為泰勒級數(shù)法的初始迭代點從而得到精確的用戶位置。計算機仿真實驗表明本算法的定位性能優(yōu)于傳統(tǒng)的Chan算法和組合定位法。

2 基本原理

2.1 定位模型

假設(shè)定位系統(tǒng)中共有 N個基站,向量 si=[xi,yi]T表示基站i的位置坐標,u=[xu,yu]T表示用戶的位置坐標。在假定電磁波傳播速度為常數(shù)的情況下,基于TDOA與距離差定位是完全一致的。下面的討論就是建立在距離差上的。不失一般性,以基站s1作為量測參考站,相應(yīng)的量測方程為

將式(1)寫為向量的形式:

定位算法所要解決的問題就是在給定基站位置和一組距離差量測值 d的情況下,如何快速、準確地確定用戶的位置。為了充分利用量測信息,本文采用最大似然準則來估計用戶位置,假設(shè)噪聲向量n服從均值為零、協(xié)方差陣為Qn的高斯分布,則量測向量 d的似然函數(shù)為

其中,K為常數(shù)。求使似然函數(shù)最大的用戶位置坐標值等價于求解如下的優(yōu)化問題:

優(yōu)化問題(4)是一個關(guān)于用戶坐標的非線性非凸二次優(yōu)化問題,其全局最優(yōu)解難以得到,傳統(tǒng)的非線性迭代求解方法(如泰勒級數(shù)展開法、牛頓法)需要一個接近真實位置坐標的初始估計,否則迭代法難以收斂。

2.2 二階錐規(guī)劃簡介

所謂SOCP,就是在有限個二階錐的笛卡爾乘積的仿射子空間的交集上極小化一個線性函數(shù),其數(shù)學表述一般為

3 基于二階錐規(guī)劃的定位算法

對于難以求解的非線性非凸優(yōu)化問題(4),首先引入輔助變量ri=‖u-si‖,則問題(4)可以描述為

其中,r=[r1,r2,…,rN]T,H=[-1 I],1為(N-1)×N的全1向量,I為單位矩陣。

在優(yōu)化問題(6)中,目標函數(shù)是關(guān)于優(yōu)化變量r的二次凸函數(shù),而非線性的等式約束使的該問題仍然是一個非線性非凸的優(yōu)化問題。為了將其轉(zhuǎn)化為SOCP問題,考慮將等式約束松弛為不等式約束‖u-si‖≤ri,并引入懲罰項 ρ rTr對松弛的約束條件加以限制,則可以得到松弛后的優(yōu)化問題為

其中,ρ>0是一個較小的常數(shù),稱為懲罰因子。

為了將優(yōu)化問題(7)表示成SOCP形式,首先對目標函數(shù)進行如下變換:

將式(8)代入問題(7)中,注意到目標函數(shù)中的常數(shù)項并不影響優(yōu)化問題的求解,將其忽略得到

再次引入輔助變量ξ,則優(yōu)化問題(9)與下述優(yōu)化問題等價:

至此,得到一個與問題(7)完全等價的SOCP問題(10),其全局最優(yōu)解可以通過內(nèi)點算法[9]進行有效求解,具體求解過程此處不再敘述。得到其全局最優(yōu)解 x＊=(u＊,r＊,ξ＊),x＊中的 u＊即為用戶位置估計,將其作為Taylor級數(shù)展開法的初始位置估計,進一步提高用戶位置估計精度。

4 仿真實驗

為了評估和比較算法的定位性能,并考慮實際中可能出現(xiàn)的多種情況,進行了2 000次統(tǒng)計獨立的Monte-Carlo仿真實驗。量測噪聲 n為零均值高斯分布,其協(xié)方差矩陣Qn主對角線上的元素值為σ2d,非主對角線元素的值為0.5σ2d,即假設(shè)各基站之間的量測噪聲是相互獨立的,采用定位結(jié)果的均方根誤差(Root Mean Square Error,RMSE)來衡量算法的定位性能,實驗中通過逐次改變噪聲方差的值,得到不同噪聲方差下算法的定位性能。N表示參與定位的基站數(shù)目,SOCP問題采用凸優(yōu)化工具箱CVX進行求解。

(1)實驗1(N=3)

本實驗中,用戶位置為u=(40 m,30 m)T,3個基站的坐標分別為 s1=(-20 m 80 m)T,s2=(120 m 40 m)T,s3=(0 m-60 m)T。圖1給出了SOCP松弛算法(懲罰因子設(shè)為ρ=10-6)和Chan算法在不同量測噪聲方差下的定位誤差RMSE曲線,同時為了評估算法的性能,給出了定位RMSE的克拉美羅下限(Cramer-Rao Lower Bound,CRLB)。由于Chan算法中的系數(shù)矩陣在N=3時為奇異陣,本實驗中用偽逆操作代替了原始的求逆操作。從實驗結(jié)果中看以看出,在基站數(shù)目為3時,本算法不但能夠完成對用戶的位置估計,并且定位性能達到了CRLB,而Chan算法在這種情況下則無法完成用戶的有效定位。

圖1 不同量測噪聲下的定位RMSEFig.1 Location R MSE versus measurement noise

懲罰因子對SOCP松弛定位算法的性能有著很大影響,為了確定懲罰因子合適的選取范圍,分別就兩種不同量測噪聲情況下,懲罰因子對定位性能的影響進行了研究,結(jié)果如圖2所示。從中可以看出,懲罰因子的合適選取范圍為[10-7,10-2],在此區(qū)間內(nèi)該算法均可完成對用戶的有效定位。

圖2 懲罰因子對定位R MSE的影響Fig.2 Location R MSE versus different penalty factor

(2)實驗2(N>3)

本實驗考慮超定情況下算法的定位性能,設(shè)定4個基站,各基站坐標為 s1=(80 m 98 m)T,s2=(70 m-80 m)T,s3=(-80 m-75 m)T,s4=(-91 m 82 m)T。用戶位置為 u=(12 m,10 m)T。分別就SOCP松弛算法、Chan算法、Chan+Taylor組合法、SOCP+Taylor組合算法的定位性能進行了研究,其中SOCP松弛算法中的懲罰因子仍設(shè)為10-6,仿真結(jié)果如圖3所示。在量測噪聲較小的情況下,Chan算法、Chan+Tayor組合法以及SOCP+Taylor組合法的定位精度相當,都可以達到定位的CRLB。但隨著量測噪聲的增大,Chan算法的性能開始急劇下降,基于該算法的組合定位法由于初始用戶位置估計誤差較大,定位誤差RMSE迅速增大,并且會出現(xiàn)無法收斂的情況。SOCP松弛算法的定位性能卻始終比較穩(wěn)定,并且基于該方法的組合定位算法在量測噪聲較大時仍可以達到定位的CRLB。

圖3 不同量測噪聲下的定位R MSEFig.3 Location RMSE versus measurement noise

圖4給出了本實驗場景下懲罰因子對SOCP松弛算法的影響。從結(jié)果中可以看出,使算法有效的合適區(qū)間為[10-7,10-2],與實驗1中的相同?？梢姴煌瑘鼍耙约安煌牧繙y噪聲對懲罰因子的選取范圍基本沒有影響。

圖4 懲罰因子對定位RMSE的影響Fig.4 Location RMSE versus different penalty factor

5 結(jié)束語

針對基于時差量測信息的移動用戶定位問題,本文提出了一種基于SOCP的時差定位方法。仿真結(jié)果表明,基于SOCP松弛的新時差定位算法對量測噪聲不敏感,具有較好的定位性能。在基站數(shù)目為3時,相比于其他定位算法,文中所提算法仍可以實現(xiàn)用戶的有效定位;當基站數(shù)目大于3時,通過將本算法的位置估計作為Taylor展開法迭代的初始點,可以取得逼近于CRLB的定位性能。本算法求解一次用戶位置的時間大約為1 ms,且算法中的懲罰因子選取范圍容易確定,在工程上具有一定的應(yīng)用前景。

[1]Zekavat R,Buehrer R M.Handbook of Position Location:Theory,Practice and Advances[M].Wiley:IEEE,2010:25-28.

[2]Foy W H.Position-Location Solutions by Taylor-series Estimation[J].IEEE Transactions on Aerospace and Electronic Systems,1976,12(2):187-193.

[3]Schau H C,Robinson A Z.Passive Source Localization employing intersecting spherical surfaces from time-of-arrival differences[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1987,35(8):1223-1225.

[4]Yiteng Huang,Jacob Benesty,Elko G W,et al.Real-time Passive Source Localization:A Practical Linear-Correction Least-Squares Approach[J].IEEE Transactions on Speech and Audio Processing,2001,19(8):943-956.

[5]Beck A,Stoica P,Li Jian.Exact and Approximate Solutions of Source Localization Problems[J].IEEE Transactions on Signal Processing,2008,56(5):1770-1778.

[6]ChanY T,Ho K C.A Simple andEfficient Estimator for Hyperbolic Location[J],IEEE Transactions on Signal Processing,1994,42(8):1905-1915.

[7]熊瑾煜,王巍,朱中梁.基于泰勒級數(shù)展開的蜂窩TDOA定位算法[J].通信學報,2004,25(4):145-150.XIONG Jin-yu,W ANG Wei,ZHU Zhong-liang.TDOA location algorithm based on T aylor series expansion[J].Journal on Communications,2004,25(4):145-150.(in Chinese)

[8]Boyd S,Vandenberghe L.Convex Optimization[M].Cambridge,UK:Cambridge University Press,2005.

[9]Lobo M S,Vandenberghe L,Boyd S,et al.Applications of second-order cone programming[J].Linear Algebra and its Application,1998,284(1-3):193-228.

JIN Jia-bao was born in Changfeng,Anhui Province,in 1982.He received the M.S.degree in2008.He is currently working toward the Ph.D.degree.His research concerns passive location and convex optimization application.

Email:jin-jiabao@qq.com

張 頌(1984—),男,江蘇徐州人,2011年獲博士學位,現(xiàn)為工程師,主要研究方向為無線電通信、信號處理等;

ZHANG Song wasborn in Xuzhou,Jiangsu Province,in1984.He received the Ph.D.degree in 2011.He is now an engineer.His research interestsinclude wireless communication and signal processing.

楊景曙(1950—),男,安徽合肥人,教授、博士生導(dǎo)師,主要研究方向為無源定位、通信信號處理、導(dǎo)航技術(shù)等。

YANG Jing-shu was born in Hefei,Anhui Province,in 1950.He is now a professor and also the Ph.D.supervisor.His research concerns passive location,signal processing and radio navigation.

A New TDOA Location Algorithm Based on Second Order Cone Programming

JIN Jia-bao1,ZHANG Song2,YANGJing-shu1
(1.Information Department,Electronic Engineering Institute,Hefei 230037,China;2.The Army Aviation Research Institute of Headquarters of General Staff,Beijing 101121,China)

The traditional TDOA(Time Difference of Arrival)location algorithms have large performance loss as the measurement noise is high.To overcome this drawback,this paper proposes a new effective TDOA location algorithm based on second order cone programming(SOCP).By introducing a penalty term and relaxing the equality constrains,the nonlinear and nonconvex maximum likelihood estimation problem for user position is transformed into a convex optimization problem,named second order cone programming that can be efficiently solved by modern interior point methods.The optimal solution of relaxed problem is used as the initial guess for traditional Taylor method to estimate the user position.The simulation provides the location performance versus measurement noise under different numbers of base station.Simulation results show that the performance of proposed algorithm can attain the Cramer-Rao lower bound as the noise variance is high.The intervals of penalty factor are also discussed in this paper.

TDOA;location algorithm;maximum likelihood estimator;Taylor series expansion;second order cone programming;penalty factor

TN929.5

A

10.3969/j.issn.1001-893x.2012.06.011

1001-893X(2012)06-0888-05

2012-04-11;

2012-06-04

金家保(1982—),男,安徽長豐人,2008年獲碩士學位,現(xiàn)為博士研究生,主要研究方向為無源定位、凸優(yōu)化應(yīng)用等;