余 江， 邱 玲

(中國科學技術(shù)大學中國科學院無線光電通信重點實驗室，合肥 230027)(2016年1月7日收稿； 2016年3月2日收修改稿)

隨著互聯(lián)網(wǎng)的高速發(fā)展，據(jù)工業(yè)界預(yù)計，第5代移動通信系統(tǒng)的容量需提升1 000倍[1]．為應(yīng)對海量數(shù)據(jù)增長，增加小站密度，實現(xiàn)密集組網(wǎng)極具前景．在密集小站網(wǎng)絡(luò)下，由于小站數(shù)量激增，為節(jié)省成本，考慮采用銅纜或毫米波部署回程鏈路，而這可能導致小站回程鏈路容量受限[2]．為克服該限制，一種有效的方案是在小站上部署緩存[3]，若用戶請求文件在緩存中，小站直接通過無線鏈路傳輸該文件；否則需經(jīng)由回程鏈路從核心網(wǎng)中獲取，再通過無線鏈路傳輸該文件，使得用戶的傳輸速率不僅與無線信道條件有關(guān)，還受限于回程鏈路容量．另一方面，小站在考慮接入哪些用戶時，除考慮信干燥比等因素外，還需考慮用戶請求文件在緩存中的命中率．因此，如何決策緩存內(nèi)容以提高命中率，并基于此優(yōu)化用戶歸屬有待研究．

目前，學術(shù)界已逐漸聚焦對該問題的研究[4-8]．由于緩存容量有限，合理預(yù)測用戶未來請求，并根據(jù)文件流行性確定緩存內(nèi)容以提高命中率顯得尤為重要．一種常見的簡化方案是假設(shè)文件全局流行性服從Zipf分布[4-5]．基于該假設(shè)，Pantisano等[6]提出一種緩存協(xié)助的最大化系統(tǒng)吞吐量的用戶歸屬算法；Zhou等[7]提出一種最大化小站和用戶能量效率的用戶歸屬方案．然而Zink等[8]指出局域網(wǎng)內(nèi)，Youtube上視頻文件的全局流行度和局部流行度的關(guān)聯(lián)度并不大．假設(shè)文件全局流行度服從Zipf分布盡管合理，但卻失去了利用文件局部流行性和關(guān)聯(lián)做出更精準預(yù)測的能力．進一步，Pantisano等[9]利用用戶行為信息預(yù)測其請求文件的概率，提出一種最小化小站回程鏈路帶寬分配的用戶歸屬算法．然而，在緩存內(nèi)容決策上，文獻[9]和文獻[6-7]類似，仍采用隨機緩存策略或緩存最受歡迎文件，未考慮緩存內(nèi)容的優(yōu)化決策．因此，如何基于用戶歷史行為更精準地決策緩存內(nèi)容，并基于此確定用戶歸屬有待研究．

基于上述研究現(xiàn)狀，本文利用基于用戶的Top N協(xié)作濾波推薦系統(tǒng)[10]決策小站緩存內(nèi)容，提出一種最大化系統(tǒng)吞吐量的低復(fù)雜度用戶歸屬方案．基于用戶的Top N協(xié)作濾波推薦系統(tǒng)通過計算用戶間的相似性，為用戶推薦與其相似用戶請求過而該用戶尚未請求的文件，進而預(yù)測用戶未來請求，以在小站緩存最可能被盡可能多用戶請求的文件，提高緩存命中率．具體地，問題解決分2個階段．首先根據(jù)用戶歷史行為確定小站緩存內(nèi)容．隨后根據(jù)緩存內(nèi)容確定用戶歸屬．為保證用戶間的比例公平，形成用戶間吞吐量比例約束下的系統(tǒng)吞吐量最大化問題．由于該問題為混合整數(shù)規(guī)劃問題，難以直接求解，因此本文提出一種低復(fù)雜度歸屬算法．通過對用戶未來請求文件更精準的預(yù)測及其歸屬的優(yōu)化，所提方案提升了系統(tǒng)性能，緩解了回程鏈路壓力．

1 系統(tǒng)模型

考慮由N個小站及M個用戶組成的密集小站網(wǎng)絡(luò)的下行鏈路傳輸，如圖1所示．該網(wǎng)絡(luò)中，小站和用戶集合分別表示為：S={1,2,…,N}和U={1,2,…,M}．

圖1 系統(tǒng)模型Fig.1 System model

每個小站通過回程鏈路連接到核心網(wǎng)，小站i的回程鏈路容量為Bi，配置容量為Qi的緩存，存儲從文件庫F下載的部分文件子集Ci?F．每個用戶j請求一系列文件Fj={f1,…,fm}?F，簡單起見，假設(shè)所有文件大小相等，為s．設(shè)小站i的傳輸功率為Pi，小站i和用戶j間的信道增益為hij，其中包括路徑損耗和小尺度衰落．W為系統(tǒng)帶寬，因此，根據(jù)香農(nóng)公式可得用戶j歸屬到小站i時可達傳輸速率為

(1)

其中，N0為噪聲功率，Ij表示所有干擾用戶j的小站集合，即Ij={Si}．設(shè)小站i對用戶j的資源分配比例為βij，考慮用戶以時分復(fù)用多址接入(TDMA)，即βij為實變量，故有∑j∈Uβij=1．

2 緩存內(nèi)容決策和用戶歸屬

2.1 基于協(xié)作濾波的緩存內(nèi)容決策

由于用戶行為信息多為僅記錄用戶操作的隱式信息，因此，相較于評分預(yù)測推薦系統(tǒng)，Top N推薦系統(tǒng)更適合預(yù)測用戶未來請求．同時，在密集小站網(wǎng)絡(luò)下，由于用戶數(shù)遠小于其可能請求的文件庫大小，即M?|F|，該場景下，基于用戶的協(xié)作濾波推薦系統(tǒng)相較基于物品的協(xié)作濾波推薦系統(tǒng)，計算復(fù)雜度更低．因此，本文利用基于用戶的Top N協(xié)作濾波推薦系統(tǒng)預(yù)測用戶未來請求，并依此決策緩存內(nèi)容，以在性能和復(fù)雜度間取得折中．

所提基于用戶的Top N協(xié)作濾波推薦系統(tǒng)利用用戶間相似性計算文件間相關(guān)性以預(yù)測用戶未來請求文件．用戶間相似性[10]通過余弦相似性計算如下：

(2)

其中，N(u)和N(j)分別表示用戶u,j請求過的文件集合．因此，對于小區(qū)內(nèi)的用戶u，計算與其最相似的K個用戶集合為S(u,K)={u1,u2，…,uK}，則對于用戶u，可預(yù)測其未來請求文件如下．首先，構(gòu)建候選預(yù)測文件集合為

(3)

即將與用戶u最相似的K個用戶請求過而用戶u未請求的文件作為候選預(yù)測文件．隨后，計算用戶u對Ru中每個文件f的感興趣程度為

(4)

步驟1(預(yù)測用戶未來請求文件)：

1)計算用戶間相似度wuj,?u,j∈U；

2)?u∈U，確定其K鄰近用戶集合S(u,K)及其候選預(yù)測文件集合Ru；

步驟2(確定緩存內(nèi)容)：

確定小站i的緩存內(nèi)容為

hitRatio(i)=(∑j∈Mmij/|Fj|)/M.

(5)

2.2 最大化系統(tǒng)吞吐量的用戶歸屬策略

(6)

C3:L1:L2:…:LM=η1:η2:…:ηM.

其中，約束1表示每個用戶最多接入一個小站，約束3表示用戶間吞吐量的比例約束．由于P0為混合整數(shù)規(guī)劃問題，難以直接求解．因此放松用戶僅能接入一個小站的限制，允許用戶同時接入多個小站，即xij=1,?i,j，則原問題可轉(zhuǎn)化為

P1為標準線性規(guī)劃問題，其最優(yōu)解存在且唯一，可通過內(nèi)點法等凸優(yōu)化方法求得[11]．由于用戶可接入多個小站，該最優(yōu)解提供了原問題的一個性能上界．然而一方面由于內(nèi)點法的求解復(fù)雜度過高為O(M3N3)，另一方面允許用戶接入多個小站實現(xiàn)復(fù)雜，因此亟需設(shè)計用戶接入單小站時的低復(fù)雜度算法．注意到此時用戶間吞吐量的比例約束可能難以滿足，為使問題可解，放松P1中的等式約束(C3)，最大化最小歸一化吞吐量y，形成P1的近似問題為

問題P2的拉格朗日函數(shù)為

(7)

其中，λj≥0,δi≥0,μij≥0為拉格朗日乘子．求其KKT條件如下：

?J/?βij=λjbij/ηj-δi+μij=0,?i,j.

(8)

μijβij=0,?i,j.

(9)

根據(jù)式(8)、式(9)可得下述引理：

引理2.1對于小站i和k存在最優(yōu)偏置因子θik，使得用戶j在bij/bkj>θik時接入小站i，在bij/bkj<θik時接入小站k．

引理2.1可通過文獻[12]中類似的方法證明，不再贅述．由引理2.1可知，用戶j對小站i，k的選擇依賴于用戶j在小站i，k間基礎(chǔ)吞吐量的比值bij/bkj，bij/bkj最小的用戶有優(yōu)先切換到小站k的權(quán)利．并且對于小站i，用戶間吞吐量滿足比例約束時其歸一化吞吐量yi可表示為

yi=(βi1bi1+ci1)/η1=…

=(βi|Ai|bi|Ai|+ci|Ai|)/η|Ai|

=(1+∑j∈Aicij/bij)/(∑j∈Aiηj/bij).

(10)

其中，Ai為接入小站i的用戶集合．式(10)中最后一項根據(jù)∑j∈Aiβij=1得到．因此根據(jù)上述對P2最優(yōu)解的分析，提出用戶接入單個小站時的低復(fù)雜度歸屬算法如下

步驟1(用戶預(yù)歸屬)：根據(jù)最大信干燥比原則預(yù)歸屬用戶到相應(yīng)小站；

步驟2(歸屬更新)：

1)根據(jù)式(10)計算各小站歸一化吞吐量yi,?i；

2)計算ψik=yi-yk，令Ψ={ψik|ψik<0,?i,k}；

3)尋找歸一化吞吐量差距最大的2個小站

(i′,k′)←argminψik∈Ψψik；

4)尋找接入小站i′的用戶中具有最小基礎(chǔ)吞吐量比值的用戶：j′=argminj∈Ai′bi′j/bk′j；

6)移除各小站中最近最不常使用的文件，更新各小站緩存；

7)循環(huán)步驟2，直到Ψ=?．

上述算法表明當小站i′切換用戶j′到小站k′后，小站k′的歸一化吞吐量仍大于小站i′的歸一化吞吐量時，才執(zhí)行切換，因此可保證每次迭代最小歸一化吞吐量單調(diào)不減，從而保證算法的收斂性．

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

仿真中設(shè)M=200個用戶和N=[60,300]個小站均勻分布在500 m×500 m的小區(qū)內(nèi)，路徑損耗為L(d)=128.1+37.6lgd，小站和用戶間的信道服從獨立同分布瑞利衰落．系統(tǒng)帶寬為20 MHz，小站的傳輸功率為33 dBm，噪聲功率為-114 dBm，小站回程鏈路容量Bi=[10,100]Mbps．仿真中采用Movielens數(shù)據(jù)集[13]建模用戶請求，設(shè)每個用戶請求3 900部電影中的15部電影，各用戶間吞吐量的比例約束為η1∶η2∶…∶nM=1∶1∶…∶1．

為比較算法間性能差異，考慮下列對比算法．對比算法1為最大信干燥比算法[7]，該算法歸屬用戶到接收信干燥比最大的小站，且小站上無緩存．對比算法2在此基礎(chǔ)上，考慮文件流行度服從Zipf分布，在小站上緩存文件庫中最受歡迎文件．

圖2、圖3對比不同算法的緩存命中率．從圖2可以看出，隨著緩存文件數(shù)的增多，所提算法和對比算法2的緩存命中率均增加，且相較對比算法2有明顯增益，當緩存文件數(shù)大于等于100時，所提算法增益均在10%以上．在固定緩存文件數(shù)為100時，圖3顯示隨著用戶數(shù)的增多，所提算法的增益愈發(fā)明顯，這是因為隨著用戶歷史行為信息的增多，能通過所提緩存決策算法挖掘的個性化信息也越多．

圖4展示小站回程鏈路容量Bi=10 Mbps時，系統(tǒng)吞吐量和小站數(shù)的關(guān)系．可以看出，所提算法相較2種對比算法有明顯的增益，尤其是在小站部署密度較大時，如小站數(shù)為220時，所提算法相較對比算法1、2的增益分別為19.1%和11.3%.這是因為所提算法一方面通過提升緩存命中率帶來增益，另一方面在歸屬用戶時使各小站間的負載盡可能均衡，減少了空閑小站數(shù)，進而帶來了性能提升．

圖2 緩存文件數(shù)與命中率關(guān)系Fig.2 Number of cache files versus hit ratio

圖3 用戶數(shù)與命中率關(guān)系Fig.3 Number of users versus hit ratio

圖5給出小站數(shù)為200時，系統(tǒng)吞吐量與小站回程鏈路容量的關(guān)系圖．隨著回程鏈路容量的增加，其容量逐漸不再受限，因此3種算法的系統(tǒng)吞吐量先增加最終趨于穩(wěn)定．所提算法相較對比算法仍有明顯增益，這是因為緩存命中率的提高在回程鏈路容量較小時會帶來較大增益，而在回程鏈路容量充足時，合理的用戶歸屬會帶來較大增益．

圖4 小站數(shù)目與系統(tǒng)吞吐量關(guān)系Fig.4 Number of small cells versus throughput

圖5 回程鏈路容量與系統(tǒng)吞吐量關(guān)系Fig.5 Backhaul bandwidth versus throughput

4 結(jié)束語

本文提出一種密集小站下，基于協(xié)作濾波的緩存內(nèi)容決策和用戶歸屬算法．本文首先利用基于用戶的Top N協(xié)作濾波推薦系統(tǒng)確定小站緩存內(nèi)容，以提高緩存命中率．隨后形成一個系統(tǒng)吞吐量最大化的用戶歸屬問題．通過放松約束條件，得出用戶對小站的選擇與其在不同小站的基礎(chǔ)吞吐量之比相關(guān)的結(jié)論，并提出一種低復(fù)雜度歸屬算法．通過對緩存內(nèi)容更精準的決策和用戶歸屬的優(yōu)化，所提算法相較已有算法在緩存命中率和系統(tǒng)吞吐量上有明顯增益，緩解了回程鏈路壓力，提升了服務(wù)質(zhì)量．