UC Riverside

This work minimizes the cost of answering queries in wireless sensor networks. To answer a query, data generated by the sensors needs to be collected and processed. We optimize the cost by constructing sophisticated query trees. Queries are divided into two categories: queries that need data from all the nodes in the network and queries that need data from a subset of nodes only.

For the first type of queries we propose a distributed algorithm to construct a near-optimal balanced communication tree with minimum overhead. Such a tree has inherently minimal number of collisions during query execution, and therefore avoids numerous retransmissions. Our algorithm outperforms previous work both in tree construction overhead and in tree balance.

For the second type of queries we present methods for constructing query trees to route and perform in-network processing of data. First, we focus on snapshot queries and show that minimizing the problem is NP-hard. We propose a dynamic programming algorithm to compute the optimal solution for small problem instances. We also propose a low complexity, approximate, heuristic algorithm for solving larger problem instances efficiently. Finally, we adapt the Fermat point problem (1-median problem) for a weighted graph, and propose a centralized solution that is used as heuristic in the above algorithms.

Dealing with continuous queries of the second category, we present an optimal distributed algorithm to adapt the placement of a single operator. Our parameter-free algorithm finds the optimal node to host the operator with minimum communication cost overhead. Three ideas, proposed here, make this feature possible: 1) identifying the special, and most frequent case, where no flooding is needed, otherwise 2) limitation of the neighborhood to be flooded and 3) variable speed flooding and eves-dropping. To our knowledge this is the first optimal and distributed algorithm to solve the 1-median (Fermat node) problem. In our experiments we show that for the rest of cases our algorithm saves 30\%-80\% of the energy compared to previously proposed techniques.