改进DV-Hop算法在微网中的应用

王乾元，刘振兴，张 永，蔡 彬

(武汉科技大学 信息科学与工程学院，湖北 武汉 430081)

0 引 言

随着科学技术的发展和不断进步，许多技术运用于智能电网中，例如计算机网络技术、传感器技术，以及现场总线等技术[1,2]，这就意味着智能电网的规模增大、结构越来越复杂、分布式电源应用种类繁多，使得电力行业的安全问题成为了目前国内外的研究热点。因此，当发生故障时，需要对故障发生点进行准确定位。恶劣的环境对微网的监测造成了很大困扰，传统的故障定位系统非常依赖于硬件设施且成本高，因此本文引入无线传感器网络(wireless sensor networks，WSN)来提高故障定位效率[3]。

无线传感器网络是结合信息采集、传输、处理为一体的智能信息系统，在很多领域都具有广阔的应用。无线传感器网络是由大量低功耗、可进行数据感知和处理的无线传感器节点通过自组织多跳的方式形成的网络[4]。基于无线传感器网络的技术研究主要集中在目标发现与定位、路由协议及路由恢复等方面，本文将对其定位技术在微电网中的应用进行探讨。

近年来许多学者对无线传感器节点的定位技术进行了大量研究，主要分为两大类：基于测距(range-based)的方式和基于无测距(range-free)的方式两种[5]。基于测距法虽然对系统故障点定位的精度较高，但是对硬件的需求高，成本相对于免测距法也高，因此实际微网监测系统中，免测距法更受青睐，其中尤为通用的是DV-Hop算法。毕竟DV-Hop算法相比于其它免测距算法具有低成本、对信标节点比例要求较少、定位精度较高等优点。因此本文在不增加额外硬件设备的前提下，结合微网中分布式电源的分布情况，深入分析原始DV-Hop算法的缺陷，在跳数值和节点坐标两方面进行了修正，提出了一种改进的DV-Hop算法。

依据微网分布式电源监测系统建立相应的仿真模型，将其转化为无线传感器网络节点定位问题。仿真结果表明，本文改进的定位算法相比原始DV-Hop算法、文献[6,7]所提出的算法，误差有所降低，可以更好应用于微网监测中。

1 基于WSN的微网监测系统

微网运行过程中，分布式电源的数据监测系统如图1所示，监测系统架构主要由数据采集子网、数据传输网络和控制中心组成[8]。故障定位过程可分3个步骤进行：①信号的采集，由无线传感器完成。②将采集的信号以自组织多跳的方式传输给网关(汇聚节点)。③将网关处理后的信号传给控制中心，该环节按照一定的故障检测方法处理所接收的信号，最终判断出故障的类型和发生的位置。传感器节点的位置对于在线检测系统尤为重要，所以在本文中，改进算法的主要工作便是对传回故障信息的节点进行定位。

图1 微网中分布式电源模块监测系统

图1无线监测区域中，一些位置信息已知的传感器节点安装在少数设备上，可将这一部分设备看作无线传感器网络中的锚节点。因此图1监测区域的分布式电源分布图可以抽象为图2的仿真场景。

图2 监测网络仿真场景

图2中正方形边框表示无线传感器网络的监测区域，区域内的三角形是锚节点；而区域内的圆点是未知节点。

锚节点位置已知，本文改进算法再根据锚节点位置定位未知节点，监控中心就可判断故障位置，安排工作人员进行检修。

2 原始DV-Hop算法

DV-Hop定位算法由Niculescu等提出[9],可以更好解决周围只少数邻居锚节点的未知节点定位问题。图3是9节点小型网络，DV-Hop算法的定位过程就以此网络来举例说明。该算法主要分为三阶段[10-12]。

图3 小型网络拓扑结构

(1)记录每个节点间的最小跳数。

每个锚节点Ai以洪泛的形式广播包含其自身标识IDi、位置信息(xi,yi)和初始跳数为0的数据包，这个跳数值将在广播过程中增加，用hopij表示，以上信息记做{IDi,(xi,yi),hopij}。按照通用的距离矢量交换协议，并用最短路径算法获得所有节点间的最小跳数hopij。例如：图1小型网络中，锚节点A1与锚节点A2间的最小跳数为4，未知节点N1与未知节点N3间的最小跳数为2，锚节点A2与未知节点N4间的最小跳数为2。

(2)计算未知节点到锚节点的距离。

步骤(1)中每个锚节点之间的最小跳数已知，由于锚节点是位置信息可知的传感器节点，因此锚节点间的实际距离容易获得。此时利用式(1)可估算每个锚节点的平均每跳距离

(1)

其中，Hopsizei是锚节点Ai的平均每跳距离，(xi,yi)、(xj,yj)分别是锚节点Ai与锚节点Aj的坐标，n是锚节点个数，hopij表示步骤(1)中所获得的各节点间的最小跳数。

例如：图3所示，利用式(1)求解各锚节点的平均每跳距离。锚节点A1、A2、A3的平均跳距分别为：Hopsize1=(d1+d3)/(4+4)，Hopsize2=(d1+d2)/(4+3)，Hopsize3=(d2+d3)/(3+4)。未知节点与各锚节点之间的估计距离由式(2)计算

dij=Hopsizei*hopij

(2)

Hopsizei为未知节点Ni从最近锚节点处获得的平均跳距，例如N1从A1处获取平均跳平均跳距Hopsize1，N3从A2处获取平均跳平均跳距Hopsize2，N5将A3的平均跳平均跳距作为自身平均跳距，dij表示未知节点Ni与锚节点Aj的估计距离。

以图3中未知节点N1为例，由式(2)可计算出N1与锚节点A1、A2、A3的距离分别为：1*Hopsize1、2*Hopsize1、3*Hopsize1。

(3)未知节点的坐标定位。

步骤(2)求得估计距离后，可利用如下方法获得未知节点的估计坐标：

假设未知节点的坐标为(xk,yk)，d1,d2,d3,…,dn为未知节点到n个锚节点的估计距离，即步骤(2)中所得的结果

(3)

从式(3)的第1个方程开始依次减去最后一个方程，可得未知节点最终的估计坐标

X=(ATA)-1ATB

(4)

其中

3 改进IDV-Hop算法的提出

3.1 误差分析及改进方案

本节通过分析原始DV-Hop算法的三步骤缺陷[10-12]，针对以下两个方面给出了相应的改进方案，有利于提高故障定位精度并且降低成本。

误差1：各节点间的跳数值不精确导致后续步骤存在较大误差。

改进方案1：针对以上算法的不足，本文引入一种基于双通信半径的改进方案。许多文献提出锚节点设置多个通信半径，定位过程中锚节点以泛洪的形式广播信息至邻居节点，会存在较大的能量消耗，影响网络生命周期，因此采用基于双通信半径的改进算法[6]，此方案假设前提是锚节点以R和R/2通信半径广播自身信息，而未知节点只有一种通信半径，即R，但是仍存在缺陷。因为在泛洪广播信息时，若广播信息的是未知节点，接收信息的是锚节点，实际两者距离R/2以内的跳数值应为0.5跳的，按照文献[6]却会记作1跳，必然存在很大的误差，网络规模越大，跳数值越多，累积误差就会越大。因此在第一次泛洪广播自身信息的过程中，即当发射节点为锚节点，接收节点是未知节点时，接收节点应记录与自己相距0.5跳的锚节点的标识IDi，在第二次泛洪广播时，锚节点接收到具有自身IDi标识的信息，跳数值加0.5后转播，而不是加1后转播给邻居节点。其它步骤与原始DV-Hop算法一致，为了便于描述，此改进方案称为DV-Hop(A)。

误差2：未知节点的坐标不精确。

改进方案2：针对以上算法的不足，本文结合DV-Hop(A)的改进方案提出最终改进算法IDV-Hop。原始DV-Hop算法和DV-Hop(A)算法直接使用三边测量法或者最大似然估计法求解未知节点的坐标，此方法导致有部分节点的坐标超出监控区域，因此利用反转法对估计坐标进行粗调整。根据微电网中分布式电源的实际分布情况，监控范围设置在100m*100m范围内，分布式电源模块随机分布在此区域内，DV-Hop(A)算法所得的估计坐标会超出此范围，首先利用下式进行初步修正

(5)

反转法具体实现过程:微网分布式电源模块实际位置图2已经给出，模拟放在100m*100m的范围内。已知位置的设备不需要再定位，图中三角形已经标出,主要观察定位算法对未知节点(即图中的圆点)的坐标定位是否准确。图4是DV-Hop(A)算法定位后的节点分布图，其中有的圆点超出了100m*100m这个范围，已用圆圈表示。反转法的目的就是对这些未知节点进行坐标初步修正，修正后的节点坐标如图5所示。

图4 DV-Hop(A)定位算法节点分布

图5 反转法修正后的节点分布

图5可以看出，在DV-Hop(A)算法上再引入反转法确实可以使所有节点都在100m*100m模拟范围内，不会出现超出范围的未知节点，达到改进目的。

最后结合文献[7]所述的坐标修正方法，这样获得的未知节点的估计坐标更接近实际值。文献[7]利用的是一个与跳数相关的动态权值wk修正坐标,如式(6)所示

(6)

其中，wk是未知节点k的动态权值，hopknearest为未知节点k与最近锚节点间的最小跳数，hopki为未知节点k与锚节点i间的跳数，n为锚节点个数，N为未知节点个数。

3.2 算法流程图

本节介绍IDV-Hop算法的具体实现步骤如图6所示。

步骤1 初始化监控区域，设置无线传感器节点个数，锚节点个数。如改进方案1所述锚节点以两种通信半径泛洪广播数据包，未知节点以一种通信半径转播数据包，直到记录各节点间的最小跳数值该过程停止，其中考虑了接收节点为锚节点的特殊情况。

步骤2 利用式(1)得出每个锚节点平均跳距后，未知节点从最近锚节点处获取平均每跳距离，并结合步骤1中的最小跳数用式(2)计算该未知节点与各个锚节点的估计距离。

步骤3 利用最小二乘法得出未知节点的估计坐标，使用本文提出的反转法进行初步修正，最后用动态权值进行进一步修正，所得的坐标即为本文IDV-Hop算法的最终结果，更加接近实际坐标，定位过程结束。

图6 IDV-Hop算法流程

4 算法仿真分析

4.1 仿真参数设置

利用MATLAB软件，模拟一个100m×100m正方形监测区域，参考图1微网分布式电源监控网络的实际情况，设置设备总数为100，即传感器节点数为100，至于已知位置的设备数量及传感器节点半径是根据需要来调整的。后文中设置锚节点覆盖率分别为4%、9%、16%、25%、36%、49%，通信半径分别取20 m、30 m、40 m、50 m，进行算法对比。式(7)是测定算法可行性的标准，即定位精度(accuracy)，值越小说明定位精度越高。由于随机性较大，所以仿真100次取平均值，减小偶然性

(7)

其中，N为未知节点的总个数，h为仿真次数100次，R指的是节点通信半径，(xk,yk)和(x0k,y0k)分别指的是未知节点的估计坐标与实际坐标。相关仿真场景参数具体见表1。

表1 仿真场景参数

4.2 IDV-Hop算法与其它算法的比较

图7是4种算法的对比：原始DV-Hop算法、文献[6]提出的双通信DV-Hop算法、文献[7]提出的加权DV-Hop算法与本文IDV-Hop算法，对比结果可知：本文IDV-Hop算法相比双通信DV-Hop算法，在通信半径为30 m，锚节点覆盖率为16%时，定位精度提高了1.32%。在锚节点以4%、9%、16%、25%、36%、49%，半径以20 m、30 m、40 m、50 m变化时，每种算法会得出24个相互对应的精度值，取平均值，可知IDV-Hop算法比文献[7]中的算法提高了11%左右，相比原始DV-Hop算法提高了15%左右。因此仿真实验验证本文提出的算法在微网故障定位中会有更高的精确度和更好的适用性。

图7 IDV-Hop算法与其它算法的比较

5 结束语

针对微网中分布式电源故障定位问题，本文提出了一种基于WSN的改进DV-Hop定位算法。根据微网监测系统采集节点数量多、分布广以及位置已知的设备比例较少等特点，选择WSN定位技术中基于免测距方式的DV-Hop算法用于仿真中。本文在进行仿真之前对传统的DV-Hop算法进行了优化，提出了以下优化方案：基于双通信的DV-Hop(A)算法和基于反转法的IDV-Hop算法。仿真结果说明了本文提出的算法相比原始DV-Hop算法和其它改进算法在定位精度上有所提高，更加适用于微网监测中。下一步工作是针对算法中存在的平均跳距方面的误差进行改进并应用于实际微网环境中，验证其可行性。

参考文献：

[1]YANG Xinfa,SU Jian,LV Zhipeng,et al.Overview on micro-grid technology[J].Proceedings of the Chinese Society of Electrical Engineering,2014,34(1):57-70(in Chinese).[杨新法,苏剑,吕志鹏,等.微电网技术综述[J].中国电机工程学报,2014,34(1):57-70.]

[2]Dufour C,Belanger J.On the use of real-time simulation technology in smart grid research and development[C]//Energy Conversion Congress and Exposition.IEEE,2014:2982-2989.

[3]Shih HC,Ho JH,Liao BY.Fault node recovery algorithm for a wireless sensor network[J].IEEE Sensors Journal,2013,13(7):2683-2689.

[4]PAN Zhuojin,LIU Wenchun,LUO Zhen,et al.Improvement of DV-Hop localization algorithm for wireless sensor network[J].Computer Engineering and Design,2016,37(7):1701-1704(in Chinese).[潘琢金,刘文春,罗振,等.无线传感器网络DV-Hop定位算法的改进[J].计算机工程与设计,2016,37(7):1701-1704.]

[5]ZHAO Xiaoqing,MAO Yongyi.Improved DV-Hop algorithm based on error weighting and distance correction[J].Compu-ter Engineering and Applications,2016,52(18):117-121(in Chinese).[赵晓青,毛永毅.基于误差加权和距离修正的改进DV-Hop算法[J].计算机工程与应用,2016,52(18):117-121.]

[6]LI Juan,LIU Yu,QIAN Zhihong,et al.Improved DV-Hop localization algorithm based on two communication ranges for wireless sensor network[J].Journal of Jilin University,2014,44(2):502-507(in Chinese).[李娟,刘禹,钱志鸿,等.基于双通信半径的传感器网络DV-Hop算法[J].吉林大学学报,2014,44(2):502-507.]

[7]QIU Fengmei,LI Huaizhong.Improved DV-Hop localization algorithm based on two communication ranges for wireless sensor network[J].Computer Engineering,2014,40(8):15-20(in Chinese).[邱奉美,李怀忠.无线传感器网络DV-Hop定位算法的改进[J].计算机工程,2014,40(8):15-20.]

[8]WU Yalian,LEI Tianqi,GONG Neng,et al.Application of an improved DV-Hop localization algorithm in fault location on distribution line[J].Natural Science Journal of Xiangtan University,2016,38(1):82-85(in Chinese).[吴亚联,雷天齐,龚能,等.一种改进的DV-Hop定位算法在配电线路故障定位中的应用[J].湘潭大学自科学报,2016,38(1):82-85.]

[9]Zhang Wanli,Yang Xiaoying,Song Qixiang.Improvement of DV-Hop localization based on evolutionary programming resample[J].Journal of Software Engineering,2015,9(3):631-640.

[10]JIN Chun,YE Cheng,HAN Zhibin,et al.DV-Hop localization algorithm improvements in wireless sensor network[J].Computer Engineering and Design,2013,34(2):401-404(in Chinese).[金纯,叶诚,韩志斌,等.无线传感器网络中Dv-Hop定位算法的改进[J].计算机工程与设计,2013,34(2):401-404.]

[11]XIAO Jiqing,LIU Zhenyu,XIAO Jiang.Hop difference based secure localization scheme for wireless sensor network[J].Journal of Computer Applications,2016,36(4):945-951(in Chinese).[肖继清,刘震宇,肖江.基于跳数差的无线传感器网络安全定位方法[J].计算机应用,2016,36(4):945-951.]

[12]PENG Jishen,YANG Muzi,MA Bing.Application of an improved DV-Hop localization algorithm of wireless sensor network to leakage fault of underground coal mine[J].Chinese Journal of Sensors and Actuarors,2014,27(10):1431-1436(in Chinese).[彭继慎,杨慕紫,马冰.一种改进的无线传感器网络DV-Hop定位算法在煤矿井下漏电事故中的应用[J].传感技术学报,2014,27(10):1431-1436.]