王 梟,劉瑞敏,毛劍琳

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,昆明 650500)

無線傳感器網(wǎng)絡(luò)是一種被部署在受控區(qū)域的多跳自組織網(wǎng)絡(luò),它由大量的具有通信與感知能力的傳感器節(jié)點(diǎn)構(gòu)成,在入侵檢測、工業(yè)自動(dòng)化、智能建筑等眾多領(lǐng)域有著極其廣泛的應(yīng)用[1-4]。在任何領(lǐng)域中，只要涉及到無線傳感器網(wǎng)絡(luò)的應(yīng)用,那么它的節(jié)點(diǎn)定位就起著不可估量的作用。目前,在節(jié)點(diǎn)定位技術(shù)中,主要有基于測距和基于非測距的定位技術(shù)。雖然基于測距的定位技術(shù)通過節(jié)點(diǎn)間的絕對距離來計(jì)算節(jié)點(diǎn)的位置,精度相對較高,但是，在大型區(qū)域中它會(huì)產(chǎn)生較高的硬件成本,同時(shí)也會(huì)產(chǎn)生較高的能耗。然而，基于非測距的定位技術(shù)僅需要節(jié)點(diǎn)間的互連來實(shí)現(xiàn)定位,因需要較少的硬件支持,成本比較低廉而受到青睞[5]。在測距定位中,研究較為廣泛的是TOA，TDOA，RSSI，AOA等技術(shù);在非測距定位中,對于Centroid，APIT，DV-HOP技術(shù)的研究較為廣泛。

本文在DV-HOP算法的基礎(chǔ)上進(jìn)行改進(jìn)優(yōu)化，使得定位效果更佳。DV-HOP技術(shù)通過錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的相互通信來獲取每個(gè)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)值,然后，根據(jù)錨節(jié)點(diǎn)間的跳數(shù)與距離,計(jì)算出錨節(jié)點(diǎn)的平均跳距,最后，未知節(jié)點(diǎn)通過跳距計(jì)算出到錨節(jié)點(diǎn)距離,再根據(jù)某種計(jì)算方法計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)。DV-HOP算法由于其在實(shí)際環(huán)境定位中無需測距設(shè)備,可以大大降低網(wǎng)絡(luò)的成本,因此，在實(shí)際應(yīng)用中具有獨(dú)特的優(yōu)勢。當(dāng)DV-HOP在大規(guī)模網(wǎng)絡(luò)中被應(yīng)用時(shí),它的關(guān)鍵問題是如何設(shè)計(jì)跳數(shù)機(jī)制、如何能有效降低跳距的誤差以及如何能較準(zhǔn)確地求出未知節(jié)點(diǎn)的定位算法。實(shí)際上,由于網(wǎng)絡(luò)中未知節(jié)點(diǎn)的數(shù)量多于錨節(jié)點(diǎn)數(shù)的原因,利用錨節(jié)點(diǎn)的跳距來求錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離是造成距離誤差的一個(gè)因素;另外,由于錨節(jié)點(diǎn)間的跳數(shù)可能會(huì)存在不是整跳數(shù)的情況,按照傳統(tǒng)整數(shù)跳數(shù)機(jī)制就會(huì)使得跳距出現(xiàn)偏差;最后,在定位算法中由于沒有對未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離進(jìn)行誤差校正而使得定位效果較差。但是由于DV-HOP定位精度較低的缺點(diǎn),使得許多研究人員致力于定位精度優(yōu)化算法的研究[6]。因此,國內(nèi)外的研究學(xué)者們紛紛對DV-HOP算法做了不同的改進(jìn)與優(yōu)化。趙雁航等[7]首先對跳距進(jìn)行修正,然后，通過粒子群優(yōu)化算法來降低定位誤差;文獻(xiàn)[8]通過距離校正因子結(jié)合傳感器節(jié)點(diǎn)的通信半徑校正未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的平均跳距;文獻(xiàn)[9]引入跳數(shù)因子,通過跳距的誤差加權(quán)來進(jìn)行跳距的修正,最后，通過加權(quán)最小二乘來定位;文獻(xiàn)[10]中錨節(jié)點(diǎn)先將跳距傳播給鄰居的未知節(jié)點(diǎn),然后，依據(jù)此跳距計(jì)算出錨節(jié)點(diǎn)間的估計(jì)距離，計(jì)算出與錨節(jié)點(diǎn)間實(shí)際距離的誤差,并且將此誤差的百分比作為權(quán)重來計(jì)算未知節(jié)點(diǎn)的跳距;文獻(xiàn)[11]依據(jù)最小均方誤差來求出每個(gè)錨節(jié)點(diǎn)的跳距,然后，將某個(gè)錨節(jié)點(diǎn)間跳數(shù)的倒數(shù)與所有錨節(jié)點(diǎn)間跳數(shù)的倒數(shù)之和的比作為加權(quán)值來對跳距進(jìn)行加權(quán),最后，采用雙曲線定位算法進(jìn)行定位;徐慧娟等[12]利用相似度對測距值進(jìn)行校正,然后，將最小二乘法得到的未知節(jié)點(diǎn)坐標(biāo)作為遺傳模擬退火算法的初始解進(jìn)行迭代，得到比較優(yōu)良的未知節(jié)點(diǎn)坐標(biāo);劉登峰等[13]將定位問題轉(zhuǎn)換為優(yōu)化問題,利用布谷鳥差分優(yōu)化算法進(jìn)行優(yōu)化求解,可以有效地規(guī)避定位過程中誤差積累的缺點(diǎn)。雖然一直有許多研究學(xué)者在DV-HOP方面做出了大量的研究與改進(jìn),但是依舊有些問題是需要繼續(xù)研究的,包括未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳距、符合實(shí)際情況的跳數(shù)機(jī)制、在定位算法中未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離誤差校正等問題。

本文提出一種基于三重修正的無線傳感器網(wǎng)絡(luò)定位算法(triple correction localization algorithm),以下簡稱TC定位算法。在計(jì)跳階段,采用新的跳數(shù)計(jì)跳機(jī)制;在跳距階段,通過質(zhì)心定位算法來對錨節(jié)點(diǎn)的跳距加權(quán)得出未知節(jié)點(diǎn)的跳距,減小節(jié)點(diǎn)的距離誤差;在定位階段,采用最小二乘法校正傳感器節(jié)點(diǎn)的距離矩陣。最后，通過高斯牛頓算法進(jìn)行定位求解,有效地減小定位過程中產(chǎn)生的誤差。

1 定位模型

該算法模型共含有3個(gè)步驟:

step1估計(jì)所有節(jié)點(diǎn)跳數(shù)。錨節(jié)點(diǎn)以泛洪的方式將它自身的信息傳播到整個(gè)網(wǎng)絡(luò)中,這些信息分別包括坐標(biāo)、id、跳數(shù)。直到網(wǎng)絡(luò)中的節(jié)點(diǎn)全部連通時(shí),所有的未知節(jié)點(diǎn)即可獲取到錨節(jié)點(diǎn)的跳數(shù)。當(dāng)多個(gè)錨節(jié)點(diǎn)給同一未知節(jié)點(diǎn)傳播坐標(biāo)信息時(shí),未知節(jié)點(diǎn)只保留跳數(shù)值最小的信息。這樣就得到了未知節(jié)點(diǎn)到所有錨節(jié)點(diǎn)的跳數(shù)信息。

step2估計(jì)錨節(jié)點(diǎn)的平均跳距。錨節(jié)點(diǎn)根據(jù)自己的坐標(biāo)與到其他錨節(jié)點(diǎn)的跳數(shù)信息計(jì)算錨節(jié)點(diǎn)的平均跳距,然后，錨節(jié)點(diǎn)將本身的平均跳距傳播到網(wǎng)絡(luò)中。錨節(jié)點(diǎn)i到其他未知節(jié)點(diǎn)的平均跳距如式(1)所示，

(1)

其中：(xi,yi)，(xi,yj)分別表示錨節(jié)點(diǎn)i，j的坐標(biāo);N表示錨節(jié)點(diǎn)的個(gè)數(shù)；Hi,j表示錨節(jié)點(diǎn)i，j之間的跳數(shù)。根據(jù)已經(jīng)得到的跳數(shù)信息與錨節(jié)點(diǎn)的平均跳距計(jì)算出未知節(jié)點(diǎn)z到錨節(jié)點(diǎn)i的距離，如式(2)所示，

Di,z=WHD_i×Hi,z。

(2)

其中：Hi,z表示錨節(jié)點(diǎn)i到未知節(jié)點(diǎn)z的跳數(shù)；Di,z表示錨節(jié)點(diǎn)i到到未知節(jié)點(diǎn)z的距離。

step3估計(jì)未知節(jié)點(diǎn)坐標(biāo)。根據(jù)第2步中未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離信息,利用定位算法估計(jì)未知節(jié)點(diǎn)的坐標(biāo)。

2 TC定位算法

傳統(tǒng)DV-HOP算法在計(jì)跳階段以整數(shù)的形式對節(jié)點(diǎn)間的跳數(shù)來計(jì)量,但實(shí)際中的跳數(shù)并不都是整數(shù),所以，在整個(gè)網(wǎng)絡(luò)中會(huì)造成誤差的積累;在錨節(jié)點(diǎn)的平均跳距階段,由于每個(gè)錨節(jié)點(diǎn)到所有未知節(jié)點(diǎn)的跳距相同,當(dāng)未知節(jié)點(diǎn)較多時(shí),也會(huì)出現(xiàn)誤差較大的情況;另外,由于跳數(shù)、跳距獲得過程中累積的誤差,在計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)間的距離時(shí)，勢必會(huì)產(chǎn)生較大偏差,所以，應(yīng)該在定位階段加入校正未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的環(huán)節(jié)。因此,文中首先利用新的跳數(shù)機(jī)制實(shí)現(xiàn)非整數(shù)的計(jì)跳,再通過質(zhì)心算法對不同錨節(jié)點(diǎn)到每個(gè)未知節(jié)點(diǎn)的跳距進(jìn)行加權(quán)，得出較合理的未知節(jié)點(diǎn)的跳距,然后，利用最小二乘法對未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離矩陣進(jìn)行校正,最后，根據(jù)校正后的距離矩陣，利用高斯牛頓算法來得出比較準(zhǔn)確的未知節(jié)點(diǎn)位置。

2.1 新的跳數(shù)機(jī)制

按照傳統(tǒng)的計(jì)數(shù)方式,當(dāng)節(jié)點(diǎn)在它的通信半徑內(nèi)可以與其他節(jié)點(diǎn)通信時(shí)，就認(rèn)為這些節(jié)點(diǎn)間的跳數(shù)為1跳,但這種辦法在實(shí)際應(yīng)用中是不太合理的,所以，將跳數(shù)機(jī)制修正成式(3)，

(3)

其中，

(4)

(5)

ai=min(Dalli,j)。

(6)

其中：Dalli,j表示錨節(jié)點(diǎn)i，j的距離；Di表示其他錨節(jié)點(diǎn)到錨節(jié)點(diǎn)i的平均距離；ai表示與錨節(jié)點(diǎn)i距離最近的錨節(jié)點(diǎn)的距離值。

2.2 跳距修正

通過質(zhì)心定位算法[14]對錨節(jié)點(diǎn)的跳距進(jìn)行加權(quán)，作為未知節(jié)點(diǎn)的跳距。錨節(jié)點(diǎn)的跳距是在已經(jīng)校正跳數(shù)的前提下按照式(1)計(jì)算得到。未知節(jié)點(diǎn)z的跳距如式(7)所示，

WHD_z=HOPT×Cent_Weigh。

(7)

其中：HOP是錨節(jié)點(diǎn)的跳距矩陣,是一個(gè)N行1列的矩陣;Cent_Weigh是一個(gè)N行1列的矩陣,這個(gè)矩陣中第i個(gè)元素為

Cent_Weigh(i)=

(8)

其中：(xi,yi)是錨節(jié)點(diǎn)的坐標(biāo)；(xz,yz)是由質(zhì)心算法計(jì)算出的未知節(jié)點(diǎn)的坐標(biāo)；N表示錨節(jié)點(diǎn)的個(gè)數(shù)。

2.3 定位算法

未知節(jié)點(diǎn)的求解過程可以看作求解非線性方程組,而高斯牛頓法是求解非線性方程組的一種有效方法[15]。但是，直接利用高斯牛頓算法會(huì)由于錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離誤差而造成定位精度下降,所以，在采用高斯牛頓算法定位前，應(yīng)對未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離進(jìn)行校正。

在經(jīng)過計(jì)跳與跳距修正以后,可以得到未知節(jié)點(diǎn)z到錨節(jié)點(diǎn)i之間的距離，

Diz=WHD_z×Hi,z。

(9)

通過最小二乘法對式(9)的距離進(jìn)行校正,

Derror＿iz=

(10)

其中：(xls_z,yls_z)表示由最小二乘法得到的第z個(gè)未知節(jié)點(diǎn)的坐標(biāo)；Diz表示第i個(gè)錨節(jié)點(diǎn)到第z個(gè)未知節(jié)點(diǎn)的距離；Derror＿iz表示錨節(jié)點(diǎn)i與未知節(jié)點(diǎn)z的距離誤差。

經(jīng)過校正后的未知節(jié)點(diǎn)z到錨節(jié)點(diǎn)i的距離為

Dcor＿iz=Diz+Derror＿iz。

(11)

其中,Dcor＿iz表示已經(jīng)經(jīng)過校正的未知節(jié)點(diǎn)z與錨節(jié)點(diǎn)i的距離。

假定Xz為未知節(jié)點(diǎn),未知節(jié)點(diǎn)坐標(biāo)為(xz,yz)。Bi為n個(gè)錨節(jié)點(diǎn)中的第i個(gè)錨節(jié)點(diǎn),它的坐標(biāo)為(xBi,yBi)。Diz表示未知節(jié)點(diǎn)Xz到錨節(jié)點(diǎn)i的距離, 是經(jīng)過校正的,即Diz∈Dcor_z。未知節(jié)點(diǎn)z到錨節(jié)點(diǎn)的距離的方程組如式(12)所示，

(12)

其中:‖·‖表示歐幾里得范數(shù)；n表示錨節(jié)點(diǎn)的個(gè)數(shù)。

經(jīng)過前期的校正算法后,得到了比較高效的未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離矩陣,最后，將問題轉(zhuǎn)化為求解式(13)中的非線性方程組,采用高斯牛頓算法進(jìn)行求解。將未知節(jié)點(diǎn)求解的問題轉(zhuǎn)化最小二乘問題,如式(13)所示，

(13)

其中,dz如式(14)所示，

(14)

設(shè)Xk為經(jīng)過k次迭代所得到的未知節(jié)點(diǎn)坐標(biāo),根據(jù)式(13)可以得到第k+1次的未知坐標(biāo)，

X(k+1)=X(k)+λ×ΔX，

(15)

ΔX=-[JT(X)J(X)]-1J(X)e(X)，

(16)

e(X)=‖Xz-B‖-Dz。

(17)

其中,λ為迭代步長,需要根據(jù)實(shí)驗(yàn)進(jìn)行設(shè)置,式(16)中J為雅克比矩陣。

具體的TC定位算法步驟如下：

step1部署網(wǎng)絡(luò),錨節(jié)點(diǎn)以泛洪方式在整個(gè)網(wǎng)絡(luò)中傳播自己的信息,并且根據(jù)式(3)，(7)，(9)來計(jì)算錨節(jié)點(diǎn)到位置節(jié)點(diǎn)的距離,再通過式(11)對未知節(jié)點(diǎn)到錨節(jié)點(diǎn)間的距離矩陣進(jìn)行校正；

step2對未知節(jié)點(diǎn)z的位置X、迭代次數(shù)iter、迭代步長λ、迭代誤差ε和當(dāng)前迭代次數(shù)k進(jìn)行初始化；

step3計(jì)算式(16)的雅克比矩陣,根據(jù)式(14)進(jìn)行迭代更新；

step4只要f(x)的值滿足迭代誤差,則將此時(shí)未知節(jié)點(diǎn)z的坐標(biāo)輸出，否則，返回至step3繼續(xù)迭代,令k=k+1,直至達(dá)到迭代次數(shù)要求；

step5輸出位置節(jié)點(diǎn)的坐標(biāo)。

3 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證文中所提算法的性能,在Matlab上進(jìn)行仿真實(shí)驗(yàn)。文獻(xiàn)[9，11]中的定位算法是在DV-HOP的基礎(chǔ)上進(jìn)行改進(jìn)的，所以，本文與文獻(xiàn)[9，11]中的算法進(jìn)行比較。另外,在本文修正跳距、跳數(shù)的基礎(chǔ)上,利用最小二乘法(LS)進(jìn)行定位,并與本文所提算法進(jìn)行對比。布置傳感器的檢測區(qū)域?yàn)?00m×100m,隨機(jī)撒200個(gè)節(jié)點(diǎn),傳感器的通信半徑為25m,錨節(jié)點(diǎn)的比例為s%,假定拋撒之后的傳感器節(jié)點(diǎn)不移動(dòng),并且錨節(jié)點(diǎn)的通信半徑都是相同的.每次實(shí)驗(yàn)在相互獨(dú)立的條件下進(jìn)行50次，取50次的平均誤差值作為定位誤差值。

將歸一化的定位誤差作為衡量定位性能的標(biāo)準(zhǔn),如式(18)所示，

(18)

其中：(xtl,ytl)和(xl,yl)分別是傳感器節(jié)點(diǎn)的真實(shí)坐標(biāo)和估計(jì)坐標(biāo)；s為未知節(jié)點(diǎn)的個(gè)數(shù)；r為傳感器節(jié)點(diǎn)的通信半徑。

圖1給出了傳感總節(jié)點(diǎn)數(shù)與平均定位誤差的關(guān)系曲線。設(shè)置信標(biāo)節(jié)點(diǎn)的比例為25%,通信半徑為25m。從圖1中可知,隨著傳感器節(jié)點(diǎn)數(shù)量的增加,本文所提算法的定位效果均優(yōu)于其他3種定位算。

圖2為錨節(jié)點(diǎn)的通信半徑變化對定位誤差的影響。設(shè)置信標(biāo)節(jié)點(diǎn)的比例為25%,傳感器總節(jié)點(diǎn)數(shù)為200。從圖2可以得知,隨著通信半徑的增加,在25m與35m之間,本文所提算法的定位誤差比其他3種定位誤差小。但是在35m之后,本文所提算法的精度開始有所下降,進(jìn)而可以得知,在適當(dāng)?shù)耐ㄐ虐霃椒秶畠?nèi),對未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離校正會(huì)起到正向作用,如果超出通信半徑范圍，由于距離校正起到反作用，從而導(dǎo)致定位精度反倒下降。多跳方式是引起距離測量誤差的一種因素，通信半徑變大到一定程度,即圖2中的35m,錨節(jié)點(diǎn)可以與更多的未知節(jié)點(diǎn)在通信半徑內(nèi)進(jìn)行通信,減少了需要多跳方式進(jìn)行通信的未知節(jié)點(diǎn),所以，加上跳數(shù)與跳距環(huán)節(jié)的修正,通信半徑較大的錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離測量誤差本來就很小了，在這個(gè)情況下加入距離校正,會(huì)導(dǎo)致圖2中過校正的情況。

圖1 傳感器總節(jié)點(diǎn)數(shù)變化對定位誤差的影響Fig.1 The effect of the total number of sensors on the positioning error

圖2 通信半徑變化對定位誤差的影響Fig.2 Effect of communication radius change on positioning error

圖3中給出了錨節(jié)點(diǎn)比例對定位誤差的影響曲線關(guān)系。設(shè)置傳感器總節(jié)點(diǎn)數(shù)為200,通信半徑為25m。從圖3中可以看出,隨著錨節(jié)點(diǎn)比例的增加,本文所提算法的誤差在不斷減小,由此可以得知所提算法的有效性。另外,在圖3中可以看到,本文所提算法的定位誤差均比其他3種算法的誤差小,可以得知，本文算法在定位中具有較好的優(yōu)勢,能夠提高定位精度。

圖3 錨節(jié)點(diǎn)比例變化對定位誤差的影響Fig.3 Effect of anchor node ratio change on positioning error

4 結(jié) 語

為了有效應(yīng)對傳感器網(wǎng)絡(luò)定位誤差較大的問題,本文提出一種基于三重修正的定位算法。首先，給出了新的計(jì)跳機(jī)制計(jì)算公式；然后，結(jié)合質(zhì)心定位算法計(jì)算未知節(jié)點(diǎn)的跳距；再利用最小二乘法對未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離矩陣進(jìn)行修正；最后，利用高斯牛頓法對未知節(jié)點(diǎn)與錨節(jié)點(diǎn)所組成的非線性方程組進(jìn)行優(yōu)化求解。另外,再通過Matlab實(shí)驗(yàn)平臺(tái)進(jìn)行仿真實(shí)驗(yàn),分析不同因素對定位誤差的影響。通過對比其他算法的定位效果,驗(yàn)證了本文所提算法能夠有效提高定位精度。在下一步的研究中,可以與多位標(biāo)度、模糊翻轉(zhuǎn)等技術(shù)結(jié)合，開發(fā)更加完備的無測距定位算法。