Robust Optimization Methodologies for Wireless Network Planning
The Wireless Network Planning Problem
The planning of wireless networks remains a crucial and complex problem in the future not least due to rising traffic demands. The problem consists of base station (BS) placement and traffic node (TN) assignment to BSs fulfilling the required bit rates. Moreover, two conflicting BSs (intercell interference) cannot be installed at the same time and each TN can only be served by at most one BS (hard handover), see Figure 1 for the total network setting. The power consumption of wireless networks is, not only from an ecological but also from a financial point of view, an important factor. Therefore, the objective of the wireless network planning problem is to minimize the total power consumption of the network while minimizing the number of not covered TNs. Signal propagation data is needed to determine the possible links between BSs and TNs, see Figure 2.


Figure 1: Considered network setting. 
Figure 2: Signal propagation data. 
Optimization Problem
min 
power consumption + number of not covered TNs 
subject to 
assignment of TNs to at most one BS 
intercell interference limitation via conflict graph 

capacity constraints of BSs 
Robust Optimization
An aspect which should be considered already in the planning of a wireless network are nondeterministic factors, e.g., user mobility, fluctuating bit rate requirements (see Figure 3) and channel conditions. To handle such uncertainties, robust optimization is a recently proposed technique. For uncertain factors with an unknown probability distribution, Bertsimas and Sim introduced the Γrobustness approach which limits the number of uncertain entries by a robustness parameter Γ.
Following this approach, fluctuating TN demands are modeled as symmetric and bounded random variables taking values in the interval [N − D, N + D] with an unknown distribution, where N is the nominal demand, D the highest deviation, and N + D the peak demand. For this setting, the robustness parameter Γ limits the number of demand values per BS that can deviate from their nominal value simultaneously.
Figure 3: Traffic fluctuations in a telecommunication network in time intervals of 5 minutes during one week for three traffic demands. 
Approaches
The Integer Linear Programs (ILPs) modeling the planning of robust wireless networks are in general computationally not tractable. Therefore, advanced optimization methodologies are applied such as cutting planes to cut off noninteger solutions, branchandprice to limit the number of variables, and (primal) heuristics to find good solutions fast.
This is a joint project with Prof. Arie M.C.A. Koster, Lehrstuhl II für Mathematik, RWTH Aachen University.