基于多服务器的轮询接入控制协议分析

杨志军，毛 磊

(1.云南大学 信息学院，云南 昆明 650500；2.云南省教育厅 教育科学研究院，云南 昆明 650223)

0 引 言

互联网的快速发展使得网络的规模和业务流量不断增加，服务器需要具备更加强大的运算能力，才能保证网络时延和服务效率。因此对于使用单一服务器的接入控制协议而言，服务器的内存、处理器很容易到达瓶颈[1]。物联网时代，感知层对高密集站点的数据进行采集，通过各种网络实现实时传送，这对感知层的接入控制协议要求较高[2]。基于轮询接入机制的MAC协议，在计算机网络和物联网中有着广泛应用[3-5]，传统的轮询系统大多采用单服务器接入控制方式(single server access control mechanism，SSACM)[6,7]，由于单台服务器的运算能力是有限的，在业务量和网络规模较大时，网络时延较高，吞吐量较小，显然不能满足物联网中数据实时传输的需求。解决这类问题有两种方法：一是为服务器配置高性能的硬件设备；二是多服务器并发处理方式[8-11]。但是由于硬件扩展成本较高，通过提升硬件性能并不能从根本上解决这个问题，只有采用多服务器才能满足大量用户访问的需要，实现负载均衡[12,13]。

针对上述单服务器轮询接入协议的缺陷，本文将多服务器并发处理的方式应用到轮询接入协议中，旨在实现轮询系统的负载均衡，提高轮询系统的服务效率和吞吐量。多个服务器调度时，使用同步控制的方式实现服务器在站点之间的轮询，然后利用轮询多址系统理论和排队论对系统的平均排队队长和平均时延等性能进行了近似分析，并通过仿真实验进行了验证。

1 轮询接入控制协议

1.1 背景知识及相关工作

MAC协议是构建无线传感器网络(wireless sensor network，WSN)底层结构的基础，主要用来解决多个节点共享同一链路或资源时，信道资源如何分配和划分的问题。一般分为随机访问MAC协议和轮询访问MAC协议。在设计一个无线传感器网络时，主要考虑能耗、时延、网络效率等因素。基于轮询接入控制方式的MAC协议，是一种非竞争的协议，其时延和公平性较好，因此在WSN中有着广泛应用。根据节点占用信道的时间，轮询接入控制协议主要分为完全、门限和限定3种。完全服务协议[14]是指，当节点占用信道时，只有在发送完所有数据后才会释放信道；门限服务协议是指，当节点占用信道时，只发送当前时刻节点内存储的数据；限定服务协议是指，当节点占用信道时，只发送K(K≥1)个信元。3种协议有各自的优势和应用场景，其中完全服务协议用户的平均等待时延和平均排队队长较低，适用于高优先级或者实时性要求较高的业务。门限服务协议和限定服务协议公平性较好，适用于普通业务。

现阶段对轮询接入控制协议的研究，主要还是集中在区分业务优先级[15]和服务器调度方式[16]上。文献[17]中提出了一种使用两个服务器同步控制(dual server synchronization control strategy，DSSCS)的负载均衡策略，在一定程度上提高了系统的服务效率，但当网络中访问请求较多时，仍然不能解决系统效率低的问题。文献[18]提出一种基于忙闲队列的轮询控制协议，根据队列中有无顾客将队列分为忙队列和空闲队列，每次轮询时，服务器只访问忙队列，提高了系统的服务效率，但在网络规模和业务量较大时，网络时延仍然较高。上述轮询机制，虽然在一定程度上改善了系统的性能，但并没有改变单台服务器的限制，其数据处理方式仍然比较单一。本文提出的多服务器接入协议，突破了传统单服务器轮询接入控制协议的局限，扩展了轮询接入协议的内容，有效提高了轮询系统的服务质量。

1.2 MPACP协议

多服务器轮询接入控制协议(multi-server polling access control protocol，MPACP)由N个站点，S个服务器组成，如图1所示。服务器按完全服务方式对各个站点提供服务，即只有正在接受服务的站点没有数据需要被发送，服务器才切换到下一个站点继续提供服务。多个服务器调度时，可以同时参加站点的服务器的最大数量是1或S。声明：在任何给定时间内只有一个服务器可以为站点提供服务的服务器利用策略称为1×N，也可以叫作异步控制策略；所有S个服务器可以同时参加站点的服务器利用策略称为S×N，也可称为同步控制策略，当S=1时，两种策略明显重合。本文使用同步控制策略实现多个服务器的接入，S个服务器同时为站点提供服务，服务完成后同时离开。

图1 MPACP模型

在该协议中，多个服务器同时为站点提供服务指的是：当站点中有大量数据或访问请求等待处理时，将其分割成不同的块，然后发送到多台服务器上进行处理，以此来降低用户的平均排队队长和平均等待时延；或者是将单个大负载分发到多个服务器上分别处理，然后将每台服务器的处理结果合并后返回给用户。

多服务器轮询接入控制协议的这种结构对每一个客户来说都是透明的，从客户角度来说，客户看不到真正提供服务的多个服务器，只能看到一个虚拟的服务器。当用户提出发送请求后，首先将请求包传递给虚拟服务器，然后虚拟服务器将请求包中的目标MAC地址转换为选定服务器的MAC地址后，将用户请求转发出去，服务器处理后将用户的请求结果返回给用户。多服务器轮询接入机制的工作流程如图2所示。

图2 MPACP工作流程

2 MPACP系统分析

一个轮询系统的性能，主要从系统内用户的平均排队队长、平均循环周期、平均时延等方面来衡量，前两者是一阶特性，后一个是二阶特性。相同负载下，队长、周期、时延越小，说明系统的性能越好，服务效率越高。根据基本轮询系统的分析方法和排队理论，我们对多服务器轮询机制的特征参数进行解析，分析方法和结果如下所示。

2.1 系统工作条件

由于数据传输过程中，系统内的业务量或者是用户的访问请求随机性和不确定性较大，情况非常复杂，为了能对系统的性能做出正确的评估，仿真实验又不失一般性，在本文中考虑具有如下特征的多服务器轮询接入机制：

(2)系统内，站点数量等于N(N≥1)，服务器数量等于S(S≥1)。

(4)轮询顺序是服务器按升序索引访问每一个站点，访问完站点N之后，服务器返回站点1。

(6)系统是对称的：所有站点都是相同的，所有服务器的行为都是相同的，服务器按照数据到达的先后顺序为其提供服务(first come first serve，FCFS)。

2.2 随机变量和概率母函数

为分析系统的状态变量，定义以下随机变量：

vi(n)：服务器对i号站点中的信元进行完全服务所耗费的时间。

ui(n)：服务器从i号站点切换到i+1号站点的时间。

μj(ui)：ui(n)时间内进入j号站点的信元数。

ηj(vi)：vi(n)时间内进入j号站点的信元数。

设tn时刻，S个服务器同时访问i号站点并提供服务，当服务器处理完该站点存储器内的信元后转去查询i+1号站点，i+1号站点在tn+1时刻接受服务。ξi(n)表示tn时刻，i号站点存储器内存储的信元数，则tn时刻系统的状态变量可表示为{ξ1(n),ξ2(n),…,ξi(n),…,ξN(n)}。通过分析可知，tn+1时刻的系统状态只与tn时刻有关，网络的规模，即站点数量是有限的，该系统的状态变量构成马尔可夫过程，并且在Nλβ

(1)

定义πi(x1,x2,…,xi,…,xN)的概率母函数为

(2)

tn+1时刻，服务器为i+1号站点提供服务，由此可得

(3)

(4)

2.3 平均排队队长

定义系统的平均排队队长为：tn时刻，服务器按照完全服务规则对i号节点中的信元进行传输时，j号节点存储器内存储的信元数，用gi(j)来表示

(5)

由式(4)、式(5)可得MPACP系统中信元的平均排队队长为

(6)

式中：N表示站点数量，S表示服务器数量(N,S≥1)。

2.4 平均等待时延

通常使用系统中客户的平均等待时延来衡量网络的传输能力，时延过大，系统内的每个客户都需要等待很长时间才能得到服务，因此系统性能较差。定义系统的平均等待时延为：信元从进入节点到其开始被发送出去所经历的时间间隔。

定义系统的二阶偏导为

(7)

由式(4)、式(7)可得

(8)

与单服务器完全服务机制[14]类似，MPACP系统的平均等待时延也由E(wi,1)和E(wi,2)两部分组成，E(wi,1)表示：服务器轮询到i号节点开始传输数据时，缓冲区内存储的信元的平均等待时延；E(wi,2)表示，服务器为i号节点提供服务期间，到达i号节点的信元的平均等待时延。由式(6)～式(8)可得

(9)

2.5 系统吞吐量

定义系统吞吐量为：单位时间内，多服务器完全轮询接入机制所能处理的信元数，用T表示。MPACP采用多个服务器并发处理的结构，增大了系统的吞吐量，其计算方式如下

T=NSλβ

(10)

由文献[14]可知，SSACM的吞吐量为Nλβ，与其相比，多服务器系统的吞吐量增大了S倍。说明MPACP协议的负载能力更大，相同时间内，MPACP处理的信元数是SSACM的S倍。

2.6 平均查询周期

系统平均查询周期定义为：服务器对所有站点完成一次遍历所花费的时间，也就是服务器连续两次查询同一站点之间的时间间隔，用E[θ]表示。平均查询周期的计算大多是根据平均排队队长与平均循环周期的关系推导而出，该方式计算较为复杂[15]。本文根据轮询系统的工作机制，提出一种计算方法，定义如下：

服务器对所有站点完成一次访问所花费的时间由两部分组成：轮询转换所花费的总时间Nγ和为每个节点的信元进行传输所花费的总时间。后一部分，平均而言，在稳定状态下(由于对称性和稳定性)，必须等于一次遍历期间到达的平均总工作量的1/S,而根据我们的定义，单位时间内到达MPACP系统的平均总工作量为λtotβ=Nλβ，所以可以得到

(11)

3 仿真实验

根据2.1节理论分析的条件，在MATLAB2018a平台上构建多服务器轮询接入控制模型。使用exprnd()函数生成满足泊松分布的随机序列，用于模拟到达每个节点的信元数，其均值为λ。假定仿真时，数据通信过程是理想状态，也就是所有的信元都被发送成功，不会发生丢包和重传的情况。通信过程中，按时隙划分时间轴。仿真过程中，需要满足下面条件：

(1)系统是对称的：所有队列都是相同的，所有服务器的行为都是相同的；

(2)在每一个单位时隙内，数据按照泊松过程到达节点，节点的存储空间无限大；

(3)系统在Nλβ

(4)为确保实验的准确性，设置每次实验的循环次数为10万次以上；

(5)为提高仿真效率，实验中，网络规模，即节点数量在5-30个内变化，服务器数量在3-10个内变化，数据包的到达率λ的取值为[0.001∶0.001∶0.01]，单位为Mbps。

在该系统中，其初始条件为：在开始时刻，各个站点内没有数据需要被发送，当站点提出发送请求后，S个服务器同时去查询第一个站点，然后按完全服务方式为其提供服务。服务完成后，转去查询第二个站点。以此类推，服务完最后一个站点后，又开始对第一个站点提供服务。实验内容主要分为一下几个步骤：

步骤1 根据假定的条件，在MATLAB2018a上构建MPACP系统模型；

步骤2 产生满足泊松分布的数据信息；

步骤3 统计所有的数据信息；

步骤4 计算平均排队队长、平均循环周期、平均等待时延的实验值；

步骤5 根据式(6)～式(11)计算出理论值，然后与实验值比较，计算出相对误差；

步骤6 验证模型的正确性；

步骤7 设置实验条件，将MPACP模型与SSACM和DSSCS模型比较，评价MPACP模型的优越性；

模型仿真过程中，MPACP模型的控制流程见表1。

表1 MPACP控制流程

4 实验结果及分析

通过改变网络中的业务量(即数据包的到达率)、服务器数量和网络规模，分析系统中用户的平均排队队长、平均循环周期和平均等待时延的变化规律，结果如下所示。

表2是具有固定节点数量(λ=0.05,β=4,N=6,γ=2)，服务器个数在2到7之间变化的系统的平均队长和平均循环周期对比结果。通过对比发现，理论值与实验值基本一致，误差保持在较小范围内，说明理论分析的可靠性和准确性。

表2 MPACP理论值与实验值的相对误差

图3和图4是具有固定站点数量(N=5)，服务时间β=10，不同服务器数量情况下，系统的平均排队队长和平均等待时延的对比。首先，两个图中，各曲线上，理论值与实验值基本拟合，说明理论分析与仿真实验的一致性。然后，从两个图可以分别看出，随着服务器数量的增加，MPACP的平均队长和平均时延不断降低，说明相同业务量情况下，随着服务器数量的增加，系统的服务效率逐渐提高，使用多服务器轮询接入控制方式可以提高系统的性能。进一步分析图3，在数据包的到达率较小时，MPACP对系统平均队长的影响不是很明显；只有在到达率较高时(即高业务量情况下)，使用多服务器才能降低系统的平均队长。这是因为在业务量较小时，使用单服务器接入方式就能满足系统数据处理的需求，没必要使用多服务器。对比图4发现，在业务量一定时，MPACP的平均时延随着服务器数量的增加而降低，当服务器数量为10个以上时，其平均时延的下降趋势逐渐趋于平滑。

图3 MPACP平均排队队长随服务器数量的变化 (N=5,β=10,γ=1)

图4 MPACP平均时延随服务器数量的变化 (N=5,β=10,γ=1)

两个图中，分析S=6，S=10，两条曲线，即服务器个数取6、10。可以看出，在不同服务器下，系统的平均队长和平均时延变化趋于平稳，特别是数据包到达率较小的时候尤为明显，这说明使用多服务器并不能无限提升系统性能，当系统性能优化到一定程度时，继续增加服务器数量不仅不能提升系统性能，反而会造成资源的浪费。结合式(6)和式(9)也可以发现，轮询系统的性能除了与服务器数量有关，还与网络规模N和轮询转换时间γ有关。因此当使用MPACP协议提升系统性能遇到瓶颈时，可以通过优化站点数量、降低轮询转换时间和提高服务器的配置来进一步提升系统性能。

图5是不同数量的服务器下，系统平均循环周期的对比分析。在轮询系统中，平均循环周期是衡量轮询系统服务效率的重要指标，相同网络规模和业务量情况下，平均循环周期越小，系统的服务效率越高。从图5可以看出，MPACP的平均循环周期随着数据包到达率的增加而增大。当到达率一定时，随着服务器数量的增加，系统的平均循环周期逐渐降低，这说明使用MPACP协议，系统的服务效率和稳定性得到了很大提高。

图5 MPACP平均循环周期随服务器数量的变化 (N=5,β=10,γ=1)

4.1 网络规模对MPACP的影响

在实际通信过程中，不同的场合需要应用不同的网络规模。随着物联网的快速发展和感知层高密集节点的接入，网络规模成为影响WSN系统性能的重要因素。为分析网络规模对MPACP协议的影响，保持网络中业务量不变(即每个站点数据包的到达率都为0.004 Mbps)，网络中节点数量在10-30内变化，然后对比3种协议的平均时延，其中SSACM表示单服务器接入控制方式，DSSCS表示双服务器同步控制策略，仿真结果如图6所示。

图6 不同网络规模下3种协议平均时延对比

从图6的对比结果可以看出，在网络规模一定时，MPACP协议的平均时延最低。MPACP协议的平均时延受网络规模影响较小，而SSACM和DSSCS协议的平均时延随着网络规模的增大而快速增加。当网络规模为30个节点时，SSACM系统的平均时延爆炸，已经严重影响系统的运行，此时与SSACM和DSSCS协议相比，MPACP的平均时延分别降低了72.37%和28.12%左右。

4.2 业务量对MPACP的影响

在网络部署成功后，即网络规模不变，业务量是影响网络性能的主要因素，当网络规模固定为10个节点，数据包(即业务量)的到达率分别为0.002 Mbps、0.004 Mbps、0.006 Mbps、0.008 Mbps、0.01 Mbps时，3种协议的平均时延、吞吐量变化如图7、图8所示。

图7 不同业务量下3种协议平均时延对比

图8 不同业务量下3种协议吞吐量对比

从图7可以看出，3种协议中，MPACP的平均时延最小。说明MPACP协议通过增加服务器数量，使用同步控制策略，将业务量分担到多个服务器上分别处理，降低了用户的平均等待时延。具体分析，当业务量增大时，MPACP协议的平均时延比SSACM减小了1到3倍，比DSSCS减小了50%左右。整个实验过程中，随着网络中业务量的增加，MPACP的平均时延变化不大，保持在5 ms左右，MPACP性能较好。

从图8可以看出，相同业务量下，MPACP的模型的吞吐量远远大于SSACM和DSSCS，也就是说，单位时间内，MPACP能够传输更多的信元数和服务更多的用户，MPACP协议的服务效率更高。随着业务量的增加，SSACM和DSSCS协议的吞吐量增加较小，这是因为单一的服务器数量和数据处理方式限制了系统性能提升。这也是SSACM和DSSCS在业务量较高时，平均时延较大的原因。

5 结束语

轮询代表一类调度控制模型，为系统资源分配提供了一种非竞争的访问控制机制，在无线传感器网络中有着广泛应用。基于传统的单服务器轮询控制模型，本文提出使用同步控制方式的多服务器轮询接入控制协议实现负载均衡，提高轮询接入协议的服务效率，然后对其进行了理论计算和实验仿真。分析结果表明，在不同网络规模和不同业务量情况下，MPACP平均排队队长和平均时延都远远小于SSACM和DSSCS，MPACP响应速度较快。使用MPACP协议，提高了轮询系统的服务质量，为物联网感知层的接入提供了一种控制方式。下一步工作中，可将多服务器接入方式扩展到区分优先级的两级轮询接入控制模型中。