基于粒子群进化的输电网络WSN节点定位算法*

任鹏飞， 谷灵康

(1. 河南工程学院 电气信息工程学院， 郑州 451191； 2. 安徽工程大学 计算机与信息学院， 安徽 芜湖 241000)

当前，电力资源在人类能源使用中所占据的比例日益突出，电力网络肩负着电力传输和能源供给的重任.以特高压线路为代表的电力网络已经开始全面铺设，网络覆盖面积广袤，且大部分暴露在野外，布设环境较为复杂，需要通过无线传感器网络(wireless sensor networks，WSN)来监测输电网络的实时状态.无线传感器网络具有成本低廉、易于布设、自组织等多重优点，目前在电力传输网络系统监测方面已有广泛应用[1-2].在电力网络的实际监测中，首先需要考虑网络中各个位置的电力传输情况.由于服务于输电网络的无线传感器网络需要能够实时传递系统监测信息，包括电力故障、电网运行状态等，这些信息与传感器节点的位置息息相关，对实时了解和掌握输电网络的运行情况具有重要的意义，因此，无线传感器节点的位置信息对于电力网络系统监测和性能分析极为重要.节点定位算法能够直接给出无线传感器所在的位置，并避免繁琐的实地测量，可有效地提升电力网络监测和信息传输的效率和性能[3-4].

基于无线传感器网络的节点定位在输电网络中具有诸多应用，是实现输电网络系统监测的基础，也是输电网络应用无线传感器网络亟需解决的关键问题之一[5-7].文献[8]将粒子群算法(particle swarm optimization，PSO)进行改进，并应用于WSN网络节点定位，具有计算复杂度低的优点，但该算法只是简单沿用了粒子群算法完成优化定位，性能提升并不明显；文献[9]将节点定位分为两个阶段，首先采用DV-distance算法对节点位置进行粗略估计，然后使用粒子群算法精确定位；文献[10]则将粒子群算法与DV-Hop算法相融合，利用粒子群算法进一步优化定位结果，但该算法计算复杂度较高，定位精度也受限；文献[11]使用边界盒方法预估计节点的所在区域，并通过WSN网络中的数据交换获取其他邻居节点的估计信息，以进一步缩小估计区域，优化定位精度，但该方法在两次估计间等待时间较长，使得定位过程耗时较长，定位精度提高有限.

针对上述问题，本文提出一种粒子群进化算法，以应用于输电网络的WSN节点定位.该算法通过区域估计，缩小并限制传感器节点的预估计区域空间，以简化计算复杂度，并应用粒子群算法快速寻找节点定位的最优解.通过引入粒子群竞争和权重自适应的机制，以加快节点定位的搜索速度，并提升算法的搜索能力.通过仿真和分析发现，相比同类的WSN节点定位算法，该算法在锚节点密度、通信距离、测距误差等方面都具有一定的性能优势，能够显著提升节点的定位精度，降低计算复杂度，为输电网络的无线传感器网络提供更高效准确的定位服务.

1 粒子群算法原理

粒子群算法是一种基于种群的启发式智能算法，其搜索策略受鸟群集体活动启发，并引入了群体的智能策略.相比同类启发式算法(如退火算法、蚁群算法等)，粒子群算法需要设定的参数少、收敛迅速快且计算复杂度低.

定义1粒子.在粒子群算法中，种群中的单个个体称为粒子.在进化迭代过程中，每个粒子的速度、位置、局部最优解(pbesti)和全局最优解(gbesti)都需要记录.

定义2粒子适应度函数.粒子适应度函数是用于比较所有粒子候选解的适应度.通过舒服粒子在当前迭代的位置，计算粒子的适应值，以此衡量粒子候选解的优劣.

假设D表示解空间维度，P表示粒子种群规模，Vi=[vi，1，vi，2，…，vi，D]为粒子i速度，Xi=[xi，1，xi，2，…，xi，D]为粒子i位置，则粒子群算法可进一步表示为

(1)

式中：ω为惯性权重；k为进化代数；c1、c2为进化系数；r1和r2为(0，1)之间的随机数；i=1，2，…，P，d=1，2，…，D.在粒子群迭代过程中，粒子通过搜索个体最优解pbesti与全局最优解gbesti不断调整自身的位置和速度，逐步达到全局最优解.

2 输电网络WSN节点定位算法

基于WSN网络中节点定位的模式和特点，本文采用了区域估计方法限制了传感器节点的预估计区域空间，以简化计算复杂度.引入了粒子群竞争和权重自适应策略，粒子群在每次迭代演化中搜索局部最优解(pbesti)和全局最优解(gbesti)，同步调整粒子群的位置、速度，以优化未知节点的精确定位.采取上述改进策略在粒子群算法的复杂度和定位性能间获得最优平衡.

2.1 问题描述

假设WSN网络依托输电网络进行布设，并为其提供定位服务.无线传感器网络包含M个锚节点和N个普通节点，其中任意锚节点的坐标可表示为mi(xi，yi)，而普通节点的位置坐标未知.无线传感器网络的节点定位就是基于网络中位置已知的M个锚节点，计算并确定其余N个普通节点的位置，这里称需要定位的普通节点为目标节点.寻找N个目标节点的位置过程即为粒子群算法的迭代过程，通过获取最小的粒子适应度函数估计得到未知节点的精确位置.适应度函数可表示为

(2)

2.2 区域估计

区域估计是指粒子群在执行搜索之前，对未知节点所在区域进行合理估计，限制节点位置可行解空间，减少粒子群算法的复杂度和计算量，提升未知节点的定位精度.

在文献[11]的基础上，本文提出了未知节点的区域估计方法.对于未知节点i，首先获取其所有的邻居锚节点，计算所有邻居锚节点的正方形覆盖区域的交集几何中心，作为传感器节点i的位置估计.需要指出的是，锚节点的正方形覆盖区域以该锚节点为中心，边长是传感器节点通信距离的2倍.由于计算矩形交集比计算圆形交集更加简单易实现，这使得后续的粒子群算法得到了简化，降低了计算量，并有效提升了区域估计的精度.区域估计的具体流程如图1所示.

图1 区域估计流程图Fig.1 Flow chart of regional estimation

在未知节点的区域估计过程中，未知节点首先需要收集邻居锚节点的位置信息，然后将节点ID和存储的邻居锚节点信息向邻居节点广播，同时接收其他目标节点的广播消息，最后综合所有邻居锚节点的位置信息完成自身的区域估计.未知节点i的估计区域表示为

(3)

(4)

(5)

(6)

式中：r为输电网络中传感器节点的最大通信距离；Lright，i，Lleft，i，Lup，i，Ldown，i分别为未知节点在4个方位上的节点位置，这4项参数共同确定了节点i的估计位置.

在分析区域估计的过程中发现，改进后的区域估计只需要完成加减运算或min(max)运算即可完成未知节点的位置估计，这就为后续粒子群迭代有效地缩小了可行解空间，大大减少了计算量，节约了WSN网络的节点能耗，从而促进了输电网络的节点定位服务.

2.3 基于粒子群进化的WSN节点定位算法

为进一步加快算法的搜索速度，增强算法的实用性，基于粒子群进化的WSN节点定位算法还引入了权重自适应的策略，以加快算法的收敛速度.

在粒子群算法中，权值w对节点适应度函数的影响较大.如果w取值过大，则粒子速度变化较快，使得粒子容易跳出局部极小点，具有较强的全局搜索能力，但也会降低粒子群的局部搜索能力；反之，如果w取值过小，则粒子群的局部搜索能力增强，便于算法收敛，却会降低粒子群的全局搜索能力.因此，有必要采用自适应的权重w，在实现算法快速收敛的同时，保证粒子群进化在全局和局部范围内达到有效的平衡.自适应权重w表示为

(7)

式中，fa为未知节点的节点适应度满足要求的门限阈值.当节点适应度剧增时，自适应降低w的权值；当节点适应度剧降时，自适应增加w的权值.自适应地调整权重w，使其停留在(wmin，wmax)范围内，能够保持局部搜索与全局搜索能力的平衡，使得粒子群收敛的速度最快.

基于粒子群进化的WSN节点定位算法具体步骤如下：

1) 对目标节点进行区域估计，缩小并确定可搜索的空间S.

2) 初始化迭代次数iter=0，粒子群规模为e.

3) 若满足e

4) 淘汰50%适应度较低的粒子，保留50%适应度较高的优选粒子.

5) 围绕每个优选粒子的位置设定一个局部的搜索范围，并进行局部搜索.

6) 获取每个优先粒子的局部最优解(pbesti)，并将该粒子更新为局部最优解对应的位置，比较所有的局部最优解，获取并记录全局最优解(gbesti).

7) 判断迭代终止条件是否满足，若满足，则粒子群迭代结束，以全局最优解(gbesti)作为未知节点的位置估计；若不满足，补充(E-e)/2个随机粒子，并跳转至步骤3).

为便于输电网络中实现WSN网络测距，本文采用RSSI技术实现相邻节点间的测距.由于实际网络中节点布设、地形起伏等因素的影响，无线传感器节点的通信覆盖范围不一定是圆形，往往导致测距误差，因此，在仿真过程中需要考虑环境等因素引起的测距误差并加以修正.

3 仿真结果与分析

3.1 仿真环境说明

为验证节点定位算法的有效性，本文采用MATLAB 2010的平台进行仿真.在WSN网络的覆盖范围内(100 m×100 m)，随机生成100个无线传感器节点.其中，锚节点个数20～50，位置已知，其余个节点位置未知.输电网络中无线传感器节点定位的评价指标为：对未知节点重复10次节点定位，计算平均定位误差，即定位位置与实际位置的距离与节点通信半径之比.同类算法中，选取了经典的DPSO算法[12]、Standard PSO算法[13]进行对比；不同类算法中，选取了经典的测距定位算法Improved DV[14]来比较.测距定位算法Improved DV不需要设置粒子群参数，其余3种算法的参数设置如表1所示.

3.2 锚节点密度对定位性能的影响

图2为在不同锚节点密度下4种算法的定位误差.随着锚节点密度的逐步增加，所有算法的定位误差都呈不断缩小的趋势，其中，Improved DV算法的定位误差下降幅度最大.因为随着锚节点的增多，输电网络中未知节点有了更多的位置参考，在节点定位过程中能够获取更多的邻居节点位置信息，从而有效地降低定位误差.综合比较4种定位算法，本文算法的定位性能最优.当锚节点密度为10%时，其定位误差为33.5%；而当锚节点密度为40%时，其定位误差约为8.1%，一直处于所有算法中的误差最低水平.在同等锚节点密度下，本文的定位算法具有最优的定位精度，从而需要最少的锚节点，有效降低了输电网络的部署成本.

表1 WSN节点定位的参数设置Tab.1 Parameter setting of WSN node localization

图2 不同锚节点密度下4种算法的定位误差Fig.2 Localization error of 4 algorithms under different anchor node density

3.3 通信距离对定位性能的影响

图3为4种算法在不同通信距离下的定位误差，其中节点通信距离限定在20～50 m.如图3所示，随着节点通信距离的不断扩大，定位误差都呈现出逐步缩小的趋势.综合比较4种定位算法，在同等通信距离的条件下，本文算法的节点定位误差最小.当节点通信距离为25 m时，其定位误差为12.4%；而当节点通信距离为50 m时，其定位误差约为9.3%，一直处于所有算法中的误差最低水平.在相同的定位误差要求下，本文算法所需节点通信距离最小，即要求无线传感器节点的通信半径最小，需要消耗的信号功率最低，有效降低网络的通信能耗，提升网络的工作寿命，提升无线传感器网络的稳定性和有效性.

图3 不同通信距离下4种算法的定位误差Fig.3 Localization error of 4 algorithms under different communication distances

3.4 测距误差对定位性能的影响

节点定位会受部署环境的影响，比如信号衰减、通信范围受限等.其中，测距误差对节点定位影响尤为重要，这里通过实验进一步进行对比和分析.

图4为4种算法在不同测距误差下的定位误差.当测距误差逐步增大，4种算法的定位误差也呈现不断增加的趋势.由于Improved DV算法是测距定位算法，测距过程中需要累加基于接收信号强度(RSSI)的测试距离，测距误差对定位误差的影响尤为明显.当RSSI测距误差较小时，Improved DV算法性能与DPSO算法接近；当RSSI测距误差较大时，Improved DV算法性能急剧下降，定位误差最大.综合比较4种定位算法，在同等测距误差的条件下，本文算法的节点定位误差虽然也在逐步增加，但表现较为稳定，且在4种算法中定位误差最小，一直处于所有算法中误差最低水平.这说明本文算法抗测距误差性能最佳，稳定性最好，能够适用于多种复杂恶劣的输电网络环境.

图4 不同测距误差下4种算法的定位误差Fig.4 Localization error of 4 algorithms under different ranging errors

4 结 论

基于无线传感器网络的节点定位对于输电网络的信息传输和故障判定具有重要意义，为改善输电网络中的节点定位精度，本文提出一种基于粒子群进化的节点定位算法.该算法通过区域估计，缩小并限制传感器节点的预估计区域空间，以简化计算复杂度，并通过引入粒子群竞争和权重自适应的机制，改善了无线传感器节点的定位精确.通过仿真和分析发现，相比同类的WSN节点定位算法，该算法在锚节点密度、通信距离、测距误差等方面都具有性能优势，能够显著提升节点的定位精度，降低计算复杂度.该算法非常适用于现有的输电网络，利用输电网络搭载的无线传感器网络，为输电网络监测提供更高效、更准确的定位服务.