Geo-locating end-user devices on a communication network

• US 8,428,098 B2
• Filed: 07/06/2006
• Issued: 04/23/2013
• Est. Priority Date: 07/06/2006
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Chen, Liren, Steenstra, Jack, Taylor, Kirk S., Noerenberg, John W. II
• Primary Examiner(s): Washburn, Daniel
• Assistant Examiner(s): HUGHES, EBONI N
• Application Number:
  US11/483,268
• Publication Number:
  US 20080010367A1
• Time in Patent Office: 2,483 Days
• Field of Search: 370/229, 370/230, 370/241, 370/254, 370/351, 702/150, 702/186, 709/223, 709/224, 455/456.1, 375/133
• US Class Current: 375/133
• 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
• CPC Class Codes: H04W 80/04 Network layer protocols, e.g. mobile IP [Internet Protocol]

Abstract

A scheme is provided for determining the geographical location of an active IP device coupled to an IP network. A network path to the user device is obtained to identify a last hop device having a known first geographical location. A last leg distance between the last hop device and the user device is calculated. The last leg bandwidth, propagation time, and propagation speed are also characterized to more accurately determine the last leg distance. By combining the known first geographical location and the distance of the last hop device and user device, a geographical location for the user device is obtained. To improve the accuracy of the geographical location of the user device, multiple last hop devices with known geographical locations are employed to obtain multiple geographical areas for the user device. The intersection or overlap of these geographical areas indicates a refined geographical location of the user device.

Claims

1. A method for determining the geographical location of a user device coupled to a communication network, comprising:

obtaining a network path to the user device;

obtaining a first last hop network device in the network path to the user device;

obtaining a first geographical location of the first last hop network device;

obtaining a plurality of pairs of ping times to the user device and corresponding ping times to the first last hop network device;

obtaining a smallest time difference among the plurality of pairs of ping times to the user device and corresponding ping times to the first last hop network device;

determining a distance for a last leg path between the first last hop network device and the user device using, at least in part, the smallest time difference obtained; and

determining a first user device geographical location for the user device based on the geographical location of the first last hop network device and the last leg path distance.

2. The method of claim 1, further comprising:

executing a route tracing utility to obtain the network path to the user device.

3. The method of claim 1, wherein the first last hop network device is a network device having a known geographical location.

4. The method of claim 1, wherein obtaining the distance of the last leg path further comprises:

determining a transmission medium bandwidth for the last leg path;

determining a last leg round-trip time for the last leg path based at least in part on the difference between the ping times;

calculating a round-trip transmission time of a ping packet over the last leg path based on the transmission bandwidth and a packet size for the ping packet;

determining a round-trip propagation time for the last leg path by subtracting the round-trip transmission time from the last leg round-trip time;

selecting a propagation speed for the transmission medium of the last leg path; and

determining a one-way distance of the last leg path based on the selected propagation speed and the round-trip propagation time.

5. The method of claim 4, wherein the transmission medium bandwidth for the last leg path is obtained by

obtaining a first last leg round-trip ping time for the last leg path using a first packet size;

obtaining a second last leg round-trip ping time for the last leg path using a second packet size;

determining the difference between the first and second packet sizes and dividing by the difference between the first and second last leg round-trip ping times.

6. The method of claim 4, wherein the propagation speed is selected based on the transmission medium of the last leg path.

7. The method of claim 5, wherein the first last leg round-trip ping time is obtained by

determining the time difference between a round-trip ping from a first network station to the first last hop network device and a different round-trip ping from the first network station to the user device, where the pings have a first packet size, and

wherein the second last leg round-trip ping time is obtained by

determining the time difference between a round-trip ping from the first network station to the first last hop network device and a different round-trip ping from the first network station to the user device, where the pings have a second packet size.

8. The method of claim 7, wherein high-resolution pings having microsecond resolution are used to obtain the first and second last leg round-trip ping times.

9. The method of claim 1, further comprising:

obtaining a second network path to the user device;

obtaining a second last hop network device in the second network path to the user device;

obtaining a second geographical location of the second last hop network device;

obtaining a distance for a second last leg path between the second last hop network device and the user device, wherein the distance is obtained in part by ascertaining a difference between a ping time to the user device and a ping time to the second last hop network device, wherein the ping times are high-resolution ping times having microsecond resolution; and

determining a second user device geographical location for the user device based on the second geographical location of the second last hop network device and the second last leg path distance.

10. The method of claim 9, further comprising:

obtaining a refined geographical location for the user device based on the overlap of the first user device geographical location the second user device geographical location.

11. The method of claim 9, Wherein the first network path is different than the second network path and the first last hop network device is a different network device than the second last hop network device.

26. The method of claim 1, wherein the ping times to the user device are obtained based at least in part on pings from an entity to the user device, and wherein the ping times to the first last hop network device are obtained based at least in part on pings from the entity to the first last hop network device.

27. The method of claim 1, wherein the first last hop network device has a known or ascertainable geographical location which is closest to the user device along the network path.

28. The method of claim 1, wherein:

one or more of the ping times to the user device and ping times to the first last hop network device are high-resolution ping times having microsecond resolution.

29. The method of claim 4, wherein the transmission medium bandwidth is determined in accordance with at least one of a residential location, a commercial location, and an age of the last leg path of the communication network, or subsets thereof.

12. An apparatus comprising:

a communication interface to communicatively couple the apparatus to a communication network;

a processing circuit coupled to the communication interface and configured to;

obtain a network path to a user device;

obtain a last hop network device in the network path to the user device;

obtain a first geographical location of the last hop network device;

obtain a plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

obtain a smallest time difference among the plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

determine the distance for a last leg path between the last hop network device and the user device using, at least in part, the smallest time difference; and

determine a first user device geographical location for the user device based on the geographical location of the last hop network device and the distance of the last leg path.

13. The apparatus of claim 12, wherein the processing circuit is configured to:

send a first high-resolution ping having a first packet size to the last hop network device from a first network station to obtain a first round-trip time;

send a second high-resolution ping having the same first packet size to the user device from the first network station to obtain a second round-trip time;

subtract the first round-trip time from the second round-trip time to obtain a first overall last leg round-trip time;

send a third high-resolution ping having a second packet size to the last hop network device from the first network station to obtain a third round-trip time;

send a fourth high-resolution ping having the same second packet size to the user device from the first network station to obtain a fourth round-trip time; and

subtract the third round-trip time from the fourth round-trip time to obtain a second overall last leg round-trip time.

14. The apparatus of claim 13, wherein the processing circuit is further configured to:

obtain a last leg round-trip propagation time by subtracting a last leg round-trip transmission time from a last leg overall round-trip time;

obtain a propagation speed for the last leg path based on the transmission medium of the last leg path; and

obtain the last leg path distance based on the last leg propagation time and the last leg propagation speed.

15. The apparatus of claim 14, wherein the processing circuit, to obtain the last leg round-trip transmission time, is further configured to:

determine a transmission bandwidth for the last leg path based on the first and second packet sizes and the difference between the first and second overall last leg round-trip times; and

determine the last leg round-trip transmission time of a ping packet over the last leg path based on the transmission bandwidth and a packet size for the ping packet.

16. The apparatus of claim 12, wherein the processing circuit is further configured to:

obtain a second network path to the user device;

obtain a second last hop network device in the second network path to the user device;

obtain a second geographical location of the second last hop network device;

obtain the distance between the second last hop network device and the user device;

obtain a second user device geographical location based on the second geographical location of the second last hop network device and the distance between the second last hop network device and the user device; and

obtain a smaller geographical location for the user device based on the overlap of the first user device geographical location the second user device geographical location.

17. A networked apparatus comprising:

means for obtaining a network path to a user device;

means for obtaining a last hop network device in the network path to the user device;

means for obtaining a first geographical location of the last hop network device;

means for obtaining a plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

means for obtaining a smallest time difference among the plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

means for determining the distance for a last leg path between the last hop network device and the user device using, at least in part, the smallest time difference; and

means for determining a first user device geographical location for the user device based on the geographical location of the last hop network device and the distance of the last leg path.

18. The networked apparatus of claim 17, further comprising:

means for obtaining a second network path to the user device;

means for obtaining a second last hop network device in the second network path to the user device;

means for obtaining a second geographical location of the second last hop network device;

means for obtaining the distance between the second last hop network device and the user device;

means for obtaining a second user device geographical location based on the second geographical location of the second last hop network device and the distance between the second last hop network device and the user device; and

means for obtaining a smaller geographical location for the user device based on the overlap of the first user device geographical location the second user device geographical location.

19. A processing device comprising:

a communication interface to communicatively couple the processing device to a communication network;

a circuit coupled to the communication interface and configured to

identify a last hop network device having a known first geographical location in a first network path to a user device;

obtain a plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

obtain a smallest time difference among the plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

determine a last leg distance between the last hop network device and the user device based, at least in part, on the smallest time difference; and

determine a user device geographical location based on the known first geographical location and the last leg distance.

20. The processing device of claim 19, wherein the circuit is further configured to:

determine a first round-trip time for a last leg path using a first packet size;

determine a second round-trip time for the last leg path using a second packet size; and

obtain the transmission bandwidth for the transmission medium of the last leg path based at least in part on the first and second round-trip times.

21. The processing device of claim 20, wherein the first and second round-trip times are obtained using a plurality of high-resolution pings.

22. The processing device of claim 19, wherein the circuit is further configured to:

identify a second last hop network device having a known second geographical location in a second network path to the user device;

obtain a second last leg distance between the user device and the second last hop network device; and

refine the user device geographical location based on the second geographical location and the second last leg distance.

23. A non-transitory machine-readable storage medium having one or more instructions for determining a geographic location of a user device communicatively coupled to a communication network, which when executed by a processor causes the processor to:

identify a last hop network device having a known first geographical location in a first network path to a user device;

obtain a plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

obtain a smallest time difference among the plurality of pairs of ping times to the user device and corresponding ping times to the last hop network device;

determine a last leg distance between the last hop network device and the user device based at least in part on the smallest time difference; and

determine a user device geographical location based on the first geographical location and the last leg distance.

24. The non-transitory machine-readable storage medium of claim 23, having one or more instructions which when executed by a processor causes the processor to further:

obtain a last leg propagation time based on one or more round-trip time measurements between the last hop network device and the user device using a plurality of high-resolution pings; and

refine the last leg distance based upon the last leg propagation time.

25. The non-transitory machine-readable storage medium of claim 24, having one or more instructions which when executed by a processor causes the processor to further:

obtain a last leg propagation speed by characterizing the bandwidth between the last hop network device and the user device based on the one or more round-trip time measurements with different packet sizes; and

refine the last leg distance based upon the last leg propagation speed.