，，

(中國電子科技集團公司 第五十四研究所，石家莊 050081)

0 引言

負載均衡技術是集群工作的關鍵技術，負載均衡算法是影響集群效率的決定性因素， 因此研究并提出一個性能良好的負載均衡調度算法對提高集群工作具有重要意義。

對于軟件負載均衡調度技術，研究學者一般重點解決節(jié)點數(shù)據(jù)傾斜問題以及數(shù)據(jù)分類問題[1-3]，采用改進算法對資源進行分類以實現(xiàn)“合適的資源服務于合適的任務”這一原則[4-5]，通過反饋機制實現(xiàn)負載的實時監(jiān)測以更精確表示節(jié)點負載情況[6-7]。

本論文將節(jié)點負載的研究和資源分配的研究結合起來，通過區(qū)分不同的任務請求，使得同一類型的請求分派到同一類型的服務器節(jié)點上處理，以此實現(xiàn)資源分配最優(yōu)，效率最大化實現(xiàn)，系統(tǒng)也達到更好的均衡效果。

1 分類負載均衡模型

根據(jù)集群任務調度的過程，本文抽象出一種負載均衡模型，即分類負載均衡調度模型(CLBM)。該模型共分為三層：應用層、任務層和資源層。應用層由獲取數(shù)據(jù)模塊構成，包括提交請求和用戶登錄；任務層由請求分類模塊和任務調度模塊構成，請求分類模塊包括接受用戶請求和算法分類，任務調度模塊包括任務指派和任務調度；資源層由資源分類模塊和返回模塊構成，資源分類模塊包括服務器預分類(降維)和模糊關聯(lián)聚類，返回模塊包括服務器處理請求和返回用戶請求。該模型各模塊具體功能如下。

獲取數(shù)據(jù)模塊：該模塊主要功能是統(tǒng)計提交的用戶請求。用戶登錄系統(tǒng)并提交請求，用戶提交的請求就作為下一步分類的數(shù)據(jù)來源。

請求分類模塊：該模塊的主要功能是請求任務的分類。服務器間隔固定的時間統(tǒng)一接收用戶請求，分析任務請求的屬性特征，構建指標體系，根據(jù)請求分類算法對請求分類。

任務調度模塊：該模塊的主要功能是請求任務的調度。將分好類別的任務請求分派到對應類別的任務指派器上，然后順序選擇服務器對任務請求進行任務調度。

資源分類模塊：該模塊主要功能是對服務器進行兩次分類。首先，對服務器功能特性對服務器進行預分類，以減少冗余，降低后續(xù)工作的復雜度；然后根據(jù)服務器特征參數(shù)對其進行模糊關聯(lián)聚類，使得服務器具有清晰的劃分。

返回模塊：該模塊主要功能是處理請求任務。首先屬于某一類別的服務器處理對應類別的任務請求，并將處理結果反饋給用戶。

因此，在該模型下，負載均衡調度的全過程如下：首先登錄系統(tǒng)并提交請求，作為下一步分類的數(shù)據(jù)來源；服務器間隔固定的時間統(tǒng)一接收用戶請求，分析任務請求的屬性特征，構建指標體系，根據(jù)請求分類算法對請求分類；將分好類別的任務請求分派到對應類別的任務指派器上，使得訪問同一類型的請求對應相應類型的服務器，然后順序選擇服務器對任務請求進行任務調度；最后，屬于某一類別的服務器處理對應類別的任務請求，并將處理結果反饋給用戶。分類負載均衡模型如圖1所示。

圖1 分類負載均衡模型

根據(jù)上述分類負載均衡模型各個模塊的主要實現(xiàn)功能，該模型主要實現(xiàn)構建指標體系、對請求分類、對服務器分類三大功能。

構建指標體系：確定任務請求的主要特征屬性，并根據(jù)這些屬性確定任務請求的指標體系，作為下一步對請求分類的數(shù)據(jù)來源與數(shù)據(jù)依據(jù)。

對請求分類：按照由任務請求屬性構建的指標體系，采用某種有效的數(shù)學算法，對請求進行分類。

對服務器分類：按照服務器的特征參數(shù)，對服務器進行分類，并與對請求的分類形成呼應。使得同一類大小的請求負載對應同一類處理能力的服務器。

因此，對分類負載均衡模型建模過程如下：

設Web集群服務器由一個分配器和M個后臺服務器RS1,RS2,...,RSM組成，服務器按照處理負載能力大小分為c類。我們將用戶請求x={x1,x2,...,xn}按照任務量大小劃分為c個不相交的區(qū)間{[s0=0,s1],[s1,s2],...,[sN-1,sC]=∞}，并且讓第i(1≤i≤c)類服務器僅僅服務請求大小落在第i個區(qū)間[si-1,si]的請求，即實現(xiàn)訪問同一類型的請求分配到同一類型的服務器處理的初衷。

2 分類負載均衡模型的實現(xiàn)

2.1 構建指標體系

針對某項目系統(tǒng)，用戶基本操作主要有以下4種：登錄、增刪改查、提交和GPU計算。一般操作對象為視頻和文檔，針對某系統(tǒng)現(xiàn)狀，主要操作對象為文檔。傳統(tǒng)的調度算法只考慮了請求文檔的大小，忽略了文檔的其他屬性。比如請求文檔的緊急程度，文檔的是否涉密等。而實際應用中，忽略這些屬性往往會產(chǎn)生較大的誤差，造成資源分配不合理，請求響應時間增加，不滿足用戶需求。這里我們定義文檔屬性為文檔大小、緊急程度、涉密程度。因此本論文中我們定義4個指標：視頻/文檔、大小、緊急程度和涉密程度。

定義4個指標為請求數(shù)據(jù)的4個屬性，為了便于分析，我們將指標量化數(shù)值表示優(yōu)先級高低，如表1所示。將屬性進行加權求和，請求的任務量大小用每個請求的屬性加權和來表示，根據(jù)量化數(shù)據(jù)的加權和來劃分分類范圍。

表1 數(shù)據(jù)指標的屬性及量化值

2.2 對任務請求分類

任務請求到達的方式有很多種，我們假定是在訪問量穩(wěn)定的情況下。以時間片為單位，將在某時間片內的所有請求進行分類。因此，請求的分類需要高頻隨時進行，需要選用相對簡單復雜度低的算法，且算法運行時間要短，這里我們選擇模糊C均值(FCM)聚類算法。

利用最小支撐樹(MST)算法可以得到請求數(shù)據(jù)的初始聚類中心，算法原理是在數(shù)據(jù)密集區(qū)選擇密度最大數(shù)據(jù)節(jié)點作為第一個類的初始中心，然后在距離第一個初始中心足夠遠的區(qū)域內選擇數(shù)據(jù)密集區(qū)最大的數(shù)據(jù)節(jié)點作為第二個類初始中心，以此類推[8]。

我們對MST算法進行改進，得到改進的最小支撐樹算法(IMST)，該算法降低最小支撐樹算法(MST)的計算復雜度，解決了MST算法初始點選取的冗余問題?，F(xiàn)給出如下兩個定義：

定義一：用加權屬性和之差來定義兩節(jié)點的距離。即:

(1)

其中:dik表示節(jié)點xk到聚類中心vi的距離，m為屬性的個數(shù)，w屬性值大小。

定義二：定義所在節(jié)點的度與分離度之積為該節(jié)點的稀疏度，分離度指兩節(jié)點間的距離。即:

Sk=nk×dik

(2)

其中:Sk為節(jié)點xk相對于聚類中心vi的稀疏度，nk為節(jié)點xk的度，dik為節(jié)點xk到聚類中心vi的距離。

實際計算中，我們無須將所有節(jié)點都作為初始聚類中心的候選點，為減少計算量，我們選擇節(jié)點的度大于平均值的點作為候選點[9]。

這里采用類間最小距離原則：首先選取節(jié)點中度最大的值作為第一個初始聚類中心，然后更新候選點集合，去掉距離第一個聚類初始化中心為0的候選點，計算新候選點集合到第一個初始聚類中心的分離度，選擇分離度最大的點作為第二個初始聚類中心，繼續(xù)更新候選點集合，去掉距離第一、二初始聚類中心為0的候選點，然后從新候選點集合中選取分離度最大的點作為第三個初始聚類中心，如此反復直至候選點集合為空。此時得到準初始聚類中心集合。根據(jù)有效測度指標確定最佳聚類數(shù)，由此確定最終的初始聚類中心點。

算法1:IMST算法

輸入:請求數(shù)據(jù)Data

輸出:初始聚類中心

Step1:利用請求數(shù)據(jù)，以數(shù)據(jù)為節(jié)點，兩節(jié)點間距離作權值，構造最小支撐樹;

Step2:求各請求節(jié)點的度nk及平均度navg，若nk>navg,則xk∈N(N為候選中心集合);

Step3:利用類間最小距離原則:取nmax的節(jié)點作為p01(p0i表示第i個初始聚類中心),然后更新N(為避免重復,去掉d1k=0的節(jié)點),計算更新后N中元素到p01的稀疏度S1,取Smax1對應的節(jié)點作為第二個初始中心p02;

Step4:重復Step3直至N為空集,輸出初始聚類中心;

Step5:算法停止。

針對FCM算法提出了很多有效性指標，使用以下有效性測度指標來確定其聚類個數(shù)，定義如下：

(3)

BP神經(jīng)網(wǎng)絡算法比較實際輸出與理想輸出的差值反向修改神經(jīng)元之間的權值來實現(xiàn)反饋迭代，因此算法具有較強的適應性和學習能力，這彌補了FCM聚類算法因其模糊性造成的適應能力差的缺陷，將BP算法應用于FCM聚類算法可以增加其學習能力并提高準確識別率。在FCM的輸出數(shù)據(jù)中，選取距離最佳聚類中心稀疏程度最小的部分數(shù)據(jù)作為BP算法的訓練輸入數(shù)據(jù)，使網(wǎng)絡具有對輸入請求分類的能力，然后用訓練好的BP神經(jīng)網(wǎng)絡預測請求所屬類別。其算法流程圖如圖2所示。

算法2：模糊神經(jīng)網(wǎng)絡算法(MBFCM算法)

輸入：待分類請求數(shù)據(jù)Data，F(xiàn)CM停止閾值emps，模糊指數(shù)m，BP停止閾值e,BP算法學習速率η。

輸出：最佳聚類數(shù)c，正確識別率h。

Step1：輸入待分類請求數(shù)據(jù)Data，根據(jù)MSTZ算法求得初始聚類中心集合；

Step2：根據(jù)有效性測度確定初始分類中心v0和最佳分類個數(shù)c；

Step3：運行從指定中心開始的模糊C均值(MFCM)聚類算法，得到最佳聚類中心v；

Step4：計算個體到聚類中心的分離度并選擇稀疏度程度最小的部分數(shù)據(jù)進行網(wǎng)絡訓練；

Step5：網(wǎng)絡預測與結果統(tǒng)計，得到正確識別率h。

圖2 MBFCM算法流程圖

2.3 對服務器分類

根據(jù)服務器結構描述，現(xiàn)對服務器進行兩次分類。首先對服務器進行預聚類(功能分類)，從而避免因服務器屬性過于復雜導致算法計算復雜度過高，并且有效提高任務調度的精準性；緊接著運用模糊關聯(lián)聚類算法對服務器進行性能分類，然后F統(tǒng)計量確定服務器分類個數(shù)，并用編網(wǎng)法獲取最佳聚類劃分。使同一類別的請求分派到后臺對應類別的服務器上處理，避免小任務排在大任務后面受到巨大的響應延時。

因服務器特征參數(shù)復雜繁瑣，且變化幅度較大，其分類個數(shù)用F統(tǒng)計量來獲取。F統(tǒng)計量根據(jù)樣本空間中數(shù)據(jù)的特征來劃分類別，通過類間距離和類內距離比值量化分類效果的好壞，顯然，類與類之間的距離越大，類內樣本數(shù)據(jù)之間的距離越小，同一類別的數(shù)據(jù)分布越稠密，不同類別的數(shù)據(jù)越分散，分類效果就越好[10]。

F統(tǒng)計量公式如下:

(4)

基于模糊等價關系的聚類算法基本原理是：首先對請求數(shù)據(jù)構建數(shù)據(jù)矩陣并利用某種方法對數(shù)據(jù)矩陣建立模糊相似矩陣，然后對模糊相似矩陣作水平截集，通過改變截距的大小獲得不同精度的聚類劃分。

3 云仿真調度模型驗證與結果分析

CloudSim是一款可以模擬實際仿真調度的工具，本章將使用CloudSim工具對分類負載均衡模型做實驗驗證。開發(fā)人員通過擴展或者修改CloudSim中的基礎類，來優(yōu)化或者實現(xiàn)不同的調度算法，比如順序分配策略和貪心策略，將算法原理加入DataCenterBroker類中，然后調度分配算法，實現(xiàn)算法仿真。

用CloudSim模擬用戶數(shù)量為3，服務器數(shù)量為5的集群調度過程，如圖3所示，用戶列表為User1，User2，User3；虛擬機列表為Vm0,Vm1,Vm2,Vm3,Vm4;請求的任務列表為Task1，Task2,…Taskn；實際模擬過程中，數(shù)據(jù)中心并不直接參與調度，而是由數(shù)據(jù)代理管理和調度任務列表中的請求任務，分發(fā)給虛擬機處理，完成數(shù)據(jù)中心和虛擬機之間的交互。本文的仿真環(huán)境設置和實驗參數(shù)設置表1所示。

圖3 CloudSim模擬集群調度過程

在相同實驗環(huán)境及實驗參數(shù)下分別運行順序選擇策略、貪心策略和分類負載均衡策略，比較3種調度策略的性能優(yōu)劣。

在DataCenterBroker類中加入本文算法：

表1 實驗軟硬件仿真環(huán)境

broker.bindCloudletsToVmsMBFCM-CLBM;//分類負載均衡調度算法

通過逐步增加任務請求個數(shù)來驗證分類負載均衡調度策略的有效性。現(xiàn)設計3種場景對3種算法進行仿真調度實驗，對比其最大運行時間和資源利用率的變化情況。

1)針對高負載任務的實驗仿真，任務的指令長度遠大于服務器的處理速度。

對于場景(1),針對只有高負載任務的請求場景，如圖4～5所示，順序策略的最大運行時間最長，貪心策略和CLBM策略的最大運行時間相接近；順序選擇策略的資源利用率最低，在任務量較小時，貪心策略的資源利用率要高于CLBM策略，隨著任務量的增加，兩者資源利用率逐漸接近。因此，針對高負載任務場景，CLBM策略的性能和貪心策略的性能基本接近，且遠大于順序選擇策略的性能。

圖5 資源利用率隨請求個數(shù)變化圖

圖4 最大運行時間隨請求個數(shù)變化圖

2)針對低負載任務，服務器在單位時間內就可以處理完成，任務的指令長度小于服務器單位時間處理速度。

對于場景(2)，針對低負載的任務請求場景，如圖6～7所示，順序策略的最大運行時間大于貪心策略最大運行時間，貪心策略最大運行時間稍高于CLBM策略的最大運行時間；順序選擇策略的資源利用率最低，隨著任務量增加，CLBM策略的資源利用率遠大于貪心策略的資源利用率。說明，針對低負載的請求場景，CLBM策略的性能高于貪心策略的性能。

圖6 最大運行時間隨請求個數(shù)變化圖

圖7 資源利用率隨請求個數(shù)變化圖

3)針對高負載任務和低負載任務混合調度，其中，高負載任務請求個數(shù)：低負載任務請求個數(shù)=1：1 。

對于場景(3)，針對既有高負載又有低負載的請求場景，根據(jù)圖8～9所示，隨著任務量的增加，順序選擇策略的最大運行時間遠大于其他兩種策略，貪心策略的最大運行時間稍比CLBM策略的最大運行時間稍高；順序選擇策略的資源利用率最低，CLBM策略的資源利用率高于貪心策略的資源利用率，說明CLBM策略的調度性能高于貪心策略的調度性能。

圖9 資源利用率隨請求個數(shù)變化圖

觀察并分析上述實驗結果：順序分配策略不考慮任務的大小以及虛擬機的處理能力，僅僅以每個虛擬機上運行任務數(shù)量作為衡量標準，為實現(xiàn)負載均衡，盡量滿足每個虛擬機上運行任務數(shù)量相同，原理簡單，易于實現(xiàn)，但實際上不同的任務請求具有不同的負載大小，并且服務器的處理能力也不盡相同，因此順序選擇策略的調度性能很差。

相比于順序選擇策略，貪心策略加入任務的指令長度(MI)和虛擬機的執(zhí)行速度(MIPS)這兩個性能參數(shù)，將某任務在某虛擬機上的執(zhí)行時間(T)定義為指令長度與執(zhí)行速度的比值，即T=MI/MIPS[11]，該算法思想為指令長度越大的任務需要執(zhí)行速度越快的虛擬機處理，其目的是令所有任務的完成時間接近最短。

但是貪心策略僅僅以所有任務的完成時間作為衡量標準，沒有考慮資源的使用情況。本文提出的分類負載均衡策略同時考慮執(zhí)行時間和資源使用情況兩大性能，即將任務的完成時間和資源利用率作為衡量調度性能的標準，客觀全面地反映調度的性能，算法的最大運行時間最短，資源利用率最高，最高可達99%。

綜上以上分析，理論和實驗皆證明本文提出的分類負載均衡調度算法適用性更強，性能更好。

4 結束語

本文基于模糊聚類算法，提出一種分類負載均衡調度模型，分別對用戶請求和后臺服務器分類。用改進的最小支撐樹算法獲取初始中心，F(xiàn)測度確定最佳聚類數(shù)，通過BP神經(jīng)網(wǎng)絡算法提高FCM算法的學習能力，預聚類以及模糊關聯(lián)聚類算法對資源有效分類。最后CloudSim下的仿真環(huán)境模擬，在3種場景下對比傳統(tǒng)算法和本文算法，具有更強的適應性和更好的調度性能。實驗表明該模型在作業(yè)調度和資源分配上有實際的指導意義。

[1] 李明陽，嚴 華. 改進粒子群算法在云計算負載均衡中的應用研究[J]. 計算機測量與控制, 2016,24(10)：219-221.

[2] I Konstantinou，D Tsoumakos, N Koziris. Fast and cost-effective online load balancing in diatributed range-queriable systems[J]. IEEE Transactions on Parallel and Distributed Syst. 2011,22(8):1350-1364.

[3] Wang X J,Wang Y,Hao Z,et al.The Research on Resource Scheduling Based on Fuzzy Clustering in Cloud Computing[A]. ICICTA 2015:2015 8th International Conference on Intelligent Computation Technology and Automation[C].2015:1025-1028.

[4] 曹鴻強，盧錫城. 多機服務器任務調度的經(jīng)濟學方法[J]. 計算機工程與科學，2001,23(2):4-9.

[5] 李春鴿，劉欣然, 張哲宇,等. 虛擬計算環(huán)境下一種基于模糊聚類的資源匹配模型[C].VARA 2013:The sixth Session of Information Security Vulnerability Analysis and Risk Assessment,2013:365-378.

[6] Wang Y,Wang J K,Wang G R,et al.Utility optimization strategy of resoutce scheduling in cloud computing[A].CCC 2016:Control Conference[C].2016 35th Chinese:5235-5238.

[7] 劉 健，徐 磊，張維明. 基于動態(tài)反饋的負載均衡算法[J]. 計算機工程與科學. 2003,25(5):65-68.

[8] 李春生．模糊聚類的組合方法及其應用研究[D].長春：吉林大學，2010, 8.

[9] 李榮榮，孫紀敏. A Fuzzy Clustering Algorithm Based on Complex Synaptic Neural Network[A].2017 17th IEEE International Conference on Communication Technology(ICCT 2017)[C].China, 2017,1291-1295.

[10] 曲福恒，崔廣才，李巖芳,等．模糊聚類算法及應用[M]．北京：國防工業(yè)出版社，2011．

[11] 劉 鵬．云計算(第二版)[M]．北京：電子工業(yè)出版社,2012．