胡 遠(yuǎn)，喬建華

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

無(wú)線傳感器網(wǎng)絡(luò)(WSN)是指將大量的具有通信與計(jì)算能力的微小傳感器節(jié)點(diǎn)，通過(guò)人工布設(shè)、空投、火炮投射等方法布置在預(yù)定的監(jiān)控區(qū)域[1]，構(gòu)成的智能自治監(jiān)控網(wǎng)絡(luò)系統(tǒng)，可以將感知和計(jì)算后的相關(guān)信息傳輸?shù)接?jì)算機(jī)終端，實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域的信息采集和監(jiān)控[2]。較早的定位技術(shù)只是局限于在二維平面區(qū)域內(nèi)研究的，隨著科學(xué)技術(shù)的發(fā)展和進(jìn)步，二維定位算法已經(jīng)不能滿足許多定位需求，無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)也逐漸發(fā)展到三維空間網(wǎng)絡(luò)中[3]。例如越來(lái)越多的建筑物的外形采用殼體，由于其特殊的外形給檢查和維修帶來(lái)了較大的麻煩，利用三維節(jié)點(diǎn)定位技術(shù)和傳感器技術(shù)就可以對(duì)故障進(jìn)行初步定位，給建筑物維修帶來(lái)很大的便利。通過(guò)在地形不平整的山區(qū)地形布設(shè)無(wú)線傳感器網(wǎng)絡(luò)，從而可以運(yùn)用三維定位技術(shù)來(lái)監(jiān)控預(yù)防泥石流、山體滑坡等大型地質(zhì)災(zāi)害的發(fā)生[4]。

近年來(lái)隨著傳感器網(wǎng)絡(luò)定位技術(shù)的發(fā)展應(yīng)用許多定位算法被提出，這些定位算法主要分為兩類：基于距離的定位算法和無(wú)需距離的定位算法，前者主要利用到達(dá)時(shí)間(TOA)[5]、到達(dá)時(shí)間差(TDOA)、接收信號(hào)強(qiáng)度(RSSI)[6]等方法，距離信息容易受到多徑衰落和環(huán)境的影響，另一方面功耗較高使得該算法無(wú)法大量使用。無(wú)需距離的定位算法主要有質(zhì)心算法[7]、DV-Hop算法以及APIT 算法等，這些算法功耗小且可以滿足大部分應(yīng)用的定位需求，因此得到更多研究。董靜薇等人針對(duì)DV-Hop算法的缺點(diǎn)，將基于距離和無(wú)需距離兩種定位方法相結(jié)合，引入了RSSI測(cè)距技術(shù)對(duì)平均每跳距離計(jì)算進(jìn)行修正，提高了定位精度[8]；劉桂琦等人使用改進(jìn)的微分進(jìn)化算法對(duì)DV-Hop進(jìn)行改進(jìn)，減小了定位誤差[9]；任克強(qiáng)等人提出將二維雙曲線法應(yīng)用到三維空間定位，結(jié)果比原始算法定位精確[10]；劉志貴等人基于APIT算法提出一種APIT-3D算法并進(jìn)行改進(jìn)，使得定位算法應(yīng)用更加廣泛[11]；Xiao Chen等人在三維定位基礎(chǔ)上提出粒子群優(yōu)化技術(shù)的方法，較好的使用了群體智能算法的優(yōu)點(diǎn)[12]。沈世凱等人提出了基于概率信息的錨節(jié)點(diǎn)選擇方法，并采用二維雙曲線函數(shù)來(lái)預(yù)測(cè)未知節(jié)點(diǎn)的位置，實(shí)驗(yàn)表明算法定位精度較高[13]。崔志華等人提出一種新的杜鵑搜索算法對(duì)DV-Hop算法定位性能進(jìn)行優(yōu)化改進(jìn)，仿真結(jié)果表明改進(jìn)后的算法具有更好的精度[14]。

本文在分析和學(xué)習(xí)二維DV-Hop基礎(chǔ)上，進(jìn)一步將此算法擴(kuò)展到了三維無(wú)線傳感器網(wǎng)絡(luò)的定位中，并在此基礎(chǔ)上提出了基于雙通信半徑的改進(jìn)算法。以基于CC2530的無(wú)線傳感器網(wǎng)絡(luò)為例，無(wú)障礙無(wú)功放傳輸距離為(10～200)m，可以通過(guò)改變TXPOWER寄存器的值來(lái)改變發(fā)射功率大小得到兩個(gè)通信半徑，使得節(jié)點(diǎn)間的最小跳數(shù)更加接近真實(shí)值[15]，明顯提高了三維DV-Hop定位精度。

1 三維DV-Hop定位算法

1.1 算法描述

三維DV-Hop定位算法主要通過(guò)節(jié)點(diǎn)的三維坐標(biāo)計(jì)算來(lái)對(duì)立體空間中的一些目標(biāo)進(jìn)行定位研究[16]。

(1)獲得所有節(jié)點(diǎn)之間的最小跳數(shù)值

開始定位時(shí)，錨節(jié)點(diǎn)i向網(wǎng)絡(luò)中廣播數(shù)據(jù)包，這些數(shù)據(jù)包主要包含錨節(jié)點(diǎn)i的標(biāo)號(hào)、跳數(shù)值以及位置等信息，并將跳數(shù)初始值設(shè)置為0，接收到數(shù)據(jù)包的 節(jié)點(diǎn)首先檢查自己是否接收過(guò)來(lái)自這個(gè)錨節(jié)點(diǎn)發(fā)出的信息。如果此前沒有接收過(guò)該數(shù)據(jù)包，就把數(shù)據(jù)包中的跳數(shù)值保留下來(lái)，然后把該跳數(shù)值加一繼續(xù)轉(zhuǎn)發(fā)到網(wǎng)絡(luò)中去；如果接收過(guò)，則進(jìn)行跳數(shù)比較并僅保存跳數(shù)較小的跳數(shù)值再將跳數(shù)加一繼續(xù)轉(zhuǎn)發(fā)，直到所有節(jié)點(diǎn)都計(jì)算出到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)。

(2)計(jì)算未知節(jié)點(diǎn)的平均每跳距離

通過(guò)第一階段網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)據(jù)包洪泛后，每個(gè)錨節(jié)點(diǎn)都記錄了與其它錨節(jié)點(diǎn)的所有跳數(shù)值和三維坐標(biāo)，可以用公式(1)估算出每一跳的距離。

Hopsizei=

(1)

上式中表示錨節(jié)點(diǎn)i的平均每跳距離，式子中(xi,yi,zi)表示Hopsizei錨節(jié)點(diǎn)i的三維坐標(biāo)，(xj,yj,zj)表示錨節(jié)點(diǎn)j的三維坐標(biāo)，hij表示求出的錨節(jié)點(diǎn)i和j間的最小跳數(shù)。

(3)計(jì)算未知節(jié)點(diǎn)的坐標(biāo)

計(jì)算出每一跳的距離后，每一個(gè)錨節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)洪泛平均每跳距離，未知節(jié)點(diǎn)在計(jì)算與錨節(jié)點(diǎn)的距離時(shí)使用收到的第一個(gè)平均每跳距離，當(dāng)未知節(jié)點(diǎn)得到4 個(gè)或4 個(gè)以上錨節(jié)點(diǎn)的距離后，可以選擇用四邊測(cè)量法或極大似然估計(jì)法來(lái)確定自己的位置坐標(biāo)。

假設(shè)待定位節(jié)點(diǎn)U坐標(biāo)為(x,y,z)，錨節(jié)點(diǎn)坐標(biāo)為(xi,yi,zi)，兩者之間所求距離用di表示，得到(2)式。

(2)

節(jié)點(diǎn)U的坐標(biāo)可由下式求出：

X=(ATA)-1ATB

(3)

其中

A=

B=

1.2 三維DV-Hop定位算法示例

在圖1中，U表示未知節(jié)點(diǎn)，L1,L2,L3,L4表示四個(gè)錨節(jié)點(diǎn)，根據(jù)前面的定位算法可以求出L2的平均每跳距離Hopsize2.

圖1 DV-Hop算法示意圖

Hopsize2=(40+60+20)/(2+5+1)=15 m

從拓?fù)鋱D中可以看到未知節(jié)點(diǎn)到錨節(jié)點(diǎn)L1,L3,L4的最小跳數(shù)都為三跳，距離L2的最小跳數(shù)為兩跳，根據(jù)1.1介紹的定位算法，可以求出節(jié)點(diǎn)U到周圍四個(gè)錨節(jié)點(diǎn)的距離公式如下：

然后再應(yīng)用極大似然估計(jì)法就可以估算出未知節(jié)點(diǎn)的位置。

2 三維DV-Hop算法存在的問(wèn)題

在原始三維DV-Hop 定位算法中，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都是隨機(jī)拋撒的，節(jié)點(diǎn)的位置分布不均衡，尤其在三維空間定位分布更廣泛，不同節(jié)點(diǎn)間的拓?fù)浣Y(jié)構(gòu)圖大部分都不是直線路徑，而是通過(guò)其他節(jié)點(diǎn)連接起來(lái)的，在計(jì)算節(jié)點(diǎn)間的距離時(shí)如果用直線路徑求得的距離進(jìn)行計(jì)算，就會(huì)與實(shí)際距離有較大的偏差，會(huì)對(duì)最終的定位效果產(chǎn)生消極影響。

原始三維算法在計(jì)算節(jié)點(diǎn)間距離時(shí)，使用收到的第一個(gè)錨節(jié)點(diǎn)的平均每跳距離與跳數(shù)相乘，但是在傳感器網(wǎng)絡(luò)中一個(gè)未知節(jié)點(diǎn)周圍通常有多個(gè)錨節(jié)點(diǎn)，這樣只考慮最近的錨節(jié)點(diǎn)而忽略其它錨節(jié)點(diǎn)對(duì)定位精度的影響，也會(huì)影響定位精度的準(zhǔn)確性。

3 基于雙通信半徑的改進(jìn)三維DV-Hop定位算法

3.1 雙通信半徑算法

DV-Hop算法定位時(shí)，只要在錨節(jié)點(diǎn)通信半徑R廣播范圍內(nèi)的所有節(jié)點(diǎn)的跳數(shù)都記為一跳，那么在求錨節(jié)點(diǎn)的校正距離時(shí)就會(huì)產(chǎn)生誤差，從圖2中看到，當(dāng)區(qū)域中間錨節(jié)點(diǎn)數(shù)據(jù)在網(wǎng)絡(luò)中傳播時(shí)，四個(gè)未知節(jié)點(diǎn)都在其一跳的通信半徑范圍內(nèi)，所以它們收到的跳數(shù)都會(huì)增加一，再進(jìn)行轉(zhuǎn)發(fā)，從圖中很明顯看出它們到錨節(jié)點(diǎn)的跳數(shù)是有較大差別的，這樣用最小跳數(shù)乘以校正距離所得的節(jié)點(diǎn)間的距離與實(shí)際距離會(huì)有較大的誤差，會(huì)對(duì)算法定位精確度造成較大影響。以雙通信半徑進(jìn)行改進(jìn)后，圖2中節(jié)點(diǎn)1到錨節(jié)點(diǎn)的跳數(shù)就為0.5，節(jié)點(diǎn)2,3,4的跳數(shù)為1，計(jì)算出的跳數(shù)更加符合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而定位精度提高。

圖2 節(jié)點(diǎn)一跳區(qū)域示意圖

3.2 改進(jìn)算法示例

在圖1中，可以求出網(wǎng)絡(luò)中未知節(jié)點(diǎn)U到L1,L2,L3,L4四個(gè)未知節(jié)點(diǎn)的最小跳數(shù)分別為3，2，3，3，在本文經(jīng)過(guò)雙通信半徑廣播以后，可以得到四個(gè)節(jié)點(diǎn)的最小跳數(shù)變?yōu)?.5，2，2.5，3，這樣求出來(lái)的跳數(shù)比原始算法里的跳數(shù)更加接近真實(shí)值，經(jīng)過(guò)計(jì)算可以得到未知節(jié)點(diǎn)到四個(gè)錨節(jié)點(diǎn)的距離公式如下：

從上面的計(jì)算結(jié)果可以看出,求出來(lái)的四個(gè)距離能較好反映網(wǎng)路中節(jié)點(diǎn)的真實(shí)拓?fù)浣Y(jié)構(gòu)，從而使定位結(jié)果更加精確。

3.3 改進(jìn)算法的具體步驟

(1)計(jì)算節(jié)點(diǎn)間的最小跳數(shù)

定位開始時(shí)，節(jié)點(diǎn)的初始跳數(shù)為0，讓錨節(jié)點(diǎn)以0.5R為通信半徑廣播自身位置信息，接收到信息的鄰居節(jié)點(diǎn)將跳數(shù)值加上0.5；一段時(shí)間后，錨節(jié)點(diǎn)再以R為通信半徑進(jìn)行廣播，當(dāng)鄰居節(jié)點(diǎn)接收到該信息后先判斷是否接收過(guò)來(lái)自該節(jié)點(diǎn)的數(shù)據(jù)信息，如果沒有則更新跳數(shù)，否則不更新跳數(shù)。鄰居節(jié)點(diǎn)接收到信息以后繼續(xù)以上過(guò)程轉(zhuǎn)發(fā)數(shù)據(jù)。最后網(wǎng)絡(luò)中所有節(jié)點(diǎn)都會(huì)記錄到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)信息。

(2)計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離

當(dāng)通過(guò)第一步廣播得到了錨節(jié)點(diǎn)與其他節(jié)點(diǎn)間的最小跳數(shù)以后，所有錨節(jié)點(diǎn)由公式(1)計(jì)算得到各個(gè)錨節(jié)點(diǎn)的校正距離，它們之間距離由跳數(shù)值與未知節(jié)點(diǎn)收到的第一個(gè)錨節(jié)點(diǎn)的平均每跳距離相乘求得，本文的改進(jìn)算法可以使求得的距離更加精確，如圖2中，未知節(jié)點(diǎn)1的跳數(shù)記為0.5，就比原始算法中的跳數(shù)為1更加接近真實(shí)值。

(3)根據(jù)以上求出的距離使用極大似然法計(jì)算節(jié)點(diǎn)位置。

3.4 改進(jìn)算法的流程圖

4 仿真實(shí)驗(yàn)與結(jié)果分析

本文使用MatlabR2014a軟件對(duì)算法進(jìn)行仿真。模擬在長(zhǎng)、寬、高都為100 m的立體空間區(qū)域內(nèi)，通過(guò)隨機(jī)拋撒節(jié)點(diǎn)的方式自組織形成無(wú)線傳感器網(wǎng)路，節(jié)點(diǎn)總數(shù)記為100個(gè)，實(shí)驗(yàn)通過(guò)給錨節(jié)點(diǎn)個(gè)數(shù)和通信半徑設(shè)置不同數(shù)值來(lái)比較兩種定位算法誤差大小，由于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布具有隨機(jī)性，本文仿真是在經(jīng)過(guò)150次實(shí)驗(yàn)求得的平均值，圖3是在一次實(shí)驗(yàn)中三維空間網(wǎng)絡(luò)中所有節(jié)點(diǎn)的分布情況。

圖3 節(jié)點(diǎn)隨機(jī)分布圖

采用相對(duì)定位誤差對(duì)兩種算法定位性能做對(duì)比，公式如下:

(4)

相對(duì)定位誤差的值越小，說(shuō)明算法的定位精度越高，上式中(xi，yi，zi)表示估算出的未知節(jié)點(diǎn)坐標(biāo)，(xo，yo，zo)是未知節(jié)點(diǎn)真實(shí)坐標(biāo)。

圖4設(shè)置網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)為100個(gè)，錨節(jié)點(diǎn)比例為20%，通信半徑為50 m，兩種點(diǎn)位算法的定位誤差對(duì)比情況。從下面圖中可以看到，除了極少數(shù)的幾個(gè)節(jié)點(diǎn)以外，其他未知節(jié)點(diǎn)在改進(jìn)算法的定位誤差明顯小于原始三維定位算法，且本文算法的定位誤差更加穩(wěn)定。

圖4 兩種算法未知節(jié)點(diǎn)誤差對(duì)比圖

圖5設(shè)置網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)為100個(gè)，通信半徑為50 m時(shí)，讓錨節(jié)點(diǎn)個(gè)數(shù)從10個(gè)以5為步長(zhǎng)增加到50個(gè)，通過(guò)仿真得到的誤差對(duì)比圖。從仿真結(jié)果看出，當(dāng)網(wǎng)絡(luò)中錨節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，兩種算法的定位誤差逐漸變小，且改進(jìn)算法定位誤差遠(yuǎn)小于原始算法定位誤差。

圖5 不同錨節(jié)點(diǎn)比例定位誤差對(duì)比圖

圖6是設(shè)置節(jié)點(diǎn)總數(shù)為100個(gè)，錨節(jié)點(diǎn)數(shù)為20個(gè)，通信半徑從45 m增加到70 m時(shí)兩種算法定位誤差情況。當(dāng)通信半徑從45 m增大到70 m時(shí)，可以看到兩種算法的定位誤差都在變小。在任意通信半徑下，改進(jìn)的算法都在原有算法的基礎(chǔ)上有了很明顯的提高。這是因?yàn)殡S著通信半徑的增大，未知節(jié)點(diǎn)獲得的錨節(jié)點(diǎn)信息越多，從而錨節(jié)點(diǎn)計(jì)算出的平均每跳距離比較接近真實(shí)值，所以誤差會(huì)變小。

圖6 不同通信半徑定位誤差對(duì)比圖

5 結(jié)論

本文經(jīng)過(guò)研究原始三維定位算法及已有的改進(jìn)算法，引入雙通信半徑來(lái)改變節(jié)點(diǎn)間最小跳數(shù)，使得節(jié)點(diǎn)間的跳數(shù)更加精確，能較好反映節(jié)點(diǎn)分布情況。通過(guò)仿真圖像可以得到，隨著錨節(jié)點(diǎn)個(gè)數(shù)和通信半徑的增加，兩種算法的定位誤差都在減小，并且本文改進(jìn)的算法比原始三維算法定位誤差減小了10%左右。