MDS與三邊定位相結(jié)合的多點(diǎn)相對(duì)定位算法

,,

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

0 引言

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

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

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

1 MDS-MAP算法

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

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

對(duì)傳統(tǒng)的MDS用于定位的MDS-MAP算法原理進(jìn)行深入推導(dǎo)。

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

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

設(shè)節(jié)點(diǎn)i的坐標(biāo)為(xi,yi,zi)，則有：

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

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

在此，不防構(gòu)造兩個(gè)矩陣R，X：

其中:Ii2=xi2+yi2+zi2

X即為節(jié)點(diǎn)的坐標(biāo)矩陣，則有:

D(2)=R+RT-2XTX

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

其中:

所以:

易知:

RJ=0,JRT=0

所以:

所以:

其中:U、V分別為對(duì)B進(jìn)行特征值分解的特征值組成的對(duì)角陣及其對(duì)應(yīng)的特征向量組成的矩陣。

JXT即為中心化后的各節(jié)點(diǎn)的相對(duì)坐標(biāo)。

2 MDS與三邊定位相結(jié)合定位算法

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

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

圖1 算法流程圖

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

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

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

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

對(duì)D′使用MDS，得到所選取節(jié)點(diǎn)的相對(duì)位置坐標(biāo)X。

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

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

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

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

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

設(shè)置壓力函數(shù):

化簡為:

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

寫作矩陣形式：

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

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

其中：

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

Xk+1=V+B(Xk)Xk

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

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

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

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

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

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

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

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

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

圖2 方法示意

3 仿真驗(yàn)證

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

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

圖3 隨機(jī)分布定位結(jié)果

圖4 隨機(jī)分布定位誤差

圖5 U型分布定位結(jié)果

圖6 U型分布定位誤差

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

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

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

表1 算法性能對(duì)比

4 結(jié)束語

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

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

在三邊定位向外擴(kuò)展時(shí)，會(huì)逐層傳遞誤差，增加定位結(jié)果不確定性。

該算法依然屬于一種集中式算法，計(jì)算負(fù)擔(dān)大，資源消耗多，與傳統(tǒng)的MDS-MAP算法在定位時(shí)間和計(jì)算速度上無顯著優(yōu)勢，甚至?xí)?/p>

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