# An ALOHA-Based Algorithm Based on Grouping of Tag Prefixes for Industrial Internet of Things

Authors: Dongbo Zhong
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Nowadays, radio frequency identification (RFID) technology has been widely used in logistics, warehousing, urban transportation, medicine, and other fields due to its advantages of fast identification speed, low cost, and high security. The multitag collision problem causes the reader to fail to complete the identification of the tags in its coverage in time, thus seriously affecting the work efficiency of the entire RFID system. Therefore, the study of an efficient multitag identification algorithm is the basic premise to ensure the industrial application of RFID. Aiming at the problems of the low slot utilization rate of the existing DFSA algorithm in a large-scale tag recognition environment, we proposed a dynamic frame slotting anticollision algorithm based on tags prefix grouping called G-DFSA. G-DFSA uses the tag prefix to recognize the tag set and constructs the probe frame based on the grouping. Then, the slot statistics results of the probe frame are used to process the frames whose frame length does not match the number of tags. As shown in the simulation results, the system efficiency of the proposed algorithm is still close to the theoretical optimal throughput rate of DFSA algorithm 0.368 in the large-scale tag set. Compared with the existing methods, G-DFSA has obvious advantages in system throughput.


---

## Body

## 1. Introduction

Radio frequency identification (RFID) [1–5] technology is an automatic identification technology, which uses radio frequency signals to carry out information exchange in the wireless channel, and realizes the noncontact identification between objects. A complete RFID system consists of readers, tags, and background components. In many applications based on RFID technology, a mass of passive RFID tags are deployed in the system. Due to the nature of passive tags, tags cannot communicate with each other, so all tags can only receive signals from readers. Since multiple tags share the same wireless channel to communicate with readers, when multiple tags send data to readers at the same time, the phenomenon of collision between or more tags will occur, resulting in the failure of readers to identify tags, which brings great challenges to information collection. Therefore, the research on RFID electronic tag information collection is very suitable for the background of the development of the times [5, 6] and has important reference value and practical significance. Therefore, when there are multiple tags at the same time in the covering area of the reader, the reader must use anticollision algorithm to improve the efficiency of tag recognition.Existing RFID tag anticollision algorithms can be roughly divided into two categories. (1) ALOHA-based probabilistic anticollision algorithms [4, 5, 7–10]. ALOHA-based algorithm takes the way of tag answering first and lets the tag randomly select a time period to respond to the query request of reader. If only one tag responded to the query in the current time period, the tag was successfully identified. Thus, these algorithms are easy to implement and have low equipment cost but may have tag starvation. (2) Anticollision algorithm based on tree true shape [11–15]. As the query progresses, the tree splits and all the child nodes of the query tree are retrieved. In other words, as long as there are enough queries, readers can accurately query the ID of each tag. Thus, tree-based algorithm has a 100% recognition rate and can avoid the problem of tag starvation. However, once the tag IDS are not evenly distributed, the tree-based algorithm will generate many collision slots, leading to a gradual deterioration in performance. In Table 1, we summarized the features and development trends for existing representative anticollision algorithms.Table 1
Features of various types of anticollision algorithms.
TypesFeaturesDevelopment trendsALOHA-basedTag starvation; high estimation complexityReduce the complexityTree-basedNo tag starvation; long identification latencyOptimize probe mechanismHybrid-basedComplex structure; performance limitOptimize the architectureBy analyzing the two existing types of anticollision algorithms, we can conclude that the ALOHA-based algorithm is generally more efficient and adaptable in a table-dense environment. Instead, tree-based algorithms are executed differently and can recognize each active tag, making them more suitable for marking idle scenarios.Although the existing algorithm can solve the multiple tags collision problem to a certain extent, there are still some flaws in the ALOHA-based algorithm1 stipulated in the RFID system standard, the frame length must be a power of 2, and the length cannot exceed 256. Therefore, when there are far more than 256 tags to recognize, too many collision time slots will be generated, resulting in low efficiency of the overall system of the algorithm.LC-DFSA [16] and ILCM-SbS [17] optimized the frame length updating algorithm to find the frame length more suitable for the current number to improve the system throughput rate. However, due to the limitations of the RFID system and the existence of a large number of tag scenarios, the previously mentioned algorithm still cannot solve the problem of a large number of tag backlogs. [10] proposed the method of fuzzy C-means clustering to group and identify tag. But it is accompanied by a larger amount of computation. In [18], the authors analyze two different types of algorithms and propose an RFID anticollision algorithm suitable for dynamic scenarios. The algorithm adopts the idea of grouping to reduce the total number of time slots required, thereby improving the recognition performance.Based on the previously mentioned analysis, we proposed an improved algorithm called PG-DFSA. Before the first frame of the tag identification, in order to adjust the number of tags, PG-DFSA algorithm considered using the tag ID prefix divided tag set. This mechanism makes the subset as far as possible close to the number of initial frame length and eliminate the continuous tag collision problem. Meanwhile, the detection frame mechanism is used to optimize the process of subset tag recognition.The remainder of this paper is summarized as follows: In Section2, we will give a brief overview of the tag anticollision algorithm. In Section 3, the basic principle and concrete procedure of GP-DFSA are systematically discussed. Section 4 provides a simulation experiment for the GP-DFSA and compares it with the experimental results of other protocols. Finally, conclusions will be presented in Section 5.


## 2. Related Work

### 2.1. The Brief Analysis of ALOHA-Based Anticollision Algorithm

ALOHA-based algorithms are a classic probability anticollision protocol, which can send tag ID to the reader at all the time. ALOHA-based algorithm is the simplest multiaccess method. The algorithm takes the way of tag answering first and lets the tag randomly select a time period to respond to the query request of reader. If only one tag responded to the query in the current time period, the tag was successfully identified. Otherwise, collision slot with multiple tags responses or free time slot with no tag responses will be formed.Aloha-based algorithms experience pure ALOHA (PA), slotted ALOHA (SA), frame slotting ALOHA (FSA), and dynamic frame slotting ALOHA (DFSA) four stages. PA is the first ALOHA-based anticollision algorithm. Based on PA algorithm, SA algorithm divides the whole recognition time into several discrete time slots. Each tag can only randomly select one slot to send its ID at the beginning of each slot. Therefore, SA algorithm avoids the occurrence of tag partial collision and improves the efficiency of system. On the basis of SA algorithm, FSA algorithm combines several time slots into one frame to reduce the probability of tag collision.DFSA algorithm is a classic algorithm belong to ALOHA-based algorithm. Based on the frame time slot algorithm, the DFSA algorithm estimates the number of tags in the current recognition stage through the tag estimation algorithm and adjusts the frame length at the beginning of each frame recognition stage according to the estimated number of tags to be recognized. Therefore, the key to the improvement of DFSA algorithm is as follows: (1) improve the accuracy of the estimation of the number of tags and adjust the frame length reasonably; (2) reduce the number of idle time slots and collision time slots. The working principle of the DFSA algorithm is illustrated in Figure1.Figure 1
The working principle of DFSA algorithm.


### 2.2. Optimal Frame Size

We suppose the number of effective tags isN, and the length of frame size is L. Therefore, the probability of choosing the same time slot for any m tags can be expressed as(1)pm=CNm1Lm1−1LN−m.For a successful slot, there is only one tag send its IDs to reader. So, the probability of successful slot is(2)ps=CN11L1−1LN−1.When the current time slot has no tag send ID, it is defined as an idle time slot and its probability can be expressed as(3)pe=1−1LN.Only there are three slot condition during the recognition process: successful slot, idle slot, and collision slot. Thus, the probability of collision slot is(4)pc=1−ps−pe=1−N+L−1L1−1LN−1.According to (1), (2), and (3), we can get the expected values of successful slot, idle slot, and collision slot as follows:(5)Es=N1−1LN−1,Ee=L1−1LN,Ec=L−N+L−11−1LN−1.We denote the throughput rate as the ratio of successful slots to total slotsL, denoted as S. Thus, S is as follows:(6)S=NL1−1LN−1.In order to maximizeS, (7)dSdN=1L1−LN−1+NL1−LN−1ln1−1L=1−1LN−11+Nln1−1L1L=0.The result of maximize is(8)L=11−e−1/N.When the number of tags is large enough, we will obtain(9)L=11−e−1/N=e1/Ne1/N−1≈1/N+11/N=N+1,N≫1.As shown in (9), the maximum throughput rate S will be realized if the frame size L is equal to tag number N.


## 2.1. The Brief Analysis of ALOHA-Based Anticollision Algorithm

ALOHA-based algorithms are a classic probability anticollision protocol, which can send tag ID to the reader at all the time. ALOHA-based algorithm is the simplest multiaccess method. The algorithm takes the way of tag answering first and lets the tag randomly select a time period to respond to the query request of reader. If only one tag responded to the query in the current time period, the tag was successfully identified. Otherwise, collision slot with multiple tags responses or free time slot with no tag responses will be formed.Aloha-based algorithms experience pure ALOHA (PA), slotted ALOHA (SA), frame slotting ALOHA (FSA), and dynamic frame slotting ALOHA (DFSA) four stages. PA is the first ALOHA-based anticollision algorithm. Based on PA algorithm, SA algorithm divides the whole recognition time into several discrete time slots. Each tag can only randomly select one slot to send its ID at the beginning of each slot. Therefore, SA algorithm avoids the occurrence of tag partial collision and improves the efficiency of system. On the basis of SA algorithm, FSA algorithm combines several time slots into one frame to reduce the probability of tag collision.DFSA algorithm is a classic algorithm belong to ALOHA-based algorithm. Based on the frame time slot algorithm, the DFSA algorithm estimates the number of tags in the current recognition stage through the tag estimation algorithm and adjusts the frame length at the beginning of each frame recognition stage according to the estimated number of tags to be recognized. Therefore, the key to the improvement of DFSA algorithm is as follows: (1) improve the accuracy of the estimation of the number of tags and adjust the frame length reasonably; (2) reduce the number of idle time slots and collision time slots. The working principle of the DFSA algorithm is illustrated in Figure1.Figure 1
The working principle of DFSA algorithm.


## 2.2. Optimal Frame Size

We suppose the number of effective tags isN, and the length of frame size is L. Therefore, the probability of choosing the same time slot for any m tags can be expressed as(1)pm=CNm1Lm1−1LN−m.For a successful slot, there is only one tag send its IDs to reader. So, the probability of successful slot is(2)ps=CN11L1−1LN−1.When the current time slot has no tag send ID, it is defined as an idle time slot and its probability can be expressed as(3)pe=1−1LN.Only there are three slot condition during the recognition process: successful slot, idle slot, and collision slot. Thus, the probability of collision slot is(4)pc=1−ps−pe=1−N+L−1L1−1LN−1.According to (1), (2), and (3), we can get the expected values of successful slot, idle slot, and collision slot as follows:(5)Es=N1−1LN−1,Ee=L1−1LN,Ec=L−N+L−11−1LN−1.We denote the throughput rate as the ratio of successful slots to total slotsL, denoted as S. Thus, S is as follows:(6)S=NL1−1LN−1.In order to maximizeS, (7)dSdN=1L1−LN−1+NL1−LN−1ln1−1L=1−1LN−11+Nln1−1L1L=0.The result of maximize is(8)L=11−e−1/N.When the number of tags is large enough, we will obtain(9)L=11−e−1/N=e1/Ne1/N−1≈1/N+11/N=N+1,N≫1.As shown in (9), the maximum throughput rate S will be realized if the frame size L is equal to tag number N.


## 3. The Proposed Novel Algorithm

In this section, we will introduce the grouping strategy of tags and optimization of frame size in detail.


### 3.1. Initialization

As shown in (9), when the number of tags and slot is the same, the system can be achieve the highest throughput rate. But for a large-scale RFID system, the reader set time slot number is usually defined 20−28; namely, frame length range is 1–256 [10]. When the number of tags is much greater than the number of time slots, a large number of tags will choose the same time slot for transmission. Thus, there will be a large number of collision time slots in the first frame. Due to the nature of passive tags, the reader is unable to quantify the exact number of collision tags per collision slot, resulting in inappropriate frame length adjustments. Therefore, we consider dividing the initial tag set into several small subsets before the tag estimation of the first frame. The number of tags in each group is adjusted within the conventional frame length range to increase the accuracy of tag estimation.To reduce the number of collision slots in the initial frame, we consider dividing the initial tag set into several small subsets before recognition. In the case of 96-bit tag IDs, the ID and prefix of the tag and their relationships can be integrated into a full binary tree. The full binary tree only shows all “possible” cases of ID and prefix. Assuming that the tags are uniformly and randomly distributed in the whole leaf node of the full binary tree, the leaf nodes can be divided into multiple subsets by selecting the prefix parent node in the upper layer. Then, the inverse probability function is used to calculate the probability and expectation of each node containing the tags. Finally, the initial tag set is divided according to the length of the initial frame.LetN denote the full length of ID, M is the number of IDs, and L is the default frame size. So, a N-bit tag has 2N different IDs, which means that the probability of a tag in each leaf node is p=1/2N. Let Pl be the probability that the leaf node contains tags. We have(10)pl=M2N.According to formula (10), in order to achieve maximum throughput and identify more tags in the first frame, we approximate the number of estimated tags in the subset to the frame length. Then, the number of layers that needed to achieve the expected number of tags is(11)log2L⋅2NM.Therefore, the number of layers divided is as follows:(12)S=N−log2L⋅2NM=log2ML.


### 3.2. Estimation of the Tag Number and Probe Frame

In Section3.1, we divide the tags into subsets. In probability theory, the number of tags in a subset should be as close to the frame length as possible, so that the number of collision slots and idle slots should be minimized. But in practice, the number of tags in the subset is still indeterminate. So, the tag estimation algorithm is still needed at the end of each subset poll.To estimate the tag number, this paper applies the traditional [11] to calculate n^. Vogt [12] proposed to estimate the number of tags by minimizing the Euclidean norm between the actual value and the expected value of each slot.(13)n^=minpiN,LLpkN,LLpsN,LL−ninkns,where · is the Euclidean norm, and ni,nk,ns is the number of idle slot, collision slot, and successful slot in total frame.


### 3.3. The Proposed Modified Frame Slotted ALOHA Protocol

#### 3.3.1. Settings for Probe Frames

After grouping in Section3.1, readers can awaken each group of tags by broadcasting different prefixes for tag identification. However, the initial grouping is only based on the uniform distribution of tags over the whole value space, so there are three situations in the actual identification process. (1) The number of tags in current subset is close to the value of the initial frame length; the polling can be carried out directly or through appropriate frame adjustment. (2) The number of tags in the subset is much less than the length of the frame or the subset is empty, which will result in a mass of idle slots. The reader can optionally break current frame and merge the few unidentified tags into the next subset. (3) When the number of tags in current subset is much larger than the frame length, there are a mass of collision slots. The reader selects to interrupt the current frame and further splits the subset.The probability of the tag response within every time slot is theoretically the same, that is,p=1/L. The selection of each tag is completely independent and do not interfer with each other. This paper proposes to set a probe frame of length n at the beginning of the initial frame. The probe frame can also detect the situation of the current frame when carrying out tag recognition. The total number of tags is estimated by counting the actual value of collision slots, idle slots, and success slots in the current subframe.The detection framework needs to meet two basic conditions: (1) using individuals to estimate the overall value as accurately as possible; (2) the length of the frames should be as small as possible to facilitate rapid processing of overstocked subsets and almost empty subsets. In order to obtain the appropriate detection frame length, we have carried out experiments onL=64,128,256.The results are as follows.As shown in Figure2, when L = 64, the length of probe frame can be set to l = 8. When L = 128, the length of probe frame can be set to l = 16. When L = 256, the length of probe frame can be set to l = 32.Figure 2
(a) MAE withL = 64 in different M. (b) MAE with L = 128 in different M. (c) MAE with L = 256 in different M.
(a)(b)(c)


#### 3.3.2. Algorithm Design

We count the number of successful slots, idle slots, and collision slots in the probe frame as the number of tags increases. A thousand Monte Carlo experiments were done, and the final result was the average of a thousand experiments.As shown in Table2, when the number of tags is quadruple the length of the frame, the actual value of the collision slot is almost equal to the length of the probe frame. This means that when the number of tags in a frame reaches this value, the throughput rate of the tag recognition process is close to zero. Each time slot has two or more tag responses, which means there is no successful slot.Table 2
ni and nk in different frame and probe frame.
Length of frameLength of probe frameNumber of tags481632641282565181024648ni87.866410.320.000.00nk0.020.100.401.464.177.27.78812816ni15.5115.0314.0712.429.625.922.290.280.00nk0.000.020.100.431.474.259.2515.621625632ni31.5031.0030.0428.2925.0019.3012.304.300.6nk0.000.010.050.200.803.008.0019.2030.00So, we chose the number of idle time slots in the probe frame as a metric. Whenni∈l−1,l, the current subset either has no tags or contains only a number of tags far less than the number of time slots. So, after the probe frame section ends, choose to skip the rest of the current frame. This means that tag recognition for the current subset is finished, and the reader will recognize tags in the next subset. When ni∈1,l−1, if the number of tags estimated based on the probe frame matches the setting of the current frame, the reader continues the query for the current frame. And update the value of ni,nk,ns to estimate the frame length of the next frame. When ni∈0,1, the number of tags in current subset is much larger than the length of the initial frame. According to the data in the table, we divide the current subset into four smaller subsets according to the prefix. The proposed algorithm is given in Algorithm 1.Algorithm 1: The proposed algorithm.
(1)
InitializeL,l,S, where L is the initial frame length, l is the detection frame length, and S is the prefix length of the initial grouping, respectively.(2)
while2S>0(3)
while (there is tag response)(4)
Reader broadcast the prefix of current subset and frame lengthL.(5)
Each tag selects a time slot randomly amongL slots and transmits its data to the reader in current slot(6)
Computeni,ns,nk after the reading of l slot(7)
ifni∈1,l−1(8)
ComputeMest and adjust next frame size(9)
else ifni∈l−1,l(10)
2S−1(11)
break(12)
else ifni∈0,1(13)
Goto step 3, divide current subset into four and repeat 3 to 13.(14)
end if(15)
2S−1(16)
end while(17)
end while


## 3.1. Initialization

As shown in (9), when the number of tags and slot is the same, the system can be achieve the highest throughput rate. But for a large-scale RFID system, the reader set time slot number is usually defined 20−28; namely, frame length range is 1–256 [10]. When the number of tags is much greater than the number of time slots, a large number of tags will choose the same time slot for transmission. Thus, there will be a large number of collision time slots in the first frame. Due to the nature of passive tags, the reader is unable to quantify the exact number of collision tags per collision slot, resulting in inappropriate frame length adjustments. Therefore, we consider dividing the initial tag set into several small subsets before the tag estimation of the first frame. The number of tags in each group is adjusted within the conventional frame length range to increase the accuracy of tag estimation.To reduce the number of collision slots in the initial frame, we consider dividing the initial tag set into several small subsets before recognition. In the case of 96-bit tag IDs, the ID and prefix of the tag and their relationships can be integrated into a full binary tree. The full binary tree only shows all “possible” cases of ID and prefix. Assuming that the tags are uniformly and randomly distributed in the whole leaf node of the full binary tree, the leaf nodes can be divided into multiple subsets by selecting the prefix parent node in the upper layer. Then, the inverse probability function is used to calculate the probability and expectation of each node containing the tags. Finally, the initial tag set is divided according to the length of the initial frame.LetN denote the full length of ID, M is the number of IDs, and L is the default frame size. So, a N-bit tag has 2N different IDs, which means that the probability of a tag in each leaf node is p=1/2N. Let Pl be the probability that the leaf node contains tags. We have(10)pl=M2N.According to formula (10), in order to achieve maximum throughput and identify more tags in the first frame, we approximate the number of estimated tags in the subset to the frame length. Then, the number of layers that needed to achieve the expected number of tags is(11)log2L⋅2NM.Therefore, the number of layers divided is as follows:(12)S=N−log2L⋅2NM=log2ML.


## 3.2. Estimation of the Tag Number and Probe Frame

In Section3.1, we divide the tags into subsets. In probability theory, the number of tags in a subset should be as close to the frame length as possible, so that the number of collision slots and idle slots should be minimized. But in practice, the number of tags in the subset is still indeterminate. So, the tag estimation algorithm is still needed at the end of each subset poll.To estimate the tag number, this paper applies the traditional [11] to calculate n^. Vogt [12] proposed to estimate the number of tags by minimizing the Euclidean norm between the actual value and the expected value of each slot.(13)n^=minpiN,LLpkN,LLpsN,LL−ninkns,where · is the Euclidean norm, and ni,nk,ns is the number of idle slot, collision slot, and successful slot in total frame.


## 3.3. The Proposed Modified Frame Slotted ALOHA Protocol

### 3.3.1. Settings for Probe Frames

After grouping in Section3.1, readers can awaken each group of tags by broadcasting different prefixes for tag identification. However, the initial grouping is only based on the uniform distribution of tags over the whole value space, so there are three situations in the actual identification process. (1) The number of tags in current subset is close to the value of the initial frame length; the polling can be carried out directly or through appropriate frame adjustment. (2) The number of tags in the subset is much less than the length of the frame or the subset is empty, which will result in a mass of idle slots. The reader can optionally break current frame and merge the few unidentified tags into the next subset. (3) When the number of tags in current subset is much larger than the frame length, there are a mass of collision slots. The reader selects to interrupt the current frame and further splits the subset.The probability of the tag response within every time slot is theoretically the same, that is,p=1/L. The selection of each tag is completely independent and do not interfer with each other. This paper proposes to set a probe frame of length n at the beginning of the initial frame. The probe frame can also detect the situation of the current frame when carrying out tag recognition. The total number of tags is estimated by counting the actual value of collision slots, idle slots, and success slots in the current subframe.The detection framework needs to meet two basic conditions: (1) using individuals to estimate the overall value as accurately as possible; (2) the length of the frames should be as small as possible to facilitate rapid processing of overstocked subsets and almost empty subsets. In order to obtain the appropriate detection frame length, we have carried out experiments onL=64,128,256.The results are as follows.As shown in Figure2, when L = 64, the length of probe frame can be set to l = 8. When L = 128, the length of probe frame can be set to l = 16. When L = 256, the length of probe frame can be set to l = 32.Figure 2
(a) MAE withL = 64 in different M. (b) MAE with L = 128 in different M. (c) MAE with L = 256 in different M.
(a)(b)(c)


### 3.3.2. Algorithm Design

We count the number of successful slots, idle slots, and collision slots in the probe frame as the number of tags increases. A thousand Monte Carlo experiments were done, and the final result was the average of a thousand experiments.As shown in Table2, when the number of tags is quadruple the length of the frame, the actual value of the collision slot is almost equal to the length of the probe frame. This means that when the number of tags in a frame reaches this value, the throughput rate of the tag recognition process is close to zero. Each time slot has two or more tag responses, which means there is no successful slot.Table 2
ni and nk in different frame and probe frame.
Length of frameLength of probe frameNumber of tags481632641282565181024648ni87.866410.320.000.00nk0.020.100.401.464.177.27.78812816ni15.5115.0314.0712.429.625.922.290.280.00nk0.000.020.100.431.474.259.2515.621625632ni31.5031.0030.0428.2925.0019.3012.304.300.6nk0.000.010.050.200.803.008.0019.2030.00So, we chose the number of idle time slots in the probe frame as a metric. Whenni∈l−1,l, the current subset either has no tags or contains only a number of tags far less than the number of time slots. So, after the probe frame section ends, choose to skip the rest of the current frame. This means that tag recognition for the current subset is finished, and the reader will recognize tags in the next subset. When ni∈1,l−1, if the number of tags estimated based on the probe frame matches the setting of the current frame, the reader continues the query for the current frame. And update the value of ni,nk,ns to estimate the frame length of the next frame. When ni∈0,1, the number of tags in current subset is much larger than the length of the initial frame. According to the data in the table, we divide the current subset into four smaller subsets according to the prefix. The proposed algorithm is given in Algorithm 1.Algorithm 1: The proposed algorithm.
(1)
InitializeL,l,S, where L is the initial frame length, l is the detection frame length, and S is the prefix length of the initial grouping, respectively.(2)
while2S>0(3)
while (there is tag response)(4)
Reader broadcast the prefix of current subset and frame lengthL.(5)
Each tag selects a time slot randomly amongL slots and transmits its data to the reader in current slot(6)
Computeni,ns,nk after the reading of l slot(7)
ifni∈1,l−1(8)
ComputeMest and adjust next frame size(9)
else ifni∈l−1,l(10)
2S−1(11)
break(12)
else ifni∈0,1(13)
Goto step 3, divide current subset into four and repeat 3 to 13.(14)
end if(15)
2S−1(16)
end while(17)
end while


## 3.3.1. Settings for Probe Frames

After grouping in Section3.1, readers can awaken each group of tags by broadcasting different prefixes for tag identification. However, the initial grouping is only based on the uniform distribution of tags over the whole value space, so there are three situations in the actual identification process. (1) The number of tags in current subset is close to the value of the initial frame length; the polling can be carried out directly or through appropriate frame adjustment. (2) The number of tags in the subset is much less than the length of the frame or the subset is empty, which will result in a mass of idle slots. The reader can optionally break current frame and merge the few unidentified tags into the next subset. (3) When the number of tags in current subset is much larger than the frame length, there are a mass of collision slots. The reader selects to interrupt the current frame and further splits the subset.The probability of the tag response within every time slot is theoretically the same, that is,p=1/L. The selection of each tag is completely independent and do not interfer with each other. This paper proposes to set a probe frame of length n at the beginning of the initial frame. The probe frame can also detect the situation of the current frame when carrying out tag recognition. The total number of tags is estimated by counting the actual value of collision slots, idle slots, and success slots in the current subframe.The detection framework needs to meet two basic conditions: (1) using individuals to estimate the overall value as accurately as possible; (2) the length of the frames should be as small as possible to facilitate rapid processing of overstocked subsets and almost empty subsets. In order to obtain the appropriate detection frame length, we have carried out experiments onL=64,128,256.The results are as follows.As shown in Figure2, when L = 64, the length of probe frame can be set to l = 8. When L = 128, the length of probe frame can be set to l = 16. When L = 256, the length of probe frame can be set to l = 32.Figure 2
(a) MAE withL = 64 in different M. (b) MAE with L = 128 in different M. (c) MAE with L = 256 in different M.
(a)(b)(c)


## 3.3.2. Algorithm Design

We count the number of successful slots, idle slots, and collision slots in the probe frame as the number of tags increases. A thousand Monte Carlo experiments were done, and the final result was the average of a thousand experiments.As shown in Table2, when the number of tags is quadruple the length of the frame, the actual value of the collision slot is almost equal to the length of the probe frame. This means that when the number of tags in a frame reaches this value, the throughput rate of the tag recognition process is close to zero. Each time slot has two or more tag responses, which means there is no successful slot.Table 2
ni and nk in different frame and probe frame.
Length of frameLength of probe frameNumber of tags481632641282565181024648ni87.866410.320.000.00nk0.020.100.401.464.177.27.78812816ni15.5115.0314.0712.429.625.922.290.280.00nk0.000.020.100.431.474.259.2515.621625632ni31.5031.0030.0428.2925.0019.3012.304.300.6nk0.000.010.050.200.803.008.0019.2030.00So, we chose the number of idle time slots in the probe frame as a metric. Whenni∈l−1,l, the current subset either has no tags or contains only a number of tags far less than the number of time slots. So, after the probe frame section ends, choose to skip the rest of the current frame. This means that tag recognition for the current subset is finished, and the reader will recognize tags in the next subset. When ni∈1,l−1, if the number of tags estimated based on the probe frame matches the setting of the current frame, the reader continues the query for the current frame. And update the value of ni,nk,ns to estimate the frame length of the next frame. When ni∈0,1, the number of tags in current subset is much larger than the length of the initial frame. According to the data in the table, we divide the current subset into four smaller subsets according to the prefix. The proposed algorithm is given in Algorithm 1.Algorithm 1: The proposed algorithm.
(1)
InitializeL,l,S, where L is the initial frame length, l is the detection frame length, and S is the prefix length of the initial grouping, respectively.(2)
while2S>0(3)
while (there is tag response)(4)
Reader broadcast the prefix of current subset and frame lengthL.(5)
Each tag selects a time slot randomly amongL slots and transmits its data to the reader in current slot(6)
Computeni,ns,nk after the reading of l slot(7)
ifni∈1,l−1(8)
ComputeMest and adjust next frame size(9)
else ifni∈l−1,l(10)
2S−1(11)
break(12)
else ifni∈0,1(13)
Goto step 3, divide current subset into four and repeat 3 to 13.(14)
end if(15)
2S−1(16)
end while(17)
end while


## 4. Simulation Results

In this section, the Monte Carlo simulation method is used to verify the performance of the proposed GP-DFSA algorithm, and the comparison with the existing DFSA algorithm is made. Performance measures used in the simulation include tag unit collision and system efficiency. All of simulations are performed with 1000 turns [18–23].We compared the different algorithm in terms of collision slots of per tag by varying the number of tagsM from 1000 to 8000, where the initial frame length L = 64 and the probe frame length l = 8. DFSA algorithm only adds grouping mechanism but does not add probe frame mechanism. We conducted a thousand Monte Carlo experiments, and the results are shown in Figure 2. GP-DFSA is mainly used to solve the problem of large collision time slots caused by label backlog in the classical algorithm. So, the collision slots of per tag are counted in Figure 2.As shown in Figure3, when the number of tags reaches 2000, the collision slot of per tag of DFSA algorithm increases sharply. However, with the increase of the number of tags, the unit collision time slot of the proposed GP-DFSA algorithm is all below 1, and the minimum time slot can reach 0.7. When the number of tags M to be identified is 1000–8000, we simulate the system throughput of GP-DFSA algorithm and DFSA algorithm. The result is shown in Figure 4. Due to the influence of a mass of collision slots, although the statistics of idle slots and successful slots are close to the results of the GP-DFSA algorithm, the collision time slots of DFSA algorithm increase. That results in the total recognition time slots being far greater than those of GP-DFSA algorithm.Figure 3
Collision slots of per tag.Figure 4
System throughput.In the previously mentioned experiment, we chose the initial frame lengthL = 64, but as the number of tags increases, the number of collision slots increases at a faster rate. This is because the number of initial packets grows exponentially, meaning that more probe frames are needed, resulting in an increase in the number of idle slots. Therefore, we made a horizontal comparison of using different initial frame lengths L for tag recognition under the same number of tags, where L=64,128,256. The comparison results are summarized in Table 3.Table 3
Different initial frame lengthsl for the tag number.
Length of frameParameter10002000300040005000600070008000L = 64Throughput0.330.320.330.340.340.330.350.33Collision slot9521710235732013752502261507014L = 128Throughput0.330.330.320.330.320.330.330.33Collision slot9541772239933363668481862587198L = 256Throughput0.310.320.330.320.350.350.350.33Collision slot9021720215533893194433657366813It can be seen from Table3 that the initial frame length can be selected optimally for the number of tags in different quantity intervals.


## 5. Conclusion

In order to improve the efficiency of tag collection under large-scale tag sets, GP-DFSA algorithm is proposed in this paper. Readers can pregroup a set of tags using prefixes and recognize tags by grouping them using the tag silence mechanism. The probe frame is set in the initial frame of each grouping, and the reader can choose to skip current frame or continue to recognize or regroup based on the result of the probe frame. Through our simulation, G-DFSA in the system throughput rate is better than the classical DFSA algorithm.We still have some work to do in the future. The tag algorithm is optimized to provide more overall and accurate estimation with as few probe frames as possible. We will further optimize the length of the initial frame and probe frame to obtain more accurate estimates with the least amount of time slots.



---

*Source: 1812670-2022-04-13.xml*