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

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

?

基于并行分層時間間隔測量的TDOA定位算法研究

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

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

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

時間同步；到達時間差(TDOA)；到達信號增益比(GROA)；最小二乘；并行分層測量

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

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

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

1 TDOA與GROA定位方法

1.1 TDOA定義

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

(1)

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

將時差值乘以信號傳播速度c得到目標到第i個傳感器和到傳感器1的到達距離差(RDOA).則第i個傳感器與目標之間的距離可以表示為：

(2)

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

(3)

r=r′+Δr

(4)

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

1.2 GROA定義

(5)

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

g=g′+Δg

(6)

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

2 基于并行分層時間間隔測量的TDOA和GROA定位方法

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

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

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

2.1 定位場景分布

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

2.2 建立定位方程

(7)

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

(8)

(9)

(10)

(11)

(12)

通過從1989年～2011年，2012年～2017年兩個不同時段對我國信息素養(yǎng)主題研究論文進行統(tǒng)計分析，特別是近6年來的研究現(xiàn)狀，可以發(fā)現(xià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維全零向量.

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

(27)

(28)

又知:

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

(29)

(30)

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

(31)

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

(32)

則:

(33)

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

(34)

首先利用u′Tu′=(a+h)2，可以得到引入約束信息的最小化目標函數(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)化粒子群算法算法

為確保定位算法的準確精度，本文采用并行間隔來作為時間同步測量支撐，并采用優(yōu)化的粒子群算法計算定位的最優(yōu)值.文在粒子群優(yōu)化算法的基礎(chǔ)上，引入了隨機性的Levy飛行機制來調(diào)節(jié)粒子的運動軌跡，這樣不僅有助于跳出局部最優(yōu)，且當粒子在全局最優(yōu)附近時得到較好的收斂性.其主要作用在于當粒子在局部最優(yōu)附近進行小范圍的移動時，會突然給出一個較大步長的跳變使其跳出局部最優(yōu).在d維的空間下，粒子在t時刻改進后的速度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飛行機制的粒子群算法的具體步驟如下：

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

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

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

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

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

3 實驗及分析

(46)

其中：u(l)為第u′次蒙特卡洛仿真得到的目標位置估計值，u′為目標真實位置，L=5 000為獨立仿真運行次數(shù).假設(shè)時差測量誤差的均方根為σ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 誤差隨時差測量誤差變化曲線圖Fig.2 The ranging error results with RDOA

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

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

從圖2～4可以看出：

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

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

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

4 結(jié)論

本文提出了一種基于并行分層時間間隔測量的TDOA和GROA定位算法，引入含有約束條件下的兩步加權(quán)最小二乘法來求解定位結(jié)果與目標方程之間的非線性關(guān)系.仿真和實驗結(jié)果表明，特別是在參考節(jié)點有限制和抗干擾能力差的情況下，本文提出的定位算法相比TDOA算法有更為精確的定位性能.因此，本文算法相比其它改進的TDOA算法而言，不僅采用含有約束信息的最小二乘法來求解優(yōu)化定位方程，而且同時克服傳統(tǒng)時間同步的缺點，引入多層次間隔測量提高時間同步的精度，因此更適用于多節(jié)點和大規(guī)模的無線傳感網(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] 劉志先，趙榮陽.基于RSSI的室內(nèi)定位改進算法[J].廣西科學院學報,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ǎng)絡(luò)RSSI定位算法的研究與改進[J].北京郵電大學學報,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的多信號源被動定位[J].電子學報,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.

責任編輯：高 山

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.

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

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

1008-8423(2016)04-0435-07

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

TP393

A