,,

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

0 引言

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

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

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

1 MDS-MAP算法

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

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

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

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

其中:dij,i=1,2,3,…，n,j=1,2,3,…,n為節(jié)點i與節(jié)點j之間的距離，n為區(qū)域內節(jié)點的個數(shù)。

設節(jié)點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即為節(jié)點的坐標矩陣，則有:

D(2)=R+RT-2XTX

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

其中:

所以:

易知:

RJ=0,JRT=0

所以:

所以:

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

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

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

傳統(tǒng)的MDS-MAP算法雖然可以實現(xiàn)網(wǎng)絡集群定位，但通過上述分析仍存在一些問題：

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

圖1 算法流程圖

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

第一步：根據(jù)節(jié)點間測量的歐氏距離得出距離矩陣：

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

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

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

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

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

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

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

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

設置壓力函數(shù):

化簡為:

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

寫作矩陣形式：

對此，采用smacof算法，取輔助函數(shù)為：

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

其中：

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

Xk+1=V+B(Xk)Xk

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

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

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

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

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

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

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

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

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

圖2 方法示意

3 仿真驗證

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

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

圖3 隨機分布定位結果

圖4 隨機分布定位誤差

圖5 U型分布定位結果

圖6 U型分布定位誤差

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

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

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

表1 算法性能對比

4 結束語

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

在尋找包含連通節(jié)點最多的區(qū)域時，本文所采用的算法循環(huán)次數(shù)多，計算時間較長。

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

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

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