（计算机软件与理论专业论文）ad+hoc网络中保证覆盖的广播方法的研究.pdf

论文题目： 专业： 硕士生： 指导教师： a dh 0 c 网络中保证覆盖的广播方法的研究 计算机软件与理论 刘聪 张治国副教授 摘要 广播是在移动a dh o c 网络中被，“泛应用的一个基本操作有效的广播算法要求能 在保证覆盖的基础上选择一个小的传送节点集在实际的物理网络当中，由于节 点的快速运动而的使网络的物理拓扑结构在不断的变化各个节点在发送信息时 由于不能获得及时的网络物理拓扑结构的更新信息而作出的错误决定使得广播信 息的覆盖不能被保证，我研究了有关移动a dh o c 网络( m a n e 丁) 中的保证覆盖的广 播问题中的几个算法目的是在动态的a dh o c 网络中决定一个较小的传送节点集 而又保证网络中每个节点都被覆盖这些算法解决了移动a dh o c 网络中虚拟网络 的连通、链路的有效和本地视图的一致方面存在的问题，扩展了一种能有效的减 少移动a dh o c 网络中传送节点数目的循环本地方法，提出了一种高效的本地自我 剪枝算法来进步减少移动a dh o c 网络中传送节点数目具体地说本文提出了三 种新的算法其中使用准缉矛移移安全籀路方法( s l a t ) 通过在链接信息中加入准 确的计时信息保证了移动a dh o c 网络中的虚拟网络的连通和链路的有效，基本上 保证了本地视图的一致，在s l a t 的基础上痧t 属触在趱掰万方搓使用的优先级分 类生成方法和局部优先级大小控制方法减少了传播节点地数目而且解决了旧算法 当中需要周期的全局复位的缺点，可放丢弹标法的艿点集算拦( s u n ) 使用比以往 算法更精确的剪枝方法加快了剪枝的效率和速度为了验证和进一步考察所提出 的算法，我在自行编写的模拟实验程序中对所提出的算法进行性能分析和比较 从大量的模拟实验的出的数据表明：在s l a t 算法能有效的保证覆盖：当网络的 密度有一定大时，即使放宽其中的一些条件仍保持较高的覆盖率：s u n 算法就连 通支配节点集的大小和收敛速度而言优于改经的i l s 算法，因此优于现有的其它 算法实验中还对其它关键参数的取值对剪枝算法的影响进行了考察和分析 关键词：移动a d l o c 网络( m a n e t ) ，广播，保证覆盖，本地循环算法，模拟 t n ：l e ： m a j o r ： n a m e ： s u d e r v i s o r ： ar e s e a r c ho nc o v e r a g ee n s u r e db r o a d c a s t i n gi na dh o cn e t w o r k c o m p u t e rs o f t w a r e t h e o r y c o n gl i u z h ig u oz h a n g( a s s o ci a t ep r o f e s s o r ) a b s t r a c t is t u d i e ds e v e r a la l g o r i t h m so nt h ep m b l e mo fc o v e r a g ee n s l l r e d b r o a d c a s t i n gi n m o b i l ea d h o cn e t w o r k s ( m a n e t s ) t h eo b j e c t i v ei st od e c i d eas m a l ls e to f f b r w a r d i n gn o d es e tt h a te n s u r ec o v e r a g ei nm en e 觚o r k m yr e s e a r c h e ss o l v e dt | l e p r o b l e m so fc o n n e c t i v i t y o fv i n u a ln 咖o r k ，t l e a v a i l a b i l i t yo f1 i 1 1 k s a n dt h e c o n s i s t e n c yo fl o c a lv i e wi nm o b i l e a d - h o cn e 押o r k ，e x t e n d e da 1 1 n e r a t i v el o c a l s o l u t i o nt h a tc a ne 币c i e n t l yr e d u c em en 啪b e ro ff o 州a r d i n gn o d e si nm o b i l ea d h o c n e t w o r k ，a n dp r o p o s e da 1 1e f f i c i e l l tl o c a ls e l f - p m n i n ga l g o r i t l l 】mm a tf h n h e rr e d u c e st h e n u m b e ro ff b 州a r d i n gn o d e s s p e c m c a l l y ，t h i sw o r kp r o p o s e d3n e wa l g o r i t h m s ： c “旭f n 妇w 舶4 c c “m 据n 小f ，培( s l a t ) 咖e sc o l l n e c t i v i t yo f t h ev i n i l a ln e 觚o r k a 1 1 dt h ea v a i l a b i l i t yo fl i n k s ，a n db a s i c a l l ye 1 1 s 1 1 r e st 1 1 ec o n s i s t e n c yo fl o c a lv i e w ；口月 蹦f 删如df f 删f f v e 肠c d ，s o m f f d 聪t h a tc o u l dr e d u c en 啪b e ro ff o r w a r d i n gn o d e sa 1 1 d s 0 1 v et h ep r o b l e mo fp e d o d i c a lg l o b a lr e s e ti nt h eo l dm 就h o db yu s i n gd i f ! e h e n t p r i o r i t yr a n g e sf o rf b 州a r d i n gn o d e sa 1 1 dn o n - f b 刑a r d i n gn o d e sa n d am e m o dt o p r e v e mt h eo v e r n o wo fn o d ep r i 耐t i e s ；fd 厂矾川口r 妇6 如d 如( s l 刀邯a i g o r i t h mi s m o r ee 饭c i e n tt h a no t h e rl o c a ls e l f - p r u 越n ga l g o r i t h mf o ri tu s # sam o r ea c c u r a t e m e 1 0 dt op e r f b n ns e l f p m n i n 晷i n 也ec n do ft l l i s 、v o r k ，s i m u l a t i o nc x p 谢m e m sa r e p e r f b m e dt oa 1 1 a l y z et h ep r o p o s e ds c h e m e s ，a n dm ee 腩c t i v e n e s so ft h ep r o p o s e d s c h e m e si sc o n 6 n e di n 也es i m u l a t i o ne x d 甜m e i i t s ， k e y w o r d s ：m o b i l ea d h o cn e l w o r k s ( m a n e t s ) ，b r o a d c a s t i n g ，e n s u r i n gc o v e r a g e i t e r a t i v el o c a ls 0 1 u t i o n s i m u l a t i o n i i 第1 章引言 因为a dh o c 无线网络( 或者简称a dh 0 c 网络) 的动态特性，全局的信息或基础设 施如最小生成树不再适合用于a dh o c 网络的广播洪水法( b 1 i n d f l 0 0 d i n g ) 是 种简单的不需要全局信息或基础设施的广播方法在洪水法当中每一个信息包被 网络中的每个节点传递一次洪水法能保证覆盖：它能确保广播的信息包被整个 网络中的每一个节点收到( 假设不存在m a c 层冲突和节点高速运动引起的丢包) 但是因为无线通信都是通过广播进行的，由洪水法引起冗余传输会造成广播风暴 的问题 1 在广播风暴中会存在节点发送信息的竞争和信息包之间的冲突 自我剪枝方法是一种减少广播中的冗余信息的有效方法与洪水法不同，在自我 剪枝的广播协议 2 ， 3 ， 4 ， 5 ， 6 ， 7 中每一个节点通过”h e l l o ”信息 收集邻接节点的拓扑结构和从广播的信息包中取得广播的历史信息( 也叫动态信 息) 每一个节点在特定的广播中决定它的角色：成为一个传播节点并传播广播 信息包，或者成为一个非传播节点( 也就是自我剪枝了) 并且不传递广播信息包 传播节点集包括发起广播的信息源节点形成一个连通的支配节点集( c d s ) 并能保 证覆盖一个节点的集合是支配节点集仅当网络中的每一个节点要么在这个集合 内要么是一个这个节集中的节点的者吸收点如果是否传送信息的决定是根据静 态信息来作出的，对应的算法叫做静态算法，否则叫做动态算法静态算法和动 态算法都是本地算法，也就是说在每个节点上所作的决定都不是依赖于全局信息 或者一些基础设施的 支配节点集( d s ) 已经被广泛地应用在移动a dh o c 网络选择传输节点的过程中当 所有的传输节点集形成一个支配节点集，网络中的所有节点就称为能到达的当 一个支配节点集是连通的，任何两个在支配节点集的节点能由支配节点集的其它 中洲节点连接起来如果一个支配节点集是连通的它就被称为连通的支配节点集 ( c d s ) 连通的支配节点集作为虚拟的通信中枢已被广泛地应用在广播和路由协 议中，如o l s r 8 ，在高效的广播当中，只有连通的支配节点集中的节点需要传 递广播信息包，而其它的节点只接收信息包但并不传递它们在0 l s r 8 中，链 路状态信息只存储在支配节点中连通的支配节点集的构造方法根据判定传送状 态时每个节点上所需的信息可以分为全局，半全局，半本地，和本地几种 9 本地方法只使用本地附近范围内节点的拓扑结构来决定本节点的状态并且节点的 这些状态是不传播的，也就是说每一个节点的状态并不依赖于其它节点的状态 因此从扩展性可动态环境中的维护两方面来说本地方法是最理想的方法 广播一个信息包到整个网络是一个基本的操作，它在移动a dh o c 网络中有广泛的 应用例如，在些路由算法如d s r 1 0 ，a o d v 1 1 ，z r p 1 2 ，和l a r 1 3 中，当要通知错误信息以从路由表中擦除无效的路由时，广播被用在路由发现过 程中广播还可以在快速移动的移动a dh 0 c 网络中作为可靠组播的有效机制广 播协议可以被划分为确定和不确定两种不确定的方法如【1 ，n 4 通常在每个 节点使用简单的方法，当收到一条广播信息时，以概率p 继续传播广播信息但 是，不确定的广播方法不能保证完全的覆盖确定的广播方法可以保证完全的覆 盖，它又可以进一步同过使用的邻接节点的信息划分为基于位置信息和基于邻接 节点集信息两种在基于位置信息的广播协议中，假设邻接节点的位置信息是可 以得到的，而在基于邻接节点集的广播协议，能用于只有邻接节点集的信息可以 得到的时候位置信息可以在生成较小的传送节点集方面提供有效地帮助但是 它也伴随着一定地代价：位置信息需要其它地硬件地帮助，如g p s 其它种类的 信息可以归类在上述两种模型之间，它们包括：给出信息到来地角度的方向信息 和基于收到信息的强弱的距离信息，其中距离信息只需要很简单的附加硬件设备 所有的这些模型都假设有某种的硬件支持本文的考虑只限定在只使用邻接节点 集合信息和距离信息的确定的广播协议 图1 _ 1 在广播的过程中，每个节点根据邻接节点的信息决定它的传送状态，这些信息 是根据每个节点的邻接节点集构造的，对应的广播过程叫做自我剪枝在图卜1 中，褐色的点是传播节点，绿色的节点是非传播节点节点周围浅绿色的圆圈内 部的是该点的卜跳邻接节点所有的信息源节点都是传送节点大多数现有的 广播方法都假设底层的网络拓扑结构在广播过程中是静态或者是半静态的，它的 邻接节点的信息可以被及时的更新在 1 5 中的结果表明现有的静态网络中的广 播方法当节点移动的时候就传送率来说性能很差消息传送失败的原因有两个： 冲突：一条发向一个目标节点的信息和另外一条信息冲突在图卜l 中，如果从 节点3 0 和节点3 9 的广播消息在节点0 处冲突，那么节点0 就会收不到任何的消 息 节点的移动：一个曾经是邻接的节点移动到当前节点的传送范围之外，也就是说 这个邻接节点不再是邻接节点了在图中，当节点3 l 移动出节点2 0 的传送范围后 以节点3 l 为根的一支节点就可能收不到广播信息 从 7 的结论可以知道冲突引起的效果可以被一个很短( 如l 毫秒) 的随机延迟有 效地消除，在静态的网络中何以取得很高的传送率( 9 9 ) 由节点的移动引起的 传送失败是主要原因因此，在本文中，我把只关注于由节点的移动引起的传送 失败设计一个本地的保证覆盖的广播协议的困难主要如下 ( 1 ) 网络的拓扑结构随时变化，即使在广播的过程中 ( 2 ) 本地的卜跳信息是由”h e l l o ”信息周期内接收到的”h e 儿o ”信息构造的为 了减少严重的”h e l l o “信息的冲突，每个节点异步的开始各自的”h e l l o ”信 息周期，使得很难保证各个节点的本地视图的一致 ( 3 ) k 一跳信息( 即使是很小的k ) 的收集时引起的延迟使得当节点移动时本地视图 不能反映当时的网络拓扑结构 以上几个困难造成由本地视图组合而成的虚拟网络并不一定是连通的，虚拟网络 中的连接并不一定在，及由本地视图组合而成的全局视图不一定一致 本文的主要贡献如下 ( 1 ) 提出了第一个本地的广播算法来处理存在覆盖范围不同，”h e 儿o ”信息周期 长度不同，并且移动的节点的网络中保证覆盖的广播的方法一使用准确 计时的安全链路方法( s l a t ) 解决了这种网络中的逻辑网络的连通，连接的 有效，和本地视图的一致的问题 ( 2 ) 对在有覆盖范围不同，”h e l l o ”信息周期长度不同，并且移动的节点的网络 中存在的逻辑飚络的连通，连接的有效，和本地视图的一致的问题进行了 例子分析对使用准确计时的安全链路方法中的一些参数的选择进行了数 学的分析 ( 3 ) 扩展的本地循环方法，通过使用一种优先级的分类生成方法和局部优先绂大 小控制方法有效地减少了传播节点地数目而且解决了旧算法当中需要周期 的全局复位的缺点 ( 4 ) 提出了可被去掉标志的节点集算法( s u n ) 使用比以往算法更精确的剪枝方法 加快了剪枝的速度和算法的收敛速度 ( 5 ) 进行了模拟实验对所提出的算法进行性能分析，对所提出算法的进行了讨论 还对其它关键参数的取值对本地剪枝算法的影响进行了考察和分析 本文的结构如下：第2 章给出了一些基础知识和相关工作第3 章给出本文提出 的3 个算法，第4 章进行了模拟实验，第5 章总结了本文 4 第2 章相关研究 2 1自我剪枝的广播协议 一个移动a dh o c 网络通常使用一个有向图g 作为模型，其中g = ( v ，e ) ，v 是一个 移动节点的集合，e 是一一个无线链路的集合一条链路( u ，v ) 存在于节点u 可节点 v 之间当且仅当u 和v 之间的物理距离小于u 的发射距离r w u 和d a i 在 1 6 中 提出了一种高效的基于自我剪枝的广播协议叫g e n e r i c 在自我剪枝协议中每一 个节点根据它的本地k 一跳信息决定自己的传播状态每一个节点默认是传送节 点，当满足g e n e r i c 中的覆盖条件时，它就可以变成一个非传播节点( 即被剪枝 掉) 任意一个在节点集v 中的节点v ，它的0 一跳邻接节点集h 。( v ) 就是 v ，它的真讵 的k 一跳邻接节点集，h k ( v ) ，是有的节点u 的集合，其中( w ，u ) g ，且u h k 1 ( v ) w 凡( v ) ，x k 1 节点v 的k 一跳邻接节点集，( v ) = h o ( v ) u h 。( v ) u h 。( v ) u u ( v ) ，也就是离开节点v 的距离小于等于k 跳的节点的集合节点v 的 k 跳连接信息，g 。( v ) ，就是n 。( v ) 的导出图，除去连接( w ，u ) ，其中w m ( v ) 但是 u h ，( v ) 当中，x k 一条从w n 。( v ) 出发到达u h x ( v ) 的连接不属于k 一跳链接 信息，从u h 。( v ) 出发到达w n 。( v ) 的链接( u ，w ) 则属于k 一跳链按信息 每一个接待那通过周期性的与它们的邻接节点交换它们的( k 一1 ) 一跳信息来构造它 的k 一跳信息因此，k 个回合的通过”h e l l o ”信息在邻接节点之间的累积的邻接点 信息的交换对于在每个节点上收集k 一跳的信息是必要的”h e n o ”信息也能传播 节点的优先级，其中这些优先级既能是动态的( 例如节点的i d ) 也能是静态的( 例 如节点的度数) 在广播过程中，每个节点也可以从收到的信息中提取一个已经 访问过的节点的集合，也就是曾经传送过这个广播信息的节点使用k 一跳信息， 优先级，和访问过的节点的信息，每个节点就可以根据以下的g e n e r i c 算法中的 覆盖条件决定它的状态( 传送或不传送) 覆盖条件 3 1 ：一个节点v 的状态是非传送状态如果对于任意两个邻接节点u 和 w ，存在一点条代替的路径把u 和w 通过一些优先级高于v 的中间节点或者是被访 问过的节点作为中间节点连接起来 g e n e r i c 算法中的覆盖条件决定适用于每个节点的覆盖范围大小都相等( 也就是 说只有双向连接，没有单向连接) 的节点模型下面给出一种由g e n e r i c 算法中 的覆盖条件改动而成的适用于每个节点的覆盖范围大小不必相等( 也就是说既有 双向连接，也有单向连接) 的节点模型的覆盖条件 覆盖条件 ：一个节点v 的状态是非传送状态如果对于任意的支配节点( d o m i n a n t n o d e ) u 和任意的吸收节点( a b s o r b e n tn o d e ) w ，存在一点从u 到w 的支配路径通 过一些优先级高于v 的中间节点或者是被访问过的节点作为中间节点连接起来 可以证明自我剪枝算法在静态的网络中能保证覆盖在这里我使用反正法假设 在一个广播中没有收到广播信息包的节点集u = v f n 。( f ) 不是空集，其中v 是所有节点的集合，f 是传输节点的结合，n 。( f ) 是传输节点集f 的吸收节点集 假设w = ( u ) 一u ，其中n d ( u ) 是节点集u 的支配节点集，是所有接收到广播信 息包当又不继续传送广播信息包的节点的集合显然，wnf = 中注意到w 中，否则就意昧着网络中存在分割设节点w 是w 中优先级最高的节点从条 件可以得到最少有一个w 的吸收节点u u ，并且根据自我剪枝算法对于它必定 没优先级高于w 的节点组成的代替路径于一个优先级高于节点w 的节点或是一个 被访问过的节点相连注意到任意一条代替路径必须经过一个节点w w 而且 w 的优先级必须高于w 这与假设矛盾 一个自我剪枝协议是静念的当它在使用覆盖条件时并不收集已被访问过的节点的 信息或者不使用这些信息否则这个自我剪枝协议是一个动态的协议在静态的 协议中，传送节点集是在广播之前预先决定的，也就是与本次传送中信息源节点 的位置无关例如，静态协议中图1 2 ( a ) 中的节点2 是一个传送节点，因为没有 一条代替路径连接它的邻接节点o 和3 ( 假设节点o 和节点2 有较节点1 和节点3 高的优先级) 当节点1 是发起广播的节点时，实际上会有3 个传输节点：节点 0 ，节点1 和节点2 6 ( b ) 在动态协议中，传送状态是在广播过程中决定的每一个节点通常在接收到广播 信息后一段很短的随机时间后才决定它的状态在随机延迟的时间内，更多的邻 接节点会传送统一条广播信息而成为被访问过的节点每一个广播的信息都携带 一个最近被访问的节点的列表所有的节点使用被访问过的节点的信息去增加被 剪枝的机会在动态剪枝协议中传输节点的数目通常小于静态协议，但是对传输 节点的选择通常与广播的信息源有关图卜2 ( b ) 展示了与图卜2 ( a ) 同一个网络 中同一个广播信息源的广播过程这次，节点2 是一个非传送节点集，这是因为 节点0 和节点3 都被节点1 支配，其中节点1 是一个被访问过的节点( 这个信息是 被广播信息捎带的) 这次整个网络中只有两个传播节点 在 1 6 中，广播中的局部视图中的一些信息( k 一跳信息和优先级信息) 被假设为是 静态且安全的但是在移动网络中这些静态的信息通常变化丽引起不一致的本地 视图使用这些不一致的本地视图，广播信息的完全覆盖( 也就是1 0 0 的传输 率) 通常不能达到一般情况下自我剪枝协议中的广播的冗余和传送率是受不同 的实现选项影响的，其中包括优先级类型，4 h e l l o ”信息周期的长短，节点收到 广播信息后的随机延长时间的长短使用静态的优先级( 如节点的i d ) 通常不如 使用动态的优先级( 如节点的度) 好，这是因为一个静态的优先级通常能在移动的 网络中取得较高的传送率和在密集的网络中取得较少的冗余 1 5 使用一个较小 的”h e l l o ”信息周期可以提供较新的k 一跳信息和提高动态网络中的传送率，但却 存在大量的“h e l l o ”信息把带宽饱和掉的危险在一些自我剪枝协议如s b a 4 ， 一个较大的随机延迟时间是取得高的传播效率的必要条件但一个大的随机延迟 时间也导致一个大的端到端延迟一个很小的随机延迟时间也被使用于防止冲突 但它通常不足够大以用于影响广播冗余和传送率 下面给出7 个现有的算法( 包括动态的算法和静态的算法) ，它们是w u 和l i 的 r uj el 和r u l e 2 f 静念) 7 ，d a i 和w u 的r u l e k 1 7 ，c h e n 等的s p a n ( 静态) 2 ， r i e c k 的算法( 静态) ，s u c e c 和m a r s i c 的l e n w b ( 动态) 6 ，p e n g 和l u 的s b a ( 动 态) 4 ，和s t o j m e n o v ic 的算法( 静态或动态) 1 8 w u 和l i 的算法( 静态) ：w u 和l i 提出一个决定网关( 也就是传送节点) 使之成为 一个连通的支配节点集：如果一个节点有两个邻接节点不是直接相连的它就被标 记为网关两个剪枝规则可以用于进一步减少连通支配节点集的大小根据剪枝 规则r u l e 一1 ，如果一个网关节点v 的所有邻接节点都是另外一个有较高优先级的 邻接节点的邻接节点，那么它可以成为一个非网关节点，即节点v 的邻接节点集 被节点u 所覆盖，所以u 也叫做覆盖点根据剪枝规则r u l e 一2 ，如果一个作了标 志的节点( 被标记为网关的点) 的所有的邻接节点被另外两个优先级高于该节点的 直接相连的节点覆盖，那么它可咀被除去标记 d a i 和w u 的算法( 静态) ：d a i 和w u 使用了一个叫做r u l e k 的更一般化的剪枝规 则扩展了上面的算法如果一个网关的邻接节点集被另外k 个优先级高于这个节 点连通的节点集覆盖，那么这个网关可以成为一个非网关r u l e i 和r u l e 一2 是 r u l e k 的特例d a i 和w u 同时提出了种受限的r u l e k ，而且当使用一中有效 的深度优先集算法时受限的r u l e k 的计算时间复杂度时o ( d 2 ) 。实验结果表明受 限的r u l e k 与不受限的r u l e k 在减少传送节点集上有同样的效率 c h e n 等的s p a n ( 静态) ：c h e n 等提出了一种构造一个协调者集( 传播节点集) 的方 法当一个节点u 的两个邻接节点既不是直接相连又不是间接由一个或两个中间 协调者相连那么这个节点就成为一个协调者在一个节点从一个非协调者成为一 个协调者时它等待一个延迟时间，这个延迟时间是由节点的电量，度数，和它的 直接相连的节点对的数目计算出来的这个延迟时间可以被看成是一个优先级数 值在这样的优先级下，更短的延迟时间使得节点有更大的机会成为一个协调者 s p a n 不能保证覆盖，这是因为两个协调者可能同时重新变为非协调者而使剩下 的协调者不能成为一个连通的支配节点集 r i e c k 的算法( 静态) ：r i e c k 等提出了一个连通的支配节点集算法，它可以看成 一个增强的s p a n 的特例在r i e c k 的算法中，个节点v 是属于连通支配节点集 的当它有两个邻接节点没有直接的连接或者通过一个优先级较高的节点相连与 s p a n 不同，两个相邻节点通过两个相互连接的较高优先级的节点相连的情况没 有考虑因此，得到的连通支配节点集大于由s p a n 所得到的另一方面，r i e c k 的算法要求2 一跳的信息和o ( d 2 ) 的计算复杂度 s u c e c 和m a r s i c 的l e n w b ( 动态) ：s u c e c 和m a r s i c 提出了一种轻量级的高效的全 网络的广播算法，它是在广播时才计算传送状态的当一个节点v 接收到一个从 邻接节点w 传送来的广播信息时，它计算可以由w 通过优先级高于v 的节点连接 到的节点的集合c 如果y 的邻接节点集n ( v ) 包含在c 中，节点v 将是一个非传 送节点，否则它是一个传送节点l e n w b 是一个动态的协议，每一个节点的状态 会在广播的过程中根据2 一跳节点的信息在o ( d 2 ) 的时间内重新计算 p e n g 和l u 的s b a ( 动态) ：p e n g 和l u 提出了可扩展的广播算法( s b a ) 来减少传送 节点数目象在l e n w b 一样，一个传送节点的状态是在广播的时候才计算的当 一个节点v 接收到一个广播信息包时，它并不马上把它传送出去，而是等待一段 较长的延迟时间对于任意曾经传送过广播的邻接节点w ，节点v 把n ( w ) 从n ( v ) 中删除掉如果n ( v ) 在延迟之后并不变成空集，节点v 就会成为一个传送节点， 否则节点v 是一个非传送节点如l e n w b ，s b a 使用2 一跳信息和o ( d 2 ) 的计算时间 s t o j m e n o v i c 的算法( 混合) ：s t o j m e n o v i c 从两个方面等扩展了w u 和l i 的算法： ( 1 ) 假设每一个节点知道它的准确的地理位置，只要卜跳信息就可以用来实现 r u l e l 和r u l e 一2 的标记过程也就是说，每一个节点只保留一个它的邻接节点 和它们的位置的信息，它们之间的连接就可以通过计算得出( 2 ) 使用与s b a 相 识的方法传送节点的数目进一步减少s t o j m e n o v i c 的算法是混合的在任何广 播之前，一个静态的算法( 标记过程和r u l e 一1 和r u l e 一2 ) 根据1 一跳位置信息以 0 ( d 3 ) 被使用在所有的在所有的节点上在每一个广播中，个动态的算法( s b a ) 被使用在这些节点上，使用卜跳的信息和o ( d 2 ) 的计算时间像静态算法一样把这 些节点临时地标记成传送节点 2 2 移动节点的管理 移动a dh o c 网络的可靠性被同时的信息传送的相互干扰所限制节点的移动使相 互干扰的问题更加复杂化很多的研究 1 9 ， 2 0 集中在移动网络的可靠性的问 题上c a m p 等 2 1 给出了一个移动a dh o c 网络中全面的研究三个普遍使用的 移动模型包括：( 1 ) 随机移动模型，是一个基于随机方向和随机速度的简单移动 模型，( 2 ) 随机路途点模型，包括在改变目标位置和速度时的停顿时间，( 3 ) 随 机方向模型，在节点移动到模拟区域的边界才改变节点的运动方向在 2 3 中给 出了一个有限速度模型( 对于在一个小的区域内佩戴移动节点的步行者) 和一个有 限加速度模型( 对于高速的车辆) 其它的移动模型在 2 2 中讨论到，它们对路由 协议的性能影响在 2 3 中作出了讨论 过去在移动环境中维持准确的邻接节点信息而不增加”h e l l o ”信息的频率的工作 比较少在 2 4 中，每个节点都根据节点的由g p s 得到的位置，速度，和方向定 义了稳定区域和警戒区域稳定区域是节点可以和邻接节点维持一个相对稳定的 连接的区域，因为在这个区域它们的位置比较近警戒区域是节点可能与邻接节 点维持一个不稳定的连接的区域，因为在这个区域它们的位置比远这个方法的 缺点是它需要g p s ，而g p s 带来其它的开销此外，缺少节点移动对在两种区域 的选择的有力的分析 在 2 5 中解决了使两个节点之间的连接保持有效的最近距离的时间断的问题几 个路由协议，如基于连接的路由( a b r ) 2 6 和基于信号稳定的适应性路由 ( s s a ) 2 7 ，被提出用于选择稳定的连接来构造一条路径在 2 8 中g p s 信息用 于估计两个相邻节点之间连接的无效时间最近有几个移动对路由路径的影响方 面的研究 2 3 但是，很少广播协议使用稳定连接的想法去估计邻接节点集的稳 定性以用于更好的决定每个节点的传播状态 1 4 和 2 9 通过衡量效率( 简单的 设计) 和覆盖效率( 传送效率) 提出了几个非确定的广播协议 在 3 0 中提出了使用两个邻接节点集的方法其中有效邻接节点集由在实际传送 半径r ：范围内的所有节点构成，广告邻接节点集只由距离小于一个较小的广告传 送半径r 。的节点构成如果v 是一个非传播节点集，v 的每一对有效的邻接节点 必须被条代替路径连接另一方面，只有广播的邻接节点集信息被传播到k 跳邻接节点这个方法是一个保守的方法由传输半径r 得出网络是连通的是充 分的如果两个邻接节点的物理距离可以通过接收到的信号的强弱来估计，双邻 接节点集可以通过发送传送半径为r ：的”h e l l o ”信息来实现每个节点把它的邻 接节点集根据它们的估计距离分成有效邻接节点集和广告邻接节点集当信号的 强弱是不可得到的或不准确是，每个节点发送两种”h e l l o ”信息第种用于发 现有效邻接节点的”h e l l o ”信息通过传送半径r 2 来发送第二种用于发现有广告 邻接节点的信息通过传送半径r ，来发送 第3 章本文提出的保证覆盖的广播方法 3 1使用准确计时的安全链路方法s l a t ( s e c u r el - n kw - t h a c c u r a t et i m i n g ) 在实际的物理网络当中，网络的物理拓扑结构可能在不断的变化网络的物理拓 扑结构不但会在”h e l l o ”消息的间隙时间内变化，还会在广播过程之中变化 为了简化起见，假设各个节点有不同的优先级，并定义每个节点的本地视图 ( 1 0 c a lv i e w ) 为它的k 一跳信息( k 一跳信息是它的邻居节点拓扑结构的一个近似) 在a n e t 使用本地自我剪枝算法时，通常是基于一些抽象的，即假设这个近似的 拓扑结构是物理拓扑结构机构的一个精确和及时的反映但是，在m a n e t 这个假 设可以由于节点不断地移动丽很容易地被破坏为了能够使用本地自我剪枝算法 本文使用一种和 3 0 同类的逻辑网络它是一个动态构造地虚拟地网络，它包括 本地视图，邻居节点的广播状态，广播过程中地本地视图它包括以下两层的抽 象： 第一层抽象：从物理网络到逻辑网络的抽象 第二层抽象：从逻辑网络到广播状态的抽象 一个逻辑网络是所有本地视图的集合，即一个以所有节点的本地视图为子图的父 图 定义l 本地视图，g 。( v ，t ) = ( n 。( v ，t ) ，e 。( v ，t ) ) ，是节点v 在时间t 时收集 的k 一跳网络拓扑结构信息逻辑网络，g ( t ) = ( v ，e ( t ) ) ，其中e ( t ) u ，。 e 。( v ，t ) ，是所有本地视图的集合 本地视图和逻辑网络都是随时间变化的在物理网络变化时，这些变化可从 ”h e l l o ”信息中获得并反映在逻辑网络中假设w ，u 和v 是三个点，他们分别有 不同地”h e l l o ”间隔f f 。和f ，即它们是异步地发”h e l l o ”信息的把每个节点 上一次发送”h e l l o ”信息发送的时间设为t 。，把在此之前地”h e 儿o ”信息发送的时 间设为t 。t ，。等等注意到t 。对于不同地节点可能对应到不同的物理时间假 设在这罩每个节点收集它的卜跳信息如果w 的”h e “o ”信息首先被被u 在t 一。 和t 。之间接收到，u 就发现链接( w ，u ) ，并把它作为0 一跳信息加到u 地本地视 图中，将它在h 时添加到”h e l l o ”信息发送出去当v 在t 。和t ，之间接收到u 地”h e o ”信息后，把链接( w ，u ) 作为卜跳信息加到v 地本地视图中 广播状态是由本地视图组成地逻辑网络地一个快照在一定地广播过程中，广播 状态形成一个虚拟的静态网络，用于运行本地自我剪枝算法 定义2 一个节点v 的本地状态g 。”( v ) = ( n k ( v ，t 。) ，医( v ，t ，) ) 是它在时间t 。时 地本地视图，其中t ，是节点决定它是否继续传播接收到的广播信息的时间个 全局状态，g ”= ( v ，e ”) 其中e ”= u 。e 。( v ，t 。) ，是所有本地状态的集合 假设节点w 发出个广播，并且节点u 和v 是这个信息所传送到的节点节点w 在开始发送广播信息之前在时间t 。和时间t 。之间取样它的本地状态当接收到 从节点w 传来的广播信息之后，节点u 和v 在一个随机的等待时间( b a c k o f fd e l a y ) 之后决定它们的传播状态假设节点u 决定它成为个传播节点( 它会把从w 接收 到的广播信息再次发送出去) 而节点v 决定它成为一个非传播节点然而，节点u 和v 都是在它们作是否成为个传播节点的决定的时候是在不同的物理时间对它 们的本地状态进行取样的全局状态就是在广播过程中所有节点的本地状态的集 合，因此它不一定与某一个物理时间上的所有节点的本地状态的集合一致 下面将会考察各个抽象层之间的”缺口”，这些”缺口”是由在不同抽象层之间的各 种同步延迟和协议握手所造成的在下面将会看到一些由那些”缺口”所造成的问 题和给出这些问题的解决方法 第一层抽象中的”缺口”：为了建立k 一跳信息，每一个节点从它的邻接节点的 ”h e l l o ”信息中接收( k 一1 ) 一跳的信息，然后根据接收到的”h e l l o ”信息更新本地视 图因为邻接节点是异步地发送周期的”h e l l o ”信息的，在某个时刻t 的卜跳邻 接节点集并不一定反映该时间真实的卜跳邻接节点集忽略节点间的信息传送 时1 1 日j ，这个时间差就是。= t 、一t 。其中t ，是本地视图被采样的时间，而t ，是 发送”h e l l o ”信息的时叭实际上，k 一跳信息都是由在不同时间采样的邻接节点 1 1 的信息所组成的总的来说，如果邻接节点u 的信息h 。( u ) 在h ，( u ) 到达并经过 时间断后j 被采样，那么在时间t 时的k 一跳信息并不能反映这个时间中真实 的k 一跳邻接节点的信息( k 一跳邻接节点的拓扑结构) ，而时l ；l j 差为。= 。 如果某条链接的两个节点的相对速度为。，那么这两个节点的采样距离和真是 距离的差距小于。= 。 第二层抽象中的”缺口”：在使用本地自我剪枝方法的广播过程中，每一个节点都 做以下三步的动作：( a ) 首先是接收广播信息，( b ) 延迟一段时间，和( c ) 决定继续 传播与否和进行传播( 如果需要传播) 一个广播周期开始于第一个发起广播的节 点发出广播信息，结束于最后一个节点决定它的继续传播与否( 传播状态) 如上 文所说，本文假设广播消息的传播速度很快，由它引起的延迟可以被忽略在广 播过程中的中间节点上可以有等待延迟( b a c k o f fd e l a y ) 累计的等待延迟时间 为，m “t ，其中t t 是广播信息在第i 个节点上的等待延迟时间这罩，如果广播 信息的传输延迟时间不能被忽略，t 也可以包括它 使用本地状态进行本地自我剪枝方法时通常需要以下的三个本地的条件的满足： 虚拟网络的联通，链接的有效，和本地视图的一致第一个和第二个条件分别解 决了第一层和第二层抽象的”缺口第三个条件保证本地试图的一致 虚拟网络的连通：对应与全局广播状态的虚拟网络应该是联通的以下的定理 给出使逻辑网络联通的节点密度的要求 定理l 如果物理链路( w ，u ) 存在并且节点w 和节点u 之间的距离总是小于d ( w ，u ) = r 一，其中r ，是节点u 的覆盖半径，= ，( 。，+ 。t ) ，、 是节点w 和节点u 的最大相对速度，。；，。是从节点u 到节点v 的最短路径上相 邻节点的”h e l l o ”信息周期的异步时间差，。，t 。是从节点v 到节点u 的广播信息 的累计的等待延迟时间，那么在节点v 的本地状态中逻辑链路( w ，u ) 总是存在 证明：假设一个取样于一个广播过程的全局广播状态的取样开始于时间t 因为 广播的延迟时间为t 。= ，。“t 。所有的本地状态都在时间 t ，t + t d 内被取样如 果两个节点w 和u 之间的距离在时间t 。= t 一。小于d = r 。一，那么节 点w 和u 之间的距离在时蚓 t ，t + td 内小于r ，即逻辑链路( w ，u ) 存在口 1 4 定理2 如果任意节点w ，u ，和v 都满足定理l ，即d ( w ，u ) r 。一，那么 每个有全局广播状态得出的虚拟网络都是联通的 证明：假设v 在时间t 对本地广播状态采样，那么它接收的链路信息( u ，v ) 是由 u 在时间。，“。发出的，因为所有的本地状态都在时间 t ，t + 。“t 。 内被取样 因此节点v 的本地广播状态中的逻辑链路( u ，v ) 是联通的由于全局广播状态是 由全部的本地广播状态组威的，并且网络中的所有链接的距离都小于一( 对 于任意节点w ) ，所以全局广播状态是联通的口 定理2 是一个保证物理网络联通的非常严格的条件这个条件不能满足，在逻辑 网络上运行的本地自我剪枝方法就有可能会失败，在后面将会给出以不保证剪枝 的j 下确性为代价的对这个联通条件的放松的方法 链接的有效：广播状态中的任意的链接在广播的过程中仍然存在本文提出使 用一个链接有效时间t 。如果一条链接的有效时间t 。o 表示该链接是有效的 对于节点v ，两个节点w ，u 之间的链接( w ，u ) 的有效时间0 ，则节点w 是节 点u 的有效支配点( d 。t i l n a n tn o d e ) ，节点u 是节点w 的有效吸收点( a b s 。r b e n t n o d e ) 定理3 为了满足链接的有效，必须满足t ，。o ，其中t 。= t “一。是 采样点的采样时间和采样点接收到链接信息的时间差，t ，。是采样点接收到链接 信息时链接的有效时间，t 。= 。，一( 。+ 。，。t 。) ，。= r ，一 、，、是链接的支配点与吸收点之间的距离( 由链接的吸收点在发现链接时测 量) ，是链接的支配点与吸收点之间的相对速度，。：。+ 。“t 的定义如 定理一 证明：因为广播的延迟时闻为t 。：，0 t 。所有的本地状态都在时间 t ，t + ta 内被取样如果t 。o ，r ，一。”= 。+ ( ：。+ ，m t t ) 。 t 。，+ ( 。、+ 。，t 。) = r 。一。，所以链接的支配点与吸收点之间的距 离r 。一、”r 一。，即链接有效口 以二的定理提供了一些保证安全链接的理论基础然而以上的分析考虑的是最坏 的情况，实际上最坏的情况是很少出现的本文在后面将会分析到，即使给出 个比链接的支配点与吸收点之间的相对速度。大得多的。，存在没被发现的 链路的可能也是相当小的这是因为使用大多数的本地自我剪枝算法后都存在 定程度的冗余，一个信息传递的失败通常要几个链路的失败才能造成