Locating electromagnetic signal sources

Abstract

There is disclosed a method of estimating the location of a plurality of electromagnetic signal sources, comprising: scanning at a first plurality of locations to generate signal source position data, the signal source position data representing estimates of the position of at least one of said signal sources; scanning at a second plurality of locations using a signal detection system to generate signal detection data, the signal detection data relating to signals received at the second plurality of locations from the signal sources; processing the signal source position data in dependence on the signal detection data to correct estimation errors in the signal source position data; and outputting the processed signal source position data.

Claims

1. A method of estimating the location of a plurality of electromagnetic signal sources, comprising: scanning at a first plurality of locations to generate signal source position data, the signal sources being wireless access points, radio transmitters and/or wireless beacons, the signal source position data representing estimates of the position of one or more said signal sources; scanning at a second plurality of locations using a signal detection system to generate signal detection data, the signal detection data relating to signals received at the second plurality of locations from the signal sources; at least part of the scanning being carried out using a vehicle-mounted device, a mobile phone or other hand-held portable device; processing the signal source position data in dependence on the signal detection data to correct estimation errors in the signal source position data; and outputting the processed signal source position data; storing the processed signal source position data; receiving a user location request from a user device, the user location request including data obtained from a signal detection system associated with the user device; processing the stored signal source position data in dependence on the user location request data to generate user location data representing an estimate of the location of the user device; and outputting the user location data.

2. A method according to claim 1, wherein processing the signal source position data further comprises using the signal detection data to estimate the position of the second plurality of locations.

3. A method according to claim 1, further comprising receiving location information data representing information about the second plurality of locations, and wherein processing the signal source position data further comprises using the location information data to estimate the position of the second plurality of locations.

4. A method according to claim 3, wherein the location information data comprises a user estimate of the position of at least one of said second plurality of locations.

5. A method according to claim 4, further comprising inputting the location information data via a user input device.

6. A method according to claim 1, wherein processing the signal source position data further comprises processing the signal detection data in accordance with an environmental model representing environmental factors applying to the signal sources.

7. A method according to claim 6, further comprising receiving at least one of environmental model selection data representing a choice of environmental model and environmental model parameter data representing a choice of at least one parameter of the environmental model, and processing the signal detection data in accordance with said at least one of the environmental model selection data and the environmental model parameter data.

8. A method according to claim 7, further comprising inputting said at least one of environmental model selection data and environmental model parameter data via a user input device.

9. A method according to claim 1, wherein processing the signal source position data further comprises generating further signal source position data representing new estimates of the signal sources in dependence on the signal detection data.

10. A method according to claim 9, further comprising processing the signal source position data and the further signal source position data to determine an appropriate adjustment to the signal source position data.

11. A method according to claim 1, further comprising processing the signal detection data to estimate the location of additional signal sources that were not detected at the first plurality of locations, and adding additional signal source position data to the signal source position data.

12. A method according to claim 1, wherein scanning at the first plurality of locations comprises: scanning at the first plurality of locations to generate initial signal detection data, the initial signal detection data relating to signals received at the first plurality of locations from the signal sources; processing the initial signal detection data in dependence on first scanning position data, the first scanning position data representing the position of each of the first plurality of locations, in order to generate the position estimate data.

13. A method according to claim 12, wherein scanning at the first plurality of locations comprises using the signal detection system to generate the initial signal detection data.

14. A method according to claim 1, further comprising using a positioning system at each of the first plurality of locations to generate the first scanning position data.

15. A method according to claim 14, wherein the positioning system is generally more effective at the first plurality of locations than at the second plurality of locations.

16. A method according to claim 14, wherein the signal detection system is generally more effective at the second plurality of locations than at the first plurality of locations.

17. A method according to claim 1, further comprising scanning using a signal detection system at a further plurality of locations to generate further signal detection data, and further processing the signal source position data in dependence on the further signal detection data.

18. A method according to claim 1, further comprising processing the signal source position data to generate map data representing a map of the signal sources.

19. A method according to claim 1, wherein the signal source is a wireless access point, such as a base station in a wireless communications network.

20. A method according to claim 19, in which at least one of the signal detection data, the signal source position data and the processed signal source position data is transmitted via the wireless access point.

21. A method according to claim 1, wherein at least part of the scanning is carried out using a hand-held portable device.

22. A method according to claim 1, wherein at least part of the scanning is carried out using a vehicle-mounted portable device.

23. A method according to claim 1, wherein the scanning is carried out by a user travelling between a plurality of locations.

24. A non-transitory computer readable medium tangibly embodying computer program code for causing a computer to carry out a method as claimed in claim 1.

25. A portable unit programmed with computer program code for causing the portable unit to carry out a method as claimed in claim 1.

26. A method according to claim 1, wherein the plurality of electromagnetic signal sources are wireless access points or wireless beacons.

27. A method according to claim 1, wherein the electromagnetic signal sources are stationary.

28. A method according to claim 1, wherein a second phase of scanning is repeated in order to further refine the accuracy of the positional estimates.

29. A method according to claim 28, wherein a further signal detection system is used at a further plurality of scanning locations to further improve the accuracy of the location estimates.

30. A method according to claim 29, wherein the further signal detection system is a user device operable to send a location request to a telecommunications network, including properties of signals detected from nearby signal sources, and to receive back location data which the user device then processes to retrieve and display an estimate of the location of the user device.

31. A method according to claim 29, wherein the further signal detection system is a smart phone with WiFi and GPS capability.

32. A method according to claim 28, comprising rescanning a site inside a building with more scanning locations.

33. A method according to claim 1, further comprising receiving data from one or more additional sensors which measure a parameter relating to movement, direction or altitude and taking the received data into account when estimating the position of the second plurality of locations.

34. A method according to claim 33, wherein the additional sensors are one or more of a magnetometer, an accelerometer and a barometer.

35. A method according to claim 1, wherein processing the signal source position data in dependence on the signal detection data comprises using a time of arrival, time difference of arrival or angle of arrival distance measurement algorithm.

36. A method of estimating the location of a plurality of electromagnetic signal sources, comprising: scanning at a first plurality of locations to generate signal source position data, the signal sources being wireless access points, radio transmitters and/or wireless beacons, the signal source position data representing estimates of the position of one or more said signal sources; scanning at a second plurality of locations using a signal detection system to generate signal detection data, the signal detection data relating to signals received at the second plurality of locations from the signal sources; at least part of the scanning being carried out using a vehicle-mounted device, a mobile phone or other hand-held portable device; processing the signal source position data in dependence on the signal detection data to correct estimation errors in the signal source position data; and outputting the processed signal source position data; wherein: a second phase of scanning is repeated in order to further refine the accuracy of the positional estimates; a further signal detection system is used at a further plurality of scanning locations to further improve the accuracy of the location estimates; and the further signal detection system is a user device operable to send a location request to a telecommunications network, including properties of signals detected from nearby signal sources, and to receive back location data which the user device then processes to retrieve and display an estimate of the location of the user device.

37. A method according to claim 36, wherein processing the signal source position data further comprises using the signal detection data to estimate the position of the second plurality of locations.

38. A method according to claim 36, further comprising receiving location information data representing information about the second plurality of locations, and wherein processing the signal source position data further comprises using the location information data to estimate the position of the second plurality of locations.

39. A method according to claim 36, wherein processing the signal source position data further comprises processing the signal detection data in accordance with an environmental model representing environmental factors applying to the signal sources.

40. A method according to claim 36, wherein processing the signal source position data further comprises generating further signal source position data representing new estimates of the signal sources in dependence on the signal detection data.

41. A method according to claim 36, further comprising processing the signal detection data to estimate the location of additional signal sources that were not detected at the first plurality of locations, and adding additional signal source position data to the signal source position data.

42. A method according to claim 36, wherein scanning at the first plurality of locations comprises: scanning at the first plurality of locations to generate initial signal detection data, the initial signal detection data relating to signals received at the first plurality of locations from the signal sources; processing the initial signal detection data in dependence on first scanning position data, the first scanning position data representing the position of each of the first plurality of locations, in order to generate the position estimate data.

43. A method according to claim 36, further comprising using a positioning system at each of the first plurality of locations to generate the first scanning position data.

44. A method according to claim 43, wherein the positioning system is generally more effective at the first plurality of locations than at the second plurality of locations.

45. A method according to claim 43, wherein the signal detection system is generally more effective at the second plurality of locations than at the first plurality of locations.

46. A method according to claim 36, further comprising processing the signal source position data to generate map data representing a map of the signal sources.

47. A method according to claim 36, wherein the signal source is a wireless access point, such as a base station in a wireless communications network.

48. A method according to claim 36, wherein the electromagnetic signal sources are stationary.

49. A method according to claim 36, further comprising receiving data from one or more additional sensors which measure a parameter relating to movement, direction or altitude and taking the received data into account when estimating the position of the second plurality of locations.

50. A method according to claim 49, wherein the additional sensors are one or more of a magnetometer, an accelerometer and a barometer.

51. A method according to claim 36, wherein processing the signal source position data in dependence on the signal detection data comprises using a time of arrival, time difference of arrival or angle of arrival distance measurement algorithm.

52. A method according to claim 37, wherein the further signal detection system is a smart phone with WiFi and GPS capability.

53. A method according to claim 37, comprising rescanning a site inside a building with more scanning locations.

Description

DESCRIPTION OF THE DRAWINGS

(1) An example embodiment of the present invention will now be illustrated with reference to the following Figures in which:

(2) FIG. 1 is an illustration in overview of a system for locating a user device using Wi-Fi wireless access point (WAP) signal sources;

(3) FIG. 2 is a flowchart illustrating a process for locating the position of wireless access points (WAPs) for use in the system of FIG. 1;

(4) FIG. 3 is an illustration of the first phase of scanning of a set of wireless access points (WAPs) in a building in accordance with the process of FIG. 2;

(5) FIG. 4 is an illustration of the estimated positions of the WAPs of FIG. 3 after the first phase of scanning in the process of FIG. 2;

(6) FIG. 5 is an illustration of the second phase of scanning of the set of wireless access points (WAPs) in the building of FIG. 3;

(7) FIG. 6 is an illustration of the estimated positions of the scanner during the second phase of scanning shown in FIG. 5;

(8) FIG. 7 is an illustration of the estimated positions of the WAPs of FIG. 3 after the second phase of scanning in the process of FIG. 5;

(9) FIG. 8 is an illustration of the process of triangulating the position of a wireless access point (WAP);

(10) FIG. 9 is a schematic illustration of a dedicated scanner system suitable for use with the first phase at least of the process of FIG. 2;

(11) FIG. 10 is a schematic illustration of a handheld unit suitable for use with the first and second phases of the process of FIG. 2; and

(12) FIG. 11 is an overview of a system for locating a user device using the data generated by the process of FIG. 2.

DETAILED DESCRIPTION OF AN EXAMPLE EMBODIMENT

(13) A method and system will be described for locating electromagnetic signal sources, with a particular (but not exclusive) application to a system for locating a user device by cross-referencing signals received at the user device with data previously gathered using the abovementioned method and system.

(14) In one particular embodiment a method is described in relation to dynamically determining the location (such as position co-ordinates) of Wireless Access Points (WAPs) or Wireless Beacons in wireless technology-based positioning systems. 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.

(15) In a Wi-Fi-based positioning system, the co-ordinates/location of WAPs are used together with other signal processing algorithms to estimate users' location in Wireless Local Area Networks (WLAN). Here, the users can be mobile or stationary within WLAN and have any device with inbuilt or external Wi-Fi capability. This device may also have a capability to connect to the Internet for exchanging parameters with central server, for example Wi-Fi system parameters such as Mac addresses, signal strength, their co-ordinates etc. One example is a user with a mobile phone using inbuilt Wi-Fi to connect to the Internet. Hence, in this positioning method, a user's location accuracy relies heavily on the accuracy of the known position of the WAPs in respective WLANs.

(16) War-driving and war-walking, described above, are some techniques for determining and/or mapping a WAP's position.

(17) FIG. 1 is an illustration in overview of an example system for locating a user device using Wi-Fi wireless access point (WAP) signal sources. A user device 102 is operated by a user (not shown) and contains a Wi-Fi adaptor (also not shown). A number of wireless access points (WAPs) 104, 106, 108, 110, 112 are located in the immediate vicinity of the user within two buildings 114, 116. Because of signal attenuation, transmission power limits and other factors, only WAPs 104, 106, 110, 112 can be detected by the Wi-Fi adaptor in the user device 102. The WAP 108 is not detected by the user device 102. A GSM (mobile telephone) mast 118 and others may also be present, and properties of these and other electromagnetic signal sources may also be measured and used in the location finding system.

(18) The user device 102 can measure certain characteristics of the signals, either in terms of the signal qualities such as signal strength, angle of incidence, and so on, or in terms of the data carried by the signal, such as the MAC address or other identifier associated with the transmitting WAP.

(19) The system processes various of the signal characteristics and compares the characteristics with data in a database. As is described in more detail below, the location system can use the stored data relating to some or all of the relevant WAPs 104, 106, 110, 112 to triangulate (or otherwise determine) the position of the user device 102 and hence also the user.

(20) A method and system will now be described in which the disadvantages of both war-driving and war-walking methods can be substantially overcome, using a multi-phase process and using dynamic and self-correcting recursive techniques to determine location co-ordinates of WAPs accurately inside buildings and in difficult environments (for example with many obstacles). To search and determine WAPs' location co-ordinates will be referred as scanning and mapping respectively here onwards.

(21) FIG. 2 is a flowchart illustrating a process for locating the position of wireless access points (WAPs) for use in the system of FIG. 1.

(22) In step S200, in a first phase of the process, signal sources (signals from the WAPs) are scanned at a first set of locations. Various scanning processes can be used, for example using a hand-held device such as a mobile telephone, smartphone or other device, and either outside or inside a building (in the present embodiment). In an alternative embodiment the first set of locations is formed from the path of a vehicle carrying out a war-driving procedure. As described above and below (for example in relation to FIG. 7), the data gathered during the scanning process is used to generate estimates of the positions of the signal sources (WAPs). These estimated positions are then stored (in step S202). In the first phase of scanning the positions of the WAPs are usually (but not necessarily) estimated by combining the output of a global or absolute positioning system such as GPS or AGPS with the result of a relative positioning system such as triangulation using WAP signal strengths (again described below in more detail). In another embodiment the first set of estimated positions may for example merely be drawn from a map or plan of the building or area in which the scanning takes place and entered by user directly using device's user interface in to the processing software. The term scanning may thus be interpreted quite broadly in such a case.

(23) In step S204, in a second phase of the process, signal sources (the WAP signals) are scanned again at a second set of locations. In a preferred embodiment the second set of locations is the path of a scanning operative generally within or amongst buildings that have been scanned at a distance by the war-driving in phase 1. In other embodiments the scanning is automated and may be carried out by the same or a differently configured war-driving set-up. The scanning locations may be chosen by an operative on the ground or determined in real-time or prior to the scanning operation as a result of an analysis of the results gathered in phase 1 (for example with reference to geographical and/or commercial data relating to the scanning environment and the buildings and other structures therein. The scanning results are recorded in step S206.

(24) As is described in more detail below, the user may also record their own estimate of the position of the second set of locations or may input a correction (where appropriate) to an automatically derived (by GPS, for example) estimate of the positions, and may also input a selection of environmental model to apply and/or parameters for use with such a model (as is discussed in more detail below). A user may also input data to enable or to enhance performance of a reference positioning system such as GPS assistance data (estimated position, time, ephemerides etc) for GPS.

(25) In step S208 the first set of estimated WAP locations (or locations of other signal source such as mobile telephone masts and so on) are processed and corrected using the results of the second phase of the scanning process. This process is described in more detail below. The corrected estimates are then output in step S210.

(26) In the first embodiment, the user or a group of users carrying out the mapping process have compact consumer devices (such as smart mobile phones, laptops and so on) or sophisticated electronic devices (such as a customised computing device, amplifiers, antennas etc) with Wi-Fi capability, and preferably other positioning system capability such as GPS/AGPS, cell tower based positioning, and so on. These devices may have additional sensors which could assist in positioning, for example, an accelerometer, magnetometer etc. These devices may also have the capability other than Wi-Fi to connect to the Internet such as through mobile Internet service provider gateways.

(27) Users may for example be equipped with Satsis proprietary software running on a consumer mobile device with or without any operating system and having a micro-controller, GPS/AGPS and Wi-Fi hardware capabilities. Essentially all of the scanning and mapping processes described herein including multiple phases of scanning can be carried out using software such as this using previously described hardware when needed. The chosen software may also be capable of using a user's input to record information about the area/places where scanning/mapping is being done, such as position co-ordinates, types of buildings, height information such as scanning floor etc., urban or rural place types and so on when needed.

(28) FIG. 3 is an illustration of the first phase of scanning of a set of wireless access points (WAPs) in a building in accordance with the process of FIG. 2.

(29) In FIG. 3 a building 300 contains six WAPs 302, 304, 306, 308, 310, 312. Nine scanning sites 320, 322, 324, 326, 328, 330, 332, 334, 336 are chosen around the perimeter of the building, although in practice this may be around fewer than all sides, and may for example only be along one or two sides of the building (depending on accessibility, for example). It will be appreciated that more or fewer WAPs may be found and more and less scans (and corresponding scanning locations) may be used, depending for example on the size of the building and the complexity of the environment.

(30) The WAPs (shown in circles) are placed in a typical building at different places. In the present embodiment a user described earlier with a consumer device such as smart phone with Wi-Fi and GPS/AGPS capability can scan this building from different places from outside (shown in a rectangular box) all around the building. At every place user records Wi-Fi scanning parameters such as signal strength, MAC addresses of visible WAPs, Signal Quality etc. and user's own position through GPS/AGPS. The user may also record other useful environment specific data from observation and/or prior knowledge such as height and type of building, numbers and types of physical signal obstructions close to the scanning place etc. The user may also record data from additional sensors on or in the device, if available, to assist in positioning. For example, they may record heading data received from a magnetometer, height information from a barometer etc.

(31) As stated earlier, any other position system or methods excluding GPS and its variants may also be used to locate user's position such as Cell Tower based triangulation, Inertial Sensors, User Position Inputs, GIS etc. or any Hybrid system combining these technologies.

(32) As can be seen from FIG. 3, many WAPs can be scanned from more than one place from outside. For example WAPs 302, 304 are scanned from three locations, WAPs 310, 312 are scanned from two locations, and WAP 308 is scanned from one location. WAP 306 is not scanned from any location because of its central location in the building and lack of visibility of the signals from the outer scanning locations.

(33) The records from the scanning process are processed together by software installed on the device using various signal processing algorithms to determine the distances between user location at different places and visible Wireless Access Points, and subsequently to create a map of these WAPs.

(34) A number of distance measurements algorithms exist to allow positioning using a Wi-Fi or other comparable system. The algorithms include, for example, Time of Arrival (TOA), Time Difference of Arrival (TDOA), Angle of Arrival (AOA), Received Signal Strength (RSS), and so on. Depending on the technical capabilities of the software, mobile devices and WAPs, the RSS based distance measurement algorithm is normally employed but the other algorithms may also be used as appropriate.

(35) In the RSS algorithm, the strength (power) of a Wi-Fi signal at the receiver (user) is measured in comparison to the transmitted strength of a signal from the radio source (WAP) and is given by following mathematical equation in free space:

(36) $\begin{array}{cc}{P}_r=\frac{P_t{G}_t{G}_r{}^2}{{\left(4\right)}^2{d}^2}& \left(1\right)\end{array}$

(37) Where P.sub.r is the received power, P.sub.t is a transmitted power, G.sub.r and G.sub.t are receiver and transmitter antenna gains respectively, is a signal wavelength and d is a distance between source and receiver. This equation can also be represented in terms of propagation gain (PG) as:

(38) $\begin{array}{cc}\mathrm{PG}=\frac{P_r}{P_t{G}_t{G}_r}={\left(\frac{}{4d}\right)}^2& \left(2\right)\end{array}$
and in decibels form as:

(39) $\begin{array}{cc}{\mathrm{PG}}_{dB}=20\log \left(\frac{}{4d}\right)& \left(3\right)\end{array}$

(40) 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:

(41) $\begin{array}{cc}{\mathrm{PG}}_{dB}=20\log \left(\frac{}{4d_0}\right)+10n\log \left(d_0\right)+X_{}\mathrm{for}d>d_0& \left(4\right)\end{array}$

(42) Where X, n and d.sub.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.sub.0 for a typical hard partitioned office environment are 7.0, 3.0 and 100 respectively.

(43) 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.

(44) 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:

(45) $\begin{array}{cc}\mathrm{PL}=20\log \left(\frac{4d_0}{}\right)+10n\log \left(\frac{}{{}_0}\right)+X_f+X_h+s\mathrm{for}d>d_0& \left(5\right)\end{array}$

(46) 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.

(47) Once all the distances are determined using any of the models available, they are processed together with reference location co-ordinates of the places where user have scanned from to map visible WAPs one by one. Depending on the number of measurements (records) for a specific WAP, various methods are available to map these WAPs. One method, triangulation, is described below with reference to FIG. 8.

(48) FIG. 4 is an illustration of the estimated positions of the WAPs of FIG. 3 after the first phase of scanning in the process of FIG. 2.

(49) In FIG. 4 the actual locations of WAPs 402, 404, 406, 408, 410, 412 are shown with a solid circle, and the estimated locations WAP are shown by the overlaid, dashed circles 452, 454, 458, 460, 462 corresponding to WAPs 402, 404, 408, 410, 412 respectively. There is no WAP estimate 456 because the corresponding actual WAP 406 was not found in the first phase of scanning.

(50) Again it can be seen that WAP 406 is not mapped because of its signal visibility at any of the nine scanning locations outside of the building. The accuracy of the mapped WAPs depend on many factors such that the scanning distance, modeling of the environment, the accuracy of the user position, the number of scans (measurements) from outside the building for a WAP as well as the geometry of those places in reference to respective WAP, and so on.

(51) FIG. 5 is an illustration of the second phase of scanning of the set of wireless access points (WAPs) in the building of FIG. 3. In the building 500 the six WAPs 502, 504, 506, 508, 510, 512 are again shown. Five new scan sites 520, 522, 524, 526, 528 are chosen inside the building, interspersed (where possible) between the WAPs.

(52) As mentioned, in the second phase of mapping, the scanning points are located inside the building where a user doing the mapping generally does not have GPS/AGPS availability. In this case a user's co-ordinates at these five places will be derived using Wi-Fi positioning technology. Wi-Fi positioning will use the co-ordinates of mapped (using the first phase of scanning as described above) and other available WAPs at respective places inside the building. For example, a user at place 524 will use WAPs 504, 508, 512 to locate himself using the phase 1 mapped WAPs' co-ordinates with other signal processing algorithms such as distance measurements using Wi-Fi signal strengths, environmental modeling such as through user inputs and triangulation, and so on as described above with reference to phase 1.

(53) A user (or other operator, for example processing received survey data at a central location) has the facility to input his own estimation of the position of the second set of locations or to input a correction (where appropriate) to an automatically derived estimate of the positions (for example to correct an apparently incorrect or overly inaccurate GPS reading if available and being used). A user may also input data to enable or to enhance performance of reference positioning system such as GPS assistance data (estimated position, time, ephemerides etc) for GPS if available and being used. The user may in particular record a perceived height or other measure (such as the storey number in the building) allowing a height or other dimension to be estimated with more accuracy. If a baseline height h.sub.b is available for a particular location (for example using data derived from topographical maps), a height estimate h can be computed as h.sub.b+h.sub.ss, where h.sub.s is the estimated height per storey (based on a global or local average or using specific knowledge about a building at the scanning location, for example) and s is the storey number (0 being the ground floor, 1 being the first floor, and so on, using UK terminology). In one embodiment using inertial (or differential) positioning, for example, a user can when appropriate input datum (or absolute) values to allow calibration of the inertial positioning system.

(54) The user may also in particular input a selection of environmental model to apply and/or parameters for use with such a model (see below for a discussion of some possible environmental models and their parameters). The selection of the environmental (and other data) may for example be made using drop-down menus or other input devices in a user interface (such as an interactive application running on a hand-held device carried by a user).

(55) In the absence of sufficient points to allow triangulation or a user-supplied positional estimate, for example, other possible methods such as weighted average can be used (including if necessary a manual input by the scanner user or operator processing the data at a later stage) to obtain a best guess of the scanning location.

(56) During the second phase of scanning, all of the six WAPs 502, 504, 506, 508, 510, 512 are scanned from inside the building, on account of the closeness to the scanning user and typical absence (for example) of thick structural walls to attenuate the signal. It can be seen that many WAPs can be scanned from more than one place. For example WAP 508 is scanned from locations 522, 524, 526, 528. Similar to phase one, at every place user again records Wi-Fi scanning parameters such as signal strength, MAC addresses of visible WAPs, Signal Quality etc. and user's own position. User may also records other useful environment specific data from observation and/or prior knowledge such as height and type of building, numbers and types of physical signal obstructions close to the scanning place etc. The user may also records data from additional sensors on the device if available to assist in positioning such as magnetometer which can provide heading, barometer which can provide height information etc.

(57) FIG. 6 is an illustration of the estimated positions of the scanner during the second phase of scanning shown in FIG. 5, in accordance with the process described above. As before the six WAPs 602, 604, 606, 608, 610, 612 in the building 600 are shown. Also shown are the estimated positions of the scanner at scan site 620, 622, 624, 626, 628, which vary from the actual scan sites by varying degrees in dependence on the above-mentioned factors that affect the signal propagation, for example.

(58) In a further embodiment in which the device has an Internet connection, a user's co-ordinates can also be derived using a central web-server by exchanging Wi-Fi parameters with it. In this case a central web server is operable to provide a user's location either through an internal database or from other Internet resources. In some cases the user may also use GPS/AGPS co-ordinates as well as any other positioning technology if it is available. Users can also input information such as co-ordinates, environment types, and so on (as described above regarding phase I) in the processing software to aid mapping process.

(59) The records formed from scanning from all of the five scanning locations are processed together in a software on a device with different signal processing algorithms such as distance measurements using Wi-Fi signal strengths, environmental modeling using user inputs, triangulation, and so on to (generally more accurately) map WAPs inside the building.

(60) FIG. 7 is a schematic illustration of the estimated positions of the WAPs of FIG. 3 after the second phase of scanning in the process of FIG. 5. In FIG. 7 the actual locations of WAPs 702, 704, 706, 708, 710, 712 are shown with a solid circle, and the estimated locations WAP are shown by the overlaid, dashed circles 752, 754, 756, 758, 760, 762 corresponding to WAPs 702, 704, 706, 708, 710, 712 respectively.

(61) It can be noted that in this hypothetical case the estimates of the positions of the WAPs are generally improved, although in individual cases such as for WAP 704 (and estimate WAP 754) the estimate can become less accurate with regard to the first phase (as illustrated in FIG. 4). Phase II has also mapped WAPs that were not mapped in phase I (for example WAP 706).

(62) Though a user's co-ordinates (derived inside from Wi-Fi positioning after phase I) at scanning points may not be accurate in comparison to user's co-ordinates (derived outside using GPS/AGPS), the overall improvement of mapping accuracy and coverage of mapped WAPs are increased after second phase of mapping due to the closeness of the scanning/mapping user (inside the building) to WAPs and hence to be able to measure the distance between user and WAPs by predicting signal propagation path more accurately through applying indoor signal propagation models described above with regard to phase I.

(63) This whole mapping process can be extended to subsequent phases to improve coverage and some level of accuracy as many times as improvements may be seen in mapped co-ordinates of WAPs. The process remains essentially the same as of phase II and can be repeated for example to rescan a previous site with more scanning locations, either inside our outside a building, for example if a particular site is identified as being a particularly difficult environment (for example after review of the initial scanning data).

(64) FIG. 8 is an illustration of the process of triangulating (in 2D) the position of a wireless access point (WAP). This is one of the possible methods for estimating the position of the WAP. In FIG. 8 three scanning sites 802, 804, 806 are shown, each detecting a signal from a WAP in the approximate region 808. The WAP/region 808 is at a distance d.sub.1, d.sub.2, d.sub.3 from respective scanning sites 802, 804, 806. Each site 802, 804, 806 is surrounded by a circle representing the locus of all points at distance d.sub.n.

(65) Here, d.sub.1, d.sub.2, d.sub.3 are derived from any of the available distance measurement models described earlier and are used together with location co-ordinates of sites 802, 804, 806 in the following equation:
d.sub.i={square root over ((x.sub.rx.sub.si).sup.2+(y.sub.ry.sub.si).sup.2)}(6)

(66) Where d.sub.i is the distance, x.sub.r and y.sub.r are the x and y co-ordinates of WAP 7 and x.sub.si and y.sub.si are the x and y co-ordinates of places, where i is 1, 2, . . . . , n. Three equations are formed and solved for x and y co-ordinates of the WAP in region 808. These equations can be solved with any available methods such as the least squares method.

(67) As shown in FIG. 8, the mapped co-ordinates for the WAR in region 808 are where the three circles (the loci of the estimated distances between the sites and the WAP) overlap. The circles do not overlap at a single point because of errors in the measurement/estimation of the distances d.sub.1, d.sub.2, d.sub.3 and possible errors in the reference (or estimated) co-ordinates of the scanning sites 802, 804, 806.

(68) It will be appreciated that the above 2D example can be extended into 3 dimensions as required. It is not normally required to record the three-dimensional position of a WAR (merely the two-dimensional position) but it will be appreciated that the relevant modifications can be made if a 3D location is required.

(69) FIG. 9 is a schematic illustration of a dedicated scanner system suitable for use with the first phase at least of the process of FIG. 2. This scanner may be used in some or all of the embodiments described above in preference to a handheld unit (which may or may not be the same unit as the unit described below in relation to FIG. 10).

(70) In FIG. 9 the dedicated scanner system (such as a war-driving rig) includes a directional antenna 902 (such as a direction Wi-Fi antenna), amplifier 904 for amplifying signals from the antenna, a GPS (or AGPS or other similar unit) 906 for providing reference coordinates of the scanner system 900, a computer 908 for controlling and/or processing and/or receiving data from any or all of the antenna 902, amplifier 904, GPS unit 906, a user interface 910 for controlling the scanner system, inputting relevant data and displaying results, and a data storage unit 912 for storing records created by the scanning process. In an alternative embodiment a network interface unit (not shown) is provided to allow data to be sent and/or received via a communications network, for example to allow remote control and/or data collection, which may obviate the need for the storage unit 912 for example.

(71) FIG. 10 is a schematic illustration of a handheld unit suitable for use with the first and second phases of the process of FIG. 2.

(72) The handheld unit includes a Wi-Fi interface 1002, a GPS or AGPS unit 1004, a network interface 1006 (which may optionally not be present for a purely local operation of the scanner), a processor (or microcontroller or other computerised device) 1008, a user interface 1010 and a data storage unit 1012. This unit may have less selectivity, signal amplification and/or processing power or storage capacity compared to the device described above in relation to FIG. 9, but may on the other hand be more portable and therefore easier to bring into closer contact with any WAPs that require scanning. In a further embodiment the handheld unit may omit or deactivate the GPS/AGPS unit 1004, for example if used only during the second phase of scanning.

(73) In a further embodiment a scanner unit may be provided which mixes features from both the scanner system 900 described above in relation to FIG. 9 and the handheld unit 1000 described above in relation to FIG. 10.

(74) FIG. 11 is an overview of a system for locating a user device using the data generated by the process of FIG. 2.

(75) In FIG. 11 a user device 1100 (such as the handheld device 1000 described above or any other device, for example), a telecommunications network (such as a mobile telephone network) 1102, a location server 1104 and a WAP location database 1106 (which may be integrated with the location server 1104) are shown.

(76) In use, a user causes the user device 110 to send a location request 1150 to the telecommunications network 1102 (for example using a service on a mobile telephone). The request 1150 may typically include data received at the user device 1100, such as properties (such as those described above with regard to phases I and II above) of signals detected from nearby WAPs. The request 1150 may thus, for example, include details of the signal strengths of nearby WAPs and MAC addresses (and/or cell tower signals, and so on).

(77) A request 1152 (usually the same as the initial request 1150) passes from the network 1102 to the location server 1104. The location server 1104 then processes the request 1152 and in so doing interrogates the location database 1106 with a WAP lookup request 1154, to specify WAP data that is relevant to the location request 1152. The database 1106 then returns the requested data 1156 to the server 1104. The server finishes processing the data 1156 in conjunction with the received request data 1152 to produce a location estimate which is sent back to the user device 1100 in the form of location data 1158. The network forwards location data 1160 (usually the same as the data 1158) to the user device 1100. The user device can then process the location data 1160 to retrieve (and for example display) the location estimate.

(78) The system described above with reference to FIG. 11 may also be used in the initial discovery phases, for example in conjunction with the phases I and II described above. The server 1104 may for example additionally or alternatively operate software to process the scanning data to produce the various estimates described above.

(79) 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).

(80) 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.

(81) 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.