[發明專利]一種基于蟻群算法的云副本放置方案

在審

• 申請號: 201910324079.6
• 申請日: 2019-04-22
• 公開（公告）號: CN109902797A
• 公開（公告）日: 2019-06-18
• 發明（設計）人: 王鑫;覃琴;孟雨;閆月
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;H04L29/08
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 劉梅芳

1.一種基于蟻群算法的云副本放置方案，其特征是，包括如下步驟：

1)確定副本放置模型：

在云存儲系統中，在副本被創建之后，用戶需要對副本進行合理的放置以保證數據的訪問的性能，系統會在一系列副本中選出最佳的副本進行放置，不同系統的副本放置的標準也會不同，當有符合系統要求多個副本需要放置時，通過統計不同文件的訪問開銷，首先對文件訪問頻率貢獻大的副本進行放置，定義文件的訪問頻率為公式(1)：

R表示整個系統中的副本的個數，file_r(f)表示高頻率文件在副本r中頻率的大小，用來表示文件在第t個時間周期內被請求訪問的次數，

文件所應放置的副本的數量為公式(2)：

最后響應給請求的用戶，副本放置中有以下兩個關鍵的過程：

(1)根據用戶請求中給定的檢索文件名，通過云存儲系統的副本管理器查找該檢索文件名對應的若干個副本位置信息集合；

(2)在問題(1)的基礎上，查找出的若干個副本信息集合后，利用相關副本放置策略再進行相關副本的放置；

2)定義蟻群優化算法與副本放置結合：結合的3個原則為：

(1)把螞蟻覓食時行走的路徑抽象成目標放置前選擇的過程，把路徑集合抽象成一個解空間；

(2)螞蟻移動過程中，會留下信息素，信息素會隨著時間在較短路徑上越來越濃，選擇這條路的螞蟻也會越來越多；

(3)蟻群信息素的正反饋作用，使蟻群的行走路徑逐漸變得統一，最終到達目的地，完成對目標的放置，此條路徑便是目標放置的最優解；

依據以上原則，則有把蟻群抽象成選擇放置副本的檢索文件RF(Retrieve Files，簡稱RF)，同時會為該文件創建和尋找相應的副本，把螞蟻行走路徑的集合抽象為副本對象的集合R＝{r₁,r₂,...r_n}，這樣螞蟻覓食的過程就變成了檢索文件尋找相應副本并放置的過程；

假設螞蟻尋食行走的路徑集合為P＝{p₁,p₂,...,p_n},這里n為螞蟻的個數；覓食過程中所產生的信息素表示為集合Γ＝{τ₁,τ₂,...τ_n}，

設置整個蟻群是一個可行解的解空間，整個蟻群表示為A，對副本的信息素值進行初始化如公式(3)：

其中，replicasize指的是副本大小，readspeed指的是讀取的速度，

當副本被訪問多次之后，信息素會相應的發生變化，信息素相應的屬性值也需要調整，表達式為公式(4)：

τ_i(t+1)＝ρ·τ_i(t)+Δτ_i(t) (4)

信息素揮發系數ρ的設定是否合理會影響蟻群的搜索能力和計算效率，引入動態改變ρ值的方法，使ρ能自適應的改變大小，從而保證算法的綜合性能，現給出的調整策略如公式(5)、如公式(6)：

ρ_a(t)＝1-ln(t)/ln(t+c) (5)

其中c為常數，信息素揮發系數ρ控制在[ρ_min,ρ_max]，并對其取值為[0.2,0.8]，

副本放置的概率公式定義如公式(7)：

其中τ_j(t)指的是副本j在t時刻的信息素的濃度，η_j表示副本本身的固有屬性，α和β分別分別指代副本當前的信息素啟發因子和期望啟發因子，如果α比β的值大，說明在節點選擇中，信息素濃度的作用比副本固有屬性的影響大，取α為3，β為1.5；引入了拉普拉斯概率分布的思想，在副本放置的過程中，先計算出轉移概率最大的對象MaxP，再進行循環遍歷，計算出副本放置對象的概率和最大概率MaxP之間的距離，選取最靠近MaxP的副本進行放置，可得公式(8)：

P(i)＝[MaxP-rand,MaxP+rand],i＝{1,2,...m} (8)

則第i個副本對象將會被選擇放置；

3)蟻群優化副本放置：云存儲系統在受到副本文件RF的請求后，對信息素的副本依次進行放置，包括：

(1)初始化副本信息素，客戶端對系統提出訪問請求，確定分布式文件系統的集群是否可用的；

(2)統計周期T中的各個文件被訪問的次數，根據式(1)計算副本文件RF的訪問頻率和存儲的節點情況；

(3)根據文件的熱度情況設立熱度閾值H_max、H_min，規定增加副本數量的臨界值H_max和減少副本副本數量的臨界值H_min；

(4)確定副本的數量：將計算出的熱度值與H_max、H_min進行比較，若大于H_max，則增加副本數，若小于H_min，則減少副本數，若在[H_min、H_max]區間內則保持副本數量不變；

(5)若副本文件存儲在遠程節點，則依據改進蟻群策略進行副本的放置；

(6)對副本對象進行概率匹配，據選擇的概率根據公式(7)、(8)選出合適的副本；

(7)選擇出副本之后，數據傳往終端，終端在獲取副本之前，使用公式(5)減小副本信息值，降低被重復訪問的概率，平衡節點負載；

(8)若副本在本地進行存儲，則直接讀取本地副本，不必執行蟻群副本放置；

(9)若副本的相關數據沒有被讀取成功，則跳轉到步驟(2)進行下一個副本對象的讀取；

(10)當副本被讀取成功的時候，判斷是不是最后一個副本對象，如果是，則結束副本放置，如果不是，再次讀取下一個副本對象，進行改進蟻群副本放置。