Geo-locating end-user devices on a communication network

• US 20080010367A1
• Filed: 07/06/2006
• Published: 01/10/2008
• Est. Priority Date: 07/06/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Chen, Liren, Taylor, Kirk S., Steenstra, Jack, Noerenberg, John W.
• Granted Patent: US 8,428,098 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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 distance for a last leg path between the first last hop network device and the user device; 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 1 further comprising:

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

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

4. The method of 1 wherein obtaining the distance of the last leg path includes

determining a transmission medium bandwidth for the last leg path;

determining a last leg round-trip time for the last leg path;

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 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 4 wherein the propagation speed is selected based on the transmission medium of the last leg path.

7. The method of 4 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 7 wherein the high-resolution pings having microsecond resolution are used to obtain the first and second last leg round-trip ping times.

9. The method of 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; 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 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 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 then second last hop network device.

12. An apparatus comprising

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

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 the distance for a last leg path between the last hop network device and the user device; 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 12 wherein the processing circuit is further 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 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 14 wherein the processing circuit is further configured to obtain the last leg round-trip transmission time by

determining 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

determining 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 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 the distance for a last leg path between the last hop network device and the user device; 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 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 last leg distance between the last hop network device and the user device by

obtaining a last leg propagation speed for the transmission medium of the last leg path,

obtaining a last leg propagation time, and

determining the last leg distance between the last hop network device and the user device based on the last leg propagation time and the last

leg propagation speed; and

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

20. The processing device of 19 wherein the circuit is further configured to obtain the last leg distance by

determining a first round-trip time for the last leg path using a first packet size,

determining a second round-trip time for the last leg path using a second packet size,

obtaining a transmission bandwidth for a transmission medium of the last leg path,

obtaining a transmission time for the last leg path based on the transmission bandwidth, and

obtaining the last leg propagation time by subtracting the transmission time from an overall last leg round-trip time.

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

22. The processing device of 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. The processing device of 19 wherein for a given packet size, the circuit is further configured to

obtain a plurality of round-trip times to the last hop network device,

obtain a plurality of round-trip times to the user device, and

ascertain one of either the first or second round-trip times as the smallest difference between one of the plurality of round-trip times to the last hop network device and one of the plurality of round-trip times to the user device.

24. A geo-locating network device comprising:

means for identifying a last hop network device having a known first geographical location in a first network path to a user device;

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

means for determining a geographical location for the user device based on the known first geographical location and the last leg distance.

25. The geo-locating network device of 24 further comprising:

means for obtaining a propagation speed between the user device and the last hop network device, and

means for obtaining a propagation time between the user device and the last hop network device.

26. The geo-locating network device of 24 further comprising:

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

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

means for refining the geographical location of the user device based on the second geographical location and the second last leg distance.

27. A machine-readable medium having one or more instructions for geolocating 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 last leg distance between the last hop network device and the user device; and

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

28. The machine-readable medium of 27 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.

29. The machine-readable medium of 28 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.