METHOD FOR LOCALIZATION OF NODES BY USING PARTIAL ORDER OF THE NODES

• US 20110105161A1
• Filed: 03/27/2009
• Published: 05/05/2011
• Est. Priority Date: 03/27/2008
• Status: Active Grant

• Current Assignee: Locusense AB
• Original Assignee: SICS Swedish Institute of Computer Science AB (Government of Sweden)
• Inventors: Nilsson, Martin
• Granted Patent: US 8,326,329 B2
• Time in Patent Office: Days
• US Class Current: 455/500
• CPC Class Codes: G01S 11/06 using intensity measurements
• CPC Class Codes: G01S 3/46 using antennas spaced apart and measuring phase or time difference between signals therefrom, i.e. path-difference systems
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks

Abstract

The present invention relates to a new method for localization, i.e. finding positions and orientations of nodes communicating in wireless networks. The method is based on using directional information (angle-of-arrival, AOA), and optionally distance information, combined with estimation by recursive filters such as e.g, Kaiman filters, recursive least squares filters, Bayesian filters, or particle filters. The method expresses the localization problem as set of linear equations and ensures stability and convergence by imposing a partial order on the nodes.

Claims

1. A system operable to localize nodes (X, . . . , Y) communicating in a wireless network, wherein each node (X, . . . , Y) comprises a partial ordering means operable to initially classify its node (X, . . . , Y) as an anchor node (A) if a measure of uncertainty of the state estimate, such as a state estimate error covariance norm, is below a first threshold value, or else classify its node (X, . . . , Y) as a non-anchor node, giving rise to a partial order of said nodes (X, . . . , Y), wherein each node (X, . . . , Y) also comprises a control means connected to said partial ordering means, a to said control means connected recursive filter means, wherein every time a node (X) receives a message from another node (Y) said control means is operable to check that said node (Y) precedes said node (X) in said partial order, wherein a node (Y) preceding a node (X) meaning that said node (Y) being located in an ordered sequence comprising both node (X) and node (Y) and being located closer than node (X) to an initial anchor node in said sequence, whereby said recursive filter means is operable to be applied on said current state and measurement, giving an updated state, whereby said partial ordering means, if node (Y) precedes node (X), is operable to update said status of said node (X) in said partial order, wherein each control means is operable to repeat the above, giving the position and orientation of each node (X, . . . , Y), and in that for said system at least one estimation is chosen from the group consisting of the two estimations,

position estimation, where the measurement equation system comprises vectors y and x related as Gy=Gx, where G is a matrix, where y is a vector comprising a position coordinate estimate for a node (Y) received from said node (Y), and where x is a state vector comprising a position coordinate for node (X), and

orientation estimation, where the measurement equation system comprises vectors z and x related as z=Hx, where H is a matrix, where z is a measurement vector comprising an angle of arrival for node (X), and where x is a state vector comprising an orientation coordinate and an angle of arrival for node (X).

2. A system according to claim 1, wherein said control means for each node (X, . . . , Y) is operable to find said position and orientation sequentially.

3. A system according to claim 1, wherein said control means for each node (X, . . . , Y) is operable to find said position and orientation partially or fully in parallel.

4. A system according to claim 1, wherein each recursive filter means is a recursive least square filter or weighted recursive least square filter.

5. A system according to claim 1, wherein each recursive filter means is a Kalman filter.

6. A system according to claim 1, wherein said partial ordering means is operable to assign an initially classified anchor node (A) a minimum fixed rank, wherein rank refers to an entity obeying a total order, wherein an anchor node (A) always precedes a non-anchor node in said partial order.

7. A system according to claim 6, wherein said partial ordering means of a non-anchor node (X) that receives and uses data from a set of nodes assign said non-anchor node (X) a rank which is higher than the highest rank of said set of nodes.

8. A system according to claim 7, wherein said partial ordering means is operable to reclassify a non-anchor node (X) as an anchor node (A) during updating if said measure of uncertainty of the state estimate is below said first threshold value, and its current rank is frozen.

9. A system according to claim 1, wherein each node (X, . . . , Y) also comprises a to said control means connected memory means operable to store estimated angle of arrival (AOA) by a node (X) from every neighbour node, error of AOA estimate, estimated orientation of node (X), error of orientation estimate, and error of position estimate.

10. A method for localization of nodes (X, . . . , Y) communicating in a wireless network, said method comprises the steps:

to initially classify a node (X, . . . , Y) as an anchor node (A) if a measure of uncertainty of the state estimate, such as a state estimate error covariance norm, is below a first threshold value, or else classify its node (X, . . . , Y) as a non-anchor node, giving rise to a partial order of said nodes (X, . . . , Y);

every time a node (X) receives a message from another node (Y), said node (X) performs the following steps;

to check that said node (Y) precedes said node (X) in said partial order, wherein a node (Y) preceding a node (X) meaning that the node (Y) being located in an ordered sequence comprising both node (X) and node (Y) and being located closer than node (X) to an initial anchor node in said sequence;

to apply a recursive filter on the current state and measurement, if node (Y) precedes node (X), giving an updated state; and

to update said status of said node (X) in said partial order; and

said method also comprises the step;

to repeat the above steps, giving the position and orientation of each node (X, . . . , Y); and

in that for said method at least one estimation is chosen from the group consisting of the two estimations,

position estimation, where the measurement equation system comprises vectors y and x related as Gy=Gx, where G is a matrix, where y is a vector comprising a position coordinate estimate for node (Y) received from said node (Y), and where x is a state vector comprising a position coordinate for node (X), and

orientation estimation, where the measurement equation system comprises vectors z and x related as z=Hx, where H is a matrix, where z is a measurement vector comprising an angle of arrival for node (X), and where x is a state vector comprising an orientation coordinate and an angle of arrival for node (X).

11. A method for localization according to claim 10, wherein said method comprises the step:

to find said position and orientation sequentially.

12. A method for localization according to claim 10, wherein said method comprises the step:

to find said position and orientation partially or fully in parallel.

13. A method for localization according to claim 10, wherein said recursive filter is a recursive least square filter or weighted recursive least square filter.

14. A method for localization according to claim 10, wherein said recursive filter is a Kalman filter.

15. A method for localization according to claim 10, wherein said method also comprises the step:

to assign an initially classified anchor node (A) a minimum fixed rank, wherein rank refers to an entity obeying a total order, wherein an anchor node (A) always precedes a non-anchor node in said partial order.

16. A method for localization according to claim 15, wherein said method also comprises the step:

to assign a non-anchor node (X) that receives and uses data from a set of nodes a rank which is higher than the highest rank of said set of nodes.

17. A method for localization according to claim 16, wherein said method also comprises the step:

to reclassify a non-anchor node (X) as an anchor node (A) during updating if said measure of uncertainty of the state estimate is below said first threshold value, and to freeze its current rank.

18. A method for localization according to claim 10, wherein said method also comprises the step:

for each node (X, . . . , Y) to store estimated angle of arrival (AOA) by a node (X) from every neighbour node, error of AOA estimate, estimated orientation of node (X), error of orientation estimate, estimated position, and error of position estimate.

19. At least one computer program product (102₁, . . . , 102_n) directly loadable into the internal memory of at least one digital computer (100₁, . . . , 100_n), comprising software code portions for performing the steps of claim 10 when said at least one product (102₁, . . . , 102_n) is/are run on said at least one computer (100₁, . . . , 100_n.