Competitive and fair throughput for co-existing networks under adversarial interference

ABSTRACT

This paper initiates the formal study of a fundamental problem: How to efficiently allocate a shared communication medium among a set of K co-existing networks in the presence of arbitrary external interference? While most literature on medium access focuses on how to share a medium among nodes, these approaches are often either not directly applicable to co-existing networks as they would violate the independence requirement, or they yield a low throughput if applied to multiple networks. We present the randomized medium access (MAC) protocol COMAC which guarantees that a given communication channel is shared fairly among competing and independent networks, and that the available bandwidth is used efficiently. These performance guarantees hold in the presence of arbitrary external interference or even under adversarial jamming. Concretely, we show that the co-existing networks can use a Ω(ε² min{ε, 1 poly(K)})-fraction of the non-jammed time steps for successful message transmissions, where ε is the (arbitrarily distributed) fraction of time which is not jammed.

References

1. L. Anantharamu, B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki. Medium access control for adversarial channels with jamming. In Proc. 18th International Conference on Structural Information and Communication Complexity (SIROCCO), pages 89--100, 2011.
2. H. Asai, K. Fukuda, and H. Esaki. Towards characterization of wireless traffic in coexisting 802.11a/g and 802.11n network. In Proc. ACM CoNEXT Student Workshop, 2010.
3. B. Awerbuch, A. Richa, and C. Scheideler. A jamming-resistant mac protocol for single-hop wireless networks. In Proc. PODC, 2008.
4. E. Bayraktaroglu, C. King, X. Liu, G. Noubir, R. Rajaraman, and B. Thapa. On the performance of IEEE 802.11 under jamming. In Proc. INFOCOM, 2008.
5. M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson. Adversarial contention resolution for simple channels. In Proc. SPAA, pages 325--332, 2005.
6. B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki. Adversarial queuing on the multiple-access channel. In Proc. PODC, pages 92--101, 2006.
7. S. Dolev, S. Gilbert, R. Guerraoui, D. R. Kowalski, C. Newport, F. Kuhn, and N. Lynch. Reliable distributed computing on unreliable radio channels. In Proc. 2009 MobiHoc S3 Workshop, 2009.
8. S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference). In Proc. 21st International Symposium on Distributed Computing (DISC), pages 208--222, 2007.
9. S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Secure communication over radio channels. In Proc. 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 105--114, 2008.
10. S. Gilbert, R. Guerraoui, D. R. Kowalski, and C. C. Newport. Interference-resilient information exchange. In Proc. 28th IEEE International Conference on Computer Communications (INFOCOM), pages 2249--2257, 2009.
11. S. Gilbert, R. Guerraoui, and C. Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In Proc. OPODIS, 2006.
12. L. A. Goldberg, P. D. Mackenzie, M. Paterson, and A. Srinivasan. Contention resolution with constant expected delay. Journal of the ACM, 47(6):1048--1096, 2000.
13. J. Hastad, T. Leighton, and B. Rogoff. Analysis of backoff protocols for mulitiple access channels. SIAM Journal on Computing, 25(4):740--774, 1996.
14. M. Heusse, F. Rousseau, R. Guillier, and A. Duda. Idle sense: an optimal access method for high throughput and fairness in rate diverse wireless LANs. SIGCOMM Comput. Commun. Rev., 35(4):121--132, 2005.
15. J. Ji and W. Chen. Transmission capacity of two co-existing wireless ad hoc networks with multiple antennas. In Proc. IEEE International Conference on Communications (ICC), pages 1--6, 2011.
16. V. King, J. Saia, and M. Young. Conflict on a communication channel. In Proc. 30th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 277--286, 2011.
17. C. Koo, V. Bhandari, J. Katz, and N. Vaidya. Reliable broadcast in radio networks: The bounded collision case. In Proc. PODC, 2006.
18. B.-J. Kwak, N.-O. Song, and L. E. Miller. Performance analysis of exponential backoff. IEEE/ACM Transactions on Networking, 13(2):343--355, 2005.
19. D. Meier, Y. A. Pignolet, S. Schmid, and R. Wattenhofer. Speed dating despite jammers. In Proc. DCOSS, June 2009.
20. G. Nychis, R. Chandra, T. Moscibroda, I. Tashev, and P. Steenkiste. Reclaiming the white spaces: spectrum efficient coexistence with primary users. In Proc. 7th Conference on Emerging Networking Experiments and Technologies (CoNEXT), 2011.
21. A. Pelc and D. Peleg. Feasibility and complexity of broadcasting with random transmission failures. In Proc. PODC, 2005.
22. P. Raghavan and E. Upfal. Stochastic contention resolution with short delays. SIAM Journal on Computing, 28(2):709--719, 1999.
23. A. Richa, C. Scheideler, S. Schmid, and J. Zhang. A jamming-resistant mac protocol for multi-hop wireless networks. In Proc. DISC, 2010.
24. A. Richa, C. Scheideler, S. Schmid, and J. Zhang. Competitive and fair medium access despite reactive jamming. In Proc. 31st IEEE ICDCS, 2011.
25. A. Richa, C. Scheideler, S. Schmid, and J. Zhang. Self-stabilizing leader election for single-hop wireless networks despite jamming. In Proc. 12th ACM MobiHoc, 2011.
26. A. Richa, C. Scheideler, S. Schmid, and J. Zhang. Towards jamming-resistant and competitive medium access in the SINR model. In Proc. 3rd Annual ACM S3 Workshop, 2011.
27. A. Santoso, Y. Tang, B. Vucetic, A. Jamalipour, and Y. Li. Interference cancellation in coexisting wireless local area networks. In Proc. 10th IEEE Singapore International Conference on Communication Systems, pages 1--7, 2006.
28. J. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223--250, 1995.
29. M. Young and R. Boutaba. Overcoming adversaries in sensor networks: A survey of theoretical models and algorithmic approaches for tolerating malicious interference. IEEE Communications Surveys and Tutorials, 13(4):617--641, 2011.
30. G. Zhou, J. A. Stankovic, and S. H. Son. Crowded spectrum in wireless sensor networks. In Proc. 3rd Workshop on Embedded Networked Sensors (EmNets), 2006.

Index Terms

• Networks

  • Network properties

    • Network range

      • Local area networks

      • Wide area networks

• Theory of computation

  • Design and analysis of algorithms