CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> RFID tags are being used in many diverse applications in increasingly large numbers. These capabilities of these tags span from very dumb passive tags to smart active tags, with the cost of these tags correspondingly ranging from a few pennies to many dollars. One of the common problems that arise in any RFID deployment is the problem of quick estimation of the number of tags in the field up to a desired level of accuracy. Prior work in this area has focused on the identification of tags, which needs more time, and is unsuitable for many situations, especially where the tag set is dense. We take a different, more practical approach, and provide very fast and reliable estimation mechanisms. In particular, we analyze our estimation schemes and show that the time needed to estimate the number of tags in the system for a given accuracy is much better than schemes presented in related work. We show that one can estimate the cardinality of tag-sets of any size in near-constant time, for a given accuracy of estimation. <s> BIB001 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> RFID has been gaining popularity for inventory control, object tracking, and supply chain management in warehouses, retail stores, hospitals, etc. Periodically and automatically estimating the number of RFID tags deployed in a large area has many important applications in inventory management and theft detection. The prior work focuses on designing time-efficient algorithms that can estimate tens of thousands of tags in seconds. We observe that, for a RFID reader to access tags in a large area, active tags are likely to be used. These tags are batterypowered and use their own energy for information transmission. However, recharging batteries for tens of thousands of tags is laborious. Unlike the prior work, this paper studies the RFID estimation problem from the energy angle. Our goal is to reduce the amount of energy that is consumed by the tags during the estimation procedure. We design several energy-efficient probabilistic algorithms that iteratively refine a control parameter to optimize the information carried in the transmissions from the tags, such that both the number and the size of the transmissions are minimized. <s> BIB002 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> The RFID technology greatly improves efficiency of many applications including inventory control, object tracking, and supply chain management. In such applications, it is common that new objects are added into the system or existing objects are misplaced in wrong regions. When this happens, fast and complete identification of such tags is very important. We name this problem unknown tag identification, as these tags appear to be unknown by the reader(s) currently covering them. In this paper, we propose a series of protocols to identify unknown tags completely and fast. In these protocols, we develop several novel techniques to efficiently resolve collisions caused by known tags when identifying unknown tags, which greatly improve the time efficiency. To our knowledge, this is the first work that completely identify all the unknown tags with deterministic approaches. Simulation results show the superior performance of the proposed protocols: Compared with a baseline method which collects IDs of all the tags in the system, our best protocol reduces the execution time by 63% in average and by 85% at most. <s> BIB003 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Estimating the number of RFID tags in the region of interest is an important task in many RFID applications. In this paper we propose a novel approach for efficiently estimating the approximate number of RFID tags. Compared with existing approaches, the proposed Probabilistic Estimating Tree (PET) protocol achieves O(loglogn) estimation efficiency, which remarkably reduces the estimation time while meeting the accuracy requirement. PET also largely reduces the computation and memory overhead at RFID tags. As a result, we are able to apply PET with passive RFID tags and provide scalable and inexpensive solutions for large-scale RFID systems. We validate the efficacy and effectiveness of PET through theoretical analysis as well as extensive simulations. Our results suggest that PET outperforms existing approaches in terms of estimation accuracy, efficiency, and overhead. <s> BIB004 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Efficient estimation of tag population in RFID systems has many important applications. In this paper, we present a new problem called differential cardinality estimation, which tracks the population changes in a dynamic RFID system where tags are frequently moved in and out. In particular, we want to provide quick estimation on (1) the number of new tags that are moved in and (2) the number of old tags that are moved out, between any two consecutive scans of the system. We show that the traditional cardinality estimators cannot be applied here, and the tag identification protocols are too expensive if the estimation needs to be performed frequently in order to support real-time monitoring. This paper presents the first efficient solution for the problem of differential cardinality estimation. The solution is based on a novel differential estimation framework, and is named zero differential estimator. We show that this estimator can be configured to meet any pre-set accuracy requirement, with a probabilistic error bound that can be made arbitrarily small. <s> BIB005 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Many algorithms have been introduced to deterministically authenticate Radio Frequency Identification (RFID) tags, while little work has been done to address the scalability issue in batch authentications. Deterministic approaches verify them one by one, and the communication overhead and time cost grow linearly with increasing size of tags. We design a fine-grained batch authentication scheme, INformative Counting (INC), which achieves sublinear authentication time and communication cost in batch verifications. INC also provides authentication results with accurate estimates of the number of counterfeiting tags and genuine tags, while previous batch authentication methods merely provide 0/1 results indicating the existence of counterfeits. We conduct detailed theoretical analysis and extensive experiments to examine this design and the results show that INC significantly outperforms previous work in terms of effectiveness and efficiency. <s> BIB006 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Owing to its superior properties, such as fast identification and relatively long interrogating range over barcode systems, Radio Frequency Identification (RFID) technology has promising application prospects in inventory management. This paper studies the problem of complete identification of missing RFID tag, which is important in practice. Time efficiency is the key performance metric of missing tag identification. However, the existing protocols are ineffective in terms of execution time and can hardly satisfy the requirements of real-time applications. In this paper, a Multi-hashing based Missing Tag Identification (MMTI) protocol is proposed, which achieves better time efficiency by improving the utilization of the time frame used for identification. Specifically, the reader recursively sends bitmaps that reflect the current slot occupation state to guide the slot selection of the next hashing process, thereby changing more empty or collision slots to the expected singleton slots. We investigate the optimal parameter settings to maximize the performance of the MMTI protocol. Furthermore, we discuss the case of channel error and propose the countermeasures to make the MMTI workable in the scenarios with imperfect communication channels. Extensive simulation experiments are conducted to evaluate the performance of MMTI, and the results demonstrate that this new protocol significantly outperforms other related protocols reported in the current literature. <s> BIB007 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Owing to its attractive features such as fast identification and relatively long interrogating range over the classical barcode systems, radio-frequency identification (RFID) technology possesses a promising prospect in many practical applications such as inventory control and supply chain management. However, unknown tags appear in RFID systems when the tagged objects are misplaced or unregistered tagged objects are moved in, which often causes huge economic losses. This paper addresses an important and challenging problem of unknown tag identification in large-scale RFID systems. The existing protocols leverage the Aloha-like schemes to distinguish the unknown tags from known tags at the slot level, which are of low time-efficiency, and thus can hardly satisfy the delay-sensitive applications. To fill in this gap, two filtering-based protocols (at the bit level) are proposed in this paper to address the problem of unknown tag identification efficiently. Theoretical analysis of the protocol parameters is performed to minimize the execution time of the proposed protocols. Extensive simulation experiments are conducted to evaluate the performance of the protocols. The results demonstrate that the proposed protocols significantly outperform the currently most promising protocols. <s> BIB008 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Radio Frequency Identification (RFID) technology has been widely used in inventory management in many scenarios, e.g., warehouses, retail stores, hospitals, etc. This paper investigates a challenging problem of complete identification of missing tags in large-scale RFID systems. Although this problem has attracted extensive attention from academy and industry, the existing work can hardly satisfy the stringent real-time requirements. In this paper, a Slot Filter-based Missing Tag Identification (SFMTI) protocol is proposed to reconcile some expected collision slots into singleton slots and filter out the expected empty slots as well as the unreconcilable collision slots, thereby achieving the improved time-efficiency. The theoretical analysis is conducted to minimize the execution time of the proposed SFMTI. We then propose a cost-effective method to extend SFMTI to the multi-reader scenarios. The extensive simulation experiments and performance results demonstrate that the proposed SFMTI protocol outperforms the most promising Iterative ID-free Protocol (IIP) by reducing nearly 45% of the required execution time, and is just within a factor of 1.18 from the lower bound of the minimum execution time. <s> BIB009 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Unknown RFID tags appear when the unread tagged objects are moved in or tagged objects are misplaced. This paper studies the practically important problem of unknown tag detection while taking both time-efficiency and energy-efficiency of battery-powered active tags into consideration. We first propose a Sampling Bloom Filter which generalizes the standard Bloom Filter. Using the new filtering technique, we propose the Sampling Bloom Filter-based Unknown tag Detection Protocol (SBF-UDP), whose detection accuracy is tunable by the end users. We present the theoretical analysis to minimize the time and energy costs. SBF-UDP can be tuned to either the time-saving mode or the energy-saving mode, according to the specific requirements. Extensive simulations are conducted to evaluate the performance of the proposed protocol. The experimental results show that SBF-UDP considerably outperforms the previous related protocols in terms of both time-efficiency and energy-efficiency. For example, when 3 or more unknown tags appear in the RFID system with 30 000 known tags, the proposed SBF-UDP is able to successfully report the existence of unknown tags with a confidence more than 99%. While our protocol runs 9 times faster than the fastest existing scheme and reducing the energy consumption by more than 80%. <s> BIB010 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> Radio frequency identification (RFID) systems have been widely deployed for various applications such as object tracking, 3-D positioning, supply chain management, inventory control, and access control. This paper concerns the fundamental problem of estimating RFID tag population size, which is needed in many applications such as tag identification, warehouse monitoring, and privacy-sensitive RFID systems. In this paper, we propose a new scheme for estimating tag population size called Average Run-based Tag estimation (ART). The technique is based on the average run length of ones in the bit string received using the standardized framed slotted Aloha protocol. ART is significantly faster than prior schemes. For example, given a required confidence interval of 0.1% and a required reliability of 99.9%, ART is consistently 7 times faster than the fastest existing schemes (UPE and EZB) for any tag population size. Furthermore, ART's estimation time is provably independent of the tag population sizes. ART works with multiple readers with overlapping regions and can estimate sizes of arbitrarily large tag populations. ART is easy to deploy because it neither requires modification to tags nor to the communication protocol between tags and readers. ART only needs to be implemented on readers as a software module. <s> BIB011 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> The widely used RFID tags impose serious privacy concerns as a tag responds to queries from readers no matter they are authorized or not. The common solution is to use a commercially available blocker tag which behaves as if a set of tags with known blocking IDs are present. The use of blocker tags makes RFID estimation much more challenging as some genuine tag IDs are covered by the blocker tag and some are not. In this paper, we propose REB, the first RFID estimation scheme with the presence of blocker tags. REB uses the framed slotted Aloha protocol specified in the C1G2 standard. For each round of the Aloha protocol, REB first executes the protocol on the genuine tags and the blocker tag, and then virtually executes the protocol on the known blocking IDs using the same Aloha protocol parameters. The basic idea of REB is to conduct statistically inference from the two sets of responses and estimate the number of genuine tags. We conduct extensive simulations to evaluate the performance of REB, in terms of time-efficiency and estimation reliability. The experimental results reveal that our REB scheme runs tens of times faster than the fastest identification protocol with the same accuracy requirement. <s> BIB012 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> RFID is one of the most important automatic identification techniques in the future IoT world. Compared with the other techniques, RFID has various advantages such as no requirement of line of sight, the capability of wireless communication, low cost, small size, and so on. This article discusses two types of anomaly tags, i.e., missing tags and unknown tags, which usually appear due to theft or product misplacement. Generally, there are two categories of anomaly tag pinpointing protocols: boolean detection, which aims at probabilistically determining whether there exist anomaly tags or not; and exact identification, which aims at identifying all anomaly tag IDs. This article first conducts a comprehensive survey of the existing anomaly tag pinpointing protocols, particularly emphasizing their evolution road. After that, we also conduct a taxonomy of the existing protocols and summarize their pros and cons. Finally, we discuss some technical challenges and problems that have not been covered yet, and point out the potential opportunities in RFID research and applications. <s> BIB013 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> With the increasing popularization of radio frequency identification (RFID) technology in the retail and logistics industry, RFID privacy concern has attracted much attention, because a tag responds to queries from readers no matter they are authorized or not. An effective solution is to use a commercially available blocker tag that behaves as if a set of tags with known blocking IDs are present. However, the use of blocker tags makes the classical RFID estimation problem much more challenging, as some genuine tag IDs are covered by the blocker tag and some are not. In this paper, we propose RFID estimation scheme with blocker tags (REB), the first RFID estimation scheme with the presence of blocker tags. REB uses the framed slotted Aloha protocol specified in the EPC C1G2 standard. For each round of the Aloha protocol, REB first executes the protocol on the genuine tags and the blocker tag, and then virtually executes the protocol on the known blocking IDs using the same Aloha protocol parameters. REB conducts statistical inference from the two sets of responses and estimates the number of genuine tags. Rigorous theoretical analysis of parameter settings is proposed to guarantee the required estimation accuracy, meanwhile minimizing the time cost and energy cost of REB. We also reveal a fundamental tradeoff between the time cost and energy cost of REB, which can be flexibly adjusted by the users according to the practical requirements. Extensive experimental results reveal that REB significantly outperforms the state-of-the-art identification protocols in terms of both time efficiency and energy efficiency. <s> BIB014 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Efficient Communication Scheduling <s> This paper concerns the practically important problem of multi-category radio frequency identification (RFID) estimation: given a set of RFID tags, we want to quickly and accurately estimate the number of tags in each category. However, almost all the existing RFID estimation protocols are dedicated to the estimation problem on a single set, regardless of tag categories. A feasible solution is to separately execute the existing estimation protocols on each category. The execution time of such a serial solution is proportional to the number of categories, and cannot satisfy the delay-stringent application scenarios. Simultaneous RIFD estimation over multiple categories is desirable, and hence, this paper proposes an approach called simultaneous estimation for multi-category RFID systems (SEM). SEM exploits the Manchester-coding mechanism, which is supported by the ISO 18000-6 RFID standard, to decode the combined signals, thereby simultaneously obtaining the reply status of tags from each category. As a result, multiple bit vectors are decoded from just one physical slotted frame. Built on our SEM, many existing excellent estimation protocols can be used to estimate the tag cardinality of each category in a simultaneous manner. To ensure the predefined accuracy, we calculate the variance of the estimate in one round, as well as the variance of the average estimate in multiple rounds. To find the optimal frame size, we propose an efficient binary search-based algorithm. To address significant variance in category sizes, we propose an adaptive partitioning (AP) strategy to group categories of similar sizes together and execute the estimation protocol for each group separately. Compared with the existing protocols, our approach is much faster, meanwhile satisfying the predefined estimation accuracy. For example, with 20 categories, the proposed SEM+AP is about seven times faster than prior estimation schemes. Moreover, our approach is the only one whose normalized estimation time (i.e., time per category) decreases as the number of categories increases. <s> BIB015
In the future smart warehouse, each screw, tool, or product may be affixed with a sensor or RFID tag for inventory. Due to the contradiction between the large number of sensing devices and the limited communication resources, it is non-trivial to investigate efficient communication scheduling strategies when collecting sensing data from large-scale CPS devices. By saying large-scale, it means thousands of CPS devices working together. For example, in a smart warehouse, there can be tens of thousands of CPS devices such as RFID tags and readers, BLE beacons, Wi-Fi APs, robots, etc. Compared with the existing automatic identification techniques such as barcode, sensor, and Bluetooth, RFID has promising advantages of no requirements on line-of-sight (multiple objects can be identified simultaneously), battery-free (passive tags have almost infinite service time), and small-size (as thin as a paper), which make RFID more suitable for large-scale deployment in future smart industry. Therefore, we discuss RFID communication scheduling in this paper. A general solution is to identify all tags' IDs for inventory. There are two types of tag identification protocols: Aloha-based protocols and tree-based protocols. The Aloha-based protocol is a kind of Time Division Multiple Access (TDMA) mechanism. Multiple tags contend for multiple time slots, and a tag can be successfully identified in a slot when only one tag responds in the selected slot. In tree-based protocols, the RFID reader broadcasts a 0/1 string to query the tags. A tag will respond with its ID once it finds that the queried string is the prefix of its ID. If multiple tags respond, the reader attaches a bit of 0/1 to the end of the previous string. A longer queried string entails the smaller probability of tag collisions. A reader identifies a tag ID when only one tag responds. Although we can gather the most comprehensive data via tag identification protocols, it leads to much overhead regarding time efficiency or energy efficiency. A general solution may not be optimal for a specific problem, e.g., missing tag detection/identification, unknown tag detection/identification, RFID tag cardinality estimation, etc. This is because we only want to know which tags are missing or unknown, and the tag cardinality instead of the exact tag IDs. Hence, plenty of attention had been paid to detection/identification of missing/unknown tags and the tag cardinality estimation. Missing tags mean the tags that should be present in the warehouse but are absent now, which may be caused by theft. In contrary, unknown tags mean the tags that should not be in the warehouse but present now, which may be caused by misplacement. Detection is to judge whether there is anomaly tag or not; identification is to discover all the anomaly tags accurately. The literature BIB013 has conducted a comprehensive survey of the existing anomaly tag (missing BIB009 BIB007 or unknown BIB003 BIB010 BIB008 ) pinpointing protocols, particularly emphasizing the evolution road of the related protocol development. After that, the authors also conduct taxonomy of the existing protocols and summarized their pros and cons, respectively. Hence, this paper will not discuss the details of the protocols that deal with missing/unknown tags again. In this paper, we pay more attention to the existing RFID cardinality estimation protocols. Although RFID identification protocols can be used to obtain the exact tag IDs and obviously get the tag cardinality, the involved execution time is extremely high particularly when the number of tags is large (proportional to the number of tags). In the scenarios when we just want to know the approximate number of tags instead of exact tag IDs, it is not efficient to execute the tag identification protocols. Hence, a great deal of effort was also made by academic communities to study the tag cardinality estimation problem, which is defined as follows. Given a set of RIFD tags whose cardinality is n, a confidence interval α, a reliability β, we want to obtain the estimation resultn such that Pr{|n − n| < n × α} > β. Kodialam et al. took the first step to study this problem and proposed the cardinality estimation schemes called Unified Simple Estimator (USE) and Unified Probabilistic Estimation (UPE), which use the number of empty or collision slots to estimate population sizes BIB001 . USE and UPE are used for the RFID systems that use Aloha-based protocols as the MAC (media access control layer communication mechanisms. The basic working principle of these two protocols is as follows. The reader announces a frame size for all tags and then initializes a time-slotted frame. All the tags randomly select time slots in the forthcoming time frame to respond. The reader records the number of empty slots (no tag response), singleton slots (just one tag response), and collision slots (two or more responses). Intuitively, the more tags there are in the vicinity of the reader, the reader observes more collision slots and less empty slots. Moreover, the authors built a functional relationship between the number of tags and the number of empty/collision slots. Then, the number of observed empty/collision slots can be used to calculate the number of tags. The estimation result from one-time frame may not be accurate due to estimation deviation. Hence, multiple frames of estimation are repeated to achieve fine-grained estimation result. Currently, there are a bunch of RFID estimation protocols. Their performance differs because they use the observed slot status differently. Shahzad et al. used the average run length of non-empty slots (i.e., the average length of continuous non-empty slots) for cardinality estimation, and thus proposed the Average Run-based Tag estimation (ART) protocol BIB011 . ART is faster for obtaining the fine-grained estimation result because the used estimator has smaller variance. Li et al. revisited the problem of cardinality estimation from the new view of energy-efficiency and proposed the Maximum Likelihood Estimator (MLE) BIB002 . The above RFID estimation protocols are all designed for RFID systems that run the Aloha-based MAC communication mechanisms. Zheng et al. studied this problem for RFID systems that run tree-based communication mechanisms, and proposed Probabilistic Estimation Tree (PET) protocols BIB004 . The above estimation protocols can only estimate the number of tags that are currently present in the systems. However, some RFID systems are dynamic because some tags are moved out of the system, and some new tags are added to the system. Moreover, the above methods cannot tell how many tags are absent and how many tags are new. For such dynamic scenarios, Xiao et al. compared the observed frame status and the expected frame status, and used the slot status changes to estimate the number of absent/remaining/new tags BIB005 . Liu et al. found that the estimation protocol in BIB005 requires the reader to monitor the whole long time frame even if the time frame is quite long. To this end, they proposed the Sampling-based Key tag Tracking (S-KT) protocol, in which an RFID reader only needs to observe the status change of expected singleton slots corresponding to key tags instead of the whole time frame. In fact, the ratio of key tags to all current tags is small because key members are usually rare. As a result, even when the whole time frame is long, the number of expected singleton slots could be still, which makes S-KT faster than the protocol in BIB005 . Gong et al. focused on the RFID tag cardinality estimation in the context of anti-counterfeiting, and wanted to estimate the number of counterfeit tags whose IDs are not stored in a database, and finally proposed the INformative Counting (INC) protocol BIB006 . Liu et al. BIB012 concerned with the privacy issue of RFID that when an RFID reader queries a tag; no matter whether the reader is authorized or not, it immediately answers with its ID and other information in a broadcast manner. Although a bunch of cryptography-based authentication protocols have been proposed to tackle with malicious scanning, no one is compliant with the C1G2 standard. Furthermore, these protocols often require computational resources that exceed the capability of commercial C1G2-compliant passive RFID tags. If such additional computational capability is indeed implemented, the cost of such tags will be much more expensive than the C1G2-compliant passive tags. Then, the concept of blocker tag was proposed to protect RFID privacy with almost zero-cost on RFID tags. Its basic principle is that the blocker tag could intentionally create signal collisions to prevent malicious attackers from reading information from the privacy-sensitive RFID tags. However, with the presence of blocker tag, none of the existing RFID tag estimation protocols could correctly estimate the number of genuine tags. Then, Liu et al. proposed the RFID estimation scheme with blocker tags (REB), which first executes the protocol on the genuine tags and the blocker tag, and then virtually executes the protocol on the known blocking IDs using the same Aloha protocol parameters. Liu et al. also conducted statistical analysis on the two frame status obtained from these two Aloha processes to estimate the number of genuine tags. Liu et al. then considered the energy-efficiency for the active RFID systems and studied how to optimize REB protocol for saving energy in BIB014 . A common assumption of the above RFID cardinality estimation protocols is that all tags belong to the same category. However, in practical scenarios, the items are usually categorized according to types, manufacturing countries, brands, etc. Each RFID tag ID contains two fields: category ID that describes the category of the tagged items; and member ID that identifies the individual tagged item within the same category. Hence, the tags also belong to different categories. Traditional tag cardinality estimation protocols can only tell the total tag number instead of the tag number in each category. We naturally desire to know the number of tags in each category. To this end, Liu et al. proposed the estimation protocol called Simultaneous Estimation for Multi-category RFID systems (SEM) BIB015 , which exploits the Single-one Manchester coding string and could know which categories of tags responded in a collision slot. Thus, it can make full use of the information in each type of slot and even the corrupted information in the collision slots, which makes it quite time-efficient.