無線傳感器網絡多維定標算法綜述

摘 要：闡述了無線傳感器多維定標技術的原理，給出了兩種典型算法的推導，分析了三維坐標的轉換。

關鍵詞：多維定標算法

本文系2011年院級自然科學基金“集中式無線傳感器網絡三維定位算法研究”（XYKJ2011013）和2012年院級教改項目“基于proteus的《單片機原理》虛擬教學平臺的研究與應用”（JY1208）的階段性研究成果。一、多維技術原理

假設空間上n個對象點的任意第i個點和第j個點之間的相異（似）性以δij來表示，則可構成一個相異（似）性矩陣[δij]，設空間上n個對象點的坐標矩陣為X，則X是一個n×p的矩陣，每一行對應一個點的p維坐標。多維空間上對象點i和j的距離用dij表示，多維標度技術就是利用各對象點間的相異（似）性來構造多維空間上點的相對圖，并使得相異（似）性δij與距離dij盡可能的接近，即使得f（δij）≈dij，系數函數為Stress=Σ（f（δij）-dij）2

二、基于Metric MDS的定位算法

假設有n個對象點，對應的節點坐標為X=（x1，x2，…，xn）p，其中X是一個n×p的矩陣，表示n個節點的p維坐標，p=3。任意兩個節點間的距離已經獲得，則可以得到距離矩陣D=[dij]是一個n×n的方陣，表示點xi和xj之間的估算距離。若i=j則有dii=0，對于任意i和j有dij=dji，由歐氏距離公式得到距離平方矩陣D2=[d2ij]，如式2-1所示：

設有矩陣B，，可以得到矩陣D和矩陣B的關系，如式2-2：

（2-2）

對矩陣D2二次中心化，即對相應的坐標矩陣X中心化，使得

，即，由此可推導出式2-3：

上式可以寫成矩陣形式，即式2-4：

（2-4）

其中，為中心矩陣，In×n為n階單位矩陣，

e1×n[1，1，…，1]。對矩陣B進行特征值分解，如式2-5：

B=XXT=UVUT （2-5）

并保留三個最大的特征值和對應的特征向量來計算節點的三維坐標，設u1>u2>u3和v1>v2>v3分別為三個最大的特征向量和特征值，按式2-6計算節點的三維坐標：

（2-6）

其中U是由特征向量u1，u2，u3按列排列組成的矩陣，V是以，，為主對角元，其他元素為零的矩陣，則X即為節點的三維坐

標矩陣。

三、基于Non-metric MDS的定位算法

假設n個對象點在多維空間中的坐標用矩陣X表示，X是一個n×p維的矩陣，其中n表示對象點的數目，p代表坐標點的維數，則矩陣X中的第i行表示第i個對象點的p維坐標。

基于Non-metric MDS的定位算法根據給定的對象點之間的相異（似）性重構多維空間上各對象點的坐標和它們之間的距離，是一個反復迭代的計算過程，共分為三個階段：第一階段為初始化階段，可以采用某種算法粗略地計算節點的坐標只要保證對象點的初始坐標不相同即可，根據計算獲得的初始坐標從任意一個對象點的坐標X0開始計算對象點之間的歐式距離dij0。第二階段為非定標階段，根據第一階段獲得的歐式距離可以得到一個等級值，該值的意義為，如是通過構

建δi和dij0的單調回歸關系時產生的。δi和dij0必須滿足弱單調性要求：對于任意i，j，k，l，如果有δij<δkl則。為了得到可以采用一

種近似方法，例如PAV（pool adjacent violators）算法。PAV算法的過程為，首先由相異（似）性用δij的最小值開始，把鄰近的與每一個δij比較來確定是否滿足與對應的δij滿足單調關系。當存在一組連續的

值違背了與δij的單調關系時，就取這些值的平均值。第三階段為定標階段，根據X0和計算新坐標X1，再計算它們之間的歐式距離dij1，不

斷地重復第二和第三階段，直到滿足一定的系數要求即可。由此可見Non-metric MDS也可以看作是一種對Metric MDS的優化算法。

Non-metric MDS算法也采用類似于Metric MDS的系數方程來衡量計算結果與給定相異性的吻合度，其中Kruskal系數如式3-1：

其中表示平均距離。

四、三維坐標轉換

在分布式的無線傳感器網絡定位中，多數情況計算出的坐標是局部相對坐標，每一個局部小區域內有各自的相對坐標。為了得到統一的全局坐標，必須將局部坐標轉換到全局坐標系中去。

對于兩個不同的坐標系R1和R2而言，設點Xi1∈R1，Xi2∈R2，要將Xi1轉換到坐標系R2中，也就是要對目標坐標系進行相異的平移，旋轉和縮放，即需要三個變量，分別是平移向量，比例因子和旋轉矩陣。對于兩個三維坐標系而言，能夠將其互相轉換的前提條件是，需要已知至少四個點分別在兩個坐標系中的坐標，即Xi1和Xi2中至少有4個點同時屬于坐標系R1和R2。■

參考文獻

[1] H. Chen， D.Ping， Y.Xu， X.Li. A Novel Localization Scheme Based on RSS Data for Wireless Sensor Networks， Advanced Web and Network Technologies， and Applications， LNCS 2006.

[2] H. Chen， D.Ping， Y.Xu， X.Li. A robust location algorithm with biased extended kalman filtering of TDOA data for wireless sensor networks. In： Proceedings of International Conference on Wireless Communictions， Networking and Mobile Computing 2005， 883-886.

[3] 袁文燕， 劉慧， 姜冬青. 矩陣論及應用. 化學工業出版社.2003.9. 43～62.

作者簡介

閔輝（1983-），男，江西南昌人，江西科技學院商學院，本科，講師。研究方向：無線傳感器網絡。