# Sharing with Caution: Managing Parking Spaces in Vehicular Networks

Thierry Delot, Sergio Ilarri, Sylvain Lecomte, Nicolas Cenerario

► To cite this version:

Thierry Delot, Sergio Ilarri, Sylvain Lecomte, Nicolas Cenerario. Sharing with Caution: Managing Parking Spaces in Vehicular Networks. Mobile Information Systems, 2013, 9 (1), pp.69-98. 10.1155/2013/703830. hal-03594510

HAL Id: hal-03594510

https://uphf.hal.science/hal-03594510

Submitted on 28 Apr 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Sharing with caution: Managing parking spaces in vehicular networks

Thierry Delot<sup>a,c,*</sup>, Sergio Ilarri<sup>b</sup>, Sylvain Lecomte<sup>a</sup> and Nicolas Cenerario<sup>a</sup>

**Abstract.** By exchanging events in a vehicular ad hoc network (VANET), drivers can receive interesting information while driving. For example, they can be informed of available parking spaces in their vicinity. A suitable protocol is needed to disseminate the events efficiently within the area where they are relevant. Moreover, in such a competitive context where each vehicle may be interested in a resource, it is crucial not to communicate that resource to each driver in the vicinity. Otherwise, those drivers would waste time trying to reach a parking space and only one of them would be fulfilled, which would lead to a poor satisfaction in the system.

To solve this problem, we detail in this paper a reservation protocol that efficiently allocates parking spaces in vehicular ad hoc networks and avoids the competition among the vehicles. We have integrated our protocol within VESPA, a system that we have designed for vehicles to share information in VANETs. An experimental evaluation is provided, which proves the usefulness and benefits of our reservation protocol in both parking lots and urban scenarios. Besides, we present an in-depth study of the state of the art on this topic, that shows the interest and the originality of our approach.

**Keywords:** Vehicular networks, data sharing, parking space allocation

## 1. Introduction

Nowadays, there is a great interest in developing systems to assist drivers on the road, providing them with different types of relevant information. VANETs rely on the use of short-range networks (a few hundred meters), like IEEE 802.11, Ultra Wide Band (UWB), or WAVE (IEEE 802.11p, IEEE 1609), for vehicles to communicate [27] and provide bandwidth in the range of Mbps. Using such communication networks, the driver of a car can receive information from its neighbors. Many pieces of information can be exchanged in the context of inter-vehicle communications, for instance to warn drivers when a potentially dangerous event arises (an accident, an emergency braking, an obstacle on the road, etc.) or to try to assist them (with information about traffic congestions, real-time traffic conditions, etc.). As opposed to communication approaches based on a support infrastructure or a wide-area network such as a 3G cellular network, the use of ad hoc communications can facilitate a quick exchange of data with neighboring nodes at no cost, which will encourage the cooperation among close vehicles. VANETs have attracted an intensive research attention (for some recent examples, see [19,35,44]).

<footnote><sup>a</sup>University Lille North of France, Valenciennes, France</footnote>

<footnote><sup>b</sup>IIS Department, University of Zaragoza, Zaragoza, Spain</footnote>

<footnote><sup>c</sup>INRIA Lille Nord Europe, Villeneuve d'Ascq, France</footnote>

<footnote>*Corresponding author: Thierry Delot, University Lille North of France, LAMIH UMR UVHC/CNRS and INRIA, Le Mont Houy, 59313 Valenciennes, France. Tel.: +33 3 27 51 19 56; Fax: +33 3 27 51 19 40; E-mail: Thierry.Delot@univ-valenciennes.fr.</footnote>
Among the different types of information that a driver may find interesting, information about available parking spaces is one of the most valuable. Finding an available parking space is indeed stressful, time-consuming and contributes to increasing traffic; so, according to [23], searching for parking spaces is a basic component of urban traffic congestion (between 5% and 10% of the traffic in cities and up to 60% in small streets). Besides, it leads to fuel consumption and environment pollution due to the emission of gases. Some studies emphasize the costs of searching for parking spaces. For example [10], indicates that nearly one out of two vehicles on the move are searching for a parking space. Similarly, from a study by the Imperial College in London (Imperial College Urban Energy Systems Project) it is known that, during congested hours, more than 40% of the total fuel consumption is spent while looking for a parking space. As a final example, according to a study by Donald Shoup [41], in Westwood Village (a commercial district next to the campus of the University of California, Los Angeles) parking searching leads every year to about 47000 gallons of gasoline, 730 tons of CO2 emissions and 95000 hours (eleven years) of drivers' time. Moreover, the Directive 2010/40/EU of the European Parliament sets among the priority areas for Intelligent Transport Systems the provision of both information and reservation services for (safe and secure) parking places for trucks and commercial vehicles.

Vehicular networks bring new opportunities but also significant challenges from the data management point of view [19]. The work presented in this paper is an extension of VESPA [12, 16, 18, 20] (Vehicular Event Sharing with a mobile P2P Architecture, http://www.univ-valenciennes.fr/ROI/SID/tdelot/vespa/), which is a system developed to share information about events in inter-vehicle ad hoc networks. In such environments, both push-based (data dissemination) and pull-based (query dissemination) approaches [46] have been proposed. On the one hand, with a push-based approach the vehicles receive data from their neighbors and then it is possible to process queries locally over the data received in order to provide interesting information to the driver (relevant for that time and location). On the other hand, with a pull-based approach a query is actually disseminated over the vehicular network in order to collect the relevant data from the vehicles. Push-based solutions are more frequently used. So, data about the events occurring on the road or available resources such as parking spaces may have to be communicated to a potentially large set of vehicles, depending on the relevance of the data to the drivers. As opposed to other proposals, VESPA aims at supporting all types of events. Thus, VESPA proposes a dissemination protocol [12] and a relevance estimation mechanism [16,20] not only suitable for stationary events (e.g., an emergency braking, an accident, etc.) but also for mobile events (e.g., an emergency vehicle asking preceding vehicles to yield the right of way, a vehicle with a non-functioning brake light, etc.). When supporting such mobile events, the set of vehicles for which the event information is relevant evolves according to both the movements of the vehicle generating the event (e.g., a vehicle that brakes suddenly) and the other vehicles involved (in the previous example, the vehicles behind). Besides, the direction of traffic is also of major importance in establishing the relevance of shared information, even for non-mobile events (e.g., consider a traffic jam affecting only the vehicles moving in one direction).

In this paper, we focus on the exchange of information about available parking spaces using VESPA. As opposed to other types of events, it is not enough to indicate the presence of the event to the driver. Indeed, if the same information (i.e., the same available parking space) is presented to several interested drivers, this will lead to a competition between the vehicles and only one of them will be able to take that parking space. It is so crucial to propose a solution for parking spaces to be "reserved". By reservation we understand the fact that the parking space should be communicated to only one driver, as there is no way to physically prevent other vehicles from taking a public parking space; so, thanks to the reservation protocol, the information about an available parking space is disclosed to a single driver. The fully decentralized environment imposed by vehicular networks makes that reservation process particularly
challenging since vehicles keep moving and no reliable link or central server can be used. Although other solutions have been proposed to disseminate information about available parking spaces using short range communications (e.g., [49]), to the best of our knowledge, no other work has tackled the problem of parking space reservation in VANETs. This paper extends [17]; among the extensions, we could mention an extensive study of related proposals, an experimental evaluation in urban environments, and an analysis of reliability issues.

The structure of the rest of this paper is as follows. In Section 2, we introduce the representation of events in VESPA and describe how the relevance of parking spaces received by vehicles is evaluated using the concept of Encounter Probability. In Section 3, we present our reservation protocol. In Section 4 we discuss some reliability issues. In Section 5, we evaluate experimentally our solution. In Section 6, we compare our work with other approaches by presenting a detailed study of the state of the art (including both research proposals and existing systems). Finally, in Section 7 we summarize our conclusions and indicate some ideas for future research.

## 2. Relevance of events

One of the major problems in inter-vehicle applications is how to estimate the relevance of the events received. The traditional approach is to define a relevance function used to determine whether an event received should be considered or ignored. The relevance function used in VESPA, called *Encounter Probability (EP)*, which estimates the likelihood that a vehicle is going to meet a certain event, is used to verify whether an event is relevant for a vehicle or not. Thus, when an event is received by a vehicle, the EP for this event is computed. If the EP computed is higher than a certain *storage threshold (ST)* then the event is stored in a local data cache, as it is considered *relevant for the vehicle*. If the EP is also higher than a certain *relevance threshold (RT, with RT ≥ ST)* and besides the driver is interested in that type of event (because the event is interesting for any driver – e.g., an event indicating an accident – or because the driver submitted a query to retrieve events of that type), then the event is *relevant for the driver* and has to be communicated to the driver. Finally, a *dissemination threshold (DT)* is also used to decide whether the event should be communicated to other neighboring vehicles or not.

In the following, we first describe how events are represented and then we briefly summarize the method used to compute the *Encounter Probability (EP)*.

### 2.1. *Representation of events in VESPA*

VESPA relies on a generic structure to represent events whatever their type (both *stationary* vs. *mobile* and *direction-dependent* vs. *direction-independent* events are considered). Each event is described using several attributes: 1) a unique *Key* set by the event source, 2) a *Version* number allows to distinguish between different updates of the same event (e.g., used to indicate that a mobile event has changed its location), 3) an *Importance* value helps to determine the urgency of presenting that information to the driver (e.g., accidents that may affect the driver have a high importance), 4) a *CurrentPosition* indicates the time and place for the data generated, 5) a *DirectionRefPosition* and a *MobilityRefPosition* store preceding reference positions used to compute an Encounter Probability, 6) a *LastDiffuserPosition* and a *HopNumber* contain the location of the last vehicle which relayed the message and the number of rediffusions of the event (for purposes of the dissemination protocol, as explained in [12]), and 7) a *Description* field contains additional information for the driver.
<table><caption>Table 1
Example of dissemination of an available parking space</caption><thead><tr><th>Key</th><th>Vrs</th><th>Imp</th><th>CP</th><th>LDP</th><th>Hop</th><th>Desc</th></tr></thead><tbody><tr><td>v1e1</td><td>1</td><td>1</td><td>50°19'15.91 N<br>3°30'51.11 E<br>10h25m17s</td><td>-</td><td>0</td><td>Available parking space</td></tr><tr><td>v1e1</td><td>1</td><td>1</td><td>50°19'15.91 N<br>3°30'51.11 E<br>10h25m17s</td><td>50°19'15.91 N<br>3°30'51.11 E<br>10h25m17s</td><td>1</td><td>Available parking space</td></tr><tr><td>v1e1</td><td>1</td><td>1</td><td>50°19'15.91 N<br>3°30'51.11 E<br>10h25m17s</td><td>50°19'17.51 N<br>3°30'54.71 E<br>10h25m18s</td><td>2</td><td>Available parking space</td></tr></tbody></table>

The type of the event (stationary or mobile, direction-dependent or not) is not explicitly represented as an attribute of the event, as it can be inferred from some of the other message fields. Thus, when dealing with a stationary object/event, the *MobilityRefPosition* will always be set to *null*. Similarly, for non-direction-dependent events the value of *DirectionRefPosition* will be set to *null* to allow the identification of such type of event.

### 2.1.1. Example: Disseminating the availability of parking spaces

The protocol used in VESPA to disseminate information about available parking spaces and other types of events is described in detail in [12]. It aims at delivering events to potentially interested vehicles and relies on the concept of EP. Indeed, the probability that an event relevant for a vehicle is also relevant for its neighbors is high. So, when the EP computed for the event reaches the dissemination threshold, the dissemination of the event has to be continued in the network. Such an EP-based dissemination protocol ensures the adaptivity of the dissemination of an event according to its type. This is indeed crucial when several types of events are considered (e.g., the information about an available parking space has to be broadcasted to all surrounding vehicles whereas the information about an emergency braking should only be diffused to the vehicles behind).

As an example, we illustrate in Table 1 several steps of the diffusion of an event representing an available parking space using the dissemination protocol that we introduced in [12]. In the table, *Vrs* represents the version number, *Imp* the importance of the event, *CP* the current position, *LDP* the last diffuser's position, and *Desc* the description of the event. The first row represents the message emitted by a vehicle leaving a parking space or by a static sensor detecting the car leaving. None of the fields corresponding to the reference positions are filled here because of the type of event (*DirectionRefPosition* and *MobilityRefPosition* are both *null* for stationary non-direction-dependent events like available parking spaces), and so they are not shown in Table 1. The second row presents the message generated by a vehicle relaying the message presented in the first row of the table; the only attributes modified are the *HopNumber*, increased because the message is relayed, and the *LastDiffuserPosition*, corresponding to the position of the previous sender of the message (i.e., the generator of the event). The third row shows a next rediffusion of the message. For simplicity, only the longitude and latitude (and not the altitude) of GPS positions are shown.

### 2.2. Computation of the EP

In this section, we briefly summarize the way the EP is computed in VESPA. Actually, there are two different methods considered. The first method does not require any road maps or other information
about the environment and estimates future locations of vehicles and events based on geographic vectors, in order to estimate the probability that they will meet [16]. The second method attempts to achieve a higher accuracy by exploiting the information available in real road maps [20]. For more details about the computation of the Encounter Probability, along with an evaluation of its benefits, we refer the interesting reader to [12,16,20].

### 2.2.1. Computation of the EP based on geographic vectors

In order to compute the Encounter Probability between a vehicle and an event, two movement vectors are defined for a vehicle (computed by sampling the vehicle's locations periodically): the direction vector and the mobility vector. The direction vector allows estimating future positions of the vehicle on a short term, whereas the mobility vector captures an overall impression of the vehicle's direction and allows to estimate future positions on the long term. Each vehicle can compute its direction vector and its mobility vector easily. Similarly, each vehicle can compute the mobility and direction vectors of the events it receives. For that purpose, it uses the data associated to the events, and more precisely the CurrentPosition attribute and either the DirectionRefPosition or the MobilityRefPosition attribute, respectively. Finally, for each event, a vehicle's mobility vector (and direction vector) in relation to the event is computed by the vehicle, so that managing a single mobility and direction vector for each couple <vehicle, event> is enough.

Then, the computation of the EP is based on four factors: the minimal geographical distance between the vehicle and the event over time ($\Delta d$), the difference between the current time and the time when the vehicle will be closest to the event ($\Delta t$), the difference between the time when the event is generated and the moment when the vehicle will be closest to the event ($\Delta g$), and the angle between the direction vector of the vehicle and the direction vector of the event (represented by a colinearity coefficient $c$). These elements are weighted by considering different penalty coefficients ($\alpha, \beta, \gamma$ and $\zeta$) and aggregated to compute a value for the EP:

$$EP = \frac{100}{\alpha \times \Delta d + \beta \times \Delta t + \gamma \times \Delta g + \zeta \times c + 1}$$

For more details about the computation of the EP with geographic vectors, please see [16].

### 2.2.2. Computation of the EP based on maps

The information used in the previous method can be noisy, as for example the vehicle could abruptly change its direction at any time due to the constraints imposed by the road network infrastructure. So, we have proposed a second method to compute the EP when digital road maps are available. The goal is to try to compute the EP in a more precise way. This method is based on the estimation of the TTL (Time to Live) of an event, which is the time interval during which the event will be valid, and on the distinction between two different types of events: attraction events and repulsion events. Attraction events represent events that the driver would like to reach (e.g., in this paper parking spaces); for them, a Reachability Probability (ReachP) is defined based on the TTL and the time needed to reach the event by following the shortest path between the vehicle and the event (TTR). Repulsion events are events that the driver would like to avoid (e.g., traffic congestions or accidents); for them, a Need to Escape Probability (NeedEsP) is defined based on the TTL and the time needed by the vehicle to reach the last intersection that offers the vehicle an alternative route to avoid the repulsion event (TTE). The value of the EP is computed as ReachP or NeedEsP depending on the type of event:

$$ReachP = \begin{cases} 100 & \text{if TTL} > TTR \\ 0 & \text{otherwise} \end{cases}$$
$$NeedEsP = \begin{cases} 100 & \text{if TTL} > TTE \\ 0 & \text{otherwise} \end{cases}$$

According to experiments performed in the context of VESPA, this method to compute the EP can increase the accuracy. Nevertheless, the approach based on geographic vectors will also behave well in scenarios where the information about road maps may be unavailable. For more details, see [20].

### 3. Reservation protocol for parking spaces

In Section 2, we have described how to estimate the relevance of events. For most events, these mechanisms can be used efficiently to disseminate the events in the vehicular network to warn drivers. However, disseminating information about an available parking space with the basic VESPA approach is not enough, as this would lead to competition between vehicles to try to take that space. So, in this section, we present a solution to allocate available parking spaces in VANETs.

Coordinating different vehicles in vehicular ad hoc networks for them to choose one vehicle to which the parking space will be allocated is not an easy task. Indeed, no centralized server is available in environments where vehicles only communicate through short range communication networks. Moreover, all the vehicles have the same importance/role. So, we propose in the following a protocol in which a coordinator vehicle is chosen for each parking space. The role of such a coordinator is to collect, from the neighbors interested in finding an available parking space, the necessary information to decide to which vehicle the resource will be allocated. In the following, we will call “reservation” the process consisting of allocating parking spaces to vehicles. Our goal is to ensure that the information about a parking space is shown only to the driver of the vehicle that is chosen to occupy it, in order to minimize competition.

#### 3.1. Basics of the protocol

Using vehicle-to-vehicle communications, a vehicle can inform the other surrounding ones when it is about to leave a parking space. Therefore, a message describing the event “available parking space” is generated and broadcasted using VESPA, as explained before. To avoid causing an unnecessary competition among vehicles, a suitable reservation protocol should aim at:

- Indicating to the driver an available parking space reserved for his/her vehicle (and not a list of all the received available parking spaces).

- Maximizing the probability that the parking space will still be available when the driver arrives there.

- Maximizing the use of resources (by avoiding that a parking space remains available if there are vehicles searching in its vicinity).

- Ensuring a fair use of resources (i.e., it should be equitable and avoid situations where a vehicle has consistently higher priority than others).

- Minimizing the actions that the driver has to perform, with two goals: 1) not to disturb her/him while driving, and 2) to prevent the drivers from disseminating themselves misleading information that they could use to their own advantage (i.e., to obtain a parking space before the others).

- Avoiding network congestion.

Our solution to reserve parking spaces relies on the election of one coordinator per available parking space (i.e., a vehicle with a temporary particular role in the allocation of an available space). The coordinator is responsible for the allocation of the parking space to a vehicle according to a predefined policy.
It should be noted that if several coordinators were in charge of the same parking space, the information
could be disseminated faster, but this would lead to the competition situations that we want to avoid.
In this section, we detail how our protocol works for the case where there are vehicles interested in the
resource in the communication range of the vehicle diffusing it, and in Section 3.2 we explain how the
advertisement range can be extended (if needed) by switching the coordinator.

At first, the coordinator is the vehicle that leaves the parking space.<fnref n="1" /> It sends a message to inform the vehicles in its communication range that a parking space is available. Then it waits for potential answers. Among the vehicles receiving the information, only those interested in the parking space answer to the coordinator. So, each vehicle receiving a notification about an available parking space has to verify if that information is relevant. For this purpose, the vehicle computes the Encounter Probability (presented in Section 2) for the event received, to estimate if it can reach the space while it is still estimated available. In that case, it declares its interest in the parking space. Each interested vehicle $v_i$ provides to the coordinator its vehicle's identifier and the information necessary for the coordinator to choose the vehicle to which the resource has to be allocated, such as (depending on the allocation policy) the time $t_i$, corresponding to the current duration of the search of a parking space for that vehicle.

After a period of time $T$ (amount of time during which the coordinator waits for answers from interested vehicles), the coordinator chooses, among the vehicles that answered, the one for which the parking space is “reserved” (i.e., the one whose driver will receive the information about the parking space, including its geographic coordinates). Different policies may be applied to choose the vehicle to which the parking space should be allocated. The choice of an appropriate allocation policy will be further discussed in Section 5, in the context of an experimental evaluation; summing up, we consider that an appropriate policy could be to assign the parking space to the vehicle with the highest EP (to maximize the probability to find it free when it reaches it). Finally, the vehicle sends a message to the coordinator to confirm that it will take the parking space. This confirmation message avoids losing parking spaces: in case the chosen vehicle does not accept the parking space (or if it does not receive the allocation message), another vehicle is chosen by the coordinator. This exchange will be performed in a short time.

The flow charts of the algorithms executed by the vehicles searching for a parking space and the coordinator are detailed in Figs 1 and 2, respectively. Regarding Fig. 1, the method *declareInterest* is executed when a vehicle searching for a parking space receives an available parking space event (*apse*) from a coordinator and *confirmInterest* is executed when a vehicle is informed by a coordinator that it has been allocated the parking space; regarding the latter, it should be noticed that a vehicle may send an abort message if it has already found another parking space in the meanwhile or if the driver changed his/her mind and does not want to park anymore. Regarding Fig. 2, the method *advertiseParking (Event apse)* is executed when a vehicle leaves a parking space (or when it becomes a coordinator through delegation, as explained in Section 3.2), *sort(answers)* sorts the answers received according to the allocation policy used and the information communicated by the interested vehicles, and *notification* becomes true when the winning vehicle confirms the allocation.

## 3.2. Extending the notification range

We have described so far the interactions between the coordinator and the interested vehicles to allocate an available parking space. However, we have considered that at least one of the vehicles within the

<footnote n="1">¹If the event is generated by a fixed sensor in the parking space, an initial coordinator is chosen between the vehicles receiving this event.</footnote>
declareInterest(Event apse, Coordinator c)

<figure><img src="image_2.png" /></figure>

confirmInterest(Event apse, Coordinator c)

<figure><img src="image_3.png" /><figcaption>Fig. 1. Behavior of the receiving side.</figcaption></figure>

advertiseParking(Event apse)

<figure><img src="image_4.png" /><figcaption>Fig. 2. Behavior of the coordinator in the normal process.</figcaption></figure>

communication range of the coordinator was interested in finding an available parking space. If this is not the case, the information has to be relayed farther to try to find a vehicle interested in the resource. Anyway, it is not possible anymore to interact with the same coordinator using multi-hop techniques. Indeed, due to the use of short range communication networks and the absence of any fixed support infrastructure, we have no way to ensure that the coordinator would still be reachable when using multi-hop relaying (all vehicles are highly mobile). Thus, the decision process could not be guaranteed.

Instead, we rather try to choose a new coordinator. The new coordinator has to be farther from the
<figure><img src="image_5.png" /><figcaption>Fig. 3. Behavior of the coordinator when it needs to be replaced.</figcaption></figure>

resource to increase the probability to reach new potentially interested vehicles. In the case of parking spaces, the coordinator should however not be selected too far away from the available slot. Indeed this would increase the probability that another vehicle arrives to park in that parking space in the meanwhile. Instead, we choose the new coordinator according to the demand in terms of available parking spaces in its vicinity.

Our goal is to find an interested vehicle as quickly and as close to the parking space as possible. Therefore, each vehicle periodically broadcasts to its neighbors its “state” (i.e., whether it is searching for a parking space or not). This allows each vehicle to estimate the approximate number of nearby vehicles searching for a parking space. So, when a new coordinator has to be elected, the former one broadcasts a message to its neighbors. The neighboring vehicles receiving that message (and not already coordinators for another parking space) reply to the coordinator by indicating their estimations. The coordinator then sorts the candidates in increasing number of these estimations and contacts the vehicles in that list following that order until one vehicle confirms the reception of the proposal and so becomes
the new coordinator. In case no candidate coordinator answers, the former one keeps its role and, after a while, broadcasts again the message about the available parking space. By then, new vehicles interested can now be in its neighborhood. If not, a process to switch the coordinator is initiated again. The flow chart of the algorithm executed by the coordinator when it needs to find a replacement is shown in Fig. 3; in this case, notification becomes true when a vehicle accepts to become the new coordinator. The flow chart of the corresponding algorithm for the other vehicles is trivial from the descriptions in the text.

Thus, vehicles interested in finding an available parking space can be located even if they are further from the available parking space than the communication range of the wireless network used.

### 3.3. Some remarks

In the following, we discuss some situations that may arise during the allocation protocol:

- *Several advertisements of different parking spaces.* Obviously, several available parking spaces can be communicated to the same vehicle at the same moment (e.g., two close vehicles can leave their parking space or become coordinators at the same time). Thus, a vehicle can receive different messages, issued by different coordinators, indicating an available parking space. Then, a difficulty arises for that vehicle to choose to which coordinator it should send a positive answer. This is not easy because the vehicle does not know by which coordinator it could be elected since it does not even know which other vehicles will answer. So, it is not possible for the vehicle to take an informed decision.

Consequently, we choose to let the vehicle answer to all the available coordinators. Once again, the confirmation message used in the protocol helps to avoid losing a parking space in case the same vehicle is elected twice by two different coordinators. At the coordinator side, if one vehicle does not confirm its interest in the parking space, the coordinator tries to contact the second vehicle in the list of candidates, and so on. Notice that an alternative solution could be to reply only to one coordinator (chosen randomly), but in this case the probability to receive a parking space would decrease.

- *Vehicles not compliant with the proposed protocol.* It should be noted that we do not assume that all the vehicles will have the proposed system installed. There may be other vehicles not participating in the data sharing or even vehicles that participate but whose drivers follow a behavior different from the one expected:

* *Choice of a parking space different from the one assigned.* A vehicle that has been allocated a parking space could see a different parking space available, before reaching the one assigned, and take it. In that case, it could advertise again its allocated parking space (that will remain available), acting as a coordinator for it. In this way, the information about its availability would not get lost.

* *Occupation of the parking space by other vehicles.* In the previous case, the vehicle could actually end up occupying a parking space reserved for another vehicle. Similarly, vehicles not equipped with the proposed system could find and occupy any parking space. So, even if we try to help the elected vehicle to reach the parking space while it is still available, we cannot ensure that no other driver will see and use that space before. This is obviously unavoidable. What our protocol eventually ensures is an effective dissemination of information about available parking spaces, without leading to a competition.

It is also important to emphasize that the proposed protocol relies in the concept of Encounter Probability explained in Section 2. Therefore, the information about available parking spaces is not propagated randomly, but within the areas where the information could reach interesting vehicles.
4. Reliability issues

In this section, we discuss some aspects about the reliability of the proposed protocol. In particular,
we analyze what may happen if some message gets lost or if duplicates arise during the advertisement
and allocation process, as well as potential solutions and their limitations.

In the vehicular network, a message is communicated to other nearby vehicles by broadcasting. When a vehicle tries to communicate a message to another vehicle but the message does not reach the intended destination (because the target vehicle has moved out of the communication range), we say that *the message has been lost*. We distinguish between this kind of problem and the case when the broadcast itself fails (e.g., due to interferences/collisions in the channel, fading, obstructions, reflections, or other propagation effects). Thus, in the case of *broadcasting failure* the communicating vehicle will be able to detect the problem by overhearing the communication channel; in case it detects a failure, it will retry the communication. The situation is different when a message gets lost, as the communicating vehicle may be unaware of this situation unless acknowledgement messages are included in the protocol to ensure the reception. However, it should be noticed that the acknowledgement itself may get lost. Therefore, receiving it is a guarantee that the vehicle received the message but the destination may have received the message even if no acknowledgment is received. This is consistent with what is mentioned in [11] (in relation to the WAVE protocol): “Unlike unicast traffic, broadcast frames are never acknowledged by the receivers; therefore, failed transmissions cannot be detected by the sender, and broadcast frames cannot be retransmitted.”

Now, let us analyze all the communication messages exchanged in the protocol described in Section 3:

1. *Announcement of the availability of a parking space by the coordinator.* First, the coordinator advertises the parking space in its vicinity. The advertisement is disseminated by broadcast in the area within the communication range of the coordinator. As it is not aimed at a specific vehicle, it cannot get lost. Of course, if there is no vehicle within range, then the message will not be received and the protocol to choose a new coordinator and extend the notification range will be started. This will lead to a slight increase in the delay of the allocation protocol, but it is very unlikely that the coordinator will change again without need.

2. *Communication of interest by the interested vehicles.* Each vehicle receiving the advertisement and searching for parking communicates a message indicating its interest in the parking space. If the communication of interest from a vehicle gets lost, then such a vehicle will not be among the candidates to receive the parking space. Therefore, that potential candidate will not be chosen by the coordinator and the allocation decision may be sub-optimal. In the worst case, if that was the only interested vehicle or all the messages from the interested vehicles get lost, the coordinator may end up assuming that there is no interested vehicle in the vicinity. So, a new coordinator may be chosen unnecessarily.

3. *Communication of a decision by the coordinator.* The coordinator decides to which vehicle the parking space should be allocated based on certain spatio-temporal criteria. Once it has decided, it communicates the assignment to the chosen vehicle. If the assignment message gets lost, the allocation will fail. The coordinator will not receive the confirmation from the chosen vehicle and so it will select another interested vehicle. As a consequence, the final assignment may be sub-optimal. However, selecting the second best candidate should not be a major problem.

4. *Confirmation of the parking space assignment by the chosen vehicle.* The vehicle chosen receives the information from the coordinator and sends back a confirmation to indicate that it has successfully received the information and accepts the parking space.
If the confirmation message is not received by the coordinator due to a communication problem, the coordinator will assume that the allocation was not successful. So, it will start the allocation process again to find another vehicle that may be interested in the parking space. In this way, the parking space will be allocated to another vehicle. However, the previously-chosen vehicle will be unaware of this situation and the driver will also make use of the information to try to occupy the space. As a result, some competition will be generated between the first vehicle and the second one. This is an important problem, but the situation is still better than in the case of a pure data sharing approach where the information about parking spaces is communicated to all the vehicles, which would generate a higher competition for the spots.

5. Announcement of the need of a new coordinator. When the advertisement ranges needs to be extended, the coordinator sends a message requesting a new coordinator.

The announcement is disseminated within the communication range of the coordinator, but it is not sent to any specific vehicle. Therefore, it cannot get lost. If there is no vehicle within range, the coordinator will try again by repeating the dissemination.

6. Communication of answers from the potential candidates for new coordinator. When the need of a coordinator is advertised, the vehicles receiving the message answer with their estimations about nearby vehicles searching for an available parking space.

If one of these answers gets lost, then that vehicle will not be considered as a candidate to take on the role of coordinator. This may lead to a sub-optimal election of the new coordinator, as that vehicle could have been the best choice. However, as all the vehicles are within the communication range of the coordinator, we do not expect very big differences in terms of the number of neighboring vehicle searching for a parking space; therefore, the impact of this communication failure will be small. Of course, if all the answers get lost, then the process of searching a new coordinator has to be restarted. Whereas this will lead to a slight increase in the delay of the protocol used to choose a new coordinator, it is very unlikely that the problem will happen again next time.

7. Acceptance of the coordinator's role. The process of change of coordinator concludes when the vehicle selected as a new coordinator sends a confirmation to the previous coordinator.

However, if the message indicating the acceptance gets lost, then the coordinator will try to find another target to pass on its responsibility to allocate the parking space. As a result, a second coordinator will be chosen. This will lead to the existence of several coordinators for the same parking space. Consequently, the parking space may be allocated to more than one vehicle (as each coordinator will perform one allocation of the parking space). This situation is quite similar to the one discussed in 4), but in this case from the point of view of the coordinator.

So, the two most important problems occur: 1) when the confirmation from a chosen vehicle to the coordinator gets lost in the assignment process, and 2) when the acceptance of the vehicle chosen as a new coordinator gets lost in the process of election of a new coordinator. Both cases will probably lead to a situation where the assignment of the parking space is communicated to several vehicles (even if from the point of view of a coordinator the parking space is assigned to only one vehicle), and therefore to some competition.

The possibility to lose those types of messages in unavoidable unless unicast messages and an appropriate multi-hop routing protocol (e.g., [31]) are used. However, broadcasting/geocasting is the predominant communication mode in vehicular networks [12,24,32,40] and avoids the overhead of routing messages to specific vehicles. Therefore, the only alternative that would completely avoid the possibility of some competition introduced by the data sharing system would be to remove the two types of messages mentioned. In that case, we would be implicitly assuming: for the first type of message, that
<table><caption>Table 2
Summary of potential problems due to message losses</caption><thead><tr><th>Message type</th><th>Problem if lost</th><th>Impact</th><th></th></tr></thead><tbody><tr><td>Availability of parking space</td><td>–</td><td>–</td><td rowspan="4">Process of allocation of parking spaces</td></tr><tr><td rowspan="2">Communication of interest</td><td>Pb. 1: Sub-optimal allocation</td><td>Very low</td></tr><tr><td>Pb. 2: Unnecessary election of a new coordinator (if all the communications of interest get lost) → increase of delay</td><td>Low</td></tr><tr><td>Parking assignment</td><td>Pb. 3: Sub-optimal allocation</td><td>Very low</td><td></td></tr><tr><td>Confirmation of the parking assignment</td><td>Pb. 4: Multiple assignment of the parking space</td><td>Medium</td><td></td></tr><tr><td>Request for new coordinator</td><td>–</td><td>–</td><td rowspan="4">Process of selection of a new coordinator</td></tr><tr><td rowspan="2">Answer to the request for new coordinator</td><td>Pb. 5: Sub-optimal allocation</td><td>Very low</td></tr><tr><td>Pb. 6: Restart of the process to elect a new coordinator (if all the communications of interest get lost) → increase of delay</td><td>Low</td></tr><tr><td>Acceptance of the coordinator's role</td><td>Pb. 7: Multiple coordinators → Multiple assignment of the parking space</td><td>Medium</td></tr></tbody></table>

the vehicle that is assigned the parking space will receive the message and accept it; and for the second type of message, that the chosen coordinator will receive the message and accept the role. If this is not the case, the information about the available parking space would get lost and not communicated to any vehicle. Therefore, we advocate keeping these confirmation messages to ensure that the information will be successfully delivered to some vehicle, while at the same time avoiding the competition that would arise if all the vehicles receive the information.

Table 2 shows a summary of the types of messages used in the proposed protocol, the problems that may arise if they get lost, and their impact.

## 5. Experimental evaluation

In this section, we describe our experimental evaluation. In particular, we evaluated different strategies to advertise available parking spaces in two different scenarios: parking lots and urban environments.

We have developed a prototype of VESPA for smartphones (see http://www.univ-valenciennes.fr/ROI/SID/tdelot/vespa/prototype.html), which can be used in a real scenario. However, due to obvious scalability reasons (it is difficult to perform repeatable scenarios with a high number of vehicles in a real environment), we use a simulator that we have developed to evaluate our system. Tests in a real environment are thus used mostly for verification, to calibrate our simulations, and for demonstration purposes.

We notably observed that the time elapsed since a vehicle started searching for a parking space could not be the only criterion for the allocation of parking spaces. Indeed, if a driver is close to an available parking space and sees it, he/she will park his/her vehicle if he/she is searching for such a resource (i.e., the space will be taken even if the event reporting the availability of that parking space is not communicated to that driver). Thus, it seems interesting to consider the value of the Encounter Probability of the resource for the vehicles searching; for example, we need to take into account that nearby vehicles are more likely to occupy the space.

### 5.1. Brief description of the simulator

In order to evaluate our solution with an important number of vehicles, a simulator has been designed. We needed a testing system that could simulate realistic vehicles' movements, wireless exchanges, the
generation of events, etc. Moreover, whereas the traffic naturally strongly impacts the dissemination of resources among vehicles, the information exchanged among those vehicles also influences the way the vehicles move. For example, if an interested driver receives the position of an available parking space, he/she will move in that direction. This is why we decided to develop our own simulator, since no existing one could fit our needs.

Our simulator allows simulating vehicles on real road networks stored on digital road maps and also creating artificial roads and parking lot structures by hand. In the simulated scenario, the vehicles drive from a random departure point to a destination point through roads defined according to real maps. The choice of roads used for each vehicle to reach its destination is computed using Dijkstra's shortest path algorithm. When a vehicle does not have any destination point because it is looking for a parking space but does not know any available slot, a random road is chosen (simulating a driver that is looking around for a place to park). A communication range of 200 m is considered by default.

It should be emphasized that the behavior of the vehicles during the simulations depends on both the information provided by the inter-vehicle communication system (i.e., the positions of available parking spaces communicated to the driver) and the information that the drivers observe. For example, to simulate a real environment, a driver searching for a parking space will take an available one once he/she sees it, even if a farthest one has been allocated to her/him.

## 5.2. Relevance evaluation and reservation policies

As explained in Section 3.1, different allocation policies could be considered. Moreover, the relevance of parking spaces could be evaluated using different strategies, such as the EP-based approach discussed in Section 2. In this section, we briefly mention some strategies that could be considered for relevance evaluation and parking allocation. Thus, some strategies that could be considered for relevance evaluation are:

- One with no inter-vehicle communication (i.e. drivers searching only park their car when they physically see an available space), called *View Only*.

- One for which the relevance is evaluated using our Encounter Probability, called *VESPA only* (see Section 2). We will use the geographic-based method to consider the worst-case where a road map is not available.

The penalty coefficients used to compute the Encounter Probability for parking spaces in parking lots are: $\alpha^{-1} = 50$, $\beta^{-1} = 30000$, $\gamma^{-1} = 600$ and $\zeta = 0$, in order to prefer free parking spaces located in the same row even if there are closer ones (considering the Euclidean distance) in neighboring rows. For urban environments, we use: $\alpha^{-1} = 750$, $\beta^{-1} = 900$, $\gamma^{-1} = 2700$ and $\zeta = 1/2$. It should be clarified that the values of the penalty coefficients, when considered individually, allow to set upper bounds for the different factors affecting the computation of the EP (see Section 2.2.1); for example, the value $\alpha^{-1} = 750$ along with a relevance threshold of 75% implies that a parking space located further than 250 meters when the vehicle is expected to be closest to the parking space would not be considered relevant for the driver. For more details about how to fine-tune the penalty coefficients, see [12].

- One for which the relevance is evaluated using the relevance function proposed in [49], called *Time and Distance*. Specifically, the authors use the following function to characterize the relevance of a parking space $s$:

$$F(s) = -\alpha \times t - \beta \times d \quad (\alpha, \beta \ge 0)$$
<figure><img src="image_6.png" /><figcaption>Fig. 4. Scenario for evaluation in a parking lot.</figcaption></figure>

where *t* is the age of *s*, *d* is the distance from the location of *s*, and α and β are non-negative constants that represent the relative importance of time and distance. We consider α⁻¹ = 30000 and β⁻¹ = 50 for the coefficients of the function *F*(*R*), in order to have the same relative weights than the strategy *Vespa Only*, as we will focus on highly-competitive scenarios where the distance will be the key factor to consider.

The three previous strategies, considered alone, imply that no reservation protocol is used. Besides,
different allocation strategies are considered:

- An available space is allocated by the coordinator to the vehicle with the highest EP for the consid-
ered space, called *Reservation EP*.

- The relevance function F(s), used by the *Time and Distance* strategy, is considered to allocate avail-
able spaces to vehicles, called *Reservation Time and Distance*.

In the rest of this section, we present the experimental results obtained in parking lots and urban environments.

5.3. *Experimental results in a parking lot*

In the following, we present some of the results obtained in the scenario of a parking lot. A snapshot
of the GUI of our simulator with a sample parking lot is shown in Fig. 4.

The results reported consider a parking lot with 60 parking spaces; of course, parking lots of other
sizes can be equally managed with our approach. Each vehicle entering the parking lot was considered as
searching for an available space. During our experiments, some vehicles leave their parking spaces while
others (driving at 10 kmph) are searching for an available slot. We evaluated different configurations
with more or less free parking spaces and searching vehicles. For the configurations where the number
of available parking spaces is always greater than the number of vehicles searching, the strategies using
V2V communications (i.e., all those we evaluated except *View Only*) perform better but no significant
difference between them can be observed. So, we present in the following the results for a “heavy”
parking configuration where we always consider more searching vehicles than available parking spaces.
In this “heavy” configuration, we considered a number of vehicles searching for a parking space ranging
between 1 and 10% of the total capacity of the parking facility.
<figure><img src="image_7.png" /><figcaption>Fig. 5. Experimental results in a parking lot.</figcaption></figure>

Figure 5 shows the average results obtained after 20 simulations for three evaluated criteria: the evolution of the average time needed by the vehicles to park, the standard deviation of the amount of time needed to find a parking space, and finally the percentage of useful information provided to the driver (i.e., parking spaces allocated to a driver that are really obtained by that driver).

As concerns the results of the strategies without reservation protocol, we can first observe, thanks to the average times, the interest of V2V-based solutions. Besides, the results for the *Distance and time only* approach are not very good in terms of average search time, as that relevance function was basically proposed to monitor a set of available parking spaces close to the vehicle. Compared with *VESPA only*, we can notice the importance of the vehicles’ direction to determine the best parking space to allocate, since this may avoid u-turns. Moreover, it also maximizes the probability that a vehicle arrives in a
parking space earlier than other vehicles trying to park. So, an available parking space in the same row should be preferred even if it is not the closest (i.e., one available parking space may be closer in the next row but the time to reach it will be higher).

To provide vehicles more relevant information, we introduced invalidation messages. These messages are generated by vehicles, once parked, in order to inform the other ones that the slot is not available anymore. The results for the *Time and Distance with invalidation* and *VESPA with invalidation* strategy are presented in Fig. 5. These invalidation messages really improve the result for the *Time and Distance* strategy, since they avoid wasting time to reach a no more free parking space. However, these messages also have an impact on the network load. They indeed require the generation of one additional message per parking space. Furthermore, this message has to be broadcasted using multi-hop techniques in order to (try to) reach all the vehicles previously informed of the available parking space. Even if the results obtained with invalidation messages in this scenario are good, this is also due to the fact that it is not so difficult to quickly communicate the invalidations to all the vehicles in a parking lot. However, ensuring this in a general environment would be really challenging.

Regarding the reservation protocol, the average times are rather good, compared with the other solutions, especially when the Encounter Probability is used to allocate parking spaces. Indeed, since we considered that a driver who sees a parking space will park on that space even if he/she had another parking space allocated, it is better to allocate a parking space close to the vehicle (and if possible in its driving direction). Otherwise, the probability that the parking space is going to be occupied by another driver increases. In that case, the vehicle which had the parking space allocated would have to ask for a new allocation when it receives a new event about an available parking space. This explains the average performance of the reservation protocol deployed on top of the *Time and Distance* strategy due to the “row effect”. Indeed, the target parking space is computed here with the Euclidean distance and may be located in the next row. The driver may so need more time to reach it, which increases the probability that the space is no more available when he/she arrives. This also justifies the importance of the standard deviation for this strategy. Besides, the reservation protocol allows maximizing the percentage of useful information provided (i.e., the ratio between the number of resources effectively acquired and the total number of resources communicated to the driver), whatever the allocation strategy used. This means that the reservation protocol allocates a lot of useful parking spaces (i.e., where the driver receiving the position of the available parking space can effectively park his/her vehicle) even if the misses may be very penalizing using the *Time and Distance* allocation strategy (i.e., the driver needs a lot of time to note that the parking space is no more free). Notice that this percentage of useful information is unsurprisingly bad for the strategies where no reservation protocol is used. This means that the drivers received more non-relevant information because the positions of free parking spaces are not communicated to only one driver but to several ones at the same time.

We can conclude that the *Reservation EP* strategy is the best choice with the heavy parking lot configuration. This strategy helps to reduce the average search time for a parking space, especially when the competition is high. By reducing that competition, it also improves the percentage of useful information communicated to the vehicles. Indeed, in spite of the congested situation (in terms of vehicles searching for an available parking space), about 50% of the vehicles received a correct information as opposed to the strategies without reservation protocol (about 15%). We have performed other experiments with different numbers of vehicles and parking spaces, leading to similar conclusions.

### 5.4. *Experimental results in an urban environment*

In the previous section we considered parking lots and different data sharing strategies to highlight that our reservation protocol can be used on top of systems other than VESPA. In this section, we present
<figure><img src="image_8.png" /><figcaption>Fig. 6. Scenario for evaluation in an urban environment: city of Lille in France.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 7. Experimental results in an urban environment.</figcaption></figure>

the experimental results obtained when evaluating the proposed approach in an urban environment. As in previous papers [12,16,20] we have already shown that sharing data in a vehicular ad hoc network following the VESPA approach (based on the computation of the Encounter Probability) leads to interesting benefits in both urban environments and highway scenarios, in this section we will focus on evaluating the improvement that we can obtain when we add the reservation protocol for the case of parking spaces. It should be noted that strategies such as the use of invalidation messages can be used in small scenarios such as parking lots but are not suitable in urban environments (due to the difficulty of reaching all the vehicles previously informed about the event that is invalidated); besides, the geographic-based EP could behave like the *Time and Distance* relevance function by appropriately setting the values of the penalty coefficients.

We performed several experiments using real road maps corresponding to the city of Lille in France (see Fig. 6). In these experiments, we compared a solution based on sharing data about available parking spaces using VESPA with a solution that also uses the reservation protocol proposed in this paper.
Specifically, we measured the improvement in the average search time and the maximum search time when the reservation protocol is also used. Several situations were considered by varying the amount of competition with respect to the existing number of parking spaces in a scenario (to evaluate a challenging scenario, we assumed that 75% of the vehicles in the scenario search for a parking space).

The results are shown in Fig. 7, where we vary the number of vehicles in excess of the number of parking spaces available (averages of 100 tests for each competition scenario are reported). According to these results, the reservation protocol implies an improvement in terms of the cost of drivers to find an available parking space. Intuitively, it helps to avoid some competitive situations where several vehicles try to reach the same parking space.

# 6. Related work

In this section, we present several related proposals, that illustrate the interest and originality of the work presented in this paper. First, we focus on research contributions in the academia. Then, we present some existing systems.

## 6.1. *Research on parking spaces*

In this section, we present the state of the art on sharing information about available parking spaces. The main features of the most relevant proposals considered are summarized in Fig. 8. In the figure, for each approach we provide the following information: its main *focus*, which can be parking lots or garages (*PL*), on-street parking (*SP*), and/or parking spaces controlled by parking meters (*PM*); the *interaction* mechanism used, which may be *V2V* (vehicle-to-vehicle), *V2I* (vehicle-to-infrastructure), *I2I* (infrastructure-to-infrastructure), and/or client/server (*CS*); the data dissemination *mode*, which can be *push* or *pull* [46]; the communication mechanism (*comm.*), which can assume a wide-area communication system (*WAN*) and/or be *ad hoc* (*AH*); whether it requires (*req.*) a support infrastructure (*I*) and/or monitoring sensors (*S*); whether the approach supports reserving parking spaces (*res.*); and whether it takes competition somehow into account (*comp.*). Usually the use of V2V and V2I implies ad hoc communications and the existence of a central server implies a system based on a support infrastructure; however, arguably it would also be possible to exchange information between vehicles using 3G, so we have decided to separate the criteria for the interaction and the communication features. Similarly, even if it may be unrealistic, it would be possible to communicate with a central server using multi-hop ad-hoc communications. We also consider that V2I implies communication between vehicles and the infrastructure independently of the direction of the communication (i.e., from the vehicles to the infrastructure and/or viceversa). We would also like to clarify that we are considering parking lots and other parking facilities such as garages as equivalent, as even if there may be some differences between them they are not relevant here. Finally, we understand that if a work includes a reservation process, then this is also a mechanism to decrease the competition between vehicles.

Some key aspects about the different proposals discussed in this section are collected in Fig. 9. In the following, we first present general proposals about disseminating parking information. Then, we consider proposals that acknowledge that competition problems may arise when the vehicles receive information about available parking spaces. After that, we describe proposals that focus specifically on parking lots or garages. Finally, we overview other interesting proposals that are less related to the approach in this paper.
<table><caption>Fig. 8. Main research proposals: Summary of features.</caption><thead><tr><th rowspan="2">Work</th><th colspan="3">focus</th><th colspan="3">interaction</th><th colspan="2">mode</th><th colspan="2">comm.</th><th colspan="2">req.</th><th rowspan="2">res.</th><th rowspan="2">comp.</th></tr><tr><th>PL</th><th>SP</th><th>PM</th><th>V2V</th><th>V2I</th><th>I2I</th><th>CS</th><th>push</th><th>pull</th><th>WAN</th><th>AH</th><th>I</th><th>S</th></tr></thead><tbody><tr><td>ParkNet</td><td></td><td>•</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>•</td><td>•</td><td></td><td></td></tr><tr><td>SmartPark</td><td></td><td>•</td><td></td><td></td><td>•</td><td>•</td><td></td><td></td><td>•</td><td></td><td>•</td><td>•</td><td>•</td><td></td><td></td></tr><tr><td>Agent-based</td><td></td><td>•</td><td></td><td></td><td></td><td></td><td></td><td>•</td><td></td><td></td><td></td><td>•</td><td></td><td>-</td><td></td></tr><tr><td>Time-Varying<br>TSP approach</td><td></td><td>•</td><td></td><td></td><td>•</td><td></td><td></td><td>•</td><td></td><td></td><td></td><td>•</td><td></td><td>-</td><td>•</td></tr><tr><td>GPA</td><td></td><td>•</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>•</td></tr><tr><td>PMNET</td><td></td><td></td><td>•</td><td></td><td></td><td>•</td><td>•</td><td></td><td>•</td><td></td><td>•</td><td>•</td><td>•</td><td>•</td><td>•</td></tr><tr><td>Caliskan et al.<br>(parking<br>automats)</td><td></td><td></td><td></td><td>•</td><td>•</td><td></td><td></td><td></td><td></td><td>•</td><td></td><td>•</td><td>•</td><td>•</td><td></td></tr><tr><td>SPARK</td><td>•</td><td></td><td></td><td></td><td></td><td>•</td><td>•</td><td></td><td></td><td></td><td>•</td><td>•</td><td>•</td><td></td><td></td></tr><tr><td>OAPS</td><td></td><td>•</td><td></td><td></td><td>•</td><td></td><td></td><td>•</td><td></td><td></td><td>•</td><td></td><td>•</td><td></td><td></td></tr><tr><td>CAPS</td><td></td><td>•</td><td></td><td></td><td></td><td></td><td>•</td><td></td><td>•</td><td>•</td><td></td><td>•</td><td>•</td><td>•</td><td>•</td></tr><tr><td>SmartParking</td><td>•</td><td></td><td></td><td></td><td></td><td>•</td><td>•</td><td></td><td>•</td><td></td><td>•</td><td>•</td><td>•</td><td>•</td><td>•</td></tr><tr><td>VESPA +<br>reservation</td><td>•</td><td>•</td><td>•</td><td>•</td><td></td><td></td><td></td><td>•</td><td></td><td></td><td>•</td><td></td><td></td><td>•</td><td>•</td></tr></tbody></table>

### 6.1.1. Proposals on disseminating parking information

Some proposals focus on the problem of collecting information about available parking spaces. Thus, for example, *ParkNet* [34] is a mobile sensing system for road-side parking spaces. The vehicles use ultrasonic sensors to collect information about the availability of parking spaces while driving by and they communicate these data to a central server, which aggregates them and builds a real-time map of parking space availability. Interested vehicles can then query the central server to obtain information about available parking spaces. The authors show that this monitoring approach is very effective and much cheaper and convenient than deploying fixed sensors on the parking spaces.

Another related approach is *SmartPark* [39] (see http://smartpark.epfl.ch). In this case, however, there is no centralized server and fixed sensors are used to detect if a parking space is occupied or not. A vehicle searching for parking announces its need to the nearby sensors and the request for parking is re-broadcasted periodically if needed.

A dissemination approach based on the use of fixed hotspots and opportunistic exchanges between mobile peers when they encounter each other is presented in [48]. To reduce the amount of data exchanged, a relevance function is applied, that takes into account the age of the report and the distance to the resource. However, according to [1] (a more recent contribution by some of the authors of [48]), that approach makes the assumption that a driver knows (approximatively): 1) for how long the parking space will remain available, and 2) how much time it will need to reach it.

### 6.1.2. Proposals that acknowledge the competition among vehicles

In the proposal presented in [7] (agent-based community), vehicles exchange information about both available and occupied parking spaces in cities. Based on the preferences of the driver, a decision module selects an appropriate parking space (in the experimental evaluation, parking spaces closer to the current location of the vehicle are preferred) and stops diffusing information about that available parking space in order to maximize the chance to find it free.

Another proposal to maximize the probability to find an available parking space in a city is [45], which computes a route that goes through all the parking spaces considered available. For this purpose,
<table><caption>Fig. 9. Main research proposals: Key aspects.</caption><thead><tr><td>Work</td><td>Main aspects</td></tr></thead><tbody><tr><td>ParkNet</td><td>Mobile sensing, ultrasonic rangefinders. Environmental fingerprinting. Space count, occupancy map.</td></tr><tr><td>SmartPark</td><td>Parking spot sensors. Request for parking.</td></tr><tr><td>Agent-based</td><td>Assistant agent. FS (Free Spot) list, OS (Occupied Spot) list. Communication module, Itinerary module and Decision module.</td></tr><tr><td>Time-Varying TSP approach</td><td>Time-Varying TSP. Exact approach. Clustering-based approach. Live approach.</td></tr><tr><td>GPA</td><td>Gravity-based Parking Algorithm. Parking places attract vehicles. Parking Slot Assignment Games (PSAG).</td></tr><tr><td>PMNET</td><td>Parking meters, pm-nodes. Cluster-Based status updates.</td></tr><tr><td>Caliskan et al. (parking automats)</td><td>Parking automats. Atomic information. Aggregated information. Quadtree-based aggregation.</td></tr><tr><td>SPARK</td><td>Road-Side Units (RSUs). Parking info dissemination. Parking navigation service. Anti-theft protection.</td></tr><tr><td>OAPS</td><td>Opportunistically assisted parking search. Mobile storage nodes (msnOAPS).</td></tr><tr><td>CAPS</td><td>Centrally assisted parking search. First-Come-First-Serve allocation policy.</td></tr><tr><td>SmartParking</td><td>Based on NOTICE, secure and privacy-aware. Sensor belts, parking belts. Base station, publisher station, order station.</td></tr><tr><td>VESPA + reservation</td><td>Reservation protocol. Coordinator for parking space allocation. Encounter Probability (EP). Pure ad hoc network.</td></tr></tbody></table>

the *Time-Varying TSP* (*Travelling Salesman Problem*) is considered. Several algorithms are proposed (the *exact* approach, the *clustering-based* approach, and the *live* approach), including an approach where the path is automatically readjusted when new information from neighboring vehicles is received (the *live* approach). However, according to [1] this type of solution based on the *Time-Varying TSP* is not appropriate because the availability of the parking spaces can change at any time.

In [1–3], the authors view the competition for parking spaces as an assignment game where the players are the vehicles and the parking spaces are resources with different costs associated. In this context of *Parking Slot Assignment Games (PSAG)*, they assume that the vehicles can receive information about available parking spaces (by using existing proposals) and propose algorithms for vehicles to choose the “ideal” parking space:

- First, they study a *centralized model* that optimizes the total system cost (the “social welfare”). Although an optimal solution can be found in polynomial time, the assignments obtained could imply that some drivers incur in higher costs for the benefit of others; so, they argue that this is not appropriate in distributed scenarios where the drivers make their own choices.

- Then, they study a *distributed PSAG model with complete information* and establish the relation between this parking model and the *stable marriage problem*. In this model, it is assumed that each vehicle has access to the location information of other vehicles, which arises privacy concerns and technical difficulties to perform the real-time tracking.

- Therefore, a *distributed PSAG model with incomplete information* is proposed. The problem is that solving it for an arbitrary number of parking spaces and vehicles is difficult.

- So, finally, a heuristic *gravitational model* (the *Gravity-based Parking Algorithm*, or *GPA*) is proposed. The idea is that parking spaces attract searching vehicles towards them in a way that the vehicles will move towards areas with higher density of parking spaces (even if there are closer parking spaces but with less gravitational pull).

In [2] the authors specifically focus on the GPA approach and compare it with Nash equilibrium strategies with complete information. In [3] the authors consider that vehicles are constrained to
move within road networks and propose three variants of GPA adapted to road networks: *Deterministic Angular GPA (DA-GPA)*, *Randomized Magnitude GPA (RM-GPA)*, and *Deterministic Magnitude GPA (DM-GPA)*. These variants were evaluated through simulations.

In [4,5] (*PMNET*), the authors describe a multi-hop wireless network composed of parking meters that exchange information about the availability of their parking spaces based on a hierarchical geographic clustering. The network of parking meters (*pm-nodes*) is considered a distributed database that can be queried by vehicles through a nearby (within communication range) pm-node. They also consider the use of unicast (position-based) routing for drivers to reserve a spot controlled by a certain parking meter. Finally, they consider that the competition between drivers can be managed by enhancing the information provided about available parking spaces with information about potential competitors; this extra information includes data such as the location of the competitors, which may be considered privacy-sensitive information. In this approach, a vehicle must be within range of some parking meter to receive this information. Moreover, no experimental evaluation is presented.

Parking payment terminals (*parking automats*) are also used in [10] to disseminate information about available parking spaces. Both atomic information (information about the availability of specific parking places managed by a single parking automaton) and aggregated information (summarized information about the availability in an area covered by several parking automats) are disseminated using ad hoc communications. Atomic information is disseminated in the local proximity of the available parking spaces, whereas aggregated information (which is more stable) is transmitted over wider areas to provide a higher-level perspective of parking availability to vehicles located in more distant locations. The vehicles themselves also periodically re-broadcast the information they have about available parking spaces. The information is prioritized based on the age of the resource and the distance to the resource. The authors acknowledge that several vehicles could try to get the same parking space at the same time, but leave the problem of fair resource sharing as future work.

### Considering reservation

To avoid the competition problem, some proposals explicitly consider the importance of booking a parking space for a vehicle. For example, in [22] an agent-based parking reservation facility is presented. However, it is adapted to the specific scenario of a campus and relies on the existence of a support infrastructure (composed of *InfoStations*) and a centralized computer (an *InfoStation Center*) where the information about the parking spaces is managed.

Another interesting example is *SmartParking* [50,51], which is a secure and privacy-aware architecture for the reservation of parking spaces in parking facilities. A support infrastructure based on the use of sensor belts is used to advertise information about parking spaces to nearby vehicles. This infrastructure allows the driver to choose a parking space and reserve it.

In [29,30], the authors assume that each parking space has a sensor providing information about its occupancy status, and compare (through simulations and analysis) three different approaches to discover parking spaces in a city:

- *Non-assisted parking search (NAPS)* or “blind” sequential search, where the driver tries to find a parking space near his/her destination without the help of any software system or external information.

- *Opportunistically assisted parking search (OAPS)*, where the vehicles collect information about the parking spaces that they encounter and exchange it when they meet with other vehicles, filter out this information based on time and space criteria, and then try to reach the available space that is closest to their destination.
- *Centrally assisted parking search (CAPS)*, where a central server (that has a global knowledge about the parking space availability) processes requests for parking spaces in a First-Come-First-Served (FCFS) manner and guarantees (through reservation) a parking space close to the driver's destination.

The previous approaches are compared by considering two different types of scenarios: one where the destinations of the drivers are uniformly distributed and one where the destinations are mainly focused within a certain road (hotspot). Overall, we could say that in the first scenario the opportunistic scheme performs the best and the centralized solution exhibits the worst behavior (especially for high traffic volumes), but in the second one the centralized solution outperforms the others. That study shows that opportunistically sharing information about parking spaces can indeed increase the competition among vehicles (by synchronizing the movement patterns of the vehicles), and that the cost of setting up and maintaining a centralized infrastructure does not necessarily provide the best results. So, it proves the interest of alternative approaches like the one proposed in this paper.

Summing up, approaches that support the reservation of parking spaces to deal with competition are either restricted to specific scenarios such as parking facilities (as in [22] or in [50,51]) or based on a centralized solution (as in *CAPS* [29,30]). However, up to the authors' knowledge, a general reservation-based solution to avoid the competition in vehicular ad hoc networks is a novelty in the work described in this paper.

### Considering probabilities

In the following, we describe some other proposals that take competition into account by considering the availability probabilities at the time of arrival, instead of the current status information about parking spaces. Thus, several proposals acknowledge that the probability to find an available parking space in a certain area, rather than the current occupancy status of specific parking spaces, is an interesting factor to manage. For example, in [28], parking lots (modeled by a continuous-time Markov chain) periodically disseminate in the vehicular ad hoc network some status parameters (specifically, their capacity, the number of occupied spaces, the arrival rate, and the parking rate), thus providing to the vehicles with information that they can use to estimate the probability to find there an available parking space at the time of arrival. A similar approach is described in [9]. As another related example, the availability of parking spaces is predicted in [8] within the context of a parking facility reservation system.

Whereas the previous proposals focus on estimating probabilities for parking lots, other proposals consider parking spaces in general. For example, [49] emphasizes the importance of considering aggregate information and guiding the driver towards areas where finding an available parking space is very likely (instead of guiding the user towards a specific parking space that could be taken by another vehicle in the meanwhile). Within the VESPA project, in [53] the idea is to aggregate information about available parking spaces to extract general knowledge about their overall availability in certain areas and time periods. As commented before, the use of aggregated information about parking spaces is also proposed in [10].

### 6.1.3. *Proposals focused on parking facilities*

Several proposals focus on parking lots or garages. Many existing parking management systems just keep track of the number of vehicles within a facility (using a simple barrier system to monitor/count the vehicles entering and leaving the site), whereas others monitor the individual available parking spaces. In this last case, wireless sensor networks are usually used (e.g., see [6,13,38,42,52]). A review of smart parking systems can also be found in [25].
An example is SPARK [33] (*Smart PARKing*), which proposes the use of RSUs (Road-Side Units) in parking lots to disseminate information about available parking spaces and to protect the vehicles parked there from theft.

The approach in [37] also considers parking lots and divides the geographic space in *zones* managed by different RSUs (the radius of each zone is smaller than the communication range of vehicles and RSUs). A Voronoi region is assigned to each RSU, such that each RSU keeps the occupancy state of the parking spaces in its region. The main focus of that work is on security aspects. However, no many details are provided, as it is a short paper.

### 6.1.4. Other proposals

There are other proposals that are less related to the work presented in this paper but that also concern parking spaces. So, in [14] the authors argue that not only drivers compete for parking spaces but car park operators also compete for drivers; with this motivation, and assuming that parking prices are negligible, they develop an agent-based negotiation platform. In [43], the authors focus on real-time parking reservation systems and propose a fuzzy-based model to decide whether a certain reservation request can be accepted or not (based on the current status of the system regarding space availability, cancellations, etc.) with the goal of maximizing revenues. As a third example, [15] presents an agent-based model to study the interrelation of different factors, such as the parking pricing strategies and the behavior of drivers. These proposals do not concern about communication issues (a wide-area communication infrastructure seems to be assumed).

Finally, it is interesting to mention that technologies such as inductive loops, optical sensors, ultrasonic sensors and magnetic sensors (among others) have been proposed to detect the occupancy status of a parking spot [13,47,50]. Video sensors (specifically, webcam) were also proposed in the *IrisNet* project [36], and [34] proposed the use of ultrasonic range finders along with environmental fingerprinting for mobile sensing from the vehicles. These are complementary technologies to the approach presented in this paper, as the release of a parking space could be detected and disseminated by a sensor located there or by the driver leaving the parking space.

## 6.2. Working systems and applications

In this section, we overview some existing systems. The main features of the most relevant systems considered are summarized in Fig. 10. In the figure, for each system we indicate its *name* and *URL*, its *availability* regarding the platforms where it is currently supported (as an application for iOS and/or Android devices, or Web when it has a website accessible from web browsers), whether it requires sensors to monitor the available parking spaces (*req. sensors*), whether it supports the reservation of parking spaces (*prov. reserv.*), and the main *types of parking spaces* targeted (the ones under the control of parking *meters*, parking *lots* or garages, private parking spaces *owned* by some person, and/or *public parking spaces*). It should be noted that the features considered in the comparison are different from the ones used for research prototypes (see Section 6.1), as it makes no sense to consider the same elements. Thus, for example, no existing system relies on V2V communication but on wide-range communications (e.g., 3G) and centralized servers, which is a current limitation.

In the following, we describe these systems in three categories: those that are based on the use of sensors, those that rely on the cooperation of people to input the interesting information, and other working systems less related to the work presented in this paper because they focus on very specific scenarios.
<table><caption>Fig. 10. Examples of existing systems: Summary of features.</caption><thead><tr><th rowspan="2">name</th><th rowspan="2">URL</th><th colspan="3">availability</th><th rowspan="2">req. sensors</th><th rowspan="2">prov. reserv.</th><th colspan="4">types of parking spaces</th></tr><tr><th>iOS</th><th>Android</th><th>Web</th><th>meters</th><th>lots</th><th>owned</th><th>public</th></tr></thead><tbody><tr><td>SFPark</td><td>http://sfpark.org</td><td>•</td><td>•</td><td>•</td><td>•</td><td></td><td>•</td><td>•</td><td></td><td></td></tr><tr><td>ParkingCarma</td><td>http://www.parkingcarma.com</td><td></td><td></td><td>•</td><td>•</td><td>•</td><td></td><td>•</td><td>•</td><td></td></tr><tr><td>ParkSense</td><td>http://www.smartgrains.com</td><td>•</td><td></td><td></td><td>•</td><td></td><td></td><td>•</td><td></td><td></td></tr><tr><td>Parker</td><td>http://www.streetline.com</td><td>•</td><td>•</td><td></td><td>•</td><td>•</td><td>•</td><td>•</td><td></td><td>•</td></tr><tr><td>SpotScout</td><td>http://www.spotscout.com</td><td></td><td></td><td>•</td><td></td><td>•</td><td></td><td>•</td><td>•</td><td></td></tr><tr><td>Apila</td><td>http://www.apila.fr</td><td>•</td><td></td><td></td><td></td><td>•</td><td></td><td></td><td></td><td>•</td></tr><tr><td>Placelib</td><td>http://www.placelib.com</td><td>•</td><td>•</td><td></td><td></td><td>•</td><td></td><td></td><td></td><td>•</td></tr><tr><td>ParkShark</td><td>http://www.parkshark.mobi</td><td>•</td><td></td><td></td><td></td><td>•</td><td></td><td></td><td></td><td>•</td></tr><tr><td>Roadify</td><td>http://www.roadify.com</td><td>•</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>•</td></tr></tbody></table>

### 6.2.1. Working systems based on sensors

Among the existing systems, one of the frequent examples mentioned in the literature is SFPark (http://sfpark.org), that allows checking online the availability of parking spaces in San Francisco, that are shown on a map. The information is obtained thanks to wireless parking sensors embedded in the pavement, that monitor the occupancy status of the different slots. Besides, SFPark adjusts meter and garage prices according to the existing demand, in order to optimize the parking resources. This is a very interesting system. However, according to [34], deploying the required infrastructure is quite expensive.

ParkingCarma (http://www.parkingcarma.com) allows to search and reserve a parking space in several cities in the United States through the Internet. Owners of parking lots or other parking assets can sign up with ParkingCarma and share information about the availability of their parking spaces. Then, ParkingCarma will be able to match the available parking spaces with the needs of potential customers. It can also make price adjustments in real-time.

ParkSense (http://www.smartgrains.com) provides solutions for on-street parking, public car parks, shopping centers and airports. It is interesting to mention that this system considers not only parking spaces but also charging stations for electric vehicles. Parking sensors are organized into a mesh network and communicate status information with their neighbors (by radio) until it is finally collected by a gateway node. According to the information provided in the website, several case studies have been considered for shopping centers and there is also an experience for on-street parking in Issy-les-Moulineaux (with 100 parking spots equipped).

Streetline (http://www.streetline.com) offers several products: ParkEdge (an information platform for parking providers), ParkSight (for managing parking facilities in cities), and Parker (for drivers). In the context of this paper we focused our attention on Parker, which allows drivers to find and reserve spots controlled by parking meters. A wireless sensor mesh network communicates the information about parking spaces to mirrored data sites with the help of relays located on streetlights and telephone poles.

### 6.2.2. Working systems based on information shared by people

Several systems rely on information provided by people (drivers) instead of using sensors to monitor parking spaces:

- *SpotScout* (http://www.spotscout.com) supports “SpotScouting” (searching for parking spots) and “SpotCasting” (broadcasting information about a parking spot owned so that others can find it and use it) in cities in the United States. The spots can be reserved and paid through the Internet. No sensors are used because the availability of the parking spaces is determined based on the information provided by the “SpotCasters” (who can define the periods when the space is available) and the actual reservations made. A rating system similar to the one used in eBay is used to provide information to users before the agree to trade a parking space. The system can also show information about parking spaces with an electric outlet available to charge electric vehicles (EV).
- Apila (http://www.apila.fr) relies in the cooperation among drivers to facilitate searching and finding a public parking space in France. The idea is to actually perform an exchange of the parking space. First, the vehicle that is going to release a parking space announces it. Then, if there is any vehicle interested in that parking space, it requests the spot. Finally, the vehicle releasing the parking space will wait for a while (an average of three minutes, according to the description in the website) until the other interested vehicle comes and then it will complete the transaction by liberating the space for the arriving vehicle. In the exchange of the parking space, the vehicle taking the spot pays a “ticket” to the vehicle releasing it. This is an interesting idea, but reserving a public space for a specific driver may lead to disputes and even be illegal in some cities.

- Placelib (http://www.placelib.com), formerly ShareMySpot, proposes a similar idea to Apila (also for France). A driver announces that he/she is going to release a parking space in a few minutes and the system decides which vehicle searching for a parking space is the ideal candidate for that spot. Before releasing the parking space, the driver will wait for the arrival of that vehicle. The transaction is paid with “virtual nuts”. The main difference with Apila is that the system automatically matches parking spaces and searching vehicles.

- ParkShark (http://www.parkshark.mobi) is a similar application that allows drivers to share information about the parking space that they are going to release. It uses a rating system to encourage cooperation (good “sharers” and “reservers” are expected to receive positive reviews), such that users with a high rating will more likely receive information about available parking spaces earlier than others.

- Roadify (http://www.roadify.com) also supports sharing information about available or soon-to-be-available parking spots in the United States. However, we did not find much information about it on the Web.

Finally, it is interesting to mention Waze (http://www.waze.com), that allows the exchange of information about traffic, events on the roads, and maps. However, it does not focus on parking spaces, even if parking lots can be represented on the maps.

### 6.2.3. Other working systems

In many cities, information about available parking spaces is usually posted in electronic panels located near major parking sites. Such *Parking Guidance and Information (PGI)* systems usually provide information about the location, direction and status of parking sites (mainly, regarding the availability of parking spaces within). Some systems try to provide very precise information by monitoring the individual parking spaces (e.g., *Intelligent Parking*, http://www.intelligentparking.com). There are also products focused on helping managing parking facilities, such as *myParkfolio* (http://www.parkeon.com).

A number of services are available nowadays that allow a driver to book a parking space in a certain parking facility by submitting a reservation request through the Internet [26]. One of these services is *E-Z Park* (http://www.ezparkinc.com) in the city of Philadelphia, but the examples are numerous. Some of these services focus on specific parking facilities, such as *eparking* (http://www.eparking.uk.com), about airport parkings in the United Kingdom, or *AboutAirportParking* (http://www.aboutairportparking.com), with information about many international airports. Other web sites provide information about the existence of parking spaces and their associated fees (e.g., http://www.chicagometers.com in the city of Chicago), but do not allow reservations or provide the occupancy status in real-time. It is also interesting to mention *Parkopedia* (http://en.parkopedia.com), which provides information about parking facilities in 28 countries and sometimes even supports booking; private parking spaces can be listed at http://www.parkatmyhouse.com and then be provided by Parkopedia.
Finally, a number of similar applications are available for smartphones; for example, for iOS devices we could mention *BestParking* (to find garages and compare parking rates), *EasyPark* (interface between parking operators and drivers to support parking payments), *ParkMe* (that provides parking recommendations based on their location and price), *Parking Mate* (to help keep track of timers and other aspects related to pay parking spots), *SocialParking* (that allows drivers to share information about the parking spaces that they are releasing), etc. Existing systems show the interest of applications to help with parking-related issues.

## 7. Conclusions and future work

In this paper, we have presented a solution to disseminate and allocate available parking spaces to drivers. The originality of our contribution resides in our reservation protocol, which is to the best of our knowledge the first solution to allocate parking spaces to vehicles in VANETs. We have evaluated our approach in different scenarios (including parking lots and urban environments), obtaining positive results: our system reduces both the time needed to find a parking space and the competition among the vehicles. Besides, an extensive study of related work has been performed to properly situate our approach within the state of the art and highlight its novel contributions.

We could envision an adaptation of this work to enable its use with other types of resources. For example, in hybrid networks with vehicles and mobile users we could use a similar approach to help users to find available taxi cabs. Similarly, in car sharing applications we can see a shareable car as a limited resource with some capacity and availability. Finally, charging stations for electric vehicles could become a scarce resource in the future. Each of these scenarios would probably benefit from a different resource allocation policy, but the basics of the general schema proposed in this paper could be used. Besides, it could be interesting to analyze the benefits of a pull-based query processing approach about parking spaces based on the work presented in [21].

## Acknowledgments

We thank the support of the French ANR agency in the scope of the MURPHY project and the CICYT project TIN2010-21387-C02-02. We also gladly acknowledge the funding provided by the Ministry of Education (Ministerio de Educación) in Spain through the program "Programa Nacional de Movilidad de Recursos Humanos del Plan Nacional de I-D+i 2008-2011" ("José Castillejo", ref. JC2011-0196). Finally, we thank Dorsaf Zekri for her help with some aspects related to the simulations.

## References

[1] D. Ayala, O. Wolfson, B. Xu, B. Dasgupta and J. Lin, Parking slot assignment games, in: *19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2011)*, pp. 299–308, ACM Press, 2011.

[2] D. Ayala, O. Wolfson, B. Xu, B. Dasgupta and J. Lin, Parking in competitive settings: A gravitational approach, in: *13th International Conference on Mobile Data Management (MDM 2012)*, IEEE Computer Society, 2012. To appear.

[3] D. Ayala, O. Wolfson, B. Xu, B. DasGupta and J. Lin, Stability of marriage and vehicular parking, in: *Second International Workshop on Matching Under Preferences (MATCH-UP 2012)*, 2012. To appear.

[4] P. Basu and T.D.C. Little, Networked parking spaces: Architecture and applications, in: *IEEE Vehicular Technology Conference (VTC'02)*, pp. 1153–1157. IEEE Computer Society, 2002.

[5] P. Basu and T.D.C. Little, Wireless ad hoc discovery of parking meters, in: *MobiSys Workshop on Applications of Mobile Embedded Systems (WAMES'04)*, 2004.
[6] J.P. Benson, T. O'Donovan, P. O'Sullivan, U. Roedig and C. Sreenan, Car-park management using wireless sensor networks, in: *31st IEEE Conference on Local Computer Networks (LCN'06)*, pp. 588–595. IEEE Computer Society, 2006.

[7] N. Bessghaier, M. Zargayouna and F. Balbo, An agent-based community to manage urban parking, in: *Advances on Practical Applications of Agents and Multi-Agent Systems*, volume 155 of *Advances in Intelligent and Soft Computing*, pp. 17–22. Springer, 2012.

[8] F. Caicedo, C. Blazquez and P. Miranda. Prediction of parking space availability in real time, *Expert Systems with Applications* 39(8) (2012), 7281–7290.

[9] M. Caliskan, A. Barthels, B. Scheuermann and M. Mauve. Predicting parking lot occupancy in vehicular ad hoc networks, in: *Vehicular Technology Conference (VTC'07)*, pp. 277–281. IEEE Computer Society, 2007.

[10] M. Caliskan, D. Graupner and M. Mauve, Decentralized discovery of free parking places, in: *Third ACM International Workshop on Vehicular Ad Hoc Networks (VANET'06)*, pp. 30–39. ACM Press, 2006.

[11] C. Campolo, A. Molinaro, A. Vinel and Y. Zhang, Modeling prioritized broadcasting in multichannel vehicular networks, *IEEE Transactions on Vehicular Technology* 61(2) (2012), 687–701.

[12] N. Cenerario, T. Delot and S. Ilarri, A content-based dissemination protocol for VANETs: Exploiting the encounter probability, *IEEE Transactions on Intelligent Transportation Systems* 12(3) (2011), 771–782. Special issue on exploiting wireless communication technologies in vehicular transportation networks.

[13] J. Chinrungrueng, U. Sunantachaikul and S. Triamlumlerd, Smart parking: An application of optical wireless sensor network, in: *International Symposium on Applications and the Internet Workshops (SAINTW'07)*, IEEE Computer Society, 2007.

[14] S.-Y. Chou, S.-W. Lin and C.-C. Li, Dynamic parking negotiation and guidance using an agent-based platform, *Expert Systems with Applications* 35(3) (2008), 805–817.

[15] M. Dell'Orco and D. Teodorović, *Applied Research in Uncertainty Modeling and Analysis*, volume 20, chapter "Multi agent systems approach to parking facilities management", pp. 321–339. Springer, 2005.

[16] T. Delot, N. Cenerario and S. Ilarri, Vehicular event sharing with a mobile peer-to-peer architecture, *Transportation Research Part C: Emerging Technologies* 18(4) (2010), 584–598.

[17] T. Delot, N. Cenerario, S. Ilarri and S. Lecomte, A cooperative reservation protocol for parking spaces in vehicular ad hoc networks, in: *Sixth International Conference on Mobile Technology, Applications and Systems (Mobility Conference 2009)*, pp. 1–8. ACM Press, 2009. Best paper award.

[18] T. Delot and S. Ilarri, Data gathering in vehicular networks: The VESPA experience (invited paper), in: *Fifth IEEE Workshop On User MObility and VEHicular Networks (LCN ON-MOVE 2011)*, pp. 801–808. IEEE Computer Society, 2011.

[19] T. Delot and S. Ilarri, Introduction to the special issue on data management in vehicular networks, *Transportation Research Part C: Emerging Technologies* 23 (2012), 1–2.

[20] T. Delot, S. Ilarri, N. Cenerario and T. Hien, Event sharing in vehicular networks using geographic vectors and maps, *Mobile Information Systems* 7(1) (2011), 21–44.

[21] T. Delot, N. Mitton, S. Ilarri and T. Hien, GeoVanet: A routing protocol for query processing in vehicular networks, *Mobile Information Systems* 7(4) (2011), 329–359.

[22] I. Ganchev, M. O'Droma and D. Meere, Intelligent car parking locator service, *International Journal on Information Technologies and Knowledge* 2(2) (2008), 166–173.

[23] E. Gantelet and A. Lefauconnier, The time looking for a parking space: strategies, associated nuisances and stakes of parking management in France, in: *European Transport Conference*, 2006.

[24] A.M. Hanashi, I. Awan and M. Woodward, Performance evaluation with different mobility models for dynamic probabilistic flooding in MANETs, *Mobile Information Systems* 5(1) (2009), 65–80.

[25] M. Idris, Y. Leng, E. Tamil, N. Noor and Z. Razak, Car park system: A review of smart parking system and its technology, *Information Technology Journal* 8 (2009), 101–113.

[26] K. Inaba, M. Shibui, T. Naganawa, M. Ogiwara and N. Yoshikai, Intelligent parking reservation service on the Internet, in: *2001 Symposium on Applications and the Internet – Workshops (SAINT’01 Workshops)*, pp. 159–164. IEEE Computer Society, 2001.

[27] G. Karagiannis, O. Altintas, E. Ekici, G.J. Heijenk, B. Jarupan, K. Lin and T. Weil, Vehicular networking: A survey and tutorial on requirements, architectures, challenges, standards and solutions, *IEEE Communications Surveys and Tutorials* 13(4) (2011), 584–616.

[28] A. Klappenecker, H. Lee and J.L. Welch, Finding available parking spaces made easy, *Ad Hoc Networks*, Available online: 17 March, 2012.

[29] E. Kokolaki, M. Karaliopoulos and I. Stavrakakis, Value of information exposed: wireless networking solutions to the parking search problem, in: *Eighth International Conference on Wireless On-Demand Network Systems and Services (WONS 2011)*, pp. 187–194. IEEE Computer Society, 2011.
[30] E. Kokolaki, M. Karaliopoulos and I. Stavrakakis, Opportunistically assisted parking service discovery: Now it helps, now it does not, *Pervasive and Mobile Computing* **8**(2) (2012), 210–227.

[31] E. Kulla, M. Hiyama, M. Ikeda, L. Barolli, V. Kolici and R. Miho, MANET performance for source and destination moving scenarios considering OLSR and AODV protocols, *Mobile Information Systems* **6**(4) (2010), 325–339.

[32] T.-H. Lin, H.-C. Chao and I. Woungang, An enhanced MPR-based solution for flooding of broadcast messages in OLSR wireless ad hoc networks. *Mobile Information Systems* **6**(3) (2010), 249–257.

[33] R. Lu, X. Lin, H. Zhu and X. Shen, SPARK: A new VANET-based smart parking scheme for large parking lots, in: *28th IEEE International Conference on Computer Communications (INFOCOM'09)*, pp. 1413–1421. IEEE Computer Society, 2009.

[34] S. Mathur, T. Jin, N. Kasturirangan, J. Chandrashekharan, W. Xue, M. Gruteser and W. Trappe, ParkNet: Drive-by sensing of road-side parking statistics, in: *Eighth International Conference on Mobile Systems, Applications, and Services (MobiSys 2010)*, pp. 123–136. ACM Press, 2010.

[35] H. Mousannif, I. Khalil and S. Olariu, Cooperation as a service in VANET: Implementation and simulation results, *Mobile Information Systems* **8**(2) (2012), 153–172.

[36] S. Nath, A. Deshpande, Y. Ke, P. B. Gibbons, B. Karp and S. Seshan, IrisNet: An architecture for internet-scale sensing services, in: *29th International Conference on Very Large Data Bases (VLDB'03)*, **29**, pp. 1137–1140. VLDB Endowment, 2003.

[37] R. Panayappan, J. M. Trivedi, A. Studer and A. Perrig, VANET-based approach for parking space availability, in: *Fourth ACM International Workshop on Vehicular Ad Hoc Networks (VANET'07)*, pp. 75–76. ACM Press, 2007.

[38] B. Panja, B. Schneider and P. Meharia, Wirelessly sensing open parking spaces: Accounting and management of parking facility, in: *Americas Conference on Information Systems (AMCIS 2011) – All Submissions*, 2011. Paper 270.

[39] M. Piórkowski, Collaborative transportation systems, in: *Wireless Communications and Networking Conference (WCNC 2010)*, IEEE Computer Society, 2010.

[40] R. Saqour, M. Shanuldin and M. Ismail, Prediction schemes to enhance the routing process in geographical GPSR ad hoc protocol, *Mobile Information Systems* **3**(3–4) (2007), 203–220.

[41] D. Shoup, Cruising for parking, *Access* (30) (2007), 16–22.

[42] V.W. Tang, Y. Zheng and J. Cao, An intelligent car park management system based on wireless sensor networks, in: *First International Symposium on Pervasive Computing and Applications*, pp. 65–70. IEEE Computer Society, 2006.

[43] D. Teodorović and P. Lučić, Intelligent parking systems, *European Journal of Operational Research* **175**(3) (2006), 1666–1681.

[44] S. Ukkusuri, Y. Wang and T. Chigan, Introduction to the special issue on exploiting wireless communication technologies in vehicular transportation networks, *IEEE Transactions on Intelligent Transportation Systems*, **12**(3) (2011), 633–634.

[45] V. Verroios, V. Efstathiou and A. Delis, Reaching available public parking spaces in urban environments using ad-hoc networking, in: *12th International Conference on Mobile Data Management (MDM 2011)*, pp. 141–151. IEEE Computer Society, 2011.

[46] A.B. Waluyo, B. Srinivasan and D. Taniar, Research in mobile database query optimization and processing, *Mobile Information Systems* **1**(4) (2005), 225–252.

[47] J. Wolff, T. Heuer, H. Gao, M. Weinmann, S. Voit and U. Hartmann, Parking monitor system based on magnetic field sensors, in: *2006 IEEE Intelligent Transportation Systems Conference (ITSC'06)*, pp. 1275–1279. IEEE Computer Society, 2006.

[48] O. Wolfson, B. Xu and H. Yin, Dissemination of spatio-temporal information in mobile networks with hotspots, in: *Second International Workshop on Databases, Information Systems, and Peer-to-Peer Computing (DBISP2P'04)*, volume 3367 of *Lecture Notes in Computer Science*, pp. 185–199. Springer, 2004.

[49] B. Xu, A. M. Ouksel and O. Wolfson, Opportunistic resource exchange in inter-vehicle ad-hoc networks, in: *Fifth International Conference on Mobile Data Management (MDM'04)*, pp. 4–12. IEEE Computer Society, 2004.

[50] G. Yan, S. Olariu, M.C. Weigle and M. Abuelela, SmartParking: A secure and intelligent parking system using NOTICE, in: *11th International Conference on Intelligent Transportation Systems*, pp. 569–574. IEEE Computer Society, 2008.

[51] G. Yan, W. Yang, D.B. Rawat and S. Olariu, SmartParking: A secure and intelligent parking system, *IEEE Intelligent Transportation Systems Magazine* **3**(1) (2011), 18–30.

[52] Y.-Z. Bi, L.-M. Sun, H.-S. Zhu, T.-X. Yan and Z.-J. Luo, A parking management system based on wireless sensor network, *ACTA AUTOMATICA SINICA*, **32**(6) (2006), 968–977.

[53] D. Zekri, B. Defude and T. Delot, Summarizing sensors data in vehicular ad hoc networks, *RAIRO – Operations Research 44*(4) (2010), 345–364.

**Thierry Delot** is an Associate Professor at the University of Valenciennes since 2002. He is a member of the LAMIH research centre (UMR CNRS/UVHC 8201) and an associate researcher at INRIA Lille Nord Europe in the FUN research group. Thierry received the MSc and the PhD in Computer Science at the University of Versailles in 1998 and 2001, respectively. At that time,
he was working in the database group leaded by Pr. G. Gardarin. Then, he moved to the University of Valenciennes where he got the accreditation to supervise research in 2009. Thierry's research interests mainly concern mobile data management and query processing techniques. He is or has been involved in several projects related to data management in vehicular networks. He authored over 70 publications and was guest editor of special issues published in Transportation Research Part-C, Pervasive and Mobile Computing or the Journal of Systems and Software. Thierry has also been the (co-)organizer of several events of the database community such as the CNRS Summer School on Ambient Intelligence in 2009 and 2011, the EDBT Summer School in 2009, the DS2ME@ICDE workshop in 2008 or the IMMoA@VLDB workshop in 2012.

**Sergio Ilarri** is an Associate Professor in the Department of Computer Science and Systems Engineering at the University of Zaragoza. He received his B.S. and his PhD in Computer Science from the University of Zaragoza in 2001 and 2006, respectively. For a year, he was a visiting researcher in the Mobile Computing Laboratory at the Department of Computer Science at the University of Illinois in Chicago, and he has also cooperated (through several research stays) with the University of Valenciennes and with IRIT in Toulouse. His research interests include data management issues for mobile computing, vehicular networks, mobile agents, and the Semantic Web. He authored a number of publications in relevant journals and conferences and participated (or participates) as guest editor of special issues published in Transportation Research Part-C, IEEE Internet Computing, IEEE Multimedia, or the Journal of Systems and Software.

**Sylvain Lecomte** is Full Professor at LAMIH-University of Valenciennes. He obtained the HDR in Computer Science at the University of Valenciennes (Title: Conception and adaptation of technical services dedicated to ambient computing, 2005) and a PhD in Computer Science at the University of Lille 1 (Title: COST-STIC: Smart Card embedded into transactional services and transactional services embedded into smart Card, 1998). His research interests include context-aware computing, deployment of mobile services and vehicular networks.

**Nicolas Cenerario** earned his Research Master and Ph.D. degrees in Computer Science at the University of Valenciennes, France, in 2006 and 2010, respectively. His research interests concern information sharing in intervehicular communication networks. In this context, he is particularly interested in information dissemination, continuous query processing and resource allocation.
<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

Hindawi

Submit your manuscripts at
http://www.hindawi.com

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>