鄧源基

（廣州珠江數(shù)碼集團(tuán)股份有限公司，廣州 510000）

基于一種公平性的智能電視系統(tǒng)資源分配算法研究

鄧源基

（廣州珠江數(shù)碼集團(tuán)股份有限公司，廣州 510000）

本文著重介紹了DRF算法在嵌入式智能電視系統(tǒng)多資源公平分配中的具體應(yīng)用情況，旨在通過DRF分配，使用戶支配資源趨于均衡，以此提高系統(tǒng)性能，優(yōu)化用戶體驗(yàn)。

公平性；智能電視；系統(tǒng)資源；分配算法

1 引言

互聯(lián)網(wǎng)時代，隨著硬件技術(shù)不斷應(yīng)用與發(fā)展，智能終端成為人們生活中的必需品。以平板電視為中心的智能家居系統(tǒng)，在帶給人們無限愉悅體驗(yàn)的同時，其作為一種便捷、交互式的嵌入式終端產(chǎn)品，在多任務(wù)語義環(huán)境下所承載的資源十分有限。用戶要想展開多任務(wù)管理與運(yùn)行，必然導(dǎo)致智能電視終端產(chǎn)生資源荷載過量與資源競爭狀況，從而影響用戶體驗(yàn)，降低系統(tǒng)運(yùn)行性能。在此背景下，基于單資源最大公平、最小及比例公平和效用公平原則，對智能電視系統(tǒng)資源分配算法進(jìn)行研究，可確保智能電視產(chǎn)品在面臨多用戶場景時，基于DRF算法對有限資源進(jìn)行合理、公平分配，使系統(tǒng)總體運(yùn)行性能和服務(wù)質(zhì)量達(dá)到最優(yōu)。

2 智能電視系統(tǒng)單資源分配算法的公平性

2.1 最大公平及最小公平

按用戶需求增長次序分配智能電視系統(tǒng)共享支配資源；用戶不會得到比其他需求更多的智能電視系統(tǒng)共享支配資源；一切尚未達(dá)到資源需求的用戶，將得到公平的智能電視系統(tǒng)共享支配資源。在此分配原則下：假設(shè)用戶個數(shù)為N；di為用戶i的資源需求；wi為用戶i資源需求相對應(yīng)的權(quán)重；R為分配于N個用戶的總資源量；用戶i的資源需求矢量為[di]；用戶i資源需求相對應(yīng)的權(quán)重矢量為[wi]。則最大、最小公平性原則下，每位用戶智能電視系統(tǒng)支配資源分配算法可表示為：

式中，ai為用戶i所能獲得的最大智能電視系統(tǒng)支配公平資源及最小公平支配資源。在系統(tǒng)資源分配過程中，通過以下FMMF偽代碼分別輸入用戶智能電視系統(tǒng)支配資源需求矢量[di]及用戶i資源需求相對應(yīng)的權(quán)重矢量[wi]和分配于N個用戶的總資源量R，最終即可輸出用戶i所能獲得的最大智能電視系統(tǒng)支配公平資源及最小公平支配資源分配矢量[ai]。

2.2 效用最大公平及最小公平

以平板電視為中心的智能家居系統(tǒng)應(yīng)用程序彈性流會有如圖1a所示的凸效用函數(shù)；以平板電視為中心的智能家居系統(tǒng)視頻和音頻實(shí)時流會有如圖1b所示最低要求的效用函數(shù)；以平板電視為中心的智能家居系統(tǒng)自適應(yīng)速率效用分化函數(shù)會有如圖1c所示的曲線拐點(diǎn)。

圖1 效用最大及最小公平下智能電視系統(tǒng)資源分配算法效用函數(shù)

效用最大及最小公平原則下，假設(shè)用戶i所能獲得的智能電視系統(tǒng)資源總量為R，用戶i的資源需求向量為[di]，用戶i的資源需求相對應(yīng)的權(quán)重向量為[wi]，基于上述三種效用分配函數(shù)FUMMF，每位用戶所能獲得的智能電視系統(tǒng)資源分配向量[ai]可表示為

2.3 比例公平

最大及最小和效用公平原則下，有更多優(yōu)先權(quán)的用戶一般資源需求量少，而在比例公平原則下，資源需求少的用戶優(yōu)先權(quán)更少[1]。

結(jié)合上述最大及最小公平和效用公平原則，智能電視系統(tǒng)資源比例公平分配算法也可以表示為

3 智能電視系統(tǒng)多資源分配算法的公平性及算法實(shí)例分析

隨著智能家居系統(tǒng)的多樣化，相關(guān)學(xué)者對智能電視系統(tǒng)資源分配算法的研究還主要集中于單資源類型環(huán)境下，但用戶一旦具有異構(gòu)資源需求，就需基于Hadoop和Dryad兩種集群計算框架對多資源類型環(huán)境下，不同用戶智能電視系統(tǒng)資源公平分配算法進(jìn)行分析。對此，本文試圖通過DRF多資源場景，力圖最大化所有用戶智能家居系統(tǒng)的最小支配份額。

圖2 智能電視系統(tǒng)多資源分配中任務(wù)需求與單位插槽資源關(guān)系圖

DRF分配算法的優(yōu)點(diǎn)在于以插槽為粒度高度重視視智能電視系統(tǒng)異構(gòu)用戶需求。通過如圖2所示不同用戶集群任務(wù)需求和插槽比之間的關(guān)系，在用戶需求與系統(tǒng)異構(gòu)資源之間形成良好的匹配，提高智能電視系統(tǒng)多資源分配效率。

結(jié)合上述理論，本文將智能電視系統(tǒng)資源分配算法轉(zhuǎn)化為多資源、異構(gòu)環(huán)境下最大及最小公平的最優(yōu)分配策略問題：

假設(shè)以平板電視為中心的智能家居系統(tǒng)分別包括2個用戶、9個CPU、18GB RAM。其中，用戶A和B單運(yùn)行任務(wù)分別需要獲得資源量為＜1CPU，4GB RAM＞和＜3CPUs，1GB RAM＞。則基于公平原則，可通過激勵共享、防止策略性操縱、無嫉妒性及帕累托最優(yōu)四大屬性指導(dǎo)制定公平分配策略[2]。

由于在單資源環(huán)境下，智能電視系統(tǒng)資源分配算法滿足上述四大特性，但按照微觀經(jīng)濟(jì)學(xué)帕累托最優(yōu)原理，在多資源和異構(gòu)用戶需求環(huán)境下首選的智能電視系統(tǒng)資源分配機(jī)制“Competitive Equilibrium from Equal Incomes”無法保證用戶單個資源之間不產(chǎn)生策略性操縱行為。對此，本文還分別考慮了“Single resource fairness”，“Resource monotonicity”，“Bottleneck fairness”，“Population monotonicity”四種平板智能電視系統(tǒng)資源分配算法特性，從而提出如圖3所示的用戶資源分配方案。

圖3 用戶智能電視系統(tǒng)多資源分配方案

（1）在圖3分配方案中，用戶A平板智能電視系統(tǒng)單任務(wù)需消耗CPU和總內(nèi)存，故用戶A平板智能電視系統(tǒng)支配資源為內(nèi)存。

（2）用戶B平板智能電視系統(tǒng)單任務(wù)需消耗總CPU和總內(nèi)存，故用戶B平板智能電視系統(tǒng)支配資源是CPU。

如圖3所示，基于DRF公平分配策略會均衡用戶平板智能電視系統(tǒng)資源分配。其中，用戶A平板智能電視系統(tǒng)3個任務(wù)共消耗的有效資源為＜3CPUs，12GB RAM＞；用戶B平板智能電視系統(tǒng)2個任務(wù)共消耗的有效資源為＜6CPUs，2GB RAM＞；在此資源分配過程中，每位用戶都會得到相同的平板智能電視系統(tǒng)資源分配，用戶A和用戶B分別獲得RAM和CPU。上述分配方案可通過數(shù)學(xué)分配算法加以計算：

假設(shè)，x，y是DRF分配于平板智能電視系統(tǒng)用戶A、B的任務(wù)數(shù)，A用戶消耗的資源量為＜xCPU，4xGB RAM＞；B用戶消耗的資源量為＜3yCPU，yGB RAM＞，公平原則下A、B用戶消耗的平板智能電視系統(tǒng)資源等同；則A用戶的資源支配占有率=4x/18，B用戶的資源支配占有率=3y/9。所以，DRF分配算法可表示為

通過計算求解可得x=3，y=2。

所以，A用戶最終所獲得的平板智能電視系統(tǒng)資源總量為＜3CPUs，12GB RAM＞，B用戶最終所獲得的平板智能電視系統(tǒng)資源總量為＜6CPUs，2GB RAM＞。

4 結(jié)束語

綜上所述，基于一種公平性的智能電視系統(tǒng)資源分配算法分析，需充分考慮單資源和多資源用戶異構(gòu)環(huán)境下的資源匹配與公平性問題。本文基于最大、最小及效用最大最小和比例公平原則，分別分析了單資源與多資源環(huán)境下智能平板電視系統(tǒng)資源分配算法，經(jīng)過DRF資源分配算法計算，A、B兩個用戶所獲得的總資源分配量達(dá)到均衡。

[1] 徐超，曾學(xué)文，郭志川．一種智能電視終端在線自適應(yīng)多資源調(diào)度方法[J]．計算機(jī)應(yīng)用研究，2015,32(03):697-700

[2] 李青，何大治，管云峰，殷惠清．一種適合數(shù)字電視上行信道的資源分配方法[J]．電視技術(shù)，2015,39(11):94-98

Research on Resource Allocation Algorithm of Intelligent TV System Based on Fairness

Deng Yuanji
(Guangzhou Digital Media Group Co., Ltd., Guangzhou, 510000)

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.

Fairness；Smart TV; System resource; Allocation algorithm

10.3969/J.ISSN.1672-7274.2017.08.007

TN94文獻(xiàn)標(biāo)示碼：A

1672-7274（2017）08-0019-03