COMP9334: Capacity Planning of Computer Systems and Networks
Optimisation (4): Placement problems
Integer Programming – What have you seen?
A recurrent theme is to use integer programming to make binary decisions
Examples of binary decisions
Week 9A: Grid computing problem
Choose a particular grid computing company or not
Week 9B: Routing of flows
Should the flow be routed on a link or not?
Page 1
This week’s lecture
Integer programming for placement problem
Example: There are a number of potential places that I can put certain devices, what are the best places to put them?
We will study a placement problem in wireless networks Placement of wireless access points
For the revision problem, we will look at the controller placement problem for software-defined networking
Page 2
Wireless Local Area Networks
Commonly known as Wireless LAN, WiFi etc.
Formal standards in IEEE 802.11, IEEE 802.11a/b/g/n/ac/ad etc.
Infrastructure mode: Wireless Access Points (APs) and Wireless stations
Internet
Station D
AP
Station C
Station A
AP
Station B
Page 3
Wireless Access Point Coverage
Due to radio propagation loss and mandated limit on transmission power, wireless access points have only limited coverage
For example, a Cisco Aironet access point has a coverage of 304m when operating outdoor at 11 Mbps
Ideal coverage area is a circle. In the picture below, Station A can talk to the access point but not Station B
AP
Transmission range
Station B
Station A
Page 4
AETTER LAYOUT 12/4/06 2:57 PM Page 12
Coverage in practice
Note: High attenuation = Poor signal = Poor coverage
An area is covered only if the attenuation is smaller than a threshold
(a)
110
Covered area
Potential AP location
40
(b)
Page 5
L
Attenuation [dB]
Number of potential servers
Atte
Covering a given area
(a)
Multiple access points may be required to cover a given area
Covered area
Decisions to make
The number of access points required to cover the given area
The position of the access points
(b)
(c)
I Figure 3. Modeling coverage planning as a set covering problem: a)signal propagation prediction for one potential AP location i; b)corresponding cover- age set Ci; c)AP location density.
Potential AP location
40
15
0
Page 6
The coverage problem – definition
Given
A number of potential access point locations L1, L2, …, Lp A number of stations s1, s2, s3, …, sn
Binary constant δij where
1 if station si is covered by an AP at location Lj 0 otherwise
δij =
See the next page for a graphical explanation for δij
Find the minimum number of access points required so that All stations are covered
Page 7
Explanation of δij Example: δ10,5 = 1, δ3,5 = 0
= location of station
Station 3 Station 10 Potential
AP location #5
Page 8
The coverage problem: Verbal formulation
Decision variables:
1 if an AP is to be installed at location Lj 0 otherwise
Integer programming formulation:
min
subject to
xj ∈{0,1}
xj =
The number of access points (An expression in xj)
Each station is covered (One expression for each station, need xj and δi,j)
Page 9
The coverage problem: Formulation
Decision variables:
1 if an AP is to be installed at location Lj 0 otherwise
xj =
Integer programming formulation:
subject to
p minxj
j=1
p
δijxj ≥ 1 ∀i=1,…,n
j=1
xj ∈ {0,1}
Page 10
Some alternative constraints
Each station can associate with at least b AP p
δijxj ≥ b ∀i=1,…,n j=1
Each station can associate with at least c APs and at most d APs where d ≥ c
p
δijxj ≥ c ∀i=1,…,n
j=1 p
δijxj ≤ d ∀i=1,…,n j=1
Page 11
Summary
Placement problem
Using binary decision variables to decide whether to use a potential location or not
Important class of problems for (mixed) integer programming
Page 12
Acknowledgments
Picture credits:
Andreas Eisenbla ̈tter and Hans-Florian Geerdes, ”Wireless Network Design: Solution-oriented modeling and mathematical optimization”, IEEE Wireless Communications, December 2006
Page 13