基于割圆术的DV-Hop全...SNs节点定位算法改进研究_赵晴.pdf

第 42 卷第 2 期2023 年 3 月Vol.42No.2Mar.2023JOURNAL OF HENAN POLYTECHNIC UNIVERSITY（NATURAL SCIENCE）河南理工大学学报（自然科学版）基于割圆术的 DV-Hop全局优化 WSNs节点定位算法改进研究赵晴，徐震（武汉轻工大学 电气与电子工程学院，湖北 武汉 430048）摘要：为提升 DV-Hop（distance vector-hop）算法定位精度水平，提出一种基于割圆术的 DV-Hop全局优化（circle-cutting technique for global optimization of DV-Hop algorithm，CTGO-DV-Hop）算法。该算法精确了最小跳数，引入权值模型对全部锚节点的平均单跳距离进行优化，并采用加权最小二乘递推算法对未知节点坐标进行拟合。实验测试多种因素对于算法的影响，结果表明，所 提 出 的 CTGO-DV-Hop 算 法 表 现 出 良 好 的 性 能，相 较 于 DV-Hop、OCSLC-DV-Hop 和WOCS-DV-Hop，平均定位误差的最大降幅为 70%左右，适用于构建节点数目大、锚节点比例低的无线传感器网络系统。关键词：无线传感器网络；DV-Hop；割圆术；全局优化；定位中图分类号：文献标志码：A文章编号：1673-9787（2023）2-127-7Study on improvement of WSN node localization algorithm based on CTGO-DV-HopZHAO Qing，XU Zhen（School of electrical and electronic engineering，Wuhan Polytechnic University，Wuhan 430048，Hubei，China）Abstract：In wireless sensor networks，location information is one of the crucial and imperative elements.The DV-Hop（distance vector-hop）algorithm is a typical range-free algorithm with various application scenarios，and it is of significant value to improve its localization performance.To improve the localization accuracy level，a circle-cutting technique for global optimization of DV-Hop algorithm（CTGO-DV-Hop）was proposed.The algorithm was accurate in the minimum number of hops.The weight model was introduced to optimize the average single-hop distance of all anchor nodes，and the weighted least squares recursive algorithm was used to fit the unknown node coordinates.The effects of various factors on the algorithm were experimentally tested.The results showed that the proposed CTGO-DV-Hop localization scheme exhibited good performance，it achieved a maximum reduction of about 70%in the average localization error compared with DV-Hop，OCSLC-DV-Hop，and WOCS-DV-Hop，and was suitable for building wireless sensor network systems 赵晴，徐震.基于割圆术的 DV-Hop 全局优化 WSNs 节点定位算法改进研究 J.河南理工大学学报（自然科学版），2023，42（2）：127-133.doi：10.16186/ki.1673-9787.2021080016ZHAO Q，XU Z.Study on improvement of WSN node localization algorithm based on CTGO-DV-HopJ.Journal of Henan Polytechnic University（Natural Science），2023，42（2）：127-133.doi：10.16186/ki.1673-9787.2021080016收稿日期：2021-08-28；修回日期：2022-01-14基金项目：国家自然科学基金资助项目（61373091）；湖北省自然科学基金资助项目（2017CKB893）第一作者简介：赵晴（2000），女，湖北石首人，硕士生，主要从事无线传感器网络研究。Email：通讯作者简介：徐震（1974），男，河南信阳人，博士，副教授，主要从事无线传感器网络及光纤通信方面的教学和研究工作。Email：O S I D2023 年第 42 卷河南理工大学学报（自然科学版）with a large number of nodes and a low percentage of anchor nodes.Key words：wireless sensor network；DV-Hop；circle-cutting technique；global optimization；localization0引 言无 线 传 感 器 网 络（wireless sensor networks，WSNs）拥有高度的灵活性、容错性、自组性和快速部署等优势1-3，位置信息是其监测数据的基本要素之一。随着智能军事4、智慧医疗5、精准农业6、灾害预警7、水下探测8等领域的需求推动，对传感器节点的精确度有了更高要求。因此，研究节点定位方案或算法有着重要的理论意义和应用价值。定位方案包含基于测距和无需测距两种类型9，近年来，国内外学者对此做了大量探索和研究。距 离 向 量 跳 数10（distance vector-hop，DV-Hop）作为无需测距的方案之一，具有较强的普适性、较低的设备成本和较好的覆盖面等优势11，可部署在偏远、有毒等条件苛刻的环境中，还可以根据需要协同执行较为复杂的监测任务。DV-Hop的定位可分为 3个阶段，即连通性检测、距离估计和未知节点位置估计12。由于标准算法的平均跳距对锚节点个数和拓扑结构具有依赖性，以及最小二乘法在位置拟合上不够准确，各种改进算法被相继提出。A.Kaur 等13采用单移动锚节点和基于网格的路径规划模型对节点进行逐一定位；WANG P H 等14提出基于 NSGA-的多目标 DV-Hop 定位算法，对煤矿隧道、峡谷地形和 湖 海 地 形 等 部 署 环 境 进 行 了 测 试；GUI L Q等15提出一种基于分布式连接的 CCDV-Hop 算法，建立以任意两个节点之间的真实连通性为约束条件来优化定位精度。上述改进措施采用了确定性改进策略或随机优化策略。针对 DV-Hop 在距离估计的误差和位置拟合时的模型缺陷，本文提出一种基于割圆术的全局优化 DV-Hop 定位方案（circle-cutting technique for global optimization of DV-Hop algorithm，CTGO-DV-Hop）。运用割圆术思想，引入分割因子对跳数区间进行分割，采用加权模型对平均跳距进行校正，选用加权最小二乘递推算法对未知节点的位置进行计算，以达到全局优化的目的。测试多种因素对算法的影响，以验证该方案的定位精度和鲁棒性。1DV-Hop定位方案和误差分析1.1DV-Hop定位过程DV-Hop 算法10依据 WSNs 中的连通性和节点间多跳转发原理对未知节点位置进行计算，由3个阶段组成。阶段 1。确定未知节点与各锚节点的最小跳数。锚节点（人工标定或配备国产北斗卫星导航系统16，全球定位系统17等）以洪泛方式进行广播数据包，其他节点对数据包进行存储转发，记录下最小跳数。阶段 2。计算实际跳数距离，计算式为Hop_sizek=k tXk-Xt2k tHopk，t，（1）式中：Hop_sizek和Xk=xk，ykT分别为锚节点 k 的平均每跳距离和横纵坐标；Hopk，t为锚节点 k 与 t之间最短路径的最小跳数。计算未知节点 m到锚节点 k的距离：dm，k=Hopm，k Hop_sizek。（2）阶段 3。估计未知节点位置。利用三边定位法或多边定位法计算未知节点位置。假设部署环境中有 n个锚节点，有矩阵|(x1-xm)2+(y1-ym)2(x2-xm)2+(y2-ym)2(xnm-xm)2+(ynm-ym)2=|d2m，1d2m，2d2nm，m，（3）整理消掉平方项，可得 n-1 维线性方程组AX=B。由于实际测量存在误差，设误差向量为E，此时方程组为AX+E=B，（4）其中，A=|2(xnm-x1)2(xnm-x2)2(xnm-xnm-1)2(ynm-y1)2(ynm-y2)2(ynm-ynm-1)|，（5）B=|d2m，1-d2nm，m-x21+x2nm-y21+y2nmd2m，2-d2nm，m-x22+x2nm-y22+y2nmd2nm-1，m-d2nm，m-x2nm-1+x2nm-y2nm-1+y2nm，（6）128第 2 期赵晴，等：基于割圆术的 DV-Hop全局优化 WSNs节点定位算法改进研究X=xm，ymT。（7）为了降低 n-1维误差向量 E 对定位结果的影响，用最小二乘法使其模的平方最小：J=B-AX22=XTATAX-2XTATB+BTB，（8）对X求导，并令其导数等于 0。当rank(A)=n-1时，唯一解为X=(ATA)-1ATB，（9）X即为未知节点 m的位置坐标。1.2误差分析DV-Hop算法中，使用跳数距离代替直线距离存在较大误差。图 1为一个 10个节点随机分布的网络，根据式（1）可计算锚节点 A1，A2 的Hop_size分别为 37.667 m 和 34.000 m。由于网络中可以直接进行通信的两节点间的跳数值被记为 1，但能和同一节点直接通信的其他节点，实际距离存在差异。对于整个网络，会出现诸多节点实际距离相差较大，但最小跳数相同的情况。图 1 中未知节点 2与锚节点 A1，A2的最小跳数均为 2，但实际距离相差极大。阶段 2 中，未知节点接收的是距离最近的锚节点估计平均跳距。但是仅参考一个锚节点，未考虑其他节点的影响力问题，不能反映出网络中全部节点的部署情况。阶段 3中，位置拟合时，使用最小二乘法。该方案计算量大，存储量大，对于节点能量有限的WSN 不够友好，可能无法提供连续稳定的定位过程。2基于割圆术的全局优化 DV-Hop定位方案2.1割圆术割圆术由数学家刘徽提出，用圆内接正多边形的面积无限逼近圆的面积，以此求得圆周率。在阶段 1中使用割圆术理论，将跳数值在0，1内进行分割。根据文献 12，误差是契合均值为 0、方差为R/3的正态分布；文献 18 表明，误差随着跳数的增加而增加，最终收敛到R/4。因此，模拟割圆术内的正三角形和正四边形分割方式，如图2所示。2.2加权最小二乘递推算法为解决最小二乘法的存储量、误差向量的权重等问题，考虑选用加权最小二乘递推算法。这样，能在网络中少部分节点失效或新节点加入等情况时，提供稳定的定位过程。由于不同的测距