能耗优化的流媒体传输任务调度研究

郝一鸣，付 雄

(南京邮电大学 计算机学院，江苏 南京 210003)

0 引 言

随着信息技术和网络技术的迅速发展，电信网、广播电视网、互联网三网在语音、数据、图像等综合多媒体的通信业务方面逐步融合，形成的三网融合使得智能电视得到极大的发展[1]。近年来，基于云计算构架的流媒体平台成为智能电视主流发展方向，利用云计算中的云存储技术为智能电视流媒体提供海量可扩展的存储空间，利用资源虚拟化技术实现计算资源的弹性可扩展[2]。在智能电视系统提供的视频播放服务中，与用户最直接相关的就是流媒体传输服务，对应的流媒体传输任务也是系统中占用资源最多的主要任务[3-4]。

随着视频点播业务越来越多，流媒体传输任务逐渐增长的访问量和数据规模会带来许多问题[5]。用户在进行点播视频的操作时，系统会收到请求并且在系统中建立与这一行为对应的流媒体传输任务，如果用户数量上升，流媒体传输任务的规模也会同时增加，负载流媒体传输任务的服务器集群的搭建与运行工作所带来的能源消耗成本也会随之提高[6-7]。在调度服务器执行流媒体传输任务时，能进行更为合理的调度和资源配置，就可以在一定程度上减少流媒体传输任务的服务器运维成本，从而改善智能电视系统的整体开销[8-9]。流媒体传输任务调度问题成为智能电视系统待解决的难题之一[10]，由于智能电视机系统多采用基于云计算的架构，当前云计算环境中的任务调度为此提供了一些思路[11]。如文献[12]将分组和动态优化技术结合来进行云环境中的资源调度，通过优化后的任务分组调度算法减少处理时间和成本，再根据资源的处理性能和开销动态分配虚拟机。目前任务调度问题的研究主要是在一些场景下针对某方面指标性能的优化和改进，在许多任务调度问题中已经取得了一定的优化效果，包括对执行时间、完成时间、截止时间、成本、负载均衡、资源利用率、能效比、吞吐量、安全性可靠性等的优化[13]，但针对能耗优化的流媒体传输任务调度问题还较少展开[14-15]。

针对上述能耗优化的流媒体任务调度问题，首先设计了任务调度问题模型，然后根据模型提出一种能耗优化的流媒体任务调度算法，计算流媒体传输任务的持续时间并根据时长选择调度，避免了长短任务随机散布在服务器中导致能耗浪费的情况。通过实验验证算法的性能与时间开销，在能耗上可以取得比较理想的效果，将能耗控制在理论能耗下限的130%左右。

1 流媒体传输任务调度问题描述

在流媒体传输任务中，通常待传输的流媒体任务可表示为M={t1,t2,…,tm}，其中ti表示第i个传输任务。每个任务对应的文件大小为Si，每个任务对应的客户端网络下行速率为vi，每个传输任务之间是相对独立的，分配和执行时都不存在相关性。一个同构的云服务器虚拟机集合VM={vm1,vm2,…,vmm}，其中vmi表示第i个服务器，Mi表示vmi上现在的任务，VM中有充足的虚拟机数量，每个可以最多稳定地同时执行b个流媒体传输任务。

在云计算中单个服务器的各方面资源都是有限的，所以每个服务器必然有一定的承载传输任务的数量上限，根据云服务器各自配置的系统资源规格可以计算出这个上限的数值。由于执行流媒体传输任务的同时还需要满足系统要求的服务质量，为了使所有传输任务都能稳定执行，此处b定义为满足服务质量要求的任务数上限。当一个虚拟机上存在至少一个传输任务时，该虚拟机现在正处于“运行”状态中，没有则置于“闲置”状态，闲置状态的能耗忽略不计。总体而言，相关流媒体传输任务可用图1所示的模型表示。

流媒体传输任务调度指将M分为n个不相交的子集Ti(i=1,2,…,n)，每个子集Ti代表将M中的这些任务分配到服务器vmi执行；分配后预估总能耗E，希望E尽可能小。能耗E可以通过式(1)进行计算，其中pi(t,Mi)表示t时刻服务器vmi的功率。这里将同构的服务器满载运行的功率看作1个功率单位，t时刻的功率与此时vmi上的任务Mi的关系见图1，使所有服务器处于“运行”状态时间的总和尽可能小从而降低总能耗E。

图1 流媒体传输任务调度问题模型

(1)

2 能耗优化的流媒体传输任务调度算法

视频点播系统中，因用户不同的使用场景会产生一些特征，从任务时长和数量的角度看，流媒体传输任务会呈现两极分化的特征，系统中会同时存在服务器时长非常短的大量任务和时长较长的极少量任务。在传统的数据中心服务器集群中，会将新产生的流媒体传输任务循环往复地分配到可以提供需要内容并且有空余负载量的服务器上，这样分配可以保证所有任务都能够及时得到处理。但同时这样的分配算法也意味着不同时长的任务将会随机地分配在各个服务器上，在任务逐渐执行的过程中，短任务会比长任务提前很多时间结束。倘若某个服务器在短任务执行完毕后没有及时得到新的任务分配，就会在一段时间内形成服务器被少量长任务占用，处于低负载却无法置于空闲的状况，根据低负载状态任务平均变高的现象，导致这一部分的服务器的使用效率降低，产生能耗浪费。为了避免这种情况，尽可能使少量高负载服务器执行同样数量的流媒体传输任务，需要通过调整流媒体传输任务调度的算法，提高每个服务器的利用效率，以达到减少整体能耗开销的目的。

根据上述分析，针对流媒体传输任务调度问题，文中提出了一种能耗优化的流媒体传输任务调度算法(streaming media transmission task scheduling algorithm，SMTTSA)。该算法的整体思路是：根据目标媒体的文件大小和客户端的下行网速计算近似的任务长度,并将所有用于流媒体传输任务的服务器按照这个时长分为长任务和短任务两类，然后再使用降序贪心算法将任务分配给对应类别服务器中最接近其稳定承载上限的。一旦出现完全空闲的服务器就将其置于空闲状态，等到再次需要的时刻唤醒。

该算法的主要步骤如下：首先需要根据每个任务请求传输流媒体文件的大小和发出请求的用户的下行网速计算每个任务的时间长度并按降序排列；接着按照服务器当前的负载状态将其分为三类：长任务服务器集合、短任务服务器集合、空闲服务器集合，再各自按照剩余可负载任务数量升序排列；然后开始对每个任务进行分配，先按长度分类再查询对应分类的服务器集合中是否存在可以负载的服务器，如果有就将这个任务分配到该服务器执行，如果没有就从空闲服务器中启用一个进行分配，并将该服务器加入对应的服务器集合。将所有任务分配完后算法结束，输出结果的任务调度方案。算法具体步骤如下所述：

Algorithm：能耗优化的流媒体传输任务调度算法。

Input:流媒体传输任务集合M={t1,t2,…};每个任务对应的文件大小S={s1,s2,…};每个任务对应的用户网络下行速率V={v1,v2,…};服务器虚拟机集合VM={vm1,vm2,…}；单个虚拟机的最大任务负载量b;虚拟机的当前任务负载量Bnow={bnow1,bnow2,…};长任务时间阈值tth。

1：forti∈M;ti=si/vi；

2：将M中元素按照ti降序重新排序;

3：/*将VM分为VMlong、VMshort和VMspare*/

4：for vmi∈VM：

5：bi=bmaxi-bnowi;

6：ifbnowi==0：

7：vmi→VMspare;

8：else if vmi上最长任务剩余时间大于tth:

9：vmi→VMlong;

10：else vmi→VMshort;

11：将VMlong、VMshort中元素按bi升序排序;

12：forti∈M:

13：ifti≥tth:

14：if存在vmj∈VMlong且bj>0:

15：ti→Tj,bj--;

16：else vmj→VMspare，ti→Tj，bj--，vmj→VMlong;

17：else if存在vmj∈VMshort且bj>0:

18：elsevmj→VMspare，ti→Tj，bj--，vmj→VMshort;

19：return {T1,T2,…}

3 实验及结果分析

本节将对算法SMTTSA的性能进行模拟测试和验证。将任务信息带入算法进行计算，并将其结果与理论值下限和GTSA[5]分别进行比较。GTSA调度算法是指按照任务请求原本的顺序，对每个任务按照服务器负载最低的原则进行贪心选择。

实验中假设流媒体传输任务的持续时间完全符合计算，不会出现速度不稳定、意外或是主动中断的情况。参照问题的描述，可以根据输入的条件计算得到能耗的理论下限值。根据已知的任务信息可以求出任务时长的总和，在理想状态下这些任务都能使运行的服务器达到极限的利用率，所以在这种情况下平均每个任务所产生的功率是一致的。设p0为一台服务器稳定满载的功率，总能耗的理论最小值可以用式(2)求得。理论最小能耗将作为两种算法调度后能耗的主要参考。实验中将p0设为与b相同的数值以方便计算统计，计算出的能耗值在数值上等于任务时长的总和。

(2)

每一组实验的过程是将相同的一批任务和相同条件的一批服务器信息输入，分别执行两种调度算法，输出调度方案并计算预计能耗结果。调度目标的服务器集合为一组10个，每个可以同时稳定负载的任务数量为20个任务。第一批流媒体任务数据200个，时长分布从30秒到3 000秒。服务器集合以完全空载的状态执行两种算法，输出的结果分别如图2和图3所示。柱状图中横坐标表示服务器的编号，柱体表示对应服务器上分配的任务，纵坐标为任务对应的时间秒数。

图2 第一组GTSA算法输出方案时长分布

图3 第一组SMTTSA算法输出方案时长分布

图4 调度算法能耗比较1

按照相同的方式使用共五组不同的数据集，根据五组任务计算两种算法输出方案的预计能耗和理论最小值，如图4所示。预计能耗的计算是算法输出方案中每个服务器预计处于“运行”状态的时长的总和。

保留第一次调度的结果，让所有服务器在模拟环境中运行600秒，再分别输入第二批流媒体任务数据100个，时长分布从30秒到3 000秒。这个过程是模拟系统运行过程中再次进行任务调度，并且任务数量减少的情况，两种算法输出的分配方案如图5和图6所示。

图5 第二组GTSA算法输出方案时长分布

图6 第二组SMTTSA算法输出方案时长分布

第二组模拟实验中的能耗理论值下限计算方式与第一组相同，将两批任务的理论值下限相加就可以得到全体任务的理论值下限。两组算法将中间运行过程的能耗计算出来之后，再统计第二批任务调度完毕时每个服务器上分配的任务情况计算之后预计能耗，求出全体的总能耗。图7是第二组模拟实验的能耗比较。

图7 调度算法能耗比较2

两组实验得到的能耗结果(图4、图7)，参照调度算法得到的预计能耗分别为理论值下限的396.89%和318.26%，文中提出的算法得到的能耗分别降低到了理论值下限的128.39%和130.65%，因此可以认为，算法在很大程度上把系统用在流媒体任务传输的能耗降低到一个比较理想的范围，起到了一定的节能作用。

4 结束语

视频点播系统中的流媒体任务调度是决定流媒体传输的性能和能耗的关键问题，文中定义了基于云计算架构的流媒体传输任务模型，根据此模型提出了一种能耗优化的流媒体传输任务调度算法。该算法根据预测任务时间长度区分不同类型的任务并分别分配到各自类型的节点执行，将碎片化的任务集中调度，让尽可能少的服务器以较高负载状态执行任务从而达到整体节能的目的。对比模拟实验的结果表明，该算法可在不影响服务质量的前提下对能耗起到一定的优化效果。