IAA: Interference Aware Anticipatory Algorithm for Scheduling and Routing Periodic Real-Time Streams in Wireless Sensor Networks

Download Now Date Added: Dec 2009
Format: PDF

This paper provides a polynomial time heuristic for the real-time communication scheduling problem in multi-hop wireless sensor networks. Wireless networks add a new dimension to the real-time communication problem because of interference: a transmission cannot be scheduled on a radio link if another transmission is scheduled on any interfering link. The problem being NP-hard in nature, the authors propose a novel heuristic that comes into two parts: a scheduler that uses a topological analysis of the network to anticipate the effects of radio interference in order to improve scheduling prioritization and an iterative route update scheme that pushes apart interfering streams and spreads them out over the network to reduce interference and improve schedulability while meeting the deadline requirements.