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

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

（1.北京郵電大學網絡與交換技術國家重點實驗室，北京 100876；2.北京郵電大學移動網絡技術國家工程實驗室，北京 100876）

1 引言

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

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

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

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

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

2 相關工作

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

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

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

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

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

3 BMEC 系統(tǒng)模型

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

3.1 網絡模型

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

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

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

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

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

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

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

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

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

圖2 BMEC 系統(tǒng)網絡模型

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

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

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

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

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

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

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

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

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

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

3.3 用戶卸載任務計算模型

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

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

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

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

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

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

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

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

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

4 問題分析與算法設計

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

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

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

證畢。

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

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

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

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

算法1帶寬資源分配算法

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

算法2帶寬資源分配方案轉換算法

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

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

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

證明同定理1。

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

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

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

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

初始化

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

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

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

4.3 算法復雜度分析

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

5 仿真結果與分析

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

5.1 仿真參數(shù)設置

本文考慮的BMEC 系統(tǒng)中包含5 個MEC 服務器，每個服務器服務的用戶數(shù)量為15，假設所有服務器均為區(qū)塊生成節(jié)點，且每個節(jié)點輪流負責新區(qū)塊的生成。本文考慮移動用戶上行信道傳輸速率為隨機變量[17]，假設每個用戶在單位子信道上的上行傳輸速率均勻分布于[106,2 ×106]bit/s。本文假設每個服務器裝配有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。本文考慮每個服務器可處理五類應用，每類應用對應一種計算任務，每個用戶隨機產生其中一種任務，五類任務對應的應用信息如表2 所示。此外，區(qū)塊鏈應用為特殊應用且GPU 利用效率為0.5，根據所有BP 節(jié)點輪流生成新區(qū)塊的特征，本文假設區(qū)塊鏈任務計算量滿足概率，。其他仿真參數(shù)設置如表3所示。

表2 應用信息

為了證實所提PSRA 算法的性能和異構計算架構引入的效果，本文將其與以下基準算法進行比較。

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

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

2) 貪婪算法。凡屬于特殊應用類型的任務，均調用GPU 處理器執(zhí)行相關計算，資源分配采用JRA算法。

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

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

5.2 算法收斂性

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

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

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

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

圖5 PSRA 算法收斂性

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

5.3 算法性能

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

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

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

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

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

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

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

6 結束語

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