Optimal Privacy-Preserving Probabilistic Routing for Wireless Networks

Privacy-preserving routing protocols in wireless networks frequently utilize additional artificial traffic to hide the identities of communicating source-destination pairs. Usually, the addition of artificial traffic is done heuristically with no guarantees that the transmission cost, latency, and so on, are optimized in every network topology. In this paper, we explicitly examine the privacy-utility tradeoff problem for wireless networks and develop a novel privacy-preserving routing algorithm called optimal privacy enhancing routing algorithm (OPERA). OPERA uses a statistical decision-making framework to optimize the privacy of the routing protocol given a utility (or cost) constraint. We consider global adversaries with both lossless and lossy observations that use the Bayesian maximum-a-posteriori (MAP) estimation strategy. We formulate the privacy-utility tradeoff problem as a linear program, which can be efficiently solved. Our simulation results demonstrate that OPERA reduces the adversary's detection probability by up to 50% compared to the random Uniform and Greedy heuristics, and up to five times compared to a baseline scheme. In addition, OPERA also outperforms the conventional information-theoretic mutual information approach.