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 -