Sage Journals: Discover world-class research

Abstract

With the development of radio frequency identification technology, radio frequency identification system has been deployed in different applications in a large scale. It needs a densely deployed reader environment to cover the work area, especially in radio frequency identification logistics and warehousing applications. If the distribution area and the number of readers are not optimized, and some of them will be redundant, which will reduce the efficiency of the whole radio frequency identification system. Researchers have proposed many algorithms and optimization techniques to solve the problem of redundant readers. In this paper, the authors propose a novel redundant reader elimination algorithm, namely, L-NCD, in P2P-RFID reader network, combined with layered eliminate optimization and neighboring coverage density. The simulation results demonstrate that the proposed algorithm eliminates more redundant readers than the other methods such as redundant-reader elimination under the same conditions.

Keywords

Radio frequency identification P2P network data cleaning technology layered eliminate optimization neighboring coverage density

Introduction

Radio frequency identification (RFID) uses radio frequency signals through space coupling (alternating magnetic or electromagnetic fields) to achieve noncontact transmission of information and to achieve automatic identification via passed information. The advantage lies in that the electronic tags and readers can complete identification without contact. RFID system can be divided into three components: readers, antennas, and tags. First of all, the reader emits electronic signals through an antenna, and then the tag emits identification information of internal storage after receiving the signal. Secondly, the reader receives and identifies the information sent back from the tag via an antenna. Finally, the reader sends the identification results to the host. The working principle of RFID system is shown in Figure 1.

Figure 1.

Working principle of RFID system.

RFID technology has been widely used in supply chain or inventory management,¹ e-passports,² credit cards,³ driving licenses,⁴ vehicle system (electronic toll collection system or passive keyless enter),⁵ access cards⁶ (to buildings or parking lots or public transportation), location services,⁷ medical industry, and other fields. Especially in developed countries, such as the United States, Britain, Germany, Japan, it has a more extensive use of mature and advanced RFID system. Some major retailers have invested immensely in RFID technology, and authorized manufacturers to use tags on goods, resulting in mass production of low-cost RFID tags.⁸

In order to accurately monitor a working area, it needs dense deployments of RFID readers and tags, which can lead to unexpected consequences. In fact, when multiple readers in the same working environment communicate through a common wireless channel, a signal from a reader may produce frequency interference on other readers. This frequency interference occurs when a reader sends a communication signal to read the tag, and the communication signal interferes with other reader reading the tag. Even if the reader does not overlap the interrogation zone it will interfere with the operation of other readers. The backscatter signal from the tag is so weak that it is vulnerable to interference. Thus, frequency interference of the coverage area can cause inaccurate reading and also lengthening the reading interval. Consequently, in an RFID system, before the large-scale deployment of the reader, we should fully analyze the impact caused by interference of readers in RFID coverage area.^9,10

Extra readers in the network will consume more power, resulting in a waste of reader resources. Therefore, the elimination of redundant readers is important to optimize an RFID network deployment. RFID reader redundant deployment optimization can ensure that users use the minimum number of readers to cover a specific range of all tags. RFID reader redundancy example is shown in Figure 2. Tag T1, T2, T3, and T4 can be covered by R2, but also in the coverage area of readers R1, R3, and R4. Obviously, R2 is the minimal subset covering all tags. The reader R1, R3, and R4 are redundant readers. Although redundant readers improve the tracking accuracy, they increase the energy consumption and additional write overhead.¹¹ When multiple readers share the same perception of the area and the communication channel, a signal from a reader can interfere with other readers.¹² In addition, the redundant data generated by the redundant readers take up more computing resources to achieve the purpose of data gathering. Therefore, effective algorithm to detect and minimize redundant readers is essential to developing RFID network.

Figure 2.

Reader redundancy in an RFID system.

Technology of eliminating redundant readers has been widely used in large warehouses, production lines and large retailer areas. Some research has been done related to this issue.^13–15 In this paper, we propose an efficient algorithm L-NCD to eliminate redundant readers. Firstly, we use layered eliminate optimization (LEO) hierarchical optimization technology that eliminates most of the redundant readers. On top of that, we exclude more redundant readers according to covering domain tags assigned to the reader and the calculated weight. In addition, we compare the classical algorithms such as RRE¹³ to prove the effectiveness of the algorithm we propose. Experimental results show that the algorithm can eliminate more redundant readers, and have a higher stability compared with other algorithms.

This paper is organized as follows: the next section describes the data cleaning technology, existing redundant reader elimination technology, and P2P-RFID reader network system. Then the details of the proposed redundant reader elimination algorithm is introduced, and subsequently, simulation and experimental results are displayed. The final section sums up the paper.

Related work

Data cleaning technology

Data cleaning¹⁶ refers to a program, which can detect and correct the identifiable error in data files. RFID data have the following features:¹⁷

Temporality, dynamic, and associativity;

Semantic richness;

Inaccuracy and heterogeneity;

Flow, bulk, and mass characteristics.

In early RFID application development, the RFID data were directly sent to the application, and then the raw data were processed by applications. The current trend is to provide RFID application with middleware platform, while middleware shields the reader hardware and the upper system, shares the processing of data, and preprocesses the raw data (data cleaning). It is shown in Figure 3.

Figure 3.

The working principle of the RFID system.

Inaccuracies of the RFID raw data can result in the following three errors (from the angle of readers):¹⁸

Positive error: tag data that should not be recognized are read for some reason (noise, etc.) by readers;

Negative error: tag data that should be recognized are not read by readers;

Read redundancy: tag data are read multiple times.

There are already some classical data cleaning algorithms, such as SMURF¹⁹ (statistical smoothing for unreliable RFID data) model that combine statistical knowledge based on a sliding window to clean the tag data. Online five pipe cleaning frame ESP²⁰ does data cleaning after five stages of processing, namely point processing, smoothing processing, merge processing, decision processing, and blurring processing. RRE method¹³ is used to solve the reader redundancy. A large amount of redundant data result in increasing the energy consumption and time delay in the integration of wireless sensor networks and RFID; the data cleaning technology solves the problem of inefficiency effectively.²¹ In this paper, the RFID data redundancy issues of readers have been discussed. The reader repeatedly reads the tag data and the reader’s identification range overlapping causes a lot of redundant data in the system, thus seriously affecting the identification accuracy and efficiency of RFID systems. In the actual environment (such as inventory management), readers and tags are often very dense so the redundant data caused by tags read simultaneously by multiple readers cannot be ignored. Therefore, this paper will detail the methods of redundant reader elimination.

Redundant reader elimination technology

Following are the definitions for redundancy readers and the elimination of redundant readers:

Suppose (R, T) denotes an RFID system with R representing a collection of readers and T representing the set of corresponding tags.

Coverage (R, T) represents tag covering domain of the system.

Definition 1

(Redundant reader set): A set $R'$ of redundant readers, which is a minimal subset of $R - R'$ .

Definition 2

(The elimination of redundant readers): A process of looking for the largest subset $R'$ of the set R. For any other reader redundant subset $R ″$ satisfies $| R' | \geq | R ″ |$ .

Over the past few years, researchers have done extensive research on RFID collision, among which the most important issue is the signal collision. Signal collision is divided into two categories: tag signal collision and reader signal collision. RFID systems often use SDMA (space division multiple access), FDMA (the frequency domain multiple access), and TDMA (the time domain multiple access) to solve the problem of collisions, such as slotted ALOHA²² based on ALOHA algorithm. For RFID anti-collision problems, Cha and Kim,²³ Huang and Le,²⁴ and Liu and Lai²⁵ proposed an improved ALOHA algorithm; Waldrop et al.²⁶ proposed a theory of color wave algorithm based on TDMA; Guo and Hu²⁷ and Liu et al.²⁸ proposed using TDMA-based tag identification code. These algorithms are based on Manchester coding, which is similar to a binary search. The maximum weight independent set-based algorithm (MWISBA) is used to solve the signal collision of readers.²⁹ Simulated annealing particle swarm algorithm (SA-PSO) is for the integration optimization of multi-objective.³⁰ The plant growth simulation algorithm (PGSA) proposed a k-coverage model to optimize the RFID network by reducing the best adjustment parameters.³¹

Another way to solve the anti-collision problems is to reduce the number of redundancy readers in RFID network. This approach not only increases the effectiveness of RFID systems, but also saves power consumed by redundancy readers. RRE algorithm¹³ and LEO algorithm¹⁴ are the most representative algorithms of the method. Huang and Lv³² put forward a middleware-based redundant reader elimination (MRRE)-based EPC network architecture; the algorithm utilizing tag information in the RFID middleware does not need to write-to-tag operation.³² Gong et al.³³ proposed a practical algorithm of redundant reader elimination based on swarm optimization algorithm to optimize RFID network planning. Hsu et al.³⁴ proposed a technique based on the overlap-aware technique to eliminate redundant readers. Pan et al.³⁵ proposed an efficient count-based algorithm (CBA), where the algorithm is based on the number of readers covering itself and changed its record continuously; the algorithm was determined to exclude redundant readers, which is determined to be redundant firstly. SCBA algorithm improves the CBA and inherits the advantages of RRE algorithms. While it eliminates more redundant readers, the constantly rewriting the record led to the increasingly write-to-tag operations.³⁶ Jedda et al.³⁷ proposed the two deterministic decentralized RFID coverage algorithms OB-COVERAGE and IOB-COVERAGE; these two algorithms use only the communication between every two readers. The former is a local distributed algorithm running in a single round of communication, while the latter needs to run in O (n) rounds, where n is the number of readers in the network. The authors³⁸ proposed an algorithm based on the communication of information between the readers. Mahdin et al.³⁹ proposed a simple and effective method to eliminate redundant readers, which can save energy and reduce interference in a high-density RFID reader network. The relevant algorithms will be discussed in the following.

RRE algorithm is a greedy algorithm; the main idea is to record the “tag number” that the maximum number of tags a reader can cover. The reader having the maximum number of tags will become the holder of the corresponding tag. Repeat the above steps until all the tags have corresponding readers in the network. In the end, if there is no tag assigned to a reader, it will be eliminated as a redundant reader. Hsu et al.¹⁴ pointed out that RRE algorithm is difficult to eliminate redundant readers in some RFID network topologies, and to deal with it, they proposed the LEO algorithm using a layered approach. The main idea of the algorithm is “first read first own” and all readers send requests to the tags within their coverages to obtain records of tags. The first reader that sends a quest to the tag will become the holder of the tag. If the tag already has other reader’s ID, the ID cannot be changed. Finally, the readers are eliminated if they have no tags. NCD algorithm is first based on the NCD (neighboring coverage density) method, which is aimed at problems of eliminating redundant readers. Some definitions are made as follows:

Definition 3

(Neighboring reader): Let the read range radius of a reader is M, if the distance between reader $R_{i} and R_{j}$ ( $R_{i}, R_{j} \in R$ ) l < 2M, then $R_{i} and R_{j}$ are called neighboring readers.

Definition 4

(Neighboring coverage density): Suppose that ${R_{i 1}, R_{i 2}, \dots, R_{in}}$ is a set of neighboring readers, then D_i = $\sum {no}_{j = 1}^{n} Coverage (R_{ij})$ is called neighboring coverage density of R_i.

Definition 5

(Weight of the reader): Suppose that ${R_{i 1}, R_{i 2}, \dots, R_{in}}$ is a set of neighboring readers of R_i, the weight of the reader R_i is $W_{i} = \frac{Coverage (R_{i})}{D_{i}}$ .

For example, in Figure 2, readers R₂ and R₁ cover the same tag T₁, so they are mutually neighboring readers. Similarly, R₂ is adjacent to $R_{3}, R_{4}$ .

NCD algorithm is divided into four steps:

Step 1: Each reader queries its own neighboring readers to calculate its tag coverage, and writes the reader s ID into all the coverage lists of tags it covers.

Step 2: According to the coverage list and according to the Definition 5, calculate the weight of the reader.

Step 3: All readers will write the command containing their reader ID and weight into tags they cover. Each tag chooses a holder, which has the largest weight in its neighboring areas.

Step 4: Each reader inquiries each of its covered tags and reads the selection of tag s holder. A reader having no tags will be eliminated as a redundant reader.

P2P-RFID reader network system

The redundancy elimination algorithm for the reader proposed in this paper is based on the P2P-RFID network system. It needs to have the ability to communicate with each other between readers; therefore, the following is the introduction of P2P-RFID reader network.

P2P (peer-to-peer) network is a distributed network of the application layer on the IP network, participants in the network i.e. peers share a portion of the hardware resources (such as processing power, storage capacity, network connectivity, etc.)⁴⁰ that they have. P2P-RFID reader network system⁴¹ is a new way of P2P-based RFID reader network systems. The operation exchanging tag information among the readers is asynchronous, because there is no restriction of the readers. The P2P-RFID reader network takes advantage of P2P technology, which can work in client and server mode. Embed ZigBee (ZigBee is a short-range, low-power wireless communication technology based on the IEEE802.15.4 standard) technology in the reader, compose P2P network between them, and they can communicate with each other, because the Zigbee technology is embedded in P2P-RFID reader, while its maximum transmission rate is 250 Kbps. P2P-RFID reader can act as a relay node between P2P-RFID reader server and tag when it works for the client mode. This can largely extend the reading distance between reader and tag and improve the recognition speed when tackling multiple tags. In addition, when P2P-RFID reader is in the client mode, it reads the information of RFID tags and storages it to its memory. Then it is convenient for the other neighboring readers to get the information from this reader via getting its memory. The P2P-RFID reader reads other readers tags information into its memory when working in server mode, which increasing the protocol complexity of reading the tags, so we need to put forward an effective agreement to solve the problem.

P2P-RFID reader network architecture proposed in Xu et al.⁴¹ is shown in Figure 4.

Figure 4.

P2P-based RFID reader network system.

A novel algorithm L-NCD for redundant reader elimination

L-NCD algorithm

LEO is applied for high-density wireless RFID network as a distributed optimization technology of wireless RFID network¹⁴; it can eliminate most of the redundant readers, and greatly reduce the “write-to-tag” operation, but LEO relies on the RFID reader query sequence. The result is different when the query sequence is different. NCD algorithm improves the accuracy with regard to other distributed algorithms, but the calculation is more complicated, so it does not apply to RFID network in high-density environments. This paper combines the advantages of LEO and NCD algorithm, and proposes a comprehensive data cleaning algorithm in an environment of high-density readers. For the convenience of discussion, we make the following assumptions:

The covering domain tag of the reader is known in advance.

The reader of the algorithm proposed in this paper belongs to P2P-RFID reader to determine whether the two readers are neighboring readers.

A flag(tag) is added and used to record the number of tags in reader R_i. Each time it reads a tag, and then does an increment operation to the tag. If the value does not change in a certain period of time, then the reader completes its interrogation of tags.

The query-response process of the reader (i = 1… n, the algorithm will be executed in parallel for n times, n is the total number of reader, total number of tag T is m) is shown in Figure 5.

Step 1: Reader broadcasts an “inquiry message “(Do you have a holder?) to the tags in the coverage domain to ask whether the tag has a “holder”.

Step 2: Tags in the coverage domain of R_i reply to R_i, $holder = {„ NULL ” „ R_{k} ”$ (R_kis a reader in the RFID network).

Step 3: If tag’s holder = “NULL”, reader R_i will write its ID to the tag, i.e. tag’s holder = R_i; else if holder = $„ R_{k} ”$ , and $R_{k} \neq R_{i}$ , then R_i will ignore this reply.

Step 4: If there is no NULL in all the replies of tags in the coverage domain of the reader, then R_i will be eliminated as a redundant reader (i.e. exist = NO), and end this query-response process; Otherwise, exist = YES (exist is the mark of whether the reader exists). If exist = YES in reader R_i, then go to step 5.

Step 5: Reader R_i broadcasts a “query message” to query the neighboring reader R_j (j = 1…n, n is the number of neighboring readers of R_i).

Step 6: Reader R_i’s neighboring reader R_j replies the tag value (The value is a mark of a reader to record the number of tags in its coverage domain).

Figure 5.

Query-response process of the reader.

The above is the entire query response process of the reader R_i and the neighboring reader and the tag. After the end of the process, R_i calculates the neighboring coverage density D_i and weight W_i according to Definitions 4 and 5. If the neighboring coverage density D_j of reader R_j is 0 and the number of the coverage domain tag T_j is not 0, then reader R_j must not be a redundant reader. List the weight comparing chart (see corresponding examples in Figures 6 and 7) of reader R_i (i = 1…n, n is the remaining number of eliminated redundant readers and R_j) and tag T_i (i = 1…m, m is the number of tags, $T_{i} \neq T_{j}$ ); T_i chooses the reader that has the largest weight to be its “holder”; finally, the readers that are not chosen by any tag are redundant readers.

Figure 6.

Example one of the redundant reader.

Figure 7.

Example two of the redundant reader.

The pseudo code for L-NCD is shown below.

1: Program L-NCD

2: input(σ) //σ refers to a random RFID network

3: for each reader $R_{i} \in R$

4: R_i. c overedt ags = the set of tags covered by R_i

5: for each $T_{i} \in R_{i}$ .CoveredTags

6: T_i .holder = the reader covering T_i

7: if(T_i. holder ==NULL)then

8: T_i. holder = R_i

9: R_i. exist = true ‘R_i is not redundant reader

10: else $if T_{i}$ . holder ! = NULL

11: break

12: endif

13: end

14: end

15: for each reader $R_{j} \in R_{i}$

16: ncd = the neighboring coverage density of R_j

17: If( ncd! = 0)

18: R_j. weight = R_j. coveredtags / ncd

19: endif

20: If( ncd ==0&R_j. coveredtags !=NULL)

21: R_j. exist =true ‘R_j is not redundant reader

22: endif

23: end

24: for each $R_{k} \in R_{j}$

25: for each $T_{j} \in R_{k}$ . coveredtags

26 $T_{j} . holder = R_{k} owing the largest weight$

27: end

28: end

29: holders =the set of optimal readers

30: for each $T_{j} \in T$

31: if( $holders don' t contain T_{j} . holder$ )

32: holders .add( $T_{j} . holder$ )

33: endif

34: end

35: output( $σ, holders$ )

36: end L-NCD

Example analysis

As shown in Figure 6, the example one of the redundant reader, first reader R₁ writes its ID (R₁) to tag

T_{1}, T_{2}, T_{3}

; since all tags

T_{1}, T_{2}, T_{3}

have “holders”,

R_{2}, R_{3}, R_{4}, R_{5}

do not need the operation of “write to tag”. As shown in Table 1,

R_{2}, R_{3}, R_{4}, R_{5}

are redundant readers. Then the algorithm is over.

Table 1.

Reader tag comparison table corresponding to the example one.

	T ₁	T ₂	T ₃
R ₁	R ₁	R ₁	R ₁
R ₂
R ₃
R ₄
R ₅
Results	R ₁	R ₁	R ₁
Redundant readers	$R_{2}, R_{3}, R_{4}, R_{5}$

One more example is shown in Figure 7: R₁ writes ID (R₁) to

T_{1}, T_{2}

, then R₂ writes ID (R₂) to T₃; since T₃ has already had a “holder”, R₃ only writes ID (R₃) to T₄, because the coverage domain tags of R₄ are

T_{2}, T_{3}

, but

T_{2}, T_{3}

have “holders” (

R_{1}, R_{3}

), R₄ does not need operation of “write to tag”. As shown in Table 2, R₄ is a redundant reader. The results of the procedure are shown in Figure 8. And the neighboring coverage density of R₁ is 0, and the coverage domain tag is not 0, so R₁ must not be a redundant reader. Next,

R_{2}, R_{3}

calculate the neighboring coverage density and weight.

D_{2} = \sum_{j = 1}^{n} Coverage (R_{2 j}) = Coverage (R_{23}) = 2

D_{3} = \sum_{j = 1}^{n} Coverage (R_{3 j}) = Coverage (R_{32}) = 1 W_{2} = \frac{Coverage (R_{2})}{D_{2}} = \frac{1}{2} W_{3} = \frac{Coverage (R_{3})}{D_{3}} = \frac{2}{1} = 2

Table 2.

Reader tag comparison table corresponding to the example two.

	T ₁	T ₂	T ₃	T ₄
R ₁	R ₁	R ₁
R ₂			R ₂
R ₃				R ₃
R ₄
Results	R ₁	R ₁	R ₂	R ₃
Redundant readers	R ₄

Figure 8.

Results of Figure I of example two.

The weights are listed in comparison Table 3, and we can obtain the redundant reader R₂. In summary,

R_{2}, R_{4}

are redundant readers. The final result is shown in Figure 9.

Table 3.

Weight comparison table corresponding to example two.

	T ₃	T ₄
R ₂	( $R_{2},$ 1/2)
R ₃	( $R_{3}, 2$ )	( $R_{3}, 2$ )
Results	( $R_{3}, 2$ )	( $R_{3}, 2$ )
Redundant readers	R ₂

Figure 9.

Results of Figure II of example two.

Complexity analysis

We assume that the number of readers is θ and τ be the number of tags; Carbunar et al.¹³ have proved the complexity of the RRE algorithm is O (τ logθ). Each tag of LEO algorithm is read only once, and the complexity is associated with the number of tags and linear, as O (τ). Obviously, the complexity of LEO + RRE is between the former two. Liu et al.²⁹ demonstrated that the number of time frames per epoch is set to the number of readers θ and the complexity of NCD is O(τlogθ). The best case of L-NCD algorithm is that all redundant readers are excluded in the first phase, and the complexity is O (τ); the worst case is that no redundancy reader is excluded in the first stage, and the time complexity is O (τlogθ) which is the same as NCD. Obviously, this does not occur at the worst scenario, because most of the redundant readers can be excluded in the first phase.¹⁴ The complexity of algorithms is shown in Table 4.

Table 4.

Complexity of the redundant reader elimination algorithms.

Algorithm	RRE	LEO	LEO+RRE	NCD	L-NCD
Complexity	$O (τ \log θ)$	$O (τ)$	$O (τ \log θ)$ < $ɛ$ < $O (τ)$	$O (τ \log θ)$	$O (τ \log θ)$ < $ɛ$ < $O (τ)$

Note: ɛ indicates the corresponding algorithm’s complexity.

Simulations and conclusions

Settings of simulation

Whether an algorithm is efficient or not depends on whether it can detect the greatest number of redundant readers and a least number of “write in tag” operations. In order to evaluate the performance of the algorithm, we first have to simulate a random and different sized RFID network. The simulator produces different characteristics of the network topology using the number of readers, the number of tags, and the radius of readers. In the experiment, we compare RRE, LEO, LEO + RRE, NCD and the proposed algorithm L-NCD. We use java to implement a random RFID network simulator to evaluate the algorithm performance. The simulator generates a random RFID network using working area size, the reader detection radius, the number of readers, and the number of tags. Shown in Figure 10 is a 50 × 50 (square meters) randomly generated RFID network topology. The experimental hardware and software environment is:

(1) hardware environment

PC: HP WIN7-20150414FZ, 2.33GHZ CPU frequency, 2GB memory;

(2) software environment

programming language: Java, JDK version jdk1.8.0_40;

Programming environment: Eclipse IDE for Java Developers, version Luna Service Release 2 (4.4.2).

The simulator is coded in java language, the simulation results are shown in matlab, and the results show the number of redundant readers detected.

Experiment 1: The work area is 50 × 50 (square meters), the reader detection radius is a constant 5 (meters), the number of readers is 200, the number of tags is 500–4500, and the results show the number of redundant readers detected.

Experiment 2: The work area is 50 × 50 (square meters), the number of readers is 200, the number of tag is 4500, the reader detection radius is 5–10 (meters), and the results show the number of redundant readers detected.

Experiment 3: The work area is 50 × 50 (square meters), the number of readers is 200, the number of tags is 500, the reader detection radius is 5 (meters), each algorithm is executed 10 times and the results show the number of redundant readers detected, in order to evaluate the stability of each algorithm.

Figure 10.

RFID network topology.

Results and discussion

In experiment 1, when the reader’s detection radius is a constant and the number of RFID tags is variable, compare and evaluate the number of redundant readers detected by these algorithms. Each algorithm is run under different random RFID network simulation environments for an average of 10 times. Because LEO is an independent algorithm optimization technology, it can be executed independently or combined with other algorithms to improve the performance of the algorithm. The neighboring coverage density technology also has a high accuracy rate and the L-NCD algorithm combines the advantages of both technologies; therefore, the performance of the algorithm has been greatly improved. Figure 11 describes the relationship between the redundant readers and the number of tags, and shows the number of redundant readers detected by different algorithms in this experiment. It is obvious that the L-NCD algorithm proposed in the article paper a better performance compared to RRE, LEO, LEO + RRE and NCD, i.e., under the same conditions more redundant readers can be detected (Up to 67.9%). When the number of tags is greater than 4500, the number of redundant readers detected by L-NCD algorithm is 22.3% greater than the RRE algorithm, 10.45% greater than the LEO algorithm, 4.2% greater than the LEO+RRE algorithm, and 10.05% greater than the NCD algorithm.

Figure 11

Comparison of the number of redundant readers detected when the number of tags change.

In experiment 2, when the reader’s detection radius is a variate, compare and evaluate the number of redundant readers detected by these algorithms. Figure 12 shows that L-NCD algorithm can detect more redundant readers under the same conditions (up to 84.6%). When the reader radius is 5 m, the number of redundant readers detected by the L-NCD algorithm is greater than that detected by the RRE, LEO, LEO+RRE, NCD algorithms – by 20.6%, 8.35%, 4.25%, 10.6%, respectively.

Figure 12.

Comparison of the number of redundant readers detected when the detection radius changes.

In experiment 3, when each experimental parameter is a constant, and each algorithm is executed 10 times, compare the number of redundant readers detected by each algorithm to evaluate the stability of each algorithm. Stability shows the reliability of an algorithm; low-stability algorithm may cause results to vary significantly. The results in Figure 13 show that the L-NCD algorithm proposed in this paper has a better stability compared to other existing algorithms.

Figure 13.

Comparison of stability.

In addition, the redundant reader elimination algorithm proposed in this paper is based on the P2P-RFID network system, and it requires the ability to communicate with each other between the readers. Therefore, for the reader’s “read the tag” operation, this algorithm has absolute advantages compared with other algorithms, and each reader only requires reading all the neighboring readers once, to obtain all of its required tag information.

Conclusion

In this paper, the authors propose a reader-redundant elimination algorithm under a high-density environment based on NCD algorithm. The algorithm is based on the P2P-RFID reader network environment where readers can communicate with each other directly via using P2P technology. It can obtain the tags’ information in neighboring readers’ coverage domain directly, and therefore can greatly reduce the reader’s “read the tag” operation. In order to evaluate the performance of L-NCD, we implement random RFID network simulator, and compare it with other classical algorithms such as RRE, etc. The number of redundant readers that each algorithm can detect are compared under the same conditions in the case of tags and reader s detection radius as variables. In addition, the results show that under a high-dense environment, the L-NCD algorithm can detect more redundant readers under the same conditions compared to other algorithms (up to 84.6%), and the stability of the algorithm is better than the other existing algorithms.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is financially supported by the National Natural Science Foundation of PR China (No. 61373017, No. 61572260, No. 61572261, No. 61672296, No. 61602261), the Natural Science Foundation of Jiangsu Province (No. BK20140886, No. BK20140888), Scientific & Technological Support Project of Jiangsu Province (No. BE2015702, BE2016185, No. BE2016777), Natural Science Key Fund for Colleges and Universities in Jiangsu Province (No. 12KJA520002), China Postdoctoral Science Foundation (No. 2014M551636, No. 2014M561696), Jiangsu Planned Projects for Postdoctoral Research Funds (No. 1302090B, No. 1401005B), Natural Science Foundation of the Jiangsu Higher Education Institutions of China (No. 14KJB520030), Jiangsu Postgraduate Scientific Research and Innovation Projects (SJLX15_0381, SJLX16_0326), Project of Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks(WSNLBZY201509), and NUPTSF(No. NY214060, No. NY214061).

References

Chen

Cheng

Huang

. Supply chain management with lean production and RFID application: A case study. Expert Syst Appl 2013; 9: 3389–3397.

Kundra S, Dureja A and Bhatnagar R. The study of recent technologies used in E-passport system. In: 2014 IEEE global humanitarian technology conference-South Asia Satellite (GHTC-SAS), Trivandrum, Kerala, India, 26–27 September, 2014, pp. 141–146.

Zhu

Chen

Wang

. Consumer’s acceptance of high-tech products: The case of RFID credit cards in Taiwan. Int J Technol Market 2013; 2: 139–144.

Agarwal M, Sharma M and Singh B. Smart ration card using RFID and GSM technique. In: 2014 5th international conference on the next generation information technology summit, Uttar Pradesh, Noida, India, 25–26 September, 2014, pp. 485–489.

Jagtap

Barge

. Toll collection and stolen vehicle detection using RFID. Int Eng Res J 2015; 2: 36–39.

Shu

Chen

. Dynamic authentication with sensory information for the access control systems. IEEE Trans Parallel Distribut Syst 2014; 2: 427–436.

Montaser

Moselhi

. RFID indoor location identification for construction projects. Autom Constr 2014; 2: 167–179.

Sarma S. Towards the five-cent tag. Technical Report MITAUTOID-WH-006, MIT Auto ID Center, 2001.

Engels DW. The reader collision problem. White Paper MIT-AUTOID-WH-007, MIT Auto ID Center, November 2001.

10.

Kim D-Y, Jang B-J, Yoon H-G, et al. Effects of reader interference on the RFID interrogation range. In: Proceedings of the 37th European microwave conference, Munich, Germany, 8–12 October 2007, pp. 728–731.

11.

lrfan N and Yagoub MCE. Efficient approach for redundant reader elimination in large-scale RFID networks. In: 2010 first international conference on integrated intelligent computing, Bangalore, India, 5–7 August 2010, pp. l02–107.

12.

Engels DW. The reader collision problem. White Paper M1T-AUT01O-WH-007, MIT Auto 10 Center, 2001.

13.

Carbunar B, Ramanathan MK, Koyuturk M, et al. Redundant-reader elimination in RFID systems. In: Second annual IEEE communications society conference on sensor and ad hoc communications and networks (SECON), California, USA, 26–29 September 2005, pp. 176–184.

14.

Hsu C-H, Chen Y-M and Yang C-T. A layered optimization approach for redundant reader elimination in wireless RFID networks. In: IEEE Asia-Pacific services computing conference, Tsukuba Science City, Japan, 11–14 December 2007, pp. 138–145.

15.

Yu K-M, Chang WY and Lin Z-Y. A density-based algorithm for redundant reader elimination in a RFID network. In: Proceedings of the second international conference on future generation communication and networking, Hainan Island, China, 13–15 December 2008, pp. 89–92.

16.

Guo

Zhou

. Data quality and data cleaning research. J Software 2002; 13: 2076–2082.

17.

Zhang

. RFID complex event processing technology. Comput Sci Explor 2017; 1: 255–267.

18.

Juels

Pappu

. Squealing Euros: Privacy protection in RFID-enabled banknotes. In: Financial cryptography, Berlin Heidelberg: Springer, 2003, pp. 103–121.

19.

Jeffery SR, Garofalakis M and Franklin MJ. Adaptive cleaning for RFID data streams. Adaptive cleaning for RFID Data Streams – Research Gate, 2006, pp. 163–174.

20.

Jeffery SR, Alonso G, Franklin MJ, et al. A pipelined framework for online cleaning of sensor data streams. In: Proceedings of the 22nd international conference on data engineering. Washington DC: IEEE Computer Society, 2006, p. 140.

21.

Wang

Da Xu

. Data cleaning for RFID and WSN integration. IEEE Trans Ind Inform 2014; 10: 408–418.

22.

Lee S-R, Joo S-D and Lee C-W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification. In: The second annual international conference on networking and services, San Diego, California, USA, 17–21 July, 2005, pp. 166–172.

23.

Cha J-R and Kim J-H. Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system. In: Consumer communications and networking conference, Las Vegas, Nevada, USA, 8–10 January, 2006, pp. 768–772.

24.

Huang X and Le S. Efficient dynamic framed slotted ALOHA for RFID passive tags. In: The 9th international conference on advanced communication technology, Phoenix Park, Korea, 12–14 February 2007, pp. 94–97.

25.

Liu L and Lai S. ALOHA-based AntiCollision algorithms used in RFID system. In: International conference on wireless communications, networking and mobile computing, Wuhan, China, 22–24 September 2006, pp. 1–4.

26.

Waldrop J, Engels DW and Sarma SE. Colorwave: An anticollision algorithm for the reader collision problem. In: IEEE international conference on communications, Alaska, USA,11–15 May 2003, pp. 1206–1210.

27.

Guo ZM and Hu BJ. A dynamic bit arbitration anti-collision algorithm for RFID system. In: IEEE international workshop on anticounterfeiting, security and identification, Xiamen, China, 16–18 April 2007, pp. 457–460.

28.

Liu L, Xie ZH, Xi JT, et al. An improved anti-collision algorithm in RFID system. In: 2nd international conference on mobile technology, applications and systems, Guangzhou, China, 15–17 November 2005.

29.

Liu

Nguyen

Pham

. A maximum-weight-independent-set-based algorithm for reader-coverage collision avoidance arrangement in RFID networks. IEEE Sens J 2016; 16: 1342–1350.

30.

Tao

Huang

. SA-PSO based optimizing reader deployment in large-scale RFID systems. J Network Comput Appl 2015; 52: 90–100.

31.

. A fuzzy k-coverage approach for RFID network planning using plant growth simulation algorithm. J Network Comput Appl 2014; 39: 280–291.

32.

Huang

. A middleware-based approach for redundant reader elimination. In: Information science and service science, New York: IEEE, 2011, pp. 209–214.

33.

Gong

Shen

Zhang

. Optimizing RFID network planning by using a particle swarm optimization algorithm with redundant reader elimination. IEEE Trans Ind Inform 2012; 8: 900–912.

34.

Hsu CH, Yu CH, Chung CY, et al. An overlap aware technique for redundant reader elimination. In: International conference on ubiquitous intelligence & computing and, international conference on autonomic & trusted computing, 2012, pp. 357–360. New York: IEEE.

35.

Pan S and Yang Z. A count based algorithm for redundant reader elimination in RFID application system. In: International conference on intelligent system design & engineering applications, Hong Kong, China, 16–18 January 2013, pp. 30–33.

36.

Wei

Zhi

. An efficient algorithm for redundant reader elimination in RFID network system. Mod Comput 2015; 6: 36–41.

37.

Jedda

Mouftah

. Decentralized RFID coverage algorithms with applications for the reader collision avoidance problem. IEEE Trans Emerg Topics Comput 2015, pp. 1–1.

38.

Gao

Wang

. Method of reduction the redundant reader based on RFID reader communication protocol. Adv Sci Technol Lett 2014; 79: 124–128.

39.

Mahdin

Fudzee

Farhan

. Redundant readers elimination in dense radio frequency identification network. Sens Lett 2015; 13: 992–997.

40.

Zhang

. A comprehensive analysis of the P2P technology, Beijing: People’s Posts and Telecommunications Press, 2010.

41.

Wang

. A novel RFID reader system framework based on peer-to-peer network. Int J Adv Comput Technol 2011; 3: 104–110.

A novel algorithm L-NCD for redundant reader elimination in P2P-RFID network

Abstract

Keywords

Introduction

Related work

Data cleaning technology

Redundant reader elimination technology

Definition 1

Definition 2

Definition 3

Definition 4

Definition 5

P2P-RFID reader network system

A novel algorithm L-NCD for redundant reader elimination

L-NCD algorithm

Example analysis

Complexity analysis

Simulations and conclusions

Settings of simulation

Results and discussion

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References