移動(dòng)邊緣計(jì)算中資源受限的串行任務(wù)卸載策略*

劉 偉 , 黃宇成 , 杜 薇 , 王 偉

1(武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢 430070)2(交通物聯(lián)網(wǎng)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430070)3(同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,上海 200092)

據(jù)思科視覺網(wǎng)絡(luò)指數(shù)預(yù)測(cè),到2021 年,全球移動(dòng)數(shù)據(jù)流量每月將達(dá)到49 艾字節(jié)(EB),這對(duì)移動(dòng)終端的性能和移動(dòng)網(wǎng)絡(luò)的數(shù)據(jù)傳輸率提出了新的要求[1].此外,一類新的應(yīng)用程序也應(yīng)運(yùn)而生,諸如人臉識(shí)別[2]、移動(dòng)增強(qiáng)現(xiàn)實(shí)[3]等,這類應(yīng)用對(duì)延遲比較敏感,且需要大量的資源.然而,移動(dòng)終端的計(jì)算和存儲(chǔ)資源有限,尤其是電池的續(xù)航周期較短,運(yùn)行這類應(yīng)用程序會(huì)帶來較高的延遲,增加移動(dòng)終端的能耗.而移動(dòng)云計(jì)算(mobile cloud computing,簡(jiǎn)稱MCC)[4]的出現(xiàn),為解決這些問題提供了一種有效方式,通過任務(wù)卸載(也稱計(jì)算卸載或計(jì)算遷移)[5,6]將應(yīng)用程序的部分計(jì)算任務(wù)卸載到遠(yuǎn)程云端,減少了應(yīng)用程序的完成時(shí)間,提高了移動(dòng)終端的續(xù)航能力.

然而在傳統(tǒng)移動(dòng)云計(jì)算中,移動(dòng)終端通過互聯(lián)網(wǎng)與遠(yuǎn)程公有云連接,如阿里云、騰訊云等,由于集中式部署的遠(yuǎn)程公有云距離移動(dòng)終端較遠(yuǎn),在兩者之間通過互聯(lián)網(wǎng)進(jìn)行數(shù)據(jù)傳輸往往會(huì)帶來比較高的網(wǎng)絡(luò)延遲[7],這對(duì)于延遲敏感型的移動(dòng)應(yīng)用程序無法容忍.為了解決MCC 存在的高延遲問題,誕生了一種新的計(jì)算模式——移動(dòng)邊緣計(jì)算(mobile edge computing,簡(jiǎn)稱MEC)[8],在靠近移動(dòng)終端的網(wǎng)絡(luò)邊緣部署邊緣服務(wù)器,將遠(yuǎn)程云端提供的IT 服務(wù)和計(jì)算能力延伸到距離移動(dòng)終端更近的位置,移動(dòng)終端便能夠利用邊緣服務(wù)器強(qiáng)大的資源,并以較低的網(wǎng)絡(luò)延遲與邊緣服務(wù)器進(jìn)行數(shù)據(jù)傳輸.當(dāng)終端提交卸載請(qǐng)求時(shí),可以直接在邊緣服務(wù)器上處理而不需要發(fā)送給遠(yuǎn)程云端,節(jié)省了應(yīng)用完成時(shí)間和終端能耗.MEC 既有強(qiáng)大的計(jì)算和存儲(chǔ)能力,又有靠近用戶的高帶寬、低時(shí)延的優(yōu)勢(shì),能夠顯著地提高用戶的實(shí)時(shí)體驗(yàn)和滿意度.國(guó)內(nèi)相關(guān)學(xué)者在邊緣計(jì)算體系結(jié)構(gòu)等領(lǐng)域取得了一定的研究成果[9].但是,邊緣計(jì)算在移動(dòng)性管理、虛擬化技術(shù)和計(jì)算卸載等領(lǐng)域還存在一定的技術(shù)挑戰(zhàn)[10].

學(xué)者們針對(duì)邊緣服務(wù)器環(huán)境中的任務(wù)卸載問題,從不同的角度開展研究工作[11-24].然而,這些工作大多針對(duì)單個(gè)移動(dòng)終端或邊緣服務(wù)器資源無限的場(chǎng)景.與傳統(tǒng)的云計(jì)算相比,邊緣服務(wù)器提供的計(jì)算、網(wǎng)絡(luò)及存儲(chǔ)資源是有限的.此外,當(dāng)有大量用戶同時(shí)向邊緣服務(wù)器提交卸載請(qǐng)求時(shí),用戶之間會(huì)對(duì)邊緣服務(wù)器的資源產(chǎn)生競(jìng)爭(zhēng),導(dǎo)致資源的不足而帶來應(yīng)用性能的衰減.因此,考慮多用戶同時(shí)向資源受限的邊緣服務(wù)器提交卸載請(qǐng)求的場(chǎng)景是非常有必要的.但是,與已存在的工作相比,這將導(dǎo)致計(jì)算卸載情況更加復(fù)雜.

本文針對(duì)邊緣服務(wù)器資源受限場(chǎng)景下的任務(wù)卸載和資源分配問題展開研究,提出了一種面向多用戶的串行任務(wù)動(dòng)態(tài)卸載策略(MSTDOS).此策略考慮了多用戶同時(shí)請(qǐng)求的競(jìng)爭(zhēng)關(guān)系和任務(wù)卸載決策與服務(wù)器資源分配之間的相互影響,以應(yīng)用的平均完成時(shí)間和移動(dòng)終端的平均能量消耗作為評(píng)價(jià)指標(biāo),采用化學(xué)反應(yīng)優(yōu)化算法求解.該策略遵循先來先服務(wù)原則,合理分配邊緣服務(wù)器的資源,減少任務(wù)在服務(wù)器上的等待時(shí)間,從而使用戶得到一個(gè)更好的卸載結(jié)果,提高用戶體驗(yàn)和應(yīng)用性能.

本文的主要貢獻(xiàn)如下.

1)解決了邊緣服務(wù)器資源受限時(shí)的多終端串行任務(wù)卸載問題.本文建立了串行任務(wù)模型、應(yīng)用完成時(shí)間模型和終端能耗模型,旨在降低應(yīng)用平均完成時(shí)間和終端平均能耗;同時(shí),采用線性加權(quán)的方法將多目標(biāo)優(yōu)化問題歸一為單目標(biāo)優(yōu)化問題,并證明該問題屬于NP-hard;

2)提出了一種面向多用戶的串行任務(wù)動(dòng)態(tài)卸載策略MSTDOS.該策略基于化學(xué)反應(yīng)優(yōu)化算法,在滿足組件間依賴關(guān)系的前提下,充分考慮多用戶的競(jìng)爭(zhēng)關(guān)系和任務(wù)卸載決策與資源分配的相互影響,提高了應(yīng)用性能和用戶體驗(yàn);

3)驗(yàn)證了MSTDOS 策略的有效性.本文選取現(xiàn)實(shí)生活中的人臉識(shí)別應(yīng)用作為評(píng)估對(duì)象,仿真實(shí)驗(yàn)表明:在邊緣服務(wù)器資源受限的多終端任務(wù)卸載場(chǎng)景下,MSTDOS 策略比存在的方法在應(yīng)用性能提升上有明顯優(yōu)勢(shì).

本文第1 節(jié)介紹國(guó)內(nèi)外的研究現(xiàn)狀.第2 節(jié)描述任務(wù)卸載的場(chǎng)景及相關(guān)概念.第3 節(jié)闡述具體的系統(tǒng)模型和問題定義.第4 節(jié)重點(diǎn)介紹本文提出的卸載策略.第5 節(jié)分析實(shí)驗(yàn)環(huán)境和評(píng)估結(jié)果.最后,對(duì)本文工作進(jìn)行總結(jié)和展望.

1 相關(guān)工作

近年來,任務(wù)卸載[11-24]問題在學(xué)術(shù)界引起了廣泛的關(guān)注.為了擴(kuò)展移動(dòng)終端的計(jì)算能力,延長(zhǎng)終端的續(xù)航周期,相關(guān)研究者們提出了多種任務(wù)卸載框架,如MAUI[11],ThinkAir[12],CloneCloud[13]等,關(guān)于計(jì)算遷移的研究方法和策略也開展了相關(guān)工作.浙江大學(xué)的鄧水光等人[14]考慮到移動(dòng)云環(huán)境中用戶的移動(dòng)性,提出了一種包含容錯(cuò)機(jī)制的卸載系統(tǒng),保障了應(yīng)用的穩(wěn)定執(zhí)行,并采用遺傳算法為應(yīng)用做出卸載決策.北京大學(xué)的黃罡團(tuán)隊(duì)[15]針對(duì)Web 應(yīng)用中由復(fù)雜腳本導(dǎo)致任務(wù)計(jì)算量過大的問題,將Web 應(yīng)用動(dòng)態(tài)變化的特征和計(jì)算卸載相結(jié)合,提出了一種應(yīng)用運(yùn)行時(shí)的卸載策略從而得到Web 應(yīng)用的卸載結(jié)果.南洋理工大學(xué)的張維文等人[16]研究了移動(dòng)云環(huán)境中基于隨機(jī)無線信道的任務(wù)卸載問題,分別采用窮舉法和one-climb 策略為應(yīng)用做出卸載決策,確定在截止時(shí)間約束下能耗最優(yōu)的選擇結(jié)果.文獻(xiàn)[17]針對(duì)由多用戶資源競(jìng)爭(zhēng)而導(dǎo)致的高能耗問題,提出了一種任務(wù)聯(lián)合執(zhí)行策略,將聯(lián)合執(zhí)行應(yīng)用的優(yōu)化問題建模為最小化終端能耗問題,并采用遺傳算法來處理該優(yōu)化問題.武漢大學(xué)的傅建明團(tuán)隊(duì)[18]對(duì)CM-MCC 和CA-MCC 兩類彈性移動(dòng)云計(jì)算方式展開了研究,分析了其實(shí)現(xiàn)流程及存在的問題;同時(shí),針對(duì)彈性移動(dòng)云計(jì)算的安全問題展開分析,并研究相應(yīng)防御方法.北京郵電大學(xué)的王尚廣團(tuán)隊(duì)[19]針對(duì)已有服務(wù)選擇工作沒有考慮到移動(dòng)終端的狀態(tài)和歷史特征信息的問題,提出了一種狀態(tài)感知和穩(wěn)定性感知的選擇方法,分別對(duì)任務(wù)在移動(dòng)終端和云端運(yùn)行兩種情況建模,并設(shè)計(jì)了一種選擇算法決定最優(yōu)的服務(wù).

由于集中式部署的遠(yuǎn)程公有云距離移動(dòng)終端較遠(yuǎn),他們之間的數(shù)據(jù)傳輸將帶來較高的網(wǎng)絡(luò)延遲.借助于移動(dòng)邊緣計(jì)算,將計(jì)算和存儲(chǔ)服務(wù)部署在移動(dòng)網(wǎng)絡(luò)的邊緣,能有效彌補(bǔ)傳統(tǒng)云計(jì)算的不足.韋恩州立大學(xué)的施巍松等人[8]針對(duì)集中式數(shù)據(jù)處理方式無法滿足大量數(shù)據(jù)的實(shí)時(shí)處理需求問題,提出了面向邊緣設(shè)備的邊緣計(jì)算模型,將其與現(xiàn)有的云計(jì)算模式相結(jié)合,提升了數(shù)據(jù)處理的效率.香港科技大學(xué)的張軍等人[20]針對(duì)移動(dòng)邊緣計(jì)算中終端電量不足的問題,提出了基于李雅普諾夫優(yōu)化的動(dòng)態(tài)任務(wù)卸載策略,綜合考慮應(yīng)用的卸載策略、移動(dòng)終端執(zhí)行的時(shí)鐘頻率和云端執(zhí)行的傳輸功耗,為應(yīng)用做出最優(yōu)的卸載決策.西安電子科技大學(xué)的汪彥婷等人[21]針對(duì)移動(dòng)邊緣計(jì)算中的部分任務(wù)卸載問題,分別從單個(gè)邊緣服務(wù)器場(chǎng)景和多個(gè)邊緣服務(wù)器場(chǎng)景來考慮任務(wù)的卸載問題,并采用動(dòng)態(tài)電壓頻率調(diào)節(jié)技術(shù)來優(yōu)化移動(dòng)終端能耗,提出的卸載算法降低了應(yīng)用延遲和終端能耗.

然而,上面的研究工作都是考慮單個(gè)移動(dòng)終端或邊緣服務(wù)器資源無限的場(chǎng)景,這在實(shí)際應(yīng)用中存在一定的局限性.香港理工大學(xué)的曹建農(nóng)等人[22]針對(duì)云端資源受限的多終端任務(wù)卸載問題,提出了一種卸載策略SearchAdjust.該策略先假設(shè)云端資源無限然后再作調(diào)整,有效提高了應(yīng)用性能和用戶體驗(yàn).西南大學(xué)的郭松濤等人[23]針對(duì)時(shí)間約束下的移動(dòng)終端能耗最優(yōu)問題,提出了一種節(jié)能的動(dòng)態(tài)卸載和資源調(diào)度策略eDors.該策略由任務(wù)卸載、CPU 時(shí)鐘頻率控制和傳輸功率分配這3 個(gè)子算法組成,有效降低了終端能耗.關(guān)于多信道干擾的多終端任務(wù)卸載策略的問題,中山大學(xué)的陳旭等人[24]采用博弈論的方法為所有應(yīng)用做出近似最優(yōu)的卸載決策,從而在滿足應(yīng)用完成時(shí)間約束時(shí),達(dá)到移動(dòng)終端的能耗最優(yōu).

本文針對(duì)邊緣服務(wù)器資源受限條件下多終端的串行任務(wù)卸載問題,考慮多個(gè)用戶請(qǐng)求之間的相互影響,研究如何高效分配邊緣服務(wù)器的資源,為所有應(yīng)用做出近似最優(yōu)的卸載決策,使得所有應(yīng)用的平均完成時(shí)間和移動(dòng)終端的平均能耗達(dá)到近似最優(yōu).

2 任務(wù)卸載場(chǎng)景及介紹

圖1 呈現(xiàn)了多終端任務(wù)卸載的場(chǎng)景,該場(chǎng)景主要包括3 個(gè)部分:移動(dòng)終端、移動(dòng)網(wǎng)絡(luò)和邊緣服務(wù)器.本文的研究工作主要集中在移動(dòng)終端和邊緣服務(wù)器端.多終端的任務(wù)卸載過程如下:對(duì)于移動(dòng)終端,產(chǎn)生并運(yùn)行移動(dòng)應(yīng)用程序,通過移動(dòng)網(wǎng)絡(luò)向邊緣服務(wù)器提交卸載請(qǐng)求;對(duì)于邊緣服務(wù)器端,接收來自移動(dòng)端的任務(wù)卸載請(qǐng)求,分配合適的資源處理應(yīng)用請(qǐng)求,處理完成后通過移動(dòng)網(wǎng)絡(luò)將最終的結(jié)果返回到移動(dòng)終端.

接下來主要介紹在任務(wù)卸載過程中涉及到的相關(guān)概念的定義.

(1) 移動(dòng)應(yīng)用程序

移動(dòng)應(yīng)用程序是移動(dòng)終端運(yùn)行的任務(wù),此類任務(wù)一般分為獨(dú)立任務(wù)和依賴任務(wù)兩種:獨(dú)立任務(wù)表示應(yīng)用程序的結(jié)構(gòu)是不可分割的,只由單個(gè)任務(wù)構(gòu)成,如N皇后問題、矩陣運(yùn)算問題等;依賴任務(wù)表示應(yīng)用程序可自動(dòng)劃分為多個(gè)具有相互依賴關(guān)系的子任務(wù),子任務(wù)之間存在數(shù)據(jù)交互,如人臉識(shí)別應(yīng)用、QR 二維碼應(yīng)用等.本文以依賴任務(wù)中的串行移動(dòng)應(yīng)用程序?yàn)檠芯繉?duì)象.假設(shè)一個(gè)任務(wù)可劃分為n個(gè)子任務(wù),即Task={1,2,…,n}.第k個(gè)子任務(wù)能夠開始執(zhí)行,除了要分配有足夠的計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)資源外,還需其前驅(qū)組件k-1 已執(zhí)行完成.串行任務(wù)模型已被許多研究者所采用[2,17,22].具體介紹見第3.1 節(jié).

(2) 移動(dòng)終端

移動(dòng)終端是產(chǎn)生應(yīng)用程序的環(huán)境,本文假設(shè)每個(gè)移動(dòng)終端都只運(yùn)行一個(gè)相同的應(yīng)用程序.用N表示提交卸載請(qǐng)求的移動(dòng)終端數(shù)量,可以表示為MDs={md1,md2,…,mdN},而每個(gè)移動(dòng)終端可以表示成一個(gè)八元組:

其中,i表示移動(dòng)終端的編號(hào),i∈[1,N];表示移動(dòng)終端的計(jì)算能力(每秒執(zhí)行的指令數(shù),單位為MIPS);poweri表示移動(dòng)終端i當(dāng)前的可用電量;分別表示移動(dòng)終端的CPU 在工作狀態(tài)和空閑狀態(tài)下的功率;Pi,send,Pi,recv和分別表示移動(dòng)終端的網(wǎng)絡(luò)接口在發(fā)送數(shù)據(jù)、接收數(shù)據(jù)和空閑狀態(tài)下的功率.

(3) 邊緣服務(wù)器

邊緣服務(wù)器部署在靠近移動(dòng)終端的網(wǎng)絡(luò)邊緣,為任務(wù)卸載提供計(jì)算、網(wǎng)絡(luò)和存儲(chǔ)等服務(wù).本文只考慮部署在單個(gè)固定地理位置的邊緣服務(wù)器.選取M個(gè)配置相同的虛擬機(jī)表示邊緣服務(wù)器資源的集合,即VMs={VM1,VM2,…,VMM},每個(gè)虛擬機(jī)可以表示為一個(gè)四元組:VMi={i,capacityi,Bi,waiti},其中,i表示虛擬機(jī)的編號(hào),i∈[1,M];capacityi為虛擬機(jī)i的計(jì)算能力,表示每秒執(zhí)行的指令數(shù);Bi表示當(dāng)前時(shí)刻移動(dòng)終端與邊緣服務(wù)器通信的網(wǎng)絡(luò)帶寬;waiti表示組件卸載到虛擬機(jī)i上需要等待的時(shí)間.假設(shè)所有虛擬機(jī)的處理能力和傳輸能力均一致,并不會(huì)隨著任務(wù)量的上升而改變.

(4) 移動(dòng)網(wǎng)絡(luò)

移動(dòng)網(wǎng)絡(luò)表示移動(dòng)終端和邊緣服務(wù)器之間數(shù)據(jù)的通信方式,為組件的卸載提供了可能.移動(dòng)終端可以通過蜂窩網(wǎng)絡(luò)(如4G,5G[25])或者無線接入點(diǎn)(Wi-Fi)方式,將應(yīng)用程序的部分組件卸載到邊緣服務(wù)器執(zhí)行.

(5) 卸載策略

卸載策略表示應(yīng)用程序的卸載結(jié)果,對(duì)于每個(gè)終端運(yùn)行的應(yīng)用程序,其卸載策略可以表示為一個(gè)n維向量:Si={xi,1,xi,2,…,xi,n},其中,n為應(yīng)用i包含的組件個(gè)數(shù).向量中的每個(gè)值xi,j代表應(yīng)用i的組件j是在本地執(zhí)行還是邊緣服務(wù)器執(zhí)行,其取值為0 或1:xi,j=0 表示應(yīng)用i的組件j在本地執(zhí)行,xi,j=1 表示組件卸載到邊緣服務(wù)器執(zhí)行.

Fig.1 An illustration of task offloading with multiple mobile terminals圖1 多終端任務(wù)卸載場(chǎng)景

3 系統(tǒng)模型及問題定義

3.1 任務(wù)模型

本文的研究對(duì)象是由若干個(gè)串行組件組成的移動(dòng)應(yīng)用程序.如圖2 所示,該應(yīng)用由n個(gè)組件構(gòu)成,其中,組件0 和組件n+1 為虛擬組件,表示數(shù)據(jù)輸入和結(jié)果輸出的組件,且固定在本地執(zhí)行.本文采用線性鏈表L={V,E}來表示組件之間的依賴關(guān)系,每個(gè)節(jié)點(diǎn)i∈V示移動(dòng)應(yīng)用程序的一個(gè)組件,每條有向邊e(i,j)∈E表示組件i和組件j之間的依賴關(guān)系.可以看出,組件j只有等待其前驅(qū)組件i執(zhí)行完成后才能開始執(zhí)行.

Fig.2 An illustration of serial task model for mobile applications圖2 移動(dòng)應(yīng)用的串行任務(wù)模型

串行應(yīng)用程序在實(shí)際生活中存在著廣泛的應(yīng)用,如人臉識(shí)別應(yīng)用[2]、視頻字符識(shí)別和國(guó)際象棋等.人臉識(shí)別應(yīng)用包括圖片輸入、人臉檢測(cè)、圖像預(yù)處理、臉部特征提取、人臉匹配和結(jié)果輸出等6 個(gè)順序執(zhí)行組件,前一個(gè)組件計(jì)算的輸出結(jié)果作為后一個(gè)組件的輸入數(shù)據(jù),當(dāng)所有組件執(zhí)行完成并輸出最終結(jié)果,表示應(yīng)用執(zhí)行完畢.視頻字符識(shí)別應(yīng)用包括視頻輸入、關(guān)鍵幀提取、文本區(qū)域定位、字符識(shí)別、OCR 識(shí)別和文本輸出等6 個(gè)組件.人機(jī)對(duì)戰(zhàn)中的中國(guó)象棋或國(guó)際象棋,機(jī)器每走一步,其后臺(tái)的計(jì)算都可以劃分為幾個(gè)串行的任務(wù):首先計(jì)算每顆棋子能夠移動(dòng)的位置,然后計(jì)算每個(gè)棋子的最優(yōu)移動(dòng)位置,最后計(jì)算最優(yōu)的移動(dòng)棋子[17].

3.2 完成時(shí)間模型

完成時(shí)間[26]是評(píng)價(jià)應(yīng)用性能的一個(gè)重要指標(biāo),表示應(yīng)用程序從數(shù)據(jù)輸入到結(jié)果輸出整個(gè)過程所需的時(shí)間.接下來,分別從應(yīng)用組件在本地執(zhí)行和邊緣服務(wù)器執(zhí)行來討論組件的執(zhí)行時(shí)間.

3.2.1 本地執(zhí)行

本地執(zhí)行表示組件(i,j)在移動(dòng)終端上執(zhí)行,STi,j,FTi,j分別表示組件(i,j)的開始執(zhí)行時(shí)間和結(jié)束時(shí)間,RTi記錄移動(dòng)終端i可以開始執(zhí)行任務(wù)的時(shí)間.由于組件(i,j)必須等待其前驅(qū)組件(i,j-1)執(zhí)行完成后才能開始執(zhí)行,則組件(i,j)在本地的開始執(zhí)行時(shí)間表示為

其中,pred(i,j)表示組件(i,j)的前驅(qū)組件的集合;Ti,j-1,j表示組件(i,j-1)和(i,j)之間的數(shù)據(jù)傳輸時(shí)間,計(jì)算公式如下:

其中,datai,j-1,j表示組件(i,j-1)和組件(i,j)之間數(shù)據(jù)傳輸?shù)拇笮?

3.2.2 邊緣服務(wù)器執(zhí)行

邊緣服務(wù)器執(zhí)行表示組件通過移動(dòng)網(wǎng)絡(luò)卸載到邊緣服務(wù)器上執(zhí)行.對(duì)于組件(i,j),如果前驅(qū)組件沒有在邊緣服務(wù)器上執(zhí)行,由于應(yīng)用之間對(duì)邊緣服務(wù)器資源的競(jìng)爭(zhēng)使用,則需要考慮等待時(shí)間;反之,則不需要考慮等待時(shí)間.因此,組件(i,j)在邊緣服務(wù)器上的開始執(zhí)行時(shí)間可以表示為

其中,waiti,v表示應(yīng)用i在虛擬機(jī)v中的等待時(shí)間,其等待時(shí)間的長(zhǎng)短主要取決于虛擬機(jī)v中排隊(duì)在應(yīng)用i之前的應(yīng)用的服務(wù)時(shí)間之和.這里用servicek,v表示應(yīng)用k在虛擬機(jī)v上的服務(wù)時(shí)間,每個(gè)應(yīng)用維護(hù)一個(gè)鏈表Listk,表示應(yīng)用k卸載到邊緣服務(wù)器上的組件的集合.則應(yīng)用i的等待時(shí)間可以通過如下公式得到:

其中,FTi,exit表示應(yīng)用程序出口組件的結(jié)束時(shí)間,STi,entry表示應(yīng)用程序入口組件的開始執(zhí)行時(shí)間.

3.3 能耗模型

移動(dòng)終端包括屏幕、CPU、藍(lán)牙、GPS、ROM、RAM、網(wǎng)絡(luò)接口等[27]多個(gè)部件,本文主要考慮移動(dòng)終端CPU 和網(wǎng)絡(luò)接口產(chǎn)生的能耗.

3.3.1 計(jì)算能耗

移動(dòng)終端的CPU 主要包括運(yùn)行和空閑兩種狀態(tài).如果CPU 有任務(wù)執(zhí)行,就會(huì)一直處于運(yùn)行狀態(tài),沒有任務(wù)處理時(shí),CPU 則會(huì)進(jìn)入空閑狀態(tài).CPU 處于運(yùn)行狀態(tài)的能耗計(jì)算如下:

3.3.2 傳輸能耗

傳輸能耗主要是移動(dòng)終端和邊緣服務(wù)器之間進(jìn)行數(shù)據(jù)傳輸產(chǎn)生的,包括數(shù)據(jù)發(fā)送能耗、數(shù)據(jù)接收能耗和網(wǎng)絡(luò)接口空閑能耗.對(duì)于一個(gè)應(yīng)用而言,當(dāng)存在兩個(gè)滿足前驅(qū)后繼關(guān)系的相鄰組件都在移動(dòng)端或邊緣服務(wù)器上執(zhí)行時(shí),傳輸能耗為零;只有當(dāng)兩個(gè)組件在不同的位置執(zhí)行時(shí),才存在傳輸能耗.移動(dòng)終端發(fā)送數(shù)據(jù)到邊緣服務(wù)器產(chǎn)生數(shù)據(jù)發(fā)送能耗,接收邊緣服務(wù)器返回的數(shù)據(jù)產(chǎn)生數(shù)據(jù)接收能耗.則對(duì)應(yīng)的能耗分別表示為

3.4 問題定義

在第3.2 節(jié)和第3.3 節(jié)中分別建立了單個(gè)應(yīng)用的完成時(shí)間模型和單個(gè)移動(dòng)終端的能耗模型,MskeSpani表示應(yīng)用i的完成時(shí)間,Ei表示移動(dòng)終端i產(chǎn)生的能耗.上述時(shí)間和能耗模型都受卸載決策S的影響,不能通過獨(dú)立計(jì)算同時(shí)達(dá)到最小值,其中,S={S1,S2,…,SN}.本文針對(duì)邊緣服務(wù)器資源受限條件下多終端的串行任務(wù)卸載問題,旨在提高串行應(yīng)用性能的同時(shí)降低移動(dòng)終端能耗,采用線性加權(quán)的方法來規(guī)劃聯(lián)合目標(biāo)函數(shù).因此,原問題可以定義為

上述λt和λe分別代表應(yīng)用完成時(shí)間和終端能耗所占的權(quán)重,有λt,λe∈(0,1),且滿足λt+λe=1.其中:限制條件(a)保證了組件(i,j)只有等待其前驅(qū)組件(i,j-1)執(zhí)行完成才能開始執(zhí)行;限制條件(b)表示邊緣服務(wù)器中每個(gè)虛擬機(jī)在同一時(shí)間只能處理一個(gè)任務(wù),即應(yīng)用k和應(yīng)用i都有任務(wù)在虛擬機(jī)v上執(zhí)行,應(yīng)用k表示應(yīng)用i后面的應(yīng)用,則應(yīng)用k的任務(wù)只有等待應(yīng)用i的任務(wù)執(zhí)行完成后才能開始執(zhí)行;限制條件(c)表示所有任務(wù)所分配的帶寬量應(yīng)滿足邊緣服務(wù)器提供的網(wǎng)絡(luò)帶寬的約束;限制條件(d)表示應(yīng)用組件的執(zhí)行位置只能是0 或1.根據(jù)應(yīng)用系統(tǒng)模型,應(yīng)用的輸入數(shù)據(jù)由移動(dòng)終端產(chǎn)生,輸出結(jié)果將返回到移動(dòng)終端,限制條件(e)表明應(yīng)用的入口組件和出口組件只能在本地執(zhí)行.

命題1.F1 問題屬于NP-hard.

證明:考慮F1 問題的一種特殊情況,參數(shù)λt=1,λe=0,并忽略組件之間傳輸時(shí)間.此時(shí),應(yīng)用i的任務(wù)完成時(shí)間僅由所有組件的執(zhí)行時(shí)間構(gòu)成.計(jì)算如下:

滿足上述約束條件(a)～約束條件(e).

可以看出:該特殊情況為組件在本地執(zhí)行或邊緣服務(wù)器執(zhí)行的完成時(shí)間最小化問題,等價(jià)于0-1 背包問題.我們知道,0-1 背包問題屬于NP-hard 問題[28].因此,F1 問題的特殊情況也是NP-hard 問題,故F1 問題也屬于NP-hard[29].

4 算法描述

本文研究的任務(wù)卸載問題是典型的多目標(biāo)組合優(yōu)化問題[30],屬于NP-hard 問題,可以采用啟發(fā)式算法求解該類問題.目前存在多種啟發(fā)式算法,如遺傳算法(GA)[31]、粒子群算法(PSO)[32]、蟻群算法(ACO)[33]和化學(xué)反應(yīng)優(yōu)化算法(CRO)[34]等.相比于遺傳算法,化學(xué)反應(yīng)優(yōu)化算法能避免過早地陷入局部最優(yōu),獲取全局近似最優(yōu)解,同時(shí)以更快的速度收斂于最優(yōu)解[35].化學(xué)反應(yīng)優(yōu)化算法[34]最早是在2010 年由Lam 和Li 提出來的,靈感來源于大自然中的化學(xué)反應(yīng).根據(jù)實(shí)際應(yīng)用表明:化學(xué)反應(yīng)算法能夠有效地解決多目標(biāo)優(yōu)化問題,并且在二次分配問題、網(wǎng)格任務(wù)調(diào)度問題、人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練、資源受限項(xiàng)目調(diào)度問題等方面得到廣泛的應(yīng)用.針對(duì)邊緣服務(wù)器資源受限的多終端任務(wù)卸載問題,本文采用化學(xué)反應(yīng)優(yōu)化算法求解.

4.1 算法框架

化學(xué)反應(yīng)優(yōu)化算法中,分子具有3 個(gè)必要屬性:分子結(jié)構(gòu)(structure,簡(jiǎn)稱S)、分子勢(shì)能(potential energy,簡(jiǎn)稱PE)和分子動(dòng)能(kinetic energy,簡(jiǎn)稱KE).分子結(jié)構(gòu)S表示任務(wù)卸載策略的一個(gè)解空間;分子勢(shì)能PE表示分子結(jié)構(gòu)的穩(wěn)定性,定義為目標(biāo)函數(shù)的值;分子動(dòng)能KE使得分子勢(shì)能趨向更高的狀態(tài),避免目標(biāo)函數(shù)值過早地陷入局部最優(yōu)解而繼續(xù)尋找全局最優(yōu)解.第4.2 節(jié)～第4.4 節(jié)主要從問題編碼、適應(yīng)度函數(shù)和操作算子設(shè)計(jì)這3 個(gè)角度介紹化學(xué)反應(yīng)優(yōu)化算法.問題編碼定義了卸載策略與分子結(jié)構(gòu)之間的關(guān)系;適應(yīng)度函數(shù)是評(píng)估分子好壞的標(biāo)準(zhǔn),分子的適應(yīng)度值越小,代表所求問題的解越優(yōu),因此,設(shè)計(jì)一種好的適應(yīng)度函數(shù)有利于獲得最優(yōu)解;操作算子是算法搜索解空間的關(guān)鍵步驟,不同的操作算子能夠改變分子結(jié)構(gòu),避免算法過早陷入局部最有解,同時(shí)搜索全局最優(yōu)解.第4.5 節(jié)介紹具體的算法設(shè)計(jì),第4.6 節(jié)和第4.7 節(jié)分別對(duì)算法的復(fù)雜度和收斂性進(jìn)行分析.

4.2 問題編碼

化學(xué)反應(yīng)優(yōu)化算法是一種通過模擬化學(xué)反應(yīng)過程搜索最優(yōu)解的方法,問題解空間用分子集合表示,分子是由若干個(gè)原子編碼組成.本文研究的移動(dòng)應(yīng)用程序是由串行執(zhí)行的組件構(gòu)成,每個(gè)組件執(zhí)行位置分為移動(dòng)終端執(zhí)行和邊緣服務(wù)器執(zhí)行,分別用0 和1 表示.移動(dòng)應(yīng)用程序的卸載決策表示為分子,組件的執(zhí)行位置用原子表示.

圖3 是移動(dòng)應(yīng)用程序及其對(duì)應(yīng)的分子結(jié)構(gòu),該應(yīng)用程序包含5 個(gè)組件,分子結(jié)構(gòu)表示應(yīng)用程序的卸載策略,分子中每個(gè)原子的值代表組件的卸載位置.圖中是一種可能的分子結(jié)構(gòu)S={1,1,0,1,0},表示組件3、組件5 在移動(dòng)終端上執(zhí)行,組件1、組件2、組件4 卸載到邊緣服務(wù)器執(zhí)行.

4.3 適應(yīng)度函數(shù)

本文評(píng)價(jià)卸載策略性能的指標(biāo)是平衡所有應(yīng)用的平均完成時(shí)間和移動(dòng)終端的平均能耗.對(duì)于一種卸載策略S,對(duì)應(yīng)的應(yīng)用完成時(shí)間用T表示,移動(dòng)終端能耗用E表示,將兩個(gè)不同量綱的目標(biāo)進(jìn)行歸一化處理,并采用線性加權(quán)方式將雙目標(biāo)轉(zhuǎn)化為單目標(biāo),則適應(yīng)度函數(shù)[36]可以表示為如下形式:

其中,Tmax和Tmin分別代表分子種群中所有分子對(duì)應(yīng)的應(yīng)用完成時(shí)間的最大值和最小值,Emax和Emin分別代表分子種群中所有分子對(duì)應(yīng)的移動(dòng)終端能耗的最大值和最小值.α和β分別代表應(yīng)用完成時(shí)間和移動(dòng)終端能耗的比例所占權(quán)重,其取值主要由移動(dòng)終端的可用電量來決定,α,β∈(0,1),且滿足α+β=1.當(dāng)移動(dòng)終端電量充足時(shí),完成時(shí)間為主要優(yōu)化目標(biāo),參數(shù)設(shè)置條件為α>β;當(dāng)電量不足時(shí),主要優(yōu)化移動(dòng)終端能耗,設(shè)置α<β.然而,在實(shí)際場(chǎng)景中,完成時(shí)間和能耗的權(quán)重的合理分配可根據(jù)多屬性決策理論[24,34]來確定.

4.4 操作算子設(shè)計(jì)

本節(jié)介紹化學(xué)反應(yīng)優(yōu)化算法的4 種基本操作算子,包括單分子碰撞、單分子分解、分子間碰撞和分子合成.問題編碼中介紹過每個(gè)分子結(jié)構(gòu)表示一種卸載策略,不同的操作算子對(duì)分子結(jié)構(gòu)會(huì)產(chǎn)生變化,應(yīng)用程序的卸載策略也會(huì)隨之改變.單分子碰撞和分子間碰撞對(duì)原分子結(jié)構(gòu)改變較小,旨在原卸載策略的鄰域空間搜索更優(yōu)的卸載策略;單分子分解和分子合成提供搜索更大解空間的機(jī)會(huì),避免卸載策略過早地陷入局部最優(yōu)解.下面詳細(xì)介紹4 種基本操作算子的具體設(shè)計(jì).

4.4.1 單分子碰撞

單分子碰撞是指單個(gè)分子與容器壁發(fā)生碰撞并反彈的過程.對(duì)于分子S,發(fā)生單分子碰撞后產(chǎn)生新的分子S′,新分子S′與原分子S在分子結(jié)構(gòu)上相差不大,表示碰撞過程是在分子S的鄰域空間搜索最優(yōu)解.

具體設(shè)計(jì)如圖4 所示:從原分子S中隨機(jī)選擇一個(gè)原子,改變其執(zhí)行位置,剩余部分保留不變.對(duì)應(yīng)到卸載策略中,原先的卸載策略經(jīng)過單分子碰撞后,隨機(jī)改變應(yīng)用某個(gè)組件的執(zhí)行位置,產(chǎn)生新的卸載策略.

Fig.4 On-wall ineffective collision圖4 單分子碰撞

4.4.2 單分子分解

單分子分解是指單個(gè)分子與容器壁發(fā)生碰撞后分解為兩個(gè)或多個(gè)分子的過程.本文假設(shè)分解后產(chǎn)生兩個(gè)分子.對(duì)于分子S,經(jīng)過單分子分解后產(chǎn)生新的分子S1 和S2,新分子S1 和S2 與原分子S在分子結(jié)構(gòu)上差別較大,表示分解過程是探索更大的解空間,避免結(jié)果過早地收斂于局部最優(yōu)解.

具體設(shè)計(jì)如圖5 所示:在原分子中隨機(jī)選擇一個(gè)分解點(diǎn)point,新分子S1 保留原分子S的[start,point]部分的原子,新分子S2 保留原分子S的[point,end]部分的原子,S1 和S2 剩余的原子位隨機(jī)生成.對(duì)應(yīng)到卸載策略中,原卸載策略經(jīng)過單分子分解,隨機(jī)選擇一個(gè)組件作為分解點(diǎn),將分解點(diǎn)的前部分組件和后部分組件分別保留到兩個(gè)新分子的對(duì)應(yīng)位置,剩余組件的執(zhí)行位置隨機(jī)產(chǎn)生,從而得到新的卸載策略.

Fig.5 Decomposition圖5 單分子分解

4.4.3 分子間碰撞

分子間碰撞是指兩個(gè)分子相互碰撞并反彈的過程.對(duì)于分子S1 和S2,發(fā)生分子間碰撞后產(chǎn)生新分子S1′和S2′,新分子S1′和S2′與原分子在分子結(jié)構(gòu)上比較相似,表示碰撞過程是在分子S1 和S2 的鄰域空間搜索最優(yōu)解.

具體設(shè)計(jì)如圖6 所示:從原分子中選擇兩個(gè)碰撞點(diǎn)point1 和point2,交換原分子S1 和S2 對(duì)應(yīng)碰撞點(diǎn)的原子的值,形成新的分子.對(duì)應(yīng)到卸載策略中,原卸載策略經(jīng)過分子間碰撞,隨機(jī)交換兩個(gè)卸載策略中對(duì)應(yīng)兩個(gè)組件的執(zhí)行位置,得到兩個(gè)新的卸載策略.

Fig.6 Inter-Molecular ineffective collision圖6 分子間碰撞

4.4.4 分子合成

分子合成是指兩個(gè)或多個(gè)分子相互碰撞并合成一個(gè)分子的過程.本文假設(shè)是兩個(gè)分子進(jìn)行分子合成操作.對(duì)于分子S1 和S2,經(jīng)過分子合成后產(chǎn)生新的分子S,新分子S和原分子在分子結(jié)構(gòu)上相差較大,表示合成使得分子種群呈現(xiàn)多樣化,擴(kuò)大解的搜索空間.

具體設(shè)計(jì)如圖7 所示:隨機(jī)生成一個(gè)合成點(diǎn)point,新分子繼承原分子S1 的[start,point]部分的原子和原分子S2 的[point,end]部分的原子.對(duì)應(yīng)到卸載策略中,原卸載策略經(jīng)過分子合成后,隨機(jī)選擇一個(gè)組件作為合成點(diǎn),將第1 種卸載策略的合成點(diǎn)的前部分組件和第2 種卸載策略對(duì)應(yīng)合成點(diǎn)的后部分組件保留,合成后得到新的卸載策略.

Fig.7 Synthesis圖7 分子合成

4.5 算法設(shè)計(jì)

本文提出了一種面向多用戶的串行任務(wù)動(dòng)態(tài)卸載策略MSTDOS.針對(duì)邊緣服務(wù)器資源受限的多終端任務(wù)卸載問題,MSTDOS 算法為所有應(yīng)用做出近似最優(yōu)的卸載決策,使得在減少應(yīng)用完成時(shí)間的同時(shí)降低移動(dòng)終端能耗.

算法1 中,首先,MSTDOS 對(duì)邊緣服務(wù)器上所有虛擬機(jī)的狀態(tài)進(jìn)行初始化(line 1),保證所有虛擬機(jī)可以最早開始執(zhí)行任務(wù)的時(shí)間為零,其次,進(jìn)入迭代過程,為所有應(yīng)用做出近似最優(yōu)的卸載決策.在每次迭代過程中,遍歷所有的虛擬機(jī),選擇可以最早開始執(zhí)行任務(wù)的虛擬機(jī)v,記錄該虛擬機(jī)的最早開始時(shí)間為RTmin(line 3～line 7),此時(shí),將虛擬機(jī)v作為應(yīng)用i卸載組件到邊緣服務(wù)器的候選虛擬機(jī).確定應(yīng)用i卸載的候選虛擬機(jī)后,采用化學(xué)反應(yīng)優(yōu)化算法CRO(i,RTmin)為應(yīng)用i做出任務(wù)卸載決策(CRO 算法的具體過程在算法2 中介紹)(line 7),并返回應(yīng)用i的近似最優(yōu)卸載策略,將其添加到所有應(yīng)用的策略集StrategyList中(line 8),并更新虛擬機(jī)的最早開始執(zhí)行時(shí)間(line 9).最后,迭代過程結(jié)束,得到所有應(yīng)用的近似最優(yōu)卸載策略.

算法1.多用戶串行任務(wù)動(dòng)態(tài)卸載策略MSTDOS.

輸入:所有移動(dòng)終端的卸載請(qǐng)求、移動(dòng)應(yīng)用程序;

輸出:所有應(yīng)用的近似最優(yōu)任務(wù)卸載策略.

算法2 詳細(xì)介紹了通過化學(xué)反應(yīng)優(yōu)化算法CRO 為應(yīng)用做出任務(wù)卸載決策的過程.CRO 算法包括3 個(gè)階段:初始化、迭代和結(jié)果輸出.在初始化階段(line 1～line 11)進(jìn)行相關(guān)參數(shù)的定義(line 1),并隨機(jī)生成包含PopSize個(gè)分子的分子種群(line 2～line 11).在迭代階段(line 12～line 31)進(jìn)行MaxIter次迭代過程,每一次迭代過程中,從4種基本操作中選擇一種操作發(fā)生反應(yīng).將參數(shù)MoleColl定義為分子間發(fā)生反應(yīng)的概率,生成一個(gè)隨機(jī)數(shù)t∈(0,1),如果t>MoleColl,則發(fā)生單分子反應(yīng)(line 15～line 21);否則發(fā)生分子間反應(yīng)(line 22～line 28).單分子反應(yīng)時(shí),隨機(jī)選擇一個(gè)分子,如果分子滿足分解條件,則發(fā)生單分子分解操作;否則發(fā)生單分子碰撞操作,單分子反應(yīng)結(jié)束時(shí)更新策略集Strategies.分子間反應(yīng)時(shí),隨機(jī)選擇一對(duì)分子,判斷分子對(duì)是否同時(shí)滿足分子合成操作:滿足則發(fā)生單分子合成操作,否則發(fā)生單分子碰撞操作.在結(jié)果輸出階段(line 32,line 33),從分子種群中選擇具有最小勢(shì)能的分子,作為應(yīng)用i的近似最優(yōu)卸載策略.

算法2.化學(xué)反應(yīng)優(yōu)化算法CRO(i,RTmin).

輸入:移動(dòng)終端i的請(qǐng)求、移動(dòng)應(yīng)用程序;

輸出:應(yīng)用i的近似最優(yōu)任務(wù)卸載策略.

4.6 算法的時(shí)間復(fù)雜度分析

設(shè)應(yīng)用的個(gè)數(shù)為N,邊緣服務(wù)器的虛擬機(jī)個(gè)數(shù)為M,分子種群的規(guī)模為PopSize,最大迭代次數(shù)為MaxIter,應(yīng)用的組件個(gè)數(shù)為n.算法1 中,MSTDOS 算法為每個(gè)應(yīng)用做決策主要包括兩個(gè)步驟:首先,從邊緣服務(wù)器中選擇合適的虛擬機(jī),作為卸載應(yīng)用的候選虛擬機(jī),其時(shí)間復(fù)雜度為O(M);其次,采用CRO 算法為當(dāng)前應(yīng)用做出具體的任務(wù)卸載決策,其中,初始化分子種群的時(shí)間復(fù)雜度為O(PopSize×n),單分子碰撞操作的時(shí)間復(fù)雜度為O(1),單分子分解操作的時(shí)間復(fù)雜度為O(n),分子間碰撞的時(shí)間復(fù)雜度為O(1),分子合成的時(shí)間復(fù)雜度為O(n),基本操作迭代的次數(shù)為MaxIter,因而,CRO 算法的時(shí)間復(fù)雜度為O(PopSize×n+MaxIter×n2).

因此,算法1 總的時(shí)間復(fù)雜度為O(N×(M+PopSize×n+MaxIter×n2)).

4.7 算法的收斂性分析

MSTDOS 算法的收斂性主要受化學(xué)反應(yīng)算法的基本操作影響.參考文獻(xiàn)[37]中建立的有限吸收馬爾可夫鏈模型,將每個(gè)分子結(jié)構(gòu)表示成一種狀態(tài),用X表示所有狀態(tài)空間的集合.對(duì)于一種狀態(tài),經(jīng)過基本操作Λ后會(huì)改變其狀態(tài),令ΨΛ(x)表示分子x經(jīng)過操作Λ后可能出現(xiàn)的狀態(tài)的集合,且ΨΛ(x)?X,二元組(X,(ΨΛ(x),x∈X))能夠抽象成一個(gè)有向無環(huán)圖G(V,E),頂點(diǎn)集V用X表示,邊集E則根據(jù)ΨΛ(x)={i|(x,i)∈E}得到.如圖8 所示為經(jīng)過操作Λ后狀態(tài)的轉(zhuǎn)換過程,可以得出,狀態(tài)x1經(jīng)過操作Λ可以轉(zhuǎn)換成x2,x3和x4,即ΨΛ(x1)={x2,x3,x4},以此類推,ΨΛ(x2)={x2,x5,x6},ΨΛ(x3)={x1,x2,x6},ΨΛ(x4)={x3,x5},ΨΛ(x5)={x2,x6},ΨΛ(x6)={x2}.

Fig.8 A state transition under operator Λ圖8 操作Λ下的狀態(tài)轉(zhuǎn)換

定義1(最佳可達(dá)性[37]).設(shè)G(V,E)為CRO 算法的解圖,若?x?X-Xopt,則經(jīng)過一定的狀態(tài)轉(zhuǎn)換,至少存在一個(gè)最優(yōu)解xopt∈Xopt,使得x=x0→x1→x2→…→xI=xopt,其中,l為從x到xopt狀態(tài)轉(zhuǎn)換的次數(shù),則稱G(V,E)為最佳可達(dá).

定理1.CRO 收斂于全局最優(yōu)解的必要條件是G(V,E)最佳可達(dá).

證明:CRO 中每種操作算子都存在一個(gè)解圖,用G(V,Eowi),G(V,Edec),G(V,Eimi),G(V,Esyn)分別表示單分子碰撞、單分子分解、分子間碰撞和分子合成的解圖,G(V,E)表示CRO 算法的解圖,則滿足E=Eowi∪Edec∪Eimi∪Esyn.假設(shè)解圖G(V,E)不是最佳可達(dá),其解圖的任意非最優(yōu)解都無法通過狀態(tài)轉(zhuǎn)化到達(dá)最優(yōu)解,則存在解x′∈X-Xopt.CRO 算法中初始種群產(chǎn)生的解都是非最優(yōu)解x′的概率為1/||X||n,||X||表示X的基,n為初始種群大小.于是,從x′轉(zhuǎn)換到最優(yōu)解的概率為

則不存在一個(gè)從非最優(yōu)解到最優(yōu)解的轉(zhuǎn)換過程,因此,產(chǎn)生最優(yōu)解的概率計(jì)算如下:

由此可得:當(dāng)G(V,E)不滿足最佳可達(dá)的條件時(shí),CRO 算法不能收斂于全局最優(yōu)解.證畢.□

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

5.1 仿真實(shí)驗(yàn)環(huán)境

(1) 移動(dòng)終端

本文的移動(dòng)終端選取Oppo A37、樂視3、Vivo Y67 和小米6 這4 款手機(jī),其詳細(xì)的參數(shù)配置見表1,具體的功率值是通過移動(dòng)終端的power-profile.xml 文件獲取得到.

Table 1 Mobile terminals configuration表1 移動(dòng)終端配置

(2) 邊緣服務(wù)器

采用由實(shí)驗(yàn)室4 臺(tái)服務(wù)器搭建的Openstack 集群環(huán)境,Openstack 的版本為Juno,4 臺(tái)服務(wù)器的型號(hào)都是Lenovo ThinkServer RD330,CPU 是兩個(gè)核心數(shù)為四核的Intel Xeon E5-2620,主頻是2.1GHz,內(nèi)存大小是32G,硬盤容量是500G,操作系統(tǒng)是Ubuntu 14.04 的linux 系統(tǒng).

(3) 網(wǎng)絡(luò)環(huán)境

邊緣服務(wù)器的內(nèi)部節(jié)點(diǎn)之間是通過帶寬為56Gbps 的InfiniBand 高速交換機(jī)進(jìn)行連接,交換機(jī)的型號(hào)是Mellanox SX602.邊緣服務(wù)器與外部設(shè)備通過TP-Link 的千兆以太網(wǎng)交換機(jī)連接,交換機(jī)型號(hào)為TL-SG1024T.

(4) 移動(dòng)應(yīng)用程序

本文選用人臉識(shí)別應(yīng)用[2]作為實(shí)驗(yàn)驗(yàn)證的應(yīng)用程序.如圖9 所示,人臉識(shí)別應(yīng)用主要包括6 個(gè)順序執(zhí)行的組件,分別是圖片輸入、人臉檢測(cè)、圖像預(yù)處理、臉部特征提取、人臉匹配和結(jié)果輸出.將每個(gè)組件用序號(hào)進(jìn)行編號(hào),其中,No.0 和No.5 分別代表人臉識(shí)別應(yīng)用程序的開始和結(jié)束組件,固定在移動(dòng)終端執(zhí)行.實(shí)驗(yàn)中,選取一張240KB 大小的包含人臉圖像的圖片作為輸入數(shù)據(jù).

Fig.9 Face recognition applications圖9 人臉識(shí)別應(yīng)用

首先,分別在給定的移動(dòng)終端和服務(wù)器上運(yùn)行人臉識(shí)別應(yīng)用,測(cè)出應(yīng)用的每個(gè)組件的執(zhí)行時(shí)間,表2 給出了每個(gè)組件的平均執(zhí)行時(shí)間.

Table 2 Average execution time of each component表2 應(yīng)用程序組件的平均執(zhí)行時(shí)間

然后,對(duì)組件之間傳輸?shù)臄?shù)據(jù)大小進(jìn)行了測(cè)量,測(cè)量結(jié)果見表3.

Table 3 Transmission data size among components表3 組件之間的傳輸數(shù)據(jù)大小

5.2 實(shí)驗(yàn)結(jié)果分析

本節(jié)將提出的MSTDOS 策略與已有的AllInMobile 策略[24]、SearchAdjust 策略[22]和MDSA 策略[38]進(jìn)行比較.其中,AllInMobile 策略表示應(yīng)用的所有組件都在本地執(zhí)行,不受邊緣服務(wù)器資源和網(wǎng)絡(luò)帶寬的影響.SearchAdjust 策略是一種多終端離線卸載策略,先假設(shè)邊緣服務(wù)器資源無限,做出應(yīng)用的卸載決策,再對(duì)不滿足資源限制條件的組件進(jìn)行延遲執(zhí)行,保證所有任務(wù)都能夠正常執(zhí)行完成.MDAS 策略是一種多維搜索調(diào)整策略,在邊緣服務(wù)器資源受限時(shí),通過判斷計(jì)算資源和網(wǎng)絡(luò)資源是否發(fā)生沖突,來動(dòng)態(tài)調(diào)整任務(wù)的卸載位置以達(dá)到降低延遲的效果.接下來,文獻(xiàn)[22,38]分別通過調(diào)整移動(dòng)終端數(shù)量、虛擬機(jī)數(shù)量和網(wǎng)絡(luò)帶寬這3 個(gè)參數(shù)對(duì)上述4個(gè)策略的性能進(jìn)行對(duì)比分析,以及測(cè)試權(quán)重因子α和β對(duì)MSTDOS 卸載策略性能的影響和測(cè)試MEC 服務(wù)器性能瓶頸.

5.2.1 移動(dòng)終端數(shù)量的影響

本組實(shí)驗(yàn)研究應(yīng)用數(shù)量對(duì)不同卸載策略的影響,具體的參數(shù)配置見表4.

Table 4 Environment configuration of experiment 1表4 實(shí)驗(yàn)1 的環(huán)境配置

本實(shí)驗(yàn)中,邊緣服務(wù)器有200 個(gè)虛擬機(jī),網(wǎng)絡(luò)帶寬取8Mbps,移動(dòng)終端選取上面提到的4 款手機(jī),主要研究移動(dòng)終端數(shù)量不斷增加時(shí)對(duì)卸載策略性能的影響.具體的實(shí)驗(yàn)結(jié)果如圖10 所示.

Fig.10 Impact of mobile terminals’ number on average completion time and average energy consumption圖10 移動(dòng)終端數(shù)量對(duì)平均完成時(shí)間和平均能耗的影響

從圖10(a)和圖10(b)可知:隨著移動(dòng)終端數(shù)量的增加,SearchAdjust 策略、MDSA 策略和MSTDOS 策略的應(yīng)用平均完成時(shí)間和終端平均能耗都會(huì)明顯的增加;而AllInMobile 策略所有組件都在本地執(zhí)行,不受移動(dòng)終端數(shù)量的影響,且其平均完成時(shí)間和平均能耗開銷較大.其中,MSTDOS 策略與MDSA 策略相比,兩者平均完成時(shí)間較接近,有一點(diǎn)劣勢(shì);但在平均能耗上有較大的優(yōu)勢(shì).主要是由于在移動(dòng)終端可用電量不充足時(shí),MSTDOS 策略以犧牲一部分完成時(shí)間的代價(jià)來獲得更低的平均能耗,而MDSA 策略只關(guān)注于減少平均完成時(shí)間,忽視了終端能耗.其中,MSTDOS 策略與SearchAdjust 策略相比,當(dāng)移動(dòng)終端數(shù)量較小時(shí),兩者平均完成時(shí)間非常接近,在平均能耗上有點(diǎn)優(yōu)勢(shì);當(dāng)移動(dòng)終端數(shù)量較大時(shí),在平均完成時(shí)間有明顯優(yōu)勢(shì),而平均能耗很接近.因?yàn)楫?dāng)移動(dòng)終端數(shù)較少時(shí),邊緣服務(wù)器資源充足,MSTDOS 策略和SearchAdjust 策略都能取得較好的性能.但移動(dòng)終端數(shù)量的增加,大量的移動(dòng)終端會(huì)同時(shí)向邊緣服務(wù)器提交卸載請(qǐng)求,MSTDOS 策略考慮到移動(dòng)終端之間卸載策略的影響,能夠動(dòng)態(tài)地調(diào)整某些應(yīng)用組件的執(zhí)行位置,縮短了組件在邊緣服務(wù)器上的等待時(shí)間;而SearchAdjust 策略并不會(huì)做出類似MSTDOS 策略的調(diào)整過程,對(duì)于卸載到邊緣服務(wù)器的組件只考慮了延遲執(zhí)行,這會(huì)增加額外的等待時(shí)間,導(dǎo)致應(yīng)用性能的衰減.

5.2.2 邊緣服務(wù)器虛擬機(jī)數(shù)量的影響

本組實(shí)驗(yàn)研究邊緣服務(wù)器虛擬機(jī)個(gè)數(shù)對(duì)不同卸載策略的影響,具體參數(shù)配置見表5.

Table 5 Environment configuration of experiment 2表5 實(shí)驗(yàn)2 的環(huán)境配置

本實(shí)驗(yàn)中,移動(dòng)終端數(shù)量為500 個(gè),網(wǎng)絡(luò)帶寬為8Mbps,移動(dòng)終端選取上面提到的4 款手機(jī),主要研究邊緣服務(wù)器上虛擬機(jī)不斷增加時(shí)對(duì)卸載策略性能的影響.具體的實(shí)驗(yàn)結(jié)果如圖11 所示.

Fig.11 Impact of virtual machines’number on average completion time and average energy consumption圖11 虛擬機(jī)數(shù)量對(duì)平均完成時(shí)間和平均能耗的影響

從圖11(a)和圖11(b)可知:隨著邊緣服務(wù)器虛擬機(jī)數(shù)量的增加,SearchAdjust 策略、MDSA 策略和MSTDOS策略的應(yīng)用平均完成時(shí)間和終端平均能耗都會(huì)明顯的降低.主要由于隨著虛擬機(jī)數(shù)量增多,應(yīng)用對(duì)虛擬機(jī)資源的競(jìng)爭(zhēng)得以緩解,邊緣服務(wù)器能提供足夠的資源同時(shí)服務(wù)多個(gè)終端的請(qǐng)求.而AllInMobile 策略所有組件都在本地執(zhí)行,虛擬機(jī)數(shù)量的變化對(duì)其性能沒有影響,且其平均完成時(shí)間和平均能耗開銷較大.其中,MSTDOS 策略與MDSA 策略相比,兩者平均完成時(shí)間較接近;但在平均能耗上有較大的優(yōu)勢(shì).主要是由于兩者策略的專注點(diǎn)不同,MSTDOS 策略是折中平均完成時(shí)間和平均能耗,在移動(dòng)終端可用電量不充足時(shí),為了降低平均能耗而犧牲一部分完成時(shí)間;但MDSA 策略主要針對(duì)減少平均完成時(shí)間,沒有考慮如何降低終端能耗,從而取得了最優(yōu)的平均完成時(shí)間,而導(dǎo)致平均完成能耗比較高.其中,MSTDOS 策略與SearchAdjust 策略相比,當(dāng)虛擬機(jī)數(shù)量較小時(shí),在平均完成時(shí)間和平均能耗上都有優(yōu)勢(shì);當(dāng)虛擬機(jī)數(shù)量較大時(shí),平均完成時(shí)間和平均能耗都非常接近.因?yàn)樘摂M機(jī)數(shù)量較少時(shí),用戶數(shù)大于虛擬機(jī)數(shù)量,導(dǎo)致用戶請(qǐng)求對(duì)虛擬機(jī)資源的競(jìng)爭(zhēng)激烈.此時(shí),MSTDOS 策略會(huì)采取動(dòng)態(tài)調(diào)整機(jī)制為應(yīng)用做出近似最優(yōu)的卸載決策,盡可能地降低所有應(yīng)用的平均完成時(shí)間和終端平均能耗,而SearchAdjust 策略對(duì)于卸載到邊緣服務(wù)器的請(qǐng)求,采用推遲執(zhí)行的方法,應(yīng)用之間的等待時(shí)間會(huì)大大增加,導(dǎo)致應(yīng)用性能較差.但虛擬機(jī)數(shù)量較大時(shí),邊緣服務(wù)器資源充足,能夠同時(shí)處理的用戶請(qǐng)求量大.此時(shí),MSTDOS 策略和SearchAdjust 策略在平均完成時(shí)間和平均能耗上都能取得較好的性能.

5.2.3 網(wǎng)絡(luò)帶寬的影響

本組實(shí)驗(yàn)研究網(wǎng)絡(luò)帶寬對(duì)不同卸載策略的影響,具體參數(shù)配置見表6.

Table 6 Environment configuration of experiment 3表6 實(shí)驗(yàn)3 的環(huán)境配置

本實(shí)驗(yàn)中,移動(dòng)終端數(shù)量有500 個(gè),邊緣服務(wù)器提供200 個(gè)虛擬機(jī),移動(dòng)終端選取上面提到的4 款手機(jī),主要研究網(wǎng)絡(luò)帶寬不斷增加時(shí)對(duì)卸載策略性能的影響.實(shí)驗(yàn)具體結(jié)果如圖12 所示.

Fig.12 Impact of network bandwidth on average completion time and average energy consumption圖12 網(wǎng)絡(luò)帶寬對(duì)平均完成時(shí)間和平均能耗的影響

從圖12(a)和圖12(b)可知:AllInMobile 策略由于所有的組件都在本地執(zhí)行,網(wǎng)絡(luò)帶寬的變化對(duì)其沒有影響,且其平均完成時(shí)間和平均能耗的開銷較大.而SearchAdjust 策略、MDSA 策略和MSTDOS 策略的應(yīng)用平均完成時(shí)間和終端平均能耗都與網(wǎng)絡(luò)帶寬呈負(fù)相關(guān)關(guān)系.隨著網(wǎng)絡(luò)帶寬的增加,數(shù)據(jù)傳輸?shù)难舆t會(huì)減小,更多的組件會(huì)卸載到邊緣服務(wù)器上執(zhí)行,從而降低了應(yīng)用平均完成時(shí)間和終端平均能耗.3 種策略的性能隨著網(wǎng)絡(luò)帶寬的增加最初變化明顯,而后趨近于平穩(wěn).主要是因?yàn)榫W(wǎng)絡(luò)帶寬決定著移動(dòng)終端與邊緣服務(wù)器之間數(shù)據(jù)的傳輸速率與應(yīng)用傳輸時(shí)間成反比,隨著網(wǎng)絡(luò)帶寬的增大,對(duì)應(yīng)用傳輸時(shí)間的影響越來越小,從而對(duì)決策性能的提升逐漸減低.其中,MSTDOS 策略與MDSA 策略相比,在平均完成時(shí)間上存在劣勢(shì);但在平均能耗上有較大的優(yōu)勢(shì).主要是由于MSTDOS 策略側(cè)重于平均完成時(shí)間和平均能耗的均衡,而MDSA 策略側(cè)重于減少平均完成時(shí)間.在移動(dòng)終端可用電量不充足時(shí),前者為了得到較低的平均能耗以犧牲部分完成時(shí)間為代價(jià),而后者只關(guān)注于減少平均完成時(shí)間,忽視了終端能耗.其中,MSTDOS 策略與SearchAdjust 策略相比,在平均完成時(shí)間和平均能耗上都有一定的優(yōu)勢(shì).主要是由于邊緣服務(wù)器資源有限,用戶請(qǐng)求會(huì)對(duì)資源產(chǎn)生競(jìng)爭(zhēng).此時(shí),MSTDOS 策略考慮到多個(gè)終端之間會(huì)相互影響,能夠根據(jù)邊緣服務(wù)器的狀態(tài)信息調(diào)整應(yīng)用的卸載策略,為所有應(yīng)用做出較優(yōu)的卸載決策,而SearchAdjust 策略只是延遲組件的執(zhí)行,并沒有采取相應(yīng)措施進(jìn)行調(diào)整.

5.2.4 權(quán)重因子α和β的影響

本組實(shí)驗(yàn)研究權(quán)重因子α和β對(duì)平均完成時(shí)間和平均能耗的影響.α和β的取值依賴于移動(dòng)終端當(dāng)前可用電量的多少,且滿足α+β=1.具體參數(shù)配置見表7.

Ta ble 7 Environment configuration of experiment 4表7 實(shí)驗(yàn)4 的環(huán)境配置

本實(shí)驗(yàn)中,移動(dòng)終端數(shù)量有500 個(gè),邊緣服務(wù)器提供200 個(gè)虛擬機(jī),網(wǎng)絡(luò)帶寬取8Mbps,移動(dòng)終端選取上面提到的4 款手機(jī),主要研究移動(dòng)終端可用電量充足和不足時(shí)對(duì)卸載策略性能的影響,實(shí)驗(yàn)具體結(jié)果如圖13 所示.

從圖13 中可以看出:隨著權(quán)重因子α的減少,用戶的平均完成時(shí)間是增加的,存在負(fù)相關(guān)關(guān)系;而終端平均能耗卻相應(yīng)減少,存在正相關(guān)關(guān)系.主要原因是:當(dāng)α的值較大時(shí),意味著移動(dòng)設(shè)備有著充足的電量,用戶更關(guān)心減少應(yīng)用的完成時(shí)間;相反,當(dāng)α的值較小時(shí),β的值較大,意味著移動(dòng)設(shè)備電量不充足.在這種情況下,執(zhí)行能耗的權(quán)重比平均完成時(shí)間的更高,才能有效地降低應(yīng)用執(zhí)行能耗.

Fig.13 Impact of mobile terminal’s available batter power on average completion time and average energy consumption圖13 移動(dòng)終端可用電量對(duì)平均完成時(shí)間和平均能耗的影響

5.2.5 MEC 服務(wù)器性能瓶頸測(cè)試

本組實(shí)驗(yàn)研究服務(wù)器的性能瓶頸,即對(duì)于一定數(shù)量的虛擬機(jī)能夠支持的最大用戶數(shù).實(shí)驗(yàn)配置見表8.

Table 8 Environment configuration of experiment 5表8 實(shí)驗(yàn)5 的環(huán)境配置

為了驗(yàn)證MEC 服務(wù)器的性能瓶頸,本文選擇與AllInMobile 策略進(jìn)行實(shí)驗(yàn)比較.在AllInMobile 策略中,人臉識(shí)別應(yīng)用的所有組件都在移動(dòng)終端上執(zhí)行,通過實(shí)驗(yàn)測(cè)得應(yīng)用平均執(zhí)行時(shí)間是515ms.人臉識(shí)別應(yīng)用的執(zhí)行時(shí)間一般分布在370 ms～620ms[39],AllInMobile 策略的結(jié)果在合理范圍內(nèi).最終實(shí)驗(yàn)測(cè)試結(jié)果如圖14 所示.

Fig.14 Performance bottlenecks of MEC server圖14 MEC 服務(wù)器的性能瓶頸

如圖14 所示:當(dāng)MEC 服務(wù)器的虛擬機(jī)數(shù)量變化時(shí),通過調(diào)節(jié)提交卸載請(qǐng)求的用戶數(shù)目來測(cè)試MEC 服務(wù)器的性能瓶頸.對(duì)于MEC 服務(wù)器上指定數(shù)量虛擬機(jī),不斷地調(diào)節(jié)移動(dòng)用戶數(shù)目,當(dāng)MSTDOS 策略的執(zhí)行性能低于AllInMobile 策略的執(zhí)行性能時(shí)停止調(diào)節(jié),將此時(shí)的用戶數(shù)量作為MEC 服務(wù)器支撐的最大用戶數(shù).例如:在MEC服務(wù)器擁有50 臺(tái)虛擬機(jī)的情況下,當(dāng)用戶數(shù)量小于1 100 時(shí),MSTDOS 策略的執(zhí)行性能高于AllInMobile 策略的執(zhí)行性能;而一旦用戶數(shù)量超過1 100 時(shí),MSTDOS 策略的執(zhí)行性能將會(huì)下降,同時(shí)低于AllInMobile 策略的應(yīng)用性能.因此,我們能夠得出一個(gè)結(jié)論:有50 臺(tái)虛擬機(jī)時(shí),MEC 服務(wù)器最多能夠支撐1 100 個(gè)用戶,則將此環(huán)境下1 100 個(gè)用戶作為MEC 服務(wù)器的性能瓶頸.

6 總結(jié)與展望

本文針對(duì)邊緣服務(wù)器資源受限的多終端任務(wù)卸載問題,提出了一種面向多用戶的串行任務(wù)動(dòng)態(tài)卸載策略MSTDOS.該策略根據(jù)收集的移動(dòng)終端信息和邊緣服務(wù)器狀態(tài)信息,動(dòng)態(tài)地為所有應(yīng)用做出近似最優(yōu)的卸載決策.最后進(jìn)行一系列實(shí)驗(yàn),對(duì)MSTDOS 的性能進(jìn)行了評(píng)測(cè).實(shí)驗(yàn)結(jié)果表明:本文提出的卸載策略在邊緣服務(wù)器資源受限的多終端任務(wù)卸載場(chǎng)景下,在平均完成時(shí)間方面要優(yōu)于SearchAdjust 策略和AllInMobile 策略,較劣于MDSA 策略;而在平均能耗方面與SearchAdjust 策略比較接近,比AllInMobile 策略和MDSA 策略有明顯優(yōu)勢(shì).

本文研究的任務(wù)卸載問題默認(rèn)移動(dòng)終端的位置是固定的,因此,將來的工作可以考慮用戶移動(dòng)性導(dǎo)致網(wǎng)絡(luò)連接的變化,將任務(wù)卸載問題與移動(dòng)性管理問題相結(jié)合來開展研究工作.此外,當(dāng)前的研究工作主要考慮了邊緣服務(wù)器只部署在單個(gè)固定的地理位置,其資源有限的特點(diǎn)會(huì)影響多終端任務(wù)卸載的應(yīng)用性能,因而可以考慮部署在多個(gè)地理位置的邊緣服務(wù)器場(chǎng)景下,研究多個(gè)終端的任務(wù)卸載問題.