Aggregate sum retrieval in sensor network by distributed prefix sum data cube

Several data aggregation algorithms for sensor networks have been proposed. They are capable of returning the aggregate value of a single set of sensors. However, when data aggregates of several sets of sensors are needed at the same time, the only solution these techniques provide is to build multiple distributed data structures or gossip groups in these sets of sensors. Hence in a sensor network with N sensors, we may need 2^N distributed data structures or gossip groups in order to get the aggregates of all possible sets of sensors. In this paper, we propose a novel and data-centric technique for the fast retrieval of aggregate sums from multiple regions in a sensor network, using only one single distributed data structure. Our idea is to construct a distributed data cube in the sensor network. The distributed data cube construction algorithm we propose makes use of the inclusion-exclusion principle and it can build a distributed prefix sum data cube in a sensor network in O(N) worst case time. With the distributed data cube, data aggregate queries on any rectangular regions in the sensor network can be answered in just a constant number of operations.