A Voronoi-Based Location Privacy-Preserving Method for Continuous Query in LBS

Abstract

Most of the mobile phones have GPS sensors which make location based service (LBS) applicable. LBS brings not only convenience but also location privacy leak to us. Achieving anonymity and sending private queries are two main privacy-preserving courses in LBS. A novel location privacy-preserving method is proposed based on Voronoi graph partition on road networks. Firstly, based on the prediction of a user's moving direction, a cooperative k-anonymity method is proposed without constructing cloaking regions which may lead to efficiency decline in continuous query. And then, a query algorithm is proposed without providing any user's actual location, replaced by continuous anchor sequence, to LBS provider. This algorithm can work out precise results according to candidate sets returned by LBS provider and it also solves uneven distribution problem in SpaceTwist. Performance analysis and experiments show that our method achieves a preferable tradeoff between QoS and location privacy preserving; it has obvious advantages compared with other methods.

1. Introduction

Nowadays, GPS sensors are available on many smart phones, which can report accurate location of a user, and location based service (LBS) has been widely used. Query service for places of interests (PoIs) based on a user's location is one of the most frequently used service types in LBS, such as nearest neighbor queries and range queries. Typical query is “get K nearest restaurants around me” and “get all restaurants within the scope of R kilometers,” respectively. And a user may send a snapshot or a continuous query request [1] according to his current moving condition. For all these query methods ask a user to provide his actual locations before getting query service. But it leads to a deep-going privacy exposure as the location data is leaked due to the correlation between location information and user's identity, hobbies, home address, and other privacy data. The location privacy must be protected effectively in the process of LBS.

There are 3 kinds of privacy in LBS, location privacy, query privacy [2–5], and identity privacy [6]; we focus on location privacy preserving. How to cloak a user's location has been widely studied [7–13] and most of them choose a central server to achieve k-anonymity for users. The architecture of location privacy preserving in LBS is central or centerless. In Figure 1, the centerless architecture has two kinds of entities: users and LBS providers (LSP), but in this architecture privacy-preserving burden is heavy at the user end. The central architecture is added with a central server (CS) providing stronger privacy-preserving methods. Location k-anonymity normally adopts the latter architecture to construct cloaking regions at CS end, as shown in Figures 1 and 2, a user sends his actual location to a CS, and the anonymity module of CS obscures the location before sending the query to LSP; the untrusted LSP cannot get any user's precise location. But constructing cloaking regions for each user causes lots of burden and low success rate of anonymity when CS confronts with a large number of anonymity requests.

Figure 1

A central/centerless architecture.

Figure 2

Continuous cloaking regions.

In view of that defect, Chow et al. [14] have proposed P2P cooperative anonymity method without CS. In that method, the head node which comes from users organizes other users to form an anonymity group without constructing any cloaking region. It is a simple structure but too much burden for a user to be a head node, and the users’ credibility is hard to guarantee.

However, using snapshot cloaking region is not security in continuous query because adversaries are supposed to get the distribution of users and cloaking regions all the time, so when a user constructs continuous cloaking regions for a user, as shown by the solid line rectangles in Figures 2(a)–2(c), the intersection A of three regions is the actual user using anonymity service. To solve this problem, researchers have proposed lots of methods for continuous query [15–24], such as constructing continuous minimum cloaking regions [15–17], as shown by the dash line rectangles in Figure 2.

But constructing continuous regions needs to find neighbor users who have similar moving trend and makes sure most of them will not depart from the cloaking regions. That increases the difficulty of constructing and has a side effect which restricts the users in a small specified region. Query with these regions requires processing function of imprecise coordinates at server end, too. Moreover, most of these methods are based on Euclidean space, not based on the actual road networks.

There are other protecting methods, such as dummies [25, 26], using pseudo locations instead of actual location. These methods have the defects of imprecise query results or too much overhead. Lung Yiu et al. [27] have proposed SpaceTwist which gets candidate sets of PoIs from LSP. SpaceTwist achieves comparatively accurate query result. Gong et al. [28] and Huang et al. [29] have, respectively, improved SpaceTwist. We also consult SpaceTwist to make it applicable for continuous query with an anchor sequence. The main contributions and innovations of this paper are as follows.

• (1)

  Considering the defects of constructing continuous cloaking regions, we propose a location privacy-preserving method without any cloaking region. We use Voronoi graph partition for the first time to divide road networks into cells, which facilitates the prediction of a user's moving direction, and a user's registration algorithm to CS is proposed with the help of Voronoi partition. When a mobile user registers to a CS, he has a high accuracy to an appropriate one. After registration, a cooperative anonymity algorithm at CS end is proposed. This algorithm satisfies each user's k-anonymity degree.

• (2)

  We propose an accurate query algorithm, which is called Singoes running on CS, without providing any user's actual location to LSP. Singoes takes fixed anchors between two cells to replace the user's actual locations in continuous query and get precise query results using anchors. According to the returned candidate PoIs from LSP, Singoes deduces precise results by expanding demand space again. This algorithm also solves the problem of PoIs uneven distribution in SpaceTwist. As we know, we have found the problem for the first time.

2. Related Work

In order to provide strong location privacy preservation at the data generated end, Gruteser and Grunwald [7] have proposed k-anonymity to obscure a user's actual location. After that lots of location privacy-preserving works have been presented [8–14, 24], Chow et al. [10] and Li and Zhu [13] have proposed partition method for cloaking region, and Xue et al. [2] have proposed cloaking region constructing method in road networks, which is appropriate for practical situation. Chow et al. [14] have proposed a P2P cloaking algorithm without a CS. We take these ideas as a reference in this paper.

The above researches were proposed in a static situation; Dewri et al. [17] make a formal analysis on the privacy leaking problems in continuous LBS, which points out that the static protecting method is not appropriate for mobile situation. Now most works are caring about dynamic privacy preserving. Pan et al. [15] take users’ moving speed and direction as affecting factors and a distortion function is defined to measure the temporal query distortion of a cluster in continuous queries, and they also have proposed a method which maintains maximal cliques to deal with location-dependent attacks [16]. Lee et al. [18] have proposed a grid-based cloaking region creation scheme for continuous LBS, and Wang et al. [19] consider the similarity of velocity and acceleration as factors to construct cloaking regions. Pingley et al. [23] use dummies to protect privacy in continuous query; this method does not need a trust third party. Hashem et al. [20] have presented a mobile K nearest neighbor query against overlapping rectangle attack in continuous query. In road networks, Palanisamy et al. [21] and Yang et al. [24] have proposed location protecting methods in continuous query, which have more practical significance.

In the aspect of using dummies to achieve privacy preserving, Hong and Landay [25] use a significant object to replace a user's location, but the query result is not accurate enough. Reference [26] sends several dummies accompanied with actual location to LSP to get query results, which brings extra burden to LSP. Based on these researches, Lung Yiu et al. [27] have proposed SpaceTwist running on user side, LSP performs INN (Incremental Nearest Neighbor) searching process for PoIs and returns the candidate sets to the user, and the user works out the accurate results himself. But SpaceTwist has not achieved k-anonymity, so Gong et al. [28] and Huang et al. [29] have proposed improved methods. And there is still an issue in SpaceTwist which can be improved.

As shown in Figure 3, we cite the figure of SpaceTwist to specify the issue that can be improved. There are 3 courses in SpaceTwist, a user staying at q takes $q^{\prime }$ as an anchor, then the user sends an INN query request with anchor $q^{\prime }$ to LSP, as the second PoI ${\mathcal{P}}_2$ is found, supply space which is the dark grey circle with a radius τ expands, and demand space which is the light grey circle with a radius γ shrinks, the query procedure will not terminate until supply space covers demand space, and the user at q gets K PoIs.

Figure 3

Query processing instance [27].

The above process has a problem called PoIs uneven distribution. After ${\mathcal{P}}_3$ is found, if a ${\mathcal{P}}_x$ exists, which is closer to $q^{\prime }$ than ${\mathcal{P}}_4$ , as shown in Figure 4(a), the query algorithm will terminate immediately since the demand space shrinks and it is covered by supply space; the other PoIs will not be found anymore. That is caused by the appearance of a PoI ${\mathcal{P}}_x$ which is near to q in the opposite direction of $q^{\prime }$ . The demand space will shrink quickly and is covered by expanded supply space. Moreover, all the found PoIs are distributed around the anchor $q^{\prime }$ and not around the user at q; as shown in Figure 4(b), no PoIs in bottom left of the dash line have been found. All the found PoIs are above the dash line around anchor $q^{\prime }$ ; the user does not get his K nearest neighbor PoIs. We call this case PoIs uneven distribution problem. We will solve this problem and guarantee that the found PoIs are distributed around the user rather than the anchor, which is more precise. SpaceTwist is proposed for snapshot query; it is not related to continuous query. In this paper, we will make it appropriate to get continuous query results.

Figure 4

Uneven distribution problem.

3. Relevant Knowledge

In this section, we will introduce system structure, cooperative k-anonymity, and road network partition based on Voronoi graph.

3.1. System Structure

The structure of privacy-preserving method contains three parts: as shown in Figure 5, a mobile user is denoted as $u_k$ . Each user is equipped with an intelligence terminal which contains a GPS sensor and velocity and direction sensors. CS contains three modules; the anonymity module deals with user's registration, makes moving direction prediction for a user, and forms cooperative k-anonymity groups; the communication module broadcasts the current users’ registration situation of its cell periodically and communicates with users. After constructing an anonymous group, query processing module sends query requests with anchors to LSP; this module refines PoIs candidate sets and deduces KNN PoIs a user requires. CS is credible, and LSP and users are not.

Figure 5

System structure.

There are also adversaries who aim to find a user's actual location and a correlation between a user identifier and a query request. We suppose that an adversary has three abilities: $(1)$ obtaining the distribution of mobile users without their identities; $(2)$ obtaining cloaking regions; $(3)$ correlation analysis ability and some background knowledge.

3.2. The Concept of Cooperative Anonymity

Anonymity method can be divided into single anonymity and cooperative anonymity; for example, constructing cloaking regions for each user is single anonymity, and cooperative anonymity is different users sharing one cloaking region. The sharing idea decreases CS's burden. In this paper, we do not construct cloaking regions but organize users to form a cooperative anonymous group just like a P2P anonymous group [14, 29]. But the P2P cooperative method has to select a user as a cluster head, which is not suitable for energy constrained mobile users. So we modify this method and add powerful CS to organize users in its cell to achieve cooperative k-anonymity. Cooperative k-anonymity in this paper should meet the following two criterions.

• (1)

  Each user belongs to a sole cooperative group.

• (2)

  A cooperative k-anonymity group meets any user's k-anonymity degree.

3.3. Road Network Division Based on Voronoi Graph Partition

Voronoi graph [30] is a geometry of flat space; as shown in Figure 6, it is a way of dividing space into a number of regions. A set of spots is specified beforehand and for each spot there will be a corresponding region consisting of all points closer to that spot than to any other. One way is connecting all CSs around CS₁ with dash line segments and doing perpendicular bisectors to all these line segments. The polygon with connected bisectors is a Voronoi cell.

Figure 6

Voronoi graph partition.

Similarly, we choose places to deploy central servers (CSs); the deployment follows 3 criterions.

• (1)

  A CS is deployed in crowded and traffic convenient places, which insures a lot of users in its cell avoiding constrained space identity attack. Users help CS to transmit messages.

• (2)

  The distance between neighbor CSs meets ${\varsigma }_a<\mathrm{dist}(\text{C}{\text{S}}_i,\text{C}{\text{S}}_k)<{\varsigma }_b$ , ${\varsigma }_a$ and ${\varsigma }_b$ are thresholds, which insure the area of a cell is reasonable.

• (3)

  The connected paths of neighbor cells are not less than a threshold ${\varsigma }_l$ , as shown in Figure 8, which insures a user is not specified in a sole road when he is moving from one cell to another.

After a certain density deployment of CSs, we divide the entire area Ω using Voronoi graph partition into many cells centered with different CSs. Each cell is used to achieve cooperative anonymity. The Voronoi graph partition is defined as follows.

Definition 1 (Voronoi graph partition).

The spots of $\left\{\text{C}{\text{S}}_{\mathrm{1}},\text{C}{\text{S}}_{\mathrm{2}},\dots ,\text{C}{\text{S}}_n\right\}$ are distributed in a 2-dimension space Ω, for any $V\left(\text{C}{\text{S}}_i\right)$ meeting $V(\text{C}{\text{S}}_i)=\{A\mid \mathrm{dist}(A,\text{C}{\text{S}}_i)\le d(A,\text{C}{\text{S}}_k)$ , $A\in \Omega$ , $i\ne k\}$ , where $\mathrm{dist}(A,B)$ is the Euclidean distance between A and B, and all the $V\left(\text{C}{\text{S}}_i\right)$ forms a Voronoi graph, and the subregion $V\left(\text{C}{\text{S}}_i\right)$ is a cell.

The whole city area can be denoted as $V(\Omega )=\{V(\text{C}{\text{S}}_{\mathrm{1}}),V(\text{C}{\text{S}}_{\mathrm{2}}),\dots ,V(\text{C}{\text{S}}_n)\}$ . Obviously, neighbor cells have no overlap area and each user belongs to a sole cell. All the users in the same cell can form different cooperative k-anonymity groups.

4. Cooperative Anonymity and Continuous Query with Anchors

There are 3 phases in our method: initialization phase, cooperative k-anonymity phase, and continuous query PoIs with anchors phase. After initialization phase, a user registers to a CS and sends his request of joining in a cooperative anonymous group, CS organizes k users to form a cooperative k-anonymity group according to their moving trends and sends k queries to LSP, a user's identity is removed, and his actual location is replaced by continuous anchors in the query procedure. After registration, a user should report his latest locations to a CS periodically to achieve continuous query until he gets in a new cell or finished a query. In query phase, the CS takes its own location and a neighbor CS location which the user is heading to as two elementary anchors and chooses other continuous anchors in the line segment between them. Then CS sends each snapshot query of continuous query request with an anchor which the user has not passed yet. In a snapshot query, CS performs algorithm Singoes to compute results for a user according to candidate sets returned from LSP.

4.1. Initialization Phase

A Trust Authority (TA) picks appropriate CSs’ deploying locations according to the 3 criterions and generates Voronoi graph partition cells. Then TA sends road segments and neighbor CSs situation of each cell to the corresponding CS; the details will be discussed in Section 4.2. Any CS can verify validity of a user's pseudonym [31].

A $\text{C}{\text{S}}_i\in \text{CS}$ initializes a registering table according to registered time sequence of each user $\text{Tabl}{\text{e}}_R=(\text{UID},\mathrm{loc},\text{dest},t_r,\stackrel{⃑}{V},\text{Con},k,P\text{set},n_i)$ , where $\text{UID}$ is a pseudonym of a user, and $t_r$ is the registered time, loc and dest are the location of a user and his destination, respectively, $\stackrel{⃑}{V}$ represents a user's history velocity vectors, $\text{Con}$ represents a query content, k is his anonymity degree, $P\text{set}$ is a prediction of the next cells, and $n_i$ is registered users’ amount. $\text{C}{\text{S}}_i$ broadcasts his registration situation $B_{\text{cs}i}=(\text{C}{\text{S}}_i,\text{lo}{\text{c}}_{\text{cs}i},n_i,t_i,r_{\min },r_{\max })$ at a regular interval; $t_i$ is broadcasting time, and $r_{\min }$ and $r_{\max }$ are defined in Definition 2 and in Figure 7.

Figure 7

Repartition of a cell.

Figure 8

Road networks Voronoi graph.

Definition 2 (repartition of a cell).

If a user's location meets $\mathrm{dist}(u_k,\text{C}{\text{S}}_i)<r_{\min }$ , he is in a convinced region, if it meets $\mathrm{dist}(u_k,\text{C}{\text{S}}_i)>r_{\max }$ , he is in an excluding region, and if it meets $r_{\min }\le \mathrm{dist}(u_k,\text{C}{\text{S}}_i)\le r_{\max }$ , he is in an unconvinced region.

As shown in Figure 7, a user in a convinced region of a cell is certainly in the cell, such as C, and in an excluding region, the user is certainly not in the cell, such as D, and in an unconvinced region, a user has both situations, such as A and B.

4.2. Registration and Cooperative k-Anonymity Phase

In road networks, registration and anonymity are affected by user's moving direction, so we specify a cell prediction method first.

4.2.1. Road Networks Voronoi Graph Partition

Direction prediction is important to all the following procedures. We consider a user is in restrained road networks; his moving direction is affected by roads. The Voronoi graph partition is on the road networks, as shown in Figure 8. In initialization phase, TA marks all the roads with numbers according to its sole actual road name, the same road may go through several cells, and the roads are directed connected graph and form road networks. Then TA sends two tables to every corresponding CS, $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{1}}$ records all the road segments in a cell, and $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{2}}$ records all of the neighbor CSs of a cell.

Definition 3 (Table_csi1).

The road segments table is denoted as $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{1}}$ and represented by its attributes $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{1}}=〈\text{RoadID}\mid \text{Connect}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{RoadID}〉$ , RoadID is the identification number of a road in cell $V(\text{C}{\text{S}}_i)$ , and Connect RoadID is all the directly connected roads to RoadID in the cell.

As shown in Figure 8, in a cell $V(\text{C}{\text{S}}_i)$ , Road Segment 1 is recorded in $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{1}}$ as a row record $〈\mathrm{1}\mid \mathrm{2,3},\mathrm{4}〉$ . Each road segment in $V(\text{C}{\text{S}}_i)$ has the same kind of row record.

Definition 4 (Table_csi2).

All the neighbor CSs of a cell are in $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{2}}$ and represented by its attributes $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{2}}=〈\text{CS}\mid \text{lo}{\text{c}}_{\text{cs}}\mid \text{Connect}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{RoadID}〉$ , CS is neighbor's identities, $\text{lo}{\text{c}}_{\text{cs}}$ is the location of CS, and $\text{Connect}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{RoadID}$ represents directed connected road numbers to a neighbor cell.

As shown in Figure 8, a neighbor $\text{C}{\text{S}}_k$ of cell $V(\text{C}{\text{S}}_i)$ is recorded as $〈\text{C}{\text{S}}_k\mid \text{lo}{\text{c}}_{\text{cs}k}\mid \mathrm{2,3},\mathrm{4}〉$ ; each neighbor CS has the same kind of row record in $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{2}}$ .

The correlation of $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{1}}$ and $\text{Tabl}{\text{e}}_{\text{cs}i\mathrm{2}}$ can deduce paths which leads a user in a cell to another neighbor cells. Due to the constraints of roads, that is, a user has to travel along the roads rather than arbitrary locations in Euclidean space, CS can predict next neighbor cell for a user according to his history movements and destination. The result of prediction is also provided to the user, which helps the user to register to next CS.

4.2.2. Next Neighbor Cell Prediction

Although there are roads constraints, a user always chooses the paths which most of its road segments approximately point to his destination, or else the user will not get to his destination. And most of his history velocity vectors, constrained by the roads, have the same feature. CS uses Formula (1) to predict the weights of each neighbor cell for a user according to his registering message ${\text{Register}}_{u_k}=(u_k,\text{lo}{\text{c}}_{u_k},\text{dest},t_r,\stackrel{⃑}{V},\text{Con},k_{u_k})$ , and then it stores the prediction results in $P\text{set}$ . Suppose $u_k$ is in a cell $V({\text{CS}}_j)$ ; ${\text{CS}}_j$ computes the weight of one of his neighbor cells $\text{C}{\text{S}}_i$ for $u_k$ :

$$\begin{array}{cc}& P_{\text{cs}i}={\delta }_d·\theta \left(\stackrel{⃑}{{\text{CS}}_j\text{dest}},\stackrel{⃑}{{\text{CS}}_j\text{C}{\text{S}}_i}\right)+{\delta }_h·\frac{{\sum }_{x=\mathrm{1}}^w\theta \left(\text{C}{\text{S}}_i,\stackrel{⃑}{v_x}\right)}{w}.\end{array}$$

(1)

$\stackrel{⃑}{{\text{CS}}_j\text{dest}}$ is the vector from ${\text{CS}}_j$ to $\text{dest}$ , θ is used to compute the angle between two vectors, $\stackrel{⃑}{v_x}\in \stackrel{⃑}{V}$ is one of the user's history velocity vectors, and w is its amount; ${\delta }_d$ and ${\delta }_h$ are weights which are 0.4 and 0.6, respectively. According to Formula (1), we can find that a smaller $\theta (\stackrel{⃑}{{\text{CS}}_j\text{dest}},\stackrel{⃑}{{\text{CS}}_j\text{C}{\text{S}}_i})$ means a small deviation to a user's destination if the user chooses a cell $V(\text{C}{\text{S}}_i)$ to pass through, and more history velocity vector pointing to $\text{C}{\text{S}}_i$ means entering the cell $V(\text{C}{\text{S}}_i)$ will not bring large deviation comparing with history directions. Therefore, the lower $P_{\text{cs}i}$ is, the higher probability of a user to go through $\text{C}{\text{S}}_i$ . ${\text{CS}}_j$ computes all the neighbor cells’ weights for a user and stores them in $P\text{set}=\{P_{\text{cs}i},P_{\text{cs}k},P_{\text{cs}r},\dots \}$ in ascending order.

After the registration for a user, CS checks the road number which the user travels on by reverse geocoding techniques and computes $P\text{set}$ ; the neighbor cell with minimum weight is the most likely cell which the user will enter into.

The prediction result also affects the anchors selection in continuous query. It also can be used to plan routes for users. The connecting paths of next cell are deduced by Definitions 3 and 4; CS can select the best one for a user according to path length and road congestion situation.

4.2.3. User Registration

A user will receive several neighbor CSs broadcasting messages $B=\{B_{\text{CS}\mathrm{1}},B_{\text{CS}\mathrm{2}},\dots ,B_{\text{CS}n}\}$ , and he needs to register to an appropriate CS that he is in or about to. As a user's query request will be sent to LSP through a CS, enough users in the same cell make a user avoid being the only target to be attacked. According to these messages, only if there are enough users in the appropriate cell, a user will register to the CS or else wait for the next message. $u_k$ 's other related information will be sent within $\text{Registe}{\text{r}}_{uk}=(u_k,\text{lo}{\text{c}}_{uk},\text{dest},t_r,\stackrel{⃑}{V},\text{Con},k_{uk})$ . The key point is how to register to an appropriate CS according to $B=\{B_{\text{CS}\mathrm{1}},B_{\text{CS}\mathrm{2}},\dots ,B_{\text{CS}n}\}$ .

As shown in Figure 7, according to repartition, $u_k$ estimates the cell which he is in or heading to: for each $B_{\text{cs}i}\in B$ , $u_k$ drops the old message and computes the distance between each $\text{C}{\text{S}}_i$ and himself; if $\mathrm{dist}(\text{lo}{\text{c}}_{uk},\text{lo}{\text{c}}_{\text{cs}i})<r_{\min }(\text{C}{\text{S}}_i)$ is found, $u_k$ is definitely in $V(\text{C}{\text{S}}_i)$ according to Definition 2, the user registers to the $\text{C}{\text{S}}_i$ and drops all the other messages then or else drops all messages which meet $\mathrm{dist}(\text{lo}{\text{c}}_{uk},\text{lo}{\text{c}}_{\text{cs}i})>r_{\max }$ ; because these messages are from excluding regions. And then $u_k$ computes minimum distance “ $\min \{\mathrm{dist}\mathrm{\hspace{0.17em}\hspace{0.17em}}(\text{lo}{\text{c}}_{uk},\text{lo}{\text{c}}_{\text{cs}i})\}$ ” of these neighbor CSs, because $u_k$ is in their unconvinced regions at the same time, and registers to the minimum distance CS. Since the deployment of CS, lots of users can help to transmit broadcasting messages and each user is more possible to receive the message from his cell quickly. Even if $u_k$ have not received the message from the appropriate cell during a time period, that means there are not enough users around the CS; it cannot achieve k-anonymity for any user either. $u_k$ should not register to that CS. The static registration algorithm is as shown in Algorithm 1.

Algorithm 1: A static user estimates the Voronoi cell he is staying in and registers to the CS.

(1)   Procedure: $$u_k$$ receives n broadcasting messages

     $$B=\{B_{\text{cs}\mathrm{1}},B_{\text{cs}\mathrm{2}},\dots ,B_{\text{cs}n}\}$$ from different CSs, a

     $$B_{\text{cs}i}\in B$$ is $$B_{\text{cs}i}=(\text{C}{\text{S}}_i,lo{c}_{\text{cs}i},n_i,t_i,r_{\min },r_{\max })$$

(2)    $$u_k$$ generates empty arrays Array and RegisTime

(3)   for each $$B_{\text{cs}i}\in B$$   do

(4)    while   $$t_{now}-t_i<\delta$$ and do       //   $$t_{now}$$ is current

      time, $$\delta$$ is a threshold, the formula helps to drop

      old messages

(5)       compute $$dist(lo{c}_{uk},lo{c}_{\text{cs}i})$$

(6)       if   $$dist(lo{c}_{uk},lo{c}_{\text{cs}i})<r_{\min }$$   then

(7)        discard all the other messages

(8)       else if   $$dist(lo{c}_{uk},lo{c}_{\text{cs}i})>r_{\max }$$   then

(9)         discard $$B_{\text{cs}i}$$

(10)     else   $$Array\leftarrow B_{\text{cs}i}$$

(11)   compute $$\min \{dist(lo{c}_{uk},lo{c}_{\text{cs}i})\}$$   Array

(12)  if   $$\min (dist(lo{c}_{uk},lo{c}_{\text{cs}i}))$$ exits then

(13)    register to $$\text{C}{\text{S}}_i$$

(14)     $$RegisTime\leftarrow T_{reg}(\text{C}{\text{S}}_i)$$

    // record the register time to $$\text{C}{\text{S}}_i$$

(15)  End Procedure.

Algorithm 1 is only suitable to static or slow users, but when a user moves quickly, such as B in Figure 8, if he moves upward of the figure and registers to ${\text{CS}}_j$ , he will register wrong even he is still in $V({\text{CS}}_j)$ , because he is about to get out of that cell. So we modify the algorithm with cell prediction to make sure that a user registers to an appropriate CS (see Algorithm 2).

Algorithm 2: Registration algorithm with cell prediction for dynamic users.

(1)   Procedure: $$u_k$$ receives n broadcasting messages

     $$B=\{B_{\text{cs}\mathrm{1}},B_{\text{cs}\mathrm{2}},\dots ,B_{\text{cs}n}\}$$ from different CSs, a

     $$B_{\text{cs}i}\in B$$ is $$B_{\text{cs}i}=(\text{C}{\text{S}}_i,lo{c}_{\text{cs}i},n_i,t_i,r_{\min },r_{\max })$$

(2)    $$u_k$$ generates empty arrays Array, Angle and Register

(3)   for each $$B_{\text{cs}i}\in B$$   do

(4)    while   $$t_{now}-t_i<\delta$$   do

(5)     compute $$dist(lo{c}_{uk},lo{c}_{\text{cs}i})$$

(6)     if   $$dist(lo{c}_{uk},lo{c}_{\text{cs}i})<r_{\min }$$   then

(7)      discard all the other messages

(8)     else if   $$dist(lo{c}_{uk},lo{c}_{\text{cs}i})>r_{\max }$$   then

(9)       discard $$B_{\text{cs}i}$$

(10)   else   $$Array\leftarrow B_{\text{cs}i}$$

(11)  while   $$Array=\text{!}NULL$$   do

(12)   for each $$B_{\text{cs}i}\in Array$$   do

(13)    compute $$\theta =(\overrightarrow{V_{uk}},\overrightarrow{u_k\text{C}{\text{S}}_i})$$ // $$\overrightarrow{V_{uk}}$$ is $$u_k$$ 's

       moving direction and $$\overrightarrow{u_k\text{C}{\text{S}}_i}$$ is vector

       from $$u_k$$ to $$\text{C}{\text{S}}_i$$ , $$\theta$$ is vetorial angle

(14)    if   $$\theta \ge {\mathrm{90}}^{°}$$   then

(15)     discard $$B_{\text{cs}i}$$

(16)    else if a weight of $$\text{C}{\text{S}}_i$$ exists in $$Pset$$

       //     $$Pset=\{P_{\text{cs}n},P_{\text{cs}k}$$ , $$.P_{\text{cs}i},\dots$$ } is the cell

       prediction results from CS he had just

       registered to, referring to Section 4.2

(17)      compute $${\mathcal{M}}_{\text{cs}i}={\lambda }_{uk}·{\theta }_{\text{cs}i}+{\lambda }_{\text{cs}}·P_{\text{cs}i}$$

         //   $${\lambda }_{uk}$$ and $${\lambda }_{\text{cs}}$$ are weights, values

         are 0.6 and 0.4 respectively

(18)        $$Angle\leftarrow {\mathcal{M}}_{\text{cs}i}$$

(19)       else   $${\mathcal{M}}_{\text{cs}i}={\lambda }_{uk}·{\theta }_{\text{cs}i}+{\lambda }_{\text{cs}}·\mathrm{1}$$

(20)          $$Angle\leftarrow {\mathcal{M}}_{\text{cs}i}$$

(21) compute $$\min (Angle)\mathrm{\hspace{0.17em}\hspace{0.17em}}$$

(22) if   $$\min (Angle)$$ exists and is $${\mathcal{M}}_{\text{cs}i}$$   then

(23)  register to $$\text{C}{\text{S}}_i$$

(24)   $$RegisTime\leftarrow T_{reg}(\text{C}{\text{S}}_i)$$

(25) End Procedure.

After successful registration to a CS, a user will report his latest locations periodically to the CS and drop broadcasting message from it until the user gets out of the cell or registers to next cell. If a user is in an unconvinced region, he has a probability to enter into a neighbor cell, so prediction to the next cell is significant; the prediction has two factors, as shown in Line 17: one is the current moving direction of the user himself, the other one is cell prediction results from CS he had just registered to, referring to Formula (1), and the former one we have not discussed yet, and it is a little complicated that we divide it into 3 cases.

• (1)

  $u_k$ in a convinced region need not estimate next cell. As shown in Figure 9(a), $u_k$ staying at C decides whether to register to $\text{C}{\text{S}}_i$ according to his motion state. We divide motion state into two kinds: $(1)$ when ${\theta }_{\mathrm{1}}=(\overrightarrow{V_{uk}},\overrightarrow{u_k\text{C}{\text{S}}_{\text{i}}})<\mathrm{9}{\mathrm{0}}^{\circ }$ , $u_k$ has just gotten into a cell and received $B_{\text{cs}i}$ , so $u_k$ registers to $\text{C}{\text{S}}_i$ directly without estimating next cell; $(2)$ when ${\theta }_{\mathrm{2}}=(\overrightarrow{V_{uk}},\overrightarrow{u_k\text{C}{\text{S}}_i})>\mathrm{9}{\mathrm{0}}^{\circ }$ , $u_k$ has just left from the convinced region, which indicates $u_k$ has entered into the cell and registered to $\text{C}{\text{S}}_i$ for a certain time; $B_{\text{cs}i}$ is a repeat message now and discarded by $u_k$ . To sum up, if $u_k$ finds that he is in a convinced region, he need not compute angle $\theta =(\overrightarrow{V_{uk}},\overrightarrow{u_k\text{C}{\text{S}}_i})$ or predict next cell.

• (2)

  $u_k$ in an excluding region need not estimate next cell. As shown in Figure 9(b), $u_k$ stays at D and receives $B_{\text{cs}i}$ ; if he has just left the cell, he will discard it, or if he is about to enter into the cell he will receive $B_{\text{cs}i}$ again with high probability when he is much closer to $\text{C}{\text{S}}_i$ . So in this case, $u_k$ is far from $\text{C}{\text{S}}_i$ ; he discards $B_{\text{cs}i}$ without estimation.

• (3)

  $u_k$ in an unconvinced region must estimate next cell. As shown in Figure 9(c), $u_k$ staying at B may receive several messages, from ${\text{CS}}_j$ or $\text{C}{\text{S}}_k$ . $(1)$ When ${\theta }_{\mathrm{3}}=(\overrightarrow{V_{uk}},\overrightarrow{u_k{\text{CS}}_j})>\mathrm{9}{\mathrm{0}}^{\circ }$ , $u_k$ is leaving from $V({\text{CS}}_j)$ ; he discards $B_{\text{cs}j}$ even he is still in the cell. $(2)$ When ${\theta }_{\mathrm{1}},{\theta }_{\mathrm{2}}<\mathrm{9}{\mathrm{0}}^{\circ }$ and ${\theta }_{\mathrm{1}}\approx {\theta }_{\mathrm{2}}$ , it is hard for $u_k$ to estimate which cell he is heading to; $u_k$ needs a further estimation. In Algorithm 2 Lines 16–22, all the angle less than $\mathrm{9}{\mathrm{0}}^{\circ }$ may be the next cell, for each of the $u_k$ computes $\mathcal{M}$ which is affected by prediction results $P\text{set}$ from CS; the minimum $\mathcal{M}$ is the predicted result, which makes the estimation more accurate.

Figure 9

Mobile user's current direction estimation.

In conclusion, only the users in an unconvinced region need to predict next cell by computing $\mathcal{M}$ , those are the users who are leaving from the current cell to another, and it is consistent with actual situation. Therefore the repartition of a Voronoi cell is befitting for registration and simplifies the procedure for a user.

4.2.4. Cooperative Anonymity Algorithm

After receiving registrations from users, CS organizes them to form several cooperative k-anonymity groups which meet each member's k-anonymity degree in a group. As discussed before, cooperative k-anonymity is just like the way P2P achieves anonymity, and the function of cluster head is undertaken by a CS. As shown in Algorithm 3, $\text{C}{\text{S}}_i$ checks the road number of the registering user staying at and computes $P\text{set}$ for the user. $\text{C}{\text{S}}_i$ searches registration table $\text{Tabl}{\text{e}}_R$ for all the users who have the same next cell prediction result and stores them in array $\text{Sim}$ . That considers user's moving direction similarity and insures proportion of users using the same anchor sequence to avoid correlating attacks. Then $\text{C}{\text{S}}_i$ picks users in $\text{Sim}$ on neighbor roads by preference; if users in a group are not enough, the group will be combined with another group. It is worth noticing that the way of constructing cloaking regions always finds the minimum boundary rectangle containing neighbor uses, which insures the security of a query. In our method, CS organizes users registered to the same cell to form anonymity groups without constructing cloaking regions, so we do not consider finding neighbor users but the similar direction users in the cell. The cell is similar to a cloaking region and several users in it are chosen to form a group (see Algorithm 3).

Algorithm 3: Cooperative anonymity group construction.

(1)   Procedure: $$\text{C}{\text{S}}_i$$ received registration message

    $$Registe{r}_{uk}$$ from $$u_k$$ , and computes $$Pse{t}_{uk}$$ for him

   according to Formula (1), $$\text{C}{\text{S}}_i$$ stores $$Pse{t}_{uk}$$ in

    $$Tabl{e}_R$$ . The CS owns two tables: $$Tabl{e}_{\mathrm{1}}$$ and $$Tabl{e}_{\mathrm{2}}$$ as in

   Definitions 3 and 4, respectively.

(2)    $$\text{C}{\text{S}}_i$$ generates empty arrays Sim, Group

(3)   for each $$u_i\in Tabl{e}_R$$   do

(4)    if   $$\min (Pse{t}_{ui})=\min (Pse{t}_{uk})$$   then

(5)      $$Sim\leftarrow u_i$$

(6)      $$Grou{p}_{uk}\leftarrow$$ find users in $$Sim$$ clockwise

       whose anonymity degree meets $$k_{ui}\le k_{uk}$$

(7)   if   $$\left|Grou{p}_{uk}\right|<k_{uk}$$   then

(8)      for other $$Grou{p}_{um}$$   do

(9)         if   $$\left|Grou{p}_{um}\right|+\left|Grou{p}_{uk}\right|\ge \max (k_{um},k_{uk})$$   then

(10)           $$Group\leftarrow$$ combine $$Grou{p}_{um}$$ with $$Grou{p}_{uk}$$

(11) return   $$Group$$

(12) End procedure

In Algorithm 3, Lines 3–5 pick users who have the same next neighbor cell to form the group; Lines 6 and 9 make the constructed group satisfy each user's anonymity degree. The combination in Line 10 guarantees quality of anonymity service. After successful anonymity, CS removes users’ identities and sends the group of queries to LSP with continuous anchors instead of any user's actual location. An item of query is denoted as $(\text{C}{\text{S}}_i,\text{lo}{\text{c}}_{\text{anchor}},\text{Con})$ , $\text{lo}{\text{c}}_{\text{anchor}}\in \text{Anchor}$ ; $\text{Anchor}$ is an anchor sequence and $\text{Con}$ is a query content.

4.3. Query Phase

4.3.1. Anchor Picking

When a user has gotten out of one cell he will enter into another cell inevitably. Therefore, a user picks anchors according to the cell prediction result in continuous query. The anchor sequence is generated by two elements: one is the location of $\text{C}{\text{S}}_i$ which the user is staying in now; the other one is the location of $\text{C}{\text{S}}_m$ which the user is heading to. The anchor sequence is on the line segment from $\text{C}{\text{S}}_i$ to $\text{C}{\text{S}}_m$ ; the anchor amount in a sequence depends on user query frequency. Midpoint of the segments is picked as an anchor:

$$\begin{array}{cc}& \text{lo}{\text{c}}_{\text{mid}im}=\left(\frac{X\text{cs}i+X\text{cs}m}{\mathrm{2}},\frac{Y\text{cs}i+Y\text{cs}m}{\mathrm{2}}\right).\end{array}$$

(2)

An anchor sequence with three anchors for $u_k$ is denoted as $\text{Ancho}{\text{r}}_{uk}=(\text{lo}{\text{c}}_{\text{cs}i},\text{lo}{\text{c}}_{\text{mid}im},\text{lo}{\text{c}}_{\text{cs}m})$ ; CS computes anchor sequences for different users. The users who enter into the same next cell have the same anchor generating elements.

4.3.2. Query Algorithm

CS picks an anchor from anchor sequence to replace user's location and send a snapshot query of a continuous query request [23]. The anchor is the one which the user has not passed in his anchor sequence. So CS asks a registered user to report his latest location in a continuous query procedure. When LSP receives a query, it uses the anchor to perform an INN search. After candidate results are returned from LSP, CS uses Algorithm 4 to work out each snapshot query result which is precise KNN PoIs to a user. We propose Algorithm 4 at CS end consulting SpaceTwist, but SpaceTwist has the uneven distribution problem we have specified in Section 2. We will solve this problem to make PoI results distribute around a user but not around the anchor. We call Algorithm 4 the “Singeos.”

Algorithm 4: Singoes running on CS for KNN PoIs.

(1)   Procedure: $$K\in Con$$ , $$q\leftarrow$$ get $$u_k$$ 's current location

(2)    $$q^{\prime }\leftarrow$$ pick an anchor which $$u_k$$ has not passed yet in

    the anchor sequence $$Ancho{r}_{uk}$$

(3)   the registered central server generates a min heap $$H_{\min }$$

(4)   insert K pairs of $$〈NULL,\mathrm{\infty }〉$$ in previous snapshot

    query into $$H_{\min }$$

(5)    $$\gamma \leftarrow$$ the bottom distance in $$H_{\min }$$

    // initialize radius of demand space

(6)    $$\tau \leftarrow \mathrm{0}$$    // initialize radius of supply space

(7)   Send INN search request to LSP with anchor $$q^{\prime }$$

(8)   while   $$\gamma +dist(q,q^{\prime })>\tau$$ and $$\tau <r_{threshold}$$   do

(9)       $$\text{POI}\leftarrow$$ continue to get an INN package of

       PoIs from LSP

(10)     $$\tau \leftarrow \text{ma}{\text{x}}_{\mathcal{P}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{i}\in \text{POI}}\hspace{0.17em}dist(q^{\prime },{\mathcal{P}}_{\mathrm{i}})$$

(11)    for each $${\mathcal{P}}_{\mathrm{i}}\in \text{POI}$$   do

(12)     if   $$dist(q,{\mathcal{P}}_{\mathrm{i}})<\gamma$$   then

(13)      update $$H_{\min }$$ and $$\gamma$$ by using $$dist(q,{\mathcal{P}}_{\mathrm{i}})$$

(14) $$\gamma \leftarrow$$ get $$dist(q,{\mathcal{P}}_{\mathrm{k}})$$ of Kth PoIs in $$H_{\min }$$

    // expand demand space and don't change $$\gamma$$ anymore

(15) while   $$\gamma +dist(q,q^{\prime })>\tau$$ and $$\tau <r_{threshold}$$   do

(16)     $$\text{POI}\leftarrow$$ continue to get an INN package of

       PoIs from LSP

(17)     $$\tau \leftarrow \text{ma}{\text{x}}_{\mathcal{P}h\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}\in \text{POI}}\hspace{0.17em}dist(q^{\prime },{\mathcal{P}}_h)$$

(18)    if   $$dist(q,{\mathcal{P}}_h)<\gamma$$   then

(19)     update $$H_{\min }$$ by using $$dist(q,{\mathcal{P}}_h)$$

(20)   terminate INN search request

(21)    return  K PoIs from the first one in $$H_{\min }$$

(22)   End Procedure.

As proposed in [27], SpaceTwist terminates when supply space covers the demand space, as shown in Figures 3(c) and 4(a). That is why the PoIs are around anchor $q^{\prime }$ . One solution to deal with this problem is to make the query procedure continue to get more PoIs and terminate when KNN PoIs around the user are found. Singoes is as shown in Algorithm 4.

As shown in Figure 3(c), when ${\mathcal{P}}_4$ is found, supply space covers the demand space, and SpaceTwist terminates and gets $K=4$ PoIs $\{{\mathcal{P}}_{\mathrm{3}},{\mathcal{P}}_{\mathrm{2}},{\mathcal{P}}_{\mathrm{1}},{\mathcal{P}}_{\mathrm{4}}\}$ , but they are around anchor $q^{\prime }$ . In Singoes, demand space expands for the last time and covers K PoIs in the region, which guarantees K PoIs at least are gotten by the user, as shown in Figure 10(a). As each PoI is found gradually, supply space will not stop expending until it covers demand space. As shown in Figure 10(c), LSP returns 8 PoIs in total. Singoes gets $K=4$ PoIs $\{{\mathcal{P}}_{\mathrm{3}},{\mathcal{P}}_{\mathrm{2}},{\mathcal{P}}_{\mathrm{1}},{\mathcal{P}}_{\mathrm{5}}\}$ , distributing around q, which is more precise than SpaceTwist.

Figure 10

K nearest neighbor PoIs query for a user.

After finishing a snapshot query with an anchor, the other PoIs will not be discarded, because the user may get closer to these PoIs in next snapshot query of the same continuous query request with anchor sequence. As shown in Figure 10(c), because a snapshot anchor is always picked in front of user, when a user is at q and heading to anchor $q^{\prime }$ , $\{{\mathcal{P}}_{\mathrm{6}},{\mathcal{P}}_{\mathrm{7}}\}$ is closer to the user, so CS can use them to refine the result with a user's latest location to ensure continuous query quality.

4.3.3. Brief Summary

The procedure of our method is as follows.

After initialization, a user who has LBS query request registers to a CS according to his current location and cell prediction results from previous CS. If he registers to a CS for the first time, he will use Algorithm 1 to achieve registration. Then CS predicts the next cell for him according to his history velocity vectors and current direction; CS also returns the prediction results to the user to help him achieve next cell registration. After registration the user should report his latest location and CS constructs a cooperative k-anonymity group for users, and then CS sends a group of queries to LSP with anchors. Each anchor for a user is generated according to the CS locations of his current cell and next cell. At last, CS performs Singoes to compute KNN PoIs for the user according to PoIs candidate sets returned from LSP. For each snapshot query belonging to a continuous query request, CS always picks an anchor in front of the user to ensure the query quality according to Singoes.

4.4. Performance Analysis

4.4.1. Analysis of Anonymity Procedure

Accuracy of Prediction and Registration. Cell prediction is affected by a user's history velocity vector and the current direction. A user always chooses a path in which most of its road segments approximately point to his destination; otherwise the user will not get to his destination. And most of his history velocity vectors, constrained by the road, have the same feature. Since CS's neighbor cells are not many, the direction range of each neighbor cell around the user is obvious; prediction with angular separation has a high success rate. According to Algorithm 2, only the user who is in an unconvinced region needs to predict his next cell, and the prediction has a high success rate. It is a rare event that the user changes his direction in an unconvinced region since the road constraints. According to criterion ${\varsigma }_a<\mathrm{dist}(\text{C}{\text{S}}_i,\text{C}{\text{S}}_k)<{\varsigma }_b$ in Section 3.3, it will not happen that an unconvinced region covers its neighbor convinced regions, so there is no registration in advance by mistake.

Success Rate of Cooperative k-Anonymity. CSs are picked in crowed locations around by lots of users. After Voronoi partition, global map with U users uniform distribution is divided into b cells, each cell containing about $U/b$ users in average. The Voronoi partition is analogous to divide all the users into $U/b$ anonymous groups in advance, so Voronoi partition helps users to achieve k-anonymity quickly. In Algorithm 3 Lines 7–10, the combination of groups guarantees the anonymity quality. Suppose a mobile user whose velocity is 70 km/h enters into a cell with $r_{\max }=\mathrm{500}$ meters; the passing time is about $t\approx \mathrm{0.5}\times \mathrm{2}/\mathrm{70}\times \mathrm{3600}\approx \mathrm{51}$ seconds; experiments in Section 5.2 show the response time of query is less than 1 second. So LBS will last for a while in a cell; a user has enough time to achieve k-anonymity without a jitter.

Anonymity and Query Security. Suppose users are distributed uniformly; if an adversary knows n users distribution in a cell, a user will be identified with a probability $p(x_i)=\mathrm{1}/n$ when he issues a query; the entropy of issuing a query is

$$\begin{array}{cc}& H\left(q\right)={\displaystyle \sum }_{i=1}^{n}p\left(x_i\right)\log \frac{1}{p\left(x_i\right)}={\displaystyle \sum }_{i=1}^n\frac{1}{n}\log n=\log n.\end{array}$$

(3)

Our method does not utilize cloaking regions so there are no overlapping region attacks. A trusted CS provides anonymity of each query from the same user, and most of the users in a cooperative anonymous group querying with anchors only indicate that these users have passed the cell. An adversary cannot know any user's actual location or the correlation with any query. The m queries from the same user are mutual independence, so the information entropy of a continuous query is

$$\begin{array}{cc}& H\left(q_1\cdots q_m\right)={\displaystyle \sum }_{i=1}^{n}H\left(q_i\right)=m\log n.\end{array}$$

(4)

So our method achieves a less information release which increases an adversary's uncertainty.

Deployment Cost. Constructing a Voronoi graph depends on a large number of CS deployments, which brings cost increasing. That is a defect of our method. But comparing with mobile communication base station whose deployment generally follows shouting distance about 1000 m, our method is acceptable. Distribution service from CSs helps to reduce service bottleneck. And CS can be embedded and maintained as a part of communication base station.

4.4.2. Analysis of Query Procedure

Query Efficiency. Suppose PoIs are randomly distributed on a 2-dimensional space; CS can obtain K PoIs if it searches a circle no more than a radius of γ, so PoIs on a unit area can be computed as $K/\pi {\gamma }^2$ , and the number of PoIs on a region with a radius τ is about $N_1=\pi {\tau }^2·(K/\pi {\gamma }^2)=K·(\tau /\gamma {)}^2$ , in Figure 10(c). When Algorithm 4 terminates, $\tau =\gamma +\mathrm{dist}(q,q^{\prime })$ , so the number of PoIs $N_1$ becomes

$$\begin{array}{cc}& N_1=K·{\left(\mathrm{1}+\frac{\mathrm{dist}\left(q,q^{\prime }\right)}{\gamma }\right)}^{\mathrm{2}}.\end{array}$$

(5)

The fewer PoIs in $N_1$ , the higher query efficiency. As we have just supposed, γ is a constant value; therefore the query efficiency is affected by the distance between a user and his anchor $\mathrm{dist}(q,q^{\prime })$ , which means the anchor picking is significant to query efficiency. As shown in Figure 10(c), if each anchor picking satisfies $\mathrm{dist}(q,q^{\prime })<\gamma$ , so $N_1<4K$ . Compared with using n dummies to issue every PoIs query, which LSP has to return $N_2=nK$ PoIs, Singoes has a remarkable advantage when $n>\mathrm{4}$ . The searching upper limit of Singoes is 4K, but the query procedure will terminate before reaching it in practical.

Query Accuracy. CS uses a user's actual location to work out KNN PoIs according to returned candidate sets; in Singoes Line 14, demand space expands again and keeps it radius γ unchanged, and demand space covers K PoIs at least that time, so even if there are no other PoIs found in the following procedure, K PoIs in the demand space can be found in 100% success rate, which guarantees finding KNN results around a user.

Fixed Anchor. There are many ways to generate anchors; most of them are generated randomly and temporarily. But the anchor sequence in our method is generated only by two neighbor CSs, and other anchors are restrained on the line segments between them; the anchors are not many since the user is moving fast from one cell to another, so the anchors are picked from the integer division points of the line segment; most users may use the same anchor in the anchor sequence, so the anchor is nearly fixed. And the advantages of fixed anchor are as follows.

• (1)

  An anchor which is related to a CS's location is near to users; it guarantees a high efficiency of continuous query as we have just discussed.

• (2)

  Different users pick the same fixed anchors and make adversaries confused; it is much more difficult for them to relate a query with a user.

• (3)

  Fixed anchor queries are sent to LSP; LSP can use cache to store same queries with fixed anchors, which decreases searching database operations compared with random anchors.

5. Experiments

We discuss 4 main metrics in LBS: anonymity success rate, average response time, data traffic, and accuracy of query results. And the affecting factors of metrics are users amount U, user's anonymity degree k, and PoIs number K. The experiments run on different data sets. Comparative experiments of anonymity and query followed.

5.1. Environment Preferences

Simulation experiment is running on Windows 7, CPU is 3.5 GHz Intel Core i7 processor, and RAM is 16 GB. The algorithms are written by Java. We use two data sets, one is a real data set from BGN (http://geonames.usgs.gov/index.html), denoted as GDS, and it includes 169553 PoIs. The other one is simulated data set (http://iapg.jade-hs.de/personen/brinkhoff/generator/), denoted as TBS, and this data set is generated by widely used Thomas Brinkhoff Generator which is based on road networks of Oldenburg in Germany; it generates a city area about 24 km × 27 km. The bandwidth between CS and users is 3 Mbps. CS gets a data package of 128 bytes from LSP each time. Removing 40 bytes package head, if a PoI costs 8 bytes, a package contains at most $\beta =(\mathrm{128}-\mathrm{40})/\mathrm{8}=\mathrm{11}$ PoIs. The parameters and defaults are in Table 1.

Table 1

Parameters and defaults.

Parameters	Value range	Defaults
Anonymity degree k	$$\mathrm{5}\le k\le \mathrm{30}$$	10
Number of users U	$$\mathrm{25000}\le U\le \mathrm{200000}$$	100000
$$\mathrm{dist}(q,q^{\prime })$$	$$\mathrm{500}\le \mathrm{dist}(q,q^{\prime })\le \mathrm{1500}$$	1000 m
PoIs capacity $$\beta$$	$$\mathrm{1}\le \beta \le \mathrm{11}$$	6
Query number of PoIs K	$$\mathrm{5}\le K\le \mathrm{30}$$	10
Amount of PoIs m	—	169553

5.2. Experiments on Different Data Sets

We estimate anonymity success rate, average response time, average packages amount, and accuracy of query results as the number of LBS users increasing on dataset GDS and TBS. Anonymity success rate is the ratio of users achieving anonymity and all LBS users. Response time is the time cost during anonymity and query PoIs, packages amount is sending and receiving packages during response time, and accuracy of query results is the rate of precise PoIs in a KNN query result and K; that is, if 10 NN query results are PoIs of $\{A,B,C,\dots ,I,J\}$ , and eight of them are the ones which a user wants and the K nearest neighbor PoIs to the user, the accuracy of query results is 0.8.

As shown in Figures 11-12, as LBS users are increasing, anonymity success rate is gradually increasing, maintaining ratios more than 80%, and users achieve anonymity effectively and timely. The average response time declines gradually in Figure 12; there are more messages to deal with when confronting with more users; the average response time would have increased, but CS does not construct cloaking regions, and more users make CS facilitated to form cooperative anonymity groups quickly and the PoIs are quickly found with fixed anchors in LSP's cache; therefore the average response time declines and keeps stable at 0.3 seconds.

Figure 11

Success rate of anonymity.

Figure 12

Average response time.

As shown in Figure 13, although packages increase as the number of users increases, average packages maintain stable, because users achieve anonymity by forming anonymity groups instead of constructing continuous cloaking regions; most of them send the request once in a cell until they get out. In the other hand, packages of query for PoIs are increasing, because Singoes needs to search more area via LSP to get KNN PoIs to a user, and the communication between CS and users increases more, as shown in Figure 14.

Figure 13

Average packages of anonymity.

Figure 14

Average packages of query.

As shown in Figure 15, the accuracy of query result maintains steady. That is because Algorithm Singoes guarantees the demand space covers K PoIs in the second expansion and the radius of demand space keeps unchanged; then LSP gradually returns candidate PoIs to Singoes; when the supply space covers the demand space, the searching procedure terminates. Due to the reliability of LSP, all the PoIs which a user queries for are found in the unchanged demand space, so it is easy for Singoes to find the precise K nearest neighbor PoIs in the candidate set around the user who is the center of the demand space.

Figure 15

Accuracy of query results.

5.3. Comparative Experiments of Anonymity

The comparative experiments are carried out on simulation dataset TBS. Firstly, we compare Casper ${}^{*}$ [10], P2P anonymity [14] with cooperative k-anonymity method we have proposed. As shown in Figure 16, when users are increasing, packages of P2P anonymity have a significant growth due to communications among users to form anonymous groups. And there is much burden for anonymizers in Casper ${}^{*}$ to construct cloaking regions for users; therefore the average packages and response time increase both. Therefore the anonymizer is a service bottleneck. Average packages keep stable in our cooperative method without constructing cloaking regions in any cell.

Figure 16

Average packages of anonymity as U is increasing, $k=10$ .

Large anonymity degree of users means more users are needed to achieve k-anonymity; as shown in Figure 17, packages are increasing as k becomes larger. The packages of our method are less than the other two, because CS organizes k registered users to form anonymous groups in low communications. But the success rate of anonymity will decline as k is increasing. From Figures 16-17, we conclude that average packages of our method will maintain stable even if  U and k vary.

Figure 17

Average packages of anonymity as k is increasing, $U=100000$ .

5.4. Comparative Experiments of Query

We compare SpaceTwist [27], PrivacyGrid [32], P2P [14] with our query algorithm Singoes in the query procedure. SpaceTwist and our method both use anchors to query for PoIs. But Singoes uses fixed anchors in every snapshot of the same continuous query request. SpaceTwist runs on user end; Singoes runs on CS. The other two methods PrivacyGrid and P2P query for PoIs both with cloaking regions.

Figure 18 shows that the average packages of query will increase in two algorithms, because both of them have to search more area, which have to return more PoI candidate sets. And in Figure 19, PrivacyGrid has similar packages communication when U is less than 100 thousand, and Singoes's communication cost is lower than it when U is growing larger. P2P has more packages increasement than the other two methods, because the cluster head has to transmit PoIs to each user when U is growing larger.

Figure 18

Average packages of query, compared with SpaceTwist.

Figure 19

Average packages of query, compared with PrivacyGrid and P2P.

In continuous query, Singoes does not discard returned PoIs which are filtered once in KNN query; most of these PoIs in front of the user are used for the next snapshot queries, which makes a snapshot query terminate as soon as KNN PoIs are found. So packages of Singoes are less than SpaceTwist. In Figure 20, as fixed anchors are picked, LSP will store these PoIs around frequently used anchors in cache, which significantly reduces searching time at LSP end, so the average query time of Singoes does not have a significant growth.

Figure 20

Average time of query: K varies from 5 to 30.

PrivacyGrid and P2P are both higher than Singoes in Figure 20; their query time is growing as K increases, especially PrivacyGrid which has to construct cloaking regions for each user, and querying with the cloaking regions leads to the time delay, so the query time cost of Singoes is better than these methods.

6. Conclusion

We propose anonymity algorithm and query algorithm to achieve location privacy preserving. Based on Voronoi graph partition on road networks, we propose cell predicting method as a precondition. In anonymity procedure, CS need not construct cloaking regions for each user, which reduces time and communication cost. And then we propose query algorithm Singoes referring to SpaceTwist, which solves the PoIs uneven distribution problem in SpaceTwist. It uses fixed anchor sequence to issue every snapshot query of the same continuous query request. That protects a user's actual location, and any adversary is hard to associate a query request with a user. The precise query results of KNN PoIs are obtained around a user's actual location. Performance analysis and experiments show that our method achieves QoS of query for PoIs and location privacy preserving. It has better performances compared with other methods.