Abstract:
A method of positioning a RFID tag by using four antennas associated with an algorithm is disclosed. A diagram is depicted, which is about relationships between the RSSI and distance according to environment of the space. Next, four antennas are arranged in the space. Four measured distances analyzed from the RSSI curve are measured. Thereafter, a position of the RFID tag is assumed at the center of space. The position is served as an initial coordinate. Subsequently, the root mean square error (RMSE) is determined. If the RMSE is small than or equal to termination criteria, the coordinate is regarded as the position of the RFID tag, otherwise the initial 3-D coordinate is updated by adding some correcting values at each measuring weight. This process is repeated till the RMSE meets the assigned condition.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention is relates to a RFID tag, particularly, to a positioning method using an algorithm. 
       BACKGROUND OF THE INVENTION 
       [0002]    Nowadays, communication over wireless technique is widely applied on our daily lives. It brings us extreme convenience and usefulness on many aspects. Positioning is an example of applying the wireless technique. The known techniques about positioning include global positioning system (GPS), Cell identification, infrared, IEEE 802.11, supersonic, Ultra-wideband, Zig-bee, radio frequency identification (RFID), etc. GPS provides precisely positioning with low cost, however, it is appropriate for outdoor use only. Cell ID and super-wide band are apt in large district positioning. Infrared position is known for environmental interference-prone and high cost for apparatus installation. The performances of IEEE 802.11 and Zig-Bee techniques in positioning have been found not as good as expectation. Cost for constructing a supersonic positioning system is usually expensive. 
         [0003]    RFID positioning system is an automatic identification system without direct contact. The RFID tag broadcasts radio frequency out so as to transmit identification message. An identification system is composed of RFID tags and readers. Each RFID tag contains a circuit thereon so that a reader can access the information written on the RFID tags in distant using radio frequency. RFID tag essentially is a silicon chip with a simple antenna formed thereon and then capsulated by glass or plastic film. 
         [0004]    A RFID system for indoor positioning was first proposed by HighTower and Borriello in 2001. The research developed a SpotON positioning system to verify the feasibility of using RFID in indoor positioning. In the method of SpotON, unknown positions are not processed by the central control console but are approached by many local detectors. The respond signals, i.e. RSSI (radio signal strength indicator), transmitted from many local detectors distributed in the environment are collected. The RSSI is then analyzed by a positioning algorithm to determine the positions of the article. 
         [0005]    RFID positioning is especially apt to indoor use by taking advantage of low cost for system setup. In 3-D (three dimensional) space, for positioning a target RFID tag, one RFID antenna can constitute a sphere surface only and two RFID antennas can constitute a joint area of two spheres. The third additional antenna can further position the target to two possible answers. To obtain a merely reasonable solution, four antennas are generally demanded. 
         [0006]    Referring to  FIG. 1 , it shows three signal transmitter (or stations) with known positions provided to locate a target tag. Each transmitter transmitting a radio signal outward constitutes a sphere as is shown in figure. The coordinate of the transmitters are respectively, located at (X=0,Y=0), (X=1,Y=0), and (X=3,Y=0). The coverage radiuses of them are r1, r2, and r3, respectively. The unknown position can be determined by the intersection of them. With the same concept, utilizing four transmitters to transmit signals are generally called Multilateration. 
       SUMMARY OF THE INVENTION 
       [0007]    The present invention discloses a method of positioning a RFID tag by using four antennas associated with an algorithm. At first, a diagram is made, which is about the RSSI versus distance according to environment of the space having a target RFID tag to be positioned therein. Next, four antennas are arranged in the positioning space. Utilizing the RSSI curve and four antennas, four measured distances between the RFID tag and the antennas can be obtained. 
         [0008]    Thereafter, a position of the RFID tag is assumed and served as an initial 3-D coordinate for processing iteration. Thus, four distances between the initial 3-D coordinate to the antennas are calculated. Preferably, the initial position is assumed at the center of the space so as to save the iteration time for positioning. 
         [0009]    The errors that are the differences between the measured distances and the calculated distances corresponding for each antenna are calculated. 
         [0010]    Subsequently, the root mean square error (RMSE) is determined. If the RMSE is small than or equal to termination criteria, the initial coordinate is the position of the RFID tag to be determined, otherwise the initial 3-D coordinate is updated by adding some correcting values to each weighting axis. Thereafter, the errors and RMSE are updated according to the newly 3-D coordinate. 
         [0011]    The forgoing iteration processes are repeatedly until the RMSE meets the required condition. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein: 
           [0013]      FIG. 1  shows a schematically diagram for 3-D RFID spatial positioning according to prior art. 
           [0014]      FIG. 2  shows a flow chart in accordance with the algorithm (SPA 1.0) of the present invention. 
           [0015]      FIG. 3  shows curves illustrating the convergent tendency during the iteration processes with an initial position at a corner of the positioning space in accordance with the present invention. 
           [0016]      FIG. 4  shows a curve illustrating the error tendency versus iteration times with an initial position at a corner of the positioning space in accordance with algorithm (SPA 1.0) of the present invention. 
           [0017]      FIG. 5  shows the trace of positioning with an initial position at a corner of the positioning space in accordance with algorithm (SPA 1.0) of the present invention. 
           [0018]      FIG. 6  shows a coordinate tendency versus iteration times with an initial position at a center of the positioning space in accordance with algorithm (SPA 1.0) the present invention. 
           [0019]      FIG. 7  shows a curve illustrating the error tendency versus iteration times with an initial position at a center of the positioning space in accordance with algorithm (SPA 1.0) of the present invention. 
           [0020]      FIG. 8  shows the trace of 3-D positioning with an initial position at a center of the positioning space in accordance with algorithm (SPA 1.0) of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0021]    RFID reader including an antenna can be used to read radio frequency strength indicators (RSSI) emitted from the RFID tags. By means of RSSI, the distance can be determined but the precise position is still unknown. Thus as forgoing description in the background of the invention, at least three antennas are needed (but two positions may still occur). 
         [0022]    The present invention utilizes RSSI of the target tag and reference tag to calculate the distance between the reader and the target tag. 
         [0023]    The present invention provides an algorithm called SPA 1.0 thereby spatially positioning the RFID tag. Please refer to  FIG. 2 . It shows a flow chart according to the algorithm of the present invention. 
         [0024]    The method begins from the step  100 . In step  110 , n reference tags and m antennas are arranged in an indoor space having a RFID target tag to be poisoned. 
         [0025]    In step  115 , let j=0 
         [0026]    In step  120 , assuming the coordinate of the target tag is located at (Xi(j),Yi(j),Zi(j)) after iteration for j times where i represents the reader i. For the purpose of expediting convergence speed for targeting the position (so as to save the run time), the center of the space is assumed. It may be the shortest distance between the correct position of the target tag and the initial coordinate with such assumption. The coordinate can then be written as Xi(j)=x c : Yi(j)=y c ; Zi(j)=z c   
         [0000]    
       
         
           
             
               ( 
               
                 
                   x 
                   c 
                 
                 , 
                 
                   y 
                   c 
                 
                 , 
                 
                   z 
                   c 
                 
               
               ) 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         x 
                         c 
                       
                       = 
                       
                         
                           ( 
                           
                             
                               x 
                               i 
                             
                             - 
                             
                               x 
                               e 
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                 
                 
                   
                     
                       
                         y 
                         c 
                       
                       = 
                       
                         
                           ( 
                           
                             
                               y 
                               i 
                             
                             - 
                             
                               y 
                               e 
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                 
                 
                   
                     
                       
                         z 
                         c 
                       
                       = 
                       
                         
                           ( 
                           
                             
                               z 
                               i 
                             
                             - 
                             
                               x 
                               e 
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                 
               
             
           
         
       
     
         [0027]    Where (x i ,y i ,z i ) is a coordinate of a corner, e.g. an original point of coordinate axes in the positioning space and (x e ,y e ,z e ) is a coordinate of another corner diagonal to the corner, i.e. the end of the coordinate axes in positioning space. 
         [0028]    In step  125 , let k=1. In step  130 , the radio signal strength indication (RSSI) of all of the reference tags are, respectfully, measured by the antenna k. 
         [0029]    In step  135 , the curve for radio signal strength decay versus distance is depicted. Using this diagram, it is easily to calculate distance between target tag and antenna since the positions of all reference tags and the antenna k are known. The diagram is also necessary since the signal of the RFID is prone to be affected or vary by the environment. Every reference tag has its identification; therefore, the antenna k can easily distinguish the RSSI signal emitted from the individual reference tag. In a preferred embodiment, nine reference tags are arranged in the positioning space. 
         [0030]    The RSSI of the target tag is measured by the antenna k, as seen in step  140 . 
         [0031]    Accordingly, the measured distance S ik  between the antenna k and the target tag i can be determined by means of radio signal strength decay and the RSSI of the target tag. Next, the calculated distance  S   ik  between the antenna k and the position at j th  iteration is determined, as seen in step  145 . 
         [0032]    Subsequently, as seen in step  150 , the difference between the S ik  and  S   ik  called error e k  is calculated, as follows: 
         [0000]        e   k =( S   ik   −  S     ik ) 
         [0033]    In step  160 , a judgment of k&gt;4 is made. If it is true, then go to step  170 , otherwise, go to step  165 . 
         [0034]    In step  165 , let k=k+1 then go back to step  135 . 
         [0035]    In step  170 , the root mean square error (RMSE) for all of the antennas and the target tag i is calculated using the equation: 
         [0000]    
       
         
           
             
               ɛ 
               i 
             
             = 
             
               
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                     m 
                   
                    
                   
                     
                       ( 
                       
                         
                           
                             S 
                             ik 
                           
                           - 
                           
                             
                               S 
                               _ 
                             
                             ik 
                           
                         
                         
                           S 
                           ik 
                         
                       
                       ) 
                     
                     2 
                   
                 
                 m 
               
             
           
         
       
     
         [0036]    Where m is a number of RFID antennas in the positioning space. 
         [0037]    In step  180 , a decision step of ε(j)&lt;η is made. The value η is a predetermined value set by the user. It represents the criteria value that user can accepted for the positioning. If it is true, the (X i (j),Y i (j), Z i (j)) is regarded as coordinate of the target. Otherwise, the step goes to step  200  for further correcting the position of the target tag. 
         [0038]    In step  200 , let k=1. 
         [0039]    In step  210 , a correcting quantity (Δx i (j), Δy i (j), Δz i (j)) is added to the coordinate (X i (j), Y i (j),Z i (j)) of j th  iteration. 
         [0040]    The results of equation are as follows: 
         [0000]    
       
         
           
             
               ( 
               
                 
                   
                     x 
                     i 
                   
                    
                   
                     ( 
                     
                       j 
                       + 
                       1 
                     
                     ) 
                   
                 
                 , 
                 
                   
                     y 
                     i 
                   
                    
                   
                     ( 
                     
                       j 
                       + 
                       1 
                     
                     ) 
                   
                 
                 , 
                 
                   
                     z 
                     i 
                   
                    
                   
                     ( 
                     
                       j 
                       + 
                       1 
                     
                     ) 
                   
                 
               
               ) 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           x 
                           i 
                         
                          
                         
                           ( 
                           
                             j 
                             + 
                             1 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           
                             x 
                             i 
                           
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             
                               x 
                               i 
                             
                              
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           y 
                           i 
                         
                          
                         
                           ( 
                           
                             j 
                             + 
                             1 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           
                             y 
                             i 
                           
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             
                               y 
                               i 
                             
                              
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           z 
                           i 
                         
                          
                         
                           ( 
                           
                             j 
                             + 
                             1 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           
                             z 
                             i 
                           
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             
                               z 
                               i 
                             
                              
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0041]    Wherein the correcting quantity (Δx i (j),Δy i (j),Δz i (j)) is assumed to be a product of adjustability (α x ,α y ,α z ), current coordinate (x i (j),y i (j),z i (j)), and local gradient (δ k ). It is thus expressed as: 
         [0000]    
       
         
           
             
               ( 
               
                 
                   Δ 
                    
                   
                       
                   
                    
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       j 
                       ) 
                     
                   
                 
                 , 
                 
                   Δ 
                    
                   
                       
                   
                    
                   
                     
                       y 
                       i 
                     
                      
                     
                       ( 
                       j 
                       ) 
                     
                   
                 
                 , 
                 
                   Δ 
                    
                   
                       
                   
                    
                   
                     
                       z 
                       i 
                     
                      
                     
                       ( 
                       j 
                       ) 
                     
                   
                 
               
               ) 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             x 
                             i 
                           
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                       
                       = 
                       
                         
                           α 
                           x 
                         
                          
                         
                           x 
                           i 
                         
                          
                         
                           δ 
                           k 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             y 
                             i 
                           
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                       
                       = 
                       
                         
                           α 
                           y 
                         
                          
                         
                           y 
                           i 
                         
                          
                         
                           δ 
                           k 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             z 
                             i 
                           
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                       
                       = 
                       
                         
                           α 
                           z 
                         
                          
                         
                           z 
                           i 
                         
                          
                         
                           δ 
                           k 
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0042]    Where α x ,α y ,α z  are respectively, adjustability at X-axis, Y-axis, and Z-axis. Each value is ranging from 0.000001 to 0.1 according to the size of the positioning space. A larger adjustability is preferred initially but a value about one or two order or multitude smaller than the previous adjustability will be selected if the coordinate of the (j+1) th  iteration is out of the positioning space. 
         [0043]    The local gradient (δ k ) of the antenna k can be determined from  S   ik  and e k . The equation is as follows: 
         [0000]      δ k   =  S     ik   ×e   k  
 
         [0044]    In step  220 , the coordinate (x i (j+1), y i (j+1),z i (j+1)) of the (j+1) th  iteration is set as a new initial coordinate. That is: 
         [0000]      ( X   i ( j ),Y i ( j ),Z i ( j ))=( x   i ( j+ 1),y i ( j+ 1),z i ( j+ 1)) 
         [0045]    In step  230 , the error e k =(S ik −  S   ik ) is recalculated, which is the difference between the measuring distance and calculated distance after the j th  iteration. 
         [0046]    In step  240 , a judgment of k&gt;4 is made. If it is true, then go to step  250 , otherwise, go to step  245 . 
         [0047]    In step  245 , let k=k+1 then go back to step  210 . 
         [0048]    In step  250 , a RMSE for m antennas and the target tag i is calculated as above. 
         [0049]    In step  260 , a decision step of ε(j)&lt;η is made. If it is true, the coordinate (X i (j),Y i (j),Z i (j)) is regarded as position of the target, otherwise, go back to step  265 . For an indoor space as concerned, a predetermined value θ ranging from 5 cm to 15 cm is generally acceptable. The smaller the value θ is, the more precision of position can expect. But it costs more iteration times. 
         [0050]    In step  265 , let j=j+1 and then go back to step  200 . 
         [0051]    The step  270  is an ending step. 
         [0052]    To verify the feasibility of the aforementioned algorithm 1.0 (SPA 1.0) for spatially positioning, a simulation flow is run. In the experiment, a space with a size of 926 cm×535 cm×211 cm is assumed and the target tag is placed at the coordinate (694 cm, 400 cm, 75 cm). 
         [0053]    At first, the initially coordinate is set at (1,1,1). The search tendency of the SPA 1.0 algorithm is shown in  FIG. 3 . In  FIG. 3 , the curves of x, y, and z represent the distribution values in each iteration. The parameters of α x ,α y ,α z  are set as α x =α y =α z =5×10 −5 . Viewing from  FIG. 3 , the initial x and y coordinates are far from the x and y coordinates of the target tag so that the convergent processes show them approaching the true x, and y coordinates initially. After the tendency of x and y coordinate approaching stable, the convergence of z coordinate starts. The tendency of the error versus iterations is shown in  FIG. 4 . In  FIG. 4  it shows the method using steepest gradient correction can be successfully used in the spatial positioning. The 3-D variations are shown in  FIG. 5 . In  FIG. 5 , the trace shows that the estimated coordinates are gradually converged to the target position. 
         [0054]    Another initial position is assumed. The starting position is at the center point (463,267.5,105.5) of the positioning space. In case of the starting coordinate at the center of the positioning space, the estimated coordinates for x-axis, y-axis, and z-axis are converged simultaneously and toward the target position. Hence the number of iterations is smaller than the initial position at a corner such as coordinate (1,1,1). Thus it is found that starting position assumed to be at the center point is appreciated. It can save the run time. The tendency of the error versus iterations is shown in  FIG. 7 . Referring to  FIG. 8 , it shows the trace of the convergence. The amplitudes of the oscillation for initial position at a center point is smaller than those of initial position at the point (1,1,1). Thus, it proves the initial poison at the center of the positioning space can meet a better convergent condition. 
         [0055]    As is understood by a person skilled in the art, the foregoing preferred embodiment of the present o invention is an illustration of the present invention rather than limiting thereon. It is intended to cover various modifications and similar arrangements included within the spirit and scope of the appended claims, the scope of which should be accorded the broadest interpretation so as to encompass all such modifications and similar structure.