Privacy-aware Task Management for Mobile Crowd Sensing Public

Abstract

Location-aware Mobile crowd sensing (MCS) has numerous applications in

a wide range of domains including syndromic surveillance, crime mapping,

traffic monitoring, and emergency response. Preserving the privacy of participants

in such applications is one of the main challenges in developing effective

task management solutions in MCS. Moreover, the inherent dynamic

environment of MCS characterized by continuous change and inaccurate

participant movement information pose further challenges for coordination

of tasks and participants. Therefore, in this dissertation, we propose novel

methods to build robust task management frameworks to handle uncertainty

and ensure privacy in MCS applications. Our solutions not only increase the

disposition of the participants to engage in data collection and sharing activity,

but also ultimately lead to more effective MCS applications.

Table of Contents

Contents

1 Introduction 1

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Participant Location Privacy . . . . . . . . . . . . . . . . . . . 3

1.1.2 Dynamic MCS Environments . . . . . . . . . . . . . . . . . . 4

1.2 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Privacy-aware Coordinated Spatial Task Assignment (Chapter 3) . . . 5

1.2.2 Private Reverse K-Nearest Queries for Autonomous Spatial Task Selection (Chapter 4) . . . 6

1.2.3 Dynamic Spatial Task Assignment using Uncertain Trajectories (Chapter 5) . . . 7

1.2.4 An Extensive Experimental Evaluation of Location Prediction Models For Moving participants (Chapter 6) . . . 8

2 RelatedWorks 10

2.1 Spatial Task Management in Mobile Crowd Sensing . . . . . . . . . . 10

2.2 Participant Privacy in Spatial Task Management . . . . . . . . . . . . 11

2.2.1 Location-based Privacy Attacks . . . . . . . . . . . . . . . . . 11

2.2.2 Spatio-Temporal Privacy-preserving Methods . . . . . . . . . 13

2.3 Reverse k-nearest neighbor (RkNN) queries . . . . . . . . . . . . . . . 16

2.3.1 RkNN Queries in Exact Databases . . . . . . . . . . . . . . . 16

2.3.2 RkNN Queries on Uncertain Data . . . . . . . . . . . . . . . . 17

2.4 Participant Mobility Modeling and Prediction . . . . . . . . . . . . . 17

3 Spatial Task Assignment for Crowd Sensing with Cloaked Locations 19

3.1 Two-Stage Optimization Approach . . . . . . . . . . . . . . . . . . . 19

3.1.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.2 Formal Two-stage Optimization Objective . . . . . . . . . . . 23

3.1.3 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . 25

3.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.1 First Stage: G-STAC . . . . . . . . . . . . . . . . . . . . . . . 27

3.2.2 Second Stage: L-STAC . . . . . . . . . . . . . . . . . . . . . . 30

3.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3.1 Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 Private Reverse K-Nearest Queries for Autonomous Spatial Task Selection 45

4.1 Problem Definition: Private RkNN Queries . . . . . . . . . . . . . . . 46

4.2 Server-side Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.1 Naive Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2.2 RkNN-HG: Hilbert Grid Indexing . . . . . . . . . . . . . . . . 49

4.2.3 RkNN-HRT: Hilbert R-Tree Indexing . . . . . . . . . . . . . . 50

4.3 Client-side Query Processing . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.1 Pruning Strategies . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.2 Pruning Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 58

4.3.3 Verification Phase . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.3.4 RkNN Query Retrieval Example . . . . . . . . . . . . . . . . . 63

4.3.5 Query Answer Retrieval Modifications for RkNN-HRT . . . . 64

4.4 Query Plan Pre-computation . . . . . . . . . . . . . . . . . . . . . . . 64

4.4.1 Modified Pruning for Query Plan Computation . . . . . . . . 65

4.4.2 Modified Verification for Query Plan Computation . . . . . . 66

4.5 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.5.1 Experimental Methodology . . . . . . . . . . . . . . . . . . . . 67

4.5.2 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.5.3 Parameter Tuning . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.5.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.6 Application of Private RkNN Queries for Autonomous Spatial Task Selection . . . 74

4.6.1 Evaluation Setting . . . . . . . . . . . . . . . . . . . . . . . . 75

4.6.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5 Dynamic Data Driven Crowd Sensing Task Assignment 78

5.1 Dynamic Data Driven Framework For Task Assignment . . . . . . . . 79

5.1.1 Learning Mobility Models . . . . . . . . . . . . . . . . . . . . 80

5.1.2 Adaptive Filtering . . . . . . . . . . . . . . . . . . . . . . . . 82

5.1.3 Uncertain Spatial Task Assignment . . . . . . . . . . . . . . . 84

6 An Extensive Experimental Evaluation of Location Prediction Models For Moving Participants 87

6.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

6.2 Classification of Methods . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.2.1 Personalization . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.2.2 Temporal Representation . . . . . . . . . . . . . . . . . . . . . 90

6.2.3 Spatial Reperesentation . . . . . . . . . . . . . . . . . . . . . 90

6.2.4 Learning Mobility Behavior . . . . . . . . . . . . . . . . . . . 91

6.3 Location Prediction Algorithms . . . . . . . . . . . . . . . . . . . . . 93

6.3.1 Markov Chain Models . . . . . . . . . . . . . . . . . . . . . . 93

6.3.2 Recursive Motion Function . . . . . . . . . . . . . . . . . . . . 94

6.3.3 Hybrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6.3.4 Semi-Lazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

6.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.4.1 Experiment setup . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.4.2 Predictability Analysis . . . . . . . . . . . . . . . . . . . . . . 100

6.4.3 Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7 Conclusions and Future Work 112

7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Bibliography 115

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Computer Science and Informatics
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Computer Science
Mot-clé	Data Privacy Task Management Uncertain Trajectories Mobile Crowd Sensing Mobility Modeling
Committee Chair / Thesis Advisor	Xiong, Li, Emory University Sunderam, Vaidy S, Emory University
Committee Members	Ho, Joyce C, Emory University Shahabi, Cyrus, University of Southern California

Dernière modification

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Privacy-aware Task Management for Mobile Crowd Sensing ()	2018-08-28 15:43:20 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions