## 2 Background
### Multi-Access Methods  
Each anti-collision protocol uses certain multi-access methods for identification in order to physically separate the transmitters' signals. Accordingly, they can be categorized into four different types: Space Division Multiple Access (SDMA), Frequency Division Multiple Access (FDMA), Code Division Multiple Access (CDMA) and Time Division Multiple Access (TDMA) [2; 5; 8]. Figure 3 shows various multiple access and anti-collision procedures.  
SDMA--The term space division multiple access relates to dividing of the channel capacity into separate areas. Protocols based on this method can point the beam at different areas in order to identify tags. The channel is spatially separated using complex directional antennas. Another means of achieving this is through the use of multiple readers. As a result, the channel capacity of adjoining readers is enhanced. A huge number of tags can be read simultaneously as a result of the spatial distribution over the entire layout. This method is quite expensive and requires complex antenna design. The use of this type of method is restricted to a few specialized applications [9; 10; 11]. This technique is shown in Figure 4.  
Figure 1: Reader collision.  
Figure 2: Tag collision.  
FDMA--Tags transmitting in one of several different frequency channels requiring a complex receiver at the reader. Consequently, different frequency ranges can be used for communication from and to the tags: from the reader to the tags, 135 kHz, and from the tags to the reader, in the 433-435 MHz range. However, this technique is expensive and is only intended for certain specific applications [12]. Figure 5 shows FDMA procedure.  
CDMA--Tags to multiply their ID by a pseudo-random sequence (PN) before transmission. CDMA is quite good in many ways, such as the security of the communications between the RFID tags and the reader, and multiple tag identification. It adds great complexity and  
Figure 4: Space Division Multiple Access (SDMA) procedure.  
Figure 5: Frequency Division Multiple Access (FDMA) procedure.  
Figure 3: Multi-access methods.  
is expensive for RFID tags. Furthermore, this method consumes a great deal of power and can be classified as a group with elevated demands [13]. Figure 6 shows this procedure.  
TDMA--Given that it is less expensive, this is the most widely used method. This method involves the largest group of anti-collision algorithms. The transmission channel is divided between the participants and ensures that the reader can identify a tag at different times in order to avoid interfering with another one. The space-distributing characteristic of tags is not considered. The number of tags in the interrogation zone is reduced after every successful response. Another option involves the ability to mute all tags except for the transmitting tag. After that, the tags are activated one by one [14; 15]. TDMA is shown in Figure 7.  
In an RFID environment, anti-collision protocols typically use the TDMA method. Protocols that use this method first select an individual tag from a large group using a specific algorithm and then the communication takes place between the selected tag and the reader. Significant increases in number of collisions in the identification process decreases the throughput and increases the number of transmitted bits. These protocols can be divided into three categories: Aloha-based protocols, tree-based protocols and hybrid protocols (which use a combination of the first two methods). In the following subsections, some Aloha, tree-based and hybrid protocols shall be presented.