Anonymous Location Sharing in Urban Area Mobility

Abstract

This work studies the location-privacy preserving location update in the context of data-centric people mobility applications. The mobility model involves an urban area annotated city network (ACN) over which the users move and record/report their locations at non-regular intervals. The ACN is modeled as a directed weighted graph. Since the data receiver (e.g., an LBS provider) is curious in our privacy model, the users share their locations after anonymization which requires k-member partitioning of the ACN. Our framework, in the offline stage, requires a prototype vertex selection for each of the partitions. To this end, we develop a heuristic to obtain more representative prototype vertices. The temporal dimension of the location anonymity is achieved by two notions of the anonymity models, called weak location k-anonymity (to provide snapshot location anonymity) and strong location k-anonymity (to provide historical location anonymity). The attack scenario models the belief of the attacker (the LBS provider) on the whereabouts of the users at each location update. In the online stage, our algorithms make anonymity violation tests at every location update request and selectively block the anonymity violating ones. The online stage algorithms providing weak/strong location k-anonymity are shown to run in constant time per location update. An extensive experimental evaluation, mainly addressing the issue of privacy/utility trade-off, on three real ACNs with a simulated mobility is presented.