一种基于哈希图的移动自组网区块链模型

宫在为 黄建华 顾彬 宁宇豪 张文韬

摘 要：针对移动自组网存在的网络覆盖范围有限、连接不稳定、节点协同时易遭受恶意攻击等问题，结合区块链技术增加数据的安全性与完整性，提出一种基于哈希图的移动自组网区块链模型。首先，提出一种分簇算法，将节点划分为不同的簇，选举簇首统计簇内节点数量，并写入事件中进行传播，以保证共识的顺利进行；其次，对Gossip协议进行优化，提出FS-Gossip（fast spreading Gossip）协议，减少邻居节点选择的盲目性，提高传播效率，增大新入簇节点的检测速度；最后，改进哈希图中复杂的共识计算，并提出一种基于簇首优先的传播机制，在簇内节点应用轻量级共识与传播机制，以加快事件确认速度，降低时延，提升吞吐量。仿真实验结果验证了模型在时延、吞吐量与传播效率方面的优势。

关键词：区块链；MANETs；哈希图；Gossip协议；分簇

中图分类号：TP309   文献标志码：A

文章编号：1001-3695（2023）09-003-0000-00

doi：10.19734/j.issn.1001-3695.2023.01.0020

Blockchain model for mobile Ad hoc networks based on hashgraph

Gong Zaiwei， Huang Jianhua， Gu Bin， Ning Yuhao， Zhang Wentao

（School of Information Science & Engineering， East China University of Science & Technology， Shanghai 200237， China）

Abstract：Aiming at the problems of mobile ad hoc networks， such as limited network coverage， unstable connection， and vulnerability to malicious attacks when nodes cooperate， this paper combined with blockchain technology to increase the security and integrity of data and proposed a blockchain model for mobile Ad hoc networks based on hashgraph. Firstly， this paper designed a clustering algorithm， which divided the nodes into different clusters， selected cluster heads to count the number of nodes in the cluster， and writed them to events for propagation to ensure the smooth progress of consensus.Secondly， it optimized the Gossip protocol， and proposed the FS-Gossip （fast spreading Gossip） protocol， which reduced the blindness of neighbor node selection， improved the propagation efficiency， and increased the detection speed of new cluster nodes.Finally， it improved the complex consensus calculation in hashgraph， and proposed a propagation mechanism based on cluster head priority. The lightweight consensus and propagation mechanism was applied to nodes in the cluster to speed up event confirmation， reduce delay， and improve throughput. The simulation results verify the advantages of the model in terms of delay， throughput and propagation efficiency.

Key words：blockchain; MANETs; hashgraph; Gossip protocol; clustering

0 引言

移動自组网（mobile Ad hoc networks，MANETs）是由一群移动节点自发组成无线网络的技术［1］，无须基站等固定的基础设施，成网快速，易于搭建，具有很强的灵活性，适用于基础设施被摧毁的紧急情况，或无法建设基础设施的临时场景，如军事、抢险救援、偏远野外使用等。移动自组网中，每个节点地位平等，既可成为消息的发送方、接收终端，也具备路由器的功能。当消息接收方节点超出通信覆盖范围，即无法实现直接通信时，借助网络中其他节点的转发传递，多跳通信可将消息送达。

移动自组网中节点的移动性会导致网络传输不稳定，节点之间进行协作时易遭受窃听、欺骗等安全攻击［2］。自2008年比特币［3］诞生以来，区块链技术走入人们的视野，并获得广泛关注。它是一种综合了分布式系统、网络技术、密码学、博弈论等学科的新兴技术模式，将账本数据分布式存储在全网节点上，并设计共识机制维护账本一致，实现了没有中心化第三方的去信任结构，具有去中心化、可溯源、不可窜改的特点，可以用来解决分布式系统中的数据安全问题。一些学者探讨了移动自组网环境中应用区块链的可能性，文献［4］提出了一个基于区块链的组密钥分发方案以解决无人机自组织网络面临的安全问题。为了减轻网络攻击并增强基于NDN的移动自组网的网络层信任，文献［5］提出了一种基于区块链的系统架构，可以有效发现中毒分发内容并检测内部攻击者。在移动自组网中，当网络受节点移动性的影响分裂为多个分区时，多个分区独立共识会导致区块链出现分叉。为消除分叉，网络合并后需要删除较短的分支链以保留最长链，导致会丢失先前在独立网络中生成的部分数据。2015年，Lewenberg等人［6］通过将通常的区块链替换为有向无环图（directed acyclic graph，DAG），提出了一种对区块链拆分和合并具有鲁棒性的结构，允许任何区块都可以有多个父区块，从而可以使区块链集成因分叉未集成到主链中的区块交易。文献［7］将MANETs中复杂的节点流动问题抽象为网络分裂与网络合并两种情况。网络发生分裂时会形成多个分区，为了保证区块链的可用性，分区内节点需继续进行共识，且挖矿产生区块的速率要与新的网络规模相适应。网络发生合并时，首先需同步来自其他网络分区的区块，然后发起一个合并交易，并由此继续挖矿，产生新的区块。文献［8］通过有向无环图来解决网络移动性引发的分区问题，设计了区块图（blockgraph）结构来适应网络拓扑的变化，每个网络分区可以独立共识以延伸本地区块链，发生网络合并时，通过产生合并块指向之前分区的端块，以适配分区产生的分叉，最终构成区块图结构区块链。

文献［9］提出的哈希图（Hashgraph）是一种用于联盟链或私有链的共识模型，共识环境为异步网络，与移动自组网环境相符。在哈希图中，无须进行挖矿与leader选举，依靠流言协议传播新产生的事件，用虚拟投票代替真实投票，节省了网络开销。文献［10］在此基础上进行改进，提出了Teegraph。通过可信执行环境（TEE）保障了自父原则的正确运行，可以抵御双花攻击，同时对区块设置了传播终止条件，解决哈希图空区块传播造成的存储浪费的问题。虽然哈希图为MANETs环境中应用区块链提供了一种可行的解决方案，但也存在一些问题。首先，移动自组网节点的频繁移动会引发网络拓扑动态变化，而哈希图节点间地位平等，以全网共识为主，网络发生分区时，节点无法得知分区内节点的数目，阻碍了分区内共识的进行；其次，哈希图采用Gossip协议传递事件消息，对邻居节点的选择具有随机性，影响了通信效果，并且不能迅速检测出信息量较多的新入簇节点；最后，移动自组网节点资源有限，电池能量比较珍贵，而哈希图共识计算复杂，步骤多，时延较高，会消耗较多的设备资源。

本文对以上不足进行改进，提出一种基于哈希图的移动自组网区块链模型。该模型首先将无秩序的移动节点划分成簇，并选举簇首，以分层结构代替平面结构，减少节点移动带来的控制开销，并由簇首负责统计簇内节点数量，写入事件中进行传播，解决了缺少关键参数无法进行簇内共识的问题，提高了网络管理能力；其次，对Gossip协议的不足进行改进，提出FS-Gossip（fast spreading Gossip）协议，以增大有效信息交换的概率，减少通信资源浪费；最后，对复杂的哈希图共识进行改进，简化了共识流程，并提出一种事件传播机制，明确了事件的传播方向，提高事件扩散的速度，降低时延。

本文的主要贡献如下：a） 提出一种基于权值的分簇算法，并将簇首选举的权值写入事件中，代替节点间互相交换权值的方法，减少了通信开销;b） 针对原始Gossip协议传播效率较低的问题，提出一种快速FS-Gossip协议，减少邻居节点选择的盲目性，提高新入簇节点的检测速度;c） 提出一种简化的哈希图共识机制，降低了事件确认的时延，提升区块链的性能，同时提出一种基于簇首优先原则的传播机制，加快事件的传播速度。

1 相关工作

1.1 分区共识

区块链最核心的部分是共识层，共识层应用共识算法实现全网节点数据的一致性，共识算法决定了区块链的性能与效率。分区（partitioning）将节点划分为不同分区，分而治之，并行共识，是一种提高区块链性能和扩展性的有效方法［11］，同时分区共识也与移动自组网的分簇共识相适应。Elastico［12］首先提出了区块链分区的设计，节点运行PoW随机进行分区，分区内共识使用PBFT，然而分区时挖矿的难度不好控制。OmniLedger［13］采用RandHound方案产生无偏随机数，保证了分区的随机性，却可能导致单一分区内节点数量过少，降低区块链安全性。文献［14］提出一种基于双链模型的分区共识协议，节点先进行地址随机分区，交押金成为权益人，所拥有的权益再按份额随机分区，避免分区内权益较大的节点垄断出块权，提升了权益分区的安全性。以上分区方法可以提前设计，属于主动分区方法，网络环境为部分同步，不同分区间同步数据延时较低。部分同步网络模型对消息的到达时间作出假设，要求消息传播有确定的时延上限，一旦网络分裂，共识可能终止，抗攻击性较差。而移动自组网的节点均处于不可预测的移动状态中，发生网络分裂后节点将依据地理位置被动进行分区，并在分区内继续进行共识，不同分区间的区块延时受诸多因素影响，消息传输没有确定的时延上限，允许异步到达，情况更加复杂。

1.2 改进Gossip协议

Gossip协议（又称流言传播协议）具有简单高效的特点，以及很好的可扩展性与鲁棒性，常用于大规模点对点网络的数据分发与传播，然而原始Gossip协议在具体应用中可能引起冗余与延时，许多学者对Gossip协议进行研究，提出不少改进方案。文獻［15］提出一种基于 Gossip 的先推后拉的快速数据分发方法，主动推送和被动请求的切换以当前网络中有效链路的概率阈值为分界点，减少了分发冗余量与带宽浪费。文献［16］提出一种改进的节点选择算法 MR-Gossip（most reliable Gossip），结合模糊理论提出基于可靠性的节点选择策略，提高搜索效率。文献［17］提出基于改进Gossip协议的数据同步方法。运用环算法选举领导者，提高数据同步效率，减少数据同步对系统整体性能的影响。文献［18］提出一种树型结构的传播路由模型，加快传播速度，降低收敛的时间，减少冗余。文献［19］提出极化的Gossip协议，设置两种Gossip转发概率，传播方向正确时加大扩散的概率，反之使用衰减概率。文献［20］提出基于Gossip协议的信任收集共识算法，节点通过评估邻近节点的信息度选择通信节点，消息在通信过程中收集信任值，超过阈值，消息达成共识。目前改进方案大多应用于同步网络，主要筛选信息度较高的邻居节点进行通信，而在移动自组网环境中，节点在不同分簇间移动，新入簇节点会携带其他分簇的信息，为保证数据的安全性与一致性，这些新信息需迅速在该簇节点中同步并达成共识，所以除信息度这一因素，改进Gossip协议还需考虑节点的入簇时间，以加快新入簇节点的检测速度。

2 基于哈希图的移动自组网区块链模型

2.1 模型结构

移动自组网逻辑上分为平面式和层次式两种结构。平面式结构的特点是所有节点地位平等，网络健壮性较强，但当网络规模增大时，用于发现路由和位置管理的控制报文也随之迅速增加，网络效率显著降低，存在可扩展性问题。层次结构将网络节点划分到不同的簇中，每个簇选择一个簇首负责簇的管理，可以有效解决移动自组网的可扩展性问题，因此本文针对分簇结构研究移动自组网区块链模型。图1为本文采用的移动自组网分簇结构，相较于完全的分布式结构，分簇结构可以节省拓扑变化造成的控制开销，更有利于Ad hoc网络的扩展和管理，提高网络的性能与实用性。通过分簇算法，将网络中所有节点依据地理位置聚合成不同的簇。分簇后，有簇首、簇成员、网关三种角色，分别发挥不同的传播作用，其中网关节点用于连接相邻分簇，在不同分簇间传递信息实现跨簇通信。

形成簇結构后，每个节点在本地存储一张全网的哈希图，通过FS-Gossip协议选择信息收益较大的邻居节点，进行通信，更新并维护本地的哈希图。节点产生或接收新事件，将按照一种传播机制进行事件传播，提高扩散的速度。

节点移动会导致网络不断发生分裂与合并，可能使某一分区内节点数量较少，这时如果恶意节点发动女巫攻击，伪造多个身份控制共识过程，会严重影响系统的安全性，所以需对所有加入网络的节点进行身份认证，本文假设模型应用场景为联盟链或私有链。

2.2 哈希图

本文基于哈希图构建面向移动自组网的区块链模型。2016年提出的哈希图是一种基于Gossip协议的DAG共识算法，网络中每个节点都在本地保存一张哈希图，节点间通过Gossip协议更新本地副本，延续哈希图。哈希图中没有区块，由许多事件（event）组成，每个事件代表发生了一次Gossip通信，如图2所示，节点A与D通信，接收了节点D当前哈希图副本中的全部事件，更新结束时，节点A产生一个新事件，指向自身的上一个事件与节点D的当前事件，以新事件记录本次的Gossip活动。哈希图保存了节点间发生Gossip的历史记录，通过哈希图可以清楚地看到事件传播的路径，即节点于何时、何处更新了本地的副本，事件在不断地传播中被其他节点见证并达成共识。

哈希图用虚拟投票代替实际投票，具有节省通信开销的优点，图中完整保存了所有的交易信息，不会丢失交易。哈希图完全异步，没有leader，也无须工作量证明，因此本文将哈希图用于网络动态变化，不断发生分裂与合并的MANETs环境。哈希图事件结构如图3所示，交易信息一项可以为空，当节点暂无交易，又收到其他节点的新事件，为了进行存储与投票，就会创建一个空事件。

哈希图通常应用于共识成员固定的联盟链中，并假设成员节点的数量已知，进而判断是否达到2/3的共识门槛。然而，在拓扑动态变化的MANETs环境中，全网节点被划分为多个簇，簇成员形成共识组进行共识以继续协同工作，节点移动性会导致节点不断加入和离开簇，成员的动态变化使得节点无法及时获知簇内节点数量，给簇内共识带来挑战。此外，哈希图共识流程长，计算复杂，时延较高，会消耗较多的设备资源。针对这些问题，本文对分簇算法和Gossip协议进行改进，使得哈希图可以更好地适配移动自组网区块链的共识。本文设计了两种特殊的事件结构，分别为选举事件与簇首见证事件，选举事件用于簇首选举，簇首见证事件用于传播簇内节点数量这一参数，将在后文介绍。

2.3 分簇算法

分簇是一种常见的应用于移动自组网的节点管理方法，模型将无规则无秩序的移动自组网节点划分成簇，分而治之，与未分簇相比，节省了动态拓扑带来的全局控制开销，更有利于事件的传播，同时提高了网络的可扩展性。分簇时，节点依据地理位置，获取邻居列表，协同任务的节点组成一个簇，簇内任意节点间依靠单跳或多跳通信，可将消息传达。超出分簇通信范围的节点，可以加入其他分簇，或成为未分簇的自由节点。

分簇算法通常需选举簇首对分簇进行管理，现有算法大多将簇首选举所参考的数据值进行全网广播，即网络中所有节点广播自己的数据，同时接收其他节点的数据，进行比较，按照算法定义的规则选出合适的簇首节点，该方法通信复杂度较高，占用较多的通信资源，可能导致区块链在簇首选举期间不可用。本文利用哈希图传播事件分布存储的特点，对事件结构进行改进，借用事件的传播散发选举数据，将通信开销由O（n2）降为O（n），同时保证区块链的可用性。

本文簇首选举算法设计如下：首先，所有节点进行初始化，建立自己的邻居视图，并获得一些自身的性能数据。然后，节点综合连接度、跳数和、活跃度、相对移动性、电池能量五个因素，代入权值公式算出能力值。本文通过设计一种特殊的事件结构，借助事件传播捎带能力值数据，减少节点间通过消息交换能力值数据造成的通信开销。簇首选举期的事件结构如图4所示，其中包含时间戳、交易、自父事件的哈希值、其他父事件的哈希值以及能力值五个字段，增加的能力值字段用于选举簇首。

通过在事件中增加能力值（capacity value）字段，节点存储新事件的同时也获得了其他节点的能力值数据。选举事件可以附带交易信息，在未选出簇首时，节点仍能发布交易，不影响区块链功能的正常运行，待簇首选举完成后对含有交易的事件进行共识确认。当簇内所有节点均发出了选举事件，哈希图中能力值最大的节点成为簇首。最后，所有节点确认自己的身份，簇首整理出当前簇成员列表，在同步哈希图时，生成具有特殊结构的簇首见证事件，将簇内节点数量与成员列表传播给其他节点，保证共识的顺利进行。 分簇算法的流程如图5所示。

本文将移动自组网的拓扑结构抽象成一张简单的有向图，记作G=（V，E），这里V表示网络中所有节点组成的集合，E为边集，表示两个节点间是否可以直接通信。下面对使用的参数进行定义：

a）节点ID。移动自组网中每个节点具有唯一的标识，节点i的ID记为IDi。

b）邻居节点集合。节点一跳邻居视图中的所有节点构成的集合，记为N（v）。

c）邻居节点变化率。存在两个时刻t1，t2，得到两个时刻总共出现的邻居节点数目为|N（v）t1∪N（v）t2|，两个时刻重合的邻居节点数目为|N（v）t1∩N（v）t2|，则

NCR（v）=|N（v）t1∩N（v）t2||N（v）t1∪N（v）t2|（1）

d）连接度。节点拥有邻居节点的数量，记为Cd（connectivity degree），Cd=|N（v）|。

e）可通信节点列表。由节点在一跳或多跳通信范围内可到达的节点组成，表中记录节点ID与对应的跳数，节点通过周期性与邻居节点交换此表来进行更新，记为ntable。

f）跳数和。节点将可通信节点列表中的跳数进行相加，跳数越少，节点的通信便利度越高，记为Hs（hop sum）。

設可通信节点列表中共有n个节点，即

Hs=∑ni=1ntable.hopi（2）

g）活跃度。节点在上一个epoch中创建事件的频率，记为Ef（event frequency）。

h）相对移动性。节点相较于附近节点，移动性的强弱，记为Rm（relative mobility）。

i）电池能量。表示节点剩余的电池能量的多少，记为Bp（battery power）。

考虑到移动节点运算能力有限，因此简化了相对移动性的计算，规定其近似等于邻居节点变化率的倒数，即

Rm=1NCR（v）（3）

NCR（v）的值越大，节点的邻居变化越小，节点越稳定，相对移动性越弱。

能力值计算公式为

Capacity（v）=αCd+βHs+γEf+δ1Rm+εBp（4）

即

Capacity（v）=αCd+βHs+γEf+δNCR（v）+εBp（5）

其中：α+β+γ+δ + ε=1。

可根据系统运行状态调整每项的权重，改变簇首选举的侧重点，以获得更高的系统性能。

分簇成功后产生了簇首、簇成员和网关三种角色。簇首负责统计每一轮次中簇成员的数量，收集并管理本簇及其他簇产生的新事件，并依据传播机制运行Gossip算法；簇成员承担中间路由的功能，在传播过程中检查事件，存储簇内一致的分布式账本；网关是指能与两个或多个簇直接通信的节点，负责簇间事件的传播，连接不同簇，提高了区块的扩散效率。

分簇完成后，节点维护邻居列表，发送的Hello消息格式为

Helloi = （IDi | Statusi | hopi | eventi | tlivei | timestamp | ski（hash））

其中：字段IDi表示节点i的唯一标识ID；Statusi表示节点i的状态，如果节点未分簇，值为0，如果节点是网关节点，值为1，如果节点是簇成员节点，值为分簇ID（clusterID），本文设置分簇ID为簇首ID； hopi表示节点i距离簇首的跳数；eventi表示节点i拥有事件的数量；tlivei表示节点i从该簇诞生起，在簇内生存的时间，一旦节点离开该簇，tlivei清空为零；timestamp表示节点i发出消息的时间戳；ski（hash）表示节点i将整条消息取哈希值，并用私钥签名，防止其他节点伪造消息，提高安全性。

为了保证系统的安全性，簇首需要定期更换。然而，频繁地分簇会引起网络动荡，使区块链的性能下降。因此，本文模型采用划分任期、簇首失效时发起替换的机制，规定簇首的任期为一个纪元（epoch），若纪元未结束，而簇首出现故障无法工作，或在运动中移出该簇，则触发簇首更换算法，节点产生选举事件，选出新的簇首。如果当前纪元已结束，该簇所有节点更新自身性能数据，重新计算能力值并创建簇首选举事件，选出新的簇首，开启下一个纪元。簇首更换算法如算法1所示。

算法1 簇首更换算法

输入：出现故障的当前簇首节点。

输出：新的簇首节点。

while （node CurrentCH fails） do // 节点CurrentCH表示当前簇首节点

if （current epoch ends = = true） // 判断当前epoch是否结束

Call clustering algorithm ; /* 如果当前epoch结束，调用分簇算法，重新分簇 */

else

create election event ; // 创建簇首选举事件

exchange election events and grow local Hashgraph ; /* 交换选举事件，并发展哈希图*/

check the max number of capacity value in local Hashgraph ; /* 在本地哈希图副本中查找最大的能力值 */

node N = getNodeID （max number） ; // 获得该节点的ID

node N becomes NewCH ；// 新簇首选举结束

end if

end while

2.4 FS- Gossip协议

本文针对移动自组网的需求，对Gossip协议进行了改进。Gossip协议于1978年被提出，是一种简单高效的数据分发方法，具有良好的可扩展性与鲁棒性，在点对点网络中发挥关键的作用。当一个节点需要同步消息时，它不与服务器进行连接，而是随机从对等的邻居节点中选择节点转发消息，其他节点收到消息后同理，该过程类似于流行病或谣言的传播。常见的Gossip协议交换信息有三种方法：

a） 基于推（push）的方法，节点A将信息发送给节点B，节点B根据收到的信息进行更新；

b） 基于拉（pull）的方法，节点A向节点B主动请求，节点B将信息发给节点A，A进行更新；

c） 基于推/拉（push/pull）的方法，A与B相互发送信息给对方。

哈希图中采用了基于拉的方法，即节点随机请求一个邻居节点，该邻居节点将存储的所有事件发送给原节点，原节点更新本地的哈希图并创建一个新事件，代表了此次Gossip过程。

然而，Gossip协议具有随机性与盲目性，进行邻居的选择时，不同节点的概率是相等的，容易造成延时与冗余，浪费通信资源，使性能下降，无法满足移动自组网的需求。为了更快速地传播事件，提高复制速度，节点应增大优质邻居节点的选择概率，进行有效的信息互换，减少无效的Gossip次数，避免冗余的通信量与资源浪费，本文提出改进的Gossip协议，即FS-Gossip（fast spreading Gossip）。

在FS-Gossip协议中，假设节点Nodei共有m个邻居，邻居节点列表为{n1，n2，…，nm}，从本地哈希图事件的时间戳，可得节点Nodei上一次与邻居节点nj （1≤j≤m）发生Gossip的时间为t0（i，j），当前时间为t。节点Nodei周期性发送Hello消息，维护邻居列表，并通过邻居节点回复的Hello消息中的参数值计算概率，选择概率较高的邻居节点进行拉，实现Gossip信息收益最大化。

设k为收益预估值，k计算公式如下：

k=μ |eventi－eventj|+λ（t－t0（i，j））（6）

其中：0≤μ≤1，0≤λ≤1·μ、λ为归一化调节因子。当节点处于同一分簇时，节点拥有事件数量的差值越大，距离上一次Gossip同步过去的时间越久，预估发生Gossip后的信息收益越大。

当一节点离开它所在簇，加入Nodei节点所在簇，成为Nodei节点的邻居时，由于该节点可能存储了其他簇的事件，有效信息更多，可知该节点被选中的概率应高于同簇的其他邻居节点，发生Gossip的优先级更高。

将k代入概率p的计算公式：

p=11+e－（φk+ω）  0≤p≤1（7）

其中：φ为调节系数，防止φk值过大，影响公式的效果;ω为判断项，通过将Hello消息中的簇内生存时间字段tlive与设置的阈值相比较，可判断该邻居节点是否处于同簇。若该节点簇内生存时间大于阈值，可推知处于同簇，ω值为0；反之，簇内生存时间小于阈值，可推知该节点为新节点，要么离开其他簇加入此簇，要么是新加入区块链网络的节点，这时，ω取上限值，以提高与之进行Gossip的概率。

ω=0   tlive>bounduppertlive

其中，被判定为同簇节点的阈值bound与簇首上一轮次（round）共识所用时间及事件差异率有关。上一轮所用共识时间越长，阈值越高，簇内生存时间不足一个轮次的新节点将被快速检测出来。事件差异率大，说明新节点信息差较大，阈值也将提高。

哈希图中节点同步事件时，为节省带宽开销，通常不直接发送一张完整的哈希图，而是发送一张节点存储事件表，表中记录了对不同节点分别存储了多少事件，对面节点根据此表，将缺少的事件补给原节点。

设全网共v个节点，节点Nodei与其邻居节点nj发生存储差异的事件数量计算公式如下：

difference（i，j）=∑vr=1|store（i，r）－store（j，r）| （9）

可以得到相比于节点Nodei，事件差异率为

eventrate=difference（i，j）eventi（10）

阈值将依据簇内运行状态与新节点存储情况，进行动态调整，计算如下：

bound=（1+eventrate）tround（11）

2.5 共识算法

哈希图的共识中，每个节点首先产生一个见证事件，随着Gossip的不断进行，当节点存储的副本中能看到超过2/3个上一轮的见证事件时，就产生新一轮的见证事件。达成共识需要经过虚拟投票、统计投票、确定声望三个阶段，结果是一个事件至少经过三轮，才能达成共识，划分轮次计算复杂，消耗了设备资源，且事件确认的时延较高。本文对共识过程进行了简化与改进，设置共识结果有簇内共识与全网共识两种。若一个事件被簇内超过2/3的节点直接或间接地引用，则达成簇内共识；若一个事件被全网超过2/3的节点直接或间接地引用，则达成全网共识。在移动自组网环境中，随着节点的自由移动，网络完全彻底地分裂，没有网关节点时，不同分簇间很难直接通信，导致最终达成全网同步的时间不可预知，故以簇内共识的时延为准，缩短达成共识所需的时间。

确定簇内节点的成员和数量，对簇内共识的达成具有关键作用。如图6所示，本文将簇首发出的见证事件设置为特殊结构，增加了簇内节点数量、簇成员列表两个字段。在每一轮共识中，簇成员节点通过簇首发出的见证事件，获知本轮簇内节点数量与成员列表，从而可以判断是否达到创建见证事件的门槛。簇内节点发生变动共有两种情况：一种由节点数的改变直接显示出来；另一种节点数未变，但簇成员组成发生变化。通过簇首见证事件携带的信息，簇内节点可以及时获知成员情况，进而判断是否达成共识。

本文的快速共识过程包括两个步骤，事件最少经过两轮就能确认。第一步为寻找候选的极佳见证事件（superb witness event），第二步为统计投票，判断是否确定成为极佳见证事件，并划分出达成共识的事件。当任意节点创建第n轮见证事件时，说明该节点已经收到超过分簇节点数2/3的n-1轮的见证事件，在这些上一轮次的事件中，如果存在一条或多条路径，从同一个见证事件起始，连接了其他所有事件，那么這一见证事件就成为极佳见证事件。即存在一个见证事件，在同轮次中，被超过2/3的簇内节点引用过，该事件就达成共识，被该事件引用的所有父事件也达成了共识。共识确认示意图如图7所示。

假如某一时刻的全局哈希图如图7（a）所示，分簇中的节点B创建第三轮B3见证事件时，从图7（b）本地哈希图副本中可以发现D2→A2和D2→B2这两条路径，分簇中节点数目为4，路径中节点的数目超过了2/3的共识门槛，可以得知D2为极佳见证事件，D2所引用的所有第一轮的事件达成了共识。同理，从图7（c）中可以发现，节点C创建C3见证事件时，看到D2被A2、B2、C2均验证过，也能得到D2为极佳见证事件，并划分出共识确认的事件。

如果节点创建第n轮见证事件时，发现本地哈希图副本中，不存在满足条件的n-1轮极佳见证事件，就继续创建新事件，不断地从邻居节点处同步最新的副本，发展哈希图，直到找出极佳见证事件。

3 传播机制

本文设计一种基于簇首优先的传播机制，包括簇内传播与簇间传播两种传播方式。节点收到新的含交易事件后，根据邻居节点Hello消息中的跳数（hop）进行筛选，选择更靠近簇首的邻居节点传播本地副本，通过明确事件的传播方向，确保簇首优先收到包含交易事件并进行检查，以加快事件的传播速度与新入簇节点的发现速度，降低传播冗余。

3.1 簇内传播机制

事件的簇内传播，总体思路为簇成员节点收到含交易的非空事件后，先检查本地哈希图副本中是否有簇首发出的事件引用过它，如没有引用则判定为新交易事件，则先沿着跳数减少的方向传播事件，优先让簇首更新本地哈希副本，保存该事件，在簇首引用后，再沿着跳数增加的方向，传播给簇内其他节点。簇内传播过程如图8所示。

图8（a）中簇内一个成员节点产生了一个新的含交易事件，标记为单词event的首字母“e”，该节点随即将新事件以Gossip的方式传播给邻居节点，邻居节点收到事件后，检查本地哈希图副本，发现簇首未直接或间接引用过该事件，则调用簇首优先（CH-First）算法，沿着跳数减少趋近簇首的传播路径，筛选邻居节点进行传播，簇首優先算法的执行过程如算法2所示。其他节点收到事件后同理，如图8（b）所示。簇首收到事件，检查格式、私钥签名无误后，就传播给邻居节点，如图8（c）所示。成员节点收到含有簇首引用事件的哈希图，则按照跳数增加的方向进行传播，最后，簇内全部节点都会收到该事件。通过明确事件传播方向，可以建立有效的传播秩序，避免传播过程的混乱现象，减少通信冗余。

簇首优先算法的执行过程见算法2。

算法2 簇首优先算法

输入：邻居节点列表NeighborList。

输出：距离簇首更近的邻居节点。

while （receive non-empty event with no CH event reference） do /* 收到的非空事件没有簇首的引用 */

find hop data in NeighborList ; /* 在邻居列表中查找邻居节点距离簇首的跳数 */

hop ← min（hop）; // 找到最小的跳数

node N = getNodeID （hop） ; // 获得该邻居节点的ID

gossip to node N；// 将更新事件发给该邻居节点，CH-First算法结束

end while

3.2 簇间传播机制

通过判断有无网关节点，可将事件的簇间传播划分为两种情况。当簇间存在网关节点时，簇间传播总体思路为依靠网关节点，实现事件的跨簇传递。如果一个节点同时处于两个或多个簇首的通信范围内，那么该节点不属于任何一个分簇，成为独立的网关节点。如果两个分簇距离较近，边缘节点之间可以直接通信，那么就设定ID较小的边缘节点成为网关节点。不同分簇之间可能会由网关节点相连，也可能彼此孤立没有连接。如果分簇间存在网关节点，那么由网关节点作为沟通的桥梁，与不同簇的节点进行Gossip通信，实现事件的跨簇传播。

网关节点位于不同簇首之间时，借助网关节点的事件簇间传播过程如图9所示。图9（a）中簇C2的簇首收到簇内的事件后，首先判断邻居列表中是否包含网关节点，如果不包含，则不涉及借助网关节点的簇间传播；如果包含，再判断该事件是否曾经发送给网关节点。如果已发送过，则不再发送；如果从未发送过，则优先发给网关节点，如图9（b）所示。网关节点收到簇C2的更新事件，立刻传播给邻居列表中的其他簇的节点，如图9（c）所示，将其传播给簇C1的簇首。簇C1的簇首再选择邻居节点进行通信，如图9（d）所示，将其他簇更新的哈希图在本簇中传播开来，最后，簇C1、C2中所有的节点都拥有了更新的事件。

边缘节点成为网关节点时，簇间传播过程如图10所示。图10（a）中两个分簇逐渐靠近，边缘节点取得联系。根据设定的规则，ID较小的边缘节点成为网关节点，如图10（b）所示，簇C2的边缘节点将本簇的新事件同步至网关节点。网关节点再将事件传播至其他分簇的节点，如图10（c）所示。簇C1的簇首节点将收到的事件在本簇中传播开来，如图10（d）所示，最终实现了簇C1、C2哈希图的同步。

当簇间不存在网关节点，无法借助网关节点直接进行事件同步时，簇间传播的总体思路为依靠移动入簇的新节点，实现分簇间事件的同步。由于移动，节点可能离开原簇，加入新簇，在此过程中，节点可将自身存储的原簇事件同步至新簇，同时，接收并存储新簇的事件，这一过程实现了不同簇间事件的传播。无网关节点的事件簇间传播过程如图11所示。

图11（a）中簇C2的簇内事件同步结束后，簇C2的某一成员节点由于移动，脱离了簇C2的通信范围，成为未分簇节点，如图11（b）所示。该节点移动至簇C1的通信范围内，加入了簇C1，并建立了新的邻居视图。根据FS-Gossip算法，该节点被邻居节点以较大概率选中，发生Gossip同步，簇C1节点收到新事件后，对本地哈希图进行检查，发现没有本簇簇首的引用事件，则调用CH-First算法，沿着趋近簇首的传播路径，优先传播给簇首，如图11（c）所示。簇C1的簇首再选择邻居节点进行通信，将其他簇的事件在本簇中传播开来，最后，簇C1依靠簇C2移动过来的节点，成功同步了簇C2的哈希图，结果如图11（d）所示。

4 安全性分析

本章讨论模型的安全性，并具体分析模型如何防范联盟链中几种常见的安全攻击。

a）双花攻击。在双花攻击中，恶意节点建立分叉，创建两个新事件，使两个事件引用同一个自父事件，如果两个事件均能通过共识确认，节点就成功发动了双花攻击。在本文共识中，通过选举极佳见证事件并投票，只有被超过2/3个节点检查无误并引用过的事件，才能达成共识。而双花攻击的两个事件，最多只能有一条分叉被超过2/3的节点见证并通过共识，此时另一条分叉因引用节点少于1/3而无法通过共识，或两条分叉均无法达到2/3的共识门槛。两种情况下，恶意节点的双花攻击均无法成功实现。

b）女巫（Sybil）攻击。女巫攻击指恶意节点冒充多个身份，实现数量在分簇中占据优势，从而操纵共识。在本文模型中，为保障数据隐私与安全，假设模型应用场景为联盟链或私有链，节点加入网络需进行注册和身份认证，所有节点的公钥公开已知，身份可以相互验证，一个节点无法通过申请多个公钥冒充多个节点，从而可以防范女巫攻击。

c）拒绝服务（DoS）攻击。在DoS攻击中，攻击者将大量信息发送给弱点节点，使该节点无法将有限的设备资源用于区块链网络，从而影响区块链的性能，弱点节点通常为领导者节点。本文模型中共识算法没有领导者，所有节点共同维护共识的正确进行。即使攻击者攻破某个节点，剩余节点也可以正常维持整个区块链系统，进而有效抵抗DoS攻击。

d）针对领导者的攻击。多出现于能预先确认领导者的PBFT算法。恶意节点通过预知领导者是哪一节点，从而发动攻击，阻碍共识的正常进行。在本文模型中，没有领导者来主导共识。簇首节点仅对共识具有推动作用，一旦失效可以进行替换。同时，根据权值公式中的能力值影响因素，簇首是分簇内性能较高的节点，具有应对攻击的防范能力。通过发布簇首选举事件，验证并比较其他节点能力值的高低来选举簇首，确保了选举的公平性。

5 实验

本章從分簇数量、活跃度、吞吐量、平均共识时延、FS-Gossip协议五个方面对模型的性能进行测试，以此验证模型的可用性。

实验的硬件环境为一台MacBook Air，处理器为八核Apple M1，内存8 GB，软件环境为Eclipse IDE 4.24.0。为模拟多个节点建立分簇拓扑并创建新事件、同步哈希图，实验采用JAVA多线程技术，每个线程代表一个节点，线程与线程之间可以相互通信，以传递参数。

5.1 分簇数量与模型性能的关系

本实验测试不同分簇数量对模型性能的影响，探究当节点总数固定时，划分为多少个簇才能使全网总吞吐量到达最大值。本文对比的区块链模型为Hashgraph与Teegraph。Teegraph模型改进了Hashgraph，引入可信执行环境，节点在此环境下无法发起双花攻击，从而无须多轮次的见证检查双花事件，加速了共识，可应用于移动自组网区块链。实验假设全网共有60个节点，且每个簇的节点数量相同，每个节点每隔400 ms创建一个新事件，最后根据各个分簇的吞吐量值，累计求和得到全网的总吞吐量。如果分簇数量不能整除，就取近似的整数值，仍保证节点总数为60。当分簇数量为15时，每个簇仅有4个节点，是进行拜占庭共识的最少节点数，故当全网节点总数为60时，最大分簇数量为15。分簇数量决定了簇的大小，进而会影响模型的性能。

实验结果如图12所示，本文模型的吞吐量始终高于Hashgraph，平均提高了约32.2%，但略低于Teegraph，仅下降了3.8%。原因在于Teegraph没有设计不同共识组节点的管理机制与Gossip协议的优化方法，主要研究共识层算法，本文引入了分簇节点管理、事件传播管理，且节点未装备可信执行环境，这些都会增加一定的共识开销，但本文算法性能只是略有下降，且解决了Teegraph没有考虑的节点与事件管理问题。实验结果也可以看出，模型存在最佳分簇数，使全网总吞吐量达到最大值，当实验的分簇数量为10个时，全网总吞吐量达到最高值，为每秒140个事件。这一结论可为设计具体应用提供参考。

5.2 活跃度与模型性能

本实验测试节点活跃度对模型性能的影响，设置了多组不同的创建事件频率，记录平均时延，实验结果如图13所示。可以看出，事件创建间隔越长，节点产生新事件频率越低，共识越慢，时延越高，本文提出的确定极佳事件快速共识机制的时延增速慢于Hashgraph，略高于Teegraph。本文通过节点计算能力值选举簇首，而能力值公式中除了电池能量、相对移动性等客观因素外，还考虑了活跃度这一主观因素，能够激励节点提高活跃度，增加创建事件频率，加快共识进程，因此时延性能要明显好于Hashgraph，在考虑节点与事件管理功能的前提下与Teegraph基本相同。

5.3 吞吐量测试

吞吐量是评价系统性能的重要指标之一，体现了单位时间内达成共识确认的事件的多少，吞吐量越大，系统的处理能力越强。本实验测试改进后共识机制的吞吐量，并与Hashgraph、Teegraph进行对比，假设每个节点创建新事件的频率不变，实验结果如图14所示。从图中可以看出，本文共识算法的吞吐量高于Hashgraph，与Teegraph不相上下，原因是本文提出的共识算法在节点不装配可信执行环境的情况下，确保安全性的同时缩短了共识轮次，简化了共识流程，增大有效Gossip的发生概率，提高系统吞吐量。

5.4 共识时延测试

本实验测试改进后共识机制的时延，并与Hashgraph、Teegraph进行对比。共识时延用来评价事件从产生到完成事件确认所经历的时长，一些特殊应用对共识时延要求很高，对交易确认速度比较敏感。共识时延越低，代表交易确认越快，模型越高效。实验结果如图15所示。从图中可以看出，本文共识算法的时延明显低于Hashgraph，仅略高于Teegraph。这是由于Hashgraph共识需经过虚拟投票、统计投票、确定声望三个阶段，事件至少经过三轮才能达成共识，增加了时延；Teegraph因为装入可信执行环境，将共识门槛由2/3降至1/2，不再划分轮次，提升了共识速度。本文共识步骤较为简洁，最快经过两轮就能达成共识，虽然未通过装备可信执行环境来减轻节点负担，且对节点与事件的管理也带来一些性能损耗，但时延相比Teegraph仅略有增加。

5.5 FS-Gossip测试

本文设计事件同步率这一变量，来评价Gossip协议的通信效果。图中横坐标代表全局哈希图中事件的数目，纵坐标事件同步率体现了节点对这些事件的平均存储比例。随着节点扩展哈希图，产生的事件越来越多，全网节点平均存储事件的数目与当前全局哈希图所拥有的事件数目作百分比，就得到事件同步率。实验分别对两种情况进行测试，一种情况为簇内节点间距较小，任一节点均处于其他节点的通信范围内，节点间可以互相通信；另一种情况为簇内节点间距较大，每个节点拥有自身的邻居列表，不相邻的节点传递信息需借助中间节点，并设置了一种拓扑情况进行实验。节点间距较小时，实验结果如图16所示。从图中可以看出，在6个和9个节点两种情况下，产生的事件数相等时，本文提出的FS-Gossip算法更容易选择高信息收益的邻居节点进行通信，平均事件同步率均高于随机Gossip算法。

节点间距较大时，设置了两种拓扑情况进行实验，图17（a）展示了簇内有6个节点时的一种拓扑情况，由于节点间距离较远，节点2只能与节点1、5发生通信，簇内其他节点不在节点2通信范围内，故无法与之直接通信。同理，图17（b）展示了簇内有9个节点时一种可能的拓扑情况。

实验结果如图18所示。从图中可以看出，在6个节点和9个节点两种情况下，本文提出的FS-Gossip算法增加了信息收益大的邻居节点的选择概率，事件同步率均高于随机Gossip算法。

6 结束语

本文提出一种基于哈希图的移动自组网区块链模型，解决了移动自组网环境下，由于网络不断发生分裂与合并，导致事件同步不及时、影响共识的问题。模型首先依据地理位置，对全网节点进行分簇，并选举簇首，设计了特殊的事件结构，由簇首统计并传播簇内节点数量这一影响共识的关键参数，解决了由于节点数量不明确导致簇内共识无法进行的问题；其次，提出FS-Gossip协议，通过在Hello消息中增加字段，计算信息收益，筛选邻居节点，提高了事件同步效率；最后，对哈希图中复杂的共识机制进行改进，将原来的三步共识缩减为两步，在确保安全性不变的同时，提升了共识速度，降低了时延。实验结果表明，本文模型在兼具安全性的同时，提高了吞吐量与事件同步率，降低了时延。

参考文献：

[1]李少谦，兰岚.无线Ad hoc网络技术［J］.中兴通信技术，2002（1）：9-12.（Li Shaoqian，Lan Lan.Wireless Ad hoc network technology［J］.ZTE Communications，2002（1）：9-12.）

［2]宋建华，洪帆，何晓冰.移动Ad hoc网的典型网络攻击与防范［J］.微计算机应用，2007（5）：454-459.（Song Jianhua，Hong Fan，He Xiaobing.Typical network attacks and prevention of mobile Ad hoc networks［J］.Network New Media Technology，2007（5）：454-459.）

［3]Nakamoto S.Bitcoin：a peer-to-peer electronic cash system［EB/OL］.（2008）.https：//bitcoin.org/en/bitcoin-paper.

［4]Li Xinghua，Wang Yunwei，Vijayakumar P，et al.Blockchain-based mutual-healing group key distribution scheme in unmanned aerial vehicles ad-hoc network［J］.IEEE Trans on Vehicular Technology，2019，68（11）：11309-11322.

［5]Lei Kai，Zhang Qichao，Lou Junjun，et al.Securing ICN-based UAV Ad hoc networks with blockchain［J］.IEEE Communications Magazine，2019，57（6）：26-32.

［6]Lewenberg Y，Sompolinsky Y，Zohar A.Inclusive block chain protocols［M］//Bhme R，Okamoto T.Financial cryptography and data security.Berlin：Heidelberg：Springer，2015：528-547.

［7]Laube A，Martin S，Al Agha K.A solution to the split & merge problem for blockchain-based applications in ad hoc networks［C］//Proc of the 8th International Conference on Performance Evaluation and Modeling in Wired and Wireless Networks.Piscataway，NJ：IEEE Press，2019：1-6.

［8]Cordova D，Laube A，Nguyen T M T，et al.Blockgraph：a blockchain for mobile Ad hoc networks［C］//Proc of the 4th Cyber Security in Networking Conference.Piscataway，NJ：IEEE Press，2020：1-8.

［9]Baird L.The swirlds hashgraph consensus algorithm：fair，fast，Byzantine fault tolerance，SWIRLDS-TR-2016-01［R］.［S.l.］：Swirlds，Inc.，2018.

［10]Fu Xiang，Wang Huaimin，Shi Peichang，et al.Teegraph：a blockchain consensus algorithm based on TEE and DAG for data sharing in IoT［J］.Journal of Systems Architecture，2022，122（C）：102344.

［11]劉懿中，刘建伟，张宗洋，等.区块链共识机制研究综述［J］.密码学报，2019，6（4）：395-432.（Liu Yizhong，Liu Jianwei，Zhang Zongyang，et al.Overview of research on blockchain consensus mechanism［J］.Journal of Cryptologic Research，2019，6（4）：395-432.）

［12]Luu L，Narayanan V，Zheng Chaodong，et al.A secure sharding protocol for open blockchains［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security.New York，NY：ACM Press，2016：17-30.

［13]Kokoris-Kogias E，Jovanovic P，Gasser L，et al.Omniledger：a secure，scale-out，decentralized ledger via sharding［C］//Proc of IEEE Symposium on Security and Privacy.San Francisco，CA：IEEE Press，2018：583-598.

［14]黄建华，黄雪茹，季钰翔，等.一种基于双链模型的分区共识协议［J］.计算机应用研究，2021，38（2）：356-362.（Huang Jianhua，Huang Xueru，Ji Yuxiang，et al.A sharding consensus protocol based on dual blockchains［J］.Journal of Application Reserch of Computers，2021，38（2）：356-362.）

［15]马行空.基于Gossip的多源快速数据分发技术研究 ［D］.湖南：国防科技大学，2009.（Ma Xingkong.Research of Gossip-based multisource flash data dissemination technology［D］.Hunan：National University of Defense Technology，2009.）

［16]张娓娓，范训礼，房鼎益.基于模糊理论的P2P流媒体节点选择算法［J］.计算机工程，2009，35（23）：88-90.（Zhang Weiwei，Fan Xunli，Fang Dingyi.A P2P streaming media node selection algorithm based on fuzzy theory［J］.Computer Engineering，2009，35（23）：88-90.）

［17]田振興，代杰.基于改进Gossip协议的数据同步设计［J］.指挥信息系统与技术，2017，8（5）：99-103.（Tian Zhenxing，Dai Jie.Data synchronization design based on improved Gossip protocol［J］.Command Information System and Technology，2017，8（5）：99-103.）

［18]Kan Jia，Zou Lingyi，Liu B，et al.Boost blockchain broadcast propagation with tree routing［M］//Qiu M.Smart blockchain.Cham：Springer，2018：77-85.

［19]Beraldi R.The polarized Gossip protocol for path discovery in MANETs［J］.Ad hoc Networks，2008，6（1）：79-91.

［20]张奇文，王志强，张逸谦.基于Gossip协议的信任收集共识算法研究［J］.计算机科学，2020，47（S1）：391-394.（Zhang Qiwen，Wang Zhiqiang，Zhang Yiqian.Research on trust collection consensus algorithm based on Gossip protocol［J］.Computer Science，2020，47（S1）：391-394.）

［21]徐晶晶，张欣慧，许必宵，等.无线传感器网络分簇算法综述［J］.计算机科学，2017，44（2）：31-37.（Zhang Jingjing，Zhang Xinhui，Xu Bixiao，et al.Overview of clustering algorithms in wireless sensor networks［J］.Computer Science，2017，44（2）：31-37.）

［22]周艺华，贾立圆，贾玉欣，等.基于信誉度的Hashgraph共识算法［J］.计算机应用研究，2021，38（9）：2590-2593，2599.（Zhou Yihua，Jia Liyuan，Jia Yuxin，et al.Hashgraph consensus algorithm based on credit［J］.Application Reserch of Computers，2021，38（9）：2590-2593，2599.）

收稿日期：2023-01-16；

修回日期：2023-03-16

基金项目：国家自然科学基金资助项目（62076094）

作者简介：宫在为（2000-），女，黑龙江密山人，硕士，主要研究方向为区块链；黄建华（1963-），男（通信作者），湖南怀化人，副教授，博士，主要研究方向为计算机网络与信息安全（jhhuang@ecust.edu.cn）；顾彬（1999-），男，上海人，硕士，主要研究方向为区块链；宁宇豪（1998-），男，山西运城人，硕士，主要研究方向为区块链；张文韬（1999-），男，浙江绍兴人，硕士，主要研究方向为区块链．