基于輔助設備的D2D集群的文件塊緩存策略研究

周 仙， 宋 暉， 潘達儒, 黃 旭

(華南師范大學物理與電信工程學院， 廣州 510006)

近年來互聯(lián)網(wǎng)用戶和移動設備不斷增長，思科視覺網(wǎng)絡索引報告[1]指出：到2023年，全球互聯(lián)網(wǎng)用戶總數(shù)將從2018年的39億增至53億，全球移動設備將從2018年的88億部增至131億部[1]. 這對于傳統(tǒng)的蜂窩網(wǎng)絡將是巨大的流量負擔，可能導致用戶體驗(QoS)下降[2]. 為提高用戶體驗，3GPP提出了D2D(Device-to-Device)通信，使用戶數(shù)據(jù)不經(jīng)過基站而在終端之間進行直接通信，從而降低了基站的負載，提供了比基站轉發(fā)更高速率、更低功耗的短距離傳輸服務[3]. 研究[4-7]表明: 集群是提高緩存輔助D2D網(wǎng)絡性能的有效方法，使用集群可以保證用戶的QoS、傳輸?shù)牡脱舆t以及系統(tǒng)的高頻譜、高能效、高緩存命中概率. 此外，AMER等[8]研究了一種集群協(xié)作策略，該策略將用戶設備劃分為集群并在集群內(nèi)通過D2D通信或傳統(tǒng)的蜂窩傳輸實現(xiàn)集群間數(shù)據(jù)交換，實現(xiàn)最小時延；為了增加系統(tǒng)的總數(shù)據(jù)速率，ZHENG等[9]提出了一個面向集群的D2D通信方案，該方案考慮了功率、帶寬和鏈路分配的優(yōu)化.

雖然D2D設備可以大大緩解基站壓力，但由于D2D設備的容量有限，無法滿足用戶對無線網(wǎng)絡的需求. 因此，衍生了類似機器人、公交車和汽車等緩存容量更大的移動式緩存設備，并通過D2D通信與其他設備共享內(nèi)容[10]. 移動式緩存設備的加入可以幫助用戶出行交流，分享共同的興趣[11-12]. CHEN等[13]開發(fā)了一個新的網(wǎng)絡框架，即使用具有緩存啟動和自維持的移動設備來分析D2D網(wǎng)絡的成功內(nèi)容交付性能. 此外，VO等[14]提出了一種社交感知的頻譜共享與緩存輔助設備選擇(SSC)策略,該策略在5G網(wǎng)絡中卸載視頻. 但是，文獻[11-14]沒有考慮用戶的相似性，這使得文件在通信過程中被相似用戶反復使用，從而產(chǎn)生文件冗余問題，造成資源浪費. 因此，本文提出了基于輔助設備的D2D集群的流性文件塊分批緩存策略(FCPhit)：首先，根據(jù)請求文件的相似性將用戶分為幾個集群；然后，將用戶分批并將流行文件分為若干塊，用戶設備緩存文件的第1塊，移動輔助設備緩存其他文件塊.

1 系統(tǒng)模型

設Pj為用戶請求排序為第j流行文件的概率，用zipf分布[6]表示：

(1)

其中，γ是zipf指數(shù)，γ值越高表示文件流行度越高，被訪問次數(shù)越多.

當用戶請求文件j時，可能發(fā)生以下緩存命中情形：

(1)自緩存：當請求用戶在自己的緩存空間里擁有所請求的文件時，自請求的緩存命中概率為：

(2)

其中，M為文件庫中文件的總數(shù)量.

(2)D2D緩存：當請求用戶無法通過自請求獲得文件時，通過D2D通信向通信范圍內(nèi)的用戶請求此文件. D2D通信半徑為RD2D，在泊松點過程(PPP)中，用戶密度為λ，所以，在用戶的D2D通信覆蓋范圍內(nèi)存在t個緩存了文件j的用戶的概率[6]為：

(3)

則在周圍用戶中能找到文件f的概率為：

(4)

因此，D2D緩存命中概率為：

(5)

(3)輔助設備緩存：當用戶無法從周圍用戶通過D2D通信獲得文件時，從附近的移動輔助設備中獲得文件. 輔助設備能夠在它們的本地緩存內(nèi)保存文件并應對普通用戶的請求. 假設文件被緩存在移動速度為VHE的輔助設備中，在T秒內(nèi)，用戶在輔助設備的D2D覆蓋范圍μ為[15]：

(6)

用戶在輔助設備的D2D覆蓋范圍內(nèi)至少被命中一次的概率為:

(7)

則輔助設備的緩存命中概率為：

(8)

所以，系統(tǒng)的緩存命中概率為：

(9)

2 問題制定

最優(yōu)的緩存策略是為了得到最優(yōu)的Pcj(j=1,2,…,M)的值，從而得到系統(tǒng)的緩存命中概率的最優(yōu)解. 由于用戶設備的緩存容量有限，Pcj(j=1,2,…,M)的總和不應該超過用戶緩存容量. 因此，優(yōu)化問題可以表示為：

(10)

其中，Pc={Pc1,Pc2,…,PcM}，j[1,M]. 為了解決問題(10)，本文提出了基于輔助設備的D2D集群的流行文件塊分批緩存策略(FCPhit)：先將具有相似文件請求的用戶置于一個集群中；然后將用戶分批，并同時考慮文件流行度和文件分塊，舍棄請求次數(shù)排序靠后的文件，在用戶設備緩存受歡迎的文件的第1塊，輔助設備緩存其他文件塊.

2.1 集群方法

(11)

ksim(ut,ur)越大，代表2個類越相似. 最后，根據(jù)用戶間的相似性將其組成一個集群.

圖1 用戶集群圖

2.2 流行文件塊分批緩存策略

在日常生活，很多用戶在瀏覽文件時，往往只關心文件的開頭. 如果在用戶請求文件時每次均傳輸整個文件，沒有被瀏覽的部分會占用過多的內(nèi)存，從而造成D2D資源的浪費. 針對這種狀況，本文提出了一種基于輔助設備的D2D集群的流行文件塊分批緩存策略(FCPhit). 由zipf分布可知：集群內(nèi)的用戶雖然有較相同的興趣愛好，但其緩存空間內(nèi)依然存在部分不受歡迎的文件. 基于此，本策略舍棄不受歡迎的文件，選取流行的文件組成文件庫φ，并將這些流行文件分為m塊，用戶在瀏覽完文件的第一塊后可選擇繼續(xù)瀏覽剩余的文件塊或者放棄瀏覽. 用戶設備緩存這些文件的第1塊，移動輔助設備緩存除了第1塊的其他文件塊. 為了減少數(shù)據(jù)量，本文采用分批緩存的方式.

如圖2所示，假設給定用戶設備的最大緩存容量為5 bit，文件庫φ中的文件數(shù)Q=10，φ中的文件分為2批被用戶設備緩存. 將集群用戶隨機進行標記，分別編號1、2、3、…，將φ中的文件依次緩存在用戶設備的緩存空間內(nèi)，即：第1個用戶設備(U1)的緩存空間緩存文件j(j=1,2,3,4,5)的第1塊fj1，移動輔助設備緩存這些文件的其他塊；第2個用戶設備(U2)的緩存空間緩存文件j(j=6,7,8,9,10)的第1塊fj1，移動輔助設備緩存這些文件的其他塊，此時φ中的文件都已經(jīng)被緩存；接下來，第3個用戶設備(U3)的緩存空間的使用情況與U1相同，第4個用戶設備(U4) 緩存空間的使用情況與U2相同，以此類推，直到所有用戶設備的緩存空間均緩存了文件.

圖2 示例分批緩存

(12)

其中

當用戶y請求文件的fj1不在自己的設備的緩存空間中時，假設集群中共有wj名用戶緩存了該文件，由于用戶位置不固定，wj名用戶中任一用戶處于用戶y的D2D通信半徑范圍內(nèi)的概率為：

(13)

則在周圍用戶中能找到文件fj1的概率為：

(14)

那么D2D緩存命中概率為：

(15)

當文件分成m塊時，用戶設備在自己的緩存空間里緩存文件的第1塊，如圖 3所示，假設此后每塊文件被選擇的情況服從概率P=1/2的0-1分布，在用戶已經(jīng)得到第1塊文件后，有1/2的概率得到第2塊，有1/4的概率得到第3塊，以此類推，用戶得到第m塊的概率為1/2m-1. 第m塊在實際使用之前有一段時間間隔，在(m-1)T秒后才會被得到.

圖3 文件分塊示意圖

在(m-1)T秒期間，用戶在輔助設備的D2D覆蓋范圍內(nèi)至少命中一次的概率可以寫為[16]：

(16)

如果2RD2D+VHE(m-1)T>2RBS，則有效的D2D覆蓋范圍不能包含在蜂窩網(wǎng)絡中，此時對于第m塊文件塊來說，與有效的D2D覆蓋范圍重疊的最小單元數(shù)可表示為：

(17)

假設D2D有效的覆蓋范圍被分成Kcell個大小相同的區(qū)域，則式(16)可寫為：

(18)

則輔助設備緩存的緩存命中概率為：

(19)

那么流行文件塊分批緩存策略緩存文件集bi的緩存命中概率為：

(20)

則該策略下系統(tǒng)的平均緩存命中概率為：

(21)

當用戶分批緩存文件時，總體來說流行文件的每個文件被緩存的次數(shù)是相同的. 由式(14)、(20)、(21)可知：若要使系統(tǒng)的緩存命中概率最大，就要確保wj盡量大，而文件數(shù)Q的數(shù)目會直接影響到wj的大小. 當集群內(nèi)的用戶數(shù)一定時，若選取緩存的文件數(shù)Q過大，則用戶過于分散，當文件流行度高時，找到受歡迎的請求文件的概率會很低，系統(tǒng)的緩存命中概率下降；若選取緩存的文件數(shù)Q太小，當文件流行度低時，文件被請求的概率基本相當，排序靠后的文件被請求的概率會變低，系統(tǒng)的緩存命中概率也會下降. 所以，可以通過調(diào)節(jié)參數(shù)來調(diào)整Q，從而找到使系統(tǒng)的緩存命中概率最大的最佳文件數(shù). 由圖4可知：當文件數(shù)為140時，系統(tǒng)的緩存命中概率最大；隨著Q的增加，系統(tǒng)的緩存命中概率出現(xiàn)了震蕩現(xiàn)象，這是因為文件的請求概率遵循zipf分布，雖然整體的趨勢是下降的，但是在文件流行度分布的峰值依然會出現(xiàn)命中概率上升的現(xiàn)象. 文件越多，文件本身分布的影響就會更明顯.

圖4 文件數(shù)的選取

3 仿真結果與討論

本節(jié)討論了不同狀態(tài)下的集群間系統(tǒng)性能以及集群內(nèi)系統(tǒng)性能. 通過仿真實驗，對本文提出的FCPhit策略與最流行緩存策略(MPhit)[17]、最優(yōu)緩存策略(OCPhit)[6]、等概率緩存策略(EPRC)[18]進行對比，研究了系統(tǒng)的緩存命中概率(Phit)與zipf指數(shù)(γ)、緩存容量、用戶數(shù)、文件數(shù)、集群個數(shù)、輔助設備的移動速度及其數(shù)量的關系，以驗證FCPhit策略的有效性.

3.1 zipf指數(shù)與系統(tǒng)的緩存命中概率

由4種策略下系統(tǒng)的緩存命中概率與zipf指數(shù)的關系(圖5)可知：OCPhit策略下系統(tǒng)的緩存命中概率在zipf指數(shù)的低值部分(0.2～0.7)會高于MPhit策略下系統(tǒng)的緩存命中概率，這是因為zipf指數(shù)越低，用戶請求文件的傾向越不明顯，此時MPhit策略喪失了其優(yōu)勢性；隨著zipf指數(shù)的增長，OCPhit、MPhit、FCPhit策略下系統(tǒng)的緩存命中概率隨之上升；EPRC策略下系統(tǒng)的緩存命中概率沒有變化是因為該策略下用戶請求文件時是等概率請求的，與zipf指數(shù)無關.

圖5 4種策略下zipf指數(shù)對系統(tǒng)的緩存命中概率的影響

3.2 用戶緩存容量與系統(tǒng)的緩存命中概率

由4種策略下系統(tǒng)的緩存命中概率與緩存容量的關系(圖6)可知：(1)隨著用戶緩存容量的增加，系統(tǒng)的緩存命中概率增加，這是因為緩存容量的增大意味著用戶可以用于緩存的空間越多，即用戶可以在其緩存空間內(nèi)緩存更多的文件，那么用戶能獲取請求文件的概率就更大. (2)FCPhit策略下系統(tǒng)的緩存命中率比其他策略下系統(tǒng)的緩存命中率更高.

圖6 4種策略下用戶緩存容量對系統(tǒng)的緩存命中概率的影響

3.3 用戶數(shù)與系統(tǒng)的緩存命中概率

由4種策略下系統(tǒng)的緩存命中概率與用戶數(shù)的關系(圖7)可知：(1)OCPhit、FCPhit、EPRC策略下系統(tǒng)的緩存命中概率均隨著用戶數(shù)的增加而不斷提高，這是因為用戶數(shù)的增加意味著在一定的區(qū)域內(nèi)周圍用戶更加密集、用戶提供的總體緩存空間更大，緩存的文件更多，所以用戶能夠輕易地從周圍用戶的緩存空間里獲取相應的請求文件，直接提高了用戶從周圍用戶的緩存空間中找到請求文件的概率. (2)MPhit策略下系統(tǒng)的緩存命中概率不會受用戶數(shù)量的影響，這是由于每個用戶都緩存了相同的最受歡迎的部分文件.

圖7 4種策略下用戶數(shù)對系統(tǒng)的緩存命中概率的影響

3.4 文件數(shù)與系統(tǒng)的緩存命中概率

由4種策略下系統(tǒng)的緩存命中概率與文件數(shù)的關系(圖8)可知：(1)4種策略下系統(tǒng)的緩存命中概率均隨著文件總數(shù)的增加而呈下降趨勢. 這種現(xiàn)象的出現(xiàn)是因為文件總數(shù)的上升使得流行趨勢不明顯，用戶沒有顯示出對哪些文件有一定的偏好. (2)FCPhit策略下系統(tǒng)的緩存命中概率始終高于其他3種策略，這是因為文件數(shù)的增加使得決定分批緩存的文件庫增多，用戶在周圍用戶獲取請求文件的可能性更大.

圖8 4種策略下文件數(shù)對系統(tǒng)的緩存命中概率的影響

3.5 集群數(shù)量與系統(tǒng)的緩存命中概率

由系統(tǒng)的緩存命中概率與集群數(shù)量的關系(圖9)可知：隨著集群數(shù)量的增多，F(xiàn)CPhit策略下系統(tǒng)的緩存命中概率隨之提升. 出現(xiàn)這種現(xiàn)象的原因是：在單個基站覆蓋范圍內(nèi)且系統(tǒng)的用戶設備數(shù)量不變的前提下，隨著集群數(shù)量的增加，每個集群的用戶設備數(shù)量將會減少，集群內(nèi)的文件庫總量也會對應減少，但在同一集群里的用戶請求仍然有高度相似性. 所以，即使文件庫的流行度低，系統(tǒng)的緩存命中概率依然上升.

圖9 3種zipf指數(shù)下集群數(shù)量對系統(tǒng)的緩存命中概率的影響

3.6 輔助設備個數(shù)與系統(tǒng)的緩存命中概率

由3種移動速度下系統(tǒng)的緩存命中概率與輔助設備的關系(圖 10)可知：隨著輔助設備數(shù)量的增加，用戶的系統(tǒng)緩存命中概率增加. 出現(xiàn)這種情況的原因為：(1)當輔助設備數(shù)量增加時，有更多的機會與用戶設備進行通信；(2)隨著輔助設備的移動速度的增加，輔助設備的傳輸范圍隨之增加，用戶設備和輔助設備可以相互命中的概率增加，從而系統(tǒng)的緩存命中概率增加.

圖10 3種移動速度下輔助設備個數(shù)對系統(tǒng)的緩存命中概率的影響

4 結語

本文分析了將相似用戶進行集群的必要性和有效性，同時，為了避免D2D資源的浪費，以最大化D2D網(wǎng)絡的系統(tǒng)緩存命中概率為目標，提出了一種基于輔助設備的D2D集群的流行文件塊分批緩存策略(FCPhit). 由仿真結果可知FCPhit策略能夠有效提高網(wǎng)絡的系統(tǒng)性能：對比最流行緩存策略(MPhit)、最優(yōu)緩存策略(OCPhit)、等概率緩存策略(EPRC)，在相同的zipf指數(shù)、緩存容量、用戶數(shù)、文件數(shù)的條件下，F(xiàn)CPhit策略下系統(tǒng)的緩存命中概率均有很大提升；同時，隨著集群數(shù)量和系統(tǒng)中移動輔助設備數(shù)量的增加，系統(tǒng)的緩存命中概率也相應增大. 然而，本文的模型是理想化的，例如，用戶請求文件時只遵循簡單的zipf分布、用戶集群的理想化. 此外，移動輔助設備的加入會相應增加系統(tǒng)的能耗和成本，如何在保證緩存命中概率的同時降低能耗和成本也將是未來研究的方向. 同時，在未來的研究中，應使用更多偏向現(xiàn)實化的模型，并在系統(tǒng)模型中考慮傳輸中斷、傳輸延遲和用戶的差異性等現(xiàn)實性情況.