Complexity in wireless scheduling: Impact and tradeoffs

Yung Yi, Alexandre Proutière, Mung Chiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations

Abstract

It has been an important research topic since 1992 to maximize stability region in constrained queueing systems, which includes the study of scheduling over wireless ad hoc networks. In this paper, we propose a framework to study a wide range of existing and future scheduling algorithms and characterize the achieved tradeoffs in stability, delay, and complexity. These characterizations reveal interesting properties hidden in the study of any one or two dimensions in isolation. For example, decreasing complexity from exponential to polynomial, while keeping stability region the same, generally comes at the expense of exponential growth of delays. Investigating trade-offs in the 3-dimensional space allows a designer to fix one dimension and vary the other two jointly. For example, incentives for using scheduling algorithms with only partial throughput-guarantee can be quantified with regards to delay and complexity. Tradeoff analysis is then extended to systems with congestion control through utility maximization for non-stabilizable arrival inputs, where the complexity-utility-delay trade-off is shown to be different from the complexity-stability-delay tradeoff. Finally, we analyze more practical models with bounded message size, and consider "effective throughput" which reflects resource occupied by control messages. We show that effective throughput may degrade significantly in certain scheduling algorithms, and suggest a mechanism to avoid this problem in light of the 3D tradeoff framework.

Original languageEnglish (US)
Title of host publicationProceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08
Pages33-42
Number of pages10
DOIs
StatePublished - Dec 15 2008
Event9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08 - Hong Kong SAR, China
Duration: May 26 2008May 30 2008

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Other

Other9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08
CountryChina
CityHong Kong SAR
Period5/26/085/30/08

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Complexity in wireless scheduling: Impact and tradeoffs'. Together they form a unique fingerprint.

  • Cite this

    Yi, Y., Proutière, A., & Chiang, M. (2008). Complexity in wireless scheduling: Impact and tradeoffs. In Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing 2008, MobiHoc'08 (pp. 33-42). (Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)). https://doi.org/10.1145/1374618.1374624