TY - JOUR
T1 - An optimal greedy algorithm for the single access contention resolution problem
AU - Olivos-Castillo, Itzel C.
AU - Menchaca-Mendez, Ricardo
AU - Menchaca-Mendez, Rolando
AU - Carvalho, Marcelo M.
AU - Rivero-Angeles, Mario E.
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We present the greedy optimal algorithm for contention resolution (GOAL-CR), a greedy algorithm that solves a variant of the standard contention resolution problem where a set of nodes want to access a shared resource only once, and the objective is to minimize the time it takes for all the nodes to access the resource successfully. These assumptions hold, for instance, in event reporting applications or in the cluster formation phase of wireless sensor networks. We formally prove that the GOAL-CR computes access policies that minimize the expected contention resolution time. We also show, numerically, that the performance of the greedy policies is close to that of a protocol with complete information about the exact number of nodes that have not yet accessed the resource; this latter assumption is hard to fulfill in practice but allows the derivation of a lower bound for the problem. In addition, we show how to adapt the algorithm to scenarios where there is uncertainty in the initial number of nodes and to scenarios where nodes have very limited memory. Finally, we use simulations to show the robustness of the GOAL-CR against asynchronous starts.
AB - We present the greedy optimal algorithm for contention resolution (GOAL-CR), a greedy algorithm that solves a variant of the standard contention resolution problem where a set of nodes want to access a shared resource only once, and the objective is to minimize the time it takes for all the nodes to access the resource successfully. These assumptions hold, for instance, in event reporting applications or in the cluster formation phase of wireless sensor networks. We formally prove that the GOAL-CR computes access policies that minimize the expected contention resolution time. We also show, numerically, that the performance of the greedy policies is close to that of a protocol with complete information about the exact number of nodes that have not yet accessed the resource; this latter assumption is hard to fulfill in practice but allows the derivation of a lower bound for the problem. In addition, we show how to adapt the algorithm to scenarios where there is uncertainty in the initial number of nodes and to scenarios where nodes have very limited memory. Finally, we use simulations to show the robustness of the GOAL-CR against asynchronous starts.
KW - Algorithms
KW - contention resolution
KW - greedy algorithms
KW - optimization
KW - random algorithms
KW - wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=85063254583&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2019.2902358
DO - 10.1109/ACCESS.2019.2902358
M3 - Artículo
AN - SCOPUS:85063254583
SN - 2169-3536
VL - 7
SP - 28452
EP - 28463
JO - IEEE Access
JF - IEEE Access
M1 - 8654626
ER -