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

王 越， 周 奧， 劉金城

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

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

王 越， 周 奧， 劉金城

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

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

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

0 引 言

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

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

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

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

1 非測距混合定位算法

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

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

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

(1)

(2)

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

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

圖2 非測距混合定位算法

整個(gè)算法的步驟如下：

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

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

(3)

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

2 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

[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].計(jì)算機(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ìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，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

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

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

TP 393

A

1000—9787(2015)02—0147—03

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