高瑞娟，陳桂芬，徐 赫

(長春理工大學(xué) 電子信息工程學(xué)院，吉林 長春 130022)

0 引 言

傳感器節(jié)點(diǎn)包括靜止節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)，這些節(jié)點(diǎn)通過自組織的方式構(gòu)成無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)[1,2]。基于無線傳感器的研究主要有節(jié)點(diǎn)定位技術(shù)、網(wǎng)絡(luò)覆蓋技術(shù)和路由協(xié)議技術(shù)等方面，本文將對(duì)眾多技術(shù)中的定位技術(shù)進(jìn)行研究。

隨著當(dāng)今時(shí)代技術(shù)的發(fā)展，許多傳感器技術(shù)被應(yīng)用于大型農(nóng)業(yè)中，例如無線溫度傳感器、無線光照傳感器等。然而在規(guī)模較大、環(huán)境惡劣、地形較復(fù)雜的農(nóng)田中部署的傳感器一般是通過飛機(jī)隨機(jī)拋灑的，這就意味著對(duì)隨機(jī)拋灑的傳感器節(jié)點(diǎn)進(jìn)行準(zhǔn)確定位成為獲取農(nóng)田可靠溫度、光照、氣體等信息的前提。目前，有許多學(xué)者對(duì)DV-Hop定位算法進(jìn)行了改進(jìn)[3-5]，但這些僅適用于二維空間。由于實(shí)際環(huán)境的復(fù)雜性，二維空間的定位算法已經(jīng)滿足不了定位精度的需求，需上升到三維空間進(jìn)行研究。

目前為止，三維空間中的定位算法有Landscape-3D(landscape three-dimensional)算法[6]、APIS(approximate point in sphere)算法[7]、3D-DV-Hop (three-dimensional distance vector-hop)算法[8]、Constrained-3D(constrained three-dimensional)算法[9]等。其中，眾多算法中的3D-DV-Hop定位算法計(jì)算相對(duì)簡單，所以有許多學(xué)者將其進(jìn)行改進(jìn)[10,11]。但這些改進(jìn)算法并沒有考慮錨節(jié)點(diǎn)共面問題，因此本文將對(duì)節(jié)點(diǎn)定位中存在的共面問題進(jìn)行深刻研究，提出一種適用于三維空間中的錨節(jié)點(diǎn)組按規(guī)定路徑移動(dòng)的非測(cè)距定位算法。

1 3D-DV-Hop定位算法介紹

三維空間中DV-Hop定位原理類似于二維空間中DV-Hop定位原理，具體介紹如下：

(1)獲取最小跳數(shù)

大量節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)被隨機(jī)部署后，錨節(jié)點(diǎn)通過向周圍節(jié)點(diǎn)發(fā)送自身包含ID號(hào)、位置信息以及跳數(shù)hi的數(shù)據(jù)包信息[12]。其中，跳數(shù)hi開始值記為0。未知節(jié)點(diǎn)不斷接收來自周圍錨節(jié)點(diǎn)的數(shù)據(jù)包，若接收到的數(shù)據(jù)包中的跳數(shù)小于已經(jīng)保存的最小跳數(shù)，則拋棄已經(jīng)保存的跳數(shù)，同時(shí)把當(dāng)前跳數(shù)進(jìn)行加一，并將自身的信息傳送到網(wǎng)絡(luò)中。

(2)估算平均跳距

用錨節(jié)點(diǎn)間坐標(biāo)之差除以錨節(jié)點(diǎn)間的跳數(shù)求得檢測(cè)區(qū)域內(nèi)所有錨節(jié)點(diǎn)間的平均跳距HopSizeij為

(1)

式中：(xi,yi,zi)、(xj,yj,zj)分別為錨節(jié)點(diǎn)i、j的位置坐標(biāo)，hij為錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j之間的跳數(shù)。進(jìn)一步可得出未知節(jié)點(diǎn)與錨節(jié)點(diǎn)i之間距離di為

di=hij×HopSizeij,(i≠j)

(2)

(3)計(jì)算未知節(jié)點(diǎn)位置

最后，經(jīng)過以上計(jì)算后，若未知節(jié)點(diǎn)附近的鄰居錨節(jié)點(diǎn)數(shù)等于4個(gè)，傾向于選擇四邊測(cè)量法獲得未知節(jié)點(diǎn)的坐標(biāo)。若未知節(jié)點(diǎn)附近的鄰居錨節(jié)點(diǎn)數(shù)超過4個(gè)，傾向于選擇極大似然估計(jì)法獲得未知節(jié)點(diǎn)的坐標(biāo)。

2 算法改進(jìn)思想

本文的改進(jìn)算法具體介紹如下：

2.1 分層式錨節(jié)點(diǎn)組移動(dòng)路徑

在三維空間中，節(jié)點(diǎn)部署雜亂無序。為了定位計(jì)算容易，將三維空間分層為無數(shù)個(gè)二維空間進(jìn)行處理。三維空間的分層式劃分如圖1所示。

監(jiān)測(cè)區(qū)域經(jīng)過分層處理后，在監(jiān)測(cè)區(qū)域邊界處部署一組移動(dòng)錨節(jié)點(diǎn)組，并使錨節(jié)點(diǎn)組按一定的靜態(tài)移動(dòng)路徑移動(dòng)。其中，移動(dòng)錨節(jié)點(diǎn)組的相對(duì)位置關(guān)系如圖2所示。

圖1 三維空間的分層式劃分

圖2 移動(dòng)錨節(jié)點(diǎn)組的相對(duì)位置關(guān)系

接下來，讓錨節(jié)點(diǎn)組在監(jiān)測(cè)區(qū)域內(nèi)按規(guī)定的移動(dòng)路徑開始移動(dòng)，如圖3所示。

圖3 錨節(jié)點(diǎn)組移動(dòng)路徑

2.2 計(jì)算錨節(jié)點(diǎn)共面度值

為了解決共面現(xiàn)象導(dǎo)致未知節(jié)點(diǎn)不能確定的問題，必須要采取一些度量標(biāo)準(zhǔn)衡量四面體的質(zhì)量?，F(xiàn)有的衡量四面體質(zhì)量的標(biāo)準(zhǔn)有系數(shù)γ、半徑比ρ、最小立體角θ等，考慮到衡量四面體網(wǎng)格質(zhì)量標(biāo)準(zhǔn)方法的準(zhǔn)確性幾乎等價(jià)，本文采用最小立體角θ的測(cè)量方式測(cè)量共面度，具體介紹如下：

在4個(gè)錨節(jié)點(diǎn)構(gòu)成的四面體中，4個(gè)夾角分別用θ1、θ2、θ3、θ4表示，具體計(jì)算如式(3)所示

(3)

式中：V表示四面體的體積，lij表示錨節(jié)點(diǎn)i、j之間的距離。將θ1、θ2、θ3、θ4這4個(gè)角度進(jìn)行對(duì)比，取其中的最小角度θ作為衡量四面體的平面度值，如式(4)所示

θ=MIN(θ1、θ2、θ3、θ4)

(4)

(5)

2.3 虛擬錨節(jié)點(diǎn)組平均跳距

3D-DV-Hop定位算法是用平均跳距等于錨節(jié)點(diǎn)間距離除以錨節(jié)點(diǎn)間跳數(shù)。但在本文中提出的錨節(jié)點(diǎn)組按規(guī)定路徑移動(dòng)的三維定位算法中，錨節(jié)點(diǎn)組是按靜態(tài)移動(dòng)路徑SCAN移動(dòng)整個(gè)三維區(qū)域，遍移動(dòng)后的區(qū)域中不存在錨節(jié)點(diǎn)，且未知節(jié)點(diǎn)所獲得信息均來源于虛擬錨節(jié)點(diǎn)并非錨節(jié)點(diǎn)。因此，無法直接計(jì)算錨節(jié)點(diǎn)間的平均跳距。

接下來，用一種計(jì)算虛擬錨節(jié)點(diǎn)組間的距離方法解決移動(dòng)路徑中存在的問題，即用篩選出來的r組虛擬錨節(jié)點(diǎn)組來估算平均每跳距離，如式(6)所示

(6)

2.4 未知節(jié)點(diǎn)位置重新定位

最后，將節(jié)點(diǎn)之間的距離進(jìn)行共面度加權(quán)處理，如下式(7)所示

(7)

式中：(x,y,z)表示待定位節(jié)點(diǎn)坐標(biāo)，(xn,yn,zn)表示虛擬錨節(jié)點(diǎn)組的位置，wi表示平面度加權(quán)值，di(i=1,2,…,n)表示節(jié)點(diǎn)間的距離。

將式(7)化簡后可得

AX=b

(8)

其中

(9)

(10)

(11)

最終求得未知節(jié)點(diǎn)的坐標(biāo)為

X=(ATA)-1ATb

(12)

3 仿 真

為驗(yàn)證提出的移動(dòng)錨節(jié)點(diǎn)組按規(guī)定移動(dòng)路徑移動(dòng)的定位算法能夠有效降低節(jié)點(diǎn)定位誤差，本文對(duì)算法進(jìn)行了仿真，并與3D-DV-Hop算法以及其它的改進(jìn)算法進(jìn)行比較。仿真中，平均定位誤差的衡量標(biāo)準(zhǔn)如式(13)所示

(13)

式中：待定位未知節(jié)點(diǎn)的實(shí)際坐標(biāo)用(xi,yi,zi)表示，待定位未知節(jié)點(diǎn)的所求坐標(biāo)用(xj,yj,zj)表示，監(jiān)測(cè)區(qū)域內(nèi)待定位未知節(jié)點(diǎn)的數(shù)量用N表示，監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)的通信范圍半徑用R表示。相關(guān)的仿真參數(shù)見表1。

表1 仿真參數(shù)

將通信半徑R為40 m的500個(gè)節(jié)點(diǎn)隨機(jī)拋灑在100 m*100 m*100 m的監(jiān)測(cè)區(qū)域內(nèi)，節(jié)點(diǎn)隨機(jī)拋灑生成圖如圖4所示。其中，錨節(jié)點(diǎn)為100個(gè)，符號(hào)為“*”，未知節(jié)點(diǎn)400個(gè)，符號(hào)為“°”。

為了仿真結(jié)果的可靠性，對(duì)節(jié)點(diǎn)隨機(jī)分布進(jìn)行500次仿真，仿真的相對(duì)平均誤差如圖5所示。由500次仿真結(jié)果可知，除了個(gè)別次仿真外，改進(jìn)算法的定位誤差均在0.21 m上下浮動(dòng)，定位誤差較穩(wěn)定。

圖4 未知節(jié)點(diǎn)定位誤差

圖5 loop次相對(duì)平均誤差

圖6為錨節(jié)點(diǎn)比例對(duì)平均定位誤差的影響仿真圖。仿真中，設(shè)監(jiān)測(cè)區(qū)域?yàn)檫呴L100 m的三維空間，在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)分布500個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)通信半徑固定為40 m，改變網(wǎng)絡(luò)中錨節(jié)點(diǎn)的比例，從10%逐步增加到40%，同時(shí)對(duì)本文算法、傳統(tǒng)算法、文獻(xiàn)[10]算法以及文獻(xiàn)[11]算法進(jìn)行仿真對(duì)比。

圖6 錨節(jié)點(diǎn)比例對(duì)平均定位誤差的影響仿真

根據(jù)圖6中的數(shù)據(jù)線變化能夠看到，當(dāng)錨節(jié)點(diǎn)數(shù)達(dá)到總節(jié)點(diǎn)數(shù)的20%以上時(shí)，節(jié)點(diǎn)定位誤差變化開始緩慢。4種算法平均定位誤差隨著錨節(jié)點(diǎn)的比例增大均有所下降，本文算法的平均定位誤差相對(duì)于傳統(tǒng)定位算法、文獻(xiàn)[10]算法、文獻(xiàn)[11]算法分別降低了29.76%、10.22%、4.31%。

圖7為節(jié)點(diǎn)通信半徑對(duì)平均定位誤差的影響仿真圖。網(wǎng)絡(luò)中總節(jié)點(diǎn)為500，錨節(jié)點(diǎn)比例為20%，讓節(jié)點(diǎn)通信半徑逐漸遞增，對(duì)算法進(jìn)行仿真。

圖7 節(jié)點(diǎn)通信半徑對(duì)平均定位誤差的影響仿真

從圖7中的數(shù)據(jù)線變化可以明顯看出當(dāng)節(jié)點(diǎn)通信半徑達(dá)到40 m時(shí)，節(jié)點(diǎn)定位誤差的變化開始平緩。4種算法的平均定位誤差隨著通信半徑的增大均有明顯下降，本文算法的平均定位誤差相對(duì)于傳統(tǒng)定位算法、文獻(xiàn)[10]算法、文獻(xiàn)[11]算法分別降低了37.26%、13.85%、8.96%。

圖8為總節(jié)點(diǎn)個(gè)數(shù)對(duì)平均定位誤差的影響仿真圖。在監(jiān)測(cè)區(qū)域中分別部署100個(gè)、200個(gè)、300個(gè)、400個(gè)、500個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)中錨節(jié)點(diǎn)占比固定為總節(jié)點(diǎn)的20%，節(jié)點(diǎn)通信半徑固定為40 m，對(duì)算法進(jìn)行仿真。

圖8 總節(jié)點(diǎn)個(gè)數(shù)對(duì)平均定位誤差的影響仿真

從圖8中可以看出，傳統(tǒng)定位算法、文獻(xiàn)[10]算法、文獻(xiàn)[11]算法以及本文提出的定位算法隨著總節(jié)點(diǎn)個(gè)數(shù)的增加，平均定位誤差都有所下降。在同等總節(jié)點(diǎn)個(gè)數(shù)情況下，本文提出的定位算法的平均定位誤差相對(duì)于傳統(tǒng)定位算法、文獻(xiàn)[10]算法、文獻(xiàn)[11]算法分別降低了36.25%、12.77%、16.83%。

4 結(jié)束語

當(dāng)三維空間中錨節(jié)點(diǎn)組出現(xiàn)共面現(xiàn)象時(shí)，將會(huì)導(dǎo)致未知節(jié)點(diǎn)無法定位。針對(duì)這個(gè)現(xiàn)象，提出一種適用于三維空間中的錨節(jié)點(diǎn)組按規(guī)定路徑移動(dòng)的非測(cè)距定位算法。通過對(duì)監(jiān)測(cè)區(qū)域進(jìn)行分層式錨節(jié)點(diǎn)組移動(dòng)路徑規(guī)劃，計(jì)算虛擬錨節(jié)點(diǎn)組的共面度值以及用虛擬錨節(jié)點(diǎn)組計(jì)算平均跳距，最終對(duì)節(jié)點(diǎn)間距離進(jìn)行共面度加權(quán)計(jì)算出待定位節(jié)點(diǎn)位置。實(shí)驗(yàn)結(jié)果表明本文提出的算法有效的避免了錨節(jié)點(diǎn)共面現(xiàn)象，進(jìn)而提高了未知節(jié)點(diǎn)的定位精度。接下來的工作是針對(duì)算法中存在的共線問題進(jìn)行研究。