计算机科学与技术（参考文献）Moving Tag Detection via Physical Layer Analysis for Large-Scale RFID Systems

Moving Tag Detection via Physical Layer Analysis for Large-Scale RFID Systems Chuyu Wang,Lei Xie,Wei Wang,Tao Xue,Sanglu Lu State Key Laboratory for Novel Software Technology,Nanjing University,China Email:{wangcyu217,txue@dislab.nju.edu.cn,fIxie,ww,sanglu@nju.edu.cn Abstract-In a number of RFID-based applications such as essential to devise a moving tag detection scheme to detect the logistics monitoring,the RFID systems are deployed to monitor motion status of all tags.In this way,we only need to focus on a large number of RFID tags.They are usually required to tracking the moving tags,saving a lot of effort which might track the movement of all tags in a real-time approach,since the tagged-goods are moved in and out in a rather frequent approach. be wasted in tracking stationary tags. However,a typical cycle of tag inventory in COTS RFID system According to the prior art,in order to track the moving tags usually takes tens of seconds to interrogate hundreds of RFID in the monitoring area,two schemes are essentially required, tags.This hinders the system to track the movement of all tags i.e..a fast tag inventory scheme to interrogate tags,and an in time.One critical issue in such type of tag monitoring is to effective positioning scheme to detect the motion status of the efficiently distinguish the motion status of all tags,i.e..stationary or moving.According to the motion status of different tags,the tags.For the tag inventory in RFID systems,polling protocols state-of-art localization schemes can further track those moving [3,4]have been proposed to improve the time efficiency. tags,instead of tracking all tags.In this paper,we propose a However,they still take tens of seconds to interrogate RFID real-time approach to detect the moving tags in the monitoring tags in a real environment,when the cardinality of tags is area,which is a fundamental premise to support tracking the movement of all tags.We achieve the time efficiency by decoding more than several hundreds.The inefficiency is primarily due collisions from the physical layer.Instead of using the EPC ID to the waste of the collision slots,which usually occupy a fairly which cannot be decoded in collision slots,we are able to extract large proportion in the overall time slots.Hence,even schemes two kinds of physical-layer features of RFID tags,i.e.,the phase based on the pooling protocols [5,6]can efficiently detect the profile and the backscatter link frequency,to distinguish among moving tags based on the statistical signal information.but different tags in different positions.By resolving the two physical- also suffer from the effect of collision slots.Recent research layer features from the tag collisions,we are able to derive the motion status of multiple tags simultaneously,and greatly works consider to redesign new protocols or modify the EPC improve the time-efficiency.Experiment result shows that our C1G2 protocols to make use of the collision slots for better solution can accurately detect the moving tags while reducing time efficiency [7-9].However,they have not yet considered to 80%of inventory time compared with the state-of-art solutions. detect the motion status of the tags.Some protocols [3,10]are Index Terms-RFID,Collision Decoding,Tag Inventory also proposed to detect the missing tags via the physical-layer symbols.But they cannot be used to detect the moving tags I.INTRODUCTION since a moving tag can still exist in the monitoring area instead With the rapid proliferation of RFID-based applications, of missing.For the positioning scheme of RFID systems,the RFID tags have been deployed into various applications in state-of-the-art localization schemes [11,12]usually locate the increasingly large numbers.For example,in the application of tags one by one,and the time delay of localizing a unique logistics monitoring,there are usually more than hundreds of object is up to several hundreds of milliseconds.When dealing goods attached with RFID tags in the monitoring area.Since with more than hundreds of RFID tags it is impossible to the tagged-goods are moved in and out in a rather frequent concurrently locate all tags in a real time approach. approach,the RFID systems are usually required to track the In this paper,we propose a real-time approach to detect movement of all tags in a real-time approach.However.a the moving tags in large scale RFID systems,which is a typical round of tag inventory in COTS RFID system usually fundamental premise to support tracking the movement of takes tens of seconds to interrogate hundreds of RFID tags all tags.Since a missing tag must be moved first,it can [1,2].This greatly hinders the system to track the movement also be simplified as a moving tag detection problem.In of all tags in time.One critical issue in such type of tag our problem,we achieve the time efficiency by effectively monitoring is to efficiently distinguish the motion status of all decoding collisions from the physical layer.Instead of using tags,i.e.,stationary or moving.For the"moving"tags,we can the EPC ID,which cannot be decoded in collision slots,we leverage the state-of-art localization schemes to track them;for are able to extract two kinds of physical-layer features of the "stationary"tags,we do not need to track them any more, RFID tags,i.e.,the phase profile and the backscatter link since they are supposed to be statically placed in a specified frequency,to distinguish the tags in different positions.These position.In most situations,the stationary tags occupy a rather physical-layer features serve as fingerprints of tag identities large proportion while the moving tags occupy only a small and positions.By resolving the two physical-layer features proportion in regard to a certain moment.Therefore,it is from the tag collisions,we are able to derive the motion

Moving Tag Detection via Physical Layer Analysis for Large-Scale RFID Systems Chuyu Wang, Lei Xie, Wei Wang, Tao Xue, Sanglu Lu State Key Laboratory for Novel Software Technology, Nanjing University, China Email: {wangcyu217, txue}@dislab.nju.edu.cn, {lxie, ww, sanglu}@nju.edu.cn Abstract—In a number of RFID-based applications such as logistics monitoring, the RFID systems are deployed to monitor a large number of RFID tags. They are usually required to track the movement of all tags in a real-time approach, since the tagged-goods are moved in and out in a rather frequent approach. However, a typical cycle of tag inventory in COTS RFID system usually takes tens of seconds to interrogate hundreds of RFID tags. This hinders the system to track the movement of all tags in time. One critical issue in such type of tag monitoring is to efficiently distinguish the motion status of all tags, i.e., stationary or moving. According to the motion status of different tags, the state-of-art localization schemes can further track those moving tags, instead of tracking all tags. In this paper, we propose a real-time approach to detect the moving tags in the monitoring area, which is a fundamental premise to support tracking the movement of all tags. We achieve the time efficiency by decoding collisions from the physical layer. Instead of using the EPC ID, which cannot be decoded in collision slots, we are able to extract two kinds of physical-layer features of RFID tags, i.e., the phase profile and the backscatter link frequency, to distinguish among different tags in different positions. By resolving the two physical￾layer features from the tag collisions, we are able to derive the motion status of multiple tags simultaneously, and greatly improve the time-efficiency. Experiment result shows that our solution can accurately detect the moving tags while reducing 80% of inventory time compared with the state-of-art solutions. Index Terms—RFID, Collision Decoding, Tag Inventory I. INTRODUCTION With the rapid proliferation of RFID-based applications, RFID tags have been deployed into various applications in increasingly large numbers. For example, in the application of logistics monitoring, there are usually more than hundreds of goods attached with RFID tags in the monitoring area. Since the tagged-goods are moved in and out in a rather frequent approach, the RFID systems are usually required to track the movement of all tags in a real-time approach. However, a typical round of tag inventory in COTS RFID system usually takes tens of seconds to interrogate hundreds of RFID tags [1, 2]. This greatly hinders the system to track the movement of all tags in time. One critical issue in such type of tag monitoring is to efficiently distinguish the motion status of all tags, i.e., stationary or moving. For the “moving” tags, we can leverage the state-of-art localization schemes to track them; for the “stationary” tags, we do not need to track them any more, since they are supposed to be statically placed in a specified position. In most situations, the stationary tags occupy a rather large proportion while the moving tags occupy only a small proportion in regard to a certain moment. Therefore, it is essential to devise a moving tag detection scheme to detect the motion status of all tags. In this way, we only need to focus on tracking the moving tags, saving a lot of effort which might be wasted in tracking stationary tags. According to the prior art, in order to track the moving tags in the monitoring area, two schemes are essentially required, i.e., a fast tag inventory scheme to interrogate tags, and an effective positioning scheme to detect the motion status of the tags. For the tag inventory in RFID systems, polling protocols [3, 4] have been proposed to improve the time efficiency. However, they still take tens of seconds to interrogate RFID tags in a real environment, when the cardinality of tags is more than several hundreds. The inefficiency is primarily due to the waste of the collision slots, which usually occupy a fairly large proportion in the overall time slots. Hence, even schemes based on the pooling protocols [5, 6] can efficiently detect the moving tags based on the statistical signal information, but also suffer from the effect of collision slots. Recent research works consider to redesign new protocols or modify the EPC C1G2 protocols to make use of the collision slots for better time efficiency [7–9]. However, they have not yet considered to detect the motion status of the tags. Some protocols [3, 10] are also proposed to detect the missing tags via the physical-layer symbols. But they cannot be used to detect the moving tags since a moving tag can still exist in the monitoring area instead of missing. For the positioning scheme of RFID systems, the state-of-the-art localization schemes [11, 12] usually locate the tags one by one, and the time delay of localizing a unique object is up to several hundreds of milliseconds. When dealing with more than hundreds of RFID tags it is impossible to concurrently locate all tags in a real time approach. In this paper, we propose a real-time approach to detect the moving tags in large scale RFID systems, which is a fundamental premise to support tracking the movement of all tags. Since a missing tag must be moved first, it can also be simplified as a moving tag detection problem. In our problem, we achieve the time efficiency by effectively decoding collisions from the physical layer. Instead of using the EPC ID, which cannot be decoded in collision slots, we are able to extract two kinds of physical-layer features of RFID tags, i.e., the phase profile and the backscatter link frequency, to distinguish the tags in different positions. These physical-layer features serve as fingerprints of tag identities and positions. By resolving the two physical-layer features from the tag collisions, we are able to derive the motion

status of multiple tags simultaneously,and greatly improve II.RELATED WORKS the time-efficiency.Specifically,we propose a two-phase tag Collision Recovery Many works focus on how to extract monitoring scheme including the tag inventory and continuous tag cardinality [13]or recover the tag signal [8,9]from polling.In the tag inventory phase,the RFID reader constructs the collision signals based on the specialized instruments like a physical fingerprint for each tag individually via traditional USRP.Since Buettner et al.propose a Software Defined Ra- tag inventory.In the continuous polling phase,the RFID reader dio based UHF-RFID reader [14],several researchers further continuously issues multiple query cycles to interrogate the leverage this platform to deal with the collision problems tags.For each polling cycle,the RFID reader measures a new [7-9,15].Wang et al.[7]implement a new scheme which distribution of physical-layer features via both the singleton enables rateless code transmitting.[8,9]use the time-domain and collision slots.By matching the updated distributions to separation to recovery the data from the collision signals.Hou the original distributions,our solution is able to efficiently et al.[13]present a physical-layer cardinality estimator from detect the moving tags.The above two phases are executed the collision signals for large scale RFID system. alternately,and the time overhead of the tag inventory phase Physical Layer Identification Previous studies [16,17]focus can be amortized by the following multiple polling cycles, on physical-layer identification by leveraging the hardware im- such that the overall time-efficiency is achieved. perfection in tag manufacturing.Davide et al.[16]distinguish There are three key technical challenges.The first challenge from different tags based on the frequency difference orE is to achieve real-time time efficiency in large scale RFID caused by manufacturing imperfection of tags.Han et al.[18] systems.In a large scale RFID system,it is rather difficult to leverage the internal similarity among pulses of tags'RN16 continuously update the monitoring results within limited time preamble signals as the fingerprint for distinguishing.Zheng intervals.To address this challenge,we propose a two-phase et al.[10]employ a method to detect the missing tags based monitoring scheme including a normal tag inventory phase on physical-layer signals. and multiple fast tag polling phases,we significantly improve Different from previous work,in this paper,we focus on the time efficiency in extracting the physical-layer features via how to design a real-time tag monitoring scheme to efficiently decoding the tag collisions.The second challenge is to detect detect the motion status of all tags,so as to further support the motion status of all tags via the physical-layer features. tracking the movement of all tags.We aim to improve both To address this challenge,we exploit the relationship between the time efficiency in tag inventory and the accuracy in detect the physical-layer features and the motion status of tags.We the motion status of all tags. find that the phase value from the tag's response changes even if the specified tag is moved with a small distance, III.SYSTEM OVERVIEW while the backscatter link frequency of the tag's response A.Design Goals has high degree of distinction among different tags.We thus In this paper,we propose a real-time approach to detect leverage these physical-layer features to detect the motion the motion status of all tags in the monitoring area,so as to status of specified tags.The third challenge is to extract the further support tracking the movement of all tags.Because above physical-layer features from the collisions of multiple the tags may change their motion status any time,we need tag responses.To address this challenge,we recover each tag to continuously update the motion status within a limited response according to the geometrical characteristic of the time interval.Therefore,our objective in designing a moving collision signals in I-Q plane,and extract the phase profile tag detection scheme is to improve both the time efficiency of each tag response.Further,we refer to special patterns to in tag inventory and the accuracy in detecting the motion identify the starting and ending parts of recovered RF signals status of all tags.1)The average time for each cycle of tag based on cross-correlation,and extract the backscatter link inventory should be sufficiently reduced to achieve the real- frequency from the signal length of each tag. time requirement for large scale RFID systems.2)There are We make three contributions in this paper.First,to the two kinds of errors in the problem:a)False positive errors:the best of our knowledge,we are the first to propose a moving stationary tags are identified as moving tags.b)False negative tag detection scheme for tag monitoring by leveraging the errors:the moving tags are identified as stationary tags.Both physical-layer features,which is a fundamental premise for of the two errors should be effectively reduced in detecting tracking the movement of RFID tags in large-scale RFID the motion status. systems.Second,our solution is able to accurately detect the motion status of all tags,by referring to the physical-layer B.System Framework features,including the phase profile and backscatter link fre- In order to effectively detect the motion status of all tags, quency.Moreover,we extract these physical-layer features of we exploit the relationship between the physical-layer features multiple tags from collision slots,which significantly improves and the motion status of tags.The following two physical- the time efficiency.Third,we implemented a prototype system layer features are investigated:1)Phase profile:it is the phase and evaluated its performance in realistic settings.Experiment value of an RF signal.The phase value from the tag's response result shows that our solution can accurately detect the moving changes even if the tag is moved with a small distance.2) tags while reducing 80%of inventory time compared with state Backscatter link frequency (BLF):it is the frequency of the of arts solutions. tag-to-reader link,which determines the tag's data rate in

status of multiple tags simultaneously, and greatly improve the time-efficiency. Specifically, we propose a two-phase tag monitoring scheme including the tag inventory and continuous polling. In the tag inventory phase, the RFID reader constructs a physical fingerprint for each tag individually via traditional tag inventory. In the continuous polling phase, the RFID reader continuously issues multiple query cycles to interrogate the tags. For each polling cycle, the RFID reader measures a new distribution of physical-layer features via both the singleton and collision slots. By matching the updated distributions to the original distributions, our solution is able to efficiently detect the moving tags. The above two phases are executed alternately, and the time overhead of the tag inventory phase can be amortized by the following multiple polling cycles, such that the overall time-efficiency is achieved. There are three key technical challenges. The first challenge is to achieve real-time time efficiency in large scale RFID systems. In a large scale RFID system, it is rather difficult to continuously update the monitoring results within limited time intervals. To address this challenge, we propose a two-phase monitoring scheme including a normal tag inventory phase and multiple fast tag polling phases, we significantly improve the time efficiency in extracting the physical-layer features via decoding the tag collisions. The second challenge is to detect the motion status of all tags via the physical-layer features. To address this challenge, we exploit the relationship between the physical-layer features and the motion status of tags. We find that the phase value from the tag’s response changes even if the specified tag is moved with a small distance, while the backscatter link frequency of the tag’s response has high degree of distinction among different tags. We thus leverage these physical-layer features to detect the motion status of specified tags. The third challenge is to extract the above physical-layer features from the collisions of multiple tag responses. To address this challenge, we recover each tag response according to the geometrical characteristic of the collision signals in I-Q plane, and extract the phase profile of each tag response. Further, we refer to special patterns to identify the starting and ending parts of recovered RF signals based on cross-correlation, and extract the backscatter link frequency from the signal length of each tag. We make three contributions in this paper. First, to the best of our knowledge, we are the first to propose a moving tag detection scheme for tag monitoring by leveraging the physical-layer features, which is a fundamental premise for tracking the movement of RFID tags in large-scale RFID systems. Second, our solution is able to accurately detect the motion status of all tags, by referring to the physical-layer features, including the phase profile and backscatter link fre￾quency. Moreover, we extract these physical-layer features of multiple tags from collision slots, which significantly improves the time efficiency. Third, we implemented a prototype system and evaluated its performance in realistic settings. Experiment result shows that our solution can accurately detect the moving tags while reducing 80% of inventory time compared with state of arts solutions. II. RELATED WORKS Collision Recovery Many works focus on how to extract tag cardinality [13] or recover the tag signal [8, 9] from the collision signals based on the specialized instruments like USRP. Since Buettner et al. propose a Software Defined Ra￾dio based UHF-RFID reader [14], several researchers further leverage this platform to deal with the collision problems [7–9, 15]. Wang et al. [7] implement a new scheme which enables rateless code transmitting. [8, 9] use the time-domain separation to recovery the data from the collision signals. Hou et al. [13] present a physical-layer cardinality estimator from the collision signals for large scale RFID system. Physical Layer Identification Previous studies [16, 17] focus on physical-layer identification by leveraging the hardware im￾perfection in tag manufacturing. Davide et al.[16] distinguish from different tags based on the frequency difference ∂TIE caused by manufacturing imperfection of tags. Han et al. [18] leverage the internal similarity among pulses of tags’ RN16 preamble signals as the fingerprint for distinguishing. Zheng et al. [10] employ a method to detect the missing tags based on physical-layer signals. Different from previous work, in this paper, we focus on how to design a real-time tag monitoring scheme to efficiently detect the motion status of all tags, so as to further support tracking the movement of all tags. We aim to improve both the time efficiency in tag inventory and the accuracy in detect the motion status of all tags. III. SYSTEM OVERVIEW A. Design Goals In this paper, we propose a real-time approach to detect the motion status of all tags in the monitoring area, so as to further support tracking the movement of all tags. Because the tags may change their motion status any time, we need to continuously update the motion status within a limited time interval. Therefore, our objective in designing a moving tag detection scheme is to improve both the time efficiency in tag inventory and the accuracy in detecting the motion status of all tags. 1) The average time for each cycle of tag inventory should be sufficiently reduced to achieve the real￾time requirement for large scale RFID systems. 2) There are two kinds of errors in the problem: a) False positive errors: the stationary tags are identified as moving tags. b) False negative errors: the moving tags are identified as stationary tags. Both of the two errors should be effectively reduced in detecting the motion status. B. System Framework In order to effectively detect the motion status of all tags, we exploit the relationship between the physical-layer features and the motion status of tags. The following two physical￾layer features are investigated: 1) Phase profile: it is the phase value of an RF signal. The phase value from the tag’s response changes even if the tag is moved with a small distance. 2) Backscatter link frequency (BLF): it is the frequency of the tag-to-reader link, which determines the tag’s data rate in

the response signal.Due to manufacturing imperfection,BLF and wireless environment can be regarded unchanged.So we varies among different tags.Therefore,it is suitable to combine can extract the physical-layer feature directly from the RN16 the two features to detect the motion status of tags.Moreover, and omit the EPC-ID signal. we recover each tag response according to the geometrical 800 JQUERY ACK characteristic of the collision signals in I-Q plane,and extract the aforementioned physical-layer features. EPCID Tag inventory phase Extract Features Physical-layer Fingerprints 10 15 Tag Signal Time(ms) nnnnnnAn BLF Fig.2:A typical singleton slot in RFID systems Continuous pooling B.Phase Profile Collision Signal In RFID systems,the tag transmits data using backscattering modulation.Hence,the received signal of one tag is: Fig.1:System framework y(t)=(A1+r(t)A2·cos(2πfit+8))-cos(2πfet+B)+n(t) (1) As for detecting the motion status of tags,we propose a where A1·cos(2πfct+B)is the signal of carrier,.x(t)A2· two-phase monitoring scheme,including the tag inventory and cos(2πfit+a)·cos(2πfet+)is the signal of tag and n(t) continuous polling phase,to efficiently extract the physical- is the ambient noise.Here,x(t)is the binary bits sent by the layer features for detection.In the tag inventory phase,the tag.After converting the signal to baseband by the removing reader issues multiple query cycles to extract the physical-layer carrier cos(2mfet),the baseband signal can be represented as: features of all the tags in stationary status.In the continuous polling phase,the reader continuously issues multiple query s(t)=Ajei+(t)Azei()+i(t).(2) cycles to extract physical-layer features of tags in real-time.By Therefore,the actual received signal is a superposition of comparing the real-time features with the stationary features, carrier wave and backscattered signal. we utilize a Graph Matching Method (GMM)to detect the Intuitively,we can model the received signal from a single motion status of tags in every query cycle of continuous tag response in I-Q plane as shown in Fig.3.The received polling phase.The continuous polling phase contains multiple signal consists of two parts:1)leakage signal:the constant real-time query cycles to amortize the time spent in the carrier signal (i.e.,CW),2)backscattered signal:the modu- inventory phase.We show the whole framework in Fig.1. lated tag signal.As for the phase value of the backscattered signal,it can be represented as: IV.PHYSICAL-LAYER FEATURES In this section,we demonstrate the concept of our physical- 0=Φ-6. (3) layer features via realistic experiments.We implement a which is the difference between the carrier signal phase B and software defined reader (SDR reader)according to the Gen2 the backscattered signal phase in Fig.3.We call the phase project [14].Specifically,we operate the Gen2 project on profile of the tag in this work. our USRP platform with two FLEX-900 daughter boards and two Larid S9028 antennas on each board for transmitting and Backscattere receiving respectively.For the receiving module,we set the signal sampling rate to 2MHz,which represents 0.5us per sample. Leakage A.The Response of a Normal Singleton Slot Fig.2 illustrates a typical slot in RFID systems,which is collected from USRP.The reader sends a QUERY/QRep Fig.3:Model of the received signal of a single tag command to start a slot.All the tags that select this slot, We carry out trace-driven evaluations to study the property will transmit its RN16 to the reader.If the reader succeeds in of the phase profile.Firstly,we evaluate the stability by decoding the RN16 bits,it then sends an ACK to the tag,that conducting an empirical experiments on 50 tags with random tells the tag to transmit its EPC-ID.During the tag response, deployments.For each setting,we measure 100 phase values the reader keeps transmitting continuous wave(CW)to supply by querying each tag 100 times.The results are normalized power.Hence,there are two kinds of tag response generally:1) by subtracting the average phase value of each result set.As RN16 period,responding the QUERY or QRep command from shown in Fig.4(a),the phase profile varies from-5 to 5 the reader,2)EPC-ID period,answering the ACK command. following a typical Gaussian distribution.So we can treat the In fact,both the RN16 signal and the EPC-ID signal contain phase profile as a stable feature for motion detection. preamble,data bits and check bits.As a result,the time of Secondly,we compare the phase profile of SDR reader with the EPC-ID period is about 4 times longer than that of the the phase value of commercial reader(ImpinjR420)by issuing RN16 period as shown in Fig.2.Meanwhile,since the time the same tag.We vary the distance between the antenna and the interval between the two responses is so small,the position tag,which ranges from 20cm to 70cm stepping by 1cm.For

the response signal. Due to manufacturing imperfection, BLF varies among different tags. Therefore, it is suitable to combine the two features to detect the motion status of tags. Moreover, we recover each tag response according to the geometrical characteristic of the collision signals in I-Q plane, and extract the aforementioned physical-layer features. !"#$%&'(&)*+,$ -."/( !"#$%&#'"( 0*&)%&1*1/$-**2%&#$ -."/( )*((&+&*'$%&#'"( ,-./"0.$$12".3/2+ ,-./"0.$12".3/2+ 45"+2 671 8/"95$:".05&'#$;"+2+&0"(?(">2/$ 1&'#2/9/&'.+ Fig. 1: System framework As for detecting the motion status of tags, we propose a two-phase monitoring scheme, including the tag inventory and continuous polling phase, to efficiently extract the physical￾layer features for detection. In the tag inventory phase, the reader issues multiple query cycles to extract the physical-layer features of all the tags in stationary status. In the continuous polling phase, the reader continuously issues multiple query cycles to extract physical-layer features of tags in real-time. By comparing the real-time features with the stationary features, we utilize a Graph Matching Method (GMM) to detect the motion status of tags in every query cycle of continuous polling phase. The continuous polling phase contains multiple real-time query cycles to amortize the time spent in the inventory phase. We show the whole framework in Fig. 1. IV. PHYSICAL-LAYER FEATURES In this section, we demonstrate the concept of our physical￾layer features via realistic experiments. We implement a software defined reader (SDR reader) according to the Gen2 project [14]. Specifically, we operate the Gen2 project on our USRP platform with two FLEX-900 daughter boards and two Larid S9028 antennas on each board for transmitting and receiving respectively. For the receiving module, we set the sampling rate to 2MHz, which represents 0.5µs per sample. A. The Response of a Normal Singleton Slot Fig. 2 illustrates a typical slot in RFID systems, which is collected from USRP. The reader sends a QUERY/QRep command to start a slot. All the tags that select this slot, will transmit its RN16 to the reader. If the reader succeeds in decoding the RN16 bits, it then sends an ACK to the tag, that tells the tag to transmit its EPC-ID. During the tag response, the reader keeps transmitting continuous wave (CW) to supply power. Hence, there are two kinds of tag response generally: 1) RN16 period, responding the QUERY or QRep command from the reader, 2) EPC-ID period, answering the ACK command. In fact, both the RN16 signal and the EPC-ID signal contain preamble, data bits and check bits. As a result, the time of the EPC-ID period is about 4 times longer than that of the RN16 period as shown in Fig. 2. Meanwhile, since the time interval between the two responses is so small, the position and wireless environment can be regarded unchanged. So we can extract the physical-layer feature directly from the RN16 and omit the EPC-ID signal. !"#$% $&'( )*+ #,*-. /////////01234256 ///////7 ////'8 ////'7 )29:1;<=3 Fig. 2: A typical singleton slot in RFID systems B. Phase Profile In RFID systems, the tag transmits data using backscattering modulation. Hence, the received signal of one tag is: y(t)=(A1 +x(t)A2 · cos(2πflt+θ))· cos(2πfct+β) +n(t), (1) where A1 · cos(2πfct + β) is the signal of carrier, x(t)A2 · cos(2πflt + θ) · cos(2πfct + β) is the signal of tag and n(t) is the ambient noise. Here, x(t) is the binary bits sent by the tag. After converting the signal to baseband by the removing carrier cos(2πfct), the baseband signal can be represented as: s(t) = A1ejβ + x(t)A2ej(2πfl t+θ+β) + ˆn(t). (2) Therefore, the actual received signal is a superposition of carrier wave and backscattered signal. Intuitively, we can model the received signal from a single tag response in I-Q plane as shown in Fig. 3. The received signal consists of two parts: 1) leakage signal: the constant carrier signal (i.e., CW), 2) backscattered signal: the modu￾lated tag signal. As for the phase value of the backscattered signal, it can be represented as: θ = Φ − β, (3) which is the difference between the carrier signal phase β and the backscattered signal phase Φ in Fig. 3. We call θ the phase profile of the tag in this work. ! " #$%&%'$( )*'+%,  -%.&).%//$0$1( )*'+%,    Fig. 3: Model of the received signal of a single tag We carry out trace-driven evaluations to study the property of the phase profile. Firstly, we evaluate the stability by conducting an empirical experiments on 50 tags with random deployments. For each setting, we measure 100 phase values by querying each tag 100 times. The results are normalized by subtracting the average phase value of each result set. As shown in Fig. 4(a), the phase profile varies from −5◦ to 5◦, following a typical Gaussian distribution. So we can treat the phase profile as a stable feature for motion detection. Secondly, we compare the phase profile of SDR reader with the phase value of commercial reader (Impinj R420) by issuing the same tag. We vary the distance between the antenna and the tag, which ranges from 20cm to 70cm stepping by 1cm. For

to 7690.This indicates that the signal length can be used to distinguish among tags.Furthermore,we draw the histogram of the normalized variance of signal length in Fig.6(b).The 0.2 signal length is relatively stable with an average deviation of 2 samples,which is equal to lus.Therefore,BLF is stable and 10 (a)The distinctive even though they are at different positions.But there the extracted (b)Comp arison of hase between phase profile commercial reader and SDR reader are also some tags with the same BLF value which means we need to combine it with other attributes. Fig.4:Evaluation of the distinctiveness of the phase profile 770 1500 each step we measure 100 phase values individually.As shown in Fig.4(b),the phase profile of SDR reader is almost the same as the phase value of commercial reader,where the correlation coefficients calculated on MATLAB is 0.9979.As shown in this figure,the phase profile is sensitive to any tiny movements, 20 e.g.,Icm movement,which guarantees the distinctiveness in (a) The distribution of the signal (b)Histogram of of sig- motion detection. length of different tags nal length C.Backscattered Link Frequency Fig.6:Evaluation of the distinctiveness of BLF Due to manufacturing imperfection,the backscatter link V.EXTRACT PHYSICAL-LAYER FEATURES frequency (BLF)of the response signal,i.e.,f in Eg.(1). In the previous section,we have demonstrated the physical- varies among different tags.Thus,it can be used to distinguish layer features in the singleton slots.We can collect the tags as in [16,18].In fact,f determines the length of a square physical-layer features in these singleton slots in the tag wave,i.e.,the duration of high/low voltage in Fig.5(a).In inventory phase.However,it is still time inefficiency because regard to the typical modulation schemes in RFID systems, we cannot avoid useless collisions in RFID system.If c tags i.e.,FMO and Miller Modulation.data-0 and data-1 share the same amount of square waves.Taking Miller-4 Modulation select the same slot to transmit the data,a c collision happens. When N tags select slots randomly from a frame with f slots as an example,both data-0 and data-1 contain eight square according to the Binomial distribution,the probability of a waves as shown in Fig.5(a).Since the length of RN16 signal c-collision slot can be expressed as: is fixed,it is reasonable to use the corresponding signal length of RN16 to represent BLF.The signal length of RN16 can be (4) also transmitted to the BLF based on the actual sampling rate. Pr(c)= Example of preamble 6T11 01101111 Ending of RN16 风 (a)The preamble and (b)Cross-correlation between measured sam- 0 44 ending of RN16 signal ples and theoretical preamble Number of tags in one slot Fig.5:Calculate the signal length through cross-correlation Fig.7:Theoretical probability of collision slots We use the cross-correlation technology to extract the signal Fig.7 shows the theoretical probability distribution of length by locating the starting and ending point of RN16 collision slot.The C1G2 standard improves the time efficiency by maximizing Pr(1),thus at most 36.8%slots are singleton signal.Specifically,we adopt a slide window to calculate In this case,2-collision and 3-collision slots occupy 18.4%and the cross-correlation value between the measured samples in the window and the special data sequence as shown in Fig. 6.13%slots respectively,while only 1.89%slots are remained 5(b).Then we find the window whose cross-correlation value in 4+-collisions.So if we can efficiently resolve all the tags in singleton,2-collision and 3-collision slots,we can identify is the maximum,and record the position of the window.In this example,we locate the starting point of RN16 based on 92%tags in a frame,which is 2.5 times compared with current the special preamble sequence.Similarly we can locate the protocol.Hence,we focus on how to extract physical-layer ending point using"dummy 1".We use the number of samples features from 2-collision and 3-collision slots between the starting and the ending point to represent BLF. A.Model of Collision Signal To validate the distinctiveness of BLF,we conduct experi- Based on Eq.(2),the received baseband signal of a c- ments on 50 different tags at 9 random positions in front of the collision slot can be expressed as: antennas.We repeat querying each tag 100 times to extract the signal lengths in different positions.As shown in Fig.6(a),the s(t)=Aei+;(t)hi+(t) (5) signal length of 50 tags are randomly distributed from 7620 =1

Phase variation(degree) -10 -5 0 5 10 CDF 0 0.2 0.4 0.6 0.8 1 (a) The variance of the extracted phase profile Transmitting distance(cm) 20 40 60 80 100 Phase value(degree) 0 100 200 300 400 Phase of SDR reader Phase of impinj reader (b) Comparison of phase between commercial reader and SDR reader Fig. 4: Evaluation of the distinctiveness of the phase profile each step we measure 100 phase values individually. As shown in Fig. 4(b), the phase profile of SDR reader is almost the same as the phase value of commercial reader, where the correlation coefficients calculated on MATLAB is 0.9979. As shown in this figure, the phase profile is sensitive to any tiny movements, e.g., 1cm movement, which guarantees the distinctiveness in motion detection. C. Backscattered Link Frequency Due to manufacturing imperfection, the backscatter link frequency (BLF) of the response signal, i.e., fl in Eq. (1), varies among different tags. Thus, it can be used to distinguish tags as in [16, 18]. In fact, fl determines the length of a square wave, i.e., the duration of high/low voltage in Fig. 5(a). In regard to the typical modulation schemes in RFID systems, i.e., FM0 and Miller Modulation, data-0 and data-1 share the same amount of square waves. Taking Miller-4 Modulation as an example, both data-0 and data-1 contain eight square waves as shown in Fig. 5(a). Since the length of RN16 signal is fixed, it is reasonable to use the corresponding signal length of RN16 to represent BLF. The signal length of RN16 can be also transmitted to the BLF based on the actual sampling rate. 1 0 dummy 1 dummy 1 0 1 0 1 1 1 Example of preamble Ending of RN16 (a) The preamble and ending of RN16 signal 1 0 1 1 1 Slide window Cross correlation (b) Cross-correlation between measured sam￾ples and theoretical preamble Fig. 5: Calculate the signal length through cross-correlation We use the cross-correlation technology to extract the signal length by locating the starting and ending point of RN16 signal. Specifically, we adopt a slide window to calculate the cross-correlation value between the measured samples in the window and the special data sequence as shown in Fig. 5(b). Then we find the window whose cross-correlation value is the maximum, and record the position of the window. In this example, we locate the starting point of RN16 based on the special preamble sequence. Similarly we can locate the ending point using “dummy 1”. We use the number of samples between the starting and the ending point to represent BLF. To validate the distinctiveness of BLF, we conduct experi￾ments on 50 different tags at 9 random positions in front of the antennas. We repeat querying each tag 100 times to extract the signal lengths in different positions. As shown in Fig. 6(a), the signal length of 50 tags are randomly distributed from 7620 to 7690. This indicates that the signal length can be used to distinguish among tags. Furthermore, we draw the histogram of the normalized variance of signal length in Fig. 6(b). The signal length is relatively stable with an average deviation of 2 samples, which is equal to 1µs. Therefore, BLF is stable and distinctive even though they are at different positions. But there are also some tags with the same BLF value which means we need to combine it with other attributes. Tag counts 0 10 20 30 40 50 Signal length 7600 7620 7640 7660 7680 7700 (a) The distribution of the signal length of different tags Signal length deviation -10 -5 0 5 10 Counts 0 5000 10000 15000 (b) Histogram of the variance of sig￾nal length Fig. 6: Evaluation of the distinctiveness of BLF V. EXTRACT PHYSICAL-LAYER FEATURES In the previous section, we have demonstrated the physical￾layer features in the singleton slots. We can collect the physical-layer features in these singleton slots in the tag inventory phase. However, it is still time inefficiency because we cannot avoid useless collisions in RFID system. If c tags select the same slot to transmit the data, a c collision happens. When N tags select slots randomly from a frame with f slots according to the Binomial distribution, the probability of a c-collision slot can be expressed as: P r(c) = Ç N c å Å 1 f ãc Å 1 − 1 f ãN−c . (4) Number of tags in one slot 0 1 2 3 4+ f/N 0 1 2 3 4 5 0 0.2 0.4 0.6 0.8 Fig. 7: Theoretical probability of collision slots Fig. 7 shows the theoretical probability distribution of collision slot. The C1G2 standard improves the time efficiency by maximizing P r(1), thus at most 36.8% slots are singleton. In this case, 2-collision and 3-collision slots occupy 18.4% and 6.13% slots respectively, while only 1.89% slots are remained in 4+-collisions. So if we can efficiently resolve all the tags in singleton, 2-collision and 3-collision slots, we can identify 92% tags in a frame, which is 2.5 times compared with current protocol. Hence, we focus on how to extract physical-layer features from 2-collision and 3-collision slots. A. Model of Collision Signal Based on Eq. (2), the received baseband signal of a c￾collision slot can be expressed as: s(t) = Aejβ +!c i=1 xi(t)hi + ˆn(t). (5)

S2 I S 200 Tag BO Leakage signal 00 10001500 200 0 0 ample time (us) (a)Model of a 2-collision slot in (b)The preamble of a 2-collision sig- (c)Case I for 3-collision signal in (d)Case 2 for 3-collision signal I-Q plane I-Q plane in I-Q plane Fig.8:Model of collision signal Here,i(t)is the binary bits sent by tag i over time t.hi is are transmitting the same data during the preamble,signals the channel coefficient of tag i and can be written as: are switching between state So and Sa during the preamble hi Biei(2ft+0+B)) as shown in Fig.8(b).Therefore,we can determine the (6) state S3 using the preamble part.Hence,the remained two where B;is the amplitude and 0;is the phase profile of tag i. states are S and S2 respectively.At last,we calculate the Actually,hi represents a vector in I-Q plane,thus the collided channel coefficients of each tag as h=C(S1)-C(So)and signal can be represented as the superposition of the vectors. h2 =C(S2)-C(So),where C(Si)is Si in the I-Q plane. Taking a 2-collision as an example in Fig.8(a),since both 2)Channel Coefficients Estimation for 3-collision Slot: tag A and B send a binary bit,we can use four different states When the number of collided tags increases to three,the signal So~S3 in I-Q plane to represent the two binary bits.State So states can be represented with a three-bit binary.This means means both tag A and B are transmitting i(t)=0,therefore there are 8 states,which is much more complex,because we the signal contains only one component:the leakage signal. need to define 4 more states compared to 2-collision problem. State S3 means both tag A and B are transmitting xi(t)=1, Based on the combination of signal vectors in I-Q plane,the 8 therefore the signal is superposition of the three vectors.For states constitute a parallelepiped.Our basic idea is that since 3- state S1 and S2,only one tag is transmitting bit 1,therefore collision signal can be always represented as the superposition the signal is the combination of the leakage signal and the of 2-collision signal and one tag signal,we can find and backscattered signal of the corresponding tag. resolve a 2-collision problem inside the 3-collision problem and then handle the 3rd tag signal.For example,parallelogram B.Recover Signal States from Collision Slots SoS2SS4 and S1S3S7Ss in Fig.8(c)are the superposition of Based on the above model,the combination of the signal two tags and the vector pointing from one parallelogram to vectors constitute different states in I-Q plane,which repre- another represents the signal of the 3rd tag.By resolving one sents different binary bits sent by the collided tags.Hence, parallelogram,we can get the channel coefficients of two tags the key step to extract features from collision signal is to and further calculate the coefficients of the 3rd tag. resolve the signal states.Firstly,we need to find out which To find the parallelogram in the parallelepiped,we divide combination of binary bits each state represents.Secondly, the states into two parts according to their ranks of amplitude. we calculate the channel coefficient h;of each tag using the Due to the geometric feature,the four states with smaller positions of states.Lastly,for each sample s(t)we estimate amplitudes can either constitute a parallelogram as shown in the binary bits i(t)of tag i according to Eq.(5)as: Fig.8(c),or a plane tetrahedron as shown in Fig.8(d).For the parallelogram case,we have found the parallelogram such as arg min s(t)- (:(t).h)-Arel,where i(t)=0or 1. Fig.8(c).For the plane tetrahedron case,the edges among the four states inside the parallelepiped intersect at one state,e.g., (7) in Fig.8(d)three vectors intersect at S2.For this situation.we Eq.(7)chooses the combination of zi(t).such that the error can exchange one of the other three states with a symmetrical between the sample s(t)and the generated collided signal,i.e..state,e.g.,replacing S3 with S4 in Fig.8(d),to constitute a ∑=1(xi(t)-h:）is minimized. parallelogram.Then,we will find the parallelogram so as to 1)Channel Coefficients Estimation for 2-collision Slot: further extract the channel coefficients. According to the above analysis,a 2-collision slot contains The detailed steps for estimating the channel coefficients in four states,which is the size of two-bit binary.When we get 3-collision slot are as follows:Firstly,we cluster signals into the collision signals,we first acquire the positions of each state 8 clusters,similar as in the 2-collision problem.Secondly,we by clustering all the samples into clusters based on the sample determine state So and S7 from the preamble,because all the distribution in I-Q plane.Then we pick the peaks of density three tags transmit the same data and signal switches between function as the centers of clusters as in [13]. state So and S7.Here,So means all the three tags transmit After clustering,we will get four cluster centers,which xi(t)=0 and S7 means xi(t)=1. represent four states similar to Fig.8(a).As So only contains Thirdly,we search for the parallelogram in the paral- the leakage signal which can be estimated from the continuous lelepiped.We sort the eight states based on the amplitudes of wave,we can first determine the state So.Since both tags cluster centers.Based on the analysis above,then we search

I Q Leakage signal Tag A Tag B S0 S3 S1 S2 (a) Model of a 2-collision slot in I-Q plane Sample # 1000 2000 3000 4000 Magnitude 6000 6200 6400 Sample time (µs) 500 1000 1500 2000 Amplitude S0 S3 S0 S3 (b) The preamble of a 2-collision sig￾nal S1 S0 S2 S3 S4 S5 S6 S7 I Q O (c) Case 1 for 3-collision signal in I-Q plane S1 S0 S2 S3 S4 S5 S6 S7 I Q O (d) Case 2 for 3-collision signal in I-Q plane Fig. 8: Model of collision signal Here, xi(t) is the binary bits sent by tag i over time t. hi is the channel coefficient of tag i and can be written as: hi = Biej(2πfl t+θi+β)), (6) where Bi is the amplitude and θi is the phase profile of tag i. Actually, hi represents a vector in I-Q plane, thus the collided signal can be represented as the superposition of the vectors. Taking a 2-collision as an example in Fig. 8(a), since both tag A and B send a binary bit, we can use four different states S0 ∼ S3 in I-Q plane to represent the two binary bits. State S0 means both tag A and B are transmitting xi(t)=0, therefore the signal contains only one component: the leakage signal. State S3 means both tag A and B are transmitting xi(t)=1, therefore the signal is superposition of the three vectors. For state S1 and S2, only one tag is transmitting bit 1, therefore the signal is the combination of the leakage signal and the backscattered signal of the corresponding tag. B. Recover Signal States from Collision Slots Based on the above model, the combination of the signal vectors constitute different states in I-Q plane, which repre￾sents different binary bits sent by the collided tags. Hence, the key step to extract features from collision signal is to resolve the signal states. Firstly, we need to find out which combination of binary bits each state represents. Secondly, we calculate the channel coefficient hi of each tag using the positions of states. Lastly, for each sample s(t) we estimate the binary bits xi(t) of tag i according to Eq. (5) as: arg minx |s(t) −!c i=1 (xi(t) · hi) − A1ejβ|, where xi(t)=0 or 1. (7) Eq. (7) chooses the combination of xi(t), such that the error between the sample " s(t) and the generated collided signal, i.e., c i=1(xi(t) · hi) is minimized. 1) Channel Coefficients Estimation for 2-collision Slot: According to the above analysis, a 2-collision slot contains four states, which is the size of two-bit binary. When we get the collision signals, we first acquire the positions of each state by clustering all the samples into clusters based on the sample distribution in I-Q plane. Then we pick the peaks of density function as the centers of clusters as in [13]. After clustering, we will get four cluster centers, which represent four states similar to Fig. 8(a). As S0 only contains the leakage signal which can be estimated from the continuous wave, we can first determine the state S0. Since both tags are transmitting the same data during the preamble, signals are switching between state S0 and S3 during the preamble as shown in Fig. 8(b). Therefore, we can determine the state S3 using the preamble part. Hence, the remained two states are S1 and S2 respectively. At last, we calculate the channel coefficients of each tag as h1 = C(S1) − C(S0) and h2 = C(S2) − C(S0), where C(Si) is Si in the I-Q plane. 2) Channel Coefficients Estimation for 3-collision Slot: When the number of collided tags increases to three, the signal states can be represented with a three-bit binary. This means there are 8 states, which is much more complex, because we need to define 4 more states compared to 2-collision problem. Based on the combination of signal vectors in I-Q plane, the 8 states constitute a parallelepiped. Our basic idea is that since 3- collision signal can be always represented as the superposition of 2-collision signal and one tag signal, we can find and resolve a 2-collision problem inside the 3-collision problem and then handle the 3rd tag signal. For example, parallelogram S0S2S6S4 and S1S3S7S5 in Fig. 8(c) are the superposition of two tags and the vector pointing from one parallelogram to another represents the signal of the 3rd tag. By resolving one parallelogram, we can get the channel coefficients of two tags and further calculate the coefficients of the 3rd tag. To find the parallelogram in the parallelepiped, we divide the states into two parts according to their ranks of amplitude. Due to the geometric feature, the four states with smaller amplitudes can either constitute a parallelogram as shown in Fig. 8(c), or a plane tetrahedron as shown in Fig. 8(d). For the parallelogram case, we have found the parallelogram such as Fig. 8(c). For the plane tetrahedron case, the edges among the four states inside the parallelepiped intersect at one state, e.g., in Fig. 8(d) three vectors intersect at S2. For this situation, we can exchange one of the other three states with a symmetrical state, e.g., replacing S3 with S4 in Fig. 8(d), to constitute a parallelogram. Then, we will find the parallelogram so as to further extract the channel coefficients. The detailed steps for estimating the channel coefficients in 3-collision slot are as follows: Firstly, we cluster signals into 8 clusters, similar as in the 2-collision problem. Secondly, we determine state S0 and S7 from the preamble, because all the three tags transmit the same data and signal switches between state S0 and S7. Here, S0 means all the three tags transmit xi(t)=0 and S7 means xi(t)=1. Thirdly, we search for the parallelogram in the paral￾lelepiped. We sort the eight states based on the amplitudes of cluster centers. Based on the analysis above, then we search

-3400 120 0 3600 -3800 81008200 830 -4000 4200 7800 7900800081008200 x30 -4400 hmVI是 102030 40 4500 5000 780079008000810082008300 Grid X Inphase (a)Histogram of signal in I-Q plane (b)Signal in I-Q plane and the state division (C)Extracted R of three tags Fig.9:Extract the physical-layer features from 3-collision signal for the parallelogram among first five states with smaller D.Case Study amplitudes.There are only two possible choices:1)For the Fig.9 is an example of extracting the physical-layer features parallelogram case we can use Ist~4th state to constitute from a 3-collision slot.Firstly,we cluster the samples into a parallelogram.2)For the plane tetrahedron case,we can eight clusters based on the density function in I-Q plane as replace 4th state with 5th and use 1st~3rd and 5th state to shown in Fig.9(a).In the following we denote each state constitute a parallelogram. as the amplitude rank of states in I-Q plane.Secondly,we To decide the correct choice,we leverage the property that determine state So from continuous wave and state S7 from the opposite sides of parallelogram are parallel and equal in the preamble as shown in Fig.9(b).Thirdly,we search for the length.For each choice there are three possible edge pairs. parallelogram based on the first 5 states.The left quadrilateral If we use the rank of state to represent the vertex,the three in Fig.9(b)is the estimated parallelogram from the first 5 pairs are (12,34).(13,24)and (14,23)in choice 1,We use states and the right one is the symmetrical one.Fourthly,we the similarity among the edge pairs to express the likelihood calculate the channel coefficients including the phase profiles of constituting a parallelogram as: as the arrow in the figure.Lastly,we recover the RN16 signal a.b of each tag according to Eq.(7).Here,we use"1"to represent Sim= 1a×阿（园-例 (8)high voltage and"-1"to represent low voltage.We compute the signal length of RN16 as the indicator of BLF based on where (a,b)are the possible edge pair.The first part of Eq(8) cross-correlation values.Fig.9(c)shows the ending part of is the cosine value of the edge pair and the second part is the three separated RN16 signals and points out the slide window reciprocal of the length difference.We choose the edge pair which has the maximum cross-correlation value. with the maximum similarity as the corresponding opposite VI.DETECT THE MOVING TAGS side of the parallelogram.Then we can resolve the vertex A.Motivation and Approaches sequence of the parallelogram based on the similarity. After we extract the phase profiles from the collision signals, Lastly.we measure the channel coefficients based on the we demonstrate how to detect the moving tags by using the geometric construction.The parallelogram will always include phase profiles.Since the phase profile always changes even if either state So or S7 because they are symmetric.Hence,we the tag is moved a small distance,the basic idea is to compare can measure the two channel coefficients in the parallelogram the updated phase profiles with the stationary phase profiles. according to the states So and S7 similar as in the 2-collision Suppose we need to monitor N tags,we obtain the stationary problem.Then the channel coefficient of the 3rd tag can be phase profiles of the N tags in the tag inventory phase.We easily computed based on So,S7 and the first two channel use a vector P =(01,02,...,ON)to represent the phase coefficients,since S7 contains the channel coefficients of three distribution,where is the ith phase profile in distribution tags and So contains none. P.Then in the each cycle of the continuous polling phase,we obtain an updated phase distribution P=(,2,...). C.Measure the Physical-Layer Features from Collision Signal We compare p with P to detect the moving tags in each After extracting the channel coefficients from the collision polling cycle. slot,we can directly compute the phase profile based on Eq. Traditional C1G2 protocol usually costs tens of seconds (3).For backscatter link frequency (BLF),we utilize Eq.(7) to obtain the tag information,which can build the phase to recover the RN16 signal of each tag.It is difficult to decode distribution P'.It is inefficient due to the collision problem these RN16 signals into complete binary sequences due to the and the long EPC-ID signal.Instead,we can extract the phase ambient noise.But according to the special encoded pattern of distribution P'only from the RN16 signal of collision signal preamble and"dummy I"as shown in Fig.5(a),we can decide Hence,we propose a Fast Tag Polling Scheme (FTPS)by the starting and ending point of each RN16 signal using cross- suppressing the transmitting of EPC-ID signal with a new correlation.Here we adopt the same cross-correlation process command OrepSup.The QrepSup command is used to respond as in Section IV-C to decide the signal length.Then we use the RN16 signal of the tags.It not only starts the next slot like the signal length as the indicator of BLF. the Qrep command in C1G2,but also makes the tags,which

Grid X 10 20 30 40 50 Grid Y 10 20 30 40 50 0 20 40 60 80 100 120 (a) Histogram of signal in I-Q plane Inphase 4000 4500 5000 Quadrature -4600 -4400 -4200 -4000 -3800 -3600 -3400 S0 S7 (b) Signal in I-Q plane and the state division Amplitude 7800 7900 8000 8100 8200 8300 -2 0 2 Amplitude 7800 7900 8000 8100 8200 8300 -2 0 2 Sample Counts Amplitude 7800 7900 8000 8100 8200 8300 -2 0 2 (c) Extracted RN16 signals of three tags Fig. 9: Extract the physical-layer features from 3-collision signal for the parallelogram among first five states with smaller amplitudes. There are only two possible choices: 1) For the parallelogram case we can use 1st∼4th state to constitute a parallelogram. 2) For the plane tetrahedron case, we can replace 4th state with 5th and use 1st∼3rd and 5th state to constitute a parallelogram. To decide the correct choice, we leverage the property that the opposite sides of parallelogram are parallel and equal in length. For each choice there are three possible edge pairs. If we use the rank of state to represent the vertex, the three pairs are (ı12, ı34), (ı13, ı24) and (ı14, ı23) in choice 1, We use the similarity among the edge pairs to express the likelihood of constituting a parallelogram as: Sim = # # # # # ⃗a ·⃗b |⃗a| × | ⃗b| × 1 (|⃗a| − | ⃗b|) # # # # # , (8) where (⃗a,⃗b) are the possible edge pair. The first part of Eq(8) is the cosine value of the edge pair and the second part is the reciprocal of the length difference. We choose the edge pair with the maximum similarity as the corresponding opposite side of the parallelogram. Then we can resolve the vertex sequence of the parallelogram based on the similarity. Lastly, we measure the channel coefficients based on the geometric construction. The parallelogram will always include either state S0 or S7 because they are symmetric. Hence, we can measure the two channel coefficients in the parallelogram according to the states S0 and S7 similar as in the 2-collision problem. Then the channel coefficient of the 3rd tag can be easily computed based on S0, S7 and the first two channel coefficients, since S7 contains the channel coefficients of three tags and S0 contains none. C. Measure the Physical-Layer Features from Collision Signal After extracting the channel coefficients from the collision slot, we can directly compute the phase profile based on Eq. (3). For backscatter link frequency (BLF), we utilize Eq. (7) to recover the RN16 signal of each tag. It is difficult to decode these RN16 signals into complete binary sequences due to the ambient noise. But according to the special encoded pattern of preamble and “dummy 1” as shown in Fig. 5(a), we can decide the starting and ending point of each RN16 signal using cross￾correlation. Here we adopt the same cross-correlation process as in Section IV-C to decide the signal length. Then we use the signal length as the indicator of BLF. D. Case Study Fig. 9 is an example of extracting the physical-layer features from a 3-collision slot. Firstly, we cluster the samples into eight clusters based on the density function in I-Q plane as shown in Fig. 9(a). In the following we denote each state as the amplitude rank of states in I-Q plane. Secondly, we determine state S0 from continuous wave and state S7 from the preamble as shown in Fig. 9(b). Thirdly, we search for the parallelogram based on the first 5 states. The left quadrilateral in Fig. 9(b) is the estimated parallelogram from the first 5 states and the right one is the symmetrical one. Fourthly, we calculate the channel coefficients including the phase profiles as the arrow in the figure. Lastly, we recover the RN16 signal of each tag according to Eq.(7). Here, we use “1” to represent high voltage and “-1” to represent low voltage. We compute the signal length of RN16 as the indicator of BLF based on cross-correlation values. Fig. 9(c) shows the ending part of three separated RN16 signals and points out the slide window which has the maximum cross-correlation value. VI. DETECT THE MOVING TAGS A. Motivation and Approaches After we extract the phase profiles from the collision signals, we demonstrate how to detect the moving tags by using the phase profiles. Since the phase profile always changes even if the tag is moved a small distance, the basic idea is to compare the updated phase profiles with the stationary phase profiles. Suppose we need to monitor N tags, we obtain the stationary phase profiles of the N tags in the tag inventory phase. We use a vector P = ⟨θ1, θ2, ··· , θN ⟩ to represent the phase distribution, where θi is the ith phase profile in distribution P. Then in the each cycle of the continuous polling phase, we obtain an updated phase distribution P′ = ⟨θ′ 1, θ′ 2, ··· , θ′ N ⟩. We compare P′ with P to detect the moving tags in each polling cycle. Traditional C1G2 protocol usually costs tens of seconds to obtain the tag information, which can build the phase distribution P′ . It is inefficient due to the collision problem and the long EPC-ID signal. Instead, we can extract the phase distribution P′ only from the RN16 signal of collision signal. Hence, we propose a Fast Tag Polling Scheme (FTPS) by suppressing the transmitting of EPC-ID signal with a new command QrepSup. The QrepSup command is used to respond the RN16 signal of the tags. It not only starts the next slot like the Qrep command in C1G2, but also makes the tags, which

is resolved in the collision slot,silent for the following frames Therefore,the process of constructing the multi-dimensional in the query cycle.On the other hand,all the unidentified tags phase profile consists of two steps:We first try to extract caused by the unresolved collision or environment factors,will the physical-layer features from the receiving signal of each receive the Qrep command and respond in the next frame antenna individually.For singleton slots,we just directly com- similar as C1G2 protocol.Based on FTPS,we can acquire the bine the phase values together to construct a multi-dimensional phase distribution P in a short time in every polling cycle. phase profile.If it is a c-collision slot,we combine the phase B.Construct the Multi-dimensional Phase Profiles profiles received from different antennas by matching the BLFs to construct c multi-dimensional phase profiles. Even though the movements of tags lead to the difference between the two phase distributions P and P,but the phase C.Detect the Moving Tags via Graph Matching profile extracted from one antenna cannot sufficiently detect Based on the two phase distributions P and P,we demon- the moving tags due to the following two reasons:1)The phase strate how to detect the moving tags.The intuition is that for value is periodical,meaning different tags may have the same a stationary tag,its phase profile should be stable.Consid- phase profile.2)Errors of phase measurement will affect the ering the measurement errors,the distance between the two accuracy of detecting the movements. phase profiles from the same tag should be smaller compared Fig.10 shows a simple example.P and P2 are two with the distances from different tags.Here,we denote the stationary phase distributions of five tags T1~T5 measured Euclidean distance dij between the ith phase profile 0 in by two antennas in the tag inventory phase.When tag T3 is distribution P and the jth phase profile in P'as: moved,its phase profiles will change in both Pi and P2.But since T2 has similar phase profile with Ta in P,we cannot di.j =lei-0ll. (9) accurately determine which is the moving tag.Similarly,T For a moving tag,because it has changed its position,the has similar phase profile with T in P2,which makes the distances from other phase profiles should be large in a detection confusing.However,if we can combine the two statistical manner.Suppose k is an empirical threshold about phase profiles of the same tag in P and P2 together,every the phase variance,we can set dij,whose value exceeds tag will have a special phase profile of two phase values.We to oo to filter the parings,which are not the phase pairs of a call it a two-dimensional phase profile.In the figure,we use a stationary tag.So if we can match the phase profiles in the matrix to depict the phase distribution of the two-dimensional two distributions so that the overall sum of distances for these phase profiles.Thus,T3 can be accurately detected because matchings is the minimum among all the possible matchings no tag has similar two-dimensional phase profile as it. then only the stationary tags should be matched,because the P2 910f02770-30 distances of the moving tags are large in statistic. T1797 T11024 0 It is not suitable to enumerate all the possible matchings T2 T11849 T5099 since the complexity is O(n!).So we propose a Graph Match- T41 T489 22 ing Method (GMM)by employing the Hungarian algorithm T98° T2889 [20]to solve the problem in polynomial time.Firstly,we Fig.10:Example of the multi-dimensional phase profile calculate the pairwise distance between distributions P and p In actual applications,we can exploit an SDR reader [19] according to Eq.(9).It is a Nx N matrix DNxN.Secondly, with a transmitting antenna and two receiving antennas to we filter all the unlikely pairs by setting the distance in DNxN. acquire the two distributions P and P2.But it is difficult whose value exceeds K,to oo.Thirdly,we utilize DNxN as to construct a two-dimensional phase profile simply based the input of the Hungarian algorithm and get a matching result on the phase values from two antennas.Suppose tag T1 and Lastly,we pick up all the tags in P,whose phase profiles are T collide in a 2-collision and we have extracted the phase unmatched,as the moving tags. profiles7oand194°from one antenna and192°andl8°from Fig.11 shows an example of the process.We use two gray another antenna.But we cannot determine whether the phase matrices to represent the two distributions P and p of five pair(7,192)belong to the same tag or not,because we do tags from three antennas.And we use dashed lines to represent not have the tag IDs.Obviously,it is not practical to enumerate all the possible pairing schemes and calculate the distances of all the possible matchings when we have more antennas. them.The Hungarian algorithm takes the distances as input To solve the problem,we use the backscatter link frequency and returns the matchings,represented as the solid lines in the (BLF)to match them.Because the two receiving antennas figure.So we can detect the moving tag as unmatched one, receive the same signal in the physical layer,the extracted which is marked with a circle in the figure. BLFs of the same tag from the two antennas should match In this work,the phase profile is the main factor to detect perfectly.Suppose we have also extracted the corresponding the motion status,where the BLF is used to construct the BLF values for each phase profile,then we are more likely to multi-dimensional phase profile.In fact,BLF can further help combine 7 and 192 together because the extracted BLFs of distinguish tags.Since BLF is an inherent feature,it will not tag Ti should be similar from the two receiving antennas.Such be changed by the position.If we add BLF into the distance matching method can be easily extended to multi-dimensional calculation of GMM,we can filter the phase profiles pair, phase profile,where we use multiple receiving antennas. whose phase distance is small but BLF distance is large

is resolved in the collision slot, silent for the following frames in the query cycle. On the other hand, all the unidentified tags, caused by the unresolved collision or environment factors, will receive the Qrep command and respond in the next frame similar as C1G2 protocol. Based on FTPS, we can acquire the phase distribution P′ in a short time in every polling cycle. B. Construct the Multi-dimensional Phase Profiles Even though the movements of tags lead to the difference between the two phase distributions P and P′ , but the phase profile extracted from one antenna cannot sufficiently detect the moving tags due to the following two reasons: 1) The phase value is periodical, meaning different tags may have the same phase profile. 2) Errors of phase measurement will affect the accuracy of detecting the movements. Fig. 10 shows a simple example. P1 and P2 are two stationary phase distributions of five tags T1 ∼ T5 measured by two antennas in the tag inventory phase. When tag T3 is moved, its phase profiles will change in both P1 and P2. But since T2 has similar phase profile with T3 in P1, we cannot accurately determine which is the moving tag. Similarly, T4 has similar phase profile with T3 in P2, which makes the detection confusing. However, if we can combine the two phase profiles of the same tag in P1 and P2 together, every tag will have a special phase profile of two phase values. We call it a two-dimensional phase profile. In the figure, we use a matrix to depict the phase distribution of the two-dimensional phase profiles. Thus, T3 can be accurately detected because no tag has similar two-dimensional phase profile as it. T3 T5 T2 T4 T1 184° 98° 15° T3 T5 194° T4 T2 T1 7° T5 288° 99° T4 T3 T1 18° 192° 98° T2 P1 P2 P1 P2 0°~90° 270°~360° 180°~270° 90°~180° 0°~90° 90°~180° 180°~270° 270°~360° Fig. 10: Example of the multi-dimensional phase profile In actual applications, we can exploit an SDR reader [19] with a transmitting antenna and two receiving antennas to acquire the two distributions P1 and P2. But it is difficult to construct a two-dimensional phase profile simply based on the phase values from two antennas. Suppose tag T1 and T2 collide in a 2-collision and we have extracted the phase profiles 7◦ and 194◦ from one antenna and 192◦ and 18◦ from another antenna. But we cannot determine whether the phase pair ⟨7◦, 192◦⟩ belong to the same tag or not, because we do not have the tag IDs. Obviously, it is not practical to enumerate all the possible matchings when we have more antennas. To solve the problem, we use the backscatter link frequency (BLF) to match them. Because the two receiving antennas receive the same signal in the physical layer, the extracted BLFs of the same tag from the two antennas should match perfectly. Suppose we have also extracted the corresponding BLF values for each phase profile, then we are more likely to combine 7◦ and 192◦ together because the extracted BLFs of tag T1 should be similar from the two receiving antennas. Such matching method can be easily extended to multi-dimensional phase profile, where we use multiple receiving antennas. Therefore, the process of constructing the multi-dimensional phase profile consists of two steps: We first try to extract the physical-layer features from the receiving signal of each antenna individually. For singleton slots, we just directly com￾bine the phase values together to construct a multi-dimensional phase profile. If it is a c-collision slot, we combine the phase profiles received from different antennas by matching the BLFs to construct c multi-dimensional phase profiles. C. Detect the Moving Tags via Graph Matching Based on the two phase distributions P and P′ , we demon￾strate how to detect the moving tags. The intuition is that for a stationary tag, its phase profile should be stable. Consid￾ering the measurement errors, the distance between the two phase profiles from the same tag should be smaller compared with the distances from different tags. Here, we denote the Euclidean distance di,j between the ith phase profile θi in distribution P and the jth phase profile θ′ j in P′ as: di,j = ||θi − θ′ j ||. (9) For a moving tag, because it has changed its position, the distances from other phase profiles should be large in a statistical manner. Suppose κ is an empirical threshold about the phase variance, we can set di,j , whose value exceeds κ, to ∞ to filter the parings, which are not the phase pairs of a stationary tag. So if we can match the phase profiles in the two distributions so that the overall sum of distances for these matchings is the minimum among all the possible matchings, then only the stationary tags should be matched, because the distances of the moving tags are large in statistic. It is not suitable to enumerate all the possible matchings since the complexity is O(n!). So we propose a Graph Match￾ing Method (GMM) by employing the Hungarian algorithm [20] to solve the problem in polynomial time. Firstly, we calculate the pairwise distance between distributions P and P′ according to Eq. (9). It is a N × N matrix DN×N . Secondly, we filter all the unlikely pairs by setting the distance in DN×N , whose value exceeds κ, to ∞. Thirdly, we utilize DN×N as the input of the Hungarian algorithm and get a matching result. Lastly, we pick up all the tags in P, whose phase profiles are unmatched, as the moving tags. Fig. 11 shows an example of the process. We use two gray matrices to represent the two distributions P and P′ of five tags from three antennas. And we use dashed lines to represent all the possible pairing schemes and calculate the distances of them. The Hungarian algorithm takes the distances as input and returns the matchings, represented as the solid lines in the figure. So we can detect the moving tag as unmatched one, which is marked with a circle in the figure. In this work, the phase profile is the main factor to detect the motion status, where the BLF is used to construct the multi-dimensional phase profile. In fact, BLF can further help distinguish tags. Since BLF is an inherent feature, it will not be changed by the position. If we add BLF into the distance calculation of GMM, we can filter the phase profiles pair, whose phase distance is small but BLF distance is large

AI A2 A3 AI A2A3 Moving T Tag receiving antennas are attached on each wall randomly.We deploy the transmitting antenna in the center of room for Stationary Updated simplicity.The phase values are measured according to the Taes Distribution transmitting distance and wavelength.We first extract the Stationary Distribution stationary phase distribution from singleton slot in the tag Fig.11:Matching example inventory phase.Then in continuous polling phase,we extract the real-time phase distribution from singleton and collision VII.PERFORMANCE EVALUATION slots.For every polling cycle,we utilize the Hungarian algo- In the following,we evaluate the performance from three rithm to detect the moving tags. aspects.Firstly,we evaluate the feature extraction scheme In this experiment,we study the effect of the following based on a small scale experiment in the realistic environment parameters on the detection accuracy:phase variance o,num- Then we evaluate GMM solution in terms of the detection ber of moving tags n,number of antennas r and number of accuracy of motion status.Lastly,we compare FTPS and monitoring tagsw.K is set to 2w for simplicity.We utilize false C1G2 standard to evaluate the time efficiency. positive error(FP)and false negative error(FN)to evaluate the accuracy.False positive error means the stationary tags is A.Evaluate the Accuracy in Feature Extraction identified as moving tags,and false negative error means the 1)Experiment Settings:We perform a realistic experiment moving tags is identified as stationary tags. to evaluate the extracted physical-layer features by issuing 50 Because phase values vary in accordance with Gaussian tags.All signal traces are collected with the GNURadio/USRP distribution as evaluated.We import the variances according to platform as described in Section IV.Due to the power limita- the collision type.For singleton slot,a fixed standard deviation tion of USRP for scattering 50 tags,we use a four-step scheme of 4 is used based on the evaluation in Section IV-B.For to collect the realistic signal.Firstly,we emulate the process collision slot,we import parameters o and 2o to denote the of slot selection on MATLAB according to C1G2 standard. standard deviations of 2-collision and 3-collision respectively. Secondly,we collect the responding signal trace for each slot We cannot extracted phase profiles from 4+-collision slots. on the USRP platform according to the result of slot selection. 2)Results:GMM can correctly detect 85%of the moving Thirdly,we extract physical-layer features from singleton and tags with about 6%false positive errors.Fig.12(e)~12(h) collision slots.Lastly,we modify the frame size based on the report the results from different points of views.We note the number of identified tags for a new frame.In this experiment, number of antennas and tags affect the accuracy obviously, the initial frame size is set to 64 according the tag cardinality. while the number of moving tags slightly affect the accuracy. 2)Results:We can save 60%frames to extract physical- Specifically,FN errors are mainly caused by the relative layer features by decoding the collision signals,while the scales between antenna number and tag number.When the standard variance of extracted phase profiles and BLF are number of antennas is relatively small compared with the 9.7 and 4.3us respectively.Fig.12(a)shows the collision number of tags,we cannot exclusively distinguish all tags distribution and corresponding slot utilization of the first due to lower dimension of phase profiles.As a result,some frame.When we extract features from singleton,2-collision moving tags cannot be detected,which leads to high FN errors. and 3-collision slots,there are only 4.6 tags unidentified on As the number of antennas increases to be comparable with average after the first frame.The identification ratio is about the cardinality of tags,we can accurately detect the moving 2 times of C1G2 standard,which only identifies tags in the tags with high probability.FP errors are mainly caused by singleton slot.Further,Fig.12(b)reports unidentified tags the measuring phase variance.When the phase profiles are number of each frame.To identify all the tags,ClG2 standard relatively accurate,it is less likely to identify a stationary tag as usually need 5 frames typically.However,if we could exploit a moving one.Besides,both FP and FN are not sensitive about the collision slot,we could finish the inventory in 2 frames. the number of moving tags.This is because when fixing other Meanwhile,as shown in Fig.12(c)and 12(d),both phase parameters,the probability of correct and incorrect identifying profiles and BLF variance can be sufficiently restricted.We each tag is the same.Hence in Fig.12(g)both FP and FN exploit the cumulative distribution function(CDF)to show the varies a little. accuracy of the extracted physical-layer features from collision C.Evaluate the Time Efficiency signal.80%variances of signal length are 5us and 8us for 2- FTPS can save 80%inventory time when querying more collision and 3-collision respectively.For the phase profile, than hundreds of tags compared with CIG2 protocol.We the variances of 80%sample are 8 and 16 respectively.The compare with C1G2 standard to evaluate the time efficiency. errors are caused by the noise imported by the collided tags. Specifically,we evaluate the querying time and the cost frames of conducting a typical query cycle.We use the time of each B.Evaluate the Accuracy in Moving Tag Detection period in [1,2]to estimate the querying time,i.e.,Ims for 1)Experiment Settings:We further perform extensive sim- collision slot and 4ms for singleton slot.We set the initial ulations to evaluate GMM over different parameters on MAT- frame size based on the number of tags. LAB.In this experiment,we monitor hundreds of tags,which As shown in Fig.13(a),the modified protocol can save are scattered randomly inside a 10m x 10m room and the 80%time compared with C1G2 standard through decoding the

!"#$%&' ()& *+)+$"%),-' ()&. /0 /1 /2 /0 /1 /2 345)+65' 7$.+,$89+$"% *+)+$"%),-' 7$.+,$89+$"% ! !" Fig. 11: Matching example VII. PERFORMANCE EVALUATION In the following, we evaluate the performance from three aspects. Firstly, we evaluate the feature extraction scheme based on a small scale experiment in the realistic environment. Then we evaluate GMM solution in terms of the detection accuracy of motion status. Lastly, we compare FTPS and C1G2 standard to evaluate the time efficiency. A. Evaluate the Accuracy in Feature Extraction 1) Experiment Settings: We perform a realistic experiment to evaluate the extracted physical-layer features by issuing 50 tags. All signal traces are collected with the GNURadio/USRP platform as described in Section IV. Due to the power limita￾tion of USRP for scattering 50 tags, we use a four-step scheme to collect the realistic signal. Firstly, we emulate the process of slot selection on MATLAB according to C1G2 standard. Secondly, we collect the responding signal trace for each slot on the USRP platform according to the result of slot selection. Thirdly, we extract physical-layer features from singleton and collision slots. Lastly, we modify the frame size based on the number of identified tags for a new frame. In this experiment, the initial frame size is set to 64 according the tag cardinality. 2) Results: We can save 60% frames to extract physical￾layer features by decoding the collision signals, while the standard variance of extracted phase profiles and BLF are 9.7◦ and 4.3µs respectively. Fig. 12(a) shows the collision distribution and corresponding slot utilization of the first frame. When we extract features from singleton, 2-collision and 3-collision slots, there are only 4.6 tags unidentified on average after the first frame. The identification ratio is about 2 times of C1G2 standard, which only identifies tags in the singleton slot. Further, Fig. 12(b) reports unidentified tags number of each frame. To identify all the tags, C1G2 standard usually need 5 frames typically. However, if we could exploit the collision slot, we could finish the inventory in 2 frames. Meanwhile, as shown in Fig. 12(c) and 12(d), both phase profiles and BLF variance can be sufficiently restricted. We exploit the cumulative distribution function (CDF) to show the accuracy of the extracted physical-layer features from collision signal. 80% variances of signal length are 5µs and 8µs for 2- collision and 3-collision respectively. For the phase profile, the variances of 80% sample are 8◦ and 16◦ respectively. The errors are caused by the noise imported by the collided tags. B. Evaluate the Accuracy in Moving Tag Detection 1) Experiment Settings: We further perform extensive sim￾ulations to evaluate GMM over different parameters on MAT￾LAB. In this experiment, we monitor hundreds of tags, which are scattered randomly inside a 10m × 10m room and the receiving antennas are attached on each wall randomly. We deploy the transmitting antenna in the center of room for simplicity. The phase values are measured according to the transmitting distance and wavelength. We first extract the stationary phase distribution from singleton slot in the tag inventory phase. Then in continuous polling phase, we extract the real-time phase distribution from singleton and collision slots. For every polling cycle, we utilize the Hungarian algo￾rithm to detect the moving tags. In this experiment, we study the effect of the following parameters on the detection accuracy: phase variance σ, num￾ber of moving tags η, number of antennas τ and number of monitoring tags ω. κ is set to 2ω for simplicity. We utilize false positive error (FP) and false negative error (FN) to evaluate the accuracy. False positive error means the stationary tags is identified as moving tags, and false negative error means the moving tags is identified as stationary tags. Because phase values vary in accordance with Gaussian distribution as evaluated. We import the variances according to the collision type. For singleton slot, a fixed standard deviation of 4◦ is used based on the evaluation in Section IV-B. For collision slot, we import parameters σ and 2σ to denote the standard deviations of 2-collision and 3-collision respectively. We cannot extracted phase profiles from 4+-collision slots. 2) Results: GMM can correctly detect 85% of the moving tags with about 6% false positive errors. Fig. 12(e)∼12(h) report the results from different points of views. We note the number of antennas and tags affect the accuracy obviously, while the number of moving tags slightly affect the accuracy. Specifically, FN errors are mainly caused by the relative scales between antenna number and tag number. When the number of antennas is relatively small compared with the number of tags, we cannot exclusively distinguish all tags due to lower dimension of phase profiles. As a result, some moving tags cannot be detected, which leads to high FN errors. As the number of antennas increases to be comparable with the cardinality of tags, we can accurately detect the moving tags with high probability. FP errors are mainly caused by the measuring phase variance. When the phase profiles are relatively accurate, it is less likely to identify a stationary tag as a moving one. Besides, both FP and FN are not sensitive about the number of moving tags. This is because when fixing other parameters, the probability of correct and incorrect identifying each tag is the same. Hence in Fig. 12(g) both FP and FN varies a little. C. Evaluate the Time Efficiency FTPS can save 80% inventory time when querying more than hundreds of tags compared with C1G2 protocol. We compare with C1G2 standard to evaluate the time efficiency. Specifically, we evaluate the querying time and the cost frames of conducting a typical query cycle. We use the time of each period in [1, 2] to estimate the querying time, i.e., 1ms for collision slot and 4ms for singleton slot. We set the initial frame size based on the number of tags. As shown in Fig. 13(a), the modified protocol can save 80% time compared with C1G2 standard through decoding the

0.6 .0.6 03 02 789 30 (a)Collisions in the Ist frame (b)Unidentified tags after each frame (c)Variance of signal length (d)Variance of phase 05 18 01 The numbe rof an The number of tags (x100) The number of moving tags (e)Accuracy evaluation with a =8.(f)Accuracy evaluation with o =8,(g)Accuracy evaluation with o =8.(h)Accuracy evaluation w n=3 andw =500 n=3 andT =8 w =500 andT =8 w=500 and T=8 Fig.12:Evaluation results of the accuracy in feature extraction collision slot.As for the cost frames,even though we need to REFERENCES identify hundreds,the modified protocol can extract features [1]L.Xie,Q.Li,X.Chen,S.Lu,and D.Chen,"Continuous scanning with within 2 frames for most cases.By setting initial frame size mobile reader in RFID systems:An experimental study."in Proc.of appropriately,we can identify over 80%tags in the first frame. MobiHoc,2013. [2]J.Gummeson,P.Zhang,and D.Ganesan,"Flit:a bulk transmission Then the rest tags can be easily identified with a next frame. protocol for rfid-scale sensors."in Proc.ofACM MobiSys.2012. But C1G2 standard can only identify about 35%tags in the [3]S.Chen,M.Zhang,and B.Xiao."Efficient information collection first frame,which leads 7~10 frames in total. protocols for sensor-augmented RFID networks."in Proc.ofINFOCOM. 2011 [4]"EPC CIG2 Protocol,http://www.epcglobalinc.org/standards/uhfc1g2. [5]L.Yang,Y.Qi.J.Fang.X.Ding.T.Liu,and M.Li,"Frogeye:Perception of the slightest tag motion,"in Proc.of IEEE INFOCOM,2014. [6]T.Liu,L.Yang.X.-Y.Li.H.Huang.and Y.Liu,"Tagbooth:Deep shopping data acquisition powered by rfid tags."in Proc.of IEEE INFOCOM.2015. [7]J.Wang.H.Hassanieh,D.Katabi,and P.Indyk,"Efficient and reliable 2004006008001000 low-power backscatter networks,"in Proc.of ACM SIGCOMM,2012. Number of tao [8]J.Ou,M.Li,and Y.Zheng,"Come and be served:Parallel decoding (a)Time of a query cycle (b)Frame numbers of a query cycle for cots rfid tags,"in Proc.of ACM MobiCom,2015 Fig.13:Evaluation of querying time 9]P.Hu,P.Zhang.and D.Ganesan,"Laissez-faire:Fully asymmetric VIII.CONCLUSION backscatter communication,"in Proc.of ACM S/GCOMM,2015. [10]Y.Zheng and M.Li,"P-MTI:Physical-layer missing tag identification In this paper,we propose a real-time approach to detect via compressive sensing,"in Proc.of IEEE INFOCOM,2013 the moving tags in the monitoring area.We achieve the time [11]L.Yang.Y.Chen,X.-Y.Li,C.Xiao,M.Li.and Y.Liu,"Tagoram: efficiency by decoding collisions from the physical layer. Real-time tracking of mobile RFID tags to high precision using COTS devices,"in Proc.of ACM MobiCom.2014. We are able to extract two physical-layer features,i.e.,the [12]J.Wang and D.Katabi,"Dude,wheres my card?RFID positioning phase profile and the backscatter link frequency,to distinguish that works with multipath and non-line of sight,"in Proc.of ACM SIGCOMM.2013. different tags.By resolving the physical-layer features from [13]Y.Hou,J.Ou,Y.Zheng,and M.Li,"PLACE:Physical layer cardinality collisions,we are able to derive the motion status of multiple estimation for large-scale RFID systems,"in Proc of INFOCOM,2015 tags.Experiment result shows that when monitoring 1000 [14]M.Buettner and D.Wetherall,"A software radio-based UHF RFID tags,our solution can accurately detect the moving tags while reader for PHY/MAC experimentation,"in Proc.of IEEE RFID,2011. [15】Y.Zheng and M.Li,“Read bulk data from computational RFIDs,”in reducing 80%time compared with the state-of-art solutions. Proc.of IEEE INFOCOM.2014. ACKNOWLEDGMENT [16]D.Zanetti,B.Danev er al,"Physical-layer identification of UHF RFID tags."in Proc.of ACM MobiCom,2010,pp.353-364. This work is supported in part by National Natural Science [17]B.Danev,S.Capkun,R.Jayaram Masti,and T.S.Benjamin,"Towards Foundation of China under Grant Nos.61472185,61373129 practical identification of HF RFID devices,"ACM TISSEC,2012. [18]D.Ma,C.Qian,W.Li,J.Han,and J.Zhao,"Geneprint:Generic and 61321491,91218302,61502224;JiangSu Natural Science accurate physical-layer identification for UHF RFID tags."in Proc.f Foundation.No.BK20151390:Key Project of Jiangsu Re- IEEE ICNP,2013. search Program under Grant No.BE2013116;EU FP7 IRSES [19]D.De Donno,F.Ricciato,L.Catarinucci,A.Coluccia,and L.Tarricone "Challenge:towards distributed RFID sensing with software-defined MobileCloud Project under Grant No.612212;CCF-Tencent radio,"in Proc.of ACM MobiCom.2010. Open Fund:China Postdoctor Science Fund under Grant No. [20]H.W.Kuhn,"The hungarian method for the assignment problem,"Naval 2015M570434.This work is partially supported by Collabo- research logistics quarterly.1955. rative Innovation Center of Novel Software Technology and Industrialization.Lei Xie is the corresponding author

Collision types 0123456 Number of slots 0 10 20 30 Number of actual slots Number of utlized slots (a) Collisions in the 1st frame Frame counts 0123456789 Number of remained tags 0 10 20 30 40 50 C1G2 FTPS (b) Unidentified tags after each frame Signal length variance 0 10 20 30 40 CDF 0 0.2 0.4 0.6 0.8 1 2-collision 3-collision (c) Variance of signal length Phase variance (Degree) 0 10 20 30 40 CDF 0 0.2 0.4 0.6 0.8 1 2-collision 3-collision (d) Variance of phase The number of antennas 2 3 4 5 6 7 8 9 10 Percentages 0 0.2 0.4 0.6 0.8 1 FP FN (e) Accuracy evaluation with σ = 8, η = 3 and ω = 500 The number of tags (×100) 1 2 3 4 5 6 7 8 9 10 Percentages 0 0.1 0.2 0.3 0.4 0.5 FP FN (f) Accuracy evaluation with σ = 8, η = 3 and τ = 8 The number of moving tags 0 1 2 3 4 5 6 7 8 9 10 Percentages 0 0.1 0.2 0.3 0.4 0.5 FP FN (g) Accuracy evaluation with σ = 8, ω = 500 and τ = 8 Phase variance (degree) 4 5 6 7 8 9 10 Percentages 0 0.2 0.4 0.6 FP FN (h) Accuracy evaluation with η = 3, ω = 500 and τ = 8 Fig. 12: Evaluation results of the accuracy in feature extraction collision slot. As for the cost frames, even though we need to identify hundreds, the modified protocol can extract features within 2 frames for most cases. By setting initial frame size appropriately, we can identify over 80% tags in the first frame. Then the rest tags can be easily identified with a next frame. But C1G2 standard can only identify about 35% tags in the first frame, which leads 7 ∼ 10 frames in total. Number of tags 200 400 600 800 1000 Identification time(ms) 0 2000 4000 6000 8000 FTPS C1G2 (a) Time of a query cycle Number of tags 200 400 600 800 1000 Number of frames 0 5 10 15 FTPS C1G2 (b) Frame numbers of a query cycle Fig. 13: Evaluation of querying time VIII. CONCLUSION In this paper, we propose a real-time approach to detect the moving tags in the monitoring area. We achieve the time efficiency by decoding collisions from the physical layer. We are able to extract two physical-layer features, i.e., the phase profile and the backscatter link frequency, to distinguish different tags. By resolving the physical-layer features from collisions, we are able to derive the motion status of multiple tags. Experiment result shows that when monitoring 1000 tags, our solution can accurately detect the moving tags while reducing 80% time compared with the state-of-art solutions. ACKNOWLEDGMENT This work is supported in part by National Natural Science Foundation of China under Grant Nos. 61472185, 61373129, 61321491, 91218302, 61502224; JiangSu Natural Science Foundation, No. BK20151390; Key Project of Jiangsu Re￾search Program under Grant No. BE2013116; EU FP7 IRSES MobileCloud Project under Grant No. 612212; CCF-Tencent Open Fund; China Postdoctor Science Fund under Grant No. 2015M570434. This work is partially supported by Collabo￾rative Innovation Center of Novel Software Technology and Industrialization. Lei Xie is the corresponding author. REFERENCES [1] L. Xie, Q. Li, X. Chen, S. Lu, and D. Chen, “Continuous scanning with mobile reader in RFID systems: An experimental study.” in Proc. of MobiHoc, 2013. [2] J. Gummeson, P. Zhang, and D. Ganesan, “Flit: a bulk transmission protocol for rfid-scale sensors,” in Proc. of ACM MobiSys, 2012. [3] S. Chen, M. Zhang, and B. Xiao, “Efficient information collection protocols for sensor-augmented RFID networks.” in Proc. of INFOCOM, 2011. [4] “EPC C1G2 Protocol,” http://www.epcglobalinc.org/standards/uhfc1g2. [5] L. Yang, Y. Qi, J. Fang, X. Ding, T. Liu, and M. Li, “Frogeye: Perception of the slightest tag motion,” in Proc. of IEEE INFOCOM, 2014. [6] T. Liu, L. Yang, X.-Y. Li, H. Huang, and Y. Liu, “Tagbooth: Deep shopping data acquisition powered by rfid tags,” in Proc. of IEEE INFOCOM, 2015. [7] J. Wang, H. Hassanieh, D. Katabi, and P. Indyk, “Efficient and reliable low-power backscatter networks,” in Proc. of ACM SIGCOMM, 2012. [8] J. Ou, M. Li, and Y. Zheng, “Come and be served: Parallel decoding for cots rfid tags,” in Proc. of ACM MobiCom, 2015. [9] P. Hu, P. Zhang, and D. Ganesan, “Laissez-faire: Fully asymmetric backscatter communication,” in Proc. of ACM SIGCOMM, 2015. [10] Y. Zheng and M. Li, “P-MTI: Physical-layer missing tag identification via compressive sensing,” in Proc. of IEEE INFOCOM, 2013. [11] L. Yang, Y. Chen, X.-Y. Li, C. Xiao, M. Li, and Y. Liu, “Tagoram: Real-time tracking of mobile RFID tags to high precision using COTS devices,” in Proc. of ACM MobiCom, 2014. [12] J. Wang and D. Katabi, “Dude, wheres my card? RFID positioning that works with multipath and non-line of sight,” in Proc. of ACM SIGCOMM, 2013. [13] Y. Hou, J. Ou, Y. Zheng, and M. Li, “PLACE: Physical layer cardinality estimation for large-scale RFID systems,” in Proc. of INFOCOM, 2015. [14] M. Buettner and D. Wetherall, “A software radio-based UHF RFID reader for PHY/MAC experimentation,” in Proc. of IEEE RFID, 2011. [15] Y. Zheng and M. Li, “Read bulk data from computational RFIDs,” in Proc. of IEEE INFOCOM, 2014. [16] D. Zanetti, B. Danev et al., “Physical-layer identification of UHF RFID tags,” in Proc. of ACM MobiCom, 2010, pp. 353–364. [17] B. Danev, S. Capkun, R. Jayaram Masti, and T. S. Benjamin, “Towards practical identification of HF RFID devices,” ACM TISSEC, 2012. [18] D. Ma, C. Qian, W. Li, J. Han, and J. Zhao, “Geneprint: Generic and accurate physical-layer identification for UHF RFID tags,” in Proc. of IEEE ICNP, 2013. [19] D. De Donno, F. Ricciato, L. Catarinucci, A. Coluccia, and L. Tarricone, “Challenge: towards distributed RFID sensing with software-defined radio,” in Proc. of ACM MobiCom, 2010. [20] H. W. Kuhn, “The hungarian method for the assignment problem,” Naval research logistics quarterly, 1955