[發明專利]一種分布式云中計算中心選擇方法及其應用

有效

• 申請號: 201410172326.2
• 申請日: 2014-04-25
• 公開（公告）號: CN103997515B
• 公開（公告）日: 2018-02-02
• 發明（設計）人: 沈玉龍;宗旋;張琪;姜曉鴻;裴慶祺;張華慶
• 申請（專利權）人: 西安電子科技大學昆山創新研究院;西安電子科技大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;G06F17/30
• 代理公司: 西安智萃知識產權代理有限公司61221
• 代理人: 張超

1.一種分布式云中計算中心選擇方法，其特征在于包括如下步驟：

1)設定分布式云中計算中心的無向圖G＝(V,E)，其中V是無向圖G中頂點的集合，代表分布式云中的計算中心，E是無向圖G中邊的集合，表示不同計算中心間的連接；

2)在無向圖G中隨機選取一個頂點的集合V'，集合V'所代表的計算中心的計算容量由用戶預先設定；以集合V'中的源點v0為起始點，將源點v0周圍距離源點v0最近的頂點加入到集合V'中，若集合V'中的計算中心擁有的計算容量達到預先設定的計算容量，則終止頂點的加入；若集合V'中的計算中心擁有的計算容量未達到預先設定的計算容量，則繼續將源點v0周圍距離源點v0最近的頂點加入到集合V'中；

3)對滿足終止頂點加入的集合V'，在集合V'中連通圖的邊的長度之和作為兩頂點間的內部最長線段，將該內部最長線段作為第一條線段；

4)將集合V'中第一條線段的兩個頂點組成頂點集合V1，除去第一條線段的兩個頂點的所有其他頂點組成另一個頂點集合V2；計算頂點集合V2中的頂點到頂點集合V1的頂點的外部最長線段和外部最長路徑長度，外部最長線段的兩個頂點組成集合U；將集合U中的兩個頂點加入到頂點集合V1中，并將外部最長線段的兩個頂點從頂點集合V2 中去除；接著，將計算出的外部最長線段的長度與外部最長路徑長度進行加和，并將該加和獲得的長度值作為下一次迭代過程的外部最長路徑長度；

5)所述步驟4)是迭代過程，迭代過程的終止條件為直至頂點集合V2為空集；若頂點集合V2滿足迭代過程的終止條件，則獲得外部最長路徑長度和分布有供選擇的最優計算中心的最優子圖G'。

2.一種云平臺處理用戶提交應用程序或任務的方法，其特征在于：根據用戶向云平臺托管的任務需求，采用權利要求1所述一種分布式云中計算中心選擇方法，在云平臺中篩選最優子圖G'，根據最優子圖G'中的最優計算中心提供滿足用戶需求的虛擬機；

云平臺提供的滿足應用程序或任務所需的資源需求為(θ₁,θ₂,…,θ_n)，云平臺中存在m種不同類型的虛擬機，類型為k的虛擬機占用資源為(c_1k,c_2k,…,c_nk)，支付費用為p_k；其中，n為資源需求的數量，且為正整數；

讓用戶在得到足夠資源的前提下，在所述最優子圖G'中選擇最優計算中心，最優計算中心提供的虛擬機占用資源的最少支付費用的計算公式如下：

其中，i表示云平臺存在的類型為i的虛擬機，i的取值范圍[1，m]；x_i表示類型為i的虛擬機需求數目；p_i表示類型為i的虛擬機支付費用；

所述支出最少費用的計算公式滿足如下約束條件：

其中，(x₁,x₂,…,x_m)表示每種類型的虛擬機需求數目。

3.根據權利要求2所述的云平臺處理用戶提交應用程序或任務的方法，其特征在于：所述最優子圖G'中存在n個計算中心，各個計算中心的容量分別是d₁,d₂,…,d_n；用戶請求的分布式任務由m個子任務組成，各個子任務所需的虛擬機數目分別是g₁,g₂,…,g_m；用戶請求的分布式任務需要N個虛擬機，且滿足g₁+g₂+…+g_m＝N；

某個計算中心放置一定數目虛擬機的變量為p_j(y_j)，j∈{1,2,…,n}，變量p_j(y_j)表示計算中心j在當前放置y_j個虛擬機的條件下的可用帶寬大小，變量p_j(y_j)隨著放置虛擬機個數的增加而減小；

變量x_ijk,i∈{1,2,…,N},j∈{1,2,…,n},k∈{1,2,…,m}表示虛擬機i為子任務k提供服務，同時被放置在計算中心j中；

使計算中心之間的可用帶寬之和最大化的目標公式如下：

所述使計算中心之間的可用帶寬之和最大化的目標公式滿足如下約束條件：

約束條件一：

約束條件二：

約束條件三：

其中，約束條件一中的變量x_ijk∈{0,1}，是個整型變量，具體的某個虛擬機只為一個子任務服務同時只能被放置在一個計算中心中；約束條件二表示分配某個計算中心的虛擬機數目要小于等于這個計算中心的容量；約束條件三表示所有計算中心為某個子任務提供的虛擬機數目之和等于這個子任務所需的虛擬機數目。