SEVAK ZANKAR UPENDRAKUMAR (GB)
ARSLAN TUGHRUL SATI (GB)
US20110143770A1 | 2011-06-16 | |||
CN101620270A | 2010-01-06 |
Claims 1 . A method of estimating the position of a user device, the method comprising: receiving signal source data from a plurality of electromagnetic signal sources having known locations; dividing the plurality of electromagnetic signal sources into a plurality of groups of the signal sources; processing the received signal source data to generate group position data representing the position of at least one group location, each group location being characteristic of the location of a respective group of the signal sources; and processing the group position data to generate position data representing an estimate of the position of the user device; and outputting the position data. 2. A method according to Claim 1 , wherein the group position data represents the position of a plurality of group locations, each group location being characteristic of the location of a respective group of the signal sources. 3. A method according to Claim 2, wherein the plurality of electromagnetic signal sources is divided into groups such that the distribution of the plurality of group locations is generally more uniform than the distribution of the plurality of electromagnetic signal sources. 4. A method according to any one preceding claim, wherein at least one group location is substantially equivalent to the location of an electromagnetic signal source in the respective group. 5. A method according to any one preceding claim, wherein at least one group location is derived from the locations of a plurality of the electromagnetic signal sources in the respective group. 6. A method according to any preceding claim, further comprising selecting said at least one group location by accessing stored group data, and selecting said at least one group location from the stored group data. 7. A method according to any one of Claims 1 to 5, further comprising generating said at least one group location in dependence on the received signal data. 8. A method according to Claim 7, wherein generating said at least one group location comprises selecting a datum point and wherein the plurality of signal sources are divided into groups with respect to the datum point. 9. A method according to Claim 8, wherein the plurality of signal sources is divided into groups by at least one dividing line passing through the datum point. 10. A method according to Claim 8 or 9, wherein the plurality of signal sources are divided into groups by a plurality of dividing lines extending radially from the datum point. 1 1 . A method according to any one of Claims 8 to 10, further comprising selecting the datum point in dependence on user input. 12. A method according to any one of Claims 8 to 1 1 , further comprising receiving further signal data from a further device in the vicinity of the user device, determining the position of the further device in dependence on the further signal data, and selecting the datum point in dependence on the determined position of the further device. 13. A method according to any preceding claim, wherein at least one group of signal sources has a plurality of group locations associated with it. 14. A method according to any preceding claim, further comprising receiving signal source position data representing the position of each of the plurality of electromagnetic signal sources. 15. A method according to Claim 14, further comprising assessing the validity of the positions of each of the plurality of electromagnetic signal sources, and disregarding any signal sources which are considered invalid. 16. A method according to any preceding claim, wherein processing the group position data to generate position data further comprises generating position accuracy data representing an estimate of the accuracy of the position estimate of the user device. 17. A method according to Claim 16, wherein processing the received signal data to generate group position data further comprises generating group position accuracy data representing an estimate of the accuracy of the group position data, and wherein the position accuracy data is generated in dependence on the group position accuracy data. 18. A method of estimating the position of an electromagnetic signal source, the method comprising: receiving signal data from the electromagnetic signal source at a plurality of reference locations; dividing the plurality of reference locations into a plurality of groups of the reference locations; processing the received signal data to generate group position data representing the position of at least one group location, each group location being characteristic of the location of a respective group of the reference locations; and processing the group position data to generate position data representing an estimate of the position of the electromagnetic signal source; and outputting the position data. 19. A method according to Claim 18, wherein the group position data represents the position of a plurality of group locations, each group location being characteristic of the location of a respective group of the reference locations. 20. A method according to Claim 18 or 19, wherein the plurality of reference locations is divided into groups such that the distribution of the plurality of group locations is generally more uniform than the distribution of the plurality of reference locations. 21 . A method according to any one of Claims 18 to 20, wherein at least one group location is substantially equivalent to the location of a reference location in the respective group. 22. A method according to any one of claims 18 to 21 , wherein at least one group location is derived from the locations of a plurality of the reference locations in the respective group. 23. A method according to any one of claims 18 to 22, wherein selecting a plurality of group locations comprises accessing stored group data, and selecting the plurality of group locations from the stored group data. 24. A method according to any one of Claims 18 to 22, wherein selecting a plurality of group locations comprises generating the plurality of group locations in dependence on the received signal data. 25. A method according to Claim 24, wherein generating the plurality of group locations comprises selecting a datum point and wherein the plurality of reference locations are divided into groups with respect to the datum point. 26. A method according to Claim 25, wherein the plurality of reference locations is divided into groups by at least one dividing line passing through the datum point. 27. A method according to Claim 25 or Claim 26, wherein the plurality of reference locations are divided into groups by a plurality of dividing lines extending radially from the datum point. 28. A method according to any one of Claims 25 to 27, further comprising selecting the datum point in dependence on user input. 29. A method according to any one of Claims 25 to 27, further comprising receiving further signal data from a further device in the vicinity of the electromagnetic signals source, determining the position of the further device in dependence on the further signal data, and selecting the datum point in dependence on the determined position of the further device. 30. A method according to any one of claims 18 to 29, wherein at least one group of reference locations has a plurality of group locations associated with it. 31 . A method according to any one of claims 18 to 30, further comprising receiving reference location data representing the position of each of the plurality of group locations. 32. A method according to Claim 31 , further comprising assessing the validity of the positions of each of the plurality of reference locations, and disregarding any signal sources which are considered invalid. 33. A method according to any one of claims 18 to 32, wherein processing the group position data to generate position data further comprises generating position accuracy data representing an estimate of the accuracy of the position estimate of the electromagnetic signal source. 34. A method according to Claim 33, wherein processing the received signal data to generate group position data further comprises generating group position accuracy data representing an estimate of the accuracy of the group position data, and wherein the position accuracy data is generated in dependence on the group position accuracy data. 35. A user device comprising a processor, an electromagnetic signal receiver, and a memory containing computer program code that, when executed by the processor in conjunction with the electromagnetic signal receiver, causes the user device to carry out a method according to any one of Claims 1 to 18. 36. A user device according to Claim 35, wherein the memory further comprises a database containing the known positions of the plurality of electromagnetic signal sources. 37. A computing device comprising a processor and a memory storing computer program code that, when executed by the processor, causes the computing device to carry out a method according to any one of claims 19 to 34. 38. A computing device according to claim 37, wherein the memory further comprises a database of the known positions of the plurality of reference locations. 39. A computer readable medium tangibly embodying computer program code for causing a computer to carry out a method as claimed in any one of Claims 1 to 34. 40. A method substantially as herein described with reference to Figures 2 to 12. 41 . Apparatus substantially as herein described with reference to Figures 2 to 12. |
PtGtGr And and in decibels form as: G.» = 201og(— ) (3)
And The free space model (equations) cannot easily be applied in real world environments without modifications because of the signal propagation uncertainties. Wi-Fi signal propagation can be affected by many factors such as signal attenuations and reflections (multipath effects) from the surfaces, building types, moving objects and people, transmission frequency, antenna heights and polarisation, and so on. However, various models exist to try to model different environments and signal propagation behaviour through them to determine the distance between receiver and source. For example, there are models available to predict signal behaviour for different indoor environments. One of the indoor models is described by the following equation: PGdB = 20log(-^—) + 10n log(do) + Xa for d > d 0 (4)
Ando Where X, n and d 0 are the parameters which vary with different indoor environments and which can be determined empirically. For example, the values of X, n and d 0 for a typical hard partitioned office environment are 7.0, 3.0 and 100 respectively. User input can be provided to select types of environment and then to use specific values of the abovementioned parameters stored in memory (that were for example previous input by the user or other operator). Alternatively, if user inputs are not available default values can be chosen from the software configuration. There are also models available for outdoor environments for example. One such model, designated as Stanford University Interim (SUI) Model, is described by the following equation: Z = 201og(-^¾ + 10rc log(— ) + X f + Xh + s for d > d 0 (5) λ do PL is described as path loss and other parameters can be processed similarly as described in for indoor models, that is (for example) either through user inputs or from software configuration. Once all the distances are determined using any of the models available, they are used to generate an estimate of the position of the user device. Depending on the number of measurements made, various methods are available to form the estimate. One method, triangulation, is described below with reference to Figure 3. Figure 3 is an illustration of position estimation by triangulation. A first 302, second 304 and third 306 signal source are shown, each having a known location that has previously been recorded, for example by 'war walking' with a GPS enabled device, or similar. The distances d-i , d 2 and d 3 have been estimated using a suitable method as aforementioned, and an appropriate algorithm selects the most probable intersection 308 of the three lengths, and hence the estimated user location. Due to estimation errors in previous steps, the likely user location 308 is subject to a degree of uncertainty. An appropriate algorithm can be used to select the most suitable estimate. Figure 4 is an illustration of a user device for use with the system of Figure 2. The user device 400 includes a processor 402, a Wi-Fi interface 404, a user interface (such as a keyboard and/or touch screen), data storage 408 (including program storage), a network interface 410 (such as a radio for use with a mobile phone network), and a display 412. Depending on the type of device, the network interface 410 or other components of the device may for example be omitted. Further features may of course be provided that are not shown, including further devices and/or interfaces. Figure 5 is an overview of a system for locating a user device, operable with the system of Figure 2. In Figure 5 a user device 500 (such as the user device described above or any other device, for example), a telecommunications network (such as a mobile telephone network) 502, a location server 504 and a WAP location database 506 (which may be integrated with the location server 504) are shown. In use, a user causes the user device 500 to send a location request 550 to the telecommunications network 502 (for example using a service on a mobile telephone). The request 550 typically includes data received at the user device 500, such as properties of signals detected from nearby WAPs. The request 550 may thus, for example, include details of the signal strengths of nearby WAPs and MAC addresses (and/or cell tower signals, and so on). A request 552 (usually the same as the initial request 550) passes from the network 502 to the location server 504. The location server 504 then processes the request 552 and in so doing interrogates the location database 506 with a WAP lookup request 554, to specify WAP data that is relevant to the location request 552. The database 506 then returns the requested data 556 to the server 504. The server finishes processing the data 556 in conjunction with the received request data 552 to produce a location estimate which is sent back to the user device 500 in the form of location data 558. The network forwards location data 560 (usually the same as the data 558) to the user device 500. The user device can then process the location data 560 to retrieve (and for example display) the location estimate. In another embodiment, some or all of the components of the system shown in Figure 5 are provided locally at the user device. Thus the network 502 and any use thereof is not obligatory, for example. As is mentioned above, the positioning system divides the detected signal sources into a number of groups. This is to simplify aspects of the processing, and to create a more uniform distribution of measured points (relative to measuring the locations of all individual WAPs, which are often disposed in tight clusters). Any number of different methods can be used to divide the WAPs (or other signal sources) into different groups, and generally such methods are effective providing that they generally achieve the same aim (a greater uniformity of distribution of the points which are being measured). In some cases it is appropriate to use a number of different methods at the same time. Two methods will now be described which make use of a 'pilot point', which is effectively a datum point that lies at the centre of the various arrangements of the groups. Figure 6 is an illustration of a first method of dividing a plurality of signal sources into different groups, for use with the system of Figure 2. In Figure 6, various buildings are illustrated schematically by cross-hatching, and a number of WAPs are indicated with the letter 'W. A pilot point P 600 is shown, as well as an indication of the actual location of the user device UD 602. In this method, horizontal and vertical dividing lines (dashed) intersect at the pilot point 600 and divide the map into four quadrants, forming four distinct groups d, G 2 , G 3 , G 4 . Since processing is typically carried out using Cartesian coordinates, this method has the benefit of great simplicity and ease and speed of processing to determine the group to which a particular WAP belongs. It will be appreciated that the pilot point 600 does not (necessarily) coincide with the location of the user device 602. The pilot point 600 is essentially a virtual point which is chosen to ensure a relatively uniform distribution of WAPs around the point. Conveniently it may be chosen (for example) as the mean or median of the coordinates of all of the detected WAPs. Figure 7 is an illustration of a second method of dividing a plurality of signal sources into different groups, for use with the system of Figure 2. In this method, the pilot point P 700 is chosen as before, and the location of the user device UD 702 is shown for completeness. The buildings and WAPs are present as before. This time, a number of lines are projected radially outward from the pilot point 700 so as to define a number (in this case, 5) of sectors, forming groups Gi, G 2 , G 3 , G 4 , G 5 . The angles subtended by the radial dividing lines can be chosen to maximise the uniformity of the distribution of WAPs in different groups, for example. Figure 8 is an illustration of a method of eliminating invalid signal sources, for use with the system of Figure 2. This can further refine the position estimate. Again the pilot point P 800 and the user device UD 802 are shown, as well as the various WAPs W. In practice there is a maximum radius R relative to the wireless receiver (in the user device 802) out to which Wi-Fi signals can reliably be received. For example the maximum practical travel distance for Wi-Fi signals is 300m. There may exist WAP devices 804, 806 which lie outside this distance and which should ideally not contribute to the position estimate, because they appear to be anomalous (invalid) readings. Accordingly, as part of the location process, each of the WAP locations is assessed to see if it is outside the expected radius (or other metric) and discarded if so. Figure 9 is an illustration of the selection of leader points for the groups shown in Figure 7. As mentioned earlier, each group selected in previous steps has a leader point associated with it. This leader point may either be a selected one of the WAPs in the group (for example, the WAP with the strongest signal, greatest availability, or least interference, and so on), or a 'virtual leader point' derived from the location of multiple WAPs in the group (some or all). As before the pilot point 900 and user device 902 are shown. In addition various leader points 910, 912, 914, 916, 918 corresponding to the groups Gi, G 2 , G 3 , G 4 , G 5 are shown. Leader points 912, 914, 918 are the 'simple' type, and are merely the locations of single, 'preferred' WAPs within the relevant groups. Leader points 910, 916, however, are the 'virtual' type, and are defined in relation to various of the WAPs in the respective groups. A number of methods can be used to derive the virtual leader points but typically they will be derived from the mean or median coordinates of some or all of the WAPs in the respective group. The choice of whether to assign a 'real' or 'virtual' leader point to a particular group can be determined in accordance with the particular circumstances. For example, if there is a WAP in a group with clearly superior signal properties, it may make sense to use that as the leader point. In another instance, there may be a dense cluster of similar WAPs with widely varying propagation effects. In this case it may make more sense to use a virtual leader point derived from the mean of the measured coordinates of the individual WAPs, or using an algorithm such as the weighted centroid algorithm (see below). In variants, more than one leader point may be assigned to each group. In one configuration this provides additional points for use in the computation of the position estimate. In another configuration, the extra leader points are provided as a back up only in case the preferred leader point is not usable. Figure 10 is a very simple illustration of the application of a weighted centroid algorithm to signal sources in the system of Figure 2. This is an algorithm that can be used to derive a virtual leader point as described above. Three circles 1000, 1002, 1004 correspond to three WAPs having a particular RSSI , which dictates the size of the relevant circle. The weighted average 1006 derived from this algorithm is shown. A further feature of the positioning system is providing an indicator (a quality index, Ql) of the accuracy of the position estimate. As is mentioned above, an important factor in the quality of the estimate is the uniformity of the distribution of WAPs around the user device. The quality index (Ql) is computed first for each leader point, and these results are then combined to provide an overall Ql associated with the final position estimate. The importance of the Ql parameter appears clearly when storing the virtual calculated reference points, for each group or section, in a database for future use. As each virtual reference point has been calculated to describe the characteristics of all the reference points in the section or group, we should be able to tell the quality of this calculation before using it in the future. Figure 1 1 is an illustration of the calculation of a quality index for a leader point 1 100 in a group as may be used in the system of Figure 2. The calculation process of the Quality Index (Ql) is a combination of few parameters describing the signals characteristics and distribution in the target group. To estimate the Ql value we have included the following parameters: N: number of valid reference points in the group or section.
R: the median RSSI for all reference points in the group.
C: the coverage of the reference points around the group leader.
V: the variance RSSI for each section around the leader point Although there are different possible combinations of the above mentioned parameters in calculating Ql value, the following example is the currently preferred formula:
QI= C - RX N
∑ Vi (6) Where Vi is the Variance RSSI for the section (i). The positioning process may also include creating a database record for the Ql associated with each leader point. This record maintains the above mentioned parameters in the database in order to assist with future readings (reference points) in the associated group. Figure 12 is a flowchart illustrating the operation of the system of Figure 2. The process begins in step S1200. In step S1202 the user device carries out a scan of the electromagnetic signal sources in the vicinity, recording for example their unique identifiers and received signal strength (RSS). Depending on whether or not dynamic grouping is used (step S1204), either a pilot point is selected (step S1206) and the signal sources divided dynamically into different groups (step S1208), if so, or the static grouping data is retrieved from a database (step S1210), if not. In step S1212 a leader point is selected for each group. Where necessary, calculations are carried out in respect of the positions of virtual leader points (step S1214), and all of the leader point positions are then processed (step S1216) to generate a final estimate of the position of the user device. The process then ends (step S1218). The process described above allows the location of a user device with reference to known signal sources, but it will be appreciated that the same process with appropriate modifications can be used to estimate the position of a static signal source. Locating such signal sources is an essential process to enable position requests for any area. This process is called the calibration process. Usually the calibration is started by collecting transmitted signal measurements from a plurality of different reference locations. Then, to locate the signal source, the collected measurements (including signal characteristics and location information data) are processed. The signal measurements in a plurality of known locations can be considered as reference points with a known position. The reference points are divided into groups depending on the geographical location using an equivalent process to those described above. In one example a Wi-Fi transmitter can be 'mapped' by walking around with a GPS- and Wi-Fi-enabled mobile phone. During the calibration the mobile phone collects the Wi-Fi signals at a predefined rate, creating reference points. Each reference point contains the Latitude/Longitude position as received from the GPS module with the Wi-Fi signal characteristics data received from the specific transmitter. The subsequent process includes: Calculating a pilot point.
Dividing the measured points into four groups depending on
Latitude/Longitude values.
Validating the reference points in each group
Selecting the leader point and the alternative point for each group
Calculating the transmitter position. The major difference between this approach to locate signal transmitters and the method of estimating the position of a user device is the requirement to store some data. As the transmitters' locations are used as reference points to locate mobile devices, it is preferable to store any available information about these transmitters. The location information and the unique ID of a transmitter are usually enough for the normal positioning system. Although some systems based on fingerprinting store huge amount of calibration data, the modern indoor positioning theory aims to minimise the calibration efforts and data. The aim behind this is to make the indoor positioning system perform globally with reasonable efforts and resources. Storing all the available calibration data for a geographical location will be useful to filter the transmitter position when new calibration data is received frequently. But it will also consume more storage space, data processing time and data transmission power. Therefore, the dividing method gives the ability to store only the virtual leader reference point for each group. Each leader point is considered as a group representative and would be sufficient to allow filtering to be carried out in respect of future updates. Predominantly the wireless standard described in this document is Wi-Fi and the positioning system is a Wi-Fi-based system, but this method can equally be applied to other related standards such as Bluetooth and radio-frequency (RF) and other systems. Furthermore this method can also be applied in determining the location of base stations in other communication technologies such as mobile communication (such as GSM and CDMA for example), Wi-Max and so on. It will be appreciated that other applications of the position location system described above are of course possible, for example including location systems that are entirely local to a user device (for example including all relevant data and processing power in the user device), and devices that communicate via a variety of various different networks (not limited to one or to a telecommunications network, for example). It will also be appreciated that the positioning method described above can be combined with other positioning methods fully or in part such that, for example, only a portion of the groups of signal sources (or even only one group) may have a corresponding leader point selected or generated as the case may be. In some cases a calculation may be performed in respect of only selected groups at first, and the calculation may cease if a sufficiently accurate result is obtained at that stage, for example. In summary, a method has been described of determining position co-ordinates of Wireless Access Points (WAPs) in Wireless Local Area Networks (WLANs) using a multiphase self correcting mapping process. The WAPs are typically Wi-Fi Access Points in respective WLANs, but they may be other WAPs of another Wi-Fi based position system. The method and system may be implemented fully on a consumer mobile device, for example, or may rely on remote components and software (such as a central server connected via some form of communications network, such as a Wi-Fi, mobile telephone or other network) to achieve the same aims. Although the present invention has been described above with reference to specific embodiments, it will be apparent to a skilled person in the art that modifications lie within the spirit and scope of the present invention.