Transcript 0 - Lyle School of Engineering - Southern Methodist University

W-CDMA Network Design
Qibin Cai1
Joakim Kalvenes2
Jeffery Kennington1
Eli Olinick1
Dinesh Rajan1
Southern Methodist University
1 School
of Engineering
2Edwin L. Cox School of Business
Supported in part by Office of Naval Research Award N00014-96-1-0315
Wireless Network Design: Inputs
• “Hot spots”: concentration points of users/subscribers
(demand)
• Potential locations for radio towers (cells)
• Potential locations for mobile telephone switching
offices (MTSO)
• Locations of access point(s) to Public Switched
Telephone Network (PSTN)
• Costs for linking
– towers to MTSOs,
– MTSOs to each other or to PSTN
2
Wireless Network Design:
Problem
• Determine
–
–
–
–
Which radio towers to build (base station location)
How to assign subscribers to towers (service assignment)
Which MTSOs to use
Topology of MTSO/PSTN backbone network
• Maximize profit: revenue per subscriber served minus
infrastructure costs
3
Wireless Network Design Tool
4
Optimization Model for Wireless
Network Design: Sets
• L is the set of candidate tower locations.
• M is the set of subscriber locations.
• Cm is the set of tower locations that can service
subscribers in location m.
• Pl is the set of subscriber locations that can be
serviced by tower ℓ.
• K is the set of candidate MTSO locations
– Location 0 is the PSTN gateway
– K0 = K  {0}.
5
Optimization Model for Wireless
Network Design: Constants
• dm is the demand (channel equivalents) in subscriber location m.
• r is the annual revenue generated per channel.
• al is the cost of building and operating a tower at location .
•
•
•
•
bk is the cost of building an MTSO at location k.
clk the cost of providing a link from tower ℓ to MTSO k.
hjk the cost of providing a link from MTSO j to MTSO/PSTN k.
 is the maximum number of towers that an MTSO can support.
6
Optimization Model for Wireless
Network Design: Constants
• SIRmin is the minimum allowable signal-to-interference
ratio.
– s = 1 + 1/SIRmin.
• gmℓ is the attenuation factor from location m to tower ℓ.
– Ptarget is the desired strength for signals received at the
towers.
– To reach tower l with sufficient strength, a handset at
location m transmits with power level Ptarget / gmℓ.
7
Optimization Model for Wireless Network
Design: Power Control Example
P
g
Received signal strength
must be at least the
target value Ptar
tar
P
g
g
tar
13
13
 Ptar
13
Signal is attenuated by a factor of g13
Subscriber at Location 1
Assigned to Tower 3
Tower 3
8
Optimization Model for Wireless Network
Design: Decision Variables Used in the Model
• Binary variable yℓ=1 iff a tower is constructed at location ℓ.
• The integer variable xmℓ denotes the number of customers
(channel equivalents) at subscriber location m served by the
tower at location l.
• Binary variable zk=1 iff an MTSO or PSTN is established at
location k.
• Binary variable slk=1 iff tower l is connected to MTSO k.
• Binary variable wjk= 1 iff a link is established between
MTSOs j and k.
• ujk= units of flow on the link between MTSOs j and k.
9
Optimization Model for Wireless Network
Design: Signal-to-Interference Ratio (SIR)
g
P 2 g P
Tower 3
23
tar
tar
24
SIR 
g P
g
tar
14
2
Tower 4
P
tar
13
1
 2g 
 23 
 g 24 


P
g
tar
13
Subscriber at Location 1
assigned to Tower 3
P
g
tar
24
P
g
tar
24
Two subscribers at Location 2
assigned to Tower 4
10
Optimization Model for Wireless Network
Design: Quality of Service (QoS) Constraints
• For known attenuation factors, gml, the total received
power at tower location ℓ, PℓTOT , is given by
TOT

P
g m
 Ptarget  
xmj .
mM jCm g mj
• For a session assigned to tower ℓ
– the signal strength is Ptarget
– the interference is given by PℓTOT – Ptarget
• QoS constraint on minimum signal-to-interference
ratio for each session (channel) assigned to tower ℓ:
Ptarget
TOT

P
 Ptarget
 SIRmin
11
Optimization Model for Wireless Network
Design: Quality of Service (QoS) Constraints
Since tower  is built if y  1, this constraint can be
written as follows :
g m
1
xmj  1 
 (1  y )  


SIRmin
mM jC g mj
  L,
m

 g m  

where     d m  max mC \{ } 


g
mM
 mj  


 g m  
   0 if | Cm \ {} | 0.
where  max mC \{ } 


g
 mj  

m
m
12
Optimization Model for Wireless Network
Design: Integer Programming Model
The objective of the model is to maximize profit:
max r   xm   a y   bk zk   ck sk    h jk w jk .
mM Cm
L
K
L kK
K kK 0 \{ j }
 k
 

 j

 

revenue
Tower cos t
MTSO cost
Connection Cost
Backbone Cost
subject to the following constraints:
xm
x
C m

mM
m
g m
xmj

jCm g mj
 d m y
m  M ,   Cm , (1)
 dm
m  M ,
(2)
 s  (1  y )  
  L,
(3)
13
Optimization Model for Wireless Network
Design: Connection Constraints
s
kK
k
s k
s
L
k

y
  L,

zk
  L, k  K , (5)
 αz k
k  K ,
(4)
(6)
14
Optimization Model for Wireless
Network Design: Flow Constraints for
Backbone Construction
u jk
 | K | w jk
j  K , k  K 0 \ { j}, (7)
u jk
 | K | zk
j  K , k  K 0 \ { j}, (8)
z ,
(9)
u
 (u
kK
jK \{ k }
z0

k0
kj
 u jk )  uk 0
kK
 zk
 1.
k
k  K ,
(10)
(11)
15
Computational Experiments
•
Computing resources used
–
–
•
Compaq AlphaServer DS20E with dual EV6.7 (21264A) 667 MHz
processors and 4,096 MB of RAM
Latest releases of CPLEX and AMPL
Computational time
–
–
•
Increases substantially as |L| increases from 40 to 160
Very sensitive to value of 
Lower Bound Procedure
–
–
•
Solve IP with l = 0 for all l
Stop branch-and-bound process when the optimality gap (w.r.t LP) is
5%
Estimated Upper Bound Procedure
–
–
Relax integrality constraints on x, y, and s variables.
Solve MIP to optimality with l = 0 for all l
16
Data for Computational
Experiments
•
•
15
C

{


L
:
g

10
}.
Restrict m
m
Two Series of Test Problems:
1. Candidate towers placed randomly in 13.5 km by 8.5 km
service area
–
–
–
1,000 to 2,000 subscriber locations dm ~ u[1,10]
|L| drawn from {40, 80, 120, 160}
|K| = 5, placed randomly in central 1.5 km by 1.0 km rectangle
2. Simulated data for North Dallas area
–
–
–
|M| = 2,000 with dm ~ u[1,10]
|L| = 120
|K| = 5
17
Sample Results for Data Set 1
Upper Bound Procedure
Problem
|L|
|M|
R110
40
R160
Best Feasible Solution from Lower Bound
Procedure
Towers
Demand
Profit
CPU
Towers
Demand
Profit
CPU
Gap
1,000
35.6
92.60%
18.33
0:00:02
37
92.80%
18.22
0:00:20
0.60%
80
1,000
42.0
92.20%
17.55
0:08:43
39
87.50%
16.74
0:01:40
4.62%
R210
120
1,000
50.0
94.20%
17.66
0:43:18
51
91.50%
16.97
0:08:48
3.91%
R410
160
1,000
53.1
93.10%
16.81
0:57:02
53
90.30%
16.21
0:15:07
3.57%
R260
40
2,000
37.0
65.30%
26.72
0:00:14
38
65.30%
26.6
0:01:17
0.45%
R310
80
2,000
62.4
87.60%
34.93
0:10:04
65
86.80%
34.33
0:03:51
1.72%
R360
120
2,000
N/A
N/A
N/A
2:00:00
75
93.40%
36.42
0:14:52
5.00%
R460
160
2,000
N/A
N/A
N/A
2:00:00
88
93.70%
35.24
0:56:40
5.00%
• Solution times for Lower Bound Procedure varied from 30 seconds to 1 hour
of CPU time.
•Average value of 2.0 ≤ |Cm| ≤ 8.4.
18
Data Set 2: North Dallas Area
|M| = 2,000, dm ~ u[1,10], |L| = 120, and |K| = 5
19
Results for North Dallas
Problem
Upper Bound
Name MTSOs Towers Demand Profit
ND100
2
75.4
82.6% 31.55
ND200
2
75.4
85.5% 32.33
ND300
3
84.2
87.3% 33.00
ND400
2
79.5
86.3% 32.92
ND500
2
81.5
87.0% 32.93
ND600
2
80.7
86.1% 32.86
ND700
2
81.4
85.6% 32.36
Lower Bound Procedure
CPU MTSOs Towers Demand Profit CPU
Gap
0:39:05
2
77
82.0% 31.13 0:02:12 1.3%
0:55:18
3
78
84.8% 31.71 0:03:35 1.9%
1:13:05
2
82
85.2% 32.17 0:03:15 2.5%
0:45:29
2
80
85.6% 32.45 0:03:04 1.4%
0:40:46
2
82
85.0% 32.00 0:03:10 2.8%
0:46:06
2
82
85.9% 32.63 0:06:00 0.7%
0:53:35
2
82
84.7% 31.93 0:03:31 1.3%
20
Sample Results with Heuristics
Heuristic 1: |Cm| ≤ 1
Heuristic 2: |Cm| ≤ 2
Problem
|L|
|M|
Towers
Demand
Profit
CPU
Gap
Towers
Demand
Profit
CPU
Gap
R110
40
1,000
40
93.50%
18.09
0:00:01
1.31%
37
92.80%
18.22
0:00:14
0.60%
R160
80
1,000
67
92.40%
15.05
0:00:01
14.25%
47
90.40%
16.53
0:00:33
5.81%
R210
120
1,000
94
93.00%
13.03
0:00:01
26.22%
67
93.90%
15.88
0:01:14
10.08%
R410
160
1,000
94
83.90%
10.53
0:00:01
37.36%
76
92.10%
14.26
0:00:54
15.17%
R260
40
2,000
40
65.30%
26.38
0:00:03
1.27%
38
65.30%
26.6
0:00:45
0.45%
R310
80
2,000
79
89.80%
33.90
0:00:02
2.95%
65
86.50%
34.21
0:01:52
2.06%
R360
120
2,000
113
96.50%
34.39
0:00:02
10.30%
85
94.30%
35.98
0:03:36
6.15%
R460
160
2,000
141
96.40%
31.51
0:00:01
15.06%
100
93.30%
33.99
0:06:23
8.37%
Geo. Mean
3.55%
21
The Power-Revenue Trade-Off
22
Downlink Modeling
23
Conclusions and Directions for
Future Work
• IP model for W-CDMA problem
– Too many variables to be solved to optimality with commercial solvers
– Developed cuts and a two-step procedure to find high-quality solutions with
guaranteed optimality gap.
– Largest problems took up to 1 hour of CPU time
– Heuristic 2 reduces computation times by an order of magnitude and still finds
fairly good solutions
• Results for North Dallas problems on par with randomly generated data
sets.
• Model can be integrated into a planning tool; quick resolves with new
tower locations added to original data
• Extensions
– Construct a two-connected backbone with at least two gateways
– Consider sectoring
– Tighten the l parameters
24