超密集網絡下基于用戶聚類的緩存策略研究

王鶴云 陳雯

摘 要：目前隨著5G網絡的迅猛發展，超密集網絡下的緩存策略研究價值也越來越大。目前業界常用的是Least Recently Used（最近最少使用），Least Frequently Used（最近最不常用）算法。然而，隨著數據量與數據內容多樣性的迅猛增長，有效而安全地向最終用戶提供高質量服務變得越來越具有挑戰性。常規的應用方法是被動性策略，但無法像主動性策略一樣應對復雜的數據沖擊。不同的用戶對不同的內容有著不同的需求。基于此，本文提出了一種基于用戶聚類的緩存預測算法。首先對用戶的相似度進行分組聚類，這樣可以更好地對相似偏好的用戶進行區分。再通過基站與用戶的相似度進行匹配，這樣使得基站與用戶的匹配度更高，提高命中率。本文還基于喜好因素，熱度因素和時間間隔因素三個不同方面對基站的緩存文件進行更新管理。實驗結果表明，該策略可以有效提高緩存命中率并降低用戶響應時延。

關鍵詞：超密集網絡;緩存策略;命中率;時延

近年來，5G通信技術不僅僅依靠擴展的帶寬來支持日新月異的內容數據沖擊，而且還采用超密集網絡為內容數據的爆炸性增長提供足夠的質量保證。一些研究人員發現，越來越多的數據以及網絡流量被用戶重復下載，而由于回程鏈路阻塞，內容分發可能給用戶帶來長時延并降低服務可靠性，為了更好地提高緩存命中率，可以直接將這些內容儲存到本地基站或宏基站中。基站中每個數據對象最終都將發送給感興趣的用戶。當用戶靠近數據對象的存儲位置時，他們將消耗較少的網絡流量來訪問數據對象[1]。在選擇內容的緩存位置時，用戶的興趣偏好具有一定的指導，并且內容應存儲在距離感興趣的用戶更近的位置。因此，可以基于用戶的偏好相似度來設計緩存部署策略。在不同的時間段，不同內容的熱度下，用戶對基站的需求匹配度是不同的，需要做到更新匹配。因此本文提出了一種基于聚類算法的緩存流行度預測策略來解決這些問題。

1 相關工作

針對目前的現狀，業界常用的緩存策略是LRU，也就是最近最少使用策略。但是隨著時代的發展，內容的本地緩存越來越需要對用戶進行精準對接，提供個性化服務。雖然被動性策略可以在一定程度滿足命中率的要求，但是需要進一步升級為更加優異的主動性緩存策略。L.Fan等人明顯地指出了超密集網絡中主動緩存對提高緩存命中率的重要意義[2]。主動緩存也就是指在用戶操作后臺時，由系統去刪除原有緩存進行更新的緩存模式。Mohamad Salhani提出了一種解決超密集網絡中致密化的緩存方案，提出了一種基于基站集群的緩存算法[3]。Xiaodong Zhu提出了一種清除無效信息，使得核心需求內容聚集在用戶的緩存方法，這顯著提高了系統性能[4]。ChengJia提出了一種基于基站的聚類算法，通過對不同的SBS進行片段分割，對文件的緩存與否進行判斷處理[5]。M.Song等人基于不同時段的神經網絡模型進行內容流行度的預測，通過對數據的分析進行合理的判斷[6]。Dewang Ren等人通過對內容流行度進行分層，將不同的內容對應不同的緩存級別，實現了多內容的對應預測，提高的緩存性能[7]。D.Liu等人通過對于不同的用戶相似度進行劃分，使得內容的命中率進一步提高[8]。M.Liu等人提出了一些關于超密集網絡內關于資源調配，緩存管理的前瞻性調研[9]。綜合以上文章，可以發現，目前雖然考慮到了對于用戶相似度的劃分，但是沒有考慮到用戶與不同基站的對應差異，例如在不同時間段，不同內容的熱度下，用戶對基站的需求匹配度是不同的，要進行恰當的相似度匹配。同時沒有結合多角度對用戶與內容本身的分析，策略過于單一。本文考慮從偏好因素、熱度因素和時間間隔因素來分析緩存文件，使基站內文件內容的存儲與刪除更加合理，在有限利用其內部空間的同時提高效率，降低時延。

目前在超密集網絡下基于內容的流行度緩存，有著諸多不足，比如缺少用戶與基站相似度的匹配，忽視了不同用戶的需求。基于此本文提出一種基于聚類算法的緩存流行度預測策略。該方法結合K-中心點算法，依據不同的用戶的偏好相似度，劃分出不同的用戶集群，再將它與基站的相似度進行分析，使得用戶與基站相匹配。根據偏好因素、熱度因素和時間間隔因素這三方面進行基站存儲文件緩存策略的調整，最終使得時延降低，提高緩存命中率，達到提高整體系統性能的目的。

2 建模分析

一個典型的網絡場景如圖1所示，在宏基站下有著多個小型基站與不同的用戶。小型基站與宏基站之間是無線連接的。本次研究主要是考慮一段時間內的內容緩存情況，假設大部分用戶會固定在一個地方一段時間，故而少部分用戶的移動不會對這次研究造成影響。

首先可以定義小型基站W=S1，S2，...Sn用戶U=U1，U2...Un。存儲文件內容文件F=e1，e2...en。每個SBS存儲的文件個數為L。因為不同區域覆蓋的用戶不同，所以MBS與SBS中的內容存儲以及受到用戶關注程度也會有不同，所以會從多個方面考慮來進行文件的緩存與替換。

2.1 基于K-中心點算法的用戶聚類劃分建模

K-中心點算法是一種在數據處理中常用的聚類算法，它是一種基于劃分的聚類算法。K-中心點算法的核心思想就是通過連續的迭代計算，選取出簇中處于最中心位置的對象，在迭代的過程中，將N個對象給出不同的K個劃分。在這里，中心點的定義是，該點的平均差異性是在這簇中所有被列選出的點中最小的。在本文場景下，該算法可以對不同興趣相似度的用戶進行聚類區分，有效提高緩存命中率。在超密集網絡的場景下，想要取得良好的對用戶的劃分效果，重要的就是對不同興趣的用戶進行分類劃分。因為它可以反映用戶對不同的內容繼續請求的可能性，這與內容密切相關。

首先需要確定用戶間的興趣余弦相似度，通過它來對用戶進行度量。用來表示不同用戶的興趣偏好性。具體來說，用戶ua和ub的余弦相似度θa，b如下所示：其中F（a）與F（b）分分別表示用戶ua和ub對不同內容的訪問集合。