面向邊緣計算的組合拍賣式任務(wù)卸載機(jī)制

李穎浩，嵩 天，楊雅婷

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 系統(tǒng)模型

2.1 計算任務(wù)

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

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

2.2 計算節(jié)點

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

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

2.3 組合拍賣

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

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

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

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

（1）拍賣商接收ASP 的拍賣請求；

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

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

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

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

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

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

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

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

2.4 模型分析

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

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

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

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

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

Table 2 Model analysis表2 模型分析

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

3 ECP 投標(biāo)決策

3.1 決策分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 任務(wù)選擇算法

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

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

算法2三維背包算法

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

4 拍賣算法

4.1 算法設(shè)計

首先，定義ECPj的單位競價為：

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

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

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

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

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

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

算法3單勝者拍賣算法

算法4多勝者拍賣算法

4.2 算法分析

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

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

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

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

（1）UASP≥0

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗分析

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

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

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

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

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

5.1 資源利用率

圖2 展示了ECP 數(shù)量為10 時，任務(wù)數(shù)量從0 增加到100，計算、存儲、網(wǎng)絡(luò)3 類資源的平均利用率（以下簡稱利用率）變化情況。利用率越高，說明ECP 獲得越多的計算任務(wù)。由圖可知，當(dāng)任務(wù)數(shù)量不超過50時，4 種算法的效果相同，利用率均近似線性增長。這是因為該階段ECP 資源相對充足，任務(wù)均成功卸載。當(dāng)任務(wù)數(shù)量超過50，有限的資源無法滿足所有的任務(wù)需求，各算法的卸載結(jié)果出現(xiàn)差異，利用率的增長也隨之不同：順序分配在80 任務(wù)數(shù)時達(dá)到最大值49.6%，單項拍賣、單勝者拍賣和多勝者拍賣均在90 任務(wù)數(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 時，ECP 數(shù)量從1 增加到10，4 種算法的利用率情況。由圖可知，在不同的ECP 數(shù)量下，所提出的兩種算法利用率相近，且均優(yōu)于單項拍賣和順序分配的結(jié)果。

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

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

5.2 ASP 收益

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

圖4 表示任務(wù)數(shù)量為100 時，ECP 數(shù)量從1 增加到10，3 種拍賣算法的ASP 收益與順序分配下的ASP收益之比。由圖可知，隨著ECP 數(shù)量的增加，ASP 收益比隨之增加。這是因為ECP 越多，競爭越激烈，進(jìn)而降低了ASP 所支付的費用。當(dāng)ECP 數(shù)量大于1 時，所提出的兩種拍賣算法的ASP 收益優(yōu)于順序分配；當(dāng)ECP 數(shù)量大于3 時，單項拍賣的ASP 收益優(yōu)于順序分配。進(jìn)一步比較3 種拍賣算法可知，所提出的兩種算法在不同的ECP 數(shù)量下均優(yōu)于單項拍賣。這是因為在單項拍賣中，ECP 只能對單個任務(wù)進(jìn)行競價，各個任務(wù)的拍賣彼此獨立，而在組合拍賣中，ECP 基于自身資源從同一個ASP 發(fā)布的多個任務(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 收益之和，即社會效益隨ECP 數(shù)量變化的情況。其中單項拍賣的社會效益比穩(wěn)定在1.2 左右，所提出的兩種算法的社會效益比穩(wěn)定在1.4 左右，均優(yōu)于順序分配的結(jié)果。這是因為拍賣機(jī)制能增加成功卸載的任務(wù)數(shù)量，進(jìn)而提高社會效益。

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

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

5.3 拍賣效率

圖6 展示了在任務(wù)數(shù)量為100 時，ECP 數(shù)量從1增加到10，拍賣輪數(shù)的變化情況。ECP 數(shù)量的增加，表示更多的資源可供使用，因此拍賣輪數(shù)隨之增加。單勝者拍賣比多勝者拍賣需要更多的拍賣輪數(shù)，這種差異在整體上隨ECP 數(shù)量的增加而增加。當(dāng)ECP 數(shù)量為10 時，單勝者拍賣的輪數(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 的情況下，改變單個ASP 的任務(wù)數(shù)n對拍賣輪數(shù)的影響。n的增加，表示每輪拍賣的初始任務(wù)數(shù)量增加，因此拍賣輪數(shù)隨之減少，而多勝者拍賣的效率優(yōu)勢隨之放大。

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

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

6 總結(jié)

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