监测煤矿的一种无线传感器网络节点定位算法

2010-12-07 06:04:52霞,孙
传感器与微系统 2010年9期
关键词:跳数煤矿安全距离

薛 霞,孙 勇

(1.西北大学 信息学院,陕西 西安710127;2.北京理工大学电子安全工程系,北京100081)

0 引言

我国煤矿安全技术与装备水平低,事故隐患多。由于无线传感器网络(WSNs)可应用于布线和电源供给困难的区域、人员不能到达的区域和一些临时场合[1~4]。因此,本文将WSNs应用于煤矿安全监测,这将有效地提高了煤矿安全生产的监测水平,并且减少了事故隐患[5]。在煤矿安全监测中,需要知道采集的数据信息所对应的具体区域位置,如对瓦斯突出,只有快速确认瓦斯突出的具体地点,才能及时采取相应的措施,防止事故发生。因此,研究节点定位是WSNs的一项重要支撑技术。

1 WSNs在煤矿安全监测中的基本定位机制

节点定位是依靠传感器网络中少量锚节点的位置信息确定监测区域中其他未知节点的位置坐标,在传感器节点间建立起一定的空间关系。根据节点是否已知自身的位置,把传感器节点分为锚节点和未知节点。在WSNs中,锚节点(anchor node)是已知自身精确的位置,且能够协助未知节点进行定位;未知节点(unknown node)是需要进行定位的节点。在一个节点的通信半径内,直接通信的节点称为邻居节点。一个节点拥有的邻居节点数量称为网络连通度。

根据定位机制的不同,将WSNs自身定位算法分为两类:基于测距(range-based)的定位方法和无需测距(rangefree)的定位方法[6]。前者需要测量未知节点与锚节点之间的距离或者角度信息,然后使用三边测量法、三角测量法或极大似然估计法计算未知节点的位置。后者无需距离或角度信息,仅根据网络的连通性、跳段估算距离等信息来确定节点的位置,具有低功耗、低成本的优势,且不需硬件支持[7,8]。NiculescuD等人提出的DV-Hop节点定位算法[9,10]不需要提供额外的硬件,节点间的通信量低。在煤矿中,WSNs节点通常按需随机分布,因此,节点的分布不均匀,且不能保证节点的密度。故在煤矿安全监测中,采用DV-Hop节点定位算法是一个可选的方案。本文通过对DV-Hop算法的进一步改进,使得改进后的DV-Hop节点定位算法成为煤矿安全监测的一个理想方案。

图1为WSNs的煤矿安全监测区域,阴影节点表示未知节点,空心节点表示锚节点,锚节点个数至少必须是3。未知节点根据附近的锚节点或已定位的未知节点之间的通信,使用某种定位算法计算自己的坐标位置。

图1 无线传感器网络中煤矿监测的的锚节点和未知节点Fig 1 Anchor nodes and unknown nodes of WSNs for coal mine safety monitoring

2 DV-Hop算法及其改进

2.1 基本的定位算法

DV-Hop算法,是美国路特葛斯大学(Rutgers University)的Niculescu D等人利用距离矢量路由(distance vector routing)和GPS定位原理,提出的其中一种分布式定位算法,它由3个阶段组成。

第1阶段,利用距离矢量交换协议,使网络中所有节点获得自己到锚节点的跳数(distance in hops)。锚节点向距离自己跳数为1的邻居节点广播自身坐标信息与跳数信息(初始跳数值为0)。接收节点仅记录自己到每个锚节点的最小跳数,然后将跳数值加1,并转发给邻居节点。

第2阶段,获得了其他锚节点坐标信息和它们之间的跳距信息,锚节点计算平均每跳距离,然后,将这个跳距矫正值(correction)广播到网络中。锚节点i的平均每跳距离为

其中,锚节点 i,j的坐标分别为(xi,yi),(xj,yj),hij为锚节点i与j(i≠j)之间的跳数。

锚节点将平均每跳距离广播至网络中,未知节点仅记录接收到的第1个平均每跳距离,并转发给邻居节点。未知节点接收到平均每跳距离后,根据记录的跳数,可以计算出到每个锚节点的距离。

第3阶段,当未知节点获得3个或3个以上锚节点的距离时,利用三边测量法或极大似然估计法计算自身坐标位置。

图1所示的情形推广到了更一般的情况,极大似然估计法是三边测量法的推广。假设有n个锚节点,其位置坐标为(xi,yi)(i=1,2,...,n),未知节点坐标为(x,y),要求锚节点数n≥3;di为第i个锚节点与未知节点间的距离,根据平面内两点间的欧式距离公式,得到以下方程组为

在式(2)中,将前n-1个等式分别减去第n个等式,整理成Ax=b的线性方程组形式。其中

使用标准最小二乘法,求得未知节点坐标x的估计^x。

2.2 改进后的定位算法

DV-Hop算法用锚节点之间的平均每跳距离代替未知节点到锚节点的平均每跳距离,未知节点和锚节点之间的距离用每跳跳距×跳数表示。对未知节点进行定位时,只考虑了离未知节点最近的一个锚节点估计的平均每跳距离,然而单个锚节点估计的平均每跳距离值无法准确地反映整个网络的实际平均每跳距离。为了减小误差、进一步提高定位精度,对上面算法进行了改进。改进后的定位算法由以下4个步骤组成:

1)通过路由协议,每个锚节点采用广播方式,将其锚节点的位置、跳数以及到锚节点的每跳距离和广播给其他节点。当某个锚节点接收到其他锚节点的信息时,便可根据两者的位置计算出两者之间的实际距离。根据实际距离与每跳距离和的差值,计算锚节点i,j之间的总距离误差校正值Eij。

设锚节点i的平均每跳距离为HopDisi,锚节点i,j(i≠j)之间总共有n跳,dij表示锚节点 i,j间的每跳距离和,Dij表示锚节点i,j间的实际距离。计算总距离误差校正值Eij

其中,dij=HopDisi×n ,

2)各个未知节点到锚节点的距离不同,距离误差也不同。因此,应该采用不同的误差校正值进行计算。设锚节点i,j间的跳数为n,计算i到j的平均每跳误差校正值eij

各个锚节点在网络中广播自己到其他锚节点的跳数和距离误差校正值。因此,锚节点获得了其他所有锚节点的总距离误差校正值和平均每跳误差校正值。每个接收到此数据的节点将此信息记录到一张表中,然后继续向其邻居广播(重复的数据包丢弃)。经过了总距离误差校正和平均每跳误差校正后,意味着找到了一条到达锚节点的更短路径。

3)经过步骤1和步骤2的广播,未知节点得到了距离自己最近的3个锚节点的距离误差校正值,利用这些校正值,获得自己到锚节点的距离和计算自己到各个锚节点的实际距离。

设未知节点u在锚节点i与j之间,N表示未知节点u到锚节点i的跳数,未知节点u到锚节点i的每跳距离和用HopDisi×N表示,eij表示i到j的平均每跳误差校正值(公式(4))。计算未知节点u到锚节点i的实际距离Dui为

4)利用三边测量法计算自己的位置坐标。

通过以上的改进算法,邻居节点只接收节点转发的一个具有最小跳数的信息,同时丢弃其他节点的转发信息。因此,丢弃的这些节点无法进行定位计算,从而减少了平均定位误差。

3 仿真实验

利用Matlab7.0对DV-Hop算法和本文算法进行了仿真实验。假设某一煤矿安全监测局部无线传感器网络区域为200m×200m的正方形区域,随机分布400个节点,其中,锚节点数为30,节点通信距离为15 m。每种性能的仿真都随机运行20次,然后取其平均值。

3.1 锚节点数与平均定位误差

在仿真区域内随机分布了400个节点,如图2所示,锚节点数量较小时,误差较大;锚节点数增加后,定位误差快速降低。仿真结果显示,在锚节点数量较少的情况下,平均定位误差大约降低了30%。改进算法的平均定位误差小于DV-Hop算法,因为改进算法随着锚节点数的增加,节点的距离误差得到了校正。

图2 锚节点数与平均定位误差Fig 2 Number of anchor nodes and average localization error

3.2 锚节点数与定位覆盖

DV-Hop定位算法和改进算法的覆盖率如图3所示。随着锚节点数的增加,改进算法的定位覆盖范围快速达到了100%。在DV-Hop算法中,当锚节点数较少时,有的节点由于不能找到至少3个锚节点,故不能用三边测量法计算坐标位置,因此,覆盖率只有63%左右。从图中可以看出:改进算法在定位覆盖率方面明显高于DV-Hop算法。

图3 定位覆盖率Fig 3 Localization coverage rate

3.3 锚节点数与通信量

在仿真区域内随机分布了400个节点,如图4所示,随着锚节点数的增加,2种算法的数据包总量都增大,但改进算法的增长低于DV-Hop算法,是因为不可定位节点没有参与计算,从而大大降低了节点之间的通信开销。

图4 锚节点数量与数据包总量Fig 4 Number of anchor nodes and total quantity data pack

3.4 节点数与平均定位误差

在仿真区域内,随机分布了1000个节点,取30个为锚节点。在不同节点数的情况下,观察DV-Hop算法和改进算法的平均定位误差。如图5所示:本文算法的平均定位误差小于DV-Hop算法。在节点数量为1000的情况下,本文算法的定位误差大约是DV-Hop算法的55%左右。平均定位误差降低,是因为本文算法中的不可定位节点不会参与定位计算。

图5 节点数与平均定位误差Fig 5 Number of nodes and average localization error

4 结论

本文介绍了一种改进后的WSNs节点定位算法。实际距离用节点间的跳数×平均每跳距离代替,通过引入距离误差校正值,并且考虑了跳数的影响,同时在路径上实行距离校正,实现了节点的精确定位。改进后的DV-Hop算法不仅降低了平均定位误差,同时也提高了定位覆盖率。仿真实验证明了该方法的有效性。这种新的WSNs节点定位方法解决了类似煤矿这种场景的定位需求,为煤矿的瓦斯突出问题提出了一种新的理想解决方案。

[1]Akyildiz IF,Su W,Sankarasubramaniam Y,et al.A survey on sensor networks[J].IEEE Communications Magazine,2002,40(8):102-114.

[2]尚志军,曾 鹏,于海斌.无线传感器网络节点定位问题[J].计算机科学,2004,31(10):35-38.

[3]Langendoen K,Reijers N.Distributed localization in wireless sensor networks:A quantitative comparison[J].Computer Networks,2003,43(4):499-518.

[4]Sohrabi K,Gao J,Ailawadhi V,et al.Protocols for self-organization of a wireless sensor network[J].IEEE Personal Communications,2000,7(5):16-27.

[5]杨 维,冯锡生,程时昕,等.新一代全矿井无线信息系统理论与关键技术[J].煤炭学报,2004,29(4):506-509.

[6]He T,Huang C D,Blum B M.Range-free localization schemes in large scale sensor networks[C]∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking.San Diego:ACM Press,2003:81-95.

[7]王福豹,史 龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868.

[8]彭 刚,曹元人,孙利民.无线传感器网络节点定位机制的研究[J].计算机工程与应用,2004,40(35):27-29.

[9]Niculescu D,Nath B.Ad Hoc positioning systems[J].IEEE Communications Society,2001,5:2926-2931.

[10]Niculescu D,Nath B.DV-based positioning in Ad Hoc networks[J].Journal of Telecommunication Systems,2003,22(1/4):267-280.

猜你喜欢
跳数煤矿安全距离
强化忧患意识,推动全国煤矿安全生产形势持续稳定向好
算距离
抓煤矿安全基础建设四大支柱
劳动保护(2018年8期)2018-09-12 01:16:08
基于RSSI比例系数跳数加权的DV Hop定位算法
科技风(2017年10期)2017-05-30 07:10:36
跳数和跳距修正的距离向量跳段定位改进算法
经典路由协议在战场环境下的仿真与评测
每次失败都会距离成功更近一步
山东青年(2016年3期)2016-02-28 14:25:55
关于煤矿安全事故责任追究问题的思考
爱的距离
母子健康(2015年1期)2015-02-28 11:21:33
水下无线传感网络路由性能参数研究
科技资讯(2014年26期)2014-12-03 10:56:56