下载文档原格式
无线传感器网络中—种基于加权的DV-Hop定位算法随着科技的发展，无线传感器网络（WSN）被广泛应用于农业、能源、环境等领域，定位技术成为其重要的研究方向之一。
基于跳数的分布式定位算法（DV-Hop）因其简单、经济和可靠的特点而受到广泛关注。
本文将介绍一种基于加权的DV-Hop定位算法。
传统DV-Hop定位算法利用无线传感器网络中节点的跳数来计算节点的位置，其基本思想是节点利用其跳数信息和锚节点的位置信息来进行三角定位，从而分布式地计算节点位置。
然而，这种方法存在着误差较大的问题。
因此，研究者提出了一种基于加权的算法来解决传统算法中误差较大的问题。
基于加权的DV-Hop定位算法将节点间的距离作为权重，利用跳数和权重的乘积来计算节点的位置，从而减小位置误差。
该算法的基本步骤如下：1. 以锚节点为根节点构建一个拓扑结构，计算任意两个节点之间的距离。
2. 将距离的倒数作为权重，以根节点为起点使用DV-Hop算法计算出所有节点到根节点的距离信息。
3. 利用跳数信息和加权距离信息，通过三角定位算出每个节点的位置。
其中，节点位置的计算可以使用多种三角定位算法，如最小二乘法、加权最小二乘法等。
相比传统DV-Hop定位算法，基于加权的算法不仅考虑跳数信息，而且将距离作为权重，使得定位的精度更高。
同时，该算法没有增加额外的通信开销，因此保持DV-Hop算法的经济性和可靠性。
然而，基于加权的算法在实际应用中仍存在一些问题。
由于节点间的距离或权重可能存在变化，节点位置的准确性会受到影响。
此外，由于算法计算过程相对复杂，需要较高的计算能力。
因此，在实际应用中需要根据实际情况选择合适的算法。
总之，基于加权的DV-Hop定位算法作为一种有效的定位方法，在无线传感器网络中得到了广泛的应用。
然而，在具体应用中，需要充分考虑算法的优缺点，选择合适的算法以提高定位精度和准确性。
基于进化算法的多通信半径DV-Hop改进定位算法陈业海;郑日荣;许亮【摘要】定位是无线传感器网络中最重要的问题之一.针对DV-Hop算法定位精度低问题,提出基于进化算法的多通信半径DV-Hop改进定位算法.该方法在多通信半径定位算法基础上,使用蛙跳算法对锚节点跳距进行优化,并对其适应值函数进行改进,让跳距值更接近真实值,然后在DV-Hop算法最后阶段利用遗传算法求解未知节点坐标.实验仿真结果表明,改进算法在不增加额外硬件情况下,大大降低了定位误差,相比于传统DV-Hop算法,定位精度提高了大约69％,相比其他文献,定位精度提高了大约21％.【期刊名称】《计算机工程与应用》【年(卷),期】2019(055)001【总页数】7页(P89-95)【关键词】无线传感器网络;DV-Hop算法;改进蛙跳算法;遗传算法【作者】陈业海;郑日荣;许亮【作者单位】广东工业大学自动化学院,广州 510900;广东工业大学自动化学院,广州 510900;广东工业大学自动化学院,广州 510900【正文语种】中文【中图分类】TP3931 引言无线传感器网络（Wireless Sensor Network，WSN）是由大量小而便宜的基于微机电系统的节点所组成。
这些传感器节点是随机分布在监测区域，根据需求收集环境信息和进行信息处理[1]。
每个传感器节点包含传感单元、处理单元、通信单元和电源部分，具有有限的计算能力、存储能力和通信范围，是一种低能耗的节点[2]。
无线传感器网络在军事侦察、环境监测和工业生产等前沿领域有着广泛的应用[3]。
在无线传感器网络的大多数应用中，节点的位置和数据的获取一样重要。
例如，在目标跟踪[4]、医疗保健[5]和智能社区[6]应用中，如果节点只获得信息而没有地理位置是没意义的。
未知节点获得位置信息最简单的解决方案之一是使用全球定位系统（GPS）。
但是，不可能把它应用到所有的传感器节点中，因为使用GPS增加节点的大小，功耗和成本，而且GPS设备在室内基本不能工作。
基于迭代协作的改进DV-Hop定位算法邰剑秋【摘要】针对无线传感器网络中DV-Hop定位算法的不足,提出一种基于迭代协作的优化算法(ICDV-Hop算法).通过限制跳数来减小距离误差,利用共线度测试约束节点间几何位置关系,选择最优信标三角形组合以提高定位精度.同时将定位误差在设定阈值范围内的已定位节点转化为信标节点,进行迭代协作,从而在控制误差传播的前提下增加定位覆盖.仿真结果表明,ICDV-Hop算法与传统DV-Hop算法相比,定位精度和定位覆盖均有明显改善,定位性能受网络条件影响小,表现出良好的可靠性和鲁棒性,尤其是在信标节点比例较低及网络稀疏的情况下.【期刊名称】《中国传媒科技》【年(卷),期】2014(000)010【总页数】4页(P108-111)【关键词】DV-Hop算法;迭代协作;节点定位;信标节点;无线传感器网络【作者】邰剑秋【作者单位】新华社音视频部【正文语种】中文介绍在无线传感器网络中，节点准确地进行自身定位对其有效性起着关键的作用。
为了适应无线传感器网络中节点低能耗的特性要求，充分利用节点资源，在节点定位中引入协作技术，以获得更高定位的性能，即协作定位[1]。
对于无线传感器网络节点定位算法主要可以分为两大类：基于测距的定位算法和无需测距的定位算法。
测距技术主要包括基于TOA的定位、基于TDOA的定位、基于AOA的定位、基于RSSI的定位等[1][2]。
无需测距的算法主要包括以下几种：质心算法[3]、APIT算法[4]、MDS-MAP算法[5]、DV-Hop算法[6]等。
上述算法中，DV-Hop算法具有方法简单、定位精度较高等优点，但其定位性能受节点分布影响大，仅在密集网络中，才能达到较高定位精度，当网络拓扑不规则时，定位误差较大。
文献[7]通过加入接收信号强度指示器（RSSI）测距模块辅助定位，对算法进行改进，提高了定位精度和系统稳定性。
但是需要增加额外的测距模块，使硬件复杂度增大，有悖于无需测距算法简单易行、成本低的特点。
一种改进的无线传感器网络DV-Hop定位算法马晓贤;彭力【摘要】Self-positioning of sensor nodes is one of the important researches in the wireless sensor networks. The main error source of DV-Hop localization algorithm is the estimation error of the distance between unknown nodes and anchor nodes. In order to reduce the error, this paper introduces the ideal anchor nodes’distance. It is used to exclude a part of average single-hop distance calculated by anchor nodes that has large errors. It’ll fix the network-wide average single-hop distance. Then it will correct the coordinates of unknown nodes that are obtained by the least squares. The simulation results show that, the algorithm can effectively improve the positioning accuracy of the nodes. And the algorithm has low require-ment on the number of anchor nodes and the communication radius. It can effectively save energy and cost of the network.%传感器节点的自定位问题是无线传感器网络的重要研究内容之一。
一种基于DV-Hop的无线传感器网络节点定位算法王景珲【摘要】针对无线传感器网络节点的自身定位问题,提出一种基于分布式协作的DV-Hop改进算法.在距离计算的基础上,采用最大似然估计方法选取共线度较低的参考点作为锚节点.综合考虑所有锚节点,以可信度为准则,通过加权平均计算每一个未知节点的平均跳距.计算未知节点的定位误差,将误差低于预设阈值的未知节点转化为锚节点,扩大定位范围.仿真结果表明,在初始锚节点数和通信半径相同的情况下,该算法的定位误差比DV-Hop算法减少约20％,尤其当节点密度较小时,其定位误差可稳定在40％以下.当节点通信半径超过10 m时,该算法的剩余节点比例可降低约30％.【期刊名称】《计算机工程》【年(卷),期】2015(041)001【总页数】5页(P82-86)【关键词】无线传感器网络;DV-Hop算法;锚节点;共线度;协作定位【作者】王景珲【作者单位】国家数字交换系统工程技术研究中心,郑州450001【正文语种】中文【中图分类】TP393无线传感器网络的节点定位技术是网络应用的关键支撑技术之一。
对于无线传感器网络应用来说,节点的位置信息非常重要。
传感器节点的位置可以标示监测数据源的位置,为网络管理提供拓扑结构,并可生成用于数据传输的路由协议。
传感器节点的位置可以通过配置GPS定位装置或人工定位布置获得,但由于传感器网络的节点数量较大,GPS定位装置的费用较高,因此目前常用的做法是,网络中的少量锚节点配备GPS接收器或人工布置,其他节点依靠锚节点的位置信息和节点间的通信或测距技术,通过相应的节点定位算法来获得其位置信息[1-2]。
迄今为止,研究人员分别从不同的角度来考虑WSN节点的定位问题,如网络拓扑、设备能力、定位精度和能量需求等,并提出了很多行之有效的节点定位算法。
美国Rutgers大学的Niculescu提出了一系列分布式定位算法APS(Ad hoc Location System),其中DV-Hop定位算法DV-Hop(DistanceVector-Hop)是目前应用最为广泛的一种,该算法根据距离矢量路由和GPS定位原理,仅依靠网络的连通度就能实现对未知节点的定位,而且传感器节点不需要任何的额外硬件设施。
基于改进DV-Hop算法的无线传感器网络定位研究李鹏【摘要】在分析DV-Hop算法特点的基础上,提出了改进DV-Hop算法的无线传感器网络定位方法,通过粒子群优化算法优化每跳平均距离误差函数,经过多次迭代寻找最优解,使得未知节点与信标节点之间的跳段距离更加精确,通过三边测量法计算出的未知节点位置较精确,通过仿真实验表明:改进DV-Hop算法相比DV-Hop 算法平均定位误差率低,定位效果良好.【期刊名称】《重庆工商大学学报（自然科学版）》【年(卷),期】2014(031)008【总页数】5页(P46-50)【关键词】DV-Hop算法;无线传感器网络;粒子群优化【作者】李鹏【作者单位】长江大学计算机科学学院,湖北荆州434023【正文语种】中文【中图分类】TP3930 引言无线传感器网络是由部署在监测区域内大量的具有计算和通信能力的微型传感器节点组成，通过无线通信的方式形成一个多跳的自组织的网络系统[1]，其作用是利用传感器来监测、收集、处理信息数据，传感器的无线收发装置将数据通过无线通信传输。
传感器节点的定位是无线传感器网络的基本功能。
根据是否需要测量实际节点间的距离，把无线传感器网络定位算法分为两类：基于距离的定位算法(Range-based)和距离无关的定位算法(Range-free)[2]。
基于距离的定位算法共同特点是需要测量相邻节点间的绝对距离或方位，并通过测量的绝对距离和方位来计算未知节点的位置；距离无关的定位算法则不需要测量节点间的绝对距离或方位，而是要得到节点间的估计距离，然后利用估计距离计算节点位置。
距离无关的定位算法通常有DV-Hop算法、质心算法、APIT算法等经典算法[3]。
其中DV-Hop算法使用每跳平均距离乘以跳段数来计算节点间距离，对网络节点的硬件设备要求低，部署简单，实现起来比较简易，缺点是节点间的跳段距离是估算出来的，用节点间的跳段距离代替节点间的实际直线距离是不精确的，存在误差[4]。
无线传感器网络中的DV-Hop定位改进算法周杨;秦嘉杭;李万雷【期刊名称】《单片机与嵌入式系统应用》【年(卷),期】2013(13)1【摘要】DV-Hop is a typical range-free position algorithm in wireless senor network. Aiming at the existing low position accuracy in DV-Hop, an improved algorithm is proposed. The average hop distance is amended using the average hop distance of whole network and equalizing value of the average hop distance estimated by a single anchor node.%DV-Hop算法是无线传感器网络中一种典型的基于非测距的定位算法.针对DV-Hop存在的定位精度低的缺陷,本文提出了改进的算法.该算法中的平均跳距利用全网平均跳距与单个锚节点估计的平均跳距的均值来修正,并且根据连通度不同,选取最优的3个锚节点进行三边定位计算.【总页数】4页(P1-4)【作者】周杨;秦嘉杭;李万雷【作者单位】南京邮电大学【正文语种】中文【中图分类】TP393【相关文献】1.无线传感器网络中DV-Hop定位算法的改进 [J], 曾福庚2.一种无线传感器网络中 DV-Hop定位的改进算法 [J], 陈晶杰;罗明3.无线传感器网络中DV-Hop定位算法的改进 [J], 马淑丽;赵建平4.无线传感器网络中改进的DV-Hop定位算法 [J], 李凤超;高美凤5.无线传感器网络中DV-Hop定位算法的改进 [J], 李云飞;江明;娄柯;葛愿因版权原因，仅展示原文概要，查看原文内容请购买。
基于GWO和PSO协同优化的DV-Hop定位算法作者：朱子行陈辉来源：《现代信息科技》2022年第03期摘要：無线传感器网络具有感知和处理信息的能力，只有当被测网络内节点的位置已知时，节点传递给用户的信息才有意义。
针对DV-Hop定位中传统最小二乘法不可避免的精度低的缺点，引入粒子群算法（PSO）和灰狼优化器（GWO）来估计未知节点位置。
粒子群算法具有个体记忆的特点，采用粒子位置更新代替灰狼个体位置更新，使灰狼算法在优化上具有可记忆性。
仿真数据表明，改进后的算法可以有效降低节点定位误差，实现更高的定位精度。
关键词：无线传感器网络;DV-Hop;灰狼优化器;粒子群算法中图分类号：TN934 文献标识码：A文章编号：2096-4706（2022）03-0088-04DV-Hop Positioning Algorithm Based on GWO and PSO Collaborative OptimizationZHU Zihang， CHEN Hui（Anhui University of Science & Technology， Huainan 232001， China）Abstract： Wireless sensor networks have the ability to sense and process information， and the information passed by the nodes to the user is meaningful only when the location of the nodes within the network under test is known. In view of the inevitable shortcoming of low precision of the traditional least squares method in DV-Hop （distance vector-hop） localization， the Particle Swarm optimization （PSO） and the Gray Wolf Optimizer （GWO） are introduced to estimate unknown node positions. The Particle Swarm optimization has the characteristics of individual memory， and the particle position update is used to replace the gray wolf individual position update， so that the gray wolf algorithm has memory in optimization. The simulation data show that the improved algorithm can effectively reduce the node positioning error and achieve higher positioning accuracy.Keywords： wireless sensor network; DV-Hop; Grey Wolf Optimizer; Particle Swarm optimization0 引言无线传感器网络（Wireless Sensor Network， WSN）作为信息获取的重要技术随着网络信息的快速发展得到了广泛使用[1]。
近些年来，WSN在城市建筑，路况交通，医疗军事，森林农田[2]等领域具有广阔的应用前景。
识别网络节点的位置是无线传感器网络中的一个重要步骤，在不知道节点位置的情况下收集的信息大多是无意义的。
在应用WSN时，传感器节点通常采用随机部署，特别是对于大规模网络。
因此，每个节点的位置信息是不可或缺的。
一种解决方案是在每个节点上安装一个GPS或北斗定位模块来获取它们的位置信息，这不仅成本高，而且不实用，因为传感器节点的功耗会大大增加，每个节点的生命周期显著缩短。
此外，在室内或者密集环境中，定位模块的性能会下降。
另一种解决方案是使一部分节点装有定位模块（锚节点）和利用一些定位技术来估计未知节点的位置。
目前，WSN定位技术根据是否需要硬件辅助测量节点间的距离分为基于测距和非测距两大类[3]。
基于测距的定位算法主要包括AOA、TOA、TDOA和RSSI等。
非测距的经典定位算法主要包括质心定位、APIT、DV-Hop等。
非测距算法对相邻锚节点的最小数量有严格的要求，锚节点数目越多越容易获得更高的定位精度[4]。
DV-Hop（Distance Vector-Hop）由于它的算法实现简单，不需要提供额外硬件设备，引起了国内外众多厂商、学者的关注。
该算法的核心原理是通过平均跳距和最小跳数的乘积来近似传感器节点之间的距离，因此难以达到某些应用所要求的定位精度。
本文提出一种改进的DV-hop定位算法，引入粒子群协同灰狼算法代替最小二乘法对未知节点坐标进行估计，实验结果证明可以有效降低定位误差，提高定位稳定性。
1 传统DV-Hop定位算法1.1 未知节点定位过程DV-Hop定位是一种基于距离矢量路由机制的非测距定位算法[5]。
该算法是由NICULESCU D.和NATH B在2003年提出的，根据节点间的距离选择最佳路径进行定位。
无线传感器网络包含两种节点：信标节点（Anchor Node， AN）和未知节点（Unknown Node，UN）。
DV-Hop算法步骤为：（1）求节点之间的最小跳数。
每个节点通过距离矢量路由交换原理接收到从ANi发送的数据包。
在数据包广播过程中，邻居节点收到数据包时，包内跳数值增加1并转发出去。
如果节点接收到来自同一个信标节点的数据包，保留较小跳数值的数据包。
（2）计算ANi的平均每跳距离：（1）式中hij是ANi和ANj之间的最小跳数值。
（xi，yi），（xj，yj）分别是ANi，ANj的坐标。
AN依据公式（1）得到平均跳距后，把自身的平均跳距广播给其他节点。
邻居节点接收信息后将跳数加1并继续广播（如果收到多个节点广播的信息，只接收第一个到达的信息），然后通过公式（2）来计算出自身和AN之间的距离：（2）其中hui是ANi到UNu的最小跳数，Hopsizei为ANi所在路径的平均跳距。
（3）求出UN和AN之间的距离后通过最小二乘法来估计未知节点的位置。
设UNm的坐标为（x，y），ANi的位置是（xi，yi），UNm到ANi的距离为di则：（3）为了使方程组线性化，将式（3）转换为AX=B的方程。
A，B，X由下式得出：（4）最后根据最小二乘法我们得到未知节点的位置为：（5）1.2 误差分析1.2.1 跳数不精确问题根据DV-Hop跳数定义规则，将信标节点与通信范围内其他节点之间视为1跳，这必然会导致较大的误差。
如图1所示。
信标节点a发送数据包时，未知节点a1、b、c接收到数据包并都记录为1跳。
但明显能看出三个未知节点和信标节点a之间的距离并不相等，因此这种方法计算跳数时会累积更多的误差。
1.2.2 未知节点坐标的计算方法不合理采用最小二乘法或最大似然估计求解矩阵形式的方程组，可能导致无解或逆矩阵的情况，影响定位结果。
2 改进算法2.1 PSO算法粒子群优化算法是一种智能计算领域的群优化算法，该算法通过模拟鸟群捕食过程中每只鸟的活动来达到函数优化的目的[6]。
PSO算法的本质是粒子在空间中不断地向特定方向变速运动，并通过自身的记忆和群体通信找到下一个位置，从而找到最优解。
速度和位置的更新公式为：vi（t+1）=vi（t）+c1×rand（）×（pbesti-xi（t））+c2×rand（）×（gbestj-xi（t））（6）xi（t+1）=xi（t）+vi（t+1）（7）2.2 GWO算法灰狼优化器（Grey Wolf Optimizer， GWO）模拟自然界中灰狼的领导水平和狩猎机制[7]。
灰狼通常被称为顶级掠食者，也就意味着它们在食物链中处于首位。
它们通常以5～12只成群生存，具有严格的社会等级地位。
四种类型的灰狼α、β、δ、ω，在设计GWO时需要将狼的社会等级抽象为合适的数学模型。
默认第一等级（最优解）为α，第二和第三等级分别为β和δ，剩余的候選解为ω。
在GWO算法中，搜索时由（α，β，δ）引导，ω跟随前三等级的狼。
灰狼狩猎方法涉及三个阶段，接近受害者、包围受害者和攻击受害者。
A>1表示灰狼与猎物分离以确定最佳攻击目标。
确定攻击目标后，狼群包围猎物可表示为：（8）t为当前迭代次数，X为狼的位置，Xp为猎物的位置，D为猎物与狼之间的距离，r1，r2∈[0，1]，a∈[0，2]。
包围猎物后，我们认为（α，β，δ）是三种可能的解，它们的位置随着猎物的移动而变化。
狼群追逐行为可以表示为：（9）2.3 混合策略单一的群体智能算法会受到自身搜索能力的限制，在处理一些复杂的问题时，会出现求解精度低，容易陷入局部最优等问题[8]。
而混合优化算法可以通过不同种群之间的信息交换来达到提高算法性能的目的。
现有的混合算法大多数按照使用顺序来优化目标，不能相互结合。
因此，PSO-GWO更像是一种并行算法，同时工作和兼顾算法的收敛速度和准确性。
本文采用粒子群算法具有个体记忆的特点，采用粒子位置更新代替灰狼个体位置更新，使灰狼算法在优化上具有可记忆性。
通常调整惯性常数w来协调混合算法平衡全局搜索和局部开发能力，w的变化范围为[0.5，1]。
则上式（6）变成了（10）：（10）公式（9）中三个狼到猎物之间的距离变为（11）：（11）适应度函数设置为：（12）其中，（x，y）为待测节点的坐标，（xi，yi）为信标节点i的坐标，di为信标节点i到未知节点的距离。
粒子群混合灰狼优化算法的具体实现流程为：（1）初始化a、A、C的值，设置灰狼种群大小为N;（2）初始化种群个体，同时计算灰狼的适应度;（3）取适应度值前三位的个体α、β、δ，其对应的位置信息为Xα、Xβ、Xδ;（4）使用公式（8）更新A和C的值，根据公式（10）更新灰狼个体位置，返回步骤2重新计算并更新α、β、δ;（5）如果迭代次数t>tmax则认为灰狼已经找到最优解的位置。
否则返回第三步继续寻找更好的位置。
3 实验仿真在本节中，我们使用仿真来评估改进算法的性能。
我们把无线传感器网络部署在正方形区域内，每个传感器节点的空间坐标都是随机选择的。
所有节点的定位误差是整个仿真过程中唯一的判断标准，从节点总数，锚节点的占总节点数的比例，节点传输半径来分析算法的定位误差。
