基于區塊鏈的輪詢系統MAC協議研究

楊志軍，寇倩蘭，丁洪偉

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

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

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

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

1 背景知識

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

圖1 區塊鏈系統結構Fig. 1 The structure of blockchain system

1.2 輪詢系統輪詢系統由N個隊列和一個或多個服務器組成，如圖2所示. 服務器根據一定的規則按照一個方向對每個隊列進行操作，直到最后一個隊列的操作完成后再返回到第一個隊列再次執行. 通俗地說就是由N個隊列共享一個或者多個資源，在應用時通過一個或者多個邏輯上的中心，根據一定的周期順序對各隊列進行查詢，向需要被服務的隊列提供資源的使用權.

圖2 輪詢系統結構Fig. 2 The structure of polling system

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

區塊鏈的底層技術，主要是指在有關數據層、網絡層、共識層、合約層方面的研究. 其中最底層的技術就是區塊鏈基礎架構中的協議層，起著類似電腦操作系統的作用. 協議層由網絡層和數據層構成，二者相互獨立又不可分割. 本文提出將輪詢MAC協議應用到區塊鏈系統的數據鏈路層中，如圖3所示，取消輪詢系統專門的服務器，即實現去中心化. 建立模型的具體步驟如下：

步驟1每個區塊既作為待服務的節點又作為服務器，各個區塊之間直接進行服務.

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

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

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

圖3 基于區塊鏈的輪詢系統模型Fig. 3 The model of blockchain-based polling system

2 基于區塊鏈的輪詢系統工作機制

2.1 系統數據傳輸本文將輪詢加入到區塊鏈底層技術中，各個隊列按照時間順序將數據區塊以順序相連的方式組合成一種鏈式數據結構. 前一個隊列區塊的信息分組服務完畢之后，轉向下一個隊列區塊，依次往后，直到最后一個隊列區塊N也服務完畢，再調轉回第一個隊列區塊，具體數據傳輸狀態轉移如圖4所示.

圖4 數據傳輸狀態轉移圖Fig. 4 Data transfer state transition diagram

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

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

圖5 數據傳輸原理Fig. 5 The principle of data transmission

將輪詢MAC協議應用于區塊鏈系統中，使得整個系統得以利用塊鏈式數據結構驗證與存儲數據、利用分布式節點共識算法生成和更新數據、利用自動化腳本代碼組成的智能合約來編程和操作數據. 本文將區塊鏈底層技術與輪詢系統相結合，旨在使區塊鏈系統在網絡應用中最大限度地提升數據處理速度.

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

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

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

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

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

對(1)式求導得平均排隊隊長. 其中，門限服務系統平均排隊隊長為gi(G)(i)為

完全服務系統平均排隊隊長gi(E)(i)為

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

根據文獻[18]方法求得平均等待時間. 其中門限服務系統平均等待時間為

完全服務系統平均等待時間為

限定K=1服務系統平均等待時間為

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

3 實驗仿真

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

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

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

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

(3)系統在Nλβ＜1的情況下達到穩定狀態.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結論

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