Location data diffusion and location discovery

• US 7,026,983 B2
• Filed: 07/13/2001
• Issued: 04/11/2006
• Est. Priority Date: 07/18/2000
• Status: Expired due to Term

• Current Assignee: Didi (HK) Science and Technology Ltd.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Spratt, Michael P.
• Primary Examiner(s): Maung, Nay
• Assistant Examiner(s): DEAN, RAYMOND S
• Application Number:
  US09/905,774
• Publication Number:
  US 20020045455A1
• Time in Patent Office: 1,733 Days
• Field of Search: 455/41.2, 455/11.1, 455/7, 455/456.1, 455/404.2, 455/518, 455/519, 455/41.3, 342/357.08, 342/357.09, 342/357.1, 342/457, 342/458, 342/463, 342/464
• US Class Current: 342/458
• CPC Class Codes: G01S 1/045 Receivers
• CPC Class Codes: G01S 5/0009 Transmission of position information to remote stations involving assistance data G01S5/0236
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04L 12/12 Arrangements for remote connection or disconnection of substations or of equipment thereof
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• 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 64/006 with additional information processing, e.g. for direction or speed determination
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A location discovery method using location data items that originate at known locations (X,Y) and are passed to, and diffused between, entities (A,B) by short-range communication. Each location data item received by an entity (A,B) indicates a maximum distance of the entity from one of the known locations (X,Y). Each entity (A,B) prior to using a location data item for location determination or transferring it to another entity, is operative to increase the maximum distance indicated by the location data item to take account of movement of the mobile entity since receiving that item. A mobile entity (A) effects location determination by finding locations (40) simultaneously consistent with the maximum distances (31,36) it knows of and any applicable route constraints for how the location data items passed to the mobile entity.

Claims

1. A method of disseminating location information wherein location data items originating at known locations are passed to, and diffused between, entities by short-range communication, each location data item specifying the said known location at which it originated and including a distance quantity indicative of an upper bound value for the distance to the specified known location, each entity increasing the distance quantity of each location data item it handles to take account of additional travel of the location data item as perceived by the entity.

2. A method according to claim 1, wherein a said entity, which is a mobile entity, increases the distance quantity of the or each location data item it handles by an amount corresponding to the distance moved by the entity whilst holding the location data item.

3. A method according to claim 2, wherein the mobile entity is a vehicle equipped with a short-range transceiver and an odometer, the vehicle increasing the distance quantity of its location data items by the distance travelled by the vehicle as indicated by said odometer.

4. A method according to claim 2, wherein the mobile entity is a pedestrian carrying a mobile device with a short-range transceiver, the device effecting an estimate of the maximum distance likely to have been travelled by the pedestrian based on a speed value and elapsed time, and the device increasing the distance quantity of its location data items by said estimate of the maximum distance likely to have been travelled by the pedestrian.

5. A method according to claim 4, wherein said speed is the maximum speed of the pedestrian as judged over time by the device based on the time taken for the pedestrian to move between locations as determined by the location determination operation.

6. A method according to claim 4, wherein said speed is a standard maximum speed for walking pedestrians, the device:

monitoring the current speed of the pedestrian based on the time taken for the pedestrian to move between locations of known position, and

in the event of the current speed of the pedestrian exceeding said standard maximum speed, preventing the passing on of location data items from the mobile entity to other said entities.

7. A method according to claim 1, wherein the distance quantity of a said location data item is increased, for each transmission hop between two entities, by an amount related to the transmission range of the transmitting entity.

8. A method according to claim 7, wherein the increase of said distance quantity is a fixed range value for the transmitting entity, this range value being added by the transmitting entity to said distance quantity.

9. A method according to claim 7, wherein the said distance quantity incorporates a hop count for providing a measure of the distance travelled by the location data item concerned as a result of transmission hops.

10. A method according to claim 7, wherein the increase of said distance quantity is a fraction of a range value for the transmitting entity, this fraction being determined by the receiving entity in dependence on the received signal strength, the receiving entity adjusting said distance quantity accordingly.

11. A method according to claim 1, wherein a said entity, which is a mobile entity, increases the distance quantity of the or each location data item it handles both by an amount corresponding to the distance moved by the entity whilst holding the location data item and by an amount related to the transmission range of the transmitting entity in respect of one of receipt and transmission of the location data item by mobile entity.

12. A method according to claim 1, wherein a said entity determines its location by determining a location simultaneously consistent, or most nearly consistent, with the upper bound values it knows of as a result of location data items it has received.

13. A method according to claim 12, wherein said entity in determining its location, applies one or more route constraints for how the location data items passed to the mobile entity.

14. A method according to claim 13, wherein said entity in determining its location, applies a constraint that the said upper bound values are distances along predetermined routes from the known locations concerned.

15. A method according to claim 14, wherein said predetermined routes are routes on a map represented by map data known to the entity.

16. A method according to claim 13, wherein said entity in determining its location applies a constraint that the said upper bound values are distances along indeterminate routes that avoid particular zones.

17. A method according to claim 13, wherein a received location data item includes an indication of a constraint type to be applied over at least a certain length of the associated upper bound distance value.

18. A method according to claim 12, wherein upon said entity receiving a location data item indicating an upper bound distance value to a known location for which a location data item has been previously received, one of the location data items is discarded, the discarded item being the one indicating the larger upper bound distance value to the known location taking account of any increases due to movement of the entity after item receipt.

19. A method according to claim 12, wherein upon location determination by said entity initially indicating multiple location zones where the entity could be located, the entity seeks to determine which location zone is the most probable on the basis of one or more of the following probability indicators:

the size of the location zones as compared with an expected degree of location uncertainty;

the natures of the routes followed in order to arrive at the location zones from the known locations involved;

a previous history of locations visited or passed through by the entity;

the correspondence of sensed travel events, such as turning, with opportunities for such events along routes to the location zones.

20. A method according to claim 12, wherein the location of said entity is determined on two separate occasions with the later determination using location data received after the first determination whereby to enable an indication of the average direction of travel to be derived.

21. A method according to claim 12, wherein a best estimate of location is derived within an area of possible locations based on an averaging relative to vertices of that area.

22. A method according to claim 21, wherein said estimate is carried out by averaging of coordinate values of said vertices.

23. A method according to claim 21, wherein said estimate is carried out by finding the center of gravity of a polygon delimited by said vertices.

24. A method according to claim 2, wherein a said entity determines its location by determining a location simultaneously consistent, or most nearly consistent, with the upper bound values it knows of as a result of location data items it has received.

25. A method according to claim 24, wherein said entity in determining its location, applies one or more route constraints for how the location data items passed to the mobile entity.

26. A method according to claim 25, wherein said entity in determining its location, applies a constraint that the said upper bound values are distances along predetermined routes from the known locations concerned.

27. A method according to claim 26, wherein said predetermined routes are routes on a map represented by map data known to the entity.

28. A method according to claim 25, wherein said entity in determining its location applies a constraint that the said upper bound values are distances along indeterminate routes that avoid particular zones.

29. A method according to claim 25, wherein a received location data item includes an indication of a constraint type to be applied over at least a certain length of the associated upper bound distance value.

30. A method according to claim 24, wherein upon said entity receiving a location data item indicating an upper bound distance value to a known location for which a location data item has been previously received, one of the location data items is discarded, the discarded item being the one indicating the larger upper bound distance value to the known location taking account of any increases due to movement of the entity after item receipt.

31. A method according to claim 24, wherein upon location determination by said entity initially indicating multiple location zones where the entity could be located, the entity seeks to determine which location zone is the most probable on the basis of one or more of the following probability indicators:

the size of the location zones as compared with an expected degree of location uncertainty;

the natures of the routes followed in order to arrive at the location zones from the known locations involved;

a previous history of locations visited or passed through by the entity;

the correspondence of sensed travel events, such as turning, with opportunities for such events along routes to the location zones.

32. A method according to claim 24, wherein the location of said entity is determined on two separate occasions with the later determination using location data received after the first determination whereby to enable an indication of the average direction of travel to be derived.

33. A method according to claim 24, wherein a best estimate of location is derived within an area of possible locations based on an averaging relative to vertices of that area.

34. A method according to claim 33, wherein said estimate is carried out by averaging of coordinate values of said vertices.

35. A method according to claim 33, wherein said estimate is carried out by finding the center of gravity of a polygon delimited by said vertices.

36. A method according to claim 7, wherein a said entity determines its location by determining a location simultaneously consistent, or most nearly consistent, with the upper bound values it knows of as a result of location data items it has received.

37. A method according to claim 36, wherein said entity in determining its location, applies one or more route constraints for how the location data items passed to the mobile entity.

38. A method according to claim 37, wherein said entity in determining its location, applies a constraint that the said upper bound values are distances along predetermined routes from the known locations concerned.

39. A method according to claim 38, wherein said predetermined routes are routes on a map represented by map data known to the entity.

40. A method according to claim 37, wherein said entity in determining its location applies a constraint that the said upper bound values are distances along indeterminate routes that avoid particular zones.

41. A method according to claim 37, wherein a received location data item includes an indication of a constraint type to be applied over at least a certain length of the associated upper bound distance value.

42. A method according to claim 36, wherein upon said entity receiving a location data item indicating an upper bound distance value to a known location for which a location data item has been previously received, one of the location data items is discarded, the discarded item being the one indicating the larger upper bound distance value to the known location taking account of any increases due to movement of the entity after item receipt.

43. A method according to claim 36, wherein upon location determination by said entity initially indicating multiple location zones where the entity could be located, the entity seeks to determine which location zone is the most probable on the basis of one or more of the following probability indicators:

the size of the location zones as compared with an expected degree of location uncertainty;

the natures of the routes followed in order to arrive at the location zones from the known locations involved;

a previous history of locations visited or passed through by the entity;

the correspondence of sensed travel events, such as turning, with opportunities for such events along routes to the location zones.

44. A method according to claim 36, wherein the location of said entity is determined on two separate occasions with the later determination using location data received after the first determination whereby to enable an indication of the average direction of travel to be derived.

45. A method according to claim 36, wherein a best estimate of location is derived within an area of possible locations based on an averaging relative to vertices of that area.

46. A method according to claim 45, wherein said estimate is carried out by averaging of coordinate values of said vertices.

47. A method according to claim 45, wherein said estimate is carried out by finding the center of gravity of a polygon delimited by said vertices.

76. A method according to claim 1, wherein said distance quantity is indicative of an upper bound value for the distance travelled by the location data item from the specified known location, independently of the specified known location.

48. An entity comprising:

a short-range transceiver for exchanging, with currently-nearby entities, location data items that each specifies its originating location and includes a distance quantity indicative of an upper bound distance to its originating location;

a memory for storing received location data items;

an update arrangement for maintaining the received location data items by increasing the distance quantity of each location data item to take account of additional travel of the location data item as perceived by the entity; and

a control arrangement for causing the short-range transceiver to pass on to a newly encountered entity, previously-received location data items the distance quantities of which have been updated by the update arrangement.

49. An entity according to claim 48, wherein said entity is a mobile entity and the update arrangement is arranged to maintain the received location data items by increasing the distance quantity of the or each location data item by an amount corresponding to the distance moved by the entity whilst holding the location data item.

50. An entity according to claim 49, wherein the mobile entity is a vehicle equipped with a short-range transceiver and an odometer, the update arrangement being arranged to increase the distance quantity of the received location data items by the distance travelled by the vehicle as indicated by said odometer.

51. An entity according to claim 49, wherein the mobile entity is a mobile device intended to be carried by a pedestrian, the update arrangement being arranged to effect an estimate of the maximum distance likely to have been travelled by the pedestrian based on a speed value and elapsed time, and to increase the distance quantity of the received location data items by said estimate of the maximum distance likely to have been travelled by the pedestrian.

52. An entity according to claim 51, further comprising a location determining arrangement for effecting location determination by determining what locations are simultaneously consistent, or most nearly consistent, with the said upper bound distances known to the entity;

the location determining arrangement being arranged to determine a maximum speed of the pedestrian based on the time taken for the pedestrian to move between locations determined by the location determination arrangement;

the update arrangement being arranged to use this maximum speed as said speed value for estimating the maximum distance likely to have been travelled by the pedestrian.

53. An entity according to claim 51, further comprising a location determining arrangement for effecting location determination by determining what locations are simultaneously consistent, or most nearly consistent, with the said upper bound distances known to the entity;

the update arrangement being arranged to use as said speed value a standard maximum speed for walking pedestrians; and

the control arrangement being arranged to;

monitor the current speed of the pedestrian based on the time taken for the pedestrian to move between locations of known position as determined by the location determining arrangement, and

in the event of the current speed of the pedestrian exceeds said standard maximum speed, prevent the passing on of location data items from the mobile entity to other said entities by the short-range transceiver.

54. An entity according to claim 48, wherein the update arrangement is arranged to maintain the received location data items by increasing the distance quantity of a said location data item by an amount related to the transmission range of the transmitting entity in respect of one of receipt and transmission of the location data item by the subject entity.

55. An entity according to claim 54, wherein the update arrangement is arranged to increase the distance quantity of a location data item immediately prior to the entity transmitting that item to another entity, this increase being by a fixed transmission range value.

56. An entity according to claim 54, wherein the update arrangement is arranged to increase the distance quantity of a location data item received from another entity by a fraction of a range value for the transmitting entity, the update arrangement being arranged to determine this fraction in dependence on the received signal strength as measured by the short-range transceiver.

57. An entity according to claim 48, further comprising a location determining arrangement for effecting location determination by determining what locations are simultaneously consistent, or most nearly consistent, with the said upper bound distances known to the entity.

58. An entity according to claim 57, wherein the location determining arrangement is arranged, in determining the location of the entity, to apply one or more route constraints for how the location data items passed to the entity.

59. An entity according to claim 58, wherein the location determining arrangement is arranged, in determining the location of the entity, to apply a constraint that the said upper bound distances are distances along predetermined routes from the known locations concerned.

60. An entity according to claim 58, wherein the location determining arrangement is arranged, in determining the location of the entity, to apply a constraint that the said upper bound distances are distances along indeterminate routes that avoid particular zones.

61. An entity according to claim 57, wherein the location determining arrangement is arranged to derive a best estimate of location within an area of possible locations based on an averaging relative to vertices of that area.

77. An entity according to claim 48, wherein the distance quantity included in each location data item and indicative of an upper bound distance to the originating location specified in the data item, is independent of the specified originating location.

62. A mobile entity provided with a location discovery system comprising:

a short-range receiver for receiving location data items from currently nearby transmitting entities, each location data item specifying a known location and including a distance quantity indicative of an upper bound distance to that location;

a memory for storing the received data items;

a distance sub-system for measuring or estimating the distance travelled by the mobile entity;

an update unit for updating the received data items by increasing the distance quantity of each data item by the distance measured or estimated by the distance sub-system since the item concerned was received or last updated; and

a location determination unit operative to determine what locations are simultaneously consistent, or most nearly consistent, with the said upper bound distances known to the mobile entity.

78. An entity according to claim 62, wherein the distance quantity included in each location data item and indicative of an upper bound distance to the known location specified in the data item, is independent of the specified known location.

63. An entity provided with a location discovery system comprising:

a short-range receiver for receiving location data items from currently nearby transmitting entities, each location data item specifying a known location and including a distance quantity indicative of an upper bound distance to that location;

a memory for storing the received data items;

an update unit for updating the received data items by increasing the distance quantity of each data item by an amount related to the transmission range of the transmitting entity in respect of one of receipt and transmission of the location data item by the entity; and

a location determination unit operative to determine what locations are simultaneously consistent, or most nearly consistent, with said upper bound distances known to the mobile entity.

79. An entity according to claim 63, wherein the distance quantity included in each location data item and indicative of an upper bound distance to the known location specified in the data item, is independent of the specified known location.

64. A location discovery method wherein location data items originating at known locations are passed to, and diffused between, mobile entities by short-range communication, each location data item received by a mobile entity specifying a location and including a distance quantity indicative of a maximum distance of the entity from the specified location, and each mobile entity prior to using a location data item for location determination or transferring it to another mobile entity, increasing the maximum distance indicated by the distance quantity of the location data item to take account of movement of the mobile entity since receiving that item, the mobile entity effecting location determination by finding locations simultaneously consistent with the said maximum distances it knows of and any applicable route constraints for how the location data items passed to the mobile entity.

80. A method according to claim 64, wherein the distance quantity included in each location data item and indicative of a maximum distance from the location specified in the data item, is independent of the specified location.

65. A location discovery method in which a mobile entity:

receives location data items from currently-nearby transmitting entities, each location data item specifying a location and including a distance quantity indicative of a maximum distance to that location;

maintains the received data items by increasing the distance quantity of each data item by the actual or estimated movement of the mobile entity; and

effects location determination by determining what locations are simultaneously within all the said maximum distances known to the mobile entity and satisfy any other constraints applied by the mobile entity.

66. A method according to claim 65, wherein the mobile entity, on encountering another mobile entity, passes on its previously-received location data items to the other mobile entity, the distance quantities associated with these items having been increased to take account of the actual or estimated movement of the mobile entity passing them on.

67. A method according to claim 65, wherein the mobile entity is a vehicle equipped with a short-range transceiver and an odometer, the vehicle increasing the distance quantities of its location data items by the distance travelled by the vehicle as indicated by said odometer.

68. A method according to claim 66, wherein the mobile entity is a vehicle equipped with a short-range transceiver and an odometer, the vehicle increasing the distance quantities of its location data items by the distance travelled by the vehicle as indicated by said odometer.

69. A method according to claim 65, wherein the mobile entity is a pedestrian carrying a mobile device with a short-range transceiver, the device effecting an estimate of the maximum distance likely to have been travelled by the pedestrian based on a speed value and elapsed time, and the device increasing the distance quantities of its location data items by said estimate of the maximum distance likely to have been travelled by the pedestrian.

70. A method according to claim 66, wherein the mobile entity is a pedestrian carrying a mobile device with a short-range transceiver, the device effecting an estimate of the maximum distance likely to have been travelled by the pedestrian based on a speed value and elapsed time, and the device increasing the distance quantities of its location data items by said estimate of the maximum distance likely to have been travelled by the pedestrian.

71. A method according to claim 65, wherein the location determination operation applies a constraint that the said maximum distances are distances along predetermined routes from the specified locations concerned.

72. A method according to claim 65, wherein the location determination operation applies a constraint that the said maximum distances are distances along indeterminate routes that avoid particular zones.

81. A method according to claim 65, wherein the distance quantity included in each location data item and indicative of a maximum distance to the location specified in the data item, is independent of the specified location.

73. A mobile entity provided with a location discovery system comprising:

a short-range receiver for receiving location data items from currently nearby transmitting entities, each location data item specifying a location and including a distance quantity indicative of a maximum distance to that location;

a memory for storing the received data items;

a distance sub-system for measuring or estimating the distance travelled by the mobile entity;

an update unit for updating the received data items by increasing the distance quantity associated with each data item by the distance measured or estimated by the distance sub-system since the item concerned was received or last updated; and

a location determination unit operative to determine what locations are simultaneously within all the said maximum distances known to the mobile entity and satisfy and any other constraints applied by the mobile entity.

82. An entity according to claim 73, wherein the distance quantity included in each location data item and indicative of a maximum distance to the location specified in the data item, is independent of the specified location.

74. A method of disseminating location information, wherein location data, including a first component specifying a location and a second component indicative of the distance from the location specified by the first component, is passed between devices by short-range transceivers, said second component of the location data being increased, for each transmission hop between two devices, by an amount related to the transmission range of the transmitting device.

83. A method according to claim 74, wherein the second component is indicative of the distance from the location specified by the first component, independently from the first component.

75. A method of disseminating location information wherein location data items originating at known locations are passed to, and diffused between, entities by short-range communication, each location data item specifying the said known location at which it originated and including a distance quantity indicative, without computational combination with the specified known location, of an upper bound value for the distance travelled by the location data item from the specified known location, said entities increasing the distance quantity of each location data item it handles to take account of additional travel of the location data item as perceived by the entity.