[發明專利]一種基于混合云的可靠應用分配分布式遺傳方法

有效

• 申請號: 201710207785.3
• 申請日: 2017-03-31
• 公開（公告）號: CN107103360B
• 公開（公告）日: 2020-08-18
• 發明（設計）人: 涂成棟;梁亞玲;杜明輝
• 申請（專利權）人: 華南理工大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;H04L29/08
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 羅觀祥

1.一種基于混合云的可靠應用分配分布式遺傳方法，其特征在于，所述方法包括：

S1、構建優化模型，該模型包括云環境模塊和應用程序幾何模塊，過程如下：

S1-1、用一個實體設備集PMs和一個實體鏈路集PLs來構建云環境；

S1-2、將應用程序集合分配到云環境中，每個應用包括一個服務集和一個虛擬鏈路集VLs；

S2、根據混合云環境的特點及應用分配所涉及內容定義約束條件，過程如下：

S2-1、準入控制：每個應用程序分配的副本數最多不超過δ：

|D|＝δ，

其中，δ為某個應用程序的副本數量，D為某個應用程序所有副本組成的集合；

至少有一個對應的副本被分配時，一個應用程序才能被認為成功分配：

其中，a表示某個應用程序；d表示應用程序a的副本d；A為所有應用程序組成的集合，O^a是一個變量，其定義為：如果應用程序a被成功分配則值為1，反之為0；G^d,a是一個變量，其定義為：如果應用程序a的副本d被分配則值為1，反之為0；

S2-2、節點嵌入：只在副本被認為已成功放置時才為其分配節點資源：

其中，s表示某個服務，n表示某個實體設備PM，S為所有的服務組成的集合，N為所有的實體設備PM組成的集合，是一個變量，其定義為：如果節點是應用程序a的副本d對應的服務s所占用的宿主則值為1，反之為0；I_a,s是一個變量，其定義為：如果應用程序a對應的服務s被實例化則值為1，反之為0；

如果一個副本沒有成功放置則不會有實例化的服務：

如果一個服務寄宿在一個節點上，那么CPU資源必須預先分配給該服務：

其中，是一個變量，其定義為：如果實體設備PM運行應用程序a對應的服務s則值為1，反之為0；

對每個服務而言，其最多寄宿在一個節點上：

CPU和內存資源的保護約束：

其中，ω_s為服務s要求的CPU資源，Ω_n為實體設備PM的CPU容量，且

其中，U_s,n是一個變量，其定義為：如果服務s寄宿在實體設備PM上則值為1，反之為0，γ_s為服務s的存儲容量要求，Γ_n為實體設備PM的存儲容量；

一旦一個服務被某個副本使用，此服務必須寄宿在某個節點上：

S2-3、鏈路嵌入：在每個節點上的多網絡流約束可表示為：

其中，是一個變量，其定義為：如果服務s₁與服務s₂之間的虛擬鏈路部署在應用程序a的副本d對應的節點n₁和n₂之間的實體鏈路上則值為1，反之為0，e表示某個實體鏈路PL，E表示所有實體鏈路PL組成的集合；其中，

其中，是一個變量，其定義為：如果服務s₁與服務s₂之間的虛擬鏈路部署在應用程序a的副本d對應的實體鏈路PL上則值為1，反之為0，是一個變量，其定義為：如果至少有一個應用程序a的副本通過部署在其上的服務s₁與服務s₂之間的虛擬鏈路使用實體鏈路PL則值為1，反之為0；

每個鏈路使用的總帶寬不能超過總連接能力：

其中，表示應用程序a所對應的兩個服務s₁，s₂之間的帶寬要求，B_e是實體鏈路PL的帶寬限制；

S2-4、可靠性感知約束：對于一個可用副本，它所使用的每一個單獨組件必須是可用的，當一個組件被任意一個副本的服務或虛擬鏈路使用時即認為這個組件被此副本所使用：

其中，c表示某個實體組件，包括實體設備PM和實體鏈路PL，C為實體組件的集合，即C＝N∪E，是一個變量，其定義為：實體組件c被應用程序a的副本d所使用則值為1，反之為0；

單個組件的狀態描述為：

其中，χ_c表示實體組件c的狀態；

一個組件的失敗概率：

基層網絡狀態描述為：

X＝(χ₁,χ₂,...,χ_|C|)；

S3、定義目標函數，將方法所要解決的問題轉換為最大化分配的應用數量：

實體設備PM所使用的

γ_s為服務s的存儲容量要求，

S4、定義染色體Ω，具體如下：

其中，A₁,A₂,...,A_U描述應用分配的順序，其中A_U表示應用程序集合A中的第U個應用程序；

描述如何給每個應用和每個副本分配服務的順序，其中表示服務集合S中第U個應用程序的副本δ_U所對應的第|S_U|個服務；

被用于選擇一個實體設備PM來運行一個給定應用的給定副本所對應的服務，其中表示實體設備PM集合N中運行第U個應用程序的副本δ_U所對應的第|S_U|個服務的實體設備PM；

S5、構建一個分布式池模型，一個集中池包含所有的遺傳方法中的個體，任務將分布式地選擇一個隨機的個體集來進化成新的一代，在每一代中所有的個體都被存儲在分布池中，每個任務可以檢查結束條件，如有必要，任務可以計算下一代；

S6、譯碼，用一個譯碼方法將染色體轉換成一個解空間的解，過程如下：

S6-1、將應用程序根據染色體的第一部分的值A₁,A₂,...,A_U進行排序，如果要分配一個應用，從第一個副本開始分配，如果這個副本已被分配，檢查其可用性；

S6-2、按照染色體第二部分的值來確定一個給定的應用程序a的給定副本δ所對應的服務的排序；

S7、判斷應用程序放置的數量或迭代次數是否達到規定值，過程如下：

S7-1、若已達到規定值，則跳到S13,方法結束得出對應解集合；

S7-2、若未達到規定值，則執行S8；

S8、計算個體的適應度；

S9、復制，復制過程采用精英策略，即根據約束條件和計算的適應度并按照一定比例選擇一部分優秀個體復制形成下一代的子個體；

S10、選擇交叉，交叉的兩個個體，一個來自精英群體，另一個以隨機方式從全部個體中產生；

S11、變異，變異操作在下一代種群中增加更多的新個體，即按照初始解空間生成相同的分布，以隨機方式來選擇一些個體加入新一代的解空間；

S12、返回步驟S7；

S13、結束，輸出最優解。