[發明專利]一種內容中心網絡中文件的最優緩存配置方法

有效

• 申請號: 201710106111.4
• 申請日: 2017-02-27
• 公開（公告）號: CN106998353B
• 公開（公告）日: 2020-07-31
• 發明（設計）人: 鄒君妮;王悅
• 申請（專利權）人: 上海大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 上海上大專利事務所(普通合伙) 31205
• 代理人: 陸聰明

1.一種內容中心網絡中文件的最優緩存配置方法，其特征在于，具體步驟如下：

步驟1：分別定義緩存命中率和能量消耗函數；

步驟2：建立聯合最大化的性能目標函數；

步驟3：用貪心算法得到最優緩存配置；

所述步驟1的具體步驟如下：

在一個內容中心網絡中，一般包括源服務器，包含全部的文件資源；邊緣路由器，具有有限的緩存能力且覆蓋許多用戶；當用戶請求視頻時，首先嘗試向自己所屬的邊緣路由器請求內容，如果其所屬的邊緣路由器沒有其所需的內容，其邊緣路由器向周圍的邊緣路由器請求內容，如果仍然沒有，該用戶則向源服務器請求內容，因此為了使用戶獲得更好的體驗，如何進行緩存內容的放置顯得十分關鍵；如果僅僅只考慮用戶命中率的問題，緩存配置問題會變得很簡單，每個邊緣路由器只需要緩存被請求概率最大的文件；同時，還需要考慮視頻內容在傳輸過程中的能量消耗問題，此時我們也希望緩存能有效的節約該網絡的能量；

定義能量損耗：對于能量損耗主要考慮兩部分，分別為緩存功耗和傳輸功耗；緩存功耗E^ca使用能量比例模型來定義：假設文件k的大小為s^k，節點i在時間t內緩存大小為s^k的文件k所消耗的能耗為在這里w_ca是緩存的能量系數，它取決于緩存的硬件條件，節點和路由器是等同的概念；傳輸功耗E^tr指的是當邊緣路由器向其他邊緣路由器請求內容時會產生傳輸功耗，主要包含路由能量功耗和鏈路的能量消耗；當節點i向節點j請求文件k時消耗的能量為其中指的是節點i對文件k的請求速率，也表示文件的流行性分布，d_i,j指兩個路由器i和j的距離，當j＝-1時表示邊緣路由器i和源服務器之間的距離，表示核心路由器的能量密度，表示ROADM的能量密度，表示WDM鏈接的能量密度；對于一個傳統的沒有緩存設備的網絡，所有文件都需要從服務器進行傳輸，其總能量消耗為

對于能耗部分，具體定義為：

其中N表示節點總數量，M表示文件總數量，x_i,k和y_i,j,k均為指示變量，當x_i,k為1時表明節點i緩存了內容k，否則為0；當y_i,j,k為1時表明節點i從節點j下載內容k，否則為0，當j＝-1時，表示節點從服務器獲取所需內容；

定義緩存命中率：所謂緩存命中率指的是節點所請求的文件能在緩存中被滿足的概率，若想要最大化緩存命中率就是盡量減少從源服務器請求文件的概率，具體定義為：

所述步驟2的具體步驟如下：由最大命中率和最小能量消耗來決定的緩存內容放置策略寫成這樣的形式：

y_i,j,k≤x_i,k (4)

y_i,-1,k+x_i,k+∑_j≠iy_i,j,k＝1 (5)

在式(1)中，寫成兩部分，能量消耗部分和命中率部分其中能量消耗部分由三個部分表示分別為緩存消耗，訪問其他節點消耗以及訪問服務器消耗；式(2)表示節點i上緩存的內容大小不能超過最大緩存空間C_i，式(4)表示只有內容在節點j上時，節點i才能從j上下載內容k；式(5)表示一個節點的請求被自身緩存、其他節點緩存或者服務器滿足；

所述步驟3的具體步驟如下：問題P1的約束條件是滿足擬陣條件的，聯合目標函數是滿足亞模性質的，對于基于擬陣約束的最大化亞模問題一般采用貪心算法尋求近似解，貪心算法從空集開始；在每次迭代中，向集合中增加邊際效用值最大的元素，

在貪心算法之前，對一些變量進行計算，首先令這樣式(1)中的目標函數可以表示為maxf(X)＝max[h(X)+g(X)]，其中基集X＝{x_1,1,x_1,2,...,x_1,M,...,x_N,M}表示所有可能被放在節點緩存中的文件集合，假設節點中文件的存儲是和其流行性相關的，即其次分別計算命中率函數h(X)和能量消耗部分函數g(X)的邊際效用：

命中率：在此考慮兩種情況：1)假如文件k不在節點的緩存中且節點緩存空間還有富余時，那么節點會緩存該文件，其邊際效用為2)當其他節點已經緩存了該文件時，節點i會將該文件與最受歡迎的文件進行交換；把這樣的文件記做k'，這樣邊際效用為

能量消耗：將和E^sr的表達式代入g(X)中，得其中利用約束條件(5)將其進行化簡得考慮兩個放置集合X₁和X₂，X₁＜X₂；我們把新文件加入到兩個集合中，對于放置集合X₁來說同樣分兩種情況考慮，1)假如文件k不在節點的緩存中且節點緩存空間還有富余時，那么節點會緩存該文件，其邊際效用為2)當其他節點已經緩存了該文件時，節點i會將該文件與最受歡迎的文件進行交換；把這樣的文件記做k'，這樣邊際效用為當把文件k加入到集合X₂中，因為文件k不屬于X₂，同樣分兩種情況考慮，1)假如文件k不在節點的緩存中且節點緩存空間還有富余時，那么節點會緩存該文件，其邊際效用為2)當其他節點已經緩存了該文件時，節點i會將該文件與最受歡迎的文件進行交換；把這樣的文件記做k'，這樣邊際效用為

貪心算法從空集開始，在每步迭代中，貪心算法選擇具有最高邊際效用的x_i,k，選擇元素x_i,k代表節點i緩存文件k，因為目標函數(1)為亞模函數，隨著加入集合中元素的增多，邊際效用值會減小，在某一次迭代中如果所選擇元素的邊際效用值為0，那么下一個被選擇的文件的邊際效用值也為0；因此，我們的迭代將會在邊際效用為0的時候停止，所有被選擇的文件在開始時都根據文件的流行性降序存儲在初始集合D中，初始元素集合D也就是基集X，在每次迭代中，我們從集合D中移出元素x_i,k，如果某個節點i的緩存空間變滿，那么將集合D中和i相關的元素全部移除，這樣節點i相關元素的邊際效用值將不會被考慮在隨后的迭代中，放置集合X和每個被節點i緩存的文件x_i,k在每次迭代的時候更新，最后貪心算法會返回放置集合X。