基于区块链的轮询系统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协议加入到区块链底层技术以提高信息传输效率，改善系统性能的方案正确可行. 其中性能最优的是门限服务系统. 下一步，课题组将考虑如何在保证公平性的基础上通过实现负载均衡的方式，降低加入区块链技术过程中产生的能源消耗，实现高效传输.