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

鄔春明，宋強歡，楊　濤

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

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

鄔春明，宋強歡，楊濤

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

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

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

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

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

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

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

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

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

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

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

階段5：根據錨節點在全局相對坐標圖中相對坐標與絕對坐標之間的轉換關系，將網絡中所有節點的相對坐標轉換成絕對坐標。

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

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

信號衰減模型為

(1)

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

將式(1)進行簡化得

(2)

其中。

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

(3)

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

圖1　錨節點分布圖

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

(4)

節點n1與節點n2,n3可得

(5)

由式(5)可得

(6)

2.1錨節點參數對的加權算法

由節點n1與節點n2,n3可以得到環境影響參數λ1和信號傳輸衰減參數S1，相應地，節點n1與節點n2,n4、節點n3,n4可得到環境影響參數和信號傳輸衰減參數λ2、S2和λ3、S3。

則通過加權可得

(7)

(8)

(9)

(10)

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

STRESS=∑(d^ij-dij)2

(11)

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

2.2采用最小二乘算法優化參數對

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

(12)

則最小脅強系數為

(13)

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

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

3實驗結果與分析

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

3.1仿真環境與參數設置

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

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

(14)

歸一化誤差為

(15)

3.2算法的性能分析

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

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

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

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

a 錨節點數量M=8，高斯噪聲方差δ=2

b 錨節點數量M=10，高斯噪聲方差δ=2

4總結

在真實環境下，節點間通信容易受到環境因素和傳輸衰減因素的影響，因此，在MDS-MAP(P)算法的基礎上提出了WMDS-MAP(P)算法，從仿真結果中可以看出改進的算法能夠克服復雜環境的影響，且平均定位誤差降低17%左右。將該算法的改進部分用于其他基于MDS-MAP(P)改進算法中，可以提高一定的節點定位精度。未來工作是將考慮無線傳感器網絡區域為不規則區域時，該改進算法是否依然能夠獲得較好的定位精度。同時，考慮在改進算法的基礎上減少在局部相對坐標轉換為全局絕對坐標時產生的誤差，從而實現更高的定位精度。

參考文獻：

[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]劉春平. 基于多維尺度分析的三維非均勻無線傳感網定位算法研究[D].杭州：杭州電子科技大學，2014.

鄔春明(1966— )，碩士，教授，碩士生導師，從事無線通信技術領域科學研究與教學工作；

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

楊濤(1991— )，碩士生，主要從事無線傳感網絡定位及系統硬件設計的研究。

責任編輯：薛京

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

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

作者簡介：

收稿日期：2015-07-18

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