We have developed a method of managing vacancy information of a large parking lot in a distributed manner using only intervehicle communication. A group of parking spaces is defined as a cluster. Vacancy information of a cluster is managed by a vehicle in it. This vehicle is called a cluster head. The proposed method generates a communication path topology between cluster heads. The topology is a tree structure with the cluster head of the cluster nearest to the parking lot entrance as the root node. Cluster heads are ranked in order of the number of vacant spaces and the distance to the shop entrance. The vehicle entering the parking lot collects vacancy information of clusters. This information is transmitted along the tree structure from the lowest ranking cluster head. We have developed a simulation model for a parking lot that can accommodate nearly 1,000 vehicles and used it to evaluate the proposed method. We have confirmed that the proposed method generates less communication traffic and enables the vehicle entering a parking lot to collect vacancy information about the area near the shop entrance with a higher probability and in a shorter time. 1. Introduction Today, large commercial facilities invariably have large parking lots. For example, the parking lot of Tokyo Disney Resort [1] accommodates 20,000 vehicles, and that of representative shopping mall in Japan 4,000 vehicles. There are more than 150 theme parks in Japan that have parking lots for 1,000 or more vehicles. If vehicles are concentrated on a specific area in a parking lot, such as the areas near shop entrances, they jam these areas and generate traffic congestion, causing drivers to waste time and lose incentive to do shopping. This means lost opportunities for both shoppers and shop owners. A system that is attracting interest as a means of solving this problem is intelligent transport systems (ITS) [2, 3]. ITS addresses a range of traffic issues, such as traffic optimization, by linking drivers, roads, and vehicles using leading-edge telecommunication technology. It mainly uses road-vehicle communication and intervehicle communication. Road-vehicle communication is used in the electronic toll collection (ETC) system and the vehicle information and communication system (VICS) in Japan. ETC uses dedicated short-range communication (DSRC) for communication between the road and the vehicle. Intensive studies are being made on intervehicle communication that conforms to ITS FORUM RC-005 to 007 [3] and IEEE802.11p [4, 5]. Intervehicle communication is expected to prevent accidents at
References
[1]
“The parking lot of the Tokyo Disney resort,” May 2012, http://ja.wikipedia.org/wiki.
[2]
“Intelligent Transport Systems (ITS),” Road Bureau Ministry of Land, Infrastructure, Transport and Tourism, Japan, http://www.mlit.go.jp/road/ITS/j-html/.
D. Eckhoff, C. Sommer, and F. Dressler, “On the necessity of accurate IEEE 802.11P models for IVC protocol simulation,” in Proceedings of the IEEE 75th Vehicular Technology Conference (VTC Spring '12), pp. 1–5, Yokohama, Japan, June 2012.
[5]
C. Campolo, A. Cortese, and A. Molinaro, “CRaSCH: a cooperative scheme for service channel reservation in 802.11p/WAVE vehicular ad hoc networks,” in Proceedings of the International Conference on Ultra Modern Telecommunications & Workshops ( ICUMT '09), Saint-Petersburg, Russia, October 2009.
[6]
V. Namboodiri and L. Gao, “Prediction-based routing for vehicular Ad Hoc networks,” IEEE Transactions on Vehicular Technology, vol. 56, no. 4, pp. 2332–2345, 2007.
[7]
T. Kosch, C. J. Adler, S. Eichler, C. Schroth, and M. Strassberger, “The scalability problem of vehicular ad hoc networks and how to solve it,” IEEE Wireless Communications, vol. 13, no. 5, pp. 22–28, 2006.
[8]
M. Raya and J.-P. Hubaux, “Securing vehicular ad hoc networks,” Journal of Computer Security, vol. 15, no. 1, pp. 39–68, 2007.
[9]
F. Borgonovo, A. Capone, and M. Cesana, “RR-ALOHA, a reliable R-ALOHA broadcast channel for ad-hoc inter-vehicle communication networks,” in Proceedings of the Med-Hoc-Net, pp. 15–19, 2002.
[10]
Y. Zang, L. Stibor, B. Walke, H. Reumerman, and A. Barroso, “A novel MAC protocol for throughput sensitive applications in vehicular environments,” in Proceedings of the IEEE 65th Vehicular Technology Conference (VTC '07), pp. 2580–2584, April 2007.
[11]
R. M. Yadumurthy, A. Chimalakonda, M. Sadashivaiah, and R. Makanaboyina, “Reliable MAC broadcast protocol in directional and omni-directional transmissions for vehicular ad hoc networks,” in Proceedings of the 2nd ACM International Workshop on Vehicular Ad Hoc Networks (VANET '05), pp. 10–19, September 2005.
[12]
I. Broustis and M. Faloutsos, “Routing in vehicular networks: feasibility, modeling, and Security,” International Journal of Vehicular Technology, vol. 2008, Article ID 267513, 8 pages, 2008.
[13]
S. Kamakshi and S. Natarajan, “Distributed algorithm for constructing efficient tree topology for message dissemination in vehicular networks,” International Journal of Vehicular Technology, vol. 2014, Article ID 903895, 9 pages, 2014.
[14]
K. Matsukawa, “Parking Position Management System and Parking Position Management Method,” 2014, http://patent.astamuse.com/ja/granted/JP/No/4696016.
[15]
W. S. Vanessa, Y. Zheng, and J. Cao, “An intelligent car park management system based on wireless sensor networks,” in Proceedings of the 1st International Symposium on Pervasive Computing and Applications, pp. 65–70, August 2006.
[16]
R. Lu, X. Lin, H. Zhu, and X. Shen, “SPARK: a new VANET-based smart parking scheme for large parking lots,” in Proceedings of the IEEE INFOCOM, pp. 1413–1421, Rio de Janeiro, Brazil, April 2009.
[17]
R. Lu, X. Lin, H. Zhu, and X. Shen, “An intelligent secure and privacy-preserving parking scheme through vehicular communications,” IEEE Transactions on Vehicular Technology, vol. 59, no. 6, pp. 2772–2785, 2010.
[18]
E. H.-K. Wu, J. Sahoo, C.-Y. Liu, M.-H. Jin, and S.-H. Lin, “Agile urban parking recommendation service for intelligent vehicular guiding system,” IEEE Intelligent Transportation Systems Magazine, vol. 6, no. 1, pp. 35–49, 2014.
[19]
Y. Wang, T. Liang, X. Yang, and D. Zhang, “Scalable and effective cluster based routing algorithm using nodes' location for Mobile Ad Hoc Networks,” Information Technology Journal, vol. 7, no. 7, pp. 958–971, 2008.
[20]
L. Ritchie, H. Yang, A. W. Richa, and M. Reisslein, “Cluster Overlay Broadcast (COB): MANET routing with complexity polynomial in source-destination distance,” IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 653–666, 2006.