RSAA:Reliable Splitting Aware ALOHA to Capture The Passing Tags
Lei Kang and Lionel Ni
Department of Computer Science and Engineering
Hong Kong University of Science and Technology
Clear Water Bay, Kowloon, Hong Kong
E-mail: {kang, ni}@cse.ust.hk
Abstract— In some RFID application scenarios, e.g. products the off-the-shelf RFID products. ALOHA based algorithm
checking on conveyor belt or stock taking in warehouse, the works as follows: the reader probes tags with a Q value, each tags labeled on the products should be accessed before fading tag in the probing range will randomly pick one time slot in ???out of the reader’s probing range. Due to the probability ?. The tags will make response to the the frame, ?，(?nature of ALOHA protocols and unreliability of wireless links, reader in the selected time slot. A collision occurs when two passing tags could suffer from colliding or link failures and or more tags make responses in the same time slot. Only tags then move out without successful response. The arriving speed transmit without collisions can be identified. If one tag has of the tags should be decreased to guarantee the query been identified, the reader will choose to read or write the entireness, but the throughput correspondingly drops. The current identified tag or move to next time slot. Another problem here is to increase the system throughput and method is called query tree (QT) [9, 26], such as class 1 maintain an acceptable tag loss probability (or tag loss rate) in generation 1 UHF RFID protocol [14]. As our effort focuses a time constrained environment. Reliable Splitting Aware on the off-the-shelf RFID products, we will mainly study the ALOHA (RSAA) is designed to improve the throughput when ALOHA based protocol. keeping a threshold of tag loss probability. Given a tag loss probability, RSAA can reach the optimal system throughput. We implement it on the NI Emulator as software. Compared with commercial reader with optimal parameters setting and embedded frame adaption algorithms, RSAA can reliably
increases the throughput roughly by 2X. Extensive
experiments in the indoor and imitated outdoor (chamber) scenarios are conducted to demonstrate the efficiency of RSAA. To eliminate the nature constraints of antennas and driver of NI emulator, we further demonstrate the efficiency of RSAA by simulation, which shows that the RSAA can significantly increase the average throughput and energy efficiency.
Keywords-RFID; ALOHA; RSAA
Figure 1. Reliability vs. Moving Speed I. INTRODUCTION
Most RFID application scenarios [16, 17] consist of tags Radio Frequency Identification (RFID) is an emerging that are arriving and leaving frequently, which may be wireless technology used in everyday scenarios, such as caused by the dynamic nature of tags or the limited probing supply chain control, object tracking and asset management. range of reader, such as products checking on conveyor belt The key driver behind this widespread adoption is the and warehouse stock taking by a mobile reader. Hence an simplicity of RFID tag, which consists of a small and important question is whether the existing protocols can inexpensive computer chip. There are three kinds of tags: work efficiently with passing tags. The properties of such passive tags, semi-active tags, and active tags. The passive applications are access time constraint and identification tags can be powered up by the consecutive probing signal entireness, e.g. tag has limited life time in the probing range from the reader, and then transmits the information stored in but tag loss is unpermitted. We start with a common its memory. Semi-active tags are powered by the reader in application demo (rewrite the EPC number of the tag) built the same way with passive tags, but they can drive other on-in the commercial reader CSL CS-461 [29]. The reader can board circuitry by their own power source. Smart active tags write a single tag successfully with 1.8~3.8m/s moving speed have their own CPU, memory and power source. Today’s when range the power level from 16dBm to 20dBm (the large-scale RFID systems generally involve passive and probing range ranges from 0.4m to 0.56m). We next move to semi-active tags. a general case, ten tags passing the probing range A basic issue in RFID systems is tag query, also known consecutively and the result is shown in Fig. 1. We can see as tag identification, which is the procedure that reading the that the reader is highly vulnerable to the increasing moving tags’ EPC numbers (tag ID). To access (read, write or kill speed. After we double the tag density, the reader with etc.) a tag is usually conducted during the procedure of tag 20dBm power (>0.56m probing range) cannot maintain the query. ALOHA-based algorithm, used by EPC Global Class reliability even the moving speed less than 200mm/s. That is 1 Generation 2 UHF RFID protocol [15], is widely placed in because the tags suffer from colliding or link failures and
leave without responding to the reader. To avoid tag loss, we structure is known as binary tree, the main drawback of it is must decrease the arriving speed of tags, which will the high frequent collisions. The DFS (depth first search) dramatically drop the throughput of the system. There is liked binary tree [6, 8] iteratively split the collided tags into naturally a tradeoff between the reliability and throughput. multiple (binary, triple or more) tag subsets until only one In this paper, we propose a novel scheme called Reliable tag make response. This process continues until no tag make Splitting Aware ALOHA (RSAA) to enhance the throughput response. Recently, a researcher shows that the framed and reliability when RFID systems facing the passing tags. ALOHA can generally outperform binary tree [13]. To our best knowledge, this is the first work to reliably Toward the localization and movement of tags, the enhance the system throughput under the constraints finite LANDMARC system [5] can be an attractive alternative for life time of tags. The RSAA mainly consists of four indoor object localization. It was designed to localize the components. First, it combines the design of a new practical objects labeled tags in a certain range, and tag arbitration is optimal frame length, which guarantees the optimal not its focus. In the scenario of object tracking and throughput of single query round. Second, it supports a first management, several much efficient methods proposed in [3], come first serve work mode in the random access nature of which take the advantage of current stored tags information ALOHA based algorithm, which can avoid tag loss in under-to facility the identification of new arriving tags. Though, load situation and guarantee the optimal throughput in the they did not consider how to deal with the tag loss problem, dynamic environment. Third, it takes the speed factor into and the throughput of these methods approach to simple consideration to calculate the optimal frame length, as the query tree protocol and binary protocol in a high tag arriving performance of ALOHA based algorithm is highly speed. We are interested in a more dynamic situation. A influenced by the offered load. Fourth, it can discontinuously similar mobile scenario is discussed in [18], which is to probe the tags to save the energy usage. We finally maximize the number of identified tags by adjusting the implement RSAA in a RFID emulator as software. The arriving speed of conveyor belt. Our work is different with it extensive evaluations demonstrate that the emulator installed in the following ways: their work did not prevent the loss of with RSAA can outperform fine grained configured tags, which is our focus; Their work focus on the speed commercial readers in terms of reliability and throughput. adjustment of the conveyor belt, but we think that adjusting We further simulate RSAA to demonstrate its efficiency. the reader to the environment is more practical than the vice The rest of this paper is organized as follows. The related versa; Our main research interest is on the current RFID work is discussed in Section II. In Section III, we build the systems.
system model and describe the tag passing problem. The Our work falls in the field of multiple accesses in a time RSAA and the main components are proposed in Section IV. constrained situation [19]. But the author of [19] only focus We explain the implementation and the nature constraints of on the TDMA as a time constrained communication protocol, NI emulator in Section V. In section VI we compare time constrained ALOHA had not been discussed. The implemented RSAA with the commercial reader and conduct scheduling of packets in time critical environments is a simulator to further demonstrate the high performance of investigated in [22], which prove a variety of results that RSAA. We make a conclusion and discuss the future work in establish the optimality of the STE (shortest time to Section VII. extinction) policy. The tag accesses in ALOHA system is
quite different from the packets access in other wireless II. RELATED WORK systems. The tag has limited chance to decide when to
transmit, it should be probed by the reader first. Another The identification of RFID tags is a very attractive topic class of related works is queuing system with impatient and many excellent arbitration mechanisms [6, 7, 8, 9, 10, 11, costumers [20, 21, 25]. In [20], the different service 12, 26] have been proposed in the past decades. They are disciplines (FCFS, first come first serve, and SIRO, serve in generally classified into two categories: probabilistic and random order) are discussed and compared in the presence of deterministic, also known as ALOHA-based and query tree impatient customers. Scheduling policy optimization for a based algorithm. In [10], the author shows that the framed class of queues with customer deadlines is analyzed in [21], ALOHA protocol can get the maximum throughput when the which only focus on the FCFS service disciple only. The frame length is set to the number of tags. The estimation traditional queuing theory mainly focus on the FCFS schemes [1, 4] are also crafty designed to count the number discipline, which is unsuitable for the ALOHA related of tags in a very short time interval. The query tree (QT) system, as ALOHA is naturally random and impossible to protocol, which is also known as memoryless protocol [9], implement FCFS. The queuing system generally estimates takes the advantage of tag ID to match query binary string the system by the average queue length and the number of with the prefix of it. The performance of QT depends on the customer loss, our system is naturally tag loss unpermitted. distribution of tags’ ID. A smart trend traverse (STT) Our effort is to maximize the system throughput (arriving protocol [12] is proposed to tolerate different ID distributions, speed of the tags) under the constraint of no tag loss in a time and have been shown very good performance in several ID critical environment. distributions. In [26], IQT (Intelligent Query Tree) is
proposed to identify RFID tags more efficiently in scenarios
where tags IDs have some common prefix. However, these
protocols are designed only for static tags, so cannot evaluate
and efficiently identify arriving tags. Another tree related
III. SYSTEM MODEL (normally 60?). This range is decided by the power of the reader, the distance ； between the antennas to the tags, and A. Reader to Tag Communication the communication types (read or write). The probing range As mentioned earlier, the power of tags are original from can be easily extended to an area or number of tags. We just the continuous RF wave (CW) of RFID reader, by which the treat it as a line for simplicity. The moving speed of the tags tags can operate as requested. In current RFID protocol [15], is ?, so the time constraint of the tags can be defined as the each tag has four Sessions S0, S1, S2, and S3. Each Session length of probing range to the moving speed of tags. We has a flag value to indicate if the tags have been identified. ?？?? and tags have the denote the time constraint by ??This flag is default A and will be turned to B after equal time constraint. The average arriving interval between identification. We choose S2 because the flag will be two tags is ?? ：. The arriving speed of tags could be maintained more than 2 second even no CW received. There represented by ：. In some specific application scenarios, is also a SL value in each tag and default as ~SL. The reader such as conveyor system, the average density of tags is can assert or deassert a tag population to set its SL value as known as d, the arriving speed of the tag can be represented SL or ~SL by a Select Command. The reader can send some by ：???(. We will mainly discuss three system Select Commands to participate the tags into different tag parameters: the probing range ？, the distance ； and the populations by the SL value or Session value. The reader can arriving speed of tags ： . query the asserted (with SL) or deasserted (with ~SL) or both The arriving speed of tags can be under-load or overload. tag populations to perform identification. The tag population The under-load happens when the arriving speed of the tags is divided by the EPC series in the Select Command, e.g. the is below the capacity of the current protocol. For example, tags match the selected EPC number can be set to SL or ~SL. the capacity of framed ALOHA in a static environment is 10 Therefore, the reader can select one particular tag (if the EPC tag/s, hence, if ： ??， ?！，??, the arriving speed is an under-number is previously known) or select all the tag by sending load speed. The overload situation means that the arriving a zero EPC number. The Select Command is usually speed of the tags exceeds the capacity of the protocol. followed by a Query Round and the time interval between Therefore, the tag loss is inevitable for single reader. We these two commands should not exceed the maximum only focus on under load situation for single reader and leave settling-time interval specified in [15]. multiple readers situations for future work. In a normal Query Round, the reader sends a Query The ALOHA based methods are naturally probabilistic, Command with the frame length (Q value) to the tags. The given a time constraint, the loss probability of one particular ?tag randomly picks a time slot from 0 to ???, the tag tag is ???. For a specific protocol, we assume that the picks zero will send a random number (RN16) to the reader. probability of a tag can be identified in one Query Round, Reader could fail to receive a random number in a collision is ????, the loss probability then is ??????, so the or empty slot. This can also happen when the wireless link probability that the tag will move out of the transmission condition is terrible. If no RN16 received, the reader sends a range before making successfully response to the reader Query Repeat Command to move to next time slot, and the ???is ?????????????, where ； is the number of Query ???tag will decrease the picked number by one. If only one tag Rounds that the tag experience in the time constraint, and we in current time slot store the picked number of zero, then a want the ??????. single RN16 will be received by reader if no link failure. The We can drive the similar observations in [19] from the reader can choose to read or write this tag or only identify its above equations: Given a fixed arriving speed, the larger the EPC number, and then sends a Query Repeat Command to imposed time constraint, the smaller the loss rate. Given a move to next time slot. fixed loss rate, the larger the arriving speed, the larger the time constraint needed to realize this fixed loss rate. Given a fixed time constraint, the larger the arriving speed, the larger the loss rate. The problem solved in this paper can be easily described as: in a listen-before-talk system (such as RFID system, tags listen to the reader and then talk back), given a fixed loss probability (or reliability), what is the largest throughput we can achieve.
C. Important Metrics
Loss probability: The loss probability of a tag is the probability that it has not been identified or accessed by the Figure 2. An illustration of tag passing reader in the time constraint. In ALOHA systems, the tag loss emerges when it has no opportunity to make response B. Problem Description after the failures (collision happens) of prior Query Rounds, or in overload situation. In most applications, the tag loss is The RFID system considered in this paper consists of one
unpermitted, or more precisely, the loss probability of a tag reader and many tags. The tags are coming and leaving. The
should below a value ?. length covered range by the reader is called probing range ？,
which is formed by the directional antenna of reader
Reliability: The reliability can be seemed as a Boolean Query Command (see Table II) to choose a particular tag function of the tag loss rate, as the RFID related applications population. The Select and Query commands are partially are naturally lost unpermitted, such as the conduct selling shown in table I and table II. The full version of these two and vehicle charging. For simplistic, we set the reliability as commands can be found in current EPCglobal UHF RFID one minus tag loss rate. The loss probability is a definition protocol [15].
regards to single tag and the reliability is a definition regards The efficiency of ALOHA-based protocol depends to the to the system or the tags as a whole. offered load, which is the number of tags over the frame Throughput: The throughput of the system is defined as length. On the one hand, we split the arriving tags according the expected number of successful identification or access to the rest life time. In the under-load situation, we prefer to per time unit. It is proportional to arriving speed of tags identify the tags with the least life time. On the other hand, when no tag loss. The discussion of throughput is in the we consider the arriving speed of tags when calculating the domain of reliable system, that is, throughput could be frame length to enhance the capacity of RSAA. Toward the treated as useless when the system is unreliable. energy efficiency of the system, we choose the session S2 Energy efficiency: The energy efficiency refers to the and calculate a reasonable probing interval. Below we ratio of the number of identified tags to the energy the reader discuss the four main components of RSAA in detail. cost. We adopt the model in [6] for the energy cost of the A. Optimal Frame Length reader, which involves in the transmission and receiving The traditional slotted framed-ALOHA can get the energy cost of the reader. optimal capacity when the offered load is equal to one, in
other words, the frame length is equal to the number of tags. TABLE I. SELECT COMMAND The assumption therein is that each slot has the identical time, Target Action which is not reasonable in RFID systems, as the empty and 000: Inventoried (S0) 000: Assert SL or inventoried ; A collision slot cost only a small amount of time [15]. The slot 001: Inventoried (S1) 001: Assert SL or inventoried ; A only one tag make response will cost different amount of 010: Inventoried (S2) …… time depends to the user demand, query or read or write the 100: Inventoried (S3) 011: Negate SL or (A;B, B;A) tags. 101: SL 100: Deassert SL or inventoried ; B Here we extend this model. We assume that the time cost 101: Deassert SL or inventoried ; B . The slot only one tag make of empty and collision slot is ??response will cost ?, which could involve in the time cost of ?TABLE II. QUERY COMMAND identification, read or write or all. The total time cost
is ??；???~??, where ； refers to the frame length ????Sel Session Target Q ?and is the contention probability of each tag, ~ is the ?00: All 00: S0 0: A 0 – 15 ?expected number of tags that successfully make response in 01: All 01: S1 1: B ????one round. We can know that ~?~?????, where ~ ?10: ~SL 10: S2 ?is the number of tags in the probing range. The throughput of 11: SL 11: S3 ?????one Query Round is , which is the proportion of time ??IV. RELIABLE SPLITTING AWARE ALOHA (RSAA) cost that used for tag access. We first briefly explain the basic idea of RSAA. The Lemma 1. Suppose the number of tags ~ is known, the RSAA uses the stored SL value in the tag to split the tag optimal frame length of ALOHA based RFID systems is ~ ?populations. The reader first asserts or negates the currently ?and the corresponding throughput is at least . ?????unidentified tags as SL, so that the tags are logically ??????separated from the new arriving tags, which store ~SL. In the The throughput of one normal Query Round is . ????????coming several Query Round, the reader only query the tag ?????We can maximize the throughput by maximizing . The population with SL. After there is no collision from the SL ????value tag population or a pre-assigned time limit, the reader minimum value of concave function can be reached when the will send another Select Command to reverse the SL value of derivation of it equals to zero. Let the derivative of this ????the tags in the probing range. The reader again starts to query function with respect to equal to zero, we can get ????the tags with SL. The interval between two consecution ?????????reverse commands is called a Query Circle. As the logical ?????????~??????? ??，. The ； could ???staying tags and the new arriving tags are stored different SL not be one, so ；?~. The throughput then is values, the reader can split them and focus on the query of ????????, as ??????? is at least as ???the tag population with less life time. ??????????????????????As shown in Table I, this Select Command includes ? increases from 2. several Target bits, which indicate the Session number and The optimal throughput of one Query Round is a ??the SL value. The reader normally can send out several monotonic function of . To achieve the optimal capacity, ??Select Commands to divide or choose the tags. After state we should estimate the number of tags in the range by the tags to particular populations, the reader then send a estimating the arriving speed and calculate the current
identified tags. After we finish one Query Circle and start to access the new coming tags, we can calculate the number of tags by the estimated arriving speed of tags. During a Query Circle, we can easily know the rest tags by the estimated number of tags and identified tags in prior Query Round. The methods of estimating the number of tags can be found in [1]. B. First Come First Serve
Although the work modem of RFID system is random access, we can conduct a FCFS (First come first serve) modem to avoid the unnecessary tag loss and tolerant a much higher arriving speed of tags. The optimal capacity of RFID system in single Query Round is discussed in prior section. Figure 3. Loss Probability vs. Time Suppose the capacity of each Query Round is the same and independent to the number of tags. We already know that C. Arriving Speed Estimation there are ？tags in the probing range by the frame length ? The estimation of the moving speed and arriving speed is estimation method described above. The rest life time of important. Based on the estimation, we can know the life them is ????？?：. We seem the ？ tags as whole and ????time of each tag and number of tags in the probing range. the life time of them depends on the least life time one. We Meanwhile, we can compare the estimated arriving speed will adaptively set the frame length so that the time cost of with the capacity of the RFID system to see if it should warn ??each Query Round will be ？??????(？??????????????that the arriving speed is overload. Firstly the reader records ?????()(？?????????, where ? refers to the ????a start time t (s) when identifying all the tags in the range identification probability of in one Query Round and ： is the with the value of SL. After all the tags in the range are number of Query Rounds in one Query Round. Meanwhile, identified, the reader reverse the SL value of all the tags to ???the loss probability of each tag is ???????. We estimate the number of new arriving tags N (SL) and record assume a fixed probability value here. the current time t (c). The estimated arriving speed of tags is We can easily find three constraints in our system model. simply ：?？ ?，？?? ?? ?，? – ? ????. We renew the estimated First, suppose there are ： Query Rounds in this Query Circle, V by average the sum of all the estimated values. the time cost of this Query Circle should be less or equal to ?????the rest life time, ？??????????????. Second, ????D. Energy Efficiency ???we want the loss probability of any tag therein to be less than In a low speed situation, the first arriving tags are the first ?or equal to ?. We should guarantee that ???????. In Fig. choice of identification. However, when we probe the new 2, we compare the tag loss probability of RSAA with the arriving tags, there could be no tags come in the current normal ideal. The only different of normal ideal scheme and Query Circle. The redundant probes will cost energy and so RSAA is that RSAA split the tags. We use the measured that the performance of protocol drops. If we stop probing parameter in our experiment to see the relation between time and the state information of tags will change so that the old and loss probability, and found that the loss probability of tags will be identified again when next probing period. To RSAA quickly approach to zero as time goes on. It should be avoid the redundant identification, we choose Session S2 as noted that we did not involve in the link failure in this the state information of tags will keep more than 2s even no analysis. Third, after the identification of the ？ tags, the ?Continuous Wave received. number of new arriving tags should be less or equal to ？, ?When the arriving speed of the tags reaches the i.e. ：? ?????????? ,so that we can guarantee the next ??maximum value, the energy efficiency also is optimal. circle we can still finish successfully or maintain the desired Sometimes, we should keep the speed in a low level to loss probability. The k will approach infinity and the loss tolerate the varied tag density in the real deployment. We probability will reach to zero in the reasonable time need a probing interval to discontinuity initialize the reader. constraint. If we wait too long (less than 2s), the arriving tags become Lemma 2. The RSAA can get optimal throughput when too many to be identified in the range, the loss probability the number of tag in the range ？ falls in the ?will increase. There naturally a tradeoff between the cost and interval ?，(??????????, where ???，(??. ?????the loss probabilistic. The interval can be calculated as ？?：. ?This proof could be quite simple. Combine the The ： here is the estimated tag arriving speed and ？ fall in ?constraints described above, we can get the interval of ？. ?the stated interval. Toward the current tags in the probing range with SL value, we can get the maximum throughput by the calculation of V. IMPLEMENTATION optimal frame length, as we always know the number of tags. We implement RSAA on the NI VISN RFID test We assume perfect arriving speed estimation here and software, an EPC Gen2 Reader Emulator [26]. This RFID present our estimation method below. Towards the new test software has built in capability to make the user generate arriving tags, we can also get the maximum throughput as its self demand RFID signal of global requirement, ISO/IEC number is smaller than ？. ?18000-6C (EPC Global Class 1 Gen 2) [15]. The
implementation RSAA focuses on the protocol layer and Query Round as long as it can be identified, but we cannot invokes the reader to tag commands by a graphical language interrupt the multiple tag query process of the NI emulator. Labview. We do not choose the commercial readers, e.g. The only thing we can do is firstly identify the tags and then CSL CS-461, as which encapsulate the most command access each in a new Query Round by its EPC number. This parameters and only open scanty APIs to the users. We use will cause extra one Query Round for each tag access. We the 3000794 Dual Dipole “Frog” tags produced by UPM implement RSAA in the way described above. And the real Raflatac [27]. RSAA could perform 10~100 percent better in the normal
access mode.
VALUATION VI. E
Our evaluation consists of two parts, emulation part and
simulation part. In the emulation part, we compare
implemented RSAA with CSL commercial reader. We left
the comparison between RSAA and other mechanisms in the
simulation part. There are three reasons for this separation.
First, we compare RSAA and commercial reader to show the
performance of RSAA as a software product. Second, a most
recently proposed mechanism, smart trend traverse (STT)
protocol [12], is a tree based method. The current protocol that RFID emulator adopts is ALOHA based, and the tree Figure 4. Experiment Envrionment based method (e.g. STT) cannot be effectively implemented
on the emulator. Meanwhile, the tags usually have the same
default EPC number, where the tree based method doesn’t
work. Third, due to the antenna and driver constraints of the
emulator, the emulator is not a good platform to conduct the
comparison among different mechanisms fairly and
intuitively. The emulation and simulation results are shown
as below.
TABLE III. EXPERIMENT SETTINGS
d D L Power Indoor 12.5tag/m 0.3m 0.32~0.56m 16~20dBm Figure 5. Experiment Set Up Chamber 12.5tag/m 0.3~1m 0.32~0.8m 18~24dBm
A. Antennas Setting
The NI emulator has two antenna ports, one for A. Emulation Results
transmitting and the other for receiving. Two antenna setting We evaluate RSAA by rewriting the EPC numbers (IDs) will drop the performance of the system, and will be less of the tags, which is a general application as the kindred tags efficient compared to the commercial reader’s single antenna usually have the same EPC number. The user must rewrite setting. If the orientations of the two antennas (about 60?the EPC number before or after labeling it on the directional) are parallel, the probing range will be quite small, corresponding products. It should be noted that the write will and the tag will have very limited life time. If we enlarge the cost a little more time than just read and cost less time than overlap of their work range, the transmitter will produce write extra information the other memory bank of the tags. extra noise to obstruct the receiving and decoding of the Therefore, our evaluation is representative enough to all the receiver, and the tag cannot be successful decoded. This applications related to the tag access operations. The CSL influence can be partially reduced by increasing the distance CS-461 EPC C1G2 RFID Fixed Reader has a build in demo of tag and antenna, but the wireless links will become more that rewrite the EPC number of the tags. In order to eliminate unreliable as the distance increase. The two antennas setting the immanent performance difference of different products, of NI emulator are naturally deficient. we also simulate and compare the RSAA with stimulant
reader and real commercial reader. B. Driver Constriants There are 10 tags attached on a board (see Fig. 3), which The NI emulator opens all the parameter settings but is carried by a conveyor belt. The conveyor belt is controlled encapsulate the driver. The time gap between a Select by “high speed carrier”, the speed of which range from Command and a Query Command is microsecond [15], so it 100mm/s to 10m/s. We will compare the performance of is impossible to implement these two successive commands RSAA implemented in NI emulator and that of the demo by protocol level program. The NI emulator opens two program in the commercial reader (CR) in indoor commends, multiple tag query and single tag query. The environment and chamber. The power level of the reader is normal process of one tag access can be finished in one range from 10~24dBm and the probing range is usually
range from 320mm~1m. The tag density is 12.5 tag/m, i.e. from the expected capacity of it. We conduct the similar
the “frog” tag is size of 80*80 mm. The power levels in the experiment in the chamber and get approximately the same
indoor environment and chamber are a little different results.
because the chamber is wide and the distance between the 2) Varying the Probing Range tags and antennas can be adjusted from 0.3m to 1m. To better demonstrate the performance of RSAA, we further conduct groups of experiment in a chamber, which is like an open field that can eliminate the influence of the physical environment. We vary the probing range and the distance between the antenna and the tags to compare RSAA with the CR. The throughput is measured as the number of written tags per second, which is measured when the reliability is equal to one.
As shown in Fig. 5, the RSAA can generally increase the throughput by 1.5~2x with the same reliability. Four tags can be successfully written per second on the conveyor belt. Generally, in longer the distance, the link will be more unreliable even more power is supported. The RSAA can still quite reliable because the reader writes the tags also roughly in FCFS order. In a quite long distance, e.g. 1m, the Figure 6. Reliability When Varying the Moving Speed probing range will became a Boolean value, either quite large with high power or none bellow a power threshold. B. Simulation Results
The reader can identify hundreds of tags per second and rewrite the EPC number in 10~20ms. The fastest tolerated speed of single tag written of commercial reader is 3.8 m/s (indoor environment). Writing 20~40 tags per second is more reasonable than the conclusion we already have. To eliminate the nature constraints of the antennas and driver, we build a simulator to see how efficient RSAA can be after built in the driver. Meanwhile, we want to compare RSAA with other mechanisms (e.g. STT) that cannot be directly implemented on the emulator and commercial reader. We Figure 7. Throughput vs. Probing Range briefly describe our simulator below.
The tags are coming and leaving in a given arriving 1) Varying the Arriving Speed speed. The tags can be coming set by set, and each set We conduct the experiment in a narrow corridor (indoor contains one or several tags. In some applications, there environment), the distance between the antenna and the tags could be some tags arrange in a container that comes to the are constrained (by the environment) in half meter. We fix reader. The time interval between two coming tag sets can the probing range ？ and distance ； of the CR and the NI follow a uniform distribution or a Poisson distribution. Each emulator to compare the lost probability in different moving tag will stay fixed time duration in the probing range of the speed of tags. In the identical setting, the distance between reader. This setting is representative enough for the most the antenna and tag is 0.3m and probing range is 0.4m, we today’s applications. For simplistic, we use the probing range test the maximum tolerated single tag moving speed of the only to replace the combination of reader power and the CR and emulator. The CR can tolerate the speed of 1.8m/s to distance in our simulator. rewrite the EPC number of singe tag and RSAA can tolerate We compare RSAA with Aloha with Frame Estimation that of 1.7 m/s. (AFE), Simulated Commercial Reader (SCR) and Smart We run the process of rewrite the 10 tags 10 times for Trend-Traversal (STT) [12]. The RSAA and AEF use the each speed, and set the reliability is one minus the proportion same frame estimation algorithm [1], the only difference is of lost tags. In general, we seem the reliability is one when that RSAA is capable of estimating arriving speed of tags but no tag loss and zero even only one tag loss. The RSAA AFE is not. The SCR has a different frame estimation installed in the NI emulator can outperform the commercial algorithm. In SCR, the Q is selected by the following process: reader in the similar environment parameter configuration. In the interrogator first initialize a Q value and send out a a conveyer belt system, the throughput depends to the Query command to the tags, the tags which pick a 0 will arriving speed of products. The RSAA can reliably enhance make response, the interrogator then know the number of tag the throughput by 2x compared to the commercial reader. responses. If the number of tag responses is 0, Q= max (0, Q-The deviation of the reliability is the floating lost number in C), if it is larger than 1, Q= min (15, Q+C), else Q=Q+0. C is each experiment round. Due to the constraints of the a system parameter and typically in the range of 0.1~ 0.5. antennas and driver, the shown performance of RSAA is far This method is recommended by the EPC C1G2 RFID
protocol [15], we believe the reader embed the similar range is measured by the number of tags. In our system, the algorithm. STT is a tree based algorithm and simulated by throughput is related to the tolerated arriving speed and its default settings [12]. bounded by the capability of ALOHA protocol. The
throughput gain of RSAA is from the frame length
estimation algorithm and first come first sever work mode. In
Fig. 10, the throughput is measured when the reliability of
the system is equal to one, as we believe the throughput of
the system is meaningless in a low reliability situation. As
shown in Fig. 11, the energy efficiency of each method is
roughly proportional to its throughput. A high throughput
means that the work (e.g. write 1000 tags) can be finished in
a relative short time, so as the energy efficiency. Other
methods should keep probing the passing tags, so that most
of energy is wasted.
Figure 8. Reliability vs. Moving Speed
Figure 10. Throughput vs. Probing Range
Figure 9. Energy Efficiency vs. Moving Speed
1) Varying the Ariving Speed
We simulate 1000 tags are coming and leaving in an even
speed, the reader can probe 10 tags at most in the probing
range. The reliability is measured as one minus the loss rate
of the tags. We run the four methods in each moving speed
of the tags only once. The results are shown in Fig. 7. RSAA
can outperform AFE by the speed estimation and the frame
length estimation in the beginning of each Query Circle.
Meanwhile, the frame estimation algorithm of AFE shows
the similar performance compared to that of SCR. But the Figure 11. Energy Efficiency vs. Probing Range
frame length estimation method of SCR is not as “stable” as
that of the RSAA. This may be caused by the unstable frame 3) Consider Link Failures
adaptation method. STT is a little worse than other methods The time slot is set as 1 ms and the written process cost as the cost on the reader query. It should be noted that link 10ms. The link failure probability is 20~40 percent for the failure is not considered in this evaluation. CSL commercial reader (varying from different power level). The energy efficiency is measured as the time used on The link failure means the signal transmitted from the tag (up the tag access operation over the total time the reader link) is not successfully received by the reader. There are operated. The RSAA can maintain much higher energy two possible reasons. First, the energized tag (power is efficiency in each arriving speed than other methods. The insufficient) is shut down when writing, which will waste energy efficiency gain comes from the discontinuous probing one slot and cause possible collision. Second, the reader of the reader when no tags make response to it in the probing successfully receives the packets but cannot decode due to a range. The reader will power down and wait for the tags. The lower SNR. To make a fair comparison, we vary the link logical stay tags will maintain his state even no CW received failure probability in our simulator. The quality of down link as it chooses the Session S2. is quite reliable if no interference.
A common link failure is that the tag has insufficient 2) Varying the Probing Range power to rewrite the EPC number. We evaluate the several We evaluate the throughput and the energy efficiency methods in different link failure settings. The throughput when varying the probing range in this section. The probing
ratio is the ratio of the throughput of other methods to that of VII. CONCLUSION AND FUTURE WORK
the AFE. The reason we select AFE as the baseline is that the In this paper, we present a novel scheme reliable splitting frame adaptation algorithm in a normal Query Round is the aware ALOHA (RSAA) to capture the passing tags in RFID same as the RSAA. As shown in Fig. 12, the performance of systems. This is the first work to deal with the limited life RSAA increases as the increase of link failure probability, time tags. The RSAA is implemented in a RFID emulator. which indicate that RSAA is reliable to link failures. Through extensively experiment and simulation, the RSAA
can tolerant larger arriving speed of the tags in the under
load situation, by taking the speed element into the
calculation of the frame length. We believe that the
techniques proposed in this paper can work effective in many
application scenarios. Our ongoing research is focused on the
multiple arriving tag streams in the high arriving speed
environment.
ACKNOWLEDGMENT
We thank Carlo and Eric for their kind support for the
experiment. If you want to know how nice one person can be, you should find Carlo. Figure 12. Throughput Ratio vs. Link Failure probability REFERENCES
4) Complex Environment [1] M. Kodialam and T. Nandagopal. Fast and Reliable Estimation In a complex application environment, the arriving Schemes in RFID Systems, In Proceedings of ACM MOBICOM, Los Angeles, CA, Sep. 2006, pp.322-333. interval between two tags generally follows a Poison
[2] M. Buettner and D. Wetherall. An Empirical Study of UHF RFID distribution. Meanwhile, several tags may enter the probing Performance. In Proc. ACM MobiCom, 2008. range at the same time, as they are packed in the same [3] J. Myung and W. Lee, “Adaptive Splitting Protocols for RFID Tag container. The evaluation results in a complex application Collision Arbitration,” in Proceeding of ACM MobiHoc, 2006. environment are shown in Fig. 13. The Normal curve [4] C. Qian, H.-L. Ngan, and Y. Liu, “Cardinality Estimation for Large-represents a result in a uniform arriving interval distribution scale RFID Systems,” in Proceeding of IEEE PerCom, 2008. and tag comes one by one environment. The Set curve [5] L. M. Ni, Y. Liu, Y. C. Lau, and A. Patil, ”LANDMARC: Indoor represents a result in an environment that tags comes set by Location Sensing Using Active RFID,” in Proceeding of IEEE set, and each set contain 4 tags. The Poisson curve PerCom, 2003. represents a result that the time interval between two arriving [6] V. Namboodiri and L. Gao, “Energy-Aware Tag Anti-Collision tags follows a Poisson distribution. The Set+Poisson curve Protocols for RFID Systems,” in Proceeding of IEEE PerCom, 2007. represents a result in an environment that combines those in [7] J. I. Capetanakis, “Tree algorithms for packet broadcast channels,” Set and Poisson. The tags come set by set turns out to be IEEE Trans. Information Theory, IT-25(5):505-415, Sept. 1979. better than that come one by one. It shows that RSAA is [8] D.R. Hush and C. Wood, “Analysis of tree algorithm for RFID reliable to the application that tags come in a container. arbitration,” Proc. IEEE International Symposium on Information Theory, p.107, 1998. Poisson arriving tags make a little influence on RSAA, as the
Poisson arriving affects the speed estimation method of [9] C. Law, K. Lee, and K.-Y. Siu, “Efficient Memoryless Protocol for Tag Identification,” in Proceedings of Int’l Workshop on Disc. Alg. RSAA. The RSAA works in a complex application and Meth. for Mobile Comp. and Comm., Aug. 2000, pp. 75–84. environment shows better results than that other methods [10] F. Schoute, “Dynamic Frame Length ALOHA,” IEEE Trans. even work in a simple environment. Commun., vol. 31, no. 4, pp. 565–568, Apr. 1983.
[11] V. Anantharam, “The Stability Region of the Finite-user Slotted ALOHA Protocol,” IEEE Trans. Inf. Theory, vol. 37, no. 3, pp. 535 – 540, May 1991.
[12] L. Pan and H. Wu,”Smart Trend-Traversal: A Low Delay and Energy Tag Arbitration Protocol for Large RFID Systems,” In Proc. IEEE Infocom, 2009.
[13] Wen-Tzu CHEN,”Performance Comparison of Binary Search Tree and Framed ALOHA Algorithms for RFID Anti-Collision,” IEICE TRANS. COMMUN., VOL.E91–B, NO.4 APRIL 2008.
[14] A.-I. Center. 860mhz-930mhz class 1 radio frequency identification tag radio frequency and logical communication interface specification candidate recommendation, version 1.0.1. 2004. [15] EPCglobal. Epc radio-frequency identity protocols class-1 Figure 13. Throughput Ratio vs. Link Failure probability generation-2 uhf rfid protocol for communications at 860 mhz-960 mhz version 1.2.0.2008.
[16] Venture research Inc. “RFID Conveyor Tunnels”,
http://www.ventureresearch.com/PDF/ConveyorTunnels.pdf
[17] 90% Reduction in Daily Stocktaking Time with RFID Smart Fashion [24] Alien Technology Corporation. “EPCglobal Class 1 Gen 2 RFID Shop. Specification”. Whitepaper 2005.
http://www.blackbay.com/fileadmin/newsletter/Blackbay_Newsletter[25] F. Baccelli, P. Boyer, G. Hebuterne. “Single-Server Queues with _SeeNow.htm Impatient Customers”. Advances in Applied Probability, Vol. 16, No. 4 (Dec., 1984), pp. 887-905 [18] L. Simon, P. Saengudomlert, and U. Ketpro. “Speed Adjustment Algorithm for an RFID Reader and Conveyor Belt System [26] A. Sahoo, S. Iyer and N. Bhandari. “Improving RFID System to Read Performing Dynamic Framed Slotted Aloha.” IEEE International Tags Efficiently”. Technical Report, 2006 Conference on RFID, 2008. [27] NI-VISN-100 RFID Tester , Shanghai China [19] J. F Kuraose, M. Schwartz, and Y. Yemini. “Multiple-Access http://sine.ni.com/apps/utf8/niaa.ind_pro_view?p_all_id=2365&p_disProtocols and Time-Constrained Communication”. Computing play_all_id=14621 Surveys, March 1984. [28] UPM Raflatac tag products, [20] Pla V, Casares-Giner V, Matinez J. On a multiserver finite buffer http://www.upmraflatac.com/northamerica/eng/RFIDProducts/ queue with impatient customers. Proceedings of ITC specialist [29] The CSL CS-461 EPC C1G2 RFID Fixed Reader. seminar, Antwerp; 2004. http://www.rfidsolutionsonline.com/product.mvc/Class-1-Gen-2-[21] Shivendra S. Panwar. “Optimal Scheduling Policies for a Class of UHF-RFID-Fixed-Reader-0002?VNETCOOKIE=NO Queues with Customer Deadlines to the Beginning of Service”. ACM Journal of the Association for Computing Machinery. 1988.
[22] P. P. Bhattacharya and A. Ephremides. “Optimal Scheduling with Strict Deadlines” IEEE Transactions on Automatic Control. 1989. [23] C. Woo Lee, H. CHO, and S. Woo KIM. “An Adaptive RFID Anti- Collision Algorithm Based on Dynamic Framed ALOHA”. IEICE Transactions on Communicatoin. 2008.
Splitting Aware ALOHA (SAA)
Send Select Command (Target=101&& Action=011);
Send Query Command (Sel=11 && Session=10 && Target=0&& Q=function (v));
One Query Round: Waiting for response to access the tags and estimate the number of tags N (SL);
t(c) = system_time;
v _now= N (SL) / (t(c)-t(s));
v = (n*v_now + v) / (n+1);
n=n+1;
t(s) = system_time;
if (V(E) < throughput(RSAA))
mode = 0;
else
mode = 1;
end if
while over!=1 do
Send Query Command (Sel=11&&Session=00 &&
Target=0 && Q=function (N (SL)));
One Query Round: Waiting for response to access the tags and estimate the rest number of tags N (SL);
if(mode==0 && N(SL)==0)
then over=1;
else if(mode==1&&time - t(c) > threshold)
over=1;
end if
end while
Repeat all.