基于HAGA 的D2D-NOMA 資源分配優(yōu)化算法

宋勇春，王茜竹，高正念

（1.重慶郵電大學(xué) 電子信息與網(wǎng)絡(luò)工程研究院，重慶 400065；2.新一代信息網(wǎng)絡(luò)與終端協(xié)同創(chuàng)新中心，重慶 400065）

0 概述

根據(jù)思科數(shù)據(jù)顯示，預(yù)計到2022 年，全球每月數(shù)據(jù)流量將達(dá)到77 艾字節(jié)［1］。移動數(shù)據(jù)流量需求呈指數(shù)級增長，將導(dǎo)致當(dāng)前無線網(wǎng)絡(luò)的帶寬資源匱乏以及基站嚴(yán)重過載。為緩解上述問題，D2D（Deviceto-Device）技術(shù)應(yīng)運而生，該技術(shù)允許鄰近設(shè)備在沒有基站的輔助下進(jìn)行數(shù)據(jù)交換［2］，在短距離通信場景中可以大幅提升設(shè)備之間的信道增益，降低通信時延及終端發(fā)射功率并延長終端待機(jī)時間［3］。此外，通過復(fù)用蜂窩用戶的信道進(jìn)行通信，能夠有效提高無線資源的利用率［4］。D2D 技術(shù)的引入使得無線通信網(wǎng)絡(luò)的運行更加靈活高效，但是，基于傳統(tǒng)的正交多址接入（Orthogonal Multiple Access，OMA）方式的D2D 通信，一個資源塊只允許一個D2D 用戶通信，無線資源并未得到充分利用［5］。

在非正交多址接入（Non-Orthogonal MultipleAccess，NOMA）技術(shù)中，接收端利用連續(xù)干擾消除（Serial Interference Cancellation，SIC）技術(shù)對發(fā)送的疊加信號進(jìn)行解調(diào)［6］，實現(xiàn)了多用戶功率域的復(fù)用，從而大幅提高了系統(tǒng)吞吐量和頻譜效率，因此，NOMA 被視為5G最有前景的候選技術(shù)之一［7］。文獻(xiàn)［8］分析表明，將NOMA 技術(shù)應(yīng)用于D2D 通信場景能較好地提高D2D系統(tǒng)的吞吐量，但其所帶來的鏈路干擾問題不可忽略，且引入功率域復(fù)用后，同一個子載波被多個用戶共用，使得該場景下的資源分配變得更加復(fù)雜，為解決該問題，需要合理優(yōu)化信道與功率分配。

目前，對基于NOMA 的D2D 通信場景資源分配問題的研究已經(jīng)取得較多成果。文獻(xiàn)［9］在保證蜂窩用戶服務(wù)質(zhì)量（QoS）的條件下，提出一種逐步迭代算法，從而求解資源分配問題的次優(yōu)解并實現(xiàn)D2D 用戶對的速率最大化。文獻(xiàn)［10］基于隨機(jī)固定功率分配系數(shù)，研究一種求解子信道匹配問題的低復(fù)雜度算法，采用SCA（Successive Convex Approximation）迭代獲得次優(yōu)功率分配方案，從而最大化系統(tǒng)總速率。文獻(xiàn)［11］研究一種聯(lián)合子信道分配、用戶配對、功率控制的資源分配方案，以最小化傳輸功率。文獻(xiàn)［12］在多個蜂窩用戶以NOMA 方式通信時，保證其SIC 解調(diào)順序時的蜂窩用戶功率，通過對偶迭代給D2D 用戶分配合適資源，實現(xiàn)D2D 用戶對的總速率最大化。文獻(xiàn)［13］研究一種聯(lián)合信道分配與功率分配的資源分配方案，基于一對一的雙邊匹配解決資源匹配問題，并利用拉格朗日乘子法求解最優(yōu)功率分配系數(shù)。文獻(xiàn)［14］以能效最大化和時延最小化為目標(biāo)，提出一種基于多對一匹配進(jìn)行子載波分配的方案，使用拉格朗日函數(shù)求得功率分配方案。文獻(xiàn)［15］構(gòu)建一種基于納什均衡的模型，考慮NOMA 用戶不同程度的干擾，從而最大化每個參與者的自身利益。但是，傳統(tǒng)優(yōu)化算法在解決此類NP 問題時計算復(fù)雜，而啟發(fā)式算法魯棒性高、容易實現(xiàn)、復(fù)雜度低，因此，其在最優(yōu)化算法領(lǐng)域被廣泛應(yīng)用，且越來越多的學(xué)者將其用于資源分配任務(wù)。文獻(xiàn)［16］以最大化D2D 通信性能為目標(biāo)，提出一種基于DDM（Decoupled Direct Method）的優(yōu)化框架，并利用DE（Differential Evolution）啟發(fā)式算法進(jìn)行求解。文獻(xiàn)［17］提出一種基于GA（Genetic Algorithm）的資源分配方法，以最大化D2D 系統(tǒng)的總吞吐量。

啟發(fā)式算法在很大程度上依賴于控制參數(shù)的選取，且存在搜索早熟、搜索慢等問題，使其難以跳出局部最優(yōu)解，算法收斂時間長。針對傳統(tǒng)遺傳算法的不足，本文結(jié)合懲罰函數(shù)法與爬山算法對其進(jìn)行改進(jìn)，并提出一種基于HAGA（Hill-climbing Adaptive Genetic Algorithm）的優(yōu)化算法，以最大化D2D-NOMA系統(tǒng)的吞吐量。具體地，本文建立一種基于NOMA的D2D 通信資源分配模型。在滿足不同用戶QoS、D2D 用戶發(fā)射功率及信道分配約束下，最大化D2D系統(tǒng)吞吐量。針對資源分配問題，提出一種基于HAGA 的優(yōu)化算法。利用懲罰函數(shù)法將原約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，并采用自適應(yīng)懲罰系數(shù)優(yōu)化解空間。在此基礎(chǔ)上，對信道匹配標(biāo)識和功率分配因子進(jìn)行染色體編碼、自適應(yīng)交叉、自適應(yīng)變異，以生成候選種群，然后利用爬山算法對候選種群進(jìn)行二次搜索，避免優(yōu)勢個體丟失并加快收斂速度，從而得到全局最優(yōu)解。

1 系統(tǒng)模型與問題描述

本文考慮單小區(qū)上行鏈路傳輸場景，假設(shè)基站可以獲得所有用戶的信道信息，且每一個蜂窩用戶占用一個子信道，各子信道間相互正交互不干擾。在D2D 組內(nèi)采用非正交多址接入方式進(jìn)行下行通信，D2D 組內(nèi)發(fā)射用戶向接收用戶發(fā)送疊加信號，系統(tǒng)模型如圖1 所示。單小區(qū)包含一個基站、N個蜂窩用戶和M組D2D 用戶，每個D2D 組有一個發(fā)射用戶和K個接收用戶，接收用戶隨機(jī)分布在以發(fā)射用戶為圓心、d為半徑的圓中。本文假設(shè)每個D2D 組內(nèi)的接收用戶數(shù)相等，且每個D2D 組僅允許復(fù)用一個蜂窩用戶信道，而同一個信道可以被多個D2D 組復(fù)用。因此，在同一個信道上，D2D 接收用戶會受到蜂窩用戶、同一組內(nèi)其他接收用戶以及復(fù)用同一信道的不同D2D 組發(fā)射用戶的干擾。

圖1 系統(tǒng)模型Fig.1 System model

在本文系統(tǒng)中，假設(shè)集合C={c1，c2，…，cn，…，cN}表示蜂窩用戶集合，其中cn表示蜂窩用戶n，集合D={D1，D2，…，Dm，…，DM}表示M個D2D組的所有接收用 戶，其中Dm={dm1，dm2，…，dmk，…，dmK}為 組m內(nèi)K個接收用戶。同時，假設(shè)蜂窩用戶的發(fā)射功率均為PC，每個D2D 組內(nèi)發(fā)射用戶的發(fā)射總功率均為PD。蜂窩用戶n與基站之間的信道增益表示為hcn，B，發(fā)射用戶m與基站之間的信道增益表示為hm，B，cn與dmk之間的信道增益表示為hcn，mk，組m內(nèi)發(fā)射用戶與接收用戶k之間的信道增益表示為hm，mk。不失一般性，假設(shè)|hm，m1|2≤|hm，m2|2≤…≤|hm，mk|2≤…≤|hm，mK|2，用表示信道匹配標(biāo)識，為1 時表示D2D 組m復(fù)用蜂窩用戶n的信道，為0 時表示不復(fù)用，用σ2表示用戶接收到的高斯白噪聲功率。

由模型分析可知，子信道n上基站接收到蜂窩用戶的接收信噪比為：

假設(shè)D2D 組m復(fù)用cn信道進(jìn)行數(shù)據(jù)傳輸，則用戶dmk在子信道n上的接收信噪比為：

其中：αmk為組內(nèi)接收用戶k的功率分配系數(shù)。根據(jù)香農(nóng)公式可知，第m個D2D 組在子信道n上的容量為：

因此，D2D 系統(tǒng)的總吞吐量為：

2 算法設(shè)計

2.1 優(yōu)化問題構(gòu)建

本文通過優(yōu)化D2D 組信道匹配和組內(nèi)用戶在NOMA 方式下的功率分配，以最大化D2D 通信系統(tǒng)的吞吐量，目標(biāo)優(yōu)化問題建模為P1：

2.2 基于HAGA 的資源分配策略

考慮到目標(biāo)函數(shù)的NP 難解性，使用傳統(tǒng)方法不易處理，而遺傳算法可以很好地解決此類NP 問題，該類算法具有良好的全局搜索能力，但是，遺傳算法未有效利用反饋信息，導(dǎo)致搜索速度較慢，在解決大規(guī)模計算問題時容易陷入“早熟”，且其解依賴于參數(shù)的選擇。基于此，本文利用自適應(yīng)懲罰函數(shù)法改進(jìn)傳統(tǒng)遺傳算法的適應(yīng)度函數(shù)，同時采用基于爬山策略的自適應(yīng)遺傳算法提升全局搜索性能并加快收斂速度。本文算法由染色體編碼、適應(yīng)度計算、種群選擇、交叉重組、染色體變異、爬山再搜索這6 個部分組成，算法流程如圖2 所示。

圖2 本文算法流程Fig.2 The procedure of algorithm in this paper

2.3 基于HAGA 的信道匹配求解

假設(shè)每個D2D 組中功率分配系數(shù)為固定值，用αmk*表示，則原目標(biāo)函數(shù)轉(zhuǎn)化為P2：

本文算法具體步驟如下：

1）染色體編碼。為了縮短染色體長度，加快算法收斂，并盡可能減少適應(yīng)度計算過程中的約束條件，本文采取實值編碼方式。D2D 組信道匹配染色體編碼如下：

其中：vm(1≤vm≤N，1≤m≤M)的值對應(yīng)其復(fù)用的子信道序號，如V=[2，1，…，2]中值一樣的表示復(fù)用同一個信道。

2）適應(yīng)度計算。本文優(yōu)化模型是帶約束的最大化吞吐量模型，因此，需要將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，而懲罰函數(shù)法是遺傳算法中處理約束條件最常用的一種方法，本文引用外點懲罰法對目標(biāo)函數(shù)進(jìn)行處理，如下：

為了提高算法的魯棒性及搜索能力，本文參考文獻(xiàn)［18］對傳統(tǒng)懲罰函數(shù)進(jìn)行改進(jìn)?？紤]到在優(yōu)化早期種群中可行解數(shù)量較少，此時懲罰系數(shù)應(yīng)較高，隨著種群的進(jìn)化，種群中產(chǎn)生的可行解增多，懲罰系數(shù)則應(yīng)減小，當(dāng)種群中全部是可行解時，懲罰系數(shù)應(yīng)減小到0。因此，本文將懲罰系數(shù)表示為：

其中：α為當(dāng)前個體不滿足約束條件的個數(shù)；ρ為可行解比例，取值為(0，1]之間的實數(shù)，當(dāng)ρ趨近于0 時表示當(dāng)前種群幾乎沒有可行解，當(dāng)ρ=1 時表示當(dāng)前種群全為可行解。則當(dāng)前個體的懲罰項表示為：

3）種群選擇。本文使用輪盤賭選擇方式，通過計算個體被選擇的概率（即該個體的適應(yīng)度f與當(dāng)前種群的適應(yīng)度之和），對每一代種群個體進(jìn)行概率性的有放回選取，便于后續(xù)優(yōu)化。因此，具體的選擇概率Psel可以表示為：

4）交叉重組。本文針對取值為二進(jìn)制整數(shù)的信道匹配標(biāo)識，采取單點交叉法，通過隨機(jī)產(chǎn)生的交叉位點選取2 個父代個體染色體的基因進(jìn)行交換組合，以產(chǎn)生新的個體。自適應(yīng)交叉概率Pcro為：

5）染色體變異。本文針對取值為整數(shù)的信道匹配標(biāo)識，采取整數(shù)值突變算法，通過對子代個體隨機(jī)產(chǎn)生的變異位點，變異染色體上的某些基因從而生成新個體。具體的自適應(yīng)變異概率Pmut為：

其中：favg為當(dāng)前種群平均適應(yīng)度；fmax為當(dāng)前種群最大適應(yīng)度；f′為2 個交叉父代個體中較大的適應(yīng)度；f為變異個體的適應(yīng)度；k1、k2、k3、k4為[0，1]區(qū)間的常數(shù)。當(dāng)種群內(nèi)個體適應(yīng)度較高時，為了使好基因盡可能保留到下一代，應(yīng)使交叉概率和變異概率減??；當(dāng)種群內(nèi)個體適應(yīng)度較低時，應(yīng)使基因盡可能淘汰，因此交叉概率和變異概率應(yīng)增加。通常在進(jìn)化初期，種群的多樣性較高，可適當(dāng)增大其交叉概率，減小變異概率；在進(jìn)化后期，種群多樣性降低，應(yīng)適當(dāng)減小其交叉概率，增大變異概率［19］。

6）新種群的再次進(jìn)化。為了進(jìn)一步加快算法的收斂速度并提升搜索性能，本文使用爬山算法避免遍歷搜索以快速找到局部最優(yōu)解。采用爬山算法對新種群的個體進(jìn)行二次搜索［20］，選取選擇、交叉過后的候選種群中適應(yīng)度較高的優(yōu)良個體，作為爬山算法的搜索空間，在完成變異操作后利用爬山算法對新個體進(jìn)行再次搜索，若搜索空間的個體適應(yīng)度函數(shù)值優(yōu)于變異個體，則用其更新當(dāng)前變異后的候選種群，否則將其舍棄。將經(jīng)過爬山算法的種群作為新種群，進(jìn)入適應(yīng)度計算步驟。

2.4 功率分配問題求解

由于已經(jīng)確認(rèn)信道匹配方案，且正交發(fā)射用戶的總功率固定，因此各子信道上的D2D 組功率分配系數(shù)可單獨求解，原目標(biāo)函數(shù)轉(zhuǎn)換為P4：

與信道匹配模型相同，本文在功率分配問題求解時同樣使用HAGA 算法，染色體編碼同樣采取實值編碼；與信道匹配模型不同，該部分實值為連續(xù)值，處理如下：

1）染色體編碼：

其中：功率分配系數(shù)αmk∈(0，1)。

2）適應(yīng)度計算同樣基于懲罰函數(shù)得到：

3）種群選擇使用輪盤賭選擇方式，選擇概率為Psel。

4）交叉重組使用兩點交叉法，且限制2 個交叉點的選擇個數(shù)為K的倍數(shù)，以保證基因的片段性，交叉概率同樣采用自適應(yīng)交叉概率Pcro。

5）染色體變異：由于功率分配因子是（0，1）之間的連續(xù)變量，因此本文采用高斯變異法進(jìn)行基因變異，變異概率同樣采用自適應(yīng)變異概率Pmut。

6）新種群的再次進(jìn)化采取與信道匹配相同的基于爬山策略的二次搜索算法。

3 仿真與性能分析

3.1 仿真參數(shù)

對本文所提算法的信道匹配與功率分配性能進(jìn)行仿真，并分析不同的D2D組數(shù)和D2D組發(fā)射功率對D2D系統(tǒng)總吞吐量、D2D 系統(tǒng)總能效的影響。仿真場景假設(shè)某小區(qū)基站覆蓋范圍為500 m，小區(qū)內(nèi)隨機(jī)均勻分布若干蜂窩用戶及若干D2D 組，每個D2D 組內(nèi)以D2D 發(fā)射用戶為圓心、以50 m為半徑，隨機(jī)均勻分布2個或2個以上的D2D 接收用戶。本文信道模型為基于路徑損耗的信道模型，具體仿真參數(shù)如表1 所示，仿真取最優(yōu)值作為該組參數(shù)對應(yīng)的仿真結(jié)果。

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameters setting

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

針對信道匹配部分，該算法的計算復(fù)雜度取決于適應(yīng)度計算，設(shè)O(f)為適應(yīng)度計算的復(fù)雜度，每次迭代時種群進(jìn)化具有隨機(jī)性，將進(jìn)化與爬山復(fù)雜度設(shè)為O(l)，此外該算法的復(fù)雜度還取決于進(jìn)化次數(shù)T與種群大小Q，則算法的復(fù)雜度為O(T(O(f)+O(l))+Q)；針對功率分配部分，算法復(fù)雜度同理，但由于功率分配部分染色體長度是信道匹配的2 倍，因此其運行時間更長。

3.3 結(jié)果分析

本文首先對算法的收斂性能進(jìn)行測試，需要注意的是，遺傳算法受到很多因素影響，如初始種群的多樣性、交叉機(jī)制、變異機(jī)制等，此外算法的收斂速度取決于種群的大小以及染色體的長度，如果種群較大或染色體較長，則收斂較慢。

在固定功率分配方案時，以信道匹配和最大化D2D 系統(tǒng)吞吐量為優(yōu)化目標(biāo)，將GA、AGA、HAGA（本文算法）這3 種算法運用于本文場景時的搜索及收斂性能比較如圖3 所示。

圖3 固定功率分配方案下的D2D 系統(tǒng)吞吐量對比Fig.3 Comparison of D2D system throughput under fixed power allocation scheme

基于圖3 所得的信道匹配方案，以D2D 組內(nèi)功率分配因子作為優(yōu)化變量、最大化D2D 系統(tǒng)吞吐量為優(yōu)化目標(biāo)，將GA、AGA、HAGA 這3 種算法應(yīng)用于功率分配任務(wù)時的搜索及收斂性能比較如圖4所示。

圖4 固定信道匹配方案下的D2D 系統(tǒng)吞吐量對比Fig.4 Comparison of D2D system throughput under fixed channel matching scheme

從圖3 可以看出，HAGA 大約在60 次收斂，從圖4 可以看 出，HAGA 大約在160 次收斂。HAGA 的收斂、搜索性能優(yōu)于AGA 和GA，這是因為相較于GA，HAGA 與AGA 在交叉與變異概率自適應(yīng)處理后更容易跳出局部最優(yōu)值，找到全局最優(yōu)值，同時，HAGA 算法收斂性能優(yōu)于AGA 與GA，這是因為在每次選擇、交叉、變異后的種群中引入爬山算法，會進(jìn)一步搜尋更優(yōu)的種群作為下一次迭代的初始種群，使得優(yōu)勝劣汰的速度加快。因此，HAGA 算法在全局搜索和收斂性能上都有一定提升。

圖5所示為蜂窩用戶數(shù)量一定時不同D2D 組數(shù)下D2D 系統(tǒng)吞吐量的對比結(jié)果。從圖5 可以看出，隨著D2D 組數(shù)的增加，D2D 系統(tǒng)吞吐量增大，且HAGA 算法性能最優(yōu)。此外，將本文算法用于NOMA 技術(shù)所獲得的D2D 系統(tǒng)吞吐量大于傳統(tǒng)OMA 技術(shù)，這是因為傳統(tǒng)OMA 技術(shù)只允許一個子信道復(fù)用一個用戶，而NOMA 技術(shù)允許多個用戶同時復(fù)用在相同的時頻資源上，因此，隨著D2D 用戶組數(shù)的增加，系統(tǒng)吞吐量增大。

圖5 不同D2D 組數(shù)下的D2D 系統(tǒng)吞吐量對比Fig.5 Comparison of D2D system throughput under different D2D groups

圖6 所示為蜂窩用戶與D2D 組數(shù)固定、D2D 組發(fā)射用戶發(fā)射功率不同時的D2D 系統(tǒng)吞吐量對比，從圖6 可以看出，HAGA 性能更優(yōu)，且隨著D2D 用戶發(fā)射功率的提高，D2D 系統(tǒng)性能呈上升趨勢，相較于OMA 技術(shù)，基于NOMA 技術(shù)的D2D 系統(tǒng)性能更優(yōu)。

圖6 不同D2D 用戶發(fā)射功率下的D2D 系統(tǒng)吞吐量對比Fig.6 Comparison of D2D system throughput under different D2D user transmission power

4 結(jié)束語

本文提出一種基于HAGA 的無線資源分配算法，以在蜂窩用戶與D2D 用戶不同的QoS 約束條件下，優(yōu)化D2D 組信道匹配和功率分配因子，最大化D2D 系統(tǒng)總吞吐量?？紤]到優(yōu)化目標(biāo)函數(shù)包含二進(jìn)制整數(shù)變量信道匹配因子及連續(xù)變量功率分配因子，求解難度較高，本文利用HAGA 算法進(jìn)行全局搜索以尋找最優(yōu)信道匹配方案，然后基于所得信道匹配方案對D2D 組內(nèi)用戶功率分配因子進(jìn)行優(yōu)化。仿真結(jié)果表明，該算法的收斂與搜索性能優(yōu)于GA、AGA 算法，其能夠有效提升D2D 通信系統(tǒng)的吞吐量。但是，在實際的D2D-NOMA 系統(tǒng)中，由于存在時延等問題，導(dǎo)致難以獲取完美信道狀態(tài)信息，下一步將基于不完美信道狀態(tài)信息對D2D-NOMA 場景展開研究。