（计算机软件与理论专业论文）竞争—冲突淘汰存取方式Ⅵ类系统模型数学建模研究.pdf

论文摘要 近二十年来，计算机网络得到了极大的发展，目前已进入到一个新 的发展时期，即a t m 交换网和宽带业务综合数字网的时期。网络新时期 的特征是在计算机网络业已发展的基础上，将综合业务( 数据、话音、 视频、传真等服务) 引入进去。为了发展综合业务局域网，本文对星形 l 川进行了深化研究。 国内外有关多星l a n 的运行机理已经有了报告。在此基础上，竞争 冲突淘汰存取方式，作为星形l a n 的一种新的存取方式被提了出来， 并且根据顾客请求服务、再次请求服务、接受服务的各种情况进行组合， 分了多种类型的系统模型。其中竞争一冲突淘汰存取方式i 类、i i 类、 i i i 类、类、v 类系统模型的数学建模已经完成。本文就类系统模型 进行了数学建模，提出了顾客转移概率、平稳状态下系统平均队长、顾 客平均等待时间等的算式。同时进行了模拟实验，且与i 类、 v 类模型进行了比较。为“竞争一冲突淘汰”存取方式在综合业务下的 应用奠定了理论基础。 关键词：多星l a n 存取方式；竞争一冲突淘汰式：数学模型 a b s t r a c t i nt h e p a s tt w e n t yy e a r s ，c o m p u t e rn e t w o r kw a sb o o m i n g n o w , a b r a n d - n e we r a b e g i n s ，t h a ti s ，t h e e r ao f 删s w i t c h i n gn e t w o r k sa n d b i s d n w h i c hi n t e g r a t e dv a r i o u ss e r v i c e ss u c ha sd a t a v o i c e ，v i d e oa n d f a x i no r d e rt od e v e l o pt h ea r e an e t w o r ko f i n t e g r a t e ds e r v i c e ，t h i st e x tw e n t o n d e 印r e s e a r c h f o rs t a rl a n m u l t i s t a rl a n s w o r k i n gp r i n c i p l e h a sb e e n r e p o r t e d o n t h i s c o n d i t i o n 。a san e wa c c e s sm o d ei ns t a rl a n ，t h ec o n t e n t i o n c o l l i s i o n e l i m i n a t i o na c c e s s m o d e ( a b b r e v i a t e d a s c c e a m ) h a sb e e np r e s e n t e d a c c o r d i n gt oc u s t o m e r sh o w t oa s kf o rs e r v i c ea n dh o wt ob es e r v e d ，t h e s y s t e mm o d e lo fc c e a m c o u l db ec l a s s i f i e ds i xt y p e s a n dt h es t u d i e sa b o u t is t ，i in d ，i r d ，t ha n dv t h s y s t e mm o d e l sh a v ea l s ob e e nf i n i s h e d i n t h i sp a p e r , o nt h eb a s i so f p r e v i o u sr e s e a r c hw o r k s t h e t hs y s t e mm o d e l w a ss t u d i e d ，a n dr e s u l t sw e r ec o m p a r e dw i t ht h ev i t ha n dvt ho n e ，a n dw e g o te x p r e s s i o n s f o rt h et r a n s f e r p r o b a b i l i t y o ft h ec u s t o m e r s ，t h em e a n n u m b e ro fc u s t o m e r si nt h es t e a d ys t a t e 。a n dt h em e a nd e t a i n e dt i m eo f t h e c u s t o m e r si nt h e s y s t e m s of a r , t h et h e o r y f o u n d a t i o no ft h e c o n t e n t i o n - c o l l i s i o ne l i m i n a t i o na c c e s sm o d eh a sb e e ne s t a b l i s h e df o r i t s a p p l i c a t i o no ni n t e g r a t e d s e r v i c ec o n d i t i o n k e y w o r d s ：m u l t i s t a rl a na c c e s sm o d e ；c o n t e n t i o n - c o l l i s i o n e l i m i n a t i o na c c e s sm o d e ；m a t h e m a t i c a lm o d e l i n g 第一章引言 第一章引言 众所周知，即算机局域网络( l a n ) 的存取方式主要区分为非竞争式和竞争式。 在竞争方式中，以竞争一冲突避免方式的c s m a c a 和竞争一冲突后退方式的 c s m a 圮d 著称。但这两种方式使用于星形l a n 时，存在种种局限性，不是星形 l a n 的理想存取方式。 近年来，伴随着光纤通信的急速发展，由于星型拓扑的适用性，星型l a n 以及 多星l a n 的研究工作也随之快速开展起来。目前国内外对星形拓扑结构的研究主要 集中在：( 1 ) 基于无源星形网的波分多路复用( w d m ) 协议的改进【l 6 j 。( 2 ) 网络 结构模型的改进及分析。( 3 ) 星形l a n 的多点访问信道存取方式研究及系统性能分 析。 其中，在疆形l a n 的多点访问信道存取方式研究领域，一种断的适用于星形 l a n 戆耨娶存酸方式竞争羚突一滢汰式( c o n t e n t i o n - c o l l i s i o nc a n c e i l a t i o a , c - c c ) 被 提出来p ，s l ，有望克服c s m a c d 作为总线型l a n 的存取方式应用予星形l a n 的种 静爨凝挂。 目前，这种新黧存取方式的理论研究工作已经媵开。撤据顾客请求服务，再次 请求鼹务，接受服务豹甭嗣媾况，将c 。c c 分蔻六炎聊，分割进行数学建模骚究。其 中，c c c 稃取方式的单星l a ni v 类模型的数学建模醴经取得重要突破 1 0 - 1 4 1 ， 本文的磷究工佟是农它们弱麓础上，对类系统模型避行了建摸磷究秘牲镰译价， 至_ f 魄，基本究成了c - c c 方式星形l a n 的数学建模研究。 多星l a n 豹运行视理蘩已报告，为了本文建模的需要不妨赂徽阕述。 如图l 所示，多整l a n 有m 条交换通道和n 个用户终端( n m ) 。 m 条交换通道构成巾心节点。每个终端产生的 数掭毡在自磁的缓、释送捧酞，一量摊弼酞蓠， 就立即提出服务请求。如果同时提出服务请求 翦舔户终蟋数夸予蠛等予窒闲豹交羧通道数， 就让其全部通过。否则就会产生冲突，中心节 点孤发生狰突鹃多繇数舞鸯中选择等予空溺交 换通道数的数据包让其通过，其余的数据包被 海汰。如果熬舞包毅警豹终臻五臻犊浚f 邈赣是 服务成功) ，则源终端会收到响应包a c k ，准备 鼙 窝1 - i 多星l a n 示豢强 发送下一令数攘趣；知鬃服务不残璇，刘滚终端牧戮n a k ，重薮发送。零文讨谂 m = i ，n m 的情况。 本文建立撵驮攒型对，将中心缮点豹交捩通道当终服务员，将用户终端产生的 青岛大学碗上学位论文 信息单元当作顾客，将缓冲器当作排队室。而且设定信息单元长度为定长。 由上述运行机理的说明，可得竞争一冲突淘汰存取方式原系统模型如图2 所示。 掣。潞麓群 二二 # 墅警芦型墨看 服务成功 鬟亭= 寻一h ! p p 魁 刊亲石面赢li 保留服务i ：l 墨壑量堡唑ll 壑互姿里! l ! 孓：k l 一一一一一一一一一一一一一一一一一o 小保留服务权重新请求_ | 摄务 2 图1 - 2 竞争一冲突淘汰存取方式原系统模型 根据谈图，简述六种模型分焚如下： l 类：颞客第一次竞争服务权、再次竞争服务权都在服务员嶷闭时发生，获褥 服务衩静一位顾客知栗服务失败，臻傈留服务较，再次按受服务，直羁骚务成功。 或者可设定服务一次成功。 l l 类：颟客繁一次竞争骧务较、再次竞争窳务较都在黻务员夺蔑瞳靛生，这 点与l 类相同。获得服务敉的顾客在服务必败后不保留服务权，立即重新请求服务， 这熹与f 类不阕。 两者的区别在图l - 2 中明显可见，1 类时k ，接“1 ，l l 类时k ，接“2 ”。 1 1 l 类：顾客笫次竞争随机笈生，再次竞争服务权寇期发生，服务必败后保留 殿务权，终次接受鼹务，囊銎| 摄务成功。溅孝可设定鼹务次成功。 类：顾客第次竞争、再次竞争服务粳与l 娃类相简，腋务必败后不蒋傈舀f 服 务权，立即重新请求服务。 v 类；颥客第一次竞争、再次竞争服务衩都蹩随褫发生，获褥强务极的一位镞 客如果服务失败，则保留服务权，再次接受服务，直至服务成功。或者w _ 熨定服务 一次戍琏。 类：顾客蒴一次竞争、再次竞争服务权与v 类相同，服务失败后不再保留服 务投，立帮霍藜溥求骚务。 根据多星l a n 运行机理，结含类模型的特点，得竞争冲突一淘汰v i 类系统模 型瀚如下 2 第一章引言 顾客t 到达_ 呻 夕 服务失败后不保留服务权，运回捧队室重 新请求服务 图1 - 3 类系统模型图 本毕业论文以图1 3 所示的系统模型为依据，为其建立数学模型，且在实现数 学解析和模拟实验后，与已有的v 类，类系统模型性能进行了比较分析。 青岛大学硕士学位论文 第二章前期研究进展 多通道l a n 数学建模方法的探讨 对局域网的性能评价通常是通过数学建模进行的，但是近年兴起的多通道l a n 网络模型中，由于服务员数量n l ，当定量评价网络性能肘，增加了解析的复杂度， 给系统的数学建模带来很大的困难。目前人们探讨多通道局域网性能时，往往能建 立扩展式m g n 排队模型，却无法进行精确求解。为了数学建模的需要，我们希望 能够知道各种近似解法求解扩展式m g n 排队模型的精确性，以便应用到具体网络 设计建造时，其理论指导性更加可靠。 本文的前期研究工作主要是：对两种常见多通道l a n 网络建模方法的精确性问 题进行了深入讨论“”，确定了适用于扩展m g n 排队模型的数学建模算法，从而为 本毕业论文的完成奠定了基础。 2 1 m g 2 o 的近似求解 2 1 i 相位法求解m g 2 o 1 ) 相位法1 16 1 简介 通常情况下，一般分布函数可近似分解为复数个独立的指数分布的组合，把每 一个指数分布称为相位。利用这一性质，近似一般分布进行有关模型解析的方法称 为相位分析法。 在m g n 系统模型中，把服务时问x 的一般分布用k 个相位瞒，毛，黾，x t ) 来 近似表示，每个相位遵从负指数分布，且为独立变量。这样，排队系统对于每个相 位具有马尔可夫性。若设第f - 3 号相位变量t 的分布f t ) = p ( t ，) = l e ”。， 则x 的分布，( ”、均值e 纠、二阶矩e l x “、方差v 分别为 f ( o ：p “蔓f ) = e ( f ) e ( f ) ( f ) e 州= ( “q ) 。 i = i e = ( “q ) - 2 | 1 v 【x 】= e x 2 卜( e 【功2 其中为卷积符，( h q ) “为薯的均值，以c j 为第i 号相位负指数服务的服务率， 可以通过不断调整k 和“c i ( - 1 ，2 ，t ) 的值来近似原服务规律。 2 ) 求解分析 取各相位的负指数服务率恒定且等值，即hc i 。鸬岛。f 。3 肚，通过使 取不同值， 第二章前期研究进展 来进行比较分析。下面以 = 3 为例求解。 = 3 时，参数“c 12 ：吐2 2 z 。3 。肛。顾客到达后，首先送到相位l ，服务结束后 送到相位2 ，相位2 服务结束后送到相位3 ，相位3 服务结束后整个服务结束。颞客 到达率为 。 设某时点相位1 ，2 ，3 的顾客分别为儿j z ， ，系统总顾客数j2 + ：+ j ，。系统 服务过程中，j t 减少1 个，j ：增加1 个；j z 减少1 个， 增加1 个。于是，系统状 态如图2 1 所示 、 h 一1 ，五凡 、 j ，h ，一1 、一一 、_ _ 一 、z 【 、 厅肚j ( 一j l 一- - 一i , ，z + 一l ，艘可。二，i _ 、一一 力一- - ，。、一 。 f 一一r 生二m 7 。一一p 2 7 2 、 ，7( ， 一l ，j ，+ li ) j l “，一1 ， ) 一一一一 一 一- ， ( b ) + + n 圈2 - i系统状态图 设状态壤搴为段五，五，点) ，出烫2 - l 燃猁默态方狴 ( 肆，岛+ 矗肛2 + 五硒c l + 置) ， ，j 3 ) = ( + 1 ) 芦，c 3 p ( ，矗五， + 1 ) + ( 五+ 1 ) 鸬q p ( 五十1 ，五一l ， ) 饶+ 】逸c , p ( a ，五十鼍轰一 ) + 盖一l ，五，点， 由圈2 1 9 0 ) 得 毛j l 茚手s ； 社芦l 丰j t 蹿投j p j t 。j = u + 1 ) 芦2 0 2 p ( j l ， + i ， 一1 ) 十( + i ) f f i q p ( j l + l ，j 2 一l ， ) + ；t p ( j l 1 ，j 2 ， ) 限定条伴。+ 磊。户珏，磊矗，设尹嫡，五荔，矮有乘积形解，繇 “， 一西 矗 以 一“ 一、一帅一么“ ， )萧e ： | 一， 一 一， j 一l m 入 堪 西 i i 二 青岛大学硕卜学位论文 眦赢胪a 竽。等学号笋 式中，c 为待定系数。由式2 ( 1 ) 知系统内顾客数为，的概率 p ，2 p ( j t ，五，j ，) ；圭窆产( m ，n , j j | 一呐 + ，l + ，。 肛0 肛0 一七一( 五“q ) 。( z 7 地c 2 ) “( z 7 飓q ) 卜 2 萎荟c 一鼍。鼍苦警矿= 0 = 0 ” 、j”，- 由多项式定理( + m 卜，磊：。盘咿。得由多项式定理一一一尸：q ”：得 ( 置，羁q + z ，段如+ , i 1 1 a ，c 3 ) = i j i 赫( a “q ) ”( 鸬c 2 ) 。( a 鸬岛) p j = 每( h q + z ，也c 2 + 地岛) ，= 导( 3 z 叫 由限定条件，萎乃2 荟参。7 “q + 且7 芦：c 2 + a 7 ，q y = 1 c = ! ! ! 笪! ! ! 丝生! ! 凸垦!( 3 a , u c ) i 岔 ，!智，1 2 - ( 2 ) 2 - ( 3 ) 2 一( 4 1 p ：盟丝! 彦里坐型 结合2 - ( 4 ) 式，“ ，!智 72 当嘲时，n 。半【i - | 3 3 , c + 1 ( 3 2 i i “c ) z 1 同理，取2 2 ，4 ，5 等值，分别进行解析，可推导出 n = 学噻掣 ：m 、 2 。1 ，2 剩余时阕分布鹌g ”1 求筋m t g l 2 0 程更薪过程中，糯察时点t 至下一次更新事件发生的时间称为前向重复时间， 又称必剩余时嘲。求鳃过程巾，设定系统颞察数为，的概率岛豹勰的彤式与m m n 系统柏葡，予是有 坟= 等瞧挈+ 高 设目列。拙c 一 船变热岛2 半障掣+ 龋 2 - ( 6 ) 第二章前期研究进展 蚺时日= 半 1 + a p c + 历( 2 p c ) 212 l z cl 。 当n = 时，1 ，5 【 2 2 j 2 2m g 2 o 的精确求解 2 - ( 7 ) 对m g 2 0 的精确求解是在设定系统为轻负载的情况下进行的。以时问t 为观察 时点，将从顾客开始服务到t 的这一段时间称为后向服务时间，对两个顾客分别用h 和“z 表示。显然，2 1 ，2 为t 时刻第i 服务员处服务的顾客的后向服务时间，其时间 分析图如图2 2 所示。由于共有两个服务员，所以可以利用扩展状态变量的方法将 状态过程定义为状态矢量帆u l , u z ) 的集合，其中n 为系统状态数( 即顾客数) 。 蹦毒擎孝热嘉 i 不 开仍为2 e 唑爿 鳓逸|+无l i + 盈 磊 ；f 盏等：，妻： 耋 暑f 到选，十，蹙为， 攮客彳 黼! - 褒罂 选 旱 无惑：蓄# 瓴。 咸 无到然七离开，仍为1巅 幽2 - 2 时间分析图 由图2 - 2 可得三种状态变化分析图如图2 ，3 所示 中、矗玎【十 鱼宣麓。，【，l1，。l1。，。l 图2 - 3 状态变化分析图 设系统顾客数为j 的概率为p j ，按图2 - 3 列出状态方程，并求解1 1 6 , 1 7 ，得 ( a 2 p c ) 2 见2 。一 1 + 三2 ，“c + ( t 2 p c ) 2 2 - ( 8 ) 一 青岛大学硕士学位论史 2 3 解析结果比较 如前所述，对m g 2 1 0 模型的精确求解，是在设定为轻负载的情况下进行的， 因此，到达率a 设定应比较小，取0 0 0 l 0 0 1 ，设定服务率p c 。0 2 ，分别利用2 - ( 5 ) 、 2 一( 7 ) ，2 ( 8 ) 式对m g 1 2 0 模型进行求解，并对系统中顾客数为0 ，1 ，2 的概率进行计 算，得出结果如图2 - 4 所示。 a 顾客数为0b 顾客数为l c 顾客数为2 图倒：1 精确求解2 剩余时闻分布法求解 3 相位法k = 3 4 相位法k = 4 塑2 解辑缝粟琵较嚣 分析图2 - 4 可得出如下结论： ( 1 ) 与稳拉法稳毙，嬲余对耀分毒法戆求磐络祭与耪壤瓣豹热线毙较接近，鞭忿可 知其精确性较好。 ( 2 ) 越摆位法对m g 2 1 0 摸型进行求勰对，邋过比较女取不礴谯黥魏线可以壤出， k 的增大并没肖提高相位法的精确度，所以在用相位法对m j g n 模型进行近似求 鳃对，k 不寅凝过丈。 ( 3 ) 融然结论( 1 ) 怒在设定系统为轻负载情况下得出，但由图2 4 可知，剩余时 阍分布法在精确度上脊比较嬲显的优势，因此戎对扩艘m g i n 肯达尔模型进行求解 时，麻尽量采糟剩余时闻分布法。 第三章星形l a n v i 类系统模型数学建模研究 第三章竞争一冲突淘汰存取方式类系统模型 数学建模研究 3 1 解析条件分析与运算符号设定 3 1 1 解析条件分析 l 、时隙的设定 为了在离散条件下解析类系统模型，将时间轴离散化，即把时间轴划分为以 时隙为单位的小间隔。选择时隙的原则是一个时隙中每个顾客源最多只能产生1 个 顾客。 2 、顾客到达 每个终端产生顾客是独立的，随机的。如果菜终端在某时隙无顾客，则它在该 时隙产生顾客的概率为n c 0 ，不产生的概率为= 1 一以。如果该时隙该终端有顾客， 则不产生新顾客。 3 、请求服务权 根据类模型的运行机理，到达缓冲器的顾客立即请求服务。如果服务员空闲 则为有效请求，服务员从请求服务的顾客中随机选择1 个进行服务，其余的顾客被 淘汰。如果这时服务员正在服务其他顾客，则为无效请求，该顾客被淘汰。两种情 况下被淘汰的顾客返回各自的缓冲器，各源终端分别随机确定一个延时时问重新请 求服务。这里所讲述的情况正是前述的“顾客第一次请求，再次请求都是随机发生”。 被服务的顾客，若服务成功，则离开系统，否贝l j 不保留服务权，返回排队室后重新 请求服务；若服务失败，返回排队室，并再次请求服务。再次请求又可能出现两种 情况；立即重新请求服务；经随机延时再请求。具体请求服务流程如图3 - i 所 示。 广一。一一一。一。一1 圈3 - i 类模型请求服务分析图 9 。丽堕翳固 一 一茸一匣囡| 一一 ：社 剿一 酩一 青岛人学硕士学位论文 由于、两种情况运行机理不同，因此类模型的建模研究针对、分别 进行。 4 、顾客被服务 顾客“服务期”设为定长，个时隙，无论该顾客是否被服务成功，如果经“服 务期”后的一个时隙，系统还有服务请求顾客( 包括原有顾客和新产生的顾客) ， 则服务员经该时隙后又进入“服务期”，该时隙称为有效请求对隙。若“服务期” 后的一个时隙，系统排队室颐客数1 ，但系统内无顾客请求服务，则服务员进入空 闲期。此空闲期一直持续到有顾客请求的时隙出现，服务员才又进入忙期。因此， 在类系统模型中，离开期由若干服务期和空闲期两部分组成。设一个离开期经k 次 服务成功服务一个顾客，出现空闲期的总长度为卅个时隙，则离开期= j 矿+ m 个时 隙。 由以上分析，不难看出，着能满足离开期中每个有效请求时隙都有顾客请求， 则离开期中不会出现空闲期：否则就有可能出现一次或多次空闲期。能否满足上述 条件，取决于多星l a n 的工作状态。 一般来说，多星l a n 的工作状态大致可分为两种情况： ( 1 ) 重负载情况，如图3 - 2 ( a ) 所示，即认为在系统内每个有效请求时隙都有顾 客请求，服务员在每次“服务时问”后的一个时隙都必有顾客请求，服务员始终处 于忙碌状态，整个系统内不会出现空闲期。 ( 2 ) 一般情况，如图3 - 2 ( b ) 所示，由于不能保证有效请求时隙的顾客请求，所 以闲期出现的几率大大增加。在两个离开期之间可能存在闲期，在一个离开期内也 有可能出现闲期。忙期，闲期交替出现。 忙期：在图3 2 ( a ) 中由连续出现的离开期组成；在图3 - 2 ( b ) 中由连续出现的服务 期组成。 闲期：系统无顾客时，服务员处于空闲状态 蔓三皇星丝! 型塑耋墨笙焦型塾兰堡堡塑塞 耍 _ 第，+ l 膏开期 瓣下 忙期 一斗阿一一 f | 即广 _ 田 未无7 + l ( 靠) ( a ) 重盘羹情况 秆一鬲b s ：一 l ( b j 一霞馕1 9 , 例3 - 2 类系统模型的时间关系 如图3 2 ( a ) 所示，r 时点为所选嵌入点，r 时点、r + 1 时点系统各离开一个被成功 服务的顾客，在离开期的其他时点不离开顾客。在离开期的第k 次有效请求服务时 隙，既有可能到达新顾客，又必有有效服务请求存在。 本文在图l ，3 所示的类模型中解析这里所述的( 1 ) 重负载情况。 5 、与、v 类模型比较 由于人们已经完成了i v 类模型1 1 2 - 1 6 的解析建模工作，考虑到本文需要，现 瞬岍。 翦请求时蠢 结柬曩务 麓请隶时一 鲭采量务 鼓请束时 一 k攻有效请求时豫 尊卜敬结索曩务 ? 无教请求 s 第0攻有慧请采时纛 毛第次结柬晨务 摹，次有鼓请求时 青岛大学硕 学位论文 选取r v 、v 类模型与类比较，其服务流程如图3 - 3 所示。 阻3 - 31 v 、v 类模龋与类比较图 对其比较分析如下； i 、类、v 类系统模型比较 ( 1 ) 服务员成功服务1 个顾客的情况不相同。v 炎模型中，一在接受服务的某 联客鼹努失败嚣，傈蟹裰务较，经连续蓿干次暇务，馥溅务成功褥离开系统；在诲类 模型中，服务员w 能要经多次服务若干个顾客，才有1 个顾客章运地获樽成功服务而 离开系绞。兹豢楚多次黢务麓颓客，嚣者楚多次著 # 激务霹一颓客。 ( 2 ) 就顾客第一次请求以及再次请求服务看，、v 类相同。为此对类进行 数学建模瓣，v 类酝报导茨蕻雾请求骚务熬分援真氆签终臻。 2 、类、i v 类模型比较 裁叛客骚势失败曩褥次谚求豹揍掇藿，类模型巾鲍( 1 ) 每斑类模塑一一致，罄 是不保留服务枚，顾客经“超时”时间返回排队室后立即重新请求服务一当类模 型处予燕( 2 ) 瓣蟪况时，与类模型蓑翅较大。为此零文在进行螭析援寸，应与类 1 2 第三章星形l a n 类系统模型数学建模研究 所报导的顾客服务过程区别开来。 以上比较不难看出，类模型是比较复杂的，是顾客请求服务与顾客服务过程 的新结合。因此，解析难度变大。 当为情况时，服务失败后再请求的情况与请求失败再请求的情况相同，上述 流程图可进行简化，如图3 - 4 所示： 图3 - 4 类模型服务流程( 简化) 本文难是根据图3 4 所示流稷对类模型进彳亍解析建模研究的。 青岛大学硕士学位论文 3 1 2 运算符号设定 n 顾客源总数，2s n 。 x ，r 时点系统顾客数0 z ，一l ，n = 2 , 3 f 0请求服务时隙的大小 r第，个接受服务顾客的离开期，单位为 岸一个离开期中，服务员处于服务期的次数。 s 第r + l 离开期中，k 次服务期结束的时点，o ”彭。其中为r 时点， 为r + l 时点 屯时点系统顾客数 段无顾客的源在1 个时隙产生1 个顾客的概率，= - - p g p ，有顾客的源在某1 个时隙产生1 个请求顾客的概率 ，服务员经1 次服务，成功服务1 个顾客的概率 以服务员经k 次服务，才能成功服务1 个顾客的概率。p x = n ( 1 b ) “1 只，r 时点系统顾客数为i ，r + i 时点顾客数由f 变为的转移概率，0 s n - i x ；，x ；，x j，时点后的第】时隙有f 个顾客请求，第2 时隙有霉个请求，第 ，时隙有j 个请求 ，时点后的第l 时隙有个顾客到达，第2 时隙有个到达，第，时隙 有f ，个到达 丽在平稳状态下，系统在r 时点的平均顾客数 巩r 时点，系统顾客数为i 的概率 吧 顾客在排队室的平均等待时间 w顾客在系统的平均滞留时问 4 第三章星形l a n 类系统模型数学建模研究 3 2 数学解析 ：j 2 1 分析与讨论 设一= o ，由于是重负载，所以，时点后的一个有效请求时隙必有顾客到达，立 即进入服务期。 设某顾客a 在，一s 内的某时隙到达，则到达可分为三种情况： 在有效请求时隙到达，并有幸被服务员选择服务。若服务成功，_ 离开系统， 与v 类模型相同；若服务失败，则返回排队室，经随机延时再请求，也就是说，在 第2 有效请求时隙，a 顾客可能再次参加请求，也可能不清求。 在有效请求时隙到达。但未被服务员选中，顾客a 被淘汰，返回排队室后经 随机延时再请求。同样，在第2 有效请求时隙，a 也不一定请求。 在服务员忙碌时到达，此时的请求必定是无效请求，顾客a 被淘汰，再次请 求的情形同。 由上述分析可知，在第2 有效请求时隙，提出服务请求的顾客，可能由3 部分组成： a ，该时隙新到达的顾客；b 第种情况中服务失败，且在该时隙又提出服务请求的顾 客；c 、所述被淘汰且在该时隙再次提出请求的顾客。 由图4 可知，无论是服务失败还是请求失败，顾客再次提出请求的过程是完全 一样的，即顾客自返回排队室至再次请求的时间闯隔都是随机的，所以在对类模 型进行数学解析时，可把b , c 两种情况合并考虑。当然，此种合并在v 类模型中是 不存在的。 不考虑上述中服务成功的情况，则有， 第2 有效请求时隙提出请求的顾客数 ；( 第2 有效请求时隙内新到达的顾客数) + f 重新请求服务的顾客中在该时隙 提出请求的顾客数，3 一( 1 ) 设只：重薪请求的顾客中，在第2 有效请求时隙提出请求的顾客数，同下 只，只斥。则3 - ( 1 ) 式变为 f 第2 有效请求时隙提出请求的顾客数) ；( 第2 有效请求时隙内新到达的顾客数) + 重新请求服务的顾客数) 岛 3 一( 2 ) 其中， 重新请求服务的顾客数) 青岛大学硕士学位论文 = 有效请求时隙请求失败的顾客数 顾客数 = 。时点的系统顾客数) 将3 一( 3 ) 代入3 一( 2 ) 得 + 无效请求的顾客数 + 服务失败的 3 - ( 3 ) 第2 有效请求时隙提出请求的顾客数 = ( 第2 有效请求时隙内新到达的顾客数) + & 时点的系统顾客数 b3 - ( 4 ) 另外，我们设定随机延时r 的范围为0 t ，则在第1 服务期请求的顾客在第 2 服务期必定再次请求，但具体哪一时隙提出请求则是随机选择的。同理，对于第2 服务期来说，顾客请求情况同第1 服务期，也可以分为如上所述三种情况，郎有下 式成立， 第3 有效请求时隙撬出请求的顾客数， = ( 鹪3 有效请求时隙内新到达的顾客数) 十 是时点的系统顾客数 与 簌兹类接， 赞女蠢效请求拜搴豫提爨请求麴疆客数，1 s 女s * = ( 第t 有效请求时隙内新到达的顾麟数) 十 蕞一时点的系统顾客数) 只 = ( 第l 有效请求辩陈内新羁这斡顾客数) + f 重新请求静颥客中在孩时隙褥出 请求的顾窑数)3 ，f 5 ) 参凳文献礴，在v 类篌壅牵，骞 第，+ i 有效请求时隙提出请求的顾客数 ； 第r + l 鸯散请求霹蒎蔌簧达颓客数 + ，时点原有顾客中提出请求的顾客数)3 一( 6 ) 逮较3 - ( 5 ) 、3 - 式毒瑷番爨，熟集恕3 6 ) 式巾数“r 瓣焘爨蠢鬏客”教麦“蓬 新请求的顾客”，则，对于有效请求时隙的顾客请求情况，v 类、类模型趋于 致。毽诧，下瑟兹对类模型逡行数学瓣辑聪，懑寿、类貘型弱袋鼹过羧具有羹黉 的参考价值。 3 2 + 2 鬏辔姨态转移穰率趣 设r 时点系统的顾客数蕾= i ，在，+ 1f i 寸点系统的顾客数x 。= j ，o s i , j s n 一1 ， 根据图3 2 ( a ) 。分析可得 l 当i = e 砖，薅= p 量+ ：= 、名，：o = p 在k 个有效请求服务时隙必有顾客请求，在。；够个时隙新到顾客j + 1 个 1 6 第三章星形i 。a n 类系统模型数学建模研究 以= 0 ) = p 在第l 有效请求时隙新到顾客个，第1 服务期新到，1 1 个，1 s 啊，+ i ；在k 一1 个有效请求对隙必有顾客请求，在t r ，= ( k 1 ) ，个时隙新烈顾客，+ i - 蚂个x ，= 0 = 只 第1 有效请求时隙到达顾客个，墨时隙到达顾客m 一个， 1 m j + l x ，= o ) 只 在k - 1 个有效请求时隙必有顾客请求，在c + 。一f = ( l v 个时隙新到顾客，+ 1 一粥个t = o ) 丘 = 艺艺c ，t ；( 以) ( 1 ) c 置( 吼川) 一一n ( 1 一曝，- 1 ) 43 ( 7 ) ，1 叶= 只o = p 服务员经k 次服务成功一个一= o 只 在k 1 个有效请求时隙必 f ， 有顾客请求，在i + 一f = ( k i ) f 个时隙新到顾客j + l 一鸭个x ，= 0 ) = & b 卜)3 - ( 8 ) = l e = 矗 在第2 有效请求时隙必有顾客请求，且新产生7 2 个顾客，在第2 服 务期产生顾客m 2 个，o s 鸭冬，+ l r c x ，= o p c 在k - 2 个有效请求时隙必有顾客 请求，在t + 一2 f = ( k 一2 ) f 个时隙新到顾客j + l 一确一卅2 瓜x ，= 0 ) = 只 在第2 有效请求时隙没有新到顾客，原有顾客有毛个请求， 1 5 屯啊；在是时隙新到顾客肼z 个，0 5 鸭s j + l 一啊一= o ) + 咒 在第2 有效请求时 隙新到? 2 个顾客，原有顾客有t 个请求，o t5 啊：在最时隙新到顾客m ：一，2 个， i s m ：j + l 一啊墨= 0 e = o - p ；) 肛“c ：p ，0 一p ，) _ 呻c ；： ( ，。1 ) n 1 凡( 1 一卜1 ) 啦 3 - ( 9 ) ，+ l ，+ j 一 j + j 一 b 。 。荟蕃点垛一一岛1 一& “”k 萎嗡p r 一”。强； - + 只 3 。( 1 0 ) 味： ( 嚷，- 1 ) 。 一帆( 1 _ ，。1 ) 啦吐 只= 最， - e 第- 3 有效请求服务时隙必有顾客请求，且产生，3 个顾客：第3 服务期 青岛大学顿士学位论文 产生顾客惕个，o s 鸭，+ l 一啊一、t = 0 b 在k 一3 个有效请求时隙必有顾客 请求，在t _ 3 f = ( k 一3 ) ，个时隙新到顾客j + l 一鸭一鸭个x ，= o ) 毛= # 在第3 有效请求时隙没有新到顾客，原有顾客有为个请求， 5 墨s 鹊+ ；在s 时隙新到顾客鸭个，0 - m 3 - j + l 一鸭一心、五= o ) + 在第3 有效 请求时隙新到，3 个顾客，原有顾客有如个请求，0 屯5 鸭+ m ：；在墨时隙新到顾客 晰l 一1 3 个，1 j ，s ，鸭j + l 一，吨一刖2 t = 0 e , i ：窆喾”1 “( 1 强广一t 苫，p 产( i 嘈p t n = ，恍。o 却 = l - c 2 _ 一帕( 7 1 ) ”一砖一唧( 1 一7 4 ) 一 ，tjj 1 + 1 - i 。呐“ j + 卜 2气+ ”1 只 ，) = 西，。以( 1 一岛) ”1 吐c ：+ ，只( 1 一只) ”1 = 也，e ，1吨= 。o c ；l 一- * t 3 一 也( 71 ) ” 一”一( 1 一略7 。) 鸭 吃= 坪k + 只 ) 圪 ；乓，f 第m 有效请求时隙必脊顾客请求，且产生顾客0 个，第m 服务 期产生顾客个，o o sj + 1 一警x ，：o 卜露 在足一膨个有效请求时隙必有 瑗客谚求，芝。j = l ，不产生裁鬏窖、墨一o ，= 骂 在第m 有效请求辩隙没肖薪到顾客，原有顾辫有个请求， l 蜒窆；在时隙新到顾客个，o s ，+ 1 一羔爿，。o + 墨 在笫肘有 效请求时隙新到。个顾客，原有颇客有翰个请求，o 蔓芝；在时隙新到颇 客一令，1 0s j + l - 、蕾= o ；3 - ( 1 1 ) 第三章星形l a n 类系统模型数学建模研究 孙扣错7 喜”蕾警曾， _ l c z 善，( 如”) ”毒( ，一“) “ 卧- 一辫”熏”誊屯咖t f 1 v c ? 誊。( 。= ，1 ) ”一善“t ，一。s ，一) = # o + b 。“ 只= 【1 一( q ，) 7 “】k - m 【( 1 一几) 一“7 】”。“ 嘞= 只矗气岛。名 k 一， b ) 夸。毫咤矿p p r ) * = 0 上 2 只一0j i - 1 3 户= p f t + l * 一；f f o ，f ，l 3 - ( 1 2 ) 3 - ( 1 3 ) = 尹 _ 兹夏，= 秽薅豫翻这，一i + 1 仑籁客，奁鬈次存款渗求程稼宓鸯黢客涛采， l k 爿，= = 只 第】谢效请求时隙必有顾客请求，第1 服务期产生顾客弼个， o 鹦j + l i x ，* i ) 只( 擞- 1 个裔效请求时傺必菊顾客请求，在i 。一，= ( 踅一1 ) ，个 薅稼产堡黻客j + 一i 理令、墨= i ) 只= 足，( 在第1 有散请求时隙未到_ 遴顾客，原有j 个顿窖商五个请求服务， l s 五 - i ；在s 1 个时隙产生m 个顾客，o 曼m j + l f 丘= i ) + 只2 在第1 有效请求 时隙新列个顾客tt 蔓g + l i 原有顾客有一个请求服务，l 簟i 在s 个时 骧产生鹊一令鬏鬻，礁s j = | 一j 、萎= j 一 童璺查堂堕主兰些篓壅 = ( 1 一以) “。9 | 口，o - p d i - x 。c 是，( “) “一( 1 一q g “) “ 只：= 芝1 磷。4 ( 1 - p s ) “屯杰9 ( 卜p 一j - i , i c 扎 ( q j - ) 一一n ( i - q j - j p l 只= 只， ) 十只： 只 ) = & 最 x 一1 个有效请求时隙必有顾客请求，在+ 一，= ( 置一0 f 个时隙 k = 】 产生顾客j + l f 一鸭爪x ，= i ) e = b ( 第2 有效请求时隙必有顾客请求，第2 服务期产生顾客m 2 个， o s r a ：j + l - i - r a l x r = i ( k - 2 个有效请求时隙必有顾客请求，在 i + 一f = ( k 一2 ) ，个时隙产生顾客+ l i 一帆一爪置= f ) 名= 弓， 在第2 有效请求时隙未到达顾客，原有顾客有t 个请求服务， i z ：s i + j l l ；在是个时隙产生m 2 个顾客，o s m ：- j + l i 一x ，= i ) + b 2 在第2 有 效请求时隙新到，2 个顾客，l s l j + l i m t ：原有顾客有x ：个请求服务， 1 s z 2 f + ；在& 个时隙产生m 2 - 1 2 个顾客，1 2s m ：j + l i 一竹一= i ，h - ir + 柏r + l f 一 b ，= ( 】一见) ”1 c 氛只。2 0 - p , ) “”。“c 轻。一 ( 嚷“) ”“2 ( 1 - q 。卜1 ) ”1 一02 l。j 一0 ，i - i + l 一*j + 岛：= 碍一p 。( 1 一p ；) ”“”c k p ，“o - p ，p t = ob ，1h = o i j + l h 四：_ 一b ( 1 ) ”1 2 ( 1 - q 。) ”一 b = b ， + b ， ) 己f ) = 易 禁材有效请求时隙必有顾客请求，第硝服务期产生顾客个， 封- o s s j + l f 一善、墨= f p x ( k 辫个窝藏请求辩豫螫蠢颓窖谚隶，芝= j + l f ， n = l = 一1 不产生额颞鬈、置z i 第三章星形l a n 类系统模型数学建模研究 = ， 在第膨有效请求时隙未到达顾客，原有顾客有个请求服务 11 妇f + 型； s u 个时隙产生个顾客，o s ，+ l 一，一芝、x ，：) + 村一1 ： 在第2 有效请求时隙新到0 个顾客，1 蔓0 j + l - i 一m 。：原有顾客有个 请求服务， 1 5 f + m - 4 m 。；在个时隙产生m b t 一0 个顾客 mi os m 。+ 1 一f 鸭墨= i ) 耻参i “誓( 1 - 岛厂芬” 矿”b ；+ 乳z - a。= 岛)鲁4 c 。n 。( 1 一只) “ 一01 2 = 0m。t”厶 吧小”) “、“ l - lj f 。i 叶 心：= = 0 性；0 c ，u 一。2 - - , k ( q f f - i ) ”+ 善“( 1 以1 ) ”一k 岛= 。 + ：k ) 只= 【1 一( 以) + 1 r 一 o - p 。) 一“1 7 r 7 + ” p o = 只( 只+ 只：弓+ b ：) ( - + 气，) b 以) ”轴j + 誊。州h j 沁 t o h 2 一”- 3 + 2 3 顾客积累数的平均值五， 设r 时刻系统顾客数为i ，则匀一窆，艺砖；芝翌謦 j 。f 灯= = j 舻= l 3 - 0 4 ) 其中，p # 表示经铲个时隙系统顾客数由f 。j 的概率，而当i + ，有限，矿取值1 q c + ，时 ? 。， 考= 气，孟t = 赐 hj ；o 3 2 。4 憋黠壤奉筑 由前灏的分析可知，在观察时点系统可构成嵌入马尔科夫链，即存在 2 t 矿 争 沙 嘻 青岛大学硕士学位论文 k j = 晶 墨。片1号2 0 b lp 2 2 0 0 如 ooo 000 昂m r ， ” 0 b f 3 - ( 1 5 ) 丌，表示平衡状态下，