The Performance of Collision Arbitration for ISO/IEC 18000-6 RFID Standard

The Performance of Collision Arbitration for ISO/IEC 18000-6 RFID Standard

Chiang Ling Feng

Department of Electronic Engineering, ChienKuo Technology University, Taiwan

AbstractFor multiple random accesses, a low throughput due to channel contention is the major limitation. The most latency occurs in the contention phase and, therefore, reducing the delay time thus becomes a relevant task. A collision occurs in real network access if two or more packets are simultaneously transmitted. Hence, the contention must be resolved when applying a protocol in the wireless data network. RFID anti- collision of ISO/IEC 18000-6 [1-2] adopts the concept of tree [3] expansion in to reduce the delay time and enhance the throughput. Analyses results indicate that the variety of the mean delay time performance is insignificant related to its probability factors. However, the impact on the throughput performance due to these probability factors is significant.

KeywordsRFID; anti-collision; throughput; mean delay time; tree elimination algorithm

1. INTRODUCTION

   Basic RFID [4-6] typically consists a reader and tags. Tag becomes activate after it receives a command which is initiated from a reader. For a passive tag, the energy to make the tag to be activated is gained from the transmitted power of reader by coupling. In a RFID system, RFID reader is required to identify multiple tags in a given period of time simultaneously. If a transmission channel is simultaneously accessed by multiple tags within the range of a reader, mutual interferences incurred and this phenomenon is known as tag collision. To resolve the collision problems is a crucial issue to a RFID reader network system.

   When considering the sharing of bandwidth in random access network communication, throughput performance and mean delay time are two critical factors. Therefore, the collision resolution algorithm must be used to obtain the system performance of the multiple access schemes. In this paper, we will analyze the system performance of RFID anti- collision of ISO/IEC 18000-6 that adopts the concept of tree expansion in to reduce the delay time and enhance the throughput.

   The rest of this paper is organized as follows. Section 2 describes the operation of RFID anti-collision of ISO/IEC 18000-6. Section 3 illustrates the relationship among the delay-throughput characteristics for RFID anti-collision of ISO/IEC 18000-6. Numerical results are presented in Section

   4. Concluding remarks are finally made in Section 5.

2. ANTI-COLLISION PROCEDURE

   A means of enhancing the system performance is to resolve the probability of contending packets. According to information theory, the more pertinent information which is

   available to describe the observed event allows us to more accurately estimate the event. In real network access, a collision may occur if two or more packets are simultaneously transmitted at the same slot. Hence, how to resolve the contention collision is a relevant issue when applying a protocol in the wireless data network.

   In the ISO/IEC 18000-6 international standard, the collision arbitration be briefly summarized as follows.

   Step 1: When the interrogator initiates a tag census to these selected tags, these tags with counter at 0 will transmit their ID.

   Step 2a: If more than one tag transmits simultaneously, the interrogator may detect the collisions and receives the erroneous contention from multiple transmissions. Then, the interrogator will respond a FAIL command to these tags. Go to Step 3a.

   Step 2b: If only one tag transmits its ID and the transmitted ID is correctly received by the interrogator, the interrogator sends a DATA_READ command with the received ID to the corresponding tag. Then go to Step 3b. Otherwise, if only one tag transmits its ID and the transmitted ID is erroneously received by the interrogator, the interrogator sends a RESEND command with the received ID to the corresponding tag. If the number to a RESEND command with the same received ID excesses the level of error handling for the system, the interrogator assumes that more than one tag transmit simultaneously, and go to Step 2a.

   Step 2c: If no reply is received by the interrogator, it means that no tag with counter at zero exists. The interrogator sends a SUCCESS command to all tags which enter the energizing field of the interrogator. Go to Step 3c.

   Step 3a: Tag will randomly generate a number (just 0 or 1 can be generated) from its random generator when it detects its contention is failed. When a tag rolls 1 with probability 1-pc from its random generator, the content of counter increases one. The counter will keep its counter at zero if the tag rolls 0 with probability pc.

   Step 3b: If the transmitted DATA_READ command is correctly received by the corresponding tag, the tag will transient to DATA_EXCHANGE state and then transmit its data.

   Step 3c: When tags receive the SUCCESS command from the interrogator, the value of counters decreases one.

   Step 4: Step 1 repeats.

   The detailed flow chart is given as Fig. 1. To analyze the protocol, we assume that these tags have to randomly generate a number from its random generator before the interrogator initiating a tag census.

   cycle, for completely serving all tags in which are located within the coverage of a specified interrogator. Now, let us consider the case that there are n tags being selected by the interrogator at the beginning of performed collision arbitration. Assume that there are nd tags with counter 0. Among these nd tags, assume that there are nf tags receiving RESEND command from the interrogator with probability p,

   and nd – nf tags receiving a DATA_READ command from the interrogator with probability 1-p. While considering n tags

   within the coverage of a RFID reader and neglecting the situation of nf = 0, the following cases should be considered independently.

   Case 1: nd = 0

   In this case, it means that no tags with counter at zero exist. Therefore, the time to completely serve these n tags for a round cycle under the condition that there are nd non-collision tags is given as

   n

   n

   poll max

   poll max

   T n | nd 0 1- pc t t T n

   Case 2: nd = 1

   (1)

   In this case, it means that just one tag with counter at zero exists. Therefore, the time to completely serve these n tags for a round cycle under the condition that there are nd tags with counter 0 is given as

   Fig. 1. The detailed flow chart of ISO/IEC 18000-6 Collision Arbitration

3. SYSTEM PERFORMANCE

   In this section, we establish a system model to obtain the performance of system. All tags are assumed to be independent and identical sources, in which each tag has exactly a packet with a fixed packet length to be transmitted at any time. Herein, the packet of a tag is immediately generated after receiving the polling command from the interrogator which covers the tag. In this manner, a perfect physical transmission to generate the polling request from the interrogator is assumed. However, an imperfect physical transmission to receive the generated packet from a tag is assumed.

   T n | nd 1 npc 1- pc t t T n 1 (2) Case 3: nd 2

   n-1

   n-1

   poll s

   poll s

   In this case, it means that there is more than one tag with counter at zero exists. These tags will randomly generate a random number (just 0 or 1 can be generated) from its random generator when it detects its contention to be failed. The probability that a tag rolls 1 is 1-pc from its random generato, the content of counter increases one. The counter will keep its counter at zero if the tag rolls a zero with probability pc. Since the counters at one among these tags which roll 1 will rejoin the contention with other n – nd tags, the time to completely serve these n tags for a round cycle under the condition that there are nd tags with counter 0 is given as [7-9].

   nd

   nd n

   n n

   1. ISO/IEC 18000-6 standard

      n

      t

      t

      p d 1 1 p d

      d1

      T n | n 2 pnd 1 p n nd

      poll c

      n c c

      n c

      n c

      In general, throughput and average delay time largely

      d

      d

      c

      T(n | n

      nd1 0 d1

      0) T(n | n 1) T (n | n

      2

      justify a systems robustness. Denote ts to be the ID packets transmission time of a tag, tc to be the packets collision

      d d1

      d d1

      d d1

      (3)

      period. Let tpoll be the time, including the propagation time, to

      poll the tags with counter at zero. Denote tmax is the time to justify that no tags with counter at zero exist. is the

      Combining cases 1, 2, and 3, the time to completely serve these n tags for a round cycle is given as

      maximum propagation delay and tf is the time to justify the transmitted ID packet is erroneously received the transmitted ID from the tag and to process it. In addition to include the

      T n T(n | nd

      0) T(n | nd

      1) T(n | nd nd 2

      0)

      (4)

      n

      n

      propagation time and processing interrogator and tags, the times ts and tc include the time of transmitted DATA_READ command, and transmitted RESEND command or transmitted FAIL command, respectively. Time tf includes the propagation time, processing interrogator and tags and the time to send a SUCCESS command.

   2. Throughput performance

      We define the throughput as the ratio of expected successful transmission duration to the total time, denoted as a round

      Consider the condition that there are n students in a

      classroom and nf 0. Assume that all tags counters are at zero at the beginning of the initiation polling cycle. Denote the probability p is the probability that only one tag transmits its ID and the transmitted ID is erroneously received by the interrogator. Then, the probability 1-p is the probability that the interrogator can successfully access a tag. In this situation, we only modify the case 1 of nf = 0. Therefore, the time to completely serve these n tags for a round cycle is given as

      d c c s f

      d c c s f

      T n | n 1 np 1- p n-1(1 p) T (n 1) p(

      T (1) T (n 1))

      (5)

      probability that a tag rolls 1 is 1-p from its random generator, the content of counter increases one. The counter will keep its

      (1 p) s p f pT (1) T (n 1)

      where

      s t poll ts

      (6)

      counter at zero if the tag rolls a zero with probability p. Since the counters at one among these tags which roll 1 will rejoin the contention with other n – nd tags, the delay time to serve

      these n tags under nd2 is given as

      f tpoll t f

      (7)

      nd

      nd n

      n n

      n

      p d 1 1 p d

      d1

      X n | n

      2 pnd 1 p n nd c

      n c c

      (8) d

      n c

      c nd1 0 d1

      max t poll tmax

      d

      X (n | n 0) X (n | n 1) X (n | n 2

      Let

      d d1

      d d1

      d d1

      H(n) H(n) |m0

      n

      n

      H (n) |m (1 pc ) max T (n | nd 1)

      (9)

      (10)

      (16)

      Combining cases 1, 2, and 3, we obtain the time to completely serve these n tags for a round cycle is given as

      pc m 1 p

      pc m 1 p

      n n n

      n n

      d d m H (n ) |

      c

      c d m m m1

      c

      c d m m m1

      n (17)

      and

      nd m 0 ndm

      1 p nd

      X n X (n | nd 0) X (n | nd 1) X (n | nd 0)

      nd 2

      Consider the condition that there are n tags within the

      coverage of a reader and nf 0. Assume that all tags

      n n c

      (11)

      Y (n) 1 p n p nd 1 p nnd n n

      counters are at zero at the beginning of the initiation polling

      c n c c

      d p nd1 1 p nd nd1 1 p nd1

      We have

      nd 2 d

      c c

      n

      n

      nd1 2 d1

      H n

      c

      (12)

      cycle. Denote the probability p is the probability that only one tag transmits its ID and the transmitted ID is erroneously received by the interrogator. Then, the probability 1-p is the probability that the interrogator can successfully access a tag.

      T n

      1- Y n

      In this situation, we only modify the case 1 of nf = 0. Therefore, the time to completely serve these n tags for a

      Under a steady state, the average time ratio of non- collision packet periods in a mean round cycle is called the

      round cycle is given as (17), excepting

      d

      d

      c

      c

      c

      c

      s

      s

      f

      f

      X n | n 1 np 1- p n-1(1 p)(n 1) X (n 1) p(n

      X (1) X (n 1))(18

      throughput. According to the definition of throughput, we have [9]

      )

      (1 p)n 1 s pn f

      pX (1) X (n 1)

      throughput n

   3. Delay performance

   nts

   T n

   (13)

   Let

   n

   n

   H1 (n) |m (1 pc ) max X (n | nd 1)

   (19)

   pc m 1 p

   pc m 1 p

   n n n

   nn

   Allow X(n) to be the delay time to serve these n tags. While

   d

   n

   n

   c

   c

   n 0 d

   d m

   H (n ) |

   H (n ) |

   c 1 d m mm1

   considering n tags within the coverage of a RFID reader and neglecting the situation of nf = 0, the following cases should be considered independently.

   Case 1: nd = 0

   In this case, it means that no tag with counter at zero exists. Therefore, the mean delay time to serve these n tags under

   nd 0 is given as

   d m

   then

   Therefore,

   m

   H1 (n) H1 (n) |m0

   X n H1 n

   1- Y n

   (20)

   (21)

   c

   c

   Case 2: nd = 1

   X n | nd

   0 1- p n n

   max

   X n

   (14)

   Moreover, one of these tags may have one packet to be transmitted during round cycle. Based on this condition, the renewal process is appropriate for calculating a packets mean waiting time. Assume that our system is a closed

   In this case, it means that just one tag with counter at zero

   exists. Therefore, the delay time to serve these n tags under

   system, therefore, W(n) = 0, and the mean delay time of a tag can be expressed as

   nd 1 is given as

   X n | n 1 np 1- p n-1n 1 X n 1

   (15)

   Dn

   X n n

   (22)

   Case 3: nd 2

   d c c s

4. NUMERICAL RESULTS

   In this case, it means that there is more than one tag with counter at zero exists. These tags will randomly generate a random number (just 0 or 1 can be generated) from its random generator when it detects its contention is failed. The

   This section evaluates the performance of anti-collision protocols with ISO/IEC 18000-6 standard. Subsequent impacts on the performance of anti-collision protocols with ISO/IEC 18000-6 standard among a variety of the number of polled tags and the system are examined by considering

   different response probabilities. According to our results, we change only one parameter and maintain the others unchanged to clarify the effect of the changed parameter as much as possible for each comparison.

   The first comparison is made by varying the valu of pc. The relationships between throughput and the number of tags are shown in Fig. 2 and Fig. 4. The relationships between the mean delay time and the number of tags are shown in Fig. 3 and Fig. 5. These results demonstrate that the throughput decreases when the number of tags increases. From Fig. 2 to Fig. 5, if there are a few tags are polled by the RFID integrator at the beginning of anti-collision procedure, the more the probability pc is, the better the throughput performance is. Otherwise, the performance will increase according to the decrease of pc. It is intuitive that if the probability of pc is, the larger the number of tags with counter zero is. This phenomenon reflects a situation in which the probability of colliding packets decreases. From this result, we also knew that the tradeoff is between pc versus the number of tags.

   In addition, From Fig.2 to Fig. 5, the impact on the throughput performance due to probability p is also significant. The less the probability p is, the better the throughput performance is. Therefore, the value of p is a prerequisite for reducing the delay and obtaining the maximum throughput. Figures also reveal that the variety of the mean delay time performance is insignificant when the numbers of the tags within the coverage of the interrogator is less than a level. These figures also depict that the variety of the mean delay time performance is insignificant related to parameters p and pc.

   The second comparison is performed by varying the value of tc. From Fig. 4 to Fig. 7, the smaller time factor tc implies a better performance of the protocol. This is attributed to that the probability of generating the collision packet is more than the probability of generating the transmitted successful packet periods. Therefore, the performance increases by reducing the time of collision detection.These figures also reveal that the time factor tc is most important factor to the performance of the protocol than that of pc.

   Fig.2. The throughput performance of the protocol for various pc for p=0.3

   Fig. 3. The man delay performance of the protocol for various pc for p=0.3

   Fig. 4. The throughput performance of the protocol for various pc for p=0.5

   Fig. 5. The man delay performance of the protocol for various pc for p=0.5

   To see the impact on the performance of anti-collision protocols with ISO/IEC 18000-6 standard, the third comparison is made by varying the value of tf based on the condition of p0. It is intuitive that if the number of tags do not surpass the pre-defined level of tags in the system, then

   the performance is largely enhanced when pc becomes larger. Otherwise, the performance decays rapidly when pc becomes larger. This phenomenon is found to be the same as that of p=0. However, reducing the value of tf can strongly enhance the system performance. We also believe that if the time factor tf exceeds the packet length ts, then the performance decays rapidly (not shown in this paper).

   Fig. 6. The throughput performance of the protocol for tc=0.2ts and p=0.5

   Fig. 7. The man delay performance of the protocol for tc=0.2ts and p=0.5

   The final comparison is made to compare the impacts on the system performances between time factor tf and time factor tc. Based on the same conditions, from Fig. 6 to Fig. 9, these figures illustrate that the system performance decays related to the increment of pc. Instead of the result of tf, the system performance is enhanced according to the increment of pc. We also see that the time factor tf more profoundly influences the system performance time factor tc.

   Fig. 8. The throughput performance of the protocol for tf=0.2ts and p=0.5

   Fig. 9. The man delay performance of the protocol for tf=0.2ts and p=0.5

5. CONCLUSIONS

This paper presents the impact on the system performance among time factor tc, time factor tf, the probability p, the probability pc and the number of tags at the beginning of anti- collision procedure which is initiated by the RFID integrator. A preferred choice is studied to examine the influence of this protocol. For ISO/IEC 180006-6, the fact that we adopt tree algorithm to resolve the colliding packets in the contention phase institutively accounts for why the contention time can be largely reduced. It is intuitive that the lesser amount of contention time implies a higher throughput performance. In addition, in order to enhance system performance, the collision resolution strategy should be used to reduce the contention time, tc, and reduce the time, tf, to justify the transmitted ID packet is erroneously received the transmitted ID from the tag and to process it. If not, collision time seriously degrades the system performance. In addition, these important factors are available to enhance the system performance.

REFERENCES

universities using RFID, RFID Eurasia, 1st Annual, pp. 1-6, 5-6 Sept. 2007.