Koster A., Munoz X. Graphs and Algorithms in Communication Networks

Подождите немного. Документ загружается.

11 Mathematical Optimization Models for WLAN Planning 293

11.6 Minimum-Overlap Channel Assignment

Given a set

A ⊆ A of installed APs, the next step is to assign one of the available

channels to each AP. With 13 available channels as shown in Figure 11.1, two basic

selections of the set of candidate channels are the complete set C = {1,...,13},

and the set of non-overlapping channels C = {1,6,11} for which only co-channel

overlap may occur. We will ﬁrst present a channel assignment model for the general

case, and then a model speciﬁc to the case of three non-overlapping channels.

In this section, we treat channel assignment in a similar way as frequency as-

signment in cellular networks. Instead of trying to model CSMA/CA explicitly, we

model interference and medium contention indirectly by considering the amount of

overlap between APs operating on the same channel or adjacent channels. To do

so, we deﬁne a parameter

to represent the number of TPs at which the received

signals of APs a and b are both detectable. More precisely,

is the number of TPs

that lie within the carrier sense ranges of both APs and in the serving range of at

least one of them. We call

the co-channel overlap if APs a and b are assigned

the same channel. If the two APs operate on adjacent channels at a distance d,the

parameter is scaled by a weight F(d) ∈ [0,1]. In our computational experiments we

use F(d)=1/(1+ d/5MHz)

if d ≤24 MHz, and 0 otherwise. Note that F(0)=1

and that F(0) models the impact of contention and co-channel interference on the

system performance, while F(d > 0) addresses the inter-channel interference issue,

which is less critical but may still have a signiﬁcant effect on the performance when

channel distance is small. The parameter k can be used to model the impact of over-

lap due to adjacent channels; in our experiments we set k = 2. For an alternative

deﬁnition of F(d), derived empirically, see [29, 38]. Also, instead of using the size

of overlap between AP pairs, another modeling approach is to consider for each TP,

the covering APs and their signal strengths. For channel assignment in GSM, such

an approach (e.g., [18]) amounts to aggregating multiple interfering sources.

To formulate the problem, we introduce the following variables:



1ifAPa operates on channel c,

0 otherwise.



1 if the channel distance between AP a and AP b equals d,

0 otherwise.

(11.3)

Variables w

translate channel assignment into overlap. The minimum weighted-

overlap channel assignment problem (M

OCA) can then be modeled as follows.

294 S. Bosio et al.

min

∑

(a,b)∈

∑

d∈D

F(d) w

(11.4a)

s. t.

∑

c∈C

= 1 a ∈

A (11.4b)

−c

≥ f

+ f

−1 (a, b) ∈

∈ C ,|c

−c

|∈D (11.4c)

∈{0,1} (a,b) ∈

,d ∈D (11.4d)

∈{0,1} a ∈

A ,c ∈C (11.4e)

Constraints (11.4b) ensure that one channel is chosen for each AP, and con-

straints (11.4c) relate channel assignment to the overlap variables. Recall that D

contains distances between overlapping channels only, as we do not need to consider

distances d for which F(d)=0. The objective function (11.4a) is the total weighted

overlap over all pairs of APs. Note that the problem represented by M

OCA is a type

of minimum interference frequency assignment problem that has been studied, for

example, in [1, 10, 12, 23].

If the candidate channels are non-overlapping, i.e., if D = {0}, the problem can

be alternatively formulated as a minimum K-partition problem, with K = 3. Only

variables w

are used, and we drop for simplicity the index 0. The resulting formu-

lation, denoted by 3-M

OCA, is the following.

min

∑

(a,b)∈

(11.5a)

s. t.

∑

a,b∈Q : (a,b)∈

≥ 1 Q ⊆

A : |Q| = 4 (11.5b)

≥ w

+ w

−1 (a, b),(b,c) ∈

(11.5c)

≥ w

+ w

−1 (a, b),(b,c) ∈

(11.5d)

≥ w

+ w

−1 (a, b),(b,c) ∈

(11.5e)

∈{0,1} (a,b) ∈

(11.5f)

The objective function (11.5a) of 3-M

OCA minimizes the total co-channel over-

lap. By (11.5b), for any group of four APs, at least two have to use the same channel.

Constraints (11.5c)–(11.5e) are referred to as the triangle inequalities. They ensure

the transitivity of channel assignment: For any group of three APs, if any two pairs

of them use the same channel, then the same is true for the third pair. To translate

a feasible solution of 3-M

OCA to a channel assignment, let the APs be represented

by nodes of a graph. The graph’s edges correspond to the nonzero w-variables in the

solution. It is easy to see that the graph has at most three disconnected components,

each being a clique. The APs of every clique then operate on the same channel.

Model 3-M

OCA eliminates the symmetry of MOCA (formed by the f -variables).

On the other hand, the underlying idea of 3-M

OCA results in model size that grows

exponentially in the number of channels [10]. For three non-overlapping channels,

however, ﬁnding the optimum to 3-M

OCA is typically computationally feasible.

11 Mathematical Optimization Models for WLAN Planning 295

11.7 Maximum-Efﬁciency Channel Assignment

The AP overlap view models the CSMA/CA protocol behavior coarsely, because it

aggregates the interference and contention between users into the amount of over-

lap between APs. Hence, the contention experienced by every individual user is not

modeled explicitly. A more detailed analysis is to consider the contention sets. The

contention set of a TP is the set of test points potentially contending for medium

access with it; this set has a pivotal inﬂuence on user throughput achieved under

CSMA/CA. From the discussion in Section 11.2, two TPs will contend for the

medium if they use the same channel, or more precisely, if the APs with which they

are associated use the same channel, and if at least one of the following conditions

holds:

1. The two TPs are associated with the same AP.

2. The two TPs are located within the carrier sense range of each other, and hence

one will sense the carrier as busy when the other is transmitting.

3. One of the two TPs is within the carrier sense range of the AP with which the

other TP is associated; this corresponds to the exposed terminal problem.

If the two TPs use adjacent channels at some distance d > 0, then F(d) can be

considered as the likelihood that interference will occur (recall that F(0)=1, and

F(d)=0 for non-overlapping channels). We denote by d(i, h) the channel distance

between the TPs i and h (i.e., between APs ¯a(i) and ¯a(h)).

For each TP i ∈ I ,letF

= {h ∈I \{i} :¯a(h)= ¯a(i)} be the set of TPs which

contend for the medium with i due to condition 1, and let P

be the set of all other

potential contending TPs. The set P

is derived from the input data by assuming

that all APs operate on one single channel, and taking TPs h /∈ F

for which at

least one of conditions 2 and 3 holds. Based on these contention sets, we deﬁne an

efﬁciency metric for every TP. Since a user can access the network only if no other

user is contending for the medium, the efﬁciency metric of a TP i ∈ I is deﬁned

as the throughput t

scaled by the probability of successfully accessing the medium,

which is deﬁned as

1+ |F

∑

h∈P

F(d(i,h))

The overall network efﬁciency is the sum of the efﬁciency values over all TPs.

This leads to a maximum-efﬁciency channel assignment problem. Note that the con-

tention relation is symmetric for every pair of TPs. Moreover, if we consider only

non-overlapping channels, for which F gives binary values, the denominator is the

cardinality of the contending set plus the TP itself.

296 S. Bosio et al.

11.7.1 A Hyperbolic Model and Linear Reformulations

Consider variables f

and w

deﬁned for MOCA. For two TPs i,h ∈I , let us denote

and

the variable w

, with a = min{¯a(i), ¯a(h)} and b = max{¯a(i), ¯a(h)}.

A model for the problem of ﬁnding a channel assignment that maximizes the average

efﬁciency, denoted by M

ECA, reads:

max

∑

i∈I

1+ |F

∑

h∈P

∑

d∈D

F(d)

s. t. (11.4b), (11.4c),(11.4d),(11.4e)

The hyperbolic objective function (sum of ratios) in M

ECA is the average efﬁ-

ciency over all TPs. As for M

OCA, for three non-overlapping channels we have the

alternative model 3-M

ECA, where w

= w

and

max

∑

i∈I

1+ |F

∑

h∈P

s. t. (11.5b), (11.5c),(11.5d),(11.5e)

Problem M

ECA is NP-hard, even when restricted to the special case 3-MECA.

This can be shown by a polynomial-time reduction from 3-coloring. Given an undi-

rected graph G =(V, E), for each node v ∈ V we create an AP location a

and a

TP i

, and deﬁne the covering set of each AP a

as I

= {i

: {v,u}∈E}∪{i

The rates are then deﬁned so that t

= 1 for every v ∈ V and t

for every

{u,v}∈E, with

< 1. Hence ¯a(i

)=a

and t

= 1. It is then easy to see that G ad-

mits a 3-coloring if and only if M

ECA admits a frequency assignment with objective

function value 1.

Solving the hyperbolic formulations M

ECA and 3-MECA is very difﬁcult. As

these are constrained problems, solution approaches for unconstrained hyperbolic

problems (e.g., [13]) cannot be applied. It is thus justiﬁable to look for a linear re-

formulation. Consider problem 3-M

ECA. A standard way of linearizing a hyper-

bolic objective function is to introduce a new variable for each fraction. In our

case this consists of adding a continuous variable s

for each TP i ∈ I , thus re-

deﬁning the objective function as

∑

i∈I

. The resulting hyperbolic constraint s

1/(1+ |F

∑

h∈P

) can be linearized in two ways. The ﬁrst linearization is to

introduce, for each TP i ∈I , the quadratic constraint 1 =(1+|F

|)s

∑

h∈P

and linearize the bilinear product

by standard techniques. The second lin-

earization consists of introducing, for each TP i ∈ I and for each possible value

1/(1+ |F

|+m) of s

, a binary variable r

,form ∈{0...|P

|}, and including into

the formulation the following constraints:

11 Mathematical Optimization Models for WLAN Planning 297

∑

m=0

1+ |F

|+ m

i ∈ I

∑

m=0

= 1 i ∈I

∑

m=0

m ·r

∑

h∈P

i ∈ I ,

which guarantee that if TP i has m contending TPs among those in P

, then r

= 1.

The linear programming (LP) relaxation of the ﬁrst linearization can be improved

by exploiting a disjunctive argument. The LP relaxation of the second linearization

can be improved by removing variables r

for which the value 1/(1 +m) cannot be

attained by s

in any feasible solution. Even after the tightening, however, both the

LP relaxations are outperformed by that of an integer-linear model derived from an

enumeration of medium contention scenarios, which we present in the next section.

11.7.2 An Enumerative Integer Linear Model

Let us consider problem 3-MECA. A medium contention scenario for a TP i ∈ I

is deﬁned by the set F

and a subset of the TPs in P

that use the same frequency

channel as i. The idea is to construct, for every TP, the set of all the possible medium

contention scenarios, i.e., the set of all the subsets of P

. But since there could be

TPs in P

associated with the same AP as i, not all the subsets of P

represent

possible contention scenarios. It is therefore more efﬁcient to enumerate the subsets

of the set B

= {a ∈

A : a = ¯a(h) for some h ∈ P

} with which TPs in P

may be

associated. Since P

is deﬁned on the carrier sense range of TP i,thesetB

may

have some APs that are not included in

Let S

= {S : S ⊆ B

} be the set of all contention scenarios for TP i. Note that

for every contention scenario S ∈S

, the corresponding objective function value for

TP i, denoted by d

, is known. To represent the resulting medium contention of a

channel assignment, the following variables are introduced.



1 if the channel assignment results in scenario S ∈S

for TP i,

0 otherwise.

The enumerative linearization, denoted by 3-M

ECA

, is the following:

298 S. Bosio et al.

max

∑

i∈I

∑

S∈S

s. t. (11.5b), (11.5c),(11.5d),(11.5e)

∑

S∈S

= 1 i ∈I (11.8a)

¯a(i)b

∑

S∈S

:b∈S

i ∈ I ,b ∈B

(11.8b)

∈{0,1} i ∈ I ,S ∈ S

Constraints (11.8a) state that exactly one scenario must be chosen for every TP,

while constraints (11.8b) make sure that for every b ∈ B

the variable w

¯a(i)b

has

value 1 if and only if the scenario selected for TP i includes AP b. This imposes

coherence among w and v

. A similar model can be derived for problem MECA.In

this case, a medium contention scenario is represented by a partition of B

into |D|

subsets, one for each channel distance.

An obvious difﬁculty in the model 3-M

ECA

is that the number of v-variables

grows exponentially fast in the size of B

. However, B

is typically small in size

when planning channel assignment, since only a small number of APs are installed

out of all the possible candidate locations. Moreover, since in an optimal solution

typically only few overlapping APs share the same frequency, it is possible to create

a restricted formulation by considering only elements S ∈ S

having cardinality

less than or equal to a given parameter. An alternative approach is to apply column

generation to the LP relaxation of 3-M

ECA

, and to use branch-and-price to search

for an optimal solution.

11.8 Integrated Planning of AP Location and Channel

Assignment

We now introduce integrated optimization models that decide both AP locations and

channel assignments simultaneously.

11.8.1 AP Location and Minimum-Overlap Channel Assignment

Throughput and overlap have been used as objectives in the two tasks, and both ob-

jectives obviously antagonize each other. This calls for multi-criteria optimization

techniques. We use the popular weighted-sum scaling technique [9]: A trade-off pa-

rameter

∈ (0, 1) is introduced to weigh the two objectives for AP location and

channel assignment. Because the two objectives are of different dimension, we in-

troduce an additional scaling parameter K whose value is found empirically. The

integration of M

TAL and MOCA (with

A = A ) results in the following model,

11 Mathematical Optimization Models for WLAN Planning 299

denoted by MT-MO:

max (1−

∑

i∈I

∑

a∈A

−

∑

(a,b)∈A

∑

d∈D

F(d) w

s. t.

∑

c∈C

= z

a ∈ A (11.9)

(11.2b),(11.2c),(11.2d),(11.2e),(11.2f)

(11.4c),(11.4d),(11.4e).

In M

T-MO, AP location and channel assignment interact in the objective function

and in (11.9); the latter states that a channel needs to be assigned to an AP if and

only if the AP is installed.

Another integrated model can be derived from M

TAL and 3-MOCA (with

A =

A ). The resulting model will be referred to as 3-M

T-MO. The constraints where

TAL and 3-MOCA interact are as follows:

∑

(a,b)∈A

:a,b∈Q

≥

∑

a∈Q

−3 Q ⊆A , |Q|= 4. (11.10)

Constraint (11.10) replaces (11.5b) in the integrated model.

11.8.2 AP Location and Maximum-Efﬁciency Channel Assignment

A difﬁculty in integrating AP location and maximum-efﬁciency channel assignment

is that the sets F

and P

for TP i depend on the set of installed APs. In order to

deﬁne an integrated model, we need to introduce additional variables to represent

this relation, and additional notation to specify the input data. For simplicity, we

will consider 3-M

ECA with three non-overlapping channels. A similar integration

can be obtained for the more general case.

Let

be the set of APs within the carrier sense range of TP i. We denote by Q

the set of TPs within the carrier sense range of TP i, and by R

the set of TPs that

arecoveredbysomeAPa ∈

, excluding i and those in Q

. Note that Q

is the set

of TPs that are potential direct interferers to i, while R

is the set of TPs to which i

is potentially exposed. Which users in Q

and R

will contend for the medium with

i depends on the association (i.e., on the AP location) and the channel assignment.

We introduce the following variables:



1ifTPsi, h ∈ I operate on the same channel,

0 otherwise.



1ifTPsi, h ∈ I contend for the medium,

0 otherwise.

300 S. Bosio et al.

In contrast to 3-MECA, explicit variables

are necessary because the associations

¯a(i) and ¯a(h) are not part of the input. We obtain the integrated model 3-M

T-ME:

max

∑

i∈I

∑

a∈A

∑

h∈I

(11.11a)

s. t. (11.2b), (11.2c),(11.2d),(11.2e), (11.2f)

(11.5c),(11.5d),(11.5e),(11.5f)

(11.10)

∑

b∈A

≤ 1 i ∈ I ,a ∈A

(11.11b)

∑

a∈A

∑

b∈A

i,h ∈I (11.11c)

≥

i ∈ I ,h ∈Q

(11.11d)

≥

∑

a∈

∩A

i ∈ I ,h ∈R

(11.11e)

∈{0,1} i,h ∈I , i = h

∈{0,1} i,h ∈I , i = h.

In 3-M

T-ME, the objective function (11.11a) is the efﬁciency of AP location

and channel assignment. Constraints (11.11b) state that if an AP a covering a TP

i is installed, then i is not associated with an AP b providing a lower rate than a.

Note that these constraints are not required in model M

TAL because of its objective

function. Constraints (11.11c) deﬁne variables

:TwoTPsi and h operate on the

same channel if and only if they are associated with two APs a and b that are as-

signed the same channel. Constraints (11.11d) state that a TP h within carrier sense

range of TP i contends for the medium (i.e., y

= 1) if TPs i and h operate on the

same channel, thus deﬁning condition 2 of medium contention (see Section 11.7).

Constraints (11.11e) deﬁne condition 3, stating that a TP h to which i is exposed

contends for the medium with i,ifi and h operate on the same channel, and if h is

associated with an AP within carrier sense range of i. Since the carrier sense range

is at least as large as the coverage range, constraints (11.11e) deﬁne condition 1 as

well.

Problem 3-M

T-ME is very complex, due to the hyperbolic objective function

and to the large number of variables and constraints, some nonlinear. Exact and

heuristic solution approaches to this problem are currently under study by some of

the authors, but their description is beyond the scope of this chapter.

11 Mathematical Optimization Models for WLAN Planning 301

11.9 Experimental Results

We present computational experiments for a network instance representing a part of

the WLAN deployed at Zuse Institute Berlin. There are 32 candidate AP locations

and 798 TPs distributed on two ﬂoors, as shown in Figure 11.5. All APs are of type

Cisco AP-1200/AP21G [7] and compliant with the I

EEE 802.11g standard. Path loss

predictions are obtained by 3D ray-tracing methods with multiple reﬂections using

a 3D model of the building [19, 20].

Fig. 11.5 Candidate APs locations and pathloss predictions for AP location 22

For comparison, we deﬁne a reference planning solution, which has been de-

ployed in this network. In the reference solution there are eight installed APs using

the three non-overlapping channels 1, 6, and 11, and the additional channel 7. The

APs are installed in service rooms with thick concrete walls, located at the center of

the corridors, resulting in a rather low throughput at many TPs. In particular, single-

user throughput is below 1 Mbit/s at 22.75% of the TPs and the coverage loss is

11.5%. Figures 11.6(a), 11.7(a), and 11.9(a) show respectively single-user through-

put, channel overlap, and efﬁciency for the reference solution. The thickness of lines

in Figure 11.7(a) represents the amount of overlap. Note that not all TPs are covered

in the reference solution. Indeed, by applying a minimum-cardinality set covering

model, it is revealed that at least nine APs are required for full coverage. To make the

comparisons meaningful, we set M = 8 as the budget for the AP location. Moreover,

in order to apply and compare the minimum-overlap approach and the maximum-

efﬁciency approach for channel assignment, in our experiments we use the three

non-overlapping channels.

302 S. Bosio et al.

[Mbit/s]

(a) Reference solution: the APs are located in the middle section of the

building, leading to large low-throughput areas

[Mbit/s]

(b) M

TAL solution allows for maximum average throughput

[Mbit/s]

T-MO solution (

= 0.6): some throughput is sacriﬁced for re-

ducing overlap

Fig. 11.6 Effect of optimization on single-user throughput