MASSACHUSETTS INST OF TECH CAMBRIDGE ELECTRONIC SYSTEMS LAB
The random accessing problem for packet radio networks is considered. The contention resolving tree algorithm of Capetanakis is applied to a model in which packets are transmitted by terminals and received by repeaters, with the possibility of geometries in which more than one repeater hears a single terminal. It is shown that naive applications of the tree algorithm of this multiple-coupled random access problem lead to algorithms which deadlock. A deadlock-free algorithm, restricted-entry algorithm for the multiple-coupled random access problem, is developed. The deadlock-free property is proved. An algorithm describing how new terminals join the network is presented.