（运筹学与控制论专业论文）基于csmaca的无线网络多播协议的排队性能分析.pdf

硕士学伊论文 摘要 本文研究内容包括两个方面：无线局域网内采用基于冲突避免的载波多址协 议( c s m a c a ) 的两种多播协议的时延和吞吐量；蓝牙微微网内多播协议的时延 性能。目前，对于多播协议的研究以改进协议的功能为主，缺乏对协议的各种性 能进行完整的数学分析。本文主要目标是分别在无线局域网和蓝牙微微网环境下， 针对多播协议建立带休假的排队模型，求解系统时延和吞吐量表达式，并利用 m a t l a b 仿真分析系统参数对时延、吞吐量的影响。 本文基于排队理论对两种无线网络的多播协议时延性能等指标做了深入的模 型研究，所做工作和创新研究集中在第3 、4 章。第3 章的创新点概括如下：首先， 分析无线局域网内多址接入协议，建立了带休假的排队模型来描述节点的传输过 程。其次，分别分析了两种多播协议节点休假期的开始和结束，推导出休假期的 一阶矩、二阶矩和多播帧重传k 次传输成功的概率及时延，进而求出成功传输一个 多播帧的时延均值和吞吐量的表达式。最后，通过m a t l a b 仿真，对两种协议的 时延、吞吐量进行了比较，得到新自动请求重传( a r q ) 协议优于b m m m 协仪， 并得到系统参数对两种协议性能的影响。第4 章的创新内容概括如下：首先，分析 蓝牙微微网的通信原理，建立了一个两服务窗h 串联的排队网络。其次，分别对 蓝牙微微网内两种传输机制建模分析。采用带优先级的分区多播机制时，第一阶 段的发送可以归纳为一个排队队列，建立带休假的强占优先制的排队模型；第二 阶段的传输遵从先到先服务，没有排队队列。推导出此机制下从设备的等待时延、 休假时延，从而得到排队系统平均服务时延表达式。当微微网采用差额轮询机制 ( d r r ) 通信时，将第一阶段两节点的发送归纳为一个队列，用纯限量服务休假 模型近似描述，推导出每类数据包的平均等待时延，进而求得系统的平均服务时 延。最后，m a t l a b 仿真证明了带优先级的分区多播机制优于d r r 机制，且得到 系统参数对两种机制性能的影响。 关键词：多播协议；b m m m 协议；新a r q 协议；带优先级的分区机制；d r r 轮询机制；带休假的排队模型；平均服务时延；归化饱和吞吐量；优先级 基于c s m a c a 的无线网络多播协议的排队性能分析 a b s t r a c t t h i st h e s i si n c l u d e st w oa s p e c t s ：t h ed e l a yp e r f o r m a n c ea n dt h r o u g h p u to ft w o m u l t i c a s t i n gp r o t o c o l sb a s e do nc s m a c ai nw i r e l e s sl a n ；t h ed e l a yp e r f o r m a n c eo f m u l t i c a s t i n gp r o t o c o l i nt h ep i c on e to fb l u e t o o t hn e t w o r k 。t h er e s e a r c h e so n m u l t i c a s t i n gp r o t o c o lm e a nt oi m p r o v ei t s f u n c t i o n sn o w a d a y s b u tt h e ya l ll a c k e d d e t a i l e dm a t h e m a t i c a la n a l y s i sw i t hi t sv a r i o u sp e r f o r m a n c e t h i st h e s i sa i m st ob u i l d q u e u i n gm o d e l sw i t hv a c a t i o nf o rm u l t i c a s t i n gp r o t o c o l su n d e rt h ee n v i r o n m e n to f w i r e l e s sl a na n dt h ep i c on e to fb l u e t o o t hn e t w o r kr e s p e c t i v e l y t h e n ，w ed e r i v e dt h e d e l a y a n d t h r o u g h p u t m a t h e m a t i c a l e x p r e s s i o n o f m u l t i c a s t i n gp r o t o c o l s t h e m u l t i c a s t i n gp r o t o c o l sw e r es i m u l a t e dw i t hm a t l a bi n t h ee n d t h ei n f l u e n c eo f p a r a m e t e r so nd e l a ya n dt h r o u g h p u tw a sa l s oo b t a i n e d i nt h i st h e s i s ，t h ed e l a yp e r f o r m a n c ea n do t h e ri n d i c a t o r so ft h em u l t i c a s t i n g p r o t o c o l si nt w ow i r e l e s sn e t w o r k sw e r es t u d i e dd e e p l yb ym o d e l i n gc o n t a c t e dw i t h q u e u i n gt h e o r y t h em a i nw o r k sa n di n n o v a t i o n so ft h i sd i s s e r t a t i o na r ec o n c e n t r a t e d i nt h ec h a p t e r3 r da n dc h a p t e r4 t h t h ei n n o v a t i o n sc o n t e n to fc h a p t e r3 r dg e n e r a l i z e d a sf o l l o w s ：f i r s t l y , t h ep a p e ra n a l y z e dt h em u l t i p l ea c c e s sp r o t o c o li nw i r e l e s sl a n ； w ec a nm o d e lt h ed a t at r a n s f e rp r o c e s so fo n en o d ea saq u e u i n gs y s t e mw i t hv a c a t i o n s e c o n d l y , t h ep a p e ra n a l y z e dt h eb e g i n n i n ga n de n do fv a c a t i o np e r i o do f t w o m u l t i c a s t i n gp r o t o c o l si nw i r e l e s sl a nr e s p e c t i v e l y , g o ti t s f i r s to r d e rm o m e n ta n d s e c o n do r d e rm o m e n t ，a l s os o l v e dt h ep r o b a b i l i t yo fm u l t i c a s tf l a m e s kt i m e s r e t r a n s m i s s i o n t h e n ，t h em e a no ft h em u l t i c a s t i n gf r a m e sd e l a ya n dt h r o u g h p u tw e r e d e r i v e dw h e ni tw a ss u c c e s s f u l l ys e r v e d l a s t l y , t h et w om u l t i c a s t i n gp r o t o c o l s d e l a y a n dt h r o u g h p u tw e r es i m u l a t e dw i t hm a t l a b w ec o m p a r e dt h er e s u l t so fs i m u l a t i o n ； f i n dt h a tt h en e wa r qs c h e m eo v e r m a t c h e st h eb m m mp r o t o c 0 1 t h ei n n o v a t i o n s c o n t e n to fc h a p t e r4 t hg e n e r a l i z e da sf o l l o w s ：f i r s to fa l l ，b ya n a l y z i n g t h e c o m m u n i c a t i o np r i n c i p l eo fp i c on e to fb l u e t o o t hn e t w o r k ，w em o d e l e dt h ep a c k e t s t r a n s f e rp r o c e s sa saq u e u i n gn e t w o r km o d e lw i t ht w os e r i e s w o u n ds e r v i c ew i n d o w s n e x t ，t h ep a p e rm a d em o d e l so ft w o s c h e m e si np i c on e tr e s p e c t i v e l y w h e nt h ep i c o n e ta d o p tm u l t i c a s tp a r t i t i o n i n ga n dp r i o r i t i z a t i o ns c h e m e ，t h et r a n s f o r m a t i o n si nt h e f i r s ts t a g ec a nb em o d e l e da so n eq u e u e ；t h es e c o n dt r a n s f o r m a t i o ns t a g ef o l l o wt h e f i r s tc o m ef i r s ts e r v i c ep r i n c i p l e ，t h e r ei sn oq u e u e t h es l a v e rn o d e sv a c a t i o n sw e r e a n a l y z e d ，a n dt h e nd e r i v et h ew a i t i n gd e l a y , v a c a t i o nt i m e f u r t h e r m o r e ，w ed e r i v e d i l 硕士学位论文 t h ed e l a ya n dt h r o u g h p u tm a t h e m a t i c a le x p r e s s i o no ft h es y s t e mu n d e rt h en e w m u l t i c a s tp a r t i t i o n e da n dp r i o r i t i z e dp r o t o c 0 1 w h e nt h ep i c on e tu s ed i f f e r e n c er o u n d r o b i n ( d r r ) p o l l i n gm e c h a n i s m t oc o m m u n i c a t e ，t h et r a n s f o r m a t i o n so ft w on o d e si n t h ef i r s ts t a g ew e r ei n d u c t e da so n eq u e u e ap u r el i m i t e d s e r v i c em o d e lw i t hm u l t i p l e v a c a t i o n sc a nd e s c r i b et h et r a n s f e rs y s t e ma ss u i n gd r ra n dt h e r e b yd e r i v a t et h e d i f f e r e n tp a c k e t s m e a nw a i t i n gt i m e t h e n ，w ea l s od e r i v e dt h ed e l a ya n dt h r o u g h p u t m a t h e m a t i c a le x p r e s s i o no fp a c k e tu n d e rt h ed r rm e c h a n i s m a tl a s t ，t h et w o s c h e m e s d e l a ya n dt h r o u g h p u tw e r es i m u l a t e dw i t hm a t l a b w ec o m p a r e dt h er e s u l t o fs i m u l a t i o n ；f i n dt h a tt h en e ws c h e m e s p e r f o r m a n c eo v e r m a t c h e st h ed r rs c h e m e s t h ei n f l u e n c eo fs y s t e mp a r a m e t e r sw a sa l s or e c e i v e d k e yw o r d s ：m u l t i c a s t i n gp r o t o c o l s ；b m m mp r o t o c o l ；n e wa r qp r o t o c o l ；p r o t o c o l s b a s e do nm u l t i c a s tp a r t i t i o n i n ga n dp r i o r i t i z a t i o n ；d r r ；q u e u i n gm o d e l w i t hv o c a t i o n ；m e a np a c k e ts e r v i c ed e l a y ；u n i t a r ys a t u r a t i o nt h r o u g h p u t ； p r i o r i t y i i i 基于c s 眦a 的无线网络多播协议的排队性能分析 插图索引 图1 1c s m a 协议基本操作图3 图1 2 四次握手机制示意图4 图2 1 多节点共用信道的系统传输过程一1 0 图2 2 第f 个数据帧到达时的系统状态1 1 图2 3 节点带休假的m g 1 队列的剩余服务时延1 1 图3 1 发端首次发送数据帧成功的情形一1 8 图3 2 收端个数对竞争信道平均次数的影响1 9 图3 3 数据帧的格式一2 1 图3 4a c k 位图的结构图一2 2 图3 5 两种系统时延的比较”2 4 图3 6 两种系统最大吞吐量的比较”2 4 图3 7 不同退避时间下收端个数对系统时延的影响2 4 图3 8 不同数据帧到达率下收端个数对系统时延的影响2 4 图4 1 蓝牙网络拓扑结构一2 6 图4 2 主设备与从设备间以t d d 方式建立的物理信道2 7 图4 3 微微网分区前2 9 图4 4 微微网分区后2 9 图4 5 采用d r r 轮询机制主设备的轮询模式3 5 图4 6 多播组节点个数对两种机制时延的影响图一3 7 图4 7 链路正确率对两种机制时延的影响一3 7 图4 8 新机制在不同数据到达率下p 下的系统时延3 8 图4 9d r r 轮询机制在不同数据到达率下p 下的系统时延一3 8 i v 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：躁 丽君 日期：2 啪年参月午日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名：路丽君 别磁孙绷 日期：功加年 日期：沙，晦! 易月牛日 月7 日 硕士学位论文 第1 章绪论 随着信息技术的飞速发展，人们对网络通信的需求也随之不断提高，希望打 破不同的地域或客观条件的制约，能够“实现任何人( w h o e v e r ) 在任何时候 ( w h e n e v e r ) 的任何地方( w h e r e v e r ) 与任何人( w h o m e v e r ) 进行任何方式( w h a t e v e r ) 的通信 的目标。作为个人通信的一个重要组成部分，无线局域网已经掀起了移 动计算的新浪潮，在现实及未来的社会生活中得到广泛的应用。无线局域网 ( w i r e l e s sl o c a la r e an e t w o r k s ，w l a n ) 广义上是指在局部区域内以无线媒体或介 质进行通信的无线网络，是一种能在几十米到几公里范围内支持较高数据速率( 如 2 m b s 以上) 的无线网络，可以采用微蜂网( m i c r oc e l l ) 、微微蜂网( p i c oc e l l ) 结 构，也可以采用非蜂窝( 如a dh o c ) 结构。目前无线局域网领域的两个典型标准 是i e e e 8 0 2 1 1 系列标准和h i p e rl a n 系列标准。 无线局域网采用的传输媒体或介质分为射频无线电波和光波两类，它们代替 了传统的缆线进行信息传输，可以作为传统网络的延伸、补充或替代。比较之下， 无线局域网具有以下许多优点【1 】： 1 ) 移动性。“无线 就意味着可能移动，通信范围不再受环境条件的限制， 拓宽了网络传输的地理范围。 2 ) 灵活性。安装容易，组网灵活，无线局域网可以将网络延伸到线缆无法连 接的地方，并可以方便地增减、移动和修改设备。 3 ) 可伸缩性。在适当的位置放置或添加接入点( a c c e s sp o i n t ，a p ) 或扩展点 ( e x t e n dp o i n t ，e p ) 就可以满足扩展组网的需要。 4 ) 经济性。无线局域网不仅可以节省缆线及其附件的费用还可以节省人员、 节省时间。 然而，无线局域网并非完美无瑕，也面临许多问题需要解决。 1 ) 可靠性。无线局域网采用无线信道进行通信，而无线信道存在各种各样干 扰和噪声，引起信号的衰落与误码，是不可靠的信道。由于无线传输的特殊性， 还可能产生“隐藏终端 、“暴露终端”和“插入终端等现象，影响系统可靠性。 2 ) 带宽与系统容量。由于频率资源有限，无线局域网的信道带宽远小于有线 网的带宽。由于无线信道数有限，即使可以复用，无线局域网的系统容量通常也 要比有线网的容量小。 3 ) 干扰。外界干扰可对无线信道和无线局域网设备形成干扰，无线局域网系 统内部也会形成自干扰；同时，无线局域网系统还会干扰其他无线系统。 4 ) 节能管理。由于无线局域网的终端设备是便携设备，如笔记本电脑、p d a 基于c s m a c a 的无线网络多播协议的排队性能分析 ( 个人数字助理) 等，为了节省电池消耗，延长设备使用时间，网络应有节能管 理功能，当某站不处于数据收发状态时，应使收发机处于休眠状态，当要收发数 据时，再激发收发信机。 本文讨论的局域网内的多节点参与的多播协议，采用带有冲突避免的载波侦听 多址协议( c s m a 7 c a ) 和四次握手机制，能有效缓解干扰和“隐藏终端造成的 碰撞问题。 1 1 无线局域网m a g 协议的原理 在多点之间的多个用户进行相互通信时，需采用多点( 址) 接入( m u l t i p l e a c c e s s ) 技术。这种技术不需要使用复用器和集中器，而是通过共享一个物理链 路( 信道) 将所有用户连接起来。它涉及多址信道的分割、接入方式、分配策略 和控制机制等多方面内容。多址接入技术的一个核心问题是：对于一个共享信道， 当信道的使用产生竞争时，如何采用有效的协调机制或服务准则来分配信道的使 用权。这就是媒体( 信道) 访问控制m a c ( m e d i u ma c c e s sc o n t r 0 1 ) 技术，它定 义了分配节点访问媒体的规则。 严格来讲，多址接入与m a c 不完全相同，但在计算机通信中，一般用m a c 协议来描述和实施各用户的多址接入，通常把这两种概念视为同一概念。m a c 协 议的分析常用多址接入协议的排队模型。 m a c 协议分为以下三类。 1 ) 固定分配类。把共享的一条信道分割成若干相互独立的子信道，每个子信 道又分配给一个或多个用户专用。四种基本的固定分配多址技术是频分多址 ( f d m a ) 、时分多址( t d m a ) 、码分多j 址( c d m a ) 、和空分多j 址( s d m a ) 引。 2 ) 随机分配或竞争类。随机竞争类m a c 协议使用的传输媒体一般是广播式 信道，连接在这条信道上的终端都可以向信道发送广播信息。如果终端需要发送 信息，它以某种方式竞争信道的使用权，一旦得到使用权就以某种规则发送( 可 以立即发送，也可以退避后发送) 。这类协议有c s m a 系列、a l o h a 系列等。 3 ) 按需分配类。网络按某种循环顺序询问每个终端是否有数据发送，如果有 则立即发送，否则网络立即转向询问下一个终端。 评价m a c 协议的性能或设计m a c 协议需要考虑的技术要求主要有吞吐率、 延迟、公平性和稳定性等。理想的m a c 协议应该具有尽可能小的时延，尽可能高 的吞吐率。 面向数据的随机竞争m a c 协议分为两大类g 一类是基于a l o h a 的无线m a c 协议，协议中各用户端不需经过协调各自发送自己的竞争分组：另一类是基于载 波侦听( c s m a ) 的无线随机m a c 协议，协议中各用户终端在发送自己的分组之 前需要侦听信道，前者多用于广域网，后者常用于局域网。 2 硕士学位论文 12 ( 3 s m a c a 协议的工作原理 在局域网中，每个节点都能够检测( 侦听) 到信道上有无分组在传输。如果 f 一个节点有分组要传输它首先检测信道是否空闲，如果信道有其他分组在传 输，则该节点可以等待信道空闲( 也称退避) 后再传输，这样可以减少相互之间 碰撞，提高信道的利用率。这是载波侦听型多址( c s m a ) 协议的基本出发点。 c s m a 协议的基本操作如图1 1 所示。用户l 连续两次先侦听信道( 空闲) 后 发送，用户2 在用户1 第二次发送时侦听信道( 发现忙) ，采用一定的退避算法延 迟后再处理。 月p 1 p 27 _ _ 图11c s m a 协议基本操作图 c s m a 协议大大减少了数据分组碰撞的概率。但由于传播时延的存在掩盖了 正在进行的传送，因此并不能完全消除碰撞。若两个用户同时侦听到信道忙，他 们退避后的发送时问又有重叠这同样会造成冲突。由于发射信号的泄漏和隐藏 终端问题的存在，在无线系统中，一般采用带有冲突避免( c o l l i s i o na v o i d a n c e ) 的c s m a 机制【”。本文分析的局域网多播协议就采用c s m a c a 机制。 在c s m a c a 中，每个工作站都会在传输之前检测它附近的介质如果发现 附近的介质有载波在传输，那么这个工作站就会延迟传输。载波侦听是靠检测发 送者四周范围内的信号强弱来避免碰撞的，但是一般都是两个或两个以上的相互 干扰的信号在接收者处相汇，因此碰撞一般发生耷接收者处而不是在发送者处。 为了解决隐藏终端问题，c s m c a 机制通过阻止碰撞来提高协议性能有两 种形式 1 ) 带带外信令的c a 协议。为了解决无线局域网内隐藏终端问题，这个晦议 除了数据发射信道( d c ) 外，在d c 信道发射数据期间还用一个b t c 信道发射一 个信令( 忙音) 来告诉其他站点数据信道正在发射数据( d c 信道忙) 。 2 ) 带带内控制信息的c a 协议。这里的带内控制信息指的是在同一无线信道 上传输的控制握手信息。这种控制握手可以有两次、三次、四次，甚至更多。 本文研究的无线局域网多播协议采用四次握手机制。下面介绍四次握手机制。 如图l2 所示，四次握手机制包括r t s c t s d a t a a c k 四个过程，发送者在发送 基于c s m a c a 的无线网络多播协议的排队性能分析 数据帧之前，首先发送一个r t s 帧预约信道，接收者发回一个c t s 帧，之后开始 进行数据帧的发送和a c k 确认。 源站 目的站 其他站 u 婴小司眄习 时而 圉闰圆 c t sa c k s i r s l 每胃 时而 n a v ( r t s ) n a v ( c t s ) 时 n a v ( 数据帧) n a v ：网络分配向量 图1 2 四次握手机制示意图 如果发送者没有接收到返回的a c k ，则会认为之前的传输没有成功，会重新 传输；但是返回的a c k 丢失了，之前的r t s c t s 传输非常成功，则重新发送的 r t s 到达接收者后，接收者只会重新发送a c k 而不是c t s ，且退避时间量并不会 增加；如果发送了r t s 后，在接收超时之前都没有接收到c t s 或a c k ，那么退 避时间量就会增加，当接收到a c k 后，退避时间量就会减少。 1 3 无线通信系统多点传输协议的研究现状 目前对于无线通信系统的多节点参与通信的多播协议的研究主要表现在两个 方面： 1 多播信息的路由选择和安全 在无线网络中，当多个信源共用一条无线链路时，除了考虑多信源的冲突避 免问题，还需考虑多播信息路由的选择。文献【7 】在无线移动自组网( a dh o e ) 中 提出一种全新的基于路由选择的多播协议，解决了两个问题：路径的可用性和更 高的电池使用寿命( 节能性) 。协议构建了一个网络来连接小组成员，提供稳定的 路径。并且比较了所提协议与按需多播路由协议( o d m r p ) 、自适应需求多播路由 协议( a d m r ) 的性能。文献【8 】提出一种多频无线电分集系统，用路径多样性来改进 无线局域网的丢失重传。此系统协调多个无线接收端，一定程度上解决了由路径 传输的衰落引起的数据帧丢失恢复问题。这种协议结合了两种技术：一方面采用 复合帧的形式，结合了帧可能出现的错误和帧的多个副本，从而能恢复帧而不需 重传；一种是在数据链路层上采用低开销的重传机制。文献【9 1 提出了光虚拟专用 网里一种基于优先级的最小干扰的多播路由选择算法，结合波长变换技术，选择 一条不妨碍多播服务的路径，降低了阻断概率，增加了波长利用率。文献 1 0 1 提出 一种对多视频信道支持广播的机制，只有被授权的用户拥有信道的使用权。机制 有效地保护了信息安全，而且当一个视频通道在最后一公里不能可视时，传输暂 4 硕士学位论文 时停止，电缆可用于其他服务，如标准互联网接入等。文献【1 1 】提出一种跨层设计， 提供高能效的平衡的密钥分配策略，解决了a dh o c 网内多播信息的安全问题。同 时，在齐次和非齐次环境下，得到一种新算法，获得了计算的复杂性。最后，仿 真证明在三个不同环境下，此跨层设计有利于无线网络的安全。 2 多播协议的改进方案和系统容量、时延、吞吐量的分析 著名的i e e e 8 0 2 1 1 无线局域网标准对单点传输包括了数据帧的冲突避免和丢 失重传这两种功能，但对多点传输没有涉及。而多点传输是无线局域网内一种重 要的服务。国际上对于多播协议的研究，致力于改进传输协议。文献【1 2 1 研究了 a dh o c 网的多播机制，信源通过多跳传播的方式将统一信息或服务发送给一组收 端。用纳什均衡法使得各用户只能按一定规则选择策略来增加收益。文献【1 3 】将无 线信道建模为i p 层上的删除信道，当有一个用户时，设计一个结合了前向纠错编 码的混合自动重传请求算法；当有多个用户时，将多播的实时视频信息设计成最 大成本函数，求最优化算法。所提出的模型从理论上推导分析了算法，并且通过 实验证明此算法优于已有方法。文献【1 4 】提出一种无线信道包错误率分级模型，不 仅解决了无线信道内存在的，实时多播信息的不可靠和缺乏链路层上的错误控制 问题，而且能够整合比率控制策略。仿真结果证明了这种模型优于简单的吉尔伯 特信道模型。 在无线通信网多播信息的传输过程中，还存在不同类型的信息具有不同优先 级的情况。不同优先级的数据包同时发送，增加了系统的复杂度，系统各种性能 的提高面临考验。各国研究者在改进基于不同优先级信息的多播协议方面也做出 积极贡献。文献【1 5 】提出一种光纤网络中时延敏感的多播机制，它遵循先到先服务 规则，考虑不同优先级的多播队列。仿真结果揭示了这一多播协议能够有效地解 决收端冲突和支持优先级通信。文献 1 6 1 分析了一种基于优先级的无源光纤网中多 播调度机制。仿真分析了数据包的时延、吞吐量、数据包丢失率等系统性能指标。 文献 1 7 1 提出一种异步传输网络( a t m ) 的输入访问机制，使每个输入端1 2 1 的多播 和单点传输数据分开排队。多播队列按较高优先级通过且两种类型的队列在每轮 循环询问中公平服务。最后，用一种循环优先级简化模型近似地分析了机制，并 仿真证明了机制比已有机制具有较高吞吐量和较低时延、数据包丢失率。 无线局域网中，媒体访问控制层( m a c ) 数据的可靠传输依赖于两个功能： 数据帧的冲突避免和丢失重传。文献【1 8 研究了无线网络中的m a c 层多播协议的 应用，通过实验得到了采用8 0 2 1 1 协议的无线网络在数据速率为2 m b p s 时达到最 大吞吐量，得到m a c 层多播只能在附加高层机制用于缓和m a c 层帧丢失时采用。 还分析了避免碰撞的随机退避在隐藏终端环境中的运用。为了解决无线局域网内 流媒体难以克服的带宽变化和数据丢失的问题，文献1 1 9 】比较了几种误差控制策 略：媒体访问控制层前向纠错、访问控制层重传、应用层前向纠错，来实现可靠 5 基于c s m a c a 的无线网络多播协议的排队性能分析 通信，并且评估了不同多径信道条件下系统的性能。文献【2 0 】分析了四种采取请求 发送允许发送( r t s c t s ) 短帧握手机制的m a c 协议，并通过仿真证明了提出 的b m m m 协议( b a t c hm o d em u l t i c a s tm a cp r o t o c 0 1 ) 具有较好的吞吐量性能。 文献【2 1 】提出了一种新的a r q 传输机制，改进了数据帧的构造和构造一种虚拟的 肯定应答( a c k ) 位图，并利用n s 2 软件仿真对比了新a r q 机制与b m m m 协议 的节点吞吐量、重传比率，仿真结果表明新机制比b m m m 协议有更优的系统性能。 文献 2 2 1 分析了无线局域网内网络总负载对不同系统中广播音频信息的碰撞概率、 系统吞吐量的影响。 以上文献的研究，多是从改进协议功能的角度出发，改善多播协议的各种性 能。利用专业的通信软件仿真验证了所提改善方案的优越性。但是都缺乏对协议 性能进行数学分析，从理论上解释协议性能因何提高，如何提高。文献【1 4 】虽已建 立排队模型，却没有从排队论的角度进行排队性能分析。这正是本论文的研究方 向。 1 4 休假排队系统的的研究现状 1 、休假排队论概述 经典排队论假定服务台在任何时候都可用于接待顾客，休假排队泛指服务台 在某些时候不能被顾客利用的排队系统。导致服务暂时中断的理由可以有多种多 样的解释，而暂时不能用于接待顾客的那些时间统称为休假。下面是一些诱发休 假排队研究的典型例子【4 1 。 1 ) ( 交通堵塞) 在公路交通问题中，通常把车辆通过某待定路段看成顾客服 务。由交通事故或其他原因造成的交通堵塞可视为服务员休假。在无线通信网络 多址访问协议中，多个节点随机竞争接入信道。当只有一个节点尝试发送时，帧 会被成功发送。当多个节点尝试发送时，会发生冲突，节点将随机退避。节点的 竞争信道和退避过程可视为节点休假期。 2 ) ( 轮询服务) 一个服务员依某种规则轮流地为若干队列顾客服务。在通信 网络中，无论是有线网络还是无线网络，由于信道不能在同一时刻为所有队列利 用，需要采用某种规则轮流服务所有队列。当轮询排队中某待定队列时，服务员 接待其他队列及在诸队列间转移的时间，对该队列顾客相当于服务员休假。 3 ) ( 优先权) 具有不同优先权的多类顾客的排队系统在经典排队论中已得到 深入研究。如果把高优先权顾客造成的低优先权顾客的服务中断( 强占的或非强 占的) 视为对低优先权顾客的服务员休假，优先权排队也可纳入休假排队的框架 之中。 4 ) ( 辅助工作) 在负荷较低的排队系统中，为了有效利用空闲时间，可设置 某种辅助工作。一旦系统内无顾客，服务员立刻开始一项辅助工作。适当设置辅 硕士学位论文 助工作，可较好地满足相继到达的顾客需求，又可充分利用空闲时间，增加系统 收益。 5 ) ( 机器故障) 假定服务台在运行过程中可能发生损坏或需要补充能量，而 故障维修或能量补充时，必须中断正在进行的服务，这些中断时间可视为服务员 休假。 2 、休假排队论研究的内容和主要指标 经典排队系统由到达过程、服务机制、排队规则三部分组成，休假排队系统 只是在此基础上再增加一个休假策略。针对不同应用背景，可以引入各种各样的 休假行为。一个完整的休假策略，既包括休假开始和结束的规则，也包括休假时 间的分布。按休假开始规则可将休假策略分成两类：空竭服务和非空竭服务。前 者服务一旦开始进行，就要持续工作到系统中无顾客，休假只能在系统空闲时开 始。后者泛指那些在系统中有顾客时也可以开始休假的情况。 描述休假排队论系统的主要数量指标有以下几个【5 1 。 1 ) 队长与等待队长。队长指在系统中的顾客数( 包括正在接受服务的顾客) ， 等待队长指系统中排队等待的顾客数，他们都是随机变量，应确定它们的分布。 2 ) 顾客在系统中的等待时间与逗留时间。等待时间指从顾客进入系统时刻起 到开始接受服务时刻止这段时间，逗留时间指顾客在系统中的等待时间与服务时 间之和。若假定到达与服务是相互独立的，等待时间与服务时间相互独立。 3 ) 系统的忙期与休假期。忙期是指系统从某时刻开始服务起到服务完成止这 段时间( 服务遵循某种规则，或服务几个顾客或服务某段时间) ，休假期指在每 个忙期后，服务员需要休假( 休假对应于服务员如通信链路，可指需要传输其他 节点的预约信息或数据信息) 。 4 ) 输出过程。指接受服务完毕的顾客相继离开系统的过程，主要指标是相继 离去的间隔时间和在一段时间内离去顾客的数目，这些指标从一个侧面反映了系 统的工作效率。 排队论主要研究描述系统的上述指标的概率特性，包括它们的瞬态性质和稳 态性质。排队系统的性态问题是排队论研究的核心，是排队系统统计推断和最优 化问题的基础，从应用方面考虑，稳态指标的性质尤其重要【6 1 。 3 、休假排队论的研究发展过程及研究现状 作为随机运筹学中一个有独立特色的方向和经典排队论的新发展，休假排队 研究是从2 0 世纪7 0 年代才开始的。l e v y 与y e c h i a l i ( 1 9 7 5 ) 从有效利用排队系 统闲期的观点出发，首先研究m g 1 型休假排队系统，并引入了“休假”和“休 假策略 等术语。8 0 年代，研究的重点是休假m g 1 型排队系统。c o o p e r ( 1 9 7 0 ) ， c o u r t o i s ( 1 9 8 0 ) ，f u h r m a n n ( 1 9 8 4 ) ，f u h r m a n n 与c o u r t o i s ( 1 9 8 5 ) ，h a r r i s 与m a r c h a l ( 1 9 8 8 ) ，k e i l s o n 与r a m a s w a r n y ( 1 9 8 8 ) ，l e v y 与k l e i n r o c k ( 1 9 8 6 ) 7 基于c s m a c a 的无线网络多播协议的排队性能分析 等众多工作相继讨论了各种休假策略及服务规则的m g 1 型排队系统【4 1 。初步形 成了以随机分解为核心的休假排队理论框架。 以触发休假开始为基础的休假规则有空竭服务( e x h a u s t i v es e r v i c e ) 规则、闸门 服务( g a t e ds e r v i c e ) 规则、限量服务( 1 i m i t e ds e r v i c e ) 规则、伯努利( b e r n o u l l i ) 休假 规则、一般非空竭服务规则以及以休假终止机制为基础的休假规则的有多重休假 ( m u l t i p l ev a c a t i o n ) 规则【2 3 2 4 】、单重休假( s i n g l ev a c a t i o n ) 规则、多级适应性休假【2 5 】 ( a d a p t i v em u l t i s t a g ev a c a t i o n ) 、一般休假( g e n e r a lv a c a t i o nr u l e s ) 规则。田乃硕等首 先把矩阵集合解方法引入休假排队研究，推进了g i m 1 型休假排队系统和多服务 台休假排队系统的研究。田乃硕等建立了随机分解理论，研究了多级适应性休假 系统及离散时间休假排队。最近的工作侧重于研究了m m 1 n 考虑负顾客到达的、 止步的成批到达的、带有止步和中途退出等的多重和单重工作休假排队模型。利 用马尔科夫过程理论和矩阵解法求出了稳态概率的矩阵解，并得到了系统的平均 队长、平均等待队长以及顾客的消失概率等性能指标【2 6 3 1 1 。朱翼隽等则侧重运用 全概率分解，更新过程理论和l a p l a c e 。s t i e l t j e s 变换，研究休假排队网络，求得了模 型的稳态分布和循环时间1 3 2 引】。 当前带休假排队论的研究热点主要集中在排队网络、矩阵分析法、排队性能 数值计算方法等方面。另外，结合带休假排队理论分析现实生活中的排队实例， 亦是目前研究的热点。黎锁平等将休假排队理论用于无线通信协议排队性能的研 究，既为工程上改进通信协议提供了理论支持，也推动了带休假排队理论的应用 与发展【3 5 3 7 1 。 1 5 本论文的研究意义和内容 本课题来自甘肃省自然科学基金项目及教育部“春晖计划 基金项目。本论 文的研究内容是基于排队论对无线局域网内多节点参与通信，基于数据链路层差 错控制技术自动请求重传( a r q ) 的多播协议以及蓝牙微微网内多播协议，进行传输 原理研究以及排队时延性能建模分析，力图找到在较低实现复杂情况下，提高无 线局域网和更小的蓝牙网内多点传输系统的通信吞吐量和降低系统传输时延的方 法。 本论文的结构安排如下： 第l 章绪论，主要介绍无线局域网多址接入协议采用的冲突避免机制和 m a c 层协议以及带休假的排队理论发展和研究现状。最后说明本论 文的研究意义和内容。 第2 章对多址接入理论的原理进行介绍与分析，建立带休假的m g i 扫 队模 型。介绍带休假的纯限量服务排队系统的研究方法，为以后的模型研 究奠定理论基础。 硕七学位论文 第3 章 分析文献 2 0 2 1 提出的无线局域网内带冲突避免的多址接入技术 下多播协议的传输原理，分别建立比较准确的多播协议时延和吞吐量 模型，进行时延和吞吐量的性能分析和比较。并探索系统参数对两种 多播协议的影响，对结果进行比较，得到时延和吞吐量最优的协议。 第4 章 缩小无线局域网的通信范围，分析