Significant advances of wireless communication technologies enable many innovative and exciting wireless networking applications, which will penetrate every aspect of our lives, changing the way we talk, work, play, and commute. Increasingly, these emerging applications require stringent delay guarantees to achieve the desired performance. Just to name a few examples: military command-and-control in the battlefield, video streaming over a wireless mesh network, and vehicular networks for highway safety. Clearly, the key to the success of these wireless networking applications is to ensure that delay-sensitive data are delivered to the recipient before the deadline expires. Unfortunately, our current understanding of how to support delay-sensitive applications on wireless networks is fairly limited. Delay-guarantees in 2G cellular networks is mainly provided by a circuit-switched paradigm, assisted by power control. For the newer packet-based wireless networks and ad hoc networks, it remains an open problem how to efficiently provide delay-guarantees. Compared to wireline networks, the delay problem in wireless networks is more challenging because: (1) The wireless channel is error-prone, suffering from frequent degradation due to interference, fading and user mobility. (2) The protocol layers of wireless networks interact with each other in complex ways, compounding the delay control problem. (3) The spectrum resource is scarce, and hence over-provisioning is usually not an option. Combined, these issues pose a great amount of challenge to provide delay performance guarantees required by these applications, while maintaining high-capacity and highly-efficient operation of the network at the same time.
We have developed a new theoretical foundation for supporting delay-sensitive applications on wireless networks. Our goal is to build an advanced suite of theory and algorithms for understanding delay performance and for designing efficient and low-delay algorithms/protocols tailored to application-specific needs. Specifically, we have used large-deviation theory to study the delay performance of queue-length-based wireless scheduling algorithms. Compared with other approaches such as expected delay analysis, large-deviation theory can potentially provide more refined characterization of the delay performance, e.g., to control small delay-violation probabilities. However, a key difficulty in applying large-deviation theory to queue-length-based scheduling algorithms is the embedded multi-dimensional calculus-of-variations (CoV) problem for computing the most-likely-path-to-overflow. In our work, we have used a novel idea of combining Lyapunov functions with large-deviation theory. This technique can map the multi-dimensional CoV problem to a one-dimensional CoV problem, which is then much easier to solve. Using this technique, we have been able to provide sharp bounds on the queue-overflow probability and delay-violation probability for important classes of wireless scheduling algorithms, including the max-weight algorithm and the back-pressure algorithm. Further, for the first time in the literature, we have been able to characterize the optimal scheduling algorithms subject to a given delay constraint.
This marriage between Lyapunov functions and large-deviation theory can potentially develop into a powerful theory to analyze sophisticated cross-layer wireless control algorithms. Possible future directions include: (1) to study the delay-performance on wireless multi-hop networks; (2) to develop a theory for exploiting multi-channel systems to achieve low delays; and (3) to study new cross-layer network control architectures to support applications with delay constraints. This work is supported by the NSF CAREER Award.
Selected publications: