（计算机软件与理论专业论文）综合业务星形lan的数学建模.pdf

论文摘要 返二一卜年来，诗冀极嬲终褥到了极大鲍发展，爨萁萋已进入裂一令瑟翡发袋对期， 即a t m 交换网和宽带业务综合数字网的时期。网络新时期的特征是在计算机网络业 已发展的基础上，将综合业务( 数攥、话啻、图像嚣服务) g l 入送森。本文鹱是为 将综合业务引入星形l a n 所进行的研究。 国内外套关多星l a n 的运行桃理已经商了介缡。在蜮蕊础上，竞争一冲突淘 汰存取方式，作为鹫形l a n 的一一种新的存取方式被提了出 束，并且搬据顾客请求服 务、再次清求服务、接受服务的各种情况进行组合，分了多种类型的系统模型。其 中竞争一狰突淘汰存取方式l 类、i 类、i i i 炎、v 粪系统模激的数学建模已缀完成。 本文就i v 类系统模型进行了数学建模，提出了顾客转移概率b 、平稳状态下系统平 均酞长露、颥客平均等待时闽等酌算式。同时进彳子了模拟实验，飘与i i 类模型进 行了比较。警此为“竞争一冲突淘汰”存取方式的成用奠定了理论基础。 关键词多星l a n ，竞争冲突淘汰式，数学模泌 a b s t r a c t i nt h ep 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 , ab r a n d n e we r a b e g i n s t h a ti s 、t h ee r ao f a t m s w i t c h i n gn e t w o r k sa n db - i s d n ，w h i c hi n t e g r a t e dv a r i o u s s e r v i c e ss u c ha sd a t a v o i c ea n dv i d e o t h ep u r p o s eo ft h i sr e s e a r c hi st oi n t r o d u c et h e i n t e g r a t e ds e r v i c e si n t os t a rl o c a la r e an e t w o r k ( l a n ) m u l t i s t a rl a n sw o r k i n gp r i n c i p l ea n dd e s i g nc o n s t r u c t i o nh a v eb e e nr e p o r t e d o n t h i sc 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 ne l i m i n a t i o n a c c e s sm o d e ( a b b r e v i a t e da sc 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 es y s t e mm o d e lo fc c e a mc a nb ec l a s s i f i e d s i x t y p e s ，a n dt h es t u d i e sa b o u t js t ，i in d ，i i i r da n dvt h s y s t e mm o d e l sh a v ea l s o b e e nf i n i s h e d i nt h i sp a p e r , o nt h eb a s i so fp r e v i o u sr e s e a r c hw o r k s t h e t i ls y s t e m m o d e li ss t u d i e d ，a n dr e s u l t sa r ec o m p a r e dw i t ht h ei it ho n e ，a n dw e g e te x p r e s s i o n sf o r t h et r a n s f e rp r o b a b i l i t yo ft h ec u s t o m e r s 昂，t h em e a nn u m b e ro fc u s t o m e r si nt h es t e a d y s t a t em a n dt h em e a nd e t a i n e dt i m eo ft h ec u s t o m e r si nt h es y s t e m s of a r , t h e t h e o r y f o u n d a t i o no ft h ec 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 n e s t a b l i s h e df o ri t sa p p l i c a t i o n k e y w o r d s ：m u l t i s t a r l a n ，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 l i n g 第一章引害 1引言 基形拓芥怒两域闻常觅的拓扑结构之一，以其扩展往、容易实现高速传送而著 称。近年来，伴随着光纤通信的急速发展，人们注意到星形拓扑很适予连接光终， 对光l a n 的开发研究旋起键进作用。予是，星形l a n 翘星形必l a n 的磷究积辍开 展起来。 目前潼内筛对疆形拓扑结构的研究主要集中在：( 1 ) 基于无源娶形网的波分多 路复用( w d m ) 办议的改进 i - 5 l 。( 2 ) 网络结构模型的改进及分析。( 3 ) 星形l a n 的多点访问信道存取方式研究及系统性能分据。 w d m 技术是一项鸯望列蹋巍终巨大豢宽瓣技术，无深鼙形耦会器能够绱鼙的 结合并传播艨杏躬发送波长，这意昧着鬃形物疆籀释是优越的。值楚由于交换过程 弓l 入的“电子瓶颈”问题成为限制通信两络吞吐能力的主要因素。所谓“电子瓶颈” 怒指电子线路的极限速率。按数字速率计，现行的电信网利用电的对分多路t d m 技 术，按照标准的同步数字群系歹i js d h ，最裹的数字速嶷墩子最离一级数字群麴速嶷， 掣1 0 g b i t s 。在熨裁，该数字速度必未能突破，这是受到窀静t d m 控术豹限制，常 称“电予瓶颈”。弱鼗交换技术作为先嘲络的一个组成部分成为研究热点之一瀚。 对于w d m 星形藕合网络的多路存取协议一般有两种方式：一种是预约方式， 一种是预分配方式。预约方式一般使用一个专用波长信遂作为控爨4 镶遭( 也可以不 采用控制信道 7 , 8 1 或采用多个控枣4 信道【9 。o b ，于是馋遂毒缀燕的利鼹率，然褥帮增加 了硬件复杂性零 进稷殍销。疆分配惦 义预先绘结熹分配了数据信邋和时间稽【l 。不 需要控制倍道，倍愚随着两络结点豹增长，挥酞延迟也会增大。针对这两种协议的 优缺点，应用于w d m 疆形藕合结构中的t d m a c 无冲突多路访问协议( z 2 1 和穗无源 双星网中使用n g t d m a 节点分组多鼹访问协议鲍结点聪方案( 8 1 胡继被提了出来。 通过改进网络继构是提裹网络性能豹又一令方法。广播星形潮络是最流行静分 维交换嬲络结梅之一。在羹受载漪充分乖j 用信遂容蠢的一个方法就是应用冲突避免 转换器f l 孤。在广播一选择波分多路复用( w d m ) 局域网中，给厘形藕合器入口安置 一个带有解决终端冲突功能的装鬻 1 4 l 也是一个比较有新意的提案。 屋形l a n 的另一薰要提察怒多星l a n 触研究 1 j - l ，在该l a n 巾，人 f 】提爨了 竞争一冲突淘汰程取方式f l 射。劳且壤撂鬏客请求服务、器次请求鼹务、接受鼹务豹 各转情墩避行缀会，分了六类系统模登。为了谱价竞争一冲嶷瀚汰存淑方式的多疆 l a n 的性熊，盈给改进网络设计挺供理论依据。关予演婪模型的数学建模和性能评 价已经歹_ f ：展起来了。其中，i 类 1 5 , 1 6 , 1 7 1 、i i 类l 、i i i 类l 、v 类【2 哪系统模型的建模 研究都已取得了重要突破。本研究是在它们的基础上，为在综会业务艇环境下捌媚 多星l a n 。对l v 类系统模型进每建摸磺究釉矬施评徐。 第一章引言 关于多星l a n 的运行机理及六类系统模型已有详尽阐述【2 l ，2 2 1 ，为了本论文建模 解析的需要，不妨予以简单描述。 多星l a n 的示意图如图1 所示。其中中心结点有m 条交换通道，m l 。用户 终端为，n m 。每个想要发送信息单元的终端，将产生的信息单元寄存于自己 的缓冲器，该信息单元被正确服务而离歼缓冲器之前，就在自己缓冲器排队等待。 信息单元要通过中心结点时，即使交换通道空闲，但如果同时要求通过的信息单元 数，空闲通道数，就会因竞争通道发生冲突。此时中心结点从发生冲突的多路信息 单元中随机选择与空闲通道数相等的数据单元让其通过，其余的被淘汰。通过中心 结点的信息单元，如果正确通过( 以下称为服务成功) ，则源终端会收到响应单元 a c k 。如果服务不成功，则源终瑞收到n a k ，且重新请求发送刚才的信息单元。在 冲突时被淘汰的信息单元经过“超时”h j 问后，由源终 端重新发送。通常情况下，选择“超时”长度为信息单 元发出至响应单元到达的时宽。总之，竞争一冲突淘汰 方式可归结为：终端发送信息单元后，在某一确定时间 内，要么收到a c k ，要么收到n a k ，要么因淘汰而“超 时”。收到a c k 后，终端有可能发送下1 个信息单元， 收到n a k 或发生“超时”时，终端的原信息单元重新 发送。 图1 多星l a n 示意图 习髑掣瞥服务成功 雾塞予三引引竺竺咿：一lhl t 刊菜再面赢li 保留服务i ：l 叁壑耋堡型il 壑要盗璺垒 ：! 孓i 。 2 第一孽引蠢 服务权的一位顾客如果服务失败，则保暇服务权，辩次接受服务，鸯至4 照务成功 或者可设定服务次成功。 l 类：鬟囊客第一次竞争派务校、再次竞争服务较都在驻务爨空闹对发生，这一 点与i 类相同。获霉导服务权的顾客程服务失败羼不像霉服务权，立即夔裁请求服务， 这一点与i 类不同。 两者熬区爨程鼙2 中嗳驻可焚i 。l 炎耩圣k 2 谈“l ”，l i 类辩k 2 接“2 ”。 i i i 类：顾客第一次竞争随机发生，爨次竞争服务权定期发生，服务失效羼像罄 服务权，再次接受服务，直到服务成功。或者可设怒服务次成功。 l v 类：颧客第一次竞争、再次竞争黻务投与i i l 类相同，觳务失效稻不褥保留服 务权，立即蘸新请求服务。 ， v 类：颇客第一次竞争、再次竞争服务权都是随机发建，狱得服务权的一位顾 客热栗凝务失败，粪# 保窝服务投，褥次接受服务，纛至灏务成功。或者可设定服务 次成功。 类：顾客第一次竞争、再次竞争服务权与v 类相同。服务失败后不群保留服 务毂，立鄄蘩耘请求骚务。 由上可见，i 、l i l 、v 类虽然顾客请求服务的时闽不同，缀是毒一个共霹点： 获得服务权的颁客服务失败后保留服务权，再次接受服务，直到服务成功。相应地， l 、壤类葭捐同点楚：获得缀务蔽静簇客缀务失败螽不傈窝服务权，变都重新 请求服务。从图2 e 可以藩出，i 、l i l 、v 类l l 重k 2 接“l ”，l l 、n 、磷类k 2 接“2 ”。 因此，本论文为兴系统模型完成数学模型和模拟实验后。就其实验结果与i i 类系 统横羹遴行了魄鞍。 出上述趱行枫理的说盟，可褥巍争一冲突淘汰存取方式类系统横型麴銎3 掰 示。该圈正怒图2 的一部分。 7 颟客t 到达_ 少 辍务失簸嚣苓摄窝黻务被，谴颟馨蠢耩壤鬃辍备 鹭3 竞争一 孛突海汰存彀方式 本毕业论文以圈3 所示的系统模型为依据，为其建立数学模型，盛在实现数学 解桥和横叛实验后，评价多星l a n 的性能。 3 第一：章前期研究进展 2 前糍研究进展 霄关文漱u 51 6 舀经对竞争一冲突淘汰存取方式豹i 类系统穰塑建立了数掌模 型- 但是只考虑了系统重负载的情况。在本文的前期研究中，合理的纳入了系统空 瓣麓，跌纛在系统轻、重受载莠存静倍况下，为l 类系统模壁建立了数学棱整。该 文”的完成，强有力的支持了对类系统模型的数学建模，为了保持硕士研究课题 豹逡续性与宠整性，不戆对 l 摹期聚究貉鸯瑟西鬏。 1 彰星l a n i 型流穰图 竞争一冲突淘汰l 类系统攘型豹滚摇妇嚣4 联零。 圈4竞争一冲突淘汰l 型流稳圈 根据该流程圈结合时间关系剿研，褥状态转移概率终必t 当f ：oh e 妒南c 渤f q ，q 岛= l c 荔j j n 。- ，j - i 黢务虽凄蠛窆瓣麓 观察顾客源必到达1 个顾客 观察顾客源必不到达顾客 第二章前期研究进展 当i 0 ，i l ，n 一1 时 名= c j - i + 。p c j - + l q 。“川 服务员未出现空闲期 考虑观察顾客源时，分两种情况 弓_ 嚣c 饥n - j - l p 气c 观察顾客源必到达1 个顾客 观察顾客源必不到达顾客 其中为顾客源总数；p c 为无顾客源在服务员空闲的1 个时隙产生1 个顾客的 概率，q 。= 卜p c ； 从状态转移概率出发，求出了数据单元服务期的平均长度、平均滞留时间等。 根据上述解析结果，经模拟实验，求得等待时间的曲线，如图5 所示。其中r 为 在观察时点系统顾客数为x 、观察顾客源a 有顾客的条件下，从观察时点起至a 终 端顾客被服务结束的平均时间。f ，为在观察时点系统顾客数为x 、观察顾客源a 无 顾客的条件下，从观察时点起至a 终端顾客第一次被服务结束的平均时间。 鑫 专 趟 邑 墨 豢 1 6 叩 1 4 0 0 1 2 0 0 1 0 0 1 0 01 02 03 0 幻5 d6 0 系| 壳顾客数x 图5 n = 6 0 时的，一引蛩 讨论：当负载较轻，出现空闲期且考虑服务存在失败的条件下，所得图5 的曲线真 实的反映了i 类模型的平均等待时间，由图可见，当系统顾客数x 4 9 时，见取值越大，等待时间就越小。当 n 固定时( n = 6 0 ) ，若到达概率见较高时( 如以= 0 9 ) ，等待时间很快饱和，且 5 哪 鲫 卿 瑚 。 第二章前期研究进展 几乎与系统顾客数z 的变化无关。说明当j v 固定时，为了减小等待时间，首要措施 是适当减少见。 6 第三章解析条什分析与符号设定 3 解析条件分析与符号设定 3 1 解析条件分析 1 ) 时隙的设定。为了在离散条件下解析i v 类系统模型，如同解析其它各类模型 一样，要将时问轴离散化，即把时间轴化分成以时隙为单位的小间隔。选择时隙的 原则是在一个时隙中每个用户终端最多产生1 个顾客( 即1 个信息单元) 。 2 ) 顾客到达。每个终端产生顾客都是独立的。如果某终端在某时隙无顾客，那 么它在该时隙内产生1 个顾客的概率为儿，不产生顾客的概率为q 。= 1 一p c 。如果某 时隙该终端有顾客，那么该时隙该终端不再产生顾客。因此当我们开始考虑这个系 统时，如果系统有i 个顾客，这个时隙内的顾客到达满足二项式分布，具有参数 ( 一i ，p c ) 。 3 ) 请求服务权。每个终端新产生的顾客，立即请求服务。如果这时服务员正在 服务其它顾客，那么服务员不理睬新产生顾客的服务请求，新顾客立即返回自己的 终端，且经过1 个“超时”时间后再次请求服务；如果服务员空闲，则必然从请求 服务的多个顾客中随机选择1 个，对它立即服务。其余被淘汰的顾客都返回自己的 终端，再等待1 个“超时”后重新请求服务。这样的请求服务一直进行到淘汰顾客 被服务员选择为服务对象。显然，某一顾客被选择为服务对象时，可能发生于第1 次请求服务，也可能发生于多次请求服务之后。在竞争一冲突淘汰方式中，将服务 员非忙碌时出现的顾客请求称为有效请求( 请求顾客有可能被选择为服务对象) ；将 服务员服务时出现的顾客请求称为无效请求( 请求顾客不可能被选择为服务对象) 。 4 ) 顾客被服务。获得服务权被立即服务的顾客，其“服务时间”为信息单元发 出至响应单元a c k ( 或n a k ) 到达的时间，本文设为定长厂一1 个时隙。无论该顾 客是否被正确服务，如果经“服务时间”后的1 个时隙，系统还有服务请求顾客( 包 括原有顾客和该时隙新产生的顾客) ，则服务员经该时隙后又会进入“服务时间”。 本文将该时隙称为有效请求时隙，且划入服务员的“服务期”。于是服务期= 有效请 求时隙+ 服务时间= f 。某顾客得到正确服务至下1 个顾客正确服务，服务员可能要 经历若干服务期服务多个顾客。本文将这一段时间称为离开期。连续出现的离开期 使服务员不断处于忙碌状态的“忙期”，显然忙期由若干离开期构成。与忙期对应的 是闲期。本系统模型中的闲期与经典排队论中的闲期区别较大。在经典排队论中， 当系统无顾客时，服务员处于空闲状态而出现闲期。而在本模型中，并非仅仅如此。 当系统有顾客，但在离开期之后的若干时隙不提出服务请求时，服务员亦可处休闲 状态而出现闲期。因此这星的闲期由上述两个因素形成。 设经1 次服务期某顾客被成功服务的概率为风，那么在一次离开期中服务员经 第二章解析条件分析与符号设定 k 次服务，最后1 次被成功服务的概率显然遵从几何分布，即为p s ( 1 - p s ) “1 。 通过上述分析和说明，可得类系统模型的时间关系如图6 所示。在图6 中的， 时点、r + 1 时点等，系统各离开1 个被成功服务的顾客，在离开期内的其它时点系 统不离开顾客。在离开期的k 次有效请求时隙既可能到达新顾客，又必有有效服 务请求存在。在其它时隙虽然可能到达新顾客，但只能是无效请求。 图6i v 类系统模型的时间关系 5 ) 以+ l 与第k 次请求服务的关系。在第k 次服务之前( 包括第k 次服务) ， 系统的到达顾客数一定要达到一+ + l ，但究竟在哪一次服务时达到，完全是随机的。 如果设第肘次服务中系统顾客达到4 + 。+ 1 个，那么当m = k 时，说明第世次服务 中系统顾客数达到z + i + 1 个，并且被服务的1 个顾客经该次服务成功后离开系统。 离开时点正是r + l 。这时系统中还剩一+ 1 个顾客，实现了由t _ 以+ ，的转移。当 m k 时，说明第m 次服务中，系统顾客数已达到以。+ 1 个，以后的k m 次服 务期系统未产生新顾客，而且第m 次寸第岸一1 次服务期并未服务成功顾客，在第足 次服务中才使1 个顾客服务成功而离开系统，系统剩余下以+ ，个顾客，实现了 一_ 一+ l 的转移。显然系统何时到达4 + i + 1 个顾客与系统在离开期的服务次数并 无对应关系。为了实现离开期经芷次服务期后离开1 个顾客，每1 个有效请求时 隙必须至少要有1 个请求服务的顾客( 包括本时隙产生的顾客) 。也就是说，研究离 开期顾客由4 斗墨+ 转移的前提条件是每一有效请求服务时隙系统必须有顾客请 求服务。由于i v 类模型中前一次有效请求服务时隙请求服务的顾客被淘汰后( 或服 务失败后) ，在下一次有效请求服务时隙必定再次请求服务，所以这些顾客再次请求 8 第三章解析条1 ，| ：分析与符号设定 服务的概率为1 。于是，只要蒴一次有效请求服务时隙系统有顾客请求，则离开期 箕稔各次有效请求服务时豫，必定有顾客请求服务，因此类模型是可以数学建模 麴。 3 2 运算符号设定 置在r 时点被j e 确服务的1 个顾馨离开后，系统的顾客数。 0 x r n i ，n = 2 ，3 ， 爿，。杰r 瓣点，被强确溅务静1 个颥客离歼螽，狡态处搿的颥客数。掰魑这 撵提爨故：在r 矮弱第啦瓣踩，墨令蹶客中鸯盖，8 ；令请袋骚务。潞现墨。楚出予在 第1 斗，个时陈j i 孛请求蹶客逶霉亍区分的结采，1 o ：y o y h j 之翦系统产生了新颥客，按上面设定y 之前系统原有的f 个顾客未提出服务请求，刚 厶不定，由凝产生蹶客静状态来确定磊。 k 在桀离开期中服务员臌务鹅次数。l k 0 ( 即系统有顾客) ，且有效请求时隙必在离开期之后仅接的第1 个时隙到第l r 个时隙。其中 p i x = j x ? = i 、 l l = 尸( 第r 个顾客离开后的空闲期长度为，在第，+ 1 离开期共蓟一i + 1 个新顾客 ，z 0 到达x r = i l 一i 2 h 空闲期，的出现仅仅由于原有f 个顾客未提出服务请求，在第r + 1 离开期共 l = 0 葡一i + 1 个新顾客到大、z = i + ， 由于在l 前的1 个时隙产生了m 个新顾客 而使空闲期终止，在第r + 1 个离开期共蓟一i + 1 个新顾客到达z ，：i 1 0 第三章解析条件分析与符号设定 一i = ( 吼“) t r = o l r 一2 + ( q n - , ) t r = 0 以。- 1 风c s + l - ( 1 一矿) 肿( qk 1 ) “7 一 k = l = 【1 一( 吼。) “】，( 1 一q c n - i ) 吼“p ，c j + 一l ，- ( 1 一吼) 川_ 1 ( 吼) ”一_ i = l ，+ l 一 + 1 - ( q c l , - i ) “】( 1 一q c “。) c l p c ”q 。“” m = l - q s 卜1 几c j + 一l - i 。- “( 1 - q , x f ) 川叫圳( 吼_ ) _ 一 ( 1 ) 足= l 由( 1 ) 式可见，一+ 。的取值还与有关，即在t = i ，且有效请求时隙在离开期之后 紧跟的第1 时隙至第2 时隙的条件下，并不能由x ，唯一地确定x 川，当x ，相同时， 会有不同的值，而值与墨一。有关，所以 z ) 的马尔科夫性不成立于是当讨论选 ，为嵌入点时， 以) 的状态转移不能形成马尔科夫链。为此必须另想办法，不然 类模型在忙期+ 闲期无法进行解析。 由一。的定义得知，在r 后的第k 时隙，k = l ，2 ，以个顾客中有以。个参加 服务请求。当 x r ) 确定后，不仅一确定了，而且，也是确定的，从而在下1 个有 效请求时隙及离开期的其它各个时隙，新到达顾客只与有关，即t + 。的分布仅 由x ，确定，故 以+ 能形成一个嵌入马氏链。 p 灯 j 吼 一 黜 c p 卜 g 。心 啪 吼巴m c 卅d 第四章数学解析 4 数学解析 4 1 转移概率气：，j ，m ：，j ，) 在图6 中，设，寸之间为间隔( 1 ) ，其中各时隙到达顾客后，在时点顾客 所处状态为 ，j c 2 ， i ) ，在，时点顾客所处状态= i 为( f l ，j 2 ，) ，为清楚表 达，下面将( 一f 2 ，i 7 ) 表示为( i l ，i s ) 。各个时隙到达的顾客分别为 川一， t ) ：一t ， ”，一，o 设啊_ 1 2 之间为间隔( 2 ) ，其中各个时隙到达顾客后， 在r t 2 时点顾客所处状态为 ：”五：) 2 ， ：) ，。显然各个时隙到达的顾客分别为 2 ) 一 l ”， 2 ) 2 一 呲， 2 ) 一 1 ) ，依此类推，设一j 哼n k 之间为间隔( k ) ，其中 各个时隙到达顾客后，在时点顾客所处状态为 k ) i ， k ) 2 ， k ) ，。即，+ 1 时 点，存在五驯= 工+ 1 ， 删= j 2 ， ，= 矗。显然各时隙到达的顾客分别为 一 删，一缸呲，厂 ，。其中 删l = ，虹i ) 2 l = f 2 ， 叫，k ：l2 f ，1 k 。 当，i + j 2 + + y s o 日寸 ( 6 ) ，训胁，n ) 。以k + = ( 一，小，矗) 、一+ = ( ，讧，f ，) m 堙得 厶k ， + 式 几” ，j、( = ， 理 整 第四章数学解析 = j p 在第，+ 1 时隙丌始出现请求服务的顾客( 新到达顾客或原有顾客 r = o 有请求者) ，x r + l + = ( ，止，办) t + = ( i l ，2 ，f ，) ( 7 ) 为t i ：t - 算p x 。+ x ，) ，必须对，时点后闲期与第l 服务期的关系进行分析，如图7 所示。 五( ，f ，) i u i j i j 2 ，一， l j ，) 图7第1 服务期与闲期的关系 当，= o 时，求鼻忆_ ) ( 九j 2 ，力) 要根据的情况而定。因为当 = 0 时， l 1 ，即 l ”一f l l ：当0 时，i 0 ，即 川一o 。故分别予以求解。 当 = 0 时 ，”删 ，n ，川 c 艘囊n “川“吼“以。 。) + p c 枷b 吼“弘m1+j1警。c。jro-imm旷m*w饥-】j m j 。“= o 。 。 一jl+萎lj(i一l。础铲pe矿-qcnrm川笠”。cj(z)24却(m矿。一，：j ，f 础z 7 州”m 矿巾” 一， i ” f “。u + 。见栅： ( 2 ) l 。j ( i ) 1 2 0 2 ) 2 - 舶2 = o ” q c n j i - 2 ) 。 2 】2 + ) i + l 2 4 、p c “2 wq c n j n 2 】 b 吨 矿砟 c 卸 笙m 呲 矿峨q”伽 j 忡帅 第露章数学解析 浚式中共蠢趸个方括号，l k 式，褥 ，i ，w h ：，山) ：【j l + l - 7 lc 嬲, 成坩n 吼岍彬n 笠c ) i l ) 2 ， 州i 2 。憎q 吼。r 川”2 2 芝c m ( 1 ) l i 柑f柑咖盯- i 咿蚋成j ( i ) l - l ! g c n j n l 爿 ( 8 ) 其中 辩= h 【 c j k ) y j i k ”或取扩船啦吼舭埘“瑚堋强“ c j x 山) 2 i k j 哪( x m ： + - 1 ) l p c 矗。2 一矗2 一2 q c n j ( k o j ( x ) y j f x ) 2 + j ( x q ) i + 矗x 由2 - c 一j ( - ( 4 l k - j ( r - k i “1 ) 山，p c 4 。7q c ”，“。】 ( 8 ”) 强i 0 辩 雌酗桫矿fj 篁i j o ) h i 吨繇峭坩“。笠c ，j ( t 。) 2 i 2 。m + p c 棚& 矗! i o i - - 0 1 0 ) 2 - 吐= o 毂w ，瑚扩椭2 埘。) j 呈- q ：。嗖椰轴“书巾铲+ 札，瓤啪t 封，) 弘函数联x ) = 等：霹涛) 式帮( s ) 式合势必令式予棚 鬈吣缸酗缸由j = 【( 1 + 1 4 磷! 翠救 ) i i l q c n 鼻却 + + ) + 敝肌鼻) 艺c 袭跣。+ 致角砖一繇肌墨懂l l 嚏嘴鸭“ j ( n ) 2 i 2 3 u j j 4 睇j 端i ) l 蛳枷“- ) 即咿埽，p c 栅矿如】h o ， 口一1 ) ， 口、= o ，1 ，一l ，它们分别由顾客状态的转移概率气j 2 ， 拈，) 构成。其中 心，】- 【鼻3 ；：舢，鼻3 i ：川m 鼻& 嚣。鼻a i ；。舯，鼻茹k 们鼻3 ；舯，鼻：菇哪) 1 比如当口= 0 ，= 1 ， 【l 】= l 鼻i ；l o ) 鼻t o r ，0 】= 0 i o j )鼻编；( ) 冀爱；( o ，1 ) 鼻o t r 0 ) = o o ( )量t o r ，o ) = o 。( ) 1 。 只：蒿。一。，1 ( q j c - u ) ，+ 。1 c 坟，。，= f 篡i ：i ：二卜f 兰二；：f 暑笺参：o 紫茅三盂妻磐取- 1 c - s ， 【鼻t 。，j 【( 吼“。) 7 “j 一 星婴里墼堂坚堑 一 _ _ _ _ _ _ _ _ _ - _ - _ _ - - - _ _ - _ - ，_ - _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ _ _ _ - - _ - _ _ _ _ _ - _ 一 t ：l ：x i l 当口= 2 ，7 = 1 时，【岛1 _ 。 i 】_ i l ，赫舢 瞄i 帆1 ) 圪盎舯，吼：拓。， 一l 喘嚣m i 鼻t 2 r ，0 ) ( 1 = o ，o ) 鼻l 蔫m 冀t o r 驯= 1 o ) ( q c n - 2 ) 7 ( q c ”一2 、7 ( q c l v - 2 ) ，+ 加) 档蝌删 档l m m ) 麟阳。 目撼。四积喘耘目曷+ 。户“) 4 , 1 1 。，一。， 瑶敖瑶盎。舾u ：。p 描。m 旷，、榴q 1 p 揣m “p 、堆淼+ 一， ( 1 7 ) 比如当口= ，卢= ，时，c c t - ，= 鼻编i 0 1 墨饔：曩锰。，鼻铽叫， 。 以上是厂= 2 的i i l i 况，厂为其它值的表达式很繁冗，但都能写出。 由于存在( 0 ，0 ，o ) ( ，五，) 及( ，x 2 ，_ ，) _ ( 一l ，五，) 一_ ( 0 ， ，) _ ( 0 ，2 2 - l ，) 寸寸( o ，0 ，矗，) _ ( 0 ，o ，0 ) ，故 以+ ) 是 一个有限嵌入马尔科夫链， 一+ 存在平稳分布，而且= ( 硝“0 ，硝“。0 ， 弼“。1 0 ，硝“1 0 ，硝“。) 是唯一的。 4 2 绝对概率( 样x l ) ( x j 0 是平稳状态下，时点被正确服务的1 个顾客离开后，系统顾客的 各种状态为 ，+ = ( f ，f ，) 的概率。根据上述讨论，系统顾客的各种状态 x ，+ 在r 时点形成了嵌入马尔科夫链。则可得到下式 桫胪 = 舻呱。”如，) ( 1 8 ) n + f ，+ + l r = 0 因为吲是平稳状态下，r 时点被正确服务的1 个顾客离开后，系统顾客数为，的概率。 故有 g =赢“。 ( 1 9 ) 第四章数学解析 4 3 平衡状态下的平均顾客数府 由于存在 x r ) 的平稳分布昂= ( 口，r ，r “1 ) ，所以很容易得到平均队列长度 为 一l 厨= t 】- z l p o ( 2 0 ) 4 4 平均滞留时间 设某顾客的无效滞留时间为阡，无效。降，无姓是顾客第1 次请求服务至请求服务 正巧在有效请求时隙的时间间隔a 设某顾客的有效滞留时间为效，效是顾客 第1 次请求服务e 巧在有效请求时隙发生至该顾客获得服务权后被正确服务的时 间间隔。故顾客的平均滞留时间为 e w 】= e 陟鲁效】+ e 【效】( 2 1 ) 显然研效】= e 【t 】e l k 】， 其中e k 】为每个顾客的平均服务次数，e l k = l 只。 顾客第1 次请求服务究竟出现在服务期的哪个时隙完全是随机的、而且通常是 等概率的。又出建模过程可知，系统的无效请求时隙共有，一1 个，因此平均等待的 时隙为( 厂一i ) 2 ，而每个服务期平均提出服务请求的顾客数仍为研x ，故r 研阡，无效 - e 【z 】fe k 】( f 1 ) 2 当r = l 故e w 】= 目】，b + 研z 】f p s ( f - 1 ) 2 = e 【以】，( 1 + f ) 2 ( 2 2 ) 第再章模拟实验及结果分析 5 模拟实验及结果分析 可以验证，( 1 4 ) 式p 矩阵中的元素0 有重复概率出现，例如厂= 2 时的昱l 有三 种情况，如图8 所示，其中前两种情况是一样的：在r 时点系统顾客数为2 ，在r + 1 时点系统顾客数为1 ，空闲期长度为0 ，且无顾客到达。因此矩阵尸不满足马氏链的 n l 限定条件弓= 1 。 j = o ( 2 0 ) 图8 f = 2 时b i 的三种系统状态转移图示 现设定值和厂值t 考察转移概率矩阵气，1 2 ，) ，如f _ 3 ，厂= 3 ，( ，如，f ，) 共有( 3 ，o ，0 ) 、( 2 ，l ，o ) 、( 2 ，o ，1 ) 、( 1 ，2 ，0 ) 、( 1 ，l ，1 ) 、( 1 ，o ，2 ) 、( o ，3 ，o ) 、( 0 ，2 ，1 ) 、( 0 ，l ，2 ) 、 ( o ，o ，3 ) 十种情况( 厂= 3 ，为其它值时( ，f 2 ，0 ) 要作具体分析) ，得到如下矩阵： 岛= 鼻3 n o ) ，2 鼻2 o m 鼻3 ，o ，o ) ，3 鼻2 t ) ，3 o 0 ) 舻l 鼻2j 1o ) 州 鼻o n3 1 2鼻o n 3 ) ，3 鼻o 0 ，耽一 i l j 一1 j x 能取矩阵中的范围 蹴相位转移( f l 一，f ，) _ ，的概率满足马氏链的限定条件酗n - i “山旷1 ，因 此就厂= 3 进行实验，得到两组实验数据( 见附录1 ) 。 由实验结果，我们可以看出：一旦f 值被设定，如- 口，o 口。n ，矩阵可以简 化成下面的形式 巴，= 呐) ，2 鼻o n 川2 鼻o n n 2 气，1 2 b 日o 3 o t 3 ) , 3 川一 鼻o 一 j i o 吣) - i + 之+ f 3 = 口 口一1 ， n ， 职能取矩阵中的范围 第彳i 章模拟实验及结果分析 根据前面已建立的数学模型，可以设计出模拟实验的流程图，如图9 所示。本 实验使用c 语言编写，在p s = 0 5 ，厂= 2 的条件下来分析该模型的性能。 协笺连1 兹_ jf z po l = t 其它口样1 = d 陬据( 18 ) 武计算出石o ( j l 止 。i ，循环、次、是 否i 翻9 模拟实验流程图 本实验的程序包括了9 个函数和1 个主函数。其中s e l e c 0 0 $ os e l e c t u ( ) 两个函数 实现了流程图中的第二个框体的内容，对于某对固定的f 和，通过多次调用这两个函 数可以将( “i 2 ，f ，) 和( j 。，j 2 ，j , - ) 的所有情况都列举出来。甜“1 是稳态下顾客 状态为( ，f 2 ，f r ) 的概率，因此可用迭代算法1 2 3 】循环计算，直到误差小于等于1 0 6 为 止。程序清单详见附录2 。分别就n = l0 ，n = 2 0 ； 1 1 n = 4 0 三种情况做了实验，p 分c 第五章模拟实验及结果分析 别取值为0 0 0 5 ，0 0 1 ，00 2 ，o 1 ，实验结果如图1 0 所示。其中( a ) 为p 。一平均顾客数 的曲线，( b ) 为p c 一平均等待时间的曲线，( c ) 为i i 型一类p c 一平均顾客数比较。 图1 0 ( a ) p c 一平均顾客数曲线图 幽1 0 ( b )p 。一平均等待时间曲线图 图1 0 ( c ) n = 4 0b , 寸i v 类与i i 类模型的平均顾客数比较 ( 1 ) 由图1 0 ( a ) 可以看出，当无顾客的源在某时隙产生1 个顾客的概率p c 增加时， 平均顾客数厨的曲线呈上升趋势。当见o 0 4 时，平均顾客数开始慢慢趋向饱和 第1 i 章模拟实验及结果分析 ( n ：l0 刚趋向于7 ，n ：2 0u 寸趋向j ：1 7 ，= 4 0 时趋向于3 6 ) 。要想减少平均顾 客数露，就要减少p 。当p 。在o _ o 0 4 范围时p c 的减少，能使厨极快减少。因 此p ，的可调范围应耿p ， 0 0 4 。 由图1 0 ( b ) 可见，顾客的平均等待时间也是随着n 的增加而增加，与图1 0 ( a ) 的走势是样的。为了减少平均等待时问，也要使以 0 0 4 。由此州见图1 0 ( a ) 、( b ) 所得结果是致的。 当p ， 0 0 0 5 时，即使变大，平均等待时间也比较小，可见为了减少平均等待 时间，以实现准实时通信，造就的网络环境应该是以 0 0 2 时，也就是负载较重时，顾客排 队规模i l 型i ；l i v 型要小，这解析结果是符合多星l a n 运行机理的。由前面所述， 在l i 型中，顾客第一次请求服务在服务员空闲时发生，顾客产生后不存在无效请求。 而在i v 型中，顾客第一次请求随机发生，顾客产生后存在无效请求，顾客停留时间 变艮，因此顾客规模相对要变大。然而i i 型的这一优点是有代价的，为了判断每一 用户结点至中心结点通道( 即服务员) 是否空闲，必须为每一用户结点安装检测装 置，这是- - f 4 q 0 繁冗的措施。 由图1 0 ( c ) 还可看出，当以 o 0 2 ，也就是负载变轻时，顾客排队规模i i 型- b - - i v 型渐趋一致。说明当n 一样4 l l i j ，随机产生顾客和定时产生顾客的效果渐趋一致。 综合比较结果，应该说i v 型模型比l i 型模型的性能优越。 第六章参考文献 6 参考文献 1 s j k o w s h i k s b a b u g m a u i m a r a n c s r m u r t h y a d i s t r i b u t e dr e a l - t i m em a c p r o t o c o lf o rw d m b a s e dl a n s c o l n p u t e rc o m m u n i c a t i o n s2 4 ( 2 0 0 1 16 5 4 6 6 6 2j a s o np j u e ，b i s w a n a t hm u k h e r j e e m u l t i c o n f i g u r a t i o nm u l t i h o pp r o t o c o l s ：an e w c l a s so fp r o t o c o l sf o rp a c k e t s w i t c h e dw d mo p t i c a ln e t w o r k s 1 e e e a c m t r a n s a c t i o n so nn e t w o r k i n g ，v o l 8 ，n o 5 ，m a y2 0 0 0 ，6 31 - 6 4 2 3 李一武，李乐民，双跳波分复用网络的结构和访问协议电子学报，v 0 1 2 6 ， n o 7 ，j u l y1 9 9 8 ，1 4 9 - 1 5 4 4a b e ld a s y l v a ，r s r i k a n t o p t i m a lw d m s c h e d u l e sf o ro p t i c a ls t a rn e w o r k s i e e e t r a n s a c 1 1 i o n s0 n n e t w o r k i n gv o l 7 ，n o 3 ，j u n el9 9 9 ，4 4 6 4 5 6 5m a r t i nw m c k i n n o n ，g e o r g en r o u s k a s ，h a r r yg p e r r o s q u e u e i u g b a s e da n a l y s i s o fb r o a d c a s to p t i c a ln e t w o r k s m e a s u