[發明專利]基于雙倍復制的MDS緩存方案

在審

• 申請號: 201811267307.2
• 申請日: 2018-10-29
• 公開（公告）號: CN109445990A
• 公開（公告）日: 2019-03-08
• 發明（設計）人: 顧術實;王念念;王野;李柯;李娟;張欽宇
• 申請（專利權）人: 哈爾濱工業大學（深圳）
• 主分類號: G06F11/14
• 分類號: G06F11/14;H04L29/08;H04W4/70
• 代理公司: 深圳市添源知識產權代理事務所(普通合伙) 44451
• 代理人: 羅志偉

1.基于雙倍復制的MDS緩存方案，其特征在于：所述基于雙倍復制的MDS緩存系統(以下簡稱DR-MDS緩存系統)將原始文件分為k塊，k≥2，通過MDS編碼生成n個編碼符號，每個編碼符號包含數據，每個節點存儲1個編碼符號；其次將n個編碼符號進行備份，緩存到2n個移動設備中，其中n個為存儲節點，另外n個為備份節點；存儲相同數據的節點互為備份節點；

當任意一個存儲節點丟失，但其備份沒有丟失，通過備份修復丟失數據；

當存儲節點和備份節點同時丟失時，通過MDS方式修復其中一個節點，然后通過新修復的節點復制修復備份節點；

下載文件時，連接任意k個不相關的存儲節點即可恢復原文件。

2.根據權利要求1所述的基于雙倍復制的MDS緩存方案，其特征在于：所述DR-MDS緩存系統以D2D分布式存儲系統為模型，在以基站提供的單個網絡中，當存儲節點離開DR-MDS緩存系統時有三種修復方式：

備份節點沒有離開系統時，通過備份數據修復；

當存儲節點和備份節點都離開系統時，通過MDS修復一份數據，再修復備份數據；當系統中不相關的存儲節點小于k時通過基站修復數據，k≥2；

DR-MDS緩存系統的下載有兩種方式：當DR-MDS緩存系統中的不相關的存儲節點數不小于k時，通過MDS鏈路下載文件，否則通過基站直接下載數據。

3.根據權利要求2所述的基于雙倍復制的MDS緩存方案，其特征在于：所述D2D分布式存儲系統在修復過程產生整體通信開銷，整體通信開銷包括兩部分：一部分是存儲節點離開系統后更新新節點數據帶來的修復開銷，另一部分是用戶請求文件的下載開銷。

4.根據權利要求3所述的基于雙倍復制的MDS緩存方案，其特征在于：所述修復開銷是對丟失的數據的修復，存在通過備份數據修復、通過MDS修復和通過基站修復三種修復方式：

其中，當i≤n時，丟失的i個存儲節點中最少存在0對存儲相同數據的節點，可通過備份數據修復；

當i>n時，除去n個不相關的存儲節點之外，其余的都為備份節點，采用復制MDS編碼修復丟失數據，當丟失的i個存儲節點中有j對節點存儲相同的數據時，可以通過備份數據修復的節點數為(i-2j)；

其中，i表示丟失的存儲節點數；j表示丟失i個節點時存在的存儲相同數據節點數，n表示復制之前系統中總的節點數目。

5.根據權利要求4所述的基于雙倍復制的MDS緩存方案，其特征在于：所述下載開銷包括通過D2D鏈路下載和BS鏈路下載兩部分；其中，當系統中至少存在k個不相關的存儲節點時，用戶通過D2D鏈路下載，否則通過BS鏈路下載；當系統中存儲節點小于k個時，系統中不相關的存儲節點數肯定小于k，用戶通過BS鏈路下載文件；當存儲節點數大于2k-2時，用戶通過D2D鏈路下載文件；其中k≥2。

6.根據權利要求5所述的基于雙倍復制的MDS緩存方案，其特征在于：所述下載開銷的計算過程為：

當系統中存在i個存儲節點時，有(n-i)個存儲節點離開，此時系統中存在不相關的k個存儲節點的概率為少于k個不相關的存儲節點的概率為在[0～Δ]時間內，丟失的節點數可能為0,1,2,…,2n，定義和分別為系統中存在i個存儲節點時用戶通過D2D鏈路和BS鏈路下載文件的概率，且

通過D2D鏈路和基站鏈路下載文件傳輸的數據量都為F，系統中存在i(i＝k+1,k+2,…2k-2)個存儲節點時，通過公式：

一次請求發生時的下載開銷；

當請求發生時，系統中至少存在i個存儲節點的概率S_i為：

而系統中恰好存在i個存儲節點的概率為則[0～△]時間內，系統中存在i個存儲點則表示有(2n-i)個存儲節點離開，由此通過公式：

計算在Δ時間內單位時間內總的下載開銷C_d，其中Δ為修復間隔。