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

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

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

中圖分類號：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 引言

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

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

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

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

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

1 相關(guān)工作

1.1 分區(qū)共識

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

1.2 改進Gossip協(xié)議

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

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

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

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

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

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

2.2 哈希圖

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

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

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

2.3 分簇算法

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

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

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

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

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

a）節(jié)點ID。移動自組網(wǎng)中每個節(jié)點具有唯一的標識，節(jié)點i的ID記為IDi。

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

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

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

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

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

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

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

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

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

h）相對移動性。節(jié)點相較于附近節(jié)點，移動性的強弱，記為Rm（relative mobility）。

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

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

Rm=1NCR（v）（3）

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

能力值計算公式為

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

即

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

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

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

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

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

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

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

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

算法1 簇首更換算法

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

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

while （node CurrentCH fails） do // 節(jié)點CurrentCH表示當前簇首節(jié)點

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

Call clustering algorithm ; /* 如果當前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é)點的ID

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

end if

end while

2.4 FS- Gossip協(xié)議

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

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

b） 基于拉（pull）的方法，節(jié)點A向節(jié)點B主動請求，節(jié)點B將信息發(fā)給節(jié)點A，A進行更新；

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

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

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

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

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

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

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

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

將k代入概率p的計算公式：

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

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

ω=0?? tlive>bounduppertlive

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

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

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

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

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

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

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

bound=（1+eventrate）tround（11）

2.5 共識算法

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

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

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

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

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

3 傳播機制

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

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

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

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

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

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

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

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

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

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

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

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

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

end while

3.2 簇間傳播機制

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

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

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

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

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

4 安全性分析

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

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

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

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

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

5 實驗

本章從分簇數(shù)量、活躍度、吞吐量、平均共識時延、FS-Gossip協(xié)議五個方面對模型的性能進行測試，以此驗證模型的可用性。

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

5.1 分簇數(shù)量與模型性能的關(guān)系

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

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

5.2 活躍度與模型性能

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

5.3 吞吐量測試

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

5.4 共識時延測試

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

5.5 FS-Gossip測試

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

節(jié)點間距較大時，設(shè)置了兩種拓撲情況進行實驗，圖17（a）展示了簇內(nèi)有6個節(jié)點時的一種拓撲情況，由于節(jié)點間距離較遠，節(jié)點2只能與節(jié)點1、5發(fā)生通信，簇內(nèi)其他節(jié)點不在節(jié)點2通信范圍內(nèi)，故無法與之直接通信。同理，圖17（b）展示了簇內(nèi)有9個節(jié)點時一種可能的拓撲情況。

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

6 結(jié)束語

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

參考文獻：

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

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

［16]張娓娓，范訓禮，房鼎益.基于模糊理論的P2P流媒體節(jié)點選擇算法［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]田振興，代杰.基于改進Gossip協(xié)議的數(shù)據(jù)同步設(shè)計［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]張奇文，王志強，張逸謙.基于Gossip協(xié)議的信任收集共識算法研究［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]徐晶晶，張欣慧，許必宵，等.無線傳感器網(wǎng)絡分簇算法綜述［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-），女，黑龍江密山人，碩士，主要研究方向為區(qū)塊鏈；黃建華（1963-），男（通信作者），湖南懷化人，副教授，博士，主要研究方向為計算機網(wǎng)絡與信息安全（jhhuang@ecust.edu.cn）；顧彬（1999-），男，上海人，碩士，主要研究方向為區(qū)塊鏈；寧宇豪（1998-），男，山西運城人，碩士，主要研究方向為區(qū)塊鏈；張文韜（1999-），男，浙江紹興人，碩士，主要研究方向為區(qū)塊鏈．