Yvonne Anne Pignolet ; Stefan Schmid ; Roger Wattenhofer - Tight Bounds for Delay-Sensitive Aggregation

dmtcs:489 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 1 - https://doi.org/10.46298/dmtcs.489
Tight Bounds for Delay-Sensitive Aggregation

Authors: Yvonne Anne Pignolet 1; Stefan Schmid ORCID-iD2,3; Roger Wattenhofer 4

  • 1 IBM Research Laboratory [Zurich]
  • 2 NEC Europe Ltd., Network Laboratories
  • 3 Telekom Innovation Laboratories [Berlin]
  • 4 Computer Engineering and Networks Laboratory

This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. We derive an upper bound on the competitive ratio of O(min (h, c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Omega(min (h, c)). For chain networks, we prove a tight competitive ratio of Theta(min (root h, c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root.


Volume: Vol. 12 no. 1
Section: Distributed Computing and Networking
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: Competitive Analysis,Wireless Sensor Networks,Distributed Algorithms,Aggregation,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1007/978-3-540-72951-8_12
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.tcs.2008.08.043
Source : ScholeXplorer IsRelatedTo HANDLE 1871/44890
  • 10.1016/j.tcs.2008.08.043
  • 1871/44890
  • 10.1007/978-3-540-72951-8_12
  • 10.1007/978-3-540-72951-8_12
Data aggregation in sensor networks: Balancing communication and delay costs

1 Document citing this article

Consultation statistics

This page has been seen 270 times.
This article's PDF has been downloaded 435 times.