摘 要：為了克服區(qū)塊鏈單鏈技術效率低的問題，一種新的范式有向無環(huán)圖正在蓬勃發(fā)展。針對區(qū)塊鏈有向無環(huán)圖中考慮代價權重的非獨立任務調度問題，構建了區(qū)塊鏈DAG的任務調度數(shù)學模型，并為了求解該問題提出了一種基于改進分布估計鯨魚的新任務調度算法。新算法在WOA中引入EDA的空間采樣和統(tǒng)計學習來預測搜索的最佳區(qū)域，進而產生優(yōu)秀的新個體，從而使得新算法具備更強的全局搜索能力和更快的收斂速度。最后通過程序仿真，對比了多種算法在收斂速度和全局尋優(yōu)能力方面的性能。實驗表明IEWOA比傳統(tǒng)的WOA和EDA在以上參數(shù)性能有明顯優(yōu)勢，相比于改進遺傳算法FPGA，IEWOA同樣在參數(shù)性能上有一定的優(yōu)勢。

關鍵詞：DAG；分布估計；鯨魚算法；任務調度

中圖分類號：TP18 文獻標志碼：A 文章編號：1001-3695（2024）11-023-3364-06

doi：10.19734/j.issn.1001-3695.2024.04.0094

Improved distribution estimation whale algorithm for block chain DAG task scheduling

Xu Jun¹， Peng Junfeng^{1， 2}， Tang Yong²， Wang Jihong¹， Cai Weishan¹

（1.School of Computing， Guangdong University of Education， Guangzhou 510303， China; 2.School of Computing， South China Normal University， Guangzhou 510631， China）

Abstract：In order to overcome the efficiency issues of single chain technology in blockchain， a new paradigm directed acyclic graphs is flourishing. This article focused on the non independent task scheduling problem considering cost weights in blockchain directed acyclic graphs， and constructed a mathematical model for task scheduling in blockchain DAG， and proposed a new task scheduling algorithm based on improved distribution estimation whale to solve this problem. The new algorithm introduced spatial sampling and statistical learning of EDA in the WOA algorithm to predict the optimal search area， thereby gene-rating excellent new individuals， making the new algorithm have stronger global search ability and faster convergence speed. Finally， through program simulation， it compared the performance of multiple algorithms in terms of convergence speed and glo-bal optimization ability. The experiments show that IEWOA has significant advantages over traditional WOA and EDA in the above parameter performance. In addition， comparing with the improved genetic algorithm FPGA， IEWOA also has certain advantages in parameter performance.

Key words：DAG; distribution estimation; whale algorithm; task scheduling

0 引言

區(qū)塊鏈是當今討論最多的技術之一^{［1，2］}，是由公共或私有網(wǎng)絡組成的交易數(shù)字賬本，每隔一段時間的一組交易被連續(xù)打包在區(qū)塊中。區(qū)塊鏈以前被設計為一種加密貨幣^［3，4］，并被認為是分類賬或分布式數(shù)據(jù)庫的一種創(chuàng)新方法，其中非理性數(shù)據(jù)也可以保存在交易的元數(shù)據(jù)中。區(qū)塊鏈數(shù)據(jù)庫或分類賬包含交易和區(qū)塊兩個級別的記錄。區(qū)塊中包含一個或多個事務的列表，每個塊帶有時間戳并鏈接到上一個塊。為確保區(qū)塊鏈數(shù)據(jù)的安全，塊中的數(shù)據(jù)以加密形式存儲。由于每個塊包含前一個塊的哈希，所以每個塊將與前一個塊鏈接，形成類似鏈表的數(shù)據(jù)結構。然而第一個塊卻沒有先前鏈接的塊，因此其先前的哈希值設置為NULL，稱為創(chuàng)世塊。這種單鏈區(qū)塊鏈技術在可擴展性、成本和效率方面存在一定的局限性，這阻礙了其在需要高效微交易的應用中的發(fā)展，如單鏈技術無法支持高并發(fā)的需求、鏈與鏈之間不能互通互聯(lián)、無法適應不同的應用場景等，這些缺點對其在新興物聯(lián)網(wǎng)（IoT）應用中的適應性有重大影響^［5～10］。有向無環(huán)圖（DAG）如圖1所示，因其在物聯(lián)網(wǎng)中的特殊含義而徹底改變了區(qū)塊鏈技術^{［11～14］}，由于其優(yōu)化驗證、高可擴展性、高效來源、物聯(lián)網(wǎng)支持和多方參與等特點，導致這種區(qū)塊鏈DAG技術正在迅速發(fā)展^{［15～17］}，而其中DAG（有向無環(huán)圖）任務調度問題也成為研究熱點之一。

DAG任務調度一般目標是最小化任務執(zhí)行時間 （make-span），該問題是一個完全NP問題^［18］，因此大多數(shù)研究都是基于啟發(fā)式算法。例如文獻［19］提出了一種使用強化學習的蒙特卡羅樹搜索（MCTS）信任感知自適應DAG任務調度算法，該方法使用強化學習模型進行定義，確定在可信和不可信實體中同時執(zhí)行DAG任務時的實際調度策略。文獻［20］提出一種最短剩余時間優(yōu)先 （distributed shortest remaining time first， D-SRTF），在搶占式調度中，能夠優(yōu)先執(zhí)行剩余執(zhí)行時間最短的任務，適用于動態(tài)變化的任務執(zhí)行時間，需要頻繁地進行任務切換，可能增加調度開銷，不適用于任務切換開銷較大的情況。文獻［21］提出了最早截止時間優(yōu)先 （earliest deadline first，EDF），可能導致長任務長期等待，影響任務的響應時間，不適用于短任務密集型的場景。以上這些任務調度算法都不考慮異構復雜環(huán)境下的通信開銷， 而區(qū)塊鏈DAG任務調度卻是在復雜異構網(wǎng)絡環(huán)境下進行的， 因此以上算法不適用。為解決復雜異構網(wǎng)絡環(huán)境下區(qū)塊鏈DAG任務調度問題，文獻［22］提出了一種改進FPGA遺傳算法，具有較好的全局搜索能力，適用于復雜的任務調度問題，但也需要較長的計算時間和資源。同樣針對復雜異構網(wǎng)絡環(huán)境下區(qū)塊鏈DAG任務調度問題，本文提出了改進分布估計鯨魚任務調度算法（IEWOA）。該算法是一種用于優(yōu)化區(qū)塊鏈DAG網(wǎng)絡中任務調度的算法，其目標是通過合理分配任務和資源，充分滿足區(qū)塊鏈DAG任務調度問題。通過對比了文獻［22］的FPGA、WOA和EDA，IEWOA在參數(shù)性能上有一定的優(yōu)勢。

1 區(qū)塊鏈DAG的任務調度問題建模

區(qū)塊鏈DAG任務調度是在區(qū)塊鏈網(wǎng)絡中，根據(jù)任務之間的依賴關系和執(zhí)行時間，合理地安排任務的執(zhí)行順序，以最小化整體任務的執(zhí)行時間。在區(qū)塊鏈中，任務可以是智能合約的執(zhí)行、交易的確認和數(shù)據(jù)的處理等。另外這些任務可以是獨立的，也可以是非獨立的。獨立任務是指彼此之間沒有依賴關系，可以獨立執(zhí)行的任務。非獨立任務則是指彼此之間存在依賴關系，需要按照一定的順序或條件進行執(zhí)行的任務。獨立任務可以同時進行，而非獨立任務需要滿足其依賴關系才能執(zhí)行。例如，一個任務可能需要等待前一個任務的結果才能開始執(zhí)行，或者多個任務之間存在數(shù)據(jù)共享或交互的依賴關系。因此，區(qū)塊鏈的DAG中既包含獨立任務，也包含非獨立任務如圖2所示，本文研究的任務調度算法需要考慮任務之間的依賴關系和執(zhí)行順序，以實現(xiàn)有效的任務調度和優(yōu)化。

1.1 數(shù)學符號定義

在圖2中，節(jié)點的權值表示任務的執(zhí)行時間，有向邊表示任務間的依賴關系即后繼任務必須在它的前驅任務處理完畢后才能開始執(zhí)行，邊的權值表示任務間的通信開銷。為了準確描述DAG的區(qū)塊鏈任務調度問題的數(shù)學模型，假定區(qū)塊鏈的DAG拓撲為G，給出下列符號定義：

V為有向無環(huán)圖G所有任務的集合，n為任務數(shù)；

P為有向無環(huán)圖G所有處理器節(jié)點的集合，m為任務數(shù)；

E為有向無環(huán)圖G所有任務之間依賴關系的邊集合；

D={d_{i， j}|v_i，v_j∈V}為n×n二維矩陣，d_{i， j}表示v_i任務與依賴的v_j之間數(shù)據(jù)通信開銷；

VP={vp_{i， j}|v_i∈N，p_j∈M}為n×m二維矩陣，vp_{i， j}表示v_i任務在處理節(jié)點p_i的執(zhí)行時間；

ST是處理節(jié)點啟動通信的一維時間矩陣，st_pi是處理節(jié)點p_i的通信啟動時間；

TR是節(jié)點之間的通信速率，tr_pi，pj是處理節(jié)點p_i與p_j的通信速率。

這里假設8個任務，3個處理器的DAG調度問題，圖3就是一個DAG任務模型實例圖。

假設任務v_i是v_j的前繼任務，并且被分別分配到節(jié)點p_k和p_q上執(zhí)行時，通信代價數(shù)學計算公式為

c_{i， j}=st_pm+d_{i， j}tr_pm，pn（1）

如果p_m=p_n就是這兩個任務剛好分配到同一個處理節(jié)點，那么這里就把通信成本設置為0。

1.2 區(qū)塊鏈DAG任務調度目標函數(shù)

DAG的makespan是指在一個有向無環(huán)圖中完成所有任務所需的最長時間。在一個DAG中，每個任務都有一個預計的執(zhí)行時間。每個任務的執(zhí)行時間可能不同，且任務之間存在依賴關系。例如，任務B可能依賴于任務A的完成，只有在任務A完成后才能開始執(zhí)行任務B。DAG的makespan是指在滿足所有任務依賴關系的前提下，完成所有任務所需要的最長時間。假設每個任務的執(zhí)行時間已知，并且所有任務的依賴關系已經確定，可以使用拓撲排序算法來計算DAG的makespan。通過拓撲排序算法，可以有效地計算DAG的makespan，并找到最優(yōu)的任務執(zhí)行順序，以最小化完成所有任務所需的時間。

為了準確地描述目標函數(shù)的意義，下面給出異構網(wǎng)絡環(huán)境下DAG 任務調度問題中常見的定義及公式。

定義1 最早開始時間（earliest start time，EST）。

任務v_i在p_k上的最早開始時間為

EST（v_i，p_k）=max{FTT（p_k），maxv_m∈pred（v_i）{AFT（v_m）+c_m，i）}}（2）

其中：FTT（p_k）代表p_k完成最后一個任務的時間；AFT（v_m）代表v_m完成最后一個任務的時間。

定義2 最早完成時間（earliest finish time，EFT）。

EFT（v_i，p_k）=EST（v_i，p_k）+c_i，k（3）

定義3 調度長度（makespan）。

makespan=max{AFT（v_exit）}（4）

有序DAG是一個有向無環(huán)圖，為NP問題^［18］。本文目標為最小化并行應用程序的最早完成時間［makespan］，參照文獻［1］，目標函數(shù)的公式為

min{max{AFT（v_exit）}}（5）

其中：AFT（v_exit）表示出口節(jié)點的實際完成時間。

跨度是一個主要、常見的目標，指的是調度的長度，也就是從第一個任務開始運行到最后一個任務運行完畢所經歷的時間?？缍仍叫≌f明調度策略越好。當用戶向網(wǎng)格系統(tǒng)提交任務后，最大的愿望是網(wǎng)格系統(tǒng)盡快完成自己的任務。

以上構建的區(qū)塊鏈DAG任務調度數(shù)學模型正是考慮異構復雜環(huán)境下的通信開銷， 為解決復雜異構網(wǎng)絡環(huán)境下區(qū)塊鏈DAG任務調度問題，文獻［22］提出了一種改進FPGA遺傳算法，具有較好的全局搜索能力，適用于復雜的任務調度問題，但也需要較長的計算時間和資源。而本文同樣針對復雜異構網(wǎng)絡環(huán)境下的區(qū)塊鏈DAG任務調度問題，提出了一種改進分布估計鯨魚任務調度算法。該算法融合分布估計的搜索空間采樣和統(tǒng)計學習來預測搜索的最佳區(qū)域， 進而產生優(yōu)秀的新個體，從而提升算法的全局搜索能力和收斂性。另外本文之所以選用鯨魚算法進行改進優(yōu)化，是因為WOA的三個種群更新機制相互獨立，使得算法在尋優(yōu)階段能夠分別運行及控制全局探索和局部開發(fā)過程。與其他群體智能優(yōu)化算法相比，WOA不需要人為設置各種控制參數(shù)值，簡化了算法的使用并降低了應用難度，在多種測試中WOA展現(xiàn)出了優(yōu)于蟻群算法和粒子群算法等其他智能優(yōu)化算法的尋優(yōu)性能^{［23，24］}。

2 算法描述

2.1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法（whale optimization algorithm，WOA）是一種基于自然界鯨魚狩獵行為的元啟發(fā)式算法。該算法模擬了鯨魚的社會行為和狩獵策略，用于解決優(yōu)化問題。鯨魚優(yōu)化算法的基本思想是通過模擬鯨魚的追蹤行為和呼叫行為來搜索最優(yōu)解。算法中的個體被稱為鯨魚，它們在搜索空間中移動并調整自身位置和速度。每個鯨魚根據(jù)自身的適應度值和全局最優(yōu)解來更新自己的位置和速度，以尋找更優(yōu)的解。鯨魚優(yōu)化算法的主要步驟包括初始化種群、計算適應度值、更新位置和速度、調整搜索范圍等。通過多次迭代和交互，鯨魚優(yōu)化算法逐漸收斂到最優(yōu)解。鯨魚優(yōu)化算法具有以下特點：

a）算法簡單易實現(xiàn)，不需要過多的參數(shù)設置；

b）可以應用于各種優(yōu)化問題，包括連續(xù)優(yōu)化和離散優(yōu)化；

c）具有較好的全局搜索能力和收斂性能；

d）算法具有自適應性，能夠自動調整搜索范圍。

鯨魚優(yōu)化算法已經在工程優(yōu)化、機器學習、圖像處理等多個領域得到應用。它在解決復雜優(yōu)化問題方面具有一定的優(yōu)勢，并且在一些實際問題中取得了較好的效果。

鯨魚優(yōu)化算法包括的這三個核心算子，如下所示。

a）包圍獵物。該行為數(shù)學模型等式表示為

Xⁱ（t+1）=|Xⁱ_best（t）－A·|CXⁱ_best（t）－Xⁱ（t）||（6）

其中：t表示當前迭代次數(shù)；A和C表示相關系數(shù)；Xⁱ（t）表示當前位置向量；Xⁱ_best（t）表示現(xiàn)有最優(yōu)解。

b）氣泡網(wǎng)攻擊方式。該行為數(shù)學模型等式表示為

Xⁱ（t+1）=|Xⁱ_best（t）－Xⁱ（t）|·e^rz·cos（2πz）+Xⁱ_best（t）（7）

其中：|Xⁱ_best（t）－Xⁱ（t）|是鯨魚i到食物的距離；z是［-1，1］隨機值；r是螺旋常數(shù)。

c）尋找獵物。當Agt;1時，鯨魚根據(jù)自身位置隨機搜索獵物。該行為數(shù)學模型等式表示為

Xⁱ（t+1）=|Xⁱ_rand（t）－A·|CXⁱ_rand（t）－Xⁱ（t）||（8）

其中：Xⁱ_rand（t）是隨機鯨魚在種群中的位置；控制參數(shù)向量A=2rand·a－a和C=2rand，a隨著迭代次數(shù)的增加從2線性減小到0，rand是分布于［0，1］的隨機向量。

2.2 分布估計算法

分布估計算法 （EDA）^{［25～27］}是一種新興的基于統(tǒng)計學原理的隨機優(yōu)化算法。EDA與遺傳算法（GA）、鯨魚算法等優(yōu)化算法有著明顯的區(qū)別。GA 采用交叉和變異等操作產生新個體， EDA 則通過對搜索空間采樣和統(tǒng)計學習來預測搜索的最佳區(qū)域， 進而產生優(yōu)秀的新個體。相比于GA 基于基因的微觀層面的進化方式， EDA采用基于搜索空間的宏觀層面的進化方法， 具備更強的全局搜索能力和更快的收斂速度。EDA是一類用于估計未知概率分布的方法，通過從已有數(shù)據(jù)中學習概率分布的參數(shù)或者通過擬合一個合適的概率分布函數(shù)來近似未知分布。常見的分布估計算法包括最大似然估計（maximum likelihood estimation，MLE）、貝葉斯估計（Bayesian estimation）、核密度估計（kernel density estimation，KDE）等。分布估算法的核心算子是概率模型的建立。在分布估計算法中，表示解空間分布的概率模型是一個概率向量p（x）=（p（x₁），p（x₂），…，p（x_n）），其中p（x_i）表示位置i上取某數(shù)值的概率。概率模型的計算公式如下：

p_j+1（x）=（1－a）p_j（x）+a1N∑Nj=1x^j_i（9）

其中：p_j（x）表示第j次種群解空間的概率向量；x¹_i，x²_i，…，x^N_i表示N個優(yōu)質解；x^j_i表示位置i上的取值；a表示學習因子。

2.3 改進的分布估計鯨魚DAG任務調度分配優(yōu)化算法

1）編碼

采用十進制整數(shù)編碼。每一位置代表一種可行的任務調度分配方案。每一位置有2×n個維數(shù)（n表示需要分配的任務數(shù)）。其中每一維是1～n的十進制數(shù)。前面n維代表任務的序列，后面n維代表分配給任務的相應處理器，如表1所示。任務V₁提供給P₂處理器，任務V₂提供給P₁處理器，由此類推。

2）算法主要參數(shù)

a）種群數(shù)（PopSize），一般取30～50。 其實對于大部分的問題20個種群規(guī)模已經足夠可以取得好的結果， 不過對于比較難的問題或者特定類別的問題， 種群數(shù)可以取到100 或 200?？梢酝ㄟ^仿真的結果而定。

b）單個種群每一維取值（TaskNum），前半段由算法設定的任務數(shù)數(shù)決定，后半段由給定的處理節(jié)點數(shù)決定。

3） 算法流程

WOA的主要優(yōu)點是簡單性和速度。然而，WOA缺乏堅實的數(shù)學基礎，容易收斂到局部最優(yōu)解。為了克服這些問題，本文嘗試在WOA中通過對搜索空間采樣和統(tǒng)計學習來預測搜索的最佳區(qū)域， 進而產生優(yōu)秀的新個體。相比于FPGA 基于基因和WOA基于個體的微觀層面的進化方式， EDA采用基于搜索空間的宏觀層面的進化方法， 具備更強的全局搜索能力和更快的收斂速度，進而快速找到最優(yōu)解。以下是整個IEWOA算法的具體步驟：

a）初始化迭代計數(shù)器、種群規(guī)模、最大迭代次數(shù)等初始參數(shù)，并隨機產生初始種群。

b）通過式（5）計算每個鯨魚的最佳目標函數(shù)值。

c）進入算法的主循環(huán)。如果plt;0.5且|A|lt;1，則每頭鯨魚將根據(jù)式（6）更新當前位置，否則plt;0.5且|A|≥1根據(jù)式（8）更新鯨魚個體位置。如果p≥0.5，每只鯨魚都根據(jù)式（7）更新其位置。

d）根據(jù)式（9）建立種群的概率模型，并進行隨機采樣產生新的群體。

e）排序。對新的鯨魚種群計算評估，以找到全局最優(yōu)的鯨魚個體及其位置，并更新最優(yōu)解。

f）如果滿足算法的終止條件（最大迭代次數(shù)），則結束并輸出最優(yōu)解；否則，轉到步驟b）并繼續(xù)算法迭代。

整個算法的流程如圖4所示。

3 模擬實驗與數(shù)據(jù)分析

模擬實驗平臺在由十臺機器組成的一組機器上進行測試。每臺機器的配置如下：操作系統(tǒng)為Cent OS 5.4系統(tǒng)；CPU為Intel Core i5-4590；內存為8 GB。實驗的區(qū)塊鏈DAG任務圖采用隨機產生，除了把 IEWOA 與傳統(tǒng)的 EDA 算法和WOA進行比較，還將IEWOA與文獻［24］的FPGA進行了比較，分別測試它們的收斂速度和尋優(yōu)能力等方面性能。在隨機區(qū)塊鏈DAG任務圖中，任務處理節(jié)點個數(shù)從 10變化到 100，每次增加 10，每個任務的后繼任務個數(shù)取均值為 v/10的隨機數(shù)，任務在各處理機上的執(zhí)行時間為［1，40］的任意數(shù)，任務間的數(shù)據(jù)傳輸量為［100，500］的隨機數(shù)；隨機生成處理機的通信啟動時間為［1，10］的整數(shù)，處理機間的傳輸率為［1，10］的任意數(shù)。

1）尋優(yōu)性能

參數(shù)設置處理節(jié)點數(shù)為3，種群數(shù)為20，算法的迭代次數(shù)為100。尋優(yōu)性能主要比較算法的尋最優(yōu)解的能力和平均最優(yōu)解的能力，圖5是不同任務數(shù)（30，50，70，90）情況下的算法尋最優(yōu)解能力對比，圖6是各算法平均最優(yōu)解（實驗重復20次取平均）的能力對比。

從圖5可以觀察到IEWOA對比其他三個算法，在任務數(shù)分別為30、50、70、90的分配要求下，每次都能獲取更優(yōu)的目標函數(shù)值。雖然任務數(shù)為70和90 的情況下四種算法所獲得最優(yōu)目標函數(shù)值相近，但任務數(shù)在30和50時IEWOA所獲得目標函數(shù)值優(yōu)勢較為明顯。說明在任務分配和計算消耗資源較少的情況下，IEWOA具有更強的全局尋優(yōu)的能力。

從圖6不難發(fā)現(xiàn)IEWOA尋找平均目標函數(shù)值的優(yōu)勢更為明顯，而且更能體現(xiàn)算法的全局尋優(yōu)能力和算法收斂性能。不僅對比傳統(tǒng)的WOA，還是相比于FPGA（基于基因）和WOA（基于個體）的微觀層面的進化方式， 融合EDA采用基于搜索空間的宏觀層面的IEWOA明顯具有更強全局搜索能力和更快的收斂速度。

2）改變種群規(guī)模

參數(shù)設置任務數(shù)為60，處理節(jié)點數(shù)為3，算法的迭代次數(shù)為300。圖7（a）是種群數(shù)分別為10、30、60、90、120的情況下，四種算法的尋優(yōu)能力比較。很顯然隨著種群數(shù)的遞增，四個算法都能隨著種群數(shù)的增加而獲得更好的目標函數(shù)值。WOA、EDA和FPGA隨著種群數(shù)擴大所獲得的最優(yōu)目標函數(shù)值趨近，而很明顯IEWOA較其他三種算法始終能獲得更優(yōu)的目標函數(shù)值，而且隨著種群數(shù)的增加IEWOA優(yōu)勢更加明顯。

為進一步驗證大種群規(guī)模對算法的影響及體現(xiàn)各算法的性能，參數(shù)設置同圖（a），而種群數(shù)分別為120、150、180、210、240的情況下，驗證四種算法的獲得的最優(yōu)目標函數(shù)值的能力，實驗結果如圖7（b）所示。

從圖7（b）能發(fā)現(xiàn)當種群數(shù)從120遞增到240時，四種算法都隨著種群數(shù)的遞增所獲得最優(yōu)目標函數(shù)值也逐漸變小。說明種群數(shù)的增加確實能增加算法全體多樣性從而影響算法的全局尋優(yōu)能力，但同時可發(fā)現(xiàn)IEWOA始終都比其他三種算法所獲得最優(yōu)解更好一點，而且隨種群數(shù)的增加這種優(yōu)勢一直保持。隨著種群數(shù)的增加，其他三種算法也逐漸能尋找到更好的最優(yōu)解，同時也發(fā)現(xiàn)改進FPGA比傳統(tǒng)EDA和WOA尋優(yōu)能力要更強一些。最終這次實驗發(fā)現(xiàn)隨著種群數(shù)的增加四種算法都能不斷逼近全局最優(yōu)解并且最終所獲得最終目標函數(shù)值都越來越接近，但IEWOA始終能比其他算法找到更優(yōu)的解。這是由于IEWOA在傳統(tǒng)WOA中建立概率模型有利地保證了算法平穩(wěn)地向最優(yōu)解空間靠近，指導了算法的進化方向，使得IEWOA較其他算法具有更好的尋優(yōu)能力。

3）改變迭代次數(shù)

為驗證算法的迭代次數(shù)對各算法性能的影響，在處理節(jié)點數(shù)為3，種群數(shù)為10，任務數(shù)為60的情況下，改變迭代次數(shù)依次100、200、300、400、500情況下各算法的尋優(yōu)能力對比，具體實驗結果如圖8（a）所示。

初始種群的產生由于隨機性，質量不會隨著迭代次數(shù)的改變而發(fā)生變化。圖8（a）展示迭代次數(shù)對調度結果的影響，IEWOA在迭代次數(shù)為100時與EDA尋優(yōu)能力近似，但隨著迭代次數(shù)增加IEWOA較EDA、WOA和FPGA都略勝一籌，并且迭代次數(shù)達到500時，四種算法所獲得最優(yōu)目標函數(shù)值非常接近。為進一步驗證迭代對四種算法性能的影響，再一次將迭代次數(shù)依次從600每次遞加100直到1 000，具體的實驗結果如圖8（b）所示。

從圖8（b）可以發(fā)現(xiàn)，算法的迭代次數(shù)600時，F(xiàn)PGA、WOA和EDA三算法所獲得最優(yōu)目標函數(shù)值近似，而IEWOA所獲得最優(yōu)目標函數(shù)值要小于前三種算法。但隨著迭代次數(shù)逐漸遞增到1 000時，雖然IEWOA全局尋優(yōu)的能力都略強于前三種算法，但四種算法都在不斷收斂到全局最優(yōu)解，而且迭代次數(shù)越多四種算法所獲得最優(yōu)解越近似趨近于全局最優(yōu)解。這也說明當算法迭代次數(shù)足夠時四種算法都會無限逼近全局最優(yōu)解，但是由于計算資源的有限必然需要限制迭代次數(shù)，這樣IEWOA在同等情況下就具有更好的實用價值。

4）算法的執(zhí)行時間

參數(shù)設置為處理節(jié)點數(shù)為3，種群數(shù)為10和算法的迭代次數(shù)為1 000，比較了IEWOA、EDA、WOA和FPGA四種算法在任務數(shù)分別為30、50、70、90、110、130、150、170、190、210、230、250時，獲的最優(yōu)解所耗費的時間，如表2所示。

從表2發(fā)現(xiàn)在任務數(shù)從30遞增到130時，F(xiàn)PGA獲得最優(yōu)解所耗費的時間要少于IEWOA、WOA和EDA三算法。這說明在任務數(shù)較少的情況下，F(xiàn)PGA由于算法變異因子特性獲得不容易陷入局部最優(yōu)解而能更快地找到全局最優(yōu)解，而IEWOA、WOA和EDA三種算法耗費時間近似。但是當任務數(shù)從150遞增到250時，IEWOA隨著任務數(shù)的增大獲最優(yōu)解所耗費時間較其他三算法都要少，而且隨著任務數(shù)的增大這種優(yōu)勢越明顯，同時FPGA對比傳統(tǒng)EDA和WOA表現(xiàn)又要好一些。通過比較可以發(fā)現(xiàn)，IEWOA在前期任務數(shù)不多的情況下，算法在尋優(yōu)方面的性能并不是太明顯而且有時會顯得落后于FPGA，但是隨著任務數(shù)和計算量的增加，IEWOA的全局尋優(yōu)能力和性能優(yōu)勢就比較突顯。為更全面驗證算法的整體尋優(yōu)能力和以上分析結果，把實驗設定任務數(shù)從30每次遞增10直到250為止，四種算法獲最優(yōu)解所耗費的時間如圖9（a）所示。

圖9（a）進一步驗證在任務數(shù)隨30遞增到100時，四種算法在獲最優(yōu)解所耗費的時間比較接近，任務數(shù)從100到130時，四種算法任務完成獲最優(yōu)解所耗費的時間開始有所分化，但分化不算明顯，尤其IEWOA、WOA和FPGA三種算法此時性能還比較近似。隨著任務數(shù)從130到150再到250，四種算法的性能開始明顯分化，傳統(tǒng)EDA和WOA比FPGA和IEWOA該方面的性能就明顯落后，同時IEWOA的較其他三種算法優(yōu)勢也逐漸明顯。為避免由于一兩次算法運行可能產生隨機性導致算法驗證不可靠，下面進一步對任務數(shù)30到250的實驗反復進行10次，最后總結出四種算法的平均任務完成時間如圖9（b）所示。

圖9（b）驗證任務數(shù)從30遞增到110時，在計算平均完成時間下四種算法在獲最優(yōu)解所耗費的時間非常接近，并且隨任務數(shù)的遞增較平穩(wěn)遞增，此時能避免由于算法隨機初始化數(shù)據(jù)導致算法性能波動等不良因素。說明計算平均完成時間時四種算法在任務數(shù)30～110時性能都比較接近，然后隨著任務數(shù)130～250，四種算法的性能開始分化，F(xiàn)PGA和IEWOA的性能優(yōu)勢開始顯現(xiàn)，傳統(tǒng)EDA和WOA隨著任務數(shù)的遞增性能一直比較接近。同時也發(fā)現(xiàn)FPGA和IEWOA在任務數(shù)130～170的遞增過程中性能近似，IEWOA略優(yōu)于FPGA。在任務數(shù)170～250兩算法的性能優(yōu)勢開始分化，這時IEWOA明顯開始優(yōu)于FPGA，充分說明IWEOA具有更好的尋優(yōu)能力。

4 結束語

總之IEWOA對于解決區(qū)塊鏈有向無環(huán)圖中的非獨立任務調度問題具有較好的性能，可以為該領域的研究和應用提供有力支持。最后通過仿真實驗，從設置特定參數(shù)、改變種群規(guī)模、改變迭代次數(shù)三方面依次對比了IEWOA與EDA、FPGA、WOA的尋優(yōu)能力，從而充分地展示了IEWOA的優(yōu)勢，也說明IEWOA相比于FPGA和WOA的微觀層面的進化方式， 其融入EDA采用基于搜索空間的宏觀層面的進化方式， 從而獲得比其他三種算法更強的全局搜索能力和更快的收斂速度。

參考文獻：

［1］Alladi T， Chamola V， Parizi R M， et al. Blockchain applications for industry 4.0 and industrial IoT： a review［J］. IEEE Access， 2019， 7（1）： 176935-176951.

［2］Hsiao S J， Sung W T. Blockchain-based supply chain information sharing mechanism［J］. IEEE Access， 2022， 10（1）： 78875-78886.

［3］Li Zhi， Barenji A V， Huang G Q. Toward a blockchain cloud manufacturing system as a peer to peer distributed network platform［J］. Robotics and Computer Integrated Manufacturing， 2018， 54（1）： 133-144.

［4］Giungato P， Rana R， Tarabella A， et al. Current trends in sustainability of bitcoins and related blockchain technology［J］. Sustainability， 2016， 9（12）： 1-11.

［5］Elsayeh M， Ezzat K A， El-Nashar H， et al. Cybersecurity architecture for the internet of medical things and connected devices using blockchain［J］. Biomedical Engineering Applications Basis and Communications， 2021， 33（2）： 2150013.

［6］Dorri A， Kanhere S S， Jurdak R， et al. LSB： a lightweight scalable blockchain for IoT security and anonymity［J］. Journal of Parallel and Distributed Computing， 2019， 134（1）： 180-197.

［7］Ravishankar R， Daniel C. Perspectives on emerging directions in using IoT devices in blockchain applications［J］. Internet of Things， 2020， 10（1）： 100079.

［8］Biswas S， Sharif K， Li F， et al. PoBT： a lightweight consensus algorithm for scalable IoT business blockchain［J］. Internet of Things， 2019， 7（3）： 2343-2355.

［9］Mohanty S N， Ramya K C， Rani， S S， et al. An efficient lightweight integrated blockchain（ELIB） model for IoT security and privacy［J］. Future Generation Computer Systems， 2020， 102（1）： 1027-1037.

［10］Huang Junqin， Kong Linghe， Chen Guihai， et al. Towards secure industrial IoT： blockchain system with credit-based consensus mechanism［J］. IEEE Trans on Industrial Informatics， 2019， 15（6）： 3680-3689.

［11］Cui Laizhong， Yang Shu， Chen Ziteng， et al. An efficient and compacted DAG-based blockchain protocol for Industrial Internet of Things［J］. IEEE Trans on Industrial Informatics， 2020， 16（6）： 4134-4145.

［12］Zhou Tong， Li Xiaofeng， Zhao He. DLattice： a permission-less blockchain based on DPoS-BA-DAG consensus for data tokenization［J］. IEEE Access， 2019， 7（1）： 39273-39287.

［13］Yuan Yong， Wang Yuefei. Blockchain and cryptocurrencies： model， techniques， and applications［J］. IEEE Trans on Systems Man amp; Cybernetics Systems， 2018， 48（9）： 1421-1428.

［14］Novo O. Blockchain meets IoT： an architecture for scalable access management in IoT［J］. IEEE Internet of Things Journal， 2018， 5（2）： 1184-1195.

［15］Makhdoom I， Abolhasan M， Abbas H， et al. Blockchain’s adoption in IoT： the challenges， and a way forward［J］. Journal of Network amp; Computer Applications， 2019， 125（1）： 251-279.

［16］Andoni M， Robu V， Flynn D， et al. Blockchain technology in the energy sector： a systematic review of challenges and opportunities［J］. Renewable amp; Sustainable Energy Reviews， 2019， 100（1）： 143-174.

［17］Kotilevets D， Ivanova A， Romanov O， et al. Implementation of directed acyclic graph in blockchain network to improve security and speed of transactions［J］. IFAC-PapersOnLine， 2018， 51（30）： 693-696.

［18］陳紅華， 崔翛龍， 王耀杰. 基于多種云環(huán)境的任務調度算法綜述［J］. 計算機應用研究， 2023， 40（10）： 2889-2895. （Chen Honghua， Cui Xiaolong， Wang Yaojie. Summary of task scheduling algorithms based on multiple cloud environments［J］. Application Research of Computers， 2023， 40（10）： 2889-2895.）

［19］Cheng Yuxia， Wu Zhiwei， Liu Kui， et al. Smart DAG tasks scheduling between trusted and untrusted entities using the MCTS method［J］. Sustainability， 2019， 11（7）： 1826.

［20］Gao Chengxi， Lee V， Li Keqin. D-SRTF： distributed shortest remaining time first scheduling for data center networks［J］. IEEE Trans on Cloud Computing， 2021， 9（2）： 562-575.

［21］Xu Jiang， Nan Guan， Xiang Long. Decomposition-based real-time scheduling of parallel tasks on multicores platforms［J］. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems， 2020， 39（10）： 2319-2332.

［22］曹懷虎， 張艷梅， 王堅， 等. DAG區(qū)塊鏈中基于確定性退火技術的融合分割遺傳任務調度算法［J］. 中國科學： 信息科學， 2020， 50（2）： 261-274. （Chao Huaihu， Zhang Yanmei， Wang Jian， et al. Fusion-partitioning genetic task scheduling algorithm based on deterministic annealing technology in DAG blockchains［J］. Scientia Sinica： Informationis， 2020， 50（2）： 261-274.）

［23］Mirjalili S， Lewis A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016， 95（5）： 51-67.

［24］Mohamed A， Ei A， Ahmed A， et al. Whale optimization algorithm and moth-flame optimization for multilevel thresholding image segmentation［J］. Expert Systems with Applications， 2017， 83（1）： 242-256.

［25］Sun Yanan， Yen G G， Yi Zhang. Improved regularity model-based EDA for many-objective optimization［J］. IEEE Trans on Evolutionary Computation， 2018， 22（5）： 662-678.

［26］Shirazi A， Ceberio J， Lozano J A. EDA+： estimation of distribution algorithms with feasibility conserving mechanisms for constrained continuous optimization［J］. IEEE Trans on Evolutionary Computation， 2022， 26（5）： 1144-1156.

［27］Platel M D， Schliebs S， Kasabov N. Quantum-inspired evolutionary algorithm： a multimodel EDA［J］. IEEE Trans on Evolutionary Computation， 2009， 13（6）： 1218-1232.