葛志輝,劉子萌,王 哲,李陶深

1(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,南寧 530004)

2(廣西民族大學(xué) 人工智能學(xué)院,南寧 530005)

1 引 言

5G技術(shù)的發(fā)展與廣泛部署促使移動(dòng)網(wǎng)絡(luò)在原有通信服務(wù)基礎(chǔ)上,產(chǎn)生了諸多垂直型服務(wù),如自動(dòng)駕駛,虛擬/增強(qiáng)現(xiàn)實(shí)(Virtual Reality/Augment Reality,VR/AR),車聯(lián)網(wǎng),遠(yuǎn)程手術(shù)等.這類垂直型服務(wù)的實(shí)現(xiàn)歷來(lái)與移動(dòng)網(wǎng)絡(luò)的計(jì)算能力和極短的時(shí)延有著十分重要的關(guān)系,然而,受限于用戶設(shè)備的容量和能耗,計(jì)算密集型應(yīng)用的本地處理時(shí)延較高,無(wú)法滿足垂直型業(yè)務(wù)的服務(wù)質(zhì)量要求.除此之外,計(jì)算密集型應(yīng)用由于在計(jì)算能力和時(shí)延方面要求較高,同時(shí)也會(huì)造成用戶設(shè)備耗電量較大,極大縮短了用戶設(shè)備的電池壽命.傳統(tǒng)的解決方案是采用移動(dòng)云計(jì)算技術(shù)(Mobile Clouding Computing,MCC),將用戶設(shè)備任務(wù)卸載到資源豐富,數(shù)據(jù)存儲(chǔ)量大的遠(yuǎn)程中央云服務(wù)器上在進(jìn)行任務(wù)的處理后將結(jié)果反饋給用戶設(shè)備,這雖然解決了用戶設(shè)備對(duì)于計(jì)算能力的要求,但通過(guò)廣域網(wǎng)的數(shù)據(jù)傳輸容出現(xiàn)成因數(shù)據(jù)交換而產(chǎn)生較長(zhǎng)的時(shí)延以及數(shù)據(jù)丟失的情況.

近幾年來(lái),為了解決爆炸性的計(jì)算需求和日益增長(zhǎng)的計(jì)算質(zhì)量的設(shè)備需求,多接入邊緣計(jì)算(Multi-Access Edge Computing,MEC)應(yīng)運(yùn)而生.多接入邊緣計(jì)算是一種結(jié)合5G架構(gòu)的技術(shù),其目標(biāo)是將云功能帶到網(wǎng)絡(luò)的邊緣,通常部署在靠近接入點(diǎn)(Access Point,AP)或核心網(wǎng)絡(luò)的某些聚合點(diǎn).利用毫米波接入到鄰近的移動(dòng)邊緣主機(jī)(Mobile Edge Host,MEH)上完成計(jì)算,存儲(chǔ)和通信等操作,能夠?yàn)橐苿?dòng)用戶設(shè)備提供更快的服務(wù)訪問(wèn)能力,提高計(jì)算體驗(yàn)的質(zhì)量,包括能耗和執(zhí)行時(shí)延[1-4].

當(dāng)前如何定義對(duì)通信資源和計(jì)算資源的有效管理,保證較低的端到端的服務(wù)時(shí)延和較高可靠性有待深入研究.Pavel.等詳細(xì)的介紹MEC功能集成到移動(dòng)網(wǎng)絡(luò)的現(xiàn)有概念,并討論MEC標(biāo)準(zhǔn)化的當(dāng)前進(jìn)展,闡述計(jì)算卸載的研究主要分為3個(gè)關(guān)鍵領(lǐng)域,即計(jì)算卸載決策,MEC內(nèi)的計(jì)算資源分配以及移動(dòng)性管理三方面,并討論尚未解決的研究挑戰(zhàn)以及MEC存在的發(fā)展?jié)摿5,6].如何實(shí)現(xiàn)計(jì)算卸載中的資源分配問(wèn)題是當(dāng)前MEC所面對(duì)的一大挑戰(zhàn),同時(shí)也是過(guò)去幾年該研究領(lǐng)域所研究的關(guān)鍵課題,并在各種MEC系統(tǒng)中廣泛研究.

文獻(xiàn)[7]關(guān)注在單用戶設(shè)備的MEC系統(tǒng)中在時(shí)延的約束下最小化本地計(jì)算和任務(wù)卸載功耗問(wèn)題.文獻(xiàn)[8]將該網(wǎng)絡(luò)場(chǎng)景擴(kuò)展到多用戶設(shè)備的MEC系統(tǒng)中,在特定應(yīng)用程序的時(shí)延約束下,協(xié)同優(yōu)化卸載決策選擇,通過(guò)聯(lián)合考慮無(wú)線電資源和計(jì)算資源分配從而解決化移動(dòng)用戶設(shè)備的功耗最小化問(wèn)題,并定義該問(wèn)題為混合整數(shù)非線性規(guī)劃問(wèn)題(Mixed Integer Nonlinear Programming,MINIP),基于分枝定界方法(Reformulation Linearization Technique Based Branch-and-Bound,RLTBB)的線性化技術(shù)和基尼系數(shù)的貪心啟發(fā)式算法實(shí)現(xiàn)該凸問(wèn)題的最優(yōu)解或次優(yōu)解.

在多用戶設(shè)備MEC系統(tǒng)中,最優(yōu)系統(tǒng)資源分配不僅與隨機(jī)計(jì)算任務(wù)到達(dá)有關(guān),而且與多個(gè)設(shè)備之間的競(jìng)爭(zhēng)所產(chǎn)生的空間耦合有關(guān).此外,并行本地和遠(yuǎn)程處理的自由度使得移動(dòng)執(zhí)行策略、計(jì)算卸載策略和在MEC服務(wù)器上的操作都相互影響著.因此,應(yīng)考慮無(wú)線電資源和計(jì)算資源的智能聯(lián)合分配,以最大限度地提高M(jìn)EC的系統(tǒng)性能.文獻(xiàn)[9]考慮基于頻分多址(Frequency Division Multiple Access,FDMA)的多用戶設(shè)備MEC系統(tǒng)中,隨機(jī)聯(lián)合無(wú)線電資源和計(jì)算資源管理,并引入李雅普諾夫隨機(jī)優(yōu)化理論技術(shù)(Lyapunov stochastic optimization)實(shí)現(xiàn)在任務(wù)緩沖區(qū)穩(wěn)定性的約束下最小化移動(dòng)設(shè)備和MEC服務(wù)器的平均加權(quán)功耗.文獻(xiàn)[10]則分別考慮在基于時(shí)分多址(Time Division Multiple Access,TDMA)和正交頻分多址(Orthogonal Frequency Multiple Access,OFDMA)的多用戶設(shè)備MEC系統(tǒng)下,多移動(dòng)設(shè)備在具有相同時(shí)延約束下的資源分配問(wèn)題.文獻(xiàn)[11]以用戶設(shè)備為中心,考慮在用戶設(shè)備長(zhǎng)期平均功耗的約束下,最優(yōu)化無(wú)線接入和計(jì)算所產(chǎn)生的時(shí)延,引入一個(gè)懲罰函數(shù)避免用戶設(shè)備頻繁切換和多臂賭博機(jī)(Multi-Armed Bandit Algorithm)算法以用戶設(shè)備最佳關(guān)聯(lián).文獻(xiàn)[12]在考慮在物聯(lián)網(wǎng)場(chǎng)景下,設(shè)計(jì)一個(gè)基于隨機(jī)梯度下降(Stochastic Gradient Descent,SGD)的在線計(jì)算算法使得物聯(lián)網(wǎng)設(shè)備,邊緣服務(wù)器和總服務(wù)延遲之間保持最優(yōu)權(quán)衡.文獻(xiàn)[13]對(duì)計(jì)算任務(wù)的功耗和時(shí)延很高要求的車聯(lián)網(wǎng)領(lǐng)域在傳統(tǒng)的粒子群算法基礎(chǔ)上,提出粒子矩陣編碼的方式,優(yōu)化車輛的卸載決策和MEC的資源分配,解決車輛網(wǎng)絡(luò)中動(dòng)態(tài)卸載過(guò)程中的多約束優(yōu)化問(wèn)題.但隨著深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning,DRL)在許多領(lǐng)域都取得巨大的成功,DRL由于對(duì)時(shí)變環(huán)境具有較強(qiáng)的認(rèn)知性,在車輛網(wǎng)絡(luò)中得到廣泛的應(yīng)用.文獻(xiàn)[14]提出基于DRL的高效計(jì)算卸載策略,在降低任務(wù)失敗率和時(shí)延方面達(dá)到很好的效果.上述的研究均考慮在較為經(jīng)典的無(wú)線信道條件下的傳輸,但MEC的計(jì)算卸載效率極其的依賴于無(wú)線信道的條件,因?yàn)橛?jì)算卸載需要在移動(dòng)設(shè)備和MEC服務(wù)器之間進(jìn)行有效的無(wú)線數(shù)據(jù)傳輸.隨著5G技術(shù)的全面部署,利用高容量毫米波(mmWave)訪問(wèn)和移動(dòng)邊緣主機(jī)(MEH)的密集部署向結(jié)合的技術(shù)的到深入的研究,mmWave能夠提供極寬的帶寬極大的提高傳輸?shù)男蔥4].文獻(xiàn)[15]研究了通過(guò)mmWave通信傳輸實(shí)現(xiàn)多移動(dòng)用戶設(shè)備與AP-MEH的匹配,以及通信資源和計(jì)算資源的聯(lián)合分配問(wèn)題,基于多對(duì)一的匹配理論和懲罰逐次凸逼近策略(Successive Convex Approximation,SCA)在減少時(shí)延和功耗的約束下為移動(dòng)用戶設(shè)備接入到AP-MEH上提供最優(yōu)的策略.文獻(xiàn)[16]將單AP和單MEH的網(wǎng)絡(luò)場(chǎng)景擴(kuò)展到多AP多MEH對(duì)的場(chǎng)景,提出由兩個(gè)階段組成的ODS-AO算法,在第1階段實(shí)現(xiàn)最優(yōu)卸載決策,第2階段是實(shí)現(xiàn)資源分配的局部最優(yōu)解的解決方案.文獻(xiàn)[17]只考慮多AP和多MEH場(chǎng)景,在隊(duì)列穩(wěn)定性約束條件下,提出一種基于隨機(jī)優(yōu)化理論和匹配理論的在線算法,實(shí)現(xiàn)用戶設(shè)備與計(jì)算資源和通信資源的最優(yōu)動(dòng)態(tài)資源分配.

從現(xiàn)有的研究來(lái)看,計(jì)算卸載中的資源分配在各個(gè)領(lǐng)域上都得到廣泛的應(yīng)用,其所運(yùn)用的場(chǎng)景從單用戶設(shè)備的MEC系統(tǒng)場(chǎng)景向多用戶設(shè)備的MEC系統(tǒng)場(chǎng)景擴(kuò)展研究較為廣泛的多AP多MEH的場(chǎng)景.在不同的通信條件下和約束條件下的資源分配方案也得到了深入的研究.但由于當(dāng)前的系統(tǒng)設(shè)計(jì)依賴于平均指標(biāo)(例如平均隊(duì)列長(zhǎng)度和平均延遲),對(duì)時(shí)延約束條件下的資源分配方案還需進(jìn)行深入研究.

時(shí)延約束下的動(dòng)態(tài)計(jì)算卸載問(wèn)題首次在文獻(xiàn)[18]中提出,Liu.等對(duì)計(jì)算隊(duì)列引入一個(gè)概率約束,并通過(guò)極值理論定義為超過(guò)一個(gè)確定值概率的邊界,文獻(xiàn)[19]則擴(kuò)展到多AP多MEH的場(chǎng)景下,基于匹配理論引入一個(gè)用戶設(shè)備分配策略.文獻(xiàn)[20]為每個(gè)用戶設(shè)備增加能量收集裝置,在多用戶設(shè)備的MEC系統(tǒng)下,考慮有限塊長(zhǎng)度和可靠性的約束,基于隨機(jī)優(yōu)化理論在服務(wù)時(shí)延和移動(dòng)設(shè)備上能耗之間實(shí)現(xiàn)了最優(yōu)平衡的策略,文獻(xiàn)[21]考慮在平均時(shí)延和失效概率的約束下,將用戶設(shè)備任務(wù)卸載到單個(gè)MEH上,聯(lián)合優(yōu)化在計(jì)算和通信資源分配.最終實(shí)現(xiàn)用戶設(shè)備長(zhǎng)期平均功耗.

綜上所述,在時(shí)延約束下的資源分配方案的研究大部分主要是在單MEH的場(chǎng)景下,對(duì)于多AP和多MEH場(chǎng)景下的資源分配方案,大部分考慮在平均性能的約束下,不能滿足于要求極高時(shí)延和可靠性的計(jì)算密集型應(yīng)用.

基于上述的分析,本文針對(duì)基于mmWave接入的多AP和多MEH的邊緣計(jì)算場(chǎng)景,解決在平均時(shí)延和失效概率的約束下最小化用戶設(shè)備的長(zhǎng)期平均功耗問(wèn)題,并將該最小化問(wèn)題定義為混合整數(shù)非線性規(guī)劃問(wèn)題.基于隨機(jī)優(yōu)化和匹配理論,提出了一種聯(lián)合優(yōu)化無(wú)線資源和計(jì)算資源的資源分配方案,在實(shí)現(xiàn)用戶設(shè)備與AP-MEH關(guān)聯(lián)后,實(shí)現(xiàn)通信資源和計(jì)算資源的最優(yōu)分配.通過(guò)調(diào)用李雅普諾夫隨機(jī)優(yōu)化理論處理卸載請(qǐng)求,信道狀態(tài)以及計(jì)算隊(duì)列,同時(shí)引入懲罰函數(shù)減少用戶設(shè)備頻繁切換,通過(guò)定義上述最小化問(wèn)題優(yōu)化通信資源和計(jì)算資源.通過(guò)與在隊(duì)列穩(wěn)定性的約束條件下的資源分配方案,證明所提出的資源分配策略將有著更好的性能.

本文的主要貢獻(xiàn)有以下:

1)構(gòu)建通過(guò)mmWave接入的多AP和多MEH的場(chǎng)景下的邊緣計(jì)算網(wǎng)絡(luò)的動(dòng)態(tài)計(jì)算卸載問(wèn)題,這樣更能有效緩解把所有用戶設(shè)備的計(jì)算任務(wù)卸載到同一個(gè)MEH上所需要的計(jì)算能力以及用于等待計(jì)算過(guò)程所消耗的時(shí)延,從而是用戶設(shè)備能提供更好的服務(wù)質(zhì)量.

2)引入匹配理論和李雅普諾夫隨機(jī)優(yōu)化理論,分別實(shí)現(xiàn)了用戶設(shè)備的關(guān)聯(lián)以及關(guān)聯(lián)后的通信資源和計(jì)算資源的最優(yōu)化;引入一個(gè)懲罰函數(shù),有效地減少了用戶設(shè)備在關(guān)聯(lián)過(guò)程中的頻繁切換,提高整體的計(jì)算卸載性能.

3)基于平均時(shí)延和失效概率值的約束條件,提出一種以最小化用戶設(shè)備長(zhǎng)期平均功耗為目標(biāo)的計(jì)算卸載策略,通過(guò)仿真實(shí)驗(yàn)證明所提出的策略具有很好的系統(tǒng)性能.

2 系統(tǒng)模型

本文主要考慮在多AP和多MEH的網(wǎng)絡(luò)場(chǎng)景模型下,優(yōu)化用戶設(shè)備與移動(dòng)邊緣主機(jī)關(guān)聯(lián)匹配以及在實(shí)現(xiàn)關(guān)聯(lián)匹配后聯(lián)合優(yōu)化通信資源和計(jì)算資源的問(wèn)題.考慮K個(gè)用戶設(shè)備(k=1,2,3,…,K)和N個(gè)AP-MEH對(duì)(n=1,2,3,…,N)的網(wǎng)絡(luò)場(chǎng)景,其中每個(gè)用戶設(shè)備通過(guò)毫米波(mmWave)接入AP上,并將相應(yīng)的計(jì)算任務(wù)卸載到與之相對(duì)應(yīng)的MEH,如圖1所示.

圖1 網(wǎng)絡(luò)場(chǎng)景

在動(dòng)態(tài)的場(chǎng)景下,定義用于處理計(jì)算任務(wù)的時(shí)間為T,時(shí)間T被劃分具為相等持續(xù)時(shí)間τ的時(shí)隙t,t∈{0,1,2…}.在時(shí)隙t內(nèi),定義akn(t)為當(dāng)用戶設(shè)備k與第n對(duì)AP-MEH對(duì)之間形成關(guān)聯(lián)后的一個(gè)二進(jìn)制變量,Sn(t)為在時(shí)隙t內(nèi)用戶設(shè)備分配到第n個(gè)AP的集合,則當(dāng)用戶設(shè)備k的卸載任務(wù)分配到第n對(duì)AP-MEH上時(shí),可以通過(guò)以下公式表示為:

(1)

在時(shí)隙t內(nèi),用戶設(shè)備端隨機(jī)并持續(xù)生成計(jì)算任務(wù),定義hkn(t)為用戶設(shè)備k與AP-MEH之間的信道功率增益,在上行鏈路的傳輸過(guò)程中,定義pk(t)為鏈路的傳輸功率,βkn(t)為用戶設(shè)備與MEH形成關(guān)聯(lián)后,分配給用戶設(shè)備k的帶寬比例.在時(shí)隙t內(nèi),用戶設(shè)備k的的最大傳輸速率為:

(2)

(3)

(4)

(5)

(6)

該動(dòng)態(tài)分配問(wèn)題用以下數(shù)學(xué)表達(dá)式進(jìn)行表示:

s.t

(c)0≤pk(t)≤PK,?k,t;

(d)0≤βkn(t)≤1,?k,n,t;

(f)akn(t)∈{0,1},?k,n,t;

(h)0≤fkn(t)≤Fn,?n,t;

(7)

(8)

其中,σ是一個(gè)懲罰因子,引入懲罰函數(shù)的目的是減少該動(dòng)態(tài)過(guò)程中的頻繁切換的次數(shù),因?yàn)樵诿總€(gè)時(shí)隙內(nèi),用戶設(shè)備與AP-MEH之間進(jìn)行關(guān)聯(lián)時(shí),會(huì)導(dǎo)致分配變量的頻繁切換,及用戶設(shè)備在不同的AP-MEH對(duì)之間進(jìn)行切換,找到最適合的匹配關(guān)聯(lián).這不僅增加了關(guān)聯(lián)的復(fù)雜性,同時(shí)造成因從舊的AP-MEH到新的AP-MEH之間的狀態(tài)轉(zhuǎn)移而產(chǎn)生了額外的時(shí)延.

為了有效的定義式(7)中的(a)和(b)兩個(gè)約束條件,我們引入兩個(gè)虛擬隊(duì)列.定義Zk(t)為每個(gè)用戶設(shè)備的平均隊(duì)列長(zhǎng)度(即為平均時(shí)延),且該長(zhǎng)度不超過(guò)一個(gè)預(yù)定義的值,該虛擬隊(duì)列長(zhǎng)度可以定義為:

(9)

上述引入的虛擬隊(duì)列主要與(a)的約束條件相對(duì)應(yīng),約束條件(b)表達(dá)的含義為確保式(5)中總隊(duì)列長(zhǎng)度超過(guò)最大值的概率不超過(guò)預(yù)先定義的失效概率值,為了引入虛擬隊(duì)列,引入一個(gè)指標(biāo)函數(shù)1{·},通過(guò)以下等效的轉(zhuǎn)換形式可以將約束條件(b)改寫成以下表達(dá)式:

(10)

(11)

其中,u(·)為階躍函數(shù),定義虛擬隊(duì)列Yk(t)對(duì)約束條件(b)進(jìn)行描述,μ是一種用于加速算法收斂的步長(zhǎng),不會(huì)影響問(wèn)題的本質(zhì).該虛擬隊(duì)列可以表達(dá)為:

(12)

用戶設(shè)備k通過(guò)引入虛擬隊(duì)列Zk(t)和Yk(t),上述的約束條件可以被虛擬隊(duì)列的平均速率穩(wěn)定的約束條件所替代,可以通過(guò)以下表達(dá)式表示為:

(13)

(14)

3 問(wèn)題描述與求解

為了解決上述的動(dòng)態(tài)分配問(wèn)題,使用文獻(xiàn)[22]中的隨機(jī)優(yōu)化工具.在K個(gè)用戶設(shè)備的環(huán)境下,定義兩個(gè)虛擬隊(duì)列長(zhǎng)度的隊(duì)列積壓,定義一個(gè)李雅普諾夫(Lyapunov)函數(shù)為:

(15)

其中,Θ(t)=[Z(t),Y(t)],Z(t),Y(t)用向量進(jìn)行表示,該向量中的元素表示在時(shí)隙t內(nèi)所有用戶設(shè)備的虛擬隊(duì)列長(zhǎng)度.一個(gè)時(shí)隙條件下的李雅普諾夫漂移函數(shù)表示為:

Δp(Θ(t))=E{L(Θ(t+1))-L(Θ(t))|Θ(t)}

(16)

式(16)定義的漂移函數(shù)可以導(dǎo)致虛擬隊(duì)列的平均速率穩(wěn)定性,但同時(shí)也會(huì)造成不必要的功耗.為了平衡虛擬隊(duì)列的平均速率穩(wěn)定性和用戶設(shè)備的長(zhǎng)期平均功耗,引入漂移加懲罰函數(shù):

(17)

其中,V是一個(gè)控制參數(shù),用于權(quán)衡功耗和隊(duì)列長(zhǎng)度的切換數(shù)目.根據(jù)文獻(xiàn)[18]的引用,首先推導(dǎo)出該懲罰函數(shù)的上界,通過(guò)最小化在每個(gè)時(shí)隙內(nèi)上界的瞬時(shí)值,最小化該上界問(wèn)題表示為:

(18)

其中,C是一個(gè)正實(shí)數(shù),式(18)中的u{·}可定義為:

(19)

聯(lián)立式(18)和式(19),該動(dòng)態(tài)問(wèn)題的數(shù)學(xué)表達(dá)式為:

(20)

其中,Z為式(7)中的(a)～(g)的約束條件,該最優(yōu)化問(wèn)題可定義為求解每個(gè)時(shí)隙內(nèi)的混合整型非線性規(guī)劃問(wèn)題.具體可分解為兩部分,第1部分主要采用匹配理論將用戶設(shè)備k與AP-MEH對(duì)n之間建立關(guān)聯(lián)匹配,第2部分在形成關(guān)聯(lián)匹配的基礎(chǔ)上,將最優(yōu)化資源以閉式解分配到相應(yīng)的MEH上.

3.1 最優(yōu)化通信與計(jì)算資源

(21)

(22)

當(dāng)用戶設(shè)備將計(jì)算任務(wù)卸載到移動(dòng)邊緣主機(jī)上時(shí),移動(dòng)邊緣主機(jī)分配用于處理計(jì)算任務(wù)的周期頻率為fkn(t)=Fn.

3.2 用戶設(shè)備關(guān)聯(lián)匹配

為實(shí)現(xiàn)用戶設(shè)備與AP-MEH對(duì)之間的相互關(guān)聯(lián),提出有著較低的復(fù)雜性和較高穩(wěn)定性的基于大學(xué)招生問(wèn)題的穩(wěn)定廣義匹配理論[23].該匹配理論涉及到兩個(gè)集合,一個(gè)是用戶設(shè)備集合,另一個(gè)是AP-MEH對(duì)集合.主要解決的是一個(gè)多對(duì)一的匹配問(wèn)題,即一對(duì)AP-MEH可以和多個(gè)用戶設(shè)備之間的產(chǎn)生關(guān)聯(lián)匹配.但每個(gè)AP-MEH對(duì)可分配的的用戶設(shè)備數(shù)是有限的.每個(gè)用戶設(shè)備建立一個(gè)偏好函數(shù)用于對(duì)所有的AP-MEH對(duì)進(jìn)行排序,即為Rk,n.相應(yīng)的,AP-MEH對(duì)用戶設(shè)備也有著偏好函數(shù),即為Rn,k,偏好函數(shù)是基于用戶設(shè)備的信噪比(SNR),且根據(jù)信噪比對(duì)用戶設(shè)備進(jìn)行降序排序.為了避免在分配過(guò)程中出現(xiàn)兩個(gè)用戶設(shè)備k1、k2分別分配到兩個(gè)AP-MEH對(duì)n1、n2上,即相比于n2,k2更偏好于n1(即n1?k2n2)或者AP-MEH對(duì)n1嚴(yán)格偏好k2多于k1,提出基于延遲接受算法(Deferred Acceptance,DA)的優(yōu)化算法,其多項(xiàng)式復(fù)雜度能有效收斂到一個(gè)穩(wěn)定匹配的狀態(tài).

在實(shí)現(xiàn)聯(lián)合優(yōu)化計(jì)算和通信資源之前,定義Gkn為用戶設(shè)備與與接入點(diǎn)形成關(guān)聯(lián)后式(20)的目標(biāo)函數(shù)值,Gkn′為后續(xù)匹配過(guò)程中,用戶設(shè)備k遷移到最新的MEH上所產(chǎn)生的新目標(biāo)函數(shù)值.AP-MEH對(duì)可分配給用戶設(shè)備的最大數(shù)量為qn,具體的聯(lián)合優(yōu)化通信資源和計(jì)算資源分配方案如下所示.

算法:聯(lián)合優(yōu)化通信資源和計(jì)算資源分配方案

輸入:qn,Rk,n,Rn,k

輸出:更新的穩(wěn)定匹配Sn′目標(biāo)函數(shù)值Gkn′

1.Fort=1:Nslotdo

2.ift=1do

運(yùn)用延遲接受算法,得初始匹配Π0

根據(jù)式(21)、式(22)獲得資源分配方案,并獲得式(20)目標(biāo)函數(shù)值Gkn

3.else

5.運(yùn)用延遲接受算法,獲得新的匹配

6.根據(jù)式(21)、式(22)得到資源分配方案,并獲得新的目標(biāo)函數(shù)值Gkn′

7.if|Gkn′|>|Gkn|

Sn→Sn′

|Sn′∪{k}|≤qn′

8.End

從上述算法分析可知,在用戶設(shè)備與AP-MEH對(duì)之間關(guān)聯(lián)方面,對(duì)已經(jīng)進(jìn)行初始匹配的用戶設(shè)備在進(jìn)行一次匹配優(yōu)化,具體的匹配有方案為:第1個(gè)時(shí)隙內(nèi),每個(gè)用戶設(shè)備只需根據(jù)自己的偏好函數(shù)實(shí)現(xiàn)用戶設(shè)備與AP-MEH對(duì)之間關(guān)聯(lián),只需要滿足每個(gè)MEH上所分配給用戶設(shè)備的數(shù)量不超過(guò)最大數(shù)量即可.其他時(shí)隙內(nèi),用戶設(shè)備在上述方案中的條件下建立新的偏好匹配函數(shù),當(dāng)新的偏好函數(shù)被執(zhí)行時(shí),用戶設(shè)備k的接入狀態(tài)從集合Sn轉(zhuǎn)移到集合Sn′,且都不超過(guò)最大數(shù)量qn′.當(dāng)兩個(gè)用戶設(shè)備都請(qǐng)求接入到同一個(gè)AP-MEH對(duì)上時(shí),只考慮擁有最高信噪比的用戶設(shè)備,當(dāng)用戶設(shè)備與AP-MEH對(duì)之間形成關(guān)聯(lián)匹配后,會(huì)自動(dòng)調(diào)用優(yōu)化的計(jì)算資源和通信資源,并將兩個(gè)最優(yōu)化方案聯(lián)合考慮,從而實(shí)現(xiàn)用戶的長(zhǎng)期平均功耗最小化.

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

為了證明本文系統(tǒng)模型和策略的有效性,將本文提出的方案與在隊(duì)列穩(wěn)定性約束條件下的資分配方案進(jìn)行性能對(duì)比分析.

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

在仿真實(shí)驗(yàn)中,本文考慮在多移動(dòng)邊緣主機(jī)和多用戶設(shè)備場(chǎng)景下的計(jì)算卸載問(wèn)題.該網(wǎng)絡(luò)場(chǎng)景考慮10個(gè)用戶設(shè)備在一個(gè)大小為150×150平方米的區(qū)域內(nèi)隨機(jī)移動(dòng),6個(gè)AP-MEH對(duì)在該區(qū)域內(nèi)隨機(jī)部署.每個(gè)用戶設(shè)備通過(guò)最高的信噪比連接到AP,并將需要處理的計(jì)算任務(wù)卸載到與之相對(duì)應(yīng)的MEH上,用戶設(shè)備k與接入點(diǎn)n之間使用信道路徑損失模型[24],相關(guān)的系統(tǒng)參數(shù)如表1所示.

表1 系統(tǒng)參數(shù)設(shè)置

此外,本文的目的是分析平均隊(duì)列和失效概率的約束下最小化用戶設(shè)備的長(zhǎng)期平均功耗,因此,約束條件的參數(shù)如表2所示.

表2 約束條件參數(shù)設(shè)置

4.2 仿真實(shí)驗(yàn)與分析

本文通過(guò)MATLAB建立數(shù)值仿真實(shí)驗(yàn),針對(duì)3.2節(jié)中提到在進(jìn)行最優(yōu)用戶設(shè)備匹配時(shí),會(huì)存在用戶設(shè)備在不同的AP-MEH對(duì)之間進(jìn)行切換以提高整體卸載的性能,但同時(shí)頻繁切換的過(guò)程中會(huì)產(chǎn)生一定的時(shí)延損失.因此,當(dāng)發(fā)生切換時(shí),假設(shè)NtrNtr為應(yīng)用程序狀態(tài)從初始AP向目的AP遷移后所需要的時(shí)延,并在該時(shí)隙內(nèi),只能進(jìn)行本地任務(wù)計(jì)算.本文將與考慮在隊(duì)列穩(wěn)定的約束條件下資源分配方法進(jìn)行對(duì)比,證明所提出方法具有更好的增益.圖2描述了平均用戶隊(duì)列長(zhǎng)度和平均用戶總功耗之間的關(guān)系,將平均任務(wù)到達(dá)率Aavg(t)設(shè)置為2Mbps,運(yùn)行時(shí)間T=10000,通過(guò)對(duì)100組仿真實(shí)驗(yàn)結(jié)果進(jìn)行總結(jié)分析,可得到該平均總隊(duì)列長(zhǎng)度(本地和遠(yuǎn)程隊(duì)列之和)與用戶設(shè)備平均總功耗之間的關(guān)系.

圖2 平均功耗和平均隊(duì)列長(zhǎng)度的關(guān)系圖

從圖2可知,非負(fù)的李雅普諾夫權(quán)衡參數(shù)變量V與平均用戶設(shè)備隊(duì)列長(zhǎng)度之間呈現(xiàn)反比,當(dāng)V增加時(shí),平均用戶設(shè)備隊(duì)列長(zhǎng)度則不斷減少,最后趨于平穩(wěn)狀態(tài).相比于在隊(duì)列穩(wěn)定下的約束條件,本文所提出的方法平均用戶隊(duì)列長(zhǎng)度隨著用戶功耗的增加,不斷減少且在平均隊(duì)列長(zhǎng)度下,即在隊(duì)列長(zhǎng)度/功率權(quán)衡之間具有更好的效益;從圖2也可知,Ntr越高,動(dòng)態(tài)卸載的性能也越低,這是由于在用戶設(shè)備切換發(fā)生后,遷移計(jì)算也需要消耗部分時(shí)延.但與在隊(duì)列穩(wěn)定下的資源分配方案相比,在平均時(shí)延和失效概率約束條件下的資源分配方法有著更好的性能.

為了更詳細(xì)的分析在平均時(shí)延和失效概率的約束下有著更好的性能,接下來(lái)通過(guò)對(duì)約束條件的參數(shù)設(shè)置不同的變量,考慮在不同參數(shù)下的失效概率的變化.在圖3中,考慮在V=4×1016以及平均執(zhí)行時(shí)隙為T=3×105,考慮3個(gè)用戶設(shè)備在不同的Qkavg,Qkmax,εk下的性能情況,分別設(shè)置用戶設(shè)備的參數(shù)Qkmax=[15,25,35]×106,失效概率為εk=[10-1,10-2,10-3],k==1,2,3.為了說(shuō)明失效概率的約束下的有效性,定義為1-CDF(Qktot)的可靠性函數(shù).

圖3 3個(gè)不同用戶設(shè)備的總隊(duì)列長(zhǎng)度的概率變化

圖3中的每條曲線表示Qktot(t)的概率大于橫坐標(biāo)上的值的概率,而不同的垂直虛線表示不同的用戶設(shè)備所滿足的最大隊(duì)列長(zhǎng)度.從圖3結(jié)果可知,實(shí)線和虛線的交點(diǎn)表示Qktot和Qkmax之間的關(guān)系,通過(guò)導(dǎo)入式(11)對(duì)兩者之間的關(guān)系進(jìn)行分析,結(jié)果表明都滿足所提出的失效概率的約束條件.

圖4考慮了3個(gè)用戶設(shè)備在每個(gè)時(shí)隙內(nèi)的計(jì)算卸載的總隊(duì)列長(zhǎng)度的瞬時(shí)值的變化情況,每條曲線代表著每個(gè)用戶設(shè)備在不同的時(shí)隙內(nèi)的總隊(duì)列長(zhǎng)度瞬時(shí)值,虛線代表每個(gè)用戶設(shè)備所需的最長(zhǎng)隊(duì)列長(zhǎng)度,Qkmax,k=1,2,3.

圖4 3個(gè)用戶設(shè)備的總隊(duì)列長(zhǎng)度瞬時(shí)值變化

從圖4可知,基于失效概率約束下的計(jì)算卸載方案能有效確保用戶需求所需的總隊(duì)列長(zhǎng)度的快速收斂,且不斷收斂靠近每個(gè)用戶的Qkmax.雖然在一些時(shí)隙內(nèi)用戶的總隊(duì)列長(zhǎng)度瞬時(shí)值超過(guò)用戶的Qkmax,但從整體性能進(jìn)行分析,基于失效概率約束條件下的資源分配方案將有著更好的性能.

本文所采用的計(jì)算卸載為部分卸載,即計(jì)算任務(wù)主要分為本地處理和遠(yuǎn)程處理.本文采用平均任務(wù)到達(dá)率Aavg(t)對(duì)整個(gè)動(dòng)態(tài)任務(wù)卸載過(guò)程進(jìn)行衡量,當(dāng)設(shè)置不同的平均任務(wù)到達(dá)率對(duì)卸載過(guò)程的用戶設(shè)備隊(duì)列長(zhǎng)度有著不同的影響.圖5給出在不同的平均任務(wù)到達(dá)率的條件下,用戶設(shè)備與平均總隊(duì)列長(zhǎng)度之間的關(guān)系.其中,橫坐標(biāo)表示用戶設(shè)備的數(shù)量,縱坐標(biāo)表示平均總隊(duì)列長(zhǎng)度.

圖5 平均總隊(duì)列長(zhǎng)度與用戶設(shè)備數(shù)量的關(guān)系

從圖5可知,隨著用戶設(shè)備數(shù)量的增加,需要進(jìn)行卸載的計(jì)算任務(wù)也因此增加,但是在相同的任務(wù)到達(dá)率的條件下,本文方法比在隊(duì)列穩(wěn)定條件下的方法所需的時(shí)延更少,效益更好.在同一種方法下,設(shè)置不同的平均任務(wù)到達(dá)率參數(shù),用于動(dòng)態(tài)卸載所需要的時(shí)延也有所不同.

綜上,本文提出的動(dòng)態(tài)計(jì)算卸載方法相比于在隊(duì)列穩(wěn)定性約束條件下的資源分配策略有更好的性能和效益,能有效降低用戶設(shè)備長(zhǎng)期平均功耗.

5 總 結(jié)

本文主要研究在MEC下的動(dòng)態(tài)聯(lián)合無(wú)線資源和計(jì)算資源的計(jì)算卸載中的資源分配問(wèn)題.考慮在平均時(shí)延和失效概率約束條件,最小化用戶設(shè)備長(zhǎng)期平均功耗問(wèn)題.為了實(shí)現(xiàn)功耗與隊(duì)列長(zhǎng)度的最佳權(quán)衡,基于隨機(jī)優(yōu)化理論,引入一個(gè)在線算法框架用于處理系統(tǒng)的動(dòng)態(tài)特性,引入匹配理論實(shí)現(xiàn)用戶設(shè)備與移動(dòng)邊緣主機(jī)之間的相互關(guān)聯(lián).通過(guò)與隊(duì)列穩(wěn)定性約束下的計(jì)算卸載資源分配策略進(jìn)行數(shù)值仿真實(shí)驗(yàn)對(duì)比,證明了所提出的方法對(duì)系統(tǒng)具有潛在的增益,能有效的降低總用戶設(shè)備的長(zhǎng)期平均功耗.