TY - JOUR
T1 - Network Design under General Wireless Interference
AU - Halldórsson, Magnús M.
AU - Kortsarz, Guy
AU - Mitra, Pradipta
AU - Tonoyan, Tigran
N1 - Publisher Copyright: © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2021/11
Y1 - 2021/11
N2 - We introduce the problem of finding a spanning tree along with a partition of the tree edges into the fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close—thus, the available pairs are specified with a link graph G= (V, E). Also, signal attenuation need not follow a nice geometric formula—hence, interference is modeled by a conflict (hyper)graph C= (E, F) on the links. The objective is to maximize the efficiency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the conflict graph. Specifically, we give a simple algorithm that attains a O(ρlog n) -approximation, where n is the number of nodes and ρ is the inductive independence. For an extension to Steiner trees, modeling multicasting, we obtain a O(ρlog 2n) -approximation. We also consider a natural geometric setting when only links longer than a threshold can be unavailable, and analyze the performance of a geometric minimum spanning tree.
AB - We introduce the problem of finding a spanning tree along with a partition of the tree edges into the fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close—thus, the available pairs are specified with a link graph G= (V, E). Also, signal attenuation need not follow a nice geometric formula—hence, interference is modeled by a conflict (hyper)graph C= (E, F) on the links. The objective is to maximize the efficiency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the conflict graph. Specifically, we give a simple algorithm that attains a O(ρlog n) -approximation, where n is the number of nodes and ρ is the inductive independence. For an extension to Steiner trees, modeling multicasting, we obtain a O(ρlog 2n) -approximation. We also consider a natural geometric setting when only links longer than a threshold can be unavailable, and analyze the performance of a geometric minimum spanning tree.
KW - Connectivity
KW - Network Design
KW - Scheduling
KW - Wireless interference
UR - http://www.scopus.com/inward/record.url?scp=85112211145&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85112211145&partnerID=8YFLogxK
U2 - 10.1007/s00453-021-00866-z
DO - 10.1007/s00453-021-00866-z
M3 - Article
SN - 0178-4617
VL - 83
SP - 3469
EP - 3490
JO - Algorithmica
JF - Algorithmica
IS - 11
ER -