Self-stabilizing leader election for single-hop wireless networks despite jamming

ABSTRACT

Electing a leader is a fundamental task in distributed computations. Many coordination problems, such as the access to a shared resource, and the resulting inefficiencies, can be avoided by relying on a leader. This paper presents Select, a leader election protocol for wireless networks where nodes communicate over a shared medium. Select is very robust in two respects. First, the protocol is self-stabilizing in the sense that it converges to a correct solution from any possible initial network state (e.g., where no or multiple nodes consider themselves a leader). This is an appealing property, especially for dynamic networks. Second, the described protocol is resilient against a powerful reactive jammer that blocks a significant fraction of all communication rounds. The reactive model is general and of interest beyond jamming (e.g., in the context of co-existing networks). The paper also reports on experimental results obtained from our simulation framework which allows us to study convergence behavior under different types of adversarial jammers.

References

1. G. Alnifie and R. Simon. A multi-channel defense against jamming attacks in wireless sensor networks. In Proc. of Q2SWinet '07, pages 95--104, 2007.
2. Gheorghe Antonoiu, Gheorghe Antonoiu, Pradip K Srimani, and Pradip K Srimani. A self-stabilizing leader election algorithm for tree graphs. Journal of Parallel and Distributed Computing, 34:227--232, 1996.
3. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (Chapter 3). John Wiley & Sons, 2004.
4. B. Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In Proc. STOC, 1987.
5. Baruch Awerbuch, Andrea Richa, and Christian Scheideler. A jamming-resistant mac protocol for single-hop wireless networks. In Proc. of PODC '08, 2008.
6. E. Bayraktaroglu, C. King, X. Liu, G. Noubir, R. Rajaraman, and B. Thapa. On the performance of IEEE 802.11 under jamming. In Proc. of IEEE Infocom '08, 2008.
7. T. Brown, J. James, and A. Sethi. Jamming and sensing of encrypted wireless ad hoc networks. In Proc. of MobiHoc '06, pages 120--130, 2006.
8. Shukai Cai, Taisuke Izumi, and Koichi Wada. Space complexity of self-stabilizing leader election in passively-mobile anonymous agents. In Proc. 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2009.
9. J. T. Chiang and Y.-C. Hu. Cross-layer jamming detection and mitigation in wireless broadcast networks. In Proc. of MobiCom '07, pages 346--349, 2007.
10. Edsger W. Dijkstra. Self-stabilization in spite of distributed control. Communications of the ACM, 17(11):643--644, 1974.
11. Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Dariusz R. Kowalski, Calvin Newport, Fabian Kuhn, and Nancy Lynch. Reliable distributed computing on unreliable radio channels. In Proc. 2009 MobiHoc S3 Workshop, 2009.
12. R. G. Gallager, P. A. Humblet, and P. M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5(l):66--77, 1983.
13. Sukumar Ghosh and Arobinda Gupta. An exercise in fault-containment: self-stabilizing leader election. Inf. Process. Lett., 59(5):281--288, 1996.
14. S. Gilbert, R. Guerraoui, and C. Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In Proc. of OPODIS '06, 2006.
15. J. Hromkovic, R. Klasing, A. Pelc, P. Ruzicka, and W. Unger. Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance (Chapter 8). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005.
16. Gene Itkis, Chengdian Lin, and Janos Simon. Deterministic, constant space, self-stabilizing leader election on uniform rings. In Proc. 9th International Workshop on Distributed Algorithms (WDAG), pages 288--302, 1995.
17. C. Y Koo, V. Bhandari, J. Katz, and N. H. Vaidya. Reliable broadcast in radio networks: The bounded collision case. In Proc. of PODC '06, 2006.
18. E. Korach, S. Kutten, and S. Moran. A modular technique for the design of efficient distributed leader finding algorithms. ACM Trans. Program. Lang. Syst., 12(1):84--101, 1990.
19. Shay Kutten and Boaz Patt-Shamir. Time-adaptive self stabilization. In Proc. PODC, 1997.
20. Seungjoon Lee, Dave Levin, Vijay Gopalakrishnan, and Bobby Bhattacharjee. Backbone construction in selfish wireless networks. In Proc. ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), 2007.
21. Xin Liu, Guevara Noubir, Ravi Sundaram, and San Tan. Spread: Foiling smart jammers using multi-layer agility. In Proc. of Infocom '07, pages 2536--2540, 2007.
22. Koji Nakano and Stephan Olariu. Randomized leader election protocols in radio networks with no collision detection. In ISAAC '00: Proceedings of the 11th International Conference on Algorithms and Computation, pages 362--373, London, UK, 2000. Springer-Verlag.
23. Vishnu Navda, Aniruddha Bohra, Samrat Ganguly, and Dan Rubenstein. Using channel hopping to increase 802.11 resilience to jamming attacks. In Proc. of Infocom '07, pages 2526--2530, 2007.
24. Koji Nikano and Stephan Olariu. Uniform leader election protocols for radio networks. IEEE Tram. Parallel Distrib. Syst., 13(5):516--526, 2002.
25. A. Pelc and D. Peleg. Feasibility and complexity of broadcasting with random transmission failures. In Proc. of PODC '05, 2005.
26. Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. A jamming-resistant mac protocol for multi-hop wireless networks. In Proc. DISC, 2010.
27. Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. Competitive and fair medium access despite reactive jamming. In Proc. 31st IEEE International Conference on Distributed Computing Systems (ICDCS), 2011.
28. Georgios Smaragdakis, Ibrahim Matta, and Azer Bestavros. Sep: A stable election protocol for clustered heterogeneous wireless sensor networks. In Proc. 2nd International Workshop on Sensor and Actor Network Protocols and Applications (SANPA), 2004.
29. Dan E Willard. Log-logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput., 15(2):468--477, 1986.
30. A. D. Wood, J. A. Stankovic, and G. Zhou. DEEJAM: Defeating energy-efficient jamming in IEEE 802.15.4--based wireless networks. In Proc. of SECON '07, 2007.
31. W. Xu, T. Wood, and Y. Zhang. Channel surfing and spatial retreats: defenses against wireless denial of service. In Proc. of Workshop on Wireless Security, 2004.

Index Terms

• Networks

  • Network properties

    • Network structure

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making