Method and system for determining a location using a plurality of selected initial location estimates

• US 20050143100A1
• 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: Gorday, Paul E., Shi, Qicai, Kyperountas, Spyros, Correal, Neiyer S., Niu, Feng
• Granted Patent: US 7,092,726 B2
• Time in Patent Office: Days
• US Class Current: 455/456.600
• CPC Class Codes: G01S 5/02 using radio waves using satellite radio beacon systems for determining position G01S19/00
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method and system is provided for determining a location for each of a plurality of units, which is selected from one of multiple sets of locations, which are each estimated based upon different initial location estimates. The selected set of locations includes the set which has the minimum error value, where the error value is based on the aggregate of the differences between the range determined from the estimated locations and the measured range. By using different sets of initial location estimates, there is a greater chance that at least one of the sets of initial location estimates will avoid any local minimums and produce a more accurate estimate of unit locations.

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 locations are at least one of determined and known, said method comprising:

measuring range information between each of the units and any reference units within communication range of one another;

establishing a possible location area for each of the units including a plurality of possible initial location estimates;

selecting an initial location estimate for each of the units, whose location is not known, from an area corresponding to the possible location area;

estimating a location for each of the units, which minimizes an error value, based on the difference between the measured range values and a range calculated from the estimated location values;

repeating, at least once, the selection of initial location estimates using a different set of initial location estimates for each of the units from the plurality of possible initial location estimates and the estimation of a location for each of the units, which minimizes an error value; and

selecting the set of location estimates from the repeated estimations having the smallest minimized error value.

2. A method in accordance with claim 1 wherein measuring range information between each of the units and any reference units within communication range of one another includes at least one of measuring received signal strength indicator, angle of arrival, time of arrival, and time difference of arrival for signals transmitted by one or more of the units.

3. A method in accordance with claim 1 wherein establishing a possible location area for each of the units includes determining the overlapping area, based upon the communication range and known or estimated locations of other units communicatively coupled to the unit for which the possible location area is being determined.

4. A method in accordance with claim 1 wherein establishing a possible location area for each of the units includes determining a known previous location, and estimating an amount of possible deviation during an interval of time that has elapsed since the unit was at the previous known location.

5. A method in accordance with claim 4 wherein the possible deviation is based upon an estimated rate of travel and the time interval since the unit was at the previous known location.

6. A method in accordance with claim 4 wherein the possible deviation is based upon an inertial navigation estimation during the time subsequent the previous known location.

7. A method in accordance with claim 1 wherein selecting an initial location estimate for each of the units includes randomly selecting a location from the plurality of possible initial locations from the established possible location area.

8. A method in accordance with claim 1 wherein selecting an initial location estimate for each of the units includes sequentially selecting a location from a sub-set of the plurality of possible initial locations from the established possible location area, which are spaced in a predesignated pattern relative to the possible location area.

9. A method in accordance with claim 8 wherein the predesignated pattern includes locations, which are substantially evenly spaced apart.

10. A method in accordance with claim 9 wherein the distance of the spacing is based upon the size of the possible location area and a predetermined number of the repeated iterations of location estimations.

11. A method in accordance with claim 1 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.

12. A method in accordance with claim 1 wherein estimating a location for each of the units includes after selecting an initial location estimate for each of the units, iteratively estimating an updated location for each of the units at least until the error value is no longer getting smaller.

13. A method in accordance with claim 1 further comprising increasing the communication range of at least some of the plurality of units.

14. A method in accordance with claim 1 further comprising determining the units having links with a sufficient number of reference units to determine a location via triangulation, triangulating the location for each of the identified units, and identifying the triangulated units as reference units during subsequent processing in which the triangulated location remains valid.

15. A method in accordance with claim 14 wherein if any of the units have been newly triangulated and identified as reference units, repeating the attempt to triangulate further units, and subsequently identified as reference units, until no further units can be triangulated.

16. A system for determining the location for each 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 or known, said system comprising:

a transceiver for receiving connectivity and range information for the plurality of units and the reference units in communication range with one another; and

a processor coupled to the transceiver, the processor including

a storage area for maintaining the connectivity, communication range information, and multiple sets of location estimates and corresponding minimized error values,

a calculation module adapted for determining possible location areas for each of the units and estimating a location for each of the units, which minimizes an error value, based upon each set of initial location estimates, and

one or more selection modules for sequentially selecting multiple different sets of initial location estimates corresponding to the possible location areas for each of the units, and selecting the set of estimated locations, which is associated with the smallest minimized error value.

17. A system in accordance with claim 16 wherein at least one of the calculation modules and the one or more selection modules includes one or more sets of pre-stored instructions.

18. A system in accordance with claim 17 wherein the one or more sets of pre-stored instructions are stored in the storage area.

19. A system in accordance with claim 16 wherein the one or more selection modules is adapted for randomly selecting an initial location estimate from the corresponding possible location area for each of the units.

20. A system in accordance with claim 16 wherein the one or more selection modules is adapted for sequentially selecting an initial location estimate from the corresponding possible location area for each of the units, which are spaced apart in a predesignated pattern.

21. A system in accordance with claim 16 wherein the system for determining the location is incorporated as part of one of the units to be located.

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

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

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