ALOHA Anti-collision Algorithm
165
Step 6: The reader sends a tag slot adjusting (Adjust_slot) command. After receiving
the command, the tag to be identified changes the communication-slot according to the
st array. If the tag selected an unsuccessful time slot, the tag adjusts the time slot to
be L 0 . Otherwise, the tag calculates the number of collision and idle slots f before the
selected time slot, while adjusting the time slot to be (i–f).
3) Tag-recognition phase
Step 7: The reader sends a frame-recognition-start command Query (L0), and successfully identified tags are in a silent state and no longer respond to the reader’s
instructions.
Step 8: The reader performs two checks in sequence:
(1) The reader checks whether the cumulative number of used slots (Slot_i) is an
integer multiple of the PTGO ordering period of the tag group:
a. If yes, the reader sends a tag group order to command and then performs a check
(2).
b. If no, no operation is performed, checks directly (2).
(2) The reader checks whether the current frame ends:
a. If yes, is there a collision of the current frame recognition process? If yes, the
reader’s head remains unchanged, and the next frame continues to identify the current
group; otherwise, the reader modifies head = mod (head + l, 16), and determines whether
the head is equal to the rear. If yes, go to end; otherwise, go to Step 4.
b. If no, the reader sends a command (Query_Rep), and the reader identifies the next
time slot of the current frame.
Step 9: When the label of the earliest group in the signal area receives the Query_Rep
command, the tag decrements the slot counter by one. The tag with a slot counter of
zero responds to the reader, and then performs Step 8.
4 Algorithm Analysis
Slots consist of three states: idle slots are those without tags, successful time slots are
chosen by a tag, and collision slots are chosen by multiple tags. According to inference,
the probability that K tags choose the same time slot is as follows:
P(L,N,K) = C
K
N ×
1
L
K
×
1 −
1
L
N−K
(1)
where L is the frame length, N is the total number of tags, and K is the number of tags
in the same time slot. The probability of deriving three types of time slots is as follows:
When K = 0, the probability of an idle time slot is,
P i = P(L,N,0) =
1 −
1
L
N
(2)
165
Step 6: The reader sends a tag slot adjusting (Adjust_slot) command. After receiving
the command, the tag to be identified changes the communication-slot according to the
st array. If the tag selected an unsuccessful time slot, the tag adjusts the time slot to
be L 0 . Otherwise, the tag calculates the number of collision and idle slots f before the
selected time slot, while adjusting the time slot to be (i–f).
3) Tag-recognition phase
Step 7: The reader sends a frame-recognition-start command Query (L0), and successfully identified tags are in a silent state and no longer respond to the reader’s
instructions.
Step 8: The reader performs two checks in sequence:
(1) The reader checks whether the cumulative number of used slots (Slot_i) is an
integer multiple of the PTGO ordering period of the tag group:
a. If yes, the reader sends a tag group order to command and then performs a check
(2).
b. If no, no operation is performed, checks directly (2).
(2) The reader checks whether the current frame ends:
a. If yes, is there a collision of the current frame recognition process? If yes, the
reader’s head remains unchanged, and the next frame continues to identify the current
group; otherwise, the reader modifies head = mod (head + l, 16), and determines whether
the head is equal to the rear. If yes, go to end; otherwise, go to Step 4.
b. If no, the reader sends a command (Query_Rep), and the reader identifies the next
time slot of the current frame.
Step 9: When the label of the earliest group in the signal area receives the Query_Rep
command, the tag decrements the slot counter by one. The tag with a slot counter of
zero responds to the reader, and then performs Step 8.
4 Algorithm Analysis
Slots consist of three states: idle slots are those without tags, successful time slots are
chosen by a tag, and collision slots are chosen by multiple tags. According to inference,
the probability that K tags choose the same time slot is as follows:
P(L,N,K) = C
K
N ×
1
L
K
×
1 −
1
L
N−K
(1)
where L is the frame length, N is the total number of tags, and K is the number of tags
in the same time slot. The probability of deriving three types of time slots is as follows:
When K = 0, the probability of an idle time slot is,
P i = P(L,N,0) =
1 −
1
L
N
(2)