（通信与信息系统专业论文）cdma系统中多点接入技术研究.pdf

华中科技大学硕士学位论文 = = = = = = = = = = = = = = ；= = = = = = ；= = = = = = ；= = ；： 摘要 在高速无线移动i p 通信系统中，多点接入控制协议是支持多个终端设备共享无 线信道通信所不可缺少的。在目前的移动通信中，由于传输速率低，提供的业务少 、 ( 主要是话音业务) ，对无线资源使用效率自谣求不高。在高速无线i p 移动通信系 统中，传输速率大为提高，持续时间短、具有寒发 电壮的业务牦占主导地位，因此 用有效的多点接入技术控制移动终端f 使其合理地占用有限的网络资源是关键技术 之一。 、 、( 从当前多点接入技术发展角度来看，现有的多点接入技术已经可以很好地解决 有线网络( 如以太网) 上的接入问题，但是对于无线网络并没有一个很理想的解决 方案，其最大的难点主要在于无线链路上传输数据比有线网络上的具有更大的时延 r - 和更高误比特率。r 本文对现有主要的多点接入技术进行了介绍，讨论了多点接入协议设计中的技 术要点，并提出了一种适用于c d m a 接入网络中的多点接入协议，最后，建立了一 个仿真平台对协议算法进行了验证。从仿真结果可以知，该协议较好地解决了 c d m a 网络中多点接入的协议开销、接入时延和分配公平性等方面的问题。 关键词：多点接入控制码分多址 l 华中科技大学硕士学位论文 a b s t r a c t i n1 1 i g hs p e e dw i r e l e s sm o b i l ei pc o m m u n i c a t i o ns y s t e m m u l t i p l ea c c e s sc o n t r o l t e c h n o l o g yi sn e c e s s a r yt os u p p o r tm u l t i p l em o b i l et e r m i n a lt oc o m m u n i c a t i n gi ns h a r e d w i r e l e s sc h a n n e l i nc u r r e n tm o b i l ec o m m u n i c a t i o n ，t h e r ei sn o tm u c h h i g hr e q u i r e m e n t f o rt h ee f f i c i e n c yo fu t i l i z a t i o no fw i r e l e s sr e s o u r c eb e c a u s eo fa b s e n c eo f a p p l i c a t i o n s ， h o w e v e r ，i nh i g hs p e e dw i r e l e s sm o b i l ei pc o m m u n i c a t i o ns y s t e m ，t r a n s m i s s i o nr a t eh a s b e e ne n h a n c e dg r e a t l ya n da p p l i c a t i o n s 、 ，i mb u r s tc h a r a c t e rw o u l db ei nt h el e a d i n g p o s i t i o n s o ，o n eo f t h ek e yt e c h n o l o g i e si sm u l t i p l ea c c e s sc o n t r o lf o rh i g h l ye f f i c i e n t u t i l i z a t i o no fl i m i t e dn e t w o r kr e s o u r c e f r o mt h ev i e wo fd e v e l o p e m e n to fm u l t i p l ea c c e s sc o n t r o lt e c h n o l o g y , c u r r e n t m u l t i p l ea c c e s sc o n t r o lt e c h n o l o g i e s h a dr e s l o v e dt h ep r o b l e m so fa c c e s si nw i r en e t w o r k ， b u tt h e r ei sn o ta ni d e a lc o r r e s p o n d i n gw a yi nw i r e l e s sn e t w o r k t h em a i nh a r dp o i n tl i e s i nt h eh i g ht r a n s m i s s i o nd e l a ya n d h i g hb i t e r r o rr a t i o t h i sp a p e ri n t r o d u c e st h em a i nm u l t i p l ea c c e s sc o n t r o lt e c h n o l o g i e s ，d i s c u s s e st h e k e pp o i n t so fd e s i g n i n gm u l t i p l ea c c e s sp r o t o c o l sa n ds u g g e s tam u l t i p l ea c c e s sp r o t o c o l f o rc d m an e t w o r k a tl a s t ，as i m u l a t i o np l a t f o r mi se s t a b l i s h e dt ov e r i f yt h ep r o t o c 0 1 t h es i m u l a t i o nr e s u l t sv a l i d a t et h a tt h i sn e wp r o t o c o lc o u l dr e s o l v et h ep r o b l e m so f a c c e s sd e l a y , b a n d w i d t h o c c u p i e db yp r o t o c o l a n df a i m e s so f a l l o c a t i o n k e yw o r d s ：m u l t i p l e a c c e s sc o n t r o lc d m a i i 华中科技大学硕士学位论文 = = = = = = = 一 插图目录 图2 1 体主多点接入的分类6 图2 - 2 共享信道型网络7 图2 。3 蜂窝接入型网络8 图2 。4 纯a l o h a 系统的工作原理9 图2 5 纯a l o h a 的吞吐量和网络负载的关系1 0 图2 - 6 d q r a p 信道结构图1 4 图2 7 e t i 和c i u 1 4 图2 - 8 d q r a p 和m d 1 以及其他随机接入协议吞吐率比较1 6 图2 - 9 轮叫轮询多点线路1 8 图2 1 0 轮叫轮询的工作原理1 9 图2 11 轮询系统的循环时间t c 1 9 图2 1 2 传递轮询多点线路2 1 图2 1 3 o s s s 上行信道结构2 5 图3 一1 上行数据带宽分配总体结构图2 6 图3 2 移动终端下行数据发送状态转移图2 7 图一3 队列长度修正方法一2 8 图：一4 移动终端上行带宽申请状态转移图3 0 匿3 5 带宽分配指示信息块格式一3 2 图36 分配信息块格式3 2 图3 一数据帧捎带字段格式一3 2 图3 一 控制帧捎带字段格式一3 3 图3 - 0 控制帧捎带字段格式一3 3 图3 1 0 数据带宽w f q 分配流程图3 5 图4 一1 控制p d u 总个数分布直方图3 8 图4 2 数据p d u 总个数分布直方图3 8 v 华中科技大学硕士学位论文 = = = = = ；# 一 图4 3 移动终端l 获得的数据p d u 个数分布直方图3 9 图4 - 4 移动终端1 0 获得的数据p d u 个数分布直方图3 9 图4 - 5 移动终端2 0 获得的数据p d u 个数分布直方图一4 0 图4 - 6 所有移动站获得的数据p d u 个数的分布直方图4 1 图4 7 分配带宽和实际使用带宽积累值的比较4 1 图4 - 8 移动终端1 的p d u 申请时延变化曲线4 2 图4 - 9 移动终端1 的p d u 申请时延的分布直方图4 2 图4 - 1 0 所有移动终端的p d u 申请时延的分布直方图4 3 v i 华中科技大学硕士学位论文 表格目录 表2 - 1 d q r a p 和m d ! 理想系统的平均时延和方差的比较( m i n i s l o t s 2 3 ) 1 7 表3 1 上行控制带宽分配方法一2 7 表3 - 2 长度等级对应表一2 8 v 1 i 华中科技大学硕士学位论文 = = = = = = = = = = = = 2 = = = = = = = = = = = = = = = = = = 一 1 1 引言 1 绪论 近年来随着信息技术的发展，人们对广域移动通信网和局域无线接入网的需求 都越来越大。人们希望能够拥有无所不在和无所不能的通信方式。9 0 年代以来，无 线通信技术的迅猛发展使得通过无线媒介向移动用户提供宽带接入称为研究的热 点，最有前景为用户提供高速无线数据业务的通信技术一- - c d m a 能够提供下行 2 m b s 的峰值数据率，并且向各种业务类型提供高质量的q o s 保证。 现有的蜂窝通信系统主要用于话音通信，不具备支持高速率，多类型综合业务 的能力。当前应用最广泛的g s m 系统提供最高8 个g s m 业务信道( 8 9 6 k b s ) 的 数据率。目前大多数无线局域网标准主要支持多种业务服务质量的能力，当前准备 进入商业用同的第三代移动通信系统，遵循u m t s p l m t s 标准 4 1 1 ，系统采用宽带 c d m a 技术，系统最高可达2 m b s 的数据率，支持话音、数据和低数据率视频等业 务。 第三代移动通信( 3 g ) 网路应具有的特点如下： 1 ) 传输技术的宽带化； 2 ) 传输数据的分组化； ) 承载业务的多样化； 4 ) 无线资源的共享化： 5 ) 移动管理的简易化。 i 线信道的特点是多用户、多业务共享介质。与宽带骨干网上高容量相比，有 限的无哇p 源是非常宝贵的。因此设计一个高效率的无线多址接入控制协议，为各 种多媒# 业务进行资源的分配与调度，对于q o s 性能保证非常重要。由于没有完善 的无线：e 波监听，用户在传送信息时并不知道别的用户是否同时在传送，如果发生 了碰撞，将造成无线资源的浪费，因此要有效率地共享无线资源，就需要基站来协 l 华中科技大学硕士学位论文 调各个用户终端，用户与基站之间用与协调接入的协议就是多点接入控制( m u l t i p l e a c c e s sc o n t r o l ，m a c ) 协议。 在高速无线i p 移动通信系统中，传输速率大为提高，因此用有效的多点接入技 术控制移动终端，使其合理地占用有限的网络资源是关键技术之一，多点接入控制 协议是支持多个终端设备共享无线信道所不可缺少的。从网络层次上分析，多点接 入技术属于数据链路层中的媒体接入控制m a c 子层的内容，m a c 子层的主要功能 包括： 1 ) 逻辑信道和物理信道的映射和多路复用； 2 ) 数据封装功能，包括成帧，编址； 3 ) 逻辑信道之间对物理信道访问的优先级处理； 4 ) 差错检测，包括c r c 生成和c r c 校验，实现对物理介质传输差错的检测。 多点接入控制属于信道共享技术之一( 另一信道共享技术为使用集中器和复用 器) ，主要用于解决多个用户对公共带宽如何划分使用的问题。导致该问题的根本原 因在于每个用户在需要发送数据时，不能准确知道其它用户是否也需要发送数据， 而这个困难在以太网和蜂窝网中都存在。最早的多点接入技术是于1 9 7 0 年在 a l o h a 系统【1 】中提出的，随后发展了一系列m a c 协议及相关技术，最著名的有 现在广泛用于以太网的c s m a c d 。 m a c 技术的相关理论基础包括随机过程和排队论，对于以太网，其理想的m a c 接入模型为m d i ，对于蜂窝网络，其理想的m a c 接入模型为m d m 4 2 】( k 为码 道数或载波数) 。蜂窝无线网络中的长传输时延、高误帧率和多信道使m a c 协议的 设计存在很大的难度。到现在为止，蜂窝无线网络的接入问题并没有很好的解决。 第三代移动通信技术( 3 g ) 的主要有：以美国为主提出的c d m a 2 0 0 0 技术、以 欧洲、只本为主的w c d m a 技术和以中国为主的t d - s c d m a 技术，这三种技术都 是n j 于扩频技术。对于采取扩频技术的蜂窝系统，其上行都是一个自干扰系统 4 3 】， 其反向链路的同小区干扰是由其他移动站的信号在基站接收机叠加而成的。在基站 接收机的几乎所有噪声都是由于移动信号的干扰造成的。可同时呼叫发射的移动台 数目( 系统容量) 达到最大值所要求的条件是使每个移动站信号到达基站时具有相 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一 同的功率，而且应在满足链路性能的前提下信号功率尽可能的低。如果每个移动单 元的发射机都进行调整，使得基站接收到的信扰比达到可允许的最低水平，系统的 容量将会达到最大。 在建立起理想上行闭环功率控制的条件下，当用户数不变时，上行的容量是固 定的，那么每个传输时间间隔( t t i ) 内发送的数据数量不能超过这个规定的容量， 否则将造成上行的冲突，该t t i 的所有上行数据得不到的正确的解码。另一方面， 如果每个t t i 内发送的数据量远小于规定的容量，则回造成信道资源的浪费，只有 当实际发送数据量尽可能接近规定容量而又不能超出，才是最佳的。 传统的上行速率分配策略主要采取电路交换方式，上行带宽资源被每项业务( 或 用户) 独占。这种分配策略在处理话音业务时可以说是成功的。然而i p 数据业务有 着和话音业务完全不同的流量特性，主要表现为在时间、空间两方面的高度不确定 性( 或突发性) 。电路交换方式在处理数据业务时，将会造成带宽极大的浪费。 在现有的技术标准中的上行速率控制算法的设计上，均采取一种近似电路式交 换的分配方式，其基本方法分述如下： w c d m a 技术 3 7 3 8 将业务按其对传输的需求划分为8 种传输格式( t r a n s p o r t f o r m a t ) ，分别具有不同的绝对优先级( 即可抢占型) 。给定的传输格式规定了传输 的速率、时延和瞬时最大吞吐量等特性。当有数据需要发送时，移动站和基站之间 的r r c 首先选择一种传输格式作为业务承载，协商建立该业务承载的连接。然后 m a c 层按照该传输格式的规定( 发送频率，发送包的大小等) 传送数据包，等到 数据传输完毕后双方r r c 释放该业务承载连接。 c d m a 2 0 0 0 的上行速控算法 3 9 4 0 1 和w c d m a 类似，根据业务需求建立若干 个逻辑连接，当有数据需要发送时，该连接被激活；当长时间没有数据发送时，该 连接妒转入休眠状态，部分系统资源被释放。 ：c d m a 和c d m a 2 0 0 0 的算法在处理话音类业务时有其优势，但是在面对 t c p i p 类的数据业务时，数据的突发性要远远高于话音类业务，这样就会造成两个 问题：t1 ) 频繁的连接激活、休眠的状态转换使控制带宽占用量增大。( 2 ) 在正式传数 据前需要进行连接状态的转换( 或者是连接的重新建立) ，增大了数据传输时延。 3 华中科技大学硕士学位论文 ；= = = 一= ： 所以当c d m a 无线通信网处理数据业务时，需要设计新的算法去满足其通信需 求。 媒体接入控制的目标是支持可用比特率( a b r ) 、可变比特率( v b r ) 、恒定比 特率( c b r ) 和未指定比特率( u b r ) 业务的同时，保持高效的无线信道利用率， 并提供相应的q o s 控制。衡量无线多址接入控制协议的主要指标可包括时延、时延 抖动、误帧率、吞吐率。 时延可以定义为m a c 帧从开始发送到被全部正确接收所消耗的平均时间，理 想状态下，信道没有误帧，则时延等于m a c 帧的发送时间加上传播时延。实际系 统中，时延还要考虑多点接入控制耗时和误帧重传耗时。对于一些时延敏感性业务 ( 如话音，视频会议等) ，过大的时延将会造成上层业务质量下降，甚至业务完全不 可用；而对于某些非实时性业务，时延的影响对其业务性能影响并不显著，如何在 这两类业务间权衡将是多点接入算法需要考虑的问题之一。 时延抖动衡量时延的变化幅度，时延抖动对上层业务的影响可以转换为时延的 影响，但其最主要的问题在于增加数据量的突发性，缓冲区占用量变大，路由的过 程中容易发生拥塞而导致丢弃，从而降低数据传输的效率。 误帧率指成功接收的数据量相对实际发送数据量的比例。数据业务对误帧率的 要求很严格，稍微大一点的误帧就会导致业务完全不可用，而对于语音业务，由于 人f 的敏感度和插值算法的使用，其影响并不大。对于误帧率的控制，主要是通过 a r o 协议。但是当重传到达一定次数时，由于时延过大，导致上层协议的超时，那 么谚数据帧实际上仍相当于丢失了，所以一般在a r q 协议中都会限制误帧的重传 长数 = l ；吐率主要是指链路层实际传输的数据量相对于信道理论最大传输量的比例。 这1 吞吐率的定义包含了传输误帧的影响。因为作为多点接入协议，其性能的优劣 主晏奉址在对信道的利用率上，而不应将物理层传输误帧对传输量的影响考虑进去。 垦唇，对于c d m a 系统中的多点接入控制协议，必需保证上行发送总数据量不 能超过系统上行设计容量，否则发送时隙所有上行数据都不能正确接收。 一 4 华中科技大学硕士学位论文 = = = = = = = = = = = ；= = = = = = = = = = = = = ： 1 2 研究目标和内容 本课题的来源是国家8 6 3 重大课题“高速无线互联网技术”，主要承担c d m a 系统中上行链路多点接入控制部分的研究。在深入研究当前多点接入技术体系架构 的基础上，针对c d m a 系统空中接口部分高误帧、高时延的无线传输特点，提出一 种新型的多点接入方案，力图在保持移动终端上行接入高效的同时，维护用户之间 资源占用的公平性，最后通过仿真验证其性能。 本文各章的内容安排如下： 第一章概述多点接入技术的研究背景和发展现状，提出c d m a 网络中多点接入 技术实现的难点，并给出多点接入技术性能衡量的指标。 第二章按照多点接入技术特点将接入技术分为随机接入类、受控接入类和混和 类。着重介绍了各类型中最具代表性的几种多点接入技术，比较分析了它们的性能。 第三章结合业务特性和无线信道高误帧、高时延的特点，提出了一种适用于 c d m a 无线环境下的多点接入技术方案，详细阐述了其中的技术细节。 第四章给出了这种新的多点接入协议在c d m a 网络环境下的仿真性能曲线。并 作出相应的分析解释。 第五章给出总结和未来研究工作的展望。 5 华中科技大学硕士学位论文 2 多点接入理论分析与系统架构 2 1 多点接入技术路线 常见多点接入技术的划分如图2 - 1 所示，m a c 技术从其基本策略上可以划分为 两大类：随机接入和受控接入。此外，还有结合两者特征的混和类型。 多点接入技术 图2 1体主多点接入的分类 6 华中科技大学硕士学位论文 受控接入的特点是各个用户不能任意接入信道而必须服从一定的控制。这又分 为两种：即集中式控制和分散式控制。属于集中式控制的有多点线路轮询( p o l l i n g ， 分为轮叫轮询和传递轮巡) ，即主机按照一定顺序逐个询问各用户有无信心发送。如 有，则被询问的用户就立即将信息发送给主机：如无，则再询问下一站。属于分散 式控制的有令牌环形网。在环路中有一个特殊的帧，叫做令牌或权标( t o k e n ) 。令 牌沿环路逐站传递。只有获得令牌的站才有权发送信息。当信息发送完毕后，即将 令牌传递给下一个站。在协议的控制下，连接到环路上的许多站就可以有条不紊的 发送数据。环形网也叫做令牌传递环( t o k e n p a s s i n g r i n g ) ，是一种常用的局域网。 随机接入的特点就是所有的用户都可以根据自己的意愿随机地发送信息。以太网就 属于这种类型。在以太网中，当两个或者更多的用户同时发送信息时，就产生了帧 的冲突的网络协议。随机接入实际上就是争用接入，争用胜利者才能获得总线( 即 信道) ，从而获得信息的发送权。 2 2 网络模型 应用m a c 技术的常见网络模型有两种：共享信道型和蜂窝接入型。 共享信道型的特点有：网络拓扑结构为总线型。网络中的用户可以直接判断信 道状态和检测冲突。任一时刻信道只能供一个用户使用，如果有两个或更多的用户 数据在时n _ k 重叠则发生冲突：检测信息反馈时延一般较短。以太网是最典型的共 享信道型网络，如图2 2 所示。 l2n 1n 图2 2 共享信道型网络 蜂窝接入型的特点有：网络拓扑结构为星型。网络中的只有一个节点可以直接 掌握信道状况，该节点对所有用户的传输是广播式的；用户不能直接进行冲突检测： 任何时刻信道可以容纳多个用户同时传播数据，但数据量不能超过规定的门限；检 华中科技大学硕士学位论文 测信息反馈时延一般较长。如图2 3 所示。 2 3 主要的随机接入技术 图2 3 蜂窝接入型网络 随机接入最基本的流程为：用户随机选取时刻发送数据，一旦发现了冲突，则 延迟一段随机时间后，重发冲突的数据。随机接入最早是在a l o h a 系统中发展起 来的，1 9 7 3 年提出了r e s e r v e d a l o h a 2 ，1 9 7 5 年提出了s l o t t e d a l o h a 3 ，并由 此演变出著名的c s m a 以及c s m a c d 、c s m a c a 4 7 等一系列的协议。1 9 8 9 年， d j g o o d m a n 在考虑了业务特性的基础上，提出了一种类似于r e s e r v e d a l o h a 的 协议一- - p r m a 8 ，9 】，并由此派生出一系列p r m a 类协议 1 0 - 1 3 】。为了克服a l o h a 类协议在高负载时不稳定性，t r e es p l i t t i n ga l g o r i t h m 冲突判决算法【2 2 】于1 9 7 7 年被 提出，以后通过不断改进信道反馈方法，最大吞吐率不断被提高，其中a a ra 1 5 获得了最高达0 8 5 3 的吞吐率和良好时延特性。1 9 9 3 年提出的d q r a p 协议 1 6 ，1 7 】 可以在足够小的系统开销前提下同时到达稳定性和接近于1 的吞吐率。 2 - 3 1 纯a l o h a a l o h a 系统最初是在2 0 世纪7 0 年代初期在夏威夷大学试验成功的，目的是 使地理上分散的用户通过无线电来使用中心计算机。由于无线信道是一个公用信道， 一个站发送的信息可以同时被多个站收到，而每个站又是随机发送的，因此这种系 统是一个随机接入系统。在a l o h a 系统出现以后，很多性能更好的协议也相继问 8 o 盆 o ， 盗 丑：童 ，r ， i 丑 盆 华中科技大学硕士学位论文 世，其中一种改进的随机接入协议c s m a c d ( c a r r i e rs e n s em u l t i p l ea c c e s sw i t h c o l l i s i o nd e t e c t i o n ) ，即载波监听多点接入冲突检测，现在已称为总线式局域网的标 准协议。 图2 - 4 表示一个a l o h a 系统的工作原理。每一个站均自由地发送数据帧。以 发送帧所需时间来表示帧的长度，且发送的帧均为定长t o 。当站1 发送帧1 时，其 他的站都未发送数据，如果不考虑由于信道不良造成的误码，站1 的发送必定成功。 但随后站2 和站n 一1 发送的帧2 和帧3 在时间上重叠了一些，就会产生数据冲突。 发生冲突的各站不能马上进行重发，否则必然会继续造成冲突。a l o h a 系统采用 的重发策略是让各站等待一段时间，然后再进行重发。如再发生冲突，则需再等待 一段随机的时间，直到重发成功为止。 站z 酋团兰，。 川 斗阳兰釜i t 站z 团e 塾曲兰塾 站i 一。 由三三竺三全口 站w 田 ，。 图2 4 纯a l o h a 系统的工作原理 下面我们分析a l o h a 的性能。如图2 - 4 最下面的坐标所示，垂直向下的箭头 表示某个帧的开始发送时间，可以看出，一个帧如欲发送成功，必须在该帧发送时 刻之前和之后各一段时间t o 内( 一共有2 t o 的时间间隔) ，没有其他帧的发送。否 则就必产生冲突而导致发送失败。将每发送一个帧看成是有一个帧到达a l o h a 网 络，则一个帧发送成功的条件，就是该帧与该帧前后的两个帧的到达时间间隔均大 于t o 。 在假设站点数目足够多、重发时的随机时延足够长，且每个站的通信量都很小 的条件下，整个系统帧的到达可以看成是泊松过程。为了分析a l o h a 的性能，定 华中科技大学硕士学位论文 义如下两个归一化的参数。 吞吐量s ：又称为吞吐率，等于在帧的发送时间t o 内成功发送的平均帧数。显 然，0 s 1 ，而s = 1 是极限情况。在s = 1 时，帧连续不问断地发送出去，信道 没有空闲。这种情况虽然使信道的利用最为充分，但实际中是不可能实现的。可以 用s 接近1 的程度来衡量信道的利用率是否充分。在稳定的情况下，在时间t o 内到 达系统的平均帧数应等于吞吐量s 。 网络负载g ：从网络的角度看，g 等于在t o 内总共发送的平均帧数。这里包括 发送成功的帧和因冲突未发送成功而重发的帧。显然，g s ，而只有在不发生冲突 的时候，g 才等于s 。还应注意到，g 可以远大于l 。例如，g = 1 0 ，表示在t o 时 间内网络平均发送1 0 个帧，这当然会导致很多的冲突。 在稳定状态下，吞吐量s 与网络负载g 的关系为： s = g p 【发送成功】 这里p 【发送成功】是一个帧发送成功的概率，它实际上就是发送成功的帧在所发 送帧中所占的比例。所以： p 发送成功 = p 连续两个到达时间间隔 t o 】= ( p 到达时间间隔 t o ) 2 因为到达率为泊松过程，所以到达时间间隔的概率密度如下式所示 a ( t 、= 2 e 一“ 其中 是帧的平均到达率。所以 = g 厂r o 。于是可以求出： p 【达到时间间隔 t 。】2e 口( t ) d t = e 号e - 6 l t 。d t = p - g 图2 5 纯a l o h a 的吞吐量和网络负载的关系 1 0 华中科技大学硕士学位论文 所以 p 【发送成功】= e 2 g 最后可得吞吐率 s = g e 之。 故可以求得，当g = 0 5 时，s = 0 5 e s 0 ，1 8 4 ，这是吞吐量s 可能达到的极大 值。由图2 5 的吞吐量曲线可知，当g 值大于0 5 时呈现负的斜率，因而这段区域 是不稳定的。可见，在纯a l o h a 系统中，网络负载g 一定不能超过0 5 。 纯a l o h a 是最早提出的随机接入协议，当网络负载为0 5 时，纯a l o h a 可 达到理论最大吞吐率为o 1 8 ，如图2 5 所示。当网络负载大于0 5 时，吞吐率随网 络负载增加而减小，因而这段区域为不稳定区域。 时隙a l o h a 要求各站在时间上同步起来，将信道在时间尺度上划分为等长的 时隙，数据只能在时隙开始的时候发送出去。当网络负载为1 时，时隙a l o h a 可 以达到理论最大吞吐率0 3 6 。 a l o h a 是最早提出的随机接入协议，由a l o h a 扩展出了许多性能更为优越 的随机接入协议，算形成了一个庞大的a l o h a 协议族，其中最著名的有广泛应用 于以太网的c s m a 和c s m 刖c d 。 由a l o h a 演变出的载波监听多点接入c s m a ( c a r r i e rs e n s em u l t i p l ea c c e s s ) 最大的改进之处在于：每个站都能在发送数据前监听信道上其他站是否在发送数据， 如在发送，则此站暂不发送数据，从而减小了发送冲突的可能，提高了系统的吞吐率。 根据监听信道后采取的策略不同。又可分为非坚持，l 坚持和p 坚持。非坚持 就是一旦监听到信道忙，则停止监听，延迟一个随机的时间后重新监听。坚持c s m a 的特点是监听到信道忙时，仍继续监听下去，直到发现信道空闲为止。如果这时立 即发送数据，则称为1 坚持，如果按照概率p 发送数据，而以概率( 1 一p ) 延迟一段 时f b jt ( 端到端的传播时延) ，重新监听信道，则称为p 坚持c s m a 。 c s m a c d 在c s m a 的基础上增加了冲突检测，即边发送边监听，只要监听到 发生冲突，则冲突双方立即停止发送。 所有的a l o h a 类协议都存在一个不稳定区，一旦网络负载超过了某一门限， 华中科技大学硕士学位论文 都会导致网络性能急剧下降。在实际应用中必须采取特殊的手段加以防止。 冲突发生之后，最常用的随机退避算法为截断二进制指数类型( t r u n c a t e d b i n a r y e x p o n e n t i a lt y p e ) 。具体如下：令k = - m i n ：重发次数，1 0 】，从离散整数集合f o 1 ，2 b 1 】 中随机选取一个数r ，重发所需的延迟就是r 倍的基本退避时间( 一般取为2t ) 。 当重发若干次后仍不能能成功，则丢弃该帧，并向高层报告。 定义网络端到端的最大传播时延r 和数据帧长t 0 之比为a ，称为归一化时延。 a l o h a 类协议的性能对归一化时延非常敏感【2 1 】。则只有当a 远小于1 时，网络才 能达到较理想的最大吞吐率。当a 增大到o 1 以后时，最大吞吐率会迅速下降。所 以对于时延较大的蜂窝网络，即使在有冲突检测的前提下，a l o h a 类协议也是不 能直接使用的。 2 3 2 树分算法 为了解决a l o h a 类协议的不稳定性问题，树分算法( t r e es p l i t t i n gc o l l i s i o n r e s o l u t i o n a l g o r i t h m ) 被提出。严格的说，树分算法并不是一个独立的多点接入技术， 而是多点接入中一种冲突避免的方法。所以它在不同网络环境中有不同的表述方式， 其基本思想如下。 设网络中有n 个用户，所有用户按i n 编号。所有用户都能独立地监听信道和 检测冲突。如果某时刻发生了冲突，则未参与冲突的用户将不再向信道中发送数据， 直到冲突解决。发生了冲突的用户中，编号在l n 2 范围内的用户推入堆栈中，编 号在n 2 n 范围内的用户在下一时隙发送数据。这时候有三种情况出现： 1 ) 如果仍然有冲突，则编号在n 2 3 n 4 范围内的用户推入堆栈中，编号在 3 n 4 n 范围内的用户在下一时隙发送数据。 2 ) 如果没有冲突且有数据正常发送，则在数据发送完毕后，将堆栈顶部的用户 弹出，在下一时隙发送数据。 3 ) 如果没有冲突也没有数据在信道中传输，则将堆栈顶部的用户弹出，在下一 时隙发送数据。 像上面重复操作，直到堆栈清空，所有参与了冲突的用户的数据都发送完毕， 这一轮的冲突才算完全解决。 1 2 华中科技大学硕士学位论文 树分算法有很多种实现方式，另一种常见的就是在发生冲突之后每个站生成一 个0 - 1 浮点随机数，如果值小于o 5 则推入堆栈，大于o 5 的可以参与下一时隙的 竞争。 树分算法的最大优势在于其稳定性，无论输入负载如何变化，系统总可以保持 一定的吞吐率。 a l o h a 类协议采取了控制发送概率、随机延迟等方法，将竞争在时间轴上向 后分散开来，这种策略对短时的冲突有效，如果负载长时间保持在一个较高的门 限上，将冲突推迟到后面只会增加后面冲突的概率，导致冲突更加频繁，最终导 致系统吞吐量急剧下降。树分算法的关键在于每次发生冲突之后，禁止部分发生 冲突的站继续参与竞争，降低下一时隙竞争用户的个数，从而降低冲突发生的概 率。当一轮冲突解决之后，被禁止的移动站才可以参加竞争，保证他们仍有机会 发送数据。 第一个冲突判决算法于1 9 7 7 年被c a p e t a n a k i s 在其博士论文 2 2 1 q 6 提出提出， c a p e t a n a k i s 显示树分算法在保持稳定的前提下达到o 4 3 1 4 的最大吞吐率。m a s s e y 改进了树分算法，并将最大吞吐率提高到0 4 6 2 2 3 ，t s y b a k o v 和l i k h a n o v 提出在 三元信道反馈信息的条件下，树分算法的吞吐率的理论上限为o 5 6 8 2 4 】。有些协议 通过使用控制微时隙( c o n t r o lm i n i s l o t s ) 来获得额外的反馈信息，可以达到大于0 5 的 吞吐率 1 5 ，2 5 2 8 ，其中a a r a 在使用三个控制微时隙的条件下达到了o 8 5 3 的最 大吞吐率。但是如果需要达到吞吐率1 ，则需要无限多个控制微时隙。r a m a 3 2 3 3 是树分算法在g s m 系统上的应用。 2 3 3d q r a p 在d q r a p ( ad i s t r i b u t eq u e u e i n gr a n d o ma c c e s sp r o t o c 0 1 ) 协议中，信道被划分 为等长的时间单元，每个时间单元由m 个控制微时隙和1 个数据时隙组成。设控制 微时隙的长度为6 ，数据时隙的长度为1 ，则6 1 ，如图2 - 6 所示。控制微时隙用 于传输请求信息，数据时隙用于传输数据包。所有用户可以实现控制微时隙和数据 时隙的同步，并且能独立检测到信道中的三种反馈信息。假设用户可以实时地获取 反馈信息。 华中科技大学硕士学位论文 m l i i 一 i 图2 6d q r a p 信道结构图 在包到达时间轴上，定义初始时间为x o 。t i - l 代表在传输时间轴上在x i - l 时间以 前到达的所有帧已经成功解决了他们的冲突，定义x i 为：x i = x i 1 + m i n w 。，t j 1 一 x i 1 ，其中、k 称为d e f a u l tw i n d o ws i z e 。时间间隔( x ，x i ) 称为t h ee n a b l et r a n s m i s s i o n i n t e r v a l ( e t i ) ，时间间隔( t i 1 ，t i ) 称为t h ec o n t e n t i o nr e s o l u t i o ni n t e r v a l ( c r i ) ，时间间隔 ( x ，t i i ) 称为t h ew a i t i n gi n t e r v a l 。显然，( x i 1 ，t i - 1 ) ( x i _ i ，1x i ) ，如图2 _ 7 所示。 ( a ) w o t 。l x 。 t r a n s m i s s i o na x i s ( b ) w 0 t 一x 1 t r 椰幽i a x i 8 图2 7e t i 和c r i 在d q r a p 中，冲突检测是基于e t i 的，只有当前e t i 内到达的数据包的冲突 都解决了，下一e t i 内的数据传输才能开始。 网络中每个站维护两个分布式队列：数据传输队列，简写为t q ，和冲突检测 队列，简写为r q 。令 t q ( t ) i 和i r q ( t ) 1 分别代表在第t 个时间单元t q 和r q 的长度。 1 4 华中科技大学硕士学位论文 令f j j = 1 , 2 ，r ，代表第j 个控制微时隙的反馈信息，f j 有三种可能的值 e ，s ， c ，e 表示一个空的微时隙，s 表示只有一个请求信息在微时隙中，c 表示有两个 或者更多的请求信息在一个微时隙中。 协议算法分为三部分：数据传输规则( d t r ) ，请求传输规则( r t r ) 和队列组 织规sj j ( q d r ) ，分别表述如下。 数据传输规则( d t r ) 1 ) 如果i t q ( t ) i = 0 且f r q ( t ) l = 0 ，那么在当前e t i 有数据到达的用户可以立即在 发送数据包。 2 ) 如果i t q ( t ) l 0 ，则在t q 最前端的用户发送数据。 请求传输规则( r t r ) 1 ) 如果i r q ( t ) = 0 ，则在当前e t i 内有数据到达的用户在m 个控制微时隙中随 机选取一个，发送请求信息。每一个数据包对应一条请求信息，一条请求信息只占 用一个微时隙。 2 ) 如果i r q ( t ) l 0 ，则在r q 最前端的用户在m 个控制微时隙中随机选取一个， 发送请求信息。 队列组织规则( q d r ) 1 ) 每次获得f j = s ，( j = 1 ，m ) ，所有用户将 t q ( t ) i 加l 。 2 ) 在第t l 时间单元成功发送一个数据包，则所有用户将i t q ( t ) i 减1 。 3 ) 如果i r q ( t ) l = 0 ，则所有用户将修改i g q ( t ) i 为n ，其中1 3 为在第t 时间单位内微 时隙冲突次数( 即f j = c 的次数，j = 1 ，m ) 。 4 ) 如果i r q ( t ) i 0 ，则所有用户将将i r q ( t ) i 加n - 1 ，其中n 为在第t 时间单位内微 时隙冲突次数( 即f j = c 的次数，j = l ，m ) 。 5 ) 所有传输了数据或者发生了请求冲突的用户知道自己在t q 和r q 中的位 置，并做相应调整。 整体规则 根据上面的规则，整个d q r a p 协议描述如下 设置t = 0 ，l r q ( t ) f = 0 ，l r q ( t ) l = 0 ； 华中科技大学硕士学位论文 w h i l e ( t r u e ) 1 、t = t + 1 2 ) 按照d t r 传输数据 3 ) 按照r t r 传输请求 4 ) 所有用户按照q d r 修改b t q ( t ) l 和i r q ( t ) b ，调整自己在t q 和r q 中的位置。 ) d t r 的第一条保留了随机多点接入协议的立即接入的特征，从而和其他带宽保 留类协议区分开。虽然这点会造成数据时隙的冲突，但是提高了协议的时延特性， 尤其是在负载低的情况下。d q r a p 解决队列竞争的方法和多比特反馈算法【2 9 ( m f a ) 类似，但其反馈是通过多个微时隙获得三元反馈信息，而不是通过多比特 获得二元反馈信息。 d q r a p 可以在保持稳定性的条件下，使用少量微时隙，达到接近于理想 ( m d 1 ) 的吞吐率和时延特性。图2 8 是d q r a p 和m d 1 以及其他随机接入协 议的吞吐率的比较。表2 - 1 比较了使用3 个微时隙的d q r a p 和m d 1 系统的时延 的均值、方差。 图2 8d q r a p 和m d i 以及其他随机接入协议吞吐率比较 华中科技大学硕士学位论文 表2 - l d q r a p 和m d 1 理想系统的平均时延和方差的比较( m