文献：DPTO: A Deadline and Priority-aware Task Offloading in Fog Computing Framework Leveraging Multi-level Feedback Queueing
延迟相关优先级感知卸载（DPTO）策略，基于任务的最后期限为每个任务分配优先级，并将其分配给适当的多级反馈队列。该模式减少了队列上延迟敏感任务的等待时间，并最小化了低优先级任务的饥饿问题。DPTO策略根据每个任务的资源可用性和从物联网设备的传输时间为其选择最佳计算设备。该策略在满足最后期限的同时，最大限度地减少了任务的总卸载时间。
一、介绍
任务通过延迟期限分为硬期限和软期限。
基于硬截止日期的任务，任务应在指定的截止日期内完成其处理，否则任务输出对物联网设备不再有效。
基于软期限的任务，任务的输出在一定程度上是有效的，即使任务未能满足相应的期限，也会受到一些惩罚。
基于任务的优先级和以最小延迟满足任务的最后期限和资源约束的能力，将任务卸载到合适的计算设备。
使用多级反馈排队模型，为物联网应用程序在分层雾云环境中引入了启发式任务卸载模式。该工作的主要目标是最小化实时任务的总排队等待时间和卸载时间，同时满足最后期限和资源限制。
提出分层雾云模型，用于处理从物联网设备生成的任务。
指定优先级分配策略，设计基于规则的任务调度策略，以找到任务的最优顺序并最小化队列中的等待时间。
采用启发式任务卸载策略，以找到合适的计算设备，最大限度地减少总体卸载时间。
二、系统模型和问题公式
1、网络模型
本地计算：如果任务是在物联网设备本地计算的，那么总计算主要取决于物联网设备的CPU频率，而不是通信延迟。
远程计算：任务都上传到本地分布式雾设备或集中式云服务器。任务的最后期限以及物联网设备和计算设备（雾或云服务器）之间的通信延迟将对卸载决策起主要作用。
（1）任务上传：通过本地物联网网关上传。
（2）任务处理：任务处理具有该设备的计算频率。
（3）任务下载：计算设备根据其完成情况将其结果发送到相应的物联网设备。
总卸载时间：基于物联网的任务要么在本地处理，要么应根据其最后期限和计算设备的资源可用性卸载到本地分布式雾设备或集中式云服务器。
对于本地处理，任务的总卸载时间仅取决于它们在物联网设备上的处理时间。
对于远程计算的基于物联网的任务的总卸载时间取决于数据上传和下载的传输时间以及所选计算设备上的处理时间。
2、排队模型
先到先服务FCFS
离散任务序列的发生可以被现实地建模为泊松过程，即连续任务到达之间的时间间隔是指数分布的。对于泊松过程，两个这样的任务到达之间的时间间隔被视为独立的随机变量。
物联网网关根据任务的截止日期将任务分为三类：硬截止日期、软截止日期和无截止日期任务。设置三个多级反馈优先级队列放置不同等级的任务。
3、问题公式
最小化来自物联网设备的所有任务的卸载延迟（上传时间、远程任务处理和下载时间）和本地或远程计算队列中的等待时间。
硬期限和软期限的任务分配给本地雾服务器设备；无限期任务可以部署在集中式云服务器上。
本策略最小化任务集的总排队等待时间和总卸载时间。
三、延迟相关优先级感知任务卸载（DPTO）策略
a） 在第一阶段，物联网网关根据其截止日期验证每个任务并分配优先级。
b） 在下一阶段，任务调度器找到一个最小化队列中任务等待时间的最优调度策略，并优化低优先级任务的饥饿问题。
c） 最后，调度的任务被卸载到适当的计算设备，该设备在满足任务的最后期限的同时最小化总延迟。
1、优先级分配
任务优先级1：支持具有严格期限的延迟敏感任务。在物联网设备中的本地或本地雾设备处理。
任务优先级2：通过协商总等待时间来满足其最后期限。在本地雾设备处理，或卸载到集中式云服务器处理。
任务优先级3：支持资源密集型任务，无需任何期限。卸载到具有足够处理和存储资源的集中式云服务器处理。
2、任务调度
考虑队列中任务的两种等待时间约束，以避免饥饿问题。
3、任务卸载
任务卸载策略使用启发式策略来为每个调度任务找到合适的计算设备，该策略在满足最后期限的同时最小化总卸载时间。
四、经验评价
随机卸载：在这种卸载中，每个物联网设备随机选择一个计算设备来卸载其任务。
最高数据速率（HDR）卸载：每个物联网设备都以最短的上传时间将其任务卸载到计算设备。
最高计算设备（HCD）卸载：物联网设备将任务卸载到具有足够CPU频率处理任务的计算设备。
- 平均排队等待时间
基于硬截止日期的任务具有更高的优先级，并且需要比其他任务更快地处理，因此，基于硬期限的任务的排队等待时间最小。
DPTO策略将基于硬截止日期和软截止日期的任务安排为立即卸载，而不是基于无截止日期的。考虑其优先级和截止日期，减少了基于最后期限的任务的等待时间。 - 平均卸载延迟
当物联网设备生成更多具有处理期限的任务时，雾设备有限的计算能力和通信带宽不足，导致，任务卸载时间随着任务数量的增加而增加。此外，高优先级任务的卸载延迟低于低优先级任务。
DPTO策略基于最小通信开销和用于处理任务的计算资源的可用性将任务部署到适当的计算设备。 - 满足延迟期限的任务数量
取决于排队等待时间和卸载时间。
具有硬截止日期的任务大多满足其截止日期。由于有限的资源约束和本地雾节点的通信开销，软截止日期任务无法满足其截止时间。
DPTO策略首先分配硬期限任务，然后分配软期限和无期限任务。随着队列中任务数量的增加，基本满足最后期限。 - 吞吐量性能
任务的吞吐量取决于在特定时间戳内完成其处理的任务的数量。
DPTO策略将基于截止时间的任务部署到本地雾节点，本地雾节点以最小的通信开销完成任务的处理，并增加任务的吞吐量。
将任务部署到本地雾设备，以最小卸载时间满足任务的资源需求。这将最大限度地减少任务的总处理量，并提高吞吐量。
五、结论
具有多级反馈排队模型的分层雾云环境中的任务卸载策略，关键思想是尽量减少任务的总卸载时间，同时满足任务的最后期限。该策略基于任务的截止日期来考虑任务的优先级，并将它们分配到不同的优先级队列中，以最小化较高优先级任务的等待时间。该策略利用多级反馈排队模型减少了低优先级任务的饥饿问题。
