Conflict-free data aggregation on a square grid when transmission distance is not less than 3

Adil Erzin, Roman Plotnikov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)

Abstract

In this paper a Convergecast Scheduling Problem on a unit square grid, in each node of which there is a sensor with transmission distance d which is not less than 3, is considered. For the cases d= 1 and d= 2, polynomial algorithms, which construct the optimal solution to the problem, are known. For an arbitrary d, an approximate algorithm is proposed, the application of which gives an upper bound on the length of the conflict-free data aggregation schedule, depending on d. We conducted a priori and a posteriori analysis of the accuracy of this algorithm for various d comparing either with the optimal length of the schedule, or with a lower bound, the value of which we improved.

Original languageEnglish
Title of host publicationAlgorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages141-154
Number of pages14
Volume10718 LNCS
ISBN (Print)9783319727509
DOIs
Publication statusPublished - 2017
Event13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017 - Vienna, Austria
Duration: 4 Sep 20178 Sep 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10718 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017
CountryAustria
CityVienna
Period04.09.201708.09.2017

Keywords

  • Convergecast scheduling problem
  • Data aggregation
  • Grid graph
  • Min-length conflict-free scheduling
  • Wireless sensor networks

Fingerprint

Dive into the research topics of 'Conflict-free data aggregation on a square grid when transmission distance is not less than 3'. Together they form a unique fingerprint.

Cite this