混沌粒子群鸡群融合优化的RSSI 质心定位算法

王改云，陆家卓，焦 傲，郭智超，张 琦

（桂林电子科技大学电子工程与自动化学院，广西桂林 541004）

0 概述

物联网被认为是继计算机、互联网后世界信息产业的第三次浪潮，其将传感器技术应用于环境监测、智慧农业和智慧城市等领域［1-2］。在无线传感网络应用场景中，如果传感节点不能获知它们的位置信息，则这些传感器所感知的数据也将没有意义［3-5］。因此，研究无线传感网络的定位技术显得尤为重要［6］。

无线传感网的定位方式分为测距定位和非测距定位两种类型［7-8］。其中，TOA 算法［9］、三边定位算法、RSSI 算法和TDOA［10］算法属于常见的测距定位算法，而APIT 算法、质心定位算法和DV-Hop 算法则属于非测距定位算法［11］。为了解决基础定位算法精度较差且实用性不高的问题，国内外研究人员针对上述算法进行了深入的研究。在国外，ZONG 等人分析了两种环境扰动对RSSI 值的影响，利用卡尔曼滤波对RSSI 值进行预处理，并提出一种三角中心定位算法。LOGANATHAN 等人［13］提出一种利用基于Zigbee 的接收信号强度指示器（RSSI）和数字测定仪来提高移动节点室内定位的新技术。通过改进路径损耗传播模型和凸搜索优化每种定位技术的加权参数来更准确地预测移动节点的坐标，使得定位性能得到大幅提升。BYRNE 等人［14］在RSSI 的基础上优化了室内定位算法，将其应用于室内定位并进行优化，结果表明，该算法在室内应用中具有更高的定位精度。国内研究人员潘琢金等人［15］利用卡尔曼滤波器来优化RSSI 的采集过程，并用锚节点的相关信息对四点质心定位算法的结果进行误差补偿。路泽忠等人［16］将对RSSI 值解算的距离值的倒数和作为权重，得出修正参数对精度进行了修正。张鸿洋等人［17］分析了节点动态与距离的关系，主动删除孤立节点并确定权重，进一步提高定位精度。汪晨等人［18］利用信号识别强度得到的参考节点的距离和位置信息作为人工鱼群算法的适应度函数，达到优化求解过程的目的，从而降低定位误差。

不同定位算法在面对各种类型的应用环境时，需要设计出不同的改进方案。本文利用混沌搜索的随机性、遍历性和鸡群算法（CSO）的多种群性，对粒子群优化（PSO）算法求解过程进行完善，结合RSSI测距的低成本、低功耗以及计算量小的优点优化传统质心定位算法，并提出基于混沌粒子群鸡群融合算法的RSSI 质心定位算法。

1 混沌粒子群鸡群的融合算法

1.1 标准粒子群算法

粒子群算法是一种原理简单、搜索速度快的群体智能算法，其求解最优值的优化思想是模拟群鸟觅食的过程。假设在解空间对速度与位置的初始值都是随机分配的M个粒子进行空间维数为D的最优搜索。粒子群算法的思路是通过个体极值pbest 与全局极值gbest 不断地修正粒子的位置和速度，使得粒子不断向最优解靠拢。若迭代次数为K，则粒子的速度V与位置X的更新为：

其中，w为惯性权重，r1和r2为分布在［0，1］区间的随机数，Pid为个体极值，Pgd为全局极值，c1、c2通常取2。当种群最优解达到预设范围或K等于最大迭代次数时，则终止搜索。

1.2 混沌粒子群算法

现代非线性理论将混沌解释为在确定体系中出现的一种非周期且无规则的运动。虫口模型下的Logistic 方程是 一种典 型的混 沌系统［19］，方程可简化为：

当u取4 及xn为0～1 间的随机数时，方程的输出即可在0～1 间进行无重复、类随机的遍历。因此，通过将混沌搜索与PSO 算法相结合，即可解决PSO 算法中由于粒子的初始化与进化存在极强的随机性而易陷入局部最优的问题。其中，利用混沌对PSO 进行优化可分为以下两点：一是对初始位置和初始速度使用混沌序列优化，以提高种群的遍历性与多样性；二是对当前种群的最优解进行混沌搜索，并使用搜索到的最优结果代替当前种群中任意一个粒子的位置，既可提高收敛速度，又避免易陷入局部最优的缺陷。

1.3 鸡群算法

鸡群算法（CSO）是一种新的仿生学优化算法，主要模拟鸡群的等级制度和觅食行为。CSO 的思想是将鸡群按照鸡的类型进行分组，即每一只公鸡可带领几只母鸡和小鸡成为一组，组内的母鸡会在公鸡的指引下进行觅食，组内的小鸡则只能在对应的母鸡身边觅食，且不同组间允许信息交流。需要注意的是，当这种等级制度应用在求解群体最优值时，公鸡、母鸡、小鸡的分类是根据适应度从好到坏区分的，在每轮搜索中都会对组内的公鸡、母鸡和小鸡进行重新选取。

利用CSO 的多种群性对CPSO 优化的方法如下：

1）在首轮搜索时对种群的适应度值从小到大进行排序，然后按照排好的顺序将种群中所有粒子按比例分为A 粒子（公鸡）、B 粒子（母鸡）、C 粒子（小鸡）3 类，并按规则对应分组，其余轮次则通过比较组内的适应度值来更新组内的成员类型，无需变换组号的顺序。

2）在每轮更新粒子的速度与位置时A 类粒子作为组内优秀的个体，更新公式与式（1）、式（2）相同。

B 类粒子在A 类粒子的指引下进行搜索，同时也要吸收其他组的经验，其速度与位置的迭代公式可更改为：

其中，Pgd从式（1）的全局最优变为组内最优，r3为0～1的随机数，Xf是其他组的最优位置，c3通常取2。而C 类粒子只能在B 类粒子附近搜索，其位置迭代公式为：

其 中，XBg是C 粒子对应的B 粒子的位置，FL 通 常取0.5。

2 CPSCSFO 优化的RSSI 质心定位算法

2.1 RSSI 质心定位算法

根据接收信号的强度指示来计算发送节点到接收节点的距离是RSSI 的测距原理。经实验证明，无线信号的传播服从Shadowing 模型的概率分布。因此，本次实验的无线电信号传播陨耗模型可表示为［20］：

其中，Pr为信号接收强度指示值，Pt为发射节点发出的信号指示值，d0通常取1 m 作为参考距离，PP（Ld0）为参考距离为d0时的路径陨耗功率，χ代表高斯分布因子，d为收发节点之间的距离。在节点发送数据帧时，利用该模型可得到未知节点到锚节点之间的距离。

若未定位节点有n个参考节点，坐标分别用（x1，y1），（x2，y2），…，（xn，yn）表示，则原始质心定位算法的计算方法如式（8）所示：

加权质心定位算法则只选取其中最近的3 个锚节点A、B、C作为参考，并将这三点所围成的三角形的质心坐标作为最优解。当离未知节点最近的锚节点数小于3 时，则选取最近的已定位节点作为伪锚节点来进行辅助定位。其中，假设需定位节点到A、B、C3 个节点的距离用dA、dB、dC表示，那么所求节点的坐标则如式（9）所示：

若该方法中计算各节点的距离是通过RSSI 的测距模型来实现的，则称该方法为基于RSSI 的加权质心定位算法。

2.2 适应度函数

适应度函数是群智能算法用来判断当前粒子位置好坏的标准。在本次实验中，为了修正种群粒子的位置，使其不断向最优解靠拢，需要构造合适的适应度函数来指引种群粒子的搜索方向。假设当前未定位节点的3 个参考节点坐标分别为（xa，ya）、（xb，yb）和（xc，yc），则该节点到3 个参考节点的距离可表示为：

结合由RSSI 测距模型测量出的该节点到3 个参考节点的距离（d1，d2，d3），即可构造出混沌粒子群鸡群融合算法的适应度函数为：

2.3 CPSCSFO 优化算法步骤

混沌粒子群鸡群融合算法（CPSCSFO）优化RSSI质心定位的基本思路为：在利用RSSI 测距模型获知参考节点与未定位节点的距离后，在求解最优解时使用CPSCSFO 算法进行空间搜索，并利用构造好的适应度函数判断出粒子位置优劣性，最后得到的最小适应度值对应的坐标，就是所求定位节点的坐标。CPSCSFO求解最优值的算法流程如图1 所示。

图1 CPSCSFO 算法流程Fig.1 Procedure of CPSCSFO algorithm

CPSCSFO 算法步骤如下：

步骤1设置一个M个粒子的种群并定义相关变量，利用混沌序列初始化每个粒子的初始速度与初始位置。

步骤2计算出各个粒子当前的适应度值，确定个体最优与全局最优。

步骤3判断是否需要重新建立粒子群的等级体系（即组内重新分类），如果需要，则重新建立，否则执行以下步骤。

步骤4对整个种群得到的适应度值进行排序，并以此为基础确定种群的等级体系。

步骤5按照等级体系确定A 类粒子（公鸡）与B 类粒子（母鸡）之间的隶属关系，确定B 类粒子（母鸡）与C 类粒子的母子关系。

步骤6A、B 和C 类粒子根据其对应的鸡群算法下的更新公式进行速度与位置的更新。

步骤7求解适应度值，对最优粒子利用混沌搜索进行二次寻优，若存在更优值，则用该值对应的粒子代替种群中的任意一个粒子，并更新个体最优与全局最优。

步骤8判断是否到达设定最大迭代次数，若是则终止算法，否则跳回步骤3。

3 仿真结果与分析

3.1 仿真实验

根据建立好的数学模型和适应度函数，本文对传统质心定位算法、加权RSSI 质心定位算法、PSO-RSSI质心定位算法与CPSCSFO-RSSI 质心定位算法进行仿真实验，并在求出不同λ（锚节点所占比例）、R（节点最大通信距离）下各种算法的平均定位误差后，通过实验对比验证了本文算法在无线传感网定位上具有更好的优越性。具体的参数配置如表1 所示。

表1 实验参数设置Table 1 Experimental parameter setting

此外，锚节点数量为ngps=λn，而未定位节点的数量为nunl=n−ngps。若锚节点以时间周期T向周围发送数量N（st）=S的数据包，未定位节点在监听时间t=（S+1−ε）T（0<ε<<1）内收到的数据包量为N（rt），则该未定位节点接收数据包的成功的概率SR 可用式（12）表示。这两个收发节点互为邻居节点的条件是SR>SRth。

图2 是表1 参数下的节点分布，其中，*表示锚节点，圈号表示未定位节点。当这些未定位节点利用各种算法求出对应坐标后，还需要计算出对应算法下的平均定位误差以比较不同算法的定位精确度。

图2 节点分布Fig.2 Node distribution

假设（xi，y）i是未定位节点用各种算法求解后的坐标值，（x，y）是该节点设定的实际坐标值，则实验平均定位误差Lerr的求解公式为：

3.2 结果分析

为了保证实验结果的精准性，每个点选取的平均定位误差值都是经过20 次重复实验后，将每次得出的结果进行求和再取均值而得到值。图3 是R=200 时，4 种算法随着λ变化时平均定位误差的比较曲线。

图3 4 种算法的平均定位误差与λ 变化曲线Fig.3 Curves of average positioning error and λ change of four algorithms

从图3 可以看出，当锚节点数随着比例增大时，4 种算法的定位误差都随之下降。这是由于锚节点增加后，整个系统的定位参考点呈增大的趋势，从而可以选择更好的锚节点作为定位参考点。另外，在λ增大的整个过程中，相比于其他3 种算法，CPSCSFO-RSSI 质心定位算法的平均定位误差值较低，这说明本文算法拥有更高的定位精度。其中，CPSCSFO-RSSI 算法与PSO-RSSI 算法相比也有明显的优越性（特别是在λ<0.25 时）。这是因为引入的混沌搜素与鸡群算法对PSO 起到了优化的作用，能有效解决PSO 算法容易陷入局部最优解的问题，从而进一步提高了定位精度。

由于锚节点的价格比较昂贵，在实际应用中增加锚节点的数量相当于提高了系统成本。从图3 可以看出，当λ大于0.25 后，CPSCSFO-RSSI 曲线下降不明显，且与PSO-RSSI 曲线相差也较小。因此，本文选取λ=0.25 时改变另外一个影响定位精度的因素——R（最大通信半径）的值，进一步评估这4 种算法的性能，结果如图4 所示。

图4 λ=0.25时4种算法的平均定位误差-最大通信半径变化曲线Fig.4 Average positioning error maximum communication radius curve of four algorithms when λ=0.25

从图4 可以看出，随着通信最大半径的增大，4 种算法的平均定位误差呈下降趋势，且其中定位误差最小的是CPSCSFO-RSSI 定位算法。其原因可分为以下两点：一是因为随着R的增大，未定位节点的邻居节点也随之增多，连通度增大；二是因为CPSCSFO 融入了混沌搜索的随机性、可遍历性的优点，从而有效改善了粒子群算法容易陷入局部最优的缺陷，同时利用鸡群算法的多种群性，达到进一步提高搜索精度的效果。

表2 为4 种算法当λ=0.25 及R为190 m、200 m、210 m、220 m、230 m 时的平均定位误差值。可以看出，本文算法的定位精度较高。其中，相比于原始质心定位和加权RSSI 质心定位算法，基于PSO-RSSI 质心定位算法的平均定位误差分别降低了约22%与11%，而基于CPSCSFO-RSSI算法则分别降低了约31%与21%。为了更清晰直观地表达PSO-RSSI 与CPSCSFO-RSSI算法的定位误差效果，本文实验选取λ=0.25、R=220 时1000 m×1000 m 范围内的定位情况，定位误差的效果对比如图5 所示。其中，星号代表锚节点，圈号代表已经定位的节点，实际位置与利用算法定位得到的位置之间的距离用实线表示。可以看出，图5 中CPSCSFO算法下的绝大部分线段，都比PSO 算法下的线段短。这是由于新算法融合了混沌搜索与鸡群算法，从而具有比PSO 算法更高的搜索精度。

表2 λ=0.25 时4 种算法的平均定位误差Table 2 Average positioning error of four algorithms when λ=0.25

图5 PSO 与CPSCSFO 算法定位误差对比Fig.5 Comparison of positioning error between PSO and CPSCSFO algorithm

3.3 算法复杂度分析

在PSO-RSSI 与CPSCSFO-RSSI 质心定位算法的定位过程中，整个算法复杂度的主要开销可分为两个方面：一是利用RSSI 测距模型进行测距；二是利用算法进行最优解的搜索。由于RSSI 测距的时间复杂度与锚节点数成正比关系，即O（ngps）；而本次选取的最优比例降至λ=0.25 处，因此利用RSSI 测距时间复杂度也会随之下降。而算法在搜索过程所产生的复杂度，主要与种群的数量M和最大迭代次数N的乘积成正比，即O（M×N）。

CPSCSFO 在PSO 基础上引入的鸡群算法只是改变了计算公式，并不会增加空间复杂度的开销。它的额外开销在于使用混沌搜索时所占用到的内部存储空间。但是空间复杂度和时间复杂度是互相影响 的，图6 给出了 当R=220 与λ=0.25 时PSO 与CPSCSFO 算法在求某个未知节点坐标时的适应度曲线。其中，PSO1 表示同样在该点处，PSO 陷入局部最优解的情况，PSO2 则是精准定位时的情况。相比于PSO 算法，CPSCSFO 算法因融合了混沌序列与鸡群算法的优点，既可以避免出现类似于PSO1 曲线的情况，也提升了算法的收敛速度。在基于PSO 的质心定位算法中，由于PSO 具有容易早熟的缺点，最大迭代次数N1的值若小于500 就无法保证解的精准性，而CPSCSFO 由于经过混沌序列的初始化，只需把N2的值设定为300 就可得到算法的最优解。显然CPSCSFO 质心定位算法的时间复杂度O（M×N2）小于PSO 质心定位算法的O（M×N1）。

图6 2 种算法在R=220、λ=0.25 的某一点处适应度-迭代次数曲线Fig.6 Fitness iteration degree curve of two algorithms at a point of R=220 and λ=0.25

4 结束语

传感节点的定位技术是无线传感网络实际应用中至关重要的部分。本文采用低成本、低功耗的RSSI 测距模型对传感节点进行测距，在无需增加外设的情况下引入了混沌粒子群鸡群融合算法来进行最优搜索，从而达到既提高定位精度又不增加系统成本的目的。仿真实验结果表明，混沌粒子群鸡群融合算法的RSSI 质心定位算法相比于原始质心定位算法、加权RSSI 质心定位算法和PSO-RSSI 质心定位算法具有较高的定位精度、较快的收敛速度以及较强的实用性。但是在多样的地理环境中，RSSI信号接收的强弱会受到各种不同的环境因素影响，因此下一步研究方向是提高RSSI 测距在特殊环境下的精准性与泛用性。