（计算机科学与技术专业论文）基于ns2的多信道路由仿真模型的研究与实现.pdf

、7 一 、 盖羔恙o i y l 7 i l l l l l f l l f l 5 i l l f 1 7 f l l i l 6 ”1 1 i i 。i l l l 8 i l l l 独创性( 或创新性) 声明 。 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：j 瓷垂虹本人签名：j 荽垂茎l 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：坐! ! ! 至：艺 嗍：出牛 卜l ，一 一 j ， 气 f 北京i i i i j i 也人学倾i ：研究生学位论义 基于n s 2 的多信道路由仿真模型的研究与实现 摘要 随着近年来无线网络的迅速发展，无线网络中存在的瓶颈问题也 不断的暴露，例如网络容量受限，频谱资源受限等等。多信道技术的 提出，为解决无线网络中的瓶颈问题奠定了基础，但是，已有的单信 道协议并不能充分利用多信道所带来的优势，在这样的背景下，多信 道协议的研究已经变得越来越重要了，而一直以来得到网络技术研究 者青睐的网络仿真工具，也开始面临着支持多信道协议仿真的挑战。 n s 2 作为网络仿真工具中广泛被使用和认可的重要一员，若能支持多 信道协议仿真，势必可以更好的促进多信道协议的研究发展。本文基 于上述实际需求，以实现多信道路由仿真模型为最终目的，对路由协 议和n s 2 多信道仿真相关内容进行了研究。 本文首先以路由协议分类的方式，介绍了各类中典型的路由协议 思想；接着介绍了n s 2 仿真的基本原理和移动节点模型；然后研究 了已有的基于n s 2 的多信道仿真扩展工作，从扩展意图、实现方法 以及移动节点结构等方面进行了分析，并总结了各自在多信道路由仿 真时的优缺点。 接下来从分析多信道仿真特性的角度出发，分析并总结了单信道 路由协议在多信道环境下存在的问题，解释了为什么需要研究多信道 路由协议；同时结合多信道仿真特性，分析并总结了多信道路由协议 以及多信道路由协议存在的问题，并在此基础上提出了n s 2 多信道 路由通用仿真模型。最后本文详细论述了通用模型的仿真功能需求、 结构设计和详细实现，通过仿真对通用模型多接口多信道仿真功能进 行了验证，仿真结果表明多信道路由通用仿真模型成功支持各类多信 道路由协议对多接口多信道的仿真需求，从而有力的增强了n s 2 对 多信道路由仿真的支持力度，为多信道路由协议的研究奠定了一定的 基础。 关键字：网络仿真n s 2 路由协议多接口多信道仿真 | 一 ， k l _ 北京i j | i ；i 【1 人学顾l j j 究生学位论义 r e s e a r c ha n di m p l e m e n t a t i o n0 f m u i j i c h a n n e i 。r o u t i n gs i m i a t l 0 n m o d e l0 nn s 2 a b s t r a c t r e c e n t l y , w i t ht h ed e v e l o p m e n to fw i r e l e s sn e t w o r k s ，t h eb o t t l e n e c k p r o b l e m si n w i r e l e s sn e t w o r kh a v ec o n t i n u e dt oe x p o s e ，s u c ha st h e l i m i t e dn e t w o r kc a p a c i t y , t h ec o n s t r a i n e ds p e c t r u mr e s o u r c ea n ds oo n a l t h o u g hm u l t i c h a n n e lt e c h n o l o g yh a sb e e np r o p o s e df o rs o l v i n gt h e b o t t l e n e c kp r o b l e mi nw i r e l e s sn e t w o r k s t h ee x i s t i n g s i n g l ec h a n n e l p r o t o c o l sd o n tt a k ef u l la d v a n t a g eo ft h eb e n e f i t so fm u l t i c h a n n e l i n t h i sc o n t e x t ，t h er e s e a r c ho fm u l t i c h a n n e l p r o t o c o l h a sb e c o m e i n c r e a s i n g l yi m p o r t a n t ，m e a n w h il e ，t h en e t w o r ks i m u l a t i o nt o o l st h a ta r e t h ep r e f e r r e db yt h en e t w o r k i n gt e c h n o l o g yr e s e a r c h e r sh a v eb e g u nt o f a c et h ec h a l l e n g e so fs i m u l a t i o no fm u l t i c h a n n e lp r o t o c 0 1 n s 2a st h e w i d e l yu s e ds i m u l a t i o nt o o l ，i fi tc a np r o v i d em u l t i c h a n n e lp r o t o c o l s i m u l a t i o nf u n c t i o n ，i sb o u n dt ob eb e t t e rp r o m o t i o no fm u l t i c h a n n e l r e s e a r c h b a s e do nt h ea c t u a ld e m o n dt oa c h i e v em u l t i c h a n n e lg e n e r a l s i m u l a t i o nm o d e lo fr o u t i n g p r o t o c o l s f o rt h eu i l t i m a t e p u r p o s e ， m u l t i c h a n n e l r o u t i n gp r o t o c o l s a n dn s 2m u t i l c h a n n e ls i m u l a t i o n e x t e n t i o nw e r es t u d i e di nt h i sp a p e r f i r s to fa l l ，t h i sp a p e rd i s c u s s e st h et y p i c a lr o u t i n gp r o t o c o l sa n d t h e i rc l a s s i f i c a t i o n s ，a sw e l la s p r e s e n t e st h eb a s i cp r i n c i p l e so fn s 2 s i m u l a t i o n ，a n a l y s i s o fi t sw i r e l e s sn e t w o r ks i m u l a t i o nm o d e lo ft h e m o b i l e n o d e ，a n dt h e ns t u d yt h ee x i s t i n gw o r kr e l a t e dt h em u l t i c h a n n e l s i m u l a t i o nf r o mt h ee x p a n s i o no ft h ep u r p o s e s ，t h ee x p a n s i o no ft h e m e t h o d sa n dt h es t r u c t u r eo fm o b i l e n o d e ，a l s o s u m m a r i z e st h e i r d i s a d v a n t a g e so fm u l i t c h a n n e lr o u t i n gs i m u l a t i o n n e x t ，t h i sp a p e ra n a l y s e s t h ec h a r a c t e r i s t i c so fm u l t i c h a n n e l s i m u l a t i o na n ds u m m a r i z e st h ep r o b l e m so fs i n g l ec h a n n e l r o u t i n g p r o t o c o li nam u l t i c h a n n e le n v i r o n m e n t ，t h e nc o m b i n i n gw i t hm u l t i p l e c h a n n e ls i m u l a t i o nf e a t u r e s ，a n a l y s i sa n ds u m m a r yo fm u l t i p l ec h a n n e l 一一 北京邮i u 人学颁l j 研究生学位论文 一= 一 r o u t i n gp r o t o c o la n dp r o b l e m so fm u l t i c h a n n e lr o u t i n gp r o t o c 0 1 b a s e d o nt h e s ew o r k ，am u l t i - c h a n n e lr o u t i n gg e n e r i cs i m u l a t i o nm o d e l si s p u t f o r w o r d 1 一 f i n a l l y , t h i sp a p e rd i s c u s s e st h eg e n e t i cm o d e ls i m u l a t i o nf u n c t i o n a l r e q u i r e m e n t s ，t h es t r u c t u r ed e s i g na n di m p l e m e n t a t i o no ft h eg e n e r i c m o d e li nd e t a i l t h r o u g ht h en e t w o r kt h r o u g h p u tt ov a l i d a t et h eg e n e t i c m o d e l ，t h er e s u l ta p p r o v e st h a tt h eg e n e r i cm o d e lh a si m p l e m e n t e dt h e r e q m r e m e n to fv a r i o u st y p e so fr o u t i n gp r o t o c o lm u l t i i n t e r f a c ea n d m u l t i c h a n n e ls i m u l a t i o n ，w h i c hw i l l e f f e c t i v e l yb o o s tt h ec a p a c i t yo f n s 2m u l t i c h a n n e lr o u t i n gs i m u l a t i o n k e yw o r d s ：n e t w o r k s i m u l a t i o n ，n s 2 ，r o u t i n gp r o t o c o l ，m u l t i i n t e r f a c e m u l t i c h a n n e ls i m u l a t i o n l v ， - k i 北京邮i u 人学硕i 1 i j d l 生学化论- 文 目录 第一章绪论l 1 1研究背景l 1 1 1多信道传输技术l 1 1 2多信道路由协议2 1 1 3网络协议仿真3 1 2 研究需求和主要任务4 1 3论文章节安排。5 第二章路由协议及n s 2 多信道仿真现状6 2 1路由协议6 2 1 1基于逻辑视图的分类7 2 1 2基于路由发现策略的分类7 2 2n s 2 无线仿真基础1 0 2 2 1n s 2 基本原理1 0 2 。2 2 n s 2 移动节点模型1 2 2 3n s 2 多信道仿真研究现状1 3 2 3 1 h y a c i n t h 1 4 2 ：；2r a m o n 15 2 3 3 m m s m 1 6 2 3 4研究现状小结17 第三章多信道路由协议仿真分析1 8 3 1多信道仿真特性分析1 8 3 1 1 每节点网络接口数1 8 3 1 2每网络接口信道数1 9 3 2多信道路由仿真需求2 0 3 3 多信道路由协议分析2 2 3 3 1 单接口多信道路由协议2 2 3 3 2多接口多信道路由协议2 3 3 3 3 多信道路由协议问题分析2 5 3 4 多信道路由通用仿真模型分析2 6 第四章多信道路由通用仿真模型设计与实现2 7 4 1通用模型功能需求分析2 7 v v i 北京邮电大学硕f ：研究生学位论文 1 1 研究背景 第一章绪论 随着无线网络和移动通信的迅速发展，无线通信网络从w l a n 到w m n 、 从w s n 到m a n e t ，从g s m 到3 g ，从3 g 到4 g ( l t e ，l o n g t e r me v o l u t i o n ) 不断演进和升级，而无线多信道传输技术正是这一演进和升级过程中的标志性 产物。而伴随着多信道传输技术的诞生，配套的网络协议的研究也成为了无线 领域的热点问题，这些协议包括了网络层和m a c 层，分别称为多信道的路由 和多信道的m a c 。而网络仿真工具作为协议研究的一个重要手段，一直受到研 究者的青睐，它的不断演进和扩展势必能为多信道协议的研究提供一个很好的 平台，同时也能促进两者的共同发展。 1 1 1 多信道传输技术 为什么需要多信道传输技术，带着这个问题，先了解一下单信道传输技术 和它的缺陷。单信道传输技术是使用单一信道进行通信的技术，即所有节点只 能通过一条物理信道进行通信。这样的实现信道控制机制虽然简单，但是极大 的限制了网络的带宽和系统的吞吐量，无法满足迅速发展的无线网络对带宽的 需求，而且也存在隐藏终端和暴露终端的信道冲突问题。正是由于单信道传 输技术根本无法满足无线网络发展的需求，所以，需要一种新的技术来改善单 信道传输技术的不足，在这样的背景下多信道传输技术诞生了。 什么是多信道传输技术，多信道传输技术是指无线网络中每个节点在一定 时问范围内同时使用多个信道进行通信的传输技术。这里信道从是否与传输介 质相关，可以分为物理信道和逻辑信道。物理信道是指用来传送0 ，1 数据的具 体传输介质，网络中两个节点的物理信道就是由传输介质及有关设备组成的。 逻辑信道是建立在物理信道的基础上的，由节点之问或者节点内部通过一定的 策略建立起来的虚拟通路，也就是说在源点和目的点之间并没有一条物理的传 输介质。而多信道传输技术正是创建并实现多个物理或逻辑信道的通信技术， 多信道的协议就是一种策略，来有效的使用和管理这些信道集合，从而极大的 提高系统吞吐量和网络带宽。 多信道传输技术中，比较重要的多路访问技术主要包括f d m a ( f r e q u e n c y d i v i s i o nm u l t i p l e a c c e s s ，频分多址接入) ，t d m a ( t i m ed i v i s i o nm u l t i p l e a c c e s s ， 北京邮t u 人学硕l ：研究生学位论文 时分多址接入) ，c d m a ( c o d ed i v i s i o nm u l t i p l e a c c e s s ，码分多址接入) ，s d m a ( s p a c ed i v i s i o nm u l t i p l ea c c e s s ，空分多址接入) ，m i m o ( m u l t i p l e i n p u t m u l t i p l e o u t p u t ，多输入多输出) 等。这些多路访问技术基本上都是对网络中的 某种传输资源，如时间、空问、频率和编码进行划分，从而实现多个信道的彼 此隔离。 1 1 2 多信道路由协议 多信道传输技术虽然已经为迅速发展的无线网络构建适合自身的多信道通 信奠定了基础，从而具备了进一步提升网络吞吐量和网络带宽的潜力，但是要 更好的发挥多信道通信的优势，还需要有与多信道传输技术和网络相配套的多 信道协议，这也是我们研究多信道协议的出发点。而路由协议作为无线网络通 信的基础，不但可以采用最可靠的方式建立起通信链路，而且可以减少信息的 冗余提高网络的吞吐量，从而成为在无线网络迅速发展的背景下重点关注的问 题。 路由协议1 的重要功能是路由选择和中继，位于o s i 七层协议栈参考模型 的网络层，如图1 1 所示。网络层提供的是点到点的服务，它需要在多跳无线 网络中的两点间建立通信链路，而这个过程正是由网络协议来完成的。多信道 环境的网络中相邻节点之间存在多条通信路径，而传统的单信道路由协议采用 的路由策略大都是基于最小跳数的路由策略，并没有考虑多个信道之间的信道 切换开销和信道之间的传输干扰问题，所以这样的路由策略建立的路由在多信 道环境下并不一定是最优的路由。 要更好的解决上述传统单信道路由协议在多信道环境下的问题，必须研究 新的路由协议以适应多信道环境下存在多个信道的特点，并且充分利用多个信 道的优势，更好的提高网络的吞吐量和网络带宽。目前已有的多信道路由协议 主要有，多信道目的节点序列距离矢量路由协议( d e s t i n a t i o ns e q u e n c e dd i s t a n c e v e c t o rf o rm u l t i c h a n n e l ，d s d v - m c ) 1 2 j ，它是基于表驱动的主动路由协议d s d v 的多信道扩展协议；多信道a dh o c 按需距离矢量路协议( a dh o co n d e m a n d d i s t a n c ev e c t o rf o rm u l t i c h a n n e l ，a o d v - m c ) 1 3 】，它是基于需求驱动的被动路 由协议a o d v 的多信道扩展：m r l q s r ( m u l t i r a d i ol i n k q u a l i t ys o u r c e r o u t i n g ) p j ，l q s r 是d s r 协议的改进版本，考虑了链路质量因素，m r l q s r 在l q s r 协议的基础上，提出了一种全新的路由度量策略( w e i g h t e dc u m u l a t i v e e x p e c t e d t r a n s m i s s i o nt i m e ，w c e t i ) 。 注：本文的路由协议，除特别说明都默认为无线白组织m 络中的路由协议，并不涉及有线嘲络路由协议。 2 网络仿真是进行网络协议研究的一种重要手段，而所谓的网络协议仿真就 是在计算机上通过网络仿真软件搭建一个虚拟的网络环境，来研究网络协议的 一种方法。 目前使用比较多的专用网络仿真工具有，n s 2 、g l o m o s i m 和m a t l a b 等。 n s ( n e t w o r ks i m u l a t o r ) 是由d a r p a ( 美国国防部高级研究计划局) 主导的， x e r o xp a r c ( 施乐p a l o a l t o 研究中心) 、l b l ( 美国劳伦斯伯克利国家实验室) 、 u c b ( 美国加利福尼亚大学伯克利分校) 和u s c i s i ( 美国商务部信息科学学 院) 共同参与的v i n t ( v i r t u a li n t e r n e tt e s t b e d ) 项目研究开发的网络模拟器。 n s 2 是n s 的第二版，而目前n s 的最新开发版本是n s 3 。n s 具有开放源代码， 组件丰富，扩展性灵活和仿真数据的高可靠性等诸多优点，因此在网络协议研 究领域被受欢迎。 g l o m o s i m ( g l o b a lm o b i l ei n f o r m a t i o ns y s t e ms i m u l a t o r ) 是由美国加州大 学洛杉矶分校( u c l a ) 研发的面向无线网络的大规模网络仿真平台，拥有较高 运行效率、较好扩展性和易用性等优点。但是o l o m o s i m 是针对无线网络的仿 真平台，因此适应性不如n s 。 m a t l a b ( m a t r i xl a b o r a t o r y ) 是由美国m a t h w o r k s 公司推出的，主要用 于数值计算和图形处理的科学计算系统环境。m a t l a b 是一个多功能集的综合 仿真验证工具，不单单是网络等的仿真，同时它也是一款出色的数学应用软件， 不过用于网络仿真它还是存在诸多的限制，从而更适合作为验证协议数学分析 3 北京邮l u 人学硕l ：研究生学位论文 结果的仿真工具。 基于上述的介绍，n s 2 具有灵活的扩展性和高度的数据可靠性，因此本论 文选择n s 2 作为目标仿真平台，进行多信道路由仿真模型的研究工作。 1 2 研究任务 w l a n 等无线网络，以及t d m a 等无线多信道技术的发展，给路由协议 带来了新的挑战，要求新的路由协议可以带给网络更高的吞吐量。而网络仿真 作为网络协议研究的重要手段，对于路由协议的研究和发展起着重要的促进作 用，同样也面临着支持多信道路由仿真的需要和挑战。 n s 2 作为一款开源的组件丰富的网络仿真软件，一直以来都被各个研究机 构和高等院校普遍采纳。而且随着国内外对多信道路由研究的越来越重视，对 多信道路由协议的仿真支持也日益迫切。然而，n s 2 已有的移动节点模型并不 支持多信道路由协议的仿真。但是n s 2 与生俱来的开源性和可扩展性，使得研 究人员可以扩展已有的移动节点模型来实现对多信道路由仿真的需求。 目前基于n s 2 的多信道路由协议仿真扩展工作并不多，已有的一些也是基 于特定移动节点模型的特定协议来实现的，并不能同时支持其它路由协议的仿 真。因此本论文围绕n s 2 上的多信道路由仿真扩展为核心进行研究，通过对路 由协议的研究和对相关的多信道仿真工作的总结，以及对多信道路由仿真特性 的分析，最终实现一个通用的多信道路由仿真模型。 具体来说，本论文主要对如下方面内容进行研究： 1 ) 从认识路由协议的角度对路由协议进行学习和研究，总结路由协议的分 类策略和各类中典型的协议思想；学习n s 2 网络仿真软件的移动节点 模型；研究目前n s 2 多信道协议仿真扩展现状，对已有的多信道仿真 扩展方法进行总结，分析它们在多信道路由仿真时的不足。为多信道路 由协议的分析和多信道路由模型的设计奠定基础。 2 ) 对多信道路由协议的仿真进行分析，包括了多信道路由协议的两个重要 仿真特性和多信道路由仿真的需求，以及基于仿真特性的多信道路由协 议分析。 3 ) 结合上述研究内容，结合目前n s 2 的已有多信道扩展工作，提出适用 范围更广的多信道路由通用仿真模型，详细研究该模型的移动节点结 构、方法实现和新增组件功能和接口，并在n s 2 上进行编码实现和仿 真，通过仿真结果验证通用模型的正确性和适用性。 4 北京邮1 1 1 人学硕i ：研究生学位论文 1 3 论文章节安排 本文各章节内容安排如下： 1 ) 第一章介绍了多信道传输技术和多信道路由协议，以及主流的网络协 议仿真工具，明确了课题的研究背景和研究内容。 2 ) 第二章介绍了路由协议的分类和各类中典型的协议思想，以及n s 2 网 络仿真的基本原理和移动节点模型，进而分析总结了n s 2 多信道仿真 扩展的研究现状。 3 ) 第三章分析了多信道路由协议的仿真特性和仿真需求，以及基于仿真特 性的多信道路由协议和协议中存在的问题，进而结合多信道路由仿真 特性和已有的基于n s 2 的多信道扩展工作，本文提出了n s 2 多信道路 由通用仿真模型的概念。 4 ) 第四章分析了通用模型的仿真功能，论述了通用模型的仿真特性、移动 节点结构、新增组件功能等，并且详细描述了模型的实现方法和相关 类的实现。 5 ) 第五章详细概述了仿真验证方案，基于多信道路由协议的仿真特性，对 路由协议进行仿真验证，通过仿真分析以证明模型的成功实现。 6 ) 第六章结束语对全文工作进行了总结，并提出了课题今后的发展方向。 s 北京邮i u 人学硕i j 研究生学位论文 第二章路由协议及n s 2 多信道仿真现状 本章对路由协议进行分类介绍，并对各分类中典型的协议思想进行分析总 结。同时，本文选择n s 2 作为多信道路由仿真模型扩展的平台，因此也需要对 n s 2 无线仿真的原理以及移动节点模型进行分析总结，进而对基于n s 2 的多信 道仿真现状进行学习和研究。从而为多信道路由的分析和多信道路由通用仿真 模型的设计奠定良好的基础。 为此，本章首先以路由协议分类的方式对路由协议进行介绍，总结了现有 的路由协议分类和典型的协议思想。然后本章又从介绍了n s 2 网络仿真的基本 原理和移动节点模型，进而分析了现有基于n s 2 的多信道扩展工作，总结了各 自的实现方法、移动节点模型特性以及在路由仿真时的缺陷。 2 1 路由协议 在无线自组织网络【5 】的环境中，传统的距离向量协议如r i p ( 路由信息协议) 和链路状态路由协议如o s p f ( 开放最短路径优先) 等有线网络协议，由于网 络拓扑基本固定，并不适合无线自组织网络拓扑动态变化的特性。而且传统的 路由协议设计也没有考虑无线信道的单向信道特性，因此设计出来的路由并不 能准确的反应自组织网络的拓扑结构。同时，无线信道的广播特性也使得传统 的路由协议在路由的过程中产生许多冗余链路。而且，传统路由协议在选路过 程中，需要路由器定期的发送路由更新消息，消耗了大量网络带宽，以及周期 性的更新报文也消耗了大量主机能源。 为了解决无线网络中的路由问题，i e t f 于1 9 9 6 年成立了自组网工作小组， 研究无线网络环境下基于i p 协议的路由协议规范和接口设计1 6 l 。根据路由协议 的研究状况，目前路由协议的典型分类方法如图2 1 所示。 图2 - 1 无线自组织网络路由协议分类 6 北京邮l 也大学硕i ：研究生学位论义 2 1 1基于逻辑视图的分类 按照网络逻辑视图，可划分为平面路由协议( 节点维护路由的地位平等) 和分级的路由协议( 分为簇头节点和普通节点) 。 2 1 1 1 平面路由协议 在平面路由协议中，所有节点在路由过程中的地位是平等的，每个节点都 具有相同的形成和维护路由信息的责任。由于平面结构中节点地位平等的特性， 因此平面路由协议具有自身的优点，不存在特殊节点，路由协议的健壮性好， 通信流量平均的分散在网络中；同时路由协议也不用管理节点的移动问题。但 是这样的平面结构也有自己的缺点，其中最大的缺点就是限制了网络的规模。 所以平面路由协议，比较适合于小型的自组织网络环境。 2 1 1 2 分级路由协议 在分级路由协议中，网络中的节点地位不再是平等的。网络由多个簇组成， 网络中同时存在两种不同功能类型的节点：普通节点和簇头结点。而每一簇就 由一个簇头结点和多个普通节点共同维护所在簇内部的路由信息，其中簇头结 点负责所在簇的拓扑信息的压缩和摘要处理，并同时与其他簇头结点交换拓扑 信息。这样的分级路由协议具有它自身的优点，首先减少参与路由计算的节点 数目，降低交换路由信息所需的路由开销和维护路由表所需的内存丌销；其次， 基于簇的策略，能产生一个较为稳定的子网络，减少了网络拓扑动态变化对路 由协议带来的影响。但是也有其不足的地方，那就是簇头结点的可靠性和稳定 性对网络性能有较大的影响。所以分级路由协议，比较适合大规模的自组织网 络环境。 2 1 2 基于路由发现策略的分类 按照路由发现的策略，可划分为主动路由协议或按表驱动路由协议【7 】 ( p r o a c t i v e ，各节点周期性广播路由信息分组，主动发现路由，维护到全网所 有节点的路由) 、被动路由协议或按需驱动路由协谢8 1 ( r e a c t i v e ，仅在源节点 有分组要发送而没有去往目的节点的路由时才按需进行路由发现) 和混合路由 协测9 ( h y b r i d ，在一定的区域内采用主动路由协议，区域间采用被动路由协议) 。 7 北京j t l i ；q j , 人学硕i ：研究生学位论文 2 1 2 1 主动路由协议 主动路由协议，也称为先验式路由协议又称表驱动路由协议，每个节点维 护一张包含到达节点的路由信息的路由表，并根据网络拓扑的变化随时更新路 由表，所以路由表可以准确地反映网络的拓扑结构，源节点一旦要发送报文， 可以立即获得到达目的节点的路由。主动路由协议的优点是当数据分组需要发 送时，只要去往目的节点的路由存在，就能发送，延时较小；缺点是为了及时 反映拓扑结构的变化，路由更新需要花费较大开销。同时，由于网络拓扑结构 的动态变化，并不能保证这些路由更新信息的正确性，所以路由协议始终处于 不收敛状态。 而且这类路由协议通常是通过修改现有的有线路由协议来满足无线网络的 要求，如通过修改路由信息协议( r i p ) 得到的目的节点序列距离矢量协议 ( d s d v ) 。 d s d v o l ( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r ) 是一种无环路距离向量路 由协议，它是传统的b e l l m a n f o r d 路由协议的改进。d s d v 路由协议的最大特 点是采用了序列号机制区分新旧路由信息，防止可能产生的路由环路。缺点就 是不能适应拓扑结构快速变化的自组织网络。 d s d v 的算法思想。在d s d v 算法中，网络中每个移动节点维护一张路由 表，包含所有可到达的目的节点的路由，同时每个路由表项都被目的节点赋予 一个序列号( s e q u e n c en u m b s ) ，其目的是用来区别路由信息的新旧。通过周期 性的“完全转存”( f u l ld u m p ) 方式，把完整的路由信息转送出去。两次f u l ld u m p 之白j ，若有更新路由信息则用小的“增长”( i n c r e m e n t a lp a c k e t ) 数据包传送。 更新的路由广播包括目的节点地址、到目的节点的跳数、请求信息包的序列号 和新的发送序号。一般来说新路由的序号l l i h 路由的序号要大，通过序号的比 较可以选择新的路由，但是当两者的路由序号相同时，则选择更短的路由。另 外路由更新信息要延迟发送，以防止发送后不久就得到更好的路由。 d s d v 路由算法采用序列号的机制区分新旧路由，而且利用更新延迟，以 保证所获得的更新消息是最新的。当然它也有自身的缺点，由于d s d v 是采用 广播的方式来进行路由信息的更新，所以有可能导致路由信息的洪泛，尤其是 在网络规模比较大，网络节点比较多的时候。同时，d s d v 由于要维护全网的 路由信息，所以路由表的庞大信息也给主机造成资源消耗。 2 1 2 2 被动路由协议 被动路由协议，也称为反应式路由协议或者按需路由协议，是一种当需要 北京邮f u 人学顾i j 研究生学位论文 时- a 。查找的路由选择方式。与主动路由协议相反，按需路由协议在拓扑结构动 态变化的网络环境中，不必要维护去往全网的路由信息表。当且仅当在源节点 有分组要发送但没有去往目的节点的路由时，才“按需”进行路由发现。因此， 网络拓扑结构和路由表信息是按需建立的，它可能只是整个拓扑结构信息的一 部分。此类协议的优点是不需求周期性的路由信息广播，能节省一定的网络资 源；缺点是发送数据分组时可能出现延时问题。此外路由发现过程的延时与主 动路由协议中确定的查表时间相比，也是不可预测的。 被动路由协议路由过程包括路由发现和维护两个部分。当源节点发现没有 去往目的节点的路由时，协议触发路由发现过程。典型的被动路由协议有d s r ， a o d v 等。 a o d v t l l 】( a dh o eo n d e m a n dd i s t a n c ev e c t o r ) 是d s r 和d s d v 的结合， 它借用了d s r 中按需进行路由发现和路由维护的机制，以及d s d v 中的逐跳 路由、序列号、定期广播。 a o d v 的算法思想。a o d v 算法中，每个网络节点维护一张路由缓存表， 表的内容是到达源节点己知节点的路由信息。当有节点需要发送数据包的时候， 查找路由信息，看是否有存在的去往目的节点的路由信息，如果没有则触发路 由发现过程。当有新的节点加入或者有节点离开的时候，协议会触发路由维护 过程。 路由发现过程：单节点发信息时，会先在路由表中查找路由信息，发现则 按照路由表发送信息，没发现就进行路由发现过程。节点广播路由请求包 ( r r e q ) 给自己所有的邻节点，邻节点在接收到r r e q 包后，先在自己的路 由表中查找是否有到目的节点路由，如果有则将路由信息写入r r e p 包( 路由 回复包) 发给源节点；否则再将r r e q 转发给自己所有的邻节点。依次类推， 直到到达目的节点或是中间某个节点知道到达目的节点路由。 路由维护过程：如果某发起路由请求的源节点移动了，新节点加入网络或 者已有节点离开网络，它能够再次发起一个路由发现过程，以找到到达目的节 点的新路由。当沿着路由的某个节点移动了，这时移动节点的“上游”邻节点 a 注意到此节点的移动，a 节点会传播一个链路断开信息给a 节点的每一个有 效的“上游”节点通知他们删除路由表中的对应无效路由。这些邻节点依次传 播这个链路断开信息给“上游 节点，一直达到源节点。源节点会再次发起路 由发现过程。当有新节点加入或者已有节点的离开时，同样也会有相应的链路 更新信息的传递过程。 9 北京邮i 【1 人学硕l j 研究生学位论文 2 1 2 3 混合路由协议 自组织网络中单纯采用主动或被动路由协议都不能完全解决路由问题，因 此许多学者提出了结合主动先验式和被动反应式路由协议优点的混合式路由协 议，如z r p 【i 纠( z o n er o u t i n gp r o t o c 0 1 ) 。在z r p 中，分级被称作为区域。通过 区域半径( 以跳数为单位) 来指定每个节点维护的区域大小，也就是所有距离 不超过区域半径的节点都属于该区域。 z r p 综合利用了主动和被动路由各自的优点，首先每个节点采用d v a ( 距 离矢量路由算法) 协议维护去往区域内节点的路由信息，其次采用d s r 协议中 的按需路由机制发现去往区域外节点的路由。鉴于主动和被动路由协议的特点， z r p 的路由维护的方式也是混合式的，当主机需要使用的链路断开时，主机有 两种操作方式，一是通知源主机，另外是进行路由局部查找，其路由局部查找 方法和区间路由协议中的路由查找没有区别，唯一的不同点就是查找范围较小。 z r p 协议结合了主动和被动路由的优点，区域内路由使用预先路由，没有 被动路由中的初始延迟问题，而且一般区域范围较小，路由更新的代价可以忽 略；区域问路由采用了被动方式，避免主动路由周期性信息更新开销大的问题； 区域问路由发现时，将路由请求报文发给边界主机，提高了路由发现的速度。 但是也有其自身的不足，由于只允许目的区域内的主机应答，所以源主机获得 路由的时间将会延迟；同时周期性地广播报文，消耗了一定的主机能源和浪费 了一定的网络带宽。另外，由于区域半径的设置将直接影响路由的效率，因此 区域半径的决定也是决定z r p 效率的一个重要考虑因素。一般而言，小区域半 径更适合移动节点速度快的密集网络，而大区域半径则适合移动节点速度慢的 稀疏网络。 2 2 n s 2 无线仿真基础 本文的研究工作基于n s 2 开源仿真平台，是鉴于n s 2 对无线网络协议仿 真的灵活支持，因此需要对n s 2 仿真的基本原理以及无线仿真的移动节点仿真 模型进行了解。 2 2 1n s 2 基本原理 n s 是一个基于l i n u x 的开放源代码的网络仿真软件，具有丰富的网络仿真 组件。n s 2 是n s 的第2 个版本，n s 的最新版本是n s 3 ，但是n s 3 还在开发 和完善之中，所以本论文的研究工作是基于稳定版本n s 2 进行扩展的。n s 2 目 l o 刖 网 图2 - 2n s 2 软件构成示意图 n s 2 是一个离散时间模拟器【1 4 】。所谓离散事件模拟器，简单地说，事件规 定了系统状态的改变，当特定的事件产生后会改变系统状态，状态的修改仅在 事件发生时进行。n s 2 中的系统定义事件，主要有分组到达和时钟超时等。另 外，模拟时钟的推进由事件发生的时间量确定的，模拟处理过程的速率不直接 对应着实际时间，因此仿真系统只需花费较少的运行时间就能模拟真实环境中 较长的时间，大大提高了协议验证的效率。 n s 2 的核心部分是一个离散事件模拟引擎。通过分裂对象模型( s p l i to b j e c t m o d e l ) 的思想，n s 2 由编译类和解释类共同构成，分别对应c + + 和o t c l 两种 面向对象的语言，因此n s 2 中大部分组件都是由一个是c + + 类，一个是o t c l 类相互关联来实现的。利用c h 语言的高效的执行性能，c + + 类主要是实现组 件的功能，使得仿真获得较好的性能；利用o t c l 语言解释执行的灵活性，o t c l 类主要是实现参数的配置、组件的组装扩展以及仿真脚本的编写，使得可以随 意修改其代码而无需重新编译代码。 北京邮l 【1 人学硕t ：g f 究生学位论文 2 2 2n s 2 移动节点模型 n s 2 移动节点模型是实现n s 2 无线仿真的核心，本文所研究的多信道路由 仿真模型就是基于n s 2 的移动节点模型，通过对其扩展和组装而实现的。n s 2 中有两种移动节点模型，分别称为m o b i l e n o d e 和s r n o d e ，而两者的区别就在 于网络层的分组分发机制和适用的路由协议不同，其中m o b i l e n o d e 模型使用更 为普遍，其组件结构图如下图所示。 图2 - 3n s 2 移动节点模型结构图 图中与多信道仿真密切相关的组件的含义和功能如下： c h a n n e l ( 物理传输信道) ： 连接所有节点的组件，并没有实现具体收发操作。由通用操作指导模块 g o d 对