基于改進(jìn)遺傳算法的C-RAN網(wǎng)絡(luò)動(dòng)態(tài)無(wú)線資源分配*

徐東明，譚靜茹，關(guān)文博

(1.西安郵電大學(xué) 通信與信息工程學(xué)院，西安 710121；2.西安電子科技大學(xué) 微電子學(xué)院,西安 710071)

0 引 言

云無(wú)線接入網(wǎng)(Cloud Radio Access Network,C-RAN)主要由分布式無(wú)線射頻拉遠(yuǎn)部分(Remote Radio Head,RRH)、集中式基帶處理池(Base Band Unit Pool,BBU)和連接兩者的前傳網(wǎng)絡(luò)(Frounthaul)三部分構(gòu)成[1]。不管是C-RAN基本特點(diǎn)的實(shí)現(xiàn)還是未來(lái)無(wú)線接入網(wǎng)絡(luò)各種要求的滿足，都離不開(kāi)的主題就是對(duì)接入網(wǎng)絡(luò)中各種資源的分配。目前國(guó)內(nèi)外學(xué)者對(duì)C-RAN架構(gòu)下的資源管理策略的研宄可分為兩個(gè)方面，即基于RRH的無(wú)線資源分配和基于BBU池的計(jì)算資源分配[2]。在無(wú)線資源分配問(wèn)題中，又分為一維資源分配與多維資源分配。當(dāng)只考慮RRH中的單個(gè)無(wú)線資源優(yōu)化時(shí)，文獻(xiàn)[3]使用遺傳算法(Genetic Algorithm,GA)研究了C-RAN中BBU和RRH之間的網(wǎng)絡(luò)功能劃分問(wèn)題，通過(guò)合理的劃分來(lái)降低C-RAN的運(yùn)營(yíng)成本。文獻(xiàn)[4]研究了泊松到達(dá)的C-RAN網(wǎng)絡(luò)中的呼叫阻塞概率，將RRH根據(jù)容量不同形成集群服務(wù)于網(wǎng)絡(luò)中的泊松到達(dá)用戶，通過(guò)卷積算法對(duì)阻塞概率進(jìn)行分析。文獻(xiàn)[5]研究了RRH的邊緣緩存問(wèn)題，提出了一種基于成本調(diào)度的方案來(lái)進(jìn)行RRH處的緩存資源調(diào)度，以改善用戶體驗(yàn)。在聯(lián)合考慮多維無(wú)線資源優(yōu)化時(shí)，文獻(xiàn)[6]針對(duì)毫米波信道模型下的RRH的選擇方案做了研究，基于RRH發(fā)射功率，覆蓋范圍和毫米波最大傳輸距離這三個(gè)約束條件得到了一個(gè)最優(yōu)的RRH分配方案，提高了系統(tǒng)的能量效率。文獻(xiàn)[7]提出了一種基于吞吐量感知的RRH聚類模型，提高了系統(tǒng)吞吐量，但對(duì)信道條件要求較高。

在服務(wù)質(zhì)量(Quality of Service,QoS)約束的選擇上，網(wǎng)絡(luò)資源的低效利用往往導(dǎo)致負(fù)載失衡、呼叫阻塞事件增多和用戶服務(wù)質(zhì)量的下降。已有文獻(xiàn)對(duì)C-RAN場(chǎng)景下QoS約束的考慮大多集中在中斷概率方面，對(duì)系統(tǒng)時(shí)延研究較少。文獻(xiàn)[8]考慮了時(shí)延約束和前傳鏈路約束，文獻(xiàn)[9]將包含處理時(shí)延和傳輸時(shí)延的隊(duì)列模型按照M/M/1型串聯(lián)在一起進(jìn)行討論。

在算法研究中，相較于傳統(tǒng)的優(yōu)化算法，群體智能算法對(duì)目標(biāo)函數(shù)和可行域的要求更低，在操作上具有很高的可行性。遺傳算法作為群體智能算法的一種，在通信領(lǐng)域的資源分配問(wèn)題中常常被使用，算法的結(jié)果不依賴于初始值的選取，同時(shí)不會(huì)產(chǎn)生精度波動(dòng)[10]。文獻(xiàn)[11]提出將GA和多主體優(yōu)化算法(Multi-agent Optimization,MAO)進(jìn)行結(jié)合，最大限度地提高了云計(jì)算中的資源利用率。文獻(xiàn)[12]提出了一種安全的嵌入式動(dòng)態(tài)資源分配模型，并通過(guò)非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm,NSGA-II)提高了虛擬機(jī)在任務(wù)遷移和部署期間的安全性和資源分配效率。文獻(xiàn)[13]使用粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)與GA研究了云計(jì)算中軟件服務(wù)的自適應(yīng)資源分配問(wèn)題，在所提資源分配策略下，相較于傳統(tǒng)遺傳算法，PSO-GA算法能夠在服務(wù)質(zhì)量和資源成本之間能取得更好的折中效果。文獻(xiàn)[14]研究了移動(dòng)多用戶通信系統(tǒng)中的中斷概率，提出了基于增強(qiáng)灰狼算法的功率分配算法，同時(shí)與多種群體智能算法進(jìn)行了對(duì)比，驗(yàn)證了所提算法的優(yōu)越性。

基于以上研究，本文將C-RAN系統(tǒng)中的無(wú)線資源分配作為研究對(duì)象，運(yùn)用改進(jìn)遺傳算法(Improved Genetic Algorithm,IGA)對(duì)具體分配方案進(jìn)行了研究。本文主要貢獻(xiàn)有：將RRH的無(wú)線資源映射為RRH選擇、子載波分配、功率分配；在約束條件上，將用戶請(qǐng)求的數(shù)據(jù)從處理到完成發(fā)送的總時(shí)延定義為QoS約束，并將時(shí)延隊(duì)列用M/G/1型排隊(duì)系統(tǒng)串聯(lián)在一起進(jìn)行研究，在QoS約束和系統(tǒng)傳輸模型下建立了以吞吐量最大化為優(yōu)化目標(biāo)的優(yōu)化問(wèn)題，對(duì)三種維度的無(wú)線資源進(jìn)行了合理的分配；在算法選擇上，由于目標(biāo)函數(shù)是非線性的，優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題，因此提出了IGA算法，將RRH選擇、子載波分配、功率分配作為染色體的三個(gè)部分的分配進(jìn)行了優(yōu)化，從而達(dá)到提高吞吐量的目的。

1 系統(tǒng)模型與問(wèn)題建立

1.1 系統(tǒng)傳輸模型

圖1 C-RAN系統(tǒng)架構(gòu)

由于無(wú)線信道傳輸存在不穩(wěn)定性，信息傳輸時(shí)的瞬時(shí)速率并不能總保持一個(gè)穩(wěn)定值。為了提高算法的穩(wěn)定性，本文在后續(xù)仿真中設(shè)定信道環(huán)境為完美信道狀態(tài)信息(Channel State Information,CSI)，在所有信息傳輸過(guò)程中速率為一均值。RRH與BBU池通過(guò)一個(gè)理想光纖鏈路進(jìn)行連接，由于信號(hào)通過(guò)光纖傳輸時(shí)損耗很小，因此對(duì)所有傳輸鏈路來(lái)說(shuō)，噪聲功率譜密度N0是相同的。

(1)

根據(jù)香農(nóng)公式，用戶m的可達(dá)速率為

(2)

1.2 系統(tǒng)QoS約束

圖2 M/G/1型排隊(duì)系統(tǒng)

(3)

根據(jù)上述公式，當(dāng)t→∞時(shí)，系統(tǒng)平均剩余服務(wù)時(shí)間為

(4)

當(dāng)?shù)趍個(gè)用戶連接第k個(gè)RRH時(shí)，平均等待時(shí)間為

(5)

在系統(tǒng)QoS約束的前提要求下，用戶在隊(duì)列中的傳輸時(shí)延和處理時(shí)延必須低于其能夠等待的最大時(shí)延，即

(6)

1.3 系統(tǒng)優(yōu)化問(wèn)題建立

在C-RAN網(wǎng)絡(luò)中，系統(tǒng)的吞吐量之和為

(7)

(8)

在一個(gè)時(shí)隙τ中，為了限制UEm與RRHk之間一一對(duì)應(yīng)的映射關(guān)系，子載波分配應(yīng)滿足

(9)

(10)

根據(jù)前文中提到的條件，目標(biāo)函數(shù)可以表示為

(11)

式中：C1為QoS約束，C2為子載波分配情況，C3為系統(tǒng)最大發(fā)射功率約束，C4表示一個(gè)子載波只能分配給單個(gè)用戶，C5為最小傳輸速率限制。

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

C-RAN網(wǎng)絡(luò)中無(wú)線資源的存在形式與種類多種多樣，如何將這些資源進(jìn)行更加有效的分配，是一個(gè)具有不確定性和復(fù)雜性的問(wèn)題。特別是在優(yōu)化過(guò)程中，如何提高系統(tǒng)利用率、聯(lián)合考慮多重?zé)o線資源、克服信道條件以及無(wú)線傳輸?shù)牟环€(wěn)定性，使用傳統(tǒng)的數(shù)學(xué)工具已經(jīng)不能精準(zhǔn)解決如上問(wèn)題。

遺傳算法(Genetic Algorithm,GA)由美國(guó)計(jì)算機(jī)學(xué)家Holland提出，它的主要思想是用生物進(jìn)化理論模擬自然選擇和遺傳機(jī)制的進(jìn)化過(guò)程，并進(jìn)行數(shù)學(xué)建模，尋找科學(xué)研究中疑難問(wèn)題的解決方案。經(jīng)過(guò)Goldherg等人的總結(jié)與改進(jìn)，最終發(fā)展成一種啟發(fā)式算法。參數(shù)編碼、設(shè)定初始群體、設(shè)計(jì)適應(yīng)度函數(shù)、設(shè)計(jì)遺傳操作、控制參數(shù)等則構(gòu)成遺傳算法的核心要素。

本文對(duì)遺傳算法進(jìn)行改進(jìn)，將RRH選擇、子載波分配、RRH功率分配同時(shí)優(yōu)化，以達(dá)到原優(yōu)化方案中最大化吞吐量的優(yōu)化目標(biāo)。

2.1 編碼與產(chǎn)生初始群體

編碼是遺傳算法首要的解決問(wèn)題，為了克服常用的二進(jìn)制編碼的固有缺陷，即編碼的精確度和普適度，本文采用實(shí)數(shù)編碼，避免了編碼的復(fù)雜性，縮短了染色體的長(zhǎng)度，提高了計(jì)算效率。本文將系統(tǒng)中無(wú)線資源分配次數(shù)的集合作為改進(jìn)遺傳算法中的種群，一次無(wú)線資源的分配作為一個(gè)個(gè)體，每個(gè)個(gè)體的染色體由三部分構(gòu)成，包括RRH選擇、子載波分配、RRH功率分配，每個(gè)染色體的基因值為其資源分配的結(jié)果。

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

適應(yīng)度函數(shù)能夠反映種群里所有個(gè)體對(duì)環(huán)境的適應(yīng)性。簡(jiǎn)而言之，決定一個(gè)個(gè)體能否生存并將基因繁衍到下一代的因素就是其適應(yīng)度值的大小。傳統(tǒng)遺傳算法一般將目標(biāo)函數(shù)f(x)設(shè)為種群的適應(yīng)度函數(shù)Fitness(x)，由于這種構(gòu)造方式可能產(chǎn)生負(fù)的適應(yīng)度值，不能滿足輪盤賭算子中非負(fù)適應(yīng)度的條件[16]，因此對(duì)適應(yīng)度函數(shù)進(jìn)行改進(jìn)。本文中優(yōu)化目標(biāo)為系統(tǒng)總吞吐量最大，所以算法的適應(yīng)度函數(shù)為

(12)

2.3 選擇操作

在遺傳算法中，輪盤賭算子是一種常用的選擇方法，它的缺點(diǎn)是容易導(dǎo)致早熟現(xiàn)象，因此對(duì)選擇操作進(jìn)行改進(jìn)。

首先,采用保留最佳個(gè)體算子，使得包含優(yōu)良基因且適應(yīng)度值排名前5%的個(gè)體被保留[17]，讓其直接演化到下一代；其次，采用輪盤賭算子，將其余適應(yīng)度相對(duì)較高的個(gè)體通過(guò)輪盤賭進(jìn)行選擇，隨后將它們復(fù)制并隨機(jī)與兩個(gè)親本染色體進(jìn)行之后的操作。本方案可直接減少擁有優(yōu)良基因的劣勢(shì)個(gè)體被淘汰的概率，使種群能夠更加適應(yīng)生存環(huán)境。

個(gè)體i被選擇的概率為

(13)

個(gè)體i的累計(jì)概率為

Oi=∑Pi。

(14)

式中：Fi為個(gè)體i的適應(yīng)度值，Q為種群規(guī)模。

2.4 交叉操作

經(jīng)典的交叉算法在交叉過(guò)程中容易產(chǎn)生局部極小，因此本文提出新的交叉算子。

首先對(duì)RRH選擇、子載波分配提出多點(diǎn)簡(jiǎn)單交叉算子。算法首先產(chǎn)生一個(gè)長(zhǎng)度為2M的屏蔽字，其中每個(gè)元素由等概率的0和1構(gòu)成，前M個(gè)元素對(duì)應(yīng)RRH選擇，第M+1～2M個(gè)元素對(duì)應(yīng)子載波分配，當(dāng)元素值為1時(shí)，相對(duì)應(yīng)的兩個(gè)染色體的基因以交叉概率Pc進(jìn)行交叉，為0時(shí)保持不變。對(duì)于功率分配提出多點(diǎn)非均勻算數(shù)交叉算子。首先產(chǎn)生一個(gè)長(zhǎng)度為M的屏蔽字，其中每個(gè)元素由等概率的0和1組成并分別對(duì)應(yīng)功率分配的每一個(gè)基因。當(dāng)元素值為1時(shí)，兩個(gè)相對(duì)應(yīng)點(diǎn)的父代基因值以交叉概率Pc進(jìn)行交叉得到新的子代基因，為0時(shí)保持不變。該交叉算子產(chǎn)生新的子代染色體方法為

childXi=r×parentXi+(1-r)×parentYi，

(15)

childYi=r×parentYi+(1-r)×parentXi。

(16)

式中：r為[0,1]之內(nèi)的均勻隨機(jī)數(shù)。

圖3為M=6、N=4、K=4、r=0.4時(shí)改進(jìn)的交叉操作過(guò)程。其中，RRH選擇、子載波分配的親本基因值具體參數(shù)從[1,2,3,4]中隨機(jī)選取，RRH功率分配的親本基因值具體參數(shù)從(0，1)中隨機(jī)選取。由于RRH選擇和子載波分配均采用同一交叉算子，因此圖中RRH選擇部分的交叉過(guò)程同樣適用于子載波分配，只不過(guò)兩者隨機(jī)所產(chǎn)生的屏蔽字序列有所不同。

圖3 交叉操作

2.5 變異操作

在遺傳學(xué)中，變異指基因突變導(dǎo)致新染色體的產(chǎn)生和新性狀的獲得。常見(jiàn)的變異算子都有兩個(gè)不確定性：一方面，當(dāng)前種群中擁有最高適應(yīng)度值的基因可能會(huì)進(jìn)行突變，從而破壞了目標(biāo)函數(shù)的最優(yōu)解；另一方面，當(dāng)前種群中適應(yīng)度值較低的一些基因可能不會(huì)做任何變異，從而不能改善種群的多樣性，并容易導(dǎo)致種群早熟。為此，提出新的變異操作。

對(duì)于RRH選擇和子載波分配部分，首先設(shè)置一個(gè)2×1的屏蔽字，其由等概率的1和0產(chǎn)生并且分別對(duì)應(yīng)RRH選擇和子載波分配，元素值為1時(shí)，隨機(jī)選擇2個(gè)基因值以變異概率Pm=0.001進(jìn)行變異，否則不變。對(duì)于功率分配部分，文獻(xiàn)[18]提出了一種粒子群變異算子，實(shí)驗(yàn)表明該變異算子展現(xiàn)了良好的局部搜索能力。本文依照實(shí)際進(jìn)化要求對(duì)其做了調(diào)整，首先將當(dāng)前種群中的所有基因按照適應(yīng)度大小排序，然后只對(duì)適應(yīng)度較低的基因以變異概率Pm=0.001進(jìn)行變異。具體計(jì)算公式如下：

(17)

圖4 變異操作

2.6 終止

循環(huán)執(zhí)行選擇、交叉、變異的工作，直到種群數(shù)量達(dá)到設(shè)定值Q，選擇第G代中適應(yīng)度值最高的染色體個(gè)體，其各部分的基因值即為使吞吐量最大的RRH選擇、子載波分配和RRH功率分配。

改進(jìn)的遺傳算法偽代碼如下：

Step1 產(chǎn)生初始群體

For(i=1 to MaxGeneration)do

G=(RRH Selection,Subcarrier Allocation,Power Allication)

Step2 計(jì)算適應(yīng)度值

Calculate all fitness values according to the formula(12)

Step3 選擇操作

Keep the high fitness vales individuals from population

Step4 交叉操作

for(j=1 to PopulationNumber/2*Cross Rate)do

choose two individualsXandY；

(X′,Y′)=Crossover(X,Y)；

Calculate the new fitness values；

end for

Step5 變異操作

for(j=1 to PopulationNumber*Mutation Rate)do

choose two individualsX；

X′=Mutation(X)；

Calculate the new fitness values；

end for

Step6 終止條件判斷

if(i=MaxGeneration)break；

else

i+1；

end if

end for

Output：MaxThroughput

3 數(shù)值仿真與結(jié)果分析

3.1 仿真參數(shù)設(shè)計(jì)

為了驗(yàn)證所提無(wú)線資源分配算法有效性，本節(jié)使用Matlab仿真平臺(tái)進(jìn)行數(shù)值仿真，具體仿真參數(shù)[19-20]如表1所示。

表1 仿真參數(shù)

3.2 仿真結(jié)果分析

3.2.1 算法復(fù)雜度

本文以種群規(guī)模為變量，在時(shí)間復(fù)雜度上將IGA算法同差分進(jìn)化算法(Differential Evolution,DE)、GA算法、PSO算法、文獻(xiàn)[7]算法進(jìn)行了比較。從圖5中可以看出各個(gè)算法的復(fù)雜度排序依次為DE>GA>文獻(xiàn)[7]>IGA>PSO，本文算法復(fù)雜度相對(duì)較低。

圖5 算法時(shí)間復(fù)雜度對(duì)比

3.2.2 算法穩(wěn)定性

在實(shí)驗(yàn)過(guò)程中，設(shè)置交叉概率pc=0.8，變異概率pm=0.001，系統(tǒng)吞吐量與種群演化代數(shù)G的關(guān)系如圖6所示。從圖中可以看出，在種群規(guī)模不變的情況下，吞吐量隨著演化代數(shù)的增加而逐漸增大。這是由于演化代數(shù)越多，與前一代種群相比，后一代種群的優(yōu)良個(gè)體總是更加容易生存，進(jìn)而增加系統(tǒng)吞吐量。在演化代數(shù)固定時(shí)，吞吐量隨著種群數(shù)量的增加而增加。這是由于種群數(shù)量越大，優(yōu)良個(gè)體的數(shù)量就越多，所求次優(yōu)解就越接近于最優(yōu)解。同時(shí)，不論種群規(guī)模如何變化，當(dāng)種群演化到G=200時(shí)，吞吐量基本趨于穩(wěn)定，表明算法具有很好的穩(wěn)定性。因此，在后續(xù)的仿真中，設(shè)置最大演化代數(shù)G=300，種群規(guī)模Q=200。

圖6 系統(tǒng)吞吐量和種群演化代數(shù)的關(guān)系

3.2.3 吞吐量

由圖7可見(jiàn)，隨著RRH數(shù)量的增加，系統(tǒng)吞吐量也在大幅增加。這是由于當(dāng)安置更多RRH時(shí)，RRH將分別與BBU和用戶端進(jìn)行更多的信息交互，提高系統(tǒng)的吞吐量。在RRH數(shù)量較大時(shí)，本文所提算法達(dá)到的系統(tǒng)吞吐量高于文獻(xiàn)[7]，且后者對(duì)信道條件與路網(wǎng)狀況要求較高，在實(shí)際情況中難以達(dá)到其實(shí)驗(yàn)值。在本文算法下，當(dāng)RRH數(shù)量為30時(shí)仿真得到系統(tǒng)吞吐量為291 Mb/s，文獻(xiàn)[7]吞吐量為232 Mb/s，此時(shí)吞吐量增益為25%。

圖7 系統(tǒng)吞吐量和RRH數(shù)量的關(guān)系

圖8給出了系統(tǒng)吞吐量和子載波數(shù)量的關(guān)系，可以看出，子載波數(shù)量一定時(shí)，本文所提算法明顯比已有算法更能使系統(tǒng)吞吐量增大。子載波數(shù)量較少時(shí)，系統(tǒng)吞吐量與子載波數(shù)量呈正相關(guān)。這是由于子載波數(shù)量的增加提高了系統(tǒng)傳輸速率和頻譜資源分配的靈活度，使得傳輸質(zhì)量增加，因此吞吐量增大。當(dāng)子載波超過(guò)一定數(shù)量時(shí)，系統(tǒng)吞吐量將逐漸趨于平穩(wěn)。這是因?yàn)镽RH可傳遞的信息容量有限，無(wú)法利用剩余的子載波和用戶進(jìn)行信息交互，所以吞吐量不再增大。當(dāng)子載波數(shù)量相同且吞吐量趨于平穩(wěn)時(shí)，此時(shí)系統(tǒng)吞吐量為233 Mb/s，文獻(xiàn)[7]算法所得吞吐量為199 Mb/s，吞吐量增益為17%。

圖8 系統(tǒng)吞吐量和子載波數(shù)量的關(guān)系

從圖9可以看出，RRH發(fā)射功率較低時(shí)，系統(tǒng)吞吐量隨RRH發(fā)射功率的增加而增加，而當(dāng)RRH發(fā)射功率繼續(xù)增加時(shí)，系統(tǒng)會(huì)接入更多的可服務(wù)用戶，使得部分RRH處于超負(fù)荷狀態(tài)，會(huì)增大用戶隊(duì)列的等待時(shí)延，降低傳輸速率，因此系統(tǒng)吞吐量減小。當(dāng)RRH發(fā)射功率達(dá)到峰值時(shí)，吞吐量為142 Mb/s，文獻(xiàn)[7]算法所得吞吐量為130 Mb/s，吞吐量增益為9%。由此可以得出整個(gè)系統(tǒng)的平均吞吐量增益為17%，同時(shí)也很容易得出，當(dāng)RRH發(fā)射功率和子載波數(shù)量受限時(shí)，可以通過(guò)部署更多的RRH來(lái)提高系統(tǒng)的吞吐量。

圖9 系統(tǒng)吞吐量和RRH發(fā)射功率的關(guān)系

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

本文在C-RAN網(wǎng)絡(luò)下行鏈路場(chǎng)景下針對(duì)動(dòng)態(tài)無(wú)線資源分配提出了基于QoS約束分配方案，將時(shí)延隊(duì)列用M/G/1型排隊(duì)系統(tǒng)串聯(lián)在一起進(jìn)行研究，運(yùn)用改進(jìn)的遺傳算法，聯(lián)合考慮了對(duì)RRH選擇、子載波和RRH發(fā)射功率的分配問(wèn)題。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文提出的動(dòng)態(tài)資源分配方案明顯提高了C-RAN系統(tǒng)的性能，緩解了最優(yōu)信道分配方案的饑餓現(xiàn)象。同時(shí)結(jié)果也表明，RRH數(shù)量是對(duì)系統(tǒng)吞吐量影響最大的一種無(wú)線資源。

本文分配方案對(duì)于較小的網(wǎng)絡(luò)規(guī)?？梢缘玫阶顑?yōu)解，網(wǎng)絡(luò)規(guī)模較大時(shí)，由于C-RAN網(wǎng)絡(luò)沒(méi)有接入智能電網(wǎng)，因此還需考慮整個(gè)網(wǎng)絡(luò)中的電能消耗以及支出成本等因素。此外，對(duì)于大規(guī)模用戶的C-RAN網(wǎng)絡(luò)場(chǎng)景有待進(jìn)一步的研究。