一种基于遗传算法的三维多目标定位方法

摘要

本发明实施例提供了一种基于遗传算法的三维多目标定位方法，涉及信号源定位领域。方法包括：建立三维空间模型；选取多个传感器节点，记录每一传感器节点在三维空间模型内的位置坐标；获取多个传感器节点中每一传感器节点到源节点的估计单位方向向量；根据每一传感器节点的位置坐标以及每一传感器节点到源节点的估计单位方向向量计算得到源节点的坐标。上述方法通过遗传算法对射线选择，在减少计算机的运算量的同时，可对空间内存在的多个信号源进行定位，低成本且准确率高。

说明书

技术领域

本发明涉及信号源定位领域，具体而言，涉及一种基于遗传算法的三维多目标定位方法。

背景技术

无线电发射源定位方法主要可以分为两类：距离无关定位和距离相关定位方法。距离无关的定位方法使用拓扑信息推测目标的位置，因此节省硬件花费、妥协精度和定位估计的规模。距离相关定位方法主要基于到达时间(TOA)，到达时间差分(TDOA)，到达角(AOA)，以及接收信号场强(RSS)来定位等。

遗传算法是由Holland于1975年提出的一种基于概率搜索的算法，已经应用于一系列的组合优化问题。遗传算法的原理来自于自然界生物进化的过程。在自然条件下，种群中更适应环境的个体具有更大的可能性生存下去，并在种群繁衍中将自身基因遗传给下一代，而适用性较弱的个体则会在生物进化的过程中逐渐消亡。也就是说，较高适应性个体的基因会以更大的概率出现在后代的个体中，从而导致整个种群更加地适应于环境。

遗传算法需要首先需要初始化第一代的原始种群，种群中的每个个体都被编码成表示特定问题某种可行解的编码串。个体对于环境的适应度函数可以定义为问题的目标函数。具有较高适应度函数的个体更有可能在遗传的过程中交换它们的基因，这被称作选择、交叉和变异。选择和交叉操作产生的新的可行解，更趋近于目标函数的最优解。通常在交叉操作之后执行变异操作，用来产生整个搜索空间中新的可行解。经过上述步骤足够多的循环操作，最终的种群中会很有可能出现适应度更好的个体，其对应的可行解也趋近于问题的最优解。

基本的遗传算法可以分为以下几个部分：

编码(Encoding)：假设目标问题的可行解可以表示为一系列参数的集合。这些参数(称为基因)组合起来形成一个字符串值，称为染色体。一种通常的表示方式是使用二进制串。例如，如果目标问题是最大化包含三个变量的函数F(x,y,z)，可以使用10位二进制数来表示某一个变量的合适的取值范围，这样整个问题的可行解就可以表示为一个包含30位二进制数的染色体。

适应度函数(Fitness Function)：适应度函数需要设计为方便目标问题解答的形式。对于一个给定的染色体，适应度函数返回一个对应的适应度函数值，用来表示该染色体对应的个体对于环境的适应性。对于大多数函数优化问题，一种较为简单的方法就是使用原问题作为适应度函数。

选择(Selection)：当计算完当前种群中所有个体的适应度函数，这时需要进行选择操作。采用较高适应度函数值更有可能被选择的方式，从种群中随机选择出父代染色体。在整个选择操作过程中，高适应度的个体可能被选择多次，而低适应度的个体可能完全不会被选择。

交叉(Crossover)：通过选择操作得到的两个父代个体，它们的染色体需要被重新组合。交叉操作对两个父代个体染色体的某个随机位置进行截取，然后形成了两个头段和尾段。之后将两个染色体的尾段进行交换，从而产生新的子代个体。这种方式被称为单点交叉。并不是所有的个体都会进行交叉操作，一种可能的方式是交叉操作以某种概率进行。

变异(Mutation)：变异操作作用于经过交叉操作的子代个体上。变异操作会以较低的概率随机修改子代染色体的某个基因。

现阶段，三维空间内的多个信号源同时存在时，需要完成大量的计算才能找到三维空间内的多个信号源，现有的计算机资源很难完成上述巨大计算量，甚至可能因为有限的计算资源而导致问题根本无法解决。

发明内容

有鉴于此，本发明实施例的目的在于提供一种基于遗传算法的三维多目标定位方法，以通过现有的计算机资源求得三维空间内的多个信号源的位置。

为达到上述的目的，本发明采用的技术方案如下所述：

一种基于遗传算法的三维多目标定位方法，用于定位空间中的源节点，所述方法包括：

建立三维空间模型；

选取多个传感器节点，记录每一传感器节点在所述三维空间模型内的位置坐标；

获取所述多个传感器节点中每一所述传感器节点到源节点的估计单位方向向量；

根据每一所述传感器节点的位置坐标以及每一所述传感器节点到源节点的所述估计单位方向向量通过遗传算法计算得到源节点的坐标。

进一步地，每一所述传感器节点对应一平面天线阵列，所述获取所述三维空间内每一所述传感器节点到源节点的估计单位方向向量的步骤，包括：

通过信号频率估计算法计算每一所述传感器节点到源节点对应的估计向量与所述平面天线阵列之间的估计仰角与估计方位角；

通过所述估计仰角与估计方位角得到每一所述传感器节点到源节点的估计单位方向向量。

进一步地，所述通过所述估计仰角与估计方位角得到每一所述传感器节点到源节点的估计单位方向向量通过以下公式实现：

u_m,l＝[sinθ_m,lcosφ_m,l,sinθ_m,lsinφ_m,l,cosθ_m,l]^T，

其中u_m,l为单位方向向量，θ_m,l为仰角，为估计仰角，φ_m,l为方位角，为估计方位角，其中θ_N～N(0,1)，φ_N～N(0,1)，a表示常数因子。

进一步地，所述根据每一所述传感器节点的位置坐标以及每一所述传感器节点到源节点的所述估计单位方向向量通过遗传算法计算得到源节点的坐标的步骤，包括：

步骤S1，初始化原始种群，设定种群个体数目为S，交叉率为α，变异率为β，遗传算法最大迭代次数为T，在第一次循环过程中，固定参数K＝1，表示本次遗传算法是确定第1个源节点的位置坐标；

步骤S2，根据染色体编码方式随机产生N个个体，每个个体都满足x₁＝K，设置迭代计数器为t＝1；

步骤S3，计算每个个体的适应度函数，执行选择、交叉、变异操作，产生新的子代，迭代计数器t＝t+1；

步骤S4，重复步骤S3直到t＝T，在最终一代个体中，选取适应度最高的个体作为指向第K个源节点的M条射线的组合，过滤掉其中错误的射线，然后计算出第K个源节点的位置坐标；

步骤S5，循环进行步骤S2至步骤S4，在每次循环过程中，所有的个体都满足x₁＝K，其中K＝2,…,L，L为三维空间模型源节点的个数，经过所有的L次遗传算法迭代之后，计算得到L个源节点的坐标位置。

进一步地，所述步骤S1可通过以下方式实现：

定义M条射线的所有可能组合索引为一个长度为M的编码串，其对应的决策向量为

其中[x]_i＝x_i∈{1,…,L}，i＝1,…,M，L为三维空间模型源节点的个数，决策向量x的第i为表示在第i个传感器节点上选择的射线；

对于遗传算法的每次循环，设置x₁＝K，其中K＝1,…,L，表示在这次遗传算法的迭代过程中计算的目标是第K源节点的位置。

进一步地，步骤S3中的执行选择的步骤具体包括：

定义适应度函数

表示射线组合x中射线上任意一点和射线上任意一点之间的最短距离，定义为

‖·‖表示欧几里得范式，约束条件k_i≥0，k_j≥0，为两条射线上任意一点之间的最短距离；

遗传算法中一代共计S个射线组合个体x₁,x₂,…,x_S，则计算得到对应的适应度函数值为f₁,f₂,…,f_S；

定义每一个个体被选择的概率为则下一代备选的个体为

其中η为0到1中的一个随机生成数。

进一步地，步骤S3中的执行交叉的步骤采用以下模式进行：

其中x″_i和x″_j表示经过交叉操作生成的两个子代染色体，η表示从>

进一步地，步骤S3中的执行过滤的步骤可通过以下方式进行：

对遗传算法最终得到的射线组合x中的每条射线x_i，计算所述射线x_i到组合中其他所有射线间的距离之和，为

选择x中所有C(x_i)所低于平均值的射线。

进一步地，步骤S3中的执行变异的步骤可通过以下方式进行：

其中η表示从[2,M]中随机选择的一个整数，x_η和x′_η满足条件>η≠x′_η并且x_η,x′_η∈{1,…,L}。

进一步地，步骤S4中的计算源节点的位置坐标的步骤可通过以下方式实现：

三维空间模型内任意一点为q＝[x,y,z]^T，到射线的投影为则q到射线的距离为

其中i＝1,…,M′，M′(M′≤M)，对选取的所述多个传感器节点取相同的权重，则源节点位置的最小均方差估计为

其中I是单位矩阵，

[1,…,1]^T，长度为M′，以及

本发明实施例提供了一种基于遗传算法的三维多目标定位方法，涉及信号源定位领域。方法包括：建立三维空间模型；选取多个传感器节点，记录每一传感器节点在三维空间模型内的位置坐标；获取多个传感器节点中每一传感器节点到源节点的估计单位方向向量；根据每一传感器节点的位置坐标以及每一传感器节点到源节点的估计单位方向向量计算得到源节点的坐标。上述方法通过遗传算法对射线选择，在减少计算机的运算量的同时，可对空间内存在的多个信号源进行定位，低成本且准确率高。

为使本发明的上述目的、特征和优点能更明显易懂，下文特举较佳实施例，并配合所附附图，作详细说明如下。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本发明的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。

图1是本发明较佳实施例提供的一种三维空间模型图；

图2-图3是本发明实施例提供的基于遗传算法的三维多目标定位方法的流程图；

图4-图5是本发明提供的基于遗传算法的三维多目标定位方法对应的模拟仿真图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本发明实施例的组件可以以各种不同的配置来布置和设计。

因此，以下对在附图中提供的本发明的实施例的详细描述并非旨在限制要求保护的本发明的范围，而是仅仅表示本发明的选定实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。

请参阅图1，为本发明较佳实施例提供的一种三维空间模型图。

本实施例中，设定在三维空间模型中存在M个传感器节点，每个传感器节点都包含一个平面天线阵列。不失一般性，假设所有的平面阵列都平行于x-o-y平面。第m个传感器节点的位置为

p_m＝[x_m,y_m,z_m]^T，其中m＝1,…,M。

在三维空间模型中存在L个源节点，分别位于

q_l＝[x_l,y_l,z_l]^T，其中l＝1,…,L。

请参阅图2，为本发明实施例提供的基于遗传算法的三维多目标定位方法的流程图。

步骤S101，建立三维空间模型。

具体建模时，除建立图1所述的模型外，还可以设置其他三维空间模型，如多个传感器节点在三维空间内不同水平面，每一传感器节点对应一平面天线阵列不与x-o-y平面平行的三维空间模型。

步骤S102，选取多个传感器节点，记录每一传感器节点在所述三维空间模型内的位置坐标。

本实施例中，每一传感器节点设置有对应的位置，找到每个位置在三维空间模型中对应的位置坐标，所述位置可以通过传感器节点的定位装置确定，也可以在传感器节点安装时记录所述传感器节点的位置确定。

步骤S103，获取所述多个传感器节点中每一所述传感器节点到源节点的估计单位方向向量。

请参阅图3，为本发明实施例提供的基于遗传算法的三维多目标定位方法的流程图。

进一步地，所述步骤S103，包括步骤S1031和步骤S1032。

步骤S1031，通过信号频率估计算法计算每一所述传感器节点到源节点对应的估计向量与所述平面天线阵列之间的估计仰角与估计方位角。

本实施例中，从传感器节点p_m到源节点q_l的单位方向向量为u_m,l，其中从z轴正半轴开始的仰角θ_m,l∈[0,π]，以及从x轴正半轴开始的方位角φ_m,l∈[0,2π)。

步骤S1032，通过所述估计仰角与估计方位角得到每一所述传感器节点到源节点的估计单位方向向量。

本实施例中，单位方向向量u_m,l表示为

u_m,l＝[sinθ_m,lcosφ_m,l,sinθ_m,lsinφ_m,l,cosθ_m,l]^T

其中仰角θ_m,l的估计仰角为以及方位角φ_m,l的估计方位角为通过信号频率估计算法的MUSIC、ESPRIT等算法在每一传感器节点处得到估计仰角与估计方位角

定义

其中θ_N～N(0,1)，φ_N～N(0,1)，a表示常数因子。具体实施时其中a根据具体噪音设定。

根据u_m,l＝[sinθ_m,lcosφ_m,l,sinθ_m,lsinφ_m,l,cosθ_m,l]^T，通过测量数据可以计算出单位方向向量从而可以得到一条从p_m出发，方向为的DOA估计射线，表示为

对于空间中的M个传感器节点和L个源节点，总共可以得到ML条射线其中在所有的射线中，各有M条射线指向某个源节点，这些射线包含有源节点的位置信息

虽然在一般的噪声条件下，指向某个源节点的M条射线通常不会相交于一点，但互相之间会十分靠近源节点的位置，尤其是当信噪比十分高的情况下。通过这种方法可以从所有的射线中分理出每个指向某个源节点的M条射线的组合。

为了找出指向某个源节点的M条射线的组合，需要从每个传感器节点中得带的L条射线中选出一条，则共有L种可能的组合方式。这一般需要巨大的计算量甚至可能因为有限的计算资源而导致问题根本无法解决。因此，我们提出了一种基于遗传算法的方法来解决这个问题。

步骤S104，根据每一所述传感器节点的位置坐标以及每一所述传感器节点到源节点的所述估计单位方向向量通过遗传算法计算得到源节点的坐标。

本实施例中，所述步骤S104具体包括步骤如下：

步骤S1，初始化原始种群，设定种群个体数目为S，交叉率为α，变异率为β，遗传算法最大迭代次数为T，在第一次循环过程中，固定参数K＝1，表示本次遗传算法是确定第1个源节点的位置坐标。

本实施例中，定义M条射线的所有可能组合索引为一个长度为M 的编码串，其对应的决策向量为

其中[x]_i＝x_i∈{1,…,L}，i＝1,…,M，L为三维空间模型源节点的个数，决策向量x的第i为表示在第i个传感器节点上选择的射线；

对于遗传算法的每次循环，设置x₁＝K，其中K＝1,…,L，表示在这次遗传算法的迭代过程中计算的目标是第K源节点的位置。

步骤S2，根据染色体编码方式随机产生N个个体，每个个体都满足x₁＝K，设置迭代计数器为t＝1。

步骤S3，计算每个个体的适应度函数，执行选择、交叉、变异操作，产生新的子代，迭代计数器t＝t+1。

本实施例中，执行选择的步骤具体包括：

定义适应度函数

函数表示射线组合x中射线上任意一点和射线上任意一点之间的最短距离，定义为

在上式中，‖·‖表示欧几里得范式，约束条件k_i≥0，k_j≥0，为两条射线上任意一点之间的最短距离。若去掉该约束，则就为传统意义上的两条直线之间的距离。

遗传算法中一代共计S个射线组合个体x₁,x₂,…,x_S，则计算得到对应的适应度函数值为f₁,f₂,…,f_S；

定义每一个个体被选择的概率为则下一代备选的个体为

其中η为0到1中的一个随机生成数。

进一步地，两个被选择的父代个体x′_i和x′_j有可能不发生改变，也有可能以一定的概率发生交叉，从而形成新的子串执行交叉的步骤采用以下模式进行：

其中x″_i和x″_j表示经过交叉操作生成的两个子代染色体，η表示从>

进一步地，某个子代染色体以某种概率随机发送改变，例如

其中η表示从[2,M]中随机选择的一个整数，x_η和x′_η满足条件>η≠x′_η并且x_η,x′η∈{1,…,L}。

步骤S4，重复步骤S3直到t＝T，在最终一代个体中，选取适应度最高的个体作为指向第K个源节点的M条射线的组合，过滤掉其中错误的射线，然后计算出第K个源节点的位置坐标。

本实施例中，选取适应度最高的个体作为指向第K个源节点的M 条射线的组合，记作

根据射线组合x^opt，指向第K个源节点的M条射线分别为其中i＝1,…,M。过滤掉其中错误的射线，然后可以计算出第K个源节点的位置坐标。

由于遗传算法的最终结果中并不一定的最优解，而又可能是近似解。为了通过近似最优的射线组合计算出源节点的位置坐标，需要去掉射线组合x中错误的射线x_i。

进一步地，执行过滤的步骤可通过以下方式进行：

对遗传算法最终得到的射线组合x中的每条射线x_i，计算所述射线x_i到组合中其他所有射线间的距离之和，为

选择x中所有C(x_i)低于平均值的射线作为最终的源节点定位依据。需要注意的是，选择x中所有C(x_i)所低于平均值的射线数目至少为三个。

本实施例中，步骤S4中的计算出第K个源节点的位置坐标的步骤可通过以下方式实现：

经过遗传算法迭代步骤之后，可以得到指向第[x^opt]_i个源节点的>

对于三维空间模型内任意一点为q＝[x,y,z]^T，到射线的投影为则q到射线的距离为

其中i＝1,…,M′，M′(M′≤M)，对选取的所述多个传感器节点取相同的权重，则源节点位置的最小均方差估计为

其中I是单位矩阵，

[1,…,1]^T，长度为M′，以及

请参阅图4-图5，本发明提供的基于遗传算法的三维多目标定位方法对应的模拟仿真图。

本实施例中，定义第l个源节点的绝对定位误差为其中l＝1,…,L。

定义的绝对均方根误差为

其中N表示蒙特卡洛仿真次数。

定义第l个源节点的相对定位误差为

平均相对误差为

则算法的整体绝对定位误差为

算法的整体相对定位误差为

设定在100×100×100的三维空间中，共有M＝4个传感器节点，分别位于p₁＝[14,62,69]^T，p₂＝[18,40,29]^T，p₃＝[68,10,82]^T，>4＝[41,18,28]^T，p₅＝[34，0，37]^T，p₆＝[37,57，5]^T，p₇＝[15，8，42]^T，>8＝[88，5，3]^T，p₉＝[22，45，7]^T，p₁₀＝[31,35,15]^T。共有L＝8个源节点，分别位于q₁＝[57,39，15]^T，q₂＝[20,54,50]^T，q₃＝[52,83,58]^T，>4＝[44,95,41]^T，q₅＝[54，5，9]^T，q₆＝[28,95,95]^T，q₇＝[8，45，65]^T，>8＝[66,77,90]^T。

初始化遗传算法种群个体数目S＝100，交叉率为α＝0.8，变异率为β＝0.1，遗传算法最大迭代次数为T＝50，模特卡罗仿真次数 N＝100。

则得到图4，为整体相对误差和常数因子a之间的关系。

则得到图5，为整体绝对误差和常数因子a之间的关系。

综上所述，本发明提供了一种基于遗传算法的三维多目标定位方法，方法包括：建立三维空间模型；选取多个传感器节点，记录每一传感器节点在三维空间模型内的位置坐标；获取多个传感器节点中每一传感器节点到源节点的估计单位方向向量；根据每一传感器节点的位置坐标以及每一传感器节点到源节点的估计单位方向向量计算得到源节点的坐标。上述方法通过遗传算法对射线选择，在减少计算机的运算量的同时，可对空间内存在的多个信号源进行定位，低成本且准确率高。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。