Routing through noise and sleeping nodes in sensor networks: latency vs. energy trade-offs

We consider wireless sensor networks with nodes switching "ON" (awake) and "OFF" (sleeping) to preserve energy, and transmitting data over channels with varying quality. The objective is to determine the best path from each node to a single gateway. Performance metrics of interest are: the expected energy consumption for transmissions and the probability that the latency exceeds a certain threshold. Under Markovian assumptions on the sleeping schedules and the channel conditions, we obtain the expected energy consumption of transmitting a packet on any path to the gateway. We also provide a tight large deviations asymptotic for the latency probability on each path. To capture the trade-off between energy consumption and latency probability we formulate the problem of choosing a path to minimize a weighted sum of the expected energy consumption and the exponent of the latency probability. We provide two algorithms to solve this problem: a centralized stochastic global optimization algorithm and a distributed algorithm based on simulated annealing