梁建國, 于建志, 張 浩, 傅 游

(1. 山東科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院, 山東 青島 266590;2. 青島港灣職業(yè)技術(shù)學(xué)院 信息與電氣工程學(xué)院, 山東 青島 266404)

目前,隨著“互聯(lián)網(wǎng)+”行動計劃的提出,互聯(lián)網(wǎng)產(chǎn)業(yè)發(fā)展勢頭更加迅猛,而“互聯(lián)網(wǎng)+”的發(fā)展,必將帶來“大數(shù)據(jù)+”“云計算+”以及“物聯(lián)網(wǎng)+”等的發(fā)展,因為它們是其發(fā)展的基石,也是其通往云端的天梯.其中的物聯(lián)網(wǎng)技術(shù)作為“互聯(lián)網(wǎng)+”的發(fā)展的基石,其發(fā)展也是日新月異,它的應(yīng)用已經(jīng)使我們的生產(chǎn)生活方式發(fā)生了巨大變化.無線傳感器網(wǎng)絡(luò)WSN(wireless sensor network)技術(shù)作為物聯(lián)網(wǎng)發(fā)展的重要組成部分從一出現(xiàn)就備受關(guān)注[1].它融合了目前先進(jìn)的傳感器技術(shù)、微電子技術(shù)以及無線通信技術(shù)等信息技術(shù),是一個交叉科學(xué).目前無線傳感器網(wǎng)絡(luò)技術(shù)已經(jīng)在智能醫(yī)療、智能農(nóng)業(yè)、智能交通、智能物流以及環(huán)境監(jiān)測等領(lǐng)域被廣泛使用,其關(guān)鍵技術(shù)主要有節(jié)點(diǎn)定位技術(shù)、自組織網(wǎng)絡(luò)路由技術(shù)、能耗技術(shù)、數(shù)據(jù)融合技術(shù)以及信息安全技術(shù)等,而作為其發(fā)展基礎(chǔ)的節(jié)點(diǎn)定位技術(shù)的研究一直是眾多研究者關(guān)注的熱點(diǎn),因為在無線傳感器網(wǎng)絡(luò)中,失去位置信息的節(jié)點(diǎn)將變得毫無意義[2-3].

目前,眾多研究者提出的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法根據(jù)是否需要進(jìn)行距離的測量可以分為兩類,一類是基于測距的節(jié)點(diǎn)定位算法,另一類是無需測距的節(jié)點(diǎn)定位算法.前者主要利用已有的測距技術(shù),包括RSSI(radio signal strength indicator)、AOA(angle of arrival)、TDOA(time difference of arrival)等,進(jìn)行點(diǎn)與點(diǎn)之間的距離或方向的測量,其定位精度高,但需要額外增加測距設(shè)備,成本較高[4];后者主要通過已知節(jié)點(diǎn)與未知節(jié)點(diǎn)之間進(jìn)行信息交換來進(jìn)行節(jié)點(diǎn)的距離測量,該類算法以質(zhì)心定位算法、凸規(guī)劃定位算法、DV-Hop定位算法等為其典型代表,雖然其定位精度不高,但是功耗低,對節(jié)點(diǎn)的硬件要求也不高,并且能滿足多數(shù)應(yīng)用中對節(jié)點(diǎn)定位的需求[5-14].

DV-Hop定位算法作為一種無需測距的算法,由于其計算速度快,一直備受關(guān)注,然而,在一些場景下,DV-Hop定位算法的定位精度并不高.為了提高定位精度,研究者提出了很多改進(jìn)方法.文獻(xiàn)[15]提出了基于測距技術(shù)RSSI估算節(jié)點(diǎn)間的距離來減低測距誤差,文獻(xiàn)[16]中利用跳數(shù)的倒數(shù)進(jìn)行加權(quán)同時對求解的最小二乘法進(jìn)行加權(quán)而進(jìn)行優(yōu)化,另一些研究者將粒子群優(yōu)化算法[17],蛙跳算法[18],蜂群算法[19],人工魚群算法[20], 細(xì)菌覓食優(yōu)化算[21],布谷鳥搜索算法[22-23]等智能算法引入DV-Hop定位算法對其改進(jìn),然而上述這些算法在提高精度的同時,有的需要增加硬件,有的計算復(fù)雜度較高,給本身計算能力就很有限的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)帶來較大壓力,同時也增加了能量的消耗.

針對DV-Hop定位算法存在的問題, 本文提出一種改進(jìn)的DV-Hop定位算法, 其主要思想是: 在不增加硬件的同時盡量保持算法復(fù)雜度的基礎(chǔ)上, 利用相同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中, 未知節(jié)點(diǎn)與距離自己較近的錨節(jié)點(diǎn)受到環(huán)境等各方面因素的影響相近的原則, 通過尋找距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)作為校正節(jié)點(diǎn), 將找出的校正節(jié)點(diǎn)作為未知節(jié)點(diǎn), 用DV-Hop定位算法估算其位置信息, 求出未知節(jié)點(diǎn)的校正誤差值, 最后利用校正誤差值對未知節(jié)點(diǎn)進(jìn)行校正, 減小未知節(jié)點(diǎn)的定位誤差.

1 DV-Hop定位算法

APS(ad hoc positioning system)是最早被提出的利用已知位置的錨節(jié)點(diǎn)找到未知節(jié)點(diǎn)位置的系列分布式定位算法, 主要包括DV-Hop, DV-Distance和Euclidean三種算法. 其中DV-Hop定位算法由于利用網(wǎng)絡(luò)的連通度和節(jié)點(diǎn)間的跳數(shù)值而不引入任何測量工具備受青睞[24]. DV-Hop定位算法根據(jù)每階段的實現(xiàn)任務(wù)不同可以分為計算最小跳數(shù)、 估算實際距離和定位未知節(jié)點(diǎn)坐標(biāo)3個階段, 下面詳細(xì)說明這3個階段的實現(xiàn)過程.

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

在網(wǎng)絡(luò)初始化結(jié)束以后,網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行信息交互,其中的錨節(jié)點(diǎn)會將包含自身位置信息的分組(包括初始值為0的跳數(shù)字段)在網(wǎng)絡(luò)中進(jìn)行廣播.網(wǎng)絡(luò)中的接收節(jié)點(diǎn)用表(xi,yi,hopi)對其接收的信息進(jìn)行標(biāo)識,其中(xi,yi)是錨節(jié)點(diǎn)i的坐標(biāo),hopi是錨節(jié)點(diǎn)i距離接收節(jié)點(diǎn)間的最小跳數(shù).如果第一次接收廣播信息,直接記錄并且跳數(shù)加1,之后繼續(xù)轉(zhuǎn)發(fā);如果已經(jīng)接收過來自該節(jié)點(diǎn)的廣播信息,則進(jìn)行比較,如果接收的跳數(shù)信息值比記錄的值大則拋棄,小則保留并且跳數(shù)加1,之后繼續(xù)轉(zhuǎn)發(fā).通過這種方式,使得每個節(jié)點(diǎn)記錄的跳數(shù)距離值總是距離錨節(jié)點(diǎn)的跳數(shù)最小.

1.2 估算實際距離階段

在第1階段結(jié)束以后,網(wǎng)絡(luò)中未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的跳數(shù)已經(jīng)獲得,而網(wǎng)絡(luò)中錨節(jié)點(diǎn)的位置信息是已知的.因此可以用式(1)估算錨節(jié)點(diǎn)的平均每跳距離,其中錨節(jié)點(diǎn)i,j的橫縱坐標(biāo)分別為(xi,yi), (xj,yj) ,錨節(jié)點(diǎn)i,j之間的最小跳數(shù)為hj,其中i,j不相等.

(1)

通過式(1)的計算,網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)的平均每跳距離被求出,之后每個錨節(jié)點(diǎn)將自己的所擁有的平均每跳距離在網(wǎng)絡(luò)中進(jìn)行廣播,未知節(jié)點(diǎn)接收所有廣播值,但僅記錄距離自己最近的錨節(jié)點(diǎn)的廣播值,同時將接收的廣播轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn),并將自己記錄的值作為自己與其他錨節(jié)點(diǎn)的平均每跳距離.

假如HopSizei為未知節(jié)點(diǎn)i,j記錄的平均每跳距離,hoppk為其與錨節(jié)點(diǎn)i之間的最小跳數(shù),可以用式(2)計算兩者之間的跳段距離

dpk=HopSizei×hoppk.

(2)

1.3 定位未知節(jié)點(diǎn)坐標(biāo)階段

通過第2階段的計算,未知節(jié)點(diǎn)與3個或3個以上的錨節(jié)點(diǎn)之間的距離被求出,這樣就可以利用基本的定位測量方法(例如三邊測量法、極大似然估計法或最小二乘法)進(jìn)行未知節(jié)點(diǎn)的定位.未知節(jié)點(diǎn)p的坐標(biāo)可以通過式(3)計算,

(3)

將式(3)視為線性方程組AX=b,解之可得X=(ATA)-1ATb,其中A,X,b如下.

2 利用校正節(jié)點(diǎn)改進(jìn)DV-Hop定位算法

在DV-Hop定位算法估算實際距離階段,雖然對于每個錨節(jié)點(diǎn)來說其計算的平均每跳距離都是準(zhǔn)確的,但是實際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,存在這樣兩個問題:一個是節(jié)點(diǎn)之間的路徑通常為折線而非直線;另一個是網(wǎng)絡(luò)中的節(jié)點(diǎn)分布是隨機(jī)的,而非均勻分布,同時跳段之間的距離也是非均勻的.這兩個問題的存在使得估算出的距離與實際距離之間存在著偏差,并且節(jié)點(diǎn)間距離越遠(yuǎn),這種偏差也會變得越大,因此必須找出一種合理的方法對其進(jìn)行修正.

本文提出的改進(jìn)算法是建立在原DV-Hop定位算法的基礎(chǔ)上,不改變其前2個階段的計算過程,著重關(guān)注第3階段的改進(jìn).通過上面分析可知,未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離估算誤差是傳統(tǒng)DV-Hop算法的定位誤差主要來源所在,本算法改進(jìn)的思路是盡量減小第二部分中產(chǎn)生的誤差造成的誤差偏大的影響.

(4)

式中,di表示利用傳統(tǒng)DV-Hop定位算法計算出的未知節(jié)點(diǎn)p與錨節(jié)點(diǎn)i之間距離,ei表示計算出di與未知節(jié)點(diǎn)p與錨節(jié)點(diǎn)i真實距離之間的誤差.根據(jù)式(4),則式(3)可以用式(5)表示:

(5)

由此可見,DV-Hop定位算法如果要取得較高的定位率,可以通過減小距離誤差值ei來獲得.考慮到在相同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,未知節(jié)點(diǎn)與距離自己較近的錨節(jié)點(diǎn)受到環(huán)境等各方面因素的影響相近,因此,本文提出的算法用與未知節(jié)點(diǎn)距離較近的錨節(jié)點(diǎn)來校正其距離誤差值.

首先,尋找網(wǎng)絡(luò)中未知節(jié)點(diǎn)的最近錨節(jié)點(diǎn),尋找依據(jù)是使用傳統(tǒng)DV-Hop定位算法計算出的錨節(jié)點(diǎn)的平均每跳距離與未知節(jié)點(diǎn)距其最小跳數(shù)之積求出的距離,距離最小者的錨節(jié)點(diǎn)將作為該未知節(jié)點(diǎn)的校正節(jié)點(diǎn),如圖1所示,如果距離未知節(jié)點(diǎn)p最近的錨節(jié)點(diǎn)為k,則將其作為未知節(jié)點(diǎn)p的校正節(jié)點(diǎn).

圖1校正節(jié)點(diǎn)選取示意圖
Fig.1 Correcting node selection diagram

(6)

由于錨節(jié)點(diǎn)k與未知節(jié)點(diǎn)p距離最近,在使用DV-Hop定位算法估算其預(yù)測值時,受到的測距誤差因素相同,因此可以近似認(rèn)為未知節(jié)點(diǎn)與錨節(jié)點(diǎn)具有相同的誤差值,因此將錨節(jié)點(diǎn)k作為未知節(jié)點(diǎn)p的校正節(jié)點(diǎn),并將其誤差值作為未知節(jié)點(diǎn)p的校正誤差值,則未知節(jié)點(diǎn)p與錨節(jié)點(diǎn)i之間的距離可以用式(7)表示,

(7)

在實際應(yīng)用的過程中,如果選取的校正節(jié)點(diǎn)與未知節(jié)點(diǎn)在1跳通信半徑范圍之內(nèi),那么可以使用,如果在1跳通信范圍內(nèi)無校正節(jié)點(diǎn),就需要尋找次校正節(jié)點(diǎn),可以通過2種方式尋找次校正節(jié)點(diǎn),一種是尋找1跳通信范圍之外的錨節(jié)點(diǎn),另一種是將已經(jīng)定位的節(jié)點(diǎn)升級為錨節(jié)點(diǎn)進(jìn)行校正,如果未知節(jié)點(diǎn)周圍錨節(jié)點(diǎn)分布較少,可以選擇后者,如果未知節(jié)點(diǎn)1跳通信范圍內(nèi)無錨節(jié)點(diǎn),2跳范圍內(nèi)有錨節(jié)點(diǎn),則可以選擇前者,具體選擇哪種,需要根據(jù)實際情況來選擇.

3 改進(jìn)后DV-Hop定位算法的實現(xiàn)

假設(shè)M個錨節(jié)點(diǎn)的坐標(biāo)為(x1,y1),(x2,y2),…,(xM,yM),錨節(jié)點(diǎn)的標(biāo)識為id,N個未知節(jié)點(diǎn)隨機(jī)分布在網(wǎng)絡(luò)中,節(jié)點(diǎn)通信半徑為R,限制廣播包最大跳數(shù)為hmax.

1) 初始化網(wǎng)絡(luò),設(shè)定網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)為M,未知節(jié)點(diǎn)數(shù)為N,節(jié)點(diǎn)通信半徑為R,限制廣播包最大跳數(shù)為hmax.

2) 錨節(jié)點(diǎn)向網(wǎng)絡(luò)中其他節(jié)點(diǎn)廣播包含自身位置、跳數(shù)以及廣播包最大跳數(shù)的數(shù)據(jù)報,數(shù)據(jù)包格式為{id,xi,yi,hi,hmax},hi初始值為0.

3) 網(wǎng)絡(luò)中的節(jié)點(diǎn)接收廣播包,如果已經(jīng)接收,則與已經(jīng)接受的信息進(jìn)行比較并保存包含最小跳數(shù)的信息;如果沒有接收,則直接保存信息.

4) 每個錨節(jié)點(diǎn)利用式(1)計算平均每跳距離,并將包含距離信息的數(shù)據(jù)包廣播到網(wǎng)絡(luò)中.

5) 網(wǎng)絡(luò)中的所有未知節(jié)點(diǎn)接收步驟4中錨節(jié)點(diǎn)發(fā)送廣播信息,如果第一次接收,直接保存,否則通過與自身已經(jīng)保存的廣播信息進(jìn)行比較,將與自己最近的錨節(jié)點(diǎn)信息進(jìn)行記錄.在廣播結(jié)束以后,使用式(2)計算所有未知節(jié)點(diǎn)到每個錨節(jié)點(diǎn)的距離.

6) 未知節(jié)點(diǎn)通過使用標(biāo)準(zhǔn)的最小均方差估計法計算未知節(jié)點(diǎn)的坐標(biāo)信息.

7) 未知節(jié)點(diǎn)尋找最近的錨節(jié)點(diǎn)將其作為校正節(jié)點(diǎn),同時將其作為未知節(jié)點(diǎn),使用未知節(jié)點(diǎn)的坐標(biāo)計算方法估算錨節(jié)點(diǎn)即校正節(jié)點(diǎn)的坐標(biāo).

8) 根據(jù)式(6)計算錨節(jié)點(diǎn)預(yù)測值與精確值之間的誤差,并將包含誤差值的數(shù)據(jù)包廣播到網(wǎng)絡(luò)中.

9) 未知節(jié)點(diǎn)在接收到校正節(jié)點(diǎn)的校正誤差值以后,利用式(7)重新計算未知節(jié)點(diǎn)的坐標(biāo).

4 仿真實驗及分析

本部分主要介紹算法的仿真以及仿真定位誤差結(jié)果的分析,為了比較本文提出的算法與改進(jìn)前算法的定位性能,同時與文獻(xiàn)[25]中提出的算法(記作IDV-Hop),文獻(xiàn)[26]中提出的算法(記作PDV-Hop)進(jìn)行仿真實驗對比,利用MATLAB 7.0軟件對其進(jìn)行仿真,每次仿真4種算法都被測試100次,然后取其平均值作為測試結(jié)果.網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的參數(shù)模型如下:所有節(jié)點(diǎn)分布在100 m×100 m的正方形區(qū)域中,未知節(jié)點(diǎn)與錨節(jié)點(diǎn)被隨機(jī)分布在此區(qū)域中,并且假定所有節(jié)點(diǎn)通信半徑相同,分別研究錨節(jié)點(diǎn)數(shù)、通信半徑以及網(wǎng)絡(luò)密度的變化對改進(jìn)前后算法的性能影響.如圖2所示,圓圈代表未知節(jié)點(diǎn), 星型代表錨節(jié)點(diǎn).

○—未知節(jié)點(diǎn); ?—錨節(jié)點(diǎn).
圖2 WSN拓?fù)浣Y(jié)構(gòu)
Fig.2 WSN topology diagram

在仿真過程中,定位誤差由平均定位誤差函數(shù)表示,

(8)

4.1 不同節(jié)點(diǎn)總數(shù)對算法定位性能的影響

仿真實驗過程中,節(jié)點(diǎn)總數(shù)從50變化到150,變化步長為10,錨節(jié)點(diǎn)數(shù)為節(jié)點(diǎn)總數(shù)的20%,節(jié)點(diǎn)通信半徑為30 m.

從圖3折線變化趨勢可以看出,在節(jié)點(diǎn)通信半徑保持不變的情況下,節(jié)點(diǎn)總數(shù)的增加會使算法定位誤差呈現(xiàn)減小趨勢.出現(xiàn)此種變化趨勢的原因是由于隨著網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)的增加,網(wǎng)絡(luò)中每個節(jié)點(diǎn)的鄰居節(jié)點(diǎn)也在增加,使得整個網(wǎng)絡(luò)的連通性加強(qiáng),從而使求得的錨節(jié)點(diǎn)平均每跳距離誤差減小,同時也使得求出的未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離更加接近真實距離,因此4種定位算法的定位誤差也在減小.

圖3不同節(jié)點(diǎn)總數(shù)下的平均定位誤差對比

Fig.3 Comparison of average locationerrors under different numbers of nodes

從圖3還可以看出,改進(jìn)后的算法比傳統(tǒng)DV-Hop,IDV-Hop和PDV-Hop算法定位精度分別提高大約13.5%,8.9%,5.6%,因此可知改進(jìn)的算法的定位率在相同情況下高于其他3種定位算法.

4.2 不同錨節(jié)點(diǎn)數(shù)對算法定位性能的影響

在本次仿真實驗過程中,錨節(jié)點(diǎn)數(shù)占節(jié)點(diǎn)總數(shù)的比例從5%變化到40%,變化步長為5%,節(jié)點(diǎn)總數(shù)保持100,節(jié)點(diǎn)通信半徑為30 m.

從圖4折線變化趨勢可以看出,在網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)逐漸增加的情況下,4種定位算法的定位誤差都在減小,并且在錨節(jié)點(diǎn)數(shù)增加到一定程度后,下降趨勢變緩.究其原因是由于在固定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,在錨節(jié)點(diǎn)數(shù)量比例增加的情況下,網(wǎng)絡(luò)連通度增大,錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的跳數(shù)在減少,從而使錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的估算距離更加接近真實距離,因此算法的定位誤差在減小.

圖4不同錨節(jié)點(diǎn)比例下平均定位誤差比較

Fig.4 Comparison of average position error with different numbers of anchor nodes

從圖4還可以看出,改進(jìn)后的算法比傳統(tǒng)DV-Hop,IDV-Hop和PDV-Hop算法定位精度分別提高大約14%,9.3%,5.5%,這說明改進(jìn)的算法在相同情況下定位率優(yōu)于其他3種定位算法.

4.3 不同節(jié)點(diǎn)通信半徑對算法定位性能的影響

在仿真過程中,網(wǎng)絡(luò)中節(jié)點(diǎn)通信半徑取值為20 m,25 m,……,50 m,節(jié)點(diǎn)總數(shù)保持100,錨節(jié)點(diǎn)數(shù)占節(jié)點(diǎn)總數(shù)的20%.

圖5所示的折線變化趨勢表明,在節(jié)點(diǎn)通信半徑逐漸增加的情況下,4種定位算法的定位誤差都在逐漸減小,并且在節(jié)點(diǎn)通信半徑增加到一定程度后,減少趨勢逐漸變緩,這是由于在節(jié)點(diǎn)總數(shù)一定的情況下,隨著節(jié)點(diǎn)通信半徑的增加,網(wǎng)絡(luò)的連通度在增加,這樣網(wǎng)絡(luò)中的未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)也在增加,因此算法的定位誤差在減小.

圖5不同節(jié)點(diǎn)通信半徑下平均定位誤差比較

Fig.5 Comparison of average position error with different communication radius

從圖5還可以看出,改進(jìn)后的算法比傳統(tǒng)DV-Hop,IDV-Hop和PDV-Hop算法定位精度分別提高大約12.8%,9.2%,5.5%,這說明改進(jìn)的算法在相同情況下定位率優(yōu)于其他3種算法.

5 結(jié) 論

無需測距的定位算法DV-Hop由于其易于實現(xiàn)以及對硬件依賴性小而在無線傳感器網(wǎng)絡(luò)中廣泛使用,但是由于定位誤差大不適合在定位精度要求較高的場合,為此本文在研究DV-Hop定位算法基礎(chǔ)上提出利用距離最近的錨節(jié)點(diǎn)作為校正節(jié)點(diǎn)的改進(jìn)算法,最后并對提出的算法進(jìn)行仿真驗證,通過驗證表明,提出的算法在減小定位誤差上有明顯的效果,說明其具有良好的性能.