（通信与信息系统专业论文）无线个域网中调度策略的研究.pdf

摘要 摘要 随着家庭消费电子应用的普及，高速无线个域网引起越来越多的关注。它以 个人为通信中心，将周围无线设备组成一个自组织网络，满足用户随时随地通信 的需要。高速无线个域网除了需要提供尽可能高的数据传输能力外，由于无线信 道的不可靠性，还必须有灵活有效的资源管理方法，在保证服务质量的前提下， 提高信道资源的利用效率。本文着眼于无线数据网络的机会调度思想，在 8 0 2 1 5 3 m a c 协议基础上，研究适用于个域网的机会主义时隙调度算法以及信道 状态反馈机制。研究成果和主要贡献如下： 首先分析了基于超帧结构的8 0 2 1 5 3 协议的m a c 层标准，它的数据传输特 点以及m a c 协议对调度策略设计的要求；然后概述了分组调度算法的思想和其 主要性能指标，分析总结了无线网络中主要的调度算法。这些对于无线个域网调 度策略的研究具有指导意义。 其次从无线数据网络中的机会调度思想出发，分析其中的效用公平调度策 略，在此基础上，综合考虑了信道状态信息以及用户接入信道的公平性，提出了 w p a n 下一种基于效用公平的时隙调度算法f p t s 。该算法由参数更新模块和资 源分配模块组成。参数更新模块根据调度结果更新控制参数，维护用户的公平性 和自适应的跟踪信道的变化；调度分配模块负责计算每个用户的公平效用权值， 并按照权值向各用户比例分配信道资源。仿真结果表明：所提调度方案能够在保 证系统高吞吐量的前提下，获得比p t s 算法更好的公平性和信道使用效率。 最后，本文研究了调度框架中的信道状态反馈机制。研究分析了无线数据网 络中常见的信道反馈技术，研究比较了无线数据网络下行链路与w p a nm a c 层 用户接入方式特点，表明它们的信道状态信息收集机制有很大区别，无线数据网 络的信道反馈机制并不适用于个域网。本文在8 0 2 1 5 3 m a c 协议基础上提出了 两个可实现的信道状态反馈方案，基于信道时隙分配期c t a 的方案和基于空间 复用的改进方案。它们以付出协议开销代价，获得实时性的信道反馈与空间并行 链路信息，提高了信道资源利用率。 本文的研究基于时分复用的超帧结构m a c 协议，对w l a n 网络以及无线 自组织网络( a dh o c ) 中的调度机制有一定的借鉴意义。 关键词：无线个域网，机会调度，网络吞吐量，超帧，信道状态反馈 a b s t r a c t a b s t r a c t w i t ht h ec o s u n l e re l e c t r o n i c st e c h n o l o g yd e v e l o p e dr a p i d l y , h i g h r a t ew i r e l e s s p e r s o n a la r e an e t w o r k sc a t c hm o r ea n dm o r ea t t e n t i o n w p a n st r e a ta l li n d i v i d u a la s t h ec o m m u n i c a t i o nc e n t e ra n ds a t i s f yu s e r s c o m m u n i c a t i o nd e m a n dw i t ho t h e r s a n y t i m ea n da n y w h e r e w i t l lo r g a n i z i n gt h es u r r o u n d i n gw i r e l e s se q u i p m e n t sa sa s e l f - o r g a n i z a t i o nn e t w o r k w p a nn e e d t oh a v ea v a i l a b l er e s o u r c e sa l l o c a t i o ns c h e m e t op r o t e c t u s e r s q o sa n di m p r o v ec h a n n e lu t i l i z a b l er a t i ob e c a u s eo f t h ec h a n n e ls t a t e v a r y 吨，w h i l ei tp r o v i d e se n o u g hh i g hd a t at r a n s m i s s i o nr a t e i no u rp a p e r , w e f o c u so u rr e s e a r c h o n s u i t a b l e o p p o r t u n i s t i c s c h e d u l i n g s c h e m ea n d c h a n n e l s t a t e - f e e d b a c k s t r a t e g y i n h i g h - r a t ew p a n so nt h eb a c k g r o u n d o f o p p o r t u n i s t i ct h o u g h t o u rm a i nw o r ki sa sf o l l o w s f i r s t l y , w ei n t r o d u c es u p e r f r a m e b a s e d i e e e 8 0 2 15 3m a cp r o t o c o l ，a n d a n a l y s ei t s d a t at r a n s m i s s i o ns p e c i a l t ya n dt h ed e m a n do fs c h e d u l i n gs c h e m e d e s i g n i n g a n dt h e n ，s u m m a r i z es c h e d u l i n gs c h e m ea n di t sp e r f o r m a n c ep a r a m e t e ri n w i r e l e s sn e t w o r k s ，e s p e c i a l l yi nw p a n t h e s ew o r kw i l lh e l pt os c h e d u l i n gs c h e m e d e s i g n i n g s e c o n d l y , b a s e do nt h er e s e a r c ho fo p p o r t u n i s t i cs c h e d u l i n gs c h e m ei nh i g h r a t e w p a n s ，o u rp a p e rp r e s e n t s aa p p l i c a b l e o p p o r t u n i s t i cs c h e d u l i n ga l g o r i t h m f o r w p a n s w en a m e di t f p t s ( f a i rp r o p o r t i o n a lt i m es h a r i n g ) t h ea l g o r i t h m c o n s i d e r st h ec h a n n e ls t a t ev a r y i n ga n du s e rf a i m e s s ，w h i c hc o n s i s t so ft w op a r a m e t e r u p d a t i n gm o d u l e sa n das c h e d u l i n gd e c i s i o nm o d u l e t h ep a r a m e t e ru p d a t i n gm o d u l e s u p d a t e sp a r a m e t e r sa c c o r d i n gt ot h es c h e d u l i n gr e s u l t s ，a n dp r o t e c tu s e rf a i r n e s sa n d t r a c kf a s tc h a n n e lv a r i a t i o n sa d a p t i v e l y ；t h es c h e d u l i n gd e c i s i o nm o d u l ei sr e s p o n s i b l e f o rc o m p u t i n gu t i l i t yv a l u e sa n dd i s t r i b u t i n gc h a n n e lr e s o u r c e sp r o p o r t i o n a l l y a c c o r d i n g t ou t i l i t yv a l u e s s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e d s c h e d u l i n ga l g o r i t h mc a na c h i e v eb e t t e rf a i r n e s sa n dc h a n n e lu t i l i z a b l ee f f i c i e n c yt h a n p t sa l g o r i t h mu n d e rt h ec o n s t r a i n to fh i g hn e t w o r k st h r o u g h p u t i nt h ee n d ，o u rp a p e rd o e ss o m er e s e a r c ha b o u tc h a n n e l s t a t e - f e e d b a c ks t r a t e g y i nn e t w o r k ss y s t e m w ei n t r o d u c ef a m i l i a rc h a n n e l - s t a t e f e e d b a c ks t r a t e g y , c o m p a r e m a c p r o t o c o ld i f f e r e n c e sb e t w e e nw i r e l e s sd a t an e t w o r k sa n dw p a n ，a n dt h i n ko u t t h ec h a n n e l - s t a t e f e e d b a c kt e c h n i q u ei nw i r e l e s sd a t an e t w o r k si sn o ts u i t a b l e t o w p a n w ep r e s e n tt w oa p p l i c a b l ec h a n n e l - s t a t e - f e e d b a c ks c h e m e ，e t a b a s e d i i i a b s t r a c t s c h e m ea n ds p a c ed i v e r s i t y b a s e dc h a n n e l s t a t e - f e e d b a c ks c h e m eo nt h eb a c k g r o u n d o fi e e e 8 0 2 15 3m a c p r o t o c 0 1 t h e yp a yp r o t o c o lc o s to u to ng e t t i n gr e a lt i m e c h a n n e lf e e d b a c ki n f o r m a t i o na n ds p a c ep a r a l l e ll i n k st oi m p r o v ec h a n n e lr e s o u r c e u t i l i z a b l ee f f i c i e n c y o u rr e s e a r c hi sb a s e do ns u p e r f r a m e s t r u c t u r em a cp r o t o c o l ( t d m a ) a n di s u s e df o rr e f e r e n c eb yw l a na n dw i r e l e s sa dh o cn e t w o r k k e yw o r d s ：w p a n ，o p p o r t u n i s t i cs c h e d u l i n g ，n e t w o r k st h r o u g h p u t ，s u p e r f r a m e ， c h a n n e lq u a l i t yf e e d b a c k i v 插图目录 插图目录 图1 - 1 i e e e8 0 2 1 5w p a n 系列简介2 图2 - 1 i e e e8 0 2 1 5 3 微微网5 图2 - 2i e e e8 0 2 1 5 3 超帧结构6 图2 3n o - a c k 机制7 图2 4i m m - a c k 机制7 图2 5d l y a c k 机制7 图2 - 6 分组调度结构9 图2 - 7 考虑信道状态调度的基本模型1 1 图2 - 8 标准算法流程1 5 图2 - 9i r s a 算法流程1 7 图2 - 1 0c b s 算法过程1 9 图2 - 1 1s r p t 算法流程图一2 1 图2 - 1 2s r p t 算法流程图二2 2 图3 1q u a l c o m mh d r 下行链路2 6 图3 - 2 尽力服务模式下a p f 算法的执行图2 8 图3 3 有q o s 需求模式下a p f 算法的执行图2 9 图3 4 总网络吞吐量的比较3 0 图3 - 5 平均链路吞吐量的比较3 l 图3 - 6f p t s 算法模块图3 2 图3 7 总网络吞吐量的比较3 4 图3 - 8 平均链路吞吐量的比较3 5 图3 - 9 算法公平性的比较3 5 图4 - 1 比特映射反馈方案3 8 图4 - 2 混合反馈方案( 5 1 i - h ) 3 8 图4 - 3 混合反馈方案c q i 结构3 8 图4 - 4 基于n a c k 的信道自适应反馈3 9 图4 - 5 有控制中心的下行链路4 0 图4 - 6w p a n 网络结构4 1 图妒7w p a nm a c 层协议4 2 图4 - 8 基于c t a 期的协议改进方案4 3 v t i 插图目录 图4 9 基于空间复用的协议改进方案4 4 v i i i 表格目录 表格目录 表3 - 1 仿真参数3 3 i x 中国科学技术大学学位论文原创- l 生声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：聋& 一 签字日期：塑! 皇垒盘旦生圣 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 回公开口保密( 年) 作者签名： 签字日期： 导师签名：亟! ： 签字日期：垦! 竺皇：鱼：生 第1 章绪论 第1 章绪论 1 1论文研究背景 超宽带( u l t r a - w i d e b a n d ，u w b ) 技术 1 】是一种新兴的短距离高速无线通信 技术。与传统的窄带通信系统相比，u w b 系统通过占用极大的带宽来传输信息， 具有高数据率、低成本、低功耗、低截获率等优势，同时u w b 系统的抗干扰的 能力强。 截至目前，有三种主流的超宽带系统体制：基于脉冲超宽带体制( i r - u w b ) 【2 】、基于直接序列扩频的超宽带体f l ；j j 3 和基于多带o f d m 的超宽带体制。脉冲 无线超宽带通信体制主要使用持续时间极短的脉冲进行数据传输，直接序列扩频 超宽带体制采用直接序列扩频技术调制数据进行传送，多带o f d m 超宽带体制 采用多载波的正交频分复用技术进行数据传输。三种系统体制在数据调制、接收 方法以及实现技术方面有很大的不同，其中以i r - u w b 体制最具特色。i r 系统 采用极短脉冲波形，无载波调制，结构简单，功耗低，时间分辨率高，抗多径能 力强【4 ，5 】。i r u w b 系统可以采用c m o s 工艺实现，成本控制在比较低的水平 上，能够广泛应用于便携式无线通信设备。 高速无线个域i 网( w i r e l e s sp e r s o n a la r e an e t w o r k ，w v a n ) 是u w b 通信技术的 一种典型应用。2 0 0 2 年，i e e e 协会成立标准化工作组i e e e 8 0 2 1 5 3 a ，把u w b 技术作为高速无线个域网的接入方案 6 】。在基于u w b 的高速无线个域网中， u w b 技术提供了一种高速无线数据传输解决方案。针对这种高速组网应用，良 好的m a c 协议的设计也显得非常重要 7 】。优秀的m a c 接入方法可以使网络中 多个用户高效共享物理链路，以获得高网络吞吐量和良好的用户q o s 。m a c 协 议的设计涉及多址信道的分割、接入方式、资源分配策略和控制机制等多方面内 容，需要综合考虑网络的结构、节点的数量、业务的类型与要求以及物理层的限 制等多方面的因素 8 】。 近年来，在国家相关科研计划的支持下，我国积极开展了u w b 技术的研究 工作，在传输方法、关键技术、系统验证等多方面取得了一系列技术成果。中国 科学技术大学也持续开展了u w b 技术的研究工作，并在前期成果技术上，承担 了8 6 3 导向性项目“超宽带s o c 芯片设计和组网实验”。本论文结合该项目中的 超宽带组网实验工作，重点研究了基于i r u w b 的高速个域网的资源调度策略 及其信道反馈机制等问题。 第1 章绪论 1 2 无线个域网组网技术发展 i e e e8 0 2 1 5 是目前w p a n 的主要建议标准【9 】，涉及w p a n 的m a c 层和物 理层技术，也是本论文的工作基础。以下简要介绍i e e e8 0 2 1 5 的研发情况。 i e e e8 0 2 1 5 分为4 个研究小组，从8 0 2 1 5 1 到8 0 2 1 5 4 ，技术分工各有侧 重。组织结构如图1 - 1 所示。 图1 - 1i e e e8 0 2 1 5w p a n 系列简介 从图1 1 可知，8 0 2 1 5 1 标准【9 】实际上就是蓝牙技术的底层技术( m a c 和 p h y 层) 的标准化，蓝牙技术的出现真正意义上促成了w p a n 网络的形成。蓝牙 在刚刚出现之初，由于同8 0 2 1 1 代表的w l a n 网络采用同样的频率段，因此有 可能产生干扰，8 0 2 1 5 2 小组 1 0 1 专门就此问题做了研究并提出了相应的网络共 存模型和共存机制。 8 0 2 1 5 3 1 6 和8 0 2 1 5 4 1 1 1 】同样给出了p h y 和m a c 标准，但走不同应用路 线。8 0 2 1 5 - 3 能在1 0 0 米的距离内，以每秒5 5 m b i t 的速度传输数据，确保经由 无线网络传输的数字内容具有一定的服务水平，主要针对高速数据通讯应用： 8 0 2 1 5 4 则是针对低成本、小功耗、低速率应用的w p a n 标准，l r w p a n 可连 接尚未连网的设备，并且与现有无线标准兼容，广泛应用于工业、农业、媒体、 家庭和医疗等领域。 u w b 技术提供了一种更高速率( 数百m b p s ) 的新的无线传输方法， i e e e 8 0 2 1 5 为此特别设立了i e e e 8 0 2 1 5 3 a 工作组，它以i e e e 8 0 2 1 5 为基础， 2 第l 章绪沦 针对超宽带技术的特点，开发基于u w b 技术的w p a n 应用。 总的看来，i e e e 8 0 2 1 5 将w p a n 分成三种类型，它们的主要区别在于通信 速率、q o s 能力等。8 0 2 1 5 3 是高速率的w p a n 标准，适合于多媒体应用，有较 高的q o s 保证。8 0 2 1 5 1 即蓝牙技术，具有中等速率，适合于从蜂窝电话到p d a 的通信，其q o s 机制适合于话音业务。8 0 2 1 5 4 也就是z i g b e e 技术，目标市场 是工业、家庭以及医学等需要低功耗、低成本无线通信的应用，对数据速率和 q o s 的要求不高。 i e e e 8 0 2 1 5 3 标准为了保证设计的灵活性和兼容性，仅定义了m a c 层和 p h y 层的框架及技术规范，对于在技术上如何实施以及诸如无线资源调度、链 路反馈等算法并未做具体规定，需要开发者自己确定【6 】。目前，基于u w b 的无 线个域网m a c 协议大致分为2 类：分布式u w bm a c 协议 1 2 ，1 3 和集中式u w b m a c 协议。集中式u w bm a c 协议采用分簇的网络结构。每个簇组成一个微微 网( p i c o n e 0 ，并选举出一个中心控制节点( p n c ，p i c o n e tc o o r d i n a t o r ) ，负责统一 管理和分配网络通信资源。协议采用超帧结构，每个超帧以中心控制节点发送的 信标帧( b e a c o n ) 作为起点，而后是竞争接入阶段( c o n t e n t i o na c c e s sp e r i o dc a p ) 和非竞争接入阶段( c h a n n e lt i m ea l l o c a t i o np e r i o dc t a p ) 两个部分，融合了 a l o h a ，c s m a c a ，t d m a 等多种接入方式。本论文主要研究集中式u w bm a c 协议设计中的资源调度问题。 在资源调度中，基于预约的信道使用方式使得预约时刻和实际传输时刻的信 道可能存在很大不同，导致信道资源的浪费。为了适应接收信噪比的动态变化而 采用的自适应调制技术造成了带宽随时隙不均匀分布的问题( b u d t s ， b a n d w i d t hu n e v e nd i s t r i b u t i o nw i t ht i m es l o t ) 【1 4 】，导致对资源使用的公平性产 生影响。此外，在一些特定的应用中，比如移动用户，家庭多媒体用户甚至传感 网节点，需要通过调度来提高能量效率，降低能量开销。因此，研究设计高效灵 活的资源调度机制，对保证用户的q o s ，提高网络的整体性能和信道资源利用率， 具有十分重要意义，也是当前的研究热点之- - 1 5 。 时变的信道状态对调度算法的性能会产生重大影响。本论文从信道状态信息 出发，将机会主义思想应用到个域网的调度中来，并结合用户的q o s 需求，展 开无线个域网资源调度方法以及信道状态反馈机制的研究。 1 3论文的研究内容与结构 本论文主要研究了基于超帧结构的高速个域网的调度机制，比较分析了有控 制中心的下行链路的时隙调度与个域网中资源调度机制的区别，通过引入机会主 义的思想，提出了一种适用于w p a n 的机会调度算法，并仿真分析它的性能。 3 第1 章绪论 同时研究了m a c 协议对信道状态反馈的支持，提出了两个可实现的初步的信道 状态信息反馈方案。本文将围绕这两方面进行展开，章节安排如下： 第一章首先介绍了论文研究背景，对超宽带无线通信技术的特点和几种主要 实现方式进行了简要介绍，说明i r - u w b 技术非常适用于高速w p a n 的应用； 其次简单介绍分析了无线个域网的组网技术m a c 接入协议。最后给出了论文的 章节安排，对本文的主要工作和贡献做了简要介绍。 第二章首先详细介绍了基于超帧结构的8 0 2 1 5 3 协议的m a c 层标准，它的 数据传输特点，分析了m a c 协议对调度策略设计要求；其次，概述了分组调度 算法的思想和其主要性能指标，分析介绍了无线网络中主要的分组调度算法；最 后，具体介绍了无线个域网的调度算法。这些对于无线个域网调度策略的研究具 有指导意义。 第三章研究了适用于高速个域网的机会调度算法。首先介绍了无线数据网络 的机会调度思想，分析了其中的效用公平调度策略。然后在现有个域网中基于信 道状态信息的调度研究基础上，结合信道状态的波动和用户间的公平性，提出了 一种适用于w p a n 的机会主义时隙调度算法f p t s ，并通过仿真比较分析了该算 法与其他算法的吞吐量性能与公平性。 第四章研究了m a c 协议中信道反馈机制。首先介绍分析了无线数据网络中 常见的信道反馈技术，说明信道状态反馈机制对调度算法性能的重要性；其次分 析比较了无线数据网络与w p a nm a c 层用户接入方式的特点，表明它们的信道 状态信息的收集机制有很大区别；最后在原8 0 2 1 5 3 m a c 协议的基础上提出了 两种初步的信道状态反馈方案，并进行简要分析。 第五章总结全文，并对下一步研究进行了展望。 4 第2 章高速无线个域网m a c 协议与资源调度 第2 章高速无线个域网m a c 协议与资源调度 2 1基于超帧结构的m a c 协议 根据应用场景不同，i e e e 将无线个域网的m a c 协议分为低、中、高速三 类【9 】。在高速w p a n 应用中，采用超帧结构的i e e e8 0 2 1 5 3 a 标准【6 】支持采用 u w b 物理层传输技术，是本文研究的基础。下面对i e e e8 0 2 1 5 3 a 中的m a c 协议标准做较为详细的介绍与分析。 2 1 1ie e e 8 0 2 15 3 a m a c 协议介绍 i e e e8 0 2 1 5 3 a 6 1 定义了以微微网( p i c o n e t ) 为单元的网络结构。微微网是 一种单跳无线自组网络，通信覆盖距离在1 0 米左右，它允许一系列独立的数据 设备彼此之间进行数据通信，也就是说所有的数据都是以p e e r - t o p e e r 方式进行 传输。如图2 1 所示，微微网由一般设备( d e v ) 节点和微微网协调控制器( p n c ) 节点组成。p n c 节点是微微网的核心，它负责控制整个微微网的运转，通过信 标实现微微网定时、节点通信、q o s 保护、节点接入控制和节能模式选择。d e v 节点是基本的数据通信设备，它通过向p n c 发送请求来完成接入网络、退出连 接、传输数据等功能。一个p n c 同时也可以是d e v 。 图2 - 1i e e e8 0 2 1 5 3 微微网 m a c 协议的设计采用了超帧结构，希望能提供更快的连接、支持a dh o c 网 络、提供q o s 的数据传输，安全以及有效的数据传输。超帧结构如图2 2 。 5 第2 章高速无线个域网m a c 协议与资源调度 图2 - 2i e e e8 0 2 1 5 3 超帧结构 超帧由以下的三部分组成： 1 ) 信标( b e a c o n ) 信标在超帧的开始阶段由p n c 广播，它携带微微网的控制参数、信道时隙分 配、用户流的相关信息等，主要用来设置时间的分配和传送网络管理信息等。信 标由信标帧组成。 2 ) 竞争接入期( c o n t e n t i o na c c e s sp e r i o d ，c a p ) 竞争接入期的接入方式与无线局域网相似，采用载波侦听多路访问冲突避 免( c s m a c a ) 机制争用信道，不同之处在于8 0 2 1 5 3 中没有虚拟载波侦听， 退避算法也不是二进制指数退避。竞争接入期用于传输d e v 用户的信道时间请 求、修改、终止等命令或是异步数据。 3 ) 信道时隙分配期( c h a n n e lt i m ea l l o c a t i o np e r i o d ，c t a p ) 信道时隙分配期用来传输有q o s 需求的数据流和文件。它由管理信道时间 分配( m c t a ) 和信道时间分配( c t a ) 组成。命令、同步和异步数据都可以在信道 时隙分配期中传输，其中m c t a 只用来进行p n c 节点和d e v 节点的通信。在 开放的m c t a 中，可能会有多个d e v 同时与p n c 通信，此时采用时隙a l o h a 的方式来争用信道，也有人在调度研究中取消m c t a ，让d e v 节点与p n c 节点 的通信在c t a 中进行。c t a 采用的是t d m a 的接入方式，c t a 的时隙长度及 位置由信标帧中的相关信息单元决定，d e v 节点在预先定好的c t a 里传输数据， 可自行决定传输时间长度，但不能超过给定的c t a 时隙长度。由于c t a p 在超 帧中占有的比例很大，超帧的利用率很高，这样能保证网络的吞吐量满足高速应 用的需求。 2 1 2超帧结构m a c 协议的数据传输分析 为了提高数据传输的正确性，增加信道的利用率，i e e e 8 0 2 1 5 3 标准支持数 据帧的分片和重组，以处理来自高层的大数据帧 6 】。对数据帧分片能够减小帧 长，有助于降低边缘连接的丢帧率( f e r ) 。分片后的帧带有上层原数据帧的序号 和分片后的序号和分片总数信息，可以使d e v 节点分配相应内存来接收将来的 6 第2 章高速无线个域网m a c 协议与资源调度 数据帧。研究发现，由于信道是时变的，丢帧率是与信道状况相关的，可以通过 调度自适应的改变分片帧长以提高嘲络的吞吐量性能【1 6 】。 协议规定源d e v 使用a c k 机制来保证数据帧的传送，提供了三种a c k 机 制以适应不同的应用，分别为无确认( n o a c k ) 、立即确认( i m m a c k ) 、延迟确 认( d l y a c k ) 6 。n o - a c k 机制在收到帧后不发送a c k 确认，适于重传帧到达 太迟或上层处理a c k 的情况。i m m a c k 机制指d e v 收到帧后立即发送a c k ， 对每个帧都确认。d l y a c k 机制指源端发送多个帧而不响应a c k ，当源d e v 请 求时，这些帧的a c k 在接收端组成单独的响应帧发出。d l y a c k 机制在减小 i m m - a c k 机制开销的同时，使源d e v 确认了帧发送。若源d e v 在发送后没有 收到相应的a c k 确认，将根据数据类型、重传次数和时间长度等选择重发或丢 弃。如图2 3 、2 4 、2 5 所示，其中，g u a r d 为保护期，s i f s 为帧间传输间隔时 间。 f r a m et r a n s m i s s i o n + s i f s 卜一 c o c ，) o f r a m e3 _ 一c 1 f r a m e1 一 f r a m e2 0 3( ，) a m 0 3 图2 - 3n o a c k 机制 f r a m e + s i f s + a c k + s i f s f r a m e ( d0 3 f r a m e ( 力 ( 玲 f r a m e ( 疗0 3 o 一 - 一c mo1 _ 一 m o m 一啊o 1 天 0 3 2 ( 办 天 v 天 0 3 a 图2 4i m m a c k 机制 f r a m e f r a m e f r a m e o hhh n h c 匐 禹 匐 1 匐 2 匐 u h 盘 图2 - 5d i y - a c k 机制 在通信网络中，如何高效的分配信道资源是实现q o s 的重要保i j e 1 7 ，1 8 。 i e e e 8 0 2 1 5 3 协议在m a c 层采用超帧结构，信道的使用以超帧为单位进行，而超 帧则被划分为固定格式的一系列时间片段。通信过程中，d e v 节点首先向p n c 7 第2 章高速无线个域网m a c 协议与资源调度 节点请求自己的q o s 能否被满足，p n c 根据这些请求检查是否有足够的信道资 源，若有，则分配相应的c t a 。这种d e v 与p n c 之间的基于资源预约的请求 应答机制有效地降低了协议的复杂度和开销，使信道资源达到较好的利用率，提 供了一定的q o s 保障。上述资源预约的时隙分配方法对于恒定比特率( c b r ) 数据的传送比较可靠，但对于可变比特率( v b r ) 的数据，该方法的信道利用率就 很不理想了，虽然可根据数据流的峰值带宽来分配资源，但这样信道利用率就很 差。而对于实时v b r 数据流，在不清楚它的带宽分布的情况下，无法根据峰值 带宽来分配时隙以保证q o s ，尽管可以通过请求应答来提供支持，但是延迟抖动 会很大，不能保证实时传输质量。另一方面，在信道状态波动较大的时候，上述 基于预约的方式对带宽的利用率也会很差。 因此，针对上述问题改进时隙调度方案的设计，使得协议能够保证各个用户 不同q o s ，同时实现网络系统性能的最佳化就显得十分重要。 2 2 无线网络调度算法分析 近年来，无线通信网络获得了广泛的发展与应用，目前的无线接入技术有四 类，分别是无线个域网，无线局域网( w l a n ) ，a dh o e 自组织网络和移动蜂窝 系统中的无线数据网络( 高速下行分组接入系统，h s d p a ) 。它们都需要通过分 组调度在多用户间共享信道资源，实现网络性能的最佳化。本节先从共性角度出 发，概述分组调度算法的基础思想与主要性能指标，然后介绍了四种基础的调度 算法，这些基本概念对无线个域网的调度是同样适用的。 无线数据网络的调度算法分为两类，上行链路的调度和下行链路的调度，其 中，下行链路的机会调度算法得到了广泛深入的研究，从信道时变的角度，取得 了较成熟的研究结果。本节在最后介绍分析了下行链路中经典的考虑信道状态信 息的调度算法，希望能借鉴其思想，设计适用于个域网的考虑信道状态的调度算 法。 2 2 1概述 调度是系统资源管理和网络服务质量控制的核心机制之一，是解决多用户竞 争共享资源问题的有效手段。分组调度实现对链路带宽的管理，它按照一定的规 则来决定分组队列中哪些业务数据以怎样的方式发送，从而使得所有输入用户按 照预定的方式共享链路带宽资源( 信道资源) 【1 9 ，2 0 。 分组调度一般采用c q s 结构( c l a s s i f i c a t i o n , q u e u i n g ，s c h e d u l i n g ) ，如图2 - 6 所示。一个调度器对应多个等待队列，这些队列共享输出链路资源。分组调度算 法通常遵循这样的方式，即从多个等待队列q i ( 0 i 乃 每，彬为此用户的包延迟，互为延迟界，谚为超出它的最大概率。 该算法在网络吞吐量和基站队列所产生的时延抖动之间作了有效折中。用户 信道条件好时，会有更好的q o s ，一般有2 到3 秒的队列时延；然而对信道条件 差的用户，该算法会造成这类用户的数据包在基站端有较大时延，当时延超过用 户的最大容忍时间，数据包就会被抛弃。为了降低抛弃概率，提高用户间的公平 性，需要对吞吐量较低的用户进行补偿。这时，上面的公式修正为： 跏】= 粥 乎 硐 b 【行】 rm 互 ( 2 3 ) 式中，r 【挖】代表用户i 的t i i 平均最大数据速率，m 警 咒】 是一个常量， 其值等于小区中最大的gf n l 。修正公平性后的算法虽然具有良好的公平性，但 是网络吞吐量会有所下降。 和比例公平算法相比，m l w d f 算法具有分组级稳定性，这是因为它在决 策时不但考虑信道质量，而且考虑队列长度，在用户队列长度过长时采取措施， 提高队列的优先权。 2 3无线个域网的主要调度算法 近些年，人们在如何优化基于8 0 2 1 5 3 协议的w p a n 调度算法性能上面做 1 3 第2 章高速无线个域网m a c 协议与资源调度 了许多工作。m u s t a f a 等基于可变比特率的m p e g 视频流提出i r s a ，c b s ， s r p t f s r p t 等时隙调度算法，利用数据流分组携带的网络生存期、队列长度 等信息合理的分配信道资源 3 0 ，31 】；k s u n 提出一种基于反馈的m p e g 流调度 算法f a c t a ，算法利用d e v 周期性的反馈，来实时得出每个超帧分配给d e v 的时隙长度【3 2 】；m o r a d i 等基于m p e g 帧的相关性，引入了f d a 算法，针对数 据流的特性，降低了系统的解码错误概率d f r 3 3 1 ；m i n w a n g 等利用通信设备反 馈给p n c 的信息对带宽资源进行分配 3 4 ，3 5 ；y ht s e n g 等提出对v b r 数据流 的分组大小进行预测从而分配相应的时隙调度算法 3 6 ，3 7 】；a t o r o k 对超帧结构 进行改进，提出一种分层结构来提高系统的性能 3 8 ，3 9 】；l i ux i n 提出了 m e s e s r p t 算法，对信道时隙分配期的m c t a 进行改进 4 0 1 ；e hk w o n 针对信 标丢失造成的信道时隙浪费而进行重分配以提高网络系统性能【4 l 】。这些资源调 度算法的研究都是不依赖于信道状态信息的，它们的缺点是都对信道的变化很敏 感，在信道波动频繁时，算法的性能有很大下降。 8 0 2 1 5 3 协议中对考虑信道状态信息的调度算法研究较少，e c c h o i 依据信 道状态的不同对传输的分组帧长进行调整从而改善信道利用率，提高系统性能 【4 2 】；b s k i m 提出针对信道质量变化在协议支持的五种速率中进行自适应选择 【4 3 ；e n g i nm a s a z a d e 提出了机会主义的信道接入方案p t s ，提高了信道的利用 率和系统的总吞吐量 4 4 ；s u n g d o nj o o 提出了公平接入的调度算法，通过将处 于错误状态的d e v 的c t a 分给其他器件来降低信道资源的浪费，并且通过补偿 策略保护公平性 4 5 】。上述研究工作主要考虑了在调度中使用信道状态等物理层 信息，优化网络的总吞吐量和信道使用效率，对信道状态的变化有很强的适应性， 缺点是没有考虑用户接入信道的公平性，用户的q o s 需求和上层数据流的特性 等情况，导致算法对具体流特性的针对性不强以及算法公平性较差，具有一定的 局限性。下面将分析几种基本的调度算法，他们都不依赖于信道状态，我们将在 第三章中详细研究考虑信道状态的调度算法。 2 3 1标准算法 标准算法( s t a n d a r d ) 【3 1 核心思想基于t d m a 方式。算法首先在各节点用 户流请求时隙时将它们的相关信息保存下来，包括用户流的标识i d 、请求时隙持 续期等，接着依据各用户流完成请求的顺序按照各自请求时隙分配相应的信道资 源，每次完成一个用户时隙分配之前，计算： n - i a l l o q + a l l o c , m a x s u p e r a m e ( 2 4 ) i - i 其中，a l l o c 。为该用户流的请求时隙持续期，m a x s u p e r f r a m e 是最大 超帧长度。若满足该条件，则继续给第n 条用户流分配时隙，否则说明请求时隙 1 4 第2 章高速无线个域网m a c 协议与资源调度 资源超过超帧剩余时隙，网络在本超帧周期不再为该用户流分配资源。标准算法 将所有请求的用户