一种公平性的智能电视系统资源分配算法

陈俊杰,周 晖,张小美

(南通大学电子信息学院,江苏南通 226019)

一种公平性的智能电视系统资源分配算法

陈俊杰,周 晖,张小美

(南通大学电子信息学院,江苏南通 226019)

针对智能电视系统资源分配问题,提出一种基于非线性弹性任务模型的资源分配算法.首先,定义任务间服务质量水平的公平性,并描述基于公平性的智能电视系统资源分配问题;然后,引入非线性弹性任务模型,提出利用简单迭代法求解资源分配,并且推导出简单迭代法收敛的充分条件;进一步把非线性弹性任务模型应用到公平共享自适应控制器.仿真实验结果表明,基于非线性弹性任务模型的资源分配算法能够获得近似公平的资源分配,并且与现有算法相比,收敛速度更快.

资源分配;公平性;非线性弹性任务;迭代法

作为嵌入式终端,智能电视系统资源十分有限,同时智能电视系统需要支持多任务并行执行,这必然导致系统中资源过载,引起任务间的资源竞争,从而影响部分应用的执行,降低用户的体验质量.对于弹性应用,可以根据分配的资源数量,调整任务的执行,获得不同的服务质量.例如,可伸缩视频解码任务是典型的弹性应用,可以根据资源分配,解码基本层和不同的增强层,获得不同的分辨率、帧率以及信噪比.因此,在智能电视系统中,需要对有限的资源进行合理的分配.

传统的资源分配问题以系统整体效用的最大化为优化目标.文献[1]提出了一种基于服务质量(Quality of Service,QoS)的资源分配模型Q-RAM,旨在满足应用最小需求的条件下最大化系统整体效用.文献[2]将智能电视系统资源分配问题建模为多维多选择背包问题,提出了一种启发式算法,能够在较短时间内获得近似最优的资源分配.文献[3]假设资源消耗函数是凸函数,将多资源分配问题建模为凸优化问题,并且提出了一种基于定价机制的多资源分配算法.

在资源分配过程中,还需要兼顾资源分配的公平性.基于公平性的资源分配问题在诸多领域都得到了广泛关注,诸如最大最小公平性和比例公平性已经得到了广泛应用.文献[4]引入了支配资源的概念,提出了支配资源的公平性(Dominant Resource Fairness,DRF),将最大最小公平性推广至数据中心的多资源分配问题.文献[5]以支配资源的概念为基础,将公理性的公平性指标应用于多资源分配,并且实现了效率与公平性之间的权衡.文献[6]将DRF进行推广,用于异构云计算系统的资源分配.文献[7]在DRF算法的基础上,提出了基于信誉因子的增强公平性分配算法.

文献[8]阐明了基于效用的资源分配的公平性概念.文献[9]采用公理性议价理论中卡莱-斯莫罗廷斯基议价解定义了质量公平的资源分配,提出了基于二分搜索的求解方法.文献[10]定义了任务间服务质量水平的公平性,提出了一种自适应的服务质量控制器,采用反馈控制结构,基于每个任务当前服务质量水平与其平均值的偏差搜寻公平的服务质量水平.随后,文献[11]又提出了基于神经网络比例积分微分控制(Proportional-Integral and Derivatice control,PID)的自适应资源分配算法.

笔者定义了任务间服务质量水平的公平性,在此基础上描述基于公平性的智能电视系统资源分配问题.引入非线性弹性任务模型,提出利用简单迭代法求解资源分配问题,并且推导出简单迭代法收敛的充分条件;进一步把非线性弹性任务模型应用到公平共享自适应控制器.与现有算法相比,笔者所提出的资源分配算法收敛速度更快,更加适用于实时系统.

1　智能电视系统资源分配问题

1.1资源和任务集

考虑一个实时系统,其解码任务集Γ={τ1,τ2,…,τn},中央处理器(Central Processing Unit,CPU)带宽容量为R,由任务集中的n个任务共享.任务τi能够以不同的复杂度执行,CPU带宽需求也不尽相同.

令ri(ri∈R+)为分配给任务τi的CPU带宽,利用分配的CPU带宽,τi获得的服务质量水平为LQoSi(LQoSi∈R+).通过给τi分配更多的CPU带宽来提高LQoSi.分配的CPU带宽ri和服务质量水平LQoSi之间的关系可以通过单调递增的服务质量函数描述.

在这种情况下,任务τi具有最小的服务质量需求和最大的服务质量需求,即LQoSimin和LQoSimax,其中表示τi可接受的最差服务质量水平,表示τi可获得的最佳服务质量水平.因而,对每个任务假设L QoSimin≤L QoSi≤L QoSimax.

每个任务τi根据其相对重要性分配不同的权重wi(wi∈R+),其中较大的wi表示τi在任务集{τ1,τ2,…,τn}中比较重要.

1.2服务质量水平的公平性

在实时系统中,资源分配可能会导致不公平.例如,任务τ1和τ2具有相同重要性,给τ1和τ2分配相同的CPU带宽,τ1以其最大服务质量水平执行,而τ2以最小服务质量水平执行.一般来说,LQoSi的范围与具体任务τi有关.另外,如果τ1比τ2更重要,那么相比τ2,τ1应该以更好的性能执行.为了定义这种公平性,下面介绍每个任务τi归一化的服务质量水平Qi:

这个术语代表执行结果的满意率,Qi在[0,1]上随着ri单调递增.Qi=0,表示τi以其最小服务质量水平执行;Qi=1,表示τi以其最大服务质量水平执行.每个任务τi依据其重要性分配一个权重wi,服务质量水平的加权公平性定义如下.

服务质量水平的公平性:假设分配给任务τi的CPU带宽为ri,Qi和wi分别表示τi归一化的服务质量水平和重要性权重.如果下列公式成立,那么获得公平的资源分配:

下面将Qi简称为任务τi的服务质量水平.

1.3资源利用率和服务质量水平

通过服务质量函数ϕi:[rimin,rimax]→[0,1]描述分配的CPU带宽ri和服务质量水平Qi之间的关系,其中ϕi(ri)表示分配的CPU带宽为ri时τi的服务质量水平.

一般地,使用归一化的CPU带宽利用率Ui=riR,Ui表示分配给任务τi的CPU带宽.服务质量函数可以表示为ϕi:[Uimin,Uimax]→[0,1],其中Uimin=riminR,表示τi以可接受的最小服务质量水平执行时分配的CPU带宽利用率;Uimax=rimaxR,表示τi以可获得的最大服务质量水平LQoS执行时分配的

imaxCPU带宽利用率.任务τi在执行时实际的CPU带宽利用率Ui在区间[Uimin,Uimax]上.

1.4目 标

基于公平性的资源分配问题旨在最大化每个任务的服务质量水平,同时满足服务质量水平的加权公平性和CPU带宽约束,即

2　基于非线性弹性任务模型的资源分配算法

2.1非线性弹性任务模型

令Xi=Ui-Uimin,表示分配给任务τi的额外CPU带宽利用率,此时τi加权的服务质量水平定义为Qwi=Qiwi.定义任务τi的弹性系数为

其中,gi:[0,Uimax-Uimin]→R+.任务τi的弹性系数依赖于分配的额外CPU带宽利用率,这样的任务是一个非线性弹性任务.

令Γf为CPU带宽利用率固定为最大值Uimax的任务集合,Γv为CPU带宽利用率小于最大值Uimax的任务集合.如果任务τi的弹性系数是一个正常数Ei,那么τi∈Γv的CPU带宽利用率Ui为

下面讨论一个简单的数值方法.首先假设所有任务属于集合Γv,然后放宽该假设得到完整的算法,确定在Γf非空的情况下所有任务的CPU带宽利用率.

令X=[X1,X2,…,Xn]T∈,函数G:定义为

因而,如果不动点渐进稳定,则可以通过下列迭代公式进行求解:

注意到应用牛顿法求解式(7)需要计算函数G的微分,而通过式(8)求解不动点不需要计算函数G的微分.因而,简单迭代法比牛顿法更简单.

定理1 如果∀Xj∈[0,Ujmax-Ujmin],,其中fj(Xj)=XjQj,那么不动点渐近稳定.

得到

根据定理2给出的迭代序列{X(k)}的误差估计式,在给定精度ε＞0后,要使,只要计算到即可.在实际应用中,使用小于某个充分小的数作为迭代终止条件.

2.2公平共享自适应控制器

弹性任务模型灵感来源于串联弹簧系统,弹性任务的CPU带宽利用率对应弹簧的拉伸长度,加权的服务质量水平Qwi对应弹簧系统的力.对每个任务τi,下列关系成立:

式(10)是加权的服务质量水平随CPU带宽利用率的变化特性.

为了实现CPU带宽的公平共享,笔者提出公平共享自适应控制器,使用基于非线性弹性任务模型的资源分配算法分配CPU带宽.包含公平共享自适应控制器的实时系统结构如图1所示,它包含基本调度器、公平共享自适应控制器和监视器.基本调度器根据公平共享自适应控制器分配给每个任务的CPU带宽对任务进行调度,通常采用的调度算法包括单调速率调度算法和最早截止期优先调度算法.监视器用于评估任务的服务质量水平,并且将结果反馈给公平共享自适应控制器.当任务集Γ改变时,触发公平共享自适应控制器执行资源分配算法.

图1　实时系统结构

假设控制器知道任务τi所需CPU带宽利用率的最小值Uimin和最大值Uimax.控制器在执行资源分配算法时面临两种情况,第1种情况是控制器知道τi的非线性弹性函数gi,在这种情况下可以直接应用笔者所提出的算法;第2种情况是控制器不知道τi的非线性弹性函数gi,在这种情况下利用分配的CPU带宽利用率Ui和服务质量水平Qi,估计非线性弹性函数gi的当前值Gi如下:

因此,资源分配算法的执行过程为:在迭代之前,控制器给每个任务τi分配初始CPU带宽利用率Ui(0);在第k次迭代时,控制器从监视器得到每个任务τi(τi∈Γv)的服务质量水平Qi(k-1),利用式(11)估计弹性系数Gi(k-1),更新τi的CPU带宽利用率Ui(k)为

由定理1知,如果所有任务τi满足,那么当k趋于无穷时,更新的CPU带宽利用率收敛到公平共享.公平共享自适应控制器的算法总结如下:

for(任务集Γv中每个任务τi){

从监视器得到其服务质量水平Qi;

根据式(11)估计非线性弹性函数gi的当前值Gi;

}

for(任务集Γv中每个任务τi)根据式(12)更新每个任务的CPU带宽利用率;

返回每个任务的CPU带宽利用率Ui;

}.

3　仿真实验

通过仿真实验分析基于非线性弹性任务模型的CPU带宽分配算法.算法的性能指标主要包括算法运行时间、CPU带宽分配的公平性,其中算法运行时间通过平均迭代次数来衡量.

考虑一个包含4个解码任务的实时系统,解码的视频序列分别为Silent,Stefan,Coastguard,Foreman,利用H.264编码器获得每个解码任务的服务质量函数[11].为了方便起见,假设4个解码任务具有相同的权重,同时基本调度器采用最早截止期优先调度算法.

图2　任务的加权服务质量水平和迭代次数的关系

图3　迭代误差随迭代次数的变化趋势

如图2所示,随着迭代次数的增加,所有任务的加权服务质量水平趋于一致,在大约迭代8次之后,获得近似公平的CPU带宽分配.在图3中,比较了笔者所提出的算法与基于K-S议价解的资源分配算法[9]及基于神经网络PID控制的资源分配算法[12]的性能.从图中可以看出,随着迭代次数的增加,3种算法的迭代误差均呈指数级减小,并且与另外两种算法相比,笔者所提出的算法迭代误差下降更快,性能更佳.

接下来考察任务数对算法性能的影响.随机生成300个任务集,使用笔者所提出的算法确定公平的资源分配,统计不同任务数所需的平均迭代次数.任务数与平均迭代次数的关系如图4所示.从图中可以看出,随着任务数的增加,所需的平均迭代次数逐渐减小.这是因为收敛速度与当前迭代点的加权服务质量水平以及弹性系数的变化率有关,任务数越大,不动点附近的加权服务质量水平越小,因而收敛也就越快.

图4　平均迭代次数和任务数的关系

4　总 结

笔者定义了任务间服务质量水平的公平性,在此基础上描述了基于公平性的智能电视系统资源分配问题.引入非线性弹性任务模型,提出了利用简单迭代法求解资源分配,并且推导出简单迭代法收敛的充分条件;进一步把非线性弹性任务模型应用到公平共享自适应控制器.仿真实验结果表明,基于非线性弹性任务模型的资源分配算法能够获得近似公平的资源分配,并且与现有算法相比,收敛速度更快.

[1]RAJKUMAR R,LEE C,LEHOCZKY J,et al.A Resource Allocation Model for QoS Management[C]//Proceedings of Real-time Systems Symposium.Los Alamitos:IEEE,1997:298-307.

[2]王海威,倪宏,孙鹏,等.具有用户体验保障的资源优化分配算法[J].小型微型计算机系统,2012,33(7):1551-1556. WANG Haiwei,NI Hong,SUN Peng,et al.Qo E Guaranteed Resource Allocation Algorithm[J].Journal of Chinese Computer Systems,2012,33(7):1551-1556.

[3]陈俊杰,倪宏,孙鹏.采用定价机制的多媒体系统多资源分配算法[J].西安交通大学学报,2012,46(6):98-103. CHEN Junjie,NI Hong,SUN Peng.Pricing Mechanism Based Multi-resource Allocation for Multimedia System[J]. Journal of Xi’an Jiaotong University,2012,46(6):98-103.

[4]GHODSI A,ZAHARIA M,HINDMAN B,et al.Dominant Resource Fairness:Fair Allocation of Multiple Resource Types[C]//Proceedings of NSDI.Boston:USENIX,2011:24-37.

[5]JOE-WONG C,SEN S,LAN T,et al.Multi-resource Allocation:Fairness-efficiency Tradeoffs in a Unifying Framework[J]. IEEE/ACM Transactions on Networking,2013,21(6):1785-1798.

[6]WANG W,LI B,LIANG B.Dominant Resource Fairness in Cloud Computing Systems with Hetero-Geneous Servers [C]//Proceedings of IEEE Conference on Computer Communications.Piscataway:IEEE,2014:583-591.

[7]卢笛,马建峰,王一川,等.云计算下保障公平性的多资源分配算法[J].西安电子科技大学学报,2014,41(3): 162-168. LU Di,MA Jianfeng,WANG Yichuan,et al.Enhanced Fairness-based Multi-resource Allocation Algorithm for Cloud Computing[J].Journal of Xidian University,2014,41(3):162-168.

[8]LEE C,LEHOCZKY J,RAJKUMAR R,et al.On Quality of Service Optimization with Discrete QoS Options[C]// Proceedings of 5th IEEE Real-time Technology and Applications Symposium.Washington:IEEE,1999:276-286.

[9]MASTRONARDE N,van der SCHAAR M.A Bargaining Theoretic Approach to Quality-fair System Resource Allocation for Multiple Decoding Tasks[J].IEEE Transactions on Circuits and Systems for Video Technology,2008,18(4):453-466.

[10]HARADA F,USHIO T,NAKAMOTO Y.Adaptive Resource Allocation Control for Fair QoS Management[J].IEEE Transactions on Computers,2007,56(3):344-357.

[11]SU S C,van der SCHAAR M.On the Application of Game-theoretic Mechanism Design for Resource Allocation in Multimedia Systems[J].IEEE Transactions on Multimedia,2008,10(6):1197-1207.

[12]林军,倪宏,孙鹏,等.一种采用神经网络PID控制的自适应资源分配方法[J].西安交通大学学报,2013,47(4): 112-117. LIN Jun,NI Hong,SUN Peng,et al.Adaptive Resource Allocation Based on Neural Network PID Control[J].Journal of Xi’an Jiaotong University,2013,47(4):112-117.

(编辑:郭 华)

Fair resource allocation algorithm for the smart TV system

CHEN Junjie,ZHOU Hui,ZH ANG Xiaomei
(School of Electronics and Information,Nantong Univ.,Nantong 226019,China)

In order to address the resource allocation problem of the smart TV system,a resource allocation algorithm based on the nonlinear elastic task model is proposed.First,we define fairness of QoS levels and describe the fair resource allocation problem of the smart TV system.Then,based on the nonlinear elastic task model,a fixed-point iteration method is used to solve the resource allocation problem and a sufficient condition for the convergence of the method is derived.Finally,nonlinear elastic task model is applied to the adaptive fair sharing controller.Simulation results show that the proposed algorithm can obtain fair resource allocation with a faster convergence speed than existing algorithms.

resource allocation;fairness;nonlinear elastic task;iterative methods

TP37

A

1001-2400(2016)05-0139-08

10.3969/j.issn.1001-2400.2016.05.025

2015-06-25 网络出版时间:2015-12-10

国家自然科学基金资助项目(61174065);江苏省高校自然科学研究资助项目(15KJD520002);南通市应用研究计划资助项目(BK2014063)

陈俊杰(1985-),男,讲师,博士,E-mail:cjjcy@ntu.edu.cn.

网络出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.050.html