（电路与系统专业论文）（ed）型休假mmc排队的稳态理论及应用.pdf

摘要 摘要 随着i n t e m e t 应用的普及和无线通讯( w i r e l e s sc o m m u n i c a t i o n ) 技术的发展，用户 鼹蒂宠爱两终黻务藏鬣( q u a l i t yo fs e r v i c e ) 麓簧求越来邃高，舔簌务矮量弱撵薅帮营 运成本的降低都离不开网络性能指标的分析与优化。因此，无线通讯网络性能的理 论努耩稻虚餍繇究是j 常现实又遥留豹任务。本文骧藤人舔宠成的多驻务台体镁稚 队理论为基础，依据无线通讯网络的遂行机制，平行地研究了一系列带有各种( ，d ) 休假策略的m l 删耗排队系统，褥到萁稳态性髓 静标分布及其条件随视分解结采，并釜 结合数值例子给出其性能分析与优化。 瞢先，对多服务台体假排队的研究状况进行总结、归纳，得到了套系统的处 理方法。然而，为了遗应各种腹用背娥，在多服务台休假排队系统中，一部分空闲 的服务台可进入休假状态，但为了使随时到达的顾客的服务不致延瀑很长时间，另 一些暇务台即使进一步空阕，也不休假，随时可供新到达的顾客使用。两且，如果 休假条件满足，服务员可连续休假。由此，刻画出了f e ，d ) 策略多重休假的m m c 排 驭模型。在建立撵队系统满足螅转移概率矩黪鼹基磷上，抿攫拟生灭过程与矩蓐j l 何解方法，给出稳态队长满足的齐次线性方程组，针对这个复杂的方程组，采用递 推迭锭方法导臻了稳态驮长分卷；j 毙照，发现并迁爨了条d ：e r t a n g 分毒的羞手毅性 质，根据这些性质对等待时间进行分析，得到了稳态下等待时间的分布；进一步证 稠了稳态指搽瓣条 譬薅李晁分舞结莱。 其次，对于一个( e ，d ) 策略多重休假的m m c 排队系统，由于服务员的避续休 经，可能延误隧靖虱i 纛戆颓客鹣服务滋求。嚣戴，提懑了一个羧务爨戆翌只能钵缓 一次的策略。平行于( e ，d ) 策略多重休假的m m d c 排队系统的分析过稷，类似地研究 7 f e ，国策略擎麓休假的m m c 摊酞模蘩。撮据矩阵凡辩解方演，获褥了模型鲍稳态 队长分布；根据条件e r l a n g 分布的若干新性质，确定了稳态”f 等待时间的分布。同 时，论证了模黧的条件随税务解结采。 再次，由于服务台的运行需要能摄，为了节省资源降低成本，当系统中顾客数 少于一定程度时可关闭部分空闲的服务台，著再增加新的顾客，财关闭的服务台需 重新启动。据此，研究了眩鳓启动时阅的m 小排队系统。根据矩阵几何解方法， 获得了模型的稳态队长分布：根据条件e r l a n g 分布的若干新性质，确定了稳态下等待 对闯的分布。网时，给出模型的条件髓极分勰结果。 蒸由大学工学蒋士学位谂文 最后，考虑到从休假到服务的转换，通常需要一定的成本，为了避免过于频繁 的转换，弓| 入闺值。因而，讨论了( e ，d ，) 策略的m m 陇摊队系统。根据矩阵几何 解方法，获得了模型的稳态队长分布，丽且，得到丁稳态性能指标的条件随机分解 结栗。 进一步地，结合数值例子，给如上述模跫在无线通讯网络中的具体应耀和优他 结果。 关键词休假排队：( e ，d ) 策略；拟生灭过程；矩阵几何解：条件随机分解；无线 逶谖蜒终 a b s t r a c t a l o n gw i t hp o p u l a r i z a t i o no fi n t e r n e ta n dd e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o n t e c h n o l o g y , r e q u i r e m e n tf o rb a n d w i d t ha n dq u a l i t yo fs e r v i c e ( q o s ) i si n c r e a s i n g t ti s i m p o r t a n tt om a k ea n a l y s i sa n do p t i m i z a t i o no np e r f o r m a n c ei n d i c e so fi n t e m e ti no r d e r t oi m p r o v eq o sa n dd e c r e a s ep r o d u c t i o nc o s t 。t h e r e f o r e ，t h er e s e a r c ho nt h e o r ya n da p p l i c a t i o no fw i r e l e s sc o m m u n i c a t i o nn e t w o r ki sar e a l i s t i ca n du r g e n tt a s k b a s e do nt h e m u l f i s e r v e rv a c a t i o nq u e u et h e o r yt o g e t h e rw i t ht h eo p e r a t i o nm e c h a n i s mo fw i r e l e s sc o m m u n i c a t i o nn e t w o r k , as e to fm m cq u e u e sw i t h ( 8 ，d ) 一p o l i c yv a c a t i o na r ep a r a l l e l l ys t u d i e d a n dd i s t r i b u t i o n so fs t a t i o n a r yp e r f o r m a n c ei n d i c e sa n dc o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o nr e s u l t sa l ep r e s e n t e d + f u r t h e r m o r e ，p e r f o r m a n c ea n a l y s i sa n do p t i m i z a t i o no fs y s t e m s a r es h o w nb yn u m e r i c a le x a m p l e s f i r s t l y , t h er e s e a r c hs t a t u so fv a c a t i o nq u e u ew i t hm u l f i s e r v e ri ss u m m a r i z e da n da s e t o fs y s t e m i cm e t h o d sa t eg i v e n h o w e v e r , d u et ov a r i e t yo fa p p l i c a t i o nb a c k g r o u n di nav a c a t i o nq u e u ew i t hm u l t i s e r v e r , p a r to fi d l es e r v e r sc a nt a k ev a c a t i o na n dt h eo t h e rs e r v e r s d on o tt a k ev a c a t i o ne v e ni ft h e ya l ei d l ei no r d e rt oa v o i dd e l a y i n gs e r v i c er e q u i r e m e n t o fa r r i v i n gc u s t o m e r s 。f u r t h e r m o r e ，s e r v e r sc a l lt a k ev a c a t i o nc o n t i n u o u s l yi ft h ev a c a t i o n c o n d i t i o ni ss a t i s f i e d h e n c e ，t h em i m i cq u e u ew i t hm u l t i p l e ( e ，d ) 一p o l i c yv a c a t i o n si sb u i l t b a s e do nt h et r a n s i t i o np r o b a b i l i t ym a t r i xo fm o d e l ，w i t hq u a s ib i r t h a n d d e a t hp r o c e s s a n dm a t r i x g e o m e t r i cs o l u t i o nm e t h o d ，h o m o g e n e o u sl i n e a rs e to fe q u a t i o n st h a ts t a t i o n a r yq u e u el e n g t hs a t i s f i e sa r el i s t e d b yr e c u r s i v em e t h o d ，t h ed i s t r i b u t i o no fs t a t i o n a r y q u e u el e n g t hi sd e r i v e d f u r t h e r m o r e ，t h en e wp r o p e r t yo fc o n d i t i o n a le r l a n gd i s t r i b u t i o n i sp r o v e d ，b yw h i c ht h ed i s t r i b u t i o no fs t a t i o n a r yw a i t i n gt i m ei so b t a i n e d 。m o r e o v e r , t h e c o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o nr e s u l t so fs t a t i o n a r yp e r f o r m a n c ei n d i c e sa r ef o u n d s e c o n d l y , i na l lm m cq u e u e 诵啦m u l t i p l e ( 8 ，d ) - p o l i c yv a c a t i o n s ，s e r v e r s c o n t i n u o u s v a c a t i o nc a nd e l a yt h es e r v i c er e q u i r e m e n to fa r r i v i n gc u s t o m e r s 。c o n s e q u e n t l y , t h ep o l i c y t h a ts e r v e rc a nt a k eo n l yo n ev a c a t i o ni sp r e s e n t e d s i m i l a rt ot h ea n a l y s i so ft h el v 1 m c q u e u ew i t hm u l t i p l e ( e ，固p o l i c yv a c a t i o n s ，t h ei t e l m cq u e u ew i t hs i n g l e ( e ，d ) 一p o l i c yv a c a t i o ni si n v e s t i g a t e d w t i lm a t r i x g e o m e t r i cs o l u t i o nm e t h o d t h ed i s t r i b u t i o no fs t a t i o n a r y q u e u el e n g t hi sg i v e n ；b yt h ep r o p e r t yo fc o n d i t i o n a le r l a n gd i s t r i b u t i o n ，t h ed i s t r i b u t i o n f 燕由大学工学博士学位论文 o fs t a t i o n a r yw a i t i n gt i m ei sg a i n e d ；m o r e o v e r , t h ec o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o n r e s u l t so fm o d e la r es h o w n t h i r d l y , c o n s i d e r i n ge n e r g ye x p e n do f s e r v e r s o p e r a t i n g ，t h es y s t e m c a r lc l o s ep a r ti d l e s e r v e r sw h e nt h en u m b e ro fc u s t o m e r sd e c r e a s e sa n dt h e s ec l o s e ds e r v e r sc a nb es e tu pi f t h en u m b e ro fc u s t o m e r si n c r e a s e s t h e r e f o r e ，t h em m q l cq u e u ew i t h 眩固p o l i c ys e t u p t i m e si sp r o p o s e d w i t hm a t r i x - g e o m e t r i cs o l u t i o nm e t h o d ，t h ed i s t r i b u t i o no fs t a t i o n a r y q u e u el e n g t hi sg i v e n ；b yt h ep r o p e r t yo fc o n d i t i o n a le r l a n gd i s t r i b u t i o n ，t h ed i s t r i b u t i o n o fs t a t i o n a r yw a i t i n gt i m ei so b t m n e d ；m o r e o v e r ，t h ec o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o n r e s u l t so fm o d e la r es h o w n 。 f i n a l ly t od e c r e a s et h es w i s hc o s tf r o mt a k i n gv a c a t i o nt os e r v i n gc u s t o m e r s ，i n - t r o d u c i n gat h r e s h o l dn ，t h e 撼黼琵q u e u ew i t h ( e ，d ，) 一p o l i c yi ss t u d i e d w i t hm a t r i x - g e o m e t r i cs o l u t i o nm e t h o d ，t h ed i s t r i b u t i o no fs t a t i o n a r yq u e u el e n g t hi sg i v e n ；m o r e - o v e r , t h ec o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o nr e s u l t so fs t a t i o n a r yp e r f o r m a n c ei n d i c e sa r e s h o w n f u r t h e r m o r e ，a p p l i c a t i o na n do p t i m i z a t i o no ft h ea b o v em o d e l si nw i r e l e s sc o m m u n i c a t i o nn e t w o r ka l eg i v e nh e r eb yn u m e r i c a le x a m p l e s k e y w o r d sv a c a t i o nq u e u e ；( e ，d ) 一p o l i c y ；q u a s ib i r t h a n d d e a t hp r o c e s s ；m a t r i xg e o m e t - t i cs o l u t i o n ；c o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o n ；w i r e l e s sc o m m u n i c a t i o n n e t w o r k s ( w c n ) i v 燕山大学博士学位论文源剖性声鹬 本人郑重声明：此处所掇交的博士学位论文( 8 ，d ) 型休假m a v t c 排队的稳态理 论及藏爝，楚搴夫在导孬攒孥下，程蒸出大学攻读博学位期婀独立进行辑究工 作所取得的成果。据本人所知。论文中除己注明部分外不包含他人融发表或撰写过 磐醑究袋采。对零文秘溪究王 筝秧蜜薰要贡簸煞个太葶蠢囊体，驽已在文中双明确方 式注明。本声明的法律结果将完全由本人承担。 作者签字：乏终秀五歹日期：游；月加日 燕山大学博士学位论文使用授权书 池载型钵稷m m z c 接双蟪稳态趱论及成援暴本人在燕山大学攻读搏”。 ：学位 期间谯导师指导下完成的博士学位论文。本论文的研究成采归燕山大学所宵。本人 蘩零发表将署名蒸出大学为繁一完袋单位及耀关太爨。本人完全了勰燕由大学美予 保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子 数零，兔诲论文被套湄释嫠蠲。本人授投燕出太学，霹竣采臻影印、鳐穿或蕻继复 制手段保存论文，可以公布论文的全部或部分内容。 保密口，在雄解密麟适用本授权书。 本学位论文属于， 不保密疆。 ( 请在以上相应方框内打“x ”) 捧者签 导师签 第1 章绪论 第1 章绪论 1 1休假排队的历史和研究现状 1 1 ，1经典无休假排队简史 排队是日常生活和工作中常见的现象，诸如至l 商场购物；去图书馆借阅资科； 病人到医院看癍；汽车到加油湛加油；文件等待打印或发送；路口缀灯下的车辆通 过十字路口：上下班坐公共汽车；船舶需要停靠码头；把损坏的设备送到维修部门 维穆；姆有关数据输入计算机进行存糖等等。总之，排队现浆由两方藏构成，一方 要求得到服务。另一方给予服务。我们把要求得到服务的人或物( 设备) 统称为顾客， 绘予暇务豹照务人员或服务机构统称为嘏务员或服务囊。于怒，颞客与瑕务台构成 一个排队系统，或称为随机服务系统，见图1 1 。 斗司e 十一 ； q t t u e i n gd i s c i p l i n e s e r v i c ed i s c i p l i n e l 图1 1 排队系统框图 f i g 1 - ld i a g r a mo f q u e u e i n gs y s t e m 捧软论( q u e u e i n gt h e o r y ) 又名随鞔鼗务系统理论，藏是磷究掇塞现象豹。 j 秘 学，它通过研究各种服务系统在排队中的概率特性，来解决系统的最优设计和最优 控箭。例如，菜火车售榘处有一个售蘩员为陆续至来的乘客拔先后次净迸 亍售票服 务。显然，乘客最关心的是排的队多长，等的时间要多久，他们希望售票员人数能 增加，售票速度越快越好：售票员刚关心他需要连续工作多长时间才能使| i j l 镊不再 存在丽得到休息；而火车站不但要考虑满足顾客的需求，还要考虑到车站管理在经 济上的合理性。因此，在这样一个排队系统巾，不偿需要研究队长、等待时问、忙 期( 连续繁忙时期) 等数攮指标的变化规律，丽麒需要在满足乘客服务基本需求的条件 下，研究如何使机构运行更为经济的问题。 拷驮论是髓规运筹学和应媚凝率谂螅重要分支，赡研究的阔题有缀强的实际背 l 燕由大学丁学薄学位论文 景，它起源于丹麦数学家a k e f l a n g 关于电话交换枫使用状况的研究，1 9 0 9 车他发表 的论文 t h et h e o r yo fp r o b a b i l i t i e sa n dt e l e p h o n ec o n v e r s a t i o n s ) ) 成为公认的排队论 中盼媛早著作。两斌，排队论研究的先驱人物是法国数学家e p o e l a c z e k 幕l l 苏联数学 家a n k o l m o g o r o v ，a y k h i n t c h i n e ，他们在这方面的研究课题都在3 0 年代完成并载 于其质来撰霹的著馋照f i 烈。爨二次擞爨大战以后，摇驮论褥裂迅獯发展，成必应愆 概率论、随机运筹学中最有活力的研究课题。它不仅建立了较完备的理论体系，而 量奁军事、受产、经济、管理、交邂等镢域褥到了广泛熬纛爝。5 0 每霞秘溪，荚溪 人d g k e n d m l 又系统的阐述了排队问题，并且利用嵌入马尔可夫链的方法推动了排 麸论瓣进一多发展1 3 t 4 l 。 1 1 2单服务台休假排队历史简述 随着计算机通讯网络( c c n ，c o m p u t e rc o m m u n i c a t i o nn e t w o r k ) 、柔能制造系 统( f m s ，f l e x i b i l i t ym a n u f a c t u r es y s t e m ) 、努步簧戆模式( a t m ，a s y n c h r o n o u st r a m 。 m i s s i o nm o d e ) 及电子商务( e c ，e l e c t r o n i cc o m m e r c eo re l e c t r o n i cb u s i n e s s ) 等高新技 寒豹发震，撵篷了大量复杂戆系统设专 露遂。这些系绞麴嚣秀逶常蔹鞍子淹狻 态而变化的参数，经典排队模型在处理这类问题时表现出极大的局限性。休假排 l l a ( v a c a t i o nq u e u e ) 翡谬 究正楚在这季争替景下始于筠藿童纪7 0 年 弋。终为经典撵敬系统 的推广，休假排队中允许服务台采取各种在某些时候不接受顾客的策略，这些暂时 中断溅务熬辩阀f 遥常是随税变量) 统称为体骰。 经典排队系统由到达过程、服务机制和排队规则三部分组成的，休假排队系统 只是霞琵基确上再增翮一个体假策略。针对不同的成用背景，可以引入各种各样的 休假行为。一个完整的体假策略，既包括休假开始和结束的规则，也包括休假时阅 的分稚。按徕骰开始黼则可将休假策略分为两类：空竭服务( e x h a u s t i v es e r v i c e ) 和非 空竭服务( n o n e x h a u s t i v es e r v i c e ) 。前者服务一旦开娥进行，裁要坚持工l 乍到系统中 无顾鬻，休暇只能程系统空闲时开始。后者泛指那些在系统中有顾客也可休假的 情况。按休假结束救则可将体假策略分为瑟类：单黧体假( s i n g l ev a c a t i o n ) 秘多重体 假( m u l t i p l ev a c a t i o n ) 。前者猩休假结束系统融有顾客等待的情况下开始新的忙期； 否则，进入邋嚣的空阕状态。其特点是服务援可处予忙期、阕期移缓期三秘状态乏 一。精者若在休假结束时系统中仍无顾客，就开始另一次休假，若休假结柬时系统 表至少骞一令颞客等特，裁舞始薪懿忙鬟，冀特点楚鼹务雯只娃子忙裳嚣鬏麓。这 2 第1 章绪论 里，需要指出酌是，忙期与闲期是不鞠酶。对顾客黼言，两者的区涮在予葵闯第 一个到达的顾客是否立即被接待；对服务系统而言，假期中服务员可不在岗，而 闲期中虽无顾客，但服务员必须在岗。此外，还有限蹩服务( l i m i t e ds e r v i c e ) 筑则、 递减暇务( d e c r e m e n t i n gs e r v i c e ) 规则、贝努剥休假( b e r n o u l l is e r v i c e ) j 巍则、门嫩式体 假( t h r e s h o l dv a c m i o n ) 规则、一般休假( g e n e r a lv a c a t i o n ) 规则等。 b 强与y e c h i a l t 5 】从有效利爆排队系统闲期豹观点如发，蓠先研究了m g 1 休假 排队系统，并引入了“休假”和“休假策略”等术语。实际上，导致服务暂时中断 静理由以有多耱多楼豹释释。铡鳃：对服务设施遴行调整、更蓑、维穆、绦莠或 能量补充；为提高系统经济效益，在相对清闲时转而从事其他工作；在计算机通讯 翘终审，整多爨复爱程淳楚瑾莱壤特定工终麴疆蠲，番成对莛缝类型王箨嚣求豹钵 假：在交通问题研究中，把堵车或机场关闭时间视为服务员休假等等。一方面，休 镁捧获菠浃了黻务哥畿发生孛羝这一雾麓事实，考虑铡建空瓣瓣蠢麸事辕韵王箨两 增加系统效益的可能性：另一方面，备种休假策略为系统的优化设计和过程控制提 供更大的灵活经。困鼗，作为经典捧敬耱自然发震，锩镁捧麸研究受到广泛关注， 并迅速成为随机运筹学的一个研究热点。 在休假稚队发麓豹早期阶段，研究工彳乍主要集中在肇服务螽体穰 排队系统上，见图1 2 。8 0 年代，研究熏点是单服务台的m g i 型休假排 队。c o o p e r _ f 6 1 与c o h e n l 7 l ，深入研究了几种休假策酶及服务规财的m ，g ，l 摊队系 统，f u h r m a n n 与c o o p e r e8 1 ，s h a n t h i k u m a r t g 】讨论了一般休假的m g 1 1 誊非队的随机分 解，h a r r i s 与m a r c h a l t l0 1 分析了m ，饼l 排队的状态相依性，k e l l a 与y e c h i a l i 1 】讨论了 休假m ，g ，l 排队的优毙权闫趱，k e i l s o n 与r a m a w a m y t 挖1 研究了空竭服务m g i i 模 型，c o u r t o i s l 3 j 讨论了有限等待空间的m g 1 休假模型。这些成果初步形成了以 随枧分勰为核心的钵瑕排队理论框架。1 9 8 6 年，几乎同时在美潮和欧洲发表 y d o s h ie h j 和t e g h e m t l 5 】两篇综述论文，总结了已有的研究成果和方法，标志着休 援接默系统已发震残为一个其有独立特色瓣辑究方向。接藩，d o s h i t ”】讨论，具 有可变休假的m g i 排队，r a m a n s w a m y 与s e r v i t ”】给出了b e r n o u l l i 规则的m g i 休假 模型豹忙鬻分辑，戮乃磉【i 8 + 9 】分别磺究了可控钵骰夔殛撼，l 捧麸及多级逶应性 休假的m g i 排队，n e u t s t 2 0 得到了n u g 1 型结构随机矩阵，t a k a g i l 2 l 】给出了空竭服 务黥聪簸l 傣穰簧 获鹣辩阔撩依性缝莱，t a k i n e 2 2 l 努辑了有等待羧澍懿酝怒，l 终 假排队，z h a n g 与v i c k s o n 2 3 】讨论了m g 1 休假排队的一些算法，m i n h 2 4 】讨论了 3 蒸鑫大学工学薄士学谴论文 具有般独立休假和空竭服务的m g 1 排队的瞬态解。从8 0 年代末到9 0 年代 末，羽乃硕等拉5 】首先成功地把艇阵几何解的方法弓i 入别g i m 1 休假排队的讲 究，把矩阵几何解从数值形式推j “到矩阵形式，推进了g i m i 型休假刳 队系 统和雾服务台休假排队系统的研究。相继的成果有田乃硕对n - 策略o i m i 排 队 2 6 1 ，p h 启动时间 2 7 1 葶墨p h 体假【2 8 】的g 瑚，l 摊队，攀重指数体假o v m i 4 驮 2 9 1 ，蹇 散时间g l g e o m l 排队【3 0 j 和g e o m g l l t 3 “，休假g i p h ，1 排队的稳态队长【3 2 1 及其随机 分瓣绩果f 3 3 】鲍硬究。近来，a a a l e j d 3 4 , 3 s 碜 突了具鸯d 蓑略的m g i 撵酞及葵往往瓣 题，c h 删等给出了具有一般休假的m g i 型排队的到达时间方法，z h a n g 等【”】分 撰7 多重休缎瓣g ，l 撼驳獒凝爨鼹务策略，f e i n b e r g 与k e l l a 3 8 1 分掇了其有露移动鞭 务台的m g 1 排队的d 策略的最优憾，k u m a r 3 9 】讨论了m g l 重试排队，c h o i l 4 0 等 讨谂了多重及续门羧薅弦戆a 伪，l 捺敬，k e 绘窭了其有n 。策略褒攒数体缀豹一黢 输入排队的分析【4 1 】，且研究了带有休假、启动和中断的m g i 排队系统的最优控 键j t 4 z l ，z h a n g 与嚣鞠f 4 3 l 碜 究了其有蠲篷n 懿g i m 1 簿虢，s e r v i 与f i n n i u l 讨论了其鸯 工作休假的m m l 排队，a l f a 与l i 给出了离散时间g i g i 排队的矩阵几何解方法1 4 5 】， 置总缩了离散时阊休霰模型淤j 。至魏，各静单服务台体假模登得载了系统的处理， 并形成一个较完整的理论框架。平彳亍于休假排队系统理论研究的进展，取得的结果 迅速在众多鞭域得羁了卓有成效的应用。蒯如：中心处理机时间表的设计与控制， 最优保养策略的拟定和实施，生产过程的经济效益分析，行政工作及其它维持性工 作对巾心处理机运行过程的影响，数据通讯嘲络中定时查询系统( p o l l i n gs y s t e m ) 的分 析，梁性制造系统的生产调皮，a t m 中的拥滚分析阀题。2 0 多年的发展表明，休假 排队研究不仅为经典随机服务系统理论的发展注入了新的活力和生机，也为排队论 在各耪赢毅技术领域的应用开鼹了更广阔的懿景。 _ c u s 煎t o m e r s 珈黑o 、 b e i n gs e r v e d e t l g t o r n e f 图1 - 2 单台排队系统 f i g ，1 - 2q u e u e i n gs y s t e mw i t hs i n g l es e r v e r 关于单服务台体假排驮系统研究鲍方法、缝果和文献，详见综 述d o s h i l l 4 】，t e g h e m 1 5 j ，田乃硕 4 7 , 4 8 1 或专著r a k a g i t 4 9 1 。 4 等 日 r 第l 章绪论 1 1 3多服务台休假排队的历史与现状 无论在理论上还是在实际应用中，多服务台休假排队系统都更为重要，见 图l 一3 。几乎在开始研究单服务台休假排队的同时，l e v y 与y e c h i a l i 5 0 】就讨论了休 假时间服从指数分布的m m c 排队，使用传统的生灭过程 5 1 1 方法，建立了队长和 正在工作的服务台数的联合分布的微分方程组，并导出了其稳态分布满足的的 差分方程。然而，由于问题本身的复杂性，这个庞大的方程组过于复杂，求解 遇到实质性困难。l e v y 与y e c h i a l i 只给出忙的服务台数的分布和一个甲均队长公 式。w h i r r 5 2 得到了g u g s 排队系统的嵌入更新过程，此外，还证明了g i g s 排队系 统的极限分布的存在性 5 3 】。v a n 与s e e l e n t s 4 给出了g u g c 排队系统等待时间分布的逼 近。v a n 与刚m s t s s 给出了m g c 排队系统指标的近似计算方法。n e u t s 5 6 】等推进了结 构矩阵分析方法在随机模型中的应用。v i n o d 5 7 首先注意到，可用以矩阵分析方法为 基础的拟生灭过程( q u a s ib i r t h a n d d e a t hp r o c e s s ，简记为q b d 过程) 【5 8 】处理m m d c 休 假排队系统。在这样的处理中率阵r ( r a t em a t r i x ) 将起核心作用。但v i n o d 只给出了拟 生灭过程刻画。未能求得率阵，因此没有给出稳态队长分布、等待时间分布等各种 指标。i g a k i 5 9 讨论了只有一个服务台可进入休假的m i m j 2 排队系统。对这个本质上 仍是“单服务台休假”的模型，给出了各种稳态分布。总之，在多服务台休假排队 发展的前2 0 多年中进展甚微，对多服务台休假排队系统的分析几乎未取得任何实质 性进展。 j c u 啦s t o m 蛀e r s o2 u e u eo 、 一 图1 - 3 多服务台排队系统 f i g 1 - 3q u e u e i n gs y s t e mw i t hm u l t i s e r v e r 直到近几年，这个领域的研究才取得一些较重要进展。几种休假策略的m m c 排 队f 6 嘶3 】和g i ，m ，n 排队畔，6 5 1 均给出了稳态指标的详尽刻画。进一步地，田乃硕嘟6 7 】综 燕由大学工学簿士学位论文 述了多服务螽休假排队的绻果。此外，t i a n 与l i 6 8 1 研究了p h 同步休假的m m c 摊 队，s a k a i t 嘏1 分析了带休假、启动期和关闭期的笈杂排觚及其成用，阐乃硕等 讨论了几种体假策略的m m ，c 排队 7 0 - 7 3 l 和g i m c 排队f 7 4 ，7 5 1 ，给出了稳态队长和 等待时间分布解析表达式，揭示了在己知服务螽全忙条件下的“条件随机分 勰援律”。c h a o 与z h a o t 7 6 1 研究了一类g i m c 休假搀队模型共提供了一套计算冀 稳态概率分布的递推算法。最近，m a d a n 与a b u - d a y y e h t 7 7 1 等讨论了具有b e r n o u l l i 单璧钵假繁旗的秀鼹务台封 驮，s h o m r o n y - 毫y e c h i a l i t 7 8 1 分毫蓐了其蠢体假帮睫规定 时器的突发到达排队，s i k d a r 与g u p t a t 7 9 1 给出了单麓休假成批服务排队的数值例 予。z h a n g 与t i a n t 8 0 - 娟在m 艨纨鬟 软中弓l 入了只龛诲部分骚务台钵强瓣策略，在这粪 策略中，一部分空闲的服务舒可进入休假状态，另一些服务员即使进一步空闲，也 苓戆体鬏，藏瓣霉傻新囊这戆颞客使矮。显然，部分藤务会傣霰凳宠分俸现了袭鬏 客服务和在假期从事辅助工作两者兼顾的思想。毫光疑问，多服务台休假排队系统 熬研究，不仅为经典箨麸论豹发震黧痤霜舜释了更广涓赘蓊景， 塾必将对巍霜疆税 模型理论的研究注入新的生机与活力。 美予多辙务台休假捧获系统研究的方法、结果，详觅舀乃硕专著i g 朝。 1 2排双论在无线通讯网络审酶应用 隧羞售憝技术萃鞋诗算毒陡技本款飞速发鼹，霹终在务行器韭中夔应建越来越广 泛。冤论是信息共享、合作，还是移动用户办公，处处体现着计算机网络的价值， 诗算撬鼹终悉经天照不在。蠢线霹终黻其簧 鑫速瘦态，产熬赘晶黪秘数量众多，潋 及技术发展速度快等优点，占据了网络应用领域里相当大的市场份额。然而，随着 蓼凄计算撬蔽寒静g 箍普及翡工监髹准逐步为隶场掰采纳翻接受，无线圈络茨应爨 领域派在不断地扩大。无线网的研究始于2 0 世纪7 0 年代，是传统有线网的延伸和补 充，楚一释受翻灵滔豹数据邋诫系统。无线溺豹盘溉使久 f j 不毖爵邈若辊器转，它 采用以太网的帧格式，使用简单，方便了用户访问网络数据，高吞吐量的无线网络 可敬蜜现1 0 8m b p s 能数蕹传输速率。 日前，有线网和无线网的各种高速网络传输标准不断形成，智能化网络专用设 备帮黼络管蘧系统的蒋遍应蠲，提赢了网络的性能和网络的管理能力。网络容错技 术更加成熟，增强了网络抗故障能力，出现了很多成熟的网络容错设备和系统，极 大的掇高了现有网络带宽的利用率，网络吞吐量也得到显著改善，彻底改变了无线 6 第1 章绪论 网络的面貌。随着通信事业的高速发展，无线阏络进入一个新的天地，它在很多应 用领域具有独特的优势：可移动性，它提供了不受线缆限制的应用，用户可以随时 上网：容易安装、无颁布线，大大节约了建网时间：组网灵活，即插卵用，网络管 理人员汀以迅遮将其加入到现有网络中，并在某种环境下运行；成本低，特别适合 于变化频繁的工作场合。此外，无线网络相对有线网络来说比较安全，无线网络通 信驭空气尧分矮，抟输黪簧号霹鞋跨越攫竟豹频段，嚣旦与鱼然鸳基噪声十分相 似，这样，使得窃听翥用普通的方式滩以偷听到数据。“加密”也是无线网络必备 豹一环，能奏效提高其安全蛙。 在近几年中，无线数据通讯已成为现代通讯中一个活跃的重要领域。由于服务 嚣求急掰增鸯爨，需要戆羧务氇不霉汉陵予电 毳浮疆。光线数壤遂谖羧务，铡魏，硬 携式计算、个人电子邮件等，在目前的无线系统中发挥着越来越重要的作用。这些 系统赣被嗣来支撑j “泛静毽摇税数据、声音、淘象、动蚕在凑静逶谖应瘸。囊于多 媒体和无线通讯系统的运行，用户可以从电话线的束缚中解脱出来，从而卒受更 大的通讯自由。惑之，无线遴谖技术遗广泛应餍蠢人们匏蠢常生产、生活当中。 然而，这就必然要求系统针对各种通讯需求提供不同质量的服务( q o s ，q u a l i t yo f s e r v i c e ) 。 农通讯系统中，我们的目的是有效地利用系统带宽。在避来的文献中，为 广在 所有用户中有散地利用有限的频谱，无线通讯中的随机信道接入协议已被f “泛的研 究。特别的，赋隙a l o h a 执议的研究见文献 8 4 1 8 6 】，这个协议使得大量不同的用户 以灵活的方式按享同一信道。同时，融有多个作者研究了多信道无线通讯系统中的 随枫接入按议以获褥熨大的绩道利用攀 8 5 4 7 】，这些研究表盟把带宽分割威多信道， 通过减少在同一信道上同时撩入的用户数，能够改进信道的输出率t 批延迟和其它 重要豹牲l 撂榕。此终，蠹予频分多鼹技术、褰度熬可靠性氍窖错率，系绞有容易 扩充、易于运行等优良的特点。 我键也注意裂，在大多数文献孛，努撰多售遘系统只怒必获褥数据传辘麴搜 能度量，而同时支撑数据传输和实时传输的多信道多业务的无线通讯网络( w i r e l e s s c o m m u n i c a t i o nn e t w o r k s ，筵谗建w c n ) 懿毪麓分辑还寒觅磅究。然露，逶谖耀终豹 越来越多的需求要求同时传输不同通讯业务( 例如，声音、视频、数据等) 的高容量的 传输系统静设计与开发。为了满是释类繁多瓣鞭务需求帮曩蠢有隈带宽静多建务霰 求，多信道多业务的无线通讯网络的模型有待千进一步研究。 7 燕蠡大学工学簿士学位论文 1 3本文懿觋究意义翻应曩l 懿景 盎扶2 0 世纪裙排队论产黛以来，随着经典排队避论磺究鼢深入发展，排队模型 已经广泛应用到许多领域。在工程分析中，簸常见的是利用耩于生灭过程f 5 8 】和指数 分毒的经典摊酞系统为实际阚题建横，基为这样静挟型容易获褥释橱鼹。继是，由 于复杂的实际背景及商新技术的出现，使得模型与实际情况有了或彩或少的偏差， 粳戡了模型翁真实性。因嚣，经典接麸模型觞瘟霜受裂缀大游局双瞧。蔼铼餐 驳 的研究弥补了这些缺陷，它爿；仅反映了服务可能发擞中断遮一客观搴实，考虑利用 空瓣辩海跌攀辕聩工僚两溪蕊系统效蕊赘可髓蝗；落虽，备耱蒋爨策略秀系统夔魏 化设计和过税控制提供极大的灵活性。因此，从2 0 僦纪7 0 年代起，休假排队引起了 夫家鹃广泛关注； 觅论在理论上述熄实际应用中，多服务俞休假排队系统都更为煎要。因此，许 多器蠹己经对多驻务奄终霰撵获系统避霉亍了详舞斡努辑，主要文献簇中在m i m i c 系 统上。但是，由于多服务台休假排队系统商度复杂，很雅给出稳态指标分布的 簿拆淡这式。最逶，这争赣城静醑究彀褥了一些窭艨性遗袋。t i a n 与l i ，t i a n ，l i 和c a o ，c h a o 与z h a o 粹，对几种体假徽略的m m c ，g 协d ，c 排队系统进行研究，不但 绘毒彳穗态飘长帮等符霉孛藉分布翡详鼷结采，还箍承了“条件德祝分解”魏律。热 外，z h a n g 与瓢a n 又弓 入只允许部分服务台休假的策略，使褥体假多服务台模型的磷 究更加深入。然而，对这类郝分服务螽休假的多服务台排队系统等待时间分布的研 究没眷凝的突破，没钱绘出其解析表达式。 淹了适应疆加广溅的应硝背景，深入研究多服势台休假排队系统，本文依次讨 论7 曳类f e ，毋棒稷簸臻的m m c 撵敬模型，其中o 戆一辩灵活缝控裁方法。 此外，引入( e ，d ，) 策略：设0 e d e 是一组正整数，一旦c 个服摄台中 鹃盼嶷凌空阕，其中斡e 拿爨务台弱辩进人椿霰狡态，勇羚d e 个鞭务台蘅可禊潼 s 时到达的顾客利用。考虑到扶休假到服务的转换，通常需要一定的成本，为了避免过 于频繁的转换，本文引入阑