戚文杰 史培中 古春生 景征駿

摘 要：物聯(lián)網與區(qū)塊鏈融合過程中，實用拜占庭容錯（PBFT）算法存在通信開銷大、時延高且無法根據場景與設備差異進行合理劃分的不足。為滿足物聯(lián)網多場景應用的問題，提出了一種基于綜合評價的改進實用拜占庭容錯算法。首先，對節(jié)點進行基于性能與信譽值加權的綜合評價篩選出符合特定場景需求的節(jié)點；然后，進行基于節(jié)點綜合評價的聚類，形成雙層網絡架構；最后，將共識過程分為子集群共識和主集群共識。實驗結果表明，CE-PBFT擁有較高的容錯性和場景適應性，且當場景節(jié)點數達到100時，在通信開銷和共識時延方面較PBFT分別有著93.9%和87.8%的性能優(yōu)化。

關鍵詞：物聯(lián)網；區(qū)塊鏈；實用拜占庭容錯；多場景；綜合評價

中圖分類號：TP393?? 文獻標志碼：A

文章編號：1001-3695（2024）03-005-0676-07

doi：10.19734/j.issn.1001-3695.2023.06.0288

Improved PBFT consensus algorithm for multi-scenario Internet of Things

Qi Wenjie，Shi Peizhong，Gu Chunsheng，Jing Zhengjun

（School of Computer Engineering，Jiangsu University of Technology，Changzhou Jiangsu 213001，China）

Abstract：Aiming at the problems in the practical Byzantine fault tolerance（PBFT） algorithm，such as large communication overhead，high delay and inability to reasonably divide according to the differences of scenarios and devices，cannot meet the multi-scenario application of Internet of Things（IoT） in the integration of IoT and blockchain，this paper proposed an improved PBFT consensus algorithm based on comprehensive evaluation（CE-PBFT）.Firstly，it conducted comprehensive evaluation of nodes based on the weighted performance and reputation value to screen out nodes that met the needs of specific scenarios.After that，it conducted clustering based on the comprehensive evaluation of nodes to form a two-layer network architecture.Finally，it divided the consensus process into sub-cluster consensus and main cluster consensus.The experimental results show that CE-PBFT has high fault tolerance and scenario adaptability，and when the number of scenario nodes reach 100，it respectively has 93.9% and 87.8% performance optimisation over PBFT in terms of communication overhead and consensus delay.

Key words：Internet of Things；blockchain；PBFT；multi-scenario；comprehensive evaluation

0 引言

近年來，隨著5G等基礎設施部署和應用的加速推進，互聯(lián)智能設備數量呈現爆炸式增長，物聯(lián)網的發(fā)展環(huán)境不斷優(yōu)化，這主要得益于物聯(lián)網技術的廣泛應用，為物理世界更直接地整合到計算機網絡世界創(chuàng)造了機會［1］。如今，物聯(lián)網在智慧城市［2］、交通、能源、金融、家居、醫(yī)療等多個方面都有應用，但是物聯(lián)網的不同應用領域對該場景下的設備條件也存在著需求差異，同時還存在能效低以及安全性差等問題。而區(qū)塊鏈技術具有的去信任化、自動化、匿名化、不可竄改等特點［3］以及基于加密算法的信息交換為解決

物聯(lián)網的安全問題帶來了希望［4］。但是，將目前已有的區(qū)塊鏈技術直接應用于大規(guī)模物聯(lián)網系統(tǒng)并不可行，其無法保證物聯(lián)網發(fā)展的三要素，即安全性、拓展性、高能效之間的平衡。這是由于傳統(tǒng)的區(qū)塊鏈共識機制普遍存在高能耗與高時延的問題，對于物聯(lián)網場景下的一般節(jié)點是無法承受的，同時現有共識機制無法做到根據物聯(lián)網的不同應用場景篩選出合適的節(jié)點，例如智慧存儲需要高存儲節(jié)點，而車聯(lián)網則對網絡通信有著更大的需求。由于共識機制是區(qū)塊鏈的核心技術，與區(qū)塊鏈的資源消耗、安全性、可擴展性、性能效率密切相關，設計出適合物聯(lián)網多場景需求、低開銷、高效率要求的共識算法是實現區(qū)塊鏈與物聯(lián)網有機融合的關鍵。

目前，從去中心化角度可將區(qū)塊鏈分為公有鏈、聯(lián)盟鏈以及私有鏈。公有鏈主要是以工作量證明（power of work，PoW）［5］、權益證明（proof of stake，PoS）［6］、委托權益證明（de-legated proof of stake，DPoS）［7］作為概率一致性共識機制的代表。公有鏈共識機制雖然賦予不同節(jié)點同等權限，但是犧牲了效率，同時還存在隱私保護問題，因此公有鏈共識機制并不適用于對效率與安全有著高要求的物聯(lián)網場景。私有鏈中節(jié)點的寫入權限由內部控制，私有程度過高的同時卻只能容納少量節(jié)點，因此私有鏈共識機制并不適用于大規(guī)模物聯(lián)網場景。聯(lián)盟鏈主要以實用拜占庭容錯（PBFT）機制［8］的絕對一致性共識機制為代表。聯(lián)盟鏈共識機制既能帶給大家需要的信息，又能保證自己的隱私不會被泄露，同時相較于公有鏈效率也有很大提升，滿足了物聯(lián)網高效率的要求，因此聯(lián)盟鏈共識機制更加適用于物聯(lián)網場景。表1列出了PoW、PoS、DPoS、PBFT四種算法的通信開銷、吞吐量、響應時間、容錯性、可擴展性和主要資源占用［9，10］。PBFT憑借1/3的拜占庭容錯、秒級的響應時間以及可達數千的吞吐量［10］，被認為是最適合物聯(lián)網系統(tǒng)的共識算法［11］。

PBFT 共識算法由Castro等人［8］提出，該算法實現了在異步環(huán)境下復制狀態(tài)機，使其能夠在現實場景得到應用。傳統(tǒng)PBFT共識流程如圖1所示，共識流程的核心為pre-prepare、prepare、commit三個階段，其中最為重要的commit階段既保證了最終不會提交和已經提交的消息沖突的消息，同時在惡意主節(jié)點存在的情況下還能保證算法的安全性。可是PBFT算法本身隨機選取主節(jié)點的方式并未將節(jié)點自身條件是否滿足當前場景需要考慮進去，這會導致主節(jié)點沒有能力進行共識的情況發(fā)生。另外，其通信復雜度O（N2）為平方級，平方級的通信復雜度將導致其會因為節(jié)點個數的增加而顯著影響性能，一般地，當節(jié)點個數達到100左右時性能下降極快。同時其主要占用的資源為通信資源，這就導致了以移動通信技術為核心的物聯(lián)網為了完成共識不得不付出大量的通信代價，這樣做無疑是增加了整個物聯(lián)網的通信壓力。若當前場景下網絡不穩(wěn)定，則通信時延會顯著增大。

目前已經有對PBFT共識算法的相關研究。為了防止惡意節(jié)點的攻擊，文獻［12，13］提出信用等級劃分的信用機制，選取高信用節(jié)點成為主節(jié)點，對低信用節(jié)點進行篩除，避免因惡意節(jié)點成為主節(jié)點導致算法的活性與安全性下降。為減少共識通信開銷，Li等人［14］提出一種多層的PBFT共識機制，將單層多節(jié)點的通信劃分為多層，以減少每層的通信開銷。為了避免大量通信并提高網絡擴展性，文獻［15，16］使用散列算法對一致性節(jié)點進行分組，降低了網絡的通信復雜度。為了簡化流程、減少開銷，劉肖飛［17］將PBFT的三階段共識簡化為兩階段共識，從而減少了通信開銷。面對多節(jié)點安全與效率的問題，涂園超等人［18］提出一種基于信譽投票的PBFT改進方案（G-PBFT），在進行動態(tài)信譽篩選的同時將總通信次數減少到m2+2m-1，做到了安全與效率之間的平衡。為了將區(qū)塊鏈應用于物聯(lián)網環(huán)境下，劉煒等人［19］提出一種基于聚類的實用拜占庭容錯算法（C-PBFT），根據物聯(lián)網各節(jié)點的位置特征進行聚類分層，分為底層和上層網絡分別執(zhí)行共識，減少了通信所需的通信次數，提高了共識效率。

但是在區(qū)塊鏈與物聯(lián)網融合的場景下，僅減少通信次數、提高共識效率并不能完全解決實際應用問題。不同物聯(lián)網場景對于設備的需求并不相同，多設備之間也存在性能差異。某些設備性能可能無法滿足特定場景的共識需要，卻仍要承受大量的網絡與物理資源帶來的壓力，從而影響設備本身，導致其無法按時完成共識甚至影響整個物聯(lián)網場景的共識。在傳統(tǒng)物聯(lián)網架構中，中心網絡的節(jié)點設備相較于底層設備必然會消耗更多的資源，單單依靠信譽機制只能夠減少主節(jié)點在中心網絡中作惡的可能性，并不能保證中心節(jié)點擁有足夠的存儲或通信資源。在實際應用場景需要考慮底層網絡中的眾多設備給中心設備所帶來的壓力，同時節(jié)點之間的距離對節(jié)點之間的相互通信造成影響。為了把握節(jié)點資源與距離之間的平衡，同時解決PBFT算法本身通信開銷大和共識時延較長，可能對應用于物聯(lián)網場景的共識造成影響，本文提出一種基于綜合評價的改進實用拜占庭容錯算法（improved practical Byzantine fault to-lerance based on comprehensive evaluation，CE-PBFT）。該算法在共識前對節(jié)點的性能與信譽值進行加權計算得出綜合評價并篩選出合適的節(jié)點，保證了節(jié)點的可靠；同時在面對不同物聯(lián)網場景的不同需求時可通過調節(jié)權重以適應場景變化，提高了場景適應性；之后對節(jié)點進行基于綜合評價的K-means聚類處理，使相關資源更優(yōu)的節(jié)點成為中心節(jié)點，提高了網絡的可靠性；再對共識過程進行分層簡化，將共識過程分為子集群共識與主集群共識，提高容錯性的同時減少了通信開銷與共識時延；最后通過評價節(jié)點的實時性能與共識行為，完成綜合評價的更新。

1 CE-PBFT算法

1.1 物聯(lián)網多場景描述

物聯(lián)網多場景是指物聯(lián)網在現實生活中有著不同領域的應用，如智慧城市領域、工業(yè)領域等。不同的領域中有著不同的應用場景，如智慧城市的智能家居及車聯(lián)網、工業(yè)領域的農產品運輸等。在智慧城市以及工業(yè)領域向數字化轉型升級的過程中，需要針對不同的應用場景進行分析，例如智能家居需要設備有著較高的安全性來保護用戶隱私；車聯(lián)網需要設備能提供實時的通信以收集并共享數據以保證駕駛的安全；農產品運輸需要設備有著較高的存儲性能，以保證產品存證和溯源的完整。在多種應用場景下，應用同樣特性的設備是不合理的，需要根據場景需求來篩選合適的設備且能夠實時地隨著場景需求進行變更，例如在城市交通的早晚高峰，需要保證設備的穩(wěn)定與高效；而在低峰期，則可以讓設備進行額外的存儲與備份。綜上所述，要實現區(qū)塊鏈的物聯(lián)網多場景的應用需求，需要能夠根據多種物聯(lián)網應用場景得出多種設備搭配應用方案以達到區(qū)塊鏈與物聯(lián)網更好融合。

本文針對一個經典物聯(lián)網場景進行分析研究，如圖2所示。大部分物聯(lián)網應用場景基于該場景進行拓展，根據各節(jié)點其相關資源利用率與安全性進行等級劃分，劃分為全節(jié)點、從節(jié)點和邊緣節(jié)點，以體現節(jié)點在當前物聯(lián)網場景中的適用程度。

a）全節(jié)點。在當前物聯(lián)網場景下性能與安全性均較為良好的節(jié)點，能夠承載更多的區(qū)塊信息且網絡較為穩(wěn)定、通信效率較高，能夠參與共識。

b）從節(jié)點。在當前物聯(lián)網場景下性能與安全性較為一般的節(jié)點，能夠滿足基本的共識需求，能夠參與共識。

c）邊緣節(jié)點。在當前物聯(lián)網場景下性能或安全性較低的節(jié)點，無法滿足最低的共識需求，不參與共識。

1.2 算法概述

針對PBFT算法無法根據應用場景變化適應調節(jié)、通信開銷大，共識時延長等問題，本文提出一種基于綜合評價的改進實用拜占庭容錯共識算法。CE-PBFT算法具體流程如圖3所示。

a）物聯(lián)網節(jié)點初始化。完成節(jié)點設置初始信譽值δ、綜合評價ε、分配密鑰等初始化工作，同時獲取節(jié)點的無線網絡坐標。

b）加入綜合評價模型。該模型主要由性能評價與信譽機制兩部分組成。性能評價評估節(jié)點在當前物聯(lián)網場景的存儲及網絡資源利用率；信譽機制評估節(jié)點歷史共識行為得出信譽值。結合各性能評價指標與信譽值在當前物聯(lián)網場景下的權重占比進行加權計算得出各節(jié)點的綜合評價；再根據綜合評價對節(jié)點等級劃分選出全節(jié)點和從節(jié)點，淘汰邊緣節(jié)點。

c）基于綜合評價的聚類階段。對物聯(lián)網場景的全節(jié)點和從節(jié)點進行基于綜合評價的K-means聚類，只有全節(jié)點才有資格通過聚類成為中心節(jié)點，根據節(jié)點綜合評價與具體位置特征劃分為k個子集群和1個主集群。

d）共識階段。共識階段主要分為主集群共識和子集群共識。主集群進行主集群預準備與主集群確認共識，子集群進行三階段的PBFT共識流程。

e）綜合評價更新階段。通過性能評價對節(jié)點參與共識的實時性能進行評價；通過信譽機制，根據節(jié)點在此次共識過程中的共識行為對節(jié)點信譽值進行獎懲；將節(jié)點性能評價與信譽值進行加權計算得出綜合評價，完成綜合評價的更新。

1.3 綜合評價模型

不同的物聯(lián)網場景有著不同的應用需求，不同的節(jié)點設備在不同的應用場景下也可能無法發(fā)揮其全部性能，甚至可能存在惡意節(jié)點進行攻擊而影響整個共識的流程。若不考慮節(jié)點自身性能，例如存儲和網絡性能，低存儲會影響節(jié)點在共識過程乃至共識完成后對于區(qū)塊數據的記錄與備份，造成數據的存儲不完全或失??；而高網絡延遲則會直接造成通信的延遲，無法在規(guī)定時間內完成該階段的共識通信。若只片面地考慮主觀惡意攻擊而忽視了節(jié)點的客觀因素，依然可能會造成整個共識的失敗，導致無法同步區(qū)塊信息。因此，評價物聯(lián)網設備的性能與安全性是否適用于物聯(lián)網場景是實現共識算法物聯(lián)網多場景應用的關鍵。本文提出綜合評價模型對節(jié)點性能與安全性進行綜合考量，以評價節(jié)點在物聯(lián)網場景下的適用程度，保證共識的完成綜合評價模型主要由性能評價與信譽機制兩部分組成。

1.3.1 性能評價

性能評價（performance evaluation，PE）是評價節(jié)點所擁有的性能資源的一種方式。物聯(lián)網設備性能在一定程度上影響著物聯(lián)網與區(qū)塊鏈融合的發(fā)展和應用，大多數的物聯(lián)網設備都是資源受限的，例如手表和紅外傳感器等是電池供電的無線設備，其存儲資源非常有限，無法滿足區(qū)塊鏈存儲需求。部分物聯(lián)網設備雖然存儲資源較為充足，但可能由于網絡的不穩(wěn)定或通信質量差，導致在物聯(lián)網場景下頻繁宕機或通信超時，影響整個場景的共識效率。因此，設定合理的性能評價指標是有效衡量物聯(lián)網設備能否成功完成共識的關鍵，性能評價指標的選擇由實際情況分析確定，不同指標可從不同角度對一個節(jié)點設備進行評價。

針對物聯(lián)網與區(qū)塊鏈融合場景下節(jié)點由于資源受限可能對共識造成影響的實際問題，本文采用以下兩個性能評價指標評價物聯(lián)網節(jié)點的性能，提高可靠性。

a）存儲利用率（storage utilization，SU）［21］。區(qū)塊鏈完成共識后需要在本地產生區(qū)塊用于存儲區(qū)塊數據，這將導致該節(jié)點在下一個共識周期開始之前，歷史數據一直占用著大量的本地存儲空間。設備自身存儲效率較低，在前一輪的區(qū)塊數據沒有存儲完成時就開始進行下一輪的存儲，這會導致設備的高負載，可能會對該設備的共識進度造成影響。另外，在維護區(qū)塊鏈的時候進行區(qū)塊提交等操作會消耗I/O資源，這些操作都需要該節(jié)點有著較高的存儲空間和存儲效率才能保證在規(guī)定時間內反饋消息并成功生成區(qū)塊。因此，提出一個節(jié)點性能評價指標來衡量物聯(lián)網節(jié)點在共識過程中記錄區(qū)塊等行為對存儲資源的使用情況，稱為存儲利用率，取值為［0，1］。在ti到tj的這段時間內，該節(jié)點的存儲利用率SU可由如下公式定義：

SU=size（B，Δt）+size（Ops，Δt）∫tjti（size（t）read+size（t）write）dt（1）

其中：size（B，Δt）表示該節(jié)點在Δt時間內處理的區(qū)塊數據大??；size（Ops，Δt）表示節(jié)點在Δt時間內進行其他共識操作的數據大?。籹ize（t）read表示節(jié)點在t時刻讀取的數據大??；size（t）write表示節(jié)點在t時刻寫入的數據大小。

b）網絡利用率（network utilization，NU）［21］。由于PBFT共識算法是以數據通信的方式將區(qū)塊等相關信息傳輸到網絡中，需要用到通信資源。此外，為了實現去中心化，區(qū)塊鏈采用的是P2P的通信方式，物聯(lián)網大多數節(jié)點都是無線IoT設備，節(jié)點之間的信息交換與數據同步會消耗大量的網絡流量。若某個節(jié)點由于通信質量較差導致消息發(fā)送超時，其消息會失去時效性，從而導致共識失敗。因此，本節(jié)提出一個節(jié)點性能評價指標來衡量物聯(lián)網節(jié)點在共識過程中共識通信等行為所消耗的網絡流量占比，稱為網絡利用率，取值為［0，1］。在ti到tj的這段時間內，該節(jié)點的網絡利用率NU可由如下公式定義：

NU=size（B，Δt）+size（Ops，Δt）∫tjti（net（t）upload+net（t）download）dt（2）

其中：net（t）upload表示節(jié)點在t時刻設備網絡上傳速率；net（t）download表示節(jié)點在t時刻設備網絡下載速率。

對于初始共識節(jié)點，在完成一輪共識后，根據性能評價指標及各指標在當前場景所占權重進行實時的節(jié)點性能評價，性能評價PE的取值為［0，1］，具體公式如下：

PE=ω1SU+ω2NU（3）

其中：ω1，ω2∈［0，1］且0≤ω1+ω2≤1，ω1、ω2分別代表存儲利用率SU與網絡利用率NU在當前場景下的權重占比。性能評價PE越高，說明節(jié)點擁有的相關資源越多，性能越好。

1.3.2 信譽機制

由于PBFT采用隨機選取主節(jié)點的方式，這將會導致共識過程中拜占庭節(jié)點與普通節(jié)點有著相同的概率成為主節(jié)點而無須付出任何代價，顯然這會導致安全問題。因此，根據節(jié)點歷史共識行為對其進行必要的獎懲，是提升節(jié)點共識積極性與維護共識安全的必要手段。

在CE-PBFT中，信譽機制主要分為信譽獎懲與信譽恢復兩部分。對于初始未參與共識的節(jié)點，信譽值統(tǒng)一默認為δ，信譽值及其相關計算參數在開始共識之前由客戶端進行初始化并存儲在本地。為了便于之后各節(jié)點能夠通過信譽值及其權重占比參與綜合評價，信譽值R的取值為［0，1］。

信譽獎懲是指當節(jié)點參與共識時，根據其在共識過程中的行為作出信譽評估。設節(jié)點i在第t輪共識的信譽值為Rti，則節(jié)點在t+1輪共識的信譽值Rt+1i的計算公式如下：

Rt+1i=Rti+α（1-Rti）節(jié)點行為正常

βs+1Rti節(jié)點行為異常（4）

若節(jié)點參與并完成了第t輪共識且反饋了正確的信息，則該節(jié)點下一輪的信譽值更新為Rt+1i=Rti+α（1-Rti）。α∈（0，1）為獎勵系數，用于控制信譽值的增長速度。當α固定不變時，Rti越大，Rt+1i的增長速度越慢，無限趨近于1，如此能夠提高各個節(jié)點出塊的積極性的同時，還能夠防止某一節(jié)點由于信譽值過高而造成對新加入節(jié)點的不公平。若節(jié)點在第t輪共識存在未響應或返回錯誤消息等異常行為，則該節(jié)點下一輪的信譽值更新為Rt+1i=βs+1Rti。β∈（0，1）為懲罰系數，s為該節(jié)點歷史異常行為次數，兩者均用于控制信譽值下降的速度。當β固定不變時，s越大，Rt+1i的下降速度越快，無限趨近于0，如此能夠加重對頻繁影響共識節(jié)點的信譽值懲罰，提高作惡代價。

信譽恢復是指當節(jié)點被劃分為邊緣節(jié)點時，經過n輪無法參與共識之后恢復其部分信譽值p，使其有機會重新參與共識。邊緣節(jié)點在n輪不參與共識后，進行信譽恢復的計算公式如下：

Rt+ni=Rti+p（5）

若一個節(jié)點信譽值過低，則有可能會導致其綜合評價無法滿足共識要求而被多次劃分為邊緣節(jié)點，使其連續(xù)多個n輪無法參與共識，這能有效預防惡意節(jié)點頻繁影響共識流程，同時也能使得邊緣節(jié)點有機會成為從節(jié)點或全節(jié)點。加入信譽機制，可以實現對于全網共識的安全保障。N個節(jié)點在完成第t輪共識后的信譽值更新算法如算法1所示。

算法1 信譽值更新算法

輸入：Rti，Nti，α，β。

輸出：Rt+1i。

for t，i∈N

if complete consensus && feedback correct information

Rt+1i←Rti+α（1-Rti）；

else if Nti.status←fringe node

Rt+ni←Rti+p；

else Rt+1i←βs+1Rti；

return Rt+1i；

end for

1.3.3 綜合評價

利用性能評價PE中的性能評價指標SU、NU以及信譽機制中的信譽值R與當前場景下的各自權重占比進行加權計算，得出該節(jié)點的綜合評價（comprehensive evaluation，CE）。綜合評價CE的取值為［0，1］，具體定義如下：

CE=ω1SU+ω2NU+ω3R（6）

其中：ω1，ω2，ω3∈［0，1］且ω1+ω2+ω3=1，ω1、ω2、ω3分別代表存儲利用率SU、網絡利用率NU和信譽值R在當前物聯(lián)網場景下的權重占比。

面對物聯(lián)網多場景時，可通過調節(jié)權重以適應不同應用場景的需求。對存儲空間需求較大的物聯(lián)網場景，如智慧存儲等，需要占用大量的存儲空間來存儲交易或賬本數據，則通過提升ω1來提高場景對節(jié)點存儲利用率的要求；對網絡通信要求較為嚴格的物聯(lián)網場景，如車聯(lián)網、智慧醫(yī)療等，需要較好的網絡質量與及時的通信來保證共識穩(wěn)定運行，則通過提升ω2來提高場景對節(jié)點網絡利用率的要求；對設備安全性有著高要求的物聯(lián)網場景，如智能安防等，需要保證終端節(jié)點的安全，則通過提升ω3來提高場景節(jié)點對信譽值的要求。

通過調節(jié)各評價指標的權重以適應多場景應用的需求，再根據綜合評價對節(jié)點進行等級劃分以篩選出適合當前場景的節(jié)點。對于初始未參與共識的節(jié)點，綜合評價統(tǒng)一默認為ε。全網節(jié)點綜合評價主要分為三類，如表2所示。全網節(jié)點綜合評價準則基于節(jié)點在性能評價與信譽機制中的表現，只有當節(jié)點綜合評價達到ε時節(jié)點才有資格參與本輪共識，當節(jié)點綜合評價低于ε時，將由于綜合評價不達標，無法滿足最低的共識資源要求，成為邊緣節(jié)點而禁止參與本輪共識。若節(jié)點綜合評價滿足ε且不大于ζ，則成為從節(jié)點；若節(jié)點綜合評價大于ζ，則說明節(jié)點綜合評價較高，其性能與安全性在全網節(jié)點中較為優(yōu)秀，成為全節(jié)點。

假設某個物聯(lián)網場景中共有N個節(jié)點，各節(jié)點的綜合評價為CEi，其中i=1，2，…，N，該場景需求M個合適的節(jié)點參與共識。先對各節(jié)點的綜合評價CEi進行降序排列，之后根據當前場景的共識需求將排名第M的節(jié)點的綜合評價CEM設定為從節(jié)點閾值ε。

由于傳統(tǒng)PBFT共識算法需要保證至少有4個節(jié)點才能進行共識，其中1個主節(jié)點和3個從節(jié)點，即在分簇的PBFT共識過程中，只要保證當前場景中參與共識的主從節(jié)點個數比為1：3就能保證每個簇內均可開始共識，不會發(fā)生某個簇內無法共識的情況。綜上，假設滿足從節(jié)點閾值ε的節(jié)點個數為M，各節(jié)點的綜合評價為CEh，其中h=1，2，…，M。先對各節(jié)點的綜合評價CEh進行降序排列，選取排名第「M/4個節(jié)點的綜合評價CE「M/4設定為全節(jié)點閾值ζ，這樣既可以保證在分簇過多的情況下每個簇內均可滿足開始共識的基本條件，同時當分簇數小于「M/4時剩余的全節(jié)點可作為替補節(jié)點，提高可靠性。

圖4是在不同節(jié)點個數的情況下，隨機存儲利用率SU、網絡利用率NU和信譽值R的物聯(lián)網節(jié)點分別進行權重占比（ω1，ω2，ω3）=（0.8，0.1，0.1）所代表的高存儲利用率要求的物聯(lián)網場景，（ω1，ω2，ω3）=（0.1，0.8，0.1）所代表的高網絡利用率要求的物聯(lián)網場景以及（ω1，ω2，ω3）=（0.1，0.1，0.8）所代表的高信譽值要求的物聯(lián)網場景，在以上3種不同應用場景下生成對應的綜合評價，固定篩選出25個適合當前物聯(lián)網場景的節(jié)點（全節(jié)點+從節(jié)點）時，從節(jié)點閾值ε和全節(jié)點閾值ζ的變化情況。

從圖4可知，隨著物聯(lián)網節(jié)點數量的增加，從節(jié)點閾值ε和全節(jié)點閾值ζ也在逐漸上升，上升速度逐漸減緩最后趨于平穩(wěn)。這是由于在節(jié)點數量越多的場景中篩選出固定數量的全節(jié)點，篩選條件會逐漸苛刻，而全節(jié)點的數量并不一定會隨著物聯(lián)網節(jié)點數量的增加而增加，所以上升幅度會逐漸放緩而趨于平穩(wěn)。

綜合評價模型綜合考量了每個節(jié)點在物聯(lián)網場景中可能影響共識的客觀和人為因素，較單一的信譽值等級劃分顯得更加全面，同時還能夠通過調節(jié)各評價指標的權重以適應應用場景的變化，實現不同物聯(lián)網場景下對節(jié)點的不同要求，提高了場景適應性。N個節(jié)點在進行第t+1輪共識時的綜合評價模型算法如算法2所示。

算法2 綜合評價模型

輸入：SUti，NUti，Rti，ω1，ω2，ω3。

輸出：CEt+1i，Nt+1i。

for t，i∈N

CEt+1i=ω1SUti+ω2NUti+ω3Rti；

if CEt+1i≥ε

if CEt+1i>ζ

Nt+1i.status←full node；

else Nt+1i.status←follower；

else Nt+1i.status←fringe node；

return CEt+1i，Nt+1i；

end for

1.4 基于綜合評價的聚類階段

在物聯(lián)網中，可利用無線網絡定位技術來實現將各節(jié)點以橫縱坐標的形式展現在二維空間，從而獲取節(jié)點的無線網絡坐標。在眾多聚類算法中，K-means聚類算法憑借其距離最優(yōu)原則選擇中心節(jié)點的機制而適用于實際物聯(lián)網場景。考慮到實際在進行分簇共識時，各簇內的中心節(jié)點由于需要額外參與簇間的共識導致通信次數較其他節(jié)點有著明顯增多，同時承載的區(qū)塊信息也會更大，需要用到更多的資源，所以本文將物聯(lián)網節(jié)點綜合評價與K-means根據距離分簇的思想相結合，提出基于綜合評價的K-means聚類算法。將節(jié)點是否為全節(jié)點作為選拔中心節(jié)點的條件，同時該節(jié)點必須較簇內其他全節(jié)點到其他節(jié)點距離之和最小，從而選出兼具性能與安全性且簇內距離最優(yōu)的中心節(jié)點。由于PBFT算法的通信復雜度為O（N2），為防止部分節(jié)點簇內因節(jié)點數顯著多于其他簇而增大了整個場景的通信開銷，要將每個簇內節(jié)點數平均化，最多為「N/k個，且要滿足N/k≥4防止部分節(jié)點簇內由于節(jié)點個數不足無法滿足共識條件。但原K-means聚類算法并不能對中心節(jié)點選取條件和簇內節(jié)點數量進行控制，因此本節(jié)對聚類流程進行了改進以適用于實際物聯(lián)網場景。基于綜合評價的K-means聚類流程如下：

a）根據節(jié)點的綜合評價篩選出全節(jié)點和從節(jié)點。只有全節(jié)點才有成為中心節(jié)點的資格，從節(jié)點可以通過聚類加入簇內。

b）若將N個節(jié)點劃分為k個簇，則從全節(jié)點中隨機選擇k個節(jié)點作為初始中心節(jié)點。

c）利用二維歐氏距離計算公式分別得出節(jié)點Ni到k個初始中心節(jié)點的距離大小。

d）節(jié)點Ni加入距其最近的中心節(jié)點所在簇，在加入之前需判斷該簇內節(jié)點數量是否超過閾值「N/k，若是則加入距離次之的簇，重復這一操作，直到加入某一簇內。

e）重新計算每個簇的中心點，將本簇內到其他節(jié)點距離之和最小的全節(jié)點作為新的中心節(jié)點，該節(jié)點稱為該簇的中心全節(jié)點。重復執(zhí)行步驟d）e），直到中心全節(jié)點不再變化，基于綜合評價的K-means聚類完成。

對節(jié)點進行聚類后形成的k個節(jié)點簇稱為子集群。各節(jié)點簇的中心節(jié)點由于其綜合評價優(yōu)秀且其在簇內距離最優(yōu)，稱為中心全節(jié)點，由各中心全節(jié)點組成的節(jié)點簇稱為主集群。由主集群構成中心網絡，子集群則構成底層網絡，由此構成了一個雙層網絡架構。

圖5是生成40個隨機存儲利用率SU、網絡利用率NU和信譽值R的物聯(lián)網節(jié)點分別在權重占比為（ω1，ω2，ω3）=（0.8，0.1，0.1）的高存儲利用率要求的物聯(lián)網場景，（ω1，ω2，ω3）=（0.1，0.8，0.1）的高網絡利用率要求的物聯(lián)網場景以及（ω1，ω2，ω3）=（0.1，0.1，0.8）的高信譽要求的物聯(lián)網場景下，固定篩選出25個適合當前物聯(lián)網場景的節(jié)點（全節(jié)點+從節(jié)點），并執(zhí)行基于綜合評價的K-means聚類算法求得5個中心全節(jié)點的網絡節(jié)點坐標圖。

從圖5可知，隨著場景需求的變化，即權重ω1、ω2、ω3的改變，節(jié)點角色的劃分并不統(tǒng)一，說明基于綜合評價的聚類起到了根據場景需求劃分節(jié)點的作用，具有場景適應性。此外，通過改進后的聚類算法將節(jié)點等分到各子集群中，解決了由于各集群內部節(jié)點數量不均，導致通信開銷過大的問題。網絡拓撲如圖6所示。

1.5 共識階段

基于綜合評價的K-means聚類算法將適合當前物聯(lián)網場景的節(jié)點分為了k個子集群，之后通過將傳統(tǒng)PBFT算法共識劃分為子集群共識和主集群共識兩個階段以降低原來平方級的通信復雜度，減少通信次數，緩解通信壓力。圖7展示了整個CE-PBFT的通信過程。

a）主集群預準備。客戶端通過基于綜合評價的聚類完成了共識階段的分簇，將分簇結果作為集群信息G，封裝到消息格式為［M-PRE-PREPARE，b，v，t，c，G］的主集群預準備消息中，并將消息發(fā)送至主集群的中心全節(jié)點，其中b為區(qū)塊，v為視圖編號，t為時間戳，c為客戶端標志。

b）子集群共識。中心全節(jié)點接收到請求預準備消息后，根據集群信息G得知自身所在子集群，然后發(fā)起子集群共識，共識過程分為pre-prepare、prepare、commit三步。

（a）本地子集群中的中心全節(jié)點向子集群中的其他節(jié)點廣播消息格式為〈〈PRE-PREPARE，v，n，G，D（b）〉σi，b〉的子集群預準備消息，進入pre-prepare階段，其中n為給區(qū)塊b分配的序號隨機數，D（b）為區(qū)塊b的摘要，σi為節(jié)點的簽名。（b）當節(jié)點接收到子集群預準備消息后，需要對該消息內容進行驗證，除傳統(tǒng)PBFT的驗證內容外，節(jié)點還需根據集群信息G驗證其是否為自身所在子集群中心全節(jié)點發(fā)來的消息。若驗證通過，則根據集群信息G向自身所在子集群的其他節(jié)點廣播消息格式為〈PREPARE，v，n，D（b），i〉的準備消息，進入prepare階段，若接收并驗證通過2fs個本地子集群節(jié)點發(fā)送的準備消息，則進入子集群commit階段，其中i為此節(jié)點的簽名，fs為本地子集群的拜占庭節(jié)點個數。（c）節(jié)點向其他節(jié)點廣播發(fā)送消息格式為〈COMMIT，v，n，D（b），i〉的確認消息，若接受并驗證通過2fs+1個本地子集群節(jié)點發(fā)送的確認消息，則子集群共識完成。

c）主集群確認。各中心全節(jié)點完成子集群共識后，代表本地子集群進行主集群共識，各中心全節(jié)點向其他中心全節(jié)點廣播消息格式為［M-COMMIT，v，n，D（b），i］的主集群確認消息，進入主集群確認階段。若中心全節(jié)點接收并驗證通過2fm+1個主集群確認信息，則主集群共識完成，將區(qū)塊寫入本地，全局共識完成，其中fm為主集群的拜占庭節(jié)點個數。

全局共識完成后，客戶端根據該輪共識節(jié)點的實時性能和共識行為進行綜合評價的更新。

2 實驗結果及分析

本文研究了共識算法應用于實際物聯(lián)網場景時存在的多場景應用問題，考慮了節(jié)點客觀性能的局限，對共識造成影響的可能性，提高了共識效率。本文基于Go語言對PBFT［8］、G-PBFT［18］、C-PBFT［19］、SBFT［20］與CE-PBFT進行了仿真對比實驗，通過容錯性、共識成功率、通信開銷和共識時延四個方面來驗證其性能，假設網絡中所有節(jié)點均具有連通性且都滿足共識條件。具體實驗環(huán)境為Intel CoreTM i9-12900H 2.50 GHz CPU，內存8.0 GB，操作系統(tǒng)Linux Ubuntu 20.04，Go語言版本1.17.6。

2.1 容錯性分析

容錯性是指在共識過程中，共識所能夠承受的最大拜占庭節(jié)點數量占總共識節(jié)點數的比重。傳統(tǒng)PBFT共識算法最高支持1/3的容錯，但CE-PBFT共識算法采用的是基于綜合評價模型與聚類分簇，以中心全節(jié)點代表本地子集群進行的全局共識。假設在某個子集群內節(jié)點均為拜占庭節(jié)點的極端情況下，在主集群共識時只會記為1個拜占庭中心全節(jié)點，將會造成本地子集群共識的失敗，但并不會直接導致全局共識的失敗，這使得該算法可以容忍更多的拜占庭節(jié)點。

圖8是PBFT與CE-PBFT在不同節(jié)點數量下最大可容忍拜占庭節(jié)點數目的變化情況。從圖中可以看出，隨著節(jié)點數量的增加，CE-PBFT較PBFT算法可以容忍更多的拜占庭節(jié)點，且隨著子集群個數k的增加，可容忍的拜占庭節(jié)點個數有所增加。綜上，CE-PBFT共識算法有較高的容錯性。

2.2 共識成功率分析

由于設備性能的缺陷等原因導致自身無法按照要求進行共識，導致共識失敗，則共識成功率是指共識成功次數占共識總次數的比值。

圖9是當節(jié)點數量分別為40、50、60、70、80、90、100時，在ω1=1的高存儲利用率場景和ω2=1的高網絡利用率場景下，進行100次CE-PBFT（k=10）、PBFT共識且每次共識結束隨機刷新存儲利用率SU與網絡利用率NU所得出的共識成功率。假設當某節(jié)點的存儲利用率或網絡利用率小于0.3時，該節(jié)點此次共識將無法正常進行。為了減小誤差，每個實驗重復10次，取平均值作為最終結果。

從圖9可以看出，在不同場景下，CE-PBFT共識算法的共識成功率均大于PBFT共識算法的共識成功率。這主要是由于CE-PBFT算法根據權重與性能指標對節(jié)點篩選，有效地避免了原PBFT算法由于隨機選取主節(jié)點導致無法正常進行共識的節(jié)點被選舉成為主節(jié)點的情況發(fā)生。

2.3 通信開銷分析

通信開銷是指共識節(jié)點在共識過程中相互通信所產生的信息量。假設參與共識的節(jié)點數目為N，N個節(jié)點被分為k個子集群。在CE-PBFT中，首先客戶端將主集群預準備消息發(fā)送給主集群的中心全節(jié)點，通信次數為k；各中心全節(jié)點接收到消息后驗證并發(fā)起子集群共識，子集群預準備階段的通信次數為N-k，準備階段的通信次數為k（N/k-1）2，確認階段的通信次數為N（N/k-1）。子集群共識的總通信次數T1為

T1=N-k+k（Nk-1）2+N（Nk-1）=2N2k-2N（7）

子集群共識完成后，主集群確認階段的通信次數T2為

T2=k（k-1）（8）

綜上，CE-PBFT的總通信次數T3為

T3=k+T1+T2=2N（Nk-1）+k2（9）

為驗證本算法在共識開銷方面的優(yōu)越性，表3對比了PBFT［8］、G-PBFT［18］、C-PBFT［19］、SBFT［20］、CE-PBFT五種算法完成一次共識所消耗的總通信次數。

令PBFT與CE-PBFT的通信次數比為Z，則有

Z=2N（N-1）2N（N/k-1）+k2（10）

由圖10可知，隨著k值的增加，即子集群數量的增加，比值逐漸增大，這是由于節(jié)點被平均分成k個子集群，使得CE-PBFT在子集群共識階段進行的是k次少量節(jié)點的平方級共識通信，有效地減少了共識通信次數。但并不能一味地增加k值，當k增大至某一值時，Z達到最大值隨后下降。這是由于k值并不只代表子集群的數量，它還決定了主集群中心全節(jié)點的個數，主集群的中心全節(jié)點個數過多，在主集群共識階段所需的通信次數為k（k-1），通信復雜度O（k2）為平方級，導致通信次數再次增多。當節(jié)點個數N為100，子集群個數k為20時，PBFT的總通信次數為19 800，CE-PBFT的總通信次數為1 200，可得CE-PBFT較PBFT在通信開銷方面優(yōu)化了93.9%。

2.4 時延分析

共識時延是指從發(fā)起區(qū)塊共識到完成所消耗的時間，是衡量共識效率的重要指標。本文將PBFT的共識時延與不同子集群個數k的CE-PBFT的共識時延進行對比。為減小誤差，每個實驗重復10次，取平均值作為最終結果。如圖11所示，當節(jié)點個數固定時，在一定閾值內增加子集群數k能有效地降低共識時延，提升共識效率，且隨著節(jié)點數的增加，在一定閾值內子集群數越多，時延差距越大，提升的效果越明顯。

此外，圖12還對比了不同算法完成一次共識所需的時長，其中固定N/k=5，即每個子集群內固定有5個節(jié)點。從圖中可以看出，隨著共識節(jié)點數的增加，本文提出的 CE-PBFT算法完成共識的時延最短，且隨著節(jié)點數目的增加與PBFT、G-PBFT、C-PBFT、SBFT算法之間的差距逐漸增大。當節(jié)點個數N為100，子集群個數k=20時，PBFT共識時延為1 035 ms，CE-PBFT的共識時延為126 ms，可知CE-PBFT較PBFT在共識時延方面優(yōu)化了87.8%。

3 結束語

本文提出一種基于綜合評價的改進實用拜占庭容錯算法CE-PBFT，解決了物聯(lián)網多場景中應用PBFT算法時無法隨著應用場景變化進行節(jié)點篩選條件的動態(tài)調節(jié)選出適合當前場景節(jié)點，同時算法本身通信開銷較高，共識時延較長等問題。實驗結果表明，CE-PBFT具有較高容錯性的同時，在通信開銷和共識時延方面較PBFT、G-PBFT、C-PBFT、SBFT這四種BFT類共識算法更加優(yōu)越。

然而，CE-PBFT算法在共識階段需要客戶端將集群信息發(fā)送給中心全節(jié)點，而物聯(lián)網中的節(jié)點數目是眾多的，這可能導致在發(fā)布出塊請求時集群消息條目過大，增加了網絡負載。下一步將對降低拜占庭節(jié)點的出現在共識的概率、提高共識的安全性方面繼續(xù)研究。

參考文獻：

［1］Nordrum A.The Internet of fewer Things［News］［J］.IEEE Spectrum，2016，53（10）：12-13.

［2］Ogawa K，Kanai K，Nakamura K，et al.IoT device virtualization for efficient resource utilization in smart city IoT platform［C］//Proc of IEEE International Conference on Pervasive Computing and Communications.Piscataway，NJ：IEEE Press，2019：419-422.

［3］Xie Junfeng，Tang Helen，Huang Tao，et al.A survey of blockchain technology applied to smart cities：research issues and challenges［J］.IEEE Communications Surveys & Tutorials，2019，21（3）：2794-2830.

［4］Ammi M，Alarabi S，Benkhelifa E.Customized blockchain-based architecture for secure smart home for lightweight IoT［J］.Information Processing & Management，2021，58（3）：102482.

［5］Nakamoto S.Bitcoin：a peer-to-peer electronic cash system［EB/OL］.［2023-08-10］.https：//bitcoin.org/bitcoin.pdf.

［6］Saleh F.Blockchain without waste：proof-of-stake［J］.The Review of Financial Studies，2021，34（3）：1156-1190.

［7］Larimer D.DPOS consensus algorithm：the missing white paper［EB/OL］.（2017-05-28）.https：//moreequalanimals.com/posts/dpos-consensus-algorithm-whitepaper.

［8］Castro M，Liskov B.Practical Byzantine fault tolerance［C］//Proc of the 3rd Symposium on Operating Systems Design and Implementation.Berkeley，CA：USENIX Association，1999：173-186.

［9］蔡曉晴，鄧堯，張亮，等.區(qū)塊鏈原理及其核心技術［J］.計算機學報，2021，44（1）：84-131.（Cai Xiaoqing，Deng Yao，Zhang Liang，et al.The principle and core technology of blockchain［J］.Chinese Journal of Computers，2021，44（1）：84-131.）

［10］田志宏，趙金東.面向物聯(lián)網的區(qū)塊鏈共識機制綜述［J］.計算機應用，2021，41（4）：917-929.（Tian Zhihong，Zhao Jindong.Overview of blockchain consensus mechanism for Internet of Things［J］.Journal of Computer Applications，2021，41（4）：917-929.）

［11］Salimitari M，Chatterjee M，Fallah Y.A survey on consensus methods in blockchain for resource-constrained IoT networks［J］.Internet of Things，2020，11（5）：100212.

［12］丁庭琛，陳世平.基于信用分級的PBFT共識算法改進方案［J］.計算機系統(tǒng)應用，2020，29（9）：255-259.（Ding Tingchen，Chen Shiping.Improved PBFT consensus mechanism based on credit-layered mechanism［J］.Computer Systems & Applications，2020，29（9）：255-259.）

［13］周健，張杰，閆石，等.基于動態(tài)信任的區(qū)塊鏈激勵共識機制研究［J］.計算機應用研究，2021，38（11）：3231-3235，3248.（Zhou Jian，Zhang Jie，Yan Shi，et al.Study on consensus mechanism of blockchain motivation based on dynamic trust［J］.Application Research of Computers，2021，38（11）：3231-3235，3248.）

［14］Li Wenyu，Feng Chenglin，Zhang Lei，et al.A scalable multi-layer PBFT consensus for blockchain［J］.IEEE Trans on Parallel and Distributed Systems，2020，32（5）：1146-1160.

［15］Yang Jian，Jia Zhenhong，Su Ruiguo，et al.Improved fault-tolerant consensus based on the PBFT algorithm［J］.IEEE Access，2022，10：30274-30283.

［16］Chen Runyu，Wang Lunwen，Zhu Rangang，et al.An improved practical Byzantine fault tolerance algorithm based on vague sets and random numbers［C］//Proc of the 7th International Conference on Intelligent Computing and Signal Processing.Piscataway，NJ：IEEE Press，2022：151-155.

［17］劉肖飛.基于動態(tài)授權的拜占庭容錯共識算法的區(qū)塊鏈性能改進研究［D］.杭州：浙江大學，2017.（Liu Xiaofei.Research on performance improvement of blockchain based on dynamic authorization of Byzantine fault tolerance consensus algorithm［D］.Hangzhou：Zhejiang University，2017.）

［18］涂園超，陳玉玲，李濤，等.基于信譽投票的PBFT改進方案［J］.應用科學學報，2021，39（1）：79-89.（Tu Yuanchao，Chen Yuling，Li Tao，et al.Improved PBFT scheme based on reputation voting［J］.Journal of Applied Sciences，2021，39（1）：79-89.）

［19］劉煒，阮敏捷，佘維，等.面向物聯(lián)網的PBFT優(yōu)化共識算法［J］.計算機科學，2021，48（11）：151-158.（Liu Wei，Wan Minjie，She Wei，et al.PBFT optimized consensus algorithm for Internet of Things［J］.Computer Science，2021，48（11）：151-158.）

［20］黃保華，彭麗，趙偉宏，等.基于可驗證隨機函數的實用拜占庭共識算法［J］.計算機科學，2023，50（S1）：737-742.（Huang Baohua，Peng Li，Zhao Weihong，et al.Practical Byzantine consensus algorithm based on verifiable random functions［J］.Computer Science，2023，50（S1）：737-742.）

［21］韓亞敏.面向物聯(lián)網的區(qū)塊鏈系統(tǒng)性能分析與優(yōu)化［D］.南京：南京郵電大學，2022.（Han Yamin.Performance analysis and optimization of blockchain system for the Internet of Things［D］.Nanjing：Nanjing University of Posts & Telecommunications，2022.）