基于到達時間量測的多傳感器協(xié)同定位算法研究

方藝忠，姜浩楠，陳 旸，蔡遠利，孟 剛

（1. 北京航天長征飛行器研究所，北京，100076；2. 試驗物理與計算數(shù)學(xué)國家重點實驗室，北京，100076；3. 西安交通大學(xué)電子與信息學(xué)部，西安，710049；4. 中國運載火箭技術(shù)研究院，北京，100076）

0 引 言

無線定位系統(tǒng)通常需要兩個或者更多的傳感器來對目標位置進行捕獲。常見的定位方法通?；诘竭_時間（Time of Arrival，TOA）、到達方位（Angle of Arrival，AOA）、接收信號強度（Received Signal Strength，RSS）和到達時間差（Time Difference of Arrival，TDOA）中的一種或多種量測信息對目標的位置進行估計。由于在無線通信系統(tǒng)、檢測系統(tǒng)以及導(dǎo)航系統(tǒng)中的廣泛應(yīng)用，基于TOA 等量測信息的目標定位問題得到了廣泛的關(guān)注和研究。本文主要研究基于TOA 量測的多傳感器協(xié)同定位算法。

TOA 協(xié)同定位的目標是根據(jù)分布在不同位置的傳感器獲得的目標信號到達時間量測（當信號傳播速度為1 時，到達時間量測即為距離量測）來估計目標的位置，本質(zhì)上是一類優(yōu)化問題。不同定位方法的主要區(qū)別之一是目標函數(shù)不同，常用的目標函數(shù)包括距離最小二乘（Range Least Squares，RLS）和距離平方最小二乘（Squared Range Least Squares，SRLS）。大部分解析算法都是采用SRLS 作為目標函數(shù)，將歐氏距離轉(zhuǎn)換成為更容易處理的二階多項式的形式，保證了最優(yōu)解的存在性。然而，數(shù)值迭代算法一般都采用RLS 作為目標函數(shù)，從一個給定的初始估計開始，不斷逼近最優(yōu)解。在量測噪聲服從零均值高斯分布的假設(shè)下，RLS 得到的解和最大似然估計解一致。除此以外，還有一些優(yōu)化工具箱可以給出RLS 意義下的最優(yōu)解，如半正定松弛（Semidefinite Relaxation，SDR）[和多項式優(yōu)化（Polynomial Optimization，POP）等。這一類方法可以以任意精度逼近最大似然估計，缺點是計算時間過長。

本文主要研究TOA 定位算法中的解析算法和數(shù)值迭代算法。解析算法通常是在原始問題上放松了一些條件或者運用一些巧妙的數(shù)學(xué)變換，推導(dǎo)出目標位置的直接結(jié)果；數(shù)值迭代算法則是從一個初始估計開始，不斷逼近全局最優(yōu)解，這通常會消耗非常多的時間，不便于實際應(yīng)用。然而，數(shù)值迭代算法也有著多方面的優(yōu)勢，如適用于任意數(shù)量任意類型的量測信息、編程相對簡單、不需要放松任何條件以及容易擴展和推廣等。本文利用熱圖分析了兩類算法在不同目標位置下的表現(xiàn)，隨后在不同量測噪聲強度條件下對比了多種定位算法的估計效果，能夠?qū)Σ煌瑘鼍跋露ㄎ凰惴ǖ倪x擇提供幫助。同時，通過對迭代算法進行適當調(diào)整，可以改善算法的魯棒性，提升算法在量測噪聲強度較大環(huán)境下的估計效果，達到與解析算法同樣好的估計精度。

1 問題描述

假定為二維平面內(nèi)目標的位置，s (= 1,2,…,)為第個傳感器的位置，各個傳感器獲取的信號源到自身位置的時間量測信息依次為,… , T。TOA 定位的目標是：在傳感器位置,…,和傳感器量測,… , T給定的情況下，估計目標的位置。為了簡便，本文假定信號的傳播速度為1，則TOA 量測即為距離量測。

由此量測方程可以寫為

依據(jù)極大似然準則，TOA 定位問題的解可通過下式求得：

等價于：

通過式（3）求得的最小二乘解是在方差意義下的最優(yōu)解。

2 解析算法

本小節(jié)介紹一些解決TOA 定位問題的解析算法。盡管解析算法在推導(dǎo)方面較為復(fù)雜，但其不需要初始估計且能夠保證結(jié)果的收斂性，相比于數(shù)值迭代算法得到的結(jié)果更加精確和穩(wěn)定。

2.1 基線法

基線法通過計算所有傳感器位置坐標的均值作為目標位置的估計：

從計算公式可以看出，基線法得到的目標位置估計不依賴于任何量測信息。在平均意義下，可以判斷，基線法的估計效果較差。

2.2 Simple Intersection 算法

從幾何上理解，該算法考慮?1組圓，用直線代替它們的交會部分。由于消除掉了非線性項，得到的結(jié)果等價于在少了一個量測的情況下對目標進行估計的結(jié)果。

采用Simple Intersection 算法得到的目標位置估計為

2.3 Bancroft 算法

式（7）整合到一起，可以得到：

即：

式（9）左右兩邊同時乘以矩陣的Moore–Penrose偽逆，可以得到：

兩邊同時平方可以得到：

等價于：

Bancroft 算法的具體流程為：

a）計算向量= ()1；

b）計算向量= ()；

c）求解方程（14）的兩個根；

2.4 Beck 算法

Beck 等人于 2008 年提出了一種精確的least-quartic 算法。在求解的過程中，需要使用二分法尋找單變量嚴格單調(diào)函數(shù)的根，因此得到的并不是嚴格意義上的解析解，但這種算法能夠保證估計效果收斂。具體算法流程如下：

3 數(shù)值迭代算法

數(shù)值迭代算法的典型代表是高斯-牛頓算法，又稱為加權(quán)迭代最小二乘算法。高斯-牛頓算法在量測噪聲較大的情況下無法避免估計發(fā)散的問題。為了克服這一缺陷，對傳統(tǒng)的高斯-牛頓算法進行修正，得到正則化的高斯-牛頓算法。

3.1 高斯-牛頓算法

高斯-牛頓算法流程如下：

a）選擇合理的初始估計值和算法中止參數(shù)。設(shè)置=0 。

b）計算雅可比矩陣：

c）迭代更新=+Δ，其中，

式中為量測噪聲協(xié)方差矩陣。

3.2 正則化高斯-牛頓算法

相比于原始的高斯-牛頓算法，正則化高斯-牛頓算法的不同僅在于Δx的設(shè)置，其具體流程如下：

a）選擇合理的初始估計值和算法中止參數(shù)。設(shè)置=0 ；

b）計算雅可比矩陣：

c）迭代更新=+Δ，其中，

式中為正則化系數(shù)； x為正則化位置。

4 熱圖分析法

為了更全面地刻畫不同種類算法的估計效果，本小節(jié)利用熱圖分析解析算法（以Beck 算法為例）和數(shù)值算法（以正則化高斯-牛頓算法為例）針對不同位置目標的估計誤差。熱圖起源于數(shù)據(jù)矩陣中數(shù)值的二維顯示，顏色越淺，表明該算法對位于當前方格的目標定位效果越好；顏色越深，表明該算法對位于當前方格的目標定位效果越差。

在量測噪聲標準差為100 m 的情況下，Beck 算法和正則化高斯-牛頓算法得到的均方根誤差（Root Mean Square Error，RMSE）關(guān)于目標位置熱圖如圖1和圖2 所示?？梢园l(fā)現(xiàn)，解析算法和數(shù)值算法針對不同位置目標的估計效果非常相似，數(shù)值算法的估計效果絲毫不亞于解析算法。

圖1 Beck 算法均方根誤差（RMSE）關(guān)于目標位置的熱圖Fig.1 Heat Map of RMSE of Beck Algorithm with Respect to Target Position

圖2 正則化高斯-牛頓算法均方根誤差（RMSE）關(guān)于目標位置的熱圖Fig.2 Heat Map of RMSE of Regularized Gauss-Newton Algorithm with Respect to Target Position

5 仿真分析

本小節(jié)針對多傳感器TOA 定位問題，對比不同解析算法和數(shù)值迭代算法的估計效果。

仿真結(jié)果如圖3 所示。Michael提出的Partitioning算法能夠給出R-LS 準則下的全局最優(yōu)解，可以用于性能評估。

圖3 TOA 算法效果對比Fig.3 Comparison of TOA Algorithms

Beck 算法、Cheung 算法和Partitioning 算法等在不同量測噪聲強度下均能保持較高的定位精度，對噪聲的敏感性較弱。基線法、Simple Intersection 算法和Bancroft 算法的估計效果較差。當量測噪聲標準差小于300 m 時，其余幾種算法幾乎能夠達到一致且最優(yōu)的估計效果。當量測噪聲標準差達到2 ×10 m 時，原始的高斯-牛頓算法得到的誤差曲線開始發(fā)散，表明其在較大量測噪聲強度下估計效果不能得到保證，而正則化高斯-牛頓算法在高強度噪聲環(huán)境下依然能保證與優(yōu)異的解析算法幾乎一致的估計效果，展現(xiàn)了其更強的魯棒性。

在噪聲標準差達到 6 ×10~10m 時，可從圖3 中看出基線法的估計效果反而是最好的，說明在量測噪聲強度過大時，最好的估計策略是摒棄所有得到的量測信息，直接利用先驗信息對目標的位置進行估計。

6 結(jié) 論

本文研究了基于到達時間量測的多傳感器定位問題，其本質(zhì)上是一類優(yōu)化問題，可以通過解析算法或者數(shù)值迭代算法進行求解。以Beck 算法為代表的解析算法雖然能夠保證估計結(jié)果收斂，但通常需要在多種假設(shè)和前提下才能得到閉式解，求解過程較為復(fù)雜；以高斯-牛頓算法為代表的數(shù)值迭代算法結(jié)構(gòu)簡單、易于擴展和推廣，但其需要初始估計且無法保證結(jié)果收斂。在實際應(yīng)用中，如果能夠獲得較為準確的先驗信息同時對實時性要求不高，建議采用數(shù)值迭代算法；反之，Beck 算法等解析算法是更好的選擇。本文對比了多種較為經(jīng)典和有效的TOA 定位算法，同時利用熱圖分析了算法在不同目標位置下的估計效果，能夠為TOA 定位問題的算法選擇提供幫助。