Bounds on Contention Management in Radio Networks

详细信息    查看全文

• 作者：Mohsen Ghaffari (17)
  Bernhard Haeupler (17)
  Nancy Lynch (17)
  Calvin Newport (18)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7611
• 期：1
• 页码：238-252
• 全文大小：271KB
• 参考文献：1. Bachir, A., Dohler, M., Wattayne, T., Leung, K.: MAC Essentials for Wireless Sensor Networks. IEEE Communications Surveys and Tutorials聽12(2), 222鈥?48 (2010) CrossRef
  2. Shan, H., Zhuang, W., Wand, Z.: Distributed Cooperative MAC for Multihop Wireless Networks. IEEE Communications Magazine聽47(2), 126鈥?33 (2009) CrossRef
  3. Sato, N., Fujii, T.: A MAC Protocol for Multi-Packet Ad-Hoc Wireless Network Utilizing Multi-Antenna. In: Proceedings of the IEEE Conference on Consumer Communications and Networking (2009)
  4. Sayed, S., and Yand, Y.: BTAC: A Busy Tone Based Cooperative MAC Protocol for Wireless Local Area Networks. In Proceedings of the Interneational Conference on Communications and Networking in China (2008).
  5. Sun, Y., Gurewitz, O., Johnson, D.B.: RI-MAC: a Receiver-Initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks. In: Proceedings of the ACM Conference on Embedded Network Sensor Systems (2008)
  6. Rhee, I., Warrier, A., Aia, M., Min, J., Sichitiu, M.L.: Z-MAC: a Hybrid MAC for Wireless Sensor Networks. IEEE/ACM Trans. on Net.聽16, 511鈥?24 (2008) CrossRef
  7. Alon, N., Spencer, J.H.: The probabilistic method. John Wiley & Sons, New York (1992)
  8. Chlamtac, I., Kutten, S.: On Broadcasting in Radio Networks鈥揚roblem Analysis and Protocol Design. IEEE Trans. on Communications (1985)
  9. Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization. In: PODC 1987: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pp. 98鈥?08. ACM, New York (1987) CrossRef
  10. Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci.聽43(2), 290鈥?98 (1991) CrossRef
  11. Chrobak, M., Gasieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. J. Algorithms聽43(2), 177鈥?89 (2002) CrossRef
  12. Chlebus, B.S., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in unknown radio networks. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete algorithms (SODA 2000), pp. 861鈥?70. Society for Industrial and Applied Mathematics, Philadelphia (2000)
  13. Chlebus, B.S., G膮sieniec, L., 脰stlin, A., Robson, J.M.: Deterministic Radio Broadcasting. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.聽1853, p. 717. Springer, Heidelberg (2000) CrossRef
  14. Clementi, A., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: The Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 709鈥?18. Society for Industrial and Applied Mathematics, Philadelphia (2001)
  15. Clementi, A., Crescenzi, P., Monti, A., Penna, P., Silvestri, R.: On Computing Ad-hoc Selective Families. In: Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, pp. 211鈥?22 (2001)
  16. Clementi, A., Monti, A., Silvestri, R.: Round robin is optimal for fault-tolerant broadcasting on wireless networks. J. Parallel Distrib. Comput.聽64(1), 89鈥?6 (2004) CrossRef
  17. Gasieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing (PODC 2005), pp. 129鈥?37. ACM, New York (2005) CrossRef
  18. Kuhn, F., Lynch, N., Newport, C.: The Abstract MAC Layer. Technical Report MIT-CSAIL-TR-2009-009, MIT CSAIL, Cambridge, MA (February 20, 2009)
  19. Kuhn, F., Lynch, N., Newport, C.: The Abstract MAC Layer. Distributed Computing聽24(3), 187鈥?96 (2011); Special issue from DISC 2009 23rd International Symposium on Distributed Computing CrossRef
  20. Kuhn, F., Lynch, N., Newport, C.: Brief Announcement: Hardness of Broadcasting in Wireless Networks with Unreliable Communication. In: Proceedings of the ACM Symposium on the Principles of Distributed Computing (PODC), Calgary, Alberta, Canada (August 2009)
  21. Cornejo, A., Lynch, N., Viqar, S., Welch, J.: A Neighbor Discovery Service Using an Abstract MAC Layer. In: Forty-Seventh Annual Allerton Conference, Champaign-Urbana, IL (October 2009) (invited paper)
  22. Kuhn, F., Lynch, N., Newport, C., Oshman, R., Richa, A.: Broadcasting in unreliable radio networks. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2010), pp. 336鈥?45. ACM, New York (2010) CrossRef
  23. Khabbazian, M., Kuhn, F., Kowalski, D.R.: Lynch. N.: Decomposing broadcast algorithms using abstract MAC layers. In: Proceedings of the 6th International Workshop on Foundations of Mobile Computing (DIALM-POMC 2010), pp. 13鈥?2. ACM, New York (2010)
  24. Khabbazian, M., Kuhn, F., Lynch, N., Medard, M., ParandehGheibi, A.: MAC Design for Analog Network Coding. In: FOMC 2011: The Seventh ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, San Jose, CA (June 2011)
  25. Censor-Hillel, K., Gilbert, S., Kuhn, F., Lynch, N., Newport, C.: Structuring Unreliable Radio Networks. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8 (2011)
  26. Ghaffari, M., Haeupler, B., Khabbazian, M.: The complexity of Multi-Message Broadcast in Radio Networks with Known Topology (manuscript in preparation, 2012)
  27. Ghaffari, M., Haeupler, B., Lynch, N., Newport, C.: Bounds on Contention Management in Radio Networks, http://arxiv.org/abs/1206.0154
  
• 作者单位：Mohsen Ghaffari (17)
  Bernhard Haeupler (17)
  Nancy Lynch (17)
  Calvin Newport (18)
  
  17. Computer Science and Artificial Intelligence Lab, MIT, USA
  18. Department of Computer Science, Georgetown University, USA
  

文摘

The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight bounds for this problem in two well-studied wireless network models: the classical model, in which links are reliable and collisions consistent, and the more recent dual graph model, which introduces unreliable edges. Our results prove that the Decay strategy, commonly used for local broadcast in the classical setting, is optimal. They also establish a separation between the two models, proving that the dual graph setting is strictly harder than the classical setting, with respect to this primitive.