Recovery of Collided RFID TagsW ith Frequency Drift on Physical Layer

Junzhi Li,Haifeng Wu,and Yu Zeng

Abstract—In a passive ultra-high frequency (UHF) radio frequency identification(RFID) system, the recovery of collided tag signals on a physical layer can enhance identification efficiency. However,frequency drift is very common in UHF RFID systems,and w ill have an influence on the recovery on the physical layer.To address the problem of recovery with the frequency drift, this paper adopts a radial basis function(RBF)network to separate the collision signals,and decode the signals via FM 0 to recovery collided RFID tags. Numerical results show that the method in this paper has better performance of symbol error rate (SER)and separation efficiency compared to conventional methods when frequency drift occurs.

I.INTRODUCTION

IN a passive ultra-high frequency(UHF)radio frequency identification(RFID)system,collision w ill happen when tags transm it their signals to a reader simultaneously[1]–[4].Most of traditional anti-collision methods are on a media access control(MAC)layer[5],[6], but the collision signals could be separated and recovered on a physical layer to enhance tag identification efficiency[7]–[20].For UHFRFID system,separationmethodsmay be different from traditional ones.First, the tag signals symbol period is time-variant due to its frequency drift.In the EPC C1 Gen2 standard[21],the symbol frequency drifts w ithin the range of nom inal frequency,±22%.The separation has to be performed under an asynchronous mode.Second,the separation could be considered as a cluster problem.For supervised cluster methods,good channel information is required[16] but difficult to be estimated w ith the frequency drift.On the other hand,unsupervised methods w ill have higher complexity.

The constellation mapping(CM)algorithm[17]can adopt an unsupervised cluster method to enhance the accuracy of the channel estimation, but the computational complexity increases w ith the number of the collided tags.The single antenna zero forcing(SAZF)algorithm[19]is a supervised method and needs the channel information to determ ine the centers of clusters.However, the SAZF can estimate the channel w ith only two collided tags.Collision signal separation in the successive interference cancellation(SIC)technique[18]and the least-square channel estimate(LCE)[20]also requires channel information,which is estimated via the period and delay of a preamble.Likew ise,the frequency drift leads to a time-variant period and poor channel estimation.Besides,some recent algorithms in[9],[22]also focus theirworks on physical-layer tag collision separation in an RFID system.However,[22]does not take into account the effect of the time-variant period,i.e.,the frequency drift on the separation.Reference[9]focuses more on the use of compression sensing to monitor themissing tags in real time,and still doesnot discuss the frequency drift more.

Another concern this paper addresses is signal decoding.Matched filter[19]and Viterbi algorithm[18]are popular decoding algorithms for an RFID system.They are also proposed to decode collided RFID signals.Due to the frequency drift,however,an invariant waveform of the matched filter is difficult to guarantee decoding under the condition of maximum signal to noise ratio(SNR).Viterbi algorithm is a searching method w ith fewer searches for an optimal path.The algorithm may also be introduced to decode RFID collided tag signals.Aswe know, Viterbi needs to find the minimum distance between each possible path and an expected path.When frequency drift occurs,the distance between an optimal path and an expected path may not be a m inimum value.This w ill result in poor performance of symbol error rate(SER).Although[23]considers signal decoding,it unfortunately does not discuss FM 0 or M iller code and is difficult to apply to an RFID system for EPC C1 Gen2,where FM 0 and M iller has been specified as a UHF RFID coding standard[8],[14],[22]–[25].The methods in[8],[23],[25]consider FM 0 decoding directly from collision signals and can be applied to the frequency shiftamong tags,but it assumes that the frequency drift doesnot occur.

In this paper,an adaptive radialbasis function(RBF)neural network[26]is introduced to separate the collision tag signals in the UHF RFID system.Ow ing to a prior known preamble,the introduced RBF could complete a supervised cluster for the collision signals well even though the exact channel information is not known.Then,an FM 0 decoding technique in our previous work in[27]is adopted to cancel separated errors.The technique could detect edge transitions to decode the separated signals regardless of the frequency drift.From numerical results,our method for the three collided tags performs better than conventional methods when frequency drift occurs.

In the rest of this paper, we give the system model and the proposed separation algorithm in Section II.In Section III,we describe a decodingmethod for frequency driftenvironments.We give simulation results to show the performance of the separation in Section IV.Section V isour discussion.The last final section drawsa conclusion.

II.System Model and Col l ision Sepa ra tion W ith Frequency Dr if t

A.System Model

When a reader identifies UHF RFID tags,it sends a continuous carrier signal w ith energy for the RFID tags[7],[22].Giventransmitting tags in a slot, the reader w ill receive the superposition of their signals and then down convert the receiving signals to baseband.Hence,the complex-valued baseband signal at the receiving antenna is[18]–[20]

B. RBF Separation Algorithm

Fig.1.An architectureof RBF network for separation.

Fig.2.RBFnetworks separate three collided tags.

Moreover,RBF is a supervised method,where the centers are trained via the preamble and the adaptive algorithm in(6).In fact,the symbol value of the preamble is already known since the EPC C1 Gen2 has specified it.What cannot be known is the symbol period in the preamble.How to acquire the period has been proposed in[18]. And,a previouswork in[20]also introduced it.Of course,[18]and[20]do not consider the frequency drift.Thus,the preamble acquired by[18]and[20] w ill have someerrors.However,the principleof thealgorithm in [18]and [20]is to search a maximum value in the inner products of the mother functions and collided preambles,and searching is in a range of 22%that the EPC has specified.Thus, the maximum value for searching is in fact an average value of the symbol periods and w ill not be beyond the range of 22%. Via an initial center value chosen by a method in[17](the details can be seen in the Section IID), then,our RBF network w ill adopt the adaptive algorithm in(6)to enhance the accuracy of center estimation.A fter separation by the RBF,our method can cancel the RBF separating errors via FM 0 decoding.Even if there is a small amount of error in the training data,itw ill not have a great impact on the separated signals because it can also be corrected by our FM 0 decoding, which ensures lower SER.Next,we w ill discuss other points whichmay have an impact on the performanceof this proposed collision recovery.

C.The Number of Centers

From (3)–(12),where the number of centersand the number of tagsw ill have the relationshipM=2I,our algorithm must estimate the number of tags if we want to know how many centers should be used.The cluster-based methods in[8],[17]–[20]could be used to estimate the number of tags.For example,3 gives the IQ plan of three collision tag signals.From the figure, the number of center points is 8,which can be obtained fromM=23.That is, the number of tags can determ ine the number of center points.The details of the RFID system setting in Fig.3 can be see in Section IV-A.

Fig.3.Clusters for three collided tags in an I/Q plane.

Another method in[8]may also estimate the number of tags,which is to judge how many transition edges in a V signal[21]of a preamble.The V signal indicates an FM 0 violation,which means that a phase inversion should have occurred but did not.An example is illustrated in Fig.4,where the V signal signed in an oval has three edges and the number of tags is three.

Even if we do not know the number of tags,and hence do not know theactually number of centers,there w ill beonly the follow ing two cases.

1)When the number of chosen centers is more than the actual number of clusters,the network training can be completed.As shown in Fig.5,the number of clusters iseight and the number of chosen centers marked by circles is fourteen.From the figure,a curve can effectively classify signals 0 and 1.That is,the signals on one side of the curve are 0 and on the other side are 1.The results are consistent w ith[27].However,the complexity of network training w ill increase due to excessive centers.

Fig.4.Estimation for the number of tagsvia V signal in a preamble.

Fig.5.More chosen centers than actual centers in classification.

2)When the number of chosen centers is less than the number of clusters,the trained network sometimes cannot separate collided tags.An example is shown in Fig.6,where the number of clusters is eight and the number of chosen centers is six.From the figure,a curve has crossed one of clusters.

Fig.6.Fewer chosen center than actual centers in classification.

From the analysis above,if we do not know the number of tags, we have to choose asmany centers as possible despite this leading to a higher computational complexity.However,for a dynamic frame length protocol,the average number of tags in a collision slot is about 2.33.Hence,we would consider the case for two or three collision tags in the protocol.It isnot necessary to choose excessive centerswhich aregreater than eight clusters.

D. Initial Value of Centers

Since we adopt an adaptive method in(6)to obtain the value of the centers,how we choose an initial value w ill be key for the estimation.One of the methods is to selecta value from the result of conventional estimates,like[18]–[20].Due to frequency drift, however,conventional estimates do not work well and thus the initial values from them may not be good candidates. Note that the centers of clusters are timeinvarianteven w ith the frequency drift,as long as the channel information is time-invariant.Therefore,we could adopt an unsupervised cluster method in[17],where thek-means algorithm is used to accurately estimate the centers.However,the unsupervised method has higher computational complexity.

Another simpler method is also proposed in [17]. Here, Fig.7 gives the stepsof the methods.First,let an I/Q plane be paved w ith grids.Then,the number of points falling into each grid are counted and plotted on a histogram.Finally, project the histogram to thexaxis oryaxis,and find each cluster peak.Whenwe find the grid where the peak is located,wew ill take the center of the grid as the initial value. Via the adaptive iteration in(6),our RBF network could find more accurate centers.

E. Power Gains of Channels

Our algorithm isalso related to the power gainsof channels.Different kinds of channels may produce different performances.Our channel at least guarantees the two follow ing conditions.

1)The power gains of channels should be time-invariantor slow ly variant.Sim ilar to[17],[19],[20],our algorithm is actually a cluster-based method.If the power gains change,the centers of the clusters w ill also change.Thisw ill have an influence on the performance of clustering and classification.Consider an UHFRFID system w ith link frequency 500 kHz and 96 bit-ID tags.The duration of transm itting a 96 bit ID is only about 0.192ms.UHF RFID is a type of near-field communication system.A one to three-meter field is a usual communication distance.In this case,the condition that the channels during an identification cycle are flat-fading and time-invariant condition are guaranteed.It is this reason that the power gainsof channelsare invariant,like[17]–[20].

2)The power gains and orientation of channels should be different among tags.Consider the follow ing special cases.If two or three tags channelsare all identical, the original22 and 23 clustersw ill decrease to 3 or 4 clusters,as shown in Figs.8 and 9.In this case,it is difficult to separate the collided tags.Therefore,less difference of channels among tagsw ill result in worse performance of separation,and[6]–[9]require that separation should be performed under different power gainsof channels.In practice,the position and direction of tagsmay be different.Thus,the fading coefficient and orientation of channelsw ill be different.

Fig.7.Gain the initial value of centers.

Fig.8.Infulenceof two channelsgain.

III.Signa l Decoding W ith Frequency Dr if t

Due to noises,inferences,and drifts,signals separated by the RBF network w ill have some errors.To remove these separated errors,we introduce our FM 0 decoding method under the condition of the frequency drift.In the EPC C1 Gen2 standard,FM 0 isvery popular for RFID tag signals[21],[25].Fig.10 illustrates an example of FM 0(M=1)code,where theremust be an edge(1 to 0 or 0 to 1) between two symbols.Moreover,a symbol 0 means that there is another edge in the middle,while 1 means no edges.From the example,FM 0 can be decoded where the edgesare.Due to the frequency drift, however,FM 0 w ill fail to be decoded only through the edges because the symbol period is time-variant.Next,wew ill describe how to decode separated signals under the condition of frequency drift.

A. FM 0 Decoding With Frequency Drift

Fig.9.Influenceof three channels gain.

Fig.10. An example for FM 0 code.

From the example in Fig.10,the general rule for FM 0 decoding is:a symbol w ill be decoded as 0 if there is a positive or negative edge during the symbol,and a symbol w ill be decoded as 1 if there are no edges during the symbol.Further,there must be an edge between two symbols.Furthermore,the periods of symbols are time-variant due to frequency drift.Thus,the time when the edges occurw illalso be uncertain and w ill be in a range.Of course,FM 0 is also considered as a hidden Markov chain where a Viterbi algorithm may be adopted[18].However, when the symbol frequency is time-variant,computing the distance between two paths is very difficult.Matched filters w ith maximum-SNR criterion[19]are also notappropriate.This is because a time-variant symbol frequency is difficult to match to an appropriate filter.

Some existing methods can directly recover the collided tag via decoding,e.g.,the method in[25].However,when the frequency drifts,i.e.,w ith a time-variant frequency, these methods do not work well.Themethod in[8]can be applied to the frequency shift among tags, but it assumes that the frequency in a tag w ill notdrift,i.e.,a tag whose frequency is time-invariant.Thus,an FM 0 symbol w ill be decoded as 0 if there are edges during the symbol,and decoded as 1 if there are no edges.For the example of a one-order(M=1)FM 0 code shown in Fig.11 from[8],a symbol even in collision w ill be decoded as 0 as long as there is an edge on half of its period times that are odd numbers,i.e.,(2n+1)T/2whereis a symbol period andis an integer.However,when the frequency drifts,the transition edges position may be timevariant.Determining when this transition happens is difficult.Reference[8] judges whether there is an edge through a threshold.When the value of the transition is greater than the threshold,the transition w ill be valid.If there are noises or interferences,however,the value of the transition may be affected.Thus,the use of this threshold may lead to m isjudgment.

Fig.11.Collision separation in [8].

In this paper,our algorithm is divided into two stages:separation and decoding.On one hand,since the signals separated by an RBF cover a single tag and appear either 1 or 0,it iseasy to know when the transition happensas long asa 1 changed into 0 or 0 changed into 1.A lso,because the frequency drift is w ithin 22%,the EPC specifies can eliminate invalid transitions.Thus,it is notnecessary to know the exact period.

On the other hand,due to noise and interferences,the separated signals by RBF networksw ill have separated errors,as shown in Fig.12.The signalsshown by black boxesare the separation errorsand the transition edgesare invalid edges.In this case, recovery of collision cannot be performed well only through direct FM 0 decoding, because FM 0 believes that a symbol is decoded as 0 as long as transition edges happen during the symbol.In our FM 0 decoding,a frequency beyond 22%w ill be considered asan invalid edge.Therefore,edges in theblack boxes would be canceled.

Fig.12.Separated errorsshown in black boxes.

In aword,the separated signals by RBFnetworkshave only two cases:0 or 1.Thus, where 0 changes into 1 or 1 changes into 0,a transition edge occurs.More complex detection theorymethods,such as setting a threshold or seeking a peak via correlation functionsseem to be unnecessary.

B.Steps of FM 0 Decoding

Fig.13.Stepsof FM 0 decoding.

Algorithm 1Algorithm of decoding 1)Record all edgesposition ,,where denotes the total numberof edges;2)Calculate images/BZ_137_772_2819_793_2852.pngimages/BZ_137_830_2815_1051_2852.png images/BZ_137_1217_2815_1250_2848.pngthe levelw idth ;3)Ifimages/BZ_137_497_2966_681_3003.pnga)and ,there w ill be a valid edge during a symbol and the symbol is decoded as 0.images/BZ_137_343_3066_364_3104.pngimages/BZ_137_463_3066_955_3108.png

Thus, and ;li∈[Tlp/1.22 Tlp/0.78]IDi=0 i=i+1 b),there w ill be no edges during a symbol and the symbol is decoded as1.Thus, ;liTlp/0.78 IDi=1 c),there w ill be an invalid edge during a symbol.Thus, ;i=i+1 ti=ti+1,ti+1=ti+2,...4) .If ,go to step 3).i

IV.Resu l ts

A.System Setting

In this section,we give numerical results to verify the performance of the tag collision recovery.In the numerical experiments,we consider a scenario w ith a single-antenna reader and some passive tags.The final resultsare theaverage of 3000 independent experiment results.

The readers need to use a cross-layer approach to identify tags.The A loha protocol is used on the MAC layer.When the tags in the MAC layer collide,the proposed method recovers the collision at the physical layer.Some system parameters in the experiments are referenced to the EPC C1 Gen2 standard[21],and the others are referenced to[9],[17]–[20].The detailed parametersareas follows.

B.Separation via RBF

Figs.14(a)– (c)gives resultswhere RBF network separates three collided tags in an I/Q plane when frequency drift occurs and SNR=25 dB.We can see from Fig.14 that,the signals on one side of the classified curvesare classified as 1 and the other classified as 0.That is,the curves could separate the cluster into signals1 and 0.

Furthermore,note that only an approximate linear line could classify the clusters for the separation of tag1 and tag3 shown in Fig.14(a)and (c).On the other hand,the classifying curve of tag 2 shown in Fig.14(b),requires to be nonlinear.

C. Estimation of Centers

When the number of collided tags is three and frequency drift occurs,the results for center estimation through SIC[18],SAZF[19],LCE[20]and RBF is given in Fig.15.From the figure,our method has fewer estimation errors than other conventionalmethods when SNR isgreater than about12 dB.It owes to an initial center value chosen by themethod in [17].Moreover,our RBF network can adopt the adaptive algorithm in (6)to further enhance theaccuracy of the center estimation.

D.SERand Separation Efficiency

Fig.14.RBFnetwork separates three collided tags.

To evaluate the performance of each algorithm on separating tag signals,we consider the metric of ID SER,which isdefined as

Fig.15.Comparison resultsof center estimation via variousalgorithms.

Fig.16.Symbol error rate in(14)when the number of tags is three and no frequency drift occurs.

Fig.17.Separation efficiency in(15)when the number of tags is three and no frequency drift happens.

When the number of collided tags is three and no frequency drift occurs,the SER of SIC,SAZF,LCE and RBF for the three tags is given in Fig.16.From the figure,the SER curve of the RBFalgorithm is below that of theothers.The reason is that RBF does not need accurate channel information is because itdecodes the separated signal directly from the FM 0 code.Fig.17 shows the separation efficiency of the algorithms under the condition of three collided tags and no frequency drift.From the figure, the maximum separation efficiency of SIC and SAZF are 30%and 33%,respectively.The separation efficiencies of RBF and LCE algorithm increase w ith SNR when SNR >5 dB,and the separation efficienciesnearly reach 98%.However,the RBF curve isstill on the leftof the LCE curvewhichmeans the performance of separation for RBF is a littlebetter than that of LCE.

Fig.18 gives SER of SIC,SAZF,LCE and RBF under the condition of three collided tagsand frequency drift.As shown in Fig.18,only the SER curve of RBF decreasesw ith SNR.Fig.19 shows the separation efficiency of the algorithms under frequency drift. As shown in Fig.19,only the separation efficiency of RBF increasesw ith SNR,and nearly reaches 98%when SNR=25 dB.On the other hand,the separation efficiency of SIC,SAZF and LCE algorithm is still 0 even under higher SNR.The resultsof the two figuresabove indicate that frequency driftmakes the other algorithms fail to decode the collided tags under higher SNR.

Fig.18.Symbol error rate in(14)when frequency drift happens and the number of tags is three.

Fig.19.Separation efficiency in(15)when frequency drift happensand the number of tags is three.

Fig.20 gives the SER of four algorithms above under SNR =20 dB,when frequency drift occurs and the number of tags varies from 2 to 4.Similar to Figs.19 and 20,the curve of RBF is not horizontal regardless of the number of tags.The results indicate that two collided tag signals cannot be recovered by the other three methods as long as frequency drift occurs.

Fig.20.Symbolerror rate in (14)under SNR =20 dB when frequency drift happensand thenumber of tagsvaries from two to four.

Fig.21.Symbolerror rate in (14)under SNR =20 dBwhen frequency drift varies from 0 to 22%and thenumber of tags is three.

We give the comparison between our method and the method in[8]for SER performance under different drifts,shown in Fig.21 when SNR is 20 dB.From the figure,when the frequency is time-invariant,i.e.the drift is 0%,SERs of the method in[8]and ourmethod are both lower than.Due to the noises having influence on the threshold judgment,[8]smethod shows higher SER.When the drift varies from 5%to 22%,however,[8]arrives at about.On the other hand,our methodsSER is betweenand.

V.Discussion

From the numerical results,the proposed algorithm can separate collision tag signals w ith the frequency drift.Here,we w ill discuss some several factors that have an impact on the performance of the proposed algorithm.The first factor is chosen centers.The number of clusters for collision signals mapped to an I/Q plane is the number of tags of 2 powers.Generally,the number of centers for an RBF networkmay be chosen as the number of clusters.Thus,the number of centers would be known if the number of tags is known.When the number of tags is unknown,however,selecting the appropriate number of tagsw ill be key for the RBF network.From Figs.5 and 6,it is seen that too few centers is notused for correct separation while too many centers produce higher computational complexity of network training. As seen from the numerical results in Fig.20,the performance of the separation is related to the number of collision tags.SER w ill increase w ith the number of collision tags,especially, when the number of tags is 4,SER is beyond 10–1.Thus,it is not necessary to separate all of collision tags regardless of the number of the collision tags.Separation for only two or three collision tags would a w ise choice.For a dynam ic frame length protocol,the average number of collision tags in a collision slot is about 2.33[5].Therefore,eight centers can copew ith an RBFnetwork for most of the collision tags.

Continuing, the preamble signalw illhave an impacton the RBF network.When the frequency of symbols drift,it is difficult to acquire exact information for the period and delay of symbols.The estimated preamble w ill have errors,which w ill also produce a trained RBF network w ith some errors.However,the drift is a low-frequency variation process,and the preamble signal only takes up about six symbol periods.The time information estimated by the existing methodsw ill not have more errors.Moreover,the errors w ill also be eliminated via FM 0 decoding.

The power gain and direction of channels is another key factor.In an extreme case,the exactsame channelw illnot be able to separate collision signals because the clusters of two tagsw ill overlap w ith each other.In a realenvironment,if the location,direction,and distance of the tags are different,the channel gain w ill be different,and thus the collision signals could be separated through the RBF network.

We choose three tags because the average number of collision tags in a slot is about 2.33 w ith the A loha method from[3].This indicates that the case of more than three collision tags in a slot is a low-probability occurrence.Moreover,our algorithm's separation curve makes it more difficult to classify clusters when there are too many collision tags.Thus,if more than three collision tags happen,we w ill not choose separation on the PHY layer.

It should be noted that the training time has an important influence on the tag separation performance of our algorithm,mainly on the RN16 stage.If the training time during RN16 is too long,the system w ill consider the tag asunresponsive and thus discard the subsequent identification of the tag.In fact,the training time of the proposed algorithm is related to the computing performance of hardware.Using high-performance computing chips can effectively reduce training time,but this w ill increase readers costs.As the performance of chips increase and the price decreases,our algorithm could be an alternative solution.

VI.Conc lusion

The symbol frequency drift of RFID tag signal is a common phenomenon in a UHF system.This paper uses an RBF algorithm and FM 0 to recover the collided tag signals w ith frequency drift.From experimental results, the performanceof the symbolerror ratesand the separation efficiency for RBF is better than those of traditional algorithms when symbol frequency drift occurs.

Since the separation of collision signals in an I/Q plane is in fact a clustering problem, this paper proposes an algorithm to separate collision signals via an RBF neural network.In this paper,the algorithm only gives a framework for theoretical implementation of communication signal processing,and the numerical experiment is carried out on a software platform,which is not tested in real environment.However,all parameters are set from the actual environment,such as EPC C1 Gen2,and we plan to run the algorithm in a real UHF RFID system in the future to test its performance.