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

李躍飛

(湖南信息學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙410014)

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

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

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

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

為此，本文考慮到實(shí)際環(huán)境，正視錨節(jié)點(diǎn)分布的均勻性問題，提出對(duì)跳距修正的DV-HOP定位算法HDCD。HDCD算法利用全局錨節(jié)點(diǎn)信息以及局部信息對(duì)跳距進(jìn)行修正，減少測(cè)距誤差。在不同拓?fù)浣Y(jié)構(gòu)下分析HDCD算法的定位性能。性能分析表明，提出的HDCD算法提高了定位精度，增強(qiáng)了對(duì)錨節(jié)點(diǎn)分布不均勻的惡劣環(huán)境的強(qiáng)健性。

1 系統(tǒng)模型

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

圖1 網(wǎng)絡(luò)模型

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

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

2 HDCD定位算法

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

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

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

圖2 beacon包的處理流程

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

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

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

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

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

由于節(jié)點(diǎn)是隨機(jī)分布于監(jiān)測(cè)區(qū)域，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不規(guī)則概率較大。因此，僅從全局拓?fù)浣Y(jié)構(gòu)修正跳距是不準(zhǔn)確的。為此，HDCD算法也從局部拓?fù)浣Y(jié)構(gòu)對(duì)跳距進(jìn)行修正。

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

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

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

構(gòu)建代價(jià)函數(shù)，如式(6)所示:

2.3 未知節(jié)點(diǎn)離錨節(jié)點(diǎn)的距離估計(jì)

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

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

圖3 三類情況分析

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

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

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

2.4 基于最小二乘法的位置估計(jì)

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

有κ個(gè)錨節(jié)點(diǎn)就能構(gòu)建κ個(gè)等式。參照式(10)，第κ個(gè)等式為:

3 性能分析

利用MATLAB R2016a軟件建立仿真平臺(tái)，分析HDCD算法的性能。由于本文旨在分析錨節(jié)點(diǎn)的分布均勻性對(duì)定位精度的影響，建立四個(gè)不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，它們的各項(xiàng)參數(shù)值如表1所示。

表1 四種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的參數(shù)值

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

此外，選擇同類的DV-HOP定位算法為參照，對(duì)比分析在四種不同拓?fù)浣Y(jié)構(gòu)下它們的定位誤差性能?？紤]到隨機(jī)誤差，每種拓?fù)浣Y(jié)構(gòu)下，獨(dú)立重復(fù)100次，取平均值作為最終的仿真數(shù)據(jù)。

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

圖4給出Scene-one環(huán)境下的拓?fù)浣Y(jié)構(gòu)示例，其中未知節(jié)點(diǎn)數(shù)為100，錨節(jié)點(diǎn)數(shù)為8，錨節(jié)點(diǎn)分布均勻。從圖4可知，8個(gè)錨節(jié)點(diǎn)較均勻地分布在監(jiān)測(cè)區(qū)域內(nèi)。

圖4 Scene-one的網(wǎng)絡(luò)拓?fù)涫纠?8個(gè)錨節(jié)點(diǎn))

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

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

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

圖6 給出Scene-two的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示例，其中未知節(jié)點(diǎn)數(shù)為100，錨節(jié)點(diǎn)數(shù)為10，錨節(jié)點(diǎn)分布不均勻。從圖可知，相比于圖5的Scene-one，網(wǎng)絡(luò)Scene-two中錨節(jié)點(diǎn)分布集中，未能在監(jiān)測(cè)區(qū)域內(nèi)均勻分布。

圖6 Scene-two的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示例(10個(gè)錨節(jié)點(diǎn))

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

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

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

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

圖8給出Scene-three的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示例，其中未知節(jié)點(diǎn)數(shù)為100，錨節(jié)點(diǎn)數(shù)為10。監(jiān)測(cè)區(qū)域內(nèi)有障礙物，阻礙節(jié)點(diǎn)間直接通信。而在遠(yuǎn)離障礙物的區(qū)域錨節(jié)點(diǎn)分布較均勻。

圖8 Scene-three的示例(10個(gè)錨節(jié)點(diǎn))

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

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

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

圖10 給出Scene-four的拓?fù)浣Y(jié)構(gòu)示例，其中未知節(jié)點(diǎn)數(shù)為100，錨節(jié)點(diǎn)數(shù)為14。監(jiān)測(cè)區(qū)域內(nèi)有障礙物，阻礙節(jié)點(diǎn)間直接通信。而在遠(yuǎn)離障礙物的區(qū)域錨節(jié)點(diǎn)分布不均勻。

圖10 Scene-four的示例(14個(gè)錨節(jié)點(diǎn))

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

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

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

表2 四個(gè)網(wǎng)絡(luò)拓?fù)洵h(huán)境下的定位誤差

4 總結(jié)

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