王 梟,劉瑞敏,毛劍琳

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

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

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

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

1 定位模型

該算法模型共含有3個步驟:

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

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

(1)

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

Di,z=WHD_i×Hi,z。

(2)

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

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

2 TC定位算法

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

2.1 新的跳數(shù)機制

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

(3)

其中，

(4)

(5)

ai=min(Dalli,j)。

(6)

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

2.2 跳距修正

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

WHD_z=HOPT×Cent_Weigh。

(7)

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

Cent_Weigh(i)=

(8)

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

2.3 定位算法

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

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

Diz=WHD_z×Hi,z。

(9)

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

Derror＿iz=

(10)

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

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

Dcor＿iz=Diz+Derror＿iz。

(11)

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

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

(12)

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

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

(13)

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

(14)

設(shè)Xk為經(jīng)過k次迭代所得到的未知節(jié)點坐標(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è)置,式(16)中J為雅克比矩陣。

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

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

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

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

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

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

3 仿真實驗與分析

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

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

(18)

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

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

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

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

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

4 結(jié) 語

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