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

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

（安徽工程大學 計算機與信息學院，蕪湖 241000）

隨著傳感器和通信設備尺寸、成本等限制迅速降低，無線傳感網絡不斷滲透到一些新的應用領域，如精準農業、工業自動化、汽車導航等［1-2］。在這些領域中，無線傳感器節點能夠對溫度、壓力和速度等物理量進行測量，結合節點位置信息，實現與位置有關的各類服務［3］。事實上，在很多現代的通信系統中，位置信息的價值幾乎等同于通信數據本身的信息價值［4］。考慮到在對無線傳感器節點進行部署的時候，大多數節點的位置很難被事先確定，因此，節點定位問題始終是無線傳感網絡中需要研究的重要課題。

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

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

針對以往算法存在的不足，本文提出一種基于非對稱廣義中心化矩陣的多維尺度定位算法。該算法為了解決測量過程中產生的“測距錯誤”距離矩陣對定位結果造成的影響，構造了一般的行和為0的中心化矩陣，無需對稱。該方法既增加了對中心化矩陣的可選數量，也降低了構造中心化矩陣的計算復雜度。對于一般的中心化矩陣，本文所提出的算法能很好地適應網絡連通度不高和不規則的環境，獲得更高精度的定位結果。

特別地，對于測量過程中經常出現的一些“測距錯誤”節點，本文設計了相應的中心化矩陣，降低“測距錯誤”節點對全局的影響，提高其他節點定位精度。

1 MDS定位算法

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

定義n×m維坐標矩陣：

距離平方矩陣：

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

對B進行特征值分解［18］，則：

其中，Λ為n階對角矩陣。

經過旋轉變換后的坐標為：

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

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

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

根據以上約束條件，若：

則滿足：

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

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

對A進行SVD分解，可以得到

則：

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

3 仿真實驗結果及分析

為了研究基于非對稱廣義中心化矩陣的MDS算法的定位性能，本文通過仿真實驗和經典MDS算法［16］、修正 MDS算法［17］進行了對比。實驗環境與場景：矩形隨機網絡、C型隨機網絡；隨機分布50個節點的2-D平面50m×50m區域。實驗參數：節點間通信半徑r。節點分布如圖1所示。

圖1 節點分布圖

本文使用相對誤差［19］評價算法性能。通過Procrustes方法將相對地圖擬合到真實坐標上面，消除相對坐標通過反轉、平移、正交旋轉等操作帶來的不確定性，從而得到絕對坐標。實驗評價算法性能的準則是通過計算節點真實坐標與得到的估計坐標間的均方誤差：

本文提出了利用節點間距離誤差作為評價算法的另一準則。根據不同算法生成的相對地圖得到兩兩節點間的距離D?，和兩兩節點間的真實距離D作差（這里只考慮直接連通節點間距離，不考慮多跳距離），對所有節點間的距離誤差絕對值求和，然后比較距離誤差和定位誤差之間的關系來進行驗證。表示為：

（1）非對稱廣義中心化矩陣H的可行性驗證

圖2 特定網絡拓撲

仿真結果顯示，經典MDS算法利用Procrustes方法得到前3個節點坐標為，A（-0.289 1，-0.123 6），B（4.178 8，0.070 7），C（3.110 4，4.052 9），相對誤差為0.050 3。本文所提算法通過Procrustes方法得到的結果為，A（0，0），B（4，0），C（3，4），前3個節點相對誤差為0。由此可以看出，非對稱中心化矩陣H能夠對前3個節點精準定位，完全消除了測距錯誤節點帶來的負面影響。

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

（2）距離誤差和定位精度的相關性驗證

該實驗主要比較三種算法在不同網絡拓撲下，隨著通信半徑的不同，距離誤差和定位精度的關系。在實驗場景的矩形網絡拓撲下，利用圖1的節點分布圖進行實驗。該實驗的距離誤差和定位誤差關系如圖3、圖4所示。圖3為三種算法分別在通信半徑r=10 m、r=11 m、r=12 m、r=15 m的情況下運行的結果；圖4為三種算法分別在通信半徑r=15 m、r=18 m、r=20 m、r=24 m的情況下運行的結果。

圖3 矩形網絡不同通信半徑下距離誤差和定位誤差關系圖

由實驗結果可以看出，在同種網絡拓撲，不同通信半徑下，與經典MDS算法相比，非對稱MDS算法的距離誤差會比修正MDS算法的結果更小，更集中，同時在定位性能方面提升更為顯著。圖4中，在C型網絡下r=15、r=18 m、r=20 m時，修正MDS算法平均定位誤差分別為：223.608 4，183.714 7，160.647 1；非對稱 MDS算法平均定位誤差分別為：202.745 1，177.604 3，150.902 5。因此，非對稱MDS算法能夠適應不同的網絡拓撲及通信半徑，有效地抑制節點間距離誤差，以此提升定位精度。

圖4 C型網絡不同通信半徑下距離誤差和定位誤差關系圖

（3）連通度對定位精度的影響

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

圖5 矩形網絡連通度的影響

圖6 C型網絡連通度的影響

圖5、圖6可以看出，在不同的網絡連通度下，非對稱MDS算法定位性能優于經典MDS算法和修正MDS算法。在連通度較低的情況下，本文提出的算法定位精度有明顯的提高，尤其在C型網絡環境下，定位精度提升幅度會更大。因此，與經典MDS算法和修正MDS算法相比，非對稱MDS算法在連通度不高和不規則網絡拓撲下適應性更高，在實際定位中具有明顯的優勢。

4 結論

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