×

Sade: competitive MAC under adversarial SINR. (English) Zbl 1451.68053

Summary: This paper considers the problem of how to efficiently share a wireless medium which is subject to harsh external interference or even jamming. So far, this problem is understood only in simplistic single-hop or unit disk graph models. We in this paper initiate the study of MAC protocols for the SINR interference model (a.k.a. physical model). This paper makes two contributions. First, we introduce a new adversarial SINR model which captures a wide range of interference phenomena. Concretely, we consider a powerful, adaptive adversary which can jam nodes at arbitrary times and which is only limited by some energy budget. Our second contribution is a distributed MAC protocol called Sade which provably achieves a constant competitive throughput in this environment: we show that, with high probability, the protocol ensures that a constant fraction of the non-blocked time periods is used for successful transmissions.

MSC:

68M14 Distributed systems
68M12 Network protocols
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alistarh, D., Gilbert, S., Guerraoui, R., Milosevic, Z., Newport, C.: Securing your every bit: reliable broadcast in byzantine wireless networks. In: Proceedings Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 50-59 (2010)
[2] Alnifie, G., Simon, R.: A multi-channel defense against jamming attacks in wireless sensor networks. In: Proceedings of Q2SWinet, pp. 95-104 (2007)
[3] Awerbuch, B., Richa, A., Scheideler, C.: A jamming-resistant MAC protocol for single-hop wireless networks. In: Proceedings of ACM PODC (2008) · Zbl 1301.68041
[4] Bayraktaroglu, E., King, C., Liu, X., Noubir, G., Rajaraman, R., Thapa, B.: On the performance of IEEE 802.11 under jamming. In: Proceedings of IEEE INFOCOM, pp. 1265-1273 (2008)
[5] Bender, M.A., Farach-Colton, M., He, S., Kuszmaul, B.C., Leiserson, C.E.: Adversarial contention resolution for simple channels. In: Proceedings of ACM SPAA (2005) · Zbl 0914.68103
[6] Bender, M.A., Fineman, J.T., Gilbert, S., Young, M.: How to scale exponential backoff: constant throughput, polylog access attempts, and robustness. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 636-654 (2016) · Zbl 1410.68066
[7] Bertier, M., Kermarrec, A.-M., Tan, G.: Message-efficient byzantine fault-tolerant broadcast in a multi-hop wireless sensor network. In: Proceedings of IEEE 30th International Conference on Distributed Computing Systems (ICDCS), pp. 408-417 (2010)
[8] Brown, T., James, J., Sethi, A.: Jamming and sensing of encrypted wireless ad hoc networks. In: Proceedings of ACM International Symposium on Mobile Ad hoc Networking and Computing (MOBIHOC), pp. 120-130 (2006)
[9] Chiang, J., Hu, Y.-C.: Cross-layer jamming detection and mitigation in wireless broadcast networks. In: Proceedings of MOBICOM, pp. 346-349 (2007)
[10] Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Adversarial queuing on the multiple-access channel. In: Proceedings of ACM PODC (2006) · Zbl 1314.68153
[11] Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. J. Algorithms 60(2), 115-143 (2006) · Zbl 1100.68649 · doi:10.1016/j.jalgor.2004.08.001
[12] Dams, J., Hoefer, M., Kesselheim, T.: Jamming-resistant learning in wireless networks. In: Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP), pp. 447-458 (2014) · Zbl 1409.68031
[13] Dolev, S., Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C., Kuhn, F., Lynch, N.: Reliable distributed computing on unreliable radio channels. In: Proceedings of 2009 MOBIHOC S3 Workshop (2009)
[14] Dolev, S., Gilbert, S., Guerraoui, R., Kuhn, F., Newport, C.C.: The wireless synchronization problem. In: Proceedings of 28th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 190-199 (2009) · Zbl 1291.68045
[15] Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.: Gossiping in a multi-channel radio network: an oblivious approach to coping with malicious interference. In: Proceedings of the Symposium on Distributed Computing (DISC) (2007) · Zbl 1145.68322
[16] Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.: Secure communication over radio channels. In: Proceedings of 27th ACM Symposium on Principles of Distributed Computing (PODC), pp. 105-114 (2008) · Zbl 1301.94112
[17] Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.C.: Gossiping in a multi-channel radio network. In: Proceedings of 21st International Symposium on Distributed Computing (DISC), pp. 208-222 (2007) · Zbl 1145.68322
[18] Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C.: Interference-resilient information exchange. In: Proceedings of the 28th Conference on Computer Communications. IEEE INFOCOM (2009)
[19] Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C.C.: Interference-resilient information exchange. In: proceedings of 28th IEEE International Conference on Computer Communications (INFOCOM), pp. 2249-2257 (2009)
[20] Gilbert, S., Guerraoui, R., Newport, C.: Of malicious motes and suspicious sensors: on the efficiency of malicious interference in wireless networks. In: Proceedings of OPODIS (2006) · Zbl 1157.68013
[21] Gilbert, S., King, V., Pettie, S., Porat, E., Saia, J., Young, M.: (Near) Optimal resource-competitive broadcast with jamming. In: Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 257-266 (2014)
[22] Gilbert, S.L., Zheng, C.: Sybilcast: broadcast on the open airwaves. In: Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 130-139 (2013)
[23] Goldberg, L.A., Mackenzie, P.D., Paterson, M., Srinivasan, A.: Contention resolution with constant expected delay. J. ACM 47(6), 1048 (2000) · Zbl 1094.68518 · doi:10.1145/355541.355567
[24] Gupta, P., Kumar, P.: The capacity of wireless networks. IEEE Trans. Inf. Theory 46(2), 388-404 (2000) · Zbl 0991.90511 · doi:10.1109/18.825799
[25] Hastad, J., Leighton, T., Rogoff, B.: Analysis of backoff protocols for mulitiple accesschannels. SIAM J. Comput. 25(4), 740 (1996) · Zbl 0857.60064 · doi:10.1137/S0097539792233828
[26] IEEE: Medium access control (MAC) and physical specifications. In: IEEE P802.11/D10 (1999)
[27] King, V., Saia, J., Young, M.: Conflict on a communication channel. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 277-286 (2011) · Zbl 1321.68027
[28] Koo, C., Bhandari, V., Katz, J., Vaidya, N.: Reliable broadcast in radio networks: the bounded collision case. In: Proceedings of ACM PODC (2006) · Zbl 1314.68047
[29] Kuhn, F., Moscibroda, T., Wattenhofer, R.: Radio network clustering from scratch. In: Proceedings of ESA (2004) · Zbl 1111.68320
[30] Kwak, B.-J., Song, N.-O., Miller, L.E.: Performance analysis of exponential backoff. IEEE/ACM Trans. Netw. 13(2), 343-355 (2005)
[31] Li, M., Koutsopoulos, I., Poovendran, R.: Optimal jamming attacks and network defense policies in wireless sensor networks. In: Proceedings of IEEE INFOCOM, pp. 1307-1315 (2007)
[32] Liu, X., Noubir, G., Sundaram, R., Tan, S.: Spread: foiling smart jammers using multi-layer agility. In: Proceedings of IEEE INFOCOM, pp. 2536-2540 (2007)
[33] Meier, D., Pignolet, Y.A., Schmid, S., Wattenhofer, R.: Speed dating despite jammers. In: Proceedings of DCOSS (2009)
[34] Navda, V., Bohra, A., Ganguly, S., Rubenstein, D.: Using channel hopping to increase 802.11 resilience to jamming attacks. In: Proceedings of IEEE INFOCOM, pp. 2526-2530 (2007)
[35] Ogierman, A., Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive mac under adversarial sinr. In: Proceedings of IEEE INFOCOM (2014) · Zbl 1451.68053
[36] Pelc, A., Peleg, D.: Feasibility and complexity of broadcasting with random transmission failures. In: Proceedings of ACM PODC (2005) · Zbl 1314.68080
[37] Raghavan, P., Upfal, E.: Stochastic contention resolution with short delays. SIAM J. Comput. 28(2), 709-719 (1999) · Zbl 0914.68103 · doi:10.1137/S0097539795285333
[38] Rappaport, T.: Wireless Communications. Prentice Hall PTR, Upper Saddle River (2002)
[39] Richa, A., Scheideler, C., Schmid, S., Zhang, J.: A jamming-resistant MAC protocol for multi-hop wireless networks. In: Proceedings of DISC (2010) · Zbl 1290.68028
[40] Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive and fair medium access despite reactive jamming. In: Proceedings of 31st International Conference on Distributed Computing Systems (ICDCS) (2011)
[41] Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Self-stabilizing leader election for single-hop wireless networks despite jamming. In: Proceedings of 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC) (2011)
[42] Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive and fair throughput for co-existing networks under adversarial interference. In: Proceedings of 31st Annual ACM Symposium on Principles of Distributed Computing (PODC) (2012) · Zbl 1301.68045
[43] Scheideler, C., Richa, A., Santi, P.: An \[O(\log n)O\](logn) dominating set protocol for wireless ad-hoc networks under the physical interference model. In: Proceedings of ACM International Symposium on Mobile Ad hoc Networking and Computing (MOBIHOC) (2008)
[44] Simon, M.K., Omura, J.K., Schultz, R.A., Levin, B.K.: Spread Spectrum Communications Handbook. McGraw-Hill, New York (2001)
[45] Tan, H., Wacek, C., Newport, C., Sherr, M.: A disruption-resistant mac layer for multichannel wireless networks. In: Proceedings of International Conference on Principles of Distributed Systems (OPODIS), pp. 202-216 (2014)
[46] Wood, A., Stankovic, J., Zhou, G.: DEEJAM: defeating energy-efficient jamming in IEEE 802.15.4-based wireless networks. In: Proceedings of SECON (2007)
[47] Xu, W., Wood, T., Zhang, Y.: Channel surfing and spatial retreats: defenses against wireless denial of service. In: Proceedings of Workshop on Wireless Security (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.