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

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

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

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

二、基于Metric MDS的定位算法

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

設(shè)有矩陣B，，可以得到矩陣D和矩陣B的關(guān)系，如式2-2：

（2-2）

對(duì)矩陣D2二次中心化，即對(duì)相應(yīng)的坐標(biāo)矩陣X中心化，使得

，即，由此可推導(dǎo)出式2-3：

上式可以寫(xiě)成矩陣形式，即式2-4：

（2-4）

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

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

B=XXT=UVUT （2-5）

并保留三個(gè)最大的特征值和對(duì)應(yīng)的特征向量來(lái)計(jì)算節(jié)點(diǎn)的三維坐標(biāo)，設(shè)u1>u2>u3和v1>v2>v3分別為三個(gè)最大的特征向量和特征值，按式2-6計(jì)算節(jié)點(diǎn)的三維坐標(biāo)：

（2-6）

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

標(biāo)矩陣。

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

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

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

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

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

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

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

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

其中表示平均距離。

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

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

對(duì)于兩個(gè)不同的坐標(biāo)系R1和R2而言，設(shè)點(diǎn)Xi1∈R1，Xi2∈R2，要將Xi1轉(zhuǎn)換到坐標(biāo)系R2中，也就是要對(duì)目標(biāo)坐標(biāo)系進(jìn)行相異的平移，旋轉(zhuǎn)和縮放，即需要三個(gè)變量，分別是平移向量，比例因子和旋轉(zhuǎn)矩陣。對(duì)于兩個(gè)三維坐標(biāo)系而言，能夠?qū)⑵浠ハ噢D(zhuǎn)換的前提條件是，需要已知至少四個(gè)點(diǎn)分別在兩個(gè)坐標(biāo)系中的坐標(biāo)，即Xi1和Xi2中至少有4個(gè)點(diǎn)同時(shí)屬于坐標(biāo)系R1和R2?！?/p>

參考文獻(xiàn)

[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īng)用. 化學(xué)工業(yè)出版社.2003.9. 43～62.

作者簡(jiǎn)介

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