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