一種改進的分布式多維定標算法的研究

鄔春明，宋強歡，楊　濤

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

一種改進的分布式多維定標算法的研究

鄔春明，宋強歡，楊濤

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

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

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

無線傳感器網(wǎng)絡(luò)具有自組網(wǎng)、低功耗及低成本的優(yōu)點，目前廣泛用于智能交通、目標跟蹤、森林防火及軍事領(lǐng)域等。在這些運用中節(jié)點的定位顯得尤為重要，目前，節(jié)點定位技術(shù)的研究得到了科研工作者的廣泛關(guān)注，并且也取得了豐富的成果。無線傳感器網(wǎng)絡(luò)的節(jié)點定位算法大致可以分為兩大類：一種是基于測距的定位算法，例如：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é)點定位的精度很大依靠于節(jié)點的測距精度，而由于節(jié)點與節(jié)點之間的通信過程容易受到復(fù)雜環(huán)境因素、多路徑損耗及傳輸路徑損耗等影響，使得節(jié)點間的定位誤差較大。如今，考慮這些因素的定位算法已經(jīng)取得了較高的定位精度，如李建坡等提出的基于RSSI值節(jié)點不規(guī)則傳播模型的三維定位算法[10]、姚國提出基于RSSI值的獨立目標的定位和跟蹤的銳利指數(shù)模型[11]。

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

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

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

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

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

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

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

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

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

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

信號衰減模型為

(1)

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

將式(1)進行簡化得

(2)

其中。

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

(3)

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

圖1　錨節(jié)點分布圖

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

(4)

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

(5)

由式(5)可得

(6)

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

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

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

(7)

(8)

(9)

(10)

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

STRESS=∑(d^ij-dij)2

(11)

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

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

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

(12)

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

(13)

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

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

3實驗結(jié)果與分析

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

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

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

實驗結(jié)果采用平均定位誤差進行衡量算法的性能指標，平均定位誤差為

(14)

歸一化誤差為

(15)

3.2算法的性能分析

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

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

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

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

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

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

4總結(jié)

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

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

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

責任編輯：薛京

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

中圖分類號:TN92

文獻標志碼：A

DOI：10.16280/j.videoe.2016.03.021

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

作者簡介：

收稿日期：2015-07-18

文獻引用格式：鄔春明，宋強歡，楊濤.一種改進的分布式多維定標算法的研究[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.