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

金家保,張 頌,楊景曙

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

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

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

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

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

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

1 引 言

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

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

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

2 基本原理

2.1 定位模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)實(shí)驗(yàn)1(N=3)

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

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

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

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

(2)實(shí)驗(yàn)2(N>3)

本實(shí)驗(yàn)考慮超定情況下算法的定位性能,設(shè)定4個(gè)基站,各基站坐標(biāo)為 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組合算法的定位性能進(jìn)行了研究,其中SOCP松弛算法中的懲罰因子仍設(shè)為10-6,仿真結(jié)果如圖3所示。在量測(cè)噪聲較小的情況下,Chan算法、Chan+Tayor組合法以及SOCP+Taylor組合法的定位精度相當(dāng),都可以達(dá)到定位的CRLB。但隨著量測(cè)噪聲的增大,Chan算法的性能開始急劇下降,基于該算法的組合定位法由于初始用戶位置估計(jì)誤差較大,定位誤差RMSE迅速增大,并且會(huì)出現(xiàn)無(wú)法收斂的情況。SOCP松弛算法的定位性能卻始終比較穩(wěn)定,并且基于該方法的組合定位算法在量測(cè)噪聲較大時(shí)仍可以達(dá)到定位的CRLB。

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

圖4給出了本實(shí)驗(yàn)場(chǎng)景下懲罰因子對(duì)SOCP松弛算法的影響。從結(jié)果中可以看出,使算法有效的合適區(qū)間為[10-7,10-2],與實(shí)驗(yàn)1中的相同。可見不同場(chǎng)景以及不同的量測(cè)噪聲對(duì)懲罰因子的選取范圍基本沒有影響。

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

5 結(jié)束語(yǔ)

針對(duì)基于時(shí)差量測(cè)信息的移動(dòng)用戶定位問題,本文提出了一種基于SOCP的時(shí)差定位方法。仿真結(jié)果表明,基于SOCP松弛的新時(shí)差定位算法對(duì)量測(cè)噪聲不敏感,具有較好的定位性能。在基站數(shù)目為3時(shí),相比于其他定位算法,文中所提算法仍可以實(shí)現(xiàn)用戶的有效定位;當(dāng)基站數(shù)目大于3時(shí),通過將本算法的位置估計(jì)作為Taylor展開法迭代的初始點(diǎn),可以取得逼近于CRLB的定位性能。本算法求解一次用戶位置的時(shí)間大約為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]熊瑾煜,王巍,朱中梁.基于泰勒級(jí)數(shù)展開的蜂窩TDOA定位算法[J].通信學(xué)報(bào),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年獲博士學(xué)位,現(xiàn)為工程師,主要研究方向?yàn)闊o(wú)線電通信、信號(hào)處理等;

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)師,主要研究方向?yàn)闊o(wú)源定位、通信信號(hà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—),男,安徽長(zhǎng)豐人,2008年獲碩士學(xué)位,現(xiàn)為博士研究生,主要研究方向?yàn)闊o(wú)源定位、凸優(yōu)化應(yīng)用等;