龍隆，劉子辰，陸在旺,2，張玉成,2，李蕾,2

（1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190；2.中國(guó)科學(xué)院大學(xué)計(jì)算技術(shù)研究所，北京 100049）

0 引言

隨著移動(dòng)通信與物聯(lián)網(wǎng)的高速發(fā)展，許多計(jì)算密集和時(shí)延敏感應(yīng)用（如無(wú)人駕駛、圖像識(shí)別以及自然語(yǔ)言處理等）產(chǎn)生，這類(lèi)具有低時(shí)延高可靠特點(diǎn)的應(yīng)用對(duì)終端設(shè)備的計(jì)算能力提出較高要求[1]。由于計(jì)算能力有限的終端設(shè)備在處理這類(lèi)應(yīng)用時(shí)將產(chǎn)生較高的任務(wù)時(shí)延，因此如何降低應(yīng)用處理時(shí)延是目前亟待解決的關(guān)鍵問(wèn)題之一。移動(dòng)云計(jì)算（MCC,mobile cloud computing）技術(shù)的出現(xiàn)很好地解決了終端計(jì)算能力受限的問(wèn)題。MCC 的目標(biāo)是將云端豐富的計(jì)算資源擴(kuò)展至資源受限的終端設(shè)備，從而增強(qiáng)終端設(shè)備潛在的計(jì)算能力[2-4]。終端設(shè)備與云服務(wù)器間較遠(yuǎn)的通信距離所產(chǎn)生的網(wǎng)絡(luò)時(shí)延使單純依靠MCC 無(wú)法滿(mǎn)足時(shí)延敏感型應(yīng)用程序的時(shí)延要求。為了克服以上問(wèn)題，并對(duì)MCC 技術(shù)進(jìn)行補(bǔ)充，移動(dòng)邊緣計(jì)算（MEC,mobile edge computing）作為一種新的技術(shù)被提出[5-6]。移動(dòng)邊緣計(jì)算主要由基站及其邊緣服務(wù)器組成。當(dāng)終端設(shè)備執(zhí)行計(jì)算任務(wù)時(shí)，由基站與服務(wù)器組成的邊緣節(jié)點(diǎn)可以就近為這些終端提供計(jì)算、通信以及數(shù)據(jù)存儲(chǔ)等服務(wù)，從而降低任務(wù)執(zhí)行時(shí)延、提高系統(tǒng)性能。目前，基于MEC 網(wǎng)絡(luò)的任務(wù)卸載和資源分配等問(wèn)題已有相關(guān)研究。文獻(xiàn)[7-9]在不同應(yīng)用場(chǎng)景下以最大化能效為目標(biāo)，對(duì)系統(tǒng)頻譜資源和功耗等進(jìn)行聯(lián)合優(yōu)化。文獻(xiàn)[10-11]分別以最小化能耗、時(shí)延為目標(biāo)，對(duì)計(jì)算與頻譜資源進(jìn)行聯(lián)合優(yōu)化。然而在實(shí)際應(yīng)用中，邊緣服務(wù)器的計(jì)算資源與存儲(chǔ)資源是有限的，過(guò)多的計(jì)算請(qǐng)求必然為邊緣服務(wù)器帶來(lái)較高的計(jì)算與存儲(chǔ)壓力，進(jìn)而影響系統(tǒng)性能。MCC 與MEC 融合網(wǎng)絡(luò)下的資源分配與卸載方案為解決以上問(wèn)題提供了新的解決思路。在MCC 與MEC 融合的網(wǎng)絡(luò)架構(gòu)中，終端設(shè)備進(jìn)行任務(wù)請(qǐng)求時(shí)，既可以在本地執(zhí)行，也可以在邊緣服務(wù)器或云端執(zhí)行。因此，該網(wǎng)絡(luò)架構(gòu)可以為終端提供更高效且更靈活的卸載服務(wù)，從而滿(mǎn)足不同的服務(wù)需求。目前已有相關(guān)研究表明，在三級(jí)網(wǎng)絡(luò)架構(gòu)下通過(guò)卸載決策與資源分配聯(lián)合優(yōu)化的方式可以提升網(wǎng)絡(luò)性能[12-13]。在MEC 與MCC 融合的集中式網(wǎng)絡(luò)下，文獻(xiàn)[12]對(duì)卸載決策與資源進(jìn)行聯(lián)合優(yōu)化，以降低所有終端的任務(wù)時(shí)延；文獻(xiàn)[13]以最大化系統(tǒng)收益為目標(biāo)，對(duì)任務(wù)卸載與資源分配進(jìn)行聯(lián)合優(yōu)化設(shè)計(jì)。

上述研究從不同方面解決任務(wù)卸載與資源分配聯(lián)合優(yōu)化問(wèn)題，但是這些研究忽略了任務(wù)卸載與服務(wù)緩存耦合性對(duì)系統(tǒng)性能的影響。這里的服務(wù)緩存是指將與計(jì)算任務(wù)相關(guān)的數(shù)據(jù)庫(kù)、應(yīng)用程序、函數(shù)庫(kù)以及相關(guān)代碼等放在邊緣服務(wù)中，從而支持不同類(lèi)型的應(yīng)用程序。從任務(wù)卸載角度可以將現(xiàn)有MEC 研究分為兩大類(lèi)，即計(jì)算任務(wù)完全卸載與計(jì)算任務(wù)部分卸載。完全卸載模型適用于高度集成或相對(duì)簡(jiǎn)單的任務(wù)，如自然語(yǔ)言處理、導(dǎo)航等任務(wù)，這些任務(wù)不能被分割，并且只能在移動(dòng)設(shè)備上執(zhí)行或者作為一個(gè)整體由邊緣服務(wù)器執(zhí)行。部分卸載模型適用于可分割的任務(wù)，如圖像識(shí)別、增強(qiáng)現(xiàn)實(shí)（AR,augmented reality）應(yīng)用等，這類(lèi)應(yīng)用的任務(wù)可以被分割為多個(gè)子任務(wù)通過(guò)并行或串行的方式執(zhí)行。與完全卸載模型相比，基于部分卸載模型的資源分配更加合理，資源利用率也更高。目前，關(guān)于服務(wù)緩存與資源分配已有相關(guān)研究。文獻(xiàn)[14]以最小化供應(yīng)商成本為目標(biāo)，提出了一種整數(shù)線性規(guī)劃和隨機(jī)搜索算法，對(duì)邊緣節(jié)點(diǎn)間的服務(wù)緩存資源進(jìn)行優(yōu)化。文獻(xiàn)[15]以最小化服務(wù)緩存總成本為目標(biāo)，對(duì)邊緣服務(wù)器的位置和用戶(hù)服務(wù)需求進(jìn)行聯(lián)合優(yōu)化。文獻(xiàn)[16]以最小化時(shí)延與成本為目標(biāo)，對(duì)邊緣服務(wù)器的內(nèi)容緩存進(jìn)行協(xié)同優(yōu)化。盡管以上研究通過(guò)任務(wù)卸載與服務(wù)緩存優(yōu)化使系統(tǒng)性能得到提升，但都是基于任務(wù)不可分的情況進(jìn)行的資源分配優(yōu)化，而對(duì)任務(wù)可分的情況不適用。

大多數(shù)復(fù)雜的應(yīng)用程序由多個(gè)不同的執(zhí)行組件組成，如執(zhí)行實(shí)時(shí)面部識(shí)別任務(wù)時(shí)需要將其分為4 個(gè)子任務(wù)分別處理，即人臉檢測(cè)、圖像處理與特征提取、人臉識(shí)別。這些子任務(wù)所需的計(jì)算資源、存儲(chǔ)資源以及帶寬資源各不相同。因此，如何基于部分任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化是目前亟待解決問(wèn)題。文獻(xiàn)[17]通過(guò)構(gòu)建服務(wù)鏈模型，在存儲(chǔ)資源以及計(jì)算資源約束下以最小化網(wǎng)絡(luò)響應(yīng)時(shí)延為目標(biāo)，通過(guò)開(kāi)放馬爾可夫排隊(duì)網(wǎng)絡(luò)模型構(gòu)建邊緣節(jié)點(diǎn)服務(wù)調(diào)度模型，并對(duì)緩存決策與計(jì)算資源聯(lián)合優(yōu)化，但在任務(wù)卸載過(guò)程中忽略終端設(shè)備以及云服務(wù)器資源等可用資源。文獻(xiàn)[18]基于部分卸載模型，在計(jì)算資源約束下對(duì)服務(wù)緩存與任務(wù)卸載進(jìn)行聯(lián)合優(yōu)化研究，但其假設(shè)帶寬資源均勻分配，導(dǎo)致計(jì)算數(shù)據(jù)量較大的任務(wù)得到較少的帶寬資源而產(chǎn)生較高時(shí)延，計(jì)算數(shù)據(jù)量較少的任務(wù)得到較多的帶寬資源造成資源浪費(fèi)。另外，文獻(xiàn)[18]并未對(duì)邊緣節(jié)點(diǎn)的存儲(chǔ)空間進(jìn)行約束，這意味著在該研究中邊緣服務(wù)端擁有無(wú)限大的存儲(chǔ)空間，可以緩存所有任務(wù)執(zhí)行所需的相關(guān)數(shù)據(jù)，這在實(shí)際應(yīng)用場(chǎng)景下顯然不合理。

綜上所述，本文將在終端、邊緣服務(wù)以及云構(gòu)成的三層網(wǎng)絡(luò)架構(gòu)下，綜合考慮無(wú)線帶寬資源、計(jì)算資源以及存儲(chǔ)資源等因素。通過(guò)計(jì)算、通信、存儲(chǔ)融合的思想，以最小化所有終端設(shè)備的任務(wù)時(shí)延為目標(biāo)，綜合考慮存儲(chǔ)資源、計(jì)算資源、卸載決策以及任務(wù)卸載比例等對(duì)任務(wù)時(shí)延的影響，提出一種服務(wù)緩存與資源分配的聯(lián)合優(yōu)化算法。具體創(chuàng)新點(diǎn)介紹如下。

1) 構(gòu)建了一個(gè)由多用戶(hù)、邊緣服務(wù)器以及云服務(wù)器組成的三層網(wǎng)絡(luò)架構(gòu)，每個(gè)用戶(hù)的計(jì)算任務(wù)可以通過(guò)部分卸載的方式將任務(wù)分別卸載至本地、邊緣服務(wù)器或云服務(wù)器。引入了最小化終端任務(wù)時(shí)延模型，考慮了用戶(hù)計(jì)算資源、邊緣服務(wù)的計(jì)算資源、存儲(chǔ)資源以及帶寬資源等因素對(duì)時(shí)延的影響。

2) 提出了服務(wù)緩存與資源分配聯(lián)合（JSCRA,joint service caching and resource allocation）優(yōu)化策略。首先，將原問(wèn)題的連續(xù)變量與離散變量進(jìn)行解耦，變?yōu)? 個(gè)子問(wèn)題，即服務(wù)緩存決策問(wèn)題、計(jì)算資源與通信資源聯(lián)合優(yōu)化問(wèn)題。其次，基于重構(gòu)線性化技術(shù)（RLT,reformulation linearization technique）、松弛以及凸優(yōu)化方法對(duì)2 個(gè)子問(wèn)題進(jìn)行交替迭代優(yōu)化。最后，獲得問(wèn)題次優(yōu)解。

3) 仿真結(jié)果表明，與隨機(jī)緩存和資源分配（RCRA,random caching and resource allocation）策略相比，所提策略在收斂速度和性能表現(xiàn)上都有明顯優(yōu)勢(shì)，可以獲得更低的任務(wù)時(shí)延。

1 系統(tǒng)模型

1.1 集中式移動(dòng)邊緣網(wǎng)絡(luò)模型

集中式移動(dòng)邊緣網(wǎng)絡(luò)如圖1 所示。從圖1 可以看出，集中式移動(dòng)邊緣網(wǎng)絡(luò)由云服務(wù)器、單一服務(wù)節(jié)點(diǎn)（由邊緣服務(wù)器與基站組成）以及L個(gè)具有計(jì)算與通信能力的終端組成。這里的終端泛指具有計(jì)算能力的終端設(shè)備，如手機(jī)、平板電腦、車(chē)輛等。終端個(gè)數(shù)表示為L(zhǎng)={1,2,…,L}，i∈L。云服務(wù)器與服務(wù)節(jié)點(diǎn)通過(guò)光纖進(jìn)行有線連接，為終端提供穩(wěn)定的通信、計(jì)算以及存儲(chǔ)服務(wù)。這里的云服務(wù)器主要由云服務(wù)器集群組成，因此擁有豐富的計(jì)算資源與存儲(chǔ)資源。

圖1 集中式移動(dòng)邊緣網(wǎng)絡(luò)

在圖1 所示場(chǎng)景中，服務(wù)節(jié)點(diǎn)不僅可以為終端提供通信、計(jì)算以及存儲(chǔ)資源，而且扮演著協(xié)調(diào)器的角色，即根據(jù)終端的任務(wù)請(qǐng)求提供存儲(chǔ)決策以及計(jì)算決策。這里假設(shè)邊緣服務(wù)器存儲(chǔ)計(jì)算服務(wù)的最大存儲(chǔ)容量為C，最大計(jì)算能力為F。計(jì)算服務(wù)數(shù)據(jù)主要由數(shù)據(jù)庫(kù)、數(shù)據(jù)字典以及相關(guān)的應(yīng)用代碼組成，其中每一種應(yīng)用代表一個(gè)類(lèi)型的計(jì)算任務(wù)。此外，由于存儲(chǔ)是一個(gè)長(zhǎng)期的過(guò)程，因此需要服務(wù)緩存進(jìn)行定時(shí)更新。本文認(rèn)為系統(tǒng)在離散的時(shí)間段中運(yùn)行，每個(gè)時(shí)間段的持續(xù)時(shí)間與服務(wù)緩存和任務(wù)分配決策更新的時(shí)間尺度相匹配。本文對(duì)其中一個(gè)時(shí)間段進(jìn)行研究，忽略其他時(shí)間段的索引[18]。在一個(gè)時(shí)間段的開(kāi)始階段，每個(gè)終端隨機(jī)請(qǐng)求一個(gè)計(jì)算任務(wù)，其中一類(lèi)計(jì)算任務(wù)對(duì)應(yīng)一類(lèi)計(jì)算服務(wù)。這里假設(shè)存在計(jì)算服務(wù)K={1,2,…,K}，表示用戶(hù)i請(qǐng)求計(jì)算服務(wù)Ai相應(yīng)的任務(wù)，Ai∈K，其中，表示終端i執(zhí)行服務(wù)Ai相關(guān)任務(wù)的輸入數(shù)據(jù)大小，si表示執(zhí)行1 bit 數(shù)據(jù)所需循環(huán)數(shù)。為了便于分析，本文做出如下合理假設(shè)。

1) 服務(wù)節(jié)點(diǎn)已知信道狀態(tài)信息（CSI,channel state information）、每個(gè)任務(wù)輸入數(shù)據(jù)的大小以及執(zhí)行任務(wù)所需的循環(huán)數(shù)?；谝陨霞僭O(shè)，可以得到優(yōu)化的卸載決策以及資源分配[19]。

2)每種應(yīng)用的計(jì)算結(jié)果數(shù)據(jù)都遠(yuǎn)小于計(jì)算輸入數(shù)據(jù)，因此忽略計(jì)算結(jié)果的回程鏈路傳輸時(shí)延[20]。

1.2 通信模型

本文采用正交頻分復(fù)用的方式將頻譜資源分配給終端設(shè)備，頻譜的總帶寬為B。由于每個(gè)終端設(shè)備將計(jì)算任務(wù)卸載至服務(wù)節(jié)點(diǎn)時(shí)會(huì)占用上行頻譜資源，因此終端i執(zhí)行服務(wù)Ai相關(guān)任務(wù)的上行傳輸速率可以表示為[12]

其中，為終端上傳數(shù)據(jù)所占上行帶寬百分比，Pi,s為終端的發(fā)送功率，hi,B為基站與終端間的信道衰落系數(shù)，d為終端與基站的距離，r為路徑損耗，σ2為信道的噪聲功率。

1.3 服務(wù)緩存模型

若邊緣服務(wù)器存儲(chǔ)計(jì)算服務(wù)，則意味著服務(wù)節(jié)點(diǎn)可以處理相關(guān)的計(jì)算任務(wù)，否則將任務(wù)交由云服務(wù)器執(zhí)行。由于邊緣服務(wù)器的存儲(chǔ)空間有限，故無(wú)法滿(mǎn)足所有終端設(shè)備的計(jì)算請(qǐng)求，因此邊緣服務(wù)器需要對(duì)所緩存的服務(wù)數(shù)據(jù)進(jìn)行決策。這里將服務(wù)端的存儲(chǔ)決策表示為，∈ { 0,1}且Ai∈K，i∈L；表示服務(wù)器是否緩存終端設(shè)備請(qǐng)求的Ai，xAi=1表示服務(wù)器緩存計(jì)算服務(wù)Ai，=0表示服務(wù)器沒(méi)有緩存相應(yīng)的計(jì)算服務(wù)Ai。每個(gè)服務(wù)Ai所需存儲(chǔ)大小為，而邊緣服務(wù)器緩存決策受到存儲(chǔ)容量的限制，即

1.4 計(jì)算任務(wù)卸載模型

任務(wù)部分卸載意味著計(jì)算任務(wù)可以分解成多個(gè)大小不同的子任務(wù)。本文將基于卸載模型（即向代碼分區(qū)的應(yīng)用，如圖像識(shí)別，這類(lèi)應(yīng)用分為多個(gè)模塊，其中一個(gè)模塊的輸出結(jié)果為下一個(gè)模塊的輸入）進(jìn)行研究，接下來(lái)本文將在部分卸載模型下，對(duì)任務(wù)執(zhí)行時(shí)延模型進(jìn)行描述。

1) 當(dāng)計(jì)算服務(wù)Ai存儲(chǔ)在邊緣服務(wù)器時(shí)，任務(wù)可以在邊緣服務(wù)器執(zhí)行，此時(shí)任務(wù)執(zhí)行時(shí)延分析如下。

如果部分任務(wù)在服務(wù)節(jié)點(diǎn)卸載，任務(wù)卸載至邊緣服務(wù)器時(shí)，任務(wù)卸載百分比表示為1-，相應(yīng)的任務(wù)卸載至邊緣服務(wù)器的數(shù)據(jù)大小表示為。分配給終端設(shè)備的計(jì)算資源表示為，任務(wù)在邊緣服務(wù)器的執(zhí)行時(shí)延表示為

當(dāng)任務(wù)卸載至邊緣服務(wù)器時(shí)，終端設(shè)備將占用上行鏈路對(duì)數(shù)據(jù)進(jìn)行傳輸，此時(shí)上行鏈路的傳輸時(shí)延表示為

綜上所述，當(dāng)計(jì)算服務(wù)存儲(chǔ)在服務(wù)中心時(shí)，任務(wù)執(zhí)行總時(shí)延表示為

2) 當(dāng)計(jì)算服務(wù)Ai未存儲(chǔ)在邊緣服務(wù)器時(shí)，計(jì)算任務(wù)將在本地以及云端進(jìn)行部分卸載。

如果任務(wù)卸載至云服務(wù)器，卸載百分比表示為1-，其中，任務(wù)卸載至邊緣服務(wù)器的數(shù)據(jù)大小表示為?；谇拔募僭O(shè)，云服務(wù)器具有豐富的計(jì)算資源，所以任務(wù)執(zhí)行時(shí)延只與傳輸時(shí)延有關(guān)，即上行鏈路傳輸時(shí)延以及回程鏈路傳輸時(shí)延。因此，任務(wù)在云服務(wù)器執(zhí)行時(shí)其傳輸時(shí)延表示為

其中，R為邊緣服務(wù)與云服務(wù)器之間的傳輸速率。因此，計(jì)算服務(wù)存儲(chǔ)在云服務(wù)器時(shí)任務(wù)執(zhí)行總時(shí)延表示為

2 問(wèn)題的形式化描述

由于存儲(chǔ)是一個(gè)長(zhǎng)期統(tǒng)計(jì)的過(guò)程，因此其在短期內(nèi)變化很小，但計(jì)算與通信資源是實(shí)時(shí)的，需要根據(jù)不同用戶(hù)的任務(wù)需求實(shí)時(shí)變化。基于以上特點(diǎn)，本文考慮在當(dāng)前時(shí)間段內(nèi)對(duì)計(jì)算、通信以及存儲(chǔ)資源進(jìn)行聯(lián)合優(yōu)化。本文的主要目標(biāo)是在計(jì)算、通信、存儲(chǔ)資源約束條件下，對(duì)服務(wù)緩存決策x、上行頻譜資源θ、任務(wù)部分卸載百分比α和β，以及服務(wù)器計(jì)算資源f聯(lián)合優(yōu)化，以最小化所有終端設(shè)備執(zhí)行任務(wù)總時(shí)延。優(yōu)化目標(biāo)可以表示為

從P0 可以看出，約束條件C1表示分配給所有終端設(shè)備的計(jì)算資源總和小于或等于服務(wù)器的最大計(jì)算能力，C2 表示分配給所有終端設(shè)備的頻譜資源小于或等于總頻譜帶寬，C3 表示任務(wù)卸載比例，C4 表示服務(wù)緩存決策，C5 表示邊緣服務(wù)器可以緩存計(jì)算服務(wù)的最大容量。此外，P0 是由離散變量與連續(xù)變量組成的混合整數(shù)非線性規(guī)劃問(wèn)題，很難求解，因此需要設(shè)計(jì)一種新的優(yōu)化方法對(duì)該問(wèn)題進(jìn)行求解。

3 服務(wù)緩存與資源分配聯(lián)合優(yōu)化策略

為了解決以上問(wèn)題，本文提出一種面向任務(wù)卸載與服務(wù)緩存問(wèn)題的服務(wù)緩存與資源分配的聯(lián)合優(yōu)化策略，簡(jiǎn)稱(chēng)為服務(wù)緩存與資源分配的聯(lián)合優(yōu)化策略。首先，將原問(wèn)題的連續(xù)變量與離散變量進(jìn)行解耦，變?yōu)? 個(gè)子問(wèn)題，即服務(wù)緩存決策問(wèn)題以及計(jì)算資源與通信資源聯(lián)合優(yōu)化問(wèn)題；其次，在固定緩存決策基礎(chǔ)上對(duì)計(jì)算與通信資源分配問(wèn)題進(jìn)行求解；再次，在得到優(yōu)化的資源分配變量后對(duì)緩存決策進(jìn)行優(yōu)化；最后，通過(guò)循環(huán)迭代得到原問(wèn)題的解。

3.1 計(jì)算資源與通信資源聯(lián)合優(yōu)化

首先，初始化緩存決策；隨后，對(duì)計(jì)算與通信資源進(jìn)行聯(lián)合優(yōu)化。在給定緩存決策條件下，P0 變成由計(jì)算資源、帶寬資源以及任務(wù)卸載比例等連續(xù)變量組成的函數(shù)。接下來(lái)將對(duì)連續(xù)變量進(jìn)行求解。在給定初始緩存決策為x(0)后，多終端時(shí)延優(yōu)化函數(shù)表示為

相應(yīng)的優(yōu)化問(wèn)題表示為

緩存決策確定后，其相應(yīng)的約束條件同時(shí)發(fā)生變化，其約束條件將由C1變?yōu)镃6。為了避免除零情況的發(fā)生，對(duì)變量加入常量ε1、ε2，可表示為。最后將該變量代入式(10)以及對(duì)應(yīng)的約束條件中，得到新的函數(shù)以及約束條件。相應(yīng)的問(wèn)題表示為

由P2 可以看出，式(12)中存在2 個(gè)變量相乘的乘積項(xiàng)，因此該問(wèn)題是一個(gè)非凸優(yōu)化問(wèn)題。為了求解P2，需要對(duì)以上問(wèn)題進(jìn)行再次變換。

3.2 基于RLT 的問(wèn)題轉(zhuǎn)換

其中，{·}LS表示線性化步驟。將代入式(14)可得

其中，?i∈L。同理，對(duì)應(yīng)的RLT 因子積約束條件為

經(jīng)過(guò)以上變換后，得到新的優(yōu)化問(wèn)題P3 為

3.3 緩存優(yōu)化問(wèn)題的解決

獲得P1的解后，下面解決緩存決策問(wèn)題。首先，將獲得的資源分配方案α(0)、β(0)、θ(0)、f(0)代 入P0，得到緩存決策問(wèn)題P4 為

P4 是0-1 問(wèn)題，可以通過(guò)分支定界法對(duì)以上問(wèn)題進(jìn)行求解。然而，分支定界法在最壞的情況下需要運(yùn)算2k次，當(dāng)輸入數(shù)據(jù)量較小時(shí)，其復(fù)雜度是可接受的；隨著輸入數(shù)據(jù)量的增大，則很難在有效時(shí)間內(nèi)獲得近似最優(yōu)解。為了降低時(shí)間復(fù)雜度，本文將整型變量松弛成的連續(xù)變量。此時(shí)，P4 變?yōu)橥箖?yōu)化問(wèn)題，可以通過(guò)內(nèi)點(diǎn)法與KKT（Karush-Kuhn-Tucker）條件進(jìn)行求解。隨后采用四舍五入的方法對(duì)連續(xù)變量進(jìn)行恢復(fù)，這里將閾值簡(jiǎn)單設(shè)置為0.5。

3.4 算法描述

基于上述分析可知，邊緣服務(wù)器通過(guò)階段性獲取當(dāng)前接入終端的完整信息，執(zhí)行JSCRA 優(yōu)化策略，并將緩存決策以及資源分配結(jié)果發(fā)送至終端設(shè)備，從而最小化所有設(shè)備任務(wù)的執(zhí)行時(shí)延，具體步驟如算法1 所示。

算法1服務(wù)緩存與資源分配聯(lián)合優(yōu)化算法

初始化邊緣服務(wù)的緩存策略，終端發(fā)射功率pi,s，任務(wù)的輸入數(shù)據(jù)大小，每比特輸入數(shù)據(jù)所需的計(jì)算量si，最大迭代次數(shù)tmax，算法終止條件ξ。

步驟1在已知服務(wù)緩存策略基礎(chǔ)上，原問(wèn)題變換為連續(xù)非線性問(wèn)題，得到新問(wèn)題P2。

步驟2通過(guò)RLT 技術(shù)對(duì)P2 松弛，將非線性問(wèn)題變?yōu)橥箖?yōu)化問(wèn)題P3。

步驟3采用內(nèi)點(diǎn)法對(duì)P3 進(jìn)行求解，并得到在已知緩存決策條件下的資源分配方案。

步驟4將步驟3 得到的解代入P4，通過(guò)松弛法以及凸優(yōu)化方法得到相應(yīng)的卸載決策。

步驟5獲取步驟3 與步驟4 中目標(biāo)函數(shù)的差值，如果差值小于ξ或者迭代次數(shù)達(dá)到最大值tmax，則停止計(jì)算；否則，對(duì)步驟3 以及步驟4 進(jìn)行循環(huán)迭代。

4 仿真實(shí)驗(yàn)與性能評(píng)估

本節(jié)在MATLAB 2017b 上進(jìn)行仿真實(shí)驗(yàn)，并分析JSCRA 優(yōu)化策略的性能。此外，為了進(jìn)行性能對(duì)比，本文對(duì)以下基準(zhǔn)策略進(jìn)行了仿真。

完全本地卸載（LOC,local offloading completely）策略：所有任務(wù)均在終端本地進(jìn)行處理，此時(shí)假設(shè)本地終端存儲(chǔ)任務(wù)相關(guān)的服務(wù)數(shù)據(jù)[21]。

完全卸載至云（COC,cloud offloading completely）策略：任務(wù)相關(guān)服務(wù)數(shù)據(jù)全部存儲(chǔ)在云服務(wù)器，此時(shí)任務(wù)完全在云服務(wù)器執(zhí)行，而上行鏈路帶寬資源均勻分配給每個(gè)終端設(shè)備[18]。

隨機(jī)緩存與資源分配（RCRA,random caching and resource allocation）策略：在存儲(chǔ)約束條件下，邊緣服務(wù)器采用隨機(jī)緩存策略盡可能多地緩存服務(wù)內(nèi)容并在其基礎(chǔ)上對(duì)計(jì)算與帶寬資源進(jìn)行優(yōu)化[18]。

4.1 仿真參數(shù)設(shè)置

在仿真實(shí)驗(yàn)中，終端設(shè)備的數(shù)量為10，隨機(jī)分布在邊長(zhǎng)為500 m 的正方形區(qū)域內(nèi)。hi,B服從均值為1 的指數(shù)分布[22]，計(jì)算任務(wù)數(shù)據(jù)大小表示為ci且服從[100,200]KB 的均勻分布，si設(shè)置為1 500 cycle/bit。仿真參數(shù)設(shè)置如表1 所示。

表1 仿真參數(shù)設(shè)置

4.2 算法復(fù)雜度與收斂性分析

由于原始問(wèn)題P0 是混合整數(shù)非線性規(guī)劃問(wèn)題，通過(guò)窮舉法求解問(wèn)題的復(fù)雜度為O(2n)，呈現(xiàn)指數(shù)級(jí)增長(zhǎng)。所提算法將原始問(wèn)題P0 轉(zhuǎn)換成為P3 與P4，P3 為標(biāo)準(zhǔn)凸優(yōu)化問(wèn)題，可以通過(guò)內(nèi)點(diǎn)法解決，內(nèi)點(diǎn)法的復(fù)雜度為O(n3)；P4 為0-1 問(wèn)題，離散變量經(jīng)過(guò)松弛后為凸優(yōu)化問(wèn)題，其算法復(fù)雜度為O(n3)，此外，交替迭代次數(shù)的復(fù)雜度為O(n)，因此，所提算法總體復(fù)雜度為O(n3)。與窮舉法相比，所提算法復(fù)雜度大大降低。

算法收斂過(guò)程如圖2 所示。本文將通過(guò)窮舉法獲得的值作為最優(yōu)解。由于窮舉法非常耗時(shí)，因此一般在小規(guī)模場(chǎng)景下使用。由圖2 可以看出，所提算法通過(guò)迭代25 次快速收斂并接近最優(yōu)解，這表明所提算法性能非常接近于窮舉法的性能，并可以獲得近似最優(yōu)解。

圖2 算法收斂過(guò)程

4.3 仿真結(jié)果和分析

本節(jié)仿真結(jié)果是在配置有 Intelcorei59400F 2.9 GHz 處理器和 16 GB RAM 的臺(tái)式機(jī)上用MATLAB 2017b 實(shí)現(xiàn)的。在N=10，C=300 GB，R=1的條件下，邊緣服務(wù)器的計(jì)算能力和存儲(chǔ)能力對(duì)任務(wù)執(zhí)行時(shí)延的影響分別如圖3 和圖4 所示。

圖3 邊緣服務(wù)器的計(jì)算能力對(duì)任務(wù)執(zhí)行時(shí)延的影響

圖4 邊緣服務(wù)器的存儲(chǔ)能力對(duì)任務(wù)執(zhí)行時(shí)延的影響

從圖3 可以看出，隨著邊緣服務(wù)器的計(jì)算能力逐漸增大，所提JSCRA 優(yōu)化策略與RCRA 策略的任務(wù)執(zhí)行時(shí)延逐漸減小，而LOC 策略以及COC策略任務(wù)執(zhí)行時(shí)延保持不變。這是因?yàn)長(zhǎng)OC 策略的任務(wù)時(shí)延僅與本地計(jì)算能力有關(guān)，任務(wù)執(zhí)行時(shí)延與邊緣服務(wù)器所擁有的資源沒(méi)有關(guān)系，所以LOC策略的所有任務(wù)執(zhí)行時(shí)延保持不變。對(duì)于COC 策略而言，當(dāng)任務(wù)在云服務(wù)器執(zhí)行時(shí)，其任務(wù)執(zhí)行時(shí)延僅與無(wú)線帶寬資源以及回程鏈路傳輸速率有關(guān)，因此COC 策略的任務(wù)執(zhí)行時(shí)延不隨邊緣服務(wù)器計(jì)算能力的增大而改變。另外，從圖3 還可以看出，JSCRA 優(yōu)化策略在性能上略?xún)?yōu)于RCRA 策略，這是因?yàn)镴SCRA 優(yōu)化策略對(duì)服務(wù)緩存進(jìn)行合理優(yōu)化，使更多任務(wù)可以在邊緣服務(wù)器中執(zhí)行，因此性能優(yōu)于RCRA 策略。

從圖4 可以看出，隨著邊緣服務(wù)器的存儲(chǔ)能力逐漸提升，所提策略與RCRA 策略任務(wù)執(zhí)行時(shí)延逐漸減小，而LOC 策略以及COC 策略的任務(wù)執(zhí)行時(shí)延保持不變。所提策略與RCRA 策略相比可以減少10%的任務(wù)執(zhí)行時(shí)延，與COC 策略相比可以減少30%的任務(wù)執(zhí)行時(shí)延。LOC 策略的任務(wù)執(zhí)行時(shí)延僅與本地計(jì)算能力有關(guān)，COC 策略的任務(wù)執(zhí)行時(shí)延與帶寬資源以及回程鏈路傳輸速率有關(guān)，所以LOC 策略與COC 策略的任務(wù)執(zhí)行時(shí)延不隨邊緣服務(wù)器存儲(chǔ)能力的大小變化。此外，從圖4 可以看出，隨著邊緣服務(wù)器存儲(chǔ)能力的增加，與COC 策略相比，所提策略與RCRA 策略性能增益增大。這是因?yàn)楫?dāng)邊緣服務(wù)器存儲(chǔ)能力較小時(shí)，只能緩存部分計(jì)算服務(wù)，剩余服務(wù)將存儲(chǔ)在遠(yuǎn)端云服務(wù)器。此時(shí)，大多數(shù)任務(wù)將在云服務(wù)中執(zhí)行，因此所提策略與RCRA 策略的任務(wù)執(zhí)行時(shí)延性能略?xún)?yōu)于COC 策略。但是，隨著存儲(chǔ)能力的增加，邊緣服務(wù)器可以緩存的服務(wù)內(nèi)容增多，遠(yuǎn)端執(zhí)行任務(wù)比例逐漸降低，此時(shí)邊緣服務(wù)器計(jì)算資源被充分利用，因此所提策略與RCRA 策略的性能顯著優(yōu)于COC 算法。

任務(wù)輸入數(shù)據(jù)大小對(duì)任務(wù)執(zhí)行時(shí)延的影響如圖5 所示。從圖5 可以看出，任務(wù)輸入數(shù)據(jù)越大，所有策略的任務(wù)執(zhí)行時(shí)延越大，而所提策略的性能優(yōu)于其他策略。這是因?yàn)殡S著輸入數(shù)據(jù)量的增大，任務(wù)所需的計(jì)算資源與通信資源將會(huì)增多，所有策略的任務(wù)執(zhí)行時(shí)延逐漸增大。另外，由于所提策略對(duì)計(jì)算、通信以及存儲(chǔ)資源進(jìn)行聯(lián)合優(yōu)化，因此其性能優(yōu)于其他策略。

圖5 任務(wù)輸入數(shù)據(jù)大小對(duì)任務(wù)執(zhí)行時(shí)延的影響

邊緣服務(wù)器與遠(yuǎn)端云間傳輸速率對(duì)任務(wù)執(zhí)行時(shí)延的影響如圖6 所示。從圖6 可以看出，隨著邊緣服務(wù)器與遠(yuǎn)端云間的傳輸速率逐漸增大，所提策略與RCRA 策略、COC 策略的所有任務(wù)總時(shí)長(zhǎng)逐漸減小，當(dāng)R=5 時(shí)，上述3 種策略性能基本相同。這是因?yàn)楫?dāng)邊緣服務(wù)器與遠(yuǎn)端云間傳輸速率較小時(shí)，任務(wù)卸載至云服務(wù)器的時(shí)延大于在邊緣服務(wù)器的執(zhí)行時(shí)延，此時(shí)大部分任務(wù)將在邊緣服務(wù)器執(zhí)行，因此所提策略性能優(yōu)于RCRA 策略以及COC 策略。隨著傳輸速率增大，任務(wù)在云端執(zhí)行的時(shí)延與任務(wù)在邊緣服務(wù)器執(zhí)行時(shí)延越來(lái)越接近，因此所提策略與RCRA 策略以及COC 策略的性能差異將越來(lái)越小，這也表明所提策略在傳輸速率較小時(shí)可以獲得較高的性能增益。此外，LOC 策略任務(wù)執(zhí)行時(shí)延沒(méi)有變化，這是因?yàn)槿蝿?wù)本地時(shí)延與終端自身計(jì)算資源有關(guān)與邊緣服務(wù)器，而與云端間的傳輸速率無(wú)關(guān)。

圖6 邊緣服務(wù)器與遠(yuǎn)端云間傳輸速率對(duì)任務(wù)執(zhí)行時(shí)延的影響

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

在多終端、單服務(wù)節(jié)點(diǎn)以及云服務(wù)器組成的集中式移動(dòng)邊緣網(wǎng)絡(luò)下，針對(duì)任務(wù)卸載與服務(wù)緩存耦合性對(duì)任務(wù)時(shí)延的影響，本文提出了一種服務(wù)緩存與資源分配的聯(lián)合優(yōu)化策略。首先，在計(jì)算、通信以及存儲(chǔ)容量約束下，建立服務(wù)緩存與資源分配聯(lián)合優(yōu)化問(wèn)題。隨后，將原問(wèn)題進(jìn)行分解為2 個(gè)子問(wèn)題并通過(guò)重構(gòu)線性化方法、松弛以及凸優(yōu)化方法對(duì)其進(jìn)行交替迭代優(yōu)化。仿真結(jié)果表明，與RCRA 策略、LOC 策略和COC 策略相比，所提策略可以有效地降低系統(tǒng)時(shí)延并具有良好的收斂性。