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

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

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

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

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

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

節(jié)點(diǎn)定位技術(shù)作為無(wú)線傳感器網(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)測(cè)距條件下定位精度很高。然而，集中式定位模式導(dǎo)致其在網(wǎng)絡(luò)規(guī)模較大時(shí)計(jì)算復(fù)雜度很高，同時(shí)該算法在網(wǎng)絡(luò)拓?fù)洳灰?guī)則的情況下定位誤差較大。為提升定位精度，研究人員相繼提出多種基于MDS的改進(jìn)算法，如分布式MDS算法［4，8-9］，加權(quán)MDS算法［10］，非線性濾波MDS算法［3］以及距離重構(gòu)MDS算法［11］等，它們?cè)谔囟l件下均取得了較好的定位效果。然而，這些改進(jìn)算法都需要基于節(jié)點(diǎn)距離信息進(jìn)行坐標(biāo)計(jì)算，在精準(zhǔn)測(cè)距的理想狀態(tài)下，借助錨節(jié)點(diǎn)的絕對(duì)坐標(biāo)經(jīng)過(guò)線性變換來(lái)定位其他未知節(jié)點(diǎn)是沒(méi)有問(wèn)題的。但是往往節(jié)點(diǎn)測(cè)距范圍有限，由此獲得的距離矩陣并不準(zhǔn)確，需要采用更優(yōu)的坐標(biāo)變換方法來(lái)減少未知節(jié)點(diǎn)定位的誤差。

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

1 MDS-MAP算法及分析

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

1.1 MDS-MAP算法流程

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

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

通過(guò)多維標(biāo)度技術(shù)獲得的節(jié)點(diǎn)坐標(biāo)是相對(duì)坐標(biāo)，需要參考錨節(jié)點(diǎn)的絕對(duì)坐標(biāo)，經(jīng)過(guò)平移、旋轉(zhuǎn)和翻轉(zhuǎn)等一系列線性坐標(biāo)變換，將相對(duì)坐標(biāo)轉(zhuǎn)換到錨節(jié)點(diǎn)所在的絕對(duì)坐標(biāo)系中去。下面以二維傳感器網(wǎng)絡(luò)為例，對(duì)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)的相對(duì)坐標(biāo)，Y=［yij］2*n=［Y1，Y2，…，Yn］為其對(duì)應(yīng)的絕對(duì)坐標(biāo)，假設(shè)Y1，Y2，…，Yk為錨節(jié)點(diǎn)的絕對(duì)坐標(biāo)。

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

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

故

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

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

1.3 MDS-MAP算法誤差分析

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

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

2 改進(jìn)算法

針對(duì)上述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ò)劃分為多個(gè)簇。最簡(jiǎn)單的分簇方法是將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)，以它的一跳或兩跳鄰居節(jié)點(diǎn)作為從節(jié)點(diǎn)來(lái)劃分簇。本文為了減小MDS算法的計(jì)算量，同時(shí)可以有效利用Euclidean算法提高兩跳節(jié)點(diǎn)間的距離精度，將以一跳鄰居來(lái)分簇。

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

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

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

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

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

2.2 Euclidean算法求距思想

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

圖1 Euclidean算法求距示意圖

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

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)的相對(duì)坐標(biāo)，Y為其對(duì)應(yīng)的絕對(duì)坐標(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)解的求證過(guò)程:

由矩陣跡與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)的最大值。

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

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

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

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

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

為了驗(yàn)證網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)算法性能的影響，本文分別在正方形區(qū)域和C型區(qū)域進(jìn)行仿真。同時(shí)為保證2種分布條件下網(wǎng)絡(luò)連通度的一致，做如下假定:正方形區(qū)域邊長(zhǎng)為200 m，隨機(jī)布設(shè)200個(gè)節(jié)點(diǎn)，C型區(qū)域邊長(zhǎng)200 m，其中空白區(qū)域140 m×120 m，隨機(jī)布設(shè)116個(gè)節(jié)點(diǎn);另設(shè)錨節(jié)點(diǎn)占比為5%，測(cè)距誤差方差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下能明顯改善定位精度，這是由于在分布式的定位算法中，各個(gè)節(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é)果

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

圖3給出了在規(guī)則區(qū)域中錨節(jié)點(diǎn)數(shù)量的不同對(duì)算法定位誤差的影響。分析圖中曲線可以看出，經(jīng)典的DV-HOP算法受錨節(jié)點(diǎn)數(shù)影響較大，錨節(jié)點(diǎn)越多，定位越精確。而無(wú)論是MDS-MAP算法還是基于MDS的分布式算法，雖然隨著錨節(jié)點(diǎn)的增多定位誤差有所下降，但改善并不明顯，錨節(jié)點(diǎn)數(shù)大于3個(gè)即可。這是因?yàn)椋珼V-HOP算法中每個(gè)節(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)的相對(duì)位置就可以確定。錨節(jié)點(diǎn)的作用僅僅是用來(lái)獲得未知節(jié)點(diǎn)絕對(duì)坐標(biāo)的轉(zhuǎn)換參數(shù)。因此，基于MDS的定位算法受錨節(jié)點(diǎn)數(shù)量的影響較小。

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

要考察網(wǎng)絡(luò)連通度對(duì)定位算法誤差的影響，可以通過(guò)調(diào)整單位面積內(nèi)節(jié)點(diǎn)數(shù)量或節(jié)點(diǎn)通信半徑2種方式實(shí)現(xiàn)，本文將保持節(jié)點(diǎn)密度不變，通過(guò)調(diào)整節(jié)點(diǎn)通信半徑來(lái)實(shí)現(xiàn)。在邊長(zhǎng)為200 m的正方形區(qū)域，節(jié)點(diǎn)數(shù)為200，測(cè)距誤差Er=0.15，錨節(jié)點(diǎn)10個(gè)，節(jié)點(diǎn)通信半徑在15 m～45 m之間，以5 m為步長(zhǎng)遞增，相應(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)時(shí)，改進(jìn)算法定位精度較MDS-MAP算法低，這是因?yàn)檫B通度較低時(shí)對(duì)網(wǎng)絡(luò)分簇后存在較多一跳鄰居節(jié)點(diǎn)小于1的節(jié)點(diǎn)，這些節(jié)點(diǎn)無(wú)法進(jìn)行定位，而經(jīng)典算法在規(guī)則網(wǎng)絡(luò)條件下能較為精確地估算節(jié)點(diǎn)間的距離，從而得到較高的定位精度;當(dāng)連通度較大(大于30)時(shí)，改進(jìn)算法定位精度很高，但與經(jīng)典算法相比提高有限，反而算法的計(jì)算量和通信量有所增加;而當(dāng)網(wǎng)絡(luò)連通度介于5和30之間時(shí)改進(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é)語(yǔ)

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

［1］孫利民，李建中，陳渝，等.無(wú)線傳感器網(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é)報(bào)(工學(xué)版)，2012，5(5):866-872.

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

［5］王福豹，史龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，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é)報(bào)，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ú)線傳感器網(wǎng)絡(luò)多維定標(biāo)定位算法［J］.傳感技術(shù)學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)中多維定標(biāo)定位算法［J］.計(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-)，男，湖南武岡人，碩士，工程師，研究方向?yàn)橥ㄐ判畔?，傳感技術(shù);

許新忠(1978-)，男，河南修武人，碩士，講師，研究方向?yàn)樗惴▋?yōu)化;

黃書廣(1985-)，男，河南湯陰人，碩士，助理工程師，研究方向?yàn)闊o(wú)線傳感器網(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