System and method for performing distributed sequential node localization in active sensor deployment

US 20070150176A1
Filed: 12/23/2005
Published: 06/28/2007
Est. Priority Date: 12/23/2005
Status: Active Grant

First Claim

Patent Images

1. A system for performing distributed sequential node localization in active sensor deployment, comprising:

an equilateral orthogonal reference frame comprising s+1 anchor nodes that is placed in s-dimensional physical space; and

a mobile effector to sequentially place new nodes in a natural sequential ordering within the s-dimensional physical space to form a sequentially well-connected network, for each of the new nodes, comprising;

a telemetry interface to obtain location estimates for the new node from at least s+1 of the anchor nodes previously placed in the s-dimensional physical space; and

a placement evaluator to determine a location for the new node based on the location estimates, wherein the new node is placed in the s-dimensional physical space as a new anchor node proximate to at least one of the s+1 previously-placed anchor nodes upon satisfactory location determination.

View all claims

4 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A system and method for performing distributed sequential node localization in active sensor deployment is presented. An equilateral orthogonal reference frame is defined. The reference frame includes s+1 anchor nodes that is placed in s-dimensional physical space. New nodes are sequentially placed in a natural sequential ordering within the s-dimensional physical space to form a sequentially well-connected network. For each of the new nodes, location estimates are obtained for the new node from at least s+1 of the anchor nodes previously placed in the s-dimensional physical space. A location is determined for the new node based on the location estimates. The new node are placed in the s-dimensional physical space as a new anchor node proximate to at least one of the s+1 previously-placed anchor nodes upon satisfactory location determination.

15 Citations

View as Search Results

26 Claims

1. A system for performing distributed sequential node localization in active sensor deployment, comprising:
- an equilateral orthogonal reference frame comprising s+1 anchor nodes that is placed in s-dimensional physical space; and
  
  a mobile effector to sequentially place new nodes in a natural sequential ordering within the s-dimensional physical space to form a sequentially well-connected network, for each of the new nodes, comprising;
  
  a telemetry interface to obtain location estimates for the new node from at least s+1 of the anchor nodes previously placed in the s-dimensional physical space; and
  
  a placement evaluator to determine a location for the new node based on the location estimates, wherein the new node is placed in the s-dimensional physical space as a new anchor node proximate to at least one of the s+1 previously-placed anchor nodes upon satisfactory location determination.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
- - 2. A system according to claim 1, further comprising:
    - a data screen and filter to evaluate the geometry of the at least one of the s+1 previously-placed anchor nodes, comprising;
      
      a collinear condition screen to check for collinear conditions with respect to the s+1 previously-placed anchor nodes and to remove the collinear conditions prior to placing the new node, where the s-dimensional physical space comprises a two-dimensional physical space; and
      
      a coplanar condition screen to check for coplanar conditions with respect to the s+1 previously-placed anchor nodes and to remove the coplanar conditions prior to placing the new node, where the s-dimensional physical space comprises a three-dimensional physical space.
  - 3. A system according to claim 1, wherein errors in ranging data are minimized, comprising at least one of:
    - a placement limiter to limit the placing of the new node to within a set range of the at least one of the s+1 previously-placed anchor nodes; and
      
      a solution refiner to refine the new node location.
  - 4. A system according to claim 1, wherein the new node location is determined through simple sequential multilateration.
  - 5. A system according to claim 4, wherein the simple sequential multilateration is performed in accordance with the equation:
    - {circumflex over (x)}=(A^TA)^−
      
      1A^Tb where {circumflex over (x)} is an estimate of a location x for the new node, A^TA is an s×
      
      s matrix, A=(a₁,a₂, . . . ,a_m-1)^T, b=(b₁,b₂, . . . b_m-1)^T, a₁is an s×
      
      1 vector for an s-dimensional space, b_iis a single scalar, and m is the set of anchor nodes.
  - 6. A system according to claim 1, further comprising:
    - a preprocessor, comprising at least one of;
      
      a symmetry evaluator to apply symmetric enforcement to the location estimates between the new node and each of the s+1 previously-placed anchor nodes; and
      
      a triangularity evaluator to determine triangular enforcement against each of the s+1 previously-placed anchor nodes.
  - 7. A system according to claim 1, further comprising:
    - a post processor, comprising at least one of;
      
      a least squares evaluator to perform least squares refinement on the determination of the new node location, wherein the placing of the new node is deferred to a different location in the s-dimensional physical space if the determination of the new node location is under-constrained; and
      
      a subgradient evaluator to perform subgradient refinement on the results of the determination of the new node location, wherein the placing of the new node is deferred to a different location in the s-dimensional physical space if the determination of the new node location is exceeds a predefined stress function.
  - 8. A system according to claim 1, further comprising:
    - a data filter to define a boundary condition c(A)<
      
      C , wherein C is selected from the group comprising a constant value, a data noise cutoff level, and an adaptive limit.

9. A method for performing distributed sequential node localization in active sensor deployment, comprising:
- defining an equilateral orthogonal reference frame comprising s+1 anchor nodes that is placed in s-dimensional physical space; and
  
  sequentially placing new nodes in a natural sequential ordering within the s-dimensional physical space to form a sequentially well-connected network, for each of the new nodes, comprising;
  
  obtaining location estimates for the new node from at least s+1 of the anchor nodes previously placed in the s-dimensional physical space and determining a location for the new node based on the location estimates; and
  
  placing the new node in the s-dimensional physical space as a new anchor node- proximate to at least one of the s+1 previously-placed anchor nodes upon satisfactory location determination.
- View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17)
- - 10. A method according to claim 9, further comprising:
    - evaluating the geometry of the at least one of the s+1 previously-placed anchor nodes, comprising;
      
      checking for collinear conditions with respect to the s+1 previously-placed anchor nodes and removing the collinear conditions prior to placing the new node, where the s-dimensional physical space comprises a two-dimensional physical space; and
      
      checking for coplanar conditions with respect to the s+1 previously-placed anchor nodes and removing the coplanar conditions prior to placing the new node, where the s-dimensional physical space comprises a three-dimensional physical space.
  - 11. A method according to claim 9, further comprising:
    - minimizing errors in ranging data, comprising at least one of;
      
      limiting the placing of the new node to within a set range of the at least one of the s+1 previously-placed anchor nodes; and
      
      refining the new node location.
  - 12. A method according to claim 9, wherein the new node location is determined through simple sequential multilateration.
  - 13. A method according to claim 12, further comprising:
    - performing simple sequential multilateration in accordance with the equation;
      
      {circumflex over (x)}=(A^TA)^−
      
      1A^Tb where {circumflex over (x)} is an estimate of a location x for the new node, A^TA is an s×
      
      s matrix, A=(a₁,a₂, . . . ,a_m-1)^T, b=(b₁,b₂, . . . b_m-1)^T, a_iis an s×
      
      1 vector for an s-dimensional space, b_iis a single scalar, and m is the set of anchor nodes.
  - 14. A method according to claim 9, further comprising:
    - preprocessing the location estimates, comprising at least one of;
      
      applying symmetric enforcement to the location estimates between the new node and each of the s+1 previously-placed anchor nodes; and
      
      determining triangular enforcement against each of the s+1 previously-placed anchor nodes.
  - 15. A method according to claim 9, further comprising:
    - post processing the new node location, comprising at least one of;
      
      performing least squares refinement on the determination of the new node location and deferring the placing of the new node to a different location in the s-dimensional physical space if the determination of the new node location is under-constrained; and
      
      performing subgradient refinement on the results of the determination of the new node location and deferring the placing of the new node to a different location in the s-dimensional physical space if the determination of the new node location is exceeds a predefined stress function.
  - 16. A method according to claim 9, further comprising:
    - defining a boundary condition c(A) <
      
      C , wherein C is selected from the group comprising a constant value, a data noise cutoff level, and an adaptive limit.
  - 17. A computer-readable storage medium holding code for performing the method according to claim 9.

18. A system for performing distributed sequential node localization in active sensor deployment using simple sequential multilateration, comprising:
- a reference frame comprising s+1 anchor nodes with s of the anchor nodes orthogonal to and at a known distance from a root anchor node; and
  
  a mobile effector, comprising;
  
  a sequential localizer to sequentially add new nodes in a natural sequential ordering into the s-dimensional physical space to form a sequentially well-connected network, for each of the new nodes, comprising;
  
  a telemetry interface to request location estimates for the new node from the anchor nodes previously placed in the s-dimensional physical space and to obtain the location estimates from at least s+1 of the previously-placed anchor nodes; and
  
  a placement evaluator to determine a location for the new node based on the location estimates by performing simple sequential multilateration; and
  
  a placement tool to place the reference frame in an s-dimensional physical space and to place the new node in the s-dimensional physical space as a new anchor node proximate to at least one of the s+1 previously-placed anchor nodes upon achieving satisfactory results through the simple sequential multilateration.
- View Dependent Claims (19, 20, 21)
- - 19. A system according to claim 18, wherein the simple sequential multilateration is performed in accordance with the equation:
    - {circumflex over (x)}=(A^TA)^−
      
      1A^Tb where {circumflex over (x)} is an estimate of a location x for the new node, A^TA is an s×
      
      s matrix, A=(a₁,a₂, . . . ,a_m-1)^T, b=(b₁,b₂, . . . b_m-1)^T, a_iis an s×
      
      1 vector for an s-dimensional space, b_iis a single scalar, and m is the set of anchor nodes.
  - 20. A system according to claim 18, further comprising:
    - a preprocessor to preprocess the location estimates, comprising at least one of;
      
      a symmetry evaluator to apply symmetric enforcement to the location estimates between the new node and each of the s+1 previously-placed anchor nodes in accordance with the equation;
      
      min(d_ij, d_ji) where d_ijis a distance between nodes i and j and d_jiis a distance between nodes j and i; and
      
      a triangularity evaluator to determine triangular enforcement against each of the s+1 previously-placed anchor nodes in accordance with the equation;
      
      d_ij≦
      
      d_ik+d_kjwhere d_ikis a distance between nodes i and k and d_kjis a distance between nodes k and j, for any k, if both d_ikand d_kjexist.
  - 21. A system according to claim 18, further comprising:
    - a post processor to post process the location, comprising at least one of;
      
      a least squares evaluator to perform least squares refinement on the determination of the new node location in accordance with the equation;
      
      min_x_iΣ
      
      _j(|x_i−
      
      x_j|−
      
      d_ij)²where, for any node i at location x, x_iis minimized and x_jare estimated neighbor locations, wherein the placing of the new node is deferred to a different location in the s-dimensional physical space if the determination of the new node location is under-constrained; and
      
      a subgradient evaluator to perform subgradient refinement on the results of the determination of the new node location in accordance with at least one of the equations;
      
      $\begin{matrix} s (X) = \frac{1}{2} \sum_{j} {(\langle x_{i} - {\hat{x}}_{j} \rangle - d_{i j})}^{2} \\ \frac{\partial s}{\partial x_{i}} = \sum_{j} (\langle x_{i} - x_{j} \rangle - d i j) \frac{(x_{i} - x_{j})}{\langle x_{i} - x_{j} \rangle} and \\ s (X) = \sum_{j} abs (\langle x_{i} - {\hat{x}}_{j} \rangle - d_{i j}) \\ \frac{\partial s}{\partial x_{i}} = \sum_{j} sign (\langle x_{i} - x_{j} \rangle - d i j) \frac{(x_{i} - x_{j})}{\langle x_{i} - x_{j} \rangle} \end{matrix}$ where s is a stress function, wherein the placing of the new node is deferred to a different location in the s-dimensional physical space if the determination of the new node location is exceeds a predefined stress function.

22. A method for performing distributed sequential node localization in active sensor deployment using simple sequential multilateration, comprising:
- defining a reference frame comprising s+1 anchor nodes with s of the anchor nodes orthogonal to and at a known distance from a root anchor node;
  
  placing the reference frame in an s-dimensional physical space; and
  
  sequentially adding new nodes in a natural sequential ordering into the s-dimensional physical space to form a sequentially well-connected network, for each of the new nodes, comprising;
  
  requesting location estimates for the new node from the anchor nodes previously placed in the s-dimensional physical space;
  
  obtaining the location estimates from at least s+1 of the previously-placed anchor nodes;
  
  determining a location for the new node based on the location estimates by performing simple sequential multilateration; and
  
  placing the new node in the s-dimensional physical space as a new anchor node proximate to at least one of the s+1 previously-placed anchor nodes upon achieving satisfactory results through the simple sequential multilateration.
- View Dependent Claims (23, 24, 25, 26)
- - 23. A method according to claim 22, further comprising:
    - performing the simple sequential multilateration in accordance with the equation;
      
      {circumflex over (x)}=(A^TA)^−
      
      1A^Tb where {circumflex over (x)} is an estimate of a location x for the new node, A^TA is an s×
      
      s matrix, A=(a₁,a₂, . . . ,a_m-1)^T, b=(b₁,b₂, . . . b_m-1)^T, a_iis an s×
      
      1 vector for an s-dimensional space, b_iis a single scalar, and m is the set of anchor nodes.
  - 24. A method according to claim 22, further comprising:
    - preprocessing the location estimates, comprising at least one of;
      
      applying symmetric enforcement to the location estimates between the new node and each of the s+1 previously-placed anchor nodes in accordance with the equation;
      
      min(d_ij, d_ji) where d_ijis a distance between nodes i and j and d_jiis a distance between nodes j and i; and
      
      determining triangular enforcement against each of the s+1 previously-placed anchor nodes in accordance with the equation;
      
      d_ij≦
      
      d_ik+d_kjwhere d_ikis a distance between nodes i and k and d_kjis a distance between nodes k and j, for any k, if both d_ikand d_kjexist.
  - 25. A method according to claim 22, further comprising:
    - post processing the location, comprising at least one of;
      
      performing least squares refinement on the determination of the new node location in accordance with the equation;
      
      min_x_iΣ
      
      _j(|x_i−
      
      x_j|−
      
      d_ij)²where, for any node i at location x, x_iis minimized and x_jare estimated neighbor locations, wherein the placing of the new node is deferred to a different location in the s-dimensional physical space if the determination of the new node location is under-constrained; and
      
      performing subgradient refinement on the results of the determination of the new node location in accordance with at least one of the equations;
      
      $\begin{matrix} s (X) = \frac{1}{2} \sum_{j} {(\langle x_{i} - {\hat{x}}_{j} \rangle - d_{i j})}^{2} \\ \frac{\partial s}{\partial x_{i}} = \sum_{j} (\langle x_{i} - x_{j} \rangle - d i j) \frac{(x_{i} - x_{j})}{\langle x_{i} - x_{j} \rangle} and \\ s (X) = \sum_{j} abs (\langle x_{i} - {\hat{x}}_{j} \rangle - d_{i j}) \\ \frac{\partial s}{\partial x_{i}} = \sum_{j} sign (\langle x_{i} - x_{j} \rangle - d i j) \frac{(x_{i} - x_{j})}{\langle x_{i} - x_{j} \rangle} \end{matrix}$ where s is a stress function, wherein the placing of the new node is deferred to a different location in the s-dimensional physical space if the determination of the new node location is exceeds a predefined stress function.
  - 26. A computer-readable storage medium holding code for performing the method according to claim 22.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
Original Assignee
Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
Inventors
Liu, Juan, Zhang, Ying, Huang, Qingfeng

Granted Patent

US 7,684,927 B2
Time in Patent Office

Days
Field of Search
US Class Current

701/201
CPC Class Codes

G01C 15/02   Means for marking measuring...

G01S 5/0289   of multiple transceivers, e...

G01S 5/30   Determining absolute distan...

System and method for performing distributed sequential node localization in active sensor deployment

First Claim

4 Assignments

0 Petitions

Accused Products

Abstract

15 Citations

26 Claims

Specification

Solutions

Use Cases

Quick Links

System and method for performing distributed sequential node localization in active sensor deployment

First Claim

4 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

15 Citations

26 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links