錢葉旺 周天清 楊綠溪
(1.池州學(xué)院機(jī)電工程學(xué)院,池州,247000; 2.華東交通大學(xué)信息工程學(xué)院,南昌,330013; 3.東南大學(xué)信息科學(xué)與工程學(xué)院,南京,211189)
為消除傳統(tǒng)蜂窩網(wǎng)絡(luò)中的覆蓋漏洞、提升熱點(diǎn)區(qū)域網(wǎng)絡(luò)吞吐量[1],傳統(tǒng)宏蜂窩網(wǎng)絡(luò)中引入了諸多異構(gòu)元素(如微基站、皮蜂窩、飛蜂窩和中繼等),形成了異構(gòu)蜂窩網(wǎng)絡(luò)(Heterogeneous cellular network,HCN)[2]。盡管HCN可帶來(lái)極大頻譜效益,但其用戶接入(小區(qū)選擇)問(wèn)題富于挑戰(zhàn)性且往往影響系統(tǒng)性能。由于HCN中各類基站具有明顯不同的發(fā)射功率,一些僅聚焦于用戶接收信號(hào)強(qiáng)度的接入方案(如最大信干噪比接入,最大可達(dá)速率接入、最近基站接入與最佳信道質(zhì)量接入等)已然不適用。當(dāng)這些方案被應(yīng)用于HCN時(shí),即使負(fù)載均勻分布于網(wǎng)絡(luò)覆蓋區(qū)域,各類基站間的負(fù)載水平仍表現(xiàn)為極度不平衡。具體地,絕大部分用戶選擇高功率基站,少數(shù)用戶選擇低功率基站[3]。顯然,為充分開(kāi)發(fā)新型網(wǎng)絡(luò)架構(gòu)的潛力,具有轉(zhuǎn)載能力小區(qū)選擇方案的設(shè)計(jì)有必要且意義重大。注意到,轉(zhuǎn)載能力是指將傳統(tǒng)最強(qiáng)信號(hào)接入中超載基站的用戶轉(zhuǎn)入輕負(fù)荷基站的能力,而這些轉(zhuǎn)入其他基站的用戶則被稱為轉(zhuǎn)載用戶。
目前,就網(wǎng)絡(luò)負(fù)載定義而言,已有的負(fù)載平衡方案可分為如下3類。
第1類,定義接入用戶數(shù)為基站負(fù)載。在HCN中,絕大多數(shù)負(fù)載平衡方案基于此定義。偏離因子法(區(qū)域拓展)接入[4]作為通用負(fù)載平衡方案,它為低功率基站添加一個(gè)偏離/補(bǔ)償進(jìn)而理論上提升其發(fā)射功率。在此理論功率基礎(chǔ)上,該方案再依據(jù)最強(qiáng)信號(hào)接入準(zhǔn)則執(zhí)行小區(qū)選擇,從而達(dá)到拓展小基站(低功率基站)覆蓋面積的目的。雖然該法實(shí)行簡(jiǎn)單,但由于閉式最優(yōu)偏離因子/補(bǔ)償往往難以捕捉,因此無(wú)法保證最佳系統(tǒng)性能。為避免搜索最佳參數(shù),其他負(fù)載平衡方案漸已融入HCN中[5-7],如最小路徑損耗接入[7]等。
第2類,定義小區(qū)數(shù)據(jù)流為基站負(fù)載。根據(jù)業(yè)務(wù)數(shù)據(jù)流的分布情況,Son等[8]聯(lián)合用戶接入與基站開(kāi)關(guān)操作設(shè)計(jì)了一個(gè)折衷能耗與時(shí)延的接入方案,并為其設(shè)計(jì)了兩類貪婪算法。Siomina 等[9]認(rèn)為小區(qū)間負(fù)載具有耦合性,并于此基礎(chǔ)上嘗試最大化網(wǎng)絡(luò)負(fù)載平衡指數(shù),從而達(dá)到平衡小區(qū)間數(shù)據(jù)流的目的。
第3類,定義用戶消耗資源量(物理資源塊數(shù))為基站負(fù)載。根據(jù)用戶資源消耗情況,Wang等[10]設(shè)計(jì)了一個(gè)小區(qū)選擇方案以聯(lián)合優(yōu)化負(fù)載平衡水平與系統(tǒng)容量。此外,Wang等[11]對(duì)其優(yōu)化問(wèn)題中衡量負(fù)載平衡水平的標(biāo)準(zhǔn)加以簡(jiǎn)化,使其原問(wèn)題更易處理?;赪ang等的工作,Li等[12]進(jìn)一步聯(lián)合考慮小區(qū)內(nèi)負(fù)載平衡與小區(qū)間負(fù)載平衡。不難發(fā)現(xiàn),盡管這些方案具有較好的思路,但在實(shí)際應(yīng)用中卻難以確定模型中的最佳網(wǎng)絡(luò)參數(shù),如優(yōu)化問(wèn)題中所涉及的權(quán)重等。
在上述3類定義中,第1類定義有利于小區(qū)選擇方案的設(shè)計(jì),但有時(shí)可能因無(wú)法反映小區(qū)數(shù)據(jù)流量(或資源消耗量)的變化而導(dǎo)致接入方案的性能偏差;第2類定義能反映網(wǎng)絡(luò)數(shù)據(jù)流量的變化,但因系統(tǒng)模型過(guò)于復(fù)雜而使得接入算法的設(shè)計(jì)富于挑戰(zhàn)性;第3類定義能很好地捕捉用戶服務(wù)質(zhì)量(Quality of service,QoS)需求,但要在嚴(yán)格保證用戶QoS需求下設(shè)計(jì)有效的接入算法同樣富于挑戰(zhàn)性。目前,基于第2,3類定義的小區(qū)選擇方案多數(shù)采用集中算法,而這類算法復(fù)雜度往往偏高。此外,在第2,3類定義下,針對(duì)HCN系統(tǒng)的負(fù)載平衡方案更是鳳毛麟角。因此,在HCN中,如何設(shè)計(jì)針對(duì)第2,3類定義的負(fù)載平衡方案,并為其開(kāi)發(fā)簡(jiǎn)單、有效的接入算法仍是一個(gè)富有意義的話題[13]。
鑒于此,本文基于第3類負(fù)載定義,提出了一類新型QoS感知的負(fù)載平衡方案。該方案能折衷系統(tǒng)容量與負(fù)載,即適當(dāng)?shù)亟档陀脩艨蛇_(dá)速率以盡量平衡基站負(fù)載。此處,“降低用戶可達(dá)速率”是指由于用戶選擇信道質(zhì)量略差的輕負(fù)荷基站而導(dǎo)致可達(dá)速率下降。不同于Zhou等的工作[14],本文采用動(dòng)態(tài)步長(zhǎng),在此基礎(chǔ)上給出了相應(yīng)的收斂性與復(fù)雜度分析,并給出了更為充分的仿真分析(仿真參數(shù)及指標(biāo)有所變動(dòng))。
圖1 兩層異構(gòu)蜂窩網(wǎng)絡(luò)Fig.1 Two-tier HCNs
異構(gòu)蜂窩網(wǎng)絡(luò)包含規(guī)則與不規(guī)則的兩種布置。在規(guī)則布置中,宏基站(Macro base station,MBS)按傳統(tǒng)蜂窩結(jié)構(gòu)布置;在不規(guī)則布置中,宏基站則被隨機(jī)撒點(diǎn)。鑒于接入規(guī)則本身特性,無(wú)論采用何種結(jié)構(gòu),所設(shè)計(jì)接入方案較其他方案的優(yōu)越性不變。不失一般性,僅考慮由MBS與皮蜂窩(Pico base station,PBS)組成的兩層異構(gòu)蜂窩網(wǎng)絡(luò)[1],其中MBS依傳統(tǒng)蜂窩結(jié)構(gòu)布置,而用戶與PBS則被隨機(jī)撒入宏小區(qū),其拓?fù)浣Y(jié)構(gòu)如圖1所示。
定義包含MBS與PBS的基站集為N,用戶集為K,其基分別為N=|N|和K=|K|。根據(jù)長(zhǎng)期演進(jìn)(Long term evolution,LTE)技術(shù)關(guān)于物理層的描述[15],相鄰12個(gè)子載波組成一個(gè)物理資源塊(Physical resource block,PRB),該資源塊具有180 kHz的帶寬,且為可分配給用戶的最小單元。那么,用戶k∈K接收來(lái)自基站n∈N的信干噪比(Signal-to-interference-plus-noise-ratio,SINR)為
(1)
式中:pn為基站n在單個(gè)PRB上的發(fā)射功率;gnk代表基站n與用戶k之間的信道增益;Wprb為PRB的帶寬;N0為噪聲功率譜密度。注意到,本文假設(shè)每個(gè)基站對(duì)所用頻帶進(jìn)行等功率分配。
當(dāng)給定功率pn時(shí),用戶k接收來(lái)自基站n的可達(dá)速率(單位為Kbps)為rnk=Wprblog2(1+SINRnk),且r={rnk,?n∈N,?k∈K}。
為突顯用戶資源消耗水平與實(shí)現(xiàn)負(fù)載平衡,嘗試設(shè)計(jì)了一類QoS感知的小區(qū)選擇方案。代替最強(qiáng)信號(hào)接入方案中的準(zhǔn)則,該方案以資源消耗量作為接入指標(biāo)?;诖耍O(shè)計(jì)了一個(gè)最大化網(wǎng)絡(luò)加權(quán)效益的負(fù)載平衡方案,該方案可規(guī)劃為
(2)
式中:x={xnk,?n∈N,?k∈K};Unk(·)為用戶k接入基站n時(shí)所獲得的效益;Sn為基站n的資源總量;約束C1表明服務(wù)用戶消耗資源量不能超過(guò)基站資源總量;約束C2表明用戶僅能選擇單一基站。在該式中,效用函數(shù)Unk(·)為連續(xù)可微、單調(diào)遞增且嚴(yán)格凹的函數(shù)。
為保證用戶公平性,引入對(duì)數(shù)效用函數(shù),問(wèn)題(2)則可轉(zhuǎn)化為
s.t.C1,C2,C3
(3)
(4)
其中y={yn,?n∈N}。 容易發(fā)現(xiàn),當(dāng)接入指示變量x從整數(shù)域{0,1}松馳到分?jǐn)?shù)域[0,1]時(shí),問(wèn)題(4)則為凸優(yōu)化問(wèn)題。
為解決凸形式的問(wèn)題(4),梯度下降法不失為有效手段。為搜索其最優(yōu)解,需收集全局網(wǎng)絡(luò)信息,那么需涉及集中式算法。鑒于集中式算法復(fù)雜度偏高,這里采用有效分布式算法設(shè)計(jì)。不同于集中式算法,分布式算法往往無(wú)需基站間的協(xié)作處理。
觀察問(wèn)題(4)不難發(fā)現(xiàn),約束C4具有耦合性。為便于問(wèn)題的求解,去耦(Decoupling)操作不可或缺。為此,引入了一個(gè)對(duì)偶變量μ={μn,n∈N}對(duì)該約束進(jìn)行松弛。于是,關(guān)于此約束的拉格朗日函數(shù)為
(5)
不難得出,問(wèn)題(4)的對(duì)偶函數(shù)為
(6)
且其對(duì)偶問(wèn)題為
(7)
鑒于問(wèn)題(7)為非耦合問(wèn)題,主變量x和y可以分開(kāi)求解。根據(jù)對(duì)偶分解法的思想[16],問(wèn)題(7)可分解為
(8)
(9)
為獲取對(duì)偶問(wèn)題(7)的最優(yōu)解,梯度下降法[17]不失為一種有效手段。 具體地,拉格朗日乘子μ沿著對(duì)偶函數(shù)(6)的負(fù)梯度方向(-G(μ))進(jìn)行迭代更新。為獲此梯度,主問(wèn)題的最優(yōu)解應(yīng)事先獲知,即求解問(wèn)題(8,9)。鑒于問(wèn)題(8,9)的形式,可對(duì)其采用并行處理方式。
至于問(wèn)題(8),它可簡(jiǎn)化成
?k∈K
(10)
算法1用戶k端算法
(1) Ift=0
(2) 根據(jù)來(lái)自所有基站的導(dǎo)頻信號(hào)估計(jì)r。
(3) Else
(4) 用戶k接收來(lái)自所有基站的廣播信息μ,并根據(jù)規(guī)則(10)選擇基站n*。
(5) 反饋接入信息xn*k=1給基站n*。
(6) End If
至于問(wèn)題(9),可根據(jù)其Karush-Kuhn-Tucker (KKT)[17]條件獲得基站最優(yōu)負(fù)載,即
?n∈N
(11)
式中exp(z)為關(guān)于z的指數(shù)函數(shù)。
當(dāng)最優(yōu)x和y給定時(shí),拉格朗日乘子則可以梯度下降法進(jìn)行更新,即
?n∈N
(12)
式中ξt為第t次迭代時(shí)用于更新乘子μn的步長(zhǎng),該步長(zhǎng)遵循Bertsekas規(guī)則[17]。具體地
(13)
(14)
通過(guò)式(13,14)更新乘子μ后,ε執(zhí)行如下更新
(15)
算法2基站n端算法
(1) Ift=0
(2) 初始化步長(zhǎng)ξt和μt。
(3) Else
(7) End If
從y與μ的更新規(guī)則來(lái)看,不難發(fā)現(xiàn),它們發(fā)生于基站端,即組成了基站端算法,其詳細(xì)描述可參考算法2。
完整的小區(qū)選擇算法應(yīng)交替執(zhí)行用戶與基站端算法,其收斂性可通過(guò)下面的理論加以證明。
定理1如果存在ε>0且G*>-∞,則
(16)
式中G*定義為對(duì)偶問(wèn)題(7)的最優(yōu)值。
證明:函數(shù)G(μ)的一階導(dǎo)為
(17)
為突出所設(shè)計(jì)算法的優(yōu)越性,仍調(diào)查了算法實(shí)現(xiàn)時(shí)的信息交互情況。在分布式算法中,任意基站n廣播其自身的服務(wù)費(fèi)用μn給所有用戶,而任意用戶k僅反饋其自身接入信息xnk=1給期望接入的基站n*。顯然,在每次迭代中,分布式算法的交互信息量為N+K。不同于分布式算法,集中式算法的交互信息量與NK成比例關(guān)系。
假定MBS間的距離為1 000 m,每個(gè)宏小區(qū)布置5個(gè)PBS,MBS和PBS發(fā)射功率分別為46與30 dBm,系統(tǒng)帶寬為10 MHz,且噪聲功率譜密度為-174 dBm/Hz。此外,MBS與PBS的路徑損耗分別為128.1+37.6logdnk和140.7+36.7logdnk[19-21],其中dnk為用戶k與基站n間的距離,單位為km。陰影衰弱則取為標(biāo)準(zhǔn)差為8 dB的對(duì)數(shù)正態(tài)陰影。
為突出所設(shè)計(jì)方案(QoS-aware association,QAA)的優(yōu)越性,仿真中引入了其他通用方案作比較。這些方案包括最強(qiáng)功率接入(Best power association,BPA)[5]和有偏信號(hào)強(qiáng)度接入(Biasing channel gain association,BCGA)[18]。前者屬于傳統(tǒng)最強(qiáng)信號(hào)接入,后者則屬于負(fù)載平衡接入方案。因此,方案QAA和BCGA具有轉(zhuǎn)載能力,而BPA卻不具備。此外,方案QAA具有QoS感知能力,而方案BPA和BCGA卻不具備。
為探索QoS需求對(duì)接入性能的影響,仿真中引入了兩類調(diào)度方案:(1) 最大實(shí)際速率優(yōu)先(Maximal practical rate first, MPRF)方案,即每個(gè)基站從接入用戶隊(duì)列中按實(shí)際速率從大到小的順序調(diào)度用戶;(2) 最大可達(dá)速率優(yōu)先(Maximal achievable rate first, MARF)方案,即每個(gè)基站從接入用戶隊(duì)列中按可達(dá)速率從大到小的順序調(diào)度用戶。通過(guò)引入調(diào)度算法,能更進(jìn)一步、更為明顯地展示方案QAA所帶來(lái)的負(fù)載平衡增益。
為測(cè)量網(wǎng)絡(luò)負(fù)載平衡水平,引入了Jain公平性指數(shù),即
(18)
針對(duì)不同調(diào)度方案,圖2展示了各類接入方案的網(wǎng)絡(luò)負(fù)載平衡水平隨用戶數(shù)(Number of users, NU)的變化情況,其中NU是指宏小區(qū)內(nèi)的用戶數(shù)。隨著NU的增加,各基站有更多的機(jī)會(huì)選擇用戶,從而有更多的機(jī)會(huì)實(shí)現(xiàn)基站間負(fù)載平衡。因此,LBI隨NU的增加而提高。在方案BPA中,絕大多數(shù)用戶接入至高功率基站MBS而使得該類基站資源消耗極大,且少部分用戶選擇低功率基站PBS而使得該類基站資源消耗偏少。因此,相比于其他負(fù)載平衡方案,方案BPA具有最低LBI。不同于方案BPA,方案BCGA通過(guò)為低功功率基站添加一個(gè)偏離來(lái)拓展其覆蓋范圍,因此迫使方案BPA中超載基站MBS的用戶轉(zhuǎn)入鄰近的輕負(fù)荷基站PBS。通過(guò)進(jìn)一步平衡方案BPA中的負(fù)載,方案BCGA達(dá)到了較之更高的LBI。從方案QAA的接入規(guī)則來(lái)看,用戶并非接入至擁有最佳信道質(zhì)量的基站(高功率基站),而是選擇折衷資源消耗和可達(dá)速率的基站,即表現(xiàn)為轉(zhuǎn)載能力。通過(guò)平衡基站間的負(fù)載,方案QAA達(dá)到了最高的LBI。盡管方案BCGA可通過(guò)調(diào)整偏離因子改善基站負(fù)載水平,但調(diào)整過(guò)程很難保證最優(yōu)。換言之,若偏離因子過(guò)小,則超載基站減壓不明顯;若偏離因子過(guò)大,則原信道質(zhì)量較差的基站反成超載基站。鑒于用戶調(diào)度嚴(yán)格受限于基站資源,無(wú)論何種調(diào)度方案,調(diào)度資源均不能超過(guò)基站本身所有。因此,兩類調(diào)度方案下LBI可能幾乎相同。
針對(duì)不同調(diào)度方案,圖3展示了各類接入方案的網(wǎng)絡(luò)負(fù)載平衡水平隨用戶實(shí)際速率需求(Practical rate, PR)變化的情況。如圖3所示,隨著用戶PR的增加, 方案BPA和BCGA的負(fù)載平衡水平開(kāi)始增加而后下降。在低速率域,隨著PR的增加,調(diào)度資源越發(fā)接近各類基站資源供應(yīng)量,因此負(fù)載平衡水平上升。當(dāng)PR增加到一定量時(shí),再度增加速率需求將導(dǎo)致更多資源片斷(資源塊)無(wú)法滿足用戶需求。由于高功率基站用戶往往具有高可達(dá)速率,因此高功率基站調(diào)度資源塊數(shù)通常多于低功率基站,且這一差距隨PR的增加而增大。因此,方案BPA和BCGA的LBI會(huì)出現(xiàn)下降趨勢(shì)。不同于方案BPA和BCGA,方案QAA起始時(shí)LBI就很高,即各類基站資源消耗趨近平衡。因此,方案QAA的LBI不存在上長(zhǎng)趨勢(shì)。但同其他方案一樣,當(dāng)增加PR時(shí),方案QAA的LBI應(yīng)呈現(xiàn)出下降趨勢(shì)。同時(shí)注意到,起始LBI越高,LBI增長(zhǎng)過(guò)程越短。其原因在于,原本高的LBI縮短了調(diào)度資源趨近飽和的過(guò)程。
圖2 用戶數(shù)對(duì)網(wǎng)絡(luò)負(fù)載平衡水平的影響Fig.2 Impact of NU on LBI
圖3 用戶實(shí)際速率需求對(duì)網(wǎng)絡(luò)負(fù)載平衡水平的影響Fig.3 Impact of user′s PR on LBI
針對(duì)不同調(diào)度方案,圖4展示了各類接入方案的用戶CBP隨NU的變化情況。正如之前所述,在方案BPA 中,絕大多數(shù)用戶接入至MBS,僅有少許用戶選擇PBS。顯然,在方案BPA中,很多接入至MBS的用戶由于基站沒(méi)有足夠資源而無(wú)法被調(diào)度,而PBS由于接入用戶過(guò)少而使得其資源無(wú)法被充分利用,從而造成了資源的極大浪費(fèi)。因此,相比于其他具有轉(zhuǎn)載能力的方案,方案BPA應(yīng)具有更高的CBP。盡管方案QAA以損耗資源(提升資源消耗)來(lái)迫使基站間實(shí)現(xiàn)負(fù)載平衡,但它通過(guò)平衡負(fù)載實(shí)現(xiàn)網(wǎng)絡(luò)資源的充分利用、提升用戶滿意度。因此,同方案BPA相比,方案QAA具有更低的CBP。此外,根據(jù)接入規(guī)則,不難發(fā)現(xiàn),方案BPA未考慮用戶QoS需求和資源限制,但方案QAA卻有所涉及。因此,方案QAA獲得了較方案BPA 更低的CBP。盡管方案BCGA可通過(guò)調(diào)整偏離因子而使得CBP下降,但調(diào)整過(guò)程很難保證最優(yōu),且轉(zhuǎn)載過(guò)程無(wú)法保證轉(zhuǎn)載用戶滿足基站資源限制。換言之,若偏離因子過(guò)小,則因超載基站減壓不明顯而使得許多用戶未能被調(diào)度;若偏離因子過(guò)大,則因原信道質(zhì)量較差的基站反成超載基站而使得更多用戶不能被調(diào)度。此外,在有限資源條件下,相比于調(diào)度方案MPRF,方案MARF可能調(diào)度更多用戶,從而使得調(diào)度方案MARF可能擁有較方案MPRF更低的CBP。
針對(duì)不同調(diào)度方案, 圖5展示了各類接入方案的用戶CBP隨用戶PR的變化情況。隨著用戶PR的增加,為支持用戶正常通信,基站不得不分配更多的資源給用戶。然而,每個(gè)基站的資源畢竟有限,因此用戶CBP隨用戶實(shí)際需求的增加而提高。此外,隨著用戶PR的提升,資源需求量逐漸增加,可接入用戶數(shù)越來(lái)越少。當(dāng)用戶PR足夠大后,各類方案接入用戶數(shù)可能就非常接近,即少數(shù)幾個(gè)高可達(dá)速率用戶被調(diào)度。因此,各方案的CBP越發(fā)接近。
圖4 用戶數(shù)對(duì)呼叫阻塞概率的影響Fig.4 Impact of NU on CBP
圖5 用戶實(shí)際速率需求對(duì)呼叫阻塞概率的影響Fig.5 Impact of user′s PR on CBP
圖6 QAA算法的收斂性Fig.6 Convergence of algorithm QQA
針對(duì)方案QAA的接入算法,圖6描繪了其收斂情況。根據(jù)仿真結(jié)果,不難發(fā)現(xiàn),所設(shè)計(jì)的接入算法具有較高的收斂速率,非常適用于實(shí)際應(yīng)用。
針對(duì)HCN系統(tǒng),設(shè)計(jì)了一類QoS感知的小區(qū)選擇方案以實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載平衡。在該方案中,基站資源消耗量被視為其負(fù)載。同時(shí),該方案還融入了用戶服務(wù)質(zhì)量需求,可反映用戶資源消耗水平。最終,該方案被規(guī)劃為網(wǎng)絡(luò)范圍的加權(quán)效益最大化問(wèn)題。鑒于所規(guī)劃問(wèn)題為非線性、混合整數(shù)優(yōu)化問(wèn)題,其最優(yōu)解的獲取富于挑戰(zhàn)性,嘗試?yán)脤?duì)偶分解法開(kāi)發(fā)了一個(gè)有效的分布式算法。仿真結(jié)果表明,同其他接入方案相比,所設(shè)計(jì)的接入方案具有較高的負(fù)載平衡水平和更低的用戶呼叫阻塞概率。此外,數(shù)值仿真仍顯示:所設(shè)計(jì)的分布式算法具有較快的收斂速率,非常適合實(shí)際應(yīng)用場(chǎng)景。未來(lái)研究工作可包括動(dòng)態(tài)接入算法的開(kāi)發(fā)、聯(lián)合功控方案的設(shè)計(jì)和推廣至上行系統(tǒng)。