« June 2017 »
Home Research Robust Optimization Methodologies for Wireless Network Planning

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 (inter-cell 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.


Signal propagation
Figure 1: Considered network setting.
Figure 2: Signal propagation data.

Optimization Problem

Robust Optimization

An aspect which should be considered already in the planning of a wireless network are non-deterministic 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.

Traffic fluctuations
Figure 3: Traffic fluctuations in a telecommunication network in time intervals of 5 minutes during one week for three traffic demands.


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 non-integer solutions, branch-and-price 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.