陳 卡

(駐馬店職業(yè)技術(shù)學(xué)院公共教學(xué)部，河南 駐馬店 463000)

0 引言

隨著電子信息技術(shù)的發(fā)展以及電子元器件成本的下降，由價(jià)格低廉的傳感節(jié)點(diǎn)構(gòu)成的無(wú)線傳感網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)[1-2]已在軍事勘察、康復(fù)醫(yī)療、智能農(nóng)業(yè)方面得到廣泛應(yīng)用[3]。準(zhǔn)確地獲取節(jié)點(diǎn)位置信息有助于提高應(yīng)用效率。因此，估計(jì)節(jié)點(diǎn)位置成為WSNs領(lǐng)域的研究熱點(diǎn)。

現(xiàn)存的關(guān)于WSNs的定位算法可分為基于測(cè)距和非測(cè)距兩類(lèi)定位算法。測(cè)距定位算法需要測(cè)量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離，并且測(cè)距精度與定位精度密切相關(guān)。而非測(cè)距定位算法是通過(guò)網(wǎng)絡(luò)拓?fù)涞倪B通信息估計(jì)未知節(jié)點(diǎn)位置，定位精度受網(wǎng)絡(luò)拓?fù)溆绊慬4]。相比于測(cè)距定位算法，非測(cè)距定位算法成本較低。從成本角度，非測(cè)距定位算法更適用于WSNs。

DV-Hop算法屬經(jīng)典的非測(cè)距定位算法[5]，一直受到較大的關(guān)注。盡管DV-Hop算法的復(fù)雜性低，但是其存在一些不足，如最小跳數(shù)估計(jì)不準(zhǔn)，跳距估計(jì)誤差大。為此，研究人員提出不同的改進(jìn)策略。

任克強(qiáng)等[6]利用節(jié)點(diǎn)偏差系數(shù)對(duì)跳數(shù)估計(jì)值進(jìn)行修正，并利用最小均方誤差優(yōu)化平均跳距。盡管該算法對(duì)跳數(shù)和跳距進(jìn)行了修正，但是這只是提升了測(cè)距精度，并沒(méi)有對(duì)定位算法進(jìn)行優(yōu)化。測(cè)距只是定位算法的基礎(chǔ)。黃文永等[7]利用錨節(jié)點(diǎn)密度對(duì)每跳距離進(jìn)行修正，并利用錨節(jié)點(diǎn)坐標(biāo)以及密度對(duì)節(jié)點(diǎn)位置進(jìn)行校正，但是該算法要求高密度的錨節(jié)點(diǎn)。Cui L Z等[8]為了降低跳數(shù)估計(jì)的誤差，將離散的跳數(shù)轉(zhuǎn)化為連續(xù)值，再搜索節(jié)點(diǎn)位置的最優(yōu)解。盡管該算法能夠獲取高的定位精度，但是算法的復(fù)雜度很高，并不適合于低成本的WSNs網(wǎng)絡(luò)環(huán)境。

為此，綜合現(xiàn)有的文獻(xiàn)，本文先分析了導(dǎo)致DV-Hop算法定位精度不高的原因，再基于跳距修正的節(jié)點(diǎn)定位算法(Hop Distance-Corrected Localization,HDCL)。主要的工作歸納如下：①對(duì)估計(jì)節(jié)點(diǎn)位置的錨節(jié)點(diǎn)進(jìn)行篩選，避免因錨節(jié)點(diǎn)共線而出現(xiàn)定位盲區(qū)?，F(xiàn)存的多數(shù)定位算法并沒(méi)有錨節(jié)點(diǎn)的選擇問(wèn)題；②采用無(wú)偏估計(jì)對(duì)跳距進(jìn)行優(yōu)化處理，降低跳距估計(jì)誤差；③獲取測(cè)距數(shù)據(jù)后，再利用Jaya算法搜索節(jié)點(diǎn)位置，并對(duì)搜索的區(qū)域進(jìn)行約束，提高搜索精度。

1 DV-Hop定位算法

DV-Hop定位算法主要由以下三個(gè)階段構(gòu)成[9]：

1.1 最小跳數(shù)的估算階段

網(wǎng)絡(luò)內(nèi)所有錨節(jié)點(diǎn)在網(wǎng)絡(luò)內(nèi)廣播分組包Packet，其包含錨節(jié)點(diǎn)的位置以及Packet被傳遞的跳數(shù)Num_Hop。節(jié)點(diǎn)接收了分組包Packet后，先判斷是否首次接收該分組包。若是首次，就保存相關(guān)信息，再將Num_Hop+1，并向鄰居節(jié)點(diǎn)傳遞此分組包。若不是首次，就將當(dāng)前獲取的跳數(shù)值與存儲(chǔ)的跳數(shù)值進(jìn)行比較，保存最小的跳數(shù)值。通過(guò)分組包Packet的傳遞，使網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)獲取到錨節(jié)點(diǎn)的最小跳數(shù)值。

1.2 跳距的估算階段

依據(jù)第一階段所獲取的最小跳數(shù)值，錨節(jié)點(diǎn)先估計(jì)與其他錨節(jié)點(diǎn)間的平均每一跳的距離(簡(jiǎn)稱(chēng)平均跳距)：

(1)

式中，Hopsizei表示錨節(jié)點(diǎn)i所估計(jì)的平均跳距；dij表示錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j間的真實(shí)距離；Num_Hopij表示錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j間的最小跳數(shù)。

(2)

1.3 節(jié)點(diǎn)位置估計(jì)

未知節(jié)點(diǎn)獲取了到錨節(jié)點(diǎn)的估計(jì)距離后，便通過(guò)最大似然法估計(jì)未知節(jié)點(diǎn)的位置。

由于WSNs網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不規(guī)則性，錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的分布并不均勻，只利用跳數(shù)與跳距的乘積作為估計(jì)距離存在較大誤差。為此，HDCL算法從跳數(shù)、跳距和錨節(jié)點(diǎn)的分布角度對(duì)DV-Hop算法進(jìn)行改進(jìn)，進(jìn)而提高定位精度。

2 HDCL定位算法

考慮二維(2D)網(wǎng)絡(luò)區(qū)域?yàn)閘1×l2。n個(gè)未知節(jié)點(diǎn)，其位置坐標(biāo)為θi=[xi,yi]T，且θ∈R2。通過(guò)錨節(jié)點(diǎn)估計(jì)未知節(jié)點(diǎn)的位置。令αk=[xk,yk]T表示第k個(gè)錨節(jié)點(diǎn)的位置，且k=1,2,…,m。

2.1 基于無(wú)偏估計(jì)的平均跳距的修正

直接利用式(1)計(jì)算平均跳距存在較大誤差。為此，HDCL算法引用無(wú)偏估計(jì)對(duì)其進(jìn)行修正[10]。先建立跳距誤差函數(shù)?？紤]式(1)的差值，再對(duì)兩者間的差值進(jìn)行平方運(yùn)算：

(3)

采用無(wú)偏估計(jì)。為了獲取最小誤差，對(duì)式(3)進(jìn)行求導(dǎo)，并令求導(dǎo)后的等式為0：

(4)

再依據(jù)式(4)重新計(jì)算錨節(jié)點(diǎn)i的平均跳距：

(5)

2.2 基于共線度的錨節(jié)點(diǎn)的篩選

在估計(jì)節(jié)點(diǎn)位置時(shí)，需選擇3個(gè)錨節(jié)點(diǎn)，并建立相應(yīng)的距離方程。然而，如果所選擇的3個(gè)錨節(jié)點(diǎn)位于同一條直線，即共線，就無(wú)法估計(jì)節(jié)點(diǎn)位置，出現(xiàn)定位盲區(qū)[11]。

令Ni={a1,a2,a3}表示未知節(jié)點(diǎn)i所選擇的3個(gè)錨節(jié)點(diǎn)。先計(jì)算由這3個(gè)錨節(jié)點(diǎn)所形成的三角形的內(nèi)角的余弦值：

(6)

式中，d12、d13和d23分別表示錨節(jié)點(diǎn)a1與a2的距離、a1與a3距離和a2與a3距離。若αi=π，cosαi=-1時(shí)，其表明未知節(jié)點(diǎn)i所選擇的3個(gè)錨節(jié)點(diǎn){a1,a2,a3}共線。若αi=π/3，cosαi=1/2時(shí)，則未知節(jié)點(diǎn)i離3個(gè)錨節(jié)點(diǎn){a1,a2,a3}距離相等。利用這3個(gè)錨節(jié)點(diǎn)估計(jì)未知節(jié)點(diǎn)位置誤差最小。

因此，將cosαi作為共線度。未知節(jié)點(diǎn)利用共線度篩選錨節(jié)點(diǎn)。將共線度在0～0.5范圍內(nèi)的錨節(jié)點(diǎn)集作為自己用于定位的錨節(jié)點(diǎn)。篩選錨節(jié)點(diǎn)的步驟如下：

(1)先從鄰居錨節(jié)點(diǎn)選擇三個(gè)錨節(jié)點(diǎn)，再依據(jù)式(6)計(jì)算所選擇的三個(gè)錨節(jié)點(diǎn)的共線度；

(2) 判斷共線度是否在0～0.5范圍。若不在此范圍內(nèi)，就重新選擇。返回到式(1)。

以圖1為例，分析基于共線度的錨節(jié)點(diǎn)篩選過(guò)程。圖中A1、A2、A3和A4為錨節(jié)點(diǎn)，B1為未知節(jié)點(diǎn)。B1先選擇離自己較近的3個(gè)錨節(jié)點(diǎn){A1,A2,A3}，再依式(6)計(jì)算共線度cosα1。接下來(lái)，判斷是否滿(mǎn)足0

圖1 基于共線度的錨節(jié)點(diǎn)篩選

2.3 基于Jaya算法的節(jié)點(diǎn)位置估計(jì)

HDCL算法將Jaya算法[12]引入定位階段。Jaya算法具有較快的收斂性能。將估計(jì)節(jié)點(diǎn)位置轉(zhuǎn)換成目標(biāo)優(yōu)化問(wèn)題，即以定位誤差構(gòu)建目標(biāo)函數(shù)。

(7)

未知節(jié)點(diǎn)先通過(guò)修正后的最小跳數(shù)以及優(yōu)化后的跳距后,計(jì)算離錨節(jié)點(diǎn)的距離。然后,以錨節(jié)點(diǎn)位置為圓心以估計(jì)的距離為半徑形成圓的外接正方形。最后,以三個(gè)外接正方形所重疊的區(qū)域表示未知節(jié)點(diǎn)的可能區(qū)域，如圖2所示。

圖2 種群的可行區(qū)域

再在圖2所示的可能區(qū)域內(nèi)隨機(jī)生成種群。為了提高定位精度，種群依據(jù)式(8)的上、下界搜索未知節(jié)點(diǎn)位置：

(8)

2.4 定位步驟

算法1給出定位的具體步驟，如表1所示。

表1 HDLC算法的定位步驟

3 仿真與分析

3.1 仿真環(huán)境

利用MATLAB建立仿真平臺(tái)，分析HDCL算法的定位性能。在100 m×100 m區(qū)域內(nèi)隨機(jī)部署n個(gè)未知節(jié)點(diǎn)和m個(gè)錨節(jié)點(diǎn)。所有節(jié)點(diǎn)的通信半徑相同,且為R。具體的仿真參數(shù)如表2所示。

表2 仿真參數(shù)

選擇經(jīng)典的DV-Hop算法，胡玉蘭等[13]提出基于平均跳距優(yōu)化的DV-Hop改進(jìn)算法(Average Hop Distance Optimal DV-Hop，AHDD)作為參照，對(duì)比分析它們歸一化平均定位誤差：

(9)

3.2 錨節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響

首先分析錨節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響，如圖3所示，其中錨節(jié)點(diǎn)數(shù)從10～40變化，通信半徑為30 m，未知節(jié)點(diǎn)數(shù)為100。

圖3 錨節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響

從圖3可知,錨節(jié)點(diǎn)數(shù)的增加減少了平均定位誤差，提高定位精度。原因在于：錨節(jié)點(diǎn)數(shù)越多，未知節(jié)點(diǎn)能夠獲取的測(cè)距信息越多，越能夠篩選有利的錨節(jié)點(diǎn)集。但是，DV-Hop算法，AHDD和HDCL算法的平均定位誤差隨錨節(jié)點(diǎn)的變化情況并非相同。當(dāng)錨節(jié)點(diǎn)數(shù)小于15時(shí)，HDCL算法的平均定位誤差比AHDD算法的平均定位誤差下降了約12.5%～13%；當(dāng)錨節(jié)點(diǎn)數(shù)大于35時(shí)，HDCL算法的平均定位誤差比AHDD算法的平均定位誤差下降了約2.2%～3.6%。這說(shuō)明，在錨節(jié)點(diǎn)較少時(shí)，HDCL算法在平均定位誤差性能優(yōu)勢(shì)更明顯。原因在于：在錨節(jié)點(diǎn)較少時(shí)，AHDD和DV-Hop算法的平均跳數(shù)和跳距誤差更大。

3.3 通信半徑對(duì)平均定位誤差的影響

最后，分析通信半徑R對(duì)定位精度的影響。本次實(shí)驗(yàn)參數(shù):未知節(jié)點(diǎn)數(shù)n=100；錨節(jié)點(diǎn)數(shù)為20個(gè)；通信半徑從15 m～40 m變化。

圖4給出DV-Hop算法、AHDD算法和HDCL算法的平均定位誤差隨通信半徑R的變化情況。

圖4 節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響

可以看出,通信半徑的增加有利于降低平均定位誤差。原因在于：通信半徑越大,節(jié)點(diǎn)通信的范圍越大,能夠獲取的定位信息越多,這有利于提高定位精度。此外,相比于DV-Hop算法和AHDD算法,HDCL算法降低了平均定位誤差。在通信半徑較低時(shí),HDCL算法在平均定位誤差性能方面的優(yōu)勢(shì)更明顯。

3.4 未知節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響

最后，分析未知節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響，如圖5所示。未知節(jié)點(diǎn)數(shù)從100～200變化，通信半徑為40 m，錨節(jié)點(diǎn)數(shù)占未知節(jié)點(diǎn)數(shù)的比例為30%。例如，當(dāng)節(jié)點(diǎn)數(shù)200時(shí)，錨節(jié)點(diǎn)數(shù)為60個(gè)。

圖5 未知節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響

可以看出，平均定位誤差隨未知節(jié)點(diǎn)數(shù)的增加呈緩慢下降，變化較穩(wěn)定。相比于AHDD和DV-Hop算法，提出的HDCL算法有效地降低了平均定位誤差。這歸功于：HDCL算法通過(guò)跳距和跳數(shù)的優(yōu)化，并利用共線度篩選錨節(jié)點(diǎn)，避免共線問(wèn)題，提高了定位精度。

4 總結(jié)

針對(duì)傳統(tǒng)的DV-Hop算法的定位誤差，本文分析產(chǎn)生誤差的原因，并提出基于跳距修正的節(jié)點(diǎn)定位算法HDCL。HDCL算法通過(guò)無(wú)偏估計(jì)修正跳距，并考慮到參與估計(jì)未知節(jié)點(diǎn)位置的錨節(jié)點(diǎn)的共線問(wèn)題，通過(guò)共線度概念選擇適宜的錨節(jié)點(diǎn)。最后，利用Jaya算法估計(jì)節(jié)點(diǎn)位置。仿真結(jié)果表明，相比于DV-Hop算法和AHDD算法，HDCL算法降低了定位誤差。后期研究如何進(jìn)一步減少在估計(jì)跳數(shù)和跳距階段所累積的誤差，提升定位精度，這將是后續(xù)研究的重點(diǎn)方向。