基于半定松弛的到達時差定位算法

吳　蓋

(西安電子科技大學(xué)電子信息攻防對抗與仿真技術(shù)教育部重點實驗室，陜西 西安 710071)

?

·工程應(yīng)用·

基于半定松弛的到達時差定位算法

吳蓋

(西安電子科技大學(xué)電子信息攻防對抗與仿真技術(shù)教育部重點實驗室，陜西 西安 710071)

針對到達時差定位系統(tǒng)，提出了一種新的基于半定松弛的時差定位算法。該方法首先將距離測量誤差作為一項重要參數(shù)，在到達時差測量模型下，建立了一個關(guān)于定位估計的非凸優(yōu)化問題，然后通過松弛約束條件將該非凸優(yōu)化問題轉(zhuǎn)換成等價的凸優(yōu)化問題，運用凸優(yōu)化理論中的半定松弛規(guī)劃方法求解目標(biāo)的位置。仿真實驗結(jié)果表明，該方法可以有效降低定位誤差。

到達時差；凸優(yōu)化；半定松弛；定位誤差

0　引言

多站時差定位系統(tǒng)具有較高的定位精度，近年來得到了快速發(fā)展，并已廣泛應(yīng)用于雷達、聲納[1]、無線傳感器網(wǎng)絡(luò)[2]等領(lǐng)域。根據(jù)定位利用的信息不同，無源定位可以分為三角定位、交叉定位和時差定位等。其中多站時差定位又稱為雙曲線定位，該方法具有定位速度快、精度高的優(yōu)點，因而被廣泛應(yīng)用于各領(lǐng)域。

非線性方法和線性方法[3]是解決時差定位問題的兩種常見方法。非線性理論的思路是嘗試直接求解出目標(biāo)輻射源的位置，它包含非線性最小二乘估計(NLS)和極大似然估計(ML)[4]。線性定位原理的基本思路是把非線性方程轉(zhuǎn)化為線性方程組再進行求解。通常，相比而言，非線性方法具有更高的定位精度。但是由于代價函數(shù)是多峰值的，常用的非線性方法不能保證全局性的收斂。然而線性方法經(jīng)過線性優(yōu)化的代價函數(shù)是單峰的，就能夠保證獲得全局解，并且該方法計算量較小，但隨著測量誤差的增大，該方法的性能也會急劇下降[5]。本文提出的基于半定松弛(SDR)的到達時差定位方法能夠平衡線性和非線性這兩種方法，也就是說，該方法同時具有精度高和全局收斂的優(yōu)點。該方法先將NLS或者ML估計問題轉(zhuǎn)化為一個等價的約束優(yōu)化問題，然后松弛約束條件得到一個凸的半定規(guī)劃問題。松弛后的凸優(yōu)化問題易于求解且具有唯一的全局最優(yōu)解。最后通過仿真實驗驗證了該定位算法的有效性。

1　問題描述

假設(shè)時差定位系統(tǒng)共有L(L≥4)個觀測站，各觀測站的坐標(biāo)為：Xl=[xlyl]T,l=1,2,…,L。以觀測站X1作為整個時差定位系統(tǒng)的參考站。目標(biāo)輻射源的位置為X=[xy]T。目標(biāo)輻射源同各個觀測站之間的徑向距離記為dl，其表達式為：

dl=‖X-Xl‖=((x-xl)2+(y-yl)2)1/2,l=1,2,…,L

(1)

式中, ‖·‖表示向量的二范數(shù)。

那么從TDOAs得來的徑向距離差為:

(2)

式中,ql是徑向距離的誤差，它與時間差的誤差成正比。

由式(1)、式(2)可以得到:

(3)

又由式(1)可知dl=rl,1+d1-ql，代入式(3)可消去變量dl：

(4)

將式(4)寫成矩陣形式[6]：

(5)

式中,

(6)

(7)

X=[X1-X2X1-X3…X1-XL]T

(8)

Pr=[diag(r)-r]

(9)

r=[r2,1r3,1…rL,1]T

(10)

P±=[±IL-1]

(11)

q=[q2q3…qLd1]T

(12)

Q=qqT

(13)

注意QL,L與X有關(guān)。

(14)

式中，R=XTX。

由于ql為徑向距離的誤差，在誤差平方最小準(zhǔn)則下，并考慮到上述約束關(guān)系，則目標(biāo)位置估計問題可以描述為如下的優(yōu)化公式:

(15)

(16)

2　基于半定松弛的到達時差定位算法

SDR是求解非線性非凸優(yōu)化問題的一種精確近似方法，并且對于許多非凸的優(yōu)化問題，這種近似解法往往可以得到原優(yōu)化問題的最優(yōu)解。優(yōu)化問題式(15)、(16)實際上是一個非凸的等式約束優(yōu)化問題，本節(jié)采用半定松弛方法對該問題進行求解。

根據(jù)矩陣跡的性質(zhì)XTAX=tr(XTAX)=tr(XXTA),則式(15)有如下等價：

(17)

(18)

在凸優(yōu)化理論值，式(16)是一個SDR問題。事實上，求解此類問題方法很多，本文提供一種方法：可以在Matlab中使用凸優(yōu)化工具箱CVX來求解[7]。

3　仿真實驗

本節(jié)分別就近場目標(biāo)u1=(200,300)和遠場目標(biāo)u1=(1500,1600)，對基于SDR的時差定位算法進行了仿真分析。仿真實驗中共設(shè)置了4個觀測站，3個副站以主站為中心成Y型分散，各副站到主站的距離為500m。主站及3個副站的坐標(biāo)分別為(0,0)、(500,0)、(-250,433)、(-250,-433)。各觀測站及目標(biāo)u1，u2的位置如圖1所示。

圖1　觀測站及目標(biāo)的位置

實驗中設(shè)定由時差誤差造成的徑向距離誤差ql為零均值高斯分布，其協(xié)方差矩陣的主對角線元素的值為σ2，各副站之間的徑向距離誤差是相互獨立的。通過改變σ2的精度，得到算法在不同測量誤差情況下的定位性能。共進行了200次獨立統(tǒng)計實驗，并統(tǒng)計位置估計的均方根誤差RMSE。圖2為ML、線性最小二乘法(LLS)[8]以及本文所提的SDR解法對近場目標(biāo)的位置估計RMSE曲線，圖3為上述3種算法對遠場目標(biāo)的位置估計RMSE曲線。

圖2　對近場目標(biāo)的定位RMES曲線

圖3　對遠場目標(biāo)的定位RMES曲線

從仿真結(jié)果中可以看出，SDR方法主要有ML算法以及LLS算法。 從圖2可以看出， 在近場情況下，SDR算法達到了定位的CRLB。對于遠場目標(biāo)，雖然SDR算法性能有一定的下降，但相對于另外兩種算法仍然具有較小的定位RMSE。同時從圖2和圖3可以看出，在實驗條件下，隨著σ2的增大，定位誤差會越來越大。

4　結(jié)束語

本文針對到達時差定位系統(tǒng)，提出了一種基于SDR的定位算法，該方法將關(guān)于目標(biāo)位置求解的非凸優(yōu)化問題松弛為一個可以有效求解的半定規(guī)劃問題，并且在仿真中發(fā)現(xiàn)松弛后的優(yōu)化問題總是能夠得到原問題的最優(yōu)解，這就證實了該方法的有效性、穩(wěn)定性和實用性。■

[1]Carter GC.Coherence and time delay estimation: an applied tutorial for research, development, test, and evaluation engineers[C].New York: IEEE, 1993.

[2]Ilyas M, Mahgoub I.Handbook of sensor networks: compact wireless and wired sensing systems[M].London, UK: CRC Press, 2005.

[3]So HC.Source localization: algorithms and analysis[M]∥Handbook of Position Location: Theory, Practice and Advances.Wiley-IEEE Press, 2011.

[4]任源博.多星時差無源定位系統(tǒng)研究[D].西安電子科技大學(xué),2014.

[5]Cheung KW, So HC, Ma WK, et al.A constrained least squares approach to mobile positioning: algorithms and optimality[J].EURASIP Journal on Advances in Signal Processing, 2006:1-23.

[6]Chan KW, So HC, Ma WK, et al.A flexible semi-definite programming approach for source localization problems[J].Digital Signal Processing, 2013,23:601-609.

[7]Luo ZQ，Ma WK． Semi-definite relaxation of quadratic optimization problems[J]． IEEE Signal Processing Magazine,2010，27(3):20-34．

[8]So HC.Source localization :algorithms and analysis[D]．Department of Electronic Engineering, City University of Hong Kong,2012:44-48.

TDOA location method based on the semi-definite relaxation

Wu Gai

(Key Laboratory of Electronic Information Countermeasure and Simulation,Ministry of Education, Xidian University, Xi’an 710071, Shanxi, China)

A new TDOA location method based on the semi-definite relaxation is proposed.Firstly, the distance measuring error is a very significant parameter to be utilized to establish a nonconvex optimization problem about localization estimation.Then, the nonconvex optimization problem is converted to the equivalence convex optimization problem, and the target localization is solved by using semi-definite relaxation programming method based on convex optimization method.Simulation results show that the proposed approach is effective.

TDOA; convex optimization; semi-definite relaxation; location error

2015-06-15

吳蓋，男，碩士，主要研究方向為定位技術(shù)。

TN971

A