当前位置:首页 >> 信息与通信 >>

DSDV路由协议分析与仿真


毕业设计(论文)
题目 DSDV 路由协议分析与仿真

学院(全称) 专业、年级 学 生 姓 名 指 导 教 师 论文评阅人

信息科学与工程学院 通信工程 06 级 02 班 张志超 学号 06950221 许登元

重庆交通大学 2010 年





物联网的英文名称为“The Internet of Things”,简称:IOT。由该名称可见,物联 网就是“物物相连的互联网”。这有两层意思:第一,物联网的核心和基础仍然是互 联网,是在互联网基础之上的延伸和扩展的一种网络;第二,其用户端延伸和扩展到 了任何物品与物品之间,进行信息交换和通信。因此,物联网的定义是通过射频识别 (RFID)装置、红外感应器、全球定位系统、激光扫描器等信息传感设备,按约定的协 议,把任何物品与互联网相连接,进行信息交换和通信,以实现智能化识别、定位、 跟踪、监控和管理的一种网络。物联网的概念是在 1999 年提出的。最早时期,物联网 被称之为传感网。中科院早在 1999 年就启动了传感网的研究,并已取得了一些科研成 果,建立了一些适用的传感网。1999 年,在美国召开的移动计算和网络国际会议提 出了,“传感网是下一个世纪人类面临的又一个发展机遇”。2003 年,美国《技 术评论》提出传感网络技术将是未来改变人们生活的十大技术之首。 随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟,人们研制 出了各种具有感知能力、计算能力和通信能力的微型传感器。由许多微型传感器构成 的无线传感器网络(WSN)引起了人们的极大关注。由设置在无人值守的监控区域内大 量的具有通信与计算能力的微小传感器节点构成的智能自治测控网络系统称为无线传 感器网络(Wireless sensor networks)。它包括传感器、感知对象和观察者。人们可以通 过传感器网络直接感知客观世界,称为人与自然之间重要的交互方式。 WSN 的主要任务是对分布在传感节点监测范围内的数据进行查询,收集和处理, 并将最终数据发布给终端节点, 方便人们感知客观世界;而路由算法则是 WSN 中最重 要的部分,它用来建立源节点与目的节点之间的路径,实现数据通信。DSDV 是对传 统的 Bellman-Ford 路由协议的改进,是一种无环路距离向量路由协议,同时也是一种 表驱动主动路由协议。由于其算法简单,同时又具有获取路由的延时小,较适合具有 实时要求的应用;引入目的节点序列号,既能区别路由的新旧,又能有效避免路由环 路的产生和无限计数的问题;有效减少端到端的时延,从一定程度上满足各种应用对 QoS 的要求。在此对其进行研究,通过仿真,分析其有点以及存在的问题,并相对应 的提出改进办法。 NS2(Network Simulator, version 2) 称为网络模拟器,又称网络仿真器。最初由 UC Berkeley 开发,专门用来研究大规模网络以及当前和未来的网络协议交互行为。由于 NS2 中所有源代码都开放,因此受到大量研究人员的亲睐,也是目前网络研究领域应 用最广泛的网络仿真软件之一。随着越来越多人的研究,其功能更加强大,支持的协 议和功能模块也更加丰富。它对有线和无线网络上的 TCP、路由和多播等协议的仿真

提供了强有力的支持。由于强大的功能和丰富的模块,网络传输协议、路由队列管理 机制、路由算法、业务源流量产生器,以及无线网络的 Ad hoc,WLAN 和 WSN 路由, 移动 IP 和卫星通信网络等的仿真模块均已实现。同时通过对局域网的仿真,从而实现 了多播以及一些 MAC 子层协议。因此,考虑到其中多的优点,在本次课题研究中将采 用 NS2 仿真软件进行路由仿真。 本文主要研究目的序列距离矢量路由算法(DSDV),其最初由 Charles E.Perkins 等人提出。对 DSDV 路由原理进行理论分析的同时,并通过网络仿真软件 NS2 对其进 行仿真。由于 NS2 是一款开放源代码的网络仿真软件,任何人可以获得、使用和修改 其源代码,正是如此,世界各地的研究人员每天都在对其功能进行扩展和更新,因此, 我们简单介绍了 NS2 的结构、前后台的连接和仿真的一般流程。最后通过对仿真结果 中得到的数据进行分析,并使用相关软件提取出有用数据,进行分析,来更进一步认 识和了解 DSDV 路由协议。





中文摘要 ................................................................. I 英文摘要 ................................................................ II 第1章 绪 1.1 1.2 1.3 论 ............................................................ 1

课题背景 ........................................................ 1 国内外研究现状和发展 ............................................ 1 本文研究内容及意义 .............................................. 3

第 2 章 无线传感器网络及其路由技术概论 .................................... 4 2.1 无线传感器网络概述 ............................................... 4 2.1.1 无线传感器网络定义 .......................................... 4 2.1.2 无线传感器网络的特点 ........................................ 4 2.1.3 无线传感器网络的应用 ........................................ 5 2.2 无线传感器网络的结构 ............................................. 7 2.2.1 分层结构 .................................................... 7 2.2.2 节点硬件结构 ................................................ 7 2.2.3 协议栈 ...................................................... 8 2.3 路由协议的分类 ................................................... 8 2.3.1 按需驱动路由协议 ............................................ 9 2.3.2 表驱动路由协议 ............................................. 11 2.4 本章小结 ........................................................ 13 第 3 章 NS2 仿真软件 ..................................................... 15 3.1 NS2 概述 ......................................................... 15 3.2 NS2 结构 ......................................................... 16 3.3 C++与 Otcl 的接口 ................................................ 16 3.4 Otcl 脚本编写 .................................................... 18 3.5 NS2 仿真流程 ..................................................... 19 3.6 NS2 相关工具介绍 ................................................. 20 3.7 本章小结 ........................................................ 21 第 4 章 DSDV 路由协议分析 ................................................ 22 4.1 协议的提出 ...................................................... 22 4.2 工作原理 ........................................................ 22 4.2.1 路由表的建立、更新和数据转发之间的关系 ..................... 23

4.2.2 路由表的建立 ............................................... 23 4.2.3 路由表的更新 ............................................... 23 4.2.4 数据包的转发 ............................................... 24 4.3 DSDV 相关的关键技术 .............................................. 24 4.3.1 避免路由环路 ............................................... 24 4.3.2 减少路由波动 ............................................... 26 4.3.3 定时器 ..................................................... 27 4.3.4 序列号机制 ................................................. 27 4.4 本章小结 ........................................................ 27 第 5 章 DSDV 路由仿真 .................................................... 29 5.1 总体设计 ........................................................ 29 5.2 DSDV 路由仿真实现 ................................................ 32 5.2.1 仿真场景设置 ............................................... 32 5.2.2 仿真结果及分析 ............................................. 33 第 6 章 总结与展望 ....................................................... 38 6.1 工作总结 ........................................................ 38 6.2 未来展望 ........................................................ 38 致 谢 .................................................................. 40 参考文献 ................................................................ 41

2010 届通信工程专业毕业设计(论文)





无线传感器网络(Wireless Sensor Network,WSN)作为人与自然界进行信息沟通的 一种方式,随着目前传感器节点小型化、多样化的发展,正得到越来越广泛的使用, 人们对无线传感器网络各方面的研究也成为目前学术界的研究热点。路由协议是无线 传感器网络在网络层上的一个关键研究课题,本文着重研究基于路由表的目的序列距 离矢量路由协议。 本文在阐述无线传感器网络概念和特点的基础上,引入了无线传感器网络路由, 介绍了现有无线传感器网络路由协议,并结合现有无线传感器网络路由协议,实现了 一种基于路由表驱动的路由协议(DSDV)。本文详细分析了 DSDV 路由协议,实现了 DSDV 路由协议在 NS2 上的仿真,对在仿真过程中得到的数据进行分析,从中发现网 络拓扑和找到路由路径,并对结果加以分析,进一步深化对 DSDV 路由协议的认识和 了解。

关键词:无线传感器网络,路由协议,DSDV,NS2



张志超: DSDV 路由协议分析与仿真

ABSTRACT
Wireless sensor network(WSN)is a way that people communicate with nature. Along with the development of the sensor technology, The sensor is now miniaturization and diversification. It is being more and more widely used. More attention has been paid to WSN and the research on eaeh aspect of WSN is also an active field in current aeademe. Routing protocol is a key issue on network layer inWSN. This thesis mainly focuses on Destination-Sequeneed Distanee-Veetor(DSDV) routing protocol based on routing table. This thesis describes the concept of WSN on the basis of the characteristics of the introduction of WSN routing, and generally introduces of the existing WSN routing protocol and achieves a routing protocol based on the kinds of routing table-driven in conjunction with existing WSN routing protocols (DSDV). This thesis anlysizes the DSDV routing protocol in detail, and realized simulation of DSDV routing protocols in NS2, and analysis of the data produced during simulation, then to find the routing path. After that, we analysis the results and results to furtherly deepen our understanding of DSDV routing protocols.

Keywords: Wireless sensor networks, Routing protocol, DSDV, NS2

II

2010 届通信工程专业毕业设计(论文)

第1章 绪
1.1 课题背景



随着传感器技术、微机电系统、现代网络和无线通信技术等技术的发展,无线传 感器网络得到了极大的发展和应用。无线传感器网络涉及众多学科,成为目前 IT 领域 中研究热点之一,也被认为是二十一世纪最重要的技术之一,对人类未来的生活方式 产生巨大影响[1]。目前,无线传感器网络的应用已由军事领域扩展到其他许多领域,能 够完成诸如灾难预警与救助、家庭健康监测、空间探索、抢险救灾、防恐反恐、生物 医疗等传统系统无法完成的任务。可以说二十一世纪无线传感器网络将无处不在。无 线传感器网络是由大量无处不在的,具有通信与计算能力的微小传感器节点密集布设 在无人值守的监控区域而构成的能够根据环境自主完成指定任务的“智能”自治监测 网络系统[2]。 无线传感器网络是一种超大规模、 无人值守、 资源严格受限的全分布系统, 采用多跳对等的通信方式,其网络拓扑动态变化,具有自组织、自适应等智能属性。 在研究初期,人们曾经一度认为成熟的 Internet 技术加上 Ad hoc 路由机制对无线 传感器网络的设计是足够充分的, 但进一步研究表明[3]: 无线传感器网络与传统无线网 络有着明显不同的技术要求,前者以数据为中心,后者以传输数据为目的。无线传感 器网络是集成监测、控制及无线通信的网络系统,节点数目更为庞大,节点分布更为 密集;由于环境影响和能量耗尽,节点更容易出现故障;环境干扰和节点故障易造成 网络拓扑结构的变化;另外,传感器节点具有的能量、处理能力、存储能力和通信能 力都十分有限。传统无线网络的首要设计目标是提供高服务质量和高效带宽利用,其 次才考虑节约能源;而无线传感器网络的首要设计目标是能源的高效使用,这也是无 线传感器网络与传统无线网络的最重要的区别之一。这些不同于传统无线网络的技术 要求为无线传感器网络的研究提出了新的挑战,开发专用的通信协议和路由算法就成 为了当前无线传感器网络领域内首先需要解决的课题。

1.2 国内外研究现状和发展
WSN 的研究起源于 20 世纪 70 年代。最早应用于军事领域,例如冷战时期布设在 一些战略要地的海底、用于监视苏联潜艇的声音监视系统(Sound Surveilance System, SOSUS)及空中预警与控制系统(Air-borne Warning and Control System,AWACS),这种
1

张志超: DSDV 路由协议分析与仿真

原始的传感器网络通常只能捕获单一信号,传感器节点之间进行简单的点对点通信, 网络一般采用分级处理结构。但真正具备现代意义的无线传感器网络研究是从 1980 年 左右的分布式传感器网络项目开始的。该项目由时任美国国防部高级研究计划局信处 理技术办公室主任的 Robert Kahn 主导,其主要目的是验证 Arpanet(Intemet 的前身)的 通信方式能否扩展到无线传感器网络中。 20 世纪 80—90 年代, 传感器网络的研究主要 在军事领域进行,并成为网络中心战中的关键技术,其中比较著名的系统包括美国海 军研制的协同交战能力系统,用于反潜的确定性分布系统和高级配置系统,以及远程 战场传感器网络系统和战术远程传感器系统。1994 年加州大学洛杉矶分校的 William J.Kaise 教授向美国国防部高级研究计划局提交了研究建议书“ Low Power Wireless Integrated Microsensors” ,对推动 WSN 研究有里程碑的意义[4]。1998 年 G.J.Pottie 从网 络研究的角度重新阐释了 WSN 的科学意义[5]。 在 90 年代之前,WSN 的研究多集中在军事方面。1999 年 9 月《商业周刊》将其 列为 21 世纪最重要的 21 项技术之一后, WSN 开始得到越来越多的网络研究者的关注。 1999 年美国加州大学伯克利分校的“智能尘埃”计划验证了传感器节点硬件小型化的 可行性。把传感器、微处理器、电源及无线通信单元集成在 1 m m3 的微小节点上,在 传感器节点集成化、小型化以及能量管理方面取得了很大的进展。目前美国几乎所有 著名院校都有研究小组在从事无线传感器网络相关技术的研究,一些大公司也都开始 介入该领域的研发工作。加拿大、英国、德国、韩国、日本等国家的研究机构都对无 线传感器络表现出了极大的兴趣,纷纷展开了该领域的研究工作。我国对无线传感器 网络的发展也非常重视。从 2002 年开始,国家自然科学基金、中国下一代互联网示范 工程、国家“863”等已陆续资助了多项和无线传感器网络相关的课题。 到现在为止,传感器网络的研究大致经过了两个阶段。第 1 阶段主要偏重利用 MEMS(Micro-Electro-Mechanism System)技术设计小型化的节点设备,代表性的研究项 目有 WINS 和 Smart Dust。对于网络本身问题的关注和研究可以认为是传感器网络研 究的第 2 个阶段,目前正在成为无线网络研究领域的一个不小的热点。从网络分层模 型角度分析,每一层都有需要结合传感器网络的特点进行细致研究的问题,就己有的 研究而言,主要集中在网络层和链路层。随着现代微电子技术、微机电系统材料、无 线通信技术、信号处理技术、计算机网技术等的进步。传感器所能探测的信息种类也 越来越多,温度、湿度、压力、速度等信息都能够被传感器采集到。传感器节点的结 构主要由传感器、微处理器、无线通信单元构成。节点体积小成本低使得节点能够被 大量散布在监测区域内。 传感器节点技术的进步、成本的降低使得 WSN 在商业中的应 用成为可能。
2

2010 届通信工程专业毕业设计(论文)

1.3 本文研究内容及意义
本文以无线传感器网络为研究对象,主要研究多跳通信方式的网络层路由协议, 并利用 NS2 仿真软件实现目的序列距离矢量路由协议。研究内容主要包括以下几个方 面: (l) 介绍了无线传感器网络的发展、概念、体系结构、特点以及应用。 (2) 分析和实现目的序列距离矢量路由协议(DSDV)。主要分析了 DSDV 路由协议 的工作原理和运行机制,以及 DSDV 路由协议的数据包转发过程,并在理论上证明了 DSDV 无路由环路及如何解决路由波动问题。 (3) 在 NS2 上运用 C++语言实现了目的序列距离矢量路由协议(DSDV)的仿真,对 仿真过程中产生的数据进行分析,从中发现网络拓扑和找到路由路径,并对结果加以 分析,进一步深化对 DSDV 路由协议的认识和了解。 现代信息科学由信息的生成、获取、存储、传输、处理及其应用六大部分组成, 其中信息技术产业链和应用环节的前提是信息的获取。如果没有提取到信息,就没有 信息的传输处理和应用,也就没有信息化。无线传感器网络的基本功能是获取信息。 借助于传感器,可以把被测的物理量转换为相应的电量输出,来实现信息的传输、处 理、记录、显示和控制等操作。随机分布的集成有传感器、数据处理单元和通信模块 的微小节点通过自组织的方式构成网络,一方面可以克服单一节点作用范围的局限, 有效扩展信息感知的空间范围;另一方面,可以对多个传感器所采集的信息作融合或 综合处理,以便能够从多方位对事物进行刻画。 然而由于传感器节点存在计算能力、存储能力、携带能量十分有限的缺点,每个 节点只能获取局部网络的拓扑信息,因此其上只能运行相对比较简单的网络协议。同 时,网络资源随着拓扑结构的动态变化也在不断变化,这些都对网络协议提出了更高 的要求。路由协议主要作用是寻找源节点到目的节点通信的最优化路径,它对整个网 络的利用率提高,避免产生通信拥塞和均衡网络流量至关重要。可以认为,路由协议 的好坏决定了整个网络的通信质量和生存周期。因此,研究多跳通信方式和能量有效 性的网络层路由协议成为无线传感器网络基础研究的热点,也成为无线传感器网络其 它方面研究的基础。

3

张志超: DSDV 路由协议分析与仿真

第 2 章 无线传感器网络及其路由技术概论
2.1 无线传感器网络概述
2.1.1 无线传感器网络定义 无线传感器网络[6](wireless sensor network,WSN)就是由大量密集布设的智能传感 器节点构成的网络,它采用自组织方式配置节点,节点间通过协同工作完成感知、数 据采集、简单处理并通过多跳通信方式最终将监测区域的数据信息传送给观察者。由 于传感器节点数量众多,而布设时只能采用随机投放的方式,因此传感器节点的位置 不能预先确定,这就决定了各节点间通过无线信道连接,以自组织网络为拓扑结构, 以多跳对等方式进行通信。节点具有简单的计算能力、预处理能力,通过局部的数据 采集处理并转发给其它节点,最终把监测数据传送给观察者。 2.1.2 无线传感器网络的特点 无线传感器网络中的节点采用无线方式进行组网,不需要有线基础设施的支持。 可以随时随地组建网络,自由地进行通信。各节点本身既是主机又是路由器,既进行 信息采集,又转发收到的信息包。其具有以下特点: (l) 硬件资源有限[7]。节点由于受价格、体积和功耗的限制,其计算能力、存储能 力都比普通的计算机功能要弱很多。这一点决定了在节点操作系统设计中,协议层次 不能太复杂。 (2) 能量有限。传感器节点被随机布设在监测区域内,没有有线设备的支持,只能 靠自身的电池提供能量。传感器节点要收发信息、处理信息都要消耗能量。一旦能量 耗尽就会造成传感器节点的失效,出现监测空白。要解决这个问题,一是要通过设计 合适的网络协议,减少传感器节点的能耗,使传感器节点能够工作得更长久。对于网 络层协议而言就是要减少路由信息的传递,降低路由开销,还要适应拓扑不断变化的 网络。降低协议的复杂性,减少处理协议的开销。二是要在网络工作过一段时间后, 向网络中补充一些传感器节点。 (3) 多跳路由。网络中节点通信距离有限,一般在几百米范围内,节点只能与它的 邻居直接通信。如果希望与其射频覆盖范围之外的节点进行通信,则需要通过中间节
4

2010 届通信工程专业毕业设计(论文)

点进行路由。在有线网络中,使用网关和路由器来实现多跳路由,而无线传感器网络 中没有专门的路由设备,只能由普通网络节点完成多跳路由。这样每个节点既可以是 信息的发起者,也可以是信息的转发者。 (4) 自组织网络。在布设传感器节点的时候通常采用随机散布的方式,例如采用飞 机在需要检测的地方进行散播或者由人随机放置。各节点的邻近关系不确定。并且在 通信过程中有些传感器节点因为能量耗尽或环境因素的影响而失效,一些通信节点又 可能为了弥补失效节点而补充进来,导致网络拓扑的变化。因而无线传感器网络要能 够通过节点之间的协调,以适应不断变化的自身条件和外部环境。 (5) 网络动态性[8]。无线传感器网络具有一定的动态性,网络中的传感器、感知对 象和观察者这三要素都可能具有移动性,并且经常有新节点加入或已有节点失效,因 此,网络的拓扑结构会经常动态变化,传感器、感知对象和观察者三者之间的路径也 随之变化,另外无线传感器网络必须具有可重构和自调整性。 无线传感器网络类似于 Ad Hoc 网络,多跳通信、自组织网络、能量有限。虽然有 许多的共同点,但无线传感器网络绝不是 Ad Hoc 网络的一个子集。它在很多方面有别 于 Ad Hoc 网络。由于这些区别的存在,我们就不能直接将 Ad Hoc 网络中的协议直接 应用于无线传感器网络,而是根据自身特点,对 Ad Hoc 网络的协议进行必要的改进, 进行专门的设计。 2.1.3 无线传感器网络的应用 无线传感器网络作为二十一世纪巨大影响力的技术之一,有着巨大的应用前景。 随着传感器技术、无线通信技术、计算技术的不断发展和完善,借助目前形式多样的 传感器节点,可以探测包括温度、湿度、噪声、光强度、压力、土壤成分、移动物体 的大小、速度和方向等众多我们感兴趣的物质现象。通过把这些传感器节点在探测区 域的大量散布,可以实现多种应用: (1) 军事应用 传感器网络研究最早起源于军事领域,实验系统有海洋声纳监测的大规模传感器 网络,也有监测地面物体的小型传感器网络。现代传感器网络应用中,通过飞机撒播、 特种炮弹发射等手段,可以将大量便宜的传感器密集地撒布于人员不便于到达的观察 区域,如敌方阵地内,收集到有用的微观数据;在一部分传感器因为遭破坏等原因失 效时,传感器网络作为传感器网络整体仍能完成观察任务。传感器网络的上述特点使 得它具有重大军事价值,可用于监测人员、装备等情况以及单兵系统;通过在人员、
5

张志超: DSDV 路由协议分析与仿真

装备上附带各种传感器节点,可以让各级指挥员比较准确、及时地掌握己方的保存状 态;监测敌军进攻;评估战果;核能、生物、化学攻击的侦察等地方。 (2) 智能交通 无线传感器网络具备功耗低、传输距离远、可靠性高、组网能力强的优良特性, 可以为智能交通系统的信息采集提供一种有效手段,可以监测路口各个方向上的车辆, 根据监测结果,改进信号控制算法,提高交通效率。在交通信息采集中,终端节点可 以定时收集和感知区域内车辆的相关信息。当车辆进入监控范围后,采集车辆的行驶 速度等信息,并将信息传送给下一个节点。当下一个节点感应到该车辆时,结合车辆 在两个传感器节点间的行驶时间,就可估算出车辆的平均速度。多个终端节点将各自 采集并初步处理后的信息通过汇聚节点汇聚到网关节点,进行数据融合,获得道路车 流量与车辆行使速度等信息,从而为交通信号控制提供精确的输入信息。 (3) 建筑监控 在建筑物局部形成一个无线传感器网络,分布在建筑物不同位置的传感器节点把 建筑物各点的压力值、摩擦力、张力值、振动幅度等不同数据通过 sink 节点发送到数 据处理中心。数据处理中心依据这些传感器节点传送来的信息,绘制相应的监控曲线。 由于建筑物所处的位置通常都位于设有有线基础设施的城市或其附近,sink 节点可以 通过 GSM 等传统通信网络把采集到的数据传送给附近的数据处理中心, 人们可以对此 进行相关的分析,因此就通过 WSN 实现了对建筑物随时随地的远程监控。 (4) 安全监控 在上海世博会的召开期间,为了确保世博会期间各方面的安全,特别是水、电、 煤气、交通等重要基础设施和会展场馆等重要场所的安全。作为一种新兴的检测技术, WSN 具有快速布置、自组织等特性,胜任大范围、多信号的分布式检测,可以在安全 预警、应急处理和灾后恢复中发挥重要作用。在 2010 年世博会的安全保障中,WSN 应用过程如下所述:(1)根据待检测目标和预期应用环境,设计和开发集成了相关传感 器的节点;(2)将这些传感器节点布置在检测区域,经过简单的初始化配置,这些节点 组网形成 WSN,并准备接受检测任务;(3)根据控制台的命令完成有关检测任务,并 定期汇报或紧急报告检测信息至控制台。

6

2010 届通信工程专业毕业设计(论文)

2.2 无线传感器网络的结构
2.2.1 分层结构 无线传感器网络的分层结构如图 2.1 所示。 MAC 层和物理层协议采用的是 IEEE802.15.4。IEEE802.15.4 是针对低速无线个人区域网络(LR-WPAN)制定的标准。 该标准把低能量消耗、低速率传输、低成本作为重点目标,旨在为个人或家庭范围内 不同设备之间低速互连提供统一标准。IEEE802.15.4 的网络特征与无线传感器网络存 在很多相似之处,所以许多研究机构把它作为无线传感器网络的无线通信平台。
应用、安全、多媒体

应用层 传输层 网络层

可靠、确认、流量控 制、吞吐量 连接/无连接、路 由、可达性 介质访问、功率管 理、帧格式 信道编码、无线传 输、调制解调

数据链路层 IEEE802.15.4 物理层

图 2.1 无线传感器网络的分层结构

2.2.2 节点硬件结构 一个传感器节点由四个基本部分组成[9]。如图 2.2 所示:一个感测单元、一个处 理单元、一个收发单元和一个供电单元。感测单元就是传感器模块中负责监测区域内 信息采集和数据转换。处理单元主要负责控制整个传感器节点的操作,存储和处理本 身采集的数据以及其他节点发来的数据。收发单元负责与其它传感器节点进行无线通 信,交换控制信息和收发采集数据;供电单元负责为传感器节点提供运行所需的能量。
供 电 单 元

处理单元 存储器 传感器 ADC 处理器 收发器 收发单元

感测单元

位置查找系统

移动设备

图 2.2 传感器节点结构图
7

张志超: DSDV 路由协议分析与仿真

2.2.3 协议栈 无线传感器网络作为一种网络,它的协议栈也包括物理层、数据链路层、网络层、 传输层和应用层,这与互联网协议栈的五层协议相对应。另外,协议栈还包括能量管 理平台、移动管理平台和任务管理平台[10]。如图 2.3 所示
任务管理平台 移动管理平台 能量管理平台 应 传 网 物 用 输 络 理 层 层 层 层

数据链路层

图 2.3 无线传感器网络协议栈

2.3 路由协议的分类
目前,无线传感器网中路由协议的最常见分类方式是按路由发现策略,将路由协 议按驱动方式分为按需驱动路由和表驱动两种类型,如图 2.4 和图 2.5 所示。
按需驱动路由协议

AODV

DSR

TORA

ABR

SSR

图 2.4 按需驱动路由协议

表驱动路由协议

DSDV

GSR

WRP

HSR

ZHLS

CGSR

FSR

图 2.5 表驱动路由协议
8

2010 届通信工程专业毕业设计(论文)

2.3.1 按需驱动路由协议 按需驱动路由协议(On Demand Routing),又称为反应式路由,是一种当需要时才 查找路由的路由选择方式。节点并不保存及时准确的路由信息。当源节点要向目的节 点发送报文时,源节点在网络中发起路由查找过程,找到相应的路由后,才开始发送 报文,为了提高效率,节点可以将找到的路由保存在缓存中供后续发送使用。 图 2.4 是现有的部分反应式路由协议。AODV(Ad hoc On Demand Distance Vector) 是 DSDV 的改进,但它并不维持一张路由表,而是根据需要创建路由,以减少广播数。 当有数据包需要传送时,为了寻找路径,源节点广播路由请求分组,邻近节点收到广 播后再向其它邻近点广播(但丢弃收到的重复路由请求分组),直到到达目的地或者到 达已有最新路由的中间节点。路由请求分组采用序列号编码以避免环路,并保证中间 节点只回应最新的信息。 当节点转发一个路由请求分组到其邻近节点时,在本地只对第一次出现的请求分 组进行复制,以便为后续的路由回应分组构造反向路径,但它只是适合对称链路的网 络。 若源节点移动时,路由表必须重新初始化;若中间节点移动,其邻近点会发现链 路的失效,并将链路失效的信息通告给其上行邻近点,直到源节点收到该信息,然后 根据需要重新构造路由。事实上它是 DSR 和 DSDV 的结合,它借用了 DSR 的路由发 现和路由维护机制,利用了 DSDV 的逐跳(hop-by-hop)路由、序列编号和周期更新的 机制。 DSR(Dynamic Source Routing)是一种源路由协议,每个分组的分组头中包含了源 到目的的整条路由信息。它采用路由缓存技术,用于存储源路由信息,当发现新的路 由时则修改路由缓存内容。在此协议运行过程中,包括非常重要的两个方面:路由发现 和路由维护。 当有数据包要发送时,源节点先检查缓存中是否有到达信宿的路由信息,若有一 个非过期的路由,则可直接采用,否则就广播一个路由请求分组进行路由初始化;路 由请求分组中含有源/目的地址和一个唯一的标识符,中间节点收到后,判断其是否有 到目的节点的路由,若没有,则将其地址附加到分组的路由记录中,再转发给邻近点。 为了限制路由请求分组的传播数目,只有当收到的分组信息是最新的且路由记录中没 有节点地址时,节点才处理之。在收到的路由请求分组的路由记录中已包含源节点到 此节点的节点序列,当目的节点进行应答时,它将路由记录信息从路由请求分组中复 制到应答分组中,若是中间节点的应答,则将缓存中到目的节点的路由附加到路由请
9

张志超: DSDV 路由协议分析与仿真

求分组后,再放入应答分组中。在返回应答过程中,先检查路由缓存中是否有到源节 点的路由,若网络链路是对称的,则可采用反向解析获得,否则,节点必须发起新的 路由发现过程去获得到信源的路由。 在路由维护机制中,DSR 采用两种分组:路由差错分组和路由的确认。当数据链路 出现致命的传播问题时;会产生一个路由差错分组,节点收到此分组后,从其路由缓 存中删除出错的路由跳数,所有包括此出错跳数的路由都将被截去此段。确认分组用 于识别链路的正确运行。 TORA(Temporally Ordered Routing Algorithm)是一种源初始化按需路由选择协议, 它采用链路反转的分布式算法,具有高度自适应、高效率和较好的扩充性,比较适合 高度动态移动、多跳的无线网络。其主要特点是控制报文定位在最靠近拓扑变化的一 小部分节点处,因此节点只保留邻近点的路由信息。该算法中路由不一定是最优的, 常常使用次优路由以减少发现路由的开销。TORA 包括三个基本模块:路由的创建、路 由的维护和路由的删除。 TORA 算法的原理可以用水从高山上流下的过程来比喻,水道代表节点之间的链 路,水道的转接处代表节点,水流代表分组,每个节点有一个相对于目的节点的高度, 用做计算路由的度量。如果节点 A 到节点 B 的链路中断,就给 A 一个比其邻近节点都 高的高度值,这样水流(分组)就从 A 回流(这个过程称为反转),通过其它节点流向目 的节点。 ABR(Associativity Based Routing)采用新的方法解决无线路由问题,避免了回路、 死锁和重复分组等缺陷。它定义了一种新的路由制式,称为联合稳定度,用于描述两 个节点在时间和空间的连接稳定性,节点的联合稳定度高,说明节点处于低移动状态, 反之处于较高移动状态。ABR 的实质就是发现长期有效的路由。 在 ABR 中, 根据节点的联合稳定度选择路由, 每个节点周期性地产生信号(Beacon) 以表示它的存在,当邻近节点收到一个 Beacon,就修改它的相关表,若收到来自相同 节点的信号,则增加与此节点的相关度。 ABR 协议由三部分组成:路由发现、 路由重构(RRC)和路由删除。 路由发现采用广 播查询和等待应答的循环方式(BQ-REPLY),源首先广播一个 BQ 报文,各节点只转发 一次 BQ 包,当中间节点收到 BQ 报文后,将其地址和相关标记值附加到此报文中,后 续节点删除其上行节点的邻近点联合稳定标记实体,只保留与其自身和上行节点有关 的实体。到达目的节点的每个分组包含有各路径节点的联合稳定标记值,这样目的节 点通过检查各节点的联合稳定标记值,选择最佳路由。当多条路由有相同联合稳定标 记值时,则选择具有最小跳数的路径。一旦路径选定,目的节点沿着被选定的各路径
10

2010 届通信工程专业毕业设计(论文)

发送一个应答分组。有应答分组经过的路径为有效路径,其它路径保持非激活状态, 因此可避免重复分组到达目的节点,RRC 包括局部路由发现、无效路由的删除、有效 路径的修改和新路由的发现等,它视不同节点的移动而定。若是源节点移动,将引起 一个新的 BQ-REPLY 处理,因为 ABR 是源路由协议,路由通知报文(RN)用于删除与 下行节点相关的路由实体。当目的节点移动时,其直接上行节点删除此路由。本地查 询处理 LQ(H), (H 为上行节点到目的节点的跳数)用于初始确定该节点是否仍然可达。 若目的节点收到 LQ 分组,则选择最佳局部路由并应答;否则初始节点超时并返回到 下一个上行节点, RN 报文发送给下一个上行节点去删除无效路由并通知它进行 LQ(H) 处理,当这样的处理导致路径回退超时一半时,则 LQ 处理不再继续,源节点初始化 一个新的 BQ 处理。当所发现的路由不再需要时,源节点广播一个路由删除(RD)报文 通知各节点从路由表中删除此路由实体。这里,RD 报文采用全广播方式。 SSR(Signal Stability Routing)协议选择路由的标准是利用节点之间信号的强度和 节点位置的稳定度。SSR 可分为两个相关协议:动态路由 DRP 和静态路由协议 SRP。 DRP 的任务是负责维持信号的稳定度表与路由表,信号稳定度表记录相邻节点信号强 度,通过周期性的与链路层交换信息得到。SRP 负责分组的发送和处理。利用 DRP 建 立的路由表完成。若没有现成的路由,则重新启动路由寻找过程。 2.3.2 表驱动路由协议 表驱动(Table driven)路由协议又被称为先应式路由协议,是一种基于表格的路由 协议。在这种路由协议中,每个节点维护一张或多张表格,这些表格包含到达网络中 所有其它节点的路由信息。当检测到网络拓扑结构发生变化时,节点在网络中发送更 新消息。收到更新消息的节点更新自己的表格,以维护一致、及时、准确的路由信息。 不同的表驱动路由协议的区别在于拓扑更新消息在网络中传播的方式和需要存储的表 的类型。表驱动路由协议不断的检测网络拓扑和链路质量的变化,根据变化更新路由 表,所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文,可以立即 取得到达目的节点的路由。 图 2.5 是现有的部分表驱动路由协议。 DSDV(Destination Sequenced Distance Vctor) 路由协议是一种无环路距离向量路由协议, 它是传统的 Belllnan Ford 路由协议的改进。 在 DSDV 中,每个移动节点都需要维护一张路由表。路由表表项包括目的节点、跳数 和目的地序号,其中目的地序号由目的节点分配,主要用来判别路由是否过时,并可 防止路由环路的产生。每个节点必须周期性与邻节点换路由信息,当然也可以根据路
11

张志超: DSDV 路由协议分析与仿真

由表的改变来触发路由更新。路由表更新有两方式:一种是全部更新(Full dump),即拓 扑更新消息中将包括整个路由表,主要应用于网络变化较快的情况;另一种方式是部 分更新(Inceremental update),更新消息中仅包含变化的路由部分,通常适用于网络变 化较慢的情况。 在 DSDV 只使用序列号最高的路由,如果两个路由具有相同的序列号, 那么将选择最优路由(如跳数最短)。 NS2 实现 DSDV 路由协议的具体策略如下:一个没 有找到路由的分组到达节点后首先被缓存,同时节点发送路由查询消息,直到收到接 收端的路由响应消息。当缓存溢出时,新来的分组将被丢弃。分组到达目的点后将直 接由地址解析复用器送到相应的端口,而后由端口将分组送到目的地。 CGSR(Clusrtered Gateway Switch Routing)与 DSDV 类似,但是 CGSR 并不是一个 大的平面网络。CGSR 分配指定了簇首节点和网关节点,其中簇首节点用来控制一组 节点和网关节点,网关节点是两个簇之间的节点。当一个节点要发送分组时,这个分 组首先到达该发送节点的簇首节点,然后簇首节点把这个分组通过网关节点转发给另 一个簇首节点。不断重复这个过程直到分组到达目的节点。因此,每个节点都必须有 其簇首成员的路由表。当一个节点不在任何簇的范围内时或是 2 个或多个簇首节点在 彼此的范围内时, 就产生一个新的簇首节点。 虽然 CGSR 用 DSDV 作为其底层的协议, 但是由于在 CGSR 中寻路是通过簇首节点和网关节点来完成的,所以它比 DSDV 更有 效。此外在 CGSR 中还可以采用启发式的方法如优先级令牌的调度、网关编码调度和 通路预约等来改善其性能。 WRP(Wireless Routingn Protocols)是另一种表驱动路由协议, 在网络中的节点中保 存路由信息。每个节点在路由表中保存的信息如下:距离、路由、链路开销和重传消息 的列表(MRL)。MRL 记录关于消息序列号、重传计数器、每一个邻节点正确应答所需 的标识和更新消息的更新列表等信息。这就使得节点可以决定何时发送更新消息以及 发送给哪个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上 游节点。然后邻节点就修改自己的路由表并试图通过预备的节点建立新的路由。WRP 的优点就是当一个节点试图执行路径计划算法时,可以通过目的节点的上游节点所保 存的信息和邻节点所保存的信息来限制算法,使得算法收敛得更快并避免路由当中的 环路。由于 WRP 需要保存 4 个路由表,所以比大多数的协议需要更大的内存。WRP 还依赖于周期性的 Hello 消息,也要占用带宽。 GSR(Global State Routing)全局状态路由协议,其工作原理与 DSDV 类似,采用链 路状态路由算法,但避免了路由报文的泛洪。它包括一个邻近节点表、网络拓扑表、 下一跳路由表和距离表。当链路的状态发生变化时,通过比较报文与本地路由表中的 信宿路由序列号大小,决定网络拓扑表的修改,若路由表发生变化则广播给其它节点。
12

2010 届通信工程专业毕业设计(论文)

FSR(Fisheye State Routing) 使用了“鱼眼”技术, “鱼眼”技术是 Kleinrock 和 Stevens 提出来的,这种技术可以用来减少表示图形图像的数据。鱼眼能清晰地捕捉焦 点附近的像素,但清晰度随着离焦点的距离增大而降低。 “鱼眼”技术在路由中用来维 护精确的距离和路由质量信息,但也会随着距离的变大而逐渐不精确。FSR 在不同鱼 眼域中的节点以不同的频率(这个频率是由节点距离决定的)只向邻居节点广播链路更 新信息,这能够大大减少链路状态更新信息,从而降低了泛洪的开销。通过节点之间 相互交换链路状态消息,每个 FSR 路由器都能获知网络全局的拓扑信息。根据这些最 新的拓扑信息,FSR 为每个目的节点计算最短路径。由于链路更新频率由距离决定, 因此对于域内的节点路由都是精确的,而对于域外的节点,离目的节点越远,路由的 精确度便越低,这是因为距离较近的更新较快,较远的更新较慢。但不会像按需路由 那样需要花时间去寻找路由,因此能维持较低的延时。而且随着离目的节点越来越近, 路由信息越来越精确,正好弥补了路由的不精确性。在移动网络中,逐渐精确的路由 减小了节点移动对路由精确度的影响。当链路崩溃时,FSR 不会发出任何控制信息, 而且也不包含在下一个更新信息中,而是简单地删除邻居列表和拓扑结构表中的信息, 因此适合于拓扑高度变化的网络环境。目的序列号的使用不仅使得 FSR 能使用最新的 链路状态信息去维护拓扑结构,而且还避免了路由环路的形成,因此较适合高移动性 的无线网络。 HSR(Hierarchical State Routing)是一种用于分级网络的路由协议。 高级的节点保存 它所有子孙节点的位置信息。沿着从最高级的根节点到最低级的叶节点的路径为节点 分配逻辑序列地址。序列地址指示了节点的位置,可以简单地使用序列地址进行寻址。 网络还配备了位置管理服务器来实现物理地址到逻辑序列地址的映射。 ZHLS(Zone based Hierarchical Link State)路由协议是一种基于区域的路由协议。 网 络被分割成不重叠的区域,区域与簇不同,它没有首领。并定义了两级拓扑:节点级和 区域级。节点级拓扑指一个区域内的节点的物理连接。区域级拓扑指各个区域如何互 相连接。网络中存在两种链路状态报文:节点链路状态报文和区域链路状态报文。节点 链路状态报文包含节点的邻居信息,只在区域内传播。区域链路状态报文包含区域间 的链路状态,在全网中传播。通过分区可以减少路由控制报文的个数。

2.4 本章小结
无线传感器网络是一种新型的 Ad hoc 网络,由传感器节点、Sink 节点、Internet 或通信卫星、任务管理节点等部分构成,各传感器节点以自组织形式构成网络,通过
13

张志超: DSDV 路由协议分析与仿真

多跳路由方式将监测数据传到 Sink 节点处理, 最终借助长距离或临时建立的 Sink 链路 将整个区域内的数据传送到远程中心。本章首先介绍了无线传感器网络的定义、特点 以及应用,从中体现出无线传感器网络的研究价值和应用前景。在第二节中主要分析 了一下 WSN 的体系结构和节点的硬件结构,并按网络分层的思想,把无线传感器网络 协议分成物理层、数据链路层、网络层、传输层、应用层五层和能量管理平台、移动 管理平台、任务管理平台三大平台。最后对现有的路由协议进行简单的介绍。

14

2010 届通信工程专业毕业设计(论文)

第 3 章 NS2 仿真软件
3.1 NS2 概述
NS2(Network Simulator )是网络仿真器,为有线和无线网络上的 TCP、路由和多播 等协议的仿真提供了强有力的支持。NS2 是一个开源项目,所有源代码都开放,任何 人可以获得、使用和修改其源代码。正因为此,世界各地的研究人员每天都在扩展和 更新它的功能,为其添加新的协议支持和功能模块。它也是目前网络研究领域应用最 广泛的网络仿真软件之一。 NS2 使用了被称为分裂对象模型的开发机制,采用 C++和 Otcl 两种开发语言进行 开发。他们之间采用 Tclcl 进行自动连接和映射。考虑效率和操作便利的原因,NS2 将 数据通道和控制通道的实现相分离。为了减少分组和事件的处理时间,事件调度器和 数据通道上的基本网络组件对象都使用 C++编写。这样,仿真用户只要通过简单易用 的 Tcl/Otcl 脚本编写出仿真代码,对仿真拓扑、节点、链路等各种部件和参数进行方便 快速的配置。NS2 可以说是 Otcl 的脚本解释器,它包含仿真事件调度器、网络组件对 象库等。事件调度器控制仿真的进程,在适当时间激活事件队列中的当前事件,并执 行该事件。网络组件模拟网络设备或节点的通信,他们通过制定仿真场景和仿真进程, 交换特定的分组来模拟真实网络情况,并将执行情况记录到日志文件(称为 Trace 文件) 中,以提供给仿真用户进分析解读,获取仿真结果。 NS2 的构件库是用两种面向对象的语言编写的:C++和 Otcl。C++是为人所熟知的 高级程序设计语言, Otcl(ObjectTcl) 则是 Tcl 的面向对象的扩展。 Tcl(tool command language)是一种很通用的脚本语言,它几乎在所有的平台上都可以解释运行,功能强 大。它包含了两个部分:一个语言和一个库。 Otcl 则是在 Tcl 中加入了类、实例、继承等面向对象的概念。NS2 中的构件通常都 作为一个 C++类来实现,同时有一个 Otcl 类与之对应。用户通过编写 Otcl 脚本来对这 些对象进行配置、组合,描述模拟过程,最后调用 NS2 完成模拟。NS2 中的构件一般 都是有相互关联的两个类来实现的,一个在 C++,一个在 Otcl 中。这种方式被称为分 裂对象模型。构件的主要功能通常在 C++中实现,Otcl 中的类则主要提供 C++对象面 向用户的接口。用户可以通过 Otcl 来访问对应的 C++对象的成员变量和函数。 NS2 使用这种分裂对象模型,是出于兼顾模拟性能和灵活性两方面的考虑。一方 面,C++是高效的编译执行语言,使用 C++实现功能的模拟,可使模拟过程的执行获
15

张志超: DSDV 路由协议分析与仿真

得较好的性能。另一方面,Otcl 是解释执行的,用 Otcl 进行模拟配置,可以在不必重 新编译的情况下随意修改模拟参数和模拟过程,提高了模拟效率。同时,这种分裂对 象模型增强了构件库的可扩展性和可组合性,用户通常只需要编写 Otcl 脚本就可以把 一些构件组合起来,成为一个“宏对象” 。用户通过 Otcl 进行模拟配置,很多情况下只 需要了解构件的使用和配置接口就可以了,而不需要了解这些构件的功能是如何实现 的。

3.2 NS2 结构
NS2 中含有丰富的构件库,可用于模拟各种通信网络,不仅可以对有线网络中的 协议进行仿真,而且可以对无线网络 WLAN、移动 IP 和卫星通信网络进行模拟。在 NS2 的构件库里包含有典型的有线网络协议 DV,LS 等。NS2.33 版本中还包括了对多 种协议的实现, 这正是 NS2 的优点所在, 可以方便地利用别人所编写的协议进行研究。 NS2 使用了分裂对象模型的开发机制, 采用了 C++和 TCL(Tool Command Language) 两种开发语言进行开发。大部分的网络构件都是用 C++编写的,这是因为用 C++编写 的代码执行速度快, 可以有效快速地操作字节、 包头等数据结构。 模拟场景都是用 OTCL (Object Tcl)语言编写的,能够方便地对网络环境参数、协议参数进行快速地修改和设 置。两种语言通过 TCLCL(Otcl C++ Linkage)机制进行联系,使得利用 OTCL 可以建立 C++对象,修改 C++中的变量以及调用 C++中的函数。在 NS2 中要实现一种新的协议 并进行测试,不仅要用 C++编写协议代码,还要用 TCL 语言编写出相应的测试环境并 建立两种语言的关联。 NS2 采用一个离散时间模拟器(Scheduler)控制整个模拟过程, 其本身有一个虚拟时 钟,所有的模拟都由离散事件驱动。数据包的发送、接收、处理、节点的运动等都是 由 Scheduler 所控制。各事件依照执行的时间顺序加入到 Scheduler 队列中去。在程序 的执行过程中依次从 scheduler 队列中取出并执行。

3.3 C++与 Otcl 的接口
在 NS2 中,调度器(scheduler)是仿真器的心脏,它定义在 C++类 scheduler 中 , scheduler 提供了一套接口去配置仿真器和选择驱动仿真的事件调度类型。用户为了让 自己编写的 C++类能在解释器中可见,需要借助类 TCLclass 的帮助,TCLclass 类可以 实现将解释器中的对象与 NS2 编译类的映射,这样通过创建一个从 TCLclass 继承而 来的静态类,用户就可以在 OTCL 脚本中直接使用 C++类。
16

2010 届通信工程专业毕业设计(论文)

假设用 C++语言创建了一个网络对象类,需要通过 Otcl 来创建一个此对象的一个 实例,这时就需要定义一个从 TclClass 类派生出的接口元素,它生成一个特定名称的 Otcl 对象,使之与 C++类建立一对一的映射,通过 creat 成员函数调用 C++类。例如: 从 Agent 派生出类 MyAgent, 为实现与 OTcl 类的对应, 需定义一个派生自 TclClass 的 MyAgentClass 类,他在 OTcl 类中又一个特定的名称 Agent/MyAgent,通过 creat 成 员函数与 MyAgent 建立联系。 当 NS2 启动的时候,首先执行静态变量 class-my-agent 的构造函数,于是产生实 例 MyAgentClass,在这个过程中,Agent/MyAgent 以及其成员函数均在 OTcl 空间被创 建出来。 用户需要生成该对象的一个实例时, 只需要利用 OTCl 命 new Agent/MyAgent, 仿真器通过静态变量 class-my-agent 调用 create 函数来真正创建一个 MyAgent 对象。 实际试验中常常需要在 Otcl 脚本中改变 C++中的变量值,即让编译层中定义的类 的配置参数在解释层可见。NS2 提供了一种变量绑定的方法来实现这一要求,具体是 将需要在 Otcl 仿真脚本中控制的 C++变量与一个 OTcl 变量绑定, 从而实现 OTcl 与 C++ 之间的双向控制,具体代码如下:
MyAgent : :MyAgent ():Agent (PT-UDP) { bind( “my-var1-otcl”,&my-var1);//变量绑定,实现 OTcl 与 C++之间的双向控制 bind( “my-var2-otcl”,&my-var2); }

my-var1, my-var2 是新添加类 MyAgent 的两个参数变量, my-var1-otcl, my-var2-otcl 则是在 Otcl 语言中为之设置的相应的 OTcl 变量,从而可以通过在 OTcl 脚本中控制 my-var1-otcl,my-var2-otcl 来达到控制 my-var1,my-var2 的目的,使得仿真实验更具 灵活性。需要注意的是,绑定函数在 MyAgent 构造函数中,当创建这个对象时实现对 变量的绑定;同时需要在 ns2/tcl/lib/ns-lib.tcl 文件中对 OTcl 变量赋初值,否则 NS2 平 台会给出警告信息。NS2 支持四种数据类型的绑定,包括实数或整数,带宽变量,时 间变量,布尔值;绑定函数分别如下:
bind() ;//实数或整数 bind-time () ;//时间变量 bind-bw() ;//带宽变量 bind-bool () ;//布尔值

17

张志超: DSDV 路由协议分析与仿真

3.4 Otcl 脚本编写
在使用 NS2 进行模拟前,首先要分析模拟涉及哪个层次。NS2 模拟分两个层次: 一个是基于 Otcl 编程的层次, 利用 NS2 已有的网络元素实现模拟, 无需对 NS2 本身进 行任何修改,只要编写 Otcl 脚本;另一个层次是基于 C++和 Otcl 编程的层次,如果 NS2 中没有所需的网络元素,就需要首先对 NS2 扩展,添加所需要的网络元素。这就 需要利用到分裂对象模型,添加新的 C++类和 Otcl 类,然后再编写 Otcl 脚本。 在本课题中的模拟主要是基于 Otcl 编程的层次,一般来说,编写一个 Tcl 脚本文 件分为以下几个步骤,脚本编写流程图如图 3.1 所示:
开始

配置网络 拓扑结构

建立 协议代理

设置 Trace对象

配置业务量 相关参数

编写辅助过程 设置仿真时间

执行Otcl脚本

分析trace文件 获取有用信息 否 是否需要 重新建模 是 调整配置拓扑结构 和业务量模型

结束

图 3.1 脚本编写流程图

(l) 开始编写 Otcl 脚本。首先配置模拟网络拓扑结构,拓扑结构反映了节点与节 点之间的位置关系,同时还可以确定链路的一些基本特性,如带宽、延迟和丢失策略 等。 (2) 建立协议代理,包括端设备的协议绑定和通信业务量模型的建立。 (3) 配置业务量模型的参数, 从而确定网络上的业务量分布。 设置 Trace 对象。 Trace 对象能够把模拟过程中发生的特定类型的事件全部记录在 trace 文件中。 NS2 通过 trace
18

2010 届通信工程专业毕业设计(论文)

文件来保存整个模拟过程。仿真完成后,我们可以对 trace 文件进行分析研究。使用相 关命令从中提取出重要信息,进行分析。 (4) 编写其它的辅助过程,设定模拟结束时间,至此 Otcl 脚本编写完成。 (5) 用 NS2 解释执行刚才编写的 Otcl 脚本。 (6) 对 trace 文件进行分析,得出有用的数据,可以使用 Gnuplot 或 Xgraph 工具来 绘图直观显示数据变化情况,也可以用 Nam 等工具观看网络模拟运行过程。 (7) 调整配置拓扑结构和业务量模型,重新进行上述模拟过程。

3.5 NS2 仿真流程
使用 NS2 进行网络模拟的基本流程如图 3.2 所示。如果 NS2 中己经包含了在仿真 中 所 要 采 用的协议, 就不需要再编写新的 代码。此时用户的主 要任务就是编 写 TCL/OTCL 模拟代码。通过建立不同的仿真场景,能够对协议在不同网络条件下的性 能进行测试。NS2 中自带了两个工具:setdest 以及 cbrgen。使用 setdest 工具能够方便 地生成节点运动的场景。对无线网络的模拟常常要借助这个工具。通过建立节点运动 的仿真场景,能够比较真实地模拟出无线网络的特点,考察协议适应网络拓扑变化的 能力。 Cbrgen 工具能够建立网络中任意两节点间的 cbr 或 top 数据流,模拟网络中的数 据流量。模拟结束后一般会生成两个文件:.nam 文件以及.tr 文件。其中 NAM 是基于 Tcl/Tk 的动画演示工具, 用来把模拟的过程用可视化的方式呈现出来。 用 NAM 文件能 够动态观察仿真过程,能使用户更加生动直观地了解仿真过程以及网络拓扑变化的情 况。Trace 文件中记录了整个仿真过程,包括包的发送、接收、转发。在无线网络的模 拟中,可以在代理层、路由层、MAC 层等多个层次对仿真过程进行记录。代理层记录 数据包的收发,路由层记录路由信息的处理,MAC 层记录各种信息帧的发送。 trace 文件记录了仿真过程中对每个数据包的处理过程,包括发送、接收、转发、丢弃等, 数据量庞大。要对 trace 文件进行分析必须要借助别的工具从中提取有用的信息,而后 利用 NS2 中提供的 Xgraph 工具或是 Gnuplot 工具作图, 才能够直观地反映出协议的性 能参数。

19

张志超: DSDV 路由协议分析与仿真

仿真开始 分析问题

修改源代码 重新编译NS2



是否需要 修改源代码 否

编译是 否通过 否 调试NS2



编写TCL 执行仿真 分析结果 是否得到 预期结果 仿真结束



分析问题

图 3.2 NS2 的仿真过程

3.6 NS2 相关工具介绍
1. Nam Nam 是基于 Tcl/Tk 的动画演示工具, 用于观察网络模拟的 trace 行为和现

实世界中数据包地 trace 数据。例如网络拓扑、包传输和队列管理等。Nam 的设计理念 是要创造一个动画演示工具,以能够读取大量的动画演示数据集,并能够灵活的扩展, 以适应不同网络环境下的场景可视化要求。 使用 Nam 进行演示的第一步是产生 trace 文件,其中包含了网络的拓扑信息,如 节点、链路以及数据包的 trace 数据。该文件一般由 NS2 创建。生成 trace 文件之后, 就可以用 Nam 进行演示。演示开始时,Nam 会读取 trace 文件,创建网络拓扑,显示 窗口界面,进行必要的布局设置,然后停止在时间标记为 0 的地方。 2. Xgraph Xgraph 是 NS2 中自带的一个小巧的绘图工具, 它可以根据数据文件里 的数据绘制出相应的图形。数据格式文件的格式非常简单,由两栏数据组成,每一行 表示一个点,第一栏为 x 坐标,第二栏为 y 坐标。根据 trace 文件和不同仿真实验中需 要的具体性能参数,编写性能参数提取代码,程序运行后的数据存放在某个文件中, 在 Xgraph 中运行该文件,即可绘制出所需的性能参数图形。

20

2010 届通信工程专业毕业设计(论文)

3.7 本章小结
本章首先对 NS2 仿真软件进行概述, 然后描述了 NS2 的结构组成以及 C++与 Otcl 之间的接口,接着通过流程图分析了 NS2 仿真软件的一般仿真流程,最后简单介绍了 NS2 中常用的实验辅助工具,为实现仿真打下了基础。

21

张志超: DSDV 路由协议分析与仿真

第 4 章 DSDV 路由协议分析
4.1 协议的提出
DSDV(Destination-Sequence Distance-Vector)路由协议是先应式路由协议[11],又称 为表驱动路由协议。在这种路由协议中,每个节点无论当前是否需要通信,都要建立 和维护一张或多张表格,此表格包含到达网络中其他所有节点的路由信息。当检测到 网络拓扑结构发生变化时,节点在网络中发送更新消息。收到更新消息的节点更新自 己的路由表,以维护及时、准确的路由信息。不同的先应式路由协议的区别在于拓扑 更新消息在网络中传播的方式和需要存储的表的类型不同。先应式路由协议不断地检 测网络拓扑和链路质量的变化,根据这些变化更新路由表,因此路由表可以准确地反 映网络的拓扑结构。 DSDV 路由协议是由传统的 Bellman-Ford 路由协议改进得到的,其特点是利用目 的节点序列号解决路由环路和无穷计数问题。在 DSDV 中,每个节点保存一张路由表, 路由表维护本节点到网络内部所有可到达的目的节点的路由信息。路由条目中保存目 的节点的序列号(Sequence Number),用以区别新旧路由。为维护路由表的最新,节点 周期性地广播路由更新分组。邻居节点收到路由更新分组后,节点比较其中的目的节 点序列号和自己路由表中保存的到达同一目的节点的序列号,如果前者大,就更新自 己的路由表;如果路由序列号相同,则选择具有较小跳数的路由。当节点的路由表更 新完成后,为了防止出现波动,节点要延迟一段时间再发送路由更新分组。

4.2 工作原理
目的序列距离矢量路由协议(DSDV)[12]是一种基于表驱动的主动路由协议,通过目 的节点给每个路由设定序列号来区分新旧路由,从而避免了路由环路的产生。 DSDV 采用时间驱动和事件驱动技术控制路由表的传送,即每个移动节点在本地都保留一张 路由表,其中包括所有有效目的节点、路由跳数、目的节点路由序列号等信息。路由 更新分组在全网内周期性地广播而使路由表保持连贯性。每个节点周期性地将本地路 由表传送给邻居节点,或者当其路由表发生变化时,也会将其路由信息传给邻近节点。 当无节点移动时,DSDV 使用间隔较长、包括多个数据单元的大数据分组进行路由更 新;在节点移动时使用较小的数据分组,并且只对移动的节点更新路由,这样降低了
22

2010 届通信工程专业毕业设计(论文)

整体的开销。 4.2.1 路由表的建立、更新和数据转发之间的关系 路由表的建立是在组网阶段进行的操作,在路由表建立这段时间内,并没有路由 表更新和数据转发的参与,因为节点所维持的路由表中还不包括到达网络内部所有可 能到达的目的节点的路由,这样即使有数据转发的参与,也会转发失败。只有当路由 表建立完成后,建立、更新和转发这三个操做都会进行,没有先后顺序,只要有新的 节点加入,就会进行路由表的建立,当拓扑结构发生变化或节点链路状态发生变化, 就会进行路由表的更新,在建立和更新的同时,将伴随着数据的转发。 4.2.2 路由表的建立 组网阶段或有新节点加入时,节点通过广播来告诉其他节点自己的存在,邻居节 点收到这个广播包后就将信息插入到路由表,并立即发送新的路由表,这样,经过一 段时间后,每个节点就可以建立一个完整的路由表,表中包括了到网络内部所有可能 的目的节点的路由。路由表中包含如下信息:目的节点地址、下一跳节点地址、路由 跳数、目的节点的序列号以及路由建立时间、路由稳定时间、稳定数据指针。 4.2.3 路由表的更新 无线传感器网络节点之间主要是传播路由更新分组来更新路由表。每个节点周期 性地在全网广播路由更新分组,把完整的路由信息发送给邻居节点。不管网络拓扑有 没有改变,这种周期性的广播都会发生。除了周期性的广播外,当网络结构发生变化 时,比如链路断开、节点失效或有新的节点加入,都需要立即维护路由,这时各节点 马上广播路由更新分组,邻居节点接到该分组,确认是新的路由信息就将其路由跳数 加 1 后再发送,该过程一直持续,直到每个节点都收到该分组的一个拷贝。对于过期 路由,每个路由表项都有一个序列号。节点广播路由更新分组时,将自己的序列号加 偶数再发出去。邻居节点收到更新分组后,首先来比较一下序列号,如果新分组的序 列号大于路由表中相应目的节点的序列号,则删除旧的信息,添加这条新的信息,如 果相等,就比较路由跳数,选择路由跳数小的,否则,忽略此更新分组,保留原路由 表。 路由更新分组可以采用两种形式。第一种是完全更新(Ful1 Dump),它包含该节点 的所有路由表项, 需要适配多个网络协议数据单元(NPDU),在节点移动速度不高的网
23

张志超: DSDV 路由协议分析与仿真

络中,这种数据包很少被发送。另一种是较小的增量更新数据包,用来转发那些最新 的完全更新后有变化的信息,即两次广播之间,如果有更新信息则用小增量数据包传 送。链路断开时路由表同样需要维护。可以通过两个方面来检测链路中断,一种是通 过硬件检测,另外还可以通过时间推断,即节点在过了一段时间还没收到前一节点的 信息就推断出链路中断,并用跳数为无限大来描述断开的链路。此时,检测出链路断 开的节点后就发一个更新分组,这个信息有一个新的序列号,此序列号是原不可达节 点的序列号加个奇数,跳数为无限大。这会引起路由表的刷新,只有当再次收到丢失 节点的信息后新的路由才会重新建立起来。 4.2.4 数据包的转发 在 DSDV 中,数据包转发时根据路由表选择路由。每个节点的路由表包括了传感 器网中每个其它节点的地址和对应于目的节点的下一跳地址。如图 4.1 所示:节点 1 要 和节点 5 通信,节点 1 查表后得知下一跳为节点 2,就把数据包发给节点 2,节点 2 收 到数据包时先查表,表上显示:目的为节点 5 的下一跳是节点 4,节点 2 就把数据包传 送到节点 4。同理,节点 4 收到数据包后查表,下一跳是节点 5,这样就把数据包送到 了目的节点 5。整个数据包转发过程是:源节点 1 一>节点 2 一>节点 4 一>目的节点 5。

图 4.1 DSDV 中数据包转发过程

4.3 DSDV 相关的关键技术
4.3.1 避免路由环路 DSDV 路由协议是由 Bellman-Ford(DBF)改进得到的,而 DBF 算法会导致路由环
24

2010 届通信工程专业毕业设计(论文)

路的形成。什么是路由环路呢?路由环路形成的基本原因是在分布式条件下,节点可 能会使用一个过期的消息选择路由。 DSDV 协议通过采用序列号机制避免路由环路的形成[13]。考虑一个无线传感器网 络是由 N 个节点形成的,假设系统已处于稳定状态,也就是说所有节点的路由表中的 路由均为最短路径。在这种情况下,到目的节点的下一跳节点引出一棵以目的节点为 根的树。因此,根据网络中所有节点的路由表可构造 N 棵树,每一棵树都以目的节点 为根。以下讨论中,将以目的节点 x 为例来说明由节点 i 和边(i, pix )所确定的有向图 G(x)的变化。其中 pix 是到目的节点 x 的路径中节点 i 的一下跳节点。DSDV 协议保证 在任何情况下,G(x)是无环路的,即 G(x)由一些无交叉的有向树组成。组成 G(x)的树 的根是 x 或是以 NULL 为下一跳的节点。由于节点 x 的任意性,只要说明到达 x 的路 由是无环路的,就可推断:根据 DSDV 的路由表得到的路由在任何条件下都是无环路 的。 从无环路状态开始,每当节点 i 改变下一跳节点时,就可能形成环路。需要考虑两 种情况: (1) 节点 i 探测到它与其下一跳节点间的链路中断时, 节点 i 就将 pix 重置为 NULL。 显然,这种情况下不可能产生包含 i 的环路。 (2) 节点 i 从它的一个邻节点 k 收到一条到 x 的路由,序列号为可 skx ,量度为 m。 考虑是否选择它来替换当前经过 pix 的路由。用 skx 表示存储在节点 i 的序列号的值,d ix 为节点 i 到目的节点 x 的距离量度。根据 DSDV 选择路由的原则,可知只有在下列两 种情况下,节点 i 才选择 k 作为下一跳节点来替换 pix : ① 从邻节点 k 收到的路由有更新的序列号,即 skx < six 。 ② skx = six ,但从邻节点 k 收到的路由到 x 的距离更短,即 m< d ix (若 skx = six ,且 m= d ix 时,不改变原有路由)。 在第①种情况下,节点 i 选 k 作为新的下一跳节点,不可能产生环路,这是因为节 点 i 只有从当前下一跳节点收到序列号 six 后,才将 six 传向其邻节点。因此,存储在下 一跳的序列号的值总是大于或等于存储在节点 i 的序列号,即从节点 i 出发,沿到目的 节点 x 的路径上,存储在所经过的节点的序列号构成一个非减序列。现在假设节点 i 因选择 k 作下一跳而形成环路,这意味着 skx < six ,这与原来的假设 skx > six 矛盾。因此, 节点选择序列号更新的路由是不可能形成环路的。 第②情况下的无环路性质可由 Jaffe[14]和 Moss 定理[3] [15]证明,该定理表明,静态 的或递减的链路加权距离矢量算法总能保持无环路路径。

25

张志超: DSDV 路由协议分析与仿真

4.3.2 减少路由波动 在 DSDV 协议中,在序列号相同的情况下,如果节点收到跳数为 m 的路由后立即 发送更新分组,在随后得到跳数为 n 的路由且 m<n 时,再次发送更新分组,这就会引 起路由表的波动和网络中更新分组的泛滥。 下面以图 4.2 来说明实际网络中路由表波动问题是如何产生的。如图 4-2 所示,假 设移动节点 MH2 有一条路由经 12 跳到达 MH9, 节点 MH6 经 11 跳可到 MH9, 且 MH4 先收到 MH2 发送的路由更新分组,经过 10s 后又收到 MH6 发送的路由更新分组。如 果 MH4 在收到任何新的路由更新分组后就立即更新自己的路由表,并广播更新分组, 则在图 4.2 中所示的情况下,在短短 10s 的时间中,MH4 的路由表就更新两次,并且 在网络中发送了太多的更新分组。当有许多移动节点不规则地发送更新分组,或者移 动节点独立工作,且发射间隔迥然不同时,路由波动问题就经常发生。
MH4

WSN节 点群1

MH2

MH6

WSN节 点群2

MH9

图 4.2 路由波动问题示例

在 DSDV 协议中采取触发更新和稳定时间机制来解决此类问题。当节点收到新的 路由信息时,可分为两种情况:一是链路失败、有新的路由或是路由度量无穷大;二 是调整已存在的路由。对于第一种情况需要立即发送路由更新分组,这就是所谓的触 发更新;而对于第二种情况需要等待一段时间再发送更新分组,等待时间由稳定时间 决定。所谓稳定时间是指第一次收到到此目的节点的路由的时间和收到到此目的节点 的最佳路由的时间的间隔。每个节点都保存目的节点、上次稳定时间、平均稳定时间 信息。对每一个目的节点,平均稳定时间是最近的稳定时间的加权平均值。因为越新 的稳定时间越能反映最新的网络情况,因此,在做加权平均时,最新的稳定时间的权 系数应该是最大的。算法[16]如公式(4.1):

ASTn ?

2ST ? ASTn ?1 3

式(4.1)

式中, ASTn?1 表示上次的平均稳定时间;
26

2010 届通信工程专业毕业设计(论文)

ST 表示最新的稳定时间;

ASn T表示这次的平均稳定时间。
为了避免波动,节点可以等待两倍的平均稳定时间后才发送更新分组。但为了尽 快对拓扑变化作出响应,等待时间不能太长,因此需设置等待时间最大值。任何等待 时间已超过最大值的路由就可以认为是稳定的,如果该路由被修改过,则当路由稳定 后需要发送更新分组。 4.3.3 定时器 在 DSDV 协议中,有三种重要的定时器:路由条目生存时间定时器、周期广播定 时器与稳定时间相关的定时器。 在路由表中,每个路由条目都有相应的生存时间,如果在生存时间内该条目未被 更新就删除,并认为与此路由相关的下一跳节点不可达,那么路由表条目每一次更新 后就把该定时器归零。每个节点有周期广播定时器,在接收到来自邻节点的路由更新 分组时,并不马上转发,而是等到周期广播定时器超时才转发(在触发更新时,不需要 等待)。在节点中,还有用于计算稳定时间的计时器。 DSDV 协议中,网络中的每个节点以同样的周期广播控制分组。如果所有节点在 同一时间发送控制分组,就会引起控制包的冲突和网络拥塞。为了防止节点同步发送 控制分组,每个节点在发送更新分组前,可以随机地延迟一段时间再发送。 4.3.4 序列号机制 DSDV 协议采用了序列号机制避免了路由环路问题。在网络中,每个目的节点都 维护自己的序列号。当节点的邻列表变化时,就将本节点的序列号增加 2,节点维护的 序列号总是偶数。路由表条目中也保存序列号,当节点检测出链路断开时发送一个更 新分组, 该分组中有一个新的序列号, 此序列号是在原不可达节点的序列号基础上加 1。 当网络拓扑结构发生改变时,为防止节点和邻居节点产生的序列号冲突,节点总是产 生偶数号码给自己,而邻居节点总是产生奇数号码。

4.4 本章小结
本章第一节着重介绍了 DSDV 路由协议的工作原理和运动机制,并通过实例阐述 了 DSDV 路由协议的数据包转发过程。DSDV 路由协议是一种基于表驱动的主动路由
27

张志超: DSDV 路由协议分析与仿真

协议,以路由表的跳数作为路由选择方式,以序列号来维护路由更新分组,以路由定 时器来控制传送路由更新分组,是一种典型的以时间驱动和事件驱动来控制路由更新 的路由协议。第二节从理论上对 DSDV 如何通过序列号机制避免路由环路作了证明, 接着对 DSDV 如何通过时间驱动机制来解决路由波动作了详细的阐述。DSDV 路由协 议能迅速为节点建立路由并发送数据,随着网络拓扑结构和链路状态的变化,能准确 反映网络拓扑变化信息。

28

2010 届通信工程专业毕业设计(论文)

第 5 章 DSDV 路由仿真
5.1 总体设计
在开始设计时,将 DSDV 路由协议的实现分为路由表的建立模块、路由表的更新 模块和数据包转发模块三大模块。每个大的模块又由多个函数相互调用来共同完成其 功能,最后通过各个模块之间的相互协调和调用,共同来实现对 DSDV 路由协议的仿 真。 1. 路由表的建立模块 路 由 表 的 建立 模 块 主要 完 成 网 络中 所 有 节点 路 由 表 的建 立 。 每个 节 点 通 过 rtable_ent 这个类给自己建立一张表,表中包含的信息为:目的节点地址、下一跳节点 地址、路由跳数、目的节点的序列号。表格建立完成后,节点就开始进行周期性广播, 告诉邻居节点自己的有关信息,当邻居节点收到广播后,从分组中提取出各字段,然 后更新自己的路由表,更新完成后立即进行广播,向邻居节点告知自己的路由表信息, 这个动作一直持续下去,直到网络中所有节点的路由表建立完成,该时间长短因节点 数量和网络范围的不同而不一致。在路由表的建立过程中,路由表的更新、数据包的 转发等操作也同时发生,接下来将在下面对这些进行详细说明。 2. 路由表的更新模块 路由表的更新模块主要负责对节点路由表的维护,其更新分组有两种方式:一种 是完全更新,即更新路由表的所有信息,主要适用于节点移动比较频繁的网络中;另 一种是增长更新,只对路由表中发生变化的那些路由条目信息进行更新,适用于节点 移动较少的网络中。这个模块的功能主要由 updateRoute()函数来实现,更新过程大致 为,节点首先判断自从前次接收到邻居节点的广播后,在一个周期内是否再次接收到 来自该邻居节点的信息,如果没有收到,就将路由表中到达该节点的跳数设置为∞,并 将序列号加 1,然后立即进行广播,告知网络中的其它节点。当在一个周期内接收到广 播分组,先和自己路由表进行比较,当自己路由表中没有该节点信息时,就认为是新 的节点加入到网络,更新自己路由表,立即广播;当路由表中有该节点信息,就比较 新旧路由,保留序列号大的路由,丢弃序列号小的路由,当序列号相同时,保留跳数 小的,丢弃跳数大的,更新完自己路由表后,为了避免更新过于频繁,引起路由波动, 节点可以等待两倍的平均稳定时间后才发送更新分组,平均稳定时间的确定在前文中 已经介绍过,这里不在赘述。但为了尽快对拓扑变化作出响应,等待时间不能太长,
29

张志超: DSDV 路由协议分析与仿真

因此需设置等待时间最大值。任何等待时间已超过最大值的路由就可以认为是稳定的, 则需要发送更新分组。下面通过流程图 5.1 来直观的对路由表的更新进行说明。
网络初始化 完成后 是 是否为新 加入节点

一个周期内是 否接收到广播

否 将跳数设置为∞ 序列号加1 更新自己的路由表 否 是 和自己路由表 信息做比较

调用函数 sendOutBCastPkt() 立即广播

序列号是 否相同 是



新路由序列号是否 大于原路由序列号



丢弃



新路由跳数是否 大于原路由跳数

是 丢弃

否 调用函数 updateRoute() 更新自己的路由表 等待一段时间

图 5.1 路由表更新流程

3. 数据包转发模块 数据包转发模块主要负责对数据包的接收和发送,同时也负责对数据包的简单加 工处理。当节点收到分组后,通过分析包头文件,首先判断是否由自己生成的,不是 则通过比较端口号和 IP 地址,判断该分组是邻居节点发送的广播分组,还是 cbr 数据 流,当确定是广播分组后,就跳转至路由表更新模块,进行路由表更新,更新完成后 立即进行广播,将新的路由表信息告知自己的邻居节点,从而实现对网络中所有节点 路由表的更新,这个过程在路由表的更新模块中已经详细介绍了,在这个模块中不再 赘述;如果是 cbr 数据分组,从数据分组中提取出该分组要到达的目的节点号,和自己 节点号进行比较,若目的节点号是自己本身,接收该分组,不再进行转发,若目的节 点号不是自己,首先查找自己维持的路由表,找出到达目的节点相对应的下一跳地址, 然后调用 forwardPacket ()这个函数来转发该数据分组,当下一跳接收到该分组后,进 行同样的操作,直到该分组到达目的节点。 4. 整体流程图 DSDV 路由协议仿真的实现过程大致为,在仿真开始后,首先进行网络初始化, 主要完成路由表的建立,待初始化完成后,当网络结构发生变化,例如发现到达某个
30

2010 届通信工程专业毕业设计(论文)

邻居节点链路断开、接收到邻居新的广播分组以及接收到数据分组后,从中提取出相 关信息,进行一系列的判断,判断后调用相应的函数,进行相应的操作,最终实现网 络中所有节点路由表信息的最新和实现数据的转发。最后,为了将各个模块之间的调 用关系更直观的表达出来,通过画出整体流程图来进行说明,如图 5.2 所示。
command () startUp() 网络初始化

recv ()



是否为 广播分组 是

查看路由表 获取转发地址

processUpdate()

forwardPacket()

调用函数 updateRoute() 更新路由表

sendOutBCastPkt()

图 5.2 DSDV 函数之间的关系

流程图中command ()函数通过接收到前台传递过来的参数,开启仿真;startUp()主 要来建立路由表,完成网络的初始化;recv ()函数用于节点接收来自网络中其它节点的 分组;forwardPacket()用来完成数据包的转发;processUpdate ()主要用于从接收到的广 播分组中提取出相关信息, 来判断是否要更新自己的路由表;updateRoute()函数来完成 路由表的更新, 然后通过sendOutBCastPkt()函数向邻居节点发送广播分组, 以保证整个 网络中路由信息的最新。

31

张志超: DSDV 路由协议分析与仿真

5.2 DSDV 路由仿真实现
5.2.1 仿真场景设置 本节首先通过文字,然后画出流程图,来对 DSDV 路由仿真的整个过程进行详细 描述。为了清晰的分析 DSDV 路由协议,尽量使网络拓扑结构简单化,对最简单的仿 真场景进行测试。 首先对仿真场景的相关设置进行说明,在 1000 米×1000 米的区域内随即分配 10 个节点,分别标识为 0、1、2……9,构成一个多跳的网络拓扑。为了能够直观的通过 仿真过程中的 nam 动画和生成的 trace 文件对整个仿真过程进行分析, 在整个网络拓扑 结构中只设置一条链路,即源节点和目的节点都只有一个,其他节点作为中间转发节 点,并且网络中的所有节点不移动。在本次仿真实现过程中,将节点 0 设置为源节点, 节点 5 设置为目的节点。每个节点的传输半径为 250m,整个仿真过程的时间为 300s。 新建文件夹来存放 nam 动画演示数据和 trace 数据。接下来介绍数据流的设置,在具体 实现中, cbr 数据流的相关信息在 dsdv.tcl 脚本中进行设置。 新建一个包大小为 1500bytes 的 UDP Agent 并把它绑定到 0 节点上,并将其上层应用类型设置为 CBR 应用,其包大 小为 1000bytes、速率为 0.2Mb,在 20s 是开始传送数据,290s 时结束。同时,在接收 端即节点 5 上新建一个 Null Agent, Null 是一种数据接收器(traffic sink)。 最后, 将 udp_(1) 和 null(1)这两个 Agent 连接起来,就完成了节点 0 到达节点 5 之间链路的设置。本文 在图 5.3 中用流程图的形式直观的分析了 dsdv.tcl 脚本。
仿真开始很短 时间后,所有 节点开始广播 20s后开始发送 CBR业务 290s时停止发 送CBR业务

绑定在 udp_(1)上

将udp_(1)和 Null连接起来

新建null

绑定在0号 节点上
图 5.3 dsdv.tcl 脚本流程图

绑定在5号 节点上

32

2010 届通信工程专业毕业设计(论文)

5.2.2 仿真结果及分析 Tcl 脚本编写完成后, 打开 NS2 仿真软件, 首先输入命令语句进入存放脚本的目录, 然后输入:ns dsdv.tcl 命令,则出现图 5.4 所显示的界面,从界面输出的内容可以读取 出一些信息:第 1 行是命令语句,第 2 行中显示网络中共有 10 个节点,在第 5 行中显 示出了无线电载波监听数值的大小,在仿真开始进行初始化时 distCST_的数值已经计 算过了,而且 distCST_的数值在整个仿真过程只在初始化的时候计算一次,这里只是 输出而已。

图 5.4 运行界面

下面可以通过 nam 工具查看节点广播消息、建立路由等。在编写脚本语言时,设 置在 20s 时绑定在应用层的 CBR 数据流开始传输,在仿真开始一段时间内,用于网络 中所有节点建立路由,每个节点周期性向其邻居广播其路由表,完成网络的初始化工 作,完成后,每个节点维持的路由表中就含有到达网络中其他节点的路径,网络初始 化中节点广播由 sendOutBCastPkt()这个函数来实现,然后邻居节点收到广播后,通过 void updateRoute()这个函数来实现自己路由表的更新。为了说明这个过程,图 5.5 所显 示的是从 nam 仿真动画中截取一个片段,从图中可以清楚看到,节点 8 在这个时刻正 在向其邻居广播其路由信息。

33

张志超: DSDV 路由协议分析与仿真

图 5.5 节点正在广播

经过一段时间后,完成网络初始化,网络中每个节点的路由表都包含可能到达的 网络中其他节点的路径,然后就开始传输数据,在数据传输过程中,当节点收到邻居 节点发送的数据分组后,对数据进行分析,判断该分组是否是发给自己的,如果不是, 就从数据包中找出该信息要到达的目的节点,然后查询自己的路由表,确定到达该目 的地的最短路径, 然后进行转发。 图 5.6 显示的就是一个节点从邻居节点收到目的节点 不是自己的分组,正在转发的过程。

图 5.6 数据转发

现在将拓扑结构中所有节点的位置在坐标轴中标注出来,可以通过节点与节点之 间的位置关系,来直观地确定哪两个节点互为邻居节点,从而方便接下来对仿真过程 中生成的 trace 文件的分析,节点位置信息如图 5.7 所示:
34

2010 届通信工程专业毕业设计(论文)

图 5.7 节点位置信息

虽然通过 nam 动画可以看出节点正在向邻居节点广播信息,然而这只是动态地、 粗略地描述了仿真过程,并不能看到节点之间转发数据的具体过程,因此通过对仿真 过程中生成的 trace 文件进行分析,该文件中详细记录了仿真过程中数据的传输和转发 情况,它是分析协议运行的重要依据。由于 trace 的数据较庞大,针对 DSDV 路由的原 理,从 trace 提取相关的数据然后进行分析说明。 图 5.8 就是从仿真中生成的 trace 文件中提取出来的一小部分数据,为了方便进一 步对 trace 文件中的数据进行分析,首先从图中提取出一行数据,来对 trace 的格式进 行说明。 从图 5.8 中提取出第 3 行数据,对其中的有用字段进行分析: 1 2 3 4 5 6 7 8

s 0.034809998 _2_ RTR --- 1 message 32 [0 0 0 0] ------- [2:255 -1:255 32 0] (1) 第 1 个字段是封包事件发生的原因。s:传送;r:接收;d:丢弃;f:转发。 (2) 第 2 个字段是事件发生的时间。 (3) 第 3 个字段是事件发生的节点 ID。 (4) 第 4 个字段是说明这是发生在哪一层的事件。RTR:路由层;AGT:应用层; MAC:媒体存取层。 (5) 第 5 个字段是封包的类型。 (6) 第 6 个字段是封包的大小。 (7) 第 7 个字段是来源节点地址(NodeID:PortNumber)。 (8) 第 8 个字段是目的节点地址(NodeID:PortNumber)。
35

张志超: DSDV 路由协议分析与仿真

通过上面对 trace 格式的简单介绍后, 然后对图 5.8 中数据的意义就很容易理解了, 图中显示的数据是在仿真开始很短时间后,网络中的节点开始通过广播告知邻居节点 自己的存在,开始建立路由表的过程。第 1 行显示在仿真开始 0.003769945s 后节点 0 开始发送广播,其广播封包大小为 32 字节,类型为 message。第 2 行显示节点 1 接收 到来自节点 0 的广播,由此可以得出,节点 1 是节点 0 的邻居节点,跳数为 1 跳,对 照拓扑结构图发现正好符合。同样 6、7、8、9、10 行表示节点 3 发送广播,节点 9、8、 7、2 收到广播,也可得出节点 3 分别与它们为邻居,将理论分析的结果与图 5.7 中标 注的节点位置信息进行比较,结果完全符合。

图 5.8 节点开始广播的 trace 文件

在仿真场景设置时,我们将节点 0 作为源节点,在其上绑定了 UDP Agent,并添 加了 CBR 应用; 将节点 5 作为目的节点, 在其上建立了 Null Agent, 最后将 UDP Agent 和 Null Agent 连接起来,来实现源节点 0 到目的节点 5 之间的数据传输。虽然从 nam 动画可以看到数据传输的链路情况,该链路与理论上的链路相符合。但是为了进一步 说明数据在传输过程中的链路情况,在此从 trace 文件中截取一段数据,来对 cbr 数据 流的传输和转发过程中发生的动作进行分析,如 5.9 所示。 结合上面介绍的 trace 文件的相关格式进行分析, 第 9645 行显示 0 号节点在 88.08s 时刻产生了一个大小为 1020 字节、 分组类型为 cbr 的数据分组, 其目的为节点 5, trace 的类型是 RTR,表示该事件发生在网络层。该分组正是我们要在节点之间转发的 CBR 业务,也就是我们在节点 0 上绑定的 cbr 数据流。9647 和 9648 行,表示分组,节点 1 接收到来自节点 0 的信息并进行转发,从后面的参数中可以获知,该信息所要到达的 目的节点为节点 5,到达目的节点的下一跳为节点 4,节点 0 期望节点 1 在无线信道上 发送该该分组的时间值为 13a(16 进制数)。接下来的几行数据表示,节点 4 收到信息后 转发给 9, 节点 9 然后转发给节点 5, 当节点 5 发现该信息是发给自己的, 将不再转发, 这样,cbr 数据流从节点 0 到节点 5 的路由路径就为:0-1-4-6-5。为了更加直观的看出 cbr 数据流的转发过程,我们通过坐标系的方式来表示出 cbr 数据流节点 0 到达节点 5
36

2010 届通信工程专业毕业设计(论文)

的完整链路,如图 5.10 所示。

图 5.9 CBR 数据流的 trace 文件

然而,对图 5.9 中的数据进一步分析,就会发现,在 cbr 数据流从源节点 0 经过中 间节点 1、4 和 9 的转发后,最终到达目的节点 5 的过程中,节点 6 发送了一条广播分 组,也就是图 5.9 中 9646 行所显示的数据。然后结合上文对 DSDV 中路由表的更新原 理的介绍,就很容易解释这行数据所要完成的功能,这行数据的产生就是表示节点 6 在更新自己的路由表后,然后立即通过发送广播分组,告知网络中其它节点自己的信 息,从而实现网络中所有节点路由表的最新。

图 5.10 完整的链路

37

张志超: DSDV 路由协议分析与仿真

第 6 章 总结与展望
作为新兴的测控网络技术的无线传感器网络,是一个能够自主实现数据采集、融 合和传输应用的智能网络应用系统,它将逻辑上的信息世界与真实的物理世界紧密结 合,从而真正实现“无处不在的计算”模式。无线传感器网络是一门综合性学科,它 集成了传感器、计算机和网络三大技术,被认为是二十一世纪最能影响人类发展的关 键技术之一。无线传感器网络能够获取客观物理信息,应用前景十分广阔,已经被应 用于军事国防、工农业控制、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐、 危险区域远程控制等诸多领域。在无线传感器网络的各项研究中,路由技术是无线传 感器网络的关键技术之一,与传统网络的路由技术相比存在很大差距,目前路由技术 的研究己成为无线传感器网络的热点问题。

6.1 工作总结
本文首先介绍了无线传感器网络概念、特点及应用,然后引入了无线传感器网络 路由,并简单介绍了无线传感器网络现有的路由协议。对 NS2 仿真软件进行学习,了 解其内部结构,并在此基础上实现了一种基于路由表驱动的路由协议的仿真。工作总 结如下: (1) 学习 NS2 仿真软件,了解了内部结构、前后台的连接以及仿真的一般流程。 (2) 分析目的序列距离矢量路由协议(DSDV)。主要分析了 DSDV 路由协议的工作 原理和运行机制,以及 DSDV 路由协议的数据包转发过程,并从理论上证明了 DSDV 无路由环路及如何解决路由波动问题。 (3) 利用 NS2 仿真软件实现了目的序列距离矢量路由协议(DSDV)的仿真。并对仿 真结果进行分析,更加深刻地理解了 DSDV 路由协议的工作原理和运行机制。

6.2 未来展望
由于 DSDV 路由协议最初应用与 Ad Hoc 网络中,而 Ad Hoc 网络和 WSN 网络又 有很大的区别,同时考虑到 DSDV 协议本身的特点,仍然需要进一步的研究,以后的 研究工作有: (1) DSDV 路由协议随着网络节点增加,路由表容量也相应增加,因此,如何解决
38

2010 届通信工程专业毕业设计(论文)

路由表容量不断增加的问题是今后工作的重点。 (2) DSDV 路由最初用于移动 Ad hoc 网络中, 不需要考虑能耗问题, 将其用于 WSN 中,没有能量来源,能耗问题是今后的一个研究方向。 (3) 在小范围内,DSDV 路由协议的通信能力较强,然而在大的范围内,通信能力 将受到限制,因此提高 DSDV 路由协议在大范围内的通信能力也是未来研究的方面。

39

张志超: DSDV 路由协议分析与仿真





本课题研究是在我的导师许登元老师的亲切关怀和悉心指导下完成的。他渊博的 专业知识、严肃的科学态度,严谨的治学精神,精益求精的工作作风,深深地感染和 激励着我。三个多月以来,许老师能够一直关注我的论文的进展情况并随时对设计过 程中存在的问题进行指导;在论文的写作过程中,许老师在研究方向的选择、论文提 纲、写作思路、文章组织等方面给我很多建议,让我能够顺利地完成整篇论文的写作。 许老师不仅在学业上给我精心指导,同时还在思想、生活上给我以无微不至的关怀, 在此谨向恩师致以诚挚的感谢和崇高的敬意。 感谢母校,她给我提供了一个良好的学习环境,在这里我度过了人生最美好的时 光;感谢所有的任课老师,传授给我丰富的知识和宝贵的人生经验;感谢我的朋友, 他们对我的生活和学习给予了无微不至的关怀、支持和帮助,激励我永远不断进取。 在此,向他们表示我最衷心、最真诚的谢意。 最后,我要感谢我的父母,亲戚,他们多年来无私的关爱和奉献,让我在漫长的 求学道路上不感到孤单,让我在拼搏和奋斗的历程中不感到疲倦,他们永远是我的骄 傲。

40

2010 届通信工程专业毕业设计(论文)

参考文献
[1] Thn emerging technologies that will change the world.Technology Review. Feb.2003 VOI.1,Nol,p22-49.httP:www.techreview.com/articles/emerging0203.asp [2] 于海斌,曾鹏,梁韦华.智能无线传感器网络[M].北京:科学出版社 2005 [3] Estrin D,Govindan R,Heidemann J ,et al.. Next century challenges: Scalable Coordination in Sensor Network[J].In: Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking. Seattle: IEEE Computer Society, 1999,263~270. [4] 李晓维.无线传感器网络技术.北京:北京理工大学出版社,2007. [5] 于宏毅,李鸥,张效义.无线传感器网络理论、技术与实现.北京:国防工业出版 社,2008. [6] 孙利民,李建中,陈渝,朱红松.无线传感器网络[M].北京:清华大学 [7] Edgar H.Callaway Wireless Sensor Networks: Architectures and Protocols[M].CRCPress 2004 21~35. [8] L.Hester,Huang,O.Andric,A.Allen,P.Chen.A Self-Origanizing Wireless Network Computer Communication and Networks[J],IEEE,2002,364 一 369 [9] Akyildiz I..F , Su W , Sankarasubramaniam Y , Cayirei E.A survey on sensor networks[J]. IEEE Communjciations Magazine,2002,40(8):102-114 [10] L. Akyildiz,W. Su,Y. Sankarasubramaniam,and E.Cayirci,A Survey on Sensor Networks[J].IEEE Communications Magazine,Vol.40,No.8,2002.102-114 [11] 王坤 Ad Hoc 网络路由协议的研究[A] 山东大学硕士学位论文 2005. [12] Charles E , Perkins , Pravin Bhagwat. Highly Dynamie De-stination-Sequenced Distance-Vector Routing for Mobile Computer[A].In Proceedings of the SIGCOMM’ 94 Conference on Communications Architecture,Protocols and Application,1994.8. [13] 孙晓艳,李建东,张光辉,田红涛 Ad Hoc 中的常用路由算法分析[J] 现代电子 技术 2003 VOL13(156)18-21 [14] Kemal Akkaya, Murat Demirbas, R.Savas Aygun The impact of data aggregation onthe Performance of wireless sensor networks[J] RELESS COMMUNICATIONS AND MOBILE COMPUTING DOI:10.1002 [15] CHEN Chao,ZHENG Bao-yu,ZHAO Xian-jing The researeh of cooperative routing
41

张志超: DSDV 路由协议分析与仿真

Algorithm in mobile Ad hoc networks[J]. THE JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOMMUNICATIONS. Volume 13,Issue3, September 2006 [16] Sunjoon Ahn,A.Udaya Shankar. Adapting to route-demand and mobility in ad hoc Network routing[J].Computer Networks 38(2002)745-764

42



相关文章:
AODV路由协议的仿真与性能分析论文_图文
AODV路由协议仿真与性能分析论文 - AODV 路由协议仿真与性能分析 摘要:首先,本文简单介绍了无线自组网和无线局域网的一些知识,对其主要 内容做了概述性的讲解。...
Ad Hoc网络路由协议的研究
(1) DSDV DSDV(Destination-sequenced Distance-vector)是最早的自组网路由协议。...基于OPNET的Ad Hoc网络建模与仿真.计算机工程.2009年1 月, pp.4~6 [4]Ram...
ad hoc网络路由协议性能比较综述
网络协议的性能进行比较分析。基于 Ad Hoc 网络的网络环境,对 AODV 路由协议进行详细分析,并通过网络仿真软件 NS-2 比较、分析了 AODV、DSDV、DSR 路由协议在端...
路由协议-dsdv
# number of mobilenodes DSDV ;# routing protocol 500 ;# X dimension of ...DSDV路由协议分析与仿真 暂无评价 50页 ¥10.00 DSDV路由协议的性能优化.....
DSDV
主动路由协议 4.4 主动路由协议 DSDV 主动路由协议主动路由协议 DSDV (Destination...DSDV路由协议分析与仿真 50页 5下载券 喜欢此文档的还喜欢 dsdv协议 5页 免费...
dsdv协议
并且能源受限,要求路 由协议尽量简单,这又增加了 Ad hoc 网络中路由协议设计的...DSDV路由协议分析与仿真 暂无评价 50页 ¥10.00 路由协议-dsdv 3页 1下载...
DSR协议是最早采用按需路由思想的路由协议
DSR协议是最早采用按需路由思想的路由协议_互联网_IT...AODV 协议 AODV协议是在DSDV 协议基础上结合类似DSR...2014教师资格材料分析辅... 2014小学教师资格考试《...
关于DSDV的知识
关于DSDV的知识 - 随着Ad-Hoc网络的不断发展,在.Ad-Hoc 网络 上传送不同类型的业务的需求日益增加,对路由协 议的要求也越来越高。把传统的路由协议和多路径 ...
无线自组织网络路由协议概述
7.IERP(theInterzoneRoutingProtocol)区域间路由协议。 8.IARP(theIntrazoneRoutingProtocol)区域内路由协议。 9.DSDV(DestinationSequencedDistanceVector)目标序列距离...
无线网状网络的路由协议研究
接着着重介绍 WMN 路 由协议。最后本文详细介绍分析一种适用于无线网状接入网的...(Table Driven)路由,或者预先式(Proactive)路由,如 DSDV(Dynamic Destination-...
更多相关标签: