區塊鏈網絡拓撲優化和轉發策略設計

霍如，程祥鳳，孫闖，汪碩，黃韜，F.Richard Yu

（1.北京工業大學信息學部，北京 100124；2.網絡通信與安全紫金山實驗室，江蘇 南京 211111；3.清華大學自動化系，北京 100084；4.北京郵電大學網絡與交換技術國家重點實驗室，北京 100876；5.加拿大卡爾頓大學信息技術學院，渥太華 KIS 5B6）

0 引言

雖然自比特幣誕生以來，人們對其持不同態度，但作為其底層技術的區塊鏈吸引了大眾的注意，越來越多的學者開始研究區塊鏈，區塊鏈技術呈現蓬勃發展的態勢。區塊鏈憑借自身的去中心化和難以篡改等特性，已經應用于許多領域[1-2]。隨著區塊鏈技術的廣泛使用，區塊鏈的低傳輸效率導致的高交易時延嚴重限制了其進一步發展[3]?，F已有有向無環圖（DAG,directed acyclic graph）[4]和共識協議[5]等方法分別從數據層和共識層進行改進，以提高區塊鏈傳輸效率。然而，不論針對區塊鏈架構的哪一層進行優化，區塊鏈中的交易和區塊都會不可避免地涉及數據傳輸過程。在區塊鏈網絡中，交易和區塊的生成和傳播是很頻繁的，并且在節點之間進行傳輸是相當耗時的。因此，本文對區塊鏈網絡層進行重點研究。

區塊鏈網絡層為區塊鏈提供底層的網絡支撐，搭建節點之間的數據傳輸環境。網絡層包含2 種機制，即對等（P2P,peer-to-peer）網絡、數據傳輸和數據驗證機制[6]。區塊鏈網絡包括無結構、結構化和混合式P2P 網絡[2]。其中，無結構P2P 網絡是指具有隨機圖拓撲結構的P2P 網絡。如何優化區塊鏈網絡層從而縮短數據傳輸時間是擴展區塊鏈性能的一個重要研究方向[7]。

目前，很多研究通過改進區塊鏈網絡拓撲結構和數據傳輸方法來提高區塊鏈數據傳輸效率。在區塊鏈網絡拓撲結構研究方面，Sung 等[8]通過建立數學模型將數據傳輸路徑轉化為最小生成樹問題，減少傳輸鏈路的重用來最小化處理和傳輸時延。Li 等[9]提出一種權重優先算法，該算法逐次選取通信權重小以及傳輸能力強的節點構建通信樹，為區塊鏈交易提供路徑，從而提高區塊鏈的通信效率。Lin 等[10]根據節點的可信度和中心性提出一種可靠的去中心化樹形算法，該算法利用Prim 算法構建通信樹，提高了區塊鏈交易的速度和可靠性。在區塊鏈數據傳輸方法研究方面，Ersoy 等[11]提出一種傳輸激勵機制，節點向鄰居節點傳輸交易時，可以獲得交易費的一部分作為獎勵，鼓勵更多節點參與交易的傳輸，降低區塊鏈傳輸時間。Santiago 等[12]提出一種基于權重的鄰居選擇方法，通過不斷探測節點的新鄰居并更新節點間的權重，增加選擇最佳通信節點的概率，減少區塊鏈網絡的消息傳播時間。Hao 等[13]從區塊鏈網絡拓撲結構和數據傳輸方法兩方面改進，對節點聚類生成的集群構建信任增強的區塊鏈P2P 網絡拓撲，采用并行生成樹算法進行數據傳輸，在加快區塊鏈傳輸速率的同時保證傳輸的可靠性。

上述研究未考慮節點狀態變化對已建立的網絡拓撲產生的影響[8-10]。如果區塊鏈節點狀態發生變化，只能重新構建拓撲結構，從而影響區塊鏈傳輸效率。此外，大多數研究只考慮對區塊鏈網絡拓撲結構和數據傳輸方法的單方面改進，很少有結合兩方面的改進。基于上述問題，本文針對區塊鏈網絡拓撲和轉發策略進行優化，通過設計的可信值函數計算節點可信值，綜合考慮節點可信值和節點之間的傳輸時間，提出樹形拓撲構建方法，在生成的樹形拓撲基礎上，設計一種轉發路徑選擇策略和拓撲動態優化策略，從而縮短數據傳輸時間，提高區塊鏈傳輸效率。本文主要的研究工作如下。

1) 提出樹形拓撲構建方法。首先，利用設計的可信值函數得到每個節點的可信值，根據可信值閾值劃分節點類型。然后，對可信節點采用Sollin 算法構建最小生成樹，將不可信節點加入拓撲，完成樹形拓撲的構建，簡化網絡的拓撲結構，并提高數據傳輸過程中的安全性。

2) 設計轉發路徑選擇策略。該策略以最小整體并發傳輸時間為目標，為每個區塊鏈節點建立關于其鄰居節點轉發次序的轉發表，節點根據轉發表依次選擇其鄰居節點進行數據轉發，使整個傳輸過程具有最小并發傳輸時間，有效縮短數據傳輸時間，同時避免對節點重復傳輸同一數據。

3) 設計拓撲動態優化策略。針對節點加入、節點離開、節點可信值變化和節點間權值變化情況，利用破圈法和Sollin 算法設計了相應的拓撲動態優化策略，只對節點狀態變化影響的部分拓撲結構進行調整。與全網重構拓撲相比，該策略花費的代價較小，并且能夠減少對拓撲進行調整所帶來的開銷。

1 區塊鏈傳輸效率優化方法

為了縮短區塊鏈交易數據在網絡中的傳輸時間，本文從區塊鏈網絡的拓撲結構和節點的轉發策略兩方面進行改進，提出區塊鏈傳輸效率優化方法，如圖1 所示。其中，樹形拓撲構建模型負責生成區塊鏈網絡的樹形拓撲，轉發路徑選擇模型基于樹形拓撲結構為區塊鏈節點建立轉發路徑，拓撲動態優化模型主要對樹形拓撲中狀態發生變化的節點局部拓撲進行調整。

圖1 區塊鏈傳輸效率優化方法

樹形拓撲構建模型主要負責將區塊鏈無結構P2P 網絡構建為樹形拓撲結構，通過優化網絡拓撲結構來減少冗余傳輸?？紤]到數據傳輸過程中的安全性問題，設定節點可信值函數并結合可信值閾值將區塊鏈網絡節點劃分為可信節點和不可信節點，其中，可信值大于閾值的節點為可信節點，否則為不可信節點。針對可信節點和不可信節點采用不同的方式構建網絡的樹形拓撲。

轉發路徑選擇模型基于樹形拓撲結構設計區塊鏈節點的數據轉發策略，以加快數據的傳輸。首先，為每個節點建立關于其鄰居節點的轉發表，轉發表中的節點依據其鄰居節點所在子樹的最小并發傳輸時間由大到小順序依次存放。然后，從發起節點開始轉發數據，節點按照轉發表中的次序向未接收數據的鄰居節點傳輸數據，經過多輪次的數據轉發，從而使全網節點接收到數據。

拓撲動態優化模型根據區塊鏈節點的狀態變化情況，包括節點加入、節點離開、節點可信值變化和節點間權值變化，分別設計了拓撲動態優化策略，降低調整網絡拓撲的開銷。當區塊鏈網絡的節點狀態發生變化時，拓撲動態優化模型選擇相應的拓撲動態優化策略來調整因節點狀態變化所影響的局部拓撲結構，然后更新樹形拓撲結構。

在區塊鏈網絡中，使用本文提出的區塊鏈傳輸效率優化方法對P2P 網絡建立樹形拓撲以及生成節點的轉發表，由記賬節點作為數據發起節點開始傳輸交易數據。在數據傳輸過程中，節點按照轉發路徑選擇策略進行數據轉發。節點在接收到交易數據后會驗證交易的合法性，若交易合法，則存儲到賬本。如果節點狀態變化導致樹形拓撲發生改變，則利用拓撲動態優化策略局部調整樹形拓撲。

1.1 樹形拓撲構建方法

本文將區塊鏈網絡拓撲抽象為圖，節點之間的路徑抽象為邊，邊的權值代表節點之間的數據傳輸時間?？紤]節點的可信值和節點之間的權值，提出樹形拓撲構建方法生成樹形拓撲結構，簡化網絡拓撲的同時提高數據傳輸過程的安全性。

區塊鏈網絡中的節點并不一定都是誠實節點，存在一些惡意節點，惡意節點可能產生惡意行為，篡改或者破壞已接收到的數據，再將數據轉發給其他節點，從而影響數據的可信性，存在安全性問題[14]。因此，本文設計了可信值函數計算區塊鏈節點的可信值，利用節點的可信值描述節點自身的可信程度。設置新加入節點的初始可信值為0，根據節點與其他節點進行交易的成功次數和失敗次數定義節點的可信值。節點的可信值為

其中，i為節點的標號；s為節點交易成功的總次數；u為節點交易失敗的總次數；n為節點交易失敗到下一次失敗之間累計的連續交易成功次數；為獎勵函數，表示給予交易成功節點的可信值獎勵，交易成功的次數越多，節點獲得的獎勵值越大，激勵節點進行更多成功的交易；φ(n) 是懲罰函數，在節點交易失敗時，懲罰函數會降低節點的可信值。懲罰函數定義為

其中，u x表示節點本次交易結束后總的交易失敗次數；ux-1表示節點上一次交易結束后總的交易失敗次數。然后，根據ux-ux-1的值來判斷本次交易是否成功。當節點的本次交易失敗時，φ(n)取值為0，則不會獲得來自獎勵函數的可信值獎勵，同時清空連續交易成功的累計次數n。當節點的本次交易成功時，懲罰函數為，節點獲得獎勵函數的少量獎勵值，同時累計次數增加1。

區塊鏈節點利用可信值函數計算自身的可信值，依據可信值閾值Cthreshold將可信值大于Cthreshold的節點劃分為可信節點，小于或等于Cthreshold的節點劃分為不可信節點。劃分節點的目的是讓可信節點主要承擔數據傳輸任務，向其他節點轉發數據。不可信節點則負責接收數據，防止出現由不可信節點擔任轉發節點而引起數據篡改或被破壞的安全問題?；谏鲜鏊悸?，選取可信節點以及它們之間的邊，從而得到由可信節點組成的可信拓撲。假設G=(N,E,C,W)是一個區塊鏈網絡的拓撲，N為節點集，E為邊集，C為節點可信值集，W為邊的權值集。ni表示區塊鏈節點并且ni∈N，ci表示節點的可信值并且ci∈C，wi,j表示ni與nj相連邊的權值并且wi,j∈W。設{n0,n1,n2,n3,n5}中的節點可信值大于Cthreshold，{n4,n6}中的節點可信值小于Cthreshold。

Sollin 算法是一種結合Prim 和Kruskal 算法思想構建的最小生成樹算法，其每次迭代可同時擴展多棵子樹，使其建樹的效率較高。因此，本文采用Sollin 算法構建最小生成樹。本文提出的樹形拓撲構建方法對可信節點和不可信節點按不同的方式構建網絡的樹形拓撲。在可信拓撲基礎上，該算法首先利用Sollin 算法根據可信節點之間的邊和權值，選擇權值最小邊構建最小生成樹，生成可信樹形拓撲；然后，對不可信節點進行處理，選擇與可信鄰居節點相連的權值最小邊加入樹形拓撲，不可信節點作為樹形拓撲的葉子節點；將所有不可信節點加入樹形拓撲之后完成網絡樹形拓撲的構建。

構建網絡的樹形拓撲示例如圖 2 所示，{n0,n1,n2,n3,n5}為可信節點集，{n4,n6}為不可信節點集。首先，利用Sollin 算法對集合 {n0,n1,n2,n3,n5}中的可信節點逐次選取權值最小邊構建一棵最小生成樹，得到圖2 中的實線邊即最小生成樹的邊。然后，不可信節點n4在其可信鄰居節點 {n2,n3,n5}中選擇權值最小邊w2,4加入樹形拓撲。同理可知，不可信節點n6選擇w0,6加入樹形拓撲，從而完成區塊鏈網絡的樹形拓撲構建。

圖2 構建網絡的樹形拓撲示例

通過樹形拓撲構建方法將原本的區塊鏈無結構P2P 網絡拓撲構建為樹形拓撲，極大地簡化了網絡的拓撲結構。樹形拓撲結合了可信值和最小生成樹的優勢，并且將不可信節點作為樹的葉子節點，很大程度上提高了數據傳輸過程中的安全性，而且由于樹形拓撲具有更小的權值之和，因此有效地縮短了區塊鏈整體的數據傳輸時間。

1.2 轉發路徑選擇策略

區塊鏈采用P2P 網絡組織節點之間進行數據傳輸，每個節點都獨立承擔驗證數據、網絡路由、轉發數據和發現新節點等任務[15]。本文采用并發傳輸機制，即獲得數據的不同節點可以在同一時間段內轉發數據，實現不同節點之間的并發傳輸。節點通過并發傳輸機制進行數據傳輸花費的時間稱為并發傳輸時間?；诓l傳輸機制，本文設計了一種轉發路徑選擇策略，指導節點選擇鄰居節點進行數據轉發。該策略首先為樹形拓撲中的每個節點建立關于其鄰居節點的轉發表，然后設置節點轉發數據的規則。由并發傳輸過程構建孩子-兄弟通信樹示例如圖3 所示。

圖3 由并發傳輸過程構建孩子-兄弟通信樹示例

設Tree=(V,E,W)是一個樹形拓撲，并發傳輸過程如圖3(a)所示。圖3(a)中虛線框內的數字為轉發輪次，表示節點經過第幾輪次轉發后接收到數據。從v0開始轉發數據，下面以節點間的前兩輪轉發為例介紹并發傳輸。在第一輪轉發中，v0將數據傳輸給v1。在第二輪轉發中，由于v1已經從v0接收到數據，因此v1將數據轉發給下一個子節點vv4，0也繼續向v2傳輸數據。

為了研究節點如何選擇鄰居節點轉發數據使整個數據傳輸過程花費的并發傳輸時間最小，本文引入孩子-兄弟通信樹，如圖3(b)所示。圖3(b)中的孩子-兄弟通信樹是根據圖3(a)中的并發傳輸過程建立的，節點v0的深度為0。以節點v2為例介紹孩子-兄弟通信樹的構建過程如下。由于在圖3(a)中v0先將數據轉發給v1，那么在圖3(b)中v1為v0的左孩子。之后v0轉發數據給v2，那么在圖3(b)中v2為v1的右兄弟。孩子-兄弟通信樹中節點的深度代表節點在并發傳輸過程中第幾輪次接收到數據，即節點并發傳輸的轉發輪次。在孩子-兄弟通信樹中，計算某個支路的通信時間只需計算從發起節點到該支路最后一個節點所經過的邊的權值之和。由此借助孩子-兄弟通信樹把研究從發起節點傳輸數據到全網節點花費的最小并發通信時間這個問題轉化為最小化孩子-兄弟通信樹中的支路最大傳輸時間問題。其中，支路最大傳輸時間是指在所有支路傳輸時間中并發傳輸時間最大的支路時間。當節點按照它的鄰居節點（子節點）所在子樹的最小并發傳輸時間由大到小順序選擇鄰居節點轉發數據時，能使從發起節點傳輸數據到全網節點花費的并發傳輸時間最小，證明過程如附錄1 所示。基于上述思想，本文為每個節點建立各自的轉發表，轉發表中按照最小并發傳輸時間由大到小的順序，依次存儲節點所有鄰居節點的名稱和鄰居節點所在子樹的最小并發傳輸時間。轉發表的建立過程如下。首先隨機選擇一個節點作為根節點，得到以該節點為根節點的樹形拓撲；然后，經過自底向上和自頂向下2個過程建立每個節點的轉發表。

1) 自底向上

自底向上建立節點轉發表的過程是以最小整體并發傳輸時間為目標，從樹形拓撲的葉子節點逐步向根節點方向計算節點的子節點所在子樹的最小并發通信時間，子節點向父節點發送計算結果，父節點存儲結果并依次計算以及向上發送結果，直到根節點為止。由于葉子節點沒有子節點，因此葉子節點所在子樹的最小并發傳輸時間為0，將0 發送給它的父節點，父節點按照最小并發傳輸時間由大到小的順序，存儲該葉子節點名稱和它所在子樹的最小并發傳輸時間0。針對節點是非葉子節點的情況，在接收到所有子節點發送的它們各自所在子樹的最小并發傳輸時間后，根據它的轉發表和權值計算該非葉子節點所在子樹的最小并發傳輸時間。將計算結果發送給它的父節點，父節點按照由大到小順序進行存儲。在同一轉發表中，如果存在多個子節點的最小并發傳輸時間相同，那么子節點所在子樹連通度大的子節點優先存儲；如果連通度相同，則優先存儲與節點相連權值小的子節點。當根節點轉發表建立完成時，則自底向上建立轉發表的過程結束。轉發表建立示例如圖4 所示。

圖4 轉發表建立示例

隨機選擇樹形拓撲中的n1作為根節點，以自底向上建立n1的轉發表為例介紹該過程。由于n4、n5和n6是葉子節點，因此其子樹的最小并發傳輸時間為0，分別將節點名稱和0 發送給它們的父節點n3、2n和n0。n2收到子節點n4的信息按由大到小存儲到轉發表，然后n2計算其所在子樹的最小并發傳輸時間為w2,4=2，并將n2和2 發送給n3。n3按照最小并發傳輸時間由大到小的順序存儲到轉發表。在3n收到子節點n2和n5的信息之后，n3根據轉發表的轉發順序構建以n3為根節點，以n2和n5為子節點的通信樹，類似于圖3(b)，計算支路最大傳輸時間，得到n3所在子樹的最小并發傳輸時間6，發送給n1節點并排序。同理可得n0所在子樹的最小并發傳輸時間，n1節點的轉發表建立完成。

2) 自頂向下

當自底向上建立轉發表的過程結束后，除根節點外的其他節點的轉發表中只缺少一項由父節點作為子節點時其所在子樹的最小并發傳輸時間。因此，采用自頂向下過程補全其他節點的轉發表。自頂向下建立轉發表的過程是以最小整體并發傳輸時間為目標，根據每個節點轉發表中已存儲的節點信息，從樹形拓撲的根節點逐步向葉子節點方向計算將父節點看作子節點時其所在子樹的最小并發傳輸時間，完成每個節點轉發表的建立。

以圖4中的n3為例介紹自頂向下轉發表的建立過程。n3的父節點是n1，將父節點n1看作n3的子節點時，n1所在子樹包含節點n1、n0和n6，計算該子樹的最小并發傳輸時間為w0,1+W0=5，其中W0是n1轉發表中存儲的n0所在子樹的最小并發傳輸時間，將n1和5 發送給n3節點并排序，如圖4 中n3的虛線方框所示，此時n3得到完整的轉發表。同理可得其他節點的完整轉發表。

節點轉發數據的規則是將發起交易數據的節點指定為發起節點，并作為樹形拓撲的根節點，從根節點開始進行數據轉發，直到樹中所有節點接收到數據為止。如果節點是發起節點，那么節點完全按照轉發表依次選擇鄰居節點進行數據的轉發即可。如果節點是轉發節點，不再向給它發送數據的節點轉發數據，按照轉發表依次選取其余節點轉發數據。本文提出的轉發路徑選擇策略具有最小整體并發傳輸時間，有效縮短了數據傳輸時間，同時避免對節點重復傳輸同一數據，極大提高了區塊鏈的傳輸效率。

1.3 拓撲動態優化策略

區塊鏈是由節點自主管理和維護的一種P2P 網絡。在P2P 網絡中，每個節點都可以隨時加入或退出網絡[16]。區塊鏈節點的加入和離開網絡等行為會引起網絡拓撲發生變化，本文利用提出的拓撲動態優化策略局部調整拓撲，在一定程度上減小因拓撲動態變化而引起的額外傳輸時間，從而減少區塊鏈出現分叉的情況，確保區塊鏈賬本的唯一性和一致性。拓撲動態優化策略作用于區塊鏈網絡層，對區塊鏈網絡層的改進不會影響區塊鏈共識層使用共識算法來保障區塊鏈賬本的唯一性與一致性。針對樹形拓撲存在節點加入行為、離開行為、可信值變化以及節點間權值發生變化的情況，本文設計了相應的拓撲動態優化策略，只對狀態變化節點的局部范圍進行拓撲調整，避免重構整個網絡的拓撲。下面介紹該策略使用的2 個算法以及提出的4 個子拓撲動態優化策略。拓撲動態優化示例如圖5 所示。

圖5 拓撲動態優化示例

破圈法。對于存在回路的樹形拓撲，每次刪除回路中權值最大的邊，同時確保樹形拓撲是連通的，直到樹形拓撲不存在回路。

Sollin 算法。對于目前存在的多棵子樹，依次選取每棵子樹與其他子樹相連的權值最小邊，然后合并子樹，直到構成一棵最小生成樹。

策略1節點加入拓撲動態優化策略

1) 可信節點加入拓撲動態優化策略是選取該節點與可信鄰居節點相連的所有邊加入樹形拓撲，此時樹形拓撲可能存在回路，若所有邊加入樹形拓撲存在回路，則對樹形拓撲采用破圈法，得到可信節點加入后的樹形拓撲。圖5 的可信節點n7加入網絡時，選取n7與可信鄰居節點n5相連的邊加入樹形拓撲，由于樹形拓撲沒有回路，因此直接得到7n加入后的樹形拓撲。

2) 不可信節點加入拓撲動態優化策略是從不可信節點與可信鄰居節點相連的所有邊中選取權值最小邊，將該邊加入樹形拓撲，得到不可信節點加入后的樹形拓撲。

策略2節點離開拓撲動態優化策略

1) 葉子節點離開拓撲動態優化策略是刪除該節點以及與其他節點的相連邊。

2) 針對樹形拓撲中非葉子節點離開行為，采取的節點離開拓撲動態優化策略如下所述。在刪除離開的非葉子節點以及與其他節點的相連邊之后，樹形拓撲分裂為多棵不連通的子樹，這些子樹的構成分為2 種情況，一種是由多個節點構成，另一種是僅由一個節點構成。非葉子節點離開拓撲動態優化策略如下。首先，采用Sollin 算法對由第一種情況構成的多棵不連通的子樹進行樹形拓撲的構建，對新選取的邊進行判斷。如果新選取的邊包含不可信節點，則該邊不能作為樹形拓撲的邊，繼續對不連通的子樹運行Sollin 算法，直到選取的邊不含不可信節點。然后，對第二種情況的子樹進行處理，選取這個子樹節點與其可信鄰居節點直接相連的所有邊中的權值最小邊，將該邊加入第一種情況更新后的樹形拓撲，更新樹形拓撲。

圖5 中，非葉子節點n2離開拓撲優化策略是從網絡中刪除n2以及與其他節點的相連邊，采用Sollin 算法對由多個節點構成的多棵不連通子樹構建樹形拓撲。因為只有一棵由多個節點{n0,n1,n3,n5,n6}構成的連通子樹，所以不需要利用Sollin 算法進行構建。將由一個節點n4構成的子樹加入由節點 {n0,n1,n3,n5,n6}構成的樹形拓撲，選取n3和n4相連的邊作為樹形拓撲的邊。

策略3節點可信值變化拓撲動態優化策略

節點的可信值變化可能影響節點的屬性，例如，由可信節點變為不可信節點，不可信節點變為可信節點，從而引起樹形拓撲結構的改變。

1) 當節點由可信節點變為不可信節點時，判斷該節點是否為葉子節點。如果該節點是葉子節點，則其拓撲結構不發生變化，節點屬性變為不可信節點。如果該節點不是葉子節點，那么先對該可信節點執行策略2，然后對可信值變化后的不可信節點執行策略1，更新樹形拓撲，如圖5 中的n1可信值變化過程所示。

2) 當節點由不可信節點變為可信節點時，對該節點的可信鄰居節點和不可信鄰居節點采取不同的調整策略。首先，將可信鄰居節點與該節點連接的所有邊加入樹形拓撲，運行破圈法。然后，對該節點的所有不可信鄰居節點先后執行策略2 和策略1，得到節點可信值變化后的樹形拓撲。

策略4節點間權值變化拓撲動態優化策略

1) 如果節點之間權值變化的邊是樹形拓撲的邊并且權值變小，或該邊不是樹形拓撲的邊并且權值變大，則拓撲結構不變，只更新該邊的權值。

2) 針對權值變化邊連接的2 個節點是可信節點情況，如果該邊是樹形拓撲的邊并且權值變大，更新該邊的權值，在樹形拓撲中刪除該邊，對分裂后的多棵子樹采用Sollin 算法選擇新連接的邊。若新選取的邊連接的節點都是可信節點，那么選擇該邊連接分裂的子樹，更新樹形拓撲。若新選取的邊連接的節點存在不可信節點，則選擇原先刪除的邊來連接分裂的子樹，此時樹形拓撲結構不變。

如果該邊不是樹形拓撲的邊并且權值變小，更新區塊鏈網絡拓撲中該邊的權值，將該邊加入樹形拓撲，對構成回路的節點運行破圈法，更新樹形拓撲。

3) 針對權值變化邊連接的2 個節點存在不可信節點情況，如果該邊是樹形拓撲的邊并且權值變大，更新該邊的權值，在樹形拓撲中刪除該邊，對分裂后的多棵子樹采用Sollin 算法選擇新連接的邊。若新選取的邊連接的節點只有一個不可信節點，那么選擇該邊連接分裂的子樹，更新樹形拓撲。若新選取的邊連接的節點都是不可信節點，則選擇之前刪除的邊來連接分裂的子樹，此時樹形拓撲結構不變。

如果該邊不是樹形拓撲的邊并且權值變小，更新區塊鏈網絡拓撲中該邊的權值，刪除該邊所連接的不可信節點在樹形拓撲中的邊，再對該節點執行策略1，更新樹形拓撲。圖5 中n4和n5之間邊的權值w4,5變小，更新區塊鏈網絡拓撲中該邊的權值為，刪除該邊連接的不可信節點n4在樹形拓撲的邊，即n2和n4之間的邊，再對不可信節點n4執行策略1，選擇n4和n5之間的邊作為樹形拓撲的邊，更新樹形拓撲。

2 算法設計與實現

區塊鏈傳輸效率優化方法通過樹形拓撲構建方法生成樹形拓撲，利用轉發路徑選擇策略建立轉發路徑，采用拓撲動態優化策略調整局部拓撲，從而縮短區塊鏈數據傳輸時間，提高數據傳輸效率。

2.1 樹形拓撲構建算法

可信拓撲是樹形拓撲構建的前提，樹形拓撲構建算法利用Sollin 算法對可信拓撲構建最小生成樹，之后將不可信節點作為最小生成樹的葉子節點加入樹形拓撲。具體的算法流程如算法1 所示。

算法1樹形拓撲構建算法

2.2 轉發路徑選擇算法

根據轉發路徑選擇策略，設計轉發路徑選擇算法，算法初始時隨機指定樹形拓撲的某一節點作為根節點，然后按照自底向上和自頂向下2 個過程建立關于節點的鄰居節點轉發表，最后根據轉發表和轉發數據規則進行數據的轉發。轉發路徑選擇算法如算法2 所示。

算法2轉發路徑選擇算法

2.3 拓撲動態優化算法

本文針對節點的加入行為、離開行為、可信值變化和節點間權值變化情況設計了拓撲動態優化策略，根據該策略設計了拓撲動態優化算法，算法主要利用破圈法和Sollin 算法實現對狀態變化節點拓撲的局部調整。拓撲動態優化算法如算法3 所示。

算法3拓撲動態優化算法

3 仿真分析

為了驗證所提方法和策略的有效性，本文使用Python 進行仿真實驗，使用Python 的networkx 庫生成網絡拓撲。實驗設置構建網絡拓撲的節點個數為從100 到1 000 的等步長取值，節點之間的權值設置為[1,50]隨機取值，權值的單位為s。可信值閾值用于劃分節點類型，當節點傳輸成功率小于0.6時，該節點劃分為不可信節點[10]。將其值代入式(1)計算得出可信值閾值為1.2。為了避免節點同時與多個鄰居節點進行數據傳輸時，一些節點受自身性能的限制無法同時傳輸給多個節點，從而導致數據丟失問題，設定節點在同一時間段內只能與一個節點進行數據傳輸。本文選取平均并發傳輸時間和轉發次數作為實驗指標，將本文提出的轉發路徑選擇算法與權重優先算法[9]、隨機路徑算法[10]進行對比。另外考慮到網絡中節點狀態變化情況，本文選取拓撲調整時間比和節點的參與率作為實驗指標，將本文提出的拓撲動態優化算法與全網重構拓撲算法進行對比。本文的仿真參數設置如表1 所示。

表1 仿真參數設置

權重優先算法是通過優先選取與當前節點相連的權重最小節點，按照左孩子右兄弟原則構造通信樹。隨機路徑算法是指節點隨機選擇除向它發送數據的節點之外的其他鄰居節點進行數據轉發。本文提出的轉發路徑選擇算法與權重優先算法、隨機路徑算法在不同網絡節點數量下的平均并發傳輸時間如圖6 所示。其中，平均并發傳輸時間是指將每個節點作為數據發起節點計算數據傳輸到全網節點的并發傳輸時間之和的平均值。由于隨機路徑算法隨機選擇的鄰居節點很大概率不是最優節點，因此具有最高平均并發傳輸時間。權重優先算法在逐次選擇節點加入通信樹時，只選擇與當前節點具有最小權重的節點加入，但是整體通信樹的并發傳輸時間不一定是最小的。本文算法綜合考慮了轉發節點的子節點和子節點所在子樹的最小并發傳輸時間兩方面，并且以全局最優為目標選擇節點進行數據的轉發。因此，轉發路徑選擇算法具有最小的平均并發傳輸時間，較大程度地減少了數據的并發傳輸時間，提高了數據傳輸效率。

圖6 不同網絡節點數量下的平均并發傳輸時間

本文提出的轉發路徑選擇算法與權重優先算法、隨機路徑算法在不同網絡節點數量下的轉發次數如圖7 所示。其中，轉發次數是指從發起節點開始轉發數據直到網絡中最后一個節點接收到數據的總輪次。轉發次數等同于圖3(b)孩子-兄弟通信樹的路徑長度，那么轉發次數越少，路徑長度越短。由于轉發路徑選擇算法相比于隨機路徑選擇算法和權重優先算法，具有較短的傳輸路徑。因此，從圖7 可以看出，本文提出的轉發路徑選擇算法的轉發次數一直是最少的，而權重優先算法和隨機路徑算法的轉發次數較多。隨著網絡節點數量的增加，參與數據轉發的節點數量逐漸增多，所以3 種算法的轉發次數呈逐漸上升趨勢。但是本文提出的轉發路徑選擇算法仍明顯優于其他2 種算法。因此，使用轉發路徑選擇算法完成整個區塊鏈網絡的數據傳輸只需較少的轉發次數。

圖7 不同網絡節點數量下的轉發次數

當節點加入區塊鏈網絡時，節點與其鄰居節點建立拓撲連接，之后利用拓撲動態優化算法加入樹形拓撲，網絡規模擴大。當節點離開網絡時，可能引起樹形拓撲不連通，利用拓撲動態優化算法將其調整為連通的樹形拓撲，網絡規模減小。當節點的可信值以及節點之間的權值發生變化時，可能導致一些節點之間的樹形拓撲結構發生變化，利用拓撲動態優化算法局部調整樹形拓撲，網絡規模不變。不同網絡節點數量下的拓撲調整時間比如圖8 所示，拓撲調整時間比是指采用全網重構拓撲算法與拓撲動態優化算法調整拓撲花費時間的比值。全網重構拓撲算法是指當已生成的樹形拓撲中的節點狀態變化時，利用樹形拓撲構建算法為全網節點建立新的樹形拓撲。由圖8 可知，采用節點間權值變化拓撲動態優化算法調整變化節點的拓撲結構的效果最好。這是因為節點間權值變化拓撲動態優化算法是對權值發生變化的邊進行調整，存在權值發生變化時不需要調整節點之間的拓撲結構，只更新邊的權值的情況。此外，節點加入、節點離開和節點可信值變化拓撲動態優化算法的拓撲調整時間約為全網重構拓撲算法的。因此，針對狀態發生變化的節點，采用拓撲動態優化算法實現拓撲調整花費的時間較少，從而提高了數據的傳輸效率。

圖8 不同網絡節點數量下的拓撲調整時間比

本文提出的拓撲動態優化算法與全網重構拓撲算法在不同網絡節點數量下的節點參與率如圖9所示，節點參與率是指參與調整拓撲的節點個數占網絡總節點數的百分比。參與拓撲結構調整的節點個數越少，說明節點狀態變化影響的范圍越小，則調整拓撲結構花費的時間越少。由圖9 可知，采用拓撲動態優化算法的節點參與率低于20%，顯然優于全網重構拓撲算法，因為拓撲動態優化算法只調整變化節點影響的小范圍局部拓撲結構，不對其他節點的拓撲結構進行改動。節點離開和節點可信值變化拓撲動態優化算法的節點參與率略高于其他2種拓撲動態優化算法，這是因為節點離開拓撲動態優化算法需要刪除離開節點，然后為不連通的多棵子樹進行多輪選邊，而節點可信值變化拓撲動態優化算法利用節點離開拓撲動態優化算法對節點和拓撲進行處理。因此，本文提出的拓撲動態優化算法可以減少調整網絡拓撲所帶來的額外開銷，加快數據之間的傳輸。

圖9 不同網絡節點數量下的節點參與率

4 結束語

本文提出的區塊鏈傳輸效率優化方法由樹形拓撲構建方法、轉發路徑選擇策略和拓撲動態優化策略構成。通過構建的樹形拓撲可以簡化網絡的拓撲結構。轉發路徑選擇策略根據轉發表指導節點進行數據轉發，從而縮短數據傳輸時間。拓撲動態調整策略針對狀態變化節點局部受影響的拓撲進行調整，減少重構全網拓撲所帶來的額外開銷。下一步工作考慮對區塊鏈網絡節點進行分簇，為節點設計一種基于分簇的數據傳輸策略，以加快區塊鏈數據的傳輸，更好地適應于大規模的區塊鏈網絡。

附錄1最小并發傳輸時間證明

證明當節點按照其子節點所在子樹的最小并發傳輸時間由大到小的順序轉發數據時，整體具有最小并發傳輸時間，即證按照此轉發順序構建的通信樹的支路最大傳輸時間是最小的。

假設根節點n0的n個子節點所在子樹的最小并發傳輸時間為W1≥W2≥ …≥Wn，wb是n0與子節點之間的傳輸時間（1 ≤b≤n）。以根節點按照其子節點所在子樹的最小并發傳輸時間由大到小順序轉發數據為基礎，假設并發傳輸時間最大支路中的子節點為nx，支路最大傳輸時間為

任意調換2 個子節點ni和nj的轉發順序后的支路最大傳輸時間為T '，其中，i＜j且Wi≥Wj。

在調換ni和nj轉發順序后，ni和nj所在支路的并發傳輸時間為

已知Wi≥Wi+1≥ …≥Wj，{ni,ni+1,…,nj}中節點所在支路的支路最大傳輸時間為。已知nx為調換前并發傳輸時間最大支路中的節點，下面根據x的取值情況進行討論。

綜上所述，任意調換2 個子節點轉發順序使子節點不按照由大到小順序轉發數據的支路最大傳輸時間'T≥T。因此，當節點按照其子節點所在子樹的最小并發傳輸時間由大到小的順序轉發數據時，整體具有最小并發傳輸時間。

證畢。