宮在為 黃建華 顧彬 寧宇豪 張文韜

摘 要：針對(duì)移動(dòng)自組網(wǎng)存在的網(wǎng)絡(luò)覆蓋范圍有限、連接不穩(wěn)定、節(jié)點(diǎn)協(xié)同時(shí)易遭受惡意攻擊等問(wèn)題，結(jié)合區(qū)塊鏈技術(shù)增加數(shù)據(jù)的安全性與完整性，提出一種基于哈希圖的移動(dòng)自組網(wǎng)區(qū)塊鏈模型。首先，提出一種分簇算法，將節(jié)點(diǎn)劃分為不同的簇，選舉簇首統(tǒng)計(jì)簇內(nèi)節(jié)點(diǎn)數(shù)量，并寫(xiě)入事件中進(jìn)行傳播，以保證共識(shí)的順利進(jìn)行；其次，對(duì)Gossip協(xié)議進(jìn)行優(yōu)化，提出FS-Gossip（fast spreading Gossip）協(xié)議，減少鄰居節(jié)點(diǎn)選擇的盲目性，提高傳播效率，增大新入簇節(jié)點(diǎn)的檢測(cè)速度；最后，改進(jìn)哈希圖中復(fù)雜的共識(shí)計(jì)算，并提出一種基于簇首優(yōu)先的傳播機(jī)制，在簇內(nèi)節(jié)點(diǎn)應(yīng)用輕量級(jí)共識(shí)與傳播機(jī)制，以加快事件確認(rèn)速度，降低時(shí)延，提升吞吐量。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了模型在時(shí)延、吞吐量與傳播效率方面的優(yōu)勢(shì)。

關(guān)鍵詞：區(qū)塊鏈；MANETs；哈希圖；Gossip協(xié)議；分簇

中圖分類號(hào)：TP309?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

移動(dòng)自組網(wǎng)（mobile Ad hoc networks，MANETs）是由一群移動(dòng)節(jié)點(diǎn)自發(fā)組成無(wú)線網(wǎng)絡(luò)的技術(shù)［1］，無(wú)須基站等固定的基礎(chǔ)設(shè)施，成網(wǎng)快速，易于搭建，具有很強(qiáng)的靈活性，適用于基礎(chǔ)設(shè)施被摧毀的緊急情況，或無(wú)法建設(shè)基礎(chǔ)設(shè)施的臨時(shí)場(chǎng)景，如軍事、搶險(xiǎn)救援、偏遠(yuǎn)野外使用等。移動(dòng)自組網(wǎng)中，每個(gè)節(jié)點(diǎn)地位平等，既可成為消息的發(fā)送方、接收終端，也具備路由器的功能。當(dāng)消息接收方節(jié)點(diǎn)超出通信覆蓋范圍，即無(wú)法實(shí)現(xiàn)直接通信時(shí)，借助網(wǎng)絡(luò)中其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)傳遞，多跳通信可將消息送達(dá)。

移動(dòng)自組網(wǎng)中節(jié)點(diǎn)的移動(dòng)性會(huì)導(dǎo)致網(wǎng)絡(luò)傳輸不穩(wěn)定，節(jié)點(diǎn)之間進(jìn)行協(xié)作時(shí)易遭受竊聽(tīng)、欺騙等安全攻擊［2］。自2008年比特幣［3］誕生以來(lái)，區(qū)塊鏈技術(shù)走入人們的視野，并獲得廣泛關(guān)注。它是一種綜合了分布式系統(tǒng)、網(wǎng)絡(luò)技術(shù)、密碼學(xué)、博弈論等學(xué)科的新興技術(shù)模式，將賬本數(shù)據(jù)分布式存儲(chǔ)在全網(wǎng)節(jié)點(diǎn)上，并設(shè)計(jì)共識(shí)機(jī)制維護(hù)賬本一致，實(shí)現(xiàn)了沒(méi)有中心化第三方的去信任結(jié)構(gòu)，具有去中心化、可溯源、不可竄改的特點(diǎn)，可以用來(lái)解決分布式系統(tǒng)中的數(shù)據(jù)安全問(wèn)題。一些學(xué)者探討了移動(dòng)自組網(wǎng)環(huán)境中應(yīng)用區(qū)塊鏈的可能性，文獻(xiàn)［4］提出了一個(gè)基于區(qū)塊鏈的組密鑰分發(fā)方案以解決無(wú)人機(jī)自組織網(wǎng)絡(luò)面臨的安全問(wèn)題。為了減輕網(wǎng)絡(luò)攻擊并增強(qiáng)基于NDN的移動(dòng)自組網(wǎng)的網(wǎng)絡(luò)層信任，文獻(xiàn)［5］提出了一種基于區(qū)塊鏈的系統(tǒng)架構(gòu)，可以有效發(fā)現(xiàn)中毒分發(fā)內(nèi)容并檢測(cè)內(nèi)部攻擊者。在移動(dòng)自組網(wǎng)中，當(dāng)網(wǎng)絡(luò)受節(jié)點(diǎn)移動(dòng)性的影響分裂為多個(gè)分區(qū)時(shí)，多個(gè)分區(qū)獨(dú)立共識(shí)會(huì)導(dǎo)致區(qū)塊鏈出現(xiàn)分叉。為消除分叉，網(wǎng)絡(luò)合并后需要?jiǎng)h除較短的分支鏈以保留最長(zhǎng)鏈，導(dǎo)致會(huì)丟失先前在獨(dú)立網(wǎng)絡(luò)中生成的部分?jǐn)?shù)據(jù)。2015年，Lewenberg等人［6］通過(guò)將通常的區(qū)塊鏈替換為有向無(wú)環(huán)圖（directed acyclic graph，DAG），提出了一種對(duì)區(qū)塊鏈拆分和合并具有魯棒性的結(jié)構(gòu)，允許任何區(qū)塊都可以有多個(gè)父區(qū)塊，從而可以使區(qū)塊鏈集成因分叉未集成到主鏈中的區(qū)塊交易。文獻(xiàn)［7］將MANETs中復(fù)雜的節(jié)點(diǎn)流動(dòng)問(wèn)題抽象為網(wǎng)絡(luò)分裂與網(wǎng)絡(luò)合并兩種情況。網(wǎng)絡(luò)發(fā)生分裂時(shí)會(huì)形成多個(gè)分區(qū)，為了保證區(qū)塊鏈的可用性，分區(qū)內(nèi)節(jié)點(diǎn)需繼續(xù)進(jìn)行共識(shí)，且挖礦產(chǎn)生區(qū)塊的速率要與新的網(wǎng)絡(luò)規(guī)模相適應(yīng)。網(wǎng)絡(luò)發(fā)生合并時(shí)，首先需同步來(lái)自其他網(wǎng)絡(luò)分區(qū)的區(qū)塊，然后發(fā)起一個(gè)合并交易，并由此繼續(xù)挖礦，產(chǎn)生新的區(qū)塊。文獻(xiàn)［8］通過(guò)有向無(wú)環(huán)圖來(lái)解決網(wǎng)絡(luò)移動(dòng)性引發(fā)的分區(qū)問(wèn)題，設(shè)計(jì)了區(qū)塊圖（blockgraph）結(jié)構(gòu)來(lái)適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，每個(gè)網(wǎng)絡(luò)分區(qū)可以獨(dú)立共識(shí)以延伸本地區(qū)塊鏈，發(fā)生網(wǎng)絡(luò)合并時(shí)，通過(guò)產(chǎn)生合并塊指向之前分區(qū)的端塊，以適配分區(qū)產(chǎn)生的分叉，最終構(gòu)成區(qū)塊圖結(jié)構(gòu)區(qū)塊鏈。

文獻(xiàn)［9］提出的哈希圖（Hashgraph）是一種用于聯(lián)盟鏈或私有鏈的共識(shí)模型，共識(shí)環(huán)境為異步網(wǎng)絡(luò)，與移動(dòng)自組網(wǎng)環(huán)境相符。在哈希圖中，無(wú)須進(jìn)行挖礦與leader選舉，依靠流言協(xié)議傳播新產(chǎn)生的事件，用虛擬投票代替真實(shí)投票，節(jié)省了網(wǎng)絡(luò)開(kāi)銷(xiāo)。文獻(xiàn)［10］在此基礎(chǔ)上進(jìn)行改進(jìn)，提出了Teegraph。通過(guò)可信執(zhí)行環(huán)境（TEE）保障了自父原則的正確運(yùn)行，可以抵御雙花攻擊，同時(shí)對(duì)區(qū)塊設(shè)置了傳播終止條件，解決哈希圖空區(qū)塊傳播造成的存儲(chǔ)浪費(fèi)的問(wèn)題。雖然哈希圖為MANETs環(huán)境中應(yīng)用區(qū)塊鏈提供了一種可行的解決方案，但也存在一些問(wèn)題。首先，移動(dòng)自組網(wǎng)節(jié)點(diǎn)的頻繁移動(dòng)會(huì)引發(fā)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化，而哈希圖節(jié)點(diǎn)間地位平等，以全網(wǎng)共識(shí)為主，網(wǎng)絡(luò)發(fā)生分區(qū)時(shí)，節(jié)點(diǎn)無(wú)法得知分區(qū)內(nèi)節(jié)點(diǎn)的數(shù)目，阻礙了分區(qū)內(nèi)共識(shí)的進(jìn)行；其次，哈希圖采用Gossip協(xié)議傳遞事件消息，對(duì)鄰居節(jié)點(diǎn)的選擇具有隨機(jī)性，影響了通信效果，并且不能迅速檢測(cè)出信息量較多的新入簇節(jié)點(diǎn)；最后，移動(dòng)自組網(wǎng)節(jié)點(diǎn)資源有限，電池能量比較珍貴，而哈希圖共識(shí)計(jì)算復(fù)雜，步驟多，時(shí)延較高，會(huì)消耗較多的設(shè)備資源。

本文對(duì)以上不足進(jìn)行改進(jìn)，提出一種基于哈希圖的移動(dòng)自組網(wǎng)區(qū)塊鏈模型。該模型首先將無(wú)秩序的移動(dòng)節(jié)點(diǎn)劃分成簇，并選舉簇首，以分層結(jié)構(gòu)代替平面結(jié)構(gòu)，減少節(jié)點(diǎn)移動(dòng)帶來(lái)的控制開(kāi)銷(xiāo)，并由簇首負(fù)責(zé)統(tǒng)計(jì)簇內(nèi)節(jié)點(diǎn)數(shù)量，寫(xiě)入事件中進(jìn)行傳播，解決了缺少關(guān)鍵參數(shù)無(wú)法進(jìn)行簇內(nèi)共識(shí)的問(wèn)題，提高了網(wǎng)絡(luò)管理能力；其次，對(duì)Gossip協(xié)議的不足進(jìn)行改進(jìn)，提出FS-Gossip（fast spreading Gossip）協(xié)議，以增大有效信息交換的概率，減少通信資源浪費(fèi)；最后，對(duì)復(fù)雜的哈希圖共識(shí)進(jìn)行改進(jìn)，簡(jiǎn)化了共識(shí)流程，并提出一種事件傳播機(jī)制，明確了事件的傳播方向，提高事件擴(kuò)散的速度，降低時(shí)延。

本文的主要貢獻(xiàn)如下：a） 提出一種基于權(quán)值的分簇算法，并將簇首選舉的權(quán)值寫(xiě)入事件中，代替節(jié)點(diǎn)間互相交換權(quán)值的方法，減少了通信開(kāi)銷(xiāo);b） 針對(duì)原始Gossip協(xié)議傳播效率較低的問(wèn)題，提出一種快速FS-Gossip協(xié)議，減少鄰居節(jié)點(diǎn)選擇的盲目性，提高新入簇節(jié)點(diǎn)的檢測(cè)速度;c） 提出一種簡(jiǎn)化的哈希圖共識(shí)機(jī)制，降低了事件確認(rèn)的時(shí)延，提升區(qū)塊鏈的性能，同時(shí)提出一種基于簇首優(yōu)先原則的傳播機(jī)制，加快事件的傳播速度。

1 相關(guān)工作

1.1 分區(qū)共識(shí)

區(qū)塊鏈最核心的部分是共識(shí)層，共識(shí)層應(yīng)用共識(shí)算法實(shí)現(xiàn)全網(wǎng)節(jié)點(diǎn)數(shù)據(jù)的一致性，共識(shí)算法決定了區(qū)塊鏈的性能與效率。分區(qū)（partitioning）將節(jié)點(diǎn)劃分為不同分區(qū)，分而治之，并行共識(shí)，是一種提高區(qū)塊鏈性能和擴(kuò)展性的有效方法［11］，同時(shí)分區(qū)共識(shí)也與移動(dòng)自組網(wǎng)的分簇共識(shí)相適應(yīng)。Elastico［12］首先提出了區(qū)塊鏈分區(qū)的設(shè)計(jì)，節(jié)點(diǎn)運(yùn)行PoW隨機(jī)進(jìn)行分區(qū)，分區(qū)內(nèi)共識(shí)使用PBFT，然而分區(qū)時(shí)挖礦的難度不好控制。OmniLedger［13］采用RandHound方案產(chǎn)生無(wú)偏隨機(jī)數(shù)，保證了分區(qū)的隨機(jī)性，卻可能導(dǎo)致單一分區(qū)內(nèi)節(jié)點(diǎn)數(shù)量過(guò)少，降低區(qū)塊鏈安全性。文獻(xiàn)［14］提出一種基于雙鏈模型的分區(qū)共識(shí)協(xié)議，節(jié)點(diǎn)先進(jìn)行地址隨機(jī)分區(qū)，交押金成為權(quán)益人，所擁有的權(quán)益再按份額隨機(jī)分區(qū)，避免分區(qū)內(nèi)權(quán)益較大的節(jié)點(diǎn)壟斷出塊權(quán)，提升了權(quán)益分區(qū)的安全性。以上分區(qū)方法可以提前設(shè)計(jì)，屬于主動(dòng)分區(qū)方法，網(wǎng)絡(luò)環(huán)境為部分同步，不同分區(qū)間同步數(shù)據(jù)延時(shí)較低。部分同步網(wǎng)絡(luò)模型對(duì)消息的到達(dá)時(shí)間作出假設(shè)，要求消息傳播有確定的時(shí)延上限，一旦網(wǎng)絡(luò)分裂，共識(shí)可能終止，抗攻擊性較差。而移動(dòng)自組網(wǎng)的節(jié)點(diǎn)均處于不可預(yù)測(cè)的移動(dòng)狀態(tài)中，發(fā)生網(wǎng)絡(luò)分裂后節(jié)點(diǎn)將依據(jù)地理位置被動(dòng)進(jìn)行分區(qū)，并在分區(qū)內(nèi)繼續(xù)進(jìn)行共識(shí)，不同分區(qū)間的區(qū)塊延時(shí)受諸多因素影響，消息傳輸沒(méi)有確定的時(shí)延上限，允許異步到達(dá)，情況更加復(fù)雜。

1.2 改進(jìn)Gossip協(xié)議

Gossip協(xié)議（又稱流言傳播協(xié)議）具有簡(jiǎn)單高效的特點(diǎn)，以及很好的可擴(kuò)展性與魯棒性，常用于大規(guī)模點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)與傳播，然而原始Gossip協(xié)議在具體應(yīng)用中可能引起冗余與延時(shí)，許多學(xué)者對(duì)Gossip協(xié)議進(jìn)行研究，提出不少改進(jìn)方案。文獻(xiàn)［15］提出一種基于 Gossip 的先推后拉的快速數(shù)據(jù)分發(fā)方法，主動(dòng)推送和被動(dòng)請(qǐng)求的切換以當(dāng)前網(wǎng)絡(luò)中有效鏈路的概率閾值為分界點(diǎn)，減少了分發(fā)冗余量與帶寬浪費(fèi)。文獻(xiàn)［16］提出一種改進(jìn)的節(jié)點(diǎn)選擇算法 MR-Gossip（most reliable Gossip），結(jié)合模糊理論提出基于可靠性的節(jié)點(diǎn)選擇策略，提高搜索效率。文獻(xiàn)［17］提出基于改進(jìn)Gossip協(xié)議的數(shù)據(jù)同步方法。運(yùn)用環(huán)算法選舉領(lǐng)導(dǎo)者，提高數(shù)據(jù)同步效率，減少數(shù)據(jù)同步對(duì)系統(tǒng)整體性能的影響。文獻(xiàn)［18］提出一種樹(shù)型結(jié)構(gòu)的傳播路由模型，加快傳播速度，降低收斂的時(shí)間，減少冗余。文獻(xiàn)［19］提出極化的Gossip協(xié)議，設(shè)置兩種Gossip轉(zhuǎn)發(fā)概率，傳播方向正確時(shí)加大擴(kuò)散的概率，反之使用衰減概率。文獻(xiàn)［20］提出基于Gossip協(xié)議的信任收集共識(shí)算法，節(jié)點(diǎn)通過(guò)評(píng)估鄰近節(jié)點(diǎn)的信息度選擇通信節(jié)點(diǎn)，消息在通信過(guò)程中收集信任值，超過(guò)閾值，消息達(dá)成共識(shí)。目前改進(jìn)方案大多應(yīng)用于同步網(wǎng)絡(luò)，主要篩選信息度較高的鄰居節(jié)點(diǎn)進(jìn)行通信，而在移動(dòng)自組網(wǎng)環(huán)境中，節(jié)點(diǎn)在不同分簇間移動(dòng)，新入簇節(jié)點(diǎn)會(huì)攜帶其他分簇的信息，為保證數(shù)據(jù)的安全性與一致性，這些新信息需迅速在該簇節(jié)點(diǎn)中同步并達(dá)成共識(shí)，所以除信息度這一因素，改進(jìn)Gossip協(xié)議還需考慮節(jié)點(diǎn)的入簇時(shí)間，以加快新入簇節(jié)點(diǎn)的檢測(cè)速度。

2 基于哈希圖的移動(dòng)自組網(wǎng)區(qū)塊鏈模型

2.1 模型結(jié)構(gòu)

移動(dòng)自組網(wǎng)邏輯上分為平面式和層次式兩種結(jié)構(gòu)。平面式結(jié)構(gòu)的特點(diǎn)是所有節(jié)點(diǎn)地位平等，網(wǎng)絡(luò)健壯性較強(qiáng)，但當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，用于發(fā)現(xiàn)路由和位置管理的控制報(bào)文也隨之迅速增加，網(wǎng)絡(luò)效率顯著降低，存在可擴(kuò)展性問(wèn)題。層次結(jié)構(gòu)將網(wǎng)絡(luò)節(jié)點(diǎn)劃分到不同的簇中，每個(gè)簇選擇一個(gè)簇首負(fù)責(zé)簇的管理，可以有效解決移動(dòng)自組網(wǎng)的可擴(kuò)展性問(wèn)題，因此本文針對(duì)分簇結(jié)構(gòu)研究移動(dòng)自組網(wǎng)區(qū)塊鏈模型。圖1為本文采用的移動(dòng)自組網(wǎng)分簇結(jié)構(gòu)，相較于完全的分布式結(jié)構(gòu)，分簇結(jié)構(gòu)可以節(jié)省拓?fù)渥兓斐傻目刂崎_(kāi)銷(xiāo)，更有利于Ad hoc網(wǎng)絡(luò)的擴(kuò)展和管理，提高網(wǎng)絡(luò)的性能與實(shí)用性。通過(guò)分簇算法，將網(wǎng)絡(luò)中所有節(jié)點(diǎn)依據(jù)地理位置聚合成不同的簇。分簇后，有簇首、簇成員、網(wǎng)關(guān)三種角色，分別發(fā)揮不同的傳播作用，其中網(wǎng)關(guān)節(jié)點(diǎn)用于連接相鄰分簇，在不同分簇間傳遞信息實(shí)現(xiàn)跨簇通信。

形成簇結(jié)構(gòu)后，每個(gè)節(jié)點(diǎn)在本地存儲(chǔ)一張全網(wǎng)的哈希圖，通過(guò)FS-Gossip協(xié)議選擇信息收益較大的鄰居節(jié)點(diǎn)，進(jìn)行通信，更新并維護(hù)本地的哈希圖。節(jié)點(diǎn)產(chǎn)生或接收新事件，將按照一種傳播機(jī)制進(jìn)行事件傳播，提高擴(kuò)散的速度。

節(jié)點(diǎn)移動(dòng)會(huì)導(dǎo)致網(wǎng)絡(luò)不斷發(fā)生分裂與合并，可能使某一分區(qū)內(nèi)節(jié)點(diǎn)數(shù)量較少，這時(shí)如果惡意節(jié)點(diǎn)發(fā)動(dòng)女巫攻擊，偽造多個(gè)身份控制共識(shí)過(guò)程，會(huì)嚴(yán)重影響系統(tǒng)的安全性，所以需對(duì)所有加入網(wǎng)絡(luò)的節(jié)點(diǎn)進(jìn)行身份認(rèn)證，本文假設(shè)模型應(yīng)用場(chǎng)景為聯(lián)盟鏈或私有鏈。

2.2 哈希圖

本文基于哈希圖構(gòu)建面向移動(dòng)自組網(wǎng)的區(qū)塊鏈模型。2016年提出的哈希圖是一種基于Gossip協(xié)議的DAG共識(shí)算法，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都在本地保存一張哈希圖，節(jié)點(diǎn)間通過(guò)Gossip協(xié)議更新本地副本，延續(xù)哈希圖。哈希圖中沒(méi)有區(qū)塊，由許多事件（event）組成，每個(gè)事件代表發(fā)生了一次Gossip通信，如圖2所示，節(jié)點(diǎn)A與D通信，接收了節(jié)點(diǎn)D當(dāng)前哈希圖副本中的全部事件，更新結(jié)束時(shí)，節(jié)點(diǎn)A產(chǎn)生一個(gè)新事件，指向自身的上一個(gè)事件與節(jié)點(diǎn)D的當(dāng)前事件，以新事件記錄本次的Gossip活動(dòng)。哈希圖保存了節(jié)點(diǎn)間發(fā)生Gossip的歷史記錄，通過(guò)哈希圖可以清楚地看到事件傳播的路徑，即節(jié)點(diǎn)于何時(shí)、何處更新了本地的副本，事件在不斷地傳播中被其他節(jié)點(diǎn)見(jiàn)證并達(dá)成共識(shí)。

哈希圖用虛擬投票代替實(shí)際投票，具有節(jié)省通信開(kāi)銷(xiāo)的優(yōu)點(diǎn)，圖中完整保存了所有的交易信息，不會(huì)丟失交易。哈希圖完全異步，沒(méi)有l(wèi)eader，也無(wú)須工作量證明，因此本文將哈希圖用于網(wǎng)絡(luò)動(dòng)態(tài)變化，不斷發(fā)生分裂與合并的MANETs環(huán)境。哈希圖事件結(jié)構(gòu)如圖3所示，交易信息一項(xiàng)可以為空，當(dāng)節(jié)點(diǎn)暫無(wú)交易，又收到其他節(jié)點(diǎn)的新事件，為了進(jìn)行存儲(chǔ)與投票，就會(huì)創(chuàng)建一個(gè)空事件。

哈希圖通常應(yīng)用于共識(shí)成員固定的聯(lián)盟鏈中，并假設(shè)成員節(jié)點(diǎn)的數(shù)量已知，進(jìn)而判斷是否達(dá)到2/3的共識(shí)門(mén)檻。然而，在拓?fù)鋭?dòng)態(tài)變化的MANETs環(huán)境中，全網(wǎng)節(jié)點(diǎn)被劃分為多個(gè)簇，簇成員形成共識(shí)組進(jìn)行共識(shí)以繼續(xù)協(xié)同工作，節(jié)點(diǎn)移動(dòng)性會(huì)導(dǎo)致節(jié)點(diǎn)不斷加入和離開(kāi)簇，成員的動(dòng)態(tài)變化使得節(jié)點(diǎn)無(wú)法及時(shí)獲知簇內(nèi)節(jié)點(diǎn)數(shù)量，給簇內(nèi)共識(shí)帶來(lái)挑戰(zhàn)。此外，哈希圖共識(shí)流程長(zhǎng)，計(jì)算復(fù)雜，時(shí)延較高，會(huì)消耗較多的設(shè)備資源。針對(duì)這些問(wèn)題，本文對(duì)分簇算法和Gossip協(xié)議進(jìn)行改進(jìn)，使得哈希圖可以更好地適配移動(dòng)自組網(wǎng)區(qū)塊鏈的共識(shí)。本文設(shè)計(jì)了兩種特殊的事件結(jié)構(gòu)，分別為選舉事件與簇首見(jiàn)證事件，選舉事件用于簇首選舉，簇首見(jiàn)證事件用于傳播簇內(nèi)節(jié)點(diǎn)數(shù)量這一參數(shù)，將在后文介紹。

2.3 分簇算法

分簇是一種常見(jiàn)的應(yīng)用于移動(dòng)自組網(wǎng)的節(jié)點(diǎn)管理方法，模型將無(wú)規(guī)則無(wú)秩序的移動(dòng)自組網(wǎng)節(jié)點(diǎn)劃分成簇，分而治之，與未分簇相比，節(jié)省了動(dòng)態(tài)拓?fù)鋷?lái)的全局控制開(kāi)銷(xiāo)，更有利于事件的傳播，同時(shí)提高了網(wǎng)絡(luò)的可擴(kuò)展性。分簇時(shí)，節(jié)點(diǎn)依據(jù)地理位置，獲取鄰居列表，協(xié)同任務(wù)的節(jié)點(diǎn)組成一個(gè)簇，簇內(nèi)任意節(jié)點(diǎn)間依靠單跳或多跳通信，可將消息傳達(dá)。超出分簇通信范圍的節(jié)點(diǎn)，可以加入其他分簇，或成為未分簇的自由節(jié)點(diǎn)。

分簇算法通常需選舉簇首對(duì)分簇進(jìn)行管理，現(xiàn)有算法大多將簇首選舉所參考的數(shù)據(jù)值進(jìn)行全網(wǎng)廣播，即網(wǎng)絡(luò)中所有節(jié)點(diǎn)廣播自己的數(shù)據(jù)，同時(shí)接收其他節(jié)點(diǎn)的數(shù)據(jù)，進(jìn)行比較，按照算法定義的規(guī)則選出合適的簇首節(jié)點(diǎn)，該方法通信復(fù)雜度較高，占用較多的通信資源，可能導(dǎo)致區(qū)塊鏈在簇首選舉期間不可用。本文利用哈希圖傳播事件分布存儲(chǔ)的特點(diǎn)，對(duì)事件結(jié)構(gòu)進(jìn)行改進(jìn)，借用事件的傳播散發(fā)選舉數(shù)據(jù)，將通信開(kāi)銷(xiāo)由O（n2）降為O（n），同時(shí)保證區(qū)塊鏈的可用性。

本文簇首選舉算法設(shè)計(jì)如下：首先，所有節(jié)點(diǎn)進(jìn)行初始化，建立自己的鄰居視圖，并獲得一些自身的性能數(shù)據(jù)。然后，節(jié)點(diǎn)綜合連接度、跳數(shù)和、活躍度、相對(duì)移動(dòng)性、電池能量五個(gè)因素，代入權(quán)值公式算出能力值。本文通過(guò)設(shè)計(jì)一種特殊的事件結(jié)構(gòu)，借助事件傳播捎帶能力值數(shù)據(jù)，減少節(jié)點(diǎn)間通過(guò)消息交換能力值數(shù)據(jù)造成的通信開(kāi)銷(xiāo)。簇首選舉期的事件結(jié)構(gòu)如圖4所示，其中包含時(shí)間戳、交易、自父事件的哈希值、其他父事件的哈希值以及能力值五個(gè)字段，增加的能力值字段用于選舉簇首。

通過(guò)在事件中增加能力值（capacity value）字段，節(jié)點(diǎn)存儲(chǔ)新事件的同時(shí)也獲得了其他節(jié)點(diǎn)的能力值數(shù)據(jù)。選舉事件可以附帶交易信息，在未選出簇首時(shí)，節(jié)點(diǎn)仍能發(fā)布交易，不影響區(qū)塊鏈功能的正常運(yùn)行，待簇首選舉完成后對(duì)含有交易的事件進(jìn)行共識(shí)確認(rèn)。當(dāng)簇內(nèi)所有節(jié)點(diǎn)均發(fā)出了選舉事件，哈希圖中能力值最大的節(jié)點(diǎn)成為簇首。最后，所有節(jié)點(diǎn)確認(rèn)自己的身份，簇首整理出當(dāng)前簇成員列表，在同步哈希圖時(shí)，生成具有特殊結(jié)構(gòu)的簇首見(jiàn)證事件，將簇內(nèi)節(jié)點(diǎn)數(shù)量與成員列表傳播給其他節(jié)點(diǎn)，保證共識(shí)的順利進(jìn)行。 分簇算法的流程如圖5所示。

本文將移動(dòng)自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)抽象成一張簡(jiǎn)單的有向圖，記作G=（V，E），這里V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)組成的集合，E為邊集，表示兩個(gè)節(jié)點(diǎn)間是否可以直接通信。下面對(duì)使用的參數(shù)進(jìn)行定義：

a）節(jié)點(diǎn)ID。移動(dòng)自組網(wǎng)中每個(gè)節(jié)點(diǎn)具有唯一的標(biāo)識(shí)，節(jié)點(diǎn)i的ID記為IDi。

b）鄰居節(jié)點(diǎn)集合。節(jié)點(diǎn)一跳鄰居視圖中的所有節(jié)點(diǎn)構(gòu)成的集合，記為N（v）。

c）鄰居節(jié)點(diǎn)變化率。存在兩個(gè)時(shí)刻t1，t2，得到兩個(gè)時(shí)刻總共出現(xiàn)的鄰居節(jié)點(diǎn)數(shù)目為|N（v）t1∪N（v）t2|，兩個(gè)時(shí)刻重合的鄰居節(jié)點(diǎn)數(shù)目為|N（v）t1∩N（v）t2|，則

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

d）連接度。節(jié)點(diǎn)擁有鄰居節(jié)點(diǎn)的數(shù)量，記為Cd（connectivity degree），Cd=|N（v）|。

e）可通信節(jié)點(diǎn)列表。由節(jié)點(diǎn)在一跳或多跳通信范圍內(nèi)可到達(dá)的節(jié)點(diǎn)組成，表中記錄節(jié)點(diǎn)ID與對(duì)應(yīng)的跳數(shù)，節(jié)點(diǎn)通過(guò)周期性與鄰居節(jié)點(diǎn)交換此表來(lái)進(jìn)行更新，記為ntable。

f）跳數(shù)和。節(jié)點(diǎn)將可通信節(jié)點(diǎn)列表中的跳數(shù)進(jìn)行相加，跳數(shù)越少，節(jié)點(diǎn)的通信便利度越高，記為Hs（hop sum）。

設(shè)可通信節(jié)點(diǎn)列表中共有n個(gè)節(jié)點(diǎn)，即

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

g）活躍度。節(jié)點(diǎn)在上一個(gè)epoch中創(chuàng)建事件的頻率，記為Ef（event frequency）。

h）相對(duì)移動(dòng)性。節(jié)點(diǎn)相較于附近節(jié)點(diǎn)，移動(dòng)性的強(qiáng)弱，記為Rm（relative mobility）。

i）電池能量。表示節(jié)點(diǎn)剩余的電池能量的多少，記為Bp（battery power）。

考慮到移動(dòng)節(jié)點(diǎn)運(yùn)算能力有限，因此簡(jiǎn)化了相對(duì)移動(dòng)性的計(jì)算，規(guī)定其近似等于鄰居節(jié)點(diǎn)變化率的倒數(shù)，即

Rm=1NCR（v）（3）

NCR（v）的值越大，節(jié)點(diǎn)的鄰居變化越小，節(jié)點(diǎn)越穩(wěn)定，相對(duì)移動(dòng)性越弱。

能力值計(jì)算公式為

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

即

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

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

可根據(jù)系統(tǒng)運(yùn)行狀態(tài)調(diào)整每項(xiàng)的權(quán)重，改變簇首選舉的側(cè)重點(diǎn)，以獲得更高的系統(tǒng)性能。

分簇成功后產(chǎn)生了簇首、簇成員和網(wǎng)關(guān)三種角色。簇首負(fù)責(zé)統(tǒng)計(jì)每一輪次中簇成員的數(shù)量，收集并管理本簇及其他簇產(chǎn)生的新事件，并依據(jù)傳播機(jī)制運(yùn)行Gossip算法；簇成員承擔(dān)中間路由的功能，在傳播過(guò)程中檢查事件，存儲(chǔ)簇內(nèi)一致的分布式賬本；網(wǎng)關(guān)是指能與兩個(gè)或多個(gè)簇直接通信的節(jié)點(diǎn)，負(fù)責(zé)簇間事件的傳播，連接不同簇，提高了區(qū)塊的擴(kuò)散效率。

分簇完成后，節(jié)點(diǎn)維護(hù)鄰居列表，發(fā)送的Hello消息格式為

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

其中：字段IDi表示節(jié)點(diǎn)i的唯一標(biāo)識(shí)ID；Statusi表示節(jié)點(diǎn)i的狀態(tài)，如果節(jié)點(diǎn)未分簇，值為0，如果節(jié)點(diǎn)是網(wǎng)關(guān)節(jié)點(diǎn)，值為1，如果節(jié)點(diǎn)是簇成員節(jié)點(diǎn)，值為分簇ID（clusterID），本文設(shè)置分簇ID為簇首ID； hopi表示節(jié)點(diǎn)i距離簇首的跳數(shù)；eventi表示節(jié)點(diǎn)i擁有事件的數(shù)量；tlivei表示節(jié)點(diǎn)i從該簇誕生起，在簇內(nèi)生存的時(shí)間，一旦節(jié)點(diǎn)離開(kāi)該簇，tlivei清空為零；timestamp表示節(jié)點(diǎn)i發(fā)出消息的時(shí)間戳；ski（hash）表示節(jié)點(diǎn)i將整條消息取哈希值，并用私鑰簽名，防止其他節(jié)點(diǎn)偽造消息，提高安全性。

為了保證系統(tǒng)的安全性，簇首需要定期更換。然而，頻繁地分簇會(huì)引起網(wǎng)絡(luò)動(dòng)蕩，使區(qū)塊鏈的性能下降。因此，本文模型采用劃分任期、簇首失效時(shí)發(fā)起替換的機(jī)制，規(guī)定簇首的任期為一個(gè)紀(jì)元（epoch），若紀(jì)元未結(jié)束，而簇首出現(xiàn)故障無(wú)法工作，或在運(yùn)動(dòng)中移出該簇，則觸發(fā)簇首更換算法，節(jié)點(diǎn)產(chǎn)生選舉事件，選出新的簇首。如果當(dāng)前紀(jì)元已結(jié)束，該簇所有節(jié)點(diǎn)更新自身性能數(shù)據(jù)，重新計(jì)算能力值并創(chuàng)建簇首選舉事件，選出新的簇首，開(kāi)啟下一個(gè)紀(jì)元。簇首更換算法如算法1所示。

算法1 簇首更換算法

輸入：出現(xiàn)故障的當(dāng)前簇首節(jié)點(diǎn)。

輸出：新的簇首節(jié)點(diǎn)。

while （node CurrentCH fails） do // 節(jié)點(diǎn)CurrentCH表示當(dāng)前簇首節(jié)點(diǎn)

if （current epoch ends = = true） // 判斷當(dāng)前epoch是否結(jié)束

Call clustering algorithm ; /* 如果當(dāng)前epoch結(jié)束，調(diào)用分簇算法，重新分簇 */

else

create election event ; // 創(chuàng)建簇首選舉事件

exchange election events and grow local Hashgraph ; /* 交換選舉事件，并發(fā)展哈希圖*/

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

node N = getNodeID （max number） ; // 獲得該節(jié)點(diǎn)的ID

node N becomes NewCH ；// 新簇首選舉結(jié)束

end if

end while

2.4 FS- Gossip協(xié)議

本文針對(duì)移動(dòng)自組網(wǎng)的需求，對(duì)Gossip協(xié)議進(jìn)行了改進(jìn)。Gossip協(xié)議于1978年被提出，是一種簡(jiǎn)單高效的數(shù)據(jù)分發(fā)方法，具有良好的可擴(kuò)展性與魯棒性，在點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)中發(fā)揮關(guān)鍵的作用。當(dāng)一個(gè)節(jié)點(diǎn)需要同步消息時(shí)，它不與服務(wù)器進(jìn)行連接，而是隨機(jī)從對(duì)等的鄰居節(jié)點(diǎn)中選擇節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，其他節(jié)點(diǎn)收到消息后同理，該過(guò)程類似于流行病或謠言的傳播。常見(jiàn)的Gossip協(xié)議交換信息有三種方法：

a） 基于推（push）的方法，節(jié)點(diǎn)A將信息發(fā)送給節(jié)點(diǎn)B，節(jié)點(diǎn)B根據(jù)收到的信息進(jìn)行更新；

b） 基于拉（pull）的方法，節(jié)點(diǎn)A向節(jié)點(diǎn)B主動(dòng)請(qǐng)求，節(jié)點(diǎn)B將信息發(fā)給節(jié)點(diǎn)A，A進(jìn)行更新；

c） 基于推/拉（push/pull）的方法，A與B相互發(fā)送信息給對(duì)方。

哈希圖中采用了基于拉的方法，即節(jié)點(diǎn)隨機(jī)請(qǐng)求一個(gè)鄰居節(jié)點(diǎn)，該鄰居節(jié)點(diǎn)將存儲(chǔ)的所有事件發(fā)送給原節(jié)點(diǎn)，原節(jié)點(diǎn)更新本地的哈希圖并創(chuàng)建一個(gè)新事件，代表了此次Gossip過(guò)程。

然而，Gossip協(xié)議具有隨機(jī)性與盲目性，進(jìn)行鄰居的選擇時(shí)，不同節(jié)點(diǎn)的概率是相等的，容易造成延時(shí)與冗余，浪費(fèi)通信資源，使性能下降，無(wú)法滿足移動(dòng)自組網(wǎng)的需求。為了更快速地傳播事件，提高復(fù)制速度，節(jié)點(diǎn)應(yīng)增大優(yōu)質(zhì)鄰居節(jié)點(diǎn)的選擇概率，進(jìn)行有效的信息互換，減少無(wú)效的Gossip次數(shù)，避免冗余的通信量與資源浪費(fèi)，本文提出改進(jìn)的Gossip協(xié)議，即FS-Gossip（fast spreading Gossip）。

在FS-Gossip協(xié)議中，假設(shè)節(jié)點(diǎn)Nodei共有m個(gè)鄰居，鄰居節(jié)點(diǎn)列表為{n1，n2，…，nm}，從本地哈希圖事件的時(shí)間戳，可得節(jié)點(diǎn)Nodei上一次與鄰居節(jié)點(diǎn)nj （1≤j≤m）發(fā)生Gossip的時(shí)間為t0（i，j），當(dāng)前時(shí)間為t。節(jié)點(diǎn)Nodei周期性發(fā)送Hello消息，維護(hù)鄰居列表，并通過(guò)鄰居節(jié)點(diǎn)回復(fù)的Hello消息中的參數(shù)值計(jì)算概率，選擇概率較高的鄰居節(jié)點(diǎn)進(jìn)行拉，實(shí)現(xiàn)Gossip信息收益最大化。

設(shè)k為收益預(yù)估值，k計(jì)算公式如下：

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

其中：0≤μ≤1，0≤λ≤1·μ、λ為歸一化調(diào)節(jié)因子。當(dāng)節(jié)點(diǎn)處于同一分簇時(shí)，節(jié)點(diǎn)擁有事件數(shù)量的差值越大，距離上一次Gossip同步過(guò)去的時(shí)間越久，預(yù)估發(fā)生Gossip后的信息收益越大。

當(dāng)一節(jié)點(diǎn)離開(kāi)它所在簇，加入Nodei節(jié)點(diǎn)所在簇，成為Nodei節(jié)點(diǎn)的鄰居時(shí)，由于該節(jié)點(diǎn)可能存儲(chǔ)了其他簇的事件，有效信息更多，可知該節(jié)點(diǎn)被選中的概率應(yīng)高于同簇的其他鄰居節(jié)點(diǎn)，發(fā)生Gossip的優(yōu)先級(jí)更高。

將k代入概率p的計(jì)算公式：

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

其中：φ為調(diào)節(jié)系數(shù)，防止φk值過(guò)大，影響公式的效果;ω為判斷項(xiàng)，通過(guò)將Hello消息中的簇內(nèi)生存時(shí)間字段tlive與設(shè)置的閾值相比較，可判斷該鄰居節(jié)點(diǎn)是否處于同簇。若該節(jié)點(diǎn)簇內(nèi)生存時(shí)間大于閾值，可推知處于同簇，ω值為0；反之，簇內(nèi)生存時(shí)間小于閾值，可推知該節(jié)點(diǎn)為新節(jié)點(diǎn)，要么離開(kāi)其他簇加入此簇，要么是新加入?yún)^(qū)塊鏈網(wǎng)絡(luò)的節(jié)點(diǎn)，這時(shí)，ω取上限值，以提高與之進(jìn)行Gossip的概率。

ω=0?? tlive>bounduppertlive

其中，被判定為同簇節(jié)點(diǎn)的閾值bound與簇首上一輪次（round）共識(shí)所用時(shí)間及事件差異率有關(guān)。上一輪所用共識(shí)時(shí)間越長(zhǎng)，閾值越高，簇內(nèi)生存時(shí)間不足一個(gè)輪次的新節(jié)點(diǎn)將被快速檢測(cè)出來(lái)。事件差異率大，說(shuō)明新節(jié)點(diǎn)信息差較大，閾值也將提高。

哈希圖中節(jié)點(diǎn)同步事件時(shí)，為節(jié)省帶寬開(kāi)銷(xiāo)，通常不直接發(fā)送一張完整的哈希圖，而是發(fā)送一張節(jié)點(diǎn)存儲(chǔ)事件表，表中記錄了對(duì)不同節(jié)點(diǎn)分別存儲(chǔ)了多少事件，對(duì)面節(jié)點(diǎn)根據(jù)此表，將缺少的事件補(bǔ)給原節(jié)點(diǎn)。

設(shè)全網(wǎng)共v個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)Nodei與其鄰居節(jié)點(diǎn)nj發(fā)生存儲(chǔ)差異的事件數(shù)量計(jì)算公式如下：

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

可以得到相比于節(jié)點(diǎn)Nodei，事件差異率為

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

閾值將依據(jù)簇內(nèi)運(yùn)行狀態(tài)與新節(jié)點(diǎn)存儲(chǔ)情況，進(jìn)行動(dòng)態(tài)調(diào)整，計(jì)算如下：

bound=（1+eventrate）tround（11）

2.5 共識(shí)算法

哈希圖的共識(shí)中，每個(gè)節(jié)點(diǎn)首先產(chǎn)生一個(gè)見(jiàn)證事件，隨著Gossip的不斷進(jìn)行，當(dāng)節(jié)點(diǎn)存儲(chǔ)的副本中能看到超過(guò)2/3個(gè)上一輪的見(jiàn)證事件時(shí)，就產(chǎn)生新一輪的見(jiàn)證事件。達(dá)成共識(shí)需要經(jīng)過(guò)虛擬投票、統(tǒng)計(jì)投票、確定聲望三個(gè)階段，結(jié)果是一個(gè)事件至少經(jīng)過(guò)三輪，才能達(dá)成共識(shí)，劃分輪次計(jì)算復(fù)雜，消耗了設(shè)備資源，且事件確認(rèn)的時(shí)延較高。本文對(duì)共識(shí)過(guò)程進(jìn)行了簡(jiǎn)化與改進(jìn)，設(shè)置共識(shí)結(jié)果有簇內(nèi)共識(shí)與全網(wǎng)共識(shí)兩種。若一個(gè)事件被簇內(nèi)超過(guò)2/3的節(jié)點(diǎn)直接或間接地引用，則達(dá)成簇內(nèi)共識(shí)；若一個(gè)事件被全網(wǎng)超過(guò)2/3的節(jié)點(diǎn)直接或間接地引用，則達(dá)成全網(wǎng)共識(shí)。在移動(dòng)自組網(wǎng)環(huán)境中，隨著節(jié)點(diǎn)的自由移動(dòng)，網(wǎng)絡(luò)完全徹底地分裂，沒(méi)有網(wǎng)關(guān)節(jié)點(diǎn)時(shí)，不同分簇間很難直接通信，導(dǎo)致最終達(dá)成全網(wǎng)同步的時(shí)間不可預(yù)知，故以簇內(nèi)共識(shí)的時(shí)延為準(zhǔn)，縮短達(dá)成共識(shí)所需的時(shí)間。

確定簇內(nèi)節(jié)點(diǎn)的成員和數(shù)量，對(duì)簇內(nèi)共識(shí)的達(dá)成具有關(guān)鍵作用。如圖6所示，本文將簇首發(fā)出的見(jiàn)證事件設(shè)置為特殊結(jié)構(gòu)，增加了簇內(nèi)節(jié)點(diǎn)數(shù)量、簇成員列表兩個(gè)字段。在每一輪共識(shí)中，簇成員節(jié)點(diǎn)通過(guò)簇首發(fā)出的見(jiàn)證事件，獲知本輪簇內(nèi)節(jié)點(diǎn)數(shù)量與成員列表，從而可以判斷是否達(dá)到創(chuàng)建見(jiàn)證事件的門(mén)檻。簇內(nèi)節(jié)點(diǎn)發(fā)生變動(dòng)共有兩種情況：一種由節(jié)點(diǎn)數(shù)的改變直接顯示出來(lái)；另一種節(jié)點(diǎn)數(shù)未變，但簇成員組成發(fā)生變化。通過(guò)簇首見(jiàn)證事件攜帶的信息，簇內(nèi)節(jié)點(diǎn)可以及時(shí)獲知成員情況，進(jìn)而判斷是否達(dá)成共識(shí)。

本文的快速共識(shí)過(guò)程包括兩個(gè)步驟，事件最少經(jīng)過(guò)兩輪就能確認(rèn)。第一步為尋找候選的極佳見(jiàn)證事件（superb witness event），第二步為統(tǒng)計(jì)投票，判斷是否確定成為極佳見(jiàn)證事件，并劃分出達(dá)成共識(shí)的事件。當(dāng)任意節(jié)點(diǎn)創(chuàng)建第n輪見(jiàn)證事件時(shí)，說(shuō)明該節(jié)點(diǎn)已經(jīng)收到超過(guò)分簇節(jié)點(diǎn)數(shù)2/3的n-1輪的見(jiàn)證事件，在這些上一輪次的事件中，如果存在一條或多條路徑，從同一個(gè)見(jiàn)證事件起始，連接了其他所有事件，那么這一見(jiàn)證事件就成為極佳見(jiàn)證事件。即存在一個(gè)見(jiàn)證事件，在同輪次中，被超過(guò)2/3的簇內(nèi)節(jié)點(diǎn)引用過(guò)，該事件就達(dá)成共識(shí)，被該事件引用的所有父事件也達(dá)成了共識(shí)。共識(shí)確認(rèn)示意圖如圖7所示。

假如某一時(shí)刻的全局哈希圖如圖7（a）所示，分簇中的節(jié)點(diǎn)B創(chuàng)建第三輪B3見(jiàn)證事件時(shí)，從圖7（b）本地哈希圖副本中可以發(fā)現(xiàn)D2→A2和D2→B2這兩條路徑，分簇中節(jié)點(diǎn)數(shù)目為4，路徑中節(jié)點(diǎn)的數(shù)目超過(guò)了2/3的共識(shí)門(mén)檻，可以得知D2為極佳見(jiàn)證事件，D2所引用的所有第一輪的事件達(dá)成了共識(shí)。同理，從圖7（c）中可以發(fā)現(xiàn)，節(jié)點(diǎn)C創(chuàng)建C3見(jiàn)證事件時(shí)，看到D2被A2、B2、C2均驗(yàn)證過(guò)，也能得到D2為極佳見(jiàn)證事件，并劃分出共識(shí)確認(rèn)的事件。

如果節(jié)點(diǎn)創(chuàng)建第n輪見(jiàn)證事件時(shí)，發(fā)現(xiàn)本地哈希圖副本中，不存在滿足條件的n-1輪極佳見(jiàn)證事件，就繼續(xù)創(chuàng)建新事件，不斷地從鄰居節(jié)點(diǎn)處同步最新的副本，發(fā)展哈希圖，直到找出極佳見(jiàn)證事件。

3 傳播機(jī)制

本文設(shè)計(jì)一種基于簇首優(yōu)先的傳播機(jī)制，包括簇內(nèi)傳播與簇間傳播兩種傳播方式。節(jié)點(diǎn)收到新的含交易事件后，根據(jù)鄰居節(jié)點(diǎn)Hello消息中的跳數(shù)（hop）進(jìn)行篩選，選擇更靠近簇首的鄰居節(jié)點(diǎn)傳播本地副本，通過(guò)明確事件的傳播方向，確保簇首優(yōu)先收到包含交易事件并進(jìn)行檢查，以加快事件的傳播速度與新入簇節(jié)點(diǎn)的發(fā)現(xiàn)速度，降低傳播冗余。

3.1 簇內(nèi)傳播機(jī)制

事件的簇內(nèi)傳播，總體思路為簇成員節(jié)點(diǎn)收到含交易的非空事件后，先檢查本地哈希圖副本中是否有簇首發(fā)出的事件引用過(guò)它，如沒(méi)有引用則判定為新交易事件，則先沿著跳數(shù)減少的方向傳播事件，優(yōu)先讓簇首更新本地哈希副本，保存該事件，在簇首引用后，再沿著跳數(shù)增加的方向，傳播給簇內(nèi)其他節(jié)點(diǎn)。簇內(nèi)傳播過(guò)程如圖8所示。

圖8（a）中簇內(nèi)一個(gè)成員節(jié)點(diǎn)產(chǎn)生了一個(gè)新的含交易事件，標(biāo)記為單詞event的首字母“e”，該節(jié)點(diǎn)隨即將新事件以Gossip的方式傳播給鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)收到事件后，檢查本地哈希圖副本，發(fā)現(xiàn)簇首未直接或間接引用過(guò)該事件，則調(diào)用簇首優(yōu)先（CH-First）算法，沿著跳數(shù)減少趨近簇首的傳播路徑，篩選鄰居節(jié)點(diǎn)進(jìn)行傳播，簇首優(yōu)先算法的執(zhí)行過(guò)程如算法2所示。其他節(jié)點(diǎn)收到事件后同理，如圖8（b）所示。簇首收到事件，檢查格式、私鑰簽名無(wú)誤后，就傳播給鄰居節(jié)點(diǎn)，如圖8（c）所示。成員節(jié)點(diǎn)收到含有簇首引用事件的哈希圖，則按照跳數(shù)增加的方向進(jìn)行傳播，最后，簇內(nèi)全部節(jié)點(diǎn)都會(huì)收到該事件。通過(guò)明確事件傳播方向，可以建立有效的傳播秩序，避免傳播過(guò)程的混亂現(xiàn)象，減少通信冗余。

簇首優(yōu)先算法的執(zhí)行過(guò)程見(jiàn)算法2。

算法2 簇首優(yōu)先算法

輸入：鄰居節(jié)點(diǎn)列表NeighborList。

輸出：距離簇首更近的鄰居節(jié)點(diǎn)。

while （receive non-empty event with no CH event reference） do /* 收到的非空事件沒(méi)有簇首的引用 */

find hop data in NeighborList ; /* 在鄰居列表中查找鄰居節(jié)點(diǎn)距離簇首的跳數(shù) */

hop ← min（hop）; // 找到最小的跳數(shù)

node N = getNodeID （hop） ; // 獲得該鄰居節(jié)點(diǎn)的ID

gossip to node N；// 將更新事件發(fā)給該鄰居節(jié)點(diǎn)，CH-First算法結(jié)束

end while

3.2 簇間傳播機(jī)制

通過(guò)判斷有無(wú)網(wǎng)關(guān)節(jié)點(diǎn)，可將事件的簇間傳播劃分為兩種情況。當(dāng)簇間存在網(wǎng)關(guān)節(jié)點(diǎn)時(shí)，簇間傳播總體思路為依靠網(wǎng)關(guān)節(jié)點(diǎn)，實(shí)現(xiàn)事件的跨簇傳遞。如果一個(gè)節(jié)點(diǎn)同時(shí)處于兩個(gè)或多個(gè)簇首的通信范圍內(nèi)，那么該節(jié)點(diǎn)不屬于任何一個(gè)分簇，成為獨(dú)立的網(wǎng)關(guān)節(jié)點(diǎn)。如果兩個(gè)分簇距離較近，邊緣節(jié)點(diǎn)之間可以直接通信，那么就設(shè)定ID較小的邊緣節(jié)點(diǎn)成為網(wǎng)關(guān)節(jié)點(diǎn)。不同分簇之間可能會(huì)由網(wǎng)關(guān)節(jié)點(diǎn)相連，也可能彼此孤立沒(méi)有連接。如果分簇間存在網(wǎng)關(guān)節(jié)點(diǎn)，那么由網(wǎng)關(guān)節(jié)點(diǎn)作為溝通的橋梁，與不同簇的節(jié)點(diǎn)進(jìn)行Gossip通信，實(shí)現(xiàn)事件的跨簇傳播。

網(wǎng)關(guān)節(jié)點(diǎn)位于不同簇首之間時(shí)，借助網(wǎng)關(guān)節(jié)點(diǎn)的事件簇間傳播過(guò)程如圖9所示。圖9（a）中簇C2的簇首收到簇內(nèi)的事件后，首先判斷鄰居列表中是否包含網(wǎng)關(guān)節(jié)點(diǎn)，如果不包含，則不涉及借助網(wǎng)關(guān)節(jié)點(diǎn)的簇間傳播；如果包含，再判斷該事件是否曾經(jīng)發(fā)送給網(wǎng)關(guān)節(jié)點(diǎn)。如果已發(fā)送過(guò)，則不再發(fā)送；如果從未發(fā)送過(guò)，則優(yōu)先發(fā)給網(wǎng)關(guān)節(jié)點(diǎn)，如圖9（b）所示。網(wǎng)關(guān)節(jié)點(diǎn)收到簇C2的更新事件，立刻傳播給鄰居列表中的其他簇的節(jié)點(diǎn)，如圖9（c）所示，將其傳播給簇C1的簇首。簇C1的簇首再選擇鄰居節(jié)點(diǎn)進(jìn)行通信，如圖9（d）所示，將其他簇更新的哈希圖在本簇中傳播開(kāi)來(lái)，最后，簇C1、C2中所有的節(jié)點(diǎn)都擁有了更新的事件。

邊緣節(jié)點(diǎn)成為網(wǎng)關(guān)節(jié)點(diǎn)時(shí)，簇間傳播過(guò)程如圖10所示。圖10（a）中兩個(gè)分簇逐漸靠近，邊緣節(jié)點(diǎn)取得聯(lián)系。根據(jù)設(shè)定的規(guī)則，ID較小的邊緣節(jié)點(diǎn)成為網(wǎng)關(guān)節(jié)點(diǎn)，如圖10（b）所示，簇C2的邊緣節(jié)點(diǎn)將本簇的新事件同步至網(wǎng)關(guān)節(jié)點(diǎn)。網(wǎng)關(guān)節(jié)點(diǎn)再將事件傳播至其他分簇的節(jié)點(diǎn)，如圖10（c）所示。簇C1的簇首節(jié)點(diǎn)將收到的事件在本簇中傳播開(kāi)來(lái)，如圖10（d）所示，最終實(shí)現(xiàn)了簇C1、C2哈希圖的同步。

當(dāng)簇間不存在網(wǎng)關(guān)節(jié)點(diǎn)，無(wú)法借助網(wǎng)關(guān)節(jié)點(diǎn)直接進(jìn)行事件同步時(shí)，簇間傳播的總體思路為依靠移動(dòng)入簇的新節(jié)點(diǎn)，實(shí)現(xiàn)分簇間事件的同步。由于移動(dòng)，節(jié)點(diǎn)可能離開(kāi)原簇，加入新簇，在此過(guò)程中，節(jié)點(diǎn)可將自身存儲(chǔ)的原簇事件同步至新簇，同時(shí)，接收并存儲(chǔ)新簇的事件，這一過(guò)程實(shí)現(xiàn)了不同簇間事件的傳播。無(wú)網(wǎng)關(guān)節(jié)點(diǎn)的事件簇間傳播過(guò)程如圖11所示。

圖11（a）中簇C2的簇內(nèi)事件同步結(jié)束后，簇C2的某一成員節(jié)點(diǎn)由于移動(dòng)，脫離了簇C2的通信范圍，成為未分簇節(jié)點(diǎn)，如圖11（b）所示。該節(jié)點(diǎn)移動(dòng)至簇C1的通信范圍內(nèi)，加入了簇C1，并建立了新的鄰居視圖。根據(jù)FS-Gossip算法，該節(jié)點(diǎn)被鄰居節(jié)點(diǎn)以較大概率選中，發(fā)生Gossip同步，簇C1節(jié)點(diǎn)收到新事件后，對(duì)本地哈希圖進(jìn)行檢查，發(fā)現(xiàn)沒(méi)有本簇簇首的引用事件，則調(diào)用CH-First算法，沿著趨近簇首的傳播路徑，優(yōu)先傳播給簇首，如圖11（c）所示。簇C1的簇首再選擇鄰居節(jié)點(diǎn)進(jìn)行通信，將其他簇的事件在本簇中傳播開(kāi)來(lái)，最后，簇C1依靠簇C2移動(dòng)過(guò)來(lái)的節(jié)點(diǎn)，成功同步了簇C2的哈希圖，結(jié)果如圖11（d）所示。

4 安全性分析

本章討論模型的安全性，并具體分析模型如何防范聯(lián)盟鏈中幾種常見(jiàn)的安全攻擊。

a）雙花攻擊。在雙花攻擊中，惡意節(jié)點(diǎn)建立分叉，創(chuàng)建兩個(gè)新事件，使兩個(gè)事件引用同一個(gè)自父事件，如果兩個(gè)事件均能通過(guò)共識(shí)確認(rèn)，節(jié)點(diǎn)就成功發(fā)動(dòng)了雙花攻擊。在本文共識(shí)中，通過(guò)選舉極佳見(jiàn)證事件并投票，只有被超過(guò)2/3個(gè)節(jié)點(diǎn)檢查無(wú)誤并引用過(guò)的事件，才能達(dá)成共識(shí)。而雙花攻擊的兩個(gè)事件，最多只能有一條分叉被超過(guò)2/3的節(jié)點(diǎn)見(jiàn)證并通過(guò)共識(shí)，此時(shí)另一條分叉因引用節(jié)點(diǎn)少于1/3而無(wú)法通過(guò)共識(shí)，或兩條分叉均無(wú)法達(dá)到2/3的共識(shí)門(mén)檻。兩種情況下，惡意節(jié)點(diǎn)的雙花攻擊均無(wú)法成功實(shí)現(xiàn)。

b）女巫（Sybil）攻擊。女巫攻擊指惡意節(jié)點(diǎn)冒充多個(gè)身份，實(shí)現(xiàn)數(shù)量在分簇中占據(jù)優(yōu)勢(shì)，從而操縱共識(shí)。在本文模型中，為保障數(shù)據(jù)隱私與安全，假設(shè)模型應(yīng)用場(chǎng)景為聯(lián)盟鏈或私有鏈，節(jié)點(diǎn)加入網(wǎng)絡(luò)需進(jìn)行注冊(cè)和身份認(rèn)證，所有節(jié)點(diǎn)的公鑰公開(kāi)已知，身份可以相互驗(yàn)證，一個(gè)節(jié)點(diǎn)無(wú)法通過(guò)申請(qǐng)多個(gè)公鑰冒充多個(gè)節(jié)點(diǎn)，從而可以防范女巫攻擊。

c）拒絕服務(wù)（DoS）攻擊。在DoS攻擊中，攻擊者將大量信息發(fā)送給弱點(diǎn)節(jié)點(diǎn)，使該節(jié)點(diǎn)無(wú)法將有限的設(shè)備資源用于區(qū)塊鏈網(wǎng)絡(luò)，從而影響區(qū)塊鏈的性能，弱點(diǎn)節(jié)點(diǎn)通常為領(lǐng)導(dǎo)者節(jié)點(diǎn)。本文模型中共識(shí)算法沒(méi)有領(lǐng)導(dǎo)者，所有節(jié)點(diǎn)共同維護(hù)共識(shí)的正確進(jìn)行。即使攻擊者攻破某個(gè)節(jié)點(diǎn)，剩余節(jié)點(diǎn)也可以正常維持整個(gè)區(qū)塊鏈系統(tǒng)，進(jìn)而有效抵抗DoS攻擊。

d）針對(duì)領(lǐng)導(dǎo)者的攻擊。多出現(xiàn)于能預(yù)先確認(rèn)領(lǐng)導(dǎo)者的PBFT算法。惡意節(jié)點(diǎn)通過(guò)預(yù)知領(lǐng)導(dǎo)者是哪一節(jié)點(diǎn)，從而發(fā)動(dòng)攻擊，阻礙共識(shí)的正常進(jìn)行。在本文模型中，沒(méi)有領(lǐng)導(dǎo)者來(lái)主導(dǎo)共識(shí)。簇首節(jié)點(diǎn)僅對(duì)共識(shí)具有推動(dòng)作用，一旦失效可以進(jìn)行替換。同時(shí)，根據(jù)權(quán)值公式中的能力值影響因素，簇首是分簇內(nèi)性能較高的節(jié)點(diǎn)，具有應(yīng)對(duì)攻擊的防范能力。通過(guò)發(fā)布簇首選舉事件，驗(yàn)證并比較其他節(jié)點(diǎn)能力值的高低來(lái)選舉簇首，確保了選舉的公平性。

5 實(shí)驗(yàn)

本章從分簇?cái)?shù)量、活躍度、吞吐量、平均共識(shí)時(shí)延、FS-Gossip協(xié)議五個(gè)方面對(duì)模型的性能進(jìn)行測(cè)試，以此驗(yàn)證模型的可用性。

實(shí)驗(yàn)的硬件環(huán)境為一臺(tái)MacBook Air，處理器為八核Apple M1，內(nèi)存8 GB，軟件環(huán)境為Eclipse IDE 4.24.0。為模擬多個(gè)節(jié)點(diǎn)建立分簇拓?fù)洳?chuàng)建新事件、同步哈希圖，實(shí)驗(yàn)采用JAVA多線程技術(shù)，每個(gè)線程代表一個(gè)節(jié)點(diǎn)，線程與線程之間可以相互通信，以傳遞參數(shù)。

5.1 分簇?cái)?shù)量與模型性能的關(guān)系

本實(shí)驗(yàn)測(cè)試不同分簇?cái)?shù)量對(duì)模型性能的影響，探究當(dāng)節(jié)點(diǎn)總數(shù)固定時(shí)，劃分為多少個(gè)簇才能使全網(wǎng)總吞吐量到達(dá)最大值。本文對(duì)比的區(qū)塊鏈模型為Hashgraph與Teegraph。Teegraph模型改進(jìn)了Hashgraph，引入可信執(zhí)行環(huán)境，節(jié)點(diǎn)在此環(huán)境下無(wú)法發(fā)起雙花攻擊，從而無(wú)須多輪次的見(jiàn)證檢查雙花事件，加速了共識(shí)，可應(yīng)用于移動(dòng)自組網(wǎng)區(qū)塊鏈。實(shí)驗(yàn)假設(shè)全網(wǎng)共有60個(gè)節(jié)點(diǎn)，且每個(gè)簇的節(jié)點(diǎn)數(shù)量相同，每個(gè)節(jié)點(diǎn)每隔400 ms創(chuàng)建一個(gè)新事件，最后根據(jù)各個(gè)分簇的吞吐量值，累計(jì)求和得到全網(wǎng)的總吞吐量。如果分簇?cái)?shù)量不能整除，就取近似的整數(shù)值，仍保證節(jié)點(diǎn)總數(shù)為60。當(dāng)分簇?cái)?shù)量為15時(shí)，每個(gè)簇僅有4個(gè)節(jié)點(diǎn)，是進(jìn)行拜占庭共識(shí)的最少節(jié)點(diǎn)數(shù)，故當(dāng)全網(wǎng)節(jié)點(diǎn)總數(shù)為60時(shí)，最大分簇?cái)?shù)量為15。分簇?cái)?shù)量決定了簇的大小，進(jìn)而會(huì)影響模型的性能。

實(shí)驗(yàn)結(jié)果如圖12所示，本文模型的吞吐量始終高于Hashgraph，平均提高了約32.2%，但略低于Teegraph，僅下降了3.8%。原因在于Teegraph沒(méi)有設(shè)計(jì)不同共識(shí)組節(jié)點(diǎn)的管理機(jī)制與Gossip協(xié)議的優(yōu)化方法，主要研究共識(shí)層算法，本文引入了分簇節(jié)點(diǎn)管理、事件傳播管理，且節(jié)點(diǎn)未裝備可信執(zhí)行環(huán)境，這些都會(huì)增加一定的共識(shí)開(kāi)銷(xiāo)，但本文算法性能只是略有下降，且解決了Teegraph沒(méi)有考慮的節(jié)點(diǎn)與事件管理問(wèn)題。實(shí)驗(yàn)結(jié)果也可以看出，模型存在最佳分簇?cái)?shù)，使全網(wǎng)總吞吐量達(dá)到最大值，當(dāng)實(shí)驗(yàn)的分簇?cái)?shù)量為10個(gè)時(shí)，全網(wǎng)總吞吐量達(dá)到最高值，為每秒140個(gè)事件。這一結(jié)論可為設(shè)計(jì)具體應(yīng)用提供參考。

5.2 活躍度與模型性能

本實(shí)驗(yàn)測(cè)試節(jié)點(diǎn)活躍度對(duì)模型性能的影響，設(shè)置了多組不同的創(chuàng)建事件頻率，記錄平均時(shí)延，實(shí)驗(yàn)結(jié)果如圖13所示?？梢钥闯觯录?chuàng)建間隔越長(zhǎng)，節(jié)點(diǎn)產(chǎn)生新事件頻率越低，共識(shí)越慢，時(shí)延越高，本文提出的確定極佳事件快速共識(shí)機(jī)制的時(shí)延增速慢于Hashgraph，略高于Teegraph。本文通過(guò)節(jié)點(diǎn)計(jì)算能力值選舉簇首，而能力值公式中除了電池能量、相對(duì)移動(dòng)性等客觀因素外，還考慮了活躍度這一主觀因素，能夠激勵(lì)節(jié)點(diǎn)提高活躍度，增加創(chuàng)建事件頻率，加快共識(shí)進(jìn)程，因此時(shí)延性能要明顯好于Hashgraph，在考慮節(jié)點(diǎn)與事件管理功能的前提下與Teegraph基本相同。

5.3 吞吐量測(cè)試

吞吐量是評(píng)價(jià)系統(tǒng)性能的重要指標(biāo)之一，體現(xiàn)了單位時(shí)間內(nèi)達(dá)成共識(shí)確認(rèn)的事件的多少，吞吐量越大，系統(tǒng)的處理能力越強(qiáng)。本實(shí)驗(yàn)測(cè)試改進(jìn)后共識(shí)機(jī)制的吞吐量，并與Hashgraph、Teegraph進(jìn)行對(duì)比，假設(shè)每個(gè)節(jié)點(diǎn)創(chuàng)建新事件的頻率不變，實(shí)驗(yàn)結(jié)果如圖14所示。從圖中可以看出，本文共識(shí)算法的吞吐量高于Hashgraph，與Teegraph不相上下，原因是本文提出的共識(shí)算法在節(jié)點(diǎn)不裝配可信執(zhí)行環(huán)境的情況下，確保安全性的同時(shí)縮短了共識(shí)輪次，簡(jiǎn)化了共識(shí)流程，增大有效Gossip的發(fā)生概率，提高系統(tǒng)吞吐量。

5.4 共識(shí)時(shí)延測(cè)試

本實(shí)驗(yàn)測(cè)試改進(jìn)后共識(shí)機(jī)制的時(shí)延，并與Hashgraph、Teegraph進(jìn)行對(duì)比。共識(shí)時(shí)延用來(lái)評(píng)價(jià)事件從產(chǎn)生到完成事件確認(rèn)所經(jīng)歷的時(shí)長(zhǎng)，一些特殊應(yīng)用對(duì)共識(shí)時(shí)延要求很高，對(duì)交易確認(rèn)速度比較敏感。共識(shí)時(shí)延越低，代表交易確認(rèn)越快，模型越高效。實(shí)驗(yàn)結(jié)果如圖15所示。從圖中可以看出，本文共識(shí)算法的時(shí)延明顯低于Hashgraph，僅略高于Teegraph。這是由于Hashgraph共識(shí)需經(jīng)過(guò)虛擬投票、統(tǒng)計(jì)投票、確定聲望三個(gè)階段，事件至少經(jīng)過(guò)三輪才能達(dá)成共識(shí)，增加了時(shí)延；Teegraph因?yàn)檠b入可信執(zhí)行環(huán)境，將共識(shí)門(mén)檻由2/3降至1/2，不再劃分輪次，提升了共識(shí)速度。本文共識(shí)步驟較為簡(jiǎn)潔，最快經(jīng)過(guò)兩輪就能達(dá)成共識(shí)，雖然未通過(guò)裝備可信執(zhí)行環(huán)境來(lái)減輕節(jié)點(diǎn)負(fù)擔(dān)，且對(duì)節(jié)點(diǎn)與事件的管理也帶來(lái)一些性能損耗，但時(shí)延相比Teegraph僅略有增加。

5.5 FS-Gossip測(cè)試

本文設(shè)計(jì)事件同步率這一變量，來(lái)評(píng)價(jià)Gossip協(xié)議的通信效果。圖中橫坐標(biāo)代表全局哈希圖中事件的數(shù)目，縱坐標(biāo)事件同步率體現(xiàn)了節(jié)點(diǎn)對(duì)這些事件的平均存儲(chǔ)比例。隨著節(jié)點(diǎn)擴(kuò)展哈希圖，產(chǎn)生的事件越來(lái)越多，全網(wǎng)節(jié)點(diǎn)平均存儲(chǔ)事件的數(shù)目與當(dāng)前全局哈希圖所擁有的事件數(shù)目作百分比，就得到事件同步率。實(shí)驗(yàn)分別對(duì)兩種情況進(jìn)行測(cè)試，一種情況為簇內(nèi)節(jié)點(diǎn)間距較小，任一節(jié)點(diǎn)均處于其他節(jié)點(diǎn)的通信范圍內(nèi)，節(jié)點(diǎn)間可以互相通信；另一種情況為簇內(nèi)節(jié)點(diǎn)間距較大，每個(gè)節(jié)點(diǎn)擁有自身的鄰居列表，不相鄰的節(jié)點(diǎn)傳遞信息需借助中間節(jié)點(diǎn)，并設(shè)置了一種拓?fù)淝闆r進(jìn)行實(shí)驗(yàn)。節(jié)點(diǎn)間距較小時(shí)，實(shí)驗(yàn)結(jié)果如圖16所示。從圖中可以看出，在6個(gè)和9個(gè)節(jié)點(diǎn)兩種情況下，產(chǎn)生的事件數(shù)相等時(shí)，本文提出的FS-Gossip算法更容易選擇高信息收益的鄰居節(jié)點(diǎn)進(jìn)行通信，平均事件同步率均高于隨機(jī)Gossip算法。

節(jié)點(diǎn)間距較大時(shí)，設(shè)置了兩種拓?fù)淝闆r進(jìn)行實(shí)驗(yàn)，圖17（a）展示了簇內(nèi)有6個(gè)節(jié)點(diǎn)時(shí)的一種拓?fù)淝闆r，由于節(jié)點(diǎn)間距離較遠(yuǎn)，節(jié)點(diǎn)2只能與節(jié)點(diǎn)1、5發(fā)生通信，簇內(nèi)其他節(jié)點(diǎn)不在節(jié)點(diǎn)2通信范圍內(nèi)，故無(wú)法與之直接通信。同理，圖17（b）展示了簇內(nèi)有9個(gè)節(jié)點(diǎn)時(shí)一種可能的拓?fù)淝闆r。

實(shí)驗(yàn)結(jié)果如圖18所示。從圖中可以看出，在6個(gè)節(jié)點(diǎn)和9個(gè)節(jié)點(diǎn)兩種情況下，本文提出的FS-Gossip算法增加了信息收益大的鄰居節(jié)點(diǎn)的選擇概率，事件同步率均高于隨機(jī)Gossip算法。

6 結(jié)束語(yǔ)

本文提出一種基于哈希圖的移動(dòng)自組網(wǎng)區(qū)塊鏈模型，解決了移動(dòng)自組網(wǎng)環(huán)境下，由于網(wǎng)絡(luò)不斷發(fā)生分裂與合并，導(dǎo)致事件同步不及時(shí)、影響共識(shí)的問(wèn)題。模型首先依據(jù)地理位置，對(duì)全網(wǎng)節(jié)點(diǎn)進(jìn)行分簇，并選舉簇首，設(shè)計(jì)了特殊的事件結(jié)構(gòu)，由簇首統(tǒng)計(jì)并傳播簇內(nèi)節(jié)點(diǎn)數(shù)量這一影響共識(shí)的關(guān)鍵參數(shù)，解決了由于節(jié)點(diǎn)數(shù)量不明確導(dǎo)致簇內(nèi)共識(shí)無(wú)法進(jìn)行的問(wèn)題；其次，提出FS-Gossip協(xié)議，通過(guò)在Hello消息中增加字段，計(jì)算信息收益，篩選鄰居節(jié)點(diǎn)，提高了事件同步效率；最后，對(duì)哈希圖中復(fù)雜的共識(shí)機(jī)制進(jìn)行改進(jìn)，將原來(lái)的三步共識(shí)縮減為兩步，在確保安全性不變的同時(shí)，提升了共識(shí)速度，降低了時(shí)延。實(shí)驗(yàn)結(jié)果表明，本文模型在兼具安全性的同時(shí)，提高了吞吐量與事件同步率，降低了時(shí)延。

參考文獻(xiàn)：

[1]李少謙，蘭嵐.無(wú)線Ad hoc網(wǎng)絡(luò)技術(shù)［J］.中興通信技術(shù)，2002（1）：9-12.（Li Shaoqian，Lan Lan.Wireless Ad hoc network technology［J］.ZTE Communications，2002（1）：9-12.）

［2]宋建華，洪帆，何曉冰.移動(dòng)Ad hoc網(wǎng)的典型網(wǎng)絡(luò)攻擊與防范［J］.微計(jì)算機(jī)應(yīng)用，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]劉懿中，劉建偉，張宗洋，等.區(qū)塊鏈共識(shí)機(jī)制研究綜述［J］.密碼學(xué)報(bào)，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]黃建華，黃雪茹，季鈺翔，等.一種基于雙鏈模型的分區(qū)共識(shí)協(xié)議［J］.計(jì)算機(jī)應(yīng)用研究，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的多源快速數(shù)據(jù)分發(fā)技術(shù)研究 ［D］.湖南：國(guó)防科技大學(xué)，2009.（Ma Xingkong.Research of Gossip-based multisource flash data dissemination technology［D］.Hunan：National University of Defense Technology，2009.）

［16]張娓娓，范訓(xùn)禮，房鼎益.基于模糊理論的P2P流媒體節(jié)點(diǎn)選擇算法［J］.計(jì)算機(jī)工程，2009，35（23）：88-90.（Zhang Weiwei，F(xiàn)an Xunli，F(xiàn)ang Dingyi.A P2P streaming media node selection algorithm based on fuzzy theory［J］.Computer Engineering，2009，35（23）：88-90.）

［17]田振興，代杰.基于改進(jìn)Gossip協(xié)議的數(shù)據(jù)同步設(shè)計(jì)［J］.指揮信息系統(tǒng)與技術(shù)，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]張奇文，王志強(qiáng)，張逸謙.基于Gossip協(xié)議的信任收集共識(shí)算法研究［J］.計(jì)算機(jī)科學(xué)，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]徐晶晶，張欣慧，許必宵，等.無(wú)線傳感器網(wǎng)絡(luò)分簇算法綜述［J］.計(jì)算機(jī)科學(xué)，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]周藝華，賈立圓，賈玉欣，等.基于信譽(yù)度的Hashgraph共識(shí)算法［J］.計(jì)算機(jī)應(yīng)用研究，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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（62076094）

作者簡(jiǎn)介：宮在為（2000-），女，黑龍江密山人，碩士，主要研究方向?yàn)閰^(qū)塊鏈；黃建華（1963-），男（通信作者），湖南懷化人，副教授，博士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息安全（jhhuang@ecust.edu.cn）；顧彬（1999-），男，上海人，碩士，主要研究方向?yàn)閰^(qū)塊鏈；寧宇豪（1998-），男，山西運(yùn)城人，碩士，主要研究方向?yàn)閰^(qū)塊鏈；張文韜（1999-），男，浙江紹興人，碩士，主要研究方向?yàn)閰^(qū)塊鏈．