D0I:10.13374/i.issnl00I053.2009.11.047 第31卷第11期 北京科技大学学报 Vol.31 No.11 2009年11月 Journal of University of Science and Technology Beijing Now.2009 基于模型分析的城市环境下车载移动Ad hoc网络路 由协议改进策略 米振强杨扬郭勋安建伟 北京科技大学信息工程学院，北京100083 摘要在Manhattan移动模型的基础上，深入分析了车载移动Ad hoe网络路由协议的性能问题.结合AODV路由协议，提 出了一种可以量化分析车载Ad hoc网络路由断链率和路由负载的模型.模型分析指出，传统的移动Ad hoc网络路由协议应 用于车载Ad hoc网络时性能会严重下降.针对这一问题，提出了一种基于车辆运动方向信息的类AODV路由协议DBAP,将 车辆的运动方向信息作为其路由发现过程中的辅助参数，从而显著地增强了路由稳定性·仿真结果验证了模型的正确性，同 时证明了本文所提出的DBAP路由协议在城市车载环境中具有较低的路由负载和路由断链率，在协议性能等方面相对于 AODV协议具有显著提高. 关键词车载通信；Ad hoc网络；移动模型：路由协议；路由负载 分类号TN92 Improvement of routing protocols in urban vehicular mobile Ad hoc networks based on an analytical model MI Zhen-qiang,YA NG Yang:GUO Xun,AN Jian-wei Department of Information Technology,University of Science and Technology Beijing.Beijing 100083.China ABSTRACT The performance of routing protocols was studied in vehicular Ad hoc net works(VANETs)based on the Manhattan mobility model.Integrated with the AODV routing protocol,an analytical model was proposed,which was able to quantificationally measure the route breaking rate and routing overhead of VANETs.It is indicated by the analytical model that classic routing protocols in mobile Ad hoc networks can cause serious declination in the performance of VANETs:therefore,a direction based AODV routing protocol (DBAP)was proposed.The vehicle's moving direction was used in DBAP as its auxiliary parameter in routing discovery pro- cess,which remarkably improved the routing stability.Simulations show the validity of this model and prove DBAP's lower route breaking rate and routing overhead as well as its significantly improved performance in VENETs in comparison with AODV in urban vehicular environment. KEY WORDS vehicular communication:Ad hoc network:mobility model:routing protocol:routing overhead 移动Ad hoc网络(MANET)通常由一组移动节 考虑了MANET特点的很多路由协议已经被提出 点组成，节点共享一个无线信道且网络中无集中控 并得到了应用，这些路由协议按照机制的不同可以 制装置以及固定节点组成的骨干网络，Ad hoc网络 分成两类：表驱动路由协议(table-driven)以及按需 没有固定的路由器，所有节点可以任意移动并以任 驱动(on-demand-driven)路由协议，表驱动路由协 意的方式进行动态的接入山.MANET的特点使得 议主要包括DSDV、,OLSR等，表驱动路由协议的数 用户之间的组网和通信得到很大的便利，但同时也 据延时较低，但由于其需要定期更新路由表，从而维 为其路由协议设计带来了一定困难，针对有线网络 护整个网络的路由，因此在规模较大且速率要求不 的经典路由协议无法适用于移动Ad hoc网络，因此 是很高的网络中性能低下；按需驱动路由协议主要 收稿日期：2009-06-01 基金项目：国家高技术研究发展计划资助项目(N。.2007AA01Z234) 作者简介：米振强(1983一)，男，博士研究生；杨扬(1955一)，男，教授，博士，E-mail:yyang@ustb,edu.en
基于模型分析的城市环境下车载移动 Ad hoc 网络路 由协议改进策略 米振强 杨 扬 郭 勋 安建伟 北京科技大学信息工程学院北京100083 摘 要 在 Manhattan 移动模型的基础上深入分析了车载移动 Ad hoc 网络路由协议的性能问题．结合 AODV 路由协议提 出了一种可以量化分析车载 Ad hoc 网络路由断链率和路由负载的模型．模型分析指出传统的移动 Ad hoc 网络路由协议应 用于车载 Ad hoc 网络时性能会严重下降．针对这一问题提出了一种基于车辆运动方向信息的类 AODV 路由协议 DBAP将 车辆的运动方向信息作为其路由发现过程中的辅助参数从而显著地增强了路由稳定性．仿真结果验证了模型的正确性同 时证明了本文所提出的 DBAP 路由协议在城市车载环境中具有较低的路由负载和路由断链率在协议性能等方面相对于 AODV 协议具有显著提高． 关键词 车载通信；Ad hoc 网络；移动模型；路由协议；路由负载 分类号 T N92 Improvement of routing protocols in urban vehicular mobile Ad hoc networks based on an analytical model MI Zhen-qiangY A NG Y angGUO XunA N Jian-wei Department of Information TechnologyUniversity of Science and Technology BeijingBeijing100083China ABSTRACT T he performance of routing protocols was studied in vehicular Ad hoc networks （VANETs） based on the Manhattan mobility model．Integrated with the AODV routing protocolan analytical model was proposedwhich was able to quantificationally measure the route breaking rate and routing overhead of VANETs．It is indicated by the analytical model that classic routing protocols in mobile Ad hoc networks can cause serious declination in the performance of VANETs；thereforea direction based AODV routing protocol （DBAP） was proposed．T he vehicle’s moving direction was used in DBAP as its auxiliary parameter in routing discovery processwhich remarkably improved the routing stability．Simulations show the validity of this model and prove DBAP’s lower route breaking rate and routing overhead as well as its significantly improved performance in VENETs in comparison with AODV in urban vehicular environment． KEY WORDS vehicular communication；Ad hoc network；mobility model；routing protocol；routing overhead 收稿日期：2009－06－01 基金项目：国家高技术研究发展计划资助项目（No．2007AA01Z234） 作者简介：米振强（1983－）男博士研究生；杨 扬（1955－）男教授博士E-mail：yyang＠ustb．edu．cn 移动 Ad hoc 网络（MANET）通常由一组移动节 点组成节点共享一个无线信道且网络中无集中控 制装置以及固定节点组成的骨干网络．Ad hoc 网络 没有固定的路由器所有节点可以任意移动并以任 意的方式进行动态的接入［1］．MANET 的特点使得 用户之间的组网和通信得到很大的便利但同时也 为其路由协议设计带来了一定困难．针对有线网络 的经典路由协议无法适用于移动 Ad hoc 网络因此 考虑了 MANET 特点的很多路由协议已经被提出 并得到了应用．这些路由协议按照机制的不同可以 分成两类：表驱动路由协议（table-driven）以及按需 驱动（on-demand-driven）路由协议．表驱动路由协 议主要包括 DSDV、OLSR 等表驱动路由协议的数 据延时较低但由于其需要定期更新路由表从而维 护整个网络的路由因此在规模较大且速率要求不 是很高的网络中性能低下；按需驱动路由协议主要 第31卷 第11期 2009年 11月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．31No．11 Nov．2009 DOI:10．13374／j．issn1001－053x．2009．11．047
第11期 米振强等：基于模型分析的城市环境下车载移动Adho心网络路由协议改进策略 .1481. 包括AODV、DSR等，这类路由协议中，只有源节点 系统的参考意义不明显，所以，很多针对车载Ad 有数据包发送时才会启动路由发现过程，路由负载 hoc网络的移动模型被提出来，如Freeway(FWY) 相对较低，因此比较适合于强移动性低速率的网络 模型、Random Point Group Mobility(RPGM)模型 环境，正是基于上述特点，按需路由协议目前是 和Manhattan(MH)[模型，其中具有代表性的是 MANET路由协议研究的主流， MH模型，本文采用MH模型为车辆节点运动模型 将传统Ad hoc网络应用于车载通信是一个较 进行建模，并在其基础之上分析、设计适用于车载系 新的研究领域，不同于传统的MANET,车载Ad hoc 统的路由协议， 网络主要具有以下的特点：①节点速度较高，但其 在文献[6]中，Bai等引入了Manhattan模型，模 移动轨迹被限制在道路中，由一定的规则来约束，并 型中节点的移动被限制在网格空间中，在平行和竖 且与其他运动节点相关，随机性相对较低：②不同 直的道路上移动，如图1所示，在交叉口按照一定的 道路之间即使距离较小，但由于高层建筑物的阻碍 概率选择左转右转或者直行，其主要目的就是仿真 使得其正常通信的可能性较低；③车载通信网络在 城市道路环境下的网络状况，MH模型中，同向车 城市环境下节点密度较高；④车载Ad hoc网络对 道的节点之间的链路比较稳定，反向车道链路比较 于数据发送速率要求较低，基于上述特点，传统的 容易断裂，节点的移动速度依赖于其前一个时刻的 MANET路由协议并不能完全适用于车载Ad hoc 运动速度以及相邻节点的移动速度，并遵循如下 网络，因此国际上有很多研究机构和组织致力于设 法则： 计适用于车载Ad hoc的路由协议，Kap等]提出 了GSR(geographic source routing)协议，根据获得 的目的车辆的位置信息，源节点利用城市地图计算 一系列的包必须通过的顶点来到达目的车辆；Seet 等[3]提出了A一STAR(anchor-based street and traffic aw are routing)协议，A STAR利用了城市公 交车作为信标路径，以实现对包发送率的高连接性 能，计算信标路径采用Dijkstra's最短路径算法； Wu等[提出了MDDV(mobility-centric data dissemination algorithm for vehicular networks) 法，假定了网络的密度稳定，沿源到目的节点的轨 图1 Manhattan模型示意图 迹，让信息包按照距目的节点最近节点转发，此转发 Fig.I Schematic diagram of the Manhattan model 需要利用地理信息和网络密度，这种方法增强了路 由的可靠性，但是当网络密度变化迅速时，会导致很 (1)IV:(t+1)|=|V:(t)|+random()· 长的延时.上述协议与算法均利用了GPS信息[) a:(t); 的支持进行路由选择 (2)Hi,Hj,Ht,D.(t)≤sDP|V:(t)l≤ 基于上述分析，本文在针对车载Ad hoc网络建 V(t),当且仅当节点j与节点i处于同一条道路 模的同时，提出一种适用于城市车载Ad hoc网络环 上，并在其前方，式中，SD代表两个节点的安全距 境的基于行驶方向信息的类AODV路由协议 离，「V:(t)|代表节点i在t时刻的移动速度， DBAP(direction based AODV routing protocol). |a:(t)表示节点i在t时刻的加速度，D,(t)表示 真结果表明，在不降低网络性能的情况下，DBAP路 在t时刻节点i与节点j之间的直线距离 由协议可显著降低路由负载以及路由断链率， 1.2AODV路由协议 AODV (Ad hoc on-demand distance vector) 1研究背景 由协议是一种反应式按需驱动路由协议，由于其在 1.1适合于车载Ad hoc网络的随机移动模型 协议性能、健壮性及其可扩展性等方面较之其他协 车载Ad hoc网络研究中，多数研究者使用的移 议有很大优势，因此被广泛的接纳并采用 动模型是Random Waypoint(RWP)模型.由于此 AODV路由协议的路由发现过程如下：源节点 模型没有考虑到车载Ad hoc网络的特点，因此基于 首先检查自身的路由表，如果路由表中存在到达目 此模型进行的仿真分析精确性不高，对于实际车载 的节点的有效路由，则使用该路由进行数据发送；否
包括 AODV、DSR 等这类路由协议中只有源节点 有数据包发送时才会启动路由发现过程路由负载 相对较低因此比较适合于强移动性低速率的网络 环境．正是基于上述特点按需路由协议目前是 MANET 路由协议研究的主流． 将传统 Ad hoc 网络应用于车载通信是一个较 新的研究领域不同于传统的 MANET车载 Ad hoc 网络主要具有以下的特点：① 节点速度较高但其 移动轨迹被限制在道路中由一定的规则来约束并 且与其他运动节点相关随机性相对较低；② 不同 道路之间即使距离较小但由于高层建筑物的阻碍 使得其正常通信的可能性较低；③ 车载通信网络在 城市环境下节点密度较高；④ 车载 Ad hoc 网络对 于数据发送速率要求较低．基于上述特点传统的 MANET 路由协议并不能完全适用于车载 Ad hoc 网络因此国际上有很多研究机构和组织致力于设 计适用于车载 Ad hoc 的路由协议．Karp 等［2］提出 了 GSR （geographic source routing）协议根据获得 的目的车辆的位置信息源节点利用城市地图计算 一系列的包必须通过的顶点来到达目的车辆；Seet 等［3］ 提 出 了 A－STAR （anchor-based street and traffic aware routing）协议A－STAR 利用了城市公 交车作为信标路径以实现对包发送率的高连接性 能计算信标路径采用 Dijkstraʾs 最短路径算法； Wu 等［4］ 提 出 了 MDDV （ mobility-centric data dissemination algorithm for vehicular networks） 算 法假定了网络的密度稳定沿源到目的节点的轨 迹让信息包按照距目的节点最近节点转发此转发 需要利用地理信息和网络密度．这种方法增强了路 由的可靠性但是当网络密度变化迅速时会导致很 长的延时．上述协议与算法均利用了 GPS 信息［5］ 的支持进行路由选择． 基于上述分析本文在针对车载 Ad hoc 网络建 模的同时提出一种适用于城市车载 Ad hoc 网络环 境的 基 于 行 驶 方 向 信 息 的 类 AODV 路 由 协 议 DBAP（direction based AODV routing protocol）．仿 真结果表明在不降低网络性能的情况下DBAP 路 由协议可显著降低路由负载以及路由断链率． 1 研究背景 1∙1 适合于车载 Ad hoc 网络的随机移动模型 车载 Ad hoc 网络研究中多数研究者使用的移 动模型是 Random Waypoint （RWP）模型．由于此 模型没有考虑到车载 Ad hoc 网络的特点因此基于 此模型进行的仿真分析精确性不高对于实际车载 系统的参考意义不明显．所以很多针对车载 Ad hoc 网络的移动模型被提出来如 Freeway （FWY） 模型、Random Point Group Mobility （RPGM）模型 和 Manhattan （MH） ［6］ 模型其中具有代表性的是 MH 模型．本文采用 MH 模型为车辆节点运动模型 进行建模并在其基础之上分析、设计适用于车载系 统的路由协议． 在文献［6］中Bai 等引入了 Manhattan 模型模 型中节点的移动被限制在网格空间中在平行和竖 直的道路上移动如图1所示在交叉口按照一定的 概率选择左转右转或者直行其主要目的就是仿真 城市道路环境下的网络状况．MH 模型中同向车 道的节点之间的链路比较稳定反向车道链路比较 容易断裂节点的移动速度依赖于其前一个时刻的 运动速度以及相邻节点的移动速度并遵循如下 法则： 图1 Manhattan 模型示意图 Fig．1 Schematic diagram of the Manhattan model （1） ｜Vi （ t ＋1）｜＝｜Vi （ t ）｜＋random （ ）· ｜ai（ t）｜； （2） ∀ i∀ j∀tDij （ t）≤SD⇒｜Vi（ t）｜≤ ｜Vj（ t）｜当且仅当节点 j 与节点 i 处于同一条道路 上并在其前方．式中SD 代表两个节点的安全距 离｜Vi （ t ）｜代表节点 i 在 t 时刻的移动速度 ｜ai（ t）｜表示节点 i 在 t 时刻的加速度Dij（ t）表示 在 t 时刻节点 i 与节点 j 之间的直线距离． 1∙2 AODV 路由协议 AODV （Ad hoc on-demand distance vector） ［7］路 由协议是一种反应式按需驱动路由协议由于其在 协议性能、健壮性及其可扩展性等方面较之其他协 议有很大优势因此被广泛的接纳并采用． AODV 路由协议的路由发现过程如下：源节点 首先检查自身的路由表如果路由表中存在到达目 的节点的有效路由则使用该路由进行数据发送；否 第11期 米振强等： 基于模型分析的城市环境下车载移动 Ad hoc 网络路由协议改进策略 ·1481·
.1482 北京科技大学学报 第31卷 则，源节点以洪泛的方式向邻居节点发送RREQ广 一1 (1) 播报文，收到RREQ广播报文的节点首先判断自身 =1 是否为目的节点或存在到目的节点的有效路由，如 式(1)中，V为节点的平均移动速度，Po为To时间 果有则向源节点发送路由回复信息RREP,RREP 内路由稳定的概率 经过的节点更新自己的路由表，直到源节点收到回 证明由假设可以得到，同一条道路上反向运 复信息并建立路由；若不存在到目的节点的有效路 由，则收到RREQ的节点更新自己的路由表，并继 动的节点平均链路维持时间T0一，节点N:在T0 续转发RREQ, 时间内节点选择正向节点作为下一跳节点的概 作为反应式路由协议，AODV仅在有需求时才 率为： 会建立路由，当节点数量较少、移动性不强以及网络 p=m平 负载较低的情况下，可以得到比较理想的性能 Perkins等8]指出，AODV路由协议在节点高密度高 同理，N:选择反向节点作为下一跳节点的概率为： 移动性环境下的性能仍然要高于其他按需路由协 P.me 议；而相比较于DSDV、DSR和TORA等其他经典 当N:选择反向节点作为下一跳节点时，由于链路 路由协议，AODV具有时延低、能耗较小、吞吐量大 等优势[].鉴于以上分析，最终选用AODV路由协 最大维持时间为T0,因此在T0时间内，链路稳定 议作为建模的对象 的概率为1.当N:选择同向节点作为下一跳节点 时，在To时间内，链路稳定的概率为： 2路由协议模型描述与分析 P,=(1-B'=(1-月7. 针对车载Ad hoc网络的建模近年来逐渐成为 式中，阝为单位时间内同向节点的链路断链概率. VANET研究的热点.在文献[1O]中，Yousefi等在 由上式可以得出To时间内路由稳定的概率： 对高速公路中车辆运动行为进行分析的基础，利用 「L 排队理论对VANET的连通性进行了模型化分析； 多数VANET模型是针对一维道路模型来进行的， P0= i (1 (2) Lm:十ni 并不适合于分析车辆比较密集的城市环境下的车载 网络：而针对AODV路由协议所提出的模型，均没 表示对L 式中L 所定义的路由跳数向上取整 有考虑节点的运动状态-].目前仍没有一个模 由(2)可以推出单条路由的平均路由维持时间： 型可以结合节点的运动状况，对路由层的性能进行 Tsa=lim[To(1-P:o)P:o+2To(1-Po)Po+ 量化的分析，因此笔者试图对于特定的车载Ad hoc 网络进行建模，从而给出一种相对准确的量化方法 ...+nTo(1-Po)Po]=To(1-Po) 作为设计路由协议的依据， (3) 假设车载Ad hoc网络移动模型采用MH模 在服务需求时间T1内，每次路由断链之后便 型，节点平均移动速度相同、均匀分布在道路中且无 重新启动路由发现过程，因此可以得到每条链路的 法与其他道路中的节点进行通信，源节点随机选取 平均断链次数（即路由发现次数）： 网络中的任意其他节点作为目的节点，且物理层以 TI-TIV 7-1 及MAC层有理想的通信能力（忽略隐藏节点等 问题) 定理1得证， 定义节点N:在其一跳通信范围之内，同向 定理2在AODV路由协议中，平均每条链路 运动的邻居节点数量为m,反向运动的节点邻居节 在服务需求的时间T1内，网络中针对此链路的 点数量为n:(m,n≥0)，网络场景中道路总长度为 RREQ发送或转发的总数量约为： L,节点无线传输距离为L,源节点与目的节点之 间的平均距离为Lh,场景中节点总数量为Q, 定理1采用AODV路由协议时，其每对通信 证明由假设可以得到，网络中每个节点的平 节点在其服务需求时间T1内路由的平均断链次 数为： 均邻居节点的数量Nm 2L,假设在RREQ的 L
则源节点以洪泛的方式向邻居节点发送 RREQ 广 播报文收到 RREQ 广播报文的节点首先判断自身 是否为目的节点或存在到目的节点的有效路由如 果有则向源节点发送路由回复信息 RREPRREP 经过的节点更新自己的路由表直到源节点收到回 复信息并建立路由；若不存在到目的节点的有效路 由则收到 RREQ 的节点更新自己的路由表并继 续转发 RREQ． 作为反应式路由协议AODV 仅在有需求时才 会建立路由当节点数量较少、移动性不强以及网络 负载较低的情况下可以得到比较理想的性能． Perkins 等［8］指出AODV 路由协议在节点高密度高 移动性环境下的性能仍然要高于其他按需路由协 议；而相比较于 DSDV、DSR 和 TORA 等其他经典 路由协议AODV 具有时延低、能耗较小、吞吐量大 等优势［9］．鉴于以上分析最终选用 AODV 路由协 议作为建模的对象． 2 路由协议模型描述与分析 针对车载 Ad hoc 网络的建模近年来逐渐成为 VANET 研究的热点．在文献［10］中Yousefi 等在 对高速公路中车辆运动行为进行分析的基础利用 排队理论对 VANET 的连通性进行了模型化分析； 多数 VANET 模型是针对一维道路模型来进行的 并不适合于分析车辆比较密集的城市环境下的车载 网络；而针对 AODV 路由协议所提出的模型均没 有考虑节点的运动状态［11－12］．目前仍没有一个模 型可以结合节点的运动状况对路由层的性能进行 量化的分析因此笔者试图对于特定的车载 Ad hoc 网络进行建模从而给出一种相对准确的量化方法 作为设计路由协议的依据． 假设 车载 Ad hoc 网络移动模型采用 MH 模 型节点平均移动速度相同、均匀分布在道路中且无 法与其他道路中的节点进行通信源节点随机选取 网络中的任意其他节点作为目的节点且物理层以 及 MAC 层有理想的通信能力（忽略隐藏节点等 问题）． 定义 节点 Ni 在其一跳通信范围之内同向 运动的邻居节点数量为 mi反向运动的节点邻居节 点数量为 ni（ mini≥0）网络场景中道路总长度为 L r节点无线传输距离为 Lt源节点与目的节点之 间的平均距离为 Lh场景中节点总数量为 Q． 定理1 采用 AODV 路由协议时其每对通信 节点在其服务需求时间 T1 内路由的平均断链次 数为： Nb＝ T1V Lt （1－Pt0） ∑ ∞ n＝1 nP n t0 －1 （1） 式（1）中V 为节点的平均移动速度Pt0为 T0 时间 内路由稳定的概率． 证明 由假设可以得到同一条道路上反向运 动的节点平均链路维持时间 T0＝ Lt V 节点 Ni 在 T0 时间内节点选择正向节点作为下一跳节点的概 率为： Pm＝ mi mi＋ ni ． 同理Ni 选择反向节点作为下一跳节点的概率为： Pn＝ ni mi＋ ni ． 当 Ni 选择反向节点作为下一跳节点时由于链路 最大维持时间为 T0因此在 T0 时间内链路稳定 的概率为1．当 Ni 选择同向节点作为下一跳节点 时在 T0 时间内链路稳定的概率为： Ps＝（1－β） T0＝（1－β） L t V ． 式中β为单位时间内同向节点的链路断链概率． 由上式可以得出 T0 时间内路由稳定的概率： Pt0＝ ∏ L h L t i＝1 mi mi＋ ni （1－β） L t V （2） 式中 Lh Lt 表示对 Lh Lt 所定义的路由跳数向上取整． 由（2）可以推出单条路由的平均路由维持时间： Tsta＝limn→∞ ［ T0（1－Pt0） Pt0＋2T0（1－Pt0） P 2 t0＋ …＋ nT0（1－Pt0） P n t0］＝ T0（1－Pt0） ∑ ∞ n＝1 nP n t0 （3） 在服务需求时间 T1 内每次路由断链之后便 重新启动路由发现过程因此可以得到每条链路的 平均断链次数（即路由发现次数）： Nb＝ T1 Tsta ＝ T1V Lt （1－Pt0） ∑ ∞ n＝1 nP n t0 －1 ． 定理1得证． 定理2 在 AODV 路由协议中平均每条链路 在服务需求的时间 T1 内网络中针对此链路的 RREQ 发送或转发的总数量约为： Nrreq≈ 4QT1V Lh （1－Pt0） ∑ ∞ n＝1 nP n t0 －1 （4） 证明 由假设可以得到网络中每个节点的平 均邻居节点的数量 Nb n＝ 2QLt L r 假设在 RREQ 的 ·1482· 北 京 科 技 大 学 学 报 第31卷
第11期 米振强等：基于模型分析的城市环境下车载移动Ad hoc网络路由协议改进策略 ·1483 最大生存期TTL值约等于2倍的平均路由跳数 中设置包含本节点方向信息的标志位PT-direction, 并以广播包的形式发送给邻居节点，收到RREQ的 (和实际情况较为类似)，从而可以得到RREQ的平 节点首先判断自己是否为目的节点，如果“是”则直 均转发次数约为： 接回复RREP;否则读取RREQ的PT-direction位 N,≈2XL40L, 的值，并和自身运动方向D作比较，得到F=|D一 L Lh (5) 在每条链路的服务的需求时间之内，网络中针 PT-direction,若a<F<2π一a(其中a为用户自 对此链路所发送或转发的RREQ总数量平均值 己定义的方向差异容忍阈值，且O<a<π)则表明本 应为： 节点和发送RREQ的上游节点运动方向的偏差不 Nmeg=NrNh· 在容忍范围之内，故丢弃该数据包并不作任何回应； 定理2得证 否则，判断本节点到目的节点的有效路由是否存在， 由分析可以看到，AODV路由协议在车载 如果存在有效路由，则向源节点发送RREP;否则节 Ad hoc网络环境之下，采用MH模型进行分析的时 点更新自身的路由表，加入到达源节点的路由，并更 候，其路由断链率很高，特别是在平均速度较大或节 新RREQ的PT-direction标志位，写入自己的行驶 点比较密集的时候，路由重建的次数比较多，造成的 方向，转发RREQ数据包 直接结果便是网络中的控制报文RREQ数量激增， 以上机制正是充分考虑了车载Ad hoc的特点， 从而大大影响了路由协议的效率，对网络资源浪费 每一跳的节点都选择与自身运动方向相同或相似的 严重.正是基于对以上模型的分析，本文对AODV 节点作为下一跳节点，很大程度上降低了路由断链 协议进行了改进，从而使其更加适合于车载Ad hoc 率，从而使得服务需求时间内路由发现次数减小，可 的网络环境，在不降低网络性能的前提下降低路由 以使网络中节点的路由负载降低 开销以及路由的断链率 3.3模型验证 3DBAP协议设计策略 按照假设，并选择α=乏，则所选择的转发节点 均为和上一跳同向的节点，从而可以针对DBAP协 3.1DBAP协议设计思想 议的路由发现过程得到下述定理， 基于对AODV路由协议的分析，发现经典的 定理3对于DBAP路由协议，由于其每一跳 AODV协议并不适合于车载Ad hoc网络环境，在节 都会选择同向运动的邻居节点为转发节点，可以得 点密集以及运动速度较高的城市车载环境下，其协 到其每对通信节点在其服务需求时间T1内路由的 议的性能会产生显著的下降.考虑到车载网络的特 平均断链次数： 殊性，使用同向传输、异向避免的机制来进行路由的 选择，采用本机制之后，由于避免了断链率很高的异 N=T1(1-月 (6) 向路由，因此链路的稳定性将得到很大的提高，在密 证明过程参考定理1，不再赘述. 集的城市车载环境中，本机制将会对网络性能带来 定理4在DBAP路由协议中，平均每条链路 很大改进， 在服务需求的时间T1内，网络中针对此链路的 3.2DBAP协议设计机制 RREQ发送或转发的总数量约为： DBAP机制中，每个节点保存并实时更新自己 的运动方向信息，定义如下： 20ZL1-1 Lh 节点的运动速度为Vm,运动方向为D.当 证明过程参考定理2，不再赘述 Vm=0时，D=一1；当Vm>0时，取正北方向为 比较式(6)与式(1)可以看到，DBAP路由协议 D=0,D的值按照逆时针方向增大，如当节点向正 的路由断链率和运动速度无关，而AODV路由协议 南方向运动时D=π，而当节点向正东、正西运动 路由断链率在速度V上升时会产生激增，因此在节 时，D值分布为受与受 点高速运动的时候，DBAP协议将会显示出明显的 不同于AODV路由协议，DBAP的路由发现过 优势，当路由跳数增大时，AODV的路由断链也会 程如下：源节点首先检查自身的路由表，如果路由 以更快的速度上升，同理，比较式(7)与式(4)，在同 表中存在到达目的节点的有效路由，则使用该路由 样时间的服务需求下，采用DBAP协议会大幅降低 进行数据发送；否则，源节点生成RREQ报文，报文 控制信息的发送量，降低网络的负载
最大生存期 TTL 值约等于2倍的平均路由跳数 Lh Lt （和实际情况较为类似）从而可以得到 RREQ 的平 均转发次数约为： Nr≈ 2Nb nLh Lt ≈ 4QLt Lh （5） 在每条链路的服务的需求时间之内网络中针 对此链路所发送或转发的 RREQ 总数量平均值 应为： Nrreq＝ Nr Nb． 定理2得证． 由分 析 可 以 看 到AODV 路 由 协 议 在 车 载 Ad hoc网络环境之下采用 MH 模型进行分析的时 候其路由断链率很高特别是在平均速度较大或节 点比较密集的时候路由重建的次数比较多造成的 直接结果便是网络中的控制报文 RREQ 数量激增 从而大大影响了路由协议的效率对网络资源浪费 严重．正是基于对以上模型的分析本文对 AODV 协议进行了改进从而使其更加适合于车载 Ad hoc 的网络环境在不降低网络性能的前提下降低路由 开销以及路由的断链率． 3 DBAP 协议设计策略 3∙1 DBAP 协议设计思想 基于对 AODV 路由协议的分析发现经典的 AODV 协议并不适合于车载 Ad hoc 网络环境在节 点密集以及运动速度较高的城市车载环境下其协 议的性能会产生显著的下降．考虑到车载网络的特 殊性使用同向传输、异向避免的机制来进行路由的 选择采用本机制之后由于避免了断链率很高的异 向路由因此链路的稳定性将得到很大的提高在密 集的城市车载环境中本机制将会对网络性能带来 很大改进． 3∙2 DBAP 协议设计机制 DBAP 机制中每个节点保存并实时更新自己 的运动方向信息定义如下： 节点的运动速度为 V n运动方向为 D．当 V n＝0时D＝－1；当 V n ＞0时取正北方向为 D＝0D 的值按照逆时针方向增大如当节点向正 南方向运动时 D＝π而当节点向正东、正西运动 时D 值分布为 3π 2 与 π 2 ． 不同于 AODV 路由协议DBAP 的路由发现过 程如下：源节点首先检查自身的路由表．如果路由 表中存在到达目的节点的有效路由则使用该路由 进行数据发送；否则源节点生成 RREQ 报文报文 中设置包含本节点方向信息的标志位PT －direction 并以广播包的形式发送给邻居节点．收到 RREQ 的 节点首先判断自己是否为目的节点．如果“是”则直 接回复 RREP；否则读取 RREQ 的 PT －direction 位 的值并和自身运动方向 D 作比较得到 F＝｜D－ PT －direction｜．若 α＜F＜2π－α（其中 α为用户自 己定义的方向差异容忍阈值且0＜α＜π）则表明本 节点和发送 RREQ 的上游节点运动方向的偏差不 在容忍范围之内故丢弃该数据包并不作任何回应； 否则判断本节点到目的节点的有效路由是否存在． 如果存在有效路由则向源节点发送 RREP；否则节 点更新自身的路由表加入到达源节点的路由并更 新 RREQ 的 PT －direction 标志位写入自己的行驶 方向转发 RREQ 数据包． 以上机制正是充分考虑了车载Ad hoc的特点 每一跳的节点都选择与自身运动方向相同或相似的 节点作为下一跳节点很大程度上降低了路由断链 率从而使得服务需求时间内路由发现次数减小可 以使网络中节点的路由负载降低． 3∙3 模型验证 按照假设并选择 α＝ π 2 则所选择的转发节点 均为和上一跳同向的节点从而可以针对 DBAP 协 议的路由发现过程得到下述定理． 定理3 对于 DBAP 路由协议由于其每一跳 都会选择同向运动的邻居节点为转发节点可以得 到其每对通信节点在其服务需求时间 T1 内路由的 平均断链次数： N′b＝ T1（1－β） － L h L t （6） 证明过程参考定理1不再赘述． 定理4 在 DBAP 路由协议中平均每条链路 在服务需求的时间 T1 内网络中针对此链路的 RREQ 发送或转发的总数量约为： N′rreq≈ 2QT1Lt Lh （1－β） － L h L t （7） 证明过程参考定理2不再赘述． 比较式（6）与式（1）可以看到DBAP 路由协议 的路由断链率和运动速度无关而 AODV 路由协议 路由断链率在速度 V 上升时会产生激增因此在节 点高速运动的时候DBAP 协议将会显示出明显的 优势．当路由跳数增大时AODV 的路由断链也会 以更快的速度上升．同理比较式（7）与式（4）在同 样时间的服务需求下采用 DBAP 协议会大幅降低 控制信息的发送量降低网络的负载． 第11期 米振强等： 基于模型分析的城市环境下车载移动 Ad hoc 网络路由协议改进策略 ·1483·
,1484 北京科技大学学报 第31卷 4 型选取Shadowing模型，因为较之被广泛应用的 仿真验证 TwoRay Ground模型，Shadow ing模型更加贴近实际 4.1仿真参数设置 环境中的无线传播情况，所得出的结果也更有指导 为了验证提出的模型的正确性以及DBAP协 意义 议的优劣，利用NS2仿真软件对于所提出的方法进 仿真场景1：在表1所定义的仿真参数约束下， 行了仿真验证 分别选取节点数量为10,20,30，…，200，节点运动 NS2(Network Simulation Version2)是一个事 最大速度为20ms1,最小速度为0ms1,平均运 件驱动的网络仿真器，由LNBL(Lanrenze Berkely 动速度为10m·s,在这些场景之下分别针对 Nation Laboratory)研究组开发，其前身是 AODV以及DBAP协议进行仿真实验，从而验证在 KESHAVS研制的REAL仿真器，其协议代码与真 不同的节点密度情况下两种协议的性能差异，给出 实网络应用代码很相似，仿真结果具有可靠性 比较结果 为了比较在不同节点密度以及平均运动速度的 仿真场景2：在表1参数定义下，选取网络中节 条件下协议的性能，设置了两组仿真场景，仿真场 点数量为100个，分别设置节点的平均运动速度为 景的参数设置如表一所示，选取仿真场景大小为 0ms1,5ms1,10ms1,…,40ms(最大最小 1000×1000,传输半径为150m,从而可以检验网络 速度与平均速度分别相差5ms1),在此场景之下 多跳连接的性能.物理层和MAC层采用802.11标 对AODV与DBAP协议进行仿真实验，验证运动速 准，符合实际车载Ad hoc系统的条件：无线传播模 度对于两种协议性能的影响， 表1仿真环境参数设置 Table 1 Simulation parameters 运动模型 Manhattan模型，节点在路口转弯概率为20%，道路数量为3X3,均为双向四车道 场景大小 1000X1000 无线传输模型 采用shadowing模型，路径衰弱指数P=2.5,标准偏差om=3.0 工作频段 2.4GH 发射功率 17 dBm 天线类型 全向天线，高度1.5m 传输范围 约150m MAC协议 802.11DCF 路由协议 AODV、DBAP 应用层 随机选取网络中一半节点为发包节点，采用UDP链接，发包类型为CBR数据包，封包大小为512kB,发包间 隔为0.5s,每条链路服务需求时间1等于仿真时间 4.2性能评价指标 的稳定性， 为了考量在车载Ad hoc网络环境下两种路由协 4.3仿真结果分析 议的优劣，实验主要针对以下三个性能指标进行评价， 从图2(a)可以看到，随着节点数量的增大， Routing overhead:路由开销，本文将路由开销 AODV和DBAP的Routing Overhead均有增大，但 定义为路由层所发送的控制报文的总大小与其发送 总体来说，DBAP协议的路由负载要比AODV协议 的所有报文（包括数据报文、控制报文）的总数之比， 低25%~30%，这也符合定理2与定理4所定义的 该指标可很大程度上反应路由协议的效率. 模型，在节点数量Q增大的时候，控制信息会有一 Number of break:路由断链次数，即在服务需求 定程度的增大；从图2(b)的曲线中可以看到，DBAP 内已经建立的路由，每断链一次断链次数加1，直到 协议的路由负载随着速度的增大并无太大的变化， 仿真结束，由于验证两种路由协议的场景均相同， 曲线比较平缓，路由负载始终保持在一个较低的水 因此可以直接比较路由的断链次数，从而分析两种 平，这符合定理4所刻画的模型，其控制信息量和节 路由协议的稳定性， 点运动速度无直接的关系，而AODV的路由负载明 Drop ratio:丢包率，即应用层未成功接收的数 显会随着速度的增加，其趋势验证了定理4的正确 据包与其发送的所有数据包之比，丢包率可以刻画 性.通过图2可以得出，在路由负载方面，DBAP较 协议的路由发现能力，也能一定程度上表现出路由 之AODV有着更好的性能
4 仿真验证 4∙1 仿真参数设置 为了验证提出的模型的正确性以及 DBAP 协 议的优劣利用 NS2仿真软件对于所提出的方法进 行了仿真验证． NS2（Network Simulation Version2）是一个事 件驱动的网络仿真器由 LNBL （Lanrenze Berkely Nation Laboratory ） 研 究 组 开 发其 前 身 是 KESHAVS研制的 REAL 仿真器．其协议代码与真 实网络应用代码很相似仿真结果具有可靠性． 为了比较在不同节点密度以及平均运动速度的 条件下协议的性能设置了两组仿真场景．仿真场 景的参数设置如表一所示选取仿真场景大小为 1000×1000传输半径为150m从而可以检验网络 多跳连接的性能．物理层和 MAC 层采用802∙11标 准符合实际车载 Ad hoc 系统的条件；无线传播模 型选取 Shadowing 模型因为较之被广泛应用的 TwoRayGround 模型Shadowing 模型更加贴近实际 环境中的无线传播情况所得出的结果也更有指导 意义． 仿真场景1：在表1所定义的仿真参数约束下 分别选取节点数量为102030…200节点运动 最大速度为20m·s －1最小速度为0m·s －1平均运 动速度为 10m·s －1在这些场景之下分别针对 AODV 以及 DBAP 协议进行仿真实验从而验证在 不同的节点密度情况下两种协议的性能差异给出 比较结果． 仿真场景2：在表1参数定义下选取网络中节 点数量为100个分别设置节点的平均运动速度为 0m·s －15m·s －110m·s －1…40m·s －1（最大最小 速度与平均速度分别相差5m·s －1）在此场景之下 对 AODV 与 DBAP 协议进行仿真实验验证运动速 度对于两种协议性能的影响． 表1 仿真环境参数设置 Table1 Simulation parameters 运动模型 Manhattan 模型节点在路口转弯概率为20％道路数量为3×3均为双向四车道 场景大小 1000×1000 无线传输模型 采用 shadowing 模型路径衰弱指数 βpl＝2∙5标准偏差 σdB＝3∙0 工作频段 2∙4GHz 发射功率 17dBm 天线类型 全向天线高度1∙5m 传输范围 约150m MAC 协议 802∙11DCF 路由协议 AODV、DBAP 应用层 随机选取网络中一半节点为发包节点采用 UDP 链接发包类型为 CBR 数据包封包大小为512kB发包间 隔为0∙5s每条链路服务需求时间 Tl 等于仿真时间 4∙2 性能评价指标 为了考量在车载 Ad hoc 网络环境下两种路由协 议的优劣实验主要针对以下三个性能指标进行评价． Routing overhead：路由开销．本文将路由开销 定义为路由层所发送的控制报文的总大小与其发送 的所有报文（包括数据报文、控制报文）的总数之比 该指标可很大程度上反应路由协议的效率． Number of break：路由断链次数即在服务需求 内已经建立的路由每断链一次断链次数加1直到 仿真结束．由于验证两种路由协议的场景均相同 因此可以直接比较路由的断链次数从而分析两种 路由协议的稳定性． Drop ratio：丢包率即应用层未成功接收的数 据包与其发送的所有数据包之比．丢包率可以刻画 协议的路由发现能力也能一定程度上表现出路由 的稳定性． 4∙3 仿真结果分析 从图2（a）可以看到随着节点数量的增大 AODV 和 DBAP 的 Routing Overhead 均有增大但 总体来说DBAP 协议的路由负载要比 AODV 协议 低25％～30％这也符合定理2与定理4所定义的 模型在节点数量 Q 增大的时候控制信息会有一 定程度的增大；从图2（b）的曲线中可以看到DBAP 协议的路由负载随着速度的增大并无太大的变化 曲线比较平缓路由负载始终保持在一个较低的水 平这符合定理4所刻画的模型其控制信息量和节 点运动速度无直接的关系而 AODV 的路由负载明 显会随着速度的增加其趋势验证了定理4的正确 性．通过图2可以得出在路由负载方面DBAP 较 之 AODV 有着更好的性能． ·1484· 北 京 科 技 大 学 学 报 第31卷