（计算机软件与理论专业论文）蓝牙系统调度策略的研究.pdf

中文摘要 本文主要论述的是如何在蓝牙设备组成的微微网中进行合理调 度，从而提高数据传输效率的问题。在当今蓝牙设备使用日益广泛、 蓝牙网络拓扑结构日益复杂的情况下，一个庞大的蓝牙散射网可能包 含有数十个蓝牙设备，而每个微微网中最多有七个蓝牙设备，无论是 网间还是网内的调度，都不能简单的采用轮询调度，这将使效率上受 到很大的影响，而且蓝牙系统中的主结点驱动半双工时分多路复用的 传输模式，也对调度策略提出很多特殊的要求，因此，要解决这些问 题，必须抛弃传统的调度策略的一些缺点，采用新的或改进的策略， 以提高效率。 本文先从分析已有的调度策略开始，采用概率计算和排队模型的 方法，比较它们之间的基本特点，并分析影响它们效率的主要因素， 接着从一个并不复杂，但却有较高效率的h o lp p 策略为出发点，针 对其主要的缺点和影响效率的主要原因，进行相应改进，提出一种新 的改进算法，并采用概率的方法，从理论上计算出改进的效果，最后， 通过仿真实验的验证，证明符合理论分析的结果，并且得到了一定的 改进效果。 关键词：微微网，优先级调度，仿真 a b s t r a c t w em a i n l yd i s s e r t a t et h es c h e d u l i n gp o l i c yi nap i c o n e t w h i c hi sc o n s t r u c t e db ys e v e r e lb l u e t o o t hd e v i c e sh e r e a sw e a l lk n o w ，b l u e t o o t hd e v i c e sa r eu s e dw i d l ya n dt h eb l u e t o o t h n e t w o r k t o p o l o g y i sm o r ea n dm o r e c o m p l e x f o re x a m p l e ，i n a b l u e t o o t hs c a t t e r n e t ，t h e r e m a y b ed o z e n so fb l u e t o o t h d e v i c e s ，i ne v e r yp i c o n e t ，t h e r e & r es e v e nb l u e t o o t hd e v i c e sa t m o s t ，w ec a n tu s et h er o u n dr o b i nt os c h e d u l ei t b e c a u s et h e r o u n dr o b i np o l i c yh a sp o o re f f i c i e n c y ，o t h e r w i s et h em a s t e r d r i v e nt d dm o d ew h i c hu s e di nb l u e t o o t hs y s t e ma l s oh a s s o m e s p e c i a lr e q u e s t s ow em u s tu s ean e wp o l i c y t os c h e d u l et h e b l u e t o o t hs y s t e m t o g e t an e ws c h e d u l e i n gp o l i c y ，w e f i r s t a n a l y s e s o m e e x i s t i n gs c h e d u l i n gp o l i c y ，s u c h a s r r ，p p ，k f pa n dh o lp pb y u s i n gt h ep r o b a b i l i t yt h e o r y a n d t h e q u e u et h e o r y ，f i n d t h e f a c t sw h i c hh a v er e l a t i o nw i t ht h e i rp e r f o r m a n c e ，t h e nw e u s e t h e p r o g r e s s a b o v et od e v e l o p an e w s c h e d u l i n g f r o mh o l p p ，f i n a l l y ，w e d oas i m u l a t i o n ，f r o mi tw ef i n dt h en e wp o l i c y w o r k sm o r ee f f i c i e n c yt h a nh o lp p k e yw o r d s ：p i c o n e t ，p r i o r i t yp o l i c y ，s i m u l a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盘注盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：罴听若婷签字日期：h 巾丫年月7 同 、p 7 学位论文版权使用授权书 本学位论文作者完全了解盘壅盘鲎有关保留、使用学位论文的规定。 特授权墨童盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 买俪 新虢令 签字日期：枷年月7 日 签字日期：铆争年月7 日 第一章绪论 1 1 蓝牙技术简介 1 1 1 蓝牙技术概述 第一章绪论 蓝牙技术是一种短距离的无线通信技术，它的提出是为了解决通讯终端的线 缆连接问题，如今它的应用已经远远超出了这个范围。蓝牙技术( b l u e t o o t h l 0 ) 可提供1 0 米内的无线连接，采用跳频扩展技术( f h s s ) ，跳频速率为每秒1 6 0 0 次， 最高传输速率为l m b p s ，通信协议采用t d m a ( 时分多址) ，在2 4 g h z 的i s m 频带 上设立7 9 个带宽为1 m l - l z 的信道，用每秒钟切换1 6 0 0 次的频率的跳频( h o b b i n g ) 扩展技术来实现信息的收发，支持异步数据通道( a c l ) 同步话音通道( g c o ) 两种信 道，每一个话音通道支持6 4 k b p s 的同步话音，异步通道支持最大速率? 2 1 k b p s 、 反向应答速率为5 7 6 k b p s 的非对称连接，或者是4 3 2 6 k b p s 的对称连接。改进 的蓝牙协议( b l u e t o o t h l 1 ) 可将通讯距离扩展到1 0 0 米，并提供i o m 以上的传输 速率。 蓝牙系统由无线电单元、链路控制单元、链路管理支持单元以及主机终端接 口所组成。蓝牙无线电波根据天线的传送能力可以实现从1 0 米( 家庭) 到1 0 0 米( 机场候机大厅) 范围内的无线通信。依赖于设备的类型，蓝牙无线电可以传 输最高1 0 0 毫瓦( 2 0d b m ) 最低1 毫瓦( 0d b m ) 的功率。蓝牙采用跳频技术 抑制干扰、降低信号衰减，使用时分复用t d d 和高斯频移键控g f s k ( g a u s s i a n f r e q u e n c ys h i f tk e y i n g ) 调制实现全双工数据传输。 1 1 2 蓝牙规范 蓝牙技术遵循蓝牙规范。蓝牙规范最初由s i g 于1 9 9 8 年提出，包括蓝牙协 议核心规范和协议子集( p r o t o c o lp r o f i l e ) ，称为蓝牙1 。0 规范。蓝牙核心规 范所定义的蓝牙协议采用分层结构的协议栈模式( 图卜1 ) ，从下至上依次为基带 协议( b a s e b a n d ) 链路管理层协议( l m p ) 、逻辑链路与适配协议( l 2 c a p ) 、射频通信 协议( r f c o ) 、服务发现协议( s d p ) 和电话传送控制协议( t c s ) ，此外还支持一些 附加的应用协议，如：p p p 、t c p i p 、o b e x 、v c a r d v c a r l 、l r m c 和w a p 等。 下一层协议为上一层协议提供服务。 基带协议定义蓝牙的无线链路及其传输模式、主从( m s ) 结点等，此外还可以 第一章绪论 提供面向连接( s c o ) 业务和无连接( a c l ) 业务。一般地，s c o 用于分组数据业务， 其特点是可靠性，但有延时。而a c l 用于话音传送，其特点是实时性好，但可靠 性比s c o 差。 链路管理协议( l m p ) 负责建立和解除m s 设备单元之间之间的连接，以及鉴权 和加密功能。另外还控制m s 设备单元的工作模式( 如p a r k h o l d s n i f f 等模 式) 。 l 2 c a p 是第三层的控制和适配协议。l 2 c a p 向r f c o m m 和s d p 等层提供面向连 接和无连接业务。基带数据业务可以越过l m p 而直接通过l 2 c a p 向高层协议传送 数据。从某种意义上说，l 2 c a p 和l m p 都相当于o s i 第二层即链路层的协议。 图卜1蓝牙协议栈 r f c o m m 是射频通信协议，它可以仿真串行电缆接口协议( 如r s 2 3 2 、v 2 4 等，符合e t s l 0 71 0 串口仿真协议。通过r f c o m m ，b l u e t o o t h 可以在无线环境 下实现对高层协议，如p p p 、t c p i p 、w a p 等协议的支持。另外，r f c o m m 可阻 支持a t 命令集，从而可以实现移动电话和传真机及调制解调器之间的无线连接。 s d p 服务发现协议是所有用户模式的基础。s d p 上层可以有f t p 、l a n 接入、 无绳电话、同步模式等应用。通过确定不同的信息类型和业务类型，s d p 可以在 设备单元之间建立不同的s d p 层连接。由于蓝牙技术独立于不同的操作系统和通 信协议之外，可以移植到许多应用领域，因而应用场合很普遍，适用于任何数掘、 第一章绪论 图象、声音等短距离通信场合。目前所能看到的应用有：替换蜂窝电话和远端网 络之间的通信时所用的有线电缆；提供新的多功能耳机，从而在p c 、蜂窝电话、 随身听中共用；笔记本、p d a 、蜂窝电话之间的名片数据交换。 蓝牙规范的协议子集定义了一系列蓝牙技术的应用模型，它的定义给具体的 蓝牙应用定义了完整的框架，解决了蓝牙技术的应用过程中，不同厂家之间的产 品的互操作问题。协议子集是一种应用模型，是蓝牙核心协议的组合，它规定了 某一具体的应用需要使用哪些核心协议，这些核心协议蚍怎样的顺序组合。 1 1 3 蓝牙技术的应用 蓝牙技术的应用范围是很广的，传统的应用用于取代有线电缆，如取代r s 2 3 2 串口线用于计算机与外设相连。此外还有一些新型的应用，如：数据共享、数据 同步、移动计算、i n t e r n e t 接入等。 1 2 蓝牙系统中调度策略的作用 1 2 1 蓝牙网络的拓扑结构 蓝牙技术的目的是为了把多个设备用无线的方式连接起来，实现相互间的通 信。蓝牙系统既可以实现点对点连接也可以实现一点对多点连接。在一点对多点 连接的情况下，信道由几个蓝牙单元分享，两个或者多个分享同一信道的单元构 成了微微网( p i c o n e t ) 。微微网实际上是一种个人区域网，这是一种以个人区域 ( 即办公室区域和家庭区域) 为应用环境的网络建构的，微微网由主设备单元和从 设备单元两种设备单元构成。主设备单元负责提供时钟同步信号和调频序列，而 从设备单元一般是受控同步的设备单元，并接受主设备单元的控制，在同一微微 网中，所有设备单元均采用同一调频序列，每个从设备单元的起始频率和占用信 道由主设备单元控制，一个微微网中存在1 个主单元和最多可达7 个的活动从单 元。这些设备可以处在以下几个状态情况下：a c t i v e ( 活动) 、p a r k ( 暂停) 、h o l d ( 保 持) 和s n i f f ( 呼吸) 。多个相互覆盖的微微网形成了分布网( s c a t t e r n e t ) 。( 图 1 2 ) 。 1 2 2 微微网内的数据传输效率问题 随着蓝牙技术的日益成熟，蓝牙技术将应用于i n t e r n e t 接入、图象资料的 第一章绪论 传输等数据量较大的领域。如同i n t e r n e t 上的i p 网络需要路由器、交换机等设 备，用来行使路由、调度等功能，以提高数据的传输速率和效率一样，处理大数 据量的蓝牙系统也需要路由( s c a t t e r n e t 网) 和调度策略，毕竟，b l u e t o o t h l 1 所规定的传输速率也只有i o m ，因此，一种高效合理的调度策略对一个蓝牙微微 网来说，更是至关重要。 蓝牙协议定义了一种调度策略，即轮询策略( r o u n d r o b i n ) ，这是一种较为 简单且易实现的策略，这种策略的基本思想是给每一个主结点和从结点之间的链 路预分配传输时隙，这样就造成不必要的传输时隙的浪费，而且也造成了调度的 不公平性。因此，一些改进的调度策略应运而生，常见的包括优先级调度( p p ) 、 k 公平调度( k f p ) 、h o l p p 、h o l k f p 等。 蓝牙微微网的调度策略还包括另个重要的方面，即数据的分段与重组 ( s a r ) ，这是因为s c o 链路的存在，需要等间隔的预分配时隙，导致某些分组过 大的a c l 链路数据无法在两个s c o 时隙之间发送，造成时隙的浪费。而将分组分 得较小虽然有较大的传输机会，但小分组的传输速率较慢，因此，如何确定分组 的大小是个重要问题。目前已存在的s a r 策略有：随机分配、i s a r 和p r s a r 等。 图1 2微微网与散射网 1 3 本文的研究内容 本文主要研究蓝牙系统中同一微微网内的调度策略，着重于分析各种调度策 略的优缺点、影响调度策略性能的主要因素以及相应的改进方法等。共分为五章， 第一章为绪论，介绍本课题的研究背景。第二章介绍蓝牙微微网的基本特性，着 第一章绪论 重介绍其在链路和分组方面的特点。第三章介绍传统的调度策略和s a r 策略，通 过分析比较，指出各种策略的优缺点。在第四章中，提出了一种新的调度策略， 并把该策略与传统的策略进行比较，同时分析了新的调度策略的性能。第五章是 仿真实验，将新提出的策略与一种s a r 策略结合在一起，组成完整的调度策略， 进行仿真实验，并将结果与其他策略进行比较。 第二章蓝牙的链路层及特点 第二章蓝牙的链路层及特点 蓝牙的链路层主要包括基带层和l m 层，它的主要作用是定义蓝牙链路、数 据分组的格式和数据分组的传输方式等，蓝牙系统的调度策略就工作在这层， 因此，熟悉蓝牙的数据链路层及其特点对于研究调度策略有很重要的作用。本章 将就蓝牙的数据链路层中对于调度策略起重要作用的部分进行详细的描述。 2 1 蓝牙基带协议 2 1 1 基带协议概述 基带就是蓝牙的物理层，它负责管理物理信道和链路中除了错误纠正、数据 处理、调频选择和蓝牙安全之外的所有业务。基带在蓝牙协议栈中位于蓝牙无线 电之上，基本上起链路控制和链路管理的作用，比如承载链路连接和功率控制这 类链路级路由等。基带还管理异步和同步链路、处理数据包、寻呼、查询接入和 查询蓝牙设备等。基带收发器采用时分复用t d d 方案( 交替发送和接收) ，因此 除了不同的跳频之外( 频分) ，时间都被划分为时隙。在正常的连接模式下，主 单元会总是以偶数时隙启动，而从单元则总是从奇数时隙启动( 尽管他们可以不 考虑时隙的序数而持续传输) 。蓝牙的调度策略如果按照协议栈的层次来分的话， 是运行在基带层的。 2 1 2 物理信道与时隙 蓝牙技术使用了跳频扩频技术，跳频速率为每秒1 6 0 0 次，即每隔6 2 5 u s 变 换一次频率，频率的变化规律是由微微网中主结点的蓝牙设备地址决定的，因此 每个微微网只有唯一的一个跳频序列，该跳频序列称为物理信道。 物理信道被分为许多个时隙，每个时隙的长度为6 2 5 u s ，因此，在同一个时 隙中，频率是不变的。时隙根据微微网中主结点的蓝牙时钟进行标号，范围从0 到2 2 7 1 ，超出后，重新从0 开始记数。m s 结点之间的数据传输是从时隙的起始 处开始的 蓝牙的数据传输模式称为主结点驱动的半双工t d d 模式( 图2 - 1 ) ，数据是以 分组的形式进行传输的，每个分组可以占用一个时隙或多个时隙( 图2 - 2 ) 。主结 点在偶数时隙传输数据，从结点只能在奇数时隙传输数据。从结点无法自主的将 第二章蓝牙的链路层及特点 数据传输给主结点，只有在前一个m s 时l r g , 收到发给从结点的信息后，该从结点 才能在下一个s m 时隙中向主结点发送信息。所以，一切数据传输活动都是由主 结点驱动的，从结点之间不能直接发送数据。 2 1 3 物理链路 图2 - 1t d d 传输模式 蓝牙微微网中主结点和从结点之间可以建立不同类型的链路。蓝牙协议定义 了两种类型的物理链路：同步面向连接链路( s c o ) 和异步无连接链路( a c l ) 。 s c o 链路是对称的、点到点的链路。$ c 0 链路是预留时隙的，每隔固定的时 隙数后，该s c o 链路必须被调度一次。同一个微微网内，主结点最多只能建立最 多三条到不同从结点的s c o 链路，而从结点最多只能建立三条到同一个主结点的 s c o 链路。s c o 链路主要用于语音数据的传输。 a c l 链路是非对称的( 即m s 链路与s m 链路的传输速率不同) 、一点到多点的 链路。它提供了同一微微网内主结点到所有活动的从结点之间的分组交换。主结 点到同一个从结点只能有一条a c l 链路。a c l 链路工作在除了为s c o 链路保留利 隙以外的时隙。 2 1 4 逻辑信道 蓝牙有五种逻辑信道，他们可以用来传输不同类型的信息。l c ( 控制信道) 和l m ( 链路管理) 信道用于链路层，而u a 、u i 和u s 信道则用于携带异步、类 异步和同步用户信息。逻辑信道只是一种抽象的信道，它们并不是实实在在存在 的信道，它们的最终实现，即对数据的传输还是需要借助物理信道来实现的。因 此，逻辑信道可以说是物理信道上一层的概念。 第二章蓝牙的链路层及特点 垫理! - ； 竹1 ；f ( 1 ： k + 勤：n k + 秘：t ( k + 4 1 ： f ( k + 5 7 ：f f k + 固： 旧旷 iml嗣 ； ； ； ： f f k 、 ：h k + 釉：帆+ 4 1 ：f ( k + 5 1 ；f ( k + b ) ： 川j ! 1 r n r j ； ； 1 i l k ) ；f ( k + 5 j ；f | k + 6 i l f 1 厂 i ：； ： ； 2 2 蓝牙分组 图2 - 2多时隙分组 2 2 1 蓝牙分组的结构 蓝牙的数据传输是以分组为单位的。蓝牙分组虽然有多种类型，但其基本结 构是相同的。( 图2 3 ) 从图中可见，蓝牙分组可分为三个部分，即接入码、分组头和载荷。 2 2 1 1 接入码( a c c e s sc o d e ) 图2 - 3蓝牙分组的基本结构 接入码是一个蓝牙分组必须包含的部分，它主要用于同步和分组的识别。共 有三种不同类型的接入码，即信道接入码( c h a n n e la c c e s sc o d e ) 、设备接入码 ( d e v i c ea c c e s sc o d e ) 和查询接入码( i n q u i r ya c c e s sc o d e ) 。 信道接入码用于蓝牙数据传输过程中标志同一微微网，同一微微网内传输的 数据具有相同的信道接入码；设各接入码用于蓝牙设备间建立连接的寻呼( p a g e ) 子过程；查询接入码用于蓝牙设备间建立连接的查询( i n q u i r y ) 子过程，查询接 入码分为通用查询接入码( g i a c ) 和专用查询接入码( d i a c ) ，g i a c 用于查询过程中 第二章蓝牙的链路层及特点 发现射频范围内的一个蓝牙设备，而d i a c 用于查询过程中发现射频范围内的具有 共同特征的一类蓝牙设备。图2 4 是接入码的基本格式。 图2 4接入码的基本格式 其中的p r e a m b l e 段和t r a i l e r 段都是用于动态d c 补偿，其基本格式如下 图2 - 5p r e a m b e 的格式 2 2 t 2 分组头( h e a d e r ) 分组头总共有1 8 b i t ，由于采用i 3 f e c 编码，形成共有5 4 b i t 的分组头。 a n a d d r 段用于区分同一微微网中活动状态的从结点，由于同一微微网中多 个从结点连接到同一个主结点，因此，用3 b i t 的a “_ a d d r 段可以标志每一条活 动的m s 链路。 t y p e 段标志分组的类型，下一节将详细描述。 f l o w 位用于a c l 链路的流控制。 a r q n 位类似于t e p i p 的a c e 位，用于接收方对于源发送方的回应，以表明 它是否正确收到发送方发送的分组。a r q n 位为1 ，表示正确接收分组；a r q n 位 为0 ，则表示分组接收失败，需要重传。 s e q n 位用于对接收到的相同的分组进行排序编号。例如，接收方正确接收 某一分组a 后，把下一个它将发送的分组b 的a r q n 位标为1 ，并向发送方传送， 若由于某种原因，发送方并末接收到分组b ，发送方将错误的认为接受方没有收 到分组a ，于是重新发送a ，并将分组a 的s e q n 位标为1 ，这样接收方可能收到 两个相同的分组a ，唯一的区别是其中一个的s e q n 位为0 ，另一个的为1 ，这样， 接收方就能根据s e q n 位丢弃该位为l 的分组。 h e c 段用于整个分组头的出错检验。这在各种网络协议的数据报头中都是很 常见的。 第二章蓝牙的链路层及特点 图2 - 6t r a i l e r 的格式 图2 7分组头格式 2 2 2 蓝牙的分组类型 蓝牙的分组类型有分组头的t y p e 字段决定，4 b i t 的t y p e 字段共可决定1 6 种类型的分组。蓝牙的分组类型是随着物理链路的不同而不同的，因此，对于每 一种物理链路( s c o 或a c l ) ，都有1 6 种分组，其中有4 种分组二者是相同的，这 些分组主要用于传输控制信息，另外1 2 种分组由不同的物理链路各自定义。 4 b i t 的t y p e 字段决定1 6 种分组，这些分组可依次被分为四类。第一类包 含4 中分组( 0 0 0 0 0 0 1 1 ) ，它们的具体类型都已经预先定义，用于传送控制信息 的分组，占用i 个时隙。第二类包含6 个占用1 个时隙的数据分组。第三类包含 4 个占用3 个时隙的分组。第四类包含2 个占用5 个时隙的数据分组。( 表2 一1 ) 以下重点介绍几个重要的控制分组。 i d 分组出设备接入码( d a c ) 或查询接入码( i a c ) 构成，共6 8 b i t ，用于蓝牙设 备间建立连接过程中的查询( i n q u i r y ) 和寻呼( p a g e ) 子过程。 n u l l 分组，顾名思义，是一种没有载荷( p l a y l o a d ) 的分组它只包含信道接入 码( c h a n n e lc o d e ) 和分组头( p a c k e th e a d e r ) 两个部分，固定长度为1 2 6 b i t 。n u l l 分组主要用于返回链路信息。例如，主结点在m s 时隙发送一个分组给从结点， 在紧接着的s m 时隙中，从结点若没有数据需要发送，它就发送一个n u l l 分组， 并包含f l o w 、a r q n 等信息位。 p o l l 分组是一种极为重要的分组，是蓝牙调度中最常用的分组，主结点在 没有数据发送给从结点时，发送一个p o l l 分组给从结点。p o l l 分组与n u l l 分 组极为类似，没有载荷( p l a y l o a d ) ，与n u l l 分组的最大区别是，结点在收到n u l l 分组时不需要发送一个分组回应，而从结点在收到主结点的p o l l 分组时，必须 发送相应的分组( 若有数据发送时，发送相应的数据分组，芽在分组头的相应位 塑三至堕堑塑壁堕星垦塑塞 标志从结点信息：若无数据发送，则发送n u l l 分组，也在分组头的相应位标志 从结点信息) 确认收到，同时报告结点信息。 表2 一l蓝牙分组的类型 t y p c o d e s 钼m e r i t b 3 b 扣扣o s t o t o c c u p a n c y s e o f n k矗e l l i n k 0 0 0 01n u l l n l i l l 0 0 0 11p o l l p 0 l l 1 0 0 1 0 1f h sf h s 0 0 11d m ld m l 0 1 0 01u n d e f i n e dd h l 0 1 0 11h v lu n d e f i n e d 0 1 1 01h 2 u n d e f i n e d 0 1 1 11h y 3 u n d e l i n e d 1 0 0 01d vu n d e f i n e d 1 0 0 11u n d e f i n e da u x l 1 0 1 03u n d e f i n e dd m 0 1 0 1 13u n d e f i n e dd h 3 ， ”0 03u 1 d e l l n e du n d e f i n e d 1 1 0 13u n d e f i n e du n d e f i n e d 1 1 1 05u e d e f i n e dd m 5 4 1 1 1 15u n d e f l n e dd h 5 不同蓝牙分组的传输速率是不同的，表2 2 和表2 - 3 对不同的蓝牙分组的速 率进行了比较。 表2 - 2a c l 分组速率 a s y m m e 旨l c m a x 。 p a y | o a du s e rs y m m s t r i c r a t ek b t s ) h p _ 组d e r p a y l o a d 雠8 x r a t e t y p ef b y t e s )f b y t e s ) f e cc r c f 靶埘s ) f o p n a r dr e v e 0 m 11o r l 72 舟 y e s 1 0 881 0 881 0 80 d h l10 - 2 7 1 1 0 y e s 1 7 2 81 7 2 81 7 28 d m 320 - 1 2 12 舟 y e s 2 5 8 13 25 4 4 d h 320 - 1 8 3n o y e s 3 9 0 45 8 568 64 d m 520 2 2 42 n y e s 2 74 7 7 83 6 3 d h 520 3 3 9r i o y e s 4 3 3 。97 2 3 25 7 6 a u x l10 2 9 n o n o 1 8 561 8 561 o , 56 第二章蓝牙的链路层及特点 表2 - 3s c o 分组速率 s y m m e t r i c p a y l o a dh e a d m u s e rp 列l o a dm a x r a t e t y p e b y t e s f b y t e s ) f e cc r c ( k b s ) h v lr 1 91 01 f 3m6 4o h v 2n a2 02 1 3n o6 4 0 h v 3n a3 0 i 1 0n 06 40 d v 1d1 0 + ( 0 9 ) d2 f 3 dy e sd 6 40 + 5 76d 由表中的数据可见，对于a c l 链路，相同的数据选择不同的分组进行传送 其传输速率是不同的。 2 3 蓝牙链路的分组收发规则 2 3 1 蓝牙链路的数据发送规则 图2 - 8 是蓝牙链路中的数据发送部分，从图中可以看到，蓝牙链路的数据发 送部分主要由一系列的缓冲器和一个包发生器( p a c k e tc o m p o s e r ) 组成。包发生 器用于将数据打包。每一条s c o 链路和每一条a c l 链路都拥有各自不同的缓冲器， 分别称为t xs c o 和t xa c l 。主结点对于每一个从结点的t xa c l 的结构都是相 同的，由两个f i f o 寄存器组成，其中的c u r r e n t 寄存器用于向包发生器传输送 数据，而n e x t 寄存器则用于从蓝牙协议栈的上一层，即l m 层接收数据。两个开 关s l a 和s l b 决定这两个寄存器中哪一个是c u r r e n t ，哪一个是n e x t ，它们是不 会同时连接到同一个寄存器上的。 第二章蓝牙的链路层及特点 图2 - 8 蓝牙链路的数据发送 数据的传输过程是这样的：首先，蓝牙的l m 层将有关下一个要发送的分组 的信息( 接入码、分组头和相应的数据) 装入s l a 所指向的寄存器，之后，s l a 和 s l b 同时改变指向，n o l o 装入数据的寄存器经由s l b 指向包发生器，即成为 c u r r e n t 寄存器。当传输时隙到达时，包发生器读入c u r r e n t 中的信息，并根据 其中分组头中的t y p e 字段构建一个有效载荷，再把该有效载荷接到分组头之后， 就形成一个完整的蓝牙分组，经过蓝牙硬件的射频单元将该分组发送出去。当发 送结点收到a c k 信息时，s l a 和s l b 同时换位，为下一次传输作准备；若结点收 到n a k 信息，则s l a 和s l b 暂时不换位，因为要进行数据的重发。若传输时隙时 隙到达时，c u r r e n t 中并无数据，则包发生器自动产生一个n u l l 分组并投送出 去。 由此可见，蓝牙的数据发送规则的效率还是很高的，每条链路只需使用两个 缓冲寄存器，使用两个不同时指向一个寄存器的开关的进行调控，能自动完成分 组的传输和分组重传。 2 3 2 蓝牙链路的数据接收规则 图2 - 9 描述了蓝牙链路的数据接收部分，它的基本结构与数据发送部分大致 相同，但是，就主结点来说，它只有一个r xa c l 缓冲器，所有m s 链路共用该缓 冲器，这与发送部分中，主结点中每一条m s 链路都拥有各自独立的发送缓冲器 是不同的；同时，发送部分和接收部分的数据流向是相反的，并且，发送部分的 包发生器由这里的包分解器所取代。 数据的接收过程与发送过程相似，先由包分解器根据接收到的分组的分组 头的t y p e 字段，分辨出该分组是s c o 分组还是a c l ，并把它送到相应的缓冲寄 存器中，此后的工作由l m 层控制完成，它不断从n e x t 寄存器中读走数据，并传 送到上一层的蓝牙协议进行处理，同时，它也根据控制的需要，不断的发出命令 变换开关s 1 ，使c u r r e n t 和n e x t 的状态不断的相互切换。 2 3 3s 0 0 链路的数据收发规则 以上主要描述的是a c l 链路的发送接收规则，对于s c o 链路，收发规则相 同。主结点中的每一条s c o 链路可以拥有自己单独的缓冲寄存器，或者多条的 s c o 链路共用一个缓冲寄存器，所有s c o 分组的收发操作都是在t x s c o 和r xs c o 中进行的。 第二章蓝牙的链路层及特点 图2 - 9 蓝牙链路的数据接收 第三章蓝牙系统调度策略的分析 第三章蓝牙系统调度策略的分析 作为一个由若干结点组成的蓝牙系统，它可能只包含一个微微网，也可能存 在一个由若干微微网组成的散射网，微微网内的调度和微微网间的调度是截然不 同的，需要制定不同的调度策略加以对待。同一个微微网内的调度，归根结底就 是对该微微网内a c l 链路的调度，因此，不同的链路环境会对调度策略提出不同 的要求。如，某些微微网中支持一条或数条s c o 链路，在研究对a c l 链路的调度 时，就应该充分考虑s c o 预留时隙对调度策略的影响。本文主要研究的是在考 虑s c o 预留时隙的情况下，微微网内主结点对各个从结点的调度策略。 蓝牙协议中定义的调度策略是轮询策略( r o u n dr o b i n ) ，由于其效率不高， 因此，人们又研究出几种效率更高的调度策略。本章在介绍轮询策略的基础上， 将介绍这几种新的调度策略。 3 1 几种常见的调度策略 3 1 1 轮询策略( r o u n dr o b in ) 轮询策略( 以下简称r r ) 是一种最为简单的调度策略，它非常适合蓝牙系统 这种主结点驱动的时分多路的链路模式。 r r 策略的基本原理( 图3 - i ) 是：主结点按照固定的循环序列( 如：若有三条 m s 链路，编号分别为i 、2 、3 ，则主结点按照循环序列1 2 3 1 2 3 1 2 3 进行调度) 每一条链路，在每一个可传输m s 时隙的开始处，主结点对于它调度的从结点若 有数据可传输，则选定恰当的分组类型进行传输，若无数据可传，则向从结点传 送一个p o l l 分组；从结点收到主结点的分组后，在下一个s m 时隙，它将获得数 据的传输权，此时，若从结点没有数据可传输，则它向主结点传输个n u l l 分 组，作为对主结点的应答，同时可向主结点反映从结点的状态信息( 如：f l o w 位 的信息等) 。 r r 策略的最大优点是简单且易于实现，但是它在某些情况下却大量浪费系 统的时隙。第一种情况是，某些有大量数据需要传送的链路还没有调度，而系统 却正在调度一些没有数据可供传送的m s 链路。在这种情况下，系统一方面白白 浪费时隙忙于发送和接收p o l l 分组和n u l l 分组，另一方面，某些有大量数据需 要传输的链路却可能因为迟迟得不到调度而发生丢包的现象。第二种情况与第一 种情况类似，由于蓝牙系统出于节能方面的考虑，某些从节点可暂时退出微微网， 第三章蓝牙系统调度策略的分析 处于休眠模式。由于主结点的r r 调度序列是按照微微网建立时所拥有的从结点 决定的，并不考虑中途暂时退出者，因此以固定的调度策略向暂时退出的从结点 发送p o l l 分组显然是毫无意义的。 卜1 a s t e r s l a v e1 图3 - 1r r 策略的原理 为了评价某一种调度策略的性能，在蓝牙系统中采用了吞吐率( t h o u g h o u t ) 这样一个评价指标，它的含义是系统中有用时隙与系统的总时隙之间的比值。设 有一个n ( n p 3 ) 。 ( 2 ) 调度策略以轮询的方式访问各条链路。当轮询到某一条链路时，若其优 先级数为p ，则为它服务4 p 个时隙：若在这4 p 个时隙过程中，链路的优 先级改变，则立即停止服务，转向下一条链路。 由此可见，h o lp p 的实现并不比p p 复杂多少，其最关键的部分是有关参数的 选择，即优先级数p 到底要选多少才合适，p 的值将极大的影响系统的性能。通过 对不同的p 值进行实验表明，当p l = 2 ，p 2 = 1 5 时，系统能达到最好的性能，此时， p 1 与p 2 的比值为4 3 。对于p 3 ，系统将给予一个恒定的优先级数1 ，即对于第三优 瞄，3。3 ， h 3 ，3 2s o l l 3 s a ，03， e( 第三章蓝牙系统调度策略的分析 先级的链路，系统将服务4 个时隙。对于0 0 链路的情况，与p p 相同，也是浪费一 个时隙向从结点发送p o l l 分组。 与p p 相同，h o lp p 的主要缺点也是公平性问题。由于高优先级的过度剥夺资 源和低优先级的过多让出资源而引起的调度不公平性将在一定程度上影响系统 的性能，这在h o lp p 上是无法避免的。解决的方法与讨论p p 时相同，依然是引入 k f p ，这样就形成了更具效率的h o lk f p 。 3 2 3 2h e a do fl in ek f a i t n e s sp o ii c y h e a do fl i n ek - f a i r n e s sp o l i c y ( 以下简称为h o lk f p ) 改自k f p ，它是k f p 与上一节所述的优先级分类标准相结合的产物，这使得该策略既能适应s c o 保留 时隙的影响，又能避免类似p p 的调度不公平的现象，因而是当前调度效率最高的 一种调度策略。当然，有得必有失，h o lk f p 的高效率是以其复杂的过程为代价 的，k f p 已经够复杂了，而h o lk f p 在k f p 的的基础上，又加上了细分优先级和与 之相应的一系列配套措施，因而，h o lk f p 的复杂程度是可想而知的。 正直i j k f p 策略与p p 策略的区别一样，h o lk f p 与h o lp p 的主要区别也在于增加 了公平因子k 。以下简述h o lk f p 的主要实现过程： ( 1 ) 处于第一优先级的链路按照它的优先级数安排服务时间。 ( 2 ) 在a m a x q m i n t y p e ) c a s e b t m 1 ： c u r r e n t s t a t e m a s t e r s t a t e = l ； b r e a k ； c a s e b t _ d h i ： c u r r e n t s t a t e m a s t e r s t a t e = l ： b r e a k ： c a s e b t d m 3 ： c u r r e n t s t a t e m a s t e r s t a t e = 3 ； b r e a k ： c a s eb td h 3 ： c u r r e n t s t a te _ m a s t e r s t a t e = 3 ； 第五章改进结果的验证 b r e a k ； 链路状态改变或服务时间已到时，都要使用对齐规则进行 一次判断，已确定是继续服务还是调度下一条链路$ i f ( ! ( ( c u r r e n t s t a t e m a s t e r s t a t e = = l i n k - s t a t e j m a s t e r s t a t e ) & & ( c u r r e n t s t a t e s l a v e s t a t e = = l i n k s t a t e j _ s l a v e s t a t e ) ) 1ls e r v e r ti m e = = o ) i f ( f i s o r d e r 0 ) i f ( io r d e r c o u n t ) q u e u e n o = n e x t a c t