鄔春明，宋強(qiáng)歡，楊　濤

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

一種改進(jìn)的分布式多維定標(biāo)算法的研究

鄔春明，宋強(qiáng)歡，楊濤

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

摘要:無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)間通信容易受到環(huán)境因素和傳輸衰減因素等的影響，從而造成節(jié)點(diǎn)的定位不準(zhǔn)確。為減小節(jié)點(diǎn)定位誤差，在分布式多維定標(biāo)算法基礎(chǔ)上提出了改進(jìn)的WMDS-MAP(P)算法。采用加權(quán)算法求出每個(gè)錨節(jié)點(diǎn)的環(huán)境影響參數(shù)和傳輸衰減參數(shù)對(duì)，并在構(gòu)建局部空間的節(jié)點(diǎn)矩陣時(shí)考慮這兩個(gè)因素；采用最小二乘算法選出錨節(jié)點(diǎn)中最優(yōu)的環(huán)境影響參數(shù)和傳輸衰減參數(shù)對(duì)，從而使節(jié)點(diǎn)間的一跳距離估計(jì)值更逼近真實(shí)值。仿真結(jié)果顯示改進(jìn)的算法相對(duì)于經(jīng)典的MDS-MAP(P)算法節(jié)點(diǎn)平均定位誤差減少了17%左右，可以有效提高節(jié)點(diǎn)的定位精度。

關(guān)鍵詞:分布式多維定標(biāo);WMDS-MAP(P)算法;加權(quán)算法;最小二乘算法

無線傳感器網(wǎng)絡(luò)具有自組網(wǎng)、低功耗及低成本的優(yōu)點(diǎn)，目前廣泛用于智能交通、目標(biāo)跟蹤、森林防火及軍事領(lǐng)域等。在這些運(yùn)用中節(jié)點(diǎn)的定位顯得尤為重要，目前，節(jié)點(diǎn)定位技術(shù)的研究得到了科研工作者的廣泛關(guān)注，并且也取得了豐富的成果。無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法大致可以分為兩大類：一種是基于測距的定位算法，例如：RSSI(singal received strength)、TOA(Time of Arrival)、AOA(Angle of Arrival)、Cooperative ranging、COLA(Complexity-reached 3D trilateration localization approach)[1-5]等。另一種是基于非測距算法，例如：DV-HOP、MCL(Monte Carlo Localization)、CDL(Color-Theory-Based Dynamic Localization)、WMCL(Weighted Monte Carlo Localization)[6-9]等。無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)定位的精度很大依靠于節(jié)點(diǎn)的測距精度，而由于節(jié)點(diǎn)與節(jié)點(diǎn)之間的通信過程容易受到復(fù)雜環(huán)境因素、多路徑損耗及傳輸路徑損耗等影響，使得節(jié)點(diǎn)間的定位誤差較大。如今，考慮這些因素的定位算法已經(jīng)取得了較高的定位精度，如李建坡等提出的基于RSSI值節(jié)點(diǎn)不規(guī)則傳播模型的三維定位算法[10]、姚國提出基于RSSI值的獨(dú)立目標(biāo)的定位和跟蹤的銳利指數(shù)模型[11]。

2003年，密蘇里哥倫比亞大學(xué)的Yi Shang等人將多維標(biāo)度(multidimensional scaling， MDS)的數(shù)據(jù)分析方法應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位，提出了MDS-MAP算法(multidimensional scaling map algorithm)[12]，基于多維標(biāo)度的定位算法是根據(jù)數(shù)據(jù)之間的相異性關(guān)系進(jìn)行定位，其可以分為度量多維標(biāo)度技術(shù)(metric MDS)和非度量多維標(biāo)度技術(shù)(nonmetric MDS)，由于其具有矩陣維數(shù)大、計(jì)算復(fù)雜度高及不適合大規(guī)模不規(guī)則的無線傳感器網(wǎng)絡(luò)(WSN)的缺點(diǎn)，研究者提出了MDS-MAP(P)分布式局部定位算法[13-14]，它能夠獲得較好的定位精度，其定位精度也很大程度上取決于局部空間距離矩陣D中的距離值與真實(shí)值之間誤差的大小。本文在MDS-MAP(P)算法基礎(chǔ)上提出了WMDS-MAP(P)算法(Weighted multidimensional scaling map algorithm)，其在構(gòu)建局部空間的距離矩陣D時(shí)采用加權(quán)算法和最小二乘算法相結(jié)合使矩陣中距離值更加接近于真實(shí)值，再使用經(jīng)典的MDS-MAP(P)算法，從而獲得較好的定位精度。

1MDS-MAP(P)算法的介紹

MDS-MAP(P)是在MDS-MAP的基礎(chǔ)上改進(jìn)而來，其能夠克服MDS-MAP中矩陣維數(shù)大、計(jì)算復(fù)雜度高及不適合大規(guī)模不規(guī)則的無線傳感器網(wǎng)絡(luò)(WSN)的缺點(diǎn)。采用基于MDS的分布式局部定位算法，充分利用網(wǎng)絡(luò)中任一節(jié)點(diǎn)的連通信息構(gòu)建該節(jié)點(diǎn)的局部相對(duì)坐標(biāo)圖，再通過一定的拼接策略將所有的局部相對(duì)坐標(biāo)圖拼接成全局相對(duì)坐標(biāo)圖，最后通過一定的坐標(biāo)轉(zhuǎn)換方法將相對(duì)坐標(biāo)轉(zhuǎn)換成絕對(duì)坐標(biāo)，具體步驟如下：

階段1：在無線傳感器網(wǎng)絡(luò)中采用洪泛的方法使網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)只與距其兩跳通信半徑范圍內(nèi)的節(jié)點(diǎn)進(jìn)行通信并收集其ID及節(jié)點(diǎn)間距離信息，采用一定的劃分策略將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)劃分為一個(gè)局部空間，即若無線傳感器網(wǎng)絡(luò)中分布著N個(gè)節(jié)點(diǎn)，則將該區(qū)域劃分為N個(gè)局部空間。

階段2：對(duì)于網(wǎng)絡(luò)中任一節(jié)點(diǎn)構(gòu)建距其兩跳范圍內(nèi)的節(jié)點(diǎn)間距離矩陣D，對(duì)處于距其一跳距離的鄰居節(jié)點(diǎn)采用的是基于RSSI(信號(hào)接收強(qiáng)度值)測距方法計(jì)算其距離值，而對(duì)于非鄰居節(jié)點(diǎn)的兩跳節(jié)點(diǎn)，采用Eucilidean與最小路徑相結(jié)合的方法計(jì)算其距離值。

階段3：當(dāng)完成每個(gè)節(jié)點(diǎn)的局部劃分及求出局部的距離矩陣D后采用經(jīng)典的MDS方法計(jì)算各局部空間的相對(duì)坐標(biāo)。

階段4：當(dāng)網(wǎng)絡(luò)中所有的局部空間的相對(duì)坐標(biāo)均求出時(shí)，在所有的局部相對(duì)坐標(biāo)圖中挑選出連通度最高、節(jié)點(diǎn)數(shù)量最多的局部相對(duì)坐標(biāo)圖作為主坐標(biāo)圖，并將與主坐標(biāo)圖具有公共節(jié)點(diǎn)最多的局部相對(duì)坐標(biāo)圖作為拼接對(duì)象，按此原則依次進(jìn)行拼接直至形成全局相對(duì)坐標(biāo)圖。

階段5：根據(jù)錨節(jié)點(diǎn)在全局相對(duì)坐標(biāo)圖中相對(duì)坐標(biāo)與絕對(duì)坐標(biāo)之間的轉(zhuǎn)換關(guān)系，將網(wǎng)絡(luò)中所有節(jié)點(diǎn)的相對(duì)坐標(biāo)轉(zhuǎn)換成絕對(duì)坐標(biāo)。

2改進(jìn)的WMDS-MAP(P)算法

在構(gòu)建局部空間的距離矩陣D時(shí)，距離矩陣D′與真實(shí)距離矩陣D誤差大小將決定最終節(jié)點(diǎn)的定位精度的高低，在經(jīng)典的MDS-MAP(P)算法中，在計(jì)算節(jié)點(diǎn)的一跳距離時(shí)采用的是基于RSSI的測距方法，由于節(jié)點(diǎn)與節(jié)點(diǎn)之間通信時(shí)接收到RSSI值容易受到外界環(huán)境和信號(hào)傳輸衰減損耗的影響，從而造成定位誤差較大。本文將充分考慮這兩個(gè)參數(shù)的影響，通過改進(jìn)MDS-MAP(P)算法提出WMDS-MAP(P)算法，即分別通過計(jì)算出環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)，在構(gòu)建局部空間節(jié)點(diǎn)間的距離矩陣時(shí)考慮這兩個(gè)因素，并通過加權(quán)算法和最小二乘算法進(jìn)行優(yōu)化，從而使得一跳距離估計(jì)值更逼近真實(shí)值，從而獲取一個(gè)較好的定位精度，具體改進(jìn)步驟如2.1小節(jié)和2.2小節(jié)所示。

信號(hào)衰減模型為

(1)

式中：RSS(d)為錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離為d時(shí)信號(hào)接收強(qiáng)度值，單位為dBm；RSS(d0)為通信距離為d0時(shí)信號(hào)接收強(qiáng)度值；d0為參考值，取值為1 m；δτ為服從(0，δ2)高斯分布的噪聲隨機(jī)變量。

將式(1)進(jìn)行簡化得

(2)

其中。

S=RSS(d0aa)[dBm]-δτ

(3)

假設(shè)錨節(jié)點(diǎn)n1，坐標(biāo)為(x,y)，周圍有3個(gè)一跳距離的錨節(jié)點(diǎn)n2,n3,n4，其坐標(biāo)分別為(x1,y1),(x2,y2),(x3,y3)，并距節(jié)點(diǎn)n1分別為d1,d2,d3。其分布如圖1所示。

圖1　錨節(jié)點(diǎn)分布圖

則根據(jù)式(2)、(3)可得

(4)

節(jié)點(diǎn)n1與節(jié)點(diǎn)n2,n3可得

(5)

由式(5)可得

(6)

2.1錨節(jié)點(diǎn)參數(shù)對(duì)的加權(quán)算法

由節(jié)點(diǎn)n1與節(jié)點(diǎn)n2,n3可以得到環(huán)境影響參數(shù)λ1和信號(hào)傳輸衰減參數(shù)S1，相應(yīng)地，節(jié)點(diǎn)n1與節(jié)點(diǎn)n2,n4、節(jié)點(diǎn)n3,n4可得到環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)λ2、S2和λ3、S3。

則通過加權(quán)可得

(7)

(8)

(9)

(10)

通過上述算法可知，無線傳感器網(wǎng)絡(luò)中任一錨節(jié)點(diǎn)都能得到一個(gè)特定的環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)，并將其值保存起來。由于局部空間計(jì)算的節(jié)點(diǎn)間距離估計(jì)值與真實(shí)值之間有誤差，利用脅強(qiáng)系數(shù)來表示估計(jì)值與真實(shí)值之間的接近程度，其定義為

STRESS=∑(d^ij-dij)2

(11)

式中：d^ij為通過測量得到的節(jié)點(diǎn)間距離值；dij為空間內(nèi)節(jié)點(diǎn)的估計(jì)位置的距離值。

2.2采用最小二乘算法優(yōu)化參數(shù)對(duì)

在局部空間內(nèi)每個(gè)錨節(jié)點(diǎn)都保存著由上述算法計(jì)算出的一對(duì)環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)(S,λ)，采用最小二乘算法從這些錨節(jié)點(diǎn)中選出使脅強(qiáng)系數(shù)最小的環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)。

(12)

則最小脅強(qiáng)系數(shù)為

(13)

式中：dij為空間內(nèi)估計(jì)位置的距離值。式(13)是一個(gè)最小二乘算法問題，其是根據(jù)局部空間中錨節(jié)點(diǎn)的環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)對(duì)的解空間進(jìn)行窮舉來搜索求解，通過式(13)可以得到最優(yōu)的環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)對(duì)(Sp,λp)，未知節(jié)點(diǎn)保存(Sp,λp)，并在后續(xù)計(jì)算節(jié)點(diǎn)距離時(shí)采用其進(jìn)行計(jì)算。

當(dāng)局部空間內(nèi)任一節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)進(jìn)行通信時(shí)，節(jié)點(diǎn)接收到來自鄰居節(jié)點(diǎn)的RSSI值，并考慮上述計(jì)算出的最優(yōu)環(huán)境影響參數(shù)和信號(hào)傳輸衰減參數(shù)對(duì)(Sp,λp)，從而計(jì)算出一跳節(jié)點(diǎn)的距離。采用的上述的WMDS-MAP(P)計(jì)算出一跳節(jié)點(diǎn)間的距離，同時(shí)在計(jì)算二跳節(jié)點(diǎn)距離時(shí)采用二跳距離采用的是Eucilidean與最小路徑相結(jié)合的方法，從而構(gòu)建出局部空間的節(jié)點(diǎn)距離矩陣D′。

3實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)部分采用的是MATLAB7.0軟件對(duì)改進(jìn)的WMDS-MAP(P)算法進(jìn)行仿真驗(yàn)證，并且對(duì)MDS-MAP算法、MDS-MAP(P)算法分別進(jìn)行仿真，根據(jù)得到的仿真結(jié)果進(jìn)行對(duì)比分析，從而對(duì)改進(jìn)算法的性能進(jìn)行分析。

3.1仿真環(huán)境與參數(shù)設(shè)置

本文的仿真環(huán)境是在一個(gè)200m×200m的正方形區(qū)域內(nèi)，區(qū)域內(nèi)隨機(jī)分布著200個(gè)節(jié)點(diǎn)，其中錨節(jié)點(diǎn)是隨機(jī)選取，各個(gè)節(jié)點(diǎn)設(shè)置的通信半徑相同，重復(fù)仿真實(shí)驗(yàn)500次，并將其實(shí)驗(yàn)結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)結(jié)果采用平均定位誤差進(jìn)行衡量算法的性能指標(biāo)，平均定位誤差為

(14)

歸一化誤差為

(15)

3.2算法的性能分析

圖2a和圖2b為通信半徑分別為20 m和25 m，高斯噪聲的方差δ為2時(shí)，節(jié)點(diǎn)的平均定位誤差隨錨節(jié)點(diǎn)數(shù)量變化的曲線，從圖中可以看出：通信半徑相同時(shí)，隨著錨節(jié)點(diǎn)數(shù)量的增加，與經(jīng)典的MDS-MAP算法和MDS-MAP(P)算法相比，改進(jìn)的WMDS-MAP(P)算法的平均定位誤差分別降低了32%和17%左右。

a　通信半徑R=20 m，高斯噪聲方差δ=2

b　通信半徑R=25 m，高斯噪聲方差δ=2

圖3a和圖3b為錨節(jié)點(diǎn)分別是8和10，δ為2時(shí)，節(jié)點(diǎn)的平均定位誤差隨網(wǎng)絡(luò)的連通度變化的曲線關(guān)系圖。從圖中可以看出隨著連通度的提高，節(jié)點(diǎn)的平均定位誤差逐漸減小，當(dāng)連通度為20以上時(shí)，節(jié)點(diǎn)的平均定位誤差基本不變，這是因?yàn)檫B通度越高，在計(jì)算二跳距離時(shí)，最小路徑更接近真實(shí)值，從而獲得更好的定位精度。

a 錨節(jié)點(diǎn)數(shù)量M=8，高斯噪聲方差δ=2

b 錨節(jié)點(diǎn)數(shù)量M=10，高斯噪聲方差δ=2

4總結(jié)

在真實(shí)環(huán)境下，節(jié)點(diǎn)間通信容易受到環(huán)境因素和傳輸衰減因素的影響，因此，在MDS-MAP(P)算法的基礎(chǔ)上提出了WMDS-MAP(P)算法，從仿真結(jié)果中可以看出改進(jìn)的算法能夠克服復(fù)雜環(huán)境的影響，且平均定位誤差降低17%左右。將該算法的改進(jìn)部分用于其他基于MDS-MAP(P)改進(jìn)算法中，可以提高一定的節(jié)點(diǎn)定位精度。未來工作是將考慮無線傳感器網(wǎng)絡(luò)區(qū)域?yàn)椴灰?guī)則區(qū)域時(shí)，該改進(jìn)算法是否依然能夠獲得較好的定位精度。同時(shí)，考慮在改進(jìn)算法的基礎(chǔ)上減少在局部相對(duì)坐標(biāo)轉(zhuǎn)換為全局絕對(duì)坐標(biāo)時(shí)產(chǎn)生的誤差，從而實(shí)現(xiàn)更高的定位精度。

參考文獻(xiàn)：

[1]ABID M A, CHERKAOUI S. 3D compressive sensing for nodes localization in WNs based on RSS[C]//Proc. IEEE International Conference on Communications. Beijing：IEEE Press，2012：5195-5199.

[2]KAUNE R. Accuracy studies for TDOA and TOA localization[C]//Proc. 15th International Conference on Information Fusion. Singapore：IEEE Press，2012:408-415.

[3]HARA S, ANZAI D, YABU T. A perturbation analysis on the performance of TOA and TDOA localization in mixed LOS/NLOS environments[J]. IEEE transactions on communications, 2013,61(2):679-689.

[4]SAVARESE C, RAVAEY J M, BEUTEL J. Location in distributed ad-hoc wireless sensor networks[C]//Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing. Salt Lake City：IEEE Press，2001: 2037-2040.

[5]SHIH C Y, MARRON P J. COLA: complexity reduced trilateration approach for 3D localization in wireless sensor networks[C]//Proc. 4th International Conference on Sensor Technologies and Applications. Venice：IEEE Press, 2010:24-32.

[6]NICULESCU D, NATH B. Ad Hoc positioning system (APS) [C]//Proc. IEEE Global Telecommunications Conference. San Antonio：IEEE Press，2001: 2926-2931.

[7]HU L X, EVANS D. Localization for mobile sensor networks[C]//Proc. 10th Annual International Conference on Mobile Computing and Networking. Philadelphia：IEEE Press，2004:45-57.

[8]CHANG T, WANG K, HSIEH Y L. Color-theory-based dynamic localization in mobile wireless sensor networks[C]//Proc. 1st Workshop on Wireless Ad Hoc Sensor Networks. London：IEEE Press，2005: 73-78.

[9]ZHANG S G，CAO J N，CHEN L J. Accurate and energy-efficient range-free localization for mobile sensor networks[J]. IEEE transactions on mobile computing, 2010,6(9):897-910.

[10]LI J P, ZHONG X X, LU I T. Three-dimensional node localization algorithm for WSN basd on diferential RSS irregular transmission model[J]. Journal of communications,2014,5(9):391-397.

[11]GAO Y, HUANG K D, JIANG N Y. An exponential Rayleigh model for RSS-based device-free localization and tracking[J]. IEEE transactions on mobile computing，2015,3(15):484-494.

[12]SHANG Y, RUML W, ZHANG Y, et al. Localization from mere connectivity[C]//Proc. 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York：IEEE Press，2003: 201-212.

[13]SHANG Y，RUML W. Improved MDS-based localization[J]. Twenty-third annual joint conference of the IEEE computer and communications societies，2004(4)：2640-2651.

[14]劉春平. 基于多維尺度分析的三維非均勻無線傳感網(wǎng)定位算法研究[D].杭州：杭州電子科技大學(xué)，2014.

鄔春明(1966— )，碩士，教授，碩士生導(dǎo)師，從事無線通信技術(shù)領(lǐng)域科學(xué)研究與教學(xué)工作；

宋強(qiáng)歡(1992— )，碩士生，主要從事無線傳感網(wǎng)絡(luò)定位；

楊濤(1991— )，碩士生，主要從事無線傳感網(wǎng)絡(luò)定位及系統(tǒng)硬件設(shè)計(jì)的研究。

責(zé)任編輯：薛京

Study of improved MDS-MAP (P) algorithm

WU Chunming，SONG Qianghuan, YANG Tao

(InformationEngineeringCollege,NortheastDianliUniversity，JilinJilin132012,China)

Abstract:the nodes position precision is vulnerable to the environmental factors and the influence of transmission attenuation factors in wireless sensor networks. To reduce the node positioning error, a WMDS-MAP(P) algorithm based on the distributed multi-dimensional scaling map(MDS-MAP(P)) algorithm is proposed. Using the weighted algorithm find out the environmental impact parameters and the parameters of transmission attenuation of each anchor node. And consider the two factors in computing the local space node matrix. Using the least squares algorithm to select the anchor nodes the most optimal environmental impact parameters and the parameters of transmission attenuation, and make one-jump estimate distance more close to the real value. Compared with the classical MDS-node MAP(P) algorithm, the simulation results show that the improved algorithm can reduce the average position error is about 17%, and it can effectively improve the nodes positioning precision.

Key words:multidimensional scaling map algorithm; weighted multidimensional scaling map algorithm; weighted algorithm ; the least squares algorithm

中圖分類號(hào):TN92

文獻(xiàn)標(biāo)志碼：A

DOI：10.16280/j.videoe.2016.03.021

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61301257)；吉林省科技發(fā)展計(jì)劃資助項(xiàng)目(2013020605GX);吉林省教育廳“十二五”科學(xué)技術(shù)研究項(xiàng)目(吉教科合字[2015]第250號(hào))

作者簡介：

收稿日期：2015-07-18

文獻(xiàn)引用格式：鄔春明，宋強(qiáng)歡，楊濤.一種改進(jìn)的分布式多維定標(biāo)算法的研究[J].電視技術(shù),2016，40(3)：98-102.

WU Chunming，SONG Qianghuan, YANG Tao.Study of improved MDS-MAP (P) algorithm[J].Video engineering,2016,40(3)：98-102.