囊I 研究与开发 。一。一 一㈡ 鳓 缓 车载自组织网络RBVT.R协议的改进 术 陈远龙1f2,葛剑飞。,刘南杰1I2。赵海涛1I2 2.南京邮电大学网络基因工程研究所 (1.南京邮电大学通信与信息工程学院南京210003: 南京210003;3.国家电网上海市电力公司信息通信公司上海200122) 摘 要:分析了基于地理位置的路由协议RBVT-R。针对RBVT-R协议在路由建立过程及分组转发过程中的 缺陷,提出了一种RBVT—R协议的改进算法。该算法在路由建立过程中,根据自主获取的道路车辆密度改进了 RBVT—R协议的洪泛机制;在分组转发过程中采用基于方向和位置预测的转发方法.解决了分组在同一路段 重复传输的问题。仿真结果表明,提出的改进策略有效地提升了分组的交付率与端到端平均时延。 关键词:通信与信息系统;路由协议;RBVT.R;洪泛机制;分组转发 doi:10.39696.issn.1000-0801.2013.09.003 Improvement of RBVT-R Routing Protocol in VANET Chen Yuanlong ,Ge Jianfei ,Liu Na ̄ie ’。,Zhao Haitao ’ (1.Institute of Telecommunications&Information Engineering,Nanjing University of Posts and Telecommunications, Nanjing 210003,China;2.Network Gene Engineering Research Institute,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;3.Information&Telecommunication Co.,Ltd.,State Grid Shanghai Municipal Electirc Power Company,Shanghai 200122,China) Abstract:The location—based routing protocol RBVT—R was analyzed.Aiming at the defects of RBVT—R routing protocol during the process of routing establishment and packet forwarding,an improved algorithm of RBVT—R was proposed.This method has improved the flooding mechanism by attaining road traffic density independently during the process of muting establishment.A packet forwarding scheme based on direction and location forecast was proposed during the process of packet forwarding,and had solved the pro ̄em of repeated transmission of packets in the same section.The simulation results show that the proposed improvement strategy can effectively enhance the average packet delivery ratio and end—to—end delay. Key words:telecommunications&information system,routing protocol RBVT-R flooding mechanis,packetm forwarding 1 引言 车载自组织网络(vehicular Ad Hoc network,VANET) 是指道路上车辆间、车辆与固定接人点之间相互通信组 成的开放移动Ad I-Ioc网络.可以实现事故告警、辅助驾 驶、道路交通信息查询和Internet信息服务等应用『1]。 十国家重点基础研究发展计划(“973”计划)基金资助项目(No.2013CB329005),国家自然科学基金资助项目(No.61302100,No.61201162),江 苏省基础研究计划一重点研究专项基金资助项目(No.BK2011027,No.BK2012434),江苏省高校自然科学研究基金资助项目 (No.12KJB510022,No.12l(JB510o2o),南京邮电大学引进人才科研启动基金资助项目(No.NY211007,No.NY211036),中国博士后研究基金 资助项目(No.2013M531391),教育部博士点基金资助项/ ̄(No.20123223120001),国家电网公司科技项目基金资助项I ̄l(No.52090F135015) 囊 研究与并发 根据RBVT.R协议中存在的问题,提出了一种改进算 法。该算法包括两个部分,分别是对路由建立过程的改进 和对数据分组传输过程的改进。 3.1 路由建立过程的改进 但是。这个改进洪泛机制只考虑了RD分组接收节点 和发送节点之间的距离,没有考虑到两节点所在区域一跳 范围内的车辆密度,本质上还是一种贪婪转发策略,因此 存在频繁发生局部最大的问题。针对这个问题,下面结合 自主获取的道路车辆密度对此等待函数进行了改进。 通过GPS获得RD分组发送节点/Z 和接收节点n 之 间的距离 ,根据式(1)获得两个节点之间的道路车辆密 针对RBVT.R协议在路由发现过程中,其改进的洪泛 机制没有考虑到道路车辆密度对路由稳定性影响的问题. 在改进的算法中提出了一种逐段式道路车辆密度自主估 算方法。并将估算出的道路车辆密度用于改善路由发现过 度P 。根据参考文献【10】中的多标准映射函数,可以得到包 程中的洪泛机制。 3.1.1逐段式道路车辆密度自主估算方法 如图2所示,在一个路段上。当前的分组转发节点为 下一跳转发节点为nj,根据当前两个节点的邻居节点的 数量以及它们之间的距离,估算这两个节点所在区域一跳 范围内的路段的车辆密度。计算式如下: p do.+2R一 (1) 其中, = u 是两个节点ni和珥的邻居节点的总 数,它不是邻居节点数的单纯相加,因为节点 和珥互为 邻居节点。它们之间存在共同邻居节点,如图2中三角形 节点所示, 对共同的邻居节点只添加一次;也是节点 和ni之间的距离,R是无线传输半径。2R是因为无线信号 是全方位传播的,因此其邻居节点分布也是全方位的。 图2逼路车辆密度自主估算不惹 3.1.2 RBVT.R协议洪泛机制的改进 在RBVT.R协议采用的改进洪泛机制中,中间节点在收 到RD分组后会等待一段时间,直到等待时间结束才进行判 断,决定是否转发该RD分组,等待时间的计算如式(2)所示: d):一 t ̄.d +MaxWT (2) ange 其中,d ̄=min(d,Range),d是RD分组的接收节点与 发送节点之间的距离,Range是无线传输范围,M似 是 最大等待时间。 含距离和车辆密度这两个参数的等待函数计算式: d )=K毋 +I『rzl眦 (3) 其中,K=(一W 雄d ),d 是发送节点m和接收节 点 之间的最大距离,取值为无线传输半径R;pm啦是发送 节点/Z 和接收节点珥之间的道路车辆密度的上限值;W 是最大等待时间; 、 分别是距离d 和车辆密度P 的加 权因子,都小于1,O/ 、a:取值的不同会影响如和P 在等待 函数中的作用。例如,在车辆密集的地方,有足够的节点来 转发分组,此时可以适当增大O/ 的值,以减小车辆密度对 等待函数的影响程度。 3。2数据分组传输过程的改进 当路由成功建立之后,源节点开始向目的节点发送数据, 此时它会把建立的路口序列保存到数据分组的头部,数据分 组就按照这个序列进行转发。分组从源节点到目的节点的转 发过程实质上就是按照建立的路口序列中的路口顺序,从一 个路口转发到下一个路口,不断重复直到到达目的节点。 针对RBVT.R协议中数据分组在同一路段反复传输 的问题.在改进的算法中提出了一种基于方向和位置预测 的分组转发方法。该方法需要考虑车辆节点之间链路的有 效持续时间并比较各个节点的转发优先权值,下面首先分 析了上述两个内容,然后在此基础上提出了基于方向和位 置的分组转发方法的完整方案。 3.2.1链路有效持续时间 车辆之间相对方向关系有:同向行驶(其中同向行驶 根据前后车辆的车速大小还分为赶超和落后两种情况,分 别如图3、图4所示),相向行驶如图5所示,背向行驶如 图6所示。上述4种情况下,车辆之间的链路有效持续时 间分别如式(4)一式(7)所示。 同向行驶(赶超): lifetimes= ± (4) y A_- B 同向行驶(落后): 电信料攀 跏 = 相向行驶:  ̄ (5) 背向行驶: lfietimes= R+dAB 加= (7) 其中, 、V 分别为节点A和B的行驶速度,R为节 点的传输半径,d佃为节点A和 之间的相对距离。由以上 式子可以看到.同向运行的车辆节点之间的链路有效时间 是最长的.因此在路由选择过程中应首先考虑在同向车辆 ◆ §◆ 、 中选择下一跳转发节点,这样可以选择更加稳定的路径, A A 一 尺 、、 、/ 、 ,, 、, 、,、~,、 ,,, ●●.。I-.../ , 、、’ 、 A B 卜_— ■ 广— 、、 , 、 、, ~、,~,,~,,-_--●● 图5 A、B相向行驶的相对位置关系 ,●,●--’。。-’’, , 、 , 、 , 、 , ~ , 、 , 、. / 、, ~~ ,_,_-●-●● 图6 A、B背向行驶的相对位置关系 提高路由协议的性能。 3.2.2节点转发优先权值计算 假设。当前携带数据分组的节点为S,待选的下一跳转 发节点为A。首先,根据节点5与A之间的相对关系,选择 对应的链路有效持续时间计算公式计算lfietime ;然后,采 用式(8)预测经过△f时间后节点 的位置: {【 X A',=XyA+VAxy"A "At ㈣ 一 其中,xA,ya)为节点A的当前位置,v 为A的速 度, ,ya )为经过At时间后节点A的位置。 通过地图获得下一个将要到达的路口 的位置 fijyfj, 节点A在经过△f时间后与路口li之间的距离 为: ^=、/ 一 + (9) 根据链路有效持续时间lifetime 以及节点A经过 时间后与下一个路口 的距离 ,计算节点A的优先转 发权值为: SA=t ̄X li[eti me舭。sA+ ̄×( 1一 ) (10) 其中,MaxLifetime是文中设定的一个链路时间的上限 值,用来约束在车辆同向行驶且速度很相近的情况下.链 路时间无限大的情况,lfietimesA不能超过该上限值; = 代表了待选节点A距离目标路口的远近程度,其中D 为节点S到目标路口//的距离, 越小代表A在经过时间 △f后距离路口//越近; 分别是链路有效持续时间和节 点A到路口距离的加权值,且a+fl=l,它们的取值大小代表 了各参数对计算结果的影响程度,根据节点运动方向和分 组转发方向之间的关系不同, 的取值也不同。 3.2.3基于方向和位置预测的分组转发 通过前面的分析,下面提出一种基于方向和位置预测 的分组转发方案,具体的分组转发过程如下。 (1)携带数据分组的节点.s在选择下一跳转发节点时. 首先根据邻居列表中邻居节点的位置判断在分组转发方 研究与评发 向上是否有可转发的节点,也就是在5和下一个路口之间 是否有节点,若有,则进行下一步,否则就由节点5暂时携 带该数据分组,等待可转发车辆的出现。 (2)首先选择和分组转发方向相同的节点,若没有,则再 选择反方向上的节点,然后根据邻居列表中邻居节点的速度 大小和方向等信息,计算5和它们之间链路的有效持续时间 和这些节点在△f时间后的位置,根据式(9)得到这些邻居节 点到下一个路13//的距离,再计算各节点的转发优先权值。 (3)节点|s选择优先权值最大的节点转发分组。 4仿真分析 采用基于VanetMobisim和NS.2的仿真平台。使用 VanetMobisim进行车辆移动模型的模拟。并在NS一2上实 现了对RBVT—R协议的改进.将改进后的路由协议叫作 IRBVT-R(improved RBVT—R)。 车辆节点的移动模型采用VanetMobisim中带有路口 管理的智能驾驶者模型(intelligent driver model with intersection management。IDM.IM)。采用南京市新街口附近 2 000 m范围内的道路布局作为仿真场景。详细的仿真参 数见表1,所有道路交叉13都设有红绿灯。仿真结果如图7、 图8所示 表1仿真参数 从图7、图8中可以看出,随着车辆节点数的增加。 RBVT.R和IRBVT.R两个协议的分组交付率都增大,并且端 到端平均时延都减小。这是因为这两个协议都结合了实时的 道路车辆信息,在车辆节点数很少时,道路车辆密度小,节点 的可连接性差,分组在转发时会经常因找不到下一跳转发节 点而被暂时携带,甚至被丢弃,从而导致端到端平均时延 大,且分组交付率低;随着车辆节点数的增加,道路车辆密 度逐渐增大.节点的可连接性提高,使得分组能被及时可靠 地转发,从而提高了分组交付率,并减小了端到端平均时延。 从图7、图8中还可以看出.IRBVT.R协议在分组交 付率和端到端平均时延这两个指标上,其性能都要优于 节点数 图7不同节点数时的分组交付率 节点数 图8不同节点数时的端到端平均时延 RBVT.R协议。这是因为IRBVT.R协议在路由建立阶段考 虑了道路的车辆密度.选择车辆密度大的路段作为分组传 输的路径,提高了所建路由的稳定性,并且在分组传输阶 段,考虑了车辆行驶方向与分组转发方向的关系,优先选 择与分组转发方向相同且转发优先权值最大的车辆作为 下一跳转发节点,减小了分组在同一路段重复传输的概 率,从而减小了端到端平均时延,并提高了分组交付率。 5 结束语 VANET是由车辆节点组成的Ad Hoc网络。VANET路 由协议的最大挑战就在于车辆节点的移动导致网络拓扑的 频繁变化以及城市环境下节点的移动受道路布局的导 致节点分布不均匀。本文在现有的RBVT—R协议的基础上, 提出了一种改进的IRBVT.R协议,该协议在路由建立阶段 考虑了道路的车辆密度.并且在分组传输阶段还考虑了车 辆行驶方向与分组转发方向的关系,提高了分组传输的可 靠性。仿真结果表明,IRBVT.R协议在分组交付率和端到端 平均时延等方面,其性能都要优于RBVT.R协议。 9 Li D,Huang H Y,Li X,et o1.A distance-based directional 参考文献 胡云斌.夏玮玮+宋铁成等.~种应用于VANET的改进GPSR broadcast protocol for urban vehiculr Ad Hoc netawork. Proceedings of IEEE WiCOM,Shanghai,China,2007:19-24 10 Egoh K,De S.A multicriteria receiverside relay election 路由协议.2009通信理论与技术新发展——第十四届全国青 年通信学术会议论文集,大连,中国,2009 Y,Muhlethaler P,Laoriti A.Vehicle Ad Hoc networks: 2 Toorapplications and related technical issues.IEEE Communications approach in wireless Ad Hoc networks.Proceedings of MILCOM, Washington DC,USA,2006:1-7 Surveys&Tutorials,2008,10(3):74 ̄88 Pei G,Gerla M,Chen T W.Fisheye state routing:a routing 【作者简介】 scheme for Ad Hoc wireless networks.Proceedings of 2000 IEEE International Conference on ICC,New Orleans,US 20oO:70~74 4 Das S R,Belding-royer E M,Perkins C E.Ad Hoc on—demand distance vector(AODV)routing.Proceedings of WMCSA’99, New Orleans,USA,2003 Karp B,Kung T H.GPSR:greedy perimeter stateless routing for _ 陈要自远研组织龙究方网,男络向,的南为路京移动由邮协电通议大信。学与 硕无士线研技究术生、车,主载 wireless networks.Proceedings of the 6th annual International 葛剑飞。男.国家电网上海市电力公司信息通信公司高级 Conference on Mobile Computing and Networking(MOBICOM’0o), 工程师.主要从事电力通信的研究工作。 Boston,USA,2000:243-254 6 Nzouonta J,Rajgure N,Wang Guiling.VANET routing on city wads using real—time vehicular traffic information.IEEE 刘南杰,男,博士,南京邮电大学教授、网络基因工程研究 Transactions on Vehicular Technology,2009,58(7):3609-3626 所所长,教育部工程研究中心副主任,物联网研究院副院 7 Namboodiri V,Gao L X.Prediction-based routing for Vehicular 长,江苏省南亿迪纳数字科技发展有限公司CEO、首席科 Ad Hoc networks.IEEE Transactions on Vehicular Technology, 学家,主要研究方向为泛在通信、车联网、智能交通。 2007,56(4):2332—2345 8 Lochert C,Mauve M,Hartenstein H,et a1.Geographic routing in 赵海涛,男,博士,南京邮电大学讲师、网络基因工程研究 city scenarios.ACM SIGMOBILE Mobile Computing and 所所长助理,主要研究方向为无线网络与泛在通信。 Communications Review,2005,9(1):69-72 (收稿日期:2013—06—08) (上接第13页) 9 Bjorner N,Blass A,Gurevich Y.Content—Dependent Chunking 【作者简介】 ofr Differentila Compression,the Local Maximum Approac. 刘保健,男,国防科学技术大学硕士研究 Technical Report 109.Micros0fl Research.2007 生,主要研究方向为广域网服务质量。 10 Halepovic E,Williamson C,Ghaderi M.Enhancing redundant network traffic elimination.Computer Networks,2012,56(2): 795—809 11陈曙辉.基于内容分析的高速网络协议识别技术研究.国防科 学技术大学博士学位论文,2007 12 Rabin M O.Fingerprinting by Random Polynomials.Technical 黄杰,男,博士,国防科学技术大学副研究员,主要研究方 Report TR・15・81,Department of Computer Science,Harvard 向为高性能存储网络、卫星导航信息处理。 University,1981 13 Rivest R.The MD5 Message・Digest Algorithm,Networking 王宝生,男,博士,国防科学技术大学研究员,主要研究方 Working Group Requests for Comment.MIT Laboratory for 向为新型网络体系结构、天基网络技术、系统软件及应用、 Computer Science and RSA Data Security,Inc,RFC・ 网络与信息安全。 1321,1992 张潇晓,男,西北工业大学博士研究生,主要研究方向为人 14 National Institute of Standards and Technology.Specications for 工智能、网络安全。 Secure Hash Standard,1995 (收稿日期:2013—06—10)