一種公平性的智能電視系統資源分配算法

陳俊杰,周 暉,張小美

(南通大學電子信息學院,江蘇南通 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