Exploring the Tight Asymptotic Bounds of the Trade-off Between Query Anonymity & Communication Cost in Wireless Sensor Network
Mahesh Tripunitara and Gordon Agnew
In this talk, I will discuss my contributions to work on the analysis of the trade-off between query-anonymity and communication-cost in wireless sensor networks. Prior work has observed that such a trade-off exists. In my work, starting with an unconditional notion of query-anonymity, I generalize a prior result for sourcerouted networks with square-grid topologies to source-routed networks in which the topology is a connected undirected graph. Specifically, I establish that the necessary and sufficient communication-cost to achieve query-anonymity asymptotically smaller than the diameter of the network, d, is a function of d only. And that the necessary and sufficient communication-cost to achieve query-anonymity asymptotically larger than d is a function of the desired query-anonymity only. I will discuss also an empirical validation I have done via simulations in TOSSIM, a de facto standard for wireless sensor networks.