彭继慎,杨慕紫,马 冰

(辽宁工程技术大学电气与控制工程学院,辽宁 葫芦岛 125105)



一种改进的无线传感器网络DV-Hop定位算法在煤矿井下漏电事故中的应用*

彭继慎*,杨慕紫,马 冰

(辽宁工程技术大学电气与控制工程学院,辽宁 葫芦岛 125105)

煤矿井下输电线路的实时监测中,漏电故障定位是供电系统保护的重要研究课题。针对井下无线传感器网络定位算法存在不准确的问题,提出了一种改进DV-Hop节点定位算法。首先通过计算锚节点组成的三角形面积,排除面积极小的锚节点组,避免锚节点近似共线的情况,完成了锚节点的优选方案;此外在粒子群算法的基础上结合遗传算法和混沌理论,提出了一种遗传混沌粒子群优化算法;最后利用改进的粒子群算法对DV-Hop算法定位得到的节点位置进行校正。经过仿真实验表明在相同的网络环境下,与传统DV-Hop算法相比,改进算法能够更有效地提高定位精度,从而更加准确地监测到煤矿井下漏电事故位置。

无线传感器网络;故障定位;DV-Hop算法;混沌;遗传算法;粒子群优化算法

煤矿井下的供电系统是工业生产顺利进行的重要保障。由于矿井环境十分恶劣,配电网发生漏电故障时,可能发生瓦斯泄漏等安全隐患,这将对井下人员的人身安全造成重大威胁。因此,针对井下配电网故障定位方法的研究具有重要意义[1-2]。

随着无线通信技术的蓬勃发展,孕育出的无线传感器网络(WSN)在矿井中得到了越来越多的应用。其中DV-Hop[3-4]作为一种无需测距定位算法,非常适用于煤矿井下WSN节点定位中。为了降低定位误差和提高定位精度,已有许多优化算法对其进行改进[5-9]。文献[5]将蚁群粒子群算法引入到DV-Hop算法的未知节点计算阶段,提高了定位精度。文献[6]使用多边测量法的夹角比较原则,除去了锚节点共线的问题。文献[7]引入蛙跳算法求解每跳距离的平均值,从而降低了节点定位误差,使其更接近实际值。这些算法在一定程度上对DV-Hop算法的性能起到了优化作用,但仍有不足。本文在DV-Hop定位算法的基础上,提出了一种锚节点优选方法,避免了节点无法定位的问题,同时提出了一种基于遗传混沌粒子群算法的DV-Hop改进方案,以降低井下配电网故障的平均定位误差和提高定位精度。

1 DV-Hop算法的分析与改进

1.1 DV-Hop算法

DV-Hop算法定位过程如下:

第1步 锚节点将自身的信息(ID、坐标、锚接收信息节点的跳数)通过泛洪的方式发送出去,跳数初始值设置为0,每个临界点接收到信息后就保存和更新最小跳数,并将跳数加1,并继续向邻节点转发,以此规则获得未知节点距离每个锚节点的最小跳数值。

第2步 获取其他锚节点的跳数并根据公式

(1)计算出锚节点每跳的平均每跳距离值disa。

(1)

式中:(xi,yi)、(xj,yj)分别为锚节点i、j的坐标;hcij为锚节点i、j之间最小的跳数。

第3步 利用三边测量法,如图1所示,通过式(2)计算出未知节点A0与锚节点A1、A2、A3之间的距离。

(2)

图1 三边测量法示意图

将式(2)转化为公式AX=P的形式,则有:

(3)

(4)

(5)

采用最小二乘估计得出:

X=(ATA)-1ATP

(6)

1.2 DV-HOP算法的不足

(1)锚节点的拓扑关系会直接影响无线传感器节点定位精度。图2为煤矿井下电网无线传感器节点的分布[10]。由于煤矿井下地理环境狭长,配电网中的传感器在安装时无法达到均匀布置的要求,此时会产生传感器节点共线或近似共线的情况,这两种情况都无法实现节点定位。因此,去除共线性和选择适合的锚节点的成为了一个关键问题。

图2 煤矿井下电网无线传感器分布图

(2)DV-Hop算法在节点定位过程中,由于环境和通信的影响,平均跳距往往会和实际值产生一定误差。且误差一旦产生便会累积影响后面的计算,最终导致产生更大的计算失误。所以必须通过对未知节点坐标进行校正来降低计算误差。

2 DV-Hop算法的改进

2.1 锚节点优选方案

本文通过计算锚节点组成三角形的面积Sn来判定锚节点是否共线:

(7)

假设(xi,yi),(xj,yj),(xk,yk)为随机分布任意的3个锚节点坐标,Sn为锚节点组成的三角形面积。如果0≤Sn≤δ则认为这3个锚节点在近似的一条直线上,所以需要另选锚节点来辅助定位。

2.2 粒子群优化算法DV-Hop

粒子群优化算法PSO(Particle Swarm Optimization)因具有优异的全局搜索性能和快速收敛能力在处理优化问题时表现出独特的优势[11]。PSO从随机解出发,对于n维的优化问题,随机生成m个粒子的初始种群,将第i个粒子的飞行速度Vi和位置Xi其代入优化目标函数得出适应值。经过更新Vi和位置Xi和迭代后搜索到最优解。将第i个粒子搜索得到的最优解记为pi,粒子群搜索到目前最优记为Pb,利用式(8)和式(9)更新Vi和Xi。

Xin(k+1)=Xin(k)+Vin(k+1)

(8)

Vin(k+1)=ωVin(k)+c1r1(Pin-Xin(k))+
c2r2(Pbn-Xin(k))

(9)

式中c1、c2为收缩因子,ω为惯性权重。

2.3 遗传混沌粒子群算法

本文在粒子群算法的基础上结合遗传算法并引入混沌原理和动态权重自适应调节方法,提出了一种遗传混沌粒子群算法GCPSO(Genetic Chaos Particle Swarm Optimization)。

2.3.1 遗传算法

遗传算法GA(Genetic Algorithm)是一种模拟自然界生物不断进化的发展规律[12]。本文通过PSO算法中引入GA算法的交叉、变异两种基因操作形成新一代的精英,最终得到优化问题的最优解。

(1)选择交叉

选出N个偶数个体,然后对选出的个体两两配对,执行交叉操作,产生后代粒子。假设粒子a与粒子b被选择来做交叉操作,相应的位置Xa(t)与Xb(t)被下面的后代取代:

(10)

(11)

对应的速度:

(12)

(13)

(2)变异操作

以概率P对粒子进行交叉操作后,执行下面变异操作:

(14)

(15)

2.3.2 自适应参数调节

混沌(Chaos)是一种对初始条件非常敏感且可以遍历所有状态的非线性的运动[13]。本文采用混沌原理,通过自适应调节粒子群算法的参数来优化粒子的速度Vi和位置Xi。按照下式产生混沌序列:

βk+1=λβk(1-βk)

(16)

当λ=4时系统将进入混沌状态,此时混沌变量βt(t=1,2,…)将在系统内不重复地遍历所有状态。之后对r1和r2进行动态调整,产生一个优良群体,再通过式(8)、式(9)引领粒子向最优解聚集。混沌优化如下:

(17)

惯性权重ω在寻优中起着保持算法平衡的作用。本文选用动态权重调节的方法,权重更新公式为:

(18)

式中:ωmax、ωmin为惯性权重上下限;k为当前迭代次数;kmax为迭代次数最大值。

2.4 基于遗传混沌粒子群DV-Hop改进

基于遗传混沌粒子群算法的DV-Hop算法(GCPSO-Hop)和DV-Hop算法两者通信能耗相同,但GCPSO-Hop算法在计算能耗方面略大于DV-Hop算法。由于无线传感器网络能耗主要产生于通信能耗,所以GCPSO-Hop定位算法能耗符合应用条件。本文将定位误差fi最小作为优化的目标:

(19)

其中:(x,y)为未知节点的坐标,(xi,yi)为锚节点的坐标,dk为实际的测量距离。适应度函数为:

(20)

其中:αi为未知节点与锚节点i跳数的反比值;n为未知节点的数量。

本文利用GCPSO算法对DV-Hop算法定位后期部分中求出的未知节点坐标进行校正。优化具体步骤如下:

Step 1 通过DV-Hop算法的第1步和第2步,得出平均跳距disa和最小跳数hcij。

Step 2 初始化粒子群。初始化粒子速度Vi和位置Xi,设置迭代次数k=0。

Step 3 根据式(20)计算适应值fitness。

Step 4 比较各个粒子的适应值。并设置群体中个体最优解为Pi,全局最优解为Pb。

Step 5 根据式(8)、式(9)更新粒子i的位置Xi和速度Vi。

Step 6 判断算法是否终止。若达到最大迭代次数则输出最优解,否则进行Step 7。

Step 7 按适应度值随机选出M个个体,对它们执行交叉操作,得到M个新个体。

Ste0p 8 对所有个体执行变异操作,在M+N中选取适应度高的N个体开始进入下一代,返回Step 3。

3 实验仿真与结果分析

为了验证改进算法的有效性,本文在100 m×100 m的仿真区域内随机产生传感器节点。对GCPSO-Hop算法、DV-Hop算法、GA-Hop和PSO-Hop算法利用MATLAB进行仿真实验,并对结果进行对比分析。其中绝对定位误差为:

(21)

相对定义误差为:

(22)

式中:(x,y)为未知节点实际坐标,(xe,ye)为估计坐标,R为通信半径。

设置c1=c2=2.0,ωmax=0.9,ωmin=0.4,遗传交叉概率P=0.85,每一代种群的规模N=40,迭代次数k=200。

由于煤矿井下巷道狭小细长且开阔空间有限。为了减少节点通信的误差,在部署巷道拐弯处节点时采用减小部署铺节点间距离的方法并增加一个冗余节点以保证节点间的通信。并且在宽度较窄的巷道采用较为密集的单链式部署方式,以保证节点间的通信质量[14]。

图3 实验平台结构示意图

为了测试本文算法的性能,搭建了模拟井下ZigBee无线传感器配电网监测实验平台。实验平台示意图如图3所示。电源为三相电流源,单相输出电流为1 A～100 A,隔离变压器变比为1∶1,R为保护电阻,A、B、C为三相接上电流传感器。当电网中的电路一旦发生接地故障,此时三相线路失去平衡便会出现零序分量。经过信号调节电路之后会输出为0～3.3 V电压信号,再经A/D转换器在转化为数字信号,最终利于ZigBee无线技术传送到终端。表1为实测定位线路的零序电流。

表1 无线传感器网络实测的输电线路零序电流误差

图5 排除近似共线前后定位平均误差比较

图4是节点的随机分布图。星号为未知节点,十字符号为锚节点。此时锚节点出现了与煤矿井下近似共线的情况。图5为未检测共线性和排除共线性的定位效果,如图5(a)和图5(b)所示,采用剔除共线的方案之后定位效果更优,可以有效地减小节点的平均定位误差。

图4 节点的随机分布

图6为节点总数相同的情况下,锚节点比例在(5%～35%)之间,平均定位误差变化曲线。从图中可以看出4种定位算法的平均定位误差都随着锚节点比例增大而不断减小,其中GCPSO-Hop算法的定位性能表现出明显的优势。在锚节点比例为35%时,GCPSO-Hop算法的平均定位误差最小,且较DV-Hop降低了11.16%。表明GCPSO-Hop算法可以更有效地提高节点定位精度和降低定位误差。

图6 平均定位误差随锚节点所占比例变化关系

图7是锚节点比例相同的情况下,平均定位误差随节点数量变化的关系。随着节点数量的增加,平均定位误差都出现了递减趋势,并逐渐趋于平稳。GA-Hop算法和PSO-Hop算法的平均定位误差都小于DV-Hop算法平均定位误差,但没有达到优化。由于GCPSO-Hop算法对定位得到的位置校正更精确,所以平均定位误差更小。

图7 平均定位误差随节点数量的变化关系

图8 平均定位误差随节点通信半径关系

为了更全面的分析GAPSO-Hop算法的性能。图8为锚节点比例为20%的情况下,在不同的通信半径下节点的平均定位误差变化曲线。通过仿真结果可以看出,当R较小时随着通信半径的增加,平均定位误差开始变小。如R=10 m时,GCPSO-Hop算法的节点的平均定位误差较DV-Hop算法的平均定位误差降低了23.8%。当R大于35 m时,虽然随着通信半径的增大,网络的连通度变大会引起定位误差增加。但此时GAPSO-Hop算法仍是所有算法中最优的。

为了验证GCPSO-Hop算法的有效性和准确性,在煤矿井下选取6个定位节点进行验证实验,实验数据见表2。表2中节点实际坐标为(x,y),实测坐标为(xe,ye)。通过实际测量结果可以看出本文提出GCPSO-Hop算法较其他算法更接近实际值,因此定位误差更小,精度更高。

表2 实际测量结果

4 结论

针对煤矿井下漏电事故排查存在定位不准确的问题,本文提出了一种改进DV-Hop算法。首先通过锚节点优选方案,避免了锚节点组合存在共线而无法定位的的缺陷。同时在粒子群优化算法的基础上,加入了遗传交叉技术和混沌自适应调节方法提出了一种遗传混沌粒子群优化算法(GCPSO)对DV-Hop的估计位置进行校正。实验仿真表明,GCPSO-Hop算法较DV-Hop算法在降低平均定位误差和提高定位精度方面具有更佳的优化效果,证明了GCPSO-Hop算法在煤矿井下安全监督过程中具有可行性与有效性。

[1] 富众杰,申毅,赵刚. 一种改进的煤矿井下无线传感器网络定位算法[J]. 计算机仿真,2012,29(8):123-126.

[2]湛浩旻,孙长嵩,吴珊,等. ZigBee技术在煤矿井下救援系统中的应用[J]. 计算机工程与应用,2008(24):181-183.

[3]Debessu Y G,Wu H C. Modified Turbo Decoder for Location in Single-Frequency Networks[C]//IEEE International Symposium on BMSB,2012:1-5.

[4]石为人,贾传江,梁焕焕. 种改进的无线传感器网络DV-Hop定位算法[J]传感技术学报,2011,24(1):83-87.

[5]叶蓉,赵灵锴. 基于蚁群粒子群混合的无线传感器网络定位算法[J]. 计算机测量与控制,2011,19(3):732-735.

[6]李亚红,冯东华. 基于物联网的传感器节点易移动型监测区域定位算法[J]. 计算机测量与控制,2012,20(11):2916-2918.

[7]葛宇,王学平,梁静. 基于蛙跳算法的DV-Hop定位改进[J]. 计算机应用,2011,31(4):922-925.

[8]Yi T T,Fang Z Y,Li R X. RMADV-HOP:An Improved DV-HOP Localization Algorithm[C]//Proceedings of the 2010 Seventh International Conference on Information Technology:New Generation,Las Vegas,Nevada,2010:939-943.

[9]江禹生,冯砚毫. 一种新的DV-Hop定位算法[J]. 传感技术学报,2010,23(12):1815-1819.

[10]王超楠,丁恩杰,周强,等. 应用无线传感器网络快速定位矿井配电网故障的方法[J]. 计算机辅助设计与图形学学报,2007,19(3):392-397.

[11]陈星舟,廖明宏,林建华. 基于粒子群优化的无线传感器网络节点定位改进[J]. 计算机应用,2010,30(7):1736-1738.

[12]方旺盛,曾晶. 基于量子遗传算法的非测距节点定位算法研究[J]. 计算机应用与软件,2013,30(2):180-183.

[13]孙子文,王鑫雨,白勇,等. 基于信度和早熟检验的混沌粒子群优化定位算法[J]. 传感器与微系统,2013,32(9):129-133.

[14]乔钢柱,曾建潮. 信标节点链式部署的井下无线传感器网络定位算法[J]. 煤炭学报,2010,35(7):1229-1233.

彭继慎(1969-),男,辽宁阜新人,教授,博士生导师,博士。主要从事煤矿安全生产过程监测与控制、工业过程控制与优化、电力传动系统的计算机控制技术与仿真等方面的研究;

杨慕紫(1988-),女,辽宁阜新人,硕士研究生。主要研究方向为煤矿安全生产过程监测与控制、无线传感器网络,327822293@qq.com;

马冰(1989-),男,辽宁阜新人,硕士研究生。主要研究方向无线传感器网络定位技术。

ApplicationofanImprovedDV-HopLocalizationAlgorithmofWirelessSensorNetworktoLeakageFaultofUndergroundCoalMine*

PENGJishen*,YANGMuzi,MABing

(Department of Electrical and Control Engineering,Liaoning Technical University,Huludao Liaoning 125105,China)

The location of leakage fault is an important topic of power system protection in the real-time monitoring of transmission lines of coal mine. An improved DV-Hop localization algorithm is proposed in order to solve the problem of inaccurate localization for wireless sensor networks in the underground coal mine. Firstly,by calculating the triangle area of anchor nodes to eliminate the anchor node group of which the area is tiny. Then,a beacon node optimization is followed to eliminate the beacon nodes which are approximately in a line. Besides,the Genetic Chaos Particle Swarm Optimization algorithm was proposed based on the particle swarm optimization algorithm which combine with genetic algorithms and chaos. Finally,the improved particle swarm optimization was used to correct the location of DV-Hop algorithm. The results from simulation show that the proposed improved algorithm has better locating performance in positioning accuracy than the traditional DV-Hop algorithm in the same network environment. Therefore,the location of leakage can be monitored more accurately in the coal mine.

wireless sensor network;fault location;DV-Hop;chaos;genetic algorithm;particle swarm optimization algorithm

项目来源:辽宁省创新团队项目(LT2010047)

2014-05-20修改日期:2014-08-25

10.3969/j.issn.1004-1699.2014.10.023

TP393

:A

:1004-1699(2014)10-1431-06