分享到:

研发图
联络我们 | 访客留言 |
论 文 专 利 著 作 项 目 ZigBee 与 Uwb动态 技术FAQ
 
 

 

WSN中一种基于移动信标检测的定位算法

金纯1,2, 王升刚1, 尹远阳1
(1.重庆邮电大学 无线传输技术研究所,重庆 400065;2. 重庆金瓯科技发展有限责任公司,重庆 400041)
该论文发表于《传感器与微系统》2014年第33卷第2期
刊号为:ISSN 1001-3695

摘要:信标节点在无线传感器网络定位技术中起着重要的作用,它作为参考节点决定着被定位目标的位置。在无线传感器网络的实际环境应用中,信标节点可能会因为各种原因发生移动成为不可靠的信标节点,此时依赖不可靠信标节点来定位的未知节点将可能产生较大的定位误差,甚至失去了利用价值。针对信标节点发生移动的问题,提出了一种定位前期的基于可用信标的移动信标检测方案(BAB-BMD)——在节点定位之前,对定位节点收到的所有信标进行检测并对移动信标重定位计算其可靠度。然后,依据信标可靠度选择可用信标用于定位,即基于可用信标的信标择优定位算法(BAB-BOS)。实验结果表明,BAB-BMD具有较好的检测正确度,同时采用BAB-BOS定位算法定位准确度要高于未进行移动信标检测的定位准确度和丢弃移动信标的定位准确度。

关键词:无线传感器网络;移动信标检测;节点定位;信标可信度; 中国分类号:TP277 文献标识码:A







An Algorithm for Localization Based on the Beacon Movement Detection in WSN
Chun Jin 1, 2, Sheng-gang Wang 1, Yuan-yang Yin1

(1. Wireless transmission technology research institute Chongqing University of Posts and Telecommulacations, Chongqing, 400065, China; 2. Chongqing Jinou Science&Technology Development Co., Ltd, Chongqing, 400041, China)


Abstract:Beacon nodes are playing an important role in wireless sensor network localization, which are used as the reference nodes to calculate the target position. But, the unnoticed changes of locations of some beacons may occur because of various reasons in the actual environment of wireless sensor network applications. So, the moved beacons may become unreliable nodes and at this time if we depend on the moved beacon nodes to locate the unknown node may affect the localization accuracy, and even lost the use value. An algorithm of beacon movement detection based on the available beacon was proposed for the problem of beacon movement (BAB-BMD) before localization. This algorithm detects all the beacon nodes and calculates reliability for each beacon which is received by the unknown nodes before the localization. Then select available beacon by the reliability of beacon for localization, which is beacon optimal selection based on the available beacon (BAB-BOS). Experiment results show that BAB-BMD has good detection for beacon movement. At the same time, BAB-BOS also has a better positioning accuracy compared with no detection of beacon movement and discard the moved beacon.

Keywords:wireless sensor network; beacon movement detection; node localization; beacon reliability

1.前言

    在无线传感器网络中定位技术在确定事件发生的位置中起着极其重要的作用。现有的传感器网络常见的定位机制有基于测距的定位方法和无需测距的定位方法,如信号强度定位法、到达时间及时间差定位法、DV-Hop、Amorphous算法等[1][2]。以上所有定位算法都是在网络中信标节点实时位置的可靠度得到保证的前提下,才能定位出未知的节点的可靠坐标。正常情况下信标节点布设完成后其位置并不会发生改变,然而,在类似井下传感网、环保监测传感网环境中可能由于煤矿事故或动物破坏导致某些信标节点位置发生改变。因此,如何在定位之前检测传感网中的移动信标显得十分必要。

    文献[3]提出了无线传感器网络中的信标移动问题,并利用一个功能强大的节点重新设置那些移动过的信标,例如在每个节点上安装GPS。但是,考虑到GPS的价格成本并不适合将其安装到数量庞大的传感器网络中。

    文献[4]中提出了信标移动检测概念(Beacon Movement Detection),并设计了相应的移动信标检测算法。但是该算法由于存在误差传递和判定移动信标的二义性其定位精度并不是很高,并且对移动信标进行丢弃降低了信标节点数量同样会降低定位准确度。文献[5]在以上基础上对文献[4]进行了改进提出了基于区域划分的信标节点移动检测算法和择优定位算法,相对提高了对移动信标的检测正确率和定位准确度。以上算法都是对网络中所有信标进行检测,本文提出了一种更加高效的有选择性的判断信标是否移动的算法——基于可用信标的移动信标检测。

2. 基于可用信标的移动信标检测算法

2.1 可用信标检测的思想

    在传感网络的所有的信标节点布设完成后,每个信标节点依据各自的信号强度,计算出一跳通信范围内与所有信标节点的距离,最终形成整个传感网络的信标节点之间的距离关系矩阵 。未知节点根据自身的通信范围,可以确定 时刻能与之通信的信标节点并形成距离关系矩阵 。然后,从 中选出对应的可用信标原始矩阵 ,依据 和 判断出可用信标节点是否发生移动。该算法相比文献[5]与文献[6]在检测效率和判断准确度上得到了进一步提高。

2.2 基于可用信标的移动信标检测算(BAB-BMD)

    算法的主要流程,首先计算网络初始矩阵作为信标移动检测判定的参考。其次,未知节点发送定位请求并记录传感网络中收到请求的信标节点(可用信标)。然后,形成初始判定矩阵并将初始判定矩阵与网络初始矩阵进行比较,判定出可用矩阵中的移动信标。最后,利用初始矩阵对移动信标进行定位并计算其可靠度。

2.2.1 初始矩阵和判定矩阵的初始化

    初始矩阵即为0时刻信标节点刚刚布设完成后,信标节点之间依据彼此接收到的RSSI值,计算得到的邻居信标之间的距离矩阵,记为 。判定矩阵为网络在t时刻时的可用信标依据RSSI值形成的距离矩阵与对应的初始矩阵之间的差异矩阵。其初始化步骤如下:

    (1)从网络初始矩阵中选择位置节点的可用信标形成未知节点的初始矩阵 ;

    (2)在时刻将检测到未知节点的信标节点之间的RSSI通过路径损耗模型转化成距离监测矩阵 ;

    (3)计算判定矩阵 。将 时刻的监测矩阵减去可用信标的初始矩阵,然后在取绝对值得到判定矩阵如下式所示:

    其中, 为可用信标的个数,矩阵中的每一行为可用信标在 时刻与初始时刻距离的差值。

2.2.2 移动信标检测算法的设计

    可疑移动信标检测:

    定义 为在判定矩阵中判定信标节点是否移动的临界值。根据临界值将式(1)中的信标节点划分为两部分移动信标节点集合和未移动信标节点集合。若 则认为节点 、 的相对位置发生了改变。

    依次对判定矩阵中的所有值进行判定,并记录每一行中值大于 元素的个数。例如第 行元素中有3个元素值大于 ,则记为 。 越大说明信标节点 发生移动的可能性越大。对于可用信标中的每一个信标节点 ,若 ,则判定信标节点 为可疑移动信标,并将其加入可疑移动信标集合 ,其中 , 为节点移动的概率根据文献[5]未知情况下可取0.2。反之,将其加入未移动信标集合 。

    确定可疑移动信标是否为移动信标:

    对于可疑信标采用 和0时刻坐标对比方法进行确认其是否移动。考虑到信号强度不稳定性引起的误判,首先定义 为判定信标是否移动的容忍半径。如果 和0时刻的坐标距离小于 则认为信标没有发生移动,否则信标已经移动。根据集合 中的信标节点是否可以对集合 中节点定位,分两种情况来处理。若 能定位 中信标节点,利用 集合中的信标对 集合中信标进行定位。若 中节点数,无法满足 中节点定位要求,首先根据 中信标节点ID查询0时刻的邻居矩阵,根据式(1)和可疑移动信标检测方法排除可疑信标后在对 中的信标节点进行定位。当 中的信标节点判定完成后,利用可靠度公式分别计算 中信标节点的可靠度。

2.2.3 移动信标检测算法的设计

    信标节点坐标的准确度直接影响着定位的精度,为了减少信标检测过程中产生的定位误差,对每个信标节点计算其可靠度。可靠度的计算分为移动可用信标和未移动可用信标。

    未移动可用信标可靠度的计算:

    式中, 为检测到没有发生移动的信标节点 可靠度; 为判定信标是否移动的容忍半径; 和 分别为可用信标总数和移动信标个数; 和 为未移动信标节点 和 在 和0时刻之间的距离;由式(2)可知信标节点之间距离变化越小可靠度越高,理想情况下可靠度为1。

    移动可用信标可靠度的计算:

    式中, 为移动可用信标节点 的可靠度; 为 时刻移动信标坐标与0时刻坐标的距离; 为参与移动信标定位的未移动信标可靠度 。由式(3)可知,移动距离越大可靠度越低,参与定位的信标节点可靠度越高,最终计算的移动信标的可靠度也越高。

3.基于可用信标移动检测的定位算法

3.1 基于信标可靠度的定位算法设计

    1. 网络初始化后,依据信号传播模型计算 时刻信标节点之间的距离矩阵 。

    2. 未知节点发送定位请求数据包。

    3. 收到定位请求数据包的节点,将其加入可用信标节点集合 , 。

    4. 通过移动信标检测算法检测集合 中的可用信标是否发生移动并计算每个可用信标的可靠度。

    5. 集合 中的可用信标节点周期性的单播发送自身信息数据包,数据包格式如下:


其中,ID为信标节点的物理标识; 为信标节点的坐标; 为信标节点的可靠度;MB为信标节点的移动标志,如何信标节点被检测为移动信标,则 ;否则为0;

    6. 未知节点收到应答请求后,根据收到数据包的信息优先选择其中三个可靠度高的节点作为定位信标节点,并检测三个信标节点是否共线。若共线重新选择保证最终使用的信标节点不共线。然后利用三边测量法计算未知节点的位置。

    7. 检查网络中所有未知可定位节点是否完成定位,若没有继续第三步,直至完成所有可用信标节点的定位。

4.算法的Matlab仿真与分析

    利用Matlab对所提算法进行仿真,为了与文献[5]进行比较,设定传感区域为100*100的二维平面。其中信标节点的数量设定为25个,设定相邻信标节点间距离大于15m并随机布设在传感区域中。信标节点发生移动的概率为 。为了模仿现实环境中的无线传播的不规则性,选用DOI传播模型[7]:


式中, 为平均接收信号功率, 为发送信号功率, 为参考距离 的路径损耗功率, 为路径损耗因子, 为不同传播方向上的路径损耗协同系数,计算方法为[8]:
其中, 为单位方向上最大路径损耗百分比变化程度,仿真时取0.015。

    利用Matlab对所提算法进行仿真,为了与文献[5]进行比较,设定传感区域为100*100的二维平面。其中信标节点的数量设定为25个,设定相邻信标节点间距离大于15m并随机布设在传感区域中。信标节点发生移动的概率为 。为了模仿现实环境中的无线传播的不规则性,选用DOI传播模型[7]:


式中, 为平均接收信号功率, 为发送信号功率, 为参考距离 的路径损耗功率, 为路径损耗因子, 为不同传播方向上的路径损耗协同系数,计算方法为[8]:
其中, 为单位方向上最大路径损耗百分比变化程度,仿真时取0.015。

    由于接收的信号强度,会受到服从高斯分布的噪声的影响,所以距离 处的实际接收信号强度 服从以下分布:

其中, 为高斯分布标准差取值为4到12。因此,由式(4)、(5)、(6)可推算出节点间的估算距离为:

4.1 BAB-BMD算法仿真

    为了探讨BAB-BMD算法在移动信标检测中的性能,根据文献[4]利用检测准确度对算法进行衡量,并与其中的LB、SSB算法在不同信标节点移动比例下进行比较。检测准确度的定义如下:


式中, 为检测准确度; 为可用信标节点总个数; 为信标发生了移动并检测到该信标发生了移动的信标个数;为 信标未发生移动并检测到信标未发生移动的信标个数。

图 1 不同算法间的检测准确度比较

    不同算法的仿真结果如图1所示,可以看出,LB算法的检测准确度最高,而BAB算法的检测准确度在LB和SSB算法之间。当信标节点的移动比例为0.1时三种算法的检测准确度相差不大,但是当移动比例超过0.2时三种算法的检测准确度出现明显差距。这是因为LB算法是通过比较定位前后坐标进行判定,影响准确度的因素只有RSSI引起的定位误差。SSB算法除此之外还存在算法的二义性问题是其检测准确度相对较低的主要原因。BAB算法利用可用信标进行判定,可用信标的距离相距较近RSSI值较稳定,并且判据矩阵相比SSB算法元素减少进一步减少了SSB算法的二义性问题,因此BAB算法具有较好的检测准确度。

4.2 BAB-BOS算法仿真

    可用信标检测的最终目的是用于最终的精确定位。因此,需要对BAB-BOS算法的定位性能进行仿真验证。为了突出算法的性能,以未进行移动信标检测、检测并移除移动信标、检测并定位移动信标三种情况作为对比。

    未进行移动信标检测表示网络中存在一定数量的移动信标,但并不考虑其位置已发生改变,直接利用定位算法对未知节点进行定位。

    检测并移除移动信标表示在定位前,检测可用信标是否发生移动并舍弃发生移动的信标然后在对未知节点进行定位。

    检测并定位移动信标表示在定位前,检测可用信标是否发生移动并对发生移动的信标进行定位,然后计算可用信标的可靠度,最后优先选用可靠度高的节点(BAB-BOS)对未知节点进行定位。

图 2 移动信标比例不同时定位误差

图 3 不同移动比例信标下可定位节点比例

当网络中移动信标的比例不同时,算法的性能如图 2 移动信标比例不同时定位误差、图 3 不同移动比例信标下可定位节点比例所示。由图 2 移动信标比例不同时定位误差可以看出,检测并定位移动信标的平均定位误差相对较低,这是因为移动信标的实时位置得到了更正并充分利用了可用信标。当移动信标的比例较小时三种情况下的平均定位误差相差不大,但随着移动信标的比例不断增大,未进行移动信标检测的平均定位误差急剧增大,这是因为移动信标参与了定位降低了定位精度。由于检测并移除移动信标降低了可用信标的数量但却舍弃了不可靠的移动信标所以平均定位误差处于中间。在图 3 不同移动比例信标下可定位节点比例中由于检测并移除移动信标减少了网络中的信标节点数量,所以随着移动信标节点的比例增加可定位的节点比例逐渐减少。相比其他两种算法由于并未丢弃移动信标,故可定位节点比例并未发生改变。
图 4 不同信标节点数下定位误差

图 5 不同信标节点数下的可定位节点比例

    考虑到信标节点数量对定位的影响,分别作了如图 4 不同信标节点数下定位误差、图 5 不同信标节点数下的可定位节点比例情况下的仿真。在图 4 不同信标节点数下定位误差中可以看出三种情形下的平均定位误差都有所降低,但未进行移动信标的平均定位误差明显高于其余两种情形。当信标节点数目小于35时检测并定位移动信标的平均定位误差明显低于丢弃移动信标的情形,但当大于35时检测并定位移动信标并未有明显优势甚至略高于丢弃移动信标的情形。这是由于检测并定位移动信标需要对移动信标定位此时也会产生一定的误差,当对未知节点定位时会有一定的误差累积,而由于信标节点的数目足够满足定位需求,丢弃个别移动信标并未对定位精确度产生较大影响。

5. 结束语

本文针对无线传感器网络应用中,存在部分位置发生改变的信标节点影响定位准确度的问题,提出了一种基于可用信标移动检测的定位算法(BAB-BMD)并结合此算法设计出一种基于可用信标的信标择优定位算法(BAB-BOS)。仿真实验表明,提出的基于可用信标移动检测的定位算法具有较好的检测准确度。另外,基于可用信标的定位算法的在平均定位误差、可定位节点比例、以及算法的稳定性上同样具有良好的性能。

参考文献
[1] Song W, Wang B, Zhou Y B, Technology and application of wireless sensor network [M]. BeiJing : The Electronics Industrial Publisher , 2007.
[2] 高守玮, 吴灿阳. ZigBee技术实践教程[M]. 第一版. 北京: 北京航空航天大学出版社, 2011: 391-393.
[3] Edwin Olson, John Leonard, and Seth Teller. Robust Range-Only Beacon Localization[J]. IEEE Journal of Oceanic Engineering, 2006, 31(4) : 949-958.
[4] Sheng-Po Kuo, Hsiao-Ju Kuo, Yu-Chee Tseng. The Beacon Movement Detection Problem in Wireless Sensor Networks for Localization Application[J]. IEEE Transaction on mobile computing, 2009, 8(10) : 1326-1338.
[5] 何文秀,夏明,赵小敏等. WSN中信标节点移动情况下的定位方法研究[J]. 小型微型计算机系统,2011,32(11) : 2259-2262.
[6] Sheng-Po Kuo, Hsiao-Ju Kuo, Yu-Chee Tseng. The Beacon Movement Detection Problem in Wireless Sensor Networks for Localization Application[J]. IEEE Transaction on mobile computing, 2009, 8(10) : 1326-1338.
[7] Yuanfang Chen, Lei Shu, Mingchu Li, Ziqi Fan. The Insights of DV-based Localization Algorithms in the Wireless Sensor Networks with Duty-cycled and Radio Irregular Sensors[C]. International Conference on Communications, 2011: 1-6.
[8] 许红艳, 王经卓, 董自健等. MDS-MAP算法在不同传播模型中定位误差的比较[J]. 淮海工学院学报(自然科学版), 2012, 21(1): 15-19.

作者简介:
金纯 (1966—) 博士、教授、研究生导师 主要研究方向:无线通信、计算机软件、物联网等
尹远阳 (1986—) 硕士研究生 研究方向:无线通信,无线传感器网络等 通信地址:重庆市南岸区崇文路重庆邮电大学通信与信息工程学院,无线传输重点实验室,无线传输三班(400065) (尹远阳)