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