Genetic Algorithm for 3D RFID Reader Network Planning

SHIN-YEU LIN DA JHOU KANG

Department of Electrical Engineering

Chang Gung University

259 Wen-Hwa 1st Road, Kwei-Shan, Tao-Yuan 333

TAIWAN, ROC

shinylin@mail.cgu.edu.tw m0421038@stmail.cgu.edu.tw

Abstract: - In this paper, a genetic algorithm (GA) with a spatial crossover operation and a correction scheme is proposed to solve a 3D RFID reader network planning problem. The proposed algorithm aims to improve the performance of the previously developed micro GA (mGA) in getting a better solution. We have tested the proposed GA on several 3D RFID reader network planning problems with different size. We have also compared the obtained results with the results obtained by mGA. The comparison results show that the proposed GA outperforms the mGA in the quality of the obtained solution.

Key-Words: - RFID, reader network, genetic algorithm, crossover, correction scheme


1 Introduction

The radio frequency identification (RFID) system for large warehouses is indispensible in the era of electronic commerce [1-4]. In previous work, we have developed a micro genetic algorithm (mGA) with a spatial crossover operation and a correction scheme to solve a three-dimensional (3D) RFID reader network planning problem [5]. The advantage of mGA is its computational efficiency. On the other hand, its capability in searching for the best solution may be limited by its small size of population. As a result, to gain the computational efficiency, mGA paid the price of getting a non-perfect solution. However, for a long-term 3D RFID reader network planning problem, computing time is not a stringent requirement. Therefore, to improve the performance of the previously developed mGA, a GA with a spatial crossover operation and a correction scheme is proposed. Typical GA consists of the following operations, selection, crossover and mutation. Typical crossover operations consist of single point crossover and double point crossover operations. Since the problem considered in this paper is a physically three-dimensional problem, a spatial crossover operation may be superior to the traditional crossover operations. To ensure the 100% tag coverage, the complete tag coverage is treated as a hard constraint in the considered 3D RFID reader network planning problem. In this constrained optimization problem, the chromosomes resulted from the crossover and mutation operations of the proposed GA may be infeasible. Therefore, a correction scheme can be used to turn an infeasible chromosome into a feasible one. The objective function of the considered 3D RFID reader network planning problem consists of two terms, the number of placed readers and the reading interference. Therefore, the objective of the 3D RFID reader network planning problem is to place minimum number of readers to ensure the 100% tag coverage and minimize the reading interference.

2 Problem Formulation

The room for storing the objects with tags is assumed to be a rectangular block, and the candidate reader positions are distributed in the room in a equally-spaced manner, such that the union of interrogation zones of all candidate reader positions can cover the entire room. We let denote the index of a solution, denote the total number of tags, denote the total number of tags that are covered by all placed readers, denote the total number of candidate reader positions, denote the total number of tags lying in the overlapping areas of the interrogation zones of all placed readers and denote the total number of placed readers. We let denote the tag coverage ratio, such that . Then, the requirement of 100% tag coverage of a solution can be expressed as an equality constraint, . We let denote the ratio of total number of tags that were not in the overlapping interrogation zones with respect to total number of tags, then . Therefore, the larger the , the smaller the and the reading interference. We let denote the ratio of the number of empty candidate reader positions with respect to total number of candidate reader positions, then . Therefore, the larger the , the smaller the and the associated cost. Combining the above two terms using suitable weighting coefficients, we can define the fitness of a solution as

(1)

where and are the weighting coefficients. Consequently, to minimize the cost of total placed readers and the associated reading interference while satisfying the 100% tag coverage constraint, the considered 3D RFID reader network planning problem can be formulated mathematically as follows.

subject to (2)

3 Proposed Genetic Algorithm (GA)

The difference between the proposed GA with a spatial crossover operation and a correction scheme and the previously developed mGA for solving the 3D RFID reader network planning problem lies in the main operations of the algorithm. For example, in both algorithms, they use the same representation schemes, the same roulette wheel selection scheme, the same spatial crossover operation, the same mutation operation and the same correction scheme, which are already clearly stated in [5]. Therefore, in this section, only the main operations of the proposed GA are presented in the following.

We randomly generate chromosomes to serve as the initial population and apply the correction scheme to each infeasible chromosome. We set the iteration index then evaluate the fitness of each chromosome, using equation (1). Apply the roulette wheel selection scheme to select pairs of parents to perform the spatial crossover operation with crossover probability . After the spatial crossover operations, we apply the correction scheme to the resulted infeasible offspring and update . To each chromosome in , we apply the mutation operation with mutation probability and apply the correction scheme to each mutated chromosome. Update , set and repeat the above process until , where is a preset maximum number of iterations, and the final best-so-far solution is the optimal solution we obtained.

4 Numerical Results and Comparisons

The tested 3D RFID reader network planning problems are set up as follows. A room with candidate reader positions is used as the space for storing objects with tags. The length of each side of the room is units, and the length of a unit is equivalent to a distance of , where denotes the radius of the interrogation zone of a reader, such that if a reader is placed at the center of a unit cube, the eight vertices of which will be on the boundary of the interrogation zone. Three cases of are considered, which are 5, 7 and 9 and corresponding to 125, 343 and 729 candidate reader positions, respectively. Both weighting coefficients and are set to be 1. The parameters used in the GA are set as follows. , , , . All the tests presented in this section are carried out in a personal computer with 3.3 GHz Intel Core I5 and 4 GB RAMs.

For each case of , ten long-term 3D RFID reader network planning problems are prepared, and the tags in each problem are randomly placed. The test results of applying the proposed GA to solve the ten 3D RFID reader network planning problems for each case are presented in Figs. 1-3. The vertical axis represents the average best-so-far fitness, and the horizontal axis represents the number of iterations. We also apply the mGA to the same ten 3D RFID reader network planning problems, and the test results for each case are also presented in Figs. 1-3. From these three figures, we can see that the solution obtained by the proposed GA is much better than the mGA for each case of .

5 Conclusions

In this paper, a GA with a spatial crossover operation and a correction scheme is proposed to solve the long-term 3D RFID reader network planning problem. Comparing with the previously

描述: 描述: 描述: 描述: 1

Fig. 1. Progression of average best-so-far fitness with respect to the number of iterations for proposed GA and the previously developed mGA in N=5 case.

描述: 描述: 描述: 描述: 2

Fig. 2. Progression of average best-so-far fitness with respect to the number of iterations for proposed GA and the previously developed mGA in N=7 case.

描述: 描述: 描述: 描述: 3

Fig. 3. Progression of average best-so-far fitness with respect to the number of iterations for proposed GA and the previously developed mGA in N=9 case

developed computationally efficient mGA, the proposed GA can obtain a better solution as demonstrated by several long-term 3D RFID reader network planning examples.

Acknowledgement:

This research work is supported in part by Chang Gung Memorial Hospital under grant BMRPB 29.

References:

[1] E. Bottani and A. Rizzi, “Economical assessment of the impact of RFID technology and EPC system on the fast-moving consumer goods supply chain,” International Journal of Production Economics, vol. 112, no. 2, pp. 548-569, 2008.

[2] H. Feng and J. Qi, "Radio frequency identification networks planning using new hybrid evolutionary algorithm," ICACT Transaction Advanced Communication Technology, vol. 2, no. 1, pp. 179-188, 2013.

[3] L. Ma, H. Chen, K. Hu and Y. Zhu, "Hierarchical artificial bee colony algorithm for RFID network planning optimization," The Scientific World Journal, vol. 2014, p. 21, 2014.

[4] N. Bacanin, M. Tuba and I. Strumberger, “RFID network planning by ABC algorithm hybridized with heuristic for initial number and locations of readers,” in Proceeding of the 17th UKSIM-AMSS international Conference on Modeling and Simulation, pp. 39-44, 2015.

[5] S.-Y. Lin and H.-F. Tsai, "Micro genetic algorithm with spatial crossover and correction schemes for constrained three-dimensional reader network planning," Expert Systems with Applications, vol. 4, no. 1, pp. 344-353, 2016.