Privacy-aware routing in sensor networks

A typical sensor network application is to monitor objects, including wildlife, vehicles and events, in which information about an object is periodically sent back to the sink. Many times, the object needs to be protected for security reasons. However, an adversary can detect message flows and trace the message back to its source by moving in the reverse direction of the flows. This paper aims to maximize source location privacy, which is evaluated by the adversary's traceback time, by designing routing protocols that distribute message flows to different routes. First, we give the performance bound for any routing scheme. Then, we present our routing schemes, which maximize the adversary's average traceback time and achieve max-min traceback time given certain energy constraints. We then propose WRS, a suboptimal but practical privacy-aware routing scheme, and provide simulation results. Finally, we extend the discussion to an extreme adversary model, which allows the adversary to deploy an adversary sensor network to monitor the message routing activities. Accordingly, we propose a random schedule scheme to confuse the adversary. To reduce the message delivery time, we give an approximation algorithm for message routing. (C) 2009 Elsevier B.V. All rights reserved.