胡中棟,謝金偉

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

?

基于山區(qū)地形的無線傳感器網(wǎng)絡(luò)三維定位機制*

胡中棟*,謝金偉

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

針對三維DV-hop無線傳感器定位算法在實際地形中定位時誤差較大的問題,提出了根據(jù)山區(qū)地形的網(wǎng)格數(shù)據(jù)進行較近點投影校正的無線傳感器網(wǎng)絡(luò)非測距三維定位算法。經(jīng)典的三維DV-hop算法求出未知節(jié)點位置后,在該節(jié)點附近搜索3個離該節(jié)點較近且非共線的山區(qū)地形網(wǎng)格上的點,將該節(jié)點向上述3個點確定的面進行投影,投影點即為校正后的未知節(jié)點位置。山區(qū)地形多場景實驗表明,該方法較大幅度減小了定位誤差。

無線傳感器網(wǎng)絡(luò);三維DV-hop;適應(yīng)地形;較近點投影

因人們對數(shù)據(jù)采集的需求越來越大,無線傳感器在當今世界扮演著越來越重要的作用,無線傳感器網(wǎng)絡(luò)也被評為了21世紀最有影響力的21項技術(shù)和改變世界的10大技術(shù)[1]。大部分的無線傳感器不能確定自己的位置[2],所以無線傳感器必須先為自己定位,無線傳感器定位是指傳感器通過輔助條件來確定自己的位置,輔助條件如GPS或其他已知自己位置的傳感器節(jié)點[3]。目前已經(jīng)有許多學者提出了無線傳感器定位算法,如SpotON[4]、APS[5]、MDS-MAP[6]和Constrained 3-D[7]等。程秀芝等人[8]使用了RSSI差分校正的方法提高了最小二乘-擬牛頓定位算法的定位精度;喬欣等人[9]使用了跳距修正的方法提高了WSN擬牛頓迭代定位算法的精度;陳嘉興等人[10]采用了三維序列內(nèi)心來確定傳感器的位置,較有效的提高了定位精度。以目前的條件來看,非測距的定位方法所能提供的條件有限,定位精度已經(jīng)達到了一個瓶頸,只有充分利用外在條件,才有可能較大幅度的提高算法的定位精度。本文結(jié)合實際地形的網(wǎng)格數(shù)據(jù)提出了基于較近點投影校正的無線傳感器網(wǎng)絡(luò)三維定位算法,有效的利用了地形信息,提高了定位精度。

基于山區(qū)地形的無線傳感器網(wǎng)絡(luò)三維定位方法:根據(jù)實際山區(qū)地形的網(wǎng)格數(shù)據(jù),應(yīng)用較近點投影的方法來修正經(jīng)典DV-hop算法的定位精度。在三維DV-hop定位算法求解結(jié)果的基礎(chǔ)上進行較近點投影修正來減小定位誤差。若P點為三維DV-hop的定位結(jié)果,根據(jù)網(wǎng)格的疏密度確定一個以P點為中心的局部搜索區(qū)域,在該區(qū)域內(nèi)尋找離P點最近且不共線的3個網(wǎng)格上的點P1、P2、P3,由這3個點確定一個平面M,將P點垂直投影到平面M上,得到投影點P′,P′就是P點經(jīng)過最近點投影修正后的位置。由于傳感器是部署在地形表面上的,如果經(jīng)典三維DV-hop算法所定位出P′點不在地形表面,則一定是偏離了實際位置。經(jīng)過本算法的投影,無線傳感器的位置最大程度的接近了地形表面,能夠較大幅度的提高傳感器的定位精度。

1 三維DV-hop算法

1.1 DV-hop算法

Niculescu D[11]等人提出了DV-hop算法,該算法是通過距離矢量路由原理來實現(xiàn)的[7]。無線傳感器網(wǎng)絡(luò)中的所有節(jié)點泛洪交換信息,每一個節(jié)點計算出到其他所有節(jié)點的最小跳數(shù)。所有錨節(jié)點通過GPS確定自身的位置,錨節(jié)點根據(jù)到其他錨節(jié)點的最小跳數(shù)計算出自身平均每跳距離。未知節(jié)點根據(jù)到錨節(jié)點的最小跳數(shù)和最近錨節(jié)點的平均每跳距離得出到所有錨節(jié)點的距離。

最小二乘法(極大似然估計法)計算自身坐標過程如下[12]:

若未知節(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)

由式(2)求出的X=(x,y,z)T就是未知節(jié)點的估算坐標。

1.2 性能評價

相對定位誤差是用來評價算法性能的主要方法[13]:

未知節(jié)點的估算坐標(xi,yi,zi)和實際坐標(ai,bi,ci)的差距Δdi如式(3)所示。

(3)

無線傳感器網(wǎng)絡(luò)中的n個未知節(jié)點的平均定位誤差Δ可表示為:

(4)

式中R表示傳感器的通信半徑。

2 較近點投影校正的三維定位算法

較近點投影校正的過程如圖1所示,若經(jīng)典三維DV-hop定位某個未知點的位置為P。根據(jù)P點對應(yīng)的x和y坐標確定一個搜索區(qū)域,在該區(qū)域中搜索離P點最近且不共線的3個點P1,P2,P3,從全局來看P1,P2,P3這3個點不一定是離P點是最近的,但這3個點所形成的面已經(jīng)能夠較好的逼近地形表面。因為P1,P2,P33點不在一條直線上,故可以確定一個平面。過P點向該平面垂直投影,所得的投影點P′即為P點經(jīng)過較近點投影修正后的位置。

圖1 近似投影方法

設(shè)地形的網(wǎng)格數(shù)據(jù)在xoy面的投影是x,y以步長為l所構(gòu)成的m×n個小正方形。經(jīng)典三維DV-hop算法定位某個位置節(jié)點的位置為P,其坐標為(a,b,c),則可以確定局部搜索區(qū)域為:

(5)

若P點靠近地形網(wǎng)格數(shù)據(jù)的邊緣,則不能滿足式(5)所約束的正方形區(qū)域,此時可將搜索區(qū)域向邊界的反方向擴展。例如,若a-5l已經(jīng)超出邊界范圍超過l,設(shè)邊界數(shù)值M,有M-l

(6)

P點處于其他邊界位置可仿照式(6)進行處理,這樣可以保證搜索在5×5的網(wǎng)格區(qū)域內(nèi)進行,保證投影的可靠性。

首先在區(qū)域內(nèi)尋找與P點距離最近的點P1,設(shè)其坐標為(x1,y1,z1)。然后距離次近的點P2,設(shè)其坐標為(x2,y2,z2)。最后尋找P1,P2點外距離最近的點P3,坐標為(x3,y3,z3),若P1,P2,P33點不共線,則得到搜索結(jié)果,否則繼續(xù)搜索下一個,直到搜索到不共線的3點P1、P2、P3。

因P1,P2,P33點不共線,可求得過P1,P2,P33點的平面為:

Ax+By+Cz+D=0

(7)

式中:

A=y1z2-y1z3-y2z1+y2z3+y3z1-y3z2

B=-x1z2+x1z3+x2z1-x2z3-x3z1+x3z2

C=x1y2-x1y3-x2y1+x2y3+x3y1-x3y2

D=-x1y2z3+x1y3z2+x2y1z3-x2y3z1-x3y1z2+x3y2z1

P′點即為P經(jīng)過較近點投影校正后的定位結(jié)果。

3 仿真實驗

用MATLAB對較近點投影校正算法進行了模擬實驗,兩組實驗中的計算公式和繪圖的數(shù)據(jù)都以10 m為一個單位。為了驗證算法的有效性,選擇了兩個較典型的場景進行模擬實驗,一個采用山頭地形的網(wǎng)格數(shù)據(jù)進行實驗,另一個則采用有不同高度山頭、山溝和平地的復(fù)雜地形進行實驗。用3種無線傳感器網(wǎng)絡(luò)節(jié)點定位算法進行了對比實驗,分別為經(jīng)典的三維DV-Hop定位算法、基于平均跳距修正的三維DV-Hop定位算法和本文提出的較近點投影校正算法。

圖2 山頭地形傳感器節(jié)點隨機分布圖

3.1 山頭地形實驗

對式z=10e-((x/5)2+(y/5)2)網(wǎng)格化模擬山頭地形,本實驗僅在式中高度為[10e-1,10]的區(qū)域進行布點,模擬高度約為63.2 m的模擬山頭場景。實驗中無線傳感器節(jié)點的通信半徑設(shè)為20 m,實驗分為不同錨節(jié)點比例和不同節(jié)點總數(shù)進行,隨機布點實例如圖2所示。

①山頭地形不同錨點比例實驗

傳感器總節(jié)點數(shù)設(shè)置為200,錨節(jié)點的比例取5%、10%、15%、20%、25%、30%和35%進行實驗,每組實驗進行100次,實驗結(jié)果取平均值,每次實驗均隨機布點。由圖3的實驗結(jié)果可以看到,山頭地形中當錨節(jié)點比例大于15%時,定位誤差的變化幅度已經(jīng)較小了。

圖3 山頭地形不同錨節(jié)點比例的平均定位誤差

②山頭地形傳感器節(jié)點數(shù)不同的實驗

錨節(jié)點比例固定為10%,實驗在節(jié)點總數(shù)分別為170、180、190、200、210、220和230的情況下進行,每組數(shù)據(jù)進行100次實驗,結(jié)果取平均值,每次均隨機布點。通過圖4可以看到,隨著節(jié)點的增加,定位精度更高。

圖4 山頭地形不同節(jié)點總數(shù)的平均定位誤差

3.2 復(fù)雜地形實驗

對式z=3(1-x/4)2e-(x/4)2-(y/4+1)2-10[x/10-(x/4)2-(y/4)5]e-(x/4)2-(y/4)2-(1/3)e-[(x/4)+1]2-(y/4)2網(wǎng)格化模擬復(fù)雜地形,在式中x,y范圍為24×24的區(qū)域內(nèi)進行實驗,即在240 m×240 m的復(fù)雜地形中進行實驗。實驗中無線傳感器節(jié)點的通信半徑設(shè)為40 m,實驗分為不同錨節(jié)點比例和不同節(jié)點總數(shù)進行,隨機布點實例如圖5所示。

①復(fù)雜地形不同錨點比例實驗

傳感器總節(jié)點數(shù)設(shè)置為300,錨節(jié)點的比例取5%、10%、15%、20%、25%、30%和35%進行實驗,每組實驗進行100次,實驗結(jié)果取平均值,每次實驗均隨機布點。圖6顯示,在復(fù)雜地形中錨節(jié)點比例大于10%時定位誤差相似,所以實際應(yīng)用中可以將錨節(jié)點比例設(shè)為10%。

②復(fù)雜地形傳感器節(jié)點數(shù)不同的實驗

錨節(jié)點比例固定為10%,實驗在節(jié)點總數(shù)分別為270、280、290、300、310、320和330的情況下進行,每組數(shù)據(jù)進行100次實驗,結(jié)果取平均值,每次均隨機布點。圖7顯示,當節(jié)點總數(shù)大于290時,定位精度趨同。

圖5 復(fù)雜地形傳感器節(jié)點隨機分布圖

圖6 復(fù)雜地形不同錨節(jié)點比例的平均定位誤差

圖7 復(fù)雜地形不同節(jié)點總數(shù)的平均定位誤差

4 總結(jié)

通過對比實驗可以看到本文設(shè)計的較近點投影校正的無線傳感器網(wǎng)絡(luò)三維定位算法不僅在常規(guī)的山頭環(huán)境中能夠有效的提高定位精度,在復(fù)雜地形中也有較好的表現(xiàn)。用最近點投影的方法有效的利用了地形的網(wǎng)格數(shù)據(jù),使得定位精度有大幅度提高。因?qū)嶒炇窃诓煌匦蔚木W(wǎng)格數(shù)據(jù)下進行的,能夠較真實的模擬實際地形環(huán)境,具有較大的實際應(yīng)用價值。

[1]張國清,王敬華. 基于畫圖算法的WSN節(jié)點定位算法[J]. 計算機工程,2009,35(20):25-27.

[2]Zhao F,Shin J,Reich J. Information-Driven Dynamic Sensor Collaboration[J]. IEEE Signal Processing Magazine,2002,19(2):68-77.

[3]Ma Zuchang,Sun Yining,Mei Tao. Summary for Wireless Sensor Network[J]. Journal of China Institute of Communications,2004,25(4):114-124.

[4]Hightower J,Boriello G,Want R. SpotON:An Indoor 3D Location Sensing Technology Based on RF Signal Strength[C]//Technical Report UW CSE 2000,Seattle:Department of Computer Science and Engineering. University of Washington,2000:452-463.

[5]Nicolescu D,Nath B. Ad-Hoc Positioning Systems(APS)[C]//Proc of the 2001 IEEE Global Telecommunications Conf. Vol.5,San Antonio:IEEE Communications Society,2001:2926-2931.

[6]Shang Y,Ruml W,Zhang Y,et al. Localization from Mere Connectivity[C]//Proc of the 4th ACM Int’l Symposium on Mobile Ad Hoc Networking and Computing. Annapolis:ACM Press,2003:201-212.

[7]Liang J L,Shao J,Xu Y,et al. Sensor Network Localization in Constrained 3-D Spaces[C]//Proceedings of IEEE International Conference on Mechatronics and Automation. USA:IEEE Press,2006:49-54.

[8]程秀芝,朱達榮,張申,等. 基于RSSI差分校正的最小二乘-擬牛頓定位算法[J]. 傳感技術(shù)學報,2014,27(1):123-127.

[9]喬欣,常飛,丁恩杰,等. 基于跳距修正的WSN擬牛頓迭代定位算法[J]. 傳感技術(shù)學報,2014(6):797-801.

[10]陳嘉興,劉志華. 無線傳感器網(wǎng)絡(luò)節(jié)點的三維序列內(nèi)心定位算法[J]. 南京理工大學學報:自然科學版,2011,35(3):371-375.

[11]Niculescu D,Nath B. DV-Based Positioning in Ad Hoc Networks[J]. Journal of Teleconununication Systems,2003,22(1-4):267-280.

[12]嚴筱永,錢煥延,高德民,等. 一種基于多重共線性的三維DV-Hop定位算法[J]. 計算機科學,2011,38(5):37-40,44.

[13]胡中棟,曾珽,肖紅,等. 基于地形改正的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J]. 傳感器與微系統(tǒng),2013,32(6):147-149.

The 3D Localization Mechanism for Wireless Sensor Networks Based on Mountainous Terrain*

HUZhongdong*,XIEJinwei

(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China)

This paper presents a non-dimensional distance wireless sensor network localization algorithm based on closer points projection correction which use the mountainous terrain mesh data for the problem that the localization error is large when 3D DV-hop algorithm is carried out in the actual terrain. After get the location of a node by using 3D DV-hop algorithm,search three points near the location of the node which is non-collinear and on the mountainous terrain mesh and make the node project toward the surface which is determined by the above three points. Projection point is the node’s location after correction. Multi-scene experiments show that this method can greatly reduce the position error.

WSN;3D DV-hop;adapt to terrain;closer points projection

胡中棟(1958-),男,漢族,江西婺源人,江西理工大學教授,碩士研究生導(dǎo)師,主要研究方向為無線傳感器網(wǎng)絡(luò),智能計算,jxhzd@163.com;

謝金偉(1987-),男,漢族,江蘇淮安人,江西理工大學碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò),智能計算。

項目來源:江西省教育廳項目(GJJ10492);國家基金項目(61462034);江西省教育廳自然科學基金項目(GJJ13413)

2014-07-21 修改日期:2014-12-26

C:6150P;7230

10.3969/j.issn.1004-1699.2015.03.019

TP393

A

1004-1699(2015)03-0408-04