（通信与信息系统专业论文）移动ad+hoc网络拓扑分割检测和避免技术研究.pdf

重庆邮电大学硕士论文 摘要 摘要 移动a dh o c 网络( m o b i l ea d - h o cn e t w o r k s ，m a n e t s ) 是由装备无线发射机和 接收机节点组成的无线网络通信系统，该网络具有移动性、自配置、自组织、自适 应以及自愈合等特性，能够灵活地应用于各种无任何固定通信基础设施的网络场景 中。在影响移动a dh o c 网络性能的各种因素当中，网络拓扑的连通性是一个不可 忽视的重要方面。因此如何检测出移动a dh o c 网络拓扑中的薄弱环节、增强网络 拓扑的连通性以防止网络拓扑出现分割，将是为上层通信协议提供良好的底层拓扑 支撑的拓扑控制技术研究的基础。本文研究主要有以下两个方面。 ( 1 ) 针对大多数文献中关于移动a dh o c 网络拓扑分割检测技术主要是检测网 络拓扑中的关键节点和关键链路，本文证明了以检测关键链路作为移动a dh o c 网 络拓扑分割检测技术存在局限性。为准确检测移动a dh o c 网络中导致网络拓扑分 割的关键节点，提出一种适应交叉链路的拓扑分割检测算法 c p d a ( c r o s s 1 i n k - t o l e r a n tp a r t i t i o nd e t e c t i o na l g o r i t h m ) ：通过在基本回路探测过 程中发布并利用邻节点对信息，c p d a 算法能够排除交叉链路对基本回路走向的影 响，从而解决了现有基于回路探测的分割算法d p d p ( d i s t r i b u t e dp a r t i t i o nd e t e c t i o n p r o t o c 0 1 ) 不适用于交叉链路的问题，使关键节点探测的准确度得以提高。利用 o p n e t 网络仿真工具对d p d p 和c p d a 算法进行网络建模仿真。性能分析结果表 明，c p d a 算法对网络拓扑没有特殊要求，在准确度和探测开销方面的表现优于 d p d p 算法。 ( 2 ) 提出一种基于功率调节的移动a dh o c 网络拓扑分割避免算法 p a b p a ( p a r t i t i o n a v o i d a n c eb a s e d o np o w e r a d j u s t m e n t ) 。p a b p a 算法是基于在短时间 内，邻节点度m 不变的条件下，增大基本回路度能消除网络中的关键节点i 。首先， 根据c p d a 算法探测网络中的关键节点i ，并在探测过程中，标记未构成基本回路 的邻居节点对；其次，通过功率控制技术使这些未构成基本回路的邻居节点对形成 直接链路，以增大关键节点i 的基本回路度m ，；最后，当节点i 的邻节点度m 和 基本回路度m ，满足代数关系m m ； h o p ：跳数( 表示转发h e l l o 消息包的节点数) s r c ：源节点地址 d e s t ：目的节点地址( 并将d e s t 置为1 ，表示广播) l o c a lx ：节点位置信息的横坐标 l o c a ly ：节点位置信息的纵坐标 ( 2 ) e l d r 包( e l e m e n t a r yl o o pd e t e c t i o nr e q u e s t ，基本回路探测请求包) ，其 包格式如图3 4 所示。包功能：完成基本回路探测，得出节点的基本回路度。 t y p et t l ( 8 b i t s )( 8 b i t s ) p r bi d ( 1 6 b i t s ) f r s ti d ( 1 6 b i t s ) s n di d ( 1 6 b i t s ) r c vi d ( 1 6 b i t s ) 图3 4 e l d r 包格式 t y p e ：1 ( e u ) r 包类型) ”亿：e l d r 包的生存期 p r b f l d ：探测发起节点的d 号 f r s t i d ：包经过的第一个中继节点的d 号 2 1 重庆邮电大学硕士论文第三章分布式拓扑分割探测算法及其仿真建模 s n di d ：每次发送节点的d 号 rcvi d ：每次接收节点的d 号 其次，介绍仿真中的邻居表( p o s i t i o n _ t a b l e _ p i t ) ，邻居表的结构为： t y p e d e fs t r u c tp o s i t i o n t a b l e h a td e s t _ a d d r , d o u b l ed e s t a d d r _ x ； d o u b l ed e s t a d d r _ y ； d o u b l ea n g l e ； d o u b l ec o n t r u c t t i m e ； 邻居节点的d 号 邻居节点位置信息的横坐标 邻居节点位置信息的纵坐标 厂节点与邻节点所构成的角度 表项生成的时间 s t r u c tp o s i t i o n t a b l e 牛n e x t ； p o s i t i o n t a b l e ； 与传统邻居表不同，本仿真中的邻居表中增加了邻节点位置信息和节点与邻节 点所构成的角度。这样做的目的有两个：第一，确定节点邻节点对；第二，在基本 回路探测过程中，根据右手定则遍历面方法，完成节点的选路功能。 在仿真过程中，需要对邻居表( p o s i t i o n _ t a b l e _ p t r ) 进行以下操作： ( 1 ) 查找。当节点接收到邻居节点发送的h e l l o 包时，首先需要查找邻居表中 是否已经有这个邻居节点。若有，更新表项生成的时间，不进行其他操作；若无， 则进行插入操作。 ( 2 ) 插入。将邻居节点信息插入到节点的邻居表( p o s i t i o n _ t a b l e _ p t r ) 中。根 据节点的位置信息和邻居节点的位置信息，可以计算节点和邻居节点所构成的角度 a 。注意，插入的顺序必须满足角度a n g l e 在邻居表( p o s i t i o n _ t a b l ep t r ) 中从小到 大的顺序。 ( 3 ) 定位。在基本回路探测过程中，中继节点收到上一个中继节点发送的e l d r 包，两个节点所构成的角度为b ，中继节点则在自己的邻居表中，定位比角度b 大 的角度中最小的角度c ，并以角度c 对应的节点作为下一个中继节点。若角度b 是 链表中的最大角度，则选择链表中最小的角度a 对应的节点作为下一个中继节点。 ( 4 ) 清除。清除邻居表中过时表项的信息。 最后，根据d p d p 算法逻辑上的行为，创建n o d er o u t e 进程模块。有限状态机 是o p n e t 用来实现进程模型的方式。基于有限状态机机制，o p n e t 才能以离散事 件仿真的方式协议行为的交互。它类似数字电路中的卡诺图，可以有效直观描述复 杂的一系列行为及它们之间的交互关系。o p n e t 中的状态机主要用来描述网络协 议，它是实现算法的基础。下面，将d p d p 算法划分为各个具体的行为，对应进程 模型中的有限状态机进行描述，如图3 5 所示。 重庆邮电大学硕士论文 第三章分布式拓扑分割探测算法及其仿真建模 图3 5d p d p 算法的状态转移图 ( 1 ) 状态机( i n i t ) 。仿真开始时，进程模型首先进入i n i t 状态，对节点进行初 始化。完成初始化后，激发一个自中断，离开i n i t 状态进入下个状态。 ( 2 ) 状态机( i d l e ) 。进程每完成一个状态，将仿真的控制权交给i d l e 状态， 直到下一个中断开始，i d l e 状态交出仿真的控制权，所以i d l e 状态也称为空闲状态。 ( 3 ) 状态机( s e n dr o u t e ) 。提取节点的位置信息，并填写h e l l o 包域中的内容， 周期性广播发送h e l l o 包，初始化邻节点度变量。 ( 4 ) 状态机( r i h a n dr o u t e ) 。填写e l d r 包域中的内容，周期性广播发送e l d r 包，初始化基本回路度变量。 ( 5 ) 状态机( r c v 。当 模块收到底层模块的包流后，进_ u p c o m i n ) n o d er o u t e 入r c vu p c o m i n g 状态，提取接收到的包类型。假若接收到的包的类型n 俾e 是0 ， 提取出h e l l o 包内的信息，计算出节点与邻居节点的夹角，完善邻居表 ( p o s i t i o nt a b l ep t r ) ，并统计节点的邻节点度。假若接收到的包的类型n 俾e 是1 ， 判断e l d r 包是否到达发起节点，如果是e l d r 包到达发起节点，则销毁e l d r 包， 判断f r s ti d 与r c vi d 是否是邻节点对，若是，将基本回路度加l ；若不是，保 持节本回路度不变。如果e l d r 包没有到达发起节点，则依据右手定则遍历面方法 选择下一跳节点，并且单播发送，保持基本回路度不变。最后，根据代数式 m m i 2 ，判断节点是关键节点还是普通节点。 3 3 2 节点模型 如图3 6 所示，表示节点的域模型。s o u r c e 和s i n k 模块是业务产生和销毁模块， 由于本论文研究的是网络拓扑分割技术，没有用到应用层的业务流。n o d e r o u t e 模 重庆邮电大学硕士论文第三章分布式拓扑分割探测算法及其仿真建模 块是具体实现d p d p 算法的模块，利用有限状态机实现算法的每个具体步骤，模拟 d p d p 算法的功能。w l a nm a ci n t f 模块完成上层( 网络层) 和下层( 数据链路层) 连接功能的接口。w i r e l e s sl a nm a c 模块用来仿真链路层随机接入信道协议，模块 采用的信道接入协议为i e e e 8 0 2 1 1 标准定义的d c f 协议，采用的访问机制为载波 监听多址接入冲突避免( c s m a c a ) 协议，仿真中采用i e e e 8 0 2 1 i b 。w l a np o r tt x 0 和w l a np o r t 是无线发信机和接收机模块，采用14个首尾相接的管道阶段来尽tx0 量模拟数据帧在信道中的传输，实现物理层的功能。m o b i l e 是节点的运动模型。 州如、p “扫i d钾k k 舶吃由 。 。i 图_ d 图3 6 节点的域模型 节点的运动模块的状态转移图如图3 7 所示。本文选择r a n d o mw a y p o i n t 为节 点的运动模型。其工作原理是在运动空间内随机取起始点s 和目的点d ，随机取速 度e ( 。，1 ，一) ，使用该速度从点s 沿直线移动到点d ( 其中v m ；。和分别代表节 点的最小速度和最大速度) ，节点运动到d 处时随机选取一个时间t p a u s e ，在这个 时间内e ( v 曲，v 一) 保持静止，这样完成一个s t e p 过程。将节点到达的目的点d 作 为下次运动的起始点s ，在运动空间内随机取一点作为目的点d ，重复s t e p 过程，直 至仿真结束。 一瓢：；爹0 譬掣鼍 ，弧、 、二- _ 图3 7 节点的移动模块的状态转移图 图3 8 表示的是节点o 的参数设置。节点的设置时，要保证节点含有全网唯一 的d 号。本论文中采用的节点传输半径是2 5 0 m 。数据链路层选择8 0 2 1 1 的m a c 协议。 重庆邮电大学硕士论文第三章分布式拓扑分割探测算法及其仿真建模 3 3 3 网络模型 图3 8 节点的仿真参数的设置 本文采用的是o p n e t l 4 5 仿真软件工具，建立d p d p 算法的拓扑模型。建立 的拓扑时，主要依据两种原则将节点均匀随机部署在k k ( m 2 ) 的正方形平坦区域 中：一种是在相同的节点密度下( 用p 表示) ，不同的节点数量( 5 0 ，1 0 0 ，1 5 0 ， 2 0 0 ，2 5 0 ) 。另一种是固定节点的数量，变化节点密度( 5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ， 1 2 ) ，如图2 所示。计算k 可根据公式： 尼= 眄 式( 4 1 ) 其中r 表示节点的传输半径，n 代表网路中节点的数目，p 表示网路中节点的 密度。根据公式，我们可以计算两组网络场景的边长k ( 单位：m ) 。在部署节点时， 必需要保证以下两点：( 1 ) 在场景中均匀分布节点；( 2 ) 网络拓扑的连通性。可以 通过选择适当的节点密度p 来保证网络是连通的。为了确定p 值，文献 4 2 】迸行了 大规模密集仿真实验，结果显示，当n 在5 0 5 0 0 之间时，选p = 9 ，则网络以接近 概率1 连通；假如允许5 左右节点不连通，则p = 6 。文献 4 2 】同时也说明，不论 静止还是移动网络，如果允许少量节点不连通，p = 6 仍然有效。为了使本文的研 究更具说服力，在固定节点数时，我们选择p = 5 为起点。 首先，取节点的节点密度p 为9 ，计算出不同的节点数量网络场景的边长，如 表3 2 所示。依据表中每个网络场景的边长的大小，在o p n e t 中搭建5 个网络场景， 节点数分别为5 0 、1 0 0 、1 5 0 、2 0 0 和2 5 0 。如图3 9 所示，是节点数为1 5 0 是的网络 场景。 重庆邮电大学硕士论文第三章分布式拓扑分割探测算法及其仿真建模 表3 2 不同节点数目网络场景边长( p = 9 ) 节点数目( 个)5 0 1 0 0 1 5 02 0 02 5 0 k ( m ) 9 9 1 0 1 4 4 01 7 1 61 9 8 12 2 1 5 图3 9 节点数为1 5 0 的网络拓扑场景( p = 9 ) 其次，固定节点数为1 0 0 ，计算出不同的邻节点度时的网络场景的边长，如表 3 3 所示。依据表中每个网络场景的边长的大小，在o p n e t 中搭建8 个网络场景， 节点密度分别为5 、6 、7 、8 、9 、1 0 、1 1 和1 2 。如图3 1 0 所示，是节点密度为5 的网络场景。 表3 3 不同节点密度网络场景边长( 1 0 0 个节点) p ( 个)567891 0 1 l 1 2 k ( 神 1 8 0 91 6 7 51 5 6 71 4 7 71 4 0 01 3 3 61 2 7 91 2 2 9 图3 1 0 节点密度为5 的网络场景( 节点数目1 0 0 ) 即使如此，我们也不能完全保证网络是连通的。所以，我们要对仿真中可能出 现的网络拓扑做以下处理： 一一一一一一一一一幛一一一一一一一一一一一一 辫蕤鬻 重庆邮电大学硕士论文 第三章分布式拓扑分割探测算法及其仿真建模 ( 1 ) 对于网络中可能出现的孤节点，忽略统计孤节点所得的仿真结果。 ( 2 ) 对于移动a dh o e 网络可能分割成几个连通域，由于d p d p 算法是分布式 的，最后仍将其作为一个连通域处理。 3 4 本章小结 本章介绍了d p d p 算法的基本原理和算法的具体步骤。后续的研究是基于 d p d p 算法，对d p d p 算法中存在的问题进行改进以及拓展。接着介绍了o p n e t 网络仿真软件，在o p n e t 仿真平台上搭建d p d p 算法，为下面的研究提供基础平 台。下一章，我们将对d p d p 算法不适应交叉链路进行分析，并提出一种适应一般 拓扑的移动a dh o c 网络拓扑分割算法。 重庆邮电大学硕士论文 第四章适应交叉链路的移动a dh o e 网络拓扑分割检测 第四章适应交叉链路的移动a dh o c 网络拓扑分割检测 移动a dh o c 网络是在没有固定基础设施的情况下，由具有无线传输功能的节 点白组织形成的网络。在节点随机部署时，可能会出现不同连通度的区域，导致网 络拓扑中出现关键节点。由于节点能够移动，所以移动a dh o e 网络有一个非常显 著的特征动态的拓扑，这样就导致网络拓扑经常会出现分割，即一个单一连通 的网络，分裂成两个或者更多的子网络。对于移动a dh o e 网络，一系列的应用正 在被研究，例如军事上的战场通信，在灾难时的应急通信服务，会议网络等。 4 1 理论分析 目前，移动a dh o e 网络拓扑分割探测技术主要是探测出网络拓扑中的关键节 点和关键链路。在本论文中，我们根据关键节点和关键链路的定义，归纳关键节点 和关键链路的内在联系。 导致关键链路失效的因素也可概括为两个方面：一方面是由于关键链路两端的 关键节点的失效或者移动导致关键链路断裂；另一方面由于关键链路在传输过程中 出现断裂，如图4 1 所示，由于关键链路中间出现障碍物，导致网络中的p d a 3 和 p d a 4 不能正常的通信，网络拓扑出现分割。 。pda5 l l 燃火! 一 p d a 6 障碍物 图4 1 障碍物导致关键链路的断裂 下面，我们运用图论中的知识来分析关键节点和关键链路之间的关系。 引理1 构成关键链路两端的节点一定是关键节点。 证明由关键链路的定义可知，关键链路会导致网络拓扑出现分割，可推出构 成关键链路两端的节点会导致网络拓扑出现分割。根据关键节点的定义，这种节点 就是网络中的关键节点。所以，构成关键链路两端的节点一定是关键节点。 将图g 中的关键节点构成的节点集合用c n ( n ) 表示；用c i n ) 表示网络中关键 链路两端的节点集。可以得n - 重庆邮电大学硕士论文 第四章适应交叉链路的移动a dh o e 网络拓亍卜_ 盆童! ! 坌型 性质1 在网络中，关键链路两端的节点集与关键节点的节点集满足： c l ( n ) cc n ( n ) 。 证明若想证明上述性质1 的正确性，即能在网络中找到某个关键节点，证明 这个关键节点不属于任意关键链路两端的节点，则命题成立。 如图4 2 所示，从这个简单的拓扑图，我们可以看出节点c 的邻节点度c 为6 ， 它的基本回路度m ，为4 ，计算得到节点c 的邻节点度c 与基本回路度m 。之差为2 ， 所以节点c 是一个关键节点。节点c 的邻居节点有 a , b ，d ，e ，f , g ，以节点a 为例来讨 论这些邻居节点的属性。节点a 的邻节点度d 为4 ，并且节点a 的基本回路度m 。为 4 ，所以节点a 是一个普通节点。同理可得节点b 、d 、e 、f 、g 也是普通节点。由此 可知，关键节点c 的所有邻居节点都是普通节点。并且由关键链路的定义的知，关 键节点c 与其所有的邻居节点构成的链路都不是关键链路。证毕。 p ab 一 队 一 沙 g q 图4 2 一个简单的网络拓扑图 根据性质1 ，我们会发现，基于探测关键链路的a dh o c 网络拓扑分割探测算法 存在局限性，只能探测网络中的部分薄弱环节。所以，本论文只讨论由于关键节点 引起的网络拓扑分割问题。为了有效地进行相关问题的研究，本文基于以下假设： 假设l 在网络初始部署节点时，保证网络拓扑是连通的。 假设2 本文只考虑由关键节点的失效或者移动引起的网络拓扑分割问题， 忽 略由链路层相互干扰或者障碍物等因素引起的链路断裂。 假设3 每个节点装备有g p s 系统，能够感知自己的位置信息。 4 2 网络模型 对于图g e ) 的网络模型，其中v 表示网络中的节点集，e 表示链路集邮1 。边 p = ( “，) e ，“，1 ，e 存在当且仅当”在1 ，的通信范围内。图g 中所有链路都是双 向的，例如，如果“在1 ，的通信范围内，那么v 也一定在“的通信范围内。因此，如 果( “，1 ，) e ，我们就说节点“和节点v 相互之间是邻居节点。假设网络中每个节点 重庆邮电大学硕士论文第四章适应交叉链路的移动a dh o e 网络拓扑分割检测 的通信半径是r ，定义d ( f ，) 为节点f 和节点- 之间的距离。如果( f ，j ) 叠e ，则 d ( f ，) = 0 0 。假设网络中的每个节点装备有g p s ( g l o b a lp o s i t i o ns y s t e m ) 接收机， 这样该节点就能够获得自己的坐标位置信息和一跳邻居节点的坐标信息。 为了便于论述，下面首先定义一些本文使用的概念。 定义1 ( 关键节点) ：是指如果一个节点的离去或者该节点失效，而使网络分裂 成两个或者更多独立的部分，那么，就称该节点为关键节点。 定义2 ( 邻节点度) ：节点f 的邻节点数目，即：m = f 墨| _ iu vi ( f ，) e ) l 。 定义3 ( 邻节点对) ：如果节点i 的2 个邻节点，k 满足：节点k 是以i 为顶 点沿e ( f ，) 顺时针方向上的第一条边所关联的节点，那么则称j ，k 为节点i 的一个 邻节点对( 如图4 3 所示) ，记为( ，七) ，。若e ( i ，k ) 和e ( i ，s ) 在同一条直线上( 节点k ， f ，s 共线) ，r e ( i ，七) i i e ( i ，s ) i ，则称k ，s 为节点i 的一个邻节点对( 如图4 3 所 示) ，记为( 尼，j ) ，。 图4 3 邻节点对和基本回路 定义4 ( 基本回路) ：设( ，七) ，是节点i 的一个邻节点对，并构成经过节点i 的 路p i ( ，k ) = j i k ，露( ，k ) = 只1 ( ，七) ，a 2 ( ，七) ，a 。( ，尼) ) 是不经过节点i 连 通，k 路的集合。如果层( ，k ) a ，可将所有路p ，p 只( ，k ) 在逻辑上等效为 一条路p ；( ，k ) ( 如图4 3 所示) 。称p ；( _ ，k ) - 与p j ( j ，k ) 构成的闭合回路为节点i 经 过( ，七) ，的一个基本回路，记为厶( ，七) 。 定义5 ( 基本回路度) ：节点i 经过不同邻节点对的基本回路总数，即 m f = i l i ( j ，k ) ij ，k 是节点f 的邻节点对) l 。 定义6 ( 右手法则遍历面) ：节点y 收到从节点x 发来的一个分组，选择下一跳 时，首先以节点y 为中心点，让边e ( y ，x ) 按逆时针方向旋转，相遇的第一个边e ( y ，z ) 就是下一跳路径，边的一端点z 即是下一跳节点( 如图4 4 所示) 。依此类推，最后 分组经历的路径为x y 专z x ，按顺时针次序遍历了该封闭的三角形区域( 即 面) 。并且，这种方法适用于任意的封闭多边形面。这就是右手法则遍历面。 重庆邮电大学硕士论文第四章适应交叉链路的移动a d h o e 网络拓扑分割检测 4 3c p d a y 2 一一一一一一一一一一一一一一一一一 x 图4 4 右手法则遍历面 z c p d a 算法是通过改进d p d p 算法的原理而提出的，改进的主要内容是基本回 路走向的校正。 4 3 1d p d p 算法及问题描述 定理1 在图g ( v ，e ) 中，节点f 是图g 中的关键节点，当且仅当该节点的邻节 点度m 和基本回路度m ，满足m m ，2 3 7 】【3 8 】【3 9 】。 d p d p 算法就是利用定理1 中节点f 的邻节点度m 和基本回路度m ，的代数关 系，判断节点是否是关键节点。所以，能够准确的判断发起节点的邻节点度和基本 回路度，对于判断该节点是否是关键节点非常重要。 在d p d p 算法中，基本回路的探测是通过右手法则遍历面来实现。该算法要求 网络拓扑必须是平面拓扑，即网络中不存在交叉链路。 定义7 ( 交叉链路) ：在一个平面网络g 商e ) 中，任意两条边相交，称为交叉 链路。如图4 5 所示，e ( q ，r )e ( f ，形) 相交，所以称e ( q ，r ) 和e ( f ，w ) 为交叉链 路。 图4 5 一个简单的交叉链路示例 基本回路探测时，由于交叉链路的存在，使得探测分组不能沿着邻居节点对回 重庆邮电大学硕士论文第四章适应交叉链路的移动a dh o e 网络拓扑分割检测 到发起节点，最终导致探测发生错误。 4 3 2 分析及解决方案 d p d p 算法在探测基本回路时，使用右手法则遍历面的方法。而在由单位圆图 u d g u j n i td i s kg r a p h ) 构造的一般拓扑中，由于交叉链路的存在，影响了右手法则的 正确选路，使得能构成基本回路的邻节点对无法构成回路。假设节点i 的邻节点对 能构成基本回路，以下从两种情况分析交叉链路对基本回路探测的影响，并提出解 决方案。 情况1 如图4 6 所示，节点n ，l 都是节点i 的邻节点，并且j k l 彼此也是邻 节点。节点i 可知：( ，k ) ，( k ，上) ，( 厶刀，是i 的三个邻节点对，并且e ( j ，l ) 和 e ( i ，k ) 构成交叉链路。节点i 发起基本回路探测，节点j 接收到探测包时，根据右 手法则遍历面的方法，选择下一跳节点l ，然后节点l 根据右手法则遍历面的方法， 将探测包转发回发起节点i 。但是，节点i 并不将这次探测判断为基本回路，因为这 次探测没有经过节点j 的邻节点对k 回到发起节点i 。由此可见这种情况下，交叉 链路会影响探测的结果。 k 3 l 图4 6 探测开始阶段出现交叉链路 情况2 如图4 7 所示，节点j k l 都是节点i 的邻节点，并且节点kl 一跳可 达，但是节点j 与节点k l 一跳不可达。节点i 可知：( ，k ) ，( k ，三) ，犯，刀，是 i 的三个邻节点对。节点m ，q , p 是节点j 和k 的中间节点。节点i 发起基本回路探 测，节点j 接收到探测包时，根据右手法则遍历面的方法，沿着节点m 和q ，转发 到p 。节点p 根据法则，将探测包转发给节点l ，节点l 转发给发起节点i 。然而， 节点i 也不将这次探测判断为基本回路，因为这次探测没有经过节点j 的邻节点对 k 回到发起节点i 。但是，从拓扑图中可以明显看出经过节点k 是可以构成回路的。 根据右手法则遍历面的性质 4 4 1 ，节点j 在选择下一跳是以e ( j ，i ) 逆时针旋转相交的第 一个节点，即节点m 。其他节点依此类推。因此，交叉链路并不影响探测中间节点 的选路，即节点m 、q 到p 。而是在发起节点i 构成交叉链路时，才会使基本回路 3 2 重庆邮电大学硕士论文 第四章适应交叉链路的移动a dh o c 网络拓扑分割检测 探测产生错误。 w 三 峨加_ ，重之、粥f 浮娑l k 、，1 三) r 多二一，。 图4 7 探测结束阶段出现交叉链路 解决方案节点i 发起基本回路探测，节点j 在收到节点i 发送的探测包时，根 据节点的位置信息，将其邻节点对k 置入探测包中，节点在选择下一跳时，首先判 断其邻节点集中是否有节点k 。若有，则直接发给节点k ，节点k 再转发给发起节 点i ；否则，按照右手法则选择下一跳。通过这种方法能有效地避免交叉链路对回 路探测的影响。 4 3 3c p d a 算法 根据关键节点定理和分析网络中的交叉链路，在d p d p 算法的基础上，提出一 种适用于静态或者低速运动的a dh o c 网络网络拓扑分割探测的c p d a 算法，该算 法能满足任意拓扑的探测e 4 5 1 。为获得定理中的m 和m ，c p d a 算法包括邻节点探 测和基本回路探测两个部分。 1 邻节点探测 在c p d a 算法中，节点通过与周围节点交互h e l l o 消息来获取邻节点度数信息。 网络中的节点f 周期性地广播发送h e l l o 消息告知周围节点自己的存在，其中h e l l o 消息中主要包括节点d 号和位置坐标信息。通过统计接收到h e l l o 消息的数目，节 点可以确定其邻节点度数m ，并根据邻节点相对位置关系和长度大小可以确定它的 邻节点对。 2 基本回路探测 在一般的网络拓扑中，由于存在交叉链路，拓扑图中节点i 与其邻节点对所构 成的面可能与其他平面相重叠，而节点i 的基本回路构成的平面实际上对应于其中 的一个平面。因此，c p d a 算法通过采用右手法则遍历面的方法来探测邻节点对之 间可能存在的基本回路，利用节点i 的邻节点对的信息，选择基本回路对应的平面。 探测过程是通过发送基本回路探测包( e l d p ，e l e m e n t a r yl o o pd e t e c t i o np a c k e t ) 来实现 3 3 重庆邮电大学硕士论文第四章适应交叉链路的移动a dh o c 网络拓扑分割检测 的，其格式如图4 8 所示。其中t y p e 是包类型；p r b i d 记录探测发起节点的d 号：f r s t i d 用于记录分组所经过的第一个中继节点的d 号；e n d i d 记录第一 个中继节点对应的邻节点对的m 号；s n d i d 和r c v i d 分别是每次中继时发送 节点和接收节点的d 号；n e i b i n f o r 用于记录探测发起节点的所有邻节点的d 号和位置信息：1 1 l 记录分组的生存期。 t y p e lp r b i 。l f r s t i de n d i d s n d i d r c v _ i dn e i b i n f o r硎 图4 8 e l d p 探测包结构 下面以网络中的某节点f 为例，详细介绍基本回路探测的算法流程。 步骤1 节点i 将m ，清零，向其邻节点广播发送e l d p 探测包，启动基本回路 探测。e l d p 探测包的p r bi d 域置为节点i 的d 号；n e i b i n f o r 域置为节点i 的 所有邻节点的d 号和位置信息；t r l 置为o 。 步骤2 节点i 的某个邻节点，在收到e l d p 探测包后，首先将自己的d 号，置 入该分组的f r s ti d 域。更新1 儿。获取n e i b i n f o r 的信息，根据节点，的位置 信息和n e i b i n f o r 中所存储的节点i 的所有邻节点的d 号和位置信息，可以确定 节点，的邻节点对k 的d 号，置入e n di d 中，并将n e i b i n f o r 清空。 步骤3 遍历本节点的邻节点中是否有e n di d 中的d 号；若有，转到步骤6 ； 否则，转到步骤4 。 步骤4 按照右手法则确定下一跳并向该节点单播发送e l d p 包。 步骤5 节点收到e l d p 探测包后。首先判断1 1 儿是否过期。若是，则丢弃该 探测包；否则，更新1 l ，转到步骤3 。 步骤6 将e n di d 域中的d 号的节点k 作为下一跳，单播发送e l d p 探测包。 步骤7 节点k 收到e l d p 探测包后，更新t r l 。将发起节点i 作为下一跳，单 播转发e l d p 探测包。 步骤8 节点f 收到e l d p 探测包后，更新耶 l ，并将探测包销毁，m ，加1 。 重庆邮电大学硕士论文第四章适应交叉链路的移动a dh o c 网络拓扑分割检测 4 3 4 算法示例 图4 9c p d a 与d p d p 算法示例 本节，我们借助一个局部拓扑图，具体分析d p d p 算法和c p d a 算法在基本回 路探测中的差异。 如图4 9 所示，以节点i 为发起节点，其邻居节点为x 、o 、n 、j 、q 、m ，由 此可知节点i 的邻节点度为，= 6 。所构成的邻节点对为：( x ，d ) ，( o ，川， ( ，) ，( ，q ) ，( q ，m ) ，( m ，x ) ，。下面，我们根据d p d p 算法和c p d a 算法 的步骤，分别介绍在基本回路探测过程中，两种算法所得出的结果。 ( 1 ) d p d p 算法基本回路探测示例 在d p d p 算法中，基本回路探测是通过发起节点i 广播发送基本回路探测包， 邻节点接收到基本回路探测包后，根据右手法则遍历面的方法，单播发送给下个节 点，最后看是否能回到发起节点。具体路径如表所示。 表4 1d p d p 算法基本回来探测 发起节点 邻节点回路路径是否经邻节点 是否是基本 对构成回路回路 ixi - x - n i否否 0i - o - n - i 是 是 ni 二n h g b j - i是是 j1 4 k l - p m i否否 q - q - m - i是 是 mi m - z - 、，二x i 是是 从表4 1 中我们可以看出，由于在探测过程中，有些回路没有经过邻节点对， 最后判定为非基本回路。所以节点i 的基本回路度m ，= 4 ，其邻节点度，= 6 ，故 ，一m ，= 2 ，可以判定节点i 为关键节点。但是，我们从图中可以直观的看出，节 点i 是个普通节点而不是关键节点。由此我们可以推断出，在交叉链路存在的网络 重庆邮电大学硕士论文第四章适应交叉链路的移动a d h o c 网络拓扑分割检测 拓扑中，d p d p 算法的探测结果会出现错误。 ( 2 ) c p d a 算法基本回路探测示例 在c p d a 算法中，节点i 广播发送的基本回路探测包中含有每个邻节点对的基 本信息。所以，基本回路探测包在选择下一跳时，首先遍历节点的邻居表，查看是 否有邻节点对的信息。如果有，则直接转发给邻节点对节点，最后发送给发起节点。 例如，邻节点x 收到节点i 广播发送的基本回路探测包后，遍历节点x 的邻居表( 节 点i