MEMC-R MEMC-E MEVC-R al GPS Ro 00 0 Number of Rouing Re Number of Routing Reg Routing Request ID n (a)Average travel time without back-(b)Average travel time with back-(c)Standard deviation of travel time (d)Travel time for each request ID ground traffic ground traffic when the number of requests is 8x 104 Fig.4:Time efficiency and fairness comparison among MCMF-R,TS,improved random routing and traditional GPS routing 20x faster routing decision by considering a group of vehicles for the global optimization,causing loss of fairness. at one time VI.CONCLUSION The first two figures in Fig.4 show the time efficiency comparison result for these four algorithms.Fig.4a shows In this paper,we propose two efficient algorithms for route the average travel time for different routing request volumes guidance problem in vehicular network:MCMF-R for central- with no background traffic flows on roads.In Fig.4b,heavy ized routing and TS for distributed routing.Experiment results background traffic is added on some most commonly chosen indicate that,both algorithms have better time efficiency and fairness than traditional methods.Between MCMF-R and TS. roads when no background traffic exists,which simulates the heavy traffic cases discussed in Section IV-D1. TS is more deployable,and more suitable in low traffic volume routing than MCMF-R,and when the traffic is heavy,MCMF- The last two figures in Fig.4 show the fairness comparison R is better in time efficiency but worse in fairness.A hybrid result.Fig.4c shows the standard deviation of the travel time for different routing request volumes,and Fig.4d shows the framework is then proposed to provide better deployment and routing decisions under different traffic intensity situations. sorted travel time for each route request when the routing request volume is 8 x 104 ACKNOWLEDGMENTS In both Fig.4a and Fig.4b,the average travel time of MCMF- This work is supported in part by National Natural Science R and TS are at least 20%better than those of IRR and tradi- Foundation of China under Grant No.61100196,61073028 tional GPS routing,especially when the traffic volume exceed 61321491.91218302:JiangSu Natural Science Foundation 7 x 104.For traditional GPS routing,this improvement can under Grant No.BK2011559 achieve 40%on average.This improvement is even more in REFERENCES Fig.4c and Fig.4d,when the vehicle volume approaches 8x 10 to 10 x 10,the standard deviation and max-min difference [1]D.Schrank,T.Lomax and B.Eisele.(2011,Sep.)Urban mobility report.[Online].Available:http://mobility.tamu.edu/ums/report/ value of both MCMF-R and TS are about 50%of those of [2]J.Ott and D.Kutscher."Drive-thru internet:leee 802.11 b for,automo- IRR.This indicates that the time efficiency and fairness of both bile"Proc.IEEE INFOCOM.vol.1.2004. MCMF-R and TS algorithm are improved largely compared [3]V.Bychkovsky,B.Hull,A.Miu,H.Balakrishnan,and S.Madden A to traditional methods and the random routing of local taxi asurement stu using in situ wi-f networ drivers without any route guidance. Sumo.[Online].Available:http://sourceforge.net/apps/mediawiki/sumo/ IRR is better than traditional GPS routing,especially in [5]F.Li and Y.Wang."Routing in vehicular ad hoc networks:A survey, routing ability.And this advantage is increasing with the traffic [6 veh02-2之，2007 IEEE Vehicular Technology Magazine,vol 2.no.2. L.Xie,Q.Li. and et al volume.This shows that when the traffic is getting heavy,even ursuing efficiency and fairess IEEE Transac local taxi drivers outperform traditional route guidance. Disributed Systems (TPDS).vol.2 no.8.pp.323 3120 el and [7]T.Kitani,T.Shinkawa,and et al.,"Efficient vanet-based traffic informa- For the time efficiency between MCMF-R and TS,they tion sharing using buses on regular routes,"IEEE.Vehicular Technology are quite close,and no one can dominate the other in all ference(VTC). [8 12 and C.3036.2808 "Shortest path algorithms: evaluation using conditions.In Fig.4a.when the traffic volume is fewer than networks, 73 1998 3 x 10,MCMF-R is worse than TS.This is mainly because [9] Lin and S.Chou.Developing adaptive driv ng route guidance systems MCMF-R has more usage of the upper bound of travel time based on fuzzy neural network,"Proc.IET 4th International Conference (Section IV-B)than TS,and overestimates the congestion [10] on Inrelligent Ervironments.pp.1-8.2008. M.Khanafer.M.Guennoun and H.Mouftah,"Wsn architectures condition.When the traffic volume is more than 3 x 10 inteligent tran ta ion sy nation the lack of global information makes the performance of TS Technologies,Mobility and Security (NTMS)pp.1-8. ence on New 2009 degrading largely.When traffic volume is around 5 x 104 [11]M.Khanjary and S.Hashemi,"Route guidance systems:review and classification,"Proc.6th Euro American Conference on Telematics and MCMF-R has a clear advantage over TS,which is about 28% Information Systems,pp.269-275.2012. quicker.After that,TS catches up a little,but MCMF-R is still [12]R.Bauza and J.Gozalvez,"Traffic conge stion detection in la scale narios using vehicle-to ehicle comm stronger than it in time efficiency.In Fig.4b,TS is influenced tions," Computer Applications,2012 more by heavy background traffic than MCMF-R when traffic [13]J.Ding,C.Wang,F.Meng,and T.Wu,"Real-time vehicle route guid- volume is between 3 x 104 to 11 x 104.This indicates that ance using vehicle-to-vehicle communication,"IET:Communications. MCMF-R is more time efficient under heavy traffic conditions. 149R20n20 solutions for freewa travel time In fairness shown in Fig.4c,TS and MCMF-R are compara tion "IEEE Tror Systems. ol.9. ble to each other when the traffic volume is less than 4 x 104 n0.1,Pp.38-47,2008 [15]S.Dornbush and A.Joshi,"Streetsmart traffic:Discovering and dis- Between 4 x 104 and 6 x 104,TS is less fair than MCMF-R seminating automobile congestion using vanet's."Proc IEEE Vehicular since it lacks global information.But when the traffic volume fechnology Conference (VTC),pp.11-15,2007. exceeds 6 x 10,which is also shown in Fig.4d,TS surpasses [16 J.Edmonds and R.Karp. retical improvements in algorithmid efhciency for network MCMF-R and strictly dominates it.It is because in MCMF-R ol ocy o8_264 1972o the ACM (JACM) 972 when the traffic is getting heavy,more vehicles will sacrifice [17]openstreetmap.[Online].Available:http://www.openstreetmap.org/0 2 4 6 8 10 12 x 104 0 1000 2000 3000 4000 5000 6000 7000 Number of Routing Requests Average Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (a) Average travel time without back￾ground traffic 0 2 4 6 8 10 12 x 104 0 1000 2000 3000 4000 5000 6000 7000 Number of Routing Requests Average Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (b) Average travel time with back￾ground traffic 0 2 4 6 8 10 12 x 104 0 500 1000 1500 2000 2500 3000 3500 Number of Routing Requests STDEV of Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (c) Standard deviation of travel time 0 2 4 6 8 x 104 0 1000 2000 3000 4000 5000 6000 7000 8000 Routing Request ID Travel Time (s) MFMC−R TS IRR Traditional GPS Routing (d) Travel time for each request ID when the number of requests is 8×104 Fig. 4: Time efficiency and fairness comparison among MCMF-R, TS, improved random routing and traditional GPS routing 20× faster routing decision by considering a group of vehicles at one time. The first two figures in Fig.4 show the time efficiency comparison result for these four algorithms. Fig.4a shows the average travel time for different routing request volumes with no background traffic flows on roads. In Fig.4b, heavy background traffic is added on some most commonly chosen roads when no background traffic exists, which simulates the heavy traffic cases discussed in Section IV-D1. The last two figures in Fig.4 show the fairness comparison result. Fig.4c shows the standard deviation of the travel time for different routing request volumes, and Fig.4d shows the sorted travel time for each route request when the routing request volume is 8 × 104 . In both Fig.4a and Fig.4b, the average travel time of MCMF￾R and TS are at least 20% better than those of IRR and tradi￾tional GPS routing, especially when the traffic volume exceed 7 × 104 . For traditional GPS routing, this improvement can achieve 40% on average. This improvement is even more in Fig.4c and Fig.4d, when the vehicle volume approaches 8×104 to 10 × 104 , the standard deviation and max-min difference value of both MCMF-R and TS are about 50% of those of IRR. This indicates that the time efficiency and fairness of both MCMF-R and TS algorithm are improved largely compared to traditional methods and the random routing of local taxi drivers without any route guidance. IRR is better than traditional GPS routing, especially in routing ability. And this advantage is increasing with the traffic volume. This shows that when the traffic is getting heavy, even local taxi drivers outperform traditional route guidance. For the time efficiency between MCMF-R and TS, they are quite close, and no one can dominate the other in all conditions. In Fig.4a, when the traffic volume is fewer than 3 × 104 , MCMF-R is worse than TS. This is mainly because MCMF-R has more usage of the upper bound of travel time (Section IV-B) than TS, and overestimates the congestion condition. When the traffic volume is more than 3 × 104 , the lack of global information makes the performance of TS degrading largely. When traffic volume is around 5 × 104 , MCMF-R has a clear advantage over TS, which is about 28% quicker. After that, TS catches up a little, but MCMF-R is still stronger than it in time efficiency. In Fig.4b, TS is influenced more by heavy background traffic than MCMF-R when traffic volume is between 3 × 104 to 11 × 104 . This indicates that MCMF-R is more time efficient under heavy traffic conditions. In fairness shown in Fig.4c, TS and MCMF-R are compara￾ble to each other when the traffic volume is less than 4×104 . Between 4 × 104 and 6 × 104 , TS is less fair than MCMF-R since it lacks global information. But when the traffic volume exceeds 6 × 104 , which is also shown in Fig.4d, TS surpasses MCMF-R and strictly dominates it. It is because in MCMF-R, when the traffic is getting heavy, more vehicles will sacrifice for the global optimization, causing loss of fairness. VI. CONCLUSION In this paper, we propose two efficient algorithms for route guidance problem in vehicular network: MCMF-R for central￾ized routing and TS for distributed routing. Experiment results indicate that, both algorithms have better time efficiency and fairness than traditional methods. Between MCMF-R and TS, TS is more deployable, and more suitable in low traffic volume routing than MCMF-R, and when the traffic is heavy, MCMF￾R is better in time efficiency but worse in fairness. A hybrid framework is then proposed to provide better deployment and routing decisions under different traffic intensity situations. ACKNOWLEDGMENTS This work is supported in part by National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61321491, 91218302; JiangSu Natural Science Foundation under Grant No. BK2011559. REFERENCES [1] D. Schrank, T. Lomax, and B. Eisele. (2011, Sep.) Urban mobility report. [Online]. Available: http://mobility.tamu.edu/ums/report/ [2] J. Ott and D. Kutscher, “Drive-thru internet: Ieee 802.11 b for, automo￾bile,” Proc. IEEE INFOCOM, vol. 1, 2004. [3] V. Bychkovsky, B. Hull, A. Miu, H. Balakrishnan, and S. Madden, “A measurement study of vehicular internet access using in situ wi-fi networks,” Proc. ACM MOBICOM, pp. 50–61, 2006. [4] Sumo. [Online]. Available: http://sourceforge.net/apps/mediawiki/sumo/ [5] F. Li and Y. Wang, “Routing in vehicular ad hoc networks: A survey,” IEEE Vehicular Technology Magazine, vol. 2, no. 2, pp. 12–22, 2007. [6] L. Xie, Q. Li, and et al., “Association control for vehicular wifi access: Pursuing efficiency and fairness,” IEEE Transactions on Parallel and Distributed Systems (TPDS), vol. 22, no. 8, pp. 1323–1331, 2011. [7] T. Kitani, T. Shinkawa, and et al., “Efficient vanet-based traffic informa￾tion sharing using buses on regular routes,” IEEE. Vehicular Technology Conference(VTC), pp. 3031–3036, 2008. [8] F. Zhan and C. Noon, “Shortest path algorithms: an evaluation using real road networks,” Transportation Science, pp. 65–73, 1998. [9] I. Lin and S. Chou, “Developing adaptive driving route guidance systems based on fuzzy neural network,” Proc. IET 4th International Conference on Intelligent Environments, pp. 1–8, 2008. [10] M. Khanafer, M. Guennoun, and H. Mouftah, “Wsn architectures for intelligent transportation systems,” 3rd International Conference on New Technologies, Mobility and Security (NTMS), pp. 1–8, 2009. [11] M. Khanjary and S. Hashemi, “Route guidance systems: review and classification,” Proc. 6th Euro American Conference on Telematics and Information Systems, pp. 269–275, 2012. [12] R. Bauza and J. Gozalvez, “Traffic congestion detection in large-scale scenarios using vehicle-to-vehicle communications,” Journal of Network and Computer Applications, 2012. [13] J. Ding, C. Wang, F. Meng, and T. Wu, “Real-time vehicle route guid￾ance using vehicle-to-vehicle communication,” IET. Communications, vol. 4, no. 7, pp. 870–883, 2010. [14] J. Van Lint, “Online learning solutions for freeway travel time predic￾tion,” IEEE Transactions on Intelligent Transportation Systems, vol. 9, no. 1, pp. 38–47, 2008. [15] S. Dornbush and A. Joshi, “Streetsmart traffic: Discovering and dis￾seminating automobile congestion using vanet’s,” Proc IEEE Vehicular Technology Conference (VTC), pp. 11–15, 2007. [16] J. Edmonds and R. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the ACM (JACM), vol. 19, no. 2, pp. 248–264, 1972. [17] openstreetmap. [Online]. Available: http://www.openstreetmap.org/