论文部分内容阅读
摘要： 对现有基于最小二乘法的DVHop定位算法进行分析和仿真，针对该算法定位精度依赖信标节点之间跳距和跳数这两个信息的不足，给出一种可对信标节点之间的跳距和跳数关系做出误差修正的改进的误差修正DVHop（ECDVHop）算法.仿真结果表明：在相同的室内环境下，ECDVHop算法与传统DVHop算法相比，定位精度得到一定的提高.
关键词： 无线传感器网络； 室内定位； DVHop； 最小二乘法； 误差修正
中图分类号： TN 929.5 文献标志码： A 文章编号： 10005137（2017）01004806
Abstract： In this paper，we analyzes and simulates DVHop algorithms based on the least square estimation frame.The accuracy of the algorithms depends on the information of jump number among beacon nodes.To overcome this drawback，we presents an improved algorithm of error correction DVHop （ECDVHop）.The simulation results show that，in the same indoor environment，the positioning accuracy of ECDVHop algorithm is higher than DVHop algorithm.
Key words： wireless sensor networks； indoor positioning； DVHop； least squares； error correction
0 引 言
随着信息科技的发展，无线传感器网络（WSN）的应用越来越多地跨学科交织、融合.在室内定位应用中，如何用已知定位信息的锚节点（信标节点）来确定该环境下未知节点的信息是目前WSN热门研究课题之一.
WSN定位算法可以分成两类，即基于距离的定位和与距离无关的定位.基于距离的定位算法需要掌握信标节点和未知节点之间任意的一种相互度量关系，如角度、距离、信号强度等，以此来计算未知节点的位置[1]，测距方法包括TOA法、TDOA法、AOA法和RSSI 法[2]；与距离无关的定位算法主要有质心算法、DVHop算法、APIT算法等[3].其中DVHop算法具有部署网络成本低的优点，缺点是精度不够高.[4-6]改进了该算法并取得了一定的效果，但每种改进算法均存在一定的缺陷.
本文作者在DVHop算法的基础上，通过修正信标节点之间的跳数信息和相对距离来提高定位精度，提出了改进的定位算法ECDVHop，并仿真对比了改进算法与DVHop算法的优劣.
1 DVHop定位算法
DVHop算法的基本思想是通过计算平均每跳距离来获取未知节点到信标节点之间的距离，然后使用最小二乘法求出未知节点的位置信息.算法主要分为3个阶段：
1）计算所有未知节点到每个信标节点的最小跳数.每个信标节点向邻节点广播自身的位置信息，每个未知节点都有一张数据表（xi，yi，hi），其中xi和yi是该节点收到的某一个信标节点的坐标，hi是该节点到信标节点的最小跳数.未知节点只有在与邻节点交换信息时才会更新该表.未知节点记录每个信标节点到自身的最小跳数，忽略来自同一个信标节点的较大跳数.然后将跳数值加1并转发给邻节点.通过这个方法，网络中的所有未知节点能够记录其到每个信标节点的最小跳数[4].
2 改进的ECDVHop定位算法
2.1 误差分析
为了实施改进算法，需在定位的第二个阶段增加信标节点转发信息到邻节点的阶段，通过计算整个网络的平均跳距，用（8）式多次迭代计算各个信标节点的平均每跳距离误差，并且将该误差广播至其他信标节点.每个未知节点接收到erri后，继续向其邻节点广播.经过该阶段的多次广播和转发后，所有节点（包括信标节点和未知节点）都已知所有信标节点计算的平均跳距误差，然后再将所有的平均每跳距离误差取平均，误差修正后得到全网的平均每跳距离误差：
当未知节点得到信标节点的估算距离之后，利用（5）式就能算出自己的估计坐标.
3 实验仿真与比较
3.1 迭代次数的选择
根据（8）～（10）式，在100 m×100 m的正方形区域内，随机放置200个传感器节点（包括20个信标节点和180个未知节点），每个节点的通信距离是50 m，k都取0.6，比较多次迭代的效果選出最优迭代次数.当迭代次数为2时，根据全网平均每跳距离得到的定位误差最小，因此选此时的平均距离作为估计距离值，如图2所示.
3.2 k的选择
在ECDVHop算法的式（10）中，k的值影响着定位精度.在实验中，通过改变k（从-1到1，以0.1为间隔）观察其对定位误差的影响，仿真结果如图3所示.由图3可知，当节点总数和信标节点数固定的情况下，定位误差取决于k的值.当k从-1增加到0.6时，定位误差随k值的变大而减小，因此当k=0.6时，定位误差最小，定位精度最高.以下都取k=0.6.
3.3 节点通信距离对定位精度的影响
在实验中，通过改变节点的通信距离来观察其对定位误差的影响，仿真结果如图4所示.从图4可知，在相同的网络环境下，ECDVHop算法的定位误差比 DVHop小，定位误差随着节点的通信距离变大而增大，需找到平均定位误差和通信距离之间的平衡，以下通信距离选为40 m. 3.4 信标节点数对定位精度的影响
定位误差和信标节点数的关系如图5所示，图中的传感器节点总数为300个，其中信标节点为20个.从图5可知，DVHop算法和ECDVHop算法的定位误差都随着信标节点数的增加而减少.ECDVHop算法的误差减少更加显著，因为在ECDVHop算法中，信标节点的覆盖率越高，平均每跳距离更接近于实际每跳距离；随着信标节点数的增加，未知节点到信标节点的跳数减小，定位误差也随之变小.
最后，设置仿真环境为在100 m×100 m的区域内随机放置100个传感器节点，其中包括10个信标节点，通信的平均距离为40 m，进行多遍不同次数的仿真，结果如图6所示.由图6可知，ECDVHop算法的定位误差要明显地小于DVHop算法，通过计算可以得知，ECDVHop算法的平均定位误差为0.2633，DVHop算法的平均定位误差为0.3122，因此改进算法具有一定的精度优势.
4 结 论
分析了DVHop算法的原理和误差并且给出了改进的ECDVHop算法.该改进算法采用加权每跳距离来修正全网平均每跳距离的误差，使其更接近于实际的平均每跳距离.该算法不需要额外的硬件支持.仿真结果表明，改进算法的定位精度优于传统算法.与此同时，改进算法也存在不足，通信量和计算量要高于传统算法，这也导致了更大的算法代价.
参考文献：
[1] Wang L H，Zhang G X，Shen X F.Mobile anchor nodes aided DVhop（MADVhop） algorithm [J].Journal of Hangzhou Dianzi University，2008（5）：312-315.
[2] 林金朝，刘海波，李国军，等.无线传感器网络中DVHop节点定位改进算法研究 [J].计算机应用研究，2009，26（4）：1272-1275.
Lin J C，Liu H B，Li G J，et al.Study for improved DVHop localization algorithm in WSN [J].Application Research of Computers，2009，26（4）：1272-1275.
[3] Brito L A，Liu Y，Garcia Y.An improved error localization on DVHop scheme for wireless sensors networks [J].2010 3rd International Conference on Advanced Computer Theory and Engineering （ICACTE），2010，6：V2-80-V2-84.
[4] Cui H M，Wang Y F，Liu L N.Improvement of DVHOP localization algorithm [C]//IEEE.Identification and Control （ICMIC），Sousse：IEEE，2015.
[5] 彭剛，曹元大，孙利民.无线传感器网络节点定位机制的研究 [J].计算机工程与应用，2004，40（35）：27-29.
Peng G，Cao Y D，Sun L M.Study of localization schemes for wireless sensor networks [J].Computer Engineering and Applications，2004，40（35）：27-29.
[6] Wei Q，Han J，Zhong D，et al.An improved multihop distance estimation for DVHop localization algorithm in wireless sensor networks [C]//IEEE.2012 IEEE Vehicular Technology Conference （VTC Fall），Quebec City：IEEE，2012.
（责任编辑：顾浩然，包震宇）
关键词： 无线传感器网络； 室内定位； DVHop； 最小二乘法； 误差修正
中图分类号： TN 929.5 文献标志码： A 文章编号： 10005137（2017）01004806
Abstract： In this paper，we analyzes and simulates DVHop algorithms based on the least square estimation frame.The accuracy of the algorithms depends on the information of jump number among beacon nodes.To overcome this drawback，we presents an improved algorithm of error correction DVHop （ECDVHop）.The simulation results show that，in the same indoor environment，the positioning accuracy of ECDVHop algorithm is higher than DVHop algorithm.
Key words： wireless sensor networks； indoor positioning； DVHop； least squares； error correction
0 引 言
随着信息科技的发展，无线传感器网络（WSN）的应用越来越多地跨学科交织、融合.在室内定位应用中，如何用已知定位信息的锚节点（信标节点）来确定该环境下未知节点的信息是目前WSN热门研究课题之一.
WSN定位算法可以分成两类，即基于距离的定位和与距离无关的定位.基于距离的定位算法需要掌握信标节点和未知节点之间任意的一种相互度量关系，如角度、距离、信号强度等，以此来计算未知节点的位置[1]，测距方法包括TOA法、TDOA法、AOA法和RSSI 法[2]；与距离无关的定位算法主要有质心算法、DVHop算法、APIT算法等[3].其中DVHop算法具有部署网络成本低的优点，缺点是精度不够高.[4-6]改进了该算法并取得了一定的效果，但每种改进算法均存在一定的缺陷.
本文作者在DVHop算法的基础上，通过修正信标节点之间的跳数信息和相对距离来提高定位精度，提出了改进的定位算法ECDVHop，并仿真对比了改进算法与DVHop算法的优劣.
1 DVHop定位算法
DVHop算法的基本思想是通过计算平均每跳距离来获取未知节点到信标节点之间的距离，然后使用最小二乘法求出未知节点的位置信息.算法主要分为3个阶段：
1）计算所有未知节点到每个信标节点的最小跳数.每个信标节点向邻节点广播自身的位置信息，每个未知节点都有一张数据表（xi，yi，hi），其中xi和yi是该节点收到的某一个信标节点的坐标，hi是该节点到信标节点的最小跳数.未知节点只有在与邻节点交换信息时才会更新该表.未知节点记录每个信标节点到自身的最小跳数，忽略来自同一个信标节点的较大跳数.然后将跳数值加1并转发给邻节点.通过这个方法，网络中的所有未知节点能够记录其到每个信标节点的最小跳数[4].
2 改进的ECDVHop定位算法
2.1 误差分析
为了实施改进算法，需在定位的第二个阶段增加信标节点转发信息到邻节点的阶段，通过计算整个网络的平均跳距，用（8）式多次迭代计算各个信标节点的平均每跳距离误差，并且将该误差广播至其他信标节点.每个未知节点接收到erri后，继续向其邻节点广播.经过该阶段的多次广播和转发后，所有节点（包括信标节点和未知节点）都已知所有信标节点计算的平均跳距误差，然后再将所有的平均每跳距离误差取平均，误差修正后得到全网的平均每跳距离误差：
当未知节点得到信标节点的估算距离之后，利用（5）式就能算出自己的估计坐标.
3 实验仿真与比较
3.1 迭代次数的选择
根据（8）～（10）式，在100 m×100 m的正方形区域内，随机放置200个传感器节点（包括20个信标节点和180个未知节点），每个节点的通信距离是50 m，k都取0.6，比较多次迭代的效果選出最优迭代次数.当迭代次数为2时，根据全网平均每跳距离得到的定位误差最小，因此选此时的平均距离作为估计距离值，如图2所示.
3.2 k的选择
在ECDVHop算法的式（10）中，k的值影响着定位精度.在实验中，通过改变k（从-1到1，以0.1为间隔）观察其对定位误差的影响，仿真结果如图3所示.由图3可知，当节点总数和信标节点数固定的情况下，定位误差取决于k的值.当k从-1增加到0.6时，定位误差随k值的变大而减小，因此当k=0.6时，定位误差最小，定位精度最高.以下都取k=0.6.
3.3 节点通信距离对定位精度的影响
在实验中，通过改变节点的通信距离来观察其对定位误差的影响，仿真结果如图4所示.从图4可知，在相同的网络环境下，ECDVHop算法的定位误差比 DVHop小，定位误差随着节点的通信距离变大而增大，需找到平均定位误差和通信距离之间的平衡，以下通信距离选为40 m. 3.4 信标节点数对定位精度的影响
定位误差和信标节点数的关系如图5所示，图中的传感器节点总数为300个，其中信标节点为20个.从图5可知，DVHop算法和ECDVHop算法的定位误差都随着信标节点数的增加而减少.ECDVHop算法的误差减少更加显著，因为在ECDVHop算法中，信标节点的覆盖率越高，平均每跳距离更接近于实际每跳距离；随着信标节点数的增加，未知节点到信标节点的跳数减小，定位误差也随之变小.
最后，设置仿真环境为在100 m×100 m的区域内随机放置100个传感器节点，其中包括10个信标节点，通信的平均距离为40 m，进行多遍不同次数的仿真，结果如图6所示.由图6可知，ECDVHop算法的定位误差要明显地小于DVHop算法，通过计算可以得知，ECDVHop算法的平均定位误差为0.2633，DVHop算法的平均定位误差为0.3122，因此改进算法具有一定的精度优势.
4 结 论
分析了DVHop算法的原理和误差并且给出了改进的ECDVHop算法.该改进算法采用加权每跳距离来修正全网平均每跳距离的误差，使其更接近于实际的平均每跳距离.该算法不需要额外的硬件支持.仿真结果表明，改进算法的定位精度优于传统算法.与此同时，改进算法也存在不足，通信量和计算量要高于传统算法，这也导致了更大的算法代价.
参考文献：
[1] Wang L H，Zhang G X，Shen X F.Mobile anchor nodes aided DVhop（MADVhop） algorithm [J].Journal of Hangzhou Dianzi University，2008（5）：312-315.
[2] 林金朝，刘海波，李国军，等.无线传感器网络中DVHop节点定位改进算法研究 [J].计算机应用研究，2009，26（4）：1272-1275.
Lin J C，Liu H B，Li G J，et al.Study for improved DVHop localization algorithm in WSN [J].Application Research of Computers，2009，26（4）：1272-1275.
[3] Brito L A，Liu Y，Garcia Y.An improved error localization on DVHop scheme for wireless sensors networks [J].2010 3rd International Conference on Advanced Computer Theory and Engineering （ICACTE），2010，6：V2-80-V2-84.
[4] Cui H M，Wang Y F，Liu L N.Improvement of DVHOP localization algorithm [C]//IEEE.Identification and Control （ICMIC），Sousse：IEEE，2015.
[5] 彭剛，曹元大，孙利民.无线传感器网络节点定位机制的研究 [J].计算机工程与应用，2004，40（35）：27-29.
Peng G，Cao Y D，Sun L M.Study of localization schemes for wireless sensor networks [J].Computer Engineering and Applications，2004，40（35）：27-29.
[6] Wei Q，Han J，Zhong D，et al.An improved multihop distance estimation for DVHop localization algorithm in wireless sensor networks [C]//IEEE.2012 IEEE Vehicular Technology Conference （VTC Fall），Quebec City：IEEE，2012.
（责任编辑：顾浩然，包震宇）