Patent Description:
Patent Application Publication No. <CIT> discloses obtaining a current radio signature having a plurality of measured signal qualities. The current radio signature is compared with a plurality of reference radio signatures. When the comparing identifies a match between the current radio signature and a reference radio signature, the radio receiver is deemed to be localized to the global position associated with the reference radio signature.

Patent Application Publication No. <CIT> discloses estimating velocity of a mobile station in a wireless communication system using time-frequency signal processing and a geographical database. The geographical database is used for prediction of ray trajectory and ray power to provide an estimate of propagation delay associated with database points.

Patent Application Publication No. <CIT> discloses a method for estimating the influence of a building on a mobile communication terminal. The method includes acquiring reception information indicative of an intensity of a radio wave and acquiring location information indicative of a location where the radio wave was received. The method includes estimating the intensity of the radio wave according to the location and comparing the estimated intensity and the intensity indicated by the reception information. The method estimates the influence of the building based on the result of the comparison.

A first method is described and claimed. The first method includes receiving signals, in a receiver from one or more transmitters, and recording corresponding observations associated with the received signals and recording corresponding locations associated with the receiver. The observations include power levels of the corresponding signal, and the signals propagate from the one or more transmitters through an environment to the receiver. The first method includes receiving geometry data that includes two-dimensional or three-dimensional data describing objects in the environment. The environment includes the locations associated with the received signals. The first method includes determining expected observations of the signals, corresponding to the recorded observations and locations. In the first method, determining the expected observations of the signals includes determining a bias describing gain or attenuation of a transmitter-receiver pair associated with the recorded observations. In the first method, determining the bias includes (i) calculating, for each of a plurality of sets of values for characteristics of objects in the environment, expected observations corresponding to the recorded observations and locations, (ii) calculating a difference, for each set of values, between the expected observations and the corresponding recorded observations, (iii) determining the set of values with best fit to the recorded observations accounting for the corresponding difference, and (iv) determining the bias based on the set of values with the best fit. In the first method, determining the expected observations of the signals includes determining expected observations of the signals based on the determined bias and the geometry data. The first method includes comparing the expected observations with the recorded observations; and estimating values of characteristics of the objects in the environment based on the comparing. In the first method, the estimated values of the characteristics of the objects include data describing a height of at least one of the objects in the environment.

A second method is described and claimed. The second method includes the first method. In the second method, determining the expected observations based on the determined bias includes determining the characteristics associated with the expected observations; identifying the characteristics associated with similar sets of expected observations; and determining the expected observations based on the determination of the characteristics associated with the expected observations and the identification of the characteristics associated with similar sets of expected observations.

A third method is described and claimed. The third method includes the first method or the second method. The third method includes estimating values of a vertical refractivity profile of the environment.

A fourth method is described and claimed. The fourth method includes the first, second, or third method. In the fourth method, determining the expected observations based on the determined bias includes determining sensitivities of expected observations with respect to the characteristics; and determining the characteristics with less influence on the expected observations, and determining the expected observations based on the determination of the characteristics with less influence.

A fifth method is described and claimed. The fifth method includes the first, second, third, or fourth method. In the fifth method, determining the bias includes determining the bias based on the N sets of values with the best fit; or redetermining the bias after a period of time or based on input from a sensor including one or more of: a proximity sensor, an accelerometer, and an orientation sensor.

A sixth method is described and claimed. The sixth method may include the first, second, third, fourth, or fifth method. In the sixth method, the geometry data describing objects includes building footprint, and characteristics of the objects includes building height and building material; or geometry data describing objects includes foliage area, and wherein the characteristics of the objects includes foliage height and foliage type.

A seventh method is described and claimed. The seventh method includes the first, second, third, fourth, fifth, or sixth method. In the seventh method, estimating the characteristics of the objects includes grouping characteristics of objects into a first cluster and a second cluster, estimating the characteristics in the first cluster, and estimating characteristics in the second cluster based on the characteristics estimated in the first cluster.

An eighth method is described and claimed. The eighth method includes the first, second, third, fourth, fifth, sixth, or seventh method. The eighth method comprises calculating fit metrics or ambiguity metrics to characterize ambiguity of a determination.

A first device is described and claimed. The first device includes a receiver to receive signals from one or more transmitters. The first device includes a memory to record observations associated with the corresponding received signals and record locations associated with the corresponding receiver, wherein the observations include power levels of corresponding signal and the signals include electromagnetic waves propagating through space; store geometry data describing objects in an environment in two or three dimensions, wherein the environment includes the locations associated with the received signals. The first device includes a processor to determine a bias describing gain or attenuation of a transmitter-receiver pair associated with the recorded observations. In the first device, to determine the bias the processor is configured to: (i) calculate, for each of a plurality of sets of values for characteristics of objects in the environment, expected observations corresponding to the recorded observations and locations, (ii) calculate a difference, for each set of values, between the expected observations and the corresponding recorded observations, (iii) determine the set of values with best fit to the recorded observations accounting for the corresponding difference, and (iv) determine the bias based on the set of values with the best fit; determine expected observations of the signals, based on the determined bias and the geometry data, corresponding to the recorded observations and locations; the expected observations with the recorded observations; and estimate characteristics of the objects in the environment based on the comparison, wherein the characteristics of the objects include additional geometry data describing a height of at least one of the objects (in the environment.

A second device is disclosed and claimed. The second device includes the first device. In the second device, the processor is further configured to: determine the characteristics associated with the expected observations; identify the characteristics associated with similar sets of expected observations; and determine the expected observations based on determination of the characteristics associated with the expected observations and the identification of the characteristics associated with similar sets of expected observations.

A third device is disclosed and claimed. The third device includes the first device or the second device. In the third device, the processor is further configured to estimate values of vertical refractivity of the environment.

A fourth device is described and claimed. The fourth device includes the first, second, or third device. In the forth device, the processor is further configured to determine sensitivities of expected observations with respect to the characteristics; determine the characteristics with less influence on the expected observations; and determine the expected observations based on the determination of the characteristics with less influence.

A fifth device is described and claimed. The fifth device includes the first, second, third, or fourth device. In the fifth device, the processor is further configured to determine the bias based on the N sets of values with the best fit; or redetermine the bias after a period of time or based on input from a sensor including one or more of: a proximity sensor, an accelerometer, and an orientation sensor.

A sixth device is described and claimed. The sixth device includes the first, second, third, fourth, or fifth device. In the sixth device, the geometry data describing objects includes foliage area, and the characteristics of the objects includes foliage height and foliage type, or the geometry data describing objects includes building footprint, and characteristics of the objects includes building height and building material.

A seventh device is described and claimed. The seventh device includes the first, second, third, fourth, fifth, or sixth device. In the sixth device, the processor is further configured to group characteristics of objects into a first cluster and a second cluster, first estimate the characteristics in the first cluster, and estimate characteristics in the second cluster based on the characteristics estimated in the first cluster.

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. 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 allow for the estimation of characteristics (e.g., parameters) to describe objects (e.g., buildings, foliage, atmosphere, etc.) in an environment from signals received by a receiver (e.g., a GNSS device). The parameters may include building height, building material, foliage height, foliage type, atmospheric conditions, etc. These parameters may be useful for correcting navigation errors or for any other purposes (e.g., improving communication). Using the signals received in a receiver (e.g., a GNSS receiver or some other generic, non-specialized radio receiver), the power level of received signals from one or more transmitters (e.g., radio frequency transmitters, such as a satellite or television broadcast transmitter) are compared to expected signals influenced by various characteristics of objects in the environment (e.g., expected signals generated by simulation and not by previous observation and/or information stored in a database). Based on this comparison, the characteristics of the objects may be estimated. Knowledge of the two-dimensional (2D) footprint of nearby buildings and/or foliage may be used to determine the three-dimensional (3D) characteristics of nearby buildings and foliage.

<FIG> depicts an environment <NUM> (e.g., an urban environment with foliage) for implementing algorithms disclosed herein. Environment <NUM> includes buildings <NUM>-<NUM> and <NUM>-<NUM>, foliage region <NUM>-<NUM> and foliage region <NUM>-<NUM>, receiver <NUM>-<NUM> and <NUM>-<NUM>, satellites <NUM>-<NUM> through <NUM>-<NUM>, and transmitters <NUM>-<NUM> and <NUM>-<NUM> (collectively "buildings <NUM>," "foliage regions <NUM>," "receivers <NUM>," "satellites <NUM>," and "transmitters <NUM>").

Satellites <NUM> may form part of a GNSS that permits receiver <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 receiver <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. Receiver <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, receiver <NUM> (e.g., if it includes a GNSS device) can calculate position. The GNSS depicted in <FIG> may allow receiver <NUM> to determine its location (longitude, latitude, and altitude) to within a few meters. In other implementations, the GNSS system depicted in <FIG> may allow receiver <NUM> to determine its location less accurately or more accurately.

Receiver <NUM> (e.g., if it includes a navigation device) may also determine its position using other methods (e.g., other than or in addition to using satellites). Receiver <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. Receiver <NUM> may estimate its location at a given point in time. Given multiple locations over a period of time, receiver <NUM> may estimate a track that it has traveled. Receiver <NUM> may use any technique to determine position and an estimated track.

The signals received by receiver <NUM> from satellites <NUM> may not be used to determine an estimated track, but may be received and recorded (e.g., the power level) for later use. Satellites <NUM> may broadcast satellite TV stations. Receiver <NUM> may determine its location using a navigation system or technique other than GNSS.

Receiver <NUM> may include a mobile phone, a tablet computer, a laptop, a personal digital assistant (PDA), or another portable communication device. Receiver <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 receiver <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> is 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 receiver <NUM> from satellites <NUM> from time to time, depending on the location of receiver <NUM> relative to each satellite <NUM>-x. Buildings <NUM> may also shadow receiver <NUM> from transmitters <NUM> from time to time, depending on the location of receiver <NUM> relative to transmitters <NUM>. As discussed above, when one of buildings <NUM> intersects the line of sight from satellite <NUM>-x to receiver <NUM>, the power level of the signal received by receiver <NUM> from satellite <NUM>-x may be diminished. Likewise, when one of buildings <NUM> intersects the line of sight from antenna <NUM>-x to receiver <NUM>, the power of the signal received by receiver <NUM> may be diminished. Blockage and/or interference by foliage <NUM> may similarly cause changes in received power levels (or other characteristics) of signals from transmitters <NUM> or <NUM>.

<FIG> is a block diagram of an environment <NUM> depicting additional devices other than receiver <NUM> shown in <FIG>. In addition to receiver <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. Transmitter <NUM> may be associated with a gain or attenuation (e.g., internal to transmitter <NUM> not associated with propagation of the transmitted signal). Receiver <NUM> may receive signals from transmitters <NUM> and record the power level of the received signals. Receiver <NUM> may also record the location of receiver <NUM> and information identifying the associated transmitter <NUM>. Receiver <NUM> may also use received signals to estimate the location of receiver <NUM> (e.g., if receiver <NUM> includes a navigation device).

Server <NUM> may provide services to receiver <NUM> and/or process signals recorded by receiver <NUM> for estimating the parameters (e.g., characteristics) of objects in environment <NUM>. Server <NUM> may include information (e.g., that may be downloaded by receiver <NUM>) about the geometry surrounding receiver <NUM>, such as two-dimensional and/or three-dimensional information about buildings or foliage surrounding receiver <NUM>. Server <NUM> may determine or contribute to the determination of location of receiver <NUM>. As another example, in an implementation in which receiver <NUM> is a mobile phone, receiver <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. Receiver <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., receiver <NUM>) to connect to other devices (e.g., server <NUM>) also coupled to network <NUM>.

Network <NUM> may (e.g., in which receiver <NUM> is a mobile phone) communicate wirelessly with receiver <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. Receiver <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, receiver <NUM> may receive signals from transmitters <NUM> without necessarily transmitting signals to transmitters <NUM>.

The configuration of devices in environment <NUM> of <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 receivers 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., mountains, etc.). Environment <NUM> may include additional or fewer buildings <NUM>, additional or fewer areas of foliage <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>. Environment <NUM> may also include environmental conditions (e.g., atmospheric conditions) that may cause radio signal refraction or ducting.

<FIG> is a block diagram of receiver <NUM>. Receiver <NUM> may include GNSS logic <NUM>, radio <NUM>, a clock <NUM>, and a memory <NUM>. Receiver <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 (e.g., NMEA <NUM> sentences). NMEA is a standard protocol for relaying data that can include location information and/or information for deriving location. The NMEA sentences may include the estimated location and/or track of receiver <NUM>. The NMEA sentences may included the estimated location and/or track of receiver <NUM>, signal-to-noise (SNR) information about the signal received from each satellite, and location/positional information (e.g. azimuth and elevation) for each satellite, along with other information.

Radio <NUM> may receive signals (e.g., from transmitters <NUM>) and record the signals. Radio <NUM> records the power level (e.g., signal-to-noise ratio, SNR) of the received signal in memory <NUM>. Radio <NUM> may have an associated gain (e.g., a sensitivity, attenuation, or loss) associated with it (e.g., measured in dB) not associated with the propagation of a received signal. The power of a signal observed by radio <NUM> may differ from the power of the signal that impinges on the antenna of radio <NUM> because of an internal gain or attenuation of the receiver. Clock <NUM> may determine the time and may accurately associate a time of any received signal in memory <NUM>.

<FIG> is a block diagram of receiver server <NUM>. Server <NUM> includes memory <NUM>, geometry data <NUM>, and propagation simulator <NUM>, and radio inversion processor <NUM>. Server <NUM> may include additional, fewer, or a different arrangement of components than shown in <FIG>.

Memory <NUM> may store the information collected by one or more receivers <NUM> and stored in memory <NUM>. Receiver <NUM> may upload the information from memory <NUM> to memory <NUM> during or after collection of the information.

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 effect the signals (e.g., obstruct the line of sight) transmitted from transmitter <NUM> to receiver <NUM>.

Propagation simulator <NUM> may use an electromagnetic wave propagation model or simulation tool to generate expected signals given the 2D footprint of objects (e.g., nearby foliage or buildings) and/or 3D model of objects, considering effects of shadowing, diffraction, refraction, and/or reflection. 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). One propagation model may determine expected observations based on diffraction, another propagation model may determine expected observations based on reflections, and the results may be combined to approximate effects from both diffraction and reflection. A diffraction model may be used, and background reflected power levels, which may be lower in power, may be more coarsely estimated and added. An example of a propagation simulator that can be used to calculate expected observations in the presence of buildings and foliage is the Wireless Insite propagation model provided by the company REMCOM (TM). Another example of a propagation simulator that can be used to calculate expected observations for ducting conditions is the Advanced Propagation Model (APM) developed by the by the Atmospheric Propagation Branch.

Radio inversion processor <NUM> may compare received signals to expected signals (e.g., "search the parameter space") to estimate, calculate, and/or determine the characteristics or parameters of objects in environment <NUM>.

Devices in environment <NUM> of <FIG>, 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 determine characteristics of objects in environment <NUM>. <FIG> is a flowchart of a process <NUM> for determining the characteristics of objects. Signals are received and observations recorded (block <NUM>). The location of receiver <NUM> (e.g., as determined by GNSS logic <NUM> or some other method), the time (e.g., as determined by clock <NUM> or another means), and the identity of transmitter <NUM> may also be recorded. A vehicle may carry receiver <NUM> through environment <NUM> while radio <NUM> receives signals that are transmitted from one or more transmitters <NUM> (e.g., a TV broadcast tower, a cell tower, a satellite, etc.) Recording the observations (e.g., signals) may include recording the power level or other features (e.g., SNR, frequency, polarization, etc.) of the received signal, an indication of transmitter <NUM> that transmitted the signal, and the time into memory <NUM>. In addition, the location (e.g., determined by GNSS logic <NUM> or some other method) of receiver <NUM> may be recorded in memory <NUM> and associated with the observation. The time the signals (e.g., determined by clock <NUM> or other means) are received and observed may also be recorded in memory <NUM> and associated with the corresponding power levels. Recorded observations may also be referred to as measurements or measured observations.

Receiver <NUM> may receive signals and record observations periodically (e.g., based on time such as every fraction of a second, every second, every few seconds, every minute, every few minutes, etc.) or aperiodically (e.g., not evenly spaced in time). Receiver <NUM> may receive signals and record observations at particular distance intervals (e.g., every few feet, every meter, every kilometer, etc.) or aperiodic distance intervals (e.g., distances not evenly spaced). Receiver <NUM> may receive signals and record observations when in a particular location. Multiple different receivers <NUM> may receive signals and record observations. Receivers <NUM> may be in different locations and the corresponding locations may then be recorded in memory <NUM> and associated with the recorded observations.

Expected observations are be determined (block <NUM>). For each signal that is received and observation(s) recorded, one or more expected observations may be determined. One or more expected observations may be determined for fewer than all the recorded signals. Expected observations may be determined based on (<NUM>) the location of the receiver <NUM> when the signal was received and observation(s) recorded; (<NUM>) the location of transmitter <NUM> that transmitted the corresponding received signal; and/or (<NUM>) possible combinations of characteristics that describe objects (e.g., buildings, foliage regions, and/or atmosphere) that may affect the signal as it propagates from transmitter <NUM> to receiver <NUM>. Expected observations may include the expected received power (e.g., SNR), the expected frequency, the expected polarization, the expected echo profile, etc..

The recorded observations are compared to the expected observations and the most likely characteristics of the objects in environment <NUM> may be determined (block <NUM>). The recorded power level of the received signals may be compared to the expected power level of the received signals. Based on the comparison, the most likely characteristics of objects in environment <NUM> (e.g., building height and material, foliage height and type) may be determined.

<FIG> is a flowchart of a process <NUM> for determining expected observations (e.g., block <NUM> in <FIG>). Propagation simulator <NUM> determines the expected observations. An expected observation may depend on the following information: the location of receiver <NUM>, the location of corresponding transmitter <NUM>, the frequency of the radio signal, the gains and losses of the transmitter <NUM> and/or receiver <NUM>, and/or the characteristics (e.g., parameters) of the objects in environment <NUM>. The characteristics of objects in environment <NUM>, however, may not be known (or may be only partially known). Therefore, simulator <NUM> may generate more than one (e.g., many) possible expected observations for each measured and recorded observation. Each possible expected observation may be influenced by a different set of characteristics of the objects in environment <NUM>. For a given expected observation to determine, the environmental characteristics (e.g., parameters) that are possibly associated with expected observations may be determined (block <NUM>). Removing characteristics of objects in environment <NUM> that are not associated with an expected observation may reduce the computation power and time for determining the characteristics.

<FIG> is a flowchart of a process <NUM> for determining the possible environmental characteristics associated with expected observation(s) (e.g., block <NUM> in <FIG>). Process <NUM> begins with a selection (e.g., determination) of the objects (e.g., buildings and/or foliage regions) between (e.g., directly between) the particular transmitter <NUM> and receiver <NUM> (block <NUM>). The objects (e.g., the characteristics of the objects) directly between the transmitter and receiver may be considered to have a possible influence on the expected observation between the two. Selected objects may be removed from consideration (e.g., deselected) if a propagation simulation indicates that the object does not have a significant influence on the expected observation.

Process <NUM> may continue with a selection (e.g., determination) of objects within a certain capture distance of the corresponding transmitter <NUM> and receiver <NUM> (block <NUM>). The capture distance may depend on the environment, but may range from a few meters (e.g., <NUM>), a kilometer, a few kilometers (e.g., <NUM>), etc. The capture distance for transmitter <NUM> and receiver <NUM> may be different from each other. Further, because the capture distance may depend on the environment, the capture distance may change with location (e.g., as the receiver moves).

The propagation of the signal from transmitter <NUM> to receiver <NUM> may be simulated (block <NUM>) based on varying characteristics of the selected objects (e.g. the different parameters of the selected objects). A 2D or 3D ray trace algorithm may be used to determine which objects cause reflections for a given expected observation. In another version, height parameters or transmission attenuation parameters may be varied for the selected objects to consider varying propagation paths through the objects for an expected observation. One or more objects may be considered 'transparent' and allow the signal to pass through or over them after each reflection in the simulation of the expected observation for selecting varying sets of object characteristics in the simulation. Possible characteristics of expected observations that result from signal interactions with objects (reflections from, transmission through, transmissions over) may be identified as the object characteristics are varied.

As a result of selecting objects (blocks <NUM> and <NUM>) and simulating propagation of signals (block <NUM>), a list of possible characteristics (e.g., associated with each expected observation) may be determined (block <NUM>). When a simulated reflection from an object occurs (e.g., block <NUM>), a material type characteristic (parameter) for that object may be associated with the expected observation. As another example, when a simulated reflection from an object occurs (e.g., block <NUM>), a height characteristic (parameter) for that object may be associated with the expected observation. As yet another example, when a signal is simulated to pass through or over an object (e.g., block <NUM>), a height characteristic or attenuation characteristic (parameter) for that object may be associated with the expected observation. As yet another example, when an object is determined to exist between transmitter <NUM> and receiver <NUM> (e.g., the object blocks the path of propagation for the expected observation in block <NUM>), a height characteristic (parameter) for that object may be associated with the expected observation. The expected observation and the associated characteristics may be arranged and stored in a matrix, with the expected observation in a column and the characteristics in a row. If the characteristic has a possible influence on the expected observation, then the intersecting cell may be so marked (e.g., with a '<NUM>'). If the characteristic has not been found to have a significant enough influence on the expected observation, then the intersecting cell may also be so marked (e.g., with a '<NUM>'). Removing characteristics of objects in environment <NUM> that are not associated with an expected observation may reduce the computation power and time for determining the characteristics.

Returning to <FIG>, object characteristics that are associated with similar or the same set of expected observations are identified (block <NUM>) and grouped or clustered. Object characteristics may be grouped based on the Euclidean distance between the rows in the matrix described above. Low distances indicate a higher level of similarity and identify object characteristics that may be grouped into the same cluster. A cluster may be limited to a specific number of object characteristics. A cluster may be limited to five or six objects. Grouping of object characteristics may continue until all object characteristics are included in a cluster.

The sensitivity of expected observation(s) to characteristic(s) may be determined (block <NUM>). <FIG> is a flowchart of a process for determining the sensitivity of expected observations to characteristics (e.g., block <NUM> in <FIG>). Process <NUM> may begin with the setting of the characteristics for a given expected observation (e. g, as defined in the matrix) to an average value (block <NUM>). The average value may be stored in a library and may change according to general location or class (e.g., type) of general characteristics of the area (e.g., urban versus rural, New York versus Washington, DC, etc.). The expected observation may be calculated while varying one of the characteristics (block <NUM>). The expected observation may be generated by propagation simulator <NUM>.

If the expected observation changes sufficiently (e.g., more than a threshold) (block <NUM>: YES), then the characteristic may be considered appropriate to keep in the matrix (block <NUM>). Characteristics that have less influence on an expected observation (e.g., the change is less than a threshold) (block <NUM>: NO) may be removed (block <NUM>) as part of the process for determining characteristics with less influence on expected observations (block <NUM>). Further, any expected observation that is no longer associated with any characteristics of the cluster may be removed from the cluster. Process <NUM> may return to block <NUM> and expected observations may be regrouped based on similar characteristics. Again, removing characteristics of objects in environment <NUM> that do not sufficiently influence expected observations may reduce the computation power and time for determining the characteristics. Characteristics of objects that have less influence on an expected observation (block <NUM>: NO) may be left in the cluster (e.g., so that no cluster modifications are made) but disregarded in future calculations. These characteristics may not be estimated by radio inversion processor <NUM>. Rather, a default or average value may be used for the characteristics when performing calculations in propagation simulator <NUM> to estimate other object characteristics.

Biases for a transmitter-receiver pairs are determined or calculated (block <NUM>). The bias may include the gain and/or attenuation of a transmitter-receiver pair (e.g., the attenuation and/or gain internal to transmitter <NUM> and receiver <NUM> not associated with propagation of the signal between the two). <FIG> is a flowchart of a process <NUM> (e.g., block <NUM>) for determining the bias of a transmitter-receiver pair. Process <NUM> begins with the selection of values for characteristics for simulation (block <NUM>). For a given set of values, expected observations are calculated (block <NUM>). Propagation simulator <NUM> may simulate the propagation of a signal for every recorded observation for every transmitter-receiver pair with the set of values (e.g., for a given cluster or group). The bias for the given set of values of characteristics are determined or calculated (block <NUM>). The bias may be calculated by determining the mean difference between the expected observations and the recorded observations for the transmitter-receiver pair for the set of values. It is not known whether the selected set of values are the correct values for the characteristics, however. Thus, a fit is calculated or determined between the expected observations for the set of values, assuming the determined bias, and the recorded observations (block <NUM>). The fit metric provides an indication of whether the bias calculated for the set is an actual estimation. The bias and corresponding fit metric may be recorded and stored. The bias from the set of characteristics with the best fit can be stored (e.g., in memory <NUM>), or the biases from the best N set of fit metrics from N sets of characteristics can be combined and stored. The characteristics can be combined in several ways, including averaging, taking the median bias for several different sets of characteristics, or in other ways.

The determination of fit (e.g., the "fit metric") (block <NUM>) is calculated to determine how well one set of expected observations match the recorded observations (e.g., the measurements) for one set of characteristics. The calculated bias may be applied to the expected observations (e.g., added or subtracted) so that the power level of the expected observations matches those of the measurements (e.g., the average of the expected observations matches the expected. The calculated bias may be applied (e.g. added or subtracted) to the measurements. Then a calculation may be used to determine how well the expected observations match the recorded measurements across the particular set of characteristics (e.g., a given combination of building height and materials and/or foliage height and materials). The calculation may include a root mean squared error or the mean squared error between the expected observations (e.g., offset by the bias) and the measurements. The calculation may include the mean absolute error between the expected observations (e.g., offset by the bias) and the measurements. The calculation may include the median of the difference between the expected observations (e.g., offset by the bias) and measurements. The calculation may include the maximum or minimum of the difference between the expected observations (e.g., offset by the bias) and measurements. The calculation may include several of these metrics combined together or used in a coordinated manner to define a fit metric.

If the sets of values for characteristics (e.g., "characteristic space") have not been searched to the desired extent (block <NUM>: NO), then a new set of values for characteristics are selected for simulation (block <NUM>). When selecting values for characteristics, the values may be offset by a delta value in a positive and/or negative direction (e.g. by adding height and/or subtracting height to a building height characteristic, or by considering a more reflective and/or less reflective material surface). The delta value may be different for different types of characteristics. Further the delta value may be different depending on the number of times the characteristic space has been searched. The process may be repeated (e.g., loop <NUM>) until the characteristic space has been searched simulated (block <NUM>:NO).

The bias for the set of characteristic values with the best fit is determined (block <NUM>). In this case, the set of values with the best fit may be considered the closest to the actual characteristics of objects in the environment. Therefore, the bias of the associated with the set of characteristic values with the best fit may be considered the closest to the actual bias - at least with respect to the collection of sets of values from the first pass of loop <NUM>.

Loop <NUM> has the effect of "searching" through "characteristic space," e.g., searching through the different possibilities of characteristics of objects in environment <NUM>. In other words, given the selection of characteristics of objects, expected signals can be simulated by propagation simulator <NUM> across the possible values of those characteristics (each set of characteristics being simulated at a time). Suppose that two characteristics are selected for environment <NUM> for one expected signal: the height of building <NUM>-<NUM> and the building material for building <NUM>-<NUM>. An expected observation may be calculated for the possible building heights in combination with the possible building materials: e.g., an expected observation for a one-story building of concrete; an expected observation for a two-story building of concrete; an expected observation for a three-story building of concrete; an expected observation for a four-story building of concrete; an expected observation for a one-story building of glass and steel; an expected observation for a two-story building of glass and steel; etc. These different expected observations would correspond to one of the recorded observations (e.g., measured observations). The expected observations may be determined that correspond to each recorded observation across the characteristic space.

The first set of values for characteristics may include or be based on average values (e.g., stored in a library) of objects in a class of environment (e.g., urban, suburban, rural, a particular city or region, etc.). The first pass through characteristic space (loop <NUM>) may be based on a selection of a large delta value in any one direction or both directions from the initial value (e.g. positive building height offset and negative building height offset, or positive change in building material reflectivity and negative change in building material reflectivity). The determination of fit (block <NUM>) is calculated for both directions (both sets of characteristics) and the better fit may be considered more accurate and may be retained. The set of characteristics may be considered less accurate and not used for further calculations. To refine the determination of the bias, smaller delta value(s) may be selected and used (block <NUM>) to repeat a search through the relevant characteristic space. The characteristic space is reduced to the space around the characteristic values that resulted from the best fit (e.g., block <NUM>). After each search through characteristic space (loop <NUM>), smaller and smaller delta values may be used (loop <NUM>) to continually refine the calculation of the bias. Loop <NUM> may be repeated four times. Loop <NUM> may be repeated until the values converge onto a solution. As a result, the best bias may be determined (block <NUM>). Process <NUM> may be repeated for each cluster of characteristics.

The delta value for each direction (e.g., positive and negative) may be of different magnitude. A delta value may be considered in only one direction and the resulting fit metric compared to a baseline fit metric (e.g., no variation in characteristics from the initial value). Other search methods can also be used.

Before the fit is determined or calculated (block <NUM>), filters may be applied to the recorded observations, to the expected observations, or to both. The filtering process may be used to reduce the effect of errors in the measurements or expected observations. The filtering process may be used to reduce the effect of errors (e.g., noise) in space and/or time (e.g., physical scales or temporal scales) that are not accurately represented in the measurements or expected observations. If there is a very short term variation (e.g., noise that is not part of the bias) in the receiver gain, this variation can be filtered so that the resulting difference between the expected and measured observations better represent the bias and provides for a better bias calculation. For this optional step, coefficients can be applied that produce a filtering effect either in the time or distance dimension along a set of measurements or expected observations. The filtered measurements and/or expected observations are used to calculate the fit metric (block <NUM>).

The bias for a receiver-transmitter pair may change with time. A user may hold the phone in a way that changes the resonant frequencies of the antenna, which may change the gain of the antenna of the receiver. As another example, the user may put the phone on a table or in a pocket, which may also change the characteristics of the antenna and the corresponding gain of the antenna. The bias calculation conducted in process <NUM> may be conducted for a given transmitter-receiver pair for one or more different time frames. The bias may be assumed to be valid for short intervals (e.g. a minute) or long intervals (e.g. an hour). Measurements are added to the process <NUM> that may have been captured over a restricted time interval. Multiple estimates of link biases for that transmitter-receiver pair may be estimated for each time interval. These link biases may be combined via a temporal filter (e.g., a finite-impulse response (FIR) filter, or an infinite-impulse response (IIR) filter) to provide a slower time-varying estimate of link bias. The specific characteristics of the filter may be changed to provide either a slower varying or more rapidly varying estimate of link bias, depending on the nature of the receiver and link being used. The time interval over which data is captured for each link bias estimate may be changed to support a slow time-varying estimate of link bias, or a more rapidly time-varying estimate of link bias.

The time frame associated with the recorded observations and/or the expected observations may be based on or determined by activities of the device the includes receiver <NUM>. If receiver <NUM> is in a mobile phone, a proximity sensor may determine when the phone is pressed against the body of the user; an accelerometer may determine when the phone is being carried; an orientation sensor may determine the orientation of the phone. The operating system may determine whether the user is on a call, using a particular application, touching the screen, touching the volume rocker, etc. In this case, when the mobile phone transitions from one activity to another that may affect the gain of receiver <NUM> (e.g., the resonant frequency of an antenna), then a new time frame may be initiated. Further, activities of the mobile phone may be used to determine the characteristics of the filter. That is, activities that introduce rapid and short fluctuations in the gain of receiver <NUM> (e.g., holding, walking, etc.) may result in a stronger filter response. Activities that do not introduce rapid and short fluctuations in the gain of receiver <NUM> (e.g., not in motion on a table) then the filter response may not be as strong. The activities of the mobile phone may inform the initial values of the characteristic space (e.g., the initial pass of loop <NUM>), the delta value or the change in the delta value (e.g., block <NUM>).

Process <NUM> may be repeated for each cluster (e.g., decided in block <NUM>). After each cluster completes a certain number of passes (e.g.. four), or the fit metric achieves a certain goal in error, process <NUM> may conclude. The parameters associated with the multiple passes (loop <NUM>) (e.g., the delta value for each type of characteristic for each pass, the bounds for each type of characteristic, the initial value for each type of characteristic in the first pass) can be stored and associated with a 'class' in a library. That is, these parameters can be associated with specific types of environments that may vary from one another in general characteristics (e.g., rural, suburban, urban, major metropolitan, and/or specific areas such as a particular city). For environment <NUM>, process <NUM> may be run for multiple classes (e.g., urban, suburban, etc.) even though the type of environment is known (e.g., an urban environment). Even though receiver <NUM> is known to have recorded measurements in an urban environment, process <NUM> may assume a suburban environment in one iteration and then assume an urban environment in another iteration. The results (e.g., bias and/or fit metrics) may be stored for each class. These results can be retained to be compared at the end to determine the best class. Thus, if receiver <NUM> is known to be in an urban environment, but the best class turns out to be a suburban class, then the results may be considered to be suspect. With each pass through loop <NUM>, the delta value may decrease. The delta value may decrease exponentially toward zero (e.g., the previous delta value may be multiplied by a value less than one raised to the power of the number of passes through loop <NUM>).

Returning to <FIG>, the expected observations are determined across the selected characteristics given the determined bias (block <NUM>) (e.g., completing block <NUM>). Returning to <FIG>, the expected observations are compared to recorded measurements to determine the most likely characteristics of the objects in environment (block <NUM>). <FIG> is a flowchart of a process <NUM> (e.g., block <NUM>) for determining the characteristics of objects in environment <NUM>. Process <NUM> may begin with the selection of values for characteristics for simulation (block <NUM>). For a given set of values, expected observations may be calculated (block <NUM>). Propagation simulator <NUM> may simulate the propagation of a signal for every recorded observation for every recorded observation with the set of values (e.g., for a given cluster or group). The bias that was calculated in process <NUM> may be used to offset the expected signal. It is not known whether the selected set of values are the correct values for the characteristics, however. Thus, a fit is calculated or determined between the expected observations for the set of values and the recorded observations (block <NUM>). The fit metric provides an indication of whether the bias calculated for the set is an actual estimation. The fit metric may be recorded and stored along with the set of values of characteristics.

If all of the characteristic space has not been searched (block <NUM>: NO), then a new set of values for characteristics may be selected for simulation (block <NUM>). When selecting values for characteristics, the values may be offset by a delta value from the previous simulation (block <NUM>). The delta value may be different for different types of characteristics. Further the delta value may be different depending on the number of times the characteristic space has been searched. The process may be repeated (e.g. loop <NUM>) until the characteristic space has been searched simulated (block <NUM>:NO).

The set of characteristic values with the best fit may be determined (block <NUM>). In this case, the set of values with the best fit may be considered the closest to the actual characteristics of objects in the environment. Therefore, the bias of the associated with the set of characteristic values with the best fit may be considered the closest to the actual bias - at least with respect to the collection of sets of values from the first pass of loop <NUM>.

The first pass through characteristic space (loop <NUM>) may be based on a large selection of a delta value. To refine the determination of the bias, a smaller delta value(s) may be used to repeat a search through the characteristic space (block <NUM>). The characteristic space may be reduced to the space around the characteristic values that resulted from the best fit (e.g., block <NUM>). After each search through characteristic space (loop <NUM>), smaller and smaller delta values may be used (loop <NUM>) to continually refine the calculation of the bias. Loop <NUM> may be repeated four times. Loop <NUM> may be repeated until the values converge onto a solution. As a result, the best values for the characteristics are determined (block <NUM>).

Process <NUM> may be repeated for each cluster of characteristics.

Before the fit is determined or calculated (block <NUM>), filters may be applied to the recorded observations, to the expected observations, or to both. The filtering process may be used to reduce the effect of errors in the measurements or expected observations. The filtering process may be used to reduce the effect of errors (e.g., noise) either in space and/or time (e.g., physical scales or temporal scales) that are not accurately represented in the measurements or expected observations. If there is a very short term variation (e.g., noise that is not part of the bias) in the receiver gain, this variation can be filtered so that the resulting difference between the expected and measured observations better represent the bias and provides for a better bias calculation. For this optional step, coefficients can be applied that produce a filtering effect in the time and/or distance dimension along a set of measurements or expected observations. The filtered measurements and/or expected observations are used to calculate the fit metric (block <NUM>).

Process <NUM> (to estimate link biases) and process <NUM> (to estimate best characteristics) can be repeated in stages. All characteristics of objects in an environment (e.g., environment <NUM>) may be considered together in one cluster (e.g., a single cluster), process <NUM> may calculate link biases, and the characteristics (e.g., all characteristics) for the environment may be combined in the process <NUM>.

As described in process <NUM> and block <NUM>, characteristics of objects in environment <NUM> may be grouped together into smaller clusters so that multiple clusters of characteristics form the entirety of environment <NUM>. In this case, process of <NUM> and process <NUM> can be executed separately for each cluster. This can be done considering only the objects in the cluster (e.g., ignoring objects outside the cluster) for calculations in the propagation simulator <NUM> and the radio inversion processor <NUM>. Alternatively, it can be done by varying the characteristics (searching the characteristic space) for only the objects in the cluster, but considering some other estimate of characteristics (e.g., results from previous estimates) for characteristics in other clusters while completing the computations associated with the propagation simulator <NUM>.

The multiple passes of process <NUM> and process <NUM> may be executed one time (e.g., process <NUM> and process <NUM> may be executed one time). The process <NUM> and process <NUM> can be repeated in their entirety multiple times, in multiple 'stages,' while generating results (e.g., best fit bias and best characteristics) with each stage. These multiple stages (multiple executions of process <NUM> and process <NUM>) can use the same set of transmitters <NUM> (e.g., satellites <NUM> and transmitters <NUM>). The selection of transmitters <NUM> and measurements can change or differ from one stage to the next stage. The fidelity of propagation simulator <NUM> can be constant throughout the multiple stages and across each transmitter. The fidelity of propagation simulator <NUM> can vary by transmitter or from one stage to the next stage. The estimated position of the receivers for each measurement and expected observation can be the same for all stages. Improved estimates of position for receivers for each measurement and expected observation can be used in subsequent stages. The method and apparatus described in the <CIT> titled "Navigation Track Correction," may be used to improve the location estimate from one stage to the next stage. Other methods to improve the accuracy of receiver positions from one stage to the next can also be used.

When characteristics of objects in environment <NUM> are grouped into clusters using process <NUM> (block <NUM>), the estimates of characteristics for objects from each cluster that result from each stage (each execution of process <NUM> and/or process <NUM>) can be shared among clusters at the end of each stage. These characteristics may include estimates of building heights, building materials, foliage heights, and/or foliage material types, etc..

Process <NUM> (e.g., which may included processes <NUM>, <NUM>, <NUM>, and <NUM>), can be used to estimate characteristics for a large number of objects, such as buildings <NUM> and foliage regions <NUM> (e.g., building height, building materials, foliage, and foliage material). The characteristics of the objects in an environment may be estimated with fewer than all the steps described in processes <NUM> through <NUM>.

Process of <NUM> (e.g., which may include processes <NUM> through <NUM>) can be used to estimate other characteristics of environment <NUM>, such as ducting conditions. Ducting conditions may include variations (often vertical) of the speed of electromagnetic wave propagation that may results in "bounces" and/or "shadow zones" of signal strength at various distances from the transmitter. In other words, the atmosphere itself in environment <NUM> may be considered an object as described above. Ducting conditions (e.g. the characteristics of the atmosphere treated as an object) may be identified by a vertical refractivity profile.

A refractivity profile may describe the speed of electromagnetic wave propagation as a function of altitude. This refractivity profile can be described using a small number of characteristics (e.g., eight). Two exemplary sets of characteristics of the refractivity profile are shown in <FIG>. The vertical refractivity profile (<FIG>) may be defined using five characteristics. The vertical refractivity profile (<FIG>) is defined using six characteristics. Two additional characteristics can be added to either approach. The first can be a smoothing characteristic (using a filter, such as an FIR filter applied to the vertical profile) to correlate or to smooth the refractivity profile values over a certain altitude. The second characteristic that can be added is a randomization or fluctuation characteristic that ma add a variance to the smooth, piece-wise linear profiles of <FIG> and/or <NUM>. The parameters chosen to describe the vertical refractivity profile can be estimated using the processes described previously (instead of estimating building characteristics). Characteristics may include: base height (Zb), inversion layer thickness (Zt), mixed layer slope in M-units per distance (C1), evaporative duct height (delta), M-deficit (Md) in M units, and slope above the inversion layer (C2) in M-units per unit distance.

In addition to a fit metric (block <NUM> and/or block <NUM>), an ambiguity metric can be calculated for various sets of characteristics (e.g., "solutions") used to describe the objects in environment <NUM>. Ambiguity metrics can be calculated at various stages. Ambiguity metrics of a solution (e.g., a set of characteristics) can be calculated at each stage (each complete execution of process <NUM> and process <NUM>), and ambiguity metrics of a solution can be calculated for each class of solution (each set of parameters used to describe the progression of parameter offsets in the execution of the multiple passes of process <NUM> and process <NUM>). The ambiguity metric can be used to determine whether a clear solution (e.g., less ambiguous or unambiguous solution) is identified at each stage, and whether a clear solution (e.g., less ambiguous or unambiguous solution) is identified among various classes.

Various ambiguity metrics can be used to identify whether a clear solution is identified among classes and at each stage. The ambiguity metric may compare the overlap in fit metric from the best M solutions (where M is an integer) between stages, between solutions in different classes, or among other groupings of solutions. As an example, an ambiguity metric may be obtained by comparing the overlap of the distribution of a set of fit metrics from two different groups of solutions (either at subsequent stages, among different classes, or among other groups of solutions). The ambiguity metric may be obtained in three steps to determine an "overlap metric. " The first step may calculate the percentage of fit metric values in the first group that lie within the full range of fit metric values in a second group. The second step may calculate the percentage of fit metric values in the second group that lie within the full range of fit metric values in the first group. The third step may calculate the average of the results of the previous two steps.

The ambiguity metric can be calculated for a "separability metric" as the difference between the mean, median, or mode of the fit metric distributions of groups one and two, normalized by the standard deviation or variance of either group of fit metric groups, or an average or other combination of the standard deviation or variance of the two fit metric groups. Other measurements of distribution separability can be used in the calculation of an ambiguity metric, with the basic goal of determining how much overlap, or alternatively, how much separation exists between two sets of fit metrics from two different groups of solutions.

The ambiguity metrics described can be used to determine whether a solution is an unambiguous solution, compared to another group of solutions. The 'overlap metric' described previously can be compared to a threshold to determine if overlap is reduced enough to consider a solution unambiguous. The 'separability metric' can be compared to a threshold to determine if the separability between two solutions is adequate to consider the solution unambiguous. Both the 'overlap metric' and the 'separability metric' can both be compared to thresholds, or can be applied to other logic, to determine whether a given solution is unambiguous. If the result is not unambiguous, notification can be given that the best solution provided by block <NUM> of process <NUM> may not unambiguously define a 'good' solution for an estimate of the characteristics of the objects in environment <NUM>.

The fit metrics described previously can be used to determine whether a best solution is well matched to the solution space considered for the objects in environment <NUM>. The best fit metric provided in process <NUM> (block <NUM>) can be compared to thresholds and to other solution fit metrics to determine whether an adequately low fit metric is obtained. If the best fit metric is not small enough (a small value indicating a good fit between the measurements and the expected observations for the estimates of characteristics for objects in <NUM>), then notice can be given that a 'good fit' does not exist within the parameter space searched.

In processes <NUM> and <NUM>, expected observations for a set of values of characteristics of objects in environment <NUM> are calculated and compared to measurements, and a search of the characteristic space results in a best estimate of the characteristics for those objects. In some cases, the objects with characteristics being estimated are a small subset of the total number of objects in environment <NUM>. In this case, some objects in environment <NUM> may not have their characteristics estimated. The characteristics of objects that are not estimated may already be known. The characteristics of objects that are not estimated may not known but may be assumed. Characteristics of objects immediately outside a cluster being processed may be assumed or known.

Assumptions about the characteristics of objects not being evaluated may include the general statistics of the characteristics not being estimated or characteristics of objects that are known. The average building height for buildings not being characterized may be known or assumed based on the class of those buildings. As another example, the average reflectivity of building surfaces may be known or assumed based on the class of those buildings. As yet another example, the standard deviation relative to the mean of the building heights or building reflectivities may be known or assumed based on the class of those buildings. In these cases, the influence of these non-estimated objects on the expected observations may be calculated using a statistical propagation model to augment a deterministic model in the propagation simulator <NUM>. A statistical propagation model, such as the ITU-R P. <NUM> propagation model identified by the International Telecommunications Union can be used to account for effects of objects and their assumed or known statistical properties in areas outside of the area that includes objects whose characteristics are being estimated.

The sequence of steps or blocks defined in process <NUM> and/or process <NUM> may be varied or changed. The point at which the characteristic value delta is changed (e.g., block <NUM> and/or block <NUM>) may be at another point in process <NUM> or process <NUM>. Other variations in the ordering of the steps, or in the omission of certain steps, are allowed in process <NUM> and/or process <NUM>.

When the characteristic value delta is calculated or changed (e.g., block <NUM> of process <NUM> or block <NUM> of process <NUM>), the new value can be used to update one characteristic or multiple characteristics (e.g., in block <NUM> of process <NUM> or block <NUM> of process <NUM>). A delta value can be applied to offset one value of a characteristic of one object in positive and negative directions for the next set of characteristic values and/or calculations. A delta value can be applied to offset more than one value of characteristics of one or more objects in positive and negative directions for the next set of calculations. Different delta values can be defined for different characteristics, with one or multiple values of characteristics changed for the next set of values and/or calculations, in either or both positive or negative directions.

Process <NUM> (block <NUM>) may stop looping (e.g., cessation of loop <NUM>) after a particular number of sets of values of characteristics. Process <NUM> (block <NUM>) may stop looping (e.g., cessation of loop <NUM>) after the characteristic space has been completely searched by some definition of the span of the characteristic space.

Process <NUM> (block <NUM>) may stop looping (cessation of loop <NUM>) after a particular number of loops. Process <NUM> (block <NUM>) may stop looping (e.g., cessation of loop <NUM>) after changes in the fit metrics are reduced to an acceptably low level from pass to pass, or until the fit metric achieves an acceptably low level in absolute terms. Process <NUM> (block <NUM>) may stop looping (cessation of loop <NUM>) after the delta value defined reaches an acceptably small value.

The clustering algorithm used in process <NUM> (block <NUM>) may include a single-linkage hierarchical clustering algorithm. Other clustering algorithms may be used.

In process <NUM>, the selection of which characteristics to include in estimates of characteristics of objects (block <NUM>) may be done by adaptively setting a threshold to the fit metrics that were recorded. A test may be applied to the distribution of the fit metrics in order to identify the lowest 'group' or 'mode' of values in the fit metric distribution. Alternatively, a certain percentage of values in the fit metrics may be identified to select a certain lowest set of values in the fit metric distribution. Other means may be applied to determine a set of the fit metric values in the fit metric distribution. Based on this selection, a threshold may be set in terms of fit metric values. This threshold may be used to identify the sets of characteristics, previously stored, that are associated with fit metric values below the threshold, or between two limits. In this way, a set of characteristic values may be identified for the objects. The values may be combined by taking the mean, the median, the maximum, the minimum, or some other combination of the resulting object characteristics to produce a 'best estimate' of the objects.

Process <NUM> (block <NUM>) may calculate the expected observations using propagation simulator <NUM> (e.g., in server <NUM>). Once the expected observations are calculated for a specific transmitter (e.g., knowing the location), receiver (e.g., knowing the location), characteristic set or objects in environment <NUM>, set of values for the characteristics for objects in environment <NUM>, and/or transmitter-receiver pair bias, the value and/or values may be stored (e.g., in memory <NUM>) for further use, possibly avoiding recalculation. When the same or similar expected observations are to be calculated (e.g., at some point in the future), these expected observations may be retrieved from memory <NUM> to avoid additional processing.

A matrix was described to provide an example of the organization of the relationship or association of expected observations and object characteristics in process <NUM> (e.g., block <NUM>). The data structure can be a matrix with the described organization, can be a different matrix (e.g. the transpose), and/or can be another data structure which provides the ability to conduct the same functions (e.g., similarity comparison and cluster processing) as described above.

A method may include receiving 2D geometry data (e.g., a 2D footprint) of buildings and foliage regions. The method may include receiving signals using one or more radio frequency receivers over one or more positions. The method may include estimating the heights of buildings and foliage, estimating the material types of buildings and foliage, estimating local atmospheric conditions such as vertical profiles of refractivity that may cause ducting.

The method may include receiving 2D geometry data (e.g., a 2D footprint) of buildings, and receiving 2D geometry data (e.g., 2D footprints) of foliage regions. The method may include receiving signals using one or more radio frequency receivers over one or more positions, and recording the signal power level measurements of the received signals. The method may include receiving estimated positions of the receivers and the time of the measurements, receiving or knowing transmitter location, estimating the height of the buildings, estimating the material types for each building, estimating the height of foliage, and/or estimating the material type characteristics for the foliage.

A method may include receiving signals using one or more radio frequency receivers over one or more positions, recording signal power level measurements of the received signals, receiving estimated relative positions of the transmitters and receivers at the time of the measurements, and estimating one or more profiles of the local vertical refractivity from the measurements, where each vertical profile is associated with a relative geographic position.

The methods described herein may include a method of searching to evaluate how well expected observations (e.g., replica vectors) match received signal measurements for various building parameters, foliage parameters, and/or vertical refractivity profiles in an efficient manner. The methods described herein may include identifying which building height and material parameters are associated with each radio measurement, identifying which foliage height and material parameters are associated with each radio measurement, organizing large numbers of building height and material parameters, and foliage height and material parameters, into a number of smaller groups of parameters. The methods described herein may include identifying and removing unnecessary radio frequency signal measurements from the process to reduce errors and accelerate the process. The identification and removal may include the identifying and removing certain building parameters, foliage parameters, and ducting profile parameters that cannot be adequately estimated from the expected observations (e.g., expected observations).

Methods described herein may include estimating a link bias (e.g., a link including a transmitter-receive pair) value (e.g., a constant for a period of time) for each transmitter-receiver link pair. The method may include estimating how well the estimates of building heights and materials, foliage heights and materials, and vertical refractivity profiles match the observed radio measurements. The method may include estimating whether the estimates of building heights and materials, foliage heights and materials, and vertical refractivity profiles are an unambiguous match to the received radio measurements.

Methods described herein may include splitting (e.g., grouping or clustering) the estimation process into multiple groups of building and foliage structures to conduct the process in a partially independent manner before combining results from each group of structures, and/or conducting the estimation process in stages where the fidelity of the overall picture of buildings and foliage improves in each stage and results from each group are shared between stages.

The location or position of the receiver of a navigation unit may be corrected. The method may include estimating one section of building and foliage parameters in a deterministic manner, while estimating surrounding building and foliage parameters in a statistical sense. The method described herein may include receiving 2D geometry data (e.g., footprint and coarse (e.g., inexact) 3D geometry data such as height) for buildings and foliage. Methods described herein may include updating the estimated bias for each link over time. The method may include detecting change in settings or activities of a mobile receiver that may cause a shift in the receiver link bias associated with that receiver and calculating the bias at those times.

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 (<NUM>) signals, in a receiver (<NUM>) from one or more transmitters (<NUM>), and recording (<NUM>) corresponding observations associated with the received signals and recording corresponding locations associated with the receiver (<NUM>),
wherein the observations include power levels of the corresponding signal, and
wherein the signals propagate from the one or more transmitters (<NUM>) through an environment to the receiver (<NUM>);
receiving geometry data (<NUM>) that includes two-dimensional or three-dimensional data describing objects (<NUM>, <NUM>) in the environment (<NUM>), wherein the environment includes the locations associated with the received signals;
determining (<NUM>) expected observations of the signals, corresponding to the recorded observations and locations, wherein determining the expected observations of the signals includes:
(A) determining a bias (<NUM>) describing gain or attenuation of a transmitter-receiver pair associated with the recorded observations, wherein determining the bias includes:
(i) calculating (<NUM>, <NUM>), for each of a plurality of sets of values for characteristics of objects (<NUM>, <NUM>) in the environment (<NUM>), expected observations corresponding to the recorded observations and locations,
(ii) calculating (<NUM>) a difference, for each set of values, between the expected observations and the corresponding recorded observations,
(iii) determining (<NUM>) the set of values with best fit to the recorded observations accounting for the corresponding difference, and
(iv) determining (<NUM>) the bias based on the set of values with the best fit, and
(B) determining expected observations (<NUM>) of the signals based on the determined bias and the geometry data;
comparing (<NUM>, <NUM>) the expected observations with the recorded observations; and
estimating (<NUM>, <NUM>, and <NUM>) values of characteristics of the objects (<NUM>, <NUM>) in the environment based on the comparing, wherein the estimated values of the characteristics of the objects (<NUM>, <NUM>) include data describing a height of at least one of the objects (<NUM>, <NUM>) in the environment (<NUM>).