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.2018.2857812.IEEE Transactions on Mobile Computing the tag cannot be effectively activated due to the reduced is free.In each subsequent round,each free object proposes to incident power from the RF-antennas.Besides,the object the most-preferred tag to which it has not yet proposed, occlusion may cause one specific object to be blocked by and each tag replies "maybe"if it is currently free or if another object placed in front of it,such that this object it prefers this object over its current partner object.This cannot be effectively identified from its depth histograms. scheme preserves the right of an already-engaged tag to This leads to the issue of missing tags or objects.Moreover, frade up for better choice.This process is repeated until all in some situations,it is essential to isolate the recognizable objects/tags are engaged or have no candidate partner to object with non-recognizable ones,e.g.,a number of tagged propose to. objects are placed on an untagged table,and the tagged objects are expected to be recognized instead of the table. Algorithm 2 Stable Matching-based Solution However,the table might have effects on the depth-camera 1:Initialize all O:∈O and T,∈T to free reading,but not in RFID-based scanning.This leads to the 2:Set the weight wi.j as the distance between each pair of issue of extra objects.The above two issues further lead to object O:and tag Tj.Compute the ordering of preferences imperfect matching between the objects and tags. for each object/tag according to wi.j.If the weight is greater than a threshold t,remove the corresponding tag/object 5.3.2 Tackle the Outliers in Bipartite Graph Matching from the object/tag's preference list. 3:while 3 free object o which still has a candidate tag t to Since we need to find a matching between the set of tags propose to do and the set of objects according to their estimated positions, 4 t=first tag on o's list to which o has not yet proposed. it is similar to finding a matching in a weighted bipartite 5 if t is free then graph,where the weight refers to the distance between the 6: (o,t)become engaged. tag-object pairs.However,due to the existence of the above 7: else interferences,they actually form the outliers in addition to $ some pair (o',t)already exists 9 if t prefers o to o'then the regular points of the tag set and object set.Specifically, 10: o'becomes free,(o,t)become engaged. these outliers are not essentially far from the regular points 1 else in regard to their relative distance,e.g.,the extra objects 12 (o',t)remain engaged. can be fairly close to the regular tagged objects.Therefore, 13: end if traditional solutions for the weighted bipartite graph matching 14: end if such as the Hungarian algorithm [32]cannot effectively tackle 15:end while the outlier issues in matching,since they seek to find a matching in a weighted bipartite graph which minimizes We further illustrate the above idea with an example, the overall weight (i.e.,the distance between points).They as shown in Fig.9.Fig.9 shows a scenario where 5 tagged aim to pursue the overall benefits of all members while objects are randomly placed in the 2-dimensional space.Due sacrificing the benefits of individuals.In this regard,to avoid to the impact of interferences,there exist some outliers such huge value in the overall weight,some specific regular as the missing tags/objects and extra interference objects points can be mismatched to the outliers for trade off,then In this case,the Hungarian Matching (HM)-based solution a cascade of mismatches between the regular points could can mismatch the tag T2 to the extra objects rather than appear frequently. the object O2,since it considers the overall benefit to make Hence,in order to tackle the outliers,we reduce this the tag T4 to be paired with its only adjacent object O2. problem to the stable marriage problem [33].Specifically,we Nevertheless,our Stable Marriage Matching(SMM)-based aim to find a stable matching between the set of tags and solution is able to effectively tackle the outliers,by giving the set of objects,given an ordering of preferences for priority to matching the tag-object pairs with best preference each element.The ordering of preferences can be computed in distance,e.g.,it matches the tag T2 to the object O2 rather according to the distance between each object-tag pair.We than the extra object,since O2 is in higher order of T2's aim to achieve the stable property for the matching,i.e., preference than the extra object,and T2 is in higher order of there does not exist any match (A,B)by which both A O2's preference than the tag T4. and B would be individually better off than they are with 350 the element to which they are currently matched.The basic -Hungarian Matching (HM) -Stable Marriage Matching (SMM) intuition for using the idea of stable matching is that,for any 300 o Scanned tags tagged object,the distance between the positions of the tag 0×5 o Scanned objects and the object is usually much smaller than the distance 5250 + Missing tags/objects from the outliers.So we can give priority to matching the specific pair of the tag and object according to their best Interference objects preferences in terms of distance.By considering the individ- ual benefits rather than the overall benefits of the object-tag 5 -100 -50 0 50 100 pairs,we can mitigate the impact from the outliers. X(cm) We use the Gale-Shapley algorithm [33]to solve this prob- Fig.9.Tackle the outliers with stable marriage matching lem,as shown in Algorithm 2.It involves a number of We further compare the performance of different so- iterations.Initially all objects and tags are set to free.In lutions under different settings,i.e.,the Greedy Matching the first round,each free object proposes to the tag it prefers in Algorithm 1(GM),the Hungarian Matching(HM),and most,and then each tag replies "maybe"to the object it the Stable Marriage Matching(SMM),as shown in Fig.10. most prefers and gets temporarily engaged to the object if it By default,the average cardinality and spacing of tagged 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.2018.2857812, IEEE Transactions on Mobile Computing 8 the tag cannot be effectively activated due to the reduced incident power from the RF-antennas. Besides, the object occlusion may cause one specific object to be blocked by another object placed in front of it, such that this object cannot be effectively identified from its depth histograms. This leads to the issue of missing tags or objects. Moreover, in some situations, it is essential to isolate the recognizable object with non-recognizable ones, e.g., a number of tagged objects are placed on an untagged table, and the tagged objects are expected to be recognized instead of the table. However, the table might have effects on the depth-camera reading, but not in RFID-based scanning. This leads to the issue of extra objects. The above two issues further lead to imperfect matching between the objects and tags. 5.3.2 Tackle the Outliers in Bipartite Graph Matching Since we need to find a matching between the set of tags and the set of objects according to their estimated positions, it is similar to finding a matching in a weighted bipartite graph, where the weight refers to the distance between the tag-object pairs. However, due to the existence of the above interferences, they actually form the outliers in addition to the regular points of the tag set and object set. Specifically, these outliers are not essentially far from the regular points in regard to their relative distance, e.g., the extra objects can be fairly close to the regular tagged objects. Therefore, traditional solutions for the weighted bipartite graph matching such as the Hungarian algorithm [32] cannot effectively tackle the outlier issues in matching, since they seek to find a matching in a weighted bipartite graph which minimizes the overall weight (i.e., the distance between points). They aim to pursue the overall benefits of all members while sacrificing the benefits of individuals. In this regard, to avoid huge value in the overall weight, some specific regular points can be mismatched to the outliers for trade off, then a cascade of mismatches between the regular points could appear frequently. Hence, in order to tackle the outliers, we reduce this problem to the stable marriage problem [33]. Specifically, we aim to find a stable matching between the set of tags and the set of objects, given an ordering of preferences for each element. The ordering of preferences can be computed according to the distance between each object-tag pair. We aim to achieve the stable property for the matching, i.e., there does not exist any match (A, B) by which both A and B would be individually better off than they are with the element to which they are currently matched. The basic intuition for using the idea of stable matching is that, for any tagged object, the distance between the positions of the tag and the object is usually much smaller than the distance from the outliers. So we can give priority to matching the specific pair of the tag and object according to their best preferences in terms of distance. By considering the individ￾ual benefits rather than the overall benefits of the object-tag pairs, we can mitigate the impact from the outliers. We use the Gale-Shapley algorithm [33] to solve this prob￾lem, as shown in Algorithm 2. It involves a number of iterations. Initially all objects and tags are set to free. In the first round, each free object proposes to the tag it prefers most, and then each tag replies “maybe” to the object it most prefers and gets temporarily engaged to the object if it is free. In each subsequent round, each free object proposes to the most-preferred tag to which it has not yet proposed, and each tag replies “maybe” if it is currently free or if it prefers this object over its current partner object. This scheme preserves the right of an already-engaged tag to trade up for better choice. This process is repeated until all objects/tags are engaged or have no candidate partner to propose to. Algorithm 2 Stable Matching-based Solution 1: Initialize all Oi ∈ O and Tj ∈ T to free. 2: Set the weight wi,j as the distance between each pair of object Oi and tag Tj . Compute the ordering of preferences for each object/tag according to wi,j . If the weight is greater than a threshold t, remove the corresponding tag/object from the object/tag’s preference list. 3: while ∃ free object o which still has a candidate tag t to propose to do 4: t=first tag on o’s list to which o has not yet proposed. 5: if t is free then 6: (o, t) become engaged. 7: else 8: some pair (o 0 , t) already exists. 9: if t prefers o to o 0 then 10: o 0 becomes free, (o, t) become engaged. 11: else 12: (o 0 , t) remain engaged. 13: end if 14: end if 15: end while We further illustrate the above idea with an example, as shown in Fig. 9. Fig. 9 shows a scenario where 5 tagged objects are randomly placed in the 2-dimensional space. Due to the impact of interferences, there exist some outliers such as the missing tags/objects and extra interference objects. In this case, the Hungarian Matching (HM)-based solution can mismatch the tag T2 to the extra objects rather than the object O2, since it considers the overall benefit to make the tag T4 to be paired with its only adjacent object O2. Nevertheless, our Stable Marriage Matching (SMM)-based solution is able to effectively tackle the outliers, by giving priority to matching the tag-object pairs with best preference in distance, e.g., it matches the tag T2 to the object O2 rather than the extra object, since O2 is in higher order of T2’s preference than the extra object, and T2 is in higher order of O2’s preference than the tag T4. Mismatch in HM Scanned tags Scanned objects Missing tags/ objects Interference objects Fig. 9. Tackle the outliers with stable marriage matching We further compare the performance of different so￾lutions under different settings, i.e., the Greedy Matching in Algorithm 1 (GM), the Hungarian Matching (HM), and the Stable Marriage Matching (SMM), as shown in Fig. 10. By default, the average cardinality and spacing of tagged