基于群體智能算法的大數(shù)據(jù)遷移策略研究

曾 毅,馬琳娟,魚 明

(1.廣西大學(xué)行健文理學(xué)院 理工學(xué)部 計(jì)算機(jī)與信息工程系， 南寧 530005； 2.北京理工大學(xué) 計(jì)算機(jī)學(xué)院， 北京 100081； 3.石河子大學(xué) 經(jīng)濟(jì)與管理學(xué)院， 新疆 石河子 832000)

伴隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，全球信息互通和共享已經(jīng)逐步成為現(xiàn)實(shí)。社會大眾在日常工作和生活中，通過各種聯(lián)網(wǎng)設(shè)備進(jìn)行辦公和娛樂，大大提高了工作的效率和生活的便利性。然而，隨著互聯(lián)網(wǎng)用戶數(shù)量的快速增加，網(wǎng)絡(luò)信息量急劇增長，意味著當(dāng)前已經(jīng)進(jìn)入了大數(shù)據(jù)信息化時代。當(dāng)用戶訪問服務(wù)器時，對于以往的服務(wù)器運(yùn)行體系來說，用戶必須保持與數(shù)據(jù)中心服務(wù)器的連接并發(fā)送訪問資源的請求(占用資源)[1]。這種運(yùn)作模式已經(jīng)無法應(yīng)對現(xiàn)階段復(fù)雜的場景需求，造成了服務(wù)器上計(jì)算資源的大量浪費(fèi)。在上述背景下，云計(jì)算模式[2-3]應(yīng)運(yùn)而生。作為一種新興的商業(yè)計(jì)算模式，由Google提出的云計(jì)算在IT行業(yè)內(nèi)引起了第三次變革浪潮。

不同于傳統(tǒng)的數(shù)據(jù)中心，云數(shù)據(jù)中心的規(guī)模和自動化程度更高，導(dǎo)致云數(shù)據(jù)中心的管理和維護(hù)需要解決更加復(fù)雜的問題[4]。如何有效地管理和維護(hù)云數(shù)據(jù)中心成為目前相關(guān)研究領(lǐng)域的熱點(diǎn)[5]。其中，大數(shù)據(jù)遷移是云服務(wù)器新老系統(tǒng)更替、配置修改和升級軟件的基礎(chǔ)。如果數(shù)據(jù)中心中某些節(jié)點(diǎn)出現(xiàn)負(fù)載異常，就需要執(zhí)行動態(tài)遷移策略將數(shù)據(jù)流量遷移到其他服務(wù)器設(shè)備上，以分布式處理方式完成負(fù)載均衡，這直接影響著云計(jì)算服務(wù)的效率。可以看出，一個先進(jìn)的動態(tài)數(shù)據(jù)遷移策略對于云計(jì)算服務(wù)來說十分重要[6]。

本文提出了一種基于群體智能算法的大數(shù)據(jù)遷移策略，解決了大數(shù)據(jù)遷移過程中的負(fù)載平衡和帶寬瓶頸問題。在基于云計(jì)算架構(gòu)的大數(shù)據(jù)遷移技術(shù)基礎(chǔ)上，采用人工魚群優(yōu)化算法來解決m個服務(wù)器之間n個數(shù)據(jù)遷移的最優(yōu)解問題。此外，把量子比特引入到人工魚群算法中，以避免陷入局部最優(yōu)并提高收斂速度。仿真結(jié)果表明，相比現(xiàn)有的遷移策略，本文算法更好地提升了云計(jì)算服務(wù)器的資源利用率，在一定程度上緩解了云數(shù)據(jù)中心的負(fù)載均衡和帶寬擁擠問題。

1 相關(guān)研究分析

大數(shù)據(jù)遷移直接影響著云計(jì)算服務(wù)的效率，是近年研究的熱點(diǎn)。黃冬梅等[7]針對混合云存儲架構(gòu)中的數(shù)據(jù)遷移問題，提出了基于海洋生命周期的混合云存儲中大數(shù)據(jù)遷移算法。在該遷移算法中，將海洋數(shù)據(jù)的敏感度、數(shù)據(jù)訪問頻率、數(shù)據(jù)大小、數(shù)據(jù)時間長度等因素作為遷移因子，兼顧考慮了數(shù)據(jù)存儲容量和數(shù)據(jù)訪問過程中的動態(tài)變化，能夠有效降低數(shù)據(jù)管理成本，同時保證數(shù)據(jù)的訪問速度。張晉芳等[8]分別針對云計(jì)算環(huán)境下大數(shù)據(jù)動態(tài)策略中的全局時間消耗、網(wǎng)絡(luò)訪問次數(shù)和全局負(fù)載均衡3個參數(shù)進(jìn)行求解，在Cloudsim仿真平臺中取得了良好的全局負(fù)載均衡效果。

群體智能優(yōu)化算法是指無智能的或具有簡單智能的個體通過協(xié)作發(fā)揮出群體智能優(yōu)勢的優(yōu)化算法，可在沒有集中控制且不提供全局模型的條件下為復(fù)雜分布式問題求解提供基礎(chǔ)[9-11]。由于具有并行性和分布式優(yōu)勢，群體智能優(yōu)化算法逐步成為各種復(fù)雜工程最優(yōu)求解問題的一個重要研究方向。其中，人工魚群算法是一種基于模擬魚群行為的群體智能算法[12]，主要利用魚的三大基本行為(覓食、聚群和追尾行為)，采用自上而下的尋優(yōu)模式，從構(gòu)造個體的底層行為開始，通過魚群中各個體的局部尋優(yōu)達(dá)到全局最優(yōu)值在群體中凸顯出來的目的。因此，本文將人工魚群算法應(yīng)用于多個服務(wù)器之間的負(fù)載尋求問題，通過設(shè)定合理目標(biāo)函數(shù)進(jìn)行全局搜索。此外，為了減少搜索時間，獲得更好的全局尋優(yōu)能力，本文把量子比特引入到人工魚群算法中來完成最優(yōu)求解。

2 基于云計(jì)算架構(gòu)的大數(shù)據(jù)遷移問題分析

2.1 問題表述

人工魚群算法模擬了自然界中魚群往往能自行或尾隨其他魚找到營養(yǎng)物質(zhì)豐富區(qū)域的行為，根據(jù)人工魚群的特點(diǎn)，構(gòu)造人工魚模擬魚群的覓食、聚群和追尾行為，從而實(shí)現(xiàn)尋優(yōu)的目的。人工魚群具有收斂速度快、模型簡單的優(yōu)點(diǎn)，但存在優(yōu)化精度不足的缺點(diǎn)。

通常情況下，云計(jì)算的體系結(jié)構(gòu)如圖1所示。該架構(gòu)中的大數(shù)據(jù)遷移涉及云平臺的負(fù)載均衡問題和帶寬利用率問題。作為本文研究的目標(biāo)，數(shù)據(jù)遷移是一種將離線存儲與在線存儲融合的技術(shù)，其過程大致可以分為抽取、轉(zhuǎn)換、裝載3個步驟?；谠朴?jì)算架構(gòu)的大數(shù)據(jù)遷移問題能看作為m個服務(wù)器之間n個數(shù)據(jù)遷移的最優(yōu)解問題。設(shè)Sum為n個待遷移數(shù)據(jù)大小的總和，T為數(shù)據(jù)需要的傳輸時間，兩者的計(jì)算方式分別為：

(1)

(2)

其中：Mij表示第i個服務(wù)器中的第j個待遷移數(shù)據(jù)。設(shè)η為該服務(wù)器的帶寬占用率，則

(3)

其中：a表示當(dāng)前服務(wù)器上的數(shù)據(jù)變動參數(shù)，a∈[0,π]。

2.2 基于人工魚群的服務(wù)器數(shù)據(jù)遷移

(4)

(5)

圖1 云計(jì)算的體系結(jié)構(gòu)

云計(jì)算架構(gòu)中基于人工魚群算法的大數(shù)據(jù)遷移原理如圖2所示，其中標(biāo)準(zhǔn)人工魚群算法的流程如圖3所示[13]。

圖2 基于人工魚群算法的大數(shù)據(jù)遷移原理

圖3 標(biāo)準(zhǔn)人工魚群算法的流程

3 改進(jìn)人工魚群算法

為避免人工魚群算法陷入局部極值點(diǎn)或者產(chǎn)生徘徊從而降低收斂速度，本文引入量子比特對標(biāo)準(zhǔn)人工魚群算法進(jìn)行改進(jìn)。

采用量子比特[14]與人工魚群相結(jié)合的方式對其進(jìn)行改進(jìn)。設(shè)種群大小為n，其信息素用量子位P=(p1,p2,…,pn)表示?；谌斯~群三大基本行為的算法流程如下：

(6)

其中：Rand 表示一個取值范圍為(0,1)的隨機(jī)數(shù)；step 表示步長；dij表示人工魚的當(dāng)前鄰域。

2) 聚群行為。設(shè)人工魚群中人工魚的dij內(nèi)感知到的伙伴數(shù)目為nf且中心位置狀態(tài)為Pc。若Yc/nf<δYi，則說明該伙伴中心處具有豐富的食物且附近擁擠程度較低，那么朝著該伙伴中心位置方向移動一步；反之，跳轉(zhuǎn)到上一步覓食行為。其數(shù)學(xué)表達(dá)式為：

(7)

其中，δ表示擁擠度因子。

3) 追尾行為。設(shè)人工魚在當(dāng)前的dij內(nèi)感知到食物濃度最大狀態(tài)是Pmax，若Ymax/nf<δYj，說明Pmax狀態(tài)存在較大的食物濃度且其附近擁擠程度較低，則朝Pmax的方向移動一步；反之，跳轉(zhuǎn)到覓食行為。其數(shù)學(xué)表達(dá)式為：

(8)

4) 隨機(jī)行為。設(shè)人工魚此刻的狀態(tài)是Pi，在感知范圍Visual 內(nèi)隨機(jī)挑選另外一個狀態(tài)Pj并朝著此方向前進(jìn)一步。

通過公告板保存最優(yōu)人工魚群個體的狀態(tài)。對于所有人工魚個體來說，在其尋優(yōu)過程中每次執(zhí)行結(jié)束都會將自身狀態(tài)和公告板上的狀態(tài)進(jìn)行對比，若其狀態(tài)比公告板狀態(tài)更好，則替換公告板的狀態(tài)。對于要解決的大數(shù)據(jù)服務(wù)節(jié)點(diǎn)遷移尋優(yōu)問題，按照式(4)對量子人工魚群當(dāng)前的狀態(tài)進(jìn)行評估，挑選并執(zhí)行一個使種群接下來狀態(tài)為最優(yōu)的行為。人工魚群中個體的量子行為更新方式為[14]：

(9)

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

本文采用開源的虛擬化服務(wù)的云計(jì)算仿真平臺Cloud Sim，對基于量子人工魚群算法大數(shù)據(jù)遷移進(jìn)行了驗(yàn)證分析。實(shí)驗(yàn)硬件環(huán)境：Windows 7 操作系統(tǒng)，Intel(R) Core(TM) i5 CPU，4GB RAM，500G硬盤。實(shí)驗(yàn)軟件環(huán)境： Eclipse8.5，Cloud Sim3.0.3。量子人工魚群算法的參數(shù)設(shè)置如表1所示。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

4.2 算法性能驗(yàn)證

為進(jìn)一步驗(yàn)證量子人工魚群算法的性能，選擇文獻(xiàn)[15]中的實(shí)例，將蟻群算法[16]、標(biāo)準(zhǔn)人工魚群算法[15]和量子人工魚群算法進(jìn)行對比，結(jié)果如表2所示。不同算法在已知最優(yōu)解為295時的收斂速度如圖4所示。

表2 數(shù)值結(jié)果對比

圖4 不同算法的收斂速度對比

4.3 數(shù)據(jù)遷移結(jié)果分析

在實(shí)驗(yàn)環(huán)境下根據(jù)帶寬占用率(%)，將本文的量子人工魚群與隨機(jī)遷移策略、最優(yōu)遷移策略[17]進(jìn)行對比，對比結(jié)果如表3所示?？梢钥闯觯S著帶寬的不斷提高，3種策略的服務(wù)能力會相應(yīng)提高，即帶寬占用率會越來越低。從表3可以看出，在相同帶寬條件下，相比隨機(jī)策略和最優(yōu)策略，基于量子人工魚群算法的遷移策略因?yàn)檎加玫膸捀?，具有更好的帶寬利用率，從而可以讓云?jì)算數(shù)據(jù)中心提供更多的服務(wù)。

設(shè)置10周的測試時間，在負(fù)載均衡方面對待遷移數(shù)據(jù)的目標(biāo)位置選擇策略進(jìn)行驗(yàn)證分析，期間每2周采集1次數(shù)據(jù)。10周內(nèi)3種算法的負(fù)載均衡的對比結(jié)果如圖5所示?？梢钥闯觯S著測試時間的增加，3種遷移策略的負(fù)載均衡度均不斷降低。但是，在相同時間點(diǎn)時基于量子人工魚群算法的遷移策略具有最好的負(fù)載均衡效果，有效增加了云計(jì)算服務(wù)器集群中數(shù)據(jù)節(jié)點(diǎn)的資源利用率。

表3 帶寬占用率的對比結(jié)果

圖5 負(fù)載均衡的比較

綜上所述，基于量子人工魚群算法的云數(shù)據(jù)遷移策略是一種具有較好帶寬利用率和負(fù)載均衡效果的方法。

5 結(jié)束語

本文提出了一種基于群體智能算法的大數(shù)據(jù)遷移策略，有效解決了大數(shù)據(jù)遷移過程中的負(fù)載平衡和帶寬瓶頸問題。在基于云計(jì)算架構(gòu)的大數(shù)據(jù)遷移技術(shù)基礎(chǔ)上，采用人工魚群優(yōu)化算法來解決m個服務(wù)器之間n個數(shù)據(jù)遷移的最優(yōu)解問題。此外，把量子比特引入人工魚群算法中，從而避免陷入局部最優(yōu)并實(shí)現(xiàn)了快速收斂速度。仿真結(jié)果表明，相比現(xiàn)有的遷移策略，提出算法更好地提升了云計(jì)算服務(wù)器的資源利用率，在一定程度上緩解了云數(shù)據(jù)中心的負(fù)載均衡和帶寬擁擠問題。

本文將量子比特機(jī)制引入人工魚群算法中，在大數(shù)據(jù)的遷移問題中，過大的數(shù)據(jù)量將帶來大的計(jì)算負(fù)擔(dān)。未來將重點(diǎn)關(guān)注提高人工魚群收斂速度的研究，計(jì)劃通過分布式計(jì)算提高尋優(yōu)速度，從而提高算法的實(shí)用性。