緩存輔助邊緣計(jì)算的卸載決策與資源優(yōu)化分析

燕伯峰，劉宇鵬，殷 超，張 江，金 釗

（1.內(nèi)蒙古電力集團(tuán)有限責(zé)任公司營(yíng)銷服務(wù)部，內(nèi)蒙古 呼和浩特 010010；2.內(nèi)蒙古電力科學(xué)研究院，內(nèi)蒙古 呼和浩特 010010）

互聯(lián)網(wǎng)科技迅速發(fā)展，各種移動(dòng)端開始出現(xiàn)與興起，增強(qiáng)現(xiàn)實(shí)、虛擬游戲等所需的應(yīng)用數(shù)據(jù)對(duì)用戶的基礎(chǔ)設(shè)施要求標(biāo)準(zhǔn)進(jìn)一步提升。在這種情況下，很多科技研究人員開始通過(guò)運(yùn)用移動(dòng)邊緣計(jì)算技術(shù)將一些復(fù)雜性、能耗性較高的計(jì)算任務(wù)通過(guò)卸載的方式分配到用戶的移動(dòng)端，并為其提供各項(xiàng)計(jì)算服務(wù)與云儲(chǔ)存服務(wù)等，以此來(lái)滿足5G網(wǎng)絡(luò)低時(shí)延、低功耗、熱點(diǎn)內(nèi)容集中、任務(wù)大的應(yīng)用目標(biāo)，通過(guò)進(jìn)行對(duì)應(yīng)的部署緩存，可促使骨干網(wǎng)絡(luò)壓力與基站負(fù)載的降低，在一定程度上避免了設(shè)備過(guò)多的能源消耗，并解決了傳輸時(shí)延大等問題。但大量的數(shù)據(jù)從數(shù)據(jù)源上送至遠(yuǎn)端云數(shù)據(jù)中心的同時(shí)，會(huì)顯著地增加用戶端的壓力并導(dǎo)致巨大能量的消耗。因此針對(duì)邊緣網(wǎng)絡(luò)對(duì)應(yīng)的部署緩存情況，通過(guò)優(yōu)化卸載決策和資源分配方式，使用戶能耗得到降低，新的優(yōu)化卸載決策和資源分配方式有著較大的實(shí)際價(jià)值以及科學(xué)意義。

1 研究現(xiàn)狀

緩存輔助邊緣計(jì)算的相關(guān)研究者提出一種通過(guò)能量感知進(jìn)行計(jì)算卸載方案制定的方式，建設(shè)以延遲敏感型任務(wù)卸載與設(shè)備能量壽命為基礎(chǔ)的聯(lián)合優(yōu)化方式；也有研究者提出通過(guò)聯(lián)合優(yōu)化移動(dòng)設(shè)備的計(jì)算速率與發(fā)射功率、卸載任務(wù)比例，解決移動(dòng)智能設(shè)備中相關(guān)能量損耗過(guò)大問題；還有研究者提出了一種多用戶移動(dòng)邊緣計(jì)算系統(tǒng)能量分配模型，該分配模型通過(guò)借助計(jì)算資源以及優(yōu)化分配通信，構(gòu)建了最小能量消耗總加權(quán)和的相關(guān)問題；而張海波等學(xué)者對(duì)系統(tǒng)總能耗進(jìn)行了深入的分析與研討，通過(guò)坐標(biāo)下降法以及改進(jìn)過(guò)的貪婪算法與匈牙利算法，實(shí)現(xiàn)任務(wù)卸載及其資源分配的相關(guān)聯(lián)合優(yōu)化問題，得出將內(nèi)容緩存部署在移動(dòng)邊緣計(jì)算節(jié)點(diǎn)，可在一定程度上促進(jìn)能量利用率的提升的結(jié)論[1]。

此外還有研究者在研究時(shí)，將邊緣網(wǎng)絡(luò)緩存資源分配視為一個(gè)線性規(guī)劃模型，勾勒出一種以網(wǎng)絡(luò)分片為基礎(chǔ)的緩存資源分配方案，在研究本地內(nèi)容緩存與蜂窩基站的交付策略與最優(yōu)協(xié)作內(nèi)容緩存過(guò)程中，降低了用戶的能源消耗以及回程負(fù)載。通過(guò)激勵(lì)機(jī)制以及緩存策略的聯(lián)合，借助共享存儲(chǔ)資源實(shí)現(xiàn)了邊緣網(wǎng)絡(luò)效益的提升，這相當(dāng)于啟發(fā)式緩存。

以上各種形式的設(shè)備能耗問題研究是從不同角度進(jìn)行的，而將邊緣節(jié)點(diǎn)部署內(nèi)容緩存視為輔助執(zhí)行能力，研究其卸載機(jī)制時(shí)，以上各項(xiàng)研究將存在較大的局限性，從而不再適用，原因是可供選擇的任務(wù)執(zhí)行增多，單一尋優(yōu)方式的處理方式會(huì)造成借助不同方式執(zhí)行的公正性、公平性降低，而使得資源利用率不高。本文通過(guò)搭建一種新型緩存輔助邊緣計(jì)算網(wǎng)絡(luò)模型，優(yōu)化緩存輔助邊緣計(jì)算的卸載決策，使有限的資源得到更加合理和高效的利用。

2 系統(tǒng)模型

新緩存輔助邊緣計(jì)算在構(gòu)建網(wǎng)絡(luò)模型時(shí)，要求按照如圖1所示的方式進(jìn)行，其涵蓋N個(gè)用戶設(shè)備、移動(dòng)邊緣計(jì)算服務(wù)器（MEC服務(wù)器）與邊緣基站。其中在移動(dòng)邊緣計(jì)算服務(wù)器接收到用戶設(shè)備傳遞而來(lái)的無(wú)線數(shù)據(jù)信息時(shí)，會(huì)按照固定的程序?qū)ζ浼右苑治?，并反饋出一定的決策命令信息。此時(shí)用戶設(shè)備會(huì)按照預(yù)選設(shè)定目標(biāo)執(zhí)行系列進(jìn)行決策，任務(wù)參量Ai用{Di，Ti}表示，Di指的是任務(wù)數(shù)據(jù)值，Ti指的是該任務(wù)執(zhí)行時(shí)可忍受最大延遲值，ρi通常指的是任務(wù)數(shù)據(jù)的實(shí)時(shí)處理密度，通俗來(lái)講即完成該任務(wù)執(zhí)行時(shí)所需的CPU周期數(shù)。因此，完成一項(xiàng)任務(wù)需要的總CPU周期Ci可用ρi·Di表示，即Ci=ρi·Di。在本文中，假定ρi、Ci、Di皆是對(duì)應(yīng)用戶設(shè)備的固有參量，且各項(xiàng)值已經(jīng)明確，在進(jìn)行對(duì)應(yīng)任務(wù)的計(jì)算進(jìn)程中，用戶設(shè)備的整體計(jì)算資源、執(zhí)行資源分別選擇以fii、pli來(lái)表示，由此可知在按照系統(tǒng)指令完成Ai任務(wù)時(shí)，用Ci/fil來(lái)表達(dá)能量的時(shí)延，用Ci/fil·pli表達(dá)能量的消耗[2]。

用戶設(shè)備在接收完對(duì)應(yīng)的指令信息后，可選擇借助無(wú)線傳輸線路，在移動(dòng)邊緣計(jì)算單元中按照固定的流程來(lái)執(zhí)行完所有的卸載任務(wù)與計(jì)算處理任務(wù)。以hi來(lái)表示用戶設(shè)備、邊緣基站之間的信道增益，用σ2表示噪聲的功率。任務(wù)數(shù)據(jù)卸載在進(jìn)行上傳時(shí)的實(shí)時(shí)速率ri可表示為（plmh i/σ2+1）·Wlb，其中W為系統(tǒng)帶寬，plm為傳輸功率。

用戶設(shè)備i得到的分配計(jì)算資源可用f imec表示，F(xiàn)m指的是其最大值，實(shí)施邊緣處理任務(wù)時(shí)，對(duì)應(yīng)的用戶設(shè)備處于空閑期，可選擇以pie表示其具體的功率消耗，在以卸載方式執(zhí)行上級(jí)指令的任務(wù)時(shí)，此時(shí)消耗的時(shí)間包括任務(wù)傳輸?shù)臅r(shí)間、執(zhí)行消耗的時(shí)間，則tim′可用Ci/fim′+Di/ri來(lái)表示，用戶設(shè)備此時(shí)實(shí)時(shí)的能量消耗eim′可用Ci/fim′·pie+Di/ri·plm來(lái)表示。

實(shí)現(xiàn)緩存資源的部署，用于已處理完成的原始數(shù)據(jù)與相關(guān)應(yīng)用任務(wù)的緩存，而卸載任務(wù)已經(jīng)在邊緣網(wǎng)絡(luò)完成緩存后完成，不需要再實(shí)施任務(wù)卸載，因此，可借助下行鏈路在基站位置完成結(jié)果數(shù)據(jù)的接收，降低卸載傳輸本身的能源消耗量。邊緣緩存本身的內(nèi)容放置與內(nèi)容的流行度、數(shù)據(jù)的大小有著一定的關(guān)聯(lián)，用Cd來(lái)表示可緩存的最大數(shù)據(jù)量。用戶設(shè)備在接收到能夠進(jìn)行緩存的數(shù)據(jù)信息時(shí)，通過(guò)鏈路將處理數(shù)據(jù)傳輸至用戶設(shè)備，又因信息緩存處理進(jìn)行的執(zhí)行時(shí)間短，因此可將其時(shí)間與邊緣服務(wù)器實(shí)際的執(zhí)行時(shí)長(zhǎng)視為相同。因此時(shí)間消耗t ie以及對(duì)應(yīng)的能量消耗eie可用Ci/fim′與Ci/fim′·ple表示。

3 制定卸載決策

首先，引入松弛變量Ee。將原目標(biāo)本身的問題闡述為松弛變量Ee的問題，其后為完成QCQP的轉(zhuǎn)化，可構(gòu)建對(duì)應(yīng)的約束式：（xi（1，m，c）－1）xi（1，m，c）=0。針對(duì)以上數(shù)據(jù)分析結(jié)果可知，卸載效率取決于計(jì)算資源在各個(gè)階段的分配情況，要在分配資源時(shí)，能夠明確預(yù)選卸載集合，在按照上級(jí)指令執(zhí)行各項(xiàng)決策時(shí)可不再去考量一些細(xì)小的約束條件。而以上約束式有著二次項(xiàng)造成松弛后產(chǎn)生的目標(biāo)問題呈現(xiàn)非凸?fàn)顟B(tài)問題，將（4N+1）向量yi用[xil，xim，di，xie，Ee]表示，則該項(xiàng)雙層優(yōu)化問題可構(gòu)建出具體的模型。

在轉(zhuǎn)化半定松弛后可得出對(duì)應(yīng)的SDP問題，轉(zhuǎn)化向量Z可用ziTzi表示，而zi則用[yiT，1]T表示，由此可得出對(duì)應(yīng)的函數(shù)：s.t.tr（ZG j）=0，tr（ZGic）≤Cd，（4N+2，4N+2）Z=1，由此可得出對(duì)應(yīng)的集合：

采用CHEN等提出的隨機(jī)概率映射方式，將其中產(chǎn)生的變量解通過(guò)概率約束的方式，在{0，1}3N整數(shù)集中映射，用概率形式表示其執(zhí)行選擇：取p（xi（1，m，c）=1）值為pi（1，m，c），代表其在不同形式的任務(wù)時(shí)，有著差異化的執(zhí)行方式，因此其卸載決策包括[0，1，0]T、[1，0，0]T、[0，0，1]T這3個(gè)。

4 資源優(yōu)化

通過(guò)整理以上函數(shù)式，可以得出以下資源分配問題：[pil·xil·Ci/fil+（xie+xim）Ci/fim′·pi ld]。功率分配與計(jì)算資源分配在約束以及目標(biāo)函數(shù)式中并非耦合，因此，在其計(jì)算資源給定的狀況下，還需對(duì)上式進(jìn)行優(yōu)化與調(diào)整，得出Dipim/[（hipim/σ2+1）wlb]，轉(zhuǎn)化雙層非凸問題時(shí)，定義其最優(yōu)解與最優(yōu)功率分配為V*、pm*，可得出V*的表達(dá)式Dipim/[（hipim/σ2+1）wlb]=Dipim*/[（hipim*/σ2+1）wlb]，結(jié)合非線性分?jǐn)?shù)規(guī)劃理論，當(dāng)存在{Dipim*－[（h i pim/σ2+1）]blbV*}=0時(shí)，V*在該結(jié)論中引入對(duì)應(yīng)的松弛變量Ep，由此可推導(dǎo)出Dipim－wlbV（hipim/σ2+1）≤Ep。以上式為基礎(chǔ)，可利用拉格朗日對(duì)偶分解算法，在目標(biāo)函數(shù)中進(jìn)行優(yōu)化變量的分解，以此來(lái)得到最優(yōu)功率分配pim*，由此可輔以拉格朗日輔助函數(shù)，如圖2所示，進(jìn)行拉格朗日函數(shù)的構(gòu)造。由于其凸優(yōu)化函數(shù)的存在，可有效保證零對(duì)偶間隙，并成立對(duì)應(yīng)的強(qiáng)對(duì)偶性，其對(duì)偶函數(shù)可用D（α，β）=minL（p，Ep，α，β）表示，在完成分解后，其功率分配函數(shù)式可用以下方程式來(lái)表達(dá)：

圖2 拉格朗日輔助函數(shù)圖

參考Karush-Kuhn-Tucker條件，可得出最優(yōu)功率分配解析式[3]：

5 結(jié)語(yǔ)

本文以降低用戶能耗和促進(jìn)邊緣計(jì)算系統(tǒng)相應(yīng)服務(wù)性能的提升為目標(biāo)，面向移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)，在緩存輔助基礎(chǔ)上提出對(duì)應(yīng)的卸載決策以及資源優(yōu)化方案，在探討了現(xiàn)階段的基本研究現(xiàn)狀后，決定采用半定松弛的方式按照一定的標(biāo)準(zhǔn)進(jìn)行聯(lián)合優(yōu)化目標(biāo)函數(shù)的構(gòu)造，在得到對(duì)應(yīng)的預(yù)選卸載策略集合后借助拉格朗日對(duì)偶分解計(jì)算方式得出最優(yōu)的傳輸功率，其后通過(guò)二分法按照最優(yōu)方式進(jìn)行了邊緣計(jì)算資源的分配。在相關(guān)模型和算法確定后，通過(guò)計(jì)算機(jī)仿真，對(duì)比以往的緩存輔助邊緣計(jì)算的卸載決策方案，可節(jié)省大約18.6%的能源，使有限的資源得到更加充分的利用。該新方案在保障系統(tǒng)公平性的同時(shí)，使得移動(dòng)邊緣計(jì)算終端能源消耗有所降低，對(duì)于現(xiàn)實(shí)應(yīng)用具有重大意義。

在電網(wǎng)中，現(xiàn)有基于邊緣計(jì)算的電網(wǎng)實(shí)時(shí)在線監(jiān)控業(yè)務(wù)網(wǎng)絡(luò)架構(gòu)也存在同樣的問題，在邊緣監(jiān)控系統(tǒng)中存在大量物聯(lián)網(wǎng)設(shè)備和少量的邊緣服務(wù)器。盡管這些邊緣服務(wù)器和物聯(lián)網(wǎng)設(shè)備位于固定的位置，監(jiān)測(cè)設(shè)備和邊緣服務(wù)器之間的連接靈活，但邊緣節(jié)點(diǎn)的資源和能力相對(duì)有限，如計(jì)算資源和存儲(chǔ)資源，會(huì)造成部分任務(wù)無(wú)法及時(shí)完成，進(jìn)而影響整個(gè)系統(tǒng)的監(jiān)控性能。系統(tǒng)的監(jiān)測(cè)性能與網(wǎng)絡(luò)延遲和監(jiān)測(cè)幀率有關(guān)，延遲越低、幀率越高，系統(tǒng)性能越好[4]。此外，不合理的卸載決策容易造成邊緣節(jié)點(diǎn)嚴(yán)重的資源消耗。該緩存輔助邊緣計(jì)算的卸載決策的提出對(duì)于電網(wǎng)中智能電能表的資源分配問題也具有借鑒意義。