Methods and systems for determining the location of an electronic device

[0001] Not Applicable.

[0002] The present invention relates to determining the location of an electronic device, and in particular, to methods and systems for determining the location of an electronic device having an unknown location.

[0003] As electronic devices such as computers and cell phones have become more prevalent, there is a growing desire to determine the location for such devices for a variety of applications. One of the most prevalent consumer applications has been in travel. One common approach is to use a Global Positioning System (“GPS”) to determine location. GPS systems incorporate navigation systems which help the user find their desired destinations. Many of the systems provide navigation with visual and audio cues that aid the user in navigating through streets and highways which may be unfamiliar to the user.

[0004] However, GPS systems suffer from a variety of shortcomings. GPS system signals are fairly weak and may not be sufficient to operate in many indoor locations, tunnels, and urban canyons. In large cities such as San Francisco, New York, and Chicago, there are many locations in which GPS signals do not operate or may not provide consistent location data for navigation. For example, if a user takes the subway around the city, the current GPS systems may not be able to determine any locations within the tunnels, and this may lead a user to exit the train at the wrong train station. Also, many destinations in a large metropolitan city may require a vertical coordinate as well as a longitudinal and latitudinal coordinate. For example, a store within a mall may be located on the top level of a building.

[0005] Thus, there is a need for improved systems and methods for determining location. The present invention solves these and other problems by providing methods and systems for determining the location of an electronic device.

[0006] Embodiments of the present invention improve methods and systems for determining the location of an electronic device. In one embodiment, the present invention includes a method of determining a location of an electronic device, the method comprising transmitting one or more signals between a first electronic device at an unknown location and three or more electronic devices at three or more corresponding known locations, wherein the one or more signals each include a plurality of tones having different frequencies, determining at least one first phase difference between at least two tones having a first frequency difference in the one or more signals accumulated during transmission between the first electronic device and a first electronic device of said three or more electronic devices, determining at least one second phase difference between at least two tones having a second frequency difference in the one or more signals accumulated during transmission between the first electronic device and a second electronic device of said three or more electronic devices, determining at least one third phase difference between at least two tones having a third frequency difference in the one or more signals accumulated during transmission between the first electronic device and a third electronic device of said three or more electronic devices, and determining the location of said first electronic device using said first, second, and third phase differences and said first, second, and third frequency differences.

[0007] In one embodiment, the method further comprises determining a fourth phase difference between at least two tones having a fourth frequency difference in the one or more signals accumulated during transmission between the first electronic device and a fourth electronic device of four or more electronic devices, wherein said determining the location further comprises using the fourth phase difference and the fourth frequency difference. Additional electronic devices at known locations may be used to determine the location of the unknown device.

[0008] In one embodiment, the devices at know locations are wireless access points. In one embodiment, the device at the unknown location is a mobile device such as a mobile phone, laptop computer, personal digital assistant, or a handheld computer based system.

[0009] In one embodiment, the first, second, and third frequency differences are the same, but the first, second, and third frequency differences may be different.

[0010] In one embodiment, the one or more signals comprise orthogonal frequency division multiplexed signals.

[0011] In one embodiment, a first signal of the one or more signals comprises first wireless standard and a second signal of the one or more signals comprises a second wireless standard.

[0012] In one embodiment, a first signal of the one or more signals is transmitted from the first electronic device of said three or more electronic devices and received by the first electronic device at the unknown location, a second signal of the one or more signals is transmitted from the second electronic device of said three or more electronic devices and received by the first electronic device at the unknown location, and a third signal of the one or more signals is transmitted from the third electronic device of said three or more electronic devices and received by the first electronic device at the unknown location.

[0013] In one embodiment, a first signal of the one or more signals is transmitted from the first electronic device at the unknown location and received by the first electronic device of said three or more electronic devices, a second signal of the one or more signals is transmitted from the first electronic device at the unknown location and received by the second electronic device of said three or more electronic devices, a third signal of the one or more signals is transmitted from the first electronic device at the unknown location and received by the third electronic device of said three or more electronic devices.

[0014] In one embodiment, the one or more signals is one signal transmitted from the first electronic device at the unknown location and received by each of said three or more electronic devices.

[0015] In one embodiment, at least one of said electronic devices comprises a plurality of antennas, and wherein the method comprises determining a first phase difference between at least two tones received by a first antenna of said plurality of antennas, and determining a second phase difference between at least two tones received by a second antenna of said plurality of antennas.

[0016] In one embodiment, the first electronic device at the unknown location includes a gyrator, wherein the method further comprises determining a first location of said first electronic device, storing said first location, generating movement vector indicating the movement of the first electronic device relative to first location, and adding the movement vector to the first location to determine a second location.

[0017] In one embodiment, the method further comprises estimating the distance between the first electronic device and at least one of said three or more electronic devices using a transmitted power and received power of said one or more signals.

[0018] In one embodiment, the method further comprises encoding the transmitted power in at least one signal.

[0019] In one embodiment, determining the location further comprises selecting a first integer representing the difference in the integer number of wavelengths of two tones transmitted between the first electronic device and said first electronic device of said three or more electronic devices, selecting a second integer representing the difference in the integer number of wavelengths of two tones transmitted between the first electronic device and said second electronic device of said three or more electronic devices, selecting a third integer representing the difference in the integer number of wavelengths of two tones transmitted between the first electronic device and said third electronic device of said three or more electronic devices, and determining a first distance between the first electronic device and said first electronic device of said three or more electronic devices, a second distance between the first electronic device and said second electronic device of said three or more electronic devices, a third distance between the first electronic device and said third electronic device of said three or more electronic devices using said first, second, and third integers.

[0020] In one embodiment, the first, second, and third distances are final distances indicating the location of the first electronic device relative to three of the three or more electronic devices if the first, second, and third distances intersect at a single point.

[0021] In one embodiment, the method further comprises estimating the first distance between the first electronic device and said first electronic device of said three or more electronic devices using a transmitted power and received power of said one or more signals and determining said first integer based on said estimated distance.

[0022] In one embodiment, the method further comprises determining a plurality of received amplitudes for the plurality of tones, processing one or more of the received amplitudes to determine estimated distances for each tone, weighting the estimated distances based on received amplitude values, and determining the location of said first electronic device using said estimated distances.

[0023] In one embodiment, processing comprises normalizing a plurality of received amplitudes. In one embodiment, processing comprises averaging a plurality of received amplitudes and normalizing the received amplitudes to an average amplitude value. In one embodiment, processing comprises determining a highest and a lowest amplitude value of said received amplitudes and normalizing the received amplitudes to said highest and lowest amplitude values.

[0024] In one embodiment, the present invention includes a method of determining a location of an electronic device comprising determining a first distance between a first electronic device having an unknown location and a second electronic device having a known location, determining the first distance comprising generating a plurality of tones having a plurality of frequencies, modulating the tones with a carrier frequency to produce a first signal, transmitting the first signal between the first electronic device and the second electronic device, receiving the first signal, demodulating the first signal to extract the plurality of tones, extracting the phase of at least a portion of the plurality of tones, and determining phase differences between tones at different frequencies, each phase difference having a corresponding frequency difference, determining a second distance between the first electronic device having the unknown location and a third electronic device having a known location, determining the second distance comprising the same method as determining the first distance, determining a third distance between the first electronic device having the unknown location and a fourth electronic device having a known location, determining the third distance comprising the same method as determining the first distance, and calculating the first, second, and third distances based on the phase differences and corresponding frequency differences, and determining the location of said first electronic device based on said first, second, and third distances.

[0025] In one embodiment, the method further comprises extracting an amplitude for each of said plurality of tones, estimating the first, second, and third distances using said extracted amplitudes and a transmitted power value, selecting a first integer representing the difference in the integer number of wavelengths of two tones transmitted between the first electronic device and the second electronic device, a second integer representing the difference in the integer number of wavelengths of two tones transmitted between the first electronic device and the third electronic device, and a third integer representing the difference in the integer number of wavelengths of two tones transmitted between the first electronic device and the third electronic device, wherein the integers are selected based on the estimated first, second, and third distances, and calculating the first, second, and third distances based on the first, second, and third integers.

[0026] In one embodiment, the method further comprises determining a fourth distance between the first electronic device having the unknown location and a fifth electronic device having a known location, determining the fourth distance comprising the same method as determining the first distance, calculating the fourth distances based on the phase differences and corresponding frequency differences; and determining the location of said first electronic device based on said first, second, third, and fourth distances.

[0027] In one embodiment, the present invention includes a system that employs a multi-tone OFDM signal. A signal travels between a known location transmitter (e.g. a wireless access point/base-station) and a receiver (e.g. a wireless mobile device). An OFDM range engine uses the estimated channel frequency response vector to calculate the residual phase differences between frequency tone pairs and also extracts amplitude information for each tone. This process is repeated with other transmitters with known locations. All the calculated residual phase differences and amplitude information are then processed by a location engine to locate the mobile device. A standard OFDM transmitter may be used for the system. The system may further include an OFDM range engine and an OFDM receiver, and possibly a location engine if the receiver is to be used for the location calculations.

[0028] Both the OFDM range engine and the location engine may be software algorithms that can be implemented on a DSP. The location engine may process the residual phase differences and tone amplitude information by searching for a solution to a triangulation problem as described herein. The location engine may be a software algorithm that is running on a independent server. Alternatively, the software may be implemented on the OFDM transmitters or the receiver.

[0029] In some embodiments, smaller tone amplitudes may be given smaller weights in the location calculations or ignored altogether. Amplitude information may also be used to detect multi-paths. For example, access points that provide a direct line of sight will have fewer variations in the amplitudes of their pilot tones and will be preferred in any triangulation calculations in order to reduce the effects of multipath.

[0030] In embodiments using Multiple-Input and Multiple-Output (MIMO) systems, several antennas may be used to gather more data to get more accurate results. For example, a MIMO access point acting as a transmitter can use more than one antenna. Furthermore, these antennas may be used with the highest performance, lowest bit error rates, and better lines of sights.

[0031] Embodiments of the present invention may be implemented where access points or base-stations are the OFDM transmitters and the mobile device is the receiver, or the case where the mobile device is the OFDM transmitter and the access points/base-stations are the receivers, or yet other situations where the OFDM transmitters and receiver roles are shared. The latter may be useful in some systems where transmit and receive frequencies are different, and switching the role of transmitter and receiver therefore provides more data samples and better averaging. Furthermore, some systems such as WLAN can operate at different frequencies. For example, WLAN 802.11a and 802.11g use two different frequencies and using both frequencies provides more data for a more accurate location estimate. Another way to improve the location estimate is to use several wireless standards. For example, if an access point and a mobile device have UWB, WLAN, and cellular connectivity then residual phase and amplitude information may be obtained from all standards and processed to get a more accurate location value.

[0032] After the mobile device's position is calculated it is possible to interface the system with a navigation system that provides path planning and guidance. A mobile device whose position is known or calculated can also be used as an access point to locate the position of other mobile devices.

[0033] The proposed method can be applied to any system that uses multiple pilot tones, such as OFDM, including WLAN, 4G cellular, WiMax and UWB. Embodiments of the present invention may be applied to a variety packet-based methods and standards. Thus, any packet-based method may be modified such that it uses multiple pilot tones in the packet pre-amble or packets that have room.

[0034] If the distance between the transmitter and receiver is smaller than a threshold (e.g., the speed of light divided by the frequency difference of two tones), then the full cycle phase ambiguity issue disappears and the problem simplifies such that it is possible to calculate the actual transmitter-receiver separation distance from one transmitter. The calculated residual phase differences can then be plotted against the tone pair frequency differences and the fitted gradient of this line used to calculate the separation distance. Each tone in an OFDM signal can generate its own curve with a fitted gradient. The gradients can then be combined to provide a better estimate for the separation distance. The combination algorithm can be as simple as averaging or more complex such as Kalman filtering. A single measured phase difference can also be used to calculate the separation distance, albeit with less accuracy. Multiple transmitters and triangulation can then be used to processes the range information and obtain the object's location.

[0035] Embodiments of the present invention are complementary to GPS since it works in indoor locations, tunnels and urban canyon, where GPS signals may be weak.

[0036] The following detailed description and accompanying drawings provide a better understanding of the nature and advantages of the present invention.

[0046] Described herein are techniques for methods and systems for determining the location of a mobile device. In the following description, for purposes of explanation, numerous examples and specific details are set forth in order to provide a thorough understanding of the present invention. It will be evident, however, to one skilled in the art that the present invention as defined by the claims may include some or all of the features in these examples alone or in combination with other features described below, and may further include modifications and equivalents of the features and concepts described herein.

[0047] Embodiments of the present invention may be used to determine a location of an electronic device. Information regarding the distances between electronic devices having known locations and electronic devices having an unknown location may be used to determine the location (i.e., position) of the electronic device at the unknown location. FIG. 1 illustrates system 100 for determining the location of an electronic device according to one embodiment of the present invention. Electronic device 101 may reside in an unknown location, and it may be desirable to determine the location of the device. Embodiments of the present invention may use signals transmitted between electronic device 101 and other electronic devices at known locations (e.g., electronic devices 102-104) to determine the location of device 101. For example, in one embodiment a signal that includes multiple frequency components may be transmitted between electronic device 101 at an unknown location and electronic device 102 located at a known location A. The different frequency components, which differ in frequency by an amount Δf, will result in a measurable phase difference, Δφ, at the receiving device that is related to the distance between the device transmitting the signal and the device receiving the signal. Accordingly, by transmitting and receiving such a signal, the distance between each electronic device with a known location and the electronic device with the unknown location may be determined. For example, the signal that travels between device 101 and device 102 has different frequency components Δf1 and a corresponding measurable phase difference Δφ1. Similarly, the signal that travels between device 101 and device 103 has different frequency components Δf2 and a corresponding measurable phase difference Δφ2. Likewise, the signal that travels between device 101 and device 104 has different frequency components Δf3 and a corresponding measurable phase difference Δφ3. The known location of devices 2, 3 and 4, the measured phase differences, and the frequency components can then be processed to determine distances d1, d2, d3, and the location of device 101. As described below, it is to be understood that device 101 may send out one signal, in which case Δf1=Δf2=Δf3.

[0048] In one embodiment, the electronic device 101 having the unknown location receives signals transmitted from electronic devices 102-104 to determine the unknown location. In other embodiments, the electronic device 101 having the unknown location transmits one or more signals, which are received by electronic devices 102-104 to determine the unknown location. In other embodiments, the electronic device 101 having the unknown location transmits and receives signals, and electronic devices 102-104 may transmit and receive signals. For example, some or all of the devices may both transmit and receive to improve the accuracy of the distance measurement. This provides more data to process and the averaging that result from processing more information improves the accuracy of the distance measurement since the effect of random errors is reduced. In yet another embodiment the transmitter can transmit more than once where each transmission has a different center frequency and the receiver can receive and handle these different transmissions. For example, Wireless LAN 802.11a and 802.11b use two different frequencies and if both the transmitter and receiver support 802.11a and 802.11b then using both provides better averaging. Yet another embodiment is for a multi-radio transmitter to transmit more than once where each transmission uses a different radio that supports a different wireless standard, such as WLAN and UWB. If the receiver supports these different wireless standards more data is gathered and location accuracy is improved through averaging. Alternatively, the distances between one or more devices having known locations (e.g., devices 102 and 103) and the device with the unknown location may be determined by transmitting signals from devices with known locations to the device having the unknown location, and other distances between one or more devices having known locations (e.g., device 104) and the device with the unknown location may be determined by transmitting signals from the device with the unknown location to the devices with known locations.

[0049] The locations of electronic devices 102-104 may be known by installing the devices in fixed locations and storing the location information. The location information is typically longitude, latitude and height (or altitude). It may also be x, y and z co-ordinates relative to some reference point. Alternatively, electronic devices 102-104 may have embedded GPS systems or GPS assist systems that may be used to determine the precise location of these systems using GPS techniques. Three devices with known locations may be used to determine the unknown location of a device in two dimensions (2D), and four devices with known locations may be used to determine the unknown location of a device in three dimensions (3D).

[0050] FIG. 2 illustrates the use of a pair of tones to determine a distance between electronic devices according to one embodiment of the present invention. A transmitted signal includes two frequency components f₁ and f₂, which may differ in frequency by an amount Δf. The different signal frequencies (or tones), f, will have different corresponding wavelengths, λ, that can be determined as follows:
λ=c/f,
where c is the speed of light (i.e., 3×10⁸ m/s). As illustrated in FIG. 2, the transmitted signals will propagate between a device (a transmitter) at location A to another device (a receiver) located at B. The distance between the devices is the propagation distance d between A and B.

[0051] The example shown in FIG. 2 illustrates that the two signals may be initially in-phase (Δφ=0). However, other implementations may transmit signals that are initially out of phase by some known amount. The signals propagate from the transmitter at location A to the receiver at location B, thereby traversing a distance d. When the signals arrive at location B, there is an accumulated phase difference, Δφ, which can be measured. If the signals are represented as sinusoids, a first pilot tone f1 transmitted by the transmitter may be represented as:
y₁=A sin(w₁t+φ_o),
where w₁ is the frequency in radians and φ_o is the initial phase offset and may be zero. The received signal at location B is represented as:
y₂=B sin(w₁t+φ_o+φ₁),
where φ₁ is the total phase change across the distance, d, traveled. The phase of y₂ is related to distance as follows:
φ₁=2πd/λ₁
where λ₁ is the wavelength of the tone with frequency f₁. Similarly, a frequency tone f₂ transmitted at location A is represented as:
y₃=C sin(w₂t+φ_o),
where w₂ is the frequency in radians and φ_o is the initial phase offset. The initial phase offset φ_o may be zero. The corresponding received tone at location B may be represented as:
y₄=D sin(w₂t+φ_o+φ₂),
where φ₂ is the total phase change across the distance, d, traveled for frequency tone f₂. The phase of y₄ is related to distance as follows:
φ₂=2πd/λ₂
where λ₂ is the wavelength of the signal with frequency f₂.

[0052] For both frequency tones, the distance, d, may be represented as an integer number of full wavelengths and a fractional (or residual) wavelength. For example, φ₁ and φ₂ may be represented as follows:

[0053] ${\phi }_1=2\pi d\text{/}{\lambda }_1=\frac{2\pi }{{\lambda }_1}\left(N_1{\lambda }_1+\frac{\stackrel{\_}{{\varphi }_1}}{2\pi }{\lambda }_1\right)=2\pi N_1+\stackrel{\_}{{\varphi }_1}$ ${\phi }_2=2\pi d\text{/}{\lambda }_2=\frac{2\pi }{{\lambda }_2}\left(N_2{\lambda }_2+\frac{\stackrel{\_}{{\varphi }_2}}{2\pi }{\lambda }_2\right)=2\pi N_2+\stackrel{\_}{{\varphi }_2}$
where λ₁ and λ₂ are the wavelengths of f₁ and f₂, N₁ and N₂ are integer number of full cycles of f₁ and f₂ (i.e., integer number of wavelengths of the signal corresponding to a distance), and φ₁ and φ₂ are the residual non-integer phases of the frequency tones f₁ and f₂ across distance, d. Accordingly, the total phase difference at location B is as follows:

[0054] $\mathrm{\Delta \varphi }={\varphi }_1-{\varphi }_2=\frac{2\pi d}{{\lambda }_1}-\frac{2\pi d}{{\lambda }_2}=2\pi \left(N_1-N_2\right)+\stackrel{\_}{{\varphi }_1}-\stackrel{\_}{{\varphi }_2},$
where (N₁−N₂) is the difference in the integer number of wavelengths of the two signals. If c is the speed of light, and f₁ and f₂ are the two frequency tones then:

[0055] $\begin{array}{cc}\frac{2\pi d}{c}\left(f_1-f_2\right)=2\pi \left(N_1-N_2\right)+\left(\stackrel{\_}{{\varphi }_1}-\stackrel{\_}{{\varphi }_2}\right)& \mathrm{Eqn}.1\end{array}$

[0056] FIG. 3 illustrates differences between frequency tone pairs against the measured phase differences. This figure illustrates that the phase difference will accumulate up to 2π, and then begins increasing again from zero. If the distances are small such as:

[0057] $d\le \frac{c}{\left(f_1-f_2\right)}$
one can then assume that N₁=N₂. In this case Eqn. 1 simplifies and it is possible to calculate d from the residual phase differences. Suppose there are n tone frequencies in a signal transmission spectrum. Then for each frequency there are n−1 cases where a residual phase difference can be calculated. For example, for frequency f₁ the combinations are (f₁, f₀), (f₁, f₂), . . . , (f₁, f_n-1). The calculated residual phase difference can be plotted against the pair frequency differences to generate a straight line curve. The fitted gradient of this line can then be used to calculate distance d.

[0058] The above formulation can also be generalized to the case where initially the two signals have a known fixed phase difference. This fixed offset will not however have any effect on the line's gradient. Similarly, any phase measurement calibration errors will shift the line but will not affect its gradient. This is one of the advantages of a differential phase system in that phase differences are relative rather than absolute values.

[0059] The horizontal axis of FIG. 3 measures frequency difference from a base frequency. For a multi-frequency signal that has “n” frequency tones, FIG. 3 can be repeated for each of the “n” tones (f₀, f₁, . . . , f_n-1), where each tone provides a gradient. The gradients can then be combined to provide a better estimate for a distance “d.” The combination algorithm may include averaging or a more complex algorithm such as Kalman filtering. The total number of frequency pair combinations where residual phase difference values can be calculated is as follows:
n(n−1)/2.
The division by 2 is necessary since there is no difference between (f₀, f₁) and (f₁, f₀). The distance, d, can be calculated from a single pair measurement, as was shown in the equations above. The averaging can be performed by averaging gradients or simply using Eqn. 1 and averaging the calculated values for d. Once the distance between a transmitting device and receiving device is calculated, the process can be repeated with other nearby devices, whereby the distance between each of the other devices may also be computed.

[0060] The short distance criterion

[0061] $d\le \frac{c}{\left(f_1-f_2\right)}$
is an assumption. For example, if f=1 MHz and c=3×10⁸ m/s then as long as d is less or equal to 300 m N₁=N₂, then d can be calculated directly from the residual phase difference calculations. If f=10 MHz then d has to be less than or equal to 30 m for N₁ to be equal to N₂. For the general problem, however, d is not assumed to be small. In this case, phase ambiguities N₁ and N₂ may be solved using integer ambiguity techniques. This phase ambiguity means that an individual transmitter can only calculate the range subject to a possible ambiguity factor. However, this ambiguity may be resolved by using multiple transmitters at known locations.

[0062] Eqn. 1 considers one frequency pair measurement for a transmission between two devices. However, it can be generalized for any pair of frequency measurements with any number of devices:

[0063] $\begin{array}{cc}\frac{2\pi d_k}{c}\Delta f_{\mathrm{ij}}^k=2\mathrm{\pi \Delta }{N}_{\mathrm{ij}}^k+{\mathrm{\Delta \varphi }}_{\mathrm{ij}}^k& \mathrm{Eqn}.2\end{array}$
Example devices may include a mobile device and an access point. In this case, d_k represents the distance from the mobile device to access point k, Δf_ij^k represents frequency difference between two tones (f_i−f_j) using access point k, ΔN_ij^k represents the difference between the number of full cycles associated with frequency tones f_i and f_j using access point k, and Δφ_ij^k represents the residual phase difference between frequency tones f_i and f_j using access point k.

[0064] In the case where there are three devices used to determine the location of a device with unknown location, Eqn 2 gives:

[0065] $\begin{array}{cc}\frac{2\pi d_1}{c}\Delta f_{\mathrm{ij}}^1=2\pi \Delta N_{\mathrm{ij}}^1+{\mathrm{\Delta \varphi }}_{\mathrm{ij}}^1& \mathrm{Eqn}3\\ \frac{2\pi d_2}{c}\Delta f_{\mathrm{ij}}^2=2\pi \Delta N_{\mathrm{ij}}^2+{\mathrm{\Delta \varphi }}_{\mathrm{ij}}^2& \mathrm{Eqn}4\\ \frac{2\pi d_3}{x}\Delta f_{\mathrm{ij}}^3=2\mathrm{\pi \Delta }{N}_{\mathrm{ij}}^3+{\mathrm{\Delta \varphi }}_{\mathrm{ij}}^3& \mathrm{Eqn}5\end{array}$
From the above equations, it can be seen that the distances between the devices with known locations and the device with unknown location d₁, d₂, and d₃ may be determined by solving the system of linear equations. For instance, the equations may be solved by measuring the phases φ of each tone, calculating Δφ for the different tones, calculating Δf from the known frequency values of the tones, and solving the system of linear equations for d₁, d₂, and d₃ by selecting values of N by trial and error. The correct values of N will result in a solution for the system of equations and provide the distance results.

[0066] For an n tone signal there are n(n−1)/2 frequency pair combinations where residual phase difference values can be calculated. Thus, if there are three access points then Eqns 3, 4 and 5 will result in 3n(n−1)/2 equations which can be solved to find the location of the mobile device. For the general situation where there are p access points there will be p·n(n−1)/2 equations to solve for locating the mobile device. One method to solve the equations is as follows. Given the access point locations, a positioning system may pick one access point and fix its ΔN_ij^k to an integer and then try different integers for the other ΔN_ij^k and for each integer combination try to solve the triangulation problem and see if a solution exists. For a two dimensional location problem, circles are drawn and they must intersect at one point for a valid solution. Three transmitters as access points may be used to solve this problem as mentioned above. For a three dimensional location problem spheres are drawn. Four transmitters may be used to solve this problem as mentioned above. This search process may continue until a valid solution is obtained. Other constraints may also be used during this search. For example, |d_p+d_q|>d_pq, and |d_p−d_q|<d_pq, where d_pq, is the distance between the pth and qth access points and ∥ is the modulus operator. This search process may be carried out by a location engine which is running on a server. The physical location of the location engine may be embedded into a transmitting device, a receiving device, or an independent device such as a server. While the present description illustrates resolving the phase ambiguity using examples provided above, it is to be understood that other techniques for resolving the phase ambiguity may be used to determine the distance values.

[0067] In one embodiment, the solution to the above system of equations may be resolved by using amplitude information from the received tones to select starting values of N. For example, in one embodiment the amplitudes of the received tones may be used to determine an estimate of the distance between a transmitting and receiving device. The estimated range may then be used to select values for N that are likely solutions to the above equations. For example, in one embodiment, the amplitude of the received signal may be used to determine the received power. The power attenuation of a transmitted signal is related to range as follows:

[0068] $P_{\mathrm{RX}}\propto \frac{P_{\mathrm{TX}}}{R^2}$
Where P_RX is the received power, P_TX is the transmitted power, and R is the distance. However, this distance measurement may not be very accurate. Nevertheless, if the received power is known (e.g., from the amplitude) and the transmitted power is known, then the distance may be estimated. The estimated distance may be used to determine values for N in the equations above that will result in final distance results. For example, the estimated distance values may be used with the known frequency and phase differences to calculate estimated values for N, which may in turn be used to narrow the selection of values for N. The selected values for N derived from the estimated values of the distance may then be used to calculate final distance values. In one embodiment, the transmitted power may be stored as encoded data in the tones and sent from the transmitting device to the receiving device. In another embodiment, the transmitted power may be sent to a location engine and used as part of the location calculation process. It is to be understood the transmitted and received power of individual tones or the total power of transmitted and received signals may be used to determine the estimated distance.

[0069] FIG. 4A illustrates a system 400A according to one embodiment of the present invention. System 400A includes a first device 401 at known location A, a second device 402 at known location B, a third device 403 at known location C, a fourth device 404 at known location D, and a device 405 at unknown location F. In this embodiment, devices 401-404 may transmit signals and device 405 may receive the signals for determining the distance between each device having a known location and the unknown location of device 405. In this example, each device 401-404 transmits a signal 408-411 including a plurality of frequencies (tones):
(f₀,φ₀), (f₁,φ₁), (f₂,φ₂), . . . , (f_n-1,φ_n-1).
The different signals 408-411 may include the same frequencies or different frequencies as the other signals, or combinations thereof. For example, signal 408 and signal 409 may contain the same frequencies, while signal 409 and signal 410 may share only some of the same frequencies, but otherwise use different frequencies. As described in more detail below, different multi-frequency protocols may be used between different devices to determine the distance.

[0070] Device 405 receives the signals 408-411 from the devices 401-404. The signals from each device 401-404 will be received with some detectable phase change. The distance may be determined by processing the received signals. For example, in one embodiment the received signals may be converted from analog signals into digital signals and processed using digital signal processing. Processing may include determining the phase of the received frequency components, determining the frequency characteristics of the transmission channel, and determining the phase differences. Processing may further include calculating distances using the phase difference results and determining the location of the electronic device 405 by identifying a point on a plurality of circles (or spheres) of radius, d_i, where d_i is the distance from a device having a known location to the device of unknown location, where all four circles (or spheres) intersect. The 2D locating problem requires a minimum of three circles intersecting in one point in 2D. The 3D problem requires a minimum of four spheres intersecting at one point in 3D. As illustrated in FIG. 4A, processing the signal information may be performed (in whole or in part) by a location engine. In the example illustrated in FIG. 4A, the signal information may be sent from electronic device 405 through any one of the other electronic devices (e.g., device 404) and network 450 to a server 407. Network 450 may be a wired and wireless network (e.g., a LAN or WAN) and may include the Internet, for example. Server 407 includes a location engine 451 for determining the location of electronic device 405. The location engine may receive either the raw data for the digitized signals or preprocessed data, such as extracted phase differences and estimated frequency responses, for example, for determining the location of the device. In other embodiments, the location engine may be included on one of the electronic devices 401-404 as illustrated at 451A. In yet other embodiments, the location engine may be included as part of electronic device 405 as illustrated at 451B. As described in more detail below, the location engine may include multiple components for performing different processing tasks such as phase extraction and channel estimation for each of the individual transmissions between the device 405 and the other devices 401-404 or determining the final location of device 405, for example. In some embodiments, the location engine components may be implemented on different devices in the system. In one example application, location engine 451 on server 407 may calculate the location and return this information back to the device 405. In one embodiment, embedded navigation software may help a user of device 405 navigate to a desired location (e.g., if device 405 is a cell phone or mobile wireless device). In another embodiment, device 405 may have a gyrator that can provide a differential vector of movement relative to previous positions. This can be used to minimize the errors of the system. For example, if there are system errors and the final calculated position of device 405 fluctuates widely from before then the relative movement vector of the gyrator may be used to reduce errors by adding the movement vector to a previous more reliable calculated position or by combining the latest calculated position with the gyrator movement vector.

[0071] FIG. 4B illustrates a system 400B according to one embodiment of the present invention. In this example system, device 405 may transmit signals and devices 401-404 may receive the signals for determining the distance between each device having a known location and the unknown location of device 405. Similar to the example in FIG. 4A, the different signals 418-421 may include the same frequencies or different frequencies, or combinations thereof. Devices 401-404 receive the signals 418-421 from device 405. The signals will be received with some detectable phase change. The distance may be determined by processing the received signals as described above. In this example, the signal information is initially in each device 401-404. This information may be sent from a device where the signal is received to a server 407, to any one of the other electronic devices receiving a signal, or even back to the transmitting device for processing by a location engine or component thereof.

[0072] FIG. 5 illustrates a method 500 according to one embodiment of the present invention. At 501, a first signal having a plurality of frequency components (tones) is transmitted between a first device at an unknown location and a device at a known location. At 502, a second signal having a plurality of frequency components is transmitted between the first device at the unknown location and another device at another known location. At 503, a third signal having a plurality of frequency components is transmitted between the first device at the unknown location and yet another device at another known location. This process may be repeated for any number of devices within range of the device at the unknown location. Four devices at known locations are sufficient for determining the location of the unknown device in 3D. At 504, the phase differences with corresponding frequency differences are determined for each transmission between a device at a known location and the device at the unknown location. At 505, the location of the first device is determined from the phase and frequency differences. For example, the system may determine where circles or spheres intersect in one point to locate the device. Additionally, the system can calculate the distances between the devices.

[0073] Embodiments of the present invention may locate different electronic devices using a variety of different multi-frequency transmission technologies. Example electronic devices that may be located include mobile electronic devices such as cellular phones, personal digital assistants (PDA), laptop computers, or any other electronic device with functionality to send or receive signals as described herein. Example electronic devices having known locations may include wireless network access points (e.g., an 802.11 access point) or base station (e.g., a cellular base station), for example. In another embodiment described in more detail below, the position of a first electronic device with an initially unknown location may be determined using multiple other devices with known locations, and the position of another device with an unknown location may be determined using the discovered position of the first device. This ad-hoc network positioning system is described in more detail below.

[0074] In one exemplary implementation, embodiments of the present invention may transmit orthogonal frequency division multiplexing signals between devices to determine the distance. Orthogonal frequency division multiplexing (OFDM) is a communications technique that divides a communications channel into a number of frequency bands. OFDM is also referred to as multi-tone modulation. FIG. 6A illustrates an example of an OFDM signal having a plurality of frequencies that may be transmitted between a device having a known location and a device having an unknown location to determine position. This example OFDM signal includes a carrier frequency (or center frequency) and a plurality of sub-carriers having different frequencies. The sub-carriers are typically spread symmetrically around the carrier frequency. The frequency bands are equally spaced at a distance, in frequency, of 1/Ts, where Ts is the time period corresponding to the frequency spacing. Typically, each sub-carrier frequency is used to encode a portion of the information transmitted, and each sub-carrier frequency resides within a frequency band. All the sub-carrier frequencies are combined and transmitted simultaneously for a certain time period. The time period of transmission of a certain data set encoded in the sub-carriers across all the frequencies (and modulated at the carrier frequency) is called a symbol period, and the transmitted tones for that period is a symbol. In an exemplary OFDM system, each sub-carrier is orthogonal (independent of each other) with every other sub-carrier, differentiating OFDM from the frequency division multiplexing (FDM). Therefore, these OFDM systems allow the spectrum of each tone to overlap because the tones are orthogonal and do not interfere with each other. The overall amount of spectrum that is required is reduced because the tones overlap.

[0075] Exemplary OFDM systems spread the data to be transmitted over a large numbers of carriers, each of which is modulated at a low rate. The tones in these OFDM systems have the very special property of being the only Eigen-functions of a linear channel. This prevents interference between adjacent tones in OFDM systems. The baseband OFDM signals in a system with n frequency tones can be written as:

[0076] $x\left(t\right)=\sum _{m=0}^{n-1}{X}_m\exp \left(j2\pi \frac{m}{T}t\right),0\le t\le T$
Where:

[0077] $f_m=\frac{m}{T}$
is the central frequency of the mth sub-channel and X_m is the corresponding transmitted symbol.
The signals:

[0078] $\exp \left(j2\pi \frac{m}{T}t\right)$
are orthogonal over [0, T] as illustrated below:

[0079] $\frac{1}{T}{\int }_0^T\exp \left(j2\pi \frac{m}{T}t\right)·\exp \left(-2\mathrm{j\pi }\frac{l}{T}t\right)dt={\delta }_{\mathrm{ml}}$
The frequency domain representation of a number of tones demonstrates that the peak of each tone corresponds to a zero level, or null, of every other tone. The result of this is that there is no interference between tones. When the receiver samples at the center frequency of each tone, the only energy present is that of the desired signal, plus whatever other noise happens to be in the channel.

[0080] Individual sub-channels can be completely separated by a receiver's Fast Fourier Transform (FFT) if there are no Inter-Symbol Interference (ISI) and Inter-Carrier Interference (ICI) introduced by the channel. Multi-path propagation can cause linear distortions, spread energy into adjacent channels, and cause ISI and ICI. Some implementations of OFDM systems are more robust to multi-path effects and prevent ISI and ICI by creating a cyclically extended guard interval called a cyclic prefix, where each OFDM symbol is preceded by a periodic extension of the signal. ISI and ICI can be eliminated when the guard interval is longer than the channel impulse response or multi-path delay. The overhead introduced by the cyclic prefix, however, increases with the length of the cyclic prefix. Some OFDM systems also reduce frequency selective fading by averaging over all frequencies.

[0081] Some embodiments of the present invention may determine the location of a mobile electronic device using several access points (or base-stations) with known coordinates. The resolution of the location of a mobile device may include the case where the access points/base-stations are OFDM transmitters and the mobile device is the receiver, or the case where the mobile device is the OFDM transmitter and the access points/base-stations are the receivers, or yet other situations where some access points/base-stations are OFDM transmitters and some are receivers. The proposed method can be applied to any system that is based on any OFDM scheme or uses multiple pilot tones including, but not limited to, 802.11, WLAN, 4G cellular, WiMax, and UWB standard. Other systems such as Bluetooth may also be used where one transmitted packet contains multiple frequency tones that are used for positioning as described herein. The proposed methodology may be used where the transmitter and receiver use the same standard and protocol, but not all access points/base stations used to determine the location of the mobile device need to use the same standard and protocol.

[0082] The accuracy of the location measurement improves as more transmissions with devices having known locations are utilized and as more frequency pair combinations are used for each transaction. The accuracy of the system can also be increased by increasing the number of OFDM frequency tones and increasing the bandwidth and frequency distance between the tones. These factors average out and reduce the effects of fading and multipath. The Media Access Control (MAC) layer typically determines the number of tones. Also, in Multiple-Input and Multiple-Output (MIMO) systems it is possible to use several antennas to gather more data and do more averaging to get more accurate results. For example, a MIMO access point acting as a transmitter can use more than one antenna. In a specific example, an access point can have 4 or more antennas. So in FIG. 4A the four transmitters are from one physical access point. But each transmitter represents one of the antenna of the multiple antenna access point. Likewise, in FIG. 4B the receivers can each be one of the antenna of a multiple antenna access point. If the location of each of the antenna of the access point that are used is known then triangulation can be used for locating the mobile device. Hybrid cases are also possible where for example in FIG. 4A some of the transmitters are from different antenna on the same physical multiple antenna access point and other transmitters are from physically different access points. Likewise, in FIG. 4B some of the receivers may be different antenna of the same physical multiple antenna access point and other receivers are physically different access points. A mobile device can also have multiple antenna so it can transmit using each antenna or receive with each antenna.

[0083] Furthermore, it is possible to use just those antennas with the highest performance, lowest bit error rates, and better line of sight. In ultra wideband (UWB) systems, a plurality of tones may be transmitted and received simultaneously as well. As mentioned above, in one embodiment the access points/base-stations are transmitters and mobile device is the receiver. In another embodiment the access points/base-stations are receivers and the mobile device is the transmitter. In another embodiment, the access points/base-stations and mobile device are transmitters and receiver. This may be advantageous in systems where transmit and receive frequencies are different. For example, some cellular systems transmit at 1 GHz and receive at 1.1 GHz. Switching the role of transmitter and receiver therefore provides more data samples and equations to solve. Also some systems such as wireless local area network (WLAN) can operate at different frequencies. For example, WLAN 802.11a and 802.11g use two different frequencies and using both frequencies provides more data for processing and getting a more accurate location. Another way to improve location accuracy is to use several wireless standards. For example, if an access point and a mobile device both have UWB and WLAN connectivity then data may be obtained from both standards and processed to get a more accurate location value.

[0084] After the mobile device's position is calculated, it is possible to interface the system with a navigation system that provides path planning and guidance. In another configuration a mobile device whose position is known or calculated can also be used as an access point to locate the position of other mobile devices.

[0085] FIG. 6B illustrates another example method of determining the location of a mobile device according to another embodiment of the present invention. At 650, a number “n” representing the number of transmitters having known locations is initialized (n=1). At 651, the first transmitter transmits multiple pilot tones (e.g., OFDM tones). At 652, the receiver (e.g., a mobile device) receives the signal and extracts the pilot tones. At 653, the receiver sends the pilot tone pair phase differences, which may include a plurality of phase difference values corresponding to the phase difference between some or all of the tones, to a server. The amplitudes of the different received tones may also be sent to the server. Additionally, the coordinates of the transmitter may be sent to the server. At 654, the number “n” is incremented, indicating that the next transmitter should transmit. At 655, the number “n” is compared to the number of transmitters. If all the transmitters have not transmitted, then the process returns to step 651, and the next transmitter sends a signal and steps 652 through 654 are repeated. If all the transmitters have transmitted (n>number of transmitters), then the server processes the phase difference data, tone amplitudes, and coordinates of transmitters to determine the location of the receiver at 656.

[0086] FIG. 6C illustrates a system 600 according to one embodiment of the present invention. The transmitter 601 is a OFDM transmitter. Although each standard (WLAN, WiMax, Cellular, etc.) may have slightly different implementation than this figure, the techniques for determining the location of an unknown device as applied to system 600 may be applied other standards. The receiver 603 is also a OFDM receiver including an OFDM range engine block 623 and location engine 624. The transmitter 601 receives input bits representing data such as voice, text or other kinds of information and performs channel coding 602. Channel coding protects data sent over the communication channel in the presence of noise. Channel coding is usually performed with forward error correction, where redundant bits are added to the information bits. These added bits then allow the receiver to detect and correct small errors without asking for transmission of additional data from the transmitter. Interleaving 603 may be part of the channel encoder 602 and may be used to randomize errors by exploiting frequency diversity and providing robustness against multi-path and interference. Each sub-carrier may be modulated 604 with a conventional modulation scheme (e.g. PSK/QAM). The data may be transformed from a serial representation to a parallel representation at 605. The pilot insertion block 606 inserts the pilot tones. The amplitude and phase of these pilot tones are stored and used for estimating channel attenuation and channel equalization. After the data modulation step these pilot tones become the subcarriers. The details of the implementation vary depending on the standard (e.g. WLAN, WiMax, Cellular). Some standards may use different frequencies at the same time while others may use the same frequency at different times. After the insertion step an n-point inverse fast Fourier transform (IFFT) 607 may transform the data sequence. The guard insertion block 608 may insert a cyclic extension of a time length that is larger than the expected delay spread to avoid inter-symbol and inter-carrier interference. The data is converted from a parallel representation to a serial representation 609. The Digital-to-Analog (D/A) converter 610 changes the signal into the analog domain and contains Low-Pass Filters (LPF) that match the sampling interval. After conversion, the signal is modulated at 651 by a carrier wave having a carrier frequency and transmitted. This step is also referred to as “up conversion” because the signals having a plurality of frequencies are being moved in frequency up to a higher frequency that is typically symmetric around the carrier frequency.

[0087] The wireless channel 611 in FIG. 6 is modeled as an impulse response “h” followed by complex Additive White Gaussian Noise (AWGN) 612. The receiver 614 performs demodulation of the modulated signal at 652 and Analog-to-Digital (A/D) conversion and low-pass filtering at 614. The demodulation step at 652 is also referred to as “down conversion” because the signals having a plurality of frequencies are being moved in frequency back down from the carrier frequency to their original frequencies. The data may then go through serial to parallel conversion 615 and guard removal 616. A fast Fourier transform (FFT) block 617 transforms the data back into the original form. The signals are extracted and channel estimation is performed 618. The signals and estimated channel information are then used by the OFDM range engine 623 to calculate the residual phase differences between two frequency tones and extract amplitude information for each tone. The data is converted from a parallel to a serial representation 619. The binary information is obtained after demodulation 620 that demodulates the frequency sub-carriers, de-interleaving 621, and channel decoding 622. Blocks 651 and 652 perform carrier frequency up/down conversion, whereas 604 and 620 carry out sub-carrier modulation and demodulation.

[0088] The receiver 613, optionally, has a location engine 624. This location engine 624 may be used in instances where the receiver 613 is used for location calculation via methods such as triangulation search methods. Thus, the location engine uses its calculated residual phase differences and tone amplitude information for each of the access points to calculate its own position. If the receiver 613 does not have a location engine 624 to calculate its own position it can transmit the calculated residual phase differences and tone amplitude information to a network server or another mobile device for location calculations.

[0089] Time and the index representing the access point are not shown in the equations below to avoid repetition. For example, Eqn 2 used index k to refer to a specific access point. A time index also means representing a received signal Y as Y(t) where t represents a particular time instance. Suppose that the received signal by the receiver in FIG. 6 is represented by Y. Then Y can be represented as:
Y=X·H+W
Where:
Y=[y₀, y₁, . . . , y_n-1]
is the received OFDM symbol vector and:
X=[x₀, x₁, . . . , x_n-1]
is the transmitted OFDM symbol vector and:
H=[h₀e^jφ0, h₁e^jφ1, . . . , h_n-1e^jφn-1]
is the frequency response vector of the channel and:
W=[w₀, w₁, . . . , w_n-1]
is the Additive White Gaussian Noise (AWGN) vector. FIG. 7 illustrates a range engine 700 according to one embodiment of the present invention. Channel estimation algorithms in OFDM provide estimates for H. The OFDM range engine 700 then uses the estimated channel frequency response vector 701 to extract phase information at 703 to calculate the residual phase differences, Δφ_ij^k, of Eqn. 2 and extract amplitude information at 702 for each tone. The Δf_ij^k tone frequency differences of Eqn. 2 can be calculated based on the spacing between OFDM tone subcarriers. The amplitude information may also be used to estimate range between devices as describe above, for example, where the range may be estimated by correlating the transmitted power and the received signal amplitude with the distance traveled. Additionally, in one embodiment the tone amplitude information may be used to reduce the effects of noise, fading or multipath. For example, the impact of such adverse channel effects may be reduced by weighting the tones based on received amplitudes, which may be normalized, for example. In one embodiment, the amplitudes of the received tones may be averaged, and weights may be assigned to each tone based on the amplitude of each tone relative to the average amplitude. In another embodiment, the highest and lowest received tone amplitudes are determined, and weights are assigned to each tone based on the amplitude of the tone relative to the range of received amplitudes. Accordingly, smaller received amplitudes may be given smaller weights in the location calculations or ignored altogether because it could represent noise or fading. Amplitude information may also be used to detect multi-paths. For example, the variation in amplitude across all the received tones may be determined. Access points that provide a direct line of sight will have fewer variations in the amplitudes of their tones and will be preferred in the triangulation calculations in order to reduce the effects of multipath.

[0090] The example embodiment shown in FIG. 7 uses OFDM. Other packet-based methods and standards may be utilized as well. Many packet-based methods may be modified such that it uses n pilot tones in the packet pre-amble or packets that have room. In one embodiment the transmitters may be nearby WLAN or 4G cellular or WiMax or UWB access points/base-stations, and the mobile device is a portable electronic device such as a cellular phone, personal digital assistant (“PDA”), or watch, or any computer based system, for example.

[0091] FIG. 8 illustrates determining the location of an electronic device according to one embodiment of the present invention. FIG. 8 illustrates that the distance between one device 801 having an unknown location may be used to determine the location of another device 806 having an unknown location if the first device is within range of devices with known locations or if the device has a GPS technology. For example, tones having different frequencies may be transmitted between devices 802, 803, 804, and 805 and device 801, resulting in corresponding phase differences that may be used to determine the distances between the devices at known locations and device 801. Accordingly, the location of device 801 may be determined. Additionally, tones having different frequencies may be transmitted between device 801 and device 806, resulting in corresponding phase differences. In one embodiment, if three other devices having known locations are within range (e.g., devices 802, 803, and 804 are in range, but device 805 is not in range), the location of device 806 may be determined using tones from each of these devices and tones from device 801. As a specific example, devices 801 and 806 may be mobile devices and devices 802-805 may be wireless access points. The location of mobile device 806 may be determined using a combination of signals from one or more access points and one or more other mobile devices that have known locations based on other access points. In one embodiment, if a mobile device having an unknown location is out of range of all access points having known locations, the location of the mobile device may still be determined if the mobile device is within range of other mobile devices that are within range of access points with known locations. Similarly, if a mobile device having an unknown location is out of range of all access points having known locations, the location of the mobile device may still be determined if the mobile device is within range of other mobile devices with known locations obtained through GPS. In that example, one or more mobile devices may have known locations using GPS technology (or position assisted GPS), and the location of another mobile device that does not have GPS may be determined using the techniques described above.

[0092] The above description illustrates various embodiments of the present invention along with examples of how aspects of the present invention may be implemented. The above examples and embodiments should not be deemed to be the only embodiments, and are presented to illustrate the flexibility and advantages of the present invention as defined by the following claims. Based on the above disclosure and the following claims, other arrangements, embodiments, implementations and equivalents will be evident to those skilled in the art and may be employed without departing from the spirit and scope of the invention as defined by the claims.