于千喻，楊 濤,2，馮 輝,2，胡 波,2,3

(1.復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院 電子工程系，上海 200433; 2.復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院 智慧網(wǎng)絡(luò)與系統(tǒng) 研究中心，上海 200433; 3. 復(fù)旦大學(xué) 電磁波信息科學(xué)教育部重點實驗室，上海 200433)

隨著無線通信技術(shù)的迅猛發(fā)展，移動設(shè)備的大量使用以及多媒體服務(wù)的不斷涌現(xiàn)，移動數(shù)據(jù)流量呈指數(shù)級增長.思科的預(yù)測報告[1]表明，2021年全球全年移動數(shù)據(jù)流量將達到587EB.由于現(xiàn)有網(wǎng)絡(luò)帶寬的限制，以及無線接入網(wǎng)和核心網(wǎng)之間的回程傳輸瓶頸，故日益增長的數(shù)據(jù)流量需求無法得到滿足.基于此，邊緣緩存[2]已成為學(xué)術(shù)界和產(chǎn)業(yè)界關(guān)注的熱點，即由基站或移動終端等處配置緩存設(shè)備以存儲部分流行度高的文件，從而減少回程鏈路之間文件的重復(fù)傳遞數(shù)，以減輕核心網(wǎng)絡(luò)的流量壓力.

圍繞網(wǎng)絡(luò)緩存技術(shù)學(xué)術(shù)界開展了廣泛的研究.文獻[3]中作者提出了一種博弈論方法，使得微基站做決策時能夠最大化利用緩存服務(wù)的用戶數(shù)；文獻[4]考慮用戶的移動性，提出使緩存命中率最大化的動態(tài)緩存方案；文獻[5]針對組播傳輸?shù)臒o線網(wǎng)絡(luò)，提出使得系統(tǒng)耗能最小的緩存方案.以上研究雖能達到較好的緩存效果，但均未考慮基站之間的合作，鑒于基站之間通常通過高速光纖連接，故也給緩存策略提升效率帶來了可優(yōu)化的空間.即用戶請求文件時，如果本地基站未緩存該文件，可首先選擇邊緣網(wǎng)絡(luò)及網(wǎng)絡(luò)中其他緩存有該文件的基站進行傳輸，否則再通過回程鏈路從遠端文件服務(wù)器獲取文件.本文考慮基站之間的合作，從網(wǎng)絡(luò)服務(wù)角度講，可充分利用基站空余的緩存空間，降低傳輸成本；從用戶角度而言，可以減少傳輸時延，改善用戶體驗.

針對基站緩存問題，現(xiàn)有文獻從不同角度進行了優(yōu)化建模研究，如用戶移動性[4]、能量效率[5]、物理信道狀況[6]以及傳輸時延[7]等.其中，從提升用戶體驗的角度講很重要的一個因素是降低獲取文件的傳輸時延.文獻[7]假設(shè)微基站之間可以合作緩存，作者提出了一種基于分布式最小傳輸時延模型，但假設(shè)相同鏈路的傳輸時延相同，即未考慮文件大小對于傳輸時延的影響；文獻[8]提出了一種離線緩存方案，使得所有用戶獲取文件的時延最小，但假設(shè)對不同基站所有文件的流行度(文件被請求次數(shù)的期望)均已知并相同；文獻[9]中，作者提出了一種貪婪算法，從用戶的角度建模，將最小化時延傳輸問題轉(zhuǎn)化為滿足請求最大命中率問題，但是未考慮基站之間的合作.

上述研究文獻都假設(shè)文件流行度固定且在整個網(wǎng)絡(luò)中已知，而現(xiàn)實中文件流行度分布并不能事先得到，此時需要對文件的流行度進行動態(tài)估計，進而設(shè)計更有效的緩存方案.文獻[10]用多臂賭博機(Multi-Armed Bandit, MAB)方法，結(jié)合更換文件帶來的代價，在單個蜂窩網(wǎng)絡(luò)中，通過更新緩存內(nèi)容和觀察即時請求完成了對文件流行度的估計.文獻[11]考慮多個蜂窩網(wǎng)絡(luò)場景，對傳統(tǒng)MAB方法進行改進，進而對文件流行度進行估計，但是并未考慮基站之間的協(xié)作緩存.文獻[12]針對社交網(wǎng)絡(luò)利用奇異值分解和協(xié)同濾波的方法，結(jié)合連接信息完成文件請求概率的估計，文獻[13]利用遷移學(xué)習(xí)對流行度矩陣進行估計.以上文獻算法均只使用某段時間窗口內(nèi)的信息，未利用長時間的在線學(xué)習(xí)方法.

本文針對上述研究存在的問題，考慮文件流行度未知的多基站協(xié)作緩存場景，圍繞文件的總傳輸時延進行了優(yōu)化問題建模.在組合多臂賭博機(Combinatorial Multi-Armed Bandit, CMAB)[14]框架下，利用文件請求的歷史信息進行在線學(xué)習(xí)，從而生成文件流行度的估計，并進一步給出了啟發(fā)式文件緩存優(yōu)化算法.

1 系統(tǒng)模型

假設(shè)異構(gòu)蜂窩網(wǎng)絡(luò)由一個內(nèi)容服務(wù)器和多個基站構(gòu)成.內(nèi)容服務(wù)器作為中心節(jié)點，文件目錄包含了待請求的所有文件；基站可滿足部分文件的緩存.服務(wù)器可控制、調(diào)度和響應(yīng)基站，配合基站分別對不同區(qū)域的用戶提供文件服務(wù).為了提高整個網(wǎng)絡(luò)服務(wù)的能力和效率，服務(wù)器和基站之間需要聯(lián)動地設(shè)計合理的緩存方案.服務(wù)器通過不斷接收各個基站緩存特定文件后的反饋，提高對特定文件流行度的認(rèn)知，進而優(yōu)化各個基站的文件緩存方案以提高整個網(wǎng)絡(luò)的服務(wù)效率.

圖1 協(xié)作緩存網(wǎng)絡(luò)示意圖Fig.1 Example of the cache-enabled cooperative networks

如圖1所示，網(wǎng)絡(luò)中多個基站(Base Station, BS)用集合B={1,2,…,b,…,B}表示，每個BS服務(wù)于其所覆蓋范圍內(nèi)的用戶文件請求.不同BS所服務(wù)的用戶集合使用U={u1,u2,…,ub,…,uB}表示，用戶可隨機從文件集合K={1,2,…,k,…,K}中選擇文件請求，文件的大小由集合S={s1,s2，…,sk,…,sK}表示.不同BS的緩存容量為M={M1,M2,…,Mb,…,MB}.

(1)

假設(shè)信道條件平穩(wěn)，信道平均傳輸速率恒定[16]，3種傳輸方式的傳輸速率定義如下： 基站和用戶直接傳輸?shù)乃俾蕿関BD，基站和基站之間的傳輸速率為vBB，核心網(wǎng)絡(luò)和基站之間的傳輸速率為vCB，三者之間滿足vBD>vBB>vCB.就系統(tǒng)傳輸效率而言，首先選擇基站直傳，其次是基站之間傳輸，最后為向遠端服務(wù)器請求.

2 優(yōu)化問題

本文旨在構(gòu)建合理的模型來表述異構(gòu)蜂窩網(wǎng)絡(luò)服務(wù)的時延特性，進而通過緩存優(yōu)化方案實現(xiàn)低延時的文件下載服務(wù).3種文件傳輸方案使得用戶在周期t請求文件k時存在如下的可能傳輸時延：

1) 基站b緩存文件k，直接傳遞給用戶，傳輸時延為

(2)

2) 基站b未緩存文件k，其他基站緩存了該文件，傳輸時延由基站b從其他基站下載的時延和基站b傳輸給用戶的時延兩部分組成，即

(3)

3) 基站b未緩存文件k，且其他基站也未緩存該文件，傳輸時延由基站b從核心網(wǎng)獲取的時延和基站b傳輸給用戶的時延兩部分組成，即

(4)

結(jié)合式(2)～(4)得出基站b在t周期服務(wù)用戶請求文件k的時延為

(5)

在t周期定義二元矩陣CB×K={cb,k,t,?b∈B,?k∈K,?t∈T}，其中cb,k,t∈{0,1}代表t周期基站b是否緩存文件k，若cb,k,t=1，則t周期b緩存了文件k，否則t周期b未緩存文件k.式(5)中的c-b,k,t表示t周期除基站b之外其他基站是否緩存文件k.同樣，若t周期其他基站緩存了文件k，則c-b,k,t=1，反之，c-b,k,t=0.那么c-b,k,t可以表示為

(6)

基站b每完成一個文件請求都可獲得一定的回報.對于某個請求任務(wù)，若傳輸時間長，那么用戶體驗差，基站單次可獲得的回報少，反之若傳輸時間短，那么基站單次可獲得的回報多.假設(shè)每個時間周期基站都能完成對于所有請求文件的響應(yīng)，定義在t周期基站b傳遞文件k所能獲得的回報函數(shù)為

rb,k,t=db,k,t(ΔT-lb,k,t)R0,

(7)

其中R0為單位回報常數(shù).由于回報往往是正數(shù)，因此ΔT應(yīng)取lb,k,t的上界.

圖2 回報和時延關(guān)系圖Fig.2 Relaionship between reward and latency

由式(7)，可得到基站b單次請求下的回報rb,k,t和傳輸時延lb,k,t之間的線性反比關(guān)系，如圖2所示.因此最大化回報等同于最小化傳輸時延問題.

(8)

鑒于優(yōu)化目標(biāo)希望尋找合理的緩存策略使得在一定時間積累下的期望總回報最大，問題P1可描述為

(9)

式(9)中的約束條件表明基站的存儲空間有限，不能將所有文件存儲在基站，故基站應(yīng)盡可能緩存高流行度文件，以獲取最大的系統(tǒng)回報.

3 算法原理

對于優(yōu)化問題P1，若流行度已知，則任意周期下的最優(yōu)緩存策略都是一致的.由于此處流行度未知，在每個周期t，網(wǎng)絡(luò)服務(wù)器首先需利用對基站緩存文件所得回報的觀測更新文件流行度的估計，進而將估計值代入問題P1求解得到優(yōu)化的緩存方案再配發(fā)到各個基站.流行度估計及緩存算法均在網(wǎng)絡(luò)服務(wù)器完成，為集中式算法.算法的迭代可分為流行度估計和NP完全問題求解兩步.

3.1 流行度估計

經(jīng)典的多臂賭博機問題(MAB)[17]是構(gòu)建未知環(huán)境中隨機最優(yōu)決策問題的一類數(shù)學(xué)工具.賭博機有若干個臂(拉桿)，每個臂對應(yīng)一定的回報，回報服從固定但是未知的分布.玩家通過拉臂可以觀測到即時的回報，通過不斷重復(fù)調(diào)整策略，目的是使得總期望回報最大.MAB的本質(zhì)是“探索”(嘗試更多未嘗試的臂)和“利用”(利用當(dāng)前狀態(tài)下獲得回報最大的臂)之間的權(quán)衡問題.若在MAB問題中，每次可有多個臂同時拉下則為組合多臂賭博機(CMAB)問題[14].

CMAB框架下，玩家每次可以選擇一個超臂(多個臂的組合)，超臂對應(yīng)一定回報，玩家通過拉臂可以得到未知分布下的觀測，CMAB算法是利用該結(jié)果的歷史信息決策每輪如何選擇最優(yōu)的超臂以獲得最大的回報.在本問題中，可將網(wǎng)絡(luò)服務(wù)器看作玩家，將每個基站-文件對視為賭博機的一個臂，那么在周期t，中心節(jié)點決定讓基站b存儲文件k，表明玩家選擇了(b,k)這個臂，對應(yīng)cb,k,t=1；若決定基站b不存儲文件k，則對應(yīng)的cb,k,t=0.每輪共有B·K個臂可供中心節(jié)點在滿足公式(9)約束條件的前提下進行多重選擇，中心節(jié)點每個t周期求解得到的緩存方案At={cb,k,t|cb,k,t=1,?b∈B,?k∈K}均為一種超臂方案.在每輪選擇超臂方案At后，可觀測到超臂中每個(b,k)在周期t所產(chǎn)生的請求db,k,t，據(jù)觀測結(jié)果對流行度的估計進行更新.得到新的流行度的估計后，通過求解優(yōu)化問題對超臂的選擇進行調(diào)整，二者相互促進，直到得到最優(yōu)的超臂.故優(yōu)化問題P1可等價轉(zhuǎn)化為求解CMAB問題.

參照CUCB算法[14]，本文提出CUCB-PE(Popularity Estimation)算法(見表1).

表1 CUCB-PE算法

為了分析算法CUCB-PE的性能，需要計算損失(regret)，即理論最優(yōu)收益R(Θ,Copt)和實際收益R(Θ,C)的差值.由于問題P1是NP完全問題，達到理論緩存的最優(yōu)總收益R(Θ,Copt)計算困難，故考慮算法以β的概率輸出最少α倍的最優(yōu)解，用α·R(Θ,Copt)表示近似的最優(yōu)總收益.若緩存策略帶來的期望收益達不到期望最優(yōu)總收益，認(rèn)為該超臂的選擇是次優(yōu)的，定義包含所有可能的次優(yōu)決策集J={C|R(Θ,C)<α·R(Θ,Copt)}.對于基站b和文件k，定義選取次優(yōu)決策所帶來的最大和最小的損失為[14]

定理2本文提出的CUCB-PE算法經(jīng)過n輪的迭代后，可以得到損失上界為

證明見參考文獻[14].

3.2 NP-完全問題算法求解

優(yōu)化問題P1是0-1整數(shù)規(guī)劃，求解過程中先用變量替換將其轉(zhuǎn)化為0-1多項式問題，再基于文獻[18]轉(zhuǎn)化算法將其轉(zhuǎn)化成0-1線性問題.分析如下：

(11)

(12)

(13)

由上式可見，計算復(fù)雜度隨著基站數(shù)量B和文件數(shù)量K呈指數(shù)增長.因此為了降低復(fù)雜度，本文提出了一種次優(yōu)的啟發(fā)式算法.

算法的主要思想是將問題P3松弛為線性規(guī)劃問題，先求解該線性問題，再把連續(xù)的結(jié)果映射到{0,1}上，得到近似解.首先將問題P3的最后一個約束條件替換為

(14)

由于問題P3目標(biāo)函數(shù)優(yōu)化變量的系數(shù)均為正數(shù)，故問題P3的目標(biāo)函數(shù)是凸函數(shù)，故松弛過的線性問題可以在多項式時間內(nèi)由凸優(yōu)化方法進行求解，本文選用原始對偶內(nèi)點法[20]計算方案.算法描述見表2.

由于原始對偶內(nèi)點法得出的解違背了問題P3中的最后一個約束條件，故不是原問題的可行解.根據(jù)松弛后問題的結(jié)果，本文提出一種貪婪算法以求得原問題的可行解.將該算法命名為CR(Cache Recover)算法(見表3).

4 仿真對比

本節(jié)給出算法的仿真對比分析.參考文獻[22]和[23]，通用仿真數(shù)據(jù)設(shè)置見表4.不失一般性，在仿真過程中假設(shè)不同基站不同的文件服從無偏移的Zipf分布，即αb設(shè)為1，γ設(shè)為0.9.

在仿真中，和以下3種算法進行對比：

1) 分支定界算法(B&B)： 得到緩存最優(yōu)解.

2) 最小頻率使用算法(LFU)[24]： 記錄文件緩存次數(shù)，若請求文件未緩存，則替代掉使用頻率最小的文件.

3) 最小最近使用算法(LRU)[24]： 記錄最近2次使用次數(shù)的間隔，若請求文件未緩存，則替代掉間隔長的文件.

圖3見第238頁為以上3種算法和本文算法的緩存回報對比圖，橫軸為迭代次數(shù)，縱軸為緩存回報.本文算法初始化階段對單個文件逐一進行緩存嘗試，因此這段周期不具備可比性.從圖中可以看出，迭代20次時開始，本文算法與最優(yōu)解的緩存回報已非常接近且呈現(xiàn)收斂趨勢，明顯優(yōu)于另外兩個對比算法.對比算法與初始化強相關(guān)，且未對文件流行度進行估計，同時未考慮基站之間的合作，故本文提出的算法明顯優(yōu)于對比算法.

圖3 不同算法的緩存回報比較Fig.3 Caching reward comparison among different algorithms

圖4對3種算法的累計損失性能進行比較，橫軸為迭代次數(shù)，縱軸為損失的對數(shù).累計損失函數(shù)的計算方法為： 每個周期t，將Zipf分布參數(shù)固定且已知的最優(yōu)回報(由分支定界算法確定)與同周期算法回報作差得到當(dāng)前周期的凈損失，并對到t周期為止的凈損失進行求和得到t周期的累計損失.為了使效果更加顯著，將損失函數(shù)取對數(shù)，得到對數(shù)化損失lg(reg).從仿真圖中可以看出，在1000次迭代以后，3條曲線接近平行，但由于對數(shù)化損失函數(shù)進行了以10為底的對數(shù)化處理，故縱坐標(biāo)的每個刻度之間有著數(shù)量級的差別，實際上隨時間的增加，本文算法的累計損失絕對值和增速均遠遠小于對比算法的2條曲線.

圖4 不同算法的對數(shù)損失比較Fig.4 Logarithm of caching regret comparison of different algorithms

圖5 緩存回報和存儲容量比的關(guān)系Fig.5 Caching reward versus the percentage of caching memory

圖6 緩存回報和Zipf分布參數(shù)的關(guān)系Fig.6 Caching reward versus γ

圖7 緩存回報和文件數(shù)量的關(guān)系Fig.7 Caching reward versus number of contents

圖6表征了緩存回報和Zipf分布參數(shù)γ之間的關(guān)系，γ的范圍設(shè)定在0.7～1.9之間，縱軸為運行100次回報取平均值.如仿真結(jié)果所示，緩存回報隨著γ的增加而增大.理由是當(dāng)γ較大時，更多的請求來自于少數(shù)更為流行的文件，則基站緩存同樣數(shù)目流行度高的文件可滿足更多的用戶請求，進而獲得更高的回報.

圖7見第238頁顯示了緩存回報和文件數(shù)量之間的關(guān)系，橫軸為文件數(shù)量，縱軸為運行100次回報的平均值.文件數(shù)量K的仿真參數(shù)范圍設(shè)定在10～100之間，每個基站的存儲容量調(diào)整為300.隨著文件數(shù)量的增加，同樣的緩存容量下緩存回報逐漸減少，這是由于盡管流行度分布的偏度不變，但文件個數(shù)的增多使得用戶請求被分散在更多不同的文件中，基站的自身緩存就相對更難覆蓋用戶的請求.

5 結(jié) 語

本文研究了流行度確定但未知場景下的多基站緩存問題，基于傳輸時延最小化進行分析建模，同時考慮基站之間的協(xié)作緩存.對于用戶請求，若基站未緩存該文件，則從其他基站進行傳輸，若其他基站未緩存，則通過回程鏈路傳輸，由于基站之間的合作大大降低了中心網(wǎng)絡(luò)的回傳壓力，降低了傳輸時延，提升了用戶體驗.鑒于文件請求的流行度未知，使用CMAB對其進行實時估計.本文提出的文件緩存優(yōu)化問題本身為0-1多項式問題，將其轉(zhuǎn)化為0-1線性問題后依然是NP完全的，為了減少計算復(fù)雜度，提出啟發(fā)式算法進行求解.仿真部分對本文提出的算法及常用算法在不同環(huán)境條件下進行了緩存回報和損失的對比，從存儲容量、流行度分布及文件數(shù)量等多個角度證明了本文算法應(yīng)對不同環(huán)境的魯棒性以及接近于最優(yōu)解的性能和線性的計算復(fù)雜度.