WO2019030464A1

WO2019030464A1 - A method of geolocation

Info

Publication number: WO2019030464A1
Application number: PCT/GB2017/052319
Authority: WO
Inventors: Amir Osama Mahmoud KOTB
Original assignee: Wadaro Limited
Priority date: 2017-08-07
Filing date: 2017-08-07
Publication date: 2019-02-14

Abstract

A method for determining a likely location of a device, the device being configured for wireless communication with a communication network including a plurality of cell sites; the method including the following steps: (a) detecting by the device a respective wireless signal from each of a plurality of detected cell sites; (b) accessing a cell plan comprising a database, the database including a plurality of cell site records, each cell site record corresponding to a cell site in the communication network, (c) for each of the detected cell sites, identifying the corresponding detected cell site record in the database; (d) determining a geographical region of interest based on information contained in the cell site records corresponding to the plurality of detected cell sites (e) determining the likely location of the device within the geographical region of interest.

Description

A METHOD OF GEOLOCATION

The present invention relates to a method of geolocation, and more particularly to a method of determining a likely location of a device for wireless connection to communication network.

Devices for wireless connection to communication network ("devices", for short) pervade almost all modern life. Amongst the multitude of functionalities of a device, the ability of the device to determine its own location, or for another party to determine the location of the device, is a particularly useful function. Locations derived from such geolocation

functionalities can be utilised in a great many ways, both existing and as-yet unknown.

A device may be a mobile telephone/cell phone, but may also equally be any other device that is configured to connect wirelessly to a communication network. Such devices may include diagnostic equipment for use by an operator of a communication network, or a party who is measuring the performance of a communication network.

As a first example, a mobile network operator may wish to determine the coverage of a mobile network. Effectively, this involves measuring the signal strength/quality at several locations to map the signal coverage. This is achieved by a so-called "drive test", which requires at least one vehicle fitted with specialist network measurement equipment being driven around a predefined area at a predefined time. During a drive test, mapping of a mobile network's radio characteristics is discrete (in time and location). A drive test does not therefore cover the entirety of the geographic address of the mobile network. Consequently, measurements from a drive test do not perfectly correlate with, or measure, the mobile network's subscribers' experience of network coverage quality.

As a second example, a third party may wish to know the location of a particular mobile device, the third party being located remotely from the mobile device in question. The location to be determined may be "live", i.e. "where is the device located right now?"; or "historical", for example, "where has the mobile device been in the last 24 hours?", for example. This type of geolocation may be for legal/law enforcement reasons, for example, the police may wish to know the location of a mobile device, and by proxy, the likely location of the owner of the device. On the other hand, such geolocation may be commercial, for example a mobile network operator may wish to know the locations of their users, for the purposes of network coverage planning or for provision of other services either from the mobile network operator directly, or from a third party, for example. Thus, the third party may wish to know the location of a plurality of mobile devices. As a third example, a third party may wish to know when a particular mobile device is within a particular area, for example a city centre region. Alternatively, the third party may wish to identify all mobile devices (or a subset of them) that are located within a particular area.

As a fourth example use, a location of mobile device can be used as an input to a map service. The map service, which is running on the mobile device, can display to the user where the mobile device is located, projected onto a map display. Furthermore, the user may be directed by the mobile device to a particular destination from the current location through a series of instructions, for example. The location of the mobile device may, in effect, be updated in real time. This allows the user to see their position change in real time with their movements. Without the ability for the mobile device to determine its location, such map and direction functionality would be impossible.

As mentioned above, a conventional way of measuring a location of a device is to use a global satellite navigation system, for example, the Global Positioning System (GPS). In a global satellite navigation system, a specifically designed receiver receives from satellites a plurality of radio signals from a corresponding plurality of satellites. Using the received signals and their mutual relationships, a location on the surface of the planet is calculated. Whilst global satellite navigation systems can be very accurate (accuracy of only a few metres is possible), they require a specific receiver and equipment.

Nevertheless, many modern mobile devices include a global satellite navigation system receiver, which can be used to determine the location of the mobile device. The location that is determined from the global satellite navigation system can then be used by the mobile device itself or by other parties if the mobile device outputs its location. Possible examples of the use of such a location are described above.

A significant constraint on the design and functionality of many devices is battery life. There is a constant struggle to improve battery life so that a device can remain powered on for longer, and make use of more power-hungry hardware and software. Conversely, a large battery increases the size of the mobile device, potentially undesirably.

A global satellite navigation system receiver (and the running of the accompanying software/firmware) consumes electrical power and this is a drain on the battery of a mobile device. One way to reduce battery consumption of a mobile device therefore, is to disable the global satellite navigation receiver. This disabling may be deliberately performed by the user according to a setting on the mobile device, or maybe part of a power saving routine. While disabling the global satellite navigation receiver may prolong the battery life of the mobile device, functionality of the device (as above, for example) is reduced. For a device connected to a power supply, it is still desirable to reduce power usage.

Furthermore, there are times when global satellite navigation systems simply do not work, or where the performance of the system is severely impaired. For example, global satellite navigation systems often require line-of-sight from the receiver to the satellites that are to be monitored. As such, they often do not perform well when such lines of sight are not available, for example in in a roofed-car park, or in the so-called "urban canyon". Global satellite navigation systems may also cease to operate correctly when there is multipath interference to the radio signals to be measured by the receiver in the mobile device. As the skilled person will appreciate, multipath interference can arise in a number of situations, including urban environments when radio signals are reflected from buildings.

Some devices are connected to a mobile communications network. The connection may be a two-way communications link. The link allows communications between a device and the network, and access to other services on the device. The network may allow, for example, a connected mobile telephone device to make/receive telephone calls, send/receive messages, send/receive emails, access the internet, and access web-based services.

It is often possible for a connection to the communication network to be disabled by the user. Again, the user may do so to increase battery life. However, the functionality of the mobile device is often impaired to such an extent by disabling the network connection that the user is motivated not to do so.

It is noted that with all methods of geolocation, it is only possible to calculate an approximate location of a device. Various factors can affect the accuracy of a particular method. What is in fact calculated in all methods of geolocation is a likely location - that is, the location at which, on the evidence/data available, the device is likely to be located in the real world. Such a likely location may be treated as the actual location of the device.

Accordingly, it is an object of the present invention to provide an improved method for determining a likely location of a device.

According to a first aspect, there is provided a method for determining a likely location of a device, the device being configured for wireless communication with a communication network including a plurality of cell sites; the method including the following steps: (a) detecting by the device a respective wireless signal from each of a plurality of detected cell sites; (b) accessing a cell plan comprising a database, the database including a plurality of cell site records, each cell site record corresponding to a cell site in the communication network, (c) for each of the detected cell sites, identifying the corresponding detected cell site record in the database; (d) determining a geographical region of interest based on information contained in the cell site records corresponding to the plurality of detected cell sites (e) determining the likely location of the device within the geographical region of interest.

In this way, the database, which contains the technical properties of the cell site in the mobile network in the form of cell site records. The cell site records are used to determine a geographical region of interest. The geographical region of interest constitutes an area in which to determine the likely location of the device. Thus, the geographical region of interest forms a constraint on the likely location of the device. By so constraining the area for determining the likely location to the geographical region of interest, the compute-complexity and/or quantity of computation required to determine the likely location of the device may be reduced. In other words, by using cell site records in the cell plan, the region in which to calculate the likely location of the mobile device may be constrained.

A method according the present invention allows a number of functionalities. For example:

• Emergency services - many emergency telephone calls to the emergency services are made using mobile telephones. For some of these calls, the caller may be putting themselves in danger by speaking to the emergency services operator. Thus, the caller is unable to tell the operator their location, so that assistance can be provided. Such a telephone call may be called a "Silent Emergency Call". The method of the present invention may allow a likely location of the caller to be determined so that assistance can be sent to that likely location. This is achieved without any need for the caller to speak to the operator. The operator may be permitted to send a command to the mobile telephone of the caller to send a measurement report to the server, whereupon the likely location is determined.

• Homeland security - potential criminals and terrorism suspects may have their

location tracked by proxy by using the method according to the present invention to determine at least one likely location of the mobile device. Of course, by performing multiple determinations of the likely location over time, the movements of the device in question can be tracked. Public safety - applications for devices can be developed that use the likely location determined for the device. The applications may be location based service (LBS) application. For example, mobile telephony devices include "apps", which may be LBS apps. For example, parents may be able to track the whereabouts of their children using the determined likely location(s) of the child's device. An area of interest may also be set up, for example, around the child's school. By determining the likely location of the mobile device, the parents could be notified when the child enters or leaves the area of interest. A public safety example could be defining an area of interest in which people are to be notified of an event. Users could also notify events to a third party based on their location.

Traffic monitoring - if likely locations of a motor vehicle are being tracked, or the likely locations of a device within the vehicle (for example a device belonging to a driver or passenger) then the movement of the traffic can be determined by determining locations of the device as a function of time.

Road side assistance - a likely location determined according to a method of the present invention can be used as the location to which to send roadside assistance. There is no need for the person requiring assistance to know where there are.

Insurance - the movements of a vehicle can be tracked by measuring the likely location of a device belonging to the driver (for example, a mobile telephone). In this way, the driving behaviour can be tracked and measured. Where a device is stolen, it would also be useful and desirable to be able to determine a likely location for that device (for reasons of insurance and law enforcement).

Proximity based marketing, in which service and product providers can send advertisements to mobile devices located within an area of interest. Initially all mobile devices that are monitoring a particular cell site or cell sites may be sent a command to trigger reporting of their network measurements. A likely location can then be determined for each device. The likely locations can then be filtered geographically to identify those within the area of interest, which can then be targeted. Mobile workforce management, in which an organisation in control of a number of field operatives and/or assets that need to be tracked in their locations. • Fraud prevention, in which monetary transactions can be verified by matching the likely location of a mobile device to the location of the monetary transaction, for example a credit card purchase.

• For insurance purposes, the physical movements of a mobile device can be tracked.

The mobile device may be a user's mobile telephone, which by proxy tracks the movements of the user's vehicle, or the mobile device may be fitted to the vehicle itself. Parameters of the vehicle's movements may be used to calculate an insurance premium. For example, how much and at what times of day during a vehicle is used, or the locations in which the vehicle is used, may be determined using the method of the present invention, for example.

As an example of a scheme in which geolocation of a device in the absence of satellite navigation system would be useful has been previously described by the applicant as a method and system for monitoring the performance of a network (WO 2011/089389 A1).

In the present invention, the wireless communications network may be a 2G (for example, GSM or GSM-R), 3G, or 4G mobile network, or indeed the planned 5G network, for example. In general, the communication network may be any radio network. It will be appreciated that the principles of the present invention may be applied to other types of communications network.

The method of determining a likely location may be particularly useful inside large buildings, where a communication network may be provided but in which GPS capability is unavailable or severely deteriorated. A good example is a shopping mall.

In the present application, the term "device" is intended to cover any device (static or mobile) that is capable of wireless communication with the communication network. It will be appreciated that a multitude of objects, machines, appliances, equipment, apparatuses, and vehicles can wirelessly connect with a communication network, or be configured for wireless connection with a communication network. For example, vehicles often include one or more modules that allow wireless connection with a communication network to enable some functionality for the vehicle. In general, a vehicle can physically move relative to the communication network, and such being able to determine a likely location for the vehicle is useful. The vehicle forms an example of a device. The device may also be a mobile telephony device, which is another example of a mobile device. The "device" of the present application also includes devices that are, in general, static relative to the communication network. For example, a vending machine may also be configured for wireless connection to a communication network, and may generally be considered a static device. A second example of a static device may be a metering system in the home, for example a gas meter or electricity meter. The metering systems may be configured for wireless connection with a communication network. The intention is that static, as well as mobile, devices are covered by the "device" of the claims.

The term "device" is also intended to cover a "connected device" or a "smart device". An example of such a device may be an "internet of things" (IOT) device or a wireless machine- to-machine ("M2M") device. IOT and M2M devices may be examples of devices having no GPS capability. The methods according to the present invention for determining a likely location may be particularly desirable for devices having no GPS capability.

The geographical region of interest may be determined based on information contained in the cell site records corresponding to a plurality of selected detected cell sites, where the selected detected cell sites are a sub-set of the plurality of detected cell sites. In other words, some of the detected cell sites may be selected from among the plurality of detected cell sites for use in the further steps of the method.

Optionally, step (d) includes, for each detected cell site: determining a cell site coverage shape, the cell site coverage shape corresponding to a predicted geographical area of coverage of said cell site as predicted by the information in said respective cell site record.

The cell site coverage shape for a particular cell site may correspond to the real world geographical area corresponding to area in which it would be predicted that a device located within that geographical area could detect the respective cell site. In general, a particular cell site coverage shape can have any size and form. In particular, the cell site coverage shape may be defined by a mathematical description of the perimeter of the cell site coverage shape, and/or parameters that describe the cell site coverage shape.

The cell site coverage shape may be considered as a cell site coverage zone, a cell site coverage region, a cell site coverage area, or a cell site coverage sector: the terminology is in this respect is interchangeable.

In reality, a device may not be able to detect a particular cell site even when located within the cell site coverage shape. Similarly, in reality, a device may be able to detect a cell even when it is located outside the cell site coverage shape. This is because the information may in the cell site records may not accurately describe the real-world detectability of the cell sites. This is discussed in more detail below.

Optionally, step (d) includes determining whether or not all of the cell site coverage shapes have a unique overlap region with one another, and wherein if it is determined that all of the cell site coverage shapes do have a unique overlap region with one another, then the unique overlap region is determined to be the geographical region of interest.

Each cell site record includes information that defines a coverage shape of the respective cell site. By using the cell site records of at least two detected cell sites to determine a unique overlap region of the coverage shapes of the at least two detected cell sites, the geographical region of interest may be smaller than a coverage shape of any one of said detected cells sites. The unique overlap region may correspond to a region in which at least a portion of each of the cell site coverage shapes are co-incident with each other. The geographical region of interest can thereby be reduced in size. The overlap region represents the geographical region in which it is predicted, based on the cell plan, that the device should detect the wireless signals from each of the cell sites that it has, in fact, detected. The geographic region of interest forms an area in which to determine the likely location of the device, thus forming a constraint of the likely location.

Conveniently, if it is determined that all of the cell site coverage shapes do not have a unique overlap region with one another, then the method further includes executing a full-circle routine: the full-circle routine including the steps of: for each of the cell site coverage shapes, calculating a full-circle coverage shape surrounding a corresponding cell site location;

determining whether or not all of the full-circle coverage shapes have a unique overlap region with one another, and; if it is determined that all of the full-circle coverage shapes do have a unique overlap region with one another, then the unique overlap region of said full circle coverage shapes is determined to be the geographical region of interest.

As mentioned above, in reality the cell site coverage shape predicted by information in the cell site record for that cell site may not accurately describe the real-world detectability of that cell site. This may, for example, be due to the device detecting a wireless signal that has been reflected along the path to the device from the cell site. In general, it is possible that a device will detect a cell site that it should not, according to the information in the cell plan, be able to detect. For example, initially each cell site coverage shape may have an angular extent from the cell site of less than 360 degrees, i.e. the coverage shape may have a sector shape. A device may detect such a cell site from a point beyond the angular extent of the sector shaped coverage shape. When this occurs, there may be no unique overlap region between the cell site coverage shapes of the detected cell sites.

To address this potential situation, the method may include the full circle routine described above. During the full-circle routine, each of the cell site coverage shapes are each converted to a full-circle coverage shape. In other words, each of the cell site coverage shapes is extended to have a full 360-degree extent surrounding the corresponding cell site location to form the full-circle coverage shape. By using the full-circle routine, a unique overlap region between the full-circle coverage shapes may be determined where one was not identified between the cell site coverage shapes.

Thus, the full circle routine may be performed in response to a finding that there is no unique overlap region between the cell site coverage shapes. For example, where the unique overlap region is small (for example, less than 100 square metres), the geographical region of interest may also be small. If the likely location of the device is determined to be at an edge of the geographical region of interest, then that may imply that the true location of the device could be outside the geographical region of interest. Noting that reflections of the wireless signal between the cell site location and the device will change the shape of a real-world coverage for a cell site relative to the coverage shape from the cell site record - actual beam width for a cell site could be larger than the theoretical beam width from the cell plan. The full circle routine may be able to address this discrepancy between the real-world coverage of a cell site and that described by the coverage shape.

Optionally, the method further includes executing a full-circle routine: the full-circle routine including the steps of: for each of the cell site coverage shapes, calculating a full-circle coverage shape surrounding a corresponding cell site location; determining whether or not all of the full-circle coverage shapes have a unique overlap region with one another, and; if it is determined that all of the full-circle coverage shapes do have a unique overlap region with one another, then the unique overlap region of said full circle coverage shapes is determined to be the geographical region of interest.

Thus, the full circle routine may be performed regardless of whether or not there is a unique overlap region between the cell site coverage shapes. Optionally, the method further including: a coverage shape extension routine, including: where all of the full-circle coverage shapes do not have a unique overlap region with one another, for each of the full-circle coverage shapes, incrementing the radius of said full-circle coverage shape by a radial step; determining whether or not all of the incremented full-circle coverage shapes have a unique overlap region with one another, and; if it is determined that all of the incremented full-circle coverage shapes do have a unique overlap region with one another, then the unique overlap region of said incremented full circle coverage shapes is determined to be the geographical region of interest. As mentioned above, in reality the cell site coverage shape for a particular cell site as predicted by information in the cell site record for that cell site may not accurately describe the real-world situation. The device may detect a cell site from a location outside the radial extent of the coverage shape from the cell site location, as predicted by the cell plan. When this occurs, there may be no unique overlap region between the cell site coverage shapes, or between the full circle coverage shapes (see above).

To address this situation, the present invention includes the coverage shape extension routine. During the coverage shape extension routine, the radius of each of the full circle coverage shapes is increased - thus effectively extending the range of the coverage shape from the cell site location, as described by the corresponding full circle coverage shape. In other words, during the coverage shape extension routine, each of the full circle coverage shapes is extended to have a greater radial extent from the location of the cell site than its previous radial extent from the location of the cell site. Each of the full circle coverage areas of the detected cell sites may be extended by the same factor. By using the radial extension routine, a unique overlap region of the incremented full circle coverage shapes may be determined.

The radial extension routine may be used in combination with the full-circle routine, or separately from the full circle routine. In other words, a method according to the present invention may include only the full-circle routine, only the radial extension routine, or both.

As above, the full circle routine may be used in response to a finding that there is no unique overlap region between the coverage shapes, or may be used in all situations. In other words, it is not determined whether or not the cell site coverage shapes have a unique overlap region; instead, the full circle routine is performed first and it is determined whether or not there is a unique overlap region between the full circle coverage shapes. Optionally, for each incremented full-circle coverage shape, the respective radial step is equal to a fraction of an original full circle radius of the respective full-circle coverage shape.

In this way, an initially larger coverage shape may be extended by a commensurately larger radial step than an initially smaller coverage shape. Optionally, the method further including repeating the coverage shape extension routine until the radius of at least one of the incremented full-circle coverage shapes exceeds a maximum radius or until the incremented full-circle coverage shapes do have a unique overlap region with one another.

In this way, a limit can be imposed upon the radial extent of a full circle coverage shape. In this way, a limit to a computational burden can be imposed. This is achieved by imposing a limit on the incremented radial extent of the coverage shapes. For example, the maximum discrepancy between the radius predicted by the cell plan and a real-world maximum detectable distance may be less or equal to the radius predicted by the cell plan. So, for example, the limit set for the maximum extent of each of the full circle coverage shapes (the maximum radius) may be equal to double the range of the serving cell.

When the full circle coverage shapes are incremented to the equal the maximum radius or greater, and no unique overlap region is determined, then the incrementing loop is broken. In this case, the method may return the centre location of the serving cell's coverage region as the likely location of the device. Optionally, the maximum radius is proportional to an original radius of the full circle coverage shape for a serving cell site that is providing network access to the device from among the plurality of detected cell sites.

The detected cell site having the highest signal strength may be the serving cell site.

Optionally, measurement information describing the detection by the device of the respective wireless signal from each of the plurality of detected cell sites is sent to a remote server as a measurement report.

In this way, using the information in the measurement report, the remote server is able to access the cell plan and the relevant cell site records in the database of the cell plan, determine the geographical region of interest, and determine the likely location of the device without further interaction or information from the device. This allows the method steps performed on the device to be simple, and thus reduce the necessary compute capability of the device.

Optionally, the device sends the measurement report to the server upon receipt by the device of a command signal. The command signal may be a broadcast signal or a specific command signal directed to a specific device or a command signal directed to a list of specific devices.

Optionally, the command signal includes reporting instructions, the reporting instructions dictating when the device should send at least one measurement report.

The device may send the measurement report periodically to the remote server or in response to some predefined condition. The device may send the measurement report to the remote server in response to reporting instructions that are contained in the command signal received by the device. The device may begin to send the measurement reports periodically to the remote server, in accordance with the reporting instructions. The device may send the measurement reports to the remote server a specific number of times before then ceasing sending of the measurement reports in accordance with the reporting instructions. The number of times that the device is to send the measurement report may be specified in the reporting instructions received by the device.

By using a command signal to trigger the sending of the measurement report, and thus the potential for the determination of a likely location, a device can effectively be "asked" to send the measurement report, from which a likely location of the device can be determined.

A particular device may be targeted by the command signal by addressing the command signal to the particular device. The particular device may for example be addressed based on a telephone number of the device, in the case of a mobile telephone.

Furthermore, the reporting instructions may allow a device that receives that command signal to determine whether or not the device is to send one or more measurement reports.

Additionally, or alternatively, the reporting instructions may also allow a device that receives that command signal to determine when the device is to send one or more measurement reports. For example, the reporting instructions may include an area code. If the device is in an area in which it detects, and/or is served by, a cell site having that area code, then the device is to send the measurement report. If the device is not within that area code, then the device may ignore the command signal. The device may also include a list of at least one predefined target area codes. If the device enters an area in which it detects, and/or is served by, a cell site having one of the target area codes, then the device may then send a measurement report.

The measurement information may include the cell identifier and a power measurement for each of the detected cell sites, for example.

Optionally, the device sends periodically a measurement report to the server.

By sending the measurement information periodically, a likely location of the device can be determined repeatedly. In turn, this may allow the device to be tracked.

Optionally, each cell site record for a respective cell site includes at least: a cell site identifier of said respective cell site, and; a cell site location of said respective cell site.

The cell site information comprised in a cell site record may be used to calculate the cell site coverage shape for the corresponding detected cell site. A cell site identifier may be determined by the mobile device for each detected cell from information contained in the wireless signal from said cell site. Such cell site identifiers may be used to identify the relevant cell site record in the cell plan. Each cell site record may include the cell site location, the cell site location including a latitude and a longitude at which a cell site (radio) transceiver of the cell site is located, for example. A particular cell site may have a generally circular cell site coverage shape. In this case, the cell site coverage shape extends 360 degrees around the cell site location and is centred on the cell site location. Alternatively, a particular cell site may have a sector-shaped cell site coverage shape. Multiple sector-shaped cell sites may have the same cell site location. The multiple co-located sector-shaped cell sites may, in combination, extend 360 degrees around the cell site location. The may also be some degree of overlap between the cell site coverage shapes of adjacent co-located sector-shaped cell sites.

As described above, the information in a particular cell site record may not be accurate and/or may not result in a cell site coverage shape that accurately describes the real-world coverage of the particular cell site. Thus, it will be appreciated that the method according to the present invention may be used to verify and/or amend the information stored in the cell site records so that, in future, coverage shapes derived therefrom more accurately describe the real-world coverage area of the corresponding cell site. Optionally, each cell site record for a respective cell site further includes at least one of: a cell site transmission power of said respective cell site; a cell site beam width of said respective cell site; a cell site azimuth of said respective cell site, and; a cell site maximum range of said respective cell site.

Optionally, each cell site coverage shape is calculated using the information contained in the respective cell site record.

Optionally, at least one of the cell site coverage shapes is represented as a cell site polygon.

Additionally, or alternatively:

• at least one of the full circle coverage shapes may be represented as a full circle

polygon;

• at least one of the incremented full circle coverage shapes may be represented as an incremented full circle polygon; and,

• the overlap region may be represented as an overlap polygon.

Using the cell site coverage shapes as an example, the inventors have discovered that particularly computationally advantageous way is to represent each cell site coverage shape with a cell site polygon. Each cell site polygon is a set of vertices (latitude - longitude pairs, for example), which together define the perimeter of the cell site coverage shape that the polygon represents. By using cell site polygons (and polygons in general for the elements of the method), the method according to the present invention may be computationally simpler and faster to perform. In particular, it may be simpler to calculate an overlap region between two polygons. It may also be simpler to calculate whether or not a particular point is located within a particular polygon, for example.

Optionally, step (a) includes, using the device, measuring a measured a received signal strength of the wireless signal from each of the detected cell sites; and step (e) includes: (i) defining a plurality of points distributed within the geographical region of interest; (ii) designating one of the detected cell sites as a primary cell site and at least one of the remaining detected cell sites as secondary cell sites; (iii) for each point: comparing the received signal strength for the primary cell site with a respective received signal strength for each of the secondary cell sites; (iv) choosing a favoured point from the plurality of points based on said comparisons and (v) determining the likely location of the device based on the location of the favoured point. In this way, the determination of the likely location of the device is based upon a point-wise comparison of the respective measurements of the received signal strengths of a pair of detected cell sites (one primary cell site and at least one secondary cell site).

The number of secondary cell sites may be limited. For example, the number of secondary cell sites may be limited to two secondary cell sites.

The geographical region of interest has already been used to constrain the likely location of the device, so that the computational burden of the point-wise comparison may be reduced. The number of points can be controlled in order to match with a compute capacity of the system that is performing the calculations, which allows for a flexible system. The plurality of points may be defined as a grid of points. The grid of points may be evenly distributed across the geographical region of interest.

Optionally, step (iii) includes: for each point: using a radio propagation model, calculating a primary signal strength distance, p_RSS_d, between the primary cell site and the device based on the measured signal strength from the primary cell site and a transmission power from the primary cell site, and calculating a primary real-world distance, p_RW_d, between the primary cell site and the respective point using a location of the primary cell site, and calculating a primary fraction, PF, where PF = (p_RSS_d - p_RW_d) / p_RSS_d; for each secondary cell site: using the radio propagation model, calculating a respective secondary signal strength distance, s_RSS_d between the respective secondary cell site and the device based on the measured signal strength from the respective secondary cell site and a transmission power from the respective secondary cell site, and calculating a respective secondary real-world distance, s_RW_d, between the respective secondary cell site and the respective point using a location of the respective secondary cell site, and calculating a respective modified secondary distance, s_M_d, where s_M_d = s_RSS_d + (s_RSS_d * PF); calculating a respective secondary weight, sW, where sW = abs(s_M_d - s_RW_d); and calculating a point sum, PS, for each point, the respective point sum being equal to the sum of the secondary weights corresponding to the respective point.

This constitutes and implementation of the point-wise comparison of the respective measured signal strengths of a pair of detected cell sites (one primary cell site and at least one secondary cell site).

Optionally, the method further including calculating a point weight, PW, for each point, where PW = 1/PS. Optionally, the favoured point is the point having the maximum value of PW. Optionally, the primary cell site is a serving cell site for the device.

According to a second aspect, there is provided a method for determining a likely location of a device, the device being configured for wireless communication with a communication network including a plurality of cell sites; the method including the following steps: (i) using the device, measuring a received signal strength of a wireless signal from each of detected cell sites; (ii) defining a plurality of points distributed within a geographical region of interest; (iii) designating one of the detected cell sites as a primary cell site and at least one of the remaining detected cell sites as secondary cell sites; (iv) for each point: comparing the received signal strength for the primary cell site with a respective received signal strength for each of the secondary cell sites; (v) choosing a favoured point from the plurality of points based on said comparisons, and (vi) determining the likely location of the device based on the location of the favoured point. The method of the second aspect is a method for determining a likely location of a device. A method according to the second aspect uses a geographical region of interest. However, the geographical region of interest in the second aspect is not necessarily derived in accordance with a method of the first aspect. For instance, the geographical region of interest could be specified by a user. The skilled person will appreciate that features described in respect of the first aspect are readily applicable to the second aspect, and vice versa.

Optionally, step (iii) includes: for each point: using a radio propagation model, calculating a primary signal strength distance, p_RSS_d, between the primary cell site and the device based on the measured signal strength from the primary cell site and a transmission power from the primary cell site, and calculating a primary real-world distance, p_RW_d, between the primary cell site and the respective point using a location of the primary cell site, and calculating a primary fraction, PF, where PF = (p_RSS_d - p_RW_d) / p_RSS_d; for each secondary cell site: using the radio propagation model, calculating a respective secondary signal strength distance, s_RSS_d between the respective secondary cell site and the device based on the measured signal strength from the respective secondary cell site and a transmission power from the respective secondary cell site, and calculating a respective secondary real-world distance, s_RW_d, between the respective secondary cell site and the respective point using a location of the respective secondary cell site, and calculating a respective modified secondary distance, s_M_d, where s_M_d = s_RSS_d + (s_RSS_d * PF); calculating a respective secondary weight, sW, where sW = abs(s_M_d - s_RW_d); and calculating a point sum, PS, for each point, the respective point sum being equal to the sum of the secondary weights corresponding to the respective point. According to a third aspect, a method of measuring a coverage of a mobile network, is provided, including the steps of: at each of a plurality of real world locations: determining a likely location of a device located at the respective real-world location according to a method of the first or second aspect, and; recording in a database the determined likely location and a network diagnostic measured by the device at the time that the detected cell sites were detected.

Each mobile device may send its measurements to a remote server, where a likely location for that mobile device is calculated according to the present method. The likely location can be combined with the measurements of the wireless signals to form a network measurement from a particular location (the likely location of the mobile device).

Accordingly, the performance of the communication network can be measured. Using the measurements of the network, the network may be optimised. For example, a network operator can identify areas in which there is significant overlap in coverage of cell sites. Such overlap may be reduced by reducing the transmission power of some or all of the cell sites concerned. Measuring the network coverage can also help a network operator in network planning. For example, areas of poor coverage can be identified, which may indicate the need to improve cell site coverage in that area of poor coverage.

It will be noted that that devices of the present invention need not have any further interaction with the method other than performing and sending measurements of the communication network. The device does not need to be informed that the information is used to determine a likely location, nor that the device is effectively being used to monitor network performance.

Optionally, including displaying the network diagnostic on a map.

Accordingly, the coverage of the network can be conveniently assessed by a user.

Optionally, the network diagnostic includes at least one of: a serving cell received signal strength, and; a neighbouring cell received signal strength.

In general, it will be appreciated that the methods of the first or second aspect could be performed on the device, where the cell plan is accessed remotely. Alternatively, the method may be performed remotely from the device, where the device sends details of the measurements of the wireless signals to a remote server, and the remote server determines the likely location of the device. The likely location of the device may be returned to the device. Alternatively, the device may send the details of the measurements of the wireless signals to a remote server, where the likely location is calculated, but the likely location is not returned to the mobile device. Instead, the likely location may be sent or stored elsewhere. In other words, the user or owner of the device may be unaware that a likely location of the device has been determined. It will be appreciated that there are many options for the separation of the steps associated with the present invention.

The method of the present invention may provide a transparent query point for other LBS applications running on the device. For example, an application may make a request for a current location of the device, whereupon a likely location of the device is calculated (locally or remotely), and returned to the LBS application in question for further use. The LBS application may be unaware of how the likely location has been determined. In other words, the method of determining a likely location is backwards compatible with applications and devices that has previously used GPS locations or locations derived in another way.

The following describes the application of the method to a mobile telephony device and a cellular mobile telephony communication network. However, as discussed above, it is noted that the present invention is suitable for application to other categories of communication network. For example, the device may be a WiFi-enabled device configured for wireless communication with a WiFi communication network.

So that the invention may be more readily understood, and so that further features thereof may be appreciated, embodiments of the invention will now be described by way of example with reference to the accompanying drawings in which:

Figure 1 is an overview of a scenario in which a method according to the present invention can be used;

Figure 2 is an overview of the system for performing a method according to the present invention;

Figure 3 is an overview of the stages of an embodiment;

Figure 4 is an overview of the preparation stage of the method of Figure 3; Figure 5 is a schematic of a first cell site detection scenario; Figure 6 is an overview of a polygon intersection stage of the method of Figure 3; Figure 7 is a schematic of a second cell site detection scenario;

Figure 8 is a schematic to demonstrate a full circle routine in the second cell site detection scenario; Figure 9 is a schematic to demonstrate a polygon extension routine in the second cell site detection scenario, and;

Figures 10A to 10F are an overview of the steps of a grid method in accordance with a first embodiment;

Figure 11 illustrates a grid method in accordance with a second embodiment, and; Figures 12A and 12B are a demonstration of the capability of the present invention.

Figure 1 shows a mobile device 1 , which can connect to a serving cell site 2 via wireless communication link 3. The mobile device 1 is an example of a device. The serving cell site 2 is part of a mobile network, which includes a plurality of such cell sites. The wireless communication link 3 is a two-way communication link that allows the mobile device 1 to send data to, and receive data from, the serving cell site 2. The serving cell site 2 is connected via a network connection 4 to the mobile network 5. The network connection 4 may be a wireless connection or a wired connection. The network connection 4 may be formed across the internet in a conventional manner. The mobile network 4 includes a server 6. Together the mobile device 1 and the server 7 may have a client-server relationship. The mobile device 1 is served by the serving cell site 2, which provides access for the mobile device 1 to the mobile network 5. However, because the mobile device 1 can potentially be moved (i.e. its location relative to the serving cell site 2 can change), the mobile device 1 monitors wireless signals from other neighbouring cell sites so that one of those

neighbouring cell sites can become the serving cell site when that is appropriate. This process of a change of serving cell site is called a cell handover. A cell handover may occur, for example, when the mobile device 2 is moved to be closer to a neighbouring cell site than to the serving cell site 2. Figure 1 shows an example of such a neighbouring cell site 7. The monitoring of the neighbouring cell site 7 is indicated by the cell measurement 8. The cell measurement 8 involves the mobile device 1 measuring at least one parameter of the wireless signal from the neighbouring cell site 7. The measurement 8 may include the received power of the wireless signal from the neighbouring cell site 7, which may in turn be used to determine a Received Signal Strength (RSS) for the neighbouring cell site 7. The wireless signal from the neighbouring cell 7 may also be decoded at least partially to extract information from the wireless signal concerning the neighbouring cell 7, for example a cell identifier of the neighbouring cell 7. Similar measurements of the wireless signal from the serving cell site 2 are also being performed by the mobile device 1.

While Figure 1 shows a serving cell site 2 and one neighbouring cell site 7, it will be appreciated that a mobile device 1 may detect the wireless signals from a plurality of neighbouring cell sites 7 simultaneously, as well as the wireless signal from the serving cell site 2. The mobile device 1 is configured to produce a network monitoring report (NMR), which includes parameters of the serving cell site 2 and any detected neighbouring cell sites 7. NMRs are produced periodically by the mobile device 1 , and are used to determine if and when the mobile device 1 should perform a cell site handover.

The mobile device 1 includes a subscriber identity module (SIM). The SIM identifies the user of the mobile device 1. Furthermore, the SIM has some limited compute capability, and can run small simple computer applications, referred to herein as SIM applets. In the method according to an embodiment, one such geo SIM applet takes an NMR, adds data to identify the mobile device and/or user, the time that the network measurements in the NMR were made, for example. The NMR and this additional information is packaged into a network report, which is sent to the server 6. The network report is an example of a measurement report. The network report may be sent via at least one Short Messaging Service (SMS) message or via internet protocol data, for example. In any case, the server 6 collates network reports received from the mobile device 1 and stores them in a database. Along with the network report, important information may also be stored. The important information may include, for example, a time stamp at which the corresponding NMR was made, a likely location for the device, and other key information extracted from the NMR.

The SIM and/or geo SIM applet includes some SIM configuration information, including: Con iguration Description

A list of Mobile Country Code & Mobile

Network Code (MCC : MNC ) pair data that

Home Networks specifies which mobile network is to be

considered as a home network by the mobile device .

The SMS short/long code address and IP

Destination

address to which the geo SIM applet

Addresses

uploads network reports.

The mobile device can use either SMS or IP

Bearer service as a bearer service to carry network

selection reports to the server. This configuration controls which bearer service is used.

Determines when network reports can be

Roaming support uploaded to the server when the subscriber is roaming.

Enable/Disable Simple enable/disable functionality.

Different network operators may produce different NMRs and consequently network reports of differing format. Different network protocols may also result in different NMRs and network reports of differing format. Thus, before each network report is stored in the database, the format of the network report may be standardised by the server 6.

The client-server relationship between the mobile device 2 and the server 6 is shown in more detail in Figure 2.

At least one mobile device 1 and geo SIM applet is shown connected to the server 6. The mobile device 1 is initially connected to a query manager 8, which is a component of the server 6. Also connected to the query manager 8 may be at least one location based service (LBS) application 9. Each LBS application 9 may send a request to the server 6 to request a location of a particular mobile device 1 for each of a set of mobile devices. An LBS application 9 may be installed on the mobile device 1 for which the location is requested, on a separate mobile device, or on another device altogether.

Figure 2 also shows an administration portal 10, which is connected to a cell site validator 1 1. The cell site validator 11 is a component of the server 6. The administration portal 10 is also connected to an account manager 12. The account manager 12 is also a component of the server 6. The account manager 12 is also shown as connected to the query manager 8. The account manager 12 is also connected to an accounts database 13.

The query manager 8 is also connected to a location database 14.

The server 6 includes a positioning engine 15. The positioning engine 15 is connected to the cell site database 16 that forms the cell plan.

The positioning engine 15 is configured to determine a likely location for the mobile device 1 in accordance with an embodiment. The operation of the positioning engine 15 will now be described.

In an alternative and similar arrangement, a positioning engine having an application programming interface (API). The API is configured to receive an NMR from a device, and the positioning engine is configured to determine the likely location of the device using the information contained in the NMR. The positioning engine can then return the likely location of the device. The cell plan may be processed and inserted into a positioning engine database in the positioning engine by an external process (most likely, a human being). The cell plan, having been processed and included in the positioning engine, is then accessible for use in the determination of the likely location (see below). A separate LBS enablement server/process handles requests from an LBS device by calling the positioning engine. The requests may include, for example, timed query for a likely location, historic records of likely location, billing, etc... Figure 3 illustrates the most generalised steps performed by the positioning engine 15. A preparation stage 17 is followed by a polygon intersection stage 18. The polygon intersection stage 18 is, in turn, followed by a likely location stage 19.

Figure 4 illustrates the preparation stage 17. The preparation stage 17 includes plurality of steps. In a first decoding step 20, the NMR is extracted from a network report that was received by the server 6 from a mobile device 1 , and ultimately from the geo SIM applet. In a second cell information extraction step 21 , from within the NMR (which includes measurement of the wireless signal from each of a plurality of detected cell sites), the cell site identification information and corresponding measured signal strength information is extracted for each detected cell site. In a third cell lookup step 22, using the cell site identification information, a lookup request 22A is made to the cell plan 22B. The cell plan 22B includes a plurality of cell site records stored in a database. Each cell site record includes information about a particular cell site in the mobile network. In response to the lookup request 22A, information regarding the plurality of detected cell sites (as identified from the NMR) is returned 22C. The returned information may comprise the cell site records corresponding to the cell site identification information extracted from the NMR.

Each cell site record includes:

• Cell global ID (for example, MCC, MNC, LAC/TAC, CID);

• Physical cell ID (for example, BCCH and BSIC for 2G, PSC for 3G and PhysCelllD for 4G)

• Real-world location of the cell site (for example, latitude and longitude).

Each cell site record may also include one or more additional parameters of the cell site, for example:

• Beam azimuth; · Horizontal beam width;

• Antenna height;

• Transmission power;

• Transmission frequency, and;

• Max antenna range; If these additional parameters are not available for a particular cell site, then they may be assigned default values. By way of example only, the default values may be:

• Beam azimuth = 0 degrees; • Horizontal beam width = 360 degrees;

• Antenna height = 50 metres;

• Transmission power = 33dBm (decibel-milliwatts);

• Transmission frequency = 897.5 MHz to 942.5 MHz (for a 2G mobile network), 1880.0 MHz to 1960.0 MHz (for a 3G or 4G mobile network). For WiFi, for example, the transmission frequency may be 2.4GHz.

For a default value for maximum antenna range, a minimum detectable signal strength of - 110 dBm to -140 dBm, depending on the cell access technology, is used for a typical mobile device. Using this minimum detectable signal strength, the default value for the maximum detectable range of the cell site is calculated. The calculation of the default maximum detectable distance may depend on the type of area in which the cell site is located. For example, the cell site record may include a designation of the region type, for example Urban, Sub-urban, Dense urban, or rural/small city. The maximum detectable distance of a cell site in a dense urban environment is likely to be smaller than that of cell site in a rural environment. The calculation of the default value for the maximum detectable distance may take into account the region types and the consequent environmental differences.

Either directly or via calculation, the cell site records are used to determine a cell site coverage shape for each of the detected cell sites.

In a coverage shape step 23, the information in the cell site records is used to determine a cell site coverage area for each detected cell site as identified in the network report. A cell site coverage shape is determined by the parameters from the cell site records or, if some of those parameters are not available, they are calculated as default values, as above. Each cell site coverage shape corresponds to an expected coverage area or region of the cell site, in which it would be expected that a mobile device would be able to detect that cell site. If a mobile device is located outside that cell site coverage shape, then the expectation is that the mobile device would be unable to detect that cell site.

In the ideal situation, the cell site records accurately predict the coverage area of the detected cell sites. As such, a unique overlap region of the coverage shapes of the detected cell sites should correspond to a real world geographical area in which the mobile device is located because that is the only geographical area in which the mobile device could have detected all of the detected cell sites. In a non-ideal, real world, situation the predicted coverage shapes for the detected cell sites may not overlap in a unique overlap region. In general, this is because the information in the cell site records does not describe accurately the real-world coverage of the cell sites. Reasons for this failure of the cell site records to describe accurately the real-world detectability of the cell sites may include reflection of the wireless signal from a cell site, deflection of the wireless signal from a cell site, and interference to the wireless signal from the cell site. Alternatively, or in addition, information may simply be missing from the cell site records, or the information in the cell site records may be inaccurate.

Cell site polygons

There are a number of ways to mathematically describe and define the cell site coverage shapes. However, the inventors have discovered that particularly computationally

advantageous way is to represent each cell site coverage area using a cell site polygon. Each cell site polygon is a set of vertices (latitude - longitude pairs, for example), which together define the perimeter of the cell site coverage area. By representing each cell site coverage shape as a cell site polygon, the downstream processing of the cell site polygons (described below) is made computationally simpler and faster.

As such, in a polygon step 24, a cell site polygon is calculated for each cell site coverage shape. It will also be appreciated that the cell site polygon may be immediately derived from the information in the cell site record. As an example, for a sector-shaped cell site, a start angle of the sector and an end angle of the sector, and a radius of the cell site may be used as inputs to determine a finite set of points describing the perimeter of the sector-shaped cell site. The finite set of points is the cell site polygon. It will be appreciated that increasing the number of points in the polygon increases the complexity of the shape that the polygon can represent. Circular cell site coverage shapes can thus be represented by a cell site polygon.

Generic overlap Figure 5 illustrates a detected cell site scenario. Three detected cell site polygons 25 of three detected cell sites 2, 7 are illustrated. In Figure 5, the cell site polygons 25 have been determined using the cell site records for the detected cell sites 2, 7. The cell site polygons 25 in Figure 5 are sector-shaped. However, a cell site polygon 25 may also have a generally circular shape surrounding the cell site location (i.e. with the cell site location generally at the centre of the circular shape cell site coverage shape/cell site polygon).

In Figure 5, a unique overlap region 26 of the cell site polygons 25 is shown. The unique overlap region 26 is the region in which the cell site polygons 25 are co-incident with one another (or "overlap"). If there is a unique overlap region 26, then this is the geographical region of interest as predicted by the information in the cell site records for the detected cell sites 25. A mobile device 1 located within the unique overlap region is predicted to be able to detect the detected cell sites 2, 7. The unique overlap region 26 may itself be mathematically represented as an overlap polygon, which represents the perimeter of the unique overlap region 26.

Non-overlap

Figure 6 is a flow chart that shows the steps that may be taken in order to calculate a geographical region of interest. The inputs for the polygon intersection stage are the cell site polygons 25 (as shown in

Figures 5 and 7, for examples). The detected cell sites for which cell site polygons are used may be limited in number, i.e. not all of the detected cell sites may be used in the

downstream processing. For example, the three detected cell sites having the highest measured signal strength may be selected. At intersection check 27, it is determined whether or not there is a unique overlap region of the cell site polygons 25. The cell site polygons 25, however, do not always have a unique overlap region 26. Such a scenario is shown in Figure 7, for example. This may be the case where there is more than one overlap region (in other words, there is no unique overlap region), or where is no overlap between cell site polygons at all, as in Figure 7. If intersection check 27 determines that there is a unique overlap region of the cell site polygons 25, then the Yes or "Y" pathway from the intersection check 27 is taken. In which case, a unique overlap polygon defining the perimeter of the unique overlap region 26 is returned for further use as the geographical region of interest 28.

If, on the other hand, the intersection check 27 determines that there is no unique overlap region 26 of the cell site polygons 25), the No or "N" pathway from the intersection check 27 is taken.

If the "N" pathway from the intersection check 27 is taken, then a full circle routine is performed. The full circle routine includes calculating 29 a full circle polygon for each detected cell site, and performing a full circle intersection check 30. The full circle polygon is an example of the full circle coverage shape. In some embodiments, the first intersection check 27 that performs the check for a unique overlap region between the cell site coverage shapes may be omitted. In other words, the full circle routine is performed regardless of whether or not there is a unique overlap region of the cell site polygons. The full circle routine is described in more detail below.

During the full circle intersection check 30, it is determined whether or not the full circle polygons have a unique overlap region.

If the full circle intersection check 30 determines that the full circle polygons have do have a unique overlap region with one another, then the Yes or "Y" pathway from the full circle intersection check 30 is taken. In which case, an overlap polygon defining the perimeter of the unique overlap region of the full circle polygons is returned for further use as the geographical region of interest 28.

If the full circle polygons do not have a unique overlap region with one another, the No or "N" pathway from the full circle intersection check 30 is taken. In that case, a polygon extension routine is performed. The polygon extension routine is an example of the coverage area extension routine. The polygon extension routine includes incrementing 31 the radius of each full circle polygon for each detected cell site 2, 7 and performing an incremented full circle intersection check 32. During the incremented full circle intersection check 32 it is

determined whether or not the incremented full circle polygons have a unique overlap region with one another.

If the incremented full circle intersection check 32 finds that the incremented full circle polygons do have a unique overlap region with one another, an overlap polygon defining the perimeter of that unique overlap region of the incremented full circle polygons is returned as the geographical region of interest 28. If the incremented full circle intersection check 32 finds that the incremented full circle polygons do not have a unique overlap region with one another, then the radius of each incremented full circle polygon is incremented again, and the full circle intersection check 32 is performed again. This process is repeated until the incremented full circle intersection check 32 finds that the incremented full circle polygons do not have a unique overlap region with one another, or until a maximum radius of at least one of the incremented full circle polygons is reached or exceeded, for example. A comparison between a current radius of the incremented full circle polygon for the serving cell site 2 and a maximum radius is performed during a radius check 33 in order to determine if the maximum radius has been reached or exceeded. If the incremented radius of the incremented full circle polygon of the serving cell site is equal to or exceeds the maximum radius, then the cell site polygon of the serving cell site may be returned 34 as the

geographical region of interest. The maximum radius may be equal to an initial radius of the full circle polygon for the serving cell site multiplied by a maximum size factor. The maximum size factor may be equal to two, for example.

The steps of the method of Figure 6 are now described in more detail. In Figure 7, the detected cell sites 2, 7 each have a cell site polygon 25. The cell site polygons 25 have been determined, either directly or indirectly, using the information stored in the cell site records for the detected cell sites 2, 7. In the scenario of Figure 7, there is no cell site polygon overlap region, as there is in the scenario of Figure 5. As such, in the scenario of Figure 7, at least some of the cell site polygons 25 do not accurately reflect the real-world detectability of the corresponding cell site 2, 7 by the mobile device 1. This is because the mobile device 1 has, in fact, detected at least two of the three cell sites 2, 7, which according to the information in the cell site records, the mobile device 1 should not have been able to detect.

Full circle routine Figure 8 illustrates a scenario in which the full circle routine is applied. In general, each cell site polygon 25 is converted to a full circle polygon 35. Each full circle polygon 35 surrounds the location of the corresponding cell site 2, 7. The radius of the full circle polygon 35 may be equal to the maximum coverage extent of the cell site polygon 25. In particular, as can been in Figure 8, two of the full circle polygons overlap in a partial overlap region 36. However, the third of the detected cell sites 7 does not have a full circle polygon 35 that overlaps with the partial overlap region 36. Thus, there is no unique overlap region between the full circle polygons 35.

A mobile device may be located outside a horizontal angular extent of a cell site having a sector shape. By using the full circle polygons 35, each full circle polygon 35 covers a geographical area that is beyond the initial horizontal angular extent of the corresponding cell site polygon 25. Thus, by using the full circle routine, a geographical region of interest that includes such a geographical area beyond the initial horizontal extent can be determined even when the mobile device 1 detects one or more cell sites that, according to the information in the cell site records at least, the mobile device 1 should not be able to detect. Thus, by using the full circle routine it is possible to determine accurately a likely location for the mobile device 1 , even when the information in the cell site records does not describe accurately the real-world detectability of the cell site at the location of the mobile device 1. It will be appreciated that the cell site coverage polygon 25 of some or all cell sites may already correspond to a full circle if that is what is defined in the cell site record for the corresponding cell site. In this event, a full circle polygon 35 is not calculated for those cell sites already having a cell site polygon 25 that corresponds to a full circle.

As described above, the full circle polygons may be formed regardless of whether or not there is a unique overlap region between the cell site polygons.

In the scenario of Figure 8, it can be seen that because there is an overlap region 36 between two of the full circle polygons 35 but the full circle polygon 35 of the other detected cell site does not overlap with the overlap region 36. In the scenario of Figure 8, the full circle intersection check 30 determines that there is no overlap region of the full circle polygons 35, and as such, the polygon extension routine is performed.

Polygon extension routine

In Figure 9, the detected cell sites 2, 7 are shown each having a cell site coverage polygon 25, a full circle polygon 35, and an incremented full circle polygon 37. The radius of each full circle polygon 35 has been incremented in radius to form the corresponding incremented full- circle polygon 37.

It is noted that Figure 9 is a schematic only. The size of the radius increment used to form each of the incremented full circle polygons 37 is not shown to scale, neither relative to the corresponding full circle polygon 35, nor relative to any of the other full circle polygons 35.

Each full circle polygon 35 may be incremented by an increment fraction of its radius prior to that particular incrementing step or of its initial radius, if different. Alternatively, each full circle polygon 35 may be incremented by an increment fraction of its own size prior to any incrementing steps (i.e. the radius of the full circle polygon immediately after it is first formed in the full circle routine, for example). In either scheme, the increment fraction may be 10%, for example. After the incremented full circle polygons 37 have been formed, then the incremented full circle intersection check 32 is performed (see Figure 6). The incremented full circle intersection check 32 determines whether or not there is a unique overlap region between the incremented full circle polygons 37. If the incremented full circle intersection check 32 finds a unique overlap region 38 of the incremented full circle polygons, then that unique overlap region 38 is returned to be used as the geographical region of interest. Providing a likely location - four options

At this stage, a likely location for the mobile device is calculated during the likely location stage 19 (see Figure 3). The present invention provides one of four different likely locations of the mobile device depending on the quantity of information available.

These four likely locations are referred to as follows, in order of increasing accuracy: · A cell site location;

• A cell sector location;

• An overlap location, and;

• A "grid location". Cell site location The cell site location is the location of the serving cell site. This information may be included into the cell site record for the serving cell site. The cell site ID location may be provided as the likely location of the mobile device when the serving cell site is the only detected cell site, and the serving cell site has a circular coverage area.

Cell site location - sector shape The cell sector location is the centroid of the cell site coverage shape of a single detected cell site. The cell sector location may be provided as the likely location of the mobile device when the serving cell site is the only detected cell site, and the serving cell site has a sector- shaped coverage area.

Alternatively, if a Received Signal Strength (RSS) measurement of a wireless signal from the serving cell site is available (as measured by the mobile device), then instead of the centroid of the cell coverage area, an RSS distance may be calculated. The RSS distance being calculated using a COST Hata model, for example. The COST Hata model may use information from the cell site record of the serving cell site to calculate the RSS distance, for example, the transmission power of the cell site, the frequency of transmission, and the antenna height). In this case (i.e. when an RSS distance is available), the cell sector location may be equal to a position at the RSS distance from the serving cell site location along a line that is equidistant from the two radial edges of the sector shaped coverage area of the serving cell site.

Overlap location

The overlap location is the centroid of the overlap region, where the overlap region is determined as described above.

The grid method/location The most accurate method of calculating the likely location of the device is the "grid method", by which the grid location is calculated. Specifically, the grid method is method of calculating a likely location of the device from within a geographical region of interest. The grid method in accordance with a first embodiment is described below.

Figure 10A shows two cell site polygons: a serving cell site polygon 39 and a neighbouring cell site polygon 40. A geographical region of interest 41 is located generally between the serving cell site polygon 39 and the neighbouring cell site polygon 40. The perimeter of the geographical region of interest 41 is mathematically described by an overlap polygon 42.

While the geographical region of interest 41 may correspond to an overlap region derived according to the method described above, it may equally have been derived according to another method. The grid method for calculating the likely location for the mobile device does not depend on how the geographical region of interest 41 was determined.

Figure 10B illustrates the serving cell site polygon 39 and the neighbouring cell site polygon 40 with a plurality of points distributed within the overlap region polygon 42. The plurality of points are distributed in a grid of points 43. The grid of points 43 has a uniform grid spacing in the example of Figure 10B, however that is not necessarily the case. Non-uniform point spacing is also possible.

The skilled person will appreciate that there are a number of potential methods to create a grid of points 43 within a region. However, one method to create the grid of points 43 within the overlap polygon 42 is as follows. Making grid points

First, a bounding box containing the overlap region polygon 42 is created. The bounding box is the smallest rectangular box that contains all of the vertices of the overlap polygon 42.

Second, a grid spacing is calculated. The grid spacing is the distance between each grid point and each of its immediate neighbours. The grid spacing may be defined as the maximum range of the serving cell divided by a grid factor. The grid factor may be 200, for example.

Third, positions corresponding to potential grid points within the bounding box are iterated across. That is, the locations of potential grid points are calculated as distributed across the bounding box using the grid spacing.

Fourth, the location of each potential grid point within the bounding box is calculated. Noting that the overlap region polygon 42 is also located within the bounding box, the location of each potential grid point is tested to check whether or not it is located within the overlap polygon 42. If the location of the potential grid point is within the overlap polygon 42, then said potential grid point is added to the grid of points 43 located within the overlap region polygon 42. The result is the grid of points 43 having the grid spacing as calculated above, distributed within the overlap polygon 42 as shown in Figure 10B.

Optionally, the grid spacing may be reduced by a reduction factor if the grid spacing is large relative to the size of the bounding box. For example, if twice the initial grid spacing is smaller than or equal to the extent of the bounding box in one or both dimensions, then the grid spacing may be reduced. For example, the grid spacing may be reduced by a reduction factor of 100. Recall that for each detected cell site a measurement of the received signal strength is known from the NMR, as measured by the mobile device. The measured signal strength may be represented by the RSS of the signal. In general, a primary cell site is designated from among the detected cell sites. The primary cell site may be designated as the detected cell site having the maximum measured received signal strength. The primary cell site may also be the serving cell site for the mobile device. Next, a number of secondary cell sites are designated from the remaining detected cell sites. The secondary cell sites may include a one or more of the neighbouring cell sites from the detected cell sites (excluding the primary cell site). The secondary cell sites may be selected from the detected cell sites as the detected cell sites having the maximum measured received signal strength (excluding the primary cell site). The number of detected cell sites that are designated as secondary cell sites may be limited in number. For example, the number of secondary cell sites may be limited to a maximum of two. In figures 10A-F, the serving cell site 39 is the primary cell site and the neighbouring cell site 40 is the secondary cell site. For the primary cell site 39, a primary cell site RSS distance, p_RSS_d, is calculated.

p_RSS_d corresponds to the distance between the mobile device and the primary cell site location. p_RSS_d is calculated based on the RSS of the primary cell site (as measured by the mobile device), and the transmission power of the primary cell site.

For each of the secondary cell sites 40 a respective secondary cell site RSS distance, s_RSS_d, is calculated. s_RSS_d corresponds to the distance between the mobile device and the respective secondary cell site location calculated based on the RSS of the secondary cell site (as measured by the mobile device), and the transmission power of the secondary cell site.

In the case of p_RSS_d and s_RSS_d, by estimating the transmission power of the respective cell site, or by using parameters in the cell site record to determine the

transmission power, and comparing that transmission power with the RSS for the respective cell site, an attenuation of the wireless signal that has occurred between the transmitter of the respective cell site and the mobile device is calculated. Using a radio propagation model, an RSS distance is calculated from that attenuation. The radio propagation model may be a COST Hata propagation model. The RSS distance may also depend on the frequency of the wireless signal. The frequency of the wireless signal may also be known from the cell site record, or simply by virtue of the type of wireless signal that is being measured.

Figure 10C shows a primary RSS region 44 is shown surrounding the location of the primary cell site 39. The radius of the primary RSS region 44 is equal to p_RSS_d. A secondary RSS region 45 is shown surrounding the location of the secondary cell site 40.

The radius of the secondary RSS region 45 is equal to s_RSS_d.

The next stage is of the grid method is to iterate across each of the points in the grid of points 43. For the sake of clarity, the following discussion refers to a test point 46, and the calculations are described in respect of the test point 46. However, these calculations are performed for each of the points in the grid of points 43.

Figure 10D illustrates a first step of the calculation that is performed for the test point 46. First, p_RW_d is calculated. p_RW_d is the real-world distance between the primary cell site location and the test point 46.

Second, the distance 47 between the test point 46 and the edge of primary RSS region 44 is calculated as (p_RSS_d - p_RW_d), which may be referred to as delta! deltal is expressed as a fraction of p_RSS_d, as the primary fraction, PF, where:

PF = deltal / p_RSS_d

PF is thus a measure of how close the primary RSS distance is to matching the distance between the test point 46 and the primary cell site location.

Figure 10E illustrates a second step of the calculation that is performed for the test point 46 for each of the secondary cell sites. During the second step, the respective secondary RSS distance, s_RSS_d, is augmented by PF to form a respective modified secondary distance, s_M_d, as follows: s_M_d = s_RSS_d + (PF * s_RSS_d)

Thus, if PF is low, then the respective modified secondary distance s_M_d is augmented by a relatively small amount, and vice versa. Figure 10E shows a secondary modified RSS region 48 having a radius equal to s_M_d.

Next, for each of the secondary cell sites, the distance 49 between the test point 46 and the edge of the respective modified secondary RSS region 48 is calculated as abs(s_M_d - s_RW_d), which may be referred to as a respective value for delta2. It will be appreciated that where the secondary cell site radius is augmented by a small amount, then s_M_d is similar to s_RSS_d. This happens when, effectively, the mobile device has a true location at which the measured signal strength from the secondary cell site is well matched by the PF, which depends on the degree of match of the primary cell site. delta2 therefore amounts to a comparison between the received signal strength for the primary cell site and a respective received signal strength for the respective secondary cell site.

To take account of multiple secondary cell sites, the delta2 values for each point are summed together to form a respective secondary weight, sW = sum(delta2). The summation of the delta2 values for a particular point represents a measure of the degree to which mutually augmented secondary cell site parameters (that is, radii of detection) match the measured values. A respective point weight is then calculated for the test point 46 as, PW = 1/SW.

At the conclusion of the iteration through all of the points in the grid of points 45, the location of the point having the highest value of point weight is returned as the likely location 50 of the mobile device.

Grid method optimisation

In the grid method in accordance with the first embodiment described above, an evenly spaced grid of points is formed across the geographical region of interest. Each of those points is evaluated, and the likely location is determined to be the location of the favoured point chosen from the grid of points.

A grid method in accordance with a second embodiment is described below, and is illustrated in Figure 1 1.

In first grid stage, a first grid of points 51 having a first grid spacing is formed across the geographical region of interest 52. The geographical region of interest 52 may be calculated according to the cell site shape overlap method described above, or may be determined according to a different method.

The first grid spacing is equal to the distance between neighbouring points of the first grid of points 51. Each point of the first grid of points 51 is evaluated in accordance with the method of the first embodiment. In other words, a favoured first point 53 is chosen from the first grid of points.

The first grid spacing may be 500 metres. The first grid of points 51 may cover a square area with sides of length 10 kilometres.

In a second grid stage, a second grid of points 54 having a second grid spacing is formed. The second grid spacing is smaller than the first grid spacing. The second grid spacing may be smaller than the first grid spacing by a reduction factor. The reduction factor may be 2. In other words, the second grid spacing may be half the first grid spacing. Evidently, if the second grid spacing is reduced by a reduction factor of 2 relative to the first grid spacing, then the area covered by the second grid of points 54 is reduced by a factor of 4 relative to the area covered by the first grid of points 51. The second grid of points 54 is centred on the favoured first point 53. Each point of the second grid of points 54 is evaluated in accordance with the method of the first embodiment, and a favoured second point 55 is chosen from the second grid of points 54. The second grid of points 54 may have the same total number of points as the first grid of points 51. There may be subsequent grid stages, for example, third, fourth, fifth, sixth, seventh and eighth stages, etc. During the grid stages, grids of points having progressively smaller grid spacing are formed. Each subsequent grid of points is centred on the favoured point chosen from among from the grid of points in the immediately preceding stage. Each of the grids of points may have the same total number of points. Each of the grid of points may be arranged in an n x n grid, where, for example, n = 21.

This repeated formation and evaluation of grids of points that are centred on the favoured point of the preceding grid of points may be repeated until the grid spacing is equal to or smaller than a minimum grid spacing. The grid of points having the grid spacing that is equal to or smaller than a minimum grid spacing is the final grid of points. The likely location of the device may be determined to be equal to the location of the favoured point chosen from the final grid of points.

The minimum grid spacing may be 1 metre, for example. By using the grid method in accordance with a second embodiment, the likely location of the device is arrived at over the course of a plurality of grid stages, each grid stage having higher resolution (i.e. smaller grid spacing) than the preceding grid stage. In this way, an accurate likely location for the device can be determined from within a large geographical region of interest, while minimising the number of test point evaluations. The number of test point evaluations is significantly reduced when compared to a grid of points having the coverage area of the first grid whilst also having a grid spacing that is equal to or smaller than a minimum grid spacing. Figures 12A and 12B illustrate likely locations of a mobile device that have been determined according to the grid method.

Figure 12A shows an area 56 of a map in an urban area. A mobile device was moved along the path 57. The passage of the path 57 was measured accurately using a conventional GPS device included in the mobile device. The accuracy of the GPS device is such that the path closely follows the true real-world path taken by the mobile device.

Figure 12B shows the same area 56 of the map. In Figure 12B, a plurality of markers 58 are indicated on the area 56. Each marker 58 is shown at a likely location of the mobile device determined according to the present invention. The likely locations were determined while the mobile device was travelling along the path 57 (as shown in Figure 12A). The likely locations were not determined at equal time or distance intervals along the path 57.

It will be appreciated that the markers 58 in Figure 12B fall accurately on the path 57 as shown in Figure 12A. The likely locations derived according to the grid method therefore accurately reproduce the GPS measured locations (as signified by the path 57). Of course, the likely locations of the mobile device do not rely on or use GPS measurements.

It will be noted that the markers 58 of Figure 12B are shown connected by straight lines. These straight lines are simply an artefact of the software used to prepare Figure 12B. The straight lines in Figure 12B are not intended to reflect a real-world path travelled by the mobile device.

When used in this specification and claims, the terms "comprises" and "comprising" and variations thereof mean that the specified features, steps or integers are included. The terms are not to be interpreted to exclude the presence of other features, steps or integers. The features disclosed in the foregoing description, or in the following claims, or in the accompanying drawings, expressed in their specific forms or in terms of a means for performing the disclosed function, or a method or process for obtaining the disclosed results, as appropriate, may, separately, or in any combination of such features, be utilised for realising the invention in diverse forms thereof. While the invention has been described in conjunction with the exemplary embodiments described above, many equivalent modifications and variations will be apparent to those skilled in the art when given this disclosure. Accordingly, the exemplary embodiments of the invention set forth above are considered to be illustrative and not limiting. Various changes to the described embodiments may be made without departing from the spirit and scope of the invention.

Claims

1. A method for determining a likely location of a device, the device being configured for wireless communication with a communication network including a plurality of cell sites; the method including the following steps:

(a) detecting by the device a respective wireless signal from each of a plurality of detected cell sites;

(b) accessing a cell plan comprising a database, the database including a plurality of cell site records, each cell site record corresponding to a cell site in the communication network,

(c) for each of the detected cell sites, identifying the corresponding detected cell site record in the database;

(d) determining a geographical region of interest based on information contained in the cell site records corresponding to the plurality of detected cell sites

(e) determining the likely location of the device within the geographical region of interest.

2. A method according to claim 1 , wherein step (d) includes,

for each detected cell site:

determining a cell site coverage shape, the cell site coverage shape corresponding to a predicted geographical area of coverage of said cell site as predicted by the information in said respective cell site record.

3. A method according to claim 2, wherein step (d) includes determining whether or not all of the cell site coverage shapes have a unique overlap region with one another, and wherein

if it is determined that all of the cell site coverage shapes do have a unique overlap region with one another, then the unique overlap region is determined to be the geographical region of interest.

4. A method according to claim 3, wherein if it is determined that all of the cell site coverage shapes do not have a unique overlap region with one another, then the method further includes executing a full-circle routine:

the full-circle routine including the steps of:

for each of the cell site coverage shapes, calculating a full-circle coverage shape surrounding a corresponding cell site location; determining whether or not all of the full-circle coverage shapes have a unique overlap region with one another, and;

if it is determined that all of the full-circle coverage shapes do have a unique overlap region with one another, then the unique overlap region of said full circle coverage shapes is determined to be the geographical region of interest.

5. A method according to claim 2, wherein the method further includes executing a full- circle routine:

the full-circle routine including the steps of:

for each of the cell site coverage shapes, calculating a full-circle coverage shape surrounding a corresponding cell site location;

determining whether or not all of the full-circle coverage shapes have a unique overlap region with one another, and;

6. A method according to claim 4 or claim 5, the method further including:

a coverage shape extension routine, including:

where all of the full-circle coverage shapes do not have a unique overlap region with one another, for each of the full-circle coverage shapes, incrementing the radius of said full-circle coverage shape by a radial step;

determining whether or not all of the incremented full-circle coverage shapes have a unique overlap region with one another, and;

if it is determined that all of the incremented full-circle coverage shapes do have a unique overlap region with one another, then the unique overlap region of said incremented full circle coverage shapes is determined to be the geographical region of interest.

7. A method according to claim 6, wherein, for each incremented full-circle coverage shape, the respective radial step is equal to a fraction of an original full circle radius of the respective full-circle coverage shape.

8. A method according to claim 6 or claim 7, the method further including repeating the coverage shape extension routine until the radius of at least one of the incremented full-circle coverage shapes exceeds a maximum radius or until the incremented full-circle coverage shapes do have a unique overlap region with one another.

9. A method according to claim 8, wherein the maximum radius is proportional to an

5 original radius of the full circle coverage shape for a serving cell site that is providing network access to the device from among the plurality of detected cell sites.

10. A method according to any preceding claim, wherein measurement information describing the detection by the device of the respective wireless signal from each of the0 plurality of detected cell sites is sent to a remote server as a measurement report.

1 1. A method according to claim 10, wherein the device sends the measurement report to the server upon receipt by the device of a command signal. 5

12. A method according to claim 11 , wherein the command signal includes reporting instructions, the reporting instructions dictating when the device should send at least one measurement report.

13. A method according to any one of claims 10 to 12, wherein the device sends o periodically a measurement report to the server.

14. A method according to any preceding claim, wherein each cell site record for a respective cell site includes at least:

a cell site identifier of said respective cell site, and;

5 a cell site location of said respective cell site.

15. A method according to claim 14, wherein each cell site record for a respective cell site further includes at least one of:

a cell site transmission power of said respective cell site;

0 a cell site beam width of said respective cell site;

a cell site azimuth of said respective cell site, and;

a cell site maximum range of said respective cell site.

16. A method according to any one of claims 2 to 15, as dependent on claim 2, wherein5 each cell site coverage shape is calculated using the information contained in the respective cell site record.

17 A method according to any one of claims 2 to 16, wherein at least one of the cell site coverage shapes is represented as a cell site polygon.

18. A method according to any preceding claim, wherein:

step (a) includes, using the device, measuring a received signal strength of the wireless signal from each of the detected cell sites;

and step (e) includes:

(i) defining a plurality of points distributed within the geographical region of interest;

(ii) designating one of the detected cell sites as a primary cell site and at least one of the remaining detected cell sites as secondary cell sites;

(iii) for each point:

comparing the received signal strength for the primary cell site with a respective received signal strength for each of the secondary cell sites;

(iv) choosing a favoured point from the plurality of points based on said comparisons and

(v) determining the likely location of the device based on the location of the favoured point.

19. A method according to claim 18, wherein:

step (iii) includes:

for each point:

using a radio propagation model, calculating a primary signal strength distance, p_RSS_d, between the primary cell site and the device based on the measured signal strength from the primary cell site and a transmission power from the primary cell site, and

calculating a primary real-world distance, p_RW_d, between the primary cell site and the respective point using a location of the primary cell site, and

calculating a primary fraction, PF, where PF = (p_RSS_d - p_RW_d) / p_RSS_d;

for each secondary cell site:

using the radio propagation model, calculating a respective secondary signal strength distance, s_RSS_d between the respective secondary cell site and the device based on the measured signal strength from the respective secondary cell site and a transmission power from the respective secondary cell site, and

calculating a respective secondary real-world distance, s_RW_d, between the respective secondary cell site and the respective point using a location of the respective secondary cell site, and

calculating a respective modified secondary distance, s_M_d, where s_M_d = s_RSS_d + (s_RSS_d * PF);

calculating a respective secondary weight, sW, where sW = abs(s_M_d - s_RW_d);

and calculating a point sum, PS, for each point, the respective point sum being equal to the sum of the secondary weights corresponding to the respective point.

20. A method according to claim 19, further including calculating a point weight, PW, for each point, where PW = 1/PS.

21. A method according to claim 20 wherein the favoured point is the point having the maximum value of PW.

22. A method according to any one of claims 19 to 21 , wherein the primary cell site is a serving cell site for the device.

23. A method for determining a likely location of a device, the device being configured for wireless communication with a communication network including a plurality of cell sites; the method including the following steps:

(i) using the device, measuring a received signal strength of a wireless signal from each of detected cell sites;

(ii) defining a plurality of points distributed within a geographical region of interest;

(iii) designating one of the detected cell sites as a primary cell site and at least one of the remaining detected cell sites as secondary cell sites;

(iv) for each point:

(v) choosing a favoured point from the plurality of points based on said

comparisons, and

(vi) determining the likely location of the device based on the location of the favoured point.

24. A method according to claim 23, wherein:

step (iv) includes:

for each point:

calculating a primary fraction, PF, where PF = (p_RSS_d - p_RW_d) / p_RSS_d;

for each secondary cell site:

calculating a respective secondary weight, sW, where sW = abs(s_M_d - s_RW_d);

A method of measuring a coverage of a mobile network, including the steps of:

at each of a plurality of real world locations:

determining a likely location of a device located at the respective real-world location according to the method of any preceding claim, and;

recording in a database the determined likely location and a network diagnostic measured by the device at the time that the detected cell sites were detected.

26. A method according to claim 25, including displaying the network diagnostic on a map.

27. A method according to claim 25 or claim 26, wherein the network diagnostic includes at least one of:

a serving cell received signal strength, and;

a neighbouring cell received signal strength.