1200 IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-33. NO. 1 I, NOVEMBER 1985 Throughput-Delay Characteristics of Some Slotted-ALOHA Multihop Packet Radio Networks Abstract-A Markovian model is formulated to find the throughput- delay performance for slotted-ALOHA multihop packet radio networks with a fixed configuration of packet radio units (terminals and repeaters) and.fixed source-to-link paths for packets. Improvements in performance which are obtained by the adjustment of transmission parameters (suppression/acceleration) according to the states of nearby units and/or by having repeaters equipped with multiple buffers are demonstrated. I. INTRODUCTION T HE packet radio network considered in this paper is a ground-based minicomputer communication network using a shared multiple-access radio channel. One of its potential uses will be providing real-time computer-based communication for packet radio-equipped military users, both in garrison and in the battlefield. Another application is to replace regional wired packet-switching networks without the need for cable extension. Although some intensive experimental research on packet radio networks has taken place at several locations during the last few years (e.g., PRNET in [7]), little theoretical work about their performance evaluation seems to have been published so far. Compared. to the analysis of one-hop broadcast networks,' for which extensive literature has ap- peared, one of the .difficulties in dealing with multihop networks is inherent in the fact that the issue of routing comes into play as in the wire-based store-and-forward networks. However, because of colliding transmissions from multiple packet radio units, we have not found any exact solution- whether in a product form or not-for evaluating the mean packet delay of a general class of multihop packet radio networks. One of the reasons that a discrete-time queueing network (modeled on the slotted-ALOHA system) does not lend itself to a product-form solution is that more than one event can occur 'in a single slot [ 11. As for the approximate evaluation of the average packet delay ,and the optimal routing with respect to it, some contributions may be noted. Leiner [l 11 showed an approxi- mate way to get the delay at each link, given its traffic requirement, using Kleinrock's ZAP approximation [8] for the throughput-delay curves for a variety of channel access protocols in single-hop systems. Kung [lo] speculates that the average delay is a convex function in the space over the traffic requirements on all links, on the basis of the ZAP approxima- tion [8] of the throughput-delay curves. Thus, he adapts the flow deviation method, originally developed for wire-based store-and-forward networks in [4], to the multihop packet radio networks. Some other authors [2], [3], [ 131 create more or less idealistic assumptions (such as zero propagation delay Paper approved by the Editor for Computer Communication of the IEEE Communications Society. Manuscript received Februan 14, 1983; revised January 10, 1985: This work was supported by the Defense Advanced Research Projects Agency under Contract MDA 903-824-0064. H. Takagi is with IBM Japan Science Institute, Tokyo 102, Japan. L. Kleinrock is with the Department of Computer Science, University of California, Los Angeles, CA 90024. and perfect delay capture) to inhibit interference of transmis- sions and discuss the resulting throughput and optimal routing. Some two-hop networks are analyzed by Tobagi [ 151. In this paper, we take a Markov-chain approach to find the throughput-delay characteristics for a general class of slotted- ALOHA multihop packet radio networks which consist of a relatively small number of packet radio units. In Section we describe our basic model of packet radio networks in *detail. This is followed in Section I11 by the Markov-chain formula-, tion to calculate the throughput and average end-to-end-packet delay for a given network. The tradeoffs , between them are shown for two example networks. In the following sections, we propose and analyze three ways (and their combinations) of reducing the average packet delay for a given throughput requirement and increasing the maximum supportable throughput. 11. BASIC MODEL In this section, we describe in detail our basic model of packet radio networks. Consider a network consisting of a fixed number of packet radio units, each having an omnidirec- tional antenna, thereby being capable of transmitting or receiving a packet, but not both simultaneously. We distin- guish the two kinds of packet radio units: termind and repeater. A terminal is defined to be a unit which can be a source and/or a sink of packets but does not relay any packets in transit. A repeater is defined to be a unit which neither generates nor absorbs any packets but only relays them. We assume that every unit is within the transmission range of some other units but not necessarily of all others; this hearing topology is given and fixed. Let us represent the hearing configuration by a matrix (hq) defined by - 1 if units i and j hear each other IJ- ji- I 0 otherwise hi;= 1. (1) We also assume a given set of fixed paths for packets which connect pairs of specific source and sink terminals via a number of repeaters. Thus, packets originating at the source terminal of a particular path are sent (with specific destination ID for each link) in a store-and-forward manner through several repeaters along a unique path down to the sink terminal and absorbed there. Let these paths be numbered k = 1, 2, 3, networks 1 and 2. In the (undirected) graph representation of hearing topology, nodes are packet radio units (either a terminal shown by a circle or a repeater shown by a square), and arcs are drawn between the units in the hearing range of