Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks
We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a Theta (root n) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log*n) times (i.e. in O(log*n) rounds each consisting of the n time slots), then listening to O(log*n) expected number of time slots suffices. We show that this is near optimal. We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L-infinity distance r receive m. In this model, up to t   0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log* n) times, we achieve reliable broadcast with each node sending O(n log(2) vertical bar m vertical bar + (log* n)vertical bar m vertical bar) bits and receiving an expected O(n log(2)vertical bar m vertical bar+(log*n)vertical bar m vertical bar) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log*n) time slots. Our results compare favorably with previous protocols that required each node to send Theta (vertical bar m vertical bar) bits, receive Theta (n vertical bar m vertical bar) bits and be awake for Theta (n) time slots.
radio networks bad santa reliable broadcast fault tolerance byzantine