[發明專利]一種基于調節矩陣的異構部分重復碼的構造方法

有效

• 申請號: 201911135000.1
• 申請日: 2019-11-19
• 公開（公告）號: CN110990375B
• 公開（公告）日: 2023-01-31
• 發明（設計）人: 王靜;沈克勤;孫偉;張鑫楠;何亞錦
• 申請（專利權）人: 長安大學
• 主分類號: G06F16/21
• 分類號: G06F16/21;G06F16/22;G06F16/2453;G06F16/27;G06F11/07
• 代理公司: 西安恒泰知識產權代理事務所 61216
• 代理人: 李鄭建

1.一種基于調節矩陣的異構部分重復碼的構造方法，其特征在于，該方法用于構造節點存儲容量異構的FRC，適用于分布式存儲系統節點數n為奇數的情況，且構造的FRC中數據塊的重復度ρ等于2；具體步驟如下：

步驟1：首先定義一個循環置換矩陣C_n(d-1)，該矩陣是一個n×n階的二進制矩陣，其中，n代表節點數，d-1表示每個節點存儲容量同時也表示矩陣中每一行1的個數，且d需滿足的條件為d3，d為奇數；

C_n(d-1)矩陣的第一行在數學上滿足的表達式為：

c(t)＝t+t²+…+t^(d-1)/2+t^n-(d-1)/2+…+t^n-1；

矩陣的第一行確定后，后面的每一行依次向右移動一位，共移動n-1次，最后生成C_n(d-1)矩陣；

在這里C_n(d-1)矩陣同時也是一個關聯矩陣，該關聯矩陣的行對應分布式存儲系統中的節點，列代表存儲的數據塊，同時這個關聯矩陣與未經過調節矩陣構造的同構FRC是一一對應的關系；

為了更加直觀的看出內部FRC的存儲結構，引入正則圖存儲同構的FRC，所述正則圖通過關聯矩陣[θ]＝{1,2,...,13}得出；正則圖的頂點n也就對應FRC中的節點數，正則圖的邊代表數據塊，d-1代表節點的度；

步驟2：引入一個矩陣S_n去調節步驟1中的C_n(d-1)矩陣，S_n矩陣生成方法為：在(n-1)階副對角線都為1，其他元素全為0的矩陣后面加一行0和一列0生成S_n矩陣；

步驟3：將步驟1中的矩陣C_n(d-1)和步驟2中的矩陣S_n進行模2運算，得到新的矩陣P,該矩陣P＝C_n(d-1)+S_n(mod2)；矩陣P同時也是一個關聯矩陣，這個關聯矩陣與經過調節矩陣構造的異構FRC是一一對應關系，為了更加直觀的體現內部FRC的存儲結構，引入部分正則圖的概念，將其記做PGR(n,d)，其中，n表示頂點數也就對應FRC中的節點數，圖的邊代表數據塊，d代表節點的度的最大值；

得到的矩陣P是一個n×n階的二進制矩陣，矩陣P的不同行中會出現有d,d-1,d-2個1的情況，因此對應的部分正則圖的度有d,d-1,d-2三種情況，也就對應著構造的FRC的節點存儲容量有d,d-1,d-2三種情況；

因此，通過調節矩陣S_n得到不同存儲容量的節點，其異構特性滿足實際的分布式存儲系統。

2.如權利要求1所述的基于調節矩陣的異構部分重復碼的構造方法，其特征在于，所構造節點存儲容量異構的FRC用于修復單故障節點的應用。

3.如權利要求2所述的基于調節矩陣的異構部分重復碼的構造方法，其特征在于，所述的構造節點存儲容量異構的FRC用于修復單故障節點的應用，根據異構FRC的特點分析故障節點修復的問題，因為該構造針對重復度ρ＝2的FRC，故只能考慮單節點故障修復問題，分以下3種情況：

a)若存儲容量為d的節點出現故障，那么只需要從另外的d個節點分別下載一個數據塊直接修復；

b)若存儲容量為d-1的節點出現故障，那么只需要從另外的d-1個節點分別下載一個數據塊直接修復；

c)若存儲容量為d-2的節點出現故障，那么只需要從另外的d-2個節點分別下載一個數據塊直接修復。