基于半定松弛的到達(dá)時(shí)差定位算法

吳　蓋

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

?

·工程應(yīng)用·

基于半定松弛的到達(dá)時(shí)差定位算法

吳蓋

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

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

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

0　引言

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

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

1　問(wèn)題描述

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

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

(1)

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

那么從TDOAs得來(lái)的徑向距離差為:

(2)

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

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

(3)

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

(4)

將式(4)寫(xiě)成矩陣形式[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)位置估計(jì)問(wèn)題可以描述為如下的優(yōu)化公式:

(15)

(16)

2　基于半定松弛的到達(dá)時(shí)差定位算法

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

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

(17)

(18)

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

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

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

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

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

圖2　對(duì)近場(chǎng)目標(biāo)的定位RMES曲線

圖3　對(duì)遠(yuǎn)場(chǎng)目標(biāo)的定位RMES曲線

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

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

本文針對(duì)到達(dá)時(shí)差定位系統(tǒng)，提出了一種基于SDR的定位算法，該方法將關(guān)于目標(biāo)位置求解的非凸優(yōu)化問(wèn)題松弛為一個(gè)可以有效求解的半定規(guī)劃問(wèn)題，并且在仿真中發(fā)現(xiàn)松弛后的優(yōu)化問(wèn)題總是能夠得到原問(wèn)題的最優(yōu)解，這就證實(shí)了該方法的有效性、穩(wěn)定性和實(shí)用性?！?/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]任源博.多星時(shí)差無(wú)源定位系統(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

吳蓋，男，碩士，主要研究方向?yàn)槎ㄎ患夹g(shù)。

TN971

A