胡中棟,張 康,王振東

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

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

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

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

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

1.1 三維DV-Hop定位算法

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

可得矛盾方程組:

AX=B

(1)

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

X=(ATA)-1ATB

(2)

1.2 性能評價

一般用相對定位誤差來評價算法的性能。

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

(3)

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

(4)

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

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

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

雙曲拋物面方程為:

x2/a2-y2/b2=z

(5)

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

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

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

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

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

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

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

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

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

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

法向量為:

(2b2x,-2a2y,-a2b2)

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

(6)

由式(6)有:

整理得:

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

(7)

由式(6)還可得:

整理得:

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

(8)

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

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é)點初始位置P(x,y,z)在馬鞍地形表面上的投影點有可能有多個。如圖3中P(x,y,z)有2個投影點P0(m,n,k)與P1(m1,n1,k1)。這時,就取距離節(jié)點初始位置P(x,y,z)更近的投影點作為未知節(jié)點的修正坐標。圖3中投影點P0(m,n,k)距離P(x,y,z)更近,所以P0(m,n,k)即為未知節(jié)點的較正位置。

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

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

(a)根的搜索

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

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

(14)

若有方程:

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

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

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

對式(14)有:

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

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

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

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

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

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

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

①準備:計算f(a),f(b);

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

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

若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|<ε(ε為精度要求),計算終止,此時x*=(a+b)/2;否則轉(zhuǎn)②。

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

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

3 仿真實驗

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

3.1 不同馬鞍地形的仿真實驗

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

圖4 不同馬鞍地形的平均相對誤差曲線

3.2 不同錨節(jié)點比例的仿真實驗

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

圖5 不同錨節(jié)點比例的平均相對誤差曲線

3.3 不同通信半徑的仿真實驗

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

圖6 不同通信半徑的平均相對誤差曲線

4 結(jié)束語

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