Optimal Locations for Join Processing in Sensor Networks

Battery lifetime tends to become the limiting factor for query processing in sensor networks; this calls for energy-saving implementations of query-algebra operators. As the join operator is important for data acquisition in sensor networks, e.g., to explore correlations in the data, recent research has brought up a number of in-network strategies for join processing. But it is still unclear in which cases such strategies can be applied. In some scenarios it might even be optimal to process a join query using a centralized implementation. This paper presents our work in progress on analyzing how join queries can be optimally handled in sensor networks. In particular, we provide theoretical bounds on the energy-savings that can be achieved by distinct in- network strategies as opposed to a simple centralized join. An important aspect is that devising an optimal join strategy requires knowledge, e.g. of the join selectivity. Gathering this knowledge reduces the potential energy savings. Our major contribution is to show in which cases different in-network approaches are theoretically applicable and when the superior strategy is to perform the join at the base station. This is a first step towards devising practical join strategies.