[發明專利]基于服務質量要求驅動的云計算網絡資源分配方法

有效

• 申請號: 201410081223.5
• 申請日: 2014-03-06
• 公開（公告）號: CN103856563B
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 徐雷;楊余旺;李亞平;唐振民;蘭少華;張小飛
• 申請（專利權）人: 南京理工大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L29/06
• 代理公司: 南京理工大學專利中心32203
• 代理人: 朱顯國

1.一種基于服務質量要求驅動的云計算網絡資源分配方法，其特征在于，包括以下步驟：

步驟1，云計算網絡中中央處理服務器收集用戶終端的虛擬資源使用申請；

步驟2，云計算網絡中中央處理服務器收集底層網絡中各節點的可用資源；

步驟3，云計算網絡中中央處理服務器采用量子免疫方法進行虛擬資源分配，包括以下步驟：

步驟3.1，初始化量子免疫方法參數，初始化種群中每個抗體的量子編碼向量；所述的初始化量子免疫方法參數，初始化種群中每個抗體的量子編碼向量，具體為：

(1)初始化量子免疫方法抗體的數目N_p、量子免疫方法迭代次數N_g，其中N_p、N_g均為整數且N_p∈[100,120]、N_g∈[300,350]；

(2)令迭代次數序號gen＝1，初始化虛擬鏈接(n,m)的業務流是否經過底層鏈接(u,v)的指示變量虛擬鏈接(n,m)的業務流經過底層的鏈接(u,v)的流量虛擬節點的無向帶權圖G^V＝(N^V,E^V)和底層節點的無向帶權圖G^S＝(N^S,E^S)，其中NV表示虛擬節點集合，E^V表示虛擬節點鏈接集合，N^S是底層節點集合，E^S是底層節點鏈接集合；

(3)初始化擴充的底層無向帶權圖G^S'＝(N^S',E^S')、擴充的底層節點鏈接集合其中N^S'表示擴充的底層節點集合且N^S'＝N^S∪N^V，n^V表示底層節點n，n^S表示底層節點鏈接s；

(4)初始化表示虛擬鏈接(n,m)的總業務流量b(n,m)、底層鏈接(u,v)的傳輸帶寬BW(u,v)、底層節點w資源i的最大值容量C_i(w)、種群中每個抗體的量子編碼向量Qxf＝[qx,qf]；其中向量表示底層鏈接分配指示的量子編碼向量，向量表示底層鏈接分配流量的量子編碼向量，α_i和β_i表示向量qx中的量子比特第i位，χ_i和δ_i表示向量qf中的量子比特第i位；和N_L表示擴充的底層無向帶權圖G^S'中鏈接的數目；

步驟3.2，將每個抗體的量子編碼向量轉化為二進制向量，具體為：對量子編碼向量Qxf進行觀察得到二進制向量XF＝[x,f]，向量中滿足公式(1)：

$x_{uv}^{nm}\∈\{0,1\},\∀u,v\∈N^{S^{\′}},\∀(n,m)\∈E^V---\left(1\right)$

向量中滿足公式(2)：

$f_{uv}^{nm}\≥0,\∀u,v\∈N^{S^{\′}},\∀(n,m)\∈E^V---\left(2\right)$

其中，XF表示量子免疫方法二進制編碼向量，x表示底層鏈接分配指示的二進制編碼向量，f表示底層鏈接分配流量的二進制編碼向量；

步驟3.3，檢驗每個抗體編碼向量是否滿足底層節點的流守恒公式和底層節點最大容量限制公式，檢驗每個抗體編碼向量是否滿足虛擬流量和帶寬容量限制，檢驗每個抗體編碼向量是否滿足資源分配解的可行性限制，具體步驟如下：

(1)檢驗每個抗體編碼向量XF＝[x,f]中和是否滿足底層節點的流守恒公式(3)和底層節點最大容量限制公式(4)：

$\left\{\begin{array}{c}\underset{v\∈N^{S^{\′}}}{\Σ}{f}_{uv}^{nm}-\underset{w\∈N^{S^{\′}}}{\Σ}{f}_{wu}^{nm}=0,\∀(n,m)\∈E^V,\∀u\∈N^{S^{\′}}/\{n,m\}\\ \underset{v\∈N^{S^{\′}}}{\Σ}{f}_{nv}^{nm}-\underset{w\∈N^{S^{\′}}}{\Σ}{f}_{wn}^{nm}=b(n,m),\∀(n,m)\∈E^V,n\∈N^{S^{\′}}\\ \underset{v\∈N^{S^{\′}}}{\Σ}{f}_{mv}^{nm}-\underset{w\∈N^{S^{\′}}}{\Σ}{f}_{wm}^{nm}=-b(n,m),\∀(n,m)\∈E^V,m\∈N^{S^{\′}}\end{array}\right.---\left(3\right)$

$\left\{\begin{array}{c}{P}_{c_i\left(p\right)}{c}_i\left(p\right)x_{pw}^{mn}\≤C_i\left(w\right),\∀p\⊆N^{S^{\′}}/S^S,\\ \∀w\⊆N^S,\∀i\∈I,\∀a\∈A,\∀(n,m)\∈E^V\end{array}\right.---\left(4\right)$

其中，表示虛擬鏈接(n,m)的業務流經過底層的鏈接(u,v)的流量，表示虛擬鏈接(n,m)的業務流經過底層的鏈接(n,v)的流量，表示虛擬鏈接(n,m)的業務流經過底層的鏈接(m,v)的流量，表示虛擬鏈接(n,m)的業務流經過底層的鏈接(w,u)的流量，表示虛擬鏈接(n,m)的業務流經過底層的鏈接(w,n)的流量，表示虛擬鏈接(n,m)的業務流經過底層的鏈接(w,m)的流量，p表示虛擬節點，w表示底層節點，表示虛擬節點p申請資源i的預留百分比，(n,m)表示虛擬節點n和虛擬節點m之間的鏈接，(u,v)表示底層節點u和底層節點v之間的鏈接，c_i(p)表示虛擬節點p資源i的使用量，表示虛擬鏈接(n,m)的業務流經過底層鏈接(p,w)的指示變量，I表示明確的非功能性質集合，a表示云計算網絡中CPU資源、存儲資源或帶寬資源；

(2)檢驗每個抗體編碼向量XF＝[x,f]中和是否滿足公式(5)和公式(6)，公式(5)表示經過底層鏈接(u,v)的虛擬流量、公式(6)表示不超過底層鏈接(u,v)的帶寬容量：

$(f_{uv}^{nm}+f_{vu}^{nm})\≤BW(u,v)x_{uv}^{nm},\∀u,v\∈N^{S^{\′}},\∀(n,m)\∈E^V---\left(5\right)$

$\underset{(n,m)\∈E^V}{\Σ}(f_{uv}^{nm}+f_{vu}^{nm})\≤BW(u,v),\∀u,v\∈N^{S^{\′}}---\left(6\right)$

其中，表示虛擬鏈接(n,m)的業務流經過底層的鏈接(v,u)的流量，

(3)檢驗每個抗體編碼向量XF＝[x,f]中和是否滿足公式(7)～(9)，公式(7)保證每個底層節點只能選擇一個虛擬節點，公式(8)保證每個底層節點的同一種資源只能分配給一個虛擬節點，公式(9)保證每個虛擬節點只能選擇一個底層節點：

$\underset{p\⊆N^{S^{\′}}/N^S}{\Σ}{x}_{pw}^{mn}\≤1,\∀w\⊆N^S,\∀(m,n)\∈E^V,\∀A---\left(7\right)$

$\underset{w\⊆N^S}{\Σ}{x}_{pw}^{mn}=0,\∀p\⊆N^{S^{\′}}/N^S,\∀(m,n)\∈E^V---\left(8\right)$

$\underset{w\⊆N^S}{\Σ}{x}_{pw}^{mn}=1,\∀p\⊆N^{S^{\′}}/N^S,\∀(m,n)\∈E^V---\left(9\right)$

其中，A表示云計算網絡中資源總和；表示虛擬鏈接(m,n)的業務流經過底層鏈接(p,w)的指示變量；

(4)檢驗每個抗體編碼向量XF＝[x,f]中和是否滿足公式(10)～(12)，公式(10)和公式(12)保證對虛擬鏈接(n,m)業務流經過的底層鏈接(u,v)的指示變量進行設置，公式(11)保證資源映射結果是一個連通圖，公式(11)對虛擬鏈接(n,m)業務流沒有經過的鏈接(u,v)的指示變量進行設置：

$x_{uv}^{nm}=x_{vu}^{nm},\∀u,v\∈N^{S^{\′}},\∀(n,m)\∈E^V---\left(10\right)$

$x_{uv}^{nm}=x_{uv}^{nk}=x_{uv}^{lm}=0,\∀u,v\∈N^{S^{\′}}/N^V,k,l\∈N^{S^{\′}}{N}^{S^{\′}},(n,m)\∈E^V---\left(11\right)$

其中，表示虛擬鏈接(n,m)的業務流經過底層鏈接(v,u)的指示變量，表示虛擬鏈接(n,k)的業務流經過底層鏈接(u,v)的指示變量，表示虛擬鏈接(l,m)的業務流經過底層鏈接(u,v)的指示變量；

步驟3.4，確定每個抗體的期望繁殖概率，根據期望繁殖概率從種群中提取父代種群和記憶庫種群；采用量子旋轉門操作方法得到新群體中抗體，并且合并記憶庫中抗體，構成新一代種群；

步驟3.5，重復步驟3.2～步驟3.4NI_g次，輸出云計算網絡虛擬資源分配的最優解，NI_g表示量子免疫方法的最大迭代次數。