NEDG: Locally-optimal Power, Rate Adaptation and Scheduling in Wireless Networks

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The growth of communication networks has profoundly increased the availability of information and increased productivity. A key requirement in continuing to reap the benefits of connectivity is the growth of pervasive wireless networks. Wireless networks are resource constrained, primarily due to their broadcast nature. Alleviation of this constraint requires an efficient, distributed solution to the Medium Access Control (MAC) problem. In this project, the investigators study `locally-optimal scheduling and PHY adaptation', by incorporating physical layer (PHY) models into maximal scheduling for increased accuracy, and priority mechanisms for increased efficiency. This will result in the design of efficient, distributed MAC protocols, whose guarantees are accurate, from the PHY perspective. The results from this research, which is training a graduate Ph.D., are disseminated through appropriate publications and seminars, to guide the development of future wireless network MAC protocols and are incorporated into the university?s undergraduate and graduate courses. PHY adaptation and scheduling (MAC) in general ad hoc wireless networks, is an NP-hard problem, especially, if distributed solutions are desired. In this project, the investigators study locally-optimal algorithms, a generalization of maximal scheduling, using broad queuing results that prove stability, and adapt them to wireless networks, with careful attention paid to the PHY model. Theoretical characterization of the performance of these algorithms is carried out using graph theoretic and optimization theoretic analysis, along with intuition on the design of optimal (though, centralized) MAC algorithms. The key ideas of this research, which are at the intersection of communication theory, queuing theory, graph theory and optimization, are incorporated into university courses, using the concepts of Lyapunov functions and fluid models.