基于簇級匈牙利與聯(lián)盟博弈聯(lián)合的CF mMIMO導(dǎo)頻分配算法*

譚景戈,毛翔宇,鄭建宏

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

0 引 言

無小區(qū)大規(guī)模MIMO(Cell-Free Massive Multiple-Input Multiple-Output,CF mMIMO)是一種無線網(wǎng)絡(luò)部署體系結(jié)構(gòu)[1],被認(rèn)為是6G和未來無線移動通信的核心技術(shù)之一,受到了越來越多研究者的關(guān)注。CF mMIMO系統(tǒng)中存在大量配備有單個或多個天線的接入點(diǎn)(Access Point,AP)分布在不同的地理位置,并通過回程鏈路連接到中央處理器(Central Processing Unit,CPU)。這些AP在相同的時頻資源上向所有用戶(User Equipment,UE)提供服務(wù)。該系統(tǒng)以“用戶為中心”,縮短了AP與用戶之間的平均距離,大幅降低了路徑損耗,使全區(qū)域信號均勻覆蓋,為無處不在的無線通信提供一致的服務(wù)質(zhì)量。

CF mMIMO系統(tǒng)采用時分雙工(Time Diversion Duplex,TDD)工作模式,因此,在上行訓(xùn)練階段通過導(dǎo)頻序列進(jìn)行信道估計(jì)獲得的信道狀態(tài)信息(Channel State Information,CSI)可用于下行鏈路,從而顯著節(jié)省無線資源。然而,由于正交導(dǎo)頻數(shù)量的限制,用戶間需要復(fù)用導(dǎo)頻,從而產(chǎn)生導(dǎo)頻污染,使系統(tǒng)性能受到嚴(yán)重影響。為了減輕導(dǎo)頻污染帶來的性能損失,文獻(xiàn)[1]提出了一種貪婪導(dǎo)頻分配算法,采用迭代的方法更新最低速率用戶的導(dǎo)頻;文獻(xiàn)[2]提出了一種改進(jìn)的貪婪導(dǎo)頻分配算法,利用位置信息分配導(dǎo)頻。然而與接近最優(yōu)的結(jié)果相比,這兩種算法有很大的性能差距。主要原因是貪婪算法是一種局部搜索方法,而這兩種算法未充分利用CF mMIMO系統(tǒng)的特性。文獻(xiàn)[3]提出了一種結(jié)構(gòu)化的導(dǎo)頻分配方案,從空間角度減輕了用戶復(fù)用導(dǎo)頻造成的導(dǎo)頻污染,但是用戶簇邊緣的用戶容易受到嚴(yán)重的導(dǎo)頻污染[4]。文獻(xiàn)[5]提出了一種基于禁忌搜索的導(dǎo)頻分配算法,通過創(chuàng)建禁忌列表避免導(dǎo)頻分配結(jié)果陷入局部最優(yōu)。文獻(xiàn)[6]提出了一種基于遺傳算法的導(dǎo)頻分配算法,利用生物進(jìn)化的思想不斷優(yōu)化導(dǎo)頻分配方案。文獻(xiàn)[7]利用經(jīng)典的匈牙利算法來解決導(dǎo)頻分配問題。該算法對用戶吞吐量有較大提升,優(yōu)于多種競爭方案,但由于該算法是在用戶級的基礎(chǔ)上迭代使用匈牙利算法,因此計(jì)算復(fù)雜度相當(dāng)大。同時該算法的收益矩陣只考慮了單個用戶的吞吐量,并沒有從全局出發(fā)考慮所有使用相同導(dǎo)頻用戶的吞吐量。文獻(xiàn)[8]提出了基于聯(lián)盟博弈的導(dǎo)頻分配方案,將使用相同導(dǎo)頻的用戶劃分為一個子聯(lián)盟,然后采用博弈的思想來改變用戶使用的導(dǎo)頻,以此優(yōu)化導(dǎo)頻分配方案。文獻(xiàn)[9]提出了一種基于用戶信道條件優(yōu)劣的導(dǎo)頻分配算法。該算法對mMIMO系統(tǒng)的性能有一定提升,但需要先采用一定的判斷策略得到每個用戶的信道條件。

鑒于此,本文提出一種基于簇級匈牙利與聯(lián)盟博弈聯(lián)合的導(dǎo)頻分配算法,從全局的角度對文獻(xiàn)[7]中匈牙利算法的收益矩陣進(jìn)行改進(jìn)。在此基礎(chǔ)上,利用聯(lián)盟博弈的思想避免因固定的導(dǎo)頻使用次數(shù)而帶來的性能上限。仿真結(jié)果表明,該導(dǎo)頻分配算法性能優(yōu)于多種典型導(dǎo)頻分配算法。

1 系統(tǒng)模型

本文考慮了一個CF mMIMO系統(tǒng),在其覆蓋范圍內(nèi)隨機(jī)分布M個配置單天線的AP和K個配置單天線的用戶,其中M?K,并假設(shè)所有AP都通過無損回程鏈路連接到CPU,如圖1所示。

圖1 CF mMIMO系統(tǒng)

M個AP在相同的時頻資源下為K個用戶提供服務(wù)。受大小尺度衰落的影響,信道可建模為

(1)

式中:gm,k,βmk,hmk分別表示第m個AP和第k個用戶之間的信道、大尺度衰落系數(shù)和小尺度衰落系數(shù)。

CF mMIMO系統(tǒng)幀結(jié)構(gòu)為上行訓(xùn)練、上行鏈路傳輸、下行鏈路傳輸,如圖2所示。用Tc、Bc和τc分別表示信道的相干時間、相干帶寬和相干間隔,滿足τc=Tc·Bc。在上行訓(xùn)練階段,AP根據(jù)已知的每個用戶發(fā)送的導(dǎo)頻序列估計(jì)與每個用戶間的CSI。設(shè)τp為上行訓(xùn)練階段的長度。當(dāng)τp>K時,可以將長度為τp的K個相互正交的導(dǎo)頻序列分配給K個用戶?？紤]到系統(tǒng)的頻譜效率,τp不能太大。因此,部分用戶會復(fù)用導(dǎo)頻序列。

圖2 系統(tǒng)幀結(jié)構(gòu)

1.1 上行訓(xùn)練階段

假設(shè)給用戶k分配的導(dǎo)頻序列為φk(||φk||2=1)且訓(xùn)練階段導(dǎo)頻均為全功率發(fā)送,則第m個AP接收到的信號可以表示為

(2)

式中:ρp表示導(dǎo)頻信號的歸一化信噪比;ωp,m～CN(0,1)是信道中的加性高斯白噪聲。

第m個AP根據(jù)接收導(dǎo)頻信號yp,m估計(jì)與每個用戶之間的信道系數(shù)gm,k,k=1,2,…,K。設(shè)yp,m在φk上的投影為

(3)

(4)

(5)

1.2 上行鏈路傳輸階段

(6)

式中:ρu表示歸一化上行鏈路信噪比。

(7)

第k個用戶上行鏈路吞吐量為

(8)

2 問題描述

從式(3)、(4)和(8)中可以看出,導(dǎo)頻分配在用戶的上行鏈路傳輸中起著重要作用,它決定了用戶的信道估計(jì)性能,從而決定了用戶的上行鏈路吞吐量。在本文中,我們的目標(biāo)是找到最佳的導(dǎo)頻分配方案,以便最大化用戶的吞吐量。與文獻(xiàn)[5]類似,該組合優(yōu)化問題可以表示為

(9)

式中:I=[I1,I2,…,IK],Ik∈φ,?k。

3 現(xiàn)有匈牙利導(dǎo)頻分配算法

文獻(xiàn)[7]中提出了一種基于匈牙利算法的導(dǎo)頻分配方案。該算法在每一步都涉及到一個適當(dāng)?shù)亩繄D定義,以便匈牙利算法可以用于執(zhí)行匹配。

現(xiàn)有匈牙利導(dǎo)頻分配算法(算法1)實(shí)現(xiàn)步驟如下:

輸入:K,M,τp,φ,最大迭代次數(shù)MIThung1

輸出:導(dǎo)頻分配結(jié)果I

1從φ中隨機(jī)選取導(dǎo)頻分配給每個用戶。

2 fori=1:MIThung1

3 fork=1:K

4 以用戶k為中心找出距離其最近的τp-1個用戶組成集合Sk,剩余用戶組成集合Tk。

5利用匈牙利算法重新為Sk中的用戶分配導(dǎo)頻。

6 end

7 if 算法收斂

8 break;

9 end

10 end

3.1 運(yùn)行匈牙利算法

(10)

3.2 收益矩陣元素的定義

(11)

(12)

4 基于簇級匈牙利與聯(lián)盟博弈聯(lián)合的導(dǎo)頻分配算法

4.1 簇級匈牙利算法

對匈牙利導(dǎo)頻分配算法的改進(jìn),主要在對待重分配導(dǎo)頻的用戶集Sk的重定義和收益矩陣A的重定義,從而降低復(fù)雜度并提高系統(tǒng)性能。與現(xiàn)有匈牙利導(dǎo)頻分配算法不同,我們先用K-mean聚類的方法對用戶進(jìn)行分簇,然后依次在每個簇內(nèi)利用匈牙利算法分配導(dǎo)頻。在定義收益矩陣元素時,不再只考慮被重分配導(dǎo)頻用戶的吞吐量,而是考慮所有使用此導(dǎo)頻用戶的吞吐量之和。

4.1.1 用戶集Sk的重定義

由于用戶和AP在空間上隨機(jī)分布在CF mMIMO系統(tǒng)中,因此距離用戶通信范圍內(nèi)的多個相鄰AP具有不可忽略的信道增益[10]?；诖?先利用K-mean算法將距離較近的用戶歸為一個簇并給簇內(nèi)用戶分配相互正交的導(dǎo)頻序列。

K-mean聚類算法(算法2)實(shí)現(xiàn)步驟如下:

輸入:K,τp,MITk-mean,用戶位置矢量U,收斂判決參數(shù)ε

1在覆蓋范圍內(nèi)隨機(jī)生成V(V=K/τp)個用戶簇質(zhì)心C=[C1,C2,…,CV]。

2 fori=1:MITK_mean

3 計(jì)算每個用戶與所有質(zhì)心間距離矢量dk。

4根據(jù)dk以就近原則讓用戶選擇用戶簇v并采用競爭機(jī)制使每個簇中用戶不會超過τp個。

7 break;

8 end

9 end

10所有用戶簇復(fù)用同一套導(dǎo)頻序列,同一簇中用戶使用相互正交的導(dǎo)頻序列。

在用戶分簇結(jié)束之后,就可將第v個用戶簇v中的用戶設(shè)為用戶集Sv,而其余K/τp-1個用戶簇中的用戶設(shè)為Tv,然后利用匈牙利算法為Sv中的用戶分配相互正交的導(dǎo)頻序列,這樣在每次的迭代中可以減少τp倍匈牙利算法的使用。

4.1.2 收益矩陣元素的重定義

文獻(xiàn)[7]中的匈牙利導(dǎo)頻分配算法對收益矩陣元素的定義僅考慮了Sk中單個用戶的吞吐量。事實(shí)上,當(dāng)Sk中使用第q個導(dǎo)頻序列的用戶不同時,對Tk中使用此導(dǎo)頻的K/τp-1個用戶的吞吐量會有不同程度的影響,所以將整個系統(tǒng)中所有使用第q個導(dǎo)頻用戶的吞吐量之和作為收益矩陣元素會更有利于目標(biāo)函數(shù)最大化。因此,重定義收益矩陣元素如下:

(13)

根據(jù)重定義的收益矩陣,利用匈牙利算法迭代地為每個用戶簇中的用戶分配導(dǎo)頻直到系統(tǒng)總吞吐量收斂。

4.2 聯(lián)盟博弈

由于用戶聚類時每個簇的用戶個數(shù)是均分的,且簇級匈牙利算法并不會改變使用某個導(dǎo)頻的用戶數(shù),固定的導(dǎo)頻使用次數(shù)會帶來一定的性能上限,所以本文采用聯(lián)盟博弈的思想優(yōu)化經(jīng)過簇級匈牙利算法之后的導(dǎo)頻分配。它類似于窮舉搜索,然而如果已經(jīng)有了一個較好的導(dǎo)頻分配方案,那么聯(lián)盟博弈算法將具有更低的復(fù)雜度。簡單來說,如果已經(jīng)有一個最優(yōu)方案,那么聯(lián)盟博弈算法將迭代一次后結(jié)束。

4.2.1 聯(lián)盟結(jié)構(gòu)和效用函數(shù)的定義

將K個用戶劃分入τp個不相交的子聯(lián)盟,聯(lián)盟結(jié)構(gòu)N={N1,N2,…,Nτp}表示聯(lián)盟的劃分形式。整個聯(lián)盟結(jié)構(gòu)的劃分需要滿足如下要求:使用相同導(dǎo)頻序列的用戶劃分入同一子聯(lián)盟,且同一子聯(lián)盟中的所有用戶使用的導(dǎo)頻序列相同。

可以將系統(tǒng)中用戶的總吞吐量看作當(dāng)前聯(lián)盟結(jié)構(gòu)的效用函數(shù),這樣聯(lián)盟博弈可提升總吞吐量。

4.2.2 聯(lián)盟博弈調(diào)整規(guī)則

本文借鑒文獻(xiàn)[11]在聯(lián)盟博弈論中的調(diào)整規(guī)則,即每個參與者的行為遵循增加所有用戶的效用函數(shù)之和。為了讓每個用戶受益,聯(lián)盟結(jié)構(gòu)需要不斷調(diào)整直到最終穩(wěn)定。

(14)

從定義1可以看出,任何想要加入另一個子聯(lián)盟的用戶都不會損害所有用戶的平均利益。

根據(jù)上述討論,本文所提的基于簇級匈牙利與聯(lián)盟博弈聯(lián)合的導(dǎo)頻分配算法(算法3)實(shí)現(xiàn)步驟如下:

輸入:K,M,τp,U,MITk-mean,MIThung2,MITcoal2,ε

輸出:聯(lián)盟結(jié)構(gòu)N

1根據(jù)算法2對用戶進(jìn)行分簇并初始化導(dǎo)頻分配。

2 fori=1:MIThung2

3 fori=1:K/τp

4 利用匈牙利算法對第i個用戶簇中的用戶分配導(dǎo)頻。

5 end

6 if 算法收斂

7 break;

8 end

9 end

10形成聯(lián)盟結(jié)構(gòu)N={N1,N2,…,Nτp}。

11 fori=1:MITcoal2

12 fork=1:K

14 break;

15 end

16 end

17 if 聯(lián)盟結(jié)構(gòu)穩(wěn)定

18 break;

19 end

20 end

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

本文考慮的場景為在1 km×1 km的正方形面積上隨機(jī)分布著M個單天線AP和K個單天線用戶。為了避免邊界效應(yīng),本文將上述通信區(qū)域與8個相同分布區(qū)域相鄰,以這種環(huán)繞技術(shù)來模擬具有無限區(qū)域的網(wǎng)絡(luò),并采用相關(guān)對數(shù)陰影衰落和三段路徑損耗對大尺度衰落系數(shù)進(jìn)行信道建模[1]。本文對上行鏈路數(shù)據(jù)的傳輸采用文獻(xiàn)[12]中分?jǐn)?shù)功率控制的方法以達(dá)到均衡用戶吞吐量的目的。具體仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

首先,將本文所提出的導(dǎo)頻分配算法(K-ImpHungarian-Coal)的性能與隨機(jī)(Rand)[1]、貪婪(Greedy)[1]、聚類(K-mean)[3]、遺傳(GA)[6]、匈牙利(Hungarian)[7]以及本文提出的簇級匈牙利(K-ImpHungarian)算法進(jìn)行比較,其中ImpHungarian表示只改進(jìn)了匈牙利算法中的收益矩陣。由于本文僅討論上行鏈路吞吐量,所以匈牙利算法中收益矩陣元素只考慮用戶的上行鏈路吞吐量。圖3給出了上述幾種算法上行鏈路吞吐量之和的累積分布函數(shù),可以看出本文提出的導(dǎo)頻分配算法性能優(yōu)于其他典型導(dǎo)頻分配算法。相較于Rand[1]、Greedy[1]、K-mean[3]、GA[6]算法,匈牙利類算法在系統(tǒng)總吞吐量上有較大提升。相較于現(xiàn)有匈牙利導(dǎo)頻分配算法,改進(jìn)了收益矩陣的匈牙利算法能夠得到更高的吞吐量,而其后聯(lián)盟博弈算法也使得吞吐量得到了進(jìn)一步的提升。從圖4可以看出,當(dāng)同時采用改進(jìn)收益矩陣的匈牙利算法時,基于簇級的匈牙利導(dǎo)頻分配算法性能也要略好于基于用戶級的方案。從圖4還能看出,將經(jīng)過K-ImpHungarian算法得到的導(dǎo)頻分配方案作為聯(lián)盟博弈(Coal)[8]算法的初始狀態(tài)有助于Coal算法跳出局部最優(yōu)。

圖3 上行鏈路總吞吐量的累積分布函數(shù)(K=40,τp=8)

圖4 上行鏈路總吞吐量的累積分布函數(shù)(M=100,K=40,τp=8)

圖5和圖6給出了上述幾種算法在不同正交導(dǎo)頻數(shù)量下和不同用戶數(shù)量下95%用戶可達(dá)吞吐量,可以看出本文所提算法性能優(yōu)于其他典型算法,相較于Rand[1]、Greedy[1]、K-mean[3]、GA[6]、和Hungarian[7]算法,性能提升大約為85%,32%,28%,12%,11%。

圖5 不同正交導(dǎo)頻數(shù)量下的95%用戶可達(dá)吞吐量(M=100,K=40)

圖6 不同用戶數(shù)量下的95%用戶可達(dá)吞吐量(M=100,τp=40)

因?yàn)镽and算法相當(dāng)于直接分配導(dǎo)頻,其計(jì)算復(fù)雜度可以忽略不計(jì),所以表2只給出了其他各類算法的計(jì)算復(fù)雜度,其中,O1表示計(jì)算一次系統(tǒng)上行總吞吐量的線性復(fù)雜度,O2表示計(jì)算兩用戶間距離的線性復(fù)雜度,O3表示運(yùn)行一次匈牙利算法的線性復(fù)雜度。表3給出了各算法達(dá)到收斂所需的迭代次數(shù)IT。由于GA算法后期主要是靠基因隨機(jī)變異來獲得性能提升,要達(dá)到最終收斂需要非常大的迭代次數(shù)?？紤]到計(jì)算復(fù)雜度,本文給定了GA算法一個固定迭代次數(shù)50。從表2和表3中可以看出,相較于文獻(xiàn)[7]中算法,本文所提算法不僅沒有增加使用匈牙利算法部分的迭代次數(shù),且在每次迭代中將匈牙利算法的使用次數(shù)減少了τp倍。從表3還能看出,將經(jīng)過K-ImpHungarian算法得到的導(dǎo)頻分配方案作為Coal算法的初始狀態(tài)可以大大降低Coal算法的迭代次數(shù)。

表2 各算法的計(jì)算復(fù)雜度

表3 各算法迭代部分達(dá)到收斂所需平均迭代次數(shù)

6 結(jié) 論

本文在CF mMIMO的場景下提出了一種基于簇級匈牙利與聯(lián)盟博弈聯(lián)合的導(dǎo)頻分配算法。先利用對用戶聚類的方式減少直接使用匈牙利算法進(jìn)行導(dǎo)頻分配的復(fù)雜度,再從全局的角度改進(jìn)了匈牙利算法中的收益矩陣,最后用聯(lián)盟博弈算法避免了因?yàn)楣潭ǖ膶?dǎo)頻使用次數(shù)而帶來的性能上限。仿真結(jié)果表明,本文提出的導(dǎo)頻分配算法性能優(yōu)于多種典型導(dǎo)頻分配算法。