（通信与信息系统专业论文）大规模移动自组织网广播协议的设计与实现.pdf

摘要 摘要 移动a dh o c 网络( m a n e t , m o b i l ea dh o cn e t w o r k ) 是在基础设施或中央控制 实体缺失的环境下，由无线移动节点组成的具有移动和自治特征的动态自组织网 络系统，每一个节点同时扮演主机和路由器两种角色。以上特点使得m a n e t 非 常适合于在会议、学术交流、灾难救援和恢复、家庭网络和战场军事指挥等环境 使用。然而，m a n e t 中一些关键性技术至今尚不成熟，本文介绍了针对其中之一 广播技术中存在的广播风暴问题的一些解决方案。着重介绍了基于支配集理 论的广播算法，在其中的最小连通支配集近似算法( m c d s ，m i n i m u mc o n n e c t e d d o m i n a t i n gs e t ) 的基础上对其缺陷进行了改进提出了有限冗余重传的连通支配集 算法( c d s l r ，c o n n e c t e dd o m i n a t i n gs e t sw i t hl i m i t e dr e d u n d a n c y r e t r a n s m i s s i o n ) ，通过此算法可以在网络中自动形成一个稳定的虚拟骨干网，从而 可为网络中的广播和路由操作提供一个有效的通信基础。后面给出了c d s l r 的具 体实现，包括数据结构设计，程序设计，c d s l r 在软件仿真平台上的实现以及在 基于v x w o r k s 操作系统的a dh o e 网络节点上的实现。并对c d s l r 进行了广播性 能测试，验证了c d s l r 算法的正确性和相比泛洪( f l 0 0 1 3 n g ) 算法性能的提高， 并对结果给出了合理的分析。 关键字：移动a dh o e 网络广播风暴最小连通支配集有限冗余重传泛洪 a b s t r a c t 2 a b s t r a c t m a n e t s ( m o b i l ea dh o en e t w o r k s ) ，c o m p o s e do fi n d e p e n d e n ta n dm o b i l e w i r e l e s sn o d e s ，a r ed y n a m i cs e l f - o r g a n i z e ds y s t e mi nw h i c ht h ei n f r a s t r u c t u r ea n d c e n t r a lc o n t r o l l i n ge n t i t i e sa r ea b s e n t i nm a n e t s ，e a c hn o d ew o r k sb o t ha sah o s ta n d r o u t e r t h e s ec h a r a c t e r i s t i c sm a k em a n e t se s p e c i a l l ys u i t a b l ef o ru s ei nc o n f e r e n c e m e e t i n g ，d i s a s t e rr e l i e fa n dr e s c u e ，r o o fn e t w o r k sa n db a t t l e f i e l d s h o w e v e r , t h e r ea l e s t i l ls o m eo p e ni s s u e si nm a n e t s ，o n eo ft h e m - b r o a d c a s ts t o r mp r o b l e ma n di t st y p i c a l s o l u t i o n , w e r ed i s c u s s e d i nt h i s p a p e r m u c h a t t e n t i o nw a s p a i d o na n e i g h b o r - k n o w l e d g e - - b a s e db r o a d c a s t i n ga l g o r i t h m - m c d s ( m i n i m u m c o n n e c t e d d o m i n a t i n gs e t s ) a l g o r i t h m ，b a s e do i lt h ea l g o r i t h m ，a na d v a n c e da l g o r i t h mc d s l r ( c o n n e c t e dd o m i n a t i n gs e t sw i t hl i m i t e dr e d u n d a n c yr e t r a n s m i s s i o n ) i sp r o p o s e d w h i c hc o u l di m p r o v et h ed e f i c i e n c i e so f m c d s t h ea l g o r i t h mc a l lb eu t i l i z e dt of o r ma s t a b l ev i r t u a lb a c kb o n ei nan e t w o r ka u t o m a t i c a l l y i tp r o v i d e sa ne f f e c t i v e c o m m u n i c a t i o nf o u n d a t i o nf o rb r o a d c a s ta n dr o u t i n go p e r a t i o n si nm a n e t s t h e i m p l e m e n t a t i o no nc d s l rw a si n t r o d u c e d ，i n c l u d i n gd a t as t r u c t u r ed e s i g n , p r o g r a m d e s i g n ，t h ei m p l e m e n t a t i o no ns o f t w a r es i m u l a t i o np l a t f o r ma n da dh o cn e t w o r k p r o t o t y p en o d e sw h i c hw e r eb a s e do nv x w o r k so p e r a t i o ns y s t e m f i n a l l y , t h et e s t i n g r e s u l t so f b r o a d c a s t i n gp e r f o r m a n c eo fc d s l r w a sp r e s e n t e da n dc o m p a r e dt ot h e mo f f l o o d i n g ，a n dt h e nt h er e a s o n a b l ea n a l y s i so ft h er e s u l t sw a sg i v e n k e y w o r d ：m a n e t s b r o a d c a s ts t o r mp r o b l e mc d s l r f l o o d i n g 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人 在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究 成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的 说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：2 壁皇缝日期塑2 ：i ：5 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：坐皇! 垒 别磁辄谛 日期趟：主笸 日期剑：! ! 笸 第一章绪论 第一章绪论 i 1a dh o c 网络 随着社会的进步，人们对灵活、快捷、方便的通信方式要求越来越高，而全 球化进程的加快又进一步刺激了通信与网络技术的发展，人们不断追求任何人可 以在任何时间、任何地点与任何人进行任何种类的信息交换。个人业务需求无论 是在支持范围上还是种类、质量要求上都大大的增加，极大地刺激了无线通信网 络的迅速发展。移动a dh o c 网络( m a n e t ，m o b i l ea dh o en e t w o r k ，即无基础设 施移动无线网络) 技术作为无线通信领域一种新的网络技术，正在很快地从军事 通信渗透到相关的各个民用通信领域。这种自组织对等式多跳移动通信网络，不 需要依赖于固定的基础结构，既可以与现有的网络结合形成多跳网络，从而有效 延伸传统网络的覆盖范围，同时也可以通过临时组网的方式在恶劣环境中支持移 动节点之间的数据、话音、图像和图形等业务的无线传输。这也使得a dh o e 网络 具有极大的灵活性和可扩展性，可以满足不同场合的特殊需要，其应用范围可以 覆盖工业、商业、医疗、家庭、办公环境、军事等各种场合和行业。特别是在军 事应用领域中，因其特有的无需架设网络设施、可快速展开、抗毁性强等特点， a dh o c 网络已成为数字化战场通信的首选技术。 1 1 i a dh o e 网络的特点 无中心和自组织性。a dh o c 网络中没有绝对的控制中心，所有节点的地位平 等，网络中的节点通过分布式算法来协调彼此的行为，无需人工干预和任何其它 预置的网络设施，可以在任何时刻任何地方快速展开并自动组网。由于网络的分 布式特征、节点的冗余性和不存在单点故障点，使得网络的健壮性和抗毁性很好。 动态变化的网络拓扑。a dh o e 网络中，移动终端能够以任意速度和任意方式 在网中移动，并可以随时关闭电台，加上无线发送装置的天线类型多种多样、发 送功率的变化、无线信道间的互相干扰；地形和天气等综合因素的影响，移动终端 间通过无线信道形成的网络拓扑随时可能发生变化，而且变化的方式和速度都难 以预测。 多跳路由。由于节点发射功率的限制，节点的覆盖范围有限。当它要与其覆 盖范围之外的节点进行通信时，需要中间节点的转发，即要过多跳。此外，a dh o e 网络中的多跳路由是由普通节点协作完成的，而不是由专用的路由设备( 如路由器) 完成的。反过来，如果可以使用多跳路由，节点的发射功率可以很低，从而达到 节省电能延长电池工作时间的目的。 无线信道传输。a dh o c 网络采用无线传输技术作为底层通信手段，由于无线 信道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多，并且无线 2大规模移动自组织州广播协议的设计与实现 信道的质量较差。考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道 之间干扰等多种因素，移动终端得到的实际带宽远远小于理论上的最大带宽，并 且会随时间动态变化。传统的共享广播式信道是一跳共享的，而在a dh o c 网络中， 广播信道是多跳共享的。一个节点的发送，只有其一跳相邻节点可以听到，而此 范围之外的其他节点觉察不到。此外，地形或发射功率等因素影响使得a dh o c 网 络中可能产生单向无线信道。 移动终端的局限性。a dh o c 网络中，移动终端具有携带方便、轻便灵巧等好 处。但是也存在固有缺陷，例如能源受限、内存较小、c p u 性能较低等，从而给 应用程序设计开发带来一定的难度，同时屏幕等外设较小，不利于开展功能较复 杂的业务。 安全性较差。a dh o c 网络是一种特殊的无线移动网络，由于采用无线信道、 有限电源、分布式控制等技术，它更加容易受到被动窃听、主动入侵、拒绝服务、 剥夺“睡眠 等网络攻击。信道加密、抗干扰、用户认证、密钥管理、访问控制 和其它安全措施都需要特别考虑。 1 1 2 a dh o c 网络的体系结构 a dh o c 网络的节点不仅要具备普通移动终端的功能，还要具有报文转发能力， 即要具备路由器的功能。因此，就完成的功能而言可以将节点分为主机、路由器 和电台三部分。其中主机部分完成普通移动终端的功能，包括人机接口、数据处 理等应用软件。而路由器部分主要负责维护网络的拓扑结构和路由信息，完成报 文的转发功能。电台部分为信息传输提供无线信道支持。 路由器 主机 路由器 主机 崔 a 单主机单电台b 单主机多电台 c 多主机多电台 图1 1 ：a dh o c 网络节点的结构 从物理结构上分，节点可以如图1 1 所示，分为以下几类：单主机单电台、单 主机多电台、多主机单电台和多主机多电台。一般的a d h o c 网络中的节点，如p d a 、 笔记本、无线传感器节点等大都采用图1 1 a 的单主机单电台的简单结构。作为复 杂的车载台，一个节点可能包括通信车内的多个主机，它可以采用图1 1 c 的结构， 以实现多个主机共享一个或多个电台。多电台不仅可以用来构建叠j i l ( o v e r l a y ) 的网 络，还可用作网关节点来互联多个a dh o c 网络。 第一章绪论 门鲁 笋ahocn 咄、啊、夕 g 一- 一 丘一二遍 a dh o cp q 络- - 般有两种结构：平面结构( 图1 2 ) 和分级结构( 图1 3 和图1 4 ) 。 在平面结构中，所有节点的地位平等，所以又可以称为对等式结构。而分级结构 中，网络被划分为簇( c l u s t e r ) 。每个簇由一个簇头( c l u s t e rh e a d e r ) 和多个簇成员 图1 3 单频分级 簇头簇成员 高频 低频 图1 4 多频分级 这些簇头形成了高一级的网络。在高一级网络中，又可以分簇，再次形成更 高一级的网络，直至最高级。在分级结构中，簇头节点负责簇间数据的转发，它 可以预先指定，也可以由节点使用算法选举产生。 1 1 3 m a n e t 网络主要技术难点 虽然对a dh o c 网络的研究已经开展多年，但所取得的科研成果并不足以使a d h o c 网络进入真正的商用阶段，要适应m a n e t 特点，对m a n e t 进行现实而成熟 的应用至少需要解决如下问题【2 8 】： ( 1 ) m a n e t 网络路由技术需要高效可靠的网络广播技术的支持。现有的面向 m a n e t 的路由技术仍然不成熟；众所周知的d s r ( d y n a m i cs o u r c er o u t i n g ) l l j 4 大规模移动自组织网广播协议的设计与实现 路由算法仍然未能成为正式r f c 标准；o l s r v 2 t 2 】作为对o l s r ( m t fr f c 3 6 2 6 ) 【3 】路由协议的优化也处于草案评审阶段。简单说有以下两个方面： 路由发现和维护。没有基础设施的支持，获得网络全局拓扑结构对于移动终 端来说是非常严重的负担，加之节点移动性对传统的路由算法提出挑战，使得有 线网络路由算法很难应用于a dh o c 网络。网络中每一个节点都有责任参与路由发 现和维护，由于需要在节点间交换路由信息，故从性能的角度来说，为了降低所 需的通信开销，需要有效减少参与路由计算的节点数目以及缩短路由表长度。 广播技术。影响m a n e t 路由性能的重要因素之一即简单、高效且可行的网 络广播算法 4 1 。不论是基于先应式的d s d v 路由算法【5 1 、o l s r 路由算法，还是基 于反应式( r e a c t i v e ) 的d s r 、a o d v 6 1 ，均需要采用广播进行路由选择并在节点 间更新过期的路由信息。广播技术也是进行网络节点时间同步和移动节点间组播 最常用的选择。直接的简单泛洪广播导致 扎冗余的分组转发 b 邻近节点信道争用 c 转发信号冲突等严重问题 即所谓广播风暴( b r o a d c a s ts t o r mp r o b l e m ) 【7 】，简单而高效的广播策略将直接 影响到m a n e t 通讯协议栈的性能。 ( 2 ) 动态的网络拓扑结构对网络管理技术提出了更高的要求。移动a dh o e 网络 不对节点移动行为作任何限制和假设，节点可以在特定区域内自由移动，从而使 得整个网络的拓扑结构处于不断变化的状态中，这无疑极大增加了移动a dh o e 网 络设计的难度。这要求m a n e t 协议对网络拓扑具有良好的适应性，在同样的网 络性能保证下，m a n e t 协议不至于对网络拓扑结构变化产生过强反应。另一方面， 网络规模随着移动终端加入、离开网络而动态变化。在网络规模较大时，控制开 销不应由此产生不可控的增长趋势。 ( 3 ) m a n e t 范围内的资源发现技术以及国内成为研究界关注的新的热点问 题。m a n e t 的作用在于能够在中央控制单元缺失的条件下快速部署，参与节点彼 此能够在连通的基础上进行动态协作。典型的应用包括即兴的文件共享【8 】，移动服 务发现策略【9 】等。尽管工业界和各种研究机构提出的若干分布式环境下资源发现协 议，如m t f 的s e r v i c el o c a t i o i lp r o t o c o l ( s l p ) 、s u n 公司的j i n i 、微软的u n i v e r s a l p l u ga n dp l a y ( u p n p ) 、m m 的s a l u t a t i o n 以及基于蓝牙技术的s e r v i c ed i s c o v e r y p r o t o c o l ( s d p ) 等，但除了s d p 以外，均需要依托传统的基础设施支持，故并不 适合应用于m a n e t 网络。为此，s u n 公司、美国北卡罗来纳大学、俄勒冈大学、 德国多特蒙德大学等研究机构纷纷投入相关方向的研究。并试图从对等计算( p 2 p ， p e e r - t o p e e rc o m p u t i n g ) 的角度解决这一问题。作为一个新的研究课题，移动a dh o e 网络资源发现研究已经引起研究界越来越多关注，相关知名国际学术会议包括 第一章绪论 a c m 支持的m o b i h o c 和m o b i c o m ，i e e e 支持的i n f o c o m 、g l o b e c o m 、m i l c o m 以 及p e r c o m 等，针对这一问题的研究主要集中在体系结构和平台( a r c h i t e c t u r ea n d p l a t f o r m s ) 、资源定位( r e s o u r c el o c a t i o n g ) 、节点访问和控制( n o d ea c c e s sa n d c o n t r 0 1 ) 、消息系统( m e s s a g i n gs y s t e m ) 等方面。 1 2 本文主要研究目的和内容 本文的主要研究目的是对a dh o e 网络中的广播问题进行研究，并设计一种可 靠，高效可行的a dh o e 广播算法，在西安电子科技大学宽带无线通信实验室所研 制的a dh o e 节点【l o 】上实现。文章主要以下几个部分： 第一章首先介绍了a dh o e 网络的特性和主要的研究热点。 第二章介绍了m a n e t 网络中的广播风暴问题，并介绍了一些典型的解决方 法。 第三章主要介绍了最小连通支配集( m c d s ) i n 】广播算法，在其基础上对其缺 陷进行了改进，提出了有限冗余重传的连通支配集算法( c d s l r ) 。 对于判断广播性能的主要指标数据分组的到达率和时延还没有相关文献 进行仿真和测试，第四章中对c d s l r 算法的实用性和在这两个指标上的性能进行 了仿真，并与一般的泛洪广播算法进行了比较。 第五章介绍了c d s l r 算法在a dh o e 硬件点上的实现，并对性能做了测试和 通过排队网络模型对性能及测试结果进行了分析。 第一二章m a n e t 网络中的广播风暴 7 第二章m a n e t 网络中的广播风暴 2 1 广播风暴问题概述 在m a n e t 网络中，由于主机的移动性，广播的使用要比有限网络更加频繁， 例如许多按需路由协议( a o d v ，d s r ，z r p t 坨】等) 都是通过广播来查找路由的， 而且一些禁忌消息的发送也是通过广播告知网络中所有的节点( 例如某些告警信 号) 。此外，在拓扑变化极为频繁的情况下，广播还应用于提供网络中多播业务的 最后手段。 广播一般方式是泛洪，也就是当一个主机接收到邻居节点发送过来的分组后， 将该分组转发给它周围所有的邻居。但是盲目的泛洪会导致严重的广播信息冗余， 信道争抢和广播信号碰撞。首先，由于无线传播是全方向的，有些地理位置同时 被多个主机的传输范围所覆盖，这就使得位于该位置的某些节点受到多个内容完 全相同的广播数据帧，从而产生了冗余。第二，由于转发广播信息的主机可能距 离很近，存在严重的信道争抢。第三，由于转发广播信息的时间选择是高度相关 的，所以极易产生信道碰撞。 总的来说，我们把以上这些与泛洪有关的问题叫做广播风暴问题。一般来说， 解决这个问题有两个办法：空间上，在保证覆盖范围的前提下，尽可能减少冗余 转发的可能性；实践是，尽可能使转发广播信息的时间分散，而不是集中在同一 时间段内造成信道争抢。 2 2 有关广播的基本假设 广播是自发的。在本文中，我们研究所有a dh o c 节点共享单一的物理信道， 并且使用载波侦听( c s m a c a ，c a r r i e r s e n s e m u l t i p l e a c c e s s ) ( 不具有冲突检测) 的媒体接入控制( m a c ，m e d i a a c c e s sc o n t r 0 1 ) 协议。由于每个节点随意的加入 和离开，所以它们之间的同步非常困难：此外，由于每个节点是分布式存在的， 每个节点是分布式存在的，每个节点只保留其邻居信息或者某条特殊路由的信息， 对有全网的网络拓扑并没有明确的认识，所以广播信息是自发的，并没有某种调 度机制来分配其发送时隙。 广播是不可靠的。由于在现有的m a c 层协议中，对于广播信息是不发送a c k 确认帧的，因为发送确认消息可能会导致严重的信道争抢，这就造成了某些广播 信息的丢失。此为，主机可能因为离线，临时与网络失去连通或者是遭遇重复的 碰撞而失去广播消息。而且，对于某些应用而言，绝对的传输可靠性也是没有必 要的。 大规模移动自组织网广播协议的设计与实现 请求发送清除发送( r t s c t s ) 对话机制不适用。由于广播转发的时间选择 是高度相关的，所以很容易产生信号碰撞，所以r t s c t s 并不适用。 主机能够发现重复的广播信息。这对于阻止无止境的泛洪是至关重要的，一 种方法是在广播信息中夹带一些发送属性信息( 例如源d ，发送序列号等) 来唯 一标识每一次的广播。 2 3 广播风暴的解决方案 2 3 1 减少信号争抢和碰撞的方法 减少信道争抢和碰撞的方法，一般是在转发消息前加上一个小的随机延时， 这样就可以使得转发在时间上更加分散，我们一般采用随机接入延迟来解决信道 的争抢和碰撞问题。 随机接入延时( r a d ，r a n d o ma s s e s s m e n td e l a y ) ：在广播过程中，许多广播 协议需要每一个节点记录在一段时间间隔内收到的冗余分组数，以决定是否转发 该分组。这个时间间隔，我们称之为“随机接入延迟 。它是从一个0 到t m a x 均 匀分布的时间间隔中随机选出来，其中t m a x 为最长可能延迟间隔。 在转发中引人延迟有两个作用。首先，它允许节点有足够的时间来接受冗余 分组，从而判决是否转发该分组。第二，延迟使得分组的转发随机化，在一定程 度上避免了转发数据的碰撞概率。 2 3 2 减少信息冗余的方法 在泛洪算法中，所有节点都参与广播。因为节点广播的覆盖范围可能重叠， 所以可以在确保所有节点收到广播的前提下，只选择其中一些节点重播，通过减 少重播次数来减轻广播风暴问题。 据此，先后有人提出了一些算法：基于概率( p r o b a b i l i s t i c - b a s e d ) ，基于计数 ( c o u n t e r - b a s e d ) ，基于距离( d i s t a n c e - b a s e d ) ，基于位置( 1 0 c a t i o n b a s e d ) 和基于 相邻节点信息算法( n e i g h b o r - k n o w l e d g e - b a s e d ) 。这些算法都是通过减少重播次数 来减轻广播风暴问题，区别在于节点收集信息、估计冗余、决定重播的方式。 基于概率算法【7 】 通过限制a dh o e 网络中部分节点重播来减轻广播风暴问题，很自然会想到， 可以让节点以某种概率来进行重播。这是一种简单直接的减少重播冗余的方法， 称之为基于概率算法。 基于计数算法【7 】 当节点决定重播时，由于一些原因( 如信道已经被占用，b a c k o f f 过程，或者 已经有多条广播等待发送) ，或者认为的插入r a d ，广播消息并不会马上被发送出 去。在消息真正被发送前这段时间，节点可能会因为相邻节点的重播多次受到重 第二二章m a n e t 网络中的广播风暴 9 复消息。由于重播能覆盖的新区域会随着受到重复消息次数的增加而减少，而当 重播能覆盖的新区域小到一定程度，节点重播已经没有意义。所以，可以设置计 数门限c ，如果节点受到重复消息的次数大于c ，则禁止重播，这种算法称为基于 计数算法。 基于距离算法【7 】 基于计数算法根据收到重复消息的次数估计重播覆盖新区与的大小来决定是 否重播。也可以更具节点间的距离估算重播覆盖新区域的大小来决定是重播，这 种算法被称为基于距离算法。 基于位置算法【7 】 前面分别用收到重复消息的次数和节点间的距离决定