基于山区地形的无线传感器网络三维定位机制*

胡中栋,谢金伟

(江西理工大学信息工程学院,江西 赣州 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