-
摘要:
线性赌博机模型是在线学习的基本模型之一，其每个摇臂的平均奖赏可以由线性函数进行参数化. 该模型具有坚实的理论保证和良好的实际建模能力，被广泛应用于各个场景. 然而在一些现实场景中，数据通常是从开放动态环境中收集得到，因而会存在数据不规范的问题，已有算法缺乏对此的稳健性. 特别关注2类数据的不规范性：奖励函数的回归参数可能随时间变化，环境噪声可能无界，甚至不服从亚高斯分布. 这2类问题分别被称为分布变化和重尾噪声. 为了应对这2类不利因素， 提出一种基于置信上界的在线算法， 该算法使用均值中位数估计器以处理潜在的重尾噪声，同时采用重启机制来解决分布变化问题. 在理论上，首先建立了问题的遗憾理论下界， 进一步给出了算法的理论保障， 所取得的结果可以回退到已有研究中没有分布变化或没有重尾噪声场景线性赌博机的理论结果. 此外，针对未知环境设计了实用的在线集成适应技术，并在合成和真实世界的数据集上进行了广泛的实验来验证其有效性.
-
关键词:
- 机器学习 /
- 开放环境学习 /
- 线性赌博机或没有重尾 /
- 分布变化 /
- 重尾噪声
Abstract:The linear bandits model is one of the most foundational online learning models, where a linear function parametrizes the mean payoff of each arm. The linear bandits model encompasses various applications with strong theoretical guarantees and practical modeling ability. However, existing algorithms suffer from the data irregularity that frequently emerges in real-world applications, as the data are usually collected from open and dynamic environments. In this paper, we are particularly concerned with two kinds of data irregularities: the underlying regression parameter could be changed with time, and the noise might not be bounded or even not sub-Gaussian, which are referred to as model drift and heavy-tailed noise, respectively. To deal with the two hostile factors, we propose a novel algorithm based on upper confidence bound. The median-of-means estimator is used to handle the potential heavy-tailed noise, and the restarting mechanism is employed to tackle the model drift. Theoretically, we establish the minimax lower bound to characterize the difficulty and prove that our algorithm enjoys a no-regret upper bound. The attained results subsume previous analysis for scenarios without either model drift or heavy-tailed noise. Empirically, we additionally design several online ensemble techniques to make our algorithm more adaptive to the environments. Extensive experiments are conducted on synthetic and real-world datasets to validate the effectiveness.
-
随着车联网中车辆数量的不断增加，车辆之间数据共享交换的速度和频率越来越高，安全高效的智能车联网数据共享方案已成为研究热点. 其中，基于区块链的方案持续涌现，成为车联网数据共享的重要途径. 目前，基于区块链的车联网数据共享方案主要有：基于区块链的联邦学习数据共享方案[1-2]，使用区块链代替联邦学习中的中心化服务器，提出了面向分布式终端的去中心化数据共享架构与系统； 基于新型共识协议的数据共享方案[3-4]，针对不断变化的车联网环境，提出适用于不同场景的共识机制；基于区块链访问控制的数据共享方案[5-6]，提出新的加密方式实现对区块的细粒度访问控制. 以上方法所使用的区块链系统吞吐量较为有限，难以应对未来智能车联网中海量数据共享需求.
区块链分片技术[7]旨在提高吞吐量以实现区块链系统的可扩展性. 该技术将区块链网络节点分成多个分片（shard），每个分片只需要处理一部分交易数据，多个分片并行执行. 主要的分片区块链技术，如Elastico[8]，RapidChain[9]，OmniLedger[10]，ChainSpace[11]，MVCom[12]，在提升系统吞吐量的同时，为了保证分片的安全性，采用了多种密码技术将区块链节点随机分配到各个分片中，以抵御敌手对片内节点的贿赂，防止片内恶意节点数量超过单个分片安全阈值.
将区块链验证节点随机地分配到不同分片，在理论上能最大程度地保证分片区块链的安全性，然而难以适配实际的车联网应用环境，原因在于：1）地理位置上接近的车联网区块链节点可能被分配到不同的分片当中，使得车辆之间的数据共享协同效率降低；2）随机分片的方案对车联网区块链分片的负载问题考虑较少，可能导致不同分片之间的负载存在较大差异，造成车联网基础设施资源（带宽、算力等）分配不均匀和利用不充分. 因此，亟需适用于实际车联网应用的区块链分片方案，该方案面临3个挑战：
1）现有的分片算法缺乏实现片内节点距离相近与片间负载均衡的能力，仅能够取得这2个要素中单一目标的较优解，无法同时优化2个要素；
2）各个分片内恶意路侧单元的数量未知，当分片内的恶意路侧单元（road side unit，RSU）数量过多时，由恶意RSU主导的共识产生区块上链；
3）为保证分片系统的安全性，现有方案需要定期对各个分片实行轮换和置乱等节点重新配置，带来了节点额外数据下载开销，且需要维持较大的单个片内节点数量，降低了片内共识过程效率.
针对上述3个挑战，本文设计了一种基于分片区块链的车联网数据共享方案. 主要贡献包括3个方面：
1）提出了一种基于机器学习的分片算法，该算法基于聚类实现片内节点在地理位置上的紧凑分布，借助平衡损失实现分片间在负载上的均匀分布，实现高吞吐量的车联网区块链架构；
2）提出了基于声誉的片内共识协议，通过片内各个RSU参与共识的行为评估其声誉，高于设定的声誉阈值的RSU可参与片内共识，确保高声誉节点主导片内共识，抵御片内恶意RSU数量过多导致的安全问题；
3）提出了监督人机制，选取声誉度较高的节点作为监督人，可以随机、定期验证不同分片节点交易验证的合法性，降低了对片内节点数量较大的要求，对提升分片系统的安全和效率都有重要作用.
1. 相关工作
区块链是一种去中心化的分布式账本技术，通过将交易记录按照时间顺序连接成块，并使用密码学方法保证数据的安全性和完整性，实现了可信、不可篡改的数据存储. 将区块链技术应用于智能车联网，为车联网提供了去中心化的数据共享方式，减少了单点故障的风险. 在提升性能方面，文献[13]提出了一种车联网区块链资源管理方案，通过优化RSU和利用车辆的计算资源来提升吞吐量. 文献[14]设计了一种增强的委托权益证明（delegated proof of stake，DPoS）共识协议，加速了交易确认的同时缩短了数据共享时间，有效提升了车联网系统的吞吐量. 文献[15]提出了一种新型的区块验证方法，每个节点存储自身的交易验证记录，如果之前已验证过发送节点的区块，就简化验证过程，从而提升系统性能. 在增强安全性方面，文献[16]提出了一种基于区块链的车联网可信数据共享机制，利用基于Kademlia算法的流量数据转发方法来控制车联网中信道的拥塞状态，保证了重要数据在传输过程中的安全性. 文献[17]设计了一种双链并行的车联网信息共享方案，通过智能合约的自动执行实现数据的安全流通，并与区域内其他用户共享车联网数据. 文献[18]提出一种基于区块链和加权密文的车联网数据安全共享方法，基于特征对链上数据进行访问控制，确保只有授权的访问者才能访问数据内容，实现了车联网中安全的数据共享. 文献[19]设计了基于零知识证明的区块链数据共享方案，以匿名方式将数据和车辆信息相结合，并允许其他车辆和RSU匿名验证数据记录，实现安全的数据共享.
文献[13-19]方案主要是将区块链技术引入车联网数据共享与安全领域，对区块链系统的吞吐量性能考虑较少. 分片机制是提升吞吐量的主要手段之一，它将区块链节点划分为多个分片，各个分片可以并行地、独立地处理各自的交易和数据，这使得区块链的吞吐量能够线性扩展，即吞吐量可以随着节点数的增加而线性增长. 因此，分片技术可以用来解决区块链的可扩展性问题，且同时保持较高的安全性和去中心化程度. 现有的区块链分片方案，一般从分片节点的随机分配以保障安全性[8-12]、降低跨分片开销以提升吞吐量[20-22]、分片之间负载均衡以避免热点分片[12,23-25]、分片安全与效率平衡[26-27]、智能合约分片[28-29]等多个方面开展研究.
在分片区块链安全性方面，文献[9]利用有限布谷鸟原则以保证不同分片规模的平衡，并使用可验证秘密共享来生成无偏随机性，要求新加入节点解决工作量证明（proof of work，PoW）难题加入分片协议，从而抵御女巫攻击. 文献[10]中的每个共识周期，依赖可验证随机函数(verifiable random function,VRF)进行不可预测的领导者选举. 协议将领导者视为RandHound协议的客户来生成随机种子. 此外，还可以通过引入声誉机制来确保系统的安全与可信. 文献[30]提出一种基于区块链的隐私保护车辆数据共享框架，使用零知识证明技术以保护车辆的身份隐私，同时设计高效的分片协议降低系统的通信成本，增强系统的安全性. 针对分片内部共识安全问题，文献[31]基于车辆间历史交互信息和其他车辆的推荐信息评估该车辆的声誉，并赋予高声誉节点出块权力，从而确保数据共享的安全性和可追溯性. 然而，文献[9-10, 30-31]所述的方法要求对分片的高频率重构，且忽视了将参与共识的行为作为节点声誉的评估标准，难以适用于实际车联网动态变化环境，需要提出更简单高效的分片安全性保护方法和对节点的声誉评估方法.
2. 预备知识
2.1 区块链分片
将区块链分片协议进行形式化. 给定一个区块链网络，其中包含n个节点，每个节点维护全网的一部分交易历史，其中有f个拜占庭节点. 目标是将该区块链网络分割成k个分片，其中k≪n，以提高网络的可扩展性和性能. 每个分片i(1⩽包含1组节点，记作shar{d_i}， shard = \bigcap\limits_{i = 1}^m {shar{d_i}} ，且 shar{d_i} \cap shar{d_j} = \varnothing ，即所有节点被分片覆盖且分片间的节点互不相交. 区块链节点之间运行分片协议，输出一个集合X，其中包含 k 个不相交的分片或子集 {X_{{i}}} = \{ x_i^j\} (1 \leqslant j \leqslant \left| {{X_i}} \right|) . 区块 i 中的交易 j 被定义为 x_i^j . 节点可以通过使用函数C给定任何交易，输出1或0分别表示交易是否有效，以确定交易的合法性.
1）一致性. 对于 i \in \{ 1,2, … ,k\} ，所有诚实的节点对 {X_i} 达成一致.
2）有效性. 对于 i \;\in\; \{ 1,2, … ,k\} 和 j \;\in \;\{ 1,2,…,\left| {{X_i}} \right|\} ， C({x_{i,j}})= 1 .
3）可扩展性. k 随着网络规模或 n 的增长而线性增长.
2.2 基于声誉的共识协议
共识协议的主要功能是存在拜占庭节点的情况下，确保诚实节点能够维护一个一致的账本. 声誉机制在现代社会中扮演着至关重要的角色. 在人们进行决策时，往往会依赖公开的且基于声誉的排名系统来做出选择. 将声誉机制与共识协议相结合可以实现3个重要目标：
1）对参与共识的节点的历史行为进行评估，从而实现对节点的良性行为进行褒奖和对不当行为进行追责[32-33]；
2）基于节点的声誉，公平地选举诚实的节点参与共识并且提升协议的可扩展性[34-35]；
3）将节点投票权重转换为声誉，当系统中的恶意节点超过容错上限时，能使共识协议在一定时间内保证安全性与活性[32,34].
3. 基于分片区块链的车联网数据共享方案
3.1 系统模型
本文设计了一个支持分片的车联网区块链架构，由车载单元（on board unit，OBU）、RSU和可信机构（trusted authority，TA）组成. 系统模型及组件之间的关系如图1所示.
1）OBU. OBU通常依附于智能汽车，具备计算、存储和无线通信能力，可以与其他OBU、RSU、TA进行通信，在通信之前需要向TA发起并完成注册.
2）RSU. RSU是分片内参与共识的节点. 其主要职责是接收来自OBU的数据，并与其他RSU达成共识后，最终将数据上传至本地分布式账本. 在此过程中，假设每个分片中各个RSU的公钥是相互知晓的.
3）TA. TA为合法OBU和RSU颁发证书，并通过安全通道分发车辆和RSU的公钥和私钥.
OBU之间的通信以及OBU与RSU之间的通信采用IEEE 802.11p[36]或DSRC[37]协议，以上协议在数据传输过程中具有低延迟、高稳定的性质.
3.2 基于机器学习的分片算法
区块链中，节点数据可以被转化基于属性的表示形式，以便机器学习算法进行分析和应用于分片任务. 首先需要对基于机器学习的车联网分片问题进行定义.
定义1. 基于机器学习的车联网分片. 给定一个由N个RSU组成的集合：
V = \{ {c_i}=({x_i},{y_i}),w_i|x_i,y_i \in {\mathbb{R}} ,w_i \in (0,+\infty),i=1,2,…,N\}. (1) 其中ci代表RSU的2维位置坐标，表示RSU所在的地理位置；wi代表RSU的负载，表示RSU一定时间内的平均负载. 基于机器学习的车联网分片需要通过机器学习模型，最小化以下目标函数：
\arg \min \displaystyle\sum\limits_{i = 1}^k {\displaystyle\sum\limits_{v \in {X_i}} w } + \displaystyle\sum\limits_{i = 1}^k {\displaystyle\sum\limits_{v \in {X_i}} {||c - {\mu _i}||} } \text{，} (2) 其中v代表RSU节点，k代表分片数，Xi代表第i个分片，μi代表归属于第i个分片的所有RSU的位置均值， ||{c_i} - {\mu _j}|| 代表两点之间的欧氏距离.
现有的聚类算法一般是通过将邻近节点聚合成簇实现分片，满足片内节点相近的需求. 在车联网区块链分片中，若分片间负载不均衡，会导致基础设施资源分配失衡，进而造成资源浪费. 例如，在下班高峰时段，某个分片的车流量激增，导致该分片的RSU负载显著增加，无法高效地处理车辆数据，而其他分片的计算资源却处于闲置状态. 因此，实现负载均衡的分片能避免资源浪费，并提高数据共享效率. 本文提出了一种面向车联网区块链分片的均衡聚类算法，该算法在K-Means++[38]算法上使用正则项约束簇间负载以尽可能保持均衡，其损失函数为
L({c_i},{w_i},{\mu _j}) = ||{c_i} - {\mu _j}|| + {w_i}{(1 + \lambda )^{T - M + {w_i}}} \text{，} (3) \lambda = \exp \left(\dfrac{{\ln \bar w - \ln M}}{{\bar w - M}} - 1\right) \text{，} (4) T = \displaystyle\sum\limits_{v \in {X_j}} w \text{，} (5) M = \dfrac{{\displaystyle\sum w }}{k} \text{，} (6) 其中T代表第j个簇内所有节点负载之和，M代表每个簇的最优负载值， \lambda 代表损失函数的惩罚系数.
由式（3）可知，该损失函数由2部分组成：第1部分是距离损失 ||{c_i} - {\mu _j}|| ，其代表某个点与最近聚类中心的欧拉距离，与K-Means算法中的距离损失相同；第2部分是正则项 {w_i}{(1 + \lambda )^{T - M + {w_i}}} ，其代表分片负载均衡的惩罚项. 采用贪心算法为节点分配聚类簇，若分配的簇加入该节点后权重超过簇的最优负载值，惩罚项则会呈现指数增大，进而实现负载均衡的目标；而 \lambda 作为自适应权重，能够根据节点的权值与质心数自动调整，使得惩罚处于合理的范围内.
基于该损失函数的优化过程如算法1所示.
算法1. 均衡聚类算法.
输入：节点集V，分片数k；
输出：聚类结果.
① 用式（4）~（6）初始化λ, T, M；
② for iter in max_iters
③ clear cost[k]；
④ previous_assignment = assignment；
⑤ for each vi sampled from V
⑥ assign vi to kj by minimizing 式（3）；
⑦ cost[kj] += wi；
⑧ end for
⑨ for each kj in k
⑩ centers[kj] = mean(ci where assignment == kj)；
⑪ end for
⑫ if previous_assignment == assignment
⑬ break；
⑭ end if
⑮ end for
算法1采用贪心策略搜索最优的分片策略. 每次遍历将为当前节点分配损失最小的簇，并更新对应簇的负载值，直至算法收敛. 在搜索前期，惩罚项指数为负，该阶段的分配策略是距离优先；随着节点的不断分配，部分簇的负载已接近最优负载值，惩罚项会逐步增大，该阶段的分配策略是混合分配；在搜索末期，绝大多数簇已达到最优负载，分配策略是负载优先. 这种策略能够确保算法在前期形成簇状聚类结构，并在搜索过程中不断优化，进而在维持聚类结构的同时实现负载均衡. 值得注意的是，由于RSU的数据负载随着时间不断变化，因此每隔一定时间需重新运行均衡聚类算法以生成新的区块链分片.
3.3 基于声誉机制的片内共识
通过基于机器学习的分片算法将RSU分入若干个分片后，为了保证片内共识协议安全地运行，需要对片内RSU进行筛选，从而防止恶意的RSU主导共识过程. 本节对片内RSU选举的方式和参与共识的过程进行描述.
3.3.1 设计概览
单个分片内安全地运行共识协议存在2个挑战：1）基于机器学习的分片无法保证片内节点多数诚实，单个分片可能会被贿赂；2）当每个分片内RSU数量过多时，需要共识协议具备一定的可扩展性，从而保持系统性能的稳定.
为保证共识协议的最大容错能力，假设系统处于同步网络模型中，消息在2个RSU间的传播的延迟上限为\varDelta ，能容忍小于1/2的拜占庭节点. 为了保证分布式账本确定的一致性，需要在分片中设计一个同步拜占庭容错（Byzantine fault-tolerant，BFT）协议. 同时，由于各个分片中诚实的RSU数量未知，无法确保片内共识协议能安全运行. 对此，需要对每个RSU进行声誉的评估，通过声誉显式表达RSU的可信度. 此外，需要基于各个RSU的声誉选举高声誉的RSU参与片内共识. 基于声誉的状态机复制（reputation-based state machine replication，Reputation-based SMR）协议[32]是一个同步BFT协议，能对参与共识的节点行为进行评估，从而为每个节点评估所有节点公认的声誉. 当RSU作为参与共识的节点时，该协议能针对RSU的扣留区块（即RSU作为领导者拒绝提议区块）、提议冲突区块（即RSU作为领导者提议2个及2个以上的区块）、恶意投票（即RSU投票给非领导者区块）、恶意区块提议（即非领导者RSU提议区块）4个恶意行为对RSU的声誉进行削减. 同时，该协议能针对RSU的正常区块提议与投票增加RSU的声誉，因此该协议拥有普适性，能够很好地适用于车联网环境.
在Reputation-based SMR协议上设计片内共识节点选举函数，选择声誉高于阈值的RSU参与共识，避免声誉低的恶意节点主导共识. 同时，选举高声誉的节点参与共识而非分片内所有节点降低了协议的通信复杂度并提高了可扩展性，协议的性能不会随着片内节点的增多而明显下降.
3.3.2 协议描述
1）协议组件
基于声誉的片内共识协议将Reputation-based SMR协议与片内共识节点选举函数作为协议组成部分. Reputation-based SMR协议中的声誉机制能基于节点参与共识的行为，对产生不当行为的拜占庭节点声誉削减，并给予产生良性行为的节点声誉褒奖. 此外，Reputation-based SMR协议的证据广播阶段保证了声誉一致性.
定义2. Reputation-based SMR协议. 由领导者选举函数、拜占庭广播原语和声誉机制组成. Reputation-based SMR协议满足3个属性：
1）安全性. 任意2个诚实节点在同一高度上不会提交不同的区块.
2）声誉一致性. 在同一区块高度，任意2个诚实节点不会对某一节点产生不同的声誉视图.
3）活性. 如果1笔交易被1个诚实节点接受，那么这笔交易最终会被包含在所有诚实节点的账本上.
基于Reputation-based SMR协议构建片内共识节点选举函数，确保高声誉的节点参与共识. 具体过程如算法2所示.
算法2. 片内共识节点选举函数.
输入：分片内RSU的总数m，分片内RSU的公钥集合PK，分片内RSU的声誉集合U，当前轮次数q；
输出：高声誉RSU的公钥集合PK′.
① 初始化 PK' \leftarrow \varnothing ；
② x \leftarrow H(p{k_i},q) ；
③ if \tau {r_i} - \dfrac{x}{{{2^\eta }}} > 0 then
④ PK' \leftarrow PK' \cup {p_i} ；
⑤ else
⑥ PK' \leftarrow PK' ；
⑦ end if
算法2中， {r_i} 代表任意 {RSU_i} 的声誉； \tau 代表难度系数，控制各个节点被选举的难度；\eta 代表所选加密哈希函数的位长. 可以看出，RSU声誉越高，越容易超过给定阈值，从而担任共识节点. 反之亦然.
2）基于声誉的片内共识协议
通过片内共识节点选举函数与Reputation-based SMR协议构建基于声誉的片内共识协议. 协议流程如图2所示.
![]()
图 2 基于声誉的片内共识协议流程图注：各个节点更新自身当前轮次声誉，并执行片内共识节点选举函数.Figure 2. Flow chart of reputation-based intra-shard consensus protocol基于声誉的片内共识协议在由片内共识节点选举函数选举出的高声誉节点中执行提议、转发和投票步骤. 此外，基于声誉的片内共识协议通过分片内广播的共识结果与分片内所有RSU共享. 下面描述该协议的详尽过程.
1）节点更新声誉. 此步骤与Reputation-based SMR协议下的节点更新声誉步骤相同. RSU执行Reputation-based SMR协议中附带的声誉函数更新当前轮次的声誉并开启一个4\varDelta 的计时器.
2）区块生成. 分片内的RSU执行片内共识节点选举函数，选举高声誉RSU参与共识，并且被选举的高声誉RSU被公知. 在此基础上，通过Round-Robin选举领导者来进行区块提议. 如果某个RSU被片内共识节点选举函数选中，它将参与共识协议；否则，它将等待分片内广播传播的区块与各类证据.
3）片内广播. 这个阶段与Reputation-based SMR协议的证据广播阶段相似. 当计时器仅剩\varDelta 时，参与共识流程的RSU将在提议、转发和投票过程中产生的区块和各类证据（如扣留区块、良性区块提议等）广播给分片内所有节点. 分片内所有诚实RSU将会对这些内容达成共识.
4）区块提交. 此阶段与Reputation-based SMR协议的区块提交阶段相同. RSU根据在此轮共识中是否出现扣留区块证据或冲突区块证据来判定是否提交空块.
然而，当分片内恶意RSU数量过多时（如超过1/2时），无法以极大概率选举多个诚实的RSU参与共识. 此时，恶意RSU将有可能终止甚至主导片内的共识过程，并产生非法区块，从而影响分布式账本上区块的合法性. 在3.4节中将用监督人机制来解决这个问题.
3.4 监督人机制
分片机制将区块链节点划分为多个分片，每个分片内的分片规模远小于整个区块链网络的规模. 通常情况下，在相同的节点规模的基础上，分片数量的增加，即每个分片内节点数量的减少，有助于提高系统的吞吐量.
然而，片内节点数的减少会降低分片系统的安全性，例如：单个分片容易遭受贿赂攻击[39]. 节点规模为4 000个，未分片的区块链系统，敌手需要攻击区块链系统全网的1/3节点（1 667个节点）；分片后，在16个分片情况下，敌手仅需攻击分片系统中单个分片内的1/3节点（84个节点）.
同时，对片内共识协议能够支持的节点数量提出了新的要求. 例如：使用PBFT作为片内共识协议时，由于该算法的通信复杂度为 O({n^2}) ，当分片内节点数量增多时，其共识效率会大幅度降低，导致分片系统的总吞吐量快速下降. 因此，现有分片系统往往需要选择能够支持更多节点的片内共识协议[10].
采用超几何分布来计算每个分片在不同分片规模下，随机挑选出一个分片，其恶意节点数量大于1/2的概率（分片内恶意节点数量超过分片安全阈值）.
Pr\left[X \geqslant \left\lfloor {\dfrac{m}{2}} \right\rfloor \right] = \displaystyle\sum_{x = \left\lfloor {\tfrac{m}{2}} \right\rfloor }^m \dfrac{{\left( {\begin{gathered} t \\ x \end{gathered}} \right)\left( {\begin{gathered} {n - t} \\ {m - x} \end{gathered}} \right)}}{{\left( {\begin{gathered} n \\ m \end{gathered}} \right)}} \text{，} (7) 其中m代表分片规模，n代表区块链网络中的总节点数，t代表区块链网络中恶意节点的数量，x则是被随机选中组成一个分片的恶意节点数量.
当t = n/3时，即系统容忍不超过1/3的恶意节点. 图3展示了使用超几何分布模拟在4 000个节点的场景下，随机选择一个分片，并计算该分片中恶意节点比例超过1/2的概率. 由图3可以看出，分片规模越大，选取分片失败的概率越低，区块链系统的安全性越高，当分片规模超过250个节点时，其失败概率是可以接受的. 例如：RapidChain[9]在网络规模为4 000个节点时，将每个分片的节点数量限制在250个节点以保障极高的安全性，平均每4 500年才会出现1次故障.
现有的保证系统安全性的分片方案通常是定期地将各个分片中的节点进行全部打乱或者部分打乱. 然而，这种做法会破坏分片内节点之间的地理位置关系，不利于3.2节分片算法的实施. 此外，还引入了节点更换分片时数据移动的额外开销. 当1个节点从分片 \alpha 转移到分片\beta 时，它需要重新下载分片\beta 节点所存储的所有历史数据，以便能够验证分片\beta 后续的数据.
重新组建整个分片需要耗费大量时间和额外成本，但仅进行部分重新配置无法确保足够的安全性. 例如，在RapidChain[9]中，系统周期性地对分片进行重新划分，以确保大多数成员仍属于活跃分片. 当有新节点加入时，参考分片会根据一定规则随机地将新节点分片到某个活跃分片中，并将一定数量的节点从该活跃分片随机分配到其他的消极分片中，实现了新节点加入系统，控制了活跃分片和消极分片数量，达到了一种活跃节点间的平衡. 这种方式旨在平衡活跃分片数量以及不活跃分片数量，从而提高了整个区块链分片系统的活跃性、增加了敌手共谋攻击的成本，间接提高了系统的安全性. 但由于仅是对各个分片的部分节点进行重新配置，因此系统安全性提高的程度非常有限.
为了解决以上这些问题，本文提出了监督人机制，以代替现有的分片重构方案.
根据3.3节得到每个节点的声誉度，选取每个分片中声誉度较高的节点作为系统监督人，它们可以监督和验证分片系统中的数据. 这意味着每个数据同时被1个分片的所有节点以及监督人所验证，管理者可以通过调控奖惩机制来控制监督人的数量，达到所期望的性能与安全性的平衡.
车辆在行驶过程中，会不断地与周围的RSU进行通信. 每个RSU需要接收和传播数据，如图1所示. RSU接收到了新的车辆数据时，它会将带有车辆签名的数据传输给地理位置接近的若干个RSU. 在车辆数据产生时，RSU首先将数据发送至TA，TA向所有RSU广播数据，通过车辆单元的移动和RSU之间的交互，促使各分片之间可以共享数据，监督人也进而具备监督并验证所有分片数据的能力. 如果发现其他分片对某次数据进行作恶，任何一个验证了该分片数据的监督人都可以将其验证结果通知给分片系统，从而协同决定原始分片是否存在恶意行为，并进一步做出处理.
当节点加入系统时，每个节点需要缴纳一部分的押金，该押金由TA进行管理，用于防止节点在后续处理车联网数据时出现恶意行为. 并且，有利于避免恶意监督人以增加系统运行负担为目的而提交无效监督，提高恶意行为门槛. 若监督人发现非法数据，表明该数据所属分片已经被损坏，即分片内的恶意节点数量已经超过安全阈值. 在这种情况下，监督人提交一笔特殊交易，特殊交易包含监督信息以及用于防止恶意举报行为的押金. 区块链节点将根据这一特殊交易验证举报信息是否有效，验证结果分2种情况：1）如果举报有效，则返回监督人的举报押金，扣除恶意数据中包含的所有参与签名的节点的押金，并报告至TA，TA根据一定规则对监督人以及作恶节点进行奖惩，并降低作恶节点声誉；2）若举报无效，说明监督人提交了恶意的举报，则扣除监督人的举报押金以及基础押金，降低监督人节点的声誉.
监督人可以在恶意分片中、正常分片中、数据发起用户或者区块链网络之外的第三方. 它们可以从共享数据中存储数据，从而拥有对分片系统中所有分片数据验证的能力. 显然，节点保存选择验证分片系统中的数据越多，监督成功并获得的奖励就越多. 这一机制会鼓励更多的节点提高声誉度以及担任监督人的角色，形成积极循环，从而进一步增强车联网系统的安全性.
4. 安全性分析
4.1 共识协议安全属性分析
本节将证明由片内共识节点选举函数选举的RSU满足诚实多数. 此外，证明基于声誉的片内共识协议满足安全性、活性.
引理1. 诚实多数. 如果单个分片内诚实RSU数量大于1/2，则片内共识节点选举函数选出的RSU中至少一半是诚实的.
证明. 在最坏的情况下，所有节点的声誉值均为1. 片内共识节点选举可以看作一个独立的随机抽样问题，节点被选中的概率为
Pr[{R_j}{\text{ is selected}}] = \dfrac{{s{r_j}}}{{\displaystyle\sum\limits_{i = 1}^m {{r_i}} }} = \dfrac{s}{m} \text{，} (8) 其中 s 是被选中RSU的数量， m 是分片内RSU的总数， {r_j} 是某个RSU的声誉值.
假设 \rho = \dfrac{{m - {f^*}}}{m} 表示选举的节点为诚实节点的概率， \sigma = \dfrac{{{f^*}}}{m} 表示选举的节点为拜占庭节点的概率，其中 {f^*} 代表分片内恶意节点的数量. 随机变量A表示被选中RSU中诚实节点的数量，随机变量B表示选中RSU中拜占庭节点的数量. 随机变量A和B满足以下二项式分布：
Pr[A = k] = \left( \begin{gathered} m \\[-5pt] k \\ \end{gathered} \right){\left(\rho \dfrac{s}{m}\right)^k}{\left({\text{1}} - \rho \dfrac{s}{m}\right)^{m - k}} \text{，} (9) Pr[B = k] = \left( \begin{gathered} m \\[-5pt] k \\ \end{gathered} \right){\left(\sigma \dfrac{s}{m}\right)^k}{\left({\text{1}} - \sigma \dfrac{s}{m}\right)^{m - k}} \text{，} (10) 设 X 和 Y 分别表示为
X = \left\{ {A:0 \leqslant A \leqslant \left\lfloor {\dfrac{s}{2}} \right\rfloor } \right\} \text{，} (11) Y{\text{ = }}\left\{ {B:\left\lceil {\dfrac{s}{2}} \right\rceil \leqslant B \leqslant m} \right\} \text{，} (12) 当 X 和 Y 都未成立，被选中的RSU诚实大多数的性质成立. Pr[X \cup Y] 代表 X 和 Y 至少有1个成立，其概率为
\begin{split} Pr[X\cup Y] = &Pr[X]+Pr[Y]-Pr[X\cap Y]=Pr\left[A\le \left\lfloor \dfrac{s}{2}\right\rfloor \right]+\\ & Pr\left[B\ge \left\lceil \dfrac{s}{2}\right\rceil \right]= F\left(\left\lfloor \dfrac{s}{2}\right\rfloor ,m,\dfrac{\rho s}{m}\right)+\\ &F\left(m-\left\lceil \dfrac{s}{2}\right\rceil ,m,\text{1}-\dfrac{\sigma s}{m}\right)\text{，}\\[-1pt]\end{split} (13) 其中 F(k,m,p) = Pr[X \leqslant k] 是随机变量 X \sim B(m,p) 的累积分布函数，根据二项式尾界定理可知
Pr[X\cup Y]\le 2\mathrm{exp}\left(-2m{\left(\dfrac{\lfloor s/2\rfloor -\sigma s}{m}\right)}^{2}\right)\text{=}\epsilon \left(s\right)， (14) 被选举的RSU满足诚实多数. 证毕.
引理2. 安全性. 如果片内共识节点选举函数选举出的RSU满足诚实多数且Reputation-based SMR协议满足安全性，那么基于声誉的片内共识协议也满足安全性.
证明. 假设基于声誉的片内共识协议不满足安全性，即这里存在某个出块周期，在这个周期中2个诚实RSU提出了2个不同的区块b与b′. 通过引理1，被选举出的RSU符合诚实多数的性质，且Reputation-based SMR协议满足安全性性质，对于任意2个被选中的诚实RSU，它们在同一个周期会对相同区块达成共识并提交相同的区块到本地的区块链上. 这与假设相反，因此基于声誉的片内共识协议满足安全性. 证毕.
引理3. 活性. 如果片内共识节点选举函数选举出的RSU满足诚实多数且Reputation-based SMR满足活性，则基于声誉的片内共识协议满足活性.
证明. 假设基于声誉的片内共识协议不满足安全性，即这里存在一个交易被诚实的RSU接受，但最终没有被所有诚实的RSU提交到本地的账本上. 通过引理1，被选举出的RSU符合诚实多数的性质，在此基础上通过轮询调度算法选举的领导者要么是诚实RSU，要么是恶意RSU（拜占庭节点）. 如果领导者是诚实RSU，那么领导者会提议一个区块到所有节点，并且在片内广播后，所有诚实节点将在本地提交这一区块. 如果领导者是恶意RSU，那么该RSU要么遵循协议，要么背离协议. 当RSU遵循协议时，结果与诚实RSU担任领导者时相同. 反之，当RSU背离协议时，因为Reputation-based SMR协议满足活性与片内广播，最终所有的交易都将提交到每个分片中节点的账本上. 这与假设相反，因此基于声誉的片内共识协议满足活性. 证毕.
引理4. 声誉一致性. 如果基于声誉的片内共识协议满足安全性，则基于声誉的片内共识协议满足声誉一致性.
证明. 假设某一共识轮次结束时，分片内存在2个诚实的RSU1和RSU2对RSU3的声誉视图不同. 通过引理2，基于声誉的片内共识协议满足安全性，这表明在任意一个周期，任意2个诚实的RSU提交由诚实的领导者RSU提议的区块或空块. 如果提交空块，这表明领导者RSU是恶意的并且扣留区块或提议冲突区块，在当前共识轮次的计时器还剩1个\varDelta 时，这2种行为都会被委员会内至少1个诚实的RSU所检测. 委员会内所有诚实的RSU会将检测到的行为与区块广播给片内所有RSU，片内所有诚实的RSU会根据收到的行为更新在其视图上各个节点的声誉，从而使所有诚实的RSU拥有相同的声誉视图，这与假设相反. 如果提交的区块是正常区块，那么存在2种情况：1）协议的执行中不存在不当行为；2）协议执行的过程中存在不影响共识安全性的不当行为，即恶意区块提议与恶意投票行为. 对于情况1，所有诚实的RSU通过声誉函数一致地更新其本地声誉视图，这与假设相反. 对于情况2，它与诚实节点提交空块的情况相同，在片内广播后，所有诚实的RSU将获得相同的节点声誉视图，这与假设相反. 证毕.
4.2 监督人机制安全性分析
假定分片系统中存在 n 个监督人，分片系统在运行时，每当产生 t 个由不同分片生成的区块时，监督人需要对这些区块进行验证以确认其数据合法性. 每个监督人至少需要验证1个区块，同时，为了增加系统的安全性，验证区块的选择必须具备一定的不可预测性，以确保潜在的敌手无法轻易获悉下一个需要验证的区块.
监督人从 t 个块中选取的规则为：首先，每个监督人以不可预测的方式选取1个区块. 接着，对于剩下的 t - 1 个区块，监督人对每个区块的选择验证的概率均为 x .
本文引入了以下区块选择规则选择必选区块，以增强监督人区块选择的不可预测性.
区块序号=H(最新区块哈希值||唯一标识符) {\rm mod} \;t， (15) 其中区块序号是监督人从 t 个区块中选取的， H() 是一个安全的、单向的哈希函数，其将最新的区块哈希值和监督人标识符转换为一个确定的值. 其次， || 表示字符串连接操作符， {\text{mod }}t 表示对结果取模运算. 最后，这个规则的应用范围是分片系统中需要验证的区块.
通过引入这个区块选择规则，可以增加系统的安全性，因为敌手无法轻易预测每一个监督人需要验证的区块，这使得潜在的敌手难以进行恶意行为，从而保护了整个分片系统的安全性和稳定性.
根据以上规则，在必选验证环节，某个区块不被所有监督人随机以不可预测选中验证的概率为
Pr(C) = {\left( {\dfrac{{t - 1}}{t}} \right)^n} \text{，} (16) 对于剩下的 t - 1 个区块，某个区块不被某个监督人随机选择的概率可以用 1 - x 表示. 此外，各个区块不被所有监督人选择是相互独立的，符合二项分布，可表示为
Pr(D) = {(1 - x)^n} \text{，} (17) 最终，某个区块不被监督人所验证的概率为
Pr(\text{block is not selected}) = Pr(C)\times Pr(D) = {\left( \dfrac{t-1}{t} \right)}^{n} (1 - x)^n\text{，} (18) 式（18）反映了监督人机制的安全性. 假设t = 10，系统共有n = 80个监督人，x = 0.3，一个区块不被监督人验证的概率为 3.86 \times {10^{ - 12}} . 可以得知，分片系统中每个区块都以高概率被监督人所验证. 随着监督人数量的增加，某个特定区块不被选中的概率逐渐减小，从而增大了分片系统的安全性. 一方面涉及监督人必选验证环节的不可预测性，另一方面涉及监督人随机验证区块的不可预测性. 敌手难以预测哪个监督人将验证哪个区块，保证了分片系统的安全性.
5. 实验评估
5.1 分片方案性能评估
本节对所提出基于机器学习的分片算法进行实验评估. 本实验基于Python语言实现均衡聚类、K-Means++[38]、层次聚类[40]和随机分配等算法，并评估它们的簇间负载方差与聚类距离成本. 结果显示均衡聚类算法得到的分片结果在距离成本几乎没有增加的情况下，簇间负载方差显著低于其他算法. 此外，在RSU节点负载不均衡、呈现指数分布的情况下，均衡聚类算法仍然能够维持较低的簇间负载方差与聚类距离成本.
通过实验，评估以下2个问题：
1）RSU节点负载呈现均匀分布下，随着RSU节点负载的增加，均衡聚类算法和其他3个算法的聚类距离成本与簇间负载方差的变化趋势；
2）RSU节点负载呈现指数分布下，随着RSU节点负载的增加，均衡聚类算法和其他3个算法的聚类距离成本与簇间负载方差的变化趋势.
5.1.1 实验设置与实现
实验基于Python3.10实现，采用numpy1.62.2实现均衡聚类算法和随机分配算法，采用scikit-learn1.3.2实现K-Means++与层次聚类算法，采用matplotlib3.8.2与seaborn0.13.0实现数据可视化. 随机分配算法是目前绝大多数区块链分片方案所采用的算法；层次聚类算法相较K-Means++算法具有更强的可解释性，被广泛应用于无监督聚类. 对于地理位置呈现随机分布的RSU节点，K-Means++算法与层次聚类算法能够将相近的RSU节点划分至同一分片，相较随机分配算法更加适用于车联网区块链.
实验模拟了200个RSU并将其划分为15个分片，其中每个RSU拥有位置信息与负载状态2种属性. 实验从标准均匀分布中采样200个2维数据作为RSU的位置信息，分别从均匀分布与指数分布中采样200个1维数据作为RSU的负载状态，且分布的期望值线性增大，进而模拟RSU的负载状态在不同分布、不同大小下分片算法的性能.
实验中涉及的性能指标为簇间负载方差和聚类距离成本，以每个RSU与其分片中心的平均欧拉距离为单位. 簇间负载方差能够直观反映各个分片间负载的差异性，方差越大则代表算法负载均衡的能力越差. 而每个RSU与其分片中心的平均欧拉距离（以下简称簇均值）能够反映簇内紧凑性. 采用以上2种指标对片内节点距离相近和片间负载均衡2个要素进行评估.
5.1.2 均衡K-Means性能评估
图4展示了4种算法簇间负载方差随RSU节点平均负载的变化. 相对于其他3种算法，均衡K-Means簇间方差更低. 随着RSU负载逐步提升，其余3种算法的簇间负载方差均指数级增长；而均衡K-Means线性增长，表明该算法具有更强的负载均衡能力.
![]()
图 4 4种算法的簇间负载方差对比Figure 4. Comparison of load variance between clusters of four algorithms图5与图6分别展示了4种和3种算法聚类距离成本随RSU节点平均负载的变化. 随机分配算法的簇均值显著高于其他算法，表明同一分片的节点在地理位置上分布稀疏，车辆之间的数据共享协同效率更低. 除随机分配算法以外的3种聚类算法均将地理位置相近的节点划分至同一分片，均衡K-Means与另外2种算法在簇均值上相近，均保持在较低水平，表明该算法满足车联网区块链分片的2个要素.
![]()
图 5 4种算法的聚类距离成本对比Figure 5. Comparison of clustering distance costs of four algorithms![]()
图 6 3种算法的聚类距离成本对比Figure 6. Comparison of clustering distance costs of three algorithms图7展示了负载呈指数分布与均匀分布的差异. 相对于均匀分布，指数分布下的RSU负载不均衡程度显著增加. 图8展示了除随机分配以外的3种算法在该实验设置下的聚类簇间方差. 在RSU负载不平衡的情况下，最高方差超过600 000，表明K-Means++与层次聚类算法的片间负载存在极大的差异. 均衡K-Means方差最高未超过100 000，显著优于其他算法. 由于RSU负载不平衡，维持分片间节点均衡将会付出更多的距离成本. 图9展示了除随机分配以外的3种算法在该实验设置下的聚类距离成本. 相对其他算法，均衡K-Means的簇均值略有上升，仅提升0.2左右，表明其仍然保持较为紧凑的聚类结构.
![]()
图 7 负载呈均匀分布与指数分布的差异Figure 7. Difference between balanced load distribution and exponential distribution![]()
图 8 负载呈指数分布下的聚类簇间方差Figure 8. Inter-cluster variance of clusters under exponential load distribution![]()
图 9 负载呈指数分布下的聚类距离成本Figure 9. Clustering distance cost under exponential load distribution图10对比了4种算法的聚类可视化结果. 相较随机分配算法，其他3种算法生成的聚类结构边界清晰，表明它们能够将相邻的节点划分至同一分片，满足片内节点相近的需求. 而K-Means++与层次聚类算法仅考虑片内节点相近，难以满足车联网区块链分片中负载均衡的要求. 相较K-Means++与层次聚类算法，均衡聚类算法簇间负载方差更低，更加适用于车联网区块链分片. 聚类结构同样反映了均衡聚类算法特点，即部分分片间节点出现“交叉”. 由于节点分配时需要同时考虑负载与距离2个因素，部分节点为了实现负载均衡，未加入距离最近的簇，导致“交叉”的出现，表明均衡聚类算法更加符合车联网区块链分片的需求.
5.2 片内共识性能评估
本节对所提出片内共识协议进行实验评估. 该实验通过Go语言实现基于声誉的片内共识协议，并在云实例上评估它们的吞吐量与共识时延. 结果显示在多个分片中基于声誉的片内共识协议的共识时延与Reputation-based SMR基本相同. 且随着分片中RSU数量的增加，基于声誉的片内共识协议的吞吐量下降幅度低于Reputation-based SMR协议与Sync-HotStuff协议[41]. 此外，随着分片数量的增长，基于声誉的片内共识协议相较于Reputation-based SMR吞吐量更优，且相较于Sync-HotStuff协议没有显著的吞吐量差距.
通过实验，评估以下3个问题：
1）在单个分片内，随着区块中包含的交易的增加，基于声誉的片内共识协议的性能变化趋势；
2）在单个分片内，随着RSU数量的增加，基于声誉的片内共识协议与Reputation-based SMR共识时延和吞吐量的变化趋势；
3）随着分片数量的增长，基于声誉的片内共识协议共识时延和吞吐量的变化趋势.
5.2.1 实验设置与实现
本节的实验利用libp2p完成点对点网络的搭建，采用protobuf进行信息的序列化与反序列化以便在网络中传递数据，采用secp256k1椭圆曲线算法来执行数字签名，采用SHA256作为哈希函数. 使用Go语言成功实现了Sync-HotStuff、Reputation-based SMR以及基于声誉的片内共识协议. 在协议的实现中，每个区块包含由OBUs发送的多个交易. 将每个区块包含的最多的交易数量称为该区块的大小，设置同步网络上限时延\varDelta =0.25 s，即基于声誉的片内共识协议和Reputation-based SMR的时延计时器的设定均为1 s. 而对于Sync-HotStuff，相较于以上2个协议缺少证据广播阶段和片内广播阶段，因此其时延计时器设定为0.75 s.
基于声誉的片内共识协议部署在阿里云实例上，参数如表1所示.
表 1 云服务器配置参数Table 1. Elastic Compute Service Configuration Parameters参数 配置环境 实例规格 ecs.c7a.8xlarge 处理器核心数 32 内存/GB 256 本地存储/GB 100 处理器主频/GHz 3.5 内网带宽/GBps 25 内网收发包/PPS 1200 万处理器型号 AMD EPYC™ Milan 7T83 镜像操作系统 Ubuntu18.04 64位 实验中涉及的性能指标主要为共识时延与吞吐量.
5.2.2 基于区块大小的协议性能评估
将车辆产生的每条数据近似看成区块中的1笔交易，在区块大小分别为400，800，
1600 笔交易的条件下，固定每笔交易大小为64 B，测试了基于声誉的片内共识协议的性能. 通过控制OBU节点发送命令的时间间隔来模拟不同的负载，OBU节点发送每个命令的速度越快，客户端在给定时间拥有的未完成命令池就越大. 如图11所示，最开始增加OBU发送请求的速率不会对延迟产生影响，因为节点的带宽还没有达到饱和状态. 随着节点负载的增加，吞吐量会增加，但延迟仍然保持稳定，直到系统的带宽达到饱和. 一旦带宽饱和，随着负载的增加，吞吐量将保持不变或稍微下降，而延迟则会上升. 由图11可知，基于声誉的片内共识协议的吞吐量在720 tps左右达到带宽饱和，将以800区块大小与64 B交易大小作为后续实验的固定参数.![]()
图 11 不同区块大小对协议性能的影响Figure 11. Impact of different block sizes on protocol performance5.2.3 基于RSUs节点数量的协议性能评估
图12与图13展示了在单个分片中，随着RSU数量的增加，Reputation-based SMR协议、Sync-HotStuff协议与基于声誉的片内共识协议在共识时延与吞吐量2个性能指标上的对比. 设置RSU个数分别为5，9，17，33，从图12与图13中可以观察到，随着RSU数量的增加，基于声誉的片内共识协议的共识时延增长速率与吞吐量的下降速率明显低于Reputation-based SMR协议. 且当网络中RSU数为33时，基于声誉的片内共识协议的时延和吞吐量分别约为1 600 ms，490 tps，相较于Reputation-based SMR协议的时延和吞吐量分别为2 100 ms和280 tps左右，基于声誉的片内共识协议有着更优的性能. 而对于Sync-HotStuff，该协议不具有对RSU不当行为追责的能力，但有更低的共识时延与更高的吞吐量. 随着RSU数量的增加，Sync-HotStuff协议的性能明显下降，当RSU数量为33时，Sync-HotStuff协议的时延和吞吐量分别为1 590 ms，492 tps左右，这表明随着RSU数量的增加，基于声誉的片内共识协议与Sync-HotStuff协议在性能上的差距会逐步减小. 其原因是基于声誉的片内共识协议通过小规模RSU替代分片内所有RSU参与共识，从而带来了更低的通信损耗，这意味着基于声誉的片内共识协议的性能不会随着片内RSU的增多而明显下降.
![]()
图 12 RSU数量对协议吞吐量的影响Figure 12. Impact of the number of RSU on the throughput of protocol5.2.4 基于分片数量的协议性能评估
为了尽可能体现基于声誉的片内共识协议能对高声誉节点进行选举，从而保证片内共识协议的正常运行，本节设计了如下实验. 固定每个分片中RSU节点数为11，测试分片数量分别为1，3，5，7的情景下2个协议的吞吐量. 当分片数量为3时，设定其中一个分片的恶意RSU为6个（为了简化实验的进行，通过代码沉睡这6个节点，使其不参与片内共识协议）. 同时，因为恶意节点不参与共识过程，它们的声誉远小于其他节点，将这样的分片称为恶意分片. 同理，当分片数量为5时，恶意分片数量为2；当分片数量为7时，恶意分片数量为3.
图14展示了Sync-HotStuff，Reputation-based SMR和基于声誉的片内共识协议在不同分片数量下的吞吐量变化趋势. 随着分片数量的增加，系统吞吐量明显上升. Reputation-based SMR协议的吞吐量低于基于声誉的片内共识协议. 而对于Sync-HotStuff，因为其在单个分片内拥有更高的吞吐量，当分片数量为1且不存在恶意分片时，该协议有着最优的性能. 随着恶意分片数量的增多，基于声誉的片内共识协议与Sync-HotStuff协议在吞吐量上并未体现出明显的差距. 其原因是，在恶意分片中Sync-HotStuff与Reputation-based SMR无法通过足够的签名来完成共识. 而对于基于声誉的片内共识协议，它通过片内共识节点选举，使片内诚实RSU提供签名并完成共识.
![]()
图 14 分片数量对协议吞吐量的影响Figure 14. Impact of the number of shards on the throughput of protocol6. 结 论
本文提出了一种基于机器学习分片的车联网区块链数据共享方案，每个分片负责存储和管理特定类型的车联网数据，使得设备间的数据共享可以并发执行，提高了数据共享的效率. 为了保证分片方案的安全性，本文提出了基于声誉的共识协议和监督人机制，通过片内共识节点选举函数尽可能地保证高声誉的诚实RSU参与并完成共识. 监督人机制使节点从共享数据中存储数据并获得验证其他分片数据的能力，进一步有助于提高系统的安全性. 性能评估和安全分析证明，本文方案可以实现安全高效的车联网数据共享.
作者贡献声明：陈骁、黄牧鸿负责方案整体设计并撰写论文；田一凡、王岩负责部分算法思路和实验方法；曹晟、张小松提出指导意见并修改论文.
-
表 1 仿真数据的4种场景
Table 1 Four Scenarios of Simulation Data
场景 分布变化类型（路径长度） 重尾噪声参数 S1 逐渐变化 （3.14） \left(\varepsilon,c\right)=(1,3) S2 突然变化 （5.41） \left(\varepsilon ,c\right)=(1,3) S3 逐渐变化 （3.14） \left(\varepsilon ,c\right)=(1,10) S4 突然变化 （5.41） \left(\varepsilon ,c\right)=(1,10) 
下载: 导出CSV
表 2 不同算法的每轮平均遗憾结果
Table 2 Average Regret Results Per-round on Different Algorithms
场景 LinUCB RestartUCB MENU RM-LinUCB S1 0.8061 0.5757 0.6294 0.5436 S2 0.8490 0.6676 0.8041 0.5159 S3 0.7999 0.4174 0.5612 0.4307 S4 0.7947 0.5316 0.8011 0.4088
下载: 导出CSV
表 3 真实数据集统计信息
Table 3 Statistics of Real-world Datasets
数据集 维度 样本数 数据集 维度 样本数 bolts 2 87 pokerhand 10 1000000 cloud 5 108 Criteo 10 16468027 slumptest 9 103 COMPAS 25 11001 kidney 10 76 Last.fm 25 12523 forestfire 10 517 Delicious 25 68755
下载: 导出CSV
-
[1] Bubeck S, Cesa-Bianchi N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems[J]. Foundations and Trends in Machine Learning, 2012, 5(1): 1−122 doi: 10.1561/2200000024
[2] Woodroofe M. A one-armed bandit problem with a concomitant variable[J]. Journal of the American Statistical Association, 1979, 74(368): 799−806 doi: 10.1080/01621459.1979.10481033
[3] Li Lihong, Chu Wei, Langford J, et al. A contextual-bandit approach to personalized news article recommendation [C] //Proc of the 19th Int Conf on World Wide Web (WWW). New York: ACM, 2010: 661–670
[4] Cont R, Bouchaud J. Herd behavior and aggregate fluctuations in financial markets [J]. Macroeconomic dynamics, 2000, 4（2）: 170−196
[5] Roberts, James A, Tjeerd W, et al. The heavy tail of the human brain[J]. Current Opinion in Neurobiology, 2015, 31: 164−172 doi: 10.1016/j.conb.2014.10.014
[6] Naoki A, Philip M L. Associative reinforcement learning using linear probabilistic concepts [C] //Proc of the 16th Int Conf on Machine Learning (ICML). San Francisco, CA: Morgan Kaufmann, 1999: 3–11
[7] Dani V, Hayes T P, Kakade S M. Stochastic linear optimization under bandit feedback [C] //Proc of the 21st Annual Conf on Learning Theory (COLT). San Francisco, CA: Morgan Kaufmann, 2008: 355−366
[8] Abbasi-Yadkori Y, Pál D, Szepesvári C. Improved algorithms for linear stochastic bandits [C] //Advances in Neural Information Processing Systems 24 (NIPS). Red Hook, NY: Curran Associates, Inc, 2011: 2312–2320
[9] Abbasi-Yadkori, Y, Pal D, Szepesvari C. Online-to-confidence-set conversions and application to sparse stochastic bandits [C] //Proc of the 15th Int Conf on Artificial Intelligence and Statistics (AISTATS). San Francisco, CA: Morgan Kaufmann, 2012: 1–9
[10] Agrawal S, Goyal N. Thompson sampling for contextual bandits with linear payoffs [C] //Proc of the 30th Int Conf on Machine Learning (ICML). San Francisco, CA: Morgan Kaufmann, 2013: 127–135
[11] Soare M, Lazaric A, Munos R. Best-Arm identification in linear bandits [C] //Advances in Neural Information Processing Systems 27 (NIPS). Red Hook, NY: Curran Associates, Inc, 2014: 828–836
[12] Li Yingkai, Wang Yining, Zhou Yuan. Nearly minimax-optimal regret for linearly parameterized bandits [C] //Proc of the 32nd Conf on Learning Theory (COLT). San Francisco, CA: Morgan Kaufmann, 2019: 2173–2174
[13] Zhou Yuan, Song Shihong, Zhang Huishuai, et al. Regularized OFU: An efficient UCB estimator for non-linear contextual bandit [J]. arXiv preprint, arXiv: 2106.15128, 2021
[14] Lattimore T, Szepesvári C. Bandit Algorithms [M]. Cambridge, UK: Cambridge University Press, 2019
[15] Dietterich T G. Steps toward robust artificial intelligence[J]. AI Magazine, 2017, 38(3): 3−24 doi: 10.1609/aimag.v38i3.2756
[16] Dietterich T G. Robust artificial intelligence and robust human organizations[J]. Frontiers Computer Science, 2019, 13(1): 1−3 doi: 10.1007/s11704-018-8900-4
[17] Zhou Zhihua. Learnware: On the future of machine learning[J]. Frontiers of Computer Science, 2016, 10(4): 589−590 doi: 10.1007/s11704-016-6906-3
[18] Zhao Peng, Wang Guanghui, Zhang Lijun, et al. Bandit convex optimization in non-stationary environments[J]. Journal of Machine Learning Research, 2020, 22(125): 1−45
[19] Chen Wei, Wang Liwei, Zhao Haoyu, et al. Combinatorial semi-bandit in the non-stationary environment [C] //Proc of the 37th Conf on Uncertainty in Artificial (UAI). San Francisco, CA: Morgan Kaufmann, 2021: 865−875
[20] Zhang Lijun, Lu Shiyin, Zhou Zhihua. Adaptive online learning in dynamic environments [C] //Advances in Neural Information Processing Systems 31 (NeurIPS). Red Hook, NY: Curran Associates, Inc, 2018: 1330–1340
[21] Zhao Peng, Zhang Yujie, Zhang Lijun, et al. Dynamic regret of convex and smooth functions [C] // Advances in Neural Information Processing Systems 33 (NeurIPS). Red Hook, NY: Curran Associates, Inc, 2020: 12510–12520
[22] Zhao Peng, Wang Yuxiang, Zhou Zhihua. Non-stationary online learning with memory and non-stochastic control [C] //Proc of the 25th Int Conf on Artificial Intelligence and Statistics (AISTATS). San Francisco, CA: Morgan Kaufmann, 2022: 2101−2133
[23] Wei Chenyu, Luo Haipeng. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach [C] //Proc of the 34th Conf on Learning Theory (COLT). San Francisco, CA: Morgan Kaufmann, 2021: 4300–4354
[24] Zhao Peng, Cai Lewen, Zhou Zhihua. Handling concept drift via model reuse[J]. Machine Learning, 2020, 109(3): 533−568 doi: 10.1007/s10994-019-05835-w
[25] Cheung W C, Simchi-Levi D, Zhu Ruaihao. Learning to optimize under non-stationarity [C] //Proc of the 22nd Int Conf on Artificial Intelligence and Statistics (AISTATS). San Francisco, CA: Morgan Kaufmann, 2019: 1079–1087
[26] Guo Lei, Ljung L, Priouret P. Performance analysis of the forgetting factor RLS algorithm[J]. International Journal of Adaptive Control and Signal Processing, 1993, 7(6): 525−538 doi: 10.1002/acs.4480070604
[27] Zhao Peng, Wang Xinqiang, Xie Siyu, et al. Distribution-free one-pass learning[J]. IEEE Transaction on Knowledge and Data Engineering, 2021, 33(3): 951−963
[28] Russac Y, Vernade C, Cappé O. Weighted linear bandits for non-stationary environments [C] //Advances in Neural Information Processing Systems 32 (NeurIPS). Red Hook, NY: Curran Associates, Inc, 2019: 12040–12049
[29] Zhao Peng, Zhang Lijun, Jiang Yuan, et al. A simple approach for non-stationary linear bandits [C] //Proc of the 23rd Int Conf on Artificial Intelligence and Statistics (AISTATS). San Francisco, CA: Morgan Kaufmann, 2020: 746–755
[30] Liu Keqin, Zhao Qing. Multi-armed bandit problems with heavy-tailed reward distributions [C] //Proc of the 49th Annual Allerton Conf on Communication, Control, and Computing. Piscataway, NJ: IEEE, 2011: 485–492
[31] Bubeck S, Cesa-Bianchi N, Lugosi G. Bandits with heavy tail[J]. IEEE Transactions on Information Theory, 2013, 59(11): 7711−7717 doi: 10.1109/TIT.2013.2277869
[32] Vakili S, Liu Keqin, Zhao Qing. Deterministic sequencing of exploration and exploitation for multi-armed bandit problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(5): 759−767 doi: 10.1109/JSTSP.2013.2263494
[33] Hsu D, Sabato S. Heavy-tailed regression with a generalized median-of-means [C] //Proc of the 31st Int Conf on Machine Learning (ICML). San Francisco, CA: Morgan Kaufmann, 2014: 37–45
[34] Audibert J Y, Catoni O. Robust linear least squares regression[J]. The Annals of Statistics, 2011, 39(5): 2766−2794
[35] Medina A M, Yang S. No-regret algorithms for heavy-tailed linear bandits [C] //Proc of the 33rd Int Conf on Machine Learning (ICML). San Francisco, CA: Morgan Kaufmann, 2016: 1642–1650
[36] Shao Han, Yu Xiaotian, King I, et al. Almost optimal algorithms for linear stochastic bandits with heavytailed payoffs [C] //Advances in Neural Information Processing Systems 31 (NeurIPS). Red Hook, NY: Curran Associates, Inc, 2018: 8420–8429
[37] Xue Bo, Wang Guanghui, Wang Yimu, et al. Nearly optimal regret for stochastic linear bandits with heavy-tailed payoffs [C] //Proc of the 29th Int Joint Conf on Artificial Intelligence (IJCAI). San Francisco, CA: Morgan Kaufmann, 2020: 2936−2942
[38] Yu Jiayuan, Mannor S. Piecewise-stationary bandit problems with side observations [C] //Proc of the 26th Annual Int Conf on Machine Learning (ICML). San Francisco, CA: Morgan Kaufmann, 2009: 1177–1184
[39] Benedetto D G, Bellini V, Zappella G. A linear bandit for seasonal environments [J]. arXiv preprint, arXiv: 2004.13576, 2020
[40] Asuncion A, Newman D. UCI machine learning repository[CP/OL]. 2007[2022-06-21].https://archive.ics.uci.edu/ml/index.php
[41] Cesa-Bianchi N, Gentile C, Zappella G. A gang of bandits [C] //Advances in Neural Information Processing Systems 26 (NIPS). Red Hook, NY: Curran Associates, Inc, 2013: 737–745
[42] Dressel J, Farid H. The accuracy, fairness, and limits of predicting recidivism [J/OL]. Science Advances, 2018 [2022-06-21].https://www.science.org/doi/epdf/10.1126/sciadv.aao5580
[43] Diemert E, Meynet J, Galland P, et al. Attribution modeling increases efficiency of bidding in display advertising [C/OL] //Proc of the 23rd ACM SIGKDD Conf on Knowledge Discovery and Data Mining (AdKDD). New York: ACM, 2017 [2022-08-23].https://dl.acm.org/doi/abs/10.1145/3124749.3124752
-
期刊类型引用(5)
1. 宋朋，赵伯鸾. 农业机械车路协同辅助驾驶路线规划系统的设计与实现. 农机化研究. 2025(06): 232-238 . 
百度学术
2. 尹璐，周俊龙，孙晋，吴泽彬. 不确定性感知的边缘计算任务调度算法. 控制与决策. 2024(07): 2405-2413 . 百度学术
3. 侯祥鹏，兰兰，陶长乐，寇小勇，丛佩金，邓庆绪，周俊龙. 边缘智能与协同计算:前沿与进展. 控制与决策. 2024(07): 2385-2404 . 百度学术
4. 李超，李文斌，高阳. 图多智能体任务建模视角下的协作子任务行为发现. 计算机研究与发展. 2024(08): 1904-1916 . 本站查看
5. 夏思洋，朱学芳. 5G环境下基于边缘计算的图书馆智慧服务响应能力研究. 情报理论与实践. 2023(12): 21-27+51 . 百度学术
其他类型引用(0)
计量
- 文章访问数: 269
- HTML全文浏览量: 139
- PDF下载量: 153
- 被引次数: 5
