Wireless coverage prediction via parametric shortest paths

TY - GEN

T1 - Wireless coverage prediction via parametric shortest paths

AU - Applegate, David

AU - Archer, Aaron

AU - Johnson, David S.

AU - Nikolova, Evdokia

AU - Thorup, Mikkel

AU - Yang, Ger

PY - 2018/6/26

Y1 - 2018/6/26

N2 - When deciding where to place access points in a wireless network, it is useful to model the signal propagation loss between a proposed antenna location and the areas it may cover. The indoor dominant path (IDP) model, introduced by Wölfle et al., is shown in the literature to have good validation and generalization error, is faster to compute than competing methods, and is used in commercial software such as WinProp, iBwave Design, and CellTrace. The previous algorithms known for computing it involved a worst-case exponential-time tree search, with pruning heuristics for speed. We prove that the IDP model can be reduced to a parametric shortest path computation on a graph derived from the walls in the floorplan. It therefore admits a quasipolynomial-time (i.e., nO(log n) ) algorithm. Moreover, we give a practical approximation algorithm based on running a small constant number of shortest path computations. Its provable worst-case additive error (in dB) can be made arbitrarily small, and is well below 1dB for reasonable choices of parameters. We evaluate this algorithm empirically against the exact IDP model, showing that it consistently beats its theoretical worst-case bounds, solving the model exactly (i.e., no error) in the vast majority of cases.

AB - When deciding where to place access points in a wireless network, it is useful to model the signal propagation loss between a proposed antenna location and the areas it may cover. The indoor dominant path (IDP) model, introduced by Wölfle et al., is shown in the literature to have good validation and generalization error, is faster to compute than competing methods, and is used in commercial software such as WinProp, iBwave Design, and CellTrace. The previous algorithms known for computing it involved a worst-case exponential-time tree search, with pruning heuristics for speed. We prove that the IDP model can be reduced to a parametric shortest path computation on a graph derived from the walls in the floorplan. It therefore admits a quasipolynomial-time (i.e., nO(log n) ) algorithm. Moreover, we give a practical approximation algorithm based on running a small constant number of shortest path computations. Its provable worst-case additive error (in dB) can be made arbitrarily small, and is well below 1dB for reasonable choices of parameters. We evaluate this algorithm empirically against the exact IDP model, showing that it consistently beats its theoretical worst-case bounds, solving the model exactly (i.e., no error) in the vast majority of cases.

U2 - 10.1145/3209582.3209605

DO - 10.1145/3209582.3209605

M3 - Article in proceedings

SN - 978-1-4503-5770-8

SP - 221

EP - 230

BT - Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Mobihoc '18

PB - ACM

T2 - 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing

Y2 - 26 June 2018 through 29 June 2018

ER -