基于并行分層時(shí)間間隔測(cè)量的TDOA定位算法研究

鄒東堯，劉碧微，楊 威，向家鈺

(1.鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院，河南 鄭州 450001;2.中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230026)

?

基于并行分層時(shí)間間隔測(cè)量的TDOA定位算法研究

鄒東堯1，劉碧微1，楊 威1，向家鈺2

(1.鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院，河南 鄭州 450001;2.中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230026)

基于到達(dá)時(shí)間差(TDOA)定位算法要求精確地時(shí)間同步技術(shù)作為支撐.由于傳統(tǒng)時(shí)間同步技術(shù)精度低導(dǎo)致TDOA定位結(jié)果有偏差，提出一種基于并行分層次時(shí)間間隔測(cè)量的到達(dá)時(shí)間差(TDOA)和到達(dá)信號(hào)增益比(GROA)聯(lián)合定位算法.基于TDOA與GROA聯(lián)合定位模型，構(gòu)造含拉格朗日系數(shù)的優(yōu)化函數(shù)，然后采用約束加權(quán)最小二乘算法(TSWLS)來(lái)進(jìn)行求解；同時(shí)，采用并行分層時(shí)間間隔測(cè)量法來(lái)控制定位算法的時(shí)間同步.實(shí)驗(yàn)分析表明，該算法相比較傳統(tǒng)的TDOA定位算法而言，定位精度提高了25 dB，并且具有相對(duì)較高和較穩(wěn)定的定位精度.

時(shí)間同步；到達(dá)時(shí)間差(TDOA)；到達(dá)信號(hào)增益比(GROA)；最小二乘；并行分層測(cè)量

節(jié)點(diǎn)定位在整個(gè)傳感器網(wǎng)絡(luò)中占有重要的地位，在事件觀測(cè)、目標(biāo)跟蹤、網(wǎng)絡(luò)重構(gòu)等方面都是不可缺少的環(huán)節(jié)[1-2].一般常見(jiàn)的無(wú)源定位方法是利用諸如到達(dá)時(shí)間(time of arrival,TOA)、到達(dá)時(shí)間差(time difference of arrival，TDOA)、波達(dá)角(angle of arrival，AOA)等測(cè)量參數(shù)或者它們的組合來(lái)實(shí)現(xiàn)目標(biāo)的定位.常用的基于接收信號(hào)能域信息的定位方法有接收信號(hào)強(qiáng)度定位方法RSSI(Receive Signal Strength Indicator)[3-5]和到達(dá)信號(hào)增益比定位方法GROA(Gain Ratio of Arrival)[6-8].TDOA定位技術(shù)是利用發(fā)射端發(fā)射信號(hào)與接收端接收信號(hào)的時(shí)間差進(jìn)行測(cè)距，所以要求有精確地同步時(shí)鐘.時(shí)間同步是指兩頻率信號(hào)之間的時(shí)間差被消除或被最小化處理，并且處理后的時(shí)間差值不會(huì)隨時(shí)間的變化而變化.高進(jìn)度的時(shí)間同步不僅在地球動(dòng)力學(xué)、脈沖周期、相對(duì)論以及人造衛(wèi)星動(dòng)力學(xué)測(cè)地等基礎(chǔ)研究方面有著重要的作用，而且在航空航天、導(dǎo)航定位衛(wèi)星發(fā)射等領(lǐng)域也具有極其重要的地位[9-10].時(shí)間同步離不開(kāi)短時(shí)間間隔的測(cè)量，然而傳統(tǒng)的時(shí)間間隔測(cè)量方法存在測(cè)量范圍寬，但是測(cè)量精度不高的問(wèn)題.RSSI定位技術(shù)因符合低功率、低成本的要求在多傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中應(yīng)用廣泛，但這些條件在無(wú)源定位中是不滿足的，所以RSSI定位方法在被動(dòng)定位中無(wú)法適用.GROA定位不需要事先已知待定位目標(biāo)的信號(hào)發(fā)射功率和信號(hào)傳播的路徑損耗模型，僅利用目標(biāo)信號(hào)在自由空間傳播時(shí)，接收站接收到目標(biāo)信號(hào)的幅度與傳播距離成反比[6]的原理來(lái)對(duì)目標(biāo)進(jìn)行定位，更適用于無(wú)源定位.

GROA的定位方法首先由K.C.Ho等人在文獻(xiàn)[6]中提出.他們提出同時(shí)利用GROA和TDOA測(cè)量信息的兩步加權(quán)最小二乘(two step weighted least square，TSWLS)無(wú)源定位方法，并且文獻(xiàn)[6]指出在這種混合體制的定位方法中，隨著信號(hào)帶寬的減小，GROA對(duì)定位精度的改善起到了關(guān)鍵的作用.在此基礎(chǔ)上文獻(xiàn)[7]提出了在傳感器位置有誤差條件下的TDOA和GROA多信號(hào)源兩步加權(quán)最小二乘被動(dòng)定位方法，并指出利用GROA定位信息需要精確測(cè)量出所使用環(huán)境的傳播系數(shù).文獻(xiàn)[8]在文獻(xiàn)[7]的基礎(chǔ)上，給出了BiasRed法與BiasSub法兩種偏差消減算法來(lái)進(jìn)一步提升TDOA和GROA聯(lián)合定位精度.

因此，本文主要考慮接收傳感器存在位置誤差以及定位結(jié)果易受干擾的問(wèn)題，聯(lián)合時(shí)域TDOA定位信息與能量域GROA定位信息，對(duì)信號(hào)源進(jìn)行協(xié)同定位.同時(shí)TDOA與GROA定位要求精確地時(shí)間同步，本文提出一種基于并行時(shí)間間隔的時(shí)間同步測(cè)量，最后采用優(yōu)化粒子群算法計(jì)算定位最優(yōu)值.首先，基于TDOA與GROA定位模型提出了含有拉格朗日系數(shù)的優(yōu)化函數(shù)，采用約束加權(quán)最小二乘算法來(lái)進(jìn)行迭代求解；同時(shí)，利用并行分層時(shí)間間隔測(cè)量法來(lái)確保TDOA與GROA定位的時(shí)間同步；最后通過(guò)計(jì)算機(jī)仿真驗(yàn)證本文算法在不同的參數(shù)條件下的定位效果，實(shí)驗(yàn)結(jié)果均表明，本文提出的算法相比TDOA算法魯棒性好，定位精度高.

1 TDOA與GROA定位方法

1.1 TDOA定義

接收傳感器收到的信號(hào)源發(fā)射的信號(hào)定義為：

(1)

其中i=2,3,…，M.s(t)表示目標(biāo)發(fā)射信號(hào)，ξi(t)表示第i個(gè)接收傳感器的信號(hào)接收噪聲，xi(t)為第i個(gè)接收傳感器接收到的信號(hào).不失一般性，以第一個(gè)接收傳感器作為參考節(jié)點(diǎn).

將時(shí)差值乘以信號(hào)傳播速度c得到目標(biāo)到第i個(gè)傳感器和到傳感器1的到達(dá)距離差(RDOA).則第i個(gè)傳感器與目標(biāo)之間的距離可以表示為：

(2)

其中‖*‖表示歐氏距離，i=2,3,…，M，則目標(biāo)到第i個(gè)傳感器和第1個(gè)傳感器之間的距離差為：

(3)

r=r′+Δr

(4)

假設(shè)時(shí)差誤差滿足零均值高斯分布，其協(xié)方差矩陣為E[ΔrΔrT]=Qr.

1.2 GROA定義

(5)

為方便表示，GROA參數(shù)可寫(xiě)為向量形式：g=[g21,g31,…,gM1]T，Δg=[Δg21,Δg31,…,ΔgM1]T.進(jìn)一步，到達(dá)增益比測(cè)量方程：

g=g′+Δg

(6)

其中：gi1為實(shí)際GROA測(cè)量值，Δgi1為GROA測(cè)量誤差值.假設(shè)其滿足零均值高斯分布，并獨(dú)立于時(shí)差測(cè)量誤差，其協(xié)方差矩陣為E[ΔgΔgT]=Qg.

2 基于并行分層時(shí)間間隔測(cè)量的TDOA和GROA定位方法

本文主要研究基于時(shí)差(TDOA)和增益比(GROA)聯(lián)合的定位問(wèn)題.已知定位方程與目標(biāo)位置之間的非線性關(guān)系，那么實(shí)現(xiàn)目標(biāo)位置的直接求解難度較大.目前針對(duì)這一非線性方程求解問(wèn)題主要有兩大類方法：一是泰勒級(jí)數(shù)展開(kāi)方法[11]，即通過(guò)在目標(biāo)真實(shí)位置附近將非線性方程進(jìn)行泰勒級(jí)數(shù)展開(kāi)，并舍去二階以上高次項(xiàng)，得到線性方程，并通過(guò)多次迭代逼近目標(biāo)的真實(shí)位置；二是通過(guò)引入輔助變量[12]，將非線性方程偽線性化，再求解偽線性方程獲得目標(biāo)的位置信息.第一類方法往往要求一個(gè)較為精確的迭代初始值，并不能夠保證完全收斂到真實(shí)位置處.第二類方法在一定條件下具有閉式解，且不存在發(fā)散問(wèn)題.典型的算法有兩步加權(quán)最小二乘(two-step weighted least-squares，TSWLS)算法[13]、約束加權(quán)最小二乘(constrained weighted least squares，CWLS)算法[14]等，其中，TSWLS算法運(yùn)算量最小，CWLS、CTLS算法利用最小二乘(least squares，LS)解作為初始解，在利用迭代算法獲得目標(biāo)位置.

本文利用以上思想，本文提出了基于TDOA與GROA聯(lián)合定位算法，并采用基于并行分層時(shí)間間隔測(cè)量的方法來(lái)確保高精度的定位時(shí)間同步，最后采用優(yōu)化粒子群算法計(jì)算最優(yōu)值.利用Matlab仿真工具，通過(guò)與傳統(tǒng)的TDOA定位算法相比較，來(lái)驗(yàn)證本文算法的性能.

圖1 TDOA和GROA聯(lián)合定位示意圖Fig.1 The localization layout of TDOA and GROA

2.1 定位場(chǎng)景分布

圖1為基于接收傳感器時(shí)差測(cè)量值(TDOA)和接收信號(hào)到達(dá)增益比(GROA)聯(lián)合定位示意圖.

2.2 建立定位方程

(7)

將式(2)帶入式(7)并兩邊平方，可以得到：

(8)

(9)

(10)

(11)

(12)

通過(guò)從1989年～2011年，2012年～2017年兩個(gè)不同時(shí)段對(duì)我國(guó)信息素養(yǎng)主題研究論文進(jìn)行統(tǒng)計(jì)分析，特別是近6年來(lái)的研究現(xiàn)狀，可以發(fā)現(xiàn)以下幾點(diǎn)。

(13)

由式(13)及式(9)可以得到:

(14)

(15)

(16)

(17)

其中：

(18)

根據(jù)誤差關(guān)系可得：

εt=B11Δr+C11Δg+D11Δβ

(19)

(20)

(21)

其中，O為3×1維全零向量.

同理，記εg=[εg,2,εg,3,…,εg,M]T，則:

(22)

其中：

(23)

根據(jù)誤差關(guān)系可得：

εg=B12Δr+C12Δg+D12Δβ

(24)

(25)

(26)

其中：I(M-1)×(M-1)為M-1維單位矩陣，0為3×1維全零向量.

由于測(cè)量誤差、站址誤差的存在，TDOA、GROA參數(shù)測(cè)量結(jié)果存在誤差，式(17)、(24)不為0.

(27)

(28)

又知:

εtg=BtgΔr+CtgΔg+DtgΔβ

(29)

(30)

構(gòu)造最小化目標(biāo)函數(shù):

(31)

其中W為加權(quán)矩陣:

(32)

則:

(33)

引入式(15)的約束條件，求解目標(biāo)位置即為在滿足式(31)和式(15)的約束條件下，求解目標(biāo)位置u，使得εtg的范數(shù)平方最小化，數(shù)學(xué)上可表示為:

(34)

首先利用u′Tu′=(a+h)2，可以得到引入約束信息的最小化目標(biāo)函數(shù):

(35)

其中λ1、λ2為拉格朗日(Lagrange)系數(shù).式(35)中L(u,λ1,λ2)即為所構(gòu)造的優(yōu)化函數(shù).

2.3 求解拉格朗日系數(shù)

(36)

(37)

(38)

(39)

(40)

(41)

將式(41)帶入式(36)可得:

(42)

將式(41)和式(42)帶入式(40)可得:

(43)

2.4 優(yōu)化粒子群算法算法

為確保定位算法的準(zhǔn)確精度，本文采用并行間隔來(lái)作為時(shí)間同步測(cè)量支撐，并采用優(yōu)化的粒子群算法計(jì)算定位的最優(yōu)值.文在粒子群優(yōu)化算法的基礎(chǔ)上，引入了隨機(jī)性的Levy飛行機(jī)制來(lái)調(diào)節(jié)粒子的運(yùn)動(dòng)軌跡，這樣不僅有助于跳出局部最優(yōu)，且當(dāng)粒子在全局最優(yōu)附近時(shí)得到較好的收斂性.其主要作用在于當(dāng)粒子在局部最優(yōu)附近進(jìn)行小范圍的移動(dòng)時(shí)，會(huì)突然給出一個(gè)較大步長(zhǎng)的跳變使其跳出局部最優(yōu).在d維的空間下，粒子在t時(shí)刻改進(jìn)后的速度V和位置X更新的公式為：

vd(t+1)=vd(t)+c1*(Pi(t)-xd(t))+c2*(Pg(t)-xd(t))

(44)

xd(t+1)=xd(t)+vd(t+1)+α*sign(rand-0.5)*levy(λ)

(45)

具有Levy飛行機(jī)制的粒子群算法的具體步驟如下：

1)對(duì)每個(gè)粒子進(jìn)行初始化，設(shè)定種群大小，根據(jù)方程需要，隨機(jī)生成各個(gè)粒子在設(shè)定維度下的初始解和速度值；

2)根據(jù)適應(yīng)度方程，計(jì)算各個(gè)粒子的適應(yīng)度值，并選出各個(gè)粒子的個(gè)體最優(yōu)值，比較各個(gè)粒子的最優(yōu)值確定粒子的全局最優(yōu)值；

3)按照上面給出的式(44)，更新各個(gè)粒子的速度，并把速度限定在一定的范圍內(nèi)；

4)按照上面給出的式(45)，更新各個(gè)粒子的位置信息，并把位置限定在適應(yīng)度函數(shù)所給的定義域內(nèi)；

5)當(dāng)?shù)玫降倪m應(yīng)度值達(dá)不到要求或者迭代次數(shù)達(dá)不到規(guī)定的迭代次數(shù)時(shí)，返回到(2).

3 實(shí)驗(yàn)及分析

(46)

其中：u(l)為第u′次蒙特卡洛仿真得到的目標(biāo)位置估計(jì)值，u′為目標(biāo)真實(shí)位置，L=5 000為獨(dú)立仿真運(yùn)行次數(shù).假設(shè)時(shí)差測(cè)量誤差的均方根為σt，且滿足σr=c·σt.圖2中σg=-20 dB，σs=-40 dB.圖3中σt=-60 dB，σs=-20 dB.圖4中σt=-60 dB，σg=-20 dB.

圖2 誤差隨時(shí)差測(cè)量誤差變化曲線圖Fig.2 The ranging error results with RDOA

圖3 誤差隨幅度比測(cè)量誤差變化曲線圖Fig.3 The ranging error results with GROA

圖4 誤差隨站址測(cè)量誤差變化曲線Fig.4 The ranging error results with distance

從圖2～4可以看出：

1)定位精度主要由TDOA和GROA測(cè)量誤差中較小的參數(shù)決定，另一個(gè)參數(shù)誤差變化對(duì)于定位結(jié)果的影響不明顯；

2)引入并行分層時(shí)間間隔測(cè)量法后，在相同的參數(shù)測(cè)量誤差條件下，本文提出的定位模型相比較TDOA模型大約可以提高25 dB，誤差減少較為明顯；

3)文算法在參數(shù)測(cè)量誤差以及位置測(cè)量誤差較小時(shí)，均方根誤差都在-4 dB附近，且波動(dòng)幅度變化不明顯.

4 結(jié)論

本文提出了一種基于并行分層時(shí)間間隔測(cè)量的TDOA和GROA定位算法，引入含有約束條件下的兩步加權(quán)最小二乘法來(lái)求解定位結(jié)果與目標(biāo)方程之間的非線性關(guān)系.仿真和實(shí)驗(yàn)結(jié)果表明，特別是在參考節(jié)點(diǎn)有限制和抗干擾能力差的情況下，本文提出的定位算法相比TDOA算法有更為精確的定位性能.因此，本文算法相比其它改進(jìn)的TDOA算法而言，不僅采用含有約束信息的最小二乘法來(lái)求解優(yōu)化定位方程，而且同時(shí)克服傳統(tǒng)時(shí)間同步的缺點(diǎn)，引入多層次間隔測(cè)量提高時(shí)間同步的精度，因此更適用于多節(jié)點(diǎn)和大規(guī)模的無(wú)線傳感網(wǎng)絡(luò).

[1] HO K C.Bias Reduction for an Explicit Solution of Source Localization Using TDOA[C]//IEEE Trans Signal Process,2012,60(5):2101-2114.

[2] CARTER G C.Bi-iterative method for moving source localization using TDOA and FDOA measurements[C]//ELECTRONICS LETTERS,2015,51(1):8-10.

[3] 劉志先，趙榮陽(yáng).基于RSSI的室內(nèi)定位改進(jìn)算法[J].廣西科學(xué)院學(xué)報(bào),2015,31(1):69-72.

[4] HO K C,LU X,Kovavisaruch L.Source localization using TDOA and FDOA measurements in the presence of receiver location errors: analysis and solution[C]//IEEE Trans Signal Process,2007,55(2):684-696.

[5] 譚志，張卉.無(wú)線傳感器網(wǎng)絡(luò)RSSI定位算法的研究與改進(jìn)[J].北京郵電大學(xué)學(xué)報(bào),2013,36(3):88-91.

[6] HO K C，SUN Ming.Passive Source Localization Using Time Differences of Arrival and Gain Ratios of Arrival[J].IEEE Transactions on Signal Processing,2008,56(2):464-477.

[7] 郝本建，李贊，任妘梅，等.基于TDOAs與GROAs的多信號(hào)源被動(dòng)定位[J].電子學(xué)報(bào),2012,40(12):2374-2381.

[8] HAO B J,LI Z,WAN P W,et al.Bias Reduction for Passive Source Localization Based on TDOA and GROA[J].Acta Ectronica Sinica,2014,42(3):477-484.

[9] TE L K,PARHI K K.Optimized joint timing synchronization and channel estimation for OFDM systems[J].IEEE Transactions on Wireless Communications Letters,2012,1(3):149-152.

[10] ABDZADEH-ZIABARI H,SHAYESTEH M G.Robust timing and frequency synchronization for OFDM Systems[J]. IEEE Transactions on Signal Processing,2011,59(1):5538-5557.

[11] FOY W H.Position location solution by Taylor-series estimation[C]//IEEE Trans Aerosp Electron Syst.,1976,AES-12,(2):187-194.

[12] HO K C,XU W W.An accurate algebraic solution for moving source location using TDOA and FDOA measurements[C]//IEEE Trans Signal Process,2004,52,(9): 2453-2463.

[13] MING SUN,HO K C.An asymptotically efficient estimator for TDOA and FDOA positioning of multiple disjoint sources in the presence of sensor location uncertainties[J].IEEE Transactions Signal Process,2011,59(7):3434-3440.

[14] YU H G,HUANG G M,GAO J,LIU B.An efficient constrained weighted least squares algorithm for moving source location using TDOA and FDOA measurements[J].IEEE Transactions Wireless Communications,2012,11(1):44-48.

責(zé)任編輯：高 山

The TDOA Localization Algorithm Based on Parallel
Hierarchical Measurement

ZOU Dongyao1,LIU Biwei1,YANG Wei1，XIANG Jiayu2

(1.School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450001,China;2.School of Mathematical Science,University of Science and Technology of China,Hefei 230026,China)

The precise time synchronization technology is required by the time difference of arrival (TDOA) positioning algorithm.Under the low precision of traditional time synchronization technology,this paper proposes a joint positioning algorithm gain ratio of arrival based on the TDOA and GROA of a parallel hierarchical time interval measurement.Firstly,we establish the optimization equation containing Lagrange coefficient based on TDOA and GROA joint positioning model.And then we solve the equation by constrained weighted least squares algorithm (TSWLS); at the same time,we use the method of parallel hierarchical time interval measurement to control the time synchronization of positioning model.The experiment and analysis show that the proposed algorithm accuracy increases by 25 dB compared with the traditional TDOA location algorithm,which has relatively stable and high positioning precision.

time synchronization;time differences of arrival (TDOA);gain ratios of arrival (GROA);least squares;parallel hierarchical measurement

2016-10-11.

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(15A520109)；河南省科技廳科技攻關(guān)項(xiàng)目 (112102210321)；河南省產(chǎn)學(xué)研合作項(xiàng)目 (122107000022)；研究生科技創(chuàng)新基金項(xiàng)目.

鄒東堯(1973- )，男，博士，副教授，主要從事物聯(lián)網(wǎng)、無(wú)線傳感網(wǎng)絡(luò)定位以及信息處理的研究.

1008-8423(2016)04-0435-07

10.13501/j.cnki.42-1569/n.2016.12.017

TP393

A