1、 年 无线电工程 第 卷 第 期：引用格式：高颖，夏斌，张立晔，等差分进化协同定位算法研究无线电工程，（）：，（）：差分进化协同定位算法研究高颖，夏斌，张立晔，袁文浩（山东理工大学 计算机科学与技术学院，山东 淄博）摘要：物联网定位问题可以映射为一个优化问题，通过差分进化算法（，）进行优化求解。在求解过程中，传统的适应度函数没有包含未知节点之间的距离信息，导致距离信息不够全面，使算法的定位精度提高有限。鉴于此，从提高定位精度的角度出发，提出了一种差分进化协同定位算法。构建新的适应度函数，该适应度函数不仅包含已知节点与未知节点之间的距离信息，还包含未知节点之间的距离信息，保证距离信息在优化求解过
2、程被充分利用；采用混沌映射方法保证初始种群均匀分布，使搜索范围变大，提高算法的寻优能力；采用飞行策略，解决因空间维数增大导致算法陷入局部最优解的问题。仿真结果表明，与传统差分进化定位算法相比，差分进化协同定位算法可以有效减少测距误差对定位误差的影响，改善定位性能。关键词：差分进化；定位精度；适应度函数；混沌映射；飞行策略中图分类号：文献标志码：开放科学（资源服务）标识码（）：文 章 编 号：（），（，）：，（），；，；，：；收稿日期：基金项目：国家自然科学基金（）；山东省自然科学基金（）：（）；（）引言物联网被广泛应用在智慧工厂、智能机器人、精准农业等领域，而精确定位是物联网服务应用的关键。因
3、此，开展物联网定位的相关研究具有非常广泛的应用价值和实际意义。根据测距模式，物联网定位算法一般分为测距定位算法和非测距定位算法。在基于非测距的定位算法中，例如，未知节点的位置主要通过连接性信息来确定，不需要额外的设备，但定位精度较低。而基于测距的定位算法在测距方法的辅助下，通过距离工程与应用 或角度信息实现未知节点的定位。该类算法具有良好的定位性能，因此受到了广泛关注。物联网定位问题可以映射为一个优化问题，通常采用智能优化算法进行求解。智能优化算法包括粒子群算法、差分进化算法（，）和遗传算法等。其中具有算法结构简单、易实现、优化效率高、收敛速度快等特点，得到广泛应用。文献采用了基于的定位算法，
4、减少了定位误差，实现了精确定位；文献提出了一种自适应定位算法，该算法自适应地调整每一代的交叉概率和变异因子，可以更好地搜索全局最优位置；文献提出了一种基于方法和启发式的混合算法，使用新的交叉过程来生成新一代个体；文献提出了基于和级数展开的混合定位算法，以获得的最优值作为初始值，采用级数迭代算法进行局部寻优，获得节点的精准位置。以上基于的物联网定位研究通过改进本身或将与其他算法相结合，减少了测距误差对定位精度的影响，对精确定位进行了一些有益探索，但并没有对传统的适应度函数进行改进。因此，本文提出了一种新的协同定位算法，通过改进其适应度函数，确保未知节点之间的距离信息被充分使用，以实现协同定位，提
5、高定位精度。协同定位数学模型在物联网定位区域中设置个已知节点（，）（，）和个未知节点（，）（，），并通过测距技术获取到未知节点和各个已知节点之间的距离信息，以及各个未知节点之间的距离信息，根据距离信息建立协同定位方程组：，（）（）槡，（）（）槡，（）（）槡，（）（）槡，（）（）槡，（），（）（）槡（），（）式中：（）（）槡表示未知节点到各个已知节点的真实距离，（）（）槡表示各未知节点之间的真实距离，和，表示测距误差。传统的差分进化定位算法传统的定位算法是通过将定位问题转化为基于的优化问题，根据达尔文的优胜劣汰、适者生存的思想，通过种群之间个体的相互竞争与合作产生群体智能来指导优化搜索的方向，最
6、终使得优化结果趋向于未知节点的坐标值。算法主要包含以下几个部分。构建适应度函数适应度函数用来评价个体的优劣，数值越小，则该个体越接近最优解，否则该个体与最优解相差越大。传统的适应度函数为：（）（，）（，）槡，），（）式中：，为第代的第个个体。随机生成初始化种群在解空间中随机初始化规模为、维数为的种群，通过式（）随机初始化种群：（，）（），（）式中：和分别表示每一维参数取值的上界和下界，（，）表示随机产生 的随机数。变异操作变异操作是的关键部分，对算法起着重要作用，中的个体根据式（）通过差分变异策略完成变异操作，得到变异个体，（），（）：（），（）式中：、为 的随机整数，并且，为缩放因子，用来控
7、制变异的步长，为差分向量。交叉操作为了进一步增加种群的多样性，交叉操作将变异个体与当前个体进行混合，根据式（）生成交叉个体，（），（）：，（）式中：（，）为交叉概率，为 的随机数。选择操作的选择操作采用“贪婪原则”，通过式（）比较当前个体和交叉个体的适应度函数值，从而选择进入下一代的个体，其表达式为：工程与应用 年 无线电工程 第 卷 第 期，（）（），。（）差分进化协同定位算法传统定位算法所用的适应度函数没有考虑未知节点之间的距离信息，不能充分利用所有距离信息，从而限制定位精度的提高。因此，需要对适应度函数进行改进，充分利用距离信息，减少定位误差。另外，适应度函数的改进导致解空间维数的增加，
8、使定位结果容易陷入局部最优。鉴于此，本算法将会从以下个方面进行改进，以提高定位精度。初始化种群的改进在传统的定位算法中，初始种群是通过式（）随机产生的，无法保证初始种群均匀分布，使搜索范围变小，降低算法的寻优能力。而由混沌映射产生的初始种群使个体在解空间中分布更加均匀、广泛，且个体重复率低。因此，采用混沌映射方法生成初始种群。假定混沌映射生成包含个个体，的初始种群，每个个体，。混沌映射首先随机选取个 的随机数，作为和序列的初始序列，然后按照式（）产生混沌序列：，（）式中：为取余运算。最后通过式（）将混沌序列映射到相应的解空间，生成初始位置：，（），（），（）式中：和分别表示定位区域横坐标的最小
9、值和最大值，和分别表示定位区域纵坐标的最小值和最大值。假设种群规模为，混沌映射与随机生成的初始种群对比如图所示。由图可知，与随机产生的初始种群相比，混沌映射产生的初始种群更加均匀地分布在解空间中。（）混沌映射产生的初始种群（）随机产生的初始种群图随机与混沌映射生成初始种群对比 适应度函数的改进在定位算法中，适应度函数被用来评价当前个体的好坏。在传统定位算法中，通过式（）所示的适应度函数来评价个体，但是该适应度函数只与未知节点到各已知节点间的距离信息有关，使得定位精度提高有限。所以，在本算法中，充分利用节点之间的距离信息构造适应度函数，来指引个体的搜索方向，使其不断向最优位置靠近。根据未知节点到
10、已知节点的距离信息以及未知节点之间的距离信息，可以得到改进后的适应度函数：（）（，）（，）槡，）（，）（，）槡，），（）式中：，为组合运算符。与式（）相比，改进的适应度函数充分利用未知节点之间的距离信息，提高了定位精度。飞行策略的引入飞行策略是自然界中动物常见的觅食和移动方式，可以最大限度地提高资源的搜索效率，增加种群的多样性，并增大搜索范围。该策略服从分布，以较大的概率在小范围内游走，从而加快算法的收敛速度，以较小的概率在较大的范围内游走，从而减少算法陷入局部最优解的概率。而改进的适应度函数使得解空间的维数由二维增加到多维，导致定位结果容易陷入局部最优。因此，在协同定位算法中引入飞行策略，能
11、够减少算法陷入局部最优解的概率。其位置更新式为：（），（）式中：为当前个体，为位置更新后的个体，表示点乘，（）为飞行的步长，表示为：（），（）工程与应用 式中：为常数，通常取值为，、为服从均值为的正态分布，其方差为：（）()()()。（）差分进化协同定位算法的具体步骤为：步骤：初始化种群根据混沌映射方法生成包含个个体的初始种群，其中第（，）个个体表示为，。步骤：变异操作以第代种群的第个个体为基准向量，与随机选取的个不同个体的加权向量差相加，得到，（），（），（），（），（），（）变异个体。，（），（，），（），（，），（）式中：，、，为差分向量。步骤：交叉操作对步骤中产生的变异个体与当前个体按
12、照式（）进行交叉操作，生成交叉个体，（），（），（），（），（），（）。，（），（），（），（），。（）步骤：选择操作对当前个体与步骤中产生的交叉个体分别计算式（）所示的改进的适应度函数，选择适应度函数较小，即定位误差较小的个体作为当前个体，继续进行下一步操作。（）（），（）（）（），（）（），（）（）（），。（）步骤：飞行操作对步骤产生的当前最优个体通过式（）更新个体的位置。步骤：判断是否到达最大迭代次数，若没有完成迭代，则转向步骤；若已达到最大迭代次数，则定位结束，得到未知节点的最优估计位置。差分进化协同定位算法实现的具体流程如算法所示。算法：差分进化协同定位算法输入：所有的距离信息，；种
13、群规模；迭代次数；缩放因子；交叉因子；输出：未知节点的最优估计坐标；混沌映射生成初始种群；通过的变异、交叉操作生成交叉个体；（）（）交叉个体作为当前个体，继续进行后续操作；当前个体继续进行后续操作；对当前个体采用飞行策略进行位置更新；实验结果分析为了更好地验证协同定位算法的性能，实验调用种不同的距离信息：一种是测距误差服从高斯分布的距离信息；另一种是利用测距设备测量的距离信息。传统定位算法和协同定位算法的参数都设置为：种群规模 ，最大迭代次数，。定位误差如下：（）（）槡，（）式中：（，）表示第个未知节点的估计位置坐标。高斯测距误差下的定位性能假定未知节点随机分布在的定位区域，为边长。为减少偶然
14、性，定位结果取 次独立仿真的平均值。测距误差服从均值为、方差为的高斯分布。未知节点分别为和时，定位误差随测距误差方差的变化曲线如图所示。在粒子群定位算法中，粒子群规模，。（），工程与应用 年 无线电工程 第 卷 第 期（），图定位误差随着测距误差方差变化的曲线 仿真结果表明，随着测距误差方差的不断减小，粒子群定位算法、传统定位算法、改进定位算法（）、协同定位算法和半正定（）的定位误差都在不断减少。另外，对于相同的测距误差，协同定位算法和算法的定位误差明显低于其他定位算法，因为这种算法都使用了未知节点之间的距离信息进行定位，改善了定位性能。飞行策略对定位误差的影响如图所示。当未知节点为时，飞行策
15、略以较小的概率在较大的范围内游走，从而降低了算法陷入局部最优解的概率。图飞行策略对定位误差的影响（，）（，）实测测距误差下的定位性能在边长为 的正方形物联网测距场景中，未知节点随机放置在不同的位置，已知节点固定在定位区域的个顶角。用障碍物随机遮挡部分未知节点，模拟非视距环境。物联网采用基于到达时间的测距设备获得测量距离信息。测距设备如图所示，主要由、等集成电路组成。部分测量数据如表所示，第列和第列表示已知节点或者未知节点的位置坐标，第列表示真实距离值，后面的列为测量距离值。从表可以看出，在非视距环境下，测量距离值与实际距离值相差较大，产生较大的非视距误差。图测距设备 表部分测量数据（，）（，）
16、单位：已知节点未知节点真实距离测量距离（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）根据实测数据得到的定位结果如表所示。由定位结果可见，传统定位算法的定位误差为 ，协同定位算法的定位误差为 。与传统定位算法相比，有效减少了非视距测距误差对定位性能的影响。表定位结果（，）（，）单位：实际位置传统估计位置协同估计位置（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）工程与应用 续表实际位置传统估计位置协同估计位置（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）算法复杂度分析传统定位算法主要通过变异、交叉、选择得到最优解，该定位过程占用的时间复杂度近似为（）（），其中种群规模为，已知节点的数目为，未知节点的数目为，迭代次数为。改进协同定位算法首先通过混沌映射方法获得未知节点的初始值，接着利用所有未知节点之间的距离信息实现精确定位，最后通过飞行加快算法收敛速度。该定位过程占用的时间复杂度近似为（）（），为
