区块链中的自适应广播路由分配算法

秦 毅

(重庆电子工程职业学院人工智能与大数据学院 重庆 401331)

0 引 言

区块链是一种技术，允许双方之间记录交易的每个主机可验证和永久分散的分类账[1-2]，较为流行的应用是加密货币(如比特币)。当Internet上的其他主机完成验证时，最新块将成为附加区块链的一部分，每个块包括使用哈希函数和加密密钥加密的多个事务[3]，块头中的元数据集被记录到关系中并与其他块链接。Internet上的任何主机都可以联合验证事务作为验证贡献者，并检查块是否正确[4]。这种主机的协作称为比特币应用程序中的挖掘。

当使用区块链时，该区块具有一系列过程(如交易和支付)的数字签名，其可以追溯到个人以进行识别、验证和确认。节点保持的块被分散以便共享给每个主机，这种分散的系统可以保护区块链免受篡改、删除和修改[5]。为了保持分类账副本的一致性，主机需要就事务达成一致。广播机制提供由其中一个节点创建的用于暂时提交事务的新块，并且以规则的间隔同步。该块被广播并分发给所有主机以进行验证和确认[6]，完成确认的最快节点收到奖励或加密货币金额，传输和计算延迟是矿工的关键因素[7]。

广播路由机制的服务质量(QoS)路由的目标是找到具有足够可用资源的可行路径，以满足网络中节点的QoS要求并实现有效的资源使用[8]。延迟、带宽、延迟抖动、吞吐量和丢包率是将块广播到所有矿工主机的路由策略的QoS测量[9]。研究确定优化问题的可行路径，并找到了成本最低的可行解决方案，文献[10]对各种QoS路由算法进行了分析，分为源路由算法、分布式路由算法和分层路由算法。文献[11]提出了最小生成树(MST)，涉及无向生成树的分配，当在网络中使用MST时，考虑QoS问题是必要的，受路由树的QoS约束的最短路径问题，MST问题是NP难问题。

目前区块链已经被用于复制因特网上所有矿工设备的交易数据。网络资源管理已通过软件定义网络(software-defined networking, SDN)和网络功能虚拟化(network function virtualization, NFV)适应资源容器化[12]。SDN是一种可编程机制[13]，可以动态灵活地控制路由路径和链路管理，实现端到端通信。NFV是网络功能可以转换为基于软件的应用程序的概念，可以用于区块链广播方法。启用SDN后，可以通过网络状态向应用程序通知详细路由和流量负载信息，这有助于有效地为应用级广播选择覆盖网络转发节点。

通过区块链技术引入了三个主要的数据处理任务：1) 中间矿工的交易处理协调；2) 交易处理监控的会话；3) 交易数据到区块链的分布式写入[15]。在所有节点收到完整消息后，矿工可以收到奖励，这称为工作证明，表明每个参与者将验证结果发送到区块链。生成的块在构建分布式分类账的过程中连接到现有的区块链，首先生成此块的主机有责任将块广播到必须将该块存储在网络中的其他主机。但是，在大多数情况下，单播用于发送消息，因为Internet路由器上没有启用广播，或者默认情况下使用正在运行的网络协议TCP / IP进行切换。单播消息导致许多相同的数据包被重复传输，这可能会导致网络拥塞。

针对以上问题，本文提出了一种区块链自适应广播路由新方法，该方法从数据库验证的概念出发，将区块链作为分布式AAA模块在Internet上的矿工主机进行模拟。针对每个矿工主机的加密信息，提出一种应用层广播方法，用于分析加密信息在消息中如何传播到共享网络池中的所有主机，构造广播树作为覆盖网络拓扑，以最小的延迟提高信息验证能力，包括通过适当的传输路径选择来限制传输和计算延迟。本文将区块链的比特币应用的概念扩展到一种新的分布式虚拟机AAA系统结构。

1 区块链广播数学模型

根据AAA体系结构，将块或事务引入虚拟机(VM)中初始化的VNFS，网络拓扑由VM初始化，块的信息，例如用户标识、身份验证、授权和委托，使用公钥密码进行数字签名。使用广播机制在整个网络拓扑中传播密码学，每个收件人可以使用私钥验证事务，公开密钥用于认证和识别。广播消息可能引起传播延迟，总延迟被假定为沿着路径的传输和处理时间的组合。

广播是一种自动通信技术，用于所有矿工主机始终如一地验证与区块链应用程序相关的重要数据，如事务和分类账。然而，广播环境的保密性和有效性应予以考虑，维护分散的功能验证和性能是NP问题。该问题可以用广播树模型抽象地构造和建模，该模型具有资源分配和路由分配问题。

本文提出了一种广播方案，用于分析区块链所采用的加密信息如何将消息传播到Internet上的每个节点。网络拓扑可以由广播树的成本来构造，从覆盖网络的角度以最小延迟(包括传输和处理延迟)来改进信息验证能力。

xp和ybl表示决策变量，对于块b的目的地d，如果路径p∈Pbd被选中，则xp为1，否则为0，其中Pbd表示块b的目的地d的候选路径集合d∈Db，Db表示块b的目的地集合。如果块b采用链路l，则ybl为1，否则为0。目标函数为：

(1)

式中：αl表示链路上的传输成本，βl表示链路上的处理成本，γbl表示对于块b链路l∈L上的惩罚成本，L表示覆盖网络中的链路集{1,2,…,l}，ybl受制于：每个块b被选择为采用链路l(等于1)或不采用链路l(等于0)，对于∀b∈B,l∈L，则有：

B表示所有需要向矿工主机广播的块{1,2,…,b}，对于每个块b，采用的链路数应大于到最远节点的跳跃时间和目标节点的数量，对于∀b∈B，则有：

(3)

式中：hb表示用于发送块b到最远目标节点的最小跳数，Db表示块b的目的地集合。对于每个块b，每个目标节点的接入链路数应等于或小于1，对于∀b∈B，则有：

式中：Idb表示目标节点的传入连接，对于每个块b，根节点的接入链路数应为0，对于∀b∈B，则有：

式中：Irp表示根节点的传入连接，对于广播到目的地d的每个块b，只采用一条路径，对于∀b∈B,d∈Db，有：

式中：Pbd表示块b的目的地d的候选路径集合d∈Db，Db表示块b的目的地集合。对于广播到目的地d的每个块b，可以采用许多路径(如果选择采用路径p，则决策变量等于1)或不采用路径p，则决策变量等于0，如下所示：

式(7)的约束条件为：∀b∈B,p∈Pbd,d∈Db，对于广播到目的地d的每个块b，如果采用路径p，则路径p上的所有链路应设置为1，对于∀b∈B,l∈L,d∈Db，则有：

式中：δpl表示指示函数，如果链路l在路径p上，则为1，否则为0，对于每个块b广播到所有目的节点，如果已采用链路l，则采用的总次数l应小于目的节点数，对于∀b∈B,l∈L，则有：

为了找到块b的惩罚成本，将链接的惩罚(如果在块b-1中被采用)和块b-1的惩罚成本线性组合，对于∀b∈B,l∈L，有：

对于广播策略的中继转发选择通过一个实例进行说明，以包含3个节点的网络进行举例，如图1所示。对于网络中广播中继转发一般是以减少能耗为目的的，但同时会参考节点位置分布和所处环境进行选择。本次实例忽略参数变化，重点研究最小传输能耗与位置分布的关系，图1中网络中的3个节点都具有全向天线，D12、D13、D23分别代表节点1和2之间的距离、节点1和3之间的距离、节点2和3之间的距离。

图1 包含3个节点的网络

对于图1中网络，节点1有两个广播再转发策略：(1) 直接向节点2和3进行消息广播，此时能耗为E；(2) 通过中继节点2向节点3广播数据包，此时能耗为E′=E12+E23。根据文献[16]无线广播算法中概率模型与能耗模型的计算表达式，当E>E′时，第2种广播策略能耗更小，当E

通过文献[16]中对不同位置的节点的能耗分析，可以得出：在网络拓扑结构中，广播策略中使得能耗最小的路径选择，与节点位置相关，因为位置不同，使得有时通过中继转发消耗的能量小，有时直接传输信息消耗的能量小。本文对于广播策略中路径设计和优化过程是将广播模型作为一个最小生成树问题求解本文目标函数的最小成本，具体过程在第2节中给出。

2 路由路径设计和优化链路分配

为了找到本文目标函数的最小成本，将本文模型看作为一个最小生成树(Minimum Spanning Tree, MST)问题。如果图形具有n个顶点，则每个树具有n-1个边；最小化总边缘权重。图2显示了连接的无向加权图，应用MST算法后，可以找到该图的MST。

图2 无向加权图网络拓扑

图3显示了连接图中所有节点的最小总边缘权重生成树。

图3 最小生成树

在本文数学模型中，链路上的最大聚合延迟是沿树的源节点到目的节点之间的传输延迟和进程延迟的组合，但是，应考虑广播环境的机密性和有效性。通过在使用链路后添加惩罚，解决方案将避免广播选择相同的链路，为每个广播块提供随机拓扑。

(a) 第一个广播块的MST (b) 添加重复惩罚

(c) 随机路径 (d) 随机路径图4 每个广播块的MST

3 实 验

根据第2节中所提公式，将每个块广播视为单独的MST问题，每条链路上的权重是传输成本、处理成本和重用链路的惩罚成本的组合。本文实验使用Prim算法来解决随后的块广播中的每个单独的MST问题，并获得作为实验结果的总目标值。本文实验硬件环境是笔记本电脑，具有Windows 7系统，4 GB运行内存，500 GB磁盘内存，实验软件环境是MATLAB 2013a。实验中广播树的构造如图5所示。

图5 构造广播树流程

当网络链路处于空闲状态时，广播树路由使用最短路径进行路由，当网络链路处于繁忙状态时，使用多径路由对网络压力进行分担，从前k条最少跳数的备用路径中随机分配路径进行广播。

在本文中，进行了几个实验来验证提出的模型，并比较不同情况下的结果。为了比较实验之间的差异，将固定值分配给模型中的某些给定参数，表1显示了实验中使用的给定参数的属性。通过将随机数分别乘以传输权重和计算权重，随机分配每个链路的传输成本和每个节点的计算成本。如果在以下实验中未用作独立变量，表1中指定的值是每个参数的默认值。

表1 实验参数

首先对节点数量和模型的目标值之间的关系进行实验。在现实使用中，节点的数量可以被认为是系统的规模。拥有更大规模系统的运营商将拥有比在小型系统中运营的运营商更多的节点。为了进行实验，在每个测试中保持每个参数的值相同。这种情况首先将节点数调整为10, 20,…, 90，结果如图6所示。

图6 不同节点数的目标值

图6显示了当节点数增加时，目标值随之增加的趋势，这是因为更大规模的系统意味着操作员必须花费更多来操作整个系统。

然后对不同核心比率时成本变化趋势进行实验验证。在实验中，所有节点分为两种类型：核心节点和边缘节点，在现实使用中，系统也分为核心和边缘计算节点。核心计算节点具有更强大的计算能力但节点之间的传输成本更高，边缘计算节点功能较弱但传输成本较低。为这两种节点类型分配不同的核心比率，从0.2到0.6(边缘比率分别为0.8到0.4)，结果如图7所示，提供了有关不同分配比率的模型中提到的不同类型成本变化的信息。

图7 不同核心比率的成本分布评估

从图中可以看出，随着核心比率的增加，总成本也会增加，但逐渐达到最大值，传输成本以类似的方式呈现，但最后略有减少。这是因为当核心比率首先增加时，一些节点加入核心节点，从而增加传输成本，但核心比率不断增加，两种节点的传输成本平衡并达到最大值。

当核心比率增加时，计算成本降低并达到最小值，设置为核心节点的边缘节点越多，系统的计算能力就越高，这导致整个系统的计算成本下降。当核心比率增加时，重复成本增加并逐渐达到最大值。这表明当两种类型的节点的比率变得更加平衡时，其重复成本增加，较低的核心比率将导致较低的重复成本。

最后对各种重复惩罚权重时成本的变化进行实验。在现实使用中，重复惩罚权重可以被看作是操作者反复使用链接的紧迫性。图8给出了从0到1分配权重的实验结果。

图8 不同权重值的成本评估

当权重较小时，重复成本增加，但当权重大于0.4时，重复成本逐渐降低。由于惩罚权重的增加，重复成本首先增加，然而在重复成本增加之后，系统将尝试寻找另一路径以实现较低的总成本。当选择不同的路径时，重复成本降低。

4 结 语

为了将SDN和NFV技术适应于分布在边缘和核心云环境中的云基础设施，提出了区块链的资源管理。本文提出一种区块链同步服务的自适应广播算法，广播转发节点在共享网络架构中采用具有各种拓扑的广播和路由策略，以通过较少重用传输链路来最小化处理和传输延迟，分配给AAA服务、块或事务。通过计算实验说明本文方法的可行性和有效性。