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

在審

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

本發明公開了一種基于蟻群算法的云副本放置方案，其特征是，包括如下步驟：1）確定副本放置模型；2）定義蟻群優化算法與副本放置結合；3）蟻群優化副本放置。這種方案能改進蟻群的信息素更新策略和結合拉普拉斯概率分布優化副本放置過程，最終實現副本的數量和位置的調整和優化。

技術領域

本發明針對云計算中的數據調度和訪問效率問題，具體是一種基于蟻群算法的云副本放置方案。

背景技術

隨著互聯網的發展，復雜而龐大的數據需要被處理。據互聯網數據中心的研究報告顯示，未來數據的增長是幾何式的，特別是移動終端。因此，海量數據的及時有效處理就成為了亟待解決的問題。云計算技術的興起，尤其是云存儲技術的出現，使多種類型的存儲設備連接起來進行信息交互，并實現了協同合作。云計算環境由于數據量大和存儲設備和網絡設備差異的原因，會導致數據的丟失和出錯，而副本技術的出現，能夠有效的解決這種問題。通常在存儲系統中采用多個副本，這樣可以保證存儲系統中數據的高可用性和高容錯率。

由于系統性能和節點負載密切相關，云存儲記錄會表現新近數據的局部性特點。如果系統負載不均衡，單個節點的數據存儲負載量會增大，用戶對節點的訪問性能將大大降低。同樣，熱點數據分布不均衡也會影響用戶的讀寫性能。因此，如何在云存儲系統中合理放置副本是一個值得研究的問題。

蟻群算法是意大利學者Dorigo M從自然界中螞蟻覓食行為中發現其覓食路徑會逐漸收斂，最終找到最佳的覓食路徑。根據這一現象，抽象出蟻群算法這一仿生算法。螞蟻在外出四處覓食時，所經過的地方都會留下揮發性物質，學界稱之為螞蟻的“信息素”，螞蟻對路徑中留下的信息素有感知能力，能夠感受到信息素的強弱，并趨向于信息素濃度高的路徑。設想有一食物放在遠處，螞蟻從巢穴去覓食。有不同距離的路徑，但路徑長的信息素也會揮發快。距離食物近的路徑信息素就會高，這樣就會吸引更多的螞蟻前來覓食，這種正反饋機制使距離食物近的路徑的信息素濃度越來越高，螞蟻也逐漸收斂到最佳的路徑中。

根據前面對蟻群算法介紹可得，螞蟻k(k＝1,2,..m)在覓食的過程中，會留下信息素。信息素在路徑上的濃度可以決定螞蟻的數量和行走的方向，而蟻群中最佳路徑上的信息素會越來越濃，螞蟻的活動范圍也會逐漸收斂到一條路徑上，此條路徑便是解決工程問題的解。為了方便表示這一過程，可以把路徑的集合映射到tabu_k(k＝1,2..m)中表示。螞蟻在整個覓食過程中，蟻群的路徑使動態變化的，而集合中的數據也會根據這些變化做出調整。設τ_ij(t)是t時刻從i節點到節點的信息素濃度，則t時刻螞蟻k在(i,j)區間上的概率可表示為

公式α表示啟發因子，β表示期望啟發因子，η_ij表示哈數屬性。在所有螞蟻覓食路徑中，螞蟻數量越多說明此路徑信息素的濃度越高。為了避免信息素隨著時間而揮發，造成整個蟻群的收斂性變差，所以需要對信息素進行必要的更新。用1-ρ表示揮發程度，表示信息素增量。在t+w時刻，信息素的調整公式如下：

τ_ij(t+w)＝(1-ρ)×τ_ij(t)+Δτ_ij(t)

蟻群算法作為一種受自然界蟻群啟發的仿生算法有很多應用領域，最早應用于旅行商問題，并取得了良好的優化效果。最近幾年，學界對蟻群算法也做出了各種各樣的改進，應用領域也延申到了任務調度、數據挖掘、車輛路徑等領域。蟻群算法也會和各種其它的算法進行結合，如遺傳算法、模擬退火算法等。蟻群算法中啟發因子、期望啟發因子、信息素揮發因子等關鍵參數的設定會影響算法的收斂性。

現有技術對云計算中的數據調度和訪問效率方面的研究仍有所欠缺，且在副本管理技術中，作為關鍵問題的副本放置研究相對較少，還需進一步研究。

發明內容