TY - JOUR

T1 - Computing and maximizing the exact reliability of wireless backhaul networks

AU - Coudert, David

AU - Luedtke, James

AU - Moreno, Eduardo

AU - Priftis, Konstantinos

N1 - Funding Information:
This research has been supported by ANR program ANR-11-LABX-0031-01 (D.C.), Fondecyt grant 1161064 (E.M), National Science Foundation SES-1422768 (J.L.) and Associated Team Inria AlDyNet (D.C, E.M.).
Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2018/2

Y1 - 2018/2

N2 - The reliability of a fixed wireless backhaul network is the probability that the network can meet all the communication requirements considering the uncertainty (e.g., due to weather) in the maximum capacity of each link. We provide an algorithm to compute the exact reliability of a backhaul network, given a discrete probability distribution on the possible capacities available at each link. The algorithm computes a conditional probability tree, where at each leaf in the tree a valid routing for the network is evaluated. Any such tree provides bounds on the reliability, and the algorithm improves these bounds by branching in the tree. We also consider the problem of determining the topology and configuration of a backhaul network that maximizes reliability subject to a limited budget. We provide an algorithm that exploits properties of the conditional probability tree used to calculate reliability of a given network design, and we evaluate its computational efficiency.

AB - The reliability of a fixed wireless backhaul network is the probability that the network can meet all the communication requirements considering the uncertainty (e.g., due to weather) in the maximum capacity of each link. We provide an algorithm to compute the exact reliability of a backhaul network, given a discrete probability distribution on the possible capacities available at each link. The algorithm computes a conditional probability tree, where at each leaf in the tree a valid routing for the network is evaluated. Any such tree provides bounds on the reliability, and the algorithm improves these bounds by branching in the tree. We also consider the problem of determining the topology and configuration of a backhaul network that maximizes reliability subject to a limited budget. We provide an algorithm that exploits properties of the conditional probability tree used to calculate reliability of a given network design, and we evaluate its computational efficiency.

KW - Backhaul network

KW - Network design

KW - Optimization

KW - Reliability

UR - http://www.scopus.com/inward/record.url?scp=85042361648&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2018.01.010

DO - 10.1016/j.endm.2018.01.010

M3 - Article

AN - SCOPUS:85042361648

SN - 1571-0653

VL - 64

SP - 85

EP - 94

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -