Distributed Real-Time Data Aggregation Scheduling in Duty-Cycled Multi-hop Sensor Networks

Wireless sensor network (WSN) systems often need to support real time periodic queries of physical environments. In this work, we focus on periodic queries with sufficiently long time horizon in duty-cycled sensor networks. For each periodic query issued by a control center in a WSN, after the source sensors produced the sensory data, the data are to be sent to the sink via multi-hop data aggregation timely in a periodic fashion. To this end, we propose efficient and effective data aggregation algorithms subject to quality of service constraints such as deadline requirements and interference constraints. We decompose these into three sequential operations: (1) aggregation tree construction (2) node and link-level scheduling and (3) packet scheduling. Inspired by the scheduling algorithms, we identify both sufficient conditions and necessary conditions for scheduling multiple queries. The schedulability analysis under various interference models demonstrate that the proposed algorithms achieve an approximate proportion of the maximum possible load.