Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

One major concern in pervasive wireless applications is location privacy, where malicious eavesdroppers, based on static device identifiers, can continuously track users. As a commonly adopted countermeasure to prevent such identifier-based tracking, devices regularly and simultaneously change their identifiers in special areas called mix-zones. Although mix-zones provide spatio-temporal de-correlations between old and new identifiers, pseudonym changes, depending on the position of the mix-zone, can incur a substantial cost on the network due to lost communications and additional resources such as energy. In this paper, we address this trade-off by studying the problem of determining an optimal set of mix-zones such that the degree of mixing in the network is maximized, whereas the overall network-wide mixing cost is minimized. We follow a graph-theoretic approach and model the optimal mixing problem as a novel generalization of the vertex cover problem, called the Mix Cover (MC) problem. We propose three bounded-ratio approximation algorithms for the MC problem and validate them by an empirical evaluation of their performance on real data. The combinatorics-based approach followed here enables us to study the feasibility of determining optimal mix-zones regularly and under dynamic network conditions.

Published in:
Proceedings of the 16th European Symposium on Research in Computer Security (ESORICS), 548-567
Presented at:
16th European Symposium on Research in Computer Security (ESORICS), Leuven, Belgium, September 12-14, 2011
Berlin, Springer

 Record created 2011-05-23, last modified 2019-12-05

JadliwalaBH2011ESORICS - Download fulltextPPTX
jadliwala-esorics-final - Download fulltextPDF
Rate this document:

Rate this document:
(Not yet reviewed)