吳　蓋

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

?

·工程應用·

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

吳蓋

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

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

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

0　引言

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

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

1　問題描述

假設時差定位系統(tǒng)共有L(L≥4)個觀測站，各觀測站的坐標為：Xl=[xlyl]T,l=1,2,…,L。以觀測站X1作為整個時差定位系統(tǒng)的參考站。目標輻射源的位置為X=[xy]T。目標輻射源同各個觀測站之間的徑向距離記為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有關。

(14)

式中，R=XTX。

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

(15)

(16)

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

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

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

(17)

(18)

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

3　仿真實驗

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

圖1　觀測站及目標的位置

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

圖2　對近場目標的定位RMES曲線

圖3　對遠場目標的定位RMES曲線

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

4　結束語

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

[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].西安電子科技大學,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

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

TN971

A