協同定位中的坐標配準策略研究

范英盛，齊小剛，劉立芳

（1. 西安電子科技大學 數學與統計學院，陜西 西安 710071; 2. 浙江警察學院 公共基礎部，浙江 杭州 310053;3. 西安電子科技大學 計算機學院，陜西 西安 710071）

精確的位置信息，是為許多集群網絡，包括機器人網絡[1-3]、車聯網[4]、無人機集群[5-6]、無人水面艇[7]等，提供服務或者實現完全自主導航[8]的基礎。為了獲取位置信息，一種可能的方案是為集群網絡中的每個節點安裝GPS或BDS[9]接收機，但部分應用場景在室內[10]、太空、下水管道、水下[11]等環境中，GPS信號容易受到多徑干擾、遮擋等因素的影響，往往只有少部分節點能夠得到精確的絕對位置信息，這一部分節點被稱為錨節點，而沒有位置信息的節點一般被稱為未知節點。利用集群網絡節點之間通信交互的過程中獲得的相對測量信息輔助網絡節點定位是解決缺少蜂窩系統基站和在GPS缺失環境下高精度定位的一種新思路[12-13]。相對測量信息包括相對距離測量、相對角度測量、相對速度測量等。本文只考慮基于相對距離測量的定位算法。基于測距的定位算法主要可分為兩大類，單點定位和協同定位[14]。基于距離測量的協同定位按照建模思路的不同，可劃分為兩大類：1)將定位問題建模為一個非凸優化問題[15-17]，可通過基于半定規劃[15](semidefinite programming，SDP)的算法或基于MDS[16-17](multidimensional scaling)的算法求解；2)將定位問題建模為一個非線性最小二乘問題[18]，可通過Gauss–Newton、Levenberg– Marquardt算法(LM)以及Powell’s Dog Leg 算法(DL)求解。

基于測距的協同定位算法給出的是集群網絡的相對位置信息，這是因為當依據某種算法給出位置估計后，作任意的平移和旋轉，依然能夠滿足距離約束。評價定位算法性能常用的兩個指標是平均絕對誤差(mean absolute error，MAE)和均方根誤差(root mean square error，RMSE)，而這兩個指標的計算都需要絕對位置信息。實際上，坐標配準可以通過錨節點的絕對位置信息與相對位置信息實現。理論上，對于p維空間，兩個坐標系進行坐標配準至少要有p+1個公共節點。當測距不存在誤差時，通過協同定位算法可獲得節點的精確相對位置信息，此時的坐標配準只涉及平移與旋轉，不同的配準方法都可以得到精確的配準結果。然而不論是基于RSSI(received signal strength indicators)或者TOA(time of arrival)的測距方法，都是存在測距誤差的，此時節點無法獲得精確的相對位置信息，坐標配準的誤差主要來源于3個方面：1)相對位置信息的精度，這是由測距誤差和定位算法決定的；2)錨節點的數量和構型，以3D空間、4個錨節點為例，若4個錨節點共面程度較高，則求解的旋轉矩陣可能會出現嚴重偏差，并顯著放大配準誤差，這與單點定位中，4個錨節點共面程度高會導致嚴重誤差是同樣的道理；3)配準方法，目前對于協同定位的研究主要是針對定位算法，對于坐標配準的介紹很少，文獻中最常用的配準算法主要是基于最小二乘[19]的方法，該方法比較簡單，存在的問題是放縮因子難于計算，一般認為錨節點在2個坐標系之間的構型不存在放縮。普氏分析是統計學中用于多元變量分析的一種工具，在物體統計形態分析領域應用廣泛，例如分析化學、紅外光譜指紋區相似度評價、人臉匹配、醫學成像匹配等[20-23]。近年逐漸應用于語義分析[24]。本文將詳細介紹普氏分析如何應用于協同定位中的坐標配準。

1 坐標配準模型

1.1 坐標配準模型與符號說明

2 基于普氏分析的坐標配準

普氏分析的部分推導方法參考了文獻[25]。本文將普氏分析應用于坐標配準之中，其基本思想是把坐標配準問題建模為優化問題，即

如無特殊說明，本文中的 ‖·‖是指歐幾里得范數。這里的Q是正交矩陣，即Q′Q=I，I表示單位矩陣。為簡化旋轉矩陣Q的計算，普氏分析有2步預處理：1)將矩陣A與B的幾何中心平移到同一個點，一般平移到坐標原點；2)將矩陣A與B作歸一化處理。

2.1 平移

2.2 歸一化

當把矩陣A與B的幾何中心平移到坐標原點后，還要消除放縮的影響，因此需要進行歸一化處理。歸一化后的矩陣用A0和B0表示，要滿足‖A0‖=1與 ‖B0‖=1，只需：

2.3 求解旋轉變換Q

在進行了2步預處理之后，可以先將式(1)所示的最小化問題簡化為式(6)來求解Q，即

tr(A)表 示矩陣A的跡，由矩陣跡的定義以及“循環性質”，也即 t r(ABC)=tr(CAB)=tr(BCA)，可知：

式中： tr(B0TB0) 和 t r(A0TA0)與Q無關。要使式(7)取得最小值，只要 tr(A0TB0Q)取最大值即可。對A0TB0作奇異值分解，可得A0TB0=UWVT，W為對角矩陣，由此可得:

式中H=VTQU，由于VT、Q、U皆為正交矩陣，故其乘積H也為正交矩陣。用 σi表示奇異值，hii表示H的主對角線元素，可得：

對于三維坐標配準，p=3(二維坐標配準，p=2 )。由于 σi非負，式(9)要取得最大值，則正交矩 陣H的 對 角 元 素hii=1 ，i=1,2,···,p。此 時，H=I，也即VTQU=I，進而：

2.4 在A0、B0、Q下求解放縮因子s0

不存在測距誤差的理想環境下，大部分協同定位算法可求得網絡相對位置的精確解，此時s=1。然而在實際環境中，由于測距誤差、通信環境、定位算法等因素的影響，網絡相對坐標的估計值都存在誤差，此時相對估計位置與絕對位置之間可能存在的放縮就不能被忽略。保持旋轉矩陣Q不變，在式(6)中添加放縮因子s0，可得式(11)所示的優化問題：

由式(11)可得：

式(12)實際是一個關于s0的開口向上的一元二次函數，若要使式(12)取得最小值，則：

s0A0TB0即為矩陣 奇異值分解后的奇異值之和。

2.5 求解平移向量T

由式(11)和式(13)，可以近似認為s0B0Q≈A0。再由式(2)～(5)可得

由式(15)得到放縮因子s和平移向量T分別為

2.6 基于普氏分析坐標配準的計算流程

基于普氏分析的坐標配準，需要計算旋轉矩陣Q、放縮因子s和平移向量T，其計算流程為：

輸入m個錨節點的真實坐標矩陣A，m個錨節點的相對估計坐標矩陣B；

輸出 旋轉矩陣Q，放縮因子s，平移向量T。

1)根據式(2)、(3)對矩陣A與B進行平移，求得 平 移 后 的 矩 陣Ac與Bc以 及TA與TB；

2)根據式(4)、(5)對Ac與Bc進行歸一化，求得歸一化后的矩陣A0與B0；

3)根據式(7)～(9)求得旋轉矩陣Q；

4)若考慮放縮因子s，則根據式(12)、(13)求得式(12)中的s0，轉5)；若不考慮放縮因子s，則令s=1，轉至6)；

5)根據式(16)求得放縮因子s；

6)根據式(17)求得平移向量T。

普氏分析的計算復雜度比最小二乘法高，一般來說，m遠 小于N，故其本身的計算量并不大。

3 仿真實驗

本節通過仿真實驗來分析錨節點數量、測距誤差、網絡節點平均連通度對配準精度的影響，比較基于最小二乘與基于普氏分析的坐標配準精度。配準精度用平均絕對誤差MAE來評價，MAE的定義為

3.1 實驗設置

實驗軟件是Windows10系統下Matlab2017a。協同定位算法選擇經典MDS+ LM算法，即經典MDS求解初始輸入，LM算法迭代求精。基于普氏分析的配準算法，用PA表示。基于最小二乘的配準算法作為對比算法，用LS表示。N=50 個節點隨機部署在2D和3D環境中，2D環境是100 m× 100 m的區域，3D環境是100 m×1 00 m×100 m的區域。在網絡中隨機選擇m個節點作為錨節點，分別令m取4、6、8、10。通信和測距半徑用R表示，2D環境中R=50 m，3D環境中R=60 m。測距誤差u服從高斯分布，均值取0，標準差分別取網絡邊長的2%、4%、6%、8%、10%。

3.2 不同錨節點數量對配準精度的影響

在2D和3D環境下分別進行實驗，以測試不同錨節點數量對配準精度的影響。理論上，2D空間坐標配準至少需要3個錨節點，3D至少需要4個，然而2D空間中錨節點可能存在的共線問題(3D空間中錨節點的共面問題)會放大配準誤差，從而影響本文對LS和PA的比較。因此，分別令m取4、6、8、10，測距誤差u服從均值為0，標準差為4的高斯分布。實驗結果如圖1所示。

圖1 不同錨節點數量對配準精度的影響Fig.1 Influence of the number of anchor nodes on the registration accuracy

由圖1可知，隨著錨節點數量的增加，無論在2D環境還是3D環境下，2種配準方法的MAE都呈下降趨勢，也即配準誤差在降低。在3D環境下，當只有4個錨節點參與配準時(理論上的最小值)，配準精度很低，且標準差很大，配準精度不穩定。這充分說明了坐標配準是協同定位的重要組成部分。將錨節點的數量增加至6個，相較于4個錨節點時，無論在2D還是在3D環境下，配準精度都有較大幅度的提高。繼續增加錨節點數量，配準精度有提高的趨勢，但收益不再明顯。在進行坐標配準時，可以在滿足最低要求的條件下，增加2～3個冗余錨節點來降低配準誤差。對于2種算法，在不同的維數、不同的錨節點數量下，PA的配準精度均高于LS，且標準差更小，更加穩定。以2D環境下6個錨節點為例，LS的MAE是2.465 m，PA的MAE是1.928 m，相較于LS算法，其MAE下降了約22%。在3D環境4個錨節點下，PA算法的優勢更加明顯。PA算法的計算復雜度高于LS，但考慮到錨節點數量較少，求解Q、s、T用到的矩陣規模都比較小，所以PA算法本身的計算復雜度并不高。

3.3 不同測距誤差對配準精度的影響

在2D和3D環境下分別進行實驗，以測試不同測距誤差對配準精度的影響。錨節點數量m=6。 測距誤差u的均值取0，標準差分別取網絡邊長的2%、4%、6%、8%、10%，實驗結果如圖2所示。隨著測距誤差的增大，兩種算法的配準精度都呈下降趨勢，這主要是由于協同定位算法本身造成的。無論在2D還是3D環境下，PA算法的配準精度都優于LS算法。以3D環境下u服從均值為0，標準差為2的高斯分布為例，LS算法的MAE是3.009 m，PA算法的MAE是2.353，相較于LS算法，其MAE下降了約22%。

圖2 不同測距誤差對配準精度的影響Fig.2 Influence of ranging errors on the registration accuracy

3.4 不同連通度對配準精度的影響

在2D環境下進行實驗，以測試不同節點平均連通度對配準精度的影響，節點平均連通度用deg表示。節點隨機布置后， deg主要通過通信半徑R調節， deg 分別取6、8、10、16。當通信半徑較小時，可能會出現某些網絡邊緣節點連通度為0的情況，此時可將該節點適當向網絡中心移動。其中，m=6，u服從均值為0，標準差為6的高斯分布。

實驗結果如圖3～6所示。

圖3 網絡平均連通度為6時的坐標配準Fig.3 Coordinate registration of deg=6

如圖3，當 deg=6時，經典MDS+LM的定位誤差較大 ，而LS算法配準時進一步放大了該誤差，圖3(b)的形狀與真實構型圖3(a)相差較大，圖3(c)與圖3(a)的形狀更加接近。隨著 deg的增加，定位算法的精度提高，配準后的圖形也更加接近真實構型。PA算法的配準精度始終要高于LS算法，特別是在網絡的邊緣區域，例如對比圖4(b)與圖4(c)的下端，對比圖5(b)與圖5(c)的左端。

圖4 網絡平均連通度為8時的坐標配準Fig.4 Coordinate registration of deg=8

圖5 網絡平均連通度為10時的坐標配準Fig.5 Coordinate registration of deg=10

圖6 網絡平均連通度為16時的坐標配準Fig.6 Coordinate registration of deg=16

4 結論

本文介紹了協同定位中的坐標配準問題，給出了基于最小二乘與基于普氏分析的坐標配準算法的主要步驟。通過大量的仿真實驗證明，坐標配準是協同定位的重要組成部分，一個合理的坐標配準體系可以體現協同定位算法的性能，否則可能會放大定位算法的誤差。本文的主要結論有2個方面：1)在不同維數的環境、不同錨節點數量、不同測距誤差、不同網絡節點平均連通度下，基于普氏分析的坐標配準均優于基于最小二乘的坐標配準，配準誤差降低約20%；2)設置配準所用的錨節點數量，2D環境下建議設置4～5個，3D環境下建議設置6～7個。在實驗的過程中，不論采用哪種配準算法，錨節點的構型都會對配準精度產生一定影響。目前采用的方法是適當增加錨節點數量來降低這種影響，進一步工作希望能夠定量地研究錨節點的構型對配準精度的影響。