DACAR: Distributed & Adaptable Crosslayer Anticollision and Routing Protocol for RFID

Abstract

In the midst of Internet of Things development, a first requirement was tracking and identification of those mentioned “things which could be done thanks to Radio Frequency Identification. However, since then, the development of RFID allowed a new range of applications among which is remote sensing of environmental values. While RFID can be seen as a more efficient solution than traditional Wireless Sensor Networks, two main issues remain: first reading collisions and second proficient data gathering solution. In this paper, we examine the implementation of two applications: for industrial IoT and for smart cities, respectively. Both applications, in regards to their requirements and configuration, challenge the operation of a RFID sensing solution combined with a dynamic wireless data gathering over multihops. They require the use of both mobile and fixed readers to cover the extent of deployment area and a quick retrieval of tag information. We propose a distributed crosslayer solution for improving the efficiency of the RFID system in terms of collision and throughput but also its proficiency in terms of tag information routing towards one or multiple sinks. Simulation results show that we can achieve high level of throughput while maintaining a low level of collision and a fairness of reader medium access above $95\%$ in situations where readers can be fix and mobile, while tag information is routed with a data rate of ${\approx }97\%$ at worst and reliable delays for considered applications.

This work was partially supported by CPER DATA and IPL CityLab@Inria.

1 Introduction

Radio Frequency Identification (RFID) has for the longest time been used as a mean for identification and tracking of goods, animals and even humans. Indeed, thanks to its operating scheme, it allows a contactless and non direct line of sight recognition. Using a device called a reader, one can identify an object thanks to a small chip attached to it known as a tag that stores the relative information. Different types of tags can be found and can be categorized as (i) active, if they embed an energy source, (ii): passive, if they entirely rely on the received signal power from the reader to power themselves and communicate [10] or semi active/passive tags: they stand in between the two precedent ones. They carry a battery intended to power some of their attached components but still rely on the reader’s energy to communicate. In the following of this paper, we will mainly target passive tags which are more compliant with IoT applications requirements. UHF RFID systems operating in the frequency band of 865–868 MHz or 902–928 MHz, according respectively to ETSI [8] or FCC regulations are considered a interesting complement for IoT applications and services thanks to the longer interrogation range. Multiple works have been conducted towards ambient energy harvesting and in particular [13] discuss harvesting energy in UHF RFID. Previously in [23], authors present how sensors could be attached to passive RFID tags in order to get both the original identification but also battery-free environmental sensing. A comparative study of sensing using the different RFID bands is done in [24]. Authors also present the case of wireless temperature and pressure sensors using passive battery-free RFID sensors for industrial applications.

In this paper, we venture into the use of RFID for two particular applications. The first one considers a large warehouse with tags attached to goods disposed in horizontally disposed shelves while readers, considered mobile, are attached to forklifts or hand-held by operators walking through alleys. Such an application assesses the use of RFID in supply chain management where the products could be foodstuffs such as dairy, meat or seafood products that need to be monitored in terms of humidity or temperature to prevent deterioration. The second application we consider is a smart city where passive tags are considered to be attached to vehicles, public city bikes and urban infrastructures. Targeting the vehicles and public city bikes allows the tracking of their position inside the city which, outside of the privacy issues not tackled here, can facilitate the work of law enforcement agencies, identify traffic stops for better management, scarcity of public bikes in given neighborhoods, etc. Urban infrastructures such as buildings, roads or bridges need to be monitored for different “vitals” like humidity, state of corrosion and pH-value to be able to address any defects as soon as possible before any more expensive fix or major catastrophe.

However, both of these applications share (i) the density of readers’ deployment and (i) their mobility inside the given environment which affect the efficiency of readers’ interrogation due to collisions. Next is the collection of information towards a base station which has to be done in regards of readers activity and available communication medium. Indeed, in these deployments where readers are scattered throughout the environment, they cannot all be equipped with a long range communication interface to join the decision center. Not only would that be more expensive in terms of cost but also more energy consuming [9]. As such, they have to rely on each other using their deployment topology and short range wireless communication interfaces to reach a sink responsible for uploading the data to the decision center. In order to reach the sink, a multi-hop routing algorithm must be set that integrates the readers activity (reading round) as well as the type of data being gathered in its scheduling to optimize global performance.

In [15], we presented a joint reading-gathering mechanisms for static multi-hop RFID reader networks. However, this proposal was not suitable for mobile deployments of readers where the topology is always evolving. Tag interrogation and data forwarding suffered from collisions and decreased the data rate. In this paper, we present DACAR for Distributed & Adaptable Crosslayer Anticollision and Routing protocol for RFID. A work on the compliance with mobile deployments which have different requirements in terms of scheduling and routing. The solution proposed here to overcome issues brought by mobility and to tackle the constraints of the applications introduced above features the following:

• distributed and local: same algorithm runs on all devices based on information gathered from neighbors;

• fair: medium access is regulated while ensuring no reader is prejudiced;

• reliable: data rate is highly successful with suitable latency for applications;

• adaptable: our solution can be adapted to most anti-collision protocols already available.

The main contributions of this work are: (i) a novel cross-layer scheduling and routing solution for RFID systems compliant with IoT applications and their requirements, (ii) its evaluation over two considered applications challenging the expressed concerns (density, mobility, data gathering and routing) and (iii) a discussion over future research directions regarding RFID sensing. This paper also provides the following insights: high performance can be obtained regarding the contention resolution with fairness levels close to $100\%$ and quick coverage of all deployed tags in under 60 or 90 s depending on the application; in regards to the contention algorithm chosen, the successfully forwarded packet data ratio is above $96\%$ and go as high as $99.5\%$ which is on par with considered industrial and urban application requirements; the end-to-end delay needed to retrieve and deliver tag information from the furthest point to the sink is on average around 15 to 44 s, depending on the scenario, which once again can be considered reliable for the given applications.

The rest of this paper is organized as follows. Section 2 presents the issues and concerns addressed in this work. Section 3 introduces our proposed algorithm DACAR. The evaluation over given scenarios is done in Sect. 4. Section 5 presents related work. Section 6 discusses the possible future research directions and issues that need to be focused on before we conclude in Sect. 7.

2 Problem Statement

When applying RFID solutions to industrial or urban scenarios, several issues need to be resolved. They are either directly related to the technology itself or to the application requirements and constraints. We detail here these different concerns and introduce the different ways then can be coped with.

2.1 Density of Deployment

The evolution of IoT and the requisites of intended applications lead to larger deployment of nodes in restrictive spaces. In light of the wireless nature of the technology used, this causes radio collisions. Regarding RFID, this can be translated into different types of collisions, either tags or readers collisions. Tag collisions happen when multiple tags are laying within the interrogation range of a reader and upon reception of interrogation signal, attempt to answer all at the same time. The multiple answers collide and are not perceived by the reader. Reader collisions are the result of multiple readers interrogating the same tags simultaneously. Their interrogation signals overlay at the tags level. The tags are unable to dissociate the different signals and fail to answer to the interrogation resulting in missed tags. Both issues have been topics of research in the late years, regarding tag collisions, a survey is also available in [7] which classifies proposals in their main categories, solutions are now even embedded in commercial products and we will thus not tackle this issue in this paper. Reader collisions however, remain an important issue. Our solution being compliant with most anti-collision protocols in the literature, we will re-use most performing algorithms from the state-of-the-art.

2.2 Mobility

In regards to the applications presented in Sect. 1, we understand the need to have dynamic readers and not only static placed ones. In order to reach the furthest regions of the city or warehouse, having a mobile reader is more efficient than deploying even more readers which is not cost effective, produces more collisions due to density and consumes more energy. Just as density does, the mobility of readers also produces collisions, since in a non-controlled mobility setting, readers can meet at random spots producing collisions. In order to cope with both the density and mobility of readers, having distributed algorithms is more convenient. As such, using wireless communicating readers, instead of wired ones connected to a central server synchronizing all devices, allows them to roam freely in the deployment area. Being able to wander about, the relative density of readers based on their vicinity is always changing hence the need for the algorithms to be scalable.

2.3 Data Gathering

Upon scheduling the readers’ interrogations, much more tag information is made available and needs to be forwarded in the most efficient way possible towards a base station for computing and decision making. While in traditional WSN, nodes may access to a long range communication interface (cellular, LPWAN technologies, etc.), in our paper, we focus on the previously mentioned wireless communication interface to both schedule reading activity and collect data. Since we opted for a distributed and scalable solution, readers based on their activity, relative position to the sink and neighbors perform their best effort to forward the data. Having a combined activity scheduling as well as a routing scheme allows the system to be more energy efficient and prevents from overlapping of interrogation and forwarding phases making the solution more proficient.

In the remaining of our manuscript, we assume readers have two distinct wireless interfaces. The first interface is the traditional RFID interrogation antenna. It is used by readers to communicate with tags and retrieve the stored information. The range of this interface is $d_{CRT}$. The second interface is the peer communication antenna. It is used by readers to send beacons used for activity scheduling as seen in [4, 11, 20, 22]. In our proposal, this interface is also used to forward tag information to the base station. The range of this interface is $d_{Com}$. In order for reader to be able to identify colliding neighbors, the value of $d_{Com}$ has to be set to at least $d_{Com} = 2 \times d_{CRT}$ [1].

3 DACAR

The chosen topology and its initialization remains the same as in [15] and will briefly be explained before moving on to the improvements made to comply with dynamic deployments.

3.1 Background

Topology: In order to self-organize, readers discover their hop count to the sink. This position will then determine both their interrogation activity as well as their routing behavior. The chosen topology is a gradient where readers are organized around the sink based on the hop count needed to reach it.

Network Initialization: In order for each reader to estimate its hop count to the sink, a beacon propagation emanating from the sink is conducted. At first, the sink sends a beacon containing its ID and a $rank_{local} = 0$. This beacon is received by readers within range that compare their own $rank_{local}$, with the $rank_{RX}$ enclosed in the beacon. If $rank_{RX} < rank_{local}+1$, the reader sets its $rank_{local}$ to $rank_{RX}+1$ and stores the beacon source node as its direct parent $parent_{local}$. Otherwise, if $rank_{RX} >= rank_{local}+1$, the reader discards the beacon as it originates from a node either with a greater or similar rank. Before forwarding the beacons with their own rank, readers draw a random backoff and wait it out to reduce collisions.

3.2 Proposal

In [15], readers were considered as static and the topology would not change. However, using mobile readers the topology is dynamic and the gradient needs to be maintained with readers relative positions. This work thus considers an additional gradient maintenance to keep $rank_{local}$ and $parent_{local}$ values up to date. Figure 1 illustrates the activity of 7 readers disposed around a sink. The network initialization has already been done and each reader display its respective $rank_{local}$ and $parent_{local}$. Since the highest rank in the network is $rank_{G}=4$, readers can choose timeslots within [0–3] in regards to Algorithm 1. Dashed circles represent the wireless communication range of nodes $d_{Com}$ while dotted circles portray the tag interrogation range $d_{CRT}$. Beacon exchanges regarding the scheduling are not depicted here to avoid clutter.

Gradient Maintenance: Whenever a reader has to forward data, it broadcast a beacon, answered by its neighbors with their own values. The reader then selects the neighbor with the lowest rank and sets it as its new parent $parent_{local}$ and updates its $rank_{local}$ as well. Since the network is dense, unconcerned neighbors receiving the beacon still update their $rank_{local}$ and $parent_{local}$. These values are then conserved with a timeout value in order to avoid too much overhead and unnecessary energy drain. As such, depending on the state of the timeout a reader will either update its values or conserve the ones already stored. This timeout value is set depending on the speed of the reader and its communication range. Depending on the anti-collision algorithm in use, readers will behave differently and the vicinity knowledge of each reader can be affected.

Interrogation Scheduling: As with most distributed TDMA anti-collision protocols, readers activity is organized in timeslots themselves gathered in rounds. The active timeslot, here called $slot_{local}$, is usually randomly chosen within a range before contention and tag interrogation. However, with our approach, instead of randomly selecting a timeslot $slot_{local}$ within $[0;round\_size[$, readers select their timeslot based on their ranks. The maximum rank value observed in the network is set as the new maximum value to choose from. As such, readers with an even (resp. odd) rank, i.e. $rank_{local} \% 2 = 0$ (resp. $rank_{local} \% 2 \ne 0$), will randomly chose an even (resp. odd) timeslot between $[0;round\_size[$. This has the advantage of decreasing the number of potential collisions since readers within two consecutive ranks will not interrogate tags at the same time whatsoever. Readers within the same rank are not only disposed within a concentric circle but can also choose different timeslot $slot_{local}$ values, lowering the probability of collisions. In Fig. 1b, during $t=0$, readers F & G respectively ranked $rank_{F}=2$ and $rank_{G}=4$ choose slot 0 while reader C & D, ranked $rank_{C;D}=2$ choose slot $t=2$, as seen in Fig. 1d (i.e. Algorithm 1 l1–2). On the other hand, readers A & B ranked $rank_{A;B}=1$ choose slot $t=1$, depicted in Fig. 1c, and reader E, $rank_{E}=3$, chooses $t=3$, as seen in Fig. 1e (i.e. Algorithm 1 l3). Similar to almost all TDMA anti-collision schemes, 2 durations are defined: $T_{Beacon}$, time during which readers exchange beacons for scheduling their activity and $T_{CRT}$, time used by readers to communicate with tags within range.

Tag Information Gathering: The data gathering leverages the new rank-based scheduling. Indeed, the time difference observed between even and odd ranked readers is used to perform data forwarding during periods of inactivity of readers. After interrogating tags in its range during slot n, a reader will forward the collected data towards its $parent_{local}$ during slot $n+1$. Since the wireless communication channel is different from the tag interrogation channel, the data forwarding will not interfere with the interrogation activity (see Sect. 2.3). After contending during slot n, the following course of actions can happen:

• the reader needs to transmit data (its own reading or data to forward from its children): At slot $n+1$, the reader forwards the data to its $parent_{local}$ during $T_{CRT}$ and then waits for the next round (Algorithm 2 l1–3). If the tag information has not been fully transmitted, it will be continued on the next relay occasion. In order to avoid collisions during the forwarding process, readers draw a backoff before following an RTS/CTS mechanism [21] with their $parent_{local}$. This is the case in Fig. 1c, readers F & G which previously read during slot $t=0$, now forward their data during $t=1$. Same in Fig. 1d, with readers A & B which read during $t=1$ and attempt to forward during $t=2$, and E which received data from G during $t=1$ and forwards it in $t=2$ as well. However, B fails to forwards in $t=2$, due to the RTS/CTS mechanism and avoid collisions with A. Next, in Fig. 1e (Algorithm 2 l7–10), C which read in $t=2$, forwards data in $t=3$;

• the reader has no tag information to send. It waits for the next round to perform the interrogation scheduling contention again (Algorithm 2 l6). This is the case of reader D in Fig. 1 which failed its contention with reader C during slot $t=2$ and also did not receive data from any neighbors. It waits for the following round to contend again;

• the reader performed its interrogation contention in the last available slot of the current round and thus cannot forward its data on the next round. It must wait for the following round, performs the contention algorithm and according to the new $slot_{local}$ chosen, will forward the tag information if any (Algorithm 2 l4). In Fig. 1e, reader E interrogates tags in the last slot $t=3$, and waits for the next round to forward its data.

Fig. 1.

Tag interrogation and data forwarding

4 Performance Evaluation

In order to evaluate the performances of DACAR, we stage 2 application scenarios. We implemented DACAR using two anti-collision protocols CORA and mDEFAR [14] that both highly perform for dense and mobile deployments of readers compliant with the scenarios depicted. They perform similarly to results obtained in [14, 16].

4.1 Simulation Scenarios

The first scenario stages an industrial IoT deployment in a warehouse of $100\times 100\,\mathrm{m}^{2}$. 4000 tags are disposed inside the area. They are organized in 20 horizontally disposed shelves of 200 tags each. In order to cover all tags and test the behavior of our algorithms in dense environments, we deployed 80 mobile readers moving between aisles at a speed ranging between [0.5–1.5] m/s. This allows the consideration of both readers attached to forklifts as hand-held ones. The only sink is centered in the area. The next scenario represents a city district of size $555\times 555\,\mathrm{m}^{2}$ with 3000 tags are randomly deployed, either mobile roaming freely in the area at a speed ranging in [21–36] km/h or static supposed on buildings. 570 readers are also considered either mobile at a speed ranging in [14–20] km/h or static disposed at street corners. Five sinks are deployed in the area to test the behavior of our algorithms with multiple base stations.

4.2 Results

Simulations were run on WSNet¹, an event-driven simulator for large scale wireless networks. $T_{Beacon}$ and $T_{CRT}$ are respectively set to 5 ms and 460 ms [1, 4, 8]. For each scenario and algorithm, 100 simulations are run. The graphs presented depict an average of the obtained results with the $95^{th}$ percentile expressed.

Packet Data Ratio (PDR): Figures 2a and b show the percentage of messages successfully transmitted to the base station(s). It is computed as the ratio of the number of tag information messages received at the sink(s) over the total number of tag information messages sent. In the warehouse scenario, the successful PDR is above $96\%$ while in the urban scenario it is above $99\%$ for both contention algorithms. The lowest results in the warehouse scenario are due to a higher number of tags and a lower number of readers covering them (4000 tags for 80 readers). Also in both cases, we can see that mDEFAR has slightly better results than CORA. This is due to the fact that CORA having a higher throughput and active readers at each round, has more tag information to forward inducing more traffic. Indeed, CORA enabled more readers during each timeslot, with more tag information to forward to the sink. Several involved readers collide, which affects the PDR. However, with such levels of PDR, the results are quite reliable, since tags can be covered by several readers, as such even if the information is lost by one reader it will be picked up by another neighbor and forwarded to the sink(s). Once again, the mobility and density of deployment become an advantage for the considered applications.

Latency: The latency assesses the delay between a tag information being read and its reception by one of the base stations. In DACAR, since readers are organized in a gradient topology, the latency is given according to the relative rank of the source reader. In Fig. 2c, we can see the latency, in seconds, for all 4 ranks during simulations. We can see that, on average, the on-air time for a tag information to reach the sink is around 15 s whichever contention algorithm is chosen. This duration seems to be quite reliable for the application concerned. Indeed, in case a product inside the warehouse is considered defective according to presets, depending on its position, it will take less than 16 s for the system to be notified and the appropriate countermeasure to be taken. Figure 2d shows the results for our urban simulation. Due to the higher mobility of readers, results are slightly different. However, results remain reliable with on average 44 s for the furthest tag information to reach a sink. In case a urban infrastructure needs to be evacuated due to safety measures, it would take less than a minute for the system and authorities to be notified. Also, in case of a suspect vehicle being researched, within this given time, it will be located and notified to authorities. We can see that in both scenarios, mDEFAR has slightly better results than CORA, this is once again due to the fact that mDEFAR, with a lower throughput, has less tag information to forward inducing less congestion.

Fig. 2.

Data gathering results

5 Related Work

RFID as an enabler for IoT has been a main topic of research in the later years. Indeed, RFID is now a mature technology that can be used in a range of IoT applications [6]. Indeed, multiple experiments have shown how RFID could be a better alternative for IoT applications thanks to its communication perquisites compared to traditional Wireless Sensor Networks (WSN) solutions. As such, several applications can be found with RFID being evaluated in challenging environments such as embedded in concrete [3], disposed in water [5], buried underground [2] or attached to metallic materials [18]. However, most of these works fail to discuss one of the concerns of using RFID which is collisions. As discussed in Sects. 2.1 and 2.2, in case of a dense deployment of RFID devices, collisions can negatively impact the performance of deployed systems. Multiple anti-collision proposals can be found throughout the literature. In [12], authors discuss the implementation of an RFID architecture with a base station and propose an anti-collision protocol. Their solution is based on differential backoff periods based on readers’ energy levels. In [20], a central server schedules the readers. The ETSI [8] standard proposes the use of “Listen Before Talk” in which readers listen to the medium for a defined period of time to ensure it is idle before interrogating tags. In case the medium is occupied, the readers can switch to another channel and perform their listening. Several other proposals can be found as detailed in [17].

6 Discussions

6.1 Energy Consumption

Although DACAR balances the periods of inactivity of readers for a better efficiency, energy consumption still needs to be addressed. Indeed, the contention itself as well as the topology maintenance rely on the exchange of several beacons between devices. Implementing a timeout before the topology update process allows the reduction of the overhead, however, further investigations are required to guarantee a fully autonomous system and lengthen its lifetime. Carrying out an energy harvesting solution for readers based either on photo-voltaic panels or regenerative braking for mobile nodes could also be a factor to integrate in order to improve the energy efficiency. As such, readers with the highest residual energy levels could be prioritized for interrogation and forwarding activities reducing collisions and balancing out the load of the network.

6.2 Data Aggregation

Due to the density of deployment, tag information might be read several times by several readers and forwarded to the base station. Also as shown in Figure 1, reader E could have waited until its tag interrogation before forwarding both its data and the one received from G. As such, C would forward data from G, E and its own. While this can be considered an advantage, it also creates unnecessary congestion in the network. A solution would be to aggregate data and drop duplicate packets. This has been discussed in the literature for traditional WSN networks and could be applied to RFID as well. For instance, [19] investigates the energy efficiency of distributed compressed sensing in WSNs.

6.3 Metrics

In DACAR, the topology construction and maintenance are based solely on the number of hops between readers and their relative sink(s). While this metric could be considered as reliable for some applications where for instance the state of the radio medium is not fluctuating, several other metrics can be taken into account to offer a solution that could be validated in industrial and urban scenarios. Indeed, these environments are known to be unstable and noisy due to either confinement or multiple other sources of radiation in cities. As such, we believe that link quality between readers, latency, packet drop rate, energy levels between neighbors should also be considered to propose a more robust solution.

7 Conclusion

This paper presents DACAR, a complete RFID solution to enable IoT in industrial and urban applications. This work is conducted through the performance study of our solution under different scenarios and constraints. Analysis show that proficient interrogation can be conducted using the contention algorithm proposed and this is confirmed by the throughput, collisions, fairness and coverage delay results. On the other hand, data forwarding results are reliable and guarantee both steady knowledge of the network thanks to high packet data ratio and respectable delay to provide safe outcome for the considered applications. However, improvements are achievable in regards to the issues presented in Sect. 6 and will be addressed in future works. Experiments conducted in controlled environments or in an RFID test-bed are also considered.