鬼佬大哥大
  • / 26
  • 下載費用:30 金幣  

基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法.pdf

摘要
申請專利號:

CN201510162479.3

申請日:

2015.04.08

公開號:

CN104915370A

公開日:

2015.09.16

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 17/30申請日:20150408|||公開
IPC分類號: G06F17/30 主分類號: G06F17/30
申請人: 天津理工大學
發明人: 郭星; 徐光平; 張樺; 薛彥兵; 高贊; 徐珂瓊
地址: 300384天津市西青區賓水西道391號天津理工大學主校區
優先權:
專利代理機構: 天津佳盟知識產權代理有限公司12002 代理人: 侯力
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510162479.3

授權公告號:

||||||

法律狀態公告日:

2018.11.06|||2015.10.14|||2015.09.16

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

一種基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法。包含以下步驟:使用初始編碼生成算法生成搜索起始編碼矩陣;輸入參數初始化搜索進程,采用C4圈數量作為啟發式準則,利用固定行重列重矩陣交換操作產生鄰域編碼矩陣;通過禁忌搜索策略迭代搜索得到最優編碼矩陣。本發明首先針對現有分片復制碼編碼矩陣構造方法只限于有限參數的情況,提出基于禁忌搜索的編碼矩陣搜索方法,可在任意合法參數下給出分片復制碼的編碼矩陣;其次本發明針對現有構造方法構造的編碼矩陣存儲效率較低的問題,提出了基于C4圈計數的啟發式規則,使得本方法的結果達到理論最優;最后本發明提出C4圈計數矩陣計算法,簡化算法核心運算過程,極大加快搜索速度。

權利要求書

權利要求書
1.  一種基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法,其特征在于該方法具體包含以下步驟:
第1、搜索起始編碼矩陣的生成
在分布式存儲系統中,將一個文件分為若干數據塊后存儲在n個節點上,每個節點存儲d個不同的數據塊,連接任意k個節點可重構出原文件,滿足以上性質的分布式存儲系統稱為(n,k,d)DSS
(n,k,d)DSS中,FR編碼C:(n,θ,d,ρ)的定義如下:
FR編碼C:(n,θ,d,ρ)定義為集合V={V1,V2,…,Vn},其中Vi為集合[n]={1,2,…, θ}的子集且|Vi|=d,滿足集合[n]中的任一元素出現在V中的ρ個集合里;其中n即為(n,k,d)DSS中的n,表示參與文件存儲的存儲節點數量,d(n,k,d)DSS中的d,表示每個存儲節點上存儲的數據塊數量,θ表示文件被分割成的數據塊的總數量,ρ表示每個數據包的存儲次數;集合Vi表示編號為i的存儲節點上需存入的數據包編號;且參數n,θ,d,ρ滿足:
                                (1)
算法需根據存儲文件和分布式存儲系統的具體需要,輸入參數ndθρ,使用初始矩陣生成算法生成與上述定義相對應的每行權重為d、每列權重為ρn×θ布爾矩陣,此布爾矩陣即搜索的起始編碼矩陣;
使用布爾矩陣An×θ描述,則矩陣的各行代表存儲節點,各列代表數據塊,從而當FR編碼的節點i需要存儲數據塊j,則矩陣A中ij列的位置為1,否則為0;
首先根據存儲文件和分布式存儲系統的具體需要,輸入參與文件存儲的存儲節點數n,每個存儲節點存儲文件塊數d,文件分割數據塊數θ,每個數據塊的復制深度ρ;根據以上參數,算法使用初始矩陣生成算法生成每行中1數量皆為d且每列中1數量皆為ρ初始布爾矩陣;
即初始矩陣為行權重序列為R,列權重序列為Sn×θ布爾矩陣,RS定義如下:
 和                 (2)
行權重序列R表示布爾矩陣每行中1的數量,列權重序列S表示布爾矩陣中每列中1的數量;
第2、禁忌搜索初始化
在第1步獲得搜索的起始編碼矩陣后,初始化搜索所使用的搜索節點;首先將起始編碼矩陣作為起始搜索節點的編碼矩陣M;其次計算起始搜索節點的C4圈計數矩陣C4_Matrix;同時以C4_Matrix中所有元素之和作為此矩陣的C4圈數并以此初始化搜索進程的當前最優C4圈數Opt_C4和搜索節點C4圈數C4_Num;再次輸入參數k計算此矩陣的冗余率RC(k)并以此初始化當前最優冗余率Opt_RC(k),同時計算冗余率上界g(k);最后輸入禁忌步長最大值step_max,同時將當前節點的禁忌步長step設為step_max,并將搜索進程最優矩陣Opt_M設為起始搜索節點的編碼矩陣M
第3、生成鄰域節點
在第2步得到初始化后的起始搜索節點的基礎上,以起始搜索節點作為當前節點開始搜索;在當前節點上執行固定行重列重矩陣交換操作逐一生成鄰域節點并計算鄰域節點編碼矩陣的C4圈數;若生成的鄰域節點編碼矩陣的C4圈數少于當前節點編碼矩陣的C4圈數,則此鄰域節點為較優節點,執行第4步;若生成的鄰域節點編碼矩陣的C4圈數等于當前節點編碼矩陣的C4圈數,則此鄰域節點為同等節點,執行第5步;若生成的鄰域節點編碼矩陣的C4圈數大于當前節點編碼矩陣的C4圈數則此鄰域節點為較差節點,直接放棄此節點繼續執行第3步;
第4、處理較優節點
計算較優節點編碼矩陣的RC(k),判斷是否達到FR碼存儲能力上界g(k);FR碼C:(n,θ,d,ρ)的存儲能力上界g(k)的定義如下
                                (3)
               (4)
RC(k)等于g(k)則結束算法返回較優節點;否則判斷較優節點C4圈數和RC(k)是否優于搜索進程的當前最優C4圈數和RC(k),若是則以較優節點C4圈數和RC(k)更新當前最優C4圈數和RC(k),記錄較優節點的C4圈數和RC(k),更新較優節點的C4圈計數矩陣,將搜索進程最優矩陣Opt_M更新為較優節點的編碼矩陣M,將較優節點的禁忌步長設為初始值,以較優節點為當前節點執行第3步;
第5、處理同等節點
若生成此同等節點的當前節點的禁忌步長step大于1,則將同等節點的禁忌步長設為step-1,記錄同等節點的C4圈數和RC(k),更新同等節點C4圈計數矩陣,以同等節點為當前節點執行第4步;否則直接放棄此同等節點執行第3步;
第6、輸出結果
算法停止后返回搜索進程最優矩陣Opt_M

2.  根據權利要求1所述的方法,其特征在于第2步禁忌搜索初始化的具體方法包括:
第2.1、計算起始編碼矩陣C4圈數C4_Num與C4圈計數矩陣C4_Matrix
在第1步中獲得起始編碼矩陣的基礎上,采用計算編碼矩陣C4圈數的方法作為禁忌搜索的啟發式規則;C4圈的定義如下:
C4圈為圖論概念,在布爾矩陣中表現為2階子方陣:
                              (5)
C4圈數C4_Num即為此2階子方陣在編碼矩陣中的數量;
在計算編碼矩陣C4圈數C4_Num時,使用C4圈計數矩陣C4_Matrix降低生成鄰域節點時的C4圈數計算量;通過布爾矩陣中的一行看作二進制數,利用二進制數間的并來計算兩行之間的C4圈數,具體計算公式如下:
                    (6)
其中,為i行和j行之間的C4圈數,wij為編碼矩陣Mi行和j行之間的并的值;算法遍歷起始編碼矩陣Mn行中所有兩行組合,利用上述公式(6)計算C4圈數并存入C4圈計數矩陣C4_Matrix;C4圈計數矩陣C4_Matrix中元素C4_Matrixij即表示i行和j行之間的C4圈數;C4圈計數矩陣C4_Matrix中所有元素之和即為C4圈數C4_Num
第2.2、計算冗余率RC(k)
FR編碼C:(n,θ,d,ρ)的編碼矩陣M的冗余率RC(k)的定義如下:
                       (7)
其中[n]={1,…,n}Vi為編碼矩陣M的第i行;
根據公式(7)對RC(k)的定義,算法遍歷起始編碼矩陣n行中的所有k行組合,并計算每個k行組合的并的權值,所有k行組合并的權值中的最小值即為編碼矩陣冗余率RC(k)的值。

3.  根據權利要求1所述的方法,其特征在于第3步生成鄰域節點的方法包括:
第3.1、基于固定行重列重矩陣交換操作生成鄰域節點
使用當前節點的布爾矩陣,通過固定行重列重矩陣交換操作生成鄰域節點;固定行重列重矩陣交換操作的定義如下:
存在如下兩種2階子方陣之一,

經過這種交換,能夠將這兩種子矩陣相互轉換,稱為交換操作;
本步中將逐一生成當前節點的所有鄰域節點;首先遍歷當前解矩陣n行中的所有兩行組合ij;在得到的每個i行和j行中遍歷所有2列組合rl,即得到了矩陣M中所有2×2子矩陣:

判斷編碼矩陣中是否存在可執行交換操作的子矩陣,若是則執行交換操作即生成一鄰域節點,否則繼續判斷下一個子矩陣;
第3.2、計算鄰域節點C4圈數
使用C4圈計數矩陣的方法簡化計算領域節點C4圈數;使用第2步中生成的C4圈計數矩陣C4_Matrix計算鄰域節點C4圈數;重新計算生成此鄰域節點的當前節點C4圈計數矩陣C4_Matrix中i行和j行相關的元素,但不計算C4_Matrixij,其中i和j為生成此鄰域節點使用的2×2子矩陣中的2行。

關 鍵 詞:
基于 禁忌 搜索 分片 復制 最優 冗余 編碼 矩陣 構造 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法.pdf
鏈接地址:http://www.wwszu.club/p-6373497.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大