杨志军，寇倩兰，丁洪伟

(1. 云南大学信息学院，云南 昆明 650500；2. 云南省教育厅教学仪器装备中心，云南 昆明 650223)

1 引言

如今，各行各业都与信息技术有着深入的结合，无线传感器网络在整个社会的服务领域都产生较大影响。特别是5G时代的到来，超大顾客流量、密集站点接入和超高可靠与低时延服务的需求，对基本轮询系统的服务效率和拓展轮询应用空间提出来更高的要求[1]。网络并发量增加急需降低网络时延，提高服务质量。一直以来也有许多的针对轮询系统降低延迟、提高系统性能方面的研究。轮询系统作为一种广泛使用的防冲突协议[2]，基本可分为三种：门限服务、完全服务和限定服务。在三种服务策略的对比中可以发现限定服务的公平性最好[3]。但是其工作效率却因为服务器一次只对站点中的K个信息分组进行服务而受到限制。在优化轮询系统性能过程中，平均排队队长、平均等待时间和平均轮询周期常常作为三个重要指标参与研究讨论[4]。

三种基本轮询策略常常可以做出多种改变以改善轮询系统性能。为减少系统能耗，站点的忙闲状态常作为系统在低负载时是否选择休眠的依据[5-7]。文献[8]提出了分忙闲站点的限定K=2轮询系统模型。依据站点的忙闲状态采用并行调度方式对有信息分组的忙站点提供发送服务，以节省转换发送时间，降低系统时延。文献[9]提出一种基于轮询机制的机会干扰对齐算法，在提升公平性的同时，有效地减少传输块数，增强系统容量，灵活满足用户通信需求。当没有流量控制或没有采用标准的以太网暂停帧流量控制时，投放点会有很高的缓冲区占用率。为了减少这种投放点缓冲区占用问题，文献[10]引入了两种门限流量控制协议对服务策略进行调整。在众多研究中，提高系统吞吐量和总线利用率也是对轮询系统进行改进的重点[11]。文献[12]提出一种针对可扩展的MAC协议模型，为得到饱和吞吐量，通过四态传统马尔可夫模型对其进行建模，减轻了多媒体流量负担。文献[13]将轮询顺序与包括门限和完全服务在内的访问策略相结合，提出了一种新的WSN中基于优先级的并行调度轮询MAC协议，用以实现基于优先级的方案，同时通过并行调度减少开销时间。通过嵌入式马尔可夫链和生成函数建立模型，分析了平均队列长度、周期时间和吞吐量等关键系统性能特征。结果表明，新协议具有更好的性能。

上述文献从不同方面针对轮询系统的优化进行了研究，但基本上都是在单个服务器基础上开展的，缺乏对服务器个数变化的系统性能研究。本文就是基于此点，提出了双服务器的轮询控制系统。在分布式多服务器系统和网络中，对各个站点的服务可以进行批处理[14]，每个用户也可以由不同的服务器分配资源以获得公平性和服务[15]。由于门限服务需对服务站点内当前服务时间前的所有信息分组进行服务；完全服务更需要对当前服务站点内全部信息分组服务完毕，直到该站点为空才能转向下一站点。故这两种服务策略的公平性都远远小于限定服务。为保证系统公平性，本文选择一次只对站点中的K个信息分组进行服务的限定双服务器轮询系统模型。采用嵌入式马尔可夫链理论和概率母函数方法[16]对限定K=1和限定K=2同步双服务器系统进行建模，得出平均排队队长和平均等待时间的理论表达式。然后在Matlab中仿真，验证方案的可行性。最后将同步和异步方式的限定双服务器轮询系统与单服务器进行对比，得出一种最佳服务方式。

2 轮询系统模型

轮询系统具有公平性、灵活性、高效性、实用性、高服务质量等特性，被广泛应用于无线传感器网络中[17]。避免数据冲突、减小传输时延、提高系统吞吐量和总线利用率等方向始终是轮询系统研究的热点[18]。本文主要针对增加服务器数量和改变服务方式对系统性能的改变做出研究，整个过程采用限定服务策略。

限定双服务器轮询系统是由两个服务器和N个站点组成，如图1所示。服务器从第一个站点开始对其存储器内的信息分组按照一个方向进行服务，服务结束则转向下一个站点，直到第N个站点也服务完毕又转向第一个站点重新开始。服务器调度有同步和异步两种方式。本文针对同步方式又分别研究了限定K=1和限定K=2两种系统模式。对异步方式则研究了限定K=1服务。

图1 限定双服务器系统模型

3 同步方式

同步服务方式是指两个服务器同时到达站点并对其存储器内等待发送的信息分组进行服务，服务完毕同时离开。同步方式下各站点的状态转移过程如图2所示。

图2 同步方式各站点服务状态转移图

限定K=1同步双服务器模型具体服务策略为：

从第一个站点开始，服务器按照同步服务方式每次只对非空站点内的一个信息分组服务，服务完成之后立即转向下一站点。直到对站点N内的信息分组也完成服务后又转向第一个站点重复进行相同操作。

限定K=2同步双服务器模型具体服务策略为：

1) 服务器按照同步服务方式从第一个站点开始服务，依次往后，直到最后一个站点也被服务之后再转向第一个站点；

2) 当站点为空时，不对其进行服务；当站点存储器中只有一个等待发送的信息分组时，只对该站点中这一个信息分组进行服务，服务完毕立即转向下一站点；当站点存储器中等待发送的信息分组超过一个时，则只对该站点内两个信息分组进行服务，完成服务后转向下一站点[19]。

对于同步服务方式通过概率母函数和马尔可夫理论建模可推导出平均排队队长、平均等待时间的理论表达式。下面将进行详细推导。

3.1 定义变量

系统工作环境及相关变量定义：

4) 各个站点内存储器能够容纳足够多的信息分组；

5) 各个站点存储器中等待发送的信息分组按照先进先出的原则进行传输。

假设两个服务器在tn时刻对i号站点进行服务，当服务完i号站点内的信息分组之后，转向在tn+1时刻接受服务i+1号站点，对其存储器内等待发送的信息分组提供服务。ξi(n)表示tn时刻i号站点中存储器内等待发送信息分组总数，tn时刻系统的状态变量可表示为[ξ1(n)，ξ2(n)，…，ξi(n)，…，ξN(n)]，tn+1时刻系统的状态变量为[ξ2(n)，ξ3(n)，…，ξi+1(n)，…，ξN+1(n)]，系统保持稳定的条件为：Nλβ<2。其限定K=1服务概率母函数为：

Gi+1(1)(z1，z2，…，zi，…，zN)

[Gi(z1，z2，…，zi，…，zN)

-Gi(z1，z2，…，zi-1，0，zi+1，…，zN)]

+Gi(z1，z2，…，zi-1，0，zi+1，…，zN)}

i=1，2，…，N

(1)

限定K=2服务概率母函数为

Gi+1(2)(z1，z2，…zi，…，zN)

ziGi′(z1，…，zi-1，0，zi+1，…，zN)-

Gi(z1，…，zi-1，0，zi+1，…，zN)]+

+Gi(z1，…，zi-1，0，zi+1，…，zN)}

i=1，2，…N

(2)

3.2 平均排队队长

平均排队队长是指服务器在tn时刻对i号站点提供服务时，各个站点存储器中平均存储的信息分组数。可以通过对系统的概率母函数求导得出在tn时刻j号站点内存储的信息分组数，用gi(j)表示。

(3)

由式(1)(3)可求得限定K=1同步双服务器的平均排队队长为

i=1，2，…，N

(4)

同理可得，限定K=2同步双服务器的平均排队队长为

4Nλγ-2N2λγρ-Nλ2γ2]

i=1，2，…，N

(5)

其中，ρ=λβ。

3.3 平均等待时间

平均等待时间是指信息分组从进入站点存储器内到被发送出去的这段时间。与单服务器的计算方法类似，借用文献[20]的方法，计算限定K=1同步双服务器的平均等待时间得：

NλR″(1)]

(6)

同理可得，限定K=2同步双服务器的平均等待时间得

(7)

其中，ρ=λβ。

4 异步方式

异步方式是指两个服务器分别到达不同的站点按照限定服务规则对站点内信息分组进行服务。异步方式下各站点的状态转移过程如图3所示。

图3 异步方式各站点服务状态转移图

限定K=1异步双服务器模型具体服务策略为：

1) 如果到达时有服务器正在对站点服务就直接离开对下一站点进行服务，反之则对当前站点内相应数量的信息分组进行服务，服务完成再转向下一个站点；

2) 服务器按照异步服务方式每次只对非空站点内的一个信息分组进行服务。

由于异步服务方式调度的复杂性，无法推导出排队队长和平均时延的理论表达式，故直接采用Matlab进行实验分析其性能。

5 仿真与分析

5.1 同步方式性能分析

根据第二节建立的系统模型，在系统稳定条件下进行数值计算和仿真，理论值由式(4)-(7)计算得出，实验在Matlab2019a平台展开。设定系统有10个站点，服务器按照限定服务方式提供服务，单个服务器对一个信息分组服务需要2时隙，服务器在相邻站点间的转换查询时间为1时隙。将信息分组进入站点存储器内的到达率设为自变量，在从0.0001到0.001依次变化，观察信息分组的平均队长和平均时延的情况，结果如图4和图5所示。

图4 限定K=1同步双服务器平均排队队长

图5 限定K=1同步双服务器平均等待时间

图4-5对限定K=1同步双服务器系统的平均排队队长和平均等待时间进行仿真，得到对应的理论值和仿真值对比。可以看出平均排队队长和平均等待时间都随着到达率的增加而呈线性增长，即随着站点内到达的信息分组的数量增长，存储器内队列长度也跟着变长，信息延迟增加。该现象与实际相符。在到达率小于0.005之前其平均队长和平均时延的理论值和仿真值近似相等，仿真效果较好。当到达率处于0.005-0.01之间时，理论值和仿真值存在一个较小的误差，但仍在可允许范围之内。故证明了理论分析的正确性。

图6-7对限定K=2同步双服务器系统的平均队长和平均等待时间进行仿真。平均队长和平均时延都到达率的增加而增加，与实际相符。可以明显看出K=2限定条件下两个目标参数的理论值和仿真值之间误差非常小，可忽略不计，效果显然好于限定K=1。再次验证了该方案分析的正确性。

图6 限定K=2同步双服务器平均排队队长

图7 限定K=2同步双服务器平均等待时间

图8将传统限定K=1单服务器系统、限定K=2单服务器系统、限定K=1同步双服务器系统和限定K=2同步双服务器系统的平均队长进行对比。由图8可知，两个限定单服务器系统的平均队长大致相等，说明限定条件K=1和K=2的变化并不影响站点内信息分组的队列长度。两个限定同步双服务器系统的平均队长也几乎相等，并且理论值和仿真值之间的误差小于限定单服务器系统，再次验证了K=1和K=2的限定条件不影响队列长度的结论。同时，同步双服务器系统的平均队长明显小于单服务器的队长，说明使用双服务器提供服务，降低了站点内信息分组的平均排队队长，提高了系统性能。

图8 单服务器与同步双服务器的平均队长对比

图9是将K=1和K=2条件下的传统限定单服务器系统和同步双服务器系统进行对比。容易知道，传统限定K=1单服务器系统的平均时延是最高的。当把限定条件改为K=2时，平均时延就下降很多，且随着站点内的信息分组越多，下降越明显，优化效果越好。而同步双服务器系统的平均时延均小于传统单服务器系统，且K=1时的时延大于K=2条件下的时延。随到达率增加，站点内吞吐量变大，这种差距就越大。该结论与单服务器系统的结论相符，也再次说明该方案的正确性。所以，同步双服务器系统能大大降低系统时延，加快信息处理速度，改进系统性能。且限定条件K=2的降低幅度明显大于K=1，故限定K=2同步双服务器系统的优化效果是最好的。

图9 单服务器与同步双服务器的平均时延对比

图10将4种系统的平均轮询周期做比较，结果证明K=1和K=2的限定条件不影响服务器对站点服务的轮询周期，但同步双服务器系统的平均周期远小于单服务器系统。因此，使用同步双服务器系统明显降低了轮询周期，提高了轮询效率。

图10 单服务器与同步双服务器的平均周期对比

综上所述，轮询系统服务器个数增加，使得信息分组的排队队长降低，减少了分组时延，提高了信息分组传递效率。在同样的负载下，双服务器系统具有更高的效率。且在限定条件为K=2时，信息分组的延迟小于K=1时，信息处理速率更快。

5.2 异步方式性能分析

图11将限定条件为K=1和K=2下的单服务器系统与限定K=1异步双服务器系统的平均排队队长进行对比。由图11可知，异步双服务器系统的平均排队队长明显小于单服务器系统，大大降低了站点内信息分组的队列长度，减少信息传输时延。

图11 单服务器与异步双服务器的平均队长对比

图12将限定条件为K=1和K=2下的单服务器系统与限定K=1异步双服务器系统的平均等待时间进行对比。由图12可知，单服务器系统的平均时延远远大于异步双服务器系统，且随到达率的增加，平均时延有一个明显的上升趋势。而异步双服务器系统不仅平均时延大大降低，同时随到达率的增加，平均时延只是有一个缓慢的增长。故轮询系统通过增加服务器个数并采用异步方式可以很好的降低延迟，增加系统吞吐量，提高信息处理速率。

图12 单服务器与异步双服务器的平均时延对比

图13将限定条件为K=1和K=2下的单服务器系统与限定K=1异步双服务器系统的平均轮询时间进行对比。由图13可知，异步双服务器系统轮询周期明显小于单服务器系统，故采用异步双服务器模式可减少轮询周期，提高轮询效率，加快信息传输。

图13 单服务器与异步双服务器的平均周期对比

综上所述，不论采用同步或异步方式，增加轮询系统服务器个数都能减少信息分组排队长度，降低延迟，增加系统吞吐量，提高信息处理效率。

图14 同步与异步方式的平均队长对比

图14-15将在限定K=1和K=2条件下的同步双服务器系统与限定K=1异步双服务器系统进行对比，研究同为双服务器系统下的同步和异步方式对系统性能的影响。图14表明，异步方式的平均排队队长明显小于同步方式，故异步处理系统的性能比同步更好。

图15 同步与异步方式的平均时延对比

图15表明，异步方式的平均等待时间远小于同步方式。同步方式中的K=2限定条件针对异步方式并没有明显优势。即异步极大的降低了信息分组的等待时间，加快信息处理及轮询效率。

综上所述，双服务器的运用明显降低了信息分组在存储器中的排队时间，进而降低了数据包延迟，提高了信息处理效率，扩大了系统吞吐量。在一定条件下，K的取值越大，对限定同步服务方式的系统性能改善越好。而对于限定K=1服务系统，异步方式的处理使得系统平均队长和时延更低。相较同步双服务器系统，异步方式在降低平均队长和时延方面，表现得更好。故同样条件下，异步比同步更易达成信息分组的高效传输。

6 结论

如今，网络用户的数量迅速增加，其需求量也随之扩大。由于轮询系统本身具有防冲突性，且限定服务策略的公平性最好。故为保证在较高的网络并发量中实现高效传输，本文提出限定双服务器系统。同时通过马尔科夫链并运用概率母函数方法建立限定双服务器系统的数学模型对其展开研究。

本文在第一部分，对轮询研究进行分析，并提出多服务轮询控制方式。在第二、三和四部分，对同步和异步两种服务方式的数据分发过程做了详细分析，同时推导了同步服务系统的平均排队队长和平均等待时间两个目标参数及其理论表达式。在第五部分对系统模型进行仿真及性能研究。结果表明，同步双服务器明显降低了平均队长、平均时延和平均周期，其中限定K=2同步双服务系统的系统性能最好。异步方式相对其它服务方式极大的提高了信息传输速率，性能效果最好。故系统限定双服务器系统能在保证公平性的基础上实现高效传输。