Method and apparatus for locating a mobile device within an indoor environment

A method for locating a mobile device is disclosed. Initially, a set of modulated ultrasound signals and a set of radio signals are separately broadcast from a group of transmitters. The ultrasound signals include at least one symbol configured for pulse compression. After the receipt of a demodulated ultrasound signal from a mobile device, wherein the demodulated ultrasound signal is derived from the modulated ultrasound signals, transmitter identifier and timing information are extracted from the demodulated ultrasound signal. Timing information include, for example, the arrival time of the demodulated ultrasound signal in relation to the start time of its transmission. After the locations of the transmitters have been ascertained from the transmitter identifier information, the location of the mobile device can be determined based on the timing information and the locations of the transmitters.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates to location tracking systems in general, and in particular to a method and apparatus for locating a mobile device within an indoor environment.

2. Description of Related Art

Location tracking systems, such as Global Positioning System (GPS), can generally determine the location of a mobile device in an outdoor environment very accurately. However, these location tracking systems tend to perform poorly indoors when tracking signals are usually not available.

There are several solutions for locating mobile devices indoors, but these solutions require the installation of many densely-located infrastructure devices, such as beacons and transponders, and require complicated additional hardware in mobile devices as well Consequently, it would be desirable to provide an improved method and apparatus for locating a mobile device within an indoor environment.

SUMMARY OF THE INVENTION

In accordance with a preferred embodiment of the present invention, a set of modulated ultrasound signals and a set of radio signals are separately broadcast from a group of transmitters. The ultrasound signals include at least one symbol configured for pulse compression. After the receipt of a demodulated ultrasound signal from a mobile device, wherein the demodulated ultrasound signal is derived from the modulated ultrasound signals, transmitter identifier and timing information are extracted from the demodulated ultrasound signal. Timing information include, for example, the arrival tune of the demodulated ultrasound signal in relation to the start time of its transmission or in relation to other received ultrasound signals. After the locations of the transmitters have been ascertained from the transmitter identifier information, the location of the mobile device can be determined based on the timing information and the locations of the transmitters.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

Referring now to the drawings and in particular toFIG. 1, there is illustrated a block diagram of a system for locating a mobile device within an indoor environment, in accordance with a preferred embodiment of the present invention, As shown, a system100includes multiple transmitters101-103, a server106and a time synchronization source107. Server106can be connected to transmitters101403via a network105, as shown, or connected to transmitters101-103directly, Transmitters101-103can asynchronously emit ultrasound signals108-110, respectively, in the frequency range between 19-24 KHz at known time-offsets. Transmitters101-103may be grouped and time synchronized to time synchronization source107. Time synchronization source107may achieve synchronization among transmitters101-103and a mobile device104via wires or wirelessly. Transmitters101-103are also equipped with radios for periodically broadcasting radio signals, such as Bluetooth signals or WiFi signals, containing transmitter identifier (ID) or timing information to deduce a transmitter identifier.

Referring now to the drawings and in particular toFIG. 1, there is illustrated a block diagram of a system for locating a mobile device within an indoor environment, in accordance with a preferred embodiment of the present invention. As shown, a system100includes multiple transmitters101-103, a server106and a time synchronization source107. Server106can be connected to transmitters101-103via a network105, as shown, or connected to transmitters101-103directly. Transmitters101-103can asynchronously emit ultrasound signals108-110, respectively, in the frequency range between 19-24 KHz at known time-offsets. Transmitters101-103may be grouped and time synchronized to time synchronization source107. Time synchronization source107may achieve synchronization among transmitters101-103and a mobile device104via wires or wirelessly. Transmitters101-103are also equipped with radios for periodically broadcasting radio signals118-120, such as Bluetooth signals, containing transmitter identifier (ID) or timing information to deduce a transmitter identifier.

Ultrasound signals108-110are identifiable and can be decoded by mobile device104and/or server106. If mobile device104is tightly time synchronized to transmitters101-103, a time-of-flight (TOP) ranging technique can be employed, But in order to avoid the requirement of mobile device104to be tightly synchronized with transmitters101-103, a TDOA pseudo-ranging technique can be utilized.

The location of each of transmitters101-103is known from a mapping between each. transmitter ID and its physical location, which can be determined by the system's owner or determined automatically at runtime through measurement or using techniques such as Simultaneous Localization and Mapping (SLAM). A database of the. ID-to-location mapping for transmitters101-103may be stored in server106or mobile receiver104, which can be accessed via network105. Alternatively, mobile device104can determine the positions of transmitters101-103based on the presence, and optionally, based on relative Received Signal Strength. Indicator (RSSI) levels of modulated ultrasound signals108-110as received by mobile device104.

As an example, mobile device104can time synchronize with transmitters101and102as follows, Transmitters101and102, which are equipped with Bluetooth radios BR1 and BR2, respectively, periodically emit ultrasound signals108and109, respectively, to mobile device104. Synchronized with the transmission of ultrasound signal108, both transmitters101and102begin transmitting Bluetooth packet sequences BP1 and BP2, which include Bluetooth advertisement packets containing a counter value that increases with each successive packet. The counter value in each successive packet is denotes the time that has elapsed since the transmission of ultrasound signal108, so a possible sequence will, begin with counter value t+0, then counter value t+1, then counter value t+2, etc. Mobile device104begins to listen on its Bluetooth radio BR3 asynchronously at time t+0 and receives at least one Bluetooth packet from Bluetooth packet sequences BP1 and/or BP2. Mobile device104extracts the counter value contained in the Bluetooth packets and adjust its clock to time synchronize with transmitters101and102based on the extracted counter value. Alternately, other time synchronization methods such as using the Network Time Protocol (NTP), GPS timing signals or cell tower timing signals may also be employed.

Since transmitters101-103are substantially identical to each other; thus, only transmitter101is further described in details.

With reference now toFIG. 2, there is illustrated a detailed block diagram of transmitter101, in accordance with a preferred embodiment of the present invention. As shown, transmitter101includes a processor201, a memory204, a dock202, an amplifier206and a speaker207, Optionally, transmitter101may also include a network interface203, a thermometer210, a digital-to-analog converter (DAC)205, an analog-to-digital converter (ADC)208and a microphone209.

Processor201is driven by clock202to run the internal circuitry and to keep a local notion of time. Memory204may be utilized to store ultrasound signals for transmissions, Processor201may be connected to network105(fromFIG. 1) via network interface203, over which processor201may synchronize to time synchronization source100(fromFIG. 1). DAC205converts the digital representation of an ultrasound signal, which is to be played back, to an analog signal. DAC205can send this analog signal to amplifier206that can broadcast the analog signal over speaker207.

Alternately, processor201may use a pulse code modulation (PCM) interface to directly transfer data to amplifier206for broadcasting an ultrasound signal. Transmitter101may also coordinate with transmitters102,103to determine the distances with respect to each other, Processor201may determine these distances by measuring the propagation delay of an ultrasonic ranging signal sent to transmitters102,103. Transmitter101may receive the ranging signal with microphone209that can pass the ranging signal to ADC208. ADC208then digitizes the ranging signal and passes it to processor201for processing. Thermometer210may supply processor201with the current ambient temperature in order to calculate the speed of sound under current conditions in order to perform more accurate ranging of mobile device104.

Since conventional speakers typically provide sound output in a unidirectional manner, speaker207needs to include a horn in order to provide ultrasound signal output in an omnidirectional manner.

Referring now toFIGS. 3A-3D, there are illustrated various views of a horn for speaker207, in accordance with a preferred embodiment of the present invention.FIG. 3Ashows a horn300directly attached to speaker207,FIG. 3Bis a cross-section view of horn300,FIG. 3Cis a perspective view of horn300from the bottom, andFIG. 3Dis a perspective view of horn300without the top. Horn300includes a conical top301and a cylindrical base302having a small opening303and a wide opening304. Small opening303leads to a throat316that is connected to a mouth315of conical top301. Wide opening304leads to a chamber308. Wide opening304is also connected to an outer rim of speaker207. The circumference of wide opening304covers the entire diaphragm (not shown) of speaker207to provide an airtight seal. Although base302is shown to be in a cylindrical shape inFIGS. 3C-3D, it is understood by those skilled in the art that base302can be any shape as long as it is capable of covering the entire diaphragm of speaker207to allow ultrasound signals to travel from speaker207to chamber308with minimal loss. Likewise, although top301is shown to be conical in shape, it is understood by those skilled in the art that a different shape may be used such that the acoustic wave guides are tapered in shape, increasing in cross-sectional area from throat316to mouth315.

As shown inFIG. 3D, cylindrical base302includes acoustic waveguides located between partitions307a-307d(i.e., space between partitions307a-307b,space between partitions307b-307c,space between partitions307c-307d,and space between partitions307d-307a) arranged in a radial pattern, with the throat of each of waveguides connecting to chamber308above speaker207. Acoustic waveguides307a-307dare designed to provide an acoustic impedance match between speaker207and the air surrounding horn300. The characteristics of acoustic waveguides, such as frequency response, amplification and directivity, are defined by the ratio between the area of the throat of each of acoustic waveguides and the area of the corresponding mouth, the angle θ between the mouth and corresponding throat, the dimensions of chamber308and the dimensions of small opening303. These parameters can be tuned to fit the specifications of a specific application. Horn300is preferably made of a rigid, air-tight material such as plastic, metal or wood.

Speaker207may use a permanent magnet or a piezo element to vibrate the diaphragm, which are well-known in the art, to emit ultrasound signals. The ultrasound signals from the diaphragm then go to chamber308, then to throat316and mouth315, which eventually emit to the surrounding space in an omnidirectional manner.

With reference now toFIG. 4, there is illustrated a detailed block diagram of mobile device104, in accordance with a preferred embodiment of the present invention. As shown, mobile device104includes a processor412, a memory415, a clock413, an ADC416and a microphone417. Processor412is driven by clock413to run the internal circuitry and to keep an internal notion of time. Microphone417can receive ultrasound signal transmissions that are then digitized by ADC416and passed to processor412. Mobile device104then transfers a recording of the captured ultrasound signals to server106(fromFIG. 1) to allow demodulation and decoding to be performed at server106. Alternatively, processor412may demodulate and decode the captured ultrasound signals.

Referring now toFIG. 5, there is illustrated a flow diagram of a method for locating a mobile device, in accordance with a preferred embodiment of the present invention. Starting at block500, radio signals, such as Bluetooth signals, are periodically broadcast by transmitters, such as transmitters101-103inFIG. 1, as depicted in block501. Preferably, Bluetooth signals contain corresponding transmitter identifiers (IDs) and timing information that allows a mobile device, such as mobile device104inFIG. 1, to time synchronize to a time synchronization source, such as time synchronization source107inFIG. 1, An ultrasound signal is modulated, as depicted in block502. The details of the ultrasound signal modulation is further explained inFIG. 6. The ultrasound signal preferably includes at least one symbol configured for pulse compression. A determination is made whether or not a transmitter is time synchronized to a time source, such as time synchronization source107fromFIG. 1, as shown in block503. If the transmitter is not time synchronized to a time source, the transmitter is then time synchronized to the time source, as depicted in block504; otherwise, the modulated ultrasound signal is then broadcast by the transmitter at a scheduled time, as shown in block505.

The modulated ultrasound signal is subsequently received by a mobile device, such as mobile device104inFIG. 1, and the mobile device then processes the modulated ultrasound signal, and then sends a demodulated ultrasound signal to the transmitter (or to a server, such as server106inFIG. 1) accordingly. The details of the ultrasound signal demodulation is further explained inFIG. 7.

The demodulated ultrasound signal and any corresponding Bluetooth signal from the mobile device will be picked up by the transmitter. After the transmitter has received the demodulated ultrasound signal and any corresponding Bluetooth signal, a determination is the made whether the received signals were originated from a line-of-sight (LOS) source or non-line-of-sight (NLOS) source, as shown in block507. A received signal is considered as originated from a LOS source when the signal travels directly from the transmitter to the mobile device without going through any obstruction and/or bouncing off any structures such as walls. On the other hand, a received signal is considered as originated from a NLOS source when the signal has to penetrate a structure and/or bouncing off a structure before reaching the mobile device. The details of determining whether a received signal is originated from a LOS source or NLOS source is further explained inFIG. 8.

If any of the received signals was originated from a NLOS source, the received signal will be discarded, as depicted in block508. If the received signals were originated from a LOS source, the transmitter identifier and timing information are then extracted from the Bluetooth signal and the demodulated ultrasound signal, respectively, as shown in block509. Alternately, the timing information from the Bluetooth signal may a be derived from the system clock of the mobile device, as shown in block202ofFIG. 2, or the server instead.

Next, a determination is made whether or not sufficient information have been received to locate the mobile device, as depicted in block510. If not, the process returns to block506to obtain additional signals; otherwise, the locations of the transmitters are ascertained by looking up the transmitter IDs in a transmitter map, as shown in block511. The location of the mobile device is then determined based on the extracted timing information along with the location of the transmitters, as depicted in block512. Basically, after receiving at least two demodulated ultrasound signals that are sent by two different transmitters, the distance between the mobile device and each of the two transmitters can be ascertained, and the location of the mobile device can be determined by using trilateration or multilateration.

Each of ultrasound signals108-110inFIG. 1contains at least one symbol modulated onto an ultrasound carrier, Symbols which are capable of Pulse Compression, such as those used in Chirp Spread Spectrum (CSS) modulation techniques, can encode both data and range information into ultrasound transmissions. Each individual symbol is composed of a waveform that is monotonically increasing (up-chirp) or decreasing (down-chirp) in frequency as a function of time, known as a chirp. Furthermore, different symbols may occupy different frequency ranges of the ultrasound spectrum, have different time durations and be of varying amplitudes.

The symbols are designed as to exhibit no overly rapid changes in amplitude or frequency, which would cause a speaker to produce audible artifacts. In order to smooth out transitions in levels of amplitude, such as at the beginning and end of symbols, the symbol may be preceded and appended by a sinusoid of a similar or equal frequency to that of the part of the symbol that it is concatenated with. These sinusoids gradually change in amplitude over time to smooth out the transition between otherwise rapid changes in amplitude. Alternately to the sinusoids, a window function may be applied to the symbol to achieve a similar effect. The present method can use one or a combination of the following symbol designs:(1) Up- and down-chirps with a linear relationship between frequency and time, as shown in600and601, respectively, inFIG. 6;(2) Up- and down-chirps with an exponential relationship between frequency and time, as shown in682and603, respectively, inFIG. 6(3) Up- and down-chirps with an otherwise monotonically changing relationship between frequency and time;(4) Up- and down-chirps as described in (1), (2) or (3), which employ multiple different rates of change for the relationship between frequency and time;(5) Chirps described in (1), (2), (3) or (4), to which a window function has been applied;(6) Chirps described in (1), (2), (3), (4) or (5), which are preceded and appended by a sinusoid of a similar or equal frequency to the part of the chirp that it is concatenated with, and the sinusoids may have a window function applied to them which gradually increases or decreases their amplitude over time;(7) Chirps described in (1). (2), (3), (4), (5) or (6) to which an equalization function has been applied; and(8) Other symbols that benefit from Pulse Compression such as Barker and Costas Codes.

Detection of a chirp waveform benefits from a signal processing technique known as Pulse Compression. When the received chirp is passed through a matched filter with the original waveform that was transmitted, the width of the output signals is smaller than using a standard sinusoidal pulse as a ranging signal. Alternately, a Fractional Fourier Transform or cross correlation can be performed on the received signal to obtain similar benefits. This compression makes the signal simpler to detect as it effectively increases its signal-to-noise ratio (SNR), which leads to lower amounts of timing jitter; hence improving the range resolution. Other waveforms such as Barker and Costas Codes also benefit from Pulse Compression and may also be employed solely or in a combination with chirps.

Referring now toFIG. 7, there is depicted a flow diagram of a method for demodulating and decoding a modulated ultrasound signal and any corresponding Bluetooth signal, The demodulation and decoding can be performed by a mobile device, such as mobile device104inFIG. 1, or by a server, such as server106inFIG. 1. Initially, the ultrasound signal and any corresponding Bluetooth signal are received by a mobile device, as shown in block700. The ultrasonic signal is then pre-processed by applying equalization and/or additional filtering to aid demodulation, as shown in block701. Next, timing information and any corresponding transmitter ID are extracted from the corresponding Bluetooth signal, as depicted in block702. Alternately, the timing information may be derived from the system clock of the mobile device, as shown in block202ofFIG. 2or the server instead of the Bluetooth signal. This information is used to determine the start time of the recording of the modulated ultrasound signal in relation to a time synchronization source such as time synchronization source107inFIG. 1and subsequently the ID of the transmitter which transmitted the modulated ultrasound signal contained within the recording. The modulated ultrasound signal is then demodulated using a pattern matching technique, as shown in block703. Examples of applicable pattern matching techniques include matched filtering, Successive Interference Cancellation, Fractional Fourier Analysis, cross correlation, etc. At this point, any data encoded within the ultrasound signal can now be read in the demodulated ultrasound signal. The demodulated symbols can be concatenated to form the corresponding transmitted data sequence. The decoded sequence can be checked for errors by applying a Hamming, Golay, Reed Solomon or other error correcting code (depending upon the type of error is correction that may have been used in the transmitted signal). The decoded transmitter ID of each received ultrasonic signal, the amplitude and time offset of the symbol associated with each transmitter ID and any errors that were encountered during the process are outputted. The resulting demodulated ultrasound signal as well as any corresponding ultrasound, Bluetooth signal information and timing information from that were captured is transmitted back to the transmitter or the server, as depicted in block704.

With reference now toFIGS. 8A-8B, there are depicted two flow diagrams of a method for determining whether or not a received signal is originated from a LOS source. Initially, the receiving system (i.e., transmitters and server) needs to be trained, as described inFIG. 8A. Demodulated ultrasound and Bluetooth signals originated from a LOS source are received, as shown in block800, RSSI and timing/distance information are then extracted from the received signals, as shown in block801, and are stored in a. database as LOS signal samples, as depicted in block802. A determination is made whether or not sufficient LOS signal samples have been collected, as shown in block803. If not, more samples will be collected; otherwise, demodulated ultrasound and Bluetooth signals originated from a NLOS source are received, as depicted in block804. RSSI and timing/distance information are then extracted from the received signals, as shown in block805, and are stored in the database as NLOS signal samples, as depicted in block806. A determination is made whether or not sufficient NLOS signal samples have been collected, as shown in block807. If not, more samples will be collected; otherwise, a model is built based on the signal samples stored in the database, as depicted in block808.

After the training has been completed, the receiving system can discern whether or not received signals are originated from a LOS source, as described, inFIG. 8B. During actual operation, after a demodulated ultrasound signal and Bluetooth signal information (that were sent from a mobile device) have been received, as shown in block809, RSSI, transmitter ID and timing/distance information are then extracted from the received signals, as depicted in block810. A determination is made whether or not the two received signals were originated from a LOS source, as shown in block811. Such determination can be made by using a model corresponding to the transmitter ID that was built during the training phase. If not the received signals and the extracted information are discarded, as shown in block813. Otherwise, the extracted information are retained for the purpose of calculating the location of the mobile device, as depicted in block812.

As has been described, the present invention provides an improved method and apparatus for locating a mobile device.