684 IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-32, NO. 6, JUNE 1984 The Spatial Capacity of a Slo’tted ALOHA Multihop Packet Radio Network with Capture RANDOLPH NELSON AND LEONARD KLEINROCK, FELLOW, IEEE A bstract-In this paper we determine throughput equations for a packet radio network where terminals are randomly distributed on the plane, are able to capture transmitted signals, and use slotted ALOHA to access the channel. We find that the throughput of the network is a strictly increasing function of the receiver’s ability to capture signals, and depends on the transmission range of the terminals and their probability of transmitting packets. Under ideal circumstances, we show the expected fraction of terminals in the network that are engaged in successful traffic in any ’ ,slot does not exceed 21 percent. 1. INTRODUCTION T HE proliferation of computers within the last decade has created the need to interconnect computing resources with efficient and economical communications. Packet radio broadcast techniques have been proposed as a method to implement such computer networks and are an attractive alternative to conventional land-based line networks because radio networks are not dependent on fixed topologies, can be connected to numerous devices, and can be implemented with inexpensive radio transceivers. Many novel uses for future ratio, networks can be found in [ 11 . The first packet radio network, the ALOHA system [2] , [31 , demonstrated the feasibility of this approach as did the PRNET of the Defense Advanced Research Projects Agency 141. Nodes in radio networks, known as terminals, are geographically separated and can communicate only by use of the broadcast channel. It is thus important to develop techniques that make efficient use of channel bandwidth. There has been extensive research in creating efficient protocols for networks in which all terminals are assumed to be within line9f-sight of each other [5]. In such one-hop networks, all terminals share common information about the status of the channel. The channel is said to be idle if no terminals transmit, successful if exactly one terminal transmits, and to have a collision if two or more transmit simultaneously. In networks where packets must be relayed over several hops before reaching their final destina- tion, the status of the channel can be known immediately only within the hearing distance of a terminal. Since a transmitted packet is received by only a subset of the nodes in the net- work, there is the possibility that another terminal in a dif- ferent part of the network may also be successfully transmit- ting a packet during the same time since it is not disturbed by the first terminal’s transmission. This important phenomenon is called spatial-reuse of the channel and was studied in [6]. The local nature of the channel state information, however, causes difficulty in coordinating the transmissions of termi- nals. In single-hop environments, terminals share common Paper approved by the Editor for Computer Communications of the IEEE Communications Society for publication without oral presentation. Manuscript received May 12,, 1981; revised November 10, 1982. This work was supported by the Advanced Research Projects Agency of the Department of Defense under Contract MDA 903-77-C-0272. R. Nelson was with the Department of Computer Science, University of California, Los Angeles, CA 90024. He is now with the Thomas J. Watson Research Center, IBM Corporation, Yorktown Heights, NY 10598. L. Kleinrock is with the Department of Computer Science, University of California, Los Angeles, CA 90024. information about the status of the channel. This information can be used to develop efficient single-hop channel access protocols; however, such protocols cannot always be readily adapted to multihop environments. Another example in the one-hop environment is the CSMA protocol [7] -[9]. In this protocol, a terminal first senses the channel to determine if the channel is idle. If so, the terminal transmits its packet immediately. The probability of a colli- sion on the channel is equal to the probability that two or more terminals simultaneously sensed the channel idle and transmitted their packets. For networks that are not separated by vast distances, the propagation delay between terminals is small enough to make this event occur infrequently. In the multihop environment, however, hearing the channel idle provides information only about the transmitter’s local envi- ronment and does not guarantee that the receiver’s environ- ment is also idle. Thus the probability of incurring a collision is no longer only a function of the propagation delay and packets will often collide [ 101 . This implies that using protocols developed for a single-hop environments will not always perform well in multihop net- works. The performance of the slotted ALOHA protocol in a multihop environment has been studied in [ 1 1 ] and in [ 121 the authors calculated tHe transmission radius that maximized throughput for a random planar network. In this paper we generalize their work to environments where radio receivers have the ability to capture signals. A receiver equipped with capture can, under certain circumstances, successfully decode one of several simultaneous signals on the channel. Capture models for single-hop configurations have been studied [ 131, [ 141 , and demonstrate increased performance over noncap- ture environments. In this paper we show that for a multi- hop random network increasing the receiver’s ability to capture signals will always increase the throughput of the network. 11. THE MODEL Throughout the paper we will make the following assump- tions about the network: 1) Topo1og.v: We assume that packet radios are distributed according to a Poisson point process on the plane with a mean density of h packet