（通信与信息系统专业论文）基于80211mac的多跳无线网络缓存管理机制研究.pdf

摘要 f 1 1 1 1 111i il lj i i l l l l ij i i rplfl y 2 0 6 7 9 0 0 无线多跳网状网作为一种极具吸引力的组网形式，由于其自配置、低成本、 鲁棒性强、高容量、可扩展等特点，受到学术界和产业界的青睐，可广泛用于公 共安防系统、宽带无线接入、异构无线回程等方面。 本文针对无线多跳网络中长跳流的“饥饿 现象，分析了8 0 2 1 1 媒质接入控 制协议及弃尾机制对这一不公平性的影响，提出了一种公平性缓存管理算法及其 增强型算法，通过缓存份额的初始化分配、缓存空间的动态使用和缓存份额的周 期性调整保证长跳业务的公平性；通过分组的概率性接纳机制提升重负载时长跳 流的吞吐量性能。 本文论证了算法的正确性和有效性，在该算法提供公平性保证机制的基础上， 采用基于冲突域的吞吐量分析方法对无线多跳网络中的端到端吞吐量理论值进行 研究，并与仿真结果进行对照：采用经典的公平性指数对不同算法的公平性进行 评估，使用网络仿真平台o p n e t 对算法的性能和有效性进行仿真验证。 关键字：m e s h 多跳无线公平性缓存管理 a b s t r a c t u u et 0i t s s e l f o n f i g u r a t i o n ，l o wi n s t a l l a t i o na n dm a i n t e n a n c ec o s l s ，r o b u s 雠s s m g t ls y s t 伽c 印a c i t y , e a s eo fd e p l o y m e n ta n de x p a n s i b i l i t y , w n l e s sm e s hn e 咖r k ( 帆删t c c h o l o g ) ，i sa l la t t r a c t i v en e t w o r ka r c h i t e c t u r e a n d 咖n gi i l c r e 痂g a 淝m l o i l ，w h i c hi sw i d e l yu s e di n p u b l i cs a f e t ya n ds e c u r i 够s y s t e m s ，b r o a d b a n d 聊r e l e s si n t e m e ta c c e s sa n dh e t e r o g e n e o u sb a c k h a u l n e t w o r k sa n ds o0 n i nm u l t i h o pw i r e l e s sn e t w o r k s ，f l o w ss p a n n i n g m u l t i p l eh o p ss u 船r 盘o md i s m 甜 t t t r o u g h p u tp e r f o n l l 觚c ec o m p a r e dt of l o w st r a v e r s i n gf e w e rh o p s i n 付l i sp 研况w e 锄砒y s e 舭r e a s o i l sf o rt h eu n f a i r n e s sa n ds t a r v a t i o no f l o n gh o pl e n g t hf l o w s ，沁l u d i n g 8 0 2 11m a c p r o t o c o la n di t s d r o pt a i l ”m e c h a n i s m t h e n ，w ep r o p o s ea 鼬b u 毹r m a i l a g e m e n ta l g o r i m m ( f b m a ) a n di t se n h a n c e dv e r s i o n t h i sa l g o r i t h mc a i li m 舯v e a n dp r o t e c tt h et h r o u g h p u tp e r f o r m a n c eo f m u l t i h o pf l o w sb yf a i ra l s s i 鲫e n to f b u 胁 s p a c e ，d y n a m i cu s eo fb u f f e rs p a c e ，t h ep e r i o d i ca d j u s t m e n to fb u 腕r s h 淝a i l dn l e p r o b a b i l i s t i ca c c e p t a n c em e c h a n i s m mt n ep a p e r ，、v ea l s os h o wt h ec o r r e c t n e s sa n dv a l i d i t yo f t h ea 1 9 0 r i t h m f u r t 量l e r m 0 她，耽s t u d yt h ee n d - l _ - - t oe n dt h e o r e t i c a lm a x i m u m t h r o u g h p u ti n 舢i t i h o pw i r e l e s s n e 咖r k sb a s e do nc o l l i s i o nd o m a i n t h et h e o r e t i c a lr e s u l t s a r ev a l i d a t e db ys i m u i a t i o n s ac j a s s l ct l a l r i l e s si n d e xi sa d o p t e dt o e x a c t l yd e s c r i b ea n dq u a n t i t a t i v e l ye v a l u a t em e 协础s sd e g 觥t h a td i f f e r e n ta l g o r i t h m sc a l ls u p p o r t a t l a s t ，t h ep r o p o s e da l g o r i t l l i l l a n di t sp e r f o r m a n c ea r ev a l i d a t e d b ys i m u l a t i o n sr e s u l t sb a s e do no p n e ts i m u l a t i o n p l a t f o r i l l k e y w o r d s ：m e s h m u l t i h o pw i r e l e s sf a i r n e s s b u f i e rm a n a g e m e n t 第一章绪论 第一章绪论 1 1 研究背景 随着无线通信技术的迅速发展和用户业务需求的日益丰富，涌现出各式各样 的无线接入网络，但是没有一种单一的无线接入技术能够满足所有用户的带宽、 覆盖和应用需求，无线局域网和蜂窝移动通信网络等异构网络的融合已经成为必 然趋势。通过异构网络融合，可以使各种无线接入技术构成一个整体，为用户提 供一个高带宽、广覆盖，支持语音、数据和多媒体等多种业务的高性能网络。 无线网状网( w m n ， w i r e l e s sm e s hn e t w o r k ) 1 - 3 】作为一种极具吸引力的组 网形式，由于其自身的高带宽、低成本、鲁棒性强、可扩展等特点，受到学术界 和产业界越来越多的青睐，提供了一条异构网络融合的有效途径，并广泛应用于 无线企业、无线校园、无线城市、公共安防系统、油气田组网、宽带无线接入和 通用无线回程等方面。 1 2 无线m e s h 网简介 所谓无线m e s h 网，是指通信节点之间不是通过传统的“一跳”( o n eh o p ) 方式进行通信，而是通过相邻节点的中继，以多跳的方式进行通信。 按照无线m e s h 网中节点的功能划分，无线m e s h 网由两种类型的节点构成： 网状网路由器和网状网客户端，即m e s h 路由器和m e s h 客户端。除了支持传统无 线路由器的网关和网桥的功能外，m e s h 路由器还具有支持m e s h 组网的路由功能。 m e s h 路由器位置相对固定，具有较低的移动性，m e s h 路由器通过无线的方式连 接，为m e s h 客户端形成m e s h 回程；m e s h 客户端可以是静止的，也可以是移动的 节点；部分具有网关功能的m e s h 路由器通过有线的方式与i n t e m e t 等实现互联。 所以无线m e s h 网也被部分学者形象地称为“空中的互联网( w e b i n t h e s k y ) 【4 】，一个无线m e s h 网应用的场景如图f 1 所示。在该应用场景中，各用户终端通 过无线链路接入m e s h 路由器，无线m e s h 路由器以无线方式接入m e s h 网关，m e s h 以有线方式接入外部网络，最终实现用户的i n t e r a c t 的接入。 2 基于8 0 2 1 l m a c 的多跳无线网络缓存管理机制研究 7 白7 m e s h 客户端 1 2 1 无线m e s h 网架构 图1 1 无线m e s h 网应用示意图 客户端 常见的无线m e s h 网的结构形式主要有三种，分别是基础设施架构、客户端结 构和混合式结构。 1 具有基础设施架构的无线m e s h 网 基础设施网状网拓扑结构示意图如图1 2 所示。 m ，铲 m，一 第一章绪论3 蜂窝网 图1 2 基础设施网状网拓扑结构 m e s h 路由器构成客户端连接网络的基础设施，实线代表有线链接，虚线代表 无线链接。m e s h 路由器通过自配置、自愈合方式形成网状拓扑。通过网关功能， m e s h 路由器可被连入i n t e m e t ；通过m e s h 路由器中网关网桥功能，为传统的客户 端提供骨干网，并且使w m n 与现有的无线网络能够集成工作。a 和b 是带有网 关功能的m e s h 路由器，通过有线的方式接入i n t e r n e t 。c 、d 和e 是带有网关网 桥功能的m e s h 路由器，既可以接入m e s h 客户端，也可以与其他类型接入网，如 蜂窝网、无线局域网集成工作。a 、b 、c 、d 和e 共同构成无线m e s h 骨干网。以 下我们将着重讨论骨干网中的m e s h 路由器，并将其统称为m e s h 节点。 2 客户端结构的无线m e s h 网 客户端结构的无线m e s h 网如图1 3 所示。 客户端结构的无线m e s h 网只由m e s h 客户端构成，不含有m e s h 路由器，提 供客户端之间点对点( p e e rt op e e r ) 的对等通信，即构建a dh o c 网络。在这种客 户端结构的无线m e s h 网中，实现数据包的端到端传输可能需要采用多跳的方式， 通过若干个中间节点。 4基于8 0 2 1 l m a c 的多跳无线网络缓存管理机制研究 端 图1 3 客户端式无线m e s h 网 3 混合式结构的无线m e s h 网 混合式结构的无线m e s h 网如图1 4 所示。 混合式结构的无线m e s h 网是基础设施结构的无线m e s h 网和客户端结构的无 线m e s h 网的结合。m e s h 客户端可以与其他m e s h 客户端构成a dh o e 网络，直接 进行通信，也可以通过m e s h 路由器接入网络。骨干网提供w l a n ( w i r e l e s sl o c a l a r e an e t w o r k ，无线局域网1 、蜂窝网等网络到i n t e m e t 的连接。 蜂窝网 图1 4 混合式无线m e s h 第一章绪论5 1 2 2m e s h 网的特点 无线m e s h 网具有许多独特的优势1 5 刊，具体特点如下： 第一，广覆盖。在无线网状网中，由于节点间距很短，每个节点只需要保持 较低的发射功率就可以建立连接。同时，较短的节点间距也意味着传输受到障碍 物阻挡的可能性降低，便于采用视距或者准视距传输。对于网络边缘地区和因障 碍物阻挡形成的通信盲区，无线网状网都可以提供充足的覆盖率。 第二，可靠性和鲁棒性。在传统的点对多点网络中，节点的接入采用了星型 结构，即多个节点首先接入到一个中心点，再由中心点接入到网络中。这样，若 其中一个节点出现故障，特别是中心节点出现了故障将会影响到整个网络的正常 工作，因而这种网络结构的可靠性得不到很好的保证。为了提高网络的可靠性， 目前的点对多点网络中也采用了一些保护措施。例如，为主链路配置后备链路， 此方法虽然简单，但是每条链路都需要配备有两个独立的链路和一个保护交换， 而且同时只能有一个通道用于业务的传送，大大降低了带宽的使用效率。而在无 线网状网中，链路构成网状结构，每个节点可使用的链路数大大增加，且每个网 络节点都具有链路功能，如果其中的某一条链路出现故障，节点便可以自动接入 到其他可选链路，因而网络的l 可霹性和鲁棒性有了很大程度的提高。 第三，自配置能力。无线网状网是一种自组织网，不需要或者需要很少的人 工干预配置网络。因而，网络能够自动判断并更新网络相关配置，增加新的装置 或者重新定位现有装置，简单易行。如果节点间距太远，只要增加一个或几个中 转节点就可以填补网络中的空隙。 第四，成本较低，部署方便。在蜂窝通信系统中，基站的选址是一个复杂的 问题。首先，基站的天线要有足够的高度，使得大部分用户不被障碍物阻挡；其 次，相邻小区之间的基站要保持合适的距离，以减少相互干扰；再次，基站所在 位置要有合适的通道连接到骨干网上，尤其是采用微小区、微微小区来增加系统 容量时，基站数目的急剧增加将使这一问题更加复杂。在无线网状网中，由于采 用无线多跳的回程方式，接入点的选择更具灵活性，接入点可以安装在路灯、交 通灯和道路两侧的建筑物外壁等。每个节点都有多条路由可供选择，局部网络的 维护或升级不会影响网络整体的运行。 第五，使用多接口多信道，提升网络容量。在w l a n 单信道网络环境下，由 于对共享信道的竞争，邻近区域禁止两个节点的并发传输，从而造成单信道情况 下多跳连接的带宽大幅度下降。为解决这一问题，无线网状网中的节点采用了多 接口多信道配置，相邻区域内的无线链路使用的是不同的正交信道，减轻了射频 信号问的干扰，增大了系统容量。 第六，m e s h 路由器的移动性较低，网络拓扑结构相对稳定：供电方式，有稳 6 基于8 0 2 i l m a c 的多跳无线网络缓存管理机制研究 定的电源供应。 1 2 3 无线m e s h 网的与其类型网络的区别 无线m e s h 网络虽然类似于a dh o e 网络1 7 1 ，二者均具有多跳转发分组的能力和 自组织、自配置的能力，但二者还是有明显区别。 无线m e s h 路由器位置相对固定，移动性小，且可以直接连接电源，不受能量 限制，因此拓扑结构相对稳定。仅在节点因故障失效、节点因例行维护或升级而 关闭和新节点引入等情况下发生改变；如何降低每比特能耗和电池的容量问题【8 9 1 是困扰a dh o e 网络应用的重要瓶颈，a dh o e 网络拓扑结构更加多变，由此也带来 路由的多变性和路由协议的复杂性。 虽然无线m e s h 网络与a dh o e 网络均可由对等( p e e rt op e e r ) 节点通信形成自 组织网络，但是无线m e s h 网络的基础设施架构组网形式能够为对等节点的通信提 供骨干网连接，由无线m e s h 路由器提供路由功能，提供大范围的信号覆盖和连接 性；a dh o e 网络只能由端节点提供路由和配置功能，端节点负荷较重，通信能力 相对逊色，网络的可靠性依赖于每个不可靠的端节点的支持。 无线m e s h 路由器可以配备多个射频卡，各个射频卡之间使用不交叠的频段， 虽然同时使用多个射频卡会存在干扰，但多信道的引入仍然可以大大增加网络容 量；而a dh o e 网络使用同一个信道来执行路由和配置功能、信令交互、数据传输， 因此网络性能较低。 流量模式不同。无线m e s h 网络流量分布在m e s h 网关和无线m e s h 路由器之 间，且集中于部分连接到m e s h 网关的路径上，而a dh o e 网络中，任意客户端之 间都可能存在流量分布。 无线m e s h 网络与无线局域网( w l a n ) 均可使用i e e e8 0 2 1 1 系列的媒质接 入控制协议( m a c ，m e d i aa c c e s sc o n t r 0 1 ) ，接入方式类似，单跳传输能力的计 算方式相近，但是二者仍存在显著差别。 无线m e s h 网络与无线局域网( w l a n ) 的主要区别在于，无线m e s h 网支持 多跳传输，每一跳采用视距或者准视距传输，通过多跳转发实现覆盖范围的扩展； w l a n 采用点对多点( p o i n tt om u l t i p l ep o i n t s ) 星型拓扑结构，以“一跳 的方式通 过无线接入点( a p ，a c c e s sp o i n t ) 接入因特网，因而数据不可转发，通常只能提 供几百米范围内的高数据速率服务，覆盖范围较低。 1 3 无线m e s h 网络面临的主要挑战 由于无线m e s h 网络多跳转发特性和无线信道内在固有的复杂性、时变性以及 媒质接入控制协议( m a c 协议) 的局限性，无线网状网也存在一些缺陷。 第一章绪论 7 从技术角度看，面临的主要问题【3 j 有多信道分配、m a c 协议、干扰控制、路 由判据、路由发现和维护、跨层设计、容量和安全性保障等；从满足用户体验和 保证服务质量( q o s ，q u a l i t yo fs e r v i c e ) 的角度讲，面对的主要挑战有多跳时延 的增加和端到端吞吐量的公平性问题。本文针对端到端吞吐量的公平性问题，提 出一种基于现有的8 0 2 1 1m a c 协议的公平性缓存管理方案，显著提升不同流端到 端吞吐量性能的公平性。 所谓端到端的公平性问题，是指在无线多跳网络( 典型的如无线m e s h 网络) 中，由于各节点地理位置的不同、距离网关节点的远近不同，其分组到达网关节 点所经过的跳数有所不同，由此引发的跳数越多的流，其端到端吞吐量越低，跳 数越少的流，其端到端吞吐量越大。端到端的公平性问题的成因将在第二章中进 行详细分析。 1 4 当前研究现状 在无线m e s h 网络中，节点的流量可以分为节点自身的流量和转发的流量两部 分。在现有的8 0 2 1 1m a c 层协议d c f ( d i s t r i b u t e dc o o m i n a t i o nf u n c t i o n ，分布式 协调功能) 机制下，中继流需要在源节点竞争无线资源成功后才能够达到下一跳 节点，而自身流只需要在节点内部生成并立即进入缓存中等待发送。因此，当网 络负载较重时，自身流的到达速率要远远大于中转流的到达率。 “” 当前主流的链路层缓存接纳机制为“弃尾”( d r o pt a i l ) 机制，即按照“先到 达先服务 ( f c f s ，f i r s tc o m ef i r s ts e r v i c e ) 的方式，按照分组到达的先后顺序 将分组接纳进缓存队列，一旦缓存队满，则丢弃之后到达的分组，不考虑该分组 所经过的跳数。“弃尾机制在一跳网络中简单有效，因而得到广泛应用，但是 无法适应无线多跳网络中多跳转发的新需求。距离网关节点较远的节点在传输路 径上由于中转节点队满而持续丢包，从而造成长跳业务的“饥饿”现象。 随机早期检测机制( r e d ，r a n d o me a r l yd e t e c t i o n ) i lo j 用于避免网络拥塞的 发生，也不针对流的端到端公平性问题。 这一公平性问题在2 0 0 3 年文献 1 1 】中首次得到阐述，并提出了基于m a c 层 缓存与网络层流量相匹配的解决方案。 d e e p t is n a n d i r a j u ，d a v ec a v a l c a n t i 等人【1 2 j 提出一种多跳网网络中队列管理 算法( q m m n ，q u e u em a n a g e m e n t i nm u l t i h o pn e t w o r k s ) ，该方法针对多跳网络 中的不公平性，在中转节点为各个源节点平均分配缓存，每个源节点分配到的缓 存份额为f a i rs h a r e ，以保证多跳远程业务的公平性；通过f a i rs h a r e 的动态调整， 期望能够始终满足节点的业务需求，即期望实现缓存份额f a i rs h a r e 曲线和该节点 实际占有缓存曲线的高度拟合。d r n a v e e nc h i l a m k u r t i 等人【l3 】在2 0 1 0 年撰文指出， “期望实现缓存份额f a i rs h a r e 曲线和该节点实际占有缓存曲线的高度拟合”是不 基于8 0 2 i i m a c 的多跳无线网络缓存管理机制研究 现实的，随着时间的推移，缓存份额f a i r s h a r e 曲线随时间呈指数递减，逐步降低 到0 。文中提出了一种增强型的q m 烈( e q m m n ，e n h a n c e dq u e u em a n a g e m e n ti n m u l t i h o pn e t w o r k s ) 算法，区分t c p ( t r a n s m i s s i o nc o m r o lp r o t o c o l ，传输控制协 议) 业务和u d p ( u s ed a t a g r a mp r o t o c o l ，用户数据包协议) 业务，提高了不同传 输层协议业务间的公平性问题。 m o h a m e da k a l i l 等人在2 0 0 8 年提出一种基于双队列的缓存管理方法1 1 4 j ，将 业务分为短跳和长跳两个等级，当已用缓存总数超出一定值后，长跳业务以概率1 接纳，短跳业务按照一定的概率( 小于1 ) 接收。此方法基于跳数的业务等级划分 方法稍显粗略，在文献【1 5 】中，m o h a m e da 蹦i l 等人进一步根据跳数将业务细分 为四个等级，每一等级都有明确定义且对应一个缓存子队列，用以提升公平性。 现有的公平性提升机制中，大多是基于各源节点产生相同或相似的业务负载 这一假设，采用缓存份额平均分配的方式，保证长跳业务得到公平性对待，不能 灵活应对不同源节点产生不同的业务负载的情形。另外，现有的研究中，大多是 通过端到端吞吐量的仿真结果直观地表现公平性获得的提升，缺乏严谨的公平性 指数表述和计算。 1 5 本文t 要研究内容 本文主要分为以下几部分内容： 第一章，首先介绍研究背景；其次介绍无线m e s h 网的架构、特点和与其他类 型网络的区别；最后简要分析无线m e s h 网面临的挑战，提出本文主要解决的问题。 第二章，主要对无线m e s h 多跳网络中的公平性问题进行分析。首先，对现网 存在的公平性问题，即长跳业务被“饿死 的现象进行描述和分析。其次，研究 公平性问题的成因，包括8 0 2 1 lm a c 层的d c f 协议、隐藏终端和暴露终端问题 以及数据链路层缓存管理机制的影响。 第三章，主要内容为针对现网存在的公平性问题提出的解决方案。首先，详 细介绍公平性缓存管理算法及其增强。其次，对该算法能够提供公平性保证机制 进行正确性和有效性分析，并采用基于冲突域的方法对无线m e s h 多跳网络端到端 吞吐量进行理论分析。最后，研究如何定量地准确表述公平程度。 第四章，主要内容为算法的仿真验证和性能分析。 第二章多跳公平性问题分析和研究 9 第二章多跳公平性问题分析和研究 无线m e s h 网，作为宽带无线接入和回传的关键部分，不仅仅是对现网的强有 力补充，甚至可能成为与有线网络并驾齐驱、分庭抗礼的网络组织形式，一个重 要前提是无线m e s h 同样能够实现网运营级的网络品质，迫切需要解决的一个难题 是实现端到端吞吐量的公平性。 所谓公平性，一是端到端吞吐量绝对数值上的公平性，二是投递率的公平性。 前者适用于各源节点业务产生速率相同时，后者定义为成功投递的分组数目与投 递分组总数的比值，体现的是用户获得的吞吐量与用户需求的匹配程度。 2 1 问题描述 在无线m e s h 网多跳网络中，一般来说，各m e s h 节点产生相似n , _ l k 务负载时， 来自距离网关节点较远的业务流只能获很小的端到端吞吐量，而距离网关节点较 近的业务流可以获得比较理想的端到端吞叶帚。由此，导致的严荦问题是远稃、l k 务的“饥饿 现象，即端到端吞吐量的不公平性，如下图2 1 所示。 n o d e 2n o d e lg w 图2 1 问题描述不意图 图2 1 中，n o d e l 和2 为两个无线路由器，称为m e s h 节点，通过多跳的方式 接x n 关节点g w ，网关以有线方式接入外部网络。每个m e s h 节点注入网络的业 务量为g ，随着注入网络业务量的增加，当网络负载较轻时，各流的端到端吞吐 量增加；当业务负荷增长到一定值后，随着业务量的继续增加，长跳业务和短跳 业务的吞吐量性能出现分化，流s 2 的吞吐量逐渐降低，甚至为零，如下图2 2 和 图2 3 所示。 1 0 基于8 0 2 1 1 m a c 的多跳无线网络缓存管理机制研究 图2 2 理想情形 图2 3 “饥饿”问题示意图 分析其原因，主要有以下几个方面： 第一，m a c 层的信道争用机制； 第二，隐藏终端和暴露终端问题； 第三，分组接纳的“弃尾”机制影响。 详细分析见2 2 节。 2 2 问题分析 本节对导致端到端吞吐量不公平性的几个因素进行详细分析，并对部分分析 通过仿真进行验证。 第二章多跳公平性问题分析和研究 2 2 i8 0 2 11m a c 机制对公平性的影响 目前，应用于无线m e s h 网络的主流m a c 协议是i e e e8 0 2 1 1 系列的m a c 协议，本小节将对i e e e8 0 2 1l bd c f 进行简单介绍，并论述d c f 对多跳公平性带 来的影响。 i e e e8 0 2 1l bd c f 是8 0 2 1 1 标准委员会制定的无线局域网( w l a n ) 信道接 入标准f 阍，其设计初衷是应用于单跳网络无线终端接入无线接入点( a p ) 。 2 2 1 1 帧间间隔类型 在i e e e8 0 2 1 1 协议中，通过定义不同长度的帧间间隔i f s ( i n t e r f r a m es p a c e ) 来体现对介质访问的优先级，在d c f 机制中共有三种帧间间隔，分别为：短帧帧 问间隔( s i f s ，s h o r ti n t e r f r a m es p a c e ) 、d c f 帧间间隔( d i f s ，d c fi n t e r f r a m es p a c e ) 和扩展帧间间隔( e i f s ，e x t e n d e di n t e r f r a m es p a c e ) ，并且有s i f s d i f s e i f s 。 s i f s ，持续时间最短，与必须等待较长时间才能传输的帧相比，s i f s 消失后 即可进行传输的帧的优先级较高，例如r t s c t s ( r e q u e s t t os e n d c l e a rt os e n d ， 请求发送清除发送) 和a c k ( a c k n o w l e d g e ，应答) 帧。一旦发送出第一个帧， 该工作站就会取得信道的控制权，媒介即处于十f ：碌状态。后续帧及其确认帧均可 使用s i f s ，以锁定信道不被其他工作站抢用，直到该工作站发送完毕。 d i f s ，是竞争式服务中最短的媒介闲置时间。源节点发送数据帧前必须先侦 听信道，如果信道保持空闲状态的时间达到d i f s 时长，那么该节点才可以发送数 据或者进入退避过程。 e i f s ，并非固定的时间间隔，只有在帧传输出现错误时才会用到e i f s 。当物 理层通知m a c 层，由于所发送帧的帧检验序列值不正确而不能被正确接收时，该 节点发送帧之前侦听信道空闲时间必须至少超过e i f s 。一旦m a c 帧成功接收， 节点将恢复使用d i f s 。 2 2 1 2 介质访问模式 i e e e8 0 2 11 b 分布式协调功能d c f 包含两种介质访问模式：基本接入方式 ( b a s i ca c c e s sm e t h o d ) 和r t s c t s 接入方式，后者为可选机制。 基本接入方式如图2 4 所示，需要发送数据的源节点首先检测信道是否空闲， 如果信道空闲，且空闲时间的长度达到d i f s ，那么它就立即发送数据帧d a t a ； 如果发现信道忙，那么发送节点继续侦听信道，直到信道变为空闲状态，一旦信 道变为空闲，则节点继续侦听信道，若空闲时间达d i f s ，则进入随机退避阶段， 当退避计数器递减到零后，源节点发送数据帧d a t a ；目的节点接收到该d a t a 帧后，首先等待s i f s 时间，然后回复a c k 进行应答。 1 2 基于8 0 2 i i m a c 的多跳无线网络缓存管理机制研究 图2 4 基本接入方式 r t s c t s 接入方式如图2 5 所示，源节点检测到信道空闲时间达d i f s 后，随 机退避一段时间，然后发送r t s 帧对信道进行预约，目的节点收到r t s 帧后回复 c t s 帧，发送节点收到c t s 后，才开始发送数据帧d a t a ，最后目的节点再回复 a c k 进行确认。 图2 5r t s c t s 接入方式 由于r t s 帧较短，其冲突对网络性能造成的损害远远小于数据帧之间的冲突 所造成的损害，特别是数据帧长度远大于r t s 帧长时，采用r t s c t s 访问模式可 以减少碰撞，提高网络性能。但是当数据帧长度比较小时，采用r t s c t s 访问模 式可能带来网络性能的下降，而基本访问模式可以减小由于发送控制帧所带来的 额外开销。 在传统的w i f i ( w i r e l e s sf i d e l i t y ，无线高保真) 网络中，基于一跳的媒质接 入方式可以认为能够获得相对较好的m a c 层公平性【1 1 1 ，但是在无线多跳网络中， 多跳转发的媒质接入方式意味着长跳业务需要经历多次信道争用，遭受多次d i f s 和随机退避，并遭遇更大的碰撞风险。这些因素都将带来长跳业务流分组到达率 的下降，进而影响其端到端的吞吐量性能。 2 2 1 3 二进制指数退避机制 i e e e8 0 2 1l bd c f 采用了一种基于时隙的动态离散退避算法来减少节点之间 的冲突，一个节点只能在某个时隙开始的时刻发送包，从而避免了用户发送数据 第二章多跳公平性问题分析和研究 的随意性。时隙的大小是这样确定的：若某个工作站在某一个时隙接入媒质，那 么下一个时隙开始时，其他工作站能检测出信道已经转为忙。 工作过程如下：当节点要发送数据时，通过载波侦听机制确定当前的信道状 态，如果信道忙，节点将推迟其发送；直到信道空闲，在一个d i f s 帧时间后，节 点生成一个随机退避时间，进入退避阶段。如果节点本身的退避时间为非零值， 则不允许选择随机退避时间。由于退避窗口时间是由各个节点随机生成的，所以 它们不尽相同，在多个节点同时竞争信道时，该过程可以减少发生碰撞的几率。 具体的退避时长计算公式为： b a c k o f ft i m e = 州丁( r a n d o m ( cw ) ) x as l o t t i m e 式( 2 1 ) 初始窗口值： 窗口指数退避算法： c w = c 既细式( 2 2 ) c w = m i n c w 2 + l ，c )式( 2 3 ) 其中，州丁( ) 表示取整，r a n d o m ( c w ) 是均匀分布在【o ，c 明范围内的随机 数，而竞争窗口c w ( c o n t e n t i o nw i n d o w ) 在【c 胁，c 形懈】之间取值；s l o t t i m e ( 时隙长度) 是物理层所决定的竞争窗口的最小单位。例如，对于直接序列扩频 方式，c 既抽和c 既。分别为3 l 和1 0 2 3 ，一个s l o t t i m e 的长度为2 0 u s 。 当节点侦听到信道持续空闲时间超过一个d i f s 时，节点就进入退避阶段：使 用退避算法选择争用窗口c w 中的某个时隙后，根据该时隙的位置设置一个退避 计时器。若在该时隙时间段内，信道保持空闲，计时器减1 ；若信道忙，则挂起该 退避进程，冻结退避计时器的数值不变，并记录当前值，重新等待信道变为空闲 超过d i f s 后，继续启动退避计时器( 从上次的记录开始减1 ) ，直到计时器的数 值为0 ，开始发送帧。 如果节点出现发送数据失败的情形，该节点就会把当前的竞争窗口值c w 加 倍但不会超过最大竞争窗口c 既。，并重新开始竞争过程，直到数据发送成功或达 到最大竞争窗1 5 1c 既。：数据发送成功后或重传次数超过一定门限值时，竞争窗 c w 变为初始值c 既胁；竞争窗c w 达到最大值后便不再增长。这种机制被称为二 进制指数退避( b i n a r ye x p o n e n t i a lb a c k o f f ) 机制。 指数退避机制设计初衷是为了减少碰撞次数的发生，在业务负载较重的情况 下，短时间尺度内，可能会引起某些节点相对强势、其他弱势节点因为发送失败 1 4 基于$ 0 2 i i m a c 的多跳无线网络缓存管理机制研究 而一再扩大竞争窗口的“马太效应”，但是从较长时间尺度看，在一跳网络中这 种不公平性还不明显。在无线多跳网络中，二进制指数退避可能发生在长跳业务 的任何一跳的转发中，因而具有危害累加效应，对长跳业务的影响就更加明显。 2 2 1 4 载波侦听机制 i e e e8 0 2 1 1 b 的载波侦听机制包括物理载波侦听和虚拟载波侦两种方式。 所谓物理载波侦听机制，是在检测物理载波的基础上实现的，从接收射频或 天线信号检测信号能量或根据接收信号的质量来估计信道的忙闲状态； 所谓虚拟载波侦听机制，是指通过m a c 帧的报头或r t s c t s 方式中的网络 分配矢量( n a v ，n e t w o r k a l l o c a t i o nv e c t o r ) 发布强制使用媒质的预留信息来实现 的。n a v 是一个倒计时的记数器。这种侦听方式的工作机理是：源站将它要占用 信道的时间( 包括目的站发回确认帧所需的时间) 通过r t s c t s 帧或者m a c 帧 的报头通知给所有其他工作站，以使其他工作站在这一段时间都停止发送数据， 从而减少碰撞。“虚拟”指其他工作站并没有侦听信道，而是由于收到了源站的通 知获得信道占用信息，这种效果好像是其他工作站都监听了信道。“源站的通知 是在其m a c 帧首部的第2 个字段“持续时间 中，填入了本数据帧结束后还需要 占用信道多少时间。 n a v 的设置如前图2 5 所示。 i e e e8 0 2 1 l b 的载波侦听机制规定，只要其中任何一种机制检测到信道繁忙， 则认为信道为处于繁忙状态；只有两种机制都检测到信道空闲，才认为信道处于 空闲状态。 2 2 1 5d c f 对多跳公平性的影响总结 综上对8 0 2 1 1m a c 层协议d c f 的描述，这种设计初衷为一跳无线网络的协 议无法适应多跳网络中分组转发的新需求。其中，介质访问模式要求多跳业务多 次争用信道，导致长跳业务分组会遭受更多的竞争、经历更多次的退避、更大的 丢包可能和更大的可能性延时e i f s ；多次转发导致碰撞的可能性增加，引起二进 制指数退避效应累加。这些都将导致长跳业务分组的分组到达率降低，从而影响 其端到端性能，与短程业务相比，长跳业务遭受多跳转发带来的不公平性。 2 2 2 隐藏终端和暴露终端对公平性的影响 隐藏终端和暴露终端问题是影响w l a n 吞吐量性能的重要因烈1 7 1 ，由于无线 m e s h 网络广泛使用与w l a n 相同的i e e e8 0 2 1 l bd c f 协议，因此也同样继承了 这一问题。 第二章多跳公平性问题分析和研究 1 5 2 2 2 1 隐藏终端 所谓隐藏终端，是指这样的一种节点，它在接收节点传输范围之内，而在发 送节点的侦听范围之外。隐藏终端因检测不到发送节点正在发送数据帧，可能向 同样的接收节点发送数据帧，从而造成数据帧在接收节点处发生冲突。 f 图2 6 隐藏终端 ； 如图2 6 所示，节点s 为源节点，节点d 为目的节点，实线圆为节点s 的传 输范围( 为了方便分析，采用同质节点，将节点的传输范围等价于节点的侦听范 围，不影响隐藏终端和暴露终端的定性分析，只要能说明隐臧终端无法侦听到源 节点的信息即可。一般情况下，侦听范围大于传输范围) ，虚线圆为节点d 的传 输范围。节点h 位于节点d 的传输范围之内、源节点s 的传输范围之外，因此无 法侦听到源节点正在向目的节点d 发送数据。此时，节点h 如果向节点d 或者节 点f 发送数据，会造成节点d 处发生碰撞；节点h 即为隐藏终端。 隐藏终端的问题可以通过r t s c t s 四步“握手”机制得到一定程度上的解 决。如上图2 6 所示，源节点s 首先向目的节点d 发送r t s ，目的节点d 回复c t s ， 与此同时，隐藏终端h 因为接收到节点d 发送的c t s 而静默，不会向节点d 或f 发送数据。上述方法的遗留问题是：由于节点f 无法获知节点s 和节点d 的信息， 对节点h 处于静默状态也是一无所知，如果此时节点f 向节点h 发送r t s ，会因 为接收不到节点h 的回复信息而持续重复发送r t s 。 2 2 2 2 暴露终端 所谓暴露终端，是指这样的一种节点，它在发送节点的侦听范围内，而在接 收节点的侦听范围之外。暴露终端因检测到发送节点的数据发送而静默，但因为 它在接收节点的侦听之外，实际上，它的发送不会造成接收节点处的冲突，这引 入了不必要的延迟，降低了信道的使用效率。 1 6基于8 0 2 i i m a c 的多跳无线网络缓存管理机制研究 h 旦 f 、 、 、 l ： h ?f 一， 图2 7 暴露终端问题 如图2 7 所示，节点s 为源节点，节点d 为目的节点，实线圆为节点s 的传 输范围，虚线圆为节点d 的传输范围。节点e 位于源节点s 的传输范围之内、节 点d 的传输范围之外，因此可以侦听到源节点s 正在向目的节点d 发送数据，并 被静默，从而无法向节点f 发送数据；节点e 即为暴露终端。 与隐藏终端不同，暴露终端问题无法通过r t s c t s 的“握手机制加以解 决。假设节点s 向节点d 发送的r t s 可以被节点e 正确接收，节点e 认为并行传 输可以成立，自己可以向节点f 发送数据，便向节点f 发送r t s ，而节点f 回复 的c t s 信息门了点s 发送的d a 7 f a 信息会征节点e 处发生碰撞，造成t 0 - 矗i - oe 尤法 正确解码来自节点f 的c t s ，节点e 和节点f 之间的通信就无法进行。同理，如 果节点f 先发起通信请求，向节点e 发送r t s ，仍会由于节点e 处的碰撞而导致 节点e 无法正确解码该r t s 。 2 2 2 3 仿真验证 本小节通过仿真验证上述的隐藏终端和暴露终端问题。使用的仿真参数如表 2 1 所示： 表2 1 仿真参数列表 分组净荷大小( b y t e ) 1 5 0 0 分组产生速率( p a c k e t s s ) 1 0 0 2 0 0 信道模型自由空间衰落模型 发射功率( d b m ) 5 接收灵敏度( d b m ) 8 3 链路速率( m b p s ) 2 最小值3 1 ，最大值1 0 2 3 竞争窗口配置 ( 物理层采用直接序列扩频) 外部干扰设置 无 第二章多跳公平性问题分析和研究1 7 1 隐藏终端问题验证 仿真拓扑图如图2 6 所示，仿真场景图如下图2 8 和图2 9 所示。图2 8 为对 照场景，其中，节点2 为源节点，分组产生速率为2 0 0 p k t s s ，节点8 1 为目的节点， 用来验证无隐藏终端时的一跳吞吐量，并验证r t s c t s 机制的性能。图2 9 中， 节点1 和节点2 都为源节点，分组产生速率为1 0 0 p k t s s ，节点8 1 为二者共同的目 的节点，节点1 和节点2 二者互为隐藏终端。 图2 8 隐藏终端对照场景 | | 。 i | j | 毒j 一，。，。一 。一车一。一j + ， 图2 9 隐藏终端仿真场景图 图2 1 0 为隐藏终端对照场景下的节点8 1 的吞吐量性能，显示的是采用或不采 用r t s c t s 机制两种情况下的一跳吞吐量，分别为1 5 6 6 m b p s 和1 7 2 m b p s ，通过 后文的3 3 2 小节中单跳吞吐量最大值的理论分析可以看出，该仿真值是符合预期 的。 1 8基于8 0 2 i i m a c 的多跳无线网络缓存管理机制研究 图2 1 0 有无r t s c t s 机制吞吐量比较 图2 1 0 中不使用r t s