Topological Interference Management With Adversarial Topology Perturbation: An Algorithmic Perspective

Liang, Ya-Chun, Liao, Chung-Shou and Yi, Xinping ORCID: 0000-0001-5163-2364 (2022) Topological Interference Management With Adversarial Topology Perturbation: An Algorithmic Perspective. IEEE TRANSACTIONS ON COMMUNICATIONS, 70 (12). pp. 8153-8166.

Text
TIM-ANP.pdf - Author Accepted Manuscript
Download (5MB) | Preview

Official URL: http://dx.doi.org/10.1109/tcomm.2022.3216632

Abstract

In this paper, we consider the topological interference management (TIM) problem in a dynamic setting, where an adversary perturbs network topology to prevent the exploitation of sophisticated coding opportunities (e.g., interference alignment). Focusing on a special class of network topology - chordal networks - we investigate algorithmic aspects of the TIM problem under adversarial topology perturbation. In particular, given the adversarial perturbation with respect to edge insertion/deletion, we propose a dynamic graph coloring algorithm that allows for a constant number of re-coloring updates against each inserted/deleted edge to achieve the information-theoretic optimality. This is a sharp reduction of the general graph re-coloring, whose optimal number of updates scales as the size of the network, thanks to the delicate exploitation of the structural properties of chordal graph classes.

Item Type:	Article
Additional Information:	(c) 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Uncontrolled Keywords:	Network topology, Interference, Topology, Perturbation methods, Vehicle dynamics, Time division multiple access, Heuristic algorithms, Topological interference management (TIM), weakly chordal graph, chordal graph, adversarial perturbation model, dynamic coloring
Depositing User:	Symplectic Admin
Date Deposited:	21 Oct 2022 08:56
Last Modified:	16 Mar 2024 02:41
DOI:	10.1109/TCOMM.2022.3216632
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3165689