基于IFTS 的網(wǎng)絡(luò)動態(tài)負(fù)載均衡方法*

任神河，鄭寇全，關(guān)冬冬，惠軍華

（1.咸陽師范學(xué)院，陜西 咸陽 712000；2.國防科技大學(xué)信息通信學(xué)院，西安 710106；3.空軍西安飛行學(xué)院，西安 710306）

0 引言

隨著計算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，異構(gòu)網(wǎng)絡(luò)服務(wù)平臺高度融合，網(wǎng)絡(luò)數(shù)據(jù)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)服務(wù)請求呈幾何級數(shù)增長，網(wǎng)絡(luò)負(fù)載不均衡問題日益突出，網(wǎng)絡(luò)資源的合理調(diào)配已成為亟待研究解決的重點問題［1］。動態(tài)負(fù)載均衡（Dynamic Load Balancing，DLB）能夠通過分析網(wǎng)絡(luò)節(jié)點實時負(fù)載信息和系統(tǒng)響應(yīng)情況，合理規(guī)劃節(jié)點任務(wù)部署，動態(tài)消除負(fù)載分布的不平衡性，是影響網(wǎng)絡(luò)整體承載性能的關(guān)鍵因素，而實時準(zhǔn)確的負(fù)載預(yù)測是獲得高效DLB的前提和基礎(chǔ)［2-3］。由于能夠通過預(yù)測掌握網(wǎng)絡(luò)未來運(yùn)行狀態(tài)，并有針對性地采取負(fù)載均衡策略，加快重載節(jié)點任務(wù)遷移，使得網(wǎng)絡(luò)在有計劃、可調(diào)控的狀態(tài)下穩(wěn)定運(yùn)行，基于預(yù)測的網(wǎng)絡(luò)DLB 理論一經(jīng)提出，就引起了廣泛的關(guān)注，并迅速發(fā)展成為一個重要而又熱門的課題，取得了一系列研究成果。文獻(xiàn)［4］針對負(fù)載隨機(jī)突變特性，提出了基于反傳網(wǎng)絡(luò)和動態(tài)滑動窗口機(jī)制的負(fù)載預(yù)測方法，并設(shè)計了基于神經(jīng)網(wǎng)絡(luò)的負(fù)載預(yù)測器；文獻(xiàn)［5］提出了基于多重標(biāo)準(zhǔn)的目標(biāo)節(jié)點選擇與負(fù)載預(yù)測的策略，但其需要維護(hù)額外的測試數(shù)據(jù)，易導(dǎo)致系統(tǒng)負(fù)載冗余；文獻(xiàn)［6］利用自適應(yīng)算法進(jìn)行節(jié)點負(fù)載預(yù)測，較好地解決了負(fù)載冗余的問題；文獻(xiàn)［7］依據(jù)不同網(wǎng)絡(luò)資源間的相關(guān)性，給出了異構(gòu)網(wǎng)絡(luò)負(fù)載復(fù)合預(yù)測算法，提升了復(fù)雜性網(wǎng)絡(luò)系統(tǒng)的負(fù)載均衡性能；文獻(xiàn)［8］將基于預(yù)測的負(fù)載均衡理論引入云計算領(lǐng)域，提出了基于預(yù)測的虛擬機(jī)節(jié)點資源調(diào)度算法，拓展了基于預(yù)測的DLB 方法的實際應(yīng)用范圍。然而，隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的日趨復(fù)雜，網(wǎng)絡(luò)負(fù)載變化呈現(xiàn)出了時變的、非平穩(wěn)的和隨機(jī)的新特性，模糊不確定性非常明顯，傳統(tǒng)的負(fù)載預(yù)測方法將網(wǎng)絡(luò)負(fù)載看作平穩(wěn)時間序列，采用線性模型進(jìn)行預(yù)測，對負(fù)載變化趨勢的擬合度不高，且預(yù)測的實時性較差，難以有效滿足負(fù)載均衡調(diào)度程序?qū)ω?fù)載預(yù)測精度的實際需求。可見，基于預(yù)測的DLB 理論的拓展研究已刻不容緩。

直覺模糊時間序列［9-11］（Intuitionistic Fuzzy Time Series，IFTS）作為模糊時序預(yù)測理論的重要擴(kuò)充和發(fā)展，其序列變量的數(shù)學(xué)描述更加符合客觀世界的模糊本質(zhì)，且具有良好的理論延展性，為求解不確定性網(wǎng)絡(luò)負(fù)載時序預(yù)測問題提供了新的思路和方法。因此，本文在分析網(wǎng)絡(luò)負(fù)載模糊時序變化特性的基礎(chǔ)上，構(gòu)建了網(wǎng)絡(luò)負(fù)載IFTS 預(yù)測模型，提出了基于IFTS 的網(wǎng)絡(luò)DLB 算法，解決了網(wǎng)絡(luò)負(fù)載預(yù)測中隨機(jī)不確定性影響大的問題，減緩了系統(tǒng)工作負(fù)擔(dān)，并通過加入實時校正模塊，克服了IFTS 預(yù)測的不平穩(wěn)波動問題，提升了網(wǎng)絡(luò)資源利用率，從根本上增強(qiáng)了網(wǎng)絡(luò)動態(tài)負(fù)載均衡系統(tǒng)的整體性能。

1 基于IFTS 的網(wǎng)絡(luò)負(fù)載預(yù)測方法

1.1 基礎(chǔ)知識

定義2 假設(shè)F（t）為論域U 上的IFTS，若F（t）僅由F（t-1）確定，或者僅由F（t-2）…或者僅由F（t-m）（m＞0）確定，則一階一元IFTS 預(yù)測關(guān)系可表示為：

若F（t）由F（t-1），F(xiàn)（t-2），…，F(xiàn)（t-m）（m＞0）確定，則高階一元IFTS 預(yù)測關(guān)系為：

則稱F（t）為高（k）階多（m）元IFTS。

其中，πA（xi），πB（xi）為集合A、B 的猶豫度參數(shù)。

1.2 網(wǎng)絡(luò)負(fù)載模糊時序特性分析

為精確預(yù)測網(wǎng)絡(luò)負(fù)載信息，必須分析了解節(jié)點負(fù)載的時序變化規(guī)律。如下頁圖1 所示，美國學(xué)者［8］通過對各類型網(wǎng)絡(luò)節(jié)點負(fù)載信息的跟蹤分析，發(fā)現(xiàn)網(wǎng)絡(luò)負(fù)載變化具有以下特性（圖中縱橫軸分別表示網(wǎng)絡(luò)節(jié)點類型和時段內(nèi)平均負(fù)載量值）：

1）負(fù)載分布是一種隨機(jī)過程，具有明顯的時變性、非線性和高度不確定性，是符合模糊時序分布的信號序列；

圖1 網(wǎng)絡(luò)節(jié)點負(fù)載分布圖

2）負(fù)載變化具有很強(qiáng)的時序關(guān)聯(lián)性，這表明網(wǎng)絡(luò)負(fù)載預(yù)測是可行的，且利用時序理論進(jìn)行負(fù)載預(yù)測是合適的；

3）負(fù)載變化受多因素影響，呈現(xiàn)出多樣化分布特性，且具有很強(qiáng)的主元、次元因果關(guān)系，符合多元時序預(yù)測規(guī)律，可利用高階多元時間序列進(jìn)行預(yù)測；

4）負(fù)載變化雖具有突變不可預(yù)測性，但在時間尺度下又具有高度的自相似性和長相關(guān)性，這表明負(fù)載預(yù)測模型需具備預(yù)測時間長度的修正和重適應(yīng)機(jī)制，而高階IFTS 預(yù)測模型的自適應(yīng)階數(shù)調(diào)節(jié)策略就可有效解決這一問題。

綜上所述，網(wǎng)絡(luò)負(fù)載變化的模糊不確定性非常明顯，利用高階多元時變性IFTS 預(yù)測理論進(jìn)行的網(wǎng)絡(luò)節(jié)點預(yù)測是完全可行的。

1.3 基于IFTS 的網(wǎng)絡(luò)負(fù)載預(yù)測模型

IFTS 預(yù)測理論是通過直覺模糊函數(shù)描述序列數(shù)據(jù)的模糊時序變化趨勢，在歷史數(shù)據(jù)不完備或不精確的條件下，利用直覺模糊邏輯推理進(jìn)行不確定性預(yù)測，掌握序列未來值的分布規(guī)律［10］。如圖2 所示，本文針對網(wǎng)絡(luò)負(fù)載的模糊分布特性，構(gòu)建基于IFTS 的網(wǎng)絡(luò)負(fù)載預(yù)測模型，設(shè)計模型預(yù)測實時校正機(jī)制，以期提升系統(tǒng)預(yù)測效率，獲取高精度的負(fù)載預(yù)測結(jié)果，其算法步驟可描述為：

圖2 網(wǎng)絡(luò)負(fù)載IFTS 預(yù)測模型

算法1 網(wǎng)絡(luò)負(fù)載IFTS 預(yù)測算法

2 基于IFTS 預(yù)測的網(wǎng)絡(luò)動態(tài)負(fù)載均衡方法

2.1 基于IFTS 的網(wǎng)絡(luò)動態(tài)負(fù)載均衡模型

基于預(yù)測的DLB 方法大多是通過分析負(fù)載序列的時序關(guān)聯(lián)特性，利用智能算法進(jìn)行節(jié)點負(fù)載狀態(tài)預(yù)測，并預(yù)先采取負(fù)載均衡策略，增強(qiáng)系統(tǒng)的負(fù)載均衡效能。然而，負(fù)載預(yù)測依賴大量的歷史數(shù)據(jù)，而網(wǎng)絡(luò)負(fù)載數(shù)據(jù)往往是模糊的、不確定的和時變的，這就限制了經(jīng)典預(yù)測理論在網(wǎng)絡(luò)負(fù)載預(yù)測中的應(yīng)用。因此，如圖3 所示，本文利用IFTS 對復(fù)雜不確定性時序數(shù)據(jù)的處理優(yōu)勢，基于IFTS 實時預(yù)測進(jìn)行網(wǎng)絡(luò)節(jié)點負(fù)載分配和任務(wù)調(diào)度，并動態(tài)監(jiān)測網(wǎng)絡(luò)運(yùn)行狀態(tài)和節(jié)點資源利用率，優(yōu)化修正預(yù)測模型參數(shù)，確保負(fù)載預(yù)測的準(zhǔn)確性和負(fù)載均衡系統(tǒng)運(yùn)行的可靠性。下面，重點就負(fù)載均衡模型涉及的幾個關(guān)鍵算法分別進(jìn)行描述。

圖3 網(wǎng)絡(luò)負(fù)載動態(tài)均衡模型

2.2 基于IFTS 預(yù)測的負(fù)載調(diào)度算法

網(wǎng)絡(luò)負(fù)載調(diào)度的重點是如何將任務(wù)請求合理地分配給各服務(wù)器節(jié)點，確保網(wǎng)絡(luò)高效穩(wěn)定運(yùn)行。本文提出的基于IFTS 預(yù)測的負(fù)載調(diào)度方法主要包括負(fù)載量化、分配和負(fù)載遷移兩個部分。負(fù)載量化、分配是在網(wǎng)絡(luò)任務(wù)請求初始階段，利用自適應(yīng)比例分配的方法進(jìn)行節(jié)點負(fù)載初分配；負(fù)載遷移是根據(jù)節(jié)點運(yùn)行狀態(tài)，基于節(jié)點負(fù)載預(yù)測值和觀察值間的關(guān)聯(lián)關(guān)系，進(jìn)行節(jié)點負(fù)載遷移，從而減少任務(wù)請求在節(jié)點間重復(fù)遷移卻無法執(zhí)行的現(xiàn)象。其算法可描述為：

算法2 基于IFTS 的負(fù)載量化、分配算法

Step1：算法初始化。設(shè)定序列抽樣周期T=2ω，其中ω 為節(jié)點通信往返時間；確定節(jié)點負(fù)載平均承載值Limax，i 為網(wǎng)絡(luò)節(jié)點序號；抽取負(fù)載序列數(shù)據(jù)樣本。

算法3 基于IFTS 的負(fù)載遷移算法

Step1：設(shè)定網(wǎng)絡(luò)節(jié)點平均承載雙閾值Lmin、Lmax；

1）共享發(fā)布網(wǎng)絡(luò)節(jié)點空閑狀態(tài)，包括節(jié)點地址Ri、可承受負(fù)載遷移量Ji；

2）協(xié)同負(fù)載調(diào)度模塊停止節(jié)點負(fù)載預(yù)測，并同步更新節(jié)點狀態(tài)為等待遷入；

3）接收負(fù)載遷移請求，包括節(jié)點地址Sj、負(fù)載遷移量Jj以及交互通信量Cij，計算映射節(jié)點間的通信時間Tij；

5）若節(jié)點狀態(tài)變更為任務(wù)工作節(jié)點，則共享發(fā)布節(jié)點承載狀態(tài)；否則，依據(jù)Ek排序接收負(fù)載遷移指令。若節(jié)點狀態(tài)始終空閑，則等待周期T 后返回Step2。

Step4：進(jìn)行網(wǎng)絡(luò)負(fù)載遷移調(diào)度。

1）接收共享網(wǎng)絡(luò)范圍內(nèi)節(jié)點狀態(tài)，若由空閑節(jié)點，跳至3），否則，等待負(fù)載遷移請求；

2）收到負(fù)載遷移任務(wù)，記錄并映射生成可承載節(jié)點列表；

3）向列表節(jié)點共享負(fù)載遷移任務(wù)，包括節(jié)點地址Sj、任務(wù)量Jj以及交互通信量Cij；

4）若收到列表節(jié)點更新指令，則刪除相應(yīng)節(jié)點信息；否則，在可承載量滿足的條件下，選取Cij值最小的節(jié)點建立映射關(guān)系，進(jìn)行任務(wù)遷移并同步更新節(jié)點狀態(tài)，而后跳至Step2。

Step5：默認(rèn)網(wǎng)絡(luò)節(jié)點負(fù)載適中，轉(zhuǎn)至Step2。

由此可見，本文構(gòu)建的網(wǎng)絡(luò)負(fù)載調(diào)度機(jī)制是一個基于預(yù)測的節(jié)點負(fù)載狀態(tài)循環(huán)判斷的DLB 過程，是根據(jù)負(fù)載預(yù)測啟動相應(yīng)操作，任務(wù)遷移按照最優(yōu)化原則選擇空載節(jié)點，而不是在相鄰節(jié)點間逐一傳遞，且節(jié)點間的信息交換是由空載節(jié)點驅(qū)動，這就降低了節(jié)點信息交互的頻度和代價，提升了負(fù)載遷移效率和精度。

2.3 基于IFTS 的網(wǎng)絡(luò)動態(tài)負(fù)載均衡方法

與其他基于預(yù)測的網(wǎng)絡(luò)負(fù)載均衡策略相比，本文提出的DLB 算法是從負(fù)載數(shù)據(jù)變化的模糊不確定性入手，利用IFTS 描述和處理負(fù)載序列變量，基于可變階多元自適應(yīng)直覺模糊邏輯推理進(jìn)行負(fù)載預(yù)測，根據(jù)節(jié)點自適應(yīng)比例分配進(jìn)行負(fù)載初平衡處理，利用主動型空閑節(jié)點驅(qū)動策略進(jìn)行動態(tài)地基于預(yù)測的網(wǎng)絡(luò)負(fù)載均衡操作，從而提升系統(tǒng)運(yùn)行效率，減少節(jié)點資源浪費，增強(qiáng)負(fù)載均衡系統(tǒng)自適應(yīng)特征。算法的具體步驟可描述為：

算法4 基于IFTS 的網(wǎng)絡(luò)負(fù)載動態(tài)均衡算法

Step1：按照抽樣周期，抽取t-1 時刻網(wǎng)絡(luò)節(jié)點負(fù)載序列數(shù)據(jù)集；

Step2：利用算法1 預(yù)測t 時刻網(wǎng)絡(luò)節(jié)點負(fù)載；Step3：利用算法2 進(jìn)行基于預(yù)測的節(jié)點負(fù)載量化和初始分配，并實時判定網(wǎng)絡(luò)負(fù)載均衡狀況；

Step4：利用算法3 進(jìn)行網(wǎng)絡(luò)負(fù)載動態(tài)均衡，并實時分析網(wǎng)絡(luò)運(yùn)行狀態(tài)。若系統(tǒng)運(yùn)行平穩(wěn)則轉(zhuǎn)至Step5；否則，優(yōu)化調(diào)整模型參數(shù)，返回Step2；

Step5：算法結(jié)束。

3 實例分析

為了驗證文中算法的有效性，選取文獻(xiàn)［7］仿真實驗數(shù)據(jù)作為負(fù)載序列歷史數(shù)據(jù)，設(shè)定網(wǎng)絡(luò)節(jié)點數(shù)n=4，觀測時間間隔δ=0.5 s，抽樣周期T=100 s，測試時刻數(shù)N=50。

首先，選取網(wǎng)絡(luò)節(jié)點1 的負(fù)載序列數(shù)據(jù)，利用算法1 進(jìn)行負(fù)載預(yù)測，計算預(yù)測相對誤差，并將其與其他常用算法進(jìn)行比較，結(jié)果分別如圖4、圖5 所示。

由圖可知，在模型預(yù)測初期，本文算法的負(fù)載預(yù)測精度有較大波動，但隨著時間的推移，算法表現(xiàn)出了良好的預(yù)測性能，負(fù)載預(yù)測精度和效率都得到較大的提升，尤其是加入實時校正機(jī)制后，預(yù)測誤差有了明顯的改善，且預(yù)測系統(tǒng)保持了穩(wěn)定良好的運(yùn)行狀態(tài)。當(dāng)然，本文算法需經(jīng)過循環(huán)測試進(jìn)行參數(shù)優(yōu)化調(diào)整，算法復(fù)雜度相對較高，但與系統(tǒng)預(yù)測性能的提升相比，其可忽略不計。

圖4 網(wǎng)絡(luò)節(jié)點負(fù)載預(yù)測圖

圖5 負(fù)載預(yù)測誤差對比圖

其次，利用文中算法進(jìn)行網(wǎng)絡(luò)動態(tài)負(fù)載均衡操作，并與文獻(xiàn)［12］描述的負(fù)載均衡方法進(jìn)行比較，結(jié)果如圖6、圖7 所示。

圖6 文獻(xiàn)［12］算法網(wǎng)絡(luò)負(fù)載均衡狀態(tài)圖

圖7 本文算法網(wǎng)絡(luò)負(fù)載均衡狀態(tài)圖

由圖可知，本文利用IFTS 進(jìn)行網(wǎng)絡(luò)節(jié)點負(fù)載預(yù)測，并結(jié)合節(jié)點承載量值進(jìn)行負(fù)載量化和預(yù)分配處理，可充分發(fā)揮網(wǎng)絡(luò)節(jié)點計算能力，使得初始負(fù)載分布達(dá)到了較好的均衡狀態(tài)；采用主動型空閑節(jié)點驅(qū)動策略進(jìn)行負(fù)載動態(tài)調(diào)度，加快了網(wǎng)絡(luò)重載節(jié)點的任務(wù)遷移速度，克服了傳統(tǒng)算法周期性節(jié)點探詢和遷移抖動的缺陷，獲取較好的系統(tǒng)整體資源利用率，提高了網(wǎng)絡(luò)負(fù)載動態(tài)均衡系統(tǒng)的運(yùn)行效率。

最后，采用負(fù)載均衡系列研究系列文獻(xiàn)中常用的求質(zhì)數(shù)算例，比較不同數(shù)據(jù)規(guī)模下網(wǎng)絡(luò)DLB 算法的執(zhí)行效率，結(jié)果如圖8、圖9 所示。

圖8 不同節(jié)點負(fù)載下的執(zhí)行時間圖

圖9 不同數(shù)據(jù)規(guī)模下的執(zhí)行時間圖

可見，網(wǎng)絡(luò)節(jié)點空載狀態(tài)下，幾類算法的執(zhí)行效率基本相當(dāng)，但當(dāng)網(wǎng)絡(luò)節(jié)點額外負(fù)載數(shù)目和數(shù)據(jù)規(guī)模不斷擴(kuò)大時，本文算法表現(xiàn)出了較大的優(yōu)越性，獲得了更為滿意的網(wǎng)絡(luò)負(fù)載均衡效果。因此，面對日益復(fù)雜的集群異構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)，本文算法具有更為廣闊的應(yīng)用前景。

4 結(jié)論

負(fù)載均衡是影響網(wǎng)絡(luò)整體性能的關(guān)鍵因素，本文在分析網(wǎng)絡(luò)負(fù)載模糊變化特性的基礎(chǔ)上，構(gòu)建了網(wǎng)絡(luò)負(fù)載IFTS 預(yù)測模型，解決了隨機(jī)非平穩(wěn)負(fù)載序列數(shù)據(jù)難以預(yù)測的問題；利用基于預(yù)測的局部自優(yōu)化比例分配方法進(jìn)行節(jié)點負(fù)載預(yù)分配處理，充分發(fā)揮了網(wǎng)絡(luò)節(jié)點整體計算優(yōu)勢；采用主動型空閑節(jié)點驅(qū)動策略進(jìn)行網(wǎng)絡(luò)負(fù)載動態(tài)調(diào)度，有效地降低了采樣頻率，提高了系統(tǒng)運(yùn)行效率。通過實驗分析，本文算法更有利于網(wǎng)絡(luò)節(jié)點資源的優(yōu)化配置。如何在提升節(jié)點負(fù)載預(yù)測時效性的前提下，降低負(fù)載均衡算法復(fù)雜度將是下一步研究的重點。