任鹏飞1， 谷灵康2
(1. 河南工程学院 电气信息工程学院， 郑州 451191； 2. 安徽工程大学 计算机与信息学院， 安徽 芜湖 241000)
摘要：为了提升WSN的定位精度，提出了一种基于粒子群进化的定位算法，以应用于输电网络中的节点定位.该算法通过区域估计，缩小并限制传感器节点的预估计区域空间，并应用粒子群算法快速寻找节点定位的最优解.通过引入权重自适应的机制，加快节点定位的搜索速度，并提升算法的搜索能力.结果表明，该算法有效增强了WSN节点定位的精度，降低了计算复杂度，为输电网络的无线传感器网络提供更高效准确的定位服务.
关键词：输电网络； 节点定位； 粒子群； 无线传感器网络； 测距； 适应度； 区域估计； 权重
当前，电力资源在人类能源使用中所占据的比例日益突出，电力网络肩负着电力传输和能源供给的重任.以特高压线路为代表的电力网络已经开始全面铺设，网络覆盖面积广袤，且大部分暴露在野外，布设环境较为复杂，需要通过无线传感器网络(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粒子.在粒子群算法中，种群中的单个个体称为粒子.在进化迭代过程中，每个粒子的速度、位置、局部最优解(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不断调整自身的位置和速度，逐步达到全局最优解.
基于WSN网络中节点定位的模式和特点，本文采用了区域估计方法限制了传感器节点的预估计区域空间，以简化计算复杂度.引入了粒子群竞争和权重自适应策略，粒子群在每次迭代演化中搜索局部最优解(pbesti)和全局最优解(gbesti)，同步调整粒子群的位置、速度，以优化未知节点的精确定位.采取上述改进策略在粒子群算法的复杂度和定位性能间获得最优平衡.
假设WSN网络依托输电网络进行布设，并为其提供定位服务.无线传感器网络包含M个锚节点和N个普通节点，其中任意锚节点的坐标可表示为mi(xi，yi)，而普通节点的位置坐标未知.无线传感器网络的节点定位就是基于网络中位置已知的M个锚节点，计算并确定其余N个普通节点的位置，这里称需要定位的普通节点为目标节点.寻找N个目标节点的位置过程即为粒子群算法的迭代过程，通过获取最小的粒子适应度函数估计得到未知节点的精确位置.适应度函数可表示为
(2)
式中：n为邻居锚节点数目；di为目标节点与邻居锚节点间的欧式距离；
为测试距离；(x，y)为未知节点坐标.可采用
作为测距权重，调整和约束未知节点的估计位置，保证未知节点定位的精确性.
区域估计是指粒子群在执行搜索之前，对未知节点所在区域进行合理估计，限制节点位置可行解空间，减少粒子群算法的复杂度和计算量，提升未知节点的定位精度.
在文献[11]的基础上，本文提出了未知节点的区域估计方法.对于未知节点i，首先获取其所有的邻居锚节点，计算所有邻居锚节点的正方形覆盖区域的交集几何中心，作为传感器节点i的位置估计.需要指出的是，锚节点的正方形覆盖区域以该锚节点为中心，边长是传感器节点通信距离的2倍.由于计算矩形交集比计算圆形交集更加简单易实现，这使得后续的粒子群算法得到了简化，降低了计算量，并有效提升了区域估计的精度.区域估计的具体流程如图1所示.
图1区域估计流程图
Fig.1Flowchartofregionalestimation
在未知节点的区域估计过程中，未知节点首先需要收集邻居锚节点的位置信息，然后将节点ID和存储的邻居锚节点信息向邻居节点广播，同时接收其他目标节点的广播消息，最后综合所有邻居锚节点的位置信息完成自身的区域估计.未知节点i的估计区域表示为
(3)
(4)
(5)
(6)
式中：r为输电网络中传感器节点的最大通信距离；Lright，i，Lleft，i，Lup，i，Ldown，i分别为未知节点在4个方位上的节点位置，这4项参数共同确定了节点i的估计位置.
在分析区域估计的过程中发现，改进后的区域估计只需要完成加减运算或min(max)运算即可完成未知节点的位置估计，这就为后续粒子群迭代有效地缩小了可行解空间，大大减少了计算量，节约了WSN网络的节点能耗，从而促进了输电网络的节点定位服务.
为进一步加快算法的搜索速度，增强算法的实用性，基于粒子群进化的WSN节点定位算法还引入了权重自适应的策略，以加快算法的收敛速度.
在粒子群算法中，权值w对节点适应度函数的影响较大.如果w取值过大，则粒子速度变化较快，使得粒子容易跳出局部极小点，具有较强的全局搜索能力，但也会降低粒子群的局部搜索能力；反之，如果w取值过小，则粒子群的局部搜索能力增强，便于算法收敛，却会降低粒子群的全局搜索能力.因此，有必要采用自适应的权重w，在实现算法快速收敛的同时，保证粒子群进化在全局和局部范围内达到有效的平衡.自适应权重w表示为
(7)
式中，fa为未知节点的节点适应度满足要求的门限阈值.当节点适应度剧增时，自适应降低w的权值；当节点适应度剧降时，自适应增加w的权值.自适应地调整权重w，使其停留在(wmin，wmax)范围内，能够保持局部搜索与全局搜索能力的平衡，使得粒子群收敛的速度最快.
基于粒子群进化的WSN节点定位算法具体步骤如下：
1) 对目标节点进行区域估计，缩小并确定可搜索的空间S.
2) 初始化迭代次数iter=0，粒子群规模为e.
3) 若满足e<E，在搜索空间S内随机产生E-e个粒子，保持粒子群规模稳定，根据适应度函数(式2)获取所有粒子的当前适应度.
4) 淘汰50%适应度较低的粒子，保留50%适应度较高的优选粒子.
5) 围绕每个优选粒子的位置设定一个局部的搜索范围，并进行局部搜索.
6) 获取每个优先粒子的局部最优解(pbesti)，并将该粒子更新为局部最优解对应的位置，比较所有的局部最优解，获取并记录全局最优解(gbesti).
7) 判断迭代终止条件是否满足，若满足，则粒子群迭代结束，以全局最优解(gbesti)作为未知节点的位置估计；若不满足，补充(E-e)/2个随机粒子，并跳转至步骤3).
为便于输电网络中实现WSN网络测距，本文采用RSSI技术实现相邻节点间的测距.由于实际网络中节点布设、地形起伏等因素的影响，无线传感器节点的通信覆盖范围不一定是圆形，往往导致测距误差，因此，在仿真过程中需要考虑环境等因素引起的测距误差并加以修正.
为验证节点定位算法的有效性，本文采用MATLAB 2010的平台进行仿真.在WSN网络的覆盖范围内(100 m×100 m)，随机生成100个无线传感器节点.其中，锚节点个数20～50，位置已知，其余个节点位置未知.输电网络中无线传感器节点定位的评价指标为：对未知节点重复10次节点定位，计算平均定位误差，即定位位置与实际位置的距离与节点通信半径之比.同类算法中，选取了经典的DPSO算法[12]、Standard PSO算法[13]进行对比；不同类算法中，选取了经典的测距定位算法Improved DV[14]来比较.测距定位算法Improved DV不需要设置粒子群参数，其余3种算法的参数设置如表1所示.
图2为在不同锚节点密度下4种算法的定位误差.随着锚节点密度的逐步增加，所有算法的定位误差都呈不断缩小的趋势，其中，Improved DV算法的定位误差下降幅度最大.因为随着锚节点的增多，输电网络中未知节点有了更多的位置参考，在节点定位过程中能够获取更多的邻居节点位置信息，从而有效地降低定位误差.综合比较4种定位算法，本文算法的定位性能最优.当锚节点密度为10%时，其定位误差为33.5%；而当锚节点密度为40%时，其定位误差约为8.1%，一直处于所有算法中的误差最低水平.在同等锚节点密度下，本文的定位算法具有最优的定位精度，从而需要最少的锚节点，有效降低了输电网络的部署成本.
表1WSN节点定位的参数设置
Tab.1ParametersettingofWSNnodelocalization
图2不同锚节点密度下4种算法的定位误差
Fig.2Localizationerrorof4algorithmsunderdifferentanchornodedensity
图3为4种算法在不同通信距离下的定位误差，其中节点通信距离限定在20～50 m.如图3所示，随着节点通信距离的不断扩大，定位误差都呈现出逐步缩小的趋势.综合比较4种定位算法，在同等通信距离的条件下，本文算法的节点定位误差最小.当节点通信距离为25 m时，其定位误差为12.4%；而当节点通信距离为50 m时，其定位误差约为9.3%，一直处于所有算法中的误差最低水平.在相同的定位误差要求下，本文算法所需节点通信距离最小，即要求无线传感器节点的通信半径最小，需要消耗的信号功率最低，有效降低网络的通信能耗，提升网络的工作寿命，提升无线传感器网络的稳定性和有效性.
图3不同通信距离下4种算法的定位误差
Fig.3Localizationerrorof4algorithmsunderdifferentcommunicationdistances
节点定位会受部署环境的影响，比如信号衰减、通信范围受限等.其中，测距误差对节点定位影响尤为重要，这里通过实验进一步进行对比和分析.
图4为4种算法在不同测距误差下的定位误差.当测距误差逐步增大，4种算法的定位误差也呈现不断增加的趋势.由于Improved DV算法是测距定位算法，测距过程中需要累加基于接收信号强度(RSSI)的测试距离，测距误差对定位误差的影响尤为明显.当RSSI测距误差较小时，Improved DV算法性能与DPSO算法接近；当RSSI测距误差较大时，Improved DV算法性能急剧下降，定位误差最大.综合比较4种定位算法，在同等测距误差的条件下，本文算法的节点定位误差虽然也在逐步增加，但表现较为稳定，且在4种算法中定位误差最小，一直处于所有算法中误差最低水平.这说明本文算法抗测距误差性能最佳，稳定性最好，能够适用于多种复杂恶劣的输电网络环境.
图4不同测距误差下4种算法的定位误差
Fig.4Localizationerrorof4algorithmsunderdifferentrangingerrors
基于无线传感器网络的节点定位对于输电网络的信息传输和故障判定具有重要意义，为改善输电网络中的节点定位精度，本文提出一种基于粒子群进化的节点定位算法.该算法通过区域估计，缩小并限制传感器节点的预估计区域空间，以简化计算复杂度，并通过引入粒子群竞争和权重自适应的机制，改善了无线传感器节点的定位精确.通过仿真和分析发现，相比同类的WSN节点定位算法，该算法在锚节点密度、通信距离、测距误差等方面都具有性能优势，能够显著提升节点的定位精度，降低计算复杂度.该算法非常适用于现有的输电网络，利用输电网络搭载的无线传感器网络，为输电网络监测提供更高效、更准确的定位服务.
参考文献(References)：
[1] 李金友，闫磊，齐欢，等.基于LTE230系统的电力无线通信专网研究与实践 [J].电气技术，2014(1)：132-134.
(LI Jin-you，YAN Lei，QI Huan，et al.Research and practice on the electric power wireless communication network of LTE230 system [J].Electrical Engineering，2014(1)：132-134.)
[2] 曹津平，刘建明，李祥珍.面向智能配用电网络的电力无线专网技术方案 [J].电力系统自动化，2013，37(11)：76-80.
(CAO Jin-ping，LIU Jian-ming，LI Xiang-zhen.A power wireless broadband technology scheme for smart power distribution and utilization networks [J].Automation of Electric Power Systems，2013，37(11)：76-80.)
[3] 刘耀先，孙毅，武昕，等.面向配电网故障检测的无线传感网络可靠路由方法 [J].电网技术，2015，39(12)：3609-3614.
(LIU Yao-xian，SUN Yi，WU Xin，et al.A reliable WSN routing method for distribution network fault detection [J].Power System Technology，2015，39(12)：3609-3614.)
[4] Zhang D G，Li G，Zheng K，et al.An energy-balanced routing method based on forward-aware factor for wireless sensor networks [J].IEEE Trans on Industrial Informatics，2014，10(1)：765-773.
[5] 胡学敏，崔勇，袁海文，等.基于RSSI技术提高直流线路电场测无线网络节点定位精度的算法 [J].电网技术，2014，38(6)：1644-1649.
(HU Xue-min，CUI Yong，YUAN Hai-wen，et al.An algorithm for improving the location accuracy of wireless sensor network node based on RSSI technology [J].Power System Technology，2014，38(6)：1644-1649.)
[6] 张亚明，史浩山，程伟，等.一种无线传感器网络中的进化定位机制 [J].西北工业大学学报，2013，31(4)：633-638.
(ZHANG Ya-ming，SHI Hao-shan，CHENG Wei，et al.A novel evolution localization mechanism in WSN [J].Journal of Northwestern Polytechnical University，2013，31(4)：633-638.)
[7] 杨理践，沈博，高松巍.基于组合导航技术的管道地理坐标定位算法 [J].沈阳工业大学学报，2014，36(1)：66-71.
(YANG Li-jian，SHEN Bo，GAO Song-wei.Geographical position locating algorithm for pipeline based on integrated navigation technique [J].Journal of Shenyang University of Technology，2014，36(1)：66-71.)
[8] Gopakumar A，Jacob L.Localization in wireless sensor networks using particle swarm optimization [C]//Proc IET International Conference on Wireless，Mobile and Multimedia Networks.Mumbai，India，2008：227-230.
[9] Namin P H，Tinati M A.Node localization using particle swarm optimization [C]//Proc 7th International Conference on Intelligent Sensors，Sensor Networks and Information Processing.Adelaide，Australia，2012：288-293.
[10] 孙美松，刘宴兵，黄俊.WSN中基于伪正态分布的幻影路由隐私保护方案 [J].重庆邮电大学学报(自然科学版)，2016，28(1)：113-119.
(SUN Mei-song，LIU Yan-bing，HUANG Jun.Source-location privacy protections trategy through pseudo normal distribution-based phantom routing in WSN [J].Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition)，2016，28(1)：113-119.)
[11] 王行甫，刘志强，黄秋原，等.WSN中一种改进的边界盒定位算法 [J].计算机工程，2011，37(20)：57-59.
(WANG Xing-fu，LIU Zhi-qiang，HUANG Qiu-yuan，et al.Improved bounding-box localization algorithm in WSN [J].Computer Engineering，2011，37(20)：57-59.)
[12] Wang S，Hu H S，Klausm M.Optimization and sequence search based localization in wireless sensor networks [C]//Proc 3rd International Conference on Emerging Security Technologies.Lisbon，Portugal，2012：155-160.
[13] Wang D H，Jia H D，Chen F X，et al.An improved dv-distance localization algorithm for wireless sensor networks [C]//Proc 2nd International Conference on Advanced Computer Control.Shenyang，China，2010：472-476.
[14] 李坚，刘昀，安春燕，等.电力4G无线通信网络安全技术 [J].电信科学，2015(增刊1)：69-72.
(LI Jian，LIU Yun，AN Chun-yan，et al.Security technologies in 4G network for power grid [J].Telecommunications Science，2015(Sup1)：69-72.)
REN Peng-fei1, GU Ling-kang2
(1. College of Electrical Information and Engineering, Henan Institute of Engineering, Zhengzhou 451191, China; 2. School of Computer and Information, Anhui Polytechnic University, Wuhu 241000, China)
Abstract：In order to improve the node localization accuracy of WSN, a localization algorithm based on particle swarm optimization (PSO) was proposed and applied to the node localization in the power transmission networks. Through the regional estimation, the pre-estimation regional space of sensor nodes was reduced and limited, and the optimal solution of node localization was quickly searched with the PSO algorithm. Moreover, the search capacity of the algorithm was improved. The results show that the proposed algorithm can greatly promote the accuracy of WSN node localization, reduce the computational complexity, and provide more accurate service for the node localization of wireless sensor networks (WSN).
Keywords：power transmission network; node localization; particle swarm; wireless sensor network; ranging; fitness; regional estimation; weight
doi：10.7688/j.issn.1000-1646.2018.05.11
* 本文已于2018-08-29 11∶39在中国知网优先数字出版. 网络出版地址： http：∥kns.cnki.net/kcms/detail/21.1189.T.20180828.1454.024.html
作者简介：任鹏飞(1982-)，男，河南郑州人，讲师，硕士，主要从事电气自动化应用、模式识别等方面的研究.
基金项目：国家自然科学基金资助项目(51407035)； 广东省自然科学基金资助项目(S2013040013776)； 河南省高等学校重点科研项目(17A470007).
收稿日期：2016-12-30.
文章编号：1000-1646(2018)05-0541-06
文献标志码：A
中图分类号：TN 393
(责任编辑：景 勇 英文审校：尹淑英)