李为为 魏世辉

(阜阳职业技术学院， 安徽 阜阳 236000)

船舶在航行过程中可能遇到雨、雪、大风等天气。单从航道选择方面而言，要最大程度地保证船舶航行的快捷性和安全性，就需要电子航道系统能够在最短的时间内找到可供船舶选择的最优路径。另外，布置在航道周围的传感器节点也很难补充电源。因此，低功耗、数据准确率高的窄带物联网技术即成为数字航道的必然选择。将窄带物联网技术与蚁群算法相结合，可以实现对航船位置进行快速、准确的定位。假定航船要经过的路线的坐标是确定的，而其从A地到达B地可以有多种路径，那么上述问题就可以转化为最短路径问题。

求解最短路径，在算法设计上将考虑以下几个方面的问题：(1) 已知且仅知起点的坐标；(2) 已知且仅知终点的坐标；(3) 已知起点和终点的坐标；(4) 对整个航道区域求最短路径。如果要解决的是无向图问题，已知起点和已知终点时的解决方案是一样的。如果针对的是有向图的问题，已知终点和已知起点的解决办法正好是两个相反的过程。

一般用来解决以上问题的算法有遗传算法、A*算法、Floyd-Warshall算法、Dijkstra算法等[1]。蚁群算法[2]是一种用来寻找优化路径的概率型算法，它模拟了蚂蚁在寻找食物过程中发现路径的行为。蚁群算法在旅行商问题(Travelling salesman problem)上的应用已经取得了比较好的成效。目前，蚁群算法在图的着色、车辆调度、集成电路设计、通讯网络、数据聚类分析等方面都有所应用。本次研究主要运用蚁群算法来解决数字航道的最优路径选择问题。

1 算法模型

将窄带物联网技术与蚁群算法相结合，用以解决数字航道中的路径选择问题。针对数字航道的特点[3]，建立图1所示的基于窄带物联网技术的蚁群算法模型。

根据蚁群算法进行最优路径选择。假设算法涉及的定位不受外界影响，在比较优化的环境中进行。通过传感器节点对目标节点及经过节点的位置信息进行采集，根据采集的到达目标位置所经过的节点位置信息，采用蚁群算法对路径进行选择。同时，通过对比不同的算法结果，找到更适合的算法，以期达到更优的结果。在图1中，没有采用蚁群算法时，当选择目标区域后，航道中的目标航行路线是随机选择的；采用蚁群算法后，可根据计算结果选择一条最优路径，这样就可以加快航船的航行，减少人力、物力的消耗。

图1 基于窄带物联网技术的蚁群算法模型

2 算法流程及算法原理

2.1 算法流程

假设在数字航道周围的节点能够对数字航道区域全覆盖，每个节点都处于工作状态。算法的具体步骤如下(流程见图2)：

(1) 初始化信息素常数、信息素挥发因子、启发函数因子等参数，将数据读入程序，进行预处理(如将城市的坐标信息转换为城市间的距离矩阵)。

图2 算法流程

(2) 蚂蚁随机部署在航道将要经过的区域。计算每个蚂蚁下一个访问地址，直到计算访问完所有的地址区域。

(3) 对每个蚂蚁到达区域所走的路径长度(Lk)进行计算，对当前的迭代次数的最优解进行记录，同时更新信息浓度。

(4) 判断是否达到最大迭代次数。若未达到最大迭代次数，则返回步骤(2)；若已经达到最大迭代次数，则结束程序。

(5) 输出结果，并根据需要输出寻优过程中的相关指标(如运行时间、收敛迭代次数等)。

2.2 算法原理

蚁群算法的基本原理：(1) 在路径上释放信息素。(2) 在寻找下一条路径时，发现还有未经过的路口，则通过随机算法选择任意一条路径；与此同时，释放与路径长度有关的信息素。(3) 已知路径长度与信息度的浓度是反比关系。寻找下一条路径时，碰到已经选择过的路口，则以信息度较高的路径作为下一条路径的选择标准。(4) 在不断选择路径的过程中，将信息度浓度相对最大的路径作为最优路径。(5) 最终找到最优“寻食”路径[4]。

2.3 算法参数及符号

蚂蚁数量[5]：m=50。

重要程度参数：信息素，Alpha=1；启发因子，Beta=5。

蒸发系数：信息素，Rho=0.1。

最大迭代次数：Ncmax=200。

信息素增加强度系数：Q=100。

各代最佳路线：R_best。

各代最佳路线的长度：L_best。

3 仿真实验结果

3.1 目标函数最短路径值仿真

从图3可以看出，迭代次数在0～60之间时，随着迭代次数的增加，目标函数的适应度是降低的；迭代次数大于60以后，目标函数的适应度基本趋于稳定。最后得出的目标函数最短路径值为1.5602×104。

图3 适应度进化曲线

为了进一步说明问题，通过仿真实验对比了不同迭代次数目标函数的平均距离和最短距离。从仿真实验的结果(见图4)来看，算法仿真得到的最短距离远小于平均距离，实现了理论上的距离最优。

4 结 语

图4 平均距离和最短距离

本次研究，针对数字航道系统的功能需求，根据蚁群算法和窄带物联网技术的特点，提出了将窄带物联网技术与蚁群算法相结合的一种最优路径选择算法。从算法仿真结果看，迭代次数大于60以后，目标函数的适应度基本趋于稳定；比较目标函数的平均距离和最短路径，得到的最短距离远小于平均距离，说明运用该算法可以实现路径最优选择。