Mobile device positioning system and method

Abstract

A mobile device positioning system includes a receiver to receive data on a plurality of signals received by a mobile device, each of the signals being from a transmitter in an area, the positioning system including a processor configured to execute computer program code for determining, in dependence on the data, a relative distance of the mobile device with respect to each transmitter associated with the respective signals and for determining a position of the mobile device in between the transmitters of the received signals in dependence on the determined relative distance.

Claims

1. A mobile device comprising: a receiver configured to receive signals, each of the signals being from a transmitter in an area, and each of the signals including location coordinates of the respective transmitter relative to a predetermined origin; a processor coupled to the receiver, the processor configured to: determine a zone in the shape of a polygon, the polygon defined by four or more vertices, each vertex being a location of a transmitter, and the determination based on the location coordinates of the respective transmitter; calculate a signal strength of the transmitter at each vertex; determine a relative distance of the mobile device from within the zone to each vertex, each relative distance based on the signal strength of the transmitter at each vertex; and determine a position, relative to the predetermined origin, of the mobile device in the polygon based on each relative distance.

2. The mobile device of claim 1, wherein the receiver is configured to passively listen to signals from transmitters to thereby receive the signals.

3. The mobile device of claim 1, wherein each of the transmitters comprises a BlueTooth beacon, the signals comprising advertisements from the beacons.

4. The mobile device of claim 1, wherein when the processor determines the relative distance of the mobile device from within the zone to each vertex, the processor is further configured to calculate distance according to:
distance (in meters)=e^((RSSIA)/n) where RSSI is the signal strength in decibels (dB) and A and n are system parameters determined based on physical circumstances of the area.

5. The mobile device of claim 1, further comprising: a display device coupled to the processor; the processor configured to: receive the signals from the receiver, each of the signals has an indication of signal strength; filter the signals based on an indication of reliability, the filtering results in filtered data comprising information regarding one or more transmitters in the area; determine a single-point position, relative to the predetermined origin, of the mobile device from a single transmitter if the filtered data has information on only one location transmitter; determine a two-point position, relative to the predetermined origin, of the mobile device from only two transmitters if the filtered data has information on only two transmitters; display, on the display device, an indication of the position, the single-point position, or the two-point position.

6. The mobile device of claim 5 wherein when the processor determines the two-point position of the mobile device from only two transmitters, the processor is further configured to: determine a straight line having endpoints being the location coordinates of the only two transmitters in the filtered data; determine a relative distance of the mobile device along the straight line to each endpoint, each relative distance based on the indication of signal strength for the transmitter at the respective endpoint; and calculate the two-point position residing along the straight line based on each relative distance.

7. The mobile device of claim 5 wherein when the processor determines the single-point position of the mobile device from the single transmitter, the processor is further configured to limit the single-point position based on a value indicative of walking speed of a user carrying the mobile device.

8. The mobile device of claim 5 wherein when the processor determines the two-point position of the mobile device from only two transmitters, the processor is further configured to limit the two-point position based on a value indicative of walking speed of a user carrying the mobile device.

9. The mobile device of claim 5 wherein when the processor determines the position of the mobile device from four or more transmitters, the processor is further configured to limit the position based on a value indicative of walking speed of a user carrying the mobile device.

10. The mobile device of claim 5 wherein when the processor filters the signals based on the indication of reliability, the processor is further configured to only include signals in the filtered data received within a predetermined period of time.

11. The mobile device of claim 5 wherein when the processor filters the signals based on the indication of reliability, the processor is further configured to limit the signals in the filtered data to be a predetermined number of nearest location transmitters.

12. The mobile device of claim 5 wherein when the processor displays the indication of the single-point position, the processor is further configured to display a circle around the indication of single-point positon where radius of the circle is indicative of accuracy of the single-point position.

13. A method of determining a position of a mobile device, comprising: receiving signals by the mobile device from four or more transmitters, each signal including location coordinates of a respective transmitter relative to a predetermined origin; calculating, by the mobile device, signal strength of each signal; determining, by the mobile device, a zone in the shape of a polygon, the zone having four or more vertices, each vertex being a location of a transmitter, and the determining based on the location coordinates; and determining, by the mobile device, the position of the mobile device within the zone based on the signal strength of each signal.

14. The method of claim 13, further comprising displaying, on a user interface, the position of the mobile device and overlaying a marker for the mobile device at the position on a graphical illustration of the zone.

15. The method of claim 13: scoring reliability of each signal, and thereby creating a reliability score for each signal; filtering the signals based on the reliability scores, the filtering creates filtered signals; wherein determining the zone having four or more vertices further comprises determining the zone using only the filtered signals; and wherein determining the position of the mobile device further comprises determining the position using only the filtered signals.

16. The method of claim 15 wherein scoring reliability further comprises marking as unreliable signals received earlier than a predetermined time.

17. The method of claim 16 wherein scoring reliability further comprises scoring reliability based on signal strength for each signal.

18. The method of claim 13 wherein determining the position of the mobile device further comprising limiting allowable positions based on a value indicative of maximum walking speed of a user carrying the mobile device.

19. The method of claim 13 wherein receiving signals further comprises receiving at least one signal from a transmitter that is moving.

Description

BRIEF DESCRIPTION OF THE FIGURES

(1) Embodiments of the present invention will now be described, by way of example only, with reference to the accompanying drawings in which:

(2) FIG. 1 is a schematic diagram of a mobile device positioning system according to an embodiment of the present invention;

(3) FIG. 2 is a schematic diagram of a mobile device positioning system according to another embodiment of the present invention; and,

(4) FIGS. 3-10 are schematic diagrams illustrating aspects of operation of the mobile device positioning system of FIG. 1, or 2.

DETAILED DESCRIPTION OF CERTAIN EMBODIMENTS OF THE INVENTION

(5) FIG. 1 is a schematic diagram of a mobile device positioning system according to an embodiment of the present invention.

(6) The mobile device positioning system 10 includes a processing unit 20, a receiver 30, a data store 40 and a display 50. In this embodiment, the mobile device positioning system 10 is part of a smartphone.

(7) In operation, the system 10 receives at the receiver 30 signals from a number of transmitters 60, 70. The receiver obtains a measure of the strength of each respective signal and passes this to the processing unit. The processing unit determines a location of the transmitter 60/70 corresponding to each respective signal from data within each signal and then determines a zone in between the transmitters 60, 70. The location of the smartphone within the zone is determined in dependence on the measure of the strength of each respective signal as is discussed in greater detail below.

(8) FIG. 2 is a schematic diagram of a mobile device positioning system according to another embodiment of the present invention. FIG. 2 corresponds to FIG. 1 except that the mobile device positioning system is separate to the mobile device/smartphone. For example, the system 100 may be operated by a server or other system that receives data on signals relayed by a mobile device 80. In this manner, the processing load on the mobile device 80 can be limited and the mobile device 80 nevertheless tracked/located. In this embodiment, the mobile device need not be a mobile telephone and could be a dedicated system that could be used for security, patient or customer monitoring or other applications. Positioning data may nevertheless be returned to the mobile device 80, for example as coordinates to be used (such as to show a position on a locally stored map) or as part of a user interface, webpage or the like provided by the system 100.

(9) In the embodiments of FIGS. 1 and 2, the positioning system is preferably arranged to output the determined position on a graphical user interface on the display 50. A marker or other representation may be overlaid or the mobile device at the position on a graphical illustration of the zone. The data store 40 may store maps or other visual representations. In addition or as an alternative to transmitters transmitting their location, position information on transmitters may be stored by the data store 40 (and the map and position information may optionally be combined).

(10) It will be appreciated that determining the location of the transmitter corresponding to each respective signal from data within each signal can be done in various different ways. For example, the signal may itself include or encode the location (such as x, y and optionally z and floor) coordinates relative to a predetermined origin; it may include a label or other identifier from which the location can be determined (for example by cross-referencing the label or identifier with a database that holds location information).

(11) Transmitters 60, 70 may, for example, be beacons such as BlueTooth beacons. Beacons may have a fixed, predetermined advertisement interval or this may be configurable. A typical advertisement interval may be between 300 ms up to 3 seconds. It will be appreciated that the more frequent the interval (which results in more data points) the accurate the location is likely to be. However, increased frequency will affect power consumption.

(12) Beacons may be used in addition for other purposes in conjunction with embodiments of the present inventionas long as location can be determined from the received signal, it doesn't actually matter what the received signal may be about (it will be appreciated that in practice, additional data may be added to indicate location or some existing data may be used to indicate or derive location). For example, the beacon may be providing advertisements or security information but properties of the signal can still be employed in embodiments of the present invention.

(13) In one embodiment, the processing unit has access to a register of the location of each beacon. In another embodiment, location information is communicated by each beacon when communicating receipt of a signal and its strength.

(14) Although the focus of this application is on the use of beacons and in particular BlueTooth such as BlueTooth Low Energy (BLE) Beacons, it will be appreciated that transmitters other than beacons could also be used.

(15) Various aspects involved in implementing embodiments of the present invention are discussed below, followed by explanation of operation.

(16) Distributing and Fixing Beacons in Venue

(17) Beacons are preferably positioned in a venue so that they are almost equal distance from each other, and the majority, if not all, of the accessible space is covered by the transmission area of at least 2 beacons. Once positions are determined, the beacons are preferably stuck or otherwise mounted to walls/ceilings. The transmission area between beacons is considered a logical zone.

(18) Configuring Every Beacon, One by One

(19) Each beacon is preferably configured to self-contain its position information in memory or some other fixed or long term data store, preferably in terms of relative coordinates. A beacon's advertisement data may be changed to contain its x and y position, as percentage values on the map graphic or other information may be used (or added to the advertisement). For example, a beacon's advertisement data might be configured to contain encoded information that the beacon has x=0.5, y=0.1 which means beacon is placed at 50% of x-axis and 10% of y-axis. It5 will be appreciated here that advertisement here refers to the broadcast the beacon makes indicating its presence rather than the transmission of advertising material for products/services although such data may also be encoded at source or by the beacon or otherwise be added to by the beacon at transmission time so as to provide this information.

(20) It will be appreciated that beacons may be pre-configured at manufacture (or some later time) and a fixed identifier in the beacon correlated with location information stored elsewhere so that a location lookup can be performed against the fixed identifier as and when it is received from the beacon by a mobile device. In another alternative, beacons may be configured in groups rather than each being individually configured. It will also be appreciated that a beacon may include components (or have the ability to obtain data) that allows it to determine its own location rather than the user having to configure it at this stage.

(21) Example Operation:

(22) a. Mobile Device Listens to all BLE Signals in Vicinity

(23) The receiver 30 listens to all BLE signals it can hear. Android and iOS SDK's provide native API's to achieve this via the BLE sensors in the smartphone.

(24) b. Filter Signals Belonging to the System

(25) BLE Beacons can be identified by their advertisement UUID. In addition, an encoded data structure is preferably used for beacon advertisement. Hence, BLE signals that either have a different UUID or have different/unrecognized data structure are filtered out.

(26) c. Store Non-Filtered Signals in Memory

(27) All heard signals are stored in memory of the mobile device 10 or system 100. This allows the system 10/100 to calculate how reliable a signal is (by looking at history of readings) and to use as much signal data as possible for position calculation, factoring in reliability score of each signal and applying smoothing filters as necessary. A time based approach may be applied to storage of non-filtered signals. For example, signals received over the past n seconds may be stored. Alternatively, a timestamp may be stored with received signals and used to determine which signals to take into account.

(28) d. Use Most, if not all Signal Data in Memory to Calculate Position Real-Time

(29) Preferably, the system 10/100 makes a very strong assumption that the mobile device is confined to the area (zone) enclosed by the beacons in the vicinity. Optionally, the system could be tuned or configured to only consider beacons heard in the last X seconds or it can be configured to take into consideration only up to Y nearest beacons for this assumption.

(30) e. Calculate Position

(31) After the assumption in d, signal strength value of signals (aka RSSI) is converted to a physical estimate. A preferred equation for converting this is discussed below.

(32) f. Determine Centre of Mass

(33) The centre of mass can then be calculated based on physical estimate from each beacon that is taken into calculation.

(34) The centre of mass may be calculated and/or determined in dependence on heuristic rules. For example, if only 1 beacon is considered, there is no zone between 2 beacons and the system 10/100 preferably applies a heuristic rule setting the best estimate for position as the beacon's position itself as shown in FIG. 3.

(35) For 2 beacons, there is a zone and the system 10/100 preferably applies an algorithm that assumes the mobile device is at some position along a straight line between the two beacons. The system 10/100 preferably uses an algorithm that calculates a position along the line from a weighted average of the physical estimates as shown in FIG. 4.

(36) For 3 or more beacons, there is a zone and the system 10/100 preferably applies an algorithm that assumes the mobile device is at some position in the polygonal area enclosed by the beacons. Preferably, the system 10/100 applies an algorithm that calculates a centre of mass, using physical distance estimates as weight indicators as shown in FIGS. 5 and 6.

(37) In FIG. 5, a triangular zone is formed which preferably is the only allowed area within which a mobile device detecting the three beacons may be positioned within according to the algorithm. The position is preferably calculated as centre of mass, where each beacon is representing a mass particle.

(38) In FIG. 6, there are illustrated 5 detected beacons. Position is assumed to be in the zone enclosed by the five beacons.

(39) A good analogy is the position being hooked to beacons with elastic strings and each beacon trying to pull the position to itself.

(40) In FIGS. 4 to 6, the mobile device is represented by the X and beacons each by a B in a circle. The lines between beacons and the mobile device are purely for illustration purposes, the solid lines illustrating the logical zone that is considered to bound the beacons and the fainter lines showing distance from the device to each beacon.

(41) Example Screenshots

(42) FIGS. 7 to 10 show screenshots displaying data obtained using an embodiment of the present invention.

(43) Beacons are shown as bold black dots enclosed by growing parentheses.

(44) In FIG. 7, the beacon nearest the mobile device 10/80 probably has the strongest heard signal and the beacons at top left and bottom right have much weaker heard signals, hence the resulting position.

(45) In the illustration of FIG. 8, an accuracy circle is shown about the mobile device. This gives visual feedback regarding uncertainty of position at that instance. This is calculated based on accuracy of each beacon's latest set of readings.

(46) In the illustration of FIG. 9, it is likely that the beacon in centre is very strongly heard or the other two beacons on corners are very weakly heard, hence the position is anchored almost at centre's beacon's centre.

(47) In the illustration of FIG. 10, the bottom right beacon is probably heard stronger now, pulling position towards itself.

(48) In addition to the above, finding optimal configuration parameters is important. The system currently allows the following parameters

(49) Map Height:

(50) Height of map graphic used. Used in calculation of size of accuracy circle around position pin representing the mobile device 10/80.

(51) Map Width:

(52) Width of map graphic used. Used in calculation of size of accuracy circle around position pin.

(53) Bias Power:

(54) Beacon's effect in pulling position to itself. Inverse of each beacon's distance is taken to this power for calculating centre of mass.

(55) Max Walking Speed:

(56) Allowed movement speed for user. Displacements faster than this value is not allowed and is smoothened over time.

(57) Nearest Beacons to Use:

(58) If set, up to this many beacons are allowed in position calculation.

(59) Measurement History Timespan:

(60) Position calculation uses beacons heard in the last X seconds only.

(61) Single Beacon Accuracy:

(62) Accuracy circle's relative radius size when only one beacon is used in position calculation.

(63) In addition, conversion from RSSI to physical distance estimate per beacon is also open for customisation. By default, the following conversion equation is used although others may also be used:
absolute distance (meter)=e^((RSSIA)/n)
where A=80, n=16, and RSSI is measured in dB.

(64) It will be appreciated that this equation can be updated in accordance with physical circumstances of the venue as well as transmitting power levels of beacons in use. It will also be appreciated that embodiments of the present invention while particularly suitable for indoor use, need not be so constrained and could be used outdoors subject to placement of suitable transmitters.

(65) It is to be appreciated that certain embodiments of the invention as discussed above may be incorporated as code (e.g., a software algorithm or program) residing in firmware and/or on computer useable medium having control logic for enabling execution on a computer system having a hardware processor. Such a computer system typically includes memory storage configured to provide output from execution of the code which configures a hardware processor in accordance with the execution. The code can be arranged as firmware or software, and can be organized as a set of modules such as discrete code modules, function calls, procedure calls or objects in an object-oriented programming environment. If implemented using modules, the code can comprise a single module or a plurality of modules that operate in cooperation with one another.

(66) Optional embodiments of the invention can be understood as including the parts, elements and features referred to or indicated herein, individually or collectively, in any or all combinations of two or more of the parts, elements or features, and wherein specific integers are mentioned herein which have known equivalents in the art to which the invention relates, such known equivalents are deemed to be incorporated herein as if individually set forth.

(67) Although illustrated embodiments of the present invention have been described, it should be understood that various changes, substitutions, and alterations can be made by one of ordinary skill in the art without departing from the present invention which is defined by the recitations in the claims below and equivalents thereof.