# A privacy preserving querying mechanism with high utility for electric
vehicles

Ugur Ilker Atmaca  Sayan Biswas  Carsten Maple  Catuscia Palamidessi U. Atmaca
and Carsten Maple are with the Secure Cyber Systems Research Group, WMG,
University of Warwick & Alan Turing Institute, UK, Emails: ugur-
<EMAIL_ADDRESS><EMAIL_ADDRESS>Biswas and C. Palamidessi are
with the INRIA & LIX, École Polytechnique, France, Emails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Electric vehicles (EVs) are gaining popularity due to the growing awareness
for a sustainable future. However, since there are disproportionately fewer
charging stations than EVs, range anxiety plays a major role in the rise in
the number of queries made along the journeys to find an available charging
station. On the other hand, the use of personal data in various types of
analytics is increasing at an unprecedented rate. Hence, the risks of privacy
violation are also surging. Geo-indistinguishability is one of the standards
for formalising location privacy as a generalisation of the local differential
privacy. However, the noise has to be carefully calibrated considering the
implications of potential utility-loss. In this paper, we introduce
approximate geo-indistinguishability (AGeoI) which allows the EVs to obfuscate
the individual query-locations while ensuring that they remain within their
preferred area of interest. It is vital because journeys are often sensitive
to a sharp drop in QoS, which has a high cost for the extra distance to be
covered. We apply AGeoI and dummy data generation to protect the privacy of
EVs during their journeys and preserve the QoS. Analytical insights and
experiments are used to demonstrate that a very high percentage of EVs get
privacy for free and that the utility-loss caused by the privacy-gain is
minuscule. Using the iterative Bayesian update, our method allows for a
private and highly accurate prediction of charging station occupancy without
disclosing query locations and vehicle trajectories, which is vital in
unprecedented traffic congestion scenarios and efficient route-planning.

###### Index Terms:

Location Privacy, Geo-Indistinguishability, Electric Vehicle, Charging
Station, Privacy-Utility Trade-off

††publicationid: pubid:

##  I Introduction

Air pollution is one of the immediate issues that the world is experiencing
[1, 2, 3]. In the United Kingdom in 2019, 27% of all greenhouse gas emissions
come from transportation, as the largest emitting sector [4, 5, 6]. Hence, the
transportation industry and academic communities are increasingly interested
in developing alternative energy vehicles to reduce emissions. Automobile
manufacturers are introducing a new generation of electric vehicles (EVs) that
often employ connected and automated driving functions [7].

EVs are regarded as one of the most promising means of reducing emissions and
reliance on fossil fuels. Along with environmental benefits, EVs provide
superior energy efficiency to conventional vehicles [8]. As the cost of
batteries continues to decrease, the large scale adoption of EVs is becoming
more viable [9]. Despite the advantages and competitive cost, many customers
remain concerned about running out of battery power before reaching their
destination or waiting for their EVs to charge. The primary obstacles to EV
adoption are the availability of chargers and the range that can be travelled
on a single charge, often referred to as _range anxiety_ in the literature
[10].

There has been some recent focus on forecasting how busy the charging stations
(CS) are in certain areas to ensure that the EVs can plan their journeys
conveniently [11, 12]. However, the existing research in this direction,
primarily founded upon machine learning based methods, do not address the
privacy concerns involved in such predictive techniques and do not consider
situations where there may arise an unprecedented traffic congestion (e.g. due
to a one-off concert or an event). One of the most successful approaches for
protecting the privacy of personal data while analysing and exploiting the
utility of data is along the lines of _differential privacy_ (DP) [13, 14],
which mathematically guarantees that the query output does not change
significantly regardless of whether a specific personal record is in the
dataset or not. Our proposed method, in addition to allowing the EVs to have
formal privacy guarantees on their queries to locate the nearest charging
stations, enables the users to estimate the live occupancy of the charging
stations efficiently allowing convenient journey-planning (e.g., avoid going
through a route aiming for a CS which has a dense crowd of EVs looking for a
CS around it).

However, the classical central DP requires a trusted curator who is
responsible for adding noise to the data before publishing or performing
analytics on it. A major drawback of such a central model is that it is
vulnerable to security breaches because the entire original data is stored in
a central server. Moreover, there is the risk of having an adversarial
curator. To circumvent the need for such a central dependency, a local model
of differential privacy (DP), also called _local differential privacy_ [15],
has been getting a lot of attention lately. In this model, users apply the LDP
mechanism directly to their data and send the locally changed data to the
server.

LDP is particularly suitable for situations where users need to communicate
their personal data in exchange for some service. One such scenario is the use
of location-based services (LBS), where a user typically reports her location
in exchange for information like the shortest path to a destination, points of
interest in the surroundings, traffic information, friends nearby, etc. One of
the recently popularised standards in location privacy is _geo-
indistinguishability_ (GeoI) [16], which optimises the quality of service
(QoS) for users while preserving a generalised notion of LDP on their location
data. The obfuscation mechanism of GeoI depends on the distance between the
original location of a user and a potential noisy location that they report
[17, 18].

GeoI can be implemented directly on the user’s device (tablet, smartphone,
etc.). The fact that the users can control their explicit privacy-protection
level for various LBS makes it very appealing. However, a drawback of
injecting noise locally to the datum is that it deteriorates the QoS due to
the lack of accuracy of the data.

On the other hand, future vehicles are getting more sophisticated in their
sensory, onboard computation, and communication capacities. Furthermore, the
emergence of Mobile Edge Computing (MEC) also changes the Intelligent
Transportation Systems (ITS) by providing a platform to assist computationally
heavy tasks by offloading the computation to the Edge cloud [19]. This
architecture often employs three tiers, with the vehicle on the first, MEC on
the second, and standard cloud services on the third [20]. Figure 1 shows the
system architecture for the location privacy framework proposed in this paper.

ITS provides a platform containing distributed and resource-constrained
systems to support real-time vehicular functions where these functions’
efficacy relies on the data shared across entities. However, the risk of
privacy disclosure and tracking increases due to data sharing [21]. Privacy-
preserving schemes are developed using established techniques such as group
signature, anonymity, and pseudonymity [22, 23]. However, it is possible to
identify privatised data with adequate background information. Hence, DP
approaches have emerged as the gold standard of data privacy because they
provide a formal privacy guarantee independent of a threat actor’s background
knowledge and computing capability [24].

GeoI is the state-of-the-art method for location privacy-preserving with LDP.
It can preserve one’s location privacy among a set of locations with similar
probability distributions without requiring a trusted third-party. It provides
rigorous privacy for location-based query processing and location data
collection by modelling the location domain based on the Euclidean plane.
However, vehicles are located on the road network under normal circumstances.
For vehicular location queries, GeoI mechanism may result in publishing
unrealistic privatised locations such as houses, parks, or lakes. Thus, there
is a need for an adapted model of GeoI for vehicular application. This paper
proposes a novel privacy model called Approximate Geo-Indistinguishability
(AGeoI), based on the notion of GeoI by using a discrete road network graph.
Our key contributions in this paper are outlined as follows.

  1. 1.

We presented the notion of AGeoI, a formal standard of location-privacy in a
bounded co-domain, by generalising the classical paradigm of GeoI and adapting
it to a graphical environment. We illustrate its applicability by proving that
it satisfies the compositionality theorem. Moreover, we show that the
truncated Laplace mechanism satisfies AGeoI by deriving the appropriate
$\epsilon$ and $\delta$ as privacy parameters.

  2. 2.

We proposed a two-way privacy-preserving navigation method for EVs dynamically
querying for charging stations (CSs) on road networks — the method protects
against threats to individual locations of their queries by ensuring AGeoI,
and we provide protection against adversaries tracing the trajectories of the
EVs by interpolating their query locations in an online setting.

  3. 3.

We performed experiments on real vehicular journey data from San Francisco
with real locations of CSs from the area under two settings of their sparsity
in the road network, and show that our method ensures a very high fraction of
EVs who enjoy _privacy for free_ and that the cost of utility-loss for the EVs
is very low compared to the formal gain in privacy.

  4. 4.

We demonstrated that our method, aside from providing formal location-privacy
guarantees, allows the EVs to predict the live occupancy of the charging
stations based on the sanitised queries received by the server, ensuring that
the users can plan their journeys conveniently.

The rest of this paper is organised as follows. Section II reviews some of the
related work in this area. Section III introduces some fundamental notions on
DP and GeoI. Section IV develops the mathematical theory of AGeoI. Section V
elucidates the model of our proposed mechanism by formalizing the problem we
are tackling, thoroughly discussing system architecture, and laying out the
privacy-threat landscape we are addressing in this work. Section VI delves
into insight into the cost of privacy on the EVs induced by our mechanism.
Section VII presents the experimental results to illustrate the working of our
mechanism, and Section VIII concludes the paper.

##  II Related Work

Both corporate and academic communities have recently piqued interest in
advancing EVs and charging infrastructure to improve the transportation
system’s sustainability. Despite the advancements, the EV sector confronts
challenges that delay the adoption process, such as range anxiety, an absence
of convenient and available charging infrastructure, and waiting time to
charge [25, 26]. An offline static map of CSs is insufficient to resolve these
obstacles since EVs may need to reserve a charging station when a trip is
planned or query the available stations based on their battery state, and CSs
must be reservable. Thus, live vehicular and charging station data is utilised
in querying and reservation/scheduling mechanisms [27, 28, 29]. Encryption
techniques can be used in such mechanisms to prevent external intrusions, but
they cannot preserve users’ privacy from malicious servers and third-party
providers.

Several data types are considered in these mechanisms, including real-time
location, intended route, battery level, and station availability, to ensure
the drivers are not detoured from their intended route[27, 30]. Although
disclosing such information poses privacy concerns for the driver’s location
and vehicle tracking, the privacy requirements of such mechanisms are not
sufficiently studied in the literature. Existing methods for planning charging
points for EV journeys are considered mechanisms for confidentiality and
integrity, but the drivers’ location privacy is regarded as an issue of trust
in the third-party service provider [31, 32].

This problem can be addressed by several approaches based on threat model of
the system. Location anonymity is achieved through cloaking an area [33, 34].
This approach can only be applied to the Edge of our system model to provide
anonymity to a group of EVs, but we consider the Edge as an honest-but-curious
threat actor and aim to preserve individual vehicles’ privacy locally. Thus,
such techniques are not trivially applicable to our considered threat model.
Furthermore, anonymity techniques do not provide a formal privacy guarantee
[35]. Similarly, mix-network approaches cannot be applied because there is no
guarantee that multiple vehicles will be present in an Edge’s coverage in any
timestamp due to vehicles’ movement [36].

An applicable approach to download the charging station’s live map on EVs to
search for the nearest or on-the-route available charging station has been
considered and studied by the community [37]; however, the communication
overhead of this technique is predicted to be much higher than the vehicles’
location-based inquiry since it will require downloading a recent snapshot of
the map for each query and, therefore, has been criticised in the literature
[38]. Moreover, due to the absence of data sharing, such methods hinder the
statistical utility of the location data for the servers that may be useful
for a variety of purposes (e.g. providing vital statistics to industries and
institutions for optimally placing the charging stations on the map based on
the query densities) and prevent the EVs from receiving any information about
the traffic around and occupancy of certain charging stations restricting them
to plan their journeys accordingly.

DP methods are increasingly being deployed to preserve location privacy in a
variety of domains, including automotive systems. The studies in [39, 40]
proposed models by deploying a GeoI-based mechanism on the Edge for location-
based services. However, their approach did not consider preserving vehicles’
location privacy against the Edge. An approach that compliments the problem we
aim to address in this paper was proposed by Qiu et al. in [41] where the
authors proposed a technique to crowd-source a task in vehicular network while
preserving GeoI of the location of the vehicles offering Mobility as a Service
in the spatial network to solve a task at a publicly known location in the map
(e.g. taxi services). The problem formulation in this work is the inverse of
what we aim to achieve in this paper. As a result, the work in [41] cannot be
extended to address the privacy concerns induced my multiple queries
dynamically made along the journey.

In [42], Cunningham et al. studied the problem of trajectory sharing under DP
and proposed a mechanism to tackle it. However, this work assumes the setting
of an offline trajectory sharing which breaks down in the practical
environment where the trajectories are being shared online as there is no
prior information or limitation on the number of queries made by an EV during
a journey, and their respective locations. Therefore, the method proposed by
the authors in [42] cannot be directly adapted to our dynamic environment
closely simulating the real-world scenario for such a use case.

Of late, a major direction of research is along the lines of studying the
statistical utility of differentially private data. A standard notion of
statistical utility, which is extended to a variety of contexts, is the
precision of the estimation of the distribution on the original data from that
of the noisy data. Iterative Bayesian update (IBU) [43, 44], an instance of
the famous _expectation maximization (EM)_ method from statistics, provides
one of the most flexible and powerful estimation techniques and has recently
become in the focus of the community [45, 46]. In this work, we use IBU to
approximate the distribution of the true locations of the queries made to the
server and based on that, the users of the EVs can predict the availability of
the the CSs around them in real time and plan their route accordingly.

##  III Preliminaries

The most successful approach to formally address the privacy risks is DP,
mathematically guaranteeing that the query output does not change
significantly regardless of whether a specific personal record is in a dataset
or not. Most research performed in this area probes two main directions. One
is the classical central framework [13, 14], in which a trusted third-party
(the curator) collects the users’ personal data and obfuscates them with a
differentially private mechanism.

######  Definition III.1 (Differential privacy [13, 14]).

For a certain query, a randomizing mechanism $\mathcal{R}$ provides
_$\epsilon$ -DP_ if, for all neighbouring111differing in exactly one place
datasets, $D$ and $D^{\prime}$, and all $S\subseteq$ Range($\mathcal{R}$), we
have $\mathbb{P}[\mathcal{R}(D)\in S]\leq
e^{\epsilon}\,\mathbb{P}[\mathcal{R}(D^{\prime})\in S]$.

A major drawback of central model is that it is vulnerable to security
breaches because the entire original data is stored in a central server.
Moreover, there is the risk that the curator may be corrupted. Therefore, a
local variant of the central model has been widely popularized of late [15],
where the users apply a randomizing mechanism locally on their data and send
the perturbed data to the collector such that a particular value of a user’s
data does not have a major probabilistic impact on the outcome of the query.

######  Definition III.2 (Local differential privacy [15]).

Let $\mathcal{X}$ and $\mathcal{Y}$ denote the spaces of original and noisy
data, respectively. A randomizing mechanism $\mathcal{R}$ provides _$\epsilon$
-LDP_ if, for all $x,\,x^{\prime}\,\in\,\mathcal{X}$, and all
$y\,\in\,\mathcal{Y}$, we have $\mathbb{P}[\mathcal{R}(x)=y]\leq
e^{\epsilon}\,\mathbb{P}\left[\mathcal{R}(x^{\prime})=y\right]$.

Recently, GeoI [16], a variant of the local DP capturing the essence of the
distance between locations [17, 18] has been in focus as a standard for
privacy protection for location based services, being motivated by the idea of
preserving the best possible quality of service despite the local obfuscation
operated on the data.

######  Definition III.3 (Geo-indistinguishability [16]).

Let $\mathcal{X}$ be a space of locations and let $d_{\text{E}}(x,x^{\prime})$
denote the _Euclidean distance_ between $x\in\mathcal{X}$ and
$x^{\prime}\in\mathcal{X}$. A randomizing mechanism $\mathcal{R}$ is
_$\epsilon$ -geo-indistinguishable_ if for all $x_{1},\,x_{2}\in\mathcal{X}$,
and every $y\in\mathcal{X}$, we have $\mathbb{P}[\mathcal{R}(x)=y]\leq
e^{\epsilon
d_{\text{E}}(x_{1},x_{2})}\,\mathbb{P}\left[\mathcal{R}(x^{\prime})=y\right]$.

######  Definition III.4 (Iterative Bayesian update [43]).

Let $\mathcal{C}$ be a privacy mechanism that locally obfuscates points from
the discrete space $\mathcal{X}$ to $\mathcal{Y}$ such that
$\mathcal{C}_{xy}=\mathbb{P}(y|x)$ for all $x,y\in\mathcal{X},\mathcal{Y}$.
Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables on $\mathcal{X}$ following
some distribution $\pi_{\mathcal{X}}$. Let $Y_{i}$ denote the random variable
of the output when $X_{i}$ is obfuscated with $\mathcal{C}$.

Let $\mathbf{y}\in\mathcal{Y}^{n}$ be a realisation of
$\\{Y_{1},\ldots,Y_{n}\\}$ and $q$ be the empirical distribution obtained by
counting the frequencies of each element of $\mathcal{Y}$ as observed in
$\mathbf{y}$. The _iterative Bayesian update (IBU)_ is a state-of-the-art EM
technique to estimate $\pi_{\mathcal{X}}$ by converging to the maximum
likelihood estimate (MLE) of $\pi_{\mathcal{X}}$ with the knowledge of
$\mathbf{y}$ and $\mathcal{C}$. IBU works as follows:

  1. 1.

Start with any full-support PMF $\theta_{0}$ on $\mathcal{X}$.

  2. 2.

Iterate
$\theta_{t+1}(x)=\sum\limits_{y\in\mathcal{Y}}q(y)\frac{\theta_{t}(x)\mathcal{C}_{xy}}{\sum\limits_{z\in\mathcal{X}}\theta_{t}(z)\mathcal{C}_{zy}}$
for all $x\in\mathcal{X}$.

TABLE I: List of key notations

Notation | Description
---|---
$\mathcal{X}$ | Domain of original locations
$d_{\mathcal{X}}$ | Distance on $\mathcal{X}$
$\mathcal{Y}$ | Domain of obfuscated locations
$d_{\mathcal{Y}}$ | Distance on $\mathcal{Y}$
$\mathbb{P}_{\mathcal{K}}\left[y|x\right]$ | Prob. that mechanism $\mathcal{K}$, applied to value $x$, reports $y$
$I$ | Fixed Edge in the network
$R(I)$ | Area of coverage by $I$
$m$ | Number of locations reported by each EV
$l_{u}$ | Vector of locations reported by EV $u$
$\mathcal{L}(t)$ | Set of location vectors received by $I$ at time $t$
$\mathcal{L}^{\prime}(t)$ | Shuffled set of all individual locations queried at time $t$
$\mathcal{R}(t)$ | Set of nearest CSs for $\mathcal{L}^{\prime}(t)$
$G$ | Road network graph
$d_{G}$ | Travelling distance in graph $G$

##  IV Approximate geo-indistinguishability

In the classical framework of GeoI [16], the space of the noisy data is, in
theory, unbounded under the planar Laplace mechanism. Under a certain level of
GeoI that is achieved, the planar Laplace mechanism ensures a non-zero
probability of obfuscating an original location to a privatised one which may
be quite far, thus inducing a possibility of a substantial deterioration in
the QoS of the users. This loss of QoS can be more sensitive in the context of
the navigation of EVs, where it is extremely important to prioritize a bounded
domain where a user is willing to drive – this may be a result of time
constraint, rising cost of fuel, geographical boundaries (e.g. international
borders), etc. – giving rise to an idea of _area of interest_ for each EV.
This motivated us to extend the classical GeoI to a more generalized,
approximate paradigm, inspired by the approach of the development of
approximate DP from its pure counterpart.

Let $\mathcal{X}$ and $\mathcal{Y}$ be the spaces of the real and nosy
locations equipped with distance metrics $d_{\mathcal{X}}$ and
$d_{\mathcal{Y}}$, respectively. In general
$\left(\mathcal{X},d_{\mathcal{X}}\right)$ and
$\left(\mathcal{Y},d_{\mathcal{Y}}\right)$ may be different and unrelated.
However, for simplicity, here we assume $\mathcal{X}\subseteq\mathcal{Y}$ and,
therefore, $d_{\mathcal{X}}=d_{\mathcal{Y}}=d$, and we proceed to define the
notion of _approximate geo-indistinguishability_. Note that $d$ may not
necessarily need to be symmetric, i.e., there may exist
$x1,\,x_{2}\,\in\,\mathcal{Y}$ such that $d(x_{1},x_{2})\neq d(x_{2},x_{1})$.

######  Definition IV.1 (Approximate geo-indistinguishability).

A mechanism $\mathcal{K}$ is _approximately geo-indistinguishable (AGeoI)_ or
$\emph{(}\epsilon,\delta)$-_geo-indistinguishable_ if for any set of values
$S\subseteq\mathcal{Y}$ and any pair of values
$x,x^{\prime}\,\in\,\mathcal{X}$, there exists some
$\epsilon,\,\delta\in\mathbb{R}_{\geq 0}$ such that $\delta
e^{d(x,x^{\prime})}\in[0,1]$, we have:

$\mathbb{P}_{\mathcal{K}}\left[y\,\in\,S|x\right]\leq
e^{\epsilon\,d(x,x^{\prime})}\mathbb{P}_{\mathcal{K}}\left[y\,\in\,S|x^{\prime}\right]+\delta\,e^{d(x,x^{\prime})}$
(1)

One of the biggest advantages of DP and all of its variants that are accepted
by the community is the property of compositionality, where the level of
privacy can be formally derived with repeated number of queries. Thus, we now
enable ourselves to investigate the working of the compositionality theorem
with the approximate geo-indistinguishability which we defined, to stay
consistent with the literature [35].

######  Theorem IV.1.

[Compositionality Theorem for AGeoI] Let mechanisms $\mathcal{K}_{1}$ and
$\mathcal{K}_{2}$ be $(\epsilon_{1},\,\delta_{1})$ and
$(\epsilon_{2},\,\delta_{2})$ geo-indistinguishable, respectively. Then their
composition is $(\epsilon_{1}+\epsilon_{2},\,\delta_{1}+\delta_{2})$-geo-
indistinguishable. In other words, for every
$S_{1},\,S_{2}\subseteq\mathcal{Y}$ and all
$x_{1},\,x^{\prime}_{1},\,x_{2},\,x^{\prime}_{2}\,\in\,\mathcal{X}$, we have:

$\displaystyle\mathbb{P}_{\mathcal{K}_{1},\mathcal{K}_{2}}\left[(y_{1},y_{2})\,\in\,S_{1}\times
S_{2}|(x_{1},x_{2})\right]$ $\displaystyle\leq
e^{\epsilon_{1}\,d(x_{1},x^{\prime}_{1})+\epsilon_{2}\,d(x_{2},x^{\prime}_{2})}$
$\displaystyle\times\mathbb{P}_{\mathcal{K}_{1},\mathcal{K}_{2}}\left[(y_{1},y_{2})\,\in\,S_{1}\times
S_{2}|(x^{\prime}_{1},x^{\prime}_{2})\right]$
$\displaystyle+\left(\delta_{1}+\delta_{2}\right)\,e^{d(x_{1},x^{\prime}_{1})+d(x_{2},x^{\prime}_{2})}$
(2)

###### Proof.

Let us simplify the notation and denote:

$P_{i}=\mathbb{P}_{\mathcal{K}_{i}}\left[y_{i}\in S_{i}|x_{i}\right]$
$P^{\prime}_{i}=\mathbb{P}_{\mathcal{K}_{i}}\left[y_{i}\in
S_{i}|x^{\prime}_{i}\right]$
$\tilde{\delta}_{i}=\delta_{i}\,e^{d(x_{i},x^{\prime}_{i})}$

for $i\,\in\,\\{1,2\\}$. As mechanisms $\mathcal{K}_{1}$ and $\mathcal{K}_{2}$
are applied independently, we have:

$\displaystyle\mathbb{P}_{\mathcal{K}_{1},\mathcal{K}_{2}}\left[(y_{1},y_{2})\,\in\,S_{1}\times
S_{2}|(x_{1},x_{2})\right]=P_{1}.P_{2}$ (3)
$\displaystyle\mathbb{P}_{\mathcal{K}_{1},\mathcal{K}_{2}}\left[(y_{1},y_{2})\,\in\,S_{1}\times
S_{2}|(x^{\prime}_{1},x^{\prime}_{2})\right]=P^{\prime}_{1}.P^{\prime}_{2}$
(4)

Therefore, we obtain:

$\displaystyle\mathbb{P}_{\mathcal{K}_{1},\mathcal{K}_{2}}\left[(y_{1},y_{2})\,\in\,S_{1}\times
S_{2}|(x_{1},x_{2})\right]=P_{1}.P_{2}$
$\displaystyle\leq\left(\min\left(1-\delta_{1},e^{\epsilon_{1}\,d(x_{1},x^{\prime}_{1})}P^{\prime}_{1}\right)+\tilde{\delta}_{1}\right)$
$\displaystyle\times\left(\min\left(1-\delta_{2},e^{\epsilon_{2}\,d(x_{2},x^{\prime}_{2})}P^{\prime}_{2}\right)+\tilde{\delta}_{2}\right)$
$\displaystyle\leq
m_{1}m_{2}+\tilde{\delta}_{1}m_{2}+m_{1}\tilde{\delta}_{2}+\tilde{\delta}_{1}+\tilde{\delta}_{2}$
$\displaystyle\left[\text{where
}m_{i}=\min\left(1-\delta_{i},e^{\epsilon_{i}\,d(x_{i},x^{\prime}_{i})}P^{\prime}_{i}\right)\right]$
$\displaystyle\leq
e^{\epsilon_{1}\,d(x_{1},x^{\prime}_{1})+\epsilon_{2}\,d(x_{2},x^{\prime}_{2})}P^{\prime}_{1}P^{\prime}_{2}$
$\displaystyle+\tilde{\delta_{1}}-\tilde{\delta_{1}}\tilde{\delta_{2}}+\tilde{\delta_{2}}-\tilde{\delta_{1}}\tilde{\delta_{2}}+\tilde{\delta_{1}}\tilde{\delta_{2}}$
$\displaystyle\leq
e^{\epsilon_{1}\,d(x_{1},x^{\prime}_{1})+\epsilon_{2}\,d(x_{2},x^{\prime}_{2})}$
$\displaystyle\times\mathbb{P}_{\mathcal{K}_{1},\mathcal{K}_{2}}\left[(y_{1},y_{2})\,\in\,S_{1}\times
S_{2}|(x^{\prime}_{1},x^{\prime}_{2})\right]$
$\displaystyle+\left(\delta_{1}+\delta_{2}\right)\,e^{d(x_{1},x^{\prime}_{1})+d(x_{2},x^{\prime}_{2})}$

∎

We now proceed to generalize the conventional planar Laplace mechanism [47] to
define the _truncated Laplace mechanism_ extended to a generic metric space.

######  Definition IV.2 (Truncated Laplace mechanism).

The _truncated Laplace mechanism_ $\mathcal{L}$ on a space $\mathcal{X}$
equipped with, not necessarily symmetric, distance metric $d$ truncated to a
radius $r$, is defined as:

$\displaystyle\mathbb{P}_{\mathcal{L}}[y|x]=\begin{cases}c\,e^{-\epsilon\,d(y,x)}&\text{if
}d(x,y)\leq r\\\ 0&\text{otherwise}\end{cases}$ (5)

where $c$ is the truncated normalization constant defined such that
$\int\limits_{y\in\mathcal{Y}}\mathbb{P}_{\mathcal{L}}[y|x]dy=1$, and
$\epsilon$ is the desired privacy parameter. Let us call $r$ to be the _radius
of truncation_ for $\mathcal{L}$.

Note: In case of a discrete domain $\mathcal{Y}$, $c$ is defined by
normalizing $\sum\limits_{y\in\mathcal{Y}}\mathbb{P}_{\mathcal{L}}[y|x]=1$,
and in this case $\mathcal{L}$ is an extended truncated geometric mechanism
[48] extended to a generic metric space.

######  Lemma IV.2.

$\frac{e^{-\epsilon\,d(x_{1},x_{2})}\mathbb{P}\left[y|x_{1}\right]-\mathbb{P}\left[y|x_{2}\right]}{e^{(1-\epsilon)\,d(x_{1},x_{2})}}\,e^{r}\leq
1$, where $r$ is the radius of truncation for $\mathcal{L}$, as in (1).

###### Proof.

$\displaystyle\frac{e^{-\epsilon\,d(x_{1},x_{2})}\mathbb{P}\left[y|x_{1}\right]-\mathbb{P}\left[y|x_{2}\right]}{e^{(1-\epsilon)\,d(x_{1},x_{2})}}\,e^{r}\leq
1$ $\displaystyle\iff c\left(e^{-\epsilon
d(x_{1},x_{2})+d(x_{1},y)}-e^{-\epsilon d(x_{2},y)}\right)$ $\displaystyle\leq
e^{(1-\epsilon)d(x_{1},x_{2})-r}$ (6)

Now we observe that $d(x_{1},x_{2})+d(x_{1},y)\geq d(x_{2},y)$ due to the fact
that $d$ is a metric and it satisfies triangle inequality. Immediately, we
have $e^{-\epsilon d(x_{1},x_{2})+d(x_{1},y)}-e^{-\epsilon d(x_{2},y)}\leq 0$
for any $\epsilon\in\mathbb{R}_{\geq 0}$. Therefore, as $c\geq 0$, (6) is
trivially satisfied as the RHS is always non-negative. ∎

######  Theorem IV.3.

$\mathcal{L}$ satisfies $(\epsilon,\delta)$-geo-indistinguishability where
$\delta=\max\left\\{\max\limits_{\begin{subarray}{c}S\subseteq\mathcal{Y}\\\
x_{1},x_{2}\in\mathcal{X}\end{subarray}}\frac{e^{-\epsilon\,d(x_{1},x_{2})}\mathbb{P}\left[y|x_{1}\right]-\mathbb{P}\left[y|x_{2}\right]}{e^{(1-\epsilon)\,d(x_{1},x_{2})}},0\right\\}$.

###### Proof.

Trivially $\delta e^{d(x_{1},x_{2})}>0$ for any $x_{1},x_{2}\in\mathcal{X}$ as
$\delta>0$. Moreover, Lemma IV.2 ensures that $\delta e^{d(x_{1},x_{2})}<1$.

Now observe that for every $S\subseteq\mathcal{Y}$ and for all
$x_{1},x_{2}\,\in\,\mathcal{X}$, we have:

$\displaystyle
e^{-\epsilon\,d(x_{1},x_{2})}\mathbb{P}_{\mathcal{L}}\left[y|x_{1}\right]-\mathbb{P}_{\mathcal{L}}\left[y|x_{2}\right]\leq\delta\,e^{(1-\epsilon)\,d(x_{1},x_{2})}$
$\displaystyle\implies\mathbb{P}_{\mathcal{L}}\left[y|x_{1}\right]-e^{\epsilon\,d(x_{1},x_{2})}\mathbb{P}_{\mathcal{L}}\left[y|x_{2}\right]\leq\delta\,e^{d(x_{1},x_{2})}$

∎

The explicit process of sampling private locations satisfying AGeoI from a
given set of original locations through truncated Laplace mechanism on a
discrete location space has been described in Algorithms 1 and 2.

Input: Discrete domain of original locations: $\mathcal{X}$, Discrete domain
of private locations: $\mathcal{Y}$, Desired privacy parameter: $\epsilon$,
Desired truncation radius: $r$; Output: Channel $C$ satisfying (5);

Function  _DTLap(_$\mathcal{X},\mathcal{Y},\epsilon,r$_)_:

Set $C\leftarrow\text{empty channel}$;

Set $Y\leftarrow\text{empty list}$;

for  _$x\in\mathcal{X}$_ do

$c_{x}=\frac{1}{\sum\limits_{\begin{subarray}{c}y\in\mathcal{Y}\\\ d(x,y)\leq
r\end{subarray}}e^{-\epsilon\,d(x,y)}}$ ;

for  _$y\in\mathcal{Y}$_ do

if  _$d(x,y)\leq r$_ then

$C[x,y]=0$

else

$C[x,y]=c_{x}\,e^{-\epsilon\,d(x,y)}$

Return: $C$;

Algorithm 1 Discrete and truncated Laplace mechanism (DTLap)

Input: Discrete domain of original locations: $\mathcal{X}$, Discrete domain
of private locations: $\mathcal{Y}$, Desired privacy parameter: $\epsilon$,
Desired truncation radius: $r$; Vector of original locations: $X$;

Output: Corresponding vector of private locations: $Y$;

Function  _DTLapSamp(_$\mathcal{X},\mathcal{Y},\epsilon,r,X$_)_:

$C=$ DTLap($\mathcal{X},\mathcal{Y},\epsilon,r$);

Set $Y\leftarrow\text{empty list}$;

for  _$x\in X$_ do

Randomly sample $y\in\mathcal{Y}\sim C[x,:]$;

Append $y$ to $Y$

Return: $Y$;

Algorithm 2 Sampling private locations with DTLap (DTLapSamp)

##  V System Model

This section details our privacy-preserving model for finding an optimal
charging station in the Internet of Vehicles (IoV) as a use case of the
proposed AGeoI technique. We begin with a discussion of the location privacy
problems inherent in finding optimal CSs in the IoV. This is followed by road
networking modelling, a description of the system architecture for
differentially private location sharing, the trust relationship between system
tiers, and the privacy threat model.

###  V-A Problem Statement

EVs have been identified as a critical component of future sustainable
transportation systems to reduce CO2 emissions and have garnered significant
attention from academia and business [26]. Due to the limited battery
capacity, EVs may be required to visit CSs during journeys. It causes some
drivers to have range anxiety, which is the vehicle has insufficient battery
power to cover the travel needed to reach its intended destination. It is
highlighted as one of the barriers to EVs’ widespread adoption [49]. CSs can
not always be readily available since it often takes a while to be
sufficiently charged for EVs. A CS booking service can help to overcome range
anxiety.

EVs may access such services through third-party providers to discover the
nearest and readily available CSs to minimise charging wait times by using
static or live location queries. However, location sharing raises privacy
challenges, such as vehicle tracking. GeoI technique provides a formal privacy
guarantee for location queries. However, it is not highly applicable to this
use case for two reasons. It does not consider the feasible locations where a
vehicle can be present, and it does not stop vehicle tracking in the case of
linked queries during the vehicle trajectory. Thus, a tailored privacy-
preserving mechanism is facilitated by combining the proposed AGeoI technique
with dummy location generation.

###  V-B Road Network Model

Similar to [41], the road network $G$ is represented as a weighted directed
graph $G=(N,E,W)$, where $N$ is the set of nodes, $E\subseteq N^{2}$ is the
set of edges, and $W:N^{2}\rightarrow\mathbb{R}^{+}$ is the set of weights
representing the minimum travelling distance between any two nodes. The nodes
and edges correspond to junctions and road segments of the network,
respectively. Each edge $e\in E$ is addressed by the pair of respective
starting node, ending node, and a weight representing the travelling distance
through that edge, i.e., $e=(N^{s}_{e},N^{e}_{e},w_{e})\in N$, where the
direction of the traffic is from $N^{s}_{e}$ to $N^{e}_{e}$ on $e$. For any
$i\in N$ and $j\in N$, let the sequence of edges $(e_{1},\ldots,e_{r})$ denote
a _path_ from node $i$ to node $j$ if $N^{s}_{e_{1}}=i$ and $N^{e}_{e_{r}}=j$.
Hence, let $C(i,j)$ represent the set of paths that connect node $i$ to node
$j$. Then $W$ is a $N\times N$ matrix, where

$W_{ij}=\begin{cases}\min\limits_{p\in C(i,j)}\sum\limits_{e\in p}w_{e}&\text{
if $C(i,j)\neq\phi$}\\\ \infty&\text{ otherwise}\end{cases}$

Essentially $W_{ij}$ is the shortest travelling distance from node $i$ to node
$j$ in the network. We shall address the quantity $W_{ij}$ as the _traversal
distance_ between nodes $i$ and $j$ in the graph $G$ and denote it as
$d_{G}(i,j)$ for every $(i,j)\,\in N^{2}$. Note that, as $G$ is a directed
graph, $d_{G}$ may not be symmetric.

###  V-C System Architecture

Figure 1: System Architecture (EV:Electric Vehicle, RSU: Roadside Unit, MEC:
Mobile-Edge Computing Unit)

IoV applications are transforming transportation systems by reducing human
error, increasing travel convenience, and lowering energy, operational, and
environmental costs [50, 51]. Electric vehicles (EVs) have emerged as a viable
technology for lowering carbon emissions and travel costs [52]. However, range
anxiety is one of the major challenges of their wide adoption. Vehicular
location data can be utilised to optimise the vehicle charging plan and
mitigate range anxiety. Third-party services such as Chargemap [53] and
PlugShare [31] can recommend available and the closest CSs for the users.
However, users are required to trust these third-party service providers to
use these services, which presents significant privacy concerns in the honest-
but-curious service provider threat model.

As the system architecture is depicted in Figure 1, the vehicles are part of a
three-tier cloud computing architecture and connected to Roadside Units
(RSUs), MEC Server, and the Core Cloud Network through a secure communication
channel, where these components are considered trusted. The Core Cloud Network
enables the connection between the vehicle and third-party services, including
charging station recommender, as the main consideration of this paper.
However, it is not possible to ensure fully trusted third-party services that
they will not utilise vehicular location data for further objectives. Thus,
the honest-but curious threat model is considered for the third-party service
provider and only privatised vehicular location data is shared in our proposed
architecture. The roles of the system components are described in the
following.

####  V-C1 Vehicle Tier

In this paper, we fix a road network $G$ with nodes $G(N)$ and edges $G(E)$.
We choose an arbitrary edge $I\in G$, and focus on the queries made by the EVs
in $I$’s range of coverage, $R(I)$, provided by its RSU. When an EV moves from
the area of coverage of one Edge cloud to another, we can assume the queries
and the privacy threats against the Edge to reset as each Edge communicates
with the Cloud-based services and the third-party service providers.

####  V-C2 Edge Tier

Given the large volume of data generated and shared between vehicles and
infrastructure, installing Edge cloud close to the vehicles are needed to host
the off-board vehicular services, which require a low access latency from the
onboard vehicular services [54]. Along with essential data processing and
forwarding functions, the Edge tier provides another layer for data
aggregation and deploying additional privacy-preserving measures before
sharing the data with any third-parties.

####  V-C3 Cloud Tier

It is expected to provide computation and storage capabilities for top-level
processes, including data sharing interfaces for third-party services.

####  V-C4 Third-party Service Provider

It is the external party to ITS and is expected to enhance the quality of the
function for finding the available CSs for the vehicles by receiving search
queries compromised of privatised and dummy location vectors for the
respective vehicles.

####  V-C5 Communication Channel

ITS comprises a network of RSU, vehicle on-board electronic control units
(ECU), and distributed cloud computing and storage services. Wireless
communications are enabled for V2V (Vehicle-to-Vehicle), V2I (Vehicle-to-
Infrastructure) and V2X(Vehicle-to-Everything) by the technologies such as
IEEE 802.11p DSRC/WAVE (Dedicated Short Range Communication/Wireless Access in
Vehicular Environments), cellular advances such as C-V2X, and the long-term
evolution for vehicles (LTE-V) [55]. Confidentiality of the wireless
communication channel is secured by public key infrastructure (PKI) encryption
methods which is beyond the scope of this work.

###  V-D Privacy Threat Landscape

In real-time IoV location-based applications, vehicle users who wish to
receive services tailored to their current locations need to share their
location with the service provider. Different applications may have varying
needs for data sensitivity. Data perturbation techniques are often used in
private data sharing by introducing uncertainty in the data, which entails a
trade-off in terms of the related application’s quality of service in general.
For example, EV users who want to locate the nearest available charging
station during travel can send a query with their current location to a
service provider using the Intelligent Transportation Systems (ITS)
infrastructure.

We consider the system into three categories: (i) the vehicle users (data
subject), (ii) ITS infrastructure, including the MEC and Cloud Tiers (data
controller and data processor), and (iii) the third-party that receives the
privatised data from the deployed deployment privacy-preserving mechanisms.
The third-party is assumed to be an EV charging management system, which may
operate in a registration-based approach for a specific area.

The vehicular location data may also be subject to unauthorised use, data
inference, retention or disclosure besides its primary use. Thus, a privacy-
preserving mechanism can be utilised for location data sharing to provide a
privacy guarantee while the users can receive the same or similar quality of
service. Thus, the third-party provider is considered an honest-but-curious
adversary model, which assumes it is honest in accurately executing the
protocol required to provide location data. However, it may be curious to
infer users’ private information based on the obtained location data [56].

In this work, we mainly address two notable sources of threat that might put
the EVs’ privacy at risk:

Location identification: It is essential that the locations of the queries
made by the EVs are protected from being identified. For the use case of
location CSs, it is essential that the privatized version of the true location
of the EV is within a certain radius of interest w.p. 1, making sure that the
reported location is within a feasible and drivable distance away, and most
importantly, within the area of coverage of the Edge where its true location
lies. Therefore, we defined AGeoI as an extension of GeoI, which is the
standard for location privacy. Thus, to ensure the privacy of the position of
any given query in the road network, the EVs locally obfuscate their true
locations using the truncated Laplace mechanism with their desired parameter
$\epsilon$ and the radius of truncation $r$, which, in turn, decide the value
of $\delta$.

Journey tracing: It is often the case that a certain EV might enquire about
the nearest available charging station, but choose to proceed with the journey
at that point of time, and raise further queries along the journey. In our
model, we capture this realistic setting by allowing multiple queries to be
made by the EV in a given journey. This immediately leads to a threat of
approximately tracing the trajectory of the journey of an EV by interpolating
the locations of the query, despite having each individual location being
AGeoI.

This is due to the fact that the obfuscated location of each query is not
distinguishable from the real location, but they are not too far off from each
other with a very high probability. Therefore, if the number of queries made
in a single journey is large, it could be fairly straightforward to
approximately deduce the trajectory of the journey.

Cunningham et al. [42] proposed a mechanism to securely share trajectories
under LDP. However, the authors in [42] assumed a model of offline sharing of
the entire trajectory and, hence, sanitising it with the proposed mechanism to
engender a LDP guarantee. In our setting, this method cannot be directly
implemented as we are working in a dynamic environment where the queries made
by the EVs are in real time, with the server not having any prior knowledge of
the number or the location of the queries made by a certain EV. Therefore, the
mechanism of [42] cannot trivially be extended in the online location-sharing
environment, and hence, the threat of adversaries able to reconstruct the
journey of a particular EV with a high number of queries remains as a concern.

Figure 2: Reported dummy and privatised locations for two respective time
windows (White Pins: Privatised locations, Orange Pins: Dummy locations in
$1^{\text{st}}$ Time window, Blue Pins: Dummy locations in $2^{\text{nd}}$
Time window) Figure 3: A toy example for a static location query on discrete
road network Figure 4: A toy example for linked 3 location queries on discrete
road network

###  V-E Proposed Method

At every query made along the journey, an EV $u$ located within the coverage
of an Edge $I$ locally obfuscates its true location $x^{u}\in R(I)$ to
$x^{u}_{1}\in R(I)$ using the truncated Laplace mechanism, guaranteeing AGeoI,
and generate $m-1$ feasible dummy locations
$\\{x^{u}_{2},\ldots,x^{u}_{m}\\}\in R(I)^{m-1}$, i.e., locations that cannot
be trivially identified as being artificially generated given the query of the
previous time stamp w.r.t. realistic speed limits, travelling conditions, etc.
For the first query that $u$ makes along its journey, it can generate any
random $m-1$ dummy locations in $R(I)$. Thus, each CS query of $u$ consists of
reporting the vector of $m$ locations,
$l_{u}=\left(x^{u}_{1},\ldots,x^{u}_{m}\right)\in\mathbb{R}(I)^{m}$, to $I$
for the Edge to process and communicate the query to the Cloud services and
the third-parties to find the nearest available CSs in $R(I)$ for $u$. This
inductively ensures that the adversary will have at least $m$ possible
trajectories that the EV could have realistically followed at every time
stamp, making it highly improbable for the Edge and the third-party to be able
to conclude which of them was the actual journey as, after $k$ queries made
along a single journey, each interpolated trajectory will have a probability
of at least $1/m^{k}$ of being the real one.

Figure 2 shows an example of reported $10$ dummy locations with the privatised
location for two respective time windows, where the dummy locations in the
following time window can have a feasible link at least one of the preceding
dummy locations. Toy examples are depicted on Figures 3 and 4 as more
simplistic explanations of the proposed privacy-preserving mechanism, where
the first represents a static query on an exampler discrete road network, and
the following one represents linked dynamic queries on the same exampler
discrete road network.

At any time, the Edge collects all the reported locations from the querying
EVs, shuffles them by effacing the links between the location vectors and the
corresponding EVs, and sends this jumbled collection of all the reported
locations in the network for knowing their respective nearest available CSs to
the third-party service provider. After receiving the response, the Edge,
which internally keeps the record of the IDs of the EVs against their queried
locations, assigns the corresponding vector of locations of the nearest
available CSs to each EV and communicates them back to the respective
vehicles.

In other words, at time $t$, if the Edge receives the location vectors from
$k_{t}$ querying EVs as $\mathcal{L}(t)=\\{l_{u_{1}},\ldots,l_{u_{k_{t}}}\\}$,
the Edge is responsible for shuffling all the individual location points in
these reported vectors and forward the scrambled collection of locations
$\mathcal{L}^{\prime}(t)=\\{x^{u}_{i}\colon
u\in\\{u_{1},\ldots,u_{k_{t}},i\in[m]\\}$ to the Cloud and the third-party,
while internally keeping a track of the IDs of the EVs to reconnect the query-
response back to the corresponding users. Setting $\hat{x}$ as the location of
the nearest available charging station from location $x$ in $R(I)$, the Edge
receives $\mathcal{R}(t)=\\{\hat{x}^{u}_{i}\colon
u\in\\{u_{1},\ldots,u_{k_{t}},i\in[m]\\}$ as the response from the third-party
service provider handling the CS data real-time. After this, matching the
stored IDs of the EVs with the locations of the CSs, the Edge communicates the
response vector $\hat{l}_{u}=(\hat{x}^{u}_{i}:i\in[m])$ back to the
corresponding EV $u$. Then the EV can choose to navigate to
$\operatorname*{arg\,min}_{x\in\hat{l}_{u}}\\{d_{G}(x,x_{u})\\}$, where
$x_{u}$ is the real location of EV $u$. The overview of this mechanism is
explained in Figure 1.

##  VI Cost of privacy analysis

######  Definition VI.1 (Cost of privacy).

Suppose an EV $u$ at location $x^{u}$ chooses to locally obfuscate its real
location of query as $x^{u}_{1}$ using the truncated Laplace mechanism
$\mathcal{L}_{\epsilon,r}$ satisfying $(\epsilon,\delta)$-geo-
indistinguishability with a corresponding radius of truncation $r$. Then we
define the _cost of privacy (CoP)_ of EV $u$ as
$\operatorname{CoP}(u,\mathcal{L}_{\epsilon,r})=\mathbf{c}(x^{u},\hat{x}^{u}_{1})-\mathbf{c}(x^{u},\hat{x}^{u})$,
where $\hat{x}^{u}$ and $\hat{x}^{u}_{1}$ are the nearest available CSs in the
network to $x^{u}$ and $x^{u}_{1}$, respectively, and
$\mathbf{c}:G(N)^{2}\mapsto\mathbb{R}^{+}$ is any cost function that reflects
the cost of commute from locations $x$ to $y$ in the network.

In other words, CoP, as in Definition VI.1, essentially captures the _extra_
cost that an EV needs to cover as a result of the privatized location it
reports to the Edge satisfying AGeoI, as opposed to its true location. For the
purpose of this paper and simplicity of the analysis, we considered the cost
function as the travelling distance in the network, i.e., $\mathbf{c}=d_{G}$.
However, in practice, any suitable cost function could be used (e.g. fuel
efficiency, time, etc.) could be used as $\mathbf{c}$, depending on the
context and requirement of the architecture.

To formally characterize and analyze the CoP of the EVs in the network,
inspired from the classical version of _Voronoi decomposition_ , we extend the
concept in the setting of our road network in the network coverage for a fixed
Edge w.r.t. graph-traversal distance, $d_{g}$.

######  Definition VI.2 (Voronoi decomposition).

Let $G$ be the graph representing the road network equipped with travelling
distance $d_{G}$. Let the set of CSs in $G$ be
$C_{G}=\\{c_{1},\ldots,c_{n_{G}}\\}$. Then the _Voronoi decomposition_ on $G$
w.r.t. $C_{G}$ is defined as $\mathbf{V}_{G}=\\{V_{i}\colon\,i\in[n_{G}]\\}$
such that $V_{i}\cap V_{j}=\phi$ for any $i\neq j$ and
$\bigcup\limits_{i\in[n_{G}]}V_{i}=G$, where

$V_{i}=\\{x\in G\colon\,d_{G}(x,c_{i})\leq
d_{G}(x,c_{j})\,\forall\,j\in[n_{G}],j\neq i\\}$

######  Definition VI.3 (Closed ball around a location).

For any $x\in G$ and $r\in\mathbb{R}_{\geq 0}$, the _closed ball_ of $x$ of
radius $r$ is defined as $\beta_{r}(x)=\\{y\in G\colon\,d_{G}(x,y)\leq r\\}$

######  Definition VI.4 (Fenced Voronoi decomposition).

For any $r\in\mathbb{R}_{\geq 0}$ and charging station $i$, let the _$r$
-fenced Voronoi decomposition_ on road network $G$ be defined as
$V^{-r}_{G}=\\{V_{i}^{r}\colon\,i\in[n_{G}]\\}$ such that $V^{-r}_{i}\cap
V^{-r}_{j}=\phi$ for $i\neq j$ and $V_{i}^{-r}=\\{x\in
V_{i}\colon\,B_{r}(x)\subseteq V_{i}\\}$. In other words, $V_{i}^{-r}$
essentially constructs an area contained within $V_{i}$ restricted by a
_fence_ at a distance $r$ from the edge of $V_{i}$.

######  Theorem VI.1.

Suppose an EV $u$ positioned at $x^{u}$ on $G$ obfusucates its location using
AGeoI with any radius of truncation $r\in\mathbb{R}_{\geq 0}$. Let
$\hat{x}^{u}$ be the location of the nearest available charging station to the
true location $x^{u}$. Then
$\mathbb{P}\left[\operatorname{CoP}(u,\mathcal{L}_{\epsilon,r})=0\right]=1$
for every $x^{u}\in V_{\hat{x}^{u}}^{-r}$. In other words, if an EV lies in
the $r$-fenced Voronoi decomposition for its nearest available CS, it has a
_zero cost for privacy_ w.p. 1.

###### Proof.

Immediate from Definition VI.4. ∎

######  Theorem VI.2.

Suppose an EV $u$ lies in $V_{\hat{x}^{u}}\setminus V_{\hat{x}^{u}}^{-r}$ and
it uses AGeoI to obfuscate its true location $x^{u}$ to $x^{u}_{1}$ with a
radius of truncation $r$ and privacy parameter $\epsilon$ for making a private
query to the Edge. Then
$\mathbb{P}\left[\operatorname{CoP}(u,\mathcal{L}_{\epsilon,r})=0\right]=1-\sum_{x^{u}_{1}\in
V_{\hat{x}^{u}}^{c}}ce^{-\epsilon d_{G}(x^{u},x^{u}_{1})}$, where $c$ is the
normalizing constant of the truncated Laplace mechanism as in Definition IV.2.

###### Proof.

To compute
$\mathbb{P}\left[\operatorname{CoP}(u,\mathcal{L}_{\epsilon,r})=0\right]$, we
only need to exclude the possibilities where the reported location of the EV
lies outside the Voronoi decomposition of the station $\hat{x}^{u}$, which,
essentially, is $1-\sum_{x^{u}_{1}\in V_{\hat{x}^{u}}^{c}}ce^{-\epsilon
d_{G}(x^{u},x^{u}_{1})}$. ∎

##  VII Experimental Study

A series of experiments are conducted to evaluate the proposed method for the
use case of an EV querying for a CS in Edge cloud-assisted ITS. The
experiments’ goals are to (i) validate proposed theoretical claims and
solutions empirically; (ii) use the method to find the nearest available
charging station for EVs as a case study; (iii) investigate the cost of
privacy in real-time settings; and (iv) conduct a real-time CS occupancy
prediction technique from the noisy vehicle distribution. Standard Python
packages are used to run the experiments in an environment with an Intel core
i7 processor, 16 GB of RAM, and an Ubuntu 20.04 operating system.

###  VII-A Dataset Preparation

The road network, exported from OpenStreetMap [57], is utilised in this study.
The cost of privacy is analysed by calculating the extra routing distance to
the identified optimal charging station due to additional noise in vehicular
locations in the queries. Thus, the cost of privacy depends on the sparsity of
the CSs. Two datasets with different densities are prepared to comprehend the
impact of this sparsity. The United States Department of Energy allows for the
download of up-to-date data on existing and planned alternative fuel stations,
as well as their geographical coordinates [58]. The first dataset is exported,
containing the locations of 404 existing CSs in San Francisco. For the second
dataset, we followed the assumption that CSs will be more widely spread in the
future, and parking locations are likely to deploy charging facilities. Thus,
the second dataset is prepared by merging the existing and planned charging
station locations with on-street and off-street parking locations provided by
DataSF [59]. The second dataset contains 716 independently distributed
locations.

The EPFL (Swiss Federal Institute of Technology-Lausanne) mobility dataset
contains the GPS records of the 536 taxi trajectories in San Francisco for
four weeks. The data format includes a taxi identifier, latitude, longitude,
state of the taxi (vacant or occupied), and a UNIX epoch timestamp [60]. It is
possible to split the entire taxi trajectory into realistic trajectories of
each customer because the dataset contains information on the occupancy of the
taxis. By doing so, we could export over 450 thousand trajectories. Among
those, 536 trajectories are randomly chosen from each taxi for this study.

###  VII-B Experimental Setup

In the experimental scenario, a group of vehicles sends out location queries
to find the closest available CSs during their journeys on the road network
$G$. The edges of the road network $G$ are truncated into discrete segments
with an equal $k$ travel distance, similar to the work in [41]. DTLap (e.g.,
Algorithm 1) is utilised to generate the privacy channel by using the Laplace
mechanism for the user’s desired values for privacy budget $\epsilon$ and
truncation radius $r$. Following this, DTLapSamp (e.g., Algorithm 2) is used
to generate privatised locations with respect to the users’ real locations.

A location query contains a privatised location and $m-1$ dummy locations as a
vector and is collected by the Edge for sending them to the third-party
through the core cloud as a single vector of all locations. The third-party
responds to the locations in the vector with the closest available CS for
each, and the Edge sends vehicle location vectors to the related vehicles
without being able to differentiate privatised and dummy locations.

For IBU to approximate the original distribution of the query locations of the
EVs in the road network in order to predict the availability of the CSs and,
thus, assist the users in planning their journeys appropriately, we note that
each original query location goes through two independent steps of
sanitization: a) locally using the truncated Laplace mechanism to achieve
AGeoI and b) generating the realistic dummy locations in the area of coverage
of the Edge to ensure protection against attacks reconstructing their
journeys. Setting the domain $\mathcal{X}$ as the area of coverage of the RSU
of the fixed Edge that we focus on, while the former is a straightforward use
of the channel $\mathcal{L}$, the latter can be thought of as $m-1$
independent applications of the uniform channel $\mathcal{U}$, where
$U:\mathcal{X}^{2}\mapsto\mathbb{R}$ with $\mathcal{U}_{x,y}$ denoting
$\mathbb{P}_{\mathcal{U}}[y|x]=1/|\mathcal{X}|$, by each EV. Therefore, after
accounting for the normalization, the channel incorporating the local
obfuscation and the generation of the dummy locations used by each EV reduces
down to $\frac{1}{m}\mathcal{L}+\frac{m-1}{m}\mathcal{U}$ which we use as the
privacy channel to implement IBU.

The first set of experiments examines the CoS for randomly selected 536
vehicle traces, where each trace contains a series of GPS coordinates and 3
randomly selected points along each for the real locations of the queries. The
discrete road network is generated by setting the distance $k=100$ meters. The
parameters of $\epsilon$ and $r$ are varied in the range of 0.2 to 2, and 1 to
20, respectively.

The privatised location, together with the dummy locations, is sent to the
third-party for a query to prevent the third-party from tracking the vehicle.
The area of Edge coverage, rather than the vehicle’s area of interest, is
considered for dummy location generation rather than the vehicle’s area of
interest, as the centre of mass may give away the true location. The second
set of experiments examined the impact of dummy locations on the CoS.

The location queries could be used for real-time predictive analysis on the
optimisation of the smart power grid, managing staff, and determining where
new CSs should be deployed. Thus, service providers can have the utility of
the datasets (e.g., train ML models, etc.) with DP-based methods while the
privacy of individuals is preserved. The third set of experiments utilises the
IBU method to retrieve the true distribution of locations queries from the
noisy distribution, which includes privatised and dummy locations.

Figure 5: CoS for varying $\epsilon$ or $r$ of AGeoI ($1st$ row is for sparse
CSs, $2nd$ row is for dense CSs) Figure 6: Fraction of zero CoS for varying
$\epsilon$ or $r$ of AGeoI ($1st$ row is for sparse CSs, $2nd$ row is for
dense CSs) Figure 7: Impact of introducing dummy locations along with AGeoI on
the CoS Figure 8: The distance between the original and estimated
distributions using IBU for $\epsilon=0.6$ and $\epsilon=2$ noisy
distributions by the earth mover’s distance (i.e. Kantorovich-Wasserstein
distance) Figure 9: Estimations of the original distribution using IBU for the
$\epsilon=0.6$ and $\epsilon=2$ noisy distributions.

###  VII-C Results and Discussion

####  VII-C1 Cost of Privacy Analysis

DP approaches introduce a trade-off between privacy and data utility, with a
higher level of privacy requiring a greater level of noise. The efficacy of
the respective service may correspondingly decrease due to the fall in data
utility, and it is considered the ‘cost of privacy’ (CoS) in this study.
However, there is a finite number of cases with maximum efficacy for many
applications. Thus, there must be a sweet spot of privacy for free where the
user will receive the maximum efficacy with some level of privacy. It is also
valid for our use case, in which a vehicle must be able to utilise a finite
number of unique CSs.

The following results are achieved by carrying out the experiments for $3$
linked queries of $536$ randomly selected vehicle trajectories for varying
values of $\epsilon$ or $r$ ranging from $0.2$ to $2$, and $1$ to $20$,
respectively. Figure 5 demonstrates the CoS in terms of the extra travelling
distance due to the privacy-preserving mechanism, where a similar pattern is
observed for both of the datasets. Another observation is that a high
frequency of queries resulted in no cost for privacy preservation. Figure 6
shows the fraction of the queries with “privacy for free” where both the
datasets followed similar patterns. Vehicle queries contain dummy locations
and their privatised true locations. It is possible that the dummy locations
can sometimes provide a better utility, but our experiments consider the
utility of a privatised location as the worst-case for analysis.

Figure 5 shows that our method provides a negligible cost of utility-loss for
the formal privacy-gain enjoyed by the EVs. By increasing the truncation
radius, an abrupt drop in the distance between the location of the nearest
available charging station for the true location of the query and that of the
privatised one, implies that the cost of the extra travel distance needed to
be taken due to the AGeoI guarantee is almost negligible. A similar trend is
seen for the varying $\epsilon$ with a fixed radius. As the level of privacy
decreases, the fraction of EVs in the network enjoying _privacy for free_
grows to be more than $60\%$ for a radius of truncation of merely 10 road
segments, where each segment is 100 meters long, for $\epsilon\geq 0.5$.
However, more than $90\%$ of the EVs achieve a zero cost of privacy for
$\epsilon\geq 1.5$, irrespective of the truncation radius as illustrated in
Figure 6. Due to increasing perturbation in disclosed location, the width of
the confidence interval for zero cost of privacy increases, as seen in Figure
6. The likelihood of achieving zero cost of privacy fluctuates over a wider
range and it does not monotonically decrease with the growing radius due to
rising randomness.

####  VII-C2 Impact of Dummy Data Generation

Considering an adversary interested in finding the true locations of the EVs,
$(\alpha,\beta]$_-identifiability_ is defined for any location $x$ as
$\mathbb{P}[d(y,x)<\alpha)>\beta$, where $y$ is any guessed location by the
adversary. With proposed method, with a sufficiently small radius of
truncation to obfuscate the true location using the truncated Laplace and
generating $m-1$ dummy locations in the area of coverage of the Edge, the
probability of hitting the true $x$ within an error of $\alpha$ is
$\mathbb{P}[d(x,y)<\alpha]=\frac{1}{m}ce^{-\epsilon\alpha}=\beta$, where $c$
is the normalising constant.

There has been some work in this area from the perspective of just GeoI [41,
40, 39, 61, 62] or just from the standpoint of generating dummy locations
exploiting anonymisation techniques [63, 64]. One of the first major concerns
in using only GeoI is when we allow dynamic and multiple queries along the
journey of the EVs, as individual locations, despite being privatised, can
still be interpolated to approximate the entire trace. If only dummy locations
are used, however, any estimated (or observed) $y$ could be the real location
w.p. $\frac{1}{m-1}$, as there is no formal privacy guaranteed, i.e., every
location $x$ has, is $(0,1/m-1)$-identifiable among $(m-1)$ dummy locations.
With potential parallel processing, brute-force attacks are just one way that
it has been shown that anonymisation techniques are not sufficient to protect
privacy [65].

Figure 7 illustrates how the CoP increases with an increase in the noise due
to lack of dummy locations under the same level of identifiability. To achieve
the same $(\alpha,\beta)$-identifiability with just AGeoI without dummy
locations, the parameter $\epsilon$ needs to be scaled by $\frac{1}{\ln{m}}$,
i.e., more noise needs to be added, which results in having a worse trade-off
between privacy and CoP for the same level of privacy.

####  VII-C3 Real-time Predictive Study

Predicting the availability of CSs is a crucial component of EV trip planning
and can help ease range anxiety. SoA methods utilised machine learning-based
approach to develop such prediction models [66, 67, 68, 69, 70].The main
consideration of these models is that drivers can book timeslots for CSs and
the prediction is made based on factors such as past usage of CCs, traffic
density, and some other features such as weather conditions. However, such
consideration may be limited to facilitating effective EV journey planning,
given that traffic is highly dynamic and subject to unexpected changes. Due to
the traffic, EVs may be late for their scheduled charging time, and another EV
cannot be navigated to charge from the same station, despite the fact that it
is empty. Hence, a real-time predictive analysis would be critical to
determine the likelihood of a CS being available when an EV arrives. Our
proposed method provides privacy-preserved live traffic distribution of the
querying vehicles. IBU method [46, 45] is utilised to demonstrate the
statistical distance between the predicted and the original traffic
distribution for our results with $\epsilon=0.6$ and $\epsilon=2$, see Figure
8 for IBU with 100 iterations where the distance is decreasing by iterations
of IBU. Although such a statistical distance, it is more important to predict
the heavy hitters, which helps the prediction of how likely a CS will be
available when the vehicle arrives, see Figure 9 for the heatmaps of original,
noisy, and predicted traffic distributions.

##  VIII Conclusion

This paper studied a fundamental problem of the risk of privacy violation for
EVs dynamically querying for charging stations along their journeys. The
setting of the problem has not been addressed in the literature, and some of
the related techniques along the lines of privacy-preserving vehicle routing
cannot be adapted directly into the practical model considered in this paper.

To resolve this, we theorised the notion of AGeoI and justified its
mathematical soundness and applicability by proving the compositionality
theorem, which is a novelty in itself and allows us to attain GeoI in a
strictly bounded space of noisy data. We derived the appropriate privacy
parameters to prove that the truncated Laplace mechanism satisfies AGeoI and
used it to propose a location privacy-preserving method for EVs querying for
CSs. Our method protects privacy in two ways: at the specific positions of the
queries and along the entire journey.

In experimental studies, datasets with real vehicle traces and locations were
used to demonstrate the trade-off between privacy and utility and the impact
of dummy locations on this trade-off. We used IBU for real-time prediction of
the original distribution of the EVs from the reported (noisy) locations. The
proposed method is distinct from current machine learning-based approaches in
that it considers real-time changes in the number of location-based queries.
Thus, it can reflect unprecedented traffic variations at the CSs occupancy
rate. By using IBU, the method is capable of predicting the likelihood of a
particular station being occupied by another vehicle at the time of arrival
and, hence, enables an online prediction technique to estimate the
availability of CSs around an EV, allowing the users to do convenient route-
planning. A consistent trend of a substantial majority of the EVs to have
privacy for free was observed across all the experiments, i.e., most of the
EVs suffer no loss of utility even for fairly high-level formal AGeoI. In
general, we observe that the cost of privacy induced by our method is fairly
low across settings, thus, ensuring formal privacy protection for the location
of the EVs without incurring a high price for that as far as the journey is
concerned. We dissected this cost of privacy under our method using Voronoi
decomposition to draw insight into the workings of our method.

## Acknowledgment

The authors would like to thank Professor Graham Cormode for the insightful
discussions that supported the development of this study. Ugur Ilker Atmaca
and Sayan Biswas are shared co-first authors who have worked together on this
paper and contributed equally. The authors would also like to extend their
sincere thanks to the European Research Council (ERC) Advanced Grant of
Catuscia Palamidessi which supported Sayan Biswas’ research visit at WMG, the
University of Warwick, which enabled this successful collaboration.

## References

  * [1] E. Ferrero, S. Alessandrini, and A. Balanzino, “Impact of the electric vehicles on the air pollution from a highway,” _Applied Energy_ , vol. 169, pp. 450–459, 2016.
  * [2] K. Hampshire, R. German, A. Pridmore, and J. Fons, “Electric vehicles from life cycle and circular economy perspectives,” _Version_ , vol. 2, p. 25, 2018.
  * [3] R. Zhang and S. Fujimori, “The role of transport electrification in global climate change mitigation scenarios,” _Environmental Research Letters_ , vol. 15, no. 3, p. 034019, Feb 2020.
  * [4] R. Hickman and D. Banister, “Looking over the horizon: Transport and reduced co2 emissions in the uk by 2030,” _Transport Policy_ , vol. 14, no. 5, pp. 377–387, 2007.
  * [5] S. Kufeoglu and D. K. K. Hong, “Emissions performance of electric vehicles: A case study from the united kingdom,” _Applied Energy_ , vol. 260, p. 114241, 2020.
  * [6] E. P. Seymour Millen, “Transport and environment statistics 2021 annual report,” May 2021. [Online]. Available: https://assets.publishing.service.gov.uk/government/uploads/system/uploads/attachment_data/file/984685/transport-and-environment-statistics-2021.pdf
  * [7] T. Gersdorf, P. Hertzke, P. Schaufuss, and S. Schenk, “Mckinsey electric vehicle index: Europe cushions a global plunge in ev sales,” 2020.
  * [8] R. Hensley, S. Knupfer, and D. Pinner, “Electrifying cars: How three industries will evolve,” _McKinsey Quarterly_ , vol. 3, no. 2009, pp. 87–96, 2009.
  * [9] P. Gao, R. Hensley, and A. Zielke, “A road map to the future for the auto industry,” _McKinsey Quarterly, Oct_ , pp. 1–11, 2014.
  * [10] M. Lombardi, K. Panerali, S. Rousselet, and J. Scalise, “Electric vehicles for smarter cities: the future of energy and mobility,” in _World Economic Forum. http://www3. weforum. org/docs/WEF_2018_% 20Electric_For_Smarter_Cities. pdf_ , 2018.
  * [11] A. Ostermann, Y. Fabel, K. Ouan, and H. Koo, “Forecasting charging point occupancy using supervised learning algorithms,” _Energies_ , vol. 15, no. 9, p. 3409, May 2022.
  * [12] A. Sao, N. Tempelmeier, and E. Demidova, “Deep information fusion for electric vehicle charging station occupancy forecasting,” in _2021 IEEE International Intelligent Transportation Systems Conference (ITSC)_ , 2021, pp. 3328–3333.
  * [13] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of Cryptography_ , S. Halevi and T. Rabin, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 265–284.
  * [14] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” in _Advances in Cryptology - EUROCRYPT 2006_ , S. Vaudenay, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 486–503.
  * [15] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , 2013, pp. 429–438.
  * [16] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: Differential privacy for location-based systems,” in _Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security_, 2013, pp. 901–914.
  * [17] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Optimal geo-indistinguishable mechanisms for location privacy,” in _Proceedings of the 21th ACM Conference on Computer and Communications Security (CCS 2014)_ , 2014.
  * [18] N. Fernandes, A. McIver, and C. Morgan, “The laplace mechanism has optimal utility for differential privacy over continuous queries,” in _36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021._ IEEE, 2021, pp. 1–12.
  * [19] L. Gillam, K. Katsaros, M. Dianati, and A. Mouzakitis, “Exploring edges for connected and autonomous driving,” in _IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2018, pp. 148–153.
  * [20] C. Maple, M. Bradbury, A. T. Le, and K. Ghirardello, “A connected and autonomous vehicle reference architecture for attack surface analysis,” _Applied Sciences_ , vol. 9, no. 23, p. 5101, 2019.
  * [21] D. Hahn, A. Munir, and V. Behzadan, “Security and privacy issues in intelligent transportation systems: Classification and challenges,” _IEEE Intelligent Transportation Systems Magazine_ , vol. 13, no. 1, pp. 181–196, 2019.
  * [22] X. Lin and X. Li, “Achieving efficient cooperative message authentication in vehicular ad hoc networks,” _IEEE Transactions on Vehicular Technology_ , vol. 62, no. 7, pp. 3339–3348, 2013.
  * [23] N. Kumar, R. Iqbal, S. Misra, and J. J. Rodrigues, “An intelligent approach for building a secure decentralized public key infrastructure in vanet,” _Journal of Computer and System Sciences_ , vol. 81, no. 6, pp. 1042–1058, 2015.
  * [24] P. Zhao, G. Zhang, S. Wan, G. Liu, and T. Umer, “A survey of local differential privacy for securing internet of vehicles,” _The Journal of Supercomputing_ , vol. 76, no. 11, pp. 8391–8412, 2020.
  * [25] T. Franke and J. F. Krems, “Understanding charging behaviour of electric vehicle users,” _Transportation Research Part F: Traffic Psychology and Behaviour_ , vol. 21, pp. 75–89, 2013.
  * [26] R. R. Kumar and K. Alok, “Adoption of electric vehicle: A literature review and prospects for sustainability,” _Journal of Cleaner Production_ , vol. 253, p. 119911, 2020.
  * [27] Z. Tian, T. Jung, Y. Wang, F. Zhang, L. Tu, C. Xu, C. Tian, and X.-Y. Li, “Real-time charging station recommendation system for electric-vehicle taxis,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 17, no. 11, pp. 3098–3109, 2016.
  * [28] W. Zhang, H. Liu, F. Wang, T. Xu, H. Xin, D. Dou, and H. Xiong, “Intelligent electric vehicle charging recommendation based on multi-agent reinforcement learning,” in _Proceedings of the Web Conference 2021_ , 2021, pp. 1856–1867.
  * [29] R. Flocea, A. Hîncu, A. Robu, S. Senocico, A. Traciu, B. M. Remus, M. S. Răboacă, and C. Filote, “Electric vehicle smart charging reservation algorithm,” _Sensors_ , vol. 22, no. 8, p. 2834, 2022.
  * [30] G. Wang, W. Li, J. Zhang, Y. Ge, Z. Fu, F. Zhang, Y. Wang, and D. Zhang, “sharedcharging: Data-driven shared charging for large-scale heterogeneous electric vehicle fleets,” _Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies_ , vol. 3, no. 3, pp. 1–25, 2019\.
  * [31] “Privacy policy.” [Online]. Available: https://company.plugshare.com/privacy.html
  * [32] “Chargepoint privacy and cookie policy for europe.” [Online]. Available: https://eu.chargepoint.com/privacy_policy
  * [33] C.-Y. Chow, M. F. Mokbel, and W. G. Aref, “Casper* query processing for location services without compromising privacy,” _ACM Transactions on Database Systems (TODS)_ , vol. 34, no. 4, pp. 1–48, 2009.
  * [34] B. Niu, Q. Li, X. Zhu, G. Cao, and H. Li, “Achieving k-anonymity in privacy-aware location-based services,” in _IEEE INFOCOM 2014-IEEE Conference on Computer Communications_. IEEE, 2014, pp. 754–762.
  * [35] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Found. Trends Theor. Comput. Sci._ , vol. 9, no. 3–4, p. 211–407, aug 2014.
  * [36] N. Guo, L. Ma, and T. Gao, “Independent mix zone for location privacy in vehicular networks,” _IEEE Access_ , vol. 6, pp. 16 842–16 850, 2018.
  * [37] S. Amini, J. Lindqvist, J. I. Hong, M. Mou, R. Raheja, J. Lin, N. Sadeh, and E. Tochb, “Caché: Caching location-enhanced content to improve user privacy,” _SIGMOBILE Mob. Comput. Commun. Rev._ , vol. 14, no. 3, p. 19–21, dec 2011.
  * [38] P. Asuquo, H. Cruickshank, J. Morley, C. P. A. Ogah, A. Lei, W. Hathal, S. Bao, and Z. Sun, “Security and privacy in location-based services for vehicular and mobile communications: An overview, challenges, and countermeasures,” _IEEE Internet of Things Journal_ , vol. 5, no. 6, pp. 4778–4802, 2018.
  * [39] L. Zhou, L. Yu, S. Du, H. Zhu, and C. Chen, “Achieving differentially private location privacy in edge-assistant connected vehicles,” _IEEE Internet of Things Journal_ , vol. 6, no. 3, pp. 4472–4481, 2018.
  * [40] L. Luo, Z. Han, C. Xu, and G. Zhao, “A geo-indistinguishable location privacy preservation scheme for location-based services in vehicular networks,” in _International Conference on Algorithms and Architectures for Parallel Processing_. Springer, 2019, pp. 610–623.
  * [41] C. Qiu, A. C. Squicciarini, C. Pang, N. Wang, and B. Wu, “Location privacy protection in vehicle-based spatial crowdsourcing via geo-indistinguishability,” _IEEE Transactions on Mobile Computing_ , pp. 1–1, 2020.
  * [42] T. Cunningham, G. Cormode, H. Ferhatosmanoglu, and D. Srivastava, “Real-world trajectory sharing with local differential privacy,” _Proc. VLDB Endow._ , vol. 14, no. 11, p. 2283–2295, jul 2021.
  * [43] D. Agrawal and C. C. Aggarwal, “On the design and quantification of privacy preserving data mining algorithms,” in _Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems_ , ser. PODS ’01. New York, NY, USA: Association for Computing Machinery, 2001, p. 247–255.
  * [44] R. Agrawal, R. Srikant, and D. Thomas, “Privacy preserving olap,” in _Proceedings of the 2005 ACM SIGMOD international conference on Management of data_ , 2005, pp. 251–262.
  * [45] E. ElSalamouny and C. Palamidessi, “Full convergence of the iterative bayesian update and applications to mechanisms for privacy protection,” _CoRR_ , vol. abs/1909.02961, 2019. [Online]. Available: http://arxiv.org/abs/1909.02961
  * [46] ——, “Generalized iterative bayesian update and applications to mechanisms for privacy protection,” in _2020 IEEE European Symposium on Security and Privacy (EuroS &P)_. IEEE, 2020, pp. 490–507.
  * [47] K. Chatzikokolakis, E. ElSalamouny, and C. Palamidessi, “Efficient utility improvement for location privacy,” _Proceedings on Privacy Enhancing Technologies_ , vol. 2017, no. 4, pp. 308–328, 2017.
  * [48] A. Ghosh, T. Roughgarden, and M. Sundararajan, “Universally utility-maximizing privacy mechanisms,” 2009.
  * [49] E. Bulut and M. C. Kisacikoglu, “Mitigating range anxiety via vehicle-to-vehicle social charging system,” in _2017 IEEE 85th Vehicular Technology Conference (VTC Spring)_. IEEE, 2017, pp. 1–5.
  * [50] W. Duan, J. Gu, M. Wen, G. Zhang, Y. Ji, and S. Mumtaz, “Emerging technologies for 5g-iov networks: Applications, trends and opportunities,” _IEEE Network_ , vol. 34, no. 5, pp. 283–289, 2020.
  * [51] H. Ji, O. Alfarraj, and A. Tolba, “Artificial intelligence-empowered edge of vehicles: Architecture, enabling technologies, and applications,” _IEEE Access_ , vol. 8, pp. 61 020–61 034, 2020.
  * [52] H. Patil and V. N. Kalkhambkar, “Grid integration of electric vehicles for economic benefits: A review,” _Journal of Modern Power Systems and Clean Energy_ , vol. 9, no. 1, pp. 13–26, 2020.
  * [53] “Charging station map for electric cars.” [Online]. Available: https://chargemap.com/map
  * [54] L. Gillam, K. Katsaros, M. Dianati, and A. Mouzakitis, “Exploring edges for connected and autonomous driving,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 148–153.
  * [55] H. Seo, K.-D. Lee, S. Yasukawa, Y. Peng, and P. Sartori, “Lte evolution for vehicle-to-everything services,” _IEEE communications magazine_ , vol. 54, no. 6, pp. 22–28, 2016.
  * [56] A. Paverd, A. Martin, and I. Brown, “Modelling and automatically analysing privacy properties for honest-but-curious adversaries,” _Tech. Rep_ , 2014\.
  * [57] OpenStreetMap contributors, “Planet dump retrieved from https://planet.osm.org ,” https://www.openstreetmap.org, 2022.
  * [58] “Alternative fuels data center: Data downloads.” [Online]. Available: https://afdc.energy.gov/data_download/
  * [59] “Datasf.” [Online]. Available: https://data.sfgov.org/browse?Department-Metrics_Publishing-Department=Municipal+Transportation+Agency+
  * [60] M. Piorkowski, N. Sarafijanovic-Djukic, and M. Grossglauser, “Crawdad data set epfl/mobility (v. 2009-02-24),” 2009.
  * [61] X. Li, Y. Ren, L. T. Yang, N. Zhang, B. Luo, J. Weng, and X. Liu, “Perturbation-hidden: Enhancement of vehicular privacy for location-based services in internet of vehicles,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 3, pp. 2073–2086, 2021.
  * [62] L. Zhang, X. Meng, K.-K. R. Choo, Y. Zhang, and F. Dai, “Privacy-preserving cloud establishment and data dissemination scheme for vehicular cloud,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 17, no. 3, pp. 634–647, 2018.
  * [63] J. Freudiger, M. Raya, M. Félegyházi, P. Papadimitratos, and J.-P. Hubaux, “Mix-zones for location privacy in vehicular networks,” in _ACM Workshop on Wireless Networking for Intelligent Transportation Systems (WiN-ITS)_ , no. CONF, 2007.
  * [64] H. Jiang, J. Li, P. Zhao, F. Zeng, Z. Xiao, and A. Iyengar, “Location privacy-preserving mechanisms in location-based services: A comprehensive survey,” _ACM Comput. Surv._ , vol. 54, no. 1, jan 2021.
  * [65] H. Zang and J. Bolot, “Anonymization of location data does not work: A large-scale measurement study,” in _Proceedings of the 17th annual international conference on Mobile computing and networking_ , 2011, pp. 145–156.
  * [66] C. Hecht, J. Figgener, and D. U. Sauer, “Predicting electric vehicle charging station availability using ensemble machine learning,” _Energies_ , vol. 14, no. 23, p. 7834, 2021.
  * [67] A. Nait-Sidi-Moh, A. Ruzmetov, M. Bakhouya, Y. Naitmalek, and J. Gaber, “A prediction model of electric vehicle charging requests,” _Procedia Computer Science_ , vol. 141, pp. 127–134, 2018.
  * [68] T.-Y. Ma and S. Faye, “Multistep electric vehicle charging station occupancy prediction using hybrid lstm neural networks,” _Energy_ , vol. 244, p. 123217, 2022.
  * [69] A. Almaghrebi, F. Aljuheshi, M. Rafaie, K. James, and M. Alahmad, “Data-driven charging demand prediction at public charging stations using supervised machine learning regression methods,” _Energies_ , vol. 13, no. 16, p. 4231, 2020.
  * [70] R. Luo, Y. Zhang, Y. Zhou, H. Chen, L. Yang, J. Yang, and R. Su, “Deep learning approach for long-term prediction of electric vehicle (ev) charging station availability,” in _2021 IEEE International Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2021, pp. 3334–3339.