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

華東理工大學 信息科學與工程學院，上海 200237

移動自組網（mobile ad hoc networks，MANET）是一種具有自組織能力、可快速部署的特殊類型物聯(lián)網（Internet of things，IoT），它無需固定基礎設施的支持，在軍事戰(zhàn)場、緊急救援和環(huán)境勘探等特殊環(huán)境中應用前景廣闊。在執(zhí)行任務的過程中，MANET 的節(jié)點之間需要通過無線信道傳輸數(shù)據(jù)和通過操作指令進行協(xié)同，這些數(shù)據(jù)和操作指令存在多種安全風險且容易受到攻擊。因此，維護MANET數(shù)據(jù)的機密性、完整性和真實性顯得非常重要。

區(qū)塊鏈是一種在計算機網絡節(jié)點之間共享信息的分布式數(shù)據(jù)庫，它以區(qū)塊的形式組織搜集的信息，通過密碼學將區(qū)塊之間鏈接在一起，以確保數(shù)據(jù)的不變性。作為一項新興的技術，區(qū)塊鏈為分布式系統(tǒng)提供了去中心化和防篡改的能力，確保了數(shù)據(jù)的真實性和完整性。一些學者嘗試利用區(qū)塊鏈來解決物聯(lián)網的安全問題。Islam 等人[1]提出使用基于區(qū)塊鏈的智能合約，實現(xiàn)了移動節(jié)點間機器學習模型的安全共享；Abishu[2]與Hassija[3]等學者提出將交易數(shù)據(jù)上鏈，實現(xiàn)移動節(jié)點間以及移動節(jié)點與固定節(jié)點間安全的能源交易。

然而，由于MANET 的移動性會引發(fā)網絡拓撲的動態(tài)變化，將區(qū)塊鏈與MANET 相結合面臨不少挑戰(zhàn)。Laube 等人[4]首次探討了移動性引發(fā)的網絡拓撲變化問題，提出了應對MANET分裂和合并問題的解決方案，從理論上證明了在MANET中應用區(qū)塊鏈技術的可行性。但該方案采用被動的方式檢測網絡拓撲的變化，存在效率較低下、網絡延遲等問題，并且未就檢測網絡分裂提出有效的解決方案。Block-Graph[5-6]將基于有向無環(huán)圖（directed acyclic graph，DAG）的區(qū)塊鏈模型應用于MANET，重新設計了區(qū)塊的數(shù)據(jù)結構和Raft共識算法，解決了傳統(tǒng)區(qū)塊鏈在MANET 分裂和合并下產生的問題，保證了數(shù)據(jù)的正確性與完整性。但是該模型的共識時延易受到節(jié)點數(shù)量的影響，在大規(guī)模的集群下共識效率不高。雖然以上工作取得一些進展，但是將區(qū)塊鏈應用于MANET 仍然存在以下問題需要解決。首先，不同類型的任務往往要求移動節(jié)點或分散或聚集地開展工作，需設計高效的分簇算法，使得節(jié)點快速分簇的同時有效控制簇內節(jié)點的數(shù)量；其次，受到環(huán)境和任務變化等因素的影響，網絡的結構將進行分裂和合并等動態(tài)調整，而網絡的分裂將引發(fā)區(qū)塊鏈的分叉，在網絡合并后需合理地處理這些分叉；最后，節(jié)點的通信信號易受到山體、樹木和建筑物等大型物體的干擾，在此環(huán)境下，節(jié)點間傳遞區(qū)塊所需的控制和驗證信息極易丟失。

針對以上問題，本文解決問題的思路是采用DAG結構來適配移動性引發(fā)的網絡拓撲的變化，以解決區(qū)塊鏈分叉問題；通過簇首控制簇節(jié)點密度，以限制入簇節(jié)點數(shù)量，確保簇的性能；簡化出塊和驗證流程，減小數(shù)據(jù)丟失對區(qū)塊上鏈所帶來的影響。提出一種基于DAG 結構的系統(tǒng)模型DAGGraph，以有效地控制每個簇的規(guī)模，提高分簇的速度，實現(xiàn)網絡合并后區(qū)塊鏈分支的安全恢復，通過簡化上鏈流程提高共識速度，增加系統(tǒng)的吞吐量和魯棒性。本文的貢獻如下：

（1）提出簇節(jié)點密度（數(shù)量）限制算法，有效地解決了一個簇的節(jié)點數(shù)量不受控增加所引發(fā)的性能下降問題。

（2）針對網絡分裂和合并引發(fā)的網絡拓撲的變化，提出基于簇首間數(shù)據(jù)同步的區(qū)塊恢復算法，在網絡合并后由原簇首交換并同步產生的區(qū)塊分支，實現(xiàn)對區(qū)塊分支的恢復，以保留所有節(jié)點產生的合法區(qū)塊。

（3）提出一種簡化的區(qū)塊上鏈算法，簡化了區(qū)塊的上鏈流程，節(jié)點僅需對收到的區(qū)塊進行本地驗證即可完成上鏈操作，增強了系統(tǒng)的健壯性。

1 相關工作

分簇算法可以解決MANET 中節(jié)點資源開銷大、可擴展性不高等問題。分簇算法將平面網絡結構中鄰近的節(jié)點組成一個簇，一個簇包含一個簇首和若干個簇成員節(jié)點，簇首與簇成員協(xié)同執(zhí)行任務。運行分簇算法的節(jié)點周期性地發(fā)送控制信息，這些控制信息用來進行簇首選舉、節(jié)點入簇和節(jié)點移動等操作。最小ID分簇算法[7]是較早提出的分簇算法，該算法要求每個節(jié)點擁有唯一的ID，在網絡初始化階段，節(jié)點周期性地向其他節(jié)點廣播自己的ID，節(jié)點通過比較收到的ID，選擇ID 最小的節(jié)點作為網絡的簇首。最小ID 分簇算法的一個顯著特點是算法的收斂性高，實現(xiàn)簡單。陳志軍等人[8]對最小ID分簇算法進行了改進，將剩余電量和節(jié)點相對移動速度作為簇首選舉的參考因素，使節(jié)點能耗更均衡，網絡拓撲更穩(wěn)定。受到外部環(huán)境因素的影響，在實際應用中，節(jié)點的移動方向、速度等特性在一定程度上具有某種規(guī)律。通過設計合理的數(shù)學模型，可以預測節(jié)點在某一時間段內的移動特性，降低分簇算法的開銷。宋人杰等人[9]指出移動節(jié)點具有分組移動的特性，通過計算得出節(jié)點的移動特性并進行分簇，同時將節(jié)點性能作為簇首選舉的參考因素以提高系統(tǒng)性能。陳宇等人[10]基于衛(wèi)星節(jié)點運行軌跡的可預測性，將簇的初始化階段交由可信的地面終端完成，簡化了分簇算法的復雜度，提高了網絡的穩(wěn)定性。吳振華等人[11]根據(jù)車輛移動位置的可預測性，按路段將城市道路劃分成簇，通過車輛節(jié)點的實時位置預測移動趨勢，降低了分簇算法的路由發(fā)現(xiàn)及分簇的開銷。MANET 的節(jié)點基于無線方式通信，存在消息泄露風險，網絡拓撲易受到攻擊。崔朝陽等人[12]根據(jù)MANET 的特點，提出安全分簇算法。該算法通過證書交換，確?？尚殴?jié)點加入網絡，通過協(xié)商會話密鑰，完成對信息的加密，提高了分簇算法的安全性。

基于DAG 的區(qū)塊鏈可以實現(xiàn)區(qū)塊并發(fā)寫入，且能較好地解決由網絡分裂引起的區(qū)塊鏈分叉問題，受到研究人員的廣泛關注。使用DAG結構的區(qū)塊鏈項目主要有Nano（https://nano.org/en/whitepaper）、Byteball（https://byteball.org/Byteball.pdf）、IOTA（http://tanglereport.com/wp-content/uploads/2018/01/IOTA_Whitepaper.pdf）、DagCoin（https://dagcoin.org/whitepaper.pdf）等。DAG 賬本的每一個子單元可以引用驗證多個父單元，一個父單元也可以被多個子單元驗證，這種驗證關系在提高交易確認速度的基礎上確保了DAG賬本的安全性和可靠性。為了解決由多分支合并引起的交易沖突問題，GHOST[13]提出主鏈選擇協(xié)議，對于兩個沖突的交易，將位于主鏈上的交易視為有效。然而GHOST協(xié)議將丟棄主鏈以外的交易，造成對算力的浪費。Conflux[14]和Inclusive[15]基于GHOST主鏈選擇協(xié)議，將節(jié)點產生的所有交易都視為DAG賬本的一部分，并根據(jù)主鏈對交易進行排序，解決了交易沖突問題。安全性是移動自組網所面臨的又一個問題，針對節(jié)點的惡意攻擊會給MANET帶來不可預測的風險和損失。其攻擊類型主要包括物理攻擊、惡意竊聽、洪泛攻擊[16]、拒絕服務攻擊、雙花攻擊和女巫攻擊[17]等。區(qū)塊鏈具有分布式、防篡改等特點，但與移動自組網相結合的區(qū)塊鏈也容易受到來自外部和內部的攻擊。一些學者對于如何提高區(qū)塊鏈系統(tǒng)自身的安全性進行了研究。李忠誠等人[18]根據(jù)區(qū)塊鏈中誠實節(jié)點與惡意節(jié)點之間的博弈，提出了一種激勵和押金機制。規(guī)定每個參與驗證的節(jié)點都需要繳納押金，參與共識的誠實節(jié)點將按繳納的押金比例獲得獎勵，同時惡意節(jié)點會被扣除押金，以此激勵節(jié)點理性共識，限制惡意行為。季鈺翔等人[19]引入信任度評估機制，通過對鄰居節(jié)點行為的監(jiān)督，以有效檢測惡意節(jié)點，同時引入工作量證明和押金機制來限制女巫攻擊，保證區(qū)塊鏈網絡的安全性。英特爾軟件保護擴展（Intel software guard extensions，SGX）[20]利用可信硬件提供安全容器，以確保安全容器中加載的代碼和數(shù)據(jù)不能被外界篡改，提高了區(qū)塊鏈的安全性。

在移動自組網環(huán)境中，節(jié)點的頻繁移動會引起網絡拓撲變化，當節(jié)點間的距離超出通信范圍時，網絡會分裂；節(jié)點連接恢復后，網絡將合并。分簇算法增加了MANET 組網的靈活性，提高了網絡的性能，然而節(jié)點間靈活的組網能力也為區(qū)塊鏈在MANET上的應用提出了不小的挑戰(zhàn)。傳統(tǒng)的單鏈式區(qū)塊鏈根據(jù)最長鏈原則，將丟棄由網絡分裂產生的分支，從而造成正常的數(shù)據(jù)丟失。區(qū)塊圖[5-6]將DAG結構應用于MANET，為區(qū)塊鏈應對網絡分裂和合并帶來的問題提供了解決方案。當網絡分裂成兩個子網后DAG分叉，各子網在自己的分叉上獨立地產生區(qū)塊并上鏈；當網絡合并后，啟動區(qū)塊恢復程序，恢復由其他子網產生的區(qū)塊。區(qū)塊圖基于每個子網中的領導者節(jié)點完成日志復制和區(qū)塊恢復等過程，然而區(qū)塊圖并未就網絡的分裂和合并等拓撲變化給出具體的檢測方案。Laube 等人[4]提出了一種被動檢測網絡拓撲變化的方案，指出網絡的出塊速度應根據(jù)節(jié)點的數(shù)量動態(tài)變化，并給出了優(yōu)化的方向。然而基于被動的方式可能造成網絡延遲。

2 DAGGraph

2.1 系統(tǒng)模型

節(jié)點的移動性會引發(fā)網絡拓撲的動態(tài)變化，如何確保使用區(qū)塊鏈運行的任何應用在移動自組織網絡中保持一致是本文需要解決的關鍵問題。移動自組網的特點是移動節(jié)點間連接的穩(wěn)定性通常不及固定節(jié)點，節(jié)點的無線通信范圍有限且易受環(huán)境因素的影響，節(jié)點因執(zhí)行任務移動到不同位置或外部干擾會造成連接中斷，引發(fā)網絡分裂，形成幾個稱為簇的獨立分區(qū)，分區(qū)內的節(jié)點可以相互通信，但分區(qū)之間彼此不能直接通信。當任務發(fā)生變化后，分裂的簇又會逐漸靠近，合并成一個網絡。

區(qū)塊鏈通常假設網絡是穩(wěn)定的并且具有良好的可用性。這些假設不適用于可能出現(xiàn)網絡分區(qū)的移動自組網，因為網絡的分裂和合并都會引發(fā)網絡拓撲變化，給區(qū)塊鏈網絡維持數(shù)據(jù)一致性帶來挑戰(zhàn)。在部署區(qū)塊鏈的移動自組網中，當網絡出現(xiàn)分區(qū)時，不同的簇之間不能直接通信，全網節(jié)點無法達成整體共識。要確保網絡分區(qū)后區(qū)塊鏈能繼續(xù)提供服務，不同的簇會獨立共識以延展區(qū)塊鏈，從而引發(fā)區(qū)塊鏈分叉。當網絡再次合并時，要確保數(shù)據(jù)保持可用和一致，傳統(tǒng)區(qū)塊鏈會將多余的分支進行修剪，僅保留最長鏈分支。刪除分支會刪除許多有用的數(shù)據(jù)，引起數(shù)據(jù)丟失，這是不接受的。

針對以上問題，本文采用DAG 結構來適配移動性引發(fā)的網絡拓撲的變化，以保留網絡分裂階段各簇獨立產生的區(qū)塊鏈分支，并通過簇首處理區(qū)塊的恢復和同步問題，提出一種基于DAG 結構的系統(tǒng)模型DAGGraph，如圖1所示。

圖1 DAGGraph系統(tǒng)模型Fig.1 DAGGraph system model

圖1 反映了網絡運行過程中網絡拓撲的動態(tài)變化，網絡分裂后形成多個簇（分區(qū)），由于通信距離有限，各簇間無法直接通信。每一個簇由一個簇首和多個成員節(jié)點組成，同一簇內的節(jié)點具有相同的出塊權，均可在屬于本簇的DAG 分支上產生區(qū)塊。如圖1所示，節(jié)點移動后網絡中產生A與B兩個簇，簇A的節(jié)點和簇B 的節(jié)點在各自的DAG 分支上產生區(qū)塊，兩個分支可在網絡合并后由舊簇首恢復給所有成員節(jié)點，同時由新簇首負責生成合并塊以收斂此前產生的DAG分支。

系統(tǒng)基于私有鏈運行，可信證書授權機構（certificate authority，CA）為每一個參與節(jié)點頒發(fā)證書。節(jié)點之間通過互換各自的證書，相互驗證，未被授予證書的節(jié)點將不被允許加入系統(tǒng)。節(jié)點間的消息傳輸采用會話密鑰加密傳輸，會話密鑰采用密鑰交換技術協(xié)商產生，以確保安全性。

本文將區(qū)塊鏈與移動自組網相結合需要解決的問題簡化為三個：分簇管理問題、共識問題和區(qū)塊恢復問題。分簇管理主要基于分簇算法形成簇結構，處理網絡初始化和維護簇結構，通過引入加密機制支持每個加入簇的節(jié)點與鄰居節(jié)點協(xié)商會話密鑰，確保數(shù)據(jù)安全傳輸。區(qū)塊管理模塊由共識模塊和區(qū)塊恢復模塊組成，其中共識模塊允許每個簇獨立地產生區(qū)塊，區(qū)塊恢復模塊負責網絡合并后恢復由不同簇產生的區(qū)塊。

2.2 分簇管理

MANET 被廣泛應用于搶險救災、地質勘探和水文觀測等領域，這些應用場景往往根據(jù)任務形式和物理環(huán)境的不同，要求節(jié)點分散地開展任務。然而受到通信距離的限制，MANET 節(jié)點的分布不宜過于松散，節(jié)點間的遠距離通信造成網絡的不穩(wěn)定連接將頻繁引發(fā)數(shù)據(jù)丟包和數(shù)據(jù)包重傳，大大增加通信能耗。利用分簇算法，將松散分布的節(jié)點聚集成簇，可在一定程度上緩解此類問題。然而，現(xiàn)有的分簇算法大都基于地理位置對集群進行分簇，若某一位置的節(jié)點數(shù)量過多，極易造成一個簇內的節(jié)點密度過高，節(jié)點間的頻段干擾以及帶寬占用等問題將嚴重影響節(jié)點間的通信效率。因此，本文設計了一種高效的分簇管理機制，包括分簇和簇首選舉模塊、簇結構維護模塊、拓撲變更檢測模塊、會話密鑰協(xié)商模塊等。該機制以簇的形式組織MANET節(jié)點，以發(fā)揮MANET 節(jié)點的團隊協(xié)作優(yōu)勢，提高工作效率，降低通信能耗。

如圖2所示，分簇管理機制中的節(jié)點包含五種節(jié)點狀態(tài)：未定狀態(tài)、游離狀態(tài)、成員狀態(tài)、簇首狀態(tài)、簇首隱藏狀態(tài)。其中未定狀態(tài)為每個節(jié)點啟動后的初始狀態(tài)；游離狀態(tài)表示節(jié)點未發(fā)現(xiàn)鄰居節(jié)點。簇首選舉基于加權分簇算法，該算法綜合考慮了節(jié)點性能、網絡帶寬、剩余電量等因素，選舉綜合素質最高的節(jié)點進入簇首狀態(tài)。簇內的節(jié)點狀態(tài)為成員狀態(tài)，處于簇首狀態(tài)和成員狀態(tài)的節(jié)點動態(tài)維護簇成員表。此外，為了減小網絡通信負擔，本文為簇首設計了控制簇內節(jié)點數(shù)量的機制，當簇內節(jié)點數(shù)量過多，簇首轉為隱藏狀態(tài)，此時簇首不再允許新節(jié)點加入簇。

圖2 節(jié)點狀態(tài)轉換圖Fig.2 Node state transition

基于節(jié)點靈活移動的特性，分簇管理的任務如下：網絡初始化、節(jié)點加入、節(jié)點退出、節(jié)點移動等。為了更加高效地檢測網絡拓撲變化，本文還定義了兩種拓撲狀態(tài)：拓撲變化狀態(tài)、拓撲穩(wěn)定狀態(tài)。初始階段節(jié)點都處于拓撲變化狀態(tài)，待節(jié)點檢測到分簇完成后轉為拓撲穩(wěn)定狀態(tài)。

2.2.1 網絡初始化

網絡初始化即簇結構的初始化：將網絡中物理距離接近的節(jié)點劃分成包含一個簇首和多個成員節(jié)點的簇，網絡初始化流程如圖3所示。

圖3 網絡初始化流程Fig.3 Network initialization process

為完成簇結構的初始化，節(jié)點需向全網廣播Hello消息，Hello消息包含節(jié)點ID、節(jié)點證書、節(jié)點權值、節(jié)點狀態(tài)、時間戳和消息驗證碼。其中節(jié)點權值W綜合考慮了節(jié)點的處理器性能A、網絡帶寬M和剩余電量E等因素，權值計算公式為：

當節(jié)點收到來自其他節(jié)點的Hello 消息后，根據(jù)消息驗證碼和節(jié)點證書來驗證節(jié)點的身份和消息的真實性。消息驗證通過后，根據(jù)節(jié)點發(fā)出的Hello 消息信號強度計算節(jié)點間的距離：

其中，λ為波長，PT為發(fā)送方功率大小，PR為接收方功率大小。節(jié)點i與節(jié)點j進行n次距離的測算，兩個節(jié)點間平均距離為：

若平均距離小于給定的閾值，將該節(jié)點信息加入自己的內存，若節(jié)點的內存中存在狀態(tài)為簇首的節(jié)點，則發(fā)送入簇申請。若節(jié)點的內存中存在多個可選的簇首，則計算簇首的優(yōu)先級：

其中，wv表示簇首CHv的權值，N表示簇內節(jié)點數(shù)量，s表示節(jié)點i與簇首CHv的平均距離。節(jié)點可向優(yōu)先級最大的簇首發(fā)送入簇申請。

若節(jié)點內存中不包含簇首，則選擇權值最大的節(jié)點作為簇首，其余節(jié)點以簇成員的身份加入。簇內節(jié)點主要采用廣播方式進行通信，若節(jié)點數(shù)量過多，將會造成網絡擁堵和延遲等問題。為控制簇的節(jié)點數(shù)量，本文提出簇首隱藏狀態(tài)的概念，當簇首檢測到簇內的節(jié)點數(shù)量超過給定閾值時，將自己的狀態(tài)轉為簇首隱藏狀態(tài)，不再處理入簇申請，其余節(jié)點也不會選擇隱藏狀態(tài)的簇首加入。

2.2.2 簇結構維護

簇結構維護即系統(tǒng)針對簇結構變化的一系列反應，節(jié)點的下列三種行為將引起簇結構的變化：節(jié)點加入、節(jié)點離簇和節(jié)點移動。在本文中節(jié)點可采用主動或被動的方式監(jiān)測簇結構的變化。

節(jié)點收到簇首的Hello 消息后，進入節(jié)點加入流程。首先計算簇首的優(yōu)先級，選擇向優(yōu)先級最高的簇首發(fā)送入簇申請。簇首收到入簇申請后，驗證節(jié)點的身份信息，驗證通過后，同意節(jié)點入簇，廣播修改后的簇成員表。成員節(jié)點收到廣播后，同步修改簇成員表。

根據(jù)節(jié)點的狀態(tài)和節(jié)點退出簇的方式，可將節(jié)點退出分為四類：成員節(jié)點正常退出、成員節(jié)點非正常退出、簇首節(jié)點正常退出、簇首節(jié)點非正常退出。節(jié)點離簇前需要向簇內各節(jié)點廣播離簇消息，表示自己即將離簇，成員節(jié)點離簇后簇首需要修改并廣播簇成員表，對于簇首的離簇，需要指定或選舉出新的簇首。正確廣播離簇消息的節(jié)點被視為正常離簇。此外，本文采用被動方式檢測節(jié)點的非正常離簇，正常運行的節(jié)點需要在每個周期廣播Hello消息，若某節(jié)點連續(xù)三個周期未廣播Hello 消息，則其余節(jié)點可將其視為非正常離簇。

當節(jié)點受到環(huán)境變化或任務改變等因素的影響，需要移動較大的距離，其選擇退出當前簇加入另一簇的過程就完成了一次節(jié)點移動。節(jié)點移動是節(jié)點退出和節(jié)點加入的組合。若節(jié)點移動的距離過大，無法接收到任何簇首的Hello消息，則將自己的狀態(tài)改為游離狀態(tài)，等待接收簇首的Hello消息。

綜上所述，本文主動監(jiān)測簇內網絡拓撲變化的方式為簇首接收到節(jié)點的入簇申請，以及簇內節(jié)點收到離簇節(jié)點的離簇消息；被動監(jiān)測拓撲變化的方式為連續(xù)三個周期未收到節(jié)點的Hello消息。將主動與被動的形式相結合，可以更加有效地判斷簇結構是否發(fā)生變化，增強系統(tǒng)的穩(wěn)定性。

2.2.3 拓撲狀態(tài)變更

對于簇首節(jié)點，若連續(xù)三次廣播的簇成員表都相同，則將自己的拓撲狀態(tài)從拓撲變化狀態(tài)改為拓撲穩(wěn)定狀態(tài)。簇首修改簇成員表后，需要將自己的拓撲狀態(tài)改為拓撲變化狀態(tài)。對于簇成員節(jié)點，若連續(xù)三次收到相同的簇成員表，則將自己的拓撲狀態(tài)從拓撲變化狀態(tài)改為拓撲穩(wěn)定狀態(tài)。當簇成員收到簇首更新的簇成員表或連續(xù)三個Hello消息周期未收到簇首的Hello 消息，需要將自己的拓撲狀態(tài)改為拓撲變化狀態(tài)。

2.2.4 會話密鑰協(xié)商

完成分簇的網絡初始化操作后，節(jié)點處于拓撲穩(wěn)定狀態(tài)，進入密鑰協(xié)商階段。本文的密鑰協(xié)商過程基于棣弗-赫爾曼（Diffie-Hellman，DH）密鑰交換，如圖4所示，簇內的節(jié)點兩兩協(xié)商一個共同的會話密鑰Ki。圖5 展示了節(jié)點i與節(jié)點j協(xié)商密鑰時所發(fā)送的消息，密鑰協(xié)商涉及的相關符號如表1所示。后續(xù)階段如有新節(jié)點入簇，新節(jié)點需要向簇內的所有節(jié)點協(xié)商會話密鑰，密鑰協(xié)商結束后，節(jié)點運行區(qū)塊管理模塊。

圖5 會話密鑰協(xié)商流程Fig.5 Session key negotiation process

2.3 區(qū)塊管理模塊

區(qū)塊管理模塊由共識模塊和區(qū)塊恢復模塊組成。系統(tǒng)完成密鑰協(xié)商后，每一個簇開始運行共識模塊，獨立地進行共識，簇中的每個節(jié)點（包括簇首和簇成員）都有相同的概率和地位產生區(qū)塊，區(qū)塊由會話密鑰加密后在簇內廣播。受到任務和環(huán)境變化等因素的影響，網絡可能經歷分裂和合并等拓撲變化，區(qū)塊恢復模塊負責網絡拓撲改變后對區(qū)塊鏈分支進行恢復。如圖6 所示，系統(tǒng)基于DAG 結構構建區(qū)塊鏈，網絡分裂成多個簇時，由于網絡隔離，區(qū)塊鏈會產生分支，每個簇在各自的分支上產生區(qū)塊，每一條分支也基于DAG 結構，提高了系統(tǒng)的吞吐量。當多個簇合并成一個簇后，節(jié)點運行區(qū)塊恢復模塊，恢復由其他簇產生的區(qū)塊。

圖6 DAGGraph賬本Fig.6 DAGGraph ledger

如圖6 所示，本系統(tǒng)將區(qū)塊分為四種類型：創(chuàng)世區(qū)塊（Genesis Block）、配置更改塊（ConfChange Block）、合并塊（Merge Block）以及普通塊（Normal Block）。創(chuàng)世區(qū)塊由簇首產生，是系統(tǒng)產生的第一個區(qū)塊，隨后簇中的每一個節(jié)點都有相同的概率產生普通塊，普通塊可包含交易在內的任何類型的事務信息。為簡化出塊流程，減小網絡通信負載，每個普通塊只包含一條事務信息，即節(jié)點直接將自己的事務打包成區(qū)塊，交由共識模塊共識。網絡發(fā)生分裂后，將形成多個簇，每個簇的簇首都會在本簇的賬本上生成一個相同的配置更改塊，用于收斂之前生成的區(qū)塊。網絡發(fā)生合并后由新簇首產生合并塊，合并塊將引用區(qū)塊鏈各分支上所有未被引用的區(qū)塊，用于合并各簇產生的分支。

本系統(tǒng)定義的區(qū)塊結構如圖7所示，主要包含區(qū)塊類型、區(qū)塊標記、父哈希列表和隨機數(shù)Nonce 等字段。區(qū)塊標記包含該區(qū)塊的創(chuàng)建者信息：若區(qū)塊類型為普通塊，則區(qū)塊標記為簇ID，同一簇內的節(jié)點產生的普通塊包含相同的簇ID，簇ID 由簇首在拓撲穩(wěn)定后生成，并廣播給簇成員節(jié)點。簇ID的計算公式為：

圖7 區(qū)塊結構Fig.7 Block structure

簇ID=Hash(∑簇內節(jié)點ID)（6）

若區(qū)塊類型為簇首產生的創(chuàng)世區(qū)塊、配置更改塊或合并塊，則區(qū)塊標記為簇首ID。為確保系統(tǒng)穩(wěn)定出塊，保證區(qū)塊鏈系統(tǒng)的安全性，防止女巫攻擊等惡意行為，節(jié)點在產生區(qū)塊前需運行一次工作量證明（proof of work，PoW）算法。隨機數(shù)Nonce 在節(jié)點運行PoW 算法后產生，父哈希列表包含區(qū)塊引用的所有父區(qū)塊的哈希值。

2.3.1 共識模塊

共識模塊負責區(qū)塊的生成上鏈。在DAGGraph中，每個節(jié)點均可進行出塊，在網絡質量良好、信道占用率低的情況下，簇內的節(jié)點越多，簇的出塊速度越大。然而隨著簇內節(jié)點數(shù)量的增加，節(jié)點間因出塊進行的通信可能會占用大量的信道資源，對系統(tǒng)的整體性能造成影響。因此，本文除第2.2.1 小節(jié)所提出的簇首隱藏狀態(tài)的概念用于限制簇節(jié)點密度外，還將通過共識模塊，根據(jù)簇內節(jié)點數(shù)量的變化動態(tài)調整PoW 算法的難度以調整簇的出塊速度。出塊速度可簡化為：

其中，N表示簇內節(jié)點數(shù)量，p表示節(jié)點出塊的概率，A表示節(jié)點性能，D表示共識算法的難度。因此，出塊速度與簇內節(jié)點的數(shù)量、節(jié)點出塊的概率以及節(jié)點的性能成正比，與共識算法的難度成反比。共識模塊隨節(jié)點數(shù)量的增加而適當提高共識算法的難度，可在一定程度上限制出塊速度，以確保簇內信道占用率處于可接受的水平，保證系統(tǒng)的平穩(wěn)運行，所選取的PoW 難度適中，對系統(tǒng)的整體能耗影響較小。此外，在節(jié)點出塊前引入PoW 算法還可以增加惡意節(jié)點作惡成本，提高系統(tǒng)安全性。

共識模塊負責產生區(qū)塊和區(qū)塊上鏈。區(qū)塊的共識不同于Raft算法需要超過半數(shù)節(jié)點返回確認消息，本系統(tǒng)的節(jié)點出塊流程如下：首先節(jié)點打包自己產生的事務，接著運行一次簡單的PoW 算法，并廣播自己的區(qū)塊。其他節(jié)點收到區(qū)塊后，需要驗證區(qū)塊是否滿足共識模塊規(guī)定的共識算法難度，如滿足則進入?yún)^(qū)塊上鏈階段，如不滿足則丟棄。采用工作量證明實現(xiàn)對區(qū)塊的驗證，可減少集群中的通信量，提高共識速度。如圖8 所示，節(jié)點拓撲狀態(tài)穩(wěn)定后，由簇首向簇成員節(jié)點廣播開始共識消息，簇成員收到消息后運行共識模塊。共識模塊將節(jié)點拓撲穩(wěn)定后的時間劃分為多個時間片（Epoch），節(jié)點可在每個Epoch產生區(qū)塊，每個新上鏈的區(qū)塊需要引用前一個Epoch產生的所有區(qū)塊。如果拓撲狀態(tài)發(fā)生改變，如節(jié)點退出或入簇，則簇內的節(jié)點停止出塊，待拓撲狀態(tài)穩(wěn)定后重新運行共識模塊。退出簇的節(jié)點重新組成另一個新的簇后，網絡分裂成兩個簇，區(qū)塊鏈也將分裂為獨立的分支，待拓撲穩(wěn)定后兩個簇在各自的分支上繼續(xù)進行共識。

圖8 DAGGraph共識機制Fig.8 DAGGraph consensus mechanism

2.3.2 區(qū)塊恢復模塊

區(qū)塊恢復模塊用于在簇間和簇內，對新加入的節(jié)點恢復區(qū)塊鏈分支。當網絡發(fā)生合并時，合并的簇之間需要恢復其他簇產生的分支；節(jié)點加入某一簇后，也需要從該簇節(jié)點恢復自己所缺失的所有區(qū)塊。如圖9 所示，簇A 和簇B 合并為一個新的簇，以簇A為例，它需要恢復簇B產生的區(qū)塊。簇A的簇首向簇B 的簇首發(fā)送請求消息，請求簇B 的完整分支，簇A的簇首收到完整分支后在本地進行恢復，然后向自己的簇成員廣播來自簇B的分支，實現(xiàn)簇A的所有節(jié)點對簇B 分支的恢復。簇B 也以相同的方式恢復簇A產生的分支。待區(qū)塊恢復完成后，合并后的簇選舉新的簇首，然后由新簇首生成合并塊，收斂之前的區(qū)塊鏈分支。

圖9 簇間區(qū)塊恢復Fig.9 Inter-cluster block recovery

如圖10所示，簇A的節(jié)點1因某種原因離開本簇后加入簇B，節(jié)點1 需要恢復簇B 產生的區(qū)塊，節(jié)點1的區(qū)塊恢復任務由簇B 的簇首負責完成。簇B 的簇首檢測到節(jié)點1的加入后，判定簇內網絡拓撲發(fā)生變化，立即停止共識，并生成配置更改塊，運行區(qū)塊恢復流程。節(jié)點1 向簇B 的簇首發(fā)送請求消息，請求簇B的區(qū)塊分支，節(jié)點1收到簇B分支后進行恢復，并刪除由簇A產生的分支。待網絡拓撲穩(wěn)定后，簇B的簇首產生配置更改塊，表示節(jié)點1 的區(qū)塊恢復成功，簇B的節(jié)點可繼續(xù)進行共識。

圖10 簇內區(qū)塊恢復Fig.10 Intra-cluster block recovery

2.4 節(jié)點注冊

CA具有授權DAGGraph節(jié)點的權限。在實際應用中，一批運行DAGGraph 系統(tǒng)的節(jié)點可以先后向CA 提出注冊申請。CA 完成對節(jié)點的驗證后，向節(jié)點頒發(fā)證書?？紤]到運行DAGGraph 系統(tǒng)的節(jié)點通常不具備較高的算力，因此需要一個安全高效的對稱加密方案完成證書的傳遞。每個節(jié)點開始注冊前，先通過橢圓曲線數(shù)字簽名算法（elliptic curve digital signature algorithm，ECDSA）生成自己的公鑰Pub和私鑰Priv。如圖11 所示，CA 通過節(jié)點的公鑰向節(jié)點傳輸對稱密鑰，并最終使用對稱密鑰構建的安全信道向節(jié)點傳遞證書，完成節(jié)點注冊，節(jié)點注冊所涉及的相關符號如表2所示。

表2 節(jié)點注冊相關符號Table 2 Relevant notation of node registration

圖11 節(jié)點注冊Fig.11 Node registration

2.5 網絡合并檢測

本文將網絡合并定義為當前系統(tǒng)只存在一個簇，所有節(jié)點都已加入該簇，采用對比簇成員信息的方式檢測是否發(fā)生網絡合并。本系統(tǒng)基于私有鏈，當一批節(jié)點完成向CA 的注冊后，表示節(jié)點成功加入DAGGraph 系統(tǒng)。所有節(jié)點完成注冊后，CA 將它們寫入節(jié)點信息表。節(jié)點信息表包含所有加入系統(tǒng)的節(jié)點的身份信息。其他簇的節(jié)點入簇后，原有簇的節(jié)點比較簇成員表和節(jié)點信息表，如果兩表內包含的簇成員節(jié)點信息相同，則表示發(fā)生了網絡合并，節(jié)點需要運行區(qū)塊恢復模塊，完成對分支的恢復。

3 安全性與通信復雜度分析

3.1 安全性分析

本節(jié)討論系統(tǒng)的分簇管理模塊和共識模塊易受到的安全攻擊，并分析系統(tǒng)應如何防范。

拒絕服務（denial of service，DoS）攻擊：在分簇階段，惡意節(jié)點將大量無效的Hello 消息廣播給鄰居節(jié)點，使節(jié)點無法處理正常的分簇請求。本系統(tǒng)采用CA 頒發(fā)證書的形式，確保每個節(jié)點都可被驗證身份，對于未被驗證的節(jié)點，系統(tǒng)將直接忽略其發(fā)送的消息。

雙花攻擊：在傳統(tǒng)鏈式結構的區(qū)塊鏈中，雙花攻擊指惡意節(jié)點在區(qū)塊鏈上發(fā)起一筆交易，當交易被打包成區(qū)塊后，在該區(qū)塊之前重新發(fā)布一個包含沖突交易的區(qū)塊，造成區(qū)塊鏈的分叉。若分叉鏈能夠取代主鏈，則惡意節(jié)點的雙花攻擊成功。在基于DAG 結構的區(qū)塊鏈上，雙花攻擊指的是惡意節(jié)點在區(qū)塊鏈的分支上發(fā)布兩個包含沖突交易的區(qū)塊，DAG 結構雖然能夠容忍分叉的產生，但沖突的交易也將影響區(qū)塊鏈系統(tǒng)的正常運行。本系統(tǒng)根據(jù)時間片對區(qū)塊進行排序，同一個時間片內的區(qū)塊按哈希值進行排序，通過這種方式確定DAG 賬本內區(qū)塊的總順序，對于沖突的交易，將排序靠前的交易視為有效交易。

女巫攻擊：女巫攻擊指惡意節(jié)點冒充多個身份，爭奪網絡控制權，影響共識結果以及干擾節(jié)點正常工作等。進行女巫攻擊的節(jié)點需要將自己的計算資源分配給多個身份，每個身份分配到的資源有限。本系統(tǒng)規(guī)定節(jié)點出塊前需要運行一次PoW 算法，有效地限制了女巫攻擊。此外，CA 負責為每個節(jié)點頒發(fā)證書，同一節(jié)點無法向CA 申請多個證書，不被CA驗證的節(jié)點將無法運行本系統(tǒng)，從根源上杜絕了女巫攻擊的發(fā)生。

3.2 共識階段的通信復雜度分析

BlockGraph 采用Raft 算法，假設節(jié)點總數(shù)為n，則區(qū)塊由leader發(fā)送后至少需要n2條確認消息才能上鏈，BlockGraph 在共識階段的通信復雜度為O(n)。DAGGraph簇中的簇首和簇成員均可產生區(qū)塊，且節(jié)點采用PoW 算法驗證區(qū)塊的正確性，通過驗證的區(qū)塊即可上鏈，而節(jié)點無需向簇首或其他任意節(jié)點返回確認消息。因此DAGGraph 的共識時延僅由區(qū)塊的打包和傳播時間以及節(jié)點運行PoW 算法驗證區(qū)塊的時間構成，而區(qū)塊的傳播時間可忽略不計。區(qū)塊的打包和驗證僅需節(jié)點在本地計算和驗證PoW 算法，因此共識時延與節(jié)點個數(shù)無關，DAGGraph 在共識階段的通信復雜度為O(1)，其通信效率要明顯高于BlockGraph。

4 相關工作實驗結果與分析

4.1 實驗環(huán)境

實驗采用Docker 虛擬化技術模擬節(jié)點和節(jié)點運行所需的網絡環(huán)境，Docker運行的軟硬件環(huán)境如表3所示。本實驗所采用的代碼庫均由論文作者編寫，代碼運行環(huán)境由python:3.5.4-jessie提供支持，實驗所需的Docker 鏡像基于Python3 編寫生成。實驗開始前先在Docker 中創(chuàng)建一個網絡以供節(jié)點通信使用，并使用Docker 鏡像在網絡中批量生成模擬節(jié)點行為的Docker 容器，容器可模擬BlockGraph 和DAGGraph的共識行為，容器間使用用戶數(shù)據(jù)報協(xié)議（user datagram protocol，UDP）進行通信。為便于仿真實驗，本文假設一個區(qū)塊內僅包含一筆由節(jié)點產生的交易，并將區(qū)塊大小設置為8 KB。實驗主要模擬BlockGraph和DAGGraph的出塊和上鏈過程，通過對比二者在不同節(jié)點數(shù)量以及不同簇數(shù)量下的共識時延與吞吐量，來評估方案的性能。

表3 實驗軟硬件環(huán)境Table 3 Software and hardware environments of experiment

4.2 共識時延測試

共識時延指的是簇內完成一次共識所需的時間，共識時延的大小將在一定程度上影響區(qū)塊鏈系統(tǒng)的性能。本文對比的區(qū)塊鏈系統(tǒng)為BlockGraph。BlockGraph的共識機制基于Raft算法，核心是在每個分區(qū)內選舉出領導者節(jié)點，由領導者節(jié)點向追隨者節(jié)點復制區(qū)塊，實現(xiàn)賬本的一致性。Raft算法要求領導者節(jié)點收集超過半數(shù)的確認消息，才能確保區(qū)塊復制成功，因此等待確認消息的時間將影響共識時延的大小。本文提出的DAGGraph 將每一個簇內的節(jié)點分為一個簇首節(jié)點和多個簇成員節(jié)點，且每個節(jié)點均可以產生區(qū)塊。為加強系統(tǒng)的安全性，節(jié)點產生區(qū)塊前將運行一次簡單的PoW算法，節(jié)點收到區(qū)塊后僅需要驗證必要的身份信息和區(qū)塊的正確性，簡化了區(qū)塊的確認過程。圖12 為一個分區(qū)內BlockGraph 和DAGGraph 的共識時延隨節(jié)點個數(shù)的變化關系。從實驗結果可以看出，DAGGraph的共識時延明顯優(yōu)于BlockGraph。DAGGraph 的共識時延隨節(jié)點數(shù)量的變化緩慢波動，基本維持穩(wěn)定的值。而BlockGraph的共識時延隨節(jié)點數(shù)量的增加呈近似線性增長，原因是BlockGraph 共識的通信復雜度為O(n)，隨著分區(qū)內節(jié)點數(shù)量的增加，領導者節(jié)點所需等待的確認消息越多，共識時延越長。如第3.2 節(jié)所述，DAGGraph在共識階段的通信復雜度取決于解決PoW 難題和驗證PoW所花費的時間，因此DAGGraph在共識階段的通信復雜度為O(1)，共識所需的時間僅取決于PoW算法的難度，與節(jié)點個數(shù)無關。

圖12 不同節(jié)點個數(shù)下的共識時延對比Fig.12 Comparison of consensus delay under different number of nodes

在實際應用中，整個網絡內的節(jié)點數(shù)量往往是固定的，因此隨著網絡分區(qū)數(shù)量的增加，每個分區(qū)內的節(jié)點數(shù)量會相應地減少。在本實驗中，將系統(tǒng)中的節(jié)點總數(shù)固定為200 個，分區(qū)的初始數(shù)量為20 個，假設節(jié)點均勻地分布在各分區(qū)中，此時每個分區(qū)內的節(jié)點數(shù)量為10個；之后逐漸減少分區(qū)的數(shù)量，最終分區(qū)的數(shù)量減少為1個，分區(qū)內的節(jié)點數(shù)量為200個。圖13顯示了節(jié)點總數(shù)不變的前提下，分區(qū)數(shù)量與共識時延的關系。由實驗結果可以得出，DAGGraph的共識時延在分區(qū)數(shù)量不同的情況下，仍能保持穩(wěn)定。這是因為DAGGraph 的共識時延僅取決于節(jié)點本地運行PoW 算法的時間，與分區(qū)內節(jié)點個數(shù)無關，分區(qū)數(shù)量變化所引發(fā)的分區(qū)內節(jié)點數(shù)量的變化不會對DAGGraph 的共識時延造成影響。而BlockGraph 的共識時延隨分區(qū)數(shù)量的減少而增加，受分區(qū)數(shù)量變化的影響較大。這是由于BlockGraph 采用的Raft 算法的性能隨節(jié)點數(shù)的增加而下降。在節(jié)點數(shù)量不變的前提下，分區(qū)數(shù)量越少，分區(qū)內的節(jié)點數(shù)量越多，BlockGraph 共識所需等待的確認消息越多，共識時延越大。

圖13 不同分區(qū)數(shù)量下的共識時延對比Fig.13 Comparison of consensus delay under different number of partitions

4.3 吞吐量測試

吞吐量指的是單位時間內區(qū)塊鏈系統(tǒng)處理的交易數(shù)量，與分區(qū)數(shù)量、節(jié)點數(shù)量和區(qū)塊內包含的交易數(shù)量成正比，與平均共識時延成反比。為便于仿真模擬，本實驗假設每個區(qū)塊包含一個交易，測試BlockGraph 和DAGGraph 的吞吐量與節(jié)點數(shù)量和分區(qū)數(shù)量的關系。

圖14 為吞吐量與節(jié)點數(shù)量的關系，可以看出DAGGraph 的吞吐量整體高于BlockGraph，且隨著節(jié)點數(shù)量的增加整體呈波動上升的趨勢，具有一定的可擴展性。這是因為在DAGGraph 中，簇首與簇成員是對等節(jié)點，均有出塊權，網絡中節(jié)點數(shù)量越多，則表示出塊節(jié)點的數(shù)量越多，吞吐量越高。而BlockGraph基于Raft算法，在一個簇內只有一個領導者節(jié)點可以產生區(qū)塊，因此吞吐量基本不隨節(jié)點數(shù)量變化，可擴展性較差。

圖14 不同節(jié)點個數(shù)下的吞吐量對比Fig.14 Comparison of throughput under different number of nodes

在分區(qū)數(shù)量與吞吐量的實驗中，同樣保持節(jié)點總數(shù)為200 個不變，且節(jié)點均勻分布在各分區(qū)中，則分區(qū)內的節(jié)點數(shù)量將隨著分區(qū)數(shù)量的增加而減少，在此前提下測試吞吐量與分區(qū)數(shù)量的關系。如圖15所示，隨著分區(qū)數(shù)量的增加，兩種方案的吞吐量均有一定程度的增長。DAGGraph 比BlockGraph 表現(xiàn)出更好的吞吐量性能，吞吐量的增長速度也更快。這是因為BlockGraph基于Raft算法，采用鏈式結構維護區(qū)塊鏈賬本，并由領導者節(jié)點復制區(qū)塊；而DAGGraph的每個節(jié)點均可產生區(qū)塊，且以DAG 的形式維護賬本，在分區(qū)數(shù)量更多的情況下，DAGGraph 的吞吐量性能優(yōu)勢會更明顯。

圖15 不同分區(qū)數(shù)量下的吞吐量對比Fig.15 Comparison of throughput under different number of partitions

5 結束語

移動自組網允許節(jié)點自發(fā)地形成網絡拓撲，具有組網速度快、拓撲變化靈活等特點。區(qū)塊鏈以安全和不可篡改等特性著稱，將區(qū)塊鏈與移動自組網相結合是一種新穎的嘗試。移動自組網節(jié)點的移動性會引發(fā)節(jié)點隨時離開或加入，這種網絡拓撲的動態(tài)變化給區(qū)塊鏈的運行帶來巨大挑戰(zhàn)。本文提出區(qū)塊鏈與移動自組網的結合需要解決的三個問題：分簇問題、共識問題和區(qū)塊恢復問題。針對這三個問題提出了DAGGraph，一種基于DAG 結構的系統(tǒng)模型。通過引入一種高效的分簇算法，使得節(jié)點通過主動發(fā)現(xiàn)方式完成網絡拓撲變化（分裂）后的高效成簇并快速開始共識。在共識階段，DAGGraph規(guī)定一個區(qū)塊只包含一筆交易，簡化了出塊流程，節(jié)點只需驗證區(qū)塊的正確性和身份信息即可完成區(qū)塊上鏈。在網絡合并階段，通過簇首節(jié)點進行分叉交換和區(qū)塊同步，實現(xiàn)了對缺失區(qū)塊的快速恢復。網絡中傳輸?shù)乃袇^(qū)塊信息均進行加密，確保了區(qū)塊傳輸?shù)陌踩?。此外，DAGGraph以頒發(fā)證書的形式對節(jié)點進行驗證，可以有效抵御DoS 攻擊、雙花攻擊、女巫攻擊等惡意攻擊。實驗結果表明，DAGGraph在共識時延和吞吐量方面的性能較BlockGraph 均有明顯的優(yōu)勢。