A jamming-resistant MAC protocol for single-hop wireless networks

ABSTRACT

In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is an adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon>0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it can be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel.

REFERENCES

• 1: Ghada Alnifie , Robert Simon, A multi-channel defense against jamming attacks in wireless sensor networks, Proceedings of the 3rd ACM workshop on QoS and security for wireless and mobile networks, October 22-22, 2007, Chania, Crete Island, Greece [doi>10.1145/1298239.1298257]
• 2: 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, page 1265, 2008.
• 3: Michael A. Bender , Martin Farach-Colton , Simai He , Bradley C. Kuszmaul , Charles E. Leiserson, Adversarial contention resolution for simple channels, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074023]
• 4: Timothy X Brown , Jesse E. James , Amita Sethi, Jamming and sensing of encrypted wireless ad hoc networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132919]
• 5: Jerry T. Chiang , Yih-Chun Hu, Cross-layer jamming detection and mitigation in wireless broadcast networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287901]
• 6: Bogdan S. Chlebus , Dariusz R. Kowalski , Mariusz A. Rokicki, Adversarial queuing on the multiple-access channel, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146398]
• 7: Artur Czumaj , Wojciech Rytter, Broadcasting algorithms in radio networks with unknown topology, Journal of Algorithms, v.60 n.2, p.115-143, August 2006 [doi>10.1016/j.jalgor.2004.08.001]
• 8: 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.
• 9: Leslie Ann Goldberg , Philip D. Mackenzie , Mike Paterson , Aravind Srinivasan, Contention resolution with constant expected delay, Journal of the ACM (JACM), v.47 n.6, p.1048-1096, Nov. 2000 [doi>10.1145/355541.355567]
• 10: Johan Håstad , Tom Leighton , Brian Rogoff, Analysis of Backoff Protocols for Mulitiple AccessChannels, SIAM Journal on Computing, v.25 n.4, p.740-774, Aug. 1996 [doi>10.1137/S0097539792233828]
• 11: IEEE. Medium access control (MAC) and physical specifications. In IEEE P802.11/D10, 1999.
• 12: 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]
• 13: Kishore Kothapalli , Christian Scheideler , Melih Onus , Andrea Richa, Constant density spanners for wireless ad-hoc networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073987]
• 14: Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Radio Network Clustering from Scratch. In Proc. of ESA '04, 2004.
• 15: Byung-Jae Kwak , Nah-Oak Song , Leonard E. Miller, Performance analysis of exponential backoff, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.343-355, April 2005 [doi>10.1109/TNET.2005.845533]
• 16: Yee Wei Law , Lodewijk van Hoesel , Jeroen Doumen , Pieter Hartel , Paul Havinga, Energy-efficient link-layer jamming attacks against wireless sensor network MAC protocols, Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks, November 07-07, 2005, Alexandria, VA, USA [doi>10.1145/1102219.1102234]
• 17: M. Li, I. Koutsopoulos, and R. Poovendran. Optimal jamming attacks and network defense policies in wireless sensor networks. In Proc. of Infocom '07, pages 1307--1315, 2007.
• 18: 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.
• 19: 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.
• 20: R. Negi and A. Perrig. Jamming analysis of MAC protocols. Technical report, Carnegie Mellon University, 2003.
• 21: Andrzej Pelc , David Peleg, Feasibility and complexity of broadcasting with random transmission failures, 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.1073879]
• 22: Prabhakar Raghavan , Eli Upfal, Stochastic Contention Resolution With Short Delays, SIAM Journal on Computing, v.28 n.2, p.709-719, April 1999 [doi>10.1137/S0097539795285333]
• 23: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
• 24: Marvin K. Simon , Jim K. Omura , Robert A. Scholtz , Barry K. Levitt, Spread spectrum communications handbook (revised ed.), McGraw-Hill, Inc., New York, NY, 1994
• 25: David Thuente and Mithun Acharya. Intelligent jamming in wireless networks with applications to 802.11b and other networks. In Proc. of MILCOM '06, 2006.
• 26: 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.
• 27: W. Xu, K. Ma, W. Trappe, and Y. Zhang. Jamming sensor networks: attack and defense strategies. IEEE Network, 20(3):41--47, 2006.
• 28: Wenyuan Xu , Wade Trappe , Yanyong Zhang , Timothy Wood, The feasibility of launching and detecting jamming attacks in wireless networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062697]
• 29: Wenyuan Xu , Timothy Wood , Wade Trappe , Yanyong Zhang, Channel surfing and spatial retreats: defenses against wireless denial of service, Proceedings of the 3rd ACM workshop on Wireless security, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023646.1023661]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Reliability, Theory

Keywords:
jamming, mac protocols, wireless ad-hoc networks