没有合适的资源?快使用搜索试试~ 我知道了~
一种基于风险感知策略的多节点任务调度方法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 23 浏览量
2023-02-23
20:06:55
上传
评论
收藏 774KB DOCX 举报
温馨提示
试读
15页
一种基于风险感知策略的多节点任务调度方法.docx
资源推荐
资源详情
资源评论
1. 引言
随着无线通信技术的不断进步,越来越多的文献开始研究关于集群网络中节点容错处
理方法
[1]
及节点容错调度
[2]
,由无人机组成的分布式集群具有设备数量多、计算任务复杂、
多源设备协作的特点
[3]
,可执行勘探、检测等数据处理的工作。集群中的每个无人机
(Unmanned Aerial Vehicle, UAV)都被视为一个具有计算能力的节点,实现数字化信息的快
速处理。但在复杂的真实环境下,任何计算节点(无人机)不仅面临着自身任务处理能力有
限,还可能出现网络带宽受限等问题
[4]
。一般地,资源不充裕的节点会将本地计算任务卸
载
[5]
到资源充足的计算节点
[6]
,然而这会导致目标节点上正在执行的计算任务的中断,给目
标集群带来一定风险。同时整个集群还需要承担无人机节点随机接入或离开时产生的网络
波动。
在现有工作中,研究者在解决分布式集群中任务计算与处理的问题时,普遍从节点资
源利用率和任务处理时延的角度入手,将问题转化为分布式任务分配与调度的问题。IBM
研究中心和帝国理工大学的研究将资源分配和任务调度问题建模为一个马尔可夫决策过程
[7]
,为了减少状态空间,进一步将该问题转化为两个具有分割的状态空间的独立的马尔可
夫决策过程,并利用李雅普诺夫优化技术设计了一个代价最优的在线算法。研究针对无线
城域网下 Cloudlet 集群的负载均衡问题,澳大利亚国立大学
[8]
给出的算法理念是:首先求
取各任务的平均响应时间,然后决定每个 Cloudlet 需要分配多少任务到其他 Cloudlet 中。
宾夕法尼亚州立大学
[9]
的研究指出目前多数模型将用户服务请求(或应用程序)当作专用资源
片,其获得的计算、通信和存储资源都是不可共享的,并且指出存储资源不可共享的假设
不适用于数据分析服务,如虚拟现实等,这些服务通常有部分存储资源是可以共享的;该
研究针对联合服务放置和请求调度问题建立线性规划模型,首次将通信资源和计算资源加
入约束条件,并将同类型服务的存储资源设定为可共享的,将优化目标设为最大服务用户
数,并给出了线性时间解的算法。佐治亚理工学院
[10]
提出了 Femtoclouds 框架,这是一种
将边缘集群设备转化为 Cloudlet 的边缘计算框架,用于处理来源于集群中或集群外的计算
任务;Femtoclouds 根据关键路径将其拆分成多个路径依赖的子任务,然后结合风险控制机
制依照执行时间小的优先策略将子任务分配到边缘设备上;在边缘设备内部,基于各队列
中任务已执行时间为指标,对各队列中的任务进行公平调度,并加入截止时间优化策略,
优先处理接近截止时间的任务。上述工作的主要思想都是尝试将计算任务划分为细粒度的
多个任务组件,再根据任务的资源需求特性、实时的网络连接状态等因素,动态地在计算
终端之间进行任务的调度,通过多方算力间的协同工作来实现应用的分布式执行,但类似
的解决方案尚无法满足无人机集群所面临的场景。由于单个节点(无人机)的机动性高且不
稳定,整个网络对可处理节点波动变化的容错能力的要求越来越高
[11]
。
综上所述,有效降低计算节点(无人机)的处理任务时间,将计算任务合理高效地在每
个计算节点间动态调度以加快任务处理与反馈,同时还要保障集群网络执行任务调度过程
中可对节点的高度动态性和不稳定性做出容错处理成为本文研究重点。为解决上述问题,
本文提出一种新颖的计算任务调度策略,充分考虑了任务的时效性,同时为机动计算节点
设计了容错机制可以更好地应用于复杂环境。主要研究成果如下:(1)针对任务的执行要求
和节点的资源状况选择合适的优化目标组合,并研究基于多目标优化方法的任务调度策略
以尽量满足这些优化目标。(2)针对多节点情况下因节点失效或离开等导致任务中断的情
况,研究任务调度的错误处理机制和容错机制。错误处理机制用于确保任务的完整执行,
监控任务在传输过程或执行过程的具体运行情况,当任务执行失败中断后重新调度并重新
执行。
2. 面向多节点协同计算的任务调度方法
2.1 多节点环境下协同计算任务调度框架
本文提出的调度框架的执行过程可总结为以下步骤:(1)用户提交任务后,任务加入调
度器的等待队列。(2)预测器对任务进行分析,提供任务在各计算节点上的预计执行时间。
(3)控制器根据各计算节点的实时资源信息和网络信息作出任务分配决策。(4)任务追踪器对
需要进行计算卸载的任务,向对应的计算节点上的任务调度接收服务发起计算卸载。(5)任
务追踪器在计算节点上监控各任务的执行情况,并进行错误处理,如:对被中断的任务重
新发起调度和卸载执行过程。框架示意图如图 1 所示。
图 1 任务调度框架示意图
下载: 全尺寸图片 幻灯片
2.2 产生概率分布和预测值的方法
在上述任务调度框架中,预测器负责产生任务分配决策所需各变量的预估值。预测器
包含 1 个任务预测单元集合和 1 个节点预测单元集合。每个任务预测单元为 1 个或 1 组具
有类似软硬件配置的节点,负责维护已执行任务的时间分布信息。类似地,节点预测单元
为 1 个或 1 组具有类似网络环境的节点,负责记录和预估存留时间信息。
本文采用一种黑盒方法
[12]
来为每个任务产生概率分布和预测值。该方法假设大部分任
务与先前所有任务的某个子集类似,且类似任务有相似的执行时间。该方法不需要获取任
务的结构信息或用户预先提供的信息,但需要每个任务的属性集合。本文选用 3 个属性:
提交任务的镜像名、任务的 CPU 需求和任务的内存需求。对于每个属性-键值对,该方法
通过直方图跟踪所有具有相同属性和值的任务的执行时间并生成一个经验分布。每个属性-
键值对在直方图中由算法进行预估,数值类型包括:平均值、中值、衰减率为 0.5 的移动
平均值以及最近 20 个任务的平均值。同时在每次预估时维护 4 个点估计方法的归一化平均
绝对误差(Normalized Mean Absolute Error, NMAE)。当预估一个带有若干属性任务的执行
时间时,从所有属性-键值对应的直方图中比较所有点的估计值的 NMAE,选择最低
NMAE 对应的点估计值和执行时间分布。此外,本方法使用一个直方图以跟踪所有任务的
执行时间,用于预估平均任务执行时间。根据以上原理,每个任务预测单元为 1 个或 1 组
服务节点维护其任务执行时间的分布。同理,每个节点预测单元为 1 组服务节点维护其存
留时间的分布,但并不用区分多种属性维护存留时间的分布。
本方法采用一种基于流的直方图算法以构建直方图
[13]
。1 个直方图是 1 个键值对的集
合,作为 1 个实数集合的近似代表,表示为$\{\left({v}_{1},{f}_{1}\right),
\left({v}_{2},{f}_{2}\right), \cdots ,\left({v}_{B},{f}_{B}\right)\}$。对于每对
$ \left({v}_{i},{f}_{i}\right),1\le i\le $B$ ,{v}_{i} $表示 1 个数字的值,$ {f}_{i} $表示该数
字的频数。1 个直方图在生成时规定最大键数量 B,当新加入某个数值而导致直方图总键
数超过规定数量时,归并数值最近的两个键值对。
本方法定义了概率直方图的概念,表示为
$ \{\left({v}_{1},{p}_{1}\right),\left({v}_{2},{p}_{2}\right),\cdots ,\left({v}_{B},{p}_{B}\right
)\} $。对于每对$\left({v}_{i},{p}_{i}\right), 1\le i\le$B$ ,{v}_{i} $表示一个数字的值,
$ {p}_{i} $表示该数字的概率。因此,概率直方图是一个概率分布的近似代表。本方法新
增两个算法用以将直方图转换为概率直方图,如表 1 和表 2 所示。
表 1 右移和概率转换过程(算法 1)
输入:1 个直方图
$ \{\left({v}_{1},{f}_{1}\right),\left({v}_{2},{f}_{2}\right),\cdot
s ,\left({v}_{B},{f}_{B}\right)\} $,1 个位移
值$ \delta $
输出:1 个概率直方图
$\{\left({u}_{1},{p}_{1}\right),\left({u}_{2},{p}_{2}\right),\cdots
,\left({u}_{B},{p}_{B}\right)\} $
(1) set $S=\sum _{i= 1}^{B}{f}_{i} $
剩余14页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3959
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功