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

US 7,684,927 B2
Filed: 12/23/2005
Issued: 03/23/2010
Est. Priority Date: 12/23/2005
Status: Expired due to Fees

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 unreferenced s-dimensional physical space, wherein the s+1 anchor nodes comprise s outer anchor nodes situated at fixed distances from a root anchor node located at the vertex of the reference frame; 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, wherein each of the new nodes is connected to at least s+1 of previously placed nodes, comprising;

a mobility unit to move within a predefined distance to the location of one of the previously placed nodes;

a telemetry interface to transmit ultrasonic signals to the previously placed nodes when at the predefined distance and to obtain ultrasonic signal responses comprising location estimates for the new node from 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 receipt of location estimates from at least s+1 anchor nodes and 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.

7 Citations

24 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 unreferenced s-dimensional physical space, wherein the s+1 anchor nodes comprise s outer anchor nodes situated at fixed distances from a root anchor node located at the vertex of the reference frame; 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, wherein each of the new nodes is connected to at least s+1 of previously placed nodes, comprising;
  
  a mobility unit to move within a predefined distance to the location of one of the previously placed nodes;
  
  a telemetry interface to transmit ultrasonic signals to the previously placed nodes when at the predefined distance and to obtain ultrasonic signal responses comprising location estimates for the new node from 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 receipt of location estimates from at least s+1 anchor nodes and 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, and to check for collinear conditions and coplanar conditions with respect to the s+1 previously-placed anchor nodes and to remove the collinear conditions and coplanar conditions prior to placing the new node, where the s-dimensional physical space comprises a two-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_iis 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 to perform 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.
  - 7. A system according to claim 1, further comprising:
    - a post processor to perform at least one of;
      
      performing 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
      
      performing 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 unreferenced s-dimensional physical space, wherein the s+1 anchor nodes comprise s outer anchor nodes situated at fixed distances from a root anchor node located at the vertex of the reference frame; and
  
  sequentially placing new nodes in a natural sequential ordering within the s-dimensional physical space to form a sequentially well-connected network, wherein each of the new nodes is connected to at least s+1 of previously placed nodes, comprising;
  
  moving within a predefined distance to the location of one of the previously placed nodes;
  
  transmitting ultrasonic signals to the previously placed nodes when at the predefined distance;
  
  obtaining ultrasonic signal responses comprising location estimates for the new node from 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 receipt of location estimates from at least s+1 anchor nodes and satisfactory location determination.
- View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
- - 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 ×
      
      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 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 located at the vertex of the reference frame; and
  
  a mobile effector, comprising;
  
  a sequential localizer to sequentially add new nodes in a natural sequential ordering into unreferenced s-dimensional physical space to form a sequentially well-connected network, wherein each of the new nodes is connected to at least s+1 of previously placed nodes, comprising;
  
  a mobility unit to move within a predefined distance to the location of one of the previously placed nodes;
  
  a telemetry interface to request ultrasonic signals comprising location estimates for the new node from at least s+1 of the anchor nodes previously placed in the s-dimensional physical space when at the predefined distance; 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 receipt of the location estimates from the at least s+1 of the previously placed anchor nodes and achieving satisfactory results through the simple sequential multilateration.
- View Dependent Claims (18, 19, 20)
- - 18. A system according to claim 17, 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.
  - 19. A system according to claim 17, further comprising:
    - a preprocessor to preprocess 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.
  - 20. A system according to claim 17, further comprising:
    - a post processor to post process 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, is minimized and x, are 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.

21. 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 located at the vertex of the reference frame;
  
  placing the reference frame in an unreferenced 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;
  
  moving within a predefined distance to the location of one of the previously placed nodes;
  
  requesting ultrasonic signals comprising location estimates for the new node from at least s+1 of the anchor nodes previously placed in the s-dimensional physical space when at the predefined distance;
  
  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 receipt of the location estimates from the at least s+1 of the previously placed anchor nodes and achieving satisfactory results through the simple sequential multilateration.
- View Dependent Claims (22, 23, 24)
- - 22. A method according to claim 21, 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), 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.
  - 23. A method according to claim 21, 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.
  - 24. A method according to claim 21, 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.

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, Julia, Zhang, Ying, Huang, Qingfeng
Primary Examiner(s)
Tran; Khoi
Assistant Examiner(s)
KING, RODNEY P

Application Number

US11/318,184
Publication Number

US 20070150176A1
Time in Patent Office

1,551 Days
Field of Search

701/201
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

7 Citations

24 Claims

Specification

Use Cases

Quick Links

Others

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

7 Citations

24 Claims

Specification

Subscription Required

Use Cases

Quick Links

Others