基于山區地形的無線傳感器網絡三維定位機制*

胡中棟,謝金偉

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

?

基于山區地形的無線傳感器網絡三維定位機制*

胡中棟*,謝金偉

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

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

無線傳感器網絡;三維DV-hop;適應地形;較近點投影

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

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

1 三維DV-hop算法

1.1 DV-hop算法

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

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

若未知節點的坐標為(x,y,z),已知未知節點到所有錨節點的距離為d1,d2,…dn(n≥4),其對應的錨節點坐標為(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn)。

可得矛盾方程組:

AX=B

(1)

式中:

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

X=(ATA)-1ATB

(2)

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

1.2 性能評價

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

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

(3)

無線傳感器網絡中的n個未知節點的平均定位誤差Δ可表示為:

(4)

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

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

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

圖1 近似投影方法

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

(5)

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

(6)

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

首先在區域內尋找與P點距離最近的點P1,設其坐標為(x1,y1,z1)。然后距離次近的點P2,設其坐標為(x2,y2,z2)。最后尋找P1,P2點外距離最近的點P3,坐標為(x3,y3,z3),若P1,P2,P33點不共線,則得到搜索結果,否則繼續搜索下一個,直到搜索到不共線的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經過較近點投影校正后的定位結果。

3 仿真實驗

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

圖2 山頭地形傳感器節點隨機分布圖

3.1 山頭地形實驗

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

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

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

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

②山頭地形傳感器節點數不同的實驗

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

圖4 山頭地形不同節點總數的平均定位誤差

3.2 復雜地形實驗

對式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網格化模擬復雜地形,在式中x,y范圍為24×24的區域內進行實驗,即在240 m×240 m的復雜地形中進行實驗。實驗中無線傳感器節點的通信半徑設為40 m,實驗分為不同錨節點比例和不同節點總數進行,隨機布點實例如圖5所示。

①復雜地形不同錨點比例實驗

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

②復雜地形傳感器節點數不同的實驗

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

圖5 復雜地形傳感器節點隨機分布圖

圖6 復雜地形不同錨節點比例的平均定位誤差

圖7 復雜地形不同節點總數的平均定位誤差

4 總結

通過對比實驗可以看到本文設計的較近點投影校正的無線傳感器網絡三維定位算法不僅在常規的山頭環境中能夠有效的提高定位精度,在復雜地形中也有較好的表現。用最近點投影的方法有效的利用了地形的網格數據,使得定位精度有大幅度提高。因實驗是在不同地形的網格數據下進行的,能夠較真實的模擬實際地形環境,具有較大的實際應用價值。

[1]張國清,王敬華. 基于畫圖算法的WSN節點定位算法[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]. 傳感技術學報,2014,27(1):123-127.

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

[10]陳嘉興,劉志華. 無線傳感器網絡節點的三維序列內心定位算法[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]胡中棟,曾珽,肖紅,等. 基于地形改正的無線傳感器網絡DV-Hop定位算法[J]. 傳感器與微系統,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-),男,漢族,江西婺源人,江西理工大學教授,碩士研究生導師,主要研究方向為無線傳感器網絡,智能計算,jxhzd@163.com;

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

項目來源:江西省教育廳項目(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