Efficient Scheduling for Periodic Aggregation Queries in Multihop Sensor Networks

In this paper, we study periodic query scheduling for data aggregation with minimum delay under various wireless interference models. Given a set Q of periodic aggregation queries, each query Q_i ∈ Q has its own period pi and the subset of source nodes Si containing the data. We first propose a family of efficient and effective real-time scheduling protocols that can answer every job of each query task Q_i ∈ Q within a relative delay O(p_i) under resource constraints by addressing the following tightly coupled tasks: routing, transmission plan constructions, node activity scheduling, and packet scheduling. Based on our protocol design, we further propose schedulability test schemes to efficiently and effectively test whether, for a set of queries, each query job can be finished within a finite delay. Our theoretical analysis shows that our methods achieve at least a constant fraction of the maximum possible total utilization for query tasks, where the constant depends on wireless interference models. We also conduct extensive simulations to validate the proposed protocol and evaluate its practical performance. The simulations corroborate our theoretical analysis.