MDS與三邊定位相結合的多點相對定位算法

,,

(1.衛星導航系統與裝備技術國家重點實驗室，石家莊 050081；2.中國電子科技集團公司第五十四研究所，石家莊 050081)

0 引言

PNT體系即定位(Positioning)、導航(Navigation)、授時體系(Timing)組成的時空體系，是我們得以在紛繁信息中準確描述時間和空間的關鍵技術。而定位導航的核心是準確，及時，全面地獲得待測目標的位置信息和運動參數，并為其提供下一時刻的路徑規劃，為了實現這一目的，需要定位導航系統具有精準定位能力和抗干擾能力。傳統的PNT信息大多由全球衛星導航系統提供，如美國的GPS、歐洲的伽利略、俄羅斯的格洛納斯，還有中國的北斗。近幾十年來，衛星導航不斷發展，應用廣泛，PNT對衛星導航系統形成了強烈依賴性，但衛星導航存在一些固有的缺點，如信號強度弱、穿透能力差、易被干擾欺騙和易受攻擊等。一旦衛星導航系統受到攻擊，停止工作，己方編隊將失去空中協同運作能力。因此，為了構建完整的PNT體系，發展備份導航定位顯得尤為重要。

近年來，PNT技術體系的發展對備份導航技術提出了更高的要求，而集群的相對定位技術是備份導航的關鍵技術之一。開展拒止環境下動態網絡集群定位技術的研究是發展備份導航領域的硬性需求，具有突出的研究價值。實現集群相對定位的方式之一就是多維標度法。

多維標度法(Multidimensional-Scaling，MDS)是一種把空間中物體的相似性轉換為空間坐標的數據分析方法，它是利用各節點間的相似性信息來確定坐標。最早由Shang等人提出了將MDS用于定位的MDS-MAP算法，利用節點間的距離信息代替相似性，構造相應的距離平方矩陣，然后中心化，求特征值、特征向量，進而得到相對坐標[1]。不難發現，MDS-MAP算法的基礎是要獲得所有節點之間的距離信息，但在實際中，由于測量設備和外部環境的影響，很難獲得所有距離信息，而用最短路徑等方法估計得出的距離矩陣存在較大誤差，降低了定位精度。為了提高定位精度，本文提出一種MDS與三邊定位相結合的定位方式，以此彌補傳統MDS在距離信息上的硬性需求，這種方法兼顧考慮了MDS的最短路徑問題和三邊定位的誤差傳遞層數問題，是一種對二者的優勢結合算法。

1 MDS-MAP算法

多維標度技術源于心理測量學和精神物理學，最早被心理測量學家或數學家和統計學家運用于心理測量領域。作為一種數據分析技術，MDS通過構建一個或多個矩陣來表示物體間的距離或相異程度，并在低維空間中(一般為二維或者三維)尋找一個合適的點間距離分布[2]。多維標度分析技術的主要優勢是，即使在少量錨節點的情況下，也可以使用該技術獲得精確地位置估計。但其也有本身的缺陷，包括集中式的算法對中心節點能耗較大等等[3]。

經典的度量多維標度技術中，假設已知各實體間的歐氏距離，距離值即代表實體間的相異性，其根本思想是對相異性矩陣進行數學方法上的重構，使其滿足脅強系數的要求[4]。

對傳統的MDS用于定位的MDS-MAP算法原理進行深入推導。

首先由已知的實體間的距離信息確定集群的距離平方矩陣:

其中:dij,i=1,2,3,…，n,j=1,2,3,…,n為節點i與節點j之間的距離，n為區域內節點的個數。

設節點i的坐標為(xi,yi,zi)，則有：

dij2=(xi-xj)2+(yi-yj)2+(zi-zj)2=

xi2+yi2+zi2+xj2+yj2+zj2-2xixj-2yiyj-2zizj

在此，不防構造兩個矩陣R，X：

其中:Ii2=xi2+yi2+zi2

X即為節點的坐標矩陣，則有:

D(2)=R+RT-2XTX

對D(2)進行雙重中心化，即在D(2)的兩邊同時乘以中心矩陣J，用矩陣B表示D2的雙中心形式，得到:

其中:

所以:

易知:

RJ=0,JRT=0

所以:

所以:

其中:U、V分別為對B進行特征值分解的特征值組成的對角陣及其對應的特征向量組成的矩陣。

JXT即為中心化后的各節點的相對坐標。

2 MDS與三邊定位相結合定位算法

傳統的MDS-MAP算法雖然可以實現網絡集群定位，但通過上述分析仍存在一些問題：

需要知道所有節點之間的相對測量距離，但在實際中由于資源的限制很難實現，而為了解決這個問題最常用的一種方法就是用最短路徑代替多跳之間的距離，但這種方法存在不確定性，偏差較大，會對定位精度造成很大影響[5-6]。

圖1 算法流程圖

為了解決最短路徑帶來的不確定性問題，提出一種MDS與三邊定位相結合的定位方式，這種方法的基本原理是先對一部分單跳節點使用MDS進行相對定位，然后這些節點作為錨節點，對其他節點進行三邊定位，逐層擴展，直至實現全網的定位。這種方法有效的解決了最短路徑代替多跳距離所帶來的誤差問題，相較于全部使用三邊定位，也減小了誤差擴展層數，對定位精度有很大提升，具體步驟如下：

第一步：根據節點間測量的歐氏距離得出距離矩陣：

若i、j兩點間距離不可測，則直接令dij=0，不再以最短路徑替代。

第二步：尋找包含最多節點的區域，使得該區域內所有節點都相互連通，即所有節點間距均可測量。即在矩陣D中選取m行和對應序號相同的m列，使得選取行列在矩陣D中的交點除對角元素外全部不為零，選取使m值最大的行列，并將其交點按在D中的排列提出，構成新的距離矩陣：

對D′使用MDS，得到所選取節點的相對位置坐標X。

這一步的目的是為了找到集群中最大的全連通結構，并確定其相對位置，但在實際操作中，尋找最大全連通結構的算法復雜，運行時間長，若根據測距信息逐個遍歷，耗時久，計算資源消耗大[7]，因此為了簡化算法，降低計算時間，采用一種從概率上進行優化的方法：

1)在獲得距離矩陣D后，根據集群包含的節點數量，設置一個閥值ε，當找到ε個全連通節點時，則停止尋找，執行下一步三邊定位算法。

2)在矩陣D中舍棄與其他節點連通度最低的節點所對應的行列[8]，檢查剩余D矩陣是否為除對角元素外全不為零矩陣，若滿足則判斷其中節點數是否大于閥值ε，若小于，則在此基礎上對以舍棄節點進行搜索，若大于，則執行MDS算法，若不滿足則重復此步驟。

這樣可以在定位精度和運行時間之間有一個權衡，是算法趨向最優化。

而由于下一步的三邊定位算法是逐層向外擴展，所以定位誤差也會逐層積累，越來越大，所以這就要求使用MDS算法定位的作為下一步的錨節點的節點具有較高的定位精度，因此在執行MDS算法之后在此處進行一次迭代校正[9]，具體方法如下：

設置壓力函數:

化簡為:

其中:δij表示距離估計量，可由MDS定位結果的坐標計算得出，dij(X)為測量距離。

寫作矩陣形式：

對此，采用smacof算法，取輔助函數為：

g(X,Z)=C+trXTVX-2trXTB(Z)Z

其中：

令g(X,Z)一階導數為零，即可得到{XK}序列的更新公式：

Xk+1=V+B(Xk)Xk

第三步：對剩余節點進行搜索，找出與上述已定位區域存在兩個或兩個以上連通的節點，并利用三邊定位的方法對其進行定位，得出定位結果后將其歸于該區域內，然后繼續對剩余節點進行搜索，直到包含所有節點。

若與區域內兩個以上的節點連通，連接的節點坐標分別為(x1,y1)、(x2,y2)、…、(xn,yn)，待求節點的坐標為(xc,yc)，則有以下方程組：

這里可以使用最小二乘估計來估計待測節點的坐標，這樣得出的估計值比只選用其中兩個節點進行三邊定位的結果要準確，誤差更小。

而當作為要定位的節點的錨節點數量較多時，由于我們采用的MDS與三邊定位相結合的算法架構上是從中間向周圍蔓延的，所以相較于錨節點分布在節點四周的情況，這種方法會使錨節點分布在一側，在使用三邊定位時，更有可能會出現共線和定位誤差較大的情況，最小二乘也無法有效解決此類問題，因此，在這里采用一種改進的組合三邊定位算法，具體步驟如下：

1)從要定位節點的鄰居錨節點中多次選擇不同節點進行三邊定位，獲得一系列候選節點。

2)對候選節點集進行過濾，濾除由于共線和非正常測距誤差造成的異常定位結果[10]，對剩余節點求均值作為最終定位結果。

這樣的處理方式有效解決了三邊定位的不穩定性，將定位誤差穩定在較低水平，大大緩解了其誤差傳播與積累問題，剔除了誤差較大的異常定位結果，增加了算法穩定性。

在擴展到最外層節點的時候，有可能會出現外層節點只與區域內一個節點連通，此時在只獲得距離信息，沒有其他技術支持的條件下，可以使用最短路徑來獲得間距，然后局部使用MDS或者三邊定位，這樣雖然會造成個別節點的定位結果偏離，但整體而言，影響較小。

如圖2所示，若整個集群中最多包含5個節點可以兩兩連通，則先對虛線內的這5個節點使用MDS，得出相對坐標后，再對其他和區域內節點兩個或兩個以上連通的節點進行三邊定位，依次進行。

圖2 方法示意

3 仿真驗證

針對本文提出的MDS與三邊定位相結合的定位方式，考慮在不同環境下，算法的適應性，分別在隨機分布和U型分布兩種分布條件下，對比傳統的使用最短路徑代替多跳距離的定位方式，進行節點的布置，驗證算法性能，分析算法的優越性和不足，確定算法的后續優化方向。

參數設置：在200×200的區域內設置20個隨機分布的節點來模擬集群分布，規定節點的有效測距范圍是50，分別對其使用最短路徑代替多跳的傳統MDS和本文提出的MDS，三邊定位相結合的方式進行定位，并從定位精度，計算復雜度和適用條件等方面對比分析本文所提算法的優劣性。仿真結果如圖3～5所示。

圖3 隨機分布定位結果

圖4 隨機分布定位誤差

圖5 U型分布定位結果

圖6 U型分布定位誤差

圖3和圖5中，節點表示各節點的真實位置，△表示使用最短路徑代替多跳距離的傳統MDS定位結果，O表示使用本文提出的MDS和三邊定位結合的定位結果，從圖3中可以直觀看出，在隨機分布的區域中，本文所提出的方法定位精度明顯優于傳統MDS，且不會出現大幅度的偏移。從圖5中可以看出，在U型分布的區域中，本文所提方法的定位結果依然與節點實際位置保持一致，偏差不大，而傳統的MDS算法較之隨機分布的情況，在U型分布的條件下，定位結果出現較大偏離。

圖4和圖6表示兩種方法的定位結果和節點真實位置的歐氏距離差的分布情況，可以看出本文所提出的方法的誤差相對較小，且平穩維持，而傳統MDS的誤差較大，且波動幅度較大。且本文所提算法在隨機分布和U型分布的區域內定位誤差基本保持一致，算法的適應能力強，而傳統的MDS在U型分布下由于分布更為極端導致了連通度的降低，相較于隨機分布的構型，誤差整體增大，適應能力差。

表1顯示了MDS三邊定位算法與傳統MDS定位算法的性能比較，從表中可以看出，無論是隨機分布網絡還是U型分布網絡，所提算法的定位性能都明顯高于傳統MDS，且對網絡構型的影響不敏感。但是從算法的執行時間來看，所提算法的運行時間略高于傳統MDS，而且隨著拓撲結構的變化會產生較大波動，這是由于固有的集中式計算架構所決定的，其計算復雜度相較于傳統MDS-MAP算法有所增加，所以造成了算法運行時間的增長，若是用于高動態的集群網絡的定位，則無法滿足實時性的要求，所以，也為后續算法的優化提供了方向。

表1 算法性能對比

4 結束語

本文所提出的MDS與三邊定位相結合的定位方法定位精度較高，適應能力強，相較于傳統的MDS-MAP算法，解決了由于最短路徑帶來的較大定位誤差問題，相較于傳統的三邊定位算法，減小了其誤差傳遞層數，將MDS和三邊定位進行優勢互補，用盡可能簡潔的算法實現高精度定位。但該算法仍存在一些不足：

在尋找包含連通節點最多的區域時，本文所采用的算法循環次數多，計算時間較長。

在三邊定位向外擴展時，會逐層傳遞誤差，增加定位結果不確定性。

該算法依然屬于一種集中式算法，計算負擔大，資源消耗多，與傳統的MDS-MAP算法在定位時間和計算速度上無顯著優勢，甚至會偏慢。

針對上述的三點不足，后續將繼續在簡化算法計算量和減小定位誤差方面做深入研究，推導更簡潔的尋優算法，尋求一種適用于算法的分布式計算架構，完善本文所提算法，進一步提升定位精度。