Nokia Siemens: Two-Dimensional Packing Problems in Telecommunications


2006 to 2009

In telecommunication systems adopting the IEEE 802.16/WiMAX standard, a series of Wireless Broadband standards authored by the Institute of Electrical and Electronics Engineers, a fixed station transmits and receives data packets to and from other stations, as pictorially shown in Figure 1. All transmissions are performed using [time × frequency] rectangular frames, which are called downlink zones. In the main model considered here each data packet is assigned a frequency of transmission, and it is stored in the downlink zone as a rectangle having a width (time) sufficient to transmit all data. In other words, a data packet can be stored in many different ways, corresponding to different [time × frequency] rectangles having a size sufficient to contain it.

The fixed station must maximize the frame utilization by

(i)             selecting the packets to be included in the next transmission phase;

(ii)           arranging each selected packet into one or more rectangular regions, and

(iii)          allocating the resulting regions to the frame without overlapping.

The Nokia (later Nokia Siemens) research group in charge of designing an efficient scheduler for the base station realized that no satisfactory method was available in literature. They thus contacted two research groups: the computer networking group of the University of Pisa and the combinatorial optimization group of the University of Bologna, and started a 2-year joint research project. It quickly emerged that Steps (ii) and (iii) above identify a special two-dimensional bin packing problem, not studied earlier in the combinatorial optimization literature.