Sleeping on the job: energy-efficient and robust broadcast for radio networks

ABSTRACT

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 that 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 Θ(√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, all awake nodes within L_∞ distance r receive the message. In this model, up to t< r/2 (2r+1) nodes within any 2r+1 by 2r+1 square in the grid can suffer Byzantine faults. Moreover, we assume that the nodes that suffer Byzantine faults are chosen and controlled by an adaptive adversary that knows everything except for the random bits of each non-faulty node. This type of adaptive adversary models worst-case behavior due to malicious attacks on the network; mobile nodes moving around in the network; or static nodes losing power or ceasing to function. Let n=r(2r+1). We show how to solve the broadcast problem in this model with each node awake only an expected O(1/√n) fraction of the time. Moreover, if we allow each node to send O(log* n) times, we can increase the energy savings so that each node is awake only an expected O((log* n)/ n) fraction of the time. This compares favorably with previous protocols that required each node to be awake for every time step.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: Trevor Armstrong. Wake-up based power management in multi-hop wireless networks. www.eecg.toronto.edu/~trevor/Wakeup/index.html.
• 3: Vartika Bhandari , Nitin H. Vaidya, On reliable broadcast in a radio network, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073841]
• 4: Vartika Bhandari , Nitin H. Vaidya, On reliable broadcast in a radio network, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073841]
• 5: Chiu-Yuen Koo , Vartika Bhandari , Jonathan Katz , Nitin H. Vaidya, Reliable broadcast in radio networks: the bounded collision case, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146420]
• 6: Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Space- and time-efficient deterministic algorithms for biased quantiles over data streams, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142389]
• 7: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Frequency Estimation of Internet Packet Streams with Limited Space, Proceedings of the 10th Annual European Symposium on Algorithms, p.348-360, September 17-21, 2002
• 8: Laura~Marie Feeney and Martin Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In Proceedings of IEEE INFOCOM, 2001.
• 9: Sudipto Guha , Andrew McGregor, Approximate quantiles and the order of the stream, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142390]
• 10: Sudipto Guha and Andrew McGregor. Lower bounds for quantile estimation in random-order and multi-pass streaming. In Proceedings of the $34^th$ International Colloquium on Automata, Languages and Programming, 2007.
• 11: Monika Henzinger, Prabhaker Raghavan, and Sridar Rajagopalan. Computing on data streams. Technical Report SRC-TN-1998-011, Digital Systems Research Center, 1998.
• 12: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 13: Chiu-Yuen Koo, Broadcast in radio networks tolerating byzantine adversarial behavior, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011807]
• 14: Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theoretical Computer Science, pages 315--323, 1980.
• 15: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 16: Jared Saia , Maxwell Young, Reducing communication costs in robust peer-to-peer networks, Information Processing Letters, v.106 n.4, p.152-158, May, 2008 [doi>10.1016/j.ipl.2007.11.004]
• 17: Lan Wang , Yang Xiao, A survey of energy-efficient scheduling mechanisms in sensor networks, Mobile Networks and Applications, v.11 n.5, p.723-740, October 2006 [doi>10.1007/s11036-006-7798-5]
• 18: Qin Wang, Mark Hempstead, and Woodward Yang. A realistic power consumption model for wireless sensor network devices. In Proceedings of the Third Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2006.
• 19: Andrew Chi-Chin Yao, Probabilistic computations: Toward a unified measure of complexity, Proceedings of the 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), p.222-227, September 30-October 31, 1977

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Reliability

Keywords:
broadcast, byzantine failure, data streaming, energy efficient, fault tolerance, power aware, radio networks