Design and Development of Smart Parking System Based on Fog Computing and Internet of Things

Abstract

Current parking systems employ a single gateway-centered solution (i.e., cloud) for data processing which leads to the possibility of a single point of failure, data loss, and high delays. Moreover, the parking-spot selection process considers criteria that do not maximize parking utilization and revenue. The pricing strategy does not achieve high revenue because a fixed pricing rate is utilized. To address these issues, this paper proposes a smart parking system based on the Internet of Things (IoT) that provides useful information to drivers and parking administrators about available parking spots and related services such as parking navigation, reservation, and availability estimation. A multi-layer architecture is developed that consists of multiple sensor nodes, and fog and cloud computing layers. The acquired parking data are processed through fog computing nodes to facilitate obtaining the required real-time parking data. A novel algorithm to obtain the optimal parking spot with the minimum arrival time is also presented. Proof-of-concept implementation and simulation evaluations are conducted to validate the system performance. The findings show that the system reduces the parking arrival time by 16–46% compared to current parking systems. In addition, the revenue is increased for the parking authority by 10–15%.

1. Introduction

The smart city concept integrates information and communication technologies (ICT) to facilitate sustainable development, economic growth, and quality-of-life improvement [1,2,3]. One of the directions leading towards smart cities is the development of intelligent transportation and efficient traffic management systems to optimize drivers’ travel planning and alleviate traffic congestion [4,5,6,7]. Currently, drivers obtain a parking spot themselves by searching all spots until an available spot is found. This leads to a waste of valuable time that may hinder economic growth [3]. In addition, during the waiting time due to congestion, the vehicles are burning fuel unnecessarily, causing high greenhouse gas emissions [8]. These issues can be addressed using a smart parking system that helps drivers to determine and reserve parking spots in advance before reaching their destination. Such systems would become highly significant in almost every major city in the world, especially during large events (e.g., conferences, religious events, sporting events, festivals, and concerts). They would help in tackling traffic congestion, reducing pollution, and minimizing the negative impact on the city landscape and environment [9].

Smart parking systems form part of traffic management strategies and manage parking processes by helping vehicles to park efficiently in a way that reduces parking arrival time and traffic congestion. The development of smart parking systems has attracted the attention of researchers in academia and industry, due to their economic, environmental, and aesthetic impacts. The Internet of Things (IoT) is emerging as a leading technology for smart object communication [10]. IoT is the key enabler technology for smart parking systems, which employ different sensing technologies (e.g., ultrasonic, magnetometers, and visual sensors) and networking technologies (e.g., ZigBee, Wi-Fi, and cellular). It facilitates real-time monitoring and control by collecting real-time sensor data and integrating with other technologies such as machine learning, sensor fusion, and computing [11]. Several commercial parking systems have been developed such as SmartParking [12], PlacePod [13], and Sitraffic Scala [14]. These systems offer several features such as remote parking-spot booking, fee payment, interactive parking maps, and others. However, their main drawback is the high cost and the limited development capability for public developers since they are not open source. In addition, the current systems do not meet today’s parking needs and the expectations of smart city evolution.

The current systems employ a single gateway-centered solution using cloud computing. IoT data are collected and sent to the Internet for processing, which leads to the possibility of a single point of failure, data loss during network interruption, and high delays due to data flow across the network to the cloud. In addition, most of the implemented parking monitoring systems are locally operated and do not provide real-time information to the driver about where to find a parking space [15]. The utilized communication technologies are based on wired systems or short-range communication methods such as Wi-Fi, Bluetooth, or ZigBee, which are not reliable in most scenarios of indoor and outdoor parking. They also face many issues related to interference, energy consumption, and limited resources.

Moreover, different criteria have been considered for parking-spot selection, such as the preferences of users and operators. The existing systems consider the demand and driver preferences only. The selection decision must be based on a criterion that reduces congestion and maximizes parking utilization and, consequently, revenue. The pricing strategy, on the other hand, in parking lots, is usually based on a fixed rate per hour for short-term parking and a fixed subscription rate for long-term parking, which does not achieve a high revenue. The fixed rate is obtained periodically according to the previous occupancy rate. Such a strategy does not take advantage of the parking availability and demand, and hence it leads to sub-optimal pricing. Therefore, this paper reports on the design and development of a smart parking system based on a multi-layer IoT architecture to resolve the aforementioned issues. The system considers different parking plans, including a short-term parking plan with and without advance reservation and a long-term parking plan. The proposed system is evaluated through implementation and simulation of a selected area representing our case study (i.e., Kudai parking lot). The system has the following features:

• A multi-layer IoT architecture consisting of IoT, fog and cloud layers to overcome the limitations of single gateway-centered solutions. Distributed fog computing nodes are employed to process data locally and forward essential data only to cloud servers. Sensor nodes connect to fog nodes through energy-efficient LoRaWAN communication technology, except for the vision sensors which are connected through Wi-Fi technology. This is because LoRa communication offers a low data rate that is suitable for sensor nodes that do not continuously send large amounts of data.
• A parking-spot selection algorithm that considers arrival time to a parking spot as a parking selection criterion, to reduce waiting time and congestion and, consequently, air pollution. The arrival information for the parking lot, including the rate of entering and departing the parking lot, the parking availability rate, and vehicles’ GPS locations are considered. The visual sensor information at junctions is also used to obtain the congestion rate.
• Parking availability estimation that facilitates the parking reservation process with the aim of maximizing parking-lot utilization. Reservation is allowed a minimum of three hours in advance to give walk-in clients the chance of finding a parking spot and, consequently, to reduce traffic congestion at the parking-lot entrance.
• A hybrid pricing algorithm to maximize the parking revenue. The algorithm utilizes an hourly-rate pricing strategy for short-term planning and a dynamic pricing strategy for long-term planning. The dynamic pricing represents a dynamic subscription rate that is set to correspond with demand and revenue.

The rest of the paper is organized as follows. Section 2 discusses related studies on smart parking systems and highlights their limitations and the contributions of our proposed system. In Section 3, the proposed parking system is described, including the proposed multi-layer IoT architecture and the operation workflow, parking-spot selection, parking availability estimation, and hybrid pricing algorithms. Section 4 describes the details of the implementation and simulation evaluation for the case study considered, and the utilized hardware and software tools. The obtained results are also discussed and analyzed. Finally, the conclusions and suggestions for future work are presented in Section 5.

2. Related Work

Several review articles have been presented in the literature that explore, classify, and discuss the technical aspects of smart parking solutions [16,17,18,19]. This section discusses related smart parking systems from existing studies, obtained by searching using the keywords ‘smart parking’ and ‘IoT parking’ in several databases such as ISI Web of Science and Scopus. Searching using these keywords resulted in 316 articles, with 127 articles from the ISI Web of Science and 189 articles from Scopus. The duplicated articles from these two databases were removed, resulting in 275 final articles. Figure 1 shows the review methodology used to obtain the related articles considered.

The scopes of these articles address different issues, including application and usability [20,21,22], pricing and contracts [23,24,25], availability prediction and allocation [26,27,28], and others. The 275 articles were further scrutinized based on the problem scope, solution approach, and evaluation method. Applying the review methodology helped in extracting the 14 articles most relevant to the scope and objectives of this paper. Different criteria could be considered to classify the systems, including parking environment, provided services, or core sensing technique. Parking systems can be classified based on the core sensing technique into wireless-sensor-based systems, motion-sensor-based systems, and camera-sensor-based systems. This section will discuss only the smart parking solutions most related to the proposed solution in this article, i.e., wireless-sensor-based systems that utilize LoRa as the network infrastructure of the system.

A proof-of-concept implementation of a smart parking system with LoRa infrastructure has been presented in several papers [29,30,31]. The developed implementations showed that such a system is efficient in terms of energy, integrity, and scalability for parking monitoring and management in large cities. In [32], the system was implemented with an online reservation system for car parking lots at Universitas Hasanuddin. Similarly, the authors in [33] developed a smart parking system based on LoRa that contains a sensor module, a cloud server module, reservation application, and a third-party payment platform. The system was tested in two cities in Zhejiang province, China: Ningbo and Zhoushan. The experimental results showed an enhancement in monitoring and booking capabilities. However, the quality, security, and reliability of the LoRa communication were not tested in real parking lots in a complex urban environment.

A smart parking solution was proposed in [34] that combines Libelium smart parking sensors, LoRaWAN, and a cluster of Kubernetes with MQTT and MongoDB. The combination enhanced the availability, scalability, and portability of the smart parking system by overcoming the information-sharing bottleneck. The system accumulates all messages in the messaging server for further processing if the main server for information collection fails. Another smart parking solution with a pricing algorithm for revenue maximization was proposed in [35]. The price is dynamically set to balance the available and requested parking spots and ensure the minimum parking fee is charged. The solution comprises multiple sensors that recognize vehicles and obtain contextual and environmental information. Moreover, edge–cloud computing is utilized to minimize the network load and the number of gateways.

Other studies have proposed methods to enhance the interoperability of parking solutions. The system in [36] adopted an IoT gateway-centric architecture [37] that allows real-time interaction between all supported sensor devices and/or actuators through a LoRa gateway using the LoRa network. The gateway, in turn, transforms packets to the format acceptable to the server. Hence, there is no need for a network server to route packets to their destination. The received packets are then parsed by Spring functions and processed with data from the database if required, to finalize the findings and pass them to users. The payment functions for the parking system utilize the API payment highway. In [38], a novel framework-based Wise-IoT system [8] was developed for global interoperability and mobility of IoT applications and devices. The system was developed based on different IoT infrastructures (one was LoRaWAN) and two different interoperability layers. The system was implemented in two cities around the world: Busan and Santander. The generated sensor observations in Santander were sent on different instances of oneM2M and FIWARE IoT platforms, while in Busan, they were distributed using oneM2M as a back end. As a result, the smart parking developed for Santander could be used in a different location in Busan and vice versa.

For privacy preservation in parking systems, the authors in [39] proposed an enhanced LoRaWAN security protocol that provides basic connectivity functions and averts security issues. It prevents a malicious network server from breaking the end-to-end security between a device and its application server. The protocol was examined using different tools and the results showed that the proposed protocol overcomes two handshake options in terms of network latency and signaling overheads. In [40], a new method using a secure element was proposed to safely store keys and process the LoRaWAN protocol. The secure element handles security functions such as data encryption and message signing. In addition, an efficient integrity verification method was proposed for the executable in the main microcontroller unit, based on a secure element.

Table 1. A summary of the most relevant parking systems.

Research Study	Online Platform	Parking Navigation	Reservation Service	Parking Availability Estimation	Payment Platform	Tested Parking Area
Angelov, K.K. 2020.	√	√	x	x	x	None
Anshar, M., et al., 2020.	√	√	√	x	x	Campus parking
Shi, J., et al., 2017.	√	√	√	x	√	City parking
Barriga, J.J., et al., 2020.	√	√	√	x	√	City parking
Sotres, P., et al., 2018.	√	√	x	x	x	City parking
Proposed System	√	√	√	√	√	City parking

summarizes the most relevant related studies.

3. Proposed Smart Parking System

The proposed smart parking system monitors and manages parking lots to make the vehicle parking process more convenient and comfortable by guiding drivers to their parking spot with less congestion and a shorter traveling time. The system consists of cloud computing, fog computing nodes, a group of sensors, and parking management software to acquire and process the data related to parking booking, availability, and pricing. The components have wireless connection capability to send the data to the fog node, which processes the collected data. The system considers three parking classes based on the parking plan: (i) vehicles with a parking subscription, (ii) vehicles with an advance parking reservation, and (iii) vehicles without a parking reservation. The following sub-sections detail the parking system architecture and operation, parking availability estimation, parking-spot selection, and pricing algorithms.

Table 2. List of notations.

Symbol	Definition	Symbol	Definition
i	Edge lane	${\lambda }_i$	Traffic density on that edge
V	Vehicle number in an edge	$M_i$	Maximum capacity of vehicles on that edge
$C$	The total congestion rate of all edge lanes on the route	T	The total number of all edge lanes on the route
$S_i$	A parking spot	$S_j$	The current state of parking spot $S_i$
$p_i$	A parking lot	$Ca{p}_i$	Capacity of a parking lot
d	Discount percentage	r	Range of hours
$P_T$	The total parking price	$P_F$	The first-hour price rate
$P_s$	The price rate after the first hour	h	Total parking hours
N	The maximum value of ranges	$R$	The parking revenue
k	The number of available parking spots for subscriptions	$P_n$	The subscription price rate of nth parking lot.
$U_n$	The number of clients who afford a specific rate	$Rat{e}_m$	The maximum rate that mth driver affords

gives the list of the notations utilized throughout the paper.

3.1. Parking System Architecture and Operation Workflow

A multi-layer IoT architecture for the parking system manages and monitors parking lots efficiently and maintains a low congestion rate. The architecture overcomes the limitations of the traditional sensor–cloud architecture by employing distributed fog computing nodes to process data locally and forward essential data only to cloud servers, instead of forwarding all the data. This maintains fast processing and transmission of the required data only, to achieve a real-time application experience in which the data required for the general view or for long-term services (e.g., parking lots in different locations across a city or historical parking data) are transmitted to the cloud. The architecture consists of three layers: (i) IoT parking layer, (ii) fog layer, and (iii) cloud layer, as shown in Figure 2.

3.1.1. IoT Parking Layer

The lowest layer consists of a group of sensor nodes to monitor the parking lots by detecting vehicles and gathering data about the parking area. Different types of sensors could be utilized, placed either in the ground (e.g., electromagnetic sensors), in the ceiling, or in street pillars (e.g., ultrasonic and visual sensors). The most suitable sensor to be utilized is obtained based on the parking lot and its surrounding environment. Magnetometer sensors and thermal cameras are utilized in a parking lot that is exposed to different weather conditions, to detect variations in the magnetic field and differences in temperature. Visual sensors are preferred for more sophisticated parking areas or if they are already installed [41].

In this layer, our system employs several sensors and data acquisition devices including ultrasonic, magnetic, and visual sensors, radio-frequency identification (RFID), Global Positioning System (GPS) equipment, QR code readers and a parking management platform. For instance, visual sensors are placed at the entrance, exits, and junctions to provide useful information for parking-spot selection and to monitor parking rule violations. Solar panels connected to a rechargeable battery are used to supply the power required by the data acquisition devices. Sensor nodes communicate with fog nodes through energy-efficient LoRaWAN communication technology, while vision sensors communicate through Wi-Fi technology. This is because LoRa communication offers a low data rate (i.e., up to 37.5 kbps) which is suitable for sensor nodes that do not continuously send large amounts of data. LoRa technology facilitates long-range communication up to 5 km with 25 mW maximum transmission power [42]. The configuration parameters and frequency carriers of LoRa are set according to the local regulations.

3.1.2. Fog Layer

As mentioned earlier, the purpose of this layer is to provide a robust solution that achieves real-time control and analytics requirements by relocating some of the processing and analysis (e.g., data pre-processing, filtering, and compression) close to the lowest hierarchical layer. This includes the processes of parking-spot selection, parking availability estimation, and pricing in our proposed parking system. The fog layer is usually composed of several fog nodes where the process of a specific service relates to a specific node, according to its requirements. Fog nodes are defined as distributed computing entities that have processing capabilities where each node can be formed by one or more physical devices (e.g., network device, dedicated server, or computational server). Each node can simultaneously process multiple sensor nodes with the possibility of sensor-node handover if there is a high execution load or a connectivity problem. Moreover, a collaborative task allocation can be performed to share the computational load among fog nodes to reduce the overall operational latency.

3.1.3. Cloud Layer

The highest layer provides virtually unlimited storage and computational resources. The cloud layer facilitates several services for the proposed parking system, such as usage analytics, statistical and historical information, revenue monitoring, and automatic payment and management. The cloud layer also enables secure, real-time online parking reservation information and direction to the reserved parking through a parking platform running on the web or installed in a mobile device. An encryption technique could be employed in the cloud layer to hide the payment plan and driver information, to guarantee security and privacy. Moreover, historical, and long-term information could be used for big data analytics to enhance traffic management and smart city solutions, as well as to enable real-time feedback notification and emergency alerts.

The workflow of the proposed parking system is shown in Figure 3. The process starts by obtaining parking-lot data through sensor nodes and the parking management platform. After data acquisition, the physical variables of the vehicle are sent to the fog nodes, including parking reservation, arrival, and vehicle detection. The fog nodes process the collected data every 10 ms to ensure accurate decisions and minimize the usage of resources and processing capabilities. The acquired data are processed to determine the information on arrival, parking availability, parking matching, and parking reservations. Based on the data, four different algorithms are executed including parking availability estimation, security alerts, dynamic pricing, and parking-spot selection. A detailed description of theses algorithms is given in the following sub-sections. The outcome of the algorithms is transmitted to the cloud computing layer through network devices and, consequently, transmits the parking information to the parking management platform.

3.2. Parking-Spot Selection Algorithm

The parking-spot selection is initiated upon vehicle entry into the parking lot. The parking-spot selection process uses an optimization algorithm that selects the optimal parking with the aim of minimizing the arrival time to a parking spot. The algorithm is applied to vehicles with and without a parking reservation but not to vehicles with a parking subscription. It utilizes the information on parking arrival and reservation, including the rate of entry and exit, parking availability rate, and the vehicle’s GPS location. In addition, the visual sensor information at junctions will be used to obtain the congestion rate using the congestion model presented in [43]. The entrance point is used as a navigation start-up to select the parking lot, which is determined during the vehicle arrival. The algorithm performs a forward search process in which the entrance point is located and then the expected arrival time to an available parking spot is calculated. Moreover, a backtracking process is performed to compute the arrival time from the parking spot back to the preceding entrance point.

An example of the parking-spot selection process is shown in Figure 4. Each road has two edge lanes and a maximum capacity for vehicles. For an edge lane i, the density ${\lambda }_i$ of the traffic is calculated as

$${\lambda }_i=V/M_i$$

(1)

where V represents number of vehicles in the edge and $M_i$ represents the maximum capacity of vehicles in that edge. The density is shown as a percentage in Figure 4. The total congestion rate of all edge lanes on the route is calculated as

$$C={{\displaystyle \sum }}_{i=1}^j\raisebox{1ex}{${\lambda }_i$}\!\left/ \!\raisebox{-1ex}{$T$}\right.$$

(2)

where T is the total number of all edge lanes on the route. The search for the optimal parking spot starts from a given entrance node to an available parking spot that achieves the minimum travelling time. Accordingly, the search graph consists of a root node which is the entrance point, and the next-level nodes which are all the junctions that can directly be accessed from the previous level (i.e., first root node) and so on, until candidate available parking spots are identified. The graph constitutes a tree-like view in which the maximum depth represents the number of junctions and the candidate parking junction within this depth. The optimal path with minimum travelling time can be found using Dijkstra’s algorithm [44].

3.3. Parking Availability Estimation

Parking availability estimation is proposed to facilitate the parking reservation process. Reservation is allowed a minimum of three hours in advance if it is estimated that parking spots will be available at the requested time. This maximizes parking-lot utilization and gives vehicles without a prior parking reservation the chance to find a parking spot, consequently reducing traffic congestion at the parking-lot entrance. The parking availability at the current instant in time is known by the fog nodes in the system. However, this information is not sufficient for estimating the parking availability in the near future because the vehicle arrival rate fluctuates in different seasonal periods. The traffic fluctuation can be predicted using predictive analytics from the historical seasonal data, which are collected from sensors at parking entrances and junction poles. These historical data are stored in the cloud and categorized according to seasonal periods into several instances. The periods must be small enough (e.g., one minute) to minimize the variations in parking dynamics. These data are used to develop a stochastic model based on a Markov process representing the randomly changing available parking spots.

The Markov model infers the parking availability in a future period from the historical parking availability information in similar periods. The model obtains several parameters for each parking lot including the observation time window, arrival rate, departure rate and state transition matrix.

Table 3. Parking data sample.

$\mathbf{Parking}\mathbf{Lot}{\mathit{p}}_{\mathit{i}}$
1 Season			Period (Time)	Available Spots (Average)
Year	Month	Day
1439	Safar	5	9 h 56 m	987
1440	Safar	5	9 h 56 m	970
1441	Safar	5	9 h 56 m	950
1442	Safar	5	9 h 56 m	987
1443	Safar	5	9 h 56 m	960

¹ Note: Makkah parking lots form the case study in our work, where the historical parking data fluctuate according to the Hijri calendar; thus, this calendar is used in the system.

shows an example of parking lot data, where multiple historical one-minute-period observations in similar seasons are averaged. The period is set to be short in order to obtain discrete state changes in a parking lot modelled over a time window of five minutes with fixed arrival and departure rates. The reason for choosing a short period is to justify the assumption that arrival and departure rates are fixed within each observation window; however, variations in arrival and departure rates are considered across observation windows. A single state transition matrix that represents the parking dynamics information is obtained for each observation window size.

For each parking lot, parking states are determined in which each state represents the parking availability range. The future availability state $P\left(S_i|S_j\right)$ of a parking spot $S_i$ is obtained using the classic Markov chain model and Kendall’s notation, where $S_j$ is the current state [45]. The Poisson distribution is utilized in the simulation to represent the arrival process in periods with a fixed mean value for the number of entering and departing vehicles to/from a parking lot over a single observation period. The proposed parking availability estimation uses five state ranges for a parking lot, from the highly occupied state $S_1$ to the highly available state $S_5$. Figure 5 shows an example of a state transition matrix for a parking lot with capacity $Ca{p}_i=1000$, which is derived from historical data with a five-minute period of observation. A normalized transition matrix in terms of probabilistic weights is also illustrated in Figure 5.

Algorithm 1: Hybrid pricing algorithm.

BEGIN; If short-term parking plan is selected then │   Process pricing for short-term parking plan; else if long-term parking plan is selected then │  Process pricing for short-term parking plan; end; (1) process pricing for short-term parking plan; Determine the price of the first hour; Determine the parking hours range; Calculate the price of the later hours according to the applied discount percentage based on the determined parking hours range; Calculate the total price of the short-term parking which is sum of the price of the first and later hours; (2) process pricing for long-term parking plan; Clients bid once or more during selected seasonal periods; Determine the optimal pricing rate that matches demand and revenue; Prioritize the clients based on their bidding value and time stamp in a descending order;

3.4. Hybrid Pricing Algorithm

An algorithm was developed to facilitate the pricing strategy for two types of parking plans: (i) a short-term parking plan (i.e., parking with and without a reservation) and (ii) a long-term parking plan (i.e., monthly and annual parking subscriptions). The hybrid pricing includes an hourly-rate pricing strategy for the short-term plan and a dynamic pricing strategy for the long-term plan. Algorithm 1 shows the pseudocode of the hybrid pricing algorithm.

The hourly pricing rate considers the possibility of specifying certain discount rates. It sets a fixed price rate for the first hour, then the price rate of the later hours is calculated based on ranges in which a specified discount percentage (d) is applied upon exceeding a specified range of hours (r). The total parking price is calculated as follows:

$$P_T=P_F+P_s\left(h-1\right)-Xd{P}_s\left(h-1\right)$$

(3)

where $P_T$ is the total parking price, $P_F$ is the first-hour price rate, $P_s$ is the price rate after the first hour, h is total parking hours, and X is calculated as:

$$X=Min\left(\lfloor \raisebox{1ex}{$h$}\!\left/ \!\raisebox{-1ex}{$r$}\right.\rfloor , N\right)$$

(4)

where N is the maximum value of ranges. For instance, if parking is required for a total of 20 h, the first-hour parking rate is USD 10, the rate after the first hour is USD 5, and there is a 10% discount for each of 5 ranges where each range consists of 3 h, the total parking price will be

$$P_T=10+\left(5\ast 19\right)-\left(5\ast 0.1\ast 5\ast 19\right)=\$52.5$$

For long-term parking (i.e., subscriptions), a dynamic subscription rate is allocated to correspond with demand and revenue, similarly to [46]. The objective of the strategy is to optimize the parking revenue $R={\displaystyle \sum }_{n=1}^k{P}_n$ where k is the number of parking spots available for subscription and $P_n$ is the subscription price rate of the nth parking lot. This can be achieved by enabling bidding once or more times during selected seasonal periods. The subscription price rate is obtained by firstly allocating the maximum bidding value as the price rate, then reducing it to a rate that matches demand and revenue. For instance, in the scenario where 20 clients bid USD 200 monthly, 3 clients bid USD 150 monthly, and 7 drivers bid USD 90 monthly, the optimal pricing rate will be USD 150 monthly. A maximum bid value will be pre-specified by the parking management to ensure fairness. Upon setting the subscription price rate, the clients who can pay the rate $U_n$ are prioritized based on their bidding value and time stamp in a descending order. The optimization algorithm and maximization objective can be expressed as

$$\begin{array}{l}\mathrm{Maximize} R\\ \mathrm{Subject} \mathrm{to}:\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}k\le U_n\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}Rat{e}_m\ge P_n ; \forall n\le k\end{array}$$

(5)

where $Rat{e}_m$ is the maximum rate that the mth driver will pay. The sorting algorithms Merge Sort or Heapsort [35] can be used to search for the optimal maximum value, due to their low complexity.

4. Implementation and Evaluation

To evaluate the proposed smart parking system, Makkah city parking lots near the Holy Mosque were considered as the case study. Specifically, the parking lot in the Kudai district was selected for simulation and implementation. There are 13 parking lots in Makkah city, with a total area of a million and a half square meters, and they can take up to 45,000 vehicles. Kudai parking lot’s area is around 74,000 ${\mathrm{m}}^2$ with total of 2500 parking spots. Figure 6 shows parking lots and transportation stations, including Kudai parking lot. The traffic is highly congested during the Hajj and Umrah seasons, but the system is expected to reduce traffic congestion, especially at the parking-lot entrances. According to a general statistical authority, the number of vehicles entering Makkah during the 2019 Hajj season was around 32,978 [47]. The Saudi vision aims to double the total number of pilgrims for the Hajj and Umrah season by 2022, which in turn requires better traffic and parking management.

As a proof of concept, a simplified version of a part of the Kudai parking lot was selected for experimental evaluation, as shown in Figure 7. Note that some of the components are not shown in the figure as they are placed at the back of the parking board. The visual sensor was not included in the proof-of-concept implementation for simplicity purposes. The hardware components of the experiment included HC-SR04 ultrasonic and geomagnetic sensors, an RFID-RC522 reader module, an S50 RFID card, an Adafruit Feather 32u4 with LoRa radio modules, a rechargeable Li-ion battery, a compact photovoltaic panel, LEDs, Raspberry Pi 3, and an HP workstation.

A Feather 32u4 LoRa board with an 868/915 MHz radio module was employed for LoRa communication. The serial RX/TX pins of ultrasonic, geomagnetic, and RFID sensors were connected to the Arduino serial RX/TX pins on the Adafruit Feather. Data were read from the Arduino serial RX and transmitted through the radio. The data are received by the onboard LoRa radio and sent through another serial port to the Raspberry Pi, which was used as a fog node in the experiment. The node collects, processes, and sorts the data locally, and forwards the data to the back-end server. It processes parking-spot selection, parking availability estimation, and the hybrid pricing algorithm. A HP workstation running Ubuntu was employed for back-end analysis to monitor and analyze the network’s overall performance. It processes the historical data to estimate the parking availability and accordingly allows or does not allow parking reservation. The communication module and the sensors are supplied with power through a rechargeable Li-ion battery that is charged by a compact photovoltaic panel. The Blynk app could be used to display the output of the algorithms executed in the fog node.

A simulation evaluation was conducted to investigate the benefits of the proposed parking system, specifically the slot selection and hybrid pricing algorithms. The free open-source simulator, Simulation of Urban MObility (SUMO) [48] was utilized to define each vehicle explicitly with a specific route in the map. The default behavior of vehicles in SUMO is to drive with highest specified speed with obstacle avoidance. It also contains a parking package to define a parking area and to route vehicles to a specific parking spot [49]. The area of the Kudai parking lot simulated was taken from OpenStreetMap (OSM) and inserted into SUMO to represent the simulation area. Figure 8 shows the Kudai parking lot in the SUMO simulator.

The system was compared with the traditional parking approach in which the driver starts searching for an available parking spot from the current location until one is found. A parking lot with a maximum capacity of 150 parking spots was considered, where 10 and 5 vehicles/minute were the arrival and departure rates, respectively. The initial parking availability was produced randomly in a uniform distribution with a 90% maximum rate. The parking lot was considered full if more than 80% of parking spots were occupied. The measured performance metrics for simulation evaluation were arrival time, searching time, and parking revenue. The arrival time is the time spent by a vehicle in the parking area from the entrance until a selected parking slot is reached, while the searching time is the time spent searching for a parking spot. The parking revenue, on the other hand, is the total revenue from all parking spots with different parking plans in a parking lot.

Figure 9 illustrates the arrival time considering different congestion rates and available parking spots, using the proposed system and the traditional approach. The simulation was executed until an available spot was obtained. Figure 9a shows the arrival time with only one available parking spot, with a congestion rate between 0.1 and 0.9. It shows that the arrival time using the proposed parking-spot selection algorithm was significantly less than for the traditional parking search approach. The traditional search approach consumes around 20% to 60% more time than the proposed algorithm. Although the proposed algorithm always outperformed the traditional approach, the arrival time gap between the two approaches became less with a higher congestion rate because it was difficult for vehicles to move fast at all junctions. In Figure 9b, the arrival time is shown with various available parking spots from 1 to 10 parking spots and a fixed congestion rate of 0.8. The proposed algorithm had an arrival time that was lower than the traditional approach in all cases. When only one parking spot was available, the arrival time of the proposed algorithm was notably lower compared to the traditional approach which searches blindly for all parking spots in the area until an available spot is found. However, the difference between the arrival times decreased gradually with increasing numbers of parking spots because more available spots could be found.

Figure 10 shows the searching time with various available parking spots from 1 to 10 parking spots and a fixed congestion rate of 0.8. The results show that the searching time metric and the arrival time have a similar pattern because the searching time is most of the arrival time period. The proposed algorithm had a lower searching time and arrival time; notably lower when only one parking spot was available. The difference between the two approaches became less when more parking spots were available.

The revenue for hybrid and fixed pricing algorithms was evaluated considering different parking reservation requests. Here, a parking lot with a maximum capacity of 150 parking spots was considered, in which 50 spots were allocated for the long-term plan and 100 spots for the short-term plan. Moreover, the number of parking spots available for subscription was considered to be less than the number of the clients who could pay the default subscription rate. The fixed pricing rate was USD 10 per hour in the short-term plan and USD 2000 per month in the long-term plan. For the short-term plan, the dynamic pricing was USD 10 for the first hour with a 10% discount for the remaining hours, while for the long-term plan the bidding rate was randomly higher than the default rate. Figure 11 shows the total revenue from all parking plans, including the short-term and long-term parking plans, compared to fixed pricing. The occupation rate was varied from 10% to 100% for both parking plans. The dynamic pricing scheme increased the revenue notably for the long-term plan, while it was less than the fixed pricing revenue for the short-term plan, due to the discount.

5. Conclusions

Smart cities aim to improve the quality of life of their residents in different aspects of life including transportation and travel services. In this context, smart parking systems help drivers to obtain and reserve a parking spot in advance. In this paper, a smart parking system was proposed based on a multi-layer IoT architecture with a LoRa communication interface, to overcome the limitations of the current parking systems. The system considered different parking plans including a short-term parking plan with and without advance reservation and a long-term parking plan. The acquired parking data were processed through a fog computing node to facilitate obtaining the required real-time parking data. Moreover, a dynamic pricing algorithm was introduced with aim of maximizing revenue for the parking authority. A novel algorithm to obtain the optimal parking spot with the minimum arrival time was also introduced. The proposed system was evaluated through implementation and simulation of a selected area representing our case study (i.e., Kudai parking lot). The results showed that the parking system enhanced the parking arrival time and revenue. In future work, we plan to develop and install a test field for the proposed parking system in our case study.