We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages with success simultaneously. We assume that there are n stations and at most k, k≤n, stations are active at the same time, i.e., are willing to transmit a message. If at most d, d≤k, active stations transmit simultaneously then their messages are successfully transmitted, whereas if more than d active stations transmit simultaneously then their messages are lost. The active stations receive a feedback from the channel that informs them on whether their messages have been successfully transmitted. The measure to optimize is the number of time slots needed to solve conflicts among all active stations, i.e., to make all active stations transmit their messages successfully. We prove that this measure decreases with the number d of messages that can be simultaneously transmitted with success by presenting a conflict resolution algorithm that uses a 1/d ratio of the number of time slots used by the optimal conflict resolution algorithm for the particular case d=1 [26]. We give a lower bound which is only a log(k/d) factor away from the number of time slots used by the algorithm. The algorithm is obtained via a new kind of the selectors of [13], whereas the lower bound is implied by a non-existential result for a new generalization of the locally thin families of [1,12]. We present also a randomized algorithm that allows to generate the above combinatorial structures in expected polynomial time when k=O(1).

New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions

De Bonis, Annalisa
2019-01-01

Abstract

We consider the Conflict Resolution Problem in the context of a multiple-access system in which several stations can transmit their messages with success simultaneously. We assume that there are n stations and at most k, k≤n, stations are active at the same time, i.e., are willing to transmit a message. If at most d, d≤k, active stations transmit simultaneously then their messages are successfully transmitted, whereas if more than d active stations transmit simultaneously then their messages are lost. The active stations receive a feedback from the channel that informs them on whether their messages have been successfully transmitted. The measure to optimize is the number of time slots needed to solve conflicts among all active stations, i.e., to make all active stations transmit their messages successfully. We prove that this measure decreases with the number d of messages that can be simultaneously transmitted with success by presenting a conflict resolution algorithm that uses a 1/d ratio of the number of time slots used by the optimal conflict resolution algorithm for the particular case d=1 [26]. We give a lower bound which is only a log(k/d) factor away from the number of time slots used by the algorithm. The algorithm is obtained via a new kind of the selectors of [13], whereas the lower bound is implied by a non-existential result for a new generalization of the locally thin families of [1,12]. We present also a randomized algorithm that allows to generate the above combinatorial structures in expected polynomial time when k=O(1).
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4727447
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact