（计算机软件与理论专业论文）无线局域网的mac层公平性及协议设计.pdf

论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：魁 驴口易年玉月更男日 第一章绪论 1 1 无线局域网简介 第1 章绪论 随着无线局域网技术的发展，人们越来越深刻地认识到，无线局域网( w l a n ) 不仅能够满足移动和特殊应用领域网络的要求，还能覆盖有线网络难以涉及的范 围。无线局域网作为传统局域网的补充，目前已经成为局域网应用的一个热点问 题：有了它，我们在进行数据交换时就不必受时间和空间的限制，可以随时随地 浏览i n t e r n e t ，再也不用为网络布线而苦恼 那么，到底什么是无线局域网? 简单说来，无线局域网就是利用无线通讯手 段实现快速接入以太网的技术。随着计算机技术和网络技术的蓬勃发展，网络在 各行各业的应用越来越广。有线网络以其传输速率高，产品的品牌及数量众多和 技术发展速度快等优点，在市场上有着的知名度和市场份额。然而，随着无线网 络在技术上的成熟，产品种类的不断增加和产品成本下降，在可以预期的未来， 无线网在全世界范围内将得到极大的发展。无线局域网应用越来越多，它将扩展 有线局域网或在某些情况下取而代之。可以预期，在未来信息无所不在的时代， 无线网将依靠其无法比拟的灵活性，可移动性和极强的可扩展性，使人们真正享 受到简单、方便、快捷的连接。 下面从传输方式、网络拓扑、网络接口及对移动计算的支持这四个方面来 描述无线局域网的特点。 一、传输方式 传输方式涉及无线局域网采用的传输媒体、选择的频段及调制方式。目前无 线局域网采用的传输媒体主要有两种，即微波与红外线。在采用微波做为传输媒 体的无线局域网依调制方式不同，又可分为扩展频谱方式与窄带调制方式。 l 、扩展频谱方式 在扩展频谱方式中，数据基带信号的频谱被扩展至几倍几十倍再被搬移至 射频发射出去。这一做法虽然牺牲了频带带宽，却提高了通信系统的抗干扰能力 和安全性。由于单位频带内的功率降低，对其它电子设备的干扰也减小了。采用 扩展频谱方式的无线局域网一般选择所谓的i s m 频段，这里i s m 分别取自 i n d u s t r i a l 、s c i e n t i f i c 及m e d i c a l 的第一个字母。许多工业、科研和医疗设备辐射 6 第一章绪论 ( a c c e s sp o i n t ) ，所有站点对网络的访问均由其控制。这样，当网络业务量增大 时网络吞吐性能及网络时延性能的恶化并不剧烈。由于每个站点只需在接入点覆 盖范围内就可与其它站点通信，故网络中心站点布局受环境限制亦小。此外，中 心站点为接入有线主干网提供了一个逻辑接入点。有中心网络拓扑结构的弱点是 抗毁性差，接入点的故障容易导致整个网络瘫痪，并且接入点的引入增加了网络 成本。本文将重点讨论有中心拓扑的无线局域网。 在实际应用中，无线局域网往往与有线主干网络结合起来使用。这时，接入 点也充当无线局域网与有线主干网的转接器。 三、网络接口 这涉及无线局域网中站点从哪一层接入网络系统。一般来讲，网络接口可以 选择在0 s i 参考模型的物理层或数据链路层。所谓物理层接口指使用无线信道替 代通常的有线信道，而物理层以上各层不变。这样做的最大优点是上层的网络操 作系统及相应的驱动程序可不做任何修改。这种接口方式在使用时一般做为有线 局域网的集线器和无线转发器以实现有线局域网间互联或扩大有线局域网的覆 盖范围。 另一种接口方法是从数据链路层接入网络。这种接口方法并不沿用有线局域 网的m a c 协议，而采用更合适无线传输环境的m a c 协议。在实现时，m a c 层以下对m a c 层以上是透明的，配置相应的驱动程序来完成与上层的接口，这 样可保证现有的有线局域网操作系统或应用软件可在无线局域网上正常运行。目 前，大部分无线局域网厂商都采用数据链路层接口方法。 四、无线局域网的应用环境 根据无线局域网的特点，其应用可分为两类：一类作为半移动网络应用，一 类作为全移动网络应用。 在半移动应用环境下，又可分为室内应用和室外应用。在室内应用下，无线 局域网作为有线局域网的补充，与有线局域网并存。由于无线局域网的价格比有 线局域网高，故在室内环境下，无线局域网在以下应用情况可发挥其特长：大型 办公室、车间、超级市场、智能仓库、临时办公室、会议室、证券市场等。 在难于布线的室外环境下，无线局域网可充分发挥其高速率、组网灵活之优 点。尤其在公共通信网不发达的状态下，无线局域网可作为区域网( 覆盖范围几 第一章绪论 十公里) 使用。下面列出几种应用情况：城市建筑群间通信；学校校园网络： 工矿企业厂区自动化控制与管理网络：银行、金融证券城区网络：城市交通信 息网络；矿山、水利、油田等区域网络：港口、码头、江河湖坝区网络；野 外勘测、实验等移动网络；军事、公安移动网络等。 无线局域网与有线主干网构成移动计算网络。这种网络传输速率高、覆盖面 大，是一种可传输多媒体信息的个人通信网络。这是无线局域网的发展方向。 1 2 关于m a c 协议设计 无线网络与有线网络相比，有许多特殊之处。第一，在无线网络中，无线信 道是共享介质，若在同一时刻、同一地点的同一信道上有两个或两个以上的信号 在进行传输，则信号之间会发生冲突，接收方无法分辨其中任何一个单源的信号， 导致数据传送失败( 与有线网络不同，由于天线的半双工特性，无线网络中冲突 是无法检测的，因此，有线网络中有效的c s m c d 并不能用于无线网络) 。因 此，无线信道在无线数据传输当中属于稀缺资源，其使用权在同时刻，同地 点只能被一个用户所占有。当一个用户想发送数据时，就会面临和其他相邻的用 户竞争无线信道使用权这样的情况，这就要求有机制来对这一竞争进行管理，使 信道的分配尽量地高效且公平。第二，无线传输与有线传输相比有更高的出错频 率，高丢包率会极大地影响传输层的性能，因此，需要设计专门的机制以降低上 层协议所遭遇的丢包概率。第三，因为无线网络中并不是所有节点都是彼此可达 的，这就会引申出“隐藏终端 ，“暴露终端 等等问题，如果对这些问题不加以 解决，会极大地影响无线网络的整体性能。如何高效且公平地为无线网络用户分 配信道资源，减少乃至避免冲突的发生，为上层协议提供尽量可靠的传输服务就 是无线m a c 协议的主要设计目标。 然而，现有的m a c 协议在性能上，尤其是公平性上的表现并不尽如人意 ( 2 9 3 1 ) ( 在后续章节会有较为详细的分析介绍) 。而当新的无线局域网技术( 如 多跳无线局域网( 3 2 ) ，采用多波束接入点的无线局域网( 1 7 ) ) 不断涌现出来的 时候，传统的8 0 2 1 l 协议显然已经不适用，需要提出新的改进的协议以满足新 的需求。本文将分别针对采用多波束接入点的无线局域网、多跳无线局域网提出 新的协议，并分析其性能表现。 9 第一章绪论 1 3 后续章节内容的安排 第二章，简要地介绍几种有影响力的无线m a c 协议，并作简单的分析。在 第三章，首先介绍一种新的局域网技术，采用多波束接入点的无线局域网。接着， 分析将8 0 2 1 l 协议用于此类局域网所面临的问题，论证8 0 2 1 l 协议并不适用于此 类无线局域网。最后，为了解决这些问题，提出一个新的m a c 协议以提高该网 络的性能。第四章，介绍局域网的多跳扩展技术，分析i e e e8 0 2 1 1 里的b e b 退避 算法的公平性表现，引入几种公平性定义，提出一种新的退避机制。第五章，总 结并展望。 l o 第二章无线m a c 协议概述 第2 章无线m a c 协议概述 无线网络的m a c 协议大致可以归纳为两类：基于竞争的载波侦听多路复用 访问机制( c s m a ，c a 玎i e rs e n s em u l t i p l ea c c e s s ) 和基于时分多路复用的访问机制 ( t d m a ，t i m ed i v i s i o nm u l t i p l e a c c e s s ) 。其中，基于竞争的载波侦听多路复用访问 机制由于其简单( s i m p l i c i t y ) 、灵活( f l e x i b i l i t ) r ) 和健壮性( r o b u s t n e s s ) 而广泛流行， 这种机制不需要底层架构支持，不需要严格的同步信息，不需要了解全局拓扑结 构，而且可以灵活地处理节点的动态加入和删除。基于竞争的c s m a 协议的这些 特点使得它适合于无线局域网，因此，无线局域网m a c 层广泛采用的是i e e e 8 0 2 1 1c s m c a ( c s m aw i t hc o l l i s i o na v o i d a n c e ) 机制。 自从上个世纪7 0 年代，美国夏威夷大学的n o 肌a na b r 锄s o n 等研究者提出单 跳的无线网络中进行分组数据的广播是可行的这一结论以来，针对介质共享竞争 的问题，已经有纯a l o h a 、时隙a l o h a 、载波侦听多路访问( c s m a ) ，以及i e e e 8 0 2 1 l 规范所采用的带有冲突避免的载波侦听多路访向( c s m 朋a ) 。 2 1a l o h a a l o h a 协议是2 0 世纪7 0 年代在夏威夷大学由n o 咖a na b r 锄s o n 及其同事提 出的，目的是为了解决地面无线电广播信道的争用问题。a l o h a 协议又分为纯 a l o h a ( p u r ea l o h a ) 和时隙a l o h a ( s l o t t e da l o h a ) 两种。 纯a l o h a 【4 6 】是一种完全随机的多址方式，全网不需要定时和同步，各节点 发送时间是完全随机的，即只要节点有数据要发送，就尽管让它们发送。当节点数 目不多时，系统能够很好地工作，而当节点数目很多，传输业务繁忙时，发生冲突 的概率增大，信道的传输效率就降低。通过研究证明，纯a l o h a 协议的信道利用 率最大不超过18 ( 1 2 e ) ，且存在潜在不稳定性。 l9 7 2 年，r 0 b e r t s 提出了时隙a l o h a 协议( 6 9 ) ，是对纯a l o h a 的改进，能把 信道利用率提高一倍。基本思想是，用时钟来统一节点的数据发送。办法是将信 道按时隙划分，每个时隙正好传送一个数据包，数据包到达后，必须等到下一个时 隙才能开始发送，从而避免了用户发送数据的随意性，减少了数据产生冲突的可 能性。数据包间一旦发生冲突将是百分之百的重叠，提高了信道的利用率。连续 第二章无线m a c 协议概述 2 3 多址多接入冲突避免协议( m a c a ) ，一i二：jj。：主：二_、j、 ( ，。淄辱“舀、1 )f 蒯争 ) i 、j 、 k 7 j x 7 ，j， 、一二二：-：f二：， 它不能解决控制分组之间的冲突问题，如r t s 之间的冲突，r t s 和c t s 之间的 冲突以及c t s 之间的冲突。 不具备链路层确认机制，当发生冲突需要上层超时重发，效率较低。 网络公平性较差：由于采用二进制指数退避( b e b ) 算法。如果某站的退避计 数器值较大，那么在后续的竞争中，它失败的可能性也较大，从而使得退避值 进一步增大，造成信道接入的公平性较差。例如图2 1 中，c 收到b 发来的c t s ， 如果此时d 向c 发送r t s ，则c 不能回应，从而引起d 的反复超时重发，是退避 计数器增大，当a 与b 通信完毕后，d 在重新开始的竞争中出于劣势。 2 4 无线多址接入冲突避免协议( m a c a w ) 在研究m a c a 的基础上，b h a 唱h a v a i l 等提出了m a c a w ( m a c af o rw i r e l e s s n e t w o r k s ) 算法( 2 8 ) ，其基本思路是：如果没有数据链路层的确认，丢失的分组 要等到发送机发现它们不存在时才会被重发，这样耽误了重传的时间。因此，接收 机在每次成功接收到数据分组后就回送个a c k 确认帧，发送机在二定时间内 没有收到a c k 帧就将启动重传，从而加快了分组重传的速度。 具体地，m a c a w 针对m a c a 存在的缺点进行如下修改： 避算法的改进：在发送数据报文时，报文头部包含本站的退避计数器的值， 收到报文的站可将此值作为自己的退避计数器的值。这样可使两者获得 相同的退避计数器值。当传输完成后，所有的退避计数器恢复到最小值。 这种方法能够在一定程度上防止饿死现象，但是它不能充分了解网络的 拥塞状态，从而增加了分组冲突。同时使用乘性增加线性减少退避算法 ( m i l d ) 替代b e b 算法，在m i l d 中，计数器值以1 5 的比例增加，以1 的步长 减少。此外，可以为不同的目的站维护和拷贝多个退避计数器值。通过这 些措施，公平性问题得到一定程度上的解决，但是m i l d 中使用的单一的 退避计数器会使拥塞问题过度传播，例如当某站关闭时，计数器值会急剧 增长，从而降低系统的效率。 增加了链路层确认机制：m a c a w 采用r t s c t s d a t a a c k 四次握手机 制。如果发送站没有收到来自接收站的c t s ，它超时重发r t s ：如果接收站 没有收到d a t a ，它回应c t s ：如果正确收到d a t a ，它认为c t s 被发送站 第二章无线m a c 协议概述 介质访问，避免冲突。m a c 协议的基本体系如图2 2 所示( 1 5 ) 。 在i e e e8 0 2 ，1 1 中，通过定义不同的帧间隔时间( i f s ，i n t e r - f r 锄es p a c i n g ) 来区 分对介质访问的优先级。一个节点通过载波侦听机制确定介质处于空闲状态，并 且持续空闲达到特定的间隔时间时才能进行发送。d c f 和p c f 涉及到四个不同的 间隔时间，从长到短依次是：e x t e n d e di f s 、d c f 帧间隔时间d i f s 、p c f 帧间隔时 间p i f s 、最短帧间隔时间s i f s ( s h o r ti f s ) ( 1 6 ) 2 5 1 分布式协调机制( d c d 分布式协调功能d c f 是i e e e8 0 2 1 lm a c 协议中最基本的信道共享机制，无 论是独立的基本服务集( i b s s ，i n d e p e n d e n tb a s i cs e i c es e t ) ，还是无基础设施的 网络( a d h o c 网络) ，d c f 都需要被所有节点所支持。d c f 是一种基于载波侦听多 路访问冲突避免( c s m a c a ) 的随机访问方式，它包括两种访问模式：基本访问 方法( b a m ，b a s i ca c c e s sm e t h o d ) 和可选的r i t s c t s ( r e q u e s tt os e n d c l e a rt 0 s e n d ) 访问方法。 d a t a 略i f 叫森 n 一d i f s rc w n a v 一 d e f c r a c c e s s _ b a c k o f fa r e rd e f c r 一 图2 - 3 ：基本访问方法( b a m ) 下通信模式 在基本访问方法( b a m ) 中，如图2 3 所示，一个节点要发送数据帧时，首先通 过侦听信道确定是否有其它节点正在发送数据。如果信道是空闲的并持续d i f s 时间，这个节点就开始发送。如果信道被侦听到是忙状态，这个节点将坚持侦听直 到信道空闲一个d i f s 时间，然后产生一个随机的退避时间( b a c k o f ft i m e ) ，并保存 在一个计数器中。随后，在每个时隙中，如果信道为空闲状态，退避时间计数器将 减1 ，直到退避时间计数器减到0 时，这个节点开始发送数据帧：在退避过程中，如 果在某个时隙中信道上有其它节点发送，退避时间计数器将被冻结( f r e e z i n g ) ，退 避过程暂时中断，直到信道重新变成空闲状态并持续d i f s 时间后再次被激活。目 1 6 第二章无线m a c 协议概述 标节点成功收到一个数据帧后，经过一个s i f s 时间后，向源节点发送一个确认帧 ( a c k ) ，如果源节点在超时( a c k t i m e o u t ) 设置的时间内收到a c k ，则认为数据帧 发送成功，否则，认为数据帧发送失败并进行重发。 图2 - 4 ：r t s ，c t s 方式下的通信模式 在r t s c t s 访问方法中，如图2 4 所示，一个节点需要发送一个数据帧时，等 待信道空闲并持续d i f s 时间，经过退避时间后，该节点将先发送一个请求发送数 据短帧r t s ( r e q u e s tt os e n d ) ，目标节点收到r t s 请求后，将在s i f s 间隔后返回一 个c t s ( c l e a rt 0s e n d ) 帧，源节点只有成功收到这个c t s 后才能进行数据帧的发 送。r t s 和c t s 帧中都包含着到本次数据帧发送完成所需的持续时间( d u r a t i o n t i m e ) ，其它能够侦听到r t s 或c t s 的节点将根据这个持续时间信息修改其网络 分配向量n a v ( n e t 、0 r ka l l o c a t i o nv e c t o r ) ，并在该段时间内保持沉默。因 此，r t s c t s 访问方法能够在一定程度上解决隐藏节点( t h eh i d d e nt e n n i m l s ) 问 题。数据发送完毕后，目标节点将发送确认帧a c k 以确认本次通信的完成。如果， 源节点在超时( a c k t i m e o u t ) 设置的时间内收到a c k ，则认为数据帧发送成功， 否则，认为数据帧发送失败并进行重发。其中，二进制指数退避算法( b e b ，b i n a 巧 e x p o n e n t i a lb a c k o 田( 1 6 ) 是一种冲突解决方案。二进制指数退避算法的思想是 要通过动态调整节点的发送行为以适应网络负载变化，算法要求分组冲突之后节 点退避一个随机时间，若再次发生冲突，则将退避时间加倍，若信道空闲则将退避 时间减去一个固定值，重复这样的过程直到退避时间达到某个上限。通常，i e e e 8 0 2 1 l 中规定的上限是7 次。 2 5 2 点协调机制( p c d p c f 是在d c f 的基础上定义的可选功能。p c f 需要有一个接入点来控制介质 访问，并轮询无线站点。 1 7 第二章无线m a c 协议概述 但是，当这些协议被应用到一些新型无线局域网( 如采用多波束接入点的无线局 域网( 1 7 ) ，多跳无线局域网( 3 2 ) 等等) 时，会遇到种种问题，致使协议运行 效果不佳，不能达到引入新技术以提升网络整体性能的初衷。下两章将针对这些 问题提出新的m a c 协议，它们会显著提高局域网的公平性及系统吞吐量，相应 地，为局域网用户提供更好的服务。 1 9 第三章采用多波束接入点的无线局域网m a c 协议 第3 章采用多波束接入点的无线局域网m a c 协议 本章将首先介绍一种新的无线局域网络，它的接入点( a c c e s sp o i n t ) 所用 的天线并不是传统无线局域网所采用的全向天线( o m n i d i r e c t i o i 谢a n t e 皿a ) ， 而是采用了多波束天线( m u l t i b e a ma 1 1 t e 姗a ) 。之后将分析将8 0 2 1 1 协议用于此 类局域网的时候面临的问题，论证8 0 2 1 l 协议并不适用于此类无线局域网。最后， 以解决这些问题为基本出发点，提出一个新的m a c 协议以提高网络性能。 3 1 采用多波束接入点的无线局域网的引入 随着无线局域网被越来越广泛地配置和应用于各类热点区域，如办公室，机 场，大型图书馆，工厂车间等等，人们对无线局域网的性能提出了更高的要求： 更高传输速率，更好的更稳定的服务质量，更高效的能量控制机制( 意味着更长 的终端持续使用时间) 等等。多波束智能天线系统是能够提升无线局域网性能的 技术之一。将多波束智能天线应用于无线局域网具有许多潜在的益处： 更高的天线增益能够扩襞网络的覆盖范围。得勤更高的吞吐量o 空间重翻用( 空分多址技术) 使得多个终端和接入点同时通信戒为司能o 更少的冲突。意味着更可靠的传输。 与无线终端相比，接入点有很多优势：它功能更强大；受限更少：它可以有 更大的体积和质量而不会影响到用户的使用；它有更少的功率限制，因为它不用 像终端那样需充电使用。因此，将多波束天线系统应用到无线局域网的接入点( 我 们假设终端仍然使用全向天线而不用做出太多改变，避免增加其成本) 是个非常 吸引人，且十分可行的想法。当接入点使用多波束天线时，多个使用全向天线的 终端可以同时向终端传输数据或者同时从终端接收数据，显著地提升了整个网络 的吞吐量。 3 2 新协议设计的必要性及面临的问题 i e e e8 0 2 1 1m a c 协议( 1 ，1 3 ) 是无线局域网事实上的标准，且已被广泛 地应用于商业领域。它的基本接入机制，即分布式协调机制( d c f ) ，是基于带 冲突避免的载波侦听多路接入机制( c s m c a ) 。尽管d c f 在传统的无线局域 2 0 第三章采用多波束接入点的无线局域网m a c 协议 户期望的方向形成一个窄的波束。这类天线可以通过可切换式多波束天线 ( s 、 ，i t c h e dm u l t i - b e a ma 1 1 t e r 眦) 来实现，可切换式多波束天线的多个波束之一会 被挑选用以接收或者发送信息。第二类是自适应智能天线阵列，它由若干天线单 元组成，每个单元发送的信号相互叠加，使信号在某些方向上加强，某些方向上 减弱，以满足特定的需求。尽管自适应天线阵列在多径富余环境中工作得更好， 但是它需要更复杂的信号收发器和m a c 协议，所以在本章我们考虑采用的是可 切换式多波束天线系统( 但是与上文介绍的应用稍有不同) ，因为它的简易性和 商业实用性。 在介绍扇区负载不均衡问题之前，需要先介绍将被用于无线局域网接入点的 扇区化多波束天线系统( s e c t o r i z e dm u l t i b e 锄a j l t e 皿as y s t e m ) 。假定该天线系统 由n 个窄的波束组成，那么每个波束将覆盖略大于3 6 0 0 n 的角度，每两个相邻 的波束之间会有重叠部分，这样是为了更好地覆盖整个局域网的传输空间，这n 个波束将被分配到m 个扇区当中，每个扇区由连续的幽个窄波束组成。每个 扇区将装备至少一个与其他扇区独立的无线信号收发器，每个收发器负责提供 3 6 0 0 m 方位角度的网络覆盖及信号收发服务。在每个扇区，同一时刻最多只能 有一个终端能够与该扇区的收发器进行通信。在一个扇区中采用多个窄波束天线 而不是一个宽波束天线的原因在于，如果一个扇区只由一个宽波束天线组成，那 么定向天线的主瓣与旁瓣后瓣的功率比会较低，扇区与扇区之间的干扰和冲突会 比较明显，而采用多个窄波束天线的话，每次传输选择信号最强的那个窄波束天 线，这样主瓣与旁瓣后瓣的功率比较高。可以将一个扇区中的多个窄波束天线逻 辑上看作一个天线。 图3 2 展示了一个多波束定向天线系统的例子，它由4 个扇区，1 2 个窄波束 组成。为了便于之后的关于示例场景的叙述，我们将图中的扇区和窄波束按顺时 针进行编号，正上方偏右的扇区( 波束天线) 编为1 号，于是图中的扇区依次为 1 ，2 ，3 ，4 扇区，波束天线依次为1 ，2 ，3 ，1 2 。图3 2 中特别标注了波束 天线2 的覆盖范围，第2 扇区的覆盖角度以及波束天线l l 和波束天线1 2 的重叠 覆盖区域。在图3 2 中，有4 个终端分别记为a 、b 、c 、d ，它们依次位于波束 天线l 、3 、7 、9 的覆盖范围内，其中终端a 、b 在第l 扇区而终端c 、d 在第3 扇区。 第三章采用多波束接入点的无线局域网m a c 协议 i 波束天线2 的i l 覆盖范围 j 慰蹰劁 汤 掣 图3 - 2 一个由4 扇区1 2 波束天线组成的多波束天线系统不例 容易看到，第1 扇区和第3 扇区内分别负载有两个终端，而同时第2 扇区和 第4 扇区负载为0 ，处于休眠状态，在这种情况下，最多只能有2 个终端可以同 时进行通信，但是，因为接入点由4 个扇区组成，所以理论上，同时通信的终端 数上限应该为4 ，也就是说，网络资源并没有被充分地利用。一般来说，终端用 户的位置分布并不均匀，有可能绝大多数终端用户位于少数的扇区覆盖范围之 内，与此同时，其余的扇区只有很少的负载，甚至处于休眠状态，我们将这种情 况命名为扇区负载不均衡问题。扇区负载不均衡问题会导致： 严重的网络不公平性。因为某些终端用户可能会独享一个扇区的所有带宽， 与此同时，更多的用户却可能因为处于同一扇区而只能争夺稀有的传输机 会。而事实上，这些用户是处于一个接入点覆盖范围内的，他们应该享有相 同质量的网络服务。 严重的网络吞吐量下降。假设一个扇区提供的吞吐量上限为l ，那么理论上， 如图3 2 所示的接入点提供的吞吐量上限应该为4 ，但是，当大多数终端用 户集中在少数扇区，而有扇区空置的时候，空置扇区能够提供的吞吐量完全 没有被利用起来，而终端用户拥挤的扇区却又因为过度的竞争而造成有效吞 吐量的减少( 很大部分的时间，信道被用于传输控制信号和处理冲突，而并 没有用于传输上层协议的数据) 。考虑到接入点的波束同步约束，则终端用 户稀少的扇区也会被终端用户拥挤的扇区拖累，而无法充分利用空闲信道资 源。 因此，扇区负载不均衡问题必须得到解决，因为它影响了网络为其用户提供 第三章采用多波束接入点的无线局域网m a c 协议 一个有效的机制替代“扇区旋转 来解决扇区负载不均衡问题，我们将其命名为 “波束划分( b e 锄p a n i t i o n ) ”，该机制能完满地解决绝大部分的扇区不均衡情形。 如图3 5 就是一个波束划分的例子，它解决了图3 4 中描述的扇区不均衡场景， 而这一场景是不能被“扇区旋转 解决的。“波束划分”中，每个扇区所控制的 波束数量并不一定是均匀的，而是根据终端用户的分布情况进行动态的划分，使 得每个扇区对应的终端用户数量尽量地均匀。 区 图3 5 一个用“波束划分”来解决扇区负载不均衡的倒子 为了在实际的局域网当中进行“波束划分”，需要提前做两个工作。首先， 需要一个机制，它应该能够有效地估计每个波束覆盖范围内参与传输竞争的终端 数量( 处于重叠覆盖范围的终端会被重复计数) ，所谓的“有效估计”，不仅仅是 指估计的终端数量较为准确，它还需要较为敏感地察觉终端的动态变化，这些变 化包括包括终端位置的移动，新终端的加入以及某些终端的脱离。在文献( 1 7 ， 2 l ，2 2 ，2 3 ) 当中提出的估计算法能够被借鉴用于“波束划分 机制以实现对每 个波束对应的活跃终端用户数量的动态估计，但是，这些算法要么太过复杂，要 么对终端的动态变化不够敏感。于是本章后文将提出一种简单的终端位置信息管 理机制，它简单且实用，能够有效地解决接入点对终端用户的定位问题。其次， 需要一个严格的数学标准来评估扇区的负载均衡性。令s i 表示扇区i 覆盖范围内 的终端用户数量，令m 表示扇区的总数，则扇区平衡指数b i 定义如下( 它实际 上是借鉴了j a i n 的公平性指数的定义) ： 召，：( 圣盘i m 三s f 2 2 5 第三章采用多波束接入点的无线局域网m a c 协议 题，之后，再提出新的m a c 协议。 第一个问题是非必要推迟问题。我们利用图3 5 中的场景来对这一问题加以 阐述。假定终端b 和c 在同一时刻试图与接入点进行通信，终端b 发送了一个 r t s 给接入点，终端c 与终端b 的距离较近，于是也收到了这个i h s ，根据分 布式协调机制的规定，终端c 必须推迟它的通信，根据它接收到的r t s 更新它 的网络分配向量( n e t 、v o r ka l l o c a t i o nv e c t i d r ，n a 、，) ，在终端b 与接入点通信的整个 过程完成之前保持沉默( k e e ps i l e n t ) 。但是我们注意到，终端b 和c 实际上位 于不同的扇区覆盖范围内，也就是说，逻辑上它们之间不存在竞争关系，它们能 够同时与接入点进行通信。所以我们说终端c 为一个逻辑上与之不存在竞争关 系的传输进行了一个不必要的传输推迟，这一不必要的推迟是8 0 2 1 1 d c f 机制 强加给它的。为了有效地在终端和接入点之间建立多个同时的通信，非必要推迟 问题需要得到妥善的解决。 第二个问题是接收方阻塞问题。还是以图3 5 中的场景来对此问题加以说明。 假定接入点选择了一个波束向终端a 发送信息( 下行链路数据传输) 。接入点会 先向终端a 发送一个定向的r t s ，终端a 收到此r t s ，会回复一个c t s 。但是 终端d 因为没有和a 在一个扇区覆盖范围内，所以没有收到接入点发送的r t s ， 而且它和a 隔得足够远，也没有收到终端a 回复的c t s ，因此，它并不知道在 接入点和终端a 之间有传输正在进行。此时它发送数据，于是向接入点发送i 订s ， 但是显然，因为接入点正在和终端a 通信而无法回复c t s ，则终端d 在收到接 入点发送的c t s 或者达到连续发送r t s 的上限之前，会连续发送多个i 玎s 。我 们将此情况称为接收方阻塞问题。接收方阻塞问题会导致严重的能量浪费和网络 容量的浪费，网络终端会陷于无意义的重复传输当中并阻碍其它的正常网络通 信。 第三个问题是非理想天线问题( a n t e 衄ai m p e r f e c t i o np r o b l 锄) 。波束重叠问 题，旁瓣后瓣问题和多径富余问题可以统称为非理想天线问题，因为它们都是由 于定向天线的非理想性而造成的。若一个终端位于波束重叠区域且这两个波束分 别属于不同的扇区，或者处于多径富余的环境，亦或靠接入点太近而受后瓣问题 影响，在这样的情形下，该终端发送的数据会被接入点的多个扇区的收发器同时 接收到，而多个扇区发送的数据也都会被该终端接收到，我们将这种状况称之为 第三章采用多波束接入点的无线局域网m a c 协议 非理想天线问题。这样的一个终端和多个扇区之间进行传输的情况需要在设计 m a c 协议时被纳入考虑并仔细地加以解决。 最后需要特别提到的是终端的移动问题。因为接入点采用的是多波束天线， 每个终端都是和某一个扇区相互联系的。当一个移动终端从一个扇区移动到另一 个扇区的时候，介质访问控制，尤其是下行链路的介质访问控制会收到影响，因 此，终端的移动问题是不可忽略的。为了解决终端移动对介质访问控制的负面影 响问题，新的m a c 协议需要提供一个高效的位置管理和更新机制。所谓高效， 是指该机制不仅需要能够有效地管理和更新终端的位置信息，而且需要其系统运 行负担足够小，以免影响到正常的网络数据传输。在本章提出的m a c 协议中， 每个终端都需要保存一个叫做位置指示器( 1 0 c a t i o ni n d i c a t o r ) 的数据结构，该数 据结构用以标识此终端当前所属的扇区和波束( 考虑到非理想天线问题，有些终 端所属的扇区或波束可能不止一个) 。位置指示器可以很容易地用m + n 个比特 来实现，其中前m 比特用以指示该终端所在的扇区信息，而后n 个比特用以指 示该终端所在的波束信息。举个例子来说明，例如图3 5 中的终端b ，其位置指 示器应该为o 1 0 0 ，0 0 0 0 1 l o o o o o o 。它表明，终端b 位于第2 扇区，且位于波束 5 和6 的重叠区域。类似的，接入点也需要为它覆盖范围内的每个终端保存波束 位置信息( 不用保存扇区位置信息因为接入点完全清楚其扇区划分信息) ，而当 接入点与某终端通信的时候，终端和接入点都将利用此机会更新位置信息。 3 5 采用多波束接入点无线局域网的m a c 协议 本节将介绍针对采用多波束接入点的无线局域网提出的m a c 协议。 上行链路传输是由接入点发起的。如图3 6 ，它描述了本章提出的m a c 协 议中上行链路传输的时间结构。一个上行链路超帧开始于上行传输发起周期t o ， 接入点在t o 时间内按波束依次发送r t r ( r e a d yt or e c e i v e ) 消息，每个波束发送 的i 汀r 消息里面都包含了该波束所在的扇区号和该波束的编号，也包含了一个 时间信息，该时间信息会告诉接收到该r t r 的终端需要等到多长时间t o 才会结 束，终端才能开始退避计数。接入点按序发送i h r 而不是同时发送的原因是， 如果所有波束同时传输r t r ，一是每个扇区只有一个收发器，无法使每个波束 发送的r t r 带自己的波束号，二是处于波束重叠区域或者多径富余区域的终端 会因为同时收到多个i h r 消息而无法分辨清楚其中任何一个单一i 珂r 消息的内 第三章采用多波束接入点的无线局域网m a c 协议 容。一旦接收到r t r 消息，每个终端都将根据r t r 消息里附带的波束信息更新 自己的位置指示器。需要注意的是，由于非理想天线问题，某些终端可能会收到 多个r t r 。 如图3 6 所示，在更新位置指示器之后，在竞争周期t l 时间内，有数据需 要发送的终端将通过退避之后发送r t s ( r e q u e s tt os e n d ) 消息来竞争信道接入的机 会。与i e e e 8 0 2 1 1 里的r t s 不同，这里的终端发送的r t s 包含了发送者的位置 指示器，因此我们称这里的r t s 为带标签的r t s ( 1 a b l e dr t s ) 。当一个终端接 收到另一个终端发送的i h s 之后，它取出接收到的r t s 中包含的发送者位置指 示器的前m 位( 即发送者的扇区位置信息) ，与自己的扇区位置信息做一个按位 与( b i t 、) l ，i s ea n d ) 运算以检查它与发送者之间是否存在冲突( 即是否在竞争同一 个扇区) 。如果结果不为o ( m 位不全为0 ) ，则表示存在冲突，它将停止退避计 数，推迟自己的r t s 发送，保持沉默直至信道空闲d i f s ( d i s t r i b u t e di n t e rf r a n l e s p a c e ) 时间才能重新开始退避；反之，表示不存在冲突，它将忽视此i 玎s ，继 续退避计数。通过这样的处理，非必要推迟问题得以解决。当接入点接收到一个 i 汀s 时，它将根据i 玎s 里面包含的位置指示器来更新自己保存的该r t s 发送者 的波束位置信息，不同于i e e e 8 0 2 1 1 ，接入点并不立即回复c t s ，考虑到波束 同步约束，它将一直保持接收状态直到竞争周期t l 结束( 若接入点在收到一个 r t s 后就立即回复c t s ，它就需要在发送状态和接收状态之间频繁转换，导致某 些r t s 无法收到，影响信道竞争的最终结果) 。正如之前提到的那样，如果一个 终端接收到与之存在竞争关系的终端发送的r t s 消息，它不用像d c f 里面要求 的那样设置自己的网络分配向量( n a v ) ，只需要保持沉默停止退避直至信道空 闲d i f s 时间，之后即可以继续它们的退避，如果退避计数到0 ，则发送i h s 而 不用管之前是否已有处于同一扇区的终端发送过i 玎s 。已经发送过i 玎s 的终端 不用等待接入点回复c t s 因为接入点并不会立即回复c t s ，按照d c f ，终端会 在等待一段时间之后重传r t s ，而该r t s 实际上是多余的，因此在我们的协议里， 它只需要保持沉默即可。事实上，t l 周期并不仅仅扮演一个竞争解决周期的角 色，它同时可被看作是接入点的波束位置信息更新周期。在竞争周期t i 结束前， 接入点将按扇区依次回复c t s 以通知每个扇区内竞争成功的终端。如果某个扇 区有至少一个i 玎s 被正确地接收到，那么该扇区回复的c t s 将通知最先正确收 第三章采用多波束接入点的无线局域网m a c 协议 到的i 玎s 发送者，让它准备在数据发送周期t 2 发送数据，而该扇区内其它所有 终端则需要设置自己的网络分配向量，保持沉默直至当前超帧( s u p e r - 触) 结 束。若某个扇区并没有收到任何正确的r t s 消息，它也会回复一个c t s ，以通 知该扇区内的所有终端保持沉默直至当前超帧结束。 在并行数据传输周期t 2 ，所有竞争成功的终端将同时向接入点发送它们的 数据，而在依次确认周期t 3 ，接入点将按扇区依次回复a c k 以确认数据的成功 传输，采用依次传输而不是同时传输的原因同r t r 的传输相同，是为了避免受 非理想天线问题影响的节点同时收到多个消息而无法正确解读其中任何一个消 息。至此，一个上行链路的超帧结束。 叫山 卜里一_ 胍l c 嚣n | 裂f ；e 黑 u p l i n ks u p e r - f r 锄 图3 6 上行链路传输的超帧时间结构 下行链路传输的超帧时间结构类似于图3 6 。下行链路传输亦开始于接入点 发送r t r 。实际上每一个超帧均始于接入点发送r t r ，而在接入点发送r t r 的 时候，该超帧到底是进行上行链路传输还是进行下行链路传输还没有被确定，决 定这一点的是在t l 时间的竞争，若接入点有数据发送给终端，则它会加入竞争， 且它会比终端具有更高的优先级，即它拥有更小的竞争窗口( c o n t e n t i o nw i n d o w ， c w ) ( 或者，接入点的竞争窗口大小根据待传输的下行数据的多少动态调整) 。 如果接入点先退避计数至o 并发送l h s ( 全向模式的i 玎s ) ，则代表该超帧会进行 下行链路传输。此时，接入点将根据它保存波束位置信息，先尽可能地选择多个 相互不冲突( 即处于不同扇区) 的接收终端，接着再按扇区依次发送l 玎s 以通 知所选的终端，让它们准备接收信息。如果有所选的终端同时处于多个扇区以内， 则接入点不会在这多个扇区内再选择其它的接收终端，也就是说，在这个下行链 路超帧里面，该终端会同时占据多个扇区。被选择的终端如果接收到接入点发送 的i 玎s 信息，就会统一时刻回复c t s 。如果某终端由于移动，电源关闭或者与 所在的局域网脱离而造成接入点为该终端保存的波束位置信息不准确，那么就会 产生“未命中( m i s sl l i t ) ”问题，这时，就不会有相应的c t s 回复到接入点的相 应扇区，也就是说该下行传输没有被成功建立。之后，如同上行链路传输一样， 3 0 第三章采用多波束接入点的无线局域网m a c 协议 会有多个同时的数据传输，但不同于上行链路传输的是，终端a c k 的回复可以 同时进行。 还有几点需要特别加以补充说明。 第一，在上行链路传输中，如果一个终端处于受非理想天线问题影响的区域， 它发送的r t s 可能会被多个扇区的收发器接收到，那么，当且仅当该r t s 在这 多个扇区内均最先被成功地接收，该终端才会获得传输数据的机会，否则，该终 端就不能在此超帧传输数据，扇区会选择除它之外最先成功向它发送r t s 的终 端回复c t s 。 第二，在两个连续的超帧之间，将视需要保留一段时间( 该时间长短由接入 点来决定) ，这个时间会被用作“波束划分 和“未命中修正( m i s sh i tc o r r e c t i o n ) ”。 如果当前的扇区负载不是处于最均衡的状况( 根据接入点的波束位置信息来计 算) ，那么接入点将重新进行“波束划分 来平衡扇区的负载。如果在某个下行 链路传输中发生了某终端“未命中 问题，那么，接入点将先删除此终端对应的 波束位置信息条目，在此下行链路传输过程结束后，接入点会发送一个全向的探 测信息( p r o b e ) ，尝试找回发生“未命中 问题终端的新位置信息。如果能够收 到该终端的回复，则接入点将为此终端添加一条新的波束位置信息条目。 第三，考虑到终端可能在接入点未知的情况下离开网络或者关闭电源，协议 将为接入点内保存的波束位置信息的每个条目( 对应每个终端) 添加一个寿命计 数器( 1 i f e t i m ec o u n t e r ) 。当新条目加入或者某个条目被更新的时候，其对应的寿 命计数器将被重置为最大值，而这些寿命计数器将随着时间的流逝而逐步减少， 当某个条目的寿命计数器减少为o 的时候，接入点视对应终端发生了“未命中 并进行等同的处理( 即先删除此条目，再在当前超帧结束后发起“未命中修正 尝试找回对应终端的新波束位置) 。 3 6 仿真实验及结果 首先演示扇区负