Real-time query scheduling for wireless sensor networks
Technology Implementation: JAVA
Recent years have seen the emergence of wireless sensor network systems that must support high data rate and realtime queries of physical environments. 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 trade-off between prioritization and throughput in conflict-free query scheduling. We then present three new real-time scheduling algorithms. The non-preemptive query scheduling algorithm achieves high throughput while introducing priority inversions. The preemptive query scheduling algorithm eliminates priority inversion at the cost of reduced throughput. The slack stealing query scheduling algorithm combines the benefits of preemptive and non-preemptive scheduling by improving the throughput while meeting query deadlines.
Real-time communication protocols can be categorized into contention-based and TDMA-based protocols. Contention-based protocols support real-time communication through probabilistic differentiation. This is usually achieved by adapting the parameters of the CSMA/CA mechanism such as the contention window and/or initial back-off.
Rate and admission control have also been proposed for contention-based protocols to handle overload conditions. However, contention-based approaches have two inherent drawbacks that make them unsuitable for high data rate and real-time applications. First, packet latencies are highly variable due to the random backoff mechanisms. Second, their maximum throughput is low due to channel contention under heavy load. TDMA protocols can provide predictable packet latencies and achieve higher throughput than contention-based protocols under heavy load. The IEEE 802.15.4 standard for WSNs has a reservation mechanism for providing predictable delays in single hop networks.
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Link scheduling and Node scheduling were carried out
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Low throughput
ÃƒÂ¯Ã‚ÂÃ‚Â¶ High latency
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Not suitable for dynamic applications with variable and non-uniform workloads
The proposed algorithm achieves
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Query scheduling has an inherent tradeoff between prioritization and throughput.
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Derive latency upper bounds for each scheduling algorithm.
ÃƒÂ¯Ã‚ÂÃ‚Â¶ This enables us to guarantee that the admitted queries meet their deadlines.
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Query scheduling assign slots to transmissions based on the specific communication patterns
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Efficiently adapt to changes in workloads by exploiting explicit query information provided by the query service
ÃƒÂ¯Ã‚ÂÃ‚Â¶ Adapts local scheduling algorithm that can accommodate changes in query rates without explicitly reconstructing the schedule.