王 越， 周 奧， 劉金城

(重慶理工大學 計算機科學與技術(shù)學院,重慶 400054)

無線傳感器網(wǎng)絡(luò)中非測距混合定位算法*

王 越， 周 奧， 劉金城

(重慶理工大學 計算機科學與技術(shù)學院,重慶 400054)

節(jié)點定位是無線傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)。針對質(zhì)心定位算法和DV-Hop算法的不足，提出了一種非測距混合定位算法，采用DV-Hop算法得到節(jié)點之間的距離和粗略的未知節(jié)點估計坐標以作為質(zhì)心定位算法的權(quán)重，經(jīng)過兩次加權(quán)質(zhì)心定位算法得到未知節(jié)點更為精確的坐標。仿真實驗結(jié)果表明:在不同情況下，該混合算法均能獲得比兩種原始算法更高的定位精度；與其他混合定位算法相比，計算量小，耗能更低。

無線傳感器網(wǎng)絡(luò)； DV-Hop算法； 質(zhì)心定位算法; 混合； 非測距

0 引 言

無線傳感器網(wǎng)絡(luò)系統(tǒng)主要應用于人為力量無法到達的環(huán)境復雜區(qū)域事件的監(jiān)測和數(shù)據(jù)的采集與傳輸，而事件發(fā)生的位置對于監(jiān)測消息是至關(guān)重要的，沒有位置信息的監(jiān)測消息是毫無意義的，因此，需要利用定位技術(shù)來確定相應節(jié)點的位置信息。

在無線傳感器網(wǎng)絡(luò)定位算法中，可分為基于距離(range-based)和距離無關(guān)(range-free)的定位算法。基于距離的定位算法有以下幾種常見測距方法：基于到達時間(time of arrival,TOA)的測距方法[1]、基于到達時間差(time difference of arrival,TDOA)的測距方法[2]、基于接收信號強度指示(received signal strength indication,RSSI)的測距方法[3]。文獻[4]中給出了基于TOA定位的一種簡單實現(xiàn)，即采用偽噪聲序列信號作為聲波信號，根據(jù)聲波的傳播時間來測量節(jié)點間的距離。距離無關(guān)的定位技術(shù)不需要測量目標的距離或者方位角，對節(jié)點的硬件要求不高，但定位誤差往往要比基于距離的定位方法要高。距離無關(guān)的定位方法需要確定包含待測目標的可能區(qū)域，以此確定目標位置，主要的算法包括質(zhì)心(centroid)定位算法、距離向量—跳段(DV-Hop)定位算法、自組織定位(amorphous positioning)算法、近似三角形內(nèi)點測試(APIT)法[5]等。

現(xiàn)有的混合定位算法基本是將基于距離和距離無關(guān)的定位方法結(jié)合起來以獲得更高的定位精度，文獻[6]提出了采用RSSI的改進質(zhì)心定位算法，將RSSI作為質(zhì)心定位的算法的權(quán)重求得未知節(jié)點坐標。文獻[7]提出了一種基于RSSI測距誤差修正的改進型DV-Distance差分定位算法。由于使用了基于距離的技術(shù)，這些混合定位算法需要外在的硬件設(shè)備支持，成本和能耗上沒有優(yōu)勢；基于RSSI的測距方法雖然在實驗環(huán)境中表現(xiàn)出良好的特性，但是在實際環(huán)境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得該技術(shù)在實際應用中仍然存在困難。

本文所提出的DV-Hop和加權(quán)質(zhì)心定位算法的混合定位算法是基于非測距技術(shù)的，DV-Hop算法和質(zhì)心定位算法均是基于網(wǎng)絡(luò)連通性，無需信標節(jié)點和未知節(jié)點協(xié)調(diào)，只需要節(jié)點之間能相互通信，較基于測距技術(shù)的混合定位算法實現(xiàn)比較簡單，也不需要外在的硬件設(shè)備支持，成本很低，受環(huán)境影響小，通過仿真實驗表明:混合定位算法可以獲得比原有兩種基礎(chǔ)算法更好的定位精度。

1 非測距混合定位算法

在DV-Hop算法中，未知節(jié)點和錨節(jié)點之間的距離用平均每跳距離與跳數(shù)的乘積所求得，因此,在分布均勻、各項同性[8]的網(wǎng)絡(luò)中誤差較小。對傳統(tǒng)的DV-Hop算法分析可知，無線傳感器網(wǎng)絡(luò)中節(jié)點均為隨機分布，并且使用平均跳距來計算未知節(jié)點與錨節(jié)點之間的距離，并不能準確反映網(wǎng)絡(luò)中的實際平均每跳距離，因此，定位精度較低，定位誤差較大。同時，質(zhì)心定位算法也適合在錨節(jié)點分布密集和節(jié)點分布均勻的的網(wǎng)絡(luò)。如圖1，A,B,C,D,E,F,G點為已知位置坐標的錨節(jié)點，X為待定位的節(jié)點，如果使用質(zhì)心定位算法來計算的X的坐標，由于有奇異點D的存在，使得圖形的重心發(fā)生向D的傾斜，故而所求得的X的坐標將出現(xiàn)較大的誤差[9]。

針對以上這兩種算法的優(yōu)缺點，在本文中提出了一種基于DV-Hop和加權(quán)質(zhì)心定位的混合定位算法。根據(jù)概率論原理[10]，這兩種定位算法都是為了準確計算出未知節(jié)點的坐標，如果所計算出的坐標差值越小，那么,這些坐標就越接近未知節(jié)點的真實坐標?；旌隙ㄎ凰惴ǖ幕舅枷胧牵菏紫仁褂肈V-Hop定位算法得到每個錨節(jié)點的平均每跳距離和未知節(jié)點的粗略坐標，然后以質(zhì)心定位算法為基礎(chǔ)，進行兩次加權(quán)質(zhì)心定位，權(quán)值反映出不同錨節(jié)點坐標對未知節(jié)點坐標估計的影響大小。采用這種思想的目的是因為在錨節(jié)點數(shù)目較少的情況下DV-Hop算法定位精度要高于質(zhì)心定位算法的精度，此時通過DV-Hop算法對加權(quán)質(zhì)心定位算法中權(quán)值的影響來提高混合定位算法的定位精度，而當錨節(jié)點數(shù)目增加到一定數(shù)目時，質(zhì)心定位算法將優(yōu)于DV-Hop算法，混合定位算法經(jīng)過兩次加權(quán)的目的就是使得DV-Hop算法對混合定位算法不產(chǎn)生特別大的影響，使得在質(zhì)心定位算法效果較好的情況下，混合定位算法的定位精度主要依賴于質(zhì)心定位算法。具體的算法如下：

假設(shè)在未知節(jié)點通信半徑中的錨節(jié)點數(shù)量為N，用DV-Hop定位算法求得未知節(jié)點到錨節(jié)點的距離和未知節(jié)點的估計坐標P0，依此從中選出N個錨節(jié)點使用加權(quán)質(zhì)心定位算法，得到 個重心Z1,Z2,…,ZN。權(quán)值計算方法和加權(quán)質(zhì)心定位算法如下

(1)

(2)

在第一次加權(quán)質(zhì)心定位算法中，Ri,Rj為未知節(jié)點到錨節(jié)點的估計距離，N為未知節(jié)點通信半徑內(nèi)的錨節(jié)點數(shù)量，Wi為錨節(jié)點i的權(quán)值。第二次加權(quán)知心定位算法中，Ri,Rj為P0與Zi之間的距離，N為第一次加權(quán)求得的重心數(shù)量，Wi為重心Zi的權(quán)值。

如圖2所示，P為未知節(jié)點，P0為使用DV-Hop所計算出來的未知節(jié)點坐標，A,B,C,D,E,F,G為P通信半徑內(nèi)的錨節(jié)點，從這7個錨節(jié)點中依此選出7個使用質(zhì)心定位算法得到了Z1,Z2,Z3,Z4,Z5,Z6,Z7。然后用求得的P0和7個重心第二次使用加權(quán)質(zhì)心定位算法從而估算出更精確的未知節(jié)點的坐標。

圖2 非測距混合定位算法

整個算法的步驟如下：

1)對未知節(jié)點P使用DV-Hop算法，得到P與通信半徑內(nèi)錨節(jié)點之間的距離Ri，同時估計出P的坐標P0。

2)依此從未知節(jié)點P通信半徑內(nèi)的N個錨節(jié)點中選出N-1個使用式(1)和式(2)得到N個重心Z1,Z2,…,ZN，計算出P0和這N個重心之間的距離

(3)

3)根據(jù)上一步所得的距離再一次使用質(zhì)心定位算法得到更精確的估計坐標。

2 仿真實驗

通過Matlab仿真平臺對算法進行了驗證，并且在相同的實驗環(huán)境中與質(zhì)心定位算法、DV-Hop算法以及一種混合定位算法進行了對比實驗，最后在此基礎(chǔ)上對實驗結(jié)果進行了分析。

仿真實驗環(huán)境為：網(wǎng)絡(luò)節(jié)點隨機分布在200 m×200 m的矩形區(qū)域中，通信半徑為R=50 m。同樣進行100次實驗。

1)錨節(jié)點數(shù)量對定位精度的影響

節(jié)點數(shù)量為200個，在改變錨節(jié)點比例的情況下，質(zhì)心定位算法、DV-Hop算法和混合定位算的性能如圖3所示。隨著錨節(jié)點數(shù)量的不斷上升，質(zhì)心定位算法、DV-Hop算法和混合定位算法的定位精度也不斷上升。從圖4可以看出:當錨節(jié)點數(shù)目小于40的時，改進的混合定位算法的定位誤差要高于DV-Hop算法，但它們的曲線十分的相似，它們的相關(guān)性系數(shù)為0.955 1，而質(zhì)心定位算法與混合定位算法的相關(guān)性系數(shù)為0.881，這是由于錨節(jié)點數(shù)目比較小的時質(zhì)心定位算法定位誤差比DV-Hop算法定位誤差高15 %左右，故而此時的混合定位算法主要依賴于DV-Hop算法。隨著錨節(jié)點數(shù)目的增加，混合定位算法的定位誤差不斷減小，質(zhì)心定位算法定位精度不斷提高，并且逐漸優(yōu)于DV-Hop算法，此時混合定位算法對DV-Hop算法、質(zhì)心定位算法的相關(guān)系數(shù)分別為0.898 4和0.958 4，這說明混合定位算法定位在此時主要依賴于質(zhì)心定位算法。

圖3 錨節(jié)點比例對定位精度的影響

2)節(jié)點數(shù)量對定位精度的影響

錨節(jié)點比例為30 %，在改變傳感器網(wǎng)絡(luò)中節(jié)點數(shù)量的情況下，質(zhì)心定位算法、DV-Hop算法和混合定位算法的性能如圖4所示?？梢钥吹皆诠?jié)點數(shù)量不斷增加的情況下，三種算法的定位誤差都有著明顯的下降，這是由于網(wǎng)絡(luò)中未知節(jié)點周圍的鄰居節(jié)點越多，那么所獲得的參考位置信息也就越多，從而將降低定位誤差。從圖4可以看出，混合定位算法的定位精度要高于原有的兩種算法，混合定位算法的定位誤差比DV-Hop算法平均減少10 %左右。

圖4 節(jié)點數(shù)量對定位精度的影響

3)通信半徑對定位精度的影響

節(jié)點數(shù)量為200個，錨節(jié)點比例為30 %,在改變節(jié)點通信半徑的情況下，質(zhì)心定位算法、DV-Hop算法和混合定位算的性能如圖5所示。隨著節(jié)點通信半徑的增加，三種定位算法的定位精度也隨之增加，這是由于通信半徑增加，網(wǎng)絡(luò)連通性更好，節(jié)點與節(jié)點之間的通信增加，從而未知節(jié)點所獲得的參考信息也就更多，錨節(jié)點的平均跳距也就更加準確。從圖5可知，混合定位算法要明顯優(yōu)于兩種原始的算法，混合定位算法的定位誤差比DV-Hop算法平均減少5 %～7 %。

圖5 通信半徑對定位精度的影響

4)在不同錨節(jié)點數(shù)量情況下與其他混合定位算法比較

文獻[11]提出了一種RSSI和DV-Hop的混合算法，圖6是本文非測距混合定位算法與此種算法的仿真實驗結(jié)果。實驗環(huán)境為：網(wǎng)絡(luò)節(jié)點隨機分布在100 m×100 m的矩形區(qū)域中，節(jié)點數(shù)量為200個，通信半徑為R=20 m。

如圖6所示仿真結(jié)果，隨著錨節(jié)點數(shù)目的提高，兩種算法的定位精度都得到很大的提高，文獻[12]的混合算法與本文的改進算法的定位精度差異不大，但是文獻[12]的算法中使用了RSSI技術(shù)，這是一種利用信號衰減來估算距離的技術(shù)，必然會帶來更高的算法復雜度和更大的計算量。

圖6 與其他混合定位算法比較

3 結(jié)束語

本文對DV-Hop算法和質(zhì)心定位算法進行了簡單的介紹與分析，提出了一種基于DV-Hop算法和質(zhì)心定位算法的混合定位算法。它采用DV-Hop算法得到節(jié)點之間的距離和粗略的未知節(jié)點估計坐標以作為質(zhì)心定位算法的權(quán)重，經(jīng)過兩次加權(quán)質(zhì)心定位算法得到未知節(jié)點更為精確的坐標。仿真實驗表明:混合定位算法比原始算法定位精度更高，與其他混合的定位算法相比較定位精度差異不大，計算量更小。

[1] Harter A,Hopper A,Steggles P,et al.The anatomy of a context-aware application[C]∥Proc of the 5th Annual ACM/IEEE Int’l Conf on Mobile Computing and Networking,Seattle:ACM,1999:59-68.

[2] Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing[C]∥Proc of IEEE/RSJ Int’l Conf on Inte-lligent Robots and Systems,IROS’01,Maui:IEEE Robotics and Automation Society,2001:1312-1320.

[3] Girod L,Bychovskiy V,Elson J,et al.Locating tiny sensors in time and space:A case study[C]∥Proc of the 2002 IEEE Int’l Conf on Computer Design:VLSI in Computers and Processors,Freiburg:IEEE Computer Society,2002:214-219.

[4] Yang Z,Pan J,Cai L.Adaptive clock skew estimation with interactive multi-model Kalman filters for sensor network[C]∥Proceeding of IEEE International Conference on Communication,ICC 2010,Cape Town,South Africa,2010:1-5.

[5] Azzedine Boukerche.DV-LOC:A scalable localization protocol using voronoi diagrams for wireless sensor networks[J].IEEE Wireless Communications,2009,9:50-55.

[6] 李文辰，張 雷.無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法研究[J].計算機仿真，2013,30(2)：191-194.

[7] Bulusu N,Heidemann J.GPS-less low-cost outdoor localization for very small devices[J].IEEE Personal Communications,2000,7(5):28-34.

[8] Schuhmann Stephan,Herrmann Klaus,Rothermel Kurt,et al.Improved weighted centroid localization in smart ubiquitous environments[EB/OL].[2008—06—23].http:∥www.Springer-Iink.comlindex/131121u67r12445u.pdf.

[9] Bai Jinjing,Yan Xinping,Zhang Cunbao,et al.Research of location based on mixed algorithm of weighted centroid and DV-Hop in WSNs[J].Application Research of Computers,2009,26(6):2248-2250.

[10] Cheng Yuanguo,Xu Hui.Hops-weighted centroid localization algorithm for wireless sensor networks[J].Computer Engineering and Application,2009,45(7):105- 107.

[11] 金 純，葉 誠，韓志斌，等.無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進[J].計算機工程與設(shè)計，2013,34(2):401-404.

Range-free and hybrid localization algorithm forwireless sensor networks*

WANG Yue, ZHOU Ao, LIU Jin-cheng

(School of Computer Science and Technology,Chongqing University of Technology,Chongqing 400054,China)

Node localization is a significant technology in wireless sensor networks(WSNs).Aiming at deficiency of centroid localization algorithm and DV-Hop algorithm,a range-free and hybrid localization algorithm is proposed,uses DV-Hop algorithm to get rough distance between different nodes and rough-estimated unknown node coordinate for weigh of centroid localization algorithm.By twice-weighed centroid computation,more precise coordinate of unknown node can be obtained．Simulation results show that this algorithm improves the precision of node localization compared with two original localization algorithms,and its calculation amount and energy consumption are lower than other hybrid localization algorithms.

wireless sensor networks(WSNs); DV-Hop algorithm; centroid localization algorithm; hybrid; range-free

2014—06—15

重慶市科學技術(shù)委員會科技攻關(guān)項目(2009AC2068)

10.13873/J.1000—9787(2015)02—0147—03

TP 393

A

1000—9787(2015)02—0147—03

王 越(1961-),男,重慶人,博士,教授,現(xiàn)從事計算機技術(shù)與無線傳感器網(wǎng)絡(luò)方向教學和研究工作。