周恭謙, 楊露菁, 劉 忠, 彭業(yè)飛

(海軍工程大學電子工程學院, 湖北 武漢 430033)

基于TDOA的基站布局對定位精度影響分析*

周恭謙, 楊露菁, 劉 忠, 彭業(yè)飛

(海軍工程大學電子工程學院, 湖北 武漢 430033)

對基于TDOA的定位方程進行分析,通過對其進行微分運算,求解出定位誤差關于基站目標方位角的非線性函數(shù),分析函數(shù)找出了影響定位精度的具體要素。此外針對非線性函數(shù)求解困難的問題提出一種混沌雙擾動粒子群算法(CDDPO)對該函數(shù)求解,當待測目標位置發(fā)生變化時該算法能夠迅速找出滿足定位誤差最小的基站布局,總結歸納了使誤差最小時的定位基站布局的特點。最后通過實例驗證了結論的正確性。

基站布局;定位精度;混沌雙擾動粒子群算法;時差定位;微分運算

TDOA即到達時間差,是指無線射頻信號同一時刻到達兩個基站的時間差。TDOA技術是一種無線定位技術,是根據(jù)無線射頻信號到達兩個基站之間的距離差來定位的一種技術[1]?；赥DOA的定位方法主要是通過測量經(jīng)待測目標發(fā)射信號到達不同基站的到達時間差來實現(xiàn)的,該方法不要求待測目標和基站之間的時間同步,但是要求各個基站之間必須同步,保證同一時刻下信號源到達各個基站之間的時間差是個定值,時間差與光速的乘積就是距離差。根據(jù)求解雙曲線的算法可知,為了確定待測的位置,至少需要兩條相交的雙曲線才可以確定,雙曲線的交點處就是信號源的位置估計值。因此,要確定待測目標的位置則至少需要用三個基站[2]。相比傳統(tǒng)的定位方法，TDOA有以下優(yōu)點[3]:1)TDOA 不存在相位模糊的問題,因此測向基線可以不受限制；2)TDOA 系統(tǒng)復雜度低；3)TDOA 系統(tǒng)定位的精度較高。因此，基于TDOA的時差定位技術在目標定位方面得到了廣泛的應用,本文對TDOA定位方程進行研究,分析影響定位精度的要素,并通過尋優(yōu)求解找出了滿足待測目標誤差最小時對應的基站最優(yōu)布局。

1 基站布局對定位精度影響分析

以三站為例，基于TDOA對待測目標(x,y)的定位方程為:

(1)

其中：(x1,y1)為中心基站,(x2,y2),(x3,y3)為副站的位置,R1,2,R1,3分別為中心基站和兩個副站之間的距離差。

對方程(1)進行微分有:

(2)

圖1 定位基站與待測目標連線角度關系示意圖

(3)

上式可簡化為dR=TdZ。

解上式可得dZ=T-1dR，即

(4)

(5)

求解式(5)可得

(6)

則定位誤差E可表示為

(7)

又由圖1可知β1=α2-α1,β2=α1-α3則(式7)可表達為

(8)

由圖1可知

由式(8)可知：當測距誤差一定的情況下,影響定位精度的因素是定位基站和目標所成的方位角,當出現(xiàn)α1=α2=α3中任意一種情況時目標的位置不可測,即定位基站的布設不應出現(xiàn)位置重合或接近,同時避免目標出現(xiàn)在任意兩站的連線的延長線上。由式(8)可知：當β1=π,β2=π,β1+β2=π同時滿足時誤差最小,顯然這是不可能的,這三者之間是一種互相影響互相約束的關系,所以待測目標與兩個基站之間夾角對定位誤差的影響不能單獨進行研究判斷。而對于式(8)的求解是個非線性最優(yōu)化問題,粒子群算法被廣泛應用于這方面,但該算法初期收斂很快,后期易陷入局部最優(yōu)點。針對其存在的缺陷性,混沌粒子群算法被提出并廣泛應用,其將粒子群算法在全局搜索上的快速性和混沌算法在一定范圍內(nèi)的遍歷性相結合,提高了搜索的精度。下文提出一種雙擾動的混沌粒子群算法,通過仿真與混沌算法對比證明了該方法能夠有效地提高收斂速度,提高尋優(yōu)能力,并使用該方法求解待測目標定位誤差的最小值時各基站布設位置的坐標值。

2 基于混沌雙擾動粒子群算法的優(yōu)化基站布局

2.1 基于Logistic映射的混沌粒子群算法

利用混沌的遍歷性和隨機性[4]在智能算法進行優(yōu)化搜索已發(fā)展成為一種高效的全局優(yōu)化技術,促使了混沌廣泛應用于各個學科領域。

混沌引入到粒子群算法的方法有多種,文獻[5-6]利用混沌改善速度更新式子,這些方法基本上是利用了混沌技術的遍歷性,使速度更新時具有遍歷性效果。這種算法是為了提高算法的搜索能力。主要有以下兩種速度更新公式:

Vid(k+1)=wVid(k)+c1χ(Pid(k)-Xid(k))+

c2(1-χ)(Pgd(k)-Xid(k))

(9)

Vid(k+1)=wVid(k)+c1χ1(Pid(k)-Xid(k))+

c2χ2(Pgd(k)-Xid(k))

(10)

其中，參數(shù)ω表示慣性權重因子,c1和c2為加速常數(shù),也稱為學習因子(通常取c1=c2=2),r1和r2為兩個介于(0,1)范圍內(nèi)變化的相互獨立的隨機函數(shù)。為避免粒子盲目搜索,一般將其速度和位置限制在一定空間[Vmin,Vmax]、[Xmin,Xmax]內(nèi)。式(9)、(10)中的χ序列由式(11)產(chǎn)生,即利用Logistic方程產(chǎn)生的混沌序列代替隨機數(shù)rand。

χk+1=μχk(1-χk)

(11)

目前,大多數(shù)學者采用基于Logistic映射。文獻[7]提出了基于Logistic映射的混沌粒子群算法:第一階段稱為粗搜索階段,先采用基于Logistic迭代映射遍歷整個解集空間,當達到所求問題的相應條件(迭代次數(shù)限制)時, 即把當前解默認為接近問題的最優(yōu)解;第二階段稱為細搜索階段,以第一階段的結果為中心附加混沌擾動,進行精確細致搜索,直至滿足算法終止準則。

2.2 基于Tent映射的混沌雙擾動粒子群算法(CDDTPSO)

雖然本文提出的基于Logistic映射的混沌粒子群算法改進能在一定程度上提高算法的搜索精度,但是由于Logistic映射混沌的序列主要集中分布在兩端,中間區(qū)域所獲分配不多,如果最優(yōu)解落在中間部分,則算法便會偏離最優(yōu)解的范圍以致無法得到全局最優(yōu)解。相對Logistic映射而言,Tent映射序列分布具有全局遍歷性,且較為均勻,對初值不敏感等優(yōu)點。

基于Logistic映射存在的上述缺點,本文在基于Tent映射[7]基礎上加入雙擾動的思想,提出混沌雙擾動粒子群算法(chaotic double disturbance Particle Swarm Optimization,CDDPSO)。Tent映射也稱帳篷映射,其表達式為

(12)

基于混沌雙擾動的粒子群算法主要步驟為:

步驟1 混沌初始化。設定變量的取值范圍[xmin,j,xmax,j],群體規(guī)模m,變量維度D。利用Tent映射(μ=0.5)生成i個混沌序列zij(i=1,2,…m,j=1,2,…D),將混沌序列zij通過式(4)線性映射到優(yōu)化變量:

xij=xmin,j+(xmax,j-xmin,j)·zij

(13)

xij即為m個初始粒子種群。

步驟2 計算種群適應度。將粒子的目前位置記為Pbest,群體中適應度最優(yōu)的粒子位置記為Gbest。

步驟3 利用粒子群速度公式更新粒子速度和位置,重新計算新粒子的適應度,并判斷是否更新粒子的個體極值以及群體的全局極值。

步驟4 公告板記錄。記錄每次迭代產(chǎn)生的群體極值,稱為公告板。并設定一個閾值T,如果公告板連續(xù)T次迭代沒有更新,則轉步驟5;否則轉步驟6。

步驟5 混沌一次擾動。當前群體極值的混沌擾動公式為[8]:

(14)

(15)

步驟6 判斷是否滿足迭代結束條件(達到最大迭代次數(shù)),若滿足,輸出結果,終止算法;否則,轉步驟7。

步驟7 早熟收斂判決。判決公式為:

(16)

步驟8 混沌二次擾動。利用式(17)和式(18)對早熟的粒子進行混沌擾動,

(17)

X*=ψ*(xmax,j-xmin,j)+xmin,j

(18)

2.3 算法測試

由圖2和圖3可以看出,相對于現(xiàn)有的混沌粒子群算法,本文采用的CDDPSO算法在經(jīng)過若干代運算之后仍保持較高的活性,可以從局部最優(yōu)中跳離出來,保持較快的收斂速度,極大地提高了對最優(yōu)值的全局搜索能力。

圖2 Griewank函數(shù)尋優(yōu)曲線

2.4 基于改進的混沌粒子群算法優(yōu)化的基站定位布局

圖3 Rastrigrin函數(shù)尋優(yōu)曲線

以中心基站為坐標原點,兩個副站在以中心基站為圓心,半徑為10km的圓上,測距誤差定義為7m,將坐標系中隨機生成坐標點作為待測目標的位置節(jié)點,使用改進的混沌粒子群算法對式(7)進行求解,并尋找達到最小誤差時各基站的坐標,改進混沌粒子群算法具體參數(shù)參考上文2.3節(jié)設置。隨機生成的點及此時最優(yōu)定位基站布局如圖4-圖13所示,具體實驗數(shù)據(jù)參考表1,其中(X1,Y1)表示中心基站坐標,本文使其固定在原點,(X2,Y2)(X3,Y3)分別兩副站坐標,(XX,YY)表示待測目標坐標,夾角表示兩副站和中心基站所圍成的角度,δ2表示定位誤差的平方值,斜率積代表中心基站和待測目標連線的斜率和兩副站兩線斜率的乘積。從表1可以看出，隨著待測目標的位置不同基站的最優(yōu)布局是不同的,隨著距離的增加最優(yōu)布局的基站夾角逐漸增大,且定位誤差也逐漸增大。但可以看出，最優(yōu)布局的基站拓撲結構始終保持著中心基站和待測目標的連線和兩副站連線是垂直的。由此可知,在固定的區(qū)域內(nèi),對待測目標定位精度最高的定位基站布局要滿足是等腰三角形結構且待測目標和中心基站的連線和兩副站連線垂直。

表1 最小誤差時基站最優(yōu)布局結構數(shù)據(jù)表

圖4 隨機點的最優(yōu)基站布局示意圖

圖5 隨機點的最優(yōu)基站布局示意圖

圖6 隨機點的最優(yōu)基站布局示意圖

圖7 隨機點的最優(yōu)基站布局示意圖

圖8 隨機點的最優(yōu)基站布局示意圖

圖9 隨機點的最優(yōu)基站布局示意圖

圖10 隨機點的最優(yōu)基站布局示意圖

圖11 隨機點的最優(yōu)基站布局示意圖

圖12 隨機點的最優(yōu)基站布局示意圖

圖13 隨機點的最優(yōu)基站布局示意圖

3 實例驗證

上節(jié)提出的當待測目標位置確定時,定位基站保持等腰三角形且中心基站和待測目標連線和兩副站之間連線垂直是使誤差達到最小的條件。本節(jié)基于實例對結論進行驗證,對比在等腰三角形(中心基站待測目標連線和兩副站連線垂直)和偏三角形(中心基站待測目標連線和兩副站連線不垂直)情況下定位誤差,驗證上文提出結論的正確性。在某實際實驗環(huán)境中按照一定的拓撲結構布設三個定位基站,本實驗以觀測區(qū)圓心為原點,定位基站分別按照(-50m,0)、(50m,0)、(0,-50m)等腰三角結構和(-50m,0)、(50m,0)、(-29.678m,-40.121m)偏三角結構進行布設,并在距離觀測區(qū)圓心不同距離(0～1000m范圍內(nèi))位置設置多個測試點(如圖14“☆”所示),本實驗中取距觀測區(qū)0m、50m、100m、200m、400m的測試點進行靜態(tài)試驗測量出測試點的真實局部坐標。

1)定位基站成等腰三角結構布設

圖14 定位基站成等腰三角布設拓撲態(tài)勢圖

去掉由于定位基站信號通信問題造成測得偏差較大的野值,此時試驗測得的不同距離情況下坐標散布圖如圖15-18所示。

圖15 等腰三角布設距離為0m時坐標散布圖

圖16 等腰三角布設距離為100m時坐標散布圖

圖17 等腰三角布設距離為200m時坐標散布圖

圖18 等腰三角布設距離為400m時坐標散布圖

試驗結果如表2所示。

表2 等腰三角結構布設時不同距離下定位結果分析

2)定位基站成偏三角結構布設如圖19所示。

圖19 定位基站成偏三角布設拓撲態(tài)勢圖

試驗測得不同距離情況下坐標散布圖如圖20-22所示。

圖20 偏三角布設距離為100m時坐標散布圖

圖21 偏三角布設距離為200m時坐標散布圖

圖22 偏三角布設距離為400m時坐標散布圖

試驗結果如表2所示。

表3 偏三角形結構布設時不同距離下定位結果分析

將定位基站按等腰三角形拓撲結構布設的定位結果與偏三角形拓撲結構作對比,如表4所示。

表4 不同拓撲結構布設時定位誤差對比

通過上述實驗可知,在待測目標位置一定的情況下中心基站和待測目標連線與兩副站連線的等腰三角形定位誤差比中心基站和待測目標連線與兩副站連線不垂直的偏三角形定位誤差小,且隨著待測目標和定位基站距離增加定位誤差增大,證明了上文結論的正確性。

4 結束語

本文對基于TDOA的基站最優(yōu)布局進行分析,對TDOA方程進行微分運算,得出了關于定位誤差與基站和待測目標連線水平角的非線性函數(shù),并采用一種改進的混沌粒子群算法對該函數(shù)尋優(yōu),找出了滿足最小定位誤差時最優(yōu)基站布局中各基站的坐標,總結歸納了最優(yōu)布局時定位基站拓撲結構的特點,最后通過實例仿真驗證了結論的正確性。

[1] 孫勝,李輝.基于TDOA定位技術的仿真研究[J].無線通信技術, 2002,11(4)：40-43.

[2] 馬靈芝.基于TDOA無線傳感定位算法的研究及應用[D].濟南：山東大學,2012.

[3] 俞一鳴,姚遠.程學虎.TDOA 定位技術和實際應用簡介[J].中國無線電，2013(11):57-58

[4] Zhang L,Zhang F,Wu Q,et al.Simulatable certificate-less two-party authenticated key agreement protocol[J].Information Sciences,2010,180(2):1020-1030.

[5] MacQueen J. B. Some Methods for classification and Analysis of Multivariate Observations[C]. Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1967:281-297.

[6] Blake-Wilson S,Johnson D,Menezes A. Key agreement protocols and their security analysis[C]∥Darnell M.LNCS 1355:Proc of the 6th IMA International Conference on Cryptography and Coding.Berlin/Heidelberg:Springer-Verlag,1997:30-45.

[7] Hong li Xu,Xu Qian, liang Zhang. Study of ACO Algorithm Optimization Algorithm Based on Improved Tent Chaotic Mapping Journal of Information &Computational Science.2012(6):1653-1660.

Analysis of the Influence of Base Station Layout on Location Accuracy Based on TDOA

ZHOU Gong-qian, YANG Lu-jing, LIU Zhong, PENG Ye-fei

(School of Electronic Engineering, Naval University of Engineering, Wuhan 430000,China)

Positioning equation based on TDOA is analyzed, the nonlinear function of position error on target azimuth of station is solved by the differential operation of the equation, the specific factor which affects the positioning accuracy is found out by analysis of function. In addition, an chaotic double disturbance particle swarm optimization algorithm is put forward to solve the function for the problem that nonlinear function is difficult to solve, the algorithm can quickly find the base station layout which satisfies the minimum position error when the target position is changed, and the features are summarized which meet the minimum positioning error of the base station layout. Finally the conclusion is verified by an example.

base station layout; positioning accuracy; chaotic double disturbance particle swarm optimization algorithm (CDDPSO); TDOA; differential operation

1673-3819(2017)06-0119-08

TN966；E917

A

10.3969/j.issn.1673-3819.2017.06.025

2017-03-20

2017-04-07

國家863計劃項目(2013AA7014061)；總裝預研基金(9140A01060113JB11001)

周恭謙(1988-),男,博士研究生,研究方向為模式識別、智能系統(tǒng)。楊露菁(1966-),女,博士生導師。劉 忠(1963-),男,博士生導師。