非强占有限优先权M/G/1排队系统

　　针对部分数据帧有完全优先权发送的计算机网络数据服务系统存在的网络拥塞风险问题，提出了一种非强占有限优先权M/G/1排队系统模型的方法。该系统模型引入控制完全优先权的参数n，使得数据帧的完全优先权变成有限优先权，考虑了不同优先级队伍之间的公平性，降低了计算机网络数据服务系统拥塞的风险，使得网络系统在有限优先权下有较好的稳定性。在模型研究中，运用全概率拆解方法获得各级队伍平均等待时间、平均逗留时间和平均队长的理论结果。对模型采用Matlab 2010a软件实验仿真，实验得到的各级队伍平均等待时间和理论平均等待时间的平均绝对误差为0.951%。实验中，有限优先权条件下各级顾客的平均等待时间比值显著小于完全优先权条件下各级顾客的平均等待时间比值。实验结果表明对非强占有限优先权M/G/1排队系统模型研究的理论结果是正确的，该模型具有更稳定的系统特性。

　　0引言

　　排队论是运筹学的分支，其理论得广泛应用于计算机网络数据发送服务[1]、通信系统[2]、道路交通[3]、银行[4]、地铁[5]、医院[6]等一些服务领域。对不同领域的服务系统需要建立与之对应的排队系统模型进行研究。

　　当前已有很多文献对排队系统进行过深入研究。文献[7]对强占及非强占优先权排队系统作了基础研究;文献[8]研究了非强占优先权的多服务器排队系统，将非强占优先权排队系统服务器扩充到多台经行研究;文献[9]引入绩效评价将排队系统应用在银行自动取款机(Automatic Teller Machine， ATM)系统，展示排队论在其他领域中有效的应用，此后排队论更是广泛应用于各种服务领域之中。之后研究人员纷纷研究了多级适应性M/G/1可修排队系统[10]、M/G/1休假排队系统[11]、基于多重休假的min(N，V)策略M/G/1排队系统[12]等。

　　现在文献对休假排队系统和可修排队系统研究颇多，其排队系统在计算机网络[13]和通信领域[14]也有较好的应用，但对于计算机网络应用中待解决的优先权拥堵问题相关文献比较少[15]。

　　随着计算机网络服务的快速发展，生活各个方面已逐渐离不开计算机网络[16]，计算机网络服务要解决的实际问题越来越复杂。在一个无线局域网中，可能正在播放一场关键的足球比赛，或者正在播放一部热剧，或者正值春晚等节日庆典，局域网中的部分手机终端或者计算机终端在进行需求流量极大的视频播放，另一部分终端在进行学习或者聊天等需求流量少的网络活动。为了使终端用户有较好的网络体验，需要对视频流提供优先级;同时也要保证别的终端正常进行网络活动，这是一个矛盾的问题。这样的问题不仅出现在无线局域网中，也在以太网的视频教学、视频会议等应用中出现。如何公平地解决这样的矛盾问题，这是一个十分值得深入研究的课题，涉及到了本文有限优先权排队系统的讨论[15]。

　　从非强占优先权排队系统的研究[7]知道，在有优先权的排队系统中如果大部分数据帧有优先权时，则有优先权的数据帧的平均等待时间并不会比没有优先权时缩短多少，而此时无优先权的数据帧的平均等待时间却会大大延长，增加网络系统拥塞风险，使得不同优先级之间在系统中的平均等待时间存在严重的不公平，因此将优先权排队系统直接在网络系统中应用，可能会产生服务器被优先级数据流长时期霸占而低优先级数据长时间无法传输的状态。为了解除优先权队列源较大时数据流长期霸占服务器的状态，协调不同优先级队伍之间平均等待时间的公平性，降低系统拥塞风险，需要对优先权进行限制。本文引入优先权参数n，其意义是低优先权顾客在等待高优先权n个顾客服务之后插队接受服务，定义其为有限优先权。文献[15]对非强占有限优先权M/M/1排队系统进行了研究，本文在此基础上，将模型假设中的系统服务时间服从负指数分布推广到一般分布进行研究，即对非强占有限优先权M/G/1排队系统模型进行研究，使得该排队模型更适合在计算机网络服务中应用。

　　1系统假设

　　定义1在有高优先权接受服务顾客和低优先权接受服务顾客的排队系统中，低优先权顾客在等待高优先权n(n∈N为系统参数)个顾客服务之后插队接受服务的排队系统，称为n有限优先权排队系统。

　　定义2非强占有限优先权M/G/1排队系统假设如下。

　　假设1顾客分为2个等级，第1级享优先权，第2级无优先权。

　　假设2顾客到达系统服从参数为λi的Poisson分布，λi为第i级顾客的平均到达率;i=1，2。

　　Pi(λi，t，m)=(λit)mm!e-λit; m=0，1，2，…，t>0

　　假设3系统中只有一个服务窗口，服务窗为每一级别的顾客服务的时间独立同一般分布G(t)，t≥0，平均服务时间为0<1/μ=∫+∞0t dG(t)，方差为0<σ2=∫+∞0(t-1/μ)2 dG(t)， μ为顾客的平均服务率。

　　假设4系统为n有限优先权排队系统。

　　注记1记ρi=λi/μ，λ=λ1+λ2， ρ=ρ1+ρ2， ρ为系统的业务量，由于第1至第2级顾客均是相互独立的Poisson流，因此在任何时刻到达系统的顾客属于第i级的概率为λi/λ=ρi/ρ。

　　注记2当ρ<1时，系统存在平稳分布[7]。

　　2系统理论分析

　　3模拟实验结果与分析

　　该模型G分布为一般分布，对任意的分布都成立。为验证理论的正确性，取一般分布为k阶爱尔兰分布，其均值为μ。由于1阶爱尔兰分布就是负指数分布，k阶爱尔兰分布具有较好的代表性，因此选取k阶爱尔兰分布作为代表进行模拟。用Matlab 2010a进行模拟实验。下面给出模拟步骤：

　　1)在Matlab 2010a里面，以λ1，λ2为参数的Poisson分布顾客到来时间间隔服从1/λ1，1/λ2的负指数分布，所以选取相应两列负指数分布随机数10000个作为顾客到来时间间隔模拟。

　　2)取以1/(kμ)为参数的负指数分布随机数一共2k·10000个，并从第1个开始将连续k个相加得到20000个值，作为服务窗k阶爱尔兰分布的模拟。

　　3)设定系统时间t，有限优先权参数n以及相应数值，进行有限优先权模型模拟。

　　4)记录10000个顾客的排队等待服务时间，求平均值W*q1 ，W*q2 。

　　5)循环100次，求100次计算所得W*q1 ，W*q2 值的平均数作为Wq1，Wq2模拟结果。

　　模拟实验总共进行100万次，模拟后的一些结果给出如下。

　　由表1、表2的结果可以看出，各级顾客平均等待时间的理论结果与仿真结果存在细微误差，其平均绝对误差为0.951%，误差是仿真模拟实验必然存在的。实验结果表明对非强占有限优先权M/G/1排队系统模型研究的理论结果是正确的。从中可知有限优先权参数n既是控制第1级、第2级顾客的平均等待时间参数，也是控制各队队长的参数。当一个排队系统在优先权条件下又需要考虑各个优先权队列长度时也可以用该有限优先权模型。例如有VIP服务的停车场排队系统，因为停车场只有有限的车位，顾客排队过长会导致顾客寻找别的停车场停车，使得停车场遭受损失。这就可以通过有限优先权参数调整排队队列长度挽留顾客。

　　下面将λ1∶λ2=3∶1，k=3， μ=50，n=3，系统强度ρ取值不同的有限优先权排队系统和完全优先权排队系统的平均排队等待时间的模拟实验结果进行对比，其结果如图2所示。该结果表明有限优先权排队系统对高优先权顾客的适当限制能够使得低优先级顾客的平均等待时间大大减少，既保证了顾客接受服务的公平性又保证了系统稳定性。

　　4结语

　　为了解决部分数据帧有完全优先权发送的计算机网络数据服务系统存在的网络拥塞风险问题，避免网络系统中不同优先级队伍之间的排队等待时间的不公平性，本文提出一种非强占有限优先权M/G/1排队系统模型。通过对模型的研究得到各级顾客的平均等待时间等计算结果，仿真实验表明模型的计算结果和仿真结果在误差条件下是相等的。本文系统模型各级顾客之间的平均等待时间可由有限优先权参数n控制，在有限优先权条件下各级顾客的平均等待时间比值显著小于完全优先权条件下各级顾客的平均等待时间比值，表明该模型相对一般非强占优先权排队模型对各级顾客的平均等待时间的可调控性更强，通过调控可以避免某一顾客队列等待时间过长引起系统堵塞崩溃。本文提出的模型基本解决了计算机网络中需要发送有优先级的分类数据信息可能产生网络拥塞崩溃的问题，并对该模型进一步应用有了一定探索。但本文所作的工作只是初步的，模型假设相对简单，需要继续研究更符合实际的系统模型。下一步将对模型进行完善，使得模型更好在计算机网络中实际应用。

　　作者：黄业文 邝神芬杨荣领杨春侠 来源：计算机应用 2016年7期