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

陳俊杰,周 暉,張小美

(南通大學(xué)電子信息學(xué)院,江蘇南通 226019)

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

陳俊杰,周 暉,張小美

(南通大學(xué)電子信息學(xué)院,江蘇南通 226019)

針對(duì)智能電視系統(tǒng)資源分配問(wèn)題,提出一種基于非線性彈性任務(wù)模型的資源分配算法.首先,定義任務(wù)間服務(wù)質(zhì)量水平的公平性,并描述基于公平性的智能電視系統(tǒng)資源分配問(wèn)題;然后,引入非線性彈性任務(wù)模型,提出利用簡(jiǎn)單迭代法求解資源分配,并且推導(dǎo)出簡(jiǎn)單迭代法收斂的充分條件;進(jìn)一步把非線性彈性任務(wù)模型應(yīng)用到公平共享自適應(yīng)控制器.仿真實(shí)驗(yàn)結(jié)果表明,基于非線性彈性任務(wù)模型的資源分配算法能夠獲得近似公平的資源分配,并且與現(xiàn)有算法相比,收斂速度更快.

資源分配;公平性;非線性彈性任務(wù);迭代法

作為嵌入式終端,智能電視系統(tǒng)資源十分有限,同時(shí)智能電視系統(tǒng)需要支持多任務(wù)并行執(zhí)行,這必然導(dǎo)致系統(tǒng)中資源過(guò)載,引起任務(wù)間的資源競(jìng)爭(zhēng),從而影響部分應(yīng)用的執(zhí)行,降低用戶(hù)的體驗(yàn)質(zhì)量.對(duì)于彈性應(yīng)用,可以根據(jù)分配的資源數(shù)量,調(diào)整任務(wù)的執(zhí)行,獲得不同的服務(wù)質(zhì)量.例如,可伸縮視頻解碼任務(wù)是典型的彈性應(yīng)用,可以根據(jù)資源分配,解碼基本層和不同的增強(qiáng)層,獲得不同的分辨率、幀率以及信噪比.因此,在智能電視系統(tǒng)中,需要對(duì)有限的資源進(jìn)行合理的分配.

傳統(tǒng)的資源分配問(wèn)題以系統(tǒng)整體效用的最大化為優(yōu)化目標(biāo).文獻(xiàn)[1]提出了一種基于服務(wù)質(zhì)量(Quality of Service,QoS)的資源分配模型Q-RAM,旨在滿(mǎn)足應(yīng)用最小需求的條件下最大化系統(tǒng)整體效用.文獻(xiàn)[2]將智能電視系統(tǒng)資源分配問(wèn)題建模為多維多選擇背包問(wèn)題,提出了一種啟發(fā)式算法,能夠在較短時(shí)間內(nèi)獲得近似最優(yōu)的資源分配.文獻(xiàn)[3]假設(shè)資源消耗函數(shù)是凸函數(shù),將多資源分配問(wèn)題建模為凸優(yōu)化問(wèn)題,并且提出了一種基于定價(jià)機(jī)制的多資源分配算法.

在資源分配過(guò)程中,還需要兼顧資源分配的公平性.基于公平性的資源分配問(wèn)題在諸多領(lǐng)域都得到了廣泛關(guān)注,諸如最大最小公平性和比例公平性已經(jīng)得到了廣泛應(yīng)用.文獻(xiàn)[4]引入了支配資源的概念,提出了支配資源的公平性(Dominant Resource Fairness,DRF),將最大最小公平性推廣至數(shù)據(jù)中心的多資源分配問(wèn)題.文獻(xiàn)[5]以支配資源的概念為基礎(chǔ),將公理性的公平性指標(biāo)應(yīng)用于多資源分配,并且實(shí)現(xiàn)了效率與公平性之間的權(quán)衡.文獻(xiàn)[6]將DRF進(jìn)行推廣,用于異構(gòu)云計(jì)算系統(tǒng)的資源分配.文獻(xiàn)[7]在DRF算法的基礎(chǔ)上,提出了基于信譽(yù)因子的增強(qiáng)公平性分配算法.

文獻(xiàn)[8]闡明了基于效用的資源分配的公平性概念.文獻(xiàn)[9]采用公理性議價(jià)理論中卡萊-斯莫羅廷斯基議價(jià)解定義了質(zhì)量公平的資源分配,提出了基于二分搜索的求解方法.文獻(xiàn)[10]定義了任務(wù)間服務(wù)質(zhì)量水平的公平性,提出了一種自適應(yīng)的服務(wù)質(zhì)量控制器,采用反饋控制結(jié)構(gòu),基于每個(gè)任務(wù)當(dāng)前服務(wù)質(zhì)量水平與其平均值的偏差搜尋公平的服務(wù)質(zhì)量水平.隨后,文獻(xiàn)[11]又提出了基于神經(jīng)網(wǎng)絡(luò)比例積分微分控制(Proportional-Integral and Derivatice control,PID)的自適應(yīng)資源分配算法.

筆者定義了任務(wù)間服務(wù)質(zhì)量水平的公平性,在此基礎(chǔ)上描述基于公平性的智能電視系統(tǒng)資源分配問(wèn)題.引入非線性彈性任務(wù)模型,提出利用簡(jiǎn)單迭代法求解資源分配問(wèn)題,并且推導(dǎo)出簡(jiǎn)單迭代法收斂的充分條件;進(jìn)一步把非線性彈性任務(wù)模型應(yīng)用到公平共享自適應(yīng)控制器.與現(xiàn)有算法相比,筆者所提出的資源分配算法收斂速度更快,更加適用于實(shí)時(shí)系統(tǒng).

1　智能電視系統(tǒng)資源分配問(wèn)題

1.1資源和任務(wù)集

考慮一個(gè)實(shí)時(shí)系統(tǒng),其解碼任務(wù)集Γ={τ1,τ2,…,τn},中央處理器(Central Processing Unit,CPU)帶寬容量為R,由任務(wù)集中的n個(gè)任務(wù)共享.任務(wù)τi能夠以不同的復(fù)雜度執(zhí)行,CPU帶寬需求也不盡相同.

令ri(ri∈R+)為分配給任務(wù)τi的CPU帶寬,利用分配的CPU帶寬,τi獲得的服務(wù)質(zhì)量水平為L(zhǎng)QoSi(LQoSi∈R+).通過(guò)給τi分配更多的CPU帶寬來(lái)提高LQoSi.分配的CPU帶寬ri和服務(wù)質(zhì)量水平LQoSi之間的關(guān)系可以通過(guò)單調(diào)遞增的服務(wù)質(zhì)量函數(shù)描述.

在這種情況下,任務(wù)τi具有最小的服務(wù)質(zhì)量需求和最大的服務(wù)質(zhì)量需求,即LQoSimin和LQoSimax,其中表示τi可接受的最差服務(wù)質(zhì)量水平,表示τi可獲得的最佳服務(wù)質(zhì)量水平.因而,對(duì)每個(gè)任務(wù)假設(shè)L QoSimin≤L QoSi≤L QoSimax.

每個(gè)任務(wù)τi根據(jù)其相對(duì)重要性分配不同的權(quán)重wi(wi∈R+),其中較大的wi表示τi在任務(wù)集{τ1,τ2,…,τn}中比較重要.

1.2服務(wù)質(zhì)量水平的公平性

在實(shí)時(shí)系統(tǒng)中,資源分配可能會(huì)導(dǎo)致不公平.例如,任務(wù)τ1和τ2具有相同重要性,給τ1和τ2分配相同的CPU帶寬,τ1以其最大服務(wù)質(zhì)量水平執(zhí)行,而τ2以最小服務(wù)質(zhì)量水平執(zhí)行.一般來(lái)說(shuō),LQoSi的范圍與具體任務(wù)τi有關(guān).另外,如果τ1比τ2更重要,那么相比τ2,τ1應(yīng)該以更好的性能執(zhí)行.為了定義這種公平性,下面介紹每個(gè)任務(wù)τi歸一化的服務(wù)質(zhì)量水平Qi:

這個(gè)術(shù)語(yǔ)代表執(zhí)行結(jié)果的滿(mǎn)意率,Qi在[0,1]上隨著ri單調(diào)遞增.Qi=0,表示τi以其最小服務(wù)質(zhì)量水平執(zhí)行;Qi=1,表示τi以其最大服務(wù)質(zhì)量水平執(zhí)行.每個(gè)任務(wù)τi依據(jù)其重要性分配一個(gè)權(quán)重wi,服務(wù)質(zhì)量水平的加權(quán)公平性定義如下.

服務(wù)質(zhì)量水平的公平性:假設(shè)分配給任務(wù)τi的CPU帶寬為ri,Qi和wi分別表示τi歸一化的服務(wù)質(zhì)量水平和重要性權(quán)重.如果下列公式成立,那么獲得公平的資源分配:

下面將Qi簡(jiǎn)稱(chēng)為任務(wù)τi的服務(wù)質(zhì)量水平.

1.3資源利用率和服務(wù)質(zhì)量水平

通過(guò)服務(wù)質(zhì)量函數(shù)?i:[rimin,rimax]→[0,1]描述分配的CPU帶寬ri和服務(wù)質(zhì)量水平Qi之間的關(guān)系,其中?i(ri)表示分配的CPU帶寬為ri時(shí)τi的服務(wù)質(zhì)量水平.

一般地,使用歸一化的CPU帶寬利用率Ui=riR,Ui表示分配給任務(wù)τi的CPU帶寬.服務(wù)質(zhì)量函數(shù)可以表示為?i:[Uimin,Uimax]→[0,1],其中Uimin=riminR,表示τi以可接受的最小服務(wù)質(zhì)量水平執(zhí)行時(shí)分配的CPU帶寬利用率;Uimax=rimaxR,表示τi以可獲得的最大服務(wù)質(zhì)量水平LQoS執(zhí)行時(shí)分配的

imaxCPU帶寬利用率.任務(wù)τi在執(zhí)行時(shí)實(shí)際的CPU帶寬利用率Ui在區(qū)間[Uimin,Uimax]上.

1.4目 標(biāo)

基于公平性的資源分配問(wèn)題旨在最大化每個(gè)任務(wù)的服務(wù)質(zhì)量水平,同時(shí)滿(mǎn)足服務(wù)質(zhì)量水平的加權(quán)公平性和CPU帶寬約束,即

2　基于非線性彈性任務(wù)模型的資源分配算法

2.1非線性彈性任務(wù)模型

令Xi=Ui-Uimin,表示分配給任務(wù)τi的額外CPU帶寬利用率,此時(shí)τi加權(quán)的服務(wù)質(zhì)量水平定義為Qwi=Qiwi.定義任務(wù)τi的彈性系數(shù)為

其中,gi:[0,Uimax-Uimin]→R+.任務(wù)τi的彈性系數(shù)依賴(lài)于分配的額外CPU帶寬利用率,這樣的任務(wù)是一個(gè)非線性彈性任務(wù).

令Γf為CPU帶寬利用率固定為最大值Uimax的任務(wù)集合,Γv為CPU帶寬利用率小于最大值Uimax的任務(wù)集合.如果任務(wù)τi的彈性系數(shù)是一個(gè)正常數(shù)Ei,那么τi∈Γv的CPU帶寬利用率Ui為

下面討論一個(gè)簡(jiǎn)單的數(shù)值方法.首先假設(shè)所有任務(wù)屬于集合Γv,然后放寬該假設(shè)得到完整的算法,確定在Γf非空的情況下所有任務(wù)的CPU帶寬利用率.

令X=[X1,X2,…,Xn]T∈,函數(shù)G:定義為

因而,如果不動(dòng)點(diǎn)漸進(jìn)穩(wěn)定,則可以通過(guò)下列迭代公式進(jìn)行求解:

注意到應(yīng)用牛頓法求解式(7)需要計(jì)算函數(shù)G的微分,而通過(guò)式(8)求解不動(dòng)點(diǎn)不需要計(jì)算函數(shù)G的微分.因而,簡(jiǎn)單迭代法比牛頓法更簡(jiǎn)單.

定理1 如果?Xj∈[0,Ujmax-Ujmin],,其中fj(Xj)=XjQj,那么不動(dòng)點(diǎn)漸近穩(wěn)定.

得到

根據(jù)定理2給出的迭代序列{X(k)}的誤差估計(jì)式,在給定精度ε＞0后,要使,只要計(jì)算到即可.在實(shí)際應(yīng)用中,使用小于某個(gè)充分小的數(shù)作為迭代終止條件.

2.2公平共享自適應(yīng)控制器

彈性任務(wù)模型靈感來(lái)源于串聯(lián)彈簧系統(tǒng),彈性任務(wù)的CPU帶寬利用率對(duì)應(yīng)彈簧的拉伸長(zhǎng)度,加權(quán)的服務(wù)質(zhì)量水平Qwi對(duì)應(yīng)彈簧系統(tǒng)的力.對(duì)每個(gè)任務(wù)τi,下列關(guān)系成立:

式(10)是加權(quán)的服務(wù)質(zhì)量水平隨CPU帶寬利用率的變化特性.

為了實(shí)現(xiàn)CPU帶寬的公平共享,筆者提出公平共享自適應(yīng)控制器,使用基于非線性彈性任務(wù)模型的資源分配算法分配CPU帶寬.包含公平共享自適應(yīng)控制器的實(shí)時(shí)系統(tǒng)結(jié)構(gòu)如圖1所示,它包含基本調(diào)度器、公平共享自適應(yīng)控制器和監(jiān)視器.基本調(diào)度器根據(jù)公平共享自適應(yīng)控制器分配給每個(gè)任務(wù)的CPU帶寬對(duì)任務(wù)進(jìn)行調(diào)度,通常采用的調(diào)度算法包括單調(diào)速率調(diào)度算法和最早截止期優(yōu)先調(diào)度算法.監(jiān)視器用于評(píng)估任務(wù)的服務(wù)質(zhì)量水平,并且將結(jié)果反饋給公平共享自適應(yīng)控制器.當(dāng)任務(wù)集Γ改變時(shí),觸發(fā)公平共享自適應(yīng)控制器執(zhí)行資源分配算法.

圖1　實(shí)時(shí)系統(tǒng)結(jié)構(gòu)

假設(shè)控制器知道任務(wù)τi所需CPU帶寬利用率的最小值Uimin和最大值Uimax.控制器在執(zhí)行資源分配算法時(shí)面臨兩種情況,第1種情況是控制器知道τi的非線性彈性函數(shù)gi,在這種情況下可以直接應(yīng)用筆者所提出的算法;第2種情況是控制器不知道τi的非線性彈性函數(shù)gi,在這種情況下利用分配的CPU帶寬利用率Ui和服務(wù)質(zhì)量水平Qi,估計(jì)非線性彈性函數(shù)gi的當(dāng)前值Gi如下:

因此,資源分配算法的執(zhí)行過(guò)程為:在迭代之前,控制器給每個(gè)任務(wù)τi分配初始CPU帶寬利用率Ui(0);在第k次迭代時(shí),控制器從監(jiān)視器得到每個(gè)任務(wù)τi(τi∈Γv)的服務(wù)質(zhì)量水平Qi(k-1),利用式(11)估計(jì)彈性系數(shù)Gi(k-1),更新τi的CPU帶寬利用率Ui(k)為

由定理1知,如果所有任務(wù)τi滿(mǎn)足,那么當(dāng)k趨于無(wú)窮時(shí),更新的CPU帶寬利用率收斂到公平共享.公平共享自適應(yīng)控制器的算法總結(jié)如下:

for(任務(wù)集Γv中每個(gè)任務(wù)τi){

從監(jiān)視器得到其服務(wù)質(zhì)量水平Qi;

根據(jù)式(11)估計(jì)非線性彈性函數(shù)gi的當(dāng)前值Gi;

}

for(任務(wù)集Γv中每個(gè)任務(wù)τi)根據(jù)式(12)更新每個(gè)任務(wù)的CPU帶寬利用率;

返回每個(gè)任務(wù)的CPU帶寬利用率Ui;

}.

3　仿真實(shí)驗(yàn)

通過(guò)仿真實(shí)驗(yàn)分析基于非線性彈性任務(wù)模型的CPU帶寬分配算法.算法的性能指標(biāo)主要包括算法運(yùn)行時(shí)間、CPU帶寬分配的公平性,其中算法運(yùn)行時(shí)間通過(guò)平均迭代次數(shù)來(lái)衡量.

考慮一個(gè)包含4個(gè)解碼任務(wù)的實(shí)時(shí)系統(tǒng),解碼的視頻序列分別為Silent,Stefan,Coastguard,Foreman,利用H.264編碼器獲得每個(gè)解碼任務(wù)的服務(wù)質(zhì)量函數(shù)[11].為了方便起見(jiàn),假設(shè)4個(gè)解碼任務(wù)具有相同的權(quán)重,同時(shí)基本調(diào)度器采用最早截止期優(yōu)先調(diào)度算法.

圖2　任務(wù)的加權(quán)服務(wù)質(zhì)量水平和迭代次數(shù)的關(guān)系

圖3　迭代誤差隨迭代次數(shù)的變化趨勢(shì)

如圖2所示,隨著迭代次數(shù)的增加,所有任務(wù)的加權(quán)服務(wù)質(zhì)量水平趨于一致,在大約迭代8次之后,獲得近似公平的CPU帶寬分配.在圖3中,比較了筆者所提出的算法與基于K-S議價(jià)解的資源分配算法[9]及基于神經(jīng)網(wǎng)絡(luò)PID控制的資源分配算法[12]的性能.從圖中可以看出,隨著迭代次數(shù)的增加,3種算法的迭代誤差均呈指數(shù)級(jí)減小,并且與另外兩種算法相比,筆者所提出的算法迭代誤差下降更快,性能更佳.

接下來(lái)考察任務(wù)數(shù)對(duì)算法性能的影響.隨機(jī)生成300個(gè)任務(wù)集,使用筆者所提出的算法確定公平的資源分配,統(tǒng)計(jì)不同任務(wù)數(shù)所需的平均迭代次數(shù).任務(wù)數(shù)與平均迭代次數(shù)的關(guān)系如圖4所示.從圖中可以看出,隨著任務(wù)數(shù)的增加,所需的平均迭代次數(shù)逐漸減小.這是因?yàn)槭諗克俣扰c當(dāng)前迭代點(diǎn)的加權(quán)服務(wù)質(zhì)量水平以及彈性系數(shù)的變化率有關(guān),任務(wù)數(shù)越大,不動(dòng)點(diǎn)附近的加權(quán)服務(wù)質(zhì)量水平越小,因而收斂也就越快.

圖4　平均迭代次數(shù)和任務(wù)數(shù)的關(guān)系

4　總 結(jié)

筆者定義了任務(wù)間服務(wù)質(zhì)量水平的公平性,在此基礎(chǔ)上描述了基于公平性的智能電視系統(tǒng)資源分配問(wèn)題.引入非線性彈性任務(wù)模型,提出了利用簡(jiǎn)單迭代法求解資源分配,并且推導(dǎo)出簡(jiǎn)單迭代法收斂的充分條件;進(jìn)一步把非線性彈性任務(wù)模型應(yīng)用到公平共享自適應(yīng)控制器.仿真實(shí)驗(yàn)結(jié)果表明,基于非線性彈性任務(wù)模型的資源分配算法能夠獲得近似公平的資源分配,并且與現(xiàn)有算法相比,收斂速度更快.

[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]王海威,倪宏,孫鵬,等.具有用戶(hù)體驗(yàn)保障的資源優(yōu)化分配算法[J].小型微型計(jì)算機(jī)系統(tǒng),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]陳俊杰,倪宏,孫鵬.采用定價(jià)機(jī)制的多媒體系統(tǒng)多資源分配算法[J].西安交通大學(xué)學(xué)報(bào),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ì)算下保障公平性的多資源分配算法[J].西安電子科技大學(xué)學(xué)報(bào),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]林軍,倪宏,孫鵬,等.一種采用神經(jīng)網(wǎng)絡(luò)PID控制的自適應(yīng)資源分配方法[J].西安交通大學(xué)學(xué)報(bào),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 網(wǎng)絡(luò)出版時(shí)間:2015-12-10

國(guó)家自然科學(xué)基金資助項(xiàng)目(61174065);江蘇省高校自然科學(xué)研究資助項(xiàng)目(15KJD520002);南通市應(yīng)用研究計(jì)劃資助項(xiàng)目(BK2014063)

陳俊杰(1985-),男,講師,博士,E-mail:cjjcy@ntu.edu.cn.

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.050.html