A Differential Evolution Algorithm for Reporting Cell Problem in Mobile Computing

A Differential Evolution Algorithm for Reporting Cell Problem in Mobile Computing

Brijesh Patel

Computer Engineering Department

G.H. Patel College of Engineering and Technology

V.V. Nagar, India

Priyang Bhatt

Computer Engineering Department

1. Patel College of Engineering and Technology

   V.V. Nagar, India

   Abstract in this paper we present an approach to solve the Location management problem based on the reporting cells strategy. In the location management problem the objective is to find the optimum cost for the different configuration network. We used the differential evolution algorithm to find the best network configuration, and to improve the performance for the location management. The proposed approach is applied to the different reporting cell network configuration and result is the best configuration of mobile networks.

   Keywords-mobile computing;reporting cell; location management; differential evolution algorithm

   1. INTRODUCTION

      In mobile networks its challenging task to track the current location of the people in the area of location management and also for the incoming calls arrives for the user then routing to the appropriate mobile terminal.

      In wireless mobile computing, to track the current location of the users its demanding problem in the area of location management, and for steering incoming calls to appropriate mobile terminals, the system have to keep track of the location of each mobile terminals.

      Mobility tracking provide limited resources for the wireless network, Bandwidth used for registration and paging between the mobile terminal and base stations [5]. Moreover power is also consume from the mobile devices. The signal is frequently coming so the quality of service is also degraded. When call arrives at that time search operations is performed in the network, for these operations expenditure of limited wireless resources. The goal is to balance the registration (mobile location update) and search (paging) operations, so we can minimizes the cost of the mobile terminal location tracking [11].

      In location management two necessary strategies are the location update strategy and the location inquiry strategy, In location update strategy, location update is performed when mobile is moving from old cell to new cell, so resources used by location update is very high, However search operation is not require for incoming calls. While in location inquiry strategy search operation is performed to find particular user, here location update is not performed. For searching user more tasks require but no resource would be allocated. By using one strategy cost is maximum while by using other cost

      is minimum so most cellular system used combines both of the strategies.

      The common location management strategies used by existing system is location area (LA) scheme. In this scheme network is partitioned in to different regions or Location area (LA), each region having more than one cell mobile. The location update is being performed if user moves from one location area to another area, location update is not performed when movement of the user within the location area. When call arrives for the particular user, search is confided within the in the location area. For example, in figure. 1 if call arrives for the user X then search operation is performed with in the 16 cell of the particular LA. [7].

      Another available scheme for the location management is the reporting cell, In the this scheme some of the cell are working as reporting cell and another are non-reporting cell, The location update is being performed when user move from one reporting cell to another, when mobile user moving within the non-reporting cell the location update is not performed. When call arrives search is confined to the reporting cell the user has last reported and the neighboring bounded nonreporting cells. For example, in figure. 2 if call arrives for user X, then the search is confined to the reporting cell the user has last reported and the nonreporting cell marked P. In reporting cell scheme to find out optimal set of reporting cells so cost of the location management is minimized, is an NP- Complete problem [6].

      This paper proposed an approach based on the differential evolution algorithm for solve the reporting cell network configuration in wireless network.

      The paper organized as follows. In the next section we have explained location management of the location area and reporting cell strategies. For the reporting cell problem we are discussed about the location management cost. In section III, the Differential algorithm is described, Section IV describes the related work for the differential evolution algorithm, section V we includes the methodology of evaluation and metrics. In Section VI, we are discussed about the experiment results and analysis. Finally section VII includes the conclusion of the work.

   2. LOCATION MANAGEMENT COSTS

      Today Wireless mobile network has cellular network topology; the cellular network is represented by hexagon cell. Each cell having maximum six neighboring cells and each cell having unique number.

      Fig. 1 Region represents location area (LA) (Four LA, each Having 16 cells) [5]

      In this paper we are discussed about the reporting cell scheme was proposed by Bar-Noy and Kessler [4], according to the reporting cell some of the cells are working as a reporting cell and others are the non reporting cells [6],[11].

      For example in fig. 3(a) Reporting cells represented with value 1 in grey color and nonreporting with value 0 in white color. The mobile user only perform location update when they are change their location and move to one reporting cell. If call arrives for the mobile user then search is restrict to his last reporting cell known and their respective neighbors which are non-reporting cells. In the fig 3(a) 2, 3, 5, 6, 8, 10, 14, 15 are reporting cells and other are non-reporting cells [8]; here requirement is that we have to calculate the vicinity factor for each cell, which represent maximum number of cell that the user have to search when incoming call occurs [11].

      The vicinity value of the reporting cell means number of non-reporting cells that are reachable from this reporting cell, without crossing other reporting cells and adding the reporting cell itself. For example consider the vicinity factor for cell 6 in fig. 3(a), we must count the number of neighbors that are non- reporting cell (cells 0, 1, 4, 7 and 11) and also reporting cell itself, which makes total of six neighbors, This number becomes vicinity factor for this reporting cell. If we are calculating the vicinity factor for non-reporting cell at that time we have to consider the maximum vicinity value among the reporting cells from where this can be reached. This means non-reporting cell belongs to neighboring more than one reporting cell, so here we have to calculate the vicinity value for all the reporting cell and then the maximum number is set as vicinity value for the respective reporting cell, For example in fig. 3(a), if we are taking cell number 1 for find out vicinity value then we have to observe the neighboring reporting cells. Reporting cell numbers 2, 5, 6 and 8 are neighbors of the cell 1, so first we have to calculate the vicinity values for all the neighbors and after which is the maximum number is consider as a vicinity value for the non-reporting cell number 1.The vicinity value of the cells 2, 5, 6 and 8 is respectively 4, 7, 6 and 7, so the maximum value is 7 that represent the vicinity value of the cell number 1 is 7 [11].

      <>If we consider reporting cell of fig. 3(a) and calculate the vicinity value of the each cell then result will be fig.3 (b).

      Fig. 2 Network with reporting cell and non-reporting cell [5]

      In mobile network, the location management cost is divided in two operations: updating cost and paging cost are caused by location update and location inquiry respectively. The total sot of a location management is given by

      Total cost = C * NLU + NP (1)

      Where NLU and NP represents the total number location update operation and total number of location inquiry operation respectively. Whereas C denote the cost ratio of location update and location inquiry, the cost of the location update is 10 times higher than the location inquiry so in this paper, we use c = 10 [8], [11].

      To calculate the value of NLU, each cell in the network is allocated mobile weight Wmi denoting the total number of mobile user enter in to cell I over time T. Hence the total number location update of the reporting cell equals total number users that entered in to the cell, so total of location update is

      (2)

      Where R denotes subset of cells defined as reporting cells.

      To calculate the cost location inquiry in the network, each cell i in the network assigned a call arrival weight Wci denoting the total number of the call arrived in cell i during the period of time T. To find the current location of the user X, the mobile network have to search X in the vicinity of cell I, so the cost of the location inquiry operation of a reporting cell i can be calculated by Wci * V (j) [11].

      However, to calculate the location inquiry cost of the non- reporting cell j, so we have to consider cost of each user in cell

      1. If a user X is in non-reporting cell j at present then we have consider the its neighboring reporting cell and also calculate the vicinity value of all the neighboring reporting cell, From reporting cell, cell having maximum vicinity value which is consider as vicinity value of the current non-reporting cell [11].

         (3)

         Where left portion of addition is related to the total number of reporting cell and right portion of the addition is related to the total number reporting cell, in each portion the corresponding vicinity values are multiplied

         individuals. By interchanging some of the element between mutation vector Vi,G+1 and target vector xi,G, the trial vector Tji,G +1 = (T1i,G+1, T2i,G+1, , TNi,G+1) is formed where Tji,G+1 = Vji,G+1, if random number less than the crossover otherwise Tji,G+1 = Xji,G., where j = 1, 2, , D, D represent the genes of an individual [11].

         1. (b)

      Fig. 3 (a) reporting cells planning (b) vicinity values [10]

      According to equation (1), (2) and (3) we get (4) to calculate the location management cost of the mobile network with reporting cells scheme [11].

      (4)

   3. DIFFERENTIAL EVOLUTION ALGORITHM The differential algorithm is population based algorithm,

      created by Storn and Price [6]. This is used for the purpose of

      optimization. Currently several variants of DE have been proposed, the variant used in this paper is DE/rand/1/bin which used in many application successfully.

      1. Initial Population

         Like the other evolutionary algorithm, Differential evolution algorithm works with the population of individuals (NI) and this number never change during the optimization process. The initial population is randomly generated and the population will be improved by the algorithm iteratively, and by using the mutation, crossover and selection operation.[6] Here we have to convert the individual to the problem solution, so if r =1 then cell is reporting cell and other cell r is non-reporting cell.

      2. Mutation operator

         The mutation operator F is scaling factor which is used to controls the amplitude of the differential variation of these random individuals used in the calculation. By using the mutation operator differential evolution generates the mutant individual (Vi,G+1), taking addition weighted difference of the two population individuals, to the third individual using following equation [1].

         Vi,G+1 = xr1,G + F * (xr2,G – xr3,G ) , i =1,2,…, NP

         (5)

         Where r1, r2 and r3 are random indexes selected from 1, 2, , NP and r1, r2, r3 and i are not same. The value of F must be greater than zero and will control the magnitude of the differential variations of the two individual (xr2,G – xr3,G ) [11].

      3. Crossover operator

         The value of the crossover operator is between zero and one, which is used to increase the diversity of the mutant

      4. Selection operator

      Selection operator is used to compare the trial individual which is produce by the crossover with the target individual and finally one individual determine as part of next generation. If trial individual has a smaller value than the target individual the value of the trial individual is copied to next generation otherwise target individual is used as next generation [11].

   4. RELATED WORK

      In differential evolution algorithm storn and price [6] has suggested to start Algorithm by defining and evaluating the initial population through calculating the fitness value for each individual, in next step until the termination criterion is not reached, the necessary individual are picked and new one is produced according to the differential evolution scheme and rules. The new individual is evaluated and compare with the older one, if it is lower cost function value then target vector function value, selected as next generation otherwise target vector function value keep as it is [11].

      According to another author suggested first we are taking number of individual, from those individual we are find out the best cost of the specific individual. We are picking new cost and evaluate them, and it is compare with the older cost, if new cost smaller than old cost then we are keeping old cost otherwise new cost consider as best cost, then after new cost is picked up according to the algorithm.

   5. METHODOLOGY OF EVALUATION & METRICS

      1. Networks used

         For the reporting cells strategy, other authors present the test networks used, in their studies, but there are using different algorithm to optimize the cost of the location management so it is not possible to compare our approach with them. However, in [5] it is presented a set of 3 networks, defined by size, that have been generated, based on realistic data and patterns, and are available in [5] as benchmark. In this work we used these 3 networks with the objective of compare final results. In Table 1, table 2 and table 3 it is shown, as an example, the test network that represents a 4×4, 6 x 6 and 8 x 8 cells configuration. The first column indicates the cell identification, the second column corresponds call arrival weight for the number of incoming calls NP and the third represents the mobility weight for the location update NLU.

      2. Fitness function

         In the study of the reporting cells problem the fitness function is used for measuring the total location management cost of each potential solution, which is defined according to Eq. This means that for each potential solution generated, it is calculated the fitness value, which corresponds to the network

         configuration by means of reporting cells and non-reporting cells.

      3. Parameters definition

      The initial definition of parameters is an important step because it represents the basis for the algorithm evolution. First it is defined the initial population of candidate solutions that corresponds to the individuals.

      Each individual is compound by N genes, where the N value is the number of cells in the network and each gene represents the information about the cell type, which can be a reporting cell or a non-reporting cell.

      To define the initial population we have set, with a probability of 50%, the type of each cell as RC or nRC. Initially itis also necessary to set the DE algorithm parameters and that has been done with a number of individuals NI equal to 100, the crossover value Cr defined as 0.1 and the mutation factor F set to 0.5. For the DE scheme, the DE/rand/1/bin has been selected. The number of generations, that is, the terminal condition, is set to 200. Throughout the different experiments, the parameters values have been adjusted with the specific objective of obtaining the best results [11].

      Table 1 Data set for 4×4 Network [5]

      Cell	Wci	Wmi	Cell	Wci	Wmi
      0	517	518	8	251	445
      1	573	774	9	224	2149
      2	155	153	10	841	1658
      3	307	1696	11	600	952
      4	642	1617	12	25	307
      5	951	472	13	540	385
      6	526	650	14	695	1346
      7	509	269	15	225	572

      Table 2 Data set for 6×6 Network [5]

      Table 3 Data set for 8×8 Network [5]

      Cell	Wci	Wmi	Cell	Wci	Wmi	Cell	Wci	Wmi
      0	968	533	21	414	1950	42	363	756
      1	745	907	22	104	101	43	820	436
      2	827	515	23	881	539	44	362	612
      3	705	1965	24	694	655	45	356	822
      4	902	1336	25	793	131	46	637	1912
      5	498	1318	26	955	1227	47	626	1402
      6	807	1292	27	126	450	48	345	524
      7	62	1789	28	268	470	49	135	1400
      8	331	541	29	96	1081	50	175	393
      9	212	1071	30	285	1714	51	596	1272
      10	787	1759	31	368	308	52	677	1197
      11	664	1416	32	952	121	53	283	462
      12	938	1413	33	367	1410	54	139	548
      13	719	1224	34	132	1011	55	307	500
      14	794	484	35	439	1298	56	272	113
      15	543	1892	36	134	1634	57	931	47
      16	184	626	37	153	1750	58	38	1676
      17	787	104	38	612	1948	59	896	1017
      18	319	1408	39	216	662	60	164	1307
      19	25	1256	40	878	700	61	78	499
      20	934	1637	41	957	765	62	303	1451
      						63	578	1606

      Cell	Wci	Wmi	Cell	Wci	Wmi	Cell	Wci	Wmi
      0	714	1039	12	238	507	24	328	16
      1	120	1476	13	964	603	25	255	332
      2	414	262	13	789	1479	26	393	1203
      3	639	442	15	457	756	27	370	1342
      4	419	1052	16	708	695	28	721	814
      5	332	1902	17	825	356	29	769	747
      6	494	444	18	462	1945	30	17	146
      7	810	1103	19	682	1368	31	265	904
      8	546	1829	20	241	1850	32	958	359
      9	221	296	21	700	1131	33	191	1729
      10	856	793	22	23	236	34	551	190
      11	652	317	23	827	1622	35	467	1907

      To initialize population is the important procedure of the evolution type of the algorithm. For getting the optimum search value initial population taken as higher quality and better diversity, to minimize the cost of the location management we used pseudo code of the differential evolution algorithm as follows.

      Step 1 Initialize the population

      Step 2 Evaluate the initial population

      Step 3 While (termination condition not satisfied){ Step 4 Randomly select individual xr1

      Step 5 Randomly select individual xr2 and xr1 xr2

      Step 6 Randomly select individual xr3 and xr3 xr1 and xr3 and xr3 xr2

      Step 7 Generate trial individual: xtrial = xr1 + F (xr2 xr3)

      Step 8 Use Cr to defined amount of genes changed in trial individual

      Step 9 Evaluate the trial individual

      Step 10 Deterministic selection Step 11} [6]

   6. EXPERIMENT RESULTS AND ANALYSIS The algorithm was written in c++ language and run on a

PC having core 2 duo processor, 1GB RAM and windows operating system. To evaluate the algorithm simulation experiments were conducted. The 4 x 4, 6 x 6 and 8×8 network configurations are used.

We have taken the three distinct experiments applied to the each test network with objective of the best network configuration of the reporting cell problem. For each of the experiments and for the all combination of parameters, independent run have been performed to assure the statistical relevance. In each experiment final result of the optimum fitness value obtained are presented and explained the decision taken. After that we have analyze the result obtained and find out the best configuration network.

1. Experiment 1 determining NI

   The number of individual of the initial population must be the first experiment because it is the basis of algorithm implementation. In order to find out the result we have fixed the value of crossover operation is 0.1, the mutation operation is 0.5 and stop criterion as 200 generations.

   From this experiments we have conclude that increase the value of NI the positive evolution of the result obtained which is given in table 4. Results till to the NI value 100 because after that we have observing worse result. So here we have taken stop criterion as 100 and for each different size of the network we have got the optimum cost in 100 NI so the NI = 100 would be elected value for the second experiment.

   Test Network (N. Dim)	NI fitness evaluation
   	10	20	30	40	50	75	100
   4 x 4	497090	845300	507054	434260	603763	560700	368814
   6 x 6	2985181	2534500	2048761	2078466	2483736	2863042	2038642
   8 x 8	7564272	7234570	7595865	6420456	6068663	7085340	4066770

   Table 4 Determining the best NI.

2. Experiment 2 determining Cr

   The second experiment has the objective of selecting the Cr value that obtains the best result. To proceed with this experiment, fixed the value of NI as 100 and other parameter mutation value 0.5 and stop criterion 200 generations.

   In this experiment we are using different value of Cr: 0.1, 0.15, 0.20 0.25. 0.50, 0.75 and 0.90. This is given in table

   5. From the result we can conclude that best value obtained with Cr value 0.1 for the each of the different size of the network, the results shows that the value of Cr as 0.1 is the elected value for the experiment 3.

   Table 5 Determining the best Cr.

   Test Network (N. Dim)			Cr	Fitness evalu	ation
   	0.1	0.15	0.20	0.25	0.50	0.75	0.90
   4 x 4	368114	530211	582372	543761	632529	625096	526704
   6 x 6	2038642	2338107	2721437	2323422	2132023	2531166	3080827
   8 x 8	4066770	4544560	4823390	5237589	4324568	5348123	4675260

3. Experiment 3: determining F

To find out the best value of the mutation F third experiment is being carried out. To perform the experiments it was fixed the value of NI as 100, the value of Cr as 0.1 and 200 as stop criterion for the generations. In this experiment we have used different value of F: 0.1, 0.25, 0.50, 0.75 and

0.90. The result of the above different value of the F which is given in table 6. From the result we can conclude that the value 0.90 is best value of the different network configuration

Table 6 Determining the best F.

Analyzing the experimental results we can conclude that by using the differential evolution algorithm we can get the better optimum cost of the location management. From the table 4, 5 and 6 we consider that if we are taking the Number of Individual (NI) as 100, crossover operation value 0.1, scaling factor F as 0.90 and the stop criterion for the population generation as 200 so we can get the best result.

In future work we are taking more number of individual for the experiment and also for the different configuration network. Moreover we will compare our result with the other authors so we can get the better optimum location management cost for reporting cell problem in mobile computing.

CONCLUSION

This paper present an approach based on the differential evolution algorithm applied to the location management problem with the objective to minimizing the involved costs. The approach specified for the reporting cells strategies of location management problem.

If we refer to the approach developed applied to the reporting cells problem we can get the best configuration of differential evolution including the different parameters. We have shown that the best result is obtained if we are taking the crossover value Cr 0.1, scaling factor F 0.90, number of individual NI 100 and the termination criterion of the generation is 200.

REFERENCES

1. Upkar, V., Location management for wireless networks: issues and directions. Int. J. Mob. Commun, 2003, 1(1-2): pp. 91-118.

2. Wen-Hong Wanga,Feng-Rui Wang and Quan-Ke Pan,Feng-chao Zuo Improved diffrential algorithm for Loacation management in Mobile Computing IEEE 2009.

3. Wenchao, M. and F. Yuguang, Two-Level Pointer Forwarding Strategy for Loation Management in PCS Networks, IEEE Transactions on Mobile Computing, 2002. 1(1): pp. 32-45.

4. Bar-Noy, A. and I. Kessler, Tracking mobile users in wireless communications networks, Information Theory, IEEE Transactions on, 1993. 39(6): pp. 1877-1886.

5. Subrata, R. and A.Y. Zomaya, A comparison of three artificial life techniques for reporting cell planning in mobile computing, IEEE Transactions on Parallel and Distributed Systems, 2003. 14(2): pp. 142- 153.

6. R. Storn, K. Price, Differential Evolution a simple and efficient heuristics for global optimization over continuous spaces, Journal of global optimization, pp. 341-359, Nov 1997.

7. Hac, A. and X. Zhou, Locating strategies for personal communication networks, a novel tracking strategy, IEEE Journal on Selected Areas in Communications, 1997. 15(8): pp. 1425-1436.

8. Gondim, P.R.L., Genetic algorithms and the location area partitioning problem in cellular networks, Vehicular Technology conference, 1996. 'Mobile Technology for the Human Race' IEEE 46th, Atlanta, GA, USA, vol. 3, pp.1835-1838, May 1996.

9. Shahryar, R.T. Hamid, and M.A.S. Magdy, A novel population initilization method for accelerating evolutionary algorithms, Compter Math. Appl., 2007. 53(10): pp. 1605-1614.

10. Sonia M. Almeida-Luz, Miguel A. Vega-Rodriguez, Juan A. Gomez- Pulido and Juan M. Sanchez-Perez, Differential evolution for solving the mobile location management, Applied Soft Computing 11 (2011), pp 410-427

11. Brijesh Patel A Novel Approach using differential evolution algorithm for Location Management in Mobile Computing International journal of emerging technology and application in engineering and technology (IJ-ETA-ETS), 2011, p.p 342-346