基于改進(jìn)匈牙利算法的導(dǎo)頻分配

孫文勝，胡青紅

(杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018)

0 引 言

隨著生活中人工智能的大量引入，移動(dòng)數(shù)據(jù)流量的需求迅速增長(zhǎng)。大規(guī)模多輸入多輸出(Multiple-Input Multiple-Output，MIMO)技術(shù)逐漸從理論概念發(fā)展為未來(lái)無(wú)線網(wǎng)絡(luò)的關(guān)鍵解決方案。大規(guī)模MIMO技術(shù)可按數(shù)量級(jí)提升蜂窩小區(qū)系統(tǒng)的頻譜效率，無(wú)需為獲取高數(shù)據(jù)傳輸速率在實(shí)際系統(tǒng)中部署更多的基站(Base Station, BS)[1]。在大規(guī)模MIMO系統(tǒng)中，每個(gè)BS都配備數(shù)百個(gè)有源天線陣列，提供前所未有的陣列增益和空間分辨率，每個(gè)小區(qū)的數(shù)十或數(shù)百個(gè)用戶(hù)設(shè)備(User Equipment, UE)進(jìn)行通信的同時(shí)，保持對(duì)用戶(hù)間干擾的魯棒性，大幅提升系統(tǒng)性能[2]。無(wú)線通信系統(tǒng)中，數(shù)據(jù)能否有效傳輸依賴(lài)上行鏈路和下行鏈路的信道狀態(tài)信息(Channel State Information, CSI)，因此，在大規(guī)模MIMO系統(tǒng)中，獲取準(zhǔn)確的CSI信息是實(shí)現(xiàn)高質(zhì)量通信的關(guān)鍵。在頻分雙工(Frequency Division Duplex, FDD)大規(guī)模MIMO環(huán)境中，信道互易性不再適用，這種情況下，如何獲取更多信道信息成為主要問(wèn)題[3]。時(shí)分雙工(Time Division Duplex, TDD)模式下的大規(guī)模MIMO系統(tǒng)中，相比小區(qū)總?cè)藬?shù)，系統(tǒng)可用的正交導(dǎo)頻資源數(shù)非常有限，如果為所有用戶(hù)分配正交導(dǎo)頻，隨著用戶(hù)數(shù)量的線性增加，系統(tǒng)將花費(fèi)很大的導(dǎo)頻開(kāi)銷(xiāo)[4]。為了減少導(dǎo)頻開(kāi)銷(xiāo)，實(shí)際應(yīng)用中，必然存在一些用戶(hù)使用相同導(dǎo)頻的情況，導(dǎo)致導(dǎo)頻污染[5]。為了減少信道估計(jì)誤差，提出了許多智能導(dǎo)頻分配方案，例如可調(diào)相移導(dǎo)頻(Adjustable Phase-Shift Pilot, APSP)算法可減少在寬帶大規(guī)模MIMO系統(tǒng)中的獲取信道狀態(tài)開(kāi)銷(xiāo)。文獻(xiàn)[6-7]采用以用戶(hù)為中心的聚類(lèi)方法來(lái)降低系統(tǒng)的計(jì)算復(fù)雜度，將系統(tǒng)環(huán)境作為一種分布式大規(guī)模MIMO，小區(qū)不存在邊界，允許用戶(hù)存在多個(gè)服務(wù)簇，每個(gè)用戶(hù)從附近的BS中選擇自己的服務(wù)簇，但是，基站獲取的CSI信息受到導(dǎo)頻復(fù)用的嚴(yán)重影響。文獻(xiàn)[8-9]通過(guò)設(shè)計(jì)導(dǎo)頻序列來(lái)減少大規(guī)模MIMO系統(tǒng)的導(dǎo)頻開(kāi)銷(xiāo)，但當(dāng)小區(qū)用戶(hù)數(shù)量龐大時(shí)，此類(lèi)方案計(jì)算復(fù)雜度急劇增大；文獻(xiàn)[10]結(jié)合貪婪算法與功率控制問(wèn)題對(duì)導(dǎo)頻分配問(wèn)題展開(kāi)研究，但沒(méi)有應(yīng)用大規(guī)模MIMO系統(tǒng)的多天線陣列特性。此外，文獻(xiàn)[11]提出的疊加訓(xùn)練序列設(shè)計(jì)的數(shù)據(jù)輔助信道估計(jì)和文獻(xiàn)[12]提出的基于奇異值分解(Singular Value Decomposition, SVD)的盲信道估計(jì)算法，可用以獲取準(zhǔn)確CSI信息，但當(dāng)應(yīng)用于密集小區(qū)時(shí)，這兩類(lèi)方法的計(jì)算復(fù)雜性比較高。綜合上述主流導(dǎo)頻分配方案存在的弊端，本文結(jié)合小區(qū)用戶(hù)分布特點(diǎn)和導(dǎo)頻分配算法的計(jì)算復(fù)雜度，針對(duì)實(shí)際生活場(chǎng)景建模小區(qū)，制定了最大化MIMO系統(tǒng)的下行鏈路和速率的導(dǎo)頻分配優(yōu)化問(wèn)題。

1 系統(tǒng)模型

圖1 多小區(qū)用戶(hù)的上行鏈路干擾模型系統(tǒng)

假設(shè)TDD模式下的蜂窩大規(guī)模MIMO系統(tǒng)存在L個(gè)小區(qū)，所有小區(qū)的范圍大小相同并共享相同的時(shí)頻資源。小區(qū)半徑為R，BS位于小區(qū)中心，每個(gè)BS配有M根天線，每個(gè)小區(qū)中隨機(jī)非均勻分布K個(gè)單天線用戶(hù)，其系統(tǒng)模型如圖1所示，圖1中，實(shí)線表示BS的期望信號(hào)，虛線表示小區(qū)間的干擾信號(hào)。

在TDD模式下，上行鏈路中用戶(hù)向基站發(fā)送導(dǎo)頻序列，基站根據(jù)導(dǎo)頻序列獲取上行鏈路的信道狀態(tài)信息CSI，并根據(jù)信道互易性獲得下行鏈路的CSI，最后完成數(shù)據(jù)的發(fā)送。

(1)

式中，zlk為l小區(qū)內(nèi)用戶(hù)k的地理位置，zlk∈R2，滿(mǎn)足隨機(jī)分布；dj(zlk)為從BSj到小區(qū)l中的用戶(hù)k的信道方差；根據(jù)系統(tǒng)信道互易特性，第j個(gè)小區(qū)的BS處接收的導(dǎo)頻信號(hào)為：

(2)

式中，plk為在小區(qū)中分配給用戶(hù)k的導(dǎo)頻發(fā)射功率，n∈CM×τ為第j個(gè)BS處的加性噪聲，元素獨(dú)立分布為CN(0,δ2IM),δ2為噪聲方差。

根據(jù)接收信號(hào)yj，第j個(gè)小區(qū)的用戶(hù)k與第j個(gè)BS之間的最小二乘信道估計(jì)為：

(3)

(4)

式中，pd為上行鏈路數(shù)據(jù)的傳輸功率，xlk為第l個(gè)小區(qū)中的第k個(gè)用戶(hù)向第j個(gè)基站發(fā)送的數(shù)據(jù)信號(hào)，滿(mǎn)足E[|xlk|]=1，Wj為信道噪聲，滿(mǎn)足CN(0,δ2IM)。

式(3)表示利用已知導(dǎo)頻序列獲取的信道估計(jì)值，由式(4)可知，在數(shù)據(jù)傳輸?shù)南滦墟溌分?，接收端?yīng)用匹配濾波器(Matched Filter, MF)檢測(cè)算法得到第j個(gè)小區(qū)k用戶(hù)的接收信號(hào)表示為：

(5)

(6)

根據(jù)式(3)—(5)，可求得第j個(gè)小區(qū)中第k個(gè)終端的下行鏈路信號(hào)干擾和噪聲比(Signal to Interference plus Noise Ratio, SINR)，表示為：

(7)

因此，下行鏈路第j個(gè)小區(qū)用戶(hù)k可達(dá)和速率可以表示為：

(8)

式中，W表示總帶寬，γ表示下行鏈路數(shù)據(jù)傳輸引起的頻譜效率損失。

2 導(dǎo)頻分配優(yōu)化問(wèn)題制定

考慮到系統(tǒng)導(dǎo)頻污染和系統(tǒng)下行可達(dá)和速率緊密相關(guān)，本文制定了與導(dǎo)頻分配相關(guān)的優(yōu)化問(wèn)題，如下所示：

(9)

式中，{μ}為所有小區(qū)可能的導(dǎo)頻分配方法，θ(j,k)∈{φ1,φ2,…,φK}為第j個(gè)小區(qū)用戶(hù)k的導(dǎo)頻序列，式(9)最直接的方法就是采用窮舉法，并且能通過(guò)窮舉法獲得最佳導(dǎo)頻分配方案，但是，采用這種方法意味著必須嘗試所有可能的分配方法，并且隨著小區(qū)人數(shù)的增加，窮舉搜索帶來(lái)的計(jì)算復(fù)雜度呈指數(shù)增長(zhǎng)，顯然窮舉搜索不可行。

為了降低計(jì)算復(fù)雜度，本文對(duì)上述問(wèn)題進(jìn)行簡(jiǎn)化，將L個(gè)小區(qū)的導(dǎo)頻分配分解成L個(gè)子問(wèn)題，子問(wèn)題復(fù)雜度遠(yuǎn)遠(yuǎn)小于O(K!)，總復(fù)雜度小于O(L×K!)；應(yīng)用對(duì)應(yīng)算法經(jīng)過(guò)多次迭代解決每個(gè)子問(wèn)題，同時(shí)需要預(yù)先固定其它L-1個(gè)小區(qū)的導(dǎo)頻分配，通過(guò)優(yōu)化當(dāng)前小區(qū)的導(dǎo)頻分配，最后達(dá)到最佳分配。因此，得到如下子問(wèn)題：

(10)

式中，θj為當(dāng)前對(duì)第j個(gè)小區(qū)正進(jìn)行分配的導(dǎo)頻序列，θ-j為除小區(qū)j外的其它小區(qū)已提前隨機(jī)分配導(dǎo)頻序列，R′為當(dāng)前所有小區(qū)的下行可達(dá)和速率。因此，對(duì)于式(10)，開(kāi)始時(shí)除特定小區(qū)外，其它小區(qū)的采用導(dǎo)頻資源隨機(jī)分配，預(yù)先確定其它小區(qū)的導(dǎo)頻分配矩陣，隨后針對(duì)特定小區(qū)的導(dǎo)頻進(jìn)行最優(yōu)分配。

式(10)表示的導(dǎo)頻分配策略在分解前后并沒(méi)有利用小區(qū)用戶(hù)位置的特點(diǎn)；獲取最佳導(dǎo)頻分配需要在一定的條件下最小化導(dǎo)頻復(fù)用的影響，由式(4)和式(5)可知，相比于目標(biāo)小區(qū)用戶(hù)的信號(hào)強(qiáng)度，其它小區(qū)用戶(hù)的干擾強(qiáng)度不可忽略時(shí)，目標(biāo)小區(qū)接收其它小區(qū)的導(dǎo)頻信號(hào)，由于不同小區(qū)使用同一組正交導(dǎo)頻，此時(shí)不同小區(qū)間產(chǎn)生導(dǎo)頻復(fù)用。

3 導(dǎo)頻分配算法

本文對(duì)小區(qū)用戶(hù)進(jìn)行分類(lèi)，分為第Ⅰ類(lèi)用戶(hù)和第Ⅱ類(lèi)用戶(hù)。目前許多文獻(xiàn)關(guān)于用戶(hù)分類(lèi)都是基于用戶(hù)空間位置信息對(duì)用戶(hù)進(jìn)行分類(lèi)，優(yōu)化導(dǎo)頻分配方案即最大程度減小信道估計(jì)誤差，對(duì)此，本文定義一個(gè)信道誤差度量因子(Channel Error Metric，CEM)[13]：

(11)

其期望值可表示為：

Δjk=E{Δjk}

(12)

式(11)表示任何相干時(shí)間信道估計(jì)誤差與真實(shí)信道之間的瞬時(shí)變化值，式(12)代表某特定時(shí)間內(nèi)的相對(duì)變化穩(wěn)定值，針對(duì)具有多根天線的用戶(hù)小區(qū)，基于最小均方誤差(Minimum Mean Square Error, MMSE)估計(jì)算法的信道誤差度量因子的閉式表達(dá)式如下：

(13)

式中，plk為導(dǎo)頻發(fā)送功率，βjlk為系統(tǒng)的大尺度衰落系數(shù)；并且，當(dāng)基站天線數(shù)M→∞，進(jìn)一步精確表達(dá)式(13)為：

(14)

在實(shí)際應(yīng)用中，雖然小區(qū)用戶(hù)數(shù)量龐大，但是受到嚴(yán)重導(dǎo)頻污染影響的用戶(hù)相對(duì)較少，K′?K，因此本文對(duì)第Ⅰ類(lèi)用戶(hù)采用窮舉搜索法，找出Ⅰ類(lèi)用戶(hù)的最佳導(dǎo)頻分配。多小區(qū)用戶(hù)分類(lèi)算法與第Ⅰ類(lèi)用戶(hù)導(dǎo)頻分配算法實(shí)現(xiàn)如下。

初始化：輸入閾值γ，小區(qū)數(shù)L，用戶(hù)數(shù)量K，用戶(hù)導(dǎo)頻功率pjk

步驟1：forj= 1∶L

①初始化信道各項(xiàng)參數(shù)γ，L，K，pjk

②根據(jù)公式(2)計(jì)算目標(biāo)基站j接收到的導(dǎo)頻信號(hào)yj

③為獲取高精度的信道估計(jì)值，將對(duì)式(3)采用最小均方誤差準(zhǔn)則進(jìn)行信道估計(jì)，得到各用戶(hù)的信道估計(jì)矩陣

(15)

⑤用戶(hù)分類(lèi)：

fori=1∶K

End

用戶(hù)的start[j]經(jīng)過(guò)降序排列，最后得到descend[j]

⑥根據(jù)提前設(shè)定的合適閾值γ，對(duì)排序后的CEM對(duì)應(yīng)的用戶(hù)進(jìn)行分類(lèi)，低于γ的用戶(hù)歸為第Ⅰ類(lèi)用戶(hù)，并存于 ClassⅠ[j]，否則為第Ⅱ類(lèi)用戶(hù)，對(duì)應(yīng)用戶(hù)存于ClassⅡ[j]

End

步驟2：求出每個(gè)小區(qū)的ClassⅠ[j]中元素?cái)?shù)量的最大值，得到K′。

(16)

其中

(17)

本文將一對(duì)一匹配問(wèn)題轉(zhuǎn)換成上述問(wèn)題的解決形式，針對(duì)每個(gè)子問(wèn)題通過(guò)應(yīng)用改進(jìn)匈牙利算法獲得最佳導(dǎo)頻分配。隨后，移動(dòng)到下一小區(qū)并使用相同的方法來(lái)優(yōu)化下一個(gè)子問(wèn)題的導(dǎo)頻分配。第Ⅱ類(lèi)用戶(hù)采用的改進(jìn)匈牙利導(dǎo)頻分配算法實(shí)現(xiàn)如下。

初始化：輸入小區(qū)數(shù)量L，導(dǎo)頻數(shù)=用戶(hù)數(shù)K，迭代容忍閾值ε，迭代索引t=1，小區(qū)索引j=1

步驟1：根據(jù)小區(qū)數(shù)量和小區(qū)用戶(hù)數(shù)構(gòu)建當(dāng)前小區(qū)模型

步驟2：獲取各小區(qū)Ⅰ類(lèi)用戶(hù)的導(dǎo)頻分配結(jié)果，提前固定Ⅰ類(lèi)用戶(hù)的導(dǎo)頻序列

步驟3：接下來(lái)對(duì)各小區(qū)剩余的正交導(dǎo)頻數(shù)進(jìn)行分配，采用匈牙利算法獲取當(dāng)前第j個(gè)小區(qū)的最佳導(dǎo)頻分配結(jié)果θj，獲取此時(shí)所有小區(qū)的導(dǎo)頻分配結(jié)果μt

步驟5：如果R{μt+1}-R{μt}<ε,則重復(fù)步驟3—5

步驟6：結(jié)束分配，獲取導(dǎo)頻分配結(jié)果μt

在解決每個(gè)子問(wèn)題(迭代)時(shí)，根據(jù)匈牙利算法獲得導(dǎo)頻分配，并且在該優(yōu)化(迭代)中使系統(tǒng)的總和率最大化。因此，式(16)的目標(biāo)在每次迭代中增加直到收斂。

從計(jì)算復(fù)雜度方面對(duì)算法性能進(jìn)行分析，從兩個(gè)方面對(duì)算法復(fù)雜度進(jìn)行分析。

(1)用戶(hù)分類(lèi)。根據(jù)信道特點(diǎn)，對(duì)信道誤差進(jìn)行分析，需要遍歷各個(gè)小區(qū)的用戶(hù)數(shù)，因此，需要付出的計(jì)算量為O(LK)。

4 仿真實(shí)驗(yàn)與分析

假設(shè)小區(qū)單元半徑R=750 m，每個(gè)BS配備有M個(gè)天線，基站位于小區(qū)中心，仿真參數(shù)如表1所示，根據(jù)蜂窩小區(qū)位置、用戶(hù)位置隨機(jī)特點(diǎn)以及小區(qū)用戶(hù)參數(shù)構(gòu)建的小區(qū)模型如圖2所示。

分別采用傳統(tǒng)隨機(jī)導(dǎo)頻分配、文獻(xiàn)[14]的導(dǎo)頻分配方法和本文提出的改進(jìn)匈牙利方法得到的系統(tǒng)下行鏈路平均SINR累積概率分布(Cumulative Distribution Function, CDF)曲線如圖3所示?？梢钥闯觯弘S著天線數(shù)量的增加，下行鏈路的SINR得到改善，基站天線的數(shù)量由32增加到158時(shí)，下行鏈路的SINR提高了近7 dB。天線數(shù)目為158時(shí)，對(duì)比傳統(tǒng)隨機(jī)分配方案，文獻(xiàn)[14]方法的下行鏈路的SINR提升近2 dB，相比于文獻(xiàn)[14]方法，本文提出的改進(jìn)匈牙利算法提升了近1.5 dB，說(shuō)明本文提出的方案改善了導(dǎo)頻復(fù)用帶來(lái)的影響。

表1 多小區(qū)用戶(hù)模型仿真參數(shù)

仿真參數(shù)取值小區(qū)數(shù)L小區(qū)半徑R/m基站天線數(shù)M小區(qū)用戶(hù)數(shù)導(dǎo)頻長(zhǎng)度信噪比/dB上行導(dǎo)頻功率/dBm陰影衰落因子/dB路徑損耗指數(shù)帶寬/MHz775020

圖2 多小區(qū)用戶(hù)模型

分別采用傳統(tǒng)隨機(jī)導(dǎo)頻分配、文獻(xiàn)[14]的導(dǎo)頻分配方法、文獻(xiàn)[15]的導(dǎo)頻分配方法和本文提出的改進(jìn)匈牙利方法對(duì)系統(tǒng)小區(qū)的下行鏈路平均和速率與基站天線數(shù)M的關(guān)系進(jìn)行仿真，結(jié)果如圖4所示?？梢钥闯觯寒?dāng)M>50時(shí)，考慮系統(tǒng)導(dǎo)頻資源有限，相比于傳統(tǒng)方案，文獻(xiàn)[14]和文獻(xiàn)[15]方法的平均可達(dá)和速率提升了約0.25 dB和0.35 dB，相比于文獻(xiàn)[15]方法，本文提出的改進(jìn)匈牙利算法提升了近0.2 dB。

圖3 下行鏈路平均SINR累計(jì)概率分布

圖4 下行鏈路平均和速率與基站天線數(shù)的關(guān)系

采用傳統(tǒng)隨機(jī)導(dǎo)頻分配、文獻(xiàn)[14]的導(dǎo)頻分配方法、文獻(xiàn)[15]的導(dǎo)頻分配方法和本文提出的改進(jìn)匈牙利方法得到的下行鏈路和速率隨上行鏈路功率變化曲線如圖5所示?？梢钥闯觯寒?dāng)下行發(fā)送功率小于-15 dB時(shí)，4種導(dǎo)頻分配方案的下行鏈路平均和速率無(wú)明顯差異；發(fā)送功率大于-10 dB后，隨著發(fā)送功率的增加，4種導(dǎo)頻分配方案的下行鏈路平均和速率均增大，本文算法的提升最明顯；發(fā)送功率大于10 dB時(shí)，4種導(dǎo)頻方案的下行鏈路平均和速率變化均趨于平穩(wěn)。

考慮導(dǎo)頻資源有限情形，圖6對(duì)上行鏈路發(fā)送功率與下行鏈路平均和速率關(guān)系進(jìn)行仿真。可以看出：當(dāng)上行鏈路發(fā)送功率小于-20 dB時(shí)，4種導(dǎo)頻分配方案平均和速率曲線接近重合，且系統(tǒng)下行鏈路平均和速率隨著發(fā)送功率的增大而增大；當(dāng)發(fā)送功率大于-15 dB且小于5 dB時(shí)，系統(tǒng)下行鏈路平均和速率隨著發(fā)送功率的增大而增大，與傳統(tǒng)方案相比，文獻(xiàn)[14]和文獻(xiàn)[15]方法分別提高了0.2 dB和0.35 dB，相比文獻(xiàn)[14]和文獻(xiàn)[15]方法，本文提出的改進(jìn)匈牙利算法分別提升了近0.3 dB和0.1 dB；當(dāng)發(fā)送功率大于5 dB時(shí)，4種導(dǎo)頻方法的平均和速率均趨于平穩(wěn)。

圖5 下行鏈路平均和速率與下行鏈路發(fā)送功率的關(guān)系

圖6 下行鏈路平均和速率與上行鏈路發(fā)送功率的關(guān)系

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

為了減少導(dǎo)頻污染帶來(lái)的影響，本文將存在嚴(yán)重導(dǎo)頻污染的用戶(hù)進(jìn)行分類(lèi)，針對(duì)兩類(lèi)用戶(hù)在數(shù)量上的特點(diǎn)，采用一種低復(fù)雜度的改進(jìn)匈牙利導(dǎo)頻分配方案，對(duì)Ⅰ類(lèi)用戶(hù)采用窮舉搜索法，為Ⅱ類(lèi)用戶(hù)制定導(dǎo)頻分配優(yōu)化問(wèn)題。改進(jìn)算法提高了系統(tǒng)下行鏈路可達(dá)和速率，性能表現(xiàn)良好，能以較低的計(jì)算量準(zhǔn)確獲取信道狀態(tài)特性。下一步將從導(dǎo)頻序列設(shè)計(jì)出發(fā)，進(jìn)一步減輕系統(tǒng)導(dǎo)頻污染。