典型AdHoc网络路由协议的仿真与分析

DSR路由协议中 ,路由寻找机制和维护机制完 全是按需操作的 ,不存在某种周期性分组. 当所有节 点的相互关系可以近似为静态 ,并且当前通信所需 的所有路由已经全部被找到的时候 ,这种按需操作 产生的开销数量成比例地下降 ,甚至最终为零.
A d Hoc按需距离矢量路由协议 [ 3 ] (AODV ) 吸 收了 DSR 协议按需特性 ,具有与之相类似的路由发 现过程 ,不同之处是具有传统的路由表项 ,是 DSDV 的一种改进. AODV 通过按需产生路由减少了广播 的次数 ,不像 DSDV 那样维护所有的路由.
Abstract:Ad Hoc network is a self2organized network which is formed dynam ically and temporarily by mobile nodes w ithout need of any infrastructure or centralized adm inistration. Until now, a num ber of routing p rotocols have been realized, for examp le, Destination2Sequenced D istance2Vector (DSDV ) , Dynam ic Source Routing (DSR ) , Ad Hoc On2Demand D istance Vector Routing (AODV ) , and so on. In the paper, first we introduce these three p roto2 cols. Then three important performance indexes are sim ulated w ith NS2: packet delivery rate, average end2to2end delay of data packets, normalized routing load. Finally we give an interp retation to simulation results. Keywords: Ad Hoc; routing p rotocol; simulation; NS2
作者简介 :魏 凯 (19812) ,男 ,硕士研究生 ,主要研究方向 : Ad Hoc网络 , E2mail: weikai@ hrbeu. edu. cn.
第 1期
魏 凯 ,等 :典型 Ad Hoc网络路由协议的仿真与分析
·13·
1. 1 表驱动路由 表驱动路由协议也叫先应式路由 ,它试图维护
复等场合.
driven p rotocols) 和 按 需 路 由 协 议 ( source2initiated
由于 Ad Hoc网络的多跳共享广播特性 ,网络拓 on2demand p rotocols).
收稿日期 : 2007206227. 基金项目 :黑龙江省自然科学基金资助项目 (AF200611).
网络中从各个节点到其他节点的最新路由信息 ;与 何时需要路由 ,以及需要的路由的频次无关 ,每个节 点维护一个或者多个路由表 ,当网络拓扑变化时 ,广 播更新信息传遍整个网络 ,以维护一致的网络视图. 表驱动路由协议的一种典型协议是 DSDV[ 1 ].
DSDV 协议是在 Bellman2Ford 路由算法基础上 进行改进设计的 ,它能保证无环路由. 在 DSDV 中 , 每个节点要维护它所能到达的所有目的节点的路由 表 ,其中列出了所有可能到达的目的节点 、到达目的 节点的跳数 、分配的序列号. DSDV 采用时间驱动和 事件驱动结合控制路由表更新的传送 ,每个节点周 期性地将路由更新信息传送给相邻节点 ;或者当其 路由表发生变化时 ,也会将路由更新信息传给相邻 节点.
(哈尔滨工程大学 信息与通信工程学院 ,黑龙江 哈尔滨 150001)
摘 要 :移动 Ad Hoc网络是移动节点动态临时组建的自组织的网络 ,它不需要任何基础设施 ,相距较远的节点 间的通信需要中间节点的转发. 目前已经实现了多种网络协议 ,目的序列距离矢量路由 (DSDV ) 、源动态路由 (DSR) 、Ad Hoc按需距离矢量路由 (AODV )等. 首先介绍了 DSDV、DSR、AODV 3种路由协议 ,并用 NS2 (网络模 拟器 )对它们的网络性能指标端到端时延 、数据包传送率和路由开销性能进行了仿真 ,并对实验结果进行了分 析说明. 关键词 : Ad Hoc;路由协议 ;仿真 , NS2 中图分类号 : TP391. 9 文献标识码 : A
图 1 仿真步骤流程图
阐述节点的配置和场景的建立 ,仿真结果数据 的处理可以使用多种程序语言进行 ,不再详述. 实验 中使用一个 node2config配置函数配置移动节点. 配 置的选项包括 : adhoc 路由协议 、协议栈 、通道 、拓 扑 、传输模型以及是否打开有线路由 (如果需要有 线 - 无线场景 ) ,是否打开各层的 trace ( router, mac, agent)等. 实验中使用的仿真参数见表 1.
第 35卷第 1期 2008年 1月
应
用
科
技
App lied Science and Technology
文章编号 : 1009 - 671X (2008) 01 - 0012 - 05
Vol. 35, №. 1 Jan. 2008
典型 Ad Hoc网络路由协议的仿真与分析
魏 凯 ,姜 弢 ,李 明
该条源路由转发该分组至目的节点 D 的多跳转发 序列. 通常情况下 ,源节点通过搜索其自己的路由存 储器 ( route cache)就能够找到一条合适的源路由 , 路由存储器用于存储以前获得的路由 ;但是如果源 节点 S 在自己的路由存储器里没有找到以前获得的 路由 ,源节点 S 将初始化一个路由寻找协议 ,动态地 寻找一条新路由到达目的节点 D.
随着网络技术和无线通信技术的融合 ,移动无 扑不断变化 ,使得传统的路由协议不再适用. 同时
线网络成为一门新兴的热门技术. 当前 ,移动无线网 Ad Hoc网络协议还需要考虑无线环境的低带宽和
络可以分为 2大类 :需要固定基础设施支持的网络 高误码率特性 ,需要专门设计 Ad Hoc网络的路由协
路由发现是通过泛洪 ( flood)实现的. 节点 S 按 照一个单独本地广播方式发送一个路由请求 ( route request) ,每个收到 RREQ 的节点重复广播 ,直到达 到目的节点 S或者路由存储器里含有到达目的节点 S路由的节点 , 然后 此节 点将 产生 一个 路由应 答 ( route request)按照反路径回送到源节点 S. 自此 , 源节点 S 通过 RREQ 建立一条到达目的节点的路 径 ,路径也被储存 ,以备将来使用. 路由维护过程是 : 在使用源路由发送分组的时候 ห้องสมุดไป่ตู้每个节点都需要证 实数据分组能够通过本节点到达该条源路由下一跳 节点的链. 如果路由损坏 ,上游节点将发送一个路由 错误分组 ( RERR )通知源节点 ,源节点将从它的储 存中删除这条路由 ,初始化一个新的路由发现过程 到达目的节点 (如果仍然需要这条路由的话 ).
·14·
应 用 科 技 第 35卷
链路断开了 ,就会给其上游节点发送一个链路断开 的通知 ,这样直到源节点 ,如果需要源 ,则重新启动 路由发现过程.
因为 DSR中每个包携带完整的路由信息 ,而在 AODV 中仅携带目的地址 ,这意味着 AODV 比 DSR 的路由开销要少. 并且 DSR 中路由回答包携带路由 中每个节点的地址 ,而在 AODV 中路由回答包携带 目的 IP地址和序列号. AODV 的优点使它能适应高 度动态的网络.
2 N S2 仿真实验
NS2 是 一 个 离 散 型 事 件 驱 动 的 网 络 仿 真 软 件 [ 4 - 5 ] ,能够执行多种网络协议 ,提供多种数据源 , 实现多种队列算法等 [ 6 ]. 使用添加了 CMU 无线模 块的 NS2来进行本次实验. 仿真的步骤 [ 6 ]是定义网 络参数 ,生成仿真对象 ,生成仿真场景 ,包括运动场 景和流量场景 ,仿真完成生成 trace文件及 nam 动画 演示 ,流程如图 1所示.
它的路由发现过程是 :节点发送信息时 ,先在路 由表中查找路由 ,有则按照路由发送信息 ,没有则进 行路由发现过程. 节点广播路由请求包 ( RREQ )发 送给自己 所有 的邻 节 点 , 邻 节 点 在 接 收 到 RREQ 后 ,先在自己的路由表中查找是否有到目的节点的 路由 ,如果有 ,则将路由信息写入 RREP包 (路由回 复包 )发给源节点 ;如果没有 ,再将 RREQ 转发给自 己所有的邻节点. 依此类推 ,直到到达目的节点或是 中间某个节点知道到达目的节点的路由. 路由维护 过程是 :如果中间节点移动 ,那么它的邻节点意识到
(如蜂窝系统 、WLAN )和无需固定基础设施支持的 议. 路由协议的研究成为当前 Ad Hoc网络研究的核
Ad Hoc网络. 前者的移动节点通过被称为 BS ( base 心问题.
station)或者 AP ( access point)设施进行通信 ; 后者 也称为 MANET (mobile Ad Hoc network) ,是一种由
按需路由协议也叫反应式路由 ,只当源节点需 要时才寻找路由. 当源节点需要通往目的节点的一 条路径时 ,它将发起路由发现过程 ,当找到一条路径 或者所有可能的路径都被检查过后 ,路由发现过程 结束. 路径一经建立 ,它就被某个路由程序所维护 , 直到目的节点无法经由任何路径到达或者该路径不 再需要. DSR和 AODV 属于按需协议.
为了减少控制信息的开销 , DSDV 把路由更新 信息分为 2类 :一类称为完整路由更新 ( full dump ) , 包含了该节点的路由表中所有的路由信息 ;另一种 称为增量路由更新 ( incremental) ,携带的是从上次 完整路由更新以后改变的路由信息 ;由于需要周期 性地更新消息 , DSDV 仍然产生很大的网络开销 ,并 且开销是随着网络规模来增长的. 这种协议不适于 大型网络 ,因为网络带宽的大部分将用在路由更新 处理上有许多优势 ,在小型到中型的网络中 ,这种协 议运行得比较好. 1. 2 按需路由
1 典型的 Ad Hoc网络路由协议
移动主机临时组建的 、无中心 、自组织 、不需固定基 础设施的网络. 移动主机具路由功能 ,用于发现并维 护到其他节点的路由. 这种网络灵活 、健壮 、投资少 , 可以快速方便地应用于紧急情况 、军事行动 、灾难恢
目前 ,已经提出了很多用于 Ad Hoc网络的路由 协 议 , 其 中 IETF 公 布 草 案 的 有 : AODV、TORA、 TBRPF、DRS、OLSR、FSR、MAODV、LANMAR 等 , 按 照驱动模式的不同 ,可以分为表驱动路由协议 ( table
源路由协议 [ 2 ] (D SR )是最早采用按需思想的 路由协议. 它使用了源路由的路由机制 ,每一个发送 的数据包都在其头部包含了从源节点到目的节点的 完整路由信息. 当某个源节点 S 产生一个新的分组 需要传输到某个目的节点 D 的时候 , 源节点 S 就在 该分组的分组头中添入一条源路由 , 从而给出沿着
S imula tion and ana lysis of routing protocols for Ad Hoc networks
W E I Kai, J IAN G Tao, L IN G M ing
(College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China)