區(qū)塊鏈中的自適應(yīng)廣播路由分配算法

秦 毅

(重慶電子工程職業(yè)學(xué)院人工智能與大數(shù)據(jù)學(xué)院 重慶 401331)

0 引 言

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

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

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

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

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

針對以上問題，本文提出了一種區(qū)塊鏈自適應(yīng)廣播路由新方法，該方法從數(shù)據(jù)庫驗證的概念出發(fā)，將區(qū)塊鏈作為分布式AAA模塊在Internet上的礦工主機進行模擬。針對每個礦工主機的加密信息，提出一種應(yīng)用層廣播方法，用于分析加密信息在消息中如何傳播到共享網(wǎng)絡(luò)池中的所有主機，構(gòu)造廣播樹作為覆蓋網(wǎng)絡(luò)拓撲，以最小的延遲提高信息驗證能力，包括通過適當(dāng)?shù)膫鬏斅窂竭x擇來限制傳輸和計算延遲。本文將區(qū)塊鏈的比特幣應(yīng)用的概念擴展到一種新的分布式虛擬機AAA系統(tǒng)結(jié)構(gòu)。

1 區(qū)塊鏈廣播數(shù)學(xué)模型

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

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

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

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

(1)

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

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

(3)

式中：hb表示用于發(fā)送塊b到最遠目標(biāo)節(jié)點的最小跳數(shù)，Db表示塊b的目的地集合。對于每個塊b，每個目標(biāo)節(jié)點的接入鏈路數(shù)應(yīng)等于或小于1，對于?b∈B，則有：

式中：Idb表示目標(biāo)節(jié)點的傳入連接，對于每個塊b，根節(jié)點的接入鏈路數(shù)應(yīng)為0，對于?b∈B，則有：

式中：Irp表示根節(jié)點的傳入連接，對于廣播到目的地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上的所有鏈路應(yīng)設(shè)置為1，對于?b∈B,l∈L,d∈Db，則有：

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

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

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

圖1 包含3個節(jié)點的網(wǎng)絡(luò)

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

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

2 路由路徑設(shè)計和優(yōu)化鏈路分配

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

圖2 無向加權(quán)圖網(wǎng)絡(luò)拓撲

圖3顯示了連接圖中所有節(jié)點的最小總邊緣權(quán)重生成樹。

圖3 最小生成樹

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

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

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

3 實 驗

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

圖5 構(gòu)造廣播樹流程

當(dāng)網(wǎng)絡(luò)鏈路處于空閑狀態(tài)時，廣播樹路由使用最短路徑進行路由，當(dāng)網(wǎng)絡(luò)鏈路處于繁忙狀態(tài)時，使用多徑路由對網(wǎng)絡(luò)壓力進行分擔(dān)，從前k條最少跳數(shù)的備用路徑中隨機分配路徑進行廣播。

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

表1 實驗參數(shù)

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

圖6 不同節(jié)點數(shù)的目標(biāo)值

圖6顯示了當(dāng)節(jié)點數(shù)增加時，目標(biāo)值隨之增加的趨勢，這是因為更大規(guī)模的系統(tǒng)意味著操作員必須花費更多來操作整個系統(tǒng)。

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

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

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

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

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

圖8 不同權(quán)重值的成本評估

當(dāng)權(quán)重較小時，重復(fù)成本增加，但當(dāng)權(quán)重大于0.4時，重復(fù)成本逐漸降低。由于懲罰權(quán)重的增加，重復(fù)成本首先增加，然而在重復(fù)成本增加之后，系統(tǒng)將嘗試尋找另一路徑以實現(xiàn)較低的總成本。當(dāng)選擇不同的路徑時，重復(fù)成本降低。

4 結(jié) 語

為了將SDN和NFV技術(shù)適應(yīng)于分布在邊緣和核心云環(huán)境中的云基礎(chǔ)設(shè)施，提出了區(qū)塊鏈的資源管理。本文提出一種區(qū)塊鏈同步服務(wù)的自適應(yīng)廣播算法，廣播轉(zhuǎn)發(fā)節(jié)點在共享網(wǎng)絡(luò)架構(gòu)中采用具有各種拓撲的廣播和路由策略，以通過較少重用傳輸鏈路來最小化處理和傳輸延遲，分配給AAA服務(wù)、塊或事務(wù)。通過計算實驗說明本文方法的可行性和有效性。