（通信与信息系统专业论文）ktrp核心树融合与分离算法设计.pdf

摘要 摘要 核心树路由协议( k t r p ) 是一种新的无线自组织网络的自组织无线路由协议。 该协议提出了分层结构的无线自组织网络模型，这种分层结构的自组织网络模型 将网络中的节点分成构成自组织网络骨干的移动路f l q 器：( w i r e l e s sr o u t e o 和作为接 入层的移动主机( w i r e l e s sh o s t ) 两部分，从而减少了路由算法的开销，易于组建较 大的网络。 在k t r p 的基础上，本论文设计了一种应用于核心树之间进行通信的路由算 法一核心树融合与分离算法。此算法可以适用于大部分能够运行k t r p 的网络。 使相互独立的核心树之间能够进行通信。 本论文首先分析了现有的k t r p 路由协议的现状和特点，然后针对融合与分 离算法的目的进行需求分析，按照算法的需求对原有的k t r p 报文进行一定得修 改，最后在修改的基础上设计了核心树融合与分离算法。论文的第一、二两章介 绍了k t r p 算法的一些基本概念，并详细分析了k t r p 算法的四个基本子算法。 第三章详细分析核心树融合与分离算法的需求。第四章在对原有的k t r p 报文格 式进行修改的之后，对核心树融合与分离算法进行了详细设计。 关键字：自组织网路，树形路由算法，核心树路由算法 a b s t r a c t a b s t r a c t k e r n e lt r e er o u t i n gp r o t o c o l ( k t r p ) i san e ww i r e l e s ss e l f - o r g a n i z i n gn e t w o r k p r o t o c 0 1 t h i sp r o j e c td e s i g n sah i e r a r c h i c a lw i r e l e s sn e t w o r ka r c h i t e c t u r e ，a n dn o d e so f t h i sk i n do fn e t w o r ka r ed i v i d e di n t ot w oh i e r a r c h y ，t h eu p p e r ，w h i c hi sc o m p o s e do f w i r e l e s sr o u t e r s ( w r ) ，i st h eb a c k b o n eo f t h en e t w o r ka n dt h el o w e ri st h ea c c e s sl a y e r ， w h i c hi sc o m p o s e do fw i r e l e s sh o s t s ( w h ) t h em u l t i h o pr o u t i n gp r o t o c o lr u n so n l y o nw r ；t h u st h er o u t i n gp r o t o c o lc o s ti sr e d u c e d ，s ot h i sk i n do fa r c h i t e c t u r ei sa d a p t e d t ol a r g e rw i r e l e s ss e l f - o r g a n i z i n gn e t w o r k t h i sp a p e rd e s i g n e dar o u t i n gp r o t o c o lw h i c hm a k ek e r n e lt r e ec o m m u n i c a t ew i t h e a c ho t h e ri nt h eb a s eo fk t r p ，c a nb ec a l l e dk e m e lt r e ec o m b i n i n ga n dd i v i d i n g p r o t o c 0 1 i tc a nb eu s e di nm o s to fk t r pn e t w o r k ，a n dm a k ek e r n e lt r e ec a n c o m m u n i c a t ew i t ha n o t h e rk e r n e lt r e ew h i c hi sd i f i e r e n tf r o me a c ho t h e r f i r s t ，t h i sp a p e rd i s c u s st h ek t r p a n dt h e np r o p o s i n gt h ek t r pi nc h a p t e r1a n d c h a p t e r2o ft h i sp a p e r t h i sp a p e ra n a l y z e sa n dd e s i g n st h ek e r n e lt r e ec o m b i n i n ga n d d i v i d i n gp r o t o c o li n3 ，4c h a p t e r k e y w o r d s ：s e l f - o r g a n i z i n gn e t w o r k ，b a c k b o n et r e er o u t i n gp r o t o c o l ， k e r n e lt r e er o u t i n gp r o t o c o l l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：至当盔笙e t n ：勿驴舌年乡月髟日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：饧勰导师签名：歪竺蝈 日期：拶护年f 月2 日 第一章引言 第一章引言 从上个世纪9 0 年代开始，随着集成电路技术的飞速发展，便携式电脑、p d a 和智能移动电话等移动终端产品在性能上越来越好，在价格上越来越平易近人， 使人们对移动性计算( m o b i l ec o m p u t i n g ) 的要求也越来越高：作为二十世纪最伟大 的发明之一，计算机网络已经进入了人们的生产和生活的各个方面，人们希望这 些移动终端设备不仅仅能够移动，而且能够随时随地联网。因此，将i p 网络互联 技术与个人无线通信相结合的研究已经成为目前计算机和通信领域的研究热点之 1 1 研究背景 目前能够提供个人无线数据通讯的技术已有很多，比较有代表性的有蜂窝式 数字移动通信系统( g s m c d m a ) ，无线局域网( w l a n ) 和低轨卫星通信系统。 以上几种现有的个人无线数据通讯技术，虽然其应用场合、使用成本、能够 提供的最大速率各有不同，但是它们有一些共同的特点。其一，这些网络在使用 之前必须先布设一定的基础设施( i n f r a s t r u c t u r e ) 。无论基站的建设，接入访问点 ( a c c e s sp o i n t ，a p ) a p 的布设，卫星的发射，都不是一蹴而就的。其次，这些网络 都是通过一定的设备为用户提供无线接入，这就决定了网络的覆盖范围一定是有 限的。而在某些情况下，人们需要“随时随地”的“立即”联网。但是这些网络 都不能满足这样的需求。 针对人们的这种需求，一种新型的移动a dh o c 网络( m o b i l e a dh o c n e t w o r k ， m a n e t ) 被设计出来，这种网络不需要借助已有的网络设施，有通信需求的移动用 户通过一定的协议和算法协调，自己组建一个独立的网络实现数据通信。 a dh o e 源于拉丁语，是“特别的，专门地为某一即将发生的特定目标或局势 而不为其它的”意思。这里提出的a dh o c 所标称的就是一种特定的网络结构，强 调的是多跳、自组织、无中心的概念，所以移动a dh o c 网络是多跳无线网络 电子科技大学硕士学位论文 ( m u l t i h o pw i r e l e s sn e t w o r k ) 【l l 。 适用于动态拓扑结构的高效实用的无线路由协议是移动a dh o c 网络的关键和 难点。目前，i n t e m e t 工程任务组0 e t f ) 专门成立了一个移动a dh o c 网络工作组 ( m a n e t ) ，其主要工作就是针对无线a dh o c 多跳网的开发和研究。同时，国内外 许多大学和研究机构都在研究该领域圆【3 】【4 】【5 】o 而在对a dh o c 网络的研究过程中，提出的k t r p ( k e m e lt r e er o u t i n gp r o t o c o l l 核心树路由协议算法是一种新型的易于实现的无线自组织网络路由算法。 k t r p 算法的核心思想是主动地维护w r 的逻辑拓扑结构为树形1 6 】 6 】。 在这种树形的逻辑拓扑结构中，位于树根的w r 的级别最高，每个w r 仅能 与其上级w r 和下级w r 直接通信，如果要访问其它w r ，则需要经过其父w r 转交。 k t r p 协议能够满足自组织网络自组织组网、动态拓扑发现、快速拓扑形成和 移动动态路由的要求，能够很好地支持w h ( 无线主机) 和w r ( 无线路由器) 基于 t c p i p 的通信。 = 2 l e v e l = 3 图1 1k t r p 算法的w r 核心树示意图 但是k t r p 中对于独立核心树之间的通信问题并没有做周全的考虑，如果两 棵或者多棵独立k t r p 核心树之间希望能够进行通信，必须要通过重新建立一个 2 第一章引言 更大的核心树。但是重新建立一棵核心树可能会使原来的两棵或者几棵核心树的 通信质量下降或完全中断，这在通信中应该尽量避免。 本文的目的就是在原有的k t r p 算法的基础上，分析研究并实现一种可以让 相互独立的k t r p 核心树之间不需要中断通信就能够实现互相通信的算法。 1 2 课题简介 k t r p 核心树融合与分离存在着很多种情况，而本文只讨论了其中的独立的核 心树与核心树之间的融合与分离。 1 2 1k t r p 核心树融合与分离算法的提出 树的融合与分离会在很多情况下都会发生，最为普遍的情况是k t r p 树的一 个节点进行移动的时候，该节点与连接在它下面的子节点形成一个独立的子树， 该子树有可能会重新接入到核心树网络上，本文称之为融合；也有可能会再次脱 离网络，本文称之为分离。另外一种情况是两棵相互独立的核心树，由于距离相 互靠近了希望能够进行互通，也会因为距离的拉远自动的脱离了网络。更为复杂 的情况是，独立核心树a 的一棵子树，移动到了树b 的通信范围内，并作为树b 的子树进行通信；并且在一定的时间过后，又移动回树a 重新接入。 由此看来，树进行融合与分离的情况有很多，而本文仅仅讨论了其中相互独 立的核心树之间进行融合与分离的算法。这是因为核心树之间的融合与分离具有 一些实际的应用意义。 比如，在一个救灾团中，有时候需要把各个救灾小队分工到不同的区域去进 行工作，这时各小队就作为一个独立的核心树存在着；而有时候又需要把几个小 队集合到一起，集中力量进行工作，这时就是核心树的融合；由于工作需要又再 次把小队分开作业，这时是核心树的分离。在这里，核心树融合与分离算法就有 着合适的应用环境。诸如此类的环境还有许多，这里就不一一列举。 1 2 2 融合与分离算法所适应的网络环境 显然k t r p 核心树融合与分离算法不能够适应所有的无线网络环境，但是在 电子科技大学硕士学位论文 下面的网络环境下，该算法有着十分重要的实际应用价值。 其一，存在着许多棵相互独立的核心树。 其二，核心树的运动会经常出现相互靠近和相互远离的情况。 其三，核心树内部的网络拓扑是相对稳定的。 满足以上条件的网络环境就适合运行k t r p 核心树融合和分离算法。 k t r p 核心树融合和分离算法实现的基础是k t r p 算法。 第二章k t r p 算法 第二章k t r p 算法 k t r p 核心树融合和分离算法实现的基础是k t r p 算法。所以本章对k t r p 算法进行了详细的介绍和分析。在此基础上，才能更好的分析和研究k t r p 核心 树融合与分离算法。 2 1 移动a d h o e 网络路由算法 目前在a d h o c 网络中，有几种比较流行的单播路由协议：目的序列距离矢量 路由协议( d e s t i n a t i o n s e q u e n c e dd i s t a n c ev e c t o r ，d s d v ) ，l 临时按需路由算法 ( t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m ，t o r a ) ，动态源路由协议( d y n a m i cs o u r c e r o u t i n g ，d s r ) ，a dh o c 按需距离矢量路由协议( a dh o co n d e m a n dd i s t a n c e v e c t o r ，a o d v ) 等等【”。 这些路由协议按照路由策略来划分有三种类型：先应式( p r o a t i v e ) 路由协议、 反应式( r e a c t i v e ) 路由协议以及混合式路由协议。 先验式路由协议又称为表驱动路由协议，在这种路由协议中，每个节点维护 一张包含到达其它节点路由信息的路由表。当检测到网络拓扑结构发生变化时， 节点在网络中发送更新消息，收到更新消息的节点将更新自己的路由表，以维护 一致的、及时的、准确的路由信息，所以路由表可以准确地反映网络的拓扑结构。 源节点一旦要发送数据分组，可以立即获得到达目的节点的路由。因此这种路由 协议的时延较小，但是路由协议的开销较大。先验式路由协议有d s d v 和 k t r p 8 1 1 9 。 反应式路由协议又称为按需路由协议，是一种当需要发送数据时才查找路由 的路由算法。在这种路由协议中，节点不需要维护及时准确的路由信息，当需要 向目的节点发送数据分组时，源节点才在网络中发起路由查找过程，找到相应的 路由。与先验式路由协议相比，反应式路由协议的开销较小，但是数据分组传送 的时延较大。反应式路由协议有t o r a 、d s r e l 0 1 1 1 】【1 2 】。 电子科技大学硕士学位论文 在拓扑结构动态变化的a dh o c 网络中，单独使用先验式路由协议会产生大量 的控制报文，增加网络的开销；如果采用反应式路由协议，又需要为每个报文查 找路由，增加网络传输延时。因此，就产生了一种将先验式和反应式的优点结合 起来的混合式路由协议：在大型的a dh o c 网络中，在局部范围内的数据包传输采 用先验式的路由协议；如果节点较远，则采用反应式的路由协议。a o d v 就是这 样的一种混合式的路由协议，它借用了d s r 基本的按需路由的发现和维护路由机 制，还运用了d s d v 的连跳路由、序列号以及周期性发送更新信息的机制等。 2 2 k t r p 算法概述 k t r p 算法的核心思想是主动地维护w r 的逻辑拓扑结构为树形。 树形结构的最大好处是不会产生路由环路，因为在网络拓扑结构不断变化的 无线自组织网络中，路由环路产生的几率会比固定网络中多得多。虽然在其他的 一些无线自组织网络路由算法中也有一些办法来避免路由环路，但是这些算法都 不免过于复杂，实现比较困难，对设备的资源开销也比较大。根据图论的知识， 树形结构是不会存在环路的，所以树形结构在网络拓扑中能够被经常的用到。形 结构是不会存在环路的，所以树形结构在网络拓扑中能够被经常的用到。 如图2 - 1 所示，w r l 处于树根的位置，是等级最高的w r ，等级次高的是w r 2 和w r 3 ，其它的是更低的等级。一个w r 可以有几个下级w r ，而只能有一个上 级w r ，不然就不是树形的结构了，会产生路由环路。 图2 1k i r p 核心树 6 = 2 第二章k t r p 算法 所有的w r 只能够和它的上级或下级进行通信，而不能和其他的w r 进行直 接通信，如果w r 想要和非自己上下级的w r 进行通信，必须要通过其上下级的 w r 进行转发。有时候是通过上级w r 转发，有时候要和自己的下级的下级w r 进行通信时，就通过相对应的下级w r 转发。 如图2 1 所示所有的双箭头表示物理无线链路。有双箭头连接的w r 说明它 们在对方无线电波覆盖范围之内，在链路层可以直接通信。但是实际上，在k t r p 算法中并不是所有有双箭头连接的w r 都可以直接进行通信的。只有图中实线双 箭头所连接的w r 之间可以直接通信。而虚线双箭头连接的w r 之间虽然是在无 线电波覆盖范围之内，但是在k t r p 算法中是不允许它们直接通信的。它们之间 的通信只能依靠其他w r 的转发来实现。 如图2 - 1 所示，w r 2 和w r 3 之间虽然在无线电波覆盖范围之内，但是它们之 间不允许直接通信，必须要通过它们的上级w r l 来转发。类似的w r 5 和w r 6 也不能直接通信，w r 5 把报文发送到它的上级w r 2 ，w r 2 在把报文转发到w r l ， w r l 把报文转发到w r 3 ，w r 3 最后把报文转发到目的节点w r 6 。 k t r p 采用以上这种需要转发报文的通信方式的目的是使w r 不需要掌握所 有的网络拓扑结构，而只需要掌握局部的网络拓扑结构，即只需要知道哪些w r 和w h 是与自己直接相连的，直接相连的节点之间直接通信。而对于那些不是直 接相连的w r 和w h 只需要知道报文应交给哪些w r 来转发即可，并不关心报文 的转发经过了多少w r 。 这样做的好处是，避免了先验式路由算法里面每次网络拓扑变化都要通知所 有的节点的弊端，大大减少了路由算法的开销。另外和反应式路由算法相比，由 于知道了路由的大概方向，所以不用每次都去查找路由，极大地缩短了网络延时。 当w r 离开的时候，k t r p 协议通过报文通知相关的w r 网络拓扑的改变， 把该w r 的路由从相关w r 中删除。当w r 重新加入网络的时候，k t r p 算法将 其重新加入网络，并通知相关w r 添加其路由。当w r 在网络中移动的时候，会 引起网络拓扑结构的变化，当它远离原来的上级w r 时，在k t r p 算法中会通知 相关的w r ，但并不立刻把它的路由在其他的w r 中删除，因为有可能此w r 会 在很短时间内从另外一个上级w r 接入，所以k t r p 算法只是改变了此w r 在其 他相关w r 中的状态，然后等待一段时间，如果此w r 重新接入了网络再进行相 电子科技大学硕士学位论文 应的路由修改。 w h 在网络中移动、离开和接入网络的算法和w r 的类似。由于w h 是在w r 下进行工作的，所以w r 移动或者其它的影响网络拓扑的动作都会引起其下面所 属的w h 的路由变化。w r 的移动或者离开，都会使其下的w h 重新接入网络。 2 3k t r p 算法分析 核心树算法包括树生成算法、树维护算法、树形路由算法以及w h 接入位置 维护算法。以下将在核心树和汇聚点的概念的基础上对各算法进行分析。 2 3 1 核心树结构 核心树就是无线自组织网络中由所有w r 按照一定的相互关系组成的逻辑树。 核心树结构是l 订r p 算法的实现基础，所以在研究k t r p 算法之前必须先要了解 核心树的构成。核心树由一个根节点和许多下级节点组成【1 3 】。 p a r e n t w r l e v e l = 1 s e l f w r l e v e l = 2 c h i l d w r l e v e l23 d e s c e n d a n tw r l e v e l = 4 图2 2核心树结构图 根w r ( r o o tw r ) ：根w r 是无线自组织网络的发起者，网络的初 始化即是从根w r 开始的，一个无线自组织网络有且只有一个根w r 。通 第二章k t r p 算法 常，根w r 是连接外部网络的出1 2 1 ，所有w h 和w r 访问外部网络都要 通过根w r 。用于用户访问控制的r a d i u s 服务器一般也通过根w r 连 接，或是直接在根w r 上运行。 级别e v e d ：级别决定w r 在核心树上的层次划分，根w r 级别始 终是“1 ”，直接连接到根w r 的w r 级别为“2 ”，依次类推。 父w r ( p a r e n t 阡傻) ：与w r 直接相连的级别比自己小“1 ”的w r ， 对于除了根w r 的其它w r 来说，父w r 有且仅有一个；根w r 没有父 w r 。 子w r ( c h i l d 阡偎) ：与w r 直接相连的级别比自己大“1 ”的w r ， 子w r 可以有多个，位于核心树枝末端的w r 没有子w r 。 d e s cw r ( d e s c e n d a n tw r ) ：位于核心树上自本w r 开始的分支上， 且级别比自己大“2 ”或以上的所有w r n 级核心树( l e v e l k e r n e l t r e e ) ：级别最大的w r 的级别为n 的核 心树，称为n 级核心树。 如图中所示，w r l 是此核心树的根w r ，w r 2 的级别为2 ，w r l 是w r 2 的 父w r ，w r 3 和w r 4 是w r 2 的子w r ，w r 5 和w r 6 是w r 2 的d e s c e n d a n t w r ， w r 3 ，w r 4 ，w r 5 ，w r 6 都是w r i 的d e s c w r 。此核心树是一个4 级核心树。 电子科技大学硕士学位论文 2 3 2 , e 聚点的概念 c 图2 3汇聚点的概念示意国 汇聚点是指自组织网络中两条到根w r 的路径的交叉点处的w r 。汇聚点在 k t r p 算法中是一个重要的概念。汇聚点概念的引入使路由协议的算法变得高效 【i 习 当网络的拓扑结构变化时，只需通知汇聚点以下的w r ，避免了全网的路 由更新动作，降低了先应式的路由算法开销。 当需要在两个w r 之间路由报文时，报文只需递交到汇聚点而不必到根节 点。 如图2 3 所示，w r h 和g 的汇聚点为e ；w ha 和c 的汇聚点为根w r 。当 w r 或w h 发生位置变化时，w hb 的新旧接入点的汇聚点为g ；w rj 在核心树 上的新旧位置的汇聚点为e 。 2 3 3 核心树生成算法 当无线自组织网络中的一个w r 作为根w r 启动后，网络开始初始化，核心 1 0 第二章k t r p 算法 树开始生成 1 3 1 。 1 ) 根w r 启动，产生一个仅有一个节点的一级核心树。 2 1 能够与根w r 直接通信的w r ，通过w r 加入协议( w r a o i np r o t o c 0 1 ) ，加 入此核心树，并把自己的级别设为2 ；此时的核心树是一个以根w r 为中 心的星形结构，核心树是二级核心树。 3 ) 未加入网络的其它w r ，通过w r 加入协议，找出能够与自己直接通信的 己加入网络的w r ，选择其中级别最小的w r 作为自己的父w r 加入核心 树，并设置自己的级别为父w r 级别+ 1 。 4 ) 未加入网络的w r 重复步骤3 ，直至所有的w r 加入核心树。至此，多级 核心树形成。 2 3 4 核心树维护算法 核心树的维护算法时实现自组织动态路由的关键。实时跟踪网络的拓扑结构 的变换，动态维护核心树的结构，及时调整路由是核心树维护算法的主要任务【1 3 1 。 1 ) 当w r 成功加入核心树之后，通过w rh e l l o 协议( w rh e l l op r o t o c 0 1 ) ，周期 性的向自己的父w r 和子w r 发送特定格式的k t r p 报文，以声明自己 的存在； 2 1 每个w r 收到父w r 和子w r 的声明报文后，更新与之相关的定时器； 3 ) 若一定时间未收到声明报文，则说明自己与此w r 的连接中断； 4 ) 若子w r 的定时器超时，则k t r p 将通过w r 更新协议( w r _ u p d a t e p r o t o c 0 1 ) 将此子w r 和此w r 以下的d e s cw r 从网络上删除： 5 ) 若父w r 的定时器超时，则说明w r 及其子w r 和d e s c w r 已经从网络 上脱离，这些w r 将通过w r 加入协议( w r j o i np r o t o c 0 1 ) 重新加入核心树 网络。 6 ) 对于再次加入核心树的w r ，当其在树上的位置发生了变化时，k t r p 将 通过w r 更新协议( w r _ u p d a t ep r o t o c 0 1 ) 将此w r 的新的位置信息通告给 相关的w r 。 电子科技大学硕士学位论文 7 ) 核心树的结构变化必然引起w h 的接入位置的变化，w h 的位置信息的维 护需要核心树维护算法和w h 位置维护算法共同完成。 此处描述的算法忽略了一些细节问题。 2 3 5 树形路由算法 树形路由算法是基于每个w r 所掌握的关于网络的拓扑结构信息的【1 3 】。 w r 掌握的网络的拓扑结构的信息包括以下方面： 与自己直连的w r ，包括父w r 和子w r 与自己直连的w h 对于d e s c w r ，仅知道在自己那个子w r 下，不关心级别 对于由子w r 接入的w h 和d e s cw r 接入的w h ，仅知道在自己那个子 w r 下，不关心级别 除了上述的四类节点之外的其它节点的信息一无所知。 从以上的描述可知，越接近根w r ，掌握的w r 和w h 的数量也越多，但是 位置信息也越模糊，根w r 掌握了所有的w r 和w h 的位置信息，但是对于大多 数的节点，它仅仅知道一个“大方向”。但是这个大方向对于报文的路由来说已经 足够。 实际上，树形路由算法是一个逐步求精的过程，从级别数低的w r 到级别数 高的w r ，每次向目的地前进一步，方向就越精确一些，直至目的w r 或目的w h 的接入w r ，从而有了准确的方向( 即最后一跳) 。 综上所述，树形路由算法如下： 对于目的节点是w r 的报文： 1 ) 若目的w r 是与自己直连的w r ，包括父w r 和子w r ，则通过网络信道 直接投递； 2 ) 若目的w r 是自己的d e s c w r ，则将报文投递给所属的子w r ； 3 ) 若是未知w r ，则将报文投递给父w r ； 1 2 第二章k t r p 算法 对于目的节点是w h 的报文： 1 ) 若目的w h 是从本w r 接入网络的，则接入信道直接投递给w h ： 2 ) 若目的w h 是从子w r 接入的w h 或d e s c w r 接入的w h ，则将报文 投递给所属的子w r ： 3 ) 若是未知w h ，则将报文投递给父w r ； 对于未知合法目的地址的报文：投递给父w r 。 2 3 6 w h 位置接入算法 适应分层的网络结构是k t r p 算法与其它自组织路由算法的区别之一。掌握 w h 的准确的位置信息是自组织网络正确投递报文的前提【”】。 1 ) 当有w h 接入或重新接入到核心树的某台w r 时，自组织网络的w h 接 入模块将通知k t r p 模块，k t r p 根据自己掌握的关于此w h 的原来的位 置信息，通过w h 更新协议( w h将此的新的位置信_ u p d a t ep r o t o c 0 1 ) w h 息通告给相关的w r 。 2 ) 当有w h 离开自组织网络时，自组织网络的w h 接入模块将通知k t r p 模块，k t r p 会通过w h 更新协议( w h将此 从自组u p d a t e p r o t o c 0 1 ) w h 织网络上删除。 3 ) w r 的加入和离开网络引起的其下属的w h 的位置信息的变化，将通过核 心树维护算法的协助，通告相关的w r 。 电子科技大学硕士学位论文 第三章对核心树的融合与分离技术的分析 本章对核心树的融合与分离技术进行分析和研究，并提出了几个实现算法必 须要解决的问题，并给出了相对应的解决方案。 3 1 核心树的融合与分离需要考虑的问题 本文的目标：实现k t r p 核心树的融合与分离算法。 核心树在融合时需要考虑的问题： 核心树之间的区分。由于使用的是相同的k t r p 协议，所以必须要避免两 棵核心树之间互相产生通信干扰。又要让希望相互通信的两棵或者多棵核 心树能够互相通信。 当两棵或者多棵核心树之间要融合的时候，需要考虑到避免路由环路。单 独的一棵k t r p 核心树是不可能产生路由环路的，因为它是树形结构。但 是当k t r p 核心树融合在一起的时候，原有的网络拓扑结构将会发生变化， 有可能会出现路由环路。 尽量保持各核，i l , 树内部网络通信的正常，至少不应该导致核心树内部严重 的通信堵塞。因为融合时，网络拓扑结构会出现一定的变化，所以网络通 信质量会有所下降，甚至会导致核心树内部网络通信失败。 融合过程中尽量减少对网络拓扑的变动，并保持网络拓扑的树形结构不变。 保持树形拓扑结构是k t r p 的基本要求，所有以k t r p 算法为基础的算法 设计都必须符合该要求。 核心树在分离时需要考虑的问题： 区别哪些w r 和w h 是属于同一棵核心树的。应该在分离时，区分出哪些 w r 和w h 是属于正在远离的核心树，然后对相关w r 发送报文修改路由。 1 4 第三章对核心树融合与分离算法的分析 分离后的核心树的内部都应该保持通信正常。既不应该让离开的核心树内 部通信失败，更不能使被离开的核心树内部通信失败。 在融合和分离的过程中都要考虑到的问题： 核心树之间是否使用相同的通信信道对算法的影响。 核心树的优先级问题。 两棵核心树之问的融合与分离能够适用的算法，在多棵核心树之间的适用 性问题，还要考虑到在融合树与融合树之间的适用性问题。 核心树融合范围的问题，即是在什么范围内核心树之间可以进行融合，而 在超出了多大范围后将会发生分离。 单向链路问题。 m a c 访问方式对无线路由协议的影响。 不稳定链路对协议的影响及策略。 本小结将对核心树的融合与分离过程进行分析，研究在此过程中所遇到的问 题和对应的方案。 3 2 核心树问的通信信道使用策略对算法的影响 通信信道使用策略基本上有两种： 一种就是所有的核心树都用统一的信道来进行通信，本文称之为单信道模式。 这时需要考虑到树与树之间的相互干扰问题，必须通过上层的路由策略使树与树 之间的通信不互相干扰。这种模式的算法设计是本文的主要讨论内容。 另一种就是各核心树使用不同的信道来进行内部通信，本文称之为多信道模 式。比如各树采用不同频率的无线电波来进行内部通信，因为不同频率的无线电 波是不会相互干扰的，所以核心树是感觉不到其他核心树的存在的。如果树与树 之间需要相互通信，一是通过上层的统一进行通信：二是调节通信信道，使希望 能够相互通信的所有树处于统一的通信信道上。在本文中只讨论第二种互通方式， 因为第一种互通方式不在融合与分离算法的范畴内。 电子科技大学硕士学位论文 用单信道模式进行通信，由于要考虑到树间干扰问题，所以算法会相对复杂， 实现相对困难。但是，相同的信道使树与树之间的融合不需要进行信道切换，所 以融合与分离时，更易于保持大部分网络的通信。 多信道模式可以使算法的实现更为简单，因为不用考虑树与树之间相互干扰 的问题，所以融合与分离算法都相对简单。但是由于需要通过改变信道来实现互 通，不可避免的在融合或分离的时候会有一部分网络不能进行通信，信道的切换 会使网络通信中断。 分析并比较在不同信道情况下的算法特点，可以知道多信道模式下的融合与 分离算法的优点是简单，比单信道模式下的算法更容易实现，当需要互通的时候， 所有把希望互通的树设置为相同信道即可，不用进行优先级比较。但是由于设定 了固定不变的互通信道，所以当一棵已经完成融合的树与与另外一棵已完成融合 的树相互接近的时候，不可避免的要互相干扰，严重时有可能会导致通信中断。 这种情况下需要通过单信道模式下的算法策略才能够解决，而这又导致了算法的 复杂化。假如采用单信道模式算法就不用考虑这个问题，虽然需要增加优先级算 法，但是其适应能力明显比采用固定互通信道的策略更强。 本文主要对单信道模式下的融合与分离算法进行详细的分析与设计。 3 3 核心树的优先级 在原有的k t r p 算法中，核心树是没有优先级的，这是因为k t r p 算法主要 是针对单棵核心树的路由算法，并没有对多棵独立的核心树之间的互联互通进行 深入的研究，而在单棵核心树内不存在优先级的问题。 但是本文的目标是多棵核心树之间的相互融合与分离算法，不可避免的要考 虑多棵核心树之间的关系，必须要考虑到当两棵或者多棵核心树融合时，到底是 由哪棵核心树作为主干来发起融合，如果不对这些进行统一，算法就无法实现， 因而设定核心树的优先级必不可少。 设定核心树的优先级需要达到的目的： 树与树之间需要一个标示来表示自己，区别于其它的树。 融合时需要依靠优先级来确定由哪棵树作为融合的主干，并作为各算法实现 第三章对核心树融合与分离算法的分析 的基础算法。 更为复杂的情况下，通过核心树的优先级，可以判断出融合过的树之间的优 先级别。 本文的优先级策略是：用一个序号代表一棵核心树树的优先等级，序号越小 等级越高；同时本文规定，完成融合的树比未融合过的核心树拥有更高的优先级； 同样是完成融合的核心树之间，融合次数最高的核心树拥有最高优先级；如果融 合次数相同，那么拥有的最小序号的融合树优先级最高。 以上规定的依据是如下：本文总是希望在融合时是“小”的核心树融入“大” 的核心树。所谓的“小”是指该树的网络规模小、节点少；所谓的“大”是指树 的网络规模大，节点多。因为融合时，作为主干的核心树的路由变化较小，而正 在融入的核心树路由变化较大，所以“小”的核心树融入“大”的核心树有利于 减少网络变化时引起的通信质量下降。在一般情况下，同一系统的所有核心树的 节点规模都是类似的，所以核心树融合次数越多的核心树，在大部分情况下都具 有更多的子节点，即具有更大的网络规模，以这些“大”的核心树为主干进行融 合有益于减少通信振荡。当然也会存在许多特殊的情况，对于不同情况再用不同 的优先级策略。 3 4 单向链路问题 如果采用相同的无线信道进行通信，那么就必须要考虑到由于通信的双方无 线电传输范r e ( t r a n s m i s s i o nr u n g e ) 不同，而导致的单向链路问题。 n o d 2 图3 1无线网络中的单向链路示意图 电子科技大学硕士学位论文 如图所示，无线节点n o d l 与无线节点n o d 2 的传输范围分别是r s l 和r s 2 ， 其中r s l r s 2 ，则存在如图所示的可能性，即n o d 2 在n o d l 的传输范围之内而 n o d l 在n o d 2 的传输范围之外。这种情况就会造成两个节点之间的直接的通信 中断。即其中一个节点能够收到对方发送的帧但是对方无法接收此节点发送的帧。 这种情况被称之为单向链路。实际单向链路问题还可能由隐藏终端( h i d d e nn o d e ) 现 象引起，并与节点的接收灵敏度有关，但是无论如何，单向链路现象是普遍存在 的。 目前的多跳无线网络路由协议的研究多处于理论研究和算法提出阶段。这些 提出的算法通常都会假设所有节点的无线电接收和发送范围是一致的，即如果a 节点能够收到b 节点发送的帧，b 一定也能收到a 发送的帧。这种假设虽然在一 定程度上简化了协议的算法，但是在实际实现中却会出现问题，有时甚至会关系 到算法是否收敛、协议是否失效。 既然单向链路的现象是通信的双方有一方不能收到对方的数据，那么尽早地 通过这条单向的通信通道通知对方就是打破这种局面的解决办法。根据这个原则， k t r p 协议对单向链路做了很多的保护措施。例如，p a r e n t w r 在j r e p l y t i m e r 超时 如果还未收到j o i nr e p o r t 就会向c h i l dw r 发送k i c kc h i l dw r 报文，此 报文作为一种通告措施，如果接受w r 发现发送w r 不是自己选定的p a r e n t w r ， 就会忽略此报文；如果发送w r 是自己选定的p a r e n tw r ，则说明自己和p a r e n tw r 之间存在单向链路，这样此c h i l dw r 就会重新发起一次加入过程。k t r p 的h e l l o 报文中包含父子w r 的i p 地址，也主要是为了处理w r 之间的单向链路问题。这 是一种处理单向链路的通用的手段，而不是局限于某种协议，当w r 收到的p a r e n t w r 或c h i l d w r 的h e l l o 报文中没有自己的i p 地址时，就说明自己和此w r 之 间的链路是单向的，对方由于多次丢失自己发送的h e l l o 报文，已经把自己删除。 知道了这些信息，再做进一步的操作就是水到渠成了。 本文在融合与分离算法中同样考虑到了这些问题，融合后的核心树中如果出 现了单向链路，那么应该采用类似的策略。因为子树有可能是一棵独立的核心树， 所以c h i l dw r 在收到k i c kc h i l dw r 后不一定会重新发起另一次加入过程， 而是保持其内部的通信并等待下一次的融合。 第三章对核心树融合与分离算法的分析 3 5 m a c 访问方式对无线路由协议的影响 i e e e 8 0 2 3 局域网在m a c 层的标准协议是c s m a c d ( c a r r i e rs e n s em u l t i p l e a c c e s sw i t hc o l l i s i o nd e t e c t i o n ) ，即载波侦听多点接入冲突检测。但由于无线产品 的适配器不易检测信道是否存在冲突，因此i e e e 8 0 2 1 1 定义了种全新的协议， 即c s m a c a ( c a r r i e rs e n s em u l t i p l e a c c e s sw i t hc o l l i s i o n a v o i d a n c e ，载波侦听多点 接a 冲突避免) 。一方面，通过载波侦听查看介质是否空闲；另一方面，通过一定 的时间等待算法避免冲突，使信号冲突发生的概率减到最小。不仅如此，为了系 统更加稳固，i e e e 8 0 2 1 l 还提供了带确认帧a c k 的c s m a c a 。在一旦遭受其他 噪声干扰，或者由于侦听失败时，信号冲突就有可能发生，而这种工作于m a c 层 的a c k 此时能够提供快速的恢复能力【1 4 】【“1 。 当一个协议规定需要接受方确认的数据帧发送后，发送方会等待对方的a c k 帧，如果在一定的时间内没有收到a c k ，发送方会重发此帧，多次重发后此帧被 丢弃。 在实际的i e e e 8 0 2 1 1 适配器中，对于不同的i e e e 8 0 2 1 1 帧的处理是不一样的， 对于r t s c t s ( r e q u e s tt os e n d c l e a rt os e n d ) 和a c k 这种需要马上处理的短帧一 般都是固件( f i r m w a r e ) 直接处理( 包括发送和接收) 而不是交给驱动程序。实际上 i e e e 8 0 2 1 1 的a c k 帧对于大部分的数据帧都适用，但是对于广播的数据帧，发送 方却不会期望接受到a c k ，因为不知道谁是明确的接收者。这样，广播帧由于缺 少了a c k 机制的保护，比单播的数据帧就更容易丢失。当网络比较繁忙，冲突加 剧的情况下就更加严重。 由于一般路由协议是工作在u d p 层之上的，当协议报文是u d p 广播报文时， 广播i p 地址就会映射到m a c 层的广播地址上，根据以上的讨论，这种路由协议 报文丢失的几率要大于单播的路由协议报文。 对于此问题，k t r p 采用的解决方法包括： n 减少采用的广播路由报文的种类； 多数情况下广播路由报文仅作为一种通告机制，作为加快拓扑收敛的一种 手段； 3 ) 在冲突的可能性增大时，通过增加报文的发送次数和延长超时时间来减少 1 9 电子科技大学硕士学位论文 由于报文丢失引起的拓扑振荡； 4 ) 在广播报文丢失后，有其它的手段恢复正确的拓扑结构，一般是通过定时 器来实现。 3 6 不稳定链路对协议的影响及策略 由于无线通信的特性决定，无线链路的出现不稳定的几率比有线链路高得多。 因此，有必要考虑针对无线链路的不稳定性制定特定的应对策略。在k t r p 协议 中，当c h i l d w r 检测到与p a r e n t w r 之间的无线链路中断时，此w r 自己会重新 发起加入网络的过程。但是对于下挂在自己的子树下的w r 和w h ，有两种不同 的策略。 第一种策略是，c h i l d w r 并不通知自己子树上的w r 和w h 关于自己的p a r e n t w r 丢失的消息，而只是在自己重新加入网络成功之后，通过w r 和w h 更新协 议，更新整个网络的拓扑结构。显然，这种策略最大限度地降低了协议的处理开 销和带宽开销，这在无线网络