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

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

（1.河南省電子商務大數據處理與分析重點實驗室（洛陽師范學院），河南洛陽 471934；2.洛陽師范學院物理與電子信息學院，河南洛陽 471934；3.西北工業大學網絡空間安全學院，西安 710072）

0 引言

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

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

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

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

1）在基于NOMA 接入的5G 超密網中，以計算時延和能耗的不同權重構造計算代價函數，并以此為最小化目標將計算遷移定義為一個約束最優化問題；

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

仿真實驗結果表明所設計的聯合優化策略能有效降低設備的計算代價，且具有良好的收斂性。

1 基于NOMA的5G超密網計算遷移

1.1 系統模型

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

圖1 5G超密網中的計算遷移架構Fig.1 Computation offloading architecture in 5G ultra-dense network

式中|Cm，k|表示Cm，k中設備的數目。

1.2 通信模型

1.3 計算模型

1.3.1 本地計算

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

1.4 問題定義

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

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

2 問題求解和算法設計

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

2.1 計算遷移策略優化

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

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

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

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

算法1 基于模擬退火技術的計算遷移優化算法。

2.2 帶寬分配策略設計

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

式（20）、（21）對ωk的二次導數均大于0，因此P1.2 的目標函數和約束C1均為ωk的非線性凸函數，可利用Matlab中的非線性優化函數fmincon 或在YALMIP 優化工具中利用內點法求解［13］。

2.3 設備分組匹配算法設計

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

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

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

2.4 聯合優化算法設計

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

當目標函數值不再變化或者變化值在允許誤差范圍之內，即|ΔF|<ξ，或者達到迭代次數時，即可得到P1 的最優解。具體的求解過程如算法3所示。

算法3 聯合優化算法。

2.5 算法復雜度分析

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

3 仿真實驗與結果分析

3.1 參數設置

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

表1 詳細的仿真參數Tab.1 Detailed simulation parameters

3.2 仿真結果與分析

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

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

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

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

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

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

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

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

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

4 結語

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