Standard

Aggregation Tree Construction Using Hierarchical Structures. / Ерзин, Адиль Ильясович; Плотников, Роман; Ладыгин, Илья Сергеевич.

Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings. ed. / Gerhard Goos; Juris Hartmanis. Springer Science and Business Media Deutschland GmbH, 2023. p. 101-114 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13930 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Harvard

Ерзин, АИ, Плотников, Р & Ладыгин, ИС 2023, Aggregation Tree Construction Using Hierarchical Structures. in G Goos & J Hartmanis (eds), Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13930 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 101-114, 22nd International Conference on Mathematical Optimization Theory and Operations Research, Екатеринбург, Russian Federation, 02.07.2023. https://doi.org/10.1007/978-3-031-35305-5_7

APA

Ерзин, А. И., Плотников, Р., & Ладыгин, И. С. (2023). Aggregation Tree Construction Using Hierarchical Structures. In G. Goos, & J. Hartmanis (Eds.), Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings (pp. 101-114). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13930 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-35305-5_7

Vancouver

Ерзин АИ, Плотников Р, Ладыгин ИС. Aggregation Tree Construction Using Hierarchical Structures. In Goos G, Hartmanis J, editors, Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 101-114. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-35305-5_7

Author

Ерзин, Адиль Ильясович ; Плотников, Роман ; Ладыгин, Илья Сергеевич. / Aggregation Tree Construction Using Hierarchical Structures. Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings. editor / Gerhard Goos ; Juris Hartmanis. Springer Science and Business Media Deutschland GmbH, 2023. pp. 101-114 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{6d345437800b4b8eb390dc1ceb45bcea,
title = "Aggregation Tree Construction Using Hierarchical Structures",
abstract = "In the problem under consideration it is necessary to find a schedule of conflict-free data aggregation of a minimum length, i.e. to determine the transmission moments for each vertex of the communication graph in such a way that there are no conflicts, and all data gets into the base station within the minimum time using the arcs of unknown spanning aggregation tree (AT). Although the problem remains NP-hard even with a known AT, finding an AT is an important step in conflict-free data aggregation. This paper proposes a new algorithm for constructing the ATs in the special hierarchical structures, k-HS, which initially may contain up to k≥ 1, copies of the same vertex located at k neighbouring levels. Then for different k we build a spanning tree k-HST and propose a heuristic to leave in k-HST a single copy of each node. The result is an aggregation tree k-AT. Using k-ATs constructed for different k, we find a conflict-free schedule applying the best-known algorithms. The outcome of our method is the best schedule found on k-ATs with different values of k. To assess the quality of the proposed approach, we carried out a numerical experiment on the randomly constructed unit-disk graphs, and can conclude that the construction of k-ATs speeds up the aggregation.",
keywords = "Aggregation tree, Conflict-free aggregation, Convergecast, Hierarchical structure",
author = "Ерзин, {Адиль Ильясович} and Роман Плотников and Ладыгин, {Илья Сергеевич}",
note = "The results was prepared under financial support of Russian Science Foundation grant No 21-11-00194.; 22nd International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2023 ; Conference date: 02-07-2023 Through 08-07-2023",
year = "2023",
doi = "10.1007/978-3-031-35305-5_7",
language = "English",
isbn = "9783031353048",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "101--114",
editor = "Gerhard Goos and Juris Hartmanis",
booktitle = "Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - Aggregation Tree Construction Using Hierarchical Structures

AU - Ерзин, Адиль Ильясович

AU - Плотников, Роман

AU - Ладыгин, Илья Сергеевич

N1 - Conference code: 22

PY - 2023

Y1 - 2023

N2 - In the problem under consideration it is necessary to find a schedule of conflict-free data aggregation of a minimum length, i.e. to determine the transmission moments for each vertex of the communication graph in such a way that there are no conflicts, and all data gets into the base station within the minimum time using the arcs of unknown spanning aggregation tree (AT). Although the problem remains NP-hard even with a known AT, finding an AT is an important step in conflict-free data aggregation. This paper proposes a new algorithm for constructing the ATs in the special hierarchical structures, k-HS, which initially may contain up to k≥ 1, copies of the same vertex located at k neighbouring levels. Then for different k we build a spanning tree k-HST and propose a heuristic to leave in k-HST a single copy of each node. The result is an aggregation tree k-AT. Using k-ATs constructed for different k, we find a conflict-free schedule applying the best-known algorithms. The outcome of our method is the best schedule found on k-ATs with different values of k. To assess the quality of the proposed approach, we carried out a numerical experiment on the randomly constructed unit-disk graphs, and can conclude that the construction of k-ATs speeds up the aggregation.

AB - In the problem under consideration it is necessary to find a schedule of conflict-free data aggregation of a minimum length, i.e. to determine the transmission moments for each vertex of the communication graph in such a way that there are no conflicts, and all data gets into the base station within the minimum time using the arcs of unknown spanning aggregation tree (AT). Although the problem remains NP-hard even with a known AT, finding an AT is an important step in conflict-free data aggregation. This paper proposes a new algorithm for constructing the ATs in the special hierarchical structures, k-HS, which initially may contain up to k≥ 1, copies of the same vertex located at k neighbouring levels. Then for different k we build a spanning tree k-HST and propose a heuristic to leave in k-HST a single copy of each node. The result is an aggregation tree k-AT. Using k-ATs constructed for different k, we find a conflict-free schedule applying the best-known algorithms. The outcome of our method is the best schedule found on k-ATs with different values of k. To assess the quality of the proposed approach, we carried out a numerical experiment on the randomly constructed unit-disk graphs, and can conclude that the construction of k-ATs speeds up the aggregation.

KW - Aggregation tree

KW - Conflict-free aggregation

KW - Convergecast

KW - Hierarchical structure

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85164937540&origin=inward&txGid=d0d03f7dbe7037443d970e3487188e0d

UR - https://www.mendeley.com/catalogue/e487a074-0047-3e9b-a11d-2b0b700ee494/

U2 - 10.1007/978-3-031-35305-5_7

DO - 10.1007/978-3-031-35305-5_7

M3 - Conference contribution

SN - 9783031353048

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 101

EP - 114

BT - Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings

A2 - Goos, Gerhard

A2 - Hartmanis, Juris

PB - Springer Science and Business Media Deutschland GmbH

T2 - 22nd International Conference on Mathematical Optimization Theory and Operations Research

Y2 - 2 July 2023 through 8 July 2023

ER -

ID: 55570705