Method and system for determining a location of a plurality of units using sub-divided unit groupings

• US 20050143101A1
• Filed: 12/29/2003
• Published: 06/30/2005
• Est. Priority Date: 12/29/2003
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Huang, Jian, Shi, Qicai, Correal, Neiyer, Kyperountas, Spyros, Andric, Oleg, Niu, Feng
• Granted Patent: US 7,274,940 B2
• Time in Patent Office: Days
• US Class Current: 455/456.600
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks

Abstract

A method and system is provided for determining a location for each of a plurality of units, which are sub-divided into more than one sub-net groupings, that each include two or more units. Within each sub-net grouping, measured range information between units within the sub-nets and one or more reference units is gathered in at least a selected one of the units. The selected one of the units then estimates a location for each of the units, which minimizes any error in the measured ranges between the units in each of the corresponding sub-nets.

Claims

1. A method of determining a location of a plurality of units, each unit being communicatively coupled to at least some of the other plurality of units, wherein at least some of the plurality of units are in communication range with one or more reference units, whose location is at least one of determined and known, said method comprising:

sub-dividing the plurality of units into a plurality of sub-nets, wherein each sub-net includes two or more units;

measuring, in each of the sub-nets, range information between each of the units in the sub-net and the other units in the sub-net, which are in communication range with the unit, and range information between any reference units and at least one of the units in the sub-net within communication range of the corresponding reference unit;

gathering the measured range information in at least a selected one of the units associated with each of the sub-nets;

estimating, in the at least selected one of the units in each of the sub-nets in which the measured range information was gathered, a location for each of the units in each of the sub-nets, which minimizes any error in the measured ranges between the units within communication range in each of the sub-nets and the measured range between any of the reference units and the corresponding units in the sub-net within communication range of at least one of the reference units.

2. A method in accordance with claim 1 wherein sub-dividing the plurality of units into a plurality of sub-nets includes identifying communication pathways between the units having at least one of communication traffic volumes and communication traffic latency, associated with location determination, which exceeds a corresponding predetermined threshold and includes the communication traffic volumes associated with location determination for at least two units;

and defining a sub-net boundary for a new sub-net across the identified communication pathway.

3. A method in accordance with claim 2 wherein defining a sub-net boundary for a new sub-net includes defining a centralized processor as the at least selected one of the units for the new sub-net from among the two or more units in the new sub-net.

4. A method in accordance with claim 1 wherein measuring, in each of the sub-nets, range information includes measuring range information between any nearby nodes from a neighboring sub-net and the units in the sub-net within communication range of the corresponding nearby node from the neighboring sub-net.

5. A method in accordance with claim 1 wherein measuring, in each of the sub-nets, range information includes at least one of measuring received signal strength indicator, angle of arrival, time of arrival, time difference of arrival and phase shifts for signals transmitted by one or more of the units.

6. A method in accordance with claim 1 wherein gathering the measured range information in at least one of the units within each of the subnets includes forwarding the estimates to the at least one of the units in one or more hops via one or more units to the at least selected one of the units.

7. A method in accordance with claim 1 wherein estimating, in the at least selected one of the units in each of the sub-nets, a location for each of the units in each of the sub-nets includes minimizing the error in a set of estimated locations for each of the units and the measured range between the units in each sub-net.

8. A method in accordance with claim 7 wherein minimizing the error includes minimizing the sum of the square of the difference between the range, based upon the estimated location, and the measured range.

9. A method in accordance with claim 1 wherein estimating, in the at least selected one of the units in each of the sub-nets, a location for each of the units in each of the sub-nets includes the selected one of the units in each of the sub-nets, assigning an initial location estimate for each of the units in the corresponding sub-net, and iteratively estimating an updated location for each of the units in the corresponding sub-net.

10. A method in accordance with claim 9 wherein, prior to each iterative estimation, the selected one of the units in each of the sub-nets communicates current estimated location information of units in the corresponding sub-net, used in the location estimation of units in other sub-nets, to the selected ones of the units in the other sub-nets.

11. A method in accordance with claim 1 wherein a reference unit for one sub-net includes a unit, whose location is estimated as part of another sub-net.

12. A system for determining the location of a plurality of units in a multi-hop network, each unit being communicatively coupled to at least some of the other plurality of units, wherein at least some of the plurality of units are in communication range with one or more reference units, whose location is at least one of determined and known, said system comprising:

a plurality of sub-nets, each sub-net including a plurality of units having a transceiver for sharing information including location information with other units, wherein at least one of said units associated with each of said sub-nets includes a centralized processor adapted for receiving range information from each of the units within the corresponding sub-net in one or more hops, and adapted for estimating the location of each of the units in the corresponding sub-net.

13. A system in accordance with claim 12 wherein each unit includes a range measurement module coupled to the transceiver for detecting the range between each of the units within a sub-net and other units in the sub-net, which are in communication range with the unit, and the range between any reference unit within communication range with the unit.

14. A system in accordance with claim 13 wherein the range measurement module includes a timer for determining the at least one of the time of arrival and time difference of arrival of signals transmitted by other units within communication range.

15. A system in accordance with claim 13 wherein the range measurement module is adapted for measuring the phase shift of signals transmitted by other units within communication range.

16. A system in accordance with claim 13 wherein the range measurement module includes a signal strength measurement module for detecting the received signal strength of signals transmitted by other units within communication range.

17. A system in accordance with claim 13 wherein each of said centralized processors includes an error determination module adapted for determining an error based upon the difference between the computed range calculated from the estimated location of the units within the corresponding sub-net and the received location of any reference units, and a corresponding measured range.

18. A system in accordance with claim 12 further comprising a communication monitoring module for identifying the traffic volume of information associated with location information communicated along the pathways between nodes.

19. A system in accordance with claim 12 wherein at least some of the units are mobile communication devices.

20. A system in accordance with claim 19 wherein at least some of the mobile communication devices are cellular radiotelephones.

21. A system in accordance with claim 12 wherein at least some of the units include equipment used by a group of individuals acting in concert.