A Differentially Private Framework for Spatial Crowdsourcing with Historical Data Learning

Spatial Crowdsourcing (SC) is a new avenue of crowdsourcing related to real-world scenarios involving physical locations, which requires workers to physically move to a particular location to perform tasks. The roles of components involved in SC are tasks, workers and the platform (mainly SC-server). The SC-server publishes or assigns the spatial task after receiving request and finally one or more workers accept and finish the task. Usually there are two categories of task assignment modes based on how workers are matched to tasks in SC [23]. In the Worker Selected Tasks (WST) mode, SC-server is only responsible for the release of tasks, and workers autonomously select suitable tasks according to their own locations, without reporting their locations to the SC-server. In Server Assigned Tasks (SAT) mode, SC-server collects worker locations and runs a complex optimization matching algorithm to assign the task to one or more workers, who decide whether to accept the task or not.

The quality of spatial tasks in SC is the main criterion to determine whether the tasks are assigned effectively [2]. It is usually evaluated by reliability, which is formalized as the probability that over $50$ percent of workers correctly answer the task [24], or the chance that as least one worker completes the task successfully [25]. The former is generally used for spatial tasks that require qualified answers, such as spatial data collection related to pictures and videos. For such spatial tasks, the main challenge for SC is how to verify the validity of the results provided by untrusted workers. Since malicious workers may upload some incorrect information, the number of tasks correctly completed needs to be maximized [24]. The latter is generally used in the case that a spatial task should be finished by a single worker, such as taxi calling service and fast food delivery. In such situations, the two factors, the worker-task distance and task expiration time, should be taken into account, to ensure that at least one assigned worker can correctly finish the task [25]. Similarly, the framework proposed by To et al. [6] does not guarantee that the task are disseminated to enough workers, since the SC-server assigns tasks only by the sanitized PSD. Then the method of effectiveness evaluation is to compute the probability that among those assigned to the task at least one worker is willing to accept the task.

Differential privacy (DP) has emerged as the de facto standard privacy notion for privacy-preservation research on data analysis and publishing. It makes that the probability of any output is equally likely from all nearly identical input datasets, so that it is unable to infer any sensitive information of an individual. Afterwards, any adversary cannot conclude with high confidence whether a particular individual is involved in the query result or not.

For applying DP, a crucial choice is the condition under which the datasets $D$ and $D^{\prime}$ are considered to be neighboring. The notion of Unbounded DP is used in our framework, which means that two datasets $D$ and $D^{\prime}$ are neighboring if $D$ can be obtained from $D^{\prime}$ by adding or removing one element.

The parameter $\epsilon$ is termed privacy budget that is specified by a data owner and represents the privacy level to be achieved. A lower budget means a higher privacy level.

The Laplace mechanism provides the $\epsilon$-DP [28]. The following important properties are related to composition of algorithms for preserving $\epsilon$-DP.

In our setting, we add no noise to the counting of the historical locations in each level-1 cell, and use the linear regression method to predict the real-time count of workers in each cell. The sequence of predicted counts can be regarded as a proportion of sampling probability distribution by which locations of the total (noisy) real-time number are randomly (i.i.d.) generated so as to determine a simulated partition of the second level.

Linear regression is one of the basic learning methods in machine learning. The goal is to find a line, a plane, or even a higher-dimensional hyperplane that minimizes the error between the predicted and actual values. There are univariate and multiple linear regressions. Univariate linear regression means that only one factor is considered and the solution involves a linear equation. We use unitary (least squares) regression method to predict location counts.

We evaluate related schemes with three datasets, see Section 6.1 for details. Valid historical locations of the previous 20 periods without noises in counting are used to make a prediction. This produces a probability distribution of locations by which we randomly (i.i.d.) sample a (noisy) total real-time number of points to simulate the real-time distribution. Fig. 1 shows the comparison between the actual counts of level-1 cells and the simulated counts with noise (with sensitivity 1 and privacy budget 0.04) added to the total count in the real-time period on NYTaxi and Gowalla datasets, respectively. The average error rate $\gamma$ is calculated by,

DP guarantees that the probability of producing a given output does not depend much on whether any record is present in the input dataset or not. Random noise is added to each query result to preserve privacy, such that an adversary will not be able to deduce the privacy information of any user from the query outputs, regardless of its prior knowledge.

Existing SC models with differential privacy protection mainly harness real-time location data and generate PSD by performing noise additions and domain partitioning in a crossed way. They have to add noise to worker counts in grids at all levels, which tends to incur high error on many aspects and affects efficiency of SC system.

For this, we are intended to propose a new SC model. That is, given historical and real-time data of worker locations, and a privacy budget $\epsilon$, perturb their counts with necessary noise, generate a suitable PSD and then design a more efficient SC model with privacy protection. Specifically, with the simulated locations drawn from the probability distribution learned from historical data, a domain partitioning is performed with little privacy budget. On the other hand, based on the grids determined previously, the real-time data are directly imported into the bottom cells in which the counts are perturbed with almost the whole privacy budget. In addition, how to optimize task assignments in SC from various perspectives (particularly to achieve stable success rate of task assignment) based on PSD with perturbation is also considered in this paper.

Like [6], we consider the privacy protection problem of SC worker locations in the SAT mode. Fig. 2 describes our proposed system framework that consists of four parts: CSP, SC-server, requesters and workers. Workers send their real location information to CSP. As a trusted third party, CSP collects locations reported by workers, and construct PSD with noises. Requesters submits tasks and exposed location information to SC-Server. After receiving a task request, the untrusted SC-server determines $GR$ by querying the PSD and initiates a geocast communication process.

The SC-server is assumed to be semi-honest and intentionally deduces sensitive information of locations from the PSD. Under mutually-agreed upon rules with workers for data disclosure, CSP exposes PSD release (without identities and locations) to SC-servers and contacts workers in the $GR$. CSP plays mainly the role of communications, and computations to generate $GR$ are carried out at the SC-server part. Possible disclosure of worker location and identity after her consent to the task is outside our scope.

To be specific, our work focuses on the design of PSD using historical data learning at CSP part. Based on historical locations, we adopt linear regression method to make prediction and simulate the real-time distribution of locations at the level-1 grid, which yields the partition together with adaptive grids (AG) method. Then CSP publishes the PSD with noisy real-time counts. Fig. 3 describes the procedure of building PSD with learning. See Section 4.2 for details.

As shown in Fig. 2, the whole scheme consists of the following steps.

1. Step 0:

   Workers report their real locations to the CSP, which will be divided into real-time and historical data.

2. Step 1:

   A requester sends task $t$ to SC-server.

3. Step 2:

   SC-server queries the PSD with the CSP.

4. Step 3:

   According to the given privacy budget $\epsilon$, CSP partitions the data domain by learning historical locations reported by workers and imports noisy real-time counts into the generated grids to update the PSD for answering to SC-server.

5. Step 4:

   SC-server determines $GR$ and initiates a geocast communication process in two ways (infrastructure-based or infrastructure-less mode) as in [6].

6. Step 5:

   If a worker in $GR$ accepts the task, she sends a consent message to the SC-server (or the requester) for confirming her availability.

The above scheme is mainly designed for a single-task assignment system model in dynamic scenarios where for each real-time task request, the CSP collects properly the latest real-time location data of workers and updates the PSD with newly confirmed historical data, and only a worker is required to complete the task. If worker locations change rapidly, our scheme allows fixing the grid structure and updating only real-time counting in cells, which is assigned the same privacy budget. This is a significant advantage of our scheme, in particular on running time, see Section 6.4.

In the static scenario, SC-server deploys a fixed PSD in a period to release $GR$, and Steps 0, 2 and 3 can be skipped. In the case of multiple tasks, our system model is still valid under the assumption that the task assignments do not interfere with each other.

The first stage in our framework consists of building a PSD (at the CSP part), which determines the accuracy of released data and also affects performance metrics. Here we improve the extended Adaptive Grid method (AG) developed in [6] with historical locations learning. Table I summarizes the notations used in our description.

The work flow of our improved AG is shown in Fig. 3. Compared to the extended AG proposed in [6], our PSD construction takes advantage of historical data learning. The detailed procedure is given as follows.

Firstly (Step ① in Fig. 3, level-1 partition), as before, at the first level, AG creates a fixed-size $m_{1}\times m_{1}$ grid over the data domain with the level-1 granularity $m_{1}$ chosen as

where $N^{\prime}$ is the noisy total number of locations computed by adding random Laplace noise with scale $1/(\beta\epsilon)$, $\epsilon$ is used here just as a parameter for partitioning (privacy cost $\beta\epsilon$ is a small fraction of the total budget $\epsilon$) and $k_{1}=10$ as in [6].

Secondly (Steps ②-③ in Fig. 3, prediction with historical data learning), historical data (without noise) are imported into the level-1 grid to make prediction of each cell’s count. The historical data divided by $n$ periods is denoted by $H=\{h_{1},h_{2},...,h_{n}\}$. AG issues count queries in all level-1 cells for each $h_{k}$, denoted by $N_{k}^{ij}$. For each cell $c_{ij}$, the linear regression on $\{N_{k}^{ij}\}_{k=1}^{n}$ yields $N_{p}^{ij}$, a locally predicted count of the real-time locations in cell $c_{ij}$. Then, the probability distribution is evaluated with fractions $N_{p}^{ij}/\sum_{i,j}N_{p}^{ij}$ of predicted total locations.

Next (Steps ④-⑤ in Fig. 3, simulation and level-2 partition), according to the probability distribution of locations on level-1 cells (as index nodes) predicted above, randomly generate $N^{\prime}$ points (independent and identically distributed, i.i.d.) to simulate the real-time distribution. Then level-2 granularity $m_{2}$ for each level-1 cell $c_{ij}$ is chosen as

where $N^{ij}_{\rm sim}$ denotes the point count on cell $c_{ij}$ by sampling simulation and $k_{2}=\sqrt{2}$ is selected as in [6] and $\epsilon^{\prime}$ is still a parameter with $\epsilon^{\prime}$ = 0.5 $\times\epsilon$ but not privacy budget.

Afterwards (Step ⑥ in Fig. 3, sanitized countings), real-time locations are imported into the adaptive grids generated above, and the location count in each cell are added by Laplace noise with scale $1/\epsilon$. We mention that each noisy count is set zero immediately if negative. Then the PSD is completed as is processed in Fig. 3.

Indeed, we can use only real-time data even in the simulation for level-2 partition which costs no privacy budget. However, location distribution sometimes changes rapidly and irregularly while historical data learning provides the overall trend of distribution theoretically. Such a scheme using historical data allows us to fix grid structure and update only noisy real-time count in each cell for quick release of tasks while workers move rapidly.

In this section, we mainly introduce some new strategies for constructing $GR$. We investigate some techniques across local cell selections to fuse those cells with negative noisy counts and develop a quality scoring function involving the area of cells instead of utility function for cell selections.

Currently we consider just the static case for task locations. The probability of a worker accepting a task is only related to the worker-task distance. We refer to the mean contribution distance (MCD) proposed in [29], where the MCD is computed as

where $L_{w_{i}}$ is the location of worker $w_{i}$, and $L_{c_{j}}$ the locations of its $n$ contributions. Following [30], we regard $90\%$ of $MCD$ as maximum travel distance (MTD) that is the maximum distance a worker accept to travel to perform a task.

In contrast to the utility function proposed in [6], we introduce a quality scoring function that considers noisy worker count and the cell-task distance as well as cell’s area. For adding each neighboring cell to $GR$, the score $q_{t}^{k}$ of cell $c_{k}$ in the candidate heap $Q$ for task $t$ is defined as:

where $N_{k}$ represents the number of noisy workers in candidate cell $c_{k}$, $S_{k}$ the area of cell $c_{k}$ and $D_{t}^{k}$ the cell-task distance computed by the average distance between the task and four corners of cell $c_{k}$. It is reasonable that the higher density of workers $N_{k}/S_{k}$ in cell $k$ or the shorter the cell-task distance $D_{t}^{k}$, the higher score $q_{t}^{k}$. The functions $f_{s}$ and $f_{d}$ are (positive and) monotonic on $S_{k}$ and $D_{t}^{k}$, respectively, and linear mappings to some interval $[a,b]$. Such functions are designed to control the influence of varying the factors, area and distance.

Our algorithm to construct $GR$ is shown in Algorithm 1.

In Line 2, in order to improve the compactness of the $GR$, we set a restriction by Local Maximum Geocast Region (LGR) centered at task $t$ during cell selection and the radius computation of $LGR$ is presented in Section 5.2. In Line 11, we add a termination condition for cyclic program in the case that all candidate cells include non-positive (and noisy) count of workers, which will be discussed in detail in Section 5.3.

In Lines 4 and 14, we calculate the utility value of some cell $c$ by, the utility function naturally defined in [6],

Here, $N_{c}$ denotes the noisy count of workers in cell $c$, $AR_{t}^{c}$ represents the average task acceptance probability of each worker in cell $c$. All workers in the same cell are regarded to have the same $AR$ value. Then $\left(1-AR_{t}^{c}\right)^{N_{c}}$ gives the probability that no workers in $c$ are willing to perform the task $t$. The practical meaning of $U_{t}^{c}$ is the probability that at least one worker in cell $c$ is willing to finish task $t$. All possible candidate workers for each task are limited in the maximal distance $MTD$ from task $t$. The $AR$ value is assumed to decrease linearly with distance and defined as

where $d$ represents the average distance between the task $t$ and the four corners of the cell $c$, and $MAR$ is defined as the maximum task acceptance rate of workers. Once the worker-task distance reaches $MTD$, the $AR$ vanishes.

In Line 15, after adding $c$ to $GR$, we should update the $GR$ utility by

Once $U$ reaches the expected utility $EU$, it returns $GR$ directly. Otherwise, we continue to select a new neighboring cell which ensures that the $GR$ is a continuous region. The significant effect of using quality scoring function is shown as in Fig. 4, see Section 5.1 for details.

Adding noise to protect worker locations in SC will inevitably reduce the validity of worker-task matching and efficiency of task assignment.

To be specific, a notified region with a (noisy) positive count may contain no workers. Some workers may be notified of the task with long distance while nearer workers have no tasks. Moreover, some redundant messages for notification increase overhead. In order to evaluate the performance of the framework, we concentrate on the following performance metrics proposed in [6].

1. (1)

   Assignment Success Rate (ASR). As usual, ASR measures the ratio of tasks assigned successfully to the total number of task requests. The challenge for us is to ensure that ASR reaches the threshold $EU$ in the average sense of many task assignments.

2. (2)

   Worker Travel Distance (WTD). Long distance will inevitably affect the efficiency of task execution. The goal is to keep the actual worker-task distance as small as possible on average.

3. (3)

   Average Number of Notified Workers (ANW). ANW affects both the communication overhead of the $GR$ and the computation overhead of the matching algorithm. Its goal is to inform as few workers as possible without compromise on the ASR.

4. (4)

   Average Hop Count Required for Geocast (HOP). In practice, task notifications to workers in $GR$ are sent by hop-by-hop wireless communication. HOP means the hop count required to disseminate the task request to all workers in given region. We approximate HOP as diameter of the $GR$ divided by the diameter of the communication range ($100$ meters for WiFi).

5. (5)

   Digital Compactness Measurement (DCM). Based on the assumption that the communication cost is proportional to the minimum bounding circle that covers $GR$, the ratio of the $GR$ area to the area of the smallest circumscribing circle, denoted by DCM, is adopted to measure the compactness of $GR$. Generally, the high compactness of the $GR$ is helpful in reducing communication costs. The challenge is to make DCM as close to 1 as possible.

The goal of our scheme is firstly to reduce communication cost and improve the success rate of task assignment when constructing $GR$ for a single task, which requires suitable strategy of cell selection. The utility function involving worker count and worker-task distance is usually used in previous schemes, such as G-GR. It selects a neighboring cell with the maximum utility in each step, which would makes the number of cells in $GR$ as small as possible. Indeed, in the two-level grids structure, the difference of worker counts between cells is often small. For the neighboring level-2 cells, cell-task distances are close to each other, but the gaps on area are often very large, even dozens of times, while the utility function ignores the influence of the area. This will inevitably increase communication overhead. For this reason, we consider to harness quality scoring function derived from the exponential mechanism which comprehensively takes all of the three factors into account. We compare the effects of utility function and quality scoring on Yelp (Ye.) dataset, see Fig. 4. Both functions $f_{s}$ and $f_{d}$ are assigned as linear mappings to $[1,10]$ based on series of experiments. For more detailed experimental settings, see Section 6.1.

From the perspective of the quality scoring function versus the utility function, experimental results on real-time data show that the G-GS (using scoring) performs a little better than G-GR (using utility), and G-GS improves $3.1\%$, $1.1\%$, $1.2\%$ and $2.9\%$ on WTD, HOP, ANW and DCM, respectively. This has no increase on ASR, while both of the new schemes with historical data learning, G-HS and G-HU, have $4.0\%$ increase on ASR. The G-HS (using scoring) maintains the above advantages on the above four indexes, since G-GS and G-HS prefer small cells with high worker density. The above analysis reflects fully the advantages of quality scoring function strategy.

From the perspective of using historical data, it can be seen that G-HS and G-HU (with historical data) have higher ASR than $EU$, while most of results for G-GS and G-GU failed to meet $EU$. Indeed, some negative noises in level-2 cells reduce worker count to be less than 0 and the cells’ utility is usually set zero. In the $GR$ construction stage, the cells with a high noisy count are preferred which makes that more cells with positive noise are selected into $GR$ in probability and more positive virtual counts generate. Then the noisy utility of $GR$ is generally higher than the real value. In other words, when the noisy $U$ reaches $EU$, sometimes the real $U$ may not. As for using historical data learning, the zero allocation of privacy budget in the level-2 partition makes the (counting) noise scale smaller, the deviation between noisy and real $U$ is smaller so that the (real) ASR increases naturally. By the comparison of G-HS_Ad (adjusting $EU$ of G-HS point by point to make its ASR value close to that of G-GS) to G-GS, we find out that in the average sense the indexes, WTD, HOP, ANW and DCM using historical data are $3.7\%$, $6.4\%$, $3.9\%$ and $3.7\%$ better than those using real data, respectively.

In order to improve the compactness of $GR$, we set a local maximum geocast radius $r_{\rm loc}$ by adaptive search when selecting cells. We consider all cells in Local Maximum Geocast Reigon (LGR) as a whole, calculate the average distance by weighting with the absolute value of noisy counts, and then estimate the utility of the area. The initial value of $r_{\rm loc}$ is the average distance from the task to the four corners of the cell covering the task, and it increases with the fixed step that equals half the width of the smallest cell in whole domain, until the approximate utility reaches $EU$. The algorithm for finding $LGR$ is shown in Algorithm 2.

We consider the effect of the $LGR$ trick by performing experiments on NYTaxi (Ta.) dataset, and the results are shown in Fig. 5.

From the comparisons of R-GS (with LGR trick) to G-GS, and R-HS (with LGR trick) to G-HS, respectively, we observe that applying $LGR$ does not obviously weaken the ASR. However, it performs effectively on other metrics, especially improves $13.9\%$ and $19.3\%$ (WTD), $3.5\%$ and $5.1\%$ (HOP), $5.0\%$ and $6.8\%$ (ANW), $12.3\%$ and $19.1\%$ (DCM), respectively, with the privacy budget of 1.0. After adjusting the $EU$ to make the ASR of the four schemes approximately the same, the advantage of the R-HS is more prominent on the metrics. Compared with R-GS, R-HS improves $5.0\%$, $5.6\%$, $6.8\%$ and $3.0\%$, respectively. In Section 6, a series of experiments will demonstrate the effects of our budget allocation strategy with partition simulation by historical data learning from multiple perspectives.

As is mentioned in Section 5.1, adding noise generates some negative cells (where noisy count of workers is negative) which have no contributions on utility. For this, we set a ”Break” strategy. Except for the initial cell that covers task $t$, when the alternative neighboring cells are all non-positive, the current $GR$ are returned directly. We focus on the ”Break” strategy with experiments on the Gowalla (Go.) dataset, and the results are given in Fig. 6.

It can be seen from the CELL index (number of cells in $GR$) that with application of ”Break” strategy the CELL is reduced by $1.0\%$ without causing a significant decrease in ASR. This indicates that the real utility contribution of so-called negative cell is relatively small in the average sense. Besides, the WTD and HOP are reduced by about $0.4\%$ and $0.3\%$, respectively.

In this section, we focus on the analysis of privacy budget allocation and protection in the whole system framework. The budget allocation is detailed as in Fig. 7.

Firstly, due to the nature of unbounded DP, we have to allocate a small fraction of privacy budget to noisy count of the total locations in the domain for level-1 partition.

Secondly, for level-2 partition we employ historical data learning to make sampling simulation of current distribution. Usually the prediction by learning of historical locations has correlation of real-time data no matter whether noises are added on original data. For this, we use the probability distribution determined by the predicted proportion on counts to perform random sampling (i.i.d.), which achieves a nice simulation of current distribution without privacy costs. Such a method helps us learn the overall distribution of locations in the statistical sense. Based on the sampled points (only used for local counting) generated independently, any adversary can not guess which (level-1) cell a specific worker is currently located in. Moreover, the level-2 partition costs no privacy budget.

Thirdly, in the $GR$ construction stage, real-time data is imported into the partitioned grid, and Laplace noise of main privacy budget is added to each level-2 cell in parallel.

Finally, the involved learning on historical data, “Break” strategy and $LGR$ operations suit the characteristics of post-processing (Theorem 3), and the whole system scheme satisfies $\epsilon$-DP protection.

Experimental comparison. Historical data learning technique has been proved to provide relatively high predictive accuracy [21, 20]. In order to verify the system quality of the proposed R-HT scheme, we carry out a series of experiments to compare it with the GDY [4], G-GR [6] and G-GS. Indeed, the G-GS scheme is modified from G-GR, where the utility rule is replaced by quality scoring for cell selections.

These privacy frameworks are achieved based on the notion of unbounded DP. Then the sensitivity of workers’ count in each grid (or region) is $1$, that is, while the maximum increase or decrease is 1 for the total number of workers, such a change may occur in any cell [28]. Compared with unbounded DP, the sensitivity in bounded DP case is $2$, and the increase of noise scale would significantly affect the success rate of task assignment.

Selection of Datasets. We use three real datasets: NYTaxi (NYC’s Taxi Trip Data), Gowalla and Yelp.

NYTaxi is a New York taxi location dataset. We extract taxi pickup positions in New York City during 21 days, May 1 to 21, 2013. The first 20 days are used as historical data, and 27,165 positions on May 21 as real-time data. Each pickup position is modeled as a worker position in spatial crowdsourcing (SC). Since most of the taxi pickup positions are distributed on the city’s main roads, in order to better simulate the actual positions of workers, we randomly and uniformly blur each position into a circle centered at the current position and with the radius (Blur Radius, BR) of 80 meters.

Gowalla is a social network check-in dataset. We extract the check-in locations for 42 days from September 5 to October 16, 2010. Due to the large geographic span of data, we reduce the geographical distance by a ratio of $1:280$. Every two days are regarded as a period, and the last period includes 6,736 location points for real-time data. Each restaurant location is modeled as a worker position in SC, and the BR is 250 meters.

Yelp corresponds to some data of the Phoenix area of Arizona. We take location data from March 2014 to August 2017 and assign 2 months as a period. The last period with 17,730 locations was used as real-time data. We also model the location of each restaurant as a worker position in SC, BR is 600 meters.

We can set scenes for the above three datasets separately. NYTaxi dataset can be regarded as a taxi ordering scene in the downtown. The maximum distance for taxi drivers to perform orders is 500 m. $MTD$ is 300 m, usually equal to $90\%$ of $MCD$ which is determined by Eq. (7). For Gowalla, we can consider a takeaway booking scenario in which the maximum order distance is 2 km, and then the $MTD$ is 1.2 km. Yelp can be a model of an auto repair scenario. The maximum order distance is 5 km and $MTD$ is 3 km. Besides, 2,000 positions are randomly and uniformly selected from the worker positions as task points. The relevant parameters of the datasets are shown in Table II.

In our experimental settings, privacy budget $\epsilon\in\{0.2,~{}0.4,~{}0.6,~{}0.8,~{}1.0\}$, expected utility $EU\in\{0.6,~{}0.7,~{}0.8,~{}0.9\}$, and maximum task acceptance probability $MAR\in\{0.05,~{}0.1,~{}0.15,~{}0.2,~{}0.25\}$. The default values for $\epsilon$, $EU$ and $MAR$ are set to 0.5, 0.9 and 0.1, respectively. The functions $f_{s}$ and $f_{d}$ involved in quality scoring function are linear mappings to $[1,10]$ from the interval between minimum and maximum areas of cells, and between the half length of diagonal line in the minimal cell and $MTD$, respectively.

The utility loss caused by DP can be seen more intuitively by performing a non-privacy scheme, which constructs $GR$ by selecting workers closest to the task one by one within the $MTD$ reigon. The HOP value of $GR$ is defined as the distance between the two farthest workers. As for GDY and G-GR, in order to avoid the influence of the randomness of noise on partitioning, we carry out the whole process 50 times to obtain 50 groups of results and get their average values. For R-HT, the simulation process of grids partition is independently executed 10 times, which results in 10 groups of partitioned grids. The real-time location counting noise in each level-2 cell is randomly added for 20 times separately, and then a total of 200 PSD snapshots are generated. For all schemes, 2000 single-task assignments are performed on each map, regardless of possible conflicts between task assignments, so as to obtain stable results of performance evaluation of each scheme under this scenario (single worker requested for single task). Next, we investigate the effects of varying privacy budget, $MAR$ and expected utility, respectively, and also evaluate $LGR$-based heuristics and the running time of the schemes for feasibility.

In this section, we evaluate the performance of R-HT and some closely related schemes on three datasets by varying parameters, including privacy budget $\epsilon$, maximal acceptance rate $MAR$, and expected utility $EU$. Performance is measured by the five main metrics presented in Section 4.4.

Experimental results illustrate that $LGR$ strategy improves the schemes as is mentioned in Section 5.2. However, we find that the local radius $r_{\rm loc}$ computed by Algorithm 2 is sometimes too large. Indeed, in the $GR$ construction stage, the proportion that the whole $LGR$ cells are still not enough for reaching $EU$, for adopting $1.0\,r_{\rm loc}(0.0\%)$, $0.9\,r_{\rm loc}(2.1\%)$ and $0.88\,r_{\rm loc}(4.3\%)$ is very low. We perform the R-HT schemes with 0.9$r_{\rm loc}$ and 0.88$r_{\rm loc}$, respectively, to compare with the improved hybrid scheme of the G-GR. The experimental results on Gowalla are shown in Fig. 11.

When local radius $r_{\rm loc}$ is reduced, the ASR of R-HT decreases naturally. Indeed, with the reduction of $r_{\rm loc}$, there are more tasks whose ASR can not achieve $EU$. In the case of $0.88\,r_{\rm loc}$, most ASR values for Gowalla can still reach $EU$, while the adoption of the G-GR_hybrid scheme does not improve obviously the ASR of G-GR. $0.88$R-HT has a clear advantage in WTD, $12.4\%$ smaller than G-GR_hybrid on average. As for HOP, although the two schemes are entangled to each other, $0.88$R-HT still leads $0.3\%$ overall. On the ANW, $0.88$R-HT is a bit higher due to the higher ASR. Further, On DCM $0.88$R-HT gradually loses the advantage, which is mainly related to the utility function of G-GR_hybrid, defined by

where $\alpha=0.3$, $u$ represents the task acceptance probability of cell $s$, and $Comp$ is the DCM of $GR$ with cell $s$ included. As $\epsilon$ increases, the DCM weight in the utility function becomes larger. When $\epsilon$ is equal to 1.0, the utility function only depends on DCM.

By comparing with non-privacy algorithm, we can observe that non-privacy has obvious advantages in WTD and HOP because it has no grids. On ANW, we can see that 0.88R-HT, G-GR and G-GR_hybrid are close to the non-privacy scheme when $\epsilon$ equals 1.0, which indicates that the three schemes behave well on reducing ANW, and among them the ASR of 0.88R-HT is the highest at this point.

Besides, we mention that To et al. [6] proposed a partial cell selection based on G-GR to deal with the ASR overflow problem when adding the last cell to $GR$, which reduces system overhead to some extent. However, due to the severe challenge that the actual ASR fails to reach $EU$, the partial cell selection undoubtedly aggravates this trouble, which is demonstrated by our various experiments. Therefore, the partial cell strategy in R-HT is not skipped in this paper.

In real life, despite the success rate of task assignment and communication cost, the time costs from task request to GR release is also very important. We divided the entire assignment process of a single task into two major stages. The first stage is the domain partitioning (stage A), which includes the partitioning and adding noise to the number of real-time workers. Due to using historical data, this stage can be divided into the following two parts: Partitioning with noisy historical data (Stage A1); Then, updating real-time data and adding noise to the count of workers in level-2 cells (Stage A2). The second stage is the $GR$ construction stage (Stage B).

We consider the following three comparisons in terms of time consuming: First, the entire process (A+B), which means the running time of the entire algorithm; Second, updating real-time count in each cell and constructing $GR$ (A2+B) with fixed grids, which is applicable to scenarios where the real-time data changes greatly in a period and we need only to upload real-time data for updating $GR$; Third, constructing $GR$ after updating real-time data (B).

We use Python 2.7 on Windows 10 (2.4 GHZ Intel i5 CPU, 8G RAM) to run 2,000 tasks on 3 datasets, and calculate each time cost by taking the average of 10 cycles, see Table III.

It can be seen in the table that in stage B, R-HT takes a relatively long time, because R-HT needs to calculate $r_{\rm loc}$, cell’s utility and cell’s score. For Stage A2+B, compared with stage B, updating data and adding noise only takes a very small period of time (less than 1 ms), and there is no data updates in G-GR after partitioning. In Stage A+B, The time consumption in partitioning is far greater than that in $GR$ construction, mainly due to the fact that the process of historical data prediction costs much time in R-HT.

However, our scheme is very suitable for the case that workers move rapidly, as is mentioned in Section 4.1. Fix the grids and update real-time locations. This saves much on running time (A2+B) compared with G-GR on A+B.

In a word, the running time of a single task on the three datasets is within 3 seconds, which forms an approximate direct proportion with the total count of real-time data, which guarantees the timeliness and practicability of task release in real life.