Designing least-cost survivable wireless backhaul networks

This paper presents a new heuristic algorithm for designing least-cost tele communications networks to carry cell site traffic to wireless switches whi le meeting survivability, capacity, and technical compatibility constraints . This requires solving the following combinatorial optimization problems s imultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; ( 2) Optimally assign traffic from other nodes to these hubs, so that the tra ffic entering the network at these nodes is routed to the assigned hubs whi le respecting capacity constraints on the links and routing-diversity const raints on the hubs to assure survivability; and\break (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based o n the capacities and costs associated with each link type. Each of these op timization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuri stic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such "backhaul networks" for carrying person al communications services (PCS) traffic. It solves problems that are chall enging for conventional branch-and-bound solvers in minutes instead of hour s and finds lower-cost solutions. Applied to real-world network design prob lems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.