DAGGraph:適合移動(dòng)自組網(wǎng)的區(qū)塊鏈

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

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

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

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

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

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

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

（2）針對(duì)網(wǎng)絡(luò)分裂和合并引發(fā)的網(wǎng)絡(luò)拓?fù)涞淖兓岢龌诖厥组g數(shù)據(jù)同步的區(qū)塊恢復(fù)算法，在網(wǎng)絡(luò)合并后由原簇首交換并同步產(chǎn)生的區(qū)塊分支，實(shí)現(xiàn)對(duì)區(qū)塊分支的恢復(fù)，以保留所有節(jié)點(diǎn)產(chǎn)生的合法區(qū)塊。

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

1 相關(guān)工作

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

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

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

2 DAGGraph

2.1 系統(tǒng)模型

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

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

針對(duì)以上問題，本文采用DAG 結(jié)構(gòu)來適配移動(dòng)性引發(fā)的網(wǎng)絡(luò)拓?fù)涞淖兓员Ａ艟W(wǎng)絡(luò)分裂階段各簇獨(dú)立產(chǎn)生的區(qū)塊鏈分支，并通過簇首處理區(qū)塊的恢復(fù)和同步問題，提出一種基于DAG 結(jié)構(gòu)的系統(tǒng)模型DAGGraph，如圖1所示。

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

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

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

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

2.2 分簇管理

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

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

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

基于節(jié)點(diǎn)靈活移動(dòng)的特性，分簇管理的任務(wù)如下：網(wǎng)絡(luò)初始化、節(jié)點(diǎn)加入、節(jié)點(diǎn)退出、節(jié)點(diǎn)移動(dòng)等。為了更加高效地檢測(cè)網(wǎng)絡(luò)拓?fù)渥兓疚倪€定義了兩種拓?fù)錉顟B(tài)：拓?fù)渥兓癄顟B(tài)、拓?fù)浞€(wěn)定狀態(tài)。初始階段節(jié)點(diǎn)都處于拓?fù)渥兓癄顟B(tài)，待節(jié)點(diǎn)檢測(cè)到分簇完成后轉(zhuǎn)為拓?fù)浞€(wěn)定狀態(tài)。

2.2.1 網(wǎng)絡(luò)初始化

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

圖3 網(wǎng)絡(luò)初始化流程Fig.3 Network initialization process

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

當(dāng)節(jié)點(diǎn)收到來自其他節(jié)點(diǎn)的Hello 消息后，根據(jù)消息驗(yàn)證碼和節(jié)點(diǎn)證書來驗(yàn)證節(jié)點(diǎn)的身份和消息的真實(shí)性。消息驗(yàn)證通過后，根據(jù)節(jié)點(diǎn)發(fā)出的Hello 消息信號(hào)強(qiáng)度計(jì)算節(jié)點(diǎn)間的距離：

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

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

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

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

2.2.2 簇結(jié)構(gòu)維護(hù)

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

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

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

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

綜上所述，本文主動(dòng)監(jiān)測(cè)簇內(nèi)網(wǎng)絡(luò)拓?fù)渥兓姆绞綖榇厥捉邮盏焦?jié)點(diǎn)的入簇申請(qǐng)，以及簇內(nèi)節(jié)點(diǎn)收到離簇節(jié)點(diǎn)的離簇消息；被動(dòng)監(jiān)測(cè)拓?fù)渥兓姆绞綖檫B續(xù)三個(gè)周期未收到節(jié)點(diǎn)的Hello消息。將主動(dòng)與被動(dòng)的形式相結(jié)合，可以更加有效地判斷簇結(jié)構(gòu)是否發(fā)生變化，增強(qiáng)系統(tǒng)的穩(wěn)定性。

2.2.3 拓?fù)錉顟B(tài)變更

對(duì)于簇首節(jié)點(diǎn)，若連續(xù)三次廣播的簇成員表都相同，則將自己的拓?fù)錉顟B(tài)從拓?fù)渥兓癄顟B(tài)改為拓?fù)浞€(wěn)定狀態(tài)。簇首修改簇成員表后，需要將自己的拓?fù)錉顟B(tài)改為拓?fù)渥兓癄顟B(tài)。對(duì)于簇成員節(jié)點(diǎn)，若連續(xù)三次收到相同的簇成員表，則將自己的拓?fù)錉顟B(tài)從拓?fù)渥兓癄顟B(tài)改為拓?fù)浞€(wěn)定狀態(tài)。當(dāng)簇成員收到簇首更新的簇成員表或連續(xù)三個(gè)Hello消息周期未收到簇首的Hello 消息，需要將自己的拓?fù)錉顟B(tài)改為拓?fù)渥兓癄顟B(tài)。

2.2.4 會(huì)話密鑰協(xié)商

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

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

2.3 區(qū)塊管理模塊

區(qū)塊管理模塊由共識(shí)模塊和區(qū)塊恢復(fù)模塊組成。系統(tǒng)完成密鑰協(xié)商后，每一個(gè)簇開始運(yùn)行共識(shí)模塊，獨(dú)立地進(jìn)行共識(shí)，簇中的每個(gè)節(jié)點(diǎn)（包括簇首和簇成員）都有相同的概率和地位產(chǎn)生區(qū)塊，區(qū)塊由會(huì)話密鑰加密后在簇內(nèi)廣播。受到任務(wù)和環(huán)境變化等因素的影響，網(wǎng)絡(luò)可能經(jīng)歷分裂和合并等拓?fù)渥兓瑓^(qū)塊恢復(fù)模塊負(fù)責(zé)網(wǎng)絡(luò)拓?fù)涓淖兒髮?duì)區(qū)塊鏈分支進(jìn)行恢復(fù)。如圖6 所示，系統(tǒng)基于DAG 結(jié)構(gòu)構(gòu)建區(qū)塊鏈，網(wǎng)絡(luò)分裂成多個(gè)簇時(shí)，由于網(wǎng)絡(luò)隔離，區(qū)塊鏈會(huì)產(chǎn)生分支，每個(gè)簇在各自的分支上產(chǎn)生區(qū)塊，每一條分支也基于DAG 結(jié)構(gòu)，提高了系統(tǒng)的吞吐量。當(dāng)多個(gè)簇合并成一個(gè)簇后，節(jié)點(diǎn)運(yùn)行區(qū)塊恢復(fù)模塊，恢復(fù)由其他簇產(chǎn)生的區(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ū)塊由簇首產(chǎn)生，是系統(tǒng)產(chǎn)生的第一個(gè)區(qū)塊，隨后簇中的每一個(gè)節(jié)點(diǎn)都有相同的概率產(chǎn)生普通塊，普通塊可包含交易在內(nèi)的任何類型的事務(wù)信息。為簡(jiǎn)化出塊流程，減小網(wǎng)絡(luò)通信負(fù)載，每個(gè)普通塊只包含一條事務(wù)信息，即節(jié)點(diǎn)直接將自己的事務(wù)打包成區(qū)塊，交由共識(shí)模塊共識(shí)。網(wǎng)絡(luò)發(fā)生分裂后，將形成多個(gè)簇，每個(gè)簇的簇首都會(huì)在本簇的賬本上生成一個(gè)相同的配置更改塊，用于收斂之前生成的區(qū)塊。網(wǎng)絡(luò)發(fā)生合并后由新簇首產(chǎn)生合并塊，合并塊將引用區(qū)塊鏈各分支上所有未被引用的區(qū)塊，用于合并各簇產(chǎn)生的分支。

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

圖7 區(qū)塊結(jié)構(gòu)Fig.7 Block structure

簇ID=Hash(∑簇內(nèi)節(jié)點(diǎn)ID)（6）

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

2.3.1 共識(shí)模塊

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

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

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

圖8 DAGGraph共識(shí)機(jī)制Fig.8 DAGGraph consensus mechanism

2.3.2 區(qū)塊恢復(fù)模塊

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

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

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

圖10 簇內(nèi)區(qū)塊恢復(fù)Fig.10 Intra-cluster block recovery

2.4 節(jié)點(diǎn)注冊(cè)

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

表2 節(jié)點(diǎn)注冊(cè)相關(guān)符號(hào)Table 2 Relevant notation of node registration

圖11 節(jié)點(diǎn)注冊(cè)Fig.11 Node registration

2.5 網(wǎng)絡(luò)合并檢測(cè)

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

3 安全性與通信復(fù)雜度分析

3.1 安全性分析

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

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

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

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

3.2 共識(shí)階段的通信復(fù)雜度分析

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

4 相關(guān)工作實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

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

4.3 吞吐量測(cè)試

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

圖14 為吞吐量與節(jié)點(diǎn)數(shù)量的關(guān)系，可以看出DAGGraph 的吞吐量整體高于BlockGraph，且隨著節(jié)點(diǎn)數(shù)量的增加整體呈波動(dòng)上升的趨勢(shì)，具有一定的可擴(kuò)展性。這是因?yàn)樵贒AGGraph 中，簇首與簇成員是對(duì)等節(jié)點(diǎn)，均有出塊權(quán)，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量越多，則表示出塊節(jié)點(diǎn)的數(shù)量越多，吞吐量越高。而BlockGraph基于Raft算法，在一個(gè)簇內(nèi)只有一個(gè)領(lǐng)導(dǎo)者節(jié)點(diǎn)可以產(chǎn)生區(qū)塊，因此吞吐量基本不隨節(jié)點(diǎn)數(shù)量變化，可擴(kuò)展性較差。

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

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

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

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

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