Page 289 - 《软件学报》2021年第12期

杨术 等:功能分发网络:基于容器的智能边缘计算平台 3953

略是:找到一个容器的子集和 C′⊆C,让 ∑ rc ( I p A ) ,并且 ∑ rc
()≤
() 是最大的.因此,找到最优的容器编排策略与
∈
cC′ cC′
∈
解决最大子集和问题是等价的. □
参考了文献[17]的做法,我们首先计算每个容器的优先级,并且用贪心的方式将每个容器编排到当前响应
最快、同时满足资源需求的集群上.我们根据子任务信息计算出每个子任务对应的容器的 score 值(也称为优先
级,它综合考虑了容器的数据依赖以及容器的执行时间等),并且按照 score 值的递减顺序形成一个容器列表.其
中,score 值的计算方式如下:
score ()c = t + c max c m succ∈ ()c { ( , )c cω m + score (c m )}.
平均计算时长越低,同时与其他节点通信代价越低的节点,它所在容器的 score 值就越高,并且 score 值越大,
说明它应该先被执行.在容器编排的过程中,算法会依次根据容器列表依次调度每一个容器,并根据计算时间编
排到响应最快的边缘计算集群.如果存在某个边缘计算集群的闲置资源无法满足容器的需要,那么算法会考虑
响应时间第二快的计算集群,判断它是否能容纳和运行当前的容器.以此类推,直到找到满足计算要求的边缘集
群为止.
基于启发式的容器编排算法具体细节见算法 1.
算法 1. Heu-Orche(J,P,C).
1. 初始化任务 J 的图结构,并将每个子任务对应到不同的容器;
2. 收集和计算每个容器的信息,并且计算它们的 score 值,并按照 score 值递减的顺序将它们进行排序,
存于 C={c 1 ,c 2 ,…,c m }中;
3. While 列表中存在未被编排的容器
4. 选出列表中的 score 值最小的第 1 个容器 c;
5. For p∈P
6. If r(c)≤I(p) then
7. 计算 EFT(c,p)值;
8. EndFor
9. 将 c 编排给 EFT 值最小的同时满足计算需求的集群;
10. EndWhile
11. 更新网络中的任务和闲置资源使用信息,并为下一轮编排做准备.
第 1 行、第 2 行是容器优先级计算过程.首先,在第 1 行,算法会先获取每个容器运行的计算量、资源需求
等,以及在每个集群的预计开始执行时间和完成执行时间等.接着,在第 2 行,算法会根据信息计算每个容器的
score 值,并按照 score 值的递减顺序依次对容器进行排序,并形成列表 C={c 1 ,c 2 ,…,c m },而接下来算法也会按照该
列表对它们进行调度.
接着是集群选择阶段.从第 3 行~第 10 行,算法不断选出列表中未被编排的容器计算出合适的编排策略,计
算方式则是采用贪心的方式,直到待编排容器列表为空.在第 4 行,算法每次都会选出列表中第 1 个未被编排的
容器 c 进行操作,并且会收集 c 的计算量和需求信息.从第 5 行~第 8 行,算法遍历所有可用的边缘计算集群,收集
所有集群的资源使用信息、集群间的传输代价以及用户与集群的延迟信息.第 6 行、第 7 行,对于每个集群 p,
算法首先会判断该集群当前是否满足容器的需求,也就是判断 r(c)是否小于等于 I(p):如果满足,算法会继续计
算容器 c 编排到该集群的预计完成执行时间 EFT(c,p);如果不满足,则直接跳到下一个集群进行判断.在遍历完
所有的集群后,算法会选择预计完成时间最小、并且满足容器计算需求的那个边缘计算集群,并把容器编排给
它,并更新网络的信息.最后,所有容器就会被贪心地编排到合适地边缘计算集群,并在第 11 行更新网络的信息.
定理 2. 算法 1 的时间复杂度为 O(n|E|).
证明:在第 2 行,算法需要考虑子任务间的数据依赖以及每个子任务在边缘计算集群的平均计算时间,因此,
第 2 行的时间复杂度为 O(n|E|).而从第 3 行~第 10 行为循环遍历过程,其时间复杂度为 O(mn).因此,算法 1 的时
间复杂度为 O(n|E|). □