ReLIEF

摘要

由于若干物联网应用对实时性有着严格要求，雾计算应运而生以克服云计算的高延时与其他局限性。由于数据包丢失的高概率性、物联网设备的能源限制以及雾基础设施可能频繁遭受的外部干扰，实时任务的时序约束可能受到破坏。因此，实时任务的执行可靠性一直是雾计算领域的重大挑战。除了任务正确执行之外，依照其实时分类在截止期限前完成任务同样至关重要。当前最先进的研究方法通常聚焦于雾计算系统中任务的延迟性或功能性，但这些方法鲜少关注动态环境下实时约束任务的可靠性问题。本文提出一种基于机器学习的新型主备任务分配策略（ReLIEF），以提高雾基物联网系统的可靠性。为筛选适宜执行主备任务的节点，ReLIEF采用强化学习方法，该方法通过平衡每个雾设备的通信延迟与工作负载，在动态环境中表现卓越。仿真实验表明，相较于现有技术，我们提出的新方案能将任务丢弃率降低多达84%，同时相较对比方案能将系统可靠性提升近72%，并实现工作负载均衡分配。

• 独立任务，动态调度，备份容错，截止时间

引入

• 物联网设备资源受限，节点与云资源间延迟显著

• 雾计算在网络边缘执行部分任务来降低延迟，适于时效要求高的应用

• 但分布式开放结构易故障，同时链路通信不可靠，因此设计了使用强化学习的主备份容错策略提高截止时间约束下的可靠性

• 传统优化算法依赖于规则，问题复杂时效果欠佳，强化学习擅长自动探索大规模且多样的解决空间

• 贡献：

  • 首个使用强化学习主备份策略应对链路和节点故障，同时考虑截止时间约束

  • 延迟备份丢弃策略来降低处理开销、负载和能耗，仅当备份任务临近截止时间时发送

  • 可处理不同系统结构与任意雾节点数目、工作负载

  • 实验证明在工作负载、可靠性和延迟方面优于sota

背景与相关工作

• 相关工作：略

• Q-learning：

  • 无模型（不需要对环境建模）强化学习

系统结构

• 系统与负载

  • IoT设备 <—> broker <—> 雾节点，broker与雾节点间仅单跳距离，传输带宽高

  • 主任务队列 + 备份任务队列，备份任务临近截止时间且优先执行

  • 任务属性：大小、到达时间、cpu循环数、截止时间

• 延迟模型

  • broker处理耗时、传输延迟（带宽含噪）、执行耗时、排队延迟

• 可靠性模型：泊松过程

  • 任务x在节点p上的可靠性：Rc,p = exp(-λt)，t为j在p上的执行时间，λ为节点故障率

  • 任务y传输到p的可靠性：Rl,p = exp(-μt)，t为y传输到p的耗时，μ为通信故障率

  • 任务z从broker传输到节点p上执行的可靠性：Ro,z=Rc,p·Rl,p

  • 考虑主备份任务的完成情况，有全正常、仅主节点正常、仅备份节点正常三种情况，Rz=Ro,z^2+2Ro,z(1-Rz)=2Ro,z-Ro,z^2

  • 系统可靠性：R=∏Rz

• 负载分布模型

  • 雾节点f的总负载：Wf=TPQ+TBQ，TPQ为主任务队列所需总cpu循环数，TBQ为备份任务所需总cpu循环数

  • 负载分布：WL=sum(|Wf-Wavg|)

方法

• 问题描述

  • 时间槽s内系统可靠性R >= Rs，Rs人为设定

  • 任意任务i响应时间T <=di，di人为设定

• Q-learning

  • 状态：离散化为k种取值，加速收敛，{ 节点可靠性Ri、节点负载WLi }

  • 动作空间：所有可能的主备份节点对

  • 奖励：状态si到sj，延迟、负载、可靠性的变化率的线性组合

• 方法论

  • 雾节点端

    • 将收到的任务分类添加至主/备任务队列，优先调度最接近截止时间的备份任务，再调度最接近截止时间的主任务

  • broker端

    • 获取环境状态，根据Q table选择动作，当任务临近截止时间但未收到时，发送备份任务，计算reward，更新Q table

实验

• 在可靠性、负载分布、吞吐量（截止时间内完成任务数）上优于baseline

• 在延迟上持平，因为备份任务临近截止时间才会发送