Methods and apparatuses for providing expected signal data to a mobile station

Techniques are provided which may be implemented using various methods and/or apparatuses to allow for expected signal data for a region of space within a structure to be encoded and transmitted to a mobile station. The mobile station may decode the encoded version and use the resulting decoded version to support signal-based position estimation.

BACKGROUND

The subject matter disclosed herein relates to electronic devices, and more particularly to methods and apparatuses for use in providing expected signal data to a mobile station.

2. Information

The Global Positioning System (GPS) and other like satellite positioning systems have enabled navigation services for mobile handsets in outdoor environments. Since satellite signals may not be always be reliably received and/or acquired in an indoor environment, different techniques may be employed to enable position estimation and related navigation services. For example, mobile stations can typically obtain a position fix by measuring ranges to three or more terrestrial radio transmitters which are positioned at known locations. Such ranges may be measured, for example, by obtaining a MAC ID address from signals received from such access points and measuring one or more characteristics of signals received from such access points such as, for example, signal strength, round trip delay, just to name a few examples.

By way of additional example, a mobile station, such as, a mobile phone, smart phone, etc., may perform signal-based position estimation to identify its location within a structure by taking measurements, for example of a signal strength (e.g., an RSSI) and/or propagation time (e.g., a round-trip time (RTT)) for signals exchanged with various radio transmitters (e.g., access points, beacons, etc.). A mobile station may use these or other like measurements to obtain a probability distribution over a region of space (e.g., defined using two or coordinates (x, y), etc.). Such a probability distribution or other like information may, for example, be used in a particle filter, Kalman filter, and/or other positioning mechanism using known techniques.

To support such a process, expected signal data, such as, may be related to a “heat map”, “radio map”, and/or other like form of information, may be used for probability lookup. In an example, expected signal data may take the form of a table listing an expected mean and standard deviation of a signal measurement quantity for each identifiable position point (e.g., (x,y) positions, etc.). With such information, a mobile station may convert signal measurements to a probability value for selected candidate position points.

Expected signal data may be provided to a mobile station by one or more remote devices. In certain instances, such as, for a large building or other complex structure, there may be a significant amount of expected signal data to transfer to a mobile station. Consider, for example, a uniformly distributed grid of position points set one meter apart, covering a one hundred meter by one hundred meter floor of a shopping mall. Here, there would be ten thousand position points, for which expected signal data would be provided for each radio transmitter that may support the position estimation capability of the mobile station. Further still, for example, for each position point a mean value and a variation value (e.g., a standard deviation) may be provided. Thus, assuming that such values are represented by one byte of data, in this example the expected signal data for sixteen radio transmitters would take about 320 kB. Moreover, such example shopping mall may have additional floors. Transmitting such a large amount of data from a network to a mobile station may prove costly in terms of power, bandwidth, and latency. Additionally, such expected signal data would also consume a significant amount of memory on the mobile station.

SUMMARY

Techniques are provided which may be implemented using various methods and/or apparatuses to allow for expected signal data for a region of space within a structure to be encoded and transmitted to a mobile station. The mobile station may decode the encoded version and use the resulting decoded version to support signal-based position estimation, navigation, etc.

In accordance with an example implementation, a method may be provided for use with at least one computing device. The method may comprise: obtaining one or more signals representing expected signal data associated with one or more radio transmitters for a region of space within a structure, the expected signal data being associated with a plurality of identifiable position points within the region of space; identifying at least one subset of the plurality of identifiable position points, the at least one subset comprising an anchor point and one or more non-anchor points; determining at least one function relating the expected signal data associated with the anchor point to the expected signal data associated with the one or more non-anchor points; and generating one or more signals representing an encoded version of the expected signal data associated with the one or more radio transmitters for the region of space based, at least in part, on the at least one function.

In accordance with another example implementation, an apparatus may comprise: a network interface; and at least one processing unit to: obtain expected signal data associated with one or more radio transmitters for a region of space within a structure, the expected signal data being associated with a plurality of identifiable position points within the region of space; identify at least one subset of the plurality of identifiable position points, the at least one subset comprising an anchor point and one or more non-anchor points; determine at least one function relating the expected signal data associated with the anchor point to the expected signal data associated with the one or more non-anchor points; determine an encoded version of the expected signal data associated with the one or more radio transmitters for the region of space based, at least in part, on the at least one function; and initiate transmission of at least a portion of the encoded version of the expected signal data to a mobile station via the network interface.

In accordance with yet another example implementation, an apparatus may comprise: means for obtaining expected signal data associated with one or more radio transmitters for a region of space within a structure, the expected signal data being associated with a plurality of identifiable position points within the region of space, wherein at least a portion of the expected signal data is associated with at least one of a signal strength and/or a signal propagation time; means for identifying at least one subset of the plurality of identifiable position points, the at least one subset comprising an anchor point and one or more non-anchor points; means for determining at least one function relating the expected signal data associated with the anchor point to the expected signal data associated with the one or more non-anchor points; means for determining an encoded version of the expected signal data associated with the one or more radio transmitters for the region of space based, at least in part, on the at least one function; and means for transmitting at least a portion of the encoded version of the expected signal data to a mobile station.

In accordance with still another example implementation, an article of manufacture may comprise a computer readable medium having stored therein computer-implementable instructions executable by one or more processing units to: obtain expected signal data associated with one or more radio transmitters for a region of space within a structure, the expected signal data being associated with a plurality of identifiable position points within the region of space, wherein at least a portion of the expected signal data is associated with at least one of a signal strength and/or a signal propagation time; identify at least one subset of the plurality of identifiable position points, the at least one subset comprising an anchor point and one or more non-anchor points; determine at least one function relating the expected signal data associated with the anchor point to the expected signal data associated with the one or more non-anchor points; generate an encoded version of the expected signal data associated with the one or more radio transmitters for the region of space based, at least in part, on the at least one function; and initiate transmission of at least a portion of the encoded version of the expected signal data to a mobile station.

In accordance with a further example implementation, a method may be provided for use with a mobile station. The method may comprise: obtaining one or more signals representing an encoded version of expected signal data associated with one or more radio transmitters for a region of space within a structure, the encoded version of the expected signal data being encoded based, at least in part, on at least one function associated with at least one subset of a plurality of identifiable position points within the region of space, the subset comprising an anchor point and one or more non-anchor points; generating one or more signals representing a decoded version of the expected signal data based, at least in part, on the encoded version of the expected signal data and the at least one function; receiving one or more transmitted signals from at least one of the one or more radio transmitters; and estimating a current position of the mobile station based, at least in part, on the decoded version of the expected signal data and the one or more transmitted signals.

In accordance with certain example implementations, a mobile station may comprise: a network interface; and at least one processing unit to: initiate transmission of a request for at least a portion of an encoded version of an expected signal data associated with one or more radio transmitters for a region of space within a structure, the encoded version of being encoded based, at least in part, on at least one function associated with at least one subset of a plurality of identifiable position points within the region of space, the subset comprising an anchor point and one or more non-anchor points; obtain at least the portion of the encoded version of expected signal data; establish a decoded version of the expected signal data based, at least in part, on the encoded version of the expected signal data and the at least one function; obtain information associated with one or more transmitted signals received via the network interface from at least one of the one or more radio transmitters; and estimate a current position of the mobile station based, at least in part, on the decoded version of the expected signal data and the information associated with the one or more transmitted signals.

In accordance with certain further example implementations, an apparatus for use in a mobile station may comprise: means for initiating transmission of a request for at least a portion of an encoded version of an expected signal data associated with one or more radio transmitters for a region of space within a structure, the encoded version of being encoded based, at least in part, on at least one function associated with at least one subset of a plurality of identifiable position points within the region of space, the subset comprising an anchor point and one or more non-anchor points; means for obtaining at least the portion of the encoded version of expected signal data; means for establishing a decoded version of the expected signal data based, at least in part, on the encoded version of the expected signal data and the at least one function; means for receiving one or more transmitted signals from at least one of the one or more radio transmitters; and means for estimating a current position of the mobile station based, at least in part, on the decoded version of the expected signal data and the one or more transmitted signals.

In accordance with still other certain example implementations, an article of manufacture may comprise a computer readable medium having stored therein computer-implementable instructions executable by one or more processing units of a mobile station to: initiate transmission of a request for at least a portion of an encoded version of an expected signal data associated with one or more radio transmitters for a region of space within a structure, the encoded version of being encoded based, at least in part, on at least one function associated with at least one subset of a plurality of identifiable position points within the region of space, the subset comprising an anchor point and one or more non-anchor points; obtain at least the portion of the encoded version of expected signal data; establish a decoded version of the expected signal data based, at least in part, on the encoded version of the expected signal data and the at least one function; obtain information associated with one or more transmitted signals received from at least one of the one or more radio transmitters; and estimate a current position of the mobile station based, at least in part, on the decoded version of the expected signal data and the information associated with the one or more transmitted signals.

DETAILED DESCRIPTION

In accordance with certain aspects, example techniques are provided which may be implemented using various methods and/or apparatuses to provide expected signal data to mobile stations. Here, for example, all or part of the expected signal data may be encoded to reduce the amount of data to be provided to and/or stored/processed by a mobile station. A mobile station may subsequently decode all or part of the encoded version of expected signal data to establish a decoded version of expected signal data. Thus, in one respect, an example implementation of the techniques provided herein may serve to significantly compress expected signal data.

By way of example, consider again a structure defining a region having ten thousand position points and sixteen radio transmitters, wherein mean and standard deviation values for each radio transmitter at each position point are each represented by one byte of data. The original expected signal data (for all radio transmitters) would amount to about 320 kB. In an example implementation of the encoding techniques provided herein, an encoded version of expected signal data may be reduced in size significantly. For example, as described in greater detail herein, in certain instances such an encoded version of expected signal data may be reduced in size to about 32 kB or less.

To provide such data reduction, in accordance with an example implementation, one or more computing devices may obtain expected signal data associated with one or more radio transmitters for a region of space within a structure. Here, for example, the expected signal data being associated with a plurality of identifiable position points within the region of space. The computing device(s) may apply various techniques to identify at least one subset of the identifiable position points for which an anchor point may selected along with one or more relatable non-anchor points. As such, the computing device(s) may determine at least one function relating the expected signal data associated with the anchor point to the expected signal data associated with the non-anchor point(s). The computing device(s) may then establish an encoded version of expected signal data associated with the radio transmitters) for the region of space based, at least in part, on the function(s).

Thus, for example, as described in greater detail herein, rather than list expected signal data for every positioning point and for every radio transmitter, an encoded version of expected signal data may comprise certain expected signal data for anchor points along with functional parameters which may be employed to determine a decoded version of expected signal data for non-anchor points. An encoded version of expected signal data may indicate in various manners that there is a relationship between an anchor point and one or more non-anchor points.

In certain further example implementations, additional efficiency may be introduced by selecting subsets of anchor and non-anchor points based on additional information. For example, such additional information may relate to an expected navigation route, a characteristic of a given structure, a particular period of time, a particular type of radio receiver, a particular type of transmitted signal, etc. Furthermore, for example, efficiency may be improved by selectively transmitting encoded versions of expected signal data for certain subsets, e.g., at specific instances. As described in greater detail herein, such capability may allow of a “tiling” effect for potentially large map/graphs.

Again, by way of example, consider the situation with ten thousand position points and sixteen radio transmitters, where mean and standard deviation are each represented by one byte. Let us assume that five hundred and twelve anchor points have been selected and that each anchor point will only selectively be related to its eight (e.g., most applicable) radio transmitters identified via a sixteen-bit bitmap. Here, assume further that, for a selected function, one byte is used for each of the model parameter values (e.g., coefficients c1, c2, c3, and c4). Also, suppose each non-anchor point may have its relationship to an anchor point identified using the anchor point's sixteen-bit identifier. As such, in this example, an encoded version of expected signal data may amount to a size of about 35 kB. In a further non-limiting example, if the non-anchor points are listed along with the anchor point's data (e.g., immediately after the corresponding anchors) rather than using explicit references, a tiled effect may be introduced such that the resulting encoded version of expected signal data may amount to a size of about 16 kB.

Attention is drawn now toFIG. 1which is a schematic block diagram illustrating an example environment100that includes one or more computing devices106capable of providing one or more encoded versions of expected signal data to a mobile station102, in accordance with an implementation.

Mobile station102is representative of any electronic device that may be reasonably moved about by a user. By way of example but not limitation, mobile station102may comprise a computing and/or communication device such as a mobile telephone, a smartphone, a lap top computer, a tablet computer, a wearable computer, a personal digital assistant, a navigation device, etc.

Mobile station102and computing devices106may, for example, be enabled (e.g., via one or more network interfaces) for use with various wireless communication networks such as a wireless wide area network (WWAN), a wireless local area network (WLAN), a wireless personal area network (WPAN), and so on. The term “network” and “system” may be used interchangeably herein. A WWAN may be a Code Division Multiple Access (CDMA) network, a Time Division Multiple Access (TDMA) network, a Frequency Division Multiple Access (FDMA) network, an Orthogonal Frequency Division Multiple Access (OFDMA) network, a Single-Carrier Frequency Division Multiple Access (SC-FDMA) network, and so on. A CDMA network may implement one or more radio access technologies (RATs) such as cdma2000, Wideband-CDMA (W-CDMA), Time Division Synchronous Code Division Multiple Access (TD-SCDMA), to name just a few radio technologies. Here, cdma2000 may include technologies implemented according to IS-95, IS-2000, and IS-856 standards. A TDMA network may implement Global System for Mobile Communications (GSM), Digital Advanced Mobile Phone System (D-AMPS), or some other RAT. GSM and W-CDMA are described in documents from a consortium named “3rd Generation Partnership Project” (3GPP). Cdma2000 is described in documents from a consortium named “3rd Generation Partnership Project 2” (3GPP2). 3GPP and 3GPP2 documents are publicly available. A WLAN may include an IEEE 802.11x network, and a WPAN may include a Bluetooth network, an IEEE 802.15x, for example. Wireless communication networks may include so-called next generation technologies (e.g., “4G”), such as, for example, Long Term Evolution (LTE), Advanced LTE, WiMax, Ultra Mobile Broadband (UMB), and/or the like.

FIG. 1also illustrates a plurality of radio transmitters104, various communication links108, one or more networks110, an encoder112(e.g., for establishing an encoded version of expected signal data), a decoder114(e.g., for establishing a decoded version of expected signal data), a request116(e.g., for encoded version of expected signal data), a response118(e.g., providing encoded version of expected signal data), a structure120, and one or more other resources122.

As illustrated, mobile station102may transmit a request116for one or more encoded versions of expected signal data via at least one communication link108to at least one computing device106. Mobile station102may receive a response118comprising one or more encoded versions of expected signal data via at least one communication link108from at least one computing device106. Here, for example, request116and/or response118may take the form of one or more messages transmitted via wireless communication link108-1, network(s)110, and non-wireless communication link108-2, and/or directly via wireless communication link108-3.

In certain example implementations, mobile station102may receive a response118and/or other like transmission comprising one or more encoded versions of expected signal data without necessarily having requested such. For example, computing device(s)106may be enabled to determine that mobile station102has entered into or is expected to soon enter into a structure120and/or specific region therein, and as such may independently initiate transmission of one or more encoded versions of expected signal data.

It should be recognized that one or more communication links108shown inFIG. 1, may comprise one or more wireless communication links and/or one or more non-wireless communication links (e.g., with signals transmitted using one or more wires, fibers, etc.), and that such communication links108and/or network(s)110may also represent various supporting devices and/or technologies associated therewith.

In this example, structure120is representative of any man-made and/or naturally occurring set of physical features for which expected signal data may be provided to support signal-based position estimation capabilities of mobile station102. Thus, for example, structure120may represent a building or set of buildings, an airport, an arena, a warehouse, a campus, a zoo, etc. In such instances, various location based services may be provided to further enhance a user's experience in navigating about structure120using mobile station102. For example, context information and/or other useful information may be provided to a mobile station102as part of a location based service for a given structure. By way of example, a wireless access point located at or near structure120(or elsewhere) may transmit information relating to location based services to mobile station102. In certain example implementations, such information may comprise encoded version(s) of expected signal data.

Radio transmitter(s)104, in this example, are representative of any device that may transmit one or more wireless signals which may be used by mobile station102for estimating its position. For example, a radio transmitter104may comprise a special purpose location beacon device, a network access point device, a base station, a femtocell or picocell device, and/or the like. A location of radio transmitter104may be provided to mobile station in advance and/or via one or more transmitted signals.

In a non-limiting example, the expected signal data may be associated with expected signal strengths and/or signal propagation times which may be considered in estimating a distance from mobile station to a radio transmitter. Here, for example, such expected signal data may be based, at least in part, on previously measured signal data and/or estimated signal data (e.g., modeled signal data).

As described in greater detail herein, in certain example implementations, all or part the encoded version of expected signal data may be associated with a particular period of time, a particular type of radio receiver, a particular type of transmitted signal, etc.

Reference is made next toFIG. 2, which is a schematic block diagram illustrating certain features of computing device106capable of providing an encoded version of expected signal data to a mobile station.

FIG. 2shows a specific apparatus200in the form of a computing device106, one or more of which may act, at least in part, as an encoder112to establish one or more encoded versions214of the expected signal data for use by one or more mobile stations102. In certain example implementations, apparatus200may act as an individual server, part of a server farm, part of a cloud computing arrangement, etc. In certain example implementations, apparatus200may act as part of a network110, e.g., at a base station, an access point, etc. In certain example implementations, apparatus200may comprise and/or be coupled to one or more other resources (devices)122that may be arranged to provide information such as expected signal data210.

With this mind, as illustrated inFIG. 2, example computing device106may comprise one or more processing units202, memory204, connections206, and a network interface208. As shown, memory204may comprise a primary memory204-1, and/or a secondary memory204-2. Here, for example, primary memory204-1may store computer-implementable instructions and/or data relating to encoder112, which may be executed or used by processing unit(s)202.

As illustrated, at certain times primary memory204-1may, for example, store information relating to one or more requests116for encoded versions214of expected signal data and/or one or more responses118. For example, a request116for an encoded version214may be received from mobile station102via network interface208. For example, a response118may be generated by processing unit(s)202and transmitted to mobile station102via network interface208. Network interface208may, for example, comprise one or more wireless transmitters/receivers and/or one or more non-wireless interfaces (e.g., Ethernet, etc.).

In certain example implementations, computing device106may be arranged to establish an encoded version214of expected signal data by identifying at least one subset of position points comprising an anchor point and one or more non-anchor points. Thus, by way of example, a subset may be identified based, at least in part, on one or more signal data thresholds216and expected signal data210. Here, for example, position points may be identified as candidates for a subset based on whether certain expected signal data for particular radio transmitter falls within a threshold range. For example, it may be that given a characteristic of a region of space within a structure and/or a type of radio transmitter/signal that expected signal data for position points within the region of space (e.g., a room, hallway, etc.) fall within a particular range of values (e.g., as might relate to some mathematical and/or probabilistic function).

Other information may also and/or alternatively be considered in identifying a subset of position points and/or selecting an anchor point. For example, an estimated initial position218of a mobile station may be considered. Here, for example, an estimated initial position218may be identified by a mobile station in a request116. For example, a mobile station may provide a GPS estimated position, etc. In certain example implementations, computing device106, network110and/or other resource122may provide an estimated initial position218.

In certain example implementations, to identify a subset of position points and/or select an anchor point, an expected navigation route may be considered. Thus, for example, a subset may relate to a contiguous region of space that a user may travel through, such as, for example, at least part of one or more corridors, etc. In certain examples, such routing information may be learned or otherwise identified over time by monitoring user traffic, etc.

In other example implementations, to identify a subset of position points and/or select an anchor point, one or more particular periods of time may be taken into consideration. For example, there may be periods of time wherein certain transmitters operate in different manners (e.g., ON or OFF, higher or lower transmit power, etc.). For example, there may be certain regions of space which may or may not be entered/exited or otherwise traversed.

In still other example implementations, to identify a subset of position points and/or select an anchor point, it may be beneficial to identify or otherwise consider which radio transmitters104may be more useful for use in signal-based position estimation performed by one or more mobile stations and/or a specific type of mobile station. For example, subsets may be identified in a manner that is likely to provide for reception of transmitted signals from at least a threshold number of radio transmitters at or near an anchor point and/or its one or more related non-anchor points.

In yet another example, to identify a subset of position points and/or select an anchor point, it may be beneficial to consider the number and/or pattern of candidate position points. For example, it may be useful to either limit the number of position points in a subset in some manner (e.g., in consideration of data size, processing overhead, type of function used to model expected signal data, type of mobile station, context relating to region of space/structure, etc.). In certain instances, it may further be useful to select a subset of position points based, at least in part, on whether the various position points are uniformly distributed and/or non-uniformly distributed.

With these non-limiting examples in mind, it should be recognized that the act of identifying a subset of position points and/or selecting an anchor point and its related non-anchor points may be performed in advance (e.g., via offline processing) and/or dynamically. Regardless as when such analysis may be performed, it should be clear that various information and/or heuristics may be evaluated by encoder112. In certain example implementations, encoder112may also receive and consider user inputs.

As illustrated, one or more functions212may be provided and/or otherwise employed by encoder112to relate an anchor point to one or more non-anchor points. Function(s)212, in this example, is representative of any mathematical and/or probabilistic function and/or functions that may be used to model expected signal data210for at least the selected position points within at least a portion of a region of space. Thus, for example, function(s)212may comprise one or more linear functions, non-linear functions, quadratic functions, logarithmic functions, etc., which may be used to estimate or otherwise model to some acceptable degree the expected signal data for one or more transmitted signals from one or more radio transmitters.

For example, for each and/or certain selected radio transmitters)104, at least one function212may be used to provide a local ranging model that mathematically and/or probabilistically relates to an expected signal data to at least a subset of position points. Function212may provide a local ranging model that represents such expected signal data as a function, e.g., a substantially smooth and/or contiguous function. Such a function may be associated with one or more parameter values that may be based, at least in part, on the expected signal data within region associated with the subset of position points. Such parameter values and/or other like information relating to the function and/or local ranging model may be provided as part of an encoded version214of expected signal data.

Consequently, a decoder114in a mobile station may establish a decoded version of expected signal data based, at least in part, on the encoded version214. Hence, for example, decoder114may employ a (decoding) function212′ that corresponds in some manner to the (encoding) function212. Thus, in certain instances, a (decoding) function212′ may be the same as or an inverse and/or other like applicable adaptation of the (encoding) function212.

As illustrated in greater detail in subsequent examples, in certain instances expected signal data210and/or one or more parameter values associated with function(s)212, and hence encoded and decoded versions, may comprise and/or otherwise relate to a mean value and a variance value for signal strength, signal propagation time, and/or other like signal characteristic.

Encoded version214may, for example, identify at least an anchor point and one or more parameter values. In certain example implementations, encoded version214may also identify or otherwise indicate in some manner that there is a relationship between an anchor point and one or more non-anchor points. For example, in certain instances, non-anchor points may be identified (e.g., using an identifier) along with an identifier of its respective anchor point. In other examples, it may be useful to identify an anchor point and then list therewith identifiers of its respective non-anchor points.

In certain example implementations, encoded version214may, as applicable, identify function(s)212. For example, in certain implementations, different functions may be used for different subsets of position points/anchor points, different radio transmitters, different mobile stations, different times, etc.

As illustrated, computing device106may take the form of a specific computing device comprising one or more processing units202that perform data processing (e.g., in accordance with all or part of the techniques provided herein) coupled to memory204via one or more connections206. Processing unit(s)202may be implemented in hardware or a combination of hardware and software. Processing unit(s)202may be representative of one or more circuits configurable to perform at least a portion of a data computing procedure or process. By way of example but not limitation, a processing unit may include one or more processors, controllers, microprocessors, microcontrollers, application specific integrated circuits, digital signal processors, programmable logic devices, field programmable gate arrays, and the like, or any combination thereof.

Memory204may be representative of any data storage mechanism. Memory204may include, for example, a primary memory204-1and/or a secondary memory204-2. Primary memory204-1may comprise, for example, a random access memory, read only memory, etc. While illustrated in this example as being separate from the processing units, it should be understood that all or part of a primary memory may be provided within or otherwise co-located/coupled with processing unit(s)202, or other like circuitry. Secondary memory204-2may comprise, for example, the same or similar type of memory as primary memory and/or one or more data storage devices or systems, such as, for example, a disk drive, an optical disc drive, a tape drive, a solid state memory drive, etc. In certain implementations, secondary memory may be operatively receptive of, or otherwise configurable to couple to, computer readable medium220. As illustrated, memory204and/or computer readable medium220may comprise computer-implementable instructions222associated with data processing (e.g., in accordance with the techniques provided herein).

Reference is made next toFIG. 3, which is a schematic block diagram illustrating certain features of mobile station102, for example as inFIG. 1, capable of obtaining encoded version214of expected signal data and establishing a decoded version314.

FIG. 3shows a specific apparatus300in the form of a mobile station102which may act, at least in part, as a decoder114to establish one or more decoded versions314of the expected signal data based on one or more encoded versions214received from one or more computing devices106. In certain example implementations, apparatus300may take the form of any electronic device that may be reasonably moved about by a user.

With this mind, as illustrated inFIG. 3, example mobile station102may comprise one or more processing units302, memory304, connections306, a network interface308, one or more user input devices310, and one or more user output devices312. As shown, memory304may comprise a primary memory304-1, and/or a secondary memory304-2. Here, for example, primary memory304-1is illustrated as storing information relating to decoder114, which may be executed or used by processing unit(s)302. For example, decoder114may be executed by processing unit(s)302to generate a request116for encoded version(s)214and initiate transmission of such to one or more computing devices106via network interface308. For example, decoder114may be executed by processing unit(s)302to handle a response118received from one or more computing devices106via network interface308.

As illustrated, mobile station102may take the form of a specific computing device comprising one or more processing units302to perform data processing (e.g., in accordance with all or part of the techniques provided herein) coupled to memory304via one or more connections306. Processing unit(s)302may be implemented in hardware or a combination of hardware and software. Processing unit(s)302may be representative of one or more circuits configurable to perform at least a portion of a data computing procedure or process. By way of example but not limitation, a processing unit may include one or more processors, controllers, microprocessors, microcontrollers, application specific integrated circuits, digital signal processors, programmable logic devices, field programmable gate arrays, and the like, or any combination thereof.

Memory304may be representative of any data storage mechanism. Memory304may include, for example, a primary memory304-1and/or a secondary memory304-2. Primary memory304-1may comprise, for example, a random access memory, read only memory, etc. While illustrated in this example as being separate from the processing units, it should be understood that all or part of a primary memory may be provided within or otherwise co-located/coupled with processing unit(s)302, or other like circuitry within mobile station102. Secondary memory304-2may comprise, for example, the same or similar type of memory as primary memory and/or one or more data storage devices or systems, such as, for example, a disk drive, an optical disc drive, a tape drive, a solid state memory drive, etc. In certain implementations, secondary memory may be operatively receptive of, or otherwise configurable to couple to, computer readable medium320. As illustrated, memory304and/or computer readable medium320may comprise computer-implementable instructions322associated with data processing (e.g., in accordance with the techniques provided herein).

As illustrated in the example inFIG. 3, at times, memory304may store information relating to one or more functions212′, request116, response118, encoded version(s)214, decoded version(s)314, estimated initial position218, and an estimated current position316. Here, estimated current position316represents an estimated current position of mobile station as determined, at least in part, using at least a portion of at least one decoded version314along with signal information obtained from at least one transmitted signal received from at least one radio transmitter104.

In certain example implementations, as illustrated, mobile station102may further comprise one or more user input devices310(e.g., keyboard, touch screen, etc.) and/or one or more user output devices312(e.g., a display, a projector, a speaker, etc.). Hence, for example, location based service information may be presented to the user via some form of user output. Also, user input may be received which relates to location based services or other capabilities.

Although not illustrated, it should be understood that mobile station102may be enabled to perform a variety of tasks, some or many of which may be unrelated to location based services and/or other like position estimation capabilities. Thus, mobile station102may comprise a GPS or other like global navigation satellite system (GNSS) receiver (not shown) that may be used to establish estimated initial position218, for example. Additionally, it should be understood that decoder114may be representative of one or more capabilities associated with location based services and/or other like position estimation.

FIG. 4is a flow diagram illustrating certain features of a process400that may, for example, be implemented in an encoder112and/or other like capability one or more computing devices106(FIG. 1) to establish an encoded version214of expected signal data.

At block402, which may be optional, a request for an encoded version of expected signal data may be received from a mobile station. Such a request may take the form of one or more messages transmitted over one more communication links. Such a request may indicate an estimated initial position and/or estimated trajectory of the mobile device, and/or other information indicative of a specific structure and/or region of space for which an encoded version of expected signal data may be desired or useful.

At block404, expected signal data associated with one or more radio transmitters for a region of space (e.g., within or otherwise associated with a structure) may be obtained. For example, expected signal data may be obtained from one or more other resources (devices) and/or maintained locally by one or more computing devices. Some expected signal data may, for example, be based, at least in part, on data collected by one or more devices, such as, for example, a wireless signal “sniffer” and/or other like enabled device that detects and measures certain characteristics regarding transmitted signals from radio transmitters. Some expected signal data may, for example, be based, at least in part, on estimated data obtained from one or more models that may simulate and characterize a signaling environment. Some expected signal data may, for example, be based, at least in part, on human user inputs. Some expected signal data may, for example, be interpolated or otherwise derived from other expected signal data. In certain instances, for example, expected signal data may comprise information that may relate to a heat map or other like radio map.

In certain example implementations, expected signal data and resulting decoded versions of expected signal data may relate to the same or similar position points and/or different position points. Thus, an expected signal data may relate initially to a set of position points uniformly distributed by a first distance, and the decoded version may relate to a set of position points uniformly distributed by a second distance, wherein the first and second distances may be different. Hence, for example, a first distance may be twice that of a second distance, e.g., in examples wherein the decoder effectively reduces the number of non-anchor frames by half.

At block406, at least one subset of a plurality of identifiable position points may be identified. Here, for example, a subset may comprise an anchor point and one or more non-anchor points. At block408, for example, a subset may be identified based, at least in part, on one or more signal data threshold values. At block410, for example, an anchor point may be selected based, at least in part, on at least one of an expected navigation route, a characteristic of said structure, a particular period of time, a particular type of radio receiver, a particular type of transmitted signal, and/or other like information or any combination thereof. At block412, for example, radio transmitters for use in signal-based position estimation may be identified for use in signal-based position estimation in the region of the subset of position points.

At block414, at least one function may be determined which relates (or otherwise models) expected signal data associated with an anchor point to expected signal data associated with one or more non-anchor points. At block416, an encoded version of expected signal data may be established based, at least in part, on the function. At block418, at least a portion of an encoded version of expected signal data may be transmitted or otherwise provided to a mobile station.

FIG. 5is a flow diagram illustrating certain features of a process500that may, for example, be implemented in a decoder114and/or other like capability a mobile station102(FIG. 1) to establish a decoded version314of expected signal data210(FIG. 3).

At block502, which may be optional, a request for an encoded version of expected signal data may be transmitted or otherwise provided to one or more remote computing devices. Such a request may take the form of one or more messages transmitted over one more communication links. At block504, for example, an initial position and/or trajectory may be estimated for the mobile station. Thus, a request may indicate an estimated initial position and/or estimated trajectory of the mobile device, and/or other information indicative of a specific structure and/or region of space for which an encoded version of expected signal data may be desired or useful.

At block506, an encoded version of expected signal data may be received. Here, for example, an encoded version of expected signal data may be associated with one or more radio transmitters for a region of space within a structure.

At block508, at least a portion of an encoded version of expected signal data may be decoded based, at least in part, on at least one function. Here, for example, a function may be associated with at least one subset of a plurality of identifiable position points comprising an anchor point and one or more non-anchor points.

At block510, one or more transmitted signals may be received from at least one of the radio transmitters. Here, for example, signal characteristics may be obtained based on the received signals. For example, signal strength information may be measured or otherwise obtained. For example, signal propagation time information may be obtained. In certain instances, at block510, bidirectional communication may occur between a radio transmitter and a mobile station.

At block512, a current position of a mobile station may be estimated or otherwise determined based, at least in part, on a decoded version of expected signal data and one or more transmitted signals.

Attention is drawn next toFIG. 6A, which is floor plan diagram illustrating certain features of a portion of a example structure, e.g., a floor600of a building, for which encoded expected signal data may be provided to a mobile station102for decoding and use in estimating its position.

As shown, example floor600comprises a plurality of rooms602connected via a hallway604. Radio transmitters104-1,104-2and104-3are shown in room602-1, room602-4and hallway604, respectively. Mobile station102is illustrated has being positioned in room602-6. A navigation route606is illustrated extending from room602-8through hallway604to room602-6. Navigation route illustrates an example movement/trajectory of mobile station102. In its current position in room602-6, mobile station is illustrated as being capable of receiving transmitted signals from radio transmitters104-1,104-2and104-3.

Reference is made next toFIG. 6B, wherein a plurality of position points608are shown overlaying example floor600. Here, for example, position points608are arranged in a grid pattern having rows parallel to an x-axis and columns parallel to a y-axis (e.g., see directional arrows610). Notice that in this example some position points are not shown as they fall on the lines representing walls. Also, note that in this example, position point are not shown in room602-4, which in this example, is deemed inaccessible for the mobile station's user (e.g., this room may be an equipment space, etc.). Hence, in certain instances, encoder112and/or decoder114may ignore such position points.

Reference is now made toFIG. 7, which is a perspective rendering of room602-6within example floor600. Here, by way of visual illustration, a sloping plane702is depicted as representing a heat map (e.g., via a shading and three-dimensional rendering). This example sloping plane702may, for example, be generated using a linear function that models a relationship of expected signal data for position points within the room. Here, for example, a magnitude of the applicable signal data is greater at one corner (e.g., see magnitude704-1) than it is at the other three corners (e.g., see magnitudes704-2and704-3). Thus, for example, if the signal data is associated with a signal strength then in this example, a transmitted signal from a radio transmitter104(not shown) is expected to have the highest strength at or near the corner with magnitude104-1(e.g., the radio transmitter may be located closest to this corner). Conversely, for example, if the signal data is associated with a signal propagation time then in this example, a transmitted signal from a radio transmitter104(not shown) is expected to have the shortest propagation time at the corner with magnitude104-3(e.g., the radio transmitter may be located closest to this corner).

Position points606-1,606-2and606-3are also illustrated inFIG. 7along with representative magnitude vectors extending upward to different values on sloping plane702. Accordingly, it may be seen that expected signal data for each of these position points may be related based on a function. Thus, in this example, one of these position points may be selected as an anchor point and the other related to the anchor point as non-anchor points. For example, positioning point606-1may be selected as an anchor point and position points606-2and606-3related as non-anchor points in an encoded version of expected signal data.

As illustrated in the examples herein, an anchor point may be used to define a local model which may represent a good fit for nearby non-anchor position points. Thus, for example, with RSSI or RTT signal data, a smooth function may serve as a model within local regions such as a room, or within a segment of hallway.

Accordingly, in one example of an encoded version of expected signal data, a first entry for an anchor point may comprise a bitmap indicating which radio transmitters may be useful for ranging from this anchor point. For instance, if there are M radio transmitters serving a floor, a bitmap may be M bits long, wherein a “0” may identify that a radio transmitter may not be useful (e.g., perhaps it is out of range) and a “1” identify that a radio transmitter may be useful. Such example encoded version of expected signal data may also comprise information relating to a function used to model each useful radio transmitter. By way of example, if a linear function is used then for each anchor point an encoded version may comprise a list or other like arrangement of parameters for each radio transmitter as modeled. For example, in the following linear function four parameters, namely c1, c2, c3, and c4 may be provided. Thus, an expected signal data value may be given by:
Mean Value=c1*(x−x0)+c2*(y−y0)+c3; Variance Value(Sigma)=c4
Where x0, y0 are the coordinates of the anchor point. Note that the expected signal data value for the anchor point is mean=c3 and sigma=c4.

Thus, Table 1 below shows an example, format for an Anchor Point as represented in an encoded version:

In this example, a non-anchor point may be determined using a (decoding) function to determine a mean and sigma using an (x−x0) and (y−y0) distance between itself and the anchor point. In certain example implementations, such distance differences may be provided in a lookup or other like form which lists position points (e.g., by identifier, etc.). Thus, for example, in certain instances non-anchor points as represented in an encoded version may occupy log 2(N) bits which may refer to a “best” anchor point, or simply an identifier of the anchor point, where N is the number of anchor points. Such a format may allow non-anchor points to occur in any order.

Thus, Table 2 below shows an example, format for a non-anchor point as represented in an example encoded version:

Alternatively, for example, non-anchor points may be listed (e.g., one at a time) along with a related anchor point. This example format may save space and/or may allow for a “tiled” solution, e.g., wherein each tile corresponds to a subset of position points (anchor point and its related non-anchor points). Such tiling may, for example, break up a large data file (map) into segments which may be selectively transmitted to a mobile station.

Thus, Table 3 below shows an example, format for non-anchor points as represented in an example encoded version:

As an example, consider again a structure/region with ten thousand position points and sixteen radio transmitters, wherein mean and sigma are each represented by one byte. Recall, that the original expected signal data (for all radio transmitters) would amount to about 320 kB. Now consider having five hundred and twelve anchor points. Assume that one byte is used for model coefficients (c1, c2, c3, and c4). Suppose each anchor point only refers to the nearest eight radio transmitters in the sixteen-bit radio transmitter bitmap. Also, suppose each non-anchor point reference uses sixteen bits to refer to its related anchor point identifier (ID). As such the size of the encoded version is about 35 kB, which is about a 10× savings. If non-anchor points are listed immediately after the corresponding anchors (e.g., in a tiled format), rather than using explicit references, the encoded version would be about 16 kB, which is about a 20× savings.

In certain further example implementations, an encoder may be arranged to select anchor points to ensure that the error in a decoded version remains within a desired level. This may be addressed, for example, by identifying and implementing an appropriate function and model parameters for each anchor point. In certain instances a heuristic based on a reduced routing graph may be useful. Here, for example, it may be useful to reduce a number of position points for consideration as anchor points by ranking position points in a routing graph. For example, such a ranking may be based, at least in part, on how large a radius of substantially open space surrounds a given position point.

With this in mind, for example, an encoder may identify a subset of position points and/or select an anchor point based, at least in part, by first considering “unvisited” points from a routing graph which have a highest rank. Next, a least squares fit may be made of model parameters to expected signal data values for all points within a routable distance D of the anchor point (e.g., using a routable distance may prevent crossing walls and/or other like obstacles). Once related to an anchor point, these non-anchor points may be marked in the routing graph as “visited”. Such a process may continue until no more points can be selected, or until a maximum allowed number of anchor points has been reached.

In this manner, for example, the decoder may identify position points that relate to the anchor point with an error less than some threshold value (e.g., 3 dB). Note that a typical standard deviation for an RSSI is often about 4-6 dB. The error may be reduced further, if needed, by adding more anchor points (e.g., near areas with high error).

Anchor points may be used to efficiently partition a graph into distinct regions, where each region may relate to a subset of position points associated with an anchor point. These regions may, for example, be locally contiguous or locally confined areas where RSSI or RTT may be represented accurately by planes and/or other simple curves, and/or even certain like non-linear functions. Thus, such partitioning introduced during encoding may be useful as well as large data files (graphs) may be sent as tiles. By sending tiles that correspond to the expected signal data regions, the problem of “breaking” a large graph into pieces for transmission as tiles may be inherently solved. Furthermore, for example, such tiles may be chosen based on routing graph and/or other like information. Thus, as a user traverses a routing graph, an appropriate tile or tiles (e.g., for position points within routing distance D) may be generated and transmitted.

In certain example implementations, certain model parameters may relate to certain times or time periods, etc. Thus, for example, if time is a parameter, an expected signal value may be based on (x, y) and some time. Here, an appropriate function and model parameters may be provided to account for periodic changes due to day verses night, for example, based on expected changes in the number of people in a venue, doors being opened and closed, and so forth.

It should be further recognized that a computing device performing the encoding and tiling may make certain tradeoffs between data accuracy, communication bandwidth, available memory, and/or decoding complexity. In certain instances, for example, there may be different encoded versions (e.g., map representations, different number of anchor points, different lookup formats, etc.) for different types of mobile stations. Further, in certain instances, different models, functions, and/or the like may be implemented for different anchor points.

In certain example implementations, certain information regarding anchor points and/or non-anchor points may be further used to encode user density data, other type of data about an environment, and/or the like, which may be considered in some manner. For example, a routing function or other like capability may consider such information to improve routing decisions, etc.

The example techniques described herein may help to avoid some drawbacks typically seen in certain data compression schemes. For example, while one might use a lossless compression, such as zip, but the resulting compressed file may still be significantly large. One might also consider converting signal strength information to an image, for example by letting each grid point be a pixel, and then use known image compression such as JPEG. Here, however, there may be of a lack of flexibility, since typical image compression may not relate or consider certain underlying physical aspects of a signal. Also, typical image compression uses regular blocks, rather than taking the geometry of the building into account, which might lead to compression artifacts across walls, or other areas with sharp changes in signal characteristics.

The methodologies described herein may be implemented by various means depending upon applications according to particular features and/or examples. For example, such methodologies may be implemented in hardware, firmware, and/or combinations thereof, along with software. In a hardware implementation, for example, a processing unit may be implemented within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers, microprocessors, electronic devices, other devices units designed to perform the functions described herein, and/or combinations thereof.