多緩存容量場景下的D2D內容緩存布設優化方案

龍彥汕，吳 丹，蔡躍明，王 萌，郭繼斌

0 引言

終端直傳(Device-to-Device，D2D)通信由于允許鄰近的通信雙方可以不經過基站直接通信，成為緩解蜂窩回程壓力的關鍵技術之一［1］。更進一步地，借助于網絡中大量分散的用戶終端緩存資源，基于分布式緩存的D2D通信技術更利于減輕基站負載，確保用戶的服務體驗，使得內容分發具有高可擴展性和低成本優勢［2－3］。但是，由于用戶設備的緩存容量有限以及用戶對于不同內容的偏好不同，緩存什么內容、由哪個位置的用戶來緩存，即緩存布設方案，成為影響緩存效率的關鍵因素，也是想要獲取緩存增益必須解決的問題。近年來，考慮到移動用戶的移動性和空間隨機分布的特點，越來越多的研究者開始利用隨機幾何理論來建模動態的網絡拓撲結構以及在D2D緩存網絡中內容的可獲得性［4－9］。

文獻［4］假設緩存用戶和請求用戶服從相互獨立的齊次泊松點過程，將分布式緩存的布設優化問題建模為平均緩存命中率的最大化問題，提出了低復雜度的最優對偶搜索算法;文獻［5］在此基礎上進一步考慮內容傳輸過程中信道衰落的影響，對每個文件的覆蓋概率進行分析，在假設每個節點只能緩存一個文件的條件下，以網絡中文件總的覆蓋概率為目標函數進行緩存方案優化;文獻［6］利用隨機幾何理論得到D2D緩存網絡中緩存輔助的網絡吞吐量，并通過數值仿真獲得最優緩存概率;文獻［7－8］根據用戶對內容的不同偏好將網絡用戶分組并得到最大化網絡收益的緩存策略，但是兩者依然假設所有用戶緩存容量相同，而且后者只考慮一個文件的情況。在實際的蜂窩網絡中，移動用戶所攜設備的緩存容量大小是不同的，而每個終端緩存已使用情況的特殊性使得這一情況更加突出。上述文獻都假設所有緩存節點具有相同的緩存容量的情況，由此獲得的最優緩存布設方案并不能直接應用于緩存容量多樣的情況。此外，雖然文獻［9］在靜態網絡拓撲的假設下研究小蜂窩基站緩存容量不同以及文件大小不同的情況下最小化回程鏈路速率的編碼緩存方案，但該方案并不適用于D2D緩存網絡。如上文所述，在D2D緩存網絡中，用戶移動性導致的位置不確定性，使得網絡拓撲結構是動態變化的;加之用戶對不同內容的偏好程度不同以及具體請求內容的不確定性，使得在靜態拓撲結構下得到的最優緩存布設方案只適用于某一時刻的網絡需求。為了滿足時變的動態網絡需求，則需要頻繁地更新最優緩存策略，勢必帶來較高的復雜度并且較難實現［11］。因此，如何設計在動態網絡拓撲環境下的多用戶多緩存容量的內容緩存布設方案仍亟待研究。

因此，針對D2D緩存網絡中用戶緩存能力異質的特點，本文利用隨機幾何理論建模不同緩存容量大小的用戶位置分布，分析了多用戶多緩存容量情況下的緩存命中率。在此基礎上以最大化緩存命中率為目標設計了適用于任意多種緩存容量大小的緩存布設方案，提出了基于坐標梯度優化的聯合緩存布設(Joint Cache Placement，JCP)算法。仿真結果表明，與現有的幾種緩存布設方案相比，通過JCP得到的緩存布設方案可以獲得更高的緩存命中率。

1 系統模型

考慮如圖1所示的D2D緩存網絡，網絡中所有用戶的位置服從密度為λ的齊次泊松點過程(Homogeneous Poisson Point Process，HPPP)Φ［4］。在現實情況中，移動用戶手持終端的緩存容量大小不等，例如，常見的智能手機有32 GB、64 GB、128 GB等硬盤容量大小，常見的筆記本電腦有256 GB、512 GB、1 TB等硬盤容量大小。顯然，終端緩存容量大小與用戶位置之間相互獨立，并且持有不同緩存容量終端的用戶位置之間也相互獨立。因此，假設網絡中共有K種不同緩存容量的移動用戶終端，終端緩存容量為Mk的用戶個數占總用戶數的比例為0＜τk＜1。根據HPPP的稀釋定理，可知對于k∈{1，2，…，K}，緩存容量為Mk的用戶位置分布服從密度為λk=τkλ的齊次泊松點過程Φk，稱為第k類用戶。顯不同緩存容量的用戶位置之間相互獨立。考慮擁有N個文件的數據庫，假設所有文件具有歸一化大小，在內容請求方面，用戶總是對當下最流行的多媒體內容感興趣，即大部分的用戶頻繁地請求少部分的內容;而且一個內容越流行，被用戶請求的概率越大。文獻［10］研究了計算機網絡中網頁請求的分布情況，表明網頁請求的分布可以用Zipf分布來近似;更進一步，在文獻［11］中，作者通過對YouTube等視頻點播平臺上大量用戶的請求數據，分析了視頻文件的請求分布統計特性，結果表明，視頻文件的請求分布也可以由Zipf分布來近似。因此，假設每個用戶按照Zipf分布獨立地從N個文件中請求文件，則流行度排名第i的文件被請求的概率可以表示為:其中，ν為內容流行度參數，表征文件被請求的密集程度。ν越大，大部分用戶集中請求的流行文件數越少。顯然q1＞q2＞… ＞qN。與傳統的服務器-客戶模式不同，在D2D緩存網絡中，終端用戶既是緩存提供者又是文件請求者。因此，當請求用戶發起文件請求，有3種方式獲得所需文件:1)自卸載:當用戶已經緩存該文件，可以立即從本地緩存獲得該文件;2)D2D卸載:當本地未緩存所需文件時，由距離請求用戶R范圍內已緩存目標文件的緩存用戶通過D2D通信發送該文件;3)蜂窩卸載:當前兩者都無效時，該請求將轉由其服務基站通過回程鏈路從核心網絡獲取。由于本文是以最大化D2D緩存網絡的緩存命中率為目標來優化緩存布設方案，因此暫不考慮蜂窩卸載的情況。

圖1 多緩存容量下的D2D緩存網絡示意圖Fig．1 Schematic diagram of D2D caching network with heterogeneous cache capacities

由于用戶位置的隨機分布以及請求內容的不確定性，本文考慮基于概率的緩存布設方案［11］。假設第k類緩存用戶的緩存方案為 bk= ［ck1，ck2，…，ckN］，其中0≤cki≤1 表示緩存容量為Mk的用戶緩存文件Fi的概率。所有用戶的緩存方案表示為A［cki］K×N。根據HPPP的稀釋定理可知，緩存用戶Φk中緩存文件Fi的用戶服從密度為λki=λkcki的齊次泊松點過程Φki。此外，在半雙工模式下，用戶不能同時作為D2D通信的發送者和接收者，因此，假定某個時刻網絡中發起D2D請求的用戶比例為β∈［0，1］，余下的用戶成為潛在的D2D發送者。因此，Φki中潛在的D2D發送者服從密度為=(1－β)λ=(1－β)λc的齊次泊松點過程kikki

2 緩存命中率分析

緩存命中率定義為任意請求用戶可以在自己的緩存或者周邊R范圍內找到目標文件的概率，主要由自緩存命中率和D2D緩存命中率兩部分構成［6］:

2．1 自緩存命中率分析

當第k類用戶請求文件Fi時，如果該用戶已經緩存文件Fi，那么他可以立刻通過自卸載獲得該文件。這一事件發生的概率為。進而，考慮請求用戶緩存容量以及被請求文件的不同可能性，根據全概率公式可以得到自緩存命中率為:

2．2 D2D緩存命中率分析

當請求用戶沒有緩存自己需要的文件時，則向鄰近的緩存用戶發送請求。如果在請求用戶半徑為R的區域內存在緩存該文件的用戶，D2D緩存命中。當第k類的用戶向周邊用戶請求文件Fi時，D2D緩存命中的概率為:

其中，ak=πR2(1－β)λk表示請求用戶半徑R范圍內的第k類緩存用戶的平均個數。將式(5)代入式(4)中，并根據全概率公式，可得D2D緩存命中率為:

與只有一種緩存容量的情況［6］相比，多種緩存容量帶來的影響主要體現在:1)請求用戶的緩存容量是不相同的，從而導致其自卸載概率的不同，在式(7)中主要體現在對第j類請求用戶出現概率τj的全概率求和;2)請求用戶半徑R內緩存目標文件的緩存用戶的緩存容量大小不確定，在式(7)中主要體現在指數項中對K種情況的全概率求和。當K=1時，式(7)可以退化成與文獻［6］相吻合的結論，即:

當K=1并且不考慮自卸載情況時，式(7)進一步退化成文獻［4］的結論，即:

3 最優緩存布設方案

如上所述，本文的目標是在考慮多緩存容量的情況下獲得最大化緩存命中率phit的最優緩存布設方案A。

上述問題可以表示為:

其中，第一個約束表示每一類用戶緩存的平均文件個數不能超過其緩存容量大小。

網絡拓撲的隨機性以及用戶終端緩存能力互異的特點使得緩存命中率的求解需要對多個隨機變量進行全概率求和，而不同緩存容量用戶的緩存布設方案之間的耦合關系使得目標函數關于A是非凹的。因此，為了解決不同緩存容量用戶策略相互耦合的問題，本文將退而求其次，分析當給定其他類用戶策略時，針對某類用戶的緩存策略是否具有凹性。將除了第k類緩存用戶策略bk以外的其他類用戶的緩存分布策略{b1，…，bk－1，bk+1，…，bK} 表示為 A－k= ［cji］(K－1)×N。那么，對于任意k，當給定A－k時，phit的表達式可以重新表示為:

經過兩次求導計算，可得phit關于bk的二階偏導數為由此可知phit的海森矩陣是負定矩陣，這說明phit是關于第k類用戶緩存布設方案bk的嚴格凹函數。

根據這一特性，把原問題轉化為對每種緩存容量大小的用戶緩存策略的序列迭代求解。對于任意給定的緩存分布策略A－k，原問題轉化為對第k類用戶緩存策略優化的子問題，表示為:

其中，μk為保證緩存容量約束的拉格朗日乘子。根據phit的局部凹性可知，利用Karush-Kuhn-Tucker最優化條件可以得到子問題的最優解并經過整理后，可以得到:

從式(18)可以看出，不同緩存容量的緩存策略與對應的用戶密度有關，對于固定的某種緩存容量來說，不同文件的緩存概率與其流行度qi有關。由于Lambert-W函數在非負區間是關于變量的單調增函數，因此μk越小以及qi越大，則cki越大。為得到D2D網絡中所有緩存用戶緩存布設方案，提出基于坐標梯度的聯合緩存布設算法，具體步驟如下:

算法中，ξ1是外部循環用于判斷算法是否達到最大緩存命中率的誤差精度，ξ2是內部循環用于判斷緩存的內容總數是否達到緩存容量的誤差精度。一般情況下，誤差精度越小，對應的該循環收斂所需要的迭代次數越多，反之亦然。Tmax是為防止算法陷入無限循環而設置的迭代次數門限。由于原問題的可行集合為閉集并且目標函數有下界，可知通過該算法至少可以得到一個原問題的局部最優解。通過第5)步到第13)步的判斷，如果算法收斂，將立刻跳出外部循環。因此，算法外部循環的實際迭代次數主要通過第5)步到第13)步來決定。假設外部循環實際的最大迭代次數為T(T≤Tmax)，算法第5)步到第13)步通過二分法來尋找以及對應的最優緩存方案的最大迭代次數是I，那么上述算法的計算復雜度為O(KNIT)。

4 仿真結果及分析

本章主要通過數值仿真對所提JCP算法進行有效性驗證。

根據前文可知，JCP算法可以保證至少收斂到一個局部最優解，但是由于原問題的非凹性，不同初始值可能會導致JCP算法收斂到不同的局部最優解［8］。因此，為了評估初始值設置對算法收斂性的影響，圖2描繪了在不同文件數以及不同緩存容量的用戶占比等多種場景下，算法采用不同緩存布設初始值A0時的收斂曲線。以 K=2 為例，Zero Init．表示 A0=0K×N為零矩陣;Unif．Init．表示對于每個 k通過圖中多條曲線對比可知，即使采用不同的A0，JCP算法都可以用幾次迭代收斂到相同的局部最優解，這說明JCP算法對A0的不同取值并不敏感。

為了評估JCP算法的性能，將JCP與另外三種緩存布設方案進行對比并分析系統參數對算法有效性以及網絡緩存命中率的影響。三種對比算法分別為:1)針對不同的緩存容量用戶，各自獨立地計算最優緩存布設方案(Separate Cache Placement，SCP)［6］;2) 根據內容流行度進行緩存(Adaptive cache placement，ADA)［15］;3)根據緩存容量大小，等概率地緩存不同文件(Uniform cache placement，UNI)［16］。為了使仿真結果更具說服力，以下仿真均考慮K=2和K=3兩種情況。考慮到現實場景中用戶終端容量大小均以2的冪次方呈現，因此，當 K=2 時，M1=1，M2=2，τ1= τ2=0．5;當 K=3時，M1=1，M2=2，M3=4，τ1= τ2= τ3=1/3。此外，除非特殊說明，以下仿真參數設置不變:N=5，λ=0．01(users/m2)，ξ1=10－4，ξ2=10－4［16］，β =0．5，ν =0．8，Rd=10 m。

圖2 緩存布設方案初始值對算法收斂性的影響Fig．2 Effect of cache placement initialization on convergence

圖3描繪了不同內容流行度參數ν情況下，JCP與其他三種基準算法的緩存命中率曲線。由圖可知，均勻緩存方案由于不受請求概率影響，因此其對應的緩存命中率不隨ν變化，而其他方案的緩存命中率均隨ν的增加而提高。縱向對比四種緩存方案，不難發現，JCP始終要優于其他三種方案。值得一提的是，根據理論分析可知，JCP的優越性主要來源于多種緩存容量共存的網絡中，不同緩存策略的耦合關系對D2D卸載方式產生影響。通過圖3中JCP與SCP的對比可見:當ν=0時，用戶對所有文件的興趣相同，因此在每種緩存容量的用戶緩存內肯定都會均勻緩存各個文件，此時JCP與SCP效果相同;隨著ν的增大，JCP優越性先變大再縮小，在ν=1．8時，只有少量的優勢，這是因為此時用戶集中請求的文件很少，這種情況下每個請求用戶都主要以自卸載方式來滿足文件需求。

圖4描繪了不同請求用戶比例β情況下，JCP算法與其他三種算法的緩存命中率曲線。由圖可知，請求用戶比例越大，系統緩存命中率越小，這是因為β越大，潛在的D2D發送者越少，緩存用戶之間無法充分利用鄰近用戶的緩存資源。當β=1時，所有的用戶都發送文件請求，此時他們只能采用自卸載模式，而無法參與D2D內容分發，此時，緩存命中率等于自卸載概率。由于文件的自給自足使得此時所有用戶的緩存和請求之間都是相互獨立的，因此JCP算法與SCP算法性能相同。除此以外，在整個β的區間，JCP算法都可以獲得相比其他三種算法更高的緩存命中率。

圖3 緩存命中率隨內容流行度參數ν的變化曲線Fig．3 Cache hit ratio versus content popularity factor ν

圖4 緩存命中率隨請求用戶比例β的變化曲線Fig．4 Cache hit ratio versus requesters’proportion β

圖5進一步分析了不同的D2D通信距離約束R情況下，四種算法的性能比較。由圖可知，隨著R變大，每個請求用戶周圍能夠為其提供D2D服務的緩存用戶數據增多，緩存命中率也隨之增大。通過不同算法的對比可知，不同R條件下，JCP仍然始終保持優于其他三種方案。

圖5 緩存命中率隨D2D通信距離約束R的變化曲線Fig．5 Cache hit ratio versus D2D communication distance constraint R

綜上所述，圖2從側面說明算法的低復雜度，圖3到圖5則從不同的角度揭示了JCP算法相比已有方案的優勢，即在多用戶多緩存容量場景下，本文所提JCP算法可以獲得更高的緩存命中率。

5 結語

本文針對D2D緩存網絡中用戶存在多種不同緩存容量的實際情況，以最大化網絡緩存命中率為目標，優化不同緩存容量用戶的緩存布設方案。為了達到這一目的，提出了基于坐標梯度的聯合緩存布設算法并通過仿真證明了該算法的優越性以及對現實緩存網絡中緩存布設的指導意義。但是本文假設D2D通信在一定距離范圍內可以無差錯傳輸，但在實際傳輸過程中，信號無疑會受到信道衰落和干擾的影響，因此在考慮信道條件的情況下優化多緩存容量情況的緩存布設方案是下一步要解決的問題。