面向物联网多场景的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阶段既保证了最终不会提交和已经提交的消息冲突的消息，同时在恶意主节点存在的情况下还能保证算法的安全性。可是PBFT算法本身随机选取主节点的方式并未将节点自身条件是否满足当前场景需要考虑进去，这会导致主节点没有能力进行共识的情况发生。另外，其通信复杂度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时间内处理的区块数据大小；size（Ops，Δt）表示节点在Δt时间内进行其他共识操作的数据大小；size（t）read表示节点在t时刻读取的数据大小；size（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.）