Real-Time Query Scheduling for Wireless Sensor Networks

Recent years have seen the emergence of wireless cyber-physical systems that must support real-time queries of physical environments through wireless sensor networks. This paper proposes Real-Time Query Scheduling (RTQS), a novel approach to conflict-free transmission scheduling for real-time queries in wireless sensor networks. First, we show that there is an inherent tradeoff between latency and real-time capacity in query scheduling. We then present three new real-time schedulers. The nonpreemptive query scheduler supports high real-time capacity but cannot provide low response times to high-priority queries due to priority inversions. The preemptive query scheduler eliminates priority inversions at the cost of reduced capacity. The slack stealing query scheduler combines the benefits of the preemptive and nonpreemptive schedulers to improve the capacity while meeting the end-to-end deadlines of queries. We provide schedulability analysis for each scheduler. The analysis and advantages of our approach are validated through NS2 simulations.