WO2015010976A1

WO2015010976A1 - Method and apparatus for associating information with access points with compressed identifiers

Info

Publication number: WO2015010976A1
Application number: PCT/EP2014/065201
Authority: WO
Inventors: Lauri Wirola; Laura Wirola; Jari Syrjärinne; Mikko Blomqvist
Original assignee: Here Global B.V.
Priority date: 2013-07-23
Filing date: 2014-07-16
Publication date: 2015-01-29
Also published as: GB201313110D0; GB2516461A

Abstract

In accordance with an example embodiment of the present invention, an apparatus comprises a receiver configured to receive a first uncompressed access point identifier, a processor configured to determine a compressed access point identifier corresponding to the first uncompressed access point identifier wherein the compressed access point identifier corresponds to a plurality of access points comprised in a radio map, and the processor further configured to associate at least one access point from the plurality of access points with the first uncompressed access point identifier based at least in part on a location.

Description

METHOD AND APPARATUS FOR ASSOCIATING INFORMATION WITH ACCESS POINTS WITH COMPRESSED IDENTIFIERS

TECHNICAL FIELD

[0001] The present application relates generally to associating information with access points represented with compressed identifiers.

BACKGROUND

[0002] Modern global cellular and non-cellular positioning technologies are based on generating large global databases containing information on cellular and non- cellular signals. The information may originate entirely or partially from users of these positioning technologies. This approach may also be referred to as "crowd-sourcing".

[0003] Information provided by users may be in the form of "fingerprints", which contain a location that is estimated based on, for example, received satellite signals of a global navigation satellite system, GNSS, and measurements taken from one or more radio interfaces for signals of a cellular and/or non-cellular terrestrial system. A location may comprise an area surrounding a geographical position, for example. In the case of measurements on cellular signals, the results of the measurements may contain a global and/or local identification of the cellular network cells observed, their signal strengths and/or path losses and/or timing measurements like timing advance, TA, or round-trip time. For measurements on wireless local area network, WLAN, signals, as an example of signals of a non-cellular system, the results of the measurements may contain at least one of a basic service set identification, BSSID, like the medium access control, MAC, address of observed access points, APs, the service set identifier, SSID, of the access points, and the signal strengths of received signals. A received signal strength indication, RSSI, or physical reception level may be expressed in dBm units with a reference value of 1 mW, for example.

[0004] Such data may then be transferred to a server or cloud, where the data may be collected and where further models may be generated based on the data for positioning purposes. Such further models can be coverage area estimates, communication node positions and/or radio channel models, with base stations of cellular communication networks and access points of WLANs being exemplary communication nodes. In the end, these refined models, also known as radio maps, RM, may be used for estimating the position of mobile terminals. [0005] Fingerprints do not necessarily have to comprise a GNSS based position. They may also include cellular and/or WLAN measurements only. In this case the fingerprint could be assigned a position for example based on a WLAN based positioning in a server. Such self-positioned fingerprints can be used to learn cellular network information, in case there are cellular measurements in the fingerprint. Moreover, in a set of WLAN measurements in a fingerprint there may be, in addition to measurements for known WLAN access points, also measurements for unknown access points and the position of the unknown access points can be learned through these self-positioned fingerprints. Finally, more data can be learnt of previously known access points based on self-positioned fingerprints.

[0006] It may be noted that even when using a mobile terminal having GNSS- capabilities, a user may benefit from using cellular/non-cellular positioning technologies in terms of time-to-first-fix and power consumption. Also, not all applications require a GNSS-based position. Furthermore, cellular/non-cellular positioning technologies work indoors as well, which is generally a challenging environment for GNSS-based

technologies.

SUMMARY

[0007] Various aspects of examples of the invention are set out in the claims.

[0008] According to a first aspect of the present invention, an apparatus comprises a receiver configured to receive a first uncompressed access point identifier, a processor configured to determine a compressed access point identifier corresponding to the first uncompressed access point identifier wherein the compressed access point identifier corresponds to a plurality of access points comprised in a radio map, and the processor further configured to associate at least one access point from the plurality of access points with the first uncompressed access point identifier based at least in part on a location.

[0009] According to a second aspect of the present invention, a method comprises receiving a first uncompressed access point identifier, determining a compressed access point identifier corresponding to the first uncompressed access point identifier wherein the compressed access point identifier corresponds to a plurality of access points comprised in a radio map, and associating at least one access point from the plurality of access points with the first uncompressed access point identifier based at least in part on a location. [0010] According to a third aspect of the present invention, the first

uncompressed access point identifier of the second aspect of the present invention is comprised in a radio signal observed at the location of the second aspect of the present invention.

[0011] According to further aspects of the present invention, computer programs are provided that are configured to cause methods in accordance with the second, third and fourth aspects to be performed.

BRIEF DESCRIPTION OF THE DRAWINGS

[0012] For a more complete understanding of example embodiments of the present invention, reference is now made to the following descriptions taken in connection with the accompanying drawings in which:

[0013] FIGURE 1 shows an example architecture of a positioning system;

[0014] FIGURE 2 shows an example system for generating and distributing partial RMs for offline usage in user terminals;

[0015] FIGURE 3 shows an apparatus embodying a process for associating information with APs with compressed identifiers according to an example embodiment of the invention;

[0016] FIGURE 4 is a flow diagram showing operations for associating information with APs with compressed identifiers in accordance with at least one embodiment of the invention; and

[0017] FIGURE 5 demonstrates how a partial radio map comprising compressed AP identifiers may be updated, according to an embodiment of the invention. DETAILED DESCRIPTION OF THE DRAWINGS

[0018] Positioning systems may function in two modes. The first mode is a terminal-assisted mode, in which a terminal performs measurements of cellular and/or non- cellular air interface signals and provides results of the measurements to a positioning server hosting a global cellular and/or non-cellular RM database. The server then provides a position estimate back to the terminal. This methodology is called online positioning and requires the terminal to have data connectivity whenever positioning service is needed.

[0019] The second mode is a terminal-based mode, an offline positioning technique, in which a terminal has a local copy of a RM, called a partial RM. This partial

RM is a subset of the global RM in form of WLAN RM offline files, for example. These files may be in the form of a database or any other form that is readable by a computer. There may be multiple such files, since it may be advantageous not to have a single global file, but several smaller ones so that the terminal may only download partial RM for a specific area, for example, a country or a city where a need for positioning is anticipated. This subset can also be pre-installed on the terminal. In at least one of the downloaded and pre-installed case, data in the subset may need to be refreshed at some point. Offline positioning techniques do not require the terminal to have data connectivity whenever positioning service is needed.

[0020] Offline positioning may be advantageous from a service perspective because it helps reduce load on positioning servers. Also, since the terminals are capable of positioning themselves without contacting a positioning server, the terminals may remain location aware all the time. Additionally, time-to-first-fix may be very short, since the device does not need to contact the server.

[0021] WLAN RM offline files can be very large in size. As an example, in an urban/suburban area covering roughly 10x10 km, there can be more than 10 million APs. This results in an average density of one AP every 10 m² or 400,000 APs per 2x2 km tile. Transferring location information for each of these APs from a server to a terminal consumes a lot of server resources, network bandwidth, storage space in the terminal and it can also be quite expensive to the consumer in the form of data charges. Thus, it is desirable to reduce the size of a partial RM and resultantly have smaller size WLAN RM offline files, while still maintaining an acceptable level of accuracy and availability in offline positioning. Availability of a positioning system is defined as the ratio of the number of successful positioning events to the total number of positioning requests. It can be appreciated that availability is an important metric affecting user experience and can be heavily affected if the number of APs in a radio map is reduced.

[0022] In a radio map file, large amount of data is consumed by identifiers of APs comprising the radio map. These AP identifiers may be BSSIDs or MAC addresses, for example. BSSIDs are 6-byte numbers which may be shortened, for example, by employing a digital compression algorithm, to reduce a size of a RM file. Various algorithms may be used to compress an AP identifier. One such algorithm is the CRC-16 ITU-T algorithm. An AP whose identifier is compressed may be called a compressed AP and an AP whose identifier has not been compressed may be called an uncompressed AP.

[0023] In a RM comprising 10 million APs, shortening of 6-byte SSIDs to 2- bytes will result in the amount of data consumed by AP identifiers being reduced from 60 M bytes to 20 M bytes. Such BSSID shortening, although very effective in reducing size of RM files, may result in ambiguities in identification of an AP within a RM. For example, shortening a 6-byte identifier to 2-bytes may result in multiple 6 byte BSSIDs mapping to the same 2 byte identifier. Then APs corresponding to each of these multiple BSSIDs will be represented in a RM with the same 2 byte identifier.

[0024] Embodiments of the present invention relate to reducing ambiguities in identification of APs represented in a radio map by compressed identifiers. When an uncompressed identifier of an access point represented in a radio map with a compressed identifier is determined, the uncompressed identifier is associated with the access point in the radio map. Based upon the associated uncompressed identifier, the access point may be uniquely identified at a later stage, without having to recompute the uncompressed identifier.

[0025] FIGURE 1 shows an example architecture of a positioning system. The positioning system of FIGURE 1 comprises a GNSS 101, a user terminal 102, a cellular network 103, WLAN systems 104, a positioning server 105, a collection/learning server 106 and a global RM database 107. Positioning server 105 and collection/learning server 106 may be co-located in a single site or apparatus, or alternatively they may be distinct in the sense that positioning server 105 is external to collection/learning server 106 and collection/learning server 106 is external to positioning server 105. Global RM database may be a standalone node, or it may be comprised in collection/learning server 106 and/or positioning server 105. The user terminal 102 may receive its GNSS based position from the GNSS 101. The GNSS could be GPS, GLONASS or any other satellite based navigation system. The user terminal may also receive radio signals from the cellular network 103. The cellular network 103 could be based on any kind of cellular system, for instance a GSM system, a 3rd Generation Partnership Project, 3GPP, based cellular system like a WCDMA system or a time division synchronous CDMA, TD-SCDMA, system, for example supporting high speed packet access, HSPA, a 3GPP2 system like a CDMA2000 system, a long term evolution, LTE, or LTE-Advanced system, or any other type of cellular system, like a WiMAX system. Cellular network 103 comprises a plurality of base stations or base transceiver stations as communication nodes. Furthermore, user terminal 102 may also receive signals from WLANs 104. WLANs 104 comprise at least one access point as a communication node. WLANs 104 may be based upon the IEEE 802.11 standards, for example. [0026] The user terminal 102 comprises a processor 1021, and linked to the processor, a memory 1022. Memory 1022 stores computer program code in order to cause the user terminal 102 to perform desired actions. Processor 1021 is configured to execute computer program code stored in memory 1022. The user terminal further comprises memory 1024 to store additional data such as, for example, partial RMs. The user terminal may further include at least one antenna in communication with at least one transmitter and at least one receiver to enable communication with the GNSS 101 , cellular network 103, WLANs 104, positioning server 105 and collection/learning server 106. The mobile terminal processor 1021 may be configured to provide signals to and receive signals from the at least one transmitter and the at least one receiver, respectively.

[0027] Although not shown, the user terminal 102 may also include one or more other means for sharing and/or obtaining data. For example, the apparatus may comprise a short-range radio frequency, RF, transceiver and/or interrogator so data may be shared with and/or obtained from electronic devices in accordance with RF techniques. The user terminal may comprise other short-range transceivers, such as, for example, an infrared, IR, transceiver, a Bluetooth™' BT, transceiver operating using Bluetooth™ brand wireless technology developed by the Bluetooth™ Special Interest Group, a wireless universal serial bus, USB, transceiver and/or the like. The Bluetooth™ transceiver may be capable of operating according to low power or ultra-low power Bluetooth™ technology, for example, Bluetooth low energy, radio standards. In this regard, the user terminal 102 and, in particular, the short-range transceiver may be capable of transmitting data to and/or receiving data from electronic devices within proximity of the apparatus, such as within 10 meters, for example. The apparatus may be capable of transmitting and/or receiving data from electronic devices according to various wireless networking techniques, including 6LoWpan, Wi-Fi, Wi-Fi low power, IEEE 802.15 techniques, IEEE 802.16 techniques, and/or the like.

[0028] The user terminal further comprises a collection client 1023. Collection client 1023 may comprise, for example, a software module stored in memory 1022, or in another memory comprised in user terminal 102. The collection client 1023 may be configured to collect information comprising at least one of the following to be sent to the collection/learning server 106:

• An estimate of the user terminal's location based on, for example, received satellite signals of the GNSS 101

• Measurements taken from signals of the cellular network 103. • Results of scanning of WLAN systems 104.

• Results of scanning of other short range radio signals.

[0029] The collection/learning server 106 receives this information and based on it, builds a database of AP locations and coverage areas of cellular base stations and APs, such as for example WLAN APs. Such a database may be called a global RM database 107 since the RMs stored in this database may not be specific to a country or a city. Rather, they may be global in nature. In some embodiments, collection/learning server 106 is configured to build a database of AP locations that does not comprise information on coverage areas of cellular base stations.

[0030] Once a reliable global RM database 107 is built, the positioning server

105 may serve online positioning requests from user terminals. A user terminal may take measurements of signals from cellular networks and/or perform WLAN scans and send them to the positioning server 105. The positioning server may refer to the global RM database and based at least in part upon the information provided by the user terminal, provide an estimate of the user terminal position.

[0031] If a data connection between the positioning server and a user terminal is unavailable or is undesirable, the terminal may rely on a positioning engine 1025 to serve positioning requests offline. A partial RM or a subset of the global RM in form of RM offline files, such as for example WLAN offline files, may be stored in the memory 1024 of the user terminal. With a partial RM pertaining to the area in which a user terminal is presently located stored in a memory of the user terminal, the user terminal may scan the WLANs and/or signals from cellular networks at its location and provide a list of observed AP identifiers and/or base stations identities to the positioning engine 1025. After consulting a partial RM stored in the user terminal 102 and based upon the observed AP identifiers and/or the base station identities, the positioning engine 1025 may estimate a location of the user terminal without sending a request to a positioning server. It should be noted that partial RMs may be based upon access points of short range wireless systems other than WLAN systems and a user terminal may scan for signals from at least one of these other short range wireless systems to estimate its position.

[0032] FIGURE 2 shows an example system for generating and distributing partial RMs for offline usage in user terminals. In accordance with an embodiment of the present invention, an offline WLAN RM generator, OW-RMG, 201 takes as inputs a global RM from a global database 202 and a list of WLAN APs to be included in a partial RM from an AP selector for partial RMs 203. In order to reduce a size of a partial RM, it is desirable to include only a subset of all APs in a partial RM to be stored on a user terminal. The AP selector for partial RMs 203 helps achieve this goal by identifying APs which are relevant to the performance of partial RMs. The AP selector for partial RMs 203 may comprise a memory. The selection of APs by the AP selector for partial RMs 203 may be based at least in part on the inputs provided by a user terminal 206. The OW-RMG 201 may further refine the list of APs received from the selector 203 based upon a set of at least one criterion. The OW-RMG 201 generates partial RMs based upon these inputs and transfers them for storage to the offline WLAN RM database 204. The partial RMs needed by the user terminal 206 are then transferred by the offline WLAN RM database 204 to the RM offline download server 205. In an embodiment of the invention, the offline WLAN RM database 204 may be absent and a partial RM file may be transmitted directly from the OW-RMG 201 to the RM offline download server 205. From the download server, a partial RM file may be downloaded by the user terminal 206 or any other user terminal. The user terminal may have the structure and circuitry of user terminal 102 of FIGURE 1, for example. The user terminal may include at least one antenna in communication with at least one transmitter and at least one receiver to enable communication with the download server. Similarly, the download server may include at least one antenna in communication with at least one transmitter and at least one receiver to enable communication with the user terminal. The download server may further include a processor configured to provide signals to and receive signals from the transmitter and receiver, respectively.

[0033] It is highly desirable to have partial RMs which result in high accuracy and availability of offline positioning and yet have as small a file size as posisble. In order to achieve this, a subset of identifiers of APs may be compressed. However, compressing AP identifiers may lead to more than one AP identifiers being transformed to a same compressed identifier. This leads to difficulties in determining a location of a user terminal, when a RM with compressed identifiers is used in the user terminal. In accordance with an embodiment of the invention, when an uncompressed identifier of AP represented in a RM with compressed identifier is determined, the uncompressed identifier is associated with the AP so that the knowledge of the uncompressed identifier can be utilized in future uses of the RM.

[0034] Global RM database 202, AP selector for partial RMs 203, Offline WLAN RM generator 201, Offline WLAN RM database 204 and RM offline download server 205 may be implemented as standalone nodes in a network, or alternatively at least two and optionally even all of them may be implemented as functions in a single physical server.

[0035] FIGURE 3 shows an apparatus embodying a process for associating information with APs with compressed identifiers according to an example embodiment of the invention. As an example, FIGURE 3 may be the positioning engine 1025 of FIGURE 1. Apparatus 300 comprises processors 301, 303, 304, 305, 306 and, linked to these processors, a memory 307. The processors 301, 303, 304, 305, 306 may, for example, be embodied as various means including circuitry, at least one processing core, one or more microprocessors with accompanying digital signal processor(s), one or more processor(s) without an accompanying digital signal processor, one or more coprocessors, one or more multi-core processors, one or more controllers, processing circuitry, one or more computers, various other processing elements including integrated circuits such as, for example, an application specific integrated circuit, ASIC, or field programmable gate array, FPGA, or some combination thereof. A processor comprising exactly one processing core may be referred to as a single-core processor, while a processor comprising more than one processing core may be referred to as a multi-core processor. Accordingly, although illustrated in FIGURE 3 as single processors, in some embodiments the processors 303, 304, 305, 306 may comprise a plurality of processors or processing cores. Similarly, processors 303, 304, 305, 306 may be embodied within one processor 301. In some embodiments, at least one of processors 303, 304, 305 and 306 are implemented at least in part in software, which software may be run on processor 301. Memory 307 stores computer program code for supporting associating information with AP with compressed identifiers in a partial RM. Processors 301, 303, 304, 305, 306 are configured to execute computer program code stored in memory 307 in order to cause the apparatus to perform desired actions. Apparatus 300 further comprises memory 302. Memory 302 may be used, at least in part, to store input data needed for operations of the apparatus 300 or output data resulting from operation of the apparatus 300. Apparatus 300 could be comprised in a user terminal or any other suitable device. Apparatus 300 could equally be a module, like a chip, circuitry on a chip or a plug-in board, for use in a user terminal or for any other device. Optionally, apparatus 300 could comprise various other components, such as for example at least one of a user interface, a further memory and a further processor. Memory 302 and memory 307 may be distinct memories, or alternatively memory 307 may be comprised in memory 302, or memory 302 may be comprised in memory 307. [0036] Interface 309, which may be a data interface, may receive an

uncompressed AP identifier. An uncompressed AP identifier may comprise a service set identification, SSID, and/or a basic service set identifier, BSSID such as a MAC address. In some embodiments, the uncompressed AP identifier comprises identities of base stations, such as for example cellular base stations. The interface 309 may receive the uncompressed AP identifier from a radio receiver, such as a WLAN receiver, for example. The uncompressed AP identifier may be received by the WLAN receiver during a scanning of WLANs by a user terminal. In some other embodiments of the invention, the interface 309 may receive the uncompressed AP identifier from a processor or a memory comprised in an apparatus such as user terminal 102 of FIGURE 1, for example. Once received by the apparatus 300, the uncompressed AP identifier may be stored in memory 302 or in memory 307, for example.

[0037] The compression unit 303 may receive the uncompressed AP identifier from the interface 309 or it may retrieve it from a memory such as memory 302 and/or memory 307. The compression unit may utilize a digital compression algorithm, such as for example, the CRC-16 ITU-T algorithm, to compress the uncompressed AP identifier. The compression unit may utilize the same compression algorithm that was used by a RM server, such as OW-RMG 201 of FIGURE 2, to generate compressed AP identifiers comprised in a RM which was downloaded by a user terminal comprising the apparatus 300, from a download server, such as RM offline download server 205 of FIGURE 2. A result of compression of an AP identifier is that the compressed AP identifier occupies less number of bits when compared to the uncompressed identifier. The compressed AP identifier may be stored in a memory location which may be comprised in memory 302 or memory 307, for example.

[0038] The association unit 304 may receive the compressed AP identifier from the compression unit 303. In another embodiment, the association unit 304 may obtain the compressed identifier from a memory such as memory 302 and/or memory 307. The association unit 304 identifies one or more access points comprised in a RM and represented with the same compressed identifier as the one generated by the compression unit 303. The compression unit 303 preferably uses the same compression algorithm that was used to compress identifiers included in the RM. Based upon information about a location of the user terminal, the association unit may associate the uncompressed identifier with one of the APs represented in the RM with the compressed identifier generated by compression unit 303. Based upon the association formed by the association unit 304, the RM updater 305 may update the RM. In an example embodiment of the invention, the RM updater may update the RM such that the associated AP is represented in the RM with the uncompressed identifier. In another example embodiment of the invention, the RM updater 305 may set a memory flag to indicate that the uncompressed identifier was associated with the associated AP by an association unit and not by a RM server such as OW-RMG 201 of FIGURE 2. The RM updater 305 may also set a memory flag to indicate that the uncompressed identifier was associated with the associated AP based upon a location of the user terminal. The RM updater 305 may also set a memory flag to indicate that the associated AP has a compressed identifier and an uncompressed identifier associated with it. One or more of these memory flags may be comprised in a memory such as memory 302 or 307 of FIGURE 3 or memory 1024 of FIGURE 1, for example.

[0039] In an example embodiment of the invention, a user terminal scans for WLAN APs and observes an AP with BSSID equal tol59277197314. The compression unit receives this BSSID from the interface 309. Alternatively, the compression unit may obtain the BSSID from a processor or a memory location comprised in the user terminal. The compression unit 303 compresses the BSSID using the CRC-16 ITU-T algorithm, which is the same compression algorithm that was used by a RM generator, such as the OW-RMG 201 of FIGURE 2, to compress AP identifiers comprised in RMs stored in the user terminal. After compression, the BSSID equal to 159277197314 results in a compressed AP identifier equal to 1. The association unit searches a RM corresponding to an area where the BSSID was observed, for a compressed identifier equal to 1. The association unit may have information about a location of the user terminal at the time of observing the BSSID, based upon a prior positioning request, for example. The association unit finds 6 APs, AP1-AP6, each represented in the RM with identifier equal to 1. Based upon the information about a location of the user terminal, the association unit may determine that the user terminal was located in a coverage area of API at the time of observing the BSSID. Based upon this information the association unit may associate BSSID equal to 159277197314 with API .

[0040] The RM updater may further update the RM such that API is represented with identifier equal to 159277197314 instead of identifier equal to 1. The RM updater may also set a memory flag to indicate that the BSSID was associated with API by an association unit and not by a RM server such as OW-RMG 201 of FIGURE 2. The RM updater may also set another memory flag to indicate that the BSID associated with API is based upon a location of the user terminal. The RM updater may also set another memory flag to indicate that API has a compressed identifier and an uncompressed identifier associated with it. One or more memory flags may be comprised within a RM file. One or more memory flags may be comprised in memory 302, 307 or memory 1024 of FIGURE 1, for example.

[0041] In another embodiment of the invention, the association unit 304 may determine that a location of the user terminal falls within coverage areas of more than one AP, say API and AP2. In this case, if BSSID equal to 159277197314 was observed, then the RM updater may associate both API and AP2 with BSSID equal to 159277197314. The RM updater may also set a memory flag to indicate that the BSSID was associated with API and AP2 by an association unit and not by a RM server such as the OW-RMG 201 of FIGURE 2. The RM updater may also set a memory flag to indicate that an uncompressed identifier was associated with API and AP2 based upon a location of the user terminal. The RM updater may also set at least one memory flag to indicate that API and AP2 have a compressed and an uncompressed identifier associated with them.

[0042] In an embodiment of the invention, while determining a location with an updated RM, APs whose uncompressed identifier was updated by a positioning engine, such as apparatus 300 of FIGURE 3, may be given lower priority compared to APs whose uncompressed identifiers were assigned by a RM server. Say, a user terminal observes a list of AP identifiers at a location and in order to determine its location utilizing offline positioning, transmits the list to a positioning engine comprised in the user terminal. From this list, the positioning engine may first determine a subset of APs which are represented in a RM with their uncompressed identifiers by a RM server. The positioning engine may then ignore outlier APs from this subset to determine a subset of outlier APs. An AP is an outlier if, for example, it is located so far away from other APs in the subset that its inclusion in position determination will be meaningless. For example, if there are five APs in the subset and one of them is location 1000 km away from the others, it may be classified as an outlier. Thereafter, an AP comprised in the list and represented in the RM with an uncompressed identifier associated by a positioning engine may only be utilized in resolving the positioning request if such an AP is located in a vicinity of the subset of non- outlier APs.

[0043] In yet another embodiment of the invention, the apparatus 300 may determine whether the uncompressed AP identifier is comprised in a RM or not. If the uncompressed identifier is comprised in the RM, there may be no need to compress the uncompressed identifier, associate the uncompressed identifier with an AP represented in a PvM with a compressed identifier or to update the RM.

[0044] Note that other selection methods can also be utilized and the invention is not restricted to selection methods described herein.

[0045] FIGURE 4 is a flow diagram showing operations for associating information with APs with compressed identifiers in accordance with at least one embodiment of the invention. The method may be executed by a positioning engine, such as for example, the positioning engine 1025 comprised in the user terminal 102 of

FIGURE 1. In step 401, a positioning engine receives an uncompressed AP identifier. The uncompressed AP identifier may be received from a processor comprised within a user terminal, which user terminal also comprises the positioning engine, for example. In another embodiment of the invention, the uncompressed AP identifier may be received from a WLAN receiver comprised in a user terminal comprising the positioning engine, for example. The WLAN receiver may receive the uncompressed AP identifier as a result of scanning for WLANs at a location of a user terminal. In step 402, the positioning engine compresses the received uncompressed identifier utilizing the same compression algorithm that was used by a RM server, such as OW-RMG 201 of FIGURE 2, to generate RMs utilized by the user terminal for offline positioning. After compression, an identifier may comprise less number of bits.

[0046] In step 403, the positioning engine identifies one or more access points, which are represented in a RM with the compressed identifier generated in step 402. The RM may be stored in a memory comprised in the user terminal, such as memory 302 or 307 of FIGURE 3 or memory 1024 of FIGURE 1.

[0047] In step 404, the positioning engine associates the uncompressed identifier with an AP from among the APs identified in step 403. This association may be based on a known location of the user terminal, for example. The location of the user terminal may be known from a response to a previous positioning request by utilizing an online positioning system or a GNSS, for example. Based upon a location of the user terminal, the positioning server may determine an AP among the APs identified in step 403, such that the location of the user terminal falls within a coverage area of the AP. The positioning server may associate the uncompressed AP identifier received in step 401 with this AP.

[0048] Finally in step 405, the positioning engine may update the RM to reflect the association made in step 404. The positioning engine may update the RM such that the

AP associated in step 404 may be represented in the RM with the uncompressed identifier. The positioning engine may further set a memory flag to indicate that the uncompressed identifier was associated with the AP by a positioning engine and not by a RM server such as OW-RMG 201 of FIGURE 2. The positioning engine may also set a memory flag to indicate that the uncompressed identifier was associated with the AP based upon a location of the user terminal. The positioning engine may also set a memory flag to indicate that the AP has a compressed identifier and an uncompressed identifier associated with it. One or more of these memory flags may be comprised in a memory such as memory 302 or 307 of FIGURE 3 or memory 1024 of FIGURE 1, for example.

[0049] In another embodiment of the invention, the positioning engine may determine that a location of the user terminal falls within coverage areas of more than one AP. In this case, the positioning engine may associate each such AP with the

uncompressed identifier. The positioning engine may also set a memory flag to indicate that the uncompressed identifier was associated with the APs by the positioning engine and not by a RM server such as the OW-RMG 201 of FIGURE 2. The positioning engine may also set a memory flag to indicate that the uncompressed identifier was associated with the APs based upon a location of the user terminal. The positioning engine may also set a memory flag to indicate that the APs have a compressed and an uncompressed identifier associated with them. One or more of these memory flags may be comprised in a memory such as memory 302 or 307 of FIGURE 3 or memory 1024 of FIGURE 1, for example.

[0050] In an embodiment of the invention, while determining a location with an updated RM, APs whose uncompressed identifier was updated by a positioning engine may be given lower priority compared to APs whose uncompressed identifiers were assigned by a RM server. Say, a user terminal observes a list of AP identifiers at a location and in order to determine its location utilizing offline positioning, transmits the list to a positioning engine comprised in the user terminal. From this list, the positioning engine may first determine a subset of APs which are represented in a RM with their

uncompressed identifiers by a RM server. The positioning engine may then ignore outlier APs from this subset to determine a subset of outlier APs. An AP is an outlier if, for example, it is located so far away from other APs in the subset that its inclusion in position determination will be meaningless. For example, if there are five APs in the subset and one of them is location 1000 km away from the others, it may be classified as an outlier.

Thereafter, an AP comprised in the list and represented in the RM with a compressed identifier by a RM server and whose uncompressed identifier was associated by a positioning engine may only be utilized in resolving the positioning request if such an AP is located within a vicinity of the subset of non-outlier APs.

[0051] In another embodiment of the invention, the positioning engine may determine whether the uncompressed AP identifier is comprised in a RM or not. If the uncompressed identifier is comprised in the RM, there may be no need to compress the uncompressed identifier, associate the compressed version of the uncompressed identifier with an AP or a coverage area or to update the RM.

[0052] FIGURE 5 demonstrates how a radio map comprising compressed AP identifiers may be updated, according to an embodiment of the invention. Say, the CRC-16 ITU-T algorithm is used by a RM server, such as OW-RMG 201 of FIGURE 2, to generate compressed AP identifiers to be used in a RM. Say, identifiers of following six APs were compressed by the RM server before inclusion in a RM. As shown in Table 1, all six distinct AP identifiers result in the same compressed identifier equal to 1.

Table 1 : AP identifier compression utilizing the CRC-16 ITU-T algorithm

An RM comprising these six APs represented with their compressed identifier would associate 6 coverage areas, corresponding to AP1-AP6, to one compressed identifier, equal to 1. Say, this RM is downloaded by a user terminal, from a download server such as RM offline download server 205 of FIGURE 2. At the user terminal, there is no knowledge of the uncompressed identifiers, such as BSSIDS of AP1-AP6 and as shown in FIGURE 5(a), a compressed identifier equal to 1 is associated with 6 coverage areas corresponding to the six APs, AP1-AP6.

[0053] Say, a positioning engine comprised in the user terminal receives the uncompressed identifier of API equal tol59277197314. This uncompressed AP identifier may be received from a processor comprised within the user terminal or it may be received from a WLAN receiver comprised within the user terminal, for example. The WLAN receiver may receive the BSSID of API as a result of scanning for WLANs at a location of the user terminal. The positioning engine compresses the BSSID 159277197314 using the CRC-16 ITU-T algorithm and determines that the compressed identifier is equal to 1. The positioning engine then determines that there are 6 coverage areas in the RM associated with the compressed identifier equal to 1. A location of the user terminal may be known to the positioning engine from a response to a previous positioning request served by an online positioning system or a GNSS, for example. Based upon information about a location of the user terminal, the positioning engine may determine that the BSSID was observed in coverage area 1, corresponding to API, and may associate the observed BSSID equal to 159277197314 with coverage area 1. As shown in Figure 5(b), the positioning engine may update the RM such that BSSID equal to 159277197314 is associated with coverage area 1 and the five remaining coverage areas remain associated with the compressed ID equal to 1. Next time the BSSID equal to 159277197314 is observed at the user terminal, the user terminal may resolve the positioning request utilizing the uncompressed identifier. The positioning engine may further set a memory flag to indicate that the BSSID equal to 159277197314 was associated with coverage area 1 by a positioning engine and not by a RM server. The positioning engine may also set a memory flag to indicate that the BSSID was associated with the coverage area based upon a location of the user terminal. The positioning engine may also set a memory flag to indicate that an AP has a compressed identifier equal to 1 and a BSSID equal to

159277197314 associated with it.

[0054] In another embodiment of the invention shown in FIGURE 5 (c), the positioning engine determines that a location of the user terminal falls within two coverage areas, coverage area 1 and coverage area 2. Based upon this information, the positioning engine updates the RM to reflect that BSSID equal to 159277197314 is associated with coverage area 1 and 2 and coverage areas 3 - 6 remain associated with compressed identifier 1. The positioning engine may set a flag in a memory to indicate that the BSSID was associated with the coverage areas based upon a location of the user terminal. The positioning engine may also set a memory flag to indicate that the BSSID was associated with the coverage areas by a positioning engine and not by a RM server. The positioning engine may also set a memory flag to indicate that the coverage areas 1 and 2 have a compressed and an uncompressed identifier associated with them. [0055] If desired, the different functions discussed herein may be performed in a different order and/or concurrently with each other. Furthermore, if desired, one or more of the above-described functions may be optional or may be combined.

[0056] Without in any way limiting the scope, interpretation, or application of the claims appearing below, a technical effect of one or more of the example embodiments disclosed herein is reducing a file size of a RM with minimal loss in positioning accuracy and availability. Another technical effect of one or more of the example embodiments disclosed herein is to resolve ambiguity in a location of a compressed AP by utilizing a location of an uncompressed AP.

[0057] Embodiments of the present invention may be implemented in software, hardware, application logic or a combination of software, hardware and application logic. The software, application logic and/or hardware may reside on memory 307, the processor 301 or electronic components, for example. In an example embodiment, the application logic, software or an instruction set is maintained on any one of various conventional computer-readable media. In the context of this document, a "computer-readable medium" may be any media or means that can contain, store, communicate, propagate or transport the instructions for use by or in connection with an instruction execution system, apparatus, or device, such as a computer, with one example of a computer described and depicted in FIGURE 3. A computer-readable medium may comprise a computer-readable non-transitory storage medium that may be any media or means that can contain or store the instructions for use by or in connection with an instruction execution system, apparatus, or device, such as a computer. The scope of the invention comprises computer programs configured to cause methods according to embodiments of the invention to be performed.

[0058] Although various aspects of the invention are set out in the independent claims, other aspects of the invention comprise other combinations of features from the described embodiments and/or the dependent claims with the features of the independent claims, and not solely the combinations explicitly set out in the claims.

[0059] It is also noted herein that while the above describes example

embodiments of the invention, these descriptions should not be viewed in a limiting sense. Rather, there are several variations and modifications which may be made without departing from the scope of the present invention as defined in the appended claims.

Claims

WHAT IS CLAIMED IS

1. An apparatus, comprising:

a receiver configured to receive a first uncompressed access point identifier;

a processor configured to determine a compressed access point identifier corresponding to the first uncompressed access point identifier wherein the compressed access point identifier corresponds to a plurality of access points comprised in a radio map; and

the processor further configured to associate at least one access point from the plurality of access points with the first uncompressed access point identifier based at least in part on a location.

2. The apparatus of claim 1, further comprising

the processor configured to determine a second location, wherein the at least one access point is given a lower priority in determining the second location compared to a second access point when a second uncompressed access point identifier was assigned to the second access point by a radio map server.

3. The apparatus of any of claims 1-2, wherein the first uncompressed

access point identifier is comprised in a radio signal observed at the location.

4. The apparatus of any of claims 1-3, wherein the compressed access point identifier comprises less number of bits compared to the first

uncompressed access point identifier.

5. The apparatus of any of claims 1-4, wherein the plurality of access points are represented in the radio map with the compressed access point identifier.

6. The apparatus of any of claims 1-5, wherein the processor is further configured to represent the at least one access point in the radio map with the first uncompressed access point identifier. The apparatus of any of claims 1-6, further comprising a first memory configured to store a first value indicating that the first uncompressed access point identifier was associated with the at least one access point based at least in part on the location.

The apparatus of any of claims 1-7, further comprising a second memory configured to store a second value indicating that the at least one access point is associated with a compressed identifier and an uncompressed identifier.

A method, comprising;

receiving a first uncompressed access point identifier;

determining a compressed access point identifier corresponding to the first uncompressed access point identifier wherein the compressed access point identifier corresponds to a plurality of access points comprised in a radio map; and

associating at least one access point from the plurality of access points with the first uncompressed access point identifier based at least in part on a location.

The method of claim 9, further comprising

determining a second location,

wherein the at least one access point is given a lower priority in determining the second location compared to a second access point when a second uncompressed access point identifier was assigned to the second access point by a radio map server.

The method of any of claims 9-10, wherein the first uncompressed access point identifier is comprised in a radio signal observed at the location.

The method of any of claims 9-11, wherein the first compressed access point identifier comprises less number of bits compared to the uncompressed access point identifier.

13. The method of any of claims 9-12, wherein the plurality of access points are represented in the radio map with the compressed access point identifier.

14. The method of any of claims 9-13, further comprising representing the at least one access point in the radio map with the first uncompressed access point identifier.

The method of any of claims 9-14, further comprising storing a first value indicating that the first uncompressed access point identifier was associated with the at least one access point based at least in part on the location.

The method of any of claims 9-15, further comprising storing a second value indicating that the at least one access point is associated with a compressed identifier and an uncompressed identifier.

An apparatus, comprising:

at least one processor; and

at least one memory including computer program code the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following:

receiving a first uncompressed access point identifier;

18. An apparatus, comprising: means for receiving a first uncompressed access point identifier; means for determining a compressed access point identifier corresponding to the first uncompressed access point identifier wherein the compressed access point identifier corresponds to a plurality of access points comprised in a radio map; and

means for associating at least one access point from the plurality of access points with the first uncompressed access point identifier based at least in part on a location. 19. A computer program, comprising:

code for receiving a first uncompressed access point identifier; code for determining a compressed access point identifier corresponding to the first uncompressed access point identifier wherein the compressed access point identifier corresponds to a plurality of access points comprised in a radio map; and

code for associating at least one access point from the plurality of access points with the first uncompressed access point identifier based at least in part on a location.

The computer program according to claim 19, wherein the computer program is a computer program product comprising a computer-readable medium bearing computer program code embodied therein for use with a computer. 21. A computer-readable medium encoded with instructions that, when

executed by a computer, perform:

receiving a first uncompressed access point identifier;

22. A computer program configured to cause a method according to at least one of claims 9-16 to be performed.