Optimum Power Distance Clustering for the EPC Class-1 Gen2 Standard in RFID Systems

Abstract

Tag collision is one of the main issues impacting the performance of radio-frequency identification (RFID) systems. Several research efforts have been done in order to solve such problem. Current RFID standards, such as EPCGen2 and ISO-18000-7, adopt ALOHA-based protocols as the basis to solve collisions. In recent years, there has been a trend on designing schemes that split the interrogation zone into smaller regions with the aim of improving the system's performance. In this paper, we evaluate and optimize the performance of ALOHA-based protocols for this new type of partitioning schemes. We establish the guidelines for adapting ALOHA protocols to this new approach in order to exploit the advantages it offers. Thus, we propose a new version of the EPCGen2 standard adapted to the new partitioning schemes, which overcomes its counterpart for the traditional approach, significantly reducing the identification delay, which is the main parameter to optimize in RFID.

1. Introduction

RFID systems have become common in our daily life; their utility has largely exceeded that of bar codes since they offer a large set of new advantages on their use such as being in no need of a direct sight line or contact for communications, the ability of making simultaneous identifications, and having a wider identification range [1]. Some of the most popular applications for RFID technology are asset tracking, reusable containers, automatized inventories, and parts moving to a manufacturing production line, just to mention a few. Thus, it is crucial to improve the performance of RFID technology so as to get an overall impact on such wide range of applications.

There are two types of devices in an RFID network: readers and tags. On one hand, a reader is a powerful device in terms of memory and processing capabilities; it energizes the tags, controls the network's communication sequence, transfers information among the application and the tags, and identifies the set of existing tags in its interrogation zone. On the other hand, tags are small devices that are normally attached to the objects to be identified. Each tag has a unique identifier (ID) and may be active or passive [2]. Active tags account with a high storage capacity as well as with considerable processing capabilities; they normally come equipped with a battery. Passive tags gather the incoming energy from the reader to power up their circuitry, which makes them cheap to produce, thus making the use of passive RFID environments the most important for industry and research.

Several communication processes may be performed in an RFID network, such as missing-tag detection [3], estimation of the cardinality of a set of tags [4], and tag identification [5], the latter being the most frequent for a large set of actual applications. Thus, the identification process is performed by the interaction of reader(s) and tags in order to discover the whole set of tags present within the identification range of the reader(s). Such process is as follows: the reader broadcasts an information request, querying for IDs. Hence, each tag tries to reply in an ordered way, which may produce a collision if two or more tags respond at the same time, wasting energy and channel resources. This problem is known as the tag collision problem and is one of the main research topics in RFID networks. We can find work in the literature aiming to solve such issue; however, most of the contributions focus on the design of efficient communication protocols for the traditional one reader-one set of RFID tags scenario [6, 7]. There are a few recent revolutionary approaches aiming to shift from the traditional RFID scheme to new communication approaches. In [8], the authors propose to solve the tag collision problem by partitioning the interrogation zone into smaller zones and query one at a time using any given anticollision protocol. The authors' idea is very similar to the one used in the tree-based protocols, which splits a set of tags into several subsets in order to fasten the identification process by using the concept of power distance clustering (PDC). Later, in [9] the same authors add new devices to the process, increasing the complexity of the communication between reader and tags. The main idea presented there is to divide the set of tags and query them in a parallel fashion. Finally, in [10] the authors propose a full replacement of the traditional RFID system with one composed of one transmitter and several receiver RFID listeners. Such contribution proposes to extend the coverage area of an RFID system and uses cooperative reception techniques [11, 12]. Thus, we clearly see a new promising trend on the architecture of RFID systems. Such trend shows the need of new protocols for these new approaches, since most of them have been evaluated with tree-based protocols disregarding ALOHA-based ones, which have shown to be more efficient on the identification time. Moreover, ALOHA protocols are of great importance on RFID networks since they have been adopted as the basis of the two existing standards to solve collisions for active and passive RFID environments.

In this paper, we evaluate the performance of ALOHA-based protocols under the so-called PDC mechanism, which seems to be very promising.

In a recent work [13], we analyze an identification mechanism proposed in [9], and we propose an ALOHA-based protocol that exploits the advantages offered by such mechanism. The analyzed identification mechanism differs from the PDC approach in its architecture, since it introduces a new additional device in the RFID network, which is called a cluster-head. This new device plays the role of a relay between the reader and the tags. Additionally in that work, we study the advantages and disadvantages of such scheme compared to the traditional centralized identification approach.

In this paper, by means of surface analysis we adapt ALOHA protocols for their use with PDC in an optimal manner regarding time identification. Unlike tree-based protocols, ALOHA-based protocols work on a probabilistic basis, which complicates their use on a partitioning scheme. Hence, the rest of this paper is organized as follows; Section 2 discusses the related work on ALOHA-based protocols and the PDC scheme. In Section 3, we detail our proposal, where we adapt the operation of ALOHA to the PDC paradigm. Section 4 describes the performance measures we consider to evaluate our proposal. In Section 5, we address our results. Finally, in Section 6 we conclude this paper with a discussion of the results and contributions of our work.

2. Related Work

Several anticollision protocols for RFID have been proposed in the literature; they can be classified in two groups: ALOHA-based and tree-based protocols [1]. Some designers may choose to implement tree-based protocols because they are often more reliable than ALOHA-based ones; however, the latter are the most used type of protocols in RFID for two main reasons: $(1)$ the existing standards for RFID are based on ALOHA protocols and $(2)$ these protocols are the fastest for RFID identification.

ALOHA protocols are probabilistic; thus they introduce randomness during the identification process. One of the most representative protocols falling into this category is the Dynamic Framed Slotted ALOHA protocol (DFSA) [1], which considers that time is slotted and grouped into frames [14]. In DFSA, the frame length varies during the whole identification process as the size of the set of tag decreases. In order to get this behavior, DFSA uses an estimation function that predicts the number of unidentified tags, which sets the frame length equal to such predicted number, so as to reach the maximum efficiency of ALOHA protocols [15]. Several estimation functions have been proposed in the literature such as those proposed in [16, 17]; most of them take as input parameters the number of empty slots $(c_{\mathrm{0}})$ , the number of single slots $(c_{\mathrm{1}})$ , and the number of collision slots $(c_k)$ [18, 19].

Since tree-based protocols are deterministic, they are able to identify a set of tags in a finite time. The performance of tree-based protocols strongly depends on the coding mechanism used for transmission. The main idea of such type of protocols is to divide the set of tags into many subsets. Their implementation is cheap; however, they need more commands than ALOHA protocols to carry out the identification process. This type of protocols may be classified as follows: prefix, bit by bit, and scanning-based [20]. On one hand, prefix-based protocols take a portion of the ID to carry out the identification of a given tag. On the other hand, bit by bit based protocols use bit-wise arbitration and pointers to the ID. Finally, scanning-based protocols exploit the uniqueness of IDs; thus they use the information obtained in a collision to generate all the possible IDs.

2.1. EPC Class-1 Generation-2 Standard

EPCglobal published the Class-1 Generation-2 standard (EPC Gen2 hereafter) for air interface protocols, which defines the physical and logical requirements for an RFID system of readers and passive tags in order to solve collisions in passive RFID scenarios [21]. EPC Gen2 is based on a modified version of DFSA, which uses the Q protocol as a mechanism to adapt the frame length at the end of each frame [22]. As Figure 1 shows, the Q protocol adapts the frame length according to the number of collision and empty slots. There are several papers in the literature proposing mechanisms to improve the performance of EPC Gen2. Some work proposes modifications to the Q protocol or the use of an alternative mechanism to adapt the frame length; a common conclusion among such contributions is that the frame length must be equal to the estimated number of unidentified tags ( $\widehat{n}$ ) [15]. Thus, with this end, the authors of [23] provide a heuristic to choose the optimal value of Q as a function of the estimated number of unidentified tags. Table 1 lists the value of Q as a function of $\widehat{n}$ .

Table 1

Optimal $Q$ .

Optimal Q	n
0	$n=\mathrm{1}$
1	$\mathrm{1}<n\le \mathrm{3}$
2	$\mathrm{3}<n\le \mathrm{6}$
3	$\mathrm{6}<n\le \mathrm{11}$
4	$\mathrm{11}<n\le \mathrm{22}$
5	$\mathrm{22}<n\le \mathrm{44}$
6	$\mathrm{44}<n\le \mathrm{89}$
7	$\mathrm{89}<n\le \mathrm{177}$
8	$\mathrm{177}<n\le \mathrm{355}$
9	$\mathrm{355}<n\le \mathrm{710}$
10	$\mathrm{710}<n\le \mathrm{1420}$
11	$\mathrm{1420}<n\le \mathrm{2839}$
12	$\mathrm{2839}<n\le \mathrm{5678}$
13	$\mathrm{5678}<n\le \mathrm{11357}$
14	$\mathrm{11357}<n\le \mathrm{22713}$
15	$n>\mathrm{22713}$

Figure 1

$Q\mathrm{\hspace{0.17em}\hspace{0.17em}}$ protocol: mechanism to adapt the frame length used by EPC Gen2.

Additionally, the performance of EPC Gen2 when choosing an optimal Q may be improved with the knowledge of extra information, such as the number of tags within the reader's interrogation zone. Thus, we can fasten the identification process by setting the length of the first frame equal to the existing number of tags in the interrogation zone, rather than initializing the process with the default value of Q.

2.2. Power-Based Distance Clustering Anticollision Scheme

In [8], the authors propose to adjust the reader's coverage range by varying the antenna's power. The main idea is to gradually extend the reader's interrogation zone from an initial value until reaching the maximum interrogation range. This means that, at any time, only the tags within the same cluster respond to the reader request. The main goal of such proposal is to reduce the number of concurrent participating tags, as is shown in Figure 2. We can see that the interrogation zone is divided into clusters $c_{\mathrm{1}}$ , $c_{\mathrm{2}}^{\prime }$ , and $c_k^{\mathrm{\prime \prime }}$ with distances d, $d^{\prime }$ , and $d^{\mathrm{\prime \prime }}$ , respectively.

Figure 2

Clustering based on the distance from reader to tags.

A key parameter for PDC is the “step” value (d), since it determines the number of clusters within the interrogation zone. Therefore, it is common to use small values of d for dense environments and large values for sparse scenarios.

(1) Optimal Power-Based Distance Clustering for Tag Anticollision in RFID Systems. An optimization of the PDC scheme is presented in [20]. Based on the protocol used and tag distribution, the authors provide an analytical model to get the optimal number of clusters. Thus, they take advantage of the deterministic feature of tree-based protocols to compute the optimal value of d, using the query-tree protocol by assuming a uniform distribution [24]. The authors mention that a similar analysis may be made for any other protocol and a given distribution; nevertheless, they are unable to make such analysis for ALOHA-based protocols [25].

(2) Discrete Power-Based Distance Clustering for Anticollision Schemes in RFID Systems. In [25], the authors optimize their previous work on PDC, which they call Optimal Discrete-PDC (OD-PDC). The proposal consists of partitioning the identification zone based on the possible transmission range of a reader. The OD-PDC scheme is independent of both the tags distribution and the anticollision protocol used within a single cluster. Despite the advantages mentioned before, the proposal has a strong requirement to make ALOHA protocols work under the PDC scheme, which is to know the total number of tags within the interrogation zone. This means that ALOHA protocols cannot be used if such information is unavailable and, more importantly, optimality cannot be reached as well.

3. Power Distance Clustering for ALOHA Protocols

We have seen so far that PDC is a promising mechanism to improve the performance of RFID; however, it has been barely evaluated for standard protocols. Since ALOHA is the basis of the most important standards for RFID, it becomes vital to evaluate its performance for this new promising PDC paradigm. Even if the proposal presented in [25] shows some results of the Q Algorithm on the PDC scheme, they are unclear since the authors do not mention how the frame length is chosen and how good is the performance achieved in terms of time, besides the fact that they are unable to find how to make ALOHA protocols work to the PDC in scenarios without prior information.

In this section, we adapt the operation of the ALOHA-based protocol required by the EPC Gen2 standard to work under the PDC approach. By means of surface analysis, we provide such functionality for ALOHA protocols in an optimum manner for both cases: $(1)$ the case for applications where the number of tags is known and $(2)$ the case for applications where the number of tags is unknown.

In this paper, on one hand we take advantage of the adaptable frame length feature of ALOHA protocols, and on the other hand we profit the ability of the PDC scheme to reduce the number of active tags at a time. In this way, we take the best features of both paradigms in order to make ALOHA protocols work on the PDC approach.

We model the system as follows: we consider a system with an RFID reader placed at the center of the interrogation zone, covering n passive tags. We use the spherical approach to model the interrogation zone, which has a radius of R units and an area $A_R$ . The reader is able to identify every tag within the interrogation zone. The anticollision protocol used to solve collisions into each cluster is the EPC Gen2 standard. We also assume that the tags are scattered following a uniform distribution, since this represents the general case for the number of tags per cluster. Moreover, RFID networks with uniformly distributed tags are considered well modeled this way [8, 20]; scattering RFID tags in a different way is application-specific. It is important to remark that tag distribution only varies the number of tags per cluster, which in the worst case translates the PDC approach to the traditional centralized mechanism.

Likewise, to optimize the performance of ALOHA protocols we use both, the number of clusters, k, and the knowledge acquired along the identification process to estimate the number of tags within each cluster. Thus, we adapt the frame length according to the estimated number of tags to avoid the first identification cycle. Additionally, as we will see in the following sections, we can ignore the time required to compute the number of clusters and the power needed to cover a given area. This is because this process is executed during a phase previous to the identification process.

3.1. Unknown Number of Tags: Constant Number of Clusters

A constant number of clusters may be obtained by initializing either d or k. Thus, in both cases the number of clusters is constant and is given by

$$\begin{array}{cc}& k=\left\{\begin{array}{cc}⌈\frac{R}{d}⌉\hfill & \text{with}\hspace{0.17em}\hspace{0.17em}d>\mathrm{0}\hfill \\ K\hfill & \text{with}\hspace{0.17em}\hspace{0.17em}K\ge \mathrm{1}.\hfill \end{array}\right.\end{array}$$

(1)

On one hand, by setting d, we define different cluster areas $A_i\ne A_j$ , with $d_i=d_j$ , $\forall i\ne j$ :

$$\begin{array}{cc}& R\le {\displaystyle \sum }_i‍d_i.\end{array}$$

(2)

On the other hand, if we set k, we need to determine its value at the ith step, that is, the value of $d_i$ such that we get equal cluster areas $A_i=A_j$ , with $d_i\ne d_j$ , $\forall i\ne j$ . Then, let $r_i$ be the radius associated with the maximum area covered by cluster i; we want to guarantee that

$$\begin{array}{cc}& A_i=A_j,\hspace{1em}\forall i\ne j,\hspace{0.17em}\hspace{0.17em}i\in [1,\dots ,k],\end{array}$$

(3)

which means

$$\begin{array}{cc}& \pi r_1^2=\pi r_i^2-\pi r_{i-1}^2,\hspace{1em}i\in [2,\dots ,k].\end{array}$$

(4)

Then we get

$$\begin{array}{cc}& r_i=r_{\mathrm{1}}\sqrt{i},\hspace{1em}\mathrm{2}\le i\le k,\\ r_{\mathrm{1}}=\frac{R}{\sqrt{k}}.\end{array}$$

(5)

Proof by Induction

Base Case: Two Clusters. From (4), we know that $\pi r_{\mathrm{1}}^{\mathrm{2}}=\pi r_{\mathrm{2}}^{\mathrm{2}}-\pi r_{\mathrm{1}}^{\mathrm{2}}$ and $r_{\mathrm{2}}=R$ ; thus,

$$\begin{array}{cc}& \pi r_{\mathrm{1}}^{\mathrm{2}}=\pi r_{\mathrm{2}}^{\mathrm{2}}-\pi r_{\mathrm{1}}^{\mathrm{2}},\\ r_{\mathrm{1}}^{\mathrm{2}}=r_{\mathrm{2}}^{\mathrm{2}}-r_{\mathrm{1}}^{\mathrm{2}},\\ ⟹r_{\mathrm{2}}=r_{\mathrm{1}}\sqrt{\mathrm{2}},\\ r_{\mathrm{1}}=\frac{R}{\sqrt{\mathrm{2}}}.\end{array}$$

(6)

Inductive Step. For k clusters, we know that

$$\begin{array}{cc}& r_k=r_{\mathrm{1}}\sqrt{k}\end{array}$$

(7)

and, from (4), we know that $\pi r_{\mathrm{1}}^{\mathrm{2}}=\pi r_{k+\mathrm{1}}^{\mathrm{2}}-\pi r_k^{\mathrm{2}}$ and $r_{k+\mathrm{1}}=R$ ; thus,

$$\begin{array}{cc}& \pi r_{\mathrm{1}}^{\mathrm{2}}=\pi r_{k+\mathrm{1}}^{\mathrm{2}}-\pi r_k^{\mathrm{2}},\\ r_{\mathrm{1}}^{\mathrm{2}}=r_{k+\mathrm{1}}^{\mathrm{2}}-r_k^{\mathrm{2}}\\ ⟹r_{k+\mathrm{1}}^{\mathrm{2}}=r_{\mathrm{1}}^{\mathrm{2}}+r_k^{\mathrm{2}}\end{array}$$

(8)

and replacing (7) in (8) we get

$$\begin{array}{cc}& r_{k+\mathrm{1}}^{\mathrm{2}}=r_{\mathrm{1}}^{\mathrm{2}}+{\left(r_{\mathrm{1}}\sqrt{k}\right)}^{\mathrm{2}},\\ r_{k+\mathrm{1}}^{\mathrm{2}}=r_{\mathrm{1}}^{\mathrm{2}}+r_{\mathrm{1}}^{\mathrm{2}}k,\\ r_{k+\mathrm{1}}^{\mathrm{2}}=r_{\mathrm{1}}^{\mathrm{2}}(k+\mathrm{1})\\ ⟹r_{k+\mathrm{1}}=r_{\mathrm{1}}\sqrt{(k+\mathrm{1})},\\ r_{k+\mathrm{1}}^{\mathrm{2}}=r_{\mathrm{1}}^{\mathrm{2}}+{\left(r_{\mathrm{1}}\sqrt{k}\right)}^{\mathrm{2}},\\ r_{k+\mathrm{1}}^{\mathrm{2}}=r_{\mathrm{1}}^{\mathrm{2}}\left(k+\mathrm{1}\right),\\ r_{\mathrm{1}}=\frac{r_{k+\mathrm{1}}}{\sqrt{k+\mathrm{1}}}\\ ⟹r_{\mathrm{1}}=\frac{R}{\sqrt{k+\mathrm{1}}}.\end{array}$$

(9)

Thus, the value of $d_i$ associated with the ith step is

$$\begin{array}{cc}& d_i=r_i-r_{i-\mathrm{1}},\hspace{1em}\text{with}\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2},\dots ,k.\end{array}$$

(10)

In this case, i ranges from 2 to k since when $i=\mathrm{0}$ the coverage area is null, and when $i=\mathrm{1}$ the coverage area corresponds to the whole interrogation zone; both correspond to meaningless or not interesting cases, respectively. As we can see in Figure 3, $r_i<r_j$ , $r_k=R$ , and $d_i>d_j$ for $i<j$ .

Figure 3

Coverage areas for k clusters within the interrogation zone.

Figure 4 shows the cases for equal and different areas. As we can see in Figure 4(a), when d is constant, the areas are different. In this case, d is added to the current $R^{\prime }$ . When k is chosen, the reader computes $d_i$ in order to guarantee the same area for cluster i and cluster j ( $i\ne j$ ), as depicted in Figure 4(b). Again, $d_i$ is added to the current $R^{\prime }$ . We observe that $R^{\prime }\ge R$ when d is constant and $R^{\prime }=R$ for k constant.

Figure 4

Methods for partitioning the interrogation zone.

Indeed, we can estimate the total number of tags, $\widehat{n}$ , in the interrogation zone by exploiting both, the prior knowledge we just described and the number of identified tags in the first cluster, $m_{\mathrm{1}}$ . Additionally, with such information we can estimate the number of tags within each cluster, ${\widehat{m}}_i$ , since $m_{\mathrm{1}}$ is a fraction of the total number of tags. Therefore, by means of surface analysis the total number of tags is estimated according to the relationship between $A_R$ and $A_i$ . Hence, the estimation of the total number of tags is given by

$$\begin{array}{cc}& \widehat{n}=\left\{\begin{array}{cc}\frac{m_{\mathrm{1}}{A}_R}{A_{\mathrm{1}}}\hfill & \text{when}\hspace{0.17em}\hspace{0.17em}{A}_i\ne A_j\hspace{0.17em}\hspace{0.17em}\forall i\ne j\hfill \\ k{m}_{\mathrm{1}}\hfill & \text{when}\hspace{0.17em}\hspace{0.17em}{A}_i=A_j\hspace{0.17em}\hspace{0.17em}\forall i\ne j.\hfill \end{array}\right.\end{array}$$

(11)

Correspondingly, the estimated number of tags within the ith cluster is given by

$$\begin{array}{cc}& {\widehat{m}}_i=\left\{\begin{array}{cc}\frac{\widehat{n}{A}_i}{A_R}\hfill & \text{when}\hspace{0.17em}\hspace{0.17em}{A}_i\ne A_j\hspace{0.17em}\hspace{0.17em}\forall i\ne j\hfill \\ m_{\mathrm{1}}\hfill & \text{when}\hspace{0.17em}\hspace{0.17em}{A}_i=A_j\hspace{0.17em}\hspace{0.17em}\forall i\ne j.\hfill \end{array}\right.\end{array}$$

(12)

Once ${\widehat{m}}_i$ is known, we can profit such knowledge to run the EPC Gen2 protocol by setting the length of the first frame equal to the corresponding ${\widehat{m}}_i$ . In this way, we avoid the execution of an identification cycle to find a well suited frame length.

Algorithm 1 summarizes our proposal, which is comprised of two phases: tag set partitioning and identification process. During the first phase in lines 4–22, the end system splits the set of tags according to k. Then, during the second phase in lines 26–28, the reader executes the identification process for the first cluster and afterwards, in lines 32–36, it estimates the number of tags within each cluster. In line 38, the reader uses the number of tags within each cluster to compute the initial value of Q; then in lines 40–42 it executes the identification process for the rest of the clusters using the corresponding Q. The identification process is executed in an incremental way in order to cover the whole interrogation zone, with the end to guarantee that there is only one active zone at a time.

Algorithm 1: Interrogation zone division for an unknown cardinality of the set of tags.

Phase 1-Tag set partitioning

(1) $//$ Coverage area approximation according to (2) from [8]

(2) $R=ApproximateRadiusArea(P,Greader,Gtag)$

(3) $A_R=\mathrm{\pi }\times R^{\mathrm{2}}$

(4) if (Is d constant?) then                $\leftarrow$ Different Areas

(5)    $k=\lceil \frac{R}{d}\rceil$

(6)    $A_{\mathrm{1}}=A_{\text{Accum}}=\mathrm{\pi }\times d^{\mathrm{2}}$

(7)    $r_{\mathrm{1}}=d$

(8)   for   $i=\mathrm{2}$ to k  do

(9)      $r_i=i\times r_{\mathrm{1}}$

(10)    $A_i\simeq \mathrm{\pi }\times (i\times d{)}^{\mathrm{2}}-A_{\text{Accum}}$

(11)     $A_{\text{Accum}}=A_{\text{Accum}}+A_i$

(12)  end for

(13)   $w=\frac{A_{\mathrm{R}}}{A_{\mathrm{1}}}$

(14) else                       $\leftarrow$ Equal Areas

(15)   $d_{\mathrm{1}}=r_{\mathrm{1}}=\frac{R}{\sqrt{k}}$

(16)   $A_{\mathrm{1}}\simeq \mathrm{\pi }\times d_{\mathrm{1}}^{\mathrm{2}}$

(17)  for   $i=\mathrm{2}$ to k  do

(18)     $r_i=\sqrt{i}\times r_{\mathrm{1}}$

(19)     $d_i=r_i-r_{i-\mathrm{1}}$

(20)     $A_i\simeq \mathrm{\pi }\times d_i^{\mathrm{2}}$

(21)  end for

(22)   $w=k$

(23) end if

Phase 2-Identification Process

(24) $Q_{\text{ini}}=\mathrm{4}$                      $\leftarrow$ Required by EPCGEN2

(25) $Response=\text{TRUE}$

(26) while ( $Response=\text{TRUE}$ ) do

(27)   $[Response,m_{\mathrm{1}}]=EPCGEN\mathrm{2}(Q_{\text{ini}},r_{\mathrm{1}})$

(28) end while

(29) $//$ Estimation of the total number of tags

(30) $\widehat{n}=w\times m_{\mathrm{1}}$

(31) for   $i=\mathrm{2}$ to k  do

(32)  if (Is d constant?) then

(33)     ${\widehat{m}}_i=\widehat{n}\times \frac{A_i}{A_{\mathrm{R}}}$                 $\leftarrow$ Tags estimation in cluster i

(34)  else

(35)     ${\widehat{m}}_i=m_{\mathrm{1}}$

(36)  end if

(37) $//$ Set $Q_{\text{ini}}$ to the estimated number of tags in cluster i

(38)   $Q_{\text{ini}}=FindQ({\widehat{m}}_i)$

(39)   $R^{\prime }=r_i$                     $\leftarrow$ Increase the coverage area

(40)  while ( $Response=\text{TRUE}$ ) do

(41)     $[Response]=EPCGEN\mathrm{2}(Q_{\text{ini}},R^{\prime })$

(42)  end while

(43) end for

It is important to remember that previous to the identification process the end system performs Phase 1 from Algorithm 1. The delay spent during this phase is negligible because of two reasons. First, our proposal is $O(k)$ on the number of math operations. Second, k is limited to a practical value, so it may not become too large [20].

3.2. Known Number of Tags: Number of Clusters Based on the Population

As we mentioned above, the number of tags within the interrogation zone is generally unknown for most of the RFID applications. However, for a subset of them such data is known or it is estimated before the identification process; inventories or counting tasks are applications falling into this category. For such cases, we can exploit the knowledge about the number of tags within the interrogation zone, in order to execute the identification process in a faster way.

Since we know the number and the distribution of tags within the interrogation zone, we may improve the performance of the whole identification process by computing the number of clusters, such that the expected number of tags by cluster, $E[m]$ , is the same and less than a given threshold, assuming of course that all clusters have the same size. Let W be a constant that defines the threshold for the number of tags into each cluster, $E[m]$ must hold $E[m]\le W$ , and therefore the number of clusters is given by

$$\begin{array}{cc}& k\ge ⌈\frac{N}{W}⌉.\end{array}$$

(13)

From (13), we compute the number of clusters and from (5) we can find the clusters area. Since the expected number of tags within each cluster will be less than or equal to W, we may use the EPC Gen2 standard with a frame length equal to W in order to achieve the maximum system throughput. However, this does not work very well because the number of tags within the interrogation zone decreases as the process evolves. Hence, we may improve the performance of EPC Gen2 by starting the identification process in each cluster with a frame length equal to the expected number of tags within each of them, and afterwards we may use any mechanism to adapt the frame length for the rest of identification process. Notice that W is of great importance since it defines the initial frame length in each cluster.

The corresponding pseudocode is given in Algorithm 2. The first phase, in lines 5–13, is a prephase of the identification process during which the end system computes the number of clusters according to the total number of present tags and the expected number of tags within each cluster. The second phase, in line 14, corresponds to the identification process, where the reader computes the initial value of Q in order to start the identification for each cluster. Finally, in lines 17–19, the reader executes the identification process in each cluster using the corresponding value of Q.

Algorithm 2: Interrogation zone division for a known cardinality of the set of tags.

Phase 1-Tag set partitioning

(1) $//$ Coverage area approximation according to (2) from [8]

(2) $R=ApproximateRadiusArea(P,Greader,Gtag)$

(3) $A_R=\mathrm{\pi }\times R^{\mathrm{2}}$

(4) $N=NumberOfTags()$             $\leftarrow$ Total number of tags

(5) $Threshol{d}_{{\widehat{m}}_i}=W$          $\leftarrow$ Desired number of tags per cluster

(6) $k\ge \lceil \frac{N}{Threshol{d}_{{\widehat{m}}_i}}\rceil$

(7) $d_{\mathrm{1}}=r_{\mathrm{1}}=\frac{R}{\sqrt{k}}$

(8) $A_{\mathrm{1}}\simeq \mathrm{\pi }\times d_{\mathrm{1}}^{\mathrm{2}}$

(9) for   $i=\mathrm{2}$ to k  do

(10)    $\mathrm{\hspace{0.17em}\hspace{0.17em}}{r}_i=\sqrt{i}\times r_{\mathrm{1}}$

(11)    $d_i=r_i-r_{i-\mathrm{1}}$

(12)    $A_i\simeq \mathrm{\pi }\times d_i^{\mathrm{2}}$

(13) end for

Phase 2-Identification Sequence with PDC-Scheme

(14) $Q_{\text{ini}}=FindQ(Threshol{d}_{{\widehat{m}}_i})$

(15) for   $i=\mathrm{1}$ to k  do

(16)      $R^{\prime }=r_i$                  $\leftarrow$ Increase the coverage area

(17)     while ( $Response=\text{TRUE}$ ) do

(18)      $[Response]=EPCGEN\mathrm{2}(Q_{\text{ini}},R^{\prime })$

(19)     end while

(20) end for

As in Algorithm 1, Phase 1 from Algorithm 2 is performed by the end system as a prephase of the identification process. Additionally, we find that Phase 1 is $O(k)$ ; thus we can conclude that the time needed to perform such phase is also negligible.

4. Evaluation

In this section, we evaluate the performance of our proposal. We evaluate the EPC Gen2 standard for both, the traditional centralized scheme and our proposal on the PDC scheme. The main goal is to show the improvement obtained with EPC Gen2 when the interrogation zone is divided in an optimal way. We take the identification delay as the main performance measure. The identification delay is the time needed to discover the whole set of RFID tags in the reader's coverage range. The identification delay is measured starting from the time the first query is sent by the reader until the time the last response is issued by the last unidentified tag. In order to do this, since the identification cycle is a function of the number of used slots and the messages exchanged among reader and tags, we express the identification cycles in absolute time.

Therefore, we choose Matlab to deploy the protocols to evaluate as follows.

• (i)

We implement two versions of the EPC Gen2 standard. We call the first one EPCGen2; it uses the Q protocol as mechanism to adapt the frame length in each identification cycle. The second version we implement, EPCGen2Q, uses the heuristic proposed in [23] along with the estimation function of [26] as mechanism to adapt the frame length. Also, we consider the following cases.

• (1)

$Q_{\text{ini}}=\mathrm{4}$ . The standard requires to set the initial value of Q to four; that is, $Q_{\text{ini}}=\mathrm{4.0}$ . Thus, regarding EPCGen2 we use such initial value for the identification process in each cluster.

(2)

$Q_{\text{ini}}={\widehat{m}}_i$ . In order to exploit the advantages of the PDC scheme, since we may estimate the number of tags into each cluster, we modify EPCGen2Q to start with a different $Q_{\text{ini}}$ value, $Q_{\text{ini}}={\widehat{m}}_i$ . Thus, we use $Q_{\text{ini}}={\widehat{m}}_i$ to execute the identification process in each cluster. We call this new protocol EPCGen2QMod.

(ii)

We consider an RFID reader placed at the center of the interrogation zone with a coverage range of 10 meters.

(iii)

For the case when the number of clusters is constant,

• (1)

we vary the step, d, in the range $[\mathrm{0.2},\dots ,\mathrm{1.0}]$ meters;

(2)

we vary the number of clusters, k, from 10 to 50.

(iv

For the case when the number of clusters is based on the population,

• (1)

we vary W from 15 to 255. We choose these values according to the results obtained in a previous work [27], which concludes that a well suited value to start the identification process is $Q=\mathrm{7}$ .

(v)

From [22], if we set the number of subcarrier cycles per symbol to $M=\mathrm{2}$ , it is possible to approximate to 0.575 ms the time spent by both an empty and a collision slot, while for a single slot such value is approximated to 2.505 ms.

(vi)

We assume that all the participant devices have a coherent clear channel assessment (CCA); that is, the channel is busy when a packet's preamble is detected.

(vii)

We consider that the network is free of the capture effect, since such phenomenon impacts the identification process in an RFID network. The capture effect occurs when two or more tags transmit simultaneously to a reader, and one of them succeeds because it has favorable physical conditions.

(viii)

In order to get reliable results, we run each protocol for $\mathrm{3}\times \mathrm{1}{\mathrm{0}}^{\mathrm{5}}$ times so we get confidence intervals above 95%.

5. Results

5.1. The Case of Constant d and Constant Number of Clusters k

(1) EPC Gen2. In Figure 5, we plot the identification delay for the EPCGen2 for different values of d. As we can see, the best results are obtained with $d=\mathrm{0.2}$ for almost all sets of tags. Additionally, with $d=\mathrm{1.0}$ there is a better behavior when the number of tags is greater than 1400 tags. Such behavior suggests that for the lowest number of tags it is better to use the lowest value of d, while as for highest number of tags it is better to use the highest value of d. Even if we can get a lower identification delay with the lowest value of d, its highest value exhibits a better behavior since the protocol quickly reaches a stable frame length.

Figure 5

EPC Gen2 with constant d.

Next, we plot the identification delay for the EPCGen2 protocol in Figure 6 for different values of k. As we can see, the best results are obtained with the highest value of k. The reason is that when there are more clusters, there are less tags as well in each of them, which results in a lower identification delay. Again, notice that when the number of tags is greater than 1800, it is better to choose $k=\mathrm{10}$ since EPCGen2 reaches faster a steady frame length.

Figure 6

EPC Gen2 with constant k.

(2) EPC Gen2 with Optimal Q. Figure 7 plots the identification delay for the EPCGen2Q protocol. We can clearly see that the better results are obtained with $d=\mathrm{0.2}$ , with the exception of $d=\mathrm{1}$ for the range of 100 to 300 tags. Such behavior suggests that the EPCGen2Q protocol scales very well with the tags density. Thus, when we reduce the number of participating tags by partitioning the interrogation zone, additional time is needed in order to identify them separately.

Figure 7

EPC Gen2 with optimal Q and constant d.

In Figure 8, we can see the identification delay for the EPCGen2QMod protocol. Notice that the lower identification delay is obtained when $d>\mathrm{0.4}$ . For this case, it seems we reach a limit for the identification delay since the results for different values of d are very similar.

Figure 8

EPC Gen2 with optimal Q adapted to start with a frame length equal to the estimated number of tags and constant d.

Now, let us see in Figure 9 the identification delay for the EPCGen2Q protocol for different values of k. We can see a behavior similar to the EPCGen2Q protocol with different values of d. It is clear that the best result is achieved with $k=\mathrm{50}$ , when the number of tags is greater than 500. When the number of tags is below 500, the behavior with respect to k is variable.

Figure 9

EPC Gen2 with optimal Q and constant k.

The behavior of the EPCGen2QMod protocol for different values of k is shown in Figure 10. There is a great improvement on the identification delay with $k=\mathrm{50}$ ; we can see that, for most of the values of N, choosing $k=\mathrm{50}$ allows to get improvements of up to 500 ms.

Figure 10

EPC Gen2 with optimal Q adapted to start with a frame length equal to the estimated number of tags and constant k.

5.2. Number of Clusters, k, as a Function of the Population

(1) EPC Gen2. We evaluate now the EPCGen2 protocol for the case when the number of tags is known. Thus, the EPCGen2 protocol is evaluated for different values of W. Figure 11 shows the corresponding results, where we see that the best results are obtained when $W<\mathrm{16}$ . This happens because such choice for W avoids a fast growth of the frame length and allows for a reduction of the probability of collisions. EPCGen2 exhibits its best performance when the expected number of tags per cluster is less than 32.

Figure 11

EPC Gen2 with optimum k and initial Q.

(2) EPC Gen2 with Optimal Q. Finally, we plot in Figure 12 the performance of the EPCGen2QMod protocol for different values of W. It is clear that the best performance is achieved when $W<\mathrm{16}$ . In this case, the improvement is small compared with the EPCGen2Q protocol when it operates with a priori knowledge. This case scales very well with tags density.

Figure 12

EPC Gen2 with optimal Q, optimum k, and initial Q.

6. Conclusions

Power distance clustering (PDC) has shown to be very promising to improve the performance of radio-frequency identification (RFID) systems. However, to our best knowledge, PDC has been mainly evaluated with nonstandard protocols and barely evaluated with an ALOHA-based approach. Thus, in this paper we proposed a full implementation of an optimum ALOHA-based protocol for RFID working with the EPC Gen2 requirements under the PDC approach. On one hand, our proposal optimizes the time spent of the EPC Gen2 standard and on the other hand it respects all the features required by the standard; that is, we keep the standard unmodified. Consequently, the features of our proposal are of great utility over other proposals in the literature, since an implementation based on it might be done seamlessly thanks to the standard.

Additionally, we found an optimal way of splitting an interrogation zone using ALOHA-based protocols along with a PDC approach. Such splitting spends a minimal delay and it may be executed as a prephase of the identification process.

Our evaluations have demonstrated that the performance of ALOHA-based protocols improves when there exists additional information about the interrogation process, like number of tags and their distribution. Similarly, we have shown the advantages of using the knowledge acquired during the identification process, like the number of identified tags. In such sense, we found that we may avoid the first identification cycle if we start the identification process with a Q value based on the collected information, which improves all the identification process by reducing collisions, empty slots, and consequently the identification delay.

Finally, we found the lower limit of ALOHA-based protocols for an identification process executed with the PDC approach. Such limit is reached when there is the largest number of subzones within the interrogation range of the reader, which is a consequence of the nature of ALOHA-based protocols in optimal conditions for the traditional approach.