# A Filter-Based and Parallel Unknown Tag Identification Protocol in Open RFID Systems
## 1 Introduction  
Radio frequency identification (RFID) has a variety of applications in the Internet of Things, such as supply chain management [1; 2; 3; 4; 5], warehouse inventory [6; 7; 8; 9; 10], object monitoring and tracking [11; 12; 13; 14; 15], and posture recognition and localization [16; 17; 18; 19; 20]. In this broad range of RFID-enabled applications, unknown tag identification is crucial for collecting tag IDs from unexpected tags. For example, when a group of tagged objects is moved into a supermarket or warehouse such as Walmart, the manager needs to store these new tag IDs in the back-end database server for subsequent business operations such as daily inventory. In another example of a shopping mall, the customers often misplace frozen food with candy, causing the food to rot, or misplace oil near a lighter, causing great danger. The objective of unknown tag identification is to quickly identify newly added or misplaced tags from a large number of known tags. Considering a large-scale RFID system with millions of known tags whose IDs have already been stored in the back-end database previously, these known tags will participate in the identification of unknown tags, thus making it difficult to identify the unknown tags rapidly. The existing unknown tag identification protocols are divided into two categories: probabilistic protocols [21; 22; 23] and deterministic protocols [24; 25; 26; 27; 28]. The probabilistic protocols can perform unknown tag detection quickly with an expected accuracy. The state-of-the-art probabilistic protocol is the _collision seeking detection_ (CSD) protocol [23], which finds a collision seed to make many known tags collide in the last \(N\) slots with a frame size of \(f\), thus saving the detection time and ensuring the desired detection accuracy. The deterministic protocol can correctly identify all unknown tags in a batch. Reference [25]proposed a series of protocols to improve identification performance. The _basic unknown tag identification protocol_ (BUIP) separates known tags from unknown tags and deactivates them; the _single-pairing unknown tag identification protocol_ (SUIP) adopts a slot pairing method, and the _multi-pairing unknown tag identification protocol_ (MUP) adopts multiple reselection methods to resolve the problem of known tag collisions. Meanwhile, the _filtering-based unknown tag identification protocol_ (FUTI) and the _interactive filtering-based unknown tag identification protocol_ (IFUTI) were investigated in [27] to separate unknown tags from known tags and assign a status code to each singleton slot, thus reducing known-unknown collisions and identifying unknown tags at the bit level. Although the existing protocols can identify unknown tags, they do not have enough time efficiency and space efficiency in open RFID systems. This paper investigates the problem of unknown tag identification in open RFID systems and proposes a deterministic unknown tag identification protocol called the filter-based and parallel unknown tag identification (FPUI) protocol. Considering the drawbacks of the existing protocols, the proposed protocol formulates a solution that satisfies the requirements of efficiency and accuracy by: (1) taking less time and space to achieve unknown tag identification; (2) accurately collecting the information of unknown tags. To achieve these goals, the FPUI consists of two phases: the separation phase and the collection phase. In the first phase, the FPUI adopts an RSQF-based filter [29] to calculate the hash value for each known tag by \(H(\cdot)\) and divides the hash value into two parts: _quotient_ and _remainder_. The _remainders_ of tags with an identical _quotient_ are placed in consecutive slots from small to large, and this sequence of slots is called a _run_. Meanwhile, the fingerprint filter assigns different fingerprints to multiple known tags in the same _run_ to reconcile the collision slots and separate the known tags from unknown tags.