[發(fā)明專利]一種基于組合云拍賣機(jī)制和隱私保護(hù)的動(dòng)態(tài)虛擬機(jī)分配方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910785871.1
• 申請(qǐng)日: 2019-08-23
• 公開（公告）號(hào): CN110460440B
• 公開（公告）日: 2021-12-07
• 發(fā)明（設(shè)計(jì)）人: 陳志立;陳昕;仲紅;田苗苗
• 申請(qǐng)（專利權(quán)）人: 安徽大學(xué)
• 主分類號(hào): H04L9/08
• 分類號(hào): H04L9/08;G06F9/50
• 代理公司: 安徽省合肥新安專利代理有限責(zé)任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于組合云拍賣機(jī)制和隱私保護(hù)的動(dòng)態(tài)虛擬機(jī)分配方法，其特征是應(yīng)用于由n個(gè)競(jìng)拍者{u₁,u₂,...,u_j,...,u_n}，一個(gè)提供m種虛擬機(jī)實(shí)例{VM₁,VM₂,...,VM_i,...,VM_m}的云拍賣商，一個(gè)代理服務(wù)提供方以及一個(gè)可信服務(wù)器所組成的動(dòng)態(tài)資源分配云拍賣場(chǎng)景中；其中，u_j表示第j個(gè)競(jìng)拍者；VM_i表示第i種虛擬機(jī)實(shí)例；j＝1,2,...,n；i＝1,2,...,m；所述動(dòng)態(tài)虛擬機(jī)分配方法包括以下步驟：

S1、所述云拍賣商初始化階段：

初始化m種虛擬機(jī)實(shí)例的計(jì)算能力向量w＝(w₁,w₂,...,w_i,...,w_m)，其中，w_i表示第i種虛擬機(jī)實(shí)例VM_i的計(jì)算能力，且w₁＝1且w₁＜w₂＜…＜w_m，i＝1,...,m；

根據(jù)最小計(jì)算能力的虛擬機(jī)實(shí)例VM₁，初始化最大虛擬機(jī)實(shí)例值為M；

以兩個(gè)連續(xù)拍賣之間的時(shí)間間隔為一個(gè)單位時(shí)間，初始化在一個(gè)單位時(shí)間內(nèi)運(yùn)行一個(gè)最小計(jì)算能力的虛擬機(jī)實(shí)例VM₁的成本為c_R以及在一個(gè)單位時(shí)間內(nèi)閑置一個(gè)最小計(jì)算能力的虛擬機(jī)實(shí)例VM₁的成本為c_I，c_R＞c_I；

S2、提交報(bào)價(jià)階段：

對(duì)于第j個(gè)競(jìng)拍者u_j將自己的報(bào)價(jià)信息B_j和身份標(biāo)識(shí)符Id_j分別拆分為兩個(gè)部分的分享值和以及和從而以秘密分享的形式將和以及和分別提交給云拍賣商和代理服務(wù)提供方；其中和分別表示第j個(gè)競(jìng)拍者u_j請(qǐng)求第i種虛擬機(jī)實(shí)例VM_i的第一部分?jǐn)?shù)量和第二部分?jǐn)?shù)量，和分別表示第j個(gè)競(jìng)拍者u_j愿意在一個(gè)單位時(shí)間內(nèi)使用所請(qǐng)求的多種虛擬機(jī)實(shí)例所支付的第一部分價(jià)格和第二部分價(jià)格，和分別表示第j個(gè)競(jìng)拍者u_j第一部分和第二部分的身份標(biāo)識(shí)符；

S3、秘密分享計(jì)算階段：

云拍賣商和代理服務(wù)提供方分別收到對(duì)應(yīng)的報(bào)價(jià)信息的分享值后，由第三方可信服務(wù)器生成乘法三元組，并將乘法三元組拆分為兩個(gè)部分的分享值并分別提供給云拍賣商和代理服務(wù)提供方；

所述云拍賣商和代理服務(wù)提供方由相應(yīng)得到的報(bào)價(jià)信息的分享值和乘法三元組的分享值，在域上進(jìn)行比特的加性秘密分享計(jì)算，從而得到競(jìng)拍者的分配向量及其支付向量和分配的虛擬機(jī)數(shù)量；

所述步驟S3的秘密分享計(jì)算階段包括以下步驟：

步驟1、報(bào)價(jià)排序：

步驟1.1、所述云拍賣商設(shè)置一個(gè)保留價(jià)格v_res，且v_res＝Sub(c_R,c_I)；Sub表示兩個(gè)數(shù)的減法操作；

步驟1.2、添加一個(gè)虛擬競(jìng)拍者u₀，其報(bào)價(jià)為B₀＝(1,0,...,0,...,0,v_res)，并分為兩個(gè)部分的分享值和從而以秘密分享的形式分別提交給云拍賣商和代理服務(wù)提供方；其中，和分別表示虛擬競(jìng)拍者u₀的第一部分報(bào)價(jià)和第二部分報(bào)價(jià)；

所述云拍賣商和代理服務(wù)提供方共同計(jì)算報(bào)價(jià)密度d_j＝Div(v_j,s_j)；其中Div表示兩個(gè)數(shù)的除法操作；v_j表示第j個(gè)競(jìng)拍者u_j愿意在一個(gè)單位時(shí)間內(nèi)使用所請(qǐng)求的多種虛擬機(jī)實(shí)例所支付的價(jià)格，s_j表示第j個(gè)競(jìng)拍者u_j請(qǐng)求的虛擬機(jī)實(shí)例總數(shù)量，且r_i^j表示第j個(gè)競(jìng)拍者u_j請(qǐng)求第i種虛擬機(jī)實(shí)例VM_i的數(shù)量，j＝0,...,n；其中，Mul表示兩個(gè)數(shù)的乘法操作；Add表示加法操作；

步驟1.3、用排序網(wǎng)絡(luò)將n個(gè)競(jìng)拍者按報(bào)價(jià)密度降序排序，得到降序后的n個(gè)競(jìng)拍者{u′₁,u′₂,...,u′_j,...,u′_n}，其中，u′_j表示降序后的第j個(gè)競(jìng)拍者，并將降序后的第j個(gè)競(jìng)拍者u′_j的報(bào)價(jià)密度記為d′_j，將降序后的第j個(gè)競(jìng)拍者u′_j請(qǐng)求的虛擬機(jī)實(shí)例總數(shù)量記為s′_j，j＝1,...,n；

步驟2、虛擬機(jī)分配：

步驟2.1、定義三個(gè)變量：分配向量為X′＝(x′₁,x′₂,...,x′_j,...,x′_n)；報(bào)價(jià)不低于保留價(jià)格的競(jìng)拍者數(shù)量為L(zhǎng)；分配的虛擬機(jī)實(shí)例數(shù)量總和為s；其中，x′_j＝1代表降序后的第j個(gè)競(jìng)拍者u′_j請(qǐng)求的虛擬機(jī)實(shí)例被分配，x′_j＝0代表降序后的第j個(gè)競(jìng)拍者u′_j請(qǐng)求的虛擬機(jī)實(shí)例未被分配，j＝1,...,n；

初始化X′＝(0,0,...,0...,0)，L＝0，s＝0；

云拍賣商和代理服務(wù)提供方計(jì)算Cmp₁(d′_j,d₀)并賦值給flag′_j，計(jì)算Add(L,flag′_j)并賦值給L；其中，flag′_j表示降序后的第j個(gè)競(jìng)拍者u′_j的報(bào)價(jià)密度是否比保留價(jià)格高，若flag′_j＝1代表示降序后的第j個(gè)競(jìng)拍者u′_j的報(bào)價(jià)密度d′_j≥d₀，flag′_j＝0代表示降序后的第j個(gè)競(jìng)拍者u′_j的報(bào)價(jià)密度d′_j＜d₀，Cmp₁表示比較操作，即d′_j≥d₀時(shí)，令Cmp₁(d′_j,d₀)＝1，d′_j＜d₀時(shí)，令Cmp₁(d′_j,d₀)＝0；

步驟2.2、在L個(gè)競(jìng)拍者里確定分配向量并分配虛擬機(jī)實(shí)例：

步驟2.2.1、初始化j＝1；

步驟2.2.2、云拍賣商和代理服務(wù)提供方計(jì)算Cmp₁(M,Add(s,s′_j))并賦值給x′_j，計(jì)算Add(s,Mul(x′_j,s′_j))并賦值給s；

步驟2.2.3、將j+1賦值給j后，判斷j＞L是否成立，若成立，則執(zhí)行步驟2.2.4，否則，返回步驟2.2.2；

步驟2.2.4、對(duì)于d′_j＜d₀的競(jìng)拍者，令x′_j＝0，其中，j＝L+1,...,n；則得到降序后的n個(gè)競(jìng)拍者請(qǐng)求的虛擬機(jī)實(shí)例是否被分配所組成的分配向量X′＝(x′₁,x′₂,...,x′_j,...,x′_n)；

步驟2.2.5、所述云拍賣商和代理服務(wù)提供方計(jì)算第i種虛擬機(jī)實(shí)例VM_i的實(shí)際分配數(shù)量k_i＝Add(Mul(x₁,r_i¹),Mul(x₂,r_i²),...,Mul(x_j,r_i^j),...,Mul(x_n,r_iⁿ))，從而得到m種虛擬機(jī)實(shí)例的實(shí)際分配數(shù)量；i＝1,...,m，j＝1,...,n；

步驟2.2.6、所述云拍賣商公布m種虛擬機(jī)實(shí)例的分配數(shù)量k_i，i＝1,...,m，

步驟3、定價(jià)和支付：

步驟3.1、定義支付向量P′＝(p′₁,p′₂,...,p′_j,...,p′_n)，其中，p′_j表示降序后的第j個(gè)競(jìng)拍者u′_j所需支付價(jià)格，j＝1,...,n；

定義降序后的第j個(gè)競(jìng)拍者u′_j不分配虛擬機(jī)實(shí)例時(shí)的虛擬機(jī)實(shí)例數(shù)量總和為t；

定義集合{δ′_j,δ′_j+1,...,δ′_k,...,δ′_L}，其中，δ′_k表示當(dāng)降序后的第j個(gè)競(jìng)拍者u′_j缺席的時(shí)候降序后的第k個(gè)競(jìng)拍者u′_k是否被服務(wù)，當(dāng)δ′_k＝1代表被服務(wù)，當(dāng)δ′_k＝0代表未被服務(wù)；

定義集合{λ′_j,λ′_j+1,...,λ′_k...,λ′_L}，其中，λ′_k表示當(dāng)降序后的第j個(gè)競(jìng)拍者u′_j被放在降序后的第k個(gè)競(jìng)拍者u′_k后面時(shí)降序后的第j個(gè)競(jìng)拍者u′_j是否被拒絕，當(dāng)λ′_k＝1代表降序后的第j個(gè)競(jìng)拍者u′_j被拒絕，λ′_k＝0代表降序后的第j個(gè)競(jìng)拍者u′_j未被拒絕；

定義集合{θ′_j,θ′_j+1,...,θ′_k...,θ′_L}，其中，θ′_k表示降序后的第k個(gè)競(jìng)拍者u′_k是否為降序后的第j個(gè)競(jìng)拍者u′_j的臨界競(jìng)拍者，即θ′_k＝1代表降序后的第k個(gè)競(jìng)拍者u′_k是降序后的第j個(gè)競(jìng)拍者u′_j的臨界競(jìng)拍者，θ′_k＝0代表降序后的第k個(gè)競(jìng)拍者u_k′不是降序后的第j個(gè)競(jìng)拍者u′_j的臨界競(jìng)拍者，k＝j(luò),...,L；

初始化P′＝(0,0,...,0,...,0)、s＝0、j＝1；

步驟3.2、將s賦值給t；將{0,0,...,0,...,0}賦值給{δ′_j,δ′_j+1,…,δ′_k,…,δ′_L}；將{0,0,…,0,…,0}賦值給{λ′_j,λ′_j+1,…,λ′_k…,λ′_L}；將{0,0,…,0,...,0}賦值給{θ′_j,θ′_j+1,...,θ′_k...,θ′_L}；將j+1賦值給k；

步驟3.3、從第k個(gè)競(jìng)拍者開始遍歷，并將Cmp₁(M,Add(t,s′_k))賦值給δ′_k；將Add(t,Mul(δ′_k,s′_k))賦值給t；將Cmp₀(Add(t,s′_j),M)賦值給λ′_k；將賦值給θ′_k；將Add(p′_j,Mul(Mul(Mul(x′_j,θ′_k),d′_k),s′_j))賦值給p′_j；其中，Cmp₀表示比較操作，當(dāng)Add(t,s′_j)＞M時(shí)，令Cmp₀(Add(t,s′_j),M)＝1，當(dāng)Add(t,s′_j)≤M時(shí)，令Cmp₀(Add(t,s′_j),M)＝0；

步驟3.4、將k+1賦值給k后，判斷k＞L上是否成立，若成立，則執(zhí)行步驟3.5，否則，返回步驟3.3；

步驟3.5、將Add(s,Mul(x′_j,s′_j))賦值給s，將j+1賦值給j后，判斷j＞L是否成立，若成立，則表示得到降序后的n個(gè)競(jìng)拍者應(yīng)付價(jià)格所組成的支付向量P′＝(p′₁,p′₂,...,p′_j,...,p′_n)；否則，返回步驟3.2執(zhí)行；

步驟4、用排序網(wǎng)絡(luò)將降序后的n個(gè)競(jìng)拍者按身份標(biāo)識(shí)符Id_j增序排序，云拍賣商根據(jù)增序排序后的競(jìng)拍者順序公布對(duì)應(yīng)競(jìng)拍者的分配向量分量x_j′及降序后的應(yīng)付價(jià)格p′_j，j＝1,...,n。

2.根據(jù)權(quán)利要求1所述的動(dòng)態(tài)虛擬機(jī)分配方法，其特征是，加法操作Add、減法操作Sub、乘法操作Mul、除法操作Div、比較操作Cmp₁和Cmp₀以及排序網(wǎng)絡(luò)均是基于域上逐比特的加法和乘法兩個(gè)基本操作來(lái)構(gòu)造的，并定義在域上的任意兩個(gè)一比特位分別為y和z；將比特位y和z分別拆分為兩個(gè)部分的比特位分享值，記為：y₀、y₁和z₀、z₁；且其中，云拍賣商擁有第一部分比特位分享值y₀和z₀，代理服務(wù)提供方擁有第二部分比特位分享值z(mì)₀和z₁；

兩個(gè)所述一比特位y和z的加法基本操作過(guò)程如下：

步驟A1、云拍賣商和代理服務(wù)提供方分別計(jì)算出和其中，g₀和g₁分別為比特位加法值的第一部分和第二部分；

步驟A2、若云拍賣商需要恢復(fù)出結(jié)果時(shí)，所述代理服務(wù)提供方將g₁發(fā)送給云拍賣商，云拍賣商得到g₁后，通過(guò)計(jì)算恢復(fù)出比特位加法的重建值g；

兩個(gè)所述一比特位y和z的乘法基本操作過(guò)程如下：

步驟B1、第三方可信服務(wù)器產(chǎn)生一個(gè)乘法三元組，即(α,β,γ)；其中，α、β分別是在域上隨機(jī)產(chǎn)生的乘法三元組的兩個(gè)比特位，γ是乘法三元組的第三個(gè)比特位，且γ＝α∧β；

步驟B2、所述第三方可信服務(wù)器將乘法三元組的三個(gè)比特位α、β、γ分別拆分為兩個(gè)部分的比特位乘法分享值，記為：α₀、α₁、β₀、β₁和γ₀、γ₁；且

步驟B3、所述第三方可信服務(wù)器將一部分比特位乘法分享值α₀、β₀、γ₀發(fā)送給云拍賣商，將另一部分比特位乘法分享值α₁、β₁、γ₁發(fā)送給代理服務(wù)提供方；

步驟B4、所述云拍賣商和代理服務(wù)提供方分別計(jì)算出和以及和其中，e₀和e₁分別為第一個(gè)比特位乘法中間值的第一部分和第二部分，f₀和f₁分別為第二個(gè)比特位乘法中間值的第一部分和第二部分；

步驟B5、所述云拍賣商和代理服務(wù)提供方分別將e₀和f₀以及e₁和f₁發(fā)送給對(duì)方；

雙方分別計(jì)算和其中，e為比特位乘法的第一個(gè)中間重建值，f為比特位乘法的第二個(gè)中間重建值；

步驟B6、云拍賣商和代理服務(wù)提供方分別計(jì)算出以及其中，h₀和h₁分別為比特位乘法值的第一部分和第二部分；

步驟B7、當(dāng)云拍賣商需要恢復(fù)出結(jié)果時(shí)，所述代理服務(wù)提供方將h₁發(fā)送給云拍賣商，云拍賣商得到h₁后，通過(guò)計(jì)算恢復(fù)出比特位乘法的重建值h。