Stable routing scheduling algorithms in multi-hop wireless networks
Visualitza/
Impacte
Scholar |
Altres documents de l'autoria: Cholvi, Vicent; Garncarek, Pawel; Jurdzinski, Tomasz; Kowalski, Dariusz R.
Metadades
Mostra el registre complet de l'elementcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7038
comunitat-uji-handle3:10234/8634
comunitat-uji-handle4:
INVESTIGACIONMetadades
Títol
Stable routing scheduling algorithms in multi-hop wireless networksData de publicació
2022-03Editor
ElsevierISSN
0304-3975Cita bibliogràfica
Vicent Cholvi, P. Garncarek, T. Jurdziński, Dariusz R. Kowalski, Stable routing scheduling algorithms in multi-hop wireless networks, Theoretical Computer Science, Volume 921, 2022, Pages 20-35, ISSN 0304-3975, https://doi.org/10.1016/j.tcs.2022.03.038. (https://www.sciencedirect.com/science/article/pii/S0304397522001852)Tipus de document
info:eu-repo/semantics/articleVersió de l'editorial
https://www.sciencedirect.com/science/article/pii/S0304397522001852Versió
info:eu-repo/semantics/publishedVersionParaules clau / Matèries
Resum
Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stableif ... [+]
Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stableif the number of packets waiting to be delivered (backlog) is finitely bounded at any one time.
In this paper we introduce a number of routing scheduling algorithms which, making use of certain knowledge about the network’s structure, guarantee stability for certain injection rates.
First, we introduce two new families of combinatorial structures, which we call universally strong selectorsand generalized universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, we propose two local-knowledgepacket-oblivious routing scheduling algorithms. The first proposed routing scheduling algorithm onlyneeds to know some upper bounds on the number of links and on the network’s degree, and is asymptotically optimal regarding the injection rate for which stability is guaranteed. The second proposed routing scheduling algorithm isclose to be asymptotically optimal, but it only needs to know an upper bound on the number of links. For such algorithms, we also provide some results regarding both the maximum latencies and queue lengths. Furthermore, we also evaluate how the lack of global knowledge about the system topology affects the performance of the routing scheduling algorithms. [-]
Publicat a
Theoretical Computer Science, vol. 921 (2022)Entitat finançadora
Ministerio de Ciencia, Innovación y Universidades | FEDER | Polish National Science Center (NCN)
Codi del projecte o subvenció
PRX18/000163 | PID2019-109805RB-I00 | UMO-2017/25/B/ST6/02010 | UMO-2017/25/B/ST6/02553
Drets d'accés
info:eu-repo/semantics/openAccess
Apareix a les col.leccions
- LSI_Articles [362]