A Primal-Dual Algorithmic Aspect of Link Scheduling in Dynamic Wireless Networks

Ya Chun Liang, Chung Shou Liao, Xinping Yi

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

Abstract

In this paper, we consider a primal-dual algorithmic aspect of the link scheduling problem in dynamic wireless networks, where the channel characteristics are dramatically time-varying that could render state-of-the-art link scheduling mechanisms computational expensive to fit network dynamics. Building upon the optimality condition of treating interference as noise, we formulate link scheduling as a maximum weighted clique problem on a coexisting graph, which can be transformed into a minimum weighted vertex coloring problem (MWVCP) through the primal-dual technique. With an adversarial perturbation modeling of network dynamics with edge insertion/deletion, we propose dynamic graph algorithms to solve the MWVCP for chordal graph classes with theoretical guarantees on algorithmic feasibility, optimality, and updating complexity. It is expected the resulting link scheduling mechanism could shed light on robust, scalable, and certifiable system designs in dynamic wireless networks from the algorithmic perspective.

Original languageEnglish
Title of host publication2023 IEEE International Symposium on Information Theory, ISIT 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2559-2564
Number of pages6
ISBN (Electronic)9781665475549
DOIs
Publication statusPublished - 2023
Event2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan
Duration: 2023 Jun 252023 Jun 30

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2023-June
ISSN (Print)2157-8095

Conference

Conference2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/TerritoryTaiwan
CityTaipei
Period23-06-2523-06-30

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modelling and Simulation
  • Applied Mathematics

Cite this