A channel access scheme for large dense packet radio networks

ABSTRACT

Prior work in the field of packet radio networks has often assumed a simple success-if-exclusive model of successful reception. This simple model is insufficient to model interference in large dense packet radio networks accurately. In this paper we present a model that more closely approximates communication theory and the underlying physics of radio communication. Using this model we present a decentralized channel access scheme for scalable packet radio networks that is free of packet loss due to collisions and that at each hop requires no per-packet transmissions other than the single transmission used to convey the packet to the next-hop station. We also show that with a modest fraction of the radio spectrum, pessimistic assumptions about propagation resulting in maximum-possible self-interference, and an optimistic view of future signal processing capabilities that a self-organizing packet radio network may scale to millions of stations within a metro area with raw per-station rates in the hundreds of megabits per second.

REFERENCES

• 1: Norman Abramson. THE ALOHA SYSTEM-Another alternative for computer communications. In Proceedings of the Fall Joint Computer Conference, pages 281- 285. AFIPS, 1970.
• 2: Norman Abramson, editor. Multiple Access Communications. IEEE Press, 1993.
• 3: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 4: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 5: CCIR Rep. 719-2. Attenuation by atmospheric gases. In Recommendations and Reports of the CCIR, volume V, pages 167-177, Geneva, 1986. CCIR, International Telecommunication Union.
• 6: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, FAMA-PJ: a channel access protocol for wireless LANs, Proceedings of the 1st annual international conference on Mobile computing and networking, p.76-85, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215559]
• 7: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, Floor acquisition multiple access (FAMA) for packet-radio networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.262-273, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 8: Robert E. Kahn, Steven A. Gronemeyer, Jerry Burchfiel, and Ronald C. Kunzelman. Advances in packet radio technology. Proceedings of the IEEE, 66(11):1468- 1496, November 1978.
• 9: Phil Karn. MACA - A new channel access method for packet radio. In ARRL 9th Computer Networking Conference. ARRL, 1990.
• 10: Phil Karn. Spectral efficiency considerations for packet radio. In ARRL l Oth Computer Networking Conference, pages 62-66. ARRL, 1991.
• 11: Leonard Kleinrock and John Silvester. Spatial reuse in multihop packet radio networks. Proceedings of the IEEE, 75(1):156-167, January 1987.
• 12: H. Vincent Poor, An introduction to signal detection and estimation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 13: Michael B. Pursley. The role of spread spectrum in packet radio networks. Proceedings of the IEEE, 75(1):116-134, January 1987.
• 14: S. Ramanathan , Errol L. Lloyd, Scheduling algorithms for multi-hop radio networks, Conference proceedings on Communications architectures & protocols, p.211-222, August 17-20, 1992, Baltimore, Maryland, United States
• 15: Henry R. Reed and Carl M. Russell. Ultra High Frequency Propagation. Boston Technical Publishers, second edition, 1964.
• 16: C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, XXVII(3 and 4):379-423 and 623-656, July (part 1) and October (part 2) 1948. Also republished in {20}, {21}, and {17}.
• 17: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 18: T. J. Shepard, Decentralized Channel Management in Scalable Multihop Spread-Spectrum Packet Radio Networks, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 19: Marvin K. Simon , Jim K. Omura , Robert A. Scholtz , Barry K. Levitt, Spread spectrum communications handbook (revised ed.), McGraw-Hill, Inc., New York, NY, 1994
• 20: David Slepian, editor. Key Papers in The Development of Information Theory. IEEE Press, 1974.
• 21: Neil J. A. Sloane , Aaron D. Wyner , Claude E. Shannon, Claude Elwood Shannon: collected papers, IEEE Press, Piscataway, NJ, 1993
• 22: Elvino S. Sousa. Interference modeling in a direct sequence spread-spectrum packet radio network. IEEE Transactions on Communications, 38(9):1475- 1482, September 1990.
• 23: Elvino S. Sousa and John A. Silvester. Spreading code protocols for distributed spread-spectrum packet radio networks. IEEE Transactions on Communications, 36(3):272-281, March 1988.
• 24: Hideaki Takagi and Leonard Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, COM-32(3):246-257, March 1984.
• 25: G. D. Troxel, Time Surveying: Clock Synchronization over packet Networks, Massachusetts Institute of Technology, Cambridge, MA, 1994
• 26: P. F. Tsuchiya, The landmark hierarchy: a new hierarchy for routing in very large networks, Symposium proceedings on Communications architectures and protocols, p.35-42, August 16-18, 1988, Stanford, California, United States
• 27: Sergio Verdfi. Recent progress in multiuser detection. In William A. Porter and Subhash C. Kak, editors, Lecture Notes in Control and Information Sciences. Springer- Verlag, 1989. Also republished in {2}.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance, Theory