曹廣華 張紅杰

(東北石油大學(xué)電氣信息工程學(xué)院，黑龍江 大慶 163318)

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是由大量智能傳感器節(jié)點(diǎn)構(gòu)成的具有信息感知、信息傳送和信息處理能力的綜合型智能信息網(wǎng)絡(luò)，具有成本低、自組織和環(huán)境適應(yīng)性強(qiáng)的特點(diǎn)[1,2]。節(jié)點(diǎn)定位是WSN的關(guān)鍵技術(shù)之一，目前使用較多的無(wú)線傳感器網(wǎng)絡(luò)定位方法有基于測(cè)距的定位算法和無(wú)需測(cè)距的定位算法。筆者將對(duì)無(wú)需測(cè)距的DV-Hop定位算法進(jìn)行分析并對(duì)其加以改進(jìn)。

1.1 DV-Hop算法

根據(jù)節(jié)點(diǎn)是否已知自身的位置，傳感器節(jié)點(diǎn)分為信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)。信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中所占的比例小，可以通過(guò)攜帶GPS定位設(shè)備等措施獲得自身的精確位置，未知節(jié)點(diǎn)利用信標(biāo)節(jié)點(diǎn)的位置信息來(lái)確定自身位置。DV-Hop算法是一個(gè)典型的利用信標(biāo)節(jié)點(diǎn)間多跳信息來(lái)確定未知節(jié)點(diǎn)位置的定位策略，傳統(tǒng)DV-Hop算法可以分為以下3個(gè)步驟[3,4]。

首先獲取節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)。根據(jù)典型的距離矢量路由協(xié)議，每個(gè)信標(biāo)節(jié)點(diǎn)向網(wǎng)絡(luò)中廣播自身的位置信息分組，網(wǎng)絡(luò)中的全部節(jié)點(diǎn)能夠記錄下到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

然后計(jì)算信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離。每一個(gè)信標(biāo)節(jié)點(diǎn)按照自身列表中記錄的其余信標(biāo)節(jié)點(diǎn)的位置和最小跳數(shù)信息，計(jì)算平均每跳距離hopsizei，計(jì)算式為：

(1)

其中hij為信標(biāo)節(jié)點(diǎn)i和j的最小跳數(shù)；(xi,yi)、(xj,yj)分別為信標(biāo)節(jié)點(diǎn)i和j的坐標(biāo)。

未知節(jié)點(diǎn)根據(jù)接收到的平均跳距和記錄到的每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，通過(guò)下式計(jì)算出與每個(gè)信標(biāo)節(jié)點(diǎn)的距離：

d=hopsizei×N

(2)

其中，N為未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

最后利用三邊法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的自身位置。

1.2 DV-Hop算法誤差分析

DV-Hop算法是一種非測(cè)距方法，實(shí)現(xiàn)簡(jiǎn)單且能耗適中。在節(jié)點(diǎn)分布均勻的各向同性密集網(wǎng)絡(luò)中，節(jié)點(diǎn)的定位精度較高。但在網(wǎng)絡(luò)節(jié)點(diǎn)分布不均勻的網(wǎng)絡(luò)中，由于節(jié)點(diǎn)的隨機(jī)部署，信標(biāo)節(jié)點(diǎn)相對(duì)未知節(jié)點(diǎn)的數(shù)量和位置分布不均勻，致使信標(biāo)節(jié)點(diǎn)估計(jì)的平均每跳距離不能準(zhǔn)確地反映全網(wǎng)的平均每跳距離，在使用式(2)時(shí)會(huì)造成較大的累積誤差，對(duì)定位精度有很大程度的影響，所以未知節(jié)點(diǎn)需要選擇合適的信標(biāo)節(jié)點(diǎn)進(jìn)行定位才能使定位精度更準(zhǔn)確[5]。

2 DV-Hop改進(jìn)算法

筆者針對(duì)平均每跳距離誤差大的問(wèn)題，使用文獻(xiàn)[6]中提到的跳距誤差修正方法，使計(jì)算出的每跳距離盡可能地反映網(wǎng)絡(luò)的平均跳距。對(duì)于信標(biāo)節(jié)點(diǎn)分布對(duì)定位精度的影響，提出一種基于擬合曲線的未知節(jié)點(diǎn)選擇最佳信標(biāo)節(jié)點(diǎn)參與定位的方法。

2.1 跳距誤差修正方法

每個(gè)信標(biāo)節(jié)點(diǎn)先根據(jù)傳統(tǒng)DV-Hop算法的第二階段計(jì)算出平均每跳距離，將平均跳距廣播至網(wǎng)絡(luò)中，廣播數(shù)據(jù)分組信息為{ID，hopsizei}，ID為信標(biāo)節(jié)點(diǎn)序號(hào)，hopsizei為信標(biāo)節(jié)點(diǎn)i計(jì)算的平均跳距，每個(gè)節(jié)點(diǎn)接收所有信標(biāo)節(jié)點(diǎn)的平均跳距并將該跳距信息添加到自己的數(shù)據(jù)列表中，再將信息分組向鄰居節(jié)點(diǎn)廣播，忽略重復(fù)的ID信息分組，然后每個(gè)節(jié)點(diǎn)將記錄的所有平均跳距相加取平均值，得到全網(wǎng)的平均跳距aver為：

(3)

其中，n為信標(biāo)節(jié)點(diǎn)的總數(shù)。之后每個(gè)信標(biāo)節(jié)點(diǎn)再根據(jù)下式得到自身平均跳距誤差值ei：

(4)

經(jīng)過(guò)跳距誤差修正后最終信標(biāo)節(jié)點(diǎn)i的平均每跳距離hopi為：

hopi=aver+k×ei，-1≤k≤1

(5)

根據(jù)文獻(xiàn)[6]可知，變量參數(shù)k取0.7最佳。最后信標(biāo)節(jié)點(diǎn)將新的校正值hopi廣播到網(wǎng)絡(luò)中。

2.2 最佳信標(biāo)節(jié)點(diǎn)選擇算法

在傳統(tǒng)DV-Hop算法中，未知節(jié)點(diǎn)只要獲得與3個(gè)或3個(gè)以上信標(biāo)節(jié)點(diǎn)的距離時(shí)就可進(jìn)行定位計(jì)算[7]，但由于信標(biāo)節(jié)點(diǎn)相對(duì)于未知節(jié)點(diǎn)的位置分布會(huì)對(duì)定位精度造成較大的影響，并不是所有信標(biāo)節(jié)點(diǎn)都參與定位計(jì)算定位精度就越高，未知節(jié)點(diǎn)要有選擇地選取最佳的信標(biāo)節(jié)點(diǎn)參與定位計(jì)算，才能使定位結(jié)果更加準(zhǔn)確。信標(biāo)節(jié)點(diǎn)位置分布如圖1所示，黑色圓點(diǎn)表示信標(biāo)節(jié)點(diǎn)，空心圓點(diǎn)表示未知節(jié)點(diǎn)，實(shí)線表示跳段，虛線表示實(shí)際距離。未知節(jié)點(diǎn)A用信標(biāo)節(jié)點(diǎn)B、C進(jìn)行定位計(jì)算，當(dāng)用跳距乘以跳數(shù)表示AB與AC的距離時(shí)，顯然AB的估計(jì)距離要比AC的估計(jì)距離更接近實(shí)際距離，因?yàn)槲粗?jié)點(diǎn)A到信標(biāo)節(jié)點(diǎn)B的跳段路徑更接近一條直線?；谝陨戏治?，筆者提出一種選擇最佳信標(biāo)節(jié)點(diǎn)的方法。

圖1 信標(biāo)節(jié)點(diǎn)位置分布

(6)

圖2 信標(biāo)節(jié)點(diǎn)選擇

使用多個(gè)平均跳距計(jì)算距離。在新算法中結(jié)合跳距誤差修正算法，未知節(jié)點(diǎn)接收所有信標(biāo)節(jié)點(diǎn)的平均跳距，并將該信息記錄在列表中，然后未知節(jié)點(diǎn)使用被選擇出的信標(biāo)節(jié)點(diǎn)各自的平均跳距乘以跳數(shù)作為未知節(jié)點(diǎn)與被選擇信標(biāo)節(jié)點(diǎn)的距離。

精確計(jì)算未知節(jié)點(diǎn)坐標(biāo)。未知節(jié)點(diǎn)利用所選擇出來(lái)的信標(biāo)節(jié)點(diǎn)使用極大似然估計(jì)法再次精確計(jì)算自身坐標(biāo)。由于未知節(jié)點(diǎn)與所選擇的信標(biāo)節(jié)點(diǎn)的距離不會(huì)偏向于曲折的跳段過(guò)程，更接近直線，更能反映真實(shí)距離，所以再次計(jì)算出的未知節(jié)點(diǎn)坐標(biāo)會(huì)更加準(zhǔn)確。

3 改進(jìn)算法的仿真和分析

為了驗(yàn)證改進(jìn)DV-Hop算法在提高節(jié)點(diǎn)定位精度方面的有效性和可行性，使用Matlab進(jìn)行仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)的網(wǎng)絡(luò)區(qū)域模型參數(shù)為：在100m×100m的區(qū)域進(jìn)行實(shí)驗(yàn)，節(jié)點(diǎn)通過(guò)隨機(jī)方式布置，所有節(jié)點(diǎn)的通信半徑都相同，為了取得客觀準(zhǔn)確的實(shí)驗(yàn)數(shù)據(jù)，所有數(shù)據(jù)采用100次實(shí)驗(yàn)的平均值[10]。對(duì)傳統(tǒng)算法、已有的基于跳距誤差修正的算法和筆者提出的改進(jìn)算法的定位精度進(jìn)行比較，分析改進(jìn)算法的性能。

定位精度C[11]一般用定位誤差值與節(jié)點(diǎn)通信半徑的比值表示，即：

(7)

式中 (xest,yest)——算法計(jì)算的節(jié)點(diǎn)坐標(biāo)；

(xture,yture)——節(jié)點(diǎn)實(shí)際坐標(biāo)。

由式(7)可知，節(jié)點(diǎn)定位精度C值越小表示定位越準(zhǔn)確。

圖3描述了在相同網(wǎng)絡(luò)環(huán)境下，所有節(jié)點(diǎn)的通信半徑R=20m，節(jié)點(diǎn)總數(shù)分別為100和200時(shí)，傳統(tǒng)DV-Hop算法、基于跳距誤差修正的算法與筆者提出的改進(jìn)算法定位精度隨信標(biāo)節(jié)點(diǎn)比例的變化情況?？梢钥闯?，與傳統(tǒng)算法和基于跳距誤差修正的算法相比，當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)較少時(shí)，筆者改進(jìn)算法提高定位精度幅度不大，因?yàn)槲粗?jié)點(diǎn)可選擇的最佳信標(biāo)節(jié)點(diǎn)數(shù)較少。但隨著信標(biāo)節(jié)點(diǎn)比例的增大，由于筆者改進(jìn)算法充分考慮了信標(biāo)節(jié)點(diǎn)位置的分布情況并且加入了跳距誤差修正算法，使距離計(jì)算更準(zhǔn)確，所以更有效地提高了定位精度，穩(wěn)定性也越來(lái)越強(qiáng)。當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)(從100節(jié)點(diǎn)增加到200節(jié)點(diǎn))，定位精度也明顯提高，如圖3a中當(dāng)信標(biāo)節(jié)點(diǎn)比例為15%時(shí)，定位精度大約為44%；而圖3b中，信標(biāo)節(jié)點(diǎn)比例同樣為15%時(shí)，定位精度為33%。

a. 節(jié)點(diǎn)總數(shù)為100

b. 節(jié)點(diǎn)總數(shù)為200

圖4描述了在相同網(wǎng)絡(luò)環(huán)境下，信標(biāo)節(jié)點(diǎn)比例為15%、節(jié)點(diǎn)總數(shù)分別為100和200時(shí)，傳統(tǒng)DV-Hop算法、基于跳距誤差修正的算法與筆者提出的改進(jìn)算法定位精度隨節(jié)點(diǎn)通信半徑變化的情況。

a. 節(jié)點(diǎn)總數(shù)為100

b. 節(jié)點(diǎn)總數(shù)為200

可以看出，隨著節(jié)點(diǎn)總數(shù)的增加，3種算法的定位誤差都有所減小，在節(jié)點(diǎn)通信半徑從10變化到40的過(guò)程中，筆者提出的改進(jìn)算法的定位精度均比傳統(tǒng)算法和跳距修正的算法的定位精度高，這是由于改進(jìn)算法在基于跳距誤差修正的基礎(chǔ)上又充分考慮了信標(biāo)節(jié)點(diǎn)分布對(duì)定位精度的影響，選擇合適的信標(biāo)節(jié)點(diǎn)參與定位計(jì)算，并且使用每個(gè)被選擇信標(biāo)節(jié)點(diǎn)的每跳跳距進(jìn)行距離計(jì)算，使未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的估算距離更好地反映網(wǎng)絡(luò)實(shí)際節(jié)點(diǎn)間距，定位才更準(zhǔn)確。

4 結(jié)束語(yǔ)

筆者在分析現(xiàn)有DV-Hop算法原理和產(chǎn)生誤差原因的基礎(chǔ)上，提出了改進(jìn)算法，改進(jìn)的算法考慮了信標(biāo)節(jié)點(diǎn)位置的分布情況，取最接近直線分布的信標(biāo)節(jié)點(diǎn)作為計(jì)算用的參考節(jié)點(diǎn)，從本質(zhì)上更接近使用跳距定位算法的定位原理，可以提高定位精度。當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大、信標(biāo)節(jié)點(diǎn)數(shù)增多時(shí)，筆者提出的改進(jìn)算法的定位精度比傳統(tǒng)算法都有明顯的提高；當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)比例不變，網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí)，隨著節(jié)點(diǎn)通信距離的提高，筆者提出的改進(jìn)算法對(duì)定位精度也有較顯著的改善效果。

[1] Akyildiz I F,Su W L,Sankarasubramaniam Y,et al.A Survey on Sensor Networks[J].IEEE Communications Magazine，2002,40(8)：102～114.

[2] 任豐原,黃海寧,林闖.無(wú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2003,14(7):1282～1291.

[3] Xiao J,Chen H, Zhang S.Research of Range-Based Syner-getic Localization Algorithm in Wireless Sensor Networks[C].2008 Control and Decision Conference.Shandong:IEEE,2008:2040～2044.

[4] 王福豹,史龍,任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),2005,16(5):857～868.

[5] Mao G Q,Fidan B，Anderson B D O.Wireless Sensor Network Localization Techniques[J].Computer Networks,2007,51(10):2529～2553.

[6] 李輝,熊盛武,劉毅,等.無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)[J].傳感技術(shù)學(xué)報(bào),2011,24(12):1782～1786.

[7] 張佳,吳延海,石峰,等.基于DV-Hop的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)應(yīng)用,2010,30(2):323～326.

[8] 劉少?gòu)?qiáng),龐新苗,樊曉平,等.一種有效提高節(jié)點(diǎn)定位精度的改進(jìn)DV-Hop算法[J].傳感技術(shù)學(xué)報(bào),2010,23(8):1179～1183.

[9] Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems,2003,22(1-4):267～280.

[10] Basagni S,Carosi A,Melachrinoudis E,et al.Protocols and Model for Sink Mobility in Wireless Sensor Networks[J].ACM SIGMO-BILE Mobile Computing and Communications Review,2006,10(4):28～30.

[11] Poggi C,Mazzini G.Collinearity for Sensor Network Localization[C].Proceedings of 2003 IEEE 58th Vehicular Technology Conference.Piscataway,NJ,USA:IEEE,2004:3040～3044.