Member, IEEE Abdelwahab Boualouache

Member, IEEE Sidi-Mohammed Senouci

Samira Moussaoui

S.-M Senouci

PRIVANET: An Efficient Pseudonym Changing and Management Framework for Vehicular Ad-Hoc Networks

Keywords: Vehicular ad-hoc networks (VANETs), security, location privacy, pseudonym changing. I

Protecting the location privacy is one of the main challenges in vehicular ad-hoc networks (VANETs). Although, standardization bodies, such as IEEE and ETSI, have adopted a pseudonym-based scheme as a solution for this problem, an efficient pseudonym changing and management is still an open issue. In this paper, we propose PRIVANET, a complete and efficient pseudonym changing and management framework. The PRIVANET has a hierarchical structure and considers the vehicular geographic area as a grid. Each cell of this grid contains one or many logical zones, called vehicular location privacy zones (VLPZs). These zones can easily be deployed over the widespread roadside infrastructures (RIs), such as gas stations, to provide a secure changing and management of pseudonyms. The proposed framework consists of different building blocks: 1) an effective VLPZ-based pseudonym changing strategy; 2) a reputation-based mechanism to motivate selfish vehicles to enter VLPZs; 3) an adapted user-centric privacy model; 4) a secure hybrid mechanism for the distribution of pseudonyms sets and CRLs; 5) a method to generate the IP and MAC addresses from the pseudonym; 6) a stochastic model to estimate the number of VLPZs required at a given cell; and 7) a mathematical model for an optimal placement of the VLPZs over RIs to reduce the transportation cost of vehicles in terms of time. An extensive simulation study using a realistic map and with real traffic mobility measurements is carried out to evaluate and validate the performance of the PRIVANET. The simulation results demonstrate the effectiveness of the proposed framework.

A beaconing service is often required by safety-related applications. Every vehicle regularly broadcasts a safety message, which includes its status information such as time, position, and speed [START_REF] Doukha | An SDMA-based mechanism for accurate and efficient neighborhood-discovery link-layer service[END_REF]. Safety messages are authenticated and sent with a high frequency in clear text. They significantly help in road safety by providing a vicinity view to vehicles. However, these messages can also be exploited by passive adversaries to perform location tracking attack. Indeed, the broadcast messages can easily be collected by eavesdropping wireless communications and linked after that according to vehicles' identifiers. Thereby, all locations visited by vehicles can be known by adversaries, which threatens the location privacy of VANETs' users since there is usually a strong relationship between users and their vehicles [START_REF] Eckhoff | SlotSwap: Strong and affordable location privacy in intelligent transportation systems[END_REF].

Pseudonym changing is a common approach to overcome this problem [START_REF] Dressler | Research challenges in intervehicular communication: Lessons of the 2010 Dagstuhl seminar[END_REF]. Instead of using one static identifier, each vehicle is equipped with a set of fictive identifiers, called pseudonyms. Current security standards such as IEEE 1609.2 [START_REF]IEEE Standard for Wireless Access in Vehicular Environments-Security Services for Applications and Management Messages[END_REF] and ETSI 102941-v1.1.1 [START_REF]Intelligent Transport Systems (ITS); Security; Trust and Privacy Management[END_REF], consider pseudonyms as public keys certified by a Certificate Authority (CA) and stored in vehicles' On-Board Units (OBUs). In order to alleviate the tracking of their positions, vehicles should frequently change their pseudonyms. Indeed, a higher frequency of pseudonym changing is an important parameter to provide a good degree of privacy protection. However, the frequency value should be reasonable to avoid the impact communication performances [START_REF] Schoch | Impact of pseudonym changes on geographic routing in VANETs[END_REF]. In addition, to avoid ease linkability of pseudonyms, all the communication identifiers such as the MAC and IP addresses should be changed with the pseudonym at the same time [START_REF] Papadimitratos | Architecture for secure and private vehicular communications[END_REF].

Although both of academia and industry have agreed to apply a pseudonym changing approach in the future deployment of VANETs, different challenges are still to be addressed [START_REF] Petit | Pseudonym schemes in vehicular networks: A survey[END_REF]. For example (i) many works have demonstrated that vehicle's pseudonyms can easily be linked without using a pseudonym changing strategy [START_REF] Wiedersheim | Privacy in inter-vehicular networks: Why simple pseudonym change is not enough[END_REF]. Although, different pseudonym changing strategies have been proposed (e.g. [START_REF] Lu | Pseudonym changing at social spots: An effective strategy for location privacy in VANETs[END_REF]- [START_REF] Boualouache | S2SI: A practical pseudonym changing strategy for location privacy in VANETs[END_REF]), an effective pseudonym changing strategy is not achieved yet [START_REF] Eckhoff | Driving for big data? privacy concerns in vehicular networking[END_REF], (ii) the level of location privacy could significantly be affected if rational vehicles refuse to change their pseudonyms with other vehicles [START_REF] Freudiger | Noncooperative location privacy[END_REF], and last but not least, (iii) high deployment costs are generated if existing solutions to distribute certificates (pseudonyms) revocation lists (CRLs) and pseudonyms sets are applied. Indeed, these solutions require a total coverage by Roadside Units (RSUs), which cannot always be achieved [START_REF] Ma | Pseudonym-on-demand: A new pseudonym refill strategy for vehicular communications[END_REF].

In this paper, we extend our work published in [START_REF] Boualouache | Towards an efficient pseudonym management and changing scheme for vehicular adhoc networks[END_REF] to propose PRIVANET, a complete and efficient pseudonym changing and management framework. This framework has a hierarchical structure and mainly based on logical zones, called Vehicular Location Privacy Zones (VLPZs). These zones aim at managing and changing pseudonyms and can easily be deployed over the widespread Roadside Infrastructures (RIs) such as gas stations, electric vehicles charging stations, and toll booths or created as new roadside infrastructures for the future deployment VANETs. VLPZs are equipped with a reputationbased mechanism for motivating vehicles to enter to them. Different building blocks are proposed by PRIVANET that address each issue of the pseudonym changing approach. For example, the framework includes building blocks for an efficient changing of pseudonyms, an optimal distribution of pseudonyms sets, and a synchronized changing of all identifiers of the communication stack layer. In the other hand, a stochastic model to estimate the number of VLPZs required at a given cell as a function of traffic density and the demand for vehicles to enter VLPZs is proposed. In addition, the problem of the optimal placement of VLPZs over RIs is mathematically modeled. The modularity, the extensibility, the flexibility and the ease of deployment are the main features of this framework, which makes it well adapted for the future deployment of VANETs.

The main contributions of this paper can then be summarized as follows:

• We propose a complete and efficient pseudonym changing and management framework for VANETs. It has a hierarchical structure to facilitate the control and management of the system. The building blocks of our framework address the key issues of the pseudonym changing approach.

• We propose a stochastic model to estimate the number of VLPZs required at a given cell as a function of time. This model is mainly based on traffic density and the demand for vehicles to enter the VLPZs. • We mathematically model the problem of the optimal placement of VLPZs over widespread RIs to reduce the transportation cost of vehicles in terms of time. We then define an objective function to select the best RIs to host VLPZs and propose a simple solution to solve this problem.

• We evaluate and validate the proposed framework through an extensive simulation study using a realistic map and with real traffic mobility measurements. The simulations are performed based on a reliable vehicular network simulation framework composed of Veins [START_REF] Sommer | Bidirectionally coupled network and road traffic simulation for improved IVC analysis[END_REF], OMNet++ and SUMO [START_REF] Krajzewicz | Recent development and applications of SUMO-Simulation of Urban MObility[END_REF]. The remainder of this paper is organized as follows. Some related work is described in Section II. The proposed pseudonym changing and managing framework is presented in Section III. Section IV describes the reputation-based mechanism that is used to motivate vehicles to enter VLPZs. An optimal deployment of VLPZs is described in Section V. The results of the performance evaluation are presented in Section VI. Finally, the conclusion is given in Section VIII.

II. RELATED WORK

In this section, we present an overview of recent stateof-art solutions for pseudonym changing and management in VANETs. At the end of this section, a comparison is made to highlight the features of our proposed framework comparing to relevant presented solutions.

Pseudonym linking attack makes a simple changing of pseudonym ineffective to protect the location privacy of VANETs' users [START_REF] Wiedersheim | Privacy in inter-vehicular networks: Why simple pseudonym change is not enough[END_REF]. Two kinds of this attack are considered [START_REF] Boualouache | A survey on pseudonym changing strategies for vehicular ad-hoc networks[END_REF]: (i) syntactic linking that can be performed if only one vehicle changes its pseudonym among the group of vehicles running on the road, and (ii) semantic linking that can be performed despite all vehicles change their pseudonym simultaneously, where adversaries use advanced tracking algorithms to predict the future positions of vehicles based on their current positions, and thereby link their pseudonyms. Different pseudonym changing strategies have been proposed to overcome this attack. These strategies were classified according to the used protection mechanism into three categories: (i) a synchronizing mechanism-based strategies (e.g. [START_REF] Lu | Pseudonym changing at social spots: An effective strategy for location privacy in VANETs[END_REF], [START_REF] Ying | Pseudonym changes scheme based on candidate-location-list in vehicular networks[END_REF]), (ii) encryption-based strategies (e.g. [START_REF] Ying | Motivation for protecting selfish vehicles' location privacy in vehicular networks[END_REF]), and (iii) radio silence based strategies (e.g. [START_REF] Boualouache | S2SI: A practical pseudonym changing strategy for location privacy in VANETs[END_REF]). The strategies of the last category are the most effective as they allow protection again the two kinds of pseudonym linking attack. However, radio silence may have negative impacts on road safety [START_REF] Lefèvre | Impact of v2x privacy strategies on intersection collision avoidance systems[END_REF]. To address this last issue, we proposed in [START_REF] Boualouache | VLPZ: The vehicular location privacy zone[END_REF], the VLPZ model and the VLPZ-based pseudonym changing strategy. This strategy provides protection against pseudonym linking attack while preserving road safety. Recently in [START_REF] Boualouache | A survey on pseudonym changing strategies for vehicular ad-hoc networks[END_REF], we proposed a comprehensive survey and classification of pseudonym changing strategies. We also compare and discuss them according to important parameters.

Furthermore, the cooperation between vehicles is important to ensure a successful pseudonym changing. Indeed, rational vehicles may decide to do not change their pseudonyms when they asked for it. This is due to the costs that could be generated from pseudonym changing [START_REF] Schoch | Impact of pseudonym changes on geographic routing in VANETs[END_REF]. To address this issue, a game theoretic based approach is first proposed in [START_REF] Freudiger | Noncooperative location privacy[END_REF]. The authors suggested a user-centric privacy model, where vehicles take maximizing their payoffs as a decisive parameter to change their pseudonyms. However, vehicles, in this solution, only cooperate when their location privacy protection level is below the required level, otherwise they will not. Recently, in [START_REF] Ying | Motivation for protecting selfish vehicles' location privacy in vehicular networks[END_REF] a novel solution called MPSVLP is proposed. This solution consists of a strategy of pseudonym changing and a mechanism to motivate vehicles to cooperate in this strategy. The strategy consists in creating dynamic mixed zones called, DMPLs. A request is sent to a strategy controller server (CS) each time a vehicle wants to create its own DMPL. The length of vehicle's DMPL area is calculated by CS, which after that sends a command to all vehicles found this area requesting them to cooperate in creating this DMPL. Relying on a encryption-based strategy is, however, a major drawback of this solution as it does not provide any protection again the semantic linking of pseudonyms [START_REF] Boualouache | A survey on pseudonym changing strategies for vehicular ad-hoc networks[END_REF]. Pseudonym management is another important issue in the pseudonym changing approach. Indeed, the authors in PMS [START_REF] Artail | A pseudonym management system to achieve anonymity in vehicular ad hoc networks[END_REF] highlighted the fact that more focus is placed in the literature on pseudonym changing strategy than pseudonym management and implementation issues. For this reason, they proposed a solution that completely relies on RSUs to distribute pseudonym sets and exchanging them to increase the anonymity. This solution could however generates high deployments costs as it is totally based on road infrastructures. In addition, as no strategy proposed is clearly proposed, pseudonyms linking could easily be performed. In [START_REF] Boualouache | HPDM: A hybrid pseudonym distribution method for vehicular ad-hoc networks[END_REF], we proposed HPDM a hybrid method for the distribution of the pseudonyms sets. This method uses both RSUs and vehicles to distribute pseudonyms sets. The aim is to reduce the deployment costs generated to perform this operation.

The authors in TPSRP [START_REF] Yan | Towards providing scalable and robust privacy in vehicular networks[END_REF] viewed pseudonyms as costly resources that need to be considered as services. Therefore, instead of pro-actively issuing pseudonyms, they proposed to provide pseudonyms only to vehicles requesting them. This solution seems interesting as it significantly helps to reduce the number of needed pseudonyms. However, this solution is not aligned with requirements of VANETs as location privacy protection is required and protection mechanisms are basically based on the cooperation of a large number of vehicles [START_REF] Lu | A lightweight conditional privacypreservation protocol for vehicular traffic-monitoring systems[END_REF].

Our main goal in this paper is thus to propose a complete framework that efficiently considers the key issues of the pseudonym changing approach (PCA). Indeed, to the best of our knowledge, there is no solution considers all these issues together in the literature. In Table I, we compare between state-of-art solutions for pseudonym-based system in VANETs. This comparison highlights which of the key issues of PCA are addressed by each solution such as the pseudonym changing strategy (PC Strategy) and the noncooperative behavior (Selfishness). We can see that, in contrast to state-of-art solutions, all the key issues are addressed by PRIVANET.

III. AN EFFICIENT PSEUDONYM CHANGING AND MANAGEMENT FRAMEWORK FOR VEHICULAR AD-HOC NETWORKS

In this section, we present the design of the proposed framework. Figure 1 illustrates a global view of this framework. It has a hierarchical structure and mainly based on logical zones, called Vehicular Location Privacy Zones (VLPZs) deployed over grid cells of the vehicular geographic area. This framework consists of different building blocks: (i) a VLPZ-based pseudonym changing strategy for an effective changing of a pseudonym, (ii) a secure hybrid mechanism for the distribution of pseudonyms sets and CRLs, (iii) a method to generate the IP and the MAC addresses from the pseudonym, (iv) an adapted user-centric privacy model, (v) a reputationbased mechanism to motivate selfish vehicles to enter VLPZs, and finally (vi) an optimal deployment of VLPZs over RIs of a given cell as a function of time. The first four building blocks [START_REF] Boualouache | Towards an efficient pseudonym management and changing scheme for vehicular adhoc networks[END_REF] are described in this section, while the fifth and sixth ones are presented in sections IV and V respectively.

This section is thus structured as follows. We first describe the considered system and adversary models. We then present the model VLPZ, and the VLPZ-based pseudonym changing strategy. After that, we present the VLPZ-based pseudonyms sets and revocation lists distribution. Finally, we describe the used privacy evolution model and the mechanism of generating the communication layers identifiers from the pseudonym.

A. System and Adversary Models

To facilitate the management of pseudonyms and CRLs, we consider that the vehicular geographic area is partitioned as a grid [START_REF] Boualouache | Towards an efficient pseudonym management and changing scheme for vehicular adhoc networks[END_REF]. The cells of the grid have a same predefined size. Each cell may comprise the entire downtown area of a small town or few city blocks. The VANET system is composed of vehicles and RSUs. Each vehicle has an OBU device that is equipped with a wireless technology based on the IEEE 802.11p/WAVE standard. The OBU allows the vehicle not only to communicate with other vehicles but also with RSUs. Each vehicle is also equipped with a map and a GPS receiver that allows obtaining the position and the current time. Each vehicle periodically broadcasts a safety message every t milliseconds, where each message includes information about the vehicle such as its position and its speed. We also assume the existence of a central trusted authority (TA) that provides public and private keys to vehicles and RSUs. Before joining the VANET, each vehicle registers with the TA with its vehicle identifier, denoted by ID v . During the registration, each vehicle V i is equipped with a public and a private keys and sets of pseudonyms. Each set contains n pseudonyms K i, j , where j ∈ 1,...,n. For each pseudonym K i, j of vehicle V i , the TA provides a certificate Cert i, j (K i, j ). The private key K -1 i, j corresponding to the pseudonym K i, j is used by the vehicle V i to digitally sign messages. The pseudonym is attached to each message to enable other vehicles and RSUs to verify the sender's authenticity. Each vehicle changes its pseudonym each δ minutes. Each cell contains one regional trusted authority (TA R ), and one or more Vehicular Privacy Zones (VLPZs). TA R s act as intermediates between the TA and the VLPZs. They aim at managing the pseudonyms sets and the CRLs distribution and control the location privacy protection level provided the VLPZs within the cells. Indeed, all the TA R sa r e connected to the TA, and each TA R is contacted to the VLPZs within its cell via secure communication links.

Furthermore, we are interested to study the location privacy protection against a strong passive adversary model. This adversary is passive ie. it can only eavesdrop communications and composed of an external global adversary and few internal local attackers. The global one has a complete coverage on the system but it is not an authenticated member (external). However, the local attackers are internal i.e. authenticated members but with a limited coverage on the system (local).

This adversary model aims to track the target vehicle by eavesdropping all communications of any vehicle within a region of interest. The adversary model is well aware of the system model and the proposed framework design. However, it has no control over VLPZs. In addition, this adversary is not able to perform tracking using cameras, because the cost of the global eavesdropping with cameras is much higher than the radio-based eavesdropping. Therefore, camera-based global eavesdropping is beyond the scope of this paper.

B. VLPZ Model

We define the Vehicular Location Privacy Zone (VLPZ) as a logical zone managed by trusted regional authorities like municipalities or directly by the country transportation department. Each cell of the grid can contain one or more VLPZs. The VLPZ aims not only to increase the location privacy protection level of vehicles within the cell by providing an effective pseudonym changing [START_REF] Boualouache | VLPZ: The vehicular location privacy zone[END_REF], but also to distribute pseudonyms sets and CRLs to them. The design of VLPZ is seemingly similar to widespread Roadside Infrastructures (RIs) like gas stations. As illustrated in Figure 2, a basic VLPZ consists of one entry point called the router, one exit point called the aggregator and a limited number of lanes l where l > 1. Each VLPZ is equipped with an RSU denoted by RSU v z and used to: (i) periodically announce the existence of a VLPZ, (ii) stimulate vehicles passing through the VLPZ to enter, (iii) request pseudonyms sets from the TA R and distribute them to the vehicles inside the VLPZ according to their requests, (iv) request the CRLs from the TA R and distribute them to the vehicles inside the VPLZ, and finally (v) get information from vehicles, which helps the VLPZ to take certain decisions. The VLPZ can easily be deployed over RIs such as gas stations and toll booths. However, due to the increasing interest of users to protect their location privacy, we do not rule out that the VLPZ can be created as an independent roadside infrastructure in the future VANETs deployment. Ideally, VLPZs are installed in the two directions of two-way streets and their emplacements of are shown on the map.

C. VLPZ-Based Pseudonym Changing Strategy

The strategy of pseudonym changing is executed as follows [START_REF] Boualouache | VLPZ: The vehicular location privacy zone[END_REF]. The RSU v z periodically broadcasts notifications for informing the vehicles about the existence of a VLPZ. If a vehicle wants to access to the VLPZ, it sends a request to the RSU v z . As Figure 2 shows vehicles arrive at a VLPZ, one after another, on one-lane. They keep broadcasting safety messages until they enter the VLPZ. When a vehicle reaches the router, it stops broadcasting safety messages and heads for an assigned VLPZ's lane. The assigned lane is randomly and privately selected by the router. The vehicle can then reside inside a VLPZ for a random period of time. This period mainly depends on the service time. For example, if we assume that a VLPZ is deployed in a gas station, the service time is the time taken by the driver to fill the fuel tank of its vehicle. A vehicle must change its pseudonym before it exits the VLPZ and all vehicles exit a VLPZ through the the aggregator.H o w e v e r , the exit order is different from the entering order since the residency periods of vehicles are random. We also assume that the aggregator can select a certain order in random and private way. As discussed in [START_REF] Boualouache | VLPZ: The vehicular location privacy zone[END_REF], this strategy provides protection not only against both of the syntactic and the semantic linking of pseudonyms, but also against the FIFO attacks. In addition, differently from the strategies that rely on the radio silence technique, road safety is preserved in this strategy.

D. Pseudonyms Sets and Revocation Lists Distribution

As we already highlighted in the related work section, existing state-of-art solutions totally rely on available RSUs to distribute pseudonyms sets and pseudonyms revocation lists (CRLs) [START_REF] Artail | A pseudonym management system to achieve anonymity in vehicular ad hoc networks[END_REF], which may generate high deployment costs. For this reason, in our framework, we propose that these operations are performed both inside VLPZs using RSU v z sand by vehicles through V2V communications. Our solution allows a quick and wide distribution of pseudonyms sets and CRLs, while keeping low deployment costs. Indeed, vehicles can exchange small CRLs updates as described in [START_REF] Papadimitratos | Certificate revocation list distribution in vehicular communication systems[END_REF] and involve to distribute pseudonyms sets using the method proposed in [START_REF] Boualouache | HPDM: A hybrid pseudonym distribution method for vehicular ad-hoc networks[END_REF] for example.

E. Privacy Level Evolution

The location privacy level of a vehicle changes over the time. It can be decreased due to the pseudonyms linking attack and increased each time that a vehicle accesses to a VLPZ. To capture the evolution that occurs to the location privacy level of a vehicle over time, we use the user-centric location privacy model introduced by [START_REF] Freudiger | Noncooperative location privacy[END_REF]. The location privacy level of a vehicle i is modeled using a location privacy loss function

β i (t, T v z i ) : (R + , R + ) → R +
where t is the current time and T v z i ≤ t is the time of the last pseudonym change of vehicle i inside a VLPZ. The privacy loss is set to 0, each time that i changes its pseudonym inside a VLPZ and increases with time according to a sensitivity parameter, 0 <λ i < 1 until it reaches a maximum value A i (T v z i ), which is the location privacy protection level achieved at the last pseudonym change of vehicle i inside a VLPZ. The privacy loss function is defined as follows:

β i (t, T v z i ) = ⎧ ⎪ ⎨ ⎪ ⎩ λ i (t -T v z i ) for T v z i ≤ t < T max i A i (T v z i ) for t ≥ T max i
where

T max i = A i (T vz i ) λ i + T v z i
is the time when the function reaches the maximal privacy loss. The location privacy level of vehicle i at time t is:

A i (t) = A i (T v z ) -β(t, T v z ), t ≥ T v z

F. Generating the Communication Layers Identifiers

Changing all communication identifiers with the pseudonym is required to avoid the ease linking of pseudonyms [START_REF] Papadimitratos | Architecture for secure and private vehicular communications[END_REF]. In our framework, the Cryptographically Generated Address (CGA) protocol [START_REF] Aura | Cryptographically Generated Addresses (CGA), Internet Requests for Comments[END_REF] is used to build IP addresses from pseudonyms. Indeed, as described in [START_REF] Qadir | Cryptographically generated addresses (CGAs): A survey and an analysis of performance for use in mobile environment[END_REF], CGA uses a random 128-bit number and pseudonym (public key) to create the interface identifier, which is concatenated after that with a subnet prefix to build an IPv6 address. The concept of CGA can also be used to build a MAC address [START_REF] Artail | A pseudonym management system to achieve anonymity in vehicular ad hoc networks[END_REF]. Indeed, the MAC can be generated by calculating a hash value of a set of concatenated values. The values that we propose in our framework are: a random 128-bit number, an interface identifier, collision count, a pseudonym, and extension fields. The collision count and the extension fields are described in [START_REF] Qadir | Cryptographically generated addresses (CGAs): A survey and an analysis of performance for use in mobile environment[END_REF].

IV. MOTIVATING VEHICLES TO ENTER TO VLPZS

Two important parameters impact the level of location privacy provided a VLPZ: (i) Its capacity (K): that is the maximum number of vehicles that the VLPZ can contain. This parameter is static and can be set by the system designer, and (ii) Its occupancy (|AS| t ), which represents the number of vehicles that have accessed the VLPZ at the same time i.e. the number of vehicles inside a VLPZ at a given time. In contrast to the capacity, the occupancy is a dynamic parameter that mainly depends on road traffic density and the number of vehicles requesting access to the VLPZ. Thus, the occupancy could dramatically be decreased if vehicles are rational. Indeed, these vehicles always tend to protect their location privacy with minimum possible cost. In our framework, the cost is expressed as the time that a vehicle took to move to a VLPZ and quantified by the lost of pseudonyms along this time. To this end, a non-cooperation from these vehicles is expected if they reached their required privacy level (A d ). In other words, they request to access a VLPZ only if their location privacy level goes under A d .

To overcome this problem, we propose a reputation-based mechanism for VLPZs to increase their occupancy. This mechanism consists in broadcasting invitations of access to vehicles through RSU v z s. The reputation value of each vehicle is calculated according to its response to the received invitation. Indeed, the reputation value of a vehicle will be increased if a VLPZ received a positive response from this vehicle. However, if the vehicle refuses the invitation, its reputation value will be decreased. The reputation value is calculated on the basis of the occupancy of the VLPZ at t j .t j represents the time when the vehicle quits a VLPZ, if the vehicle accepts the j th invitation from a VLPZ, otherwise, t j is the time of refusing the invitation. The following formula gives the reputation value (R j i ) of a given vehicle i after receiving the j th invitation.

R j i = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ R j -1 i +|AS| t j if v cooperates R j -1 i -|AS| t j if v defeats and R j -1 i |AS| t j 0 if v defeats and R j -1 i < |AS| t j where R j -1 i
is the old reputation value of the vehicle i.T h e reputation value of i increases as much as it cooperates. The accumulated value of reputation is thus used each time that the vehicle i needs an access to a VLPZ.

V. A N OPTIMAL DEPLOYMENT OF VLPZS

As we previously pointed out, the design the VLPZ is similar to widespread RIs like gas stations. These RIs are not mainly intended to protect the location privacy of VANETs' users, but it will be interesting to exploit them for this purpose as well. However, the deployment of VLPZs over the widespread RIs should not disturb the purpose to which these RIs are constructed for. For this reason, an optimal placement of VLPZs over existing RIs is required, in such way that the VLPZ is activated at a given RI only when it is needed. In this section, we propose an optimal deployment of VLPZs on the RIs that exist at a given cell as a function of time. We first propose a model to estimate the required VLPZs at a given cell as a function of traffic density and the demand for vehicles enter the VLPZs. We then define an objective function to select the best roadside infrastructures to host VLPZs to reduce the transportation cost of vehicles in terms of time.

A. Required VLPZs as a Function of Time

In this subsection, we provide a stochastic model to estimate the number of vehicles that are looking to enter to a VLPZ as a function of time at a given cell. The aim is to be able to predict the optimal number of VLPZs required at a given cell as a function of time. In the following, we assume a given cell that contains a single VLPZ. We define the stochastic model, illustrated in Figure 3, as follows. Let the vehicle arrival V A at the cell follows a Poisson Process Y and the inter-arrival time t A for V A has an exponential distribution with the mean 1/λ. During its residency in the cell, a vehicle may enter to a VLPZ if its location privacy protection level is below than the required level or to respond to an invitation from a VLPZ. For this reason, we define another random process M, independently of the arrival stochastic process Y. As vehicles enter the cell, M marks some of them with a positive probability ρ(t). ρ(t) models the willingness of a vehicle to enter the VLPZ during its residency period in the cell. Thus, vehicles that are not marked by M, will not enter the VLPZ during their residency in the cell. In addition, ρ(t) is a time-depended probability because it depends on the traffic density in the cell by time. Indeed, the more traffic density is, the more vehicles will enter the VLPZ. We also assume a random process R that specifies the time that will be spent by each vehicle inside the cell. This residency time can then be modeled by a random variable (G) with a distribution function F G . The vehicles' residency time is independent of the arrival process Y and the marking process M.

At t = 0, we assume there is no vehicle inside the VLPZ. Let {X(t) | t≥0} be the counting process that counts the number of vehicles that have the intention to enter the VLPZ during their residency in the cell as a function of time t.W eare then interested in E[X(t)]: the expected number of marked vehicles resided in the cell at time t. According the law of total probability, we have:

Pr[X (t) = k]= n≥0 Pr[X (t) = k | Y (t) = n] * Pr[Y (t) = n]. (1)
where Pr[X (t) = k | Y (t) = n] is the conditional probability that X (t) = kgivenn vehicles enter the cell in the period [0,t]. Knowing that the vehicles' arrival follows a Poisson process we have then:

Pr[X (t) = k]= n≥0 n k [γ(t)] k [1-γ(t)] n-k [λt] n n! exp -λt .
(2) γ (t) is the probability that a given arrived vehicle marked with a positive probability by M and it stills in the cell at time t. Given that n ≥ 0 vehicles have arrived in [0,t], where their arrival times are uniformly distributed in [0,t], γ (t) is given as follows [START_REF] Yan | Towards providing scalable and robust privacy in vehicular networks[END_REF]:

γ(t) = 1 t t 0 ρ(t -u)[1 -F G (u)] du. ( 3
)
where u is the uniform random variable on [0,t]. [START_REF] Yan | Towards providing scalable and robust privacy in vehicular networks[END_REF] demonstrated that:

Pr[X (t) = k]= [ (t)] k k! exp -(t) (4)
where {X(t) | t≥0} is a Poisson process with parameter:

(t) = λ t 0 ρ(t -u)[1 -F G (u)]du. (5)
and with an expectation E[X (t)]:

E[X (t)]= (t) = λ t 0 ρ(t -u)[1 -F G (u)]du. (6)
After estimating the number of vehicles that intend to enter a VLPZ during their residency period, we can then predict the number of VLPZs required in the cell by time, which is denoted by N vlpz (t) and given by the following formula:

N vlpz (t) = E(X (t)) K opt . (7)
where K opt is the optimal capacity of the VLPZ, which is fixed by the system designer. We denote N max the maximum number of required VLPZs at a given cell.

B. An Optimal Placement of VLPZs

In this subsection, we try to answer to the following question. Given m RIs at a given cell, with m >= N max , what are the best RIs that should host VLPZs taking reducing the transportation cost of vehicles as an objective function?

To answer to this question, we formulate the problem as follows. Let i ={ 1,...,n} the set of existing vehicles at a given cell at time t. Let j ={1,...,m} be the set of the RIs candidates to host VLPZs. Let c ij the transportation cost that is spent by a vehicle i to move to a RI j .Lety j a binary decision variable, which indicates that the infrastructure is selected to host a VLPZ at time t. x ij a binary variable, that indicates that the vehicle i is assigned to the RI j .

In order to select the best RIs to host the required VLPZs, we should minimize the following objective function F that aims to minimize the transportation cost of vehicles to move to the VLPZs.

F = min n i=1 m j =1 c ij x ij (8)
The transportation cost c ij can be expressed as the time t a k e nb yav e h i c l ei to reach a candidate RI j and quantified by the loss of pseudonyms during this time, which can be calculated using the following formula:

ci j = d ij v * η (9)
• d ij : the distance between a vehicle i and a candidate roadside infrastructure j. • v: the average speed of vehicles (m/s).

• η: the frequency of changing of pseudonym (pseudo/s). We assume that v and η are fixed values. Thus, the objective function F can be rewritten as a function of d ij as follows: [START_REF] Wiedersheim | Privacy in inter-vehicular networks: Why simple pseudonym change is not enough[END_REF] The solution's feasibility is dependent on different constraints, which are represented by the following equations: [START_REF] Lu | Pseudonym changing at social spots: An effective strategy for location privacy in VANETs[END_REF] ensures that each vehicle i is only assigned to one RI; [START_REF] Ying | Pseudonym changes scheme based on candidate-location-list in vehicular networks[END_REF] ensures that the number selected RIs is equal to the number of VLPZs required at time t (N vlpz (t)). ( 13) ensures that the number of vehicles that are assigned to each RI does not exceed the number of the capacity of the RI (K opt ); and finally, ( 14) and ( 15) are the integrity constraints.

F = min n i=1 m j =1 d ij x ij
⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ m j =1 x ij = 1 (11) m j =1 y j = N vlpz (t) (12)
n j =1

x ij <= K opt [START_REF] Ying | Motivation for protecting selfish vehicles' location privacy in vehicular networks[END_REF] x ij ∈{0, 1}

y j ∈{0, 1} (14)

VI. PERFORMANCE EVA L UAT I O N

In this section, we evaluate the performance of the proposed framework. This evaluation consists of three parts. We first evaluate the privacy protection provided by the framework. We then perform an analytical evaluation of the expected number of VLPZs required at a given cell. Finally, we run a simple algorithm to select the best RIs to host VLPZs.

A. Privacy Protection

A set of simulations are realized to evaluate the privacy protection degree provided by the proposed framework. Veins the simulation framework that is used to perform these simulations. The main foundations of Veins are OMNet++ and SUMO [START_REF] Krajzewicz | Recent development and applications of SUMO-Simulation of Urban MObility[END_REF]. These simulation tools are bi-directionally coupled and communicate through a TCP socket during the simulation runtime. The strong feature of Veins is that it is fully based full 802.11p and IEEE 1609.4 DSRC/WAVE network layers. The parameters considered in our simulation are summarized in Table II The considered scenario, models the traffic of the city of Manhattan New York, USA. We focused on a region of interest (ROI) of dimensions 2km x 2km. The vehicles were generated using SUMO to take trips of 1 hour duration over the city. We have installed a set of VLPZs (from 3 to 5) on random positions of the map.

The privacy level values and the reputation values of vehicles are initialized according to a normal distribution N (µ,σ ) with a mean equal to µ = 1.5. In addition, as shown in Table II, the required levels of all vehicles and their sensitivity parameters are assumed equals. In our evaluation, we run simulation several times with different random seeds and calculate the average value of 95% confidence interval.

Figure 4 illustrates a comparison between two variants of the framework in terms of the evolution of vehicles' privacy protection levels over time: (i) the baseline version that does not use the reputation-based mechanism to motivate vehicles to enter VLPZs, and (ii) the full version of the framework. As we can see in the Figure, the average of privacy protection levels obtained using the full version exceed the ones obtained using the baseline. Indeed, thanks to the motivation mechanism vehicles enter to VLPZs even though they reached their required level to cooperate with others vehicles, which resets the average privacy levels to A d each time it drops down.

In Figure 5, we study the impact of the number of deployed VLPZs on the average of location privacy protection levels obtained by vehicles over time. As we can see in the Figure, the average level of privacy increases with the number of deployed VLPZs. The reason for this is the fact that with a large number of deployed VLPZs, vehicles have more chance to enter a VLPZ. We also study the impact of traffic density on the average of privacy protection levels obtained by vehicles over time. For this reason, we considered two traffic density values 50 veh/km 2 and 75 veh/km 2 . As we can see in Figure 6, the average levels of privacy sightly increases with traffic density. This can be explained that with the existence of vehicles on roads, it is more likely that vehicles pass through VLPZs. Indeed, Figure 7 generally shows the occupancy of VLPZs increases with traffic density. In Figure 8, we study the impact of the adversary's power on the average of location privacy protection level obtained by vehicles over time. As we can see, the average of level of privacy decreases with the increase of the adversary's power. These results are expected due to the linear nature of the considered privacy loss model. Indeed, the adopted model is abstract and does not rely on important parameters such as the number of sent messages and the mobility of vehicles.

B. Expected Number of Required VLPZs

In this section, we illustrate the utility of the proposed model to calculate the number of required VLPZs at a given cell through a simple analytical evaluation. In this evaluation, we analyze the integral given in the formula [START_REF]Intelligent Transport Systems (ITS); Security; Trust and Privacy Management[END_REF] and calculate the required VLPZs using formula [START_REF] Schoch | Impact of pseudonym changes on geographic routing in VANETs[END_REF]. In the following, we assume that vehicles arrive at the cell with a constant rate 1000 veh/h. We also assume that the residency times of vehicles inside the cell are exponentially distributed with the distribution function F G = 1e -µt with a mean 1/λ is equal to 1 hour. M is a time-depended random process that marks vehicles according to the traffic density in the cell. For this reason, to model M, we use real measurements, recently published, of 24 hours of traffic mobility in the City of Luxembourg [START_REF] Codeca | Luxembourg SUMO traffic (LuST) scenario: 24 hours of mobility for vehicular networking research[END_REF]. We assume that, in peak hours, only 10% of vehicles intend to enter the VLPZ and the optimal capacity of a VLPZ (K opt ) is equal to 10.

Figure 9 illustrates the expected number of VLPZs (N vlpz (t)) required as a function of 24 day hours. From the Figure, we can see that N vlpz (t) starts to increase gradually from about 5 am until it reaches its maximum value (N max = 10) VLPZs at 8 am. After that, we notice that N vlpz (t) decreases until about 11 am. However, between 12 pm and 3 pm, N vlpz (t) slightly increases and decreases again. Form 4 pm, N vlpz (t) restarts to increase gradually towards the maximum value, which is reached at about 7 pm. Finally, from 8 pm, N vlpz (t) gradually decreases until the end of day.

C. RIs Selection

The selection of the best RIs to host VLPZs is Np-hard problem. In this section, we propose a simple algorithm to select the best roadside infrastructures to host VLPZs. In order to solve this problem, we first propose to group vehicles into N vlpz (t) clusters that have the same size K opt using a variation of k-means clustering algorithm. The algorithm proposed by ELKI Framework in [START_REF]Same-Size K-Means Variation[END_REF] can be used for this purpose. We then create a list that contains the distances between each centroid of a cluster and each candidate roadside infrastructure j. This list is sorted from the lowest to the highest distance. After that the selection of the list of N vlpz (t) roadside infrastructure ( ) begins. In each round, we (i) pick the first element of the list; (ii) include the roadside infrastructure j into ;a n d finally (iii) update the list by removing the distances from the centroid to the other roadside infrastructures and the distances from j to the other centroids. The algorithm runs until the selection of the N vlpz (t) roadside infrastructures is done.

An example allows illustrating the RIs selection process is given as follows. As shown in Figure 10a, we assume a cell that contains 10 RIs candidates and 70 vehicles. The positions of both vehicles and RIs are randomly generated using Matlab and the capacity of each RI (K opt ) is equal to 10. The number of RIs that should then be selected is equal to 7. Figure 10b illustrates the 7 clusters that have been created using the k-means modified version proposed by ELKI Framework and their centroids. Figure 10c illustrates the selected RIs after running the selection algorithm.

VII. DISCUSSION

In this subsection, we provide a short discussion on some advantages and limitations of PRIVANET. Indeed, PRIVANET mainly brings new solutions which are not yet implemented in the current security standards (IEEE 1609.2 [START_REF]IEEE Standard for Wireless Access in Vehicular Environments-Security Services for Applications and Management Messages[END_REF] and ETSI 102941-v1.1.1 [START_REF]Intelligent Transport Systems (ITS); Security; Trust and Privacy Management[END_REF]). Specifically, it proposes an effective pseudonym changing strategy and a new IP/MAC generation mechanism from pseudonyms. PRIVANET also proposes improvements for the solutions that are already proposed in security standards. For example, it includes a pseudonym sets distribution method that has low overhead compared to the one proposed by the security standards. In addition, the hierarchical structure of PRIVANET allows the ease of management and its modularity and extensibility make it well adapted for the future deployment of VANETs. However, PRIVANET has some limitations, especially against an active adversary model. This type of adversary can make the proposed privacy protection approach ineffective. For example, an active adversary could know all the distributed pseudonym sets if it controls RSU VLPZ s. As a result, the adversary still tracks vehicles even if they change their pseudonyms. In addition, if an active adversary controls all the VLPZs, the changing of pseudonyms will become ineffective since the adversary can easily match between the vehicles that entered the VLPZs and those that exit them.

Fortunately, the impact of the active adversary in PRIVANET depends on its coverage. Indeed, the control of all the VLPZs is more serious than the control of one or two VLPZs. To overcome this issue, PRIVANET should then be built on a strong security architecture that allows to detect active attackers and revoke them from the system.

VIII. CONCLUSION

In this paper, we proposed PRIVANET, a complete framework that can easily be deployed in the real-world and adopted by ITS community.This framework has a hierarchical structure and is mainly based on logical zones called Vehicular Location Privacy Zones (VLPZs). It considers that the vehicular geographic area is partitioned as a grid, where each cell contains one or many VLPZs. These zones can easily be deployed over the widespread Roadside Infrastructures (RIs) such as gas stations and electric vehicles charging stations. The proposed framework includes different building blocks to address the key issues of the pseudonym changing approach such as effective pseudonym changing and management and a mechanism for overcoming the selfishness behavior of vehicles. An optimal deployment of VLPZs over RIs is also proposed and the framework is evaluated and validated through extensive simulations. The obtained results are promising. They show the ability of the proposed framework to provide an efficient and secure privacy protection for VANETs'users.

Fig. 1 .

 1 Fig. 1. A global view of the PRIVANET.

Fig. 2 .

 2 Fig. 2. The VLPZ basic model.

Fig. 3 .

 3 Fig. 3. Cell stochastic model.

Fig. 4 .

 4 Fig. 4. Comparison between two variants of the framework in terms of the average privacy protection levels obtained by vehicles over time. (α = 0.1, ρ = 75 veh/km 2 , N vlpz = 4).

Fig. 5 .

 5 Fig. 5. The average of privacy protection level obtained by vehicles over time as function of the number deployed VLPZs. (α = 0.1, ρ = 75 veh/km 2 ).

Fig. 6 .

 6 Fig. 6. The average of privacy protection level obtained by vehicles over time as a function of traffic density. (α = 0.1, N vlpz = 4).

Fig. 7 .

 7 Fig. 7. The occupancy of VLPZs as a function of traffic density. (α = 0.1, N vlpz = 4).

Fig. 8 .

 8 Fig. 8. The average of privacy protection level obtained by vehicles over time as a function of the attacker power. (ρ = 75 veh/km 2 , N vlpz = 4).

Fig. 9 .

 9 Fig. 9. The expected number of VLPZs required at a given cell as a function of time.

Fig. 10 .

 10 Fig. 10. RIs selection: example.

TABLE I ACOMPARISON

 I OF PRIVANET WITH THE STATE OF ART OF PSEUDONYM-BASED SOLUTIONS

TABLE II SIMULATION PARAMETERS

 IIPARAMETERS