Optimization of the collision resolution algorithm

Article type: Research Article

Authors: Simnishkis, Saulius

Affiliations: Computer Engineering Departament, Kaunas University of Technology, 3028 Kaunas, Studentų 50-211, Lithuania

Abstract: The problem we are dealing with is following. There exist certain number of nodes η, transmitting messages at random time moments. If time interval between messages transmitted by different nodes are less than some given value, a collision occurs. We can fix the collision, but we cannot determine the nodes engaged in the collision. The hierarchical decomposition of the nodes is used to resolve the collision. At every hierarchical level, a subset of nodes “suspected” as participating in the collision is divided in a certain number of groups. There is a time period given to every group, at which messages can be transmitted. This proceeds while no more collisions occurs. This paper covers the problems of selecting a number of groups, to minimize the longest collision resolution time, as well as average collision resolution time.

Keywords: multiple access, local area network, collision resolution, optimization

DOI: 10.3233/INF-1992-3207

Journal: Informatica, vol. 3, no. 2, pp. 247-255, 1992