區(qū)塊鏈賦能的邊緣異構(gòu)計算系統(tǒng)中資源調(diào)度研究

張平，李世林，劉宜明，秦曉琦，許曉東

（1.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876；2.北京郵電大學(xué)移動網(wǎng)絡(luò)技術(shù)國家工程實驗室，北京 100876）

1 引言

隨著5G 的發(fā)展和移動終端設(shè)備的普及，日益涌現(xiàn)的移動應(yīng)用及其產(chǎn)生的數(shù)據(jù)量將急劇增長[1]。其中，人臉識別、交互式在線游戲、虛擬/增強(qiáng)現(xiàn)實、4K/8K 超高清視頻等時延敏感型、計算密集型的應(yīng)用不僅需要消耗大量的計算資源，在用戶服務(wù)質(zhì)量方面也提出了超低時延、超高可靠性的要求。圍繞6G 網(wǎng)絡(luò)的總體愿景，未來移動通信網(wǎng)絡(luò)將以智能簡約作為設(shè)計內(nèi)涵[2]，充分利用邊緣泛在的計算能力，促使通信網(wǎng)絡(luò)更加扁平化[3-4]。在云計算、移動邊緣計算（MEC,mobile edge computing）的發(fā)展大趨勢下，未來移動用戶的周圍將部署不同規(guī)模的邊緣服務(wù)器以完成復(fù)雜任務(wù)處理，并利用通信資源完成計算任務(wù)數(shù)據(jù)的高效傳輸，逐步形成通信資源賦能“端?邊?云”協(xié)同計算的新范式[5-8]。

為了滿足人臉識別、虛擬/增強(qiáng)現(xiàn)實等計算密集型移動應(yīng)用超低時延的服務(wù)需求，可以在靠近用戶側(cè)的邊緣服務(wù)器上進(jìn)行計算任務(wù)處理。由于單一邊緣服務(wù)器能力有限，通常需要多個邊緣服務(wù)器的協(xié)同處理，且涉及計算數(shù)據(jù)遷移、計算結(jié)果共享以及多維資源的使用。然而，泛在接入的邊緣網(wǎng)絡(luò)極易受到惡意節(jié)點的信息干擾或數(shù)據(jù)攻擊，惡意節(jié)點可能篡改甚至偽造計算遷移請求、計算處理結(jié)果以及資源調(diào)度指令，破壞正常計算遷移、計算結(jié)果共享與資源調(diào)度進(jìn)程。因此，在邊緣側(cè)環(huán)境異構(gòu)開放、節(jié)點互不信任的情況下，如何保障計算卸載服務(wù)、計算結(jié)果共享和資源調(diào)度過程的安全可信與高效協(xié)同，是一個亟需解決的關(guān)鍵問題[9]。

目前，學(xué)術(shù)界和產(chǎn)業(yè)界普遍認(rèn)為區(qū)塊鏈技術(shù)是助力實現(xiàn)安全可信MEC 生態(tài)的關(guān)鍵技術(shù)[10-11]。區(qū)塊鏈技術(shù)本質(zhì)上是一種基于分布式對等網(wǎng)絡(luò)的分布式賬本技術(shù)，具有去中心化、不可篡改、可追溯、匿名性和透明性五大特征，這些特征為構(gòu)建安全可信的分布式交易環(huán)境提供了良好的契機(jī)[12-15]。在區(qū)塊鏈賦能的移動邊緣計算（BMEC,blockchain-enabled mobile edge computing）系統(tǒng)中，在不需要第三方授權(quán)機(jī)構(gòu)或平臺背書的情況下，移動終端設(shè)備與邊緣服務(wù)器之間可以自由發(fā)起計算卸載和資源調(diào)度請求，利用密碼學(xué)原理，如非對稱加密算法和哈希算法，可以對邊緣資源調(diào)度指令、計算結(jié)果、交易記錄等敏感信息進(jìn)行保護(hù)與驗證，同時利用共識機(jī)制，對服務(wù)與資源交易記錄達(dá)成一致確認(rèn)，進(jìn)而保障資源與服務(wù)交易過程的安全、可信與透明[16-19]。然而，在區(qū)塊鏈系統(tǒng)的共識過程中，需要利用計算及通信資源完成區(qū)塊的生成、驗證及傳輸?shù)汝P(guān)鍵步驟，這對有限的計算資源和通信資源的高效調(diào)度提出了更高的要求。

在BMEC 系統(tǒng)中，不僅需要考慮移動用戶的計算任務(wù)卸載請求，還需要考慮來自區(qū)塊鏈系統(tǒng)的計算任務(wù)。值得注意的是，用戶卸載計算任務(wù)和區(qū)塊鏈系統(tǒng)的計算任務(wù)在并行處理方面存在較大差異。具體來說，用戶卸載計算任務(wù)中的視頻轉(zhuǎn)碼、人工智能推理、圖像識別等高并行性計算任務(wù)可以被劃分為大量相互獨立的子任務(wù)進(jìn)行并行計算，而其他復(fù)雜的計算任務(wù)如基于有向無環(huán)圖（DAG,directed acyclic graph）的高斯消元和快速傅里葉變換，往往擁有不同程度的內(nèi)部關(guān)聯(lián)性，導(dǎo)致其在并行處理方面存在諸多限制。此外，BMEC 系統(tǒng)中的區(qū)塊生成和驗證也是一種高并行性計算任務(wù)。針對不同計算任務(wù)之間存在的并行性需求差異，眾多學(xué)者和研究人員提出異構(gòu)計算架構(gòu)，聯(lián)合優(yōu)化中央處理單元（CPU,central processing unit）和圖形處理單元（GPU,graphics processing unit）調(diào)度進(jìn)行加速計算[20]。其中，CPU 一般只包含若干個單線程或多線程內(nèi)核，僅可以實現(xiàn)粗粒度并行（CP,coarse-grained parallelism），對計算任務(wù)兼容性較好；GPU 通過裝載數(shù)以千計的內(nèi)核實現(xiàn)細(xì)粒度并行（FP,fine-grained parallelism），擁有強(qiáng)大的并行計算能力，但不適用于對復(fù)雜度較高的計算任務(wù)。針對BMEC 系統(tǒng)，異構(gòu)計算架構(gòu)可以滿足不同計算任務(wù)的并行性需求，使計算任務(wù)的并行性類型與處理器類型相匹配，充分利用各種計算資源進(jìn)行并行計算，達(dá)到降低計算任務(wù)執(zhí)行時間的目的[20]。

在本文中，考慮到BMEC 系統(tǒng)中區(qū)塊鏈計算任務(wù)和用戶卸載計算任務(wù)的并行性需求存在差異，引入異構(gòu)計算架構(gòu)，優(yōu)化CPU-GPU 異構(gòu)處理器調(diào)度策略，聯(lián)合分配通信和計算資源，實現(xiàn)系統(tǒng)性能的提升。考慮處理器調(diào)度約束、計算資源限制、通信資源限制，本文提出了聯(lián)合優(yōu)化處理器調(diào)度與資源分配（PSRA,processor scheduling and resource allocation）算法。本文的主要工作總結(jié)如下：1) 考慮不同計算任務(wù)的并行性需求，引入異構(gòu)計算架構(gòu)解決計算任務(wù)并行性類型與處理器類型之間的匹配問題；2) 考慮用戶任務(wù)處理效率和系統(tǒng)區(qū)塊生成效率占系統(tǒng)整體性能的權(quán)重，通過計算資源和帶寬資源的合理分配，提升用戶任務(wù)處理效率和系統(tǒng)區(qū)塊生成效率。

2 相關(guān)工作

與本文相關(guān)的研究工作的介紹從以下三方面展開：區(qū)塊鏈在MEC 系統(tǒng)中的應(yīng)用、CPU-GPU 異構(gòu)計算架構(gòu)與應(yīng)用、基于GPU 的區(qū)塊鏈應(yīng)用。

文獻(xiàn)[16-19]主要針對BMEC 場景展開研究。文獻(xiàn)[16]考慮了區(qū)塊鏈系統(tǒng)區(qū)塊最終生成時延與MEC 系統(tǒng)能耗之間的平衡問題，以兩者加權(quán)和最小化為目標(biāo)，將計算卸載決策、傳輸速率分配、區(qū)塊生成調(diào)度、計算資源分配的聯(lián)合優(yōu)化問題建模為混合整數(shù)非線性規(guī)劃（MINLP,mixed-integer nonlinear programming）問題，在解耦優(yōu)化變量的基礎(chǔ)上提出了迭代算法用于解決卸載決策和功率分配問題，并利用二分法解決了計算資源分配問題。針對傳統(tǒng)卸載決策、資源分配、區(qū)塊生成控制方法無法根據(jù)環(huán)境變化實時調(diào)整策略的缺陷，文獻(xiàn)[17-19]將優(yōu)化問題建模為馬爾可夫決策過程（MDP,Markov decision process），并利用深度強(qiáng)化學(xué)習(xí)（DRL,deep reinforcement learning）算法進(jìn)行求解。文獻(xiàn)[17]采用聯(lián)合基于股份授權(quán)證明（DPoS,delegated proof of stake）和實用拜占庭容錯（PBFT,practical Byzantine fault tolerance）的共識機(jī)制，對BMEC 系統(tǒng)的計算卸載請求與處理結(jié)果進(jìn)行記錄并存儲至區(qū)塊鏈，提出了自適應(yīng)的資源分配和區(qū)塊生成方案，以提升由區(qū)塊鏈系統(tǒng)吞吐量和邊緣計算系統(tǒng)用戶服務(wù)質(zhì)量決定的系統(tǒng)長期獎勵。為了實現(xiàn)長期計算卸載增益最大化并適應(yīng)環(huán)境的高動態(tài)性，文獻(xiàn)[18]研究了多跳網(wǎng)絡(luò)中數(shù)據(jù)處理任務(wù)和區(qū)塊挖掘任務(wù)的實時聯(lián)合卸載控制問題，并提出DRL 算法對問題進(jìn)行求解。以區(qū)塊鏈系統(tǒng)交易吞吐量和MEC 系統(tǒng)計算速率最大化為目標(biāo)，文獻(xiàn)[19]對計算卸載決策、傳輸功率、塊大小、塊間隔進(jìn)行聯(lián)合優(yōu)化，并針對決策空間同時存在離散決策和連續(xù)決策的特征，提出了基于異步優(yōu)勢行動者?評價家（A3C,asynchronous advantage actor-crigic）的DRL 算法。

考慮CPU-GPU 協(xié)同計算的模式，文獻(xiàn)[21]設(shè)計了基于CPU-GPU 異構(gòu)處理器的云計算架構(gòu)，利用自適應(yīng)分層、分層調(diào)度、性能估計等方法提升系統(tǒng)計算性能并降低計算和通信開銷。文獻(xiàn)[22]介紹了一種基于CPU 與GPU 的云計算平臺Ankea，其是一個完整的平臺即服務(wù)（PaaS,platform as a service）框架，包含用于應(yīng)用程序快速開發(fā)的多種編程模型，支持基于分布式異構(gòu)計算資源的編程模型部署。文獻(xiàn)[23]針對視頻編碼過程中并行度較低的問題，提出了基于CPU-GPU 異構(gòu)計算系統(tǒng)的多粒度并行計算方法，提升視頻編碼過程中并行執(zhí)行的效率。文獻(xiàn)[24]針對遠(yuǎn)程醫(yī)療數(shù)據(jù)加密時延較高的問題，提出了基于CPU-GPU 異構(gòu)計算系統(tǒng)的加密函數(shù)調(diào)度優(yōu)化算法。

GPU 加速計算在區(qū)塊鏈系統(tǒng)中得到了廣泛應(yīng)用[25-28]。文獻(xiàn)[25]基于不同規(guī)格的CPU、GPU 進(jìn)行了包括比特幣、以太坊在內(nèi)的多類數(shù)字加密貨幣的挖掘測試，測試結(jié)果表明在數(shù)字貨幣挖掘的哈希速率方面，GPU 相較于CPU 有數(shù)十倍的速率提升。文獻(xiàn)[26]同樣利用基于統(tǒng)一計算設(shè)備架構(gòu)（CUDA,compute unified device architecture）的GPU 提升了區(qū)塊鏈挖掘效率，證明GPU 并行計算的優(yōu)勢只有當(dāng)并行挖掘的任務(wù)數(shù)量大于800 時才得以體現(xiàn)。文獻(xiàn)[27]針對區(qū)塊鏈系統(tǒng)中大量用戶搜索給全節(jié)點帶來的計算瓶頸問題，利用區(qū)塊鏈數(shù)據(jù)不能刪除和更改的特征，引入適合GPU 并行計算的帕特里夏樹（PT,Patricia tree）數(shù)組用于存儲區(qū)塊數(shù)據(jù)，實驗結(jié)果表明基于PT 數(shù)組和GPU 的搜索吞吐量是基于CPU 的搜索吞吐量的14.1 倍。針對區(qū)塊鏈系統(tǒng)中交易數(shù)據(jù)異常檢測過程中的時延敏感、計算密集類任務(wù)，文獻(xiàn)[28]將需要提取特征信息的交易數(shù)據(jù)緩存至GPU 存儲單元中，并在GPU 中進(jìn)行特征提取和異常檢測，實驗結(jié)果表明GPU 異常檢測速率可以達(dá)到CPU 異常檢測速率的37.1 倍。

與已有工作相比，本文考慮基于CPU-GPU 異構(gòu)計算架構(gòu)的BMEC 系統(tǒng)，以系統(tǒng)區(qū)塊生成效率和用戶任務(wù)處理效率共同決定的系統(tǒng)效用最大化為研究目標(biāo)，建立異構(gòu)處理器調(diào)度、計算資源分配、帶寬資源分配的聯(lián)合優(yōu)化問題。本文將系統(tǒng)效用最大化問題建模為MINLP 問題?？紤]到MINLP 問題的高復(fù)雜性，將原優(yōu)化問題分解為處理器調(diào)度優(yōu)化問題和資源聯(lián)合分配優(yōu)化問題，并對應(yīng)提出了PSRA 算法。

3 BMEC 系統(tǒng)模型

本文考慮了基于異構(gòu)計算的BMEC 系統(tǒng)，在邊緣服務(wù)器上分別部署了CPU、GPU 兩類處理器。本文將移動應(yīng)用劃分為低并行性普通應(yīng)用和高并行性特殊應(yīng)用（后文簡稱為普通應(yīng)用和特殊應(yīng)用），前者僅可以調(diào)用CPU 處理器，后者不僅可以調(diào)用CPU 處理器還可以調(diào)用GPU 處理器。異構(gòu)計算實現(xiàn)過程如圖1 所示，利用虛擬機(jī)（VM,virtual machine）技術(shù)，將邊緣服務(wù)器中的CPU、GPU 計算資源虛擬化并分配給不同的虛擬機(jī)，以處理區(qū)塊鏈計算任務(wù)和用戶卸載計算任務(wù)。本文假設(shè)任意虛擬機(jī)僅可同時調(diào)用一類處理器處理計算任務(wù)，且兩類計算資源可以按照任意比例分配給虛擬機(jī)。

3.1 網(wǎng)絡(luò)模型

在本文中，利用區(qū)塊鏈技術(shù)，BMEC 系統(tǒng)可以對多方共同參與計算卸載和任務(wù)執(zhí)行信息進(jìn)行記錄，包括移動用戶的計算卸載請求及任務(wù)處理結(jié)果等信息。值得注意的是，所有交易信息都先經(jīng)過區(qū)塊鏈共識節(jié)點的驗證與確認(rèn)，然后才會被存儲至所有區(qū)塊鏈節(jié)點備份中。BMEC 系統(tǒng)網(wǎng)絡(luò)模型如圖2所示。BMEC 系統(tǒng)主要由區(qū)塊鏈用戶、區(qū)塊生成（BP,block producer）節(jié)點構(gòu)成，BP 節(jié)點又分為主節(jié)點（PN,primary node）和備份節(jié)點（BN,backup node），具體介紹如下。

圖1 異構(gòu)計算實現(xiàn)過程

區(qū)塊鏈用戶。系統(tǒng)中的移動用戶，可以提交計算卸載請求，邊緣服務(wù)器完成計算任務(wù)并將處理結(jié)果反饋至移動用戶。

區(qū)塊生成節(jié)點。系統(tǒng)中的邊緣服務(wù)器，不僅提供計算卸載服務(wù)，還負(fù)責(zé)區(qū)塊的生成和驗證。

主節(jié)點。在特定時間段從區(qū)塊生成節(jié)點中選出的單個節(jié)點，被授權(quán)在該時間段生成新的區(qū)塊。

備份節(jié)點。區(qū)塊生成節(jié)點中除主節(jié)點以外的所有節(jié)點，負(fù)責(zé)新區(qū)塊的驗證工作。

交易信息。記錄移動用戶的計算卸載請求及任務(wù)處理結(jié)果，共享于整個區(qū)塊鏈網(wǎng)絡(luò)，由主節(jié)點收集并生成新的區(qū)塊。

本文采用基于DPoS-PBFT 的共識機(jī)制[17]，假設(shè)M個邊緣服務(wù)器（區(qū)塊生成節(jié)點）以T為時延間隔輪流生成區(qū)塊。服務(wù)器集合由∏={1,2,…,M}表示，m表示第m個服務(wù)器。假設(shè)惡意節(jié)點數(shù)量小于。簡單來說，在指定時間內(nèi)，PN 收集交易信息并將新生成的區(qū)塊廣播至所有BN 進(jìn)行驗證，即共識過程。當(dāng)所有BP 節(jié)點達(dá)成共識后，新的區(qū)塊才會被添加至區(qū)塊鏈，然后被存儲至所有區(qū)塊鏈節(jié)點。

假設(shè)服務(wù)器m可用的CPU、GPU 計算資源分別為FC、FG（單位為cycle/s）。服務(wù)器中部署的應(yīng)用集合表示為ψ={1,2,…,A}，A表示應(yīng)用數(shù)量，a表示第a個應(yīng)用。應(yīng)用類型表示為ρa(bǔ)∈{0,1}，ρa(bǔ)=0表示a為普通應(yīng)用，ρa(bǔ)=1表示a為特殊應(yīng)用。假設(shè)任意服務(wù)器m服務(wù)于Nm個移動用戶，用戶集合表示為Γm={1m,2m,…,Nm}，nm表示由服務(wù)器m服務(wù)的第n個用戶。此外，nm=0表示區(qū)塊鏈計算任務(wù)。用戶nm的計算任務(wù)可以表示為數(shù)組，其中am,n∈ψ表示任務(wù)所屬的應(yīng)用，αm,n表示任務(wù)數(shù)據(jù)量（單位為bit），βm,n表示利用CPU 完成計算任務(wù)所需要的計算量，γm,n表示利用GPU 完成計算任務(wù)所需要的計算量，ηm,n∈(0,1]表示計算任務(wù)對時延的敏感程度。由于不同種類應(yīng)用對GPU 的利用效率不同，本文假設(shè)，其中Xm,n∈(0,1]表示計算任務(wù)nm對GPU 的利用效率，Xm,n由任務(wù)類型決定，Xm,n越大表明對GPU 的利用效率越高。本文考慮采用正交頻分多址接入（OFDMA,orthogonal frequency division multiple access）方法，通信帶寬資源被劃分為數(shù)量為E的等帶寬子信道，每個用戶都可以被分配到若干個子信道用于無線傳輸。詳細(xì)系統(tǒng)參數(shù)表示和相關(guān)含義如表1 所示。

圖2 BMEC 系統(tǒng)網(wǎng)絡(luò)模型

表1 系統(tǒng)參數(shù)表示和相關(guān)含義

考慮到BMEC 系統(tǒng)中的計算負(fù)載分別來源于移動用戶卸載的計算任務(wù)和區(qū)塊鏈系統(tǒng)中區(qū)塊生成、區(qū)塊驗證、達(dá)成共識所需要完成的計算任務(wù)，接下來將分別對區(qū)塊鏈任務(wù)計算和用戶卸載任務(wù)計算進(jìn)行建模分析。

3.2 區(qū)塊鏈任務(wù)計算模型

首先，移動用戶向服務(wù)器發(fā)出卸載請求，服務(wù)器接受請求并處理任務(wù)；然后，將任務(wù)處理結(jié)果反饋至移動用戶并將相關(guān)信息作為交易記錄掛起等待PN 的進(jìn)一步處理。PN 在收集交易信息并生成區(qū)塊的時候，需要對交易記錄中的用戶簽名（SIG,signature）和消息認(rèn)證碼（MAC,message authentication code）進(jìn)行驗證。PBFT 共識協(xié)議包含以下5 個階段[17]：請求、序號分配、序號準(zhǔn)備、序號確認(rèn)、響應(yīng)。

在請求階段，PN 需要驗證新區(qū)塊中所有交易記錄的SIG 和MAC 并生成新的區(qū)塊，完成交易驗證任務(wù)和區(qū)塊生成任務(wù)所需要的CPU 計算量為，其中，SB、?、φ、?、g分別表示區(qū)塊數(shù)據(jù)量、平均交易數(shù)據(jù)量、驗證/生成SIG需要的CPU 計算量、驗證/生成MAC 需要的CPU計算量、有效交易記錄比例。

在序號分配階段，PN 為新區(qū)塊附上SIG 與MAC，并廣播至所有BN。BN 收到新區(qū)塊之后，需要驗證新區(qū)塊及其包含所有交易記錄的SIG 與MAC。因此，此階段在任意BN 處需要的CPU 計算量為。

在響應(yīng)階段，新區(qū)塊經(jīng)過BN 驗證為有效區(qū)塊后，所有BN 需要為新區(qū)塊中的每條交易記錄附加新的SIG 和MAC，然后將其傳回PN。因此，此階段在任意 BN 處需要的 CPU 計算量為。值得注意的是，序號準(zhǔn)備與確認(rèn)階段，各BP 節(jié)點的計算需求量相對較小，本文忽略不計。

若服務(wù)器m為PN，則完成區(qū)塊鏈計算任務(wù)的時延為

實時類應(yīng)用往往需要其交易記錄快速得到確認(rèn)，因此，當(dāng)服務(wù)器m為PN 時，系統(tǒng)區(qū)塊生成效率為

當(dāng)服務(wù)器m為BN 時，系統(tǒng)區(qū)塊生成效率為

3.3 用戶卸載任務(wù)計算模型

在用戶卸載任務(wù)計算模型中，需要考慮移動用戶卸載任務(wù)的時延和服務(wù)器處理計算任務(wù)的時延。用戶nm的上行傳輸速率可以表示為，其中，Wm,n表示用戶nm分配到的子信道數(shù)量，表示用戶nm基于單個子信道的上行傳輸速率。因此，用戶nm上傳計算任務(wù)產(chǎn)生的時延為

在任務(wù)處理階段，本文考慮每一個虛擬機(jī)都可以運行應(yīng)用集合ψ中的任意應(yīng)用，不同虛擬機(jī)可以同時運行相同的應(yīng)用，但是一個虛擬機(jī)一次只能運行一個應(yīng)用；服務(wù)器主機(jī)可以根據(jù)用戶數(shù)量劃分為數(shù)量相同的虛擬機(jī)，并將其與任務(wù)nm進(jìn)行關(guān)聯(lián)，然后根據(jù)任務(wù)需求給不同的虛擬機(jī)分配不同的計算資源。由于任意虛擬機(jī)只能同時調(diào)用一類處理器，且與用戶nm關(guān)聯(lián)的虛擬機(jī)的處理器調(diào)度決策可以表示為向量，λm,n=[0,1]表示調(diào)用 GPU，λm,n=[1,0]表示調(diào)用CPU。令向量表示計算資源分配策略，其中表示與用戶nm關(guān)聯(lián)的虛擬機(jī)所調(diào)用的CPU 資源數(shù)量，表示與用戶nm關(guān)聯(lián)的虛擬機(jī)所調(diào)用的GPU 資源數(shù)量。則計算任務(wù)nm的處理時延為

計算任務(wù)nm從上傳至處理完成的總時延可以表示為。由于移動應(yīng)用一般為時延敏感型，其任務(wù)完成時延直接決定了用戶任務(wù)處理效率。因此，本文將用戶任務(wù)處理效率定義為

3.4 BMEC 系統(tǒng)計算模型

為了均衡系統(tǒng)區(qū)塊生成效率和用戶任務(wù)處理效率，本文將服務(wù)器效用函數(shù)表示為用戶任務(wù)處理效率和系統(tǒng)區(qū)塊生成效率的加權(quán)求和。當(dāng)服務(wù)器m為PN 時，服務(wù)器效用函數(shù)為

C1 表示任意虛擬機(jī)僅可以同時調(diào)用一類處理器處理計算任務(wù)。C2 則給出了一般應(yīng)用不能調(diào)用GPU 處理計算任務(wù)的限制，其中Γm,+={0∪Γm}，。C3、C4 分別給出了可分配CPU、GPU 計算資源的上限。C5 給出了帶寬資源限制條件。C6～C8 則分別給出了不同變量的取值范圍，分別表示維持虛擬機(jī)運行所需要的最低CPU 計算資源和GPU 計算資源，其中，有

C9 表示同時最多只能有一個服務(wù)器生成新的區(qū)塊。由于所有服務(wù)器輪流生成新的區(qū)塊，導(dǎo)致zm的取值是隨機(jī)的，且當(dāng)zm確定時，所有服務(wù)器的效用最大化問題是相互獨立的。因此，C9 被松弛之后，原優(yōu)化問題可以簡化為面向任意服務(wù)器的系統(tǒng)效用最大化問題P2。

可以看出，P2 是一個典型的MINLP 問題，通常情況下此類問題沒有有效的解決方法，需要根據(jù)具體模型設(shè)計解決方案。通過觀察分析，原問題可以分解為2 個子問題，即資源分配優(yōu)化問題和處理器調(diào)度優(yōu)化問題。其中，在給定任意可行處理器調(diào)度策略λ的情況下，資源分配優(yōu)化問題可以表示為P3。

令G(λ)=G(f*,W*)，其中f*和W*分別是調(diào)度策略為λ時的最優(yōu)計算資源分配方案和最優(yōu)帶寬資源分配方案。優(yōu)化問題P2 等價于處理器調(diào)度優(yōu)化問題P4。

4 問題分析與算法設(shè)計

本節(jié)首先針對資源優(yōu)化問題P3 提出基于拉格朗日對偶理論的資源分配算法，然后針對處理器調(diào)度優(yōu)化問題P4 設(shè)計了基于任務(wù)處理時延的處理器調(diào)度與資源分配聯(lián)合優(yōu)化算法，最后對算法復(fù)雜度進(jìn)行了分析。

4.1 資源分配優(yōu)化問題

給定任意可行處理器調(diào)度方案λ，問題P3 的目標(biāo)函數(shù)可以重新表示為

證畢。

因此，問題P5 可通過拉格朗日對偶法求解，且拉格朗日函數(shù)構(gòu)造如下。

其中，v≥ 0為與C5'相關(guān)的拉格朗日乘子，限制條件C8'被暫時松弛。拉格朗日對偶函數(shù)可以表示為

將W′*代入拉格朗日對偶函數(shù)可以獲得關(guān)于v的對偶問題。由于對偶問題也是凸優(yōu)化問題，可以得到，由此可以計算出

基于上述結(jié)論，本文設(shè)計了基于拉格朗日對偶的迭代算法對帶寬資源分配方案進(jìn)行優(yōu)化，如算法1 所示。

算法1帶寬資源分配算法

需要注意的是，帶寬資源實際為離散變量，因此本文設(shè)計算法2，將W'*的連續(xù)變量轉(zhuǎn)變?yōu)榉蠗l件的離散變量。

算法2帶寬資源分配方案轉(zhuǎn)換算法

給定任意可行的帶寬資源分配方案W，由于限制條件C3、C4 互相獨立，優(yōu)化問題P3 可以根據(jù)處理器調(diào)度決策解耦為2 個子問題P6、P7，分別對CPU 計算資源分配和GPU 計算資源分配進(jìn)行優(yōu)化。具體地，CPU 計算資源分配優(yōu)化問題P6 可以表示為

GPU 計算資源分配優(yōu)化問題P7 可以表示為

定理2問題P6、P7 是凸優(yōu)化問題。

證明同定理1。

根據(jù)拉格朗日對偶理論，問題P6、P7 的拉格朗日函數(shù)分別構(gòu)造為

與之對應(yīng)的拉格朗日對偶函數(shù)可以分別表示為

注意到上述獲得的計算資源分配方案是基于假設(shè)λ0=[1,0]的。當(dāng)λ0=[0,1]時，計算資源分配方案可以按照類似的方法進(jìn)行優(yōu)化，本文不再詳細(xì)闡述。基于上述帶寬資源分配優(yōu)化方法與計算資源分配優(yōu)化方法，本文設(shè)計了資源聯(lián)合分配（JRA,joint resources allocation）算法，如算法4 所示。

算法4資源聯(lián)合分配算法

初始化

4.2 處理器調(diào)度優(yōu)化問題

根據(jù)限制條件C2 可知，與普通類型任務(wù)相關(guān)聯(lián)的虛擬機(jī)只能調(diào)用CPU 處理器處理計算任務(wù)，由此可得。由于處理器調(diào)度策略可直接決定任務(wù)處理時延，從而影響系統(tǒng)效用，本文綜合考慮任務(wù)處理時延和權(quán)重因子，設(shè)計了基于任務(wù)處理時延Tn的PSRA 算法對處理器調(diào)度問題（等價于問題P2）進(jìn)行優(yōu)化，如算法5 所示。具體地，加權(quán)任務(wù)處理時延定義為

算法5處理器調(diào)度與資源分配聯(lián)合優(yōu)化算法

4.3 算法復(fù)雜度分析

PSRA 算法的計算復(fù)雜度主要來自處理器調(diào)度方案的迭代優(yōu)化，假設(shè)迭代次數(shù)為I1。處理器調(diào)度方案每次迭代過程中的計算量主要來自JRA 算法對帶寬資源及計算資源的迭代優(yōu)化，假設(shè)迭代次數(shù)為I2。算法1 和算法3 的最大循環(huán)次數(shù)分別為N和N+1。因此，JRA 算法的計算復(fù)雜度可以表示為O(I2(2N+1))，處理器調(diào)度方案迭代優(yōu)化的計算復(fù)雜度可以表示為O(I2(I1+1) (2N+1))，算法 PSRA 的總計算復(fù)雜度則可以表示為O(I2(I1+1) (2N+1)+N)。

5 仿真結(jié)果與分析

本節(jié)對基于異構(gòu)計算的BMEC 系統(tǒng)性能進(jìn)行了仿真測驗和分析，并驗證分析了所提算法相較于其他基準(zhǔn)算法的優(yōu)越性。首先描述了仿真參數(shù)設(shè)置，然后相繼展示了所提算法的收斂性、優(yōu)越性以及系統(tǒng)效用與用戶數(shù)量之間的關(guān)系。

5.1 仿真參數(shù)設(shè)置

本文考慮的BMEC 系統(tǒng)中包含5 個MEC 服務(wù)器，每個服務(wù)器服務(wù)的用戶數(shù)量為15，假設(shè)所有服務(wù)器均為區(qū)塊生成節(jié)點，且每個節(jié)點輪流負(fù)責(zé)新區(qū)塊的生成。本文考慮移動用戶上行信道傳輸速率為隨機(jī)變量[17]，假設(shè)每個用戶在單位子信道上的上行傳輸速率均勻分布于[106,2 ×106]bit/s。本文假設(shè)每個服務(wù)器裝配有6 個主頻為2.4 GHz 的4 核8 線程CPU 處理器和一個主頻為1 038 MHz 的768 核GPU 處理器[25,28]，即FC=57.6 Gcycle/s，F(xiàn)G=797 Gcycle/s。本文考慮每個服務(wù)器可處理五類應(yīng)用，每類應(yīng)用對應(yīng)一種計算任務(wù)，每個用戶隨機(jī)產(chǎn)生其中一種任務(wù)，五類任務(wù)對應(yīng)的應(yīng)用信息如表2 所示。此外，區(qū)塊鏈應(yīng)用為特殊應(yīng)用且GPU 利用效率為0.5，根據(jù)所有BP 節(jié)點輪流生成新區(qū)塊的特征，本文假設(shè)區(qū)塊鏈任務(wù)計算量滿足概率，。其他仿真參數(shù)設(shè)置如表3所示。

表2 應(yīng)用信息

為了證實所提PSRA 算法的性能和異構(gòu)計算架構(gòu)引入的效果，本文將其與以下基準(zhǔn)算法進(jìn)行比較。

表3 仿真參數(shù)設(shè)置

1) 窮搜算法。列舉所有處理器調(diào)度方案，找出使系統(tǒng)效用最高的處理器調(diào)度方案，資源分配采用JRA 算法。

2) 貪婪算法。凡屬于特殊應(yīng)用類型的任務(wù)，均調(diào)用GPU 處理器執(zhí)行相關(guān)計算，資源分配采用JRA算法。

3) 資源平均算法。計算資源和帶寬資源平均分配給每個用戶，處理器調(diào)度策略基于PSRA 算法進(jìn)行優(yōu)化。

由于貪婪算法和資源平均算法未充分挖掘不同計算任務(wù)所存在的并行性，不能實現(xiàn)計算任務(wù)與處理器之間的匹配優(yōu)化和異構(gòu)計算資源分配優(yōu)化，可視為未引入異構(gòu)計算的基準(zhǔn)算法。

5.2 算法收斂性

圖3 和圖4 分別表示用戶數(shù)量為15 時，JRA算法關(guān)于計算資源分配方案和帶寬資源分配方案的收斂性能?？梢钥闯?，2 種資源分配方案均在有限次迭代以后達(dá)到收斂狀態(tài)。

圖3 JRA 算法收斂性（計算資源分配方案）

圖4 JRA 算法收斂性（帶寬資源分配方案）

圖5 表示PSRA 算法在不同用戶數(shù)量下的收斂性能。從圖5 可以看出，隨著迭代次數(shù)的增加，所提算法在不同用戶數(shù)量的場景下均逐漸收斂。此外，當(dāng)用戶數(shù)量較少時，所提PSRA 算法的求解空間較小，可以更快收斂，而用戶數(shù)量較大時，所提PSRA 算法的收斂速度降低。如圖5 所示，當(dāng)N=5時，所提PSRA 算法在平均迭代7 次后達(dá)到收斂狀態(tài)。當(dāng)N=15時，相比于N=5的場景，PSRA 算法需要更多迭代輪次達(dá)到收斂狀態(tài)。因此，當(dāng)平均迭代次數(shù)為7 次時，由于PSRA 算法在N=15的場景下尚未達(dá)到收斂，因此該輪次下的系統(tǒng)效用取值并不能反映系統(tǒng)效用隨用戶數(shù)量變化的相對趨勢。當(dāng)平均迭代次數(shù)為12 時，所提PSRA 算法在N=15的場景下達(dá)到收斂，此時該場景下的最終可達(dá)系統(tǒng)效用值高于N=5的場景。

圖5 PSRA 算法收斂性

本文定義的系統(tǒng)效用是由所有用戶任務(wù)處理效率與系統(tǒng)區(qū)塊生成效率的加權(quán)和決定的，系統(tǒng)效用函數(shù)不隨用戶數(shù)量增長呈現(xiàn)單調(diào)性。系統(tǒng)效用的取值受到帶寬資源、計算資源、用戶數(shù)量、用戶任務(wù)處理效率與系統(tǒng)區(qū)塊生成效率的權(quán)值等因素的綜合影響。具體來說，隨著用戶數(shù)量的增加，系統(tǒng)效用函數(shù)中被累加的任務(wù)處理效率的數(shù)量隨之增加；但是，由于隨著用戶數(shù)量的增加，每個用戶可用的平均帶寬資源、計算資源減少，區(qū)塊生成任務(wù)可用計算資源也減少，導(dǎo)致單個用戶任務(wù)處理效率及系統(tǒng)區(qū)塊生成效率逐漸降低。

5.3 算法性能

圖6 和圖7 分別為N=5和N=15場景下PSRA 算法、貪婪算法、資源平均算法的性能曲線。由圖6 和圖7 可以看出，在不同的用戶數(shù)下，PSRA 算法性能優(yōu)于貪婪算法和資源平均算法。這主要是因為，針對不同種類計算任務(wù)的處理需求，PSRA 算法通過優(yōu)化處理器調(diào)度和資源分配，可以有效提高用戶任務(wù)處理效率和系統(tǒng)區(qū)塊生成效率，進(jìn)而提升系統(tǒng)效用。

圖6 PSRA 算法、貪婪算法、資源平均算法對比（N=5）

圖7 PSRA 算法、貪婪算法、資源平均算法對比（N=15）

貪婪算法的優(yōu)勢在于可以根據(jù)任務(wù)需求優(yōu)化帶寬資源和計算資源分配方案，但是不能根據(jù)任務(wù)處理時延優(yōu)化處理器調(diào)度方案；資源平均算法的優(yōu)勢在于可以根據(jù)任務(wù)處理時延優(yōu)化處理器調(diào)度方案，但是不能根據(jù)任務(wù)需求優(yōu)化帶寬資源和計算資源分配方案。當(dāng)帶寬資源較少時，帶寬資源平均分配方案與JRA 算法優(yōu)化的帶寬資源分配方案相對接近，此時帶寬資源分配不均衡程度較低，優(yōu)化資源分配方案所帶來的系統(tǒng)效用增益較低。因此，當(dāng)帶寬資源較少時，資源平均算法的性能相對較好。但是隨著帶寬資源數(shù)量的增加，帶寬資源平均分配方案導(dǎo)致的資源分配不均衡程度越來越高，通過優(yōu)化資源分配可以獲得較高的系統(tǒng)效用增益。因此，隨著帶寬資源的增加，資源平均算法與可以優(yōu)化計算資源和帶寬資源分配方案的PSRA 算法、貪婪算法相比，其算法性能會逐漸變差。

5.4 系統(tǒng)效用與用戶數(shù)量的關(guān)系

圖8 給出了PSRA 算法在帶寬資源為50 時，系統(tǒng)效用與用戶數(shù)量之間的變化趨勢。由圖8 可以看出，隨著用戶數(shù)量的增加，系統(tǒng)效用函數(shù)呈現(xiàn)先上升后下降的趨勢。當(dāng)帶寬資源數(shù)量為50，用戶任務(wù)處理效率和系統(tǒng)區(qū)塊生成效率權(quán)重因子分別為0.4和0.6的情況下，N=15時的系統(tǒng)效用高于N=5和N=30的場景。然而，由于系統(tǒng)效用函數(shù)受到多重因素的影響，該相對趨勢并不能體現(xiàn)系統(tǒng)的性能特征，系統(tǒng)效用不會隨著用戶數(shù)量的增長呈現(xiàn)出單調(diào)性特征。

圖8 系統(tǒng)效用與用戶數(shù)量的關(guān)系

6 結(jié)束語

本文提出了一種基于異構(gòu)計算的BMEC 系統(tǒng)模型，該模型通過聯(lián)合優(yōu)化異構(gòu)處理器調(diào)度與資源分配，解決了聯(lián)合處理移動應(yīng)用計算任務(wù)和區(qū)塊鏈計算任務(wù)時面臨的高時延和資源利用率低下等問題。為了實現(xiàn)不同計算任務(wù)高效并行性處理，以系統(tǒng)效用最大化為目標(biāo)，本文研究了異構(gòu)處理器調(diào)度與資源分配的聯(lián)合優(yōu)化問題，并提出了基于拉格朗日對偶理論的處理器調(diào)度與資源分配聯(lián)合優(yōu)化算法進(jìn)行求解。仿真結(jié)果表明，本文所提的PSRA 算法優(yōu)于其他基準(zhǔn)算法，可以有效提升基于異構(gòu)計算的BMEC 系統(tǒng)效用。