1. Introduction
Radio frequency identification (RFID) is an integral driver of the Internet of Things (IoT), serving as an essential connection between low-powered and non-powered devices and IoT environments [1]. The RFID protocol known as EPCglobal Class-1 Generation-2 (Gen2) [2] is a standard that was developed specifically for these types of applications. An RFID reader is capable of transmitting data to hundreds of passive (non-powered) tags in a matter of seconds, regardless of the distance between the tags and the reader (10 m). The lightweight nature of the Gen2 standard is its most notable feature. Passive RFID systems necessitate a collision arbitration protocol to serialize tag responses and thereby reduce the likelihood of collisions arising from the shared nature of the RF medium. The Q–Algorithm, which has been incorporated into the Gen2 standard, is an algorithm for collision arbitration that exemplifies its lightweight characteristic by consisting of only a few elementary arithmetic operations.
The Q–Algorithm comprises a limited number of essential logical and arithmetic operations. [2]. When the algorithm examines the response set Q in detail, it appends the constant Δ to Q in the case of collision and deducts the same Δ from Q in the absence of a reply. The algorithm modifies the size of frame [TeX:] $$2^Q$$ in response to a modification in the Q value. Gen2 RFID readers detect tags in IoT environments without depleting batteries due to the straightforwardness of the logic and the utilization of a minimal number of computations. Another advantageous feature that Q–Algorithm inherits is the ability to adjust the size of the frame early, allowing for the cancellation of a disadvantageous frame size prior to the frame's termination. A crucial attribute of a high-quality collision arbitration protocol [3], the feature could have a significant effect on the identification performance in environments with mobile tags and/or large-scale tags, such as highways and smart factories.
An initial group of researchers made a restricted number of efforts to enhance the performance of the Q–Algorithm [4-6]. [TeX:] $$Q^{+}-\text {Algorithm}$$ [4] proposed differentiating into constants denoted as [TeX:] $$C_{coll } \text { and } C_{idle },$$ which correspond to collision and idle slots, respectively. Additionally, the research identified the optimal [TeX:] $$C_{idle } \text { to } C_{coll },$$ ratio [TeX:] $$(\mathrm{e}-2 \approx 0.7183)$$ that maximizes the throughput of tag identification per slot. Similarly, [5] refined computational techniques for ascertaining the Q value. Nevertheless, the research also aimed to achieve a per-slot throughput, which implies that the algorithm's performance is, in theory, comparable to that of [TeX:] $$Q^{+}-\text {Algorithm}$$.
In a separate effort to enhance the Q–Algorithm, [6] addresses the metric of tag identification efficiency as a per-time throughput. This is significant because, according to the Gen2 standard, the duration of each slot (i.e., success, idle, and collision) differs. The algorithms were developed to identify [TeX:] $$C_{idle } \text { and } C_{coll },$$ that minimize the collision slots, which are considerably longer than the idle slots, as opposed to the total number of consumed slots, as the studies consistently acknowledged the distinction. While this strategy seemed logical at first glance, the thorough optimization of the Q–Algorithm with respect to time efficiency has yet to be investigated. The lack of maturity in previous research efforts has resulted in limited interest in the Q–Algorithm for a considerable period of time, notwithstanding its evident advantages of being lightweight and possessing an inherent capability for early adjustment.
On the other hand, considerations of time efficiency were followed in the literature of dynamic framed slotted ALOHA (DFSA). In [7], the authors evaluated the time efficiency of an FSA protocol through temporal analysis and proposed their own optimized parameters for fast tag identification. In order to further enhance the time efficiency of an FSA protocol, [8] implemented early frame adjustment by utilizing an inherent feature of the Q–Algorithm. In contrast, traditional DFSA algorithms have been dependent on onerous statistical estimations. Even in the most recent algorithms, such as [9] and [10], which demonstrated exceptional performance in optimizing frame sizes to facilitate rapid identification, each slot required extra computations for tag number estimation.
This study presents a theoretical analysis of the time performance of the Q–Algorithm. The detailed structure of a time-efficient Q–Algorithm (SwiftQ) is obtained from this analysis. A discourse on the outcomes of the experiment ensues subsequent to an experimental investigation encompassing alternative prominent Q–Algorithm variants and competitive DFSA algorithms. Following is a summary of the contributions made by this paper:
· The optimized parameters for a time-efficient Q–Algorithm and a comprehensive analysis of the Q– Algorithm's time performance were presented.
· An assessment of SwiftQ's performance was conducted to compare it to other Q–Algorithm variants and cutting-edge DFSA algorithms. The evaluation provided a performance evaluation that identified the key factors influencing the experimental outcomes.
· SwiftQ, a novel RFID collision arbitration algorithm that maintains the Q–Algorithm's early frame adjustment and low computation cost, enables Gen2-based large-scale identification environments to identify tags in an exceedingly competitive amount of time. This achievement is the result of these collective efforts.
2. Time-Efficient Q–Algorithm
This section begins with an evaluation of the time performance of a FSA protocol that serves as the foundation for the Q–Algorithm. Based on the theoretical analysis, we then propose a Q–Algorithm that is exceptionally efficient.
2.1 Identification Time Analysis
A reader communicates a frame size to the tags in the FSA protocol, from which the tags choose their slots at random. In this model, the tag identification delay can be regarded as the mean duration that elapses between two tags that are identified consecutively within this model. The identification delay for a frame size L, given m tags, can be expressed as follows:
The variables [TeX:] $$\tau_{m, L} \text { and } p_{s u c c}$$ represent the estimated length of a frame's time and the probability of accurately identifying a tag within a given slot, denoted as m and L, respectively. Define the probability that r tags will respond in a given slot:
Then the probabilities of a success, an idle, and a collision state are denoted as, [TeX:] $$p_{succ }=\operatorname{Pr}_{m, L}(X=1),$$ [TeX:] $$p_{idle }=\operatorname{Pr}_{m, L}(X=0),$$ and [TeX:] $$p_{coll }=\operatorname{Pr}_{m, L}(X \geq 2),$$ correspondingly. The estimated duration of a frame can subsequently be determined by adding up all the expected delays within the frame, as shown below:
The durations of a success, idle, and collision slot are denoted as [TeX:] $$T_{succ }, T_{idle }, T_{coll },$$ respectively. Note that for the sake of convenience, the delay of the frame itself is disregarded. By applying Eqs. (2) and (3), Eq. (1) can be transformed into
where γ is [TeX:] $$\frac{T_{idle }}{T_{coll }}.$$
2.2 SwiftQ Algorithm
Upon thorough examination of the delay in tag identification, it is possible to optimize the efficiency of tag identification per time by minimizing the aforementioned delay.
In light of the fact that the objective function holds convexity for both m and L, the optimal solution can be achieved by the partial differentiation of the function with respect to m (m ≥ 1) rather than L, which lacks of the inverse of the derivative. When arranged [TeX:] $$\frac{\partial \Upsilon}{\partial m}=0$$ in accordance with L, the optimal frame size is obtained as shown below.
where [TeX:] $$W(\cdot)$$ is the Lambert’s W function, and [TeX:] $$\Theta \text { is }(\gamma-1) / e \text {. }$$ Consequently, under the optimal condition, we obtain [TeX:] $$p_{idle }^* \text { and } p_{c o l l}^*$$ by applying L to the probabilities. By utilizing these probabilities, it is possible to construct a stationary condition that converges to the optimal value while ensuring that the frame size remains constant.
By considering limits in [TeX:] $$\frac{p_{c o l l}^*}{p_{idle }^*}$$ as [TeX:] $$m \rightarrow \infty \text { for } 0\lt \gamma\lt 1$$ for this relationship, we can obtain the asymptotic proportions of idle and collision slots under optimal conditions. Consequently, we have achieved the optimal ratio [TeX:] $$\frac{C_{c o l l}^*}{C_{idle }^*}$$.
It is important to observe that the ratio of C values and the ratio of probabilities are reciprocal, as demonstrated in [4]. The procedure of the SwiftQ algorithm is described in detail in Algorithm 1. The algorithm's structure is identical to that of the Q–Algorithm, with the exception that no tag estimation scheme is required. Distinguishing it from the Q–Algorithm are merely the bias constants [TeX:] $$C_{idle }^* \text { and } C_{c o l l}^*$$.
The procedure of the SwiftQ algorithm
3. Experimental Study
In order to evaluate the performance of both the proposed algorithm and the reference models, exhaustive Monte Carlo simulations were conducted. In two evaluation sessions, the performance of the collision arbitration algorithms was assessed with different comparison sets:
1) Set I (Comparison of Q algorithms): For the purpose of this comparison, the original Q–Algorithm [2] and its strict variants [TeX:] $$Q^{+}-\text {Algorithm}$$ [4] and fastQ [6] were chosen as Set I algorithms. In order to demonstrate the capabilities of the SwiftQ algorithm, we set comparison targets against DFSA algorithms, which operate using techniques for determining frame size and tag estimation.
2) Set II (To compare with DFSA algorithms): For the purpose of this comparison, two DFSA algorithms relatively new and competitive were selected as the targets: optimal frame length analysis (OFLA) [9] and time and energy saving-based frame adjustment strategy (TES-FAS) [10]. The protocol parameters utilized in the environment were identical to those described in [6]: 1828.13 μsec, 260.625 μsec, and 516.625 μsec were used for [TeX:] $$T_{succ }, T_{idle }, T_{coll }$$ respectively.
To ensure the integrity of the assessment, the values of [TeX:] $$C_{idle },text{ and } T_{coll }$$ were recalculated using the protocol parameters mentioned earlier. In particular, the values of [TeX:] $$C_{idle },text{ and } T_{coll }$$ for fastQ remained unchanged from those reported in [8]. In order to facilitate comparisons, the [TeX:] $$C_{idle }$$ values were computed using the ratios [TeX:] $$\frac{C_{idle }}{C_{coll}}$$ proposed by each algorithm, while the [TeX:] $$C_{coll}$$ values of SwiftQ and [TeX:] $$Q^{+}-\text {Algorithm}$$ were set to be identical to the value of the fastQ algorithm. The adjusted parameters are summarized in Table 1. Each algorithm was executed on MATLAB R2020b, and simulations were iterated with varying random seeds for a maximum of R=5,000 iterations.
Fig. 1 illustrates the identification delays experienced by collision arbitration algorithms based on the Q–Algorithm when attempting to identify a single tag. The performance of the proposed algorithm, SwiftQ, is evidently superior to that of other reference algorithms, as illustrated in Fig. 1(a). An intriguing observation is that fastQ exhibits a performance that is comparatively inferior to SwiftQ, despite the utilization of its unique parameter for the protocol during the simulation. The [TeX:] $$C_{coll}$$ value is given greater weight than the [TeX:] $$C_{idle}$$ value by the majority of algorithms, excluding the Q–Algorithm, which were designed to be more susceptive to collision slots in order to quickly avoid undersized frames, which can incur a tremendous overhead. Therefore, [TeX:] $$\frac{c_{idle }}{c_{coll }}\lt 1$$ remains valid for those algorithms. Although this is a logical strategy, all of the algorithms except SwiftQ failed to account for a strict optimization of the [TeX:] $$\frac{c_{idle }}{c_{coll }}$$ value. As an illustration, the fastQ algorithm utilizes a [TeX:] $$\frac{c_{idle }}{c_{coll }}$$ value of 0.7081; however, the optimal ratio is nearly half of this amount (=0.3906); thus, while the fastQ algorithm is fast, it is not the fastest.
Parameters used for the algorithms
The argument presented earlier is supported by the results obtained from a comprehensive simulation, which are illustrated in Fig. 1(b). On the [TeX:] $$C_{coll }-\frac{C_{idle }}{C_{coll }}$$ plane, the simulation outcomes derived from 500 iterations for each [TeX:] $$C_{coll }$$ and [TeX:] $$\frac{C_{idle }}{C_{coll }}$$ pair exhibit a conspicuous convex shape. The SwiftQ algorithm is positioned in the vicinity of the optimal region of the convex. fastQ occupies the highest position, closely followed by the [TeX:] $$Q^{+}-\text {Algorithm}.$$ This shows why the performance of fastQ and [TeX:] $$Q^{+}-\text {Algorithm}$$ in Fig. 1(a) was comparable. Consequently, this verifies that the proposed SwiftQ algorithm successfully identified tags in an exceptionally efficient manner by utilizing the optimized parameter [TeX:] $$\frac{C_{idle }}{C_{coll }}.$$
Performance comparison of different collision arbitration algorithms based on Q–Algorithm: (a) performance comparison with other Q–Algorithm variants and (b) tag identification time per tag, with 500 tags, varying [TeX:] $$C_{coll } \text{ and } \frac{C_{idle }}{C_{coll }}.$$
In relation to the simulation results obtained from Group II, SwiftQ demonstrates an exceptional level of performance, consistently outperforming the alternative algorithms across all tag counts (Fig. 2). Considering the fact that both OFLA and TES-FAS are sophisticated algorithms specifically engineered to maximize frame size while minimizing execution time, the disparity in performance is truly astounding. Following an exhaustive evaluation, it was ascertained that the flawed estimation of tag quantities resulted in a deterioration of both DFSA algorithms. With respect to OFLA, it was affected by both the imprecise estimation of the number of tags and the flawed computation of the frame dimensions. OFLA employed a methodology similar to SwiftQ to ascertain the optimal frame size; however, it relied on the subsequent approximation obtained with a numerical procedure:
Performance comparison to DFSA algorithms.
In this environment, the linear approximation coefficient a was defined as 1.44. The reason for the variation in OFLA's performance along the tag numbers is as follows. Whether Eq. (9) approaches or recedes from the optimal curve, which is a non-linear as shown in Eq. (6), caused OFLA's time efficiency to fluctuate repeatedly. The primary cause of degradation in the case of TES-FAS was its imprecise estimation of tags. The tag estimator utilized in TES-FAS, the maximum a posteriori (MAP) estimator, is renowned for its exceptional accuracy [9]. Nevertheless, the performance of the estimator was compromised due to the sub-framing scheme, which incorporates its own early frame adjustment function. A current frame size is reevaluated by the sub- framing scheme whenever its sub-frame sizes are reached. Considerable estimation errors accumulated due to the reduction in sample sizes required for tag number estimation caused by the sub-framing scheme's small frame sizes. While early frame adjustment might have provided TES-FAS with an advantage over the evaluation, particularly in the large-scale deployment described in this study, the deterioration of tag number estimation rendered the algorithm caught between two tradeoffs.
On the contrary, SwiftQ effectively identified an analytical solution for the ideal frame size and proposed the optimal correlation between [TeX:] $$C_{idle } \text{ and } C_{coll },$$ all while preserving the advantages of the Q–Algorithm. It should be noted that this outcome was obtained in the absence of computation cost, an aspect where SwiftQ exhibits the greatest advantage in comparison to the alternative DFSA algorithms. It was assumed that the computation cost is negligible when we conceded that the redundant computation cost of DFSA algorithms, including the MAP estimator, could be reduced to that of QAlgorithm- based algorithms through the use of an additional memory space and lookup [9] (0.3674 μs and 0.8451 μs, respectively, based on the computing capability and computation cost provided in [8] and [9]). Unless the lookup table was taken into account, the computation time of 828 μs should be added to the per tag identification time TES-FAS. Put simply, SwiftQ attained the exact same level of performance as the Q–Algorithm while significantly reducing the computation cost, all without requiring any supplementary resources.
4. Conclusion
A novel and exceptionally time-efficient Q–Algorithm was introduced in this paper to facilitate collision arbitration in massive identification environments. On the basis of the investigation into the time performance of an FSA protocol implemented with Q–Algorithm, the optimal parameters of Q– Algorithm that maximize the throughput per unit of time were determined. By leveraging the inherent strengths of the Q–Algorithm, our extensive simulations and comparison to the most recent DFSA algorithms demonstrated unequivocally that the SwiftQ algorithm is the most time-efficient algorithm available.