一种改进的无线传感器网络优化定位算法

张亚明，史浩山，陈客松，程 伟

(1. 西安石油大学电子工程学院 西安 710065；2. 西北工业大学电子信息学院 西安 710129；3. 电子科技大学电子工程学院 成都 611731)

一种改进的无线传感器网络优化定位算法

张亚明1,2，史浩山2，陈客松3，程 伟2

(1. 西安石油大学电子工程学院 西安 710065；2. 西北工业大学电子信息学院 西安 710129；3. 电子科技大学电子工程学院 成都 611731)

节点定位是无线传感器网络实际应用需要解决的关键问题。为了在提高定位精度的同时降低成本，提出了一种改进的粒子群优化定位算法。该算法首先提出前摄估计思想，完成未知节点的区域估计，缩小并限制可行解空间，以此加快粒子群的搜索速度；然后给出了竞争进化思想的数学模型，使用该模型和自适应权重在进一步加快收敛速度的同时增强了算法的全局和局部搜索能力。仿真结果表明，对比同类算法，该算法能更有效地利用锚节点信息，降低网络成本，在计算量显著减少的同时明显提高了定位精度，并且具有对测距误差鲁棒性强的优点。

竞争进化; 定位; 粒子群算法; 前摄估计; 无线传感器网络

节点定位技术[1-2]是无线传感器网络[3]的一项重要支撑技术。目前，国内外学者已先后提出了多种定位解决方案和算法。因为无线传感器网络存在网络环境复杂多变、锚节点不充分、测距不准确等特殊性，学者们将其定位问题转化为约束优化类问题[4-11]，并使用智能计算技术进行求解。如文献[8]提出的SAL算法，把模拟退火算法(SA)用于无线传感网络节点定位，这是较早尝试把定位问题转化为优化问题的研究之一。该方法的缺点是计算量太大，且定位精度有限。文献[9]提出将粒子群算法(PSO)用于无线传感器网络定位。相对于SAL算法，文献[9]所提算法表现出较好的定位效果和较低的计算成本，但该算法只是简单使用PSO算法进行寻优定位，并没有针对无线传感器网络的特点做出任何修改。文献[10-11]在引入PSO算法的基础上进行了适当改进。文献[10]在第一阶段使用改进的DV-distance算法进行所有节点位置的粗略估计，第二阶段使用PSO算法完成精确估计；文献[11]则借助远端锚节点的位置信息提高网络中未知节点的定位成功率。文献[12]将PSO算法与DV-Hop算法相结合，用于对DV-Hop算法的定位结果进行优化求精。文献[13]则分别使用高斯−牛顿算法和PSO算法优化节点位置，并通过物理实验证明PSO算法的优化效果更佳，鲁棒性更强。文献[14]使用竞争进化思想和自适应权重策略对PSO算法进行改进，并在WSN定位中取得了较好的定位效果。然而，该文献对于粒子历史最优和种群全局最优的计算过程在描述上较为模糊，并未给出具体的数学模型。

在上述研究的启发下，本文提出一种改进的粒子群优化定位算法。该算法首先提出前摄估计思想，在搜索寻优前以极其简单的计算为代价合理估计并极大缩小可行解空间；再对竞争进化思想进行了更详细地阐述，并给出了具体的数学模型。仿真结果显示本文算法在显著降低计算成本的同时有效提高了定位精度，验证了算法的有效性和实用性。

1 粒子群算法基本原理

粒子群算法[15]是一种基于种群的启发式智能进化计算技术。它是受到飞鸟集群活动的启发，进而利用群体智能策略建立的一个简化模型。与其他传统智能计算技术相比，粒子群算法只有简单几个参数，具有实现简单、易收敛且计算量小等优点。

假设D表示搜索空间(即解空间)维度；P表示粒子种群规模；Xi=[xi,1,xi,2,,xi,D]和Vi=[vi,1,vi,2,,vi,D]分别表示群体中第i个粒子的位置和速度，则PSO算法的数学模型可表示为：

可以看到，粒子能在每一次进化中追踪个体最优解pbest和全局最优解gbest，进而更新自己的速度和位置。

2 基于改进粒子群的WSN节点定位

2.1 问题描述

假设无线传感器网络由M个坐标为Mi(xi,yi) (i=1,2,,M)的锚节点和N−M(M

式中，(x,y)表示未知节点坐标；di表示未知节点到第i个邻居锚节点的欧式距离表示测距结果；n为所求未知节点的邻居锚节点数目。

2.2 粒子群算法的改进

当前有很多文献从优化计算的角度对PSO算法进行了改进，试图进一步提高其性能[16]。本文结合WSN定位的特点，在对PSO算法做出合理改进的同时，在算法性能和复杂度之间进行了平衡。首先提出前摄估计思想；接着对竞争进化策略进行了详细讨论，并给出了具体数学模型。

2.2.1 前摄估计

前摄估计指在执行搜索寻优之前，对待定位节点所在区域进行合理估计，极大缩小并限制可行解空间，为粒子群算法的执行减小难度和复杂度，从而达到降低计算量节约能耗的目的。

采用边界盒[17]方法实现前摄估计。该方法是指未知节点以其所有邻居锚节点的正方形覆盖区域(该正方形覆盖区域以相应锚节点为中心，边长是节点最大通信距离的二倍)的交集的几何中心作为其位置估计的一种算法。该算法的优势是计算矩形交集比计算圆形交集更加简单易实现，所需计算量最小，可大大节约传感器节点在定位过程中的能耗；缺点是定位精度较低。文献[18]提出了一种改进方法，即未知节点在使用边界盒方法初步确定自身的估计区域后，通过信息交互获取通信范围内其他未知节点的区域估计信息，再次缩小自己的估计区域。该方法的不足在于精度提高有限且两次估计之间有一个较长的等待过程。

本文在文献[18]基础上设计一种改进的估计方法，即未知节点接收完邻居锚节点信息后，先把自身ID及其存储的所有邻居锚节点信息进行广播(如果该节点没有邻居锚节点则不广播)，同时接收其他未知节点广播的此类信息，然后再完成估计过程。具体流程如图1所示。

计算本节点初次估计区域为：

计算节点的最终估计区域为：

式中，(xi,yi)表示锚节点坐标；r表示节点最大通信距离；gleft、gright、gdown和gup表示估计结果；glefti、grighti、gdowni和gupi表示邻居未知节点i的估计结果。

可以看到，本文方法只需要执行极其简单的加减运算或者min(max)运算即可完成未知节点位置的区域估计，为随后的搜索极大缩小了解空间，减少计算量节约能耗的同时加快算法全局搜索速度，提高了算法的实用性

为了进一步提高算法性能，特别是进一步增强算法的全局和局部搜索能力，本文算法还使用了竞争进化策略和自适应权重[14]。

2.2.2 竞争进化

竞争进化策略是在优胜劣汰思想的基础上增加了分裂进化机制，本文在文献[14]的基础上对竞争进化策略进行了更深入细致地阐述，并给出了具体的数学模型。

在种群(简称“全局群”，区别于后面的“局部群”)进化过程中，每代进化完成后，首先计算种群中所有粒子的适应度值；再根据种群内所有粒子的不同适应度值，先淘汰一半性能差的粒子(在下一次迭代运算之前产生同样数目的随机粒子代替淘汰掉的粒子，以保证种群规模不变)；然后将当前所有剩余粒子作为“优选粒子(winner particles)”进行分裂进化。分裂进化就是以每个优选粒子当前位置为中心，设置一个小的搜索范围，然后引入相互独立的局部粒子群(简称“局部群”)并执行局部搜索(即这些局部群会被初始化并执行少量的迭代运算)。迭代运算结束后，各优选粒子会将其个体历史最优位置的适应度值和对应的执行局部搜索的局部群的全局历史最优位置的适应度值相比较。如果优于则用该局部群的全局历史最优位置及其对应的适应度更新相应粒子的个体历史最优位置及其适应度否则该粒子的个体历史最优位置及其适应度不变。判定规则为(k表示进化代数)：

至此，即完成一次竞争进化。接着全局群内所有粒子更新其位置和速度，进入下一次进化。

2.2.3 自适应权重

在PSO算法中，若w取值较大，则粒子的全局搜索能力较强，有利于粒子跳出局部极小点，但同时也会降低算法的局部搜索能力；若w取值较小，则粒子的局部挖掘能力较强，有利于算法收敛，但同时会降低算法全局搜索能力。本文采用自适应权重w来保证算法在快速收敛的同时平衡全局和局部搜索能力[14]：

2.3 PECEPSO算法步骤

综上所述，本文提出了基于前摄估计、竞争进化和自适应权重的PECEPSO算法，该算法步骤简要描述如下：

1) 执行前摄估计过程，确定搜索空间S。

2) 令iter=0(iter表示进化代数)，设当前种群规模为ncur，若ncur

3) 对当前种群执行一次竞争进化过程；

4) 判断是否满足进化终止条件。若满足，则输出所保留的最好解作为未知节点的最优位置估计，算法结束；反之，令iter=iter+1，转入步骤2)。

为不增加硬件成本并保持低功耗特性，本文算法采用RSSI测距技术完成邻居节点间的距离测量。考虑到实际应用中无线信号受环境影响，其通信范围模型不是理想圆形，会存在较大的测距误差，在仿真实验过程中会充分考虑由此带来的测距误差等因素。

3 仿真实验及分析

3.1 仿真说明

本文利用MATLAB 7.0进行仿真实验。为验证算法的有效性和实用性，所有节点(100个)的坐标在网络部署区域(100 m×100 m)内随机生成，并与同类DPSO算法[10]、Standard PSO算法和基于测距的定位算法Improved DV[19]相比较。

实验评价指标为T次实验所得未知节点相对定位误差(估计坐标与实际坐标之间的距离与节点通信半径之比)的算法平均。相关参数设置如下：节点通信半径为30 m；PECEPSO算法的全局粒子群规模为10，最大迭代10次，局部粒子群规模为2，最大迭代4次；DPSO算法的种群规模为30，迭代次数为30；Standard PSO算法的种群规模为50，迭代次数为100。

3.2 仿真及分析

3.2.1 不同锚节点密度时的定位结果比较

锚节点的费用比普通节点高两个数量级，所以锚节点密度将直接关系到整个网络成本大小。图2显示了不同锚节点密度时4种算法的定位效果(测距误差设为25%)。

在图2中，随着锚节点密度的增大，平均定位误差都逐渐减小。以定位误差降低较显著的Improved DV算法为例，当锚节点密度为10%时，其定位误差达40%以上，而当锚节点密度达到最大的50%时，其定位误差下降到了12%左右。这是因为锚节点数目的增加使网络中每个未知节点的邻居锚节点个数也随之增多，未知节点可以获得更多的位置参考信息，更容易被定位且误差降低。可以看到，基于PSO优化思想的3种算法定位误差降低趋势相对锚节点比例增高表现相对稳定，其中本文算法定位效果最好，定位精度明显优于同样基于PSO优化思想的DPSO。在相同的定位误差下，本文算法需要的锚节点数也最少，可见本文算法更能充分有效利用锚节点信息，更能有效节省网络成本。

3.2.2 不同通信距离时的定位结果比较

图3显示了在不同通信距离时4种定位算法的定位效果(测距误差设为25%)。

由图3可以看到，因为节点通信距离变大使得网络连通度提高，所以各算法的平均定位误差均逐渐减小。基于PSO优化思想的3种定位算法表现依然稳定(误差下降程度相对于通信距离增加程度)，其中本文算法的平均定位误差始终保持最小，同样明显优于DPSO算法。另外，在相同的定位误差下，本文算法所需通信半径最小，而通信半径越小，越有利于降低能耗，所以本文算法更有利于节约能耗，延长网络寿命，降低网络维护成本。

3.2.3 不同测距误差时的定位结果比较

针对之前提到的实际应用中无线信号会受环境影响，产生不同程度的测距误差问题，本文进行了研究分析，如图4所示。

由图4可以看到，随着测距误差增大，平均定位误差均逐渐增大，特别是Improved DV算法定位误差表现明显，这主要是因为该算法需要累加测距结果，会造成较大的积累误差，从而严重影响定位精度。而本文算法定位效果依然最好，虽然定位误差也随测距误差增大而增大，但表现相对稳定，尤其是当测距误差较大时，本文算法定位精度仍然很高，可见本文算法的抗误差性能最强，具有更高的有效性和实用性，能适应更广泛的应用场合。

3.2.4 算法计算量分析

算法复杂度及抗测量误差性能比较如表1所示。

在表1中，m表示种群规模；k表示迭代次数；n表示本文算法中局部群的种群规模；l表示本文算法中局部群的迭代次数。

由表1分析各算法进化计算量如下：按照3.1节的参数设置，标准粒子群算法的种群规模m=50，进化次数k=100，所以该算法总的个体进化计算量可表示为a=m×k=50×100=5 000 次；DPSO算法种群规模m=30，进化次数k=30，所以该算法总的个体进化计算量可表示为a=m×k=30×30=900 次；而本文算法的全局群规模m=10，进化次数k=10，局部群规模n=2，进化次数l=4，再考虑到全局群在每次迭代中只有一半最优粒子会进行局部搜索，本文算法总的个体进化计算量可表示为a=m×k×n×l/2 =10×10×2×4/2= 400 次。

由表1可以看到，本文算法复杂度最大，但是通过上述进化计算量分析和仿真实验结果(见图2～图4)可以看到，本文算法达到更高定位精度的同时所需的进化计算量最小。这主要得益于本文对前摄估计、竞争进化及自适应权重等方法的使用。其中前摄估计方法使得算法的搜索空间由整个网络覆盖区域缩小到一个较小的范围，为粒子群算法的执行减小难度和复杂度，使得算法得以更快地找到最优解；竞争进化和自适应权重方法使得算法收敛速度进一步加快的同时增强了其全局和局部搜索能力。

如果对定位精度的要求不高，则迭代运算量还可进一步调小。这样在节约能耗的同时提高定位精度，而且有着极好的抗测距误差性能，本文算法的有效性和实用性已经得到充分证明和体现。

4 结 束 语

针对无线传感器网络节点定位问题，本文提出一种基于前摄估计思想、竞争进化思想和自适应权重的优化定位算法。前摄估计思想通过改进的边界盒方法来合理估计节点所在区域，缩小并限制了可行解空间，在减小计算量的同时加快了算法全局搜索速度；竞争进化思想与自适应权重相结合在保证算法进一步加快收敛的同时增强了算法的全局和局部搜索能力。仿真实验表明，新算法在明显提高定位精度的同时能够有效降低网络成本、节约能耗，并具有对测距误差鲁棒性强的优点。

[1] BOUKERCHE A, OLIVEIRA H A B, NAKAMURA E F, et al. Localization systems for wireless sensor networks[J]. IEEE Wireless Commun, 2007, 14(6): 6-12.

[2] PANWAR A, KUMAR S A. Localization schemes in wireless sensor networks[C]//Proc 2nd International Conference on Advanced Computing & Communication Technologies. Rohtak, Haryana: IEEE, 2012: 443-449.

[3] AKYILDIZ I F, SU W, SANKARSUBRAMANLAM Y. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 393-422.

[4] ZHU S H, DING Z G. Distributed cooperative localization of wireless sensor networks with convex hull constraint[J]. IEEE Trans on Wireless Commun, 2011, 10(7): 2150-2161.

[5] LOW K S, NGUYEN H A, GUO H. A particle swarm optimization approach for the localization of a wireless sensor network[C]//Proc IEEE International Symposium on Industrial Electronics. Cambridge, USA: IEEE, 2008: 1820-1825.

[6] WANG S, HU H S, KLAUS M M. Optimization and sequence search based localization in wireless sensor networks[C]//Proc 3rd International Conference on Emerging Security Technologies. Lisbon, Portugal: IEEE, 2012: 155- 160.

[7] CHENG Y, WANG X, CAELLI T, et al. Optimal nonlinear estimation for localization of wireless sensor networks[J]. IEEE Transactions on Signal Processing, 2011, 59(12):5674-5685.

[8] KANNAN A A, MAO G, VUCETIC B. Simulated annealing based wireless sensor network localization[J]. Journal of Computers, 2006, 1(2): 15-22.

[9] 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: IET Press, 2008: 227-230.

[10] 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, SA, South Australia: IEEE, 2011: 288-293.

[11] CHUANG P J, WU C P. Employing PSO to enhance RSS range-based node localization for wireless sensor networks[J]. Journal of Information Science and Engineering, 2011, 27(5): 1597-1611.

[12] CHEN X, ZHANG B L. Improved DV-Hop node localization algorithm in wireless sensor networks[EB/OL]. (2012-07-19). http://dx.doj.org/10.1155/2012/213980.

[13] GUO H, LOW K S, NGUYEN H A. Optimizing the localization of a wireless sensor network in real time based on a low-cost microcontroller[J]. IEEE Trans Ind Electron, 2011, 58(3): 741-749.

[14] 张亚明, 史浩山, 程伟, 等. 一种无线传感器网络中的进化定位机制[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, 3(4): 633-638.

[15] KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proc IEEE International Conference on Neural Networks. Perth, Australian: IEEE, 1995: 1942-1948.

[16] HU M, WU T, WEIR J D. An adaptive particle swarm optimization with multiple adaptive methods[J]. IEEE Trans Evolut Comput, 2013, 17(5): 705-720.

[17] SIMIC S N, SASTRY S. Distributed localization in wireless adhoc networks[R]. University of California Technical Report, 2002.

[18] 王行甫, 刘志强, 黄秋原, 等. 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.

[19] 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: IEEE, 2010: 472 -476.

编 辑 张 俊

An Improved Optimization Localization Algorithm in WSNs

ZHANG Ya-ming1,2, SHI Hao-shan2, CHEN Ke-song3, and CHENG Wei2
(1. School of Electronics Engineering, Xi’an Shiyou University Xi’an 710065;2. School of Electronics and Information, Northwestern Polytechnical University Xi’an 710129;3. School of Electronic Engineering, University of Electronic Science and Technology of China Chengdu 611731)

Node localization of wireless sensor networks (WSNs) is a key problem in the practical applications. To improve the localization accuracy and reduce the cost, an improved localization algorithm based on particle swarm optimization (PSO) is proposed. In the algorithm, the idea of proactive estimate is introduced to estimate the area of nodes, reduce and restrict the solution space, so as to quicken the search speed of particles, and then the idea of competition evolution and adaptive weighting are used to enhance the global and local search ability when accelerating convergence speed. Simulation results show that, compared with other similar methods, the proposed algorithm can make more effective use of anchor node information, reduce the cost of network, and increase positioning accuracy while significantly reducing the calculation amount. Moreover the algorithm shows robust for communication ranging error.

competition evolution; localization; particle swarm optimization; proactive estimation; wireless sensor networks

TP393

A

10.3969/j.issn.1001-0548.2015.03.007

2013 − 04 − 22；

2015 − 01 − 12

国家自然科学基金(U1233103, 61401360, 61301092)

张亚明(1980 − )，男，博士，讲师，主要从事无线通信、无线传感器网络关键技术等方面的研究.