基于markov链的排队模型求解稳态方程

基于markov链的排队模型求解稳态方程

队列理论（也称为随机服务系统）是研究系统由于随机因素的干扰而发生队列（或中断）现象的一个学科。它适用于所有服务系统，包括通信系统、网络系统等。对通信系统进行性能评价是当今排队论在应用上的热门课题之一。通信系统中的业务量分析主要是研究在某种呼叫到达率和业务服务时间分布的情况下,系统所提供服务的各项指标,包括呼损率、用户平均等待时间、用户平均驻留时间、缓冲区内的平均队长等。由于理论研究的复杂性和局限性,近年来排队论的发展得益于计算机仿真模拟技术的发展。本文讨论了利用离散事件系统的仿真方法——事件调度法对排队系统进行分析,并采用Matlab语言给出了M/M/m模型的仿真结果。1动态状态仿真排队系统是比较典型的离散动态系统,按照常规,对通信系统的仿真必然涉及到时间的表示和事件驱动的表示(到达事件和离开事件)。但在通信系统的业务量分析过程中,由于每个用户都存在确定的到达时间、开始服务时间和离开系统的时间,加之Matlab语言对矩阵处理的独特优势,可以用静态的思想来实现排队系统的仿真。基本思路如下:对排队系统中的每个动态实体的状态可以由3个量(对应矩阵的一列)来反映:与前一个实体的到达间隔,在排到自己服务前的等待时间和服务时间。对于特定的排队系统,到达间隔和服务时间是一定的,所以只需对服务时间进行更新,然后根据动态实体的这3个量就可以得到系统性能的各项指标。2模型的构建和m-m模型的模拟过程2.1到达率tM/M/m模型中,顾客的到达(即用户的呼叫或分组)是平稳泊松过程。由文献,平稳泊松过程可描述为:在(t,t+s)内到达的顾客数为k的概率是:P{N(t+s)−N(t)=k}=e−λs(λs)kk!(1)Ρ{Ν(t+s)-Ν(t)=k}=e-λs(λs)kk!(1)其中:N(t)表示(0,t)内到达的顾客数,t≥0,s≥0,k=0,1,2,…,λ为到达率。由于顾客的到达满足平稳过程,则到达时间间隔服从负指数分布,其密度函数为:f(t)=λe−λt=1βe−1/βt≥0(2)f(t)=λe-λt=1βe-1/βt≥0(2)其中β=1/λ为到达时间间隔均值。2.2计算任务及影响信息的时延和占用率假设用户需要的服务时间(即话音或分组速率)服从参数为μ的负指数分布,排队规则采用FIFO(先到先服务)原则,服务员的数目(即信道总数)为m,要仿真测试的顾客总数为peo_num,则仿真步骤如下:(1)初始化系统状态:用一个3×peo_num矩阵表示每个顾客的状态(到达时间间隔、等待时间、服务时间);产生每个顾客的到达时间间隔arr_interval(i)和服务时间serve_time(i),分别服从参数为λ和μ的负指数分布,用exprnd函数即可完成,只需注意函数的参数是平均到达间隔和平均服务时间,而非到达率和服务率。其中:1≤i≤peo_num。(2)更新每个顾客的状态,计算其排队等待时间Wait_time(i)(假设缓存区无限大,每个顾客都得到了服务,不存在顾客丢弃)。其中:1≤i≤peo_num。更新思路是:判断第i个顾客到达时,m个服务员中是否有空闲。具体方法如下:当用户到达系统时,应对该时刻之前的所有用户的占用状态进行统计,以判决当前是否有空余信道。对于第i个用户,在他到达系统时不存在空余信道的充要条件是式(3),(4)所示的i-1个方程成立的数目大于m。其中j=2,3,…,i-1。Wait_time(i-1)+serve_time(i-1)-arr_interval(i)≥0(3)Wait_time(i-j)+serve_time(i-j)-arr_interval(i)−∑k=i−j+1i−1(arr_interval(k))≥0(4)(i)-∑k=i-j+1i-1(arr_interval(k))≥0(4)(3)根据已经确定的各顾客的到达系统、开始接受服务和服务完成离开系统的时间(即矩阵中一列的值),来计算排队系统的队列长度随时间变化情况、顾客的等待时间、顾客的时延和占用率等。其中计算某时刻队列长度的基本思想是用在此时刻前到达的总实体数,减去在此时刻前结束服务的实体数,进而求出平均队列长度和占用率。(4)整理和处理结果。将(3)中的仿真结果进行整理并可视化输出。3仿真测试结果文献给出了M/M/m模型的解析结果,对一个到达率为λ=2,服务率为μ=1.25,服务员m=2的排队系统,通过计算可得理论值为:ρ=0.8000,W=1.4222,T=2.2222,N=4.4444。表1是通过仿真方法得到的近似数值结果(测试顾客数peo_num=1000)从表1可以看出,通过这种模型和方法仿真的结果和理论值十分接近,如果再增加顾客数peo_num和仿真次数,可以得到更理想的结果。这种方法提供了传统分析方法难以解决的多服务员排队系统的解析,尤其当服务员较多时,更显出了其优越性,而且为通信系统业务量的分析提供了一种近似而便于实现的方法。图1和图2给出了顾客数peo_num=200时的分组时延和等待时间的分布以及队长(包括正在传输的分组)的分布。4基于业务分析的仿真通过和理论值的比较,仿真结果与根据经典解析法得到的结果误差不大,证明使用本文所介绍的静态仿真的思想对排队系统进行仿真是切实可行的,他为复