面向物聯網多場景的PBFT共識算法改進方案

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

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

關鍵詞：物聯網；區塊鏈；實用拜占庭容錯；多場景；綜合評價

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

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

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

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

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

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

1 CE-PBFT算法

1.1 物聯網多場景描述

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

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

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

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

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

1.2 算法概述

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

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

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

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

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

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

1.3 綜合評價模型

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

1.3.1 性能評價

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

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

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

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

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

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

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

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

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

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

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

1.3.2 信譽機制

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

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

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

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

βs+1Rti節點行為異常（4）

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

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

Rt+ni=Rti+p（5）

若一個節點信譽值過低，則有可能會導致其綜合評價無法滿足共識要求而被多次劃分為邊緣節點，使其連續多個n輪無法參與共識，這能有效預防惡意節點頻繁影響共識流程，同時也能使得邊緣節點有機會成為從節點或全節點。加入信譽機制，可以實現對于全網共識的安全保障。N個節點在完成第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與當前場景下的各自權重占比進行加權計算，得出該節點的綜合評價（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在當前物聯網場景下的權重占比。

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

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

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

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

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

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

綜合評價模型綜合考量了每個節點在物聯網場景中可能影響共識的客觀和人為因素，較單一的信譽值等級劃分顯得更加全面，同時還能夠通過調節各評價指標的權重以適應應用場景的變化，實現不同物聯網場景下對節點的不同要求，提高了場景適應性。N個節點在進行第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 基于綜合評價的聚類階段

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

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

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

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

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

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

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

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

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

1.5 共識階段

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

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

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

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

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

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

2 實驗結果及分析

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

2.1 容錯性分析

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

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

2.2 共識成功率分析

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

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

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

2.3 通信開銷分析

通信開銷是指共識節點在共識過程中相互通信所產生的信息量。假設參與共識的節點數目為N，N個節點被分為k個子集群。在CE-PBFT中，首先客戶端將主集群預準備消息發送給主集群的中心全節點，通信次數為k；各中心全節點接收到消息后驗證并發起子集群共識，子集群預準備階段的通信次數為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）

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

2.4 時延分析

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

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

3 結束語

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

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

參考文獻：

［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］蔡曉晴，鄧堯，張亮，等.區塊鏈原理及其核心技術［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］田志宏，趙金東.面向物聯網的區塊鏈共識機制綜述［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］.計算機系統應用，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］周健，張杰，閆石，等.基于動態信任的區塊鏈激勵共識機制研究［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］劉肖飛.基于動態授權的拜占庭容錯共識算法的區塊鏈性能改進研究［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］劉煒，阮敏捷，佘維，等.面向物聯網的PBFT優化共識算法［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］韓亞敏.面向物聯網的區塊鏈系統性能分析與優化［D］.南京：南京郵電大學，2022.（Han Yamin.Performance analysis and optimization of blockchain system for the Internet of Things［D］.Nanjing：Nanjing University of Posts & Telecommunications，2022.）