# Time Slot Detection-BasedM-ary Tree Anticollision Identification Protocol for RFID Tags in the Internet of Things

Authors: Xiaojiao Yang; Bizao Wu; Shixun Wu; Xinxin Liu; W. G. Will Zhao
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Recently, a number of articles have proposed query tree algorithms based on bit tracking to solve the multitag collision problem in radio frequency identification systems. However, these algorithms still have problems such as idle slots and redundant prefixes. In this paper, a time slot detection-basedM-ary tree (Time Slot Detection based M-ary tree, TSDM) tag anticollision algorithm has been proposed. When a collision occurs, the reader sends a predetection command to detect the distribution of the m-bit ID in the 2m subslots; then, the time slot after predetection is processed according to the format of the frame-like. The idle time slots have been eliminate through the detection. Using a frame-like mode, only the frame start command carries parameters, and the other time slot start commands do not carry any parameters, thereby reducing the communication of each interaction. Firstly, the research status of the anticollision algorithm is summarized, and then the TSDM algorithm is explained in detail. Finally, through theoretical analysis and simulation, it is proved that the time cost of the TSDM algorithm proposed in this paper is reduced by 12.57%, the energy cost is reduced by 12.65%, and the key performance outperforms the other anticollision algorithms.


---

## Body

## 1. Introduction

Radiofrequency identification is a vital noncontact automatic identification technology in the sensing layer of the Internet of Things. In a typical RFID system, multiple tags are read by the reader simultaneously through a channel. When this channel is used by multiple tags simultaneously, it will cause signal overlap and interference problems: multitag collision problems. It will cause a waste of channel bandwidth, communication energy cost, and communication time cost. Therefore, developing effective anticollision strategies to improve the performance of RFID systems has an important significance.Regarding the anticollision algorithm, massive research has been done and formed many valuable articles. Based on fundamentals and implementation, the anticollision algorithm can be divided into three main categories: ALOHA-based, hybrid-based, and tree-based algorithms. Based on theM-ary tree algorithm, we proposed a TSDM (Time Slot Detection based M-ary Tree) anticollision algorithm. Therefore, in the introduction, the current research status of the ALOHA-based algorithm and the hybrid-based algorithm is briefed, and the current research status of the tree algorithm is detailed.These articles focus on the improvement of ALOHA-based algorithm [1–6], and the basic idea behind this kind of algorithm is that the reader estimates the number of tags according to the collision, success, and idle time slots first and then adjusts the frame length dynamically based on the estimation results. When the number of tags is equal to the number of time slots, the ALOHA-based algorithm can achieve the highest throughput rate of 36.8%. Ease of implementation is an advantage of the algorithm based on ALOHA. The randomness of the identification process and the starvation problem are the disadvantages of the ALOHA-based algorithm.Those articles [7–11] proposed the hybrid-based algorithm, which combines part of the ALOHA-based algorithm and the tree-based algorithm. In the paper [11], based on the dynamic frame slot ALOHA algorithm, the binary tree algorithm is used to identify the collision slot. Compared with the ALOHA algorithm, the hybrid-based algorithm has a more considerable improvement in the throughput rate. However, the starvation problem is still to be solved, and its implementation complexity is higher than the ALOHA-based algorithm.Many papers have generated large amounts of valuable research about the tree-based algorithm [12–29]. The key technology of this algorithm is bit identification and bit tracking. The reader can group a set of tags based on collision bits. Moreover, repeat the step until there is only one tag in a group. The article [14] proposed the CwT algorithm. The tag replied that it is not the remaining ID but the partial ID with a length of w bits, which effectively reduces the average amount of data transferred between reader and tag. An MCT algorithm is proposed in the paper [15]. The data frame format is used in the MCT algorithm to process m-bit collision bits simultaneously, and the tag selects the response time slot based on the collision bits. Since only the first command of the frame is carrying the parameter, this will reduce the amount of the transferred data. An MQT algorithm based on the M-ary algorithm has been proposed [22]. The tag first mapped the m-bit ID from the highest collision bit according to rules [22]. Then, the specific mapped part is sent to the reader with the remaining ID. In the STT algorithm [27], the reader recorded continuous collision slots and idle slots in the identification process. The length of the prefix will make adjustments in agreement with the recorded value. The reader calculates the actual m-bit ID based on the collision bits of the received mapping part. In summary, the main problem of MCT is that there are too many idle slots. The redundant prefix problem still needs to be solved in the MQT, CwT, and STT algorithm. Therefore, the above algorithms still have room for improvement.We propose time slot detection based on theM-ary tree anticollision algorithm (TSDM). The core idea of the TSDM algorithm is to detect first and identify second. The anticollision identification process is divided into two steps. The first step is to detect the m-bit ID′ value using a detection command. Then, synchronization results by sending a start command of the frame. Tags select the corresponding slot based on the calculation. In this way, we can eliminate idle slots through the proposed TSDM algorithm. In the typically M-ary tree algorithm, each command takes at least a parameter, and each reply includes the entire remaining ID. Therefore, redundant prefixes exist in the tag identification process. The TSDM algorithm is adopting a frame-like mode to deal with collision tags. Only the start command takes parameters, and the others take no parameters. Therefore, the TSDM algorithm reduces the average communication load between the tag and the reader. The simulation and theoretical analysis proved that the communication load, tag cost, time cost, and energy cost of the TSDM algorithm are better than the MCT, MQT, CwT, and STT algorithms compared with those articles [14, 15, 22, 27]. In a noisy environment, that is, take capture effects and path loss into the simulation, the TSDM algorithm still performs better than the others.The writing framework of this article is as follows: Section2 details the proposed TSDM algorithm. Section 3 is the theoretical analysis part, which analyses the performance of the TSDM algorithm. Section 4 is the simulation verification. First, the communication load, time cost, and energy cost of STT, CwT, MCT, MQT, and TSDM algorithms are compared by simulation in an ideal environment. Then, the impact of the environmental noise on the time cost is simulated. Section 5 is the conclusion. The performance of the proposed TSDM algorithm is evaluated and summarized.


## 2. The Proposed Time Slot Detection Protocol

The first part of this section details the registers and commands used in the TSDM algorithm. The second part introduces the implementation process of the TSDM algorithm in detail. The third part gives an example of the TSDM algorithm.


### 2.1. Related Commands and Registers

This article uses three special commands and a register for manipulating collisions. The register is for the tag, with the rest commands used for the reader.BQ (pre): command BQ (pre) is a command for time slot detection. Only tags that match the prefix pre will reply to the command BQ.FQ (slot): the command FQ (slot) is a command to start a frame. The parameter slot is the time slot distribution of the collision tags. Expressly, set the collision bit of the string received by the command BQ to 1 and set the remaining bits to 0. The value obtained is the slot.SQ: command SQ is a command to start a time slot. Command SQ does not carry any parameters.RegisterRegM: the M-bits register in the tag used for storing binary objects. RegM will be updated when the command BQ is received.


### 2.2. Algorithm Description

This section details the TSDM algorithm, illustrated by pseudocode and an example. Table1 briefly explains the symbols used in the paper and the meanings they represent.Table 1
Meaning of symbols.
SymbolMeaningLThe length of the tag’s IDℇThe parameter of command BQ, which means empty and occupies 1 bit||Connection operator. For example,0001∥1100=00011100&Bitwise AND operator. For example,1101&0100=0100<<Left shift operator. For example,0001<<2=0100∣S∣Calculate the length of the stringS. For example, ∣0001∣=4ID [i, j]Get thei-jth string of ID, where i≤j. For example, if ID=11101010，then ID3,5=101Count (x)Count the number of 1 in the binary numberx. For example, count1101=3The pseudocode in Algorithm1 details the implementation of the TSDM algorithm. Qu in step 1-1 is a queue for temporarily storing prefixes in the identification process. Steps 1-1 to 1-4 call function Function_AntiCol() to deal with the multitag anticollision problem.Algorithm 1: Pseudocode of the TSDM algorithm.
1 Reader Operation1-1:Qu={ℇ};1-2:while(Qu≠NULL) do1-3:  Function _AntiCol()1-4:end while2 Anti-Collision processing2-1: Function _AntiCol()2-2: {pre=Deque(Qu)2-3:  Broadcast command BQ(pre);2-4:   (slot, N)=ConvertResponse(Received strings);2-5:for (i=1; i≤N; i++) do2-6:ifi==1 do2-7:     Broadcast command FQ(slot)2-8:else2-9:     Broadcast command SQ2-10:end if2-11:left_ID=received string2-12:ifleft_ID collision do2-13:     Generate the parameterpre and insert it into Qu2-14:else2-15:     Obtain the corresponding tag ID2-16:end if2-17:end for}The implementation process of Function_AntiCol() is described in steps 2-1 to 2-17 in Algorithm1. Next, we will introduce steps 2-1 to 2-17 in detail. Step 2-2 means popping a string from the queue Qu as the parameter pre. Step 2-3 represents broadcast the command BQ (pre). Step 2-4, from the received string, computes the parameter slot and N. The parameter slot is calculated by setting the collision bit of the received string to 1 and setting the remaining bits to 0. The parameter N is the number of collision bits in the received string. Loop in steps 2-5 to 2-17 uses a frame-like mode for time slot detection. Steps 2-6 to 2-10 determine whether it is the first time slot of this frame. The reader sends the command FQ only in the first time slot, while the rest time slots send command SQ. Steps 2-12 to 2-16 judge whether the received data is colliding. A collision occurs when it queues the prefix pre into the queue Qu; otherwise, the reader directly identifies a tag.The three commands in the proposed TSDM algorithm are BQ (pre), FQ (slot), and SQ. Next, we will introduce in detail the process of the tags after received the above three commands.Received command BQ(pre): if ID[1:|pre|] equals the parameter pre, the tag calculates the value of RegM first and then sends it to the reader. Otherwise, set RegM to NULL and will not reply. Algorithm 2 shows the computation procedure of RegM. Initialize register in Algorithm 2 means that RegM is a binary number with a length of 2m bits and set its initial value to 1. For instance, RegM=00000001 when m=3. The first step assigns the ∣pre∣+1 to ∣pre∣+m bits of the tag′ID to the variable Bi. The second step converts binary to decimal. The third step left shifts RegM by mi bits and assigns the result to RegM.Algorithm 2. Pseudocode of update the registerRegM.
Initialize register:|RegM|=2m,and RegM = 11:B(i)=ID[|pre|+1:|pre|+m]2:m(i)=Binary_to_ Decimal(B(i))3:RegM=RegM<< m(i)Received command FQ(slot) or SQ: if RegM==NULL, the label will not reply. On the contrary, if RegM≠NULL, the tag sends ID[|pre| + m + 1:L] to the reader in the Td-th time slot. The calculation formula of Td is Td = Count((RegM-1)&slot) + 1.


### 2.3. An Example of the Proposed TSDM Algorithm

To describe our proposed algorithm intuitively, in this part, we will use the example in Table2 and the structure figure in Figure 1 to illustrate the implementation.Table 2
An example of the TSDM algorithm.
CommandsReplyIdentified tags1.BQ(ℇ)X0X00X0XNull2.FQ(10100101)1000100010001 (T1)3.SQX0XXXNull4.SQ0101110101011 (T5)5.SQ000XXNull6.BQ(010)0X00XX00Null7.FQ(01001100)1101000111 (T2)8.SQ1101010011 (T3)9.SQ0001010100 (T4)10.BQ(111000)X00X11100000(T6) 11100011 (T7)Figure 1
Structure of the identification process.Whenm=3, Table 2 illustrates the detailed process for identifying seven tags.Step1. The reader broadcasts the command BQ(ℇ), where the parameter ℇ means empty. After receiving the command BQ(ℇ), the tag maps the highest 3-bit ID according to the rule of Algorithm 2, then saves it to the register RegM and replies, without the need to match the prefix.Step 2~step5. The reader broadcasts the command FQ(10100101), where the parameter 10100101 represents the distribution of tags. The tag chooses the corresponding slot depending on the value ofTd after receiving FQ(10100101). Taking T1 as an example, after receiving the command FQ(10100101), the calculation process of Td is as follows: Td=CountRegM−1&slot+1=Count00000001−1&10100101+1=Count00000000+1=1. Therefore, T1 will reply to the reader in the first and current time slot. Similarly, Td’s value for T2, T3, T4, T5, T6, and T7 are 2, 2, 2, 3, 4, and 4, respectively. Therefore, the tags T2, T3, and T4 will send the remaining ID in the second time slot (i.e., step 3 in Table 2). Tag T5 will send the remaining ID in the third time slot (i.e., step 4 in Table 2). Tags T5, T6, and T7 will send the remaining IDs in the fourth time slot (i.e., step 5 in Table 2).Step 6. The reader broadcasts the command BQ(010), where parameter 010 indicates the prefix needs to match. The tag first compares the prefix 010 and the highest 3 bits of the ID after receiving the command BQ(010). If they are the same, the tag maps the 3-bit data starting from the highest bit of the remaining ID according to Algorithm2, then saves it to the register RegM and replies. Otherwise, the tag sets RegM to NULL and keeps silent, waiting for the next command BQ. In step 6, only the first three bits of T2, T3, and T4 are the same as 010, so only they will reply.Step7~step9. Only T2, T3, and T4 will reply to the commands since theRegM of other unidentified tags is all NULL. The identification process has been described in detail before, and we will no cover it here.Step 10. The reader broadcasts the command BQ(111000). After receiving the command, onlyT6 and T7 will reply. Since the remaining part of the ID has 2 bits (less than 3), the tags map and reply only 2 bits. After the reader receives X00X, it decodes the collision bits, and the final two bits of ID are 00 and 11, respectively. Due to the uniqueness of the tag ID, T6 and T7 are directly identified.We can conclude that the proposed TSDM algorithm only needs ten commands to identify seven tags. The structure of the TSDM algorithm in Figure1 looks similar to the M-ary tree. However, idle leaf nodes are skipping through the time slot detection in the TSDM algorithm.Figure1 is the structure of the identification process of tags T1-T7. Due to the predetection of the command BQ, idle time slots are skipping in the TSDM algorithm. It reduces the average number of commands sent by the reader. Besides, Figure 1 intuitively shows the identification process, which is similar to a frame. Compared with the typical M-ary algorithm, the parameters carried by the commands of the TSDM algorithm are reduced. Above all, the proposed TSDM algorithm not only reduces time cost but also reduces the energy cost.


## 2.1. Related Commands and Registers

This article uses three special commands and a register for manipulating collisions. The register is for the tag, with the rest commands used for the reader.BQ (pre): command BQ (pre) is a command for time slot detection. Only tags that match the prefix pre will reply to the command BQ.FQ (slot): the command FQ (slot) is a command to start a frame. The parameter slot is the time slot distribution of the collision tags. Expressly, set the collision bit of the string received by the command BQ to 1 and set the remaining bits to 0. The value obtained is the slot.SQ: command SQ is a command to start a time slot. Command SQ does not carry any parameters.RegisterRegM: the M-bits register in the tag used for storing binary objects. RegM will be updated when the command BQ is received.


## 2.2. Algorithm Description

This section details the TSDM algorithm, illustrated by pseudocode and an example. Table1 briefly explains the symbols used in the paper and the meanings they represent.Table 1
Meaning of symbols.
SymbolMeaningLThe length of the tag’s IDℇThe parameter of command BQ, which means empty and occupies 1 bit||Connection operator. For example,0001∥1100=00011100&Bitwise AND operator. For example,1101&0100=0100<<Left shift operator. For example,0001<<2=0100∣S∣Calculate the length of the stringS. For example, ∣0001∣=4ID [i, j]Get thei-jth string of ID, where i≤j. For example, if ID=11101010，then ID3,5=101Count (x)Count the number of 1 in the binary numberx. For example, count1101=3The pseudocode in Algorithm1 details the implementation of the TSDM algorithm. Qu in step 1-1 is a queue for temporarily storing prefixes in the identification process. Steps 1-1 to 1-4 call function Function_AntiCol() to deal with the multitag anticollision problem.Algorithm 1: Pseudocode of the TSDM algorithm.
1 Reader Operation1-1:Qu={ℇ};1-2:while(Qu≠NULL) do1-3:  Function _AntiCol()1-4:end while2 Anti-Collision processing2-1: Function _AntiCol()2-2: {pre=Deque(Qu)2-3:  Broadcast command BQ(pre);2-4:   (slot, N)=ConvertResponse(Received strings);2-5:for (i=1; i≤N; i++) do2-6:ifi==1 do2-7:     Broadcast command FQ(slot)2-8:else2-9:     Broadcast command SQ2-10:end if2-11:left_ID=received string2-12:ifleft_ID collision do2-13:     Generate the parameterpre and insert it into Qu2-14:else2-15:     Obtain the corresponding tag ID2-16:end if2-17:end for}The implementation process of Function_AntiCol() is described in steps 2-1 to 2-17 in Algorithm1. Next, we will introduce steps 2-1 to 2-17 in detail. Step 2-2 means popping a string from the queue Qu as the parameter pre. Step 2-3 represents broadcast the command BQ (pre). Step 2-4, from the received string, computes the parameter slot and N. The parameter slot is calculated by setting the collision bit of the received string to 1 and setting the remaining bits to 0. The parameter N is the number of collision bits in the received string. Loop in steps 2-5 to 2-17 uses a frame-like mode for time slot detection. Steps 2-6 to 2-10 determine whether it is the first time slot of this frame. The reader sends the command FQ only in the first time slot, while the rest time slots send command SQ. Steps 2-12 to 2-16 judge whether the received data is colliding. A collision occurs when it queues the prefix pre into the queue Qu; otherwise, the reader directly identifies a tag.The three commands in the proposed TSDM algorithm are BQ (pre), FQ (slot), and SQ. Next, we will introduce in detail the process of the tags after received the above three commands.Received command BQ(pre): if ID[1:|pre|] equals the parameter pre, the tag calculates the value of RegM first and then sends it to the reader. Otherwise, set RegM to NULL and will not reply. Algorithm 2 shows the computation procedure of RegM. Initialize register in Algorithm 2 means that RegM is a binary number with a length of 2m bits and set its initial value to 1. For instance, RegM=00000001 when m=3. The first step assigns the ∣pre∣+1 to ∣pre∣+m bits of the tag′ID to the variable Bi. The second step converts binary to decimal. The third step left shifts RegM by mi bits and assigns the result to RegM.Algorithm 2. Pseudocode of update the registerRegM.
Initialize register:|RegM|=2m,and RegM = 11:B(i)=ID[|pre|+1:|pre|+m]2:m(i)=Binary_to_ Decimal(B(i))3:RegM=RegM<< m(i)Received command FQ(slot) or SQ: if RegM==NULL, the label will not reply. On the contrary, if RegM≠NULL, the tag sends ID[|pre| + m + 1:L] to the reader in the Td-th time slot. The calculation formula of Td is Td = Count((RegM-1)&slot) + 1.


## 2.3. An Example of the Proposed TSDM Algorithm

To describe our proposed algorithm intuitively, in this part, we will use the example in Table2 and the structure figure in Figure 1 to illustrate the implementation.Table 2
An example of the TSDM algorithm.
CommandsReplyIdentified tags1.BQ(ℇ)X0X00X0XNull2.FQ(10100101)1000100010001 (T1)3.SQX0XXXNull4.SQ0101110101011 (T5)5.SQ000XXNull6.BQ(010)0X00XX00Null7.FQ(01001100)1101000111 (T2)8.SQ1101010011 (T3)9.SQ0001010100 (T4)10.BQ(111000)X00X11100000(T6) 11100011 (T7)Figure 1
Structure of the identification process.Whenm=3, Table 2 illustrates the detailed process for identifying seven tags.Step1. The reader broadcasts the command BQ(ℇ), where the parameter ℇ means empty. After receiving the command BQ(ℇ), the tag maps the highest 3-bit ID according to the rule of Algorithm 2, then saves it to the register RegM and replies, without the need to match the prefix.Step 2~step5. The reader broadcasts the command FQ(10100101), where the parameter 10100101 represents the distribution of tags. The tag chooses the corresponding slot depending on the value ofTd after receiving FQ(10100101). Taking T1 as an example, after receiving the command FQ(10100101), the calculation process of Td is as follows: Td=CountRegM−1&slot+1=Count00000001−1&10100101+1=Count00000000+1=1. Therefore, T1 will reply to the reader in the first and current time slot. Similarly, Td’s value for T2, T3, T4, T5, T6, and T7 are 2, 2, 2, 3, 4, and 4, respectively. Therefore, the tags T2, T3, and T4 will send the remaining ID in the second time slot (i.e., step 3 in Table 2). Tag T5 will send the remaining ID in the third time slot (i.e., step 4 in Table 2). Tags T5, T6, and T7 will send the remaining IDs in the fourth time slot (i.e., step 5 in Table 2).Step 6. The reader broadcasts the command BQ(010), where parameter 010 indicates the prefix needs to match. The tag first compares the prefix 010 and the highest 3 bits of the ID after receiving the command BQ(010). If they are the same, the tag maps the 3-bit data starting from the highest bit of the remaining ID according to Algorithm2, then saves it to the register RegM and replies. Otherwise, the tag sets RegM to NULL and keeps silent, waiting for the next command BQ. In step 6, only the first three bits of T2, T3, and T4 are the same as 010, so only they will reply.Step7~step9. Only T2, T3, and T4 will reply to the commands since theRegM of other unidentified tags is all NULL. The identification process has been described in detail before, and we will no cover it here.Step 10. The reader broadcasts the command BQ(111000). After receiving the command, onlyT6 and T7 will reply. Since the remaining part of the ID has 2 bits (less than 3), the tags map and reply only 2 bits. After the reader receives X00X, it decodes the collision bits, and the final two bits of ID are 00 and 11, respectively. Due to the uniqueness of the tag ID, T6 and T7 are directly identified.We can conclude that the proposed TSDM algorithm only needs ten commands to identify seven tags. The structure of the TSDM algorithm in Figure1 looks similar to the M-ary tree. However, idle leaf nodes are skipping through the time slot detection in the TSDM algorithm.Figure1 is the structure of the identification process of tags T1-T7. Due to the predetection of the command BQ, idle time slots are skipping in the TSDM algorithm. It reduces the average number of commands sent by the reader. Besides, Figure 1 intuitively shows the identification process, which is similar to a frame. Compared with the typical M-ary algorithm, the parameters carried by the commands of the TSDM algorithm are reduced. Above all, the proposed TSDM algorithm not only reduces time cost but also reduces the energy cost.


## 3. Theoretical Analyses

In the TSDM algorithm, the larger them, the larger the M is since the number of groups is M=2m. Therefore, the greater the value of m, the faster the collision tag is recognized by the reader. However, the larger the value of m, the larger the mapping value. It will increase the computational complexity and increase the average number of bits between the reader and the tag. In the TSDM algorithm, the recommended value of m is 3. In this section, the number of the average paging times of the TSDM algorithm is analyzed theoretically.In the TSDM algorithm, the number of command BQ sent by the reader is equal to the number of collision slots. Cleary, the sum number of command FQ and command SQ is equal to the number of nonempty time slots in theM-ary tree algorithm.Letn be the number of tags in the broadcast domain of the reader. Let Cn be the sum of collision slots in the whole identification process. Let the number of paging times of the TSDM algorithm be Ttn. Ttn can be expressed as
(1)Ttn=2Cn+n.It can be seen from formula (1) that if Cn is obtain, Ttn is obtain. Therefore, we first have to calculate what Cn is.Theorem 1.
(2)Cn=0,n=01∑j=07∑i=2n−1PSj=i∣A0≥1∩A1≥1Ci,n≥2.The proof of Theorem1 is as follows:Whenn=0 or 1, no collision slot that exists, so Cn=0.Whenn≥2, collision tags will be divided into MM=2m subsets, based on the tag’s m-bis ID starting from the highest collision bit. In the TSDM algorithm, the recommended value of m is 3, so we take m=3 as an example. When m=3, the 8 subsets are as follows: S0=000, S1=001, S2=010, S3=011, S4=100, S5=101, S6=110, and S7=111. If the 8 subsets are grouped by the highest collision bit, they will be divided into two subsets: A0=000,001,010,011 and A1=100,101,110,111.Only if there is at least one tag in both subsetA0 and subset A1 simultaneously, the reader can identify the highest collision bit. We can deduce that the probability of i tags falling in the slot Sj is PSj=i∣A0≥1∩A1≥1. Proved formula (2) using a recursive algorithm.Lemma 1.
(3)PSj=iA0≥1∩A1≥1=1−3/7n−iin1/8i7/8n−i1−21/2n.Proof.
From the rules of set operation, we can get(4)PSj=iA0≥1∩A1≥1=PA0≥1∩A1≥1Sj=1×PSj=iPA0≥1∩A1≥1.If the tag’s ID has a law of binomial distribution, the probability ofi tags falling in subset S0 is
(5)PSj=i=in18i78n−i.Next, respectively, calculate the numerator and denominator in formula (4). The calculation processes of the molecular are as follows:
(6)PA0≥1∩A1≥1Sj=i,=1−PA0=0∩A1=0Sj=i,=1−PA0=0∪A1=0∩Sj=iPSj=i.Because the probability that a tag locates in subsetsS0 to S7 is the same, we use subset S0 as our example. Let j=0 and take it into formula (7).
(7)PA0=0∪A1=0∩Sj=i=PA0=0∪A1=0∩S0=i=PA0=0∩S0=i+PA1=0∩S0=i.−PA0=0∩A1=0∩S0=i=in18i38n−iIf we want to compute the probability that a tag locates in subsetsS1 to S7, the same type of calculation would be made. Thus, formula (8) can be derived from formula (7).
(8)PA0=0∪A1=0∩Sj=i=in18i38n−i.Substituting formulas (5) and (8) into formula (6), we can get formula (9).
(9)PA0≥1∩A1≥1Sj=i=1−37n−i.Finally, the denominator of formula (4) is calculated by the formula (10).
(10)PA0≥1∩A1≥1=1−PA0=0∪A1=0=1−PA0=0−PA1=0+PA0=0∩A1=0.=1−212nPutting formulas (5), (9), and (10) into formula (4), Lemma 1 is proved.Incorporating Lemma1 into Theorem 1, we can get Cn≈0.4382n by the iterative calculation on the computer. Putting the value of Cn into equation (1), we can get Tn≈1.876n. The parameters in Table 3 are for simulation, and we get the simulation results by simulating the implementation process of the proposed TSDM algorithm. As shown in Figure 2, the simulated value of Cn is almost consistent with the theoretical value.Table 3
Parameters used in simulations.
ParametersValuet125 ust225 usv160 kbpsPt825 MWPe125 MWL96 bitsFigure 2
Theoretical and simulation results of collision slots for a tag identification.


## 4. Simulation Results

In this section, we will start with the definition of command format and parameter values. Next, the performance of MCT, MQT, CWT, STT, and TSDM algorithms are compared by simulation. Finally, we will discuss the influence of environmental noise on the algorithm.


### 4.1. Simulation Configuration

In this part, a typical passive RFID system will be simulated by Matlab software, which includes a reader and several passive tags. Until the reader identifies the tag, the reader will not know the ID and the total number of tags. Tag generation obeys the typical binomial distribution, and each ID is unique in the simulation. The communication channel between the reader and the tag is ideal in Section4.2. We will consider the environmental noise in Section 4.3.The link sequence diagram of the TSDM algorithm is in Figure3. The values of parameters t1 and t2 in Figure 3 are in Table 3. The parameter v in Table 3 represents the data rate between the reader and the tag. The last parameter L represents the length of the tag’s ID. The parameters Pt and Pe are used to calculate the energy overhead, where Pt represents the reader’s carrier power, and Pe represents the additional carrier power produced by the reader during the tag reply to the reader.Figure 3
The format of commands in the TSDM algorithm.The proposed TSDM algorithm, MCT algorithm, MQT algorithm, CwT algorithm, and STT algorithm are simulated by Matlab software in the next part. In the TSDM, the value ofm is 3. Set the variables’ optimal values in the rest of the articles for the simulation validation’s best performance.


### 4.2. Performance Comparison

Figure2 compares the critical performance of the MQT algorithm, the MCT algorithm, the STT algorithm, and the CwT algorithm, as well as the proposed TSDM algorithm by simulation.
(1)
Total communication load. The average total bits for a tag identification in Figure4(a) represent the total communication load. It can be seen from Figure 4(a) that the average total bits for a tag identification of the TSDM algorithm are about 225 bits, which is less than MQT, MCT, STT, and CwT. Since there is no idle time slot and redundant parameters, The TSDM algorithm tremendously reduces the average bits transferred between reader and tag(2)
Communication load of the tag. The tag’s average bits for a tag identification in Figure4(b) represent the tag’s communication load. Most tags are passive or battery-powered In the RFID system, so the tag’s communication load has a significant impact on the tag’s useful lifespan. The lower the tag’s communication load, the lower the algorithm’s energy cost, so the longer the tag’s life. As shown in Figure 4(b), the communication load of tag rank from low to high is as follows: TSDM, CwT, MQT, MCT, and STT. The TSDM algorithm proposed has the least average tag communication load(3)
Time cost. The average time cost for a tag identification represents the time cost. The lower the time cost, the more tags can be identified per unit time. Figure4(c) shows that the TSDM algorithm has the lowest time cost. The average time to identify a tag is about 1.51 ms when using the TSDM algorithm. The average time to identify a tag is as follows: MQT is about 1.73 ms, MCT is about 1.76 ms, STT is about 2.6 ms, and CwT is about 2.72 ms. The time cost of the TSDM algorithm is reduced by at least 12.57% compared with the other algorithm(4)
Energy cost. The average energy cost for a tag identification represents the energy cost. Many RFID tags are battery-powered or passive. Therefore, the lower the power cost, the longer the lifespan of a tag. Figure4(d) shows that the average energy cost for a tag identification of the TSDM algorithm is about 1.36 mJ. Its performance is better than other algorithms that are comparing below. The energy cost of the TSDM algorithm is reduced by at least 12.65% compared with the other algorithmsFigure 4
Simulation results: (a)average total bits for a tag identification, (b) average bits of tag for a tag identification, (c) average time cost for a tag identification, and (d) average energy cost for a tag identification.
(a)(b)(c)(d)Table4 lists the average time cost of MQT, MCT, CwT, STT, and TSDM for a tag identification. For instance, in the TSDM algorithm, the total time to recognize 100 tags is about 153.2 ms. We divide the total time by the number of tags to get the average time for a tag identification that is about 1.532 ms. As you can see in Table 4, the TSDM algorithm spends the least time for a tag identification, followed by the MQT algorithm. Therefore, we can conclude that the time cost of the TSDM algorithm is saved at least 12.57%, compared to the other four algorithms.Table 4
The time cost table of five methods.
Tag number1001000200030004000Average valueAlgorithmMQT1.7316 ms1.7396 ms1.7292 ms1.7194 ms1.7229 ms1.729 msMCT1.7800 ms1.7560 ms1.7610 ms1.7570 ms1.7510 ms1.761 msCwT2.6800 ms2.7170 ms2.7210 ms2.7300 ms2.7330 ms2.716 msSTT2.5850 ms2.5840 ms2.5890 ms2.6000 ms2.6140 ms2.594 msTSDM1.5320 ms1.5310 ms1.5070 ms1.4932 ms1.4930 ms1.511 msDecrement rate11.53%11.99%12.85%13.16%13.34%12.57%Table5 lists the average energy cost of MQT, MCT, CwT, STT, and TSDM for a tag identification. The average energy cost can be obtained by referring to the calculation method of the average time. As we can see in Table 5, compared with MQT, MCT, CwT, and STT algorithm, the TSDM algorithm cut energy cost by at least 12.65%.Table 5
The energy cost table of five methods.
Tag number1001000200030004000Average valueAlgorithmMQT1.5651 mJ1.5685 mJ1.5580 mJ1.5484 mJ1.5511 mJ1.558 mJMCT1.6070 mJ1.5840 mJ1.5870 mJ1.5830 mJ1.5770 mJ1.588 mJCwT2.3360 mJ2.3670 mJ2.3700 mJ2.3770 mJ2.3790 mJ2.366 mJSTT2.2960 mJ2.2880 mJ2.2920 mJ2.3010 mJ2.3130 mJ2.318 mJTSDM1.3820 mJ1.3790 mJ1.3570 mJ1.3440 mJ1.3440 mJ1.361 mJDecrement rate11.7%12.08%12.9%13.2%13.35%12.65%


### 4.3. Effect of Environmental Noise

In a realistic environment, path loss and capture effects may cause randomness in the identification process, which will lead to deviations in the algorithm’s performance between the realistic environment and the ideal environment. Next, the implementation process of TSDM, MQT, and MQT in the realistic environment is simulating by Matlab software.When path loss occurs, the reader usually does not recognize the signal to which the tag is replying. LetPd be the probability of path loss and Pd∈0,0.2. Only the signal from the tag with the strongest signal will be detected when the capture effect occurs. Let Pc be the probability of path loss and Pc∈0,0.2. Since the energy cost is proportional to the time cost, we are only analyzing the time cost here.Figure5(a) shows the change rules of the average time to identify a tag due to Pd’s change when Pc=0.1. When path loss occurs, a collision slot may be inaccurately considered a successful slot or an idle slot, and a successful slot may be inaccurately considered an idle slot. It will lead to uncertainty in the tag identification process, thereby increasing the identification time. Compared with MCT and MCT, the proposed TSDM algorithm still dominates the identification time when Pd changes dynamically.Figure 5
Average time cost for a tag identification in a realistic environment: (a) the value ofPc is 0.1, and Pd ranges from 0 to 0.2, and (b) the value of Pd is 0.1, and Pc ranges from 0 to 0.2.
(a)(b)Figure5(b) shows the change rules of the average time to identify a tag due to Pc’s change when Pd=0.1. When the capture effect occurs, a collision slot may be inaccurately considered a success slot, which will speed up the tag identification process. As Pc increased, the average time for a tag identification is decreasing. Moreover, the identification time of TSDM is still less than MQT and MCT.


## 4.1. Simulation Configuration

In this part, a typical passive RFID system will be simulated by Matlab software, which includes a reader and several passive tags. Until the reader identifies the tag, the reader will not know the ID and the total number of tags. Tag generation obeys the typical binomial distribution, and each ID is unique in the simulation. The communication channel between the reader and the tag is ideal in Section4.2. We will consider the environmental noise in Section 4.3.The link sequence diagram of the TSDM algorithm is in Figure3. The values of parameters t1 and t2 in Figure 3 are in Table 3. The parameter v in Table 3 represents the data rate between the reader and the tag. The last parameter L represents the length of the tag’s ID. The parameters Pt and Pe are used to calculate the energy overhead, where Pt represents the reader’s carrier power, and Pe represents the additional carrier power produced by the reader during the tag reply to the reader.Figure 3
The format of commands in the TSDM algorithm.The proposed TSDM algorithm, MCT algorithm, MQT algorithm, CwT algorithm, and STT algorithm are simulated by Matlab software in the next part. In the TSDM, the value ofm is 3. Set the variables’ optimal values in the rest of the articles for the simulation validation’s best performance.


## 4.2. Performance Comparison

Figure2 compares the critical performance of the MQT algorithm, the MCT algorithm, the STT algorithm, and the CwT algorithm, as well as the proposed TSDM algorithm by simulation.
(1)
Total communication load. The average total bits for a tag identification in Figure4(a) represent the total communication load. It can be seen from Figure 4(a) that the average total bits for a tag identification of the TSDM algorithm are about 225 bits, which is less than MQT, MCT, STT, and CwT. Since there is no idle time slot and redundant parameters, The TSDM algorithm tremendously reduces the average bits transferred between reader and tag(2)
Communication load of the tag. The tag’s average bits for a tag identification in Figure4(b) represent the tag’s communication load. Most tags are passive or battery-powered In the RFID system, so the tag’s communication load has a significant impact on the tag’s useful lifespan. The lower the tag’s communication load, the lower the algorithm’s energy cost, so the longer the tag’s life. As shown in Figure 4(b), the communication load of tag rank from low to high is as follows: TSDM, CwT, MQT, MCT, and STT. The TSDM algorithm proposed has the least average tag communication load(3)
Time cost. The average time cost for a tag identification represents the time cost. The lower the time cost, the more tags can be identified per unit time. Figure4(c) shows that the TSDM algorithm has the lowest time cost. The average time to identify a tag is about 1.51 ms when using the TSDM algorithm. The average time to identify a tag is as follows: MQT is about 1.73 ms, MCT is about 1.76 ms, STT is about 2.6 ms, and CwT is about 2.72 ms. The time cost of the TSDM algorithm is reduced by at least 12.57% compared with the other algorithm(4)
Energy cost. The average energy cost for a tag identification represents the energy cost. Many RFID tags are battery-powered or passive. Therefore, the lower the power cost, the longer the lifespan of a tag. Figure4(d) shows that the average energy cost for a tag identification of the TSDM algorithm is about 1.36 mJ. Its performance is better than other algorithms that are comparing below. The energy cost of the TSDM algorithm is reduced by at least 12.65% compared with the other algorithmsFigure 4
Simulation results: (a)average total bits for a tag identification, (b) average bits of tag for a tag identification, (c) average time cost for a tag identification, and (d) average energy cost for a tag identification.
(a)(b)(c)(d)Table4 lists the average time cost of MQT, MCT, CwT, STT, and TSDM for a tag identification. For instance, in the TSDM algorithm, the total time to recognize 100 tags is about 153.2 ms. We divide the total time by the number of tags to get the average time for a tag identification that is about 1.532 ms. As you can see in Table 4, the TSDM algorithm spends the least time for a tag identification, followed by the MQT algorithm. Therefore, we can conclude that the time cost of the TSDM algorithm is saved at least 12.57%, compared to the other four algorithms.Table 4
The time cost table of five methods.
Tag number1001000200030004000Average valueAlgorithmMQT1.7316 ms1.7396 ms1.7292 ms1.7194 ms1.7229 ms1.729 msMCT1.7800 ms1.7560 ms1.7610 ms1.7570 ms1.7510 ms1.761 msCwT2.6800 ms2.7170 ms2.7210 ms2.7300 ms2.7330 ms2.716 msSTT2.5850 ms2.5840 ms2.5890 ms2.6000 ms2.6140 ms2.594 msTSDM1.5320 ms1.5310 ms1.5070 ms1.4932 ms1.4930 ms1.511 msDecrement rate11.53%11.99%12.85%13.16%13.34%12.57%Table5 lists the average energy cost of MQT, MCT, CwT, STT, and TSDM for a tag identification. The average energy cost can be obtained by referring to the calculation method of the average time. As we can see in Table 5, compared with MQT, MCT, CwT, and STT algorithm, the TSDM algorithm cut energy cost by at least 12.65%.Table 5
The energy cost table of five methods.
Tag number1001000200030004000Average valueAlgorithmMQT1.5651 mJ1.5685 mJ1.5580 mJ1.5484 mJ1.5511 mJ1.558 mJMCT1.6070 mJ1.5840 mJ1.5870 mJ1.5830 mJ1.5770 mJ1.588 mJCwT2.3360 mJ2.3670 mJ2.3700 mJ2.3770 mJ2.3790 mJ2.366 mJSTT2.2960 mJ2.2880 mJ2.2920 mJ2.3010 mJ2.3130 mJ2.318 mJTSDM1.3820 mJ1.3790 mJ1.3570 mJ1.3440 mJ1.3440 mJ1.361 mJDecrement rate11.7%12.08%12.9%13.2%13.35%12.65%


## 4.3. Effect of Environmental Noise

In a realistic environment, path loss and capture effects may cause randomness in the identification process, which will lead to deviations in the algorithm’s performance between the realistic environment and the ideal environment. Next, the implementation process of TSDM, MQT, and MQT in the realistic environment is simulating by Matlab software.When path loss occurs, the reader usually does not recognize the signal to which the tag is replying. LetPd be the probability of path loss and Pd∈0,0.2. Only the signal from the tag with the strongest signal will be detected when the capture effect occurs. Let Pc be the probability of path loss and Pc∈0,0.2. Since the energy cost is proportional to the time cost, we are only analyzing the time cost here.Figure5(a) shows the change rules of the average time to identify a tag due to Pd’s change when Pc=0.1. When path loss occurs, a collision slot may be inaccurately considered a successful slot or an idle slot, and a successful slot may be inaccurately considered an idle slot. It will lead to uncertainty in the tag identification process, thereby increasing the identification time. Compared with MCT and MCT, the proposed TSDM algorithm still dominates the identification time when Pd changes dynamically.Figure 5
Average time cost for a tag identification in a realistic environment: (a) the value ofPc is 0.1, and Pd ranges from 0 to 0.2, and (b) the value of Pd is 0.1, and Pc ranges from 0 to 0.2.
(a)(b)Figure5(b) shows the change rules of the average time to identify a tag due to Pc’s change when Pd=0.1. When the capture effect occurs, a collision slot may be inaccurately considered a success slot, which will speed up the tag identification process. As Pc increased, the average time for a tag identification is decreasing. Moreover, the identification time of TSDM is still less than MQT and MCT.


## 5. Conclusions

There is predetection in the TSDM algorithm that can completely avoid the idle slots of theM-ary algorithm, thus reduce the communication data between reader and tag. It will reduce the average communication load and the average time cost, which improves the TSDM algorithm’s performance. The proposed TSDM algorithm has an average communication load of about 225 bits, an average time overhead of 1.51 ms, and average power consumption of 1.36 mJ when identifying a tag with an ID length of 96 bits. Compared with the other tree-based algorithms, the TSDM algorithm reduces the time cost by at least 12.57% and the energy cost by at least 12.65%. Moreover, taking environmental noise (including path loss and capture effect) into consideration, the TSDM algorithm’s performance still outperforms the other algorithms. Therefore, the TSDM algorithm is worth researching.



---

*Source: 6638936-2021-02-04.xml*