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

張文柱，曹琲琲，孔維鵬

(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í)行基本計算的應(yīng)用程序發(fā)展到3D游戲、高清視頻流服務(wù)、圖像處理、語音識別和增強(qiáng)現(xiàn)實應(yīng)用程序等．然而，移動終端的計算能力、存儲能力、電池容量均屬受限資源，難以支持計算密集型應(yīng)用，因此，移動計算領(lǐng)域迫切需要能夠有效擴(kuò)展移動終端資源、支持計算密集型應(yīng)用的技術(shù)．

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

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

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

1 移動計算遷移模型

圖1 計算遷移模型

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

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

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

?xi) ．

(1)

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

(2)

2.2 最小化時延條件

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

T1=tlocal-tremote>0 ,

(3)

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

(4)

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

2.3 最小化能耗條件

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

T2=Elocal-Eremote>0 ,

(5)

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

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

(6)

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

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

依據(jù)前面分析，減小移動終端的運(yùn)行時延、提高能效可以轉(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)值的一個下界;求得P0的最優(yōu)解之后，對這個最優(yōu)解進(jìn)行進(jìn)一步的檢驗: 如果這個最優(yōu)解是一個整數(shù)向量，則可以確定這個最優(yōu)解也是問題P的最優(yōu)解．文中采用隱形枚舉法求解P，算法流程如圖2所示，向量(x1，x2， …，xn)表示移動終端以最小化時延為目標(biāo)的最優(yōu)計算遷移策略，系統(tǒng)依據(jù)xi的值確定是否遷移組件Mi．如果P無可行解，則所有組件均不執(zhí)行計算遷移．

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

文中基于NS-3網(wǎng)絡(luò)軟件評估所設(shè)計的計算遷移方法在減小處理時延和降低能耗方面的性能．計算遷移的系統(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ī)模計算指令數(shù)．詳細(xì)仿真參數(shù)如表1所示．

表1 仿真參數(shù)

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

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

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

4 結(jié) 束 語

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