Routing Correlated Data with Fusion Cost in Wireless Sensor Networks

In this paper, we propose a routing algorithm called minimum fusion Steiner tree (MFST) for energy efficient data gathering with aggregation (fusion) in wireless sensor networks. Different from existing schemes, MFST not only optimizes over the data transmission cost, but also incorporates the cost for data fusion, which can be significant for emerging sensor networks with vectorial data and/or security requirements. By employing a randomized algorithm that allows fusion points to be chosen according to the nodes' data amounts, MFST achieves an approximation ratio of 5/4log(k + 1), where k denotes the number of source nodes, to the optimal solution for extremely general system setups, provided that fusion cost and data aggregation are nondecreasing against the total input data. Consequently, in contrast to algorithms that only excel in full or nonaggregation scenarios without considering fusion cost, MFST can thrive in a wide range of applications