DV-Hop定位算法（精选8篇）
DV-Hop定位算法 篇1
摘要：针对无线传感器网络定位的DV-Hop定位算法定位精度不足, 文中提出了一种改进后的DV-Hop算法。改进后的算法在原基础上引入了均匀量化模型来提高每段跳距的精度和最小二乘法以解决定位过程中造成的累积误差。仿真结果证明, 改进后的算法显著的提高了未知节点的定位精度。
关键词：无线传感器网络,DV-Hop,节点定位
节点定位问题已经成为无线网络传感器的一个重要研究方向。无线网络传感器中, 根据定位过程中是否用到节点间的实际距离, 把定位机制分为:基于测距的 (Range-based) 定位和距离无关的 (Range-free) 定位方法[1]。
Range-based算法需要测量相邻节点间的实际距离, 利用已知节点间的距离和坐标定位出未知节点的位置, 但此定位方法的成本较高。该测距方法有Radio Signal Strength (RSSI) , Time of Arrival (TOA) , Time Difference of Arrival (TDOA) 和Angel of Arrival (AOA) 等。Range-free定位算法则仅利用节点间的距离关联来计算未知节点的位置。定位算法比Range-based算法差, 但成本大幅降低。典型的定位算法有DV-Hop算法[2], Sum-Dist算法, Euclidean算法和基于连通性的定位算法等。
Niculescu等为避免对节点间距离的直接测量而提出了DV-Hop算法。该算法是基于距离矢量计算跳数的算法。该算法的基本思想是, 将待定位节点到已知节点之间的距离用网络中节点平均每跳距离和到已知节点间的跳数乘积来标识, 再使用三边测量法和最大似然估计法来获得待定位节点的位置信息。
由于无线传感器网络[3]中DV-Hop算法的锚节点与未知节点之间的平均跳距估算的误差较大, 容易造成累积误差[4]。由此本文对原有DV-Hop算法进行修改, 提出了一种新的节点位置估计算法。
1 DV-Hop算法的定位过程
DV-Hop的定位算法可以分为3个过程[5,6,7]:
(1) 计算未知节点与每个锚节点的最小跳数。锚节点向邻居节点广播自身位置信息的分组, 其中包括跳数字段, 初始化为0。接收节点记录具有到每个信标节点的最小跳数, 忽略来自同一个信标节点的较大跳数的分组。然后将跳数值加1, 并转发给邻居节点。通过这个方法, 网络中的所有节点能够记录每个锚节点的最小跳数。
(2) 计算未知节点与信标节点的实际跳段距离。每个信标节点根据第一个阶段中记录的其他信标节点的位置信息和相距跳数, 利用式 (1) 估算平均每跳的实际距离
式中, hij为第i个节点到第j个节点间的跳数; (xi, yi) 为第i个节点的坐标; (xj, yj) 为第j个节点的坐标。假设DV-Hop的模型如图1所示。
其中, L1, L2, L3是锚节点;A是一个未知节点;L1, L2, L3这3点之间的距离已知, 分别是30, 50和80。节点L1~L2的距离为30;跳数为4;节点L1到节点L3的距离为50;跳数为4, 根据公式计算节点L1直接每跳的平均距离为[ (30+50) / (4+4) ]=10。同理亦可得L2的平均每跳距离为[ (30+80) / (4+6) ]=11, L3的每跳平均距离为[ (80+50) / (4+6) ]=13。
一个信标节点在计算完与其他各信标节点每跳的平均距离后, 在对邻居节点广播的消息发分组中, 包含了各锚节点的最新信息。这样, 其他节点可以得到锚节点的最新位置信息, 一般是周围相邻节点先得到。在网络中, 位置信息以广播的方式发射, 网络中的节点在收到位置信息时就与原来收到的位置信息进行比较, 如果新收到的位置信息比原来的位置信息更新, 就抛弃原来的位置信息, 将新收到的位置信息储存起来, 这样就可以保证节点只储存1条最新的位置信息。未知节点接收到锚节点的每段平均距离, 再根据式 (2) 可计算得到未知节点到锚节点的距离
其中, hops为未知节点到锚节点之间的最小跳数。
(3) 完成待定节点的位置估计。利用已经得到的数据用三边测量法和极大似然估计法完成位置节点的定位。
DV-Hop定位算法将平均每段的跳距与跳数的距离作为距离的估算值, 所以平均跳距在较大程度上决定了DV-Hop的定位精度。若要误差在合理的估算范围内, 则要求无线网络中节点分布虚密集、均匀。但网络中的节点较少且分布离散时, 就容易造成累积误差。随着跳数的增加, 误差将越来越大。
2 DV-Hop算法的改进
2.1 均匀量化模型
对任意节点i, 假设信号的最大接收功率为Pmax, 最小接收功率为Pmin, 对通讯半径进行量化, 量化的最大等级为M。任意邻居节点为j, 设节点j接收到节点i的功率为Pij, 则通过量化得到的距离信息dij为
这里k为1~M之间的任意整数, p代表最小量化单位, 当M确定后, p是一常数经过上面量化, Pij大的节点所对应的dij值小, 说明信号强度越大, 节点距离越小, 这与实际情况相符。量化后, 将节点i的邻居节点集C划分成M个聚类, 每个聚类里的节点到i的距离量化值相同。其中p由节点的最大发射功率和最小能识别的功率确定。
在RSSI测距中, 距离越近RSSI精度越高, 距离越远时由RSSI值得到的误差则较大, 因此在量化同时可以采取非均匀量化, 对较近的距离采用较小的量化区间, 对较远的距离则采用较大的量化区间。
考虑到算法的复杂性, 文中运用均匀量化模型, 量化后的模型中传统意义上的1跳由多个量化单位取代, 其在某种程度上提高了算法的精确性。
其计算步骤为: (1) 计算节点与每个锚节点的最小累计量化值。锚节点向邻居节点广播自身位置信息和路径序列。其中自身位置信息包括距离量化值字段, 初始化为0, 路径序列只包括自身节点编号。接收节点记录具有到每个锚节点的最小累计量化值, 忽略来自同一个信标节点的较大累计量化值的分组, 同时根据RSSI用式 (3) ~式 (5) 来估计其与上一跳节点间的dij, 计算出k值, 并将结果加入到量化值字段中, 通过这一方法, 网络中每个节点都能记录到锚节点的最小累计量化单位。 (2) 计算未知节点和锚节点的实际跳段距离。每个锚节点根据第一阶段中记录的其他信标节点的位置信息和相距量化单位数, 利用式 (6) 估算平均每个量化单位的实际距离
然后, 锚节点将计算的平均每个量化单位距离用带有生存期字段的分组广播至网络中, 未知节点仅记录接收到的第一个每跳平均距离, 并转发给邻居节点。这个策略确保了大多数节点从最近的信标节点接收到平均每个量化值的距离。未知节点接收到平均每个量化值距离后, 根据记录的量化单位总数, 计算到每个信标节点的跳段距离。
2.2 加权最小二乘法
引入加权最小二乘估计的方法, 即根据每个信标节点的位置精度, 在最小二乘估计中采用不同的加权系数进行定位计算, 以提高定位精度。在一般极大似然估计法的定位过程中, 其一般步骤为:已知锚节点1, 2, 3, 4, …, n的坐标分别为 (x1, y1) 、 (x2, y2) 、 (x3, y3) , …, (xn, yn) , 未知节点A的坐标为 (x, y) 。则根据空间坐标计算
式 (7) 可以写成AX=b, 则
使用标准的最小均方差估计方法可以得到节点A的坐标为:X^= (ATA) -1ATb。锚节点迭代定位可能存在较大定位置误差, 从而在下一轮的定位估计中会引入更大误差, 当网络规模较大时, 累积误差将会无法接受。为解决误差累积问题, 引入加权最小二乘估计的方法, 即根据每个锚节点的位置精度, 在最小二乘估计中采用不同的加权系数进行定位计算, 以提高定位精度。
实际应用中, 加权系数Wi与误差的协方差有关。理论可以证明, 当W取测量值误差方差矩阵的逆矩阵时可使估计误差的方差最小, 但实际应用中如何定义加权矩阵W还有待进一步改善。一般情况下, 当节点间的跳数越大时造成的误差将越大, 所以取的加权值要小一些;而当节点间的跳数较小的造成的误差会变小, 所以取的加权值应大一些。
在此引入一个加权系数Wi, 利用最小二乘法可得未知节点的坐标为
其中, Wi=1/hi, hi为参与定位的锚节点距离未知节点A的最小跳数, 则
2.3 仿真与比较
为检验改进算法的性能, 在Matlab平台上对传统DV-Hop定位算法和改进算法进行性能仿真对比分析, 对算法的性能主要从定位误差方面进行评估。仿真实验网络模型的主要参数如下:网络规模是100个节点, 随机分布在100 m×100 m的地域范围内, 未知节点的坐标随机产生, 节点的通信半径为16 m, 量化最大等级为4。每种算法的仿真进行100次, 取其定位误差的平均值, 其两种算法的定位误差随着参与定位的锚节点个数变化结果如图2所示。
由图可知, 随着参与定位的锚节点个数的增加, 其定位误差越来越小。在锚节点达到20时, 其定位误差的下降率趋于平缓。在其对比中, 改进算法与DV-Hop相比, 其误差百分比有明显的改善, 在锚节点达到30时, 其定位误差减少了12%。
3 结束语
针对无线传感器网络定位中的DV-Hop定位算法中定位精度不足, 提出了均匀量化模型来提高每段跳距的精度并用最小二乘法来解决定位过程中造成的累积误差。仿真结果证明, 该算法在定位精度上有了一定得提高。此处讨论的算法都是停留在仿真试验的基础上, 如何在实际系统中实现, 并检验算法在现实环境中的性能表现也是一个急需实现解决的问题。
参考文献
[1]WANG F B, SHI I, REN F Y.Self-localization systems and algorithms for wireless sensor networks[J].Journal of Software, 2005, 16 (5) :857-868.
[2]NIU Y C, ZHANG S D, XU X Y, et a1.An enhanced DVHop localization algorithm for irregularly shaped sensor networks[C].LNCS 4864, 2007:694-704.
[3]SUN L M, LI J Z, CHEN Y, et a1.Wireless sensor networks[M].Beijing:Tsinghua University Press, 2005.
[4]ZHANG S G, CAO J N, CHEN J, et a1.Accurate and energy-efficient range-free localization for mobile sensor networks[J].IEEE Transactions on Mobile Computing, 2010, 9 (6) :897-910.
[5]刘文远, 王恩爽, 陈子军.无线传感器网络中DV-Hop定位算法的改进[J].小型微型计算机系统, 2011, 32 (6) :1071-1074.
[6]刘明, 包亚萍, 刘汉义.无线传感器网络中一种改进的DVHop算法[J].传感器与仪器仪表, 2009, 25 (4) :128-129.
[7]王颖, 石昊阳.基于DV-Hop的无线传感器网络定位算法[J].仪表技术与传感器, 2012 (4) :97-99.
[8]张新生, 赵衍静, 李海涛.基于DV-Hop定位算法的改进与研究[J].计算机科学, 2011 (2) :76-78, 90.
DV-Hop定位算法 篇2
基于北斗双星的被动定位算法研究
针对我国现有北斗双星定位系统主动定位存在的问题,提出了一种被动定位算法.该算法根据两颗同步卫星、用户配备的原子钟、高程设备等获得卫星到用户的.时间及高程信息,首先将北斗系统的工作区域划分为若干网格,定义了费用函数.然后计算各网格的费用,将具有最小费用的网格及邻域作为下一次搜索的区域,再将该子区域进一步网格化后计算费用函数,经过多次迭代后就可将当前搜索的网格中心作为用户所在位置.最后用电子地图对三维搜索算法可行性进行了仿真,仿真考虑了网格划分方法和电离层误差对结果的影响.结果表明,该算法运算速度快,并且具有较高的定位精度,对现有北斗双星主动定位系统是一种可行的改进算法.
作 者：齐欢 陈迎春 夏爽 QI Huan CHEN Yingchun XIA Shuang 作者单位：华中科技大学控制科学与工程系,武汉,430074刊 名：空间科学学报 ISTIC PKU英文刊名：CHINESE JOURNAL OF SPACE SCIENCE年，卷(期)：26(6)分类号：V4关键词：北斗双星定位系统 被动定位 搜索算法
DV-Hop定位算法 篇3
辅助定位算法假设只有少部分传感器有确定位置通过手动配置或者使用GPS接收器,这些传感器叫做信标节点,可以用它们来估算其他传感器的位置。随着信标节点密度的增加,未知传感器的定位精确度也随之增加。研究表明除信标节点的密度外,恰当地部署信标节点也对定位精确度有影响[3]。
1 定位算法
无线传感器网络定位算法可以分为两类[4]:基于距离的算法Range- Based,如RSSI(Received Signal Strength Indicator)[5]、TOA(Time of Arrival)[6]、TDOA(Time Difference on Arrival)[7]、AOA(Angel of Arrival)[8]和距离无关的算法Range-Free,如DV-Hop(Distance Vector-Hop)算法[9]、凸规划算法[10]和MDS-MAP算法[11]等。前者需要测量相邻节点间的绝对距离或方位,并利用节点间的实际距离来计算未知节点的位置,并且对于传感器需要增加额外的硬件,这使得费用和能量消耗增加;后者无需测量节点间的绝对距离或方位,而是利用节点间的估计距离计算节点位置。
1.1 DV-Hop定位算法
DV-Hop算法的定位过程分为三个阶段[12]:
(1)信标节点向邻居节点广播自身位置信息的分组,其中包括跳数字段,初始化为0。接收节点记录具有到每个信标节点的最小跳数,忽略来自同一个信标节点的较大跳数的分组。然后将跳数加1,并转发给邻居节点。通过这个方法,网络中的所有节点能记录下到每个信标节点的最小跳数。
(2)计算未知节点和信标节点的实际跳段距离。每个信标节点根据第(1)阶段中记录的其他信标节点的位置信息和相距跳数,利用式(1)估算平均每跳的实际距离:
其中,(xi,yi)、(xj,yj)是信标节点i、j的坐标;hj是信标节点i与j(j≠i)之间的跳段数。然后,信标节点将计算的每跳平均距离用带有生存期字段的分组广播至网络中,未知节点仅记录接收到的第1 个每跳平均距离,并转发给邻居节点。这个策(略确保了大多数节点从最近的信标节点接收到每跳平均距离值。未知节点接收到平均每跳距离后,乘以记录的跳数计算到每个信标节点的跳段距离。
(3)利用三边测量法或者极大似然估计法计算自身位置。例如三边测量法如图1所示。
三边测量法已知A、B、C三个节点的坐标分别为(xa,ya)、(xb,yb)、(xc,yc),以及它们到未知节点D的距离分别为da,db,dc,假设节点D的坐标为(x,y)。那么存在下列公式:
由式(2)可以得到节点D的坐标为:
1.2 DV-Hop定位算法的不足
(1)在大型的无线传感器网络中为了节约成本,使用有限处理和微控制的传感器。微控制和微处理不能运行计算复杂的算法,例如三边测量法中需要使用的非线性最小平方问题。因此在DV-Hop定位算法中估算传感器距离时把非线性最小平方问题线性化,再加上能量有限的传感器无法承受接收大量来自信标节点信息时的能量消耗。所有这些因素都阻碍了DV-Hop定位算法定位的精确度和改进。
(2)针对特定的环境例如在稠密的森林,对于这些环境很难在内部部署信标节点,最好的方法就是在这些环境的周界上部署信标节点。
1.3改进的DV-Hop定位算法
改进的DV-Hop定位算法的思想是针对中心区域部署信标节点,这些信标节点能够在监控下均匀部署在中心区域的周界上,最小化洪泛法传播,根据必要的有限信标节点精确定位从而减少能源消耗,三边测量法将用在基站,因为基站可以快速完成NLLS计算和充足的能量保留所有可能到信标节点的距离记录。例如要在茂密的森林里定位追踪某个动物比如熊猫,信标节点部署如图2所示。
改进的DV-Hop算法的定位过程如下:
(1)信标节点向邻居节点广播自身位置信息的分组,其中包括跳数字段,初始化为0。接收节点记录具有到每个信标节点的最小跳数,忽略来自同一个信标节点的较大跳数的分组。然后将跳数加1,并转发给邻居节点。通过这个方法,网络中的所有节点能记录下到每个信标节点的最小跳数。
(2)计算未知节点和信标节点的实际跳段距离。每个信标节点根据第(1)阶段中记录的其他信标节点的位置信息和相距跳数,利用式(1)估算平均每跳的实际距离。在这个阶段不同于DV-Hop定位算法,不再是信标节点根据式(1)估算平均每跳长度后开始第二次洪泛法传播给其他的传感器所估算的平均每跳长度,而是每个信标节点发送他们的估算平均每跳长度给基站,基站保留着一张每跳长度表,包括了每个信标节点的平均每跳长度。
(3)传感器报告监测数据信息给基站,在报告中传感器产生一个新包由两部分组成:报告信息和传感器的跳数表(到每个信标节点的跳数)。传感器先根据跳数表判断找到最近的信标节点,然后通过信标节点按编号位置以就近原则依次转播给基站。如图3所示。
(4)基站定位报告监测数据信息的传感器,用它保留的跳数长度表的记录和收到报告的跳数表的记录进行匹配,然后计算传感器到所有信标节点的距离,最后用三边测量法计算传感器的位置。
2 仿真实验及分析
借助OMNET++网络模拟器,对DV-Hop定位算法和改进的DV-Hop定位算法进行平均定位误差和平均能量消耗性能测试比较。在每个仿真实验中N个传感器随机部署在一个平面中心区域里,以圆形区域为例,M个信标节点均匀的放置在周界上,设定传感器无线通信半径为20 m,N为无线传感器网络面积除以π的平方根,M为N的0.1 倍,分析不同参数对算法性能的影响,仿真次数为20次,用平均值来进行性能测试。
增大无线传感器网络面积,使无线传感器网络面积从0.1km2到20 km2逐渐增大,平均定位误差每2 km2增加,在图4中仿真实验结果表明增大无线传感器网络面积,对于平均定位误差增长率来说改进的DV-Hop定位算法比DV-Hop定位算法低。
增加传感器和信标节点的数量,设定无线传感器网络面积为600 km2,传感器的个数从600到2800增加,平均定位误差每200增加。在图5中仿真实验结果表明随着传感器个数的增加平均定位误差在DV-Hop定位算法中有明显的改变,而在改进的DV-Hop定位算法中没有明显的改变,这也说明改进的DV-Hop定位算法非常适合用在大型中心区域无线传感器网络中。在大型中心区域无线传感器网络中确保精确定位并且能够达到最小化无线传感器个数,这样可以减少部署开销。
增加无线传感器网络面积比较两种定位算法的能量消耗情况。在图6 中仿真实验结果表明随着无线传感器网络面积的增加,能量消耗随之增加,但改进的DV-Hop定位算法能量消耗比DV-Hop定位算法低些,这又更进一步说明改进的DV-Hop定位算法能够适应大型中心区域无线传感器网络。
3 结论
DV-Hop定位算法 篇4
无线传感器网络WSN(wireless sensor network)是由大量静止或者移动的无线传感节点通过Ad-Hoc(点对点)以自组织和多跳的组网方式构成的无线网络[1]。它具有远程监控、实时监测等优点，目前已广泛应用于环境监控、军事防备、交通管理、智能家居[2]等诸多领域。在实际的许多应用中，无线传感网络感知、采集、处理和传输所采集的信息中，若缺少无线传感节点的位置信息，这将使无线传感网络获取的数据信息及后续其他工作的开展显得毫无价值和意义。因此，无线传感器网络的节点定位问题已成为无线传感器网络研究的关键技术之一，也成为不可或缺的研究重点。
目前解决节点定位的问题，根据是否测量节点间的距离主要分为测距法和免测距法[3]两种。测距定位算法估计点对点的位置距离或角度信息来计算待定节点的位置信息，例如有到达时间[4]TAO(Time of arrival)，到达时间差[5]TDOA(Time difference of arrival)，到达角度[6]AOA(Angle of arrival)以及信号接收强度指示[7]RSSI(Received signal strength Indicator)等定位算法，但每种方法均有各自的优势和局限性[8];免测距定位算法采用已知锚节点的位置信息和网络连通度来估算待定节点的位置坐标，例如[9]Centroi,Amorphous,Approximate point-in triangle test(APIT)及Distance vector-hop(DV-Hop)等定位算法，与测距定位算法相比较，免测距定位算法不需要硬件设备的支持，具有成本低，实现算法简单，性价比高等优势备受广大学者的关注和青睐。其中较为典型的DV-Hop算法因硬件成本低、开销小、计算量小等优点成为目前应用最为广泛的定位算法。但DV-Hop算法存在定位精度不高、易受网络拓扑结构的影响、误差较大等缺陷，为此很多学者对其进行了相关改进，文献[10]通过改进锚节点广播数据的分组结构、增加最大转播跳数限制数据分组的广播范围、参考锚节点的平均跳距的误差进行了加权处理及采用改进的粒子群算法优化定位结果等措施做了相关改进，文献[11]采用加权最小二乘估计修正锚节点间的平均跳距、筛选并加权处理未知节点估计的平均跳距、引入粒子群优化算法进行未知节点的定位等处理策略，提出了一种最优跳距定位算法，文献[12]引入前序节点和总平均跳距设计了改进的DV-Hop算法，文献[13]根据向量的移动提出了一种适用于免测距的新的定位算法，文献[14]针对DV-Hop算法精度不高、不适用于不规则网络等缺陷，提出了一种基于对平均跳距和估计距离重新计算的改进算法，文献[15]通过邻近节点重叠度和引入网络平均连通度来计算夹角和节点间跳距，改进了DV-Hop定位算法。但在目前的DV-Hop改进定位算法中，大多仅针对二维平面进行了定位方面的研究，而实际应用中的节点往往部署在三维空间中，因此，研究三维空间的定位更具有实用价值和发展潜力。
文献[16]将免测距的DV-Hop算法拓展到三维空间提出了一种基于移动代理的三维DV-Hop定位算法，文献[17]使用RSS经验衰减模型结合节点间的最短路径，着力于解决WSN节点的三维空间定位问题。但随着三维网络规模、分布密度和定位复杂度的增加，也相应存在通信和计算开销大、定位精度低、覆盖率低等不足。因此，本文针对节点在三维网络空间中的随机分布，通过改进DV-Hop算法并将其拓展到三维空间定位中，采用残差加权及二次规划法，将提高定位精度的问题转化为无约束条件下的最小化求解问题。经过仿真实验，对本文改进方案的性能在相同通信半径、不同锚节点比例的情况下进行了比较和验证。
1 DV-Hop算法
DV-Hop是由Niculescu等人利用距离矢量路由方法提出的一种分布式、逐跳定位的算法[18]，确定锚节点的过程中引入最短路径算法，利用多跳锚节点的位置坐标来估计待定节点的位置坐标。其主要思想分为三步:
(1)计算最小跳数
每个锚节点借助距离矢量交换协议将自身位置信息广播给通信范围内的邻居节点，其中包括锚节点标识id、坐标(xi,yi)、及跳数hopsij(初始为0)。接收到广播信息的节点记录每个锚节点的最小跳数，其中忽略不计来自同一个锚节点的较大跳数，将跳数加1转发给邻居节点，然后继续向新的邻居节点广播信息，舍弃相同id号标识的锚节点信息，依此计算出各节点之间的最小跳数。
(2)计算待定节点与已知锚节点之间的跳距值
各锚节点根据第一步记录其它锚节点的跳数和位置信息，可利用式(1)计算出各锚节点跳距:
式中，(xi,yi)为第i个锚节点的坐标，(xj,yj)为第j个锚节点的坐标，hopsij为第i个锚节点与第j个锚节点的最小跳数(i,j≥3)。
(3)计算待定节点的坐标值
假设待定节点的坐标为(x,y)，第i个锚节点的坐标为(xi,yi)(i=1,2，…，n)，那么可利用式(2)计算出待定节点与各锚节点的距离。
将式(2)前n-1个方程依次减最后一个方程，并化简整理为线性方程AX=b的形式，可得式(3):
若利用最小二乘估计，可得线性方程AX=b残差方程:
求式(4)的一阶导数可得式(5):
令式(5)为0，可得待定位节点坐标式(6):
2 三维DV-Hop改进算法
2.1 三维DV-Hop算法模型
三维DV-Hop定位算法如图1所示，设待定节点坐标为(x,y,z)，第i个锚节点的坐标为(xi,yi,zi)，待定节点到第i个锚节点的距离为di,i≥4。
若引入残差函数为:
其中，ε是n维误差向量。
那么，类似于式(2)，将式(7)经整理可得式(8):
将式(8)整理为线性方程Aθ=b的形式，其中:
因此，为提高定位精度，根据最小二乘法准则，使得残差ε1，ε2，…，εn项的平方和达到最小。显然，残差项ε1，ε2，…，εn达到最小化的问题转化为等式约束条件下二次规划的问题:
为了进一步改进待定节点精度，引入加权系数矩阵w解决上述优化问题。
其中，hopui为待定节点u与第i个锚节点的最小跳数，(i=1,2，…，n)。
将式(9)进一步转化为式(10):
为了同时考虑待定节点坐标θ=[x y zε1…εn]T，可将式(10)进一步转化为无约束条件下的二次规划问题:
其中:
,k>0且为常数，hopui为待定节点u与第i个锚节点的最小跳数(i=1,2，…，n)。
若要上述二次规划问题存在全局最优解，那么要证明其Hessian矩阵必为半正定。其证明过程如下:
将式(11)写为求和形式:
可得Γ的一阶、二阶偏导方程为:
因此，，可证其Hessian矩阵必为半正定，那么上述二次规划问题存在全局最优解。
令，可得全局最优解为式(12):
2.2 三维DV-Hop算法的改进
在节点随机分布的三维无线传感网络中，往往忽略了锚节点自身存在误差的问题，为了减小锚节点产生的误差，更加准确地反映待定节点实际坐标位置，将式(12)中的加权系数矩阵W进一步进行归一化平均处理如式(13)，使得残差ε1，ε2，…，εn项的平方和达到最小，从而待定节点平均跳距的估计更加准确，以便得到更高的定位精度。
其中，u∈(1,2，…，n),hopui为待定节点u与第i个锚节点的最小跳数。W表示待定节点u与第i个锚节点之间的跳数占待定节点u与其余锚节点之间的跳数总和的比重。
式(13)中，将待定节点距离较近的锚节点赋予较大的权值，与之相反，将距离较远的锚节点赋予较小的权值，从而减小待定节点位置坐标估算带来的误差。因此，在一定程度上减小了定位误差，能够更加准确地反映待定节点的实际位置，有效解决了免测距定位算法存在定位精度不高的问题。
3 实验仿真及分析
为了验证和评价本文改进算法的性能，采用Matlab进行了仿真实验。仿真环境设置如下:200个节点随机均匀分布在100 m×100 m×100 m三维空间区域内，分析比较在不同的通信半径与不同锚节点比例条件下的定位性能。
平均定位误差是定位算法中最主要的评价标准，若采用t次实验结果统计，那么归一化平均定位误差作为评价指标为:
其中，为第i个待定节点估计值，(xi,yi,zi)为第i个待定节点实际位置坐标值，N为区域D内的所有节点总数，n为锚节点总数，R为节点的通信半径，t为实验次数。
在不同通信半径R的情况下根据锚节比例随机运行50次，取计算所得的平均值，仿真结果如图2、图3、图4所示。
从图2、图3、图4的仿真结果可以看出，DV-Hop算法和本文IDV-Hop改进算法在同一通信半径的情况下，随着锚节点比例的增加均呈现递减趋势;在同一通信半径、同一锚节点比例的情况下，本文IDV-Hop改进算法的归一化平均误差均小于传统DV-Hop算法，提高了定位精度。在通信半径R=10 m、R=20 m、R=30 m，不同锚节点比例的情况下，本文改进DV-Hop算法的归一化平均误差的对比结果如图5所示。
从图5的的对比结果可以看出，随着锚节点比例、通信半径的增加呈现出递减趋势，基本趋于平稳，并无产生剧烈振荡现象。说明了本文算法是一种可行的三维定位解决方案，并具有良好的稳定性。
4 结语
本文针对DV-Hop算法存在定位精度不高、误差较大等缺陷，对误差产生的残差函数进行了理论分析，并在该算法的基础将其拓展至三维空间定位中，将提高定位精度的问题转化为等式约束条件下的残差项达到最小化的求解问题，采用最小二乘法引入归一化加权系数并利用二次规划法再转化为无约束条件下的最小化求解问题，经过理论分析得到三维DV-Hop改进定位算法的模型。仿真实验结果表明，本文IDV-Hop改进算法相比于DV-Hop算法，在相同通信半径、不同锚节点比例的情况下，明显提高了定位精度且具有良好的稳定性。在后续的工作中，如何尽量减小硬件开销、以及在锚节点分布不均匀的前提下提高定位精度将是需要进一步研究的内容。
摘要：针对无线传感网诸多具体应用中需要节点位置信息的实际需求,提出一种基于残差加权的三维DV-Hop改进定位算法的解决方案。该方案通过引入残差函数将提高定位精度的问题转化为等式约束条件下残差最小化的求解问题,采用最小二乘准则对待定节点与锚节点的最小跳数进行平均加权处理,并利用二次规划法将其最终转化为无约束条件下最小化的问题。经理论分析得出了三维DV-Hop改进定位算法的模型,实现待定节点的坐标估计并提高了定位精度。仿真结果表明,在相同通信半径、不同锚节点比例的情况下,改进三维DV-Hop定位算法的性能得到了明显提高。
DV-Hop定位算法 篇5
DV-Hop算法以锚节点之间每跳平均距离作为未知节点的跳距, 用每跳距与跳数之积表示未知节点与锚节点间的距离。该算法适用于锚节点分布均匀、密集型的无线传感器网络。当节点分布稀疏时, 彼此间的路径不能呈直线趋势, 距离值便会产生很大的累积误差。
2 改进的DV-Hop定位算法
针对上述DV-Hop算法的不足提出了改进的DV-Hop算法。在保证DV-Hop思想的前提下, 当网络拓扑结构形成后, 节点间的跳段数便固定, 通过调节平均距离减少实际距离误差。实验证明, 最少平均定位误差的最优锚节点个数与网络环境参数密切相关。
设初始每个未知节点门限值为N, 计算后得出锚节点的估计距离, 采用极大似然估计法求出未知节点坐标。选择距离较近的锚节点作参考点, 减少计算量, 提高效率, 降低平均定位误差。
针对传统的DV-Hop算法所采用的三边定位方式来获取未知节点的最终位置。该方法对测距误差敏感, 算出的估计坐标与实际存在较大误差。为此本文提出二维双曲线定位算法, 很好的避免这样的误差产生。
3 算法仿真
为了检验改进算法的可行性, 本文对传统DV-Hop定位算法和改进算法在MATLAB平台上进行了仿真对比分析。在一个100m×100m的区域里随机布撒传感器节点, 未知节点和锚节点的坐标也随机产生100次所得。
在实验区域内节点数量从20到100变化, 锚节点比例为20%。通过仿真曲线可以看出, 随着节点数的不断增加, 每种算法的平均定位误差都有所递减。但在相同条件下, 改进算法比原有传统算法平均测距误差降低了12.5%。
在仿真区域内锚节点分别以5%、10%、…、25%比例分布。如上图所示, 横坐标为锚节点所占比例, 纵坐标为定位的平均误差。对比可以看出, 两种算法伴随锚节点比例的不断增加, 所对应的平均定位误差也不断减少。同等条件下, 改进算法优于传统算法。如图在锚节点比例为20%时, 改进的DV-Hop算法比原有传统算法的平均误差降低了11.3%。
4 结论
本文针对节点坐标计算, 采用新的算法, 引入新的定位模型。通过不断修正节点坐标的误差值来修正起始定位坐标, 使其接近实际值。相对传统算法而言, 改进算法在不需要增加软硬件开销的前提下明显提高了节点的定位精度。
摘要：节点定位技术在无线传感器网络中广为应用, 为了精准定位, 可按照距离参数分成测距算法和无需测距算法两大类。本文针对DV-Hop算法在坐标计算阶段中的不足, 尤其对节点随机分布、网络拓扑动态变化的应用环境, 提出相应改进方案。通过仿真比较改进方案的性能。
关键词：改进的DV-Hop,定位误差,算法
参考文献
[1]Yun, S., Lee, J., Chung, W., &Kim, E.Centroid localization method in wireless sensor networks using TSKfuzzy modeling[J].International symposium on advanced intelligent systems, 2008.
[2]Wen-Hwa Liao, Kuei-Ping Shih, Yu-Chee Lee.A localization protocol with adaptive power control inwireless sensor networks[J].Computer Communications, 2008.
[3]Xinwei Wang, O le Bischoff, R ainer Laur, Steffen Paul.Localization in Wireless Ad-hoc Sensor N etworksusing Multilateration with R SSI for Logistic Applications[J].Procedia Chemistry, 2009.
[4]K.E.Parsopoulos, M.N.Vrahatis.R ecent approaches to global optimization problems through Particle Swarm O ptimization[J].N atural Computing, 2002.
[5]Jason Hill, R obert Szewczyk, Alec Woo, Seth Hollar, David Culler, Kristofer Pister.System architecture directions for networked sensors[J].ACM SIGPLAN N otices, 2000.
DV-Hop定位算法 篇6
无线传感器网络(Wireless Sensor Networks,简称WSN)是由部署在监测区域内的大量低成本微型传感器节点组成,通过无线通信方式形成的一个多跳的自组织网络系统。[1]WSN中的节点采用协作方式感知、采集和处理监测区域中对象的信息,因此WSN广泛应用于军事、工业控制、智能交通、污染监测和精细化农业等领域。传感器节点采集到的信息只有和节点自身的位置联系起来,感知的信息才有参考价值。[2]多数情况下传感器节点的部署区域并不是简单的二维区域,而是随机投放在复杂多变的三维区域中,同时传感器节点取得的信息要与自身位置相结合才有应用参考价值,因此研究三维区域的传感器节点定位方法具有重要意义。
传统的传感器节点定位算法分为基于测距和非测距两大类。[3]基于测距的定位算法主要有TOA、TDOA、AOA以及RSSI等[4],一般通过测量获得节点间点到点的距离或角度信息,再使用三边测量法、三角测量法或最大似然估计法等计算节点位置;非测距的定位算法一般以带有GPS坐标定位的锚节点的位置为参照,利用节点间的邻近关系和连通性实现定位,典型的定位算法有质心算法[5]、DV-Hop算法[6,7]以及APIT算法[8]。其中质心算法和DV-Hop算法均可以直接扩充维数,把算法引入三维空间的定位场景。但由于三维场景下这些算法的精度和覆盖率都比二维部署环境低,因此本文分析和探讨了三维场景下的DV-Hop算法,并提出了改进措施,以适应节点分布不均匀和节点低密度的情况下对定位精度和定位覆盖率的要求。
1 DV-Hop 3D定位算法描述
DV-Hop 3D定位算法在原有二维算法的基础上用三维坐标代替二维坐标,算法思想与二维定位算法一致,其算法步骤分为三个阶段:
第一个阶段,锚节点通过距离矢量路由协议向邻居节点广播包含其自身ID和坐标的信息,直到网络中的所有节点都获得最大范围内锚节点的坐标和到锚节点的最小跳数;
第二个阶段,锚节点获得其他锚节点的坐标信息后使用公式(1)计算平均跳距,其中Hop Sizei代表平均跳距,(xi,yi,zi)、(xj,yj,zj)分别是锚节点i、j的坐标,hj是锚节点i与j之间的跳数;
第三个阶段,使用四边测量法或极大似然估计法计算未知节点坐标作为其位置的估计值。
2 DV-Hop 3D定位算法的改进
通过直接扩充维数得到的DV-Hop 3D定位算法与二维算法一样,定位精度依赖于节点分布的均匀度和节点连通度。本文为了提高定位精度和覆盖率,对算法作出如下改进:
在算法的第一个阶段引入跳段数阈值,记为Hop Max,其最小值可参考公式(2)。
其中,假设网络区域为正立方体区域,L是立方体边长,A为每个未知节点定位需要的平均锚节点数,S为网络中节点总数,P为锚节点的比例,R为节点通信半径。当节点到某个锚节点之间的跳数大于Hop Max时,则不记录该锚节点位置信息。引入该阈值的意义在于,当节点分布密度较大时可以在保持原有的定位精度的基础上,有效降低通信和计算量,从而减少节点能耗。
在算法的第二个阶段,由于未知节点计算与锚节点的距离时,选择的平均跳距是最近的锚节点计算的平均跳距,该值在一定程度上能反映出局部网络拓扑,但是大多数情况下会导致较大的定位误差。因此,本文算法进行了如下改进:
(1)网络中的未知节点保存并按序接收所有锚节点的平均跳距和锚节点ID,并计算所有平均跳距的均值,作为全网平均跳距,记为Hop Size_Avg;
(2)设未知节点M的最近的锚节点为i,其平均跳距为Hop Size,到锚节点i的跳数为hi,则到锚节点为i的估计距离为Hop Sizei×hi。若未知节点M到某个锚节点j的跳数hj与到锚节点i的跳数hi相同或非常接近,如│hj-hi│≤1,则表示未知节点M到锚节点i和j的跳数之差为1,到锚节点j的距离为Hop Sizei×hi;若未知节点M到某个锚节点j的跳数hj接近Hop Max时,到锚节点j的距离为HopSize_Avg×hj;其他情况下到某个锚节点j的距离用Hop Sizei×hj计算。
算法的第三个阶段,未知节点M(x,y,z)接收到n≥4个锚节点的坐标信息,n个锚节点的坐标为(x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4),…,(xn,yn,zn),它们到未知节点M的距离分别为d1,d2,d3,d4,…dn,则有以下极大似然估计方程式(3)存在,使用标准的最小均方差估计方法即可以得到节点的坐标。
3 仿真实验与结果分析
为了检验改进的DV-Hop 3D定位算法的有效性,使用Matlab7.1对算法进行了一系列仿真实验。仿真实验构造了边长为100m的正方体三维空间实验区域,该空间区域内随机投放了200个节点,其中锚节点控制在10%~30%。为了计算方便,设所有节点的通信半径R相同,且均为30m。通过多次实验对跳段数阈值Hop Max的取值区间作了合理设定,为使实验数据可信,所有仿真实验均在相同参数下取50次仿真实验的平均值。实验证明,跳段数阈值Hop Max在锚节点比例达到30%时,取值为3较为合适;锚节点比例为10%时,取值为5较为合适。
仿真实验在相同条件下比对了本文的改进算法和普通DV-Hop 3D定位算法。本文中的定位精度用定位误差与节点通信半径的比值来表示,比值越小则定位精度越高。从图一可以看出,随着锚节点比例的提高,两种定位算法均可以达到较好的定位精度,在锚节点比例较少时本文的定位算法能比普通DV-Hop 3D定位算法的定位精度更好,随着锚节点的比例提高,两种算法的定位精度基本接近。从图二可以看出,本文的定位算法由于设置了跳段数阈值,定位覆盖率(可定位节点数与总节点数的比值)略有下降,但本文的定位算法通信量大为减少,定时时间短,能耗花费小。
4 结束语
本文对普通的DV-Hop 3D定位算法进行了改进,提出了一种新的DV-Hop 3D定位算法。在提出的算法中通过设置跳段数阈值解决了锚节点比例提高后节点通信量过大的问题,同时根据未知节点到锚节点的跳数分情况选用平均跳距计算未知节点与锚节点的距离。仿真实验表明:本文算法节点通信量能得到合理控制,在定位覆盖率没有明显降低的情况下,有效提高了定位精度。
参考文献
[1]Akyildiz I F,Su W,Sankarasubramaniam Y,et al,Wireless sensor networks:a survey[J].Computer Networks,2002,38(04):393-422.
[2]Su K F,Ou C H,Jiau H C.Localization with mobile anchor points in wireless sensor networks[J].IEEE Transactions on Vehicular Technology,2005,54(03):1187-1197.
[3]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(05):857-868.
[4]Takashima M,Zhao D.Location estimation using received signal power and maximum likelihood esti-mation in wireless sensor networks[J].Electronics and Communications in Japan,2007,90(12):62-72.
[5]Bulusu N,Heidemann J,Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine,2000.
[6]Niculescu D,Nath B.Ad Hoc positioning system[C]∥IEEE Global Telecommunications Conference,2001(,05):2926-2931.
[7]Niculescu D,Nath B.DV based positioning in ad hoc networks[J].Kluwer Journal of Telecommunication Systems,2003,(22):267-280.
DV-Hop定位算法 篇7
无线传感网络(wireless sensor network,WSN)中实现其应用的关键是如何能够准确定位节点的位置信息。无线传感网络中的节点定位包括锚节点和未知节点定位。其中,锚节点是指少量带有GPS定位装置的节点,由于加装GPS设备能量消耗高,因此无法广泛使用,未知节点需要通过锚节点来进行自身定位[1,2,3]。根据定位过程中测量节点间的距离,定位算法分为基于测距(range-based)的定位算法以及基于无距离(range-free)的定位算法[4]。基于测距的算法需要测量相邻节点之间的距离,利用节点之间的实际距离来计算未知节点的位置,这种算法大多对硬件要求比较高,不太适合消耗功率和成本低的应用领域,目前常用的测距技术主要有RSSI、TOA、TDOA、AOA[5,6];基于无距离的算法无需测量节点间的实际距离,而是通过节点之间的估计距离来计算节点位置,可以降低节点的硬件要求,但是节点之间定位误差会增加,常用算法主要有质心算法、DV-HOP算法[7]。其中,DV-HOP算法主要通过距离向量路由协议来获得各个锚节点的信息,但是伴随着锚节点与未知节点之间跳数距离的增加,所测算的距离也会逐渐积累,从而对接点的定位精度造成了一定的影响。
本文首先分析目前DV-HOP算法3个步骤中存在的问题,然后将加权质心算法和二维双曲线概念引入到算法中,通过加权质心算法计算校正值,将接受信号RSS作为参考标准,有效减少误差,同时针对距离估算问题采用改进的二维双曲线算法,在二维双曲线基础上引入权值概念,使得估算距离更加精确。仿真实验表明,本文算法在校正值定位误差、最大估算误差精度都有一定程度降低,相比于文献算法有明显提高。
1 基本知识
1.1 DV-Hop算法
DV-HOP算法的主要思想是将未知节点与锚节点之间的距离通过网络平均跳数和跳数的乘积来进行决定,然后通过似然估计得到节点的位置。其算法分为3个步骤:
(1)信息广播与校正值计算。在无线传感网络中,每一个锚节点都会将自己的位置信息通过数据分组的形式广播出去,设定初始化跳数为0,当未知节点记录到每一个锚节点的最小跳数时,与已经存在跳数进行比较,如果大于已存在的跳数,则忽略不计,然后将跳数值加1,继续转发其余未知节点,这样每一个未知节点就可以得到锚节点的最小跳数。
(2)校正值广播。每一个锚节点将自身校正值以广播的形式播放出去,没有定位的未知节点得到各个锚节点的校正值。
(3)未知节点定位。通过计算锚节点的校正值和自身到锚节点的跳数计算锚节点的距离。然后再通过锚节点的坐标信息和到锚节点的距离信息,计算出未知节点的坐标信息。
1.2 DV-HOP算法的不足
DV-HOP算法的3个阶段都存在一定误差,具体如下:
(1)校正值方面的误差。在无线传感网络中,所有未知节点全部使用跳数与校正值的乘积来表示距离,计算出来的估计距离与真实距离存在着很大的偏差。假设待定节点与锚节点之间的跳数为1时,采用DV-HOP算法来计算两点的距离,如图1所示。
假设节点N为未知节点,A,B,C三个节点都为锚节点,3个锚节点之间的相互之间的距离如图1所示。其中,AB之间的跳数为6,BC之间的跳数为5,AC之间的跳数为5。各个锚节点能够计算出自己的校正值。其中,节点A的校正值为:(30+110)/(6+5)=12.72,节点B的校正值为:(30+60)/(6+5)=8.18,节点C的校正值为:(60+110)/(5+5)=17。根据最近未知节点到锚节点获取校正值的原则,节点N从节点C获得校正值是17,因此节点N到3个锚节点的距离为:NA为3*17=51,NB为3*17=51,NC为17*2=34。从节点N到节点A的直线距离为42,节点N到节点B的距离为45,节点N到节点C的距离为50,因此误差分别是60-51=9,60-45=15,60-34=26,误差率分别为:9/60=15%,15/60=25%,26/60=43.3%。由于在真实的环节中,无线传感节点的分配更加复杂,通过这种定位方法,容易造成未知节点N的定位位置偏离真实位置。
(2)未知节点距离测算不准。在无线传感网络中,未知节点的位置使用校正值与锚节点之间的跳数乘积来进行代替,这种方式显然忽视了复杂情况下的节点定位,存在非常大的误差。以图1为例,NC之间通过上述方面测出的距离结果为34,而实际之间直线的距离为45,误差率为(45-34)/34=32.4%,可以发现,NC之间的实际距离是无法改变的,NC之间的测算距离决定着误差率,很显然NC之间的测算距离越接近实际距离,误差率越小,显然采用目前这种测算方法,无法尽可能减少误差。
(3)最大估算问题。目前,在DV-HOP算法中广泛采用估算法来衡量节点位置,主要是因为算法简单,容易实现,但由于未知节点需要3个以上的锚节点来确定位置,未知节点与锚节点存在误差,这样容易造成一定范围内的误差累计。
2 基于改进的加权质心和二维双曲线的DV-HOP定位算法
2.1 改进的加权质心算法
针对DV-Hop算法中未知节点定位误差导致校正值方面不准确的问题,本文将接受信号强度(RSS)作为一个权重值,用作针对未知节点的定位进行改进。以图2为例,在一个未知节点N周围存在着不同的锚节点{A,B,C,D,E,…..K},设定锚节点的坐标为A(xA,yA),B(xB,yB),C(xC,yC)…..K(xK,yK),因此未知节点N采用表1的方式来记录未知节点接收周围锚节点发出的RSSI信号的强度,未知节点与锚节点之间的路径距离以及锚节点坐标信息等。
根据信道传输模型的特点可以得出:信号传输距离越远,其RSSI的值越弱,因此锚节点对未知节点坐标求解的影响比较大,由于未知节点处于所在区域的位置不能随意更改,所以未知节点与锚节点的距离和RSSI值作为参考就显得非常重要。本文从以上两个因素考虑,将RSSI强度值的大小对比为具体的数值,然后通过RSS数值与路径距离的比值作为参考系数,通过与锚节点的坐标的乘积来确定未知节点的坐标。计算如下:
其中,RSSIN→R表示未知节点到锚节点R之间的信号强度,SN→R表示未知节点到锚节点之间的路径距离。
2.2 改进的二维双曲线定位算法
通过前述估算算法可以发现,由于DV-HOP算法通常采用似然估计法计算节点位置,这种通过3个方程组相减的方法对坐标信息具有一定程度的损失,为了避免这种误差,采用改进的双曲线定位算法,为了更好地提高节点的定位精度,引入一个误差值ε。
假设未知节点坐标为(x,y),锚节点的坐标为K(xK,yK),则未知节点与锚节点之间的距离为:
步骤1:在距离测量的过程中获得一个近似距离length′N→i
步骤2:综合公式(2)、(3)得到:
步骤3:展开公式(4)得到:
步骤4:设定S=x2+y2,T=x12+y12代入公式(5)中,得到公式(6)
步骤5:将式(6)按照矩阵进行展开,得到公式(7):
步骤6:利用误差ε最大值设定锚节点权值。从收到的锚节点中找出距离未知节点最远的锚节点,记作lengthmax,由于距离最远导致产生的误差可能比较大,设定权值为1,然后计算未知节点与锚节点之间的距离,按照不同的路径距离设定权值集。各个锚节点的权值计算按照公式(8)计算:
步骤7:将公式(8)中各个锚节点的权值按照对角矩形形式表示为:
步骤8:通过矩阵来控制锚节点与未知节点之间不同距离对于节点定位的影响。构造目标函数F:
步骤9:使用最小二乘对公式(10)进行求解,得到K=(A-TA′)-1(A-TB′),其中,
2.3 算法流程
本文算法如图3所示。
3 算法仿真与分析
为进一步验证算法的有效性和实用性,本文在Windows平台上采用Matlab2010进行仿真实验。仿真环境选择100*100的区域,选择500个节点,其中100个为锚节点,400个为未知节点,所有节点都进行随机分布。
3.1 校正值定位误差
选取本文算法与文献[8]算法在校正值定位误差上的比较,进行100次仿真实验,如图4所示
通过图4可以发现,本文算法的误差范围在8%左右,而文献[10]算法误差近20%,在校正值计算上由于采用了改进的加权质心算法,使得误差范围缩小。
3.2 最大估算定位误差
选取本文算法与文献[8]算法对最大估算定位误差进行比较,如图5所示。
通过图5可以发现,本文算法误差范围在12%左右,而文献[8]算法误差近21%,在最大估算定位选择上由于采用了改进的双曲线算法,使得最大估算误差范围缩小。
3.3 改进后的整体算法的结果
图4、图5分别从校正值误差定位和最大估算定位对两种算法进行了比较。本文算法与文献[9]、文献[10]算法从整体上进行比较,如图6所示。
4 结语
无线传感网络中未知节点的定位一直是WSN中研究的重点,特别是未知节点定位的好坏直接影响到无线传感网络效率的高低。本文针对DV-HOP算法中校正值的误差,未知节点距离测算不准以及最大估算误差进行分析,针对校正值方面存在的问题采用了改进的加权质心算法,在最大估算算法上采用了改进二维双曲线的方法,改进后的算法在定位精度上有了明显提高。
参考文献
[1]AKYILDIZ I,SU W,SANKARASUBRAMANIAM Y,et,al.A survey on snesor network[J].IEEE Communicaitons Magazine,2002,40(8):102-144.
[2]NICLESCU D,AMERIC N L.Communication paradigms for sensor networks[J].IEEE Communications Magazine,2005,43(3):116-122.
[3]BOUKERCHE A,OLIVERIRA H A,NAKAMURA E F.Localization systens for wireless sensor network[J].IEEE Wirless Communications,2007,14(6):6-12.
[4]谭志,张卉.无线传感网络RSSI定位算法的研究与改进[J].北京邮电大学学报,2013,36(3):88-91.
[5]刘运杰,金明录,崔承毅.基于RSSI的无线传感器网络修正加权质心定位算法[J].传感技术学报,2010,23(5):717-721.
[6]何艳丽.无线传感网络质心定位算法研究[J].计算机仿真,2011,28(5):163-166.
[7]NICULESCU D,NATH B.DV-based positioning in adhoc network[J].Telecommunication Systems,2003,22(1):267-280.
[8]夏少波,连丽君,王鲁娜.基于DV-Hop定位算法的改进[J].计算机应用,2014,35(5):1247-1250.
[9]李道全,刘月月,孙付龙.基于DV-HOP的WSN网络节点定位算法[J].计算机仿真,2014,31(4):303-306.
[10]金纯,叶诚,韩志斌.无线传感器网络中Dv-Hop定位算法的改进[J].计算机工程与设计,2013,34(2):18-25.
[11]苏兵,薛伟杰,王洪元.一种WSN非测距定位DV-Hop算法的误差改进方法[J].计算机测量与控制,2013,21(5):1357-1359.
DV-Hop定位算法 篇8
根据定位机制, 现有无线传感器网络定位算法可以分为两大类[4]:基于测距 (range-based) 的定位算法和无需测距 (range-free) 的。前者通过测量节点间点到点的距离或者角度信息定位[5], 对于网络的硬件设施有较高的要求;后者仅根据网络连通性等信息定位。故其在成本、功耗方面存在较大优势。
其中DV-Hop定位算法是典型的与测距无关的定位算法之一, 其基本思想是利用跳数与平均每跳距离乘积代替节点间的距离, 然后通过三边定位或极大似然法估计获得未知节点的位置信息。然而, 在计算网络的平均每跳距离时, 该算法仅考虑了离未知节点最近的信标节点的平均每跳距离, 因此与网络的实际平均每跳距离存在很大的误差。本文结合变异系数改进传统DV-Hop的平均每跳距离计算方式。仿真实验结果表明, 改进后的算法具有较好的性能, 是一种可执行的方案。
1、D V-H op定位算法[7]
第一阶段, 计算未知节点到每个信标节点的最小跳数。每个信标节点将其位置信息在网络中以包含该信标节点跳数信息的分组形式泛洪广播, 使得网络中的所有节点都能记录下到每个节点的最小跳数。
第二阶段, 计算平均每跳距离。信标节点i可利用公式 (1.1) 计算自己的平均每跳距离:
式中:j为信标节点i数据表中的其他信标节点;hopsij为信标节点i和j之间的跳数。
每个未知节点仅接收距离自己跳数最少的那个信标节点发送的分组信息, 且根据自己数据表中记录的跳数, 计算到每个信标节点的距离。
第三阶段:未知节点利用第二阶段中计算出的到各个信标节点的估计距离, 利用三边定位法或极大似然法计算估计坐标。
2、基于变异系数的DV-Ho p改进
基于变异系数的D V-H o p算法改进思想如下:
未知节点接收到多个已知节点的平均每跳距离后, 结合变异系数的思想, 对这些平均每跳距离进行归一化的处理, 即给每个已知节点的平均每跳距离都赋予一个权值, 用这个权值与各自的平均每跳距离的乘积求和代替传统算法的平均每跳距离, 避免了传统方式采用一个最近节点的平均每跳距离带来的较大误差, 同时, 也能全面考虑各个节点与未知节点的平均每跳距离, 更平滑的处理多个节点的平均每跳距离, 计算出的结果更客观, 接近于真实值。
下面具体介绍一下新算法中的平均每跳距离计算方法。用Cj代表每个已知节点的平均每跳距离, 用Cp代表全网平均每跳距离。假设未知节点一共收到n个已知节点的信息, 将每个已知节点的平均每跳距离加权值用Wj表示。
计算全网平均每跳距离为:
计算第j个已知节点的平均每跳距离加权值为:
其中, δj为第个已知节点平均跳的变异系数, 定义为:
D为第j个已知节点的均方差,
接下来, 按传统D V-H o p算法计算未知节点的坐标。
3、仿真实验
3.1 实验设计
参考文献[7]中的仿真场景, 在网络区域为[0, 100m]×[0, 100m], 在该网络区域中的所有节点均随机生成, 并且信标节点的选取也是随机的, 在[0, 100m]×[0, 100m]的网络区域中随机分布了100个节点, 其中随机选取了10个信标节点。分别对传统DV-Hop算法和改进后的算法进行仿真和验证。
3.2 实验结果及分析
在节点总数不变的情况下, 改变节点通信半径R将影响网络的平均连通度。由仿真曲线图3.1 (a) 、3.1 (b) 可知, 在相同的网络环境 (节点通信半径R, 信标节点数) 下, 本文提出的改进算法II的定位误差均明显低于传统DV-Hop算法和文献[7]的改进算法I, 当节点通信半径由R=15m变化到R=30m时, 无论是传统D V-H o p算法还是DV-Hop (改进) 算法在平均定位误差、定位误差均方差方面都随着通信半径R的增加而增大;这是因为在增加节点通信半径R而增大网络平均连通度的同时, 导致节点计算的平均每跳距离的误差在增大, 从而导致算法参数指标误差的增大。
4、结语
本文提出了一种基于变异系数加权处理平均每跳距离的估计算法, 与文献[7]提出的方法相比, 其平均每跳距离更接近真实值, 更准确的反应了网络的实际状态, 从而提高了定位精度, 降低了定位误差。此外, 该算法不需要增加任何的硬件设施, 控制了算法成本。仿真结果表明, 本文提出的算法是一种可行的定位解决方案。
参考文献
[1]Arampatzis Th, Lygeros J, and Manesis S.A survey of appli-cations of wireless sensors and wireless sensor networks[C].Proceedings of the IEEE International Symposium on MediterreanConference on Control and Automation, Limassol, Cyprus, 2005:719-724.
[2]任丰原, 黄海宁, 林闯.无线传感器网络[J].软件学报, 2003, 14 (7) :1282-1290.
[3]Akyildiz I F, Weilian Su, and Sankarasubramaniam Y, et al..Asurvey on sensor networks[J].IEEE Communications Magazine, 2002, 40 (8) :102-114.
[4]杨冕, 秦前清.对传感器网络定位技术现状的研究[J].微机发展, 2005, 15 (3) :26-28.
[5]Niculescu D.Positioning in Ad hoc sensor networks[J].IEEENetwork, 2004, 8 (4) :24-29.
[6]史龙, 王福豹, 段渭军等.无线传感器网络Range-Free自身定位机制与算法[J].计算机工程与应用, 2004, 40 (23) :127-130.