聯(lián)合優(yōu)化時(shí)延與能效的移動終端計(jì)算遷移方法

張文柱，曹琲琲，孔維鵬

(1. 西安建筑科技大學(xué) 信息與控制工程學(xué)院，陜西 西安 710055；2. 西安電子科技大學(xué) 通信工程學(xué)院，陜西 西安 710071)

隨著互聯(lián)網(wǎng)技術(shù)和無線網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，移動應(yīng)用快速增長．當(dāng)前的移動終端配備了豐富的傳感器和更高的屏幕分辨率，并能以更快的速率傳輸數(shù)據(jù)．移動應(yīng)用程序的成熟度從執(zhí)行基本計(jì)算的應(yīng)用程序發(fā)展到3D游戲、高清視頻流服務(wù)、圖像處理、語音識別和增強(qiáng)現(xiàn)實(shí)應(yīng)用程序等．然而，移動終端的計(jì)算能力、存儲能力、電池容量均屬受限資源，難以支持計(jì)算密集型應(yīng)用，因此，移動計(jì)算領(lǐng)域迫切需要能夠有效擴(kuò)展移動終端資源、支持計(jì)算密集型應(yīng)用的技術(shù)．

為了提升移動終端的續(xù)航能力、保證實(shí)時(shí)應(yīng)用低延遲的要求，計(jì)算遷移技術(shù)日益引人關(guān)注[1-2]．計(jì)算遷移是指移動終端針對特定的工作任務(wù)，受當(dāng)前計(jì)算系統(tǒng)資源的限制，需要將計(jì)算任務(wù)通過無線信道分配到遠(yuǎn)程服務(wù)器，利用遠(yuǎn)程服務(wù)器突出資源優(yōu)勢輔助移動終端完成復(fù)雜計(jì)算任務(wù)，為移動終端提供高性能的計(jì)算遷移服務(wù)[3-5]．移動終端的計(jì)算遷移首先要通過上行信道上傳遷移數(shù)據(jù)，然后等待遠(yuǎn)程計(jì)算結(jié)果，最后在下行信道接收遠(yuǎn)程服務(wù)器返回的計(jì)算結(jié)果．這要求終端必須保持與遠(yuǎn)程服務(wù)器通信的數(shù)據(jù)連接，因此會消耗寶貴的電量．為了實(shí)現(xiàn)計(jì)算遷移的整體收益，應(yīng)在確保減小應(yīng)用程序計(jì)算時(shí)延的同時(shí)，必須考慮利用無線信道遷移數(shù)據(jù)所帶來的附加能耗．在無線可變信道條件下，如何在任務(wù)的計(jì)算量、時(shí)延敏感性、能源消耗、無線信道帶寬等諸多條件下決策計(jì)算實(shí)施遷移，以及具體遷移哪些數(shù)據(jù)，這無疑具有很大挑戰(zhàn)性[6-7]．

近年來，有關(guān)學(xué)者提出了幾種用于解決移動終端的資源可用性和可持續(xù)性問題的遷移機(jī)制．例如，基于離散時(shí)間馬爾可夫鏈(Discrete-Time Markov Chain，DTMC)設(shè)計(jì)無線移動信道模型的衰落模型，在移動終端側(cè)區(qū)分應(yīng)用程序的普通數(shù)據(jù)和計(jì)算密集型組件，執(zhí)行在多點(diǎn)遠(yuǎn)程服務(wù)器計(jì)算遷移，減小終端能耗[8]; 設(shè)計(jì)無線局域網(wǎng)環(huán)境下的計(jì)算遷移排隊(duì)遷移模型，并分析傳輸延遲和遷移效率，目標(biāo)是減小計(jì)算時(shí)延、改善用戶體驗(yàn)[9]; 基于位置決策的移動計(jì)算遷移方法[10]，等等．盡管在當(dāng)前已有的方法已經(jīng)在克服移動終端的能耗、提升移動終端的處理能力方面取得進(jìn)展，但是毫無疑問，目前的研究方案在靈活控制實(shí)施計(jì)算遷移組件、綜合考慮移動終端的能效與應(yīng)用程序的時(shí)延敏感性以及無線信道帶寬的可變性等方面還需要進(jìn)一步探索．

筆者設(shè)計(jì)了一種能夠聯(lián)合優(yōu)化時(shí)延與能效的移動終端的計(jì)算遷移方法．該方法以LTE應(yīng)用為背景，設(shè)計(jì)了移動計(jì)算遷移模型; 在此基礎(chǔ)上，分析計(jì)算遷移相關(guān)參數(shù)，包括應(yīng)用程序?qū)τ?jì)算資源的需求、移動終端的工作指標(biāo)參數(shù)以及無線信道的傳輸速率等參數(shù)，構(gòu)造遷移代價(jià)函數(shù); 最后，分析應(yīng)用程序?qū)τ?jì)算資源的需求、移動終端的計(jì)算能力和無線信道的傳輸速度，以減小時(shí)延與降低能耗為約束條件、以聯(lián)合優(yōu)化處理時(shí)延和能耗為目標(biāo)，合理規(guī)劃應(yīng)用程序的計(jì)算遷移．

1 移動計(jì)算遷移模型

圖1 計(jì)算遷移模型

設(shè)計(jì)的計(jì)算遷移模型如圖1所示．在移動終端側(cè)，遷移模型包括計(jì)組件分解模塊、組件遷移代價(jià)評估模塊、遠(yuǎn)程服務(wù)器系統(tǒng)信息收集模塊、遷移決策模塊以及結(jié)果合成模塊等．為了實(shí)現(xiàn)計(jì)算遷移，計(jì)算組件分解模塊將應(yīng)用程序代碼分解成計(jì)算組件，每個(gè)組件包含3個(gè)特征參數(shù):原始代碼規(guī)模、發(fā)送代碼規(guī)模、接收代碼規(guī)模;運(yùn)行該組件所需的指令集;本地中央處理器(Central Processing Unit，CPU)執(zhí)行指令的速率．組件遷移代價(jià)評估模塊依據(jù)信道帶寬、接收速率和發(fā)送速率、遠(yuǎn)程服務(wù)器的系統(tǒng)信息與狀態(tài)信息，計(jì)算各個(gè)模塊的遷移代價(jià); 遷移決策模塊依據(jù)遷移代價(jià)評估模塊發(fā)送過來的遷移代價(jià)以及服務(wù)器狀態(tài)收集模塊發(fā)送過來的服務(wù)器資源狀態(tài)信息，執(zhí)行文中設(shè)計(jì)的算法，合理規(guī)劃計(jì)算組件的遷移;最后，當(dāng)服務(wù)器將計(jì)算結(jié)果返回時(shí)，結(jié)果合成模塊將本地計(jì)算結(jié)果與遠(yuǎn)程服務(wù)器返回的遷移計(jì)算結(jié)果合成，作為應(yīng)用程序的最終輸出．

2 聯(lián)合優(yōu)化時(shí)延與能效的計(jì)算遷移方法

2.1 設(shè)計(jì)計(jì)算遷移的目標(biāo)函數(shù)

?xi) ．

(1)

代價(jià)函數(shù)表示為遠(yuǎn)程執(zhí)行服務(wù)的遷移代價(jià)，包括為執(zhí)行遠(yuǎn)程服務(wù)而必須遷移所有關(guān)聯(lián)組件模塊的代價(jià); 不同計(jì)算組件之間存在一定的關(guān)聯(lián)，式(1)的后半部分反映這種關(guān)聯(lián)．據(jù)此構(gòu)造計(jì)算遷移的目標(biāo)函數(shù)為

(2)

2.2 最小化時(shí)延條件

為了實(shí)現(xiàn)時(shí)延最小化的目標(biāo)，必須保證執(zhí)行計(jì)算遷移需要的時(shí)間小于本地運(yùn)行所需的時(shí)間，即

T1=tlocal-tremote>0 ,

(3)

其中，tlocal表示計(jì)算組件在本地執(zhí)行所需時(shí)間，tlocal可以由在本地執(zhí)行的指令數(shù)Ilocal與本地執(zhí)行指令速率Rlocal的比值求出，tlocal= (Ilocal/Rlocal)xi．tremote表示執(zhí)行計(jì)算遷移所需要的總時(shí)間，tremote由3部分組成:遠(yuǎn)程服務(wù)器執(zhí)行運(yùn)算所需要的時(shí)間;發(fā)送遷移數(shù)據(jù)Dsend及附加數(shù)據(jù)Dadd的所需要的時(shí)間;移動終端接收遠(yuǎn)程服務(wù)器的計(jì)算結(jié)果所需要的時(shí)間．于是服務(wù)遷移所需的總時(shí)間可由下式計(jì)算:

(4)

其中，Dsend和Drec分別是發(fā)送計(jì)算組件的數(shù)據(jù)規(guī)模大小和接收遠(yuǎn)程服務(wù)器返回計(jì)算結(jié)果的數(shù)據(jù)大小(單位為字節(jié));Dadd是發(fā)送關(guān)聯(lián)計(jì)算組件的數(shù)據(jù)規(guī)模大小;Bsend和Brec分別是發(fā)送和接收數(shù)據(jù)時(shí)的信道帶寬;Rremote是云服務(wù)器執(zhí)行指令的速率．且有

2.3 最小化能耗條件

為了實(shí)現(xiàn)能效優(yōu)先的目標(biāo)，必須保證遷移服務(wù)執(zhí)行計(jì)算遷移需要的能耗小于本地運(yùn)行所需的能耗，即

T2=Elocal-Eremote>0 ,

(5)

其中，Elocal表示本地執(zhí)行能耗，可以表示為在本地執(zhí)行的指令數(shù)Ilocal、本地執(zhí)行指令速率Rlocal以及移動終端執(zhí)行指令所需的功率Plocal的函數(shù)，即Elocal= (PlocalIlocal)/Rlocal．Eremote表示執(zhí)行計(jì)算遷移所需要的總能耗，Eremote包括:等待遷移結(jié)果返回的等待能耗Ewait；傳輸遷移數(shù)據(jù)(計(jì)算組件)需要的能耗，包括發(fā)送遷移數(shù)據(jù)所需能耗Esend和接收服務(wù)器返回計(jì)算結(jié)果所需能耗Erec；傳輸附加數(shù)據(jù)(關(guān)聯(lián)計(jì)算組件)所需的附加能耗Eadd．于是Eremote可由下式計(jì)算:

Eremote=Esend+Ewait+Erec+Eadd=Psend(tsend+tadd)+Pidletwait+Prectrec,

(6)

其中，Psend、Prec和Pidle分別是移動終端標(biāo)稱的發(fā)射功率、接收功率以及處于空閑狀態(tài)的功率;tsend和tadd分別是移動終端發(fā)送遷移數(shù)據(jù)所需時(shí)間和發(fā)送附加數(shù)據(jù)所需時(shí)間;twait和trec分別等待遠(yuǎn)程服務(wù)器返回結(jié)果所需時(shí)間和接收遠(yuǎn)程服務(wù)器返回結(jié)果數(shù)據(jù)所需時(shí)間．

2.4 聯(lián)合優(yōu)化時(shí)延與能效

依據(jù)前面分析，減小移動終端的運(yùn)行時(shí)延、提高能效可以轉(zhuǎn)化為最優(yōu)化問題，即以式(3)和式(5)為約束條件的式(2)的優(yōu)化問題，即

(7)

式(7)可通過執(zhí)行整數(shù)線性規(guī)劃(Integer Linear Programming，ILP)算法來求解[11]．為了獲得問題P的最優(yōu)解，首先找到問題P對應(yīng)的松弛問題P0:

(8)

圖2 采用隱形枚舉法求解P的最優(yōu)解流程圖

問題P和P0的關(guān)系:P的可行區(qū)域是P0的可行區(qū)域的子集;如果P0無可行解，則P無可行解;P0的最優(yōu)值是P的最優(yōu)值的一個(gè)下界;求得P0的最優(yōu)解之后，對這個(gè)最優(yōu)解進(jìn)行進(jìn)一步的檢驗(yàn): 如果這個(gè)最優(yōu)解是一個(gè)整數(shù)向量，則可以確定這個(gè)最優(yōu)解也是問題P的最優(yōu)解．文中采用隱形枚舉法求解P，算法流程如圖2所示，向量(x1，x2， …，xn)表示移動終端以最小化時(shí)延為目標(biāo)的最優(yōu)計(jì)算遷移策略，系統(tǒng)依據(jù)xi的值確定是否遷移組件Mi．如果P無可行解，則所有組件均不執(zhí)行計(jì)算遷移．

3 仿真與性能評估結(jié)果

文中基于NS-3網(wǎng)絡(luò)軟件評估所設(shè)計(jì)的計(jì)算遷移方法在減小處理時(shí)延和降低能耗方面的性能．計(jì)算遷移的系統(tǒng)模型如圖1所示．遠(yuǎn)程服務(wù)器有采用Intel i7-4770k CPU，處理能力為 1.2× 105DMIPS@ 3.5 GHz，8 GB 隨機(jī)存取存儲器(Random Access Memory，RAM)，運(yùn)行Windows Server 2008操作系統(tǒng); 長期演進(jìn)(Long Term Evolution，LTE)移動終端采用三星Galaxy s5，配置高通Snapdragon-801 CPU，處理能力為 3.3× 104DMIPS@ 2.5 GHz，2 GB RAM，操作系統(tǒng)Android 4.4．移動終端通過LTE eNB(Evolved Node B)接入網(wǎng)絡(luò)，無線信道速率分別設(shè)置為 5 Mbit/s、10 Mbit/s，誤碼率為10-3;移動終端執(zhí)行的應(yīng)用程序源碼規(guī)模最小為 0.2 MB，最大為 2.0 MB，遞增步長取 0.2 MB; 按照每4字節(jié)組成1條指令，可由程序源碼規(guī)模計(jì)算指令數(shù)．詳細(xì)仿真參數(shù)如表1所示．

表1 仿真參數(shù)

當(dāng)信道傳輸速率為5 Mbit/s時(shí)，移動終端執(zhí)行文中設(shè)計(jì)的計(jì)算遷移方法與僅執(zhí)行本地計(jì)算時(shí)的處理時(shí)延、功耗對比分別如圖3和圖4所示．圖3表明文中設(shè)計(jì)的計(jì)算遷移方法能否獲得更短的處理延遲與任務(wù)需要處理的數(shù)據(jù)量密切相關(guān)．當(dāng)任務(wù)的數(shù)據(jù)量小于 800 KB 時(shí)，執(zhí)行時(shí)間的差異極小，本地處理時(shí)延略小; 當(dāng)任務(wù)的數(shù)據(jù)量大于 800 KB 時(shí)，采用計(jì)算遷移算法總能取得更小的處理時(shí)延; 當(dāng)任務(wù)的數(shù)據(jù)量為 2 000 KB 時(shí)，執(zhí)行計(jì)算遷移算法能夠?qū)⑻幚頃r(shí)延減小28%．

圖4表明文中設(shè)計(jì)的計(jì)算遷移方法能夠獲得明顯的能效收益．具體來說，當(dāng)任務(wù)的數(shù)據(jù)量小于 400 KB 時(shí)，應(yīng)用計(jì)算遷移與本地執(zhí)行的時(shí)延幾乎沒有差別; 當(dāng)任務(wù)的數(shù)據(jù)量大于 400 KB 時(shí)，與本地執(zhí)行相比，執(zhí)行計(jì)算遷移總能獲取是更高的能效; 當(dāng)應(yīng)用程序的源碼規(guī)模最后達(dá)到 2 000 KB 時(shí)，執(zhí)行計(jì)算遷移算法能夠比僅執(zhí)行本地計(jì)算減少36%能耗，這說明文中設(shè)計(jì)的計(jì)算遷移算法在降低能耗方面也具有明顯的效果．

圖5和圖6分別表明信道速率對計(jì)算遷移算法的時(shí)延、能耗的影響．圖5表明更快的信道速率能夠減小時(shí)延，當(dāng)應(yīng)用程序源碼規(guī)模在 200～ 2 000 KB 范圍內(nèi)變化時(shí)，10 Mbit/s 信道速率比 5 Mbit/s 信道速率平均減小時(shí)延23%．圖6表明更快的信道速率始終能夠減小終端能耗，當(dāng)應(yīng)用程序源碼規(guī)模在 200～ 2 000 KB 范圍內(nèi)變化時(shí)，10 Mbit/s 的信道速率比 5 Mbit/s 信道速率平均節(jié)省能耗26%．可見，更快的信道速率有助于計(jì)算遷移算法獲得更短的時(shí)延以及更低的能耗．

4 結(jié) 束 語

面向LTE應(yīng)用背景，筆者設(shè)計(jì)了一種能夠聯(lián)合優(yōu)化時(shí)延與能效的移動終端的計(jì)算遷移方法．該方法首先設(shè)計(jì)了移動計(jì)算遷移模型;在此基礎(chǔ)上，分析計(jì)算遷移相關(guān)參數(shù)，包括應(yīng)用程序?qū)τ?jì)算資源的需求、移動終端的工作指標(biāo)參數(shù)以及無線信道的傳輸速率等參數(shù)，構(gòu)造遷移代價(jià)函數(shù);最后，以減小時(shí)延與降低能耗為約束條件、以聯(lián)合優(yōu)化處理時(shí)延和能耗為目標(biāo)，合理規(guī)劃應(yīng)用程序的計(jì)算遷移．研究結(jié)果表明，文中設(shè)計(jì)的計(jì)算遷移方法能夠有效減小移動終端的處理時(shí)延，同時(shí)可以獲得更高的能效．