[發(fā)明專利]一種基于遺傳算法的服務(wù)器負載均衡方法

有效

• 申請?zhí)枺?/td>: 201610280719.4
• 申請日: 2016-04-29
• 公開（公告）號: CN105704255B
• 公開（公告）日: 2019-01-08
• 發(fā)明（設(shè)計）人: 包曉安;魏雪;張娜;吳彪;熊子健
• 申請（專利權(quán)）人: 浙江理工大學(xué)
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 鄭海峰

1.一種基于遺傳算法的服務(wù)器負載均衡方法，其特征在于包括如下步驟：

1)采用二維十進制對空間的候選解進行編碼，隨機產(chǎn)生初始種群；

2)通過Mean-Variance模型計算資源利用率和執(zhí)行時間，從而得到組合適應(yīng)度函數(shù)對種群中的個體進行評估檢測；具體包括如下步驟：

S01負載指數(shù)的衡量

通過服務(wù)器運行時的參數(shù)得到負載指數(shù)，所述的參數(shù)包括CPU占用率，內(nèi)存及帶寬利用率；

其中每個服務(wù)器的內(nèi)存利用率定義為：

式中：V_mi為服務(wù)器i的已用內(nèi)存，P_mi為服務(wù)器i的總內(nèi)存；

CPU占用率的定義為：

式中：V_ci為服務(wù)器i已被占用的CPU，P_ci是服務(wù)器i的總CPU；

帶寬利用率的定義為：

式中：V_bi為服務(wù)器i已被占用的帶寬，P_bi則是服務(wù)器i的總帶寬；

S02服務(wù)器i的資源利用率為：

R_ui＝k₁M_ui+k₂C_ui+k₃B_ui

式中：k₁，k₂，k₃為常數(shù)，且k₁+k₂+k₃＝1；

S03用Mean-Variance模型計算資源利用率及執(zhí)行時間

假設(shè)對m個服務(wù)器進行資源利用率的配置，對應(yīng)的資源利用率為隨機變量R_ui，總的資源利用率為：

其中w_i代表m個服務(wù)器中資源利用率的權(quán)值向量，i＝1，2，...，m，期望u_p和負載均衡時間σ²_p分別為：

其中，u_i是服務(wù)器i資源利用率的期望，而cov(R_ui，R_uj)表示任意兩個服務(wù)器資源利用率R_ui，R_uj的協(xié)方差又寫作σ_ij，

Mean-Variance模型通過求解約束優(yōu)化問題來獲得最優(yōu)的權(quán)重向量，最小執(zhí)行時間makespan為：

約束條件：

在限制條件下求解R_ui資源利用率組合時的最小執(zhí)行時間，關(guān)于最值問題通過拉格朗日目標(biāo)函數(shù)求得，構(gòu)建拉格朗日式如下：

其中λ₁和λ₂是拉格朗日乘數(shù)，通過計算L相對于w_i和拉格朗日乘數(shù)的導(dǎo)數(shù)為0的等式來獲得最優(yōu)的權(quán)重向量，即分別對w_i，λ₁，λ₂求偏導(dǎo)：

S04由最優(yōu)的權(quán)重向量可得到總的資源利用率及執(zhí)行時間，組合適應(yīng)度函數(shù)：

適應(yīng)度函數(shù)用來評價負載調(diào)度任務(wù)的質(zhì)量，響應(yīng)時間越少，資源利用率越高時，適應(yīng)度值越高，表示負載均衡策略越好；

3)當(dāng)最優(yōu)字符串的適應(yīng)度穩(wěn)定時或迭代達到預(yù)設(shè)的次數(shù)時，算法終止并輸出最優(yōu)適應(yīng)度字符串；否則執(zhí)行步驟4)；

4)按輪盤賭選擇方法對適應(yīng)性強的字符串進行選擇，選擇的字符串進行循環(huán)交叉及變異運算；得到新的種群，并返回步驟2)。

2.根據(jù)權(quán)利要求1所述的一種基于遺傳算法的服務(wù)器負載均衡方法，其特征在于所述的步驟1)具體包括如下步驟：

S01：采用二維十進制對空間的候選解進行編碼，每個解被編碼為一個由兩個屬性表示的十進制數(shù)組，即作<T_i，P_j>，其中T_i，P_j分別表示任務(wù)i和被分配的服務(wù)器j，

S02：編碼后的數(shù)組采用隨機函數(shù)產(chǎn)生N個初始串結(jié)構(gòu)數(shù)據(jù)，每個串結(jié)構(gòu)數(shù)據(jù)稱為一個字符串，N個字符串構(gòu)成了一個群體，將隨機產(chǎn)生的N個初始串結(jié)構(gòu)數(shù)據(jù)作為初始種群。