SIGNAL SPACE BASED NAVIGATION

• US 20160265918A1
• Filed: 10/30/2013
• Published: 09/15/2016
• Est. Priority Date: 10/30/2013
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company), Regents of the University of California (University of California)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: ZHU, Jindan, MOHAPATRA, Prasant, Sen, Souvik, KIM, Kyu Han
• Granted Patent: US 9,733,088 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/0264 at least one of the systems being a non-radio wave positioning system
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

According to an example, a signal space based navigation apparatus may receive traces of wireless signal observations and corresponding pedestrian deadreckoning (PDR) traces between different ones of the wireless signal observations from a plurality of user devices. A plurality of wireless clusters may be generated based on the traces of wireless signal observations. A PDR displacement vector may be generated between two or more of the wireless clusters based on the two or more of the wireless clusters and a subset of the PDR traces corresponding to the two or more of the wireless clusters. A sensing map may be generated based on the plurality of wireless clusters and a plurality of PDR displacement vectors including the PDR displacement vector.

Claims

1. A signal space based navigation apparatus comprising:

a processor; and

a memory storing machine readable instructions that when executed by the processor cause the processor to;

receive traces of wireless signal observations and corresponding pedestrian deadreckoning (PDR) traces between different ones of the wireless signal observations from a plurality of user devices;

generate a plurality of wireless clusters based on the traces of wireless signal observations;

generate a PDR displacement vector between at least two of the wireless clusters based on the at least two of the wireless clusters and a subset of the PDR traces corresponding to the at least two of the wireless clusters; and

generate a sensing map based on the plurality of wireless clusters and a plurality of PDR displacement vectors including the PDR displacement vector.

2. The signal space based navigation apparatus according to claim 1, wherein the plurality of wireless clusters include a plurality of WiFi clusters, further comprising machine readable instructions to cause the processor to:

use the sensing map for route planning to guide a user from a first location represented by one of the plurality of WiFi clusters to a second location represented by another one of the plurality of WiFi clusters, and connected by one of the plurality of PDR displacement vectors.

3. The signal space based navigation apparatus according to claim 2, further comprising machine readable instructions to cause the processor to:

guide the user from the first location to the second location via an intermediate location represented by a further one of the plurality of WiFi clusters.

4. The signal space based navigation apparatus according to claim 1, wherein the traces of wireless signal observations and corresponding PDR traces include turn-aware crowd-sourced data.

5. The signal space based navigation apparatus according to claim 1, wherein to generate a plurality of wireless clusters based on the traces of wireless signal observations, the machine readable instructions are further to cause the processor to:

generate the plurality of wireless clusters based on density-based WiFi observation clustering.

6. The signal space based navigation apparatus according to claim 1, wherein to generate a plurality of wireless clusters based on the traces of wireless signal observations, the machine readable instructions are further to cause the processor to:

group the wireless signal observations based on a predetermined level of signal similarity.

7. The signal space based navigation apparatus according to claim 1, wherein to generate a plurality of wireless clusters based on the traces of wireless signal observations, the machine readable instructions are further to cause the processor to:

control physical coverage of the plurality of wireless clusters by analyzing a wireless cluster centroid offset error and wireless cluster radius error for each of the plurality of wireless clusters.

8. The signal space based navigation apparatus according to claim 1, wherein to generate a PDR displacement vector between at least two of the wireless clusters based on the at least two of the wireless clusters and a subset of the PDR traces corresponding to the at least two of the wireless clusters, the machine readable instructions are further to cause the processor to:

identify and fuse the subset of the PDR traces corresponding to the at least two of the wireless clusters to determine relative positions of the at least two of the wireless clusters.

9. A method for signal space based navigation, the method comprising:

generating turn data based on detection of a change of mobility of a user device at a turn in movement of the user device;

generating direction data based on detection of a direction of the mobility of the user device; and

using, by a processor, a route plan determined from a sensing map that includes wireless clusters and pedestrian deadreckoning (PDR) displacement vectors generated from the turn data and the direction data with a navigation user interface (UI) on the user device to guide a user of the user device from a first location represented by one of the wireless clusters to a second location represented by another one of the wireless clusters, and connected by one of the PDR displacement vectors.

10. The method of claim 9, wherein the user device comprises an accelerometer and wherein generating turn data based on detection of a change of mobility of a user device at a turn in movement of the user device, further comprises:

detecting the change of mobility of the user device at the turn based upon a condition detected by the accelerometer.

11. The method of claim 9, wherein the user device comprises an accelerometer, the method further comprising:

using the accelerometer as a trigger at the turn for performance of wireless signal observations at a higher sampling rate compared to non-turn locations.

12. The method of claim 9, wherein generating turn data based on detection of a change of mobility of a user device at a turn in movement of the user device further comprises:

evaluating an energy spectrum related to up-down movements of the user device relative to a generally horizontal plane; and

identifying a frequency at which a maximum energy is observed as a turn.

13. The method of claim 9, wherein generating turn data based on detection of a change of mobility of a user device at a turn in movement of the user device further comprises:

isolating a sideways PDR trace segment of a predetermined length from PDR traces related to non-sideways movements of the user device; and

using the isolated sideways PDR trace segment to detect a turn.

14. The method of claim 9, wherein the user device comprises a smartphone.

15. A non-transitory computer readable medium having stored thereon machine readable instructions to provide signal space based navigation, the machine readable instructions, when executed, cause a computer system to:

receive crowd-sourced traces of WiFi signal observations and corresponding pedestrian deadreckoning (PDR) traces between different ones of the WiFi signal observations from a plurality of user devices;

generate a plurality of WiFi clusters based on the crowd-sourced traces of WiFi signal observations, wherein a WiFi cluster is confined in an area of a predetermined WiFi signal coverage and predetermined physical coverage;

generate a PDR displacement vector between at least two of the WiFi clusters based on the at least two of the WiFi clusters and a subset of the PDR traces corresponding to the at least two of the WiFi clusters;

generate, by a processor, a sensing map based on the plurality of WiFi clusters and a plurality of PDR displacement vectors including the PDR displacement vector; and

use the sensing map for route planning to guide a user from a first location represented by one of the plurality of WiFi clusters to a second location represented by another one of the plurality of WiFi clusters, and connected by one of the plurality of PDR displacement vectors.