基于运行轨迹特征分析的车辆自组织网路由算法

doi:10.11959/j.issn.1000-436x.2016124

摘要/Abstract

摘要：

首先基于车辆trace数据提取了粗粒度的车辆移动信息，在此基础上，继续研究了trace数据的细粒度的车辆移动模型；然后基于移动模型提出了车辆自组织网络的路由算法（RPT-D），根据车辆移动特征将报文更快地传输到目的地；接着将对传输的QoS需求放入报文选路目标中，得到扩展性和选路结果更好的RPT-GA算法；最后通过仿真实验，分别从传输时延、投递成功率、跳数和辅助报文数量等4个性能参数角度，基于车辆trace数据将所提出的路由算法与经典的车辆自组织网路由算法（IGRP和GPSR）进行比较，实验结果验证了所提算法的有效性。

关键词: 车辆自组网, 车辆trace, 路由算法, 传输时延, 投递成功率

Abstract:

The coarse granularity vehicle mobility information is extracted from the vehicle trace data.Then a fine granularity mobility model was presented based on the coarse-grained mobility information.Based on the mobility model,a VANET routing algorithm,RPT-D,was proposed to quickly deliver the packets to the destination according to the mobility attributes.The RPT-GA algorithm,which was integrated with the QoS demands in the path selection objective,was designed.Finally,through the extensive simulations,the proposed algorithms are compared with other typical VANET routing algorithms,IGRP and GPSR,in terms of the transmission latency,the delivery ratio,the hop count and the extra package number.The simulation results verify the performance of the proposed algorithms.

Key words: vehicular ad hoc network, vehicle trace, routing algorithm, transmission latency, delivery ratio

陶桦,冯富琴,肖鹏,谭诚伟,陶军. 基于运行轨迹特征分析的车辆自组织网路由算法[J]. 通信学报, 2016, 37(6): 144-153.

Hua TAO,Fu-qin FENG,Peng XIAO,Cheng-wei TAN,Jun TAO. Routing algorithm based on characteristics analysis of vehicle trace in vehicular ad hoc network[J]. Journal on Communications, 2016, 37(6): 144-153.

图/表 15

表1

表2

表3

表4

表5

表6

表7

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 25

[1]	JIANG H , GUO H , CHEN L . Reliable and efficient alarm message routing in VANET[C]// 28th International Conference on Distributed Computing Systems Workshops,ICDCS'08. 2008: 186-191.
[2]	TAO J , XIAO P , LIU Y ,et al. A routing algorithm based on the probability of topology connectivity in vehicluar ad-hoc networks[J]. Journal of Southeast University, 2013,(3): 1-4.
[3]	FASOLO E , ZANELLA A , ZORZI M . An effective broadcast scheme for alert message propagation in vehicular ad hoc networks[C]// IEEE International Conference on ICC'06. 2006: 3960-3965.
[4]	KORKMAZ G , EKICI E , ?ZGüNER F ,et al. Urban multi-hop broadcast protocol for inter-vehicle communication systems[C]// Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks. ACM, 2004: 76-85.
[5]	DING B , CHEN Z , WANG Y ,et al. An improved AODV routing protocol for VANET[C]// 2011 International Conference on Wireless Communications and Signal Processing(WCSP). 2011: 1-5.
[6]	ABEDI O , BERANGI R , AZGOMI M A . Improving route stability and overhead on AODV routing protocol and make it usable for VANET[C]// 29th IEEE International Conference on Distributed Computing Systems Workshops,ICDCS Workshops'09. 2009: 464-467.
[7]	ABEDI O , FATHY M , TAGHILOO J . Enhancing AODV routing protocol using mobility parameters in VANET[C]// IEEE/ACS International Conference on Computer Systems and Applications. 2008: 229-235.
[8]	WISITPONGPHAN N , BAI F , MUDALIGE P ,et al. Routing in sparse vehicular ad hoc wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2007,25(8): 1538-1556.
[9]	BLUM J , ESKANDARIAN A , HOFFMAN L . Mobility management in IVC networks[C]// Proceedings IEEE Intelligent Vehicles Symposium. 2003: 150-155.
[10]	JAAP S , BECHLER M , WOLF L . Evaluation of routing protocols for vehicular ad hoc networks in typical road traffic scenarios[C]// 11th EUNICE Open European Summer School on Networked Applications, 2005: 584-602.
[11]	NAUMOV V , GROSS T R . Connectivity-aware routing (CAR) in vehicular ad-hoc networks[C]// INFOCOM 26th IEEE International Conference on Computer Communications, 2007: 1919-1927.
[12]	HARSCH C , FESTAG A , PAPADIMITRATOS P . Secure position-based routing for VANET[C]// IEEE 66th Vehicular Technology Conference. 2007: 26-30.
[13]	MENOUAR M , LENARDI M , FILALI F . A movement prediction based routing protocol for vehicle-to-vehicle communications[J]. Communications, 2005,21: 07-2005.
[14]	KARP B , KUNG H T . GPSR:Greedy perimeter stateless routing for wireless networks[C]// The 6th Annual International Conference on Mobile Computing and Networking. ACM, 2000: 243-254.
[15]	LI F , WANG Y . Routing in vehicular ad hoc networks:a survey[J]. IEEE Vehicular Technology Magazine, 2007,2(2): 12-22.
[16]	RAO S A , PAI M C , BOUSSEDJRA M ,et al. GPSR-L:Greedy perimeter stateless routing with lifetime for VANETS[C]// 8th International Conference on ITS Telecommunications, 2008: 299-304.
[17]	SALEET H , LANGAR R , NAIK K ,et al. Intersection-based geographical routing protocol for VANETs:a proposal and analysis[J]. IEEE Transactions on Vehicular Technology, 2011,60(9): 4560-4574.
[18]	TAO J , ZHU L , WANG X ,et al. RSU deployment scheme with power control for highway message propagation in VANETs[C]. IEEE Global Communications Conference(GLOBECOM). 2014: 169-174.
[19]	LI X , PAN G , WU Z ,et al. Prediction of urban human mobility using large-scale taxi traces and its applications[J]. Frontiers of Computer Science, 2012,6(1): 111-121.
[20]	KIM M , KOTZ D , KIM S . Extracting a mobility model from real user traces[C]// INFOCOM. 2006: 1-13.
[21]	ZHANG X , KUROSE J , LEVINE B N ,et al. Study of a bus-based disruption-tolerant network:mobility modeling and impact on routing[C]// The 13th Annual ACM International Conference on Mobile Computing and Networking. ACM, 2007: 195-206.
[22]	YOON J , NOBLE B D , LIU M ,et al. Building realistic mobility models from coarse-grained traces[C]// The 4th International Conference on Mobile Systems,Applications and Services. ACM, 2006: 177-190.
[23]	ZHANG L , YU B , PAN J . GeoMob:a mobility-aware geocast scheme in metropolitans via taxicabs and buses[C]// IEEE INFOCOM, 2014: 1279-1787.
[24]	TAO J , XU Y , TAN C ,et al. Location-aware opportunistic forwarding in mobile opportunistic networks[C]// IEEE Wireless Communications and Networking Conference(WCNC). 2015: 1847-1852.
[25]	PARK J S , LEE U , OH S Y ,et al. Emergency related video streaming in VANET using network coding[C]// The 3rd International Workshop on Vehicular Ad Hoc Networks. ACM, 2006: 102-103.

时间段	0～1	2～3	4～5	6～7	8～9	10～11	12～13	14～15	16～17	18～19	20～21	22～23
0～1	1.000 0	0.823 4	0.717 8	0.833 3	0.861 9	0.873 4	0.849 0	0.839 7	0.854 7	0.841 4	0.835 8	0.848 2
2～3	0.823 4	1.000 0	0.864 8	0.661 5	0.654 8	0.641 0	0.599 4	0.585 1	0.609 9	0.589 7	0.577 3	0.588 6
4～5	0.717 8	0.864 8	1.000 0	0.664 8	0.583 5	0.562 3	0.535 7	0.516 8	0.538 3	0.520 1	0.509 1	0.520 9
6～7	0.833 3	0.661 5	0.664 8	1.000 0	0.858 7	0.849 3	0.856 3	0.835 3	0.855 6	0.845 5	0.818 2	0.817 0
8～9	0.861 9	0.654 8	0.583 5	0.858 7	1.000 0	0.943 8	0.931 9	0.926 0	0.930 2	0.911 6	0.885 2	0.885 4
10～11	0.873 4	0.641 0	0.562 3	0.849 3	0.943 8	1.000 0	0.964 3	0.963 2	0.957 4	0.942 1	0.929 8	0.929 8
12～13	0.849 0	0.599 4	0.535 7	0.856 3	0.931 9	0.964 3	1.000 0	0.973 7	0.963 0	0.953 0	0.944 7	0.945 5
14～15	0.839 7	0.585 1	0.516 8	0.835 3	0.926 0	0.963 2	0.973 7	1.000 0	0.966 8	0.959 7	0.952 0	0.950 4
16～17	0.854 7	0.609 9	0.538 3	0.855 6	0.930 2	0.957 4	0.963 0	0.966 8	1.000 0	0.970 1	0.953 8	0.947 6
18～19	0.841 4	0.589 7	0.520 1	0.845 5	0.911 6	0.942 1	0.953 0	0.959 7	0.970 1	1.000 0	0.963 6	0.953 9
20～21	0.835 8	0.577 3	0.509 1	0.818 2	0.885 2	0.929 8	0.944 7	0.952 0	0.953 8	0.963 6	1.000 0	0.973 5
22～23	0.848 2	0.588 6	0.520 9	0.817 0	0.885 4	0.929 8	0.945 5	0.950 4	0.947 6	0.953 9	0.973 5	1.000 0

日期	周一	周二	周三	周四	周五	周六	周日
周一	1.000 0	0.974 0	0.973 8	0.970 9	0.972 8	0.922 6	0.884 7
周二	0.974 0	1.000 0	0.972 1	0.969 5	0.971 0	0.914 9	0.878 5
周三	0.973 8	0.972 1	1.000 0	0.974 6	0.974 1	0.920 3	0.879 9
周四	0.970 9	0.969 5	0.974 6	1.000 0	0.974 3	0.930 0	0.893 2
周五	0.972 8	0.971 0	0.974 1	0.974 3	1.000 0	0.921 8	0.880 7
周六	0.922 6	0.914 9	0.920 3	0.930 0	0.921 8	1.000 0	0.957 8
周日	0.884 7	0.878 5	0.879 9	0.893 2	0.880 7	0.957 8	1.000 0

日期	周一	周二	周三	周四	周五	周六	周日
周一	1.000 0	0.951 0	0.951 0	0.937 2	0.929 8	0.830 0	0.753 7
周二	0.951 0	1.000 0	0.949 9	0.939 8	0.931 0	0.838 5	0.769 6
周三	0.951 0	0.949 9	1.000 0	0.944 2	0.932 1	0.833 2	0.759 8
周四	0.937 2	0.939 8	0.944 2	1.000 0	0.937 3	0.830 1	0.764 4
周五	0.929 8	0.931 0	0.932 1	0.937 3	1.000 0	0.822 6	0.763 8
周六	0.830 0	0.838 5	0.833 2	0.830 1	0.822 6	1.000 0	0.922 2
周日	0.753 7	0.769 6	0.759 8	0.764 4	0.763 8	0.922 2	1.000 0

日期	A_wd[1]	A_wd[2]	A_wd[3]	A_wd[4]	A_wd[5]	A_wd[6]	A_wd[7]	A_wd[8]	A_wd[9]A_wd[10]A_wd[11]A_wd[12]
1月26日	0.972 7	0.959 4	0.960 4	0.983 0	0.985 3	0.983 7	0.986 1	0.985 2	0.985 40.983 20.983 50.982 0
1月27日	0.972 4	0.955 1	0.959 7	0.974 6	0.986 2	0.985 7	0.983 8	0.984 9	0.986 30.986 50.981 20.978 8

日期	R_wd[1]	R_wd[2]	R_wd[3]	R_wd[4]	R_wd[5]	R_wd[6]	R_wd[7]	R_wd[8]	R_wd[9]R_wd[10]R_wd[11]R_wd[12]
1月26日	0.935 7	0.949 0	0.936 2	0.958 5	0.974 3	0.972 7	0.971 2	0.971 6	0.968 20.969 20.970 70.963 5
1月27日	0.937 5	0.938 1	0.942 3	0.946 7	0.970 0	0.967 4	0.965 7	0.970 7	0.967 00.966 20.969 40.966 7