We develop a framework for minimizing the communication overhead of monitoring global system parameters in IP networks and sensor networks. A global system predicate is defined as a conjunction of the local properties of different network elements. A typical example is to identify the time windows when the outbound traffic from each network element exceeds a predefined threshold. Our main idea is to optimize the scheduling of local event reporting across network elements for a given network traffic load and local event frequencies. The system architecture consists of N distributed network elements coordinated by a central monitoring station. Each network element monitors a set of local properties and the central station is responsible for identifying the status of global parameters registered in the system. We design an optimal algorithm, the Partition and Rank (PAR) scheme, when the local events are independent; whereas, when they are dependent, we show that the problem is NP-complete and develop two efficient heuristics: the PAR for dependent events (PAR-D) and Adaptive (Ada) algorithms, which adapt well to changing network conditions, and outperform the current state of the art techniques in terms of communication cost.

We consider the general problem of tracking moving objects in sensor networks. The specific application we consider is that of tracking a chemical plume moving over a large infrastructure network. We present a distributed index structure DIST that stores and updates distributed summaries as the plume moves. We present algorithms for range queries on the history of the plume. DIST localizes information with respect to time and space using a hierarchy that scales with the plume size. The highlight of our work is an analytical model to predict the cost of query algorithms based on the query location, query size, and plume's spatio-temporal distribution. Using this model, our adaptive scheme chooses the optimal scheme. Experimental results show that DIST outperforms alternative techniques in query, update, and storage costs, and scales well with the number of plumes.