NOMA-MEC系統(tǒng)中基于改進(jìn)遺傳算法的協(xié)作式計(jì)算卸載與資源管理

周天清 胡海琴 曾新亮

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

1 引言

隨著機(jī)器學(xué)習(xí)和人工智能等科學(xué)技術(shù)的興起，人臉識(shí)別、智能家居、自動(dòng)駕駛和醫(yī)療保健等應(yīng)用應(yīng)運(yùn)而生。這些新型應(yīng)用在實(shí)時(shí)處理時(shí)占用了大量的計(jì)算和存儲(chǔ)資源，對(duì)存儲(chǔ)空間、計(jì)算資源和電池容量受限的智能設(shè)備提出了巨大的挑戰(zhàn)[1-3]。為應(yīng)對(duì)該挑戰(zhàn)，移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)允許資源受限的智能設(shè)備將計(jì)算密集型任務(wù)卸載至邊緣網(wǎng)絡(luò)，讓具備計(jì)算和存儲(chǔ)能力的邊緣節(jié)點(diǎn)處理任務(wù)。

超密集異構(gòu)網(wǎng)絡(luò)(Ultra-Dense Heterogeneous Network, UDHN)與MEC的結(jié)合進(jìn)一步縮短了用戶與計(jì)算中心的距離，且UDHN通過在宏小區(qū)內(nèi)部署大量小基站(Small Base Station, SBS)，極大地提升了服務(wù)覆蓋率和資源利用率，降低了智能設(shè)備至基站的傳輸時(shí)延。但是，密集部署的小基站會(huì)導(dǎo)致大量的能耗[4,5]。此外，在UDHN中，每個(gè)基站覆蓋下的用戶密度較大，區(qū)內(nèi)與區(qū)間均存在嚴(yán)重干擾[6]。

合適的干擾消除和頻帶資源分配方案有利于降低MEC系統(tǒng)時(shí)延和能耗，從而有效提升系統(tǒng)性能。在單MEC服務(wù)器和多用戶場景下，文獻(xiàn)[7]提出了基于正交頻分多址接入的MEC系統(tǒng)。具體而言，它將系統(tǒng)頻帶劃分為多個(gè)正交子信道以消除用戶間的干擾，并最大化了系統(tǒng)計(jì)算效率。在多小區(qū)和多用戶的MEC場景中，文獻(xiàn)[8]最小化時(shí)延和能耗的加權(quán)。其中，小區(qū)內(nèi)的用戶通過正交信道進(jìn)行信號(hào)傳輸，但小區(qū)間的用戶可能相互干擾。在多宏小區(qū)、多小小區(qū)和多用戶的UDHN場景下，文獻(xiàn)[9]研究了系統(tǒng)總能耗最小優(yōu)化問題。它為消除UDHN中層間和層內(nèi)干擾，提出了一種頻譜資源分配方案。但是，隨著用戶規(guī)模的增大，頻譜資源分配會(huì)變得越來越緊張。

為進(jìn)一步提升頻譜利用率、實(shí)現(xiàn)高速率傳輸及廣覆蓋，已有多數(shù)研究將非正交多址接入(Non-Orthogonal Multiple Access, NOMA)和MEC結(jié)合起來。文獻(xiàn)[10]研究了時(shí)分多址接入(Time Division Multiple Access, TDMA)和NOMA下的部分卸載與二元卸載問題，并嘗試最大化系統(tǒng)計(jì)算效率。文獻(xiàn)[11]考慮了NOMA-MEC在車聯(lián)網(wǎng)領(lǐng)域內(nèi)的應(yīng)用。為最大限度保證用戶效益，它利用基于深度學(xué)習(xí)網(wǎng)絡(luò)的博弈算法來為用戶選擇最優(yōu)的卸載策略。文獻(xiàn)[12]構(gòu)建了UDHN下的NOMA-MEC系統(tǒng)，并研究了多SBS、多用戶的資源分配問題以最小化用戶能耗和任務(wù)時(shí)延。

上述研究都有對(duì)干擾進(jìn)行消除和對(duì)頻帶資源進(jìn)行分配，或者引入NOMA技術(shù)進(jìn)一步提升頻帶利用率。然而，其中大部分研究考慮每個(gè)用戶僅有一個(gè)任務(wù)需要處理的情況，單個(gè)宏小區(qū)場景與非協(xié)作場景；很少研究考慮UDHN場景下多用戶多任務(wù)協(xié)作式計(jì)算卸載問題。不同于上述研究，本文構(gòu)建了UDHN場景下NOMA-MEC系統(tǒng)，其中每個(gè)用戶均存在多個(gè)計(jì)算任務(wù)，且宏基站(Macro Base Station,MBS)與小基站間存在協(xié)作式卸載。針對(duì)該系統(tǒng)，在MEC計(jì)算資源和用戶時(shí)延約束下，聯(lián)合優(yōu)化計(jì)算資源分配、用戶任務(wù)卸載和用戶發(fā)射功率以最小化系統(tǒng)總能耗。本文具體工作如下：

(1)在UDHN中融入頻帶劃分機(jī)制與NOMA技術(shù)。為解決UDHN中存在的層內(nèi)與層間干擾，引入了頻譜劃分機(jī)制。在此基礎(chǔ)上，為進(jìn)一步提升上行頻譜效益，又引入NOMA技術(shù)。

(2)在NOMA-MEC系統(tǒng)中，考慮多蜂窩與多用戶。同時(shí)，假定每個(gè)用戶有多個(gè)不可拆分的計(jì)算任務(wù)，且小基站可與宏基站協(xié)作完成任務(wù)。其次，根據(jù)計(jì)算任務(wù)所需計(jì)算資源占比，分配用戶計(jì)算資源。這種計(jì)算資源分配方式既能很好地滿足用戶計(jì)算需求，又能簡化優(yōu)化問題，便于算法實(shí)際應(yīng)用。

(3)鑒于所建模問題具備非線性整數(shù)形式，利用多樣性引導(dǎo)變異的自適應(yīng)遺傳算法(Adaptive Genetic Algorithm with Diversity-Guided Mutation, AGADGM)設(shè)計(jì)出了協(xié)作式計(jì)算卸載與資源分配算法。不同于一些組合算法[9,13]，本文僅考慮單純遺傳算法(Genetic Algorithm, GA)，僅涉及單層循環(huán)。顯然，此種考慮可以削減算法的運(yùn)行時(shí)間，且更適合超密集網(wǎng)絡(luò)場景。最后，在仿真中，引入全本地算法、最強(qiáng)信道增益關(guān)聯(lián)算法和傳統(tǒng)遺傳算法進(jìn)行對(duì)比，調(diào)查了用戶發(fā)射功率、用戶密度與頻譜劃分因子對(duì)系統(tǒng)性能的影響。

2 系統(tǒng)模型

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

本文考慮了如圖1(a)所示的UDHN場景下的NOMA-MEC系統(tǒng)。圖中每個(gè)正6邊形代表一個(gè)宏小區(qū)，每個(gè)宏小區(qū)內(nèi)部署了1個(gè)MBS、多個(gè)SBS與多個(gè)用戶終端。具體而言，在超密集異構(gòu)MEC系統(tǒng)中，部署了Nˉ 個(gè)MBS,N? 個(gè)SBS和K個(gè)用戶終端，其中SBS的索引集記為N? ={1,2,...,N?}，MBS的索引集記為N? ={N? +1,N? +2,...,N? +M}，則所有基站的索引集為N=N?∪Nˉ；用戶終端集合表示為K={1,2,...,K}。此外，假定每個(gè)宏小區(qū)內(nèi)所有SBS構(gòu)成一個(gè)SBS簇，且所有基站均配置了MEC服務(wù)器；假定每個(gè)用戶終端有多個(gè)計(jì)算任務(wù)，其任務(wù)可以在本地執(zhí)行，也可卸載至基站MEC服務(wù)器執(zhí)行；假定用戶與基站之間的通信采用無線鏈路，MBS與SBS之間的通信采用有線回程鏈路(速率為r0)。

2.2 資源模型

為消除UDHN中層內(nèi)干擾與層間干擾，根據(jù)文獻(xiàn)[9,14]，本文亦對(duì)頻譜進(jìn)行分割，如圖1(b)所示。在UDHN中，為消除MBS與SBS間的層間干擾，將頻帶F(帶寬為W)劃分為子帶F1和 子帶F2，其中子帶F1(帶寬為μW)分配給MBS，子帶F2(帶寬為(1-μ)W)分配給SBS，0≤μ≤1為頻譜劃分因子；為消除相鄰MBS間的干擾和SBS簇間的干擾，子帶F1被分割為帶寬為μW/3 的3個(gè)子頻帶F11,F12與F13， 且F2被 分割為帶寬為( 1-μ)W/3的3個(gè)子頻帶F21,F22與F23。為消除簇內(nèi)SBS間的干擾，子頻帶F21,F22與F23被再次均分為多個(gè)更小的子頻帶，它們的帶寬為 (1-μ)W/3θ，其中θ為一個(gè)SBS簇內(nèi)SBS的數(shù)目。

圖1 系統(tǒng)模型

區(qū)別于文獻(xiàn)[9]中MBS和SBS將頻帶資源均分給其所關(guān)聯(lián)的所有用戶，本文在上行鏈路中引入NOMA技術(shù)以解碼傳輸信號(hào)，并借此提升頻譜利用效率。如圖1(b)所示，在NOMA技術(shù)下，將任意MBS和SBS的頻帶資源劃分為多個(gè)NOMA子信道，允許多個(gè)用戶同時(shí)使用某個(gè)基站的同一子信道。假定每個(gè)子信道帶寬為w，則任意MBS的子信道個(gè)數(shù)為Sˉ =μW/3w， 其子信道索引集記為Sˉ ={1,2,...,Sˉ}。 同理，任意SBS的子信道個(gè)數(shù)為S? =(1-μ)W/3wU，其子信道索引集記為S? ={1,2,...,S?}。

2.3 通信模型

在上述資源模型中，本文考慮了上行NOMA技術(shù)。該技術(shù)按信道增益遞減順序進(jìn)行信號(hào)解碼，這與下行NOMA的解碼順序相反[15]。假設(shè)有多個(gè)用戶接入基站n的子信道s，Kns為 關(guān)聯(lián)至基站n的子信道s的用戶集合。類似于文獻(xiàn)[16]，對(duì)于任意基站的子信道，將用戶至該子信道的信道增益按升序排列，onsk表示用戶k在基站n的子信道s上的排序序號(hào)。當(dāng)用戶j和 用戶k同時(shí)接入基站n的 子信道s，且用戶j的信道增益hnsj低于用戶k的信道增益hnsk時(shí)，onsj

根據(jù)上行NOMA的特性[15,16]，用戶關(guān)聯(lián)基站子信道時(shí)，其上傳速率分為以下兩種情況：

(1)當(dāng)用戶終端k選擇關(guān)聯(lián)MBSn的 子信道s時(shí)，用戶k的上傳速率rnsk為

2.4 計(jì)算模型

2.5 問題描述

鑒于UDHN中部署了大量SBS，消耗了大量能耗，本文嘗試最優(yōu)化任務(wù)完成總能耗，它涉及用戶端與基站端的能耗。具體而言，在計(jì)算資源和時(shí)延約束下，聯(lián)合優(yōu)化基站子信道選擇X={xnsk,?n ∈N,?s ∈Sn,?k ∈K}、 任務(wù)卸載決策y={yk,?k ∈K}和z={zk,?k ∈K}及 用戶發(fā)射功率p={pk,?k ∈K}以最小化系統(tǒng)總能耗E。其中，Sn為 基站n的子信道索引集。優(yōu)化問題可規(guī)劃為

3 基于改進(jìn)遺傳算法的協(xié)作式計(jì)算卸載與資源分配算法

不難發(fā)現(xiàn)，問題P1為0-1非線性混合整數(shù)規(guī)劃問題。為解決該問題，可以采用文獻(xiàn)[9]中的聯(lián)合自適應(yīng)遺傳算法和自適應(yīng)粒子群算法的雙層搜索算法。但是，考慮到其中粒子群算法是對(duì)遺傳算法所獲解局部的刷新，對(duì)問題解的優(yōu)化不存在較大的影響，本文僅嘗試?yán)闷涞?層搜索算法(多樣性引導(dǎo)變異的自適應(yīng)遺傳算法)求解問題P1。最后，根據(jù)該改進(jìn)遺傳算法，本文設(shè)計(jì)出了有效的協(xié)作式計(jì)算卸載與資源分配算法。

多樣性引導(dǎo)變異的自適應(yīng)遺傳算法(AGADGM)是對(duì)傳統(tǒng)遺傳算法(Traditional GA, TGA)的改進(jìn)。在TGA算法中，1個(gè)種群包含多個(gè)個(gè)體。這些個(gè)體是帶有染色體特征的實(shí)體，它們是優(yōu)化問題的潛在解。待種群初始化后，根據(jù)適者生存和優(yōu)勝劣汰的原則，TGA用適應(yīng)度函數(shù)評(píng)價(jià)種群個(gè)體適應(yīng)度并篩選出最佳個(gè)體。具體而言，在一些特定規(guī)則下，TGA執(zhí)行選擇、交叉、變異等操作，經(jīng)過逐代演化，最終找到問題的近似最優(yōu)解。相比于T G A，AGADGM在自適應(yīng)交叉和變異運(yùn)算之前進(jìn)行了多樣性引導(dǎo)變異，克服了早熟收斂問題[9]。該算法重要內(nèi)容及相關(guān)操作如下。

3.1 染色體

類似于文獻(xiàn)[13]，本文考慮實(shí)數(shù)編碼。對(duì)于問題P1的任意一種解的優(yōu)化參量{X,y,z,p}可以編碼成 某 個(gè) 個(gè) 體i ∈I的 染 色 體{Li,Qi,Ui,Vi}，I={1,2,...,I}記 為個(gè)體索引集合，I為種群的規(guī)模，Li={lik,k ∈K},Qi={qik,k ∈K},Ui={uik,k ∈K}與Vi={vik,k ∈K}為個(gè)體i的染色體片段。為實(shí)現(xiàn)對(duì)參量X的編碼，假定每個(gè)基站的子信道構(gòu)成一個(gè)虛擬基站，并對(duì)其標(biāo)記唯一索引。因?yàn)槿我庥脩魞H能關(guān)聯(lián)至某個(gè)基站的某一個(gè)子信道，因此用戶關(guān)聯(lián)結(jié)果可用虛擬基站索引表示。于是，在任意個(gè)體i中 ，lik取 值為用戶k所關(guān)聯(lián)虛擬基站的索引。此外，qik和uik分 別為用戶k卸載至基站的任務(wù)數(shù)和自SBS上傳至MBS的任務(wù)數(shù)，且vik為 用戶k的發(fā)射功率。值得注意的是，qik不能超過用戶k的任務(wù)數(shù)，uik不 能超過qik并滿足qik的限制條件，且用戶k的發(fā)射功率需滿足0≤vik ≤pmkax。

3.2 種群初始化

遺傳算法從初始化種群開始，需要生成滿足條件的系列個(gè)體。為滿足問題P1的約束C2-C6，按照以下規(guī)則初始化種群，即

3.3 適應(yīng)度函數(shù)

3.4 選擇

為從當(dāng)前種群中選擇優(yōu)良個(gè)體，本文采用錦標(biāo)賽方式進(jìn)行選擇。在此方式中，高適應(yīng)度值的個(gè)體被選擇的概率較大。此外，在迭代更新過程中，每一代都保留歷史最佳個(gè)體。當(dāng)歷史最佳個(gè)體沒有選入下一代時(shí)，用歷史最佳個(gè)體替換當(dāng)前種群中的最差個(gè)體，從而提高遺傳算法性能。

3.5 交叉

3.6 變異

3.7 多樣性評(píng)價(jià)

為克服早熟收斂問題，在自適應(yīng)交叉和變異之前進(jìn)行多樣性評(píng)價(jià)，讓其引導(dǎo)變異。對(duì)多維數(shù)值問題，其多樣性評(píng)價(jià)[9]定義為

步驟2 按照式(7)和式(9)求取計(jì)算資源；根據(jù)式(16)計(jì)算所有個(gè)體的個(gè)體適應(yīng)度值，并找出當(dāng)前最佳個(gè)體；如果當(dāng)前最佳個(gè)體的適應(yīng)度值高于歷史最佳個(gè)體的適應(yīng)度值，則以前者替換后者。

步驟3 重復(fù)如下操作；

步驟4 根據(jù)錦標(biāo)賽選擇法選擇個(gè)體建立新種群；如果歷史最佳個(gè)體沒有進(jìn)入下一代，則以歷史最佳個(gè)體替換種群中的最差個(gè)體；根據(jù)式(25)中的概率，按式(19)-式(22)進(jìn)行多樣性引導(dǎo)變異；按照式(7)和式(9)求取計(jì)算資源，并根據(jù)式(16)計(jì)算所有個(gè)體的適應(yīng)度值。

步驟5 任意兩個(gè)相鄰個(gè)體按照式(17)中的自適應(yīng)交叉概率執(zhí)行交叉操作；根據(jù)式(18)中的自適應(yīng)變異概率，所有個(gè)體按式(19)-式(22)進(jìn)行變異操作。

步驟6 按照式(7)和式(9)求取計(jì)算資源；根據(jù)式(16)計(jì)算所有個(gè)體的適應(yīng)度值，并找到當(dāng)前種群的最佳個(gè)體。如果當(dāng)前最佳個(gè)體的適應(yīng)度值高于歷史最佳個(gè)體的適應(yīng)度值，則以前者替換后者。

步驟7 按照t=t+1更新迭代次數(shù)；如果t ≤T(T為最大迭代次數(shù))，則回到步驟3，反之則輸出歷史最佳個(gè)體的染色體片段，并終止循環(huán)。

4 系統(tǒng)仿真

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

為凸顯本文算法的有效性，仿真中引入其他計(jì)算卸載與資源分配算法，包括最強(qiáng)信道增益關(guān)聯(lián)算法(Maximum Channel Gain Association algorithm, MCGA)[9]、基于傳統(tǒng)遺傳算法的計(jì)算卸載與資源分配算法(Traditional Genetic Algorithm based Scheme, TGAS)[18]及全本地計(jì)算算法(Local Computing Algorithm, LCA)[5]作比較。在MCGA中，任意用戶將計(jì)算任務(wù)全部卸載至最強(qiáng)信道增益的基站子信道；TGAS則固定交叉和變異概率，且沒有引入多樣性保護(hù)變異；LCA讓用戶自己完成所有任務(wù)。

4.2 仿真結(jié)果分析

在保持μ=0.5、用戶最大發(fā)射功率為23 dBm及其他條件不變的情況下，圖3顯示了用戶密度ρ(宏小區(qū)內(nèi)用戶個(gè)數(shù))對(duì)系統(tǒng)效能的影響。根據(jù)式(13)可知，ρ值的增大必定會(huì)導(dǎo)致系統(tǒng)總能耗的增大。如圖3(a)所示，4種算法的系統(tǒng)總能耗均隨ρ的增長而增長。類似于圖2(a)，圖3(a)中MCGA系統(tǒng)總能耗一直低于其他算法，本文算法獲得了較前者更高的系統(tǒng)總能耗。類似于圖2(b)，圖3(b)中TGAS, LCA與本文算法總能支持所有用戶在規(guī)定時(shí)間內(nèi)完成所有計(jì)算任務(wù)。然而，MCGA支持率卻一直低于1，且總體上隨著ρ先增加后下降。在低ρ域，用戶密度的增加導(dǎo)致靠近基站的用戶增加，系統(tǒng)支持率可能隨ρ上升；在高ρ域，用戶密度的增加導(dǎo)致可利用資源的下降，系統(tǒng)支持率可能隨ρ下降。

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

圖2 用戶最大發(fā)射功率p mkax對(duì)系統(tǒng)總能耗和系統(tǒng)支持率的影響

在保持K=35、用戶最大發(fā)射功率為23 dBm及其他條件不變的情況下，圖4顯示了頻譜劃分因子μ對(duì)系統(tǒng)效能的影響。由2.2節(jié)的資源模型可知，μ越大，MBS的頻帶資源越多，SBS的頻帶資源則越少。如圖4(a)所示，總體上，TGAS, MCGA與本文算法的系統(tǒng)總能耗隨著μ的增大而增加。其原因在于，隨著μ的增大，部分選擇SBS的用戶因頻帶資源不足轉(zhuǎn)而選擇MBS。由式(6)可知，距離MBS較遠(yuǎn)的用戶越多，傳輸時(shí)延及能耗越大，系統(tǒng)總能耗也隨之增加。但是，因?yàn)長CA中用戶任務(wù)全部本地執(zhí)行，故其系統(tǒng)總能耗不隨μ變化。此外，類似于圖2(a)、圖4(a)中MCGA系統(tǒng)總能耗一直低于其他算法，本文算法獲得了較前者更高的系統(tǒng)總能耗。眾所周知，MBS中MEC服務(wù)器計(jì)算資源有限。根據(jù)式(7)可知，越多用戶接入MBS，用戶分配到的計(jì)算資源越少，計(jì)算時(shí)延就越長，于是越來越多的用戶不滿足時(shí)延約束。因此，圖4(b)中MCGA的系統(tǒng)支持率隨著μ的增大而減小。類似于圖2(b)和圖3(b)，圖4(b)顯示TGAS, LCA與本文算法總能支持所有用戶在規(guī)定時(shí)間內(nèi)完成所有計(jì)算任務(wù)。

圖4 頻帶劃分因子μ 對(duì)系統(tǒng)總能耗和系統(tǒng)支持率的影響

圖5顯示了遺傳算法中最佳個(gè)體適應(yīng)度值的收斂情況，其中K=35,μ=0.5及用戶最大發(fā)射功率為23 dBm。容易發(fā)現(xiàn)，TGAS具有較本文算法更快的收斂速度，但因前者陷入局部最優(yōu)而導(dǎo)致獲得較后者更差的適應(yīng)度值。究其原因，固定的交叉和變異概率容易使得TGAS陷于局部最優(yōu)，過早收斂。而本文算法引入了多樣性引導(dǎo)變異、自適應(yīng)交叉和變異概率等操作，這些操作使得搜索更加細(xì)致的同時(shí)，避免了過早收斂。

圖5 最優(yōu)個(gè)體的適應(yīng)度值在遺傳算法下的搜索情況

綜合上述，盡管MCGA能達(dá)到較其他算法更低的系統(tǒng)總能耗，但其系統(tǒng)支持率一直較其他算法更低。雖然本文算法的系統(tǒng)總能耗高于MCGA，但它都低于LCA和TGAS。此外，本文算法的系統(tǒng)支持率始終為1，即本文算法總能支持所有用戶在規(guī)定時(shí)間內(nèi)完成所有計(jì)算任務(wù)?？傮w而言，同其他算法相比，本文提出的基于改進(jìn)遺傳算法(AGADGM)的協(xié)作式計(jì)算卸載與資源分配算法具備一定優(yōu)勢，且能在問題約束條件下較好地優(yōu)化系統(tǒng)能耗。

5 結(jié)束語

本文構(gòu)建了UDHN場景下的NOMA-MEC系統(tǒng)，并在該系統(tǒng)中研究了多用戶多任務(wù)協(xié)作式卸載策略。為合理消除干擾和分配頻譜資源，融入了頻帶劃分機(jī)制與上行NOMA技術(shù)。然后，在計(jì)算資源占比分配策略與時(shí)延約束下，聯(lián)合優(yōu)化用戶關(guān)聯(lián)、卸載決策與用戶發(fā)射功率以最小化系統(tǒng)總能耗。為求解所規(guī)劃的問題，在改進(jìn)遺傳算法(AGADGM)的基礎(chǔ)上，提出了協(xié)作式計(jì)算卸載與資源分配算法。仿真結(jié)果表明，同其他算法相比，本文所設(shè)計(jì)算卸載與資源分配算法具備一定優(yōu)勢，且能在問題約束條件下較好地優(yōu)化系統(tǒng)能耗。未來研究可涉及單用戶多信道接入場景與大規(guī)模天線場景等。