Metrics and Algorithms for Scheduling of Data Dissemination in Mesh Units Assisted Vehicular Networks

Zhongyi LIU, Bin LIU, Wei YAN
DOI: 10.4236/wsn.2009.13020                

Abstract

Data dissemination is an important application in vehicular networks. We observe that messages in vehicular networks are usually subject to both time and space constraints, and therefore should be disseminated during a specified duration and within a specific coverage. Since vehicles are moving in and out of a region, dis-semination of a message should be repeated to achieve reliability. However, the reliable dissemination for some messages might be at the cost of unreliable or even no chance of dissemination for other messages, which raises tradeoffs between reliability and fairness. In this paper, we study the scheduling of data dis-semination in vehicular networks with mesh infrastructure. Firstly, we propose performance metrics for both reliability and fairness. Factors on both the time and space dimensions are incorporated in the reliability met-ric and the fairness in both network-wide and Mesh Roadside Unit-wise (MRU-wise) senses are considered in the fairness metric. Secondly, we propose several scheduling algorithms: one reliability-oriented algorithm, one fairness-oriented algorithm and three hybrid schemes. Finally, we perform extensive evaluation work to quantitatively analyze different scheduling algorithms. Our evaluation results show that 1) hybrid schemes outperform reliability-oriented and fairness-oriented algorithms in the sense of overall efficiency and 2) dif-ferent algorithms have quite different characteristics on reliability and fairness.

Keywords

Data Dissemination, Vehicular Networks, Scheduling, Mesh Backhaul

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	V. Bychkovsky, B. Hull, et al., “A measurement study of ve-hicular internet access using in situ wi-fi networks,” In Pro-ceedings of the 12th Annual International Conference on Mo-bile Computing and Networking (MOBICOM’06), pp. 50–61, 2006.
[2]	D. Hadaller, S. Keshav, T. brecht, et al., “Vehicular opportun-istic communication under the microscope,” In Proceedings of the 5th International Conference on Mobile Systems, Applica-tions, and Services (MobiSys’07), 2007.
[3]	B. Hull, V. Bychkovsky, Y. Zhang, et al., “Cartel: A distrib-uted mobile sensor computing system,” In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys’06), pp. 125–138, 2006.
[4]	V. Navda, A. P. Subramanian, et al., “MobiSteer: Using steer-able beam directional antenna for vehicular network access,” In Proceedings of the 5th International Conference on Mobile Systems, Applications, and Services (MobiSys’07), 2007.
[5]	Y. Zhang, J. Zhao, and G. H. Cao, “On scheduling vehi-cle-roadside data access,” In Proceedings of the Fourth ACM International Workshop on Vehicular Ad Hoc Networks (VANET’07), pp. 9–18, 2007.
[6]	I. F. Akyildiz, X. Wang, et al., “Wireless mesh networks: A survey,” In Computer Networks, Vol. 47, No. 4, pp. 445–487, 2005.
[7]	H. Y. Luo, et al., “A new model for packet scheduling in mul-tihop wireless networks,” In Proceedings of the 6th Annual International Conference on Mobile Computing and Network-ing (MOBICOM’00), pp. 76–86, 2000.
[8]	H. Y. Luo, et al., “A packet scheduling approach to Qos sup-port in multihop wireless networks,” In Mobile Networks and Applications, Vol. 4, pp. 193–206, 2004.
[9]	J. F. Wang, et al., “Opportunistic packet scheduling and media access control for wireless LANs and multi-hop ad hoc net-works,” In IEEE Wireless Communications and Networking Conference, (WCNC’04), pp. 1234–1239, 2004.
[10]	Y. Ding, et al., “A static-node assisted adaptive routing proto-col in vehicular networks,” In Proceedings of the Fourth ACM International Workshop on Vehicular Ad Hoc Networks (VANET’07), pp. 59–68, 2007.
[11]	I. Leontiadis, et al., “Opportunistic spatio-temporal dissemina-tion system for vehicular networks,” In Proceedings of the 1st International Mobisys Workshop on Mobile Opportunistic Networking (MobiOpp’07), pp. 39–46, 2007.
[12]	P. V. Kanodia, et al., “Distributed multi-hop scheduling and medium access with delay and throughput constraints,” In Pro-ceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM’01), pp. 200–209, 2001.
[13]	E-map of Beijing (English Version), http://en.beijing2008. cn/ 06/78/emap.shtml.