Abstract

In this study, a hybridized heuristics approach based on Iterative Local search and Simulated Annealing is proposed to solve the assignment problem of Cellular Mobile Network. In Cellular Mobile Networks, assigning of cells to switch is known as assignment problem. The conventional integer programming method could be used for solving this problem but then, when the number of cells exceeds 35, the total computational data surpass the memory available, computational time grow too larger and it becomes unfeasible to obtain the optimal solution. Thus, this assignment problem is a complex integer programming problem which is proved to be NP hard problem. Particularly, in this study 2-opt Local search and 3-opt Local search methods are embedded to improve the CPU performance of the proposed hybridized algorithm. The objective function is to minimize the link cost between cells and switches upon their assignment alongwiththe constraint that number of cells assigned to each switch. Empirical results show that the proposed heuristic produces results proximity to optimal solution as expected.

---

INTRODUCTION

Drastic increase in usage of mobile phones and raising demands for much more new innovations in mobile technology attracts recent research attention towards Cellular Mobile Networks. Cellular Mobile Network, honeycomb like look, consists of geographical topology of hexagonal structures called Cells. The Cellular Mobile Network consists of three major levels namely user level, access level and network level as shown in Fig. 1. The cells are interconnected in a hierarchical manner. Each cell consists of antenna named Base Transmission Station (BTS). In cellular mobile network, few cells act as Switches. Communication between cells takes place through a switch via BTS of individual cells. To hold communication, any registered cellular mobile device transmits through BTS in turn connected through switches. Conventionally, cells and switches are stationary and their locations are already known. As described by St-Hilaire et al. (2006), Cellular Mobile Networks constitutes four categories of problems: the cell planning subproblem, the access network planning subproblem, the core network planning subproblem, the assignment problem of cells to switches. The assignment of cells to switches is known as assignment problem of Cellular Mobile Network problem.

Fig. 1:	Basic Cellular Mobile Network

The conventional integer programming method couldbe used for solving this problem but then, when the number of cells exceeds 35, the total computational data surpass the memory available, computational time grow too larger and it becomes unfeasible to obtain the optimal solution. Thus, this assignment problem defined above is a complex integer programming problem which has been proved to be NP hard problem as detailed by Merchant and Sengupta (1995).

In assignment problem, the objective function is minimization of link cost between a cell and a switch, which is prelude by two ingredients.

First, whether the cells are single homed or dual homed. In single homed network of cells, each communicating cell is connected to only one switch whereas in dual homed network the each cell is connected to two different switches.

Second, whether simple or complex call handoff. During the process of mobile communication, when user travels from one cell to another cell, then updation of user information and signal handoff takes place at each cell for user’s sojourn. This is known as call handoff. Call Handoff can be of simple or complex.

When call handoff takes place between two cells sharing same switch, then it becomes simple handoff renting minimal call handoff charges. If the call handoff takes place between two cells connected to different switches then it is called complex handoff.

In this study, single homed signal handoff assignment problem is addressed. This study presents a hybridized heuristic Iterative Local Search Algorithm with Simulated Annealing method. To achieve optimization on objective function, 2 and 3-opt methods for Local Search are embedded to minimizing link cost along with constraint based on number of available port on switches.

Related works: In the literature, Cellular Mobile Network has been studied intensively. Quintero and Pierre (2003) performed comparative study on various algorithms for assignment problem.

Bhattacharjee et al. (1999) carried out their comparative study for personal communication social network. Khuri and Chiu (1997) attempted to use various Local Search Heuristic techniques in searching for optimal solution and showed promising results in implementing these local search procedure. Shyu et al. (2004) proposed ant colony optimization technique towards solving assignment problem.

Various Genetic algorithm and Evolutionary Algorithms techniques for assignment problems were discussed in study (Santos-Correa et al., 2004; Quintero and Pierre, 2003, 2008; Salcedo-Sanz et al., 2003). Salcedo-Sanz and Yao (2004) proposed hybridizing heuristic algorithms for the terminal assignment problem. Similar hybridizing was proposed by Yao et al. (2005) and Abu-Amara et al. (2006). Another popular heuristic technique Simulated Annealing algorithm was embarked by Menon and Gupta (2004) upon the assignment of cells to switches and results showed proximity to the optimal solution and confirmed efficiency of simulated annealing method. Finally, Tabu Search based heuristic local search approach was applied for cells to switch assignment (Pierre and Houeto, 2002).

Similarly various researches has been carried for cell to switch assignment problem of Cellular Mobile Network (Salcedo-Sanz et al., 2008; Quintero and Pierre, 2002; Pesant et al., 2005; Saha et al., 2000; Pierre and Houeto, 2002).

Problem formulation: In this study, single homed signal handoff assignment problem of Cellular Mobile Network is addressed. Consider Cellular Mobile Network of N cells and M switches.

Essentially, the number of switches is <number of cells in a Cellular Mobile Network, thus M<<N. Let λ_i represents call servicing capacity of cell i/unit time. Let P_k represents maximum number of ports available with the switch k. Let C be the link cost matrix of size N x M. Then, non negative C_ik represents the cable cost of connection between cells I and switch k. Let X be a matrix of size N x M:

where:

X_ik is defined as:

The value of X_ik = 1 if cell i and switch k are connected, otherwise zero. The single homed cell indicates that each cell is connected to only one single switch that is cell i is linked to only one switch at any time and is given in Eq. (1):

(1)

The assignment problem consists of two sub problems. First sub problem is assigning each of N cells to available M switches with constraint that number of cells assigned to each switch should not exceed number of ports currently available at that switch. As given in Eq. 2, the number of connectivity requesting through BTS of each cells for a particular switch, must be less than or equal to the maximum number of ports P_k currently available on switch k.

(2)

Second sub problem is calculation of objective cost function for this assignment problem which further constitutes two component. First, cost estimation of cable linked between cell and switch as shown in Eq. 3:

(3)

Second, estimation of call handoff cost between any two cells. For this consider,

(4)

From Eq. (4), Z_ijk will be equal to 1 if cell i and cell j are connected to same switch. Otherwise Z_ijk becomes zero. Also,

(5)

Equation (5) infers that when cell i and cell j are connected to same switch Y_ij is equal to 1. Otherwise, Y_ij becomes Zero. Final handoff cost is given in Eq. (6):

(6)

All together, the general objective cost function is defined as min (f) = f_cable + f_handoff,

(7)

As stated in (Quintero and Pierre, 2003) the before assignment problem can be solved using Integer Programming method. Although, Integer Programming method guarantees optimal solution, the limitation on it is number of cells must be <35, which is not consistent in today’s real mobile network. Further, the computation time becomes too large and unfeasible to obtain optimal solution, as the total computational data set exceeds the memory available for number of cells >35. To overcome in this study a hybridized heuristic method is proposed.

Iterative local search algorithm: Iterative local search is a simple and powerful metaheuristics among all other heuristic algorithms as the algorithm uses efficient local search and avoids gravel into local optimal by using effective perturbation operator. Basically two operators are used in ILS algorithm, namely, local search operator and perturbation operator. Whenever Local Search gets trapped into a local optimal solution, a perturbation operator is applied. A fresh starting point for further local search is obtained. However, the generated starting point must suitably be in proximity of solution within search space. Pseudo code for ILS is shown in Fig. 2. Algorithm begins with applying a local search on general initial solution P and produces new local optimal solution P*.

Local Search improves a solution in the search space. When the local search is stuck, the locally optimal solution P* is mutated by a move in a neighborhood different from the one already used by the local search. Perturbation kicks current local solution P* and generate an intermediate solution P’. The resulting solution of perturbation P’ is the new starting solution for the local search that takes it again to another new local optimum P*’. Using proximate optimality principle if P is close to P* in Perturbation, then the new local optimal solution generated in local search will also be in proximity of the current local optimal solution.

Finally, an acceptance criterion decides which of the two locally optimal solutions, P*’ and P*, obtained from previous step is to be select as a starting point for the next perturbation step. If P*’ win P* in acceptance criterion, then P*’ will replace P* and become current optimal solution, otherwise the search remains at the previous optimal solution P*. The terminating condition for this algorithm is number of iterations. The major impulse in ILS Algorithm lays in carrying out a randomized walk within the search space of the local optima with respect to some local search algorithm.

To overcome increasing complexity of optimality computation in entire search space, a limited number of neighbors are inspected around the local optimal solution, towards searching for the better solution. For this purpose 2-opt ILS algorithm is used. In case of 2-opt Local Search, an initial position is selected at random, begins ILS process from that position by exchanging 2-opt constant length portion resulting in generation of new neighbors. All possible 2-opt exchanges in the local optimal solution are investigated for a better solution than previous. For 3-opt exchange, three random constant length portions are exchanged for generating new neighbours and iterative Local Search is implemented in search of better solution.

Fig. 2:	Pseudo-code for iterative local search

But then, it may happen that Iterative Local Search algorithm omits the chance of searching entire neighborhood thoroughly because some of them do not meet the satisfying condition that is the current solution must be less than the best known solution so far. Probable chances exist that overleaping of certain neighborhood might lead to undesirable non global optimal solution. To overcome this in this study we propose hybridizing Iterative local search algorithm with simulated annealing algorithm.

Simulated annealing: The simulated annealing is a simple and efficient heuristics. It controls slow convergence of local search. The effectual annealing technique avoids unnecessary exchange of assignments between cells and switches.

Thus, best suitable for hybridizing with Iterative Local Search Algorithm. The simulated annealing algorithm performs search for optimal solution on those neighbourhood solutions neglected by Local Search Algorithm. Let the neglected solution be initial solution for simulate annealing. Assign this initial solution as the current best solution S_i. Let the cost of this initial solution be the minimum cost A_i. A Comparatively high temperature value T_k is selected. After perturbation the current solution, a neighborhood solution S_j is obtained.

The feasibility of this neighborhood solution is verified along with the constraints specified in Eq. (2).

If S_j is unfeasible this neighborhood solution is eliminated and then next neighboring solution is search out.

If S_j becomes feasible and constraint is satisfied then S_j is compared with the current best solution S_i. S_j becomes current best solution in case S_j<or = -S_i. This becomes the starting point of the next local search. The iteration is incremented by one.

Fig. 3:	Pseudo-code for Hybrid ILS_SA Heuristic

The effective role of simulated annealing is revealed at this point. Usually in case sole Iterative Local Search Algorithm the condition that S_j>S_i is neglected, which might leads to non global optima and resulting in undesirable local minimum solution.

To overcome the this fallouts, a random number is generated, based on uniform random distribution in the range (0, 1).

If this generated random number is <exp [(S_j-S_i)/T_k], then Sj is accepted as new best solution. The objective cost A_j of the current best solution S_j become Ai. Otherwise retain S_i as the current best solution. The iteration count is then incremented and further lower the temperature to a new value of T_k. This procedure is repeated until the termination condition is met. The pseudo code for the hybridization of ILS with SA is given in Fig. 3.

Experiment: The experiment was conducted on Genuine Intel® CPU T2250 @ 1.73 GHz, 1.00 GB of RAM machine. We ran experiment for Iterated Local Search Algorithm implemented using C++ language. The results of Iterative Local Search were uniformly distributed at the center of cells. Two matrixes namely distance matrix and flow matrix were inputted to the algorithm. The cable cost of link between cells and switches were considered as proportional to the geometric distance between cells and switches.

The binary flow matrix entries indicate value one when there exist link between cell and switch, otherwise zero for non existence of link between cell and switch. The two categories of test instances were generated. First case was based on constant number of switches and varying number of cells. Second case was based on varying number of cells and varying number of switches. For test cases, the number of switches varied between 2-5 and number of cells varied between 15-240. We ran each instance for 100 iterations.

Initial when comparing conventional Iterative Local Search Algorithm with Integer Programming methods, both produced optimal results for number of cells within 30. For both cases of varying number of switches as well as constant number of switches, Integer Programming method and conventional Iterative Local Search Algorithm showed linear increase in the computational time. Beyond 30 cells and switches, the Integer Programming method failed to produces any feasible results as depicted in Table 1.

In Integer programming method, the total computational data set exceeds the memory available in case the numbers of cells were >30. Thus the computation time becomes too large and unfeasible to obtain optimal solution, indicated as asterisk (*) in Table 1.

When comparing conventional Iterative Local Search algorithm with Hybridized ILS-SA algorithm, both produced optimal. For both cases of varying number of switches as well as constant number of switches, conventional Iterative Local and Hybridized IL-SA algorithm showed linear increase in the computational time. Further both heuristic algorithms produced objective cost values in close proximity to the optimal solution. But then, Hybridized ILS-SA algorithm showed comparatively better results than the conventional method based Local search heuristics by decrease in the time during computation of the local search technique as in Table 2.

For various sizes of cellular mobile network and by varying the number of switches, the computational time reduced considerable than conventional ILS search, proving hybridized local search method to be more efficient. Result was achieved due to avoidance of local minimum solution of the Iterative Local Search by using efficient Simulated Annealing Technique. Further the non global minima also avoided by exploring even the non optimal solution technique of simulated annealing.

From Table 3, after executing 2-opt and 3-opt local search Hybrid ILS-SA Algorithm with constant number of switches but varying number of cells in cellular mobile network, Hybridized ILS-SA outperformed comparatively. In practice, even this small improvement would reflect a huge reduction in over cost of the assignment problem in cellular mobile networks.

Table 1:	Comparison of IP with conventional ILS (*indicates unfeasible)

Table 2:	Comparison of conventional ILS with 2-opt and 3-opt method of Hybridized ILS_SA by varying number of switches

Table 3:	Comparison of conventional ILS with 2-opt and 3-opt method of Hybridized ILS-SA with constant number of switches

CONCLUSION

Assigning cells to switch known as assignment problem of Cellular Mobile Networks is a challenging complex integer programming NP-hard problem. In this study using hybridization of Iterative Local Search and Simulated Annealing heuristic algorithms, expected feasible solutions are achieved. For single homed signal handoff assignment problem, this hybridization technique further shows improvement in the computational time.

By the proposed heuristic method, the feasible solution is obtained at the latest compared to the other algorithms. In case of large scale networks, hybridized Iterative Local search results are distinctly efficient and effective. Further the problem can be extended to dual homed assignment problem.

How to cite this article:

Hima M. Bindu, Prakash Kumar and K. Rajalakshmi. Hybridizing Iterative Local Search Algorithm for Assigning Cells to Switch in Cellular Mobile Network.
DOI: https://doi.org/10.36478/ijscomp.2010.7.12
URL: https://www.makhillpublications.co/view-article/1816-9503/ijscomp.2010.7.12