基于一种公平性的智能电视系统资源分配算法研究
邓源基（广州珠江数码集团股份有限公司，广州 510000）
摘要：本文着重介绍了DRF算法在嵌入式智能电视系统多资源公平分配中的具体应用情况，旨在通过DRF分配，使用户支配资源趋于均衡，以此提高系统性能，优化用户体验。
关键词：公平性；智能电视；系统资源；分配算法d o I：10.3969/J.ISSN.1672-7274.2017.08.007
中图分类号：TN94 文献标示码：A 文章编码：1672-7274（2017）08-0019-03
Research on Resource Allocation Algorithm of Intelligent TV System Based on Fairness
Deng Yuanji
(Guangzhou Digital Media Group Co., Ltd., Guangzhou, 510000)
Abstract: This paper focuses on the application of DRF algorithm in the multi resource fair allocation of embedded intelligent TV system，we hope to optimize the user experience by allocating the DRF to the user to make the resource more balanced, so as to improve the system performance.
Keywords: Fairness；smart TV; System resource; Allocation algorithm
1 引言
互联网时代，随着硬件技术不断应用与发展，智能终端成为人们生活中的必需品。以平板电视为中心的智能家居系统，在带给人们无限愉悦体验的同时，其作为一种便捷、交互式的嵌入式终端产品，在多任务语义环境下所承载的资源十分有限。用户要想展开多任务管理与运行，必然导致智能电视终端产生资源荷载过量与资源竞争状况，从而影响用户体验，降低系统运行性能。在此背景下，基于单资源最大公平、最小及比例公平和效用公平原则，对智能电视系统资源分配算法进行研究，可确保智能电视产品在面临多用户场景时，基于DRF算法对有限资源进行合理、公平分配，使系统总体运行性能和服务质量达到最优。
2 智能电视系统单资源分配算法的公平性
2.1 最大公平及最小公平按用户需求增长次序分配智能电视系统共享 支配资源；用户不会得到比其他需求更多的智能电视系统共享支配资源；一切尚未达到资源需求的用户，将得到公平的智能电视系统共享支配资源。在此分配原则下：假设用户个数为N；di为用户i的资源需求；wi为用户i资源需求相对应的权重；r为分配于N个用户的总资源量；用户i的资源需求矢量为[di]；用户i资源需求相对应的权重矢量为[wi]。则最大、最小公平性原则下，每位用户智能电视系统支配资源分配算法可表示为： 式中，ai为用户i所能获得的最大智能电视系统支配公平资源及最小公平支配资源。在系统资源分配过程中，通过以下FMMF伪代码分别输入用户智能电视系统支配资源需求矢量[di]及用户i资源需求相对应的权重矢量[wi]和分配于n个用户的总资源量R，最终即可输出用户i所能获得的最大智能电视系统支配公平资源及最小公平支配资源分配矢量[ai]。FMMF(R, d, w)
2.2 效用最大公平及最小公平
以平板电视为中心的智能家居系统应用程序弹
性流会有如图1a所示的凸效用函数；以平板电视为中心的智能家居系统视频和音频实时流会有如图1b
所示最低要求的效用函数；以平板电视为中心的智
能家居系统自适应速率效用分化函数会有如图1c所
示的曲线拐点。
效用最大及最小公平原则下，假设用户i所能获得的智能电视系统资源总量为R，用户i的资源需求向量为[di]，用户i的资源需求相对应的权重向量为[WI]，基于上述三种效用分配函数FUMMF，每位用户所能获得的智能电视系统资源分配向量[ai]可表示为
[ ai ]= FUMMF ( R; [ di ]; [ wi ]) （2）
2.3 比例公平
最大及最小和效用公平原则下，有更多优先权的用户一般资源需求量少，而在比例公平原则下，资源需求少的用户优先权更少[1]。
对此，假设ai为用户i的资源分配量，要使用户
所能获得的智能电视系统资源总量最大，须保证全部用户总效用分配函数FUMMF的值为∑N log a i=1 i
结合上述最大及最小公平和效用公平原则，智能电视系统资源比例公平分配算法也可以表示为
3 智能电视系统多资源分配算法的公平性及算法实例分析
随着智能家居系统的多样化，相关学者对智能电视系统资源分配算法的研究还主要集中于单资源类型环境下，但用户一旦具有异构资源需求，就需基
于Hadoop和dryad两种集群计算框架对多资源类型环境下，不同用户智能电视系统资源公平分配算法
进行分析。对此，本文试图通过DRF多资源场景，力图最大化所有用户智能家居系统的最小支配份额。
DRF分配算法的优点在于以插槽为粒度高度
重视视智能电视系统异构用户需求。通过如图2所
示不同用户集群任务需求和插槽比之间的关系，在用户需求与系统异构资源之间形成良好的匹配，提高智能电视系统多资源分配效率。
结合上述理论，本文将智能电视系统资源分配算法转化为多资源、异构环境下最大及最小公平的最优分配策略问题：
假设以平板电视为中心的智能家居系统分别包
括2个用户、9个CPU、18GB RAM。其中，用户A和B单运行任务分别需要获得资源量为<1CPU，4GB RAM>和<3CPUS，1GB RAM>。则基于公平原则，
可通过激励共享、防止策略性操纵、无嫉妒性及帕
累托最优四大属性指导制定公平分配策略[2]。
由于在单资源环境下，智能电视系统资源分配算法满足上述四大特性，但按照微观经济学帕累托最优原理，在多资源和异构用户需求环境下
首选的智能电视系统资源分配机制“Competitive Equilibrium from Equal Incomes ”无法保证用户单个资源之间不产生策略性操纵行为。对此，
本文还分别考虑了“Single resource fairness”， “Resource monotonicity ”，“Bottleneck fairness”，“population monotonicity”四种平板智能电视系统资源分配算法特性，从而提出如图3
所示的用户资源分配方案。
（1）在图3分配方案中，用户A平板智能电视系统单任务需消耗CPU和总内存，故用户A平板智能电视系统支配资源为内存。
（2）用户B平板智能电视系统单任务需消耗总CPU和总内存，故用户B平板智能电视系统支配资 源是CPU。
如图3所示，基于DRF公平分配策略会均衡用
户平板智能电视系统资源分配。其中，用户A平板智能电视系统3个任务共消耗的有效资源为<3CPUS， 12GB RAM>；用户B平板智能电视系统2个任务共消耗的有效资源为<6CPUS，2GB RAM>；在此资源分配过程中，每位用户都会得到相同的平板智能电视系
统资源分配，用户A和用户B分别获得RAM和CPU。上述分配方案可通过数学分配算法加以计算：
假设，x，y是DRF分配于平板智能电视系统用户A、B的任务数，A用户消耗的资源量为<XCPU， 4XGB RAM>；B用户消耗的资源量为<3YCPU， YGB RAM>，公平原则下A、B用户消耗的平板智能电视系统资源等同；则A用户的资源支配占有率=4X/18，B用户的资源支配占有率=3Y/9。所以，DRF分配算法可表示为
max(x，y) （分配最大化）
Subject to x+3y≤9 （CPU约束）
4x+y≤18 （内存约束） 2x y
= （支配占有率等同） 9 3 通过计算求解可得x=3，y=2。所以，A用户最终所获得的平板智能电视系统资源总量为<3CPUS ，12GB RAM>，B用户最终所获得的平板智能电视系统资源总量为<6CPUS， 2GB RAM>。
4 结束语
综上所述，基于一种公平性的智能电视系统资源分配算法分析，需充分考虑单资源和多资源用户异构环境下的资源匹配与公平性问题。本文基于最大、最小及效用最大最小和比例公平原则，分别分析了单资源与多资源环境下智能平板电视系统资源分配算法，经过DRF资源分配算法计算，A、B两个用户所获得的总资源分配量达到均衡。■
参考文献
[1] 徐超，曾学文，郭志川．一种智能电视终端在线自适应多资源调度方
法[J]．计算机应用研究，2015,32(03):697-700
[2] 李青，何大治，管云峰，殷惠清．一种适合数字电视上行信道的资源
分配方法[J]．电视技术，2015,39(11):94-98