超密集網(wǎng)絡(luò)下基于用戶聚類的緩存策略研究

王鶴云 陳雯

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

關(guān)鍵詞：超密集網(wǎng)絡(luò);緩存策略;命中率;時(shí)延

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

1 相關(guān)工作

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

目前在超密集網(wǎng)絡(luò)下基于內(nèi)容的流行度緩存，有著諸多不足，比如缺少用戶與基站相似度的匹配，忽視了不同用戶的需求?；诖吮疚奶岢鲆环N基于聚類算法的緩存流行度預(yù)測策略。該方法結(jié)合K-中心點(diǎn)算法，依據(jù)不同的用戶的偏好相似度，劃分出不同的用戶集群，再將它與基站的相似度進(jìn)行分析，使得用戶與基站相匹配。根據(jù)偏好因素、熱度因素和時(shí)間間隔因素這三方面進(jìn)行基站存儲文件緩存策略的調(diào)整，最終使得時(shí)延降低，提高緩存命中率，達(dá)到提高整體系統(tǒng)性能的目的。

2 建模分析

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

首先可以定義小型基站W(wǎng)=S1，S2，...Sn用戶U=U1，U2...Un。存儲文件內(nèi)容文件F=e1，e2...en。每個SBS存儲的文件個數(shù)為L。因?yàn)椴煌瑓^(qū)域覆蓋的用戶不同，所以MBS與SBS中的內(nèi)容存儲以及受到用戶關(guān)注程度也會有不同，所以會從多個方面考慮來進(jìn)行文件的緩存與替換。

2.1 基于K-中心點(diǎn)算法的用戶聚類劃分建模

K-中心點(diǎn)算法是一種在數(shù)據(jù)處理中常用的聚類算法，它是一種基于劃分的聚類算法。K-中心點(diǎn)算法的核心思想就是通過連續(xù)的迭代計(jì)算，選取出簇中處于最中心位置的對象，在迭代的過程中，將N個對象給出不同的K個劃分。在這里，中心點(diǎn)的定義是，該點(diǎn)的平均差異性是在這簇中所有被列選出的點(diǎn)中最小的。在本文場景下，該算法可以對不同興趣相似度的用戶進(jìn)行聚類區(qū)分，有效提高緩存命中率。在超密集網(wǎng)絡(luò)的場景下，想要取得良好的對用戶的劃分效果，重要的就是對不同興趣的用戶進(jìn)行分類劃分。因?yàn)樗梢苑从秤脩魧Σ煌膬?nèi)容繼續(xù)請求的可能性，這與內(nèi)容密切相關(guān)。

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