融合差分進化和Taylor級數(shù)的超寬帶定位解算方法

張 勇，高光輝，郭一楠，鞏敦衛(wèi)，楊建建

(1.中國礦業(yè)大學 信息與控制工程學院，江蘇 徐州 221116；2.中國礦業(yè)大學(北京)機電與信息工程學院，北京 100083)

0 引言

隨著智能物聯(lián)網(wǎng)的快速發(fā)展，需要對部署在室內(nèi)的眾多設備或人員定位，且定位精度要求也日益提高[1]。然而，現(xiàn)有定位方法主要依托無線信號，受復雜室內(nèi)環(huán)境、障礙物和噪聲影響嚴重，定位精度存在誤差。

常用的室內(nèi)定位方法主要包括紅外線定位、超聲波定位、藍牙定位、射頻識別定位、激光定位和超寬帶定位[2]等。其中，紅外線定位易受障礙物干擾，且通信距離較短[3]；超聲波定位受室內(nèi)環(huán)境中存在的多徑效應影響大，且定位距離較短[4]；藍牙定位對室內(nèi)噪聲敏感，且定位誤差較大、定位距離短[5]；射頻識別定位速度快、安全性強，但是定位距離短、系統(tǒng)兼容性差[6]；超寬帶定位采用帶寬大于500 MHz的納秒級脈沖信號，穿透性強、時間分辨率高、定位精度高，信號在傳輸過程中抗干擾能力強[1]。然而，采用超寬帶實現(xiàn)目標位置標定，是根據(jù)測定距離，基于一組非線性定位方程組，通過最小二乘法(least square method, LS)[7]、直接法[8]或Taylor級數(shù)迭代算法[9-10]進行方程求解獲得。其中，采用最小二乘法和直接法進行方程求解，獲得的定位精度較差；Taylor級數(shù)迭代算法的求解精度高，但是對初始值具有較強的依賴性，可能出現(xiàn)目標定位偏離實際值且不收斂的情況。

基于此，筆者針對超寬帶室內(nèi)定位方法，提出一種融合差分進化算法和Taylor級數(shù)迭代算法的新型定位解算方法。該算法以定位誤差作為優(yōu)化目標，采用差分進化算法對目標點實現(xiàn)全局定位，然后以差分進化算法獲得的最優(yōu)定位點作為初始值，采用Taylor級數(shù)迭代算法對定位點進行局部尋優(yōu)。通過這種定位解算方法克服傳統(tǒng)Taylor級數(shù)迭代算法對初始值的依賴性，從而獲得高精度的目標定位。進而將所提方法用于煤礦掘進巷道這一復雜室內(nèi)場景下，掘進支護移動支架的超寬帶定位解算。

1 超寬帶定位原理

超寬帶技術不是利用傳統(tǒng)的載波來傳輸數(shù)據(jù)，而是通過發(fā)送和接收具有納秒及納秒以下的極窄脈沖來傳輸數(shù)據(jù)，從而具有GHz量級的帶寬[2]。美國聯(lián)邦通信委員會對超寬帶的定義為：

(1)

式中：fH和fL分別為相對于峰值功率下降10 dB時對應的高頻和低頻值；fC為載波的中心頻率。

采用超寬帶定位方法對目標點進行位置標定時，通常相對于目標點設置多個基站，如圖1所示。通過K個基站依次對目標點進行超寬帶測距，進而依據(jù)測距信息，構建定位方程組，解算獲得目標點位置坐標。

圖1 超寬帶定位原理

超寬帶定位通常采用基于接收信號強度、基于信號到達角度和基于信號到達時間[11]。相比而言，采用到達時間測距方法具有較高的測距精度，但是單向測距需要基站和目標點之間時鐘嚴格同步，這一要求很難保證，而采用雙向測距不需要時鐘同步，有效提高了測距精度[12]。

基于雙向測距的接收信號時間法原理如圖2所示。針對第i(i=1,2,…,K)個基站，目標點在Ti0時刻發(fā)送含有時間標記信息的數(shù)據(jù)包給基站i，基站i收到此數(shù)據(jù)包，并延時時間Ti delay后，回送一個信號給目標點，目標點根據(jù)接收到的信號來確定傳播時間。假設Ti為信號在目標點和基站i之間傳輸所用時間，Ti0為信號從目標點發(fā)出的時刻，Ti1為目標點收到返回信號的時刻，c為光速，則目標點和基站i之間的測定距離為：

di=Tic；

(2)

(3)

圖2 基于雙向測距的接收信號時間法原理

假設第i個基站的坐標為(xi,yi,zi)，目標點坐標為(xs,ys,zs)，則根據(jù)所有基站與目標點之間的到達時間構建超寬帶定位解算模型為：

(4)

2 融合差分進化和Taylor級數(shù)的定位解算方法

Taylor級數(shù)迭代算法求解超寬帶定位方程組可以獲得精確的定位結(jié)果，但是該算法對初始值具有較強的依賴性。選取不當?shù)某跏贾?，可能導致獲得的目標位置偏離實際值較遠，甚至不收斂的情況?；诖耍芯咳藛T提出直接法[11]、LS算法[12]用于選取Taylor級數(shù)迭代算法的初始值。但是，LS算法中逆矩陣的求解耗時，且定位精度不高?；诖耍P者引入差分進化算法這一基于群體的高效啟發(fā)式全局優(yōu)化算法，對目標點實現(xiàn)全局定位，將獲得的最優(yōu)定位點作為Taylor級數(shù)迭代算法初始值進行局部尋優(yōu)，從而獲得高精度的目標定位。

2.1 基于差分進化算法的全局定位

差分進化算法(differential Evolution，DE)由Rainer Storn和Kenneth Price于1997年提出，是一種基于種群的啟發(fā)式進化優(yōu)化方法[13]。DE算法結(jié)構較簡單且易于實現(xiàn)，調(diào)控參數(shù)少，時間復雜度低。為提高DE算法的搜索能力，目前已有一些改進，如JADE[14]、SHADE[15]算法等，相比于DE算法, JADE、SHADE算法整體上具有較快的收斂速度和收斂精度,同時表現(xiàn)出較好的穩(wěn)定性。

以目標點位置坐標(xs,ys,zs)作為差分進化個體，且個體中各個變量滿足xs∈[xs min,xs max]，ys∈[ys min,ys max]，zs∈[zs min,zs max]。記第i個超寬帶基站到目標點的測量距離為di，則超寬帶定位解算模型轉(zhuǎn)化為如下單目標優(yōu)化問題：

f(xs,ys,zs)=

(5)

采用DE算法實現(xiàn)超寬帶定位方程解算，具體算法流程如下。

Step1：初始化種群，設種群規(guī)模為N，初始化種群中的每個解記為xi(0)，i=1,2，…，N。

Step2：評價種群中每個個體的適應值。

Step3：在第t次迭代中，對第i個個體進行變異操作，從種群中隨機選擇3個個體xp1(t)、xp2(t)、xp3(t)，且p1≠p2≠p3≠i，記為：

(6)

式中：F∈[0,2]為加權因子。

(7)

式中：CR∈[0,1]是交叉概率；j=1,2,…,M；jrand為隨機整數(shù)，jrand∈[1,M]，M為個體的變量維數(shù)。

(8)

Step6：判斷是否達到最大進化代數(shù)，若是，則終止進化，將得到最優(yōu)個體作為目標點位置輸出；若否，則跳轉(zhuǎn)到Step2。

2.2 基于Taylor級數(shù)迭代算法的局部定位

Taylor級數(shù)迭代算法是一種遞歸算法。它基于定位初始值，通過反復迭代，獲得目標點的最優(yōu)坐標[10]。假設目標點的真實坐標為(xs,ys,zs)，位置初始值為(xs0,ys0,zs0)，真實目標點坐標與解算后目標點坐標滿足以下關系：

(9)

在初始坐標(xs0,ys0,zs0)處，對超寬帶定位方程組進行Taylor級數(shù)展開，并忽略二階以上分量：

Δ=(.T.)-1.T.，

(10)

式中：

.=

基于DE算法和Taylor級數(shù)迭代算法的室內(nèi)超寬帶定位解算方法的步驟如下。

Step1：目標點依次向各個基站發(fā)起一次測距，根據(jù)公式(2)和(3)，計算每次測量的距離值，對每一個基站進行1 000次測距，取其平均值作為目標點與這個基站的距離，記為d1,d2,,…,dk。

Step2：根據(jù)目標點與各個基站之間的距離，列出定位方程解算模型。

Step3：以公式(5)作為適應度函數(shù)，采用DE算法求取目標點的最優(yōu)位置坐標(xs0,ys0,zs0)，作為Taylor級數(shù)迭代的初始值。

Step4：將(xs0,ys0,zs0)代入.和.，依據(jù)公式(10)進行迭代計算，直到滿足|Δx|+|Δy|+|Δz|≤ε。

Step5：若條件成立，則把(xs0,ys0,zs0)作為最優(yōu)目標點定位輸出；若不成立，則計算公式(9)，并返回Step4。

3 實驗分析與結(jié)果說明

為充分驗證所提定位解算方法的合理性和有效性，將所提方法用于煤礦掘進巷道這一復雜室內(nèi)場景，對掘進支護移動支架進行超寬帶定位解算。

3.1 測試環(huán)境和參數(shù)設置

假設巷道為矩形，寬4.2 m、高3.9 m、長100 m。采用4個基站進行定位，且4個基站的坐標分別為(0,0,0)、(2,4,0)、(-2,4,0)、(0,0,3.8)。每隔10 m，掘進支護支架上的目標點依次對4個基站進行超寬帶測距，一般測距誤差服從均值為0、標準差為2 cm的正態(tài)分布[12]。在上述定位環(huán)境下，目標點對每個基站進行1 000次測距，取其均值作為距離估計值。

DE算法中個體的搜索范圍取決于巷道尺寸，即xs∈[-2.1,2.1]，ys∈[10,100]，zs∈[0,3.9]。選取種群規(guī)模為30，最大迭代次數(shù)為100，Taylor級數(shù)迭代算法中的誤差閾值ε=0.01。

(11)

3.2 所提定位解算方法對參數(shù)敏感性分析

筆者結(jié)合已有文獻分析DE算法參數(shù)對解算結(jié)果的影響。文獻[16]設置加權因子F=0.5，交叉概率CR=0.9或CR=0.1；文獻[17]設置加權因子F=0.5，交叉概率CR=0.5；文獻[18]設置加權因子F=0.9，交叉概率CR=0.9；文獻[19]設置加權因子F=1.0，交叉概率CR=0.9。面向不同測量距離，分別采用以上DE算法參數(shù)，進行500次獨立運行后的定位誤差均值如圖3和圖4所示。

圖3 不同加權因子時定位解算方法的平均定位誤差

圖4 不同交叉概率時定位解算方法的平均定位誤差

對比圖3可知：加權因子對于定位解算方法的影響較小。其中，定位解算方法在加權因子F=0.5時，取得較好的效果，在F=1和F=0.9時的平均定位誤差稍大于F=0.5時的平均定位誤差，但是差別不明顯。對比圖4可知：交叉概率對于定位解算方法的影響較大。其中，定位解算方法在交叉概率CR=0.1時，平均定位誤差明顯大于CR=0.5和CR=0.9時的平均定位誤差；在CR=0.9時的平均定位誤差稍小于CR=0.5時的平均定位誤差。在以下實驗中，設置加權因子F=0.5和交叉概率CR=0.9。

3.3 不同定位解算方法性能對比分析

分別用LS算法[9]、直接法[10]、直接-Taylor算法[11]、LS-Taylor算法[12]和筆者提出的DE-Taylor算法，實現(xiàn)對掘進支護移動支架超寬帶定位方程組的解算。面向不同測量距離，進行500次獨立運行后的定位誤差均值和方差如表1所示；相應的定位誤差均值和boxplot圖，如圖5和圖6所示。

表1 噪聲環(huán)境下5種解算方法的平均定位誤差和方差

圖5 5種算法的平均定位誤差

對比5種算法的平均定位誤差，可知：隨著目標點距離基站位置的增加，無論何種算法，其定位誤差都逐漸變大，且呈線性增加。在相同的定位距離下，LS算法和直接法作為全局定位方法，具有相對較大的定位誤差。在融合Taylor級數(shù)迭代這一局部定位算法后，上述算法的定位精度顯著提高。采用DE算法作為全局定位方法后，筆者所提出的DE-Taylor定位解算方法具有最好的定位精度。

圖6為5種算法的定位誤差分布圖，由圖6可知：在相同的定位距離下，LS算法和直接法的誤差分布較分散，定位誤差均值比較大。融合Taylor級數(shù)迭代算法后，3種算法的定位誤差分布較緊密，定位誤差均值有一定程度的減小，其中DE-Taylor算法的定位誤差分布最緊密且具有最小的定位誤差均值。由表1可以看出：DE-Taylor算法的平均定位誤差和方差都最小(表1加黑部分)。

圖6 5種算法定位誤差分布圖

4 結(jié)論

用于室內(nèi)設備或人員定位的超寬帶定位方法，其傳統(tǒng)的定位模型解算采用Taylor級數(shù)迭代算法，對初始值存在較強依賴性?；诖?，筆者提出一種融合差分進化算法和Taylor級數(shù)迭代的新型超寬帶定位解算方法，通過差分進化算法獲得的全局最優(yōu)值作為Taylor級數(shù)迭代的初始值，實現(xiàn)更準確的目標定位。針對煤礦掘進巷道這一復雜室內(nèi)場景，采用所提方法實現(xiàn)掘進支護移動支架的超寬帶定位解算，實驗結(jié)果表明，所提方法比LS算法、直接法、LS-Taylor算法和直接-Taylor算法具有更高的定位精度和更強的魯棒性。