Subscribe Now Subscribe Today
Research Article
 

Multi-objective Optimization of RFID Network Based on Genetic Programming



Pan Weijie, Li Shaobo, Xie Qingsheng and Yang Guanci
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

With the widespread application of RFID tags, the layout of RFID readers under guaranteed the rate of coverage, RFID network load balance and communication quality which becomes a major focus of current research on RFID network. Present study analyzes the characteristics of RFID network and the disadvantages of current optimization methods on readers’ network, by establishing the mathematical optimization model of RFID network, a kind of method that multi-objective optimization of RFID network based on Genetic Programming is proposed and the evolutional topological operators, terminal set and fitness functions are designed. Finally, it realized the module of the multi-objective optimization algorithm, the number of readers and the layout of readers’ automatic optimization. The experimental results show that it has higher efficiency, faster convergence rate and good accuracy. It can keep well balance between topology and parameter search. This research has important reference value in the theory and practice.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Pan Weijie, Li Shaobo, Xie Qingsheng and Yang Guanci, 2011. Multi-objective Optimization of RFID Network Based on Genetic Programming. Information Technology Journal, 10: 2427-2433.

DOI: 10.3923/itj.2011.2427.2433

URL: https://scialert.net/abstract/?doi=itj.2011.2427.2433
 
Received: June 29, 2011; Accepted: August 11, 2011; Published: September 30, 2011



INTRODUCTION

Radio Frequency Identification (RFID) is a non-contact technology through the use of radio frequency signals, space coupling technology, transmission performance to achieving the static or mobile identification items automatic identification (Cho et al., 2007). For the past few years, RFID technology has been widespread concerned which is mainly used in the filed of warehouse management, logistics, supply chain management, identification, entrance guard, item tracking, charging, mobile commerce and security and so on (Mehrjerdi, 2008).

In the past few decades, the studies of the RFID network are mainly about tags anti-collision and reader anti-collision technology (Eom et al., 2009). Among them, the most successful are ALOHA algorithm and binary tree search algorithm for tags anti-collision; others are the improvement of them. For reader anti-collision problem, the main optimization methods are Colorwave algorithm, Q learning algorithm, PULSE algorithm, REQ-BUSY algorithm, IRCM algorithm, RRE algorithm, TPA-CA algorithm and hybrid optimization method, etc. After searching the references about the optimization methods of the readers’ deployment both at home and abroad, we find that the tool RFID cover which is developed by Indian Institute of Technology in Mumbai, India (Anusha, 2005) which is an automated coverage planning tool to deploy the mobile readers using heuristics thinking, mainly applied to retail inventory tracking problem. However, the architecture is lacking description of specific implementations and in the high real time requirement respects are inconsiderate. Hong Kong University of Science and Technology utilized TDMA grouping based RFID network planning using hybrid differential evolution algorithm (Gao and Gao, 2010). A RFID network planning method based on GA by Yang et al. (2009), who is School of Software and Microelectronics, eking University. Chen proposesd RFID network optimization based on multi-species co-evolution (Chen et al., 2008). However, the disadvantages which they provided have one common characteristic is that they must be given the number of readers in advance before optimization, it couldn’t evolve the number of readers all over the RFID network.

In present study, an open-ended method to search topological structure and optimize parameters of RFID network based on Genetic Programming (GP) so as to realize the automatic module optimal design of RFID network is proposed. This algorithm adopts variable hierarchical structure, it is more flexible and reflects the number and distribution of readers more directly which guarantees complete coverage and load balance, meanwhile, reduce collision between readers and has a cost effective.

DESCRIPTION OF RFID NETWORK MULTI-OBJECTIVE OPTIMIZATION

Interference: In the communication process between readers, if there have coverage overlap and when occupy the same frequency, interference occurs between the readers. One of key parameters is that the read/write range of reader. There are several factors that affect the read/write, such as: The frequency of antenna, output power, receiver sensitivity, tags’ power consumption, antenna and the value of Q, antenna aspect, coupling degree, the energy obtained by RF tags themselves and the intensity of transmission signal and so on. The questions described in details as follows.

Suppose the output power by RFID reader i is pir (in terms of dB), its transmission path loss pia can be calculated as following:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(1)

where, Gir is reader i antenna gain, Gji is tag j antenna gain, iε (1,2,3,....,N), j ε (1,2,3.....,M). Ri:j is the distance between reader I and tag j, subject to the coordinate of read i is (rix, riy), the coordinate of tag j is (tix, tiy), Ri:j can be calculated by Eq. 2. α is environmental disturbance, the range between (3, 10), 10 dB is in worst case:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(2)

In reader-to-tag communication, the power Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming signal received at tag j from reader i as following:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(3)

The power received by tags which is related to the power density distribution σ near the tags and the tags’ antenna efficiency. σ can be calculated by the following formula:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(4)

Ideally, the power Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming which transmitted from the reader i by tag j absorbed is calculated as:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(5)

One part of power was wore down by tag itself, another part was reflected. The power Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming reflected from tag j to reader i mainly relative to the reflection efficiency of energy η of tag j. Where λ is the wavelength of the communication between tag and reader:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(6)

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(7)

In tag-to-reader communication, for RFID tags, tags and radio frequency identification system should work in the same frequency can build communication. Meanwhile, in the range of reader antenna directional beam, the communication will be established between reader and tags in the condition that reflected power Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming by tags greater than the backscatter signal thresholdTt and reader receives power greater than the received signal threshold Rt.

For readers interference, the coordinates of the readers i and k within the range are Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming, respectively Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming stands for the read/write range, respectively. We can reduce distance between readers to decrease the interference. In the meantime, we also use TDMA technology to solve the interference problem when occur overlapping regions of between readers.

Coverage: Coverage is an important standard to measure whether RFID network planning is good or bad. There are two major questions need to be considered, firstly, initial distribution of readers could cover all tags in given area, secondly, whether readers can read all tags in given area accurately or not. In this study, we combine the characteristics of RFID network, first of all, initialize the positions of readers, then, adjust the number of readers and topological structure of the deployment of readers dynamically, finally, get the coverage of the total area. At the same time, with the fast development of mobile readers, we bring mobile reader into the deployment of RFID network, to solve the “Bland Area” problem which the sparse distribution of the fixed placement of readers.

Combined degree of coverage with and degree of tags’ coverage which proposed by (Koza et al., 2000), to measure the coverage. In this syudy, adopt the methods combine the Gage’s coverage to measure the rate of the coverage of network with the coverage of the tags. Degree of coverage is defined as the ratio of that the area covered by RFID network readers and the total area of the given region. The area that covered by readers equal to the union set of each readers. Where, Ca stands for the degree coverage of entire RFID network, Ai represents the coverage area of node i, N represents the number of the readers, A represents the destination area. Ca can be formally expressed by the following formula:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(8)

Degree of tags’ coverage Ct is defined as the ratio of that the quantity of the identified tags and the sum of the tags in given area. If the signal power that received by tags greater than the threshold value, the communication is established between tags and readers. Mr are the sum total tags that meet the formula:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming

for arbitrary tag j and reader i. Therefore, Ct can be formally expressed by the following formula:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(9)

M is equal to the number of all tags in given area. We consider the degree of coverage and tags’ coverage.

Load balance: At the architecture of RFID network, we consider that all the readers should work at a load balance scheme.

It can realize that high read/write rate and speed of readers, improve the ability of identify tags and enhance the availability and flexibility of RFID network. It mainly solves the problems like network congestion and when one reader read excessive tags the others on the state of “starvation”.

Considering the integrated load balance of RFID network, we adopt the mechanism of dynamic feedback load balance, mainly use two types of load information: Reading index and reader index.

Definition 1: Reading index is the ratio of the number of new tags read by readers and the average number of tags by readers. In other words, the reading index δi is the ratio that the new tags by reader i and the average number of tags read by all readers within the whole RFID network, δi is as follows, Ni is the number of new tags by reader i.

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(10)

Reader index mainly record its load information, such as, read/write speed, successful reading efficiency, the number of tags read by readers φi, we hope that the relative difference φi is not overlarge.

Cost of deployment: We hope use the least number of readers for RFID network to effectively deploy readers and guarantee complete coverage. For the given region (X,Y), the number of readers Ft required for complete coverage using the layout can be estimated through the prediction formulate (Liping et al., 2006) where, U is the radius coverage of reader.

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(11)

It can be easily seen that only considering the coverage may not be cost-effective. In many practical applications, with the area becoming large, the readers deployed becoming large. We introduce GP to optimize RFID network, hope to get less number of readers relative to the result that the numbers calculated by Eq. 12.

MULTI-OBJECTIVE OPTIMIZATION OF RFID NETWORK BASED ON GP

The model of multi-objective optimization: For the problem of RFID network, the structure of network can be turned into a variable length of the search problem, it can make use of the approach of genetic programming to search for the issue from a small solution, ensuring the quality of service and minimizing the spending. It obtained the layout of RFID readers under guaranteed the rate of coverage, RFID network load balance and communication quality and more cost-effective. As a result of the evolution of GP is the “tree” graph, the problem of RFID network multi-objective optimization can be assumed to be the vertex of graph. So the problem can be transformed into the nonlinear problems of evolution algorithm with constraints, the optimal “tree” graph of evolution is the optimized the readers of RFID network topology. The whole model construction procedure is as follows:

First of all, given the number of m tags’ coordinates Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming in the RFID network coverage area, of which j = 1,2,3,…,m and given the number of n readers’ coordinates Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming, I = 1,2,3,…,n, Given the readers limited service radius, the output powers and so on
Secondly, initialize the embryonic model. This is the beginning of graphics used as growth for evolutionary tree operations, for the problem described in this study, the initial embryo randomly generated by computer. Define the class vertexes, edges and output graphs
In addition, set up function and terminal set (Table 1). Such as, one type is the set of topological operators used to insert, remove, connect or disconnect the vertexes, the other is the set of mathematical operators used to establish the parameters of the base stations, including the common functions set (+,-,*,/) and so on
Finally, set up evolution operators and fitness functions. Define operators (crossover, mutation, etc.) which determine the results of evolution, the conditions whether good or bad of the RFID network topology

Table 1: GP functions and terminals
Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming

Definition of fitness function: The fitness function of the target area tag coverage:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(12)

subject to φ1 + φ2 = 1.

The fitness function of between readers interference:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(13)

The fitness function of network load balance. Considering the two indexes that reading of reader and itself for given area which achieving the load balance of RFID network:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(14)

subject to ζ1 + ζ2 = 1.

The fitness function of the cost:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(15)

For the price of Single reader deployment κ, Ψ is constant.

Total fitness function is combined four fitness function into a single value, as a weighted sum:

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
(16)

Subject to ω12 + ω3 + ω4 = 1.

The algorithm framework: The flow chart for the problem is shown Fig. 1, the description of the algorithm as follows:

Step 1: Initialize generation of evolution G = 0 and tags’ coordinate of entire RFID network.
Step 2: Define fitness function and determine the terminal evolution conditions and initialize population, population size and so on.
Step 3: Use crossover and mutation genetic operators to evolve the topological graph of readers, at the same time, compute the fitness of individual, G = G +1.
Step 4: Test termination rules. If it is content, terminate the algorithm and output the optimal of RFID network topological graph, otherwise, return (step 3).
Step 5: End of the evolution.

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
Fig. 1: The flow chart of RFID network multi-objective optimization based on GP

EXPERIMENTAL RESULTS

The entire algorithm is evaluated against an ideal square working area 50x50 m, working space with 100 tags. It is realized in Visual C++ 6.0 compiler environment, at the same time, in order to conveniently observe the evolved graphs, it can be read by LEDA (http://www.algorithmic-solutions.com/) because it can easily call the interface of LEDA program using the output function. To make it simpler, all coordinates of the users are integer values. In addition, we use the simulation platform of SimRFID which is developed by the RFID Laboratory of department of information engineering and computer fcience, Feng Chia University. The software which is provided to be downloaded on http://rfidlab.iecs.fcu.edu.tw is completely freeware.

First we set the parameters for program running. Set population size: 300, maximum tree depth: 13, initialization tree depth: 3-4, crossover rate: 0.9, mutation rate: 0.1, maximum generations: 500. As the test device, we use the readers and tags that in market commonlt use, the parameters naturally depend on the situation. This experiment adopted the full-direction antenna, power of 1o W; the read range of 8 m, the gains of readers and tags is 1 dB more convenient for computing. It used the minimum-cost spanning tree Kruskal algorithm to guide the evolutionary (Lorenzo and Lorenzo-Freire, 2009). Its main advantage compared with Prim algorithm is often used the edge is less sparse network. First of all, judge whether there is any vertex exists, if so, the procedure continues, otherwise, the procedure ends. Then judge the distance around the vertex and add the new vertex into the graph. Finally, connect the shortest distance of the vertex to get the final graph evolution.

Initialized random readers embryonic simulation results (Fig. 2). The Initial area and tags’ points randomly generated, randomly generated the layout embryonic graph of readers. Due to the choice of evolution initial embryos are significant, therefore, in evolutionary processes, we should through try different things, finally selected relatively optimal initial embryonic to guide evolution.

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
Fig. 2: Simulation of initial readers’ embryo graph

Though 30 times experiment, we took the relatively best results, the topological graphs were shown in Fig. 3, 4 and 5 separately.

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
Fig. 3: Gen = 100 readers topological graph

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
Fig. 4: Gen = 200 readers topological graph

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
Fig. 5: Gen = 400 readers topological graph

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
Fig. 6: The coverage of RFID network

Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming
Fig. 7: The simulation results of RFID network

It has faster convergence rate through analyzing the simulation, this algorithm has obtained the minimum number of reader before 100 generation evolution. In later evolution, it mainly evolved the tree-structure because of constraint, the algorithm convergence speed slow down.

In the process of evolutionary, we analyzed given area tags coverage, interference among readers, load balance for the RFID network. As shown in Fig. 6, with the continuing evolution, the coverage of tags continual rise, the rate of coverage almost 100%. In follow-up evolution, the coverage might be changing. This is a normal phenomenon because the topological graph, in near 480 generations, the network topological graph gradually became stable.

In order to further compare the superiority of the algorithm that proposed, we calculate the number of readers required for complete coverage using Eq. 11, it is about 15. However, the number of readers is just 10 though optimized based on GP, the results less than before optimization obviously.

In order to verify readers’ topological graph, we use the simulation platform of SimRFID. Because the parameters and the type between model of reader and tag and to keep the relative position of reader and tag as invariable, some adjustments to the relevant parameters on the condition have to be done.

Table 2: The number of tags covered by each reader
Image for - Multi-objective Optimization of RFID Network Based on Genetic Programming

The simulation results have been shown in Fig. 7. Simulation suggests that the layout can recognize the tags in 100% within the region which is obtained by automatically optimizing.

The interference between readers mainly among reader 1, 2 and 3, is shown in the layout of readers. Because of the number of tags is large among reader 1, 2 and 3 and considering the other factors in the evolutionary process, the effective way as according to the size of the power to control the read of tags by readers has been used, to aim at the interferences between readers. The number of tags read by single reader in the evolutionary process is as shown in Table 2. The average of 30 times of evolutionary operation is to be analyzed statistically which suggests the layout of reader is basically to prevent the problem that the excessive transfer of one reader and the others “Starvation”. It is to provide handy read-write well and regardless of the position of the readers, reduce the response time and improve utilization ratio of reader, achieve the effect of load balancing between readers.

CONCLUSION

Present study provides the solutions of open-ended questions taking advantage of the multi-purpose evolutionary computing of GP. The technical staffs will be liberated from the heavy RFID network optimization through the automatically optimize of the RFID network reader. People will be more focused on the performance improvement of readers and tags, thus improving the overall effectiveness of the future RFID network. Of course, there is some works need to more study in this study, the main consideration in the evolution is the questions of the layout of fixed readers. With the wide application and lower prices of mobile readers, it will be the focus of the future research work, how to bring in mobile reader in evolutionary process, considering the moving speed and route of mobile readers, evolution of the whole RFID network to better and consider the design of a common RFID network planning system under changing environmental factors in practice. RFID network optimization is a system engineering which is ongoing, complex, involving many aspects and needs more in-depth study and practice.

ACKNOWLEDGMENT

This study is partially supported by the Program for New Century Excellent Talents in University of China under Grant No.NCET09-0094, the National High-Tech Research and Development Plan of China under Grant No. 2009AA043203 and the Natural Science Foundation of Guizhou Province of China under Grant No. QKHJ(2010)2095.

REFERENCES

  1. Cho, C.C., Y. Jiann-Min and W.Y. Jen, 2007. Determining technology trends and forecasts of RFID by a historical review and bibliometric analysis from 1991 to 2005. Technovation, 27: 268-279.
    CrossRef  |  Direct Link  |  


  2. Mehrjerdi, Y.Z., 2008. RFID-enabled systems: A brief review. Assembly Autom., 28: 235-245.
    CrossRef  |  


  3. Eom, J.B., S.B. Yim and T.J. Lee, 2009. An efficient reader anticollision algorithm in dense RFID network with mobile RFID readers. IEEE Trans. Ind. Electron., 56: 2326-2336.
    CrossRef  |  Direct Link  |  


  4. Anusha, S., 2005. RFIDcover-A coverage planning tool for RFID network with mobile readers. Master’s Thesis, Kanwal Rekhi School of Information Technology, Indian Institute of Technology, Bombay, India.


  5. Gao, X. and Y. Gao, 2010. TDMA grouping based RFID network planning using hybrid differential evolution algorithm. Artif. Intell. Comput. Intell., 6320: 106-113.
    CrossRef  |  Direct Link  |  


  6. Yang, Y., Y. Wu, M. Xia and Z. Qin, 2009. A RFID network planning method based on genetic algorithm. Proceedings of the International Conference on Network Security, Wireless Communications and Trusted Computing, April 25-26, Wuhan, Hubei, China, pp: 534-537
    CrossRef  |  Direct Link  |  


  7. Chen, H., Y. Zhu and K. Hu, 2008. RFID network optimization based on multi-species coevolution. J. PLA Univ. Sci. Technol., 9: 413-416.
    Direct Link  |  


  8. Koza, J.R., M.A. Keane, J. Yu, F.H. Bennett and W. Mydlowec, 2000. Automatic creation of human-competitive programs and controllers by means of genetic programming. J. Genet. Program. Evolvable Mach., 1: 121-164.
    CrossRef  |  Direct Link  |  


  9. Liu, L.P., Z. Wang and Y.X. Sun, 2006. Survey on coverage in wireless sensor network deployment. J. Electron. Inform. Technol., 28: 1752-1757.


  10. Lorenzo, L. and S. Lorenzo-Freire, 2009. A characterization of kruskal sharing rules for minimum cost spanning tree problems. Int. J. Game Theory, 38: 107-126.
    Direct Link  |  


©  2022 Science Alert. All Rights Reserved