時(shí)永鵬，張俊杰，夏玉杰1，，高雅1，，張尚偉

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

0 引言

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

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

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

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

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

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

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

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

1.1 系統(tǒng)模型

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

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

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

1.2 通信模型

1.3 計(jì)算模型

1.3.1 本地計(jì)算

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

1.4 問(wèn)題定義

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

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

2 問(wèn)題求解和算法設(shè)計(jì)

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

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

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

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

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

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

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

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

當(dāng)計(jì)算遷移和分組匹配策略已知時(shí)，帶寬分配策略可通過(guò)求解以下問(wèn)題獲得：

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

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

圖3 不同接入技術(shù)和帶寬分配策略下的計(jì)算代價(jià)對(duì)比（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ù)α對(duì)所有設(shè)備計(jì)算代價(jià)的影響。由圖4 可知，隨著α值的不斷增大，時(shí)延在計(jì)算代價(jià)中的權(quán)重越來(lái)越大而能耗的權(quán)重則逐漸降低，總的計(jì)算代價(jià)則逐步減小。特別是當(dāng)α=1時(shí)，計(jì)算代價(jià)只包括計(jì)算任務(wù)的處理時(shí)延，設(shè)備總的計(jì)算代價(jià)最小。因此，在進(jìn)行計(jì)算遷移時(shí)，必須根據(jù)計(jì)算任務(wù)的類型設(shè)置適當(dāng)?shù)臋?quán)重系數(shù)。

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

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

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

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

4 結(jié)語(yǔ)

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