區塊鏈中的自適應廣播路由分配算法

秦 毅

(重慶電子工程職業學院人工智能與大數據學院 重慶 401331)

0 引 言

區塊鏈是一種技術，允許雙方之間記錄交易的每個主機可驗證和永久分散的分類賬[1-2]，較為流行的應用是加密貨幣(如比特幣)。當Internet上的其他主機完成驗證時，最新塊將成為附加區塊鏈的一部分，每個塊包括使用哈希函數和加密密鑰加密的多個事務[3]，塊頭中的元數據集被記錄到關系中并與其他塊鏈接。Internet上的任何主機都可以聯合驗證事務作為驗證貢獻者，并檢查塊是否正確[4]。這種主機的協作稱為比特幣應用程序中的挖掘。

當使用區塊鏈時，該區塊具有一系列過程(如交易和支付)的數字簽名，其可以追溯到個人以進行識別、驗證和確認。節點保持的塊被分散以便共享給每個主機，這種分散的系統可以保護區塊鏈免受篡改、刪除和修改[5]。為了保持分類賬副本的一致性，主機需要就事務達成一致。廣播機制提供由其中一個節點創建的用于暫時提交事務的新塊，并且以規則的間隔同步。該塊被廣播并分發給所有主機以進行驗證和確認[6]，完成確認的最快節點收到獎勵或加密貨幣金額，傳輸和計算延遲是礦工的關鍵因素[7]。

廣播路由機制的服務質量(QoS)路由的目標是找到具有足夠可用資源的可行路徑，以滿足網絡中節點的QoS要求并實現有效的資源使用[8]。延遲、帶寬、延遲抖動、吞吐量和丟包率是將塊廣播到所有礦工主機的路由策略的QoS測量[9]。研究確定優化問題的可行路徑，并找到了成本最低的可行解決方案，文獻[10]對各種QoS路由算法進行了分析，分為源路由算法、分布式路由算法和分層路由算法。文獻[11]提出了最小生成樹(MST)，涉及無向生成樹的分配，當在網絡中使用MST時，考慮QoS問題是必要的，受路由樹的QoS約束的最短路徑問題，MST問題是NP難問題。

目前區塊鏈已經被用于復制因特網上所有礦工設備的交易數據。網絡資源管理已通過軟件定義網絡(software-defined networking, SDN)和網絡功能虛擬化(network function virtualization, NFV)適應資源容器化[12]。SDN是一種可編程機制[13]，可以動態靈活地控制路由路徑和鏈路管理，實現端到端通信。NFV是網絡功能可以轉換為基于軟件的應用程序的概念，可以用于區塊鏈廣播方法。啟用SDN后，可以通過網絡狀態向應用程序通知詳細路由和流量負載信息，這有助于有效地為應用級廣播選擇覆蓋網絡轉發節點。

通過區塊鏈技術引入了三個主要的數據處理任務：1) 中間礦工的交易處理協調；2) 交易處理監控的會話；3) 交易數據到區塊鏈的分布式寫入[15]。在所有節點收到完整消息后，礦工可以收到獎勵，這稱為工作證明，表明每個參與者將驗證結果發送到區塊鏈。生成的塊在構建分布式分類賬的過程中連接到現有的區塊鏈，首先生成此塊的主機有責任將塊廣播到必須將該塊存儲在網絡中的其他主機。但是，在大多數情況下，單播用于發送消息，因為Internet路由器上沒有啟用廣播，或者默認情況下使用正在運行的網絡協議TCP / IP進行切換。單播消息導致許多相同的數據包被重復傳輸，這可能會導致網絡擁塞。

針對以上問題，本文提出了一種區塊鏈自適應廣播路由新方法，該方法從數據庫驗證的概念出發，將區塊鏈作為分布式AAA模塊在Internet上的礦工主機進行模擬。針對每個礦工主機的加密信息，提出一種應用層廣播方法，用于分析加密信息在消息中如何傳播到共享網絡池中的所有主機，構造廣播樹作為覆蓋網絡拓撲，以最小的延遲提高信息驗證能力，包括通過適當的傳輸路徑選擇來限制傳輸和計算延遲。本文將區塊鏈的比特幣應用的概念擴展到一種新的分布式虛擬機AAA系統結構。

1 區塊鏈廣播數學模型

根據AAA體系結構，將塊或事務引入虛擬機(VM)中初始化的VNFS，網絡拓撲由VM初始化，塊的信息，例如用戶標識、身份驗證、授權和委托，使用公鑰密碼進行數字簽名。使用廣播機制在整個網絡拓撲中傳播密碼學，每個收件人可以使用私鑰驗證事務，公開密鑰用于認證和識別。廣播消息可能引起傳播延遲，總延遲被假定為沿著路徑的傳輸和處理時間的組合。

廣播是一種自動通信技術，用于所有礦工主機始終如一地驗證與區塊鏈應用程序相關的重要數據，如事務和分類賬。然而，廣播環境的保密性和有效性應予以考慮，維護分散的功能驗證和性能是NP問題。該問題可以用廣播樹模型抽象地構造和建模，該模型具有資源分配和路由分配問題。

本文提出了一種廣播方案，用于分析區塊鏈所采用的加密信息如何將消息傳播到Internet上的每個節點。網絡拓撲可以由廣播樹的成本來構造，從覆蓋網絡的角度以最小延遲(包括傳輸和處理延遲)來改進信息驗證能力。

xp和ybl表示決策變量，對于塊b的目的地d，如果路徑p∈Pbd被選中，則xp為1，否則為0，其中Pbd表示塊b的目的地d的候選路徑集合d∈Db，Db表示塊b的目的地集合。如果塊b采用鏈路l，則ybl為1，否則為0。目標函數為：

(1)

式中：αl表示鏈路上的傳輸成本，βl表示鏈路上的處理成本，γbl表示對于塊b鏈路l∈L上的懲罰成本，L表示覆蓋網絡中的鏈路集{1,2,…,l}，ybl受制于：每個塊b被選擇為采用鏈路l(等于1)或不采用鏈路l(等于0)，對于?b∈B,l∈L，則有：

B表示所有需要向礦工主機廣播的塊{1,2,…,b}，對于每個塊b，采用的鏈路數應大于到最遠節點的跳躍時間和目標節點的數量，對于?b∈B，則有：

(3)

式中：hb表示用于發送塊b到最遠目標節點的最小跳數，Db表示塊b的目的地集合。對于每個塊b，每個目標節點的接入鏈路數應等于或小于1，對于?b∈B，則有：

式中：Idb表示目標節點的傳入連接，對于每個塊b，根節點的接入鏈路數應為0，對于?b∈B，則有：

式中：Irp表示根節點的傳入連接，對于廣播到目的地d的每個塊b，只采用一條路徑，對于?b∈B,d∈Db，有：

式中：Pbd表示塊b的目的地d的候選路徑集合d∈Db，Db表示塊b的目的地集合。對于廣播到目的地d的每個塊b，可以采用許多路徑(如果選擇采用路徑p，則決策變量等于1)或不采用路徑p，則決策變量等于0，如下所示：

式(7)的約束條件為：?b∈B,p∈Pbd,d∈Db，對于廣播到目的地d的每個塊b，如果采用路徑p，則路徑p上的所有鏈路應設置為1，對于?b∈B,l∈L,d∈Db，則有：

式中：δpl表示指示函數，如果鏈路l在路徑p上，則為1，否則為0，對于每個塊b廣播到所有目的節點，如果已采用鏈路l，則采用的總次數l應小于目的節點數，對于?b∈B,l∈L，則有：

為了找到塊b的懲罰成本，將鏈接的懲罰(如果在塊b-1中被采用)和塊b-1的懲罰成本線性組合，對于?b∈B,l∈L，有：

對于廣播策略的中繼轉發選擇通過一個實例進行說明，以包含3個節點的網絡進行舉例，如圖1所示。對于網絡中廣播中繼轉發一般是以減少能耗為目的的，但同時會參考節點位置分布和所處環境進行選擇。本次實例忽略參數變化，重點研究最小傳輸能耗與位置分布的關系，圖1中網絡中的3個節點都具有全向天線，D12、D13、D23分別代表節點1和2之間的距離、節點1和3之間的距離、節點2和3之間的距離。

圖1 包含3個節點的網絡

對于圖1中網絡，節點1有兩個廣播再轉發策略：(1) 直接向節點2和3進行消息廣播，此時能耗為E；(2) 通過中繼節點2向節點3廣播數據包，此時能耗為E′=E12+E23。根據文獻[16]無線廣播算法中概率模型與能耗模型的計算表達式，當E>E′時，第2種廣播策略能耗更小，當E

通過文獻[16]中對不同位置的節點的能耗分析，可以得出：在網絡拓撲結構中，廣播策略中使得能耗最小的路徑選擇，與節點位置相關，因為位置不同，使得有時通過中繼轉發消耗的能量小，有時直接傳輸信息消耗的能量小。本文對于廣播策略中路徑設計和優化過程是將廣播模型作為一個最小生成樹問題求解本文目標函數的最小成本，具體過程在第2節中給出。

2 路由路徑設計和優化鏈路分配

為了找到本文目標函數的最小成本，將本文模型看作為一個最小生成樹(Minimum Spanning Tree, MST)問題。如果圖形具有n個頂點，則每個樹具有n-1個邊；最小化總邊緣權重。圖2顯示了連接的無向加權圖，應用MST算法后，可以找到該圖的MST。

圖2 無向加權圖網絡拓撲

圖3顯示了連接圖中所有節點的最小總邊緣權重生成樹。

圖3 最小生成樹

在本文數學模型中，鏈路上的最大聚合延遲是沿樹的源節點到目的節點之間的傳輸延遲和進程延遲的組合，但是，應考慮廣播環境的機密性和有效性。通過在使用鏈路后添加懲罰，解決方案將避免廣播選擇相同的鏈路，為每個廣播塊提供隨機拓撲。

(a) 第一個廣播塊的MST (b) 添加重復懲罰

(c) 隨機路徑 (d) 隨機路徑圖4 每個廣播塊的MST

3 實 驗

根據第2節中所提公式，將每個塊廣播視為單獨的MST問題，每條鏈路上的權重是傳輸成本、處理成本和重用鏈路的懲罰成本的組合。本文實驗使用Prim算法來解決隨后的塊廣播中的每個單獨的MST問題，并獲得作為實驗結果的總目標值。本文實驗硬件環境是筆記本電腦，具有Windows 7系統，4 GB運行內存，500 GB磁盤內存，實驗軟件環境是MATLAB 2013a。實驗中廣播樹的構造如圖5所示。

圖5 構造廣播樹流程

當網絡鏈路處于空閑狀態時，廣播樹路由使用最短路徑進行路由，當網絡鏈路處于繁忙狀態時，使用多徑路由對網絡壓力進行分擔，從前k條最少跳數的備用路徑中隨機分配路徑進行廣播。

在本文中，進行了幾個實驗來驗證提出的模型，并比較不同情況下的結果。為了比較實驗之間的差異，將固定值分配給模型中的某些給定參數，表1顯示了實驗中使用的給定參數的屬性。通過將隨機數分別乘以傳輸權重和計算權重，隨機分配每個鏈路的傳輸成本和每個節點的計算成本。如果在以下實驗中未用作獨立變量，表1中指定的值是每個參數的默認值。

表1 實驗參數

首先對節點數量和模型的目標值之間的關系進行實驗。在現實使用中，節點的數量可以被認為是系統的規模。擁有更大規模系統的運營商將擁有比在小型系統中運營的運營商更多的節點。為了進行實驗，在每個測試中保持每個參數的值相同。這種情況首先將節點數調整為10, 20,…, 90，結果如圖6所示。

圖6 不同節點數的目標值

圖6顯示了當節點數增加時，目標值隨之增加的趨勢，這是因為更大規模的系統意味著操作員必須花費更多來操作整個系統。

然后對不同核心比率時成本變化趨勢進行實驗驗證。在實驗中，所有節點分為兩種類型：核心節點和邊緣節點，在現實使用中，系統也分為核心和邊緣計算節點。核心計算節點具有更強大的計算能力但節點之間的傳輸成本更高，邊緣計算節點功能較弱但傳輸成本較低。為這兩種節點類型分配不同的核心比率，從0.2到0.6(邊緣比率分別為0.8到0.4)，結果如圖7所示，提供了有關不同分配比率的模型中提到的不同類型成本變化的信息。

圖7 不同核心比率的成本分布評估

從圖中可以看出，隨著核心比率的增加，總成本也會增加，但逐漸達到最大值，傳輸成本以類似的方式呈現，但最后略有減少。這是因為當核心比率首先增加時，一些節點加入核心節點，從而增加傳輸成本，但核心比率不斷增加，兩種節點的傳輸成本平衡并達到最大值。

當核心比率增加時，計算成本降低并達到最小值，設置為核心節點的邊緣節點越多，系統的計算能力就越高，這導致整個系統的計算成本下降。當核心比率增加時，重復成本增加并逐漸達到最大值。這表明當兩種類型的節點的比率變得更加平衡時，其重復成本增加，較低的核心比率將導致較低的重復成本。

最后對各種重復懲罰權重時成本的變化進行實驗。在現實使用中，重復懲罰權重可以被看作是操作者反復使用鏈接的緊迫性。圖8給出了從0到1分配權重的實驗結果。

圖8 不同權重值的成本評估

當權重較小時，重復成本增加，但當權重大于0.4時，重復成本逐漸降低。由于懲罰權重的增加，重復成本首先增加，然而在重復成本增加之后，系統將嘗試尋找另一路徑以實現較低的總成本。當選擇不同的路徑時，重復成本降低。

4 結 語

為了將SDN和NFV技術適應于分布在邊緣和核心云環境中的云基礎設施，提出了區塊鏈的資源管理。本文提出一種區塊鏈同步服務的自適應廣播算法，廣播轉發節點在共享網絡架構中采用具有各種拓撲的廣播和路由策略，以通過較少重用傳輸鏈路來最小化處理和傳輸延遲，分配給AAA服務、塊或事務。通過計算實驗說明本文方法的可行性和有效性。