容量有限批量服务轮询多址系统建模与分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇容量有限批量服务轮询多址系统建模与分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要: 采用马尔科夫链理论，对一类批量服务、队列容量有限的轮询多址系统进行分析，建立了系统状态转移图，推导了基于信息分组数的队列状态转移概率公式.使用Matlab基于有限状态机理论的Stateflow工具箱，对该类模型进行了具体的建模与仿真，并考虑了站点具有不同优先级的情况.实验结果表明，基于Stateflow的模型与仿真方法能够有效地反映该类模型服务器的平均循环时间和站点信息帧丢弃率等统计特性.

关键词: 轮询多址；有限状态机；网络时延

中图分类号:TP 391.9 文献标志码:A 文章编号:1672-8513(2011)05-0367-05

Modeling and Analysis of the Polling Multiple Access System of Batch Service and Finite Capacity

GAO Fei, LIU Shenghua，FAN Jing

（Key Lab of Wireless Sensor Networks, Yunnan University of Nationalities, Kunming 650500，China）

Abstract: This paper analyzes the polling multiple access system model with Markov chain theory, which, with non-symmetrical, limited capacity of memory and batch service, established a system state transition diagram and derived based on the information packet queue state transition probability formula. Then modeling and simulation of the class model was done according to the finite state machine theory of the Stateflow toolbox of the Matlab software with a consideration of the priority of the stations. The simulation result indicates that the model and simulation based on Stateflow can effectively reflect the average cycle time of the server and the frame loss rate of the station and other statistical characteristics of this model.

Key words: polling multiple access; Stateflow; network delay

作为一种重要的多址接入控制模型，轮询系统（Polling System）一直受到研究者的关注，在计算机网络、工业控制、军事以及社会化服务等领域得到广泛的应用［1-2］.一般来说，对轮询系统的研究方法，通常是依据排队论的相关理论知识，采用不同的数学建模方法与计算机仿真设计，对系统进行数学建模，得到系统的解析结果，并进行计算机仿真实验，得到数值结果.文献［3］讨论缓存器容量无限的单服务器的轮询服务系统，推导了普通队列和中心站点在完全服务策略下的平均队列长度和平均查询周期的数学解析式.文献［4］讨论了系统容量有限的情况，但没有相应的理论分析.文献［5］对几类基于竞争的优先级接入控制机制进行了介绍和评述.文献［6］提出了一种在数据传输前，对节点进行实时检测的基于动态优先级队列的无线多址接入协议，相较于PC下能提供更好的分组延迟.文献［7］利用Stateflow工具箱对M/M/1/∞排队系统进行了仿真.文献［8］分析了基于有限服务的轮询排队服务系统，通过概率母函数的方法，获得了平均队长和信息等待时延等性能指标.文献［9］讨论了存储器容量无限的门限服务的多队列循环服务系统，在单个服务员的情况下，采用概率母函数的方法近似求解了平均队长的理论解析式.

本文主要对存储器容量有限批量服务的多队列循环服务系统进行讨论.主要工作有2个内容：一是采用嵌入马尔科夫链理论，对存储器容量有限批量服务轮询接入控制系统模型进行了分析，建立状态转移图，推导出队列状态转移概率；二是采用Matlab中基于有限状态机理论构建的Stateflow工具箱，对此类模型进行建模和仿真.Stateflow是集成于Matlab Simulink中的图形化设计开发工具，可以清晰、简洁地反应出复杂逻辑动态关系.由于Stateflow是嵌入在Simulink仿真环境中的，所建模型可以直接链接到Simulink中，与Simulink中的既有模块可以合为一体.因此，利用Stateflow实现系统模型可以更准确地反映系统各单元之间的逻辑关系，获得更直观的性能分析结果.本文借用此工具箱，构建了10个具有3类业务优先级站点的轮询系统仿真模型，对该类模型的网络时延和站点溢出率等性能指标进行了分析和研究.

1 系统变量说明及数学建模

1.1 系统的理论模型描述

本文所研究的系统模型如图1所示.

1） 设系统为多用户单服务员系统，有1个主站， N个从站（2≤N

2） 设各从站信息帧到达为泊松（Poisson）过程，并互相独立.假定站点i的到达率为λi，在对称系统的情况下，单个站点的到达率为λ；

3） 设各从站存储器容量有限，容量设定为S（0

4） 设系统服务规则为限制式（Limited）服务，每次服务的信息帧数限定为1~k（1≤k

5） 站点i中信息帧被服务的时间为ti，“服务员”离开站点i后重返站点i的时间wi（自回归时间）均为已知分布的随机变量，均值分别为t和w；

6）“服务员”的转移时间、各站点的信息帧被服务时间以及信息分组到达间隔相互独立.

1.2 有关变量的说明

1） tc：主站对所有站点全部轮询一遍所需的时间（即循环1周的时间），包括转移时间和服务时间，即tc=∑Ni=1ti+∑Ni=1wi，由于ti和wi均为随机变量，所以tc也是一个随机变量；

2） ψi,n：从站i队列状态概率，即“服务员”到达站点i时该站存储器中有n个信息帧的概率，n=0,1,2,…,S；

3） pi,k(tc)：站点i在1个循环周期tc（在“服务员”到达本站到下一次重新到达本站的时间间隔）中到达k个信息帧的概率，k=0,1,2,…；

4） pi,m,n：站点i在tc的循环周期里，信息帧数由m变为n个的概率（k=n－m）；

5） Li：站点i中的队列均长.

2 系统的状态转移

根据1.1和1.2，当“服务员”到达站i时，其存储器中如有n个信息帧，则称站i中信息帧数的状态有n种.ψi,n与上一周期的始点状态以及周期中到达信息帧数有关.可以画出其状态转移图，如图2所示，为简化在这里略去站点号下标i，即pi,m,n简化为pm,n，ψi,n简化为ψn.

其一步转移概率矩阵:

p=p0,0p0,1p0,2…p0,n…p0,sp1,0p1,1p1,2…p1,n…p1,sp2,0p2,1p2,2…p2,n…p2,s00pn,0pn,1pn,2…pn,n…pn,s00ps,0ps,1ps,2…ps,n…ps,s ,（1）

并且有：

p0,0=p0(tc),p0,1=p1(tc),p0,2=p2(tc),…,p0,n=pn(tc),…,p0,s=∑∞k=spk(tc); p1,0=p0(tc),p1,1=p1(tc),p1,2=p2(tc),…,p1,n=pn(tc),…,p1,s=∑∞k=spk(tc); p2,0=p0(tc),p2,1=p1(tc),p2,2=p2(tc),…,p2,n=pn(tc),…,p2,s=∑∞k=spk(tc); pn,0=p0(tc),pn,1=p1(tc),pn,2=p2(tc),…,pn,n=pn(tc),…,pn,s=∑∞k=spk(tc); ps,0=p0(tc),ps,1=p1(tc),ps,2=p2(tc),…,ps,n=pn(tc),…,ps,s=∑∞k=spk(tc).（2）

根据嵌入马尔科夫链的理论和文献［10］的方法，当λi>0，由于系统状态为正常返回，并且构成的马氏链是奇次、不可约、非周期的，因而有：

ψn=∑sm=0ψmpm,n, 0≤m≤s; ∑sn=0ψn=1.（3）

由一步转移概率矩阵（2）和方程组（3）联立，得：

ψn=pn(tc), 0≤n

同时，站i在1个循环周期tc内到达k个信息帧的概率为：

pi,k(tc)=［λitc］k!ke－［λitc］ （5）

方程组（4）和（5）即为本文讨论的系统模型最基本的解析式，是求其他统计平均的依据.平均队列长度可通过如下方程计算得到：

Li=∑Sn=0nψi,n（6）

3 仿真模型

本文所述系统的Simulink模型采用模块化结构与分级建模的方法，其基本结构如图3所示.clock模块提供仿真运行过程中的时间参数，仿真运行的总时间设定为3000s.Poisson Integer Generator提供数据源，向Model模块输入服从泊松分布的随机向量.Serve_rate模块提供传输速率，Length模块提供信息分组长度，Buffer模块提供队列存储器容量，这些参数可以根据需要灵活设定.按照一般服务系统的组成，将其分成3个部分：输入、排队和服务.输入过程是指“顾客”到达的方式，无论以什么样的方式到达，都有一定的规律，这个到达规律指到达过程或到达时间间隔的分布.在本文的仿真模型中，设定为到达过程服从泊松分布，即图3中的Poisson Integer Generator.排队方式通常和服务规程相对应，有什么样的服务规程就有什么样的与之对应的排队方式，本文讨论的是有干扰的排队，即根据到达的“顾客”数，一旦超过了队列所能容纳的极限（容量），“顾客”马上离去.仿真模型中，站点node1~node10的内部结构完全一样，从站模块的内部结构如图4所示.1号站点模块包括2个部分，send部分和Queue部分.send部分包括2个状态：Generator和Temp.当条件Lambda1>0为真时，发生状态转移，统计到达信息分组数，同时广播信息分组到达事件C_A1.Queue部分主要是相应事件C_A1对应的响应函数是ca()，OVER函数.对于信息分组到达事件C_A1，在队列容量没有达到最大极限之前，信息分组数n1+1，同时，将信息分组到达时间存入数组List1中.

模块的仲裁部分具有优先控制功能，其内部结构如图5所示.利用Stateflow的图形函数工具，设计了轮询函数polling.本节设定了2号站点优先级最高，5号站点的优先级其次，其他站点为一般普通站点，无优先级.仲裁工作的流程是保证高优先级站点能够以抢断方式先行发送自己的数据.当数据发送完毕后，轮询重新回到正常的依次轮询次序.Model模块的服务器部分结构如图6所示，分为空闲Idle和工作Work 2个状态.其中服务器进入空闲状态时，b置为当前时间，当离开空闲状态时，用当前时间减去b，该语句能够统计服务器的忙闲程度.“服务员”对各站点进行轮询，当被轮询的站点有数据需要发送时，发送相关数据，当条件（time－tf）>=c×Length/Mu为真时，发生该语句的状态转移.当轮询到的站点没有数据需要发送时，“服务员”立即离开，轮询下一个站点，转移语句为［q==1］{q=0;c=0;}.

4 仿真结果分析

模型运行时间为3000s，图7~10为运行时间内的系统部分性能的统计平均值.

1） 图7所示为信息分组到达率与信息分组到达个数关系（以10号站点为例），实验参数设置为：服务速率Serve_rate=1，信息分组长度Length=1，站点容量buffer=10.到达的信息分组数随分组到达率的增加而增加，同时由于站点存在存储器容量限制，分组数趋于饱和.由公式（3）~（5）获得的数据理论值也实验结果一致.

2） 图8所示为站点因容量受限产生的信息帧丢弃率情况（以10号站点为例），同时由于站点容量大小不同，丢弃率有差异.计算方法为：丢弃率=1－m10/x10，其中m10为10号站点在运行时间内总的批量发送信息帧个数，x10为10站点在运行时间内产生的总的信息帧个数.参数设置为Serve_rate=10，Length=30.

3） 图9给出了信息分组长度与发送时间t10（10号站点信息分组的发送时延）之间的变化曲线，随着信息分组长度的增加，发送时间延长，同时由于信息分组到达率不同，发送时延存在差异.参数设置为buffer=30，Serve_rate=10.

4） 根据仲裁部分的polling函数优先级的设定，其时延情况如图10所示，高优先级站点比低优先级站点的时延要小，参数设置为Buffer=30，lambda=0.03，Length=30.

5 结语

本文根据嵌入马尔科夫链的理论，对批量服务容量有限的多站点轮询服务系统进行了理论分析，并利用Stateflow工具箱进行了仿真建模，获得了服务器平均循环时间和站点信息帧丢弃率相关指标，并在仿真模型的基础上，讨论了站点的优先级，比较了优先级站点的时延情况.从本次仿真的结果来看，仿真结果与理论值相近，证明了Matlab软件中的基于有限状态机理论的Stateflow工具箱对于完成该类系统的仿真和建模，是有效和正确的，同时也为排队系统的仿真又提供了一种新的方法.

参考文献:

［1］张宇眉，张欣，杨大成，等.基于等待时间和信道状态的轮询多址协议［J］.北京邮电大学学报，2008,31(4):126-129.

［2］曾勇，黄巍，杨静，等.运用动态优先级轮询机制的数据链仿真［J］.电子科技大学学报，2008,37(2):244-247.

［3］吴宗华，赵东风.中心站点和普通站点完全服务排队系统分析［J］.计算机工程与应用，2007,43(16)：116-134.

［4］LIU Shenghua, GAO Fei,SHI Wenyu, et al.Simulation and analysis of polling multiple access system for tactical data link by matlab stateflow modeling［C］//Proceedings of 2010 International Conference on Computer Design and Applications.Piscataway:IEEE Press,2010:274-277.

［5］GAO Fei, SARINA Qian, YIN Shitang. Review on DCF-based priority access schemes for IEEE 802.11 MAC［J］. 云南民族大学学报:自然科学版，2007,16(4)：314-320.

［6］王渊，赵东风，苏红芹.基于动态优先级队列的无线多址接入协议［J］.云南民族大学学报:自然科学版,2004,13(3)：207-209.

［7］吕学志，任帆，于永利.基于stateflow的排队系统仿真方法［J］.军械工程学院学报,2009,21(4):65-68.［8］王思明，马自立，张忠辅.多队列循环服务系统―全服务与门限服务方式的分析与建模［J］.运筹与管理，1994,3(3/4):1-7.

［9］李琰，赵东风，丁洪伟，高飞.轮询多址通信系统门限服务策略研究［J］.通信学报，2005,26(3)：99-105.

［10］王思明，汪虹.批量服务容量有限的多队列循环系统［J］.系统工程理论与实践，1998,9:100-109.

收稿日期:2011-06-23.

基金项目:国家自然科学基金（60963026）；国家民委科学研究基金（10YN07）、云南省教育厅科学研究基金研究生项目（2010J070）.

作者简介:高飞（1961-），男，教授，硕士生导师.主要研究方向：多址通信与无线传感器网络技术.