基于改進(jìn)離散布谷鳥搜索算法的毫米波大規(guī)模MIMO系統(tǒng)波束選擇

汪 銀，張紅偉，李曉輝

（安徽大學(xué)電子信息工程學(xué)院，合肥，230039）

引 言

隨著互聯(lián)網(wǎng)業(yè)務(wù)的迅速發(fā)展，人們對無線網(wǎng)絡(luò)各個應(yīng)用領(lǐng)域的需求日益增多，日益緊張的頻譜資源已經(jīng)無法滿足人們對通信的需求。毫米波大規(guī)模輸入輸出能通過更寬的信號帶寬實現(xiàn)更高的數(shù)據(jù)速率以及更高的頻譜效率，被認(rèn)為是未來5G無線通信的關(guān)鍵技術(shù)[1-2]。毫米波無線通信與新興的大規(guī)模多天線和大規(guī)模協(xié)作無線傳輸技術(shù)緊密結(jié)合，可以解決毫米波移動通信的廣域大容量無線覆蓋和支持終端中高速移動等關(guān)鍵性技術(shù)的瓶頸[3]，毫米波混合波束成形技術(shù)也是如今研究的熱點之一[4]。

傳統(tǒng)的全數(shù)字波束成形方案要求每個天線對應(yīng)一條獨立的射頻(Radio frequency,RF)鏈路[5]，隨著基站天線數(shù)和小區(qū)用戶數(shù)的不斷增加，所需的RF鏈路數(shù)量也在不斷上升，雖然性能優(yōu)異，但是增加了硬件成本以及實現(xiàn)難度。為了減少所需RF鏈路的數(shù)量，Shu等提出低復(fù)雜度基于相位對準(zhǔn)的DOA估計方法。文獻(xiàn)[7]提出混合大規(guī)模多輸入多輸出(Multiple input multiple output,MIMO)中基于數(shù)字域改進(jìn)的bat算法（I-BA）和魯棒自適應(yīng)波束形成器（RAB）方法。文獻(xiàn)[8]提出一種有效減少干擾的混合模擬和數(shù)字接收波束成形方案。Brady等提出了波束空間MIMO這一開創(chuàng)性的概念。通過采用性能損失忽略不計的離散透鏡陣列(Discrete lens array,DLA)，將傳統(tǒng)的空間信道轉(zhuǎn)換為波束空間信道，以獲得毫米波(Millimeter wave,mmWave)頻率下的信道稀疏度。由于波束空間MIMO信道具有稀疏性，只需選擇少量合適的天線就能減少RF鏈路數(shù)，并且不會造成明顯的系統(tǒng)性能損失?，F(xiàn)有文獻(xiàn)提出兩種波束選擇方法：選擇消除導(dǎo)致容量損失最小的波束，或者選擇在系統(tǒng)容量方面貢獻(xiàn)最大的波束[10]，但是這種依次搜索的波束選擇方法復(fù)雜度過高。文獻(xiàn)[11]中提出通過最大幅度(Magnitude maximization,MM)或基于閾值的幅度來選擇波束，這種基于最大幅度的波束選擇方案雖然簡單，但是卻存在著多用戶干擾以及不同的RF鏈選擇相同的波束而導(dǎo)致RF鏈被浪費的問題。在文獻(xiàn)[12]中提出一種干擾感知(Interference-aware,IA)波束選擇方案，該方案為干擾用戶重新選擇波束。文獻(xiàn)[13]中提出基于蟻群優(yōu)化(Ant colony optimization,ACO)的方案，但是該方案和IA方案類似，都是基于幅度最大化的標(biāo)準(zhǔn)，而不是直接優(yōu)化和速率。文獻(xiàn)[14]提出根據(jù)和速率來分析選擇波束的方案，但該方案要求具有特定的概率分布的信道。

針對上述問題，提出了一種新的波束選擇方案。該方案將波束選擇問題看作求解{0-1}背包問題[15]，將選擇的波束看作選中物品裝入背包，將系統(tǒng)的最大和速率看作求解背包所裝的最大容量問題，采用改進(jìn)離散布谷鳥搜索算法來獲得近優(yōu)解，針對布谷鳥算法Levy飛行離散化結(jié)果中產(chǎn)生的非正常編碼，采用啟發(fā)式貪婪算法進(jìn)行修復(fù)。仿真和理論分析結(jié)果表明，所提出的波束選擇方案在提高系統(tǒng)總和率方面優(yōu)于現(xiàn)有的波束選擇方案。

1 系統(tǒng)模型

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

考慮一個毫米波大規(guī)模MIMO單小區(qū)系統(tǒng)，假設(shè)基站端配備天線數(shù)為N，RF鏈路數(shù)為NRF?；就瑫r服務(wù)K個單天線用戶。其系統(tǒng)模型如圖1所示。

由圖1可知，傳統(tǒng)MIMO模型所需的RF鏈路數(shù)與天線數(shù)相等，即N=NRF。對于在基站處具有線性預(yù)編碼的傳統(tǒng)多用戶MIMO系統(tǒng)的下行鏈路，K個用戶所接收到的信號y可表示為

式中：H=[h1,h2,…,hK]為信道矩陣，且k=1,…,K,hk是大小為N×1的用戶k與基站之間的信道矢量；s為原始信號矢量，s∈CK×1，其歸一化功率為E(ssH)=IK；W是大小為N×K的預(yù)編碼矩陣，并且滿足tr(WWH)≤ρ，ρ為發(fā)射總功率；n是大小為K×1的加性高斯白噪聲，且n～CN(0,σ2IK)。

圖1 傳統(tǒng)MIMO系統(tǒng)模型Fig.1 Traditional MIMO system model

采用毫米波通信廣泛使用的Saleh-Valenzuela信道模型，用戶k的信道矢量為

式中：α(ψ)為陣列響應(yīng)矢量分別為用戶k的視距(Line-of-sight,LoS)路徑組成以及非視距(Non-line-of sight,NLoS)路徑組成；βk為復(fù)增益；ψk為空間方位。

1.2 波束空間MIMO系統(tǒng)模型

由于傳統(tǒng)MIMO模型所需的RF鏈路數(shù)與天線數(shù)相等，隨著天線數(shù)量增加，系統(tǒng)所需RF鏈路數(shù)也增加。為減少RF鏈路數(shù)，本文采用DLA，通過空間傅里葉變換矩陣U將傳統(tǒng)的空間信道轉(zhuǎn)換為波束空間信道，其系統(tǒng)模型如圖2所示。

圖2 波束域MIMO系統(tǒng)模型Fig.2 Beamspace MIMO system model

U為一組給定的正交基

式中為波束空間信道，且被定義為

2 波束選擇方案

2.1 問題闡述

在不造成明顯性能損失的前提下從N個天線中挑選出K個天線，需要對其建立目標(biāo)函數(shù)以及約束條件。由于是在模擬域進(jìn)行波束選擇，采用迫零波束(Zero-foring,ZF)預(yù)編碼，可表示為

式中:α為縮放因子且滿足為發(fā)射總功率。

假設(shè)在基站端給每個用戶分配相等的功率，則第k個用戶可實現(xiàn)的平均速率為

式中σ2為噪聲功率。

進(jìn)一步將波束選擇問題轉(zhuǎn)換為下述優(yōu)化問題

式(9)為目標(biāo)函數(shù)，表示在約束條件下最大化系統(tǒng)和速率；式(10)表示每個用戶只選擇一個波束；式(11)表示每個波束最多被一個用戶選擇，也有可能沒被任何用戶選中；式(12)表示xnk的取值范圍為0或者1，0表示該天線未被選中，1表示該天線被選中。

從N中挑選K個最合適的天線最優(yōu)方案是窮搜索方案，但是其計算量能達(dá)到種組合，因此尋求近優(yōu)的波束選擇方案很重要。

2.2 離散布谷鳥算法

布谷鳥搜索(Cuckoo search,CS)算法是在2009年由英國學(xué)者Yang和Deb在群體智能技術(shù)基礎(chǔ)上提出的一種新型基于自然元的啟發(fā)式算法[16]，該算法具有全局搜索能力強(qiáng)、選用參數(shù)少、魯棒性強(qiáng)等優(yōu)點。但是最初的布谷鳥算法只適用于求解連續(xù)值，不適應(yīng)于離散值，Ouyang等[17]提出了離散布谷鳥搜索算法用以解決離散型問題。針對2.1節(jié)所提出的波束選擇模型優(yōu)化問題，提出將波束選擇問題看作求解{0-1}背包問題，將選擇的波束看作將物品裝入背包，將系統(tǒng)的最大和速率看作背包所裝的最大容量問題，采用離散布谷鳥算法來求解式(9)的模型。CS算法基于以下3個假設(shè)：

(1)每只布谷鳥隨機(jī)選擇一個鳥巢并只產(chǎn)下一個布谷鳥蛋；

(2)最好的鳥巢將會被保留至下一代；

(3)鳥巢的數(shù)量是固定的，鳥巢中的布谷鳥蛋被宿主鳥發(fā)現(xiàn)的概率為Pa∈[0,1]。

采用Mantegna來模擬Levy飛行跳躍路徑的公式，Levy飛行的基本布谷鳥算法公式為

離散布谷鳥算法要求對Levy飛行每次位置更新的跳躍路徑進(jìn)行二進(jìn)制代碼變換。采用文獻(xiàn)[18]的Kennedy公式以及文獻(xiàn)[19]中提出的更新方法進(jìn)行二進(jìn)制編碼的混合更新方法[20]，二進(jìn)制編碼的變換公式為

式中：rand為產(chǎn)生的隨機(jī)數(shù)；pr為二進(jìn)制編碼控制參數(shù)且滿足pr∈[0,1]。pr越大，則離散布谷鳥算法的全局多樣性越強(qiáng)；pr越小，則離散布谷鳥算法的收斂性越強(qiáng)。

2.3 非正常編碼的修復(fù)處理

使用式(14)中Levy飛行更新的二進(jìn)制編碼方法在約束條件下很容易產(chǎn)生非正常編碼，例如第i次迭代第m個鳥巢里第k個用戶選擇不止一個波束。為了保證均為可行解，必須采用一定的編碼修復(fù)策略，本文提出使用啟發(fā)式貪婪算法對非正常編碼進(jìn)行修復(fù)。先對Levy飛行更新過的編碼為1的項進(jìn)行求信道增益大小，第k個用戶選擇前k-1個沒有選擇的且信道增益值最大的波束，依次選擇，直到所有用戶都選擇了一個波束。該修復(fù)策略的算法如表1所示。

2.4 改進(jìn)離散布谷鳥算法描述

步驟1設(shè)置算法參數(shù)：鳥巢數(shù)M，鳥巢發(fā)現(xiàn)概率Pa，二進(jìn)制編碼控制參數(shù)pr，最大迭代次數(shù)Tmax，天線數(shù)N，用戶數(shù)K。先初始化M個鳥巢，每個鳥巢為用戶選擇信道幅度值最大且無重復(fù)的波束，如果出現(xiàn)多個用戶選擇重復(fù)的波束，則為這多個用戶從剩下的波束隨機(jī)選擇不重復(fù)的波束。計算M個鳥巢的適應(yīng)度大小，即計算式(9)的目標(biāo)函數(shù)，以當(dāng)前鳥巢適應(yīng)度最大的值為全局最優(yōu)解。

步驟2在上述給定的參數(shù)條件下，將Levy飛行的路徑按照式(14)對M個鳥巢進(jìn)行二進(jìn)制編碼混合更新，并采用啟發(fā)式貪婪算法對非正常編碼進(jìn)行修復(fù)。計算新產(chǎn)生M個鳥巢的適應(yīng)度，若比原鳥巢適應(yīng)度大則替換原來的鳥巢，若比原鳥巢適應(yīng)度小則丟棄。若當(dāng)前鳥巢適應(yīng)度比全局最優(yōu)解大，則以當(dāng)前鳥巢適應(yīng)度為全局最優(yōu)解。

步驟3用外來蛋的發(fā)現(xiàn)概率Pa與服從均勻分布的隨機(jī)數(shù)R∈[0,1]進(jìn)行比較，如果R＞Pa，則采用遺傳算法(GA)中復(fù)制的思想，復(fù)制全局最優(yōu)的鳥巢來替換被發(fā)現(xiàn)的鳥巢，從而能使最優(yōu)鳥巢保存下來，確定當(dāng)前最優(yōu)的鳥巢位置及最優(yōu)值。

步驟4判斷算法是否達(dá)到最大迭代次數(shù)Tmax，若達(dá)到則輸出全局最優(yōu)解，若未達(dá)到，則重復(fù)步驟2和步驟3。

表1 修復(fù)策略的算法Table 1 Algorithm for repair strategies

2.5 計算復(fù)雜度分析

將本文所提出方案的計算復(fù)雜度與MM方案和IA方案的計算復(fù)雜度進(jìn)行比較。由于在IA和所提出的算法中K×K維矩陣求逆均有最高的復(fù)雜度(O(K3))，因此通過計算執(zhí)行矩陣求逆的次數(shù)來比較它們的復(fù)雜度。MM方案是基于最大幅度的波束選擇方案，計算復(fù)雜度為0。IA算法的主要復(fù)雜度來自具有相同波束索引且幅度最大的干擾用戶重新選擇波束。假設(shè)有個干擾用戶，則第個用戶波束選擇有因此IA算法計算復(fù)雜度為本文算法計算復(fù)雜度主要體現(xiàn)在Levy飛行產(chǎn)生的新鳥巢與原始鳥巢計算對比上，與干擾用戶數(shù)無關(guān)，本文算法復(fù)雜度為TmaxM。

3 仿真結(jié)果與分析

考慮稀疏系統(tǒng)和密集系統(tǒng)兩種毫米波大規(guī)模MIMO系統(tǒng)，其中稀疏系統(tǒng)基站配備具有N=256個天線和K=32個用戶，密集系統(tǒng)BS配備天線數(shù)N=64和K=32個用戶，發(fā)射功率均采用ρ=32 mW，SNR=30 dB，鳥巢數(shù)M=20，Pa=0.75，pr=0.5。假設(shè)用戶k的空間信道有一個LoS分量以及有L=2個NLoS分量，其中遵循分布區(qū)間在的均勻分布。

先對本文所提算法的收斂度進(jìn)行分析。設(shè)置最大迭代次數(shù)Tmax=500。以天線數(shù)N=256，用戶數(shù)K=32為例，從圖3可以看出所提基于DCS波束選擇算法在迭代100次左右基本上已經(jīng)獲得了最大和速率，為了減少迭代次數(shù)，在后續(xù)仿真中均以Tmax=100。

圖4是在稀疏系統(tǒng)的條件下基于DCS波束選擇算法與全數(shù)字預(yù)編碼算法、IA算法以及MM算法進(jìn)行比較?？梢詮膱D4中看出，IA算法與每個用戶2個波束的MM-2波束選擇和速率性能基本上一致，比每個用戶1個波束的MM-1波束選擇和率性能好很多，這是因為MM-1方案不考慮用戶間的干擾，MM-2實現(xiàn)的和速率雖然提高不少但是造成更高的能量損耗?；贒CS波束選擇算法實現(xiàn)了比上述3種算法更好的和速率性能，也更接近全數(shù)字系統(tǒng)。

圖3 基于DCS波束選擇算法收斂曲線Fig.3 Convergence curve based on DCS beam selection algorithm

圖4 當(dāng)N=256,K=32時不同波束選擇算法所實現(xiàn)的和速率Fig.4 Sum-rate achieved by different beam selection algorithms（N=256,K=32）

圖5是在密集系統(tǒng)的條件下基于DCS波束選擇算法與已有的算法所實現(xiàn)和速率的比較。IA算法在密集系統(tǒng)中受干擾的概率，也就是在密集系統(tǒng)下一定會存在不同的用戶選擇相同的天線，受干擾的用戶數(shù)越多IA算法的復(fù)雜度越大?；贒CS波束選擇算法不用考慮用戶間的干擾，直接以優(yōu)化和速率為目標(biāo)，因此實現(xiàn)的和速率性能最好。如果用戶信道有高度相關(guān)性時就會很大，此時IA算法復(fù)雜度會很高，而本文算法復(fù)雜度與干擾用戶無關(guān)。

圖6是在SNR=30 dB，N=100的條件下不同用戶數(shù)和速率的對比。從圖中可看出，基于DCS波束選擇算法獲得最佳性能。

4 結(jié)束語

本文提出了一種新的波束選擇方案，所提方案將波束選擇看作求解{0-1}背包問題并采用DCS算法進(jìn)行求解，然而DCS算法在求解過程容易出現(xiàn)非正常編碼，提出采用啟發(fā)式貪婪算法對非正常解進(jìn)行修復(fù)，保證了計算所得的解均為可行解。最后借鑒遺傳算法中的復(fù)制思想，復(fù)制全局最優(yōu)的鳥巢來替換其中被發(fā)現(xiàn)的鳥巢，使最優(yōu)鳥巢保存下來，加快算法的收斂性。實驗仿真證明所提方案比已有算法能獲得更優(yōu)的和速率性能，雖然所提方案比已有算法計算復(fù)雜度略高一點，但是考慮當(dāng)今計算機(jī)計算性能提升較快，所提方案在實際系統(tǒng)的應(yīng)用中仍具有較大優(yōu)勢。

圖5 當(dāng)N=64,K=32時不同波束選擇算法所實現(xiàn)的和速率Fig.5 Sum-rate achieved by different beam selection algorithms（N=64，K=32）

圖6 不同用戶數(shù)下和速率的比較Fig.6 Sum-rate comparison of different numbers of users