邊緣計(jì)算系統(tǒng)中資源分配防策略拍賣機(jī)制設(shè)計(jì) *

池來新,楊旭濤,謝 寧,張學(xué)杰

(云南大學(xué)信息學(xué)院，云南 昆明 650000)

1 引言

1.1 問題的提出

云計(jì)算[1]是最近十多年間流行的計(jì)算模式，它將大規(guī)模的計(jì)算資源(CPU、內(nèi)存、磁盤存儲等)集中起來，可以通過通信網(wǎng)絡(luò)方便地為用戶按需提供計(jì)算服務(wù)。但是，隨著物聯(lián)網(wǎng)技術(shù)和移動(dòng)互聯(lián)網(wǎng)的發(fā)展，人們對于計(jì)算任務(wù)的需求更加豐富，云中心數(shù)據(jù)壓力不斷增大，同時(shí)通信網(wǎng)絡(luò)存在延遲性高的特點(diǎn)，傳統(tǒng)的云計(jì)算模式已漸漸不能滿足現(xiàn)今龐大而多樣化的任務(wù)需求，而邊緣計(jì)算[2]的出現(xiàn)則能有效地解決這一問題。

邊緣計(jì)算是傳統(tǒng)云計(jì)算的改進(jìn)計(jì)算模式，它在保留云計(jì)算中心的計(jì)算能力之外又在靠近用戶的網(wǎng)絡(luò)邊緣部署一定量的計(jì)算資源，通過縮短與用戶的物理距離克服了云計(jì)算高延遲的問題，同時(shí)對于時(shí)延要求低的任務(wù)仍可以放在云中心執(zhí)行，數(shù)據(jù)的分流也有效地緩解了傳統(tǒng)云計(jì)算中數(shù)據(jù)中心壓力大的問題。邊緣計(jì)算的資源提供商可以通過虛擬化技術(shù)[3]將各種計(jì)算資源整合在一起，以虛擬機(jī)的形式為用戶提供服務(wù)，提高用戶的體驗(yàn)質(zhì)量，由于邊緣計(jì)算資源提供商的資源容量有限，為了能取得最大利益，邊緣計(jì)算資源提供商需要合理地針對用戶所提交的資源需求和報(bào)價(jià)進(jìn)行資源分配。

目前主要有2種資源分配方式，一種是傳統(tǒng)的分配方式，即由資源提供商設(shè)置好虛擬機(jī)配置和對應(yīng)價(jià)格供用戶進(jìn)行購買使用；另外一種即基于拍賣的方式，由用戶提交資源需求和報(bào)價(jià)來通過競爭使用資源，資源提供商會根據(jù)最大化社會福利(拍賣獲勝用戶的報(bào)價(jià)之和)的目標(biāo)計(jì)算出拍賣獲勝用戶和他們應(yīng)該支付的價(jià)格。基于拍賣的方式使得資源的分配和定價(jià)更加靈活，可以充分利用資源提供商的閑置資源，提高了資源提供商的資源利用率和社會福利。但是，這增加了計(jì)算模型的復(fù)雜性，且難以確定用戶的最終支付價(jià)格；同時(shí)，用戶往往會通過諸如虛報(bào)資源需求和報(bào)價(jià)等策略性行為來用更低的價(jià)格獲取同樣多的資源，或以同樣的價(jià)格獲取更多的資源，這損害了資源提供商的利益。所以，如何設(shè)計(jì)一個(gè)防策略拍賣機(jī)制也是一個(gè)重大挑戰(zhàn)。

1.2 相關(guān)工作

邊緣計(jì)算環(huán)境下的防策略拍賣機(jī)制主要需要解決3個(gè)問題，即資源分配算法的設(shè)計(jì)(拍賣獲勝用戶的確定方法)、用戶支付價(jià)格的確定和防策略拍賣機(jī)制的實(shí)現(xiàn)，下面將在上述3個(gè)方面分別闡述相關(guān)研究工作。

(1)在資源分配算法方面。文獻(xiàn)[4,5]提出了一種在云計(jì)算環(huán)境下針對虛擬機(jī)的組合拍賣機(jī)制，給出了資源分配近似算法，但該算法僅能針對資源類型單一的虛擬機(jī)進(jìn)行分配，且算法僅適用于云環(huán)境。文獻(xiàn)[6]詳細(xì)介紹了移動(dòng)邊緣計(jì)算資源分配中的一些常見策略，主要包括最小化時(shí)延、最小化能耗和最大化收益3種類型。文獻(xiàn)[7]研究了移動(dòng)邊緣環(huán)境下在移動(dòng)蜂窩網(wǎng)絡(luò)中的資源分配算法，但算法未能同時(shí)考慮云端和邊緣端的資源分配。文獻(xiàn)[8]提出了云計(jì)算環(huán)境下的虛擬機(jī)分配貪婪算法并給出了算法近似比，該算法運(yùn)算速度快，且能夠滿足防策略。文獻(xiàn)[9,10]提出了云計(jì)算環(huán)境下支持多需求的資源分配算法，可同時(shí)兼容傳統(tǒng)的單一需求情況。文獻(xiàn)[4,5,8-10]提出的算法均能滿足防策略，可以給邊緣計(jì)算的防策略機(jī)制實(shí)現(xiàn)提供參考。文獻(xiàn)[11]提出了基于改進(jìn)粒子群算法的資源分配策略，能夠在較短時(shí)間內(nèi)取得較好的實(shí)驗(yàn)結(jié)果，但該算法具備一定隨機(jī)性，在拍賣機(jī)制中無法保證防策略。

(2)在支付價(jià)格計(jì)算方面。文獻(xiàn)[12,13]將經(jīng)濟(jì)學(xué)中的VCG(Vickrey-Clarke-Groves)理論用于拍賣機(jī)制中的支付價(jià)格計(jì)算，并給出了大量理論鋪墊。文獻(xiàn)[14]在網(wǎng)格計(jì)算中使用VCG理論進(jìn)行資源定價(jià)，使得資源拍賣機(jī)制實(shí)現(xiàn)了防策略，但通過VCG理論進(jìn)行定價(jià)是一個(gè)NP難問題，計(jì)算時(shí)間耗費(fèi)太大，難以用于實(shí)際場景中。文獻(xiàn)[8]在資源分配算法為滿足單調(diào)性的貪婪法的前提下，提出了基于臨界價(jià)格的支付價(jià)格算法，該支付算法使得拍賣機(jī)制滿足了防策略，同時(shí)計(jì)算速度相比基于VCG理論的支付價(jià)格算法要快。文獻(xiàn)[9，10]采用二分法計(jì)算基于臨界價(jià)格的支付價(jià)格，使得算法性能得到進(jìn)一步提高。

(3)在防策略拍賣機(jī)制設(shè)計(jì)方面。文獻(xiàn)[15]詳細(xì)介紹了防策略拍賣機(jī)制設(shè)計(jì)的相關(guān)原理并對防策略拍賣機(jī)制的實(shí)現(xiàn)給出了理論推導(dǎo)。文獻(xiàn)[8,16]分別提出了在云計(jì)算環(huán)境下基于單調(diào)性和臨界價(jià)格理論的離線和在線2種情況下的防策略拍賣機(jī)制。文獻(xiàn)[17,18]提出了云計(jì)算環(huán)境下資源異構(gòu)時(shí)的防策略拍賣機(jī)制，能解決多服務(wù)器資源分配的問題。文獻(xiàn)[19]提出了在包含多個(gè)資源提供商的情況下的雙向防策略拍賣機(jī)制，在資源提供商合理選擇獲勝用戶的同時(shí)用戶也需合理地選擇資源提供商。文獻(xiàn)[20]提出了移動(dòng)區(qū)塊鏈同邊緣計(jì)算相結(jié)合的最優(yōu)拍賣機(jī)制。文獻(xiàn)[21]提出了一種基于邊緣計(jì)算環(huán)境的無嫉妒拍賣機(jī)制，該機(jī)制可以保證資源分配公平，但無法最大化資源提供商的社會福利。

綜上所述，在資源分配的防策略拍賣機(jī)制的問題上，已有許多積極的研究成果，但當(dāng)前研究在邊緣計(jì)算環(huán)境下的資源分配求解、支付價(jià)格的計(jì)算和防策略拍賣機(jī)制的實(shí)現(xiàn)方面仍存在較大挑戰(zhàn)。在資源分配求解方面，邊緣計(jì)算平臺除了保留有云端的資源服務(wù)器外還增加了邊緣端的資源服務(wù)器，不同的用戶也會對于資源的部署位置有著不同的要求。因此，資源分配算法還需合理地選擇將用戶的資源在云端還是邊緣端進(jìn)行分配，這給資源分配算法的設(shè)計(jì)增加了難度。在支付價(jià)格的計(jì)算方面，傳統(tǒng)基于VCG理論的定價(jià)算法計(jì)算時(shí)間太長，而基于臨界價(jià)格的定價(jià)算法雖能提高計(jì)算速度，但在邊緣計(jì)算環(huán)境下用戶的支付價(jià)格還需考慮用戶的資源部署約束，這成為了邊緣計(jì)算環(huán)境下定價(jià)算法設(shè)計(jì)的一大挑戰(zhàn)。在防策略拍賣機(jī)制設(shè)計(jì)方面，現(xiàn)有研究中均通過單調(diào)性和臨界價(jià)格理論來保證拍賣機(jī)制滿足防策略，但這些研究均要求將云資源抽象為資源池(或一臺服務(wù)器)進(jìn)行資源分配才能滿足單調(diào)性，而邊緣計(jì)算環(huán)境下云端和邊緣端的服務(wù)器具有不同的特性(如時(shí)延、傳輸能耗不同)，無法將兩者進(jìn)行整合，這使得邊緣計(jì)算環(huán)境下拍賣的單調(diào)性難以滿足，這成為了邊緣計(jì)算下的防策略拍賣機(jī)制設(shè)計(jì)中的一大挑戰(zhàn)。

1.3 本文貢獻(xiàn)

本文研究了邊緣計(jì)算環(huán)境下的資源拍賣機(jī)制問題，對邊緣計(jì)算環(huán)境下的資源分配問題進(jìn)行了數(shù)學(xué)建模，提出了最優(yōu)拍賣機(jī)制和貪婪拍賣機(jī)制2種防策略拍賣機(jī)制，可以解決邊緣計(jì)算中的資源分配問題和支付價(jià)格確定問題。其中最優(yōu)拍賣機(jī)制能取得資源分配的最優(yōu)結(jié)果，但由于求解最優(yōu)解需要消耗大量計(jì)算時(shí)間而導(dǎo)致應(yīng)用場景受限，所以還需要提出貪婪拍賣機(jī)制，能夠在較短時(shí)間內(nèi)合理地分配資源，同時(shí)使得資源提供商取得較大社會福利和收益。

本文對提出的算法進(jìn)行了仿真實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果表明本文算法在資源提供商的社會福利、收益、資源利用率和計(jì)算時(shí)間等多方面取得了不錯(cuò)的效果，驗(yàn)證了本文算法的有效性和可行性。

2 問題描述和相關(guān)定義

邊緣計(jì)算系統(tǒng)中包含云端服務(wù)器和邊緣服務(wù)器，通常需要設(shè)置服務(wù)器集群來建立資源池，以實(shí)現(xiàn)資源的虛擬化，云端服務(wù)器集群和邊緣服務(wù)器集群通過建立資源池可抽象為云端和邊緣端的2臺資源服務(wù)器，為用戶提供資源進(jìn)行計(jì)算服務(wù)。用戶可以向邊緣計(jì)算資源提供商提交資源需求和報(bào)價(jià)以申請資源，但因?yàn)樵贫朔?wù)器和邊緣服務(wù)器上的資源有限，無法滿足所有用戶的資源需求，故而邊緣計(jì)算資源提供商需要合理選擇用戶進(jìn)行資源分配，以使得自己的社會福利(拍賣獲勝用戶的報(bào)價(jià)之和)最大化。

云端服務(wù)器部署在資源提供商的數(shù)據(jù)中心，具有較大的資源容量，但由于距離實(shí)際用戶過遠(yuǎn)，所以具有較大時(shí)延，只能滿足時(shí)延敏感性低的用戶需求。邊緣服務(wù)器部署在用戶所在社區(qū)附近的通信基站(網(wǎng)絡(luò)邊緣)，僅為該社區(qū)提供計(jì)算服務(wù)，與用戶距離近，故而擁有較小的時(shí)延，可以滿足時(shí)延敏感性高的用戶需求，同時(shí)也可以為時(shí)延敏感性低的用戶分配資源。將邊緣計(jì)算的資源分配問題刻畫成數(shù)學(xué)模型進(jìn)行描述，需要先對問題中的角色進(jìn)行相關(guān)定義。

根據(jù)上述定義，可將邊緣計(jì)算的資源分配問題定義為如式(1)～式(5)所示的線性整數(shù)規(guī)劃模型：

Maximize:

(1)

Subject to:

(2)

(3)

xi1+xi2≤1,?i∈U

(4)

xi1,xi2∈{0,1},?i∈U

(5)

(6)

在上述線性整數(shù)規(guī)劃模型中，式(1)為目標(biāo)函數(shù)，用于最大化資源提供商的社會福利，其中x為決策變量(如式(6)所示)，xij=1代表用戶i的資源分配在云端服務(wù)器 (j=1) 或邊緣服務(wù)器 (j=2)上，xij=0則代表用戶i的資源在云端服務(wù)器 (j=1) 或邊緣服務(wù)器上 (j=2) 不被分配。式(2)～式(5)為約束條件，其中式(2)保證分配在云端服務(wù)器上的任務(wù)所占用的資源不超過云端服務(wù)器上各類型資源的容量；式(3)保證分配在邊緣服務(wù)器上的任務(wù)所占用的資源不超過邊緣服務(wù)器上各類型資源的容量，式(4)保證用戶的資源需求不可分，即一個(gè)用戶的資源不能同時(shí)部署在云端服務(wù)器和邊緣服務(wù)器上；式(5)限定了決策變量xij僅能取值為1或0，分別代表分配資源和不分配資源。因?yàn)橘Y源種類有多種，部署服務(wù)器也包括云端服務(wù)器和邊緣服務(wù)器2種，同時(shí)帶有資源的服務(wù)器部署約束，所以該問題本質(zhì)上是一個(gè)帶有部署約束的多維多背包問題，是一個(gè)NP難問題[22]。

3 防策略拍賣機(jī)制設(shè)計(jì)

3.1 防策略拍賣機(jī)制設(shè)計(jì)理論

一個(gè)拍賣機(jī)制包含資源分配和定價(jià)2個(gè)階段。在資源分配階段中，所有用戶提交其資源需求和報(bào)價(jià)，用戶的報(bào)價(jià)可以看作是用戶對其提交的資源需求的一個(gè)估值，拍賣機(jī)制根據(jù)資源提供商的資源容量、用戶的資源需求情況和報(bào)價(jià)來合理選擇拍賣獲勝的用戶而對其分配資源，目的是最大化資源提供商的社會福利，其中社會福利為獲勝用戶的報(bào)價(jià)之和。在定價(jià)階段，拍賣機(jī)制需要計(jì)算出獲勝用戶需要最終支付的價(jià)格，形成資源提供商的最終利潤。

在現(xiàn)實(shí)情況中，提交資源需求的用戶都具有利己性[12]，希望以更低的價(jià)格或者低于用戶資源需求估值的價(jià)格來獲取資源，或者以同樣的價(jià)格獲取更多的資源，這些會使得用戶產(chǎn)生策略性行為，提交有利于自己的不真實(shí)的資源需求和報(bào)價(jià)，從而使自己獲利，這會影響到資源提供商的社會福利，因而需要設(shè)計(jì)一個(gè)防策略拍賣機(jī)制。

定義1(用戶效用) 用戶效用用u表示，定義如式(7)所示：

?i:ui=vi-pi

(7)

其中，vi表示用戶i對提交的資源需求的真實(shí)估值，pi為用戶最終需要支付的價(jià)格。用戶效用可以代表用戶對拍賣結(jié)果的滿意程度，從式(7)可以看出，用戶效用越大，代表其最終需支付的價(jià)格愈加低于用戶對資源需求的真實(shí)估值，所以用戶希望最大化其用戶效用。

定義2(個(gè)體理性) 如果在一個(gè)拍賣機(jī)制中，所有用戶的用戶效用均大于或等于0，如式(8)所示，那么這個(gè)拍賣機(jī)制是個(gè)體理性的，個(gè)體理性說明不會產(chǎn)生負(fù)的用戶效用，這可以鼓勵(lì)用戶參與拍賣。

?i:ui=vi-pi≥0

(8)

定義3(防策略) 防策略也可以稱之為可信或激勵(lì)相容，如果一個(gè)拍賣機(jī)制使得用戶提交真實(shí)的信息報(bào)告產(chǎn)生的用戶效用比用戶提交虛假的信息報(bào)告產(chǎn)生的用戶效用更大，如式(9)所示，則這個(gè)拍賣機(jī)制是防策略的。

(9)

防策略是一個(gè)拍賣機(jī)制中的良好性質(zhì)，可以激勵(lì)用戶提交真實(shí)的信息報(bào)告，從而不影響資源提供商的社會福利。

接下來將定義拍賣機(jī)制中資源分配算法的單調(diào)性，定義單調(diào)性之前首先引入用戶信息報(bào)告之間的偏序關(guān)系，當(dāng)時(shí)，即表明信息報(bào)告中的報(bào)價(jià)不小于的報(bào)價(jià)，信息報(bào)告中的每種資源需求量均不大于所對應(yīng)類型資源的需求量，同時(shí)信息報(bào)告中的時(shí)延敏感性值不大于中的時(shí)延敏感性值，如式(10)所示：

(10)

(11)

3.2 最優(yōu)拍賣機(jī)制VMAPEC-OPT

最優(yōu)拍賣機(jī)制VMAPEC-OPT (Virtual Machine Allocation and Pricing for Edge Computing-OPTimal)設(shè)計(jì)分為最優(yōu)資源分配算法和最優(yōu)支付算法2部分。

(12)

(13)

(14)

由文獻(xiàn)[12]可知，當(dāng)一個(gè)拍賣機(jī)制的資源分配結(jié)果是最優(yōu)解的同時(shí)獲勝用戶的支付價(jià)格根據(jù)式(12)計(jì)算時(shí)，則這個(gè)拍賣機(jī)制是滿足防策略的。但是，由于VMAPEC-OPT機(jī)制需要求解線性整數(shù)規(guī)劃模型，這會耗費(fèi)過多計(jì)算時(shí)間，甚至在用戶數(shù)量過大的情況下無法計(jì)算出結(jié)果，使得VMAPEC-OPT機(jī)制在實(shí)際運(yùn)用中受限比較大，因而需要設(shè)計(jì)出計(jì)算速度快同時(shí)實(shí)驗(yàn)效果較好的防策略拍賣機(jī)制。

3.3 貪婪拍賣機(jī)制VMAPEC-G

3.3.1 VMAPEC-G機(jī)制

基于最優(yōu)拍賣機(jī)制VMAPEC-OPT因計(jì)算時(shí)間過長而難以運(yùn)用在實(shí)際場景中的問題，本文提出了貪婪拍賣機(jī)制VMAPEC-G (Virtual Machine Allocation and Pricing for Edge Computing- Greedy)。VMAPEC-G機(jī)制同樣由分配算法和支付算法2部分組成，首先通過調(diào)用資源分配算法VMAPEC-G-A(Virtual Machine Allocation and Pricing for Edge Computing-Greedy-Allocation)計(jì)算出社會福利V和資源分配決策變量x，然后對拍賣獲勝用戶調(diào)用臨界價(jià)格計(jì)算算法VMAPEC-G-P(Virtual Machine Allocation and Pricing for Edge Computing-Greedy-Payment)求取用戶的支付價(jià)格，最后再通過支付價(jià)格計(jì)算資源提供商的最終收益。

3.3.2 單調(diào)資源分配算法

介紹單調(diào)資源分配算法時(shí)需先引入任務(wù)的資源密度，用戶的資源密度定義如式(15)所示，代表資源提供商愿意接受用戶的程度，用戶的資源密度越高時(shí)，算法越傾向于給該用戶分配資源。

(15)

單調(diào)資源分配算法如算法1所示，算法首先需要對所有用戶進(jìn)行用戶密度的非升序排序(第3行)，這可以更加充分地利用服務(wù)器的資源并實(shí)現(xiàn)算法的單調(diào)性；然后依次遍歷用戶并對用戶進(jìn)行資源分配?？紤]到時(shí)延敏感性高的用戶的資源只能分配在邊緣服務(wù)器，故算法對所有用戶優(yōu)先選擇云端服務(wù)器進(jìn)行資源分配(第5行)，這樣可以在提高資源利用率的同時(shí)提高資源提供商的社會福利；而當(dāng)用戶為高時(shí)延敏感性用戶時(shí)，則會直接選擇邊緣端服務(wù)器進(jìn)行分配(第6、7行)。分配資源時(shí)需要判斷服務(wù)器上每種類型資源的剩余容量是否能滿足用戶的需求(第9～15行)，當(dāng)資源容量均能滿足要求時(shí)再進(jìn)行資源分配；同時(shí)需要更新對應(yīng)服務(wù)器的剩余資源容量和當(dāng)前社會福利V以及資源分配決策矩陣x(第16～23行)。為了不對用戶重復(fù)分配資源，算法需要在第22行跳出第5～25行的for循環(huán)。

輸出：社會福利V,資源分配決策變量x。

1.V←0;

2.x←0;

5.forj=1,2do

7. continue;

8.else

9.flag←true;

10.forr=1:Rdo

12.flag←false;

13. break;

14.endif

15.endfor

16.ifflag=truethen

17.forr=1:Rdo

19.endfor

20.V←V+vi;

21.xij← 1;

22.break;

23.endif

24.endif

25.endfor

26.endfor

27.returnV,x.

定理1資源分配算法VMAPEC-G-A滿足單調(diào)性。

(16)

□

3.3.3 基于臨界價(jià)格的支付算法

基于臨界價(jià)格的支付算法如算法2所示，算法需要遍歷所有用戶，通過決策變量x判斷該用戶是否拍賣獲勝(第2行)，僅當(dāng)拍賣獲勝時(shí)才通過二分法進(jìn)行支付價(jià)格的計(jì)算(第7～15行)，否則支付價(jià)格被設(shè)為0(第18行)。二分法由于要不斷修改用戶的報(bào)價(jià)，故需先將用戶的信息報(bào)告暫存起來(第3行)，然后將當(dāng)前報(bào)價(jià)上界和下界之和的一半作為新的報(bào)價(jià)(第6行)，并測試用戶是否還能拍賣獲勝。當(dāng)拍賣仍然獲勝時(shí)，就將當(dāng)前報(bào)價(jià)作為新的上界，否則將其作為新的下界，當(dāng)上下界的差小于一個(gè)給定的足夠小的ε時(shí)，就將支付價(jià)格設(shè)為當(dāng)前修改后的報(bào)價(jià)，其中ε需要小于支付價(jià)格的最小單位。

輸出:支付價(jià)格向量P=[p1,p2,…,pN]。

2.ifxi1=1 orxi2=1

5.lower← 0;

7.whileupper-lower>εdo

9.ifxi1=1 orxi2=1then

11.else

13.endif

15.endwhile

17.else

18.pi← 0;

19.endif

20.endfor

21.ReturnP.

定理2支付算法VMAPEC-G-P是基于臨界價(jià)格進(jìn)行設(shè)計(jì)的。

證明在支付算法中，當(dāng)用戶i為拍賣獲勝用戶時(shí)，通過取支付價(jià)格的上界和下界之和的一半作為當(dāng)前支付價(jià)格，將此支付價(jià)格作為用戶i的報(bào)價(jià)再重新判斷用戶i是否能拍賣獲勝，當(dāng)獲勝時(shí)以當(dāng)前支付價(jià)格作為上界，否則以當(dāng)前支付價(jià)格作為下界。顯然，只要支付價(jià)格上界和下界的差控制在預(yù)設(shè)的數(shù)值ε(ε小于實(shí)際交易的最小計(jì)價(jià)單位)之內(nèi)，即可保證當(dāng)用戶i的報(bào)價(jià)大于此價(jià)格時(shí)就會拍賣獲勝，小于此價(jià)格時(shí)就會拍賣失敗，根據(jù)定義5，此時(shí)的支付價(jià)格即為臨界價(jià)格。

□

定理3VMAPEC-G機(jī)制是防策略的。

證明根據(jù)文獻(xiàn)[12]，只要拍賣機(jī)制的分配算法滿足單調(diào)性，并且拍賣獲勝用戶的支付價(jià)格為臨界價(jià)格，則該拍賣機(jī)制是防策略的，由定理1和定理2可證明VMAPEC-G機(jī)制是防策略的。

□

定理4VMAPEC-G機(jī)制滿足個(gè)體理性。

證明對于任意的用戶i，若用戶i拍賣失敗，根據(jù)支付價(jià)格計(jì)算算法VMAPEC-G-P可知用戶i的支付價(jià)格為0，所以用戶i的用戶效用滿足式(17)：

(17)

(18)

綜上，根據(jù)定義2，拍賣機(jī)制滿足個(gè)體理性。

□

定理5VMAPEC-G機(jī)制滿足多項(xiàng)式時(shí)間復(fù)雜度。

□

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

對于虛擬機(jī)配置，本文使用了Microsoft Azure[24]的實(shí)際虛擬機(jī)配置數(shù)據(jù)，每種虛擬機(jī)包含3種計(jì)算資源(CPU核心、內(nèi)存、磁盤)。用戶對于虛擬機(jī)數(shù)量的需求在[1,10]，用戶的報(bào)價(jià)由式(19)進(jìn)行計(jì)算:

(19)

對于資源提供商，本文設(shè)置它的云端服務(wù)器的CPU、內(nèi)存和磁盤容量分別為2 000核心，10 000 GB和200 000 GB，邊緣服務(wù)器的CPU、內(nèi)存和磁盤容量分別為1 000核心，5 000 GB和100 000 GB。本文按照用戶規(guī)模從小到大分別針對200,500,1 000,5 000,10 000個(gè)用戶需求進(jìn)行測試。

為了體現(xiàn)用戶需求的客觀性，本文在上述實(shí)驗(yàn)配置的基礎(chǔ)上模擬了100組用戶需求，取其實(shí)驗(yàn)結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)還與文獻(xiàn)[8]提出的G-VMPAC-II(Greedy-Virtual Machines Provisioning and Allocation in Clouds-II)機(jī)制進(jìn)行了對比。該機(jī)制是經(jīng)典的資源分配拍賣機(jī)制，能在較短時(shí)間內(nèi)得出不錯(cuò)的實(shí)驗(yàn)結(jié)果，但該機(jī)制沒有考慮邊緣計(jì)算環(huán)境下的資源異構(gòu)情況，同時(shí)還無法在邊緣計(jì)算環(huán)境下滿足防策略。實(shí)驗(yàn)平臺軟硬件配置為Windows10操作系統(tǒng)，Intel i7-8550U CPU, 16 GB內(nèi)存,512 GB固態(tài)硬盤存儲，編程語言為Java。

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

4.2.1 社會福利及資源分配時(shí)間

社會福利是拍賣機(jī)制中獲勝用戶的報(bào)價(jià)總和，社會福利最大化是資源分配的目標(biāo)，同時(shí)資源算法需要合理地將計(jì)算時(shí)間控制在較小范圍內(nèi)，以使算法具備良好的可行性，因此社會福利的結(jié)果與資源分配的時(shí)間可以直接體現(xiàn)出算法的效果。

圖1顯示了本文提出的最優(yōu)拍賣機(jī)制VMAPEC-OPT、貪婪拍賣機(jī)制VMAPEC-G和文獻(xiàn)[9]中G-VMPAC-II機(jī)制的社會福利對比結(jié)果。由圖1可以看出，VMAPEC-OPT機(jī)制總能得到最高的社會福利，因?yàn)閂MAPEC-OPT機(jī)制直接對資源分配的線性整數(shù)規(guī)劃模型進(jìn)行求解，它求出的資源分配結(jié)果是最優(yōu)解；VMAPEC-G機(jī)制的社會福利結(jié)果介于其它2種機(jī)制之間，大約能達(dá)到VMAPEC-OPT機(jī)制的90%以上；而G-VMPAC-II機(jī)制由于未能考慮邊緣計(jì)算環(huán)境下的資源異構(gòu)和部署約束情況，導(dǎo)致結(jié)果比本文提出的2種機(jī)制的結(jié)果差。同時(shí)還可以看出，在用戶數(shù)目為200的時(shí)候，3種機(jī)制的社會福利較為接近，因?yàn)楫?dāng)用戶數(shù)目過少時(shí)，邊緣計(jì)算系統(tǒng)的計(jì)算資源較為充沛，用戶的資源競爭過小，3種機(jī)制的差距難以凸顯。

Figure 1 Comparison results of social welfare圖1 社會福利對比結(jié)果

圖2顯示了3種機(jī)制的資源分配時(shí)間對比結(jié)果，資源分配時(shí)間即社會福利的計(jì)算時(shí)間。由圖2可知，VMAPEC-G和G-VMPAC-II機(jī)制的資源分配時(shí)間相近且均為較低值，而VMAPEC-OPT的資源分配時(shí)間卻遠(yuǎn)高于其它2種機(jī)制，甚至在用戶數(shù)量較少的情況下(200個(gè)用戶)仍需花費(fèi)大量的計(jì)算時(shí)間，這與第3節(jié)的分析一致。資源分配最優(yōu)解的求解為NP難問題，無法在多項(xiàng)式時(shí)間內(nèi)執(zhí)行，這使得VMAPEC-OPT機(jī)制在可行性方面存在較大限制。定理5表明，VMAPEC-G機(jī)制中的資源分配滿足多項(xiàng)式時(shí)間，故而能在較短時(shí)間內(nèi)執(zhí)行，同時(shí)由圖1可知VMAPEC-G能取得不錯(cuò)的社會福利結(jié)果，故而VMAPEC-G具有極強(qiáng)的可行性。

Figure 2 Comparison results of resource allocation time圖2 資源分配時(shí)間對比結(jié)果

4.2.2 收益及收益計(jì)算時(shí)間

收益是拍賣機(jī)制中獲勝用戶的支付價(jià)格的總和，它能代表資源提供商最終的利潤，而支付價(jià)格需要在完成資源分配的前提下再由支付算法計(jì)算得出，因此，收益計(jì)算時(shí)間會大于資源分配時(shí)間。同時(shí)G-VMPAC-II由于在邊緣計(jì)算環(huán)境下無法滿足防策略，故其計(jì)算支付價(jià)格沒有意義。

圖3顯示了VMAPEC-OPT和VMAPEC-G機(jī)制的收益對比結(jié)果，可知在用戶數(shù)量較大(大于500)時(shí)，VMAPEC-OPT會產(chǎn)生更大收益，這與VMAPEC-OPT機(jī)制的資源分配算法是最優(yōu)算法有關(guān)，但VMAPEC-G機(jī)制仍然能達(dá)到最優(yōu)結(jié)果的90%以上；而在用戶量較小(200個(gè)用戶)時(shí)，VMAPEC-G和VMAPEC-OPT的結(jié)果相差不大，因?yàn)檩^小用戶量時(shí)資源競爭也相對較小。

Figure 3 Comparison results of revenue圖3 收益對比結(jié)果

圖4顯示了VMAPEC-OPT和VMAPEC-G機(jī)制的收益計(jì)算對數(shù)時(shí)間對比結(jié)果，可明顯看出VMAPEC-G機(jī)制的收益計(jì)算時(shí)間遠(yuǎn)小于VMAPEC-OPT機(jī)制的，約小于VMAPEC-OPT機(jī)制的1%。因?yàn)橹Ц秲r(jià)格的計(jì)算需要先進(jìn)行資源分配，同時(shí)支付算法還需要不斷迭代計(jì)算資源分配情況，造成收益計(jì)算時(shí)間遠(yuǎn)大于資源分配時(shí)間，相比之下，VMAPEC-OPT機(jī)制的高時(shí)耗的資源分配算法會嚴(yán)重影響收益計(jì)算時(shí)間，這使得VMAPEC-G機(jī)制相比VMAPEC-OPT機(jī)制擁有更好的可行性。

Figure 4 Comparison results of revenue calculation time圖4 收益計(jì)算時(shí)間對比結(jié)果

4.2.3 資源利用率

資源利用率是拍賣獲勝用戶的資源需求總和占資源提供商對應(yīng)類型資源容量總和的百分比，可由資源分配的結(jié)果計(jì)算得出。資源利用率對資源分配算法的衡量具有一定參考。

圖5～圖7分別顯示了3種拍賣機(jī)制的CPU、內(nèi)存和磁盤的利用率。從圖5～圖7可以看出，3種拍賣機(jī)制的資源利用率總體較為接近，表明VMAPEC-G和G-VMPAC-II機(jī)制與最優(yōu)機(jī)制一樣均趨向于使資源耗盡，這表明2種貪婪機(jī)制也能夠比較充分地利用資源。從圖7還可以發(fā)現(xiàn)，3種機(jī)制的磁盤利用率相對較小，但這和各虛擬機(jī)的配置和資源提供商的資源容量配置有關(guān)，這也可以給資源提供商進(jìn)行實(shí)際的資源配置時(shí)提供一定參考。

Figure 5 Comparison results of CPU utilization圖5 CPU利用率對比結(jié)果

Figure 6 Comparison results of memory utilization圖6 內(nèi)存利用率對比結(jié)果

Figure 7 Comparison results of disk utilization圖7 磁盤利用率對比結(jié)果

5 結(jié)束語

本文研究了邊緣計(jì)算環(huán)境下的資源分配問題，并對該問題進(jìn)行了數(shù)學(xué)建模，提出了VMAPEC-OPT和VMAPEC-G 2種拍賣機(jī)制，并從理論上證明了這2種拍賣機(jī)制是防策略的。同時(shí)，通過實(shí)驗(yàn)結(jié)果分析可以看出，VMAPEC-G機(jī)制在社會福利、資源分配時(shí)間、收益、收益計(jì)算時(shí)間和資源利用率等多方面都能取得不錯(cuò)的效果，表明VMAPEC-G機(jī)制在邊緣計(jì)算系統(tǒng)的資源分配問題中具有良好的有效性和可行性。

在下一步工作中，擬考慮用戶資源需求的動(dòng)態(tài)性，引入時(shí)間尺度，用戶的資源需求可以在不同時(shí)刻動(dòng)態(tài)產(chǎn)生，以增強(qiáng)機(jī)制的實(shí)用性。