Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We prove two broadcast lower bounds for a wireless network model that includes unreliable links. For deterministic algorithms, we show n − 1 rounds are required, where n is the number of processes. For randomized algorithms, ε(n − 1) rounds are required for success probability ε. In both cases, the bounds are proved for a network in which constant-time broadcast is possible.

REFERENCES

• 1: Lali Barriére , Pierre Fraigniaud , Lata Narayanan, Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.19-27, July 2001, Rome, Italy [doi>10.1145/381448.381451]
• 2: David Kotz , Calvin Newport , Robert S. Gray , Jason Liu , Yougu Yuan , Chip Elliott, Experimental evaluation of wireless simulation assumptions, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023679]
• 3: F. Kuhn, N. Lynch, and C. Newport. The abstract MAC layer. Technical report, MIT, 2009.
• 4: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Ad hoc networks beyond unit disk graphs, Wireless Networks, v.14 n.5, p.715-729, October 2008 [doi>10.1007/s11276-007-0045-6]
• 5: S. Obayashi and J. Zander. A body-shadowing model for indoor radio communication environments. IEEE Transactions on Antennas and Propagation, 46(6):920--927, 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Theory

Keywords:
broadcast, lower bounds