超密集邊緣計(jì)算網(wǎng)絡(luò)中面向能耗優(yōu)化的任務(wù)卸載方法

曾蓉暉，林 兵，王明芬，林 凱，盧 宇，

（1.福建師范大學(xué) 物理與能源學(xué)院，福州 350000；2.福建師范大學(xué) 協(xié)和學(xué)院，福州 350000）

0 概述

2022 年，全球移動設(shè)備的數(shù)量將會達(dá)到123 億臺［1］。隨著智能汽車、手機(jī)、無人機(jī)等一些移動設(shè)備數(shù)量的爆炸式增長，移動應(yīng)用的數(shù)量和類型也在不斷地增加，這些移動應(yīng)用通常需要強(qiáng)大的計(jì)算資源才能在響應(yīng)截止期內(nèi)被執(zhí)行完成，這對移動設(shè)備的計(jì)算能力和電池壽命都提出了嚴(yán)峻的挑戰(zhàn)［2］。

移動邊緣計(jì)算（Mobile Edge Computing，MEC）作為一種新的計(jì)算框架，可滿足移動用戶低時(shí)延高可靠的計(jì)算需求［3］。MEC 服務(wù)器通常部署在距離用戶較近的位置，從而擴(kuò)展移動設(shè)備的計(jì)算能力，將移動設(shè)備產(chǎn)生的計(jì)算任務(wù)從移動設(shè)備卸載到網(wǎng)絡(luò)邊緣，從而有效緩解移動設(shè)備的計(jì)算壓力，降低任務(wù)卸載的能耗和時(shí)延［4］。然而邊緣服務(wù)器的計(jì)算資源有限，傳統(tǒng)蜂窩無線網(wǎng)絡(luò)部署下的MEC 很難滿足大規(guī)模用戶設(shè)備的接入和通信質(zhì)量要求，傳輸過程中可分配的無線頻譜資源也會變得更加稀缺。為了更好地應(yīng)對5G 和物聯(lián)網(wǎng)時(shí)代對計(jì)算資源和頻譜資源的激增要求，迫切需要更先進(jìn)的組網(wǎng)方式和無線接入技術(shù)來增加網(wǎng)絡(luò)容量，提高頻譜利用率［5］。因此，研究者在此基礎(chǔ)上引入超密集網(wǎng)絡(luò)（Ultra-Dense Network，UDN）。

UDN 具有強(qiáng)大的接入能力，能夠在傳統(tǒng)宏小區(qū)覆蓋的基礎(chǔ)上，加密小型小區(qū)的部署，從而為移動設(shè)備提供足夠的頻譜資源，此外，通過重用小區(qū)間的有限頻譜，能夠顯著提高網(wǎng)絡(luò)頻譜利用率和網(wǎng)絡(luò)容量［6］。在UDN 的基站上部署MEC 服務(wù)器，可以形成超密集邊緣計(jì)算網(wǎng)絡(luò)，其中小基站（Small Base Station，SBS）的密集部署能夠覆蓋更多移動設(shè)備，為它們提供接入服務(wù)，打破傳統(tǒng)宏網(wǎng)絡(luò)單層覆蓋的缺陷，提高網(wǎng)絡(luò)容量，增加頻譜效率；而連接小基站的MEC 服務(wù)器則為移動設(shè)備提供了豐富的計(jì)算資源。文獻(xiàn)［7］也闡述了在UDN 中，移動運(yùn)營商通過部署大量宏基站和小功率的微基站為移動設(shè)備提供服務(wù)，能夠應(yīng)對大規(guī)模設(shè)備連接和數(shù)據(jù)流量，有效降低系統(tǒng)能耗。然而超密集邊緣計(jì)算網(wǎng)絡(luò)中的任務(wù)卸載也存在一系列的挑戰(zhàn)。首先，每個(gè)連接MEC 服務(wù)器的SBS 同時(shí)為多個(gè)移動設(shè)備提供接入服務(wù)時(shí)，需要在考慮信道狀態(tài)變化的同時(shí)，將計(jì)算資源分配給不同的服務(wù)請求；其次，移動設(shè)備需要選擇對應(yīng)的信道將任務(wù)卸載到MEC 服務(wù)器上，大量移動設(shè)備選擇同一個(gè)信道競爭有限的頻譜資源時(shí)，將會產(chǎn)生設(shè)備間干擾，影響通信質(zhì)量；最后，在任務(wù)傳輸過程中，任務(wù)執(zhí)行延遲和能耗會受到發(fā)射功率的影響。

近年來，關(guān)于超密集邊緣計(jì)算網(wǎng)絡(luò)中的任務(wù)卸載研究大多集中在計(jì)算卸載和資源分配的聯(lián)合優(yōu)化：文獻(xiàn)［8］提出一種新的卸載方案和資源分配方案，將多個(gè)任務(wù)卸載到同一個(gè)邊緣服務(wù)器，在計(jì)算資源和延遲的約束下降低了卸載能耗；文獻(xiàn)［9］利用凸優(yōu)化的方法研究TDMA 和OFDMA 系統(tǒng)中部分卸載的最優(yōu)策略，提出一種基于門限的卸載優(yōu)先級函數(shù)；文獻(xiàn)［10］則僅在TDMA 系統(tǒng)中用凸優(yōu)化研究了多用戶接入單個(gè)邊緣服務(wù)器場景下進(jìn)行計(jì)算任務(wù)卸載決策的最優(yōu)策略。然而，這些研究多數(shù)只適用于單個(gè)服務(wù)器的情況，而在實(shí)際超密集邊緣計(jì)算網(wǎng)絡(luò)的場景中，往往需要考慮多個(gè)服務(wù)器部署的情況。對此：文獻(xiàn)［11］研究系統(tǒng)節(jié)能卸載方案，提出一種遺傳算法和粒子群算法的優(yōu)化算法；文獻(xiàn)［12］研究多個(gè)用戶通過多個(gè)小基站共享一個(gè)邊緣服務(wù)器的場景，考慮不同用戶與小基站通信時(shí)的干擾問題，提出一種分步優(yōu)化的卸載決策，計(jì)算資源分配以最小化系統(tǒng)能耗和時(shí)延的加權(quán)和，同時(shí)利用圖染色法解決無線資源分配的問題并最小化用戶間干擾。

對于混合性能指標(biāo)的問題，在計(jì)算和通信過程中，時(shí)延和能耗需要進(jìn)行互相妥協(xié)。然而在實(shí)際的超密集邊緣計(jì)算網(wǎng)絡(luò)場景下，一些服務(wù)請求往往需要對時(shí)延進(jìn)行硬性約束。為此，許多研究側(cè)重于將時(shí)延約束下能耗最小化作為優(yōu)化目標(biāo)：為了同時(shí)解決邊緣服務(wù)器計(jì)算資源有限以及傳輸干擾等問題，文獻(xiàn)［13］針對多移動設(shè)備場景下的卸載問題，在考慮信道和計(jì)算資源成本的同時(shí)，通過制定有效的資源分配策略，最小化用戶的總消耗；文獻(xiàn)［14］提出一種基于博弈的任務(wù)卸載算法，解決了在小小區(qū)網(wǎng)絡(luò)架構(gòu)下的計(jì)算卸載問題；文獻(xiàn)［15］討論了物聯(lián)網(wǎng)設(shè)備下的動態(tài)任務(wù)卸載問題，在軟件定義接入網(wǎng)絡(luò)中提出了一種基于物聯(lián)網(wǎng)設(shè)備的任務(wù)卸載方案，最后通過線性化方法，將問題轉(zhuǎn)化為整數(shù)線性規(guī)劃問題，最終所提出的方案可以有效降低平均延遲和能量消耗。

以上研究提出了許多計(jì)算資源分配和計(jì)算卸載的方案，也考慮了用戶與基站通信時(shí)的干擾問題，但忽略了信道狀態(tài)動態(tài)變化時(shí)對卸載結(jié)果的影響，以及發(fā)射功率對移動設(shè)備與基站通信過程的影響。本文重點(diǎn)考慮信道狀態(tài)、發(fā)射功率等因素，討論任務(wù)傳輸干擾對卸載結(jié)果的影響，設(shè)計(jì)一種基于自適應(yīng)模擬退火遺傳（Adaptive Genetic Algorithm with Simulate Annealing，AGASA）算法的任務(wù)卸載策略，在滿足截止期約束的同時(shí)，對任務(wù)卸載能耗進(jìn)行優(yōu)化，并通過黃金分割算法求解最優(yōu)上傳功率。

1 系統(tǒng)模型

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

本文主要討論一個(gè)宏基站覆蓋范圍下，N個(gè)SBS部署的超密集邊緣計(jì)算網(wǎng)絡(luò)的場景，考慮將大量用戶設(shè)備（User Equipment，UE）產(chǎn)生的任務(wù)請求卸載到連接SBS 的MEC 上以及本地處理，具體的系統(tǒng)框架如圖1 所示。其中，宏基站是整個(gè)網(wǎng)絡(luò)的信息中心，可以收集整個(gè)網(wǎng)絡(luò)的信息，而宏基站和各個(gè)SBS之間可共享整個(gè)信道的頻譜資源。同時(shí)，每個(gè)UE 每次只能將任務(wù)請求發(fā)送到一個(gè)SBS 上，SBS 與一個(gè)邊緣服務(wù)器相連接，邊緣服務(wù)器表示為S={s1，s2，…，sn}，同時(shí)每個(gè)服務(wù)器的計(jì)算資源每次只能分配給一個(gè)UE。

圖1 超密集邊緣計(jì)算網(wǎng)絡(luò)架構(gòu)Fig.1 Ultra-dense edge computing network architecture

根據(jù)正交頻分復(fù)用技術(shù)，本文將每個(gè)SBS 覆蓋范圍內(nèi)的信道劃分成C個(gè)子信道，并將信道描述為K={k1，k2，…，kC}，不同信道之間互不 干擾。每個(gè)移動設(shè)備產(chǎn)生一個(gè)計(jì)算任務(wù)，且任務(wù)卸載過程中UE 不移動。因?yàn)椴煌^(qū)的UE 可能會復(fù)用相同的子信道，所以不同用戶在相同的信道傳輸任務(wù)時(shí)會產(chǎn)生用戶間的干擾。在本文系統(tǒng)中，UE 的集合表示為U={U1，U2，…，UM}，對應(yīng)的UE 產(chǎn)生的任務(wù)集合表示為T={T1，T2，…，Tm}，服務(wù)器和UE 的計(jì)算資源表示為f={fm，fs1，fs2，…，fsn}。

1.2 任務(wù)模型

由于每個(gè)設(shè)備產(chǎn)生一個(gè)任務(wù)，因此將Ti=(ωi，si，di，ti_deadline)表示為一個(gè)UE 產(chǎn)生的計(jì)算任務(wù)。其中：ωi表示完成任務(wù)Ti所需的計(jì)算量大??；si表示每個(gè)任務(wù)Ti的數(shù)據(jù)量大小，為產(chǎn)生任務(wù)Ti的UE 到SBS 的距離；ti_deadline表示完成任務(wù)Ti的截止時(shí)間。在超密集邊緣計(jì)算網(wǎng)絡(luò)中，每個(gè)UE 都有一個(gè)計(jì)算任務(wù)需要被處理，因此，定義二元決策變量xi，j={0，1}表示任務(wù)的卸載決策，xi，j=0 表示任務(wù)Ti選擇本地處理，xi，j=1 表示任務(wù)Ti需要卸載到服務(wù)器sj。此 外，定義二元決策變量γi，k={0，1}表示任務(wù)Ti的信道分配決 策，γi，k=1 表示任務(wù)Ti通過信道k傳輸，γi，k=0 表 示不通過信道傳輸。

1.3 通信模型

當(dāng)UE 選擇將任務(wù)Ti卸載到第n個(gè)SBS 連接的服務(wù)器sn上，不同移動用戶共享相同信道頻譜資源時(shí)，Ui會接收到來自其他移動用戶的傳輸干擾。因此，由移動用戶Ui產(chǎn)生的任務(wù)Ti在信道k上傳輸時(shí)的有效干擾表示為：

其 中：gi，k表示任務(wù)Ti在信道k上傳輸時(shí)對應(yīng)的信道增益；σ2表示噪聲功率譜密度。

因此，任務(wù)Ti在信道k傳輸時(shí)的信噪比為：

通過計(jì)算，得到UE 產(chǎn)生的任務(wù)Ti在信道k上的傳輸速率為：

其中：W表示子信道的帶寬；Pi，k表示任務(wù)Ti的上傳功率。

1.4 計(jì)算模型

當(dāng)計(jì)算任務(wù)選擇本地處理時(shí)，需要產(chǎn)生任務(wù)請求Ti的移動設(shè)備Um提供計(jì)算資源。令fm表示移動設(shè)備Um的計(jì)算能力，并將移動設(shè)備Um的本地計(jì)算功率表示為Pm，則任務(wù)本地處理時(shí)的能耗Ei，0和計(jì)算時(shí)間分別表示為：

當(dāng)選擇卸載計(jì)算時(shí)，通過無線網(wǎng)絡(luò)傳輸任務(wù)時(shí)會產(chǎn)生相應(yīng)的傳輸能耗和計(jì)算能耗，其中傳輸能耗傳輸時(shí)間、計(jì)算能耗和計(jì)算時(shí)間分別表示為：

將選擇本地處理的用戶總能耗表示為Em，那么對于超密集邊緣計(jì)算網(wǎng)絡(luò)中所有的UE，此時(shí)的任務(wù)總能耗為：

同時(shí)，將卸載的用戶的總能耗表示為Ec，在整個(gè)超密集邊緣計(jì)算網(wǎng)絡(luò)中，所有需要將UE 產(chǎn)生的任務(wù)請求卸載到MEC 的總能耗，包括將任務(wù)請求發(fā)送到SBS 上的傳輸能耗，以及在MEC 上處理的計(jì)算能耗兩部分，那么卸載任務(wù)的總能耗為：

卸載任務(wù)產(chǎn)生的總時(shí)延包括傳輸時(shí)延和MEC上的計(jì)算時(shí)延，表示為：

由于下行鏈路的傳輸數(shù)據(jù)量很小，對整體卸載結(jié)果影響不大，因此本文不考慮接收返回?cái)?shù)據(jù)時(shí)的能耗和時(shí)延。

2 問題描述與解決方案

2.1 基于信道狀態(tài)的卸載決策優(yōu)化

移動設(shè)備通過無線信道向MEC 服務(wù)器傳輸數(shù)據(jù)，當(dāng)任務(wù)通過無線信道上傳到SBS 上時(shí)，基站密集部署下網(wǎng)絡(luò)環(huán)境比較復(fù)雜，而實(shí)際任務(wù)傳輸過程中信道狀態(tài)是不斷變化的，因此，信道狀態(tài)的好壞會影響當(dāng)前任務(wù)的傳輸速率。為了更好地描述實(shí)際信道狀態(tài)變化對任務(wù)傳輸過程通信質(zhì)量的影響，本文將超密集邊緣計(jì)算網(wǎng)絡(luò)中的無線信道擬合成Gilbert Elliot 模型［16］，提出一種基于信道狀態(tài)的任務(wù)卸載方案。首先假設(shè)在時(shí)間片t內(nèi)檢測到的無線信道的狀態(tài)為gt，當(dāng)前信道狀態(tài)較差時(shí)，信道狀態(tài)描述為gB，當(dāng)前信道狀態(tài)較好時(shí)，信道狀態(tài)描述為gG。將gt=gG時(shí)對應(yīng)的傳輸速率描述為Rt=RG，同時(shí)將gt=gB時(shí)對應(yīng)的傳輸速率描述為Rt=RB。此外，為了具體描述超密集邊緣計(jì)算網(wǎng)絡(luò)中實(shí)際的信道狀態(tài)，用狀態(tài)轉(zhuǎn)移概率來表示實(shí)時(shí)信道狀態(tài)變化的情況，當(dāng)信道狀態(tài)從差變成好時(shí)，信道狀態(tài)轉(zhuǎn)移概率為PBG，而當(dāng)信道狀態(tài)從好變成差時(shí)，信道狀態(tài)轉(zhuǎn)移概率描述為PGB。因此，信道狀態(tài)較好時(shí)信道狀態(tài)的穩(wěn)定概率為，信道狀態(tài)不好時(shí)的穩(wěn)定概率為。根據(jù)信道狀態(tài)的穩(wěn)定概率，可以得到信道傳輸速率的期望值為：

在任務(wù)卸載過程中，由于信道狀態(tài)是實(shí)時(shí)變化的，當(dāng)信道狀態(tài)不好時(shí)，數(shù)據(jù)傳輸速率較低，因此會產(chǎn)生更多的傳輸能耗和時(shí)延；同時(shí)，隨著接入SBS 的移動設(shè)備Ui數(shù)量增加，任務(wù)卸載能耗和時(shí)延也會隨之增加。所以，本文根據(jù)當(dāng)前超密集邊緣計(jì)算網(wǎng)絡(luò)的信道狀態(tài)、任務(wù)屬性和所需計(jì)算資源制定了相應(yīng)的卸載方案。在該方案中，當(dāng)任務(wù)Ti初始化選擇本地處理時(shí)，如果滿足式（14），則表明綜合考慮計(jì)算任務(wù)Ti所需計(jì)算資源以及當(dāng)前信道狀態(tài)情況，選擇該任務(wù)上傳到服務(wù)器Sm能夠在保證通信質(zhì)量的同時(shí)節(jié)約計(jì)算資源。因此，任務(wù)卸載方案需要更新為卸載到服務(wù)器上。

同理，如果任務(wù)Ti初始化選擇卸載到MEC 上處理，那么當(dāng)任務(wù)類型滿足式（15），則表明針對任務(wù)Ti，相比于本地計(jì)算，卸載到MEC 可能無法保證通信質(zhì)量，更好地節(jié)約計(jì)算資源，則當(dāng)前的卸載方案需要更新為本地處理。

上述方案基于當(dāng)前的信道狀態(tài)和任務(wù)類型不斷更新卸載決策，以保證卸載的任務(wù)能夠在信道狀態(tài)良好的情況下傳輸和處理，最終得到盡可能優(yōu)的卸載決策，降低任務(wù)卸載的總能耗。

2.2 卸載用戶的信道分配方案

由于每個(gè)任務(wù)只能選擇一個(gè)信道進(jìn)行傳輸，而任務(wù)傳輸能耗主要受傳輸速率和信道分配決策的影響，因此為盡可能降低任務(wù)傳輸過程的能耗，本文給出了信道分配決策的優(yōu)化方案。由于同一基站服務(wù)范圍內(nèi)的移動用戶以及其他小區(qū)的移動用戶可能會共用相同的頻譜資源，從而產(chǎn)生信道干擾，因此為保證任務(wù)請求Ti通過信道k的傳輸速率，需要對傳輸過程的信道干擾大小進(jìn)行一定的限制。由此，根據(jù)約束條件C1（下文給出）可得，任務(wù)Ti有效干擾需要滿足：

最后得到信道分配方案γi，k，如式（18）所示，表明在任務(wù)傳輸過程中，需要選擇傳輸能耗最低且滿足約束條件C6（下文給出）的信道分配決策。

2.3 卸載用戶的上傳功率控制方案

同理，由截止時(shí)間的約束條件C1（下文給出）可以得到最小任務(wù)上傳功率如下：

2.4 優(yōu)化目標(biāo)

因?yàn)楸疚牡哪繕?biāo)是在截止時(shí)間內(nèi)最小化任務(wù)卸載的總能耗，所以將超密集邊緣計(jì)算網(wǎng)絡(luò)中所有移動設(shè)備任務(wù)卸載的總能耗作為優(yōu)化目標(biāo)。在該網(wǎng)絡(luò)中，一些UE 選擇任務(wù)請求進(jìn)行本地處理，則總能耗為；一些UE 選擇將任務(wù)請求卸載到連接SBS 的邊緣服務(wù)器上，則總能耗由傳輸能耗和計(jì)算能耗兩部分組成。由于優(yōu)化目標(biāo)是一個(gè)單目標(biāo)多變量的問題，為了降低問題的復(fù)雜性，利用分治的思想將優(yōu)化目標(biāo)分解成任務(wù)卸載、信道分配和功率控制三個(gè)子問題。因此，該網(wǎng)絡(luò)中的總能耗可表示為：

其中：C1 表示完成任務(wù)Ti的最大可容忍時(shí)延；C2 表示傳輸過程中任務(wù)Ti在信道k的信噪比大小大于閾值，才能保證傳輸過程的可靠性；C3 表示上傳功率的范圍；C4、C5 保證了一個(gè)任務(wù)只能卸載到一個(gè)服務(wù)器上處理，同時(shí)一個(gè)任務(wù)也只能通過一個(gè)信道傳輸；C6 表示任務(wù)的有效干擾需要大于閾值，才能保證任務(wù)傳輸質(zhì)量；C7 是信道選擇的條件。

3 算法設(shè)計(jì)與分析

3.1 基于黃金分割算法的功率控制方案

發(fā)射功率越高，任務(wù)可傳輸?shù)木嚯x越遠(yuǎn)，一旦發(fā)射功率過高，那么傳輸過程中會產(chǎn)生更多的能耗，而發(fā)射功率過低時(shí)，移動設(shè)備產(chǎn)生的任務(wù)請求無法及時(shí)到達(dá)對應(yīng)的SBS。為了更好地優(yōu)化傳輸能耗，需要將任務(wù)上傳功率控制在合理范圍內(nèi)。針對上傳功率控制的問題，本文采用一種黃金分割算法，以確定最優(yōu)的發(fā)射功率［17］，以期通過較少的迭代次數(shù)找到最優(yōu)解，得到使傳輸能耗最低的上傳功率極值。黃金分割算法描述如算法1 所示。

算法1黃金分割算法

3.2 基于AGASA 算法的任務(wù)卸載方法

研究人員常采用傳統(tǒng)智能算法來解決優(yōu)化問題［18-19］，而在超密集邊緣計(jì)算網(wǎng)絡(luò)的場景下，利用傳統(tǒng)智能算法同時(shí)求解任務(wù)卸載決策和信道分配決策難度較大，因此，本文考慮在自適應(yīng)遺傳算法（Adaptive Genetic Algorithm，AGA）的基礎(chǔ)上結(jié)合模擬退火（Simulate Annealing，SA）算法，提出AGASA算法，在更短時(shí)間內(nèi)得到卸載方案的最優(yōu)解。

AGA 算法［20］往往具有較強(qiáng)的全局搜索能力，但是在算法開始階段，由于個(gè)體間的差異較大，父代產(chǎn)生的子代個(gè)數(shù)與父代個(gè)體的適應(yīng)度值成正比，一些優(yōu)秀的個(gè)體則充斥著整個(gè)子代種群，導(dǎo)致算法在后期形成“早熟”的現(xiàn)象，最終陷入局部最優(yōu)解。而SA算法是根據(jù)物理退溫降火的原理建立的算法，該算法具備較強(qiáng)的局部搜索能力，并且能夠很好地跳出局部搜索的范圍。但是該算法對于整個(gè)搜索空間的掌握不夠全面，導(dǎo)致算法的搜索效率較低［21］。

AGASA 算法能夠很好地彌補(bǔ)以上兩種算法的不足。首先將AGA 算法初始化的種群適應(yīng)度值作為模擬退火的初始解，將交叉變異后的適應(yīng)度值作為模擬退火的新解。將根據(jù)模擬退火的更新規(guī)則得到的新解對應(yīng)的卸載方案作為AGA 算法下一代的初始方案。將AGA 算法和SA 算法結(jié)合能夠克服彼此的缺陷，AGASA 算法不僅在效率上優(yōu)于傳統(tǒng)的遺傳算法，而且還提高了全局搜索能力，更好地找到卸載最優(yōu)解。AGASA 算法描述如算法2 所示。

算法2AGASA 算法

輸入種群大小N，迭代次數(shù)，設(shè)備數(shù)，小基站數(shù)，截止時(shí)間，上傳功率

輸出卸載計(jì)劃X，信道分配方案γ

1.For i=1 to N do：

2.產(chǎn)生初始種群，生成初始化的卸載決策xi，j，信道分配決策γi，k

3.End for

4.根據(jù)算法1 更新上傳功率

5.For i=1 to N do：

6.根據(jù)條件式（14）和式（15）更新卸載決策

7.根據(jù)條件式（18）更新信道分配決策

8.根據(jù)式（21）計(jì)算種群和每個(gè)個(gè)體的適應(yīng)度值

9.End for

10.獲取初始的最優(yōu)適應(yīng)度值以及每個(gè)個(gè)體的最優(yōu)適應(yīng)度值

11.While i ＜Ditersdo

12.For j=1 to N do

13.通過選擇、交叉、變異，更新任務(wù)卸載方案

14.根據(jù)式（22）計(jì)算種群和每個(gè)個(gè)體的適應(yīng)度值

15.比較更新前后的適應(yīng)度值

16.if Fnew＜F

17.保留更新后的適應(yīng)度值

18.else：

19.根據(jù)退火概率決定是否保留更新前的適應(yīng)度值

20.End for

21.從N 個(gè)卸載計(jì)劃中找到最優(yōu)的卸載計(jì)劃

22.For j=1 to N do

23.根據(jù)式（25）和式（26）計(jì)算交叉概率和變異概率

24.根據(jù)式（24）計(jì)算退火概率

25.End for

26.End While

27.返回最優(yōu)的卸載計(jì)劃X 和信道分配方案γ

在初始化過程中，首先將可能的計(jì)算卸載方案作為遺傳算法中的染色體，將每個(gè)任務(wù)對應(yīng)的位置作為染色體的基因，那么每個(gè)染色體共有M個(gè)基因。編碼方式為整數(shù)編碼，每個(gè)任務(wù)可以選擇卸載到任意一個(gè)服務(wù)器上，并選擇對應(yīng)的一個(gè)信道去傳輸，也可以選擇本地處理。同時(shí)，為了衡量每個(gè)種群對生存環(huán)境的適應(yīng)性，還可以通過適應(yīng)度值來判斷并淘汰適應(yīng)程度更差的種群。適應(yīng)度值表示為：

當(dāng)任務(wù)完成時(shí)間超過該任務(wù)的最大截止時(shí)間時(shí)，在能耗的基礎(chǔ)上加入懲罰函數(shù)［22］：l=10-2.5，適應(yīng)度函數(shù)值為能耗和懲罰函數(shù)值之和。當(dāng)任務(wù)完成時(shí)間小于截止時(shí)間，將適應(yīng)度值設(shè)置為能耗的值。ti_deadline表示單個(gè)任務(wù)的截止時(shí)間，本文通過以下的方式計(jì)算截止時(shí)間：

其中：Dl=Tz表示AGASA 算法下的任務(wù)完成時(shí)間；Du=3Tz；k1是截止時(shí)間比例，取值范圍為0～1［23］。在AGASA 算法的選擇過程中，為了防止最優(yōu)個(gè)體在下一代發(fā)生丟失，導(dǎo)致無法收斂到最優(yōu)解，本文主要采用二元錦標(biāo)賽結(jié)合精英選擇的選擇策略［24］。首先保留當(dāng)前種群中最優(yōu)的個(gè)體進(jìn)入子代；然后以一定的選擇概率在種群中選擇兩個(gè)個(gè)體，將適應(yīng)度值較低的個(gè)體加入到子代，直到所有個(gè)體都完成錦標(biāo)賽。在交叉過程中，在父代染色體的前半段和后半段分別選擇兩個(gè)交叉點(diǎn)，進(jìn)行兩點(diǎn)交叉，形成子代染色體。在變異過程中，選擇單點(diǎn)變異的策略。交叉變異結(jié)束后，需要比較變異前后種群的適應(yīng)度值，如果變異前的適應(yīng)度值更低，那么以一定的退火概率接受變異前的個(gè)體，退火概率設(shè)置為：

將交叉變異后的適應(yīng)度值作為最終的適應(yīng)度值Fnew。此外，交叉概率和變異概率對算法的收斂性有很大的影響。雖然交叉概率較大時(shí)種群更容易產(chǎn)生新個(gè)體，但是當(dāng)其變大時(shí)，優(yōu)良個(gè)體在種群中保留率也相應(yīng)降低；而對變異概率而言，若其過大則該算法相當(dāng)于普通的隨機(jī)算法，失去了AGASA 算法的意義。所以，為了提高算法的性能，本文采取動態(tài)變化的交叉概率和變異概率，如式（25）和式（26）所示：

其中：faverage表示平均適應(yīng)度值；f'表示當(dāng)前個(gè)體的適應(yīng)度值；fmax表示最大適應(yīng)度值；Pc1、Pc2分別表示交叉概率；Pm1、Pm2分別表示變異概率。

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

對AGASA 算法的時(shí)間復(fù)雜度進(jìn)行分析。由于初始化種群大小為N，任務(wù)請求的數(shù)量為M，迭代次數(shù)為Diters，一條染色體的長度為2×M，那么AGASA算法的時(shí)間復(fù)雜度分析如下：初始化種群的時(shí)間復(fù)雜度為O(M×2×N)≈O(M×N)。由于初始化過程只迭代一次，因此可以忽略不計(jì)；適應(yīng)度值計(jì)算的時(shí)間復(fù)雜度可以表示為O(M×N)；選擇過程的時(shí)間復(fù)雜度為O(M×M)；交叉過程的時(shí)間復(fù)雜度為O(M/2)=O(M)；變異過程的時(shí)間復(fù)雜度為O(M)；模擬退火過程的時(shí)間復(fù)雜度為O(M)。綜上可知，最終整個(gè)AGASA 算法的時(shí)間復(fù)雜度為O(Diters×M×(M+N))。

3.4 超密集邊緣計(jì)算網(wǎng)絡(luò)卸載過程

20 個(gè)移動設(shè)備隨機(jī)分布在兩層的超密集邊緣計(jì)算網(wǎng)絡(luò)中，在該網(wǎng)絡(luò)有1 個(gè)MBS 和3 個(gè)SBS，每個(gè)小區(qū)覆蓋范圍內(nèi)的移動用戶任務(wù)卸載過程如圖2 所示，具體步驟如下：

圖2 超密集邊緣計(jì)算網(wǎng)絡(luò)卸載策略Fig.2 Offloading strategy of ultra-dense edge computing network

1）初始化移動設(shè)備產(chǎn)生的任務(wù)請求，包括任務(wù)卸載的位置和信道位置。假設(shè)有5 個(gè)移動設(shè)備分別產(chǎn)生5 個(gè)任務(wù)請求，該請求的卸載位置如圖3 所示，其中，00 表示卸載位置為本地設(shè)備端，不通過傳輸信道傳輸，12 表示卸載位置為SBS1，傳輸信道為信道2，以此類推。

圖3 初始化卸載位置Fig.3 Initial uninstall location

2）由算法1 得到最優(yōu)任務(wù)上傳功率，并計(jì)算初始卸載策略下的總能耗。

3）由算法2 更新卸載方案和任務(wù)卸載方案，并計(jì)算和比較更新前后的總能耗，得到最能耗最低的卸載方案，更新后的結(jié)果如圖4 所示，任務(wù)請求2 的卸載方案由12 更新為11，任務(wù)請求3 的卸載方案由11 更新為21，任務(wù)請求4 的卸載方案由21 更新為00，任務(wù)請求5 的卸載方案由00 更新為22。

圖4 更新后的卸載位置Fig.4 Uninstall location after update

4 實(shí)驗(yàn)設(shè)置與結(jié)果分析

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

使用Python3.7 實(shí)現(xiàn)算法，并在一臺配備8 GBRAM 的Intel I7-2.6 GHz 的PC 上進(jìn)行實(shí)驗(yàn)，系統(tǒng)參數(shù)設(shè)置如表1 所示。考慮有多個(gè)SBS 的超密集邊緣計(jì)算網(wǎng)絡(luò)的場景，其中SBS 的數(shù)量設(shè)置為30 個(gè)，每個(gè)SBS 對應(yīng)1 個(gè)MEC 服務(wù)器，則UDN 由30 個(gè)SBS和1 個(gè)MBS 組成，每個(gè)小區(qū)的信道頻譜被分成多個(gè)子頻段，并隨機(jī)分布在UDN 內(nèi)的任意位置。將噪聲功率譜密度設(shè)置為-100 dB，子信道的帶寬設(shè)置為[0.1 MHz，0.5 MHz]，本地計(jì)算資源f0=0.1 MHz，服務(wù)器的計(jì)算資源為fm=[0.15 MHz，1 MHz]。移動設(shè)備與SBS 之間的無線連接采用的則是瑞利衰落信道，路徑損耗為38.46+20lg l dB。假設(shè)距離以m 為單位，那么設(shè)備到SBS 的距離為[0 m，100 m]。將最大上傳功率設(shè)置為2 W，在實(shí)驗(yàn)次數(shù)為20 次的情況下，取平均值作為最終結(jié)果。

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

4.2 對比方案

為評估AGASA 算法的性能，本文將該算法與遺傳算法（Genetic Algorithm，GA）［24］和混合遺傳粒子群（GAPSO）算法［25］進(jìn)行對比，并結(jié)合本文的應(yīng)用場景進(jìn)行相應(yīng)的調(diào)整。同時(shí)，參照文獻(xiàn)［26］設(shè)置了相應(yīng)的算法參數(shù)，并結(jié)合超密集邊緣計(jì)算的實(shí)際場景進(jìn)行了一定的改進(jìn)，如表2 所示。

表2 算法參數(shù)設(shè)置Table 2 Algorithm parameter setting

4.3 實(shí)驗(yàn)分析

在實(shí)驗(yàn)分析部分，主要進(jìn)行以下工作，以評估超密集邊緣計(jì)算網(wǎng)絡(luò)相比與傳統(tǒng)網(wǎng)絡(luò)的對卸載結(jié)果的影響：1）對比3 種算法下的能耗和適應(yīng)度值；2）對比不同信道參數(shù)下的算法能耗，同時(shí)對比小區(qū)不同子信道分配情況下的任務(wù)卸載能耗；3）對比不同小區(qū)密集程度下的卸載能耗。

4.3.1 移動設(shè)備數(shù)對算法性能的影響

在超密集邊緣計(jì)算網(wǎng)絡(luò)中，主要目標(biāo)是在截止期限內(nèi)最小化任務(wù)卸載的總能耗，因此，可將適應(yīng)度值和能耗作為對算法的度量標(biāo)準(zhǔn)。將移動設(shè)備數(shù)設(shè)為30、60、90、120、150、180，每個(gè)小區(qū)的子信道數(shù)設(shè)置為2，任務(wù)的數(shù)據(jù)量大小設(shè)置為[0 Mb/s，1.6 Mb/s]，并將迭代次數(shù)設(shè)置為1 000 次。將本文提出的AGASA 算法與GA 算法、GAPSO 算法進(jìn)行對比。圖5和圖6 分別給出了3 種算法下能耗和適應(yīng)度值隨移動設(shè)備數(shù)的變化情況。

圖5 不同算法下的能耗對比Fig.5 Comparison of energy consumption under different algorithms

圖6 不同算法下的適應(yīng)度對比Fig.6 Comparison of fitness value under different algorithms

由圖5 可以看出：當(dāng)移動設(shè)備產(chǎn)生的任務(wù)數(shù)據(jù)量一致時(shí)，隨著移動設(shè)備不斷增加，所需要的計(jì)算資源不斷增加，因此任務(wù)卸載的能耗不斷增加；當(dāng)移動設(shè)備數(shù)相同時(shí)，AGASA 算法的任務(wù)卸載能耗最低，這是因?yàn)樵撍惴ǖ乃阉髂芰Ω鼜?qiáng)，能夠更快找到最優(yōu)的卸載方案，因此性能最好；由于本文的任務(wù)請求為離散型，隨著負(fù)載壓力增加，GAPSO 算法由于更適合連續(xù)型的任務(wù)請求，因此不容易找到卸載最優(yōu)解。

由圖6 可以看出：當(dāng)相同移動設(shè)備數(shù)時(shí)，AGASA算法下的適應(yīng)度值最低。

4.3.2 子信道數(shù)對卸載能耗的影響

為探究不同信道情況對卸載能耗的影響，對比任務(wù)數(shù)為90、120、150、180 時(shí)，每個(gè)小區(qū)子信道數(shù)分別為1、2、3 情況下的能耗。如圖7 所示，任務(wù)數(shù)的增加意味著移動設(shè)備數(shù)增加，一方面，所需要的頻譜資源和計(jì)算資源不斷增加，另一方面，同時(shí)通過同一個(gè)信道傳輸競爭有限頻譜資源的移動設(shè)備數(shù)增加，信道壓力增大帶來更多的傳輸干擾，因此卸載能耗不斷增加。當(dāng)小區(qū)的子信道數(shù)為3 時(shí)，卸載能耗最低，當(dāng)任務(wù)數(shù)為180 時(shí)，若僅通過一個(gè)信道傳輸，此時(shí)卸載能耗為0.535 5；當(dāng)子信道數(shù)為2 時(shí)，卸載能耗為0.47；當(dāng)子信道數(shù)為3 時(shí)，此時(shí)卸載能耗為0.459 4，隨著子信道的數(shù)量越多，信道壓力越小，任務(wù)傳輸時(shí)的干擾越小，因此卸載能耗越低。同時(shí)，當(dāng)每個(gè)小區(qū)只有一個(gè)信道時(shí)，任務(wù)卸載能耗最高，這是因?yàn)楫?dāng)多個(gè)任務(wù)在一個(gè)信道上傳輸時(shí)，信道過于擁擠，傳輸干擾很大，所以傳輸過程中會消耗更多的能量。同時(shí)由圖7 可以觀察到，AGASA 算法下的能耗最低，說明該算法能夠在超密集邊緣計(jì)算網(wǎng)絡(luò)中任務(wù)請求數(shù)較多的情況下，根據(jù)信道狀態(tài)更新任務(wù)卸載方案，找到最優(yōu)的分配策略。

圖7 不同子信道數(shù)下的能耗對比Fig.7 Comparison of energy consumption under different number of sub-channels

4.3.3 迭代次數(shù)對算法性能的影響

為驗(yàn)證AGASA 算法的收斂性，比較AGASA、GAPSO 以及GA 算法在不同迭代次數(shù)下的能耗。令此時(shí)移動設(shè)備的數(shù)量為90，種群的數(shù)量為100 個(gè)，迭代次數(shù)為1 000，實(shí)驗(yàn)結(jié)果如圖8 所示，可以看出：隨著迭代次數(shù)的不斷增加，GAPSO 算法收斂速度最慢，且容易過早收斂，這是因?yàn)樵撍惴ǖ木植克阉髂芰Σ睿欢鳤GASA 算法的收斂性最好，在迭代次數(shù)的影響下，當(dāng)?shù)螖?shù)為1 000 時(shí)，該算法任務(wù)卸載的總能耗低于其他對比算法，這是因?yàn)樵撍惴ńY(jié)合了SA 和GA 的優(yōu)點(diǎn)，全局搜索能力和局部搜索能力都很強(qiáng)，在面對大量任務(wù)請求的同時(shí)，能夠根據(jù)當(dāng)前信道狀態(tài)變化和計(jì)算資源，不斷更新卸載決策，更快找到最優(yōu)解。

圖8 不同算法下的收斂性對比Fig.8 Comparison of convergence under different algorithms

4.3.4 信道狀態(tài)對算法性能的影響

為對比不同信道狀態(tài)下各個(gè)算法的性能，將移動設(shè)備數(shù)M設(shè)置為120，服務(wù)器數(shù)N設(shè)置為30，每個(gè)小區(qū)的子信道數(shù)C設(shè)置2。如表3 所示，從GAPSO 的結(jié)果中可以看出：當(dāng)PBG和PGB較小時(shí)，信道處于較穩(wěn)定的狀態(tài)，此時(shí)任務(wù)卸載的能耗較低；隨著PBG和PGB的不斷增大，信道處于不穩(wěn)定的狀態(tài)，將卸載決策更改為本地處理的計(jì)算任務(wù)增多，因此任務(wù)卸載能耗增加。另一方面，相比于GAPSO 和GA 算法，AGASA 受信道狀態(tài)變化的影響最小，且能夠根據(jù)實(shí)際的環(huán)境隨時(shí)不斷調(diào)整參數(shù)，對環(huán)境的自適應(yīng)性和搜索能力更強(qiáng)，因此任務(wù)卸載能耗最低。

表3 不同算法下信道參數(shù)對能耗的影響Table 3 The influence of channel parameters on energy consumption under different algorithms 單位：J

4.3.5 SBS 部署密度對卸載能耗的影響

為分析SBS 部署密度對卸載結(jié)果的影響，對比不同SBS 數(shù)量下的卸載能耗。將任務(wù)數(shù)分別設(shè)置為90、120、150、180，對比SBS 數(shù)量為1、10、20、30、40、60 情況下的卸載能耗。實(shí)驗(yàn)結(jié)果如圖9 所示，可以看出：隨著SBS 數(shù)量從1 到30 不斷增加，小區(qū)部署密度增加，卸載能耗變低，這是因?yàn)橐环矫娌渴鹪赟BS側(cè)的服務(wù)器數(shù)量越來越多，可供給移動設(shè)備的計(jì)算資源更加豐富；另一方面部署點(diǎn)越來越密集，小區(qū)可覆蓋的移動設(shè)備數(shù)量增多，移動設(shè)備與小區(qū)的距離更近，且可供給移動設(shè)備的頻譜資源更加豐富。因此，傳輸能耗和計(jì)算能耗更低。尤其是隨著任務(wù)數(shù)增多，當(dāng)SBS 的數(shù)量為1 時(shí)，所產(chǎn)生的卸載能耗最高，而當(dāng)SBS 為30 時(shí)，卸載能耗明顯降低。同時(shí)由圖9 可以看出：相比于傳統(tǒng)網(wǎng)絡(luò)架構(gòu)下的邊緣計(jì)算，UDN 對任務(wù)卸載能耗的降低具有明顯的優(yōu)越性，然而隨著SBS 數(shù)量從40 增加到60，卸載能耗反而增加，這是由于一方面SBS 過于密集的情況下，交叉覆蓋區(qū)域的移動設(shè)備頻繁切換基站會產(chǎn)生更大的網(wǎng)絡(luò)壓力，另一方面SBS 之間距離更近的情況下，傳輸干擾也會隨之增加，因此任務(wù)卸載能耗增大。

圖9 不同SBS 部署密度下的能耗對比Fig.9 Comparison of energy consumption under different SBS deployment densities

4.3.6 超密集邊緣計(jì)算網(wǎng)絡(luò)下不同算法的性能

為驗(yàn)證本文所提算法在超密集邊緣計(jì)算網(wǎng)絡(luò)中的優(yōu)越性，對比不同小區(qū)部署密度下，AGASA 算法與GA 和GAPSO 算法的卸載能耗。在移動設(shè)備數(shù)為120 的情況下，將SBS 的數(shù)量設(shè)置為1、5、10、20、30、40，其中，SBS 數(shù)量為1 表示所有的移動設(shè)備將任務(wù)卸載到同一個(gè)SBS 對應(yīng)的MEC 上。實(shí)驗(yàn)結(jié)果如圖10 所示，可以看出：隨著SBS 數(shù)量的不斷增加，宏基站覆蓋范圍內(nèi)的小基站部署更加密集，可提供的計(jì)算資源越來越豐富，卸載能耗越來越低；而相比與GA、GAPSO 算法，AGASA 算法下的能耗最低，這是因?yàn)樵诔芗吘売?jì)算網(wǎng)絡(luò)中，該算法結(jié)合了GA 和SA 算法的優(yōu)勢，具有更強(qiáng)的搜索能力，在密集部署的環(huán)境中能夠更好地找到最優(yōu)的卸載策略。

圖10 超密集邊緣計(jì)算網(wǎng)絡(luò)中不同算法的能耗對比Fig.10 Comparison of energy consumption of different algorithms in ultra-dense edge computing network

5 結(jié)束語

針對超密集邊緣計(jì)算網(wǎng)絡(luò)中任務(wù)卸載的能耗優(yōu)化問題，本文考慮信道狀態(tài)的變化、傳輸干擾等因素，結(jié)合AGA 和SA 算法提出AGASA 算法，并基于此進(jìn)行任務(wù)卸載，在滿足截止期約束下對任務(wù)卸載能耗進(jìn)行優(yōu)化，同時(shí)通過功率控制的黃金分割算法得到更優(yōu)的上傳功率。實(shí)驗(yàn)結(jié)果表明，本文方法可獲得任務(wù)卸載能耗最低的信道分配決策和任務(wù)卸載決策，并且小區(qū)部署越密集，可提供的頻譜資源和計(jì)算資源越豐富，任務(wù)卸載能耗越低。相比于傳統(tǒng)網(wǎng)絡(luò)架構(gòu)，超密集邊緣計(jì)算網(wǎng)絡(luò)在傳輸和計(jì)算方面都具有明顯的優(yōu)勢。后續(xù)將在超密集邊緣計(jì)算網(wǎng)絡(luò)中引入非正交多址傳輸?shù)姆绞?，提高傳輸效率，降低傳輸干擾，并且將計(jì)算開銷作為優(yōu)化目標(biāo)，考慮時(shí)延敏感型和能耗敏感性任務(wù)的區(qū)別，對任務(wù)卸載、信道分配和功率控制方案做進(jìn)一步優(yōu)化。