Real-time, reliable and privacy-aware mobile crowdsourcing: algorithms and practical systems

Abstract

The recent massive prevalence of mobile devices along with the advances in mobile networking have led to the development of "Mobile Crowdsourcing Systems". In these systems the ubiquitous human users participate actively in data collection and sharing in order to identify events of interest in real-time. The data contributed by the participants in mobile crowdsourcing can be either extracted from the sensors which are embedded on the users' mobile devices or obtained by asking questions to the ubiquitous human users. Such information can be can be used to identify events of interest in real-time in a wide range of application domains from entertainment, to transportation, to environmental monitoring. Mobile Crowdsourcing is a novel application paradigm that reflects unique opportunities mainly due to: (i) the ubiquity of the users, (ii) the low-cost and easy to deploy infrastructure, (iii) the dynamic nature of the queries and (iv) the various connectivity media such as 3G, 4G, and WiFi. However, there exist several important challenges that need to be addressed in order to use Mobile Crowdsourcing systems in their full potential. These challenges include, but are not limited to, extracting data from appropriate users to maximize the information gain, privacy protection of the participants, dealing with real-time challenges and response delays, quality assessment of the collected data, data unavailability and effectively incentivizing people to participate. The purpose of this thesis is to propose practical methods to address some of these issues so as to improve Mobile Crowdsourcing Systems. The first part of the thesis improves Mobile Crowdsourcing Systems by tackling the problem of assigning crowdsourcing tasks to the most appropriate users in order to maximize the benefit for the task requester. The problem is difficult since human users have different skills and behaviors that depend on the human factor, such as objectiveness, reliability and response delays which are often difficult to estimate in advance. Hence, selecting the most appropriate users for each task in real-time is a challenging problem. This thesis first contributes to this problem by providing an approach that assigns each incoming task to the most appropriate group of human workers taking into account their reliability and real-time performance. The proposed system systematically investigates the search space for Pareto optimal solutions with respect to the defined objectives. The algorithm executes in polynomial time and improves the amount of tasks processed under the defined constraints over 71% compared to the state-of-the-art approaches like Amazon Mechanical Turk. Then, we focus on the problem of exploiting Mobile Crowdsourcing to detect ongoing events effectively and in real-time. The problem is that querying every available user is infeasible due to the volume and costs of crowdsourcing. Thus, we should be able to identify and query the optimal sample out of the available users. In this thesis we contribute to mobile crowdsourcing with a set of event detection approaches. Our first approach uses a novel sampling algorithm that selects a subset of the ubiquitous human users to provide real-time information so as to identify the state of a major emergency event. Our proposed approach captures well emergencies in large geographical regions and takes into consideration the individual characteristics of the human users to maximize the probability of receiving accurate responses in a timely manner. Our second approach exploits the sensor-based readings of the mobile devices of the users to extract important events with minimal cost. The proposed approach determines clusters of users dynamically to identify the locations where important events take place and then performs sampling to retrieve the most representative data streams in every cluster to extract additional information for the event. In the second part of the thesis we contribute on the problem of preserving user privacy. The problem relies on the fact that mobile crowdsourcing systems require from the users to share location-embedded information that can lead to exposing private user information. Hence, sophisticated attacks can expose sensitive information such as the user identity and the places that the user visits frequently. First, we contribute with a distributed data exchange approach that aims to protect the user sensitive data by making the attacker consider all user trajectories as equiprobable to contain sensitive data, so that the leak of sensitive data is prevented. Second, we examine to the privacy effect that arises when the anonymous user mobility traces can be linked with publicly available data and reveal personal user information that was not available in advance. For this problem we present an approach that uses a novel feature-based Entity Resolution technique to determine similar user identities and react to preserve user privacy on the shared data. Finally, another privacy problem arises when users share publicly geo-located information through crowdsourcing applications. The issue is that the majority of the data will reside along routes mostly visited by the individuals. Hence, as the amount of user-contributed content increases, they gradually expose the user's mobility. We address this problem with a highly-efficient privacy preserving approach for Crowdsourcing applications that runs locally on mobile devices. The approach relies on the geometric approximation solution of coresets to preserve user privacy, by evaluating the privacy exposure of the users before sharing their geo-located data. Throughout the thesis, our methodologies have been evaluated on real-world datasets and scenarios. Our experimental results have shown that our proposed algorithms systematically outperform the competing approaches and that they constitute practical approaches which can be employed in commercial Mobile Crowdsourcing Systems.

Η πρόσφατη μαζική ανάπτυξη των κινητών συσκευών μαζί με τις προόδους στον τομέα των κινητών δικτύων έχουν οδηγήσει στην ανάπτυξη των Συστημάτων Εξόρυξης Δεδομένων από Χρήστες Κινητών Συσκευών (Mobile Crowdsourcing Systems). Σε αυτά τα συστήματα οι πανταχού παρόντες ανθρώπινοι χρήστες συμμετέχουν ενεργά στη συλλογή και την ανταλλαγή δεδομένων, προκειμένου να προσδιοριστούν διάφορα γεγονότα σε πραγματικό χρόνο. Τα δεδομένα που συνεισφέρουν οι συμμετέχοντες σε αυτά τα συστήματα μπορεί είτε να προέρχονται από τους αισθητήρες που είναι ενσωματωμένοι στις κινητές συσκευές τους ή να λαμβάνονται μέσω ερωτήσεων προς τους πανταχού παρόντες ανθρώπινους χρήστες. Οι πληροφορίες αυτές στη συνέχεια μπορούν να χρησιμοποιηθούν για να προσδιοριστούν διάφορα γεγονότα σε πραγματικό χρόνο σε ένα αρκετά ευρύ φάσμα εφαρμογών όπως σε εφαρμογές ψυχαγωγίας, συγκοινωνιών και παρακολούθησης του περιβάλλοντος. Τα συστήματα εξόρυξης δεδομένων από χρήστες κινητών συσκευών αποτελούν ένα νέο πρότυπο εφαρμογών που προσφέρουν κάποια πολύ σημαντικά πλεονεκτήματα εξ' αιτίας: (i) της πανταχού παρουσίας των χρηστών, (ii) το χαμηλό κόστος και την εύκολη εγκατάσταση, (iii) τη δυναμική φύση των ερωτημάτων και (iv) τα διάφορα μέσα συνδεσιμότητας όπως τα 3G, 4G, και WiFi. Ωστόσο, υπάρχουν αρκετές σημαντικές προκλήσεις που πρέπει να αντιμετωπιστούν, προκειμένου να χρησιμοποιηθούν τα συστήματα αυτά στο μέγιστο των δυνατοτήτων τους. Οι προκλήσεις αυτές περιλαμβάνουν, χωρίς να περιορίζονται σε αυτές, την εξαγωγή δεδομένων από κατάλληλους χρήστες ώστε να μεγιστοποιηθεί το όφελος από τα δεδομένα που εξάγονται από τους χρήστες, την προστασία της ιδιωτικής ζωής των συμμετεχόντων, την αντιμετώπιση των προκλήσεων που σχετίζονται με ζητήματα εκτέλεσης σε πραγματικό χρόνο και τις καθυστερήσεις απόκρισης, την αξιολόγηση της ποιότητας των δεδομένων που συλλέγονται, την πιθανότητα μη διαθεσιμότητας των δεδομένων και την αποτελεσματική παροχή κινήτρων για τους χρήστες ώστε να συμμετέχουν. Ο σκοπός αυτής της διατριβής είναι να προτείνει πρακτικές μεθόδους για την αντιμετώπιση ορισμένων από αυτά τα ζητήματα έτσι ώστε να βελτιωθούν τα συστήματα εξόρυξης δεδομένων από χρήστες κινητών συσκευών. Το πρώτο μέρος της διατριβής βελτιώνει τα συστήματα εξόρυξης δεδομένων από χρήστες κινητών συσκευών με την αντιμετώπιση του προβλήματος της ανάθεσης εργασιών στους πιο κατάλληλους χρήστες ώστε να μεγιστοποιηθεί το όφελος του αιτούντα των δεδομένων. Το πρόβλημα είναι δύσκολο δεδομένου ότι οι χρήστες έχουν διαφορετικές ικανότητες και συμπεριφορές που εξαρτώνται από τον ανθρώπινο παράγοντα, τα οποία είναι δύσκολο να εκτιμηθούν εκ των προτέρων. Ως εκ τούτου, η επιλογή των καταλληλότερων χρηστών για κάθε εργασία σε πραγματικό χρόνο είναι ένα δύσκολο πρόβλημα. Αυτή η διατριβή συμβάλλει σε αυτό το πρόβλημα, παρέχοντας μια προσέγγιση η οποία αναθέτει κάθε εισερχόμενη εργασία στην πιο κατάλληλη ομάδα χρηστών, λαμβάνοντας υπόψη την αξιοπιστία τους και τον χρόνο απόκρισης. Το προτεινόμενο σύστημα ερευνά συστηματικά το χώρο των εφικτών λύσεων αναζητώντας τις βέλτιστες λύσεις (Pareto optimal) σε σχέση με τους καθορισμένους στόχους. Ο αλγόριθμος εκτελείται σε πολυωνυμικό χρόνο και βελτιώνει τον αριθμό των εργασιών που εκτελούνται στο πλαίσιο των καθορισμένων περιορισμών πάνω από 71% σε σύγκριση με τις υπάρχουσες προσεγγίσεις. Στη συνέχεια, έχουμε επικεντρωθεί στο πρόβλημα της εκμετάλλευσης των συστημάτων εξόρυξης δεδομένων από χρήστες κινητών συσκευών για τον εντοπισμό εν εξελίξει γεγονότων αποτελεσματικά και σε πραγματικό χρόνο. Το πρόβλημα είναι ότι το να ζητήσουμε πληροφορίες από κάθε διαθέσιμο χρήστη είναι ανέφικτο λόγω του όγκου των χρηστών και του χρηματικού κόστους για το σύστημα. Έτσι, θα πρέπει να είμαστε σε θέση να ζητήσουμε πληροφορίες από το βέλτιστο δείγμα διαθέσιμων χρηστών. Αυτή η διατριβή συμβάλλει στα συστήματα εξόρυξης δεδομένων από χρήστες κινητών συσκευών με ένα σύνολο τεχνικών για την ανίχνευση συμβάντων. Η πρώτη μας προσέγγιση χρησιμοποιεί ένα νέο αλγόριθμο δειγματοληψίας που επιλέγει ένα υποσύνολο των χρηστών για να συνεισφέρουν με πληροφορίες σε πραγματικό χρόνο, έτσι ώστε να προσδιορίσει η κατάσταση για ένα γεγονός έκτακτης ανάγκης. Η προτεινόμενη προσέγγιση αναγνωρίζει καταστάσεις έκτακτης ανάγκης σε μεγάλες γεωγραφικές περιοχές και λαμβάνει υπόψη τα ατομικά χαρακτηριστικά των ανθρώπινων χρηστών για να μεγιστοποιήσει την πιθανότητα να εξάγει ακριβείς απαντήσεις σε εύθετο χρόνο. Η δεύτερη προσέγγιση μας εκμεταλλεύεται τους αισθητήρες των κινητών συσκευών των χρηστών ώστε να εξάγει τα σημαντικά γεγονότα με ελάχιστο κόστος. Η προτεινόμενη προσέγγιση καθορίζει συστάδες χρηστών δυναμικά για να εντοπίσει τα σημεία όπου λαμβάνουν χώρα σημαντικά γεγονότα και στη συνέχεια εκτελεί δειγματοληψία για να ανακτήσει τα πιο αντιπροσωπευτικά ρεύματα δεδομένων σε κάθε συστάδα έτσι ώστε να εξάγει πρόσθετες πληροφορίες για κάθε γεγονός. Το δεύτερο μέρος της διατριβής συμβάλλει στο πρόβλημα της διατήρησης της ιδιωτικής ζωής των χρηστών. Το πρόβλημα έγκειται στο γεγονός ότι τα συστήματα εξόρυξης δεδομένων από χρήστες κινητών συσκευών συχνά απαιτούν από τους χρήστες να μοιράζονται με την κοινότητα πληροφορία που ενσωματώνει την γεωγραφική τοποθεσία τους, το οποίο μπορεί να οδηγήσει στην έκθεση της ιδιωτικής τους ζωής. Ως εκ τούτου, συγκεκριμένες επιθέσεις μπορεί να εκθέσουν ευαίσθητες πληροφορίες, όπως η ταυτότητα του χρήστη και οι γεωγραφικές τοποθεσίες που ο χρήστης επισκέπτεται συχνά. Η διατριβή αρχικά συμβάλει με μία κατανεμημένη προσέγγιση ανταλλαγής δεδομένων που έχει ως στόχο την προστασία των ευαίσθητων δεδομένων του χρήστη, κάνοντας τον εισβολέα να θεωρήσει όλες τις διαδρομές των χρηστών ως ισοπίθανες να περιέχουν ευαίσθητα δεδομένα, έτσι ώστε να εμποδιστεί η διαρροή ευαίσθητων δεδομένων. Δεύτερον, εξετάζουμε την πιθανότητα έκθεσης της ιδιωτικής ζωής των χρηστών που προκύπτει όταν οι ανώνυμες διαδρομές μπορούν να συσχετιστούν με δημόσια διαθέσιμα δεδομένα, αποκαλύπτοντας προσωπικές πληροφορίες των χρηστών που δεν ήταν διαθέσιμες εκ των προτέρων. Για το πρόβλημα αυτό παρουσιάζουμε μια προσέγγιση που βασίζεται στην τεχνική ανάλυση για τον προσδιορισμό δεδομένων με κοινή ταυτότητα και αντιδρά ώστε να διατηρήσει της ιδιωτικότητα των χρηστών. Τέλος, ένα άλλο πρόβλημα της ιδιωτικής ζωής προκύπτει όταν οι χρήστες μοιράζονται δημοσίως πληροφορίες συσχετισμένες με τη γεωγραφική τους θέση μέσω διάφορων εφαρμογών. Το θέμα είναι ότι η πλειοψηφία των πληροφοριών βρίσκονται στις διαδρομές που οι χρήστες επισκέπτονται συχνά. Ως εκ τούτου, καθώς η ποσότητα των δεδομένων για κάθε χρήστη αυξάνεται, σταδιακά αρχίζει να εκθέτει την κινητικότητα του χρήστη. Σε αυτή τη διατριβή έχουμε αντιμετωπίσει αυτό το πρόβλημα με μια ιδιαίτερα αποδοτική προσέγγιση που τρέχει τοπικά σε κινητές συσκευές. Η προσέγγιση στηρίζεται στη γεωμετρική λύση των coresets για να διατηρήσει την ιδιωτική ζωή των χρηστών, αξιολογώντας την έκθεση των προσωπικών δεδομένων τους πριν από την δημοσίευση των πληροφοριών. Καθ' όλη την διατριβή, οι μεθοδολογίες που αναπτύχθηκαν έχουν αξιολογηθεί σε πραγματικά δεδομένα και σενάρια. Τα πειραματικά αποτελέσματα έδειξαν ότι οι προτεινόμενοι αλγόριθμοι ξεπερνούν συστηματικά τις υπάρχουσες προσεγγίσεις και αποτελούν πρακτικές τεχνικές που μπορούν να χρησιμοποιηθούν σε πραγματικά συστήματα.