Abstract
We study broadcasting on multiple access channels with dynamic packet arrivals and jamming. The presented protocols are for the medium-access-control layer. The mechanisms of timing of packet arrivals and determination of which rounds are jammed are represented by adversarial models. Packet arrivals are constrained by the average rate of injections and the number of packets that can arrive in one round. Jamming is constrained by the rate with which the adversary can jam rounds and by the number of consecutive rounds that can be jammed. Broadcasting is performed by deterministic distributed protocols. We give upper bounds on worst-case packet latency of protocols in terms of the parameters defining adversaries. Experiments include both deterministic and randomized protocols. A simulation environment we developed is designed to represent adversarial properties of jammed channels understood as restrictions imposed on adversaries.
The first and second authors are supported by the NSF Grant 1016847. The third author is supported by the Engineering and Physical Sciences Research Council [grant numbers EP/G023018/1, EP/H018816/1].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Àlvarez, C., Blesa, M.J., Díaz, J., Serna, M.J., Fernández, A.: Adversarial models for priority-based networks. Networks 45(1), 23–35 (2005)
Anantharamu, L., Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Deterministic broadcast on multiple access channels. In: Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM), pp. 1–5 (2010)
Anantharamu, L., Chlebus, B.S., Rokicki, M.A.: Adversarial multiple access channel with individual injection rates. In: Abdelzaher, T., Raynal, M., Santoro, N. (eds.) OPODIS 2009. LNCS, vol. 5923, pp. 174–188. Springer, Heidelberg (2009)
Andrews, M., Awerbuch, B., Fernández, A., Leighton, F.T., Liu, Z., Kleinberg, J.M.: Universal-stability results and performance bounds for greedy contention-resolution protocols. Journal of the ACM 48(1), 39–69 (2001)
Andrews, M., Zhang, L.: Routing and scheduling in multihop wireless networks with time-varying channels. ACM Transactions on Algorithms 3(3), 33 (2007)
Awerbuch, B., Richa, A., Scheideler, C.: A jamming-resistant MAC protocol for single-hop wireless networks. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pp. 45–54 (2008)
Bayraktaroglu, E., King, C., Liu, X., Noubir, G., Rajaraman, R., Thapa, B.: On the performance of IEEE 802.11 under jamming. In: Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), pp. 1265–1273 (2008)
Bender, M.A., Farach-Colton, M., He, S., Kuszmaul, B.C., Leiserson, C.E.: Adversarial contention resolution for simple channels. In: Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms (SPAA), pp. 325–332 (2005)
Bhandari, V., Vaidya, N.H.: Reliable broadcast in wireless networks with probabilistic failures. In: Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM), pp. 715–723 (2007)
Bhandari, V., Vaidya, N.H.: Reliable broadcast in radio networks with locally bounded failures. IEEE Transactions on Parallel and Distributed Systems 21(6), 801–811 (2010)
Borodin, A., Kleinberg, J.M., Raghavan, P., Sudan, M., Williamson, D.P.: Adversarial queuing theory. Journal of the ACM 48(1), 13–38 (2001)
Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Adversarial queuing on the multiple-access channel. ACM Transactions on Algorithms (to appear); A preliminary version in Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC), pp. 92-101 (2006)
Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Maximum throughput of multiple access channels in adversarial environments. Distributed Computing 22(2), 93–116 (2009)
Gilbert, S., Guerraoui, R., Kowalski, D.R., Newport, C.: Interference-resilient information exchange. In: Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM), pp. 2249–2257 (2009)
Gilbert, S., Guerraoui, R., Newport, C.C.: Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. Theoretical Computer Science 410(6-7), 546–569 (2009)
IEEE. Medium access control (MAC) and physical specifications. IEEE P802.11/D10 (January 1999)
Meier, D., Pignolet, Y.A., Schmid, S., Wattenhofer, R.: Speed dating despite jammers. In: Krishnamachari, B., Suri, S., Heinzelman, W., Mitra, U. (eds.) DCOSS 2009. LNCS, vol. 5516, pp. 1–14. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Anantharamu, L., Chlebus, B.S., Kowalski, D.R., Rokicki, M.A. (2011). Medium Access Control for Adversarial Channels with Jamming. In: Kosowski, A., Yamashita, M. (eds) Structural Information and Communication Complexity. SIROCCO 2011. Lecture Notes in Computer Science, vol 6796. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22212-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-22212-2_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22211-5
Online ISBN: 978-3-642-22212-2
eBook Packages: Computer ScienceComputer Science (R0)