基于馬鞍地形的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法*

胡中棟,張 康,王振東

(江西理工大學(xué)信息工程學(xué)院,江西 贛州 341000)

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)的出現(xiàn)引起了全世界范圍的廣泛關(guān)注。1999年,著名的美國(guó)商業(yè)周刊將無(wú)線(xiàn)傳感器網(wǎng)絡(luò)列為21世紀(jì)最具影響的21項(xiàng)技術(shù)之一[1-2];2003年,MIT技術(shù)評(píng)論(Technology Review)在預(yù)測(cè)未來(lái)技術(shù)發(fā)展的報(bào)告中,將其列為改變世界的10大新技術(shù)之一[3]。環(huán)境監(jiān)測(cè)與預(yù)報(bào)、森林防火、地質(zhì)災(zāi)害監(jiān)測(cè)與預(yù)警等是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的重要應(yīng)用領(lǐng)域。節(jié)點(diǎn)定位是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)應(yīng)用的重要基礎(chǔ),是當(dāng)今無(wú)線(xiàn)傳感器網(wǎng)絡(luò)研究熱點(diǎn)之一[4]。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的應(yīng)用中,位置信息對(duì)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)活動(dòng)至關(guān)重要。如在大面積環(huán)境監(jiān)測(cè)中需要知道污染源發(fā)生的地點(diǎn);森林火災(zāi)災(zāi)情監(jiān)測(cè)中,需要知道火災(zāi)發(fā)生的地域[5-7];在地質(zhì)災(zāi)害監(jiān)測(cè)預(yù)警中,必需要知道發(fā)生險(xiǎn)情的時(shí)間與地域,以便迅速采取有效行動(dòng)。

現(xiàn)有的大多數(shù)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位技術(shù)都是假設(shè)應(yīng)用在理想環(huán)境下提出的。例如三維的定位算法適合三維自由空間內(nèi)的節(jié)點(diǎn)隨機(jī)分布情況,即假定信號(hào)傳輸模型為理想的球體。而無(wú)線(xiàn)傳感器網(wǎng)絡(luò)實(shí)際應(yīng)用環(huán)境往往是山區(qū)。如果用三維自由空間的定位算法來(lái)確定山區(qū)地形上的節(jié)點(diǎn)位置,往往無(wú)法達(dá)到節(jié)點(diǎn)定位的精度要求。因此,研究適合山區(qū)地形無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法具有重要意義。例如張亞杰、段渭軍等提出了改進(jìn)的距離重構(gòu)三維定位算法[8];廖興宇,余 敏,汪倫杰提出了基于錨球交域投影質(zhì)心的WSNs三維定位算法[9];屈軍鎖,侯曉寧等提出了四基站時(shí)差和牛頓迭代法的三維定位算法[10]等都是三維自由空間的定位算法。胡中棟、謝金偉、肖華為研究了基于山頭地形和基于山區(qū)地形的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法[11-13]。本文提出了基于山區(qū)馬鞍地形無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法(NLA-ST)。

1 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位技術(shù)

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位技術(shù)分為基于測(cè)距定位方法和非測(cè)距定位方法[14]?；跍y(cè)距定位方法定位精度高,但需要增加硬件成本。非測(cè)距定位方法受環(huán)境因素的影響小,雖然定位精度更低,但能夠滿(mǎn)足多數(shù)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)應(yīng)用的要求,因此備受關(guān)注。非測(cè)距定位方法主要有質(zhì)心算法、DV-Hop算法、Amorphous 算法、APIT算法等,其中影響最大、應(yīng)用最廣泛的當(dāng)屬DV-Hop算法[15]。

1.1 三維DV-Hop定位算法

Niculescu D等人提出了DV-Hop算法,距離矢量路由原理是此算法的主要原理。算法通過(guò)廣播在所有節(jié)點(diǎn)間進(jìn)行信息交換,得到每一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最小跳數(shù)。所有的未知節(jié)點(diǎn)根據(jù)到錨節(jié)點(diǎn)的最小跳數(shù)乘以每跳平均距離估算出到該錨節(jié)點(diǎn)的距離。根據(jù)以上信息通過(guò)最小二乘法(極大似然估計(jì)法)計(jì)算自身坐標(biāo)[16]。若未知節(jié)點(diǎn)的坐標(biāo)為(x,y,z),已知該未知節(jié)點(diǎn)到所有錨節(jié)點(diǎn)的距離為d1,d2,…,dn(n≥4),對(duì)應(yīng)的錨節(jié)點(diǎn)坐標(biāo)為(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn)。

可得矛盾方程組:

AX=B

(1)

若矛盾方程組有解則可得:

X=(ATA)-1ATB

(2)

1.2 性能評(píng)價(jià)

一般用相對(duì)定位誤差來(lái)評(píng)價(jià)算法的性能。

若某個(gè)未知節(jié)點(diǎn)的估算坐標(biāo)(xi,yi,zi)和實(shí)際坐標(biāo)(ai,bi,ci)差距Δdi為:

(3)

則n個(gè)未知節(jié)點(diǎn)的平均定位誤差Δ可表示為:

(4)

2 基于馬鞍地形的節(jié)點(diǎn)定位算法

山區(qū)地形是由山頭地形、山谷地形、山脊地形和馬鞍地形等組成的復(fù)雜地形。在山區(qū)地形上應(yīng)用無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的傳統(tǒng)非測(cè)距定位算法,其定位精度較低。所以需要研究適合山區(qū)地形上的節(jié)點(diǎn)定位算法,以提高傳感器節(jié)點(diǎn)定位精度。本文研究基于馬鞍地形的節(jié)點(diǎn)定位算法NLA-ST(Node Location Algorithm Based on Saddle Topography)。方法步驟如下:

第1步 建立山區(qū)馬鞍地形方程。因?yàn)殡p曲拋物面能很好的表示山區(qū)馬鞍地形,所以采用雙曲拋物面作為馬鞍地形的擬合函數(shù)。

雙曲拋物面方程為:

x2/a2-y2/b2=z

(5)

式中:a、b為正常數(shù)。采用最小二乘的曲面擬合算法,在山區(qū)電子地形圖上取一組離散點(diǎn)的坐標(biāo)代入雙曲拋物面方程(5)中,建立矛盾方程組來(lái)求擬合參數(shù)a和b,從而求得馬鞍地形方程。

圖1 山區(qū)馬鞍地形

圖2 傳感器節(jié)點(diǎn)在山區(qū)馬鞍地形隨機(jī)分布示意圖

第2步 在山區(qū)馬鞍地形上應(yīng)用經(jīng)典三維 DV-Hop 定位算法求出無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的初始位置。

第3步 將所求節(jié)點(diǎn)的初始位置垂直投影到馬鞍地形表面上。設(shè)所求節(jié)點(diǎn)初始位置P(x,y,z),在馬鞍地形表面上的投影點(diǎn)為P0(m,n,k)。通過(guò)P0(m,n,k)的法線(xiàn)方程可得2個(gè)關(guān)于m,n,k的方程,另外,P0(m,n,k)滿(mǎn)足馬鞍地形方程,得第3個(gè)方程。聯(lián)立這3個(gè)方程,可求出m,n,k。

對(duì)雙曲拋物面方程x2/a2-y2/b2=z進(jìn)行等價(jià)變換:兩邊同等乘于a2b2得:b2x2-a2y2=a2b2z。

(1)求雙曲拋物面法線(xiàn)方程

設(shè)雙曲拋物面上任意一點(diǎn)。

F(x,y,z)=b2x2-a2y2-a2b2z=0

?F/?x=2b2x, ?F/?y=-2a2y, ?F/?z=-a2b2

法向量為:

(2b2x,-2a2y,-a2b2)

過(guò)P0(m,n,k)的法向量方程為:

(6)

由式(6)有:

整理得:

b2ym-(a2+b2)mn+a2xn=0

(7)

由式(6)還可得:

整理得:

(2z-a2)m-2mk+a2x=0

(8)

投影點(diǎn)P0(m,n,k)坐標(biāo)滿(mǎn)足雙曲拋物面方程

b2m2-a2n2-a2b2k=0

(9)

聯(lián)立式(7)～式(9)式得方程組。

由式(9)得:

k=m2/a2-n2/b2

(10)

將式(10)代入式(8)式得:

(a2-2z)m+2m(m2/a2-n2/b2)-a2x=0

整理得:

a2b2(a2-2z)m+2b2m3-2a2mn2-a4b2x=0

(11)

由式(7)得:

將上式n代入(11),并整理得:

(12)

式(12)兩邊同乘以[(a2+b2)m-a2x]2,并整理得:

2(a2+b2)2m5-4a2(a2+b2)xm4+a2[(a2-2z)(a2+b2)2+
2a2x2-2b2y2]m3-a4(a2+b2)(3a2+b2-4z)xm2+
a6(3a2+2b2-2z)x2m-a8x3=0

(13)

式(13)是關(guān)于m的一元五次方程。節(jié)點(diǎn)初始位置P(x,y,z)在馬鞍地形表面上的投影點(diǎn)有可能有多個(gè)。如圖3中P(x,y,z)有2個(gè)投影點(diǎn)P0(m,n,k)與P1(m1,n1,k1)。這時(shí),就取距離節(jié)點(diǎn)初始位置P(x,y,z)更近的投影點(diǎn)作為未知節(jié)點(diǎn)的修正坐標(biāo)。圖3中投影點(diǎn)P0(m,n,k)距離P(x,y,z)更近,所以P0(m,n,k)即為未知節(jié)點(diǎn)的較正位置。

圖3 所求節(jié)點(diǎn)的初始位置垂直投影到馬鞍地形表面

(2)應(yīng)用數(shù)值解方法解關(guān)于m的一元五次方程

(a)根的搜索

將式(13)轉(zhuǎn)換為標(biāo)準(zhǔn)方程(m5的系數(shù)為1):

m5+a2m4+b2m3+c2m2+d2m+e2=0

(14)

若有方程:

f(x)=xn+a1xn-1+a2xn-2+…+an-1x+an=0

則該方程根的絕對(duì)值(即根模)的上下界有如下結(jié)論:

若a=max{ |a1|,|a2|,…,|an| },則方程的根的絕對(duì)值小于a+1

對(duì)式(14)有:

aa=max{|a2|,|b2|,|c2|,|d2|,|e2| }

式(14)的根的絕對(duì)值小于(aa+1),則根的搜索區(qū)間為:

分析表3和圖4可以得出，應(yīng)用了RANSAC算法后，擬合結(jié)果與理論值更加接近，且穩(wěn)定性亦有所提高，驗(yàn)證了本文方法的準(zhǔn)確性。從表4及圖5中可以看出，運(yùn)用本文方法與傳統(tǒng)方法擬合耗時(shí)相當(dāng)，但本文方法的魯棒性較強(qiáng)且擬合精度更高。

[-(aa+1),(aa+1)]

設(shè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布范圍是[a,b]。由于我們只需要求出范圍[a,b]內(nèi)的根。因此,如果[-(aa+1),(aa+1)]范圍超出[a,b],則從節(jié)點(diǎn)的分布范圍[a,b]搜索方程的有根區(qū)間。

(b)用二分法求方程(14)的數(shù)值解

方程:f(x)=0,在區(qū)間[a,b]內(nèi)有唯一一個(gè)根。

①準(zhǔn)備:計(jì)算f(a),f(b);

②二分:計(jì)算f((a+b)/2);

③判斷:如果f((a+b)/2)=0,則(a+b)/2為f(x)=0 的根,否則檢驗(yàn):

若f((a+b)/2)·f(a)<0,則方程的根位于[a,(a+b)/2]內(nèi),以(a+b)/2代替b;

若f((a+b)/2)·f(b)<0,則方程的根位于[(a+b)/2,b]內(nèi),以(a+b)/2代替a;

④若|b-a|<ε(ε為精度要求),計(jì)算終止,此時(shí)x*=(a+b)/2;否則轉(zhuǎn)②。

如果方程只有唯一的實(shí)數(shù)根,該數(shù)值解就是所求的初始位置P(x,y,z)在馬鞍地形上的投影,也就是所求未知節(jié)點(diǎn)的二次估測(cè)坐標(biāo)。如果方程有n個(gè)實(shí)數(shù)根,找出n個(gè)根中距離所求出的未知節(jié)點(diǎn)初始位置P(x,y,z)最近的那個(gè)根,即為未知節(jié)點(diǎn)的修正坐標(biāo)。顯然,該節(jié)點(diǎn)的定位精度更高。如果方程無(wú)實(shí)數(shù)根,則所求的初始位置P(x,y,z)就是未知節(jié)點(diǎn)的最終坐標(biāo)。

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)有時(shí)可能會(huì)有極個(gè)別節(jié)點(diǎn)對(duì)應(yīng)的一元五次方程無(wú)實(shí)數(shù)解,這時(shí)就用DV-HOP算法求出的初始位置作為節(jié)點(diǎn)的最終坐標(biāo)。

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

為了檢驗(yàn)算法的性能,在理想的馬鞍地形環(huán)境中,對(duì)經(jīng)典三維DV-Hop定位算法、改進(jìn)的三維DV-Hop定位算法和NLA-ST馬鞍地形定位算法在MATLAB平臺(tái)上進(jìn)行了仿真對(duì)比分析。研究了不同馬鞍地形與定位誤差的關(guān)系、不同錨節(jié)點(diǎn)比例與定位誤差的關(guān)系以及不同通信半徑R與定位誤差的關(guān)系。每次仿真都是在馬鞍地形中均勻隨機(jī)布放200個(gè)節(jié)點(diǎn),馬鞍地形在水平面的投影范圍是100 m×100 m。圖2是一次仿真實(shí)驗(yàn)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)均勻隨機(jī)分布圖。

3.1 不同馬鞍地形的仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)環(huán)境:通信半徑R=40 m,節(jié)點(diǎn)總數(shù)為200個(gè),錨節(jié)點(diǎn)50個(gè),占25%。用雙曲拋物面方程模擬馬鞍地形。改變式(5)中的參數(shù)a和b(設(shè)a=b),分別對(duì)a=5、10、15、20、25、30、35和40進(jìn)行仿真實(shí)驗(yàn)。對(duì)每個(gè)不同參數(shù)a都分別進(jìn)行了50次實(shí)驗(yàn),然后取相對(duì)均方誤差的平均值。每次實(shí)驗(yàn)中未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的坐標(biāo)都是隨機(jī)產(chǎn)生的,實(shí)驗(yàn)結(jié)果如圖4所示。由圖4可知,NLA-ST馬鞍地形定位算法精度明顯高于傳統(tǒng)定位算法。NLA-ST定位算法精度比經(jīng)典三維DV-HOP定位算法平均提高221.5%,比改進(jìn)的三維DV-HOP定位算法平均提高218.5%。經(jīng)典三維DV-HOP定位算法與改進(jìn)的三維DV-HOP定位算法受馬鞍地形參數(shù)的影響很大,且誤差也很大,平均相對(duì)定位誤差分別為116.2%和115.3%,難于滿(mǎn)足實(shí)際定位需要。NLA-ST定位算法精度高,平均相對(duì)定位誤差36.6%,能滿(mǎn)足實(shí)際應(yīng)用的需求。

圖4 不同馬鞍地形的平均相對(duì)誤差曲線(xiàn)

3.2 不同錨節(jié)點(diǎn)比例的仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)環(huán)境:通信半徑R=30 m,馬鞍地形的參數(shù)a=b=20,分別對(duì)錨節(jié)點(diǎn)占15%,25%,35%,45%和50%時(shí)進(jìn)行了仿真實(shí)驗(yàn)。對(duì)不同錨節(jié)點(diǎn)比例的仿真都進(jìn)行了50次,然后取相對(duì)均方誤差的平均值。每次實(shí)驗(yàn)中未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的坐標(biāo)都是隨機(jī)產(chǎn)生的,實(shí)驗(yàn)結(jié)果如圖5所示。由圖5可知,馬鞍地形節(jié)點(diǎn)定位算法精度明顯高于傳統(tǒng)定位算法的精度。錨節(jié)點(diǎn)比例越大,定位精度越高。NLA-ST定位算法精度比經(jīng)典三維DV-HOP定位算法平均提高156.6%,比改進(jìn)的三維DV-HOP定位算法平均提高151.6%。經(jīng)典三維DV-HOP定位算法與改進(jìn)的三維DV-HOP定位算法在馬鞍地形上定位誤差均較大,平均相對(duì)定位誤差分別為85.7%和84.2%,難于滿(mǎn)足實(shí)際定位需要。NLA-ST定位算法精度高,平均相對(duì)定位誤差33.2%,能滿(mǎn)足實(shí)際應(yīng)用的需求。

圖5 不同錨節(jié)點(diǎn)比例的平均相對(duì)誤差曲線(xiàn)

3.3 不同通信半徑的仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)環(huán)境:無(wú)線(xiàn)傳感器節(jié)點(diǎn)總數(shù)200,錨節(jié)點(diǎn)50,錨節(jié)點(diǎn)比例25%,馬鞍地形的參數(shù)a=b=20,分別對(duì)通信半徑R=30 m,35 m,40 m,45 m,50 m,55 m,60 m時(shí)進(jìn)行了仿真實(shí)驗(yàn)。對(duì)每種通信半徑仿真都進(jìn)行50次,然后取相對(duì)均方誤差的平均值。每次實(shí)驗(yàn)中未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的坐標(biāo)都是隨機(jī)產(chǎn)生的,實(shí)驗(yàn)結(jié)果如圖6所示。由圖6可知,3種方法的定位精度與通信半徑關(guān)系不大。NLA-ST定位算法精度明顯高于傳統(tǒng)定位算法的精度。馬鞍地形節(jié)點(diǎn)定位算法精度比經(jīng)典三維DV-HOP定位算法平均提高154.6%,比改進(jìn)的三維DV-HOP定位算法平均提高148.1%。經(jīng)典三維DV-HOP定位算法與改進(jìn)的三維DV-HOP定位算法在馬鞍地形上定位誤差均較大,平均相對(duì)定位誤差分別為82.0%和79.9%,難于滿(mǎn)足實(shí)際定位需要。NLA-ST定位算法精度高,平均相對(duì)定位誤差32.2%,能滿(mǎn)足實(shí)際應(yīng)用的需求。

圖6 不同通信半徑的平均相對(duì)誤差曲線(xiàn)

4 結(jié)束語(yǔ)

經(jīng)典三維DV-HOP定位算法與改進(jìn)的三維 DV-HOP 定位算法在馬鞍地形上定位誤差均較大,而且受馬鞍地形的變化影響較大,無(wú)法滿(mǎn)足實(shí)際應(yīng)用需求。本文研究山區(qū)馬鞍地形上無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的非測(cè)距定位算法。NLA-ST馬鞍地形定位算法利用了馬鞍地形的特點(diǎn),大大提高了節(jié)點(diǎn)定位算法的精度。不論馬鞍地形如何變化,該定位算法的誤差均比較小,完全能滿(mǎn)足實(shí)際應(yīng)用的需要。