改進(jìn)的分布估計(jì)鯨魚算法求解區(qū)塊鏈DAG任務(wù)調(diào)度問題

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

關(guān)鍵詞：DAG；分布估計(jì)；鯨魚算法；任務(wù)調(diào)度

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

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

1 區(qū)塊鏈DAG的任務(wù)調(diào)度問題建模

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

1.1 數(shù)學(xué)符號定義

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

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

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

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

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

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

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

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

這里假設(shè)8個(gè)任務(wù)，3個(gè)處理器的DAG調(diào)度問題，圖3就是一個(gè)DAG任務(wù)模型實(shí)例圖。

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

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

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

1.2 區(qū)塊鏈DAG任務(wù)調(diào)度目標(biāo)函數(shù)

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

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

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

任務(wù)v_i在p_k上的最早開始時(shí)間為

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完成最后一個(gè)任務(wù)的時(shí)間；AFT（v_m）代表v_m完成最后一個(gè)任務(wù)的時(shí)間。

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

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

定義3 調(diào)度長度（makespan）。

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

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

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

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

跨度是一個(gè)主要、常見的目標(biāo)，指的是調(diào)度的長度，也就是從第一個(gè)任務(wù)開始運(yùn)行到最后一個(gè)任務(wù)運(yùn)行完畢所經(jīng)歷的時(shí)間。跨度越小說明調(diào)度策略越好。當(dāng)用戶向網(wǎng)格系統(tǒng)提交任務(wù)后，最大的愿望是網(wǎng)格系統(tǒng)盡快完成自己的任務(wù)。

以上構(gòu)建的區(qū)塊鏈DAG任務(wù)調(diào)度數(shù)學(xué)模型正是考慮異構(gòu)復(fù)雜環(huán)境下的通信開銷， 為解決復(fù)雜異構(gòu)網(wǎng)絡(luò)環(huán)境下區(qū)塊鏈DAG任務(wù)調(diào)度問題，文獻(xiàn)［22］提出了一種改進(jìn)FPGA遺傳算法，具有較好的全局搜索能力，適用于復(fù)雜的任務(wù)調(diào)度問題，但也需要較長的計(jì)算時(shí)間和資源。而本文同樣針對復(fù)雜異構(gòu)網(wǎng)絡(luò)環(huán)境下的區(qū)塊鏈DAG任務(wù)調(diào)度問題，提出了一種改進(jìn)分布估計(jì)鯨魚任務(wù)調(diào)度算法。該算法融合分布估計(jì)的搜索空間采樣和統(tǒng)計(jì)學(xué)習(xí)來預(yù)測搜索的最佳區(qū)域， 進(jìn)而產(chǎn)生優(yōu)秀的新個(gè)體，從而提升算法的全局搜索能力和收斂性。另外本文之所以選用鯨魚算法進(jìn)行改進(jìn)優(yōu)化，是因?yàn)閃OA的三個(gè)種群更新機(jī)制相互獨(dú)立，使得算法在尋優(yōu)階段能夠分別運(yùn)行及控制全局探索和局部開發(fā)過程。與其他群體智能優(yōu)化算法相比，WOA不需要人為設(shè)置各種控制參數(shù)值，簡化了算法的使用并降低了應(yīng)用難度，在多種測試中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)解。算法中的個(gè)體被稱為鯨魚，它們在搜索空間中移動并調(diào)整自身位置和速度。每個(gè)鯨魚根據(jù)自身的適應(yīng)度值和全局最優(yōu)解來更新自己的位置和速度，以尋找更優(yōu)的解。鯨魚優(yōu)化算法的主要步驟包括初始化種群、計(jì)算適應(yīng)度值、更新位置和速度、調(diào)整搜索范圍等。通過多次迭代和交互，鯨魚優(yōu)化算法逐漸收斂到最優(yōu)解。鯨魚優(yōu)化算法具有以下特點(diǎn)：

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

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

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

d）算法具有自適應(yīng)性，能夠自動調(diào)整搜索范圍。

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

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

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

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

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

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

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］隨機(jī)值；r是螺旋常數(shù)。

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

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

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

2.2 分布估計(jì)算法

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

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個(gè)優(yōu)質(zhì)解；x^j_i表示位置i上的取值；a表示學(xué)習(xí)因子。

2.3 改進(jìn)的分布估計(jì)鯨魚DAG任務(wù)調(diào)度分配優(yōu)化算法

1）編碼

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

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

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

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

3） 算法流程

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

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

b）通過式（5）計(jì)算每個(gè)鯨魚的最佳目標(biāo)函數(shù)值。

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

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

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

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

整個(gè)算法的流程如圖4所示。

3 模擬實(shí)驗(yàn)與數(shù)據(jù)分析

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

1）尋優(yōu)性能

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

［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)境的任務(wù)調(diào)度算法綜述［J］. 計(jì)算機(jī)應(yīng)用研究， 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］曹懷虎， 張艷梅， 王堅(jiān)， 等. DAG區(qū)塊鏈中基于確定性退火技術(shù)的融合分割遺傳任務(wù)調(diào)度算法［J］. 中國科學(xué)： 信息科學(xué)， 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.