陳光武， 佘一鳴， 楊菊花， 任 超

(1.蘭州交通大學(xué) 自動(dòng)控制研究所，甘肅 蘭州 730070；2.甘肅省高原交通信息工程及控制重點(diǎn)實(shí)驗(yàn)室，甘肅 蘭州 730070)

0 引 言

到達(dá)時(shí)間差(time difference of arrival,TDOA)技術(shù)在無(wú)源定位中具有對(duì)硬件要求低、不需要特定的時(shí)間戳要求以及精度較高的優(yōu)勢(shì)。目前對(duì)于TDOA問(wèn)題的研究有多種方法，一般來(lái)說(shuō)較為常見(jiàn)的有泰勒級(jí)數(shù)展開(kāi)法[1,2]，這種方法的缺點(diǎn)就是迭代初期的初值必須有一定的準(zhǔn)確度，否則容易出現(xiàn)算法不收斂的情況。此外，解決這類(lèi)問(wèn)題較為常見(jiàn)的還有最小二乘算法。例如：約束總體最小二乘法，順序最小二乘法等[3～5],這些算法也是處理定位問(wèn)題的傳統(tǒng)方法。這類(lèi)算法的優(yōu)勢(shì)在于速度快，計(jì)算量少，在噪聲較小時(shí)定位精度較高，是當(dāng)前研究較為成熟的方法。文獻(xiàn)[6]提出一種約束最小二乘法，針對(duì)約束最小二乘無(wú)源定位算法中最優(yōu) Lagrange乘數(shù)的求解問(wèn)題，提出了新的計(jì)算方法。2014年，曲付勇等人[7]提出的基于約束總體最小二乘法的方法，使非線性問(wèn)題轉(zhuǎn)變?yōu)閹Ъs束條件的最小二乘模型問(wèn)題，將約束最小二乘定位解作為約束總體最小二乘的定位解。以上這些針對(duì)最小二乘法的改進(jìn)方法雖然在噪聲較小時(shí)精度很高，但是卻有兩個(gè)顯著的不足：1)這類(lèi)算法在計(jì)算過(guò)程中含有求逆矩陣的步驟，為了使矩陣不出現(xiàn)奇異，必須通過(guò)增加觀測(cè)站來(lái)提升精確度，在三維情況中，在基礎(chǔ)原理上至少需要4個(gè)觀測(cè)站才可滿(mǎn)足條件，對(duì)于改進(jìn)算法所需的觀測(cè)站最少也得5個(gè)才可比較精確地找到位置；2)這類(lèi)方法只能用于噪聲較小的環(huán)境，否則就會(huì)出現(xiàn)門(mén)限效應(yīng)，從而導(dǎo)致精度大幅度下降。

除去上述的各種解析法以外，還有智能優(yōu)化算法被運(yùn)用到這一問(wèn)題的解決，2005年李俊峰等人[8]提出利用粒子群優(yōu)化算法去解決TDOA問(wèn)題。2017年劉寶生等人[9]提出利用遺傳優(yōu)化算法對(duì)時(shí)差問(wèn)題求解，但其算法的計(jì)算量較大。這類(lèi)使用智能優(yōu)化算法的方法首先在搜索范圍內(nèi)初始化大量的隨機(jī)點(diǎn)，通過(guò)建立符合要求的適應(yīng)度函數(shù)來(lái)篩選合適的隨機(jī)點(diǎn)，然后利用迭代過(guò)程在這些較好的隨機(jī)點(diǎn)中找出最優(yōu)解，這個(gè)解即為目標(biāo)位置。這種方法不存在矩陣求逆的過(guò)程，所以，對(duì)基站個(gè)數(shù)的要求較最小二乘的方法少。

目前使用智能算法處理TDOA問(wèn)題時(shí)一般會(huì)出現(xiàn)算法后期收斂太慢，陷入局部最優(yōu)解的問(wèn)題，還有一些智能算法的控制參數(shù)過(guò)多，不但加大了調(diào)整參數(shù)的難度而且還使得計(jì)算速度減慢，所以，找到一種針對(duì)這類(lèi)問(wèn)題的合適的智能算法顯得十分重要。

2016年，澳大利亞學(xué)者M(jìn)irjalili S根據(jù)座頭鯨的捕食行為，提出了一種新的群體智能算法即鯨魚(yú)優(yōu)化算法(whale optimization algorithm，WOA)[10]。這種全局搜索算法的優(yōu)勢(shì)在于結(jié)構(gòu)簡(jiǎn)單，調(diào)節(jié)的參數(shù)少，運(yùn)算速率快，也間接減少了參數(shù)影響問(wèn)題。本文將改進(jìn)WOA(improved WOA,IWOA)應(yīng)用于三維時(shí)差定位，通過(guò)對(duì)適應(yīng)度函數(shù)和初始化的調(diào)整，使其更加適合時(shí)差問(wèn)題的解決，并將IWOA算法與其他智能優(yōu)化算法進(jìn)行性能比較。

1 多站TDOA定位模型的建立

在三維時(shí)空中建立時(shí)差觀測(cè)模型，假設(shè)存在M個(gè)觀測(cè)站，設(shè)定基站的位置Si=[xi,yi,zi]，i=1,2,…,M，目標(biāo)位置L=[x,y,z]。觀測(cè)目標(biāo)發(fā)出的信號(hào)到達(dá)基站時(shí)間ti為

(1)

(2)

eri=ceti

(3)

ri,j=c(ti-tj)=c(ti+eti-tj-etj)=ri+eri-rj-erj

(4)

即

(5)

為了使得似然函數(shù)取得最大值，相當(dāng)于求解式(6)

(6)

2 IWOA

2.1 種群初始化優(yōu)化

將尋找目標(biāo)位置的空間假定為一個(gè)N×M維的，N代表的是種群數(shù)量，M則代表空間的維數(shù)，Lm和Um分別表示空間的上下限，m=1,2,…,M，初始化種群的初始位置依據(jù)式(7)在空間中隨機(jī)產(chǎn)生

Xim=Lm+rand(1,3)(Um-Lm)

(7)

初始化的種群散布情況對(duì)接下來(lái)的搜尋過(guò)程有著較大影響，大部分智能算法采用隨機(jī)分布，本文則采取復(fù)雜程度較低的Chan算法[11]先去生成一個(gè)初始解，將這個(gè)解去替換掉初始種群中的一個(gè)隨機(jī)解，對(duì)初始種群進(jìn)行優(yōu)化處理。因?yàn)槌跏冀獗容^接近最終估計(jì)解，所以,全局搜索的效率會(huì)提升。

2.2 改進(jìn)適應(yīng)度函數(shù)

2.2.1 針對(duì)基站不同影響問(wèn)題

根據(jù)式(6)可以看出，傳統(tǒng)的解析法對(duì)于這個(gè)問(wèn)題的求解較為復(fù)雜，本文利用IWOA對(duì)其求解，可以根據(jù)式(6)得出適應(yīng)度函數(shù)

(8)

式中X為位置矢量，適應(yīng)度函數(shù)的構(gòu)建將會(huì)對(duì)算法產(chǎn)生較大影響，結(jié)合式(2)可以得出如下結(jié)論：主基站的到達(dá)時(shí)間t1對(duì)式(8)中的每一項(xiàng)都有作用，但是從基站的達(dá)到時(shí)間ti則對(duì)其中的i-1項(xiàng)有影響，可知主從基站存在差異，主基站的影響較大，假如主基站的測(cè)量誤差較大，那么對(duì)于適應(yīng)度函數(shù)將產(chǎn)生很大影響。

所以做出進(jìn)一步改進(jìn)，改進(jìn)的適應(yīng)度函數(shù)為

(9)

利用式(9)將每個(gè)基站作為主基站去處理，消除了主從基站差異。篩選出其中的最小值作為改進(jìn)的f(X)代入方程，具體公式為

f(X)=min[f1(X),f2(X),…,fM(X)]

(10)

(11)

2.2.2 針對(duì)優(yōu)化算法調(diào)整

在此基礎(chǔ)上對(duì)其進(jìn)一步改進(jìn)，通過(guò)引入慣性權(quán)重因子ω協(xié)調(diào)全局和局部性能。具體如下：在運(yùn)算過(guò)程中，將各個(gè)個(gè)體的適應(yīng)度值按大小進(jìn)行排序，將序列分割成兩部分，分別計(jì)算平均數(shù)值fa1fa2(fa1

1)f(i)

此時(shí)的個(gè)體適應(yīng)度優(yōu)于較好平均值，說(shuō)明此個(gè)體的質(zhì)量較好，此時(shí)應(yīng)該在其附近進(jìn)行小范圍運(yùn)動(dòng)，有利于對(duì)局部的搜索能力提升，所以,ω取值(0.8,1.2)之間的隨機(jī)數(shù)。

2)f(i)>fa2

此時(shí)個(gè)體的適應(yīng)度比較差群體的平均值還差，說(shuō)明其位置不好，個(gè)體應(yīng)該在大范圍移動(dòng)去尋找有利位置，故此時(shí)ω以50%概率選擇(0.3,0.6)或者(1.3,1.6)之間的隨機(jī)數(shù)。

3)f(i)介于兩數(shù)值之間

此時(shí)個(gè)體的適應(yīng)度數(shù)值不好也不壞，按照一般規(guī)律運(yùn)動(dòng)即可。ω取值為1即可。

2.3 WOA的優(yōu)化

WOA主要分為3個(gè)部分：包圍收縮、覓食以及螺旋式更新。

2.3.1 包圍收縮

座頭鯨識(shí)別獵物并且將其包圍，在此過(guò)程中以鯨群中處于最佳的捕食位置作為目標(biāo)或最接近目標(biāo)的位置，其他鯨魚(yú)向其移動(dòng)，其表達(dá)式為

(12)

A=2ar-a

C=2r

(13)

式中a為一個(gè)控制變量，取值通過(guò)a=2-2t/tmax形式變化，tmax為最大迭代次數(shù)，r為(0,1)間隨機(jī)數(shù)。

2.3.2 覓食搜索

在此階段進(jìn)行隨機(jī)搜索行為，表示如下

(14)

2.3.3 螺旋式更新

此階段是模仿座頭鯨狩獵中，鯨魚(yú)通過(guò)螺旋移動(dòng)方式向著最優(yōu)解靠近，數(shù)學(xué)模型建立如下

(15)

(16)

其中，第i個(gè)鯨魚(yú)目前位置和最佳個(gè)體的距離關(guān)系，b為個(gè)螺旋形狀參數(shù)，l為(-1,1)間的隨機(jī)數(shù)。

此時(shí)的鯨魚(yú)不僅要以螺旋形式游動(dòng)而且要收縮包圍獵物，其通過(guò)50%的概率在螺旋游動(dòng)和收縮包圍兩種機(jī)制之間進(jìn)行位置變化，表示如下

(17)

其中，p為(0,1)間隨機(jī)數(shù)。

2.4 IWOA算法步驟

使用IWOA算法針對(duì)TDOA定位問(wèn)題的具體步驟如下：

1)初始化種群和各個(gè)參數(shù)。根據(jù)式(7)隨機(jī)初始化種群個(gè)體，然后如2.1節(jié)所述，通過(guò)使用Chan算法產(chǎn)生一個(gè)初始解去替換種群中一個(gè)隨機(jī)的個(gè)體；

2)對(duì)種群計(jì)算適應(yīng)度。通過(guò)式(10)分別計(jì)算出當(dāng)前個(gè)體的適應(yīng)度值，記錄其中的適應(yīng)度最優(yōu)值個(gè)體位置；

3)開(kāi)始迭代，當(dāng)t

4)位置更新。使用式(17)通過(guò)p值選擇行為機(jī)制；

5)計(jì)算更新后種群的適應(yīng)度,通過(guò)適應(yīng)度數(shù)值比較進(jìn)行位置替換；

6)重復(fù)步驟(3)～步驟(5)，直至算法到達(dá)迭代次數(shù)的門(mén)限，輸出最優(yōu)食物位置以及其適應(yīng)度取值,此時(shí)的獵物位置就是目標(biāo)的估計(jì)位置。

3 實(shí)驗(yàn)的仿真結(jié)果與分析

3.1 收斂性能分析

本文設(shè)定三維時(shí)空模型，在此條件下，通過(guò)與常見(jiàn)的粒子群(PSO)算法及其改進(jìn)權(quán)重的粒子群(IPSO)算法，遺傳算法(GA)，經(jīng)典WOA進(jìn)行對(duì)比，驗(yàn)證IWOA對(duì)于TDOA非線性問(wèn)題求解的性能，仿真實(shí)驗(yàn)的環(huán)境設(shè)定如下：基站按照Y型分布，在地上的基站的坐標(biāo)分別為，主觀測(cè)站S1=[0,0,0]，從觀測(cè)站S2=[0,15,0]，S3=[-10,10,0]，S4=[-10,-10,0]，目標(biāo)位置L=[80,55,20]，單位km。

種群數(shù)為40，迭代上限為500，以此條件進(jìn)行迭代運(yùn)算，以反應(yīng)其不同算法針對(duì)TDOA問(wèn)題計(jì)算的特性，結(jié)果如圖1所示。

圖1 算法迭代對(duì)比

從圖1中可以看出，經(jīng)過(guò)500次的迭代過(guò)程，曲線均是可以收斂的，前期過(guò)程中可以看出，IWOA算法由于引入了初始解，初始種群更接近全局最優(yōu)解，其搜索范圍相比其他算法更有效，效率也較其他算法有提升，減緩了智能算法迭代次數(shù)多的劣勢(shì)。其他算法由于前期過(guò)程需要在整個(gè)空間中做充分的全局搜尋工作，所以，需要進(jìn)行更多次迭代才可以收斂到較小值。

在迭代的后期，IWOA相比于經(jīng)典WOA采取了一種新的適應(yīng)度函數(shù)策略，其對(duì)個(gè)體位置好壞的評(píng)價(jià)標(biāo)準(zhǔn)更準(zhǔn)確，使得算法可以收斂到更低的適應(yīng)度值，而其他智能算法都是采用一般的適應(yīng)度函數(shù)，所以其最后收斂結(jié)果近似且高于IWOA。在后期，IWOA的適應(yīng)度已經(jīng)明顯低于IPSO算法了，此外值得注意的是，在仿真的過(guò)程中，PSO及其IPSO算法，GA很容易出現(xiàn)問(wèn)題，會(huì)出現(xiàn)因?yàn)閰?shù)設(shè)置問(wèn)題導(dǎo)致收斂結(jié)果出現(xiàn)問(wèn)題，而且這類(lèi)智能算法的參數(shù)比較多，對(duì)收斂的速度和效率的影響較大，在實(shí)際中找到最優(yōu)參數(shù)是很困難的，IWOA在這一方面與其相比有著明顯的優(yōu)勢(shì)。

3.2 精度分析

為了觀察算法在位置判斷中的精確性，對(duì)不同位置的目標(biāo)源進(jìn)行位置判斷，采用Monte-Carlo方法仿真統(tǒng)計(jì)各個(gè)算法的定位正確率。仿真條件為，上界ub=[100,100,50]，下界lb=[-100,-100,0]，單位km，最大迭代次數(shù)600次，種群數(shù)40，對(duì)各個(gè)目標(biāo)源進(jìn)行5000次的Monte-Carlo仿真實(shí)驗(yàn)，并與WOA，PSO及其IPSO算法進(jìn)行比較，設(shè)定距離超過(guò)15 m即為錯(cuò)誤，實(shí)驗(yàn)結(jié)果如表1所示。

表1 定位正確率 %

從表1中可以看出，在目標(biāo)位置較近的情況下，幾種算法的準(zhǔn)確率都是比較高的，當(dāng)目標(biāo)源位置開(kāi)始變遠(yuǎn)時(shí)，幾種算法便出現(xiàn)差異性，PSO算法和WOA的正確率開(kāi)始降低。IPSO通過(guò)改進(jìn)線性權(quán)重，在迭代后期，其由于權(quán)重?cái)?shù)值變小，個(gè)體的移動(dòng)步長(zhǎng)也隨其減少，所以在后期時(shí)其強(qiáng)于PSO算法，另外PSO算法的過(guò)程中很容易陷入到局部極值之中，所以其準(zhǔn)確率較低。

相比于PSO及其改進(jìn)算法，IWOA更適合處理TDOA定位問(wèn)題，其算法中特有的搜索策略使得權(quán)值隨適應(yīng)度函數(shù)值隨機(jī)調(diào)整，使得種群在尋優(yōu)中更加多樣化，即增強(qiáng)了全局搜索的隨機(jī)性，提升全局搜索能力，平衡了局部探索和全局最優(yōu)的問(wèn)題。從結(jié)果看出，條件相同時(shí)，IWOA的準(zhǔn)確率較高，其面對(duì)不同的目標(biāo)位置時(shí)，算法的穩(wěn)定性也比較好。

圖2 實(shí)驗(yàn)結(jié)果

根據(jù)試驗(yàn)結(jié)果可以看出，在目標(biāo)較近時(shí)，幾種算法都沒(méi)有出現(xiàn)太大的波動(dòng)，IWOA比較貼合克拉美羅界，其他算法曲線相比之下略高于IWOA曲線。對(duì)于遠(yuǎn)場(chǎng)的目標(biāo)，IWOA的精度更高，可以更好地接近克拉美羅界。綜上，IWOA的穩(wěn)定性較好，精度更高。另外，由于PSO及其改進(jìn)算法，GA等涉及參數(shù)較多，且選取適合的參數(shù)需要更多的條件，所以復(fù)雜度較大，而IWOA的參數(shù)較少，且由于改進(jìn)了適應(yīng)度函數(shù)，計(jì)算結(jié)果更為準(zhǔn)確，相對(duì)其他算法結(jié)構(gòu)簡(jiǎn)單，且精度更高。在所選試驗(yàn)誤差功率下，實(shí)驗(yàn)中幾種算法沒(méi)有出現(xiàn)因門(mén)限問(wèn)題導(dǎo)致的大幅度曲線波動(dòng)，曲線變化較平穩(wěn)。

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

本文針對(duì)時(shí)差定位非線性問(wèn)題使用了一種新型的鯨魚(yú)優(yōu)化算法(IWOA)，通過(guò)對(duì)初始種群和適應(yīng)度函數(shù)的調(diào)整，使得本文算法更加貼合定位問(wèn)題。通過(guò)與其他智能優(yōu)化算法的定位性能比較，結(jié)果表明，IWOA具有結(jié)構(gòu)簡(jiǎn)單，計(jì)算效率較高，定位的精度高且穩(wěn)定性好的優(yōu)勢(shì)，對(duì)于實(shí)際利用基站定位有一定參考價(jià)值。