A Dynamic Multi-ary Query Tree Protocol for Passive RFID Anti-collision

Gang Li,Haoyang Sun,Zhenbing Li,Peiqi Wu,Daniele Inserra,＊,Jian Su,Xiaochuan Fang and Guangjun Wen

1Centre for RFIC and System,School of Information and Communication Engineering,University of Electronic Science and Technology of China,Chengdu,611731,P.R.China

2Nanjing University of Information Science&Technology,Nanjing,210044,China

3Queen Mary University of London,London,United Kingdom

Abstract: In this paper,a dynamic multi-ary query tree(DMQT)anti-collision protocol for Radio Frequency Identification(RFID)systems is proposed for large scale passive RFID tag identification.The proposed DMQT protocol is based on an iterative process between the reader and tags which identifies the position of collision bits through map commands and dynamically encodes them to optimize slots allocation through query commands.In this way,the DMQT completely eliminates empty slots and greatly reduces collision slots,which in turn reduces the identification time and energy costs.In addition and differently to other known protocols, the DMQT does not need to estimate the number of tags, reducing the protocol implementation complexity and eliminating the uncertainty caused by the estimation algorithm.A numerical analysis shows that DMQT has better performance than other algorithms for a number of tags larger than 300.Meanwhile, when the number of tags is 2000 and the tag identity(ID)length is 128 bits,the total identification time is 2.58 s and the average energy cost for a tag identification is 1.2 mJ,which are 16.9% and 10.4% less than those of state-of-the-art algorithms, respectively.In addition, a DMQT extension based on ACK command has also been presented to deal with capture effect and avoid missing identification.

Keywords:Anti-collision;DMQT;RFID;dynamic multi-ary query;seamless identification

1 Introduction

RFID is attracting a lot of attention from both academic research and industrial environment not only because of historical field of applications like assets management and tracking[1]or indoor localization [2,3], but also for other new potential usages like the implementation of tag-sensors for environmental monitoring[4,5].Furthermore,RFID has been recognized as one of the key technology for the implementation of Internet of Things (IoT)and Internet of Everythings (IoE)paradigms[6].In this context where a multitude of RFID tags are simultaneously connected,it is fundamental to develop anti-collision algorithms specifically designed for RFID; in fact, general multiple access algorithms cannot be applied for RFID due to the limited hardware equipment of tags,especially the passive ones.

The existing anti-collision algorithms are mainly based on Aloha (where the medium access mechanism is random)and tree (based on deterministic search mechanisms)schemes, and many variants have been proposed during the years(Pure Aloha(PA)[7],Slotted Aloha(SA)[8],Framed Slotted Aloha(FSA)[9],Dynamic Frame Slotted Aloha(DFSA)[10],etc.,and Query tree(QT)[11],Tree Splitting(TS)[12]Binary Search(BS)[13], Bitwise arbitration(BTA)[14],etc.).Clearly, if tree anti-collision algorithms are properly designed, they can offer superior efficiency than other nondeterministic methodologies.

In QT protocols,the reader probes different ID prefixes(starting from one bit and then iteratively concatenating all the others)to identify all the tags population.In Binary QT protocol, only the most significant bit (MSB)of the collided ID part is used, therefore it generates a large number of collision slots and empty slots during the identification process [15].For this reason, some Multiary QT protocols (which probe tag IDs with multiple M bits simultaneously)have been proposed to improve the system’s identification performance.For this reason, some Multi-ary QT protocols(which probe tag IDs with multiple M bits simultaneously)have been proposed to improve the system’s identification performance.[16]proposes a time-and energy-aware protocol based on M-ary collision tree(MCT)for efficient RFID tag identification,the M is a fixed value,and this may cause many idle slots when M is too large,or several collision slots when M is too small,making difficult to find an optimum performance, [17] is similar to [16] in that it has fixed M value.[18] proposed a bit query algorithm based on Multi-ary query tree (BQMT)protocol to eliminate empty slots.However, the algorithm requires to estimate the number of tags of non-idle nodes,which increases the uncertainty and complexity.In[19],authors proposed an adaptive assigned tree slotted Aloha(AdATSA)protocol,which again needs to estimate the number of tags, and its maximum efficiency is only 61.7%.In[20], Self-learning Smart Trend-Traversal (STT)protocol dynamically changes the length and the value of query prefix,which increases the number of empty slots and,therefore,resulting in a longer identification time.In[21],a collision window tree(CwT)protocol used to transmits W bits instead of the whole ID (0＜W＜K (K is the bit width of ID)), which causes more time slots than other QT-based protocols,resulting in a longer identification time.

In this paper,a dynamic multi-ary query tree(DMQT)protocol for passive RFID anti-collision is proposed.Differently from[16-18]which use a fixed M value,the proposed DMQT exploits a dynamic multi-ary tree structure to eliminate the number of empty slots with the consequent minimization of the identification time and required tag energy, and it does not require any number of tags estimation algorithm as in[18,19],avoiding estimation uncertainties and the consequent identification time stretching.Moreover,it employs multi-ary Map command to reduce the transmission overhead similarly to[21],which further reduces the identification time.

The main contribution of this paper can be summarized as follows:

1.A DMQT protocol which uses Map command to identify collision bits quantity and position and dynamically group certain portions of tags to minimize the collision probability,and Query command to complete the identification of the grouped tags.The dynamic selection ofMand the Map/Query mechanism is fundamental to eliminate empty slots and minimize collision slots,with the consequent reduction of the identification time.

2.The DMQT does not rely on any number of tags estimation algorithm, therefore greatly reducing the implementation complexity if compared with[18](which requires such estimation process),and eliminating the uncertainty caused by the estimation algorithm(which in many cases increase the identification time).

3.An extensive numerical analysis is performed to benchmark the performance of the proposed DMQT and compare it with other existing algorithms,confirming the validity of the proposed algorithm.Moreover, a simple algorithm extension is proposed for coping with the capture effect,whose performance is also numerically verified.

2 Preliminaries:Bit Tracking and ID Query

In this paper, we mainly focus on large RFID systems, i.e., the identification of a large number of passive tags.Readers have no prior knowledge of the distribution of tags around them (they do not know the number of tags and their ID information), and adopt the reader-talk-first model to work.Tags respond to commands issued by readers.As the number of tags in RFID system may reach thousands to tens of thousands and all tags share the same communication channel, tag collisions easily happen which increases the collision time slot and identification time.How to quickly identify a large number of tags is a big challenge for RFID system[22-27].

In RFID systems,Manchester encoding is often used to identify collision information.Manchester Encoding is a line code,in which every bit of data will have a transition in the middle of the data bit after coding [28].In general, the transition from high to low level (down edge)in the middle of the data represents data 1,and the transition from low to high level(up edge)represents data 0.If the receiver receives two tags returning different information at the same time, this will cause the rising edge and falling edge to cancel each other,resulting in the appearance of an illegal symbol,which the receiver can consider as a collision[29].As shown in Fig.1,it is assumed that the IDs of the two tags are“10101101”and“11101011”,respectively.

Figure 1:Manchester coding

The ID of the two tags is encoded using Manchester code, and sent to the receiver at the same time,resulting in the received code“1x101xx1”,where“x”represents the collision bit.As a result,the receiver can detect collisions with 3 bits of data.The receiver can estimate the number of tags around it according to the collision information and some tag number estimation algorithms,thus improving the identification efficiency of RFID system[30].Finally,due to the very low modulation signal rate of the tag and the commands issued by the reader,bit-wise synchronization of tag responses is assumed[18,31,32].

3 Proposed DMQT Description

For the sake of a better comprehension and to make the paper more readable,Tab.1 summarizes the notation employed in this work.

Table 1: Notation used in this work

The proposed DMQT protocol is composed of a multi-ary Map command and a Multi-tags query command.The Map command is used to sound the distribution of collision bits, while the Query identifies tags and/or obtains collision information.Fig.2 describes the timing logic of DMQT.Except for the first Map command(M=0),there is a one-to-one correspondence between Map commands and Query commands.The Map command can obtain ID distribution of matched tags, and then perform targeted group identification in Query to eliminate empty slots.The DMQT can continuously identify multiple tags or obtain collision information of multiple groups of tags using Query,reducing the identification time and power consumption.WhereTMis the time when the reader sends the Map command,T1is the tag response time,T2is the reader response time,T3is the tag response interval in the adjacent sub-slots in Query command,TRis the duration of the tag response signal,and‘reps’is the response of tag.

As shown in Fig.2, the DMQT algorithm has no empty slots, and only the success slots and collision slots.The Query command has multiple sub-slots.The sub-slots are the success slots without collision,and the sub-slots are the collision slots with collision.

Figure 2:DMQT algorithm timing

The proposed DMQT protocol is based on a“map and query”iteration process.A Map command is firstly executed to locate the collision bits,select one portion of these bits,and identify the number of collided bit patterns,while the query command is employed to splits the tag ID patterns into different slots.This operation is executed iteratively until no collisions are identified within slots.The length of the collided patterns and the number of slots is updated dynamically to minimize the required identification time.The DMQT identification process is shown in Fig.3, where the number of tagsNtag=9.

Figure 3:Proposed DMQT protocol

3.1 Multi-ary Map Command

The structure of the Map command(simply Map in the follows)is shown in Tab.2.The fieldLenindicates the length of the fieldInfowhich is the portion of ID before the most significant collision bit;Mindicates the number of fields～present which denote the position of the firstM-1 collided bits(the first collided bitis at positionLen+1 therefore is not included).

Table 2: Structure of Multi-ary Map

At the beginning,the reader sends a Map withM=0 and waits for tag response.When the reader receives the tag response,it determines the newMvalue and all the other fields required to generate the new Map,which is then sent to tags.the newMvalue as

Here, theLindicates the number of collision bits received by the reader (the maximum value is the length of tag ID,ID_length),andis rounded down.According to Formula(1),whenx=2 andL=128,the maximum value ofMis 7;Whenx ＞2,M ＜7.The choice of the logarithmic function in(1)has been inspired by the common sense.Nevertheless,the parameterxhas been left free to provide a certain degree-of-freedom to the logarithmic function,as it will be shown in Section 4.

Table 3: Tag response to Map

The structure of tag replies to Map is instead depicted in Tab.3.When a tag receives a Map, it checks whether itsLenmost significant bits(MSB)of ID matchInfo;in this case,it setsMask_flag=‘1’,Anti_tagID={bit1,bit2,...,bitM},andTag_mdas

It is worth noting that for each tag only one bit of(2)will be‘1’,and its position withinTag_mdwill be the correspondent decimal value ofAnti_tagIDplus 1=bin2dec(Anti_tagIDk)+1,k∈{1,...,N}(whereNis the number of replying tags),e.g.,ifM=3 andAnti_tagID={‘101’},then=5 andTag_md= {‘00100000’}.In this way, the reader can useTag_mdto fully recover bit1,bit2,...,bitMvalues which will be used to generate the query command.If the ID prefix does not matchInfo,the tag remains silent and setsMask_flag=‘0’.

When reader receives theNtag replies,it checks the number of collision bits ofTag_md,n,and their positions,In this way,the reader can recover(i)the originalMbits of theNtags ID with the inverse function of(2),i.e.,

and(ii)the number of replied differentAnti_tagIDpatternsn.It is worth noting thatn≤Nbecause more than one tag may share the sameAnti_tagIDpattern, and these tag IDs will be discriminated successively.

3.2 Multi-tag Query Command

The structure of the query command(simply Query in the follows)is shown in Tab.4.The Query divides the Map matched tags intonsubsets corresponding tonslots,ordered according to[which is determined by the reader from the result of(2)].

When a tag receives the Query, it firstly checks whetherMask_flag= ‘1’and, if not, it stays silent; otherwise, the tag (i)locates its correspondent reply slot within Query, i.e., the subset with{bit1,bit2,..,bitM}=Anti_tagID,and(ii)it sends back its Remnant ID(except the portion included inInfo)within the correspondent slot according to the reply structure in Tab.5.Obviously, when only one tag replies within one slot, this tag will be identified by the reader.Otherwise, the reader will detect new collisions,and it will generate one new Map for each collision slot based on the collided bits information,pushing these Map commands into a stack,which will be executed at the end of the Query.

Table 4: Structure of the Multi-ary Query

Table 5: Tag response to Query

Note that since the tag responds to the remnant ID,the generatedInfomust include theInfofrom the previous Map command.The newInfois as follows:

Here,Info(old)comes from the previous Map command, andInfo(rem)is generated based on the remnant ID.In the same way,the newlyLenshould be added theLen(old)from the Map command:

Here,is generated based on the remnant ID.If the remnant ID received by the reader in a subslot is“010x11xx01”,thenInfo(rem )=“010”and=3.

The time duration of each slot will be

Therefore,thei-th slot will be delayed by

The reader can calculate the total time of executing the Query command as:

The reader calculates the execution time required by Query according to Eq.(8).When the Query is completed, the reader will pop a Map from the stack executing the Map-Query process until the stack is empty,and updating theLenvalue at each step as the previousLenplus the length of the newInfofield.

4 Numerical Analysis

A numerical analysis of the average and total identification time and average energy cost of the proposed DMQT protocol is now presented (simulations have been carried out according to parameters listed in Tab.6).

Table 6: Simulation parameters

The average energy consumption has been introduced in[16]by estimating the total reader energy required for performing the identification of a tag population,divided by the number of tags under the assumption of constant power(only the RF signal transmission required energy has been taken into account which is the largest energy contribution[33]).During the identification process(of durationTtotal),in fact,the reader should always transmit signals,and therefore the reader employs a total energy ofPtx×Ttotal.For what tags concern, instead, the reader consumes an extra energy contribution to receive and process tag replies, and therefore this extra energy is estimated asPrx×TR,tot.For this reason,the average energy cost has been estimated as:

Eq.(9)shows that it is not only important to reduceTtotal, but also theTR.totto the end of reducing the average energy consumption.The proposed DMQT algorithm can minimize both the total identification durationTtotal(because of the elimination of the empty slots and the reduction of the collision slots)and the tag replies timeTR.tot(because of the reduced number of reader-tag interactions and the transmission overhead).Nevertheless,becausePtxis larger thanPrx[16],andTtotalis longer thanTR.tot,Ptx×Ttotal/Ntag=Ptx×Tavgplays a dominant role in(9).Moreover,becausePtxis constant,Eavgfollows the same trend ofTavg.For this reason,DMQT performanceTavghas been firstly investigated as a function of the parameterx,i.e.,the base of the logarithm in(1),and simulation results are shown in Fig.4.Becausexis too small will produceM=8 or more,leading to tag the returnedTag_mdis too long,make the Query command to produce too much of the time slot,and affect the synchronization between tag and reader.So, the paper sets the maximumMto 7, which makes the response data of tags(M2)do not exceed the length of tag ID,consistent with the other papers[18].

As it can be seen,Tavgis minimized forx=2.1 or 2.2 when the number of tags is within the range 400-1300,when the number of tags is greater than or equal to 1300,Tavgis minimized forx=1.9.Here,theTavgof somexare very similar because the maximumMvalues generated according to thesexare the same(as in Eq.(1),Mis rounded down).For example,the maximumM=6 forx=2.1 andx=2.2,and the maximumM=5 forx=2.3 tox=2.6.In addition,thexdetermines the maximum value ofM.Whenxis smaller,there will be a larger value of M,which is applicable to the case of a large number of tags.On the contrary,whenxis larger,there is a smaller value ofM,which is applicable to the case of a small number of tags,as proved in Fig.4.Therefore,the subsequent simulation analysis ofx=2.2(for conventional application scenarios)andx=1.9(for scenarios with a large number of tags)is mainly carried out.Meanwhile,the proposed DMQT protocol(withx=1.9 andx=2.2)has been compared with other existing algorithms described above,and simulation results are reported in Fig.5,showing the superiority of the proposed scheme when the number of tags is more than 300.In particular,when the number of tags is 2000(withx=1.9),the total identification time is less than 2.58 s,and it corresponds to an average energy costs less than 1.2 mJ,which are 16.9%and 10.4%less than those of state-of-the-art algorithms,respectively.

Figure 4: Comparison of the proposed DMQT simulations results for different x values for average identification time

Figure 5:Comparison of DMQT simulation results with other referred algorithms.(a)Total identification time,and(b)Average energy costs

5 Discussion

In a passive RFID system,when multiple tags reply to the reader simultaneously,it is possible that one tag’s signal is much stronger than other signals,leading to the so-called capture effect[34].If the capture effect occurs,the original collision slot will be turned into a singleton slot,which accelerates the identification process [17].However, the capture effect may cause missing identification [34-38].Although the most part of the published papers ignore the capture effect [33,39-41], in order to improve the robustness of the DMQT algorithm, this effect shall be considered.When the capture effect exists,it may be possible that some tags uninterruptedly reply to the reader’s inventory disturbing the communication with weak signal tags(seamless identification phenomenon).Therefore,DMQT can be optimized by adding a response mechanism based on the ACK command to avoid the replies of tags already identified,i.e.,when the reader recognizes one tag,it sends an ACK command.When receiving an ACK command, the identified tag enters the identification state and does not respond to subsequent identification commands.At the same time, when the reader detects that the stack is empty,it continues a new identification process until there is no tag response in the new identification process.The format of the ACK command is shown in Tab.7,it does not require the tag to return a response signal.

Table 7: Structure of the ACK command

When receiving an ACK command,the tag matching Remnant ID setsRecognized_flag=1,then the tag will not respond to the reader identification command.In order to ensure that the reader and tag can correctly generate and process ACK command,some improvements should be made to DMQT Query timing to meet the requirements of the reader and tag processing timing.The timing logic of Query after adding ACK command is shown in Fig.6.Before adding an ACK,the tag does not need to care about whether the sub-slot is a collision slot or not, and only needs to return the response information in the allocated sub-slot.However,the timing logic adding ACK differs from Fig.2.In fact,the fixedT3cannot be used as the guard time between two continuous sub-slots.Here,T2is still used to represent the time between the end of the tag response and the ACK sent by the reader,andT3is replaced byT4(1.5T2)to ensure that the reader has enough time to generate the ACK command.

Figure 6:Query timing logic with ACK command

Since the ACK does not occur in every slot, the tag must be delayed according to the time slot status.The matching tag(Mask_flag=1)will record the number of successful time slotsSCN,and tag setsSCN= 0 at the start of each Query.According to Fig.6,in the success time slot,the reader will send an ACK,and the extra time consumed is as follows:

Therefore,after the Ack is added,the delay time of the i-th sub-slot of the Query is:

According to Fig.6,the reader can calculate the total time of executing Query as:

After adding an ACK,the identified tag enters the identification state.If no further processing is performed,the tag in the identification state may not respond to subsequent identification commands.To improve system reliability,the tag must be removed from the identification state under the control of the reader.This function can be achieved through different combinations ofMandLenvalues in the Map.Its combined functions are shown in Tab.8.To prevent tag missing identification under capture effect, DMQT will continue to send a “seamless identification”command when the stack is empty,that is,send Map(M=0,Len=1)for a new identification round.If the reader does not receive any reply after sending the seamless identification,the identification process is complete.

The need of the ACK command makes the identification longer, also because more than one inventory is necessary to identify all tags(in fact,stronger signal tags are initially identified during the first inventory round,and weaker signal tags are identified in successive inventories).Performance of the proposed modified DMQT in the presence of the capture effect has been simulated similarly to[17],and results are shown Fig.7(pis herein used to represent the probability of capture effect occurrence).

Table 8: The function represented when M and Len take different values

Figure 7:Modified DMQT simulation results for different capture effect probabilities

As it can be seen,TtotalandEavgslightly increase with the increase ofpbecause at the end of one inventory, another one is executed to verify the presence or not of other weaker signal tags.Nevertheless, the use of the ACK command and theRecognized_flagcan effectively extend the use of the DMQT algorithm to cases in which capture effect occurs.

6 Conclusions

This paper presents a dynamic multi-ary query tree collision protocol for RFID systems which can completely eliminate empty slots and greatly reduce collision slots.The proposed scheme is based on an iterative process between reader and tags which aims at locating all collision bits and dynamically encoding them to optimize slots allocation, which reduces the identification time and energy costs.Particularly, simulation results have revealed that the total identification time and the average energy costs are less than 2.58 s and 1.2 mJ,respectively,when the number of tags is from 300 to 2000,both lower than those of other existing algorithms,making the DMQT protocol very suitable for improving the anti-collision state-of-the-art performance of passive RFID systems.Finally, the DMQT is extended with the use of ACK command to cope with the capture effect,showing excellent identification performance.

Funding Statement:The authors received funding for this study from the National Key R&D Program (https://chinainnovationfunding.eu/national-key-rd-programmes/), project contract No.2018YFB1802102(G.W.)and 2018AAA0103203(W.T,F.X,G.W.),from the National Natural Science Foundation of China(https://www.nsfc.gov.cn/),project contracts No.61971113(G.W.)and 61901095(D.I.), from the Guangdong Provincial Research and Development Plan in Key Areas (https://chinainnovationfunding.eu/funding-programmes-guangdong-province-2/), project contracts No.2019B010141001(G.W.)and 2019B010142001(G.W.),from the Sichuan Provincial Science and Technology Planning Program (https://www.sc.gov.cn/10462/10758/10759/10763/2010/10/28/10147629.shtml), project contracts No.2020YFG0039 (G.W.), 2021YFG0013 (G.W.), and 2021YFH0133(D.I.), from the Ministry of Education (http://en.moe.gov.cn/)and China Mobile (http://www.chinamobileltd.com)Joint Fund Program, project contract No.MCM20180104 (G.W., G.L.), and from the fundamental research funds for the Central Universities (managed by Department of Finance,https://www.fmprc.gov.cn/mfa_eng/wjb_663304/zzjg_663340/cws_665320/),project contract no.YGX2019Z022(G.W.,G.L.,D.I.).

Conflicts of Interest:The authors of this paper declare that there are no conflicts of interest regarding the publication of this paper.