Analog On-Tag Hashing: Towards Selective Reading as Hash Primitives in Gen2 RFID Systems
Lei Yang Qiongzheng Lin Chunhui Duan Zhenlin An
cs.NI


(Technical Report)
 

      ^∗Department of Computing, The Hong Kong Polytechnic University
	^† School of Software, Tsinghua University
 
young, lin, hui, an@tagsys.org




Deployment of  billions of Commercial off-the-shelf (COTS) RFID tags has drawn much of the attention of the research community because of the performance gaps of current systems. In particular, hash-enabled protocol (HEP)  is one of the most thoroughly studied topics in the past decade.  HEPs are designed for a wide spectrum of notable applications (missing detection) without need to collect all tags. HEPs assume that each tag contains a hash function, such that a tag can select a random but predicable time slot to reply with a one-bit presence signal that shows its existence. However, the hash function has never been implemented in COTS tags in reality, which makes HEPs a 10-year untouchable mirage.  This work designs and implements a group of  analog on-tag hash primitives (called Tash) for COTS Gen2-compatible RFID systems,  which moves prior HEPs forward from theory to practice.  In particular, we design three types of hash primitives, namely, tash function, tash table function and tash operator. All of these hash primitives are implemented through selective reading, which is a fundamental and mandatory functionality specified in Gen2 protocol, without any hardware modification and fabrication. We further apply our hash primitives in two typical HEP applications (cardinality estimation and missing detection) to show the feasibility and effectiveness of Tash. Results from our prototype, which is  composed of one ImpinJ reader and 3,000 Alien tags, demonstrate that the new design lowers 60% of the communication overhead in the air. The tash operator can additionally introduce an overhead drop of 29.7%.





<ccs2012>
<concept>
<concept_id>10003033.10003106.10003112</concept_id>
<concept_desc>Networks Cyber-physical networks</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10010520.10010553</concept_id>
<concept_desc>Computer systems organization Embedded and cyber-physical systems</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>


[500]Networks Cyber-physical networks
[500]Computer systems organization Embedded and cyber-physical systems



Analog On-Tag Hashing: Towards Selective Reading as Hash Primitives in Gen2 RFID Systems
    Lei Yang^∗,  Qiongzheng Lin^∗, Chunhui Duan^∗^†,  Zhenlin An^∗ 
    December 30, 2023
========================================================================================







§ INTRODUCTION



RFID systems are increasingly used in everyday scenarios, which range from object tracking, indoor localization <cit.>, vibration sensing <cit.>, to medical-patient management, because of the extremely low cost of commercial RFID tags (as low as 5 cents per tag). 



Recent reports show that many industries like healthcare and retailing are moving towards deploying RFID systems for object tracking, asset monitoring, and emerging Internet of Things <cit.>.



 §.§ The State-of-the-Art

The Electronic Product Code global is an organization established  to  accomplish the worldwide adoption and standardization of EPC technology. It published the Gen2 air protocol <cit.> for RFID system in 2004. A Gen2 RFID system consists of a reader and many passive tags. The passive tags without batteries are  powered up purely by harvesting radio signals from readers.  This protocol has become the mainstream specification globally, and has been adopted as a major part of the ISO/IEC 18000-6 standard.




Embedding Gen2 tags into everyday objects to construct ubiquitous networks has been a long-standing vision. However, a major problem that challenges this vision is that the Gen2 RFID system is not efficient <cit.>. First, the RFID system utilizes  simple modulations (e.g., ON-OFF keying or BPSK) due to the lack of traditional transceiver <cit.>, which prevents tags from leveraging a suitable channel to transmit more bits per symbol and increase the bandwidth efficiency.  Second, tags cannot hear the transmissions of other tags. They merely reply on the reader to schedule their medium access with the Framed Slotted ALOHA protocol, which results in many  empty and collided slots. This condition also retards the inventory process. These two limitations force a reader to go through a  long inventory phase when it collects all the tags in the scene.





 §.§ Ten-Year Mirage of HEP


Motivated by the aforementioned performance gaps, the research community opened a new focus on HEP design approximately 10 years ago.  The key idea that underlies HEPs is that each tag selects a time slot according to the hash value of its  and a random seed. It then replies a one-bit presence signal rather than the entire  number in the selected slot. HEPs treat all tags as if they were a virtual sender, which outputs a gimped hash table  (a presence bitmap) when responding to a challenge (a random seed). Most importantly, HEPs assume the backend server and every tag share a hash function, and the resulting bitmap is random but predicable when the s and seeds are known.

Fig. <ref> shows a toy example with n=8 tags, each of which contains a unique  number presented in binary format (101010_2), to illustrate the HEP concept. The reader divides the time into d time slots (d=8.) and challenges these tags with the random seed r. Each tag selects the (h_d(,r))^th time slot to reply the one-bit signal, where h(·) is a common hash function (MD5, SHA-1) and h_d(·) = h(·) d. The reader can recognize two possible results for each time slot, namely, empty and non-empty[Some work assume the reader can recognize the signal collision, obtaining three results: empty, single and collision. ]. The reader abstracts the reply results into a bitmap (B=[0,1,1,0,1,1,1,0]), where each element  contains two possible values, that is, 0 and 1, that corresponds to empty and non-empty slots, respectively.  The upper layer then utilizes this returned bitmap to explore many notable  applications. We show the following two typical applications as examples to drive the key point:

∙ Cardinality estimation. Estimating the size of a given tag population is required in many applications, such as privacy sensitive systems and warehouse monitoring. Kodialam <cit.> presented a pioneer estimator. Given that tags select the time slots uniformly because of hashing, the expected number of `0's equals n_0=d (1-1/d)^n ≈ de^-n/d. Counting n_0 in an instance yields a “zero estimator”, n≈ -dln(n_0/d). For example, n=-8×ln(3/8)=7.8 in our toy example.

∙ Missing detection. Consider a major warehouse that stores thousands of apparel, shoes, pallets, and cases. How can a staff immediately determine if anything is missing?  Sheng and Li <cit.> conducted the early study on the fast detection of missing-tag events by using the presence bitmap. They assumed all s were known in a closed system. Given that hash results are predicable, the system can generate an intact bitmap at the backend. We can identify the missing tags in a probabilistic approach by comparing the intact and instanced bitmaps.  For example, if the second entry equals 0 (which is supposed to be 1), the the tag 101010_2 must be missing in our toy example.




HEPs are advantageous in terms of speed and privacy. HEPs are faster than all prior per-tag reading schemes for two reasons. First, collecting all the EPCs of the tags is time consuming  because of the aforementioned low-rate modulation, whereas one-bit presence signals of HEPs save approximately  96× of the time (the  length equals 96 bits in theory [Actual case in practice would be less than this estimate due to other extra jobs, such as setup time, query time, ]). Second, collisions  are considered as one of the major reasons that drag down the reading. On the contrary, HEPs tolerate and consider collisions as informative.  When privacy issues are considered, the tag's identification may be unacceptable in certain instances.  HEPs allow tags to send out non-identifiable information (one-bit signals).

HEPs are very promising. However, after 10 years of enthusiastic discussion about the opportunities that HEPs provide, the reality is beginning to settle: the functionality of hashing (hash function and hash table function) has never been implemented  in any Gen2 RFID tags and considered by any RFID standard. No hint shows that this function will be widely accepted in the near future.



 §.§ Why Not Support Hashing?


A large number of recent work have attempted to supplement hash functionality to RFID tags, which can be categorized into three groups. First group, like <cit.>, modifies the common hash functions to accommodate resource-constrained RFID tags. The second group <cit.> designs new lightweight and efficient hash functions dedicatedly for RFID tags. The third group seeks new design of RFID tags like WISP<cit.> and Moo <cit.>, which gives tags more powerful computing capabilities (hashing <cit.>). Unfortunately, as far as we know, none of these work has been really applied in COTS RFID systems yet.


Why is the hash function unfavored? A term called as Gate Equivalent (GE) is widely used to evaluate a hardware design with respect to its efficiency and availability. One GE is esquivalient to the area which is required by the two-input NAND gate with the lowest deriving strength of the corresponding technology.  A glance at Table. <ref> shows the available designs of hash functions for RFID tags require a significant number of GEs, which are completely unaffordable by current COTS tags. For example, the most compact hash functions requires thousands of GEs  (1,075 GEs for PRESENT-80), which  incur extremely high energy consumption and manufacture cost. Thus, relatively few RFID-oriented protocols that appeal to a hash function can be utilized. RFID was expected to be one of the most competitive automatic identification technologies  due to its many attractive advantages (simultaneous reading, NLOS, ) compared with others (barcode). However, this progress has been hindered for many years by the final obstacle that the industry is attempting to overcome (the price). The industry is extremely sensitive to the cost being doubled or tripled  by the hash, although HEPs actually introduce significant  outperformance.





 §.§ Our  Contributions


This work designs a group of  hash primitives, Tash,  which takes advantage of existing fundamental function of selective reading specified in Gen2 protocol, without any hardware modification and fabrication. Our design and implementation both strictly follow the Gen2 specification, so it can work in any Gen2-Compatible RFID system. These mimic (or analog) hash primitives act as we embedded real hash  circuits on tags[This work does not target at designing any analog circuit on readers or tags, but offers a mimic hash function acting as we  embed a hash circuit on each tag.], while we actually implement them in application layer. Specifically, we design the following three kinds of hash primitives to revive prior HEPs:

∙ We design a hash function (aka tash function)  over existing COTS Gen2 tags. The hash function outputs a hash value associated with the  of the tag and a random seed, as HEPs require.

∙ We design a hash table function (aka tash table function) over all tags in the scene. It can produce a  hash table (aka tash table), which is more informative than a bitmap, over the all tags in the scene. In particular, each entry indicates the exact number of tags hashed into this entry.

∙ Major prior HEPs require multiple acquisitions of bitmaps to meet an acceptable confidence. We design three tash operators (tash AND, OR and XOR) to perform entry-wise set operations over multiple tash tables on tag in the physical layer, which offers a one-stop acquisition solution.

Summary. It  has been considered that HEPs are hardly applied in practice because of the `impossible mission'  of implementing hash function on COTS Gen2 tags <cit.>. In this work, our main contribution lies in the practicality and usability, that is, enabling billions of deployed tags to benefit performance boost from prior well-studied HEPs, with our hash primitives.  To the best of our knowledge,  this is the first work to implement the hash functionality over COTS Gen2 tags.  Second, we provide an implementation of and show its feasibility  and efficiency in two typical usage scenarios.  Third, we investigate several leading RFID products in  market  including 18 types of tags and 10 types of readers, in terms of their compatibility with Gen2, and conduct an extensive evaluation on our prototype with COTS devices.














§ RELATED WORK



We review the related work from two aspects: the designs of hash functions and hash enabled protocols.

Design of hash function. Feldhofer and Rechberger <cit.> firstly point that current common hash functions (, , ), are not hardware friendly and unsuitable at all for RFID tags, which have very constrained computing ability.   Such difficulty has spurred considerable research <cit.>. We sketch the primary designs and their features in Table. <ref>. For example, Bogdanov <cit.> propose a hardware-optimized block cipher, PRESENT, designed with area and power constraints.  The follow-up work <cit.> presents three different architectures of PRESENT and highlights their availability for both active and passive smart devices. Their implementations reduce the number of GEs to 1,000 around. Another follow-up work <cit.> extends the design of PRESENT and gives 8 variants to fulfill different requirements, DM-PRESENT-80, DM-PRESENT-128, H-PRESENT-128,   The work <cit.> suggests to choose DES as hash function for RFID tags due to relatively low complexity, and presents a variant of DES, called asDESXL. Lim and Korkishko <cit.> present a 64-bit hash function with three key size options (64 bits, 96 bits and 128 bits),  which requires  about 3,500 and 4,100 GEs.  In summary, despite these optimized designs, majority are still presented in theory and  none of them are available for the COTS RFID tags. On contrary, our work explores hash function from another different aspect, that is, leveraging selective reading to mimic equivalent hash primitives.



 `-' means the algorithm is presented in theory and does not have  specific power consumption.

Design of hash enabled protocol. To drive our key point, we conduct a brief survey of previous related works. We list several key usage scenarios that we would like to support. Our objective is not to complete the list, but to motivate our design.
(1) Cardinality estimation. Dozens of estimators <cit.> have been proposed in the past decade. For example, Qian <cit.> proposed an estimation scheme called lottery frame. Shahzad and Liu <cit.> estimated the number based on the average run-length of ones in a bit string received using the FSA. In particular, they claimed that their protocol is compatible with Gen2 systems. However, their scheme still requires modifying the communication protocol, and thus, it fails to work with COTS Gen2 systems. By contrast, our prototype can operate in COTS Gen2 systems as demonstrated in this study. (2) Missing detection. The missing detection problem  was firstly mentioned in <cit.>. Thereafter,  many follow-up works <cit.> have started to study the issue of false positives resulting from the collided slots  by using multiple bitmaps. Additional  details regarding  this application are introduced in <ref>.
(3) Continuous reading. The traditional inventory approach starts from the beginning each time it interrogates all the tags, thereby making it highly time-inefficient. These works <cit.> have proposed continuous reading protocols that can incrementally collect tags in each step using the bitmap. For example, Sheng <cit.> aimed to preserve the tags collected in the previous round and collect only unknown tags. Xie <cit.> conducted an experimental study on mobile reader scanning. Liu <cit.> initially estimated the number of overlapping tags in two adjacent inventories and then performed an effective incremental inventory.
(4) Data mining. These works <cit.> discuss how to discover potential information online through bitmaps. For example,  Sheng <cit.> proposed to identify the popular RFID categories using the group testing technique.  Xie found histograms over tags through a small number of bitmaps<cit.>. Luo <cit.> determined whether the number of objects in each group was above or below a threshold. Liu <cit.> proposed a new online classification protocol for a large number of groups.
(5) Tag searching. These works<cit.> have studied the tag searching problem that aims to find wanted tags from a large number of tags using bitmaps in a  multiple-reader environment. Zheng <cit.> utilized bitmaps to aggregate a large volume of RFID tag information and to search the tags quickly.  Liu <cit.>  first used the testing slot technique to obtain the local search result by iteratively eliminating wanted tags that were absent from the interrogation region.
(6) Tag polling. <cit.> consider how to quickly obtain the sensing information from sensor-augmented tags. The system requires to assign a time slot to each tag using the presence bitmap. In summary, all the aforementioned HEP designs have allowed RFID research to develop considerably in the past decade.  All the work can be boosted by our hash primitives.
























§ OVERVIEW









Tash is a software framework that provides a group of fundamental hash primitives for HEPs.  This section presents its usage scope and formally defines our problem domain.



 §.§ Scope


Despite clear and certain specifications, the implementation of the Gen2 protocol still varies with readers and manufacturers because of firmware  bugs or compromises,  especially in early released reader devices, according to our compatibility report presented in  <ref>.  Here, we firmly claim
that our design and implementation strictly follow the specifications of the Gen2 and LLRP protocols  (refer to <ref>). The framework  works with any Gen2-compatible readers and tags. The  performance losses caused by  defects in devices are outside the scope of our discussion.  





 §.§ Definitions of Hash Primitives









Before delving into  details, we formally define the hash primitives that the HEPs require, from a high-level.



An l-bit tash function is actually a hash function f_l(t,r): 𝒯×ℛ→ 2^l, where 𝒯 and ℛ are the domains of  s of the tags and random seeds. 	


Tash function and tash value. As the above definition specifies, an l-bit tash function takes an  t and a random seed r as input and outputs an l-bit integer i, denoted  by:

    i=f_l(t,r)

We call l the dimension of tash function (l=0,1,2,…). The tash value i is an integer ∈ [0,2^l-1]. Similar to other common hash function, the tash function has three basic characteristics. First, the output changes significantly when the two parameters are altered.  Second, its output is uniformly distributed within the given range, and predicable if all inputs are known. Third, the hash values are accessible.






An l-bit tash table function can assign each tag t from a given set into the i^th entry of a hash table (aka tash table) with a random seed r, where i=f_l(t,r). Each entry of the tash table is the number of tags tashed into it.


Tash table function and tash table. Let B and ℱ_l denote a  tash table and a tash table function respectively. The tash table function takes a set of tags (T={t_1,t_2, …, t_n}) and a random number r as  input and  outputs a tash table B, denote by:

    B=ℱ_l(T,r)

where B[i]=|{t|f_l(t,r)=i}| (the number of tags tashed into the i^th entry) for ∀ t∈ T.  Let L=2^l, which is defined as the size of the tash table. The tash table function is the core function that HEPs expect.  HEPs consider the reader as well as all tags as a black box equipping with tash table function. When inputing a random seed, the box would output a tash table. HEPs then utilize such table to provide various services (missing detection or cardinality estimation.). It worths noting that superior to the bitmap employed in prior HEPs, our tash table is a perfect table that contains the exact number of tags tashed into each entry.  Clearly, the table is completely backward compatible with prior HEPs because it can be forcedly converted into a presence bitmap.



Tash operators. Most prior HEPs adopt probabilistic ways and their results are guaranteed with a given confidence level. To meet the level, they usually combine multiple bitmaps, which are acquired through multiple rounds and challenged by different seeds. We abstract such combination into three basic tash operators, namely, tash AND, OR and XOR. These operators can comprise other complex operations. Let B_1= ℱ_l(T, r_1) and B_2=ℱ_l(T, r_2) denote two tash tables acquired twice with two different seeds, r_1 and r_2.



The tash AND  (denoted by ⊕) of two tash tables is to obtain the intersection of  two corresponding entry sets. Formally,  B =B_1⊕ B_2, where B[i]=|{t|f_l (t,r_1)=i& f_l(t,r_2)=i}|.

The tash AND is aimed at obtaining the common intersection of corresponding entries from two tash tables. For example,  as shown in Fig. <ref>,  B_1[1] and B_2[1] count  {t_1,t_2} and {t_2} respectively. However, (B_1⊕ B_2)[1]=|{t_2}|=1, which counts t_2 only.



The tash OR (denoted by ||) of two tash tables is to merge two corresponding entry sets. Formally, B = B_1|| B_2, where B[i]=|{t | f_l(t,r_1) =i||f_l(t,r_2)=i }|.

The tash OR is aimed at obtaining the total number of tags mapped into the corresponding entries in two tash tables.  Note tash OR is not the same as the entry-wise sum, B_1 || B_2 ≠ B_1+B_2 because the tags twice mapped into a same entry are counted only once.  As shown in Fig. <ref>, (B_1||B_2)[5]=|{t_5,t_6,t_7}|=3 although B_1[5]+B_2[5]=5 because  t_6 and t_7 appear twice in the two tash tables.



The tash XOR (denoted by ⊗) is to remove the intersection of two corresponding entry sets from the first entry set. Formally, B = B_1 ⊗ B_2 such that B[i]=|{t| f_l(t,r_1)=i & f_l(t,r_2)≠ i}|.

The tash XOR is aimed at obtaining the total number of the set difference. As Fig. <ref> shows, B_1[5]=|{t_5,t_6,t_7}| and B_2[5]=|{t_6, t_7}|. Then (B_1 ⊗ B_2)[5]=|{t_5}|=1.






The above operators can be applied in a series of tash tables with the same dimension for a hybrid operation, B_1⊕ B_2 || B_3. Tash AND and OR  satisfy operational laws such as associative law and commutative law, B_1⊕ B_2 = B_2 ⊕ B_1.  The design of tash operators is one of the attractive features of the tash framework, and it has never been proposed before. More importantly, we design and implement these operators in the physical layer to provide one-stop acquisition solution.




 §.§ Solution Sketch


Tash is designed to reduce the overhead for air communications. It runs in the middle of the reader and upper application. The upper application passes a pair of arguments (r and l), or pairs of arguments (as well as operators) to .  On the basis of the arguments, generates one or more configuration files to manipulate the reader's reading. Finally, abstracts the reading results to a tash table, which is returned to the upper application.

The rest of the paper is structured as follows.  We firstly present the tash design in <ref>. We next demonstrate the usage of our hash primitives in two classic applications in <ref>. We then introduce the tash implementation using LLRP interfaces in <ref>. In <ref> and <ref>, we present the microbenchmark and the usage evaluation. Finally, we conclude in <ref> and present future directions.











§ TASH DESIGN



In this section, we introduce the background of selective reading in Gen2, and then present the technical details of our designs.






 §.§ Background of Gen2 Protocol


The Gen2 standard defines air communication between readers and tags.  On the basis of <cit.>, we introduce its four central functions we will employ:

F1: Memory Model.
Gen2 specifies a simple tag memory model (pages 44 ∼ 46 of <cit.>). Each tag contains four types of non-volatile memory blocks (called memory banks): (1)  is reserved for password associated with the tag. (2)  stores the  number. (3)  stores the  that specifies the unchangeable tag and vendor specific information. (4)  is a customized storage that contains user-defined data.  





F2: Selective Reading.
Gen2 specifies that each inventory must be started with  command (pages 72∼73 of <cit.>). The reader can use this command to choose a subset of tags that will participate in the upcoming inventory round. In particular, each tag maintains a flag variable . The reader can use the  command to turn the  flags of tags into  (true) or  (false).  The  command comprises six mandatory fields and one optional field apart from the constant cmd code (1010_2), as shown in Fig. <ref>. The following fields are presented for this study.







∙ . This field allows a reader to change   flags or the inventoried flags of the tags. The inventoried flags are used when multiple readers are present. Such scenario is irrelevant to our requirements. Thus, we aim to change  flags only by setting .

∙ . This field specifies an action that will be will performed by the tags. Table. <ref> lists eight action codes to which the tag makes different responses. For example,  the matching or not-matching tags assert or deassert their  flags  when . We  leverage this useful feature to design tash operators.



∙ , ,  and .  These four fields are combined to compose a bitmask. The bitmask indicates which tags are matched or not-matched for an . The  contains a variable length binary string that should match the content of a specific position in the memory of a tag. The  field defines the length of the  field in bits. The  field can be compared with one of the four types of memory banks in a tag. The  field specifies which memory bank the  will be compared with. The  field specifies the starting position in the memory bank where the  will be compared with. For example, if we use a tuple (b,p,l, m) to denote the four fields, then only the tags with data starting at the p^th bit with a length of l bits in the b^th memory bank that is equal to m are matched.






To visually understand the selective reading, we show an example in Fig. <ref> in which 4 out of 7 tags are selected to participate in the incoming inventory. Complex and multiple subsets of tags can be facilitated by issuing a group of  commands to choose a subset of tags before an inventory round starts. For example, we can issue two  commands: one  for division and another for one-bit reply. Note the  enabled  command  must be the last one if multiple selection commands are issued <cit.>.


F3: Truncated Reply. Gen2 allows tags to reply a truncated reply (replying a part of  ) through a special  command with an enabled  field, making a one-bit presence signal possible. When  is enabled (set to 1), then the corresponding bitmask is not used for the division of tags, but lets tags reply with a portion of their s following the pattern specified by the bitmask. Note that when  is enabled, the  must be set to the  bank (=1) and such  command must be the last one.


F4: Query Model.
Followed by a group of  commands,   command (see page 76∼80 of <cit.>.) starts a new inventory round over a subset of tags, chosen by the previous  commands. There are 7 fields in the  command. We only focus on  field, which is most tightly relevant to the selective reading. As mentioned above, the  command has divided the tags into two opposite subsets with asserted and deasserted  respectively. The  field specifies which subset will reply in the current inventory round. If , the tags with asserted  reply. If , the tags with deasserted  reply. We choose the tags with asserted  by default.



 §.§ Design of the Tash Function


An l-bit tash function is essentially a hash function that is indispensable to HEPs. We design the tash function while following the three principles outlined as follows. The first principle requires that the tash result must be dependent on the input  and the seed. Moreover, it must be predictable as long as all the input parameters are known. The second principle requires the output values to be random, uniformly distributed in [0, 2^l-1]. Even a one bit difference in the input will result in a completely different outcome. The third principle requires a method that can access the tash result of a tag directly or indirectly.


We have constructed the tash function as follows by applying the aforementioned principles:  given a tag with an  of t, we firstly calculate the hash value of the  offline, using a common perfect hash function like 128-bit  or . Let h(t) denote the calculated hash value. We then write  h(t) into the tag's user-defined memory bank of the tag, , for later use.


	The l-bit tash value of  tag t challenged by  seed r is defined as the value of the sub-bitstring starting from the r^th bit and ending at the (r+l-1)^th bit in the  of the tag.


Evidently, f_l(t,r) is actually a portion of h(t), and thus,  the parameter r∈ [0,ℒ-1] and l∈ [1, ℒ-r], where ℒ is the length of the hash value (128 bits).  Fig. <ref> shows an example wherein the  and  of the tag store its  t and the hash value h(t), respectively. When r=5 and l=4 are inputted,  the tash value that this tag outputs is 1010_2, which is the sub-bitstring of h(t) starting from the 5^th bit and ending at the 8^th bit in , f_4(t,5)=1010_2. 

Our design does not require a tag to equip a real hash function or the engagement of its chip. It clearly applies the preceding principles. First,  f_l(t,r) is evidently repeatable, predicable and dependent on the inputs. Second, the randomness of f_l(t,r) is derived from h(t) and r, which are supposed to have a good randomness quality. Third,  we have two ways to access the tash value. We can use the memory  command to access   of a tag directly, or use the selective reading function to access the tash value indirectly (discussed later).




Discussion:  A few points are worth-noting about the design:

∙ As the tash value is a portion of the hash value, if two random numbers may cover a common sub-string. For example, if r_1 and r_2 differ by 1, there exist l-1 same bits with 50% of probability that two hash values are same,  although such case occurs with a small probability, ≈ 127/(128× 128)× 0.5=0.0039. If some upper applications require extremely strong independence, we should generate the second random number r_2 meeting the condition of r_2<r_1-l and r_2≥ r+l, so as to avoid the common coverage and potential relevance.

∙ The design of tash function involves the , the user-defined storage. We can use  command to store any data into this memory bank. Our compatibility report (shown in <ref>) suggests that almost all types of tags support both  and  command except one read-only type (ImpinJ Monza R6). Our approach is generally practicable.


∙ Our design targets at enabling COTS tags, billions of which have been deployed in recent years,  to obtain performance advantages from well-studied hash based protocols, instead of enhancing their security or privacy preservation. Our design still follows the current COTS tag's security mechanism, password protected memory access.

∙ Tash function also offers a good feature that the computation is one way and irreversible, the output reveals nothing about the input. This feature is inherited from the hash function. It may be useful for privacy protection in practice. However, this topic is beyond the scope of this work.




 §.§ Design of the Tash Table Function

The tash table function treats a reader and multiple tags as if they were a single virtual node, outputting a tash table.  For simplicity, we use

    S ( a_, b^, p_, l^, m_, u^)

to denote a selection command () with an  (a), a  (b), a  (p), a  (l), a  (m) and a  (u). The command aims to select a subset of  tags with a sub-bitstring that starts from the p^th bit and ends at the (p+l-1)^th bit in the b^th memory bank that is equal to m. These selected tags are requested to take an action a. The action codes are shown in Table. <ref>. In particular, if u=1, then each tag will reply with a truncated  number.

The tash table function  is designed as follows.  An l-bit table B consists of a total of  2^l entries, each of which contains the amount of tags mapped into it. In particular, the index number of each entry, which ranges from 0 to 2^l-1, is actually the tash values of the tags mapped into this entry, B[i]=|{t|f_l(t,r)=i}|. When constructing the i^th entry, the reader performs selective reading with two selection commands as follows:

    S_1(0, 3, r, l, i, 0)  and  S_(1, 1, 1, 1, 1, 1)

Command S_1 selects a subset of  tags with a sub-bitstring that starts from the r^th bit and ends at the (r+l-1)^th bit in the  that is equal to i.  Notably, the involved sub-bitstring is the tash value of a tag, f_l(t,r), which refers to Definition. <ref>. Consequently, only  tags with tash values equal to i are selected to participate in the incoming inventory, counted by the i^th entry.  The second command S_ enables the selected tags to reply with the first bit of their  numbers for the one-bit signals. We call such inventory round as an entry-inventory. In this manner, we can obtain the whole tash table by launching 2^l entry-inventories.




To visually understand the procedure, we illustrate an example in Fig. <ref>, where r=5 and l=2. The tash table contains 2^2 entries; hence,  four entry-inventories are launched. Their selection commands are defined as follows:

    182 S_1(0, 3, 5, 2, 0, 0)  and  S_(1, 1, 1, 1, 1, 1)
    183S_1(0, 3, 5, 2, 1, 0)  and  S_(1, 1, 1, 1, 1, 1)
    184S_1(0, 3, 5, 2, 2, 0)  and  S_(1, 1, 1, 1, 1, 1)
    185S_1(0, 3, 5, 2, 3, 0)  and  S_(1, 1, 1, 1, 1, 1)

For the third entry-inventory, the  field is set to 2 because the index of the third entry is 2.  Four tags (t_5, t_6, t_7 and t_8) are selected to join in this entry-inventory. Thus,  ℱ_2(T,5)[2]=4.

For a tash table, note that (1) the sum of all its entries is equal to the total number of tags, and (2) it allows an application to selectively construct the entries of a tash table becaues each entry-inventory are independent of each other and completely controllable. For example, we can skip the inventories of these entries that are predicted to be empty.



 §.§ Design of  Tash Operators




A tash operator is connected to two tash tables, which have the same dimensions but are constructed using two different seeds. When two seeds, r_1 and r_2, are given,  we can obtain two l-bit tash tables: B_1=ℱ_l(T,r_1) and B_2=ℱ_l(T,r_2). Our objective is to obtain a final tash table B by performing one of the subsequent tash operators on B_1 and B_2.

Tash AND. If B=B_1⊕ B_2, then each entry of B denotes  the number of tags that are concurrently mapped into the corresponding entries of  B_1 and B_2. The selection commands for the i^th entry-inventory are defined as follows:

    S_1(0,3,r_1,l,i,0), S_2(2,3,r_2,l,i,0), S_

From the action codes shown in Table. <ref>, the purpose of S_1 with action code of 0  is to select tags ∈ B_1[i] and deselect tags ∉ B_1[i]. S_2 with action code of 2  deselects tags  ∉ B_2[i] and results in tags ∈ B_2[i]  doing nothing.  After S_1 is received, each tag exhibits one of two states, selected or deselected. Then, S_2 will make the selected tags remain in their selected states if they match its condition (doing nothing); otherwise, it changes their states to the deselected states (selected → deselected), which is equivalent to removing tags ∉ B_2[i] from tags ∈ B_1[i]. Meanwhile, the tags deselected by S_1 remain in their states regardless of whether they match (do nothing) or not match (deselected → deselected) the condition of S_2. Finally, S_ is reserved for the one-bit presence signal.

Tash OR. If B = B_1 || B_2, then each entry of B is the number of tags that mapped into the corresponding entry of either B_1 or B_2. The selection commands for the i^th entry-inventory are defined as follows:

    S_1(0,3,r_1,l,i,0), S_1(1,3,r_2,l,i,0),S_

Similarly,  S_1 selects tags ∈ B_1[i] and deselect tags ∉ B_1[i].  S_2 with action code of 1 (see Table. <ref>) allows tags ∈ B_2[i] to be selected as well, but tags ∉ B_2[i] remain in their states (do nothing), some of  these tags may have been selected by S_1. The process is equivalent to holding the tags selected by S_1 and incrementally  adding the new tags selected by S_2.

Tash XOR. If B = B_1 ⊗ B_2, then each entry of B is the number of tags that are mapped into the corresponding entry of B_1 but not into the entry of B_2. The selection commands for the i^th entry-inventory are defined as follows:

    S_1(0,3,r_1,l,i,0), S_2(5,3,r_2,l,i,0),S_

Similarly,  S_2 allows tags ∈ B_2[i] to be deselected (removed from tags ∈ B_1[i]) and tags ∉ B_2[i] to do nothing. This process is equivalent to removing tags ∈ B_2[i] from tags ∈ B_1[i].









Tash hybrid. The aforementioned  three operators can be further applied to a hybrid operation. When k seeds (r_1,⋯, r_k) are given, we can obtain k tash tables. The selection commands for the i^th entry-inventory can be designed as follows:

    S_1(0,3,r_1,l, i,0), S_2(,3,r_2,l, i,0),
          ⋯, S_k(,3,r_k,l, i,0),S_

where  represents the  code, which is set to 2, 1 and 5 for tash AND, OR and XOR, respectively. The action code of the first command is always set to 0.  For example, the selection commands in the i^th entry-inventory for ℱ_l(T, r_1) ⊕ℱ_l(T, r_2)  || ℱ_l(T,r_3) ⊗ℱ_l(T,r_4) are given by:

    S_1(0,3,r_1,l, i,0), S_2(2,3,r_2, l, i,0), 
          S_3(1,3,r_3,l, i,0), S_4(5,3,r_4, l, i,0),S_

We leverage the action of a selection command to perform an operation in the physical layer before an entry-inventory starts, therefore, we introduce minimal additional communication overhead, broadcasting multiple  commands. Compared with the multiple acquisitions of bitmaps used by prior HEPs, our solution provides a one-stop solution that can significantly reduce the total overhead in such situation.




 §.§ Discussion




























Comparison with bitmap. A tash table evidently takes a considerably longer time to obtain than a bitmap because a bitmap requires only one round of inventory, whereas a tash table requires multiple rounds. The additional time consumption is the trade-off for practicality because the reply of a COTS tag at the slot level is out of control. Nevertheless, this additional cost brings an additional benefit, a tash table has the exact number of tags mapped onto its each entry, which cannot be suggested by a bitmap. Moreover, a one-stop operator service can save more time.

Embedded pseudo-random function. Qian <cit.> and Shahzad <cit.> proposed a similar concept of utilizing a pre-stored random bit-string to construct a lightweight pseudo-random function. These studies have inspired our work.  However, their main objective of these previous researchers is to accelerate the calculation of a random number, which still requires the engagement  with the chip of a tag, and thus,  has never been implemented in practice. In the present work, we do not require additional efforts on changing the logics of  a tag chip and we associate this concept with the function of selective reading, moving the main task from a tag to a reader. Our design not only preserves the good features of the hash function but also gives a practical solution. This process has never been performed before.

Channel error. Channel error is one of the most notorious problems of HEPs because pure one-bit signal transmission is vulnerable to ambient interference. Thus, an additional error control mechanism is expected to be applied to HEPs. In the Gen2 protocol, the CRC8 code is automatically appended to the data transmitted between a reader and a tag for error detection, even when one bit of EPC is transmitted. The corrupt data will be retransmitted. Therefore, we should not be concerned with channel error.















§ TASH USAGE



This section revisits two classic problems of HEPs for usage study. We propose two practical solutions that use tash primitives for these problems. Note that in spite of two demonstration presented in this section, our tash primitives especially the tash table can serve any kind of HEPs. 



 §.§ Usage I: Cardinality Estimation


Cardinality estimation aims to estimate the total number of tags by using one-bit presence signals that are received without collecting each individual tag. The problem  is formally defined as follows:





When a tag population of an unknown size n,  a tolerance of β∈ (0,1), and a required confidence level of α∈(0,1) is given, how can the number of tags n be estimated such that (|n-n|≤β n)≥α?



A naive method would be to add all the entries of a tash table together or let all tags reply at the first entry.  Since each tag participates in one and only one entry-inventory,  the final number is exactly equal to n.  Keep in mind that our each entry corresponds to a complete round inventory. The naive method is equivalent to collecting them all, which is extremely time-consuming. We subsequently provide a reliable solution in a probabilistic way.

Proposed Estimator. We leverage the number of tags mapped into the first entry of a tash table to estimate n. Let X be the random variable to indicate the value of the first entry of a tash table. Since n tags are randomly and uniformly assigned into 2^l entires, we have

    (X=m) = nmp^m (1-p)^n-m

where p=1/2^l. Evidently, variable X follows a standard Binomial distribution with the parameters n and p, X∼ B(n,p). Therefore the expected value μ=np and variance δ=np(1-p). By equating the expected value and an instanced value m, our estimator n is given by:

    n= m/p = m 2^l

The estimator only requires the first entry of the hash table, so it skips inventories of other entries. We must choose an appropriate l to ensure the estimation error within the given tolerance level β with a confidence of greater than α.



Analysis. For the sake of simplicity, we use a Gaussian model to approximate the above distribution due to the central limit theory. Let the random variable Y=(X-μ)/δ∼𝒩(0,1).  We can always find a constant c, which satisfies

    α = (-c≤ Y ≤ c) = erf(c/√(2))

where erf is the Gaussian error function. Since we require
@size9@̌mathfonts

    (|n-n|≤β n) = ((1-β)n≤n≤(1+β)n)
          =((1-β)n≤m/p≤ (1+β)n))
          =((1-β)np-μ/δ≤m-μ/δ≤(1+β)np-μ/δ)
          ≥α = (-c ≤ Y ≤  c)

, we can find a constant c by subjecting to the below inequality:
@size9@̌mathfonts

    c    ≤   max{(1+β)np-μ/δ, -(1-β)np-μ/δ}
       =   (1+β)np-μ/δ = β/1-p

By substituting p=1/2^l into the above inequality, we obtain

    l≤log_2 c/c-β

where c=√(2)·erf^-1(α). Therefore, we can obtain the following theorem.


  
   The optimal dimension of the tash table is equal  to ⌈log_2 √(2)·erf^-1(α)/√(2)·erf^-1(α)-β⌉, which results in an estimation error ≤β with a probability of at least α.







 §.§ Usage II: Missing Tag Detection




The purpose of missing tag detection is to quickly find out the missing tags without collecting all the tags in the scene. Such detection is very useful, especially when  thousands of tags are present. We formally define the problem of detecting missing tags in Problem <ref>. We assume that the s of all the tags in a closed system are  stored in a database and known in advance. This assumption is reasonable and necessary, because it is impossible for us to tell that a tag is missing without any prior knowledge of its existence.



How to quickly identify m missing out of n tags with a false positive rate of γ at most?


Proposed detector. The underlying idea is to compare two tash tables B and B.  B is an intact tash table  created by tashing all the known s which are stored in the database, while B is an instance tash table obtained from the tags in the scene. We can detect the missing tags through comparing the difference between B and B. If the residual table B-B (entry-wise subtraction) equals 0,   no missing tag event happens. Otherwise, the tags mapped into the non-zero entries of the residual table are missing.


 Fig. <ref> illustrates an example in which three tags, t_1, t_2 and t_3, are mapped into the intact tash table B. B is an instance table where tag t_2 is missing, and thus B[4]=1. Consequently, (B-B)[4]=1, we can definitely infer that one tag is missing. However,  it is impossible for us to tell which tag is missing because t_2 and t_3 are simultaneously mapped into the fourth entry.

Inspired by the Bloom filter<cit.>, we perform k tashings to identify the missing tags as follows:

    B = ℱ_l(T, r_1) || … || ℱ_l(T,r_k)

The final B after tash ORs is considered to use k independent hash functions (induced by k random seeds) to map each tag into B for k times, as shown in Fig. <ref>.  The residual table of B-B is therefore viewed as a Bloom filter which represents the missing tags. Thereafter,  to answer a query of whether a tag t is missing,  we check whether all entries set by f_l(t,r_1), ⋯ and f_l(t,r_k) in the residual table have a value of  non-zero. If the answer is yes, then tag t is the missing one. Otherwise, it is not the missing tag. Fig. <ref> illustrates an example in which each tag is tashed twice. The missing tag t_2 can be identified because both the 2^rd and the 4^th entry in the residual table  have value of  non-zero.   Despite multiple tashings,  the query may yield a false positive, where it suggests a tag is missing even though it is not.





Analysis. To lower the rate of false positive rate, it is necessary to answer two questions.

(1) How many tash functions do we need? Given the table dimension l, we expect to optimize the number of tash functions. There are two competing forces: using more tash functions gives us more chance to find a zero bit for a missing tag, but using fewer tash functions increases the fraction of zero bits in the table.  After m missing tags are tashed into the table, the probability that a specific bit is still 0 is (1-1/L)^km≈ e^-km/L where L=2^l. Correspondingly, the probability of a false positive p is given by

    p = (1-e^-km/L)^k

Namely,  a missing tag falls into k non-zero entries.  Lemma. <ref> suggests that the optimal number of tash functions is achieved when k=ln 2 · (L/m).

	
	The false positive rate is minimized when p=(1/2)^k or equivalently k=ln 2 · (L/m).


Please refer to <cit.> for the proof.




(2) How large tash table is necessary to represent all m missing tags?















Recall that the false positive rate achieves minimum when p=(1/2)^k. Let p≤γ. After some algebraic manipulation, we find

    L≥mlog_2 (1/γ)/ln2 = mlog_2 e ·log_2(1/γ) = 1.44m log_2(1/γ)













Finally, putting the above conclusions together, we have the subsequent theorem.


Setting the table dimension to ⌈log_2(1.44m log_2 (1/γ)) ⌉ and using ⌈ln 2 · (2^l/m) ⌉ random seeds allow the false positive rate of identifying m missing tags lower than a given tolerance γ.









































§ TASH IMPLEMENTATION



Our implementation involves two kinds of protocols: UHF Gen2 air interface protocol (Gen2) and Low Level Reader Protocol (LLRP). As shown in Fig. <ref>,  Gen2 protocol defines the physical and logical interaction between readers and passive tags, while LLRP allows a client computer to control a reader.  Each client computer connects one ore more RFID readers via Ethernet cables.  LLRP is the driver program (or driver protocol) for  Gen2 readers. We leverage LLRP to manipulate a reader to broadcast Gen2 commands that we need.  Notice that we do not need particularly implement Gen2 protocol, which has been implemented in the COTS RFID devices that we are using.  Specifically, LLRP specifies two types of operations: reader operation (RO) and access operation (AO). Both operations are represented in  XML document form and transported to a reader through TCP/IP.

Reader operation. RO defines the inventory parameters specified in the Gen2 protocol, such as bitmask, antenna power, and frequency. Fig. <ref> shows a simplified instance of an .  An  is composed of at least one . Each  is used for an antenna setting. An  consists of more than one s. The filter functions as a bitmask. We can set multiple selection commands by adding multiple s.



Access operation. AO defines the access parameters for writing or reading data  to and from a tag.  We leverage the   inside an  to write the hash value of the  into a user-defined memory bank. As the s are highly related to the products the tags attached, the writing of hash values should be accomplished by the product manufactures or administrators.  There is almost no overhead to write data into  since it is allowed to write a batch of tags simultaneously using  commands specified in one , without physically changing tags' positions.


Tash framework. Our framework is developed by using Java language and the LLRP Toolkit<cit.>, which is an open-source library for handling  and .  Fig. <ref> shows the primary interfaces provided by the tash framework. The class  makes the first selection through its construction method and allows the calls of three operators to be chained together in a single statement.
The method  converts a  object or  a chain of   objects into an . The entry-inventories are physically executed in the connected reader when the method  is invoked.  This method allows users to make selective entry-inventories by passing an index array. For example, the operation ℱ_l(T, r_1) ⊕ℱ_l(T, r_2)  || ℱ_l(T,r_3) ⊗ℱ_l(T,r_4) can be coded in a manner similar to that shown at the bottom of Fig. <ref>.



















§ MICROBENCHMARK



We start with a few experiments that provide insight to our hash primitives.



 §.§ Experimental Setup



We evaluate the framework using COTS UHF readers and tags. We use a total of 3 models of ImpinJ readers (R220, R420 and R680), each of which is connected to a 900MHz and 8dB gain directional antenna.  In order to better understand the feasibility and effectiveness of in practice, we test a total of 3,000 COTS tags with different models. We divide these tags into 10 groups of 300 tags each. The tags of each group are densely attached to a plastic board which is placed in front of a reader antenna. As shown in Fig. <ref>, three hundreds is the maximum number of tags that can be covered by one directional antenna in our laboratory. We store the 3,000  numbers in our database as the ground truth.  The 128-bit MD5 is employed as the common hash function to generate the hash values of s. The experiments with the same settings are repeated across the 10 groups, and the average result is reported.






 §.§ Compatibility Investigation



First, we investigate the compatibility of Gen2 across 10 different  types of readers and 18 different types of  tags in terms of  the functions or commands that requires. The readers and tags may come from different manufacturers but work together in practice. These investigated products  are all publicly claimed to be completely Gen2-compatible.

Reader compatibility. We investigate the R220, R420, and R680 models from ImpinJ<cit.>, the Mercury6, Sargas  and M6e models from ThingMagic<cit.>, as well as the ALR-F800, 9900+, 9680 and 9650 models from Alien<cit.>. We perform the investigation through real tests for the first three models of readers (the ImpinJ series), and investigate the other readers through their data sheets or manuals (because we are limited by the lack of hardware). The Gen2-compatibility of readers is briefly summarized in Table. <ref>. Consequently, we have the subsequent findings. (1) All the readers do support  command, which Tash uses for writing or reading hash values of  numbers. (2) All the readers do support the  command, which Tash uses for the selective reading. (3) However, our practical tests suggest that none model of the ImpinJ series supports the   command, which Tash uses to hear the one-bit presence signal. The serviceability  of other readers is not clearly indicated in the manuals of those readers.  (4) The Gen2 protocol does not specify how many s and s  that a reader should support. Our practical tests suggest that the ImpinJ series supports 4 s and 16 s, which means that we can only use a maximum of four tash operators each time.



Tag compatibility.  We investigate 9 chip models from ImpinJ Monza series and 9 additional models from Alien ALN series. The majority of tags on the market contain these 18 models of chips and customized antennas. Table. <ref> summarizes the result of our investigation, from which we have the subsequent findings. (1) Tags reserve 96∼ 480 bits of memory for storing  numbers, among which the size of 96 bits has become the de facto standard.  (2) requires  to store the hash values. The results of the investigation show that almost all tags allow to write to and read from the third memory bank, with an exception of ImpinJ Monza R6, which does not have the user-defined memory. The size of the third memory bank fluctuates around 32∼ 512 bits. The de facto standard has become 128 bits. (4) All tags are claimed to support the  command according to their public data sheets. However, we have no idea about their real serviceability   due to the lack of -supportable reader available for practical tests. In our future work, we plan to utilize USRP for further tests.

Summary. Despite positive and public claims, our investigation shows that current COTS RFID devices, regardless of readers or tags and models, have some defects in their compatibility with Gen2, especially with regard to  .  The reason, we may infer, is that these commands are seldom used in practice and therefore never receive attention from manufacturers. The partial compatibility of such devices cannot fully achieve the performance brings. Even so, we are obliged to make the claim, again, that our design strictly follows the Gen2 protocol. We hope this work can encourage manufacturers to upgrade their products (reader firmware) to achieve full compatibility.





























































 §.§ Tash Function









Second, we evaluate the tash function with respect to the randomness and the accessibility.




Randomness. Randomness is the most important metric for a hash function. It requires that the outputs of a hash function must be uniformly distributed.  To validate the randomness of the tash function, we collect 99,886 real  numbers from our partner (an international logistics company), which introduced RFID technology for sorting tasks five years ago. Each  number has a length of 96 bits and encodes the basic information about the package, such as sources, destinations, serial numbers, and so on. We employ the 128-bit MD5 to create the hash values of these s. As the minimum size of the  is 32 bits (see Table. <ref>), we choose to use only the first 32 bits for our tests. We traverse r and l from 0∼31 and 1∼ 32-r respectively. For each pair of r and l, we obtain 99,886 tash values over all the s. Across these tash values, we further conduct the following two analysis: (1) We merge 100 tash values, which are randomly selected from the above results, into a long bit string. We then calculate the percents of `0' and `1' emerged in that bit string. This operation is repeated for 100 times. Finally, totally 100 pairs of percents are obtained. Their CDFs are plotted in  Fig. <ref>. Ideally, each bit has a equal probability of 0.5 to be zero or one if a hash function makes a good randomicity. From the figure, we can figure out that the percents distributed between 0.4 and 0.6. In particular,  percents of `0' and `1' have means of 0.49 and 0.50 with standard deviations of 0.043 and 0.044 respectively.  (2)  We shuffle these values into 100 groups, and employ the χ^2-test with a significance level of 0.05 to test each group's goodness-of-fits of the uniform distribution (passed or failed). Then, we finally calculate the pass rate for a pair of setting. In this manner, we totally obtain 496 pass rates. More than 60% of the pass rates are over than 0.95. In particular, three sets of the results with r=16, 20 and 26 and a variable l, are selected to show in Fig. <ref>. We find that 90% of the pass rates exceed 0.95 for the three cases, and their median pass rates are around 0.97. Thus, the two above statistical results suggest that our tash function has a very good quality of randomness.









Accessibility. Accessibility  refers to the ability to get access to a tash value from a tag. As aforementioned, we have two ways to acquire the tash values. The first way is to use the  command. The second way is to indirectly access a tash value through a selective reading. We choose the second method since it is the basis of our design. Specifically, we perform a selective reading to determine whether the tags are collected as expected, when given random inputs and a possible tash value. We intensively and continuously perform such readings across the 10× 300 tags using three 4-port ImpinJ readers for three rounds of 24 hours in a relatively isolated environment (an empty room without disturbance). Surprisingly, we find all the reading results faithfully conform to our benchmarks without any exceptions. This shows that the selective reading is well supported by the manufactures and is both stable and reliable.





 §.§ Tash Table Function






Third, we evaluate the performance of the tash table function in terms of its balance and gathering speed.

Balance. A good hash table function will equally assign each key to a bucket. We expect the output tash table to be as balanced as possible.  To show this feature, we generate 100 different 4-bit tash tables (each includes 16 entries) across 300 tags using 100 different random seeds. If the tash table is well balanced, the expected number of each entry should be very close to 300/16=18.7. Fig. <ref> shows the mean number of tags in each entry as well as their standard deviations. The average number across 16 entries equals 18.75, which is very close to the expected  theoretical value. The average standard deviation equals 0.44. Thus, the good randomness quality of tash functions results in output tash tables being well balanced.







Gathering speed. We then consider the time consumption of gathering a tash table. Fixing the random seed, we vary the table dimension l from 0 to 6. We then measure the  time taken on gathering a tash table with the deployed 300 tags.  Fig. <ref> shows the resulting time as a function of the table dimension. From the immediately above-mentioned  figure,  we can observe the subsequent findings.  (1)  When l=0 without truncating reply, the result is equivalent to collecting 300 complete s of all the tags. Such time consumption (4,524ms) is viewed as our baseline.  (2) By contrast, when l>0 without truncating a reply, the collection amounts to dividing all the tags into 2^l groups “equally” and then collecting each group independently.  In this manner, when l≤ 4, such “divide and conquer” approach is better than “one time deal”, a drop in overhead of about 10%. The Gen2 reader uses a Q-adaptive algorithm for the anti-collision. This algorithm is able to adaptively learn the best frame length from the collision history. Due to the division,  a smaller number of tags can make reader's learning relatively quicker and improve the overall performance.  (3) However, when l>4, the performance of “divide and conquer” approach starts to deteriorate. The ImpinJ reader  supports 16 s at most (see Table. <ref>). We have to re-send another  for the remaining selective readings when the number of entry-inventory is above 16 (l>4), which introduces additional time consumption. (4) We then consider the case where the reply is truncated to a one-bit presence signal as assumed by HEPs. Due to the defects of ImpinJ readers in the implementation of the  command, we cannot measure the actual time spent on collecting truncated s. We can only utilize the least-square algorithm to estimate the transmission  time for a one-bit presence signal. Our fitting results show that truncating reply would introduce about 60% drop of the overhead at least.



 §.§ Tash Operators




Finally, we investigate the performance of tash operators.  Superior to existing HEPs, these operators allow us to perform set operations on-tag and conduct a one-stop inventory. In particular, we show the performance of OR as a representative across 300 tags. The tests for other operators are similar and omitted due to the space limitation. In the experiments, we fix the two random seeds but change the dimension of tash table. Fig. <ref> shows the results of three cases. In Case 1, we independently produce 2 tash tables without truncating a reply and conduct the OR in the application layer.  In Case 2 and Case 3, we conduct on-tag OR function as provides without and with truncating a reply respectively. Consequently, when the dimension equals 2, Case 1 takes 6,511ms on collecting two tables. On the contrary,  the amount of time taken is reduced to 4,578ms (29.7% drop) if we perform an on-tag OR function even without truncation (Case 2).  Ideally, the amount of time taken could be further reduced to 50.97ms by using a truncating reply (Case 3), which offers a staggering drop in time usage by 99.22%. Our experiments relate only to the amount of time spent on ORing two tables. It may be predicted that  much more outperformance will be gained if multiple tables are involved. The tash operators that we design in this work have never been proposed before.






§ USAGE EVALUATION




We then use our prototype to demonstrate the benefits and potentials of in two typical applications.



 §.§ Usage I: Cardinality Estimation


We evaluate our estimation scheme through the testbed as well as large-scale simulations.



Testbed based. Our scheme only uses the first entry of the tash table for the estimation, thereby we only need one entry-inventory. Fig. <ref> shows the CDF of estimation results across 300 tags. We define the error rate as |n-n|/n where n is the estimated number.  As a result, 90% of the estimations have an error rate less than 0.1 and a median of 0.04 when setting the dimension l=1. In this case, almost half tags follow into the first entry so the rate could be pretty high, at the price of longer inventory time. As l increases, the error rate also increases because less samples are acquired for the estimation. These experiments show the feasibility of using tash table for cardinality estimation.

Simulation based. We then perform the evaluation through large-scale simulations for two reasons: (1) ensuring its scalability when meeting a huge number of tags. (2) making comparisons with prior work, which are all simulation-based. We numerically simulate in Matlab using tash scheme as well as other five prior RFID estimation schemes: UPE<cit.>, EZB<cit.>, FNEB<cit.>, MLE<cit.>, ART<cit.>. We implement these schemes by referring to the RFID estimation tool developed by Shahzad<cit.>. Fig. <ref> shows the time cost with a varying n given α=0.9 and β=0.08. We observe that our scheme is 5× faster than the others on average when n<1000. Thus our scheme is suitable for the estimation with a small number of tags. When n>1000, the performance of our scheme starts to vibrate between ART and MLE, due to two reasons. First, our scheme is not collision-free so that more efforts are required to deal with the collisions incurred by more tags. Second,  the size of a tash table can only increase in the power of two, making the size always vibrate around the optimal one.  Even so, the advantage of our scheme is still clear: it is the first RFID estimation scheme that can work in real life. Notice that ART claimed to work with RFID systems because they are theoretically compatible with ALOHA protocols.   Actually, the current COTS RFID systems do not allow user to control the low-level access, like fined-grained adjustment of  frame length and obtaining slot-level feedback, which are necessary to implement ART. Thus, there is no way for ART to implement their algorithms over COTS RFID systems without any hardware  modification and fabrication.








 §.§ Usage II: Missing Detection


Finally, we evaluate the effectiveness of missing detection in real case. We randomly remove m tags from the testbed. Since we only have 300 tags in total, we fix the number of random seeds to 2, k=2. The performance is evaluated in term of the false positive rate (FPR), which is the ratio of number of mistakenly detected as missing tags to the total number of really missing tags. Our scheme is able to successfully find out all the missing tags because the residual table always contains the entries that missing tags are tashed into. Fig. <ref> shows the results of the first case in which we use an 8-bit hash table (l=8) to detect the missing tags. Consequently, the FPR is maintained around 0.01 when m<14 (5% of the tags are missing).  Fig. <ref> shows the second case in which we remove 10 tags and detect the missing tags by changing the dimension of tash table.  As Theorem. <ref> suggests, we should set l=5,6,7 to guarantee the FPR γ< 0.2,0.1,0.01. From the figure, we can find that the results of our experiments completely conform to this theorem. The real FPRs equal 0.21, 0.07 and 0.008 in the three cases. Tash enabled missing detection works well in practice.








§ CONCLUSION



This work discusses a fundamental issue that how to supplement hash functionality to existing COTS RFID systems, which is dispensable for prior HEPs. A key innovation of this work is our design of hash primitives, which is implemented using selective reading. Tash not only makes a big step forward in boosting prior HEPs, but also opens up a wide range of exciting opportunities.




§ ACKNOWLEDGMENTS

The research is  supported by GRF/ECS (NO. 25222917), NSFC  General Program (NO. 61572282) and Hong Kong Polytechnic University (NO. 1-ZVJ3). We thank all the reviewers for their valuable comments and helpful suggestions, and particularly thank Eric Rozner for the shepherd. 


ACM-Reference-Format
 

