Reduced order model node location method for multi-hop networks

• US 20070025272A1
• Filed: 07/29/2005
• Published: 02/01/2007
• Est. Priority Date: 07/29/2005
• Status: Abandoned Application

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Shi, Qicai, Kyperountas, Spyros, Niu, Feng
• Application Number:
  US11/194,009
• Publication Number:
  US 20070025272A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method for locating nodes in a multi-hop sensor network forms a rigid body (RB1, RB2, RB3) and, from the nodes, utilizes the rigid body to decide if a node is locatable. The method obtains a reduced order model (ROM) of the network by categorizing all of the nodes by location status, grouping them based upon the categorizations, and defining and identifying a rigid body from a group. To locate the nodes, the nodes are separated from one another into subsets dependent upon characteristics (1100). Then, super groups are formed from one subset (1200) and the sub-groups are formed from each super group (1300). The rigid body core is formed (1400) and the resultant rigid body is determined (1500). The ROM is formed from the rigid body (1600) and a location capability of the rigid body is evaluated based upon the ROM (1700).

Claims

1. A method for locating nodes in a multi-hop sensor network, comprising the steps of:

forming at least one rigid body from the nodes of the network;

utilizing the at least one rigid body to decide if a node is locatable;

categorizing all of the nodes by location status;

grouping the nodes into substantially large groups based upon the location status categorizations;

grouping the substantially large groups into sub-groups; and

forming the at least one rigid body from the sub-group of the grouped nodes if the sub-group has at least two nodes.

2. The method for locating nodes according to claim 1, further comprising the steps of:

defining a space with the network; and

defining the at least one rigid body as a non- deformable structure within the space.

3. The method for locating nodes according to claim 1, further comprising the step of:

locating only nodes within the at least one rigid body.

4. The method for locating nodes according to claim 1, further comprising the step of:

making peer-to-peer ranging information of each node available throughout the network.

5. The method for locating nodes according to claim 1, further comprising the step of:

providing the nodes with blind nodes without knowledge of their own location and reference nodes each having a defined location.

6. The method for locating nodes according to claim 1, further comprising the step of:

expanding the at least one rigid body if it is determined that a node or a rigid body is locatable and the at least one rigid body is a reference frame.

7. A method for locating nodes in a multi-hop sensor network for obtaining a reduced order model of the network comprising the steps of:

categorizing all of the nodes by location status;

grouping the nodes into super groups based upon the location status categorizations;

grouping the nodes in each super group into at least one sub-group; and

defining and identifying at least one rigid body from at least one sub-group of each super group if the sub-group has as at least two nodes.

8. The method for locating nodes according to claim 7, further comprising the step of:

utilizing the at least one rigid body to decide whether a node is locatable.

9. The method for locating nodes according to claim 7, further comprising the step of:

identifying a plurality of rigid bodies from at least one sub-group of the grouped nodes.

10. The method for locating nodes according to claim 7, further comprising the steps of:

defining a space with the network; and

defining the at least one rigid body as a non- deformable structure within the space.

11. The method for locating nodes according to claim 7, which further comprises:

locating only nodes within the at least one rigid body.

12. The method for locating nodes according to claim 7, further comprising the step of:

making available peer-to-peer ranging information of each node throughout the network.

13. The method for locating nodes according to claim 7, further comprising the step of:

providing the nodes with blind nodes and a plurality of reference nodes each having a defined location.

14. The method for locating nodes according to claim 7, further comprising the step of:

expanding the at least one rigid body if it is determined that a node or rigid body is locatable and the at least one rigid body is a reference frame.

15. A method for locating nodes in a multi-hop sensor network, comprising the steps of:

categorizing all of the nodes in the network by location status;

grouping the nodes into super groups based upon the location status categorizations;

grouping the nodes in each super group into at least one sub-group; and

simplifying determinability of node location by forming at least one rigid body from each sub-group based upon the categorized location status if the sub-group has at least two nodes.

16. The method for locating nodes according to claim 15, wherein the step of simplifying further comprises the steps of:

separating the nodes into classes including locatable nodes and non-locatable nodes; and

forming at least one rigid body from the locatable nodes.

17. The method for locating nodes according to claim 15, further comprising the step of:

utilizing the at least one rigid body to determine if a node is locatable.

18. The method for locating nodes according to claim 15, further comprising the step of:

forming at least one rigid body from the node categorizations.

19. The method for locating nodes according to claim 15, further comprising the steps of:

defining a space within the network; and

defining the at least one rigid body as a non-deforming structure within the space.

20. The method for locating nodes according to claim 15, further comprising the steps of:

locating only nodes within the at least one rigid body; and

eliminating from further investigation all nodes outside the at least one rigid body.

21. The method for locating nodes according to claim 15, further comprising the step of:

making available peer-to-peer ranging information of each node throughout the network.

22. The method for locating nodes according to claim 15, further comprising the step of:

providing the nodes with blind nodes and at least one reference node having a defined location.

23. The method for locating nodes according to claim 15, further comprising the step of:

expanding the at least one rigid body if it is determined that a node or a rigid body is locatable and the at least one rigid body is a reference frame.