Robust Optimization in Dense WLANs under user mobility and rate uncertainty

(1)

Dipartimento di Informatica

Corso di Laurea Specialistica in Computer Science and Networking

Computer Science and Networking

Robust Optimization in Dense

WLANs under user mobility and

rate uncertainty

Supervisors:

Rosario Garroppo

Maria Grazia Scutell`

a

Candidate:

Thomas Fiorenzani

(2)

Ai miei genitori che mi hanno

sempre supportato ed hanno sempre

creduto in me

Alle persone a me vicine durante

questo mio percorso universitario

A Flavia per avermi spronato ed

aiutato con una grande forza

d’animo

(3)

Desidero ringraziare tutti coloro che hanno svolto un ruolo fondamentale nella stesura della mia tesi, a loro va tutta la mia gratitudine.

In particolare, desidero ringraziare Rosario Giuseppe Garroppo e Maria Grazia Scutell`a i cui consigli sono stati preziosi per portare a termine nel miglior modo possibile questo lavoro.

Un ringraziamento va sicuramente ai miei genitori e alla mia fidanzata che mi hanno supportato e sopportato durante il periodo della tesi; a loro va tutta la mia gratitudine e tutto il mio affetto.

Un ringraziamento particolare a tutti i professori incontrati nel mio percorso di studi, grazie ai quali ho potuto ampliare le mie competenze e la mia passione per il Network-ing.

(4)

Abstract

This Thesis aims to evaluate robust optimization under users mobility in Dense WLANs; this work is a continuation of what has already begun by A. Massida. In that Thesis, he shall exploit the robust optimization paradigm to deal with uncertainty aspects in real application contexts, such as the Green WLAN (see [10]). The concept of Local Area Network is the first step to the WLANs, which introduce the use of mobile devices and, as a consequence, the deployment of this kind of infrastructure. These networks are implemented with several access points (APs) that provide wireless connectivity to user terminals (UTs) located in the area. In this scenario, it is possible to switch off some APs guaranteeing the same UTs coverage as if the network was working at full power. The idea is to connect UTs to the minimum number of APs, in order to power off some of them to save energy. This problem must take into account two uncertain factors, like wireless instability and user mobility; hence, we should take into account that users roam across the service area. This last feature has a notable impact to channel capacity, which in turn strongly depends on the UT-AP distance. The models described in this work are evaluated exploiting CPLEX solver, it enables rapid development and deployment of decision optimization models using mathematical and constraint programming. First of all, we investigate the problem of switch off some APs to minimize power consumption in dense WLANs, granting power savings. The just mentioned problem can be formulated as an Integer Linear Programming (ILP) and solved by CPLEX. Anyway, we can have difficulties to solve this problem in short amount of time, as required in real WLAN environments; a proper setting of CPLEX parameters can help us to compute solutions in a reasonable time with reasonable power savings. Then we investigate a heuristic to manipulate the number of access points that are not switched off, and finally, we implement a simple reallocation algorithm to increase the number of feasible future solutions after CPLEX evaluation.

(5)

Acknowledgements ii

Abstract iii

Contents iv

List of Figures vi

List of Tables vii

1 Introduction 1

2 Networking Background 3

2.1 IEEE 802.11 . . . 3

2.2 Radio Transmission . . . 11

2.3 Attenuation in Radio Transmission . . . 13

2.4 Fading effects due to reflection . . . 15

2.5 MAC throughput in indoor environment . . . 17

3 Mathematical Programming 20 3.1 Linear Programming . . . 22

3.2 Integer Linear Programming . . . 24

3.3 Robust Optimization . . . 30

4 Problem formulation 38 4.1 Nominal model . . . 40

4.2 Basic robust model . . . 42

4.3 Multiband robust model . . . 45

(6)

Contents

5 Experimental results 54

5.1 Architecture of the simulation tool . . . 56

5.2 Performance comparison for different CPLEX settings . . . 60

5.3 Mathematical heuristic results . . . 63

5.4 Robust models performance . . . 66

5.5 Reallocation algorithm . . . 74

5.5.1 High UAR . . . 74

5.5.2 Low UAR . . . 77

6 Conclusions 81

(7)

2.1 IEEE 802.11 architecture . . . 4

2.2 DCF mechanism . . . 6

2.3 RTS-CTS mechanism . . . 7

2.4 Channel Division in the 2.4 GHz band . . . 9

2.5 Allocation of OFDM channels . . . 9

2.6 Multipath propagation . . . 16

2.7 Prediction Error and PDR as a function of SNR . . . 18

3.1 LP and ILP . . . 24

3.2 An example of convex envelope . . . 26

5.1 CT and PC models comparison . . . 64

5.2 Type solutions of the multiband model without heuristic . . . 66

5.3 Type solutions of the basic robust model without heuristic . . . 67

5.4 Type solutions of the multiband model with heuristic . . . 68

5.5 Type solutions of the basic robust model with heuristic . . . 68

5.6 Power ratio without heuristic . . . 70

5.7 Power ratio with heuristic . . . 70

5.8 Future Feasibility of the two robust models without heuristic . . . 73

5.9 Future Feasibility without the mathematical heuristic in high UAR . . . 74

5.10 Future Feasibility with the mathematical heuristic in high UAR . . . 75

5.11 Future Feasibility without the mathematical heuristic in low UAR . . . 77

(8)

List of Tables

2.1 802.11g summary values . . . 19 5.1 Configurations . . . 56 5.2 Nominal model . . . 60 5.3 Basic model . . . 61 5.4 Multiband model . . . 61

5.5 Performance comparison with the heuristic . . . 64

5.6 Power Consumption for robust models without heuristic . . . 69

5.7 Power Consumption for robust models with heuristic . . . 70

5.8 Computational Time for robust models without heuristic . . . 71

5.9 Computational Time for robust models with heuristic . . . 72

5.10 Comparison between the two robust models in low UAR scenarios (with-out heuristic) . . . 79

5.11 Comparison between the two robust models in low UAR scenarios (with heuristic) . . . 79

(9)

Introduction

This Thesis focuses on Local Area Networks (LANs), in particular on the possibility to exchange data through portable devices. The concept of mobility in LANs started with IEEE 802.11 Standards, a set of protocol stacks that define physical and data-link layers for interoperability in Wireless LANs (WLANs). The deployment of this kind of infrastructure is growing up thanks to the increase of mobile devices use.

This type of networks is equipped with Access Points (APs) that provide coverage for User Terminals (UTs) attached to them, thanks to wireless connectivity. The en-ergy power used to provide connectivity across the area is not negligible in large-sized WLANs, so the importance to guarantee power saving preserving wireless connectivity is a central point of these infrastructures.

The key point is to act on the AP - UT associations to achieve considerable energy power savings while preserving the same coverage and quality level as if the networks were running at full power. The problem with this idea is the user mobility and the wireless instability. The former aspect is due to the fact that users can roam across the service area and can have different distances in different instants. The UT - AP distance is of fundamental importance because is an aspect that impacts on link ca-pacity.

The Thesis tackles the problem above and studies some possible solutions, by em-ploying Operations Research (OR). Robust Optimization will be exploited to deal with uncertainty aspects.

(10)

Chapter 1. Introduction

Chapter 2 describes some notions of network background, starting from IEEE 802.11 and radio transmission. The latter aspect regards the attenuation and impact of phys-ical phenomena on wireless link capacities. The last subsection shows the throughput evaluation, to give an idea of its estimation in indoor environments, that we use as simulation area in this Thesis.

Chapter 3 regards Mathematical Programming, an area of Operations Research aiming to solve optimization problems. We start with Linear Programming and Integer Linear Programming, which allows imposing the integrality of some decision variables. The last section regards Robust Optimization, to achieve robustness against elements of uncertainty.

Chapter 4 describes the Mathematical Models evaluated in this Thesis. The first one is a Nominal model, i.e., a mathematical model that not take into account the influence of data uncertainties on the quality and feasibility of the model. The second is a robust mathematical model based on Bertsimas and Sim’s robust framework (described in depth in [6]). The third is a robust mathematical model based on Busing and D’Andreagiovanni’s multiband framework described in [3]. Finally, we present our three strategies, simple heuristic techniques to enhance the results obtained via CPLEX. Chapter 5 presents the simulations we carried out and the results we found, comparing the two robust solutions. The chapter focuses on the effects of three key points. The first concerns the evaluation of some CPLEX settings to understand the behavior of the three models. The second concerns the application of a mathematical heuristic. The third concerns the application of a reallocation algorithm that provides benefits regarding future feasibility in some scenarios.

(11)

Networking Background

The aim of this chapter is to provide the reader proper knowledge about networking. The sections of this chapter start with an introduction of IEEE 802.11 standards. The second aspect is related to the investigation of radio transmission, useful to understand how radio channels can be handled in order to estimate the wireless links performance. Finally, we describe the MAC throughput associated with indoor environments, useful to understand the environment in which we perform the simulations.

2.1 IEEE 802.11

IEEE 802.11 has a precise goal: ”provide wireless connectivity to automatic machinery, equipment or stations that require rapid deployment, which may be hand-held, or which may be mounted on moving vehicles within a local area” [9]. Over the years, the previously mentioned working group has published new versions, some of them used to improve data rate (e.g., 802.11b, 802.11g), while other ones used to solving various kind of problems (e.g., 802.11e for QoS purposes). Useful to our work, it is mentioning the 802.11x. A key feature of this version is the transparent communication among mobile stations. This means that mobility is handled at MAC level. The Network Architecture consists of the following elements:

(12)

Chapter 2. Networking Background

• Basic Service Set (BSS): it is made up of a group of station STA controlled by a single Coordination Function (CF). There are two kinds of CF, the Distributed Coordination Function (DCF) and the Point Coordination Function (PCF). • Independent BSS (IBSS): it is the basic type of network, it includes at least

two APs.

• Extended Service Set (ESS): it interconnects various BSS through a Distri-bution System (DS).

The following figure describes the Network Architecture:

Figure 2.1

(13)

The IEEE 802.11 consists in a MAC sub-layer. This protocol is based on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). According to the DCF, a station (e.g., AP) must sense the medium before sending a frame. The frame is transmitted if the carrier is detected to be idle for a greater time than in a DIFS (Distributed Coordination Function Inter Frame Space), used to the APs to access the medium to send a frame. If APs are not able to send frame (due to a time less than a DIFS), then the backoff process starts. A station computes a random number in the interval [0 , Content Window (CWmin)]. Then this number is multiplied by the

time slot. The result will be the backoff interval, used to set the backoff timer. The station can access the medium as soon as the backoff expires. In this protocol, the Acknowledgement is sent to inform a station that its frame has arrived. This ACK is sent at an interval of time equal to a SIFS (Short Inter Frame Space). If the ACK did not receive, the station schedules a retransmission using the backoff interval; note that every time a transmission fails, the Content Window is doubled until it reaches its maximum value. Next, after a successful transmission, this Window is set to the minimum value.

(14)

Figure 2.2 DCF mechanism

In systems based on medium sensing, the problem of hidden-station can occur. This arises actually when STA A can receive frames both from B and C, but B e C can’t communicate with each other. It means that B and C cannot sense the medium busy if the other sends a frame. As a result, we have a collision as A tries to receive both frames. Two short control frames have been implemented in MAC protocol to avoid this problem. A Request To Send (RTS), sent by the station that wants to transmit (in our case B or C), a Clear to Send (CTS) sent by a receiving station (A), that allows the other one to transmit the frame. The transmitting station sends the RTS during a particular time interval until the CTS is not received. In the next figure, there is a small description of the just mentioned mechanism.

(15)

Figure 2.3

RTS-CTS mechanism

It is possible allowing IEEE 802.11 devices to save energy through the Power Save Mode (PSM). This feature provides the possibility to let in the active mode the wireless interface of a mobile host only for the time necessary to exchange data. For this purpose, the state of a station can be awake or doze: the first one has a significant impact on power consumption, while the latter one has a very low power consumption. So, while in the awake mode, the STA is always ready to exchange data, in doze modality, the STA wakes up for the time necessary to transfer frames with AP. If the Access Point has data to send to the STA, the host has to switch to the awake mode to exchange data.

(16)

Frame structure Frames are divided into three types: management, control, data. The first one has used for association and disassociation, timing, authentication, and de-authentication, the most famous management frame is the beacon. The second ones are the ones used to ACK and handshake (e.g. RTS, CTS). The third ones are used to send data. More in detail the MAC frame consists in a header, a body and a CRC. The Frame Control field is 16 bits long, and it specifies items such as the protocol version, the type of frame; a field useful to label the frame as a frame that arrives from a DS, or a frame that is sent to a DS. Then it contains other fields used to management. The Frame Body contains (for data frames) the Mac Service Data Unit (MSDU), or its fragment, while the CRC includes a 32-bit field for redundancy check calculated over the MAC header and body.

The IEEE 802.11 Physical Layer consists in two sub-layers: Physical Layer Converge Procedure (PLCP) and the Physical Medium Dependent (PMD). The first one provides a mapping of MAC PDUs into frames suitable for user data to transmit and receive information among the associated PMD entities. The latter one describes the method of sending and receiving data through a wireless medium.

PMD sub-layer Some 802.11 standards utilize the 2.400-2.500 GHz band, while the other ones utilize the 4.915-5.825 GHz band. These are renamed “2.4 GHz band” and “5 GHz band” respectively. Each one of these spectrums is sub-divided into channels, with a specific frequency and bandwidth. In particular, the 2.4 GHz band is divided into 14 channels, whose carriers are spaced 5 MHz (except for channel 14, which is spaced 12 MHz from channel 13). This means that no more than three channels can be simultaneously used in the same coverage area without producing interference. The channel numbering of the 5 GHz band is less intuitive than the other because of the differences in regulations between countries. IEEE 802.11b uses channels that are 22 MHz wide, with Direct Sequence Spread Spectrum (DSSS) as the modulation technique. DSSS is a method for taking a data signal of a given bit rate and modulating it into a signal that occupies a much larger bandwidth. It represents 0 and 1 by the symbols -1 and +1 and then multiplies each symbol by a binary pattern of +1s and -1s in order to obtain a digital signal that varies more rapidly and, as a consequence, occupies a larger frequency band. The IEEE 802.11 DSSS physical layer uses a particularly simple form: each binary data bit results in the transmission

(17)

of plus or minus the polarity of the 11-chip Barker sequence. So, given the Barker sequence, [+1,-1,+1,+1,-1,+1,+1,+1,-1,-1,-1], for the transmission of the symbol +1 we should send [+1,-1,+1,+1,-1,+1,+1,+1,-1,-1,-1], while to transmit the symbol -1 we should send [-1,+1,-1,-1,+1,-1,-1,-1,+1,+1,+1]. The Barker sequence provides good immunity to interference and noise as well as some protection against multi-path propagation.

Figure 2.4

Channel Division in the 2.4 GHz band

In IEEE 802.11 the Orthogonal Frequency Division Multiplexing (OFDM) is widely used as a transmission technique. The idea is to split a data flow in N parallel flows, transmitted through a set of N carriers inter-spaced by ∆f Hz, so that the crosstalk effect is null. In order to avoid interferences among sub-carriers, their orthogonality must be guaranteed. OFDM is a combination of modulation and multiplexing. We refer to multiplexing as the sharing of bandwidth with other independent data channels. Here, instead, the whole OFDM channel is split into independent sub-channels (see Figure 2.5). The net result of this added signal robustness is the possibility to reach higher data rates, because of the reduced number of retransmissions.

Figure 2.5

Allocation in OFDM channels

Starting with 802.11n, a trick has been used to increase transmission capacity. Here, the channel size is variable, so it is possible to choose between 20 or 40 MHz. The

(18)

second channel is obtained by merging two 20 MHz channels, reducing the number of non-overlapping channels in the same area. The enlargement of the channel is not the only trick. In this case, the Multiple Input Multiple Output (MIMO) is used, data can be transmitted and received simultaneously through multiple antennas. There are two ways to implement this feature: Spatial Division Multiplexing or Spatial Diversity. In the former, the transmission of the independent data stream is done simultaneously (data throughput increases as the number of antennas is increased). In the latter, there is a replication of the unique data stream (assuming sufficient distance between antennas) to exploit the independent paths, with the net effect of reducing the error probability at the receiver.

PLCP sub-layer The PLCP data provide information to the modulation or coding scheme (MCS) of a frame transmission. The MCS must be fixed, to let every station be able to decode the information successfully. In the PLCP there is a 128-bit preamble useful to receiver synchronization, plus 16-bit of Start Frame Delimiter. The header length is 48 bits, and it contains the modulation used, the frame length and other information.

(19)

2.2 Radio Transmission

Radio systems require knowledge in the propagation of radio waves. The propagation of electromagnetic waves in free space can be divided into three types of propagation: ground waves, space waves, direct waves. The general rule is that the higher the frequency of the wave to be transmitted, the shorter the distance (or range) at which a signal can be received.

The low-frequency signals are propagated as ground waves, and they can be received from long distance and in tunnels.

The higher frequencies contain space waves, and these waves can also be diffracted and reflected in the troposphere or the ionosphere, depending on their frequency. Waves with a frequency above 3GHz propagate direct waves and can be received only in the optical horizon.

Their power determines the range of electromagnetic waves. The strength of electro-magnetic waves decreases as the distance of the transmitter increase. The power P0

of an ideal point-shape source is transmitted uniformly in all direction θ . The constant spatial power density of the transmitter is:

P_T(θ ) = P0

4π = Piso. (2.1)

In the isotropic case, the power density flow F through a sphere with radius d is:

F= P0

4πd2[W /m

2_]. _(2.2)

In the normal case, the main part of an antenna power P(θ ) is transmitted in preferred directions. The antenna efficiency can be accounted as a antenna gain gT(θ ). The

Effective Isotropically Radiated Power (EIRP) is the product PTgT(θ ), and it expresses

the power that an isotropic source must radiate to transmit an equivalent power PT(0)

(20)

P_T(θ ) = gT(θ )

P₀

4π. (2.3)

Naturally, PT(θ ) can be integrated into all direction. Hence, its power flow density

through a sphere of radius d is

F(θ ) = PT(θ )

4πd2 = gT(θ )

P0

(4πd)2. (2.4)

The received power PR an antenna can take of the electromagnetic waves is the product of F and the effective antenna area. It can be expressed by the wavelength λ (in electromagnetic radiation, it is given by the ratio between the speed of light c and the frequency f of the wave) and the gain gR of the receiver antenna

P_R=P0· gT(θ ) · gR (4πd)2 · λ

2_, _(2.5)

where the term

L= ( λ 4πd)

2 _(2.6)

is the free-space path loss. Finally, given −10 log(PR

PT) as the logarithmic representation of the difference PT− PR,

the free-space loss LF in this representation (with c = λ f ) is:

L_F = −10 log gT− 10 log gR+ 20 log f + 20 log d − 20 log

c

(21)

2.3 Attenuation in Radio Transmission

In mobile communication, the free space propagation is of little importance, because of reflective surfaces and obstacles that appear in the transmission path. In this scenario, the two main problems are due to distance and loss of energy because of obstacles. This kind of scenario can be modeled in some way, in this Thesis we refer to the models contained in [1].

One-Slope Model It is the simple model. The path loss is

L_dB= L_0,dB+ 10n log₁₀d. (2.8)

where L0,dB is the path loss obtained at 1 meter distant from the transmitter, and

the path loss exponent n can be determined experimentally using an interpolation procedure.

Dual-Slope Model It is an improvement of the previous one, it has better accuracy, and path loss is divided:

L_dB= L0,dB+      10n1log10d, if 1m < d ≤ dbp 10n1log10dbp+ 10n2log10(ddbp), if d > dbp

This model divides in two part the distance, one line-of-sight and one LOS region that is obstructed. The path loss exponents n1 and n2 are experimentally determined.

(22)

Partitioned Model It is used for office, micro-cells and residential structures, path loss is: L_dB= L0,dB+                  20 log₁₀d, if 1m < d ≤ 10m 20 + 30 log₁₀(₁₀d), if 10m < d ≤ 20m 29 + 60 log₁₀(₂₀d), if 20m < d ≤ 40m 47 + 120 log₁₀(₄₀d), if d > 40m

It uses pre-determined values for the path-loss exponents and breakpoint distances, according to some field cited in [1].

Multi-Wall Model It is used for initial WLANs planning in indoor environments, path loss is:

L_dB= L_C+ L_0,dB+ 20 log₁₀d+ k [k f +2 k f +1−b] f Lf+ Kw

∑

i=1 K_wiL_wi (2.9)

L_C is a constant loss term, the element kf denotes the number of floors that are

penetrated. The b parameter is used to have non-linear effects on the number of floors. Lf derives the loss between adjacent floors. The integer kw is the number of

walls type, where Lwi denotes the loss for the Kwi wall numbers of i-th type.

Average-Wall Model This model follow the previous one, the difference is that the loss is aggregate in a unique parameter Lw, so the path loss will be:

L_dB= L_0,dB+ 20 log₁₀d+ kwLw (2.10)

(23)

2.4 Fading effects due to reflection

Fading refers to fluctuations in the amplitude of a received signal that occurs owing to propagation-related interference. Transmitted signals can arrive at destination phase-shifted over paths of different lengths, and this is caused by scattering and reflection of radio waves on multipath propagation. This interference can distort or even eliminate the signal at the receiver. In radio environment, a receiver can be reached not only on a direct path but also on other paths from different directions (see Figure 2.6). A receiver with two antennas positioned in proximity to each other enables the receiver to pick up the most reliable available signal, to overcome the problem of fading. In the frequency range of mobile radio being considered, changes such as the movement of reflecting objects alter the propagation conditions. So, it is only possible to provide a statistical description of the transmission channel, to take into account fading phenomena.

The Rayleigh Distribution This distribution occurs for the signal envelope on the assumption that components waves are incident on a plane and have the same ampli-tude. This distribution occurs when the receiver has no line-of-sight connection with the transmitter, so the path between them includes the presence of obstacles, like in Figure 2.6. When the environment consist of many objects, Rayleigh Fading is a reasonable model, in which the signal is scattered before it arrives at the destination. The envelope of the channel response has the following distribution density function:

f(x; σr) =

x σ_r2e

−x2

(2σ 2r ), if x > 0 (2.11)

The Rayleigh Fading produce propagation paths that have different reflection and transmission coefficient on the several obstacles and that are of different lengths. This cause phase shifts in incoming paths; fading occurs at an interval of the order of half the wavelength, λ

(24)

Figure 2.6

Multipath propagation

The Rice Distribution In environments in which line-of-sight dominates, the waves have not the same amplitude, so the envelope is better described with the Rice dis-tribution. The envelope of the channel response has the following distribution density function: f(x; σr) = x σ_r2 e −x2+x2s (2σ 2r ) I₀(xxs σ_r2) (2.12)

where I0 is the Bessel function of 1st type and 0th order. Note that the Rayleigh

distribution is a particular case of the Rice distribution when x_s= 0.

This model is well suited for measurements in rural areas: [11] contains a reference table of parameter values for several measures. There is no closed-form solution for the mean value and the variance of the Rice density function. These parameters can only be determined using approximation formulas and tables.

The conclusion is that the former distribution is more suitable for indoor environments like the latter is more suitable in rural areas, where there is a little presence of obstacles.

(25)

2.5 MAC throughput in indoor environment

Starting from the distance di, j between the UT i and AP j is possible to evaluate the

data-rate associated to their link. This connection could be exposed to performance degradation due to phenomena presented in the previous section (2.4). There is a notable difference in evaluating these aspects in rural areas or indoor environments; it is necessary to choose the right models to develop a model that computes the rate a PHY level, based on the environment in which we perform a simulation. The environment assumption in our case is the indoor environment, so we choose:

• Multi Wall Model (section 2.3) : to estimate the path-loss, so destructive effects on the signal. The path-loss is defined in the following way:

PL_mw(di, j) = Pre f+ LC+ 20 log10(di, j) + nw · Lw + ncl · Lcl, (2.13)

where P_{re f} is the path-loss obtained with the default distance d0 set to 1 meter,

in the free-space formula; while LC is the constant loss term. We assume that

the wall types are two: column and wall. Hence, nw is the number of walls, and Lw is the path loss; ncl is the number of columns and Lcl is the path loss. • Rayleigh Fading (section 2.4): to estimate the path-gain, so constructive

ef-fects on the signal. In our case the path-gain associated with the f-quantile of the Rayleigh fading, taking into account also the path-loss, is given by the following formula:

Pg(di, j, f ) = 20 log10(σrp−2 · log(1 − f )) − PL2 mw(di, j). (2.14)

These are useful information because we can exploit them to obtain the Signal-to-Noise-plus-Interference-Radio (SNIR) as follow:

SNIR(di, j, f ) = Pg(di, j, f ) + 10 log10(Pt) − noise, (2.15)

where Pg(di, j, f ) is the last measure taking into account the gain and the

(26)

in dB. The correlation between SNIR and PHY data − rate present no standard def-inition (as discussed in [13]). IEEE 802.11 Standards do not state any detail about the algorithms to be implemented in compliant devices, as a consequence that these algorithms provide different behavior among devices, according to channel conditions; as discussed in [13].

There are several ways to have a possible correlation between SNIR and PHY data − rate, to achieve a realistic estimation, through some experimental studies with com-modity devices. We exploit the test results reported in [13], performing a logarithmic interpolation procedure on such results:

R(di, j, f ) = β · SNIR(di, j, f ) − δ , (2.16)

where R is the resulting maximum theoretical PHY data-rate, expressed in bit_s ; β and δ have been set to 1760 and 7480 respectively. For instance, we consider N input SNIRs, then N PHY data-rate will be calculated.

The following figures show the Average Prediction Error of SNR measurement and the impact of interference on the Packet Delivery Ratio (PDR) as a function of SNR with different transmission rate:

Figure 2.7

Prediction Error and PDR as a function of SNR

Once the data-rate at PHY layer has been estimated, the next step regard to deriving its throughput at MAC layer. To evaluate wireless link capacity, it is necessary to take into account the overhead discussed in section 2.1 for the MAC protocol. The formula of the Throughput (bit_s ) will be:

(27)

T hr= MSDU

T_MPDU+ SIFS + TACK+ DIFS + Tbacko f f

, (2.17)

where the denominator is the interval between each MPDU transmission, and the numerator is the payload in bits.

The denominator consists in two time-slot multiplier of different length (SIFS and DIFS) and in three times, T_{backo f f} is the backoff procedure time; while the other two are defined as follow:

T_MPDU = PLCP overhead + MAC header + MSDU + FCS

PHY rate , (2.18)

T_ACK = PLCP overhead + ACK length

ACK rate . (2.19)

These elements have a high dependency on the PHY version of IEEE 802.11. In our cases, we assume to have APs 802.11g; given this assumption, the values used for the simulation in this work are visible in the following table; for convenience, we use static Contention Window1.

Parameters 802.11g Value

PHY rate 6,9,12,18,24,36,48,54 Mbps

ACK rate 6 Mbps

ACK length 112 bit

FCS 32 bit

MAC header 192 bit

PLCP overhead 192 bit T_{backo f f} 67.5 µs CWmin 15 DIFS 28 µs Slot Time 9 µs SIFS 10 µs Table 2.1

Summary of the 802.11g values in the simulation

1_{Contention Window is always in the same interval: [0 , CW}

(28)

Chapter 3 Mathematical Programming

In this chapter we will present some notions of Mathematical Programming (MP). MP (area of Operations Research (OR)) concerns the study of mathematical models, particularly optimizing models, used to assist in taking decision. This description will be useful to understand the approaches discussed in this Thesis, namely:

• Basic Robust mathematical model based on [6].

• Multiband Robust mathematical model based on the framework in [3] and [5].

The aim of Operations Research (OR) is the study and the definition of methodologies to solve decision-making problems. The problems tackled by OR are the ones where it is necessary to choose the usage of a set of limited resources while respecting a given set of conditions (constraints), and maximizing the “benefit” achievable by the use of such resources. Operational Research, therefore, considers all the methods useful to improve the effectiveness of the decisions; this means, in principle, to consider all phases of the decision-making process:

• problem individuation

• reality analysis and collection of data • model definition

(29)

• result analysis

The model is the central element of the decision-making process, and it is a description of a real problem of interest, provided by logic or mathematical tools. The difference between reality and the model itself should not be forgotten; the solutions of the model would not be accurate as well as the real ones. In the model, the ability to correctly predict some real events we want to evaluate is fundamental. An additional important feature is to determine the solutions within an amount of time that reflects the real problem. The model aims to find a solution that responds to a precise trade-off between two important aspects. Firstly, considering all the elements used to describe a phenomenon in an accurate way. Secondly, defining a model tractable enough to evaluate the results in the imposed deadline. There is not a formal methodology to build an analytic model automatically. In point of fact, even if some techniques and software tools exist aiming at supporting and simplifying some steps of the decisional process, the author experience is the key. In general, a problem depends on the number of parameters and variables; an instance of a problem (P) is the demand obtained by specifying the values for all the parameters of (P).

An optimization problem is characterized by an objective function over the set of possible solutions (Feasible set F), c : F → R, that returns the cost related to each solution. The solution of the problem is an element of F that minimizes, or maximizes, the objective function. For example:

(P) min{c(x) : x ∈ F}

is a optimization problem in a minimization form. Its optimal value will be:

z(P) = min{c(x) : x ∈ F}

A feasible solution x∗∈ F such that c(x∗) = z(P) is an optimal solution for the problem (P).

(30)

Chapter 3. Mathematical Programming

3.1 Linear Programming

In Linear Programming (LP), the constraints between variables, as well as the objective function, are linear. Variables are not constrained by a discrete set of values (e.g., integer values), rather real values can be assigned to them. An LP problem is an optimization problem (in minimization or maximization form) characterized by the following properties:

• a finite number n of variables, that can assume real values;

• a linear objective function, that is of the type f (x) = cx where c ∈ Rn _{is the cost}

vector (given) and x ∈ Rn is the variables vector;

• a finite set defined by a finite set of linear constraints of the type ax_{= b, and/or ax ≤ b, and/or ax ≥ b, where a ∈ R}n _{and b ∈ R.}

A primal LP Problem (in minimization or maximization form), can be solved introduc-ing its dual LP Problem. Let (P) be an LP Problem of the followintroduc-ing form:

(P) max{cx : Ax ≤ b, x≥ 0} (3.1)

where A is a real matrix m x n.

The dual problem of (P) is defined as:

(31)

It exists a correlation between these two problems, stated by the following set of corollaries and theorems (related proofs are shown in [7]):

Theorem 2.1: The dual of the dual is the primal.

The pair of dual problems we have introduced is called symmetric pair. An equivalent definition of a pair of dual problems is with the asymmetric pair. From now on, we will use the asymmetric form of duality, but the results obtained are independent of the particular form used.

(P) max{cx : Ax ≤ b} (D) min{yb : yA = c, y≥ 0}

In the following, we will use the asymmetric form of duality, but the results obtained are independent of the particular form used.

Theorem 2.2: (Weak duality) If ¯x and ¯y are feasible solutions for the maximization problem (P) and its dual (D), respectively, then c ¯x≤ ¯yb.

Corollary 2.1: If (P) is unbounded (i.e. the value of the objective function has no upper bound), then (D) is empty.

Corollary 2.2: If ¯x and ¯y are feasible solutions for (P) and (D), respectively, and cx¯= ¯yb, then ¯xand ¯y are optimal solutions, to (P) and (D), respectively.

Theorem 2.3: (Strong duality) If (P) and (D) both have feasible solutions, both problems have an optimal solution, and

(32)

3.2 Integer Linear Programming

Problems concerning Integer Linear Programming (ILP) are different from the ones expressed as LP because the variables can assume integer values. Integer variables can be managed to model logic conditions (e.g., booleans), or situations in which the problem must decide on a finite set of alternatives. It is possible to use powerful theoretical results and efficient algorithmic methodologies by exploiting some relations between ILP and LP. We can define the feasible set of an ILP Problem as follows:

F _{= {x ∈ Z}n: Ax ≤ b}.

The linear constraints Ax ≤ b define a convex polyhedron:

¯

F_{= {x ∈ R}n: Ax ≤ b}.

The feasible set is given by the intersection between the “grid” of the points with integer coordinates and ¯F, namely, all the points with integer coordinates that belong to the polyhedron (white points). Since F is made of isolated points, it is not convex, and thus it may be difficult to optimize over it (see [7]).

Figure 3.1 LP and ILP

(33)

According to what has been already described in this section, we achieve the relation F⊆ ¯F, so ¯F can be considered as an approximation of F. In the following we will talk about Linear Programming Relaxation (LPR). More in detail, consider a problem max{cx : Ax ≤ b, x_{∈ Z}n}, its LPR is:

(LPR) max{cx : Ax ≤ b},

where the relaxation of the problem regards the integer constraints. LPR can be efficiently solved, being a Linear Programming problem, and allows achieving some information about the original problem.

The optimal value of its objective function, z(LPR), provides:

• in case of maximization problem an upper bound of the optimal value of the objective function of ILP: z(LPR) ≥ z(ILP).

• in case of minimization problem a lower bound of the optimal value of the objective function of ILP: z(LPR) ≤ z(ILP).

It is possible that the relaxation solution allows solving the original problem directly. The following lemma relates on this concept:

Lemma 2.1: Let x∗ be an optimal solution of LPR: if x∗_{∈ Z}n, namely x∗ is feasible for ILP, then x∗ is optimal for ILP.

A possible case in which the Lemma 2.1 conditions hold, is the one showed in Figure 3.1. In fact, ”A” (the optimal solution of LPR) is integer valued, and it is also an optimal solution for ILP.

There are several methods to solve ILP Problems: the most notable ones will be discussed in the next pages (for their completeness see [12]).

(34)

It is intuitively clearly intuitive that the goodness of the upper limit of z(ILP), in case of a maximization problem, is much better as the adherence of the polyhedron ¯F to the feasible set F increase. There is one continuous relaxation that is good for whichever objective function, because of its “complete adherence” with F. This relaxation is called convex envelope of F:

˜

F= Conv(F),

and it is a polyhedron so that it can be represented by a finite system of inequalities ˜

Ax≤ ˜b. Note that, the dashed polyhedron shown in Figure 3.2 is an example of a convex envelope for the feasible region F.

Figure 3.2

An example of convex envelope

Representing the convex envelope of a generic ILP problem is not easy; for this purpose, we will introduce an iterative method which, starting from an approximation of ˜F, produces at each step a ”less approximated” representation.

Let the inequality dx ≤ δ be valid for ˜F if it is satisfied by each point x ∈ F; in other words, dx ≤ δ is valid for ILP if it is satisfied by all the integer solutions of the problem. In general, it is not necessary to achieve the exact representation of ˜F to solve its related ILP problem; it is sufficient to solve the following separation problem:

Given ¯x_{∈ R}n, is there a valid inequality dx ≤ δ for ˜F that is not satisfied by ¯x , namely such that d ¯x> δ ?

(35)

The above separation problem allows to verify if a certain point ¯x belongs to ˜F or not. In the case ¯x6∈ ˜F, it is necessary to provide a proof, in form of inequality, that separates ¯xfrom ˜F. The above mentioned inequality is called cut for ¯x.

The Cutting-Plane Method finds accurate approximation (maybe the exact repre-sentation) of the convex envelope for an ILP Problem. It acts as follow:

During the ith iteration the optimal solution x(0) of the linear relaxation (let us call such a problem LPR) is found; if x˜ (0) ∈ F, then x(0) is an optimal solution for ILP, so cx(0)= z(ILP); otherwise, a cut dx ≤ δ for x(0) is determined and added to the problem formulation.

If in the ith iteration x(0) has been cut, a new less approximated representation is found, since x(0) is no more belonging to this representation. This procedure iterates until the optimal solution of ILP is found.

The Branch and Bound algorithm (B&B) splits the original problem into easier subproblems, computing an upper bound (u.b.) and a lower bound (l.b.) of the optimal value of the objective function for each of them. Then it puts such information together to solve the original problem. The algorithm we are going to summarize is not explicitly designed for solving ILP problems; rather it is based on a divide & conquer approach that is able to solve more general optimization problems. Consider an ILP problem as:

z= max{c(x) : x ∈ S}

Now, let S = S1∪ S2∪ ... ∪ Sk be a decomposition of S.

Let zk= max{c(x) : x ∈ S_k}, with k = 1, ..., K.

The solution of ILP is then given by z = maxk{zk}.

Enumeration tree typically implements the decomposition of S. It is self-evident that the time to visit the tree suffers of the possibly exponential number of nodes.

Let ¯zk be an u.b. and zk be a l.b. on zk, then: ¯z = maxk{ ¯zk} is an upper bound on z

(36)

Then, the following relationship holds true: z ≤ z ≤ ¯z.

In particular, the following pruning rules avoid the explicit visit of the sub-tree rooted at a certain node t, if one of the following conditions holds:

• zt= max{c(x) : x ∈ St} for some t has been solved (pruning by optimality)

• ¯z_t≤ z , for some t (pruning by bound) • St= /0 , for some t (pruning by unfeasibility)

In the following, the schema of B&B algorithm: Algorithm 1 Branch and Bound

1: Q:= {(P)}; z := −∞; repeat 2: (P0):= Next(Q); Q := Q\{(P0)} 3: ¯z := RELAX (P0); 4: if ¯z > z then begin

5: z:= HEU RIST IC(P0);

6: if z > z then z := z;

7: if ¯z > z then

8: Q:= Q ∪ BRANCH(P0) until Q = /0

where:

P is the problem to be solved and z is the best objective function value found by the algorithm during its execution (z will contains the optimal solution only when the algorithm is terminated).

The steps are the following ones:

1. Starting from the root of the tree (P), the set of Q active nodes is computed. Then z is initialized to −∞ and it will assume a finite value as soon as the first feasible solution is generated. If at the end of the algorithm z = −∞ then P = /0.

2. The next node to visit is assigned to P0, then the nodes being visited are removed, and the new set is updated.

(37)

be provided by the LPR of an ILP maximization problem (actually, whichever relaxation technique can be used in this context).

4. If the condition in this step not holds, the node P0 is pruned by optimality or by bound and the next active node is visited. If the condition in 4. holds, the lower bound is determined through a heuristic: if the node cannot be pruned even after the condition in 6., then P0 is decomposed in subproblems, and their nodes are added to the set of active nodes (step 8.).

(38)

3.3 Robust Optimization

During the last years, Robust Optimization (RO) has become a valid methodology to deal with optimization problems subject to uncertainty. A key concept of RO is to model uncertainty as hard constraints, that are added to the original formulation of the problem. This restricts the set of feasible solutions to robust solutions, i.e. solutions that are protected from deviations of the data. Several methodologies have been proposed to manage the problem of uncertainty. In these proposals, the main issue of such methodologies is to find a proper trade-off between the range of uncertainty conditions and the computational effort necessary to determine the related solution. The trade-off is expressed in term of methodology conservativism. A methodology is very conservative if its solutions protect the systems from a wide range of uncertain conditions. A methodology is said to be little conservative if it ensures less robustness, but usually at a lower computational cost.

In robust optimization, the most general way to express the uncertainty is the rep-resentation through scenarios. According to this reprep-resentation, the uncertainty is structured by means of a set of possible scenarios (possible realizations of the uncer-tain parameters). If the number of possible realizations is finite, it is possible to define such a set through the notation S = {s1, s2, ..., sk}, where each scenario si, i = 1, 2, ..., k,

denotes a possible realization of the uncertain parameters. Such a robust approach is crucial when dealing with complex systems, such as telecommunication networks design, because the complexity of such systems comes mainly from two reasons:

• some decisions have to be made despite the uncertainty of some system param-eters; this uncertainty can affect the current state of the system (that could be unknown), as well as the future states, relative to the evolution of the system. • even when the parameters are perfectly known, and there are no unpredictable

events, some problems can be hard to be solved because of their computational complexity, or because of their considerable size.

In the next pages we will present some techniques, for determining a robust solution in presence of uncertainty, represented through scenarios.

(39)

The generic optimization problem can be denoted by:

min{c(x) : x ∈ F}, (3.3)

where c(x) is the objective function (in this case it must be minimized) and F is the set of feasible solutions. The problem in (3.3) is referred to as the nominal problem, while the problem that allows determining a robust solution is indicated as its robust counterpart. In the definition of the feasible region, or in the objective function, can be found an uncertain parameter α. In the following, we present the problems characterized by uncertain feasible region. The first presented problem will be described by a unique uncertain parameter, because of a straightforward generalization in case of multiple uncertain parameters.

A. Absolute Robustness with uncertain feasible region

The feasible region varies depending on the value of α in S, where α is the uncertain parameter that behaves according to scenario s, where s ∈ S. The feasible solutions set relative to scenario s is indicated as F(s). Then, let F∗ the intersection of these sets (the set of feasible solutions for every scenario): F∗= ∩s∈SF(s). The following

problem is defined as the robust counterpart of (3.3), useful to compute a robust solution x∗:

min{c(x) : x ∈ F∗}. (3.4)

The absolute robustness criterion is very conservative when the uncertainty concerns the feasible region. Indeed, its purpose is to find the least expensive feasible solution, regardless the realization of the α parameter.

_∑

j∈J c_jx_j (LPP) (3.10)

∑

j∈J a_{i j}x_j≤ bi i∈ I xj≥ 0 j∈ J,

where I = {1, ..., m} and J = {1, ..., n} denote the set of constraints and variable in-dexes, respectively. The uncertainty regards the coefficient ai j, its value is equal to the

summation of a nominal value ¯ai j and a deviation lying in the range [dK

−

i j ,dK

+

i j ], where

d_{i j}K−,d_{i j}K+ _{∈ R represent respectively the maximum negative and positive deviations} from ¯a_{i j}. The actual value ai j lies in the interval [ ¯ai j+ dK

−

i j , ¯ai j+ dK

+

i j ]. The partition

of single band into K bands is defined as follow:

−∞ < di jK−< ... < di j−2< d −1 i j < d 0 i j = 0 < di j1 < di j2 < ... < dK + i j < ∞.

These deviation values, provide us the possibility to define:

• A set of positive deviation bands: k ∈ {1, ..., K+_}

• A set of negative deviation bands: k ∈ {K−, ..., −1} • The 0 deviation band: d0

(43)

In addition, for each k ∈ K, a lower bound l_k and an upper bound u_k are defined, on the number of deviations that may fall in k, with lk, uk∈ Z satisfying 0 ≤ lk≤ uk≤ n.

All the above introduced elements define what we call a multiband uncertainty set SM. We now proceed with studying the robust counterpart of (3.10) under multiband

k∈K yk_{i j}≤ 1 j∈ J yk_{i j} ∈ {0, 1} j∈ J, k ∈ K.

The lying of coefficient ai j in k is indicated by binary variables yki j. The families of

constraints of (3.12) impose the lower bound and the upper bound on the number of deviations falling in each band k and ensure that each coefficient ai j deviates in at

most one band. Thus, an optimal solution of (DEV 01) defines a distribution of the coefficients among the bands that maximizes the deviation w.r.t. the nominal values, while respecting the bounds on the number of deviations of each band. The integrality property of (3.12) is satisfied by its linear relaxation (proven in [3]), expressed as:

(44)

j∈J z_ij≤ bi i∈ I −vk_i+ wk_i+ z_ij≥ d_{i j}kx_j i∈ I, j ∈ J, k ∈ K vk_i, wk_i ≥ 0 i∈ I, k ∈ K z_ij≥ 0 i∈ I, j ∈ J x_j≥ 0 j∈ J.

(46)

Chapter 4 Problem formulation

The most recent versions of IEEE 802.11 define the PSM modality. This feature exploits the central role of the Access Points in the Extended Service Set, enabling the hosts to save energy. An interesting point, which is not touched by IEEE specifications, is the possibility to implement a mechanism for reducing the overall power consumption of APs in Extended Service Sets.

In this chapter, we present three Mathematical Programming models (see section 3.3) aiming at minimizing the overall power consumption of Extended Service Sets (as reported in [10]). The first one is a model in which we assume UTs are stationary and that the capacities of the wireless links between UTs and APs are stable. The second one is a robust counterpart of the just mentioned model in which we consider uncertain elements. Hence, the users are allowed to move and the wireless channels are subjected to capacity fluctuations. The third model is a multiband model, a robust formulation that aims to reduce the price of robustness paid in the basic robust version.

We assume to work in WLAN system in which a set I of User Terminals (UTs) are served by a set of J Access Points (APs). In this scenario, exactly one AP must satisfy the traffic demand wi of user i, for each i. The power Pj consumed by the AP j can

be expressed as follows:

(47)

There are three parts of this equation. There is a constant part bj, that is a value

which depends on switching on or switching off the access point. The variable part aj,

which accounts for the so-called airtime (i.e., the fraction of time in which the device is either transmitting or receiving frames). This factor is weighted by a constant wireless factor pw, that is the power drain of the radio, which fronts for the transmission and reception operations. The system is also characterized by ri j parameters, which

account for the data-rate available between the U T i and the AP j. For convenience, we assume that the links are symmetric: ∀i, j , ri j = rji.

(48)

Chapter 4. Problem formulation

4.1 Nominal model

In this scenario, the two most important constraints regard the traffic demand of UTs that has to be satisfied and the capacity of each APs that must not be exceeded. This model aims to minimize the overall power consumption. The problem can be formulated by the following ILP model, which is based on two sets of binary variables:

• yj: set to 0 if AP j has been switched off, to 1 if AP j is powered-on.

• xi j: set to 1 if the U T i is assigned to AP j, 0 otherwise.

The objective function for the WLAN system to be minimized is:

z= min

_∑

j∈J

P_j. (4.2)

It can be written in the following way:

z= min

_∑

j∈J

(bjyj+ pwaj).

The airtime aj can be written in terms of variables xi j, so:

a_j=

_∑

i∈I

w_i ri j

x_{i j}. (4.3)

The mathematical model is:

z= min

_∑

j∈J (bjyj+ pw

∑

i∈I w_i ri j x_{i j}) (4.4)

∑

j∈J x_{i j}= 1 i∈ I

∑

i∈I wi r_{i j}xi j ≤ yj j∈ J xi j∈ {0, 1} i∈ I, j ∈ J y_j∈ {0, 1} j∈ J,

(49)

where the constraints are the following:

• The first family of constraints imposes that each UT must be attached to one exactly AP.

• The second family of constraints forces the AP airtime not to exceed the AP capacity. It also ensures that no U T is assigned to a power-off AP, so the ones with yj= 0.

• The last two groups of families of constraints define the boolean variables de-scribed in this section.

(50)

4.2 Basic robust model

The previous model has a limitation; namely, it cannot be implemented to simulate a real condition, because of users movement. The first robust model considers two crucial aspects: user movements and capacity fluctuations. The distance between UT and AP may change, causing a new evaluation on link capacities ri j. This model

provides an advantage w.r.t. the previous one. This solution is more robust to the uncertain events considered than the previous one, and this allows to re-compute the allocation between UTs and APs with a lower frequency than it would be done with the nominal model.

We must to take into account the UT mobility, so we shall denote by R(i, j) the set of possible capacities between U T i and AP j, in a certain time interval, depending on the mobility of i, i.e. R(i, j) = {r1_{i j}, ..., r_{i j}h(i)}, where h(i) denotes the number of the alternative final destinations for i.

The second aspect that has influence on ri jis the fluctuation in the signal propagations.

Taking into account each position α : 1 ≤ α ≤ h(i), then [¯rα

i j− ˆrαi j , ¯rαi j+ ˆri jα] denotes

the interval of the possible rα

i j deviations around its nominal value, with the average

value ¯rα i j, ∀i, j.

This model is implemented according with the framework in section 3.3.B. We assume that at most H UTs can move simultaneously and that at most K link capacities may deviate from their nominal value simultaneously.

The robust counterpart of the left-hand-side of each capacity constraint of the previous model is an ILP model which gives the maximum value that the left-hand-side may achieve under the robustness assumptions stated above. Relative to j, this optimal value is: crob_j = max

_∑

i∈I {wiqi rdmin_{i j} + w_iz_i ¯r_{i j}curr− ˆrcurr i j +wi(1 − qi− zi) r_{i j} }xi j, (4.5) where:

• qi: set to 1 if user i can move and its capacities can deviate from their nominal

(51)

• zi: set to 1 if user i cannot move and its capacities can deviate from their nominal

value. • rdmin

i j = minα{¯r_{i j}α− ˆrα_{i j}}: it denotes the minimum deviation among all values in

R(i, j). • rcurr

i j : is the capacity between U T i and AP j on the current position of U T i.

• ri j: is the realization of the random variable rcurri j in the interval [ ¯ri jcurr− ˆrcurri j ,

¯rcurr_{i j} + ˆrcurr_{i j} ] in the instant in which the optimization is pursued.

Since the values at denominator are constant, it is possible to re-write the formula in a linear way, where Cj= ∑

i∈I wi

ri jxi j is linear w.r.t. the variable xi j; then we can denote

with Ai j and Bi j the coefficients of qi and zi respectively.

βi j≥ 0 i∈ I, j ∈ J.

Applying the technique in section 3.3.B we can derive the robust counterpart of the objective function (4.4).

The Basic robust model will be:

zrob= min

_∑

j∈J {bjyj+ pw(Cj+ Kγ1 j+ Hγ2 j+

∑

i∈I βi j)} (4.8) Cj+ {Kγ1 j+ Hγ2 j+

_∑

i∈I βi j)} ≤ yj j∈ J

∑

j∈J x_{i j} = 1 i∈ I, x_{i j}∈ {0, 1} i∈ I, j ∈ J, y_j∈ {0, 1} j∈ J, γ1 j+ γ2 j+ βi j ≥ Ai jxi j i∈ I, γ1 j+ βi j≥ Bi jxi j i∈ I, γ1 j ≥ 0 j∈ J, γ2 j ≥ 0 j∈ J, βi j≥ 0 i∈ I, j ∈ J.

(53)

4.3 Multiband robust model

In the previous model, to control the price of robustness, the maximum number of users that are assumed to move and the maximum number of link capacities that are supposed to fluctuate have an upper bound denoted, respectively, by H and K. This model provides the possibility to break some bands into multiple narrowed bands to give a more realistic estimation of deviations in uncertain sets, referring to section 3.3.C.

The assumption based on the fact that users can move in more bands (we evaluate a set of B bands), according to the distance of the users’ movement. We assume that we have the zero-band plus other three bands, which depend on the user movement (low distance, medium distance, high distance). So we have the following parameters:

• b = 0: is the static band, the one in which the users does not move, but their links are subjected to fluctuations.

• H0: maximum number of users that belong to the previous case.

• b = 1: users low mobility and links subjected to fluctuations. b= 2: users medium mobility and links subjected to fluctuations. b= 3: users high mobility and links subjected to fluctuations.

• Hb: maximum number of users that can move simultaneously according to the

type of movement, with b = 1, ..., |B|, and link capacities are subject to fluctua-tions.

The following representation gives us an idea on how the bands are divided, based on the low, medium, and high users movement.

(54)

band1

band2

band3

band0

We model the fluctuation of the fading channels through a single band for keeping the model simpler and because we agreed that the mobility of UTs is the uncertain event subject to more significant variability. The data-rate of this model change according with the band to which the user belongs, because the data-rate is strictly associated with user distance. A function r_{i j}(b, f ) will represent the data-rate. In this function, b is the user mobility band, f characterizes the state of the fading channel ( f can be equal to its nominal value ¯f, or it can be set to the lower band f1 of the unique band

characterizing the fading channel fluctuations).

The robust counterpart of the left-hand-side of each capacity constraint of the previous model is an ILP model which gives the maximum value that the left-hand-side may achieve under the robustness assumptions in the framework described in section 3.3.C. Relative to j, this optimal value is:

cmrob_j = max

_∑

i∈I |B|

∑

b=0 w_i qib r_{i j}min−b+ wi (1 − |B| ∑ b=0 q_ib) ri j x_{i j} (4.9) where:

• q_ib: set to 1 if UT i moving according to band b (with b > 0), and channel fading is subject to fluctuation; or it is set to 1 if i doesn’t move (b = 0), and channel fading is subject to fluctuation.

• rmin−b_{i j} : denotes the minimum value assumed by the capacity function (ri j(b, f ))

(55)

• ri j: is the data-rate of link(i,j) in a certain time instant.

• (1 −

|B|

∑

b=0

q_ib): models the case in which i does not move and the related fading channel is not subject to fluctuation.

The values at the denominator are constant, so we can re-write the just mentioned problem in the following way:

The above mentioned second constraint remark the fact that the link capacities of at most K UTs may deviate from their nominal value simultaneously.

The third family of constraints remarks that for each band b, there are at most H_b users.

The linear relaxation of the maximization problem in (4.10) satisfies the integrality property. By associating a set of dual variables with the last three families of con-straints, we can state the Dual LP of the linear relaxation of problem (4.10):

min

_∑

i∈I πi j+ Kδj+ |B|

∑

b=0 µ_{b j}H_b (4.11) πi j+ µb j+ δj≥ wi( 1 r_{i j}min−b− 1 r_{i j})xi j i= 1, ..., |I|, b = 0, ..., |B|, πi j ≥ 0 i= 1, ..., |I|,

(56)

µb j ≥ 0 b= 0, ..., |B|,

δj≥ 0,

where:

• πi j: are the dual variables associated with the first family of constraints of the

problem 4.10.

• δj: is the dual variable associated with the second constraint of the problem

4.10.

• µb j: are the dual variables associated with the third first family of constraints

of the problem 4.10.

The overall ILP model for the special robust case under consideration is therefore:

b=0 µb jHb≤ yj j∈ J, πi j+ µb j+ δj≥ wi( 1 r_{i j}min−b− 1 r_{i j})xi j i∈ I, j ∈ J, b = 0, ..., |B|, πi j≥ 0 i∈ I, j ∈ J, µ_{b j}≥ 0 b= 0, ..., |B|, j ∈ J, δj≥ 0 j∈ J, x_{i j}∈ {0, 1} i∈ I, j ∈ J, y_j∈ {0, 1} j∈ J.