基于雾计算的路网- 野区路径规划研究

王 砾，岳东峰，刘严岩，毕竹清

（北方信息控制研究院集团有限公司，南京 211153）

0 引言

随着智能设备的普及、可穿戴计算设备的发展，网络发展呈现出两种明显的趋势：基于云计算的架构普及以及持续激增的移动智能设备。智能设备的小型化、轻量化与高性能之间存在一定的矛盾，为了解决这类矛盾，云计算框架的快速发展，已经成为现在互联网的关键基础设施之一。并且随着智能手表、智能眼镜的逐步普及，移动智能设备的需求会进一步激增，对云计算的负载能力、实时响应能力和安全保密能力提出了更高的要求［1-2］。为了应对该类挑战，雾计算技术近些年发展较为迅猛，雾计算是分布式部署于网络边缘的小型云计算系统，能够对逻辑上邻近的移动设备提供有效的云服务，同时降低了大型云端的负载压力，雾计算结合了移动互联网与云计算技术，同时具有网络拓扑的弹性缩放能力与云平台的分布计算能力。能够根据用户需求的变化，实时调整网络节点的接入策略，通过虚拟化技术，整合不同硬件平台的计算、存储等资源，合理分配网络资源。

路径规划技术是目前日常生活中较为普及的技术之一，除了能够提供快速、实时的路径规划功能以外，现有移动端应用程序已经能够提供较为全面的地理信息服务，包括周围商业设施的搜索、拥堵区域提示等信息。现有路径规划技术的核心分为两部分：第1 部分是对地图的处理，将矢量地图进行预处理，形成可用于路径规划拓扑图；第2 部分是路径寻优算法，根据起始点、关键点、终止点的信息，规划出合理的路线。根据获取的地图信息范围，可以将路径规划方法分为：基于先验全地图信息的全局路径规划，以及基于实时地图信息的局部路径规划。局部路径规划算法有人工势场法、遗传类算法等。全局路径规划常见的路径寻优算法有：适用于栅格路径寻优的Dijkstra 算法［3-4］、A*算法［5-6］与适用于可视图的Voronoi 图法［7］等。

本文提出了基于雾计算框架的野区路径规划服务设计方法。在雾计算平台提供的计算、存储等资源的基础上，综合考虑野区的地质信息、水域信息、建筑群信息、道路信息以及高程信息等，结合雾计算平台收集的实时信息，包括桥梁被毁、道路堵塞等，并以栅格类算法中的A*算法作为野区环境下的路径寻优方法，构建适用于野区的路径规划服务，提出实时的道路-野地无缝连接的路径规划方法。

1 云计算与雾计算介绍

1.1 云计算介绍

军用增强现实电子沙盘以高精度三维地形数据为基础。现在较为广泛接受的云计算定义是美国国家标准与技术研究院（NIST）提出的，定位为：云计算是一种按使用量付费的模式，这种模式提供可用、便捷、按需的网络访问，提供可配置的计算资源共享池（资源包括网络、服务器、存储设备、应用软件、服务等），这些资源能够被快速提供、只需要很少的管理工作，或与服务供应商进行很少的交互［8］。

云计算的定义中，强调了云计算是根据用户的需求提供计算服务，能够聚合网络带宽、数据储存、应用服务等资源，对外提供整合后的虚拟化资源池，并且该资源池能够根据应用场景的需求进行配置，即提供资源的弹性扩展能力。同时采用统一的网络访问方式，提供标准的、与平台无关的服务访问接口，屏蔽了“云”内部结构的差异。

1.2 雾计算介绍

雾计算是云计算的延伸概念，能够将云服务扩展至网络边缘。雾计算是地理上分布式计算架构，由大量泛在的、相互连接的、异构的设备共同组成资源池。雾计算与云计算可以相互协作，但不依赖云计算，为用户群提供弹性的计算、存储、通信与服务等资源［9-10］。

雾计算的特点［11］包括：1）雾计算与网络边缘的用户组距离较近，从而在网络边缘提供对时延敏感的服务；2）雾计算提供区域感知能力，在地理上分布的各个雾节点（网络边缘的服务器）能够推断出自身的位置，并跟踪用户组的运动状态，从而提供更加切合当前环境的计算服务；3）在大数据的时代，雾计算可以支持边缘分析与流数据挖掘，在数据收集的早期阶段对数据进行降维，从而降低数据延迟与节省带宽消耗。

1.3 云计算与雾计算的关系

雾计算与云计算是相辅相成的关系，雾计算是云计算在网络边缘的延伸，更加贴近各类移动终端，雾计算与云计算的关系如图1 所示。

图1 雾计算与云计算的关系图

通过云计算，聚合各类服务器群的计算能力、存储能力以及相应的网络资源，并将各类资源虚拟化后形成资源池，对各类服务的运行提供基础支撑。雾计算通过整合不同雾节点的资源，形成局部的资源池，并对所属的各类用户群提供服务支撑。云计算可以为雾计算提供更多的计算能力、存储能力以及更多的服务类型。对于用户而言，无需知道服务所处的实际位置，只需要采用统一的访问接口，即可向“雾”/“云”请求服务。

2 雾计算平台上的野区路径规划应用场景分析

2.1 野区路径规划功能介绍

野区路径服务能够结合具体的道路信息、河流信息、湖泊信息、居民区信息等，自动识别出可通行的野地范围，并在路径规划过程中，无缝衔接道路，在有道路的情况下，优先选择道路，在道路绕远或无道路情况下，生成合适的野地路径规划方案。

野区路径规划分为预处理模块与路径规划模块两部分，预处理模块是将矢量类型的地图信息栅格化，提取每个栅格中的地理信息并保持至相应的矩阵中，并分析栅格本身的属性，包括是否可通行、是否代表河流等信息以及栅格与栅格之间的关系，包括下一个栅格是否某障碍区域的边界等。执行预处理模块的耗时长、内存占用大、计算结果占用磁盘空间多。路径规划模块是在预处理模块的基础上，根据预处理生成的结果，采用合适的寻路方法，如A*算法、蚁群算法等方式，选择合适的路线。

2.2 野区路径规划应用场景分析

根据上节介绍的野区路径规划模块描述，野区路径规划在“雾”计算平台上的应用场景如图2所示。

图2 野区路径规划应用场景

根据云平台提供的计算以及存储能力，针对大范围、多类型车辆进行预处理操作，提取出基础的地理信息，包括道路、河流、湖泊、草地等信息，并根据不同型号车辆的通行能力，包括野地通行速度、涉水深等，结合矢量地图与车辆通行参数，生成栅格数据，栅格数据中每个栅格点保存了该点及其周围区域的地理信息，如该栅格区域内是否为道路、河流或者湖泊，以及该类型车辆是否可以通过该栅格等。将不同区域、不同车辆的栅格信息持久化保存在云端存储器中，当某雾平台需要对外提供野区路径规划能力时，从云端将指定区域的栅格数据信息下载到特定的雾平台中，雾平台采集各个车辆、平板电脑等设备的实时状态信息，结合具体的用户需求与“云”端预处理结果，进行实时的路径推送功能。雾平台可将搜集的地理变化信息，整理后反馈至“云端”，优化生成的栅格数据。

2.3 基于雾计算平台的路径规划服务优点分析

基于雾计算平台的路径规划服务能够为用户提供实时、准确的路径建议，主要优点如下：

1）基于雾计算平台的路径规划服务能够根据当前道路与野区的状况提供低时延的服务；

2）能够提供灵敏的断线重连服务，当车辆由于环境变化出现通信中断并重新连接后，能够继续提供相关服务；

3）能够有效降低终端的计算压力，能够提供多种类型的访问方式，为异构的终端提供统一的路径规划服务；

4）能够有效降低云计算平台的访问量，针对某特定位置，推送地区相关性服务，包括油料补给点、临时休整区域等；

5）能够搜集特定地区的天气、水位等信息，实时修改路径方案；

6）能够将路径规划的衍生及相关的信息，如预计到达时间、前方雷雨等信息，实时推送至用户；

7）能够采集汇总路况、野地、水纹、居民区的变化信息，整理并融合后将变化内容上传至云计算平台，优化地形预处理结果。

3 野区路径规划算法

3.1 单类型车辆野区路径规划介绍

利用“云”环境下的计算能力，针对不同类型的车辆，分别对需要进行路径规划的区域进行地图预处理操作。

单类型车辆路网-野区路径规划问题主要包括两个部分：1）地图预处理；2）针对单一车辆类型的路径寻优。本文假设已获取初始地理环境信息，包括道路桥梁信息、建筑群信息、水域信息、高程信息等。对于突发的地图信息，包括桥梁断裂、新建临时桥梁等，在雾计算平台上采用动态地图调整的方式进行路径调整。

3.2 地图预处理

通过预先获取的地理信息，对指定地域的地图进行栅格化。单个栅格中包含的信息为：道路信息与可通行/不可通行信息，道路信息的优先级最高，当该栅格同时有道路和不可通行区域，如代表桥梁穿过湖泊的栅格，认为该栅格代表道路。不可通行信息包括建筑物或建筑物群信息、湖泊信息、河流信息、高程障碍信息等，同一标示为不可通行区域。地图预处理流程，如图3 所示。

图3 地图预处理流程图

3.3 地图动态调整

随着道路与野区的环境发生变化，初始化的栅格信息无法满足后续路径寻优的需求，此时需要设立动态地图调整图层，根据该图层中的信息进行栅格矩阵的二次调整。动态地图调整图层中包括：1）临时可通行区域；2）动态障碍区域。

临时可通行区域：当开拓出新路、新建临时桥梁等情况下，在动态图层中设置临时可通行图元，将对应区域的栅格设置为可通行区域。临时可通行区域信息优先级高于湖泊、河流等初始障碍信息。

动态障碍区域：临时设置禁入区域、道路堵塞等情况下，在动态图层中设置动态障碍区域，将对应区域的栅格设置为障碍区域，动态障碍区域的优先级高于原始道路信息。

3.4 野区路网路径寻优

将地图映射为栅格矩阵的基础上，采用A*算法作路径寻优方法。A*算法是一种启发式路径搜索算法，具有较高的搜索效率。A*算法的核心为启发函数，如式（1）所示。

其中，f（n）为第n 个栅格点的启发函数值，g（n）为从起始栅格点到当前栅格点的累计消耗，h（n）为从当前栅格点到终止栅格点的预计消耗。

野区路网环境下需要提供不同的规划模式，包括：1）路径最短模式；2）道路优先。路径最短模式情况下，采用传统的A*算法的启发函数；时间最短模式下，采用优先道路的原则。本节在结合地图预处理的基础上，根据栅格中保存的道路相关属性，创新性地提出含有道路损耗的启发函数，在靠近道路的情况下，优先使用道路机动，当道路绕远时，采取抄近路的方式，进入野地机动，野区路网的启发函数如式（2）所示。

其中，gi，j为从起始栅格到第i 行、第j 列栅格的累计损耗，hi，j为从第i 行、第j 列栅格到终点栅格的预计损耗，μLast表示上一栅格点至该栅格点的道路损耗，计算公式如式（3）所示。

其中，r 为接近道路率，r 越大，道路损耗的变化率越快，K 为道路因子的上限值，K 越大远离道路的消耗越高。θcurr为当前栅格点的道路距离，θLast为上一栅格点的道路距离，θgap为相邻两个栅格间最大的道路距离差，在初始化矩阵的过程中，通过式（4）计算得到。

其中，Lot（1，1）表示第1 行、第1 列的经度值，Lot（3，3）为第3 行、第3 列的经度值，Lat（1，1）表示第1 行、第1 列的纬度值，Lat（3，3）表示第3 行、第3列的纬度值，Lj表示该地区单位经度的实际距离（m），Lw表示该地区单位纬度的实际距离（m）。

A*算法收敛的充要条件是：对于任意节点n，都有h（n）≤h'（n），h'（n）是n 到目标的实际最短距离。此时也称h（n）是可采纳的。本文中采用Moore型栅格，路径寻优时，只能向上、下、左、右、左斜上、左斜下、右斜上、右斜下这8 个方向移动，所以，第i行、第j 列的预计消耗函数h（i，j）如式（5）所示。

其中，Endi、Endj 是终点的栅格坐标信息，i，j 是当前路径点的栅格坐标。根据野区路网启发函数，结合A*算法的常见步骤，实现野区路网的路径规划功能。

4 基于雾计算平台的路径规划结果

本次仿真中，首先试验了路网-野区的路径规划结果，预处理区域分别涵盖了居民区、河流、道路、桥梁、沟渠等常见矢量地理信息，预处理结果如图4 所示。

图4 路网-野区预处理结果

其中，图4（a）表示原始地图情况，图4（b）表示预处理后的结果，其中标号①标签表示识别该区域为居民区障碍；②号标签表示识别该区域为面状湖泊障碍；③号标签表示识别出河流障碍；④号标签表示识别该区域为道路。其余未标示为可通行野地区域。

图4（c）与（d）分别表示当预处理的车辆爬坡度为30°与45°时，识别出该区域的坡度障碍，红色区域表示高程障碍区域。爬坡度为45°相比于车辆爬坡度为30°的情况，高程障碍明显减少，只有零星区域为高程障碍。

在完成地图栅格化的基础上，考虑了时间最短模式与路径最短模式，在时间最短模式中，设置优先接近道路，假设车辆在道路上的行驶速度是野地上行驶速度的一倍，两种路径寻优结果如图5所示。

图5 静态双模式路径寻优结果

图5 中，标号①表示时间最短模式，标号②表示路径最短模式，在时间最短模式中，从起始点出发后，优先考虑在道路上行驶，当靠近终点时，脱离道路进入野地行驶，在路径最短模式中，以快速接近终点为最优目标，在靠近重点的过程中，通过道路跨越水系障碍物。

通过模拟器向雾计算平台发送桥梁被毁以及新建临时桥梁的模拟数据，并执行动态路径调整功能，仿真结果如图6 所示。

图6 地图动态调整路径规划仿真

图6 中①号标签指向地图为动态调整之前规划的路径；②号标签指向地图动态调整之后规划的路径；③号标签指向障碍信息，该障碍区域覆盖在原图层中跨越河流的桥梁上；④号标签指向临时可通行区域，表示在该区域建立一座新的桥梁，提供跨越水系的通行能力。仿真的顺序为：1）先设定起始点与终止点并进行路径规划，生成①号标签指向的路径；2）模拟器向雾计算平台发送桥梁被毁信息，如③号标签所示，此时进行路径规划，显示为“未找到合适路径”；3）模拟器向雾计算平台发送新建桥梁信息，如④号标签所示；4）重新进行路径规划，生成动态调整后的路径，如②号标签所示。

选取高层区域，设定车辆的爬坡度为30°，并进行预处理，通过模拟器向雾计算平台发送高程变化数据，并执行动态路径调整功能，仿真结果如图7所示。

图7 高程变化动态仿真

图7 中，（a）图表示针对爬坡度为30°的车辆，进行预处理后，雾计算平台的路径规划服务识别出的不可通信区域，如①号标签指向的红色区域；（b）图表示高程变化后的动态路径规划效果，③号标签指向高程平滑区域，如通过炸裂山体等方式将坡度过高的地方移除后，重新进行路径规划，规划结果如④号标签所示，雾计算平台的路径规划服务识别出新的可通信区域，并采用新开辟出的通路作为规划结果。

5 结论

本文提出了基于雾计算环境下的道路- 野区路网的路径规划的方法，分别阐述了路径规划服务在雾计算平台下的应用模式。并从地图预处理、地图动态调整、路径寻优这3 个方面，阐述了单类型车辆的路径规划方法。今后的研究过程中，在路径规划时要考虑更多的约束信息，如某通道的流量约束，并将单类型车辆的路径规划扩展至包含不同类型车辆队伍的联合路径规划。