一種聯(lián)合優(yōu)化內(nèi)容獲取與容量的蜂窩關(guān)聯(lián)方案

張文天,王祿生,林 海,方 超

(1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230601; 2.武漢大學(xué) 國(guó)家網(wǎng)絡(luò)安全學(xué)院,湖北 武漢 430072)

0 引 言

近年來,無線移動(dòng)通信技術(shù)迅猛發(fā)展,第五代移動(dòng)通信系統(tǒng)(5G)將達(dá)到更高的數(shù)據(jù)速率、更大的系統(tǒng)容量、更低的傳輸時(shí)延以及更好的服務(wù)質(zhì)量。高密度網(wǎng)絡(luò)是5G關(guān)鍵技術(shù)之一,通過在傳統(tǒng)大功率宏蜂窩的覆蓋范圍內(nèi)大規(guī)模密集部署低功率微微蜂窩和飛蜂窩,縮短終端與服務(wù)基站之間的“距離”以提升終端接入后獲得的頻譜效率和系統(tǒng)吞吐量[1];其次,隨著智能終端的迅速普及,移動(dòng)網(wǎng)絡(luò)中多媒體業(yè)務(wù)的需求正以驚人的速度增長(zhǎng)。然而,當(dāng)前蜂窩網(wǎng)絡(luò)的集中式架構(gòu)會(huì)造成核心網(wǎng)擁塞程度增大與回程鏈路帶寬偏小以致于難以應(yīng)對(duì)移動(dòng)通信流量爆炸式增長(zhǎng)的問題,因此相關(guān)研究普遍認(rèn)為應(yīng)把各種媒體信息推送到距離移動(dòng)終端較近的網(wǎng)絡(luò)邊緣,以減少核心網(wǎng)流量并提高對(duì)終端的服務(wù)質(zhì)量[2-4]。

傳統(tǒng)方法指出,終端可以關(guān)聯(lián)到某方面最大化的基站,如最大接收信號(hào)強(qiáng)度、最大信干噪比、最大信道容量等。一種業(yè)界熟知的方案是蜂窩范圍擴(kuò)展(cell range expansion,CRE),擴(kuò)大小蜂窩關(guān)聯(lián)范圍以提升網(wǎng)絡(luò)容量或公平性[5]。文獻(xiàn)[6]研究了一種基于能效的蜂窩關(guān)聯(lián)算法,其優(yōu)化目標(biāo)為最大化能效,并可分布式地得到一個(gè)較優(yōu)解。文獻(xiàn)[7]提出了一種通過求解對(duì)數(shù)效用函數(shù)最優(yōu)來獲取關(guān)聯(lián)策略的方法,通過松弛約束條件轉(zhuǎn)化為凸優(yōu)化問題并求解其拉格朗日對(duì)偶問題。還有一些研究通過組合優(yōu)化來求解,如文獻(xiàn)[8]通過求解基于二部圖的匹配問題來獲取蜂窩關(guān)聯(lián)策略;文獻(xiàn)[9]將蜂窩關(guān)聯(lián)問題轉(zhuǎn)化為二部圖匹配問題,并采用貪婪算法求解。

然而這些方案在做蜂窩關(guān)聯(lián)時(shí)均沒有考慮終端接入基站后獲取媒體信息內(nèi)容所需的傳輸路徑。未來5G網(wǎng)絡(luò)邊緣部署著高密度的小蜂窩,內(nèi)容一般會(huì)在一些小蜂窩中存儲(chǔ),通過以上方案進(jìn)行蜂窩關(guān)聯(lián)會(huì)帶來一個(gè)嚴(yán)重問題,即所關(guān)聯(lián)蜂窩需要小蜂窩之間較長(zhǎng)的路徑來傳輸該內(nèi)容。就業(yè)務(wù)實(shí)時(shí)性而言,傳輸時(shí)延是非常重要的因素,因此讓內(nèi)容獲取路徑盡量短是非常重要的。近年來關(guān)于內(nèi)容獲取的研究正在逐步展開,文獻(xiàn)[10]根據(jù)流行度來實(shí)現(xiàn)內(nèi)容分布式緩存,通過將流行的內(nèi)容部署在終端附近,來減少服務(wù)器負(fù)載；文獻(xiàn)[11]提出了一種基于Stackelberg博弈模型的邊緣緩存方案來緩存視頻；文獻(xiàn)[12]提出了一種主動(dòng)緩存機(jī)制,借助移動(dòng)邊緣計(jì)算架構(gòu)的協(xié)同緩存學(xué)習(xí)策略與貪婪算法來解決內(nèi)容部署問題。

為了使網(wǎng)絡(luò)中的終端整體上均獲得較好的服務(wù)質(zhì)量,本文提出了一種聯(lián)合優(yōu)化內(nèi)容獲取路徑與系統(tǒng)容量的蜂窩關(guān)聯(lián)方案。首先利用貪婪算法求出內(nèi)容在小蜂窩中的近似最優(yōu)部署,再通過虛擬基站的方法將該問題轉(zhuǎn)化為二部圖的最優(yōu)匹配,最后用匈牙利算法求得最優(yōu)解。仿真結(jié)果表明,該方案可在多項(xiàng)式時(shí)間內(nèi)得到一個(gè)對(duì)應(yīng)效用函數(shù)最大化的蜂窩關(guān)聯(lián)策略,并盡量減小內(nèi)容獲取路徑的平均跳數(shù)。

1 系統(tǒng)模型

本文考慮有限地域范圍內(nèi)一個(gè)宏蜂窩和多個(gè)小蜂窩構(gòu)成的5G異構(gòu)網(wǎng)絡(luò),小蜂窩基站之間的媒體信息內(nèi)容傳輸是通過光纖完成的。網(wǎng)絡(luò)中有M個(gè)基站(包括宏基站和小基站),表示為{Ωi|i=1,…,M}。當(dāng)前有內(nèi)容請(qǐng)求的終端有N個(gè),表示為{Uq|q=1,…,N},并簡(jiǎn)化假設(shè)每個(gè)終端僅有一個(gè)內(nèi)容請(qǐng)求。

若Uq接入到Ωi,則Uq的上行信號(hào)與干擾加噪比(signal to interference plus noise ratio,SINR)表示為:

(1)

其中:Pq,i為Uq到Ωi的有效信號(hào)功率;N0為加性高斯白噪聲;Ii,up為Ωi受到的來自接入周圍基站的終端的上行平均干擾。因此,Uq獲得的上行系統(tǒng)容量表示為:

(2)

其中:B為系統(tǒng)帶寬;ni為接入Ωi的終端數(shù)量。ni表示為:

(3)

其中,bq,i為一個(gè)0/1整數(shù)變量,1表示Uq接入Ωi,0表示未接入。

Uq所獲得的下行系統(tǒng)容量表示為:

(4)

其中,ψq,i,down為Uq接入Ωi的下行SINR,其計(jì)算方法與(1)式相同。

假設(shè)基站的存儲(chǔ)有限,只能放入一個(gè)內(nèi)容,且同一種內(nèi)容部署在K個(gè)基站中。當(dāng)Uq接入到Ωi后通過該基站獲取內(nèi)容的最小跳數(shù)為Si。在某時(shí)間段內(nèi),Ωi有ni個(gè)內(nèi)容請(qǐng)求。若Ωi內(nèi)有該內(nèi)容,則Si為0,進(jìn)而傳輸開銷為0。否則,接入Ωi的每個(gè)終端收到該內(nèi)容的平均傳輸開銷為Siβ/ni,其中β表示單跳開銷。(4)式除以ni的原因在于,該內(nèi)容傳至Ωi之后在某時(shí)間段內(nèi)該內(nèi)容仍存儲(chǔ)在其緩存內(nèi),因此這ni個(gè)終端都可以直接從Ωi獲取到該內(nèi)容,而不需要將該內(nèi)容從遠(yuǎn)端基站反復(fù)傳至Ωi。當(dāng)內(nèi)容在網(wǎng)絡(luò)中的部署已定時(shí),蜂窩關(guān)聯(lián)優(yōu)化問題的目標(biāo)函數(shù)可以表示為:

(5)

s.t.C1:bq,i∈{0,1},1≤i≤M;

其中:λ為上行業(yè)務(wù)占總傳輸業(yè)務(wù)的比率;ε用于表征系統(tǒng)容量和小蜂窩之間內(nèi)容獲取開銷的權(quán)重,取值在0～1之間;C2確保了每個(gè)終端只能接入一個(gè)基站。效用函數(shù)取對(duì)數(shù)對(duì)應(yīng)比例公平,它在實(shí)際問題上比直接優(yōu)化效用函數(shù)應(yīng)用更廣泛[13]。

如果內(nèi)容在網(wǎng)絡(luò)中的部署未知,可以用一個(gè)0/1整數(shù)變量來表征內(nèi)容在基站中的部署情況:

(6)

于是可以將內(nèi)容部署建模為圖的最短路徑問題。由于不能給出一個(gè)簡(jiǎn)單的閉式解,需要用ai的函數(shù)來表示,即

Si=ming(ai)

(7)

于是問題(5)改為:

(8)

s.t.C1:ai∈{0,1}；

C2:bq,i∈{0,1},?i∈Ω；

2 蜂窩關(guān)聯(lián)的聯(lián)合優(yōu)化方案

因?yàn)?5)式和(8)式均涉及蜂窩關(guān)聯(lián)和內(nèi)容部署2個(gè)問題,導(dǎo)致直接求解比較復(fù)雜,所以需要將問題進(jìn)行轉(zhuǎn)化。

2.1 基于內(nèi)容隨機(jī)部署的聯(lián)合優(yōu)化方案

基于內(nèi)容隨機(jī)部署的方案是將內(nèi)容部署在一些隨機(jī)選定的基站中。由于內(nèi)容是隨機(jī)部署在基站中的,該方案的關(guān)鍵是優(yōu)化終端的關(guān)聯(lián)。

對(duì)于(5)式,可以將其轉(zhuǎn)化為：

(9)

參照文獻(xiàn)[7]的方法,通過將基站分解為虛擬基站,使終端與真實(shí)基站的關(guān)聯(lián)轉(zhuǎn)化為終端和虛擬基站的匹配。虛擬基站分解方法如圖1所示?；緄用虛擬基站B(i)代替,因?yàn)橛?個(gè)終端,所以B(i)由4個(gè)虛擬基站構(gòu)成,圖1a中與基站i相關(guān)聯(lián)的終端2、3轉(zhuǎn)化為分別與B(i)的前2個(gè)虛擬基站相連。

圖1 虛擬基站分解方法

將終端與基站多對(duì)一關(guān)聯(lián)下的權(quán)值求和轉(zhuǎn)化為終端與虛擬基站的匹配權(quán)值之和,可以構(gòu)造出終端和基站匹配的N×NM維虛擬權(quán)值矩陣,其元素可表示為:

(10)

其中,t為虛擬基站的序號(hào)。

因此(9)式等價(jià)于以下二部圖匹配問題,可以利用匈牙利算法獲得最優(yōu)解。

(11)

2.2 基于內(nèi)容貪婪式部署的聯(lián)合優(yōu)化方案

上一節(jié)提出的基于內(nèi)容隨機(jī)部署的方案,因?yàn)閮?nèi)容隨機(jī)部署會(huì)導(dǎo)致獲取內(nèi)容的平均跳數(shù)較大,所以需要設(shè)計(jì)更優(yōu)的內(nèi)容部署方案。對(duì)于(8)式,因?yàn)镾i是不確定的值,不能直接以(5)式的方式進(jìn)行轉(zhuǎn)化,所以需要先給出一個(gè)近似最優(yōu)的內(nèi)容部署策略,即先利用某種算法求出一個(gè)近似最優(yōu)的ai部署策略,然后在此基礎(chǔ)上完成對(duì)(8)式的求解,具體求解方式與(5)式相同。

本文設(shè)計(jì)了一種基于貪婪式內(nèi)容部署的蜂窩關(guān)聯(lián)算法,流程圖如圖2所示。

具體算法步驟如下:

(1) 以基站為節(jié)點(diǎn),由基站間連線形成一幅連通圖,表示為G(V,E),其中V表示基站集合,E表示邊的集合,E可以通過給定的閾值d-thd判斷基站之間是否有連接得到,然后再利用Dijkstra算法計(jì)算出M×M維的基站間跳數(shù)矩陣H。

(2) 根據(jù)H和給定的內(nèi)容部署數(shù)K,通過貪婪算法求出Si。

貪婪算法描述如下:①對(duì)于任一基站,求出其到其余基站的跳數(shù)總和,該步驟是對(duì)H每一列進(jìn)行求和,選出到所有其他基站跳數(shù)之和最小的基站,將內(nèi)容部署在該基站。當(dāng)K=1時(shí),這里求出的就已對(duì)應(yīng)最優(yōu)內(nèi)容部署。②當(dāng)K≥2時(shí),需要將算法此前已經(jīng)選出的內(nèi)容部署基站到其他基站的跳數(shù)與任一基站到其他基站的跳數(shù)一一做差對(duì)比,并將較小的跳數(shù)值放入到對(duì)應(yīng)的H里,更新H。這是因?yàn)楫?dāng)某一基站部署內(nèi)容后,H需要根據(jù)該基站到其他基站的跳數(shù)和剩余基站到其他基站的跳數(shù)比較后更新,以作為下一次迭代的輸入。③對(duì)步驟①、步驟②迭代K次,從而得到K個(gè)需要部署內(nèi)容的基站。

3 性能仿真結(jié)果分析

仿真實(shí)驗(yàn)中,本文設(shè)置了1個(gè)宏蜂窩,若干個(gè)小蜂窩。其中宏蜂窩的半徑為500 m,宏基站和小基站的傳輸功率分別置為46 dBm和21 dBm,終端的發(fā)射功率為30 dBm,帶寬為1 MHz,信道路徑損耗模型采用近距離自由空間路徑損耗模型(close-in free space reference distance pathloss,CI-FSPL)[14],λ=0.5,ε=0.2,β=6×104。

3.1 單內(nèi)容部署和蜂窩關(guān)聯(lián)方案的性能對(duì)比

1個(gè)宏蜂窩、10個(gè)小蜂窩和100個(gè)終端,選擇最大SINR[15]和基于匈牙利算法[9]這2種蜂窩關(guān)聯(lián)方案與本文方案進(jìn)行對(duì)比。最大SINR算法是求解蜂窩關(guān)聯(lián)最經(jīng)典的算法之一,而基于匈牙利算法的蜂窩關(guān)聯(lián)算法可以求出最優(yōu)系統(tǒng)容量?；诓煌桨傅姆涓C關(guān)聯(lián)結(jié)果如圖3所示。圖3中：菱形表示部署的內(nèi)容；綠色表示關(guān)聯(lián)到宏蜂窩；黑色表示關(guān)聯(lián)到小蜂窩。圖3a中大多數(shù)終端均關(guān)聯(lián)到宏蜂窩,是因?yàn)榻K端關(guān)聯(lián)到宏蜂窩的SINR比較大。圖3b～圖3d中大多數(shù)終端會(huì)關(guān)聯(lián)到小蜂窩,是因?yàn)榛镜膸捰邢?所以與最大SINR相比,大多數(shù)終端會(huì)關(guān)聯(lián)到小蜂窩。圖3c、圖3d中終端關(guān)聯(lián)到小蜂窩要多,是因?yàn)槠溥€考慮了內(nèi)容獲取路徑對(duì)蜂窩關(guān)聯(lián)的影響。

圖3 不同方案的蜂窩關(guān)聯(lián)結(jié)果對(duì)比

不同蜂窩關(guān)聯(lián)方案的系統(tǒng)總效用對(duì)比如圖4所示,從圖4可以看出：隨著部署內(nèi)容的基站數(shù)量在增加；效用函數(shù)Zm的值在增加,且與其他算法相比,本文提出的基于內(nèi)容貪婪式部署的方案的系統(tǒng)總效用最大。

不同蜂窩關(guān)聯(lián)方案的平均跳數(shù)如圖5所示。從圖5可以看出,隨著部署內(nèi)容的基站數(shù)量增加,所有方案的平均跳數(shù)均逐漸減小,而本文方案明顯優(yōu)于最大SINR和基于匈牙利算法的方案,其中基于內(nèi)容貪婪式部署的方案性能最好。以K=6為例,獲取內(nèi)容的平均跳數(shù)與基于匈牙利算法的方案相比降低了16.6 %,與最大SINR的方案相比降低了54.5%?；诓煌涓C關(guān)聯(lián)方案的終端系統(tǒng)容量總和如圖6所示。從圖6可以看出,最大SINR的終端系統(tǒng)容量最大。雖然本文提出的方案在系統(tǒng)容量方面與最大SINR方案相比有些差距,但與其他優(yōu)化方案相比在系統(tǒng)容量方面沒有降低。

圖4 不同方案的系統(tǒng)總效用對(duì)比

圖5 不同方案的平均跳數(shù)

圖6 基于不同蜂窩關(guān)聯(lián)方案的終端系統(tǒng)容量總和

3.2 多內(nèi)容部署和蜂窩關(guān)聯(lián)方案的性能對(duì)比

假設(shè)網(wǎng)絡(luò)中存在2種內(nèi)容,且部署數(shù)量一樣多。這2種內(nèi)容也是根據(jù)貪婪算法進(jìn)行內(nèi)容部署的,不同之處在于先利用貪婪算法在一些基站中部署其中一種內(nèi)容,然后在剩余的基站中再次利用貪婪算法部署另外一種內(nèi)容。

對(duì)2種內(nèi)容、1個(gè)宏蜂窩、10個(gè)小蜂窩和100個(gè)終端的情況進(jìn)行仿真?；诓煌桨傅姆涓C關(guān)聯(lián)結(jié)果如圖7所示,圖7中藍(lán)色和紅色的點(diǎn)分別表示部署了2種不同內(nèi)容的基站。

圖7 不同方案的蜂窩關(guān)聯(lián)結(jié)果對(duì)比

2種內(nèi)容的不同蜂窩關(guān)聯(lián)方案的系統(tǒng)總效用對(duì)比、不同蜂窩關(guān)聯(lián)方案的平均跳數(shù)和不同蜂窩關(guān)聯(lián)方案的終端系統(tǒng)容量總和如圖8～圖10所示,可以看出與部署單內(nèi)容時(shí)的結(jié)果基本相同。

圖8 不同方案的系統(tǒng)總效用對(duì)比

圖9 不同方案的平均跳數(shù)

從圖5和圖9的比較可看出，當(dāng)內(nèi)容種類增多時(shí),本文提出的方案平均跳數(shù)相對(duì)增加,其原因是基站的存儲(chǔ)有限。

圖10 基于不同蜂窩關(guān)聯(lián)方案的終端系統(tǒng)容量總和

4 結(jié) 論

本文通過將內(nèi)容獲取路徑和蜂窩關(guān)聯(lián)聯(lián)合考慮,提出一種聯(lián)合優(yōu)化內(nèi)容獲取路徑與系統(tǒng)容量的蜂窩關(guān)聯(lián)方案。該方案使用虛擬基站的方法,將效用函數(shù)最大化問題轉(zhuǎn)化為基于二部圖的最優(yōu)匹配,并利用匈牙利算法求得最優(yōu)解。通過仿真發(fā)現(xiàn)提出的方案比以往方案效用函數(shù)更大,且時(shí)延較小,即較傳統(tǒng)方案而言更適合于高密度網(wǎng)絡(luò)。由于未來網(wǎng)絡(luò)中將部署大量的媒體信息內(nèi)容,因此在以后的研究中需要將該方案擴(kuò)展至基站存儲(chǔ)更多內(nèi)容的場(chǎng)景中去。