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

秦 毅

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

0 引 言

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

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

廣播路由機(jī)制的服務(wù)質(zhì)量(QoS)路由的目標(biāo)是找到具有足夠可用資源的可行路徑，以滿足網(wǎng)絡(luò)中節(jié)點(diǎn)的QoS要求并實(shí)現(xiàn)有效的資源使用[8]。延遲、帶寬、延遲抖動(dòng)、吞吐量和丟包率是將塊廣播到所有礦工主機(jī)的路由策略的QoS測(cè)量[9]。研究確定優(yōu)化問題的可行路徑，并找到了成本最低的可行解決方案，文獻(xiàn)[10]對(duì)各種QoS路由算法進(jìn)行了分析，分為源路由算法、分布式路由算法和分層路由算法。文獻(xiàn)[11]提出了最小生成樹(MST)，涉及無向生成樹的分配，當(dāng)在網(wǎng)絡(luò)中使用MST時(shí)，考慮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是一種可編程機(jī)制[13]，可以動(dòng)態(tài)靈活地控制路由路徑和鏈路管理，實(shí)現(xiàn)端到端通信。NFV是網(wǎng)絡(luò)功能可以轉(zhuǎn)換為基于軟件的應(yīng)用程序的概念，可以用于區(qū)塊鏈廣播方法。啟用SDN后，可以通過網(wǎng)絡(luò)狀態(tài)向應(yīng)用程序通知詳細(xì)路由和流量負(fù)載信息，這有助于有效地為應(yīng)用級(jí)廣播選擇覆蓋網(wǎng)絡(luò)轉(zhuǎn)發(fā)節(jié)點(diǎn)。

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

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

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

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

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

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

xp和ybl表示決策變量，對(duì)于塊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表示對(duì)于塊b鏈路l∈L上的懲罰成本，L表示覆蓋網(wǎng)絡(luò)中的鏈路集{1,2,…,l}，ybl受制于：每個(gè)塊b被選擇為采用鏈路l(等于1)或不采用鏈路l(等于0)，對(duì)于?b∈B,l∈L，則有：

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

(3)

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

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

式中：Irp表示根節(jié)點(diǎn)的傳入連接，對(duì)于廣播到目的地d的每個(gè)塊b，只采用一條路徑，對(duì)于?b∈B,d∈Db，有：

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

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

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

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

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

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

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

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

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

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

圖2 無向加權(quán)圖網(wǎng)絡(luò)拓?fù)?/p>

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

圖3 最小生成樹

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

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

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

3 實(shí) 驗(yàn)

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

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

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

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

表1 實(shí)驗(yàn)參數(shù)

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

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

圖6顯示了當(dāng)節(jié)點(diǎn)數(shù)增加時(shí)，目標(biāo)值隨之增加的趨勢(shì)，這是因?yàn)楦笠?guī)模的系統(tǒng)意味著操作員必須花費(fèi)更多來操作整個(gè)系統(tǒng)。

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

圖7 不同核心比率的成本分布評(píng)估

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

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

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

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

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

4 結(jié) 語

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