用于智能矿山移动边缘计算的二维动态匹配算法

赵端，申澄洋，史新国，刘柯

（1.中国矿业大学 矿山互联网应用技术国家地方联合工程实验室，江苏 徐州 221116；2.中国矿业大学 信息与控制工程学院，江苏 徐州 221116；3.淄博矿业集团有限责任公司 信息中心，山东 淄博 255299）

0 引言

近年来，煤炭行业的高质量发展目标对智能矿山建设提出了更高要求，少人、无人成为煤矿智能化下一阶段的重要目标。在智能矿山发展初期，煤矿井下复杂通信环境导致的通信设备传输速率和带宽不足的问题长期以来未能实现本质突破。云计算和5G 技术以其超高数据速率、超低延迟和超大规模接入的优点，为结合边缘计算的智能矿山建设提供了解决方案[1]。

云计算技术可以较好地解决任务处理延迟高、速度慢等问题，提高用户服务质量与用户体验质量[2]。但从用户到云端的物理距离较远，会造成一定的传输延迟和较慢的响应速度，尽管随着5G 技术的发展，这种延迟可以被缩短到很低的数量级，但依然无法满足部分延迟敏感任务如虚拟现实、实时轨迹预测等的延迟约束。为了缓解延迟约束问题，边缘计算被提出。边缘计算是将具有一定计算能力的计算设备和常用数据存储设备部署在靠近用户的边缘端，从而使用户任务处理延迟大大降低，达到了性能和延迟的均衡。因此，边缘计算在结合物联网和信息物理系统的场景中获得大量应用[3]。

智能矿山建设中，边缘计算服务能够支持煤矿工业多类应用达到智能化水平，如高精度实时定位、远程生产实时控制、煤矿井下智能巡检和安全防护等。虽然边缘服务器能够较好地完成边缘侧移动用户迁移来的任务，但通常边缘服务器是轻量级的，其算力与云计算相比较为有限，如果某一区域内移动用户任务量在短时间内激增，会导致任务出现排队现象，从而造成延迟，影响服务质量，甚至无法满足延迟约束。因此，目前在1 个区域内通常部署多个边缘服务器，以满足该区域内可能出现的任务拥塞。然而，移动用户生成任务后往哪个边缘服务器迁移的决策，以及使用何种功率进行任务数据包发送的选择，均会大大影响整个网络的整体延迟、任务完成率及能耗，因此，基于多对多匹配模型的计算迁移问题（Computing Offloading Problem，COP）成为目前移动边缘计算（Mobile Edge Computing，MEC）的研究热点。近年来，国内外学者开展了针对MEC 中COP 的研究。文献[4]提出了一种MEC 多跳卸载算法，以降低区域中移动用户整体能耗。文献[5]提出了一种MEC 和无线能量传输技术结合的优化方法，在无线供电的多用户MEC 系统中通过对接入点（Access Point，AP）的能量传输波束形成、用户的中央处理单元（CPU）频率及用户之间的时间分配进行联合优化来提高MEC 性能，使AP 总能量消耗达到最小。文献[6]提出了一种基于边缘计算架构的短期能量预测系统，对整个MEC 网络能量消耗进行调控。文献[7]利用MEC 中边缘服务器数据存储的文件热度指标，提出了一种边缘服务器数据更新机制，将较常用数据保存在靠近用户的位置，将不常用数据传输至上层设备，降低了任务处理过程中的数据下载时间延迟。文献[8]建立了移动用户联合卸载和传输功率分配模型，针对任务传输过程中的排队现象，提出了一种离散功率调整机制，在满足延迟约束的情况下，完成任务数据传输并最小化设备功率。文献[9]联合优化了用户选择和资源分配策略，并将问题转换为混合整数非线性优化问题，再进一步松弛为凸优化问题，以获得最大化的能源效率。最近一段时间，能量收集技术和无线能量传输技术取得了较大发展，无线设备可从自然环境中获得能量或者通过无线充电设备获得额外电量[10-11]，这为MEC 应用场景中无线设备能量约束问题提供了一种可行的优化方案。一些研究也将无线能量传输技术应用于MEC 场景中，在能量辅助设备的协助下，MEC 相关执行步骤得到了一定优化[12-13]。随着无人机（Unmanned Aerial Vehicle，UAV）技术和机器学习技术的发展与广泛应用，也有研究将UAV 技术应用于MEC 中作为可移动的中继设备，对区域中无线通信网络架构进行动态维护和优化[14]，根据UAV 本身的飞行能耗和无线传输能耗优化中继节点位置及MEC 卸载匹配决策。文献[15-16]提出了基于深度强化学习的MEC 资源分配机制，在较多实际数据支撑的条件下有效提升了MEC 整体性能。

以上研究较新颖，但实施难度较大，工程实现方式较复杂，应用难度高，并且多为面向个人用户的商业化服务优化，目前还未有针对智能矿山中MEC 资源分配优化的相关研究[17]。本文将多边缘服务器、多移动用户的应用场景建模为多对多匹配问题，并引入边缘服务器动态算力和移动用户动态剩余能量2 个动态参数，将传统的静态模型转换为动态匹配模型，提出一种基于移动用户对边缘服务器偏好表及边缘服务器对移动用户偏好表的二维动态匹配算法，使区域内移动用户任务在满足延迟约束条件下提高总任务完成率，进而最大化系统效用。

1 算法应用场景模型

在智能矿山工业生产环境中任务内容量激增情况下，传统边缘计算卸载机制难以满足服务质量。因此，本文对MEC 任务卸载过程中的边缘服务器与移动用户多对多匹配问题进行优化，以找到满足预设条件的解。具体应用场景举例：由于自然灾害、电力事故等导致部分边缘服务器无法提供服务或需使用备用电源，伴随移动用户信息传输的爆发式增长。以上情况可描述为资源紧缺状态下出现较大任务量的应用场景模型，在该应用场景模型下对计算和能源资源的合理分配显得尤为重要，采用优异的资源分配算法将大大改善特殊情况下无法满足服务质量要求的情况。密集任务条件下MEC 模型如图1所示。短时间内多任务进入MEC 服务区域，导致边缘服务器无法为所有任务同时提供满足延迟约束的服务，因此部分用户无法在延迟约束下完成任务。需要注意的是，由于边缘计算概念中资源被提供方通常称作“用户”，本文讨论的应用场景中“用户”为井下设备。

图1 密集任务条件下MEC 模型Fig.1 Mobile edge computing model under intensive task conditions

1.1 网络模型

MEC 服务器部署在智能矿山场景中的基站上，具有一定的数据存储能力和计算能力。本文定义边缘服务器集S={s1，s2，···，sm}（sj为边缘服务器，j=1，2，···，m，m为边缘服务器数量），移动用户集U={u1，u2，···，un}（ui为移动用户，i=1，2，···，n，n为移动用户数量）。令二进制函数Ψ（ui，sj）表示移动用户ui在时隙Δt内是否将任务迁移到边缘服务器sj：

1.2 通信模型

移动用户与边缘服务器之间采用无线通信模式，根据香农公式，移动用户ui至边缘服务器sj的传输速率为

式中：B为信道带宽；Pi为移动用户ui的功率；hi,j为移动用户ui到边缘服务器sj的信道增益；σ2为高斯噪声功率谱密度。

生成任务的移动用户将决定直接发送任务数据包到边缘服务器还是通过路径空闲的移动用户进行中继发送，由于发送消耗能量与传输路径距离呈正相关，所以移动用户更偏向于通过中继用户进行卸载。

1.3 任务处理模型

定义边缘服务器sj的计算能力=FjTlatency，其中Fj为边缘服务器CPU 频率，Tlatency为用户延迟约束的最大容忍延迟，所用时间若超过最大容忍延迟即认为服务未达到预期需求。定义完成移动用户ui的任务所需计算量为。

设一个边缘服务器是单线程的，同时仅能处理1 个任务，所有移动用户的最大容忍延迟Tlatency均相同，并且将Tlatency作为标准时隙Δt，所有移动用户在时隙开始时刻确定是否生成任务，若ui生成任务，则令移动用户ui在时隙Δt内所产生的任务=1，否则=0。在1 轮任务处理过程中，MEC 网络模型中所有移动用户在标准时隙开始时刻确定其任务状态信息，并 形成一张任务 状态表，以表示所有移动用户的任务状态，其中为移动用户ui当前位置坐标信息。

1.4 偏好模型

本文提出的二维动态匹配算法是基于偏好的，包含边缘服务器对移动用户的偏好及移动用户对边缘服务器的偏好。进行任务处理初始化时，每个边缘服务器形成一张针对移动用户的一维偏好表，移动用户也形成针对边缘服务器的一维偏好表。由于边缘服务器能源约束较低，不必考虑移动传输的能源消耗，仅考虑边缘服务器算力消耗，所以边缘服务器优先偏好任务计算量小的移动用户。而移动用户由电池供电，具有一定的能量约束，因此需要考虑影响能量消耗的因素。本文以物理距离表征能耗性质，即移动用户更偏向于将任务卸载到最近的边缘服务器。同时，由于本文旨在对整个智能矿山MEC网络进行优化，需尽可能使煤矿边缘服务器算力资源均匀分配，所以将边缘服务器的算力作为动态参数。例如，当第1 个移动用户的任务分配到边缘服务器sj后，sj的算力更新为，此时移动用户对边缘服务器的偏好表发生更改，第2 个移动用户将向位于新的偏好表首位的边缘服务器提出卸载请求，依此类推，直到匹配完成。

移动用户对边缘服务器的偏好与传输路径距离和边缘服务器剩余算力有关，因此，令移动用户对边缘服务器的偏好值为

式中：ε，ω为偏好系数，由于边缘服务器剩余算力和距离同样重要，本文中取 ω=ε，在计算资源稀缺的应用中可取 ω＞ε，在能量资源稀缺的应用中可取 ω＜ε；di,j为移动用户ui到边缘服务器sj的物理距离。

2 问题分析

定义Dk为第j个边缘服务器当前时间段第k个子任务的数据大小，Rk为第k个子任务的传输速率，则第k个子任务排队等待时间为

任务数据包传输阶段耗时为

第k个子任务排队过程和传输过程总耗时为

卸载完成后，边缘服务器执行处理任务的时间为

单个移动用户的任务从生成到收到结果的总时间为

由于计算结果数据包与任务数据包相比通常要小数个数量级，所以可以忽略计算结果从边缘服务器回传的时间。优化模型可描述为在边缘服务器算力不超过限制的情况下，最小化总任务完成时间及移动用户发送、中继、接收的耗能（其中耗能通过移动用户发送功率表示）。

式中：Ei为当前剩余能量；Ed为维持MEC 各设备正常运行的最低能量。

约束C1表示每个移动用户只能将任务卸载到1 个边缘服务器，约束C2表示移动用户任务完成时间需要满足延迟约束，约束C3表示移动用户的当前剩余能量要高于维持MEC 各设备正常运行的最低能量。

3 算法实现

移动用户将自身状态信息传输至边缘服务器，边缘服务器根据收到的状态信息，形成边缘服务器集S对移动用户集U的偏好表及移动用户集U对边缘服务器集S的偏好表。设经过边缘服务器排序后的移动用户偏好表KS={u1,u2,···,un}，由于边缘服务器仅考虑移动用户产生的任务的困难程度，所以各边缘服务器对移动用户的偏好表是相同的，均为根据移动用户生成任务所需计算量排序的一维偏好表。而不同移动用户由于物理位置和能耗不同，其对边缘服务器的偏好表可能是无规律且各不相同的，分别记为。将边缘服务器对移动用户偏好表及移动用户对边缘服务器偏好表相结合，可形成一张二维动态偏好表，为便于算法执行，将其抽象为二维矩阵：

智能矿山MEC 资源分配模型与约会匹配模型[18]类似，约会匹配模型是一个经典的稳定匹配模型，最终会达到匹配稳定状态，本文中移动用户与边缘服务器之间的匹配也可视为稳定匹配问题，期望求出满足约束条件的最大化用户总任务完成率的稳定匹配状态。与约会匹配模型不同的是，为了减少算法计算量，MEC 资源分配模型中边缘服务器对移动用户的偏好表被设置为静态，而边缘服务器的剩余算力是动态变化的，因此移动用户对边缘服务器的偏好表也是动态变化的。二维动态匹配算法如下。

二维动态匹配算法结合边缘计算实际情况，将边缘服务器对移动用户的偏好设为静态量，生成MEC 匹配决策时，直接提取当前二维矩阵M中位于M（1，1）的移动用户和位于M（1，2）的边缘服务器形成匹配即可；更新未匹配移动用户对边缘服务器的偏好表时，将M（1，2）处边缘服务器的剩余算力作为比较值，在各移动用户对边缘服务器的偏好表中从后向前插入排序即可。对于刚匹配成功的边缘服务器，由于剩余算力急剧减少，移动用户对其偏好会下降很多。因此大多数情况下，M（1，2）处的边缘服务器将在第1 次迭代时就被插入到移动用户对边缘服务器偏好表的最后一位，这样大大减少了处理时间。

4 仿真分析

采用Matlab 软件进行仿真，在20 m×100 m（宽×长）的煤矿井下综采工作面区域内部署3 个边缘服务器，设置在某一时间段内有100～1 000 个移动用户在区域内活动的仿真实验组，移动用户生成任务是随机的，包括环境感知传感设备数据采集处理任务，机械手、运输设备和钻井机械设备等位置及状态感知任务，井下人员定位设备数据采集任务等。为方便起见，将任务数据大小分为20 kB，1 MB，20 MB 3 种，任务处理难度与任务数据大小无关，以所需边缘服务器CPU 计算次数1×106，1×107，1×108表示3 种计算难度，任务数据大小和所需边缘服务器CPU 计算次数由程序随机等概率生成，设边缘服务器CPU 频率为2 GHz，延迟约束Tlatency为2 s。

用总任务完成率 υcompleted表示匹配结果的好坏程度：

式中：βcompleted为完成的任务数；βgenerated为1 个时隙中生成的任务总数。

选用随机卸载算法、分区卸载算法、基于能量收集的匹配算法与本文提出的二维动态匹配算法进行仿真对比。随机卸载算法即生成的所有用户任务随机进行卸载，直到区域内总算力耗尽或总耗能达到阈值；分区卸载算法即提前将区域分成子区域（子区域数量与区域中边缘服务器数量相等），在预设的子区域内生成的任务自动卸载至该子区域所对应的边缘服务器进行处理；基于能量收集的匹配算法即为用户配备能量收集装置，设置能量收集能力为能量消耗阈值的10%，使用二维动态匹配算法进行资源分配。仿真结果如图2 所示。

图2 不同MEC 资源分配算法总任务完成率对比Fig.2 The results of comparison of different mobile edge computing resource allocation algorithms on task completion rate

从图2 可看出，4 种算法的总任务完成率均随着区域内移动用户数增加而下降，这是因为当区域内移动用户数激增时，计算负载过大，导致边缘计算服务器无法满足所有任务的延迟约束。在区域内移动用户较少时，4 种算法均可达到较高的总任务完成率；当移动用户个数大于200 时，4 种算法的总任务完成率均开始下降，其中分区卸载算法和随机卸载算法下降速度较快，这是因为在数据量激增的情况下，使用普通算法的卸载机制此时已接近满载，而本文提出的二维动态匹配算法能够优先执行计算量较小的任务，从而使总任务完成率随任务增加而下降的趋势放缓，并且在极端情况下，即区域内移动用户个数在短时间内增至500 以上时，能够保持较高的总任务完成率。在区域内总移动用户个数为600 以下时，基于能量收集的匹配算法和本文提出的二维动态匹配算法在总任务完成率上无明显差异；移动用户个数在600 以上时，基于能量收集的匹配算法表现指标略优于本文算法，但未达10%，即未能较好地利用所收集的能量。这是因为能量收集技术更多用于耗能平均的无线传感网中，对于任务耗能差异较大的任务群无法做到将收集的能量按比例分配，生成低难度任务的移动用户收集的能量无法转移至高耗能用户处使用，而高耗能用户本身收集的能量又不足以满足其过高的能量需求。再者，能量收集技术更多应用于工业场景，对于面向消费者的商业服务领域的应用场景，能量收集装置无法大规模部署。综上可得，本文提出的二维动态匹配算法在移动用户数增加的情况下能够较好地保证一定的总任务完成率，满足移动用户体验质量及服务质量需求。

5 结语

针对智能矿山应用中任务数据量突然增大情况下MEC 应用场景保证服务质量的问题，将问题类比约会匹配问题并进一步转换为二维动态匹配问题，对边缘服务器对用户的偏好表进行了优化，降低了匹配过程计算量。仿真结果表明，提出的二维动态匹配算法形成的任务卸载匹配所达到的总任务完成率与常规MEC 场景卸载算法相比有明显提高。未来将考虑引入中继移动用户进行数据辅助中继传输，进一步降低移动用户能耗，提升用户体验质量。