Completely Irrepressible Sequences for the Asynchronous Collision Channel Without Feedback

A channel is asynchronous if all users can start to transmit at an arbitrary point in time. Protocol sequences are used for multiple access in the collision channel without feedback. In this paper, we consider protocol sequence sets with the property that each user is able to successfully send at least one packet in each sequence period for the asynchronous channel. Such sequence sets are said to be completely irrepressible (CI). We analyze the class of CI sequences with the minimum number of ones in each period and derive lower bound on the minimum period. Moreover, if the sequence structure satisfies some technical conditions, which are called equi-difference, we improve the lower bound and present a construction that asymptotically meets this lower bound. We also show that the deterministic sequences proposed in this paper yield better performance in terms of average delay than the random approach.