Reliability based Radio Frequency Identification Reader

Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
1,3,4
He Xu, 2Suo-ping Wang, 1,3,4Ru-chuan Wang
College of Computer, Nanjing University of Posts and
Telecommunications, Nanjing 210003, China, E-mail: [email protected]
2
College of Automation, Nanjing University of Posts and Telecommunications,
Nanjing 210003, China, E-mail: [email protected]
3
Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Jiangsu,
Nanjing 210003, China, E-mail: [email protected]
4
Key Lab of Broadband Wireless Communication and Sensor Network Technology (Nanjing
University of Posts and Telecommunications), Ministry of Education Jiangsu Province,
Nanjing 210003, China, E-mail: [email protected]
*1, First Author, Corresponding Author
Abstract
The Electronic Product Code (EPC) Network, originally developed by the Auto-ID Center with its
standards now managed by EPCglobal, is designed and implemented to enable all objects in the world
to be linked via the Internet for all time. EPC is the next evolution of product identification, utilizing
Radio Frequency Identification (RFID) technology to identify objects. RFID technology has been
widely used in many areas, and how to deploy of a large number of readers becomes a core challenge
due to the limited read range between reader and tag. This paper proposes a novel reader redundant
optimization model for finding optimal redundant number of readers and their positions to cover all
tags with using optimization algorithm in EPC network. Firstly, we give an overview of the collision
problems in RFID system. Secondly, we propose reliability based RFID reader system model. Thirdly,
we use ant colony algorithm to solve this optimization problem. Analysis results show the effectiveness
of the proposed system model and simulation results show that the algorithm is effective in achieving
the goal of this optimal solution.
Keywords: RFID, Reliability, EPC Network, Ant Colony Optimization
1. Introduction
Along with the advent of the Internet of Things (IoT), the humanity will use artificial
intelligence to process the basic daily management all the time, which will make us extricate
from the tedious low level management, thus more manpower and physical resource will be
invested into this new technical research and development. Radio Frequency Identification
(RFID) technology is one of the key technology of the IoT[1], and has been successfully applied
to the areas of supply chain, transportation, healthcare, mobile payment and services to name a
few[2-6]. An RFID system usually consists of three components: transponder, reader and
middleware. The tag stores information, the reader is capable of reading data from and writing
data to the tag, usually, the middleware usually is a data processing server which consists of a
host computer utilizing data acquired through the reader and applications.
There are two conflicts in RFID reader network, which is tag-tag conflict and reader-reader
conflict. For the tag-tag conflict, ALOHA algorithm[7-9] and the binary tree algorithm[10] are
usually used in RFID system. For the reader-reader conflict, there are also many works done in
this problem. The reader collision problem in RFID system was first presented in [11]. When
this problem was proposed, James Waldrop et al in [12, 13] presented the colorwave algorithm,
which is an anti-collision algorithm for the reader collision problem and presented the
colorwave which is a MAC for RFID reader networks. Colorwave is a distributed TDMA based
algorithm, where each reader chooses a random time slot to transmit. If it collides, it selects a
new timeslot and sends a kick (small control packet) to all its neighbors to indicate selection of
new timeslot. If any neighbors has the same color, it chooses a new color and sends a kick and
International Journal of Advancements in Computing Technology(IJACT)
Volume4, Number18,October. 2012
doi:10.4156/ijact.vol4.issue18.68
577
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
this continues. If the percentage of successful transmission goes below certain threshold, the
maxColors is incremented and if the percentage increases beyond certain threshold, the
maxColors is decremented. But in [12, 13], there was a small numbers of readers in RFID
network.
Shailesh M. Birari and Sridhar Iyer proposed PULSE [14], which is a distributed protocol
reducing reader collisions. In PULSE, there are two channels: data channel and control channel.
The data channel is used for reader-tag communication whereas the control channel is used for
reader-reader communication. It has an assumption that the reader is able to simultaneously
receive on both the control and the data channel. But PULSE is based on a beaconing
mechanism, while a reader is reading the tags, it periodically broadcasts a beacon on a separate
control channel. Any other reader that wants to communicate with the tags first senses the
control channel for a beacon. If it does not receive any beacon for a specified amount of time, it
transmits a beacon and starts communicating with the tags. It then continues to periodically
transmit a beacon as long as it is communicating with the tags. But this kind of periodic
transmitter data for the peripheral neighbor will cause the reader energy consumption to speed
up.
DiCa[15] was proposed to suit for energy-efficient wireless mobile network environments
cooperated with RFID, and the DiCa is capable not only of avoiding collisions, but also
changing power states autonomously through simple interaction of adjacent readers. But DiCa
algorithm has not considered reader’s concrete position, when it carry on the avoidance no
matter whether to have the interference region. In the meanwhile, fairness question has not been
considered among in reader competition data channel’s domination time.
HiQ[16] is a hierarchical, online learning algorithm that finds dynamic solutions to the
Reader Collision Problem in RFID systems. The algorithm is based on a type of reinforcement
learning called Q-learning, which is used to determine frequency and time assignments. But the
tag does not have the frequency recognition capability, while there are two different frequencies
simultaneously reading the identical tag, the tag is unable to decide the information returns for
which reader, and this condition causes collision’s occurrence. Because HiQ has used the
intelligent processing method, and this increases the complexity of the reader protocol design.
The goal of this paper is to study the potential to discover more redundant RFID readers. The
novelty we suggest is that we set up a novel reliability based optimization model with using ant
colony algorithm to solve this optimization model for finding optimal number of readers in
RFID network. The next two sections will describe the proposed optimization model depicting
all the entities, working process and the solution method for this optimization model.
2. Proposed Model
The reliability of RFID reader system is described with the confidence and the coverage. Consider
the reality stream R, and an RFID data stream D. Given R and D, define: (1) True Positives (TP) as the
set of all readings that are present in R as well as D; (2) False Positives (FP) as the set of all readings
that are present in D but not in R; (3) False Negatives (FN) as the set of all readings present in R but
not in D. The confidence and coverage are defined by as follows[17].
Confidence: a per-reading value, gives the probability that the reading exists in the reality stream
(i.e., that the object exists in reality at the given time and location). Ideally, confidence is 1 for all
readings in TP and 0 for all readings in FP. This metric is naturally extended to the entire data stream D,
or any subset of readings: The confidence for a set of readings is the average of the confidences of the
individual readings.
Coverage: Coverage is a window-level value assigned to a set of readings for a given time period
T. It gives the fraction of readings from R in the time period T that are present in D. Hence, for the
entire stream, or for any time-window having associated values of TP, FP and FN,
TP
.
Coverage 
TP  FN
Redundant-Reader Problem[18]: Given a set of RFID tags and a set of RFID readers covering all
the RFID tags, find the minimum cardinality subset of RFID readers, covering all the tags.
Suppose there are n regions and m kinds of readers in RFID Reader system. The similar kind of
578
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
reader is used in each region. According to the above supposition, the redundancy optimization model
for reader system is set up as follows:
n
m
minCs   cij xij
(1)
i 1 j 1
s.t. R s 
n
m
i 1
j 1

Rij ( xij )  R0
(2)
1 if reader is active
xij  
0 if reader is turned off
(3)
Where C s represents the cost of total reader system, Rs is the system reliability,
coverage
of
readerij ,
represents
the
absence
Rij ( xij )
represents
or
present
status
of
reader,
of
the
i-th
m
xi  {0,1}
(
xij
cij is the
),

reliability
j 1
m
subsystem, R ij ( x ij )  1  (1  p ij )

j 1
x ij
,
pij is the confidence of readerij , R0 is the
predetermined reliability which RFID reader system must achieve.
3. Optimization Algorithm
Finding minimal set of readers to cover the entire region in RFID network is a NP-hard
problem[18]. Hence suitable optimization algorithm may be applied to solve the problem. In this paper,
we use the ant colony optimization (ACO) algorithm to solve the Reader Redundant Elimination
(RRE) optimization problem, and name it ACO-RRE. In order to solve the proposed reliability based
redundancy optimization model, we make the constraint equation as the penalty function added to Eq.
(1), then the original constraint question is transformed to non-restraint optimization, which can be
solved by ACO algorithm. Namely,
n
min
m

i 1 j 1
m

  n m
 
 xij
j 1
 R0  
cij xij  M min 0,  (1  Rij )
  i 1 j 1

 
2
(4)
Where M is a very big positive number.
Because of the limit power of reader, coverage area and entire RFID system, the redundant quantity
m

j 1
m
xij (i=1,2,…, n) cannot be too big, suppose the maximum value of

j 1
xij is x max . The
reliability diagram is as Fig. 1 shown. There are x max readers in every column, totally x max  n
readers in RFID network. From Fig. 1 we can see that the 1st column level to the n-th column level are
connected together, which composes a solution. As Fig. 1, it shows an probable solution (31,22,23,
…,1n).
579
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
Figure 1. The reliability based network topology
According to the literature [19], the template for defining ACO models is:
M(<problem>,<update_rule>,<nr_of_ants>)
(5)
Where < problem > is the considered problem (or problem type, such as, for example,
unconstrained problems), < update_rule > is the pheromone update rule that is considered, and
< nr_of_ants > is the number of ants that build solutions at each iteration.
Suppose each column level establishes 1 ant (it is also possible to be set more than 1) in
reliability based RFID network, each ant only moves in its own column level among readers, the
probability of the ant in the j-th column level transfers to i-th reader is
q ij 
q ij :
 ij
(6)
x max

i 1
ij
The renewal equation is:
 ijnew   ijold  Q
(7)
Where  ij represents the attraction intensity of the i-th reader in j-th column,
durable coefficient of the intensity (generally it takes 0.5~0.9),

represents the
Q is a normal number.  ij represents
the target function difference of the Eq. (4). If  ij  0 , because the goal function value reduces, then
the ant moves from the i-th reader to the j-th reader; if  ij  0 , the ant maintains the current condition.
Fig. 2 shows the detailed steps to solve RRE using ACO-RRE, which has the following steps:
1)S = 0(S is the cycle-time), the matrix [  ij ]n  m is bestowed the same value, and set the value of
Q and  .
2)Put each column an ant randomly. (This is similar to give an initial solution) .
3)The ant according to the probability
q ij decides to choose the reader. If  ij  0 , the ant moves
and then set the corresponding xij = 1 ; If  ij  0 , the ant doesn't move, and set the corresponding
xij = 0.
580
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
4) Update the
 ij
according the renewal equation (Eq. (7)), and set S = S+1.
5)If S > predefined cycle times, we record current ant's position (current solution), then stop the
ant’s movement. Otherwise go to step 3.
 ij
ij
ij  0
ij  0
 ij
Figure 2. Flow chart of ACO-RRE
4. Performance Evaluation
In this section, we compare the performance of our ACO-RRE with traditional RRE[18]. In the
experiment, we set: n=m=10,
q ij
= Random (0.5, 0.9),
cij = Random (0.8, 1.0), M=107,
[  ij ]n  m=[10]n  m, Q=10, R0=0.95. The experiment compares the performance of RRE and ACORRE when the number of RFID readers increases from 100 to 1000(that is m or n which changes from
10 to 100), when the total number of RFID tags is 5000.
Fig. 3 shows the results of this experiment. For scarce RFID readers, few of the readers are
redundant. As the number of reader increases, the number of the redundant readers increases, but RRE
discovers fewer redundant readers than ACO-RRE. The experiment’s result shows that ACO-RRE is a
stable solution with good performance for redundant reader elimination for RFID system.
581
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
Figure 3. Number of redundant readers discovered
The second experiment measures the dependency between the number of redundant readers
discovered by RRE and ACO-RRE and the interrogation radius of readers. We randomly deploy 800
RFID readers and 2000 RFID tags, and increase the interrogation radius of readers from 10 to 100m.
Fig. 4 shows that with the increase in the interrogation radius of RFID readers, both RRE and ACORRE discover an increasing number of redundant readers. This is because active readers cover larger
areas, effectively necessitating fewer active readers to cover all the tags. While RRE discovers fewer
redundant readers than ACO-RRE, the difference is almost constant for smaller interrogation zone
overlaps, and the difference between RRE and ACO-RRE increases gradually for large interrogation
zones.
Figure 4. Number of redundant readers discovered by different reader interrogation zone
5. Conclusions
In this paper we firstly give an overview of RFID reader collision problems. Then we set up
optimization model for redundant reader elimination in RFID network which is reliability-based
redundant optimization method, and use ant colony algorithm to solve this problem. Simulation results
582
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
show the effectiveness of the proposed optimization model and also show that the ant colony algorithm
is effective in achieving the goal of this optimal solution. However, the proposed RFID reader system
and the optimal reader redundant model add the communication complex compared with the traditional
RFID reader system. We need to develop a new reader protocol for RFID reader software, and the
security of RFID system in EPC network also has to be studied in future work.
6. Acknowledgments
The subject is sponsored by the National Natural Science Foundation of P. R. China ( No. 60973139,
61170065, 61171053, 61003039, 61003236, 61103195), the Natural Science Foundation of Jiangsu
Province(BK2011755), Scientific & Technological Support Project (Industry) of Jiangsu Province
(No.BE2010197, BE2010198, BE2011844, BE2011189), Natural Science Key Fund for Colleges and
Universities in Jiangsu Province (11KJA520001), Project sponsored by Jiangsu provincial research
scheme of natural science for higher education institutions(10KJB520013, 11KJB520014,
11KJB520016, 12KJB520009), Scientific Research & Industry Promotion Project for Higher
Education Institutions(JH2010-14, JHB2011-9), Postdoctoral Foundation (20100480048), Science &
Technology Innovation Fund for higher education institutions of Jiangsu Province(CX10B-196Z,
CX10B-199Z, CX10B-200Z, CXZZ11-0405, CXZZ11-0406), Doctoral Fund of Ministry of Education
of China(20103223120007, 20113223110002) and key Laboratory Foundation of Information
Technology processing of Jiangsu Province (KJS1022), A Project Funded by the Priority Academic
Program Development of Jiangsu Higher Education Institutions(PAPD). The authors would like to
thank the editors and the anonymous reviewers, who provide insightful and constructive comments for
improving this paper.
7. References
[1]Welbourne E, Battle L, Cole G, Gould K, Rector K, Raymer S, Balazinska M, and Borriello G,
"Building the internet of things using RFID: the RFID ecosystem experience", IEEE Internet
Computing, vol. 13, no. 3, pp. 48-55, 2009.
[2]Koralalage K S and Yoshiura N, "OTag: Architecture to Represent Real World Objects in RF Tags
to improve future Intelligent Transportation Systems", Journal of Convergence Information
Technology, vol. 4, no. 2, pp. 30-48, 2009.
[3]Qadeer M A, Akhtar N, Govil S, and Varshney A, "A Novel Scheme for Mobile Payment Using
RFID-Enabled Smart SIMcard", In Proceedings of the International Conference on Future
Computer and Communication (ICFCC 2009), pp. 339-343, 2009.
[4]Joseph K S, Liang G, Pang K, Sheng H, and Wang D, "Impact of RFID Technology on Tracking of
Export Goods in Kenya", Journal of Convergence Information Technology, AICIT, vol. 5, no. 9,
pp. 190-199, 2010.
[5]Wang S W, Chen W H, Ong C S, Liu L, and Chuang Y W, "RFID application in hospitals: a case
study on a demonstration RFID project in a Taiwan hospital", In Proceedings of the the 39th
Annual Hawaii International Conference on System Sciences (HICSS '06), vol. 8, pp. 184a, 2006.
[6]Nambiar A N, "RFID Technology: A Review of its Applications", In Proceedings of the
Proceedings of the World Congress on Engineering and Computer Science, vol. 2, pp. 1253-1259,
2009.
[7]Floerkemeier C, "Bayesian transmission strategy for framed ALOHA based RFID protocols", In
Proceedings of the IEEE International Conference on RFID (2007), pp. 228-235, 2007.
[8]Wang Y Q, Jiang G P and Wang J, "Framed slotted ALOHA with grouping tactic and binary
selection for anti-collision in RFID systems", The Journal of China Universities of Posts and
Telecommunications, vol. 16, no. 4, pp. 47-52, 2009.
[9]Wang Y Q and Jiang G P, "Dynamic framed slotted ALOHA algorithm used in RFID system",
Nanjing Youdian Daxue Xuebao(Ziran Kexue Ban), vol. 30, no. 1, pp. 26-32, 2010.
[10]Zhang N and Vojcic B, "Binary search algorithms with interference cancellation rfid systems", In
Proceedings of the IEEE Military Communications Conference (MILCOM 2005), pp. 950-955,
2006.
[11]Engels D W and Sarma S E, "The reader collision problem", In Proceedings of the IEEE
583
Reliability based Radio Frequency Identification Reader Redundant
Optimization Model in Electronic Product Code Network
He Xu, Suo-ping Wang, Ru-chuan Wang
International Conference on Systems, Man and Cybernetics, vol. 3, pp. 6-11, 2002.
[12]Waldrop J, Engels D W and Sarma S E, "Colorwave: an anticollision algorithm for the reader
collision problem", In Proceedings of the IEEE International Conference on Communications
(ICC'03), vol. 2, pp. 1206-1210, 2003.
[13]Waldrop J, Engels D W and Sarma S E, "Colorwave: A MAC for RFID reader networks", In
Proceedings of the IEEE Wireless Communications and Networking (WCNC 2003), vol. 3, pp.
1701-1704, 2003.
[14]Birari S and Iyer S, "Pulse: A mac protocol for RFID networks", Embedded and Ubiquitous
Computing, Springer, pp. 1036-1046, 2005.
[15]Hwang K, Kim K and Eom D, "DiCa: Distributed tag access with collision-avoidance among
mobile RFID readers", Emerging Directions in Embedded and Ubiquitous Computing, Springer, pp.
413-422, 2006.
[16]Ho J, Engels D W and Sarma S E, "HiQ: a hierarchical Q-learning algorithm to solve the reader
collision problem", In Proceedings of the Proceedings of the International Symposium on
Applications and the Internet Workshops (SAINTW’06), pp. 1-4, 2006.
[17]Sarma A D, Jeffery S R, Franklin M J, and Widom J, "Estimating data stream quality for objectdetection applications", Technical Report, Citeseer, 2005.
[18]Carbunar B, Ramanathan M K, Koyuturk M, Hoffmann C, and Grama A, "Redundant reader
elimination in RFID systems", In Proceedings of the IEEE SECON, pp. 176-184, 2005.
[19]Dorigo M and Blum C, "Ant colony optimization theory: A survey", Theoretical computer science,
Elsevier, vol. 344, no. 2-3, pp. 243-278, 2005.
584

Download Report