密集小站網(wǎng)絡下基于協(xié)作濾波的緩存內(nèi)容決策和用戶歸屬*

余 江， 邱 玲

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

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

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

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

1 系統(tǒng)模型

考慮由N個小站及M個用戶組成的密集小站網(wǎng)絡的下行鏈路傳輸，如圖1所示．該網(wǎng)絡中，小站和用戶集合分別表示為：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，簡單起見，假設所有文件大小相等，為s．設小站i的傳輸功率為Pi，小站i和用戶j間的信道增益為hij，其中包括路徑損耗和小尺度衰落．W為系統(tǒng)帶寬，因此，根據(jù)香農(nóng)公式可得用戶j歸屬到小站i時可達傳輸速率為

(1)

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

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

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

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

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

(2)

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

(3)

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

(4)

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

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

2)?u∈U，確定其K鄰近用戶集合S(u,K)及其候選預測文件集合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，則原問題可轉化為

P1為標準線性規(guī)劃問題，其最優(yōu)解存在且唯一，可通過內(nèi)點法等凸優(yōu)化方法求得[11]．由于用戶可接入多個小站，該最優(yōu)解提供了原問題的一個性能上界．然而一方面由于內(nèi)點法的求解復雜度過高為O(M3N3)，另一方面允許用戶接入多個小站實現(xiàn)復雜，因此亟需設計用戶接入單小站時的低復雜度算法．注意到此時用戶間吞吐量的比例約束可能難以滿足，為使問題可解，放松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間基礎吞吐量的比值bij/bkj，bij/bkj最小的用戶有優(yōu)先切換到小站k的權利．并且對于小站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)解的分析，提出用戶接入單個小站時的低復雜度歸屬算法如下

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

步驟2(歸屬更新)：

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

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

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

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

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

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

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

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

3 仿真結果與分析

仿真中設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]建模用戶請求，設每個用戶請求3 900部電影中的15部電影，各用戶間吞吐量的比例約束為η1∶η2∶…∶nM=1∶1∶…∶1．

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

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

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

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

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

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

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

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

4 結束語

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