Patent Publication Number: US-2007099625-A1

Title: Object location

Description:
The invention relates to a positioning method and to a radio system, radio station and computer program for use in locating an object, particularly, but not exclusively, in a building by means of radio frequency signals.  
      A number of positioning systems have been proposed to locate the position of a radio transmitter or receiver.  
      A simple approach is to measure the distance of a receiver from a transmitter by measuring at the receiver the strength of a signal transmitted from the transmitter. By using an estimate of the attenuation of the signal strength with distance, and knowing the transmitted power, the received signal strength can be converted into a range measurement.  
      The position of the receiver can be determined by using signals transmitted from a number of transmitters to the receiver, determining the corresponding distance from each transmitter to the receiver, and then locating the receiver from this information, for example by using trilateration.  
      When used indoors, this method has a number of inconveniences. Firstly, the attenuation of a radio signal with distance is hard to estimate indoors, since it depends on the number of absorbers and reflectors such as walls, people, and other highly variable quantities. Systems which use empirical methods, for example using measured attenuation values, to convert received signal strength into range measurements can therefore work better than those that simply calculate range from the equation governing radio transmission in free space. However, measured signal strength values can deviate significantly from those estimated empirically, for example caused by people or other objects moving about the building or fast fading effects which cause nulls in signal reception. Therefore, the method is not very accurate.  
      Secondly, the need for more than one transmitter is inconvenient.  
      Some of the difficulties with the above method in buildings can be addressed using a system in which distance is measured by measuring the time of flight that signals take when they are transmitted from transmitter to receiver. In a simple arrangement, a correlator is used to maximise the correlation between a duplicate of the transmitted signal delayed by a variable delay and the received signal. The variable delay that maximises the correlation is taken to be the time of flight of the signal. By using a number of transmitters, the position of the receiver can be calculated as above using trilateration.  
      However, this approach does not solve the problem of multiple transmitters. Indeed, as well as the three unknown position coordinates needed to locate a receiver in space, the time offset between the internal clocks in both the transmitter and the receiver is also normally unknown, so there are four unknowns to be determined. Therefore, in general four or more transmitters are needed to locate the receiver in space, which remains a significant inconvenience.  
      The other difficulty with such systems when used in indoor environments is that the receiver can receive a number of signal components corresponding to reflections off a variety of reflectors in the indoor environment. This can make it difficult to identify the direct line of sight signal received in the receiver. The effects of reflections are known as multi-path effects and they are particularly significant for use indoors. Indeed, the direct line of sight signal may be completely blocked, and it is very difficult indeed to estimate the time of flight of a line of sight signal in the absence of the direct line of sight component.  
      Therefore, radio positioning in buildings is fraught with difficulty.  
      A known example of a positioning system for use indoors is the system described in “RADAR: an in-building RF-based user location and tracking system”, Bahl et al, Proceedings of INFOCOM 2000, Tel Aviv, March 2000. However, this system only claims a median error distance of about 3 m, about the size of a room.  
      Thus there remains a need for a positioning system and method suitable for use in a building, and particularly for a positioning system and method that can function even when the direct line of sight signal is blocked.  
      According to a first aspect of the invention, there is provided a positioning method of a radio station, the method comprising:  
      providing a parameter database including expected signal parameters of backscattered signals as a function of position;  
      providing an object database including expected signal parameters of backscattered signals from a plurality of objects;  
      transmitting a location signal from the radio station so that it undergoes multipath reflection before being received back at the radio station as a received signal;  
      measuring predetermined features of the received signal;  
      comparing the predetermined features of the received signal with the stored data in the parameter database to find the best match and accordingly the position of the radio station;  
      identifying differences between the predetermined features of the received signal and that expected from the stored data in the parameter database; and  
      comparing the differences with the stored data in the object database to find any matches meeting a predetermined fit criterion and accordingly to identify objects located in the vicinity of the radio station.  
      By first finding the location and then identifying differences, the ability to locate nearby objects is improved. The difference information provides knowledge of other reflectors in the environment not accounted for in the building model. This can be used to build up a more accurate map of the indoor environment than that originally used, so that the user knows his or her position with respect to furniture. The information also allows the receiver to distinguish between fixed objects (such as walls) and movable objects (such as people) which may be very useful in some applications.  
      The method has a number of benefits over prior approaches. Firstly, it does not require multiple transmitters and receivers. Secondly, the method does not require the reception of a direct line of sight signal sent from transmitter to receiver to obtain a relative position measurement between two radios.  
      The invention uses a backscattered signal for location, i.e. a signal that is transmitted from the radio station whose position is to be measured. The invention has realised that this is more reliable since the use of a signal that is transmitted from a remote transmitter might be blocked or affected by intervening walls or other objects.  
      The predetermined features may be the amplitude, phase and delay of components of the transmitted signal received at the receiver. The components will correspond to reflections off a variety of walls, items of furniture and other items. It may not be necessary to store or measure the amplitude, phase and delay of each of the components. Instead, only the data for the more significant components need to be stored. During the measurement step, only the more significant components then need to be measured. The more significant data may be the data relating to the strongest signals.  
      The number of components that need to be stored for each area may be predetermined to be a value sufficient to distinguish between the various areas. One component is generally not enough, so a predetermined plurality of components needs to be treated. For example, the number of components measured and the number of components stored may be five or greater, preferably ten or greater.  
      In alternative embodiments, the predetermined features may be the received power of the received signal as a function of time, the power delay profile. This method can avoid the need for software in the receiving device to calculate the amplitude of the components; such software can be complicated and requires significant processing power which may not be convenient or available in small or portable devices.  
      The invention is applicable in a number of scenarios.  
      The invention is particularly applicable to systems having a pair of radio stations in communication with another. In this case, in preferred embodiments, after locating the area that gives the best match, one or both of the stations transmit its location to the other station as an information signal. This can use the same frequency or frequency band as the location signal—indeed, the signal can even be used as a location signal.  
      Thus, instead of just obtaining a relative measurement of the positions of the two radios, their absolute measurements are determined.  
      In embodiments, the frequency band used for the transmission of the information signal is a lower frequency band than that of the location signal, which is less likely to be absorbed by materials other than metal reflectors.  
      Preferably, the method also includes analysing the received radio signal to determine the objects in the vicinity of the receiver.  
      In embodiments, the receiver has multiple antennas and the back-scattered signal not only measures the reflectivity and distance of local objects but also their size and shape, and compares this with the size shape and reflectivity of typical indoor objects.  
      In preferred embodiments, the user locates the radio station close to various objects in the indoor environment. A signal is transmitted, and the reflectivity, size and shape information is measured for each of the objects. The user inputs the name of the object. In this way, a database of objects, their names and their reflectivity patterns is built up.  
      The system can then match the observed signal with the parameters to enable the closest local objects to be determined.  
      In alternative embodiments, predetermined expected parameters are stored for typical objects. The transmitter sends out a signal and the resulting received signal is compared with that expected for a plurality of typical objects to find the best match.  
      In another aspect, the invention relates to a computer program arranged to cause a radio station to carry out a method as set out above.  
      In a further aspect, the invention relates to a radio station comprising: at least one antenna; a transceiver; a processor; and a memory storing a parameter database including expected signal parameters of backscattered signals as a function of position within the building; and providing an object database including expected signal parameters of backscattered signals from a plurality of objects, wherein the memory includes code arranged to cause the radio station: to transmit a location signal from the transmitter so that it undergoes multipath reflection before being received at the receiver as a received signal; to measure predetermined features of the received signal at the receiver; to compare the predetermined features of the received signal with the stored data in the parameter database to find the best match and accordingly the position of the radio station; to identify differences between the predetermined features of the received signal and that expected from the stored data in the parameter database; and to compare the differences with the stored data in the object database to find any good matches and accordingly to identify objects located in the vicinity of the radio station.  
      Preferably the radio station has a plurality of antennas for transmitting simultaneously multiple radio signals.  
      The invention also relates to a radio system comprising a plurality of such radio stations arranged to communicate with one another. 
    
    
      For a better understanding of the invention, embodiments will now be described, purely by way of example, with reference to the accompanying drawings, in which:  
       FIG. 1  shows a system according to a first embodiment of the invention;  
       FIG. 2  shows a plan of a building in which the system of  FIG. 1  is being used;  
       FIG. 3  shows a plan of part of the building of  FIG. 2 ; and  
       FIG. 4  is a flow chart of the operation of the embodiment of  FIG. 1 . 
    
    
      A system according to a first embodiment has a first radio station  10  ( FIG. 1 ) with a transceiver  12 , a processor  14  and a memory  16  as well as multiple antennas  18 . The system also has a second radio station  20  with a transceiver  22 , controller  24 , memory  26  and multiple antennas  28 . Both the first and second radio stations are portable.  
      Each of the first and second radio stations contains code  30  stored in memory  16 , 26  for causing the radio stations to carry out the steps set out below. The code  30  includes a ray-tracing simulator  32  for building up a parameter database  36  and an operation controller  34  for controlling operation of the radio stations.  
      In use, ( FIGS. 2, 3  and  4 ) the building plans, typical reflectivity of the building materials and details of the type of radio signal to be sent are passed to a ray-tracing simulator  32  (step  40 ). Next, the ray-tracing simulator  32  calculates (step  42 ) the expected received signal for a signal transmitted from the same radio station in each of a number of bins, i.e. areas  4 , of building  2 . That is to say, the amplitude, phase and delay of backscattered signal components  8  reflected from the signal  6  are calculated.  
      Although the diagram shows a grid similar in size to the rooms, for clarity, a real grid may be on a much finer scale to allow more precise location. For example, the grid may divide the building into square or rectangular areas with sides in the range 0.1 m to 2 m, preferably 0.5 m to 1 m. Square grids may be most convenient in many situations. The simulator determines the amplitude, phase and delay of each expected reflected signal component returning to the radio receiver after being reflected off corresponding reflectors.  
      The calculation and storage steps are then repeated for each area  4  of the building to build up the complete parameter database  36 .  
      The results of the calculations are then input into the first and second radio stations and stored as part of the parameter database  36  for that area  4  (step  46 ). In the specific embodiment described, information regarding the ten most significant (i.e. strongest) signal components  8  are stored, though this number may be varied as required.  
      After these preparation steps, and other preparation steps described below, the radio station  10 ,  20  sends out (step  54 ) a location signal  6 . This is scattered in the real building and reflected back-scattered components  8  are received back at the radio station  10  and picked up by the antenna  18 ,  28  (step  56 ), called a received signal.  
      Next (step  57 ) the radio station  10 ,  20  calculates the amplitude phase and delay of the received back-scattered components  8 . This calculation may be done in any of a number of ways, for example using a maximum likelihood estimate. The amplitude, phase and delay of the back-scattered components  8  of the received signal are then compared (step  58 ) with the calculated values stored in the parameter database  36  to determine the best match. The area  4  corresponding to the best match is then taken to be the area  4  in which the radio station  10 ,  20  is located.  
      As a result of this procedure being carried out in both radio stations  10 , 20 , each knows its own location.  
      One or both of the radio stations  10 , 20  can then send (step  60 ) information regarding its own location to the other. In the first embodiment, a longer wavelength signal is used to transmit this information than that used for position determination, since a longer wavelength signal is less susceptible to being absorbed by materials, other than metal reflectors, preventing any transmission of the line of sight signal.  
      The radio stations  10 ,  20  are also able to build up an object database  37 . To build up the object database  37 , the radio station  10 ,  20  is brought adjacent to an object and transmits a signal through the multiple antennas (step  48 ). This is then reflected off the object and a reflected signal received (step  50 ). The use of multiple antennas allows the reflected signal to represent not merely the reflectivity and distance of the object but also its size and shape. The user is prompted (step  51 ) to input the object name, and this is stored (step  52 ) in the object database together with the reflectivity size and shape information. Steps  48  to  52  are then repeated (step  53 ) to build up an object database  37  with information regarding multiple objects.  
      The information is then used after the room information is determined to locate adjacent objects. The received signals received in step  56  are analysed or a best fit to adjacent objects.  
      In a preferred arrangement, the features of the received signals are compared with those stored as the parameter data of the area that gives the best match. The differences will generally be caused by reflections of objects not in the building plan. Accordingly, the method includes (step  66 ) determining the differences between the features of the received signals with the features stored in the parameter database corresponding to the best match of the received signals with the parameter database, and then comparing (step  68 ) the differences with the objects stored in the object database to determine the size shape and distance to one or more nearby objects.  
      The name of the best fit object can then be output (step  70 ).  
      In a concrete example, the first radio station  10  can be a mobile telephone and the second radio station  20  can be a set of door keys equipped with a transceiver key fob. If the keys become lost, a signal can be sent from the mobile telephone  10  to the door keys  20  to cause the door keys to operate the procedure above to locate local objects. This may determine, for example, that the door keys are in the bedroom 1 m from a table  80  and 2 m from a table lamp  82 . This information can be transmitted to the mobile telephone and displayed to allow the user of the mobile telephone to find the door keys more easily.  
      The differences between the calculated and measured data gives information about differences between the real environment and that in the building plans input at the start of the process to calculate the expected signals received. Thus, the differences and information about local objects can be stored in a map database  39  (step  72 ). The map database can then be used, for example, to determine both the room containing the door keys and the location of the door keys with respect to the objects in the room.  
      The differences caused by moving objects such as people should in general not be included in the map database  39 . This can be achieved by checking for motion of a particular reflector and not including data from moving reflectors in the map database. Alternatively, reflectors having a reflectivity and permitivity corresponding to humans or animals can be rejected.  
      In a modification of the first embodiment, the object database is not built up experimentally but simply stored in the radio stations. Typical objects such as tables, chairs and floors can simply be included with typical parameters, or alternatively or additionally more specific objects known to be in the local environment can be included.  
      In a second embodiment, instead of the amplitude, phase and delay of the reflected signal components being measured, the backscattered signal strength of the received signal as a function of time is measured. Therefore, in this embodiment, the calculation and storage steps  42 , 44  calculate the expected backscattered signal power as a function of time. The step of finding the best match then fits the received signal to the expected reflected signal power to find the best fit and hence the location of the radio station.  
      In a third embodiment, the first radio station  10  is a static radio station at a known position. The second radio station  20  is a mobile station that obtains information about its location and objects in its vicinity and sends the information back to the first radio station  10 .  
      Although the preferred embodiments use radio stations  10 ,  20  with multiple antennas the invention is also applicable to radio stations  10 ,  20  with single antennas. It is more difficult to determine the size and shape of objects but this may not be necessary in all applications. One way of obtaining more information using just a single antenna is to send radio signals of different frequencies. As will be appreciated by the skilled person, this approach can also be used with multiple antennas.  
      The invention can also be used outdoors as well as indoors, especially where the outdoor environment is well mapped.  
      The invention may have applications for games played using mobile radio transmitters that can use information about the location and velocity of the player to provide information to a game server and to the player.  
      In the present specification and claims the word “a” or “an” preceding an element does not exclude the presence of a plurality of such elements. Further, the word “comprising” does not exclude the presence of other elements or steps than those listed.  
      From reading the present disclosure, other modifications will be apparent to persons skilled in the art. Such modifications may involve other features which are already known in the art of positioning and the art of radio and which may be used instead of or in addition to features already described herein.