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:
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:
In reader-to-tag communication, the power 
signal received at tag j from reader i as following:
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:
Ideally, the power 
which transmitted from the reader i by tag j absorbed is calculated as:
One part of power was wore down by tag itself, another part was reflected.
The power 
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:
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
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 
,
respectively 
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:
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:
for arbitrary tag j and reader i. Therefore, Ct can be formally
expressed by the following formula:
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.
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.
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
in the RFID network coverage area, of which j = 1,2,3,…,m and given
the number of n readers’ coordinates  ,
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 |
 |
Definition of fitness function: The fitness function of the target area
tag coverage:
subject to φ1 + φ2 = 1.
The fitness function of between readers interference:
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:
subject to ζ1 + ζ2 = 1.
The fitness function of the cost:
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:
Subject to ω1 +ω2 + ω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. |
|
| 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.
|
| 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.
|
| Fig. 3: |
Gen = 100 readers topological graph |
|
| Fig. 4: |
Gen = 200 readers topological graph |
|
| Fig. 5: |
Gen = 400 readers topological graph |
|
| Fig. 6: |
The coverage of RFID network |
|
| 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 |
 |
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.
Subscribe Today
