基于區(qū)塊鏈的輪詢系統(tǒng)MAC協(xié)議研究

楊志軍，寇倩蘭，丁洪偉

(1. 云南大學(xué) 信息學(xué)院，云南 昆明 650500；2. 云南省教育廳 教學(xué)儀器裝備中心，云南 昆明 650223)

輪詢系統(tǒng)具有公平性、靈活性、高效性、實用性、高服務(wù)質(zhì)量(Quality of Service，QoS)等特點，被廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)中[1]. 區(qū)塊鏈作為一種去中心化、不可篡改、可追溯、多方共同維護的分布式數(shù)據(jù)庫，能夠在互不了解的多方間建立可靠的信任，在沒有第三方中介機構(gòu)的協(xié)調(diào)下，實現(xiàn)可信的數(shù)據(jù)共享和點對點的價值傳輸[2]. 通過輪詢控制，有利于避免多址通信中由碰撞而產(chǎn)生的能量損耗，與此同時還可以記錄輪詢過程中的活躍節(jié)點數(shù)，可靠性和安全性較高. 一個高效的輪詢系統(tǒng)與區(qū)塊鏈結(jié)合日益成為研究熱點.

近年來為了改進輪詢系統(tǒng)性能，專家們做了許多嘗試. 其中，隊列長度、時延和吞吐量作為系統(tǒng)研究的重要性能指標(biāo)[3-6]. 為了減少輪詢過程中信息分組的排隊長度，并避免無用的通信，文獻[7]提出了一種增量輪詢協(xié)議. 根據(jù)當(dāng)前輪詢向量與前一個輪詢向量之間的值差異更新輪詢向量. 針對基于時分多路復(fù)用的光片網(wǎng)絡(luò)受到高網(wǎng)絡(luò)輪詢時間的影響，尤其在低負載下導(dǎo)致高延遲的問題. 文獻[8]利用基于方向的波長分配和環(huán)面拓撲結(jié)構(gòu)，提出了一種高效的通信策略，以改善相鄰簇間的并行通信，減少時分多路復(fù)用總槽數(shù)，從而減少網(wǎng)絡(luò)輪詢時間和降低平均網(wǎng)絡(luò)延遲. 為解決基于電磁的無線納米傳感器網(wǎng)絡(luò)的需求與回程鏈路的可用帶寬不匹配，降低物聯(lián)網(wǎng)回程帶寬效率的問題. 文獻[9]提出了一種按需概率輪詢方案. 該方案與之前提出的高效輪詢相比帶寬效率提高了18%，與貪婪輪詢相比能耗降低了69%. 文獻[10]通過引入多優(yōu)先級機制和降低信息分組發(fā)生碰撞所占的時隙長度來滿足不同優(yōu)先級業(yè)務(wù)的服務(wù)質(zhì)量需求，并提高系統(tǒng)的吞吐率，有效地緩解信道擁堵現(xiàn)象，改善無線Ad Hoc網(wǎng)絡(luò)的系統(tǒng)性能. 文獻[11]針對一種基于物理層輔助電源管理的輪詢方案，提出了一種新的排隊模型，在滿足延遲要求的前提下最小化功耗，幫助系統(tǒng)開發(fā)人員選擇最優(yōu)的系統(tǒng)參數(shù)，促進物理層輔助電源管理的實用性.

在上述文獻的討論中缺乏對輪詢系統(tǒng)技術(shù)的改善，多數(shù)是有關(guān)輪詢在現(xiàn)實生活中的各種應(yīng)用.針對該問題，本文提出將區(qū)塊鏈底層技術(shù)與輪詢系統(tǒng)結(jié)合的重要構(gòu)思. 區(qū)塊鏈能夠保存所有完整信息，并且任何節(jié)點在任何情況下都可以用加密哈希驗證數(shù)據(jù)塊. 同時，它具有分布式高冗余存儲、時序數(shù)據(jù)且不可篡改和偽造、去中心化信用、自動執(zhí)行的智能合約、安全和隱私保護等顯著特點，使得區(qū)塊鏈技術(shù)不僅可以成功應(yīng)用于數(shù)字加密貨幣領(lǐng)域，同時在經(jīng)濟、金融和社會系統(tǒng)中也有著廣泛的應(yīng)用[12]. 區(qū)塊鏈利用序列化鏈路，按照時間順序把所有數(shù)據(jù)區(qū)塊串聯(lián)起來，每個區(qū)塊包含父區(qū)塊的哈希值，由此形成了一個去中心化的數(shù)據(jù)賬本[13]. 雖然區(qū)塊鏈以此解決了信任問題，但帶來了成本的上升和效率的下降[14]，這也是制約其應(yīng)用的重要因素.而輪詢系統(tǒng)由N個隊列和一個或多個服務(wù)器組成，即N個隊列共享一個或多個資源. 該特征與區(qū)塊鏈底層技術(shù)中的共識機制類似. 但輪詢系統(tǒng)不能脫離服務(wù)器單獨工作，而區(qū)塊鏈最突出的技術(shù)特點就是去中心化. 故本文提出將輪詢系統(tǒng)加入到區(qū)塊鏈底層技術(shù)中，以實現(xiàn)系統(tǒng)去中心化，加快數(shù)據(jù)傳輸效率. 通過門限服務(wù)、完全服務(wù)、限定服務(wù)3種輪詢方式結(jié)合區(qū)塊鏈技術(shù)進行實驗分析及驗證，最后結(jié)果證明該方案切實可行，且加入輪詢后的區(qū)塊鏈系統(tǒng)傳輸效率更高.

1 背景知識

1.1 區(qū)塊鏈系統(tǒng)區(qū)塊鏈?zhǔn)怯梢粋€容錯的、共享的分布式數(shù)據(jù)庫和多節(jié)點網(wǎng)絡(luò)組成的系統(tǒng)，如圖1所示. 通過區(qū)塊鏈技術(shù)可以實現(xiàn)不依賴第三方由可信價值交換和對等式網(wǎng)絡(luò)的數(shù)據(jù)通信，對所有面向系統(tǒng)中心控制者的攻擊都有很強的抵抗力. 區(qū)塊鏈系統(tǒng)中每個節(jié)點都可以瀏覽區(qū)塊0到區(qū)塊N，但不能完全控制區(qū)塊. 每個節(jié)點也能夠驗證各個區(qū)塊，參與共識，通過共識增加數(shù)據(jù). 與基礎(chǔ)輪詢系統(tǒng)不同的是區(qū)塊鏈的這種點對點技術(shù)中的每一個用戶既是一個節(jié)點又是一個服務(wù)器. 將輪詢MAC協(xié)議加入到區(qū)塊鏈系統(tǒng)中，勢必將大大降低信息分組的平均等待時間和平均排隊隊長.

圖1 區(qū)塊鏈系統(tǒng)結(jié)構(gòu)Fig. 1 The structure of blockchain system

1.2 輪詢系統(tǒng)輪詢系統(tǒng)由N個隊列和一個或多個服務(wù)器組成，如圖2所示. 服務(wù)器根據(jù)一定的規(guī)則按照一個方向?qū)γ總€隊列進行操作，直到最后一個隊列的操作完成后再返回到第一個隊列再次執(zhí)行. 通俗地說就是由N個隊列共享一個或者多個資源，在應(yīng)用時通過一個或者多個邏輯上的中心，根據(jù)一定的周期順序?qū)Ω麝犃羞M行查詢，向需要被服務(wù)的隊列提供資源的使用權(quán).

圖2 輪詢系統(tǒng)結(jié)構(gòu)Fig. 2 The structure of polling system

1.3 基于區(qū)塊鏈的輪詢系統(tǒng)輪詢系統(tǒng)的原理是通過一個或多個服務(wù)器對N個隊列進行服務(wù)，整個工作過程中不能脫離服務(wù)器單獨作業(yè)，即將服務(wù)器當(dāng)作中心，中心化情況嚴(yán)重. 而區(qū)塊鏈技術(shù)最大的特點就是去中心化，將輪詢系統(tǒng)加入到區(qū)塊鏈底層技術(shù)之后，新的基于區(qū)塊鏈的輪詢系統(tǒng)把每一個區(qū)塊既當(dāng)作一個隊列又當(dāng)作服務(wù)器，每一個隊列區(qū)塊可以直接聯(lián)系，對信息分組進行服務(wù)，省去第三方服務(wù)器，以此提高對信息的處理效率. 由于輪詢系統(tǒng)的實質(zhì)是N個隊列共享一個或多個資源，與區(qū)塊鏈中的共識機制和智能合約理念相同. 所以不論采取3種服務(wù)策略中的哪一種，都能夠與區(qū)塊鏈技術(shù)產(chǎn)生一個很好的結(jié)合，最大程度地改進現(xiàn)有的設(shè)計方案.

區(qū)塊鏈的底層技術(shù)，主要是指在有關(guān)數(shù)據(jù)層、網(wǎng)絡(luò)層、共識層、合約層方面的研究. 其中最底層的技術(shù)就是區(qū)塊鏈基礎(chǔ)架構(gòu)中的協(xié)議層，起著類似電腦操作系統(tǒng)的作用. 協(xié)議層由網(wǎng)絡(luò)層和數(shù)據(jù)層構(gòu)成，二者相互獨立又不可分割. 本文提出將輪詢MAC協(xié)議應(yīng)用到區(qū)塊鏈系統(tǒng)的數(shù)據(jù)鏈路層中，如圖3所示，取消輪詢系統(tǒng)專門的服務(wù)器，即實現(xiàn)去中心化. 建立模型的具體步驟如下：

步驟1每個區(qū)塊既作為待服務(wù)的節(jié)點又作為服務(wù)器，各個區(qū)塊之間直接進行服務(wù).

步驟2將上一個隊列區(qū)塊的哈希值作為下一個隊列區(qū)塊計算哈希值的一部分，每一個新的隊列區(qū)塊的哈希值都會受到上一區(qū)塊哈希值的影響，從而也在隊列區(qū)塊和隊列區(qū)塊之間形成一個單向鏈條的結(jié)構(gòu).

步驟3將區(qū)塊鏈的每一個區(qū)塊作為一個隊列，各個隊列之間共享資源，并且按照一定的規(guī)則傳輸信息，直到最后一個隊列的操作完成之后再返回第一個隊列.

步驟4在工作過程中，任意隊列區(qū)塊作為服務(wù)器對其他隊列進行服務(wù)時，其余隊列作為被服務(wù)對象，處于閑置或替補狀態(tài).

圖3 基于區(qū)塊鏈的輪詢系統(tǒng)模型Fig. 3 The model of blockchain-based polling system

2 基于區(qū)塊鏈的輪詢系統(tǒng)工作機制

2.1 系統(tǒng)數(shù)據(jù)傳輸本文將輪詢加入到區(qū)塊鏈底層技術(shù)中，各個隊列按照時間順序?qū)?shù)據(jù)區(qū)塊以順序相連的方式組合成一種鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu). 前一個隊列區(qū)塊的信息分組服務(wù)完畢之后，轉(zhuǎn)向下一個隊列區(qū)塊，依次往后，直到最后一個隊列區(qū)塊N也服務(wù)完畢，再調(diào)轉(zhuǎn)回第一個隊列區(qū)塊，具體數(shù)據(jù)傳輸狀態(tài)轉(zhuǎn)移如圖4所示.

圖4 數(shù)據(jù)傳輸狀態(tài)轉(zhuǎn)移圖Fig. 4 Data transfer state transition diagram

隊列區(qū)塊中有任何的信息被服務(wù)，即存在交易記錄，默克爾樹根 (Merkle Root) 值都會相應(yīng)地發(fā)生改變. 默克爾樹是一顆二叉樹，它把所有交易記錄各自的Hash值作為葉子節(jié)點，兩個葉子節(jié)點哈希值合起來又進行1次哈希計算，生成父節(jié)點；直到最終的樹根. 樹根哈希值就是Merkle Root. 而在隊列區(qū)塊頭中，每一個隊列區(qū)塊自己的Hash由上一個區(qū)塊的Hash、時間戳、隨機數(shù)、目標(biāo)Hash和版本號經(jīng)過組合計算得來，然后該隊列區(qū)塊的Hash再作為下一個隊列區(qū)塊計算Hash的一部分.這就是每個隊列區(qū)塊具體的數(shù)據(jù)傳輸過程，如圖5所示.

隊列區(qū)塊體中記錄整個服務(wù)信息分組的交易，隊列區(qū)塊頭中將交易的信息分組收入緩存區(qū). 各個隊列區(qū)塊可以單個對其余隊列區(qū)塊存儲器中的信息分組按照一定的規(guī)則進行服務(wù)，服務(wù)后的信息分組被追加到下一隊列區(qū)塊尾部，依次往后.

圖5 數(shù)據(jù)傳輸原理Fig. 5 The principle of data transmission

將輪詢MAC協(xié)議應(yīng)用于區(qū)塊鏈系統(tǒng)中，使得整個系統(tǒng)得以利用塊鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)驗證與存儲數(shù)據(jù)、利用分布式節(jié)點共識算法生成和更新數(shù)據(jù)、利用自動化腳本代碼組成的智能合約來編程和操作數(shù)據(jù). 本文將區(qū)塊鏈底層技術(shù)與輪詢系統(tǒng)相結(jié)合，旨在使區(qū)塊鏈系統(tǒng)在網(wǎng)絡(luò)應(yīng)用中最大限度地提升數(shù)據(jù)處理速度.

2.2 系統(tǒng)變量定義(1)進入各個站點內(nèi)等待發(fā)送的信息分組的到達過程獨立同分布，其概率母函數(shù)用A(z)表示，均值用λ=A′(1) 表示，方差用A′′(1)+λ-λ2表示.

(2)任意終端站接受服務(wù)時發(fā)送一個信息分組所需要的時間獨立同分布，其概率母函數(shù)用B(z)表示，均值用 β=B′(1)表示，方差用表示.

(3)任意兩個相鄰終端站之間的轉(zhuǎn)換查詢時間獨立同分布，其概率母函數(shù)用R(z)表示，均值用γ=R′(1)表示，方差用

設(shè)隨機變量ξi(n)是在tn時刻第i號終端站其存儲器內(nèi)存儲的信息分組數(shù)，整個排隊系統(tǒng)可表示為[ξ1(n),ξ2(n),···,ξi(n),···,ξN(n)]，其概率分布為P[ξi(n)=xi;i=1,2,···,N]，在的條件下系統(tǒng)達到穩(wěn)定，其中 ρ=λβ. 由此得出該系統(tǒng)的概率母函數(shù)為

門限服務(wù)規(guī)則是服務(wù)器為某一隊列區(qū)塊在查詢到該隊列區(qū)塊的時刻之前所到達的信息分組提供服務(wù)，而在服務(wù)期間到達的信息分組轉(zhuǎn)入下一次服務(wù). 完全服務(wù)系統(tǒng)的服務(wù)規(guī)則是服務(wù)器對某一隊列區(qū)塊提供服務(wù)，直到該隊列區(qū)塊為空才轉(zhuǎn)入下一個隊列區(qū)塊提供服務(wù). 限定K=1服務(wù)系統(tǒng)的服務(wù)規(guī)則是服務(wù)器在查詢到任意隊列區(qū)塊時，每次最多服務(wù)一個信息分組. 其中，將平均排隊隊長、平均等待時間和平均循環(huán)周期作為目標(biāo)參數(shù)，進行分析和計算，最后對系統(tǒng)進行評估. 這些參數(shù)也是研究輪詢系統(tǒng)的重要參考指標(biāo)[15-17]. 理論上，平均排隊隊長是指區(qū)塊隊列存儲器中信息分組的平均隊列長度. 平均等待時間是指從信息分組到達區(qū)塊隊列直到被發(fā)送出去的這段時間. 平均查詢周期是指服務(wù)器連續(xù)兩次訪問同一個區(qū)塊隊列的時間間隔.

對(1)式求導(dǎo)得平均排隊隊長. 其中，門限服務(wù)系統(tǒng)平均排隊隊長為gi(G)(i)為

完全服務(wù)系統(tǒng)平均排隊隊長gi(E)(i)為

限定K=1服務(wù)系統(tǒng)平均排隊隊長gi(L)(i)為

根據(jù)文獻[18]方法求得平均等待時間. 其中門限服務(wù)系統(tǒng)平均等待時間為

完全服務(wù)系統(tǒng)平均等待時間為

限定K=1服務(wù)系統(tǒng)平均等待時間為

3種輪詢策略的平均輪詢周期為

3 實驗仿真

利用上述定義的條件對本模型的門限、完全和限定3種服務(wù)策略進行實驗仿真，整個實驗在Matlab2018a平臺完成. 通過將平均隊長、平均時延和平均周期設(shè)為目標(biāo)參數(shù)進行實驗仿真，對比實驗仿真值與期望值之間的差距，判斷系統(tǒng)性能是否良好. 同時，在同一到達率的情況下，以平均排隊隊長、平均等待時間和平均循環(huán)周期為目標(biāo)參數(shù)，對比3種服務(wù)策略的性能優(yōu)劣.

調(diào)用函數(shù)隨機生成以λ為均值的泊松序列模擬終端站中的信息分組數(shù). 假設(shè)5個隊列區(qū)塊內(nèi)的所有信息分組全部成功發(fā)送，保證公平性，信息無沖突傳輸. 設(shè)信息分組進入隊列區(qū)塊的到達率從0.005到0.05，以0.005為步長依次遞增. 每個信息分組接受服務(wù)需要2時隙，然后被釋放出去. 服務(wù)器對區(qū)塊隊列進行轉(zhuǎn)換查詢需要1時隙. 隨著到達率的變化，分別討論系統(tǒng)平均隊長、平均時延和平均周期. 又在同一到達率的情況下，對比3種服務(wù)策略的平均隊長和平均時延. 實驗分析在以下條件下進行：

(1)在任意單位時隙內(nèi)，所有隊列區(qū)塊內(nèi)的信息分組的到達過程服從泊松分布；

(2)到達各個終端站內(nèi)的信息分組相互獨立，并且服從相同的概率分布；

(3)系統(tǒng)在Nλβ＜1的情況下達到穩(wěn)定狀態(tài).

圖6～8分別對比了基于區(qū)塊鏈的門限服務(wù)的平均隊長、平均時延和平均輪詢周期的期望值和仿真值. 其中，期望值是通過相應(yīng)目標(biāo)參數(shù)的公式計算得出，仿真值是通過實驗仿真得到的. 圖6～8門限服務(wù)的平均隊長、時延、周期的仿真值和期望值曲線幾乎完全重合，其性能效果最好，驗證了理論分析的正確性. 隨到達率的變大，3個目標(biāo)參數(shù)也隨之增加，與實際相符，說明了該方案合理可行.

圖6 門限服務(wù)隊長期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 6 Comparison of gate service queue length expected value and simulation value (N=5,β=2,γ=1)

圖9～11將基于區(qū)塊鏈的完全服務(wù)的平均隊長、時延和周期的期望值和仿真值進行對比. 由圖9和圖10可知，當(dāng)?shù)竭_率較小時，平均隊長和時延的期望值和仿真值幾乎相等，仿真效果較好；當(dāng)?shù)竭_率較大時，期望值和仿真值之間存在些許誤差. 但誤差范圍較小，在可允許范圍內(nèi). 并且，通過圖11明顯看出完全服務(wù)的平均周期各自的仿真值和期望值近似相等. 故證明了該方案分析的正確性.

圖7 門γ=限1服)務(wù)時延期望值與仿真值對比(N=5,β=2,Fig. 7 Comparison of gate service delay expected value and simulation value (N=5,β=2,γ=1)

圖8 門限服務(wù)周期期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 8 Comparison of gate service cycle expected value and simulation value (N=5,β=2,γ=1)

圖9 完全服務(wù)隊長期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 9 Comparison of exhaustive service queue length expected value and simulation value (N=5,β=2,γ=1)

圖10 完全服務(wù)時延期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 10 Comparison of exhaustive service delay expected value and simulation value (N=5,β=2,γ=1)

圖11 完全服務(wù)周期期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 11 Comparison of exhaustive service cycle expected value and simulation value (N=5,β=2,γ=1)

圖12～14對比了基于區(qū)塊鏈的限定K=1服務(wù)平均隊長、時延和周期的期望值和仿真值. 可以看出當(dāng)?shù)竭_率較小時，仿真效果較好，平均隊長、時延和周期各自的仿真值和期望值近似相等；當(dāng)?shù)竭_率較大時，平均隊長、時延和周期的期望值和仿真值之間都存在相應(yīng)的誤差. 其中平均隊長的期望值和仿真值之間的誤差逐漸擴大. 故相對另外兩種服務(wù)方式來說，當(dāng)?shù)竭_率比較大時，限定服務(wù)系統(tǒng)不是特別穩(wěn)定.

圖15～16對比了當(dāng)?shù)竭_率處于0.005到0.05之間3種服務(wù)策略的平均隊長和時延隨到達率的變化. 由圖15可知，當(dāng)?shù)竭_率小于0.02時門限服務(wù)的平均隊長大于限定K=1服務(wù)；當(dāng)?shù)竭_率大于0.02時門限服務(wù)的平均隊長小于限定服務(wù). 并且不論到達率為多少，完全服務(wù)的平均隊長始終是最低的. 由圖16可知，在同樣的到達率下限定服務(wù)的時延最大，門限服務(wù)的時延略大于完全服務(wù). 故在相同負載下，完全服務(wù)具有更小的信息延遲. 即加快了信息處理速度，但兩者之間的差距很小. 對比門限和完全服務(wù)策略，門限服務(wù)具有更好的公平性.綜上所述，將輪詢加入到區(qū)塊鏈底層技術(shù)以提高數(shù)據(jù)處理效率的方案可行. 且在保證公平性的基礎(chǔ)上，門限服務(wù)系統(tǒng)能提高信息傳輸效率，改善系統(tǒng)性能，驗證共識機制，建立更強大的智能合約系統(tǒng)，滿足更高條件的用戶需求.

圖12 限定服務(wù)隊長期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 12 Comparison of limited-1 service queue length expected value and simulation value (N=5,β=2,γ=1

圖13 限定服務(wù)時延期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 13 Comparison of limited-1 service delay expected value and simulation value (N=5,β=2,γ=1)

圖14 限定服務(wù)周期期望值與仿真值對比 (N=5,β=2,γ=1)Fig. 14 Comparison of limited-1 service cycle expected value and simulation value (N=5,β=2,γ=1)

圖16 3種服務(wù)策略時延隨到達率變化對比 (N=5,β=2,γ=1)Fig. 16 Comparison of three service strategies delay with arrival rate (N=5,β=2,γ=1)

4 結(jié)論

隨著區(qū)塊鏈技術(shù)的不斷發(fā)展，在關(guān)注到區(qū)塊鏈巨大優(yōu)勢的同時，也需要對區(qū)塊鏈底層和基礎(chǔ)技術(shù)做進一步的研究. 本文分別分析區(qū)塊鏈及輪詢系統(tǒng)各自的模型特點，找到其共同點及不同特征，然后建立了新模型. 最后通過理論公式計算和程序模擬對比了門限、完全和限定3種服務(wù)的期望值和仿真值. 結(jié)果證明，將輪詢MAC協(xié)議加入到區(qū)塊鏈底層技術(shù)以提高信息傳輸效率，改善系統(tǒng)性能的方案正確可行. 其中性能最優(yōu)的是門限服務(wù)系統(tǒng). 下一步，課題組將考慮如何在保證公平性的基礎(chǔ)上通過實現(xiàn)負載均衡的方式，降低加入?yún)^(qū)塊鏈技術(shù)過程中產(chǎn)生的能源消耗，實現(xiàn)高效傳輸.