Research output: Contribution to journal › Article › peer-review
Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles. / Erzin, Adil I.; Plotnikov, Roman V.
In: CEUR Workshop Proceedings, Vol. 1987, 2017, p. 187-193.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles
AU - Erzin, Adil I.
AU - Plotnikov, Roman V.
N1 - Publisher Copyright: © Copyright by the paper's authors.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85036635789&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85036635789
VL - 1987
SP - 187
EP - 193
JO - CEUR Workshop Proceedings
JF - CEUR Workshop Proceedings
SN - 1613-0073
ER -
ID: 9053090