Conflict Multiplicity Estimation and Batch Resolution Algorithms

Abstract

The standard model of a multiple access channel with ternary feedback is considered. When packets of a batch of k nodes initially collide, it is assumed that no a priori statistical information about k is available. A new algorithm is presented and analyzed that enables the nodes to compute a statistical estimate of k. Combining the estimation procedure with tree algorithms leads to batch resolution algorithms that resolve conflicts more efficiently than any other reported to date. Both complete resolution and partial resolution algorithms are presented. © 1988 IEEE