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 Vari￾ance (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 match￾ing tags of one object. Firstly, we calculate the phase differ￾ence 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