This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing Probing into the Physical Layer:Moving Tag Detection for Large-Scale RFID Systems Chuyu Wang,Student Member,IEEE,Lei Xie,Member,IEEE,Wei Wang,Member,IEEE, Yingying Chen,Senior Member,IEEE,Tao Xue,and Sanglu Lu,Member,IEEE Abstract-Logistics monitoring is a fundamental application that utilizes RFID systems to manage numerous tagged-objects.Due to the frequent rearrangement of tagged-objects,a fast RFID-based tracking approach is highly desired for accurate logistics distribution. However,traditional RFID systems usually take tens of seconds to interrogate hundreds of RFID tags,not to mention the time delay involved to locate all the tags,which severely prevents from in-time tracking.To address this issue,we reduce the problem domain by first distinguishing the motion status of the tagged-objects,i.e.."stationary"or"moving",and then tracking the moving objects with the state-of-the-art localization schemes,which significantly reduces the efforts of tracking all the objects.Toward this end,we propose a moving tag detection mechanism,which achieves the time efficiency by exploiting the useless collision signal in RFID systems.In particular,we extract two kinds of physical-layer features(namely phase profile and backscatter link frequency)from the collision signal received by the USRP to distinguish tags at different positions.We further develop the Graph Matching(GM)method and Coherent Phase Variance(CPV)method to detect the moving tagged-objects.Experiment results show that our approach can accurately detect the moving objects while reducing 80%inventory time compared with the state-of-art solutions. Index Terms-RFID,Collision Decoding,Tag Inventory 1 INTRODUCTION WimdutryD.ml h -300 Decode collision signal 3600 in I-Q plane ployed in increasingly large numbers to facilitate the smart 3800 management.For example,in the logistic monitoring,there are usually more than hundreds of objects attached with 200 RFID tags in the monitoring area.Due to the frequent 400 Recovery rearrangement of the tagged-objects,the RFID systems are 4500 500 4 )e)1 Inphase required to track the movement of all tags timely to prevent Backscatter link frequency Phase profiles extraction the target objects from mistakenly rearranging.However, extraction a Commercial-Of-The-Shelf (COTS)RFID system usually Fig.1.Illusion of extracting physical-layer features from collision signal. takes tens of seconds to interrogate hundreds of RFID based schemes 3-5,14]leverage the Frame-Slotted- tags [1],[2],not to mention the time delay to track all the Aloha (FSA)protocol to identify the tags,which usually tags.This severely hinders the system from tracking the takes tens of seconds to interrogate hundreds of RFID tags in movement of tagged-objects in time.Since only some of the real RFID systems.The main cause of such time inefficiency objects are moved at a certain moment,to reduce the efforts is the waste of the collision slots,which usually occupy a of tracking all the objects,one possible solution is to first large proportion of the overall time slots.Recently,some identify the motion status of the objects,i.e.,"stationary"or emerging work try to make use of the collision slots to "moving",and then only track the"moving"objects.For the improve time efficiency of tag inventory [6]-[9]and further stationary"objects,since they are presumed to be statically detect the missing tags from the collision signals [3],[10]. placed in a specific location,we do not need to track them. However,different from a missing tag,a moving tag can For the "moving"objects,we can leverage the existing still be interrogated by the reader,thus these methods localization techniques to track them.Since the "moving" are not suitable to detect the moving tags.In addition, objects only occupy a small part of the total number,we can for the positioning schemes,the state-of-the-art localization save a lot of time by only focusing on tracking the moving schemes [11]-[13]usually locate the tags one by one,and objects,instead of wasting time in tracking the stationary they usually take up to several hundreds of milliseconds to objects,which makes it possible to perform the fast large- locate a unique tag.Therefore,it is difficult to concurrently scale monitoring. locate all tags timely using existing solutions,when dealing To track the moving tags in the monitoring area,exist- with hundreds of tags. ing studies [3]-[14]usually involve two steps,i.e.,a fast In this paper,we propose a fast moving tag detection tag inventory scheme to interrogate tags,and an effective scheme for large-scale RFID systems,which works as a positioning scheme to determine the motion status of the fundamental premise to support the tracking applications tags,which would be hard to perform large-scale moving of tagged-objects.The main idea is to extract the physical- RFID monitoring in a timely manner.Specifically,for the layer features of each tag from the collision signal to achieve tag inventory schemes in RFID systems,traditional polling- the time efficiency.Fig.1 uses the collision signal of three 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 1 Probing into the Physical Layer: Moving Tag Detection for Large-Scale RFID Systems Chuyu Wang, Student Member, IEEE, Lei Xie, Member, IEEE, Wei Wang, Member, IEEE, Yingying Chen, Senior Member, IEEE, Tao Xue, and Sanglu Lu, Member, IEEE Abstract—Logistics monitoring is a fundamental application that utilizes RFID systems to manage numerous tagged-objects. Due to the frequent rearrangement of tagged-objects, a fast RFID-based tracking approach is highly desired for accurate logistics distribution. However, traditional RFID systems usually take tens of seconds to interrogate hundreds of RFID tags, not to mention the time delay involved to locate all the tags, which severely prevents from in-time tracking. To address this issue, we reduce the problem domain by first distinguishing the motion status of the tagged-objects, i.e., “stationary” or “moving”, and then tracking the moving objects with the state-of-the-art localization schemes, which significantly reduces the efforts of tracking all the objects. Toward this end, we propose a moving tag detection mechanism, which achieves the time efficiency by exploiting the useless collision signal in RFID systems. In particular, we extract two kinds of physical-layer features (namely phase profile and backscatter link frequency) from the collision signal received by the USRP to distinguish tags at different positions. We further develop the Graph Matching (GM) method and Coherent Phase Variance (CPV) method to detect the moving tagged-objects. Experiment results show that our approach can accurately detect the moving objects while reducing 80% inventory time compared with the state-of-art solutions. Index Terms—RFID, Collision Decoding, Tag Inventory ✦ 1 INTRODUCTION WITH the rapid proliferation of IoT (Internet of Things) industry, RFID, as a key technology, has been deployed in increasingly large numbers to facilitate the smart management. For example, in the logistic monitoring, there are usually more than hundreds of objects attached with RFID tags in the monitoring area. Due to the frequent rearrangement of the tagged-objects, the RFID systems are required to track the movement of all tags timely to prevent the target objects from mistakenly rearranging. However, a Commercial-Of-The-Shelf (COTS) RFID system usually takes tens of seconds to interrogate hundreds of RFID tags [1], [2], not to mention the time delay to track all the tags. This severely hinders the system from tracking the movement of tagged-objects in time. Since only some of the objects are moved at a certain moment, to reduce the efforts of tracking all the objects, one possible solution is to first identify the motion status of the objects, i.e., “stationary” or “moving”, and then only track the “moving” objects. For the “stationary” objects, since they are presumed to be statically placed in a specific location, we do not need to track them. For the “moving” objects, we can leverage the existing localization techniques to track them. Since the “moving” objects only occupy a small part of the total number, we can save a lot of time by only focusing on tracking the moving objects, instead of wasting time in tracking the stationary objects, which makes it possible to perform the fast largescale monitoring. To track the moving tags in the monitoring area, existing studies [3]–[14] usually involve two steps, i.e., a fast tag inventory scheme to interrogate tags, and an effective positioning scheme to determine the motion status of the tags, which would be hard to perform large-scale moving RFID monitoring in a timely manner. Specifically, for the tag inventory schemes in RFID systems, traditional pollingDecode collision signal in I-Q plane Backscatter link frequency Phase profiles extraction extraction Decode Recovery Fig. 1. Illusion of extracting physical-layer features from collision signal. based schemes [3]–[5], [14] leverage the Frame-SlottedAloha (FSA) protocol to identify the tags, which usually takes tens of seconds to interrogate hundreds of RFID tags in real RFID systems. The main cause of such time inefficiency is the waste of the collision slots, which usually occupy a large proportion of the overall time slots. Recently, some emerging work try to make use of the collision slots to improve time efficiency of tag inventory [6]–[9] and further detect the missing tags from the collision signals [3], [10]. However, different from a missing tag, a moving tag can still be interrogated by the reader, thus these methods are not suitable to detect the moving tags. In addition, for the positioning schemes, the state-of-the-art localization schemes [11]–[13] usually locate the tags one by one, and they usually take up to several hundreds of milliseconds to locate a unique tag. Therefore, it is difficult to concurrently locate all tags timely using existing solutions, when dealing with hundreds of tags. In this paper, we propose a fast moving tag detection scheme for large-scale RFID systems, which works as a fundamental premise to support the tracking applications of tagged-objects. The main idea is to extract the physicallayer features of each tag from the collision signal to achieve the time efficiency. Fig. 1 uses the collision signal of three
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing 2 tags received by the USRP platform as an example to show with a small distance.The coexistence of these two physical- our basic idea.When we obtain the collision signal from layer features allows fine-grained tags and their locations the USRP,we can decompose them based on the signal discrimination to further determine their motion status.The distribution in the I-O plane.Then the channel coefficient third challenge is to extract the above physical-layer features of each tag can be represented as an arrow in the figure, from the collisions of multiple tag responses.To address this which is further used to extract the physical-layer features challenge,we investigate the geometrical characteristic of for moving detection.Particularly,we are able to extract two different kinds of collision signals in I-Q plane,and extract kinds of physical-layer features of RFID tags,i.e.,the phase the phase profile of each tag response based on the specific profile and the backscatter link frequency,to distinguish the geometrical characteristic.For each tag response,we further tags at different positions.The two physical-layer features leverage the special patterns(e.g.,preambles)to extract the then serve as the fingerprints of each tag to derive the backscatter link frequency from the signal length. motion status of all tags simultaneously,greatly improving This paper presents the first study of probing into the the overall time-efficiency.Toward this end,we design a physical-layer features to detect the moving tags for large two-phase tag-detection scheme,including the tag inventory scale RFID systems.Specifically,we make four main con- and confinuous polling,to determine the motion status of tributions (a preliminary version of this work appeared tags.In the tag inventory phase,the RFID reader identifies in [15]):First,we develop a mechanism to detect the motion each tag via a traditional inventory cycle and constructs status of RFID tags,which is a fundamental premise for the original distribution of the physical-layer features for all tracking the movement of RFID tags in large-scale RFID sys- the tags.It may take tens of seconds due to the waste of tems.Second,our approach is able to extract the physical- collision slots.In the continuous polling phase,the RFID layer features,including the phase profile and backscatter reader continuously monitors the motion status of each tag link frequency,from the collision signal for efficient moving by issuing multiple query cycles.Differing from the existing tag detection.Third,we develop a voting-based scheme solutions,which still identify the tags via the singleton to determine the moving objects from multiple attached slots,we focus on extracting the physical-layer features tags,which can tackle the measurement errors in real en- from the signal of collision slots.Thus we can save lots of vironments.Fourth,we evaluated our system in realistic inventory time by making use of the useless collision slots. settings and experiment results show that our solution can For each query cycle,we construct an updated distribution accurately detect the moving objects while reducing 80% of the physical-layer features from both the singleton and inventory time compared with existing approaches. collision slots.Then we can detect the moving objects from the two distributions based on the fact that a static tag has 2 RELATED WORK stable physical-layer features,while a moving tag has dif- ferent physical-layer features across the two distributions. Missing tag detection.There have been active studies on Particularly,a Graph Matching(GM)method is proposed to detecting the missing tags based on the RF signals [3],[5], detect the moving tags effectively based on the Hungarian [16].Yang et al.[5]propose to detect the missing tags based algorithm,and a Coherent Phase Variance(CPV)method is on the statistical signal information,which measures the RF proposed to determine the moving objects when we attach signal of tags for a fairly long time for data collection.Zheng multiple tags on one object for robustness.Since the fag et al.[10]employ an efficient method to detect the missing inventory phase and continuous polling phase are executed tags based on signal superposition principle on physical alternately,the time inefficiency of the tag inventory phase layer.Zhu et al.[16]try to identify the unknown tags in can thus be amortized by the subsequent multiple polling large-scale RFID system.Different from the above work, cycles,and the overall time-efficiency is achieved. which only consider the missing tags,we focus on detecting There are three main technical challenges in detecting the the moving tags,which still can be identified by the reader. moving tags.The first challenge is to achieve time efficiency in Moreover,in regard to a large-scale RFID system,we need large scale RFID systems.Due to the long duration of a tradi- to achieve the time efficiency by updating the motion status tional inventory cycle,it is difficult to continuously update in time,which is seldom discussed in the above works the motion status of all tags within limited time intervals Collision recovery.Many studies focus on recovering the in a large-scale RFID system.To address this challenge,a tag signal [7],[8]or estimating tag cardinality [17]from the two-phase monitoring scheme is proposed,which includes collision signals based on the dedicated instruments like a normal tag inventory phase and multiple fast tag polling USRP.With the Software Defined Radio based UHF-RFID phases.During the fast tag polling phases,we significantly reader designed by Buettner et al.[18],several methods are improve the time efficiency by exploiting the tag collisions proposed to deal with the collision problems [6]-[8],[19]. to extract the physical-layer features for the detection of Zheng et al.[19]use the Computational RFID tags and SDR moving tags.The second challenge is to detect the motion status reader to improve the data throughput.Wang et al.[6]view of all tags via the physical-layer features.Since the EPC ID is collisions as a code across the bits transmitted by the tags not even transmitted in the collision slot,it is difficult to to improve the bandwidth in RFID system.Hou et al.[17] determine the moving tags only based on the physical-layer investigate the collision signals in physical layer to estimate features.To solve this problem,we find that the backscatter cardinality of large scale RFID system.Other work [7],[8]try link frequency of the tag's response has high degree of to recovery the data from the collision signals by leveraging difference among different tags regardless of the motion the time-domain separations.Unlike these work,we try to status of the tags,whereas the phase profile from the tag's extract the tag position related physical features from the response changes accordingly even if a specific tag is moved collision signals to detect the moving tags. 1536-1233 (c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 2 tags received by the USRP platform as an example to show our basic idea. When we obtain the collision signal from the USRP, we can decompose them based on the signal distribution in the I-Q plane. Then the channel coefficient of each tag can be represented as an arrow in the figure, which is further used to extract the physical-layer features for moving detection. Particularly, 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 at different positions. The two physical-layer features then serve as the fingerprints of each tag to derive the motion status of all tags simultaneously, greatly improving the overall time-efficiency. Toward this end, we design a two-phase tag-detection scheme, including the tag inventory and continuous polling, to determine the motion status of tags. In the tag inventory phase, the RFID reader identifies each tag via a traditional inventory cycle and constructs the original distribution of the physical-layer features for all the tags. It may take tens of seconds due to the waste of collision slots. In the continuous polling phase, the RFID reader continuously monitors the motion status of each tag by issuing multiple query cycles. Differing from the existing solutions, which still identify the tags via the singleton slots, we focus on extracting the physical-layer features from the signal of collision slots. Thus we can save lots of inventory time by making use of the useless collision slots. For each query cycle, we construct an updated distribution of the physical-layer features from both the singleton and collision slots. Then we can detect the moving objects from the two distributions based on the fact that a static tag has stable physical-layer features, while a moving tag has different physical-layer features across the two distributions. Particularly, a Graph Matching (GM) method is proposed to detect the moving tags effectively based on the Hungarian algorithm, and a Coherent Phase Variance (CPV) method is proposed to determine the moving objects when we attach multiple tags on one object for robustness. Since the tag inventory phase and continuous polling phase are executed alternately, the time inefficiency of the tag inventory phase can thus be amortized by the subsequent multiple polling cycles, and the overall time-efficiency is achieved. There are three main technical challenges in detecting the moving tags. The first challenge is to achieve time efficiency in large scale RFID systems. Due to the long duration of a traditional inventory cycle, it is difficult to continuously update the motion status of all tags within limited time intervals in a large-scale RFID system. To address this challenge, a two-phase monitoring scheme is proposed, which includes a normal tag inventory phase and multiple fast tag polling phases. During the fast tag polling phases, we significantly improve the time efficiency by exploiting the tag collisions to extract the physical-layer features for the detection of moving tags. The second challenge is to detect the motion status of all tags via the physical-layer features. Since the EPC ID is not even transmitted in the collision slot, it is difficult to determine the moving tags only based on the physical-layer features. To solve this problem, we find that the backscatter link frequency of the tag’s response has high degree of difference among different tags regardless of the motion status of the tags, whereas the phase profile from the tag’s response changes accordingly even if a specific tag is moved with a small distance. The coexistence of these two physicallayer features allows fine-grained tags and their locations discrimination to further determine their motion status. The third challenge is to extract the above physical-layer features from the collisions of multiple tag responses. To address this challenge, we investigate the geometrical characteristic of different kinds of collision signals in I-Q plane, and extract the phase profile of each tag response based on the specific geometrical characteristic. For each tag response, we further leverage the special patterns (e.g., preambles) to extract the backscatter link frequency from the signal length. This paper presents the first study of probing into the physical-layer features to detect the moving tags for large scale RFID systems. Specifically, we make four main contributions (a preliminary version of this work appeared in [15]): First, we develop a mechanism to detect the motion status of RFID tags, which is a fundamental premise for tracking the movement of RFID tags in large-scale RFID systems. Second, our approach is able to extract the physicallayer features, including the phase profile and backscatter link frequency, from the collision signal for efficient moving tag detection. Third, we develop a voting-based scheme to determine the moving objects from multiple attached tags, which can tackle the measurement errors in real environments. Fourth, we evaluated our system in realistic settings and experiment results show that our solution can accurately detect the moving objects while reducing 80% inventory time compared with existing approaches. 2 RELATED WORK Missing tag detection. There have been active studies on detecting the missing tags based on the RF signals [3], [5], [16]. Yang et al. [5] propose to detect the missing tags based on the statistical signal information, which measures the RF signal of tags for a fairly long time for data collection. Zheng et al. [10] employ an efficient method to detect the missing tags based on signal superposition principle on physical layer. Zhu et al. [16] try to identify the unknown tags in large-scale RFID system. Different from the above work, which only consider the missing tags, we focus on detecting the moving tags, which still can be identified by the reader. Moreover, in regard to a large-scale RFID system, we need to achieve the time efficiency by updating the motion status in time, which is seldom discussed in the above works. Collision recovery. Many studies focus on recovering the tag signal [7], [8] or estimating tag cardinality [17] from the collision signals based on the dedicated instruments like USRP. With the Software Defined Radio based UHF-RFID reader designed by Buettner et al. [18], several methods are proposed to deal with the collision problems [6]–[8], [19]. Zheng et al. [19] use the Computational RFID tags and SDR reader to improve the data throughput. Wang et al. [6] view collisions as a code across the bits transmitted by the tags to improve the bandwidth in RFID system. Hou et al. [17] investigate the collision signals in physical layer to estimate cardinality of large scale RFID system. Other work [7], [8] try to recovery the data from the collision signals by leveraging the time-domain separations. Unlike these work, we try to extract the tag position related physical features from the collision signals to detect the moving tags
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing 800 QUERY A Tag inventory Physical-layer phase Extract features 600 Singleton signal Fingerprints 400 inmmn Phase BLF 200 EPCID 10 Continuous pooling phase Extract features Fig3.A typicalingms. Collision signal 11 一LI Phase BLF Phase2 BLF2 to manufacturing imperfection,BLF varies among different tags.Therefore,it is suitable to combine the two features to Graph Matching Coherent Phase Variance detect the motion status of tags.Moreover,in order to satisfy the time efficiency,we recover each tag response according to the geometrical characteristic of the collision signals in I-Q plane,and extract the aforementioned physical-layer Fig.2.System Architecture. features from collision signals. Physical layer identification.Due to the hardware imper- Fig.2 presents the whole architecture of our system.We fection,leveraging the physical layer features to perform propose a two-phase monitoring scheme,including the tag tag identification or authentication has drawn widespread inventory and continuous polling phase,to efficiently detect attention recent years [20]-[23].Danev et al.[21]study the the motion status of all tags.In the tag inventory phase,the feasibility of physical-layer fingerprint in tag identification reader identifies each tag via a traditional inventory cycle in practical settings.Zanetti et al.[20]exploit the difference to extract the physical-layer features of all tags.Since the of backscattered link frequency caused by manufacturing tags are all static in this phase,the physical-layer features imperfection of tags to distinguish different tags.Further- of all tags construct an original distribution of the physical- more,Ma et al.[22]distinguish the tags by leveraging the layer features.In the continuous polling phases,the reader internal similarity among pulses of tags'RN16 preamble continuously monitors the motion status of all tag by issuing signals.Yang et al.[23]leverage the phase deviation of each multiple query cycles.For each query cycle,the reader tag and the specific geometric relationship among these tags constructs an updated distribution of the physical-layer fea- to authenticate the legal products.However,apart from the tures by effectively extracting the two features from both identification,we also need to detect the motion status of the singleton and collision signals.By comparing the up- each tag,which is a fundamental premise of tracking the dated distribution with the original distribution,we utilize movement of all the tags. a Graph Matching(GM)method to detect the moving tags in every query cycle.Moreover,based on the detected moving 3 SYSTEM DESIGN tags from the GM method,we further propose a Coherent 3.1 System Goals Phase Variance(CPV)method to detect the moving objects, In this paper,we propose a fast moving tag detection missing objects and inserting tags based on the multiple scheme for large scale RFID systems,so as to further sup- tags attached on one object.The multiple query cycles in port tracking the movement of all tagged-objects.Since the the continuous polling phase save lots of time from the tagged-objects in real RFID may be frequently moved in collision signals,and thus can amortize the time spent in and out for logistic distribution,we need to continuously the inventory phase,which takes more time due to the tra- ditional inventory cycle.Therefore,by efficiently extracting update the motion status within a limited time interval Therefore,our moving tag detection scheme should be able the position related features from the collision signal,we can to improve both the time efficiency in tag inventory and largely reduce the overall time in detecting the motion status the accuracy in detecting the motion status of all tags:1) compared with the existing C1G2 standard-based methods. The average duration for each cycle of tag inventory should 4 PHYSICAL-LAYER FEATURES CALCULATION be sufficiently reduced to achieve the time requirement for In this section,we demonstrate how to calculate our large scale RFID systems.2)There are two kinds of errors physical-layer features from the raw signal of tag response in the problem:a)False positive errors:the stationary tags via realistic experiments.We implement a software defined are detected as moving tags.b)False negative errors:the reader (SDR reader)according to the Gen2 project [18]. moving tags are detected as stationary tags.Both of the two Specifically,we operate the Gen2 project on our USRP errors should be effectively reduced in detecting the motion platform [24]with two FLEX-900 daughter boards and two status of all tags. Larid S9028 antennas on each board for transmitting and 3.2 System Architecture receiving,respectively.For the receiving module,we set the In this paper,two kinds of physical-layer features are inves- sampling rate to 2MHz,which represents 0.5us per sample. tigated to effectively detect the motion status of all tags 4.1 Tag Response in a Singleton Slot 1)Phase profile:it is the phase values of the RF signal, According to the EPC C1G2 standard [4],the RFID reader which describes the degree that the received signal offsets interrogates the tags based on the Frame-Slotted-Aloha from sent signal,ranging from 0 to 360 degrees.The phase (FSA)protocol.In the FSA protocol,each inventory cycle is value from the tag's response changes even if the tag is separated into several frames,while each frame is further moved with a small distance.2)Backscatter link frequency divided into multiple slots to identify the tags.For each (BLF):it is the frequency of the tag-to-reader link,which frame,the unidentified tags need to randomly select one slot indicates the data rate in the tag's response signal.Due for its data transmission.The reader starts a slot by sending 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 3 Tag inventory phase Singleton signal Continuous pooling phase Extract features θ θ Extract features θ Phase BLF Graph Matching Physical-layer Fingerprints Coherent Phase Variance Missing Inserting Phase1 BLF 1 Phase2 BLF2 Collision signal Fig. 2. System Architecture. Physical layer identification. Due to the hardware imperfection, leveraging the physical layer features to perform tag identification or authentication has drawn widespread attention recent years [20]–[23]. Danev et al. [21] study the feasibility of physical-layer fingerprint in tag identification in practical settings. Zanetti et al. [20] exploit the difference of backscattered link frequency caused by manufacturing imperfection of tags to distinguish different tags. Furthermore, Ma et al. [22] distinguish the tags by leveraging the internal similarity among pulses of tags’ RN16 preamble signals. Yang et al. [23] leverage the phase deviation of each tag and the specific geometric relationship among these tags to authenticate the legal products. However, apart from the identification, we also need to detect the motion status of each tag, which is a fundamental premise of tracking the movement of all the tags. 3 SYSTEM DESIGN 3.1 System Goals In this paper, we propose a fast moving tag detection scheme for large scale RFID systems, so as to further support tracking the movement of all tagged-objects. Since the tagged-objects in real RFID may be frequently moved in and out for logistic distribution, we need to continuously update the motion status within a limited time interval. Therefore, our moving tag detection scheme should be able to improve both the time efficiency in tag inventory and the accuracy in detecting the motion status of all tags: 1) The average duration for each cycle of tag inventory should be sufficiently reduced to achieve the 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 detected as moving tags. b) False negative errors: the moving tags are detected as stationary tags. Both of the two errors should be effectively reduced in detecting the motion status of all tags. 3.2 System Architecture In this paper, two kinds of physical-layer features are investigated to effectively detect the motion status of all tags. 1) Phase profile: it is the phase values of the RF signal, which describes the degree that the received signal offsets from sent signal, ranging from 0 to 360 degrees. 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 indicates the data rate in the tag’s response signal. Due !"#$% $&'( )*+ #,*-. /////////01234256 ///////7 ////'8 ////'7 )29:1;<=3 Fig. 3. A typical singleton slot in RFID systems. 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, in order to satisfy the time efficiency, 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 from collision signals. Fig. 2 presents the whole architecture of our system. We propose a two-phase monitoring scheme, including the tag inventory and continuous polling phase, to efficiently detect the motion status of all tags. In the tag inventory phase, the reader identifies each tag via a traditional inventory cycle to extract the physical-layer features of all tags. Since the tags are all static in this phase, the physical-layer features of all tags construct an original distribution of the physicallayer features. In the continuous polling phases, the reader continuously monitors the motion status of all tag by issuing multiple query cycles. For each query cycle, the reader constructs an updated distribution of the physical-layer features by effectively extracting the two features from both the singleton and collision signals. By comparing the updated distribution with the original distribution, we utilize a Graph Matching (GM) method to detect the moving tags in every query cycle. Moreover, based on the detected moving tags from the GM method, we further propose a Coherent Phase Variance (CPV) method to detect the moving objects, missing objects and inserting tags based on the multiple tags attached on one object. The multiple query cycles in the continuous polling phase save lots of time from the collision signals, and thus can amortize the time spent in the inventory phase, which takes more time due to the traditional inventory cycle. Therefore, by efficiently extracting the position related features from the collision signal, we can largely reduce the overall time in detecting the motion status compared with the existing C1G2 standard-based methods. 4 PHYSICAL-LAYER FEATURES CALCULATION In this section, we demonstrate how to calculate our physical-layer features from the raw signal of tag response via realistic experiments. We implement a software defined reader (SDR reader) according to the Gen2 project [18]. Specifically, we operate the Gen2 project on our USRP platform [24] 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. 4.1 Tag Response in a Singleton Slot According to the EPC C1G2 standard [4], the RFID reader interrogates the tags based on the Frame-Slotted-Aloha (FSA) protocol. In the FSA protocol, each inventory cycle is separated into several frames, while each frame is further divided into multiple slots to identify the tags. For each frame, the unidentified tags need to randomly select one slot for its data transmission. The reader starts a slot by sending
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing 400 Backscattered 0. signal 06 00 0.4 Leakage 0.2 signal -10 .5 0 400 0 80 Phase variation(degree) Transmitting distance(cm) Fig.4.Received signal model of a single tag.The baseband signal (a)Phase variance (b)Phase comparison received by the reader consists of the leakage signal and the backscat- tered signal.The phase profile can thus be extracted from these two Fig.5.Distinctiveness of phase profile.(a)shows the stability of the signal parts. extracted phase profile 6.(b)compares the extracted phase profile 6 from the USRP reader with the phase value from ImpinJ reader a QUERY/ORep command.Any tag that selects this slot strength.As for the phase value of the received signal in will respond the reader with a 16-bit random number RN16 Fig.4,it can be represented as: for channel probing.If the reader successfully decodes the 8=Φ-B, (2) RN16 bits,it responds the tag with an ACK,that tells the tag to transmit its EPC-ID.Otherwise,the reader will start which is the angle difference between the carrier signal the next slot,because there are multiple tags or none tag phase B and the backscattered signal phase We call 0 transmitting in this slot.Therefore,there are two kinds of the phase profile of the tag in this work. tag responses generally:1)RN16,where the tag responds We further carry out trace-driven evaluations to study the QUERY or QRep command,2)EPC-ID,where the tag the property of the phase profile.Firstly,we evaluate the answers the ACK command.During the tag response,the stability by conducting an empirical experiment on 50 tags reader keeps transmitting Continuous Wave(CW)to supply with random deployments.For each setting,we deploy power for the tags.Fig.3 presents a typical singleton slot each RFID tag 1m in front of the SDR reader [18]based on in RFID systems,which is collected from USRP.We note USRP platform,and measure 100 phase profiles by querying that the time of the EPC-ID is about 4 times longer than each tag 100 times with the USRP reader.The results are that of the RN16,because the data length of EPC-ID is normalized by subtracting the average phase value of each much longer than RN16.Meanwhile,since the time interval result set.Therefore,5000 normalized phase profiles are between the two responses,i.e.,the length of ACK,is so measured to evaluate the stability.As shown in Fig.5(a), small,the position and wireless environment of both RN16 the phase profile varies from-5°to5°，following a typical and EPC-ID can be regarded unchanged.Hence,instead of Gaussian distribution.So we can treat the phase profile as a extracting the physical-layer features from the EPC-ID,we stable feature for motion detection. can directly extract the feature from the RN16 signal,and Secondly,we compare the phase profile of SDR reader then skip the EPC-ID signal to save the inventory time. with the phase value of commercial reader (Impinj R420) by issuing the same tag.We vary the distance between 4.2 Phase Profile the antenna and the tag,which ranges from 20cm to 70cm Next,we demonstrate how to calculate the phase profile stepping by 1cm.For each step we measure 100 phase values from the RN16 signals via the signal transmitting model.In individually.As shown in Fig.5(b),the phase profile of SDR RFID systems,the tag transmits data using backscattering reader is almost the same as the phase value of commer- modulation.Hence,the baseband signal received by the cial reader,where the correlation coefficients calculated on reader can be represented as: MATLAB is 0.9979.Therefore,the phase profile is sensitive to any tiny movements,e.g.,Icm movement,which guarantees the s(t)=AeiB+x(1)Bei)+(t). (1) distinctiveness of the phase profile in the motion detection Here,Aei is the carrier signal(i.e.,Continuous Wave,CW), 4.3 Backscattered Link Frequency where A indicates the amplitude,j is v-1 and B is the In regard to the backscatter link frequency (BLF)of the corresponding phase value.Bej)is the backscattered response signal,it can be represented as fi in Eq.(1).Due signal of the tag,where B indicates the amplitude of the to the manufacturing imperfection,the BLF varies among backscattered signal and fi indicates the corresponding fre- different tags,which is used to distinguish tags [20],[22]. quency of the backscattered signal.x(t)is the binary bits In fact,fi determines the data rate of the tag's response.In sent by the tag,which is equal to either '0'or '1'.f(t)is regard to a typical encoding scheme Miller-4 of RFID system the ambient noise.Therefore,the actual baseband signal in Fig.6(a),fi determines the duration of a binary symbol, received by the reader is a superposition of the carrier signal i.e.,bit-0 or bit-1.Therefore,both bit-0 and bit-1 have the and the backscattered signal. same signal duration according to the Miller-4 encoding Intuitively,the baseband signal received from a single scheme.Since the binary length of RN16 signal is fixed tag response can be expressed in I-Q plane as shown in including the same preambles,a 16 bits random number Fig.4.The received signal consists of two parts:1)leakage and 1 check bit,it is reasonable to use the corresponding signal:the constant carrier signal (i.e.,CW),2)backscat- signal length of RN16 to represent the BLF.Meanwhile,we tered signal:the modulated tag signal.Formally,we define can also convert the signal length of RN16 to the BLF based the channel coefficient of the tag's backscattered signal as on the actual symbols in RN16.In regard to other encoding h =Bejft+),which expresses the channel information schemes in RFID system,e.g.,FMO,we can similarly use the of the backscattered signal,i.e.,the phase value and signal signal length of RN16 to represent the BLF. 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 4 ! " #$%&%'$( )*'+%, -%.&).%//$0$1( )*'+%, Fig. 4. Received signal model of a single tag. The baseband signal received by the reader consists of the leakage signal and the backscattered signal. The phase profile can thus be extracted from these two signal parts. a QUERY/QRep command. Any tag that selects this slot will respond the reader with a 16-bit random number RN16 for channel probing. If the reader successfully decodes the RN16 bits, it responds the tag with an ACK, that tells the tag to transmit its EPC-ID. Otherwise, the reader will start the next slot, because there are multiple tags or none tag transmitting in this slot. Therefore, there are two kinds of tag responses generally: 1) RN16, where the tag responds the QUERY or QRep command, 2) EPC-ID, where the tag answers the ACK command. During the tag response, the reader keeps transmitting Continuous Wave (CW) to supply power for the tags. Fig. 3 presents a typical singleton slot in RFID systems, which is collected from USRP. We note that the time of the EPC-ID is about 4 times longer than that of the RN16, because the data length of EPC-ID is much longer than RN16. Meanwhile, since the time interval between the two responses, i.e., the length of ACK, is so small, the position and wireless environment of both RN16 and EPC-ID can be regarded unchanged. Hence, instead of extracting the physical-layer features from the EPC-ID, we can directly extract the feature from the RN16 signal, and then skip the EPC-ID signal to save the inventory time. 4.2 Phase Profile Next, we demonstrate how to calculate the phase profile from the RN16 signals via the signal transmitting model. In RFID systems, the tag transmits data using backscattering modulation. Hence, the baseband signal received by the reader can be represented as: s(t) = Aejβ + x(t)Bej(2π fl t+Φ) + nˆ(t). (1) Here, Aejβ is the carrier signal (i.e., Continuous Wave, CW), where A indicates the amplitude, j is √ −1 and β is the corresponding phase value. Bej(2π fl t+Φ) is the backscattered signal of the tag, where B indicates the amplitude of the backscattered signal and fl indicates the corresponding frequency of the backscattered signal. x(t) is the binary bits sent by the tag, which is equal to either 00 0 or 01 0 . ˆn(t) is the ambient noise. Therefore, the actual baseband signal received by the reader is a superposition of the carrier signal and the backscattered signal. Intuitively, the baseband signal received from a single tag response can be expressed in I-Q plane as shown in Fig. 4. The received signal consists of two parts: 1) leakage signal: the constant carrier signal (i.e., CW), 2) backscattered signal: the modulated tag signal. Formally, we define the channel coefficient of the tag’s backscattered signal as h = Bej(2π fl t+Φ) , which expresses the channel information of the backscattered signal, i.e., the phase value and signal Phase variation(degree) -10 -5 0 5 10 CDF 0 0.2 0.4 0.6 0.8 1 (a) Phase variance 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) Phase comparison Fig. 5. Distinctiveness of phase profile. (a) shows the stability of the extracted phase profile θ. (b) compares the extracted phase profile θ from the USRP reader with the phase value from ImpinJ reader. strength. As for the phase value of the received signal in Fig. 4, it can be represented as: θ = Φ − β, (2) which is the angle difference between the carrier signal phase β and the backscattered signal phase Φ. We call θ the phase profile of the tag in this work. We further carry out trace-driven evaluations to study the property of the phase profile. Firstly, we evaluate the stability by conducting an empirical experiment on 50 tags with random deployments. For each setting, we deploy each RFID tag 1m in front of the SDR reader [18] based on USRP platform, and measure 100 phase profiles by querying each tag 100 times with the USRP reader. The results are normalized by subtracting the average phase value of each result set. Therefore, 5000 normalized phase profiles are measured to evaluate the stability. As shown in Fig. 5(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 each step we measure 100 phase values individually. As shown in Fig. 5(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. Therefore, the phase profile is sensitive to any tiny movements, e.g., 1cm movement, which guarantees the distinctiveness of the phase profile in the motion detection. 4.3 Backscattered Link Frequency In regard to the backscatter link frequency (BLF) of the response signal, it can be represented as fl in Eq. (1). Due to the manufacturing imperfection, the BLF varies among different tags, which is used to distinguish tags [20], [22]. In fact, fl determines the data rate of the tag’s response. In regard to a typical encoding scheme Miller-4 of RFID system in Fig. 6(a), fl determines the duration of a binary symbol, i.e., bit-0 or bit-1. Therefore, both bit-0 and bit-1 have the same signal duration according to the Miller-4 encoding scheme. Since the binary length of RN16 signal is fixed, including the same preambles, a 16 bits random number and 1 check bit, it is reasonable to use the corresponding signal length of RN16 to represent the BLF. Meanwhile, we can also convert the signal length of RN16 to the BLF based on the actual symbols in RN16. In regard to other encoding schemes in RFID system, e.g., FM0, we can similarly use the signal length of RN16 to represent the BLF
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing Example of preamble 7700 15000 咖肌 Sliding window 010111 0000 Ending of RN16 n几几nn几u 500 0 dummy 1 6 L几uu几4几几 760 0 10 20 30 10 (a)RN16 signal (b)Cross-correlation Tag ID Signal length deviation Fig.6.Calculate signal length through cross-correlation.(a)shows the (a)BLF measurement (b)BLF histogram preamble and ending part of the RN16 signal.(b)shows to measure the Fig.7.Distinctiveness of BLF (a)shows the distribution of the BLF signal length with the cross-correlation method. values of different tags.(b)uses the histogram to present the variance of the extracted BLF feature. We present a cross-correlation based technology to ex- tract the signal length by locating the starting and ending Binomial distribution and the probability of a c-collision slot point of RN16 signal.Specifically,we adopt a slide window can be expressed as: to calculate the cross-correlation value between the mea- Pr(c)- (3) sured samples in the window and the special data sequence, -引 i.e.,the preamble or the "dummy 1".Then we find the Fig.8 shows the theoretical probability distribution of window whose cross-correlation value is the maximum,and different slot types.In this figure,in regard to the slot types, record the position of the window.In Fig.6(b),we move the '0'indicates the empty slot,'1'indicates the singleton slot, slide window forward to locate the starting point of RN16 and '2','3','4+'indicates the collision slot with different based on the preamble sequence.Similarly we can locate the number of collided tags in one slot.We enumerate the ending point using the"dummy 1",while moving the slide values of f/N,which are the ratio between the frame size window from the end of RN16 signal backward.We use f and the total tag number N(N is set to 1000 as default), the number of samples between the starting and the ending and calculate the distribution of each slot type according point to represent the value of the BLF. to Eq.(3).In regard to the C1G2 protocol,since it only To validate the distinctiveness of BLF,we conduct ex- receives signal from the singleton slot,it need to maximize periments on 50 different tags at 9 random positions in Pr(1)to improve the time efficiency.As a result,at most front of the antennas.We repeat querying each tag 100 36.8%slots are singleton when f equals to N.Then,about times with our USRP reader,and then extract the signal 63.2%slots are wasted,which severely affects the inventory lengths in different positions.As shown in Fig.7(a),the time efficiency.In this case,2-collision and 3-collision slots average signal length of 50 tags is randomly distributed occupy 18.4%and 6.13%slots respectively,while only 1.89% from 7620 to 7690 samples.Since the sampling rate of the slots are remained in 4+-collisions.So if we can efficiently USRP reader is 2MHz,the signal length is around 3.81ms resolve all the tags in singleton,2-collision and 3-collision to 3.845ms.It indicates that even though the same model slots,we can identify 36.8%+2 x 18.4%+3 x 6.13%=92% tags are queried with the same settings and the actual data tags in a frame,which is 2.5 times compared with current rates are different due to the manufacturing imperfection. protocol,i.e.,36.8%.Hence,we focus on how to extract Therefore,the distinctive value of BLF can be regarded as physical-layer features from 2-collision and 3-collision slots a unique physical-layer feature to distinguish among tags. to improve the time efficiency. Furthermore,we draw the histogram of the normalized variance of the signal length in Fig.7(b).The normalized signal length is relatively stable with an average deviation of 2 samples,which is equal to lus according to the 2MHz sampling rate.Therefore,the BLF is relatively stable and distinctive even though the tags are at different positions.But some tags have similar BLF values,meaning BLF cannot be used to uniquely differentiate the tags. 2 4+ Slot types 5 PHYSICAL-LAYER FEATURES EXTRACTION Fig.8.Theoretical probability distribution.The probability distribution of different kinds of collision slots in regard to the ratio between the frame FROM COLLISION SIGNAL size f and the number of tags N.N is set to 1000 as default. In the previous section,we have shown how to calculate 5.1 Model of Collision Signal the physical-layer features in the singleton slots.Such cal- culations can be used to collect the physical-layer features Extending Eq.(1)from a single tag to multiple tags,the re- in the tag inventory phase,since we leverage the traditional ceived baseband signal of a c-collision slot can be expressed C1G2 protocol [4]to identify the tags from the singleton as: slots.However,it is still time inefficient because we cannot s(t)=AeiB+(t)hi+(t) (4) avoid the useless collisions in C1G2 protocol.If c tags select the same slot to transmit the data,a c collision happens and Here,xi(t)is the binary bits sent by tag i over time t. such slots are wasted in C1G2 protocol.In fact,when we Aei represents the leakage signal from the reader.hi is the interrogate N tags with an f-slot frame based on the C1G2 channel coefficient of tag i and can be written as: protocol,the N tags select slots randomly according to the hi =B:ei2nft+0+B) (5) 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 5 0 5 1 0 dummy 1 dummy 1 0 1 0 1 1 1 Example of preamble Ending of RN16 (a) RN16 signal 1 0 1 1 1 Sliding window Cross correlation 0 1 0 1 1 1 (b) Cross-correlation Fig. 6. Calculate signal length through cross-correlation. (a) shows the preamble and ending part of the RN16 signal. (b) shows to measure the signal length with the cross-correlation method. We present a cross-correlation based 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, i.e., the preamble or the “dummy 1”. Then we find the window whose cross-correlation value is the maximum, and record the position of the window. In Fig. 6(b), we move the slide window forward to locate the starting point of RN16 based on the preamble sequence. Similarly we can locate the ending point using the “dummy 1”, while moving the slide window from the end of RN16 signal backward. We use the number of samples between the starting and the ending point to represent the value of the BLF. To validate the distinctiveness of BLF, we conduct experiments on 50 different tags at 9 random positions in front of the antennas. We repeat querying each tag 100 times with our USRP reader, and then extract the signal lengths in different positions. As shown in Fig. 7(a), the average signal length of 50 tags is randomly distributed from 7620 to 7690 samples. Since the sampling rate of the USRP reader is 2MHz, the signal length is around 3.81ms to 3.845ms. It indicates that even though the same model tags are queried with the same settings and the actual data rates are different due to the manufacturing imperfection. Therefore, the distinctive value of BLF can be regarded as a unique physical-layer feature to distinguish among tags. Furthermore, we draw the histogram of the normalized variance of the signal length in Fig. 7(b). The normalized signal length is relatively stable with an average deviation of 2 samples, which is equal to 1µs according to the 2MHz sampling rate. Therefore, the BLF is relatively stable and distinctive even though the tags are at different positions. But some tags have similar BLF values, meaning BLF cannot be used to uniquely differentiate the tags. 5 PHYSICAL-LAYER FEATURES EXTRACTION FROM COLLISION SIGNAL In the previous section, we have shown how to calculate the physical-layer features in the singleton slots. Such calculations can be used to collect the physical-layer features in the tag inventory phase, since we leverage the traditional C1G2 protocol [4] to identify the tags from the singleton slots. However, it is still time inefficient because we cannot avoid the useless collisions in C1G2 protocol. If c tags select the same slot to transmit the data, a c collision happens and such slots are wasted in C1G2 protocol. In fact, when we interrogate N tags with an f -slot frame based on the C1G2 protocol, the N tags select slots randomly according to the Tag ID 0 10 20 30 40 50 Signal length 7600 7620 7640 7660 7680 7700 (a) BLF measurement Signal length deviation -10 -5 0 5 10 Counts 0 5000 10000 15000 (b) BLF histogram Fig. 7. Distinctiveness of BLF. (a) shows the distribution of the BLF values of different tags. (b) uses the histogram to present the variance of the extracted BLF feature. Binomial distribution and the probability of a c-collision slot can be expressed as: Pr(c) = N c 1 f c 1 − 1 f N−c . (3) Fig. 8 shows the theoretical probability distribution of different slot types. In this figure, in regard to the slot types, 00 0 indicates the empty slot, 01 0 indicates the singleton slot, and 02 0 , 03 0 , 04+ 0 indicates the collision slot with different number of collided tags in one slot. We enumerate the values of f /N, which are the ratio between the frame size f and the total tag number N (N is set to 1000 as default), and calculate the distribution of each slot type according to Eq. (3). In regard to the C1G2 protocol, since it only receives signal from the singleton slot, it need to maximize Pr(1) to improve the time efficiency. As a result, at most 36.8% slots are singleton when f equals to N. Then, about 63.2% slots are wasted, which severely affects the inventory time efficiency. 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 36.8% + 2 × 18.4% + 3 × 6.13% = 92% tags in a frame, which is 2.5 times compared with current protocol, i.e., 36.8%. Hence, we focus on how to extract physical-layer features from 2-collision and 3-collision slots to improve the time efficiency. Slot types 0 1 2 3 4+ f/N 0 1 2 3 4 5 0 0.2 0.4 0.6 0.8 Fig. 8. Theoretical probability distribution. The probability distribution of different kinds of collision slots in regard to the ratio between the frame size f and the number of tags N. N is set to 1000 as default. 5.1 Model of Collision Signal Extending Eq. (1) from a single tag to multiple tags, the received baseband signal of a c-collision slot can be expressed as: s(t) = Aejβ + Õc i=1 xi(t)hi + nˆ(t). (4) Here, xi(t) is the binary bits sent by tag i over time t. Aejβ represents the leakage signal from the reader. hi is the channel coefficient of tag i and can be written as: hi = Bie j(2π fl t+θi+β)) , (5)
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing S5 Tag A Tag B 00 s00 10001500 2000 S2 Leakage signal 0S6 0 Sample time (us) S6 (a)2-collision model (b)2-collision signal (c)Case 1 for 3-collision model (d)Case 1 for 3-collision model Fig.9.Model of collision signal.(a)shows the signal model of the 2-collision slot in the I-Q plane.(b)shows the preamble part of the corresponding 2-collision signal in the time domain and illustrates the I-Q state in the time domain.(c)shows case 1 for the 3-collision slot in the l-Q plane.(d) shows case 2 for the 3-collision slot in the I-Q plane. where B:is the amplitude and 0;is the phase profile of tag i. sample distribution in I-Q plane.Then we pick the peaks of Similar to the model in Fig.4,hi describes the backscattered density function as the centers of clusters based on [171. signal in I-O plane as a vector,thus the collided signal of After clustering,we will get four cluster centers,which the c tags can be represented as the superposition of the represent four states similar to Fig.9(a).As So only contains backscattered signal and the leakage signal. the leakage signal,which can be estimated from the continu- Taking a 2-collision as an example in Fig.9(a),since both ous wave,we can first determine the state So.Since both tags tag A and B send a binary bit,the superposition signal are transmitting the same data during the preamble,signals based on the combination of the two binary bits forms four are switching between state So and S3 during the preamble different states So ~S3 in I-Q plane.State So means both as shown in Fig.9(b).Therefore,we can determine the state tag A and B are transmitting xi(t)=0,therefore the signal S3 using the preamble part,which contains only So and S3 contains only one component:the leakage signal.State S3 Then,the remained two states are S and S2 respectively. means both tag A and B are transmitting xi(1)=1,therefore At last,we calculate the channel coefficients of each tag as the signal is superposition of the leakage signal and the h1=C(S1)-C(So)and h2=C(S2)-C(So),where C(Si)is Si in backscattered signals.For state S and S2,only one tag is the I-Q plane. transmitting bit 1,therefore the signal is the combination of the leakage signal and the backscattered signal of the 5.2.2 Channel Coefficients Estimation for 3-collision Signal corresponding tag.Here,the key step to decompose the When the number of collided tags increases to three,the backscattered signals of different tags is to efficiently resolve signal states can be represented with a three-bit binary.This these states and extract the channel coefficients h. means there are 8 states,which is much more complex, because we need to define 4 more states compared to 2- 5.2 Channel Coefficients Estimation from Collision collision problem.Based on the combination of vectors from Signal 3 backscattered signals in I-Q plane,the 8 states constitute Based on the above model,the superposition of the a parallelepiped.Our basic idea is that since the 3-collision backscattered signals constitute different states in I-Q plane, signal can be always represented as the superposition of which represents different binary bits sent by the collided 2-collision signal and one tag signal,we can resolve a 2- tags.Hence,we next demonstrate how to resolve the signal collision problem inside the 3-collision problem and then states so as to extract features from collision signal.Firstly, handle the 3rd tag signal.Taking Fig.9(c)as an example,the we need to find out which combination of binary bits each parallelogram So.S2S6S4 and S1S3.S7S5 are the superposition of state represents,e.g.,in Fig.9(a)So represents two bit 0. two tags and the vector pointing from one parallelogram to Secondly,we calculate the channel coefficient hi of each tag another represents the signal of the 3rd tag.By resolving using the positions of states.Lastly,for each signal sample one parallelogram,we can get the channel coefficients of s(t)we estimate the binary bits xi(t)of tag i according to Eq. two tags and further calculate the coefficients of the 3rd tag. (4)as: To find the parallelogram in the parallelepiped,we di- vide the states into two parts according to their ranks of arg min |s(t)- ∑(x0·)-Ae形，where x()e{0,1.(6) amplitude.Due to the geometric feature,the four states xi() i-1 with smaller amplitudes can either constitute a parallelogram Eq.(6)chooses the combination of xi(t),such that the error as shown in Fig.9(c),or a plane tetrahedron as shown in between the sample s(t)and the generated collided signal, Fig.9(d).For the parallelogram case,we have found the par- i.e.,f(xi(t).h)is minimized.Then,we can calculate the allelogram such as Fig.9(c).For the plane tetrahedron case, phase profiles from the channel coefficient hi of each tag and the edges among the four states inside the parallelepiped calculate the BLFs from the binary sequence xi of each tag intersect at one state,e.g.,in Fig.9(d)three vectors intersect based on the cross-correlation method. at S2.For this situation,we can exchange one of the other three states with a symmetrical state,e.g.,replacing S3 with 5.2.1 Channel Coefficients Estimation for 2-collision Signal S4 in Fig.9(d),to constitute a parallelogram.Then,we will According to the above analysis,we next resolve the signal find the parallelogram so as to further extract the channel states in 2-collision problem.There are four states in a 2- coefficients. collision slot,which is the size of two-bit binary.When we The detailed steps for estimating the channel coefficients get the collision signals,we first acquire the positions of each in 3-collision slot are as follows:Firstly,we cluster signals state by clustering all the samples into clusters based on the into 8 clusters,similar as in the 2-collision problem.Sec- 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 6 I Q Leakage signal Tag A Tag B S0 S3 S1 S2 (a) 2-collision model Sample # 1000 2000 3000 4000 Magnitude 6000 6200 6400 Sample time (µs) 500 1000 1500 2000 Amplitude S0 S3 S0 S3 (b) 2-collision signal (c) Case 1 for 3-collision model (d) Case 1 for 3-collision model Fig. 9. Model of collision signal. (a) shows the signal model of the 2-collision slot in the I-Q plane. (b) shows the preamble part of the corresponding 2-collision signal in the time domain and illustrates the I-Q state in the time domain. (c) shows case 1 for the 3-collision slot in the I-Q plane. (d) shows case 2 for the 3-collision slot in the I-Q plane. where Bi is the amplitude and θi is the phase profile of tag i. Similar to the model in Fig. 4, hi describes the backscattered signal in I-Q plane as a vector, thus the collided signal of the c tags can be represented as the superposition of the backscattered signal and the leakage signal. Taking a 2-collision as an example in Fig. 9(a), since both tag A and B send a binary bit, the superposition signal based on the combination of the two binary bits forms four different states S0 ∼ S3 in I-Q plane. 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 leakage signal and the backscattered signals. 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. Here, the key step to decompose the backscattered signals of different tags is to efficiently resolve these states and extract the channel coefficients hi . 5.2 Channel Coefficients Estimation from Collision Signal Based on the above model, the superposition of the backscattered signals constitute different states in I-Q plane, which represents different binary bits sent by the collided tags. Hence, we next demonstrate how to resolve the signal states so as to extract features from collision signal. Firstly, we need to find out which combination of binary bits each state represents, e.g., in Fig. 9(a) S0 represents two bit 0. Secondly, we calculate the channel coefficient hi of each tag using the positions of states. Lastly, for each signal sample s(t) we estimate the binary bits xi(t) of tag i according to Eq. (4) as: arg min xi(t) |s(t) − Õc i=1 (xi(t) · hi) − Aejβ |, where xi(t) ∈ {0, 1}. (6) Eq. (6) 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. Then, we can calculate the phase profiles from the channel coefficient hi of each tag and calculate the BLFs from the binary sequence xi of each tag based on the cross-correlation method. 5.2.1 Channel Coefficients Estimation for 2-collision Signal According to the above analysis, we next resolve the signal states in 2-collision problem. There are four states in a 2- collision slot, 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 based on [17]. After clustering, we will get four cluster centers, which represent four states similar to Fig. 9(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. 9(b). Therefore, we can determine the state S3 using the preamble part, which contains only S0 and S3. Then, 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. 5.2.2 Channel Coefficients Estimation for 3-collision Signal 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 vectors from 3 backscattered signals in I-Q plane, the 8 states constitute a parallelepiped. Our basic idea is that since the 3-collision signal can be always represented as the superposition of 2-collision signal and one tag signal, we can resolve a 2- collision problem inside the 3-collision problem and then handle the 3rd tag signal. Taking Fig. 9(c) as an example, the parallelogram S0S2S6S4 and S1S3S7S5 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. 9(c), or a plane tetrahedron as shown in Fig. 9(d). For the parallelogram case, we have found the parallelogram such as Fig. 9(c). For the plane tetrahedron case, the edges among the four states inside the parallelepiped intersect at one state, e.g., in Fig. 9(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. 9(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. Sec-
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing -3600 100 3800 8000 8100 8200 830 80 400 420 79008000810082008300 440 20 46 10 2030 50 4000 4500 7900 80008100 8200 830 Grid X Inphase Sample Counts (a)Histogram of signal in I-Q plane (b)Signal in I-Q plane and the state division (c)Extracted RN16 signals of three tags Fig.10.Extract physical-layer features from 3-collision signal.(a)shows the distribution of the 3-collision signal in the l-Q plane.(b)shows the state division of the 3-collision signal based on the 3-collision model.(c)shows the extracted RN16 signal of three collision tags and uses rectangles to mark the ending part according to the cross-correlation method ondly,we determine state So and Sz from the preamble, coefficient,which is the phase difference between the two because all the three tags transmit the same data and signal states bit'0'and bit '1'in the I-Q phase. switches between state So and S7.Here,So means all the In regard to the BLF,we utilize Eq.(6)to roughly recover three tags transmit xi(t)=0 and S7 means xi(t)=1.Thirdly, the RN16 signal of each tag and calculate the signal length of we search for the parallelogram in the parallelepiped.We RN16 for each tag.Particularly,we have already estimated sort the eight states based on the amplitudes of cluster the channel coefficient of each tag as hi and the summation centers.Based on the analysis above,then we search for of the signal of all the tags has been measured as s(t).Then the parallelogram among first five states with smaller am- we can calculate the binary samples of each tag as xi(t)from plitudes.There are only two possible choices:1)For the h;and s(t)based on Eg.(6).Here,the value of binary bit parallelogram case we can use 1st~4th state to constitute trace xi(r)is set to either'0'or'1'.Due to the large noise a parallelogram.2)For the plane tetrahedron case,we can of the collision signal,it is usually difficult to accurately replace 4th state with 5th and use 1st~3rd and 5th state to decode the binary bit trace.It means that even though the constitute a parallelogram. whole trace of xi(t)is almost correct,some samples may To decide the correct choice of parallelogram,we lever- be incorrect,which is later shown in Fig 10(c).However, age the property that the opposite sides of parallelogram are according to the special encoded pattern of preamble and parallel and equal in length.For each choice there are three "dummy 1"as shown in Fig.6(a),we can still determine the possible edge pairs.If we use the rank of state to represent starting and ending point. the vertex,the three pairs are (12,34),(13,24)and (14,23) Specifically,we first use the moving average method in choice 1.We use the similarity among the edge pairs to to smooth the recovered binary trace xi(t)and reduce the express the likelihood of constituting a parallelogram as: influence of the incorrect samples.Then we adopt the cross- a.b 1 correlation process similar to Section 4.3 to decide the signal Sim= (7 1a×(a- length.The cross-correlation method calculates the similar- ity between the special encoded pattern and the recovered where(d,b)is the possible edge pair.The left part in the trace xi(t).The similarity will reach the peak when the trace multiplier is the cosine value of the edge pair and the xi(t)is the same as the special encoded pattern,which is right part is the reciprocal of the length difference.We regarded as the starting and ending point of RN16 for each choose the edge pair with the maximum similarity as the tag i.Finally,we use the length between the starting and corresponding opposite side of the parallelogram.Then we ending point as the indicator of BLF. can resolve the vertex sequence of the parallelogram based 5.4 Case Study on the similarity. Lastly,we measure the channel coefficients of each tag Fig.10 presents an example of extracting the physical-layer based on the geometric construction in the I-Q plane.Based features from a 3-collision slot.Firstly,we cluster the sam- on our division,the selected parallelogram will always ples into eight clusters based on the density function in the include either state So or S7.Hence,we can measure the two I-Q plane as shown in Fig.10(a).In the following we denote channel coefficients in the parallelogram according to the each state according to the amplitude rank of states in the states So and S similar as in the 2-collision problem.Since I-Q plane.Secondly,we determine state So from continuous S7 contains three channel coefficients and So contains none, wave and state S7 from the preamble as shown in Fig.10(b) the channel coefficient of the 3rd tag can be easily computed Thirdly,we search for the parallelogram based on the first 5 based on So,S7 and the first two channel coefficients. states.The left quadrilateral in Fig.10(b)is the estimated parallelogram and the right one is the symmetrical one. 5.3 Features Estimation from Collision Signal Fourthly,we calculate the channel coefficients including After extracting the channel coefficients from the collision the phase profiles,which is shown as the arrow in the slot,we can directly compute the phase profile based on Eq. figure.Lastly,we recover the RN16 bit trace of each tag (2).Suppose the channel coefficient for tag i is estimated as according to Eq.(6).We compute the signal length of RN16 hi.Then it represents that hi includes two states according as the indicator of BLF based on cross-correlation results to the estimation method for channel coefficient:one for bit Fig.10(c)shows the ending part of three separated RN16 0'and one for bit '1'.According to Eq.(2),we can then signals and points out the slide window which has the peak calculate the phase profile of the tag based on the channel cross-correlation value.In this figure,we can clearly see the 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 7 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 S0 S7 (b) Signal in I-Q plane and the state division 7800 7900 8000 8100 8200 8300 -1 0 1 2 Amplitude 7800 7900 8000 8100 8200 8300 -1 0 1 2 Amplitude 7800 7900 8000 8100 8200 8300 Sample Counts -1 0 1 2 Amplitude (c) Extracted RN16 signals of three tags Fig. 10. Extract physical-layer features from 3-collision signal. (a) shows the distribution of the 3-collision signal in the I-Q plane. (b) shows the state division of the 3-collision signal based on the 3-collision model. (c) shows the extracted RN16 signal of three collision tags and uses rectangles to mark the ending part according to the cross-correlation method. ondly, 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 parallelepiped. We sort the eight states based on the amplitudes of cluster centers. Based on the analysis above, then we search 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 of parallelogram, 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®|) , (7) where (a®, b®) is the possible edge pair. The left part in the multiplier is the cosine value of the edge pair and the right 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 of each tag based on the geometric construction in the I-Q plane. Based on our division, the selected parallelogram will always include either state S0 or S7. 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. Since S7 contains three channel coefficients and S0 contains none, the channel coefficient of the 3rd tag can be easily computed based on S0, S7 and the first two channel coefficients. 5.3 Features Estimation from Collision Signal After extracting the channel coefficients from the collision slot, we can directly compute the phase profile based on Eq. (2). Suppose the channel coefficient for tag i is estimated as hi . Then it represents that hi includes two states according to the estimation method for channel coefficient: one for bit 00 0 and one for bit 01 0 . According to Eq. (2), we can then calculate the phase profile of the tag based on the channel coefficient, which is the phase difference between the two states bit 00 0 and bit 01 0 in the I-Q phase. In regard to the BLF, we utilize Eq. (6) to roughly recover the RN16 signal of each tag and calculate the signal length of RN16 for each tag. Particularly, we have already estimated the channel coefficient of each tag as hi and the summation of the signal of all the tags has been measured as s(t). Then we can calculate the binary samples of each tag as xi(t) from hi and s(t) based on Eq. (6). Here, the value of binary bit trace xi(t) is set to either 00 0 or 01 0 . Due to the large noise of the collision signal, it is usually difficult to accurately decode the binary bit trace. It means that even though the whole trace of xi(t) is almost correct, some samples may be incorrect, which is later shown in Fig 10(c). However, according to the special encoded pattern of preamble and “dummy 1” as shown in Fig. 6(a), we can still determine the starting and ending point. Specifically, we first use the moving average method to smooth the recovered binary trace xi(t) and reduce the influence of the incorrect samples. Then we adopt the crosscorrelation process similar to Section 4.3 to decide the signal length. The cross-correlation method calculates the similarity between the special encoded pattern and the recovered trace xi(t). The similarity will reach the peak when the trace xi(t) is the same as the special encoded pattern, which is regarded as the starting and ending point of RN16 for each tag i. Finally, we use the length between the starting and ending point as the indicator of BLF. 5.4 Case Study Fig. 10 presents 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 the I-Q plane as shown in Fig. 10(a). In the following we denote each state according to the amplitude rank of states in the I-Q plane. Secondly, we determine state S0 from continuous wave and state S7 from the preamble as shown in Fig. 10(b). Thirdly, we search for the parallelogram based on the first 5 states. The left quadrilateral in Fig. 10(b) is the estimated parallelogram and the right one is the symmetrical one. Fourthly, we calculate the channel coefficients including the phase profiles, which is shown as the arrow in the figure. Lastly, we recover the RN16 bit trace of each tag according to Eq.(6). We compute the signal length of RN16 as the indicator of BLF based on cross-correlation results. Fig. 10(c) shows the ending part of three separated RN16 signals and points out the slide window which has the peak cross-correlation value. In this figure, we can clearly see the
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing recovered RN16 signal of each tag.The covered trace is not P2 the perfect square wave,which has some noise.It is caused 1920 by the incorrect calculated binary bits.We use the moving 194 180 10 average method to smooth the whole trace and reduce the 84° 999 150 4 98° 12 effect of these incorrect bits Ts 98 Ts 288° 70360 MOVING OBJECT DETECTION VIA A SINGLE TAG Fig.11.Example of multi-dimensional phase profile.By using the 2 6.1 Motivation and Intuition dimensional phase profile,each tag can be uniquely distinguished com- pared with the 1-dimensional phase profile. As shown in Section 4.3,BLF is only able to differentiate in the figure.We can clearly see that 73 can be uniquely dozens of tags,but cannot distinguish tags with the same detected,because no tag has similar 2-dimensional phase BLF.However,in our scenario,the most tags are stationary, profile with T3. meaning we can also use the unique positions,i.e.,phase In actual applications,we can exploit with a transmitting profiles,to represent each static tag.Therefore,we can com- antenna and multiple receiving antennas to acquire the bine BLF and phase profiles to detect the moving tags,which multiple distributions [25].But combining multiple distribu- integrates both the inherent tag features and the position- tions to construct a multi-dimensional phase profile is still related tag features.In this section,we focus on how to challenging,because we do not obtain the tag IDs.Taking detect the moving tags by using the phase profiles,after Fig.11 as an example,if tag Ti collides with T2 in a 2- extracting the physical-layer features.BLF can be combined collision,we can extract the phase profiles 7 and 194 from with the phase profile similarly. one antenna and 192 and 18 from another antenna.But we The phase profile always changes if the tag moves,even cannot determine whether the phase pair(7,192)belongs if the moving distance is small,thus the basic idea is to com- to the same tag or not,because we do not have the tag pare the updated phase profiles with the stationary phase IDs.Fortunately,the two antennas receive the same collision profiles.Suppose the stationary phase profiles of the N tags signal in the physical layer,meaning the BLFs of the same obtained in the tag inventory phase is P =(01,02....,ON), tag from the two antennas should match perfectly.Based on where 0i is the ith phase profile.In the each continuous the understanding,we can combine 7 and 192 together, polling cycle,we also obtain the updated phase distribution if the corresponding BLF values are similar.We can easily P'=(0.0...).We compare p'with P to detect the extend the matching method to multi-dimensional phase moving tags in each polling cycle.For the convenience of profile,where we use multiple receiving antennas. demonstration,we use the terms "phase profile","tag"in- Therefore,the process of constructing the multi- terchangeably to represent the corresponding phase profile. dimensional phase profile consists of two steps:We first Traditional C1G2 protocol usually costs tens of seconds try to extract the physical-layer features from the receiving from singleton slots to obtain the phase distribution,which signal of each antenna individually.For singleton slots,we is quite inefficient due to the collision problem and the long just directly combine the phase values together to construct EPC-ID signal.Instead,we can extract the phase distribution a multi-dimensional phase profile.For a c-collision slot,we P'only from the RN16 signal of collision signal.Hence,we combine the phase profiles received from different antennas propose a Fast Tag Polling (FTP)scheme by suppressing by matching the BLFs to construct c multi-dimensional the transmitting of EPC-ID signal with a new command phase profiles. QrepSup.The QrepSup command is used to respond the RN16 signal of the tags.It not only starts the next slot 6.3 Moving Tag Detection via Graph Matching like the Qrep command in C1G2,but also makes the tags, Based on the two phase distributions P and P',we demon- which is resolved in the collision slot,silent for the following strate how to detect the moving tags by comparing the two frames in the query cycle.Based on the FTP scheme,we can phase distributions.The intuition is that for a stationary tag, acquire the phase distribution P'in a short time in every its phase profile should be stable between the two distri- polling cycle. butions,while for a moving tag,its phase profile should change across the two distributions.Therefore,if we can 6.2 Multi-dimensional Phase Distribution Construction match the stationary tags together,the rest tags are moving. Even though the movements of tags lead to the difference So the moving tag detection problem is transformed into between the two phase distributions P and P,the phase a matching problem of stationary tags.In particular,we profile extracted from one antenna cannot sufficiently dis- calculate the Euclidean distance di;between the ith phase tinguish the moving tags due to the following two reasons: profile 0i in distribution P and the jth phase profile 0;in p' 1)The phase value is periodical,meaning different tags may as. have the same phase profile.2)Measurement errors of phase dij =lle:-0fll (⑧) profile will affect the accuracy of moving detection. Thus,if 0i and e;belong to the same stationary tag,the Fig.11 presents a simple example.P and P2 are two distance dij should be small.Otherwise,the distance dij phase distributions of five tags Ti~T5 measured by two should be large,because dij represents either the phase antennas.We find that 72 and 73 have similar phase profile change of the moving tag or the phase difference of two in P1,and T3 and T4 also have similar phase profile in P2. different tags,i.e.,a random distance.Supposing k is an Therefore,we cannot uniquely distinguish each tag based empirical threshold about the phase variance of a stationary on the phase profile from one antenna.To solve the problem, tag,we can use it to filter the obvious abnormal distance we can combine the two phase profiles together as a 2- by setting di.j,whose value exceeds k,to oo.So if we can dimensional phase profile,which is shown as the matrix match the phase profiles in the two distributions,so that the 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 8 recovered RN16 signal of each tag. The covered trace is not the perfect square wave, which has some noise. It is caused by the incorrect calculated binary bits. We use the moving average method to smooth the whole trace and reduce the effect of these incorrect bits. 6 MOVING OBJECT DETECTION VIA A SINGLE TAG 6.1 Motivation and Intuition As shown in Section 4.3, BLF is only able to differentiate dozens of tags, but cannot distinguish tags with the same BLF. However, in our scenario, the most tags are stationary, meaning we can also use the unique positions, i.e., phase profiles, to represent each static tag. Therefore, we can combine BLF and phase profiles to detect the moving tags, which integrates both the inherent tag features and the positionrelated tag features. In this section, we focus on how to detect the moving tags by using the phase profiles, after extracting the physical-layer features. BLF can be combined with the phase profile similarly. The phase profile always changes if the tag moves, even if the moving distance is small, thus the basic idea is to compare the updated phase profiles with the stationary phase profiles. Suppose the stationary phase profiles of the N tags obtained in the tag inventory phase is P = hθ1, θ2, · · · , θN i, where θi is the ith phase profile. In the each continuous polling cycle, we also obtain the updated phase distribution P 0 = hθ 0 1 , θ0 2 , · · · , θ0 N i. We compare P 0 with P to detect the moving tags in each polling cycle. For the convenience of demonstration, we use the terms “phase profile”, “tag” interchangeably to represent the corresponding phase profile. Traditional C1G2 protocol usually costs tens of seconds from singleton slots to obtain the phase distribution, which is quite inefficient due to the collision problem and the long EPC-ID signal. Instead, we can extract the phase distribution P 0 only from the RN16 signal of collision signal. Hence, we propose a Fast Tag Polling (FTP) scheme 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 in the query cycle. Based on the FTP scheme, we can acquire the phase distribution P 0 in a short time in every polling cycle. 6.2 Multi-dimensional Phase Distribution Construction Even though the movements of tags lead to the difference between the two phase distributions P and P 0 , the phase profile extracted from one antenna cannot sufficiently distinguish 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) Measurement errors of phase profile will affect the accuracy of moving detection. Fig. 11 presents a simple example. P1 and P2 are two phase distributions of five tags T1 ∼ T5 measured by two antennas. We find that T2 and T3 have similar phase profile in P1, and T3 and T4 also have similar phase profile in P2. Therefore, we cannot uniquely distinguish each tag based on the phase profile from one antenna. To solve the problem, we can combine the two phase profiles together as a 2- dimensional phase profile, which is shown as the matrix 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. 11. Example of multi-dimensional phase profile. By using the 2- dimensional phase profile, each tag can be uniquely distinguished compared with the 1-dimensional phase profile. in the figure. We can clearly see that T3 can be uniquely detected, because no tag has similar 2-dimensional phase profile with T3. In actual applications, we can exploit with a transmitting antenna and multiple receiving antennas to acquire the multiple distributions [25]. But combining multiple distributions to construct a multi-dimensional phase profile is still challenging, because we do not obtain the tag IDs. Taking Fig. 11 as an example, if tag T1 collides with T2 in a 2- collision, we can extract the phase profiles 7◦ and 194◦ from one antenna and 192◦ and 18◦ from another antenna. But we cannot determine whether the phase pair h7 ◦ , 192◦ i belongs to the same tag or not, because we do not have the tag IDs. Fortunately, the two antennas receive the same collision signal in the physical layer, meaning the BLFs of the same tag from the two antennas should match perfectly. Based on the understanding, we can combine 7◦ and 192◦ together, if the corresponding BLF values are similar. We can easily extend the matching method to multi-dimensional phase profile, where we use multiple receiving antennas. Therefore, the process of constructing the multidimensional 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 combine the phase values together to construct a multi-dimensional phase profile. For a c-collision slot, we combine the phase profiles received from different antennas by matching the BLFs to construct c multi-dimensional phase profiles. 6.3 Moving Tag Detection via Graph Matching Based on the two phase distributions P and P 0 , we demonstrate how to detect the moving tags by comparing the two phase distributions. The intuition is that for a stationary tag, its phase profile should be stable between the two distributions, while for a moving tag, its phase profile should change across the two distributions. Therefore, if we can match the stationary tags together, the rest tags are moving. So the moving tag detection problem is transformed into a matching problem of stationary tags. In particular, we calculate the Euclidean distance di,j between the ith phase profile θi in distribution P and the jth phase profile θ 0 j in P 0 as: di,j = ||θi − θ 0 j ||. (8) Thus, if θi and θ 0 j belong to the same stationary tag, the distance di,j should be small. Otherwise, the distance di,j should be large, because di,j represents either the phase change of the moving tag or the phase difference of two different tags, i.e., a random distance. Supposing κ is an empirical threshold about the phase variance of a stationary tag, we can use it to filter the obvious abnormal distance by setting di,j , whose value exceeds κ, to ∞. So if we can match the phase profiles in the two distributions, so that the
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing 9 Al A2 A3 Al A2 A3 Moving Tag Stationary Tags Updated Distribution Stationary Distribution Pr Fig.12.Matching moving tags from phase profile.We compare the Time(s) phase profiles with the stationary distribution to detect the moving tags. (a)Measured phase of four tags (b)Correlation among four tags overall sum of distances for these matchings is the minimum among all the possible matchings,then only the stationary Fig.13.Experimental result of moving a carton box with four tags. (a)shows the phase changes of four different tags.(b)shows the tags should be matched,because the distances of the moving correlations among these four tags. tags are large in statistic. Matching between the two phase distributions can be detected as moving/missing tags based on the GM method reduced to an arrangement problems.For the first tag in due to the misreading.When the wireless environment P,we have N phase profiles in the undated distribution becomes better,these tags can usually be successfully identi- to arrange,and for the second tag,we have N-1 phase fied later.To solve the false detection,one intuitive solution profiles to arrange.It means for all the N tags in P,there are is to expand the detection cycle,i.e.,any tag is regarded as a N×(W-1)×…×1 possible matchings.It is not suitable to moving tag if it is detected as moving for several continuous enumerate all the possible matchings since the complexity cycles.However,this solution delays the detection time and is O(N!).So we propose a Graph Matching(GM)method by affects the system performance.In this paper,we propose employing the Hungarian algorithm [26]to solve the prob- to attach multiple tags on the object for the detection of lem in polynomial time.Firstly,we calculate the pairwise moving/missing events.The basic idea is to determine distance between distributions P and P'according to Eq. the moving status from the majority tags attached on the (8).It is a N x N matrix DNxN.Secondly,we filter all the object,so that a portion of reading errors will not affect the unlikely pairs by setting the distance in DNxN,whose value detection result.Additionally,based on the redundant tag exceeds k,to oo.Thirdly,we utilize DNxN as the input of deployment,it is possible to distinguish the moving objects the Hungarian algorithm and get a matching result.Lastly, from the missing objects,and even identify the newly joined we pick up all the tags in P,whose phase profiles are tags,which are moved in from outside. unmatched,as the moving tags. 7.2 Phase Variance of Multiple Tags Fig.12 shows an example of the matching process.We use two gray matrices to represent the two distributions We first study the phase variance of the multiple tags P and P'of five tags from three antennas,i.e.,A1,A2 and attached on a moving object via a real experiment.Even though these tags may also rotate along with the objects, A3.We use the color of gray grid to represent the value of the moving effect can be usually much larger than the phase profiles,and three gray grids in one line represent rotation effect,when the tags are deployed vertically in the three phase profiles of one tag received by antenna A1, warehouse [27].Therefore,we neglect the rotation effect and A2 and A3.The objective is to match the static tags in the focus on the moving effect.When an object is moving,all the two distributions together,where the distance between the attached tags are under the same movement with the object, three matching phase profiles in P and p'is the smallest. leading to the similar phase variance across these tags.To We use dashed lines to represent all the possible matching schemes and calculate the distances of them.The Hungar- validate the hypothesis,we conduct an empirical study in the realistic environment by moving a carton box attached ian algorithm takes the distances as input and returns the with four tags.Particularly,we continuously move the car- matchings,represented as the solid lines in the figure.So ton box 40cm in front of the antenna,and measure the phase we can detect the moving tag as unmatched one,which is values of these tags simultaneously.Fig.13(a)presents the marked with a circle. phase variances of the four tags during the movement of Currently,the phase profile is the main factor to detect the box.We find that the measured phase values of the four the motion status,where the BLF is used to construct the tags are similar as expected.We call such phase variance multi-dimensional phase profile.In fact,since BLF is an the coherent phase variance of the multiple tags on the same inherent feature,it can be further used to distinguish the object.We further present the correlation matrix among the tags with similar phase profiles.We can add BLF into the four phase sequences in Fig.13(b).We note that all of the distance calculation of the GM method,which may act as correlation values are larger than 99%,which indicates they one more dimension of the phase profiles.Then,we can distinguish the tags,whose phase distance is small but BLF have the same variance pattern.Therefore,it is reasonable to use the coherent variance pattern to facilitate the detection distance is large. of moving objects. 7 MOVING OBJECTS DETECTION VIA MULTIPLE 7.3 Moving Objects Detection from Unmatched Tags TAGS Next we demonstrate how to use the coherent phase vari- 7.1 Motivation and Intuition ance pattern to determine the moving objects.Consider we In practical environment,RFID systems usually suffer from have detected the moving tags by matching between the sta- various degrees of misreading phenomenon.As a result, tionary phase distribution P and updated phase distribution even though some tags are stationary,they are likely to be P'based on the GM method in Section 6.Denote the phase 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 9 !"#$%&' ()& *+)+$"%),-' ()&. /0 /1 /2 /0 /1 /2 345)+65' 7$.+,$89+$"% *+)+$"%),-' 7$.+,$89+$"% ! !" Fig. 12. Matching moving tags from phase profile. We compare the phase profiles with the stationary distribution to detect the moving tags. 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. Matching between the two phase distributions can be reduced to an arrangement problems. For the first tag in P, we have N phase profiles in the undated distribution to arrange, and for the second tag, we have N − 1 phase profiles to arrange. It means for all the N tags in P, there are N × (N − 1) × · · · × 1 possible matchings. It is not suitable to enumerate all the possible matchings since the complexity is O(N!). So we propose a Graph Matching (GM) method by employing the Hungarian algorithm [26] to solve the problem in polynomial time. Firstly, we calculate the pairwise distance between distributions P and P 0 according to Eq. (8). 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. 12 shows an example of the matching process. We use two gray matrices to represent the two distributions P and P 0 of five tags from three antennas, i.e., A1, A2 and A3. We use the color of gray grid to represent the value of phase profiles, and three gray grids in one line represent three phase profiles of one tag received by antenna A1, A2 and A3. The objective is to match the static tags in the two distributions together, where the distance between the three matching phase profiles in P and P 0 is the smallest. We use dashed lines to represent all the possible matching 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. Currently, 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, since BLF is an inherent feature, it can be further used to distinguish the tags with similar phase profiles. We can add BLF into the distance calculation of the GM method, which may act as one more dimension of the phase profiles. Then, we can distinguish the tags, whose phase distance is small but BLF distance is large. 7 MOVING OBJECTS DETECTION VIA MULTIPLE TAGS 7.1 Motivation and Intuition In practical environment, RFID systems usually suffer from various degrees of misreading phenomenon. As a result, even though some tags are stationary, they are likely to be Time (s) 0 2 4 6 Phase (radian) -15 -10 -5 0 5 Tag 1 Tag 2 Tag 3 Tag 4 (a) Measured phase of four tags 1.00000 0.99419 0.99302 0.99252 0.99419 1.00000 0.99007 0.99162 0.99302 0.99007 1.00000 0.99453 0.99252 0.99162 0.99453 1.00000 Tag ID 1 2 3 4 Tag ID 1 2 3 4 0.99 0.991 0.992 0.993 0.994 0.995 0.996 0.997 0.998 0.999 1 (b) Correlation among four tags Fig. 13. Experimental result of moving a carton box with four tags. (a) shows the phase changes of four different tags. (b) shows the correlations among these four tags. detected as moving/missing tags based on the GM method due to the misreading. When the wireless environment becomes better, these tags can usually be successfully identi- fied later. To solve the false detection, one intuitive solution is to expand the detection cycle, i.e., any tag is regarded as a moving tag if it is detected as moving for several continuous cycles. However, this solution delays the detection time and affects the system performance. In this paper, we propose to attach multiple tags on the object for the detection of moving/missing events. The basic idea is to determine the moving status from the majority tags attached on the object, so that a portion of reading errors will not affect the detection result. Additionally, based on the redundant tag deployment, it is possible to distinguish the moving objects from the missing objects, and even identify the newly joined tags, which are moved in from outside. 7.2 Phase Variance of Multiple Tags We first study the phase variance of the multiple tags attached on a moving object via a real experiment. Even though these tags may also rotate along with the objects, the moving effect can be usually much larger than the rotation effect, when the tags are deployed vertically in the warehouse [27]. Therefore, we neglect the rotation effect and focus on the moving effect. When an object is moving, all the attached tags are under the same movement with the object, leading to the similar phase variance across these tags. To validate the hypothesis, we conduct an empirical study in the realistic environment by moving a carton box attached with four tags. Particularly, we continuously move the carton box 40cm in front of the antenna, and measure the phase values of these tags simultaneously. Fig. 13(a) presents the phase variances of the four tags during the movement of the box. We find that the measured phase values of the four tags are similar as expected. We call such phase variance the coherent phase variance of the multiple tags on the same object. We further present the correlation matrix among the four phase sequences in Fig. 13(b). We note that all of the correlation values are larger than 99%, which indicates they have the same variance pattern. Therefore, it is reasonable to use the coherent variance pattern to facilitate the detection of moving objects. 7.3 Moving Objects Detection from Unmatched Tags Next we demonstrate how to use the coherent phase variance pattern to determine the moving objects. Consider we have detected the moving tags by matching between the stationary phase distribution P and updated phase distribution P 0 based on the GM method in Section 6. Denote the phase
This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TMC.2019.2907244.IEEE Transactions on Mobile Computing 10 Unmatched Unmatched Unmatched Uamatched taos D taes D tags D' tags of object O 团 Moving tags Moving object O Moving tags in D m1上m3m Ist row Missing tags in D 2,2,2 m3m24 m25 2nd row Moving tags in D' Phase difference Missing m3I m3.2 m3.3 m34 3rd row object O Newly joined tags in D' s Fig.15.Matching moving tags of one object.We compare the phase Fig.14.Results of GM method.We can only detect the moving tags profile of tags attached on one object to match the moving object. from the GM method,but when we attach more tags on one object,it is possible to determine the moving/missing objects from multiple tags. the object.Otherwise,it is only a random phase variance. profiles of unmatched tags in P as set D,which are collected Secondly,we build a graph from all the nodes mi.j and in the tag inventory phase.Meanwhile,we denote the phase connect the similar nodes based on the coherent phase profiles of unmatched tags in P'as another set D',which variance.Specifically,we link nodes mi.j and mi+1.&of two can be either the moving tags unmatched due to the phase adjacent rows,if the phase variances are similar,e.g.,less change or the newly joined tags.Therefore,our mission is than the standard deviation of phase measurements.Note to efficiently find the matching between D to D'based on that there is no link between nodes in the same column, the coherent phase variance,such that the moving tags are i.e.,mi.j and mi+1.j.Since we measure the phase profiles matched together while the missing tags and inserting tags from multiple antennas,it is quite effective to search for are unmatched. the similar nodes.Thirdly,we search for the path from The basic idea is that the multiple tags on the same the graph,that traverses all the w rows as the matching. moving object have the same moving trace,so that the Here,the path means all the nodes in the path have similar phase variance of these tags should also be similar.We phase variances.If multiple paths exist,we just choose exploit Fig.14 as an example to demonstrate the matching the one with minimum phase variance,which means this method.We attach w (w 3)tags on each object for the path is most likely to be the matching result.Then we can detection of moving objects.After the GM method,6 tags determine the matching tags as follows:for node mi.i in the of two objects in P are unmatched,whose phase profiles path,tag t in D'is the matched tag for ti in D after the are D=(n1,...,16).And the unmatched phase profiles of 5 movement.Fourthly,we remove the matched tags in D', tags in p'are denoted as D'=(,.,1).Suppose object since they have been matched,and handle the other objects 01 is moving and the object 02 is missing.Then,only 3 tag one by one.Finally,we could distinguish the moving objects pairs should be matched between D and D'as shown in the from the missing objects and the remained tags of D'are the figure,such that the phase variance of the 3 tag pairs are newly joined tags. similar.If we use a brute force search to find the matching, Fig.15 shows an example of the searching flow.We firstly the possible matchings will increase exponentially along calculate the phase difference nodes mi.j for the object O1, with the scale of D and D'.In this example,even though the i.e.,tag n.t2.3.We use the gray scale to represent the phase size of D and D'are only 6 and 5,respectively,for each tag difference.Secondly,we build the graph by connecting the in D',there are 7 possible matching candidates,i.e.,n to t6 similar phase variance nodes in adjacent rows.Thirdly,we and null.Therefore,there are 57=78,125 possible matching search for the path that traverses all the 3 rows as m1.2- combinations in total. m23-m3.4.Therefore,the matching tags for (n1.12,t3)are To tackle the problem,we propose Coherent Phase Vari- (2.),respectively.Fourthly,we remove (.from ance(CPV)algorithm,a greedy method to search for the D',and finally search for the matching tags for the object matching of the moving tags for each object.Instead of 02.Since we find there is no validate path connecting all the searching for a global matching between D and D',our rows of 02,the object 02 is a missing object.Moreover,we idea is to separate the tags in D into objects,and then can regard tags t and is in D'as the newly joined tags search for the matching phase profiles in D'for each object. 7.4 Combating the Identification Errors Since phase profiles D are achieved from the stationary phase distribution P in the tag inventory phase,we know The above method solves the problem of distinguishing the moving objects in the ideal environment,where every which tags in D belong to one object.Therefore,we know (n1,12,13)are from the same object 01.Hence,we first focus existing tag is successfully identified and the phase profile is correct.However,due to the thermal noise,a moving on searching for the matching tags of object O1 and then handle other objects one by one. tag may be misread in the realistic environments.Since it We propose a five-step method to search for the match- is unlikely all the tags on the same object encounter such ing tags of one object.Firstly,we calculate the phase differ- reading errors at the same time,we could leverage the deployment of multiple tags and use a voting-based method ence node mij between each tag ti of object Og and each tag in D'as: to determine the moving object.In particular,for an object attached with w tags,if more than [w/2]tags occur in the tag m=llt-ill,where t∈Ok,t∈D' (9) set D,this object is regarded as a possible moving/missing If ti and t are the phase profiles of the same tag,then object.Otherwise,the object is determined as static and the mi.j calculates the phase variance due to the movement of corresponding tags are unmatched due to the multi-path 1536-1233(c)2018 IEEE Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1536-1233 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2019.2907244, IEEE Transactions on Mobile Computing 10 t1 t2 t3 t4 t5 t6 t1 ' t2 ' t3 ' t4 ' t5 ' Moving object O1 Missing object O2 } } Unmatched tags D Unmatched tags D' Moving tags in D Missing tags in D Moving tags in D' Newly joined tags in D' Fig. 14. Results of GM method. We can only detect the moving tags from the GM method, but when we attach more tags on one object, it is possible to determine the moving/missing objects from multiple tags. profiles of unmatched tags in P as set D, which are collected in the tag inventory phase. Meanwhile, we denote the phase profiles of unmatched tags in P 0 as another set D 0 , which can be either the moving tags unmatched due to the phase change or the newly joined tags. Therefore, our mission is to efficiently find the matching between D to D 0 based on the coherent phase variance, such that the moving tags are matched together while the missing tags and inserting tags are unmatched. The basic idea is that the multiple tags on the same moving object have the same moving trace, so that the phase variance of these tags should also be similar. We exploit Fig. 14 as an example to demonstrate the matching method. We attach w (w = 3) tags on each object for the detection of moving objects. After the GM method, 6 tags of two objects in P are unmatched, whose phase profiles are D = ht1, · · · , t6i. And the unmatched phase profiles of 5 tags in P 0 are denoted as D 0 = ht 0 1 , · · · , t 0 5 i. Suppose object O1 is moving and the object O2 is missing. Then, only 3 tag pairs should be matched between D and D 0 as shown in the figure, such that the phase variance of the 3 tag pairs are similar. If we use a brute force search to find the matching, the possible matchings will increase exponentially along with the scale of D and D 0 . In this example, even though the size of D and D 0 are only 6 and 5, respectively, for each tag in D 0 , there are 7 possible matching candidates, i.e., t1 to t6 and null. Therefore, there are 57 = 78, 125 possible matching combinations in total. To tackle the problem, we propose Coherent Phase Variance (CPV) algorithm, a greedy method to search for the matching of the moving tags for each object. Instead of searching for a global matching between D and D 0 , our idea is to separate the tags in D into objects, and then search for the matching phase profiles in D 0 for each object. Since phase profiles D are achieved from the stationary phase distribution P in the tag inventory phase, we know which tags in D belong to one object. Therefore, we know ht1, t2, t3i are from the same object O1. Hence, we first focus on searching for the matching tags of object O1 and then handle other objects one by one. We propose a five-step method to search for the matching tags of one object. Firstly, we calculate the phase difference node mi,j between each tag ti of object Ok and each tag t 0 j in D 0 as: mi,j = ||t 0 j − ti ||, where ti ∈ Ok, t 0 j ∈ D 0 . (9) If ti and t 0 j are the phase profiles of the same tag, then mi,j calculates the phase variance due to the movement of m1,1 m1,2 m1,3 m1,4 m1,5 m2,1 m2,2 m2,3 m2,4 m2,5 m3,1 m3,2 m3,3 m3,4 m3,5 Moving tags t1 t2 t3 t1 ' t2 ' t3 ' t4 ' t5 ' Unmatched tags of object O1 Unmatched tags D' Phase difference 1st row 2nd row 3rd row Fig. 15. Matching moving tags of one object. We compare the phase profile of tags attached on one object to match the moving object. the object. Otherwise, it is only a random phase variance. Secondly, we build a graph from all the nodes mi,j and connect the similar nodes based on the coherent phase variance. Specifically, we link nodes mi,j and mi+1,k of two adjacent rows, if the phase variances are similar, e.g., less than the standard deviation of phase measurements. Note that there is no link between nodes in the same column, i.e., mi,j and mi+1,j . Since we measure the phase profiles from multiple antennas, it is quite effective to search for the similar nodes. Thirdly, we search for the path from the graph, that traverses all the w rows as the matching. Here, the path means all the nodes in the path have similar phase variances. If multiple paths exist, we just choose the one with minimum phase variance, which means this path is most likely to be the matching result. Then we can determine the matching tags as follows: for node mi,j in the path, tag t 0 j in D 0 is the matched tag for ti in D after the movement. Fourthly, we remove the matched tags in D 0 , since they have been matched, and handle the other objects one by one. Finally, we could distinguish the moving objects from the missing objects and the remained tags of D 0 are the newly joined tags. Fig. 15 shows an example of the searching flow. We firstly calculate the phase difference nodes mi,j for the object O1, i.e., tag t1, t2, t3. We use the gray scale to represent the phase difference. Secondly, we build the graph by connecting the similar phase variance nodes in adjacent rows. Thirdly, we search for the path that traverses all the 3 rows as m1,2 → m2,3 → m3,4. Therefore, the matching tags for ht1, t2, t3i are ht 0 2 , t 0 3 , t 0 4 i, respectively. Fourthly, we remove ht 0 2 , t 0 3 , t 0 4 i from D 0 , and finally search for the matching tags for the object O2. Since we find there is no validate path connecting all the rows of O2, the object O2 is a missing object. Moreover, we can regard tags t 0 1 and t 0 5 in D 0 as the newly joined tags. 7.4 Combating the Identification Errors The above method solves the problem of distinguishing the moving objects in the ideal environment, where every existing tag is successfully identified and the phase profile is correct. However, due to the thermal noise, a moving tag may be misread in the realistic environments. Since it is unlikely all the tags on the same object encounter such reading errors at the same time, we could leverage the deployment of multiple tags and use a voting-based method to determine the moving object. In particular, for an object attached with w tags, if more than dw/2e tags occur in the tag set D, this object is regarded as a possible moving/missing object. Otherwise, the object is determined as static and the corresponding tags are unmatched due to the multi-path