Analysis of contention tree algorithms

Author

Janssen, Augustus J E M ; De Jong, Marc J M

Author_Institution

Philips Res. Lab., Eindhoven, Netherlands

Volume

46

Issue

6

fYear

2000

fDate

9/1/2000 12:00:00 AM

Firstpage

2163

Lastpage

2172

Abstract

The Capetanakis-Tsybakov-Mikhailov (1978, 1979) contention tree algorithm provides an efficient scheme for multiaccessing a broadcast-communication channel. This paper studies the statistical properties of multiple-access contention tree algorithms with ternary feedback for an arbitrary degree of node. The particular quantities under investigation are the number of levels required for a random contender to have successful access, as well as the number of levels and the number of contention frames required to provide access for all contenders. Through classical Fourier analysis approximations to both the average and the variance are calculated as a function of the number of contenders n. It is demonstrated that in the limit of large n these quantities do not converge to a fixed mode, but contain an oscillating term as well

Keywords

access protocols; broadcast channels; multi-access systems; multiuser channels; random processes; trees (mathematics); Fourier analysis approximations; average; broadcast-communication channel; collision-resolution algorithm; contention frames; medium-access protocols; multi-access communication channel; multiple-access contention tree algorithms; oscillating term; random contender; random multiple-access protocols; statistical properties; ternary feedback; variance; Access protocols; Algorithm design and analysis; Analysis of variance; Broadcasting; Delay; Feedback; Helium; Laboratories; Time division multiple access; Transmitters;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/18.868486

Filename

868486