基于混合粒子群算法的計(jì)算卸載成本優(yōu)化

周天清 曾新亮 胡海琴

(華東交通大學(xué)信息工程學(xué)院 南昌 330013)

1 引言

近年來，隨著移動(dòng)終端(Mobile Terminal,MT)的爆發(fā)式增加，以及自動(dòng)駕駛、人工智能、虛擬現(xiàn)實(shí)/增強(qiáng)現(xiàn)實(shí)(VR/AR)等急需計(jì)算資源且對(duì)時(shí)延有極高要求的計(jì)算密集型業(yè)務(wù)的不斷增長(zhǎng)，給資源受限的移動(dòng)計(jì)算系統(tǒng)和無線通信網(wǎng)絡(luò)帶來了前所未有的挑戰(zhàn)[1,2]。

移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)通過將計(jì)算和存儲(chǔ)資源部署在網(wǎng)絡(luò)邊緣，允許MT將計(jì)算任務(wù)卸載到邊緣服務(wù)器，為用戶提供了超低時(shí)延、高帶寬的網(wǎng)絡(luò)服務(wù)[3]。但是，由于無線和計(jì)算資源有限，如果太多的MT將其計(jì)算任務(wù)卸載到MEC服務(wù)器，會(huì)導(dǎo)致嚴(yán)重的網(wǎng)絡(luò)計(jì)算擁塞和干擾[4]。超密集異構(gòu)網(wǎng)絡(luò)[5]通過在宏小區(qū)中部署更為密集的小基站(Small Base Station, SBS)并與MEC相結(jié)合，能進(jìn)一步縮短MT與MEC服務(wù)器間的距離以降低傳輸時(shí)延及支持海量鏈接。

時(shí)延和能耗作為計(jì)算卸載性能評(píng)估的重要指標(biāo)，近年來得到了深入的研究。文獻(xiàn)[6]提出了一種延遲感知計(jì)算卸載算法，聯(lián)合優(yōu)化保密配置、計(jì)算卸載和無線資源分配，以最大限度地減少整體執(zhí)行延遲。文獻(xiàn)[7]在超密集網(wǎng)絡(luò)場(chǎng)景下對(duì)卸載策略、信道資源和傳輸功率進(jìn)行聯(lián)合優(yōu)化，以最小化系統(tǒng)能耗。文獻(xiàn)[8]建立SBS和宏基站(Macro Base Station,MBS)之間的無線回程鏈路以實(shí)現(xiàn)共享頻譜的目的，并最終最小化能耗和執(zhí)行時(shí)間的加權(quán)和。但是上述研究或是利用單個(gè)MEC服務(wù)器來滿足傳入的卸載請(qǐng)求，或是未實(shí)現(xiàn)MEC服務(wù)器計(jì)算資源的合理利用。而對(duì)于多MT的場(chǎng)景，MEC服務(wù)器很容易擁塞，這將直接影響用戶體驗(yàn)。

鑒于此，越來越多的研究?jī)A向于多MEC服務(wù)器的場(chǎng)景。文獻(xiàn)[9]在多用戶和多MEC服務(wù)器場(chǎng)景下，聯(lián)合優(yōu)化計(jì)算卸載和資源分配策略以最小化MT能耗。文獻(xiàn)[10]在能量約束下，通過優(yōu)化卸載決策和計(jì)算資源分配以最大限度地降低超密集網(wǎng)絡(luò)中MT的計(jì)算延遲。進(jìn)一步，為更合理分配網(wǎng)絡(luò)及計(jì)算資源，研究者開始關(guān)注卸載成本問題。文獻(xiàn)[11]針對(duì)非正交多址接入的車載邊緣計(jì)算網(wǎng)絡(luò)，聯(lián)合任務(wù)卸載、用戶分簇和計(jì)算資源塊聯(lián)合優(yōu)化以最小化任務(wù)處理成本問題。文獻(xiàn)[12]研究了基于邊緣計(jì)算的車聯(lián)網(wǎng)，通過優(yōu)化任務(wù)的卸載時(shí)間、無線帶寬分配和計(jì)算資源分配來最小化系統(tǒng)的計(jì)算與通信成本。文獻(xiàn)[13]為了最小化系統(tǒng)的計(jì)算和通信成本，提出了一種具有垂直和水平卸載的4層云邊緣計(jì)算系統(tǒng)。雖然文獻(xiàn)[11-13]考慮了任務(wù)卸載時(shí)所需支付的計(jì)算和通信費(fèi)用，但未連同任務(wù)在本地計(jì)算時(shí)產(chǎn)生的開銷一起考慮。

不同于上述研究，本文研究了融合MEC的超密集異構(gòu)網(wǎng)絡(luò)下多小區(qū)多用戶的計(jì)算卸載問題，將聯(lián)合執(zhí)行計(jì)算卸載和計(jì)算資源管理，并在相同的帶寬利用率下最小化用戶的任務(wù)處理成本。其中，任務(wù)處理成本由本地能耗開銷、無線頻譜占用開銷和邊緣計(jì)算資源租用開銷3部分組成。本文的主要貢獻(xiàn)總結(jié)如下：

(1)在融合MEC的超密集異構(gòu)網(wǎng)絡(luò)中，將用戶任務(wù)處理所需支付的費(fèi)用作為計(jì)算卸載成本，聯(lián)合無線資源、計(jì)算資源管理，滿足時(shí)延約束的同時(shí)，使所有用戶的任務(wù)處理成本最小化，并建立相應(yīng)的問題模型。

(2)設(shè)計(jì)了混合粒子群優(yōu)化(Hybrid Particle Swarm Optimization, HPSO)算法來解決上述非凸問題，該算法先后執(zhí)行多樣性增強(qiáng)(Diversity Enhancement, DE)的自適應(yīng)遺傳算法和自適應(yīng)粒子群算法。但不同于文獻(xiàn)[14]中的分層自適應(yīng)搜索(Hierarchical Adaptive Search, HAS)算法，HPSO算法引入了部分參量的規(guī)范化處理，且改變了粒子群算法的權(quán)重更新規(guī)則以提升粒子群算法的收斂速度。此外，與[4,14]不同的是，為更合理地分配MEC服務(wù)器的計(jì)算資源，HPSO算法改進(jìn)了遺傳算法中的資源塊初始化操作，并由此引進(jìn)了計(jì)算資源塊按需分配策略。最后，通過仿真驗(yàn)證了本文所提算法優(yōu)越性。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

超密集異構(gòu)邊緣計(jì)算網(wǎng)絡(luò)的系統(tǒng)模型如圖1所示，每個(gè)六邊形的蜂窩網(wǎng)格包含1個(gè)宏基站(MBS)、N個(gè)微基站(SBS)和K個(gè)MT，并且每個(gè)基站配有一個(gè)MEC服務(wù)器。不失一般性的情況下，本文考慮一個(gè)MBS的場(chǎng)景。假設(shè)基站的索引集合為N={1,2,...,n,...,N,N+1}，其中MBS的索引為N+1，MT集合表示為K={1,2,...,k,...,K}。

考慮到SBS的小范圍覆蓋和超密集部署，為降低控制開銷，SBS的控制信令可由MBS負(fù)責(zé)處理。類似文獻(xiàn)[14]，本文亦將頻帶分割為控制面和用戶面，其中控制面用于傳輸控制信令，用戶面用于傳輸數(shù)據(jù)。由于計(jì)算卸載發(fā)生在用戶面，因此計(jì)算卸載機(jī)制研究時(shí)僅需關(guān)注此平面。在圖1中，MT可以選擇將自己的數(shù)據(jù)任務(wù)上傳至SBS或者M(jìn)BS上進(jìn)行處理，亦可自身完成計(jì)算任務(wù)。值得注意的是，MBS不僅需要處理網(wǎng)格中的所有控制信令，還需處理由MT上傳的數(shù)據(jù)，而SBS僅需完成數(shù)據(jù)處理任務(wù)。在計(jì)算卸載過程中，對(duì)于任何任務(wù)，如果其本地計(jì)算時(shí)延小于任務(wù)截止時(shí)間，MT會(huì)選擇本地計(jì)算以降低額外開銷，否則MT將任務(wù)上傳至基站進(jìn)行計(jì)算以減少時(shí)延，保證滿足時(shí)延約束。

圖1 系統(tǒng)模型

一般來說，計(jì)算卸載包括以下3個(gè)階段。首先，MT的計(jì)算任務(wù)通過無線信道上傳到BS上；然后，BS執(zhí)行計(jì)算任務(wù)；最后，BS反饋計(jì)算結(jié)果給MT?？紤]到計(jì)算結(jié)果的數(shù)據(jù)量相對(duì)較小，反饋過程可忽略不計(jì)。

2.2 資源模型

如圖1所示，每個(gè)宏小區(qū)內(nèi)所有小基站形成一個(gè)簇。為消除層間和層內(nèi)的干擾，用戶面所用頻帶F被劃分為F1和F2兩部分以分別供宏基站和小基站使用，其帶寬分別為μW和( 1-μ)W，其中μ表示頻帶劃分因子。為了消除宏基站間的干擾，頻帶F1被 再次劃分成3個(gè)子帶F11,F12和F13，即相鄰宏小區(qū)中的宏基站的頻帶帶寬為μW/3。為了消除小基站簇之間的干擾，頻帶F2同樣被再次劃分成3個(gè)子帶F21,F22和F23。進(jìn)一步，為消除簇內(nèi)小基站間的干擾，任意簇所用子帶被平分給簇內(nèi)小基站，即每個(gè)小基站可利用的頻帶帶寬為 (1-μ)W/3N。最后，為了再次提升用戶上行傳輸性能，宏小區(qū)及小小區(qū)內(nèi)MT間的干擾需要被消除。為此，假設(shè)任意基站可利用的頻帶被平分給其所關(guān)聯(lián)的MT。此外，假設(shè)每個(gè)MEC服務(wù)器提供U個(gè)具有相同處理能力的計(jì)算資源塊，其索引集合記為U={1,2,...,U}，其中每個(gè)計(jì)算資源塊的處理能力記為funit。

2.3 通信模型

2.4 計(jì)算模型

3 問題建模

顯然，問題P2是非凸優(yōu)化問題，其目標(biāo)函數(shù)和約束表現(xiàn)為混合整數(shù)及非線性的形式。

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

遺傳算法有很強(qiáng)的全局搜索能力，但是局部搜索能力較差[15]；而粒子群算法比較簡(jiǎn)單，收斂速度很快[16]，但容易陷入局部最優(yōu)值出現(xiàn)早熟。鑒于兩種算法有著互補(bǔ)的優(yōu)勢(shì)，因此，類似于文獻(xiàn)[4,14]，聯(lián)合遺傳算法和粒子群算法來開發(fā)HPSO算法以解決問題P2。為了避免過早收斂，提高收斂速度，糅合了基于DE的自適應(yīng)遺傳算法和自適應(yīng)粒子群算法，前者用于粗粒度搜索，后者則用于細(xì)粒度搜索，算法流程如圖2所示。

圖2 算法流程圖

4.1 遺傳算法

作為一種隨機(jī)搜索算法，遺傳算法從一組初始可行解集開始，其關(guān)鍵因素及相應(yīng)步驟如下：

(1)染色體。在問題P2中，優(yōu)化參量X被編碼成染色體S={sik,?i ∈I,?k ∈K}， 參量λ被編碼成染色體Q={qik,?i ∈I,?k ∈K}， 其中I={1,2,...,I}為個(gè)體集群。在任意個(gè)體i中，sik和qik分別表示MTk所選擇的基站索引號(hào)及所獲取的計(jì)算資源塊數(shù)，sik=0表示個(gè)體i中的MTk不選擇基站，在本地完成計(jì)算任務(wù)。

(2)適應(yīng)度函數(shù)?？紤]到約束C1具備混合整數(shù)非線性的形式，在遺傳算法的初始化和基因操作中難以滿足，它被作為一個(gè)懲罰項(xiàng)引入適應(yīng)度函數(shù)中。鑒于此，為解決問題P2，個(gè)體i的適應(yīng)度函數(shù)被定義為

結(jié)合上述遺傳算法因素，基于DE的自適應(yīng)遺傳算法的完整過程可概述表1。

表1 基于DE的自適應(yīng)遺傳算法(算法1)

4.2 粒子群算法

在粒子群算法中，粒子(個(gè)體)的位置代表問題P2的解，速度則展示解的演化情況。粒子群算法中粒子的初始位置取值為算法1的輸出值。具體而言，粒子群算法的關(guān)鍵要素及步驟如下。

結(jié)合上述要素，自適應(yīng)粒子群算法的完整過程可被概述表2。

表3 計(jì)算資源塊按需分配策略(算法3)

5 仿真及對(duì)比分析

5.1 參數(shù)設(shè)置

在仿真中，本文主要研究了計(jì)算資源塊和無線信道資源的單位價(jià)格對(duì)不同卸載算法的任務(wù)平均處理時(shí)延及任務(wù)平均處理成本的影響。通過對(duì)比任務(wù)的平均處理時(shí)延和成本及算法的收斂性來論證所設(shè)計(jì)算法的有效性。為此，引入如下其他算法作為對(duì)照組。

全本地算法：所有MT的計(jì)算任務(wù)都在本地執(zhí)行；全關(guān)聯(lián)算法：所有MT的計(jì)算任務(wù)都卸載到MEC服務(wù)器上執(zhí)行，其中計(jì)算資源塊分配方式為隨機(jī)分配。此外，在全關(guān)聯(lián)算法中，本文考慮的是將MT的計(jì)算任務(wù)卸載到與其對(duì)應(yīng)的信道增益最好的基站上；HGP算法：此算法為文獻(xiàn)[4]中分層的遺傳和粒子群優(yōu)化 (Hierarchical Genetic and Particle swarm optimization, HGP)算法，其中計(jì)算資源塊分配方式為隨機(jī)分配；HAS算法：此算法為文獻(xiàn)[14]中的分層自適應(yīng)搜索算法，其中計(jì)算資源塊分配方式為隨機(jī)分配。

5.2 結(jié)果分析

圖3給出了兩種資源單價(jià)的變化對(duì)任務(wù)平均處理時(shí)延的影響。在圖3(a)中，無線資源單價(jià)ω2固定為1 元/(MHz·s)，在圖3(b)中，計(jì)算資源塊的單價(jià)ω3固定為0.1元。可以看到，幾種算法下的任務(wù)平均處理時(shí)延并不會(huì)隨著計(jì)算資源塊或無線資源單價(jià)的變動(dòng)而受到影響。這是因?yàn)閷?duì)于在本地計(jì)算的任務(wù)而言，其處理時(shí)延主要取決于任務(wù)的數(shù)據(jù)量和MT的計(jì)算能力，而對(duì)于要上傳到基站進(jìn)行計(jì)算的任務(wù)，其處理時(shí)延主要取決于傳輸時(shí)的信道狀態(tài)和分到的計(jì)算資源塊個(gè)數(shù)。

此外，在圖3中，全本地算法的任務(wù)平均處理時(shí)延最長(zhǎng)，全關(guān)聯(lián)算法最短，其他3種算法則介于兩者之間。這是由于其他3種算法考慮了任務(wù)截止時(shí)延的約束，對(duì)于無法在截止時(shí)延內(nèi)完成計(jì)算任務(wù)的MT，這3種算法才會(huì)選擇關(guān)聯(lián)基站，而全本地算法中實(shí)際存在著不滿足時(shí)延約束的MT。在全關(guān)聯(lián)算法中，雖然所有任務(wù)的時(shí)延約束都滿足了，但該算法的任務(wù)平均處理成本也是最高的。相比于全本地算法，引入資源塊按需分配策略的HPSO算法的任務(wù)平均處理時(shí)延縮短了約25%，資源塊隨機(jī)分配策略下的HAS算法則更低。這是因?yàn)檫@兩種算法都滿足了時(shí)延約束(由圖5(b)可驗(yàn)證)，但在隨機(jī)分配策略下，計(jì)算資源塊可能存在額外分配的情況。因此，HAS算法下任務(wù)平均處理時(shí)間會(huì)更短，這也意味著HAS算法的開銷會(huì)更高。

圖3 單價(jià)變化對(duì)任務(wù)平均處理時(shí)延的影響

圖4為兩種資源單價(jià)的變化對(duì)任務(wù)平均處理成本的影響。在圖4(a)中，隨著計(jì)算資源塊單價(jià)的增加，除全本地算法外，其他算法的任務(wù)平均處理成本都相應(yīng)地增加了。雖然全本地算法的任務(wù)平均處理成本最低，但是它不能保證所有任務(wù)都滿足時(shí)延約束。隨機(jī)分配策略下的全關(guān)聯(lián)算法的任務(wù)平均處理成本最高，這是因?yàn)樗蠱T都選擇將任務(wù)上傳至基站進(jìn)行計(jì)算，甚至是一些滿足時(shí)延約束，可以在本地完成計(jì)算的任務(wù)。另外，可以發(fā)現(xiàn)，引入資源塊按需分配策略的HPSO算法是使得任務(wù)平均處理成本最低的算法。

表4 實(shí)驗(yàn)參數(shù)

在圖4(b)中，引入資源塊按需分配策略的HPSO算法依舊是任務(wù)處理成本最小的算法。此外，會(huì)發(fā)現(xiàn)隨著無線資源單價(jià)的不斷提高，HGP算法的任務(wù)平均處理成本逐漸逼近甚至高于全關(guān)聯(lián)算法。這是因?yàn)殡S著無線資源單價(jià)的提高，傳輸費(fèi)用會(huì)成為任務(wù)處理的主要開銷。結(jié)合式(10)也不難理解，雖然在全關(guān)聯(lián)算法中或許將一部分可以在本地進(jìn)行計(jì)算的任務(wù)上傳到了基站，但每次選擇的都是對(duì)應(yīng)信道增益最好的基站，而HGP算法由于無法找到一個(gè)合適的解(由圖5(b)可驗(yàn)證)，最后得到的卸載決策可能并不理想。因此，最終會(huì)導(dǎo)致HGP算法下的任務(wù)平均處理成本逐漸逼近甚至高于全關(guān)聯(lián)算法。

圖4 單價(jià)變化對(duì)任務(wù)平均處理成本的影響

圖5給出了適應(yīng)度值在遺傳和粒子群算法部分的收斂變化情況。從圖5(a)可以發(fā)現(xiàn)，在有限的迭代次數(shù)內(nèi)，HGP算法中傳統(tǒng)的遺傳算法難以求解P2這一混合整數(shù)非線性規(guī)劃問題。而相較于HAS算法中改進(jìn)的遺傳算法，HPSO算法中的自適應(yīng)遺傳算法由于一開始引入計(jì)算資源塊按需分配策略，使得資源約束條件變得更為苛刻。因此，初始化時(shí)最優(yōu)個(gè)體的適應(yīng)度值較高，但在迭代過程中會(huì)快速收斂。

在圖5(b)中，HGP算法中傳統(tǒng)的粒子群算法在迭代求解過程中依舊沒有找到合適的可行解。相比于會(huì)對(duì)全局最佳粒子的速度和位置進(jìn)行更新的自適應(yīng)粒子群算法，HAS算法和HPSO算法中的自適應(yīng)粒子群算法最終都能收斂。此外，容易發(fā)現(xiàn)，采用非線性慣性權(quán)重的HPSO算法相比采用線性慣性權(quán)重的HAS算法收斂速度明顯更快，并且最終的收斂結(jié)果更好。

圖5 適應(yīng)度值的搜索情況

6 結(jié)束語

本文研究了超密集異構(gòu)邊緣計(jì)算網(wǎng)絡(luò)中任務(wù)處理成本最小優(yōu)化問題。具體而言，在延遲和計(jì)算資源約束條件下，聯(lián)合優(yōu)化了計(jì)算卸載和MEC服務(wù)器的計(jì)算資源塊分配以使用戶的任務(wù)處理成本降最小。在此之前，一個(gè)有效的頻帶劃分方案被引入以用于消除平面間、層間和層內(nèi)的干擾?？紤]到最終所規(guī)劃的問題具備非線性且混合整數(shù)形式，同時(shí)為滿足問題約束條件及提升算法收斂速度，本文改進(jìn)HAS以獲取HPSO算法。仿真結(jié)果表明，同其他卸載算法相比，HPSO算法在減少任務(wù)處理成本方面具有顯著的優(yōu)勢(shì)。