Scheduling algorithms for tree-based convergecast networks with a random number of messages

In the paper we consider tree-based L-level convergecast networks, in which leaf nodes correspond to data sources (DS), a root node - to a base station (BS), and other nodes - to intermediate repeaters (IR). At a startup phase each DS generates a random number of messages for transmission to a BS. For such a model a lower bound for an average duration of collision-free convergecast is given. Also we propose a collision-free messages transmission scheduling algorithms for which the lower bound is achieved at L → ∞.