Interference-Aware Real-Time Flow Scheduling for Wireless Sensor Networks

Octav Chipara1,  Chengjie Wu2,  Chenyang Lu2,  William G. Griswold1
1University of California San Diego, 2Washington University in St. Louis


With the emergence of wireless sensor networks an enabling communication technology for distributed real-time systems, we face the critical challenge of meeting the end-to-end deadlines of real-time flows. This paper presents Real-time Flow Scheduling (RFS), a novel conflict-free real-time transmission scheduling approach for periodic real-time flows in wireless sensor networks. In contrast to existing transmission scheduling algorithms that ignore interference between transmissions or prevent spatial reuse within a same channel, RFS supports spatial reuse through a novel interference-aware transmission scheduling. While recent work on conflict-free transmission scheduling focused on specialized communication patterns such as queries and converge cast, RFS is designed for peer-to-peer real-time flows with arbitrary inter-flow interference. Moreover, RFS features several novel contributions that makes it particularly suitable for distributed real-time systems: RFS provides a real-time schedulability analysis that accounts for interference between real-time flows. Second, RFS improves reliability by incorporating retransmissions in a flexible scheduling scheme. Finally, RFS enhances scalability by dividing the network into neighborhoods and provides real-time performance for flows crossing multiple neighborhoods through a novel application of Release Guard. RFS was evaluated through simulations based on the traces collected from an indoor sensor network testbed. Compared with a traditional TDMA protocol, RFS reduces flow latencies by up to two orders of magnitude, while improving the real-time capacity by as much as 3.5 times.