[發明專利]一種基于云端大數據遷移和處理成本的優化算法

在審

• 申請號: 201710445796.5
• 申請日: 2017-06-14
• 公開（公告）號: CN107273184A
• 公開（公告）日: 2017-10-20
• 發明（設計）人: 夏輝;王曉薇;范書國
• 申請（專利權）人: 沈陽師范大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48;H04L29/08
• 代理公司: 沈陽維特專利商標事務所(普通合伙)21229
• 代理人: 陳福昌

1.一種基于云端大數據遷移和處理成本的優化算法，其特征在于，包括如下步驟：

(1)定義是從數據源r∈R傳輸1GB數據到數據中心d∈D的價格，那么t時刻的帶寬總費用可定義為：

Cb(t)=Σd∈DΣr∈Rλrd(t)·brd---(1)]]>

(2)假設s_d為單時隙內數據中心d∈D上儲存1GB數據所需要的成本,則t時刻系統產生的存儲數據的總成本為：

Cs(t)=Σd∈DΣr∈Rλrd(t)·sd---(2)]]>

(3)定義為t時刻從數據中心d中租用的k類型虛擬機數量，令為t時刻數據中心d中k類型的虛擬機的價格,則數據處理所需要的計算成本為：

Cp(t)=Σd∈DΣk∈Kndk(t)·pdk(t)---(3)]]>

(4)假設為數據源r∈R傳輸數據到數據中心d∈D的延遲，α為將延遲轉換為經濟成本的權重系數，則延遲轉換的計算成本為：

Cl(t)=Σd∈DΣr∈Rα·λrd(t)·Lrd---(4)]]>

基于以上的成本公式,可以得到系統中產生的總成本為：

C(t)＝C_p(t)+C_s(t)+C_b(t)+C_l(t) (5)

假設a_r(t)為t時刻數據源r生成的數據量，由于從任意數據源生成的數據可移動到任意數據中心進行處理,設為在t時刻從數據源r移動到數據中心d的數據量,為數據源r產生的最大數據量；則有：

ar(t)≤Armax,∀r,t∈[1,T]---(6)]]>

ar(t)≤Σd∈Dλrd(t),∀r,t∈[1,T]---(7)]]>

根據上面的定義和假設，最小化時間段[0,T]內數據遷移和處理的時間平均成本可以形式化為：

P1.min:limT→∞1TΣt=1T-1E{C(t)}---(8)]]>

s.tar(t)≤Armax,∀r,t∈[1,T]---(9)]]>

ar(t)=Σd∈Dλrd(t),∀r,t∈[1,T]---(10)]]>

0≤ndk(t)≤Ndk,max,∀d,∀k,t∈[1,T]---(11)]]>

ndk(t)∈Z+∪0,∀d,∀k,t∈[1,T]---(12)]]>

從問題P1表達來看,由于數據生成是未知且動態的,資源變量是整數型,因此以上問題是一個約束隨機整數優化問題；其中約束(10)是為了確保在單時隙內分配給各數據中心數據的總和等于在該時刻產生的總數據量.約束(11)確保了所需的虛擬機數量不超過數據中心可以提供的圍.

(5)利用李雅普諾夫優化框架理論設計在線控制算法

令H_d(t)為時間序列上數據中心d中未處理的數據量，首先,定義H_d(0)＝0,則隊列H_d(t)的演化可以描述如下：

Hd(t+1)=max[Hd(t)-Σk∈Kndk(t)·vk,0]+Σr∈Rλrd(t)---(13)]]>

上述隊列的更新規則意味著所處理的數據量為新到達的數據量為為了保證隊列H_d(t)，在最壞情況下的延遲處于最大工作負載延遲l內,設計了一個相關虛擬隊列Z_d(t)，其中,虛擬隊列Z_d(t)的負載初始化為Z_d(0)＝0,且更新如下規則：

Zd(t+1)=max[Zd(t)+1Hd(t)>0(ϵ-Σk∈Kndk(t)·vk)-1Hd(t)=0Σk∈KNdk,max·vk,0]---(14)]]>

其中指示函數表示當H_d(t)＞0時等于1,否則等于0；同樣地,表示當H_d(t)＝0時為1,否則為0；ε_d為預設常數,用來控制隊列延遲的范圍。由此可以證明,若所提算法能夠保證隊列H_d(t)和Z_d(t)在長時間的穩定,則所有數據都可以在至多l個時隙延遲內得到處理.并且,l可設置為其中和分別是隊列H_d(t)和Z_d(t)的上限；

令Z(t)＝(Z_d(t))，H(t)＝(H_d(t)),分別表示虛擬隊列和實際隊列的矩陣,則可以用θ(t)＝[H(t),Z(t)]來表示實際隊列和虛擬隊列的聯合矩陣；據李雅普諾夫框架,定義李雅普諾夫函數如下:

L(θ(t))=12Σd∈D{Zd(t)2+Hd(t)2}---(15)]]>

其中L(θ(t))為系統中負載積壓的度量。則單時隙的李雅普諾夫漂移函數則可定義為：

Δ(θ(t))＝E{L(θ(t+1))L(θ(t))|θ(t)}(16)

為在保證系統隊列穩定的同時還最小化系統所產生的花費,則李雅普諾夫漂移-懲罰項可以在上式(16)漂移函數中增加系統總成本函數獲得,即：

Δ(θ(t))+V·E{C(t)|θ(t)}(17)

其中V為非負參數,它可以在系統穩定性和成本之間進行折衷.V越大,系統產生的成本就越小,反之成本就越大.因此,原來的問題P1就變成了下面的問題P2：

P2.min(17)(18)

s.t.:(9)(10)(11)(12)(19)

求解P2的關鍵是找到其上界，通過推導可證明,式子(17)的界為：

Δ(θ(t))+V·E{limT→∞1TΣt=1T-1C(t)|θ(t)}≤B+E{Σd∈DΣk∈Kndk(t)·(Vpdk(t)-Hdk(t)vk-Zdk(t)vk)|θ(t)}+E{Σd∈DΣr∈Rλdr(t)·(Vsd+Vbrd+VLrd+Hd(t))|θ(t)}---(20)]]>

其中

通過仔細研究不等式(20)右邊,將優化問題等價地分解成兩個子問題：即數據分配問題和資源供應問題；

(6)求解以上兩個子問題的細節如下所述：

a、數據遷移：為最小化式(20)右邊,其中與數據遷移相關的部分可被提取為：

min E{Σd∈DΣk∈Kλdr(t)·(Vsd+Vbrd+VαLrd+Hd(t))|θ(t)}---(21)]]>

此外,由于各數據源的數據是獨立生成的,式子(21)所述的多數據源整體優化方式可以分別在各數據源獨立執行，考慮t時刻數據源r上數據分配,則所述數據遷移問題轉化為解決如下問題：

minΣd∈Dλdr(t)[Vsd+Vbrd+VαLrd+Hd(t)]s.t.(9)(10)---(22)]]>

該問題是一個廣義的最小權重問題,從數據源r遷移到數據中心d的權重為它與數據積壓H_d(t),帶寬成本儲存成本s_d,延遲成本有關，通過使用線性規劃理論,我們可以求得以下解決方案：

λrd(t)=αr(t)d=d*0else---(23)]]>

其中顯然，t時刻算法傾向于將數據源r產生的數據遷移至該時刻具有最短任務隊列和最小運行成本的數據中心進行處理。

b、資源配置：如去掉式子(20)右邊的常數項B，則變量相關的部分可以被認為是資源供應問題，通過解決如下問題得到虛擬機最優供應策略：

min E{Σd∈DΣk∈Kndk(t)·(Vpdk(t)-Hd(t)vk-Zd(t)vk)|θ(t)}s.t.(11)(12)---(24)]]>

同理，由于各數據中心中的資源供給是獨立的，與數據分配問題相似，式子(23)可以在每個數據中心建分布地求解，因而，對于單個數據中心d，資源供應問題可以進一步改寫為：

min E{Σk∈Kndk(t)·(Vpdk(t)-Hd(t)vk-Zd(t)vk)|θ(t)}s.t.(11)(12)---(25)]]>

易得上述線性問題的解為：

ndk(t)=Ndk,max,ifHd(t)+Zd(t)>Vpdk(t)vk0,ifHd(t)+Zd(t)≤Vpdk(t)vk---(26)]]> 4