TY - GEN
T1 - Solution of the convergecast scheduling problem on a square unit grid when the transmission range is 2
AU - Erzin, Adil
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - In this paper a conflict-free data aggregation problem, known as a Convergecast Scheduling Problem, is considered. It is NP-hard in the arbitrary wireless network. The paper deals with a special case of the problem when the communication graph is a square grid with unit cells and when the transmission range is 2 (in L1 metric). Earlier for the case under consideration we proposed a polynomial time algorithm with a guaranteed accuracy bound. In this paper we have shown that the proposed algorithm constructs an optimal solution to the problem.
AB - In this paper a conflict-free data aggregation problem, known as a Convergecast Scheduling Problem, is considered. It is NP-hard in the arbitrary wireless network. The paper deals with a special case of the problem when the communication graph is a square grid with unit cells and when the transmission range is 2 (in L1 metric). Earlier for the case under consideration we proposed a polynomial time algorithm with a guaranteed accuracy bound. In this paper we have shown that the proposed algorithm constructs an optimal solution to the problem.
KW - Conflict-free scheduling
KW - Data aggregation
KW - Wireless networks
KW - DATA-COLLECTION
KW - WIRELESS SENSOR NETWORKS
UR - http://www.scopus.com/inward/record.url?scp=85034235978&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-69404-7_4
DO - 10.1007/978-3-319-69404-7_4
M3 - Conference contribution
AN - SCOPUS:85034235978
SN - 9783319694030
VL - 10556 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 50
EP - 63
BT - Learning and Intelligent Optimization - 11th International Conference, LION 11, Revised Selected Papers
A2 - Battiti, R
A2 - Kvasov, DE
A2 - Sergeyev, YD
PB - Springer-Verlag GmbH and Co. KG
T2 - 11th International Conference on Learning and Intelligent Optimization, LION 2017
Y2 - 19 June 2017 through 21 June 2017
ER -