基于改进双系统协同进化算法的无线传感器网络节点定位

摘要：为进一步提高无线传感器网络（WSN）中节点的定位精度，提出了一种双系统协同进化（BCO）算法。改进算法利用粒子群优化（PSO）算法快速收敛的特性和混合蛙跳算法（SFLA）较高的寻优精度的特性，在较少的迭代次数内快速收敛且实现深度搜索达到较高的精度。仿真实验结果表明：在应用双系统协同进化算法对测试目标函数进行求解时，能非常接近最优解；同时将该算法应用到基于接收信号强度值（RSSI）测距的节点定位中，预测位置与实际位置的绝对误差在0.05m范围内；相比基于RSSI的分步粒子群算法（IPSORSSI），其定位精度至少提高了10倍。

关键词：节点定位；粒子群算法；蛙跳算法；并行系统；协同进化；定位精度

中图分类号： TP393 文献标志码：A

英文摘要

Abstract：In order to improve the locating accuracy in Wireless Senor Network （WSN） node localization， an algorithm based on Particle Swarm Optimization （PSO） and Shuffled Frog Leaping Algorithm （SFLA） was proposed， namely Bisystem Cooperative Optimization （BCO） algorithm. With the advantages of fast convergence in PSO and high optimization precision in SFLA， the proposed algorithm was easier to converge through less iterations and achieve higher accuracy of depth search. The simulation experiments indicate that the BCO algorithm is effective. First， the BCO algorithm can be very close to the optimal solution when it is used for solving the test target functions with better locating accuracy and higher convergence speed. Meanwhile， when the proposed algorithm is used for node localization based on Received Signal Strength Indicator （RSSI）， the absolute distance error of the prediction location and the actual location is less than 0.05 meters. Compared with the Improved Particle Swarm Optimization algorithm based on RSSI （IPSORSSI）， the locating accuracy of the proposed algorithm can be increased 10 times at least.

英文关键词

Key words：node localization； Particle Swarm Optimization （PSO） algorithm； Shuffled Frog Leaping Algorithm （SFLA）； parallel system； cooperative optimization； positioning accuracy

0 引言

在无线传感器网络（Wireless Senor Network，WSN）应用中，精确地获取传感器节点位置信息对传感器网络的整个远程监控和实时监测来讲至关重要，从而定位作为无线传感网络的关键技术，一直是研究的热点。节点定位有基于测距和非测距两种方式，其中测距定位算法具有定位精度相对较高、通信开销较小等优点，得到众多研究者的关注。测距定位[1]包括节点测距和定位两部分，首先通过接收信号强度值（Received Signal Strength Indicator，RSSI）、到达时间（Time of Arrival，TOA）、到达时间差（Time Difference of Arrival，TDOA）、到达角（Angle of Arrival，AOA）[2]文献2引用只针对AOA算法还是都包含到达角（Angle of Arrival， AOA）[2]等技术测量出等技术测量出待定位节点和信标节点的距离，然后再通过三边测量法、三角测量定位、极大似然估计、最小二乘法等算法[3]实现待测节点的位置估计。当前有研究者将定位问题通过数学模型转换为对节点位置的优化问题，通过智能算法对节点进一步优化来提高定位的精度。文献[4]在标准粒子群算法的基础上对适应度函数进行修正提出了带罚函数的粒子群优化（Particle Swarm Optimization with Penalty Function，PSOPF）算法，但其定位精度较低。文献[5]提出的基于粒子群优化（Particle Swarm Optimization，PSO）算法的定位算法中，锚节点中心位置被定义为到底定义为哪一个，还是两个都有？锚节点的中心位置被定义为初始估算位置和初始全局最优解的均值来降低算法误差。应该加上“的均值”三个字。初始估算位置和初始全局最优解的均值来降低算法的误差。一般情况下，由于中心位置和实际位置相差较大，因此，该算法的定位精度较低，算法收敛速度较慢。文献[6]提出的基于PSO的定位算法将均匀分布的测距误差的平均值作为优化目标来降低定位误差，实际上，节点的测距误差是满足高斯分布的，因此，算法的定位精度较低。文献[7]提出具有自动过滤锚节点机制的分步粒子群优化（Improved Particle Swarm Optimization，IPSO）算法，但是算法所用锚节点数目较多，定位精度提高不多。针对定位精度低这一主要问

题，本文利用PSO快速收敛的特性和混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）较高的寻优精度的特性，提出基于PSO和SFLA的双系统协同优化（Bisystem Cooperative Optimization，BCO）算法，并通过仿真函数验证了所提出的双系统协同算法的性能；同时将其应用到WSN的节点定位优化中，验证了算法的有效性。

1 基本算法原理

1.1 粒子群算法

粒子群算法[8]中的每一个粒子均是目标函数的一个潜在可行解，粒子在可行域中不断地更新自己的位置和速度来寻找最优解。所有粒子都用一个适应度函数来判断目前位置的好坏，粒子具有记忆性，知道到目前为止发现的自身最好的位置和整个种群中所有粒子发现的最好位置。设粒子群优化算法解空间的维数为D，总粒子群数为N，粒子i当前位置为Xi=（x1， x2，…， xD），当前飞行速度向量为Vi=（v1，v2，…，vD），粒子在每一次迭代过程更新自己的位置和飞行速度，更新方程如下：

1.2 混合蛙跳算法

混合蛙跳算法[9]是一种基于群体的协同搜索方法，具有局部深度搜索和全局信息交换的特点。算法中设随机生成的F只青蛙构成初始化群体P=[p1， p2，…， pF]，每只青蛙的维数就是解空间的维数设为D，则每只青蛙用pi=（pi1， pi2，…， piD）表示。该算法将可行域中蛙群个体按照适应度值的大小降序排列，按照一定的规则分组。SFLA的核心部分主要在于蛙群的局部搜索，设最大跳跃距离为dmax， 全局的最优蛙的位置记为pg与初始化群体中Pi有何关系，是否对应，是否也为向量？该处pg是所有初始个体pi中最优个体，也属于pi中的一个个体，是向量。，每个团体局部最优位置记为pb，最差蛙记为pw，那么最差蛙的更新公式如下：

其中：rand为（0，1）上的随机数；d为每只蛙的跳跃距离。那么最差解就通过式（3）、（4）来进行位置更新。如果更新后的个体的适应度值小于原位置的适应度值，说明该个体已经跳跃到更优的位置，则保留此次更新的位置。如果位置更新后没有跳跃到更好的位置则用pg代替式（3）中的pb重新利用更新公式进行位置更新；如果依旧没有跳跃到更好的位置，那么就采用随机更新，重新随机加入新个体来替代最差蛙。

2 BCO算法

双系统协同进化思想是指利用A、B两个并行系统分别演化同一个目标函数，但是从整个系统来看A、B系统并不是完全孤立的进化，二者个体间进行信息交流共享来实现协同进化，并利用两个系统中的最优个体引导进化寻优方向。该算法结合了粒子群算法快速收敛和蛙跳算法深度搜索的优点，并且具有较强的鲁棒性。

2.1 算法改进思路

BOC算法利用PSO算法和SFLA对同一目标函数进行优化，二者的最小适应度值在不同进化时期具有不同的特点：蛙跳算法在迭代进化前期比粒子群算法拥有更小的适应度值，说明SFLA中个置更接近于最优解，用该最优解指导PSO算法的进化方向会提高算法的收敛速度；在迭代进化中期，PSO算法比SFLA有更小的最小适应度值，此时用对应位置的最优解去指导蛙跳算法进化，就会大大减少其迭代次数而找到最优解，提高收敛速度；在进化的后期，SFLA具有深度搜索的能力，其全局最优解的位置更接近于真实解，用此最优解指导PSO算法的进化方向，使其具有较高的精度。利用双系统协同进化的思想，将PSO算法与SFLA分别独立复制给A、B两个子系统并分别演化同一个目标函数，两个算法在整个系统中相辅相成，相互指导进化，加速了收敛且提高了优化精度。此外，整个系统中，每个子系统除了利用两者中的最优解位置指导进化方向以外，系统之间又进行了个体交流实现信息共享，蛙跳算法进行个体交流以后可以将每组中最差蛙进行替换从而更快地寻找到最优解。在算法复杂度方面，通过融入PSO算法的个体来替代基本SFLA中部分个体，所以该算法中的个体总数相比于SFLA并没有增多，标准 PSO算法具有参数少、模型简单、快速收敛等优点且算法复杂度并不是很高，从整体上来看，所提算法的复杂度并没有增加很多，但是算法的优化精度和收敛速度却得到了提高。

2.2 算法步骤流程

本文所提的双系统协同进化算法中，A系统采用混合蛙跳算法，B系统采用粒子群算法，其实现步骤如下：

1）设定粒子群算法和混合蛙跳算法的参数、各自总个体数、最大迭代次数，以及随机产生初始群体的位置和速度。

2）计算B系统中每一个个体的自适应度值，寻找出粒子群算法的全局最优个体记录其位置是否黑斜红线标注的globe，pg，均为矢量，需要用黑斜体表示。凡""所涉及的到globe，pg均为矢量，用黑斜体表示，globe及其对应的最小适应度函数值fb。

3）计算A系统中每个个体的适应度函数值，标记全局最优蛙位置pg以及对应的最小适应度函数值fa。

4）比较A、B系统中fa与fb的大小，如果fa小于fb，说明A系统的最优解pg更接近于真实解，则pg来替换B系统全局最优解globe；反之用B系统的最优解globe替换A系统的最优解pg。

5）将A系统按照适应度值大小进行降序排列，按照第1个个体分在第1组、第2个个体分在第2组、…、第m个个体分在第m组、第m+1个个体分在第1组、第m+2个个体分在第2组的分组原则分为m个组，组内个体按照蛙跳算法的更新机制和步骤4）中得到的全局最优解进行个体更新进化，直到m个族群中个体更新完全，计算个体适应度值，并分别记录A系统的全局最优解是否黑斜pg和相应的最小适应度值fa。

6）将 B系统按照粒子群算法的进化规则依据步骤4）中得到的最优解指导个体的更新进化，并记录B系统的全局最优解globe和最小适应度值fb。

7）将A、B系统进化更新后的所有个体混合，并重新为A系统随机挑选个体，B系统保持不变，实现了个体间交流信息共享。

8）重复以上步骤4）～7）直到达到迭代终止条件或者最大迭代次数，输出系统最小适应度值对应的最优解。

2.3 性能仿真

为了验证改进双系统协同进化算法的性能，采用标准测试函数进行优化寻找最优解。下面对比各种算法对6个标准函数的寻优能力，详细函数解析式和解空间搜索区域如表1[10]所示。对于仿真所用的标准函数可分为两类[11]：1）Sphere、Quadric、Rosenbrock是典型的单模函数，其中Rosenbrock函数是单峰连续函数，其极小点所在的山谷易于找到，但取值区间走势平坦，极难收敛到全局最优点，是测试算法全局收敛性能的经典函数。2）Griewank、Rastrigin、Schatter F6是具有较多局部极值的多模函数，可以有效检验算法的群体多样性、全局搜索性能、逃离局部极值并避免早熟的收敛能力。其中：Griewank 函数是多峰多极值函数，有众多局部极值，种群极易陷入局部极值中，主要用来评价算法的探索、开发能力；Rastrigrin 函数为多极值函数，在解空间内存在大约10D 个（D为解空间维数）局部极小点；Schaffer F6 函数是具有强烈振荡的多峰函数。

在标准函数的测试中，对于单模函数，以其理论最优值的1‰为标准，多模函数以最优理论值5‰为标准，如果最小适应度值小于以上标准说明该算法取得了正确解。表2中是以20维解空间为例，不同算法对不同标准函数的寻优能力进行综合评判。随机初始化个体寻优，为了具有对比统一性，此处采用了归一化处理，归一化值较小说明函数寻优的最小适应值也是较小的。实验中采用带罚函数的粒子群优化（PSOPF）算法、文献[12]提出的基于高斯算子及混沌变异算子的混合蛙跳算法（LogisticGaussian Shuffled Frog Leaping Algorithm，LGSFLA）与本文的双系统协同优化（BCO）算法进行寻优测试对比。实验中，PSOPF采用100个个体，LGSFLA中蛙群分为10组、每组20只个体，双系统则采用二者个体数目的结合；每种算法分别进行300次迭代循环，对每种结果进行50次平均，其结果如表2所示。

由表2可知，无论是病态单峰函数还是具有较多局部极值的多峰函数，相比PSOPF和LGSFLA，双系统协同进化算法有以下特点：寻优成功率较高，体现了算法的鲁棒性；归一化的最小适应度值很接近理论值，说明了深度搜索能力比较强，算法的优化精度较高；在算法的收敛性方面，由于利用两种基本算法中最优个体指导进化方向，所以收敛速度快于LGSFLA。

3 双系统协同进化算法

在传感器节点定位中的应用

下面将改进的双协同进化算法用于无线传感器网络定位的问题，验证本算法在最优解寻优精度上的性能。对于传感器定位问题，由于传感器节点上自带的RSSI指示功能，采用基于RSSI算法测距并不增加硬件设备成本[13]，所以该算法建立在RSSI测距的基础上对定位计算进行优化。在仿真研究中，以平均定位误差AVE作为定位误差大小的评判标准，为了便于比较，所有定位误差均为绝对误差，其公式如下：

由第2章具体指哪一节可知，利用双系统协同进化算法求解优化问题时，该算法不仅有较高的优化精度并且具有收敛速度快的优点。将该方法用于函数f（x，y）寻找最优解的问题上，可以提高未知节点的定位精度。

3.2 仿真分析句子不完整

仿真实验以Matlab 7.0为平台，节点的通信半径设置为10m， 30个传感器节点随机分布在为何纵坐标只到30？处图1的横纵坐标为0-30m，所给图1表示的不全，我会把完整的图1 上传30m×30m的正方形区域内，锚节点比例为5%，最大迭代次数为100，每一个节点定位预测值选取20次平均值。用带有罚函数的粒子群算法和双系统协同算法进行仿真预测，结果如图1所示。

图1是对30个未知节点位置仿真，由图1可知，实际位置与预测位置几乎完全重合，绝对误差值较小，显示出双系统协同算法具有高精度估计的性能，而带有罚函数的粒子群算法节点预测位置与实际位置还是有较大的距离误差。由于节点是随机产生的，说明双系统协同算法具有普遍适用性和稳定性。

为了验证所提出的双系统协同进化算法求解节点定位的性能，实验仿真选取图1中未知节点为测试目标，利用具体的仿真数据定量地说明所提算法具有优化精度高的优点。实验中用绝对误差来衡量算法定位性能的优劣，测距误差控制在1%内，锚节点比例为5%的范围内，将双协同进化算法与PSOPF、IPSO在定位精度、收敛速度、绝对误差距离方面进行性能比较，结果如表3所示。

由表3可知，PSOPF在求解节点定位时，其精度误差在1.5m的范围内，IPSO的定位误差和收敛速度得到改善，其精度要优于PSOPF算法，但效果不明显。对比表3可知，双系统协同算法的定位精度是IPSO算法的10倍，更接近于真实位置；而从收敛的代数来看，双系统协同算法的收敛速度与IPSO算法相当，说明本文所提出的算法具有收敛速度快的优点。从表3整体上来看，双系统协同进化算法的性能要优于以上其他算法。

图2给出了锚节点个数对定位精度影响关系图，图中比较了带罚函数的粒子群（PSOPF）算法、分步粒子群（IPSO）算法、标准粒子群（PSO）算法以及双系统协同算法的性能。图2在进行30次仿真取的平均值，由于算法初始化的随机性，并不能保证每一次随机初始化赋值均符合要求，所以平均结果与实际每个节点的定位误差是有所不同的。

从图2可知，四种算法均是绝对误差随着锚节点个数的增多呈线性趋势，而双系统协同优化算法的绝对误差小于其他算法，表明该算法整体上具有深度搜索的能力、拥有较高的定位精度。同时对于PSO与PSOPF算法来说，IPSO分步粒子群算法和双系统协同进化算法的定位精度更好。而本文算法随着锚节点数量的逐渐增加其定位绝对误差减小的幅度并不是很大，说明可以使用较少的锚节点进行高精度的节点定位。

图3是在不同的测距误差比例情况下绝对误差对比情况。由图3可知：在测距误差比例较小、在10%的误差内时，PSOPF、IPSO和双系统协同算法的绝对误差都很小，PSOPF算法和双系统协同算法误差敏感度较低，二者性能相当；但当测距误差在10%以上时，双系统协同算法的误差忍受能力明显优于PSOPF算法，也说明本文算法深度搜索能力强；虽然在10%～20%内有IPSO低于本文算法，但是在整体上本文所提算法性能要优于IPSO算法。在不同的测距误差下，双系统协同算法的定位绝对误差波动幅度很小，反映算法性能比较稳定，也即说明了该算法有较强的鲁棒性。

4 结语

本文在研究粒子群算法和混合蛙跳算法的基础上提出了双系统协同进化算法，该算法充分结合了两者的优势，有较高优化精度的同时提高了收敛速度。文中通过测试函数对该算法进行验证，结果说明了改进的算法具有高效的寻优能力和鲁棒性。本文随后将该算法用于传感器节点定位的问题中，仿真比较了该算法在定位优化求解中的性能。仿真结果均说明本文所提算法定位精度优于PSO、IPSO和PSOPF算法，同时通过比较锚节点个数和节点间的测距误差对不同算法的定位精度的影响，均验证了所提算法的有效性。

参考文献：

[1]PATWARI N， ASH J N， KYPEROUNTAS S，et al. Locating the nodes： cooperative localization in wireless sensor networks[J]. IEEE Signal Processing Magazine， 2005， 22（4）：54-69.

[2]NICULESCU D， BATH B. Localized positioning in Ad Hoc networks [J]. Ad Hoc Networks， 2003，1： 247-259.

[3]CHENG H. Improve research on node localization algorithm based on RSSI in wireless sensor networks [D].Chongqing： Chongqing University of Technology，2013：29-32.（程海军.基于RSSI的无线传感网络定位算法的改进研究[D].重庆：重庆理工大学，2013：29-32.）

[4]CAI S，GAO Z， PAN H， et al. Localization based on particle swarm optimization with penalty function for wireless sensor network[J]. Journal of Computer Research and Development，2012，49（6）：1228-1234.（蔡绍滨，高振国，潘海为，等，带有罚函数的无线传感网络粒子群定位算法[J].计算机研究与发展， 2012， 49（6）：1228-1234.）

[5]GOPAKUMAR A， JACOB L. Localization in wireless sensor networks using particle swarm optimization[C]// Proceedings of the 2008 IET Conference on Wireless， Mobile and Multimedia Networks. Piscataway： IEEE， 2008：227-230.

[6]KULKARNI R V， VENAYAGAMOORTHY G K，CHENG M X. Bioinspired node localization in wireless sensor network [C]// Proceeding of the 2009 IEEE International Conference on Ststems， Man and Cybernetics. Piscataway：IEEE， 2009：205-210.

[7]FENG X， LV S. Wireless sensor networks locating algorithm based on RSSI and splitstep particle swarm optimization algorithm[J]. Control and Decision，2014，29（11）：1966-1972. （冯秀芳，吕淑芳.基于RSSI和分步粒子群算法的无线传感器网络定位算法[J].控制与决策， 2014， 29（11）：1966-1972.）

[8]LIU Z，LIANG H. Parameter setting and experimental analysis of the random number in particle swarm optimization algorithm [J]. Control Theory & Applications， 2007，27（11）： 1489-1496.（刘志雄，梁华.粒子群算法中随机参数的设置与实验分析[J].控制理论与应用， 2007，27（11）： 1489-1496.）

[9]CUI W，LIU X，WANG W， et al. Survey on shuffled frog leaping algorithm [J]. Control and Decision， 2012， 27（4）：481-487.（崔文华，刘晓冰，王伟，等.混合蛙跳算法研究综述[J].控制与决策，2012，27（4）：481-487.）

[10]HE S， WU Q H， SAUNDERS J R. Group search optimizer： An optimization algorithm inspired by animal searching behavior [J].IEEE Transaction on Evolutionary Computation， 2009，13（5）：973-990.

[11]ZENG C，LI N，WANG W， et al. An improved group searching optimization method [J]. Transducer and Microsystem Technologies， 2012，31（9）：28-31.（曾超，李娜，王维，等.一种改进的群搜索优化方法[J].传感器与微系统，2012，31（9）：28-31.）

[12]LI Z. Research on fuzzy Cmean clustering algorithm based on particle swarm optimization and shuffled frog leaping algorithm [D]. Changsha： Changsha University of Science and Technology， 2011：15-19. （李真.融合粒子群和蛙跳算法的模糊C均值聚类算法研究[D].长沙：长沙理工大学，2011.：15-19）

[13]FANG Z，ZHAO Z，GUO P， et al. Analysis of distance measurement based on RSSI [J]. Chinese Journal of Sensors and Actuators， 2007，20（11）：2526-2530.（方震，赵湛，郭鹏，等.基于RSSI测距分析[J].传感技术学报，2007，20（11）：2526-2530.）