余江, 邱玲
中国科学技术大学中国科学院无线光电通信重点实验室, 合肥 230027
2016年01月07日 收稿; 2016年03月02日 收修改稿
基金项目: 863计划项目（2014AA01A702）资助
通信作者: 邱玲,E-mail:lqiu@ustc.edu.cn

摘要: 为应对信息的爆炸式增长，在小站上部署缓存以缓解回程链路压力显得尤为重要.考虑到用户历史行为中蕴含大量个性化信息，采用基于用户的Top N协作滤波推荐系统预测用户未来请求以确定缓存内容，并提出一种最大化系统吞吐量的用户归属方案.通过放松约束条件，得到用户归属与其在小站间吞吐量之比的关系，提出一种低复杂度归属算法.仿真结果表明所提算法比已有算法在缓存命中率和系统吞吐量上均有明显增益.
关键词: 密集小站协作滤波缓存用户归属
Collaborative filtering-based cache determination and user association in dense small cell networks
YU Jiang, QIU Ling
Key Laboratory of Wireless-Optical Communications of Chinese Academy of Sciences, University of Science and Technology of China, Hefei 230027, China


Abstract: In response to the explosive increase of data, it is necessary to deploy cache in small cells to relieve the pressure of capacity-constrained backhauls. Considering vast personalized information implied in the user history logs, we utilize a user-based Top N collaborative filtering recommender system to predict user requests and determine cache contents, and propose a user association scheme maximizing the system throughput. Through relaxing the constraints, we find the relationship between user association and ratio of user throughput, and propose a low-complexity algorithm. Simulation results show the obvious gains in hit-ratio and system throughput compared to the existing algorithms.
Key words: dense small cellscollaborative filteringcacheuser association
随着互联网的高速发展，据工业界预计，第5代移动通信系统的容量需提升1 000倍^[1]．为应对海量数据增长，增加小站密度，实现密集组网极具前景．在密集小站网络下，由于小站数量激增，为节省成本，考虑采用铜缆或毫米波部署回程链路，而这可能导致小站回程链路容量受限^[2]．为克服该限制，一种有效的方案是在小站上部署缓存^[3]，若用户请求文件在缓存中，小站直接通过无线链路传输该文件；否则需经由回程链路从核心网中获取，再通过无线链路传输该文件，使得用户的传输速率不仅与无线信道条件有关，还受限于回程链路容量．另一方面，小站在考虑接入哪些用户时，除考虑信干燥比等因素外，还需考虑用户请求文件在缓存中的命中率．因此，如何决策缓存内容以提高命中率，并基于此优化用户归属有待研究．
目前，学术界已逐渐聚焦对该问题的研究^[4-8]．由于缓存容量有限，合理预测用户未来请求，并根据文件流行性确定缓存内容以提高命中率显得尤为重要．一种常见的简化方案是假设文件全局流行性服从Zipf分布^[4-5]．基于该假设，Pantisano等^[6]提出一种缓存协助的最大化系统吞吐量的用户归属算法；Zhou等^[7]提出一种最大化小站和用户能量效率的用户归属方案．然而Zink等^[8]指出局域网内，Youtube上视频文件的全局流行度和局部流行度的关联度并不大．假设文件全局流行度服从Zipf分布尽管合理，但却失去了利用文件局部流行性和关联做出更精准预测的能力．进一步，Pantisano等^[9]利用用户行为信息预测其请求文件的概率，提出一种最小化小站回程链路带宽分配的用户归属算法．然而，在缓存内容决策上，文献^[9]和文献^[6-7]类似，仍采用随机缓存策略或缓存最受欢迎文件，未考虑缓存内容的优化决策．因此，如何基于用户历史行为更精准地决策缓存内容，并基于此确定用户归属有待研究．
基于上述研究现状，本文利用基于用户的Top N协作滤波推荐系统^[10]决策小站缓存内容，提出一种最大化系统吞吐量的低复杂度用户归属方案．基于用户的Top N协作滤波推荐系统通过计算用户间的相似性，为用户推荐与其相似用户请求过而该用户尚未请求的文件，进而预测用户未来请求，以在小站缓存最可能被尽可能多用户请求的文件，提高缓存命中率．具体地，问题解决分2个阶段．首先根据用户历史行为确定小站缓存内容．随后根据缓存内容确定用户归属．为保证用户间的比例公平，形成用户间吞吐量比例约束下的系统吞吐量最大化问题．由于该问题为混合整数规划问题，难以直接求解，因此本文提出一种低复杂度归属算法．通过对用户未来请求文件更精准的预测及其归属的优化，所提方案提升了系统性能，缓解了回程链路压力．
1 系统模型考虑由N个小站及M个用户组成的密集小站网络的下行链路传输，如图 1所示．该网络中，小站和用户集合分别表示为：S={1,2,…,N}和U={1,2,…,M}．
Fig. 1

	Download: JPG larger image
图 1 系统模型 Fig. 1 System model

每个小站通过回程链路连接到核心网，小站i的回程链路容量为B_i，配置容量为Q_i的缓存，存储从文件库F下载的部分文件子集C_i?F．每个用户j请求一系列文件F_j={f₁,…,f_m}?F，简单起见，假设所有文件大小相等，为s．设小站i的传输功率为P_i，小站i和用户j间的信道增益为h_ij，其中包括路径损耗和小尺度衰落．W为系统带宽，因此，根据香农公式可得用户j归属到小站i时可达传输速率为

${{r}_{ij}}\left( t \right)=Wlo{{g}_{2}}\left( 1+\frac{{{P}_{i}}{{h}_{ij}}\left( t \right)}{{{\sum }_{k\in {{I}_{j}}}}{{P}_{k}}{{h}_{kj}}\left( t \right)+{{N}_{0}}} \right).$

(1)

其中，N₀为噪声功率，I_j表示所有干扰用户j的小站集合，即I_j={S\i}．设小站i对用户j的资源分配比例为β_ij，考虑用户以时分复用多址接入(TDMA)，即β_ij为实变量，故有${{\sum }_{j\in U}}{{\beta }_{ij}}=1$．
因此，当用户j归属到小站i，且其请求文件在C_i中时，小站直接传输该文件给用户，传输速率为r_ij¹(t)=β_ijr_ij(t)；当其请求的文件不在C_i中时，则需经由回程链路获取该文件，此时传输速率为r_ij²(t)=β_ijmin{r_ij(t),B_i}．注意到，当小站回程链路容量受限，即B_i＜r_ij(t)时，用户会经历与无线信道条件无关的服务质量下降．由此可见，缓存的加入使命中文件的传输速率不受限于回程链路容量，因此，亟需设计合理的缓存内容决策以提升服务质量．
2 缓存内容决策和用户归属2.1 基于协作滤波的缓存内容决策由于用户行为信息多为仅记录用户操作的隐式信息，因此，相较于评分预测推荐系统，Top N推荐系统更适合预测用户未来请求．同时，在密集小站网络下，由于用户数远小于其可能请求的文件库大小，即$M\ll \left| F \right|$，该场景下，基于用户的协作滤波推荐系统相较基于物品的协作滤波推荐系统，计算复杂度更低．因此，本文利用基于用户的Top N协作滤波推荐系统预测用户未来请求，并依此决策缓存内容，以在性能和复杂度间取得折中．
所提基于用户的Top N协作滤波推荐系统利用用户间相似性计算文件间相关性以预测用户未来请求文件．用户间相似性^[10]通过余弦相似性计算如下：

${{w}_{uj}}=\frac{\left| N\left( u \right)\cap N\left( j \right) \right|}{\left| N\left( u \right)N\left( j \right) \right|}.$

(2)

其中，N(u)和N(j)分别表示用户u,j请求过的文件集合．因此，对于小区内的用户u，计算与其最相似的K个用户集合为S(u,K)={u₁,u₂，…,u_K}，则对于用户u，可预测其未来请求文件如下．首先，构建候选预测文件集合为

${{R}_{u}}=\left\{ \underset{i\in S\left( u,K \right)}{\mathop{\cup }}\,N\left( i \right) \right\}\backslash N\left( u \right).$

(3)

即将与用户u最相似的K个用户请求过而用户u未请求的文件作为候选预测文件．随后，计算用户u对R_u中每个文件f的感兴趣程度为

$p\left( u,f \right)=\sum\limits_{j\in S\left( u,K \right),f\in R\left( u \right)}{{{w}_{uj}}{{r}_{jf}}}.$

(4)

其中，r_jf为用户j对文件f的评分，由于用户信息为隐式信息，因此用户请求过文件f时r_jf=1，否则r_jf=0．即用户u对文件f的感兴趣程度为用户u与S(u,K)中请求过f的用户的相似度之和．最后，根据用户的感兴趣程度，降序排列R_u中的文件，取其前N个文件集合F_pre^u作为对用户u未来请求的预测．因此，提出一种缓存决策算法如下
步骤1(预测用户未来请求文件)：
1) 计算用户间相似度w_uj,?u,j∈U；
2) ?u∈U，确定其K邻近用户集合S(u,K)及其候选预测文件集合R_u；
3) ?u∈U，计算用户对未请求文件的感兴趣程度p(u,f),?f∈R_u，确定用户未来请求文件预测集合为$F_{pre}^{u}=sort\left( p\left( u,f \right) \right)\left[ 0,N \right]$.
步骤2(确定缓存内容)：
确定小站i的缓存内容为

${{C}_{i}}=sort(popularity(\underset{j=1}{\overset{M}{\mathop{\cup }}}\,F_{pre}^{j}))\left[ 0:P \right].$

上述算法表明小站缓存内容通过在所有用户未来请求文件预测集合F_pre^j的并集中，取前P个最受欢迎的文件确定，其中P根据缓存容量大小确定，即$P=\left\lfloor {{Q}_{i}}/s \right\rfloor $．确定C_i后，当用户j请求文件集合F_j时，令m_ij=F_j∩C_i为用户j请求的文件集F_j在C_i中的命中数，则小站i的缓存命中率可表示为所有用户接入该小站时请求文件命中率的平均值，即

$hitRatio\left( i \right)=({{\sum }_{j\in M}}{{m}_{ij}}/\left| {{F}_{j}} \right|)/M.$

(5)

2.2 最大化系统吞吐量的用户归属策略考虑T时间内用户的吞吐量，令t_ij^cache=m_ijs/r_ij¹表示传输用户j在小站i缓存中命中文件的时间．当T较长，即满足t_ij^cache＜T时，T时间内用户j的吞吐量可表示为

$\begin{align} & {{L}_{j}}=\sum\limits_{i=1}^{N}{{{x}_{ij}}}\left( t_{_{ij}}^{cache}r_{ij}^{1}+\left( T-t_{_{ij}}^{cache} \right)r_{ij}^{2} \right) \\ & \sum\limits_{i=1}^{N}{{{x}_{ij}}}\left( {{\beta }_{ij}}{{b}_{ij}}+{{c}_{ij}} \right). \\ \end{align}$

(6)

其中，b_ij=Tmin{r_ij(t),B_i}表示小站没有部署缓存时，即用户请求的所有文件均需经由回程链路获取，T时间内用户j和小站i间的基础吞吐量；c_ij=m_ijs(1－r_ij²(t)/r_ij¹(t))，表示小站部署缓存后，部分文件命中，服务质量提升带来的额外吞吐量．由式(6)可知，用户吞吐量不仅与无线信道条件有关，还与缓存命中率及回程链路容量有关．因此，为保证用户间的比例公平，考虑用户间吞吐量比例约束下系统吞吐量最大化问题，形成用户归属问题如下：

$\begin{align} & P0:\max \sum\limits_{j=1}^{M}{{{L}_{j}}} \\ & s.t.C1:\sum\limits_{i=1}^{N}{{{x}_{ij}}}=1,\forall j;{{x}_{ij}}\in \left\{ 0,1 \right\},\forall i,j, \\ & C2:\sum\limits_{i=1}^{N}{{{\beta }_{ij}}}=1,\forall i;0\le {{\beta }_{ij}}\le 1,\forall i,j, \\ & C3:{{L}_{1}}:{{L}_{2}}:\cdots :{{L}_{M}}={{\eta }_{1}}:{{\eta }_{2}}:\cdots :{{\eta }_{M}}. \\ \end{align}$

其中，约束1表示每个用户最多接入一个小站，约束3表示用户间吞吐量的比例约束．由于P0为混合整数规划问题，难以直接求解．因此放松用户仅能接入一个小站的限制，允许用户同时接入多个小站，即x_ij=1,?i,j，则原问题可转化为

$P1:\max \sum\limits_{j=1}^{M}{{{L}_{j}}},s.t.\left( C2 \right)-\left( C3 \right).$

P1为标准线性规划问题，其最优解存在且唯一，可通过内点法等凸优化方法求得^[11]．由于用户可接入多个小站，该最优解提供了原问题的一个性能上界．然而一方面由于内点法的求解复杂度过高为O(M³N³)，另一方面允许用户接入多个小站实现复杂，因此亟需设计用户接入单小站时的低复杂度算法．注意到此时用户间吞吐量的比例约束可能难以满足，为使问题可解，放松P1中的等式约束(C3)，最大化最小归一化吞吐量y，形成P1的近似问题为

$\begin{align} & \text{P}2:\max y \\ & s.t.y\le \frac{{{L}_{j}}}{{{\eta }_{j}}},\forall j;\left( C2 \right) \\ \end{align}$

问题P2的拉格朗日函数为

$\begin{align} & J=y+\sum\limits_{j=1}^{M}{{{\lambda }_{j}}}\left[ \frac{1}{{{\eta }_{j}}}\sum\limits_{i=1}^{N}{\left( {{\beta }_{ij}}{{b}_{ij}}+{{c}_{ij}} \right)-y} \right]+ \\ & \sum\limits_{i=1}^{N}{{{\delta }_{i}}}\left( 1-\sum\limits_{i=1}^{N}{{{\beta }_{ij}}} \right)+\sum\limits_{i=1}^{N}{\sum\limits_{i=1}^{N}{{{\mu }_{ij}}{{\beta }_{ij}}}.} \\ \end{align}$

(7)

其中，λ_j≥0,δ_i≥0,μ_ij≥0为拉格朗日乘子．求其KKT条件如下：

$\partial J/\partial {{\beta }_{ij}}={{\lambda }_{j}}{{b}_{ij}}/{{\eta }_{j}}-{{\delta }_{i}}+{{\mu }_{ij}}=0,\forall i,j.$

(8)

${{\mu }_{ij}}{{\beta }_{ij}}=0,\forall i,j.$

(9)

根据式(8)、式(9)可得下述引理：
引理2.1 对于小站i和k存在最优偏置因子θ_ik，使得用户j在b_ij/b_kj>θ_ik时接入小站i，在b_ij/b_kj＜θ_ik时接入小站k．
引理2.1可通过文献^[12]中类似的方法证明，不再赘述．由引理2.1可知，用户j对小站i，k的选择依赖于用户j在小站i，k间基础吞吐量的比值b_ij/b_kj，b_ij/b_kj最小的用户有优先切换到小站k的权利．并且对于小站i，用户间吞吐量满足比例约束时其归一化吞吐量y_i可表示为

$\begin{align} & {{y}_{i}}=\left( {{\beta }_{i1}}{{b}_{i1}}+{{c}_{i1}} \right)/{{\eta }_{1}}=\cdots \\ & =\left( {{\beta }_{i{{A}_{i}}}}{{b}_{_{i\left| {{A}_{i}} \right|}}}+{{c}_{_{i\left| {{A}_{i}} \right|}}} \right)/{{\eta }_{\left| {{A}_{i}} \right|}} \\ & =\left( 1+{{\sum }_{j\in {{A}_{i}}}}{{c}_{ij}}/{{b}_{ij}} \right)/\left( {{\sum }_{j\in {{A}_{i}}}}{{\eta }_{j}}/{{b}_{ij}} \right). \\ \end{align}$

(10)

其中，A_i为接入小站i的用户集合．式(10)中最后一项根据∑_j∈Aiβ_ij=1得到．因此根据上述对P2最优解的分析，提出用户接入单个小站时的低复杂度归属算法如下
步骤1(用户预归属)：根据最大信干燥比原则预归属用户到相应小站；
步骤2(归属更新)：
1) 根据式(10)计算各小站归一化吞吐量y_i,?i；
2) 计算ψ_ik=y_i－y_k，令Ψ={ψ_ikψ_ik＜0,?i,k}；
3) 寻找归一化吞吐量差距最大的2个小站

$\left( i\prime ,k\prime \right)\leftarrow \arg {{\min }_{{{\psi }_{ik}}}}\in {}_{\Psi }{{\psi }_{ik}};$

4) 寻找接入小站i′的用户中具有最小基础吞吐量比值的用户：j′=arg min_j∈Ai′b_i′j/b_k′j；
5) 计算切换j′到小站k′后，小站i′,k′的归一化吞吐量y′_i,y′_k，如果y′_i＜y′_k则执行切换；否则，令Ψ=Ψ＼{ψ_i′k′}，返回3)；
6) 移除各小站中最近最不常使用的文件，更新各小站缓存；
7) 循环步骤2，直到Ψ=?．
上述算法表明当小站i′切换用户j′到小站k′后，小站k′的归一化吞吐量仍大于小站i′的归一化吞吐量时，才执行切换，因此可保证每次迭代最小归一化吞吐量单调不减，从而保证算法的收敛性．
3 仿真结果与分析仿真中设M=200个用户和N=[60,300]个小站均匀分布在500 m×500 m的小区内，路径损耗为L(d)=128.1+37.6 lgd，小站和用户间的信道服从独立同分布瑞利衰落．系统带宽为20 MHz，小站的传输功率为33 dBm，噪声功率为-114 dBm，小站回程链路容量B_i=[10,100] Mbps．仿真中采用Movielens数据集^[13]建模用户请求，设每个用户请求3 900部电影中的15部电影，各用户间吞吐量的比例约束为η₁∶η₂∶…∶n_M=1∶1∶…∶1．
为比较算法间性能差异，考虑下列对比算法．对比算法1为最大信干燥比算法^[7]，该算法归属用户到接收信干燥比最大的小站，且小站上无缓存．对比算法2在此基础上，考虑文件流行度服从Zipf分布，在小站上缓存文件库中最受欢迎文件．
图 2、图 3对比不同算法的缓存命中率．从图 2可以看出，随着缓存文件数的增多，所提算法和对比算法2的缓存命中率均增加，且相较对比算法2有明显增益，当缓存文件数大于等于100时，所提算法增益均在10%以上．在固定缓存文件数为100时，图 3显示随着用户数的增多，所提算法的增益愈发明显，这是因为随着用户历史行为信息的增多，能通过所提缓存决策算法挖掘的个性化信息也越多．
Fig. 2

	Download: JPG larger image
图 2 缓存文件数与命中率关系 Fig. 2 Number of cache files versus hit ratio

Fig. 3

	Download: JPG larger image
图 3 用户数与命中率关系 Fig. 3 Number of users versus hit ratio

图 4展示小站回程链路容量B_i=10 Mbps时，系统吞吐量和小站数的关系．可以看出，所提算法相较2种对比算法有明显的增益，尤其是在小站部署密度较大时，如小站数为220时，所提算法相较对比算法1、2的增益分别为19.1%和11.3%.这是因为所提算法一方面通过提升缓存命中率带来增益，另一方面在归属用户时使各小站间的负载尽可能均衡，减少了空闲小站数，进而带来了性能提升．
Fig. 4

	Download: JPG larger image
图 4 小站数目与系统吞吐量关系 Fig. 4 Number of small cells versus throughput

图 5给出小站数为200时，系统吞吐量与小站回程链路容量的关系图．随着回程链路容量的增加，其容量逐渐不再受限，因此3种算法的系统吞吐量先增加最终趋于稳定．所提算法相较对比算法仍有明显增益，这是因为缓存命中率的提高在回程链路容量较小时会带来较大增益，而在回程链路容量充足时，合理的用户归属会带来较大增益．
Fig. 5

	Download: JPG larger image
图 5 回程链路容量与系统吞吐量关系 Fig. 5 Backhaul bandwidth versus throughput

4 结束语本文提出一种密集小站下，基于协作滤波的缓存内容决策和用户归属算法．本文首先利用基于用户的Top N协作滤波推荐系统确定小站缓存内容，以提高缓存命中率．随后形成一个系统吞吐量最大化的用户归属问题．通过放松约束条件，得出用户对小站的选择与其在不同小站的基础吞吐量之比相关的结论，并提出一种低复杂度归属算法．通过对缓存内容更精准的决策和用户归属的优化，所提算法相较已有算法在缓存命中率和系统吞吐量上有明显增益，缓解了回程链路压力，提升了服务质量．
参考文献

[1]	ElSawy H, Dahrouj H, Al-Naffouri T Y, et al. Virtualized cognitive network architecture for 5G cellular networks[J].Communications Magazine, IEEE, 2015, 53(7):78–85.DOI:10.1109/MCOM.2015.7158269
[2]	Shanmugam K, Golrezaei N, Dimakis A G, et al. Femtocaching:wireless content delivery through distributed caching helpers[J].Information Theory, IEEE Transactions on, 2013, 59(12):8402–8413.DOI:10.1109/TIT.2013.2281606
[3]	Bi S, Zhang R, Ding Z, et al. Wireless communications in the era of big data[J].Communications Magazine, IEEE, 2015, 53(10):190–199.DOI:10.1109/MCOM.2015.7295483
[4]	Bastug E, Bennis M, Debbah M. Living on the edge:the role of proactive caching in 5g wireless networks[J].Communications Magazine, IEEE, 2014, 52(8):82–89.DOI:10.1109/MCOM.2014.6871674
[5]	Ahlehagh H, Dey S. Video-aware scheduling and caching in the radio access network[J].IEEE/ACM Transactions on Networking (TON), 2014, 22(5):1444–1462.DOI:10.1109/TNET.2013.2294111
[6]	Pantisano F, Bennis M, Saad W, et al. Cache-aware user association in backhaul-constrained small cell networks[C]//Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), 201412th International Symposium on. IEEE, 2014:37-42.
[7]	Zhou Z, Dong M, Ota K, et al. Energy-efficient context-aware matching for resource allocation in ultra-dense small cells[J].Access, IEEE, 2015, 3:1849–1860.DOI:10.1109/ACCESS.2015.2478863
[8]	Zink M, Suh K, Gu Y, et al. Characteristics of YouTube network traffic at a campus network:measurements, models, and implications[J].Computer Networks, 2009, 53(4):501–514.DOI:10.1016/j.comnet.2008.09.022
[9]	Pantisano F, Bennis M, Saad W, et al. Match to cache:Joint user association and backhaul allocation in cache-aware small cell networks[C]//Communications (ICC), 2015 IEEE International Conference on. IEEE, 2015:3082-3087.
[10]	Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems:a survey of the state-of-the-art and possible extensions[J].Knowledge and Data Engineering, IEEE Transactions on, 2005, 17(6):734–749.DOI:10.1109/TKDE.2005.99
[11]	Boyd S, Vandenberghe L. Convex optimization[M].Cambridge: Cambridge University Press, 2004.
[12]	Xue P, Gong P, Park J H, et al. Radio resource management with proportional rate constraint in the heterogeneous networks[J].Wireless Communications, IEEE Transactions on, 2012, 11(3):1066–1075.DOI:10.1109/TWC.2011.102611.110281
[13]	Miller B N, Albert I, Lam S K, et al. MovieLens unplugged:experiences with an occasionally connected recommender system[C]//Proceedings of the 8th international conference on Intelligent user interfaces. ACM, 2003:263-266.