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

摘要：为进一步提高无线传感器网络（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 引言

1 基本算法原理

1.1 粒子群算法

其中：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。

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

7）将A、B系统进化更新后的所有个体混合，并重新为A系统随机挑选个体，B系统保持不变，实现了个体间交流信息共享。 8）重复以上步骤4）～7）直到达到迭代终止条件或者最大迭代次数，输出系统最小适应度值对应的最优解。

2.3 性能仿真

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

3 双系统协同进化算法

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

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

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

3.2 仿真分析句子不完整

图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次仿真取的平均值，由于算法初始化的随机性，并不能保证每一次随机初始化赋值均符合要求，所以平均结果与实际每个节点的定位误差是有所不同的。

4 结语

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

参考文献：

[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.