基于非對(duì)稱廣義中心化矩陣的多維尺度定位算法

程飛，章平，周祺，秦心靜，楊彩鳳

（安徽工程大學(xué) 計(jì)算機(jī)與信息學(xué)院，蕪湖 241000）

隨著傳感器和通信設(shè)備尺寸、成本等限制迅速降低，無線傳感網(wǎng)絡(luò)不斷滲透到一些新的應(yīng)用領(lǐng)域，如精準(zhǔn)農(nóng)業(yè)、工業(yè)自動(dòng)化、汽車導(dǎo)航等［1-2］。在這些領(lǐng)域中，無線傳感器節(jié)點(diǎn)能夠?qū)囟取毫退俣鹊任锢砹窟M(jìn)行測量，結(jié)合節(jié)點(diǎn)位置信息，實(shí)現(xiàn)與位置有關(guān)的各類服務(wù)［3］。事實(shí)上，在很多現(xiàn)代的通信系統(tǒng)中，位置信息的價(jià)值幾乎等同于通信數(shù)據(jù)本身的信息價(jià)值［4］?？紤]到在對(duì)無線傳感器節(jié)點(diǎn)進(jìn)行部署的時(shí)候，大多數(shù)節(jié)點(diǎn)的位置很難被事先確定，因此，節(jié)點(diǎn)定位問題始終是無線傳感網(wǎng)絡(luò)中需要研究的重要課題。

根據(jù)測量的物理量不同，基于節(jié)點(diǎn)的定位方法可以分為兩類：基于測距（Range-based）和非測距（Range-free）的定位方法。Range-based算法通過測量節(jié)點(diǎn)之間的距離來實(shí)現(xiàn)定位，有三邊算法［5］、多邊算法［6］等。Range-free算法則無需測量節(jié)點(diǎn)之間的距離，而是根據(jù)網(wǎng)絡(luò)的連通性等信息來實(shí)現(xiàn)定位［7］，包括距離向量-跳段（Distance Vector-hop，DV-hop）定位［8］、凸規(guī)劃（Convex Op‐timization）定位以及質(zhì)心定位等算法［9，10］。其中，多維尺度（Multidimensional Scaling Map，MDS-MAP）算法［11］可以在Range-based的環(huán)境下，通過測量節(jié)點(diǎn)間距離實(shí)現(xiàn)定位；也能在Range-free的情況下，根據(jù)節(jié)點(diǎn)間的連通信息進(jìn)行位置估計(jì)，因此該算法在實(shí)際生活中被廣泛應(yīng)用。

最早將MDS算法引入無線傳感器網(wǎng)絡(luò)定位領(lǐng)域的是 Yi Shang等人［11］，其提出的 MDS-MAP算法首先使用經(jīng)典MDS算法獲得相對(duì)位置信息，然后通過MAP迭代，進(jìn)行集中式優(yōu)化。后來他們又提出了一種改進(jìn)的MDS-MAP（P）算法［12］，該算法的MAP部分可以通過分布式算法來計(jì)算位置，有利于降低能耗和提高魯棒性［13］。與MDS-MAP相同，該算法也存在MAP的迭代優(yōu)化，分布式可以降低算法復(fù)雜度，卻比較容易陷于局部極值。文獻(xiàn)［14］則是在MDS算法的基礎(chǔ)上，提出了一種距離自調(diào)整的MDS定位算法。該算法運(yùn)用3種方法對(duì)節(jié)點(diǎn)的兩跳距離進(jìn)行估算，然后自動(dòng)調(diào)整節(jié)點(diǎn)間的估計(jì)距離，從而提高定位精度。文獻(xiàn)［15］提出了一種基于MDS的改進(jìn)算法，通過構(gòu)建每個(gè)節(jié)點(diǎn)的局部地圖（相鄰節(jié)點(diǎn)構(gòu)成），然后拼接成全局地圖。其缺點(diǎn)是合并局部地圖存在誤差累積的問題。文獻(xiàn)［17］中通過考慮一般的中心化矩陣推廣了MDS算法，通過尋找滿足條件的中心化矩陣抑制多跳距離誤差，進(jìn)而提高定位精度。該算法存在兩個(gè)缺陷，一方面，該算法提出來的中心化矩陣是要求對(duì)稱的，但對(duì)稱性要求在構(gòu)造矩陣時(shí)會(huì)帶來額外的計(jì)算量，增加了算法的時(shí)間復(fù)雜度；另一方面，實(shí)際應(yīng)用中，如何構(gòu)造或者選擇合適的中心化矩陣尚未明確。

針對(duì)以往算法存在的不足，本文提出一種基于非對(duì)稱廣義中心化矩陣的多維尺度定位算法。該算法為了解決測量過程中產(chǎn)生的“測距錯(cuò)誤”距離矩陣對(duì)定位結(jié)果造成的影響，構(gòu)造了一般的行和為0的中心化矩陣，無需對(duì)稱。該方法既增加了對(duì)中心化矩陣的可選數(shù)量，也降低了構(gòu)造中心化矩陣的計(jì)算復(fù)雜度。對(duì)于一般的中心化矩陣，本文所提出的算法能很好地適應(yīng)網(wǎng)絡(luò)連通度不高和不規(guī)則的環(huán)境，獲得更高精度的定位結(jié)果。

特別地，對(duì)于測量過程中經(jīng)常出現(xiàn)的一些“測距錯(cuò)誤”節(jié)點(diǎn)，本文設(shè)計(jì)了相應(yīng)的中心化矩陣，降低“測距錯(cuò)誤”節(jié)點(diǎn)對(duì)全局的影響，提高其他節(jié)點(diǎn)定位精度。

1 MDS定位算法

假設(shè)m維空間中（一般m取2或3），隨機(jī)分布n個(gè)節(jié)點(diǎn)，i點(diǎn)坐標(biāo)為Xi=(Xi1,Xi2,…,Xim)T，j點(diǎn)坐標(biāo)為Xj=(Xj1,Xj2,…,Xjm)T，則節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的歐氏距離為：

定義n×m維坐標(biāo)矩陣：

距離平方矩陣：

在不考慮測量誤差的情況下：

對(duì)B進(jìn)行特征值分解［18］，則：

其中，Λ為n階對(duì)角矩陣。

經(jīng)過旋轉(zhuǎn)變換后的坐標(biāo)為：

2 非對(duì)稱廣義中心化矩陣的MDS定位算法

在經(jīng)典MDS算法中，采用的是已經(jīng)定義好的雙中心化矩陣，當(dāng)存在少量誤差較大的距離估計(jì)時(shí)，整體定位精度會(huì)受到這些誤差較大的距離估計(jì)的影響而降低。在文獻(xiàn)［17］中重新對(duì)中心化矩陣H1進(jìn)行約束，需滿足H1en=0，并要求H1對(duì)稱。

本文考慮到測距環(huán)節(jié)出現(xiàn)的一些“測距錯(cuò)誤”節(jié)點(diǎn)會(huì)影響定位精度，提出一類非對(duì)稱廣義中心化矩陣H，定義為k×n隨機(jī)矩陣，滿足He=0，其中e為全1矩陣。對(duì)H重新進(jìn)行約束，一是放寬了約束條件增加了H的可選數(shù)量，可以找到符合高定位精度需求的H；二是H無需對(duì)稱，能夠在構(gòu)造時(shí)減少計(jì)算量，降低時(shí)間復(fù)雜度。

根據(jù)以上約束條件，若：

則滿足：

任一滿足行和為0的矩陣都是非對(duì)稱中心化矩陣H的選擇。

將式（3）兩端同時(shí)左乘H，右乘HT，得到：

對(duì)A進(jìn)行SVD分解，可以得到

則：

令ξ1,ξ2,…,ξr是H的零空間的一組基向量，即：

3 仿真實(shí)驗(yàn)結(jié)果及分析

為了研究基于非對(duì)稱廣義中心化矩陣的MDS算法的定位性能，本文通過仿真實(shí)驗(yàn)和經(jīng)典MDS算法［16］、修正 MDS算法［17］進(jìn)行了對(duì)比。實(shí)驗(yàn)環(huán)境與場景：矩形隨機(jī)網(wǎng)絡(luò)、C型隨機(jī)網(wǎng)絡(luò)；隨機(jī)分布50個(gè)節(jié)點(diǎn)的2-D平面50m×50m區(qū)域。實(shí)驗(yàn)參數(shù)：節(jié)點(diǎn)間通信半徑r。節(jié)點(diǎn)分布如圖1所示。

圖1 節(jié)點(diǎn)分布圖

本文使用相對(duì)誤差［19］評(píng)價(jià)算法性能。通過Procrustes方法將相對(duì)地圖擬合到真實(shí)坐標(biāo)上面，消除相對(duì)坐標(biāo)通過反轉(zhuǎn)、平移、正交旋轉(zhuǎn)等操作帶來的不確定性，從而得到絕對(duì)坐標(biāo)。實(shí)驗(yàn)評(píng)價(jià)算法性能的準(zhǔn)則是通過計(jì)算節(jié)點(diǎn)真實(shí)坐標(biāo)與得到的估計(jì)坐標(biāo)間的均方誤差：

本文提出了利用節(jié)點(diǎn)間距離誤差作為評(píng)價(jià)算法的另一準(zhǔn)則。根據(jù)不同算法生成的相對(duì)地圖得到兩兩節(jié)點(diǎn)間的距離D?，和兩兩節(jié)點(diǎn)間的真實(shí)距離D作差（這里只考慮直接連通節(jié)點(diǎn)間距離，不考慮多跳距離），對(duì)所有節(jié)點(diǎn)間的距離誤差絕對(duì)值求和，然后比較距離誤差和定位誤差之間的關(guān)系來進(jìn)行驗(yàn)證。表示為：

（1）非對(duì)稱廣義中心化矩陣H的可行性驗(yàn)證

圖2 特定網(wǎng)絡(luò)拓?fù)?/p>

仿真結(jié)果顯示，經(jīng)典MDS算法利用Procrustes方法得到前3個(gè)節(jié)點(diǎn)坐標(biāo)為，A（-0.289 1，-0.123 6），B（4.178 8，0.070 7），C（3.110 4，4.052 9），相對(duì)誤差為0.050 3。本文所提算法通過Procrustes方法得到的結(jié)果為，A（0，0），B（4，0），C（3，4），前3個(gè)節(jié)點(diǎn)相對(duì)誤差為0。由此可以看出，非對(duì)稱中心化矩陣H能夠?qū)η?個(gè)節(jié)點(diǎn)精準(zhǔn)定位，完全消除了測距錯(cuò)誤節(jié)點(diǎn)帶來的負(fù)面影響。

在實(shí)際定位過程中，會(huì)有外界因素干擾導(dǎo)致測得的距離矩陣并不完全正確，從而影響整體的定位精度。在構(gòu)造H時(shí)可以通過合理的設(shè)計(jì)，假設(shè)第n個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)連通度不高，其多跳距離估計(jì)誤差較大，則可以減小H最后一列的值，降低與第n個(gè)節(jié)點(diǎn)相關(guān)的距離對(duì)整體的影響。極限情況就是假設(shè)H最后一列全是0，則第n個(gè)節(jié)點(diǎn)的測量完全不采用，最終定位后，等價(jià)于對(duì)前n-1個(gè)節(jié)點(diǎn)使用MDS算法定位，完全消除最后一個(gè)節(jié)點(diǎn)帶來的負(fù)面影響。

（2）距離誤差和定位精度的相關(guān)性驗(yàn)證

該實(shí)驗(yàn)主要比較三種算法在不同網(wǎng)絡(luò)拓?fù)湎拢S著通信半徑的不同，距離誤差和定位精度的關(guān)系。在實(shí)驗(yàn)場景的矩形網(wǎng)絡(luò)拓?fù)湎?，利用圖1的節(jié)點(diǎn)分布圖進(jìn)行實(shí)驗(yàn)。該實(shí)驗(yàn)的距離誤差和定位誤差關(guān)系如圖3、圖4所示。圖3為三種算法分別在通信半徑r=10 m、r=11 m、r=12 m、r=15 m的情況下運(yùn)行的結(jié)果；圖4為三種算法分別在通信半徑r=15 m、r=18 m、r=20 m、r=24 m的情況下運(yùn)行的結(jié)果。

圖3 矩形網(wǎng)絡(luò)不同通信半徑下距離誤差和定位誤差關(guān)系圖

由實(shí)驗(yàn)結(jié)果可以看出，在同種網(wǎng)絡(luò)拓?fù)?，不同通信半徑下，與經(jīng)典MDS算法相比，非對(duì)稱MDS算法的距離誤差會(huì)比修正MDS算法的結(jié)果更小，更集中，同時(shí)在定位性能方面提升更為顯著。圖4中，在C型網(wǎng)絡(luò)下r=15、r=18 m、r=20 m時(shí)，修正MDS算法平均定位誤差分別為：223.608 4，183.714 7，160.647 1；非對(duì)稱 MDS算法平均定位誤差分別為：202.745 1，177.604 3，150.902 5。因此，非對(duì)稱MDS算法能夠適應(yīng)不同的網(wǎng)絡(luò)拓?fù)浼巴ㄐ虐霃剑行У匾种乒?jié)點(diǎn)間距離誤差，以此提升定位精度。

圖4 C型網(wǎng)絡(luò)不同通信半徑下距離誤差和定位誤差關(guān)系圖

（3）連通度對(duì)定位精度的影響

該實(shí)驗(yàn)主要比較3種算法在不同連通度下的性能。在實(shí)驗(yàn)場景的矩形網(wǎng)絡(luò)和C型網(wǎng)絡(luò)下，節(jié)點(diǎn)部署如圖1所示，矩形網(wǎng)絡(luò)連通度分別為5.84，7.08，8.32，11.92，16.72，C 型網(wǎng)絡(luò)連通度為11，14.04，17.20，21.20，23.32。實(shí)驗(yàn)結(jié)果如圖 5、圖6所示（連通度=節(jié)點(diǎn)間連通次數(shù)/節(jié)點(diǎn)數(shù)）。

圖5 矩形網(wǎng)絡(luò)連通度的影響

圖6 C型網(wǎng)絡(luò)連通度的影響

圖5、圖6可以看出，在不同的網(wǎng)絡(luò)連通度下，非對(duì)稱MDS算法定位性能優(yōu)于經(jīng)典MDS算法和修正MDS算法。在連通度較低的情況下，本文提出的算法定位精度有明顯的提高，尤其在C型網(wǎng)絡(luò)環(huán)境下，定位精度提升幅度會(huì)更大。因此，與經(jīng)典MDS算法和修正MDS算法相比，非對(duì)稱MDS算法在連通度不高和不規(guī)則網(wǎng)絡(luò)拓?fù)湎逻m應(yīng)性更高，在實(shí)際定位中具有明顯的優(yōu)勢。

4 結(jié)論

針對(duì)以往算法容易受到“錯(cuò)誤”距離估計(jì)影響的問題，本文提出了基于非對(duì)稱廣義中心化矩陣的MDS算法。該算法推廣了已有的中心化矩陣，構(gòu)造了一類中心化矩陣用于“測距錯(cuò)誤”節(jié)點(diǎn)的篩選，降低其對(duì)整體定位效果的影響；在距離誤差和定位精度相關(guān)性驗(yàn)證的算法仿真對(duì)比實(shí)驗(yàn)中，非對(duì)稱MDS算法表現(xiàn)出了比修正MDS更好的性能，能更好地抑制距離誤差，以此提升定位精度；在連通度對(duì)定位精度影響的算法仿真對(duì)比實(shí)驗(yàn)中，本文提出的算法通過選擇有助于抑制“錯(cuò)誤”距離的中心化矩陣，有效地提高了節(jié)點(diǎn)對(duì)連通度不高和不規(guī)則網(wǎng)絡(luò)的適應(yīng)性，改善了定位性能。