霍如，程祥鳳，孫闖，汪碩，黃韜，F(xiàn).Richard Yu

（1.北京工業(yè)大學(xué)信息學(xué)部，北京 100124；2.網(wǎng)絡(luò)通信與安全紫金山實(shí)驗(yàn)室，江蘇 南京 211111；3.清華大學(xué)自動(dòng)化系，北京 100084；4.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876；5.加拿大卡爾頓大學(xué)信息技術(shù)學(xué)院，渥太華 KIS 5B6）

0 引言

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

區(qū)塊鏈網(wǎng)絡(luò)層為區(qū)塊鏈提供底層的網(wǎng)絡(luò)支撐，搭建節(jié)點(diǎn)之間的數(shù)據(jù)傳輸環(huán)境。網(wǎng)絡(luò)層包含2 種機(jī)制，即對(duì)等（P2P,peer-to-peer）網(wǎng)絡(luò)、數(shù)據(jù)傳輸和數(shù)據(jù)驗(yàn)證機(jī)制[6]。區(qū)塊鏈網(wǎng)絡(luò)包括無(wú)結(jié)構(gòu)、結(jié)構(gòu)化和混合式P2P 網(wǎng)絡(luò)[2]。其中，無(wú)結(jié)構(gòu)P2P 網(wǎng)絡(luò)是指具有隨機(jī)圖拓?fù)浣Y(jié)構(gòu)的P2P 網(wǎng)絡(luò)。如何優(yōu)化區(qū)塊鏈網(wǎng)絡(luò)層從而縮短數(shù)據(jù)傳輸時(shí)間是擴(kuò)展區(qū)塊鏈性能的一個(gè)重要研究方向[7]。

目前，很多研究通過(guò)改進(jìn)區(qū)塊鏈網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)傳輸方法來(lái)提高區(qū)塊鏈數(shù)據(jù)傳輸效率。在區(qū)塊鏈網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究方面，Sung 等[8]通過(guò)建立數(shù)學(xué)模型將數(shù)據(jù)傳輸路徑轉(zhuǎn)化為最小生成樹(shù)問(wèn)題，減少傳輸鏈路的重用來(lái)最小化處理和傳輸時(shí)延。Li 等[9]提出一種權(quán)重優(yōu)先算法，該算法逐次選取通信權(quán)重小以及傳輸能力強(qiáng)的節(jié)點(diǎn)構(gòu)建通信樹(shù)，為區(qū)塊鏈交易提供路徑，從而提高區(qū)塊鏈的通信效率。Lin 等[10]根據(jù)節(jié)點(diǎn)的可信度和中心性提出一種可靠的去中心化樹(shù)形算法，該算法利用Prim 算法構(gòu)建通信樹(shù)，提高了區(qū)塊鏈交易的速度和可靠性。在區(qū)塊鏈數(shù)據(jù)傳輸方法研究方面，Ersoy 等[11]提出一種傳輸激勵(lì)機(jī)制，節(jié)點(diǎn)向鄰居節(jié)點(diǎn)傳輸交易時(shí)，可以獲得交易費(fèi)的一部分作為獎(jiǎng)勵(lì)，鼓勵(lì)更多節(jié)點(diǎn)參與交易的傳輸，降低區(qū)塊鏈傳輸時(shí)間。Santiago 等[12]提出一種基于權(quán)重的鄰居選擇方法，通過(guò)不斷探測(cè)節(jié)點(diǎn)的新鄰居并更新節(jié)點(diǎn)間的權(quán)重，增加選擇最佳通信節(jié)點(diǎn)的概率，減少區(qū)塊鏈網(wǎng)絡(luò)的消息傳播時(shí)間。Hao 等[13]從區(qū)塊鏈網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)傳輸方法兩方面改進(jìn)，對(duì)節(jié)點(diǎn)聚類生成的集群構(gòu)建信任增強(qiáng)的區(qū)塊鏈P2P 網(wǎng)絡(luò)拓?fù)?，采用并行生成?shù)算法進(jìn)行數(shù)據(jù)傳輸，在加快區(qū)塊鏈傳輸速率的同時(shí)保證傳輸?shù)目煽啃浴?/p>

上述研究未考慮節(jié)點(diǎn)狀態(tài)變化對(duì)已建立的網(wǎng)絡(luò)拓?fù)洚a(chǎn)生的影響[8-10]。如果區(qū)塊鏈節(jié)點(diǎn)狀態(tài)發(fā)生變化，只能重新構(gòu)建拓?fù)浣Y(jié)構(gòu)，從而影響區(qū)塊鏈傳輸效率。此外，大多數(shù)研究只考慮對(duì)區(qū)塊鏈網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)傳輸方法的單方面改進(jìn)，很少有結(jié)合兩方面的改進(jìn)?；谏鲜鰡?wèn)題，本文針對(duì)區(qū)塊鏈網(wǎng)絡(luò)拓?fù)浜娃D(zhuǎn)發(fā)策略進(jìn)行優(yōu)化，通過(guò)設(shè)計(jì)的可信值函數(shù)計(jì)算節(jié)點(diǎn)可信值，綜合考慮節(jié)點(diǎn)可信值和節(jié)點(diǎn)之間的傳輸時(shí)間，提出樹(shù)形拓?fù)錁?gòu)建方法，在生成的樹(shù)形拓?fù)浠A(chǔ)上，設(shè)計(jì)一種轉(zhuǎn)發(fā)路徑選擇策略和拓?fù)鋭?dòng)態(tài)優(yōu)化策略，從而縮短數(shù)據(jù)傳輸時(shí)間，提高區(qū)塊鏈傳輸效率。本文主要的研究工作如下。

1) 提出樹(shù)形拓?fù)錁?gòu)建方法。首先，利用設(shè)計(jì)的可信值函數(shù)得到每個(gè)節(jié)點(diǎn)的可信值，根據(jù)可信值閾值劃分節(jié)點(diǎn)類型。然后，對(duì)可信節(jié)點(diǎn)采用Sollin 算法構(gòu)建最小生成樹(shù)，將不可信節(jié)點(diǎn)加入拓?fù)洌瓿蓸?shù)形拓?fù)涞臉?gòu)建，簡(jiǎn)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并提高數(shù)據(jù)傳輸過(guò)程中的安全性。

2) 設(shè)計(jì)轉(zhuǎn)發(fā)路徑選擇策略。該策略以最小整體并發(fā)傳輸時(shí)間為目標(biāo)，為每個(gè)區(qū)塊鏈節(jié)點(diǎn)建立關(guān)于其鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)次序的轉(zhuǎn)發(fā)表，節(jié)點(diǎn)根據(jù)轉(zhuǎn)發(fā)表依次選擇其鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，使整個(gè)傳輸過(guò)程具有最小并發(fā)傳輸時(shí)間，有效縮短數(shù)據(jù)傳輸時(shí)間，同時(shí)避免對(duì)節(jié)點(diǎn)重復(fù)傳輸同一數(shù)據(jù)。

3) 設(shè)計(jì)拓?fù)鋭?dòng)態(tài)優(yōu)化策略。針對(duì)節(jié)點(diǎn)加入、節(jié)點(diǎn)離開(kāi)、節(jié)點(diǎn)可信值變化和節(jié)點(diǎn)間權(quán)值變化情況，利用破圈法和Sollin 算法設(shè)計(jì)了相應(yīng)的拓?fù)鋭?dòng)態(tài)優(yōu)化策略，只對(duì)節(jié)點(diǎn)狀態(tài)變化影響的部分拓?fù)浣Y(jié)構(gòu)進(jìn)行調(diào)整。與全網(wǎng)重構(gòu)拓?fù)湎啾?，該策略花費(fèi)的代價(jià)較小，并且能夠減少對(duì)拓?fù)溥M(jìn)行調(diào)整所帶來(lái)的開(kāi)銷(xiāo)。

1 區(qū)塊鏈傳輸效率優(yōu)化方法

為了縮短區(qū)塊鏈交易數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸時(shí)間，本文從區(qū)塊鏈網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)的轉(zhuǎn)發(fā)策略兩方面進(jìn)行改進(jìn)，提出區(qū)塊鏈傳輸效率優(yōu)化方法，如圖1 所示。其中，樹(shù)形拓?fù)錁?gòu)建模型負(fù)責(zé)生成區(qū)塊鏈網(wǎng)絡(luò)的樹(shù)形拓?fù)?，轉(zhuǎn)發(fā)路徑選擇模型基于樹(shù)形拓?fù)浣Y(jié)構(gòu)為區(qū)塊鏈節(jié)點(diǎn)建立轉(zhuǎn)發(fā)路徑，拓?fù)鋭?dòng)態(tài)優(yōu)化模型主要對(duì)樹(shù)形拓?fù)渲袪顟B(tài)發(fā)生變化的節(jié)點(diǎn)局部拓?fù)溥M(jìn)行調(diào)整。

圖1 區(qū)塊鏈傳輸效率優(yōu)化方法

樹(shù)形拓?fù)錁?gòu)建模型主要負(fù)責(zé)將區(qū)塊鏈無(wú)結(jié)構(gòu)P2P 網(wǎng)絡(luò)構(gòu)建為樹(shù)形拓?fù)浣Y(jié)構(gòu)，通過(guò)優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來(lái)減少冗余傳輸?？紤]到數(shù)據(jù)傳輸過(guò)程中的安全性問(wèn)題，設(shè)定節(jié)點(diǎn)可信值函數(shù)并結(jié)合可信值閾值將區(qū)塊鏈網(wǎng)絡(luò)節(jié)點(diǎn)劃分為可信節(jié)點(diǎn)和不可信節(jié)點(diǎn)，其中，可信值大于閾值的節(jié)點(diǎn)為可信節(jié)點(diǎn)，否則為不可信節(jié)點(diǎn)。針對(duì)可信節(jié)點(diǎn)和不可信節(jié)點(diǎn)采用不同的方式構(gòu)建網(wǎng)絡(luò)的樹(shù)形拓?fù)洹?/p>

轉(zhuǎn)發(fā)路徑選擇模型基于樹(shù)形拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)區(qū)塊鏈節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)策略，以加快數(shù)據(jù)的傳輸。首先，為每個(gè)節(jié)點(diǎn)建立關(guān)于其鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)表，轉(zhuǎn)發(fā)表中的節(jié)點(diǎn)依據(jù)其鄰居節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間由大到小順序依次存放。然后，從發(fā)起節(jié)點(diǎn)開(kāi)始轉(zhuǎn)發(fā)數(shù)據(jù)，節(jié)點(diǎn)按照轉(zhuǎn)發(fā)表中的次序向未接收數(shù)據(jù)的鄰居節(jié)點(diǎn)傳輸數(shù)據(jù)，經(jīng)過(guò)多輪次的數(shù)據(jù)轉(zhuǎn)發(fā)，從而使全網(wǎng)節(jié)點(diǎn)接收到數(shù)據(jù)。

拓?fù)鋭?dòng)態(tài)優(yōu)化模型根據(jù)區(qū)塊鏈節(jié)點(diǎn)的狀態(tài)變化情況，包括節(jié)點(diǎn)加入、節(jié)點(diǎn)離開(kāi)、節(jié)點(diǎn)可信值變化和節(jié)點(diǎn)間權(quán)值變化，分別設(shè)計(jì)了拓?fù)鋭?dòng)態(tài)優(yōu)化策略，降低調(diào)整網(wǎng)絡(luò)拓?fù)涞拈_(kāi)銷(xiāo)。當(dāng)區(qū)塊鏈網(wǎng)絡(luò)的節(jié)點(diǎn)狀態(tài)發(fā)生變化時(shí)，拓?fù)鋭?dòng)態(tài)優(yōu)化模型選擇相應(yīng)的拓?fù)鋭?dòng)態(tài)優(yōu)化策略來(lái)調(diào)整因節(jié)點(diǎn)狀態(tài)變化所影響的局部拓?fù)浣Y(jié)構(gòu)，然后更新樹(shù)形拓?fù)浣Y(jié)構(gòu)。

在區(qū)塊鏈網(wǎng)絡(luò)中，使用本文提出的區(qū)塊鏈傳輸效率優(yōu)化方法對(duì)P2P 網(wǎng)絡(luò)建立樹(shù)形拓?fù)湟约吧晒?jié)點(diǎn)的轉(zhuǎn)發(fā)表，由記賬節(jié)點(diǎn)作為數(shù)據(jù)發(fā)起節(jié)點(diǎn)開(kāi)始傳輸交易數(shù)據(jù)。在數(shù)據(jù)傳輸過(guò)程中，節(jié)點(diǎn)按照轉(zhuǎn)發(fā)路徑選擇策略進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。節(jié)點(diǎn)在接收到交易數(shù)據(jù)后會(huì)驗(yàn)證交易的合法性，若交易合法，則存儲(chǔ)到賬本。如果節(jié)點(diǎn)狀態(tài)變化導(dǎo)致樹(shù)形拓?fù)浒l(fā)生改變，則利用拓?fù)鋭?dòng)態(tài)優(yōu)化策略局部調(diào)整樹(shù)形拓?fù)洹?/p>

1.1 樹(shù)形拓?fù)錁?gòu)建方法

本文將區(qū)塊鏈網(wǎng)絡(luò)拓?fù)涑橄鬄閳D，節(jié)點(diǎn)之間的路徑抽象為邊，邊的權(quán)值代表節(jié)點(diǎn)之間的數(shù)據(jù)傳輸時(shí)間?？紤]節(jié)點(diǎn)的可信值和節(jié)點(diǎn)之間的權(quán)值，提出樹(shù)形拓?fù)錁?gòu)建方法生成樹(shù)形拓?fù)浣Y(jié)構(gòu)，簡(jiǎn)化網(wǎng)絡(luò)拓?fù)涞耐瑫r(shí)提高數(shù)據(jù)傳輸過(guò)程的安全性。

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

其中，i為節(jié)點(diǎn)的標(biāo)號(hào)；s為節(jié)點(diǎn)交易成功的總次數(shù)；u為節(jié)點(diǎn)交易失敗的總次數(shù)；n為節(jié)點(diǎn)交易失敗到下一次失敗之間累計(jì)的連續(xù)交易成功次數(shù)；為獎(jiǎng)勵(lì)函數(shù)，表示給予交易成功節(jié)點(diǎn)的可信值獎(jiǎng)勵(lì)，交易成功的次數(shù)越多，節(jié)點(diǎn)獲得的獎(jiǎng)勵(lì)值越大，激勵(lì)節(jié)點(diǎn)進(jìn)行更多成功的交易；φ(n) 是懲罰函數(shù)，在節(jié)點(diǎn)交易失敗時(shí)，懲罰函數(shù)會(huì)降低節(jié)點(diǎn)的可信值。懲罰函數(shù)定義為

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

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

Sollin 算法是一種結(jié)合Prim 和Kruskal 算法思想構(gòu)建的最小生成樹(shù)算法，其每次迭代可同時(shí)擴(kuò)展多棵子樹(shù)，使其建樹(shù)的效率較高。因此，本文采用Sollin 算法構(gòu)建最小生成樹(shù)。本文提出的樹(shù)形拓?fù)錁?gòu)建方法對(duì)可信節(jié)點(diǎn)和不可信節(jié)點(diǎn)按不同的方式構(gòu)建網(wǎng)絡(luò)的樹(shù)形拓?fù)?。在可信拓?fù)浠A(chǔ)上，該算法首先利用Sollin 算法根據(jù)可信節(jié)點(diǎn)之間的邊和權(quán)值，選擇權(quán)值最小邊構(gòu)建最小生成樹(shù)，生成可信樹(shù)形拓?fù)?；然后，?duì)不可信節(jié)點(diǎn)進(jìn)行處理，選擇與可信鄰居節(jié)點(diǎn)相連的權(quán)值最小邊加入樹(shù)形拓?fù)?，不可信?jié)點(diǎn)作為樹(shù)形拓?fù)涞娜~子節(jié)點(diǎn)；將所有不可信節(jié)點(diǎn)加入樹(shù)形拓?fù)渲笸瓿删W(wǎng)絡(luò)樹(shù)形拓?fù)涞臉?gòu)建。

構(gòu)建網(wǎng)絡(luò)的樹(shù)形拓?fù)涫纠鐖D 2 所示，{n0,n1,n2,n3,n5}為可信節(jié)點(diǎn)集，{n4,n6}為不可信節(jié)點(diǎn)集。首先，利用Sollin 算法對(duì)集合 {n0,n1,n2,n3,n5}中的可信節(jié)點(diǎn)逐次選取權(quán)值最小邊構(gòu)建一棵最小生成樹(shù)，得到圖2 中的實(shí)線邊即最小生成樹(shù)的邊。然后，不可信節(jié)點(diǎn)n4在其可信鄰居節(jié)點(diǎn) {n2,n3,n5}中選擇權(quán)值最小邊w2,4加入樹(shù)形拓?fù)?。同理可知，不可信?jié)點(diǎn)n6選擇w0,6加入樹(shù)形拓?fù)?，從而完成區(qū)塊鏈網(wǎng)絡(luò)的樹(shù)形拓?fù)錁?gòu)建。

圖2 構(gòu)建網(wǎng)絡(luò)的樹(shù)形拓?fù)涫纠?/p>

通過(guò)樹(shù)形拓?fù)錁?gòu)建方法將原本的區(qū)塊鏈無(wú)結(jié)構(gòu)P2P 網(wǎng)絡(luò)拓?fù)錁?gòu)建為樹(shù)形拓?fù)洌瑯O大地簡(jiǎn)化了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。樹(shù)形拓?fù)浣Y(jié)合了可信值和最小生成樹(shù)的優(yōu)勢(shì)，并且將不可信節(jié)點(diǎn)作為樹(shù)的葉子節(jié)點(diǎn)，很大程度上提高了數(shù)據(jù)傳輸過(guò)程中的安全性，而且由于樹(shù)形拓?fù)渚哂懈〉臋?quán)值之和，因此有效地縮短了區(qū)塊鏈整體的數(shù)據(jù)傳輸時(shí)間。

1.2 轉(zhuǎn)發(fā)路徑選擇策略

區(qū)塊鏈采用P2P 網(wǎng)絡(luò)組織節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)傳輸，每個(gè)節(jié)點(diǎn)都獨(dú)立承擔(dān)驗(yàn)證數(shù)據(jù)、網(wǎng)絡(luò)路由、轉(zhuǎn)發(fā)數(shù)據(jù)和發(fā)現(xiàn)新節(jié)點(diǎn)等任務(wù)[15]。本文采用并發(fā)傳輸機(jī)制，即獲得數(shù)據(jù)的不同節(jié)點(diǎn)可以在同一時(shí)間段內(nèi)轉(zhuǎn)發(fā)數(shù)據(jù)，實(shí)現(xiàn)不同節(jié)點(diǎn)之間的并發(fā)傳輸。節(jié)點(diǎn)通過(guò)并發(fā)傳輸機(jī)制進(jìn)行數(shù)據(jù)傳輸花費(fèi)的時(shí)間稱為并發(fā)傳輸時(shí)間。基于并發(fā)傳輸機(jī)制，本文設(shè)計(jì)了一種轉(zhuǎn)發(fā)路徑選擇策略，指導(dǎo)節(jié)點(diǎn)選擇鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。該策略首先為樹(shù)形拓?fù)渲械拿總€(gè)節(jié)點(diǎn)建立關(guān)于其鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)表，然后設(shè)置節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的規(guī)則。由并發(fā)傳輸過(guò)程構(gòu)建孩子-兄弟通信樹(shù)示例如圖3 所示。

圖3 由并發(fā)傳輸過(guò)程構(gòu)建孩子-兄弟通信樹(shù)示例

設(shè)Tree=(V,E,W)是一個(gè)樹(shù)形拓?fù)?，并發(fā)傳輸過(guò)程如圖3(a)所示。圖3(a)中虛線框內(nèi)的數(shù)字為轉(zhuǎn)發(fā)輪次，表示節(jié)點(diǎn)經(jīng)過(guò)第幾輪次轉(zhuǎn)發(fā)后接收到數(shù)據(jù)。從v0開(kāi)始轉(zhuǎn)發(fā)數(shù)據(jù)，下面以節(jié)點(diǎn)間的前兩輪轉(zhuǎn)發(fā)為例介紹并發(fā)傳輸。在第一輪轉(zhuǎn)發(fā)中，v0將數(shù)據(jù)傳輸給v1。在第二輪轉(zhuǎn)發(fā)中，由于v1已經(jīng)從v0接收到數(shù)據(jù)，因此v1將數(shù)據(jù)轉(zhuǎn)發(fā)給下一個(gè)子節(jié)點(diǎn)vv4，0也繼續(xù)向v2傳輸數(shù)據(jù)。

為了研究節(jié)點(diǎn)如何選擇鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)使整個(gè)數(shù)據(jù)傳輸過(guò)程花費(fèi)的并發(fā)傳輸時(shí)間最小，本文引入孩子-兄弟通信樹(shù)，如圖3(b)所示。圖3(b)中的孩子-兄弟通信樹(shù)是根據(jù)圖3(a)中的并發(fā)傳輸過(guò)程建立的，節(jié)點(diǎn)v0的深度為0。以節(jié)點(diǎn)v2為例介紹孩子-兄弟通信樹(shù)的構(gòu)建過(guò)程如下。由于在圖3(a)中v0先將數(shù)據(jù)轉(zhuǎn)發(fā)給v1，那么在圖3(b)中v1為v0的左孩子。之后v0轉(zhuǎn)發(fā)數(shù)據(jù)給v2，那么在圖3(b)中v2為v1的右兄弟。孩子-兄弟通信樹(shù)中節(jié)點(diǎn)的深度代表節(jié)點(diǎn)在并發(fā)傳輸過(guò)程中第幾輪次接收到數(shù)據(jù)，即節(jié)點(diǎn)并發(fā)傳輸?shù)霓D(zhuǎn)發(fā)輪次。在孩子-兄弟通信樹(shù)中，計(jì)算某個(gè)支路的通信時(shí)間只需計(jì)算從發(fā)起節(jié)點(diǎn)到該支路最后一個(gè)節(jié)點(diǎn)所經(jīng)過(guò)的邊的權(quán)值之和。由此借助孩子-兄弟通信樹(shù)把研究從發(fā)起節(jié)點(diǎn)傳輸數(shù)據(jù)到全網(wǎng)節(jié)點(diǎn)花費(fèi)的最小并發(fā)通信時(shí)間這個(gè)問(wèn)題轉(zhuǎn)化為最小化孩子-兄弟通信樹(shù)中的支路最大傳輸時(shí)間問(wèn)題。其中，支路最大傳輸時(shí)間是指在所有支路傳輸時(shí)間中并發(fā)傳輸時(shí)間最大的支路時(shí)間。當(dāng)節(jié)點(diǎn)按照它的鄰居節(jié)點(diǎn)（子節(jié)點(diǎn)）所在子樹(shù)的最小并發(fā)傳輸時(shí)間由大到小順序選擇鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，能使從發(fā)起節(jié)點(diǎn)傳輸數(shù)據(jù)到全網(wǎng)節(jié)點(diǎn)花費(fèi)的并發(fā)傳輸時(shí)間最小，證明過(guò)程如附錄1 所示?；谏鲜鏊枷耄疚臑槊總€(gè)節(jié)點(diǎn)建立各自的轉(zhuǎn)發(fā)表，轉(zhuǎn)發(fā)表中按照最小并發(fā)傳輸時(shí)間由大到小的順序，依次存儲(chǔ)節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)的名稱和鄰居節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間。轉(zhuǎn)發(fā)表的建立過(guò)程如下。首先隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，得到以該節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)形拓?fù)洌蝗缓?，?jīng)過(guò)自底向上和自頂向下2個(gè)過(guò)程建立每個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)表。

1) 自底向上

自底向上建立節(jié)點(diǎn)轉(zhuǎn)發(fā)表的過(guò)程是以最小整體并發(fā)傳輸時(shí)間為目標(biāo)，從樹(shù)形拓?fù)涞娜~子節(jié)點(diǎn)逐步向根節(jié)點(diǎn)方向計(jì)算節(jié)點(diǎn)的子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)通信時(shí)間，子節(jié)點(diǎn)向父節(jié)點(diǎn)發(fā)送計(jì)算結(jié)果，父節(jié)點(diǎn)存儲(chǔ)結(jié)果并依次計(jì)算以及向上發(fā)送結(jié)果，直到根節(jié)點(diǎn)為止。由于葉子節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，因此葉子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間為0，將0 發(fā)送給它的父節(jié)點(diǎn)，父節(jié)點(diǎn)按照最小并發(fā)傳輸時(shí)間由大到小的順序，存儲(chǔ)該葉子節(jié)點(diǎn)名稱和它所在子樹(shù)的最小并發(fā)傳輸時(shí)間0。針對(duì)節(jié)點(diǎn)是非葉子節(jié)點(diǎn)的情況，在接收到所有子節(jié)點(diǎn)發(fā)送的它們各自所在子樹(shù)的最小并發(fā)傳輸時(shí)間后，根據(jù)它的轉(zhuǎn)發(fā)表和權(quán)值計(jì)算該非葉子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間。將計(jì)算結(jié)果發(fā)送給它的父節(jié)點(diǎn)，父節(jié)點(diǎn)按照由大到小順序進(jìn)行存儲(chǔ)。在同一轉(zhuǎn)發(fā)表中，如果存在多個(gè)子節(jié)點(diǎn)的最小并發(fā)傳輸時(shí)間相同，那么子節(jié)點(diǎn)所在子樹(shù)連通度大的子節(jié)點(diǎn)優(yōu)先存儲(chǔ)；如果連通度相同，則優(yōu)先存儲(chǔ)與節(jié)點(diǎn)相連權(quán)值小的子節(jié)點(diǎn)。當(dāng)根節(jié)點(diǎn)轉(zhuǎn)發(fā)表建立完成時(shí)，則自底向上建立轉(zhuǎn)發(fā)表的過(guò)程結(jié)束。轉(zhuǎn)發(fā)表建立示例如圖4 所示。

圖4 轉(zhuǎn)發(fā)表建立示例

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

2) 自頂向下

當(dāng)自底向上建立轉(zhuǎn)發(fā)表的過(guò)程結(jié)束后，除根節(jié)點(diǎn)外的其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)表中只缺少一項(xiàng)由父節(jié)點(diǎn)作為子節(jié)點(diǎn)時(shí)其所在子樹(shù)的最小并發(fā)傳輸時(shí)間。因此，采用自頂向下過(guò)程補(bǔ)全其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)表。自頂向下建立轉(zhuǎn)發(fā)表的過(guò)程是以最小整體并發(fā)傳輸時(shí)間為目標(biāo)，根據(jù)每個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)表中已存儲(chǔ)的節(jié)點(diǎn)信息，從樹(shù)形拓?fù)涞母?jié)點(diǎn)逐步向葉子節(jié)點(diǎn)方向計(jì)算將父節(jié)點(diǎn)看作子節(jié)點(diǎn)時(shí)其所在子樹(shù)的最小并發(fā)傳輸時(shí)間，完成每個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)表的建立。

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

節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的規(guī)則是將發(fā)起交易數(shù)據(jù)的節(jié)點(diǎn)指定為發(fā)起節(jié)點(diǎn)，并作為樹(shù)形拓?fù)涞母?jié)點(diǎn)，從根節(jié)點(diǎn)開(kāi)始進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，直到樹(shù)中所有節(jié)點(diǎn)接收到數(shù)據(jù)為止。如果節(jié)點(diǎn)是發(fā)起節(jié)點(diǎn)，那么節(jié)點(diǎn)完全按照轉(zhuǎn)發(fā)表依次選擇鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)即可。如果節(jié)點(diǎn)是轉(zhuǎn)發(fā)節(jié)點(diǎn)，不再向給它發(fā)送數(shù)據(jù)的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，按照轉(zhuǎn)發(fā)表依次選取其余節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。本文提出的轉(zhuǎn)發(fā)路徑選擇策略具有最小整體并發(fā)傳輸時(shí)間，有效縮短了數(shù)據(jù)傳輸時(shí)間，同時(shí)避免對(duì)節(jié)點(diǎn)重復(fù)傳輸同一數(shù)據(jù)，極大提高了區(qū)塊鏈的傳輸效率。

1.3 拓?fù)鋭?dòng)態(tài)優(yōu)化策略

區(qū)塊鏈?zhǔn)怯晒?jié)點(diǎn)自主管理和維護(hù)的一種P2P 網(wǎng)絡(luò)。在P2P 網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都可以隨時(shí)加入或退出網(wǎng)絡(luò)[16]。區(qū)塊鏈節(jié)點(diǎn)的加入和離開(kāi)網(wǎng)絡(luò)等行為會(huì)引起網(wǎng)絡(luò)拓?fù)浒l(fā)生變化，本文利用提出的拓?fù)鋭?dòng)態(tài)優(yōu)化策略局部調(diào)整拓?fù)?，在一定程度上減小因拓?fù)鋭?dòng)態(tài)變化而引起的額外傳輸時(shí)間，從而減少區(qū)塊鏈出現(xiàn)分叉的情況，確保區(qū)塊鏈賬本的唯一性和一致性。拓?fù)鋭?dòng)態(tài)優(yōu)化策略作用于區(qū)塊鏈網(wǎng)絡(luò)層，對(duì)區(qū)塊鏈網(wǎng)絡(luò)層的改進(jìn)不會(huì)影響區(qū)塊鏈共識(shí)層使用共識(shí)算法來(lái)保障區(qū)塊鏈賬本的唯一性與一致性。針對(duì)樹(shù)形拓?fù)浯嬖诠?jié)點(diǎn)加入行為、離開(kāi)行為、可信值變化以及節(jié)點(diǎn)間權(quán)值發(fā)生變化的情況，本文設(shè)計(jì)了相應(yīng)的拓?fù)鋭?dòng)態(tài)優(yōu)化策略，只對(duì)狀態(tài)變化節(jié)點(diǎn)的局部范圍進(jìn)行拓?fù)湔{(diào)整，避免重構(gòu)整個(gè)網(wǎng)絡(luò)的拓?fù)?。下面介紹該策略使用的2 個(gè)算法以及提出的4 個(gè)子拓?fù)鋭?dòng)態(tài)優(yōu)化策略。拓?fù)鋭?dòng)態(tài)優(yōu)化示例如圖5 所示。

圖5 拓?fù)鋭?dòng)態(tài)優(yōu)化示例

破圈法。對(duì)于存在回路的樹(shù)形拓?fù)?，每次刪除回路中權(quán)值最大的邊，同時(shí)確保樹(shù)形拓?fù)涫沁B通的，直到樹(shù)形拓?fù)洳淮嬖诨芈贰?/p>

Sollin 算法。對(duì)于目前存在的多棵子樹(shù)，依次選取每棵子樹(shù)與其他子樹(shù)相連的權(quán)值最小邊，然后合并子樹(shù)，直到構(gòu)成一棵最小生成樹(shù)。

策略1節(jié)點(diǎn)加入拓?fù)鋭?dòng)態(tài)優(yōu)化策略

1) 可信節(jié)點(diǎn)加入拓?fù)鋭?dòng)態(tài)優(yōu)化策略是選取該節(jié)點(diǎn)與可信鄰居節(jié)點(diǎn)相連的所有邊加入樹(shù)形拓?fù)?，此時(shí)樹(shù)形拓?fù)淇赡艽嬖诨芈?，若所有邊加入?shù)形拓?fù)浯嬖诨芈罚瑒t對(duì)樹(shù)形拓?fù)洳捎闷迫Ψ?，得到可信?jié)點(diǎn)加入后的樹(shù)形拓?fù)?。圖5 的可信節(jié)點(diǎn)n7加入網(wǎng)絡(luò)時(shí)，選取n7與可信鄰居節(jié)點(diǎn)n5相連的邊加入樹(shù)形拓?fù)洌捎跇?shù)形拓?fù)錄](méi)有回路，因此直接得到7n加入后的樹(shù)形拓?fù)洹?/p>

2) 不可信節(jié)點(diǎn)加入拓?fù)鋭?dòng)態(tài)優(yōu)化策略是從不可信節(jié)點(diǎn)與可信鄰居節(jié)點(diǎn)相連的所有邊中選取權(quán)值最小邊，將該邊加入樹(shù)形拓?fù)?，得到不可信?jié)點(diǎn)加入后的樹(shù)形拓?fù)洹?/p>

策略2節(jié)點(diǎn)離開(kāi)拓?fù)鋭?dòng)態(tài)優(yōu)化策略

1) 葉子節(jié)點(diǎn)離開(kāi)拓?fù)鋭?dòng)態(tài)優(yōu)化策略是刪除該節(jié)點(diǎn)以及與其他節(jié)點(diǎn)的相連邊。

2) 針對(duì)樹(shù)形拓?fù)渲蟹侨~子節(jié)點(diǎn)離開(kāi)行為，采取的節(jié)點(diǎn)離開(kāi)拓?fù)鋭?dòng)態(tài)優(yōu)化策略如下所述。在刪除離開(kāi)的非葉子節(jié)點(diǎn)以及與其他節(jié)點(diǎn)的相連邊之后，樹(shù)形拓?fù)浞至褳槎嗫貌贿B通的子樹(shù)，這些子樹(shù)的構(gòu)成分為2 種情況，一種是由多個(gè)節(jié)點(diǎn)構(gòu)成，另一種是僅由一個(gè)節(jié)點(diǎn)構(gòu)成。非葉子節(jié)點(diǎn)離開(kāi)拓?fù)鋭?dòng)態(tài)優(yōu)化策略如下。首先，采用Sollin 算法對(duì)由第一種情況構(gòu)成的多棵不連通的子樹(shù)進(jìn)行樹(shù)形拓?fù)涞臉?gòu)建，對(duì)新選取的邊進(jìn)行判斷。如果新選取的邊包含不可信節(jié)點(diǎn)，則該邊不能作為樹(shù)形拓?fù)涞倪?，繼續(xù)對(duì)不連通的子樹(shù)運(yùn)行Sollin 算法，直到選取的邊不含不可信節(jié)點(diǎn)。然后，對(duì)第二種情況的子樹(shù)進(jìn)行處理，選取這個(gè)子樹(shù)節(jié)點(diǎn)與其可信鄰居節(jié)點(diǎn)直接相連的所有邊中的權(quán)值最小邊，將該邊加入第一種情況更新后的樹(shù)形拓?fù)?，更新?shù)形拓?fù)洹?/p>

圖5 中，非葉子節(jié)點(diǎn)n2離開(kāi)拓?fù)鋬?yōu)化策略是從網(wǎng)絡(luò)中刪除n2以及與其他節(jié)點(diǎn)的相連邊，采用Sollin 算法對(duì)由多個(gè)節(jié)點(diǎn)構(gòu)成的多棵不連通子樹(shù)構(gòu)建樹(shù)形拓?fù)?。因?yàn)橹挥幸豢糜啥鄠€(gè)節(jié)點(diǎn){n0,n1,n3,n5,n6}構(gòu)成的連通子樹(shù)，所以不需要利用Sollin 算法進(jìn)行構(gòu)建。將由一個(gè)節(jié)點(diǎn)n4構(gòu)成的子樹(shù)加入由節(jié)點(diǎn) {n0,n1,n3,n5,n6}構(gòu)成的樹(shù)形拓?fù)?，選取n3和n4相連的邊作為樹(shù)形拓?fù)涞倪叀?/p>

策略3節(jié)點(diǎn)可信值變化拓?fù)鋭?dòng)態(tài)優(yōu)化策略

節(jié)點(diǎn)的可信值變化可能影響節(jié)點(diǎn)的屬性，例如，由可信節(jié)點(diǎn)變?yōu)椴豢尚殴?jié)點(diǎn)，不可信節(jié)點(diǎn)變?yōu)榭尚殴?jié)點(diǎn)，從而引起樹(shù)形拓?fù)浣Y(jié)構(gòu)的改變。

1) 當(dāng)節(jié)點(diǎn)由可信節(jié)點(diǎn)變?yōu)椴豢尚殴?jié)點(diǎn)時(shí)，判斷該節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)。如果該節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則其拓?fù)浣Y(jié)構(gòu)不發(fā)生變化，節(jié)點(diǎn)屬性變?yōu)椴豢尚殴?jié)點(diǎn)。如果該節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，那么先對(duì)該可信節(jié)點(diǎn)執(zhí)行策略2，然后對(duì)可信值變化后的不可信節(jié)點(diǎn)執(zhí)行策略1，更新樹(shù)形拓?fù)洌鐖D5 中的n1可信值變化過(guò)程所示。

2) 當(dāng)節(jié)點(diǎn)由不可信節(jié)點(diǎn)變?yōu)榭尚殴?jié)點(diǎn)時(shí)，對(duì)該節(jié)點(diǎn)的可信鄰居節(jié)點(diǎn)和不可信鄰居節(jié)點(diǎn)采取不同的調(diào)整策略。首先，將可信鄰居節(jié)點(diǎn)與該節(jié)點(diǎn)連接的所有邊加入樹(shù)形拓?fù)?，運(yùn)行破圈法。然后，對(duì)該節(jié)點(diǎn)的所有不可信鄰居節(jié)點(diǎn)先后執(zhí)行策略2 和策略1，得到節(jié)點(diǎn)可信值變化后的樹(shù)形拓?fù)洹?/p>

策略4節(jié)點(diǎn)間權(quán)值變化拓?fù)鋭?dòng)態(tài)優(yōu)化策略

1) 如果節(jié)點(diǎn)之間權(quán)值變化的邊是樹(shù)形拓?fù)涞倪叢⑶覚?quán)值變小，或該邊不是樹(shù)形拓?fù)涞倪叢⑶覚?quán)值變大，則拓?fù)浣Y(jié)構(gòu)不變，只更新該邊的權(quán)值。

2) 針對(duì)權(quán)值變化邊連接的2 個(gè)節(jié)點(diǎn)是可信節(jié)點(diǎn)情況，如果該邊是樹(shù)形拓?fù)涞倪叢⑶覚?quán)值變大，更新該邊的權(quán)值，在樹(shù)形拓?fù)渲袆h除該邊，對(duì)分裂后的多棵子樹(shù)采用Sollin 算法選擇新連接的邊。若新選取的邊連接的節(jié)點(diǎn)都是可信節(jié)點(diǎn)，那么選擇該邊連接分裂的子樹(shù)，更新樹(shù)形拓?fù)?。若新選取的邊連接的節(jié)點(diǎn)存在不可信節(jié)點(diǎn)，則選擇原先刪除的邊來(lái)連接分裂的子樹(shù)，此時(shí)樹(shù)形拓?fù)浣Y(jié)構(gòu)不變。

如果該邊不是樹(shù)形拓?fù)涞倪叢⑶覚?quán)值變小，更新區(qū)塊鏈網(wǎng)絡(luò)拓?fù)渲性撨叺臋?quán)值，將該邊加入樹(shù)形拓?fù)?，?duì)構(gòu)成回路的節(jié)點(diǎn)運(yùn)行破圈法，更新樹(shù)形拓?fù)洹?/p>

3) 針對(duì)權(quán)值變化邊連接的2 個(gè)節(jié)點(diǎn)存在不可信節(jié)點(diǎn)情況，如果該邊是樹(shù)形拓?fù)涞倪叢⑶覚?quán)值變大，更新該邊的權(quán)值，在樹(shù)形拓?fù)渲袆h除該邊，對(duì)分裂后的多棵子樹(shù)采用Sollin 算法選擇新連接的邊。若新選取的邊連接的節(jié)點(diǎn)只有一個(gè)不可信節(jié)點(diǎn)，那么選擇該邊連接分裂的子樹(shù)，更新樹(shù)形拓?fù)?。若新選取的邊連接的節(jié)點(diǎn)都是不可信節(jié)點(diǎn)，則選擇之前刪除的邊來(lái)連接分裂的子樹(shù)，此時(shí)樹(shù)形拓?fù)浣Y(jié)構(gòu)不變。

如果該邊不是樹(shù)形拓?fù)涞倪叢⑶覚?quán)值變小，更新區(qū)塊鏈網(wǎng)絡(luò)拓?fù)渲性撨叺臋?quán)值，刪除該邊所連接的不可信節(jié)點(diǎn)在樹(shù)形拓?fù)渲械倪叄賹?duì)該節(jié)點(diǎn)執(zhí)行策略1，更新樹(shù)形拓?fù)?。圖5 中n4和n5之間邊的權(quán)值w4,5變小，更新區(qū)塊鏈網(wǎng)絡(luò)拓?fù)渲性撨叺臋?quán)值為，刪除該邊連接的不可信節(jié)點(diǎn)n4在樹(shù)形拓?fù)涞倪?，即n2和n4之間的邊，再對(duì)不可信節(jié)點(diǎn)n4執(zhí)行策略1，選擇n4和n5之間的邊作為樹(shù)形拓?fù)涞倪?，更新?shù)形拓?fù)洹?/p>

2 算法設(shè)計(jì)與實(shí)現(xiàn)

區(qū)塊鏈傳輸效率優(yōu)化方法通過(guò)樹(shù)形拓?fù)錁?gòu)建方法生成樹(shù)形拓?fù)?，利用轉(zhuǎn)發(fā)路徑選擇策略建立轉(zhuǎn)發(fā)路徑，采用拓?fù)鋭?dòng)態(tài)優(yōu)化策略調(diào)整局部拓?fù)洌瑥亩s短區(qū)塊鏈數(shù)據(jù)傳輸時(shí)間，提高數(shù)據(jù)傳輸效率。

2.1 樹(shù)形拓?fù)錁?gòu)建算法

可信拓?fù)涫菢?shù)形拓?fù)錁?gòu)建的前提，樹(shù)形拓?fù)錁?gòu)建算法利用Sollin 算法對(duì)可信拓?fù)錁?gòu)建最小生成樹(shù)，之后將不可信節(jié)點(diǎn)作為最小生成樹(shù)的葉子節(jié)點(diǎn)加入樹(shù)形拓?fù)?。具體的算法流程如算法1 所示。

算法1樹(shù)形拓?fù)錁?gòu)建算法

2.2 轉(zhuǎn)發(fā)路徑選擇算法

根據(jù)轉(zhuǎn)發(fā)路徑選擇策略，設(shè)計(jì)轉(zhuǎn)發(fā)路徑選擇算法，算法初始時(shí)隨機(jī)指定樹(shù)形拓?fù)涞哪骋还?jié)點(diǎn)作為根節(jié)點(diǎn)，然后按照自底向上和自頂向下2 個(gè)過(guò)程建立關(guān)于節(jié)點(diǎn)的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)表，最后根據(jù)轉(zhuǎn)發(fā)表和轉(zhuǎn)發(fā)數(shù)據(jù)規(guī)則進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。轉(zhuǎn)發(fā)路徑選擇算法如算法2 所示。

算法2轉(zhuǎn)發(fā)路徑選擇算法

2.3 拓?fù)鋭?dòng)態(tài)優(yōu)化算法

本文針對(duì)節(jié)點(diǎn)的加入行為、離開(kāi)行為、可信值變化和節(jié)點(diǎn)間權(quán)值變化情況設(shè)計(jì)了拓?fù)鋭?dòng)態(tài)優(yōu)化策略，根據(jù)該策略設(shè)計(jì)了拓?fù)鋭?dòng)態(tài)優(yōu)化算法，算法主要利用破圈法和Sollin 算法實(shí)現(xiàn)對(duì)狀態(tài)變化節(jié)點(diǎn)拓?fù)涞木植空{(diào)整。拓?fù)鋭?dòng)態(tài)優(yōu)化算法如算法3 所示。

算法3拓?fù)鋭?dòng)態(tài)優(yōu)化算法

3 仿真分析

為了驗(yàn)證所提方法和策略的有效性，本文使用Python 進(jìn)行仿真實(shí)驗(yàn)，使用Python 的networkx 庫(kù)生成網(wǎng)絡(luò)拓?fù)?。?shí)驗(yàn)設(shè)置構(gòu)建網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)個(gè)數(shù)為從100 到1 000 的等步長(zhǎng)取值，節(jié)點(diǎn)之間的權(quán)值設(shè)置為[1,50]隨機(jī)取值，權(quán)值的單位為s?？尚胖甸撝涤糜趧澐止?jié)點(diǎn)類型，當(dāng)節(jié)點(diǎn)傳輸成功率小于0.6時(shí)，該節(jié)點(diǎn)劃分為不可信節(jié)點(diǎn)[10]。將其值代入式(1)計(jì)算得出可信值閾值為1.2。為了避免節(jié)點(diǎn)同時(shí)與多個(gè)鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸時(shí)，一些節(jié)點(diǎn)受自身性能的限制無(wú)法同時(shí)傳輸給多個(gè)節(jié)點(diǎn)，從而導(dǎo)致數(shù)據(jù)丟失問(wèn)題，設(shè)定節(jié)點(diǎn)在同一時(shí)間段內(nèi)只能與一個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸。本文選取平均并發(fā)傳輸時(shí)間和轉(zhuǎn)發(fā)次數(shù)作為實(shí)驗(yàn)指標(biāo)，將本文提出的轉(zhuǎn)發(fā)路徑選擇算法與權(quán)重優(yōu)先算法[9]、隨機(jī)路徑算法[10]進(jìn)行對(duì)比。另外考慮到網(wǎng)絡(luò)中節(jié)點(diǎn)狀態(tài)變化情況，本文選取拓?fù)湔{(diào)整時(shí)間比和節(jié)點(diǎn)的參與率作為實(shí)驗(yàn)指標(biāo)，將本文提出的拓?fù)鋭?dòng)態(tài)優(yōu)化算法與全網(wǎng)重構(gòu)拓?fù)渌惴ㄟM(jìn)行對(duì)比。本文的仿真參數(shù)設(shè)置如表1 所示。

表1 仿真參數(shù)設(shè)置

權(quán)重優(yōu)先算法是通過(guò)優(yōu)先選取與當(dāng)前節(jié)點(diǎn)相連的權(quán)重最小節(jié)點(diǎn)，按照左孩子右兄弟原則構(gòu)造通信樹(shù)。隨機(jī)路徑算法是指節(jié)點(diǎn)隨機(jī)選擇除向它發(fā)送數(shù)據(jù)的節(jié)點(diǎn)之外的其他鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。本文提出的轉(zhuǎn)發(fā)路徑選擇算法與權(quán)重優(yōu)先算法、隨機(jī)路徑算法在不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下的平均并發(fā)傳輸時(shí)間如圖6 所示。其中，平均并發(fā)傳輸時(shí)間是指將每個(gè)節(jié)點(diǎn)作為數(shù)據(jù)發(fā)起節(jié)點(diǎn)計(jì)算數(shù)據(jù)傳輸?shù)饺W(wǎng)節(jié)點(diǎn)的并發(fā)傳輸時(shí)間之和的平均值。由于隨機(jī)路徑算法隨機(jī)選擇的鄰居節(jié)點(diǎn)很大概率不是最優(yōu)節(jié)點(diǎn)，因此具有最高平均并發(fā)傳輸時(shí)間。權(quán)重優(yōu)先算法在逐次選擇節(jié)點(diǎn)加入通信樹(shù)時(shí)，只選擇與當(dāng)前節(jié)點(diǎn)具有最小權(quán)重的節(jié)點(diǎn)加入，但是整體通信樹(shù)的并發(fā)傳輸時(shí)間不一定是最小的。本文算法綜合考慮了轉(zhuǎn)發(fā)節(jié)點(diǎn)的子節(jié)點(diǎn)和子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間兩方面，并且以全局最優(yōu)為目標(biāo)選擇節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。因此，轉(zhuǎn)發(fā)路徑選擇算法具有最小的平均并發(fā)傳輸時(shí)間，較大程度地減少了數(shù)據(jù)的并發(fā)傳輸時(shí)間，提高了數(shù)據(jù)傳輸效率。

圖6 不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下的平均并發(fā)傳輸時(shí)間

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

圖7 不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下的轉(zhuǎn)發(fā)次數(shù)

當(dāng)節(jié)點(diǎn)加入?yún)^(qū)塊鏈網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)建立拓?fù)溥B接，之后利用拓?fù)鋭?dòng)態(tài)優(yōu)化算法加入樹(shù)形拓?fù)?，網(wǎng)絡(luò)規(guī)模擴(kuò)大。當(dāng)節(jié)點(diǎn)離開(kāi)網(wǎng)絡(luò)時(shí)，可能引起樹(shù)形拓?fù)洳贿B通，利用拓?fù)鋭?dòng)態(tài)優(yōu)化算法將其調(diào)整為連通的樹(shù)形拓?fù)洌W(wǎng)絡(luò)規(guī)模減小。當(dāng)節(jié)點(diǎn)的可信值以及節(jié)點(diǎn)之間的權(quán)值發(fā)生變化時(shí)，可能導(dǎo)致一些節(jié)點(diǎn)之間的樹(shù)形拓?fù)浣Y(jié)構(gòu)發(fā)生變化，利用拓?fù)鋭?dòng)態(tài)優(yōu)化算法局部調(diào)整樹(shù)形拓?fù)?，網(wǎng)絡(luò)規(guī)模不變。不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下的拓?fù)湔{(diào)整時(shí)間比如圖8 所示，拓?fù)湔{(diào)整時(shí)間比是指采用全網(wǎng)重構(gòu)拓?fù)渌惴ㄅc拓?fù)鋭?dòng)態(tài)優(yōu)化算法調(diào)整拓?fù)浠ㄙM(fèi)時(shí)間的比值。全網(wǎng)重構(gòu)拓?fù)渌惴ㄊ侵府?dāng)已生成的樹(shù)形拓?fù)渲械墓?jié)點(diǎn)狀態(tài)變化時(shí)，利用樹(shù)形拓?fù)錁?gòu)建算法為全網(wǎng)節(jié)點(diǎn)建立新的樹(shù)形拓?fù)?。由圖8 可知，采用節(jié)點(diǎn)間權(quán)值變化拓?fù)鋭?dòng)態(tài)優(yōu)化算法調(diào)整變化節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)的效果最好。這是因?yàn)楣?jié)點(diǎn)間權(quán)值變化拓?fù)鋭?dòng)態(tài)優(yōu)化算法是對(duì)權(quán)值發(fā)生變化的邊進(jìn)行調(diào)整，存在權(quán)值發(fā)生變化時(shí)不需要調(diào)整節(jié)點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)，只更新邊的權(quán)值的情況。此外，節(jié)點(diǎn)加入、節(jié)點(diǎn)離開(kāi)和節(jié)點(diǎn)可信值變化拓?fù)鋭?dòng)態(tài)優(yōu)化算法的拓?fù)湔{(diào)整時(shí)間約為全網(wǎng)重構(gòu)拓?fù)渌惴ǖ?。因此，針?duì)狀態(tài)發(fā)生變化的節(jié)點(diǎn)，采用拓?fù)鋭?dòng)態(tài)優(yōu)化算法實(shí)現(xiàn)拓?fù)湔{(diào)整花費(fèi)的時(shí)間較少，從而提高了數(shù)據(jù)的傳輸效率。

圖8 不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下的拓?fù)湔{(diào)整時(shí)間比

本文提出的拓?fù)鋭?dòng)態(tài)優(yōu)化算法與全網(wǎng)重構(gòu)拓?fù)渌惴ㄔ诓煌W(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下的節(jié)點(diǎn)參與率如圖9所示，節(jié)點(diǎn)參與率是指參與調(diào)整拓?fù)涞墓?jié)點(diǎn)個(gè)數(shù)占網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的百分比。參與拓?fù)浣Y(jié)構(gòu)調(diào)整的節(jié)點(diǎn)個(gè)數(shù)越少，說(shuō)明節(jié)點(diǎn)狀態(tài)變化影響的范圍越小，則調(diào)整拓?fù)浣Y(jié)構(gòu)花費(fèi)的時(shí)間越少。由圖9 可知，采用拓?fù)鋭?dòng)態(tài)優(yōu)化算法的節(jié)點(diǎn)參與率低于20%，顯然優(yōu)于全網(wǎng)重構(gòu)拓?fù)渌惴ǎ驗(yàn)橥負(fù)鋭?dòng)態(tài)優(yōu)化算法只調(diào)整變化節(jié)點(diǎn)影響的小范圍局部拓?fù)浣Y(jié)構(gòu)，不對(duì)其他節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)進(jìn)行改動(dòng)。節(jié)點(diǎn)離開(kāi)和節(jié)點(diǎn)可信值變化拓?fù)鋭?dòng)態(tài)優(yōu)化算法的節(jié)點(diǎn)參與率略高于其他2種拓?fù)鋭?dòng)態(tài)優(yōu)化算法，這是因?yàn)楣?jié)點(diǎn)離開(kāi)拓?fù)鋭?dòng)態(tài)優(yōu)化算法需要?jiǎng)h除離開(kāi)節(jié)點(diǎn)，然后為不連通的多棵子樹(shù)進(jìn)行多輪選邊，而節(jié)點(diǎn)可信值變化拓?fù)鋭?dòng)態(tài)優(yōu)化算法利用節(jié)點(diǎn)離開(kāi)拓?fù)鋭?dòng)態(tài)優(yōu)化算法對(duì)節(jié)點(diǎn)和拓?fù)溥M(jìn)行處理。因此，本文提出的拓?fù)鋭?dòng)態(tài)優(yōu)化算法可以減少調(diào)整網(wǎng)絡(luò)拓?fù)渌鶐?lái)的額外開(kāi)銷(xiāo)，加快數(shù)據(jù)之間的傳輸。

圖9 不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下的節(jié)點(diǎn)參與率

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

本文提出的區(qū)塊鏈傳輸效率優(yōu)化方法由樹(shù)形拓?fù)錁?gòu)建方法、轉(zhuǎn)發(fā)路徑選擇策略和拓?fù)鋭?dòng)態(tài)優(yōu)化策略構(gòu)成。通過(guò)構(gòu)建的樹(shù)形拓?fù)淇梢院?jiǎn)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。轉(zhuǎn)發(fā)路徑選擇策略根據(jù)轉(zhuǎn)發(fā)表指導(dǎo)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，從而縮短數(shù)據(jù)傳輸時(shí)間。拓?fù)鋭?dòng)態(tài)調(diào)整策略針對(duì)狀態(tài)變化節(jié)點(diǎn)局部受影響的拓?fù)溥M(jìn)行調(diào)整，減少重構(gòu)全網(wǎng)拓?fù)渌鶐?lái)的額外開(kāi)銷(xiāo)。下一步工作考慮對(duì)區(qū)塊鏈網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分簇，為節(jié)點(diǎn)設(shè)計(jì)一種基于分簇的數(shù)據(jù)傳輸策略，以加快區(qū)塊鏈數(shù)據(jù)的傳輸，更好地適應(yīng)于大規(guī)模的區(qū)塊鏈網(wǎng)絡(luò)。

附錄1最小并發(fā)傳輸時(shí)間證明

證明當(dāng)節(jié)點(diǎn)按照其子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間由大到小的順序轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，整體具有最小并發(fā)傳輸時(shí)間，即證按照此轉(zhuǎn)發(fā)順序構(gòu)建的通信樹(shù)的支路最大傳輸時(shí)間是最小的。

假設(shè)根節(jié)點(diǎn)n0的n個(gè)子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間為W1≥W2≥ …≥Wn，wb是n0與子節(jié)點(diǎn)之間的傳輸時(shí)間（1 ≤b≤n）。以根節(jié)點(diǎn)按照其子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間由大到小順序轉(zhuǎn)發(fā)數(shù)據(jù)為基礎(chǔ)，假設(shè)并發(fā)傳輸時(shí)間最大支路中的子節(jié)點(diǎn)為nx，支路最大傳輸時(shí)間為

任意調(diào)換2 個(gè)子節(jié)點(diǎn)ni和nj的轉(zhuǎn)發(fā)順序后的支路最大傳輸時(shí)間為T(mén) '，其中，i＜j且Wi≥Wj。

在調(diào)換ni和nj轉(zhuǎn)發(fā)順序后，ni和nj所在支路的并發(fā)傳輸時(shí)間為

已知Wi≥Wi+1≥ …≥Wj，{ni,ni+1,…,nj}中節(jié)點(diǎn)所在支路的支路最大傳輸時(shí)間為。已知nx為調(diào)換前并發(fā)傳輸時(shí)間最大支路中的節(jié)點(diǎn)，下面根據(jù)x的取值情況進(jìn)行討論。

綜上所述，任意調(diào)換2 個(gè)子節(jié)點(diǎn)轉(zhuǎn)發(fā)順序使子節(jié)點(diǎn)不按照由大到小順序轉(zhuǎn)發(fā)數(shù)據(jù)的支路最大傳輸時(shí)間'T≥T。因此，當(dāng)節(jié)點(diǎn)按照其子節(jié)點(diǎn)所在子樹(shù)的最小并發(fā)傳輸時(shí)間由大到小的順序轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，整體具有最小并發(fā)傳輸時(shí)間。

證畢。