無線傳感器網(wǎng)絡(luò)多維定標算法綜述

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

關(guān)鍵詞：多維定標算法

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

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

二、基于Metric MDS的定位算法

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

設(shè)有矩陣B，，可以得到矩陣D和矩陣B的關(guān)系，如式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）

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

（2-6）

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

標矩陣。

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

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

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

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

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

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

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

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

其中表示平均距離。

四、三維坐標轉(zhuǎn)換

在分布式的無線傳感器網(wǎng)絡(luò)定位中，多數(shù)情況計算出的坐標是局部相對坐標，每一個局部小區(qū)域內(nèi)有各自的相對坐標。為了得到統(tǒng)一的全局坐標，必須將局部坐標轉(zhuǎn)換到全局坐標系中去。

對于兩個不同的坐標系R1和R2而言，設(shè)點Xi1∈R1，Xi2∈R2，要將Xi1轉(zhuǎn)換到坐標系R2中，也就是要對目標坐標系進行相異的平移，旋轉(zhuǎn)和縮放，即需要三個變量，分別是平移向量，比例因子和旋轉(zhuǎn)矩陣。對于兩個三維坐標系而言，能夠?qū)⑵浠ハ噢D(zhuǎn)換的前提條件是，需要已知至少四個點分別在兩個坐標系中的坐標，即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] 袁文燕， 劉慧， 姜冬青. 矩陣論及應用. 化學工業(yè)出版社.2003.9. 43～62.

作者簡介

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