（信号与信息处理专业论文）交互应用程序的跨层优化.pdf

摘要 由于无线信道的时变特性和衰落特性，以及多媒体服务质量q o s ( q u a l i t yo f s e r v i c e ) 要求的苛求性和多变性。无线多媒体通信是一个充满挑战性的课题。为 了面对这些挑战，一个新的跨层设计( c r o s s - l a y e rd e s i g n ) 概念被提出了。跨层优化 设计基于交互信息在传统协议栈之间的交换，连带地使所有的系统部分都适应 于环境和应用要求的动态变化，而不是像传统的网络设计那样，独立地设计各 个传统的协议层。 本文通过在所有应用之间动态地使用优先级，将已有的跨层框架扩展到延 迟感应应用程序。加权公平队列w f qo v 磷g h t e df a i rq u e = l l i n g ) 是一种模拟流体公 平队列f f q ( f l u i df a i rq u e u i n g ) 的数据包公平队列算法，有保证带宽和限制延迟 的良好特性。基于优先级的加权公平队列p w f q ( p r i o r i t y - b a s e dw e i g h t e df a i r q u e u i n g ) 结合分配权重和优先级，来保证带宽，以及在一个滑动窗内调整延迟的 范围。 关键词：跨层优化，加权公平队列，基于优先级的加权公平队列 a b s t n 矗 w u e l e s sm u l t i m e d i ac o m m t m i c a t i o ni sav e r yc l l a l l e n g i n gt a s kb e c a u s eo ft h e t i m ew 咖a n df a d i n gn a t u r eo ft h ew i r e l e s sc h a n n e la n dt h ed e m a n d i n ga n d v a r y i n g 触t t t yo fs e t v i c e ( q o s ) r e q u i r e m e n t so fm u l t i m e d i as e r v i c e s t oa d d r e s s t h e s e sc h a l l e n g e s , ac r o s s - l a y e rd e s i g nc o n c e p ti sp r o p o s e d c r o s s - l a y e rd e s i g ni s b a s e d0 1 1i n t e r - l a y e ri n f o r m a t i o ne x c h a n g e sa c r o s st h et r a d i t i o n a ll a y e r si nt h e p r o t o c o ls t a c ka n dj o i n t l ya , h p t sa l ls y s t e mp a r t st ot h ed y n a m i c a l l yc h a n g i i l g e l l v i r o n l n t e l l t sa n da p p l i c a t i o nr e q u i r e m e n t si n s t e a do f d e s i g n i n gt h et r a d i t i o n a ll a y e r s i ni s o l a t i o n , a sb e i n gd o n ei nl r a d i t i o n a ln e t w o r kd e s i g n t h i st h e s i se x t e n d so u rc r o s s - l a y e rf r a m e w o r kf o rd e l a ys e n s i t i v ea p p l i c a t i o n sb y u s i n gd y l l a l n i cp r i o r i t ys w i t c h i n ga m o n gt h ea p p l i c a t i o n s w e i g h t e df a i rq u e u i n g o v f q ) i sap a c k e tf a i rq u e u i n ga l g o r i t h mt h a ts i m u l a t e sf l u i df a i rq u e u i n gf f f q ) a n dh a sg o o dp r o p 毹e so fb a n d w i d t hg u a r a n t e ea n db o u n d e dd e l a y p r i o r i t y - b a s e d w e i g h t e df a i rq u e u i n gt r w f q ) c o m b i n e st h ea l l o c a t e dw e i g h tt o a c h i e v et h e b a n d w i d t hg u a r a n t e ea n dt h ep r i o r i t yt oa d j u s tt h ed e l a yb o u n di n s i d eas l i d m w i n d o w k e yw o r d s ：c r o s s - l a y e ro p t i m i z a t i o n , w e i g h t e df a i rq u e u i n g ( w f q ) ，p r i o r i t y - b a s e d w e i g h t e df a i rq u e u i n g ( p w f q ) 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：离梅静 2 0 0 6 年q 月1 0 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名： 学位论文作者签名：郭海静 年月日卿6 年q 月1 0 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：挪海静 舢6 年q 月j 0 日 第1 章引育 第1 章引言 随着3 g 无线通信系统的引入，以及互联网的显著增长和普及，无线多媒体 通信服务将在社会中起到越来越大的作用根据预测，全球蜂窝服务将在不久 的将来呈现指数增长未来无线网络上的通信量将是诸如语音、多媒体远程会 议和游戏这样的实时通信和诸如网络测览、讯息和数据传输这样的数据通信的 混合许多蜂窝电话已经配置了额外的大彩屏、数字相机、媒体播放器、网络 溺览器、多媒体讯息、视频播放器和m p 3 播放器 然而，无线技术和多媒体应用程序的结合不但使网络拥有无限的可能性， 也带来了巨大的挑战首先。呈现多媒体数据需要大量的信息，这将导致对带 宽的高要求由于无线系统的链接带宽资源有限，对带宽的巨大要求成为无线 多媒体通信最严重的瓶颈之一，特别是对于宽带多媒体应用程序( 倒如视频和 音频) 其次，由于用户的移动和干扰而产生的无线网络中的环境变化导致了带宽 和错误率的动态变化 再次，殷务质量q o s ( 饲如，传输速率、传输等待时间、错误率和可靠性) 和多媒体数据质量q o m d ( 例如，图像视频质量) 的要求依赖于多媒体服务的 特性一般而言，不同种类的媒体拥有不同的特性，并对不同的流量供应要求 变化多样的q o s 保证例如，诸如视频和音频这样的实时媒体对数据率、延迟 和数据包丢失率的改变高度敏感诸如网络数据这样的非实时媒体对延迟就不 太敏感，但是要求可靠的传输 因此，在无线网络中支持多媒体服务比在有线网络中更加具有挑战性因 而，怎样有效地分配和使用这些有限的资源是一个重要的课题。 传统的网络设计的方式是确定一个协议层栈，并且独立地设计这些协议层 层次化的设计在过去广为使用，但是现在已经不再适合于无线多媒体通信 为了面对这些挑战，一种跨层设计( c m s s - l a y e r d e s i 印) 毵念被提出了。跨层优 化设计基于交互信息在传统协议栈之间的交换，连带地使所有的系统部件都适 应于环境和应用要求的动态变化可以在o s i 的所有协议层执行这样的调适 目前，大部分的研究集中于协议栈中的物理层和数据链路层【1 提议了一 第1 章引育 种基于无线视频流的多用户跨层优化概念信息在传统协议栈中的多个协议层 之间交挟，优化在多个视频流用户之间连带地进行 3 】提议了一种新的多用户 跨层优化概念，使用主观平均得分m o s ( m e a no p i n i o ns c o r e 徕作为公用的应用 层性能的衡量标准基于这些，本文通过在所有应用之问动态地使用优先级， 将已有的跨层框架扩展到延迟感应应用程序在这点上，数据包调度( s c h o d u l i n g ) 将被研究 流体公平捧队f i q 四面df a i rq u c , l i n g ) f 久以来都被视作一种流行的范例， 在共享单向链接上提供有限的延迟和公平的数据包流 4 加权公平队列w f q ( w e i g h t e df a i rq u e u i n g ) 是一种模拟f f q 的数据包公平队列算法，在保证带宽和 限制延迟方面有很好的特性然而，队列延迟范围和分配的权重联系紧密，基 于优先级的加权公平队列p w f q ( p r i o r i t y - b a s e dw e i g h t e df a i rq u e i l i i i 稍数据流 的权重和优先级结合起来，即保证带宽，又在一个滑动窗中调整延迟范围p w f q 通过将优先级整合到公平队列算法中消除了权重对延迟的影响 本文的其它部分是这样安排的第2 章介绍以前的有关跨层优化的工作 第3 章介绍有线网络和无线网络中的数据包调度概念第4 章介绍p w f q 的执 行第5 章给出仿真的结果最后，第6 章总结结论和展望以后的工作 2 第2 章以前的工作 第2 章以前的工作 1 提议了一种基于无线视频流的多用户跨层优化概念信息在传统协议栈 中的多个协议层之间交换，优化在多个视频流用户之间连带地进行【3 】提议了 一种新的多用户跨层优化概念，使用主观平均得分m o so 懒n0 i ，i 血阻s c o r o 来作为公用的应用层性能的衡量标准本章将介绍这些以前的跨层优化工作 2 1 跨层优化概念 层次化是通信协议栈的传统设计方法论传统的网络设计的方式是确定一 个协议层栈，并且独立地设计这些协议层层次化设计的本质特征是层次的独 立性然而，在所有的时问内严格保持层次化可能导致不能有效地执行协议组 因而层次化设计不能再满足无线多媒体通信的挑战，虽然它在过去广为使用 跨层设计是一个迅速增长的研究领域，被认为是一种很有前途的实现有效 网络的方法在这种范例中，层次不再在协议栈中相互独立更正确地说，特 定层次的技术和其他层次的技术被连带地设计，来连带地调适所有的系统部件 换句话说，信息在传统协议栈之间交换和共享以促进最佳配置 跨层优化的概念可以在所有通信网络中应用，但是由于无线网络的独特挑 战，它在无线网络中特别重要由于无线信道的时变特性和衰落特性以及多 媒体服务质量q o s ( q 1 l a l i t yo f s e n ，i 嘞要求的苛求性和多变性，无线多媒体通信 是一个充满挑战性的课题保持协议栈内各层独立和单独设计的传统层次化网 络设计方法将难以面对这些挑战。 跨层优化的最终f l 标是在有效使用可用的无线资源的同时，优化用户接收 的服务质量跨层优化可以得到更佳的用户满意度和增强的服务接受度 2 2 系统结构 目前，大部分的研究集中于协议栈中的物理层和数据链路层。【1 提议了一 种基于无线视频流的多用户跨层优化概念信息在传统协议栈中的多个协议层 之间交换，优化在多个视频流用户之间连带地进行连带的优化以从应用层和 物理层链路层提取的参数为基础 连带优化的目标是优化无线网络中视频流的端对端质量为了达到这个目 3 第2 章以麓的工作 的，协议栈中的三个协议层需要被考虑，即应用层、数据链路层和物理层由 于应用层拥有有关所有成功繁码的媒体数据对于用户接收质量的直接信息，以 及用户感知到的端对端质量直接取决于应用程序，连带优化包含应用层无线 电链路层( r a d i ol i n kl a y e r ) 是指物理层以及数据链路层的集合，因为无线通信的 特殊挑战来源于此两协议层必须处理的无线信道特性，所以连带优化也考虑无 线电链路层。 为了实现跨层优化，图2 1 1 】显示的系统结构被提出来提供一种可能的执 行解决方法，而视频流被假定为无线多媒体服务的一种应用程序实例假设一 个视频流服务器位于基站，而多个流客户端位于移动设备，比如移动电话多 个流客户端被假设共享相同的网络资源，但是要求不同的视频内容 图2 1 系统结构 在基站，被提出的跨层优化概念包括三个步骤：参数提取、跨层优化和决 定发布首先，通过参数提取过程从应用层和无线电链路层提取必要的状态信 息在这个过程中，协议层的特定参数被转化为跨层优化器能够理解的参数 接着，通过跨层优化过程，跨层优化器从一组输入参数对中选择一个使一个特 定的目标函数最优化的参数对作为决定最后，优化器将决定信息发布回相应 的协议层。各个协议层有责任将选择的提取参数转化回协议层特定参数和实际 的操作模式这些步骤的重复频率依赖于应用程序要求和物理媒介传输性能的 变化快慢 4 第2 章以前的工作 2 3 参数提取 因为优化器不能理解协议层特定参数或是只能使用有限的参数，所以必须 从选定的协议层中选取必要的状态信息或一组关键参数，并提供给跨层优化器 以执行跨层优化。 确定能够描述协议层性能的参数是很困难的。使用一组包含很多参数的参 数组来描述协议层会很精确，但是考虑到数据处理，这样通常会导致很高的成 本。因此，参数提取过程必须大幅减少跨层优化器使用的参数的数目 视频流应用程序在应用层压缩、分包和调度数据传输。视频源的速率，帧、 c o p 的结构、帧间的依赖性、差错隐藏、时间约束等都对在应用层压缩特定参 数产生影响。参数提取过程选择适当的协议层特定参数，并将其转换为所谓的 提取参数。在应用层，为跨层优化而提取的关键参数与压缩的源数据的性能有 关系。因为不同的应用程序可能对压缩的源数据的性能有不同的要求，这些关 键参数可能取决于应用程序的类型。 与无线网络相比，有线民络中的物理层和数据链路层的动态变化要小得多 为了适应无线信道的动态变化，无线网络中的物理层和数据链路层是专门设计 的。物理层管理传输功率、信道估计、同步、信号整形、调制和信号检测，而 无线电资源分配和差错控制由数据链路层控制。因为无线信道的独特性能对这 两个协议层都有很大的影响，物理层和数据链路层通常被合并起来作为无线电 链路层考虑。因此，无线电链路层的特定参数包括信道相干时间、s n r 、数据包 或比特错误率、调制方式、传输时间安捧、传输功率等。 因为这些协议层特定参数彼此之间都有联系，所以提取参数是必要的。调 制方式、信道编码和多用户调度都会影响到数据传输速率。而传输功率、信道 估计、信号检测、调制方式、信道编码等都会影响到传输数据包错误率。用户 的信道相干时间则与用户速率以及周围的环境相关联，而数据包长度通常由无 线系统的标准来确定。数据传输速率、数据包错误率、数据包长度和信道相干 时间可以被提取作为无线电链路层的关键参数 对于移动无线电信道而言，瑞利衰落( r a y l c i g hf a d i n 微型被广泛地接受 g i l b e r t - e l l i o t ( g e ) 数据包擦除信道模型被用来精确地描述这种类型的衰落模型。 ( 坦模型使用两种状态g ( 好) 和b ( 差) 来代表无线信道数据包差错行为的动态 性如果数据包接收正确而及时则为状态g ，如果数据包丢失则为状态b 。这种 5 第2 章以前的工作 模型可以用从状态0 转变为状态b 的转换概率p ，以及从状态b 转变为状态g 的转 换概率q 来描述 2 。4 跨层优化 跨层优化器按照一个特定的目标函数来执行优化，选择使目标函数最大化 的输入参数对。目标函数的选择依赖于系统设计的目的。不同的目标函数将使 优化器做出不同的决定。 以这个视频流应用为例。在单用户的情况下，一个可能的目标函数是源序 列和显示的视频序列的平均p s n r ( p 酞s i g n a i t o n o i s e r m i o ) 。在多用户的情况 下，对p s n r 的不同扩展都是可能的。比如，目标函数可以是所有用户的p s n r 之和，也可以是所有用户的平均p s n r 。 2 5 决定发布 一旦跨层优化器做了决定，决定发布过程将最佳的提取参数值发布到相应 的协议层。然后，单个协议层分别将选择的提取参数转化回协议层特定参数和 实际的操作模式。 2 6 多用户跨层优化 至今，应用程序驱动的跨层优化被研究用于仅支持一种应用程序的系统 然而，实际上共享无线媒介的用户通常同对运行不同的程序。每种类型的应用 程序会转化为一组不同的要求，此外，丢失率对用户接收质量的影响也随应用 程序的不同而不同。因此，对于运行不同程序的系统的连带跨层优化要求确定 一个公共的衡量标准，能够量化用户对服务传送的满意度，也要求将网络和应 用程序参数映射到这个衡量标准上【3 】。 多应用程序优化的挑战主要集中在最大化吞吐量上。吞吐量最大化只对对 延迟和数据包丢失率都不敏感的应用程序有好的性能。诸如视频和音频这样的 多媒体应用程序对数据率、延迟和数据包丢失率高度敏感因此， 3 提出了一 种新的多用户跨层优化概念，使用主观平均得分m o s ( m e a no p i n i o ns c o r e ) 来作 为公用的应用层性能的衡量标准 主观平均得分m o s 最初是为了评价语音质量而被提出的，它在电路的目的 端提供了一种对人类语音质量的数值化测量。传统上，测量接收到的语音质量 的唯一方法是通过用户的主观测试为了确定m o s ，一组有资格的听众被叫来 6 第2 章以前的工作 为他们刚刚听到的语音鉴定等级，然后对这些主观测试求数值上的平均值，来 定量显示系统的性能。在m o s 测试中使用的等级如下所示：( 1 ) 劣，( 2 ) 差，( 3 ) 中，“) 良，( 5 ) 优。m o $ 是最可靠的语音质量估计方法，但是非常昂贵和费时， 不适用于实时应用程序 3 提出的多用户跨层优化方法将m o s 作为一种用户接收质量的衡量标准 扩展至其他应用程序。使用公用的优化衡量标准使优化可以在多应用程序之间 执行。目标函数可以选择为所有用户的m o s 平均值 7 第3 章调度 第3 章调度 本文通过在不同的应用程序之间动态地使用优先级来将跨层优化框架扩展 至延迟感应应用程序。关于这个，需要考虑数据包调度的问题。 3 1 调度概念 将来，大部分通信网络都将被要求为许多不同类型的应用程序提供支持， 而每种类型的应用程序都拥有各自独特的性能和q o s 要求：许多新的应用程序的 多态性要求对现有的网络基础结构做实质性的改变。随着带有诸如吞吐量、丢 失率、延迟或延迟变化这些不同q o s 要求的应用程序的出现，越来越强调网络能 够支持不同级别服务，而非单一的尽力服务( b 喊e f f o r t ) 。被要求满足这_ 酋e q o s 要 求的服务一般分为两类：保证服务和尽力服务保证服务为分配的传输速率、 带宽、延迟和延迟抖动保留资源。尽力服务使用可用的传输能力，尽全力传送 用户流量，但不能提供任何服务质量保证。 为了在同一个网络中提供这些不同类型的服务，要求带宽分配机制。此外， 为了支持保证服务，必须提供某些形式的资源分配程序流量调度算法，即确 定不同数据流的传输顺序，使q o s 参数保证更加容易 3 2 有线罔络中的调度 3 2 1 原尉 中央调度器的主要任务是在所有的队列中选择下一个被传送的数据包根 据描述不同数据流的可用信息，调度器确定这个数据包。 为了设计一个好的公平调度算法，需要下列算法特性： 1 带竟调度器应该确保每个数据流仅仅使用自己的带宽部分，以此来保护正 常数据流免受异常数据流的影响 2 鼍迟和鼍迟抖动保证调度器也应该确保正常数据流具有延迟和延迟抖动保 证的良好性能。 3 怔复杂度为了能够应用于高速b a c k b o n e 路由器，调度器应该具有底复杂 8 第3 章调度 度，在大多数情况下，首选恒定的复杂度，这样即使提高数据流的数目也不会 降低性能。 3 2 2 分类 3 2 2 1 基于时间标记的调度叠 对于一个基于时间标记的调度器而言，每个数据包都与一个根据到达时间 来确定的时间标记相联系，而数据包的传送顺序以这个时间标记来调度确定 1 0 。 加权公平队列w f q ( w e i g h t e df a i rq u e i l i n g ) 是第一个此类基于时间标记的 公平调度器。它是g p s ( g , e n e r a i z e dp r o c e s s o rs h a r i n g ) 的一个可实现的近似，以 数据包为基础模拟了g p s 。w f q 根据数据包在g p s 中的调度情况计算一个开始 服务时间标志和一个结束服务时间标志，并且以这些结束服务时间标示升序传 送。满足最坏情况公平性的加权公平队列w f 2 q ( w o r s t - c a s ef a i rw e i g h t e df a i r q u e n i n g ) e s 致力于w f q 与g p s 的差异，实现“最坏情况下的公平性”。与w f q 相类似，开始时间公平队列s t f q ( s t a a - t t m e f a i rq u e u i n g ) 也为每一个数据包计 算一个开始标志和一个结束标志。通过以开始标志升序传送数据包的方式，它 改善了低吞吐量数据流的延迟情况w f q 还有一些变体，比如自时钟公平队列 s c f q ( s e l f - c l o c k e df a i rq u e u i n g ) 和虚拟时钟( v i r t u a lc l o c k ) ，这两种变体都不需 要以g p s 服务器为参考，因此能够以更有效的方式计算时间标记。 基于时间标记的公平调度器被证实具有良好的公平性和延迟保证。由于它 们以时间标记为顺序捧列各自的数据包，所以它们的时间复杂度至少为 0 0 0 9 ) 。因此，基于时间标记的调度器不适用于有许多数据流的链接，或是高 速的网络。 3222 基于轮i t l o t o u n dl b b h ) 的调度量 对于一个基于轮询的调度器而言，数据流依次接受服务，因此每个数据流 被服务的机会是均等的 1 0 。基于轮询的调度器将数据包分类和分至个队列 中，并以从l 至的升序顺序服务这些队列。 赤字轮询d r r ( d e f i c i tr o u n dr o b i n ) 9 以每个数据流的权重来计算一个与 之成比例的定量大小，并有一个赤字计数器来记录目前未使用的分配带宽。调 度器允许一个数据流传送的数据包的数目最高可至定量与赤字计数器之和一 9 第3 章调度 旦一个数据流已经接受完服务，它需要等待其它一1 个数据流都被服务之后才 能再次接受服务，这会导致每个数据流都存在突发输出的情况。 基于轮询的调度器实现了0 0 ) 的时闻复杂度。由于每个队列在传送新的数 据包之前必须等待其它所有的数据流，基于轮询的调度器有很差的延迟边界， 通常与成比列。 3 2 2 3 两者的组合 一些近期提出的调度算法试图同时获得基于时问标记的调度器实现的低时 延和基于轮询的调度器实现的低复杂度 1 0 。它们通常采用基本的轮询调度策 略，并在一个小单元内加上基于时间标记的调度方法。 箱柜分类公平队列( b i ns o r tf a i rq i 嘲l i n g ) 根据各自的时问标志将每个数据 包放入某个箱柜中，而同一个箱柜中的数据包并不以f i f o 的方式分类和调度。 因此，每个数据包以较低的分类代价近似地根据其虚拟时间标记来调度。分层 的轮询根据权重将数据流组合成数据流类，在类之内使用轮询的方法来调度而 在类之间使用时间标记的方法来调度。 虽然这些调度器通过降低需要分类的数据流数目来改善时问复杂度，它们 仍然由于轮询的特性而具有0 ( ) 的最坏情况下的延迟 3 2 3 几种重要的基于时间标记的调度叠 3 2 3 g 陌( g e n e r a li z e dp r e c e = u o rh r i n s ) 【】c 5 【 3 】【1 4 】 基于时阃标记的调度器的目的是近似g p s g p s 是理想的f i q 服务模型， 并具有良好的特性 1 不管每个数据流的行为如何，它为每个数据流提供了最低带宽保证， 2 对于那些经过l 坶b u c k e t 流量整形的数据流，它提供了确定的端对端 的延迟限制。 3 它在服务器提供的大量服务之间确保公平性 g p s 有两个特定的理论假设一个假设是信息不是以数据包或比特的形式 来处理，而是根据无限小的可分数据流因此，数据流被称为“流体数据流” 另一个假设是所有的数据流在同一个链接上同时接受服务。 每个数据流i 分配到一个权重w i 。根据这个分配到的权重w ，在每个时间 瞬间t ，数据流i 以速率= c 形彤接受服务速率与各自的权重与总链接 第3 章调度 容量c 成比例。彤是所有数据流的权重之和。 g p s 实现了公平性的定义，没有其他调度算法能够像g p s 这样公平。对于 一个任意时间间隔“，2 ) ，在此期间，一组数据流口( ，f 2 ) 保持不变，每个数据流 i 分配到一个数据率，“，f 2 ) 。如果所有的数据流f ，口“，2 ) 都满足下面的公式， 则带宽分配是公平的： 降一矧= 。 ( 3 1 ) 在一个实际的数据包网络系统中，任意时间只有一个数据流能够接受服务， 一个数据包必须在前一个数据包完全传送完毕后才能接受服务。因此，g i s 是 理想化的，不能在实际的环境中实现。由于其良好的特性，g p s 被用作基于时 间标记的调度算法的数据包参考。 3 2 3 2 加权公平队 l l i l l f 0 ( b i l h t e df a i r ( e u i n l ) 【4 】 5 】 1 羽【1 】 许多调度算法被提出来在实际的数据包网络中模拟o p s 在它们当中，最 著名的是加权公平队列w f q 。 在w f q 中，每个数据包都与一个开始标识和一个结束标识相联系，这两个 标识分别对应于数据包的第一个比特和最后一个比特到达的“虚拟时间”。然后， 调度器服务系统中带有最小结束标识的数据包。速率分配过程分给每个数据流 一个权重，以及一个在忙碌时也能被保证的最低速率。 在时间彳( 群) 到达的数据流i 的第k 个数据包被分配如下的开始标识s ( 才) 和结束标识f ( 才) ： 1 s ( 片) = 础彤( 彳( 计) ) ，f 饼1 ) ) ，其中时间t 的虚拟时间y 表示相应流 体公平队列服务系统中的当前周期 2 h 计) = s ( 钟) + 吐 ，其中砖是数据流i 的第k 个数据包的长度，虚拟 时间的级数为a v q ) a t = c ( d 乏：。 在w f q 中，一个数据流在最坏情况下的数据包延迟与流体服务相比的差别 以一个数据包为上限。 3 2 3 3 满足最坏情况公平性的加权公平队列- f ( i b r i r t - - e ef a i r | e i s h t e df a i r q u e u i n s ) 【阳 w f q 有重要的特性，考虑到数据流获得的服务，w f q 不会比g p s 落后一 个数据包。然而，w f q 可能比g p s 提前大于一个数据包。这个巨大的差别将导 致不稳定和不够有效的网络控制算法为了解决这个问题，满足最坏情况下的 第3 章调度 公平性的加权公平队列w f 2 q 被提出 w f 2 q 稍微修改了w f q ，并保持了有限延迟的特性和g p s 在最坏情况下的 公平性。它提供了与g p s 几乎相同的服务，最大的差别不会大于一个数据包。 在一个w f q 系统中，当调度器选择下一个要传送的数据包时，它在所有数据流 中选择带有最小结束标识的数据包在一个w f 2 q 系统中，当调度器选择下一 个要传送的数据包时，它仅仅在虚拟开始标识已经发生的数据包中选择带有最 小结束标识的数据包。 3 2 3 4 开始时间公平队列s t f o ( s t a r t - t i mf a ir0 u e u i n g ) 【 2 】 在s t f q 中，每个数据包和一个开始标识和一个结束标示相联系。然而，与 w f q 不同，调度器以数据包开始标示的升序传送数据包。s t f q 对低速率应用 程序实现了低延迟。 3 3 无线网络中的调度 3 3 1 原尉 在有线网络中，流体公平队列f i q 被广泛地接受为在一个共享链接上提供 有限延迟和公平性的流行范例。然而，由于无线信道的独特特性，将公平队列 应用于无线领域并不是一件简单的事情。这些特性包括突发信道错误和依赖于 地点的信道容量和错误 无线传送涉及到局部广播。争用和有效的信道容量依赖于地点此外，由 于干扰、衰落和多经效应，信道错误也依赖于地点。这导致在任意时刻，可能 一些数据流可以传送但另一些数据流由于信道错误而不能传送因此，任意时 刻只有一个数据流子集可以在信道上进行调度，而这个子集随着时间动态地改 变。所有的有线网络的调度算法都假设信道是无错的，或者至少要不所有的数 据流都能够被调度，要不没有数据流能够被调度。事实上，如果一个数据流子 集由于信道错误而不能传送，f f q 模型本身并不能解决公平性的问题。特别是， f f q 可以在数据流之间提供长期公平性和短期公平性。然而，由于依赖于地点 的信道错误，提供长期公平性和短期公平性的能力将被破坏。这表示，有线网 络的调度算法不能直接应用于无线网络，需要发展新的无线网络公平模型。 在调度算法的研究中，一个被广泛使用的无线信遭模型是带有两个状态的 离散时间马尔可夫链：无错( 好) 或有错( 差) 信道根据一个确定的转换概率 1 2 第3 章调度 矩阵在两个状态之间改变。只有信道在整个数据包传送过程中都是无错的，这 个数据包才算是成功地接收任意时间在无错数据流和有错数据流之间交换信 道存取将提供长期公平性，但非短期公平性 调度器在无线网络中应该实现的最重要目的是尽可能地分别为每个数据流 提供q o s 要求。为了在一个共享信道上传送实时和非实时的数据，系统模型应 该考虑不同的特性 1 4 。 1 对无错信道，调度器应该为数据流提供短期公平性和短期吞吐量极限。 2 加之，对于信道错误持续时间有限的信道，调度器应该为数据流提供长 期公平性和长期吞吐量界限。 3 此外，调度器应该同时支持延迟感应数据流和错误感应数据流。 4 自然地，调度算法应该具有低执行复杂度，使之能应用于高速传送网络。 3 3 2 调度置组件 为了在无线环境中提供有效的操作，调度器通常包括如下组件 4 6 儿1 4 3 3 2 1 无错履务模量 j 无错服务系统确定一个假设没有信道错误的理想公平服务模型，并为一个 数据流在理想无错环境中应该接收多少服务提供参考。如上所述，无线公平队 列的目标是通过使突发的短错误对数据流保持透明而仅使将长信道错误暴露给 数据流来接近无错服务模型 大多数现代无线公平队列算法使用著名的有线公平队列算法作为其无错服 务模型。有三种典型的有线公平队列算法： 1 例如w f q 这样的有线公平队列算法，其虚拟时间的变化率被精确地模 拟精确地模拟虚拟时间可能运算起来花费很高。理想无线公平队列i w f q ( i d e a l i z e dw i r e l e s sf a i rq m u m g y l l 用w f q 或者w f 2 q 来计算其无错服务。 2 例如s t f q 这样的有线公平队列算法，其虚拟时间的变化率没有精确地模 拟在s t f q q b ，虚拟时间被设置为当前被服务的数据包的开始标示。信道情况 独立公平队列c n 。- q ( c h a n n e l - c o n d i t i o ni n d e p e n d e n tf a i rq i 崩l i n 触用s 1 1 q 来计 算其无错服务。 3 一种消除调度器的延迟和速率的f f q 变体，由无线公平服务w f s ( w i r c e s sf a i rs e r v i 哟提出它为每个数据流i 分配一个速率权重e 和一个延迟权 第3 章调度 重蠢。开始标示s ( 计) 和结束标示以霄) 可以用下面的公式来这样描述： s ( p ：) = m a x ( 一( 计) ) ，f ( 片) + 骘。1 肛) 和，( 计) = s ( p ：) + e m 3 3 - 2 2 领先和落后模型 领先和落后模型显示数据流是领先于、同步还是落后于无错服务模型，以 及领先或落后多少。 落后量、落后数据流、领先量和领先数据流根据数据流在实际服务中实际 接受的服务与其理想服务的差别来描述。落后数据流的落后量代表数据流为补 偿在过去丢失的服务而在将来接受到的附加服务量。领先数据流的领先量代表 为补偿在过去接受到的附加服务量而在将来必须放弃的服务量。 有两种截然不同的方法来计算落后量和领先量。 1 数据流的落后量是无错服务和数据流接受到的实际服务的差别。在这种 情况下，一个数据流落后于无错服务将在将来得到补偿。其丢失的时隙是否被 其他数据流使用不会有任何差别基于服务器的公平方法s b f a ( s c r v 盯b a s e d f a h - n c s sa p p r o a c h ) 使用这种方法。 2 数据流的落后量是分配给该数据流的时隙数目，当该数据流由于信道错 误而不能传送，而另一个信道没有错误的数据流占用这些时隙来传送和提高自 身的领先量。在这种情况下，数据流的落后量只有在其他数据流使用这个时隙 并打算在将来放弃这个时隙的时候才会增加。i w f q 、w f s 和c i f q 使用这种方 法 可以使用数据流特定参数来确定领先量和落后量的上限。落后量的上限是可 以对数据流保持透明的最大突发错误长度，而领先量的上限是数据流为补偿在 过去接受的服务而必须在将来放弃的时隙数目的最大值。 3 3 2 3 补偿模型 补偿模型是无线公平队列算法的关键组锌。它决定落后数据流如何补足其 落后量和领先数据流如何放弃其领先量。因此，有三个问题需要考虑 1 为了降低落后数据流的落后量，领先数据流被要求放弃某些在无错服务 中分配到的时隙。领先数据流应该在何时放弃这些分配到的时隙? 有三种可能 的方法让领先数据流放弃其领先量 在第一种方法中，一个领先数据流放弃所有分配到的时隙直至它变为与无 错服务同步。如果其它数据流遇到大的突发错误，一个领先数据流将积累巨大 的领先量。如果所有的落后数据流在将来感知到无错信道，这将会导致该领先 1 4 第3 章调度 数据流可能长时问无法接收到信息。i w f q 采用这种方法。 在第二种方法中，一个领先数据流放弃一部分分配到的时隙。这部分被放 弃的时隙可以是常数，比如在c i f - q 中，或者可以与领先量成比例，比如在w f s 中。这种方法可以实现适度的服务退化。 在第三种方法中，一个领先数据流永远不放弃领先量。在这种情况下，信 道带宽的一部分被分离保留，用来补偿落后数据流。s b f a 使用这种方法 2 为补足在过去丢失的服务，落后数据流必须接收超过无错服务的附加时 隙。这些附加时隙被称为补偿时隙。这些补偿时隙应该在何时被分配给落后数 据流? 有三种可能的方法来补偿落后数据流。 在第一种方法中，补偿时隙被优先分配直至不再有接收到无错信道的落后 数据流。结果，落后数据流在信道分配中优先于同步数据流和领先数据流。i w f q 使用这种方法。 在第二种方法中，补偿时隙只有在领先数据流放弃时隙的时候才被分配。 c n ：- q 和w f s 使用这种方法。 在第三种方法中，补偿时隙从特意为补偿而保留的一部分信道带宽中被分 配s b f a 是用这种方法。 3 在信道分配上给落后数据流优先级可能会扰乱同步数据流，即使感知到 无错信道的同步数据流也会成为落后数据流。另一方面，分配信道的一个分离 保留部分静态地限制了可以得到的补偿量。因此，在落后数据流和领先数据流 之间交换时隙被认为是最合适的实现无线公平服务的方法补偿时隙应该如何 在落后数据流之间分配? 有三种方法。 在第一种方法中，拥有最大落后量的落后数据流分配到补偿时隙，比如在 c x f - q 中 在第二种方法中，保留数据流的历史记录。数据流根据他们等待传送的顺序 来补偿，比如在i w f q 和s b f a 中 在第三种方法中，落后数据流被公平地补偿。每个落后数据流接收到的补偿 时隙数目与其落后量成比例，比如在w f s 中。在这些选项中，公平补偿在无线 公平服务中实现短期公平性，但是比其他两个选项在计算上更加复杂 3 3 2 4 消除时隙队列和敷据包队列的联系 消除时隙队列和数据包队列的联系允许在单一框架中同时支持延迟感应和 错误感应数据流，并且消除连接层次数据包管理策略和链接层次数据包调度策 1 5 第3 章调度 略的联系 通常，有线调度算法在数据包到达时计算其标示。如果信道没有错误，一 个被调度的数据包永远都能被正确地传送和接收。然而，在无线信道中，信道 错误可能会导致数据包破坏，错误感应数据流可能会需要重传未能成功传送的 数据包。被重新标示的数据包将加入到数据流队列的末尾和次序颠倒地传送。 为了消除时隙队列和数据包队列的联系，使用一个附加层次的提取。每次， 调度器决定哪个时隙可以存取信道，相应数据漉队列的前端数据包被传送。附 加层次的提取根据无线公平模型使调度器同时支持错误感应和延迟感应数据 流。在传送过程中出现信道错误的情况下，错误感应数据流不会删除前端数据 包，但是延迟感应数据流则在数据包超过延迟界限时删除前端数据包 3 3 2 5 信道监控和预测 信道监控和预测在任何时问为每个数据流提供信道状态的测量和估计 为了实现完美的依赖于信道的调度，调度器需要有关每个数据流信道状态 的精确信息。因为信道错误依赖于地点，每个数据流需要不断地监控其信道状 态，预测其将来的信道状态，并将这些信息发送绘调度器。 无线信道中的错误一般突发并且在连续时隙之间高度关联，但是可能在长 时问之间不关联。因此，一个打状态马尔可夫模型就可以很好地实现精确的信道 预测 3 3 3 几种无线调度叠 a 3 3 1 理想无线公平队列i - 阳( i d e a l i z e d i r e l e s sf a i rq u e u i n g ) 【4 】 在咧f q 中，无错服务由w f q 和w f 2 q 来模拟。每个时隙的开始标示和结 束标示由w f q 来分配数据流的服务标示被设置为前端时隙的结束标示。为了 调度传送，i w f q 在所有接收到无错信道的数据流中选择带有最小服务标示的数 据流 每个数据流i 被一个领先量边界，和一个落后量边界b 。限制数据流i 的服 务标示与无错服务的差别不被允许高于，。或是低于屯。 刑f q 的补偿模型是含蓄的。如果数据流接收到信道错误，则保持其标示不 变同样地，如果数据流接收到附加服务，其服务标示增高。结果，落后数据 流具有比同步数据流与领先数据流低的服务标示，因此落后数据流在蓐知到无 第3 章调度 错信道时具有信道分配的优先级。 i w f q 的补偿模型会使一个长时间落后的数据流在感知到无错信道的时候 立刻能够存取信道。同样地，一个领先数据流可能会长时间不被允许存取信道。 因此，i w f q 的补偿模型不支持适度的服务退化加之，同步数据流可能在补偿 落后数据流时受到影响。 3 3 3 2 信道情况独立公平队舅j c i f - 0 ( c h a m m i - c o n d i t i o ni n d e p o n d o n tf a i rq u e u i n g ) 【4 】 在c - q 中，无错服务由s t f q 来模拟。每个数据流带有一个落后参数 落后数据流的落后参数是正值，而领先数据流的落后参数是负值。 如果一个落后数据流或者同步数据流f 感知到干净的信道，则传送一个数据 包。如果其他数据流_ ，感知到干净的信道，则代替i 传送一个数据包。然后j 的落 后量增高，而_ ，的落后量降低。 领先数据流f 保留其服务的一部分口而放弃另一部分l 一口，其中口是管理领 先数据流服务退化的系统参数领先数据流放弃的时隙被分配给带有最大落后s 量的落后数据流。 c 邪q 为领先数据流提供了线性的适度退化。加之，它通过优先与领先数据 流交换时隙来执行落后数据流的补偿，以此来确保同步数据流不被过多地影响 因此c - q 克服了i w