ALOHA Anti-collision Algorithm
161
The method of random post recognition to address the problem of tag collisions in
mobile scenarios was proposed initially [1]. Further, measures were adopted to group the
tags and optimize the ordering of the tag groups, which diminish the randomness of tag
recognition, thereby reducing the tag loss rate (TLR). However, these measures provided
no fundamental solution to the problem of tag-recognition collisions. Therefore, an RFID
anti-collision algorithm [2], grouped adaptive allocating slots (GAAS), was proposed
based on packet adaptive allocation of time slots. GAAS removes idle slots in a frame and
concentrates all collision tags into one time slot. The adaptive allocation of operational
time slots effectively improves the tag’s throughput and recognition rate. However, it
does not result in 100% throughput reading, thus the tag’s recognition rate can also be
further improved. To this end, a combined chaotic mapping pseudo-random generator
that combines the pseudo-random numbers of the Tent and infinitely folded chaotic
maps was proposed [3]. Compared to traditional generators, this generator improves
the uniformity of the pseudo-random numbers. Specifically, the tag to select the time
slot can be more uniform, the collision time slot is reduced to a certain extent, and the
throughput and recognition rate of the tag are improved.
In this paper, we propose an ALOHA anti-collision algorithm for frame idle slot
removal and collision reduction (CIRC-FSA) based on the GAAS anti-collision algorithm with self-adaptive packet allocation. The tags of CIRC-FSA algorithm are initially
grouped and the number of labels X in a group is determined by counting the number
of acknowledgment code (ACK) signal bars returned by the earliest group label. The
frame length L is set to be much greater than the group tag number X (L >> X).
Subsequently, adopting a combined chaotic mapping pseudo-random generator to more
evenly distribute the tags among each time slot remarkably reduces or avoids collisions.
Finally, the proposed GAAS-based algorithm removes idle and collision slots in the
frame, further improving the tag throughput and recognition rate.
2 Principle of Algorithm
2.1 Principle of Tag Grouping
The principle of ordering tag groups is based on circular queues, where the reader assigns
different grouping numbers according to the sequence of time periods when tags enter
the signal area. The grouping interval is the period of the tag group order (PTGO). A
first-come-first-served tag group means that the next tag group can be identified only
after the current earliest tag group (grouped number (GN) = head) is identified.
As shown in Fig. 1, according to the derivation, when the frame length L is larger,
the probability of the label selecting the same slot is smaller. It can be seen from the
simulation analysis that when the multiple, R, of time slots is more than five times that
of the labels, L ≥ 5N, collision of labels can be avoided to the greatest extent. Based
on the grouping order, the reader determines whether the number of tags X in a group
is larger than 100. If so, the reader sends the command Sleep (X/2), and half of the
tags are randomly silenced to participate in the next frame identification; otherwise, no
processing is performed.
161
The method of random post recognition to address the problem of tag collisions in
mobile scenarios was proposed initially [1]. Further, measures were adopted to group the
tags and optimize the ordering of the tag groups, which diminish the randomness of tag
recognition, thereby reducing the tag loss rate (TLR). However, these measures provided
no fundamental solution to the problem of tag-recognition collisions. Therefore, an RFID
anti-collision algorithm [2], grouped adaptive allocating slots (GAAS), was proposed
based on packet adaptive allocation of time slots. GAAS removes idle slots in a frame and
concentrates all collision tags into one time slot. The adaptive allocation of operational
time slots effectively improves the tag’s throughput and recognition rate. However, it
does not result in 100% throughput reading, thus the tag’s recognition rate can also be
further improved. To this end, a combined chaotic mapping pseudo-random generator
that combines the pseudo-random numbers of the Tent and infinitely folded chaotic
maps was proposed [3]. Compared to traditional generators, this generator improves
the uniformity of the pseudo-random numbers. Specifically, the tag to select the time
slot can be more uniform, the collision time slot is reduced to a certain extent, and the
throughput and recognition rate of the tag are improved.
In this paper, we propose an ALOHA anti-collision algorithm for frame idle slot
removal and collision reduction (CIRC-FSA) based on the GAAS anti-collision algorithm with self-adaptive packet allocation. The tags of CIRC-FSA algorithm are initially
grouped and the number of labels X in a group is determined by counting the number
of acknowledgment code (ACK) signal bars returned by the earliest group label. The
frame length L is set to be much greater than the group tag number X (L >> X).
Subsequently, adopting a combined chaotic mapping pseudo-random generator to more
evenly distribute the tags among each time slot remarkably reduces or avoids collisions.
Finally, the proposed GAAS-based algorithm removes idle and collision slots in the
frame, further improving the tag throughput and recognition rate.
2 Principle of Algorithm
2.1 Principle of Tag Grouping
The principle of ordering tag groups is based on circular queues, where the reader assigns
different grouping numbers according to the sequence of time periods when tags enter
the signal area. The grouping interval is the period of the tag group order (PTGO). A
first-come-first-served tag group means that the next tag group can be identified only
after the current earliest tag group (grouped number (GN) = head) is identified.
As shown in Fig. 1, according to the derivation, when the frame length L is larger,
the probability of the label selecting the same slot is smaller. It can be seen from the
simulation analysis that when the multiple, R, of time slots is more than five times that
of the labels, L ≥ 5N, collision of labels can be avoided to the greatest extent. Based
on the grouping order, the reader determines whether the number of tags X in a group
is larger than 100. If so, the reader sends the command Sleep (X/2), and half of the
tags are randomly silenced to participate in the next frame identification; otherwise, no
processing is performed.