基于改進遺傳算法的C-RAN網絡動態無線資源分配*

徐東明，譚靜茹，關文博

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

0 引 言

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

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

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

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

1 系統模型與問題建立

1.1 系統傳輸模型

圖1 C-RAN系統架構

由于無線信道傳輸存在不穩定性，信息傳輸時的瞬時速率并不能總保持一個穩定值。為了提高算法的穩定性，本文在后續仿真中設定信道環境為完美信道狀態信息(Channel State Information,CSI)，在所有信息傳輸過程中速率為一均值。RRH與BBU池通過一個理想光纖鏈路進行連接，由于信號通過光纖傳輸時損耗很小，因此對所有傳輸鏈路來說，噪聲功率譜密度N0是相同的。

(1)

根據香農公式，用戶m的可達速率為

(2)

1.2 系統QoS約束

圖2 M/G/1型排隊系統

(3)

根據上述公式，當t→∞時，系統平均剩余服務時間為

(4)

當第m個用戶連接第k個RRH時，平均等待時間為

(5)

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

(6)

1.3 系統優化問題建立

在C-RAN網絡中，系統的吞吐量之和為

(7)

(8)

在一個時隙τ中，為了限制UEm與RRHk之間一一對應的映射關系，子載波分配應滿足

(9)

(10)

根據前文中提到的條件，目標函數可以表示為

(11)

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

2 算法設計

C-RAN網絡中無線資源的存在形式與種類多種多樣，如何將這些資源進行更加有效的分配，是一個具有不確定性和復雜性的問題。特別是在優化過程中，如何提高系統利用率、聯合考慮多重無線資源、克服信道條件以及無線傳輸的不穩定性，使用傳統的數學工具已經不能精準解決如上問題。

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

本文對遺傳算法進行改進，將RRH選擇、子載波分配、RRH功率分配同時優化，以達到原優化方案中最大化吞吐量的優化目標。

2.1 編碼與產生初始群體

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

2.2 適應度函數設計

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

(12)

2.3 選擇操作

在遺傳算法中，輪盤賭算子是一種常用的選擇方法，它的缺點是容易導致早熟現象，因此對選擇操作進行改進。

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

個體i被選擇的概率為

(13)

個體i的累計概率為

Oi=∑Pi。

(14)

式中：Fi為個體i的適應度值，Q為種群規模。

2.4 交叉操作

經典的交叉算法在交叉過程中容易產生局部極小，因此本文提出新的交叉算子。

首先對RRH選擇、子載波分配提出多點簡單交叉算子。算法首先產生一個長度為2M的屏蔽字，其中每個元素由等概率的0和1構成，前M個元素對應RRH選擇，第M+1～2M個元素對應子載波分配，當元素值為1時，相對應的兩個染色體的基因以交叉概率Pc進行交叉，為0時保持不變。對于功率分配提出多點非均勻算數交叉算子。首先產生一個長度為M的屏蔽字，其中每個元素由等概率的0和1組成并分別對應功率分配的每一個基因。當元素值為1時，兩個相對應點的父代基因值以交叉概率Pc進行交叉得到新的子代基因，為0時保持不變。該交叉算子產生新的子代染色體方法為

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

(15)

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

(16)

式中：r為[0,1]之內的均勻隨機數。

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

圖3 交叉操作

2.5 變異操作

在遺傳學中，變異指基因突變導致新染色體的產生和新性狀的獲得。常見的變異算子都有兩個不確定性：一方面，當前種群中擁有最高適應度值的基因可能會進行突變，從而破壞了目標函數的最優解；另一方面，當前種群中適應度值較低的一些基因可能不會做任何變異，從而不能改善種群的多樣性，并容易導致種群早熟。為此，提出新的變異操作。

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

(17)

圖4 變異操作

2.6 終止

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

改進的遺傳算法偽代碼如下：

Step1 產生初始群體

For(i=1 to MaxGeneration)do

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

Step2 計算適應度值

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 數值仿真與結果分析

3.1 仿真參數設計

為了驗證所提無線資源分配算法有效性，本節使用Matlab仿真平臺進行數值仿真，具體仿真參數[19-20]如表1所示。

表1 仿真參數

3.2 仿真結果分析

3.2.1 算法復雜度

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

圖5 算法時間復雜度對比

3.2.2 算法穩定性

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

圖6 系統吞吐量和種群演化代數的關系

3.2.3 吞吐量

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

圖7 系統吞吐量和RRH數量的關系

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

圖8 系統吞吐量和子載波數量的關系

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

圖9 系統吞吐量和RRH發射功率的關系

4 結束語

本文在C-RAN網絡下行鏈路場景下針對動態無線資源分配提出了基于QoS約束分配方案，將時延隊列用M/G/1型排隊系統串聯在一起進行研究，運用改進的遺傳算法，聯合考慮了對RRH選擇、子載波和RRH發射功率的分配問題。實驗結果驗證了本文提出的動態資源分配方案明顯提高了C-RAN系統的性能，緩解了最優信道分配方案的饑餓現象。同時結果也表明，RRH數量是對系統吞吐量影響最大的一種無線資源。

本文分配方案對于較小的網絡規模可以得到最優解，網絡規模較大時，由于C-RAN網絡沒有接入智能電網，因此還需考慮整個網絡中的電能消耗以及支出成本等因素。此外，對于大規模用戶的C-RAN網絡場景有待進一步的研究。