Towards Predictable Real-Time Routing for Wireless Networked Sensing and Control

Download Now Date Added: Mar 2011
Format: PDF

Real-time routing is a basic element of closed-loop, real-time sensing and control, but it is very challenging due to dynamic, uncertain link/path delay. A basis of real-time routing is determining probabilistically guaranteed path delays, but this problem is NP-hard and it may well have to be solved by resource-constrained devices in a distributed manner; the highly varying nature of link/path delay makes it necessary to adapt to in-situ delay conditions in real-time routing, but it has been observed that delay-based routing can lead to instability and low data delivery performance in general. To address these challenges, the authors propose the Minimum-Delay (MD) algorithm that computes probabilistic path delay bounds in pseudo-polynomial time via dynamic programming, and the algorithm is amenable to lightweight, distributed implementation.