Providing Guaranteed Protection in Multi-Hop Wireless Networks with Interference Constraints

摘要

We consider the problem of providing protection against failures in wireless networks subject to interference constraints. Typically, protection in wired networks is provided through the provisioning of dedicated backup paths. This approach has not been previously considered in the wireless setting due to the prohibitive cost of backup capacity. Assigning capacity for dedicated backup paths in a wireless setting can more than double the total resources required from what was needed without protection, which can make protection infeasible. However, we show that in the presence of interference, guaranteed protection can be provided for all demands with little, and oftentimes no , additional resources beyond what was required without any protection. This is due to the fact that after a failure, links that previously interfered with the failed link can be activated, thus leading to a “recapturing” of lost capacity. We provide an ILP formulation to find an optimal solution for both binary and SINR interference constraints, and develop corresponding time-efficient algorithms. Our approach utilizes up to 87 percent less protection resources than traditional disjoint path routing to provide guaranteed protection. For the case of 2-hop interference, our protection scheme requires only 8 percent more resources on average than providing no protection whatsoever.