[發明專利]一種基于布谷鳥搜索的storm動態負載均衡方法

有效

• 申請號: 201811636906.7
• 申請日: 2018-12-29
• 公開（公告）號: CN109617826B
• 公開（公告）日: 2022-05-03
• 發明（設計）人: 龍笑;周良;鄭洪源
• 申請（專利權）人: 南京航空航天大學
• 主分類號: H04L47/125
• 分類號: H04L47/125;H04L47/10;H04L67/1008;H04L67/1042
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 王路

1.一種基于布谷鳥搜索的storm動態負載均衡方法，其特征在于，包括如下步驟：

步驟一：獲取集群節點負載信息，包括節點性能向量以及節點上任務的完成率，初始化相關參數，包括宿主鳥巢的數目即需要分配的任務數量，鳥蛋被發現的概率即迭代產生解的淘汰概率，全局最大迭代次數，步長初值，適應度閾值；

步驟二：判斷是否達到迭代停止條件，即達到最大迭代次數Max或適應度閾值大于步驟一中設定的閾值，若達到停止條件則停止迭代，否則繼續；

步驟三：通過節點性能向量和性能權重向量計算集群節點的負載向量，計算節點上任務的分配權重和適應度函數值；

第i個節點的負載向量L_i計算公式如下，

其中，i＝1，2，…，m；j＝1，2，…，n；m為節點個數，n為任務個數；k＝1，2，3，4，表示要監測使用率的資源的編號，分別代表CPU資源、內存、磁盤、網絡帶寬，U為集群節點的性能向量，U＝[u₁，u₂，u₃...u_m]，集群中某個節點的性能向量即U的分向量u_i，有向量表示第i個節點上的第j個任務的性能向量，有表示第i個節點上第j個任務的第k個資源的使用率，包括實時監測到的CPU資源占用率、內存占用率、磁盤I/O占用率，網絡帶寬占用率，α為節點性能向量的權重，α＝[α₁，α₂，α₃，...α_n]，對于權重向量α有α_j∈(0，1)∩∑α_j＝1，即對于節點性能向量權重的每個分向量α_j，有α_j大于0小于1，且所有的α_j之和等于1，α_j的初值為

分配權重W計算公式如下；

其中W_i 為分配權重W＝[W₁，W₂，W₃…，W_m]的分向量，L_i為第i個節點的負載向量，為所有節點負載；

步驟三中適應度函數值計算方法包括如下步驟：

3a)根據任務分配權重W擬分配任務到節點上，并得出理論完成時間來反應t時刻任務j在第i個節點上的完成所需理論時間，任務的理論完成時間的更新公式定義為：

其中，為t′時刻新任務T′在節點i上的理論完成時間，n′表示t′時刻節點i上新的任務數，θ為監測到的任務完成率；為任務初始理論時間，T_t為當前任務時間；

3b)計算適應度函數值：

其中為迭代產生的解，即鳥巢當前位置，m為節點個數，n為任務數；

步驟四：判斷本次迭代適應度函數值是否更優，即函數值更小，若更優則進行下一步，否則保留上次求得的節點性能權重向量；

步驟五：根據當前節點性能權重向量與初始距離的平均值與步長初值的乘積計算布谷鳥搜索算法的步長因子，根據節點性能權重向量更新公式計算新的節點性能權重向量；

步驟六：隨機產生一個數K，0＜K＜1，判斷隨機數K是否大于步驟一中設定的淘汰概率，若大于則隨機更新解，否則保持原解不變；

步驟七：根據迭代最后一輪求得的性能向量的權重的值，計算節點負載向量；

步驟八：根據最新的節點負載計算節點上任務的分配權重，通過選擇函數，根據計算得到的分配權重分配任務。

2.根據權利要求1所述的一種基于布谷鳥搜索的storm動態負載均衡方法，其特征在于，步驟五中步長因子a的計算方法為：

其中，a₀為步長因子的初值，為當前解，為初始解。

3.根據權利要求1所述的一種基于布谷鳥搜索的storm動態負載均衡方法，其特征在于，步驟五中節點性能權重向量更新公式：

其中，a為更改后的步長因子，表示第t次搜索產生的解；表示點乘，Levy(β)為搜索路徑，表示萊維分布產生的隨機向量，其中Levy(β)～u＝t^-β，表示隨機向量Levy(β)服從二項分布。

4.根據權利要求1所述的一種基于布谷鳥搜索的storm動態負載均衡方法，其特征在于，步驟八中分配任務的步驟包括：

8a)計算判斷向量ThrVal以計算選擇函數值，單個節點su的判斷分向量計算方法為：

ThrVal_su＝W_su×ResTol-∑W×His_su

其中，ResTol表示當前積累的總負載請求，His_su表示負載分配歷史向量的一個分量，也就是單個節點su的負載分配歷史，W_su表示單個節點su的任務分配權重，∑W為所有節點任務分配權重向量之和；

8b)根據選擇函數選擇合適的節點δ來處理當前任務：

{δ＝Sel(T，h，W)|ThrVal_δ＝max(ThrVal)}

其中，Sel(T，h，W)為選擇函數，T＝{t₁，t₂，...t_n}表示n個任務集，h為負載分配歷史向量，W為節點任務分配權重向量。