改進(jìn)的分布式無線傳感器網(wǎng)絡(luò)多維標(biāo)度定位算法

劉健苗，許新忠，黃書廣，李哲(.中訊郵電咨詢設(shè)計院有限公司，鄭州450007;.河南藝術(shù)職業(yè)學(xué)院，鄭州45000)

改進(jìn)的分布式無線傳感器網(wǎng)絡(luò)多維標(biāo)度定位算法

劉健苗1，許新忠2*，黃書廣1，李哲2
(1.中訊郵電咨詢設(shè)計院有限公司，鄭州450007;2.河南藝術(shù)職業(yè)學(xué)院，鄭州450001)

為提高無線傳感器網(wǎng)絡(luò)集中式多維標(biāo)度MDS-MAP算法的定位精度，提出了一種改進(jìn)的基于MDS的分布式定位算法。該算法在構(gòu)建距離矩陣時引入Euclidean算法距離估算思想，同時采用一種優(yōu)化的基于最小二乘逼近的坐標(biāo)轉(zhuǎn)換方法實(shí)現(xiàn)節(jié)點(diǎn)由相對坐標(biāo)到絕對坐標(biāo)的轉(zhuǎn)換。實(shí)驗結(jié)果顯示，與經(jīng)典MDS-MAP算法相比，改進(jìn)算法在多種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下均能有效提高節(jié)點(diǎn)的定位精度。

無線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)定位;坐標(biāo)轉(zhuǎn)換;分布式;多維標(biāo)度

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由密集部署在監(jiān)測區(qū)域內(nèi)的大量功能和結(jié)構(gòu)完全相同的廉價傳感器節(jié)點(diǎn)通過節(jié)點(diǎn)間的多跳無線通信而形成的自組織網(wǎng)絡(luò)系統(tǒng)［1］。作為一種全新的信息感知及處理技術(shù)，近年來無線傳感器網(wǎng)絡(luò)被廣泛應(yīng)用在災(zāi)害監(jiān)測、醫(yī)療衛(wèi)生和工業(yè)生產(chǎn)等領(lǐng)域，這些應(yīng)用大多與傳感器節(jié)點(diǎn)的位置信息密不可分，缺少位置信息支持的監(jiān)測信息通常是毫無意義的［2-3］。同時，精確獲取節(jié)點(diǎn)位置信息還有助于提高路由效率，降低節(jié)點(diǎn)能耗，延長網(wǎng)絡(luò)生命周期［4］。全球定位系統(tǒng)是目前應(yīng)用最廣的定位技術(shù)，具有定位精度高、時效性強(qiáng)等優(yōu)點(diǎn)，但能耗大，成本高，不適于遮蔽環(huán)境的特點(diǎn)導(dǎo)致其無法規(guī)模應(yīng)用于無線傳感器網(wǎng)絡(luò);而人工定位又因為測量工作量極大也不適于節(jié)點(diǎn)數(shù)量巨大的無線傳感器網(wǎng)絡(luò)［5］。因此必須結(jié)合傳感器網(wǎng)絡(luò)的自身特點(diǎn)來實(shí)現(xiàn)節(jié)點(diǎn)的自定位。

節(jié)點(diǎn)定位技術(shù)作為無線傳感器網(wǎng)絡(luò)研究領(lǐng)域的基礎(chǔ)支撐技術(shù)，已得到學(xué)術(shù)界的廣泛研究，多種定位算法相繼被提出。哥倫比亞大學(xué)Shang Yi等人將多維標(biāo)度技術(shù)MDS(Multidimensional Scaling)［6］應(yīng)用到Ad-Hoc網(wǎng)絡(luò)定位中，提出了經(jīng)典MDS-MAP算法［7］。該算法僅需少量錨節(jié)點(diǎn)便可實(shí)現(xiàn)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的定位，在精準(zhǔn)測距條件下定位精度很高。然而，集中式定位模式導(dǎo)致其在網(wǎng)絡(luò)規(guī)模較大時計算復(fù)雜度很高，同時該算法在網(wǎng)絡(luò)拓?fù)洳灰?guī)則的情況下定位誤差較大。為提升定位精度，研究人員相繼提出多種基于MDS的改進(jìn)算法，如分布式MDS算法［4，8-9］，加權(quán)MDS算法［10］，非線性濾波MDS算法［3］以及距離重構(gòu)MDS算法［11］等，它們在特定條件下均取得了較好的定位效果。然而，這些改進(jìn)算法都需要基于節(jié)點(diǎn)距離信息進(jìn)行坐標(biāo)計算，在精準(zhǔn)測距的理想狀態(tài)下，借助錨節(jié)點(diǎn)的絕對坐標(biāo)經(jīng)過線性變換來定位其他未知節(jié)點(diǎn)是沒有問題的。但是往往節(jié)點(diǎn)測距范圍有限，由此獲得的距離矩陣并不準(zhǔn)確，需要采用更優(yōu)的坐標(biāo)變換方法來減少未知節(jié)點(diǎn)定位的誤差。

針對MDS-MAP及其相關(guān)改進(jìn)算法存在的問題，本文在構(gòu)造節(jié)點(diǎn)距離矩陣時引入Euclidean算法［12］距離估算思想，同時采用一種更為有效的坐標(biāo)轉(zhuǎn)換方法優(yōu)化原算法中的坐標(biāo)轉(zhuǎn)換過程。實(shí)驗結(jié)果表明，改進(jìn)算法在提高節(jié)點(diǎn)定位精度的同時，降低了算法的時間復(fù)雜度。

1 MDS-MAP算法及分析

MDS-MAP算法利用數(shù)學(xué)心理學(xué)中的多維標(biāo)度分析技術(shù)，以節(jié)點(diǎn)間距離信息構(gòu)造距離相異性矩陣，并對其雙重中心化后再進(jìn)行特征分解，最后借助錨節(jié)點(diǎn)坐標(biāo)構(gòu)造多維空間中節(jié)點(diǎn)的絕對坐標(biāo)圖。

1.1 MDS-MAP算法流程

經(jīng)典MDS-MAP算法可分為以下3個步驟［5］:①各節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播其路由信標(biāo)，節(jié)點(diǎn)利用系統(tǒng)建立路由的過程采集來自其他節(jié)點(diǎn)的信號強(qiáng)度并保存待發(fā)，當(dāng)經(jīng)過一定次數(shù)的發(fā)送以后，認(rèn)為節(jié)點(diǎn)已經(jīng)采集了所有鄰居節(jié)點(diǎn)的信號強(qiáng)度，每個節(jié)點(diǎn)將這些鄰居節(jié)點(diǎn)信號強(qiáng)度發(fā)送至中心節(jié)點(diǎn)(通常中心節(jié)點(diǎn)是PC機(jī))，由中心節(jié)點(diǎn)生成網(wǎng)絡(luò)拓?fù)溥B通圖。在此，信號強(qiáng)度被轉(zhuǎn)換成節(jié)點(diǎn)間距賦予每條邊，當(dāng)節(jié)點(diǎn)間信號強(qiáng)度有效時，就使用該值來估計距離，當(dāng)僅擁有連通性信息時，則為該邊賦值1，最后采用最短路徑算法(如Dijkstra算法或Floyd算法)生成節(jié)點(diǎn)距離矩陣;②對距離矩陣應(yīng)用多維標(biāo)度技術(shù)，生成2維或3維相對坐標(biāo)系統(tǒng);③借助少量錨節(jié)點(diǎn)(2維不少于3個，3維不少于4個)，經(jīng)過線性變換將相對坐標(biāo)系統(tǒng)轉(zhuǎn)換成絕對坐標(biāo)系統(tǒng)。

1.2 MDS-MAP算法坐標(biāo)轉(zhuǎn)換方法

通過多維標(biāo)度技術(shù)獲得的節(jié)點(diǎn)坐標(biāo)是相對坐標(biāo)，需要參考錨節(jié)點(diǎn)的絕對坐標(biāo)，經(jīng)過平移、旋轉(zhuǎn)和翻轉(zhuǎn)等一系列線性坐標(biāo)變換，將相對坐標(biāo)轉(zhuǎn)換到錨節(jié)點(diǎn)所在的絕對坐標(biāo)系中去。下面以二維傳感器網(wǎng)絡(luò)為例，對MDS-MAP算法的坐標(biāo)轉(zhuǎn)換方法進(jìn)行討論。

令二維傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)為n，錨節(jié)點(diǎn)數(shù)為k(k≥2);X=［xij］2*n=［X1，X2，…，Xn］為節(jié)點(diǎn)的相對坐標(biāo)，Y=［yij］2*n=［Y1，Y2，…，Yn］為其對應(yīng)的絕對坐標(biāo)，假設(shè)Y1，Y2，…，Yk為錨節(jié)點(diǎn)的絕對坐標(biāo)。

平移變換可通過X'i=Xi+X0將坐標(biāo)向量Xi轉(zhuǎn)換成X'i，其中X0=［a b］T由各錨節(jié)點(diǎn)在不同坐標(biāo)系下對應(yīng)之矢量差的均值計算得出;坐標(biāo)向量Xi旋轉(zhuǎn)一個角度α即Xαi=Q1Xi可實(shí)現(xiàn)旋轉(zhuǎn)變換，其中

在相對坐標(biāo)X和錨節(jié)點(diǎn)絕對坐標(biāo)Y1，Y2，…，Yk已知的情況下，有

故

對錨節(jié)點(diǎn)以外的節(jié)點(diǎn)進(jìn)行相同的坐標(biāo)變化可得

結(jié)合式(4)、式(5)可得其余節(jié)點(diǎn)的絕對坐標(biāo)

1.3 MDS-MAP算法誤差分析

在Range-Based條件下，MDS-MAP算法中節(jié)點(diǎn)的測距誤差是引起定位誤差的主要原因。當(dāng)所有節(jié)點(diǎn)間的幾何距離都正確時，MDS-MAP算法能給出沒有誤差的解。然而受到節(jié)點(diǎn)通信范圍的制約，該算法對于不能直接測距的非鄰居節(jié)點(diǎn)間的歐氏距離以最短路徑距離來代替，在大多數(shù)情況下這樣的估算會放大節(jié)點(diǎn)間的實(shí)際距離(最短路徑上所有節(jié)點(diǎn)在同一直線上時除外)。不難推斷，網(wǎng)絡(luò)越不規(guī)則，由此產(chǎn)生的誤差則會越大。

另外，MDS-MAP算法中采用的線性坐標(biāo)轉(zhuǎn)換方法修正定位誤差的作用不夠。坐標(biāo)轉(zhuǎn)換的目的是試圖找到最優(yōu)的轉(zhuǎn)換方法將相對坐標(biāo)系統(tǒng)圖復(fù)原成絕對坐標(biāo)系統(tǒng)圖，由于MDS-MAP算法采用最短路徑距離代替了多跳節(jié)點(diǎn)間的幾何距離，多維標(biāo)度后生成的相對坐標(biāo)圖將會變形，因此，無論采取何種線性變換該算法最終得到的絕對坐標(biāo)圖都會有較大的誤差［13］。MDS-MAP算法將最小化錨節(jié)點(diǎn)在相對坐標(biāo)與絕對坐標(biāo)系統(tǒng)中的相對距離的最小均方誤差作為衡量線性坐標(biāo)變換是否最優(yōu)的標(biāo)準(zhǔn)，其坐標(biāo)轉(zhuǎn)換過程在一定程度上減小了距離估算引起的誤差，但并不是最優(yōu)變換。

2 改進(jìn)算法

針對上述MDS-MAP算法的不足，本文給出了一種改進(jìn)的基于MDS的分布式定位算法，主要做了如下兩方面的改進(jìn):①引入Euclidean算法距離估算思想構(gòu)建距離矩陣;②采用了一種優(yōu)化的基于最小二乘逼近的坐標(biāo)轉(zhuǎn)換方法。

2.1 算法描述

本文提出的改進(jìn)定位算法實(shí)現(xiàn)步驟如下:

①節(jié)點(diǎn)分簇。以節(jié)點(diǎn)分簇思想作為該分布式算法的前提，將傳感器網(wǎng)絡(luò)劃分為多個簇。最簡單的分簇方法是將網(wǎng)絡(luò)中每個節(jié)點(diǎn)作為主節(jié)點(diǎn)，以它的一跳或兩跳鄰居節(jié)點(diǎn)作為從節(jié)點(diǎn)來劃分簇。本文為了減小MDS算法的計算量，同時可以有效利用Euclidean算法提高兩跳節(jié)點(diǎn)間的距離精度，將以一跳鄰居來分簇。

②構(gòu)建局部距離矩陣。以簇為單位，引入Euclidean算法距離估算思想(見3.2節(jié))構(gòu)建局部距離矩陣。在距離矩陣中，相鄰節(jié)點(diǎn)間距離可以通過測距得到，而對于非鄰居節(jié)點(diǎn)來說，若能利用Euclidean算法計算節(jié)點(diǎn)間距離，則以該計算值作為節(jié)點(diǎn)間的歐氏距離，否則仍用最短路徑距離來代替。

③生成局部相對坐標(biāo)。利用多維標(biāo)度技術(shù)對局部距離矩陣處理后得到各簇局部網(wǎng)絡(luò)中節(jié)點(diǎn)的相對坐標(biāo)。

④全局網(wǎng)絡(luò)圖的“縫合”。選擇連通度最大(即鄰節(jié)點(diǎn)最多)的簇局部相對坐標(biāo)圖作為全局網(wǎng)絡(luò)圖的起點(diǎn)，采用貪婪遞增方式將剩余的相對坐標(biāo)圖逐步縫合到全局網(wǎng)絡(luò)圖中，最終生成全局相對坐標(biāo)圖。在網(wǎng)絡(luò)縫合過程中，每次均選擇與現(xiàn)有全局網(wǎng)絡(luò)圖擁有最多公共節(jié)點(diǎn)的局部坐標(biāo)圖作為下一次縫合的對象。

⑤全局絕對坐標(biāo)的確定。借助錨節(jié)點(diǎn)絕對坐標(biāo)，采用3.3節(jié)描述的坐標(biāo)轉(zhuǎn)換方法將全局相對坐標(biāo)轉(zhuǎn)換為全局絕對坐標(biāo)，從而實(shí)現(xiàn)節(jié)點(diǎn)的定位。在坐標(biāo)轉(zhuǎn)換過程中，利用錨節(jié)點(diǎn)的相對坐標(biāo)和絕對坐標(biāo)，通過式(13)可以計算出最優(yōu)的正交變換陣Q和向量b，作為其他未知節(jié)點(diǎn)坐標(biāo)轉(zhuǎn)換的參數(shù)。

假設(shè)傳感器網(wǎng)絡(luò)中共有n個節(jié)點(diǎn)，每個節(jié)點(diǎn)的平均鄰節(jié)點(diǎn)數(shù)即網(wǎng)絡(luò)平均連通度為r，錨節(jié)點(diǎn)數(shù)為k。改進(jìn)算法中:生成全局相對坐標(biāo)的時間復(fù)雜度為O(n·r3);由于構(gòu)建距離矩陣時引入了Euclidean和Dijkstra算法，r個節(jié)點(diǎn)中至少已知r-1條邊，由此帶來的時間復(fù)雜度為O(r2+n);將局部相對坐標(biāo)圖縫合成全局相對坐標(biāo)圖的時間復(fù)雜度為O(n·r3);將全局相對坐標(biāo)轉(zhuǎn)換為絕對坐標(biāo)的時間復(fù)雜度為O(k3+ n)。因此，改進(jìn)算法的總時間復(fù)雜度為O(k3+2nr3+ r2+2n)，優(yōu)于MDS-MAP算法O(n3)的時間復(fù)雜度。

2.2 Euclidean算法求距思想

Euclidean算法給出了傳感器網(wǎng)絡(luò)中求解與錨節(jié)點(diǎn)相隔兩跳跳距的未知節(jié)點(diǎn)距離的方法，該算法的求距思想如圖1所示。

圖1 Euclidean算法求距示意圖

假設(shè)所有節(jié)點(diǎn)均具有測距能力，未知節(jié)點(diǎn)B、C在錨節(jié)點(diǎn)A的測距范圍內(nèi)，而未知節(jié)點(diǎn)D在A的測距范圍之外，節(jié)點(diǎn)B和C間距離BC已知或可測距，節(jié)點(diǎn)D與B、C相鄰。那么對于節(jié)點(diǎn)A和D間的距離AD，可以通過以下幾何關(guān)系計算得到。

2.3 改進(jìn)的坐標(biāo)轉(zhuǎn)換方法

同樣令二維傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)為n，錨節(jié)點(diǎn)數(shù)為k(k≥2);X為節(jié)點(diǎn)的相對坐標(biāo)，Y為其對應(yīng)的絕對坐標(biāo)。記兩組坐標(biāo)的中心節(jié)點(diǎn)為:

最優(yōu)的坐標(biāo)變換為正交變換陣Q和向量b使得式(11)最小，其中QTQ=I，e=［1，…，1］。

文獻(xiàn)［14］給出此優(yōu)化條件的最優(yōu)解為

其中U和V滿足

下面給出該最優(yōu)解的求證過程:

由矩陣跡與Frobenius范數(shù)的關(guān)系‖A‖2F= tr(ATA)=tr(AAT)，有

若正交陣Q和向量b為式(11)的最優(yōu)解，那么向量b需滿足

結(jié)合式(14)和式(15)可將式(11)轉(zhuǎn)換為

由QTQ=I和tr(ATB)=tr(BAT)，有

由式(17)可知，要求得式(16)的最小值，只需求得式(18)的最大值。

對(Y-eTyc)T(X-eTxc)奇異值分解，有

這里，Z=VTQU為正交陣，由ZZT=I可知顯然-1≤zii≤1，i=1:2。因此，且當(dāng)zii=1，i=1:2時得到其最大值，此時Z=I。故Q=VZUT=VUT，得證。

3 仿真實(shí)驗與分析

基于MATLAB平臺，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、錨節(jié)點(diǎn)數(shù)量及網(wǎng)絡(luò)連通度等方面進(jìn)行實(shí)驗仿真，對本文提出的改進(jìn)算法進(jìn)行了有效性驗證和分析。對平均定位誤差定義為:

其中，R為節(jié)點(diǎn)的通信半徑，n為網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù)，～di為節(jié)點(diǎn)i的實(shí)際坐標(biāo)與定位坐標(biāo)間的偏移距離。

為了驗證網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對算法性能的影響，本文分別在正方形區(qū)域和C型區(qū)域進(jìn)行仿真。同時為保證2種分布條件下網(wǎng)絡(luò)連通度的一致，做如下假定:正方形區(qū)域邊長為200 m，隨機(jī)布設(shè)200個節(jié)點(diǎn)，C型區(qū)域邊長200 m，其中空白區(qū)域140 m×120 m，隨機(jī)布設(shè)116個節(jié)點(diǎn);另設(shè)錨節(jié)點(diǎn)占比為5%，測距誤差方差Er=0.15，節(jié)點(diǎn)通信半徑為30 m。如圖2所示，在規(guī)則區(qū)域和不規(guī)則區(qū)域MDS-MAP算法的平均定位誤差分別為11.9%和105.63%，而本文提出的基于MDS的分布式改進(jìn)算法平均定位誤差為7.9%和5.9%，顯然，改進(jìn)算法在不規(guī)則網(wǎng)絡(luò)拓?fù)淝闆r下能明顯改善定位精度，這是由于在分布式的定位算法中，各個節(jié)點(diǎn)的定位只依賴于周圍鄰居節(jié)點(diǎn)的距離信息，而與網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)關(guān)系不大。

圖2 不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的仿真結(jié)果

同時為驗證改進(jìn)的坐標(biāo)轉(zhuǎn)換方法的作用，在相同環(huán)境下，將本文提出的改進(jìn)算法與分布式的MDSMAP算法(引入Euclidean算法測距思想)的定位結(jié)果進(jìn)行對比后發(fā)現(xiàn)，改進(jìn)算法的平均定位誤差有0.5%～2%的降低。

圖3給出了在規(guī)則區(qū)域中錨節(jié)點(diǎn)數(shù)量的不同對算法定位誤差的影響。分析圖中曲線可以看出，經(jīng)典的DV-HOP算法受錨節(jié)點(diǎn)數(shù)影響較大，錨節(jié)點(diǎn)越多，定位越精確。而無論是MDS-MAP算法還是基于MDS的分布式算法，雖然隨著錨節(jié)點(diǎn)的增多定位誤差有所下降，但改善并不明顯，錨節(jié)點(diǎn)數(shù)大于3個即可。這是因為，DV-HOP算法中每個節(jié)點(diǎn)直接估算與錨節(jié)點(diǎn)的距離，錨節(jié)點(diǎn)越多，估算越準(zhǔn)確;而MDS-MAP算法和基于MDS的分布式算法只依賴于節(jié)點(diǎn)間的距離信息，當(dāng)節(jié)點(diǎn)間距離矩陣確定后，節(jié)點(diǎn)的相對位置就可以確定。錨節(jié)點(diǎn)的作用僅僅是用來獲得未知節(jié)點(diǎn)絕對坐標(biāo)的轉(zhuǎn)換參數(shù)。因此，基于MDS的定位算法受錨節(jié)點(diǎn)數(shù)量的影響較小。

圖3 錨節(jié)點(diǎn)數(shù)量與定位誤差的關(guān)系

要考察網(wǎng)絡(luò)連通度對定位算法誤差的影響，可以通過調(diào)整單位面積內(nèi)節(jié)點(diǎn)數(shù)量或節(jié)點(diǎn)通信半徑2種方式實(shí)現(xiàn)，本文將保持節(jié)點(diǎn)密度不變，通過調(diào)整節(jié)點(diǎn)通信半徑來實(shí)現(xiàn)。在邊長為200 m的正方形區(qū)域，節(jié)點(diǎn)數(shù)為200，測距誤差Er=0.15，錨節(jié)點(diǎn)10個，節(jié)點(diǎn)通信半徑在15 m～45 m之間，以5 m為步長遞增，相應(yīng)的網(wǎng)絡(luò)連通度分別為:3.534 2、6.283 2、9.817 5、14.137 2、19.242 3、25.132 7和31.808 4。仿真結(jié)果如圖4所示，當(dāng)連通度較低(小于4)時，改進(jìn)算法定位精度較MDS-MAP算法低，這是因為連通度較低時對網(wǎng)絡(luò)分簇后存在較多一跳鄰居節(jié)點(diǎn)小于1的節(jié)點(diǎn)，這些節(jié)點(diǎn)無法進(jìn)行定位，而經(jīng)典算法在規(guī)則網(wǎng)絡(luò)條件下能較為精確地估算節(jié)點(diǎn)間的距離，從而得到較高的定位精度;當(dāng)連通度較大(大于30)時，改進(jìn)算法定位精度很高，但與經(jīng)典算法相比提高有限，反而算法的計算量和通信量有所增加;而當(dāng)網(wǎng)絡(luò)連通度介于5和30之間時改進(jìn)算法定位精度與經(jīng)典算法相比有較大的提高。在實(shí)際應(yīng)用中，綜合考慮算法的定位精度和復(fù)雜度，基于MDS的分布式改進(jìn)算法適合于網(wǎng)絡(luò)節(jié)點(diǎn)連通度介于5至30之間的網(wǎng)絡(luò)。

圖4 網(wǎng)絡(luò)連通度與定位誤差的關(guān)系

4 結(jié)語

基于多維標(biāo)度技術(shù)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法其誤差主要來源于構(gòu)建距離矩陣時的距離估算，網(wǎng)絡(luò)越不規(guī)則，誤差越大，網(wǎng)絡(luò)規(guī)模越大，算法時間復(fù)雜度越高。本文對經(jīng)典MDS-MAP算法進(jìn)行分布式改進(jìn)，引入Euclidean算法計算非鄰節(jié)點(diǎn)間距離，同時優(yōu)化了原算法中的坐標(biāo)轉(zhuǎn)換方法，在規(guī)則和不規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)下均有效地提高了節(jié)點(diǎn)的定位精度，同時降低了算法時間復(fù)雜度。誠然，復(fù)雜的算法固然可以提高定位精度，但無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能量是有限的，在算法時間復(fù)雜度與能量消耗之間尋求合理的平衡點(diǎn)將值得進(jìn)一步的研究和探討。

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［2］Sayed A H，Alireza T，Nima K.Network-Based Wireless Location Challenges Faced in Developing Techniques for Accurate Wireless Location Information［J］.IEEE Signal Processing Magazine，2006，23(5):24-40.

［3］陳歲生，盧建剛，樓曉春.基于MDS-MAP和非線性濾波的WSN定位算法［J］.浙江大學(xué)學(xué)報(工學(xué)版)，2012，5(5):866-872.

［4］王健，趙亞鳳，劉勁風(fēng).一種適用于大規(guī)模無線傳感器網(wǎng)絡(luò)的定位算法［J］.東北林業(yè)大學(xué)學(xué)報，2009，37(8):84-89.

［5］王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報，2005，16(5):857-868.

［6］Borg I，Groener P.Modern Multidimensional Scaling Theory and Applications［M］.New York:Springer-Verlag，1997:10-35.

［7］Shang Yi，Ruml Wheeler，Zhang Ying.Localization from Mere Connectivity［C］//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2003:201 -212.

［8］韓雙霞，張露，范一鳴.WSN中改進(jìn)的分布式多維定標(biāo)定位算法［J］.傳感技術(shù)學(xué)報，2009，22(5):728-733.

［9］Gopakumar Aloor，Lillykutty Jacob.Distributed Wireless Sensor Network Localization Using Stochastic Proximity Embedding［J］. Computer Communications，2010，33(6):745-755.

［10］Chan F，So H C.Efficient Weighted Multi-Dimensional Scaling for Wireless Sensor Network Localization［J］.IEEE Trans on Signal Processing，2009，57(11):4548-4553.

［11］黃亮，王福豹，段渭軍，等.基于距離重構(gòu)的無線傳感器網(wǎng)絡(luò)多維定標(biāo)定位算法［J］.傳感技術(shù)學(xué)報，2013，26(9):1284 -1287.

［12］Niculescu D，Nath B.Ad-Hoc Positioning Systems(APS)［C］// Proceedings of2006 IEEE Global Telecommunications Conference，Washington，2006:2926-2931.

［13］王林，王曉鵬.改進(jìn)的無線傳感器網(wǎng)絡(luò)中多維定標(biāo)定位算法［J］.計算機(jī)工程與應(yīng)用，2011，47(27):115-118.

［14］Luo Xinlong，Wu Zhijun.Least-Square Approximations in Geometric Buildup for Solving Distance Geometry Problems［J］.Journalof Optimization Theory and Applications，2010.

劉健苗(1980-)，男，湖南武岡人，碩士，工程師，研究方向為通信信息，傳感技術(shù);

許新忠(1978-)，男，河南修武人，碩士，講師，研究方向為算法優(yōu)化;

黃書廣(1985-)，男，河南湯陰人，碩士，助理工程師，研究方向為無線傳感器網(wǎng)絡(luò)。

Advanced Distributed Multidimensional Scaling Localization Algorithm for Wireless Sensor Network

LIU Jianmiao1，XU Xinzhong2*，HUANG Shuguang1，LI Zhe2

(1.China Information Technology Designing and Consulting Institute Co.，Ltd.，Zhengzhou 450007，China; 2.Henan Vocational College of Art，Zhengzhou 450001，China)

An advanced distributed localization algorithm based on MDS was proposed，which attempted to improve the node localization accuracy of the classical MDS-MAP algorithm in wireless sensor network.During the course of producing localnode distance matrix，a new distance estimates method from Euclidean localization algorithm is introduced.Besides，a more effective transforming technology which based on the least-squares approximation is used to replace the original one，to transform the relative coordinate system to absolute coordinate system.Experimental results show that in the same experiment environment，compared with the classical MDS-MAP algorithm，the improved algorithm is more reliable in various topology networks.

wireless sensor network;coordinate transformation;node localization;distribution;multidimensional scaling

TP393

A

1004－1699(2014)05－0692－06

10.3969/j.issn.1004－1699.2014.05.023

2014-01-23

2014-04-09