㊀２０１８年㊀第５期
仪表技术与传感器
Ｉｎｓｔｒｕｍｅｎｔ㊀Ｔｅｃｈｎｉｑｕｅ㊀ａｎｄ㊀Ｓｅｎｓｏｒ
２０１８㊀Ｎｏ．５㊀
基金项目：江苏省重点研发计划（社会发展）项目（ＢＥ２０１５６９７）收稿日期：２０１７－０４－２７
卓㊀静，高清源，胡㊀平
（南京工业大学计算机科学与技术学院，江苏南京㊀２１１８１６）
㊀㊀摘要：针对存在空洞的各向异性的传感器网络中，ＤＶ－Ｈｏｐ算法由于跳数估计不准确而导致精度降低的问题，提出了一种基于网络空洞边界节点检测的ＤＶ－Ｈｏｐ改进算法㊂首先利用一些可移动的锚节点标记并定位空洞边界上节点的坐标，再通过边界节点进而优化未知节点与信标节点间的跳数值， 最后用改进的加权最小平方法进行未知节点自定位㊂仿真结果表明，当传感器网络中含有面积较大的空洞时，利用提出的算法能够让定位误差很大程度上减少，并且该算法可以更好地应用于实际场景㊂关键词：ＤＶ－Ｈｏｐ；各向异性网络；可移动锚节点；定位误差
中图分类号：ＴＰ３９３㊀㊀㊀文献标识码：Ａ㊀㊀㊀文章编号：１００２－１８４１（２０１８）０５－００８８－０６
ＩｍｐｒｏｖｅｄＤＶ－ＨｏｐＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＤｅｔｅｃｔｉｏｎｏｆＮｏｄｅｓｏｎ
ＢｏｕｎｄａｒｙｏｆＨｏｌｅｉｎＮｅｔｗｏｒｋｓ
ＺＨＵＯＪｉｎｇ，ＧＡＯＱｉｎｇ⁃ｙｕａｎ，ＨＵＰｉｎｇ
（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＮａｎｊｉｎｇＴｅｃｈＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１１８１６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｆｏｒａｓｅｎｓｏｒｎｅｔｗｏｒｋｗｉｔｈｈｏｌｅａｎｉｓｏｔｒｏｐｙ，ｆｏｒｔｈｅｐｒｅｃｉｓｉｏｎｏｆＤＶ－Ｈｏｐａｌｇｏｒｉｔｈｍｄｅｇｒａｄｅｓｉｎａｎｉｓｏｔｒｏｐｉｃｎｅｔｗｏｒｋｓ
ｗｉｔｈｈｏｌｅｓｂｅｃａｕｓｅｏｆｔｈｅｉｍｐｒｅｃｉｓｅｅｓｔｉｍａｔｉｏｎｏｆｔｈｅｈｏｐｃｏｕｎｔ，ａｎｉｍｐｒｏｖｅｄＤＶ－Ｈｏｐａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｄｅｔｅｃｔｉｏｎｏｆｎｏｄｅｓｏｎｔｈｅｂｏｕｎｄａｒｙｏｆｔｈｅｈｏｌｅｉｎｎｅｔｗｏｒｋｓｗａｓｐｒｏｐｏｓｅｄ．Ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｆｉｒｓｔｌｙｕｓｅｄｓｏｍｅｍｏｂｉｌｅａｎｃｈｏｒｓｔｏｌｏｃａｔｅｎｏｄｅｓｏｎｔｈｅｂｏｕｎｄａｒｙｏｆｔｈｅｈｏｌｅ，ｔｈｅｎｔｈｅｂｏｕｎｄａｒｙｎｏｄｅｓｗｅｒｅｕｔｉｌｉｚｅｄｔｏｒｅｆｉｎｅｔｈｅｈｏｐｃｏｕｎｔｏｆｕｎｋｎｏｗｎｎｏｄｅｓｔｏａｎｃｈｏｒｓ，ｆｉｎａｌｌｙａｎｉｍ⁃ｐｒｏｖｅｄｗｅｉｇｈｔｅｄｌｅａｓｔｓｑｕａｒｅｍｅｔｈｏｄｗａｓａｄｏｐｔｅｄｔｏｌｏｃａｔｅｕｎｋｎｏｗｎｎｏｄｅｓ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｌｏｃａｌｉｚａｔｉｏｎｅｒｒｏｒｃａｎ
ｂｅｌａｒｇｅｌｙｄｅｃｒｅａｓｅｄｕｓｉｎｇｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｎｎｅｔｗｏｒｋｓｗｉｔｈｌａｒｇｅｓｉｚｅｏｆｈｏｌｅ，ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｃａｎｂｅｂｅｔｔｅｒａｐｐｌｉｅｄｉｎａｃ⁃ｔｕａｌｓｃｅｎｅ．
Ｋｅｙｗｏｒｄｓ：ＤＶ－Ｈｏｐ；ａｎｉｓｏｔｒｏｐｉｃｎｅｔｗｏｒｋ；ｍｏｂｉｌｅａｎｃｈｏｒｓ；ｌｏｃａｌｉｚａｔｉｏｎｅｒｒｏｒ
０㊀引言
无线传感器网络是由具备传感㊁计算和通信能力的传感器节点组成的，其具有多跳自组织的性质，且应用广泛，对于无线传感器的研究有着重要意义［１－２］㊂总体来说，传感器网络中基于计算模式的协议类型可以分为分布式和集中式㊂虽然集中式的方法不需要计算与存储成本，但是其有着实时定位的性能比较差
［３］
等弊端㊂相比而言，分布式的方法只依赖节点之间的交换信息，在传统意义上来说更加灵活㊂ＤＶ－ｈｏｐ是一种典型的分布式算法，它将节点间
的跳数信息转化为距离信息
［４］
㊂这种方法通过估算，
获得从信标节点位置开始一跳的平均距离和节点之间的跳数，每个未知节点可以获得距离所有信标节点的跳数信息，并结合网络平均跳距通过计算得到估算距离，最后可由极大似然估计法得到未知节点的坐
标［５］㊂但是如果传感器网络中存在网络空洞，节点间跨空洞之间的距离估计会因为空洞的存在变得不准确，这使得测量误差显著增加［６］，此时称含有空洞的传感器网络具有各向异性［７］的性质㊂网络空洞的存在主要有下面几个因素：地理地形因素㊁自然灾害因素㊁节点随机部署或能量耗尽因素㊂
在针对各向异性网络定位精度优化的研究方面，国内外学者提出了多种方法㊂Ｃ．Ｓａｖａｒｅｓｅ［８］等提出了ＲｏｂｕｓｔＰｏｓｉｔｉｏｎ的定位算法，是ＤＶ－Ｈｏｐ算法的优化算法，用添加一种对相位的修正值并通过迭代求精的方
法来减小误差㊂这种方法是在要求传感器节点带有测距功能并且提升计算成本的基础上提高了定位精度㊂
Ｓ．Ｔ．Ｚｈａｎｇ［９］等针对网络空洞，使用一种基于动态跳数距离的定位方法，先计算各个信标节点对的平均单跳距离，再挑选出单跳距离值较大且通过路径规划后经过未知节点的信标节点作为参考点进行计算㊂
㊀㊀
㊀
㊀
㊀第５期卓静等：基于网络空洞边界节点检测的ＤＶ－Ｈｏｐ改进算法
８９㊀㊀
Ａ．Ｅ．Ａｓｓａｆ［１０］等提出的方法中：令每个常规节点和待定位节点只估计到可靠的信标节点或位置已确定节点的距离来提高定位精度㊂Ｓ．Ｚｈａｎｇ［１１］等提出了一种ＨＭＤＳ的算法来减小定位误差，通过探索虚拟节点并且建立２个节点间的最短路径来精确确定它们之间的欧式距离㊂
与以上这些研究工作相比，本文在原有ＤＶ－ｈｏｐ定位算法基础上引入移动锚节点技术
［１２－１３］
检测空洞
边界节点位置的方法形成新的算法，在此命名为ＤＢＮＤＶ－Ｈｏｐ㊂本改进方法将针对各向异性传感器网络中，跨越空洞的节点之间跳数与单跳距离进行修正，并且对未知节点的坐标计算过程进行优化㊂１㊀ＤＶ－Ｈｏｐ传统定位算法
（１）计算信标节点间的最小跳数
所有信标节点（锚节点）向邻居节点广播携带位置坐标和跳数信息的信息数据包，如（ｘｉ，ｙｉ，ｈｊ），其中（ｘｉ，ｙｉ）是信标节点ｉ的坐标，ｈｊ为信标节点距离其他节点的跳数值，并且被初始化为０㊂通过多跳方式，每个信标节点只接受来自其他信标节点的最小跳数㊂
（２）每个信标节点计算自己的平均跳距
用ｎ表示总的信标节点的个数，（ｘｉ，ｙｉ）与（ｘｊ，ｙｊ）
分别为信标节点ｉ和ｊ的坐标信息，ｈｉｊ分别为信标节点ｉ和ｊ之间的最小跳数值㊂未知节点再利用网络中的洪泛法进行广播［１４］，并且只接受距离自己最近的信标节点的平均每跳距离，从而得到与信标节点之间的距离估算值㊂
（３）未知节点利用极大似然估计法计算自己的位
置的估算值，计算方法如下：
（ｘ１－ｘ）２
＋（ｙ１－ｙ）２
＝ｄ１
（ｘ２－ｘ）２＋（ｙ２－ｙ）２＝ｄ２㊀㊀㊀㊀︙
（ｘｎ－１－ｘ）２＋（ｙｎ－１－ｙ）２＝ｄｎ－１
ìî
íï
ïïïïï（１）
式中：（ｘ，ｙ）为未知节点的坐标；ｄｉ为对应的信标节点与未知节点之间的距离㊂
通过式（２）可以得到未知节点的坐标㊂
Ｘ＝（ＡＴＡ）－１ＡＴｂ
（２）
其中，
Ａ＝２（ｘ１－ｘｎ）２（ｙ１－ｙｎ）２（ｘ２－ｘｎ）２（ｙ２－ｙｎ）︙︙２（ｘｎ－１－ｘｎ）
２（ｙｎ－１－ｙｎ）éëê
êê
êêê
ù
û
ú
差速防坠器
ú
úú
防辐射裙úú，ｂ＝ｘ２１＋ｙ２１－ｘ２ｎ－ｙ２ｎ＋ｄ２ｎ－ｄ２１ｘ２２＋ｙ２２－ｘ２ｎ－ｙ２ｎ＋ｄ２ｎ－ｄ２２㊀㊀㊀︙ｘ２ｎ－１＋ｙ２ｎ－１－ｘ２ｎ－ｙ２ｎ＋ｄ２ｎ－ｄ２ｎ－１éëêêêêêêù
û
烟气道úúúúúú，Ｘ＝［ｘ㊀ｙ］Ｔ㊂
２㊀ＤＢＮＤＶ－Ｈｏｐ定位算法
在含有未知规模大小空洞的场景下，传统定位误差产生的主要原因是由于节点分布不均匀情况的存在，导致对跳数与跳距测量值均不准确㊂本节引入一种移动锚节点检测并估计空洞边界节点位置的ＤＢＮＤＶ－Ｈｏｐ定位算法，从虚拟消除空洞的角度来进行改进㊂
此处用Ａ表示信标节点的集合，用Ｔ表示待定位节点的集合，则坐标ａ（ｘｉ，ｙｉ）㊁ｔ（ｘｉ，ｙｉ）分别表示部署于同一各向异性传感器网络的信标节点与未知节点的坐标㊂与此同时，引入了一部分可移动的信标节点，并且其利用自身的特殊性质可运动至空洞边界附近㊂整个改进的过程可分为以下的４个部分㊂２．１㊀边界节点标识阶段
由于定位误差主要来源于空洞的存在，所以
ＤＢＮＤＶ－Ｈｏｐ算法的准备工作中首先需要对空洞边界进行探寻㊂在这里采用的是文献［１５］中的分布式算法，该方法采用最短路径树［１５］的一种特有结构来探寻并检测空洞的边界㊂起始阶段在网络空洞的一端分离，并且最终在另一端聚合是传感器网络中最短路径树自然流的具有一种性质
㊂通过其分离㊁聚合的过程可以探测出传感器网络中各种不同形状与大小的空洞㊂
利用上述方法确定空洞边界节点后，利用移动锚节点的可移动特性，对空洞边界节点（记作集合）进
行初始位置的估计㊂在运动过程中，移动锚节点首先进行路径规划［１６－１７］，根据最短的路径逐跳移动至空洞边界，并且在移动过程中以ｒ为通信半径来广播位置信息，边界节点可根据被传播的信息大致估算出自身坐标㊂
ｂ（ｘｉ，ｙｉ）＝（ｘｍａ＋ｒｃｏｓθ，ｙｍａ＋ｒｃｏｓθ）
（３）
式中：（ｘｍａ，ｙｍａ）为移动锚节点的坐标；θ为０ ２π之间的任意值㊂
２．２㊀跳数值估计阶段
边界节点估算出自己的位置后，将进行第１次洪泛，所有信标节点开始广播信息包㊂根据距离矢量交换协议，所有未知节点首先得到与各个信标节点之间初始的跳数ＨｏｐＣ（Ｔｉ，Ａｊ）㊂为避免空洞对测量数据的
㊀㊀㊀㊀㊀９０㊀ＩｎｓｔｒｕｍｅｎｔＴｅｃｈｎｉｑｕｅａｎｄＳｅｎｓｏｒＭａｙ．２０１８㊀
干扰，本阶段是利用边界节点和与其间不跨越空洞（同侧）且距离最近的信标节点来估计网路的平均跳距㊂
由上述边界节点通过上一阶段估算出的坐标值，可将计算出的与信标节点之间距离转换成为跳数信息，并应用在下一阶段对跳数改进的过程中㊂由式（４）可以得到每个边界节点与信标节点间的距离为Ｄ（Ｂｉ，Ａｊ）＝［ａｉ（１）－ｂｊ（１）］２＋［ａｉ（２）－ｂｊ（２）］２
（４）每一个空洞边界节点由式（５）可估算出其自身的网络跳距㊂
ＨｏｐＤ（Ｂｉ）＝ｍｉｎＨｏｐＣ（Ｂｉ，Ａｊ）（Ｄ（Ｂｉ，Ａｊ）
ＨｏｐＣ（Ｂｉ，Ａｊ））（５）式中ＨｏｐＣ（Ｂｉ，Ａｊ）为边界节点Ｂｉ与信标节点Ａｊ之间的跳数㊂
２．３㊀跳数值改进阶段
本阶段通过全网洪泛来对跳数信息进行优化，是最核心的一个阶段㊂首先，每一个空洞边界节点根据式（５）检测出的网络跳距来修正并重新定义自身到各信标节点之间的跳数㊂
ＨｏｐＣｎｅｗ（Ｂｉ，Ａｊ）＝Ｄ（Ｂｉ，Ａｊ）
ＨｏｐＣ（Ｂｉ，Ａｊ）（６）式（６）得到的是边界节点与各个信标节点之间的跳数，由于经历第１次洪泛后边界节点已经获得一个较精准的网络平均跳距，此时的信标节点与边界节点可以为跨越空洞的２个节点，得到的跳数被称为虚拟跳数㊂在得到估算的虚拟跳数后，传感器网络中所有边界节点开始扩散由式（６）得到的虚拟跳数信息，即为第２次全网络洪泛过程，此时涉及到时间同步性［１８］㊂在该过程中，每个边界节点参照距离矢量交换协议，将根据与各个信标节点的跳数值延时广播相应的信标节点信息㊂比如：边界节点与信标节点之间通过式（６）得到跳数值为１０跳，那么经过了１０个单位时间以后，边界节点才会继续向它周边节点广播与信标节点间的跳数值信息㊂在上一阶段经过第一次洪泛，未知节点得到与各个信标节点的初始跳数ＨｏｐＣ（Ｔｉ，Ａｊ）㊂此阶段未知节点时刻将新接受的跳数与ＨｏｐＣ（Ｔｉ，Ａｊ
）相比较，只有小于原始跳数，才能计一跳数并转发至下一节点
，如果不满足此条件，则中止转发过程㊂经典算法与ＤＢＮＤＶ－Ｈｏｐ算法在含空洞网络中的跳数估计分别如图１（ａ）和图１（ｂ）所示㊂在完成对跳数值的优化后，每个未知节点将经过整个洪泛过程被传送到自身的网络跳距取平均，优化
（ａ）ＤＶ－Ｈｏｐ算法
㊀
（ｂ）ＤＢＮＤＶ－Ｈｏｐ算法
图１㊀算法跳数估计
网络跳距的值㊂计算各个未知节点的网络平均跳距如式（７）所示：
ＨｏｐＤａｖｇ＝
ðｉＨｏｐＤ（Ｔｒｅｃ）
ｎｒｅｃ
（７）
式中：ＨｏｐＤ（Ｔｒｅｃ）为未知节点接受到的已优化跳距值；ｎｒｅｃ为接受到跳距信息的未知节点的个数㊂
２．４㊀确定未知节点坐标
每个未知节点得到优化的跳数后，将其与网络平均跳距相乘，得到距离估计值ｄ，然后再利用相应改进算法计算得到自身坐标㊂具体计算方法如下：在传统ＤＶ－Ｈｏｐ极大似然法的求解中，由于使用的跳数与跳距值都存在偏差，所以得到的距离值ｄｉ也是不准确的㊂在本节中改进的计算方法中改为加权最小平方法，首先用前ｎ－１个方程分别减去第ｎ个方程，然后两边再平方并简化：
－２（ｘ１＋ｘｎ）ｘ－２（ｙ１＋ｙｎ）ｙ＋２ｋ＝ｄ２１＋ｄ２ｎ－（Ｅ１＋Ｅｎ）
－２（ｘ２＋ｘｎ）ｘ－２（ｙ２＋ｙｎ）ｙ＋２ｋ＝ｄ２２＋ｄ２ｎ－（Ｅ２＋Ｅｎ）
︙
－２（ｘｎ－１＋ｘｎ）ｘ－２（ｙｎ－１＋ｙｎ）ｙ＋２ｋ＝ｄ２ｎ－１＋ｄ２ｎ－（Ｅｎ－１＋Ｅｎ）ì
î
í
ï
ïï
ï
ïï
（８）其矩阵形式为ＱＺ＝Ｈ，其中Ｑ㊀Ｚ㊀Ｈ分别为：
Ｑ＝
－２（ｘ１＋ｘｎ）－２（ｙ１＋ｙｎ）２
－２（ｘ２＋ｘｎ）－２（ｙ２＋ｙｎ）２
︙︙︙
－２（ｘｎ－１＋ｘｎ）－２（ｙｎ＋１＋ｙｎ）２
é
ë
ê
ê
ê
ê
êê
ù
û
ú
ú
ú
ú
úú
（９）
Ｈ＝
ｄ２１＋ｄ２ｎ－（Ｅ１＋Ｅｎ）
ｄ２２＋ｄ２ｎ－（Ｅ２＋Ｅｎ）
︙
ｄ２ｎ－１＋ｄ２ｎ－（Ｅｎ－１＋Ｅｎ）
é
ë
ê
ê
ê
ê
êê
ù
û
ú
ú
ú
ú
úú
（１０）
Ｚ＝［ｘ㊀ｙ㊀ｋ］Ｔ（１１）其次，本方法中采用加权处理的方法㊂在定位过程中，假如未知节点距离一个信标节点距离越远，则
㊀㊀㊀㊀㊀第５期卓静等：基于网络空洞边界节点检测的ＤＶ－Ｈｏｐ改进算法９１㊀㊀
两者间的跳数就会越大，那么它们之间的误差就会增
大㊂为了控制定位误差，相应的加权值就要设定为比
较小㊂在这里用Ｗ来表示加权矩阵，加权值由节点间
跳数值的平方来表示㊂对于一个未知节点ｔ，它的加
权矩阵如下：
Ｗ＝ｗｐ，１０ ０
０ｗｐ，２ ０
︙︙︙
００ ｗｐ，ｎ－１
é
ë
ê
ê
ê
ê
êê
ù
û
ú
ú
ú
ú
úú
（１２）
ｗ＝（１
ＨｏｐＣｎｅｗ（Ｂｉ，Ａｊ））２（１３）式中：ｗｐ为待定位节点ｔ关于信标节点ａ的加权系数；ＨｏｐＣｎｅｗ（Ｂｉ，Ａｊ）为上阶段计算出的边界节点与信标节点之间优化的跳数㊂
可得到Ｚ矩阵的具体方程组如下：
Ｚ＝（ＱᶄＷᶄＷＱ）－１ＱᶄＷᶄＷＨ（１４）式中前两项为待定位节点横纵坐标的估计值㊂
改进的计算方法与原始计算方法比较的区别是：求解方程组时改进为先平方再相减，并且引入权值的思路来控制误差㊂通过两种计算方法修正值的比较，可得出本改进计算方法的修正值较小［１９］，即定位精度高㊂
３㊀ＤＢＮＤＶ－Ｈｏｐ算法流程与通信复杂度
本节主要给出ＤＢＮＤＶ－Ｈｏｐ算法的主要流程图，并且分析ＤＢＮＤＶ－Ｈｏｐ算法的通信复杂度，同时与传统ＤＶ－ＨＯＰ算法相比较㊂
３．１㊀ＤＢＮＤＶ－Ｈｏｐ算法流程图
ＤＢＮＤＶ－Ｈｏｐ算法流程图如图２所示㊂
图２㊀ＤＢＮＤＶ－Ｈｏｐ算法流程图
３．２㊀ＤＢＮＤＶ－Ｈｏｐ算法复杂度分析
对于ＤＶ－Ｈｏｐ算法，根据其定位过程原理，可得其算法复杂度为Ｏ（２ˑｎˑｎＡ）㊂
在改进算法中，主要是由于在第１阶段：初始跳数估计阶段以及第２阶段：跳数优化阶段牺牲了部分通
信消耗，跳数估计效果才达到一定的优化㊂在第１阶
段中，边界节点根据移动锚节点的性质估算出自身位
置后，所有信标节点开始广播自身信息包，针对相同
信标节点的信息，网络中节点只会转发其一次㊂这里
用ｎＡ表示节点总数量，表示信标节点数量，所以在初
始跳数估计阶段通信复杂度为Ｏ（ｎˑｎＡ）㊂在第２阶段，传感器网络中所有节点都需要转发已修正的网络
平均跳距信息至未知节点，此时考虑的通信复杂度最
小值为ｎ㊂如果当未知节点与信标阶段是同侧不跨越
空洞的位置关系时，节点并不需要转发信标节点的信
息㊂只有当空洞的存在干扰了信标节点的自定位时，
才需要转发并记为通信消耗，所以跳数优化阶段的复
杂度最大为Ｏ（ｎˑｎＡ）㊂由于总的复杂度为２个阶段的值相加，所以ＤＢＮＤＶ－Ｈｏｐ算法通信复杂度范围在Ｏ（ｎˑ（ｎＡ＋１））到Ｏ（２ˑｎˑｎＡ）间㊂
综上所述，ＤＶ－Ｈｏｐ定位算法与ＤＢＮＤＶ－Ｈｏｐ定
位算法的通信复杂度在数量级的层面上差异不大㊂４㊀仿真与分析
本节对ＤＢＮＤＶ－Ｈｏｐ算法与ＤＶ－Ｈｏｐ算法的性能
进行分析对比㊂通过设置不同的场景，考察不同参数
对于定位误差的影响㊂
４．１㊀仿真模型设定
在１００ｍˑ１００ｍ的正方形仿真区域内，网络被划
分为网格形式，节点将以任意形式小距离偏离网格中
线与线形成的交点，这样可以使传感器均匀的形式部
署于整个控制区域㊂节点的总数量设定为在２６８ １１５０的范围内，通信半径设定为８ｍ，信标节点的数量设定为５ ２０的范围内㊂
为了评估算法的稳定性和有效性，本次仿真中选
用了２种不同的误差定义指标：
网络平均距离估计误差：指所有未知节点每跳距
离实际测量与估计的平均偏差㊂
网络平均距离估计误差可由式（１５）表示
ｅｄｉｓｔ＝１ｎｔˑｎａðｎｔｉ＝１ðｎａｊ＝１｜ｄｉｊ－ｄᶄｉｊ｜（１５）式中：ｎｔ和ｎａ分别为未知节点和信标节点的数量；ｄｉｊ和ｄᶄｉｊ分别为未知节点与信标节点之间的真实距离和估计距离㊂
节点定位误差：指所有未知节点估计位置与实际
位置的平均偏差㊂
节点定位误差可由式（１６）表示：
ｅｌｏｃ＝１ｎðｎｉ＝１ ｘｉ－ｘｉ （１６）
㊀㊀
㊀
㊀
㊀９２
㊀ＩｎｓｔｒｕｍｅｎｔＴｅｃｈｎｉｑｕｅａｎｄＳｅｎｓｏｒ
Ｍａｙ．２０１８㊀
式中：ｎ为节点总数量；ｘｉ与ｘｉ分别为节点ｉ的具体位
置和估计位置的横坐标㊂
公牛辅助此处的二范数体现的为矢量空间中误差长度的概念㊂
４．２㊀定位效果及误差分析
下面３组仿真在设有不同参数的场景中进行，使用Ｍａｔｌａｂ２０１４ｂ软件，将ＤＢＮＤＶ－Ｈｏｐ算法的定位误差进行分析并与ＤＶ－Ｈｏｐ传统定位算法以及ＲｏｂｕｓｔＰｏｓｉｔｉｏｎ算法进行对比㊂
场景１：信标节点数量恒定设置为１１，传感器网络
中圆形（凸）空洞半径设置为３０ｍ，总节点数量在的２６８ １１５０范围内变化㊂图３为不同节点数量下算法定位误差比较
㊂
图３㊀不同节点数量下算法定位误差比较
由图３可知，在同等条件下，ＤＢＮＤＶ－Ｈｏｐ算法的定位误差明显低于另外２种算法㊂随着节点数目的增加，节点间的连通度相应增加，这３种算法的定位性能也都得到了优化㊂当节点总数目大于一定值时，３种算法的定位误差陡然减小同时趋于平缓，并且ＤＢＮＤＶ－Ｈｏｐ算法受节点总数量的影响最小㊂
场景２：节点总数量恒定设置为４６９，传感器网络
中圆形（凸）空洞的半径设置为３０ｍ，信标节点数量在５到２０的范围内变化㊂图４为不同信标节点数量下算法定位误差比较
㊂
图４㊀不同信标节点数量下算法定位误差比较
由图４可见，随着信标节点数量不断增加，３种算
法的误差都在减小且趋于稳定㊂在同等条件下，ＤＢＮＤＶ－Ｈｏｐ算法的位置定位误差距离要比其
他２种算法分别减小６０％和７０％左右㊂当信标节点数目大于１５时，ＤＢＮＤＶ－Ｈｏｐ算法定位效果不显著，提升的幅度相应减小㊂
场景３：节点总数量恒定设置为４６９，信标节点数量恒定设置为１１，网络半径长度在２０ ４０ｍ范围内以５ｍ为间隔均匀增加㊂空洞大小对定位算法性能影响见表１㊂
表１㊀空洞大小对定位算法性能影响
ｍ
空洞半径大小平均距离估计误差节点定位误差ＤＶ－ＨｏｐＤＢＮＤＶ－Ｈｏｐ
ＤＶ－ＨｏｐＤＢＮＤＶ－Ｈｏｐ
２０３．４２２．７８５．００２．３４２５３．９５２．６５７．１７２．７９３０５．３２２．４３９．８１
２．６６３５７．８９２．５６１５．８６２．６９４０
８．７３
２．８５
１９．４４２．９１
多媒体电教㊀㊀由表１可知，当传感器网络内部空洞半径较小时，两种算法的定位误差相差不大㊂随着空洞半径的均匀增加，传统定位算法的定位误差逐渐变大，且误差加大的速率变快㊂当传感器网络中空洞半径变为仿
真实验最大的４０ｍ时，ＤＢＮＤＶ－Ｈｏｐ算法的优良定位性能更显著㊂总体来说，在利用部分锚节点的可移动性后，对于存在明显规模空洞的网络，ＤＢＮＤＶ－Ｈｏｐ算法定位精度较ＤＶ－Ｈｏｐ经典算法而言提升了７０％左右，极大减小了由于空洞所导致的误差㊂
由于ＤＢＮＤＶ－Ｈｏｐ算法目的是要消除网络空洞带来的跳数估计不精确而导致的定位误差，所以本场景对网络中各种半径大小不一的空洞进行仿真实验，有着一定的研究意义㊂为使场景３的定位仿真效果更加清晰，这里给出了空洞半径为１５ｍ和３０ｍ的仿真效果图，如图５㊁图６所示㊂ ㊃ 表示未知节点的真实位置， ∗ 表示未知节点的定位位置㊂用连线连结未知节点的实际位置和估计位置，则两者间的连线表示定位误差㊂
由图５可知，当空洞半径较小时，虽然ＤＢＮＤＶ－Ｈｏｐ算法定位精度有所提高，但是优化效果不
显著㊂从图６（ａ）中可以看到，当网络中存在明显的空洞时，ＤＶ－Ｈｏｐ算法的定位误差极大，整体的定位趋势是往网络的边缘方向扩张㊂而图６（ｂ）中由于网络中通过
边界节点削弱了空洞的干扰，ＤＢＮＤＶ－Ｈｏｐ算法的定位效果良好，未知节点的实际位置点与估计位置点的连线较短，即造成的定位偏差较小㊂
>盖革计数管
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议