Three-Count Based Algorithm for Redundant Readers Elimination in the Complicated RFID System
Zhou Shen, Zhiying Yang*
College of Information Engineering, Shanghai Maritime University, Shanghai, China
To cite this article:
Zhou Shen, Zhiying Yang. Three-Count Based Algorithm for Redundant Readers Elimination in the Complicated RFID System.Internet of Things and Cloud Computing.Vol.3, No. 2, 2015, pp. 8-13. doi: 10.11648/j.iotcc.20150302.11
Abstract: Over the past decade when RFID (Radio Frequency Identification) technology is fully employed in areas, the redundant data processing in the actual system is one of the most important aspects, which furthermore affects the accuracy and the working performance of the system and leads to the waste of devices resource. Based on the previous algorithms like RRE and LEO, this paper works out an algorithm, TCBA (Three-step Count Based Algorithm), using the number of neighbor readers and the count of the tags which are covered by the neighbor readers as factors to remove the redundant readers. The simulation results show that our algorithm can substantially eliminate more redundant readers than RRE and LEO.
Keywords: Radio Frequency Identification (RFID), Redundant Reader, Removal Algorithm, Simulation System Introduction
Radio Frequency Identifier (RFID) system is composed of two main components– RFID transponders (tags) and RFID transceivers (readers). In a densely deployed RFID network, over-intensive readers easily lead to mutual interference because the radio frequencies of two or more neighboring readers may overlap and interfere. Consequently, finding the minimum number of readers to cover every tag efficiently, called the redundant reader eliminating problem (RREP), is an important and fundamental problem in RFID system. The RREP has been reduced from the minimum cover problem and thus proved to be NP-hard in [1, 10].
In this paper, a Three-step Count Based Algorithm (TCBA) is designed to detect and eliminate a larger number of redundant RFID readers, based on the number of neighbor readers and the count of the tags which are covered by the neighboring readers. Simulation results illustrate that TCBA has a better capacity to detect more redundant readers, a maximum of up to over 21% more effectively than RRE and LEO in the conditions we set.
2. Related Work
Lots of research work on the redundant reader elimination problem have been done [7, 8, 9, 10]. For reader's convenience, some definitions are given as following.
Definition 1: Aredundant reader means that in RFID system a RFID reader covers a group of RFID tags, which are also covered by the other RFID readers simultaneously.
Definition 2: Redundant reader eliminating problem (RREP) is defined as given a tag set and a reader set that cover all the tags, to find a minimum reader set that can cover all tags. RREP has been proved to be NP-hard.
As the simulative RFID network shown in Figure 1, readers R2 and R4 are the ones really need to keep active, and readers R1, R3, R5 are redundant RFID readers which need to be closed.
2.1. Algorithm RRE
Carbunar B, Ramanathan M K et al in 2005 proposed the redundant readers eliminate algorithm RRE (Redundant Reader Elimination) . The algorithm proposed a subset of approximate solution of covering the minimum cardinality of an electronic tag in the RFID system. The steps of RRE are as follows:
(1) Each RFID reader attempts to write the count of the tags it covers. An electronic tag only memorizes the maximum count and the ID of the owner of the maximum count. For this, each reader deliver a writing command containing its identifier and tag count. The writing operation is performed during consecutive epochs, and once per epoch. During each epoch, the time frame for sending the writing request is randomly chosen. This process ensures that at least one writing command delivered by each RFID reader will be correctly received by all its covered tags. When all readers have written the count into tags, tags will choose the reader which they memorize now as the holder.
(2) RFID readers detect all the tags in their interrogation zones and read their holders. The readers which lock at least one tag will be considered as non-redundant readers and keep them active. On the contrary, the readers which don’t hold any tags are seen as redundant readers.
In the first step of RRE, where each RFID reader sends a writing command to all its tags, takes (e logj) epochs. The next step, where RFID readers send query signals to each of their tags, takes (g e logj) epochs. Therefore, T (RRE) = O (g logb logj) .
Figure 3 shows an example to use RRE algorithm to eliminate the redundant readers from the RFID system network in Figure 2. First of all, the reader that covers most tags is R3, which therefore becomes active, and the tags in the interrogation zone of R3 are held by reader R3.Then, R3 is followed by the readers covering 3 tags, R1 and R4. However, due to the tags T4 and T5 already held by R3, R1 only holds T6. Similarly, R4 only holds T3. Reader R2 is the redundant reader.
2.2. Algorithm LEO
When the number of the readers and tags increases, the readers and tags in RFID system become denser and denser, and the overlap of interrogation zone becomes heavier. In this case, the reader covering more tags is more likely to become a redundant reader. However, the RRE algorithm does not take the neighboring readers into consideration. In order to overcome the shortcomings of RRE, Ching - Hsien et al proposed the LEO (Layered Elimination Optimization) algorithm . The characteristic of LEO is "first come, first served". LEO is distributed , it is unnecessary to collect all the global information to unified control. The steps of LEO are as follows: all the readers in the RFID system network broadcast queries to the tags in their interrogation zones. If any tag’s holder is empty, then the reader covering this tag will write its ID into this tag to hold it. Finally, RFID system will eliminate the readers which do not hold any tags, and see them as redundant readers. The time-complexity of LEO algorithm is O(gj) , j is the count of readers and gis the count of tags.
For instance, in Figure 2.Tags T4, T5 and T6 are held by reader R1. Then, T2 and T3 are held by R2, and R3 becomes the holder of T1. Obviously, R4 does not own any tag and therefore, R4 is a redundant reader that needs to be eliminated and the result can be seen in Figure 4.
3. Three-Step Count Based Algorithm
Algorithm TCBA (Three-step Count Based Algorithm) is designed by improving RRE and LEO.
Algorithm TCBA involves the influence of the neighboring readers while RRE and LEO don’t. In algorithm TCBA, the redundant readers will be eliminated according to the sum of the count of the neighboring readers and the count of tags covered by these neighboring readers from high to low.
3.1. Some Designations
• CC (covered count) --the number of the readers by which one certain tag is covered;
• NC (neighbor count) --the number of neighboring readers that one certain reader has;
• NCC (neighbor covering count)--the sum of NC and the tags in the interrogation zones of these neighboring readers.
(1) Every reader broadcasts a query signal to find out all the tags whose CC=1, because these tags are only covered by a unique reader, these corresponding readers are non-redundant readers (we see it as closed, but it is actually not closed), and all the tags in their interrogation zones are held by them, i.e. these readers write their ID into the tags they hold (lines 1-12);
(2) When all the readers cover the tags whose CC=1 are be found, the CC of the tags left are larger than 1.And the rest of the readers will be executed operations 3 and 4 according to the values of (NC+NCC) from high to low in turn (lines 14-17);
(3) The reader has the highest priority broadcasts first, and the CC values of the tags which in the interrogation zone of it will minus 1. Then, this reader is seen as a redundant reader (lines 18-26);
(4) Readers broadcast signals to find out the tags whose CC values are equal to 1 in operation 3, and repeat operation 1. If there is no CC value of any tag equals to 1, then repeat operation 2 (lines 23-34);
All readers broadcast a query signal, to check whether all the tags in the interrogation zones of the initial readers have holder or not. If true, elimination is over (lines 13-35).
The algorithm firstly eliminates the readers which are surely confirmed to be redundant and retain the ones that are non-redundant. After that, the eliminating and retaining operations execute in every loop to make sure the high quality of the algorithm. The time-complexity of TCBA algorithm is T(TCBA) =O(gj2),j is the number of readers and gis the number of tags.
Figure 5 illustrates an example to use TCBA algorithm to eliminate the redundant readers from the RFID system network in Figure 2. Firstly, R1 has the first priority to hold the tags (T4 and T5) in its interrogation zone, tags T4, T5 and T6 are held by reader R1 which shuts down temporarily. Next, it can be concluded that the sum of NC and NCC of reader R2 is the biggest that needs to be eliminated firstly. Then, the CC values of the tags in R2’s interrogation zone are minus 1. T1’s CC is 1 now, so tag T1 is firstly locked by reader R4, and T2, T3 are also locked by R4.
4. Simulation Experiments and Analysis
A RFID network simulation environment was designed and then compared with the classic algorithms RRE and LEO. TCBA algorithm turns out to be highly efficiency.
The following experiment data are all from the average of 3 experiments.
4.1. Experiment I
The first experiment aims to figure out the performance of different algorithms under different number of tags. Atthe invariable regional size of 1000 × 1000, randomly generating 400 readers, and their working distances are 50. The numbers of tags for experiments are 1000, 2000, 3000, 4000, 5000, 6000 and 7000 respectively. The following Figure 7 shows the comparison of results among RRE, LEO and TCBA under the condition of the above variables.
In Experiment I, TCBA algorithm can detect and eliminate the most of redundant readers all the time. When the number of tags is not very big, the performances of RRE and LEO are almost at the same level. However, with the increase of tags, the advantage of LEO is more and more obvious. The causes of the phenomenon are as follows:
Firstly, when the count of tags in the network gets larger, the probability that every reader covers at least one tag increases. With more tags covered by a certain reader, more readers might become nonredundant readers.
Secondly, the count of tags that covered by readers affects more to the performance of RRE and TCBA. RRE only takes this count as condition to judge whether the reader is the holder or not, without considering the situation that reader (named A) covers the most tags while having a large number of neighboring readers. In this circumstance, the tags in reader A may be covered by the other readers as well, which means reader A is more likely to be a redundant reader.
4.2. Experiment II
The second experiment aims to illustrate the performance of different algorithms under different number of readers. Atthe invariable regional size of 1000 × 1000, we deploy 2000 tags and thereader quantity grow from 100 to 700 and their working distance is 50. The following Figure 8 demonstrates the comparison of results among RRE, LEO and TCBA under the condition of the above variables.
As it is shown in Figure 8, the numbers of redundant readers eliminated in all three algorithms increase gradually when the number of readers deploying in this area is rising. With the growth of readers, TCBA algorithm performs more significantly than RRE and LEO. It is supposed that this tendency is caused by two main factors:
To begin with, RRE algorithm relies more on the count of tags in the system while LEO algorithm’s performance almost depends on the sequence of readers it chooses. So the number of readers has little effect on these two algorithms.
Next, TCBA algorithm involves a condition of neighbor count--when more readers come into the system, the network becomes denser and the probability of every reader with more neighbors gets larger. Therefore, an increasing number of redundant readers will be detected.
4.3. Experiment III
In thethird experiment, we attempt to dig out the performance of different algorithms under different length of working distances of RFID readers. Atthe invariable regional size of 1000 × 1000, 400 readers and 2000 tags are randomly generated. The length of radius of readers in the experiments are from 10 to 70.
In Figure 9, apparently, the tendencies of RRE, LEO and TCBA are similarin this experiment.
First, with the increase of communication distance at the beginning, the count of tags each reader covering gradually rises and the probability of a reader becoming redundant falls.
Second, when the communication distance goesup to between 20 and 30, the overlaps of readers show up and the size of these areas are getting larger and larger. Multiple readers might cover the same tags simultaneously, which causes more readers become redundant.
Third, during the dropping period, the count of neighbors has little influence on TCBA, since most of the readers do not overlap at this time. Meanwhile, the condition of tags count affects more on RRE and TCBA. Consequently, the performance of LEO is a little worse than the former two. When it comes to the stage of rising, more overlaps appear and the number of neighboring readers increase.
In this paper, we have put forward a new distributed and localized algorithm named TCBA (Three-step Count Based Algorithm) based on a conditional querying technique (CC, NC, NCC) to solve the redundant reader elimination problem in wireless RFID network system.
Our extensive simulations show that compared to LEO algorithm and RRE algorithm, the performance in redundant reader elimination of TCBA algorithm is more efficient in most of the situations.
The data of redundant reader elimination experiment we using in this paper are generated randomly by the simulated software. Although it is made close to the deployment of RFID system actual applying environment as much as possible, there is still a difference from the actual situations, which needs further testing. Meanwhile it is also necessary to consider the indoor environment and other interferential factors on the signal attenuation.