基于NOMA的5G超密網(wǎng)計算遷移與資源分配策略

時永鵬，張俊杰，夏玉杰1，，高雅1，，張尚偉

（1.河南省電子商務(wù)大數(shù)據(jù)處理與分析重點實驗室（洛陽師范學(xué)院），河南洛陽 471934；2.洛陽師范學(xué)院物理與電子信息學(xué)院，河南洛陽 471934；3.西北工業(yè)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，西安 710072）

0 引言

5G 網(wǎng)絡(luò)的快速發(fā)展為人們提供了諸如虛擬現(xiàn)實、自動駕駛等眾多具有廣泛前景的應(yīng)用和服務(wù)，這些應(yīng)用和服務(wù)除了需要高效可靠的通信資源外，也需要大量的計算資源［1］。然而由于移動設(shè)備的電池容量和計算能力有限，僅僅依靠設(shè)備本身的資源很難完成對這些計算密集型應(yīng)用的處理。云計算雖然可以顯著降低用戶的計算延遲和能耗，但由于終端用戶與云服務(wù)器之間的傳輸距離較長，無法滿足時延敏感型應(yīng)用的需求［2］。為了解決這個問題，移動邊緣計算（Mobile Edge Computing，MEC）［3］被提出并得到了廣泛研究，通過計算遷移，部署在網(wǎng)絡(luò)邊緣的計算資源可以為移動設(shè)備提供高效和靈活的計算服務(wù)。

作為5G 系統(tǒng)中的一種新的網(wǎng)絡(luò)架構(gòu)，超密網(wǎng)（Ultra dense Network，UDN）［4］通過在網(wǎng)絡(luò)區(qū)域內(nèi)大量部署短距離、低功率的小基站，可以為用戶提供吞吐率高、靈活性強的無線數(shù)據(jù)傳輸服務(wù)。同時，非正交多址接入（Non-Orthogonal Multiple Access，NOMA）也被視為5G 的關(guān)鍵候選技術(shù)之一，以解決4G 網(wǎng)絡(luò)中正交多址接入（Orthogonal Multiple Access，OMA）頻譜效率低的問題。NOMA 在發(fā)射端使用疊加編碼技術(shù)，在接收端則用串行干擾消除技術(shù)實現(xiàn)正交解調(diào)，從而在同一個子信道上允許多個用戶疊加［5］。在5G 系統(tǒng)中，UDN、NOMA 技術(shù)與MEC 的有機結(jié)合，做到優(yōu)勢互補，不但能為移動用戶提供穩(wěn)定、可靠的數(shù)據(jù)通信，提高頻譜效率，還能通過計算遷移，減少數(shù)據(jù)傳輸和處理時延，降低終端能耗。

目前針對基于NOMA的邊緣網(wǎng)絡(luò)中的計算遷移研究已經(jīng)取得了一些重要研究成果，這些研究工作主要在時延約束下最小化設(shè)備的計算能耗或時延與能耗的加權(quán)代價。文獻［6］提出了一種啟發(fā)式算法，通過優(yōu)化用戶分組、傳輸功率和計算資源，以最小化5G 網(wǎng)絡(luò)中設(shè)備的能量消耗。文獻［7］以減少用戶的任務(wù)卸載時延為目標(biāo)，綜合考慮計算遷移決策和資源分配，提出了一種基于匹配理論的聯(lián)合優(yōu)化算法。但上述兩項工作均考慮的是單基站場景。而在5G 超密網(wǎng)中，文獻［8］在獲取設(shè)備NOMA 分組的基礎(chǔ)上，采用深度確定性策略梯度算法在提高傳輸功率的同時最小化設(shè)備的計算代價，然而該工作沒有考慮子信道的帶寬分配。文獻［9］在采用NOMA 的異構(gòu)邊緣計算網(wǎng)絡(luò)中，設(shè)計了一種基于序列凸規(guī)劃的算法聯(lián)合優(yōu)化功率分配、通信資源和計算資源，從而獲得最低計算能耗。在基于NOMA 的超密集異構(gòu)網(wǎng)中，文獻［10］通過構(gòu)建效用函數(shù)，提出了一種量子粒子群優(yōu)化算法在對子載波和傳輸功率進行優(yōu)化分配的同時最大化計算遷移的能量效率，和文獻［9］類似，雖然考慮了無線資源優(yōu)化，但缺少有效的用戶分組。文獻［11］則將超密網(wǎng)中的計算遷移定義為一個混合整數(shù)非線性規(guī)劃，并提出了一個基于遺傳算法的基站分組和存儲資源分配策略，從而最小化所有計算任務(wù)的處理時延。

顯然，現(xiàn)有基于NOMA 的超密網(wǎng)中的計算遷移研究工作都提出了有效的解決方案，但它們均存在一些問題，要么沒有考慮到網(wǎng)絡(luò)中子信道的帶寬分配，要么忽略了設(shè)備的分組匹配。因此，本文提出了一種基于NOMA 的5G超密網(wǎng)計算遷移與資源分配策略，以優(yōu)化設(shè)備計算代價為目標(biāo)，綜合考慮遷移策略、帶寬優(yōu)化與分組匹配。具體工作如下：

1）在基于NOMA 接入的5G 超密網(wǎng)中，以計算時延和能耗的不同權(quán)重構(gòu)造計算代價函數(shù)，并以此為最小化目標(biāo)將計算遷移定義為一個約束最優(yōu)化問題；

2）設(shè)計聯(lián)合優(yōu)化策略，通過交替使用模擬退火技術(shù)、內(nèi)點法和貪心算法，對計算遷移、帶寬分配和分組匹配進行迭代求解，最終獲得最低計算代價。

仿真實驗結(jié)果表明所設(shè)計的聯(lián)合優(yōu)化策略能有效降低設(shè)備的計算代價，且具有良好的收斂性。

1 基于NOMA的5G超密網(wǎng)計算遷移

1.1 系統(tǒng)模型

考慮如圖1 所示的5G 超密網(wǎng)架構(gòu)，N個移動設(shè)備（N={1，2，…，N}）采用隨機形式分布在由M個小基站（M={1，2，…，M}）所覆蓋的網(wǎng)絡(luò)區(qū)域。小基站上均部署有邊緣服務(wù)器，可為接入設(shè)備提供計算服務(wù)。所有小基站均采用NOMA 技術(shù)，共享總帶寬為W的頻率資源。若設(shè)備與基站通信過程中保持位置不變，則被基站m服務(wù)的設(shè)備集合可表示為，其中|Cm|表示Cm中設(shè)備的個數(shù)。系統(tǒng)中共有K個無線子信道（K={1，2，…，K}），將Cm中利用子信道k與基站m通信的設(shè)備作為一個NOMA 分組，其中∈{0，1}表示設(shè)備n是否屬于Cm，k，如果是，則=1；否則。顯然有：

圖1 5G超密網(wǎng)中的計算遷移架構(gòu)Fig.1 Computation offloading architecture in 5G ultra-dense network

式中|Cm，k|表示Cm，k中設(shè)備的數(shù)目。

1.2 通信模型

1.3 計算模型

1.3.1 本地計算

1.3.2 遷移到小基站上的邊緣服務(wù)器計算

1.4 問題定義

根據(jù)以上描述，本文要解決的主要問題可描述為：在基于NOMA 的5G 超密網(wǎng)中，給定系統(tǒng)的頻譜資源、移動設(shè)備的計算能力、邊緣服務(wù)器的計算能力等網(wǎng)絡(luò)參數(shù)，設(shè)計最佳計算遷移、帶寬分配與分組匹配策略，在滿足計算任務(wù)最大時延的前提下，最小化設(shè)備的計算代價。為便于數(shù)學(xué)描述，設(shè)μ=為設(shè)備的計算遷移策略組合，ω={ωk}為帶寬分配方案，λ=表示設(shè)備分組匹配策略，則該問題的形式化定義為：

在問題P1 中，約束條件C1 保證每個計算任務(wù)的處理時延不得超過其最大允許時延；C2 列出了計算任務(wù)的所有計算模式但每個任務(wù)只能選擇其中一種；C3 是系統(tǒng)總帶寬的約束條件；C4、C5則是移動設(shè)備與NOMA 分組的關(guān)系。容易證明，P1是一個NP-難問題［12］。

2 問題求解和算法設(shè)計

從式（10）中的約束C2 和C5 可以看出，P1 是一個混合整數(shù)非凸優(yōu)化問題。為求解該問題，本文將P1分解成三個子問題：1）在給定設(shè)備分組匹配和帶寬分配策略的前提下求解計算遷移策略μ；2）在給定計算遷移和設(shè)備分組匹配策略的情況下求解帶寬分配策略ω；3）在計算遷移和帶寬分配策略已知的條件下獲取設(shè)備分組匹配策略λ。最后通過迭代的方法對這三個子問題進行聯(lián)合優(yōu)化，獲得最小計算代價及最優(yōu)計算遷移、帶寬分配和分組匹配策略。

2.1 計算遷移策略優(yōu)化

在給定設(shè)備的NOMA 匹配策略λ和帶寬分配策略ω的前提下，P1 中的計算遷移策略優(yōu)化是一個整數(shù)編程問題，可通過求解P1.1獲得：

該問題可通過枚舉的方法列舉出N個設(shè)備的所有可能計算遷移策略組合，并從中選取計算代價最小的組合作為最優(yōu)策略，但其計算復(fù)雜度高達O(2N)，在規(guī)模較大的網(wǎng)絡(luò)中不適用。因此，本文設(shè)計了一個基于模擬退火技術(shù)的低復(fù)雜度計算遷移優(yōu)化算法，在每次迭代中僅隨機改變一個設(shè)備的計算遷移策略：

其中，μs-1為第s-1次迭代的計算遷策略。用F(μs)表示在遷移策略為μs時對應(yīng)的P1.1中的目標(biāo)函數(shù)值，當(dāng)且僅當(dāng)式（14）為負時設(shè)備n的策略改變才能生效，否則以概率接受μs為當(dāng)前最優(yōu)策略。

其中T為當(dāng)前溫度變量。本文算法的詳細步驟如算法1所述。

算法1 基于模擬退火技術(shù)的計算遷移優(yōu)化算法。

2.2 帶寬分配策略設(shè)計

當(dāng)計算遷移和分組匹配策略已知時，帶寬分配策略可通過求解以下問題獲得：

式（20）、（21）對ωk的二次導(dǎo)數(shù)均大于0，因此P1.2 的目標(biāo)函數(shù)和約束C1均為ωk的非線性凸函數(shù)，可利用Matlab中的非線性優(yōu)化函數(shù)fmincon 或在YALMIP 優(yōu)化工具中利用內(nèi)點法求解［13］。

2.3 設(shè)備分組匹配算法設(shè)計

給定計算遷移和帶寬分配策略，設(shè)備分組匹配問題可定義為：

與P1.1類似，P1.3也是一個整數(shù)編程問題?？紤]到分組匹配的目的是為了讓設(shè)備在對應(yīng)子信道上獲得最大的數(shù)據(jù)傳輸速率，從而最小化計算時延和能量消耗。而在傳輸功率和子信道帶寬一定的前提下，傳輸速率受信道增益的影響最大。由于同一NOMA 分組中設(shè)備間的信道增益差異越大，對信道容量的提升越大［14］，本文設(shè)計了一個基于貪心算法的分組匹配策略，即先將被同一基站服務(wù)的設(shè)備按信道增益降序排列，然后依次將每個設(shè)備匹配到能使其傳輸速率最大的NOMA分組中。詳細的分組匹配過程如算法2所示。

算法2 基于貪心方法的設(shè)備分組匹配算法。

2.4 聯(lián)合優(yōu)化算法設(shè)計

通過求解子問題P1.1、P1.2 和P1.3，問題P1 的最優(yōu)解可通過基于坐標(biāo)下降法［15］的迭代算法對這三個問題交替求解獲得。坐標(biāo)下降法在連續(xù)迭代中通過依次求解一個變量而固定剩余變量的方法最小化目標(biāo)函數(shù)。問題P1 含有三個變量(μ，λ，ω)，則在算法的每次迭代過程中，首先固定(λ，ω)求解μ，然后再給定(μ，λ)得到ω，最后由更新后的(μ，ω)獲取λ。由于是最小化問題，因此在迭代中新的解應(yīng)使目標(biāo)函數(shù)值的變化沿下降方向，即：

當(dāng)目標(biāo)函數(shù)值不再變化或者變化值在允許誤差范圍之內(nèi)，即|ΔF|<ξ，或者達到迭代次數(shù)時，即可得到P1 的最優(yōu)解。具體的求解過程如算法3所示。

算法3 聯(lián)合優(yōu)化算法。

2.5 算法復(fù)雜度分析

所提出的計算遷移和資源分配問題通過算法3 中的聯(lián)合優(yōu)化策略求解，而算法3 的主要迭代過程則是對三個子問題進行交替求解。算法1 中的while 循環(huán)的每一次迭代主要用來生成新的計算遷移策略并計算ΔF，而計算ΔF的復(fù)雜度為O(N2)，如果算法1中while循環(huán)的最大迭代次數(shù)為tmax，則該算法的計算復(fù)雜度為O(tmaxN2)。帶寬分配優(yōu)化子問題通過內(nèi)點法求解，其復(fù)雜度為O(N2log(ξ-1))［16］，ξ為允許誤差。算法2的計算復(fù)雜度為O(NMK)。因此，所提的聯(lián)合優(yōu)化算法每次迭代的計算復(fù)雜度為三個子過程的復(fù)雜度之和。如果通過Jmax次迭代獲得最優(yōu)解，則整個算法的計算復(fù)雜度為：O(Jmax(tmaxN2+N2log(ξ-1)+NMK))。

3 仿真實驗與結(jié)果分析

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

不失一般性，設(shè)20 個小基站部署在1 km2的區(qū)域內(nèi)，每個小基站的覆蓋半徑為50 m，100 個移動設(shè)備隨機分布在這些小基站的服務(wù)范圍內(nèi)。設(shè)備的傳輸功率100 mW～150 mW，CPU 頻率為0.8 GHz～1 GHz。每個設(shè)備的計算任務(wù)的輸入數(shù)據(jù)大小為500 KB～800 KB，所需要CPU周期為500 Megacycles～1000 Megacycles，最大允許處理時延為0.5 s～2 s。詳細的參數(shù)設(shè)置如表1所示，所有仿真實驗均在Matlab軟件中進行。

表1 詳細的仿真參數(shù)Tab.1 Detailed simulation parameters

3.2 仿真結(jié)果與分析

圖2 是對所設(shè)計的聯(lián)合優(yōu)化算法的收斂性分析。從圖2中可以看出，對于不同的設(shè)備和小基站數(shù)目，該算法均能在25 次迭代后獲取最低的計算代價，表明了所設(shè)計算法具有良好的收斂性。從圖2 中還可以看到，小基站數(shù)目越多，總的計算代價越低，這是因為更多的邊緣服務(wù)器可以減低計算時延，從而減少計算代價。

圖2 本文算法收斂性分析（α=0.5）Fig.2 Convergence analysis of proposed algorithm（α=0.5）

圖3 為不同接入方式和帶寬分配策略下的設(shè)備計算代價的比較。本文的主要目標(biāo)是獲取在基于NOMA 的5G 超密網(wǎng)中的最優(yōu)計算遷移與帶寬分配策略，因此為凸顯NOMA 接入技術(shù)對超密網(wǎng)性能的有效提升以及在計算遷移中進行帶寬分配的優(yōu)越性，同時更好地驗證本文設(shè)計的聯(lián)合優(yōu)化算法的性能，在仿真時選取了正交接入和非正交接入、帶寬分配優(yōu)化和平均分配帶寬不同的方案進行對比。對于平均分配子信道帶寬的情況，分別選擇了文獻［8］中的非正交接入和文獻［17］中的正交接入兩種計算遷移方案。此外還考慮了正交接入時帶寬分配優(yōu)化的場景。從圖3 可以看出，總的計算代價隨著設(shè)備數(shù)目的增加而單調(diào)增大。通過多種方案的對比可知，聯(lián)合優(yōu)化策略綜合考慮了計算遷移、設(shè)備分組和帶寬分配，極大提升了信道容量，降低了設(shè)備的計算代價。

圖3 不同接入技術(shù)和帶寬分配策略下的計算代價對比（M=20，α=0.5）Fig.3 Comparison of computation cost under different access techniques and bandwidth allocation strategies（M=20，α=0.5）

圖4 展示了不同的權(quán)重系數(shù)α對所有設(shè)備計算代價的影響。由圖4 可知，隨著α值的不斷增大，時延在計算代價中的權(quán)重越來越大而能耗的權(quán)重則逐漸降低，總的計算代價則逐步減小。特別是當(dāng)α=1時，計算代價只包括計算任務(wù)的處理時延，設(shè)備總的計算代價最小。因此，在進行計算遷移時，必須根據(jù)計算任務(wù)的類型設(shè)置適當(dāng)?shù)臋?quán)重系數(shù)。

圖4 權(quán)重系數(shù)對計算代價的影響（M=20）Fig.4 Effect of weight coefficient on computation cost（M=20）

圖5給出了不同計算模式下設(shè)備計算代價的比較。

圖5 不同計算模式下的計算代價對比（M=20，α=0.5）Fig.5 Comparison of computation cost under different computing modes（M=20，α=0.5）

從圖5 中可知，當(dāng)設(shè)備數(shù)目較少時，采用邊緣服務(wù)器計算模式的代價遠小于本地計算模式的代價，這主要得益于邊緣服務(wù)器豐富的計算資源。然而隨著設(shè)備數(shù)目的增多，使得同一NOMA 分組和不同分組同一子信道的干擾逐漸增大，從而降低了設(shè)備的數(shù)據(jù)傳輸速率，導(dǎo)致了更長的傳輸時延，增大了計算代價，而采用聯(lián)合優(yōu)化策略則可以獲得最低的計算代價。

4 結(jié)語

針對基于NOMA 技術(shù)的5G 超密網(wǎng)計算遷移和帶寬分配問題，以最小化設(shè)備的計算代價為目標(biāo)，本文提出了一種聯(lián)合優(yōu)化策略。首先，將研究內(nèi)容定義為約束非凸優(yōu)化問題；然后，將其分解成計算遷移、帶寬分配和設(shè)備分組匹配三個子問題分別求解；最后，利用聯(lián)合優(yōu)化算法對三個問題用迭代方法交替優(yōu)化并得出最優(yōu)解。實驗結(jié)果表明，所提出的策略具有良好的收斂性，且能獲得最優(yōu)的計算遷移和帶寬分配方案，以及最低的設(shè)備計算代價。