Maximal throughput in a tandem multi-hop radio network

Abstract

We consider an infinite slotted tandem multi-hop network in which every node is capable of hearing only its two neighbors. The destinations of the packets in the front of the various nodes are independent and independently resampled at each slot whether or not the given node was permitted to transmit. Under the following set of permissible access protocols, the maximal node utilization of the network is derived: At the beginning of every slot, each of the nodes may transmit the first packet in its queue; the nodes can coordinate their transmissions at no cost and make use of the destination of the first packet at each queue. The transmission scheme that attains the maximum is also specified. © 1988.