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

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 BMEC 系統(tǒng)模型

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

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

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

圖1 異構(gòu)計(jì)算實(shí)現(xiàn)過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 問(wèn)題分析與算法設(shè)計(jì)

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

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

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

證畢。

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

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

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

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

算法1帶寬資源分配算法

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

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

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

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

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

證明同定理1。

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

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

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

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

初始化

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

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

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

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

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

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

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

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

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

表2 應(yīng)用信息

為了證實(shí)所提PSRA 算法的性能和異構(gòu)計(jì)算架構(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)計(jì)算，資源分配采用JRA算法。

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

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

5.2 算法收斂性

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

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

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

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

圖5 PSRA 算法收斂性

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

5.3 算法性能

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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