Performance Evaluation of Heuristic Algorithms for Optimal Location of Controllers in Wireless Networks

Abstract

In this paper, we have presented the new Ant Colony Optimization scheme for the optimal location of controllers in wireless networks, which is an important problem in the process of designing cellular mobile networks. Our objective functions are determined by the total distance based on pheromone matrix of ants satisfies capacity constraints to find good approximate solutions. Our proposed algorithms may give feasible solutions to this problem based on the global search for high quality feasible solutions. The experimental results show that our pro-posed algorithm has achieved a much better performance than the previous approaches based on heuristic and evolution algorithms.

1 Introduction

The size and complexity of computer networks have been growing very fast in the last decade. In the past, a computer network usually only served a small number of devices. Nowadays, it is common to find a computer network that serves hundreds of even thousands of devices. It seems they this incredible growth will continue as the customers needs and the telecommunication technology keep growing. As the size and complexity of computer networks grow, so too does the need for good design strategies. Optimal the placement of base stations in the designing of a wireless network is very important for a cheaper and better customer service. This issue is related to the problems of location of devices [1, 2]. The objective of Terminal Assignment (TA) problem [3] involves with determining minimum cost links to form a network by connecting a given collection of terminals to a given collection of concentrators. The capacity requirement of each terminal is known and may vary from one terminal to another. The capacity of concentrators is known. The cost of the link from each terminal to each concentrator is also known. The problem is now to identify for each terminal the concentrator to which it should be assigned, under two constraints: Each terminal must be connected to one and only one of the concentrators, and the aggregate capacity requirement of the terminals connected to any concentrator must not exceed the capacity of that concentrator. The assignment of BTSs to switches problem introduced in [4]. In which it is considered that both the BTSs and controllers of the network are already positioned, and its objective is to assign each BTSs to a controller, in such a way that a capacity constraint has to be fulfilled. The objective function in this case is then formed by two terms: the sum of the distances from BTSs to the switches must be minimized, and also there is another term related to handovers, between cells assigned to different switches which must be minimized.

2 Problem Formulation

Let us consider a mobile communication network formed by N nodes (BTSs), where a set of M controllers must be positioning in order to manage the network traffic. It is always fulfilled that $M \ll N$, and in the majority of cases. We start from the premise that the existing BTSs infrastructure must be used to locate the switches, since it saves costs. The complete optimal location of controller problem (OLCP) has to deal with two issues in Fig. 1. First, the selection of the N controllers in M nodes, second for each selection, an associated TA problem [5].

Fig. 1

Optimal location of controller problem model

Let $l_{1} ,l_{2} , \ldots ,l_{N}$ is set of N Base Stations (BTSs), $w_{1} ,w_{2} , \ldots ,w_{N}$ is the weight requirement of BTS, $\left( {l_{j1} ,l_{j2} } \right)$ is the coordinates of BTS $l_{j} \forall j = 1 \ldots N$ on the Euclidean grid; Let $r_{1} ,r_{2} , \ldots ,r_{M}$ is set of Base Station Controllers (BSCs) should be established, $p_{1} ,p_{2} , \ldots ,p_{M}$ is the capacity can satisfy of BSC $r_{i}$, $\left( {r_{i1} ,r_{i2} } \right)$ is the coordinates of BSC $r_{i} ,\forall i = 1 \ldots M$ on the Euclidean grid. The weights and capacity are positive integers and $w_{i} < \hbox{min} \left\{ {p_{1} ,p_{2} , \ldots ,p_{M} } \right\},\forall i = 1,2 \ldots ,N$. Assign each BTS to one of BSC such that no BSC exceeds its capacity. Let $\tilde{x} = \left\{ {\tilde{x}_{1} ,\tilde{x}_{2} , \ldots ,\tilde{x}_{M} } \right\}$ be a vector such that means that BTS $l_{j}$ has been assigned to BSC $r_{i}$, with is an integer such that $\tilde{x}_{j} = i$. Capacity of each BSC must be satisfied $\sum\nolimits_{{j \in R_{i} }} w_{j} < p_{i} ,i = 1 \ldots M$ where, $R_{i} = \left\{ {j|\tilde{x}_{j} = i} \right\}$, i.e., $R_{i}$ represents the BTSs that are assigned to BSC $r_{i}$. Let $X = \left\{ {x_{ij} } \right\}_{{M \times \left( {N - M} \right)}}$ is a binary matrix describes the connection between the BTS $l_{j}$ to BSC $r_{i}$. Such that, $x_{ij} = 1$ means that BTS $l_{j}$ has been connected to BSC $r_{i}$, and otherwise. The objective of optimal location of controller problem is minimize the total connectivity costs between $(N - M)$ BTSs to $M$ BSCs. The cost of connection from BTS $l_{j}$ to BSC $r_{i}$ is calculated by $cost\,t_{ij} = \sqrt {(l_{j1} - r_{i1} )^{2} + (l_{j2} - r_{i2} )^{2} }$. The problem can be defined as follows:

$$ f\left( {\tilde{x}} \right) = \sum\limits_{i = 1}^{M} \sum\limits_{j = 1}^{N - M} cost\,t_{ij} x_{ij} \to \hbox{min} $$

(1)

Subject to:

$$ \sum\limits_{i = 1}^{M} x_{ij} = 1,\quad \forall j = \overline{1 \ldots N - M} $$

(2)

$$ \sum\limits_{i = j}^{N - M} w_{j} x_{ij} \le p_{i} ,\quad \forall i = \overline{1 \ldots M} $$

(3)

3 Related Works and Our Works

Both TA and OCLP are NP-complete combinatorial optimization problems [1, 6, 7], so heuristic approach is a good choice [8]. All the previous work on the TA provides powerful approaches when the cost of assigning a single terminal to a given concentrator is known before running the algorithms. The cost function is the Euclidean distance between a terminal and its associated concentrator [1]. A Greedy is the first algorithm proposed by Abuali et al. in [3] for solving the TA. Khuri and Chui proposed a GA (Genetic Algorithm) with a penalty function as an alternative method for solving the TA [4]. They showed its performance by means of the comparison with the greedy algorithm GA-Greedy proposed in [3]. The improved GA is proposed include: GENEsYs (Genetic Search) [7], LibGA [9], and GGA (Group Genetic Algorithm) [10]. In [5], Sanz et al. introduced a hybrid heuristic consisting of SA (Simulated Annealing) and a Greedy algorithm for solving the OLCP problem is called by SA-Greedy algorithm. An improvement of SA-Greedy is LB-Greedy algorithm [11], the lower bound comes from the solution obtained by assigning each BTS $l_{j}$ to the nearest BSC $r_{i}$. A hybrid neural-GA in which a Hopfield neural network [12] manages the problems constraints and a GA searches for high quality solutions with the minimum possible cost called by Hybrid I, Hybrid II proposed in [5, 13]. In the latest works on the OCLP, we proposed GA-BSC [14], Particle Swarm Optimization (PSO-BSC) [15] and Ant Colony Optimization (ACO-BSC1) [16] algorithms.

4 Our Proposed

In this section, we propose a new ACO algorithm combined Local search to improve the speed and quality of solution. The ACO algorithm is originated from ant behavior in the food searching. When an ant travels through paths, from nest food location, it drops pheromone. According to the pheromone concentration the other ants choose appropriate path. The paths with the greatest pheromone concentration are the shortest ways to the food [17].

Ant Encoding: We consider that configurations are sets of M nodes which will be evaluated as BSCs for the network. The encoding of the ant k configuration is by means of binary string of length N, say $k = \left\{ {x_{1} ,x_{2} , \ldots x_{N} } \right\}$ where $x_{i} = 1$ in the binary string means that the corresponding node has been selected to be a controller, whereas a 0 in the binary string means that the corresponding node is not a BSC, but serve as BTS. We must select N nodes to be the controllers of the network. We use fully random initialization in order to initialize the ant population. After that, the ant k will have p 1 s, we use Ant_Repair function to ensure that all binary strings of ants have exactly M 1 s.

The pheromone matrix is generated with matrix elements that represent a location for ant movement, and in the same time it is possible receiver location. Each ant $k$ has exactly $M$ 1 s representing $M$ BSCs is associated to one matrix. We use real encoding to express an element of matrix $A_{M \times N}$ (where $N$, $M$ are the number of BTSs, and BSCs). We construct a transport network $G = \left( {I,J,E} \right)$ where $I = \left\{ {1,2, \ldots ,M} \right\}$ is the set of BSCs, $J = \left\{ {1,2, \ldots ,N - M} \right\}$ is the set of BTSs and $E$ is the set of edge connections between BSC $r_{i}$ and the BTS $l_{j}$. We adding two vertices $S$ (Source) and $D$ (Destination) is shown in Fig. 2.

Fig. 2

The transport network $G = \left( {I,J,E} \right)$

Construct Ant Solutions: Each ant can move to any location according to the transition probability defined by:

$$ p_{ij}^{k} = \frac{{\left[ {\tau_{ij} } \right]^{\alpha } \left[ {\eta_{ij} } \right]^{\beta } }}{{\sum\limits_{{l \in N_{i}^{k} }} \left[ {\tau_{ij} } \right]^{\alpha } \left[ {\eta_{ij} } \right]^{\beta } }} $$

(4)

in which, $\tau_{ij}$ is the pheromone content of the path from BSC $r_{i}$ to BTS $l_{j}$, $N_{i}^{k}$ is the neighborhood includes only locations that have not been visited by ant k when it is at BSC $r_{i}$, $\eta_{ij}$ is the desirability of BTS $l_{j}$, and it depends of optimization goal so it can be our cost function. The influence of the pheromone concentration to the probability value is presented by the constant α, while constant β do the same for the desirability. These constants are determined empirically and our values are $\alpha = 1$, $\beta = 10$. The ants deposit pheromone on the locations they visited according to the relation.

$$ \tau_{j}^{new} = \tau_{j}^{current} +\Delta \tau_{j}^{k} \quad or\quad \tau_{ij} = \left( {1 - \rho } \right)\tau_{ij} + \rho\Delta \tau_{ij} $$

(5)

where $\Delta \tau_{j}^{k} = \frac{1}{{\sqrt {(r_{i1} - l_{j1} )^{2} + (r_{i2} - l_{j2} )^{2} } }}$ is the amount of pheromone that ant k exudes to the BTS $l_{j}$ when it is going from BSC $r_{i}$ to BTS $l_{j}$. The cost function for the ant k is the total distance between BSCs to BTSs is given by (1). The stop condition we used in this paper is defined as the maximum number of interaction $N_{\hbox{max} }$. The pseudo-code of ACO-BSC1 algorithm to solving OCLP as follows:

ACO-BSC1 algorithm combined with local search is called by ACO-BSC2. The local search algorithm described as follows:

5 Experiments and Results

In our experiments, we have already defined parameters for our algorithms: ant population size $K = 100$, Maximum number of interaction $N_{Max} = 500$, parameter $\alpha = 1,\,\beta = 10$. In order to test the performance of our algorithm, we tackle a set of TA and OCLP instances of different difficulties in 3 case studies. We present the results we have obtained followed by an analysis.

Case study 1: We experiment on 13 test cases in [3]. The coordinates of terminals and concentrators have been randomly obtained in a 100 grid, whereas the weights associated with each terminal were randomly generated $w_{j} \in \left[ {1,6} \right],\forall j = 1 \ldots N$. The capacities of each concentrator assigned fixed $p_{i} = 12,\forall i = 1 \ldots M$. Table 1 shows the comparison of the best objective function of ACO-BSC1, ACO-BSC2, Greedy, GENEsYs, LibGA, GGA algorithms. The results listed under the Greedy algorithm are the best solutions yielded by the implementation after 100 executions in each case. We force Greedy algorithm to stop after 10,000 iterations in order to make a comparison with the GENEsYs, LibGA, GGA algorithms which also iterate for 10,000 generations. We use the same population size is 500 and the same crossover rate is 0.6 in the three genetic algorithms. The experiment results show that our approach are useful to reach the feasible regions very fast more than the three genetic algorithms. The GENEsYs, LibGA, GGA algorithms may have to wander for a large of generations in the search space before the feasible regions can be identified. The Greedy algorithm is the fast algorithm, but it does not always produce near optimal solutions, and the GENEsYs does not perform as well as the LibGA, GGA algorithms in all cases. While, our proposed algorithms run very efficiently and yields feasible solutions consistently based on the heuristic information.

Table 1 Performance evaluation of the best solution of algorithms in Case study 1

Case study 2: Table 2 summarize the results of executing the Hybrid I, Hybrid II, ACO-BSC1 and ACO-BSC2 algorithms in the best and average cases on 15 test cases after 100 executions in each case. The 15 TA test cases of different sizes, the difficulty increases with the problem size in [5]. The coordinates of terminals and concentrators have been randomly obtained in a 100 grid, whereas the weights associated with each terminal were randomly generated. The capacities of each concentrator vary from one problem to another, being in a range. Experimental results show that the proposed algorithms are found to be optimal solution in the best case similar to the Hybrid II algorithm. However, the performance of ACO-BSC1, ACO-BSC2 algorithms equally or better than the Hybrid I and Hybrid II algorithms in all cases. The discovery of the ACO-BSC2 algorithm are better demonstrat-ed in the average objective function.

Table 2 Performance evaluation of the solutions of algorithms in Case study 2

Case study 3: We experiment on 10 OCLP instances of different sizes, the difficulty increases with the problem size. The coordinates of terminals and concentrators have been randomly obtained in Table 3, whereas the weights associated with each terminal were randomly generated $w_{j} \in \left[ {1,30} \right],\forall j = 1 \ldots N$. The capacities of each concentrator vary from one problem to another, being in a range $p_{i} \in \left[ {50,150} \right],\forall i = 1 \ldots M$. We compare the results obtained by the objective function of the SA, SA-Greedy, LB-Greedy, GA-Greedy, GA-BSC, PSO-BSC, ACO-BSC1 and ACO-BSC2 algorithms in the best and average cases. All experiment are independent of all others, the results listed in Table 4 is the best solutions and average solutions after 100 executions in each case. The experimental results show that the objective function of our algorithms has achieved a much better performance than other algorithms. In the small grid size and small number of nodes such as problem #29, #30 and #31, all algorithms has approximate results both the best solutions and the average solutions. However, when the problem size is large, the experimental results are considerable different such as problem #34, #35, #36, #37 and #38. In some cases, all algorithms choose the same set of nodes to be BSCs, but the objective function results of the ACO-BSC2 algorithm are much better.

Table 3 Main features of OCLP problems tackled

Table 4 Comparison of the results obtained by the difference algorithms considered

Table 5 shows the computational time of the seven algorithms. The computation time of the GA-BSC, PSO-BSC is smaller than the SA, SA-Greedy and LB-Greedy algorithm, however it is larger than the ACO-BSC1 and ACO-BSC2 algorithms compared. The ACO-BSC2 algorithm is able to obtain much better solutions than the ACO-BSC1 algorithm, which is a reasonable computation time. The ACO-BSC2 is the fastest algorithm, as expected in almost cases.

Table 5 Computation time (in seconds) of compared difference algorithms

6 Conclusion and Future Works

In this paper, we have presented the new ACO scheme for the optimal location of controllers in wireless networks. The proposed algorithms overcomes the disadvantages of previous approaches based on Greedy heuristics are no longer valid, and blind algorithms are necessary for achieving high quality solutions to the problem. Our algorithms may give feasible solutions to this problem based on the global search for high quality feasible solutions. The experimental results show that our proposed algorithms have achieved a much better performance than previous heuristic algorithms. Optimizing location of controllers in wireless networks with profit, coverage area and throughput maximization is our next research goal.