Patent Description:
International Application Publication No. <CIT> discloses determining "source information" and "predetermined destination information. " This application discloses generating a predetermined path (i.e. a route) for the user to follow between the source (current location) and the predetermined destination. This application discloses first determining a recommended path to travel (i.e., directions) based on the current location of "a first terminal" to the predetermined destination. The current location may be updated when a GPS device (a second terminal) eventually determines a more accurate location of the user.

United States Patent Application Publication No. <CIT> discloses receiving radio signals along a path and comparing (or "matching‴) the characteristics of the received radio signals to a library of previously recorded radio signals that were previously received along various paths. These previously recorded radio signals are stored in "measurement packages.

A first method is described and claimed. The first method includes receiving signals, in a receiver from a transmitter, along a traveled path and recording, in a memory, signal power levels of the received signals. The traveled path is a path actually traveled by the receiver. The first method includes inputting a first estimated track. The first estimated track includes an estimate of the traveled path of the receiver. The first method includes identifying, by a processor, extracted features of the recorded signal power levels. In this first method, identifying the extracted features includes identifying a first observed change of the recorded signal power levels corresponding to a first point on the first estimated track, and identifying a second observed change of the recorded signal power levels corresponding to a second point on the first estimated track. Each of the first observed change and the second observed change is caused by a propagation path between the transmitter and the receiver transitioning between an unobstructed and an obstructed propagation path as the receiver moves along the traveled path. This first method includes determining, by the processor, expected features of expected signal power levels. In this first method, determining expected features includes generating expected signal power levels at points along the first estimated track by modeling signal propagation, identifying a first expected change of the expected signal power levels corresponding to a third point on the first estimated track, and identifying a second expected change of the expected signal power levels corresponding to a fourth point on the first estimated track. Each of the first expected change and the second expected change is caused by a modeled propagation path transitioning between an obstructed propagation path and an unobstructed propagation path. This first method includes determining a track bias based on the first point associated with the first observed change, the second point associated with second observed change, the third point associated with first expected change, and the fourth point associated with the second expected change. This first method includes generating a corrected track based on the first estimated track and the track bias.

A second method described and claimed includes the first method. In the second method, receiving the signals along the traveled path includes receiving the signals over a period of time. In this second method, recording signal power levels of the received signals includes recording the signal power levels of the received signals over the period of time. In this second method, the first observed change is caused by the signals having traveled different propagation paths to two different points on the traveled path at two different times.

A third method described or claimed includes the second or the first method. In the third method, determining the track bias includes determining the track bias based on a relative position between the first point and the second point on the first estimated track. Alternatively, in the third method, determining the track bias includes determining the track bias based on a relative position between the third point and the fourth point on the first estimated track.

A fourth method disclosed and claimed includes the first, second, or third method. In the fourth method, receiving signals includes receiving signals from one or more transmitters that are moving with respect to time. In the fourth method, identifying the first observed change and the second observed change includes identifying the first observed change and the second observed change of the signal power levels of signals received from the one or more transmitters that are moving with respect to time. In the fourth method, modeling signal propagation includes modeling propagation of the signals from the one or more transmitters that are moving.

A fifth method is disclosed and claimed. The fifth method includes the first, second, third, or fourth method. In the fifth method, determining the track bias comprises determining expected features that correspond to the extracted features.

A sixth method is disclosed and claimed. The sixth method includes the first, second, third, fourth, or fifth method. The sixth method includes determining lines of position based on the first and second expected changes or based on the first and second observed changes. The sixth method includes advancing one or more of the lines of position (based on the relative position between the first point and the second point on the first estimated track; and determining the track bias based on the lines of position.

A seventh method is disclosed and claimed. The seventh method includes the sixth method. The seventh method includes determining the track bias based on an intersection of two of the lines of position, or determining the track bias based on an intersection of three or more of the lines of position and determining a confidence level of the track bias based on a distance between intersections of different pairs of the three or more of the lines of position.

An eighth method is disclosed and claimed. The eighth method includes the first, second, third, fourth, fifth, sixth, or seventh method. In the eighth method, identifying the first observed change or the second observed change of the signal power levels includes identifying an increase or a decrease in the signal power levels indicating transitions in the propagation paths of the signals, wherein the increase or the decrease in the signal power levels is caused by an obstruction of one of the propagation paths relative to another one of the propagation paths.

A ninth method is disclosed and claimed. The ninth method includes the first, second, third, fourth, fifth, sixth, seventh, or eighth method. The ninth method includes identifying an observed change of the polarity of the received signals. In the ninth method, the observed change of the polarity of the received signals is caused by the signals having traveled different propagation paths to two different points on the traveled path.

A tenth method is disclosed and claimed. The tenth method includes the first, second, third, fourth, fifth, sixth, seventh, eighth, or ninth method. In the tenth method, modeling signal propagation includes modeling the signal propagation based on optical frequencies or line-of-sight conditions.

An eleventh method is disclosed and claimed. The eleventh method includes the first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, or tenth method. The eleventh method includes determining a bias region for the first estimated track, and selecting one or more lines of position, based on the bias region, to advance. The eleventh method includes determining the track bias based on the selected one or more lines of position.

A twelfth method is disclosed and claimed. The twelfth method includes the eleventh method. The twelfth method includes determining a plurality of biases and determining a final bias based on a sum of the plurality biases. The twelfth method includes determining the estimated track based on the sum of the plurality of biases.

The following detailed description refers to the accompanying drawings. Also, the following detailed description does not limit the invention.

One issue with navigation applications, devices, and systems is that accuracy may be reduced as a result of errors, noise, etc. For example, the accuracy of a dead reckoning navigation system may be reduced as a result of errors in the direction of travel as measured by a compass. As another example, the accuracy of GNSS positioning systems may be reduced when the signal from the one of the satellites to the GNSS receiver (e.g., the line-of-sight or LOS) is obstructed. In this case, the path from the satellite to the GNSS receiver may be obstructed by a building, reducing the signal power. In urban areas with large buildings, signals may reflect off the buildings creating multiple signals that take different paths to the GNSS receiver. As a result, when the GNSS receiver receives a signal, the propagation path length from the satellite to the mobile receiver may be increased due to reflection or diffraction around buildings. The direct path may no longer dominate, and the resulting estimated position is biased or in error. It is not uncommon in the urban environment to see significant errors in GNSS position estimates, due to multipath effects and building shadowing.

Methods and systems described below correct for the biases or errors (e.g., that result in an urban environment) in an estimated track (or a "first estimated track"). Using the signals received in a navigation unit (e.g., a GNSS receiver), features are observed in the power level or the signal-to-noise ratio (SNR) from one or more transmitters (e.g., a satellite or television broadcast transmitter), as a navigation unit travels along a path and the navigation unit generates an estimated track. The observed features are compared to expected features along the estimated track. The expected features may be calculated using an electromagnetic wave propagation model. Either a two-dimensional (2D) footprint of nearby buildings, or a three-dimensional (3D) model of nearby buildings, may be used in the propagation model and the calculation of expected features. A corrected track may then be generated based on the comparison of the expected features to the observed features. The corrected track may be referred to as a "second estimated track. " The method may be iterative and the corrected track may include a third, fourth, etc., estimated track.

<FIG> depicts an environment <NUM> (e.g., an urban environment) for implementing navigation algorithms disclosed herein. Environment <NUM> includes buildings <NUM>-<NUM> and <NUM>-<NUM> (collectively, "buildings <NUM>"), a navigation unit <NUM>, satellites <NUM>-<NUM> through <NUM>-<NUM> (collectively, "satellites <NUM>"), and transmitters <NUM>-<NUM> and <NUM>-<NUM> (collectively, "transmitters <NUM>").

Satellites <NUM> may form part of a GNSS that permits navigation unit <NUM> to determine its position (e.g., on the surface of the earth). Satellites <NUM> are placed in varying orbits so that at any one time navigation unit <NUM> may receive signals from a number of satellites. Each satellite <NUM>-x may transmit a coded signal with an accurate time reference to a clock, such as an atomic clock. Navigation unit <NUM> includes a GNSS receiver and may lock onto signals from multiple transmitting satellites <NUM>. By knowing the positions of satellites <NUM> and extracting time reference information from the signals, navigation unit <NUM> can calculate position. The GNSS depicted in <FIG> may allow navigation unit <NUM> to determine its location (longitude, latitude, and altitude). The GNSS depicted in <FIG> may allow navigation unit <NUM> to determine its location to within a few meters. In other implementations, the GNSS system depicted in <FIG> may allow navigation unit <NUM> to determine its location less accurately or more accurately.

Navigation unit <NUM> may also determine its position using other methods (e.g., other than or in addition to using satellites). Navigation unit <NUM> may estimate its position using an odometer in a car, an inertial navigation system (e.g., speedometers, magnetometers, accelerometers, compasses, gyroscopes, etc.), dead reckoning, radio direction finding (e.g., Long Range Navigation or "LORAN"), radar, etc. Thus, environment <NUM> may not include satellites <NUM> at all. Navigation unit <NUM> may estimate its location at a given point in time. Given multiple locations over a period of time, navigation unit <NUM> may estimate a track that it has traveled. Navigation unit <NUM> may use any technique to determine position and an estimated track.

The signals received by navigation unit <NUM> from satellites <NUM> may not used to determine the first estimated track, but may be used to determine the corrected track. Satellites <NUM> may broadcast satellite TV stations. In this embodiment, navigation unit <NUM> may determine its location and the first estimated track using a navigation system or technique other than GNSS. In another example, satellites <NUM> may include satellites that form a GNSS different than the GNSS used to generate the first estimated track.

Navigation unit <NUM> may include a mobile phone, a tablet computer, a laptop, a personal digital assistant (PDA), or another portable communication device. Navigation unit <NUM> may include a dedicated navigation unit that does not include the additional features of a phone, laptop, etc..

Transmitters <NUM> may include any type of transmitter that transmits a signal that is received by navigation unit <NUM>. Transmitter <NUM> may include terrestrial broadcast antennas that have a fixed location and transmit television signals using the Advanced Television System Committee (ATSC) standard. Transmitter <NUM> may include terrestrial mobile telephone cell towers, radio towers, etc. The location of transmitters <NUM> may be known (to some degree) with respect to time. Transmitters <NUM> may be fixed with time (such as a TV broadcast tower) or may move with time (such as a satellite).

In the example of <FIG>, buildings <NUM> create a canyon <NUM> that may shadow navigation unit <NUM> from satellites <NUM> from time to time, depending on the location of navigation unit <NUM> relative to each satellite <NUM>-x. Buildings <NUM> may also shadow navigation unit <NUM> from transmitters <NUM> from time to time, depending on the location of navigation unit <NUM> relative to transmitters <NUM>. As discussed above, when one of buildings <NUM> intersects the line of sight from satellite <NUM>-x to navigation unit <NUM>, the power level of the signal received by navigation unit <NUM> from satellite <NUM>-x may be diminished. Likewise, when one of buildings <NUM> intersects the line of sight from antenna <NUM>-x to navigation unit <NUM>, the power of the signal received by navigation unit <NUM> may be diminished.

<FIG> is a block diagram of a environment <NUM> depicting additional devices other than navigation unit <NUM> shown in <FIG>. In addition to navigation unit <NUM>, environment <NUM> may include transmitters <NUM>, a server <NUM>, and a network <NUM>. Transmitters <NUM> may include satellites <NUM> (e.g., GNSS satellites), transmitters <NUM> (e.g., terrestrial broadcast antenna), and/or other transmitters. Navigation unit <NUM> may receive signals from transmitters <NUM> to estimate the location of navigation unit <NUM>, determine an estimated track, and/or correct the estimated location or track as described below.

Server <NUM> may provide services to navigation unit <NUM>. Server <NUM> may include information (e.g., that may be downloaded by navigation unit <NUM>) about the geometry surrounding navigation unit <NUM>, such as three-dimensional or two-dimensional information about buildings or foliage surrounding navigation unit <NUM>. Server <NUM> may determine or contribute to the determination of the first estimated track and/or the corrected track. Navigation unit <NUM> may communicate with server <NUM> to correct location estimations. As another example, in an implementation in which navigation unit <NUM> is a mobile phone, navigation unit <NUM> may download and run applications from server <NUM>, such as applications from Apple's App Store, Amazon's Application store for Android or Kindle devices, Google's Play Store for Android devices, Verizon's Application store for Android devices, etc. Navigation unit <NUM> may also download maps, a mapping application, or a turn-by-turn navigation application from server <NUM>.

Network <NUM> may include one or more packet switched networks, such as an Internet protocol (IP) based network, a local area network (LAN), a wide area network (WAN), a personal area network (PAN), an intranet, the Internet, a cellular network, a fiber-optic network, or another type of network that is capable of transmitting data. Network <NUM> may allow devices (e.g., navigation unit <NUM>) to connect to other devices (e.g., server <NUM>) also coupled to network <NUM>.

If navigation unit <NUM> is a mobile phone, network <NUM> may communicate wirelessly with navigation unit <NUM> using any number of protocols, such as GSM (Global System for Mobile Communications), CDMA (Code-Division Multiple Access), WCDMA (Wideband CDMA), GPRS (General Packet Radio Service), EDGE (Enhanced Data Rates for GSM Evolution), LTE (Long-Term Evolution), Universal Mobile Telecommunications System (UMTS), High-Speed Downlink Packet Access (HSDPA), etc. Navigation unit <NUM> may communicate with other devices using wireless network standards such as WiFi (e.g., IEEE <NUM>. 11x) or WiMAX (e.g., IEEE <NUM>.

Devices in environment <NUM> may be networked together such that any one device may receive signals and/or messages from any other device. Further devices in environment <NUM> may be networked together such that any one device may transmit signals and/or messages to any other device. In one implementation, navigation unit <NUM> may receive signals from transmitters <NUM> without necessarily transmitting signals to transmitters <NUM>.

The configuration of devices in environment <NUM> of <FIG> and <FIG> is illustrated for simplicity. Environment <NUM> may include more devices, fewer devices, or a different configuration of devices than illustrated. Environment <NUM> may include thousands or millions of navigation devices and/or servers. The functions performed by two or more devices may be performed by any one device. Likewise, the functions performed by any one device may be performed by any other device or multiple devices.

Environment <NUM> shown in <FIG> may include more objects, fewer objects, or different objects than illustrated. Environment <NUM> may include objects other than buildings <NUM> that interfere with the propagation of signals (e.g., trees, mountains, etc.). Environment <NUM> may include additional or fewer buildings <NUM>, additional or fewer transmitters <NUM>, additional or fewer satellites <NUM>, etc. Environment <NUM> may not include any transmitters <NUM>, satellites <NUM>, and/or buildings <NUM>.

<FIG> is a block diagram of navigation unit <NUM>. Navigation unit <NUM> may include GNSS logic <NUM>, geometry data <NUM>, and correction logic <NUM>. Navigation unit <NUM> may include additional, fewer, or a different arrangement of components than shown in <FIG>.

GNSS logic <NUM> includes logic that interprets signals received from satellites <NUM> to derive location information. GNSS logic <NUM> may include logic that interprets signals from GPS (Global Positioning System) satellites, GLONASS (Globalnaya Navigatsionnaya Sputnikovaya Sistema) satellites, Galileo satellites, BeiDou satellites, or any combination of these satellites or other navigation satellites. GNSS logic <NUM> may output location information as NMEA (National Marine Electronics Association) sentences <NUM> (e.g., NMEA <NUM> sentences). NMEA is a standard protocol for relaying data that can include location information and/or information for deriving location. NMEA sentences <NUM> may include the estimated location and/or track of navigation unit <NUM>.

Geometry data <NUM> may include 2D information (e.g., footprint information) or 3D information (e.g., 3D models) about buildings and the location of the buildings. Geometry data <NUM> may include the location of a building <NUM>-x and the corresponding footprint of the building <NUM>-x. Geometry data <NUM> may include the location of a building <NUM>-x with a 3D model of buildings <NUM>-x. Geometry data <NUM> may include information from Google Earth. Geometry data <NUM> may be stored in the Keyhole Markup Language (KML) data format. Geometry data <NUM> also includes information about the characteristics of other obstructions (e.g., mountains, trees, etc.) that may obstruct the signals (e.g., obstruct the line of sight from) transmitter <NUM> to navigation unit <NUM>.

Correction logic <NUM> may input NMEA sentences <NUM> and geometry data <NUM> and output corrected NMEA sentences <NUM>. Corrected NMEA sentences <NUM> may include location information or information from which location can be derived. Corrected NMEA sentences <NUM> may provide more accurate information than NMEA sentences <NUM>. Corrected NMEA sentences <NUM> may include the corrected location and/or track of navigation unit <NUM>. Correction logic <NUM> is described in more detail below with respect to <FIG>.

Correction logic <NUM> may include or use an electromagnetic wave propagation model or simulation tool. Using the propagation model, correction logic <NUM> may generate expected features given the 2D footprint of objects (e.g., nearby buildings) or 3D model of objects (e.g., nearby buildings). To reduce computation and model complexity, the propagation model may assume optical frequencies (e.g., that light does not diffract or includes little diffraction) when generating expected features. Alternatively, the propagation model may consider diffraction (e.g., given the frequencies of the signals of opportunity) when generating the expected features. The propagation model may first determine expected features based on optical frequencies (e.g., without diffraction) and then adjust the determined expected features based on radio frequencies (e.g., with diffraction). The 3D building model of objects (e.g., nearby buildings) may be generated (e.g., by correction logic <NUM>) from 2D footprint information.

<FIG> is a block diagram of navigation unit <NUM> in a different configuration. Navigation unit <NUM> may include navigation logic <NUM>, geometry data <NUM>, and correction logic <NUM>. Navigation unit <NUM> shown in <FIG> is a more generalized version of unit <NUM> than shown in <FIG>. Navigation unit <NUM> may include additional, fewer, or a different arrangement of components than shown in <FIG>.

Geometry data <NUM> includes the same information described above with respect to <FIG>. Navigation logic <NUM> may include GNSS logic (e.g., GNSS logic <NUM> described with respect to <FIG>) or other logic to determine location of navigation unit <NUM>. Navigation logic <NUM> may estimate its position or track using an odometer in a car, an inertial navigation system (e.g., speedometers, magnetometers, accelerometers, compasses, gyroscopes, etc.), dead reckoning, radio direction finding (e.g., Long Range Navigation or "LORAN"), radar, etc. Navigation logic <NUM> may include any logic that determines location and/or track of navigation unit <NUM>. As shown in <FIG>, navigation logic <NUM> may output estimated track <NUM> (e.g., a series of points and corresponding times) to correction logic <NUM>.

In the case of <FIG>, correction logic <NUM> inputs estimated track <NUM> and geometry data <NUM>, and outputs corrected track <NUM>. Corrected track <NUM> may be more accurate than estimated track <NUM>. Correction logic <NUM> is described below in more detail with respect to <FIG>.

Devices in environment <NUM> of <FIG> (e.g., navigation device <NUM>, server <NUM>, etc), may each include one or more computing modules. <FIG> is a block diagram of components in a computing module <NUM>. Computing module <NUM> may include a bus <NUM>, processing logic <NUM>, an input device <NUM>, an output device <NUM>, a communication interface <NUM>, and a memory <NUM>. Computing module <NUM> may include other components (not shown) that aid in receiving, transmitting, and/or processing data. Moreover, other configurations of components in computing module <NUM> are possible.

Bus <NUM> includes a path that permits communication among the components of computing module <NUM>. Processing logic <NUM> may include any type of processor or microprocessor (or families of processors, microprocessors, or signal processors) that interprets and executes instructions. Processing logic <NUM> may include an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), etc..

Communication interface <NUM> may include a transmitter and/or receiver (e.g., a transceiver) that enables computing module <NUM> to communicate with other devices or systems. Communication interface <NUM> may include a transmitter that converts baseband signals (e.g., non-modulated signals) to radio frequency (RF) signals or a receiver that converts RF signals to baseband signals. Communication interface <NUM> may be coupled to one or more antennas for transmitting and receiving electromagnetic (e.g., RF) signals. Communication interface <NUM> may include phase shifters or time delays for modulating received signals.

Communication interface <NUM> may include a network interface card, e.g., Ethernet card, for wired communications or a wireless network interface (e.g., a WiFi) card for wireless communications. Communication interface <NUM> may also include a universal serial bus (USB) port for communications over a cable, a Bluetooth wireless interface, a radio-frequency identification (RFID) interface, a near-field communications (NFC) wireless interface, etc. Communication interface <NUM> may be particularly adapted to receive signals from transmitters <NUM>, satellites <NUM> (e.g., GNSS satellites), or other transmitters (e.g., cell towers, radio towers, etc.) Communication interface <NUM> may allow communication using standards, such as GSM, CDMA (e.g., CDMA <NUM>), WCDMA, GPRS, EDGE, LTE, UMTS, HSDPA, WiFi, or WiMAX.

Memory <NUM> may store, among other things, information and instructions (e.g., applications <NUM> and operating system <NUM>) and data (e.g., application data <NUM>) for use by processing logic <NUM>. Memory <NUM> may include a random access memory (RAM) or another type of dynamic storage device, a read-only memory (ROM) device or another type of static storage device, and/or some other type of magnetic or optical recording medium and its corresponding drive (e.g., a hard disk drive).

Operating system <NUM> may include software instructions for managing hardware and software resources of computing module <NUM>. Operating system <NUM> may include GNU/Linux, Windows, OS X, Android, iOS, an embedded operating system, etc. Applications <NUM> and application data <NUM> may provide network services or include applications, depending on the device in which the particular computing module <NUM> is found.

Input device <NUM> may allow a user to input information into computing module <NUM>. Input device <NUM> may include a keyboard, a mouse, a microphone, a camera, a touch-screen display, etc. Some devices may not include input device <NUM>. In other words, some devices (e.g., a "headless" device such as server <NUM>) may be remotely managed through communication interface <NUM> and may not include a keyboard.

Output device <NUM> may output information to the user. Output device <NUM> may include a display, a display panel, light-emitting diodes (LEDs) a printer, a speaker, etc. Headless devices, such as server <NUM>, may be autonomous, may be managed remotely, and may not include output device <NUM> such as a display.

Input device <NUM> and output device <NUM> may allow a user to activate and interact with a particular service or application. Input device <NUM> and output device <NUM> may allow a user to receive and view a menu of options and select from the menu options. The menu may allow the user to select various functions or services associated with applications executed by computing module <NUM>.

Computing module <NUM> may include more or fewer components than shown in <FIG>. Computing module <NUM> may include a speedometer, a magnetometer, an accelerometer, a compass, a gyroscope, etc. The functions described as performed by any component may be performed by any other component or multiple components. Further, the functions performed by two or more components may be performed by a single component.

Computing module <NUM> may perform the operations described herein in response to processing logic <NUM> executing software instructions contained in a tangible, non-transient computer-readable medium, such as memory <NUM>. A computer-readable medium include a physical or logical memory device. The software instructions may be read into memory <NUM> from another computer-readable medium or from another device via communication interface <NUM>. The software instructions contained in memory <NUM> may cause processing logic <NUM> to perform processes that are described herein.

As described above, methods and systems described herein may correct an estimated track to generate a corrected track. <FIG> is a flowchart of a process <NUM> for correcting the estimated track of a navigation device. Process <NUM> may be executed by navigation unit <NUM>, server <NUM>, and/or other devices. Process <NUM> is described with respect to <FIG>, which illustrates environment <NUM> (e.g., a simplification of environment <NUM>). Environment <NUM> includes two buildings <NUM> (individually "building <NUM>-x") and two satellites <NUM> (individually "satellite <NUM>-x"). In the following example, satellites <NUM> form part of a GNSS and navigation unit <NUM> includes navigation logic <NUM> that includes GNSS logic (e.g., GNSS logic <NUM> shown in <FIG>) and described above. Buildings <NUM> cause multipath reflections, diffraction, and building shadowing, which introduce errors in the estimated track generated by GNSS logic <NUM>.

Process <NUM> begins when navigation unit <NUM> (not shown in <FIG> for clarity) travels along a path (block <NUM>). The path traveled by navigation unit <NUM> is not shown in <FIG> because the traveled path (e.g., the exact traveled path) may not be known. Rather, the path is estimated by navigation unit <NUM> (e.g., by GNSS logic <NUM> or navigation logic <NUM>) (block <NUM>) using any navigation estimation technique. In the example of <FIG>, as navigation unit <NUM> travels along the path, navigation logic <NUM> generates an estimated track <NUM> (block <NUM>). Estimated track <NUM>, however, includes position errors as compared to the actual traveled path. As discussed above, the position errors may be caused by multipath and diffraction as signals from satellites <NUM> reflect off and propagate around buildings <NUM>. As shown, estimated track <NUM> is a line that includes points (e.g., coordinates). Navigation logic <NUM> may also record the corresponding time for each point along track <NUM>, i.e., the time navigation unit <NUM> is estimated to be at the corresponding point along estimated track <NUM>. As shown in <FIG>, navigation logic <NUM> estimates that navigation unit <NUM> is at point A1 at time T1 and at point B1 at time T2. In this example, time T2 is later than time T1 (e.g., it is estimated that navigation unit <NUM> travels from point A1 to point B1).

As navigation unit <NUM> travels along its path, it also receives signals (block <NUM>) that are used to correct or fix estimated track <NUM>. The signals may be the same signals that are used to determine estimated track <NUM>. Navigation unit <NUM> may use the signals received from satellites <NUM> to correct or fix estimated track <NUM> as well as to generate estimated track <NUM> to begin with. In one implementation, navigation unit <NUM> uses signals received from multiple sources (e.g., multiple satellites <NUM> and/or transmitters <NUM>) or different sources (e.g., transmitters <NUM>) to correct or fix estimate path <NUM> than to generate the estimated track <NUM>. In one implementation, the signals used to correct estimated track <NUM> may originate from one, two, many, most, or all of satellites <NUM> used in the GNSS. In the following example, however, only signals from satellite <NUM>-<NUM> and <NUM>-<NUM> are used for ease of understanding.

Receiving signals (block <NUM>) to correct the estimated track includes recording the power level of the signals and the corresponding time the power level is observed. Recording the power level of the signal may include recording the signal-to-noise ratio (SNR). <FIG> is a graph of a plot of an example of measured SNR over a period of time (light dashed line <NUM>) for the power from satellite <NUM>-<NUM> as seen by navigation unit <NUM>. In the case of navigation unit <NUM> using navigation logic <NUM>, the signal power may be received by correction logic <NUM> in NMEA sentence <NUM>. Because the power measurements are associated with an observation time, the power measurements may be associated with a position along estimated track <NUM>.

Features are extracted from the received signals (block <NUM>). An extracted feature may include a change in the signal power (e.g., SNR) of a satellite signal (e.g., an increase or a decrease). In the current example, as shown in <FIG>, when navigation unit <NUM> is estimated to be at point A1 (e.g., at time T1), the power level of the signal from satellite <NUM>-<NUM> dropped (as compared to a previous measurement at time T1-x). In this example, the drop in the power level of the signal received from satellite <NUM>-<NUM> is caused by the building <NUM>-<NUM> (e.g., the edge of the building) blocking the signal from satellite <NUM>-<NUM> to navigation unit <NUM>. That is, the signal from satellite <NUM>-<NUM> to navigation unit <NUM> was direct, unobstructed, or LOS immediately before time T1 and indirect, obstructed, and/or non-LOS immediately after time T1, thus causing the signal power to drop as seen by navigation unit <NUM>. As shown in <FIG>, the drop in power level of the signal from satellite <NUM>-<NUM> is abrupt, dropping <NUM> dB in less than <NUM> seconds.

A feature may be caused when the signal from the satellite <NUM>-<NUM> to navigation unit <NUM> transitions from traveling to navigation unit <NUM> from a first path (e.g., direct, LOS, and/or unobstructed) to a second path (e.g., non-LOS, obstructed, or more obstructed). The first path and the second path have different propagation characteristics, such as different attenuation (e.g., caused by an obstruction that affects the power level of the received signal), different type of path (e.g., direct versus reflected), or both (reflected but through material having different attenuation). A building blocking the line-of-sight from satellite <NUM> to navigation unit <NUM> is just one example of how a the signal can transition.

Also, when navigation unit <NUM> is estimated to be at point B1 (e.g., at time T2), the power level of the signal from satellite <NUM>-<NUM> dropped (as compared to a previous measurement at time T2-x). In this example, the drop in the power level of the signal received from satellite <NUM>-<NUM> is caused by building <NUM>-<NUM> blocking the signal from satellite <NUM>-<NUM> to navigation unit <NUM>. The power level around time T2 is not shown in <FIG> for ease of understanding.

Expected features are determined along with the corresponding lines of position (block <NUM>). Given the geometry data <NUM> (e.g., 3D model of building <NUM>-<NUM>) and the location of satellite <NUM>-<NUM>, correction logic <NUM> determines (through the modeling of signal propagation) that the drop in signal power (the extracted feature of the signal received from satellite <NUM>-<NUM> at point A1 at time T1), should have occurred at point A2 along estimated track <NUM> rather than at point A1. Correction logic <NUM> may construct a line of position (LOP) <NUM>. LOP <NUM> may be based on (e.g., may be defined by) the location of satellite <NUM>-<NUM> (at time T1), the location of the edge of building <NUM>-<NUM>, and/or estimated track <NUM>. LOP <NUM> may include a line that intersects the edge of building <NUM>-<NUM>, the location of satellite <NUM>-<NUM>, and/or estimated track <NUM> and may be defined in three dimensions (e.g., azimuth and elevation as seen from the intersection of the line with estimated track <NUM>). LOP <NUM> may include a projection (e.g., on the surface of the earth) of the line that intersects the edge of building <NUM>-<NUM>, the location of satellite <NUM>-<NUM>, and/or estimated track <NUM> and may be defined in two dimensions (e.g., azimuth as seen from the intersection of the line with estimated track <NUM>). Thus, correction logic <NUM> may base LOP <NUM> on any combination of the location of satellite <NUM>-<NUM>, the location of building <NUM>-<NUM> (e.g., the edge), and/or estimated track <NUM>.

<FIG> also includes a plot of an example of expected SNR over a period of time (dark dashed line <NUM>) for the power from satellite <NUM>-<NUM> as seen by navigation unit <NUM>. As shown in <FIG>, given the estimated track <NUM>, the location of satellite <NUM>-<NUM>, and the building information, the expected SNR is shown as a dark dashed line <NUM>. As indicated by arrow <NUM>, the measured feature (a drop in signal power at time T1) occurred earlier than the expected feature (a drop in signal power at time TZ, which is the time that corresponds to point A2 on estimated track <NUM>).

In addition, in this example, given the geometry data <NUM> (e.g., 3D model of building <NUM>-<NUM>) and the location of satellite <NUM>-<NUM>, correction logic <NUM> may determine (through the modeling of signal propagation) that the drop in signal power (the extracted feature of the signal received from satellite <NUM>-<NUM> at point B1 at time T2), should have occurred at point B2 along estimated track <NUM> rather than at point B1. Correction logic <NUM> may construct a LOP <NUM>. LOP <NUM> may be based on (e.g., may be defined by) the location of satellite <NUM>-<NUM> (at time T2), the location of the edge of building <NUM>-<NUM>, and/or estimated track <NUM>. LOP <NUM> may include a line that intersects the location of satellite <NUM>-<NUM>, the location of the edge of building <NUM>-<NUM>, and/or estimated track <NUM> and may be defined in three dimensions (e.g., azimuth and elevation from the perspective of the intersection with track <NUM>). LOP <NUM> may include a projection of the line that intersects the location of satellite <NUM>-<NUM>, the location of the edge of building <NUM>-<NUM>, and/or estimated track <NUM> and may be defined in two dimensions (e.g., azimuth from the perspective of the intersection with track <NUM>). Thus, correction logic <NUM> may base LOP <NUM> on any combination of the location of satellite <NUM>-<NUM>, the location of building <NUM>-<NUM> (e.g., the edge), and/or estimated track <NUM>. As described in more detail below, an extracted and an expected feature may include a change in the power level of a specific, isolated, delayed propagation path from transmitter <NUM> (e.g., a reflected signal from a satellite).

As indicated above, correction logic <NUM> may determine that the extracted feature (e.g., drop in signal power) of the signal received from satellite <NUM>-<NUM> should have occurred at a different point by comparing the extracted feature to an expected feature (e.g., "matching" the extracted and expected features). A comparison may be made between the received signals and the expected (modeled) signals to determine whether the features observed along a segment (e.g., of track <NUM>) are of a characteristic that is useful to the generation of LOPs (e.g., to determine that an observed feature matches an expected feature). The decision can be made to use a feature for LOP generation, or to ignore the feature. Characteristics of the received signal (e.g., dips and bumps of the power level) can be measured and compared to the expected results. In one example, if a rate of rise or fall in the received signal power does not match the expected rate of the raise or fall in the expected signal to some difference threshold, then the feature from the received signal may be discarded. As another example, if the overall amount of rise or fall in the received signal power (e.g., absolute or relative) does not match the amount of rise or fall in the expected signal to some allowable threshold, then the features from this segment may be discarded. As yet another example, if the distance between a rise and a fall of power (e.g., the width of the bump in the case of a signal bump), or if the distance between a fall and a rise of power (e.g., the width of the dip in the case of a signal dip), does not match between the received signal and expected signal to some difference threshold, then the features may be discarded (e.g., considered not useful) for LOP generation.

A track bias is determined based on the expected features and/or the measured, extracted features (block <NUM>). To determine the bias in the current example, LOP <NUM> may be advanced in time from time T1 to time T2. In other words, LOP <NUM> is moved according to a vector defined by point A1 (at time T1) and point B1 (at time T2). Although point A1 and point B1 may have an error introduced by multipath, the relative position between point A1 (at time T1) and point A2 (at time T2) may be considered to be approximately accurate. As shown in <FIG>, LOP <NUM> is advanced to LOP <NUM>. In this case, LOP <NUM> (from time T2) and LOP <NUM> (advanced in time to time T2) may intersect at point C1.

Particularly in the case where LOP <NUM> and LOP <NUM> are defined in three dimensions, LOP <NUM> and LOP <NUM> may not actually intersect at a well defined point. In this case, point C1 may be the point that has the minimum average distance to each LOP. In the case that multiple LOPs are advanced (e.g., in the case where multiple two dimensional LOPs are advanced to a third LOP), the lines may not intersect at a well defined point. Again, in this case, point C1 may be the point that has the minimum average distance or the minimum average squared distance to each LOP. In the case of two LOPs in three dimensions, point C1 may be the midpoint of the line between the LOPs (e.g., LOP <NUM> and LOP <NUM>) that has the shortest length. Thus, at time T2, point C1 is considered a more accurate location of navigation unit <NUM> than point B1. The path bias may then be determined as the vector between point B1 and point C1.

The advancement of an LOP (e.g., LOP <NUM> to LOP <NUM>) may be based on information other than (and/or in addition to) the first estimated track. an accelerometer, speedometer, compass, etc., in navigation unit <NUM> may inform the displacement of the LOP. That is, given a known direction and speed (e.g., without acceleration), the displacement the LOP may be determined. Track <NUM> is based on information provided from the accelerometer, speedometer, compass, etc. in navigation unit <NUM>.

Correction logic <NUM> may then generate a corrected path by shifting the points in path <NUM> by bias vector <NUM>. Correction logic <NUM> may limit this particular correction by bias vector <NUM> in time and/or space. Bias vector <NUM> may only be considered an accurate representation of the error in track <NUM> in the immediate vicinity of buildings <NUM>-<NUM> and <NUM>-<NUM>. Methods of determining bias regions are described in more detail below. At time T2, points along path <NUM> may be biased by bias vector <NUM> back in time until time T1.

Process <NUM> describes the advancement of one LOP (e.g., LOP <NUM>) to intersect another LOP (e.g., LOP <NUM>). Process <NUM> may be repeated numerous times by advancing different LOPs (e.g., from other buildings not shown in environment <NUM>) to intersect with a common, reference LOP (e.g., LOP <NUM>). This process may generate numerous bias vectors (e.g., like bias vector <NUM>). These numerous bias vectors are added and/or weighed to generate a total bias vector that is then used to correct estimated track <NUM>. Some bias vectors, however, may more accurately reflect the errors in the estimated track than other bias vectors. A bias vector generated from a more recent LOP (relative to the reference LOP) may more accurately reflect the error in the estimated track than a bias vector generated from a less recent LOP. A bias vector generated from an LOP closer to the reference LOP may more accurately reflect the error in the estimated track than a bias vector generated from an LOP father from the reference LOP. Bias vectors may first be weighed (e.g., scaled) based on each vector's determined (or perceived) accuracy, before summing the vectors to generate the total bias vector. Bias vectors that are similar may be determined or considered to be more accurate than a bias vector that is less similar than others.

As described above, process <NUM> may be repeated numerous times by advancing different LOPs (e.g., from other buildings not shown in environment <NUM>) to intersect with a common, reference LOP (e.g., LOP <NUM>). Further, a bias vector may be generated that takes into account the numerous LOPs. In one implementation, point C1 may be the point that has the minimum average distance to each LOP or the minimum average squared distance to each LOP. Each LOP may also be weighted (e.g., the distance from point C1 to the LOP may be given a weight) based on the perceived or determined accuracy of the LOP (e.g., based on the age of the LOP).

If a bias vector is formed by a good (e.g., tight) intersection of LOPs, then the bias vector may be considered to have a high confidence level (e.g., perceived or determined to be more accurate). If a bias vector is formed by a poor (e.g., loose) intersection of LOPs, then the bias vector may be considered to have a low confidence level (e.g., perceived or determined to be less accurate). A high confidence level means a low degree of expected error in the corrected position. A low confidence level means a higher degree of expected error in the corrected position. The determination of point C1 may be performed in numerous ways.

As described above, a bias vector (e.g., vector <NUM>) may be combined with one or more other bias vectors (e.g., a bias vector that was determined earlier or with respect to a different reference bias vector). In this case, the one or more other bias vectors may each be weighted based on perceived or determined accuracy of the corresponding bias vector. One or more of the above techniques can be used to determine a final or total bias vector. Multiple LOPs may be advanced to a single reference LOP and/or one or more previous bias vectors may be combined with a current bias vector, etc..

<FIG> is a flowchart of a process <NUM> for determining the total bias vector. "Bias regions" may be determined (block <NUM>). A "bias region" includes a portion of an estimated track over which a bias or error (e.g., bias vectors) are expected to be consistent (e.g., more highly correlated). Beyond a bias region, errors associated with a track become less correlated. The size of bias regions may vary along the estimated track. <FIG> is a diagram of an estimated track <NUM> divided into different bias regions A through L. Bias regions are separated by points and are circled (except for bias region A). As noted above, errors in estimated track <NUM> are expected to be relatively consistent in a bias region.

A bias region may be determined by calculating a correlation metric that is based on the change in LOS/non-LOS patterns (e.g., non-obstructed LOS/obstructed LOS from satellites <NUM> to navigation unit <NUM>) over a period of time. <FIG> illustrates the LOS/non-LOS patterns between satellites <NUM>-<NUM> through <NUM>-<NUM> and navigation unit <NUM>. The abscissa in <FIG> represents elapsed time during a trip. The ordinate represents the status of satellites <NUM>-<NUM> through <NUM>-<NUM>: no color indicates that a near-LOS or close to near-LOS condition is determined to exist between the corresponding satellite and navigation unit <NUM> (e.g., an unobstructed LOS); a dark region indicates that a LOS condition is determined not to exist between the corresponding satellite and navigation unit <NUM> (e.g., an obstructed LOS). Different bias regions are determined based on the changing patterns. When a certain percentage of conditions change (e.g., two of five), then a boundary of bias regions may be determined. As another example, a boundary between bias region A and bias region B is determined at the point where the status of the link to satellite <NUM>-<NUM> and the status of the link to satellite <NUM>-<NUM> change. The boundary between bias region B and bias region C is determined at the point where the link status to satellite <NUM>-<NUM> changes. <FIG> shows the boundaries between bias regions A through L that are shown in <FIG>.

The boundary between bias regions may be determined based on time and/or distance. A boundary may be determined after a certain period of time or after a certain distance, or a combination of time and distance.

LOPs are selected to advance to the reference LOP (block <NUM>) for the determination of one or more bias vectors. As mentioned above, multiple LOPs (e.g., LOP <NUM>) may be advanced to determine one or more bias vectors. Which LOPs should be advanced may be determined based on a number of factors. LOPs in the same bias region as the reference LOP are advanced. LOPs in a particular number of bias regions surrounding the bias region with the reference LOP are advanced. LOPs in surrounding bias regions are advanced, as long as the surrounding bias region is sufficiently correlated with the current bias region.

LOPs are selected to advance to the reference LOP based on a time period. LOPs within a certain time period behind the reference LOP may be advanced. LOPs are selected to advance to the reference LOP based on a distance. LOPs within a certain distance of the reference LOP may be advanced. A bias vector may be determined (block <NUM>) as discussed above (e.g., based on a point that has the shortest distance to all the LOPs, etc). Stated another way, rather than selecting LOPs to advance to the reference LOP, multiple bias vectors may be determined and selected to be summed and/or weighted to determine the total bias (e.g., as described above). In this case, bias vectors may be selected based on the same criteria discussed above for selecting LOPs to advance, discussed above. If a bias vector is formed by a good (e.g., tight) intersection of LOPs, then the bias vector may be considered to have a high confidence level (e.g., perceived or determined to be more accurate). If a bias vector is formed by a poor (e.g., loose) intersection of LOPs, then the bias vector may be considered to have a low confidence level (e.g., perceived or determined to be less accurate). A high confidence level means a low degree of expected error in the corrected position. A low confidence level means a higher degree of expected error in the corrected position. The determination of point C1 may be performed in numerous ways.

Multiple bias vectors may be selected (block <NUM>). Previous bias vectors determined from other reference LOPs may be used to determine a final bias vector. Bias vectors may be selected based on the same criteria used to select LOPs to advance to the reference LOP used to determine the bias vector with respect to block <NUM>. The factors used to select the bias vectors may be similar to the factors used to select the LOPs. Bias vectors resulting from reference LOPs that are closer in time may be given greater weight than bias vectors that result from reference LOPs that are not as close in time. Bias vectors resulting from reference LOPs that are closer in distance may be given greater weight than bias vectors that result from reference LOPs that are not as close. Bias vectors in the same bias region may be given greater weight than bias vectors in different bias regions.

The bias vectors may be weighed and/or summed (block <NUM>). The selected bias vectors can be weighed and/or summed to generate a total bias vector. As discussed above, the bias vectors may be weighted based on a number of factors. The factors used to weigh the bias vectors may be similar to the factors used to select the LOPs. Bias vectors resulting from reference LOPs that are closer in time may be given greater weight than bias vectors that result from reference LOPs that are not as close in time. Bias vectors resulting from reference LOPs that are closer in distance may be given greater weight than bias vectors that result from reference LOPs that are not as close. Bias vectors in the same bias region may be given greater weight than bias vectors in different bias regions. Given these various weights for each factor, a total weight for each bias vector is calculated, by multiplying individual weights together for each individual bias vector. Non-zero total weights, or weights which exceed a minimum threshold may then normalized. Each weight is then multiplied by its associated bias vector, and the results are then summed to form a total correction to be applied to an estimated track position.

If the bias vectors are all substantially similar (e.g., the advanced LOPs intersect the reference LOP at approximately the same point), then there is a high level of confidence in those bias vectors. In other words, there is a low degree of expected error in the corrected position. If the bias vectors are not substantially the same (e.g., the advanced LOPs do not intersect the reference LOP at approximately the same point), then there is a low level of confidence in those bias vectors (e.g., a high degree of expected error in the corrected position). Further, if two LOPs are nearly parallel (e.g., so that a slight shift in either LOP results in a large error in the corrected position), then there a low level of confidence in the corrected position. The degree of confidence (e.g., by the tightness of fit) of a bias vector may be used to determine its weight when combining bias vectors to generate the total bias vector correction.

<FIG> and <FIG> describe one method to advance LOPs to determine a bias vector according to process <NUM>. <FIG> and <FIG> describe an additional way of implementing process <NUM> to advance LOPs to determine a bias vector. <FIG> and <FIG> depict the same environment <NUM> as described in <FIG> and <FIG>. <FIG> shows estimated track <NUM>, including a point A1 estimated for time T1 and a point B1 estimated for time T2. In this implementation, a LOP <NUM> is determined from the location of satellite <NUM>-<NUM> to estimated point A1 (block <NUM>). Another LOP <NUM> is determined from the location of satellite <NUM>-<NUM> to estimated point B1.

As described above, expected features are determined along the estimated path (block <NUM>). Point A2 is determined as well as point B2. As shown in <FIG>, LOP <NUM> is advanced according to the relative locations of point A2 and B2. That is, it may be assumed that between time T1 and T2, the relative position of navigation unit <NUM> (defined by point A2 and point B2) may be assumed to be accurate, even if the absolute position is not considered accurate. In other words, it may be assumed that between time T1 and T2, the relative position of the expected feature positions (defined by point A2 and point B2) as determined by the propagation model may be assumed to be accurate. In this case, as shown in <FIG>, advanced LOP <NUM> intersects LOP <NUM> at point C1'. A bias vector <NUM>' is determined between point B2 and C1'. In this case, however, bias vector <NUM>' is in the opposite direction as needed to correct the error in point B2. Reversing bias vector <NUM>' while maintaining one end point at point B2 determines point C1, which is the corrected point. As discussed above, points along estimated track <NUM> may be adjusted according to bias vector <NUM>. As also discussed above, additional LOPs may be advanced and summed to generate a more accurate total bias vector.

In the examples above (e.g., <FIG>, <FIG>, <FIG>, and <FIG>), navigation unit <NUM> travels along a path. In addition, the method may estimate a corrected position of navigation unit <NUM> (e.g., when stationary) over time as the transmitters (e.g., satellites <NUM>) move. In this case, the LOPs of 4A, 4B, 9A and 9B can be generated as satellite <NUM>-x moves (e.g., in an arc) so that a feature either appears or disappears (e.g., based on the propagation model using diffraction of LOS modeling) to navigation unit <NUM> (e.g., navigation unit <NUM> may be stationary). In this case, the algorithm operates as described, but advancement may be omitted for the LOPs as the receiver may be considered stationary for the period of time of interest.

The process can be repeated several times to iteratively correct the track. The process can be completed, and then the updated positions (updated track) can be used as a new 'estimated' track. This new estimate can be used as an input to the algorithm, and the same steps can be executed with the same measurements to generate a new set of corrected positions. This can be repeated several times, where the weights and algorithm parameters may or may not be changed in each iterative stage, and where no new observed signal levels are required.

As described above, the presence or absence of a direct-path signal (LOS or with diffraction) is used to determine expected signals and to extract features. Correction logic <NUM> may use measured and expected signals that are reflected (e.g., off a building) as well as direct-path signals. Features and/or LOPs can be extracted from non-LOS or reflected signals. The signals received along the traveled path (block <NUM>) may include reflected signals (as well as signals that are not reflected). A signal may reflect off a building that is received in navigation unit <NUM> and the reflected signals may represent a delayed echo in the radio frequency signal. A signal processor (e.g., a correlator, an equalizer, or other mechanism) may detect or isolate reflected signals. A correlator or other signal processing device, may determine the signal power level at various delay times relative to the direct path signal. An increase or decrease in the power level of such a delayed signal, representing a reflection can also be used as a feature. Just as with direct-path signals, reflected signals may be obstructed by objects (such as another building between navigation unit <NUM> and the building that is reflecting the signal). In this case, reflected signals may transition from being present (e.g., a strong signal) to being absent (e.g., a weak signal); or transition from being absent (e.g., a weak signal) to present (e.g., a strong signal). Using geometry data <NUM>, correction logic <NUM> determines expected features from expected reflected signals (block <NUM>). Thus, correction logic <NUM> (e.g., employing process <NUM>) may correct errors in the estimated track by comparing observed power levels of reflected signals (e. isolated echos) to expected power levels of reflected signals from a propagation model.

As described above, expected features and/or LOPs are determined (block <NUM>). As discussed above with respect to <FIG>, expected features may be determined for a receiver as it travels along estimated track <NUM>, which may be determined by navigation logic <NUM>. Expected features may be determined for navigation unit <NUM> for multiple variations from the expected track. One type of variation could be an offset from estimated track <NUM> (or a second estimated track, etc.), but variations can also include other types of differences from estimated track <NUM>. For each variation from the estimated track <NUM>, LOPs, bias vectors, and new estimated tracks, may be calculated as described with respect to <FIG>. The multiple estimated tracks may be used individually or combined either by averaging, combining LOPs or bias vectors, or combining in some other method. This may allow for the use of multiple variations of the estimated track <NUM> (or a second estimated track, etc.) to improve results, but may not require the use of multiple variations of the estimated track <NUM>. Each of the variations of the estimated track are not being evaluated as a 'best fit' for the corrected track, but may provide information that when combined produce a better corrected track. Therefore, the process may be repeated for multiple variations from the first estimated track, and the resulting LOPs or bias vectors may be combined and/or used individually to produce an updated track.

Expected features may be determined based on one or more extracted feature. Expected features may be determined in the vicinity around an expected feature (e.g., based on distance from the expected feature). In one implementation, expected features are only determined based on extracted features, which may relieve correction logic <NUM> from determining expected features unnecessarily. Further, methods and systems described herein may allow for expected features to be determined along an estimated track (e.g., an estimated track <NUM> as a line) rather than in a larger volume of space surrounding an estimated track <NUM>, which may also relieve correction logic <NUM> from determining expected features unnecessarily. Further, fewer expected features may reduce processing as matching expected features with extracted (e.g., measured) features may likewise be reduced. Methods and systems described herein calculate for a geometrical error based on the determination that an expected feature matches an extracted feature.

Methods and systems described above may also correct for the biases or errors in an estimated track that result from an indoor environment. Biases and errors caused by multipath, reflections, etc. may be caused inside a building where signals may be attenuated and/or reflected by structures within the building (or from outside the building).

Methods and systems described above may also be employed to update or correct the position of two navigation units <NUM> working together. The relative position may be known, and observed and expected signals may be combined from the two navigation units <NUM>. The advancement of one LOP from one navigation unit <NUM> to be combined with the LOP of another navigation unit <NUM> may be conducted with estimated or known relative position information of the two navigation units <NUM>. Also, bias vectors from one navigation unit <NUM> may be combined with bias vectors from another navigation unit <NUM> to provide an improved result. Therefore, LOPs and/or bias vectors from multiple navigation units <NUM> may be combined to provide a single bias vector.

Extracted features can also include other identifiable characteristics of the received signal, and are not limited to sharp increases or decreases in the received power level. Features may include characteristics other than shifts in received power level. Features may include changes in the polarization of the signal; changes in other representations of the signal (e.g., in the time domain or the frequency domain) such as those determined by transforms such as the Fourier transform, Fast Fourier Transform, Discrete Cosine Transform, wavelet transform, or another filtering operation; changes in signal level between LOS and non-LOS conditions; changes in signal level entirely in non-LOS conditions; and/or changes in signal level among a specific reflected or diffracted path of the echo profile.

Line-of-sight (LOS) conditions are considered to exist when the received radio frequency signal is not significantly obstructed or attenuated, and the received signal power level at a given position is within a few decibels (dB) of the maximum signal power level (e.g., the theoretical power level given normal unobstructed propagation through atmosphere and/or received from the transmitter at other position in the region. All signals in the region can be attenuated by a common entity, such as attenuation from precipitation, but LOS conditions still exist if the signal level at any position of interest has no other significant blockage or attenuation other than this common attenuation for all receivers in the region, and the signal level is within a few dB of the maximum signal level in the region.

Geometry data <NUM> is not be stored in navigation unit <NUM> or directly used by correction logic <NUM>. Correction logic <NUM> may query a database of geometry data (e.g., that stores geometry data <NUM>). The database may return an indication of whether an optical line of sight path is exists or not between navigation unit <NUM> and the corresponding transmitter. Conversion from optical LOS conditions to radio frequency power levels may be conducted (e.g., by correction logic <NUM>) without direct access to the geometry data (e.g., geometry data <NUM> that may include 2D or 3D geometry). This may be particularly useful in the situation where geometry data is proprietary, too extensive to be stored in navigation unit <NUM>. This may also allow for the shift of some computation to a device other than navigation unit <NUM> (e.g., to server <NUM>). As described above, some or all of correction logic <NUM> may be performed by devices other than navigation unit <NUM> (e.g., by server <NUM>). Some or all of the logic of navigation logic <NUM> may also be shifted to a device such as server <NUM>. Raw satellite data may be sent to server <NUM> and first estimated track <NUM> may be returned to navigation unit <NUM> for correction logic <NUM>. Correction logic <NUM> may be in server <NUM> as well and corrected track <NUM> may be returned to navigation unit <NUM> without transmitting estimated track <NUM> to navigation unit <NUM>.

Data stored in geometry data may be generated using the method and apparatus described in the <CIT>, titled "Estimating Characteristics of Objects in Environment.

As described herein, a method may comprise receiving signals along a traveled path over a period of time; recording signal power levels of the received signals over the period of time; receiving a first estimated track of the traveled path; identifying a feature of the received signal power levels, wherein the feature is caused by the signals having traveled different propagation paths; and generating a second estimated track based on the feature and the first estimated track.

The method may further comprise, associating the recorded signal power levels with the first estimated track based on time; and determining a location on the first estimated track associated with the feature. In the method, the feature of the received signal power levels is an observed feature and the location is an observed location. The method may further comprise determining expected power levels of the received signals along the first estimated path; and identifying an expected feature of the expected power levels. The method may further comprise determining an expected location on the first estimated track of the expected feature. Generating of the second estimated track may include generating the second estimated track based on the observed location and the expected location. In the method, determining the expected power levels may include modeling propagation of the received signals to the first estimated track.

Modeling propagation may include modeling line-of-sight (LOS) propagation paths, each path having a different attenuation. The feature of the signal power levels is a decrease of the signal power levels. The feature of the received signal power levels is an increase of the received signal power levels.

A method described herein may include receiving signals along a traveled path over a period of time; recording signal power levels of the received signals over the period of time; receiving a first estimated track of the traveled path; identifying an observed feature of the received signal power levels; determining a location on the first estimated track associated with the observed feature; determining expected power levels of the received signals along the first estimated path; identifying an expected feature of the expected power levels; and determining an expected location on the first estimated track of the expected feature; and generating a second estimated track based on the observed location, the expected location, and the first estimated track.

The method may comprise associating the recorded signal power levels with the first estimated track based on time. Determining the expected power levels includes modeling propagation of the received signals to the first estimated track. Modeling propagation includes modeling LOS propagation and modeling non LOS propagation from the transmitter to the first estimated track. The observed feature of the signal power levels is a decrease of the signal power levels. The observed feature of the received signal power levels is an increase of the received signal power levels.

In this specification, various embodiments have been described with reference to the accompanying drawings.

While a series of blocks has been described with regard to the processes illustrated and described, the order of the blocks may be modified in other implementations. Further, non-dependent blocks may be performed in parallel.

It will be apparent that different aspects of the description provided above may be implemented in many different forms of software, firmware, and hardware in the implementations illustrated in the figures. Thus, the operation and behavior of these aspects were described without reference to the specific software code, it being understood that software and control hardware can be designed to implement these aspects based on the description herein.

Further, certain portions of the invention may be implemented as a "component" or "system" that performs one or more functions. These components/systems may include hardware, such as a processor, an ASIC, or a FPGA, or a combination of hardware and software.

Claim 1:
A method comprising:
receiving signals (<NUM>), in a receiver from a transmitter, along a traveled path and recording, in a memory, signal power levels of the received signals, wherein the traveled path is a path actually traveled by the receiver;
inputting a first estimated track (<NUM>), wherein the first estimated track includes an estimate of the traveled path of the receiver;
identifying, by a processor, extracted features (<NUM>) of the recorded signal power levels, wherein identifying the extracted features includes:
identifying a first observed change of the recorded signal power levels corresponding to a first point (A1, T1) on the first estimated track (<NUM>), and
identifying a second observed change of the recorded signal power levels corresponding to a second point (B1, T2) on the first estimated track (<NUM>),
wherein each of the first observed change and the second observed change is caused by a propagation path between the transmitter and the receiver transitioning between an unobstructed and an obstructed propagation path as the receiver moves along the traveled path; and
determining, by the processor, expected features (<NUM>) of expected signal power levels (<NUM>), wherein determining expected features includes:
generating (<NUM>) expected signal power levels (<NUM>) at points along the first estimated track (<NUM>) by modeling signal propagation,
identifying a first expected change of the expected signal power levels corresponding to a third point (A2) on the first estimated track (<NUM>), and
identifying a second expected change of the expected signal power levels corresponding to a fourth point (B2) on the first estimated track (<NUM>),
wherein each of the first expected change and the second expected change is caused by a modeled propagation path transitioning between an obstructed propagation path and an unobstructed propagation path,
determining a track bias (<NUM>) based on the first point (A1, T1) associated with first observed change, the second point (B1, T2) associated with second observed change, the third point (A2) associated with first expected change, and the fourth point (B2) associated with the second expected change; and
generating a corrected track (<NUM>) based on the first estimated track and the track bias.