（信号与信息处理专业论文）蓝牙ad+hoc网络路由协议及相关问题研究.pdf

摘要 近年来，a dh o e 网络已经成为无线移动通信领域内的一个研究热点。目前，实现a d h o c 网络的相关技术有i e e e8 0 2 1 l 技术、c d m a 技术、蓝牙( b l u e t o o t h ) 技术、h i p e r l a n 2 标准以及h o m e r f ( 家庭射频) 规范。其中蓝牙技术以其自组织特性、无线传输特性、动 态拓扑特性、低功耗特性、以及使用世界通用频谱( i s m ) 等等成为实现a dh o e 刚络的一 种较好的选择。但利用蓝牙技术来构建性能优越的a dh o e 网络还需要进行很多方面的改 进，其中很重要的一点就是路出协议的改进。 现有的a dh o c 网络路由协议都假定网络的m a c 层采用8 0 2 1 l 协议。但是蓝牙的m a c 层与8 0 2 1 l 不同。蓝牙采用时分双工以及轮询接入的方式，并且蓝牙a dh o c 网络是基于 主从模式的，两个蓝牙节点只有形成主从关系才能相互传送信息，而主从机制不能直接使 用传统a dh o c 网络的路由协议。另外，蓝牙技术的其他一些特点，如分组的大小也会导 致一些传统的路由协议不能直接应用于蓝牙a dh o c 网络。因此，在为蓝牙a dh o c 网络设 计路由算法时，应该考虑蓝牙技术的特点。 另外，蓝牙作为一种近距离无线通信技术规范，因其低成本、低功耗、小体积而广泛 应用于小型移动产品和信息家电产品中，而此类产品大都属于嵌入式产品。因此，掌握蓝 牙技术在嵌入式领域中的开发方法具有一定的意义。 本文首先分类介绍了几种典型的蓝牙a dh o c 网络路由协议，然后研究和改进了r v m 协议，指出其中存在的问题并给出解决方案，为该协议引入路由缓存技术，并补充了路由 维护部分。最后本文介绍了一种嵌入式蓝牙开发平台，以说明蓝牙技术在嵌入式领域中的 丌发方法。 关键词：a dh o c 网络，蓝牙，路由协议，r v m ，嵌入式开发平台 a b s t r a c t i nr e c e n ty e a r s ，a dh o en e t w o r kh a sb e c o m ear e s e a r c hf o c u si nt h ef i e l do f w i r e l e s sm o b i l e t e l e c o m m u n i c a t i o n f o rn o w , t h er e l a t i v et e c h n o l o g i e st h a ti m p l e m e n ta dh o cn e t w o r ki n c l u d e i e e e8 0 2 11 ，c d m a ，b l u e t o o t h ，h i p e r l a n 2a n dh o m e r f a m o n gt h e s e t e c h n o l o g i e s ， b l u e t o o t hh a sb e e nc h o s e na sag o o do n et o i m p l e m e n ta dh o cn e t w o r kb e c a u s eo fi t s s e l f - o r g a n i z a t i o n ，w i r e l e s s t r a n s m i s s i o n ，d y n a m i c t o p o l o g y , l o wp o w e r - c o s ta n dt h eu s a g eo f i s mf r e q u e n c y b u tt h e r ea r es t i l lm a n ya s p e c t st ob ei m p r o v e di fw ew a n tt ou s eb l u e t o o t ht o c o n s t r u c tah i g hp e r f o r m a n c ea dh o cn e t w o r k ，o n eo fw h i c hi st h ei m p r o v e m e n to fr o u t i n g p r o t o c 0 1 m o s to ft h ee x i s t i n ga dh o cn e t w o r km u t i n gp r o t o c o l sa s s u l n e8 0 2 11a st h em a c t e c h n o l o g y b u tt h eb l u e t o o t hm a cl a y e ri s d i f f e r e n tf r o m8 0 2 ，11 i tt a k e st h e w a yo f t i m e - d i v i s i o nd u p l e xa n dp o l l i n ga c c e s s m o r e o v e r ，t h eb l u e t o o t ha dh o cn e t w o r ki sb a s e do n m a s t e r - s l a v em o d e l t w ob l u e t o o t hn o d e sc a r l tc o m m u n i c a t i o nw i me a c ho t h e ru n l e s st h e m a s t e r - s l a v er e l a t i o ni sb u i l tb e t w e e nt h e m ，t h a tm e a n sw ec a n tu s er o u t i n gp r o t o c o l so ft h e t r a d i t i o n a la dh o cn e t w o r kd i r e c t l y a d d i t i o n a l l y , s o m eo t h e rc h a r a c t e r so fb l u e t o o t h ，s u c ha s t h ep a c k e ts i z el i m i t a t i o n ，a l s ol e a dt oi n v a l i d i t yo fs o m et r a d i t i o n a lr o u t i n gp r o t o c o l s t h e r e f o r e ， w h i l ed e s i g n i n gr o u t i n gp r o t o c o l sf o rb l u e t o o t ha dh o cn e t w o r k ，t h ec h a r a c t e r so fb l u e t o o t h m u s tb et a k e ni n t oa c c o u n t a l s o ，b l u e t o o t hh a sb e e na p p l i e di nt h ef i e l do fs m a l lm o b i l ep r o d u c ta n di n f o r m a t i o n a p p l i a n c eb e c a u s eo fi t sl o wc o s t ，l o wp o w e r c o s ta n ds m a l ls i z e ，a n dm o s to ft h e s ep r o d u c t sa r e e m b e d d e d t h u s ，i tw i l lm a k es e r et og e tt ok n o wt h ee m b e d d e dd e v e l o p m e n to fb l u e t o o t h t e c h n o l o g y ： t h i sp a p o ri n t r o d u c e ss e v e r a lc l a s s i cb l u e t o o t ha dh o cn e t w o r kr o u t i n gp r o t o c o l sf i r s t l y , t h e na n a l y z e sa n di m p r o v e st h er v wp r o t o c o l ，p o i n t i n go u ti t sp r o b l e m sa n dp r o v i d i n ga s o l u t i o n ，i n t r o d u c i n gr o u t ec a c h i n ga n ds u p p l e m e n t i n gr o u t em a i n t e n a n c e a tl a s t ，t h ep a p e r i n t r o d u c e sae m b e d d e db l u e t o o t hd e v e l o p m e n tp l a t f o r mi no r d e rt o e x p l a i nt h ed e v e l o p m e n t m e t h o do fb l u e t o o t ht e c h n o l o g yi ne m b e d d e df i e l d k e y w o r d s ：a dh o en e t w o r k ，b l u e t o o t h ，r o u t i n gp r o t o c o l ，r v m ，e m b e d d e dd e v e l o p m e n t p l a t f o r m i i 南京邮电大学 硕士学位论文摘要 学科、专业：工学信号与信息处理 研究方向：现代通信中的智能信号处理技术 作者：2 0 0 3 级研究生许文昭指导教师篮垂 题目：蓝牙a dh o c 网络路由协议及相关问题研究 英文题目：r e s e a r c ho nr o u t i n gp r o t o c o lo fb l u e t o o t ha dh o c n e t w o r ka n dr e l a t e dp r o b l e m 主题词：a dh o c 网络蓝牙路由协议r v m 嵌入式开发平台 k e y w o r d s ：a dh o cn e t w o r k b l u e t o o t h r o u t i n gp r o t o c o l r v m e m b e d d e dd e v e l o p m e n tp l a t f o r m 南京邮电大学学位论文独创性声明 r8 5 0 9 0 s 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文巾作了 明确的说明并表示了谢意。 研究生签名：垂量盟一i i 期：趣b ：生q 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：礁塞塑 导师签名 日期：堕! ! ：毋 南京邮电大学颈f 研究生学位论文第一章绪论 1 1 研究背景简介 第一章绪论 a dh o c 网络是一种特殊的无线移动通信网络。a dh o c 网络中所有节点的地位平等， 无需设置任何中心控制节点，具有很强的抗毁性。网络中的节点不仅具有普通移动终端所 需的功能，而且具有报文转发能力。当通信的源节点和目的节点不在直接通信范围之内时， 它们可以通过中间节点转发报文进行通信。有时节点间的通信可能要经过多个中间节点的 转发，即报文要经过多跳( h o p ) 才能到达目的地，这是a dh o c 网络与其他移动通信网络 的最根本区别。a dh o c 网络的节点通过分层的网络协议和分布式算法相互协调，实现网络 的自动组织和运行。因此它又被称为多跳无线网( m u l t i h o p w i r e l e s s n e t w o r k ) 、自组织网 络( s e l f - o r g a n i z e dn e t w o r k ) 或无固定设施的网络( i n f r a s t r u c t u r e l e s sn e t w o r k ) 。 a d h o c 网络可以在没有基础设施支持的情况下提供灵活方便的通信，拓宽了移动通信 的领域。特别是在军事应用领域，或在发生了地震、水灾、火灾等重大灾难后固定的通信 网络设施可能全部损毁或无法正常工作的地区，或当处于偏远或野外地区( 包括野外科考、 边远矿山作业、边远地区执行任务分队的通信等) 无法依赖凰定或预设的网络设施进行通 信时，就需要a dh o e 网络这种不依赖任何固定网络设施又能快速布设的自组织网络技术。 近年来，a d h o e 网络已经成为无线移动通信领域内的一个研究热点，但是在其网络实 现和应用过程中仍有许多亟待解决的问题。目前，实现a dh o c 网络的相关技术裔i e e e 8 0 2 1 l 技术、c d m a 技术、蓝牙( b l u e t o o t h ) 技术、h i p e r l a n 2 ( h i p e r p e r f o r m a n c e r a d i o l o c a l a r e a n e t w o r k t y p e 2 ) 标准以及h o m e r f ( 家庭射频) 规范。其中蓝牙技术以其自组 织特性、无线传输特性、动态拓扑特性、低功耗特性、以及使用世界通用频谱( i s m ) 等 等成为实现a dh o c 网络的一种较好的选择，但利用蓝牙技术来构建性能优越的a dh o c 网 络还需要进行很多方面的改进。 蓝牙技术最初出现于1 9 9 8 年，其初衷是为了替代麻烦的电缆连接，实现短距离无线语 音和数据通信，给便携通信设备提供一种低功耗、低成本、小体积的嵌入式无线通信方案。 蓝牙程序写在一个9 r a m 9 m m 的微芯片上，将其嵌入到手机、p d a 和数码相机等移动终 端中，就可以完成设备之间的无电缆连接，实现无线局域网( w l a n ) 和信息家电等构想。 蓝牙采用2 4 g h z l s m 频段，使用小范围射频链路，链路建立在跳频频谱上，可在同一 要塞塑皇查兰堡主婴! ! 兰兰堡堡苎兰二皇堕堡 通信带宽内无干扰的转输多个信道信息，实现终端之间的信息交换。共存于同一信道的若 干设备单元构成一个微微网( p i c o n e t ) 。在微微网中，若菜台设备的时钟和跳频序列用于其 它设备，则称为主设备，否则为从设备，一个微微网中只有一个主设备和多个从设备( 不 多于7 个) 。在同一微微网中，所以用户均用一个跳频序列同步。若干相互独立的微微网 连接在一起，就构成蓝牙分布式网络( s c a t t e r n e t ，也称散射网) 。各微微网由不同的跳频序 列区分，在一个互连的分布式网络中，一个结点设备可同时存在于多个微微网中，但不能 在两个微微网中处于活动状态( a c t i v e ) 。蓝牙散射网是自组嗣( a d h o c ) 的一种特例，可 以称之为蓝牙a dh o c 网络或者蓝牙自组织网。 然而，虽然蓝牙规范允许将多个微微网连接起来构成分布式网络，但是并没有给出具 体的协议。而且，由于蓝牙的设计初衷只是为了替代电缆连接，所以利用蓝牙技术来构建 性能优越的a dh o c 网络还需要进行很多方面的改进。其中很重要的一点就是路由协议的 改进。因为现有的a d h o e 网络路由协议都假定网络的m a c 层采用8 0 2 1 l 协议。由于蓝牙 的姒c 层与8 0 2 1 l 不同，所以传统的a dh o c 路由算法并不能直接应用于蓝牙散射网。事 实上，在为蓝牙散射网设计路由算法时，应该考虑蓝牙技术的特点。 蓝牙a dh o 网络的路由协议是蓝牙技术领域的研究热点之一。目前，已经有相当数量 的文献提出了适用于蓝牙a dh o c 网络的路由协议。有些算法是基于现有的a dh o c 路由算 法并结合蓝牙技术的特性提出的，如基于z r p 的算法【2 】以及s c r p ( s c a t t e m e t c o n s t r u c ta n d r o u t i n gp r o t o c 0 1 ) 算法 3 b 有些是结合散射网的构成协议来构造特定的路由协议，如文献 【4 构造了一个自路由散射网，该散射网内的路由算法非常简单；也有利用蓝牙技术的特点 提出的、蓝牙a dh o c 网络特有的全新的路由协议，如r v m 路由矢量算法 7 】，但是还不 完善。 另外，由于蓝牙芯片体积小( 9 m m 9 m m ) ，可以嵌入移动终端中实现设备之渊的无线 连接，并且蓝牙芯片的价格在逐步下降，使得将蓝牙a dh o c 网络应用于实际中成为可能。 因此对用户和丌发人员而言，能够快速掌握蓝牙技术在嵌入式领域中的丌发方法，让蓝牙 技术尽快应用于产品中，具有一定的意义。 1 2 论文主要内容 本文主要研究了蓝牙a dh o e 网络的路由算法，并在此基础上对r v m 算法进行了研究 和改进，通过仿真验证了性能的改善。本文还介绍了一种嵌入式蓝牙开发平台，以说明蓝 牙技术在嵌入式领域中的开发方法。本文的主要内容如下： 南京邮电大学硕士研究生学位论文第一章绪论 第二章：简单介绍了a dh o c 网络路由协议的研究现状，并重点介绍了两种典型的按需 路由协议，即d s r 和a o d v 。 第三章：介绍了蓝牙a dh o c 网络的特点及其对路由协议的要求，并基于协议的特点 分类介绍了几种比较典型的蓝牙a dh o c 网络路由协议。 第四章：分析和研究了r v m 涛议存在的问题并给出解决方案，为该协议引入路由缓 存技术，并补充了路由维护部分。 法。 第五章：介绍了一种嵌入式蓝牙开发平台，以说明蓝牙技术在嵌入式领域中的开发方 第六章：总结全文，对进一步的研究工作进行了展望。 南京部电大学硕士耐f 究生学位论文 第二蕈a d h o e 网络路由协嫂简介 第二章a dh o e 网络路由协议简介 在a dh o c 网络中，移动节点通过多跳无续链路实现相互问的通信。整个网络没有嘲定 的基础设旄，网内每一个节点都可作为路由器，向其它节点转发数据。因此，丌发一种能 有效地找到节点问路由的动念路由协议就成为a dh o e 网络设计的关键。 2 1 路由协议的分类 目前m a n e t w g 己绎提出了许多协议草案，比如d s r 、a o d v 、t o r a 、z r p 等。 此外，研究人员还发表了许多关于自组网路由协议的学术论文，比如d s d v 、w r p 、f s r 、 l a n m a r 、l a r 、z h l s 等。这些自组网路由协议根据不同的角度可以进行不同的分兴， 如图2 1 所示。 图2 1 路由协议的分类 从所处理的网络逻辑视图的角度划分，可分为平面路由协议和分级路出协议。 1 平面路由协议( f l a t ) 。在平面路由协议中，所有节点在形成和维护路由信息的责任 e 是等同的。路由协议的逻辑视图是平面结构，节点的地位是平等的。其优点是不存在特 殊节点，路由协议的鲁棒性较好，通信流量平均地分散在网络中。路出协议没有节点移动 性管理任务。缺点是缺乏扩展性，限制了网络的规模。 2 + 分级路由协议( c l u s t e r b a s e d ) 。分级路出协议中，网络由多个簇组成，节点分为两 种类型：普通节点和壤头节点。处于同一簇的簇头节点和普通节点共同维护所在簇内部的 路由信息，簇头节点负责所管辖簇的拓扑信息的压缩和摘要处理，并与其他簇头节点交换 路由信息，簇头节点负责所管辖簇的拓 卜信息的压缩和摘要处理，并与其他簇头节点交换 4 南京邮电大学硕士研究生学位论文第二章a dh o e 网络路由协没简介 第二章a dh o e 网络路由协议简介 在a dh o e 网络中，移动节点通过多跳无线链路实现相互问的通信。整个网络没有围定 的基础设施，网内每一个节点都可作为路由器，向其它节点转发数据。因此，丌发种能 有效地找到节点问路由的动态路由协议就成为a dh o e 网络设计的关键。 2 1 路由协议的分类 目前m a n e t w g 己经提出了许多协议草案，比如d s r 、a o d v 、t o r a 、z r p 等。 此外，研究人员还发表了许多关于自组网路由协议的学术论文，比如d s d v 、w r p 、f s r 、 l a n m a r 、l a r 、z h l s 等。这些自组网路由协议根据不同的角度可以进行不同的分类， 如图2 1 所示。 图2 1 路由协议的分类 从所处理的网络逻辑视图的角度划分，可分为平面路由协议和分级路幽协议。 1 平面路由协议( f l a t ) 。在平面路由协议中，所有节点在形成和维护路由信息的责任 上是等同的。路由协议的逻辑视图是平面结构，节点的地位是平等的。其优点是不存在特 殊节点，路由协议的鲁棒性较好，通信流量平均地分散在网络中。路由协议没有节点移动 性管理任务。缺点是缺乏扩展性，限制了网络的规模。 2 分级路由协议( c l u s t e r b a s e d ) 。分级路出协议中，网络由多个簇组成，节点分为两 种类型：普通节点和簇头节点。处于同一簇的簇头节点和普通节点共同维护所在簇内部的 路由信息，簇头节点负责所管辖簇的拓扑信息的压缩和摘要处理，并与其他簇头节点交换 4 堕室塑皇查竺堡主竺塞生兰垡堡兰堡三里垒! 望竺塑塑些里塑些塑坌 处理过后的拓扑信息。层次结构就是一种典型的簇方式。采用簇路由主要有两个目的。一 是通过减少参与路由计算的节点数目，减小路由表大小，降低交换路由信息所需的通信开 销和维护路由表所需的内存开销，这与有线网络中层次思想的目标是致的：二：是基于某 种簇形成策略，选举产生一个较为稳定的子网路，减少拓扑结构变化对路由协议带来的影 响。簇路由的优点是适合大规模的自组网环境，可扩展性较好；缺点是簇头节点的可靠性 和稳定性对全网性能影响较大，并且为支持节点在不同簇之间漫游所进行的移动管理将产 生一定的协议开销。 已提出的自组网路由协议大多数是基于平面路由思想，主要原因是自组网目前主要以 种末端网络形式存在，应用规模都较小，使用簇思想的作用不明显。这在一定程度上抑 制了簇思想在自组网的研究。 按路由发现的策略划分，可分为主动路由协议、被动路由协议和混合路由协议。 1 主动路由协议( p r o a c t i v e ) ，又称为表驱动路由协议或先验式路由协议。主动路由的 路由发现策略与传统路由协议类似，各节点通过周期性地广播路由信息分组，交换路由信 息，主动发现路由。同时，节点必须维护去往全网所有节点的路由。它的优点是当节点需 要发送数据分组时，只要去往目的节点的路由存在，所需的延时很小：缺点是主动路由需 要花费较大开销，尽可能使得路由更新能够及时反映当前拓扑结构的变化。然而，动态变 化的拓扑结构可能使得这些路由更新变成过时信息，路由协议始终处于不收敛状态。 在自组网路由协议的研究初期主要思路是修改有线网络的路由协议以适应在自组网 环境中的运行。这些路由协议大多属于主动路由。目静已经提出的主动协议主要有w r p 、 d s d v 、c g c r 、s t a r a 。， 2 被动路由协议( r e a c t i v e ) ，又称为按需路由协议。被动路由协议的思想类似于局域 网网桥设计中的源路由。与主动路由相反，按需路由认为动态变化的自组网环境中，没有 必要维护去往其他所有节点的路由。它仅在源节点有分组要发但没有去往目的节点的路由 时，才“按需”进行路由发现。因此，拓扑结构和路由表内容是按需建立的，它可能仅仅 是照个拓扑结构信息的一部分。 它的优点是不需要周期性的路由信息广播，节省了一定的网络资源：缺点是发送数据 分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现引起的延时。 按需路由协议通常由路出发现和路由维护两个过程组成。当源节点发现没有去往目的 节点的路由时，触发路由发现过程。这个过程类似于有线网络中建立电路连接的协商过程。 当拓扑结构发生变化时，通过路由维护过程删除失效路由，重新发起路由请求过程。路由 维护通常依靠底层提供的链路失效检测帆谁i 进行触发。 e 南京豳| f 电 学颂上谛f 究生学位论i 空=第二犟a dh o e 网络路由协议简介 一3 混合路由协议( h y b r i d ) 。混合路由协议是一类混合使用主动路由和被动路由策略的 协议，即在一定的网络区域内采用主动路由的设计，区域间则采用被动路由的设计。如z r p 协议。 按是否有g p s 辅助进行划分，可分为基于网络拓扑的路由协议和基于位置的路由协议。 基于拓扑的路由协议是利用链路信息进行路由的建立和分组转发。基于位嚣的路幽协 议是利用节点的物理位置( 通过g p s 或其他定位服务获取) 进行分组转发。 2 2 典型的按需路由协议简介 由于蓝牙技术自身的特点，如带宽比较窄、分组比较小，蓝牙a d h o c 网络不适合使用 主动路由协议。事实上，迄今为止所提出的针对蓝牙a dh o c 网络的路由协议大多是按需 路由协议或者是混合路由协议。因此，在这- - + 节我们重点介绍一下按需路由协议。目前 已经提出的按需路由协议( o nd e m a n d ) 主要有d s r ( 动态源路由d y n a m i cs o u r c er o u t i n g ) 、 t o r a ( 临时摊序路由算法t e m p o r a r y o r d e r e dr o u t i n ga l g o r i t h m ) 、a o d v ( a d h o e 按需距离 矢量协议a dh o co nd e m a n dd i s t a n c ev e c t o r ) 、a b r ( 基于关联的路由a s s o c i a t i v i t y b a s e d r o u t i n g ) 等。 若干仿真结果表明 1 2 ，a o d v 与d s r 的性能在大多数场景中不相上下丽强于其它己有 的路由协议，是两种性能相当不错的a dh o c 按需路由协议。因此下面主要介绍这两种典 型的按需路由协议：d s r 和a o d v 。 2 2 1d s r 协议 d s r 协议是最早采用按需路由思想的路由协议，是由美国卡耐基梅隆大学m o n a r c h 工 作组提出的一种使用源路由思想的a dh o c 网络按需路由协议。使用d s r 的节点只维护正 在通信的路由信息，也不使用周期性的路由信息广播完成路由信息的更新。当个节点需 要一条到某个目的节点的路由时，节点动态的从路由缓存中选择一条或者通过路由发现过 程发现一条新的路由：当节点发现与某个邻居节点问的链路失效后，通过路由维护过程完 成路由的切换。 源路由是一种由数据分组的发送节点决定整个传输过程中的完整路由的路由机制。源 节点在发送数据分组时将完整的路由路径显式地列在分组的头部，路由路径中包含了该分 组从源节点到目的节点的路径中的每一跳的信息如i p 地址、网络接口等等。使用源路由的 一个突出优点在于任何中间节点都无需维护对应于转发分组的路由，中闽节点在收到分组 6 塑堕些塑叁竺登兰! ! 塑皇兰丝堡塞 笙= ：里垒璺坚! ! 璺堡墅虫丝堡塑坌 后只需要根据源路由的地址列表中选择下一跳节点，然后将该分组转发到下一跳即可。不 同于传统的路由算法，d s r 不使用周期性路由信息广播来完成路由信息的更新，这样就在 很大程度上降低了路由协议的开销，尤其是当节点的运动频率和运动速度较低的时候。 d s r 协议主要包含两个过程，即路由发现和路由维护。当一个节点欲发送分组到某个 目的节点时，节点首先查看其路由缓存中是否存在到达该目的节点的路由。如果路由缓存 中存在到达目的结点的路由若且该路由没有超时，则节点使用该路由发送分组。否则，节 点就需要通过广播路由请求分组( r r e q ) 来发起一次新的路由发现过程，以发现到达浚 日的节点的路由。路由请求分组中包含了源节点地址、目的节点地址和一个用来唯一标t 蛙 该路由请求的i d 号。每个节点维护一个路由请求表，其中记录了在过去一段时间内收到 的路由请求信息，这些记录以源地址和路由请求i d 号作为索引。当任何中间节点收到路 由请求后，( 1 ) 查看路由请求表中是否已经包含了关于浚路由请求的记录，如果是，则简 单的将该路由请求分组丢弃；( 2 ) 查看路由请求的地址列表中是否包括本节点，如果是， 丢弃该路由请求分组：( 3 ) 查看本节点是否就是该路由请求分组指定的目的节点，如果是， 则发送路由应答分组( r r e p ) ，( 4 ) 否则，将本机的i p 地址添加在路由请求中已有的地址 列表中，然后将该路由请求再次发送出去。当路由请求到达目的节点并且目的节点的路吐j 请求表中没有相应的汜录时，目的节点则根据路由请求中的地址列表加上本机i p 构造个 路由应答并且将该路由应答通过这条路由发送到发起路由请求的源节点。源节点在收到路 由应答后，会根据路由应答中包含的路径信息形成一条新的路由，用来发送已经缓冲的和 其后到达的发往该目的结点的分组。至此，就完成了一次路由发现过程。 在发送和转发分组的过程中，路由维护过程用来检测路出失效。节点在发送或者转发 分组时，都要保证分组被正确的传输到路由中表明的下一跳节点，如果分组没有被正确的 发送到下一跳节点，则认为该节点与下一跳节点之问的链路出现了失效，进而也就导致r 整条路由的失效。因此，需要另外一条新的路由来完成对于其后分组的传递。此时节点需 要通过路由维护过程来完成路由切换。发现路由失效的节点需要向业务的源节点发送个 路由错误分组，源节点在收到路出错误分组后，首先查看路由缓存中是否存在另外一条到 达该目的节点的路由，如果是，则使用新的路由进行分组的发送；否则，发起一次新的路 由发现过程以发现到达该目的节点的新的路由。 2 2 2a o d v 协议 a o d v 协议是由c h a r l e se p e r k i n s 等人提出的种典型的按需路出协议。a o d v 借鉴 南京邮电大学坝上研艽生学位论文第二鼋a dh o e 螂络路由协议简介 了d s d v 的路由维护机制同时参考了d s r 的路出发现过程，是丽者相结合的产物。每一一个 使用a o i ) v 路由协议的节点都维护一个路由表，其中包含了所有正在进行通信的路由。路 由表中的每条路由记录包含如下的信扈、：目的节点地址、目的节点序列号、路由下一跳和 到达目的节点的路由跳数。另外，与每一条路由记录相关联的还有一个用来表明路由有效 期的参数即路由生存期。如果在路由生存期结束时浚路由仍然没有被更新过而且也没有被 使用过，则将该路由从路出表中删除。与d s d v 类似，每个节点维护自己的节点序列譬。 与d s r 中的路由请求i d 类似，a o d v 使用一个叫做广播标识b i d 的计数器。b i d 和源节点 地址的组合用来唯一标识一个路由请求( r r e q ) ，a o d v 使用b i d 列表来记录在过去一段时i h j 内收到的路由请求的信息，b i d 列表以源节点地址和b i d 作为索引。 a o d v 的路由发现过程是完全按需的，并使用与d s r 类似的路由请求路由应答过程。 源节点在欲发送信息到某个目的节点而发现路由表中不存在有效的到达该目的节点的路 由时发起一次新的路由发现过程。源节点广播一个路由请求分组，路由请求分缀中包含了 如下的信息：源节点地址、源节点序列号、广播i d ，目的节点地址和目的节点序列号，其 中源节点序列号是源节点所维护的本身的序列号，而目的节点序列号是源节点所知道的关 于该目的节点的序列号的最大值。 节点在收到路由请求后，首先查看其b i d 列表中是否已经包含了关 二该路由请求的信 息。如果是，则节点将简单的丢弃这个重复的路由请求分组；否则，节点将进行如下的动 作：1 ) 在路由表中添加一条临时反向路由用来转发可能存在的到达源节点路由应答，该反 向路由以路由请求分组的前一跳节点作为路由下一跳，以路由请求分组中的源节点序列号 作为路由的目的节点序列号，以路由请求分组的转发次数作为路由的跳数。2 ) 在路由表中 查找是否存在一条到达路由请求目的节点的有效路由，并且该路由的目的节点序列号大于 或者等于路由请求中的目的节点序列号，如果是，则节点需要构造一个路由应答( r r e p ) 分 组并且将该路由应答分组通过n , n j 添加的临时反向路由发送到路由请求的源节点；否则， 节点只需简单的将该路出请求分组再次广播给它的邻居节点。当目的节点收到路由请求后 就由目的节点发送路由应答到路由请求的源节点。 路由应答分组中主要包含如下的内容：目的节点地址、目的节点序列号和到达目的节 点的跳数。其中目的节点即为发起路由请求的节点。发送路出应答的节点使用在路由请求 传送过程中添加的反向路由单播一个路由应答分组。中间节点在收到路出应答后，将路由 应答中的路由跳数字段增一，同时更新到达路由请求目的节点的路出。当路由应答传送到 发起路由请求的源节点后，源节点就会启动路由选择策略决定是否使用新发现的路由进行 数据传输。 8 南京邮电人学硕i ： i j f 究生学位论文 第二章a dh o c 嘲络路由讪一没简介 a o d v 的路由维护过程非常褥台按需机制的约定，如果m a c 层协议提供a c k 机制( 如 i e e e 8 0 2 1 1 ) ， 则a o d v 会使用m a c 层信息确认分组是否成功到达下一跳节点；否则a o d v 通过在邻居节点问周期性的广播h e l l o 信息提供确认。 当节点确定与某个邻居节点间的链路失效后，需要通过路出错误的方式通知、务的源 节点。a o d v 路出表中包含了一个前驱节点列表，其中包含了所有使用该路由进行分组转发 的前驱节点。a o d v 发送路由错误给每个前驱节点，而每个时驱节点也会转发该路由错误信 主至到达业务的源节点。源节点在收到路由错误后，如果仍然需要到达浚目的节点的路 则节点需要发起新的路由发现过程。 9 南京邮电大学硕l ：研究生学位论史第三章蓝牙a dh o el 嘲络路出协泌尚介 第三章蓝牙a dh o c 网络路由协议简介 构造一个蓝牙散射网就是构建一个多跳的a dh o c 网络。对于路由而言，蓝牙环境提 供了很多的挑战。如前所述，虽然在a dh o c 网络的路由领域已经做了大量的研究，但是 大多数算法都假定网络的m a c 层采用8 0 2 1 1 协议。而蓝牙的m a c 层与8 0 2 1 l 不同，蓝牙 采用时分双工以及轮询接入的方式，并且蓝牙自组织网是基于主从模式的，两个蓝牙节点 只有形成主从关系才能相互传送信息，而主从机制不能直接使用传统自组织网络的路 上| 协 议。另外，蓝牙技术的其他一些特点，如分组的大小也会导致一些传统的路由协议省i 能：直 接应用于蓝牙a dh o c 网络。以d s r 路由协议为例，该协议在高动态的对等通信中有很好 的性能，但是在蓝牙自组织网中就不能很好地应用。因为蓝牙的分组很小，在a c l 链路中， 携带信息量最大的是d h 5 分组，该分组占用5 个时隙，也只能携带3 4 1 个字节的信息和 个1 6 b i t 的c r c 校验。而每个蓝牙收发器都具有一个4 8 b i t 的蓝牙设备地址，如图3 一l 所 示。该地址分成三个字段： l a p 字段：较低地址部分，包括2 4 b i t ； u a p 字段：较高地址部分，包括8 h i t ； n a p 字段：无意义的地址部分，包括1 6 b i t ； l a p 和u a p 形成b d - a d d r ，整个地址空间为2 3 2 。这样一来，每个中间节点要占用3 2 8 = 4 个字节的空间，一条完整的路径信息将占用很多分组空问，使得网络负载变褥相当大。 l s b2 481 6m s b 图3 一lb d a d d r 地址格式 因此，在为蓝牙散射网设计路由算法时，应该考虑蓝牙技术的特点。酋先，蓝牙= ! 点 很小、资源有限，因此，需要在节点存储大的信息表或者进行复杂处理的路幽方案都是不 可行的。所以，那些需要保存全局信息的方案如链路状态和距离向量方法就不是很好的选 择。其次，在蓝牙网络中，网关节点通过在所属的多个微微网之间切换来分配它在各个微 微网中的时间，因此通过多跳发送路幽查询是很耗时的。这将导致非常大的路由请求时延。 最后，蓝牙网络的结构是一个节点( 主节点) 控制一簇节点( 从节点) 。从菜种意义 = 说， 主节点是其所属微微网的代表。在这种结构的网络中，一个节点只需要维护关于主节点的 信息，主节点就可以提供给它微微网中其他从节点的信息。尽前，已经有相当数量的文献 塑塞些皇查兰塑土里塞生兰堡堡苎 塑兰塞堕要垒! ! ! ! 坚垫塑虫塑坚堕坌 提出了适用于蓝牙a d h o e 网络的路由协议。有些算法是基于现有的a d h o c 路由算法并结 合蓝牙技术的特性提出的，如基于z r p 的算法【2 】以及s c r p ( s c a t t e r n e tc o n s t r u c ta n d r o u t i n gp r o t o c 0 1 ) 算法【3 】；有些是结合散射网的构成协议来构造特定的路由协议，如文献 4 】构造了一个自路由散射网，该散射网内的路由算法非常简单；也有利用蓝牙技术的特点 提出的、蓝牙a dh o e 网络特有的全新的路由协议，如r v m 路由矢量算法1 7 1 ，但是还不 完善。下面将分别介绍这几类路由协议。 3 1 基于现有路由算法 迄今为止，相关文献中基于现有a dh o c 路由算法所提出的蓝牙自组网路由锋法并不 多，比较典型的有基于z r p 的算法【2 和基于簇的路由算法s c r p 3 。下面分别介绍这两种 算法。 3 1 1 基于z r p 的算法 2 z r p ( z o n er o u t i n gp r o t o c 0 1 ) 是一种利用集群结构、混合使用表驱动和按需路由策 略的a dh o o 网络路由协议。在z r p 中，集群被称作域( z o n e ) 。陔协议为了综合利用按需 路由和表驱动路出的各自优点，规定每个节点在区域内部采用表驱动路由协议，对于区域 外节点的路由则采用类似于d s r 中的按需路由机制寻找路由。 这里所介绍的算法借鉴了z r p 的思想，但是结合蓝牙技术的特点做了相应的改变。蓝 牙散射网中的主节点掌握了所在微微网中从节点的信息，而从节点可以从主节点获得同 微微网中其他从节点的信息。因此，只需要主节点发送含有本微微网信息的分组，从节点 可以从主节点获得这些信息。这样，区域内可以包含更多的节点而负荷并没有相应的等比 增加。对区域外面的节点，由于前面提到的原因，不使用d s r 算法而改用a o d v 算法进行 按需路由查找。 该路由方案由两部分组成：表驰动路由部分和按需路出部分。源节点酋先检查它是否 具有到目的节点的路径( 查找表驱动部分所建立的路由表以及按需路由部分所建立的路由 表) 。如果源节点不具有到目的节点的路径，那么节点将启动方案中的按需跪由部分。方 案中表驱动部分和按需路由部分所获得的路由信息将分别进行存储。下面简单介绍 - - f 两 部分的基本原理， 1 表驱动部分 查皇坚皇查兰堡：土婴垄竺兰竺堕兰笙兰要堕兰垒! ! ! ! 堕塑塑虫塑堡塑坌 在表驱动部分中，每个节点维护距它m a x h o p s 跳以内的节点的路由信息。每个主节 点将它的一跳邻居节点( 从节点) 的地址发给距它m a x h o p s 跳以内的节点。在链路管理 器协议数据包( l i n k m e n a g e rp d u ) 中发送这些信息，该p d u 称为l m pn c r g h b o r p d u 。 在l m pn e r g h b o r p d u 的p d u 头中设置一个t i m e t o 1 i v e 字段来限制该p d u 的m a x h o p s 。 如静所述，一个蓝牙设备的有效地址是3 2 b i t 。由于每个设备最多有7 个从节点，因此 一个l m pn e r g h b o rp d u 中的最大负载是3 2 字节( 7 个从节点的地址和主节点本身的地 址) 。此外，l m 头和t i m e t o 。l i v e 字段也个占一个字节，总共是3 4 个字节。根据蓝牙：基带 规范可知，一个d h l 分组最多携带2 8 个字节的信患，因此对于从节点数小于6 的主节点， 可以使用一个d h l 分组传送l m pn e r g h b o rp d u 。对于从节点数目大于等于6 的主节点， 仍然使用d h l 分组( l mp d u 通常是单时隙传输，a c l 链路中d h l 分组是举时隙传输的 分组中负载最小的，也就是说浚分组可以携带的信息量是最大的) ，具体的实现方法是： 主节点在每个l m pn e r g h b o rp d u 中只包含其中5 个从节点的信息，以循环的方式眺过两 个从节点的地址再选择5 个从节点。以一个含有7 个从节点的主节点为例，第一个p d u 携带从节点l 一5 的地址，下一个p d u 携带从节点3 7 的地址，再下一个携带5 7 和l 一2