Abstract
Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular identifier change operations in special areas called mix-zones. Although mix-zones provide spatio-temporal de-correlation between old and new identifiers, depending on the position of the mix-zone, identifier changes can generate a substantial inconvenience (or “cost”) to the users in terms of lost communications and increased energy consumption. In this paper, we address this trade-off between privacy and cost by studying the problem of determining an optimal set of mix-zones such that the degree of mixing in the network is maximized and the overall network-wide mixing cost is minimized. We follow a graph-theoretic approach and model the optimal mixing problem as a generalization of the vertex cover problem, called the Mix Cover (MC) problem. We propose three approximation algorithms for the MC problem and derive a lower bound on the solution quality guaranteed by them. Additionally, we outline two other heuristics for solving the MC problem. These heuristics are simple, but do not provide any guarantees on the solution quality. By means of extensive empirical evaluation using real data, we compare the performance and solution quality of these algorithms. The combinatorics-based approach used in this work enables us to study the feasibility of determining optimal mix-zones regularly and under dynamic network conditions.