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

宋勇春，王茜竹，高正念

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

0 概述

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

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

目前，對(duì)基于NOMA 的D2D 通信場(chǎng)景資源分配問題的研究已經(jīng)取得較多成果。文獻(xiàn)［9］在保證蜂窩用戶服務(wù)質(zhì)量（QoS）的條件下，提出一種逐步迭代算法，從而求解資源分配問題的次優(yōu)解并實(shí)現(xiàn)D2D 用戶對(duì)的速率最大化。文獻(xiàn)［10］基于隨機(jī)固定功率分配系數(shù)，研究一種求解子信道匹配問題的低復(fù)雜度算法，采用SCA（Successive Convex Approximation）迭代獲得次優(yōu)功率分配方案，從而最大化系統(tǒng)總速率。文獻(xiàn)［11］研究一種聯(lián)合子信道分配、用戶配對(duì)、功率控制的資源分配方案，以最小化傳輸功率。文獻(xiàn)［12］在多個(gè)蜂窩用戶以NOMA 方式通信時(shí)，保證其SIC 解調(diào)順序時(shí)的蜂窩用戶功率，通過對(duì)偶迭代給D2D 用戶分配合適資源，實(shí)現(xiàn)D2D 用戶對(duì)的總速率最大化。文獻(xiàn)［13］研究一種聯(lián)合信道分配與功率分配的資源分配方案，基于一對(duì)一的雙邊匹配解決資源匹配問題，并利用拉格朗日乘子法求解最優(yōu)功率分配系數(shù)。文獻(xiàn)［14］以能效最大化和時(shí)延最小化為目標(biāo)，提出一種基于多對(duì)一匹配進(jìn)行子載波分配的方案，使用拉格朗日函數(shù)求得功率分配方案。文獻(xiàn)［15］構(gòu)建一種基于納什均衡的模型，考慮NOMA 用戶不同程度的干擾，從而最大化每個(gè)參與者的自身利益。但是，傳統(tǒng)優(yōu)化算法在解決此類NP 問題時(shí)計(jì)算復(fù)雜，而啟發(fā)式算法魯棒性高、容易實(shí)現(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)解，算法收斂時(shí)間長(zhǎng)。針對(duì)傳統(tǒng)遺傳算法的不足，本文結(jié)合懲罰函數(shù)法與爬山算法對(duì)其進(jìn)行改進(jìn)，并提出一種基于HAGA（Hill-climbing Adaptive Genetic Algorithm）的優(yōu)化算法，以最大化D2D-NOMA系統(tǒng)的吞吐量。具體地，本文建立一種基于NOMA的D2D 通信資源分配模型。在滿足不同用戶QoS、D2D 用戶發(fā)射功率及信道分配約束下，最大化D2D系統(tǒng)吞吐量。針對(duì)資源分配問題，提出一種基于HAGA 的優(yōu)化算法。利用懲罰函數(shù)法將原約束優(yōu)化問題轉(zhuǎn)化為無(wú)約束優(yōu)化問題，并采用自適應(yīng)懲罰系數(shù)優(yōu)化解空間。在此基礎(chǔ)上，對(duì)信道匹配標(biāo)識(shí)和功率分配因子進(jìn)行染色體編碼、自適應(yīng)交叉、自適應(yīng)變異，以生成候選種群，然后利用爬山算法對(duì)候選種群進(jìn)行二次搜索，避免優(yōu)勢(shì)個(gè)體丟失并加快收斂速度，從而得到全局最優(yōu)解。

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

本文考慮單小區(qū)上行鏈路傳輸場(chǎng)景，假設(shè)基站可以獲得所有用戶的信道信息，且每一個(gè)蜂窩用戶占用一個(gè)子信道，各子信道間相互正交互不干擾。在D2D 組內(nèi)采用非正交多址接入方式進(jìn)行下行通信，D2D 組內(nèi)發(fā)射用戶向接收用戶發(fā)送疊加信號(hào)，系統(tǒng)模型如圖1 所示。單小區(qū)包含一個(gè)基站、N個(gè)蜂窩用戶和M組D2D 用戶，每個(gè)D2D 組有一個(gè)發(fā)射用戶和K個(gè)接收用戶，接收用戶隨機(jī)分布在以發(fā)射用戶為圓心、d為半徑的圓中。本文假設(shè)每個(gè)D2D 組內(nèi)的接收用戶數(shù)相等，且每個(gè)D2D 組僅允許復(fù)用一個(gè)蜂窩用戶信道，而同一個(gè)信道可以被多個(gè)D2D 組復(fù)用。因此，在同一個(gè)信道上，D2D 接收用戶會(huì)受到蜂窩用戶、同一組內(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個(gè)D2D組的所有接收用 戶，其中Dm={dm1，dm2，…，dmk，…，dmK}為 組m內(nèi)K個(gè)接收用戶。同時(shí)，假設(shè)蜂窩用戶的發(fā)射功率均為PC，每個(gè)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)識(shí)，為1 時(shí)表示D2D 組m復(fù)用蜂窩用戶n的信道，為0 時(shí)表示不復(fù)用，用σ2表示用戶接收到的高斯白噪聲功率。

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

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

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

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

2 算法設(shè)計(jì)

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ī)模計(jì)算問題時(shí)容易陷入“早熟”，且其解依賴于參數(shù)的選擇?；诖?，本文利用自適應(yīng)懲罰函數(shù)法改進(jìn)傳統(tǒng)遺傳算法的適應(yīng)度函數(shù)，同時(shí)采用基于爬山策略的自適應(yīng)遺傳算法提升全局搜索性能并加快收斂速度。本文算法由染色體編碼、適應(yīng)度計(jì)算、種群選擇、交叉重組、染色體變異、爬山再搜索這6 個(gè)部分組成，算法流程如圖2 所示。

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

2.3 基于HAGA 的信道匹配求解

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

本文算法具體步驟如下：

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

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

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

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

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

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

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

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

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

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

2.4 功率分配問題求解

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

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

1）染色體編碼：

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

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

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

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

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

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

3 仿真與性能分析

3.1 仿真參數(shù)

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

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

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

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

3.3 結(jié)果分析

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

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

圖3 固定功率分配方案下的D2D 系統(tǒng)吞吐量對(duì)比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ù)時(shí)的搜索及收斂性能比較如圖4所示。

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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