李穎浩，嵩 天，楊雅婷

北京理工大學(xué)計(jì)算機(jī)學(xué)院，北京100081

近年來，隨著物聯(lián)網(wǎng)、人工智能和虛擬現(xiàn)實(shí)（virtual reality，VR）等技術(shù)的發(fā)展以及可穿戴設(shè)備、智能手機(jī)、平板電腦等終端設(shè)備的普及，諸如智能家居、VR游戲等新興應(yīng)用涌入了人們的生活[1-2]。該類應(yīng)用在運(yùn)行時(shí)，受限于終端設(shè)備的計(jì)算能力以及“Client-Server”應(yīng)用模式，用戶需要向ASP（application service provider）發(fā)送數(shù)據(jù)，請(qǐng)求服務(wù)[3]。對(duì)于應(yīng)用部署方式，傳統(tǒng)的云計(jì)算模式正在遭受挑戰(zhàn)。一方面，帶寬資源消耗迅速增長：根據(jù)思科的年度網(wǎng)絡(luò)報(bào)告[4]預(yù)測，到2023 年，人均持有3.6 臺(tái)聯(lián)網(wǎng)設(shè)備，全球聯(lián)網(wǎng)設(shè)備數(shù)量達(dá)293 億，為滿足應(yīng)用服務(wù)需求，將消耗大量帶寬資源。另一方面，時(shí)延要求不斷提高：對(duì)于遠(yuǎn)程醫(yī)療、自動(dòng)駕駛等實(shí)時(shí)性應(yīng)用，對(duì)低時(shí)延的保障是正常運(yùn)行的必要條件。

與此同時(shí)，邊緣計(jì)算為ASP 部署應(yīng)用服務(wù)提供了新的模式：通過向ECP（edge computing provider）支付費(fèi)用，將應(yīng)用服務(wù)作為計(jì)算任務(wù)卸載到網(wǎng)絡(luò)邊緣，由ECP 代理執(zhí)行，以解決云計(jì)算模式中帶寬消耗嚴(yán)重和響應(yīng)時(shí)延過高等問題[5-6]。邊緣計(jì)算模式將原本云計(jì)算中心的部分或全部計(jì)算任務(wù)卸載到數(shù)據(jù)源的附近執(zhí)行[5]。例如，VR 游戲的ASP 可以將部分應(yīng)用服務(wù)部署到用戶聚集的城市附近，以降低游戲時(shí)延，提升用戶體驗(yàn)，而在目標(biāo)城市區(qū)域，各運(yùn)營商、網(wǎng)絡(luò)設(shè)備制造商、高校等均可作為ECP，利用空閑資源提供計(jì)算服務(wù)[7]。

然而，采用邊緣計(jì)算模式進(jìn)行應(yīng)用服務(wù)部署需要可行的任務(wù)卸載機(jī)制，以解決其中的雙向選擇問題：一方面，ECP 不同于傳統(tǒng)的云計(jì)算提供商，其計(jì)算資源相對(duì)有限，在多任務(wù)場景下，不能確保滿足所有的任務(wù)需求，因此將基于自身資源條件，選擇性接受ASP 所提出的計(jì)算任務(wù)；另一方面，由于各ECP 在資源配置和運(yùn)營管理方面存在差異，針對(duì)相同的計(jì)算任務(wù)可能要求不同的代理費(fèi)用，因此ASP 將基于各ECP 的反饋，選擇各個(gè)任務(wù)的卸載對(duì)象。為了解決這一問題，本文提出了一種面向邊緣計(jì)算的組合拍賣式任務(wù)卸載機(jī)制。

1 相關(guān)工作

在云計(jì)算中，依靠對(duì)資源的統(tǒng)一調(diào)度能力，任務(wù)卸載通常被建模為最優(yōu)化問題，利用線性規(guī)劃、啟發(fā)式算法、機(jī)器學(xué)習(xí)等方法進(jìn)行求解。然而在邊緣計(jì)算中，由于各ECP 缺少統(tǒng)一的管理者，彼此獨(dú)立，因此相應(yīng)的卸載機(jī)制應(yīng)對(duì)ECP 進(jìn)行激勵(lì)并維持公平競爭，而拍賣是實(shí)現(xiàn)這一目標(biāo)的有效途徑。目前，已有相關(guān)工作[8-13]利用拍賣理論對(duì)任務(wù)卸載問題進(jìn)行研究。其中，按照競標(biāo)人的不同，可分為兩類：如果任務(wù)卸載方作為競標(biāo)人，則為正向拍賣；如果計(jì)算服務(wù)提供方作為競標(biāo)人，則為逆向拍賣，也稱為采購拍賣[14]。

文獻(xiàn)[8]考慮了移動(dòng)用戶將計(jì)算任務(wù)卸載到邊緣服務(wù)器的場景。由于邊緣服務(wù)器的資源有限，移動(dòng)用戶需對(duì)所請(qǐng)求資源進(jìn)行競價(jià)，資源以貪心策略分配給競價(jià)高者。文獻(xiàn)[9]在工業(yè)物聯(lián)網(wǎng)的應(yīng)用場景下提出了一種雙向拍賣機(jī)制：終端設(shè)備向邊緣服務(wù)器請(qǐng)求服務(wù)，并進(jìn)行報(bào)價(jià)，同時(shí)邊緣服務(wù)器設(shè)置所要求的服務(wù)價(jià)格，拍賣商基于兩者進(jìn)行匹配。文獻(xiàn)[10]考慮在異構(gòu)網(wǎng)絡(luò)環(huán)境中，移動(dòng)設(shè)備利用閑置資源提供計(jì)算服務(wù)以收取費(fèi)用的場景，并基于逆向拍賣模型建立了一種任務(wù)卸載機(jī)制。其中，移動(dòng)設(shè)備為獲得計(jì)算任務(wù)進(jìn)行競價(jià)，符合任務(wù)資源需求的且競價(jià)最低者贏得拍賣。文獻(xiàn)[11]考慮在D2D 環(huán)境下的內(nèi)容分發(fā)問題：基站作為內(nèi)容源，通過租用通信范圍內(nèi)其他設(shè)備的存儲(chǔ)資源，實(shí)現(xiàn)代理分發(fā)，以節(jié)約運(yùn)營成本。作者提出了一種逆向拍賣機(jī)制，并在考慮設(shè)備網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上建立優(yōu)化模型，進(jìn)而提出一種基于隨機(jī)化的拍賣策略，在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)問題的較優(yōu)解。文獻(xiàn)[12]通過逆向拍賣為移動(dòng)群智感知系統(tǒng)招募成員，執(zhí)行拍賣決策時(shí)，綜合考慮候選人的報(bào)價(jià)和感知能力，以最優(yōu)化系統(tǒng)的運(yùn)營成本。文獻(xiàn)[13]考慮了在移動(dòng)邊緣計(jì)算環(huán)境下，邊緣服務(wù)商作為計(jì)算資源的賣家，移動(dòng)用戶作為買家的情景。作者首先建立了非競爭環(huán)境下的優(yōu)化模型，在此基礎(chǔ)上引入用戶的相互競爭，設(shè)計(jì)了一種多輪正向拍賣機(jī)制，在滿足用戶需求的同時(shí)，最大化邊緣服務(wù)商的收益。

由于一項(xiàng)應(yīng)用服務(wù)需要多種資源的共同支持，在資源受限條件下，不同的ECP 匹配不同的任務(wù)組合。而上述研究工作只考慮了單一類型的資源，忽略了任務(wù)組合的影響，因此無法解決ASP 的任務(wù)卸載問題。本文所提出的方案綜合考慮了計(jì)算、存儲(chǔ)、網(wǎng)絡(luò)等三種資源，并通過組合拍賣為ECP 提供任務(wù)選擇機(jī)制，在優(yōu)化資源利用率的基礎(chǔ)上，最大化ASP收益。需要說明的，文獻(xiàn)[8]中雖然涉及了多種類型的資源，但是通過虛擬機(jī)進(jìn)行了封裝，實(shí)質(zhì)上用戶請(qǐng)求的還是單一資源。表1 展示了本文方案與現(xiàn)有研究工作的對(duì)比情況。

Table 1 Comparison between proposed scheme and related works表1 本文方案與相關(guān)工作對(duì)比

2 系統(tǒng)模型

2.1 計(jì)算任務(wù)

在邊緣計(jì)算模式下，ASP 將所運(yùn)營的應(yīng)用服務(wù)發(fā)布為計(jì)算任務(wù)，通過ECP 在網(wǎng)絡(luò)邊緣進(jìn)行代理。每項(xiàng)應(yīng)用服務(wù)包含多個(gè)獨(dú)立運(yùn)行的服務(wù)功能（service function，SF），以滿足不斷增加的應(yīng)用需求。例如在新興的VR 游戲中，終端玩家通過VR 技術(shù)與環(huán)境進(jìn)行實(shí)時(shí)交互，ASP 不僅需要提供傳統(tǒng)游戲中的聊天、安全認(rèn)證等功能，還需要提供基于地圖的導(dǎo)航功能。同時(shí)，由于邊緣設(shè)備的計(jì)算能力有限，并且相較于數(shù)據(jù)中心可靠性更低，將應(yīng)用服務(wù)拆分為獨(dú)立的服務(wù)功能更有利于卸載執(zhí)行和提高容錯(cuò)性。ASP 的一項(xiàng)應(yīng)用服務(wù)表示如下：

其中，n代表服務(wù)功能的數(shù)目。每個(gè)服務(wù)功能SFi對(duì)應(yīng)一個(gè)計(jì)算任務(wù)，并利用虛擬化技術(shù)打包為鏡像文件進(jìn)行發(fā)布，其中typei表示所采用的虛擬化技術(shù)類型，如KVM、Xen 等虛擬機(jī)技術(shù)[15]或Docker、CoreOS等容器技術(shù)[16]，imgi則表示具體的鏡像文件。Di代表任務(wù)i的資源需求，其中分別代表對(duì)計(jì)算資源、存儲(chǔ)資源和網(wǎng)絡(luò)資源的需求量。不同的任務(wù)對(duì)資源類型的偏好不同，例如聊天服務(wù)對(duì)網(wǎng)絡(luò)資源需求較高，而導(dǎo)航服務(wù)則對(duì)存儲(chǔ)和計(jì)算資源需求較高。任務(wù)的資源需求量由自身的計(jì)算內(nèi)容、所采用的虛擬化技術(shù)、目標(biāo)用戶數(shù)量等多方因素決定，其評(píng)估工作由ASP 完成，并作為任務(wù)的關(guān)聯(lián)信息提供給拍賣商。代表ASP 愿意為SFi向ECP 支付的最高費(fèi)用，滿足為ASP 通過邊緣代理執(zhí)行SFi所獲得的收益，主要由三部分組成：（1）帶寬收益。通過減少與數(shù)據(jù)中心通信的帶寬消耗帶來的收益，用戶數(shù)量與應(yīng)用通信數(shù)據(jù)量的增加將放大該項(xiàng)收益。（2）QoS 收益。通過降低應(yīng)用響應(yīng)時(shí)延，提升用戶體驗(yàn)帶來的收益，各ASP 具有不同的量化指標(biāo)，例如活躍用戶數(shù)、用戶平均使用時(shí)長等。（3）運(yùn)營收益。將服務(wù)功能轉(zhuǎn)移到邊緣計(jì)算，可以減少ASP 在數(shù)據(jù)中心的設(shè)備投入。然而，由此也引入了應(yīng)用管理和安全防護(hù)方面的新的需求，2.4 節(jié)對(duì)此有進(jìn)一步分析。因此，運(yùn)營收益是采取邊緣計(jì)算前后的綜合運(yùn)營成本之差。

2.2 計(jì)算節(jié)點(diǎn)

在邊緣網(wǎng)絡(luò)中，ECP將所擁有的設(shè)備作為計(jì)算節(jié)點(diǎn)（computing node，CN），例如基站、智能網(wǎng)關(guān)、Cloudlet[17]等，為ASP 的應(yīng)用服務(wù)提供代理，以收取費(fèi)用。一個(gè)計(jì)算節(jié)點(diǎn)CNj的信息表示如下：

式中，STypesj表示節(jié)點(diǎn)CNj所支持的虛擬化技術(shù)集合。Rj表示節(jié)點(diǎn)CNj可用的資源信息，其中分別代表可用的計(jì)算資源、存儲(chǔ)資源和網(wǎng)絡(luò)資源。不同的計(jì)算節(jié)點(diǎn)具有不同的資源配置，例如一臺(tái)Cloudlet 比一個(gè)智能網(wǎng)關(guān)具備更多的計(jì)算資源，而后者較前者具備更多的網(wǎng)絡(luò)資源。ECP 接收到計(jì)算任務(wù)后，按照任務(wù)的資源需求選擇合適的計(jì)算節(jié)點(diǎn)進(jìn)行部署。需要說明的是，計(jì)算任務(wù)的資源需求Di與計(jì)算節(jié)點(diǎn)的可用資源Rj均是指在特定虛擬化技術(shù)下的配置信息：Di表示所對(duì)應(yīng)SFi虛擬機(jī)或容器的資源設(shè)置，Rj表示節(jié)點(diǎn)CNj通過相同虛擬化技術(shù)所能提供的資源上限。二者分別由ASP 與ECP 自行評(píng)估，并作為確定信息輔助后續(xù)的組合拍賣。任務(wù)卸載模型如圖1 所示。

2.3 組合拍賣

ASP 發(fā)布計(jì)算任務(wù)后，通過組合拍賣的方式面向各ECP進(jìn)行卸載。其中，拍賣商由可信的第三方機(jī)構(gòu)擔(dān)任，對(duì)ECP提供注冊(cè)接口并向ASP開放拍賣服務(wù)。

Fig.1 Task offloading model圖1 任務(wù)卸載模型

ECP 向拍賣商注冊(cè)時(shí)，需提供所支持的虛擬化技術(shù)類型STypes以及針對(duì)單個(gè)任務(wù)所能提供的資源上限(cmax,smax,bmax)，并在上述信息更新時(shí)，與拍賣商進(jìn)行同步。當(dāng)拍賣商接收到ASP 的拍賣請(qǐng)求時(shí)，首先利用任務(wù)信息和ECP 注冊(cè)信息進(jìn)行任務(wù)劃分，為每項(xiàng)計(jì)算任務(wù)確定候選ECP 集合，具體過程為：對(duì)計(jì)算任務(wù)SFi，遍歷ECP集合，若typei∈STypes，且則將當(dāng)前ECP 加入SFi的候選ECP集合。

組合拍賣的主要流程如下：

（1）拍賣商接收ASP 的拍賣請(qǐng)求；

（2）進(jìn)行任務(wù)劃分；

（3）拍賣商將未卸載的任務(wù)信息(typei,Di)發(fā)布給對(duì)應(yīng)的候選ECP；

（4）ECP 進(jìn)行投標(biāo)；

（5）拍賣商確定本輪獲勝者與成交價(jià)；

（6）重復(fù)（3）至（6），直至任務(wù)卸載完畢或無ECP參與投標(biāo)。

各ECP 在接收到可選任務(wù)的信息后，根據(jù)自身的計(jì)算節(jié)點(diǎn)配置進(jìn)行投標(biāo)：

式中，θj代表ECPj的投標(biāo)，包括兩個(gè)部分：任務(wù)組合Aj與競價(jià)bj。Aj是所發(fā)布計(jì)算任務(wù)的子集，代表ECPj接受卸載的任務(wù)集合。bj代表ECPj執(zhí)行這些計(jì)算任務(wù)所要求的最低報(bào)酬，滿足bj≥cj，cj代表運(yùn)行成本。由于一輪的投標(biāo)結(jié)果不能確保覆蓋所有計(jì)算任務(wù)，因此拍賣采用多輪循環(huán)的方式進(jìn)行。在每輪拍賣中，拍賣商按照拍賣算法決定本輪的獲勝者及相應(yīng)的成交價(jià)p。若ECPj贏得拍賣，則拍賣商將Aj所包含的計(jì)算任務(wù)分配給它，并且ASP 向其支付報(bào)酬p。由此計(jì)算ASP 和ECPj的收益分別為：

此時(shí)，vi表示為ASP 維持相同用戶規(guī)模和QoS 水平下，邊緣計(jì)算相較于傳統(tǒng)部署模式所減少的費(fèi)用，cj表示為ECP 執(zhí)行計(jì)算任務(wù)所需要的費(fèi)用。vi、cj與所支付報(bào)酬p的結(jié)算方式保持一致，并取決于拍賣商。當(dāng)拍賣商對(duì)所有ECP 都是可信任的，且自身具備足夠的資源條件，可作為第三方提供電子貨幣（法定貨幣）的結(jié)算服務(wù)。然而在分布式環(huán)境下，拍賣商很難滿足上述條件。此時(shí)，基于區(qū)塊鏈技術(shù)的虛擬貨幣可以作為一種解決方案，它利用分布式賬本取代中心化的結(jié)算機(jī)構(gòu)，從而降低了對(duì)拍賣商的要求。

2.4 模型分析

在所提出的任務(wù)卸載模型中，涉及三種角色：ASP、ECP 與拍賣商。每種角色都需要滿足特定的條件，才能維持系統(tǒng)的正常運(yùn)行。本節(jié)對(duì)所提出模型的適用條件與具體實(shí)現(xiàn)中的重點(diǎn)問題進(jìn)行分析，并給出相應(yīng)的支撐技術(shù)方向。

ASP 將計(jì)算任務(wù)卸載到邊緣網(wǎng)絡(luò)，在靠近用戶的區(qū)域?qū)?yīng)用請(qǐng)求進(jìn)行預(yù)處理或直接響應(yīng)，可以減少數(shù)據(jù)回傳帶來的帶寬消耗，并降低應(yīng)用的響應(yīng)時(shí)延，提升用戶體驗(yàn)。由此可見，適用于該模型的應(yīng)用須具備數(shù)據(jù)量大或時(shí)延敏感的特點(diǎn)，同時(shí)需要大量用戶帶來規(guī)模效應(yīng)，以激勵(lì)A(yù)SP 對(duì)應(yīng)用部署方式進(jìn)行重構(gòu)。此外，在實(shí)際執(zhí)行過程中，ASP 還需解決兩方面的技術(shù)問題：一方面是任務(wù)卸載帶來的應(yīng)用管理問題，涉及服務(wù)拆分、數(shù)據(jù)同步、容錯(cuò)設(shè)計(jì)等，分布式系統(tǒng)領(lǐng)域的相關(guān)研究[18-19]能夠提供幫助；另一方面是邊緣計(jì)算帶來的安全性問題，主要是如何在ECP 代理執(zhí)行計(jì)算任務(wù)的情況下保障數(shù)據(jù)隱私安全，同態(tài)加密[20]、差分隱私保護(hù)[21]等安全研究有助于這一目標(biāo)的實(shí)現(xiàn)。

ECP 基于合理的競價(jià)策略，可以利用空閑的系統(tǒng)資源換取收益。然而，成為ECP 需要具備一定的條件：一方面，由于所提供的邊緣計(jì)算服務(wù)面向企業(yè)級(jí)的ASP 用戶，因此所具備的計(jì)算資源必須達(dá)到一定規(guī)模以匹配任務(wù)需求；另一方面，計(jì)算資源要保證長期可用，以確保邊緣計(jì)算服務(wù)的穩(wěn)定。因此ECP 的角色應(yīng)由大型機(jī)構(gòu)或?qū)I(yè)公司擔(dān)任。與ASP 一樣，ECP 也面臨著安全性挑戰(zhàn)：既需要保障所承擔(dān)計(jì)算任務(wù)的安全執(zhí)行，防止外來入侵，同時(shí)需要防范攻擊者偽裝成ASP，利用惡意的任務(wù)代碼進(jìn)行內(nèi)網(wǎng)滲透。相關(guān)的安全研究有沙盒、入侵檢測等。

拍賣商作為任務(wù)卸載的中樞，是模型實(shí)現(xiàn)的關(guān)鍵。面向ASP，拍賣商代表區(qū)域內(nèi)的所有ECP 提供服務(wù)；面向ECP，拍賣商組織競價(jià)并確定優(yōu)勝者。拍賣商必須取得所有ECP 的認(rèn)可，以保障任務(wù)卸載的公平進(jìn)行。具體而言，拍賣商需履行以下職責(zé)：（1）對(duì)于滿足任務(wù)需求的ECP，平等發(fā)布任務(wù)信息，提供公平競爭機(jī)會(huì)；（2）按照既定拍賣算法，公正執(zhí)行勝者裁決和價(jià)格計(jì)算；（3）維護(hù)合約，依據(jù)任務(wù)完成情況進(jìn)行結(jié)算。然而，各ECP 屬于不同的機(jī)構(gòu)，選擇一個(gè)共同信任的第三方作為拍賣商十分困難。拍賣商的確立本質(zhì)上是要在不可信的分布式環(huán)境中構(gòu)建共識(shí)機(jī)制。針對(duì)這一問題，區(qū)塊鏈技術(shù)[22]提供了有效的解決思路。同一區(qū)域內(nèi)的所有ECP 可以共同構(gòu)建聯(lián)盟鏈，如HyperledgerFabric[23]，然后通過選舉產(chǎn)生拍賣商，并將拍賣算法寫入配置規(guī)則。每次拍賣的信息，包括任務(wù)信息、競價(jià)信息、拍賣結(jié)果等作為交易記錄寫入?yún)^(qū)塊鏈賬本。在此過程中，可以利用共識(shí)算法確保任務(wù)信息向合格的ECP 平等發(fā)布，并對(duì)拍賣結(jié)果進(jìn)行審查。此外，基于ChainCode構(gòu)建智能合約[23]，能夠?qū)崿F(xiàn)合約的自動(dòng)結(jié)算。

為了方便起見，將本節(jié)內(nèi)容總結(jié)為表2。

Table 2 Model analysis表2 模型分析

需要說明的是，本文重點(diǎn)在于對(duì)任務(wù)卸載模型的設(shè)計(jì)，以及對(duì)其中ECP 投標(biāo)決策的分析和拍賣算法設(shè)計(jì)。對(duì)于模型的落地實(shí)現(xiàn)，本節(jié)分析了其中的重點(diǎn)問題并給出相關(guān)的支撐技術(shù)方向，具體解決方案將在未來的工作中進(jìn)行研究。

3 ECP 投標(biāo)決策

3.1 決策分析

ECP 參與拍賣時(shí)，從發(fā)布的計(jì)算任務(wù)中選擇任務(wù)組合進(jìn)行投標(biāo)。由于計(jì)算節(jié)點(diǎn)的資源有限，任務(wù)組合的選擇一方面需要符合資源限制，另一方面要最大化資源利用率，使ECP 在后續(xù)拍賣中能接收盡可能多的計(jì)算任務(wù)。而在已知當(dāng)前各個(gè)任務(wù)資源需求的情況下，ECP 應(yīng)在所擁有計(jì)算節(jié)點(diǎn)上執(zhí)行模擬部署，基于部署結(jié)果選擇任務(wù)組合。

設(shè)一輪拍賣中各計(jì)算任務(wù)的資源需求分別為{D1,D2,…,Dn}，一個(gè)ECP 所擁有計(jì)算節(jié)點(diǎn)的資源信息分別為{R1,R2,…,Rm}，并使用變量xij表示部署結(jié)果：當(dāng)任務(wù)SFi部署在節(jié)點(diǎn)CNj上時(shí)，xij=1，否則xij=0，則ECP 對(duì)計(jì)算任務(wù)的模擬部署問題（以下簡稱ECP部署問題）可表示為如下最優(yōu)化問題：

式（9）為優(yōu)化目標(biāo)：對(duì)任務(wù)部署所覆蓋的計(jì)算節(jié)點(diǎn)，最大化各項(xiàng)資源的利用率之和，其中表示節(jié)點(diǎn)j是否參與了任務(wù)部署，若值為1，則有計(jì)算任務(wù)部署在其上；若值為0，則節(jié)點(diǎn)j未被使用，計(jì)算資源利用率時(shí)不予考慮。式（11）表示一項(xiàng)計(jì)算任務(wù)只能被部署到一個(gè)計(jì)算節(jié)點(diǎn)。式（12）表示計(jì)算任務(wù)的資源需求總和不能超過所在計(jì)算節(jié)點(diǎn)的可用資源。

在解決ECP 部署問題的基礎(chǔ)上，可通過如下公式獲得投標(biāo)的任務(wù)組合：

接下來證明ECP 部署問題是一個(gè)NP 完全問題。

定理1ECP 部署問題是NP 完全問題

證明將裝箱問題歸約為ECP 部署問題：

設(shè)在裝箱問題中：物品的數(shù)量為k，物品的重量分別為wi,i=1,2,…,k，箱子的承重量為V，所求箱子的最小使用個(gè)數(shù)為y。

（1）裝箱問題的輸入可轉(zhuǎn)化為ECP 部署問題的輸入

令計(jì)算任務(wù)和計(jì)算節(jié)點(diǎn)的數(shù)量分別等于物品的數(shù)量n=m=k；令計(jì)算任務(wù)的資源需求分別等于物品的重量；令計(jì)算節(jié)點(diǎn)的可用資源分別等于箱子的承重量

（2）ECP部署問題的輸出可轉(zhuǎn)化為裝箱問題的輸出

由裝箱問題的定義知：V≥wi，因此k個(gè)計(jì)算節(jié)點(diǎn)足以部署k個(gè)計(jì)算任務(wù)。又因?yàn)楦鱾€(gè)計(jì)算節(jié)點(diǎn)的資源配置相同，所以最大化資源利用率的部署方案即占用節(jié)點(diǎn)數(shù)量最少的方案，節(jié)點(diǎn)數(shù)量即為裝箱問題的解：

綜上所述，可知裝箱問題能夠歸約為ECP 部署問題。因?yàn)檠b箱問題是NP 完全問題[24]，所以ECP 部署問題是NP 完全問題，證明完畢。

3.2 任務(wù)選擇算法

本節(jié)提出一種基于三維背包的貪心算法，用于ECP 選擇投標(biāo)的任務(wù)組合。該算法基于如下啟發(fā)式規(guī)則：每輪拍賣，ECP 僅為一個(gè)計(jì)算節(jié)點(diǎn)選擇計(jì)算任務(wù)，以最大化該節(jié)點(diǎn)的資源利用率，進(jìn)而在多輪拍賣中提升整體的資源利用率。具體地，該算法將計(jì)算節(jié)點(diǎn)作為背包，計(jì)算任務(wù)作為物品，節(jié)點(diǎn)的資源利用率作為背包的價(jià)值。在此基礎(chǔ)上，對(duì)每個(gè)計(jì)算節(jié)點(diǎn)執(zhí)行背包算法，然后選擇資源利用率最高的節(jié)點(diǎn)，輸出其中部署的計(jì)算任務(wù)。算法具體描述如下：

算法1任務(wù)選擇算法

算法2三維背包算法

dp(c,s,b)表示當(dāng)前計(jì)算節(jié)點(diǎn)在提供計(jì)算資源c、存儲(chǔ)資源s、網(wǎng)絡(luò)資源b的情況下，通過對(duì)計(jì)算任務(wù)進(jìn)行選擇，所能達(dá)到的最大平均資源利用率。算法執(zhí)行過程為：針對(duì)每項(xiàng)任務(wù)i（步驟2），在保障任務(wù)資源需求的前提下，遞減c、s、b的值（步驟3～5）。對(duì)于每組取值，若不選擇當(dāng)前任務(wù)，則資源利用率保持不變，即dp(c,s,b)；若選擇當(dāng)前任務(wù)，剩余資源所提供的資源利用率為該任務(wù)帶來的資源利用率為兩者之和為此時(shí)的資源利用率。比較二者，選擇較大值更新dp(c,s,b)（步驟6）。完成對(duì)所有任務(wù)的選擇后即為最終結(jié)果。

4 拍賣算法

4.1 算法設(shè)計(jì)

首先，定義ECPj的單位競價(jià)為：

式中，代表ECPj對(duì)單位資源的最低收費(fèi)，的值越低，ECPj在拍賣中的競爭力越強(qiáng)。拍賣商在收到所有ECP 的投標(biāo)后，按單位競價(jià)對(duì)其進(jìn)行升序排列，得到候選隊(duì)列＜θ1,θ2,…,θm＞。投標(biāo)的競價(jià)必須滿足價(jià)格限制表示ASP 愿意為Aj所代表的任務(wù)集合支付的最高費(fèi)用。

基于每輪拍賣所決出的勝者數(shù)劃分，本文設(shè)計(jì)了兩種拍賣算法：單勝者算法與多勝者算法。每種算法均包括判定勝者和確定價(jià)格兩個(gè)階段：

判定勝者：單勝者算法將首個(gè)滿足價(jià)格限制的投標(biāo)作為該輪拍賣的唯一勝者；多勝者算法首先定義兩個(gè)集合，勝者集合與已分配任務(wù)集合，并分別初始化為空，然后遍歷候選隊(duì)列，若當(dāng)前投標(biāo)滿足價(jià)格限制，并且其任務(wù)組合不包含已分配的計(jì)算任務(wù)，則將其加入勝者集合，同時(shí)將其任務(wù)組合加入已分配任務(wù)集合。

確定價(jià)格：兩種拍賣算法均要求ECP 以任務(wù)組合的真實(shí)成本進(jìn)行競價(jià)，即bj=cj，并按如下公式確定成交價(jià)p：

其中，表示在候選隊(duì)列中，位于獲勝者之后一項(xiàng)投標(biāo)的單位競價(jià)，將其作為標(biāo)準(zhǔn)單價(jià)，根據(jù)獲勝者的任務(wù)組合Aj所需資源，計(jì)算標(biāo)準(zhǔn)價(jià)格p*并與比較，選擇較低者作為成交價(jià)。若獲勝者位于候選隊(duì)列尾部，則成交價(jià)等于。

每輪拍賣中，兩種算法的具體描述如下：

算法3單勝者拍賣算法

算法4多勝者拍賣算法

4.2 算法分析

本節(jié)對(duì)所提出的兩種拍賣算法進(jìn)行分析，包括拍賣的個(gè)體理性、激勵(lì)相容性[15]以及各自的適用場景。

定義1（個(gè)體理性）如果ASP 與ECP 參與拍賣所獲得的收益均不為負(fù)，則該拍賣是個(gè)體理性的。

定理2采用單勝者算法和多勝者算法的拍賣均是個(gè)體理性的。

證明分別證明ASP 與ECP 的收益不為負(fù)：

（1）UASP≥0

ASP 的收益等于每輪拍賣所帶來的收益之和，由式可得：

對(duì)任意ECPj，其收益等于每次投標(biāo)的收益之和，若競標(biāo)失敗若競標(biāo)成功此時(shí)可分為兩種情況：

①當(dāng)p=p*，由式可得：

以上證明過程同時(shí)適用于單勝者和多勝者算法，因此采用兩種算法的拍賣都是個(gè)體理性的。

定義2（激勵(lì)相容）在一輪拍賣中，設(shè)ECP 以真實(shí)成本競價(jià)(b=c)所獲得的收益為u1，以其他價(jià)格(b′≠c)競價(jià)所獲得的收益為u2。若u1≥u2成立，即ECP 以真實(shí)成本競價(jià)能獲得不低于其他競價(jià)策略的收益，則該拍賣是激勵(lì)相容的。

定理3采用單勝者算法的拍賣是激勵(lì)相容的。

證明當(dāng)各ECP 以真實(shí)成本進(jìn)行競價(jià)，假設(shè)獲勝者為θj，候選隊(duì)列中滿足價(jià)格限制的下一個(gè)投標(biāo)為θk(k＞j)。

對(duì)于獲勝者θj，若改變競價(jià)后，則仍贏得該輪拍賣，由式可知u1=u2；若，則輸?shù)粼撦喤馁u，u1≥u2=0。

對(duì)于失敗者θk，若改變競價(jià)后，則仍輸?shù)粼撦喤馁u，u1=u2=0；若，則贏得該輪拍賣，θj與θk在候選隊(duì)列中的順序調(diào)換，由式可得：

綜上所述，對(duì)拍賣的獲勝者和失敗者，均滿足u1≥u2，因此在采用單勝者算法時(shí)，拍賣是激勵(lì)相容的。

然而，采用多勝者算法的拍賣不是激勵(lì)相容的。假設(shè)各ECP 以真實(shí)成本競價(jià)，得到候選隊(duì)列＜θ1,θ2,θ3,…,＞，且θ1、θ2、θ3均為該輪拍賣的獲勝者。對(duì)于θ1，成交價(jià)為：

若該ECP 提高競價(jià)，使得候選隊(duì)列的排序結(jié)果為＜θ2,θ1,θ3,…,＞，θ1仍作為獲勝者，新的成交價(jià)為：

本文提出的兩種拍賣算法適用于不同的場景。對(duì)于拍賣商，如果注冊(cè)的ECP 集合流動(dòng)性較高，其所能掌握的信息有限，導(dǎo)致投標(biāo)的整體可信度（以真實(shí)成本競價(jià)）較低時(shí)，應(yīng)采用單勝者算法，以利用激勵(lì)相容的特性約束ECP，保障拍賣正常進(jìn)行。如果注冊(cè)的ECP 集合相對(duì)穩(wěn)定，且拍賣商有能力基于歷史行為對(duì)ECP 的投標(biāo)進(jìn)行監(jiān)督，保證其競價(jià)可信度，此時(shí)可采用多勝者算法。由于每輪可以拍賣多組計(jì)算任務(wù)，多勝者算法能夠減少拍賣的輪數(shù)，提高拍賣效率，同時(shí)降低ECP 與拍賣商之間的通信消耗。單勝者算法注重拍賣的誠實(shí)性，多勝者算法注重拍賣的高效性。

5 實(shí)驗(yàn)分析

本章采用模擬實(shí)驗(yàn)的方式，研究所提方案的性能。實(shí)驗(yàn)中，隨機(jī)生成ASP 請(qǐng)求流與ECP 計(jì)算節(jié)點(diǎn)，單個(gè)ASP 請(qǐng)求的任務(wù)數(shù)n=10，單個(gè)ECP 的計(jì)算節(jié)點(diǎn)數(shù)m=4，計(jì)算任務(wù)的資源需求與計(jì)算節(jié)點(diǎn)的初始資源設(shè)置如表3 所示。除本文所提出的兩種拍賣算法外，實(shí)現(xiàn)以下算法作為對(duì)比：

（1）順序分配：在滿足資源需求的條件下，將計(jì)算任務(wù)依次分配給各個(gè)ECP，并按固定資源單價(jià)計(jì)算報(bào)酬。

（2）單項(xiàng)拍賣：每輪拍賣一項(xiàng)計(jì)算任務(wù)，競價(jià)最低的ECP 獲勝，ASP 按第二低的競價(jià)支付報(bào)酬[11]。

Table 3 Setup of computing task and computing node表3 計(jì)算任務(wù)與計(jì)算節(jié)點(diǎn)資源參數(shù)

實(shí)驗(yàn)中，首先比較4 種算法對(duì)ECP 資源的利用率，然后以順序分配結(jié)果作為基準(zhǔn)，對(duì)比單項(xiàng)拍賣與組合拍賣的收益情況，最后在ECP 真實(shí)競價(jià)的前提下，分析單勝者算法和多勝者算法在拍賣效率上的差異和影響因素。

5.1 資源利用率

圖2 展示了ECP 數(shù)量為10 時(shí)，任務(wù)數(shù)量從0 增加到100，計(jì)算、存儲(chǔ)、網(wǎng)絡(luò)3 類資源的平均利用率（以下簡稱利用率）變化情況。利用率越高，說明ECP 獲得越多的計(jì)算任務(wù)。由圖可知，當(dāng)任務(wù)數(shù)量不超過50時(shí)，4 種算法的效果相同，利用率均近似線性增長。這是因?yàn)樵撾A段ECP 資源相對(duì)充足，任務(wù)均成功卸載。當(dāng)任務(wù)數(shù)量超過50，有限的資源無法滿足所有的任務(wù)需求，各算法的卸載結(jié)果出現(xiàn)差異，利用率的增長也隨之不同：順序分配在80 任務(wù)數(shù)時(shí)達(dá)到最大值49.6%，單項(xiàng)拍賣、單勝者拍賣和多勝者拍賣均在90 任務(wù)數(shù)時(shí)達(dá)到最大值，分別為59.3%、68.6%、67.2%，說明在資源受限的情況下，本文算法能夠有效提高ECP 的資源利用率。

Fig.2 Average resource utilization under different number of tasks when ECP count is 10圖2 不同任務(wù)數(shù)下的平均資源利用率（ECP 數(shù)量=10）

圖3 展示了任務(wù)數(shù)量為100 時(shí)，ECP 數(shù)量從1 增加到10，4 種算法的利用率情況。由圖可知，在不同的ECP 數(shù)量下，所提出的兩種算法利用率相近，且均優(yōu)于單項(xiàng)拍賣和順序分配的結(jié)果。

Fig.3 Average resource utilization under different number of ECP when task count is 100圖3 不同ECP 數(shù)量下的平均資源利用率（任務(wù)數(shù)=100）

上述兩個(gè)實(shí)驗(yàn)說明，相較于對(duì)比算法，本文所提方案能高效利用ECP 資源，并且能適應(yīng)不同的任務(wù)數(shù)量和ECP 規(guī)模。

5.2 ASP 收益

在確定ASP 所支付的費(fèi)用時(shí)，順序分配按照固定單價(jià)進(jìn)行計(jì)算，而其余3 種算法則基于拍賣的競價(jià)結(jié)果。因此將順序分配的結(jié)果作為基準(zhǔn)，比較各拍賣算法的收益情況。

圖4 表示任務(wù)數(shù)量為100 時(shí)，ECP 數(shù)量從1 增加到10，3 種拍賣算法的ASP 收益與順序分配下的ASP收益之比。由圖可知，隨著ECP 數(shù)量的增加，ASP 收益比隨之增加。這是因?yàn)镋CP 越多，競爭越激烈，進(jìn)而降低了ASP 所支付的費(fèi)用。當(dāng)ECP 數(shù)量大于1 時(shí)，所提出的兩種拍賣算法的ASP 收益優(yōu)于順序分配；當(dāng)ECP 數(shù)量大于3 時(shí)，單項(xiàng)拍賣的ASP 收益優(yōu)于順序分配。進(jìn)一步比較3 種拍賣算法可知，所提出的兩種算法在不同的ECP 數(shù)量下均優(yōu)于單項(xiàng)拍賣。這是因?yàn)樵趩雾?xiàng)拍賣中，ECP 只能對(duì)單個(gè)任務(wù)進(jìn)行競價(jià)，各個(gè)任務(wù)的拍賣彼此獨(dú)立，而在組合拍賣中，ECP 基于自身資源從同一個(gè)ASP 發(fā)布的多個(gè)任務(wù)中選擇投標(biāo)組合，后者為ECP 提供了更多的任務(wù)信息和投標(biāo)選擇，使得拍賣競爭更為充分。

Fig.4 ASP utility under different number of ECP when task count is 100圖4 不同ECP 數(shù)量下的ASP 收益（任務(wù)數(shù)=100）

圖5 展示了相同設(shè)置下，ASP 收益與ECP 收益之和，即社會(huì)效益隨ECP 數(shù)量變化的情況。其中單項(xiàng)拍賣的社會(huì)效益比穩(wěn)定在1.2 左右，所提出的兩種算法的社會(huì)效益比穩(wěn)定在1.4 左右，均優(yōu)于順序分配的結(jié)果。這是因?yàn)榕馁u機(jī)制能增加成功卸載的任務(wù)數(shù)量，進(jìn)而提高社會(huì)效益。

Fig.5 Social welfare under different number of ECP when task count is 100圖5 不同ECP 數(shù)量下的社會(huì)效益（任務(wù)數(shù)=100）

上述兩個(gè)實(shí)驗(yàn)說明，本文方案能有效增加ASP收益，同時(shí)提高整體的社會(huì)效益，并且效果優(yōu)于單項(xiàng)拍賣機(jī)制。

5.3 拍賣效率

圖6 展示了在任務(wù)數(shù)量為100 時(shí)，ECP 數(shù)量從1增加到10，拍賣輪數(shù)的變化情況。ECP 數(shù)量的增加，表示更多的資源可供使用，因此拍賣輪數(shù)隨之增加。單勝者拍賣比多勝者拍賣需要更多的拍賣輪數(shù)，這種差異在整體上隨ECP 數(shù)量的增加而增加。當(dāng)ECP 數(shù)量為10 時(shí)，單勝者拍賣的輪數(shù)約為多勝者拍賣的1.4 倍。

Fig.6 Auction rounds under different number of ECP when task count is 100圖6 不同ECP 數(shù)量下的拍賣輪數(shù)（任務(wù)數(shù)=100）

圖7 展示了在任務(wù)數(shù)量為100，ECP 數(shù)量為10 的情況下，改變單個(gè)ASP 的任務(wù)數(shù)n對(duì)拍賣輪數(shù)的影響。n的增加，表示每輪拍賣的初始任務(wù)數(shù)量增加，因此拍賣輪數(shù)隨之減少，而多勝者拍賣的效率優(yōu)勢隨之放大。

Fig.7 Auction rounds under different number of single ASP tasks圖7 不同單一ASP 任務(wù)數(shù)下的拍賣輪數(shù)

上述兩個(gè)實(shí)驗(yàn)說明，參與拍賣的ECP 數(shù)量越多，或單個(gè)ASP 的任務(wù)數(shù)越多，多勝者拍賣越能發(fā)揮其效率優(yōu)勢。

6 總結(jié)

本文提出了一種面向邊緣計(jì)算的組合拍賣式任務(wù)卸載機(jī)制，解決了ECP 的投標(biāo)決策問題以及ASP 對(duì)ECP 服務(wù)的選擇問題。本文首先建立了任務(wù)卸載的系統(tǒng)模型，然后分析了ECP 的投標(biāo)決策過程，并設(shè)計(jì)了一種啟發(fā)式的任務(wù)選擇算法，之后針對(duì)不同的應(yīng)用場景，提出了兩種拍賣算法：單勝者拍賣和多勝者拍賣。最后通過模擬實(shí)驗(yàn)與已有方案進(jìn)行對(duì)比，結(jié)果表明本文方案能有效提高ECP 的資源利用率，同時(shí)增加ASP 的拍賣收益，實(shí)現(xiàn)雙方共贏。