基于資源預(yù)測(cè)的智能終端資源緩存算法

徐 超,曾學(xué)文,郭志川

(1.中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京100190;2.中國(guó)科學(xué)院大學(xué),北京100049)

基于資源預(yù)測(cè)的智能終端資源緩存算法

徐 超1,2,曾學(xué)文1,郭志川1

(1.中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京100190;2.中國(guó)科學(xué)院大學(xué),北京100049)

針對(duì)智能電視終端應(yīng)用間資源競(jìng)爭(zhēng)導(dǎo)致的系統(tǒng)性能下降問(wèn)題,基于資源消耗預(yù)測(cè),提出一種智能終端資源緩存算法。根據(jù)系統(tǒng)記錄的各應(yīng)用程序的資源消耗統(tǒng)計(jì)數(shù)據(jù),應(yīng)用Markov模型預(yù)測(cè)下一時(shí)間段可能出現(xiàn)的資源瓶頸和應(yīng)用的資源狀態(tài),利用應(yīng)用的資源狀態(tài)動(dòng)態(tài)調(diào)整應(yīng)用權(quán)重,并以最小化應(yīng)用切換時(shí)間為目標(biāo),將資源緩存問(wèn)題轉(zhuǎn)化為多維多選擇背包問(wèn)題,采用輕量級(jí)的啟發(fā)式算法求解資源緩存問(wèn)題。仿真實(shí)驗(yàn)結(jié)果表明,在智能終端中該算法對(duì)于資源消耗的預(yù)測(cè)精確度比其他算法提高5.4%,而應(yīng)用響應(yīng)時(shí)間縮短約45%。

智能電視終端;資源預(yù)測(cè);Markov模型;資源緩存算法;多維多選擇背包問(wèn)題;啟發(fā)式算法

1 概述

在智能終端系統(tǒng)中,應(yīng)用程序(以下簡(jiǎn)稱應(yīng)用)的正常運(yùn)行需要多種資源,資源主要包括:CPU,內(nèi)存,內(nèi)存I/O帶寬,存儲(chǔ)容量,磁盤(pán)I/O帶寬,網(wǎng)絡(luò)帶寬,解碼器,解復(fù)用器,解調(diào)器等。每個(gè)終端上擁有的資源有限,難以支撐大量應(yīng)用同時(shí)運(yùn)行,多應(yīng)用對(duì)資源的競(jìng)爭(zhēng)將導(dǎo)致系統(tǒng)的用戶體驗(yàn)下降。在移動(dòng)設(shè)備操作系統(tǒng)中,應(yīng)用一般退出時(shí)不關(guān)閉而轉(zhuǎn)為后臺(tái)運(yùn)行狀態(tài),操作系統(tǒng)對(duì)其資源進(jìn)行緩存,以提高應(yīng)用重新啟動(dòng)時(shí)的資源加載速度。如何提高資源緩存算法的效率,縮短應(yīng)用的切換時(shí)間,成為智能終端系統(tǒng)亟待解決的問(wèn)題。

學(xué)術(shù)界一般采用降載算法［1-2］或負(fù)載均衡算法［3］緩解資源瓶頸現(xiàn)象。這些方法的缺點(diǎn)是:(1)不能判斷出現(xiàn)資源瓶頸現(xiàn)象的根本原因,即沒(méi)有采用合適模型描述資源狀態(tài);(2)算法反映均滯后于系統(tǒng)實(shí)際狀態(tài),將導(dǎo)致系統(tǒng)的QoS下降。在非線性預(yù)測(cè)

領(lǐng)域,應(yīng)用較多的算法包括人工神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等［4］,而資源消耗預(yù)測(cè)一般采用線性預(yù)測(cè)算法,在資源狀態(tài)頻繁切換的場(chǎng)景,基于回歸的預(yù)測(cè)算法［5］性能劣于基于Markov模型的預(yù)測(cè)算法?；贛arkov模型的預(yù)測(cè)算法分為2類:(1)分別對(duì)每種資源建立Markov模型進(jìn)行預(yù)測(cè)［6-8］;(2)采用聚類算法將應(yīng)用對(duì)所有資源的消耗數(shù)據(jù)聚類為一種資源狀態(tài),再對(duì)資源狀態(tài)建立Markov模型進(jìn)行預(yù)測(cè)［9］。

綜合考慮預(yù)測(cè)精確度和系統(tǒng)開(kāi)銷,本文采用Markov模型來(lái)預(yù)測(cè)資源消耗?，F(xiàn)有研究具有如下缺點(diǎn):監(jiān)測(cè)的資源類型局限于CPU、內(nèi)存、磁盤(pán)容量、網(wǎng)絡(luò)帶寬等資源,但是對(duì)智能終端上特有的設(shè)備資源,如解碼器、解復(fù)用器、解調(diào)器等缺乏恰當(dāng)?shù)谋O(jiān)測(cè)機(jī)制。并且,針對(duì)智能電視終端的應(yīng)用特點(diǎn),資源預(yù)測(cè)算法沒(méi)有做相應(yīng)的優(yōu)化。建模成Markov模型須滿足以下條件:(1)狀態(tài)構(gòu)成一階Markov鏈,即當(dāng)前狀態(tài)僅與前一狀態(tài)有關(guān),與之前狀態(tài)無(wú)關(guān);(2)狀態(tài)的轉(zhuǎn)移是時(shí)齊的,即狀態(tài)與具體時(shí)間數(shù)值無(wú)關(guān)。智能終端中應(yīng)用的資源消耗狀態(tài)的具備這些特性。

本文算法由資源預(yù)測(cè)算法和資源緩存算法兩部分構(gòu)成。資源預(yù)測(cè)算法根據(jù)應(yīng)用的資源消耗歷史數(shù)據(jù),預(yù)測(cè)某一時(shí)間段內(nèi)可能出現(xiàn)的資源瓶頸和資源消耗狀態(tài);資源緩存算法通過(guò)優(yōu)先緩存資源消耗增量較大應(yīng)用的資源,防止產(chǎn)生資源瓶頸現(xiàn)象,縮短應(yīng)用間的切換時(shí)間。

2 基于統(tǒng)計(jì)分析的資源消耗預(yù)測(cè)算法

本文采用基于資源消耗狀態(tài)的Markov模型來(lái)預(yù)測(cè)應(yīng)用的資源消耗。預(yù)測(cè)下一個(gè)時(shí)間段內(nèi)的資源消耗問(wèn)題,可以轉(zhuǎn)化為,在離散化的若干種資源消耗狀態(tài)中,預(yù)測(cè)出現(xiàn)概率最大的資源消耗狀態(tài)。Markov模型的輸入為資源管理組件采集的資源消耗數(shù)據(jù),輸出為預(yù)測(cè)的下一時(shí)間窗口的資源消耗狀態(tài)。資源消耗預(yù)測(cè)算法分為數(shù)據(jù)采集、獲取資源消耗狀態(tài)、構(gòu)造狀態(tài)轉(zhuǎn)移矩陣、資源消耗預(yù)測(cè)4個(gè)步驟。

2.1 數(shù)據(jù)采集

對(duì)于CPU和內(nèi)存消耗數(shù)據(jù),采用top工具獲取當(dāng)前時(shí)刻所有應(yīng)用的CPU和內(nèi)存占用,之后從系統(tǒng)日志中解析出每個(gè)應(yīng)用進(jìn)程的CPU和內(nèi)存占用。對(duì)于網(wǎng)絡(luò)帶寬的消耗數(shù)據(jù),采用開(kāi)源工具iftop監(jiān)測(cè)應(yīng)用占用的端口,之后從日志中解析每個(gè)應(yīng)用進(jìn)程的網(wǎng)絡(luò)帶寬占用。設(shè)備資源一般在終端系統(tǒng)BSP層提供封裝,其資源占用信息不能從內(nèi)核中獲取,因此,在智能電視操作系統(tǒng)中,由資源管理模塊進(jìn)行設(shè)備資源記錄和分析。

2.2 資源消耗狀態(tài)的獲取

對(duì)于連續(xù)性的資源如CPU資源,首先將其離散化為若干區(qū)間。如資源狀態(tài)數(shù)N=10,則離散化為［0,0.1),［0.1,0.2),…,［0.9,1］,每個(gè)區(qū)間分別表示一個(gè)CPU資源狀態(tài),即s1=［0,0.1),s2=［0.1, 0.2),…,s10=［0.9,1］。狀態(tài)空間S={s1,s2,…,sN}。在離散時(shí)間點(diǎn)t,采集系統(tǒng)中每個(gè)應(yīng)用的CPU資源消耗數(shù)據(jù),得到應(yīng)用的資源消耗狀態(tài)序列X:

X=(x0,x1,…,xt),t=0,1,…

2.3 狀態(tài)轉(zhuǎn)移矩陣的構(gòu)造

資源消耗狀態(tài)序列X是一個(gè)有限狀態(tài)Markov鏈,屬于離散時(shí)間隨機(jī)過(guò)程。假設(shè)由N個(gè)資源狀態(tài)組成{s1,s2,…,sN},各狀態(tài)的出現(xiàn)概率可用N×N的轉(zhuǎn)移概率矩陣表征。轉(zhuǎn)移矩陣由系統(tǒng)日志中若干時(shí)間窗口中的資源消耗數(shù)據(jù)構(gòu)造。

由有限狀態(tài)齊次Markov鏈的性質(zhì),有:

轉(zhuǎn)移概率pab(h,t)=P{xt=sb|xh=sa},滿足pab(h,t)≥0,∑bpab(h,t)=1,其中1≤h≤t。定義一步轉(zhuǎn)移概率pab(t)=P{xt=sb|xt-1=sa}。由于資源消耗的轉(zhuǎn)移概率與具體時(shí)刻t無(wú)關(guān),即系統(tǒng)為齊次Markov鏈,一步轉(zhuǎn)移概率可以簡(jiǎn)寫(xiě)為pab(t)=pab。求解一步轉(zhuǎn)移概率矩陣的方法如下:應(yīng)用的進(jìn)程運(yùn)行時(shí),將窗口時(shí)間內(nèi)每次資源消耗狀態(tài)轉(zhuǎn)移出現(xiàn)的次數(shù)記錄于資源消耗矩陣C中,即每次出現(xiàn)xt-1=sa且xt=sb時(shí),令cab=cab+1,由此得到C:

其中,1≤a;b≤N。

應(yīng)用資源消耗狀態(tài)的轉(zhuǎn)移概率構(gòu)成強(qiáng)聯(lián)通的有向圖,保證了Markov鏈的穩(wěn)定性。

2.4 預(yù)測(cè)值的計(jì)算

由查普曼-科爾莫戈羅夫等式,由當(dāng)前時(shí)間的資源消耗狀態(tài)的分布向量和式(2),求得t時(shí)刻應(yīng)用資源的分布向量:

由式(3),可求得每種資源t時(shí)刻后資源消耗增量的期望。應(yīng)用所需的m種資源構(gòu)成一個(gè)m維的資源消耗增量向量I=(xt1,xt2,…,xtm)。如果資源消耗增量向量I的模較大,認(rèn)為該應(yīng)用在t時(shí)刻具有較大概率發(fā)生狀態(tài)切換,即具有較大概率從后臺(tái)切換到前臺(tái)。

3 資源緩存算法

與CPU、內(nèi)存等資源不同,電視設(shè)備資源如解碼器、解復(fù)用器,其初始化和釋放都涉及多層接口的調(diào)用,帶來(lái)較大的系統(tǒng)開(kāi)銷,切換時(shí)間也較長(zhǎng),甚至高達(dá)秒級(jí)。在系統(tǒng)剩余資源不多時(shí),如果啟動(dòng)消耗資源較多的應(yīng)用,資源搶占將觸發(fā)系統(tǒng)的進(jìn)程調(diào)度策略,這是十分耗時(shí)的操作。這種情況下系統(tǒng)將按照進(jìn)程優(yōu)先級(jí)選擇性關(guān)閉進(jìn)程,頻繁的調(diào)度導(dǎo)致系統(tǒng)響應(yīng)速度變慢,用戶體驗(yàn)下降。

因此,在智能電視系統(tǒng)中,當(dāng)進(jìn)行應(yīng)用切換或系統(tǒng)資源過(guò)載時(shí),采用資源緩存算法對(duì)系統(tǒng)緩存資源進(jìn)行處理［10］。資源緩存算法的思想是在系統(tǒng)資源的約束內(nèi),盡可能多地緩存后臺(tái)應(yīng)用的資源狀態(tài),將有限的空閑資源在后臺(tái)應(yīng)用之類進(jìn)行合理分配,縮短應(yīng)用間的切換時(shí)間。其工程實(shí)現(xiàn)方法是引入資源管理組件,監(jiān)控系統(tǒng)中的后臺(tái)應(yīng)用的資源緩存狀態(tài)信息,同時(shí)隔離應(yīng)用層資源獲取接口和BSP層資源接口。資源管理組件對(duì)上為應(yīng)用層提供統(tǒng)一的資源管理和訪問(wèn)API,對(duì)下實(shí)現(xiàn)對(duì)物理資源的訪問(wèn)。

假設(shè)系統(tǒng)中有n個(gè)應(yīng)用,應(yīng)用集合為{t1,t2,…,ti,…,tn},系統(tǒng)中有m種資源,資源集合為{r1,r2,…,rj,…,rm}。對(duì)于智能電視應(yīng)用來(lái)說(shuō),某些資源間存在約束,如網(wǎng)絡(luò)視頻播放業(yè)務(wù),播放特定碼率視頻流需要固定等級(jí)的網(wǎng)絡(luò)帶寬、解碼器、解復(fù)用器、CPU和內(nèi)存。因此,緩存資源必須以特定資源組為單位,應(yīng)用的資源緩存狀態(tài)為單種資源組合之集合的子集。假設(shè)應(yīng)用共有l(wèi)個(gè)緩存狀態(tài),為{g1,g2,…,gk,…,gl},緩存狀態(tài)從g1到gl緩存資源的數(shù)量遞增,g1表示不緩存任何資源,gl表示緩存全部資源。

應(yīng)用i轉(zhuǎn)入后臺(tái)之后,如果其擁有的資源j被釋放,在其回到前臺(tái)時(shí),必須重新初始化資源j。不同資源的初始化時(shí)間不同,應(yīng)用的切換時(shí)間則為所有資源初始化時(shí)間之和。

資源緩存問(wèn)題指的是求解系統(tǒng)下一時(shí)刻內(nèi)全部資源的最優(yōu)緩存方案。其優(yōu)化目標(biāo)為最小化應(yīng)用切換時(shí)間的期望,可建模為以下問(wèn)題:

文獻(xiàn)［10］算法的缺點(diǎn)是,僅僅最優(yōu)化的系統(tǒng)中應(yīng)用切換時(shí)間的加權(quán)和,但未根據(jù)當(dāng)前的資源消耗估計(jì)資源消耗變化趨勢(shì),導(dǎo)致權(quán)重較小的應(yīng)用缺乏資源保障,同時(shí)應(yīng)用間權(quán)重的確定成為關(guān)鍵而困難的問(wèn)題。

本文算法的思路是,根據(jù)應(yīng)用當(dāng)前時(shí)刻的資源消耗,估計(jì)應(yīng)用下一時(shí)刻的資源消耗,增加資源消耗增量較大的應(yīng)用權(quán)重,優(yōu)先緩存此類應(yīng)用的資源,達(dá)到優(yōu)化應(yīng)用切換時(shí)間的目標(biāo)。

應(yīng)用從后臺(tái)切換到前臺(tái)時(shí),其資源消耗將增加,增量大小則取決于系統(tǒng)的緩存資源量。消耗增量越大,則發(fā)生應(yīng)用切換的概率越大。設(shè)資源增量向量為Ri,Ri=(Δri1,Δri2,…,Δrim),由Ri模的大小可以表征應(yīng)用切換的概率,代入式(5),得:

此時(shí),優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)多維多選擇背包問(wèn)題(MMKP)［11］。采用啟發(fā)式解法,可快速求得次優(yōu)解:啟發(fā)式解法通常首先由貪心策略得到初始可行解,再基于初始解迭代調(diào)整找到更好的可行解。如M-HEU［11］可在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解約96%值的次優(yōu)解,C-HEU［12］基于凸包構(gòu)建搜索空間,可在線性時(shí)間內(nèi)求得90%以上最優(yōu)值的次優(yōu)解。

為減小系統(tǒng)的開(kāi)銷,本文在C-HEU算法基礎(chǔ)上設(shè)計(jì)資源緩存算法。定義懲罰向量q=(q1,q2,…,qm),懲罰向量將m維資源向量轉(zhuǎn)化為一維。受懲后的資源向量R=(r1q1,r2q2,…,rjqj,…,rmqm)。此時(shí)應(yīng)用的資源Ri和切換時(shí)間Tik構(gòu)成二維平面。

算法迭代3次后,即可達(dá)到較好的尋優(yōu)結(jié)果［12］。迭代開(kāi)始前,由式(6)初始化懲罰向量:

其中,rsum為各應(yīng)用當(dāng)前資源向量之和;rsumj表示rsum中資源j的分量大小,以下Rj和R′j含義相同。

懲罰向量的更新公式為:

搜索開(kāi)始后,對(duì)于k=1,2,…,l,按各個(gè)點(diǎn)形成的凸包邊界與R軸夾角大小進(jìn)行排序。再按降序依次是否滿足資源約束(偽代碼中的check_ point函數(shù))。整體算法偽代碼如下:

資源緩存算法

算法第3行～第5行、第29行～第31行僅需m次計(jì)算。18行排序的時(shí)間復(fù)雜度為O(nllgn)。最壞情況下,每個(gè)應(yīng)用有l(wèi)個(gè)緩存狀態(tài),均消耗m種資源,每個(gè)應(yīng)用的12行復(fù)雜度為O(lm),15行復(fù)雜度為O(llgl)［12］,第12行～第15行復(fù)雜度為O(nlm+nllgl)。因此,資源緩存算法總體最壞時(shí)間復(fù)雜度為O(nml+nllgl+nllgn)。

4 仿真實(shí)驗(yàn)結(jié)果與分析

仿真實(shí)驗(yàn)采用的工具為Matlab 7.0,仿真實(shí)驗(yàn)平臺(tái)的配置為Intel Core i5-2400 3.10 GHz,RAM 4 GB。采用MATLAB中tic/toc命令計(jì)算算法執(zhí)行時(shí)間。應(yīng)用集包括15個(gè)常見(jiàn)周期型應(yīng)用,應(yīng)用類型涵蓋音視頻播放、音頻播放、PVR、網(wǎng)頁(yè)瀏覽、文件下載等。每個(gè)應(yīng)用均有5個(gè)資源緩存狀態(tài)。

4.1 資源消耗預(yù)測(cè)精確度

圖1 預(yù)測(cè)精確度

4.2 應(yīng)用切換時(shí)間

進(jìn)行20次重復(fù)實(shí)驗(yàn),每次從應(yīng)用集中隨機(jī)選擇

一個(gè)應(yīng)用運(yùn)行,此應(yīng)用進(jìn)入前臺(tái)狀態(tài),其他應(yīng)用進(jìn)入后臺(tái)狀態(tài)。實(shí)驗(yàn)分為3組,第1組不采用任何資源緩存算法,第2組采用文獻(xiàn)［10］的資源緩存算法;第2組采用本文資源緩存算法。由圖2所示,實(shí)驗(yàn)中無(wú)資源緩存時(shí)平均響應(yīng)時(shí)間為630 ms,文獻(xiàn)［10］算法平均響應(yīng)時(shí)間為456 ms,本文算法的平均響應(yīng)時(shí)間為253 ms。本文算法通過(guò)預(yù)測(cè)應(yīng)用的資源消耗狀態(tài),緩存部分資源,顯著縮短某些應(yīng)用的響應(yīng)時(shí)間。

圖2 應(yīng)用切換時(shí)間

4.3 資源緩存算法的計(jì)算時(shí)間

資源緩存算法的計(jì)算時(shí)間隨運(yùn)行的應(yīng)用數(shù)變化的仿真結(jié)果如圖3所示。精確解法如分支限界法(BBLP)的時(shí)間復(fù)雜度為指數(shù)級(jí),M-HEU時(shí)間復(fù)雜度為O(n2ml2),其中,n為應(yīng)用數(shù);m為資源數(shù);l為應(yīng)用的資源緩存狀態(tài)數(shù)。本文資源緩存算法的時(shí)間復(fù)雜度對(duì)于應(yīng)用數(shù)n是O(nlgn)級(jí)算法,顯著低于M-HEU。

圖3 資源緩存算法耗時(shí)

5 結(jié)束語(yǔ)

本文提出一種基于資源消耗預(yù)測(cè)的智能終端資源緩存算法,根據(jù)資源消耗的歷史統(tǒng)計(jì)數(shù)據(jù),利用Markov模型預(yù)測(cè)應(yīng)用切換概率,動(dòng)態(tài)調(diào)整應(yīng)用權(quán)重,并采用輕量級(jí)的資源緩存算法求解資源緩存問(wèn)題,動(dòng)態(tài)最小化應(yīng)用切換時(shí)間,有效解決了智能電視終端中資源瓶頸現(xiàn)象導(dǎo)致的應(yīng)用響應(yīng)緩慢問(wèn)題。實(shí)驗(yàn)結(jié)果表明,本文算法的預(yù)測(cè)精確度比其他算法提高5.4%,而應(yīng)用響應(yīng)時(shí)間縮短了約45%,算法本身復(fù)雜度低,帶來(lái)較小的額外開(kāi)銷。下一步的研究重點(diǎn)為在各種類型的應(yīng)用和業(yè)務(wù)場(chǎng)景中,進(jìn)一步提高預(yù)測(cè)精確度。

［1]Tu Yicheng,Liu Song,Prabhakar S,et al.Load Shedding in Stream Databases:A Control-basedApproach［C］// Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul,Korea:ACM Press,2006:787-798.

［2]Tatbul N,Cetintemel U,Zdonik S,et al.Load Shedding in a Data Stream Manager［C］//Proceedings of the 29th International Conference on Very Large Data Bases.Berlin,Germany:ACM Press,2003:309-320.

［3]Xing Ying,Zdonik S B,Hwang J H.Dynamic Load Distribution in the Borealis Stream Processor［C］// Proceedings of the 21st International Conference on Data Engineering.Tokyo,Japan:IEEE Press,2005.

［4]Sapankevych N I,SankarR.TimeSeriesPrediction Using Support Vector Machine:A Survey［J］.IEEE Computational Intelligence Magazine,2009,4(2): 24-38.

［5]Wood T,Cherkasova L,Ozonat K,et al.Profiling and ModelingResourceUsageofVirtualizedApplications［C］//Proceedings of the 9th ACM International Conference on Middleware.Leuven,Belgium:ACM Press,2008:366-387.

［6]Mallick S,Hains G,Deme C S.A Resource Prediction Model for Virtualization Servers［C］//Proceedings of International Conference on High Performance Computing and Simulation.Palermo,Italy:IEEE Press,2012: 667-671.

［7]Shi Lili,Shoubao Y,Liangmin G,et al.A Markov Chain Based Resource Prediction in Computational Grid［C］// Proceedings of the 4th International Conference on FrontierofComputerScienceandTechnology.Washington D.C.,USA:IEEE Press,2009:119-124.

［8]Gong Zhenhuan,Gu Xiaohui,Wilkes J.Press:Predictive Elastic Resource Scaling for Cloud Systems［C］// Proceedings of the 6th International Conference on Network and Service Management.Ontario,Canada: IEEE Press,2010:9-16.

［9]Gu Xiaohui,Wang Haixun.Online Anomaly Prediction for Robust Cluster Systems［C］//Proceedings of the 25th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2009:1000-1011.

［10]姜 艷.面向體驗(yàn)的智能電視多應(yīng)用運(yùn)行優(yōu)化關(guān)鍵技術(shù)研究［D］.北京:中國(guó)科學(xué)院大學(xué),2013.

［11]Akbar M M,Manning E G,Shoja G C,et al.Heuristic SolutionsfortheMultiple-choiceMulti-dimension Knapsack Problem［C］//Proceedings of International Conference on Computational Science.London,UK: Springer,2001:659-668.

［12]Mostofa A M,Sohel R M,Kaykobad M,et al.Solving the Multidimensional Multiple-choice Knapsack Problem by ConstructingConvexHulls［J］.Computers& Operations Research,2006,33(5):1259-1273.

編輯 顧逸斐

Smart Terminal Resource Cache Algorithm Based on Resource Prediction

XU Chao1,2,ZENG Xuewen1,GUO Zhichuan1
(1.National Network New Media Engineering Research Center,Institute of Acoustics, Chinese Academy of Sciences,Beijing 100190,China;2.University of Chinese Academy of Sciences,Beijing 100049,China)

In order to solve the problem of the performance degradation caused by the resource competition among the applications in smart TV,this paper presents a resource usage prediction based resource cache algorithm.The applications’resource consumption data is recorded and the resource state and resource bottleneck of the next time interval are predicted by Markov model.The weight of each application is adjusted dynamically and the resource cache problem is converted to multidimensional multiple-choice knapsack problem to minimize the switch time of the application.A lightweight heuristic solution algorithm with lower time complicity is presented.Simulation results show that the precision of the resource usage prediction of the algorithm is superior to others by about 5.4%,and the switch time of the application is reduced by about 45%.

smart TV terminal;resource prediction;Markov model;resource cache algorithm;multidimensional multiple-choice knapsack problem;heuristic algorithm

徐 超,曾學(xué)文,郭志川.基于資源預(yù)測(cè)的智能終端資源緩存算法［J］.計(jì)算機(jī)工程,2015,41(3):59-63.

英文引用格式:Xu Chao,Zeng Xuewen,Guo Zhichuan.Smart Terminal Resource Cache Algorithm Based on Resource Prediction［J］.Computer Engineering,2015,41(3):59-63.

1000-3428(2015)03-0059-05

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.03.011

國(guó)家科技支撐計(jì)劃基金資助項(xiàng)目“電視商務(wù)綜合體新業(yè)態(tài)運(yùn)營(yíng)支撐系統(tǒng)開(kāi)發(fā)”(2012BAH73F01);中國(guó)科學(xué)院先導(dǎo)專項(xiàng)課題基金資助項(xiàng)目“智能電視平臺(tái)與服務(wù)支撐環(huán)境研制”(XDA06040501)。

徐 超(1986-),男,博士研究生,主研方向:嵌入式系統(tǒng),多媒體技術(shù);曾學(xué)文,研究員、博士生導(dǎo)師;郭志川,副研究員。

2014-04-01

:2014-04-29E-mail:xuc@dsp.ac.cn