1 Introduction

The radio frequency identification (RFID) is an automatic technology aids machines or computers to identify, record, or control individual target through radio waves. An RFID system includes two components, RFID reader and RFID tag. The electronics in the RFID reader use an outside power resource to generate signal to drives the reader’s antenna and turn into radio wave. The radio wave will be received by RFID tag which will reflect the energy in the way of signaling its identification and other related information. To access the reflection, the RFID reader works as a receiver on sensing and decoding the signal to identify the tag. In simple RFID system, RFID tag is passive and powered by energy of the reader’s signals. In some matured system, the reader’s RF can also instruct the memory to be read or write from which the tag contained.

In many applications, such as supply chain automation, identification of products at check-out points, security, and access control, have been developed to take the primary function of RFID systems. Advantages of RFID technologies, such as price efficiency and accuracy of stock management also broaden the scope of applications of RFID systems. Similar to wireless sensor network, RFID tags can be deployed in an ad hoc fashion instead of pre-installed statically. It is motivated in recent RFID technologies that an RFID system can be integrated with wireless sensor network by interfacing RFID tags with external sensing capabilities, such as light, temperature, or shock sensors. In such way, the hybrid infrastructure combines advantages of both techniques, such as accurate identification, monitoring of objects, and efficient deployment. Furthermore, some advanced characteristics of recent RFID readers, like size miniaturization and capabilities of Wi-Fi or cellular also motivate the development of large scale and high density RFID systems.

In such environments, it will be necessary to install several RFID readers at appropriate distance from each other. Otherwise RFID readers would interfere with each other. The interference could be caused when the frequency band is shared with other potential users. As an RFID reader is designed to accept the tiny signal reflected from a tag, it will be particularly influenced to any relatively powerful transmissions from other readers that happen at the same time, which is usually referred as reader collision problems [7].

In order to prevent the mutual interference among readers, there are possible reactions; the distributed control mode means RFID readers switch the communication state with each other through self-scheduling. The centralized control mode means appropriate coordination is handled by a head readers among others. In this paper, we present a two-phase scheduling technique toward contention free communications in wireless and dynamic RFID networks. The two phase dynamic modulation (TPDM) scheduling technique consists of regional scheduling and hidden terminal scheduling phases. In the first phase, RFID readers communicate with each other through control channel competing as the candidacy locally for transactions with RFID tag in the global space. In the second phase, RFID readers will communicate with tags through data channel [12] based on hidden terminal scheduling. One of the significant improvements of this approach is that TPDM can prevent reader collisions caused either by simultaneous transmissions in reader’s vicinity or by hidden terminal [5, 21]. The TPDM method is adaptive and applicable in both static and dynamic RFID environments. The low algorithmic complexity is also an advantage of the proposed technique which leads TPDM easy to implement.

To evaluate performance of the proposed technique, we have implemented a simulator with random graph generator. Experimental results demonstrate that TPDM provides superior performance in terms of system throughput and has stable performance in arbitrary RFID networks.

The rest of this paper is organized as follows. In Sect. 2, a brief survey of related work will be presented. In Sect. 3, we introduce the hidden terminal problem, reader collision problem, and terminologies used in this paper. The two-phase dynamic modulation scheduling technique will be presented in Sect. 4. Performance evaluations will be given in Sect. 5. Section 6 concludes this paper.

2 Related work

2.1 Multiple access mechanisms

Many research efforts for collision avoidance have been presented in the literature. Frequency division multiple access (FDMA), code division multiple access (CDMA), time division multiple access (TDMA) [1], and carrier sense multiple access (CSMA) are four basic access methods to categorize MAC-layer protocols.

FDMA is functioned via frequency assignment in which the communication is applied in form of many-to-one. Since RFID tags without a frequency tuning circuitry, reader selection is not allowed during communication. Therefore, the addition of such a tuning circuitry will increase the cost of the RFID tags and deployment of RFID systems. CDMA uses spectrum modulation techniques that are based on pseudo random codes for data transmission. It is more complicated and computation intensive due to additional circuitry to the tags which also brings up the cost of tags. TDMA uses time slot to avoid collision and clock synchronization to complement each other. Because there is only one code transmitted during each slot, it allows readers to communicate using different time slot which successfully avoid the collision. To accommodate better read rate in dynamic RFID system, time slot should be reshuffled adaptively. CSMA enables individual data transmission by detecting whether the medium is busy. Collision avoidance and collision detection are two common types defined in CSMA. For hidden terminal problems in RFID networks, the interference at the tags’ communication remains as readers may not be in other’s sensing range. Thus, CSMA is not able to avoid collisions caused by hidden terminal in RFID networks.

2.2 Collision avoidance mechanisms

Standard collision avoidance protocols like RTS-CTS [17] cannot be directly applied to RFID systems due to the following reason: in the traditional wireless networks the CTS are sent back to the sender. Similar situation in RFID system occurs, when a reader broadcasts an RTS, all tags in the read range need to send back CTS to the reader. It then requires another collision avoidance mechanism for CTS, and it will make the protocol more complicated.

Techniques for resolving RFID reader collision problems are usually proposed as reader anti-collision techniques or tag anti-collision solutions [4]. The redundant reader detection [3, 10] or elimination is another kind of approach for mitigating reader collision problems. Tanaka et al. [18] presented a linear programming formulation method to obtain communication probability of the readers for a given reader deployment scenario. They also propose two algorithms based on the detect-and-abort principle for mitigating the reader-to-tag as well as the reader-to-reader interference in dense reader environments.

The Colorwave [19] is a scheduling-based approach prevents RFID readers from simultaneously transmitting signal to a RFID tag. The Colorwave is used as a distributed anti-collision system based on TDMA in RFID network. In Colorwave, RFID network is modeled as an undirected graph. Vertices are used to represent readers, and the edges represent collision constraints. When two readers are connected with an edge and transmitting data at the same time, collision occurred. The Colorwave is to address RFID network with graph coloring theory and accomplishing each reader has the smallest possible number of adjacent nodes in the same color. This approach makes easy reservation of time slots for collision-free transmission of data (i.e., reader–tag communication). A reader will transmit only in its color (time slot) and if the transmission collides with another reader, the transmission request is discarded. Furthermore, the reader will choose a new color randomly and reserve it. This cause will force its neighbors to select a new color. The Colorwave protocol attempts to optimize the graph to achieve a percentage of successful transmissions. However, there are still some limitations, such as colors are selected randomly, there is no information given on how the network is built up. The given feedback from the percentage of successful transmissions is used to regulate the parameters. However this will not ensure the system stays in a stable condition. The maximum number of colors in the network will not be the same in all readers. As the ratio of collisions of all regional readers exceeds a safe threshold, the “kick wave” will be caused by readers and then the value of maximum colors could be changed. In mobile environment, the reader stays in and out in which the behavior causes the whole topology a dynamic change. This leads to the reformation of time slot and therefore decrease system throughput. Furthermore, synchronization is required by readers in communicating state of time slot. The collision might have also happed because of limited broadcast range makes the reader incapable of knowing other existing readers, i.e., hidden terminal problems.

Pulse protocol [2] is referred as beacon broadcast and CSMA mechanism [20]. A “beacon” is sent by readers periodically in separated control channels during communication with tags. The contend_back-off and the delay_before_beaconing [14, 15] in the protocol are similar in wireless networks. If the reader receives a beacon, the residual back-off timer will be stored and kept till the next coming chance. This process is expected to achieve the fairness among all readers.

Communications among readers in the Pulse protocol is achieved through control channel which is a sub-band in the RFID spectrum separated from reader-tag communication. The data channel is for reader–tag communication while the control channel is for reader–reader communication. The transmission in the control channel cannot affect the communication in the data channel. It is assumed that the reader is able to receive on both the control and the data channel simultaneously. In [2], the beacon range factor (BRF) is defined as the ratio of the control channel transmission power to the data channel transmission power. The Pulse protocol was examined and shown effectiveness by adjusting the control channel power to cover reader range in solving reader collision problems.

A coverage-based RFID reader anti-collision mechanism was proposed in [13]. Kim et al. presented a localized clustering coverage protocol for solving reader collision problems occurring among homogeneous RFID readers. However, this technique is not applicable in dynamic RFID environments. ETSI EN 302 208 [8] is an on-going developing standard designed for RFID readers. A specified time period is set, for the reader’s first listen on the data channel for any on-going communication. If the channel is idle during the time, the tag will be read. If the channel is busy, a back-off is chosen randomly. When there is no sensing signal among readers, a hidden terminal problem may still happen.

The Class-1 Generation 2 UHF standard [6] separates the reader transmissions and the tag transmissions spectrally such that collisions between tags or readers are not affecting each other. Such separation solves the interference between readers since the transmissions of readers and tags are in separate frequency channels. Because tags do not have frequency option, when two readers using separate frequency communicate with the tag simultaneously, the tag is unable to tune to a particular frequency and a collision occurred to tags. Thus interference between readers and tags still exists.

HiQ [9], an online learning algorithm, is used to find dynamic solutions to the reader collision problem in RFID systems. The focus of the HiQ algorithm contains two parts: first, HiQ is used to allocate resources to maximize the number of readers communicating at a single time period; secondly, HiQ is used to minimize the number of collisions these readers experience when communicating.

HiQ utilizes three basic hierarchical tiers in its control structure: readers, R-servers, and Q-servers. The lowest tier is the RFID readers which they communicate solely when they have been granted a frequency and time slot in communication by a server (R-server) tier. R-servers are allocated frequencies and time slots by the Q-learning servers or Q-servers. Q-learning servers comprise the highest tier in this hierarchical algorithm. Q-servers distribute resources to the servers directly below them in the hierarchy. Regardless of how many Q-server tiers there are, there is always a single root server that has global knowledge of all frequency and time slot resources, and is able to allocate all of them. This approach has some limitations: first, the protocol reserves a hierarchical structure that requires an extra management; second, to mobile readers [16], the topology may change the hierarchical structure which will require the distribution of time slots to be reshuffled. That will consume time and make the system unavailable; furthermore, Q-learning assumes collision detection of readers not in sensing range. It is obvious that some collisions cannot be detected and leads to incorrect operation of the protocol; finally, the use of time slots requires all readers to be synchronized in the whole system which is also the weakness of this approach.

3 Hidden terminal in RFID network

To simplify the presentation, we first explain some terminologies used in this paper. Figure 1 shows an example of hidden terminal in RFID network. In this example, Tag T 1 is surrounded by two readers. Each of the readers located out of sensing range from the other one in the RFID network. Therefore, these two readers are not able to communicate with each other and the reader collision might happen. The situation is mentioned as hidden terminal problem which has the following features:

Fig. 1
figure 1

Example of hidden terminal

Full size image

  • The readers that are not in each others’ sensing range might interfere with tags and cause carrier sensing ineffective.

  • When queries or transmissions from multiple readers collide on a tag, signals can be distorted and the queries might be incorrect.

  • RFID tag can communicate only when they are activated by readers due to it is passive elements. Therefore, RFID tags will not able to pro-actively communicate with readers for avoiding collisions.

Interferences in RFID system are usually classified into reader-to-reader frequency interference and reader-to-tag interference. We further describe these two types in following subsections.

3.1 Reader frequency interference

Reader-to-reader interference, also called reader frequency interference, occurs when readers are interfered with others from communicating with tags. Figure 2 shows RFID reader R 2 resides in the frequency interference range of reader R 1 who has wider interference signal range (the dotted line). As tag T 1 responds to reader R 2, it might be influenced by the interference signal of reader R 1. Such hidden terminal problem occurred even when the readers’ range of the two readers are not overlapped.

Fig. 2
figure 2

Reader frequency interference

Full size image

3.2 Multiple readers to tag interference

Multiple readers to tag interference occurred when two or more readers in the transmission zone attempts to communicate with one tag simultaneously. In this situation, each reader performs one to one communication to the tag. However, it is not known by readers that the tag should be responsible to multiple readers simultaneously. Reader collision will happen in such undesired way. Figure 3a indicates the overlapping of three readers. Readers R 1, R 2, and R 3 are unable to detect each other during communication with tag T 1 simultaneously. Such interference is part of the hidden terminal problem. Figure 3b shows that frequency of the two readers interfered with each other while their read range is not overlapped. This also causes the hidden terminal problem.

Fig. 3
figure 3

Multiple readers to tag interference a with read range overlapped, b read range is not overlapped

Full size image

4 Two-Phase scheduling scheme

In mobile RFID environment, readers may join or leave from an RFID network dynamically, causing hidden terminal problems and communication collisions with existing readers when simultaneous transactions are issued. In order to resolve this problem, we propose a two-phase dynamic modulation (TPDM) protocol, which aims to alleviate reader collision problems, efficiently perform communications in high mobility RFID networks, and expecting better system throughput. TPDM consists of two scheduling phases, the region scheduling phase and the hidden terminal scheduling phase. In the first phase, an RFID reader who attempts to communicate with tag will first detect the density in its vicinity by broadcasting an inquiry beacon through control channel. Based on the information of neighboring density, an appropriate back-off time will be issued adaptively for self-scheduling. In the second phase, the hidden terminal scheduling will be carried out for actual communications between RFID readers and tags through data channel. Upon the geometric characteristic, which reveals that there are at most five hidden terminals that could be resulted from the first phase, the transactions in the second phase could be scheduled accordingly in an efficiency manner. We will introduce the region scheduling and hidden terminal scheduling in the following subsections.

4.1 Region scheduling

The proposed two-phase scheduling technique is a TDMA-based distributed scheme for coordinating simultaneous transmissions among RFID readers. The main concept of region scheduling is to adjust readers’ back-off time dynamically according to the density of its vicinity. As a result of adapting proper back-off time for reactivation, the reader collisions in control channel could be significantly improved. To simplify the presentation of region scheduling scheme, we first explained notations used in this section.

Let l_range and r_range are two variables, representing an interval of possible back-off time for an RFID reader. As the reader attempts to communicate with tag, it will first decide its back-off time (x) according to the following equation,

$$ x = \frac{1}{2}(l\_range + r\_range) $$
(1)

where, l_range = 0 and r_range are determined upon the density of a reader’s vicinity, initially.

The reader will broadcast beacon message after the back-off time, informing other readers that it will enter data channel to perform transactions with tag. In case the beacon message is not collided, it will start the communication with tag through data channel. On the contrary, if the beacon message collided, the back-off time will be adjusted according to the following equation,

$$ x^{\prime} = \frac{1}{2}(new\_l + r\_range) $$
(2)

where, new_l = x.

The above adjustment of back-off time indicates that the density of environment is relative high, increasing probability of reader collision. As a result, the new back-off time should be increased. In case the number of collisions remains even the value of x approaches to r_range, this implies that external RFID readers joined the network, making density of the environment much more than the origin network. When back-off time reaches r_range, the interval will be readjusted according to the following equation,

$$ r\_range = \alpha \times r\_range + (1 - \alpha ) \times [r\_range \times (1 + \beta_{\text{fail}} /x)] $$
(3)

where, α = 0–1, βfail is the number of beacon collisions during readers’ back-off time.

We use an example to clarify the above description. Figure 4 demonstrates four RFID readers R 1, R 2, R 3, and R 5 that exist in an origin network and attempt to communicate with tag. Reader R 4 is newly joined with the same sensing range as others. Readers R 1, R 3, and R 5 are in R 4’s control channel range while reader R 2 is a hidden terminal to the other readers. As reader R 4 also tries to communicate with tag, by applying the region scheduling scheme that is illustrated above, assume reader R 3 initializes r_range = 4, l_range = 0, and x = 2, it might collided with other readers if any of others issues the same back-off time, i.e., 2 time slots. In case the beacon message of R 3 is collided, the back-off time (x) will be reset to 3 according to Eq. 2. If the collision remained when x increased to r_range = 4, the interval of back-off time will be readjusted. According to Eq. 3, r_range will be reset to 6 if we adopt α = 0.5 and β fail = 4.

Fig. 4
figure 4

An example of new reader (R 4) joins region scheduling

Full size image

4.2 Hidden terminal scheduling

Once the reader proceeded to perform transactions in data channel, it will broadcast beacon continuously in order to communicate with tag. It was proved that for a given transaction target, upon geometric characteristic, there are at most five hidden terminals could be exist simultaneously [11]. Therefore, TPDM initializes l_range = 1 and r_range = 5. To carry out the communications with tag, an RFID reader will select the back-off time randomly from the interval [l_range, r_range]. It is assumed that an RFID reader can finish the transaction with tag after one back-off time if the packet_size = 1. If the packet_size > 1, one should issue a new back-off time for reactivating the second round transmission. This is because the reader who performs second round transmission might collide with other existing readers. If the same situation occurs consecutively, either starvation or deadlock could be raised. For example, Fig. 5 shows three RFID readers R 1, R 2, and R 3 are three hidden terminals attempt to communicate with tag. Readers R 1 and R 2 issued a back-off time equals 3 while reader R 3 has back-off time = 2. It is obvious that R 3 will perform the transaction before R 1 and R 2 proceed to. Assume the transaction performed by reader R 3 consumes 1 time slot and R 3 continues the transmission at time slot t = 4, at the same time, readers R 1 and R 2 will broadcast beacon messages informing their attempt to communicate with tag; the collision happened. The above demonstration clarified the need for an RFID reader to issue a new back-off time if the size of transaction is greater than one packet.

Fig. 5
figure 5

Multiple readers request communication with tag through data channel

Full size image

The algorithm of TPDM is given as follows.

figure a

5 Performance evaluation

To evaluate the performance of proposed techniques, we have implemented a random RFID network generator. The TPDM method was compared along with the Colorwave [19] and the Pulse [2] protocols. Both static and dynamic scenarios are conducted in the experiments. All programs were written in C codes. Each test sample was executed 30 times. The mean time for the 30 tests was use as the time of a test sample. We first define some notations, terminologies, comparison parameters, and performance metrics used in later parts in Sect. 5.1. Sections 5.2 and 5.3 report the simulation results for static and dynamic RFID environments, respectively.

5.1 Parameters and metrics

To simplify the presentation in the following analysis, Table 1 summarizes the definition of notations and terminologies used in this section. In order to investigate the impact of reader deployment style, the term “density” is defined to represent locality of readers in an RFID network. Figure 6 gives an example showing the RFID environment with 60% density, which is defined as follows,

$$ {\text{density}} = \frac{{|{{L}}|}}{{|{{R}}|}} $$
(4)

where |L| is number of readers located in the area of a maximum localityFootnote 1; |R| is the number of total readers in an RFID network.

Table 1 Parameters and comparison metrics
Full size table
Fig. 6
figure 6

An RFID network with 60% density

Full size image

In addition, the term CDR, short for control channel to data channel ratio, is also defined in our experimental conduction to evaluate the impact of readers’ sensing range and transmitting range. The CDR is defined as followsFootnote 2,

$$ {\text{CDR}} = \frac{{Range_{\text{ctrl}} }}{{Range_{\text{data}} }} $$
(5)

where Range ctrl is the sensing range in control channel and Range data is the transmitting range in data channel.

5.2 Static circumstance

Figure 7a shows the simulation results of the three methods Pulse, Colorwave, and TPDM under static scenario. In this experiment, parameters are initialized as R init = 40, packet_length = 4, CDR = 2, and α = 50%, because in the static circumstance, we have R join = 0. The simulation results demonstrate that TPDM has superior performance in most cases in terms of throughput. One thing worthy to mention is that when density increases to 40%, all of the three schemes have different reflections. Since the Colorwave was originally designed for dynamic RFID environments, it has neutral but stable performance. The Pulse protocol uses dual channel to coordinate simultaneous communications in wireless RFID network. The dynamic change of system’s density was not taken into consideration in the algorithm design for adjusting the random back-off time. Therefore, when number of readers becomes numerous in an RFID network, the Pulse protocol cannot handle serried communications adaptively. Consequently, the overall system throughput drop dramatically. On the other hand, because the TPDM method first detects the density of one’s vicinity, so it has better performance at system startup. Although the system changes its density, the TPDM can adjust the back-off time accordingly and has better throughput.

Fig. 7
figure 7

Performance results in static environment a impact of network density, b impact of CDR

Full size image

Figure 7b shows the performance results of another experiment with R init = 40, Packet_length = 3, and α = 50%. This experiment is conducted based on different CDR to examine the influence of reader’s sensing and communicating range to the scheduling performance. Because the CDR is defined as the ratio of control channel range to data channel range, when CDR becomes large, the amount of readers been covered by each reader could be increased. As a result, the system’s density will be increased as well. Similar to the results that obtained in Fig. 7a, the TPDM mechanism performs better than the other schemes in all test cases. When CDR increased, all of the methods decrease the throughput gradually except the Pulse protocol. Observing at CDR = 2–4, the throughput achieved by Pulse is dropped dramatically. This reflects that the Pulse protocol cannot coordinate reader–tag communications adaptively in high density RFID systems promptly. On the contrary, the TPDM method provides stable and competitive performance in different circumstances.

5.3 Dynamic circumstance

This section discusses the experiments in dynamic circumstance. Figure 8a shows the comparisons of throughput for Pulse, Colorwave, and TPDM methods. This experiment is conducted with R init = 15, Packet_length = 4, and CDR = 2 under different system density. Figure 8b reports the throughput of these algorithms on different CDR. Because of the mobility in dynamic environment, the term (1 − α) in Eq. 3 should be significant enough to reflect the change of system’s configuration. Consequently, we set α = 0.3 from the value 0.5 that used in static instance. The probability for external reader to join an existing network at each time slot is set to 0.3 in this experiment. From the experimental results illustrated in Fig. 8a and b, we observe that in system throughput, the order is TPDM > Colorwave > Pulse. Since the Colorwave algorithm is originally designed for dynamic systems, it has neutral but stable performance. Although the Pulse protocol performs better than the Colorwave in static circumstance with sparse environment but it performs worse in dynamic ones because the Pulse protocol lacks directives to adjust scheduling strategy dynamically. As contrasted with static circumstance, the Pulse protocol has ordinary performance even if CDR or system density increased. This is because the initial number of reader is only R init = 15 and readers are joined into the system based on the probability 0.3, which will not result a high-density RFID network. Therefore, the throughput achieved by Pulse protocol does not oscillate dramatically. For all methods, they can maintain a stable performance on different network density and CDR. The TPDM method also has better performance than Colorwave and Pulse schemes because of the adaptability of scheduling strategy. An RFID reader can dynamic adjust the period to broadcast beacons according to the system’s status. Therefore, it can maintain better throughput in both static and dynamic environments.

Fig. 8
figure 8

Performance results in dynamic environment a impact of network density, b impact of CDR

Full size image

6 Conclusions

Radio frequency identification technologies advance the next generation ubiquitous computing. An RFID reader is planted into cell phone or PDA after compressing to use as sensor to RFID tag for information gathering. When RFID tag is sensed, we can easily get the information required on cell phone or PDA through RFID tag at any time and anywhere. With the increasing use of RFID applications, high reader density and mobility are two major features in future RFID systems. From this point of view, the condensed RFID network incurs reader collision problem while the movement of readers brings out signal interference to prohibit correct information from reading in dynamic environment.

In this, we proposed a two-phase dynamic modulation (TPDM) method aims to efficiently perform transactions of readers and tags in mobile and high density RFID networks. TPDM is a simple mechanism for coordinating simultaneous communications among multiple readers and hidden terminals. A significant improvement of this approach is that TPDM can prevent reader collisions by using a distributed self-scheduling scheme. The other advantage of the proposed technique is that TPDM is adaptive in both static and dynamic RFID environments. The experimental results show that the TPDM can provide superior and stable performance in both static and dynamic circumstance. The TPDM is also shown to be effective in terms of system throughput and easy to implement.