论文部分内容阅读
摘 要 针对无线传感器网络中DV-Hop经典算法定位精度低的不足，提出了一种改DV-Hop定位算法； 改进后的算法对锚节点的选取进行了优化，并改进节点跳数，还采用平均计算方法计算节点平均每跳距离。仿真表明，改进的DV-Hop算法对未知节点的定位精度有显著提高。
关 键 词 WSN；DV-Hop算法；节点定位
中图分类号：TP393 文献标识码：A 文章编号：1671—7597（2013）032-058-02
1 概述
无线传感器网络（Wireless Sensor Network，WSN）是由一套称为传感器节点的独立装备组合而成，这些传感器节点具有通信、感知、数据处理和存储等功能，并通过无线通信方式形成一个自组织的网络系统。定位是无线传感器网络绝大部分应用中的一个基本问题，主要任务是获得每个节点绝对或相对，精确或近似的位置。
传感器是网络中的基本单位，节点定位是无线传感器网络关键支撑技术之一。无线传感器网络中，节点分为两类：锚节点（anchor node）和未知节点（unknown node），前者向网络广播信标信息（beacon），并且已知自身位置，后者获得与其他节点的距离或者跳数信息，进而根据一定的算法得到位置信息，从而协助未知节点定位。
2 节点位置的计算方法
在获得与锚节点的距离或相关角度信息，并满足节点定位计算条件的基础上，可通过相关定位计算的基本方法来计算出节点位置。计算的基本方法包括：三边测量、三角测量、极大似然估计等。本文以极大似然估计为例，予以介绍。
假如同时定位若干个节点，则构建的完整系统必须有严格的条件限制，形成的方程组条件充分，且拥有唯一的一个解。如图1，已知A1（x1，y1），A2（x2，y2），...An（xn，yn）的位置坐标，它们到D（x，y）的距离分别是d1，d2，...dn，则存在：
可将上式视为线性方程组AX=b，解之得：
得节点D的坐标为：
3 DV-Hop算法分析
DV-Hop（Distance Vector-Hop）通过计算锚节点与未知节点的最小跳数，对平均每跳的距离进行估计，再使用跳段距离代替实际距离来计算未知节点的定位坐标。
DV-Hop算法分为以下三个阶段：
1）计算跳数信息。
锚节点向网络广播信标信息，信标在网络中以泛洪（flooding）的方式传播出去，当信标被转发一次，跳数就增加1跳。通常接收节点在收到的信标中只保存具有最小跳数的信标，为的是所有节点都获得每一个锚节点的最小跳数值。
2）估算网络中平均每跳的距离。
网络平均每跳距离的计算可利用式（1），以每个锚节点获得其他锚节点位置及相距跳数为前提，再将计算结果作为一个校正值（correction）广播至网络中。
其中（xi，yi），（xj，yj）为锚节点i，j的坐标，hj为锚节点i和j（ij）之间的跳数。
校正值在网络中传播时采用可控泛洪（controlled flooding），未知节点在计算与锚节点之间的距离时，需根据其接收到校正值和记录的跳数。
3）当未知节点获得与锚节点的距离的数目达到三个及以上时，可利用极大似然估计、三边测量得出节点位置。
DV-Hop定位算法由两次泛洪组成，第一次泛洪中节点获得锚节点的位置信息和离锚节点的最小跳数，在第二次泛洪中将跳数信息转换为距离信息。
4 改进的DV-Hop算法
由于DV-Hop算法对跳数的过于依赖，并且节点随机分布，在锚节点接收跳数值出现障碍的情况下，计算出的平均每跳距离会有较大的偏离，进而造成定位误差加剧。本文从锚节点选取、节点跳数和平均每跳距离进行改进。
4.1 锚节点的优选
在所有网络节点中，锚节点只占很小的一部分，获取其自身的精确位置，可以通过预先制定或GPS定位等方法来实现。由于节点随机分布，对定位精度产生影响的条件还有锚节点的拓扑关系，小的测距误差会带来较大估计误差的情况出现在锚节点共线或近似共线时。
判断锚节点是否共线，可提取锚节点的二维坐标，用一次函数y=kx+b进行拟合，若任何3个锚节点的坐标与拟合直线的距离差Δ小于一个预设的值δ，即认为锚节点共线，则另选锚节点定位。诸多文献表明，锚节点组成的三角形接近等边三角形时，估计误差最小。
4.2 节点跳数的改进
本文希望引进一种机制能夠使节点之间相互跳数更加趋近于真实值。可改变跳数的取值方法，使其以分数值1/4跳递增，而不是以整数值增加。在一个区间范围内，不同的节点可以设为1/4，2/4，3/4，4/4跳。
无线传感器网络常使用超声波或无线电等电磁波信号进行信息分组广播，在空气中电磁波信号传播时由于距离会有衰减，衰减公式为：，其中为距离L处的电磁波喜好强度，为声源的信号强度，为介质系数。信号会随着距离的增大而下降。
在装有信号强度分析模块的传感器节点上，根据信号强度的不同，在接收信息时，比较接收到的信号强度与通信距离四个阀值的信号强度，进而确定跳数值的选取，可以较精确的降低跳数计算带来的误差。
4.3 改进平均每跳距离
加权平均值可以通过记录后的未知节点与锚节点的平均每跳距离获得，并最终计算出未知节点的平均距离。未知节点的平均每跳距离为
Di和Wi分别是第i个锚节点估计的平均跳距离及其加权权重，未知节点收到锚节点的信息个数为n，Ni为未知节点距离锚节点的跳数。经过加权处理之后，未知节点平均每跳距离的估计值与实际值更为接近。
5 仿真实验
模拟试验是为了测试算法的性能，利用MATLAB模拟实验环境对DV-Hop算法和改进算法进行性能仿真对比分析。在实验中，在100 m×100 m的地域范围内分布100个节点，能够获取自身坐标的一小部分节点是锚节点，其他未知节点的位置通过计算得到。仿真从节点误差进行考察。 仿真结果如图2所示，可以看出DV-Hop算法和改进算法的定位误差都随锚节点比率的增大而降低，改进的DV-Hop定位算法与经典算法相比，误差变化率低很多，且锚节点的比率对其影响不大，较为平稳。
为了比较两种算法的耗费与性能，采用交換的锚节点个数作为衡量标准。通过仿真经典DV-Hop算法与改进DV-Hop算法随临近锚节点变幻的耗费趋势，如图3。可以看出，随着锚节点的增加，交换的锚节点都随之增长。改进算法交换锚节点数明显少于经典算法。
6 结束语
本文介绍了WSN的概况，并对两种位置估计法和DV-Hop定位算法的原理进行了介绍，分析该算法的劣势和缺点，从三个方面对算法进行了改进。凭借仿真实验可以看出，改进后的算法在定位误差方面优于传统的DV-Hop算法。
参考文献
[1]Angelo Cenedese，Giulia Ortolan，Marco Bertinato.Low-Density Wireless Sensor Networks for Localization and Tracking in Critical Environments[J].IEEE Transactions on Vehicular Technology，2010，59（6）：2951-2962.
[2]Martin R K，Chunpeng Yan，Fan H H，et al.Algorithms and Bounds for Distributed TDOA-Based Positioning Using OFDM Sig-nals[J].IEEE Transactions on Signal Processing，2011，59（3）：1255-1268.
[3]杨强，王中杰.大规模无线传感器网络定位算法研究[J].传感器与微系统，2007.
[4]张震，闫连山，刘江涛.基于DV-hop的无线传感器网络定位算法研究[J].传感技术学报，2011，24（10）：1469-1472.
[5]叶小岭，王伟，张颖超，等.无线传感器网络中一种改进的DV-H0p定位算法[J].计算机测量与控制，2010，18（2）：488-490.
[6]GUAN Liang，ZHANG Kai-long，LI Tong-song.Design of WSN location system[J].Electronic Design Engineering，2010，18（5）：84-86.
关 键 词 WSN；DV-Hop算法；节点定位
中图分类号：TP393 文献标识码：A 文章编号：1671—7597（2013）032-058-02
1 概述
无线传感器网络（Wireless Sensor Network，WSN）是由一套称为传感器节点的独立装备组合而成，这些传感器节点具有通信、感知、数据处理和存储等功能，并通过无线通信方式形成一个自组织的网络系统。定位是无线传感器网络绝大部分应用中的一个基本问题，主要任务是获得每个节点绝对或相对，精确或近似的位置。
传感器是网络中的基本单位，节点定位是无线传感器网络关键支撑技术之一。无线传感器网络中，节点分为两类：锚节点（anchor node）和未知节点（unknown node），前者向网络广播信标信息（beacon），并且已知自身位置，后者获得与其他节点的距离或者跳数信息，进而根据一定的算法得到位置信息，从而协助未知节点定位。
2 节点位置的计算方法
在获得与锚节点的距离或相关角度信息，并满足节点定位计算条件的基础上，可通过相关定位计算的基本方法来计算出节点位置。计算的基本方法包括：三边测量、三角测量、极大似然估计等。本文以极大似然估计为例，予以介绍。
假如同时定位若干个节点，则构建的完整系统必须有严格的条件限制，形成的方程组条件充分，且拥有唯一的一个解。如图1，已知A1（x1，y1），A2（x2，y2），...An（xn，yn）的位置坐标，它们到D（x，y）的距离分别是d1，d2，...dn，则存在：
可将上式视为线性方程组AX=b，解之得：
得节点D的坐标为：
3 DV-Hop算法分析
DV-Hop（Distance Vector-Hop）通过计算锚节点与未知节点的最小跳数，对平均每跳的距离进行估计，再使用跳段距离代替实际距离来计算未知节点的定位坐标。
DV-Hop算法分为以下三个阶段：
1）计算跳数信息。
锚节点向网络广播信标信息，信标在网络中以泛洪（flooding）的方式传播出去，当信标被转发一次，跳数就增加1跳。通常接收节点在收到的信标中只保存具有最小跳数的信标，为的是所有节点都获得每一个锚节点的最小跳数值。
2）估算网络中平均每跳的距离。
网络平均每跳距离的计算可利用式（1），以每个锚节点获得其他锚节点位置及相距跳数为前提，再将计算结果作为一个校正值（correction）广播至网络中。
其中（xi，yi），（xj，yj）为锚节点i，j的坐标，hj为锚节点i和j（ij）之间的跳数。
校正值在网络中传播时采用可控泛洪（controlled flooding），未知节点在计算与锚节点之间的距离时，需根据其接收到校正值和记录的跳数。
3）当未知节点获得与锚节点的距离的数目达到三个及以上时，可利用极大似然估计、三边测量得出节点位置。
DV-Hop定位算法由两次泛洪组成，第一次泛洪中节点获得锚节点的位置信息和离锚节点的最小跳数，在第二次泛洪中将跳数信息转换为距离信息。
4 改进的DV-Hop算法
由于DV-Hop算法对跳数的过于依赖，并且节点随机分布，在锚节点接收跳数值出现障碍的情况下，计算出的平均每跳距离会有较大的偏离，进而造成定位误差加剧。本文从锚节点选取、节点跳数和平均每跳距离进行改进。
4.1 锚节点的优选
在所有网络节点中，锚节点只占很小的一部分，获取其自身的精确位置，可以通过预先制定或GPS定位等方法来实现。由于节点随机分布，对定位精度产生影响的条件还有锚节点的拓扑关系，小的测距误差会带来较大估计误差的情况出现在锚节点共线或近似共线时。
判断锚节点是否共线，可提取锚节点的二维坐标，用一次函数y=kx+b进行拟合，若任何3个锚节点的坐标与拟合直线的距离差Δ小于一个预设的值δ，即认为锚节点共线，则另选锚节点定位。诸多文献表明，锚节点组成的三角形接近等边三角形时，估计误差最小。
4.2 节点跳数的改进
本文希望引进一种机制能夠使节点之间相互跳数更加趋近于真实值。可改变跳数的取值方法，使其以分数值1/4跳递增，而不是以整数值增加。在一个区间范围内，不同的节点可以设为1/4，2/4，3/4，4/4跳。
无线传感器网络常使用超声波或无线电等电磁波信号进行信息分组广播，在空气中电磁波信号传播时由于距离会有衰减，衰减公式为：，其中为距离L处的电磁波喜好强度，为声源的信号强度，为介质系数。信号会随着距离的增大而下降。
在装有信号强度分析模块的传感器节点上，根据信号强度的不同，在接收信息时，比较接收到的信号强度与通信距离四个阀值的信号强度，进而确定跳数值的选取，可以较精确的降低跳数计算带来的误差。
4.3 改进平均每跳距离
加权平均值可以通过记录后的未知节点与锚节点的平均每跳距离获得，并最终计算出未知节点的平均距离。未知节点的平均每跳距离为
Di和Wi分别是第i个锚节点估计的平均跳距离及其加权权重，未知节点收到锚节点的信息个数为n，Ni为未知节点距离锚节点的跳数。经过加权处理之后，未知节点平均每跳距离的估计值与实际值更为接近。
5 仿真实验
模拟试验是为了测试算法的性能，利用MATLAB模拟实验环境对DV-Hop算法和改进算法进行性能仿真对比分析。在实验中，在100 m×100 m的地域范围内分布100个节点，能够获取自身坐标的一小部分节点是锚节点，其他未知节点的位置通过计算得到。仿真从节点误差进行考察。 仿真结果如图2所示，可以看出DV-Hop算法和改进算法的定位误差都随锚节点比率的增大而降低，改进的DV-Hop定位算法与经典算法相比，误差变化率低很多，且锚节点的比率对其影响不大，较为平稳。
为了比较两种算法的耗费与性能，采用交換的锚节点个数作为衡量标准。通过仿真经典DV-Hop算法与改进DV-Hop算法随临近锚节点变幻的耗费趋势，如图3。可以看出，随着锚节点的增加，交换的锚节点都随之增长。改进算法交换锚节点数明显少于经典算法。
6 结束语
本文介绍了WSN的概况，并对两种位置估计法和DV-Hop定位算法的原理进行了介绍，分析该算法的劣势和缺点，从三个方面对算法进行了改进。凭借仿真实验可以看出，改进后的算法在定位误差方面优于传统的DV-Hop算法。
参考文献
[1]Angelo Cenedese，Giulia Ortolan，Marco Bertinato.Low-Density Wireless Sensor Networks for Localization and Tracking in Critical Environments[J].IEEE Transactions on Vehicular Technology，2010，59（6）：2951-2962.
[2]Martin R K，Chunpeng Yan，Fan H H，et al.Algorithms and Bounds for Distributed TDOA-Based Positioning Using OFDM Sig-nals[J].IEEE Transactions on Signal Processing，2011，59（3）：1255-1268.
[3]杨强，王中杰.大规模无线传感器网络定位算法研究[J].传感器与微系统，2007.
[4]张震，闫连山，刘江涛.基于DV-hop的无线传感器网络定位算法研究[J].传感技术学报，2011，24（10）：1469-1472.
[5]叶小岭，王伟，张颖超，等.无线传感器网络中一种改进的DV-H0p定位算法[J].计算机测量与控制，2010，18（2）：488-490.
[6]GUAN Liang，ZHANG Kai-long，LI Tong-song.Design of WSN location system[J].Electronic Design Engineering，2010，18（5）：84-86.