（计算机软件与理论专业论文）蓝牙自组个人局域网形成算法研究及仿真.pdf

中国科学技术大学工学硕士学位论文 摘要 蓝牙技术规范提供了一种开放的无线语音和数据通信标准，是移动通信 技术和计算机网络技术结合的产物。蓝牙作为一种低成本、低功耗的无线接 入方式，在现代通信技术和应用发展中有良好的前景。 蓝牙自组个人局域网是由某个区域内的蓝牙设备组成的一个不需额外网 络设施，在一起自组协调工作，相互间自由通讯的独立无线移动网络。这种 网络很有可能改变我们在不远的将来处理和存取信息的方式，具有广阔的应 用前景。为实现这种网络还需要解决许多有挑战性的课题，网络形成问题就 是其中的一个。蓝牙在物理层上采用了跳频扩频技术，而且要求蓝牙网络必 须由一个个微微网组成，这些特殊限制给蓝牙自组个人局域网形成带来了挑 战。 论文深入研究了蓝牙自组个人局域网的特性，分析和比较了前人在解决 该课题时所提出的各种主要算法，并给出了l a w 算法在n s 2 模拟器上的 实现过程。仿真试验证明，l a w 算法具有以下性能：时间复杂度为 o ( 1 0 9 n ) ，消息复杂度为o ( n ) ，创建的散射网网络直径为o ( 1 0 9 n ) 。 论文对l a w 算法中的设备发现过程及来自非协作设备的干扰进行了分 析，提出了一种改进的方案。该方案利用c o d ( 殴备类型) 字段，在设备 发现过程结束前识别出非协作设备，并阻止它们参与到设备发现过程中来， 从而加速了此过程。将该改进方案和蓝牙规范中的方案进行了对比仿真试 验，结果表明，在有非协作设备干扰的环境中，改进后的方案基本消除了非 协作设备的干扰，加速了设备发现的过程，最终加快了组网速度。 关键词蓝牙，自组网络，个人局域网，散射网，形成 窒垦坠兰薹查查兰三兰堡圭兰堡兰圣 一 a b s t r a c t t h eb l u e t o o t ht e c h n o l o g yi sac o m b i n a t i o no fm o b i l ec o m m u n i c a t i o na n d c o m p u t e rn e t w o r k ，w h i c hp r o v i d e sa no p e ni n t e r n a t i o n a ls p e c i f i c a t i o no fw i r e l e s s a u d i oa n dd a t ac o m m u n i c a t i o n m o r e o v e r , t h i st e c h n o l o g ye n a b l e st h ew i r e l e s s a c c e s sw a yw i t hl o w c o s ta n dl o wc o n s u m e dp o w e r , w h i c hk e e p sw i t ht h et r e n d o ft h ed e v e l o p m e n to ft h ea d v a n c e dc o m m u n i c a t i o nt e c h n o l o g y b l u e t o o t ha dh o cp e r s o n a la r e an e t w o r k ( p a n )i sa ni n d e p e n d e n t w i r e l e s sn e t w o r kc o m p o s e do fb l u e t o o t h e n a b l e dm o b i l ed e v i c e s ，w h i c hc a n f r e e l yc o m m u n i c a t ea n dc o l l a b o r a t ew i t he a c ho t h e ri ns o m ea r e aw i t h o u te x t r a i n f r a s t r u c t u r e t h i sk i n do fn e t w o r km a yc h a n g eo u rw a yo fd e a l i n gw i t ha n d s t o r i n gi n f o r m a t i o ni nt h en e a rf u t u r ea n dh a sp r o m i s i n gp e r s p e c t i v eo fw i d e a p p l i c a t i o n s b e f o r e i tb e c o m e sr e a l i t y ，m a n yc h a l l e n g i n gi s s u e ss h o u l db e a d d r e s s e d b l u e t o o t hs c a t t e m e tf o r m a t i o ni so n eo ft h e s em a i ni s s u e s b l u e t o o t h r e l i e so nf r e q u e n c yh o p p i n gm e c h a n i s m ，a n dn o d e ss h o u l dj o i nap i c o n e tb e f o r e t h e yc a nc o m m u n i c a t ew i t he a c ho t h e r a l lt h e s el i m i t a t i o n sa r ec h a l l e n g e st ot h e f o r m a t i o no fp e r s o n a la r e an e t w o r k t h et h e s i sr e s e a r c h e si n t ob l u e t o o t ha dh o cp e r s o n a la r e an e t w o r k ，a n a l y z e s a n dc o m p a r e st h em a i na l g o r i t h m sa n ds c h e m e so ft h e s ei s s u e sr e s e a r c h e r sh a v e c u r r e n t l yp r e s e n t e d t h et h e s i sp r e s e n t s t h el a wf o r m a t i o n a l g o r i t h m ，a n d a n a l y s i s t h ei m p l e m e n t a t i o ni nn s 2 ，t h e nv a l i d a t e sw i t he x p e r i m e n t st h a tt h e a l g o r i t h mh a st h ef o l l o w i n gr e s u l t s ：o ( 1 0 9n jt i m ec o m p l e x i t y ，0 陋) m e s s a g e c o m p l e x i t ya n do ( 1 0 9 ，l jd i a m e t e ro ft h ec o n s t r u c t e ds c a t t e r n e t a tl a s t ，t h i st h e s i sp r o v i d e sa ni n s i g h to nd e v i c ed i s c o v e r yo fl a w a l g o r i t h ma n dp r o p o s e sa ne n h a n c e da p p r o a c hu s i n gt h ec o df i e l dt od i s t i n g u i s h n o n - c o o p e r a t i n gd e v i c e sb e f o r et h e ya r ed i s c o v e r e d ，w h i c hc o u l ds p e e d u pt h e p r o c e s so fd e v i c ed i s c o v e r y t h es i m u l a t i o n ，c o m p a r i n gt h eo r i g i n a la n dt h e p r o p o s e ds c h e m e ，p r e s e n t st h eb e n e f i t so f o u rn e w a p p r o a c h k e y w o r d s b l u e t o o t h ，a dh o c ，p a n ，s c a t t e r n e t ，f o r m a t i o n - i i 中国科学技术大学工学硕士学位论文 1 1 概述 第1 章绪论 蓝牙【1 是一种短距离无线数据与语音通信的开放性规范，它是由蓝牙特别 兴趣组织( b l u e t o o t hs i g ) 发起和制订的。蓝牙技术具有成本低、功耗低、尺寸 小、占用免费频段和通讯距离短等特点。它在许多领域逐渐得到广泛应用，如 计算机、通信、汽车、医疗、军事等。具备蓝牙功能的数字设备也逐渐增多， 如笔记本、移动电话、p d a 、键盘、m p 3 播放器以及其它各类数字设备。虽然 蓝牙技术最初目的是取代电缆，但基于蓝牙技术的组网技术也在快速发展当 中。 蓝牙可以提供点到点或者点到多点的组网形式。蓝牙技术中并没有基站的 概念，在有效的通信范围内，所有设备的地位都是平等的，但在底部传输层上 有主从设备之分【2 】，首先提出通信要求的设备为主设备或者主节点 ( m a s t e r ) ，被动进行通信的设备为从设备或从节点( s l a v e ) 。一个主设备最多 可以同时和7 个活动从设备进行通信，这些设备共享一个通信信道，这样的网 络称为微微网( p i c o n e t ) 。多个微微网在时间和空间上的重叠则构成散射网 ( s c a t t e r n e t ) 。 蓝牙自组个人局域网络饵l u e t o o t ha dh o cp e r s o n a la r e an e t w o r k s ，或者简 称为蓝牙自组网，蓝牙p a n 等) 是由蓝牙设备组成的一个不需要额外网络设 施，相互间可以自由通讯的独立无线网络 3 。它可以是一个微微网，也可是多 个微微网互连组成的散射网。这种个人局域网络不需要手工配置，也不需要电 缆和其他有线设施，而且蓝牙设备可以随时加入或者离开网络。蓝牙p a n 在 临时会议，联机游戏，传感器网络等方面有着重要的应用价值。 蓝牙p a n 形成( f o r m a t i o n ) 问题是指，如何将一组彼此分离的蓝牙节点 连接起来形成一个散射网，所以蓝牙p a n 形成问题也称蓝牙散射网形成问 题。这些蓝牙节点在开始的时候都不知道周围邻居设备的存在，需要通过设备 发现过程来发现邻居设备，获得对方的跳频序列等信息并建立点到点的连接。 蓝牙p a n 本质上是基于蓝牙的a dh o c 网络，虽然a dh o c 网近年来一直都是研 究热点，但其网络形成问题并没有吸引较多的关注，原因在于几乎所有的a d h o c 网都假设是在共享信道和以广播机制为基础的无线媒介上建立起来的，在 中国科学技术大学工学硕士学位论文 这种网络中，设备间的距离关系基本上确定了其拓扑结构 3 】。但在利用蓝牙技 术组建a dh o c 网时，蓝牙自身具有的一些特点对网络拓扑的形成提出了新的 挑蛳4 蓝牙技术在物理层采用跳频扩频技术，因此，蓝牙设备在通信之前必须同 步彼此的跳频模式；蓝牙网络必须由微微网组成，任何两个节点如果不在同一 个微微网内则无法直接通信，各个微微网由不同的跳频序列来区分：在媒体接 入控制( m a c ) 上采用时分双工形式：设备之间的底层通信严格遵从主从设 备方式。 这些特点都决定了蓝牙p a n 需要有自己特有的网络形成算法。目前蓝牙 规范尚未对蓝牙微微网之间的通信和基于蓝牙的a dh o c 网络形成等内容做出 具体描述。作为一个开放性问题，在最近几年里，许多学校、研究机构和公司 就蓝牙p a n 的形成问题展开了广泛和深入的研究工作。 1 2 研究现状 现有的一些文献提出了各种基于蓝牙的p a n 网络形成算法，如t s f ( t r e es c a t t e m e tf o r m a t i o n ) 【5 】、b s f a 6 、b t c p ( b l u e t o o t ht o p o l o g y c o n s t r u c t i o n p r o t o c 0 1 ) 【7 】、b l u e t r e e s 8 、b l u e t r e e 9 】、b l u e n e t 1 0 】、 b l u e s t a r s 1 1 、b l u e m e s h 1 2 】、y a o 1 3 、s c a t t e r n e t r o u t e 1 4 并 1b l u e r i n g 1 5 等。可以从不同的角度对这些算法进行分类，例如： 根据是否在有业务出现时爿+ 开始形成网络，可分为按需( o n d e m a n d ) 形 成和预先形成两大类。大部分已有算法都属于预先形成，只有s c a t t e m e t r o u t e 采用了按需形成； 根据是否在网络形成算法中结合考虑了路由、调度等其他问题，可分为 综合的和独立的两大类。现有算法中，b l u e t r e e 的出发点就是得到一种易于路 由的网络结构； 根据所采用的链路形成算法是否具有对称性，可分为对称和非对称链路 散射网形成算法两大类。很多现有算法都采用了文献 1 6 中提出的对称链路形 成方法； 根据是否要求所有的设备都处于相互的无线电传输范围之内，可分为单 跳拓扑类型和多跳拓扑类型。前者限制了设备的地理分布，通用性较后者差； 根据网络形成完毕后的形状进行分类，可分为树形、网状、线形、环形 等。现有算法中树形占多数。 中国科学技术大学工学硕士学位论文 同时考虑跳数和拓扑形状，可以将这些算法分类如下 f 一一e 。一e f 邕二。 l ； 图1 基于蓝牙的a dh o c 网络形成算法分类 1 3 本文工作内容 本论文的主要工作是： 1 对现有的一些蓝牙p a n 形成算法进行了广泛的调研与分析，重 点讨论其中有代表性的几种算法，如b t c p ，l a w ，b l u e t r e e s ， t s f 等算法。 2 对n s 2 及基于n s 2 的蓝牙模拟器的原理和结构进行深入分析。 重点讨论了n s 2 中的分裂对象模型和事件调度机制，这些都是 理解n s 2 工作原理的基础，也是后面实现l a w 算法的基础。 3 对l a w 算法进行了详细的描述，并在n s 2 中实现了该算法。 中国科学技术大学工学硕士学位论文 对l a w 算法进行了仿真试验，通过实验得到l a w 算法的时间 消息复杂度，以及形成的散射网的网络直径，微微网个数等指 标。 在深入分析设备发现过程的基础上，对l a w 算法中的设备发现 过程进行了改进，在n s 2 中实现了改进方案，并将该改进方案 与蓝牙标准中的设备发现方案进行对比。 1 4 本文组织结构 论文共分为六章，组织结构为： 第一章，绪论：介绍本文的研究背景、研究目标、已有研究成果和文章 组织结构。本文主要研究实现蓝牙p a n 的拓扑形成问题。 第二章，蓝牙p a n 概论：介绍蓝牙技术的特点，比较分析了与之竞争的 其它几种短距离无线技术，给出蓝牙p a n 的特点、性能特性及应用场景。介 绍了目前蓝牙个人局域网络工作组的进展。 第三章，蓝牙p a n 形成算法研究：蓝牙物理链路建立过程是蓝牙p a n 拓 扑形成的基础，本章对这一过程作了介绍。对现有的蓝牙p a n 形成算法进行 了讨论，重点分析了b t c p ，l a w ，b l u e t r e e s ，t s f 等形成算法。对这些算法 的性能指标进行了总结对比。 第四章，n s 2 及蓝牙仿真模块u c b t 分析：分析了广泛应用的网络模拟 器n s 2 的架构，重点讨论了n s 2 中的分裂对象模型和离散事件调度模型，这 些是理解n s 2 工作原理，扩充新的网络构件的基础。u c b t 是一个新近发展起 来的，基于n s 2 的蓝牙仿真器，本章对u c b t 的结构进行了分析。l a w 算法 的实现是建立在对n s 2 和u c b t 结构的深入理解基础之上的。 第五章，l a w 算法仿真研究：对l a w 算法进行了详尽的描述，给出了 其在n s 2 中的实现，对其节点模型，初始化过程，消息传递机制以及散射网 形成过程中的重要数据结构，重要函数进行了剖析。给出了l a w 算法仿真实 验的结果。本文提出了一种对l a w 算法中的设备发现过程进行改进的方案。 第六章，结论与展望，总结论文的主要工作，展望未来工作的方向。 中国科学技术大学工学硕士学位论文 第2 章蓝牙自组个人局域网概述 2 1 蓝牙技术概述 2 1 1 蓝牙技术简介 蓝牙己成为短距离无线数据通讯的事实标准，它是i e e e 8 0 2 1 5 1 标准的基 础。蓝牙b l u e t o o t h 取白中世纪北欧一个国王的绰号，他将丹麦所有小岛王国 以及瑞典和挪威南部组成了一个统一的国家。将这种新的无线技术命名为蓝牙 的意图在于希望它能将所有不同的设备连接起来并在一起有效工作【2 】。蓝牙特 殊兴趣小组s i g 幅p e c i a li n t e r e s tg r o u p ) 是由e r i k s s o n ，n o k i a ，t o s h i b a ，i n t e l 和 i b m 五家公司在9 8 年5 月成立的工业标准化组织，该组织的目标是要将这种 全球统一的短距离无线通信技术标准推向市场。随后有m o t o r o l a ，a g e r e ， m i c r o s o f t 和3 c o m 四家公司和最初五家公司一起成为蓝牙技术的发起者，它们 和全球其他2 4 0 0 多家公司一起加入到蓝牙技术的开发和推广中，使蓝牙技术 实际成为一个短距离无线通信的全球标准。 在短短三年时间里，蓝牙s i g 发展成为拥有2 4 9 1 个世界著名企业成员的 世界标准化组织。这说明基于此项蓝牙技术的产品具有广阔的应用前景和巨大 的潜在市场。但是，由于推广成本高、性能无法满足应用需求、和8 0 2 1 1 之间 存在干扰、兼容性未得到有效解决等问题，蓝牙并没有得到大面积的普及。到 2 0 0 4 年，蓝牙的应用才算是高速启动，市场发展颇为迅猛。2 0 0 4 年1 1 月份， 蓝牙2 0 版本颁布，意味着蓝牙技术进入新的发展阶段。2 0 0 6 年，s i g 正式宣 布下一版本的蓝牙将整合i n t e l 的u w b ( u l t r a w i d e b a n d ) ，届时蓝牙的传输速率 有望达到4 8 0 m b p s 1 7 1 。 蓝牙规范( 1 1 版本) 采用全球统一的2 4 g h z 的i s m 频段和跳频扩频技 术，它的传输距离为1 0 1 0 0 r n ，跳频物理信道上划分间隔为6 2 5 u s 的时隙，带 宽为1 m b p s ，支持6 4 k b p s 实时同步话音传输和异步数据传输。蓝牙提供了多 种用途的节能模式，使蓝牙设备功耗小。蓝牙提供了认证、加密和密钥管理等 功能，在链路层提供了安全机制。蓝牙支持点对点和点到多点的连接，可形成 灵活复杂的网络拓扑结构。蓝牙技术已经被公认为最有前途的个人局域网技术 【3 。 中国科学技术大学工学硕士学位论文 2 1 2 蓝牙协议栈 蓝牙技术规范的目的是使符合该规范的各种应用之间能够实现互操作。互 操作的远端设备需要使用相同的协议栈 1 】，不同的应用需要不同的协议栈但不 是任何应用都必须使用全部协议，而是可以只使用其中的- - y u 或多列。不过， 所有的应用都要使用蓝牙技术规范中的数据链路层和物理层协议。 图2 蓝牙协议栈 完整的协议栈包括蓝牙专用协议( 如链路管理协议l m p 和逻辑链路控制 应用协议l 2 c a p ) 以及非专用协议( 如对象交换协议o b e x 和用户数据报协 议u d p ) 。设计协议和协议栈的主要原则是尽可能利用现有的各种高层协议， 保证现有协议与蓝牙技术的融合以及各种应用之间的互操作，充分利用兼容蓝 牙技术规范的软硬件系统。蓝牙技术规范的开放性保证了设备制造商可以自由 地选用其专用防议或习惯使用的公共协议，在蓝牙技术规范基础上开发新的应 用。 蓝牙协议体系中的协议按s i g 的关注程度分为四层：核心协议： b a s e b a n d 、l m p 、l 2 c a p 、s d p ；电缆替代协议：r f c o m m ；电话传送控制 协议：t c s b i n a r y 、a t 命令集；选用协议：p p p 、u d p t c p i p 、o b e x 、 w a p 、v c a r d 、i r m c 、w a e 。除上述协议层外，规范还定义了主机控制器接口 中国科学技术大学工学硕士学位论文 ( h c i ) ，它为基带控制器、链路管理器、 口。在图2 中，h c i 位于l 2 c a p 的下层 上 2 。 硬件状态和控制寄存器提供命令接 但实际上h c i 也可位于l 2 c a p 之 蓝牙核心协议由s i g 制定的蓝牙专用协议组成。绝大部分蓝牙设备都需要 核心协议( 加上无线部分) ，而其他协议则根据应用的需要而定。 1 蓝牙核心协议 基带层协议( b a s e b a n d ) ：基带层决定了蓝牙的空中接口。同时，它还定 义了设备之间相互查找的过程和建立连接的方式。基带层为设备定义了主从角 色，也定义了如何形成通信设备所使用的跳频序列以及几个设备共享空中接口 的有关规定。基带层提供了两种物理连接方式，即面向连接( s c o ) 和无连接 ( a c l ) ，而且，在同一射频上可实现多路数据传送。a c l 适用于数据分组， s c o 适用于话音以及话音与数据的组合，所有的话音和数据分组都有不同级别 的前向纠错( f e c ) 或循环冗余校验( c r c ) ，而且可进行加密。此外，对于 不同数据类型( 包括链路管理信息和控制信息) 都分配一个特殊通道。 链路管理协议( l m p ) ：该协议负责各蓝牙设备间连接的建立。它通过连 接的发起、交换、核实，进行身份认证和加密，通过协商确定基带数据分组大 小。它还控制无线设备的电源模式和工作周期，以及微微网内设备单元的连接 状态。 逻辑链路控制和适配协议( l 2 c a p ) ：浚协议是基带的上层协议，可以认 为它与l m p 并行工作，它们的区别在于，当业务数据不经过l m p 时，l 2 c a p 为上层提供服务。l 2 c a p 向上层提供面向连接的和无连接的数据服务，它采 用了多路技术、分割和重组技术、群提取技术。l 2 c a p 允许高层协议以6 4 k 字节长度收发数据分组。虽然基带协议提供了s c o 和a c l 两种连接类型，但 l 2 c a p 只支持a c l 。 服务发现协议( s d p ) ：服务发现在蓝牙技术框架中起着至关紧要的作 用，它是所有用户模式的基础。使用s d p 可以查询到设备信息和服务类型， 从而在蓝牙设备间建立相应的连接。 2 电缆替代协议( r f c o m m ) r f c o m m 是基于e t s i 一0 7 1 0 规范的串行线仿真协议。它在蓝牙基带协议 上仿真r s 一2 3 2 控制和数据信号，为使用串行线传送机制的上层协议( 如 o b e x ) 提供服务。 3 电话控制协议( t c s ) t c s 用来控制音频和数字业务的电话呼叫。 中国科学技术大学工学硕士学位论文 4 选用协议 选用协议是根据具体应用选择采纳的现有高层协议。蓝牙选用协议包括点 对点协议( p p p ) t c p u d p i p 、对象交换协议( o b e x ) 和无线应用d t x ( w a p ) 等。 2 2 其他短距离无线通信技术简介 2 2 1i r d a 红外线数据标准协会i r d a 1 8 ( i n f r a r e dd a t aa s s o c i a t i o n ) 致力于建立无线传 播连接的国际标准，i r d a 是一种利用红外线进行点对点通信的技术，其相应 的软件和硬件技术都比较成熟。现行的i r d a 传输速率为最新v f i r 的 1 6 m b p s ，相比原来f i r 的4 m b p s 快了4 倍。接收角度也由传统的3 0 度扩展到 1 2 0 度。具有移动通信设备所必需的体积小、功率低的特点。数据传输速率比 较高，由于采用点到点的连接，数据传输所受到的干扰较少，速率可达 1 6 m b p s 。 i r d a 也的确有不尽如人意的地方。首先，i r d a 是一种视距传输技术，也 就是说两个具有i r d a 端口的设备之间如果传输数据，中间就不能有阻挡物， 这在两个设备之间是容易实现的，但在多个电子设备间就必须彼此调整位置和 角度等。其次，i r d a 设备中的核心部件红外线l e d 不是一种十分耐用的 器件。 2 2 28 0 2 1 1 8 0 2 1 1 1 1 9 是由i e e e 制订的无线局域网标准，主要用于解决办公室局域网 和校园网中的用户与用户终端之间的无线接入。8 0 2 1 1 业务主要限于数据存 取，传输速率最高只能达到2 m b p s 。由于8 0 2 1 1 在速率上的不足，已不能满足 数据应用的需求，因此，i e e e 又相继推出了8 0 2 1 1 b 和8 0 2 1 l a 这两个新的标 准。三者之间技术差别主要在于物理层。m a c 层利用载波监听多重访问冲突 避免( c s m a c a ) 协议，而在物理层，8 0 2 1 1 定义了三种不同的物理介质：红外 线、跳频扩频方式( f h s s ) 以及直扩方式( d s s s ) 。 8 0 2 1 l b ( w i f i ) 工作在2 4 g h z 频段，最大数据传输速率为l l m b p s ，无需 直线传播。8 0 2 1 l b 的使用范围在室外为3 0 0 米，在办公环境中则最长为1 0 0 米。8 0 2 1 l b 使用与以太网类似的连接协议和数据包确认方式来确保可靠的数 据传送和网络带宽的有效使用。 中国科学技术大学工学硕士学位论文 8 0 2 1 l a 工作在5 g h zu n i i 频带，从而避开了拥挤的2 4 g h z 频段。物理 层速率可达5 4 m b p s ，传输层可达2 5 m b p s s ，采用正交频分复用( p f d m ) 的独特 扩频技术，可提供2 5 m b p s 的无线a t m 接口、1 0 m b p s 以太网无线帧结构接口 和t d d f r d m a 的空中接口，支持语音、数据、图像业务，一个扇区可接入多 个用户，每个用户可带多个用户终端。 8 0 2 1 1 系列虽然具备传输距离远和速度快等优点，但功耗和价格都比蓝牙 高，8 0 2 1 1 主要定位于企业无线局域网，它和蓝牙的市场定位不同。 2 2 3h o l n e r f h o m e r f 2 0 无线标准是由h o m e r f 工作组开发的，旨在家庭范围内，使 计算机与其他的电子设各之间实现无线通信的开放性工业标准。h o m e r f 是 i e e e 8 0 2 1 1 与d e c t 的结合，使用这种技术能降低语音数据成本。它使用开放 的2 4 g h z 频段，采用跳频扩频( f h s s ) 技术，跳频速率为5 0 跳秒，共有7 5 个 带宽为1 m h z 的跳频信道。 h o m e r f 对流媒体提供了真正意义上的支持。h o m e r f 把共享无线接入协 议f s w a p ) 作为未来家庭联网的技术指标，基于该协议的网络是对等网，因此 该协议主要针对家庭无线局域网。其数据通信采用简化的i e e e 8 0 2 1 1 协议标 准，沿用类似与以太网技术中的冲突检测的载波监听多址技术( c s m a c d ) 。 不过由于h o m e r f 技术没有公开，目前只有几十家企业支持，在抗干扰等 方面相对其他技术而言尚有欠缺，这些注定它没有广泛的应用前景。 2 2 4 短距离无线通信技术比较 i r d a ，8 0 2 1 1 ，h o m e r f 和蓝牙之间技术上的对比如下表所示 i r d a 8 0 2 1 1h o l l l e r fb l u e t o o t h 连接娄型 红外 扩频( 直接序列或扩频( 跳频) 扩频( 跳频) 者跳频) 频段8 5 0 n m 光 2 4 g h zi s m2 4 g h zi s m2 4 g h z1 s m 传输功率 1 0 0 m w1 0 0 m w1 0 0 m w1 m w 数据传输速率1 6 m b p s 1 2 m b p s ，是用直 1 2 m b o s1 m t , p s 接序列扩频可达 1 1 m b p s 通讯距离 1 米 1 0 0 米 1 0 1 0 0 来1 0 1 0 0 米 支持设各数 2 每个接入点可有多网络中可支持1 2 7每个微微网中可达 个设备，网络里可个设备8 个 有多个接入点 语音信道 l v o i c eo v e ri p可达6 个可达3 个 数据安全短距离和红外光束接入点和移动点问b l o w f i s h 加密算法 可用1 2 8 位密钥认 的窄角度提供了简通过w e p 盘问响证，8 - 1 2 8 位用于 单安全性：无其他应的认证方式；加加密 安全机制 密4 0 位 地址表示 3 2 位物理地址 4 8 位m a c 地址4 8 位m a c 地址4 8 位m a c 地址 表1 短距离无线通信技术比较 2 3 蓝牙自组个人局域网特性 2 3 1 微微网和散射网 蓝牙网络必须以微微网或者散射网的形式出现。共享单个公共信道的一组 蓝牙节点组成一个微微网。微微网中一个节点做主节点，其他做从节点。从节 点的个数有限，目前不能超过7 个。主节点轮询从节点，与它们通讯，从节点 保持同主节点之间的同步，但从节点之间不能通讯，需要主节点转发数据才能 实现它们之间的互通，如图3 所示，微微网1 ，2 ，3 都是含有4 个从设备的微 微网。 中国科学技术大学工学硕士学位论文 。1 ma s t e r 一s i a v e s b r i d g e s ，s 图3 由三个微微网组成的散射网 多个微微网可以在公共区域内共存相连而形成散射网，每个微微网使用不 同跳频序列。如图3 所示，三个微微网两两之间通过一些共享的节点连接在一 起，这种共享的节点称为桥节点( b r i d g e ) 。如果桥节点在两个微微网中都是从 设备，则称为s s 桥节点；如果桥节点在一个微微网中是主设备，而在另一个 微微网中是从设备，则称为m s 桥节点。 2 3 2 蓝牙自组个人局域网特性 组成自组个人局域网的节点是可移动的，并且可以随时加入或者离开网 络，因此它与传统的有线或者无线网络有很大的区别。这些区别也正好体现了 自组网络的特点。这些特点包括： 1 分布式操作 在蜂窝式无线网络中，有基站、移动交换中心或本地位置注册机构等中心 实体。这些中心实体有协调其他设备的功能。而在自组网络中，没有这样具有 协调功能的中心实体存在。 2 动态网络结构 中国科学技术大学工学硕士学位论文 节点都是移动的，容易引起网络拓扑结构变化，但同时又必须保持应用和 服务的连续性。 3 链路不稳定 在无线环境下，由于多径、衰落、噪声和干扰等因素的影响，无线链路的 容量比有线链路低得多，误码率也较高。 4 低能耗 网络中的节点大部分是电池驱动的，只有有限的能量供应，影响到微处理 器处理能力、内存大小、信号处理和射频收发器功耗等。因此节约能量是重要 的系统优化设计标准。 5 有限物理安全 移动自组网络比有线网络在物理安全上显得更为脆弱，因此更容易受到偷 听、欺骗和拒绝服务等不同形式的攻击。 相对于一般的自组网络，蓝牙自组网络还具有以下特点： 1 节点间通讯距离短 蓝牙主要用于短距离通讯，节点间通讯距离一般为几十米，而一般自组网 络节点间通讯距离可以达到几百米。 2 节点移动性小 蓝牙节点一般为个人设备，因此节点的移动速度和频度都比较小。 3 网络带宽窄 蓝牙1 1 节点的带宽只有1 m b p s ，蓝牙2 0 也只能达到3 m b p s 。而一般的 自组网络可以达到几十兆位每秒的速度，因此优化利用蓝牙网络带宽资源就显 得尤为重要。 4 物理信道不同 在基于广播的无线局域网中，网络拓扑结构是由节点间的物理距离决定 的。但在蓝牙中，邻近节点需要发现对方并建立点对点的物理链路，可以形成 具有不同拓扑结构的自组网络。 蓝牙白组网络的上述特点给蓝牙自组网拓扑形成的研究带来了挑战。 中国科学技术大学工学硕士学位论文 2 3 3 蓝牙自组个人局域网性能特点 z u r b e s 等 2 1 1 分析了系统内同时存在多个微微网时公共信道干扰对于蓝牙 系统性能影响。j o h a n s s o n 等【2 2 分析了信号衰落与多径干扰对于蓝牙链路性能 影响，给出这种信道条件下微微网分布密度与链路性能的关系，同时分析蓝牙 纠错编码的方案对于系统性能的影响，指出蓝牙技术在短距离内对数据和语音 有良好的支持。j o h a n s s o n 等2 3 研究了t c p i p 在蓝牙无线网络上的性能。 z i l r b e s 等【2 4 对蓝牙射频和基带模块做了仿真实验，说明多时隙数据包在各种 干扰条件下具有更高的吞吐率。s h o r e y 等 2 5 1 指出蓝牙在克服容量限制、搜索 时间和节能等方面需做的工作。m i k l o s 等2 6 通过仿真具有不同特性的散射 网，得到一些影响散射网性能的重要因素，包括链路数目和微微网间转发引起 的负载等。 以上研究表明蓝牙技术是适合近距离的无线通信标准。蓝牙跳频技术可以 使多个微微网在近距离内同时存在。在构造个人局域网络时，8 0 2 1 1 也是一个 候选的技术。j o h a n s s o n 等 2 7 】对蓝牙和8 0 2 1 1 作了对比，说明它们之间互有优 劣： 8 0 2 1 1 的链路速度可达到1 0 m b p s ，而蓝牙1 1 只有l m b p s 。但是当节 点数增加时，蓝牙能增加网络整体容量。这是因为8 0 2 1 1 使用 1 7 m h z 的广播信道和c s m a c a ，当节点较少时能较好工作。但当流 量增加时，节点问信道竞争加剧，使得数据冲突增加，实际带宽锐 减。而蓝牙中，每个微微网使用1 m h z 不到的信道，并且用f h s s 机 制避免冲突，虽然这会导致较低速率，但当网络流量增大时，却能提 供稳定可预见的容量。 当网络规模增加，蓝牙的能耗效率能保持不变。相反的是，因节点增 加导致的包冲突增大，使8 0 2 1 1 的能耗效率很快降低，会浪费能量。 如果系统之间整体平均吞吐率可以比较的话，8 0 2 1 1 中的t c p 连接之 间的容量是不公平共享的。这是因为在较大流量情况下的m a c 层和 t c p 流控机制的交互作用所至。而在相同情况下，蓝牙中的t c p 连接 的容量分布得相当公平。 蓝牙比8 0 2 1 1 能更好的支持具有q o s 要求的连接，如语音链路。 总之，蓝牙p a n 的网络规模可以很大，能很好的避免节点间的干扰，有 更好的能耗效率，节点上的应用在延迟和吞吐率上能达到稳定持久的性能，可 以实现如语音和低速视频等交互服务。 中国科学技术大学工学硕士学位论文 2 4 蓝牙个人局域网协议子集 为了支持蓝牙个人局域网络，蓝牙s i g 成立了一个工作组 2 ，即个人局 域网络工作组。工作组主要目标是定义基于i p 的动态自组个人无线局域网 络，解决以太网数据包的封装、单个微微网中基于i p 的个人局域网络、主设 备转发和局域网接入点等问题。但目前只解决了单个微微网中节点间的通讯问 题。 蓝牙网络是基于i p 的动态个人网络，它与操作系统、语言和设备无关， 提供对网络协议，如i p v 4 ，i p v 6 和其他已有网络协议的支持，提供对l a n ， g s m 等网络接入点的支持，适合内存小、处理能力弱、用户接口简单的小型 设备使用。 2 4 1 协议框架 蓝牙p a n 应用框架【2 8 】定义了蓝牙设备加入个人局域网的方法，规定了单 个微微网中的网络发现、网络形成、地址分配、地址解析、域名解析、桥接路 由和网络安全等问题。 蓝牙个人局域网应用框架中包括两种网络结构，网络接入点结构( n a p ) 和 组网络结构( o n ) 。网络接入点结构中用一个或多个蓝牙设备作为蓝牙网络和 l a n ，g s m 等网络之间的网桥，网络接入点为每个相连的蓝牙设备提供了网 络服务，如l a n 上共享的资源。组网络结构是由一些移动设备在不需要其他 网络硬件或网络设施下组成的无线自组网络。本文仅讨论组网络结构的蓝牙 p a n 。 2 4 2 蓝牙网络封装协议( b n e p ) b n e p 将来自各种网络协议的包封装后直接通过蓝牙l 2 c a p 协议传输。 b n e p 使用面向连接的l 2 c a p ，b n e p 移去以太网包头，用b n e p 包头代替， 以太网的负荷保持不变。如下图所示： 1 4 中国科学技术大学工学硕士学位论文 t c p p 卜一一，一，一一掣。 二一一一t c p i i p 。j 鋈誉 | l | l 辫鋈圈 l 2 篱鬯纂紫卜。-熏nbel 幻 “。“；_ 卜b n e p ： l 。融c 姆，： ”! l 2 c a p 。 一篙2 e a p = ：- i ：i , i lj 隧：薯零髓臻醚或嚣；。j l 1 稿矗艇阳雕i ：i = ；j ；：、弱彬p m 。j ：- 图4 蓝牙协议栈中b n e p 所处位置示意图 2 5 蓝牙个人局域网应用场景 从传统移动网络的角度来看，蓝牙p a n 开辟了一种将移动网络服务扩展到 个人移动设备中的新方式。如图5 所示，由笔记本、移动电话、耳机和p d a 组 成的蓝牙p a n 通过移动电话和l a n 接入点与因特网和g p r s 网络相连，大大扩 展了移动网络的应用范围。 图5 蓝牙自组p a n 应用之一：其他网络的扩展 蓝牙p a n 也可以组成小规模自组网络，进行临时会议、网络游戏等应用。 如图6 所示，三个笔记本通过蓝牙连接在一起，可以互传文件，并可通过手机 一起接入到因特网。 中国科学技术大学工学硕士学位论文 图6 蓝牙自组p a n 应用之二：移动会议 蓝牙p a n 还可以组成大规模的面向某种应用或服务的自组网络，如传感 器网络 2 9 。如图7 所示，许多蓝牙节点自动组成一个具有复杂拓扑结构的网 络，它是一个全连通图，运行某个路由算法使数据能在整个网络中传递，这些 数据可来自应用层。 图7 蓝牙自组p a n 应用之三：传感网络及其他大规模网络 2 6 本章小结 蓝牙技术在人口密集、商业经济活动集中的地方将会有广阔的应用前景， 因为这是一项面对个人的近距离无线通信技术，在人和人之间、人和机器之间 相互交流时，将会发挥更大的作用。蓝牙的跳频技术使构造大规模的网络成为 可能，可以为许多新兴应用和服务提供一个很好的通讯平台。 霸 番鼠、 翁黼 另一方面，蓝牙p a n 的动态结构、无线连接和无中心控制等特点使得构造 和维护这种网络要比传统有线网络和移动网络困难得多；蓝牙节点本身多为个 人数字设备，节点运行的协议和应用程序必须考虑节点处理能力、内存和能耗 等方面的限制。因此如何构造散射网络，使网络里的节点能自由相互通讯，实 现蓝牙p a n 的各种潜在应用，是目前亟待解决的重要课题。 中国科学技术大学工学硕士学位论文 第3 章蓝牙自组个人局域网形成算法研究 蓝牙p a n 是由桥节点将多个微微网连接在一起的自组网络。潜在的广阔应 用前景使它逐渐成为研究热点之一，蓝牙散射网所具有的特殊限制和特性给有 效创建蓝牙网络拓扑结构带来了挑战。目前已经有不少文献提出了蓝牙p a n 的 形成算法。 本章首先介绍蓝牙物理链路建立过程，也即设备发现过程，这是网络拓扑 结构形成的基础。然后介绍散射网拓扑形成算法方面的相关研究，并重点分析 了b t c p ，l a w ，b l u e t r e e 等散射网形成算法。 3 1 物理链路建立过程 蓝牙在物理层上建立链路连接的过程是设各互相发现的过程。蓝牙节点要 通过查询和寻呼两个过程建立连接。 查询过程中，处于查询状态的节点发出查询广播包，试图发现通讯距离内 的其他节点。处于查询扫描状态的节点则监听查询包，一旦接收到查询包就发 送包含自己基带地址和时钟的查询响应包。 寻呼过程中，处于寻呼状态的节点发送含有对方地址和时钟的寻呼包，试 图建立物理链路。而处于寻呼扫描状态的节点则监听寻呼请求包，若接收到寻 呼请求包，并通过了可选的认证过程，这样就完成同对方建立物理链路的过 程。链路建立后，呼叫方成为主节点，响应方成为从节点，但通过角色协商可 以调整角色。 3 2 形成算法的相关研究 这里假定n 为散射网中节点总数，k 为微微网中从节点最大个数。 3 2 1b t c