基于錨節(jié)點分布特性的跳距修正的DV-HOP定位算法?

李躍飛

(湖南信息學院計算機科學與工程學院，湖南 長沙410014)

隨著電子技術的發(fā)展，無線傳感網絡(Wireless Sensor Networks，WSNs)已在康復醫(yī)療、工業(yè)監(jiān)測等領域廣泛使用。WSNs中的節(jié)點先感測環(huán)境數(shù)據(jù)，再將數(shù)據(jù)傳輸匯聚節(jié)點，進而實現(xiàn)對環(huán)境的監(jiān)測目的。具有準確位置信息的感測數(shù)據(jù)才具有意義。因此，定位成為WSNs領域的一個研究熱點之一[1－2]。

盡管全球定位系統(tǒng)(Global Position System，GPS)[3]定位技術很成熟，但是將WSNs中所有傳感節(jié)點配備GPS，成本太高，而且節(jié)點運行GPS增加了節(jié)點的能量消耗。對于微型的、能量有限的節(jié)點而言，高的能量消耗是無法接受的。

因此，通常在網絡內只允許部分節(jié)點配置GPS，使這些節(jié)點能夠獲取自己的位置，常將它們稱為參考節(jié)點或錨節(jié)點。現(xiàn)存的定位算法可分為測距定位和非測距定位算法。如基于接收信號強度指標(Receiver Signal Strength Indicator，RSSI)、到達角度和到達時間差(Time Difference of Arrival，TDOA)[4]屬基于測距定位算法。相比于非測距定位算法，測距定位算法需一些硬件設備，增加了定位算法的成本以及開銷。

據(jù)此，非測距定位算法，如質心定位[5]、DVHOP[6]在WSNs中廣泛應用。這些非測距定位算法利用跳數(shù)等連通信息估計節(jié)點位置。目前，研究人員對非測距定位算法進行了深入研究，并得到較滿意的定位精度[7－8]。然而，這些算法是基于同構的節(jié)點網絡。在實際環(huán)境場景中，節(jié)點間的通信區(qū)域是不規(guī)則的，并且受障礙物影響，容易形成異構網絡，這就影響了定位性能。此外，隨機部署節(jié)點無法保證錨節(jié)點在網絡內的分布的均勻性。這直接影響節(jié)點的定位精度。

為此，本文考慮到實際環(huán)境，正視錨節(jié)點分布的均勻性問題，提出對跳距修正的DV-HOP定位算法HDCD。HDCD算法利用全局錨節(jié)點信息以及局部信息對跳距進行修正，減少測距誤差。在不同拓撲結構下分析HDCD算法的定位性能。性能分析表明，提出的HDCD算法提高了定位精度，增強了對錨節(jié)點分布不均勻的惡劣環(huán)境的強健性。

1 系統(tǒng)模型

N個傳感節(jié)點隨機分布于二維(2-D)網絡區(qū)域?×?，如圖1所示，其中錨節(jié)點占比為p%，未知節(jié)點占比為(100－p)%。令αi表示第i個錨節(jié)點，其位置坐標為；令sj表示第j個未知節(jié)點，其位置坐標為(xj，yj)。

圖1 網絡模型

假定所有節(jié)點具有相同的通信半徑Rt。每個節(jié)點在其通信范圍內能夠與它的鄰居節(jié)點進行直接通信。錨節(jié)點利用GPS獲取其自身的位置。

與傳統(tǒng)的定位算法不同，本文假定區(qū)域內存在障礙物，如建筑物、樹。這些障礙物影響節(jié)點間信號的傳輸，增加跳距估計的誤差。此外，考慮錨節(jié)點分布不均勻性對定位精度的影響。本文針對上述問題，對平均跳距進行修正，進而提高定位精度。

2 HDCD定位算法

傳統(tǒng)的DV-HOP算法并沒有考慮到錨節(jié)點分布是否均勻問題。然而，在實際環(huán)境中，錨節(jié)點分布是不均勻的。換而言之，傳統(tǒng)的DV-HOP算法嚴重依賴于錨節(jié)點的分布。針對此問題，HDCD算法對未知節(jié)點與錨節(jié)點間的距離進行修正。

2.1 錨節(jié)點的全局跳距修正

首先，依據(jù)傳統(tǒng)DV-HOP算法[9]的策略，計算未知節(jié)點與錨節(jié)點間的最小跳數(shù)。具體過程如圖2所示。錨節(jié)點廣播beacon包，其包含其位置以及該beacon包被傳輸?shù)奶鴶?shù)Nh，最初Nh＝0。

圖2 beacon包的處理流程

一旦收到beacon包，節(jié)點就判斷是否之前已接收過此包。若是第一次接收，就從beacon包中提取發(fā)送節(jié)點的位置以及跳數(shù)信息。并更新beacon包中跳數(shù)值(Nh＋1)，再轉播。若之前已接收過此beacon，就將目前所接收的beacon包跳數(shù)值與之前存儲的跳數(shù)值進行比較，并且保存兩者中的最小值。

然后，錨節(jié)點就依據(jù)式(1)計算平均跳距:

傳統(tǒng)的DV-HOP算法是利用式(1)計算錨節(jié)點的平均跳距。這存在較大誤差，其并沒有充分利用錨節(jié)點的已知信息計算平均跳距的誤差。為此，HDCD算法利用錨節(jié)點的已知信息，計算式(1)所計算的平均跳距的誤差。式中:εi表示錨節(jié)點αi端所計算的平均跳距的誤差。

因此，利用該誤差εi對(i)進行修正，如式(3)所示:

2.2 錨節(jié)點的局部跳距修正

由于節(jié)點是隨機分布于監(jiān)測區(qū)域，網絡拓撲結構的不規(guī)則概率較大。因此，僅從全局拓撲結構修正跳距是不準確的。為此，HDCD算法也從局部拓撲結構對跳距進行修正。

式中:M表示估計一個未知節(jié)點位置至少需要的錨節(jié)點數(shù)；m＝p%×N表示網絡內的錨節(jié)點數(shù)；?×?表示監(jiān)測的區(qū)域面積。

錨節(jié)點將其獲取的離其他錨節(jié)點的跳數(shù)值進行比較，計算在小于跳數(shù)范圍內的單跳平均跳距。

不失一般性，平均每跳的誤差服從高斯分布。利用參數(shù)估計理論，通過估計誤差建立代價函數(shù)，再依據(jù)最小均方誤差準則獲取平均跳距[11]。具體過程如下。

構建代價函數(shù)，如式(6)所示:

2.3 未知節(jié)點離錨節(jié)點的距離估計

在真實環(huán)境中，兩節(jié)點間的真實距離與其估計的距離差值并不相同。有些差值小，有些差值大。而依據(jù)式(1)可知，平均跳距與兩節(jié)點間的歐式距離成正比，與它們間中跳數(shù)成反比。

如圖3所示，圖3中有兩個錨節(jié)點(αr、αq)。利用它們間的歐式距離以及它們間的跳數(shù)值計算平均跳距。通常，所估計的距離總是小于它們間的真實距離，如圖3(a)所示。在這種情況下，通過修正它們的平均跳距，降低定位誤差，提高定位精度。

圖3 三類情況分析

當存在障礙物時，錨節(jié)點間的跳數(shù)越大，且所估計的它們間距離小于它們真實的距離，如圖3(b)所示。在這種情況下，它們的平均跳距偏小，也需要對它們的平均跳進行修正。

第三種情況:當錨節(jié)點間跳數(shù)較少，所估計的距離與實際距離偏差較小。如圖3(c)所示。在這種情況下，平均跳距對定位精度影響偏小。

依據(jù)上述分析的三種情況可知，并結合2.1節(jié)和2.2節(jié)，未知節(jié)點利用式(8)估計距離:

2.4 基于最小二乘法的位置估計

未知節(jié)點利用式(8)獲取離錨節(jié)點間的距離，即測距。假定未知節(jié)點sj獲取了離κ個錨節(jié)點的距離，令αj，1，αj，2，…，αj，k，…αj，κ表示這些錨節(jié)點。未知節(jié)點sj所測量的離這個κ個錨節(jié)點的距離分別表示為

有κ個錨節(jié)點就能構建κ個等式。參照式(10)，第κ個等式為:

3 性能分析

利用MATLAB R2016a軟件建立仿真平臺，分析HDCD算法的性能。由于本文旨在分析錨節(jié)點的分布均勻性對定位精度的影響，建立四個不同拓撲結構的網絡，它們的各項參數(shù)值如表1所示。

表1 四種網絡拓撲結構的參數(shù)值

選用通信半徑歸一化后的平均定位誤差作為性能指標，其定義如式(18)所示:

此外，選擇同類的DV-HOP定位算法為參照，對比分析在四種不同拓撲結構下它們的定位誤差性能。考慮到隨機誤差，每種拓撲結構下，獨立重復100次，取平均值作為最終的仿真數(shù)據(jù)。

3.1 Scene-one環(huán)境下的定位性能

圖4給出Scene-one環(huán)境下的拓撲結構示例，其中未知節(jié)點數(shù)為100，錨節(jié)點數(shù)為8，錨節(jié)點分布均勻。從圖4可知，8個錨節(jié)點較均勻地分布在監(jiān)測區(qū)域內。

圖4 Scene-one的網絡拓撲示例(8個錨節(jié)點)

圖5 給出DV-HOP算法和HDCD算法在Sceneone環(huán)境下歸一化定位誤差。從圖可知，相比于DVHOP算法，提出的HDCD算法降低了定位誤差。此外，錨節(jié)點比例的增加，有利于定位誤差的下降。但是定位誤差與錨節(jié)點數(shù)并非呈線性關系。

圖5 歸一化平均定位誤差(Scene-one)

3.2 Scene-one環(huán)境下的定位性能

圖6 給出Scene-two的網絡拓撲結構示例，其中未知節(jié)點數(shù)為100，錨節(jié)點數(shù)為10，錨節(jié)點分布不均勻。從圖可知，相比于圖5的Scene-one，網絡Scene-two中錨節(jié)點分布集中，未能在監(jiān)測區(qū)域內均勻分布。

圖6 Scene-two的網絡拓撲結構示例(10個錨節(jié)點)

圖7給出Scene-two網絡環(huán)境下HDCD算法和DV-HOP算法的定位誤差隨錨節(jié)點數(shù)的變化情況。從圖可知，錨節(jié)點數(shù)的增加降低定位誤差。原因在于:錨節(jié)點數(shù)的增加，使未知節(jié)點獲取的測距信息越多，測距誤差越低。

圖7 歸一化平均定位誤差(Scene-two)

此外，相比于Scene-one條件，Scene-two條件下的定位誤差偏大。原因在于:錨節(jié)點分布不均勻。離錨節(jié)點遠的未知節(jié)點，測距誤差較大，不不利于定位，導致定位精度下降。

3.3 Scene-three環(huán)境下的定位性能

圖8給出Scene-three的網絡拓撲結構示例，其中未知節(jié)點數(shù)為100，錨節(jié)點數(shù)為10。監(jiān)測區(qū)域內有障礙物，阻礙節(jié)點間直接通信。而在遠離障礙物的區(qū)域錨節(jié)點分布較均勻。

圖8 Scene-three的示例(10個錨節(jié)點)

圖9 給出Scene-three網絡環(huán)境下HDCD算法和DV-HOP算法的定位誤差。從圖可知，錨節(jié)點數(shù)量的增加，使定位誤差下降。這符合預期。此外，對比看圖8與圖7不難發(fā)現(xiàn)，Scene-three環(huán)境下的定位精度高于Scene-two環(huán)境下的定位精度。原因在于:盡管Scene-three存在障礙物，除障礙物所在區(qū)域外的其他區(qū)域，錨節(jié)點分布均勻。

圖9 歸一化平均定位誤差(Scene-three)

3.4 Scene-four環(huán)境下的定位性能

圖10 給出Scene-four的拓撲結構示例，其中未知節(jié)點數(shù)為100，錨節(jié)點數(shù)為14。監(jiān)測區(qū)域內有障礙物，阻礙節(jié)點間直接通信。而在遠離障礙物的區(qū)域錨節(jié)點分布不均勻。

圖10 Scene-four的示例(14個錨節(jié)點)

圖11 給出Scene-four的網絡環(huán)境下HDCD算法和DV-HOP算法的定位誤差。從圖可知，錨節(jié)點數(shù)量的增加，使定位誤差下降。這符合預期。此外，對比看圖10與圖11不難發(fā)現(xiàn)，Scene-three環(huán)境下的定位精度高于Scene-four環(huán)境下的定位精度。原因在于:Scene-four的定位環(huán)境很惡劣:既存在障礙物，錨節(jié)點分布又不均勻。

圖11 歸一化平均定位誤差(Scene-four)

表2給出四個網絡拓撲環(huán)境下的定位誤差。從2可知，Scene-two和Scene-four兩種環(huán)境下的定位誤差低于Scene-one和Scene-three。這主要因為:Scene-one環(huán)境下錨節(jié)點分布均勻，又不存在障礙物。盡管Scene-three環(huán)境中存在障礙物，但是其錨節(jié)點分布是均勻的，并且其通信半徑為20 m。節(jié)點通信半徑的提高，有利于降低定位誤差。

表2 四個網絡拓撲環(huán)境下的定位誤差

4 總結

考慮到實際環(huán)境中錨節(jié)點分布的不均勻性對定位精度的影響，提出了跳距修正的DV-HOP定位算法HDCD。HDCD算法依據(jù)錨節(jié)點的分布特性對跳距進行修正，減少定位誤差。針對不同拓撲環(huán)境，分析了HDCD算法的定位性能。仿真結果表明，相比于DVHOP算法，HDCD算法在Scene-one、Scene-two、Scenethree和Scene-four網絡條件下的歸一化的平均定位誤差分別下降了約9%、6.5%、16%和37%。