Tight bounds for delay-sensitive aggregation

ABSTRACT

This paper studies the fundamental trade-off between communication cost and delay cost arising in various contexts such as control message aggregation or organization theory. An optimization problem is considered where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about their states and to use as few transmissions as possible at the same time. 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(sqrt{h},c)). Furthermore, the paper introduces a new model for online event aggregation where the importance of an event depends on its difference to previous events.

REFERENCES

• 1: Susanne Albers , Helge Bals, Dynamic TCP acknowledgement: penalizing long delays, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: Luca Becchetti , Peter Korteweg , Alberto Marchetti-Spaccamela , Martin Skutella , Leen Stougie , Andrea Vitaletti, Latency constrained aggregation in sensor networks, Proceedings of the 14th conference on Annual European Symposium, p.88-99, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_11]
• 3: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 4: Carlos Brito , Elias Koutsoupias , Shailesh Vaya, Competitive analysis of organization networks or multicast acknowledgement: how much to wait?, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 5: Daniel R. Dooly , Sally A. Goldman , Stephen D. Scott, On-line analysis of the TCP acknowledgment delay problem, Journal of the ACM (JACM), v.48 n.2, p.243-273, March 2001 [doi>10.1145/375827.375843]
• 6: Jens S. Frederiksen , Kim S. Larsen, Packet Bundling, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.328-337, July 03-05, 2002
• 7: Anna R. Karlin , Claire Kenyon , Dana Randall, Dynamic TCP acknowledgement and other stories about e/(e-1), Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.502-509, July 2001, Hersonissos, Greece [doi>10.1145/380752.380845]
• 8: Sanjeev Khanna , Joseph (Seffi) Naor , Danny Raz, Control Message Aggregation in Group Communication Protocols, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.135-146, July 08-13, 2002
• 9: P. Korteweg, A. Marchetti-Spaccamela, L. Stougie, and A. Vitaletti. Data Aggregatcion in Sensor Networks: Balancing Communication and Delay Costs. In Proc. Colloquium on Structure, Information, Communication, and Complexity (SIROCCO), 2007.
• 10: Bhaskar Krishnamachari , Deborah Estrin , Stephen B. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.575-578, July 02-05, 2002
• 11: Christos H. Papadimitriou, Computational Aspacts of Organization Theory (Extended Abstract), Proceedings of the Fourth Annual European Symposium on Algorithms, p.559-564, September 25-27, 1996
• 12: C. H. Papadimitriou and E. Servan-Schreiber. The Origins of the Deadline: Optimizing Communication in Organizations. In Manuscript, 1999.
• 13: I. Solis and K. Obraczka. The Impact of Timing in Data Aggregation for Sensor Networks. In Proc. IEEE Int. Conference on Communications (ICC), 2004.
• 14: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 15: Pascal von Rickenbach , Roger Wattenhofer, Gathering correlated data in sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022640]
• 16: O. Younis and S. Fahmy. An Experimental Study of Routing and Data Aggregation in Sensor Networks. In Proc. IEEE Int. Conference on Mobile Ad Hoc and Sensor Systems (MASS), 2005.
• 17: Y. Yu, B. Krishnamachari, and V. K. Prasanna. Energy-Latency Tradeoffs for Data Gathering in Wireless Sensor Networks. In Proc. Joint Conference of the IEEE Computer and Communication Societies (INFOCOM), 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Algorithms, Theory

Keywords:
aggregation, competitive analysis, online algorithms, wireless sensor networks