## 2 Background
### Previous Studies  
Many RFID anti-collision algorithms were proposed to identify all tags by using the minimal bandwidth resource. These algorithms can be divided into two categories, which are the probabilistic methods and deterministic methods.  
The probabilistic methods, which are also called the Aloha-based algorithms [10; 11; 12; 13; 14; 15; 16; 17; 18], attempt to adjust the frame size to maximize the bandwidth usage by observing the probabilities of collision and idle in current frame. That is, each tag randomly chooses one slot in current frame to send its message to the reader, and then the reader observes the number of collisions, readable, and idle slots in this frame in order to estimation the number of tags within its interrogation range. Ideally, in order to minimize the collision and idle slots, the number of slots in a frame should equal to the number of tags within a reader's interrogation range. Therefore, the reader then modifies the next frame size to the number of the tags.  
The deterministic methods, which are also called the Tree-based algorithms [19; 30; 31], resolve a collision among tags by repeatedly subdivided into groups until each group contains at most one tag. The Tree-based algorithms can be further classified into the binary tree protocol (BT) and query tree  
Figure 4: Relationship among collision, readable, idle and signal interference slot.  
Figure 3: Example of the interference.  
protocol (QT). For BT, the collided tags are separated by randomly choosing a binary number and sending it back to the reader. This procedure repeats until the reader confirms each group contains at most one tag. With regards to QT, the collided tags are split by the reader's query. If the tag's ID prefix matches this query, the tag will respond with its ID to the reader. This query procedure continues until no collided response occurs for each query. However, these conventional algorithms did not consider the condition of channel error, meaning that the reader would overestimate the number of collided tags.  
The error resilient estimation and adaptive binary selection algorithm (ERE-ABS) was proposed to handle the issue of channel error [6]. ERE-ABS applies the PER and number of tags to judge which event, i.e., collision or channel error, treated by the reader would acquire the highest throughput and then adopts the corresponding strategy, when the reader receives an unreadable message. That is, for example, if the throughput of regarding the unreadable message as the result caused by channel error is higher than the throughput of treating this message as a collision, the reader would ask the tag who transmitted this message to retransmit it immediately. Otherwise, the reader would treat it as a collision and adopt the Tree-based anti-collision procedure so as to identify the collided tags.  
As shown in Figure 5, the ERE-ABS used two phases for accurate estimate channel status and improves identification efficiency. In the error resilient estimation (ERE) phase, the reader would attempt to split the number of tags into j groups until the probability of idle slots is smaller than the threshold. And then, the reader will operate the estimate process to calculate number of tags and channel state. In the adaptive binary selection (ABS) phase, the reader would apply the estimate result to judge retransmission or binary selection when it detects a collision slot.  
However, the channel status changes rapidly and ERE-ABS does not dynamically adjust PER and the number of tags during the collision resolving procedure. This results in that the PER and the number of tags may be incorrectly estimated and therefore cannot reflect the actual condition with regards to the current RFID system, meaning that the inferior throughput will be inescapably caused.