基于節(jié)點密度及路徑優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法研究*

吳 凡,彭 力

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122)

?

基于節(jié)點密度及路徑優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法研究*

吳 凡,彭 力*

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122)

無線傳感器網(wǎng)絡(luò)中非測距定位算法一般采用基于連通性或跳數(shù)信息方式進行定位,一跳范圍內(nèi)節(jié)點間的估算距離值均相同,不能體現(xiàn)實際的節(jié)點間距離大小;此外,當(dāng)多跳的路徑有較大的轉(zhuǎn)折時,此時用路徑的估距值代替實際距離也會出現(xiàn)嚴(yán)重的偏差?；诖?提出了新的節(jié)點間距離模型RPD,將節(jié)點間估距與周圍節(jié)點的密度信息相關(guān)聯(lián),同時進行路徑優(yōu)化以使路徑的估距更接近實際的距離。最后將新的距離模型運用到DV-Hop節(jié)點間估距階段實現(xiàn)定位。通過仿真實驗表明,改進的定位算法與傳統(tǒng)的DV-Hop相比,在不同的錨節(jié)點比率和不同的通信半徑的情況下,定位的誤差率和穩(wěn)定性都要優(yōu)于傳統(tǒng)算法。

無線傳感網(wǎng);定位;RPD;DV-Hop;路徑優(yōu)化

節(jié)點定位是無線傳感器網(wǎng)絡(luò)WSN(Wire Sensor Network)的關(guān)鍵技術(shù),定位的精度對其所監(jiān)測的區(qū)域有著至關(guān)重要的影響[1]。在大多數(shù)應(yīng)用中,沒有位置信息的傳感器數(shù)據(jù)是沒有實際意義的[2]。傳統(tǒng)的獲取節(jié)點位置信息的方法主要采用GPS定位來實現(xiàn)[3],但是會消耗大量能量并增加傳感器硬件的開銷。因此必須采用簡單有效的定位算法滿足WSN中的應(yīng)用需求。

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展,已經(jīng)存在許多算法可以解決無線傳感器網(wǎng)絡(luò)節(jié)點的定位問題,這些算法大致可以分為以下幾類:基于測距(Range-Based)的定位算法和距離無關(guān)(Range-Free)的定位算法[4]?；跍y距的定位算法需要測量節(jié)點之間的絕對距離或角度,再根據(jù)測得的數(shù)據(jù)采用三邊測量法(trilatcration)、三角測量法(triangulation)或最大似然估計法(multilatcration)計算出節(jié)點的位置。Range-Based定位常用的測距技術(shù)有RSSI,TOA,TDOA和AOA。而后者則無需測量節(jié)點間的絕對位置或角度,僅僅根據(jù)估計距離或是網(wǎng)絡(luò)連通性求出節(jié)點的位置。Range-Free定位常用的定位算法主要有質(zhì)心算法[5]、DV-Hop算法[6]、APIT算法[7]、MDS-Map[8]等。

近年來,許多國內(nèi)外學(xué)者提出了針對DV-Hop的改進算法。文獻[4]和文獻[9]提出了根據(jù)節(jié)點接收到的RSSI對第1跳進行分級,細(xì)化跳數(shù)的方法。文獻[10]提出了利用跳數(shù)的倒數(shù)作為權(quán)值的方法并對最小二乘法進行加權(quán)處理。文獻[11]利用入侵雜草優(yōu)化的算法,將定位問題轉(zhuǎn)化為全局最優(yōu)化問題。文獻[12]在多跳路徑中引入最優(yōu)輔助估距錨點提高定位的精度。

然而以上的方法均只是利用非測距算法中連通性或跳數(shù)信息來定位,而沒有充分利用節(jié)點的鄰居節(jié)點密度或區(qū)域內(nèi)節(jié)點總數(shù)這些在定位初期就能獲得的有用信息?；诖吮疚牡?節(jié)介紹Wu,G[13]等人提出的算法,第2節(jié)提出本文的改進算法,第3節(jié)是系統(tǒng)的仿真與結(jié)果分析。

1 問題描述

Ziguo,Z[14]提出了一種基于RSD的定位算法。該算法將某節(jié)點的一跳范圍內(nèi)的鄰居節(jié)點按RSSI值大小降序排列,以此獲得節(jié)點的特征值,再利用特征值計算RSD距離來代替跳數(shù),但是此算法雖然沒有用RSSI來計算距離,但是RSSI值本身受外界影響較大所以定位結(jié)果會不穩(wěn)定。因此Wu,G等人對此進行了改進。

如圖1,Wu,G等人定義了鄰居節(jié)點距離模型RND,從圖中可以看出如果相鄰的兩個節(jié)點距離很近,那么它們的共同的鄰居節(jié)點數(shù)量就越多,相反距離越遠(yuǎn),相同節(jié)點數(shù)量越少,基于這個現(xiàn)象Wu,G提出了式(1)來表示相鄰節(jié)點間的距離,從公式中可以看出RND(i,j)的取值范圍為[0,1]。

圖1 RND距離模型

(1)

其中Mi={j|j≠i且dij≤r}表示節(jié)點i的所有鄰居節(jié)點,dij表示節(jié)點i和j之間的歐式距離,r表示通訊半徑,mij表示節(jié)點i和節(jié)點j的相同鄰居節(jié)點數(shù)量。

根據(jù)RND距離模型,則可以對網(wǎng)絡(luò)中的未知節(jié)點進行定位,其定位過程總結(jié)如下:

第1步,根據(jù)已獲得的各節(jié)點之間的RND距離信息,利用Floyd-Warshall來計算節(jié)點s1和節(jié)點sn之間路徑的距離的最小值,如式(2)。其中Path(s1,sn)表示節(jié)點s1和節(jié)點sn的通路。

(2)

然后求出全網(wǎng)平均跳距,如式(3),其中A表示為網(wǎng)絡(luò)中所有的錨節(jié)點。

(3)

第2步,根據(jù)式(3)估算出任意未知節(jié)點到已知錨節(jié)點的距離,如式(4)。

(4)

第3步,當(dāng)未知節(jié)點獲得足夠多的估計距離后,可以用三邊測量法或者是極大似然估計法求出節(jié)點坐標(biāo)。

傳統(tǒng)的基于跳數(shù)的測量方法是把某節(jié)點通信半徑r范圍內(nèi)的鄰居節(jié)點的跳距都作為一跳距離來表示,即跳距值均為1,如圖1所示,無論節(jié)點間實際距離為1 m或是5 m,經(jīng)過跳距信息計算后的估計距離值均相同,這顯然存在很大的誤差。運用此方法后雖然可以對一跳范圍內(nèi)的節(jié)點距離值進行細(xì)化,提高精度。但是此算法仍然存在不足:

第1點,利用式(1)的方法僅能使用在一跳范圍內(nèi)的節(jié)點,當(dāng)計算整個路徑時就需要像式(2)中一樣,需要逐個計算路徑上相鄰的節(jié)點RND的累加值,路徑上相間隔的節(jié)點之間信息互相獨立,沒有充分利用節(jié)點之間相同鄰居節(jié)點的信息。

在網(wǎng)絡(luò)中,任意兩個節(jié)點的距離dij的取值范圍為{dij|0≤dij≤rhopij},其中hopij表示節(jié)點i和j之間的跳數(shù)值。從取值范圍中可以看出當(dāng)兩個節(jié)點的跳數(shù)為2時,這兩個節(jié)點的共同鄰居節(jié)點最少有1個,因此應(yīng)將相鄰節(jié)點的RND距離估算擴展到相間隔的節(jié)點距離估算。

第2點,仍然不能解決當(dāng)路徑出現(xiàn)較大轉(zhuǎn)折時所帶來的估計誤差。如圖2所示。

圖2 通路Path(i,k)

當(dāng)計算節(jié)點i和節(jié)點k之間的RND距離信息時,則RNDmin(Path(i,k))=RND(i,j)+RND(j,k),此時會出現(xiàn)較大計算誤差。

2 基于RPD改進的定位算法

2.1 RPD距離模型

為了更好的利用節(jié)點的密度信息,本節(jié)提出新的距離模型RPD(Regulated Path Distance)。如圖3所示。

圖3 RPD距離模型

圖中畫出一條通路Path(si,sk)。以節(jié)點i和節(jié)點k的通訊半徑r為半徑分別畫兩個圓,這兩個圓一定會存在公共區(qū)域,且區(qū)域內(nèi)一定會包含節(jié)點j,兩圓公共面積為

(5)

對式(5)求導(dǎo)得(6),所以S與dik成反比。

(6)

此外,節(jié)點的位置是隨機部署的,所以兩圓公共面積中的相同鄰居節(jié)點數(shù)為隨機變量,所以面積S越大,落入S中的節(jié)點數(shù)目就越多,dik越小,即dik反比于相同鄰居節(jié)點數(shù)。

基于這個現(xiàn)象,本節(jié)提出的距離模型RPD,當(dāng)hopik=2時,如式(7)。

(7)

其中Mi={j|j≠i且dij≤r}表示節(jié)點i的所有鄰居節(jié)點,dij表示節(jié)點i和j之間的歐式距離,r表示通訊半徑,mij表示節(jié)點i和節(jié)點j的相同鄰居節(jié)點數(shù)量。

由式(7)可以看出,當(dāng)節(jié)點i和節(jié)點k之間的距離dik=2r時,即節(jié)點i和節(jié)點k的相同鄰居節(jié)點只有節(jié)點j時,mik=1,此時達(dá)到最大值RPD(i,k)=1,當(dāng)dik=0時,即Mi=Mk=mik,此時達(dá)到最小值RPD(i,k)=1/Mi,當(dāng)節(jié)點密度趨于無窮時有RPD(i,k)=0。

此時還可以計算出

(8)

RPD(sj,sk)=RPD(si,sk)-RPD(si,sj)

(9)

在整個網(wǎng)絡(luò)中會包含很多條通路,每條通路的跳數(shù)值會出現(xiàn)大于3的情況,如圖4所示。圖中實線部分為實際的傳輸通路,虛線是為了優(yōu)化添加的輔助線。假設(shè)圖中的一條通路Path(s1,sn)。

圖4 通路Path(s1,sn)

選取通路中任意3個相連的節(jié)點所組成的小的通路,根據(jù)選取的節(jié)點,會出現(xiàn)3種情況:

第1種情況,如圖4(a),選取的是通路的起點s1及它后面的2個節(jié)點s2s3組成一個小的通路。此時可以計算

(10)

第2種情況,如圖4(b),選取的是第2個節(jié)點s2和sn-1之間的任意3個相連的節(jié)點。在這種情況中,每兩個相鄰的節(jié)點都會被兩個小的通路所包含,例如小通路Path(si-1,si+1)和Path(si,si+2)都包含si和si+1,如果按照式(8),(9)計算,會計算出兩個RPD(si,si+1)值,所以本文采取求取平均值的辦法。

(11)

(12)

在得到Path(s1,sn)中的每一個相鄰節(jié)點RPD(si,si+1)值后,可計算出整條通路的RPD值。

(13)

但是,在一個完整的網(wǎng)絡(luò)中相鄰的跳距為1的兩個節(jié)點si和si+1會被很多總跳數(shù)大于3的通路所包含,此時需要將每次在計算通路時得到的RPD(si,si+1)進行累加求平均值的操作。

那么本節(jié)提出的距離模型應(yīng)概括為式(14)。其中l(wèi)為包含節(jié)點si和si+1的總的通道數(shù)。

(14)

2.2 RPD定位算法

將本文提出的RPD算法與傳統(tǒng)DV-Hop算法相結(jié)合,整個定位過程可以總結(jié)為以下3個過程:

第1階段,根據(jù)距離矢量交換協(xié)議,使在網(wǎng)絡(luò)中的每一個節(jié)點都可以獲得到每個信標(biāo)節(jié)點的最小路徑,遍歷所有路徑,對每一條路徑采用RPD距離模型,使每對節(jié)點都獲得RPD距離值。

第2階段,通過上一步,每個信標(biāo)節(jié)點會獲得到其他信標(biāo)節(jié)點的RPD值,類似于傳統(tǒng)DV-Hop算法,求取全網(wǎng)平均每跳距離。

第3階段,未知節(jié)點在獲得3個或3個以上到其他信標(biāo)節(jié)點的距離后,采用三邊定位或最小二乘計算自身坐標(biāo)。

3 算法的仿真與分析

為了驗證算法的性能,本文對傳統(tǒng)DV-Hop、文獻[13]及RPD算法在MatLab平臺上進行了仿真對比分析。

①設(shè)傳感器節(jié)點隨機分布在100 m×100 m的區(qū)域內(nèi),未知節(jié)點數(shù)為160,信標(biāo)節(jié)點個數(shù)為40,通信半徑r=20 m的情況下進行仿真,觀測每一次實驗的誤差率,共進行100次測試,檢查定位效果。

如圖5為經(jīng)過傳統(tǒng)DV-Hop算法計算得到的信標(biāo)節(jié)點間生成的路徑,如圖6為經(jīng)過本文算法計算得到的信標(biāo)節(jié)點間生成的路徑,圓形表示未知節(jié)點,星形表示信標(biāo)節(jié)點,信標(biāo)節(jié)點之間的路徑連線用虛線表示。圖中的一部分路徑由于使用頻率大,導(dǎo)致看起來已經(jīng)近似直線。因此比較兩圖可得出,經(jīng)過RPD算法優(yōu)化后的路徑可以避免過多的使用位于分布區(qū)域較邊緣的節(jié)點,如圖6的左上位置已經(jīng)顯示為虛線,說明選擇此部分的路徑再變少,在圖的右側(cè)和下邊緣,有一些路徑已經(jīng)不存在了;并且圖6的中間區(qū)域的線路變密集,也說明在RPD算法在路徑選擇方面是盡量選擇位于分布圖中心區(qū)域的節(jié)點和路徑,不再選擇邊緣節(jié)點以使通過算法計算出的估計距離盡量貼近實際距離。

圖5 傳統(tǒng)DV-Hop信標(biāo)節(jié)點間路徑

圖6 基于RPD算法信標(biāo)節(jié)點間路徑

如圖7,比較三種定位算法在100次實驗中的定位結(jié)果可知,傳統(tǒng)DV-Hop算法的誤差率最高,大部分集中在30%～40%之間;文獻[13]中提出的RND算法的誤差率比傳統(tǒng)DV-Hop低,但是誤差率曲線波動很大,從圖中就可以明顯看出有2次實驗的結(jié)果超過了50%,甚至達(dá)到60%,這說明RND算法的穩(wěn)定性不夠;本文提出的RPD算法的誤差率位于最下面,誤差率最低可達(dá)17%,與傳統(tǒng)DV-Hop算法相比,誤差率平均降幅達(dá)到20%,并且誤差率曲線波動穩(wěn)定,不存在大的波動。

圖7 每次實驗對應(yīng)的誤差率

②設(shè)傳感器節(jié)點隨機分布在100 m×100 m的區(qū)域內(nèi)通信半徑為20 m不變,信標(biāo)節(jié)點占節(jié)點總數(shù)的比率從0.2起,每次實驗增加0.025的比率,直至增加至0.5.根據(jù)此實驗條件觀測當(dāng)信標(biāo)節(jié)點數(shù)目增大的情況下誤差率的變化情況。

從圖8中可以看出,當(dāng)信標(biāo)節(jié)點比例較大時,本文提出的RPD算法是所有算法中誤差率最低的,且波動較小;文獻[13]提出的算法雖然要優(yōu)于傳統(tǒng)DV-Hop算法,但是在本次實驗中當(dāng)網(wǎng)絡(luò)中部署了95個信標(biāo)節(jié)點時,文獻[13]的定位誤差率出現(xiàn)了高于傳統(tǒng)DV-Hop的情況。

圖8 錨節(jié)點增加對應(yīng)的誤差率

③設(shè)傳感器節(jié)點隨機分布在100 m×100 m的區(qū)域內(nèi)信標(biāo)節(jié)點在網(wǎng)絡(luò)中的比率保持0.2不變,逐漸增加通信半徑,通信從20 m開始,每次實驗增加2 m,直至增加至40。根據(jù)此實驗條件觀測當(dāng)通信半徑增大的情況下誤差率的變化情況。

如圖9所示,本文的算法和文獻[13]的算法誤差率在通信半徑增大的情況下逐漸減少,但是本文的算法要優(yōu)于文獻[13]的算法,而傳統(tǒng)DV-Hop的誤差率隨著通信半徑的增大沒有明顯的下降趨勢。

圖9 通信半徑增加對應(yīng)的誤差率

相比于信標(biāo)節(jié)點比率增大或者是通信半徑增大的情況,我們主要關(guān)心的是使用較少的信標(biāo)節(jié)點獲得更好的定位精度。減少信標(biāo)節(jié)點意味著減少網(wǎng)絡(luò)設(shè)備數(shù)量的從而減少開銷。從結(jié)果來看在信標(biāo)節(jié)點比例較少的情況下,本文提出的算法的定位誤差率遠(yuǎn)小于傳統(tǒng)DV-Hop的誤差率。

4 結(jié)束語

本文基于文獻[13]提出了新的節(jié)點間距離模型RPD,并將RPD距離模型應(yīng)用到傳統(tǒng)DV-Hop算法中,最后通過仿真來驗證結(jié)果。通過比較本文算法、文獻[13]算法和傳統(tǒng)DV-Hop算法的仿真結(jié)果,可以很明確的得出本文提出的RPD定位算法在定位精度上有明顯的提升,說明了本文的算法具有良好的性能。

[1] 李牧東,熊偉,梁青,等. 基于人工蜂群改進算法的無線傳感器網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報,2013,26(2):241-245.

[2]Brito L A,Liu Y,Garcia Y. An Improved Error Localization on DV-Hop Scheme for Wireless Sensors Networks[C]//Advanced Computer Theory and Engineering(ICACTE),2010 3rd International Conference on. IEEE,2010,2:V2-80-V2-84.

[3]程秀芝,朱達(dá)榮,張申,等. 基于RSSI差分校正的最小二乘——擬牛頓定位算法[J]. 傳感技術(shù)學(xué)報,2014,27(1):123-127.

[4]Fang W,Yang G. Improvement Based on DV-Hop Localization Algorithm of Wireless Sensor Network[C]//Mechatronic Science,Electric Engineering and Computer(MEC),2011 International Conference on. IEEE,2011:2421-2424.

[5]Bulusu N,Heidemann J,Estrin D. GPS-Less Low-Cost Outdoor Localization for Very Small Devices[J]. Personal Communications,IEEE,2000,7(5):28-34.

[6]Levenshtein V I. New Lower Bounds on Aperiodic Crosscorrelation of Binary Codes[J]. Information Theory,IEEE Transactions on,1999,45(1):284-288.

[7]He T,Huang C,Blum B M,et al. Range-Free Localization Schemes for Large Scale Sensor Networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. ACM,2003:81-95.

[8]Shang Y,Ruml W,Zhang Y,et al. Localization from Mere Connectivity[C]//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM,2003:201-212.

[9]溫江濤,范學(xué)敏,吳希軍,等. 基于RSSI跳數(shù)修正的DV-Hop改進算法[J]. 傳感技術(shù)學(xué)報,2014,27(1):113-117.

[10]涂巧玲,宋佳,胡濤. 一種加權(quán)的DV-Hop定位改進算法[J]. 通信技術(shù),2013,46(9):58-60.

[11]張浩,呂真,連衛(wèi)民. 采用入侵雜草優(yōu)化算法的WSN定位精度提高方法[J]. 電視技術(shù),2014,38(3):146-149,162.

[12]黃智勇,張欣. 基于估距方式分類的無線傳感器網(wǎng)絡(luò)定位算法[J]. 華南理工大學(xué)學(xué)報(自然科學(xué)版),2014,42(1):77-83.

[13]Wu G,Wang S,Wang B,et al. A Novel Range-Free Localization Based on Regulated Neighborhood Distance for Wireless Ad Hoc and Sensor Networks[J]. Computer Networks,2012,56(16):3581-3593.

[14]Zhong Z,He T. RSD:A Metric for Achieving Range-Free Localization beyond Connectivity[J]. Parallel and Distributed Systems,IEEE Transactions on,2011,22(11):1943-1951

吳凡(1989-),男,江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院碩士研究生,主要從事無線傳感器網(wǎng)絡(luò)定位的研究,wufan0423@sohu.com;

彭力(1967-),男,博士,江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院教授,博士生導(dǎo)師,主要從事視覺傳感器網(wǎng)絡(luò)、人工智能、計算機仿真的研究,pengli@jiangnan.edu.cn。

LocalizationAlgorithmBasedonNodeDensityandPathOptimizationforWirelessSensorNetworks*

WUFan,PENGLi*

(College of Internet of Things,Jiangnan University,Wuxi 214122,China)

Range-Free localization algorithm for wireless sensor network commonly used connectivity information or hop-count to estimate the distance which does not reflect the actual value between nodes within the range of one hop. In addition,when the path with multi-hop has a larger turning,there will be a serious mistake to instead of the actual distance with the estimated value. In order to address this problem,we propose a new distance model called regulated path distance(RPD)by relating the density of the surrounding nodes to the estimated distance,at the same time optimizing the path to make the path more realistic to the real. Finally,the new model is applied to the DV-Hop algorithm to positioning. Simulation results show that the improved positioning algorithm compared with conventional DV-Hop,under the scenarios of different rates and different anchor node communication radius,the positioning error rate and stability are both better than traditional methods.

wireless sensor network;localization algorithm;RPD;DV-Hop;path optimization

項目來源:江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新基金項目(BY2013015-33,BY2014024,BY2014023-362014,BY2014023-25)

2014-07-01修改日期:2014-09-09

10.3969/j.issn.1004-1699.2014.11.018

TP393

:A

:1004-1699(2014)11-1539-06