Standard

Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles. / Erzin, Adil I.; Plotnikov, Roman V.

в: CEUR Workshop Proceedings, Том 1987, 2017, стр. 187-193.

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

Harvard

Erzin, AI & Plotnikov, RV 2017, 'Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles', CEUR Workshop Proceedings, Том. 1987, стр. 187-193.

APA

Erzin, A. I., & Plotnikov, R. V. (2017). Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles. CEUR Workshop Proceedings, 1987, 187-193.

Vancouver

Author

Erzin, Adil I. ; Plotnikov, Roman V. / Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles. в: CEUR Workshop Proceedings. 2017 ; Том 1987. стр. 187-193.

BibTeX

@article{b0acff4085334de08c18c4a193a05ccd,
title = "Efficient algorithm for the convergecast scheduling problem on a square grid with obstacles",
abstract = "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.",
author = "Erzin, {Adil I.} and Plotnikov, {Roman V.}",
note = "Publisher Copyright: {\textcopyright} Copyright by the paper's authors.",
year = "2017",
language = "English",
volume = "1987",
pages = "187--193",
journal = "CEUR Workshop Proceedings",
issn = "1613-0073",
publisher = "CEUR-WS",

}

RIS

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