Communication-efficient implementation of join in sensor networks

A sensor network is a multi-hop wireless network of sensor nodes cooperatively solving a sensing task. Each sensor node generates data items that are readings obtained from one or more sensors on the node. This makes a sensor network similar to a distributed database system. While this view is somewhat traditional, efficient execution of database (SQL) queries in sensor network remains a challenge, due to the unique characteristics of such networks such as limited memory and battery energy on individual nodes, multi-hop communication, unreliable infrastructure, and dynamic topology. Since the nodes are battery powered, the sensor network relies on energy-efficiency (and hence, communication efficiency) for a longer lifetime of the network. In this article, we have addressed the problem of communication-efficient implementation of the SQL "join" operator in sensor networks. In particular, we design an optimal algorithm for implementation of a join operation in dense sensor networks that provably incurs minimum communication cost under some reasonable assumptions. Based on the optimal algorithm, we design a suboptimal heuristic that empirically delivers a near-optimal join implementation strategy and runs much faster than the optimal algorithm. Through extensive simulations on randomly generated sensor networks, we show that our techniques achieve significant energy savings compared to other simple approaches.