PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks

Sensor networks are widely used in many applications to collaborativelycollect information from the physical environment. In theseapplications, the exploration of the relationship and linkage of sensingdata within multiple regions can be naturally expressed by joiningtuples in these regions. However, the highly distributed andresource-constraint nature of the network makes join a challengingquery. In this paper, we address the problem of processing join queryamong different regions progressively and energy-efficiently in sensornetworks. The proposed algorithm PEJA (Progressive Energy-efficient JoinAlgorithm) adopts an \it event-driven strategy to output the joiningresults as soon as possible, and alleviates the storage shortage problemin the in-network nodes. It also installs \it filters in the joiningregions to prune unmatchable tuples in the early processing phase,saving lots of unnecessary transmissions. Extensive experiments on bothsynthetic and real world data sets indicate that the PEJA schemeoutperforms other join algorithms, and it is effective in reducing thenumber of transmissions and the delay of query results during the joinprocessing.