一种辅助定位信标节点的移动路径规划方法

摘要

一种辅助定位信标节点的移动路径规划方法，包括如下步骤：1)程序初始化；2)计算全覆盖监控区域的六边形网格列个数和行个数，对所有六边形网格的中心和顶点进行编码，获得相关矩阵向量；3)建立优化模型；4)计算每一个网格中心和网格顶点的可选下一个停留位置集合；5)初始化蚂蚁的初始位置和已选路径；6)蚂蚁建立新的下一个停留位置集合；7)判断已选路径是否全覆盖监控区域内所有网格，如果是则记录当前选择路径和其长度；判断是否所有蚂蚁寻找到路径，如果是则跳到步骤8)；8)计算所有蚂蚁寻找的路径长度，更新所有位置的信息素。本发明提供了一种可降低信标节点的移动路径长度和停留位置个数的辅助定位信标节点的移动路径规划方法。

主权项

一种辅助定位信标节点的移动路径规划方法，其特征在于：所述移动路径规划方法包括如下步骤：1)程序初始化：初始化算法中当前蚂蚁k、迭代次数初值m₁、信息素挥发因子ρ、信息素释放总量Q、大迭代次数M₁和蚂蚁个数K，根据无线传感网应用项目，初始化监控区域边长、节点通信半径和六边形网格高度；2)根据监控区域边长和六边形网格高度，计算全覆盖监控区域的六边形网格列个数和行个数；对所有六边形网格的中心和顶点分别采用从左到右，从下到上的原则进行编码，并计算六边形网格中心和顶点的位置坐标，获得相关矩阵向量；3)根据信标节点的移动路径约束和节点定位约束，建立优化模型(1)，让信标节点的移动距离最短且保证所有传感节点都能获知自身的位置坐标；min(N_l)    (1)$s.t.L=\{l_1,l_2,..,l_{N_t}\}---(1.a)$l_g+1∈N_g,g＝1,2,...,N_l‑1    (1.b)${\lambda }_{l_g,l_{g+1},l_{g+2}}=0,g=1,2,...,N_l-2---\left(1.d\right)$$s_{ij}\ge 3,\forall i,j---\left(1.e\right)$其中，N_l表示信标节点经过的停留位置个数；表示信标节点的移动路径，即经过的停留位置集合，集合L中每一个元素表示信标节点的停留位置，是一个1×3的向量[k₁ k₂ k₃]，向量的第一个元素k₁表示停留位置的列数，第二个元素k₂表示停留位置的行数，第三个元素k₃表示停留位置的类型，取值0,1，如果k₃＝0，则表示该元素是六边形网格中心，否则表示该元素是六边形网格的顶点；N_g表示停留位置l_g的可选下一个停留位置集合；表示三个停留位置l_g,l_g+1,l_g+2是否共线的标识符，取值为1表示共线，为0表示不共线；s_ij表示网格Grid(i,j)被不同位置上的信标节点覆盖的次数；优化模型(1)中，有移动路径约束(式(1.a‑1.d))和节点定位约束(式(1.e))，其中，式(1.a)表示信标节点移动经过的最优路径，由六边形网格的顶点和中心组成；式(1.b)表示当信标节点在位置l_g停留时，只从位置集合N_g中选择下一个停留位置，当停留位置为网格中心时，可选下一个停留位置集合N_g为其中，l(i,j)表示六边形网格Grid(i,j)的中心，Ding(i,j)表示从左开始计数的第i列中从下到上开始计数的第j个顶点，m表示监控区域内第一列网格的个数，n表示监控区域内网格的列数且是奇数，当停留位置为顶点时，可选下一个停留位置集合为式(1.c)表示信标节点不在同一个位置停留二次以上，则路径L中不存在相同的停留位置；由于传感节点需要3个以上且不能共线的信标节点位置信息，因此，式(1.d)表示路径L中任意3个相邻停留位置不在同一条直线上；式(1.e)表示每一个网格至少被3个以上不同停留位置覆盖；当停留位置为网格中心时，该网格和周围邻居网格的s_ij加1，当停留位置为网格顶点时，具有该顶点的网格s_ij加1；4)根据式(2)和式(3)，计算每一个网格中心和网格顶点的可选下一个停留位置集合；5)初始化蚂蚁k的初始位置和已选路径L_y；6)蚂蚁k分析下一个停留位置集合中所有位置元素，如果当前路径L_y添加了位置元素后，不符合约束条件(1.a)‑(1.d)，则删除该位置元素，最终建立新的下一个停留位置集合；如果该新的下一个停留位置集合为空集，则进入“死胡同”，跳到步骤5)，在初始位置重新寻找路径，否则计算选择下一个停留位置，将该停留位置添加到已选路径L_y中；7)判断已选路径L_y是否全覆盖监控区域内所有网格；如果L_y未全覆盖监控区域内所有网格，跳到步骤6)，继续寻找，否则记录当前选择路径和其长度；如果k＜K，则还有蚂蚁未寻找到路径，k＝k+1，下一个蚂蚁开始寻找路径，跳到步骤5)，否则跳到步骤8)；8)计算所有蚂蚁寻找的路径长度，选择长度最短路径作为第m₁轮的最优路径，并记录该最优路径和长度Len(m₁)；如果Len(m₁)≥LenBest，挥发所有位置的信息素，否则LenBest＝Len(m₁)，其中LenBest表示迭代过程中，出现的最优移动路径长度，增加该路径上的停留位置信息素且挥发所有位置的信息素，通过计算更新所有位置的信息素；如果m₁＜M₁，则k＝1，m₁＝m₁+1，跳到步骤5)，否则结束算法，输出最优移动路径。