# Goal-Programming-Driven Genetic Algorithm Model for Wireless Access Point Deployment Optimization

Authors: Chen-Shu Wang; Ching-Ter Chang
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Appropriate wireless access point deployment (APD) is essential for ensuring seamless user communication. Optimal APD enables good telecommunication quality, balanced capacity loading, and optimal deployment costs. APD is a typical NP-complex problem because improving wireless networking infrastructure has multiple objectives (MOs). This paper proposes a method that integrates a goal-programming-driven model (PM) and a genetic algorithm (GA) to resolve the MO-APD problem. The PM identifies the target deployment subject of four constraints: budget, coverage, capacity, and interference. The PM also calculates dynamic capacity requirements to replicate real wireless communication. Three experiments validate the feasibility of the PM. The results demonstrate the utility and stability of the proposed method. Decision makers can easily refer to the PM-identified target deployment before allocating APs.


---

## Body

## 1. Introduction

Appropriate wireless access point deployment (APD) is essential for ensuring seamless user communication. Optimal APD enables good telecommunication quality, balanced capacity loading, and optimal deployment costs. APD is a typical NP-complex problem [1] because it involves multiple decision objectives, such as budget [2–4], coverage [2, 5–8], interference [3, 4, 7], and dynamic capacity [1, 4, 6–9]. Furthermore, these objectives usually contradict each other [7]. For example, the number of APs is usually positively related to the wireless signal coverage rate and telecommunication reliability [1]. However, more APs increase deployment costs. These conflicting criteria should be considered simultaneously when solving APD problems [9, 10].In the last decade, many studies have attempted to solve APD optimally by considering multiple objectives (MOs). There are four main objectives: budget, coverage rate, capacity, and interference. Studies have attempted to identify maximal coverage. For example, Huang et al. developed a growth-planning algorithm to establish the maximal coverage range [11]. Zhao et al. used a point-to-point signal strength strategy to implement indoor AP location optimization for maximal coverage [12]. For the capacity objective, the capacity requirements of wireless networks compared to wired networks are particularly difficult to evaluate because users are dynamic and can move from place to place. This makes APD a dynamic and complex problem. The dynamic capacity requirement must be addressed to resolve APD [13] because users can access particular APs to balance loads [9, 14]. Finally, for the interference objective, too many APs of the same type and placed too close together may cause AP malfunction because of frequency interference. To avoid communication interference, some studies [6, 15] have suggested that APs should be arranged on different communication channels, but this leads to other communication channel assignment problems.This paper applies a goal-programming-driven model (PM) to the MO-APD problem. It uses goal programming (GP) to infer and model the PM and a genetic algorithm (GA) to search for near optimal solutions. These methods are easily applied to MO-APD problems to reflect real situations. The remainder of this paper is organized as follows: Section2 defines the problem; Section 3 details the PM; Section 4 presents a discussion on the PM solution process using a GA; Section 5 provides the results of numerical experiments which are given in this section; lastly, Section 6 offers a conclusion and suggestions for future research.


## 2. Description of the APD Problem

This research resolves the MO-APD problem according to four decision constraints: budget, coverage, capacity requirements, and interference. The PM identifies a feasible target deployment (T), which consists of three types of wireless APs, as shown in Table 1. This study conducted experiments and surveys that indicate that the coverage range and communication speed of a Type 3 AP are wider and faster, respectively, than AP Types 1 and 2. However, Type 1 AP equipment is cheaper than AP Types 2 and 3. Two APs may interfere with each other if they are the same type and are too near. Therefore, the PM must balance the four decision constraints and allocate three AP types in the target deployment of the APD problem. Table 2 lists the variables used in the proposed models.Table 1
A comparison of the three wireless AP types.
AP Type
Cost (NT$)
Range (m)
Speed (Mbit/s)
Manufacturers
Type 1 802.11 b/g
1365
30 to 89
54
ASUS, D-Link, Lantech, SMC
Type 2802.11 b/g
1710
33 to101
108
Corega, D-Link, PCI, SMC
Type 3 802.11 b/g/n
3138
51 to 163
300
Apple, ASUS, Buffalo, Corega,    D-LinkTable 2
Variables used in this paper.
Variable
Definition
B
i
j
The base station for the potential AP deployment area, whereiis a row and j is a column.i=1,2,…,n;j=1,2,…,m.
x
q
Represents the typeq AP allocated to Bij, where q∈[1,2,3] in Table 1. If xq=0, no AP has been allocated to Bij.
c
x
q
Represents the AP cost for each AP type,xq∈[1,2,3].
re
q
i
j
The networking capacity requirement betweenBi and Bj.


### 2.1. The Budget Constraint(θ(T))

Budget is the most important APD-MO constraint that directly affects the feasibility ofT. The cost function in (2.1) evaluates the total cost of T. Equation (2.2) evaluates the budget constraint. In (2.2), bgt represents the given budget constraint for the AP allocation for T:
(2.1)CST(T)=∑i∑jCxqBi,j,∀Xq≠0,i=1,2,…,n,j=1,2,…,m,(2.2)ifCST(T)<bgt,θ(T)=1,elseθ(T)=bgtCST(T).


### 2.2. The Coverage Constraint(Φ(T))

Figure1 shows that to enable seamless user communication, two APs are allocated, but two capacity requirements (req2,1 and req2,3) have no signal coverage. The coverage function (CVG(T)) evaluates the signal coverage area of T. Equation (2.3) evaluates the coverage fulfillment rate:
(2.3)Φ(T)=CVG(T)targetarea.Figure 1
The signal coverage illustration.


### 2.3. The Capacity Constraint(Ψ(T))

Figure2 shows a dynamic capacity scenario. The target area allocates two Type 1 APs (AP1 and AP2), and two APs simultaneously cover the capacity requirements (req22). For time slot 1 (T1), the capacity requirements of req12,req13,andreq22 access AP1, and the capacity requirements of req31andreq32 access AP2. Therefore, for time slot T1, AP1 and AP2 must provide 55 and 25 mbit/s capacity, respectively. In time slot T2, req22 shifts connection from AP1 to AP2 for balance loading. Therefore, for time slot T2, AP1 and AP2 must provide 35 and 45 mbit/s, respectively. Actual capacity requirements are difficult to evaluate accurately. A Monte Carlo simulation algorithm—that simulates the capacity of T—implements the DCPij(T) function. Equation (2.4) evaluates the capacity fulfillment rate:
(2.4)ifDCPij(T)>reqij,Ψ(T)=1,i=1,2,…,n;j=1,2,…,m,elseΨ(T)=DCPij(T)reqij.Figure 2
The dynamic capacity requirements of two APs. The blue area represents time slot 1 (T1) and the pink area represents time slot 2 (T2).


### 2.4. The Interference Constraint(ω(T))

Figure3 shows that many Type 1 APs are used to maximize coverage and capacity of T because of budget constraints. However, too many APs of the same type and allocated too near to each other may lead to AP malfunction because of AP frequency interference. For example, Figure 3 shows a perfect coverage design. However, it also shows an increased interference rate. The interference function (IFT(T)) evaluates the interference area of T. Equation (2.5) evaluates the interference fulfillment rate:
(2.5)ω(T)=1-IFT(T)targetarea.Figure 3
The frequency interference illustration.


## 2.1. The Budget Constraint(θ(T))

Budget is the most important APD-MO constraint that directly affects the feasibility ofT. The cost function in (2.1) evaluates the total cost of T. Equation (2.2) evaluates the budget constraint. In (2.2), bgt represents the given budget constraint for the AP allocation for T:
(2.1)CST(T)=∑i∑jCxqBi,j,∀Xq≠0,i=1,2,…,n,j=1,2,…,m,(2.2)ifCST(T)<bgt,θ(T)=1,elseθ(T)=bgtCST(T).


## 2.2. The Coverage Constraint(Φ(T))

Figure1 shows that to enable seamless user communication, two APs are allocated, but two capacity requirements (req2,1 and req2,3) have no signal coverage. The coverage function (CVG(T)) evaluates the signal coverage area of T. Equation (2.3) evaluates the coverage fulfillment rate:
(2.3)Φ(T)=CVG(T)targetarea.Figure 1
The signal coverage illustration.


## 2.3. The Capacity Constraint(Ψ(T))

Figure2 shows a dynamic capacity scenario. The target area allocates two Type 1 APs (AP1 and AP2), and two APs simultaneously cover the capacity requirements (req22). For time slot 1 (T1), the capacity requirements of req12,req13,andreq22 access AP1, and the capacity requirements of req31andreq32 access AP2. Therefore, for time slot T1, AP1 and AP2 must provide 55 and 25 mbit/s capacity, respectively. In time slot T2, req22 shifts connection from AP1 to AP2 for balance loading. Therefore, for time slot T2, AP1 and AP2 must provide 35 and 45 mbit/s, respectively. Actual capacity requirements are difficult to evaluate accurately. A Monte Carlo simulation algorithm—that simulates the capacity of T—implements the DCPij(T) function. Equation (2.4) evaluates the capacity fulfillment rate:
(2.4)ifDCPij(T)>reqij,Ψ(T)=1,i=1,2,…,n;j=1,2,…,m,elseΨ(T)=DCPij(T)reqij.Figure 2
The dynamic capacity requirements of two APs. The blue area represents time slot 1 (T1) and the pink area represents time slot 2 (T2).


## 2.4. The Interference Constraint(ω(T))

Figure3 shows that many Type 1 APs are used to maximize coverage and capacity of T because of budget constraints. However, too many APs of the same type and allocated too near to each other may lead to AP malfunction because of AP frequency interference. For example, Figure 3 shows a perfect coverage design. However, it also shows an increased interference rate. The interference function (IFT(T)) evaluates the interference area of T. Equation (2.5) evaluates the interference fulfillment rate:
(2.5)ω(T)=1-IFT(T)targetarea.Figure 3
The frequency interference illustration.


## 3. Proposed Model to Solve MO-APD

Two main approaches can be used to formulate MO-APD. One approach is the cost-oriented approach, which aims to minimize total cost subject to MO performance constraints. This study formulated MO-APD using the cost-oriented approach as shown inProposal 1 (P1). GAL-CVG, GAL-CP, and GAL-IFT are the given constraints for coverage rate, capacity fulfillment rate, and interference fulfillment rate, respectively.(P1)(3.1)Min⁡CST(T)≤bgt,
subject to
(3.2)Φ(T)≥GAL-CVG,(3.3)Ψ(T)≥GAL-CP,(3.4)ω(T)≥GAL-IFT.Equations (3.2)–(3.4) are the coverage, capacity, and interference constraints. Equation (3.1) is the objective function, which minimizes the total cost subject to multiple decision constraints (3.2)–(3.4).The second approach is performance oriented, and it maximizes the performance of target deployment subjects to real constraints (e.g., budget). This study reformulated the MO-APD using the performance-oriented method, shown inProposal  2  (P2).(P2)(3.5)Max⁡Φ(T)+Ψ(T)+ω(T),
subject to (3.1)–(3.4).Equation (3.5) is the objective function in P2, which maximizes the coverage, capacity fulfillment, and interference fulfillment rates of T subject to budgetary (3.1) and other decision constraints (3.2)–(3.4). GP aids MO decision-making problem modeling. It was first introduced by Charnes and Cooper [16] and further developed by Tamiz et al. [17], Romero [18], and Chang [19]. Various types of GP approaches exist, such as lexicographic GP, weighted GP, MINMAX (Chebyshev) GP, and multichoice GP [19]. To enable decision makers to easily set the constraint weighting according to their preferences, this study used a weighted GP approach to translate (P2) into the (PM). wcvg, wcp, and wIFT are the important weights (between 0 and 1) for the GAL-CVG, GAL-CP, and GAL-IFT constraints, respectively.(PM)(3.6)Min⁡Wbgt(bgt+)+Wcvg(cvg-)+Wcp(cp-)+WIFT(IFT-),
subject to
(3.7)CST(T)-bgt++bgt-=bgt,(3.8)Φ(T)-cvg++cvg-=GAL-CVG,(3.9)Ψ(T)-cp++cp-=GAL-CP,(3.10)ω(T)-IFT++IFT-=GAL-IFT,(3.11)bgt+,bgt-,cvg+,cvg-,cp+,cp-,IFT+,IFT-≥0.


## 4. Process for Solving the PM Using a GA

The GA is a stochastic searching method that uses the mechanics of natural selection to solve optimization problems. The GA was developed from the theory of natural selection [20]. Because the GA is a good stochastic technique for solving combinatorial optimization problems, this study uses the GA as the PM search tool, as shown in Figure 4.Figure 4
GA-based PM solution process.An initial solution population is randomly created. The fitness of each individual in the population then determines whether it survives. Termination criteria (such as the generation size or the fitness value exceeding the threshold) determine the target deployment (T) to be achieved. Finally, genetic operators such as selection, crossover, and mutation identify the next generation. After meeting a number of iterations or predefined criteria, a near optimal solution is found.


### 4.1. Representation Structure: Encode/Decode

A graph represents a target deployment (T) that can also be expressed as a two-dimensional matrix. In the graph, each potential base station (Bi,j) has two states: AP (Bi,j=1) allocated and no AP (Bi,j=0) allocated. A base station with an allocated AP must have an AP type (xq=[1,2,3]). n×m bit strings were used as chromosomes to represent T:(4.1)T=[B1,1B1,2⋯B1,mB2,1B2,2⋯B2,m⋮⋮⋮⋮Bn,1Bn,2⋯Bn,m].


### 4.2. Evaluation Function

The PM objective function (F(i)) was used as a GA evaluation function in (4.2). All variables in (4.2) are defined as in the PM:
(4.2)F(i)=Wbgt(bgt+)+Wcvg(cvg-)+Wcp(cp-)+WIFT(IFT-).


### 4.3. GA Manipulations

(1)
Selection: roulette wheel selection ensures that highly fit chromosomes produce more offspring. This method selects a candidate network according to its survival probability, which is equal to its fitness relative to the whole population, as shown in (4.3):
(4.3)[F(i)∑F(i)].
(2)
Crossover: the crossover method randomly selects two chromosomes from the mating pool for mating. Crossover site C is randomly selected in the interval [1,n×m]. Two new chromosomes, called offspring, are then obtained by swapping all characters between position C and n×m.
(3)
Mutation: the combined reproduction and crossover methods occasionally lose potentially useful chromosome information. Mutation is introduced to overcome this. It is implemented by randomly complementing a bit (0 to 1 and vice versa). This ensures that good chromosomes are not permanently lost.


## 4.1. Representation Structure: Encode/Decode

A graph represents a target deployment (T) that can also be expressed as a two-dimensional matrix. In the graph, each potential base station (Bi,j) has two states: AP (Bi,j=1) allocated and no AP (Bi,j=0) allocated. A base station with an allocated AP must have an AP type (xq=[1,2,3]). n×m bit strings were used as chromosomes to represent T:(4.1)T=[B1,1B1,2⋯B1,mB2,1B2,2⋯B2,m⋮⋮⋮⋮Bn,1Bn,2⋯Bn,m].


## 4.2. Evaluation Function

The PM objective function (F(i)) was used as a GA evaluation function in (4.2). All variables in (4.2) are defined as in the PM:
(4.2)F(i)=Wbgt(bgt+)+Wcvg(cvg-)+Wcp(cp-)+WIFT(IFT-).


## 4.3. GA Manipulations

(1)
Selection: roulette wheel selection ensures that highly fit chromosomes produce more offspring. This method selects a candidate network according to its survival probability, which is equal to its fitness relative to the whole population, as shown in (4.3):
(4.3)[F(i)∑F(i)].
(2)
Crossover: the crossover method randomly selects two chromosomes from the mating pool for mating. Crossover site C is randomly selected in the interval [1,n×m]. Two new chromosomes, called offspring, are then obtained by swapping all characters between position C and n×m.
(3)
Mutation: the combined reproduction and crossover methods occasionally lose potentially useful chromosome information. Mutation is introduced to overcome this. It is implemented by randomly complementing a bit (0 to 1 and vice versa). This ensures that good chromosomes are not permanently lost.


## 5. Experiment Validation and Analysis

To validate the efficiency and feasibility of the PM at resolving APD problems, three experiments were designed and implemented. Experiment 1 included four subtests to validate parameter combination types consisting of different decision variables. Experiment 2 included two subtests to confirm the ability of the PM to solve dynamic capacity problems. Experiment 3 ensured that the PM is suitable for large-scale problems and tested the GA parameter effects.


### 5.1. Experiment 1: Decision Variable Combination Validation

Four subtests consisting of different decision variables and important weights validated the ability of the PM to solve APD problems. The target area in Figure5 is a 90 km2 irregularly shaped area. The capacity requirements in Figure 5 were identical for all subtests. All reqij could move around the target area, where signal coverage was present. For comparative purposes, the GA parameters of the four subtests—population size (600), terminated generation (500), crossover rate (0.4), and mutation rate (0.1)—were fixed. Table 3 lists the other decision variables.Table 3
Decision variables and import weights for four subtests in Experiment  1.
Decision variable
E1.a
E1.b
E1.c
E1.d
Budget
30000 (Wbgt = .25)
30000 (Wbgt = .40)
35000 (Wbgt = .25)
Coverage rate
85% (Wcvg = .25)
85% (Wcvg = .20)
85% (Wcvg = .25)
Capacity fulfillment rate
80% (Wcp = .25)
80% (Wcp = .20)
80% (Wcp = .25)
Interference fulfillment rate
80% (WIFT =  25)
80% (WIFT = .20)
80% (WIFT =  25)
90% (WIFT = 25)
Note that important weights are marked in parentheses.Figure 5
Capacity requirements for Experiment 1.Table4 shows the four subtests formulated as Model I and Model II according to the PM. To avoid the randomizing effect of the GA, all subtests were run three times with the same parameters on the same machine. The result averages are reported. Table 5 shows the analysis of the experiment results. The E1.a and E1.b  results show that the important budget weight is less in E1.b than in E1.a. Therefore, only 15 APs (on average) are deployed for E1.b, as shown in Figure 6. The results also show that the decision maker must either increase the budget or adjust the other decision objectives. For example, E1.b shows that the coverage and capacity fulfillment rates can only reach 0.7 at the current budget. As the budget increases from 30000 (in E1.b) to 35000 (in E1.c and E1.d), the number of APs deployed increases to 22 (on average). The coverage and capacity rates increase from 0.7 in E1.b to 0.82 in E1.c and E1.d. E1.d deployed more APs (23) at a lower cost than E1.a (22 APs). Figure 6 shows that the APs in E1.c and E1.d are spread evenly in the target area to avoid interference. Figure 7 shows the convergence trends for all subtests. T emerges after 100–150 iterations.Table 4
Model I and Model II for resolving the four subtests.
Model I (for subtests E1.a and E1.b)
Model II (for subtests E1.c and E1.d)
Min
0.2
5
a
(
0.4
)
b
bg
t
+
+
0.2
5
a
(
0.2
)
b
cv
g
-
+
0.2
5
a
(
0.2
)
b
c
p
-
+
0.2
5
a
(
0.2
)
b
IF
T
-
Min
0.25
bg
t
+
+
0.250
cv
g
-
+
0.25
c
p
-
+
0.25
IF
T
-
Subject
to
Subject
to
CST
(
T
)
-
bg
t
+
+
bg
t
-
=
30000
CST
(
T
)
-
bg
t
+
+
bg
t
-
=
30000
Φ
(
T
)
-
cv
g
+
+
cv
g
-
=
0.85
Φ
(
T
)
-
cv
g
+
+
cv
g
-
=
0.85
Ψ
(
T
)
-
c
p
+
+
c
p
-
=
0.8
Ψ
(
T
)
-
c
p
+
+
c
p
-
=
0.8
ω
(
T
)
-
IF
T
+
+
IF
T
-
=
0.8
ω
(
T
)
-
IF
T
+
+
IF
T
-
=
0
.
8
c
(
0.9
)
d
bg
t
+
,
bg
t
-
,
cv
g
+
,
cv
g
-
,
c
p
+
,
c
p
-
,
IF
T
+
,
IF
T
-
≥
0
bg
t
+
,
bg
t
-
,
cv
g
+
,
cv
g
-
,
c
p
+
,
c
p
-
,
IF
T
+
,
IF
T
-
≥
0
Note thatais for E1(a), bfor E1(b), cfor E1(c), and  dfor E1(d).Table 5
Analysis of the results of Experiment  1.
Indicator
E1.a
E1.b
E1.c
E1.d
Fitness
.9534
.9420
.9568
.9567
Time (s)
160.0993
160.106
159.0593
170.4233
Cost
36954
29360
34647
34694
Coverage rate
.85
.6967
.8167
.8233
Capacity fulfillment rate
.8490
.6981
.8189
.8269
Interference fulfillment rate
.94
.9867
.94
.99
Number of APs
22
15
21
23Figure 6
AP deployment results for the four subtests in Experiment 1.Figure 7
The convergence trends for the four subtests in Experiment 1.


### 5.2. Experiment 2: Dynamic Capacity Requirement Validation

Experiment 2 consisted of two subtests to validate the ability of the PM to resolve dynamic capacity requirements. Figure6(a) shows that in subtest E2.a, most capacity requirements are in the central area of the target (32 km2). Figure 6(b) shows that in subtest E2.b, the capacity requirements are scattered in the corners of the target area. Table 6 shows that the capacity requirements and all default decision variables are identical for both tests. The GA parameters—population size (600), terminated generation (500), crossover rate (0.4), and mutation rate (0.1)—were fixed to enable result comparison. To avoid random GA effects, all subtests were run three times with the same parameters on the same machine. The result averages are reported.Table 6
Decision variable and important weights for Experiment  2.
Decision variable
Variable value
Budget
15000 (Wbgt = .3)
Coverage rate
85% (Wcvg = .15)
Interference fulfill rate
85% (WIFT = .15)
Capacity fulfill rate
95% (Wcp = .4)
Note that the important weights are marked in parentheses.Table7 shows the experiment results analysis. As expected, APD follows the capacity requirements, as shown in Figures 8(a) and 8(b). Figures 8(a) and 8(b) also show that APs are more central in E2.a than in E2.b to fulfill the capacity requirements. Although the capacity requirements are the same in both experiments, E2.a requires nine APs, which is more than E2.b (seven APs). Therefore, capacity requirements are dynamic, and T requires more APs to manage the capacity requirement increase in  E2.a.Table 7
Analysis of the results of Experiment  2.
Indicator
E2.a
E2.b
Fitness
1
1
Time (s)
5.1883
4.7797
Cost
14387
14068
Coverage rate
.8518
.8518
Capacity fulfillment rate
1
1
Interference fulfillment rate
.9815
.9259
Number of APs
9 APs
7 APsThe capacity requirement and results of Experiment 2 for (a) subtest E2.a and (b) subtest E2.b. The numbers represent the capacity requirements.
(a)
(b)


### 5.3. Experiment 3: The Effect of Large-Scale Problems and GA Parameters on Validation

Two subtests of Experiment 3 were designed as large-scale problems. Table8 lists the decision variables and the important weights. Experiment 3 also tested GA parameter combinations, including crossover and mutation rates.Table 8
Decision variables and important weights for Experiment  3.
Objective
E3.a
E3.b
Target area
2250 km2
90000 km2
Budget (Wbgt = .55)
1350000
5650000
Coverage rate (Wcvg = .15)
85%
85%
Capacity and interference fulfillment  rates (Wcp = WIFT =  0.15)
80%
80%
Note that the capacity requirements are shown in the Appendix and the important weights are marked in parentheses.The results analysis in Table9 shows that the PM is more sensitive to crossover rate. Generation—as an evaluation indicator for subtests E3.a and E3.b—shows that feasible deployment can be reached in the following order of crossover rates: 0.6 (converged by 22 iterations), 0.4 (converged by 70 iterations), and 0.2 (converged by 95 iterations). However, no such pattern exists for mutation rate in either test. Therefore, a crossover rate of 0.4 and a mutation rate of 0.1 are recommended for experiment implementation to avoid GA parameter effects. The results in Table 9 show that large-scale problems (E3.b) can be resolved within an acceptable time (4191.52 s, approximately 1 h).Table 9
Analysis of the results of Experiment  3.
Indicator
Fixed mutation rate (m=0.1)
Fixed crossover rate (c=0.4)
C
=
0.2
C
=
0.4
C
=
0.6
m
=
0.01
M
=
0.2
Fitness
1 (.9869)
1 (1)
1 (1)
1 (1)
1 (1)
Generation
96 (93)
53 (86)
18 (26)
9 (94)
22 (62)
Time
489.2550 (3795.2)
526.2310 (5080.5)
552.5640 (3880.6)
496.0540 (3334.8)
541.5390 (4866.5)
Cost
1,349,670 (5,736,480)
1,326,549 (5,593,797)
1,347,933 (5,576,205)
1,348,896 (5,580,897)
1,324,479 (5,566,053)
Capacity fulfillment rate
.8485 (.8641)
.8384 (.8536)
.8495 (.8486)
.8450 (.8502)
.8531 (.8560)
Coverage fulfillment rate
.8500 (.8536)
.8496 (.8634)
.8484 (.8506)
.8496 (.8510)
.8496 (.8559)
Interference
.8996 (.8929)
.9100 (.8914)
.8996 (.8891)
.9048 (.8987)
.9012 (.8952)
The experiment results for E3(b) are in parentheses.


## 5.1. Experiment 1: Decision Variable Combination Validation

Four subtests consisting of different decision variables and important weights validated the ability of the PM to solve APD problems. The target area in Figure5 is a 90 km2 irregularly shaped area. The capacity requirements in Figure 5 were identical for all subtests. All reqij could move around the target area, where signal coverage was present. For comparative purposes, the GA parameters of the four subtests—population size (600), terminated generation (500), crossover rate (0.4), and mutation rate (0.1)—were fixed. Table 3 lists the other decision variables.Table 3
Decision variables and import weights for four subtests in Experiment  1.
Decision variable
E1.a
E1.b
E1.c
E1.d
Budget
30000 (Wbgt = .25)
30000 (Wbgt = .40)
35000 (Wbgt = .25)
Coverage rate
85% (Wcvg = .25)
85% (Wcvg = .20)
85% (Wcvg = .25)
Capacity fulfillment rate
80% (Wcp = .25)
80% (Wcp = .20)
80% (Wcp = .25)
Interference fulfillment rate
80% (WIFT =  25)
80% (WIFT = .20)
80% (WIFT =  25)
90% (WIFT = 25)
Note that important weights are marked in parentheses.Figure 5
Capacity requirements for Experiment 1.Table4 shows the four subtests formulated as Model I and Model II according to the PM. To avoid the randomizing effect of the GA, all subtests were run three times with the same parameters on the same machine. The result averages are reported. Table 5 shows the analysis of the experiment results. The E1.a and E1.b  results show that the important budget weight is less in E1.b than in E1.a. Therefore, only 15 APs (on average) are deployed for E1.b, as shown in Figure 6. The results also show that the decision maker must either increase the budget or adjust the other decision objectives. For example, E1.b shows that the coverage and capacity fulfillment rates can only reach 0.7 at the current budget. As the budget increases from 30000 (in E1.b) to 35000 (in E1.c and E1.d), the number of APs deployed increases to 22 (on average). The coverage and capacity rates increase from 0.7 in E1.b to 0.82 in E1.c and E1.d. E1.d deployed more APs (23) at a lower cost than E1.a (22 APs). Figure 6 shows that the APs in E1.c and E1.d are spread evenly in the target area to avoid interference. Figure 7 shows the convergence trends for all subtests. T emerges after 100–150 iterations.Table 4
Model I and Model II for resolving the four subtests.
Model I (for subtests E1.a and E1.b)
Model II (for subtests E1.c and E1.d)
Min
0.2
5
a
(
0.4
)
b
bg
t
+
+
0.2
5
a
(
0.2
)
b
cv
g
-
+
0.2
5
a
(
0.2
)
b
c
p
-
+
0.2
5
a
(
0.2
)
b
IF
T
-
Min
0.25
bg
t
+
+
0.250
cv
g
-
+
0.25
c
p
-
+
0.25
IF
T
-
Subject
to
Subject
to
CST
(
T
)
-
bg
t
+
+
bg
t
-
=
30000
CST
(
T
)
-
bg
t
+
+
bg
t
-
=
30000
Φ
(
T
)
-
cv
g
+
+
cv
g
-
=
0.85
Φ
(
T
)
-
cv
g
+
+
cv
g
-
=
0.85
Ψ
(
T
)
-
c
p
+
+
c
p
-
=
0.8
Ψ
(
T
)
-
c
p
+
+
c
p
-
=
0.8
ω
(
T
)
-
IF
T
+
+
IF
T
-
=
0.8
ω
(
T
)
-
IF
T
+
+
IF
T
-
=
0
.
8
c
(
0.9
)
d
bg
t
+
,
bg
t
-
,
cv
g
+
,
cv
g
-
,
c
p
+
,
c
p
-
,
IF
T
+
,
IF
T
-
≥
0
bg
t
+
,
bg
t
-
,
cv
g
+
,
cv
g
-
,
c
p
+
,
c
p
-
,
IF
T
+
,
IF
T
-
≥
0
Note thatais for E1(a), bfor E1(b), cfor E1(c), and  dfor E1(d).Table 5
Analysis of the results of Experiment  1.
Indicator
E1.a
E1.b
E1.c
E1.d
Fitness
.9534
.9420
.9568
.9567
Time (s)
160.0993
160.106
159.0593
170.4233
Cost
36954
29360
34647
34694
Coverage rate
.85
.6967
.8167
.8233
Capacity fulfillment rate
.8490
.6981
.8189
.8269
Interference fulfillment rate
.94
.9867
.94
.99
Number of APs
22
15
21
23Figure 6
AP deployment results for the four subtests in Experiment 1.Figure 7
The convergence trends for the four subtests in Experiment 1.


## 5.2. Experiment 2: Dynamic Capacity Requirement Validation

Experiment 2 consisted of two subtests to validate the ability of the PM to resolve dynamic capacity requirements. Figure6(a) shows that in subtest E2.a, most capacity requirements are in the central area of the target (32 km2). Figure 6(b) shows that in subtest E2.b, the capacity requirements are scattered in the corners of the target area. Table 6 shows that the capacity requirements and all default decision variables are identical for both tests. The GA parameters—population size (600), terminated generation (500), crossover rate (0.4), and mutation rate (0.1)—were fixed to enable result comparison. To avoid random GA effects, all subtests were run three times with the same parameters on the same machine. The result averages are reported.Table 6
Decision variable and important weights for Experiment  2.
Decision variable
Variable value
Budget
15000 (Wbgt = .3)
Coverage rate
85% (Wcvg = .15)
Interference fulfill rate
85% (WIFT = .15)
Capacity fulfill rate
95% (Wcp = .4)
Note that the important weights are marked in parentheses.Table7 shows the experiment results analysis. As expected, APD follows the capacity requirements, as shown in Figures 8(a) and 8(b). Figures 8(a) and 8(b) also show that APs are more central in E2.a than in E2.b to fulfill the capacity requirements. Although the capacity requirements are the same in both experiments, E2.a requires nine APs, which is more than E2.b (seven APs). Therefore, capacity requirements are dynamic, and T requires more APs to manage the capacity requirement increase in  E2.a.Table 7
Analysis of the results of Experiment  2.
Indicator
E2.a
E2.b
Fitness
1
1
Time (s)
5.1883
4.7797
Cost
14387
14068
Coverage rate
.8518
.8518
Capacity fulfillment rate
1
1
Interference fulfillment rate
.9815
.9259
Number of APs
9 APs
7 APsThe capacity requirement and results of Experiment 2 for (a) subtest E2.a and (b) subtest E2.b. The numbers represent the capacity requirements.
(a)
(b)


## 5.3. Experiment 3: The Effect of Large-Scale Problems and GA Parameters on Validation

Two subtests of Experiment 3 were designed as large-scale problems. Table8 lists the decision variables and the important weights. Experiment 3 also tested GA parameter combinations, including crossover and mutation rates.Table 8
Decision variables and important weights for Experiment  3.
Objective
E3.a
E3.b
Target area
2250 km2
90000 km2
Budget (Wbgt = .55)
1350000
5650000
Coverage rate (Wcvg = .15)
85%
85%
Capacity and interference fulfillment  rates (Wcp = WIFT =  0.15)
80%
80%
Note that the capacity requirements are shown in the Appendix and the important weights are marked in parentheses.The results analysis in Table9 shows that the PM is more sensitive to crossover rate. Generation—as an evaluation indicator for subtests E3.a and E3.b—shows that feasible deployment can be reached in the following order of crossover rates: 0.6 (converged by 22 iterations), 0.4 (converged by 70 iterations), and 0.2 (converged by 95 iterations). However, no such pattern exists for mutation rate in either test. Therefore, a crossover rate of 0.4 and a mutation rate of 0.1 are recommended for experiment implementation to avoid GA parameter effects. The results in Table 9 show that large-scale problems (E3.b) can be resolved within an acceptable time (4191.52 s, approximately 1 h).Table 9
Analysis of the results of Experiment  3.
Indicator
Fixed mutation rate (m=0.1)
Fixed crossover rate (c=0.4)
C
=
0.2
C
=
0.4
C
=
0.6
m
=
0.01
M
=
0.2
Fitness
1 (.9869)
1 (1)
1 (1)
1 (1)
1 (1)
Generation
96 (93)
53 (86)
18 (26)
9 (94)
22 (62)
Time
489.2550 (3795.2)
526.2310 (5080.5)
552.5640 (3880.6)
496.0540 (3334.8)
541.5390 (4866.5)
Cost
1,349,670 (5,736,480)
1,326,549 (5,593,797)
1,347,933 (5,576,205)
1,348,896 (5,580,897)
1,324,479 (5,566,053)
Capacity fulfillment rate
.8485 (.8641)
.8384 (.8536)
.8495 (.8486)
.8450 (.8502)
.8531 (.8560)
Coverage fulfillment rate
.8500 (.8536)
.8496 (.8634)
.8484 (.8506)
.8496 (.8510)
.8496 (.8559)
Interference
.8996 (.8929)
.9100 (.8914)
.8996 (.8891)
.9048 (.8987)
.9012 (.8952)
The experiment results for E3(b) are in parentheses.


## 6. Conclusion

Optimal wireless LAN (WLAN) design is important to ensure seamless user communication. Appropriately locating wireless APs for WLANs is important. Optimal APD enables high telecommunication quality, balanced capacity loading, and optimal deployment costs. This study proposes a GP-driven model integrated with a GA to solve MO-APD subject to four constraints: budget, capacity, interference, and coverage. The experiment results show that the PM resolves many APD problems and achieves dynamic capacity replication. Results confirm the ability of the PM to solve large-scale APD problems. Future research should focus on other applications and further verification of PM.



---

*Source: 780637-2012-07-12.xml*