基于蚁群算法的传感器充电路线规划——考虑有无障碍物影响

Charging Route Planning for Sensors Based on Ant Colony Algorithm—Consider the Presence or Absence of Obstacles

摘要: 随着物联网的快速发展，无线可充电传感器网络(WRSN)在环境、设备监测等技术应用方面越来越广泛。本文针对移动充电器寻找充电路线最优问题，建立基于蚁周系统的蚁群算法模型，将无障碍的最优路径问题转化为经典旅行商问题。其中，为合理考虑通行道路实际分布情况，加入实际障碍物对道路通行能力的影响，利用蚁群算法寻找各节点间的避障路径组成距离矩阵后，采用最近插入法求解全局最优路径。

Abstract: With the rapid development of Internet of Things, wireless rechargeable sensor network (WRSN) has been widely applied in environmental, device monitoring and other technologies. In this paper, an ant colony algorithm model based on ant week system is established to find the optimal charging route for mobile chargers, and the barrier-free optimal path problem is transformed into the classic travel agent problem. Among them, in order to reasonably consider the actual distribution of the passage road and add the influence of actual obstacles on the road capacity, ant colony algorithm is used to find the obstacle avoidance paths between each node to form the distance matrix, and the nearest insertion method is adopted to solve the global optimal path.

1. 引言

随着物联网的快速发展，无线可充电传感器网络(WRSN)在环境监测及设备监测等技术应用方面越来越广泛，人们对其性能需求越来越高，规划合理的充电路线对WRSN正常工作意义重大 [1]。无线可充电传感器网络包括一个数据中心，若干传感器及一个或多个移动充电器三个部分 [2]。在整个系统中，传感器从环境中收集信息后传递给数据中心，各传感器之间、数据中心与传感器之间均可以互相传递信息，移动充电器需要给传感器定期充电，保证WSN能够正常且持续工作。移动充电器以一定速度从数据中心出发，在每个传感器处停留一段时间，并按固定充电速率给传感器充电，每个传感器又以特定的能耗速率工作，因此需要规划出移动充电器的最优充电路径减小路上的耗能，且满足传感器能量需求。针对目前国内外一些较多应用的路线规划方法，如遗传算法，模拟退火算法，粒子群算法等 [3] [4] [5]，广泛应用在机器人作业路径规划方面 [6] [7] [8]，但在解决复杂场景路线时效率较低。

蚁群算法由于其稳定性强、并行能力高等特点，解决了一般路线算法在复杂场景最优路线寻找效率低的问题。而针对实际建筑物的影响情况，避障部分仍可采用蚁群算法寻找节点间的避障路径，具有较强的适用性，针对节点路径考虑更具体，适用于完成寻找该区域全部节点最佳的充电路线任务。

2. 节点数据分析与处理

常见的地图使用了不同的坐标系，导致同一个地址的经纬度在地图上显示有偏差，因此需要对不同地图中的经纬度坐标进行转化。针对某省研发中心给出的各传感器经度坐标与纬度坐标(见表1)，使用WGS84坐标系(国际通用)进行坐标系转化，得到传感器分布情况图(图1)。

Table 1. Sensor longitude and latitude coordinates table

表1. 传感器经度坐标与纬度坐标表

Figure 1. Sensor distribution diagram

图1. 传感器分布情况图

由图1发现原坐标系在GCJ02坐标的传感器多分布于海面上，有五个点在陆地上，将位于海面上各传感器间的可行路径视为无障碍路径，忽略传感器在海面上的偏移，暂将海面上传感器视为移动充电小车为其充电。进一步求出各个节点间的距离，部分节点间距离矩阵见表2。

Table 2. Partial node distance matrix table

表2. 部分节点间距离矩阵表

3. 模型的建立与求解

3.1. 模型的建立

移动充电器从数据中心出发，经过每个传感器一次再返回数据中心的最短路径问题，即经典旅行商问题。首先将表1中所给经纬度从数据中心开始按照顺序依次进行编号，数据中心设为0，传感器依次设为 $1,2,\cdots ,29$。设第k条路径是从节点i到节点j，距离记为。k = 1时表示数据中心到第一个传感器间的距离，k = 30时表示最后一个传感器到数据中心的距离，所以本问题就是求得一条环路，移动充电器从数据中心出发经过29个传感器的路径总距离可以建立如下数学模型：

$D=\min {\displaystyle {\sum }_{k=1}^{30}{d}_k}\left(i,j\right),$ (1)

$\text{s}\text{.t}\text{.}{d}_k\left(i,j\right)\ge 0\left(i,j\right)\in \left(0,1,\cdots ,29\right)$ (2)

对于经典旅行商问题我们采用蚁群算法求解。关于蚁群算法有三种不同模型包括蚁周系统、蚁量系统和蚁密系统。在蚁密和蚁量系统，蚂蚁释放信息素是根据局部情况，蚁周系统中蚂蚁释放信息素依靠的是整体反馈情况，本文是为了寻找一个全局的最短路径，因此采用的是蚁周系统。

蚁群算法在初始迭代时给每条路径上的浓度是一个常数，那时蚂蚁不知道每条路径的长度，它只能随机选择，产生了大量无关紧要的路径，阻碍最优路径搜索过程，同时对信息素浓度局部更新也会产生影响。但在求最短路径时，节点与节点之间的距离是已知的，因此在用蚁群算法求最短路径时，没有必要进行盲目选择，可以对迭代开始时的初始浓度进行精确赋值。

对于蚁群算法的工作原理(图2)。

初始化信息素因子α，启发函数因子β，路径启发因子 ${\eta }_{ij}$， ${\eta }_{ij}=\frac{1}{d_{ij}}$。其中， $d_{ij}$ 为i到j的欧氏距离； $q_0$ 为蚂蚁状态转移的阈值。设最大迭代次数N，选定蚂蚁数为m。计算节点距离矩阵，定义节点i和节点j之间路径上的初始信息素浓度为 ${\tau }_{ij}$，将m只蚂蚁放在起点0处，将各蚂蚁的初始节点0置于当前解集中，第k只蚂蚁从节点i转移到下一个节点j的概率：

$P_{ij}^k\left(t\right)=\{\begin{array}{ll}\frac{{\tau }_{ij}^{\alpha }\left(t\right){\eta }_{ij}^{\beta }\left(t\right)}{{{\displaystyle \sum }}_{s\in allowe{d}_k^i}{\tau }_{is}^{\alpha }\left(t\right){\eta }_{is}^{\beta }\left(t\right)}\hfill & j\in allowe{d}_k^i\hfill \\ 0\hfill & j\notin allowe{d}_k^i\hfill \end{array}$ (3)

其中， $allowe{d}_k^i=\left\{与i相连的节点\right\}-\left\{蚂蚁k已经访问过的节点\right\}$，即每只蚂蚁对每个节点最多访问一次。

在蚂蚁完成一次搜索后，信息素一方面要挥发掉一部分，另一方面蚂蚁在走过的路径上要释放一定量的信息素。设挥发和增加信息素的系数均为ρ，更新规则如下：

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+\rho \Delta {\tau }_{ij}\left(t\right)$ (4)

$\Delta {\tau }_{ij}\left(t\right)={\displaystyle {\sum }_{k=1}^m\Delta {\tau }_{ij}^k\left(t\right)}$ (5)

其中 $\Delta {\tau }_{ij}^k\left(t\right)$ 是本次循环中蚂蚁k的信息素增加量，若蚂蚁没有经过此路径，则 $\Delta {\tau }_{ij}^k\left(t\right)=0$，否则，用Q表示增加浓度的总和，可视为一个常数，用 $L_k$ 为第k只蚂蚁在本次循环搜索中搜索到的路径长度，则定义 $\Delta {\tau }_{ij}^k\left(t\right)=\frac{Q}{L}$。

重复以上工作，直到所有蚂蚁都到达终点，得到m条路径集合 $\left\{l_1,l_2,\cdots ,l_m\right\}$。比较m条路径的长度有 $\left\{l_1<l_2<\cdots <l_m\right\}$，记最优解为 $L_{location}$，平均解为 $\bar{L}$，当前迭代最短路径为 $L_{\min }$，对此路径上的信息素浓度进行全局更新：

${\tau }_{ij}\left(t+1\right)={\tau }_{ij}\left(t\right)+\sigma \mu \Delta {\tau }_{ij}$ (6)

$\sigma =\frac{1}{2}\tanh \left(\frac{L_{location}-L_{\min }}{\bar{L}-L_{\min }}\right)+\frac{1}{2}$ (7)

Figure 2. Flow chart of ant colony algorithm for ant cycle system

图2. 蚁周系统的蚁群算法流程图

3.2. 模型的求解

3.2.1. 无障碍情况

借助软件python，求解蚁群算法下路线规划的最优解，运行结果的路径图与收敛图见图3、图4。

Figure 3. The ant colony algorithm runs the result path graph

图3. 蚁群算法运行结果路径图

Figure 4. Convergence graph of ant colony algorithm running results

图4. 蚁群算法运行结果收敛图

最终求得最短路径为：0-2-1-9-8-12-10-13-16-27-15-14-11-6-7-18-25-26-29-19-20-17-21-23-24-28-22-4-3-5-0。

最短距离为：11.5819498643260 KM。

通过迭代后的最短距离与平均距离收敛图，对比可以发现在迭代次数达到大概40次后最短距离趋于稳定状态，当迭代次数大概在430次之后的平均距离波动较小，说明蚁群算法稳定性较好。

3.2.2. 有障碍情况

生活中对移动充电器充电路线有影响的因素有很多，如天气因素、交通因素和路况因素等等，相对于无障碍情况下影响最大的就是路况因素，而路况因素中最为突出的就是建筑物。各节点之间如果存在大量建筑物则移动充电器只能不断绕行，这大大增加了路上的能量消耗，所以在有大量建筑物的情况下寻找最短移动距离是减少路上能耗的最为关键的问题。在前面建立的自适应蚁群算法的基础上，结合可视图法与插入法对此类问题进行求解 [9]。

考虑实际路况中城市建筑对道路通行的影响，现将位于陆地建筑中的节点25、18、26、29加入实际路况即障碍物的影响下进行研究。由于节点15、12、17位于沿海广场，周围无较大建筑物障碍影响通行，其余节点均位于海面上，故将这些节点作为无障碍点处理。增加障碍物影响后，重新得到各节点之间的最短距离，如传感器25与传感器18之间，由于陆地建筑影响无法直接采用两点之间连线长度作为最短距离。在水经注万能地图下载器中找到建筑物经纬度坐标，运用蚁群算法画出障碍物的平面图(图5)。

Figure 5. Plan of land building

图5. 陆地建筑物平面图

增加障碍物影响后，如果将所有的点带入实际路况中进行实际考察，绘制最短路径图，针对障碍物较多的情况无法快速找出全局最优路径，为节约时间将问题分开来看：机器可以并行计算出各个节点在实际路况中的两两节点间最短距离，重新获得各节点之间的最短距离作为实际路况的距离矩阵D，利用距离矩阵D求解移动充电器访问每一个传感器一次并回到数据中心的最短回路，这样将问题就转化为组合优化中的一个NP完全问题。

利用距离矩阵D求解移动充电器访问每一个传感器一次并回到数据中心的最短回路，在求解方法的选择上，如果使用精确解，例如枚举法来解决该题，本题涉及到30个点的路线求解，依靠现有计算机很难在短时间实现。因此由于使用精确解算法求解问题的规模十分有限，实际情况中往往使用近似解法，考虑到插入算法求解质量高的优点，选择最近插入法作为最短路径的求解方法，为增加解的质量，进行1000次计算后得到最优路径图(图6)。

Figure 6. Plan of land building

图6. 陆地建筑物平面图

最短距离为：12.5374902553823 KM

最优路线为：0-1-2-12 -8-9-7-6-11-14-15-27-16-13-10-5-3-4-22-28-24-23-21-29-19-26-25-18-20-17-0。

由上面有建筑物影响得到的最优路径图可以看出，虽然只有18、25、26、19、29这五个点附近有障碍物，但是与之相邻点的路径会间接受到影响。

4. 结论

我们选用国际通用的坐标系进行节点分布研究，考虑了两种不同的情况的路径建模，分别是有障碍和无障碍的，排除了单一性，片面性对模型的影响，使模型的可利用率更高，实用性更高，更加贴近生活。蚁群算法由于其稳定性强、并行能力高等特点，解决了一般路线算法在复杂场景最优路线寻找效率低的问题，对无关路径起到抑制作用，避免蚂蚁的盲目搜索，提高了搜索全局最优解的速率，适用于完成寻找该区域全部节点最佳的充电路线任务。而且加入实际建筑物的影响后，避障部分仍可采用蚁周系统的蚁群算法模型寻找节点间的避障路径，模型具有较强的适用性，在有限的时间和资源上，我们的模型针对节点路径考虑更具体，可广泛使用在各类海陆路线一般选择工作中。

基金项目

本文获得国家自然科学基金项目(71961003)资助。