基于优先权排队论的雾计算资源配置算法

朱 敏

（江苏航运职业技术学院智能制造与信息学院，江苏南通 226010）

引言

物联网技术与应用的发展，离不开云计算技术与基础设施的支持。然而，云端数据中心通常远离物联网终端设备，数据传输所造成的网络瓶颈会导致延迟和低质量的物联网服务。使得一些对实时性要求较高的物联网应用，如智能制造、智慧医疗等无法正常运作。雾计算由此出现。它是一种分布式的计算方式。雾计算设施通常位置上靠近物联网终端设备，因而能减少延迟，提供更高质量的用户服务。雾计算不是云计算的替代品，而是云计算的有效补充，两种技术相辅相成。物联网终端设备可以将平常零散的数据先发送到雾计算设备，经过聚集和初步处理后再批量发送到云端，以减少对云端的访问数，而将复杂的计算任务交给云端处理。Mahmud 等人的研究认为雾计算是对云计算范式在物联网边缘的一种扩展，是对云计算高延迟和网络拥塞问题的一种解决方案，并就雾计算在结构、服务及安全等方面所面对的主要挑战和重要的研究方向展开讨论[1]。在文献[2]中作者研究了雾层和云层之间的相互关系，对雾计算系统的服务延迟、能耗、运营成本等方面精细建模。研究表明，当系统中延迟敏感型的应用较多时，雾计算能取得比云计算更好的综合性能。在文献[3]中作者将排队论应用于雾计算的分析与研究，提出了一个基于开放性多类别排队网络的模型，将到达任务在雾层与云平台间作有效分配。在文献[4]中作者提出了一个基于优先队列任务调度算法，以减少延迟敏感型任务的响应时间，并针对非计算型任务提出了一种动态优先级方案，从而将延迟控制在某个可接受的阈值之内。

雾计算的关键在于处理好计算任务在雾节点与云平台之间的分配问题，因此应用程序的任务调度和资源分配是它面对的主要挑战。本研究基于带优先权的排队理论，根据计算任务对延迟的敏感程度将它们分成高、中、低三个优先级层次，提出了一种雾计算环境下有优先权的任务调度和资源分配方案。并对这种方案进行模拟验证。

1 基于优先权排队论的资源配置模型

系统模型基于雾计算的计算架构，包括3 个层次，物联网终端设备层、雾计算层和云计算层。云计算层处于顶层，即远端的云计算数据中心。中间层是雾层，由一定数量的雾节点组成。每个雾节点都是一个微型数据中心。底层为物联网终端设备层，它们是服务请求的发起者。

终端设备层发出的服务请求首先发送到最近的雾节点。雾节点收到客户端请求后，根据请求的优先级，可用资源等要素，将请求放入不同优先级的队列中。然后按照优先顺序，依次为队列中的任务提供服务。如果某个任务本节点有能力处理，则将该任务就地处理后发送给客户端。如果本节点资源不足，而雾计算层中的其它节点有资源处理，则将该任务发往其它雾节点处理。否则就将服务请求发送到云计算中心处理。我们将任务的优先级分成H、M、L 三个等级，对应三个队列QH、QM、QL。每一个到达的任务都有一个最大可容忍延迟delayi。对一些有极高延迟要求的任务，这些任务必须在一个较小的延迟内得到响应。我们设一个阈值TH1。若一个任务的delayi小于TH1，就赋予这个任务高优先级（H）；若一个任务的delayi大于TH1，但小于TH2，则赋予中优先级（M）；其它对延迟不敏感的任务赋予低优先级（L）。

算法1 Priority 算法，为到达的任务赋优先级。

输入：N, delayi,TH1,TH2、

输出：Pri, QH,QM,QL

如图1 所示，我们将排队理论[5]应用于系统建模。假设有n 个物联网终端设备发出请求任务，其任务的到达过程服从总到达率为λ 的泊松过程。雾层服务器处理任务的时间服从参数为μ 的负指数分布。雾层服务器符合M/M/k 队列模型，其中k 表示系统中雾服务器的数量。

图1 系统排队模型

图2 所示为队列系统的连续时间马尔可夫链状态转换关系图。其中λ 为到达率，μ 为服务率。M/M /k 队列系统中有i 个任务的稳态概率通常为

图2 马尔可夫链状态转换关系

假如所有服务台都处于忙期，一个新的任务进入而需要等待的概率为

设定在排队系统中一个正接受服务的任务不能被后到达的优先权更高的任务所中止，即这是非强占型的排队系统，则在有3 个优先等级的队列中，正在接受服务中的任务的平均剩余服务时间W0为

3 个不同优先级（1 为最高、3 为最低）平均等待时间分别为

假设α1、α2分别为高、中优先级任务在总任务数中的平均占比，则有

某一任务在队列系统中的平均逗留时间可以表示为

这样我们的基于优先权的资源提供策略就可以转换成一个最小化任务延迟的优化问题。该问题可以形式化地表示如下

2 实验与分析

我们通过仿真实验对模型进行评估与分析，表1所示为仿真参数及其取值。

表1 仿真参数及取值

我们首先将本方案下不同优先权限任务的系统延迟进行了比较，并且把有优先权的方案与通常的无优先权的排队方案同时进行了比较，见图3。结果显示，高优先级与中优先级的任务的延迟得到显著的改善，都比无优先分级的情况要好，但低优先级任务的延迟变得更大了，显然，高、中优先级的改善是以牺牲低优先级为代价的。

图3 到达任务系统延迟

其次，我们考察了在系统空闲（ρ=0.3）与繁忙（ρ=0.8）两种情境下到达任务的延迟情况。由图4 可知，对高优先级任务而言，延迟的变化很小，而无优先级的延迟则要大得多。两者相比，在系统空闲（ρ=0.3）时，高优先级任务的延迟性能比无优先级任务提升了25.53%；而在系统繁忙（ρ=0.8））时，延迟性能的提升更为显著，达到了76.19%。图5 显示了低优先级任务在系统繁忙与空闲时的不同变化。低优先级任务在系统繁忙时延迟会显著增加，远大于无优先级时的情况。

图4 高优先权任务延迟比较

图5 低优先权任务延迟比较

3 结论

本研究提出了一种基于优先权排队论的资源分配方案，旨在使一些延迟敏感型的物联网应用能够在邻近的雾计算层得到优先处理。实验结果显示，高、中优先级任务的延迟得到显著的改善，大大优于无优先权的通常情境。