Finding Minimum Cost Data Collection Tree with Aggregation

Abstract In this paper we consider a special case of building a minimum cost data aggregation tree problem raised in the context of wireless sensor networks, when the sensors correspond to the nodes in the two-dimensional plane, and the distances between nodes are measured according to the (squared) Euclidean norm. We show that the problem is NP-hard for the general metric case and provide a number of approximation algorithms for this problem based on the concept of Dijkstra’s cheapest paths tree, Bounded-Hop Diameter Tree and Hamiltonian Cycle construction.