Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles

Adil I. Erzin, Roman V. Plotnikov

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

1 Цитирования (Scopus)


In the convergecast scheduling problem, it is required to find a spanning aggregation tree with a root in a base station (sink) in a given communication graph and build a conflict-free (half-duplex, interference-aware) min-length schedule for aggregating data over the edges of the aggregation tree. This problem is strongly NP-hard even in the case of a given aggregation tree. However, if the communication graph is a square grid in each node of which there is a sensor and in which per unit time a data packet is transmitted along one edge of the graph, the problem is polynomially solvable. In this paper, we consider a communication graph in the form of a square grid with rectangular obstacles impenetrable by the messages and propose a polynomial algorithm for constructing a conflict-free schedule for data aggregation. An intensive numerical experiment confirmed the hypothesis that the algorithm constructs an optimal solution in 100% of cases.

Язык оригиналаанглийский
Страницы (с-по)187-193
Число страниц7
ЖурналCEUR Workshop Proceedings
СостояниеОпубликовано - 2017


Подробные сведения о темах исследования «Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles». Вместе они формируют уникальный семантический отпечаток (fingerprint).