第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＝0‚D 的值按照逆时针方向增大‚如当节点向正 南方向运动时 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·