異構(gòu)蜂窩網(wǎng)絡(luò)中一種基于匈牙利算法的用戶關(guān)聯(lián)方法

蘇恭超，陳 彬，林曉輝，王 暉，李樂民

?

異構(gòu)蜂窩網(wǎng)絡(luò)中一種基于匈牙利算法的用戶關(guān)聯(lián)方法

蘇恭超1,2，陳 彬2，林曉輝2，王 暉2，李樂民1

(1. 電子科技大學(xué)通信與信息工程學(xué)院 成都 611731；2. 深圳大學(xué)現(xiàn)代通信與信息處理重點(diǎn)實(shí)驗(yàn)室 廣東深圳 518060)

在異構(gòu)蜂窩網(wǎng)絡(luò)中使用傳統(tǒng)的小區(qū)選擇方法會(huì)導(dǎo)致宏基站和小基站的負(fù)載失衡，而與小基站關(guān)聯(lián)的用戶面臨服務(wù)質(zhì)量(QoS)的降低的問題。針對(duì)該問題，提出了一種基于效用函數(shù)最大化的用戶與基站關(guān)聯(lián)方法。該方法將用戶與基站的關(guān)聯(lián)過程建模為雙目標(biāo)優(yōu)化問題并且線性化為系數(shù)可調(diào)的效用函數(shù)最大化問題，以實(shí)現(xiàn)基站負(fù)載均衡和用戶QoS之間的折中。通過設(shè)計(jì)權(quán)值系數(shù)，將該效用函數(shù)最大化問題轉(zhuǎn)化為基于二部圖的最大匹配，并用匈牙利算法求得最優(yōu)解。仿真結(jié)果表明，該方法實(shí)現(xiàn)了異構(gòu)蜂窩網(wǎng)絡(luò)中宏基站與小基站之間的負(fù)載均衡，并且通過系數(shù)調(diào)節(jié)，達(dá)到了基站負(fù)載均衡和用戶QoS之間的折中。

二部圖匹配; 用戶關(guān)聯(lián); 異構(gòu)網(wǎng)絡(luò); 匈牙利算法; 負(fù)載均衡

隨著移動(dòng)互聯(lián)網(wǎng)的高速發(fā)展，不斷增長的數(shù)據(jù)業(yè)務(wù)對(duì)蜂窩網(wǎng)絡(luò)的容量和速率的要求逐漸增加。近年來，蜂窩網(wǎng)絡(luò)架構(gòu)逐漸向異構(gòu)化方向演進(jìn)，通過在宏基站覆蓋區(qū)域內(nèi)大量架設(shè)低功率低能耗的小基站(SBS)，形成異構(gòu)網(wǎng)絡(luò)(HetNets)[1]，為用戶提供更多的頻譜資源，從而提升用戶速率和系統(tǒng)容量。

在傳統(tǒng)的蜂窩網(wǎng)絡(luò)中，終端用戶僅和宏基站關(guān)聯(lián)，由于宏基站數(shù)量有限，相鄰小區(qū)間的干擾可控，因此終端用戶通常通過測(cè)量各宏基站的參考信號(hào)功率來選擇信號(hào)最強(qiáng)的基站并與之關(guān)聯(lián)。然而由于宏基站的覆蓋范圍內(nèi)有大量的低功率小基站存在，通過測(cè)量參考信號(hào)來選擇小區(qū)基站，必然造成大量的用戶仍然選擇和大功率的宏基站關(guān)聯(lián)，使得宏基站和小基站的負(fù)載呈現(xiàn)較大差異，從而導(dǎo)致大量的資源浪費(fèi)。因此需要將終端用戶主動(dòng)的和小基站關(guān)聯(lián)，實(shí)現(xiàn)宏基站和小基站之間的負(fù)載均衡，從而更有效地利用小基站的無線資源[2]。宏基站和大量的小基站共享頻譜資源，在下行鏈路中宏基站將對(duì)與小基站關(guān)聯(lián)的用戶形成強(qiáng)烈的干擾，導(dǎo)致這些用戶的信號(hào)與噪聲加干擾比(signal to interference plus noise ratio, SINR)降低，從而降低服務(wù)質(zhì)量。因此用戶關(guān)聯(lián)策略也應(yīng)考慮到基站負(fù)載均衡和網(wǎng)絡(luò)服務(wù)質(zhì)量的折中。

近年來，異構(gòu)蜂窩網(wǎng)絡(luò)中的用戶關(guān)聯(lián)策略已成為學(xué)術(shù)界和業(yè)界研究的熱點(diǎn)。一種較簡單的方案是小區(qū)范圍擴(kuò)展[3]。終端用戶所接收的來自小基站的參考信號(hào)功率被人為放大，使得更多的用戶選擇與小基站關(guān)聯(lián)。然而功率放大系數(shù)難以確定最優(yōu)值。文獻(xiàn)[4-5]提出了一種求解對(duì)數(shù)效用函數(shù)最優(yōu)化問題來獲取最優(yōu)關(guān)聯(lián)策略的方法，通過松弛約束條件轉(zhuǎn)化為凸優(yōu)化問題并對(duì)其拉格朗日對(duì)偶問題求解。然而獲取的最優(yōu)解要求允許用戶可以同時(shí)和多個(gè)基站關(guān)聯(lián)，難以實(shí)現(xiàn)。另一類方法則是用組合優(yōu)化的方法來求解[6-9]。文獻(xiàn)[7-8]通過求解基于二分圖的匹配問題來獲取用戶關(guān)聯(lián)策略，然而其用戶關(guān)聯(lián)策略并非以基站負(fù)載均衡為目的。文獻(xiàn)[9]提出用貪心算法來求解效用函數(shù)最大化問題的次優(yōu)解，并指出效用函數(shù)的最大化問題可轉(zhuǎn)換為基于二分圖的匹配問題，但沒有考慮基站負(fù)載均衡和網(wǎng)絡(luò)服務(wù)質(zhì)量的折中。

本文提出了一種負(fù)載均衡度可調(diào)的用戶關(guān)聯(lián)策略，將用戶與基站的關(guān)聯(lián)建模為可調(diào)系數(shù)的效用函數(shù)最優(yōu)化問題，以達(dá)到基站負(fù)載均衡和網(wǎng)絡(luò)服務(wù)質(zhì)量的折中。通過將該效用函數(shù)最大化問題轉(zhuǎn)化成一個(gè)基于二部圖的最大匹配問題，利用匈牙利算法求得最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，這種方法和傳統(tǒng)的基于最大SINR的用戶關(guān)聯(lián)策略相比，實(shí)現(xiàn)了宏基站與小基站之間的負(fù)載均衡，通過調(diào)節(jié)系數(shù)，達(dá)到了基站負(fù)載和用戶QoS之間的折中。

1 系統(tǒng)模型與問題建模

考慮一個(gè)異構(gòu)蜂窩網(wǎng)絡(luò)的下行鏈路部分，該異構(gòu)蜂窩網(wǎng)絡(luò)包含宏基站和一系列小基站。假定在小區(qū)覆蓋范圍內(nèi)總共有個(gè)基站和個(gè)用戶。集合代表所有用戶，集合代表所有基站?；镜膫鬏敼β蕿?i>P。所有的基站均工作在同一頻段并且頻率復(fù)用系數(shù)為1。系統(tǒng)帶寬為，信道取均值為1的瑞利衰落信道。

若用戶與基站關(guān)聯(lián)，則基站到用戶的下行鏈路上的SINR可以表達(dá)為：

在后續(xù)的討論中，假定信道帶寬歸一化為1。由于用戶僅和單個(gè)基站關(guān)聯(lián)，因此：

(3)

要獲取用戶與基站的關(guān)聯(lián)策略，即求解關(guān)聯(lián)策略變量，其為的矩陣，各元素取值為。一種常見的方法是將用戶-基站關(guān)聯(lián)過程建模為一個(gè)效用函數(shù)最大化問題[4]，其目標(biāo)函數(shù)以用戶速率為自變量，而與有關(guān)：

(5)

然而式(5)是一個(gè)組合優(yōu)化問題并且是NP困難問題。用窮舉法列出的所有可能取值需要的復(fù)雜度，而若將約束條件松弛為連續(xù)變量，則式(5)轉(zhuǎn)為凸優(yōu)化問題，但是約束條件導(dǎo)致所得的解要求一個(gè)用戶同時(shí)與多個(gè)基站關(guān)聯(lián)，并且所得的極值必然大于等于離散變量約束條件下的極值，因此是上限值。因此有必要考慮利用組合優(yōu)化中的理論方法去求解該問題。同時(shí)，由于用戶與小基站關(guān)聯(lián)后導(dǎo)致用戶SINR的降低，從而影響網(wǎng)絡(luò)服務(wù)質(zhì)量，因此所得出的用戶關(guān)聯(lián)策略應(yīng)實(shí)現(xiàn)基站負(fù)載均衡和用戶QoS之間的折中并且這種折中應(yīng)當(dāng)可以調(diào)整。

1.1 系數(shù)可調(diào)的效用函數(shù)最大化問題

為實(shí)現(xiàn)基站負(fù)載均衡，仍然保留對(duì)數(shù)函數(shù)作為效用函數(shù)。首先式(5)中的約束條件可以導(dǎo)出隱式約束條件：

注意到式(5)的目標(biāo)函數(shù)可以寫成：

(7)

對(duì)式(7)前半部分求極值，所得的最優(yōu)解將導(dǎo)致用戶和信號(hào)最強(qiáng)的基站關(guān)聯(lián)(此時(shí)最大)。令，式(7)后半部分則可改寫成，結(jié)合隱式約束條件，對(duì)歸一化后則對(duì)該部分求極值轉(zhuǎn)換為熵最大化問題[10]，所得的最優(yōu)解將導(dǎo)致取均值，即用戶在各基站之間均勻分布。因此可以將式(5)推廣為一個(gè)雙目標(biāo)優(yōu)化問題：

將式(8)線性化后，該優(yōu)化問題表達(dá)為：

1.2 基于二部圖的最優(yōu)匹配

為使得用戶和基站的關(guān)聯(lián)符合匹配的定義，將基站用一個(gè)虛擬基站的集合來替代，由于基站最多與個(gè)用戶關(guān)聯(lián)，因此。此時(shí)基站與多個(gè)用戶關(guān)聯(lián)轉(zhuǎn)化為每個(gè)用戶與單個(gè)虛擬基站關(guān)聯(lián)。因此基站和用戶的關(guān)聯(lián)，轉(zhuǎn)化為二部圖中的匹配，其中，邊集中的邊一端連接虛擬基站集合中的頂點(diǎn)，另一端連接用戶集合中的頂點(diǎn)。圖1說明了這種轉(zhuǎn)換關(guān)系。

定理 1 假設(shè)有個(gè)用戶和基站關(guān)聯(lián)，則其權(quán)值之和等同于這個(gè)用戶與中前個(gè)虛擬基站匹配的權(quán)值之和。

證明：由于基站與個(gè)用戶關(guān)聯(lián)，因此基站的負(fù)載。此時(shí)這個(gè)用戶與基站關(guān)聯(lián)的權(quán)值之和為。而若這個(gè)用戶與中前個(gè)虛擬基站匹配，其權(quán)值之和：

(11)

文獻(xiàn)[9]已證明若匹配的權(quán)值滿足定理1的性質(zhì)，則用戶與基站之間的關(guān)聯(lián)問題等價(jià)于用戶與虛擬基站之間的最大匹配問題，因此有如下結(jié)論。

推論 1 式(9)等價(jià)于以下二部圖最優(yōu)匹配問題：

(12a)

(12b)

式(12)中，約束條件(12a)保證用戶只與單個(gè)虛擬基站關(guān)聯(lián)，約束條件(12b)保證虛擬基站最多只和一個(gè)用戶關(guān)聯(lián)。因此式(12)是一個(gè)二部圖最大匹配問題，并且由于虛擬基站的數(shù)目大于用戶數(shù)目，這種匹配是非完美匹配。

1.3 基于匈牙利算法的用戶-基站關(guān)聯(lián)

求解式(12)中的二部圖最優(yōu)匹配問題，可以使用文獻(xiàn)[11]中提出的針對(duì)長方矩陣變量的匈牙利算法。匈牙利算法在求解二部圖中的最優(yōu)匹配時(shí)的復(fù)雜度為，，為2個(gè)集合的維數(shù)。由于式(12)中虛擬基站的數(shù)量為，因此匈牙利算法在求解式(12)時(shí)復(fù)雜度為，其復(fù)雜度仍遠(yuǎn)低于窮舉法的復(fù)雜度。求出式(12)的解后，將矩陣按照列等分成部分，每部分為列，再觀測(cè)矩陣第行第部分是否有1值，如果是則將置為1。遍歷每行后即獲得了用戶與基站的關(guān)聯(lián)。算法描述如下所示。

3) for=1～

Break

End if

End for

End for

4) 輸出。

1.4 基于匈牙利算法的關(guān)聯(lián)方案與凸優(yōu)化-取整方案[4]和基于貪心算法的方案[9]的比較

由于式(9)等價(jià)于式(12)，用匈牙利算法求得的二部圖匹配式(12)的最優(yōu)解，也是組合優(yōu)化問題式(9)的最優(yōu)解。由于式(5)是式(9)的特例，文獻(xiàn)[4-5]提出將約束條件松弛為，從而將式(5)轉(zhuǎn)化為凸優(yōu)化問題求解。由于等式約束條件的存在，對(duì)于用戶，求得的最優(yōu)解中可能存在多個(gè)。為保證用戶和單個(gè)基站關(guān)聯(lián)，文獻(xiàn)[4-5]提出對(duì)最優(yōu)解取整，即選取基站與用戶關(guān)聯(lián)，從而獲得式(5)的一個(gè)可行解。然而，這種做法導(dǎo)致效用函數(shù)值降低，同時(shí)，如果最優(yōu)解中存在和用戶對(duì)應(yīng)的多個(gè)相同的最大值，則這種取整的方案只能隨機(jī)選取其中一個(gè)基站與用戶關(guān)聯(lián)。因此，文獻(xiàn)[4-5]中使用的凸優(yōu)化-取整方案獲得了式(5)的次優(yōu)解。另一方面，文獻(xiàn)[9]中提出使用貪心算法求解式(5)，但只證明了貪心算法獲得的解接近最優(yōu)解，因此求出的解仍然是次優(yōu)解。

2 仿真實(shí)驗(yàn)與結(jié)果分析

在仿真實(shí)驗(yàn)中，宏基站的覆蓋區(qū)域設(shè)定為1 km2，其中有1個(gè)宏基站、5個(gè)小基站以及100個(gè)用戶。宏基站位置居中，而小基站和用戶位置按照均勻分布在覆蓋區(qū)域內(nèi)隨機(jī)放置。宏基站和小基站的傳輸功率分別置為46 dBm和20 dBm，信道路徑損耗設(shè)置為與距離相關(guān)，取值為(為距離)[4-5]。

a. 最大SINR關(guān)聯(lián)

b.時(shí)凸優(yōu)化-取整方案

c.時(shí)基于貪心算法的用戶關(guān)聯(lián)方案

d.時(shí)基于匈牙利算法的用戶關(guān)聯(lián)方案

圖2 最大SINR和效用函數(shù)最大化下的用戶-基站關(guān)聯(lián)

可以看出，用匈牙利算法求得的用戶關(guān)聯(lián)策略與用凸優(yōu)化-取整方法和用貪心算法求得的用戶關(guān)聯(lián)策略存在一定的差異。這是由于凸優(yōu)化-取整方案和貪心算法求出的是式(9)的次優(yōu)解，與通過匈牙利算法求出的最優(yōu)解之間存在差異。圖3給出了在不同的小基站數(shù)量下與宏基站關(guān)聯(lián)的用戶占全體用戶的比例。與宏基站關(guān)聯(lián)的用戶數(shù)量，隨小基站數(shù)量的增加而逐步降低。效用函數(shù)最大化框架下，與宏基站關(guān)聯(lián)的用戶顯著少于最大SINR關(guān)聯(lián)方案?；谛傺览惴ǖ年P(guān)聯(lián)方案下與宏基站關(guān)聯(lián)的用戶最少?；谪澬乃惴ǖ姆桨负屯箖?yōu)化-取整方案下宏基站關(guān)聯(lián)用戶比例較接近于基于匈牙利算法的方案。

圖4給出了最大SINR和不同系數(shù)下基于匈牙利算法的效用函數(shù)最大化關(guān)聯(lián)策略中宏基站和小基站負(fù)載的對(duì)比。在最大SINR關(guān)聯(lián)策略下，有約10%的用戶與小基站關(guān)聯(lián)。在效用函數(shù)最大化關(guān)聯(lián)策略下與小基站關(guān)聯(lián)的用戶比率均有增加。當(dāng)時(shí)，和小基站關(guān)聯(lián)的用戶比率超過50%。當(dāng)時(shí)則更偏向于與最大SINR的基站關(guān)聯(lián)，和小基站關(guān)聯(lián)的用戶比率更接近于最大SINR策略。而當(dāng)時(shí)和小基站關(guān)聯(lián)的用戶比率位于前兩者之間。這說明，通過調(diào)節(jié)系數(shù)的值，可以影響宏基站與小基站之間的負(fù)載均衡。

圖4 不同基站-用戶關(guān)聯(lián)策略中與各類基站關(guān)聯(lián)的用戶比例

圖5給出了不同的基站-用戶關(guān)聯(lián)策略下用戶SINR均值的累積分布?？梢钥吹阶畲骃INR關(guān)聯(lián)策略能為用戶提供最高的SINR。采用效用函數(shù)最大化策略將用戶關(guān)聯(lián)至小基站后SINR均有所降低。當(dāng)時(shí)超過40%的用戶SINR降到0 dB以下。當(dāng)時(shí)超過20%的用戶 SINR降到0 dB以下，當(dāng)時(shí)SINR在0 dB以下的用戶比率約為10%。這說明調(diào)節(jié)系數(shù)后實(shí)現(xiàn)了基站負(fù)載均衡和用戶SINR之間不同程度的折中。

圖5 用戶SINR均值的累積分布

3 結(jié) 束 語

本文提出了一種系數(shù)可調(diào)的效用函數(shù)最大化策略來實(shí)現(xiàn)異構(gòu)蜂窩網(wǎng)絡(luò)中用戶與宏基站和小基站的關(guān)聯(lián)。將效用函數(shù)最大化問題轉(zhuǎn)化為基于二部圖的最優(yōu)匹配，并利用匈牙利算法求得最優(yōu)解，確保每個(gè)用戶僅和單個(gè)基站關(guān)聯(lián)，易于實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明通過本文提出的方法所獲得的基站-用戶關(guān)聯(lián)，實(shí)現(xiàn)了宏基站與小基站之間的負(fù)載均衡，并且通過調(diào)節(jié)參數(shù)在基站負(fù)載均衡和用戶QoS之間取得折中。

[1] ANDREWS J G. Seven ways that HetNets are a cellular paradigm shift[J]. IEEE Communications Magazine, 2013, 51(3): 136-144.

[2] ANDREWS J G, SINGH S, YE Qiao-yang, et alAn overview of load balancing in HetNets: Old myths and open problems[J]. IEEE Communications Magazine, 2014, 52(4): 18-25.

[3] DAMNJANOVIC A, MONTOJO J, WEI Yong-bin, et al. A survey on 3GPP heterogeneous networks[J]. IEEE Wireless Communications Magazine, 2011, 18(3): 10-21.

[4] YE Qiao-yang, RONG Bei-yu, CHEN Yu-dong, et al. User association for load balancing in heterogeneous cellular networks[J]. IEEE Transactions on Wireless Communications, 2013, 12(6): 2706-2716.

[5] SHEN Kai-ming, YU Wei. Downlink cell association optimization for heterogeneous networks via dual coordinate descent[C]//Proceedings of IEEE Int. Conf. on Acoustics, Speech and Signal Processing. Vancouver, BC, Canada: IEEE, 2013: 4779-4783.

[6] GU Yun-an, SAAD W, BENNIS M, et al. Matching theory for future wireless networks: Fundamentals and applications [J]. IEEE Communications Magazine, 2015, 53(5): 52-59.

[7] MISHRA S, RANGENENI S, MURTHY C. Exploiting an optimal user association strategy for interference management in HetNets[J]. IEEE Communications Letter, 2014, 18(10): 1799-1802.

[8] TAEJOON K, DONG Miao-miao. An iterative Hungarian method to joint relay selection and resource allocation for D2D communications[J]. IEEE Wireless Communication Letters, 2014, 3(6): 625-628.

[9] PRASAD N, ARSLAN M, RANGARAJAN S. Exploiting cell dormancy and load balancing in LTE HetNets: Optimizing the proportional fairness utility[J]. IEEE Transactions on Communications, 2014, 62(10): 3706-3722.

[10] BOYD S, VANDENBERGHE L. Convex optimization[M]. Cambridge: Cambridge University Press, 2004.

[11] BOURGEOIS F, LASSALLE J C. An extension of the Munkres algorithm for the assignment problem to rectangular matrices[J]. Communications of the ACM, 1971, 14(12): 802-804.

編 輯 葉 芳

User Association in Heterogeneous Cellular Networks Via the Hungarian Method

SU Gong-chao1,2, CHEN Bin2, LIN Xiao-hui2, WANG Hui2, and LI Le-min1

(1. School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. Key Lab of Advanced Communications and Information Processing, Shenzhen University Shenzhen Guangdong 518060)

In heterogeneous cellular networks, traditional user association schemes based on reference signal power result in load imbalances between macro cell base stations (MBSs) and small cell base stations (SBSs). Meanwhile, offloading users to SBSs face the quality of service (QoS) degradation. In this paper, we propose a utility maximization framework to address the user association problem. In order to strike a tradeoff between load balancing and user QoS experiences, a bi-criterion optimization problem is formulated to solve the user association problem. The bi-criterion optimization problem is then linearized as a utility maximization problem with a tunable parameter. In addition, we show that the utility maximization problem can be reformulated as a maximum bi-partite matching problem and can be solved in polynomial time by using the Hungarian method. Simulation results show that our proposed method achieves load balancing and can strike tradeoffs between load balancing and user QoS by tuning the optimization parameter.

bipartite matching; cell association; heterogeneous networks; Hungarian method; load balancing

TN92

A

10.3969/j.issn.1001-0548.2017.02.005

2015-07-01；

2016-01-14

國家自然科學(xué)基金(61301182, 61372078, 61171071)；國家973項(xiàng)目(2013CB329103)

蘇恭超(1979-)，男，博士，主要從事無線通信方面的研究.