基于遺傳退火的密集D2D網(wǎng)絡(luò)資源分配算法

汪漢新，李鵬威

(中南民族大學(xué) 電子信息工程學(xué)院，智能無(wú)線通信湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430074)

近年來(lái)，隨著物聯(lián)網(wǎng)和人工智能技術(shù)的發(fā)展，無(wú)線終端的數(shù)量越來(lái)越多.為了應(yīng)對(duì)5G網(wǎng)絡(luò)的增強(qiáng)移動(dòng)寬帶，大規(guī)模機(jī)器連接和高可靠低時(shí)延通信的挑戰(zhàn)[1,2]，D2D(Device-to-Device)通信技術(shù)被廣泛應(yīng)用在5G場(chǎng)景中.然而，D2D用戶復(fù)用蜂窩網(wǎng)絡(luò)的頻譜資源會(huì)帶來(lái)嚴(yán)重的設(shè)備間干擾[3]，當(dāng)D2D用戶不斷增多時(shí)，設(shè)備間干擾也隨之增多，從而導(dǎo)致D2D用戶接入率的降低.因此，如何有效的進(jìn)行資源分配來(lái)提高D2D用戶接入率成為一個(gè)急需解決的問(wèn)題[4].

目前，人們主要通過(guò)模式選擇、資源分配和功率控制等方法來(lái)減小設(shè)備間干擾以提高系統(tǒng)總吞吐量[5].文獻(xiàn)[6]提出了使用貪婪算法提高系統(tǒng)的吞吐量，但該算法只允許一個(gè)D2D用戶復(fù)用一個(gè)蜂窩信道.文獻(xiàn)[7]提出了一種基于非合作博弈的D2D資源分配算法，D2D用戶相互競(jìng)爭(zhēng)以滿足自己的服務(wù)質(zhì)量(Quality of Service，QoS).文獻(xiàn)[8]首先通過(guò)采用基于參數(shù)法的Dinkelbach算法來(lái)進(jìn)行用戶的功率分配，然后借助Kuhn-Munkres算法為D2D用戶分配蜂窩頻譜資源，提高了系統(tǒng)的能效.文獻(xiàn)[9]提出了使用匈牙利算法進(jìn)行資源分配來(lái)最大化系統(tǒng)吞吐量，但該算法只允許一個(gè)D2D用戶復(fù)用一個(gè)信道.文獻(xiàn)[10]使用最大權(quán)重二分匹配算法，在滿足蜂窩用戶信干噪比的前提下，提升系統(tǒng)公平性，并且允許一個(gè)D2D對(duì)使用多個(gè)信道.文獻(xiàn)[11]提出了基于圖著色算法的資源分配方案，該算法將資源分配問(wèn)題轉(zhuǎn)化為圖著色問(wèn)題，提高了系統(tǒng)吞吐量.文獻(xiàn)[12]提出基于改進(jìn)圖著色算法(Improved Graph Color Algorithm，IGCA)的資源分配方案，該算法通過(guò)考慮以前被忽略的D2D對(duì)受到的微小干擾來(lái)構(gòu)建干擾圖，以進(jìn)一步提高系統(tǒng)的吞吐量.文獻(xiàn)[13]提出了超密集場(chǎng)景下基于圖著色算法的資源分配方案，該方案首先判斷用戶使用D2D模式還是蜂窩模式，然后構(gòu)建干擾圖，最后通過(guò)圖著色算法優(yōu)先為D2D用戶分配信道來(lái)進(jìn)行資源分配，可以提高系統(tǒng)吞吐量.

以上文獻(xiàn)針對(duì)的主要是非密集D2D網(wǎng)絡(luò)中的資源分配問(wèn)題，主要優(yōu)化目標(biāo)為提高吞吐量或提高能效，忽略了對(duì)D2D接入率的要求.為了在保證蜂窩用戶QoS的情況下提升D2D用戶的接入率，本文提出了基于遺傳退火(Genetic Annealing Algorithm，GAA)的密集D2D網(wǎng)絡(luò)資源分配算法[14,15].首先根據(jù)系統(tǒng)內(nèi)的干擾情況建立干擾圖，然后設(shè)計(jì)適應(yīng)度函數(shù)以尋找適應(yīng)度最大的信道分配方案.實(shí)驗(yàn)結(jié)果表明，本文算法可以在保證蜂窩用戶QoS的前提下，提高系統(tǒng)總吞吐量和D2D接入率.

1 系統(tǒng)模型

本文主要研究單個(gè)蜂窩小區(qū)中D2D用戶復(fù)用蜂窩用戶上行鏈路信道資源的分配問(wèn)題.假設(shè)該小區(qū)中共有M個(gè)蜂窩用戶，N對(duì) D2D用戶，K個(gè)信道資源.集合C={C1,C2,…Ci,…CM},D={D1,D2,…Dj,…DN},K={1,2,…，k}分別代表蜂窩用戶集合、D2D用戶集合和信道集合.如圖1所示，小區(qū)中有一個(gè)宏基站BS、一個(gè)蜂窩用戶CU和兩個(gè)D2D對(duì)用戶，其中DTU代表D2D對(duì)的發(fā)射端，DRU代表D2D對(duì)的接收端.

圖1 單蜂窩網(wǎng)絡(luò)模型Fig.1 Single cellular network model

模型中主要存在三種干擾：D2D用戶接收設(shè)備受到基站的干擾；蜂窩用戶接收設(shè)備受到復(fù)用同樣頻譜資源的D2D用戶發(fā)射設(shè)備的干擾；D2D用戶接收設(shè)備受到其他D2D用戶發(fā)射設(shè)備的干擾.這三種干擾皆為同頻干擾.

假設(shè)蜂窩用戶和D2D用戶的功率分別設(shè)定為PC和PD，因此可得蜂窩用戶C的信干噪比為

(1)

D2D用戶Di的信干噪比為

SINRDj=

(2)

根據(jù)香農(nóng)公式可以得到用戶Ci和D2D用戶Dj的吞吐量RCi和RDj分別為

RCi=Blog2(1+SINRCi),

(3)

RDj=Blog2(1+SINRDj),

(4)

其中B代表信道帶寬.

2 問(wèn)題規(guī)劃及算法描述

2.1 干擾圖的構(gòu)建

為了對(duì)D2D資源分配問(wèn)題進(jìn)行求解，基于蜂窩用戶和D2D用戶之間的干擾關(guān)系，構(gòu)建干擾圖P=(V,E)，其中頂點(diǎn)集合V={V1,V2,…，Vv,…，VM+N}中的每一個(gè)頂點(diǎn)代表一個(gè)蜂窩用戶或一個(gè)D2D用戶對(duì)，邊的集合E中的每一條邊e(Vv,Vv′)代表頂點(diǎn)Vv受到頂點(diǎn)Vv′的干擾，邊的大小代表干擾強(qiáng)度.邊的公式為：

(5)

式(5)中，第一個(gè)式子表示兩個(gè)蜂窩設(shè)備使用正交的信道，它們之間不存在干擾，第二個(gè)式子表示一個(gè)通信鏈路不存在自身干擾，因此它們相應(yīng)的邊的權(quán)值為零，其余三個(gè)式子分別表示D2D用戶對(duì)蜂窩用戶的干擾，不同D2D對(duì)間的干擾以及蜂窩用戶對(duì)D2D用戶的干擾.

2.2 問(wèn)題規(guī)劃與可行解

假設(shè)基站了解所有終端狀態(tài)及鏈路信息，小區(qū)處于滿載狀態(tài)，且每個(gè)蜂窩用戶占用不同的信道資源.本文的目的是找到最優(yōu)的D2D信道分配方案，從而提高D2D接入率.基于干擾圖可以將信道分配問(wèn)題建模為如下的目標(biāo)函數(shù)：

(6)

SINRCi≥SINRCthreshold,?Ci∈C,

(7)

(8)

xi,j∈{0,1},

(9)

X∈{0,1}N×K,

(10)

式(6)表示優(yōu)化目標(biāo)為將受干擾最大的D2D對(duì)的干擾值最小化，其中，Vj代表一個(gè)D2D用戶，Vv代表一個(gè)蜂窩用戶或一個(gè)D2D對(duì)，e(Vv,Vv′)代表頂點(diǎn)Vv受到頂點(diǎn)Vv′的干擾值.式(7)表示蜂窩用戶的信干噪比要大于門(mén)限值，式(8)表示多個(gè)D2D用戶可以復(fù)用一個(gè)信道資源，式(9)表示第j個(gè)D2D用戶復(fù)用第i個(gè)蜂窩用戶的信道資源，式(10)為問(wèn)題(6)的一個(gè)可行解，當(dāng)xi,j=1時(shí)X的第j行第i列為1，當(dāng)xi,j=0時(shí)X的第j行第i列為0，X的行代表某一個(gè)D2D對(duì)復(fù)用的信道，列代表某一個(gè)信道被哪些D2D對(duì)復(fù)用.

可行解X表示一個(gè)D2D用戶的信道分配方案.為了便于算法的求解，將可行解X由矩陣轉(zhuǎn)化為集合G={G1,…，Gn,…，GN}Gn∈{1,…，i,…,M}，其中Gn=i代表第n個(gè)D2D用戶復(fù)用第i個(gè)蜂窩用戶的信道.

2.3 適應(yīng)度函數(shù)的設(shè)計(jì)

2.4 遺傳算法的改進(jìn)

2.4.1 種群初始化的改進(jìn)

經(jīng)典遺傳算法的初始化過(guò)程是在解空間中隨機(jī)產(chǎn)生種群規(guī)模數(shù)量的點(diǎn)，然后將這些點(diǎn)作為初始種群.這種做法對(duì)多峰復(fù)雜函數(shù)來(lái)說(shuō)，如果后續(xù)遺傳算子操作不當(dāng)很容易使算法出現(xiàn)早熟現(xiàn)象.出現(xiàn)早熟，一般是由于算法沒(méi)找到解空間中最優(yōu)解所在的波峰，或者處于最優(yōu)解所在波峰的較低位置進(jìn)而被進(jìn)化淘汰.因此為了能更大概率的找到最優(yōu)解，避免出現(xiàn)早熟現(xiàn)象，本文使用聯(lián)賽選擇方法進(jìn)行種群初始化，具體做法為：按一般種群初始化方法隨機(jī)生成P個(gè)個(gè)體；計(jì)算個(gè)體適應(yīng)度，并按照個(gè)體適應(yīng)度進(jìn)行排序；選取適應(yīng)度最高的一個(gè)個(gè)體作為初始種群的成員；重復(fù)上述步驟直至選出P個(gè)個(gè)體作為初始種群.

2.4.2 選擇算子的改進(jìn)

在遺傳進(jìn)化的初期通常會(huì)產(chǎn)生一些適應(yīng)度很大的個(gè)體，按照傳統(tǒng)的輪盤(pán)賭方法選擇個(gè)體，這些個(gè)體由于競(jìng)爭(zhēng)力大會(huì)被大量選中，造成種群基因多樣性降低，導(dǎo)致算法易陷入局部最優(yōu)解.因此本文對(duì)其進(jìn)行了改進(jìn)，具體做法為：將種群中的個(gè)體按照適應(yīng)度進(jìn)行排序；按照傳統(tǒng)輪盤(pán)賭方法從種群中選擇一個(gè)個(gè)體作為父代，并將該個(gè)體從種群中移走；重復(fù)上述步驟直到產(chǎn)生P個(gè)父代個(gè)體.

2.5 基于遺傳退火的密集D2D網(wǎng)絡(luò)的資源分配算法

本文將遺傳退火算法用于尋找最優(yōu)的D2D資源分配方案，其中一個(gè)個(gè)體即為一個(gè)資源分配方案，個(gè)體中的一個(gè)基因代表一個(gè)D2D用戶的信道復(fù)用方案.

算法具體步驟如下：

(1)根據(jù)干擾圖構(gòu)建D2D用戶的候選信道，當(dāng)D2D用戶和蜂窩用戶的距離小于20 m時(shí)，則D2D用戶不能復(fù)用該信道.

(2)種群初始化

(3)精英保留，將P/5的個(gè)體直接復(fù)制到子代.

(4)進(jìn)行改進(jìn)的選擇操作，選擇出4P/5個(gè)個(gè)體.

(5)對(duì)(4)中選擇的個(gè)體依據(jù)交叉概率隨機(jī)選擇一個(gè)基因位進(jìn)行單點(diǎn)交叉，生成2P/5個(gè)子代.

(6)對(duì)(5)中產(chǎn)生的個(gè)體進(jìn)行變異操作 依據(jù)變異概率對(duì)新產(chǎn)生的子代進(jìn)行變異操作，具體操作為對(duì)個(gè)體基因選取隨機(jī)位數(shù)，對(duì)選取出的基因依概率PV在[1-k]中隨機(jī)選取一個(gè)值代替舊的基因，生成新的2P/5個(gè)子代.

(7)對(duì)產(chǎn)生的新一代種群進(jìn)行適應(yīng)度排序，并保留適應(yīng)度最高的個(gè)體.判斷該個(gè)體中蜂窩用戶是否滿足最低信干噪比，如果不滿足，則刪除復(fù)用該信道的受到干擾值最大的D2D用戶，重復(fù)該步直到蜂窩用戶滿足最低信干噪比.

(8)對(duì)(7)中適應(yīng)度最高的個(gè)體進(jìn)行模擬退火操作，生成新個(gè)體并計(jì)算其適應(yīng)度.并判斷新個(gè)體中蜂窩用戶是否滿足最低信干噪比，執(zhí)行如步驟(7)中相同的步驟.

(9)比較(7)和(8)中產(chǎn)生的兩個(gè)個(gè)體的適應(yīng)度，適應(yīng)度高的個(gè)體作為最優(yōu)個(gè)體進(jìn)行保存.

(10)收斂條件判定.對(duì)最優(yōu)個(gè)體進(jìn)行判定，若它的個(gè)體適應(yīng)度函數(shù)滿足條件或達(dá)到最大迭代次數(shù)就輸出最優(yōu)解，否則返回第3步繼續(xù)進(jìn)行循環(huán).

3 仿真分析

本文在MATLAB仿真平臺(tái)對(duì)算法進(jìn)行仿真，重復(fù)執(zhí)行100次，然后對(duì)結(jié)果取平均值，每一次算法執(zhí)行過(guò)程中蜂窩用戶和D2D用戶都隨機(jī)分布在小區(qū)中，D2D用戶間的距離隨機(jī)產(chǎn)生，并限定在20 m以內(nèi).本文在保證蜂窩用戶QoS的前提下對(duì)隨機(jī)分配算法(Random Algorithm，RA)、改進(jìn)的圖著色算法IGCA和遺傳退火算法GAA進(jìn)行了對(duì)比.GAA中的參數(shù)設(shè)置為：種群規(guī)模P=100，交叉概率PC=0.8，變異概率PV=0.1，最大迭代次數(shù)為500，初始溫度T0=100，結(jié)束溫度T1=0.01，減溫系數(shù)為0.99，每個(gè)溫度的迭代次數(shù)為100.實(shí)驗(yàn)參數(shù)如表1所示.

表1 實(shí)驗(yàn)參數(shù)Tab.1 Experimental parameters

3.1 吞吐量仿真

圖2描述的是蜂窩用戶數(shù)量M為10和信道數(shù)量K為10時(shí)，系統(tǒng)總吞吐量與D2D對(duì)總數(shù)量之間的關(guān)系圖.

圖2 M=10，K=10時(shí)系統(tǒng)總吞吐量隨D2D對(duì)數(shù)量的變化圖Fig.2 The total system throughput vs. the number of D2D at M=10 and K=10

如圖2所示，GAA與IGCA、RA相比，系統(tǒng)總吞吐量平均增幅為6.2%和21.8%.當(dāng)D2D對(duì)總數(shù)量小于30時(shí)，三種算法的總吞吐量都在增加，但隨著D2D對(duì)總數(shù)量逐漸增多，系統(tǒng)總吞吐量增加速度逐漸變緩.這是因?yàn)樾诺蕾Y源有限，D2D對(duì)數(shù)量越多，占用同一信道的D2D對(duì)也隨之增多，導(dǎo)致系統(tǒng)中干擾也變多.當(dāng)D2D對(duì)數(shù)量超過(guò)30時(shí)，GAA的系統(tǒng)總吞吐量繼續(xù)增加，IGCA和RA的系統(tǒng)總吞吐量卻發(fā)生下降.這是因?yàn)镮GCA是通過(guò)為每一個(gè)D2D對(duì)尋找其最優(yōu)信道，不斷迭代得到信道分配方案，當(dāng)D2D用戶數(shù)量過(guò)多時(shí)，會(huì)有過(guò)多的D2D用戶選擇最優(yōu)信道，導(dǎo)致干擾增大，系統(tǒng)總吞吐量降低；RA是由于信道隨機(jī)分配，可能導(dǎo)致過(guò)多的D2D對(duì)選擇同一信道，系統(tǒng)中干擾增大，導(dǎo)致系統(tǒng)總吞吐量降低.

3.2 D2D接入率仿真

圖3描述的是蜂窩用戶數(shù)量M為10和信道數(shù)量K為10時(shí)，D2D對(duì)接入率與D2D對(duì)總數(shù)量之間的關(guān)系圖.

圖3 M=10，K=10時(shí)D2D接入率隨D2D對(duì)數(shù)量的變化圖Fig.3 D2D access rate vs. the number of D2D at M=10 and K=10

如圖3所示，GAA與IGCA、RA相比，D2D用戶接入率平均增幅為14.7%和44.5%.這是因?yàn)镮GCA是為每個(gè)D2D對(duì)尋找最優(yōu)信道，這會(huì)導(dǎo)致所有D2D對(duì)都去選擇最優(yōu)信道，而部分通信狀況不好的D2D對(duì)無(wú)法找到滿足QoS的信道；而GAA將受到干擾最大的D2D對(duì)的干擾值作為適應(yīng)度函數(shù)對(duì)解進(jìn)行選擇，即只關(guān)注通信狀況最差的D2D對(duì)，只要使它滿足該D2D對(duì)的QoS，則所有D2D對(duì)都能滿足QoS，這樣能更好的提升D2D對(duì)接入數(shù)量；RA則是因?yàn)樾诺婪峙涞碾S機(jī)性使得D2D對(duì)無(wú)法滿足QoS.

3.3 設(shè)備吞吐量的累積分布函數(shù)仿真

從圖4可以看出，GAA約有91%的設(shè)備吞吐量超過(guò)2.5bit/s/hz，而IGCA和RA約占70%、54%.這是因?yàn)镮GCA中一部分D2D用戶選擇了最優(yōu)的信道，導(dǎo)致部分D2D用戶無(wú)法找到能滿足QoS的信道；GAA中D2D用戶選擇的信道滿足QoS即可，而不一定是最優(yōu)信道，使得一部分通信狀況差的用戶也可以找到滿足QoS的信道；RA是因?yàn)殡S機(jī)分配信道使得部分D2D用戶無(wú)法滿足QoS.

圖4 M=10，K=10，N=40時(shí)設(shè)備吞吐量的累積分布函數(shù)Fig.4 Cumulative distribution function of device throughput atM=10 and K=10

3.4 復(fù)雜度分析

本文的GAA首先要計(jì)算蜂窩用戶和D2D用戶的干擾矩陣，因此構(gòu)建干擾圖的復(fù)雜度為O[(M+N)^2].如果遺傳算法的迭代次數(shù)為q，退火算法的溫度控制外循環(huán)次數(shù)假定為a,在每個(gè)特定溫度下內(nèi)循環(huán)次數(shù)為b，那么遺傳退火算法的復(fù)雜度就是O[q*a*b].因此，當(dāng)(M+N)的值足夠大時(shí)，GAA的總復(fù)雜度為O[(M+N)^2]，而IGCA的復(fù)雜度為O[N*(M+N)^2]，顯然GAA的復(fù)雜度是低于IGCA的.綜上所述，GAA更適合于高密集D2D網(wǎng)絡(luò)場(chǎng)景.

4 結(jié)語(yǔ)

為了提高系統(tǒng)總吞吐量和D2D接入率，降低用戶之間的干擾，本文提出了基于遺傳退火的密集D2D網(wǎng)絡(luò)資源分配算法.首先分析了系統(tǒng)中存在的三種干擾，并依據(jù)干擾情況構(gòu)建出小區(qū)內(nèi)用戶之間的干擾圖；然后根據(jù)干擾圖構(gòu)建出D2D用戶的候選信道集合，并將受到干擾最大的D2D用戶的干擾值作為代價(jià)函數(shù)，通過(guò)遺傳退火算法尋找適應(yīng)度最高的解方案；最后進(jìn)行了仿真實(shí)驗(yàn).仿真結(jié)果表明，本文提出的算法可以在有效提高系統(tǒng)總吞吐量的同時(shí)，還可以提高D2D用戶的接入率.本文只考慮了在單小區(qū)場(chǎng)景下的信道分配問(wèn)題，未考慮功率分配以及小區(qū)間的干擾問(wèn)題，下一步將聯(lián)合功率分配對(duì)多小區(qū)場(chǎng)景下的資源分配問(wèn)題展開(kāi)深入研究.