On the Optimal Placement of Mix Zones

In mobile wireless networks, third parties can track the location of mobile nodes by monitoring the pseudonyms used for identification. A frequently proposed solution to protect the location privacy of mobile nodes suggests to change pseudonyms in regions called mix zones. In this paper, we propose a novel metric based on the mobility profiles of mobile nodes to evaluate the mixing effectiveness of possible mix zone locations. Then, as the location privacy achieved with mix zones depends on their placement in the network, we analyze the optimal placement of mix zones with combinatorial optimization techniques. The proposed algorithm maximizes the achieved location privacy in the system and takes into account the cost on mobile nodes induced by mix zones. By means of simulations, we show that the placement recommended by our algorithm significantly reduces the tracking success by the adversary.