• / 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行。

說明書

說明書基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法
技術領域
 本發明屬于計算機存儲技術領域,涉及一種基于禁忌搜索的分片復制碼(Fractional Repetition Code)最優冗余率編碼矩陣構造方法,解決現有分片復制碼編碼矩陣構造方法構造的編碼矩陣存儲效率較低、構造適用參數范圍較小的困難,并提高構造速度,可以用于分布式存儲系統的冗余構造。
背景技術
計算機存儲系統冗余技術是利用存儲系統的并聯存儲模型來提高系統數據可靠性和可用性的技術。傳統的冗余技術一般使用兩種方法:數據備份和糾刪碼技術。采用數據備份的存儲系統修復丟失數據速度較快但需使用大量冗余存儲空間,造成了存儲資源的浪費。而采用糾刪碼的存儲系統占用冗余存儲空間較小但恢復數據時需讀取較多數據且需進行計算,不僅加速了存儲設備的損耗且對存儲系統有了計算功能上的要求。分片復制碼能夠很好的克服這些問題,適用于大型分布式存儲系統、商用云存儲系統以及對數據可靠性或可用性要求較高的各種類型存儲系統。
分片復制碼技術(FR編碼)是由Rouayheb和Ramchandran提出的一種基于特定組合結構的糾刪編碼。該編碼兼有數據備份和傳統糾刪碼的優點,修復數據時讀取數據量最低且不需要計算,同時具有比傳統糾刪碼更大的冗余率。由于FR編碼優良的性能,大量的研究者投入到了FR編碼的研究中。FR的冗余率主要依靠其特定組合結構決定,現有得出這種特定組合結構的方法主要為依靠組合數學特定結構的構造法和基于布爾矩陣算法的構造法。由于組合數學特定結構對參數有較嚴要求,因此大部分參數下的FR編碼無法由組合數學特定結構得出。布爾矩陣算法雖能給出所有參數下的FR編碼矩陣,但其給出的編碼矩陣冗余率較低,實用性較低。
如何在任意參數下給出FR編碼的編碼矩陣同時保證其冗余率最優是研究的重點和難點。由于每組參數下的編碼矩陣各不相同,因此選取的構造方法對結果有很大影響;FR編碼冗余率的本質是編碼矩陣中1的分布對于參數是否均勻,這是可以看作矩陣的一個整體屬性,因此任何一個1的位置改變都有可能改變編碼矩陣的冗余率。
發明內容
本發明的目的是克服現有技術存在的上述問題,提出一種基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法。由于現有的方法不能在任意參數下給出最優冗余率的FR編碼,基于禁忌搜索的構造方法能夠很好的克服這些問題,可給出任意參數下的最優冗余率FR編碼。
本發明提供的基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法,該方法具體包含以下步驟:
第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步。
計算編碼矩陣C4圈數,等價于計算編碼矩陣的RC(2)。當編碼矩陣中C4圈數較少到一定程度,其RC(2)即會上升。
本發明通過以下定理,證明了RC(2)RC(k)間的充分關系,具體定理及證明過程如下:
引理3.1. 設γ為一固定行重列重布爾矩陣DRC(2) ,δDRC(k)時,γδ存在以下關系:

證明:由RC(k)定義可知,D中任意兩行中相同列的1的個數最多為2d-γ。不失一般性,令k=3,當出現最差情況,即3行不存在同一列的3個位置皆為1,又因任意兩行間相同列的1數最多為γ,則矩陣Dδγ有以下關系:δ≥3d-3(2d-γ)。以此類推,得證。
引理3.1實際通過RC(2)給出了RC(k)值的一個下界,顯然,若一個矩陣的RC(2)的值增大,無論k為何值, RC(k)的下界也隨之增大。則由引理3.1,RC(2) RC(k) )存在以下關系:
定理3.1.設γ為一固定行重列重布爾矩陣DRC(2) ,δDRC(k)時,若δ不為最大時,必存在正整數ηφ,對任意與D行重列重相同的布爾矩陣F和任意正整數ε,當ε≥φγ≤η,矩陣FRC(2)RC(k)有:

其中ε+γ≤2d-1
證明:由引理3.1可知,當γ增大時,δ的下界也隨之增大,當矩陣F的下界大于δ時,矩陣F的RC(k)也隨之增大。
第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步所述的禁忌搜索初始化的具體方法包括:
第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步所述的生成鄰域節點的具體方法包括:
第3.1、基于固定行重列重矩陣交換操作生成鄰域節點
使用當前節點的布爾矩陣,通過固定行重列重矩陣交換操作生成鄰域節點;固定行重列重矩陣交換操作的定義如下:
存在如下兩種2階子方陣之一,

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

判斷編碼矩陣中是否存在可執行交換操作的子矩陣,若是則執行交換操作即生成一鄰域節點,否則繼續判斷下一個子矩陣;
第3.2、計算鄰域節點C4圈數
計算鄰域節點C4圈數為算法中運行頻率最高的部分。其時間復雜度為O(n3)。本發明使用C4圈計數矩陣的方法簡化計算領域節點C4圈數,將其復雜度降為O(n2)。
本發明使用C4圈計數矩陣的方法簡化計算領域節點C4圈數;使用第2步中生成的C4圈計數矩陣C4_Matrix計算鄰域節點C4圈數;重新計算生成此鄰域節點的當前節點C4圈計數矩陣C4_Matrix中i行和j行相關的元素,但不計算C4_Matrixij,其中i和j為生成此鄰域節點使用的2×2子矩陣中的2行。
本發明的優點和有益效果:
1)通過引入基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法,解決任意參數下的分片復制碼最優冗余率編碼矩陣構造的問題;2)本發明采用的禁忌搜索方法,克服了傳統的構造法無法構造任意參數的FR編碼的問題;3)本發明公開的C4圈計數方法能夠準確的描述搜索進程中分片復制碼冗余率的內在量變過程,使得禁忌搜索可以用于編碼構造的數學模型之上,從而完成搜索過程中冗余率的優化; 4)本發明提出的C4圈計數矩陣法,簡化每個鄰域節點的C4圈計算過程,極大加快搜索速度。
附圖說明
圖1為本發明的流程圖。
圖2為本發明使用的FR編碼初始編碼矩陣生成算法生成的起始矩陣實例。
圖3為搜索節點初始化后的各個參數示意圖。
圖4為C4圈計數矩陣示例圖。
圖5為起始矩陣產生的數個最優解示例。
圖6為起始矩陣產生的數個同等解示例。
圖7為算法的運行結果。
圖8為在n=12,ρ=2k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖9為在n=24,ρ=2k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖10為在n=36,ρ=2k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖11為在n=12,ρ=3k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖12為在n=24,ρ=3k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖13為在n=36,ρ=3k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖14為在n=12,ρ=4k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖15為在n=24,ρ=4k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖16為在n=36,ρ=4k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
具體實施方式
下面結合附圖對本發明作進一步的描述。
實施例1
如圖1所示,為本發明基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法的操作流程圖,該方法的操作步驟包括:
步驟01搜索起始編碼矩陣生成
首先在根據存儲文件和分布式存儲系統的具體需要,輸入參數ndθρ,用起始編碼矩陣生成算法生成起始編碼矩陣。起始編碼矩陣需為行權重序列為R,列權重序列為Sn×θ布爾矩陣,即:
 和 
目前有分別由Anil和Gupta提出的兩種不同的編碼矩陣生成算法適用本發明的起始矩陣生成算法,本實例中選擇Anil的算法。
如圖2所示,為本發明經過生成算法生成的起始編碼矩陣示意圖。本實施例中n=10,d=4,θ=20,ρ=2。
步驟02禁忌搜索初始化
禁忌搜索是一種應用廣泛的啟發式算法,其實質是將待解決問題的解集用某種規則構造成圖結構并利用特定的策略在此圖結構上進行搜索。
在步驟01生成起始編碼矩陣的基礎上,本發明將需初始化的搜索節點參數分為搜索進程參數與搜索節點兩類。如圖3所示,為本發明搜索初始化后的各個參數。
(1)編碼矩陣、C4圈數及C4圈計數矩陣初始化
C4圈為本發明的關鍵部分,是將編碼矩陣集合構造為圖結構的規則。本發明用定理證明編碼矩陣中C4圈數與編碼矩陣冗余率之間的充分關系,將表示編碼矩陣冗余率的RC(k)轉化為C4圈數,簡化了算法的核心運算。
將步驟01使用的起始編碼矩陣作為起始搜索節點的編碼矩陣M,計算其C4圈計數矩陣C4_Matrix。計算C4圈計數矩陣C4_Matrix有如下公式:

其中,C4_Matrixiji行和j行之間的C4圈數,wiji行和j行之間的并的值。算法遍歷起始編碼矩陣n行中的所有兩行組合,利用上述公式計算C4圈數并將之存入C4圈計數矩陣C4_Matrix。圖4所示即為本實例的起始搜索節點的C4圈計數矩陣。
C4圈計數矩陣中所有元素之和即為起始搜索節點的編碼矩陣矩陣C4圈數C4_Num,之后將搜索進程的當前最優C4圈數Opt_C4和搜索節點C4圈數C4_Num的值設為C4_Num。本實施例中,起始搜索節點的C4圈數為9。
(2)冗余率RC(k)初始化
輸入參數k并以此計算此矩陣的冗余率RC(k)并以此初始化當前最優冗余率Opt_RC(k)。計算此矩陣的冗余率RC(k)有如下公式:

其中[n]={1,…,n}Vi為編碼矩陣中行向量。本實施例中,k為4,起始矩陣的RC(k)為9。
(3)禁忌步長初始化
輸入禁忌步長最大值step_max,同時令當前節點的禁忌步長step=step_max。本實施例中,step_max的值為1。
(4)冗余率上界g(k)初始化
冗余率上界g(k)是由Rouayheb和Ramchandran提出,其定義如下:
(n,k,d)DSS上,FRC編碼C:(n,θ,d,ρ)maxRC(k)≤g(k)g(k)由下式遞歸得到:


步驟03生成鄰域節點
生成鄰域節點為搜索中的核心步驟之一,是運行頻率最高的程序。
在當前節點上執行固定行重列重矩陣交換操作逐一生成鄰域節點,每生成一個鄰域節點時計算其編碼矩陣的C4圈數。固定行重列重矩陣交換操作定義如下:
存在如下兩種2階子方陣之一,

經過這種交換,可將其變為另外一個2階子方陣,稱為交換操作。
本步中將逐一生成當前節點的所有鄰域節點。首先遍歷當前搜索節點的編碼矩陣M的n行中所有兩行組合ij。在得到的每個i行和j行中遍歷所有2列組合kl,即得到了矩陣M中所有2×2子矩陣:

判斷上述子矩陣中是否可執行交換操作,若是則執行交換操作即生成一鄰域節點,否則繼續判斷下一個子矩陣。
若生成的鄰域節點編碼矩陣的C4圈數少于當前節點編碼矩陣的C4圈數則此鄰域節點為較優節點,執行步驟04;若生成的鄰域節點編碼矩陣的C4圈數等于當前節點編碼矩陣的C4圈數則此鄰域節點為同等節點,執行步驟05;若生成的鄰域節點編碼矩陣的C4圈數大于當前節點編碼矩陣的C4圈數則此鄰域節點為較差節點,直接放棄此節點;
步驟04處理較優節點
較優搜索節點為搜索判斷比當前節點更為接近最優解的節點,是算法的主要搜索目標。通過多次迭代尋找較優節點,程序即可逐步減少編碼矩陣的C4圈數量。
計算此較優節點的編碼矩陣RC(k),判斷其是否達到冗余率上界g(k)。若其RC(k)等于g(k)則結束算法返回此節點。否則判斷此節點C4圈數和RC(k)是否優于搜索進程的當前最優C4圈數和RC(k),若是則更新之。以此節點為當前節點,記錄此節點的C4圈數和RC(k)等,更新節點C4圈計數矩陣,將其禁忌步長設為初始值,迭代執行第4步;
如圖5所示為起始搜索節點產生的較優節點的編碼矩陣。圖5中為起始搜索節點產生的3個不同鄰域節點編碼矩陣,圖5(a)中矩陣的C4圈數為8,圖5(b)中矩陣的C4圈數為7,圖5(c)中矩陣的C4圈數為6。
步驟05處理同等節點
同等搜索節點為搜索判斷與當前搜索節點性能相同的節點,但依然有可能通過此節點到達最優解。且隨著搜索的深入,出現鄰域節點中無較優節點的幾率會逐漸增高。故同等節點是算法的次要搜索目標。但由于其數量較多,禁忌搜索采用禁忌步長限制其搜索深度,防止其過多的訪問無用節點。
若當前節點(即生成此同等節點的搜索節點)的禁忌步長step大于1,則將此同等節點的禁忌步長設為step-1,記錄此節點的C4圈數和RC(k)等,更新節點C4圈計數矩陣,以此同等節點為當前節點執行第4步;否則直接放棄此鄰域節點;
如圖6為起始搜索節點產生的同等節點的編碼矩陣。圖6中為起始搜索節點產生的3個不同鄰域節點編碼矩陣,其C4圈數皆為9。
步驟06算法結果
圖7為經過多次迭代之后算法輸出的最優編碼矩陣。本實例中,算法運行結果的編碼矩陣中的C4圈數為0,RC(k)為11,比初始節點提高了2。
實施例2
如圖8~16所示,為本發明基于禁忌搜索的分片復制碼最優冗余率編碼矩陣構造方法的效果說明圖。本實例中,為了方便實際應用,復制深度ρ取實際中最常使用的2,3,4三值;為了方便數據對比,存儲節點數n取可整除2,3,4的12,24,36三值,保證合法參數的數量最多。
本實例中,每個參數使用了分別由Srijan Anil和Toni Ernvail提出的兩種不同的編碼矩陣生成算法生成的編碼矩陣作為起始編碼矩陣。實例說明,本發明提出的方法在任何參數下,使用完全不同的起始搜索節點都可得到最優解。
圖8為在n=12,ρ=2k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖9為在n=24,ρ=2k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖10為在n=36,ρ=2k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖11為在n=12,ρ=3k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖12為在n=24,ρ=3k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖13為在n=36,ρ=3k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖14為在n=12,ρ=4k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖15為在n=24,ρ=4k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。
圖16為在n=36,ρ=4k=4情形下,d取所有合法值的兩種初始解,優化解和上界RC(k)之間的對比。A為使用Srijan Anil的編碼矩陣生成算法作為起始矩陣生成算法得出的結果,B為使用Toni Ernvail的編碼矩陣生成算法作為起始矩陣生成算法得出的結果。A和B兩圖中橫坐標為參數d的取值,縱坐標為冗余率RC(k)。

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

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


收起
展開
山东11选5中奖结果走势图