WO2016138800A1 - Optimizing position estimates of a device for indoor localization - Google Patents

Abstract

Described are techniques for optimizing position estimates for indoor localization. One technique describes combining the strengths of trilateration and fingerprinting. This technique creates a contour including reference points with the same signal level of a target device. The position of the device may then be estimated based on the juncture of all the contours and an optimization formulation following the spirit of trilateration may be employed to minimize the distance between the estimated position and the contours. In addition, a second technique describes fusing noisy fingerprints with uncertain mutual distance information. This technique may be employed as a generic framework applicable to a wide range of wireless fingerprints and may reduce errors with a convex-optimization formulation.

Description

OPTIMIZING POSITION ESTIMATES OF A DEVICE FOR INDOOR LOCALIZATION

PRIORITY CLAIM

This application claims priority to U.S. Provisional Patent Application Nos. 62/176,979, filed on March 3, 2015, entitled “FUSING NOISY FINGERPRINTS WITH DISTANCE BOUNDS FOR INDOOR LOCALIZATION” , and 62/283,857, filed on September 14, 2015, entitled “CONTOUR-BASED TRILATERATION FOR FINGERPRINTING INDOOR LOCALIZATION” , the entireties of which applications are hereby incorporated by reference herein.

TECHNICAL FIELD

This disclosure generally relates to indoor localization, and techniques for optimizing position estimates of a device for indoor localization.

BACKGROUND

Indoor location-based service has attracted much attention in recent years due to its commercial potential. The quality of such service largely depends on the localization accuracy of users. Among all the current indoor localization techniques, fingerprint based approach emerges as a promising one.

In traditional fingerprint based approaches, a comparison between a received location and stored fingerprint of a reference point is conducted using some similarity metric. Based on the comparison, an estimate of a position is performed. With such a technique, however, errors in location estimation are inevitable due to random signal fluctuations during measurements. As targets are often considered independently, measurement noise or uncertainty often degrades the localization accuracy. Accordingly, it has been observed that localization errors can be significant (e.g., often more than 10m) under large open indoor environment such as malls, train stations, or airports. Thus, traditional fingerprint based localization techniques may not provide the necessary accuracy in certain scenarios.

Other problems with the state of the art, and corresponding benefits of some of the various non-limiting embodiments described herein, may become further apparent upon review of the following detailed description.

SUMMARY

A simplified summary is provided herein to help enable a basic or general understanding of various aspects of illustrative, non-limiting embodiments that follow in the more detailed description and the accompanying drawings.

In an implementation, described is a method of locating a device using trilateration and signal contours. The method may include identifying, by a system comprising a processor, wireless access point devices within an area and determining a received signal strength indicator (RSSI) of a device to be located. The method may also include determining, for each respective wireless access point device of the wireless access point devices, respective reference point devices each having a respective RSSI, with respect to the respective wireless access point device, that is similar to the RSSI of the device and respective contour data representing a respective contour that maps distances of the respective reference point devices from the respective wireless access point device. Accordingly, a location of the device may be determined based on a juncture determined from the respective contour data of the respective wireless access point devices.

In another implementation, described is a method of locating a device by fusing noisy fingerprints with distance bounds information. The method may include populating, by a server comprising a processor, a location fingerprint data store for reference point devices within an area within which a device is to be located based on time samples of received signal strength indicators at an access point device for the reference point devices. The method may include receiving distance information for the device based on an RSSI vector of the device at the access point device and determining an upper distance bound and a lower distance bound of a location of the device based on the distance information and the location information stored in the location fingerprint data store. The method may also include determining a metric to evaluate a difference between the distance information and location information stored in the location fingerprint data store and generating relaxation data representing a semi-definite programming relaxation based on the metric using the upper distance bound and the lower distance bound of the location as constraints on the generating. Accordingly, the device may be located based on the relaxation data.

In another implementation, described is a system for locating a device using trilateration and signal contours. The system may include a memory to store instructions and a processor, coupled to the memory, to execute or facilitate execution of the instructions to identify wireless access point devices within an area and determine a received signal strength indicator (RSSI) of a device to be located. The processor may also execute or facilitate execution of the instructions to determine, for each respective wireless access point device of  the wireless access point devices, respective reference point devices each having a respective RSSI, with respect to the respective wireless access point device, that is similar to the RSSI of the device and respective contour data representing a respective contour that maps distances of the respective reference point devices from the respective wireless access point device. Accordingly, the system may determine a location of the device based on a juncture determined from the respective contour data of the respective wireless access point devices.

In another implementation, described is a system for locating a device by fusing noisy fingerprints with distance bounds information. The system may include a memory to store instructions and a processor, coupled to the memory, that may execute or facilitate execution of the instructions populate a location fingerprint data store for reference point devices within an area within which a device is to be located based on time samples of received signal strength indicators at an access point device for the reference point devices and receive distance information for the device based on an RSSI vector of the device at the access point device. The processor may also execute or facilitate execution of the instructions to determine an upper distance bound and a lower distance bound of a location of the device based on the distance information and the location information stored in the location fingerprint data store, determine a metric to evaluate a difference between the distance information and location information stored in the location fingerprint data store, and generate relaxation data representing a semi-definite programming relaxation based on the metric using the upper distance bound and the lower distance bound of the location as constraints on the generating. Accordingly, the system may locate the device based on the result of the semi-definite programming relaxation process.

This summary is not intended, however, as an extensive or exhaustive overview. Instead, the sole purpose of this summary is to present some concepts related to some illustrative non-limiting embodiments in a simplified form as a prelude to the more detailed description of the various embodiments that follow. It will also be appreciated that the detailed description may include additional or alternative embodiments beyond those described in this summary.

Other embodiments and various non-limiting examples, scenarios, and implementations are described in more detail below.

BRIEF DESCRIPTION OF THE DRAWINGS

Various non-limiting embodiments are further described with reference to the accompanying drawings in which:

FIG. 1 illustrates an example operating environment, in accordance with various embodiments.

FIG. 2A illustrates a diagram of trilateration using signal contours, in accordance with various embodiments.

FIG. 2B illustrates an example diagram of a framework for a trilateration using signal contours system, in accordance with various embodiments.

FIGs. 3A-3C illustrate mean errors with the trilateration using signal contours technique under various conditions, in accordance with various embodiments.

FIGs. 4-6 illustrate example simulation environments for deploying the trilateration using signal contours technique, in accordance with various embodiments.

FIGs. 7-23 illustrate various simulation results associated with deploying the trilateration using signal contours technique in various simulation environments, in accordance with various embodiments.

FIGs. 24 illustrates a process associated with the trilateration using signal contours technique, in accordance with various embodiments.

FIG. 25 illustrates an example diagram of a framework for fusing noisy fingerprints with distance bounds information, in accordance with various embodiments.

FIGs. 26A-26B illustrate example simulation environments for deploying the fusing noisy fingerprints with distance bounds technique, in accordance with various embodiments.

FIGs. 27-41 illustrate various simulation results associated with deploying the fusing noisy fingerprints with distance bounds technique in various simulation environments, in accordance with various embodiments

FIGs. 42 illustrate a process associated with the fusing noisy fingerprints with distance bounds technique, in accordance with various embodiments.

FIG. 43 illustrates a block diagram of a computing system operable to execute the disclosed systems and methods, in accordance with various embodiments.

DETAILED DESCRIPTION

With the rapid development of mobile communication and the pervasive computing technology, the requirement of obtaining location-aware service is rapidly increasing. Though Global Positioning System (GPS) can provide accurate and reliable position information for location services, it cannot be used effectively for an indoor environment. To overcome this limitation, researchers have proposed many creative localization technologies such as a sensor network, radio frequency identification (RFID) ,  and Wi-Fi. Among them, Wi-Fi positioning technology has attracted extensive attention because it is built upon mobile phones, which are used widely all over the world. Crowded places, such as street, office buildings, shopping malls, hotels, and airports, usually have a large number of wireless access points (APs) , which form a wide coverage of Wi-Fi network. Therefore, it is feasible and practicable to adopt the Wi-Fi network and mobile phone to implement personnel positioning under indoor environments.

A common and widespread localization technique used for positioning with APs is based on measuring the intensity of the received signal (received signal strength indication, or RSSI) and using a fingerprint-based approach. A fingerprint-based indoor localization approach is usually conducted in two phases. In the offline (survey) phase, a site survey is conducted to collect RSSI vectors of reference points (RPs) at known locations. The vectors of these RSSIs form the fingerprints of the site and may be stored in a database (or data store) . In the online (query) phase, a target device samples an RSSI vector at its position. In traditional fingerprinting, a comparison between the RSSI vector of the target device and stored fingerprints of the RPs are conducted using some form of similarity metric. It then estimates the target device’s position by matching the target’s RSSI to a known location of a RP.Described herein are two techniques for optimizing position estimates of a target device for indoor localization.

First, a contour-based trilateration technique is described (also referred to herein as “INTRI” ) . This technique combines the strengths of trilateration with fingerprinting to form a contour including reference points with the same signal level as the target device. The position of the target device may then be estimated based on the juncture of all the contours based on an optimization that minimizing the distance between the estimated position and the contours.

Second, a technique that fuses noisy fingerprint data with distance bounds information is also described (also referred to herein as “Wi-Dist” ) . This technique relates to fusing noisy fingerprints with distance bounds information to improve indoor localization accuracy. This distance information may be spatial or temporal. Accordingly, this technique provides a generic framework applicable to a wide range of sensing techniques and enables indoor localization independent of the manner in which distances are measured.

It should be noted that the disclosed techniques may be implemented as a method, apparatus, or article of manufacture using programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof to implement the disclosed subject matter.

1. Example Operating Environment

FIG. 1 illustrates an example schematic of an operating environment, in accordance with various embodiments. The example operating environment may include one or more device (s) 102 (or device (s) to be located, or target device (s) ) , access points or APs 104a-d, reference points or RPs (shown as 110) , server (s) 106, and data store (s) 108. The device 102 may be part of a variety of computing devices such as a mobile device including a mobile phone or “smartphone, ” tablet, laptop, netbook, personal digital assistant ( “PDA” ) , media device, watch, or other types of device.

The APs 104a-d may be a suitable device that allows a component (e.g. device 102 or RPs 110) to connect to a network using, for example, a Wi-Fi, or other wireless protocol. The APs 104a-d may be a standalone device or may be part of another component.

The device 102 may be in signal communication with one or more APs 104a-d. For example, the device 102 may connect to one or more APs 104a-d via a Wi-Fi protocol. As further described herein, this signal information may be used to locate the device 102. For example, APs 104a-d may be within an area 105 that receives Radio-Frequency (RF) signals from the device 102 to measure an RSSI.

The RPs 110 may be a suitable device that connects to one or more APs 104a-d via a wireless protocol. RPs 110 may also be in signal communication with one or more APs 104a-d. The APs 104a-d may also receive RSSI information from one or more RPs 110. This information may form a fingerprint database (or data store) as described further herein. For example, the server 106 may compile such information (e.g. RSSI vectors and location information) of set of RPs 110 and store such information in a data store 108 during a site survey as further described herein.

The server 106 may be directly accessible by the components, or through an intermediary. The server 106 may access a remote platform such as cloud computing arrangement or service. The remote platform may also include a server 106 or data store 108. The server 106 can also be hardware and/or software (e.g., threads, processes, computing devices) . The server 106 can house threads to perform transformations by employing one or more embodiments as described herein.

One or more components of FIG. 1 may communicate with each other via a network, which may be a local network, wide-area network (including the Internet) , or other suitable communications network. The network may be implemented on any suitable platform including wired and wireless technologies. For example, the server 106, RPs 110, and device 102 may communicate with one or more of the APs 104a-104d using one of the 802.11 standards (or Wi-Fi as referred to herein) .

It should be noted that one of more of the components described in FIG. 1 may include or be part of a computing system 1900 as further described herein. For example, the device 102, RPs 110, or the server 106 may be a computing system 1900.

2. CONTOUR-BASED TRILATERATION TECHNIQUE ( “INTRI” )

Generally, in a trilateration approach, a target device (target, device, or device to be located) first measures its distances to a number of landmarks of known locations. It then estimates its position which best matches these measured distances (e.g., given by minimizing the error between the measured distances and the distances from the position to the landmarks) . Such a localization technique has been widely used outdoors, such as applications in GPS and cellular positioning, where the landmarks are satellites and base stations (e.g., cell towers) , respectively. However, it cannot be directly applied for indoor localization due to issues such as non-line-of-sight measurement and multipath fading. Though fingerprinting overcomes these issues, its accuracy is often hampered by signal noise and the choice of similarity metric between signal vectors.

Accordingly, a first technique referred to herein as INTRI (Indoor Trilateration) is disclosed, which is an efficient indoor localization technique. This technique employs the concept of trilateration in a fingerprint-based environment. By treating the RSSI from each AP individually (e.g. instead of as a single signal vector) , INTRI does not suffer from the problem of a dispersed set of neighbors to the same extent as other techniques. Instead, it is more effective at addressing random signals (e.g. due to signal noise and measurement uncertainty) since it is not strictly based on a fingerprint similarity comparison.

For a signal level received from an AP by a target device, INTRI may form a contour including all of the RPs of the same signal level for that AP, taking into account the signal noise. The target device may be locate based on a juncture of all the contours. Using an optimization formulation following the spirit of trilateration, the target devices’s location may be found by minimizing the distance between the position and all the contours. INTRI may furthe utilzie an online algorithm based on signal correlation to efficiently calibrate heterogeneous mobile devices to achieve higher accuracy. As described herein, INTRI has been implemented in a simulation for experiments in an international airport, shopping mall and a university campus. These simulations show that INTRI outperforms recent schemes by having a lower location error (often by more than 20％) than some traditional finger-print based approaches.

Moreover, as described herein INTRI integrates the relatively accurate trilateration technique as used in outdoor environments with indoor fingerprinting, and thus,  combines the strengths of both approaches. More specifically, it does not necessarily require the positions of APs and line-of-sight (LoS) measurements, and locates the target device at the junction of its measured signal levels by reducing or removing the dispersion problem. Although Wi-Fi RSSI fingerprinting is primarily discussed herein, INTRI is a general approach applicable to other fingerprint signals such as channel state information, visible light, RFID, or other suitable techniques. It should be noted that INTRI, may also be a complementary module to existing sensor localization systems without necessarily modifying or adding any specialized infrastructures.

FIG. 2A illustrates a diagram of trilateration using signal contours (INTRI) , in accordance with various embodiments. In FIG. 2A, an example environment may include an AP (e.g. APs 104a-d as shown in FIG. 1) . In this instance, there are three APs (AP1, AP2, and AP3) . A signal strength (e.g. RSSI) from a certain AP may be measured by the target device (e.g. device 102 as shown in FIG. 1) . For that AP, a contour may be formed from the spatially distributed RPs (e.g. RPs 110 as shown in FIG. 1) whose signal level for the AP is similar to (e.g. matches or within a tolerance) the signal level for the target device, subject to its statistical fluctuation. Given the target device’s RSSI vector, the corresponding contour for each of the APs (three contours shown in the figure) may be formed. Following the spirit of trilateration, the target device’s position may then be estimated by minimizing its distances to the signal contours. Accordingly, the target device may be located somewhere on the contour line. It should be noted that FIG. 2A shows a continuous contour, but the signal contour may also comprise discrete points in space.

For an example practical deployment of INTRI, some issues are noted:

Forming contours for random signals: Signal measurement is inherently noisy. Constructing contours can thus consider random fluctuation in order to effectively locate the target. Fingerprints and target RSSIs received can be statistically analyzed so as to construct contours under random signals. Accordingly, as the target is likely to be located at position where contours meet, described herein are techniques to locate such a region.

Efficient contour-based localization algorithm: Described is a contour-based localization algorithm based on linear programming formulation. Following the spirits of trilateration, the technique estimates a target location with the objective to minimize the distances to the contours obtained above.

Adaptive online calibration for heterogeneous devices: Typically, for the same signal, different devices may have different readings. Accordingly, device readings may benefit from being mapped, or “calibrated, ” to the corresponding signal levels stored in the database so that the contours may be correctly discovered. Offline calibration for all different  devices, however, is not always efficient or scalable. Accordingly, described herein is an efficient and practical online scheme to calibrate devices, which adapts the target measured RSSI according to the stored fingerprints based on signal correlation. Using this efficient approach, INTRI achieves higher scalability in heterogeneous devices and robustness in “noisy” environments.

FIG. 2B illustrates an example diagram of the “INTRI” system framework, in accordance with various embodiments. The Wi-Fi fingerprint database as shown may be initialized by a site survey, storing, for example, (location, RSSI vector) pairs for each RP and vendor information of the devices used for data collection. After completion of the offline (or site survey phase) , the system may be ready for online estimation.

In the online phase, INTRI may check the vendor information of the target device and if it is different from the devices used for site survey, the target RSSI vector may be calibrated using the stored fingerprints. The calibrated RSSI vector may then be used to construct the signal contours. Given the signal contours, INTRI formulates a linear programming to jointly minimize the distances to the contours and estimates the target device’s position.

2.1 Related Work

Related works in the field are briefly discussed in this section. Pattern recognition techniques have been widely studied in Wi-Fi fingerprinting localization. More recently, advanced techniques on pattern matching have been investigated including a signal propagation model that derives RSSI at different locations and utilizes rigid matching between signals and distances to determine the target location. More recent works further utilize the labeled fingerprints to derive signal propagation model and achieve higher accuracy.

In contrast to the above works, the INTRI approach described herein combines the advantages of fingerprinting and trilateration. This approach employs a geometric scheme (with spirits of trilateration) based on random fingerprint signals to constrain the target region. In addition, by formulating a linear programming, INTRI may achieve improved localization accuracy without neighbor dispersion. INTRI may also be compatible to emerging fingerprint update schemes to achieve higher robustness in real deployment.

Some other recent works leverage the temporal or spatial RSSI patterns for localization. These works consider location-dependent patterns such as the trend of RSSI sequences along corridors, order of RSSIs from different APs, or the unique existence of some Wi-Fi APs at some area. Once the target measures such patterns, its location is then  mapped to the area. These patterns achieve promising results for constrained and narrow environment with well-defined user trajectories (like corridors or offices) . In contrast, the contours in INTRI may be solely derived from fingerprints and are applicable to any indoor environment. Furthermore, INTRI does not necessarily require the positions of APs and LoS measurement.

In addition, calibrating different devices has been studied in recent works. Traditional offline calibration, however, causes extra manual efforts in real deployment and hence is not easily scalable. Given the target RSSI measurement, some approaches utilize the deduction (or ratio) between AP signal values to calibrate the devices. However, large noise and fluctuation in signal levels can degrade the quality of the above calibration. Some learning-based approaches utilize expectation maximization to calibrate the signal difference. In contrast, INTRI proposes a more efficient and robust scheme which maps the target signals to the signal space in a fingerprint database.

To improve fingerprint localization, sensor fusion has attracted intensive attention recently. Using the smartphone inertial sensors, fusing motion information has been studied extensively to improve fingerprint-based positioning. Peer-assisted localization has also been recently studied, making use of Wi-Fi Direct and high-pitch sound to measure the distance between peer devices as extra position constraints. Again, in contrast to the above fusion approaches, an implementation of INTRI may solely rely on existing Wi-Fi measurements to achieve higher scalability.

2.2 Illustrative Simulation and Results of INTRI

By way of illustrating the efficiency of INTRI, discussed herein are non-limiting simulations. For example, simulation and experimental trials were conducted in the Hong Kong International Airport (HKIA) , the Hong Kong Cyberport mall (HKCP) and at a university campus (HKUST) . Both simulation and experimental provide further evidence of the benefits of INTRI .

For example, one of the simulation environments (100×90m²) was based in an airport. Considered were all the Wi-Fi transmitters and receivers that were equipped with omni-directional antennas. The RSSI g^l (dBm) at distance d from AP l is given by the LDPL model:

where

is the Gaussian measurement noise. In our simulation, we set transmission power P^TX 25dBm, the path loss exponent γ 4.0, the reference path loss L₀ 37.7dBm and the reference distance d₀ 1 m. Based on empirical observations, if g^l<-95 dBm, the target cannot detect the signal of this AP and we discard this measurement.

Evaluated were the performance of INTRI in terms of AP number, signal noise and survey grid size in the simulation environment. INTRI was compared with four state-of-the-art schemes:

EZPerfect (EZPerf) : a model-based Wi-Fi localization scheme which considers deriving signal propagation model from fingerprint data. Given Wi-Fi fingerprints, EZPerfect first finds the matching relationship between signals and distances from APs, and then locates targets with a genetic algorithm solving trilateration problem.

KL-divergence (KL-div) : which utilizes the Kullback-Leibler (KL) divergence distance between the signal distribution at an RP and target during comparison. Then the top k RPs with the minimum KL-divergence are utilized for final estimation.

Weighted k-Nearest Neighbors (WKNN) : which computes the cosine similarity between the fingerprints and the target RSSI vector, and finds the weighted average of k-Nearest Neighbors of highest cosine similarity to estimate the target location.

Probabilistic algorithm (Horus) : which calculates the probability distribution of the RSSI values at each RP. Given a target RSSI vector, Horus computes the overall probability of the vector at each RP and finds the top several ones with the maximum likelihood as the target location.

Unless otherwise stated, the following baseline parameters was used in the simulation: 15 APs are deployed； σ_dB＝5 dB (Equation (1) ) ； k＝20 for KL-divergence, WKNN and Horus algorithm； z₀＝3 (Equation (14) ) ； survey grid size is 5m.

Let x_m be target m’s true location and 

 be its estimated location. The performance metric in the experiment is the mean error (unit: m) of the estimated targets in set V:

FIG. 3A shows the mean localization errors versus the number of APs. The performance of all the algorithms improves as the number of APs increases. As there are  more APs deployed in the site which help differentiate the RPs, the error decreases. Compared with these traditional algorithms, INTRI may achieve lower errors under different numbers of deployed APs. This is because INTRI may consider differentiating contours using contour weights, which helps distinguish the RPs and prevents dispersed estimations.

FIG. 3B shows the mean localization errors against the signal measurement noise (σ_dB in Equation (1) ) . As shown, the performance of all the algorithms may degrade as the noise in Wi-Fi signals increases. Signal noise may lead to dispersed nearest neighbors and distance measurement error, which degrades the accuracy of traditional pattern matching algorithms and EZPerfect. Moreover, in different indoor environments ranging from spacious halls or narrow corridors, the signal fluctuation of fingerprints can be different. Even under large fingerprint variation, INTRI may achieve better accuracy. Different from these traditional and state-of-the-art algorithms, INTRI may consider the signal variation in the contour construction. Therefore, it may achieve higher robustness and localization accuracy under large signal noise.

FIG. 3C shows the mean localization errors versus survey grid size, (i.e., the site survey grid width (in square shape) was varied to change the fingerprint density) . As shown, accuracy may degrade as grid sizes increase, illustrating the tradeoff between survey cost and localization accuracy. Accordingly, INTRI considers the signal contours in the formulation to constrain the target region. By minimizing distances to contours, INTRI prevents dispersion of nearest neighbors and may achieve higher accuracy.

2.2.1 Simulation Results

In addition to the simulation, experimental trials of INTRI were conducted in the Hong Kong International Airport (HKIA) , a university campus (HKUST) , and the Hong Kong Cyberport (HKCP) . First, the experimental settings are presented. As the measured AP signals are different in the three sites, the comparative studies over these differences are discussed. Then the experimental results in HKIA followed by those in HKUST and HKCP are illustrated.

In the experimental studies the same s algorithms and comparison metrics as in Section 2.2 were utilized. In addition, compared are the device calibration scheme in INTRI with two recent methods, signal strength difference (SSD) and signal ratio (SR) . SSD utilizes the differences between pairs of AP signal values as patterns. Similarly, SR calculates the ratio between pairs of AP signals as Wi-Fi fingerprints. Both methods aim at compensating the signal difference among heterogeneous devices.

FIG. 4, shows the corresponding survey floor plan of RPs and targets in HKIA. In the 10,000 m² site, 340 RPs and 1,100 targets were collected. The locations of RPs are predefined on the indoor map. To balance between localization accuracy and survey cost, a 5m grid density in fingerprinting was used. At each RP, signal data was sampled from four different directions (north, west, south and east) . For each direction, 15 samples of RSSI vectors were collected. The ground truth of the target locations was also predetermined in grid form (in the testing, the surveyors found the RP or target locations from the nearest pillars, floor tiles and other noticeable indoor landmarks) . Note that the data sampling was conducted with people around, and temporal fluctuation existed within the fingerprints and target signals. The time interval between samples in Wi-Fi scanning is 1 second.

Wi-Fi APs were officially pre-deployed. Thus, their number, locations and transmission power were already settled before conducting a site survey. In the data preprocessing, the mobile APs tethered by smartphones we filtered out, and the signals of virtual APs (VAPs) were combined. Overall 360 APs were detected (each RP measures 47 APs on average) . Part of these APs may be installed outside the survey site since their coverage in the site is relatively small and signals are globally weak. The target samples are collected one month later than RP collection. For schemes like KL-divergence and Horus which are device dependent, the calibration scheme as discussed herein was utilized.

In the HKUST campus and the HKCP shopping mall, fingerprint collection, target sampling, and data preprocessing were the same as those in the airport.

FIG. 5 shows the RPs and targets on campus (100×50m²) . In the campus corridor environment, 250 RPs and 475 targets were collected. FIG. 6 shows the RPs and targets in the shopping mall (150×100m²) . In the mall, 680 RPs and 680 targets were collected. In both maps, the blue dots represent RPs and the red diamonds are targets. Similar to airport, the officially deployed APs were given and manually changing their settings (installation locations and TX power) was not permitted. In the site survey of campus corridor, overall 320 APs were detected (each RP measures 24 APs on average) . In the site survey at shopping mall, overall 190 APs were detected (average 28 APs at each RP) .

FIG. 7 shows the histograms of AP numbers detected by targets at different sites. On average, each target detected 16 APs on HKUST and 22 APs in HKCP. In HKIA, each target detected 16 APs on average. Though targets in HKIA and HKUST have a similar detected AP number, the survey site in HKUST was smaller and hence it had a denser AP deployment. Moreover, the signal coverage of APs in the campus corridor and HKCP was constrained by the wall partitions, which helps differentiate the RPs. Therefore, better  localization performance was expected on HKUST and HKCP than in HKIA. Based on these detected APs, the effect of different received AP numbers was evaluated.

FIG. 8 shows the corresponding signal noise in each survey site. Shown is the cumulative probability of the σ^l according to Equation (12) . As shown, there was a smaller signal noise in HKUST and HKCP than in HKIA. This is because the airport boarding area was large open space with many airline passengers, which leads to higher signal uncertainty. Based on the difference in signal noise, the parameter z₀ in Equation (14) for online localization was adjusted.

FIG. 9 shows the mean localization errors of INTRI in three sites given different z₀. In general, the error first decreases and then increases. This is because the localization error depends on two factors: signal noise and RP fingerprint differentiation. When z₀ is small, the tight contours cannot accommodate the large measurement uncertainty in target. Thus, the error is high. As z₀ increases, the contours can bound the target, and hence the error decreases. As z₀ further increases, the error increases because, as contours become wide, the differentiation between RPs becomes weak. Then more distant RPs are included in localization. The result shows that without sufficient RP fingerprint differentiation, wide contours would not be beneficial. Compared with HKUST and HKCP, z₀ is slightly larger in HKIA due to higher signal variance in the airport (as shown in FIG. 8) . Thus, in the experiment, z₀＝4 in HKIA, z₀＝3.5 in HKCP, and z₀＝2.5 in the HKUST campus.

FIG. 10 shows the running time CDF of INTRI on the targets at different sites. It shows that at the three sites, INTRI shows different computation time due to the difference in RP numbers and detected AP numbers at a target side and an RP side. The running time of INTRI at HKCP was shorter than that of HKIA and HKUST. It is mainly because many of the detected APs in HKCP were installed in stores and have limited coverage (small contours) due to wall partitions, compared with those in HKIA and HKUST. A target can be quickly mapped to smaller areas and therefore the overall computation becomes much shorter.

FIG. 11 shows the linear signal model of four different target estimations in HKIA using target data (x-axis) RP signals (y-axis) . Based on the a and b, obtain were the calibrated signal strength, 

 for each given target. Shown is that the linear calibration scales up at the target, which matches our observation in FIG. 22.

FIG. 12 compares the cumulative errors of different device calibration schemes in the airport. Uncalibrated signals in INTRI were used as the baseline case. The  calibrated INTRI may improve from the uncalibrated scheme, and also outperforms SSD and SR.This is because the proposed scheme jointly considers the relative trend and the RSSI adjustment model when calibrating devices. Unlike SSD and SR, the AP signal trend may mitigate the errors in signal values when INTRI calibrates target RSSI using fingerprints, which is may be more robust under large signal noise, for example at an airport.

FIG. 13 shows the localization error with and without differentiating the contours using HKIA data. Considered were two scenarios using 5m (default) and 10m survey grid size. Without using contour weights, the number of signal contours were counted and implemented it into INTRI as the baseline case. As shown in FIG. 13, simple contour counting may not discriminate the dispersed nearest neighbors (RPs) with similar number of contours. In contrast, contour weight may discriminate the fingerprints by penalizing RPs with weak signals. Then the influence from the noise in the measurement was mitigated. Thus, shown is that using contour weights may achieve better performance than the unweighted scheme, especially under sparser survey grid size. In Figure 8, plotted were the mean localization errors of these algorithms against the number of APs used. Randomly selected parts of the APs were detected at a target side to simulate the miss of the RSSI due to crowds of people or site construction change, which generally exists at an airport. As the number of APs used decreases, the performance of all five algorithms may degrade. Accordingly, INTRI is less susceptible to a AP number change than the other four algorithms. This is mainly because the junction of contours can constrain the target in a small region and reduce the dispersed set of nearest neighbors.

FIG. 14 shows the mean localization errors against the survey grid size. As the minimum grid size is five meters, columns or rows of RPs are removed to form the grid sizes with multiples of five. Clearly all five algorithms degrade as grid size increases. One can observe that EZPerfect achieves slightly higher accuracy than WKNN, KL-divergence and Horus under larger grid size. This is because for EZPerfect additional distances from multiple APs constrain the target location and prevent large error. Compared with the algorithms above, INTRI has much higher localization accuracy at different grid sizes. This is because INTRI considers signal uncertainty in contours and constrains the target estimation through joint optimization. Without relying on accurate distance measurement, INTRI may still constrain the target estimation by signal contours under large grid size.

FIG. 15 the cumulative errors of INTRI with the four other algorithms in the HKIA. Due to large measurement noise in the airport, WKNN’s accuracy is weakened by the dispersed nearest neighbors. Horus assumes a certain distribution of signal level at each RP and therefore cannot represent real signal distribution under limited sampling. KL-divergence  also requires large data sampling and dense fingerprints in signal distribution comparison. Therefore, it cannot adapt to the noisy airport environment. The large signal noise also degrades the distance accuracy of traditional trilateration in EZPerfect. In contrast to the above methods, INTRI jointly considers the signal noise and distances to contours, and therefore reduces the misestimation of the target.

FIGs. 16 and 17 show the cumulative errors in HKUST and HKCP respectively. Compared with the HKIA, the fingerprints and target signals in HKUST and HKCP carry less signal measurement noise. Thus, one can observe the increase of localization accuracy in all the algorithms compared with that in the airport. EZPerfect becomes slightly better than WKNN as the distance measurement becomes less noisy. Similar to FIG. 16, INTRI achieves higher accuracy than other algorithms since it considers the signal variation in constructing contours and utilizes them to reduce the dispersed nearest neighbors. Accordingly, INTRI may be general enough to work under different environments with higher accuracy.

2.3 Forming Contours for Random Signals in INTRI

Table 1: Major symbols used in INTRI formulation.

In this section, described us how to properly form the signal contours for later localization estimation (Section 2.4) . In Section 2.3.1, first presented is how to find the signal contour for each AP, given target random RSSIs. A contour (of an AP) consists of discrete RPs whose signal level is the same as the target’s measured signal level, subject to statistical fluctuation. To achieve higher localization accuracy, the RPs visited by many contours of strong signals are preferred. Therefore, in Section 2.3.2 proposed is a weighting scheme which is able to differentiate the importance of the RPs. The significant RPs are kept while the less significant ones (an unlikely target location) are filtered. After the above steps, given that the target is likely to be in the “dense” region of selected RPs, finally presented in Section 2. 3. 3 is how to located such a region based on maximally connected components.

2.3.1 Finding a Signal Contour

By evaluating the signal map of each given AP within the survey site, one may observe a set of RPs which share similar RSSI values subject to some statistical fluctuation. These RPs forms the signal contour for that AP. Then a target measuring a similar RSSI value is likely within a certain range from that contour. And the juncture of contours from these detected APs becomes the potential location of the target. Inspired by the above observations, the following presents a technique to form the signal contours given fingerprints and target signals.

Let N and L be the total number of RPs and distinct APs detected in the whole survey site, respectively. Further let 

 be the random variable of the RSSI collected at RP n for AP l in the offline fingerprint collection, where 1≤n≤N and 1≤l≤L. Multiple samples are collected at different time τ indexed 1, 2, …, 

 for RP n and AP l, which are denoted as

where 

 is the total number of samples collected. The unbiased estimate of 

 denoted as 

 is the mean of 

 ’ s. The unbiased estimate on the variance of 

 is denoted as 

 Then 

 and 

 are respectively given by

Let 

 be the mean of the measured fingerprint signals (a random variable) at RP n for AP l, given by

where 

 ’s are random variables distributed as 

 and 

 ’s are their realized values. Let v (τ) be a noise process independent from 

 Let 

 be a parameter determining the autocorrelation of samples. Then the signal time series can be represented as a first order autoregressive model,

where 

 represents the correlation between successive samples 

 For 

 its expected value 

 and standard deviation 

 can be estimated as

respectively. Here 

 can be approximated by autocorrelation coefficient with lag one for the RSSI samples in Equation (3) , i.e.

Such autocorrelation within sequential RSSIs is related to the caching in Wi-Fi sampling. Such data caching can be identified using Timing Synchronization Function (TSF) of the RSSI. Accordingly, one can conclude that an RSSI is a cached one if its TSF is identical to another in an earlier scan result.

To illustrate that, we collect 21,000 signal vectors at 350 different locations in the HKIA. At each location 60 RSSI samples were collected. For each AP l at an RP n, the 

 using Equation (8) was calculated. FIG. 19 shows the histograms of all 

 before and after cache filtering. Accordingly, one can see that the autocorrelation between RSSI samples decreases if we filter the cache based on TSF.

Given low signal correlation, one can assume independence between RSSI samples and further simplify the modeling of 

 into

However, TSF of RSSI cache is not available on all smartphones. Therefore, here we implement Equations (7) and (8) to calculate 

 for more general cases. Given the above, let

be the RSSI vector (fingerprint) at RP n.

In the online query stage, denote the target measurement of AP l as g^l. We denote the RSSI vector at the target as

g＝[g¹, g², …, g^L] .             (11)

For Equations (10) and (11) , by definition, 

 (g^l＝0) , if AP l is not sampled at RP n (at the target) .

As online g^l is also random signal, we utilize the uncertainty in offline fingerprint to characterize its variation. Specifically, let (σ^l) ² be its variance, estimated as the mean of the variance in all the fingerprints, i.e.,

where N^l is the set of RPs detecting AP l in the site and |N^l| is its cardinality.

Considered is the randomness in the difference between fingerprint and target RSSI, 

 for each AP l. As g^l and 

 are independently measured, the variance of 

 is therefore given by

A signal contour for AP l, denoted as S^l, consists of a set of RPs where the target is likely within. In other words, S^l represents the RPs whose RSSI for AP l is likely within a certain range from g^l. Therefore, in finding the contour S^l, one can eliminate the RPs whose RSSI is more likely far away from the target’s, i.e., if

where z₀ represents the uncertainty range. z₀ determines the sensitivity of INTRI towards the signal noise (in our experiment we will further evaluate this parameter) . Hence the signal contour for AP l may be found as follows. Given a target RSSI g^l, utilize Equations (13) and (14) , and form the signal contour S^l consisting of RP n∈N^l such that

Given AP l, denote the corresponding index set of RPs on contour S^l as C^l, i.e.,

Accordingly, its cardinality can be denoted as |C^l|.

2.3.2 Calculation of Contour Weights

Given the found contours, an intuitive idea is to locate the target at RPs with maximum number of contours. However, due to the indoor partitions and signal measurement uncertainty, spatially dispersed RPs may have very similar number of signal contours passing by. In this case, finding the RPs with the largest number of contours may not lead to accurate location estimation. As shown in FIG. 20, a target (red diamond) measures a signal vector consisting of RSSIs from six APs, A, B, C, D, E and F. The contours of D, E and F (black circles) shift from those of A, B and C (red rectangles) due to signal fluctuation or wall partitions. Thus, the RPs in black circles may share the same number of contours as those close to target. If all these RPs are considered equally without sufficient filtering or differentiation, large location errors still exist.

Through empirical studies, one can observe that the strong signals near APs provide more reliable location-dependent information than the weak ones. The stronger the RSSI, the more important the AP contour is in contributing to location estimation. This is due to the sharpness of signal strength change at the locations near the Wi-Fi APs, which differentiates RPs the most from other distant ones. In the following, how to utilize such distinguishable RSSIs to improve location accuracy is considered.

Take FIG. 20 again as an illustration. The signals at contours of A, B and C are stronger since they are closer to the corresponding APs. If more weight is assigned to the contours with strong signals in a final location decision, one can distinguish the important RPs more accurately. Thus, proposed is a weighting scheme which differentiates RPs the most and finds the RPs with higher confidence. The physical intuition of the weighting scheme is based on the log-distance path loss (LDPL) model. This technique is adopted in the  weighting function for signal contour differentiation, which may achieve high localization accuracy.

Denote the reference power at distance d₀ as 

 (dBm) . Let d_l be the distance between target and AP l. Then the received power at target from AP l is given by

where γ^l denotes the decay rate of RSSI in propagation. X represents the inherent signal fluctuation and noise. Here using LDPL to represent the closeness of APs for contour differentiation (not exact distance) is considered, and X has been considered separately in forming contours (Section 2.3.1). Based on Equation (17) , the corresponding pseudo distance from AP l (d₀＝1 m) is defined as

Instead of indicating actual distances, it may be used to represent the confidence level with AP signals. In other words, the smaller 

 the more likely the AP is nearby. Then the contour weight at RP n from all detected APs is defined as

Using Equation (20) , for each g^l at contour S^l, considered is the potential that an AP is physically nearby. The larger D_n, the more contours of strong signals hit the RP. Such APs are more likely to be close to these RPs around the target, and such closeness information may be utilized to constrain the target region.

Then the RP set R consisting of the indices of RPs which have the highest contour weights as the potential area for final estimation may be found, i.e.,

In INTRI, the RPs with D_n higher than ρmax {D_n} (ρ＝0.75 in our simulation and experiment) may be dynamically selected. RSSIs from an AP that is located in a region surrounded by obstacles may lead to larger γ^l than those from other APs with freer signal propagation. Here an ideal line-of-sight measurement is not assumed. The external parameters (

 and γ^l) in Equations (17) and (18) can be learned through gradient decent analysis over the fingerprint signals.

To summarize, by traversing the survey site, the signal contours at each RP within the signal range in Equation (15) may be found and the contour weights at that RP using Equations (18) and (19) may be calculated. The most important RPs with strong signals will be selected to form R.

2.3.3 Finding the Dense Contour Region

The selected RPs in R may still have “strayed RPs” due to measurement uncertainty. In FIG. 21, the spatial distribution of R (red rectangles) is illustrated. We can find RPs which are physically close to each other. These RPs form a region where the target is likely located, and may be used in they localization formulation. Due to signal temporal fluctuation, some RPs (the two to the right) exist and are distant away from the target location. If included in localization, these RPs may lead to location error and unnecessary computation. Considering their spatial connectivity, one may be observe in FIG. 21 that the RPs near the target (red diamond) form a connected component with the largest cardinality.

Based on such observation, an algorithm may be used to find the maximally connected components, and to find the region with dense contours by filtering out RPs not in the region.

Let N^R be the cardinality of R. An N^R×N^R adjacency matrix A may be constructed, where A (i, j) ＝1 indicates that RP i and j are adjacent, and A (i, j) ＝0. The threshold of adjacency may be set as 

 times of the square grid width in site survey. By treating RPs in R as an undirected graph, one can find the membership list of all connected components. After that, the component with the maximum number of RPs may be found. If multiple components have the maximum cardinality in common, their union may be used for later localization.

In FIG. 22, the histograms of N^R from 1,100 plots targets in the Hong Kong International Airport before and after the proposed RP filtering. As shown, it may be observed that such a scheme narrows the search scope and facilitates the final location estimation.

2.4 Linear Programming for Location Estimation in INTRI

In this section, presented is the formulation of INTRI. To formulate the objective function, defined in Section 2.4.1 is the physical (geographical) distance from an RP to signal contours. Then in Section 2.4.2, a linear programming is formulated based on  weighted physical distances to those contours. Finally the online computational complexity of INTRI is analyzed in Section 2.4.3.

2.4.1 Defining Distances from an RP to Signal Contours

Given a set of RPs where for located contours. In the following, how to utilize the signal contours as the objective for indoor trilateration is described.

Recall that traditional trilateration estimates target position by minimizing the difference between the measured distances and the distances from the position to the landmarks. In this formulation, based on the same spirit, the distances to the constructed signal contours is used. As RPs on contours are discretely sampled in the survey site and a target is surrounded by RPs, utilize in the formulation is the distances from RPs in R to those on other contours. Accordingly, the RPs with small distances to other S^l’s are likely to be the target region.

Let r_n＝ [x_n, y_n] be the coordinate of RP n∈R. Its distance from each RP m (n≠m) in S^l is calculated, i.e.,

where 

 is RP m’s coordinate on signal contour l. Given all distances 

 the minimum is found, i.e.,

which represents the distance between RP n and contour l. Given above, the distances to all contours are aggregated as

which, in other words, approximates the residual between the target estimation’s distances to the landmarks and the measured distances.

By minimizing Equation (23) , one may minimize the distance difference and hence extend the idea of trilateration. As the contours are derived from fingerprints and target RSSIs, no explicit knowledge of AP locations or LoS measurement is required, and therefore, the advantages of both fingerprinting and trilateration is combined in our formulation.

2.4.2 Linear Programming Formulation

Given R and Δ_n, one may formulate the localization problem based on linear programming (LP) . For each target, denote its estimated location as 

 Let ω_n be the weight assigned to r_n in locating the target. As the target is surrounded by the RPs in R, its estimated position can be expressed as

where r_n∈R, and the weights satisfy the normalization and non-negativity, i.e.,

Based on Equation (22) and (24) , one may extend the idea of trilateration into finding the weights which minimize the target’s weighted sum of distances to all the contours, i.e.,

In real deployment, a target is far more likely to be between two neighboring RPs (or within the square grid formed by four RPs) . In order to jointly consider the neighboring RPs to the target, one may set a constraint over the weight ω_n at each RP, i.e.,

where W is a dynamic parameter determined by the maximum contour weight

Through Equations (26) and (27) , one can jointly consider the physical distances (denoted as {Δ_n} ) and the contour weights (denoted as {D_n} ) in our formulation.

If there are indoor wall partitions in narrow space, one can consider the map constraints in our basic formulation. Denote the set of map constraints as E. For each edge e∈E, the accessible area within the map constraints is considered as

where a_e, b_e and c_e are the line parameters obtained from the site map in our system initialization. The formula of map edges can be easily found using the nearest map constraints. Using the above, the localization problem can therefore be formulated as a linear programming (LP) :

Objective: Equation (26)

subject to: Constraints (24) , (25) , (27) , (28) and (29)           (30)

In other words, one may opt to find the estimated position with the smallest weighted physical distances to the contours within the accessible area. INTRI returns the set of weights assigned to RPs in R which minimizes the distances to contours, i.e., the RPs which are closer to all contours are assigned higher weights, and vice versa.

Using some commercial optimization solver, we can solve the above LP efficiently. The final solution {ω_n} is then used to estimate the target position according to Equation (24) .

2.4.3 Complexity Analysis

In view of the above, the computational complexity of INTRI may be analyzed as follows:

1. Forming contours with random signals: Given N RPs and L APs, the complexity of finding signal contours and calculating contour weights is given by 

 (Section 2.3.1 and 2.3.2) .

2. Finding maximally connected components: Given N^R selected RPs, finding the maximally connected component takes 

 (Section 2.3.3) .

3. LP-based localization: To prepare the objective function of LP, calculating the distances between R and contours takes 

 (Section 4.1) . In Formulation (30) , there are 

 decision variables in {ω_n} . Thus, the LP in location estimation takes weak polynomial time, i.e., 

 (Section 2.4.2) .

To summarize, the overall running time of INTRI is

After contour differentiation and finding maximally connected components, N^R＜＜N. Further computation reduction can be done via AP filtering and RP cluster mapping. The number of APs and RPs may then be significantly reduced. In this way, INTRI can be integrated on existing on-board LBS systems and can further supports mobile targets.

2.5 Efficient Online Calibration for Heterogeneous Devices

Due to difference in Wi-Fi network interfaces, the same signal may have different measurement values based on the device. To illustrate this, an experiment was  conducted that collected 1,000 RSSI samples. If such signal difference issue were not addressed, the contours (Section 2.3.1) may not be correctly found. FIG. 23 shows the similarity of signal trend between signals of the two smartphones despite the shift. Leveraging such similarity, presented is an efficient algorithm to adapt to different mobile devices.

In this section, considered is an efficient and scalable online calibration in order to reduce offline manual efforts. To this end, the target signals g were mapped to the signal space in fingerprint database. The correlation between the target RSSI vector and that of each RP may be calculated. The RPs with similar signal vectors can be leveraged for online signal calibration. The vector comparison is based on the correlation between g and fingerprint f_n, i.e.,

where 

 and 

 The above correlation compares relative signal trend of different APs rather than the absolute RSSI values. Based on Equation (32) , one can find the RPs with similar signal trend for calibration and reduce the effect of device dependency.

To mitigate the effect of random noise, one can find the top several RPs with corr (g, f_n) >η (η＝0.95 in our experiment) for linear calibration. For each target RSSI g^l from AP l, one can find the corresponding 

 at RPs. Given pairs of 

 one can conduct the linear regression and obtain the corresponding a and b for target RSSI g^l, i.e.,

Note that our online calibration approach is not restricted to linear model, and is general enough to apply to any other signal mapping model. Based on Equation (33) INTRI with calibrated 

 may be conducted. Given 

 APs and 

 RPs, the correlation comparison takes 

 Let λ (λ＜＜N) be the number of RPs whose correlation is greater than η, and linear regression takes 

 Therefore, the online computational complexity of 2-D linear regression is 

FIG. 24 shows a process 900 associated with the trilateration using signal contours technique, in accordance with various embodiments. In 910, a computing system (e.g. computing system 1900 as shown in FIG. 43) may identify wireless AP devices (e.g. AP 104a-d as shown in FIG. 1) within an area. As described above, AP devices may be identified using any suitable identifier such as a device ID. In 920, the computing system may determine an RSSI of a device to be located (e.g. device 102 as shown in FIG. 1) . In 930, the computing system may determine, for each respective wireless access point device of the wireless access point devices, respective reference point devices (e.g. RPs 110 as shown in FIG. 1) each having a respective RSSI, with respect to the respective wireless access point device, that is similar to the RSSI of the device. Determining the respective reference point devices may include retrieving the respective RSSI of each of the respective reference point devices from a location fingerprint data store. In addition, determining the respective reference point devices may include determining that the respective RSSI of each of the respective reference point devices is within a statistical tolerance of the RSSI of the device. Moreover, a weighting technique may also be deployed. For example, determining the respective reference point devices may include filtering the respective reference point devices based on a respective weighting associated with each of the respective reference point devices. In addition, the respective weighting associated with each of the respective reference point devices may be based on the respective RSSI of each of the respective reference point devices. In 940, the computing system may determine, for each respective wireless access point device of the wireless access point devices, respective contour data representing a respective contour that maps distances of the respective reference point devices from the respective wireless access point device. In 950, the computing device may determine a location of the device based on a juncture determined from the respective contour data of the respective wireless access point devices as described in the above sections. In addition, the computing device may calibrate the RSSI of the device based on identifying the type of device.

Accordingly, as described above, INTRI may be employed as a more effective technique at addressing random signals (due to signal noise and measurement uncertainty) for indoor localization than conventional methods.

3. FUSING NOISY FINGERPRINTS WITH DISTANCE BOUNDS TECHNIQUE ( “Wi-Dist” )

As described above, due to random signal fluctuations, wireless fingerprints are inherently noisy and distances may not always be accurately measured. Accordingly,  proposed is Wi-Dist (fusing noisy wireless fingerprints with uncertain mutual distances) . Wi-Dist is a generic framework applicable to a wide range of sensors (peer-assisted, INS, etc. ) and wireless fingerprints (Wi-Fi, RFID, CSI, etc. ) . Wi-Dist may achieve a lower rate of errors through the use of a convex-optimization formulation which jointly considers distance bounds and, for example, the first two moments of measured fingerprint signals. As described above, error in location estimation is inevitable. This is due to random signal fluctuation in both offline and online measurements. As targets are often considered independently in traditional approaches, such measurement noise or uncertainty may lead to a disperse set of spatially distant neighbors, which greatly degrades the localization accuracy. In order to reduce the estimation errors, one may incorporate, or fuse, wireless fingerprinting with mutual distance information. Embedding such information into the fingerprints can significantly reduce the dispersion, leading to substantial enhancement in localization accuracy.

The distance information used in the technique may be spatial, where the target estimates the distances to some of the nodes or beaconing devices in its neighborhood using, for example, Bluetooth^TM, Wi-Fi direct, ultrasound, etc. Although there have been previous works using spatial distances for localization, they often assume accurate distance measurements, resulting in rigid constraints over the fingerprints. The rigidity of these previous works, however, cannot usually be extended to the more realistic scenarios when distance measurement is often uncertain with given upper and lower bounds.

The distance information used in the technique may also be temporal, where the target estimates its displacement over consecutive time intervals (e.g., by step counter or inertial navigation system (INS) provided in one’s mobile phone) . Although there have been previous fusion works in the area, they are often based on a Bayesian approach that assumes some probability distribution in sensor measurements. In reality, however, such probability distributions are often not known. Furthermore, these works cannot be easily extended to the case of noisy sensor measurement over multiple periods of time.

Accordingly, as further described herein, Wi-Dist jointly considers distance bounds and noisy fingerprints to reduce indoor localization errors. Wi-Dist may require only the first two moments (mean and variance) of the fingerprint RSSI signals and may optimize locations based on a Semi-Definite Programming (SDP) . Using such a SDP relaxation, Wi-Dist solves the localization problem achieving improved accuracy.

For an example practical deployment of Wi-Dist, the following contributions are noted:

Bound-based Distance and Uncertainty in Signals: In contrast to the rigidity constraints or Bayesian approaches in previous works, Wi-Dist does not necessarily require overly accurate distance measurements or knowledge of distance probability distributions. It may account for target measurement noise by taking, for example, only the upper and the lower bounds of distance as input. As opposed to some works where distance must be symmetric, Wi-Dist is applicable in stances where distance may be asymmetric (in which case the upper bounds can be obtained by using the larger value of the two directions, and vice versa) . Furthermore, Wi-Dist also considers fingerprint RSSI signals to be random with a mean and variance. Such consideration of random signal noise and measurement uncertainties contributes to its improved accuracy.

Convex Optimization Formulation: Because Wi-Dist may take as input, for example, only the upper and lower bounds of distances, it is not based on rigidity constraints or Bayesian approach, and hence does not necessarily require accurate distance measurement or knowledge of probability distributions. Using the bounds as constraints, Wi-Dist may estimate the location by maximizing the overall similarity with a fingerprint map including random signals. Accordingly, it is applicable to scenarios where distances may be asymmetric, in which case the upper (or lower) bounds can be obtained by using the larger (or smaller) value of the two directions.

Generic Framework: Wi-Dist is a generic framework applicable to a wide range of sensing techniques, enabling indoor localization with adaptive spatial and temporal mobile sensing independent of how distance is measured. For example, it may employ peer-to-peer spatial distances in the crowded region. For an unpopulated area, it may then switch to dead reckoning (INS) for distance measurement. Although the discussion described herein relates to Wi-Fi fingerprints (due to its ease of deployment without extra infrastructure beyond the existing Wi-Fi one) , Wi-Dist is general enough to be extended to other wireless fingerprint signals such as RFID or channel state information (CSI) .

As described herein, Wi-Dist has been implemented in a simulation for experiments in an international airport and a university campus. These simulations indicate that Wi-Dist may achieve better accuracy than other works (e.g. often by more than 40％) .

FIG. 25 shows an example diagram of a framework for fusing noisy fingerprints with distance bounds information. The fingerprint database (e.g. data store 108 as shown in FIG. 1) may be initialized by a site survey by storing location and Wi-Fi RSSI vector pairs of RPs (e.g. RPs 110 as shown in FIG. 1) . In addition to the RSSI vectors, a target device (e.g. device 102 as shown in FIG. 1) may measure the distance bounds information and report the information to a localization server (e.g. server 106) . Based on the  reporting and a difference metric for random Wi-Fi signals, the server may construct an SDP convex-optimization problem which leads to a more accurate localization of the target.

3.1.2 Related Work

Wi-Fi fingerprinting techniques have been widely studied in recent years. The work by Horus (see e.g., M. Youssef and A. Agrawala, “The Horus location determination system, ” Wireless Networks, vol. 14, no. 3, pp. 357–374, Jun. 2008) estimates the target location using a probabilistic model which reflects the signal distribution in the site. Expectation-maximization, compressive sensing and signal geometric patterns have been implemented for fingerprint-based indoor localization. The techniques above, however, only address Wi-Fi fingerprint issues. In contrast, Wi-Dist fuses distance information with fingerprints to achieve better accuracy.

Combining dead reckoning with fingerprints has been explored. These works assume that the walking path is conditionally independent. Therefore, the distance constraints over multiple temporal Wi-Fi estimations have not been jointly considered. Furthermore, these works often treat the outputs from dead reckoning and Wi-Fi fingerprint sequentially. Wi-Dist, on the other hand, formulates the localization problem as a single joint convex-optimization problem. This reduces the influence of measurement noise and achieves higher accuracy. For example, the work on Wi-Fi SLAM (see e.g., S. He and S.H. Chan, “Sectjunction: Wi-Fi indoor localization based on junction of signal sectors, ” in Proc. IEEE ICC, June 2014, pp. 2605–2610) implements robot odometer to determine the distance accurately. In contrast, Wi-Dist considers a step counter whose measurements may be “noisy. ” 

Works have also considered the use of Wi-Fi direct and high-pitch sound to measure distances between devices. Some of these works consider using a rigid graph constructed through rotation and translation, while others consider using Bayesian approach to infer the device location. In contrast, Wi-Dist jointly considers distance bounds and fingerprint noise, and formulates an optimization problem to estimate the target location. Therefore, Wi-Dist may be a more versatile and realistic framework accommodating measurement noises.

Moreover, in contrast to the sensor fusion works described above, Wi-Dist is a seamless generic framework applicable to different sensor systems with temporal or spatial distance measurement and it may be extended to different application scenarios.

3.2.1 Illustrative Experiment

Wi-Dist was developed based on Wi-Fi fingerprints and experiments were conducted to study its performance. In this section, discussed first are the experimental settings and performance metrics in Section 3.2.1.1. Then illustrative experimental results are presented for dead reckoning and peer-assisted localization in Sections 3.2.1.2 and 3.2.1.3 respectively.

3.2.1.1 Experimental Settings and Performance Metrics

Wi-Dist was evaluated in the Hong Kong International Airport (HKIA) boarding area and HKUST campus atrium. In the airport, overall 1,400 RPs in 8,000 m² area were collected. On the campus 394 RPs in 5,000 m² area were collected. FIG. 26A and FIG. 26B show their corresponding floor plans.

In the airport and the campus, overall 80 Wi-Fi samples at each RP were taken. A quarter of these samples were collected facing north, south, west and east respectively. For all the application scenarios, the following parameters were used as baseline: 5m survey grid size； 1 Wi-Fi RSSI sample is used for each target； no Wi-Fi AP reduction is conducted over target RSSI vectors.

Wi-Dist was compared with the following typical localization schemes in the experiments:

Fingerprint-based localization (FL) , the classical algorithm which evaluates the Euclidean distance of target RSSI vector with each RP fingerprint and finds the interpolation of top k nearest neighbors for location estimation (k＝15 in our experiment) .

Sequential Monte Carlo (SMC) localization, a typical fusion algorithm based on Sequential Monte Carlo method (particle filter) which fuses INS data and Wi-Fi fingerprinting (FL) . Through the propagation along the temporal walking path, the particles translate from one location to the next. With map constraints, the spatial distribution of these particles gets corrected and resampled. The final estimation is based on the weighted average of particle locations.

Graph-based and fingerprint localization scheme (GB + FL) , which uses graph construction and Wi-Fi fingerprinting for peer-assisted localization. With the pairwise spatial distances of peer targets, the server constructs the rigid graph consisting of all targets. Then the system searches against the Wi-Fi signal map and finds a set of fingerprints to minimize the objective function 

 through rotation and translation.

Let x_m be target m’s true location and 

 be the estimated location. The performance metric in the experiment was the mean error (unit: m) of the estimated target in set V:

3.2.1.2 Dead Reckoning

In this section how Wi-Dist performs for a mobile user with INS (step counter) in his smartphone was studied.

Temporal walking distance of the target is estimated from the INS sensor which counts the steps of a walking target. Each step detection is based on the periodic changes in the vertical direction of the accelerometer readings. Based on the number of steps, the distance travelled, or motion offset, can be estimated by multiplying the average stride length of the target (which is related to walking frequency) .

As the target walks, the device also collects the Wi-Fi RSSI vectors. Using the notation in Equation (11) the index m here represents the time stamp. Each target location 

 now corresponds to a temporal measurement of a single target. The most recent M temporal targets and M-1 distances between them form a sliding window in time domain, and the estimation of the M-th target is returned as the current position.

With the fast Wi-Fi scanning on smartphone devices, the small curvature between two consecutive Wi-Fi samples can be approximated as distance. Let β be the range of confidence interval for estimating the displacement and σ_mn be the statistical standard deviation based on experimental results. Given a distance measurement 

 at time m from the last location with RSSI measurement (L_m＝ [m-1] ) , each of the distance bounds in W_m is defined as

Based on Equation (11) , a Wi-Fi temporal target P_m at time m is defined as

The distance bound for initial or the first target in the sliding window is defined to be null. Based on the empirical test, β is set to 2 in Equation (2) . The size of sliding window M is 7. 200 particles are used in the particle filter of SMC algorithm.

FIG. 27 plots the localization accuracy with respect to time for Wi-Dist and SMC. The estimation error fluctuates as the user walks in the airport. Changes in wall partitions, crowded people, user walking direction and smartphone holding gesture introduce measurement noise in Wi-Fi and INS signals. SMC sequentially considers the fingerprints and INS measurements. SMC does not jointly consider the Wi-Fi fingerprints and the distances from the multiple time periods. Therefore, large error in location estimation may occur. In contrast, Wi-Dist may constrain its estimations through the distance bounds in a joint optimization formulation. Therefore, Wi-Dist may achieve lower localization errors and smaller estimation fluctuation.

FIG. 28 shows the mean displacement measurement and corresponding standard deviation at each true walking distance. In the empirical studies, the major error of displacement comes from misestimation in step counts and step length. Meanwhile the device initialization and walking curvature also leads to additional displacement errors. Based on such empirical analysis, one may obtain the displacement variance for each measured distance, which constitutes the distance bounds (Equation (2) ) in Wi-Dist temporal measurement.

FIG. 29 shows the mean localization errors against the number of Wi-Fi temporal target measurements. As may be observed, the accuracy improves as more temporal samples are used. This is because joint consideration of more periods further constrains the location estimations. When the number of measurements is further increased, the accuracy gradually converges, indicating that distance bounds already provide sufficient constraints. Thus, to balance between localization accuracy and computational complexity several temporal measurements (like 7 in our experiment) in Wi-Dist were chosen.

3.2.1.3 Peer-Assisted Localization

For some areas visited by many users, peer-assisted (PA) localization may be used. Peer ranging can be based on either RSS-distance mapping or sound ranging. In the experiment, implemented and tested were sounds ranging under quiet and noisy campus environment. The mean peer ranging errors under these two conditions are 0.8m and 2m respectively. Since distance constraint between two peers is asymmetric due to measurement uncertainty, the larger value in the distance measurements as the upper bound 

 and the smaller one as the lower bound 

 may be used. In the peer-assisted localization, 5 targets are involved in sound-based distance measurement. The cases in which the walls may partition peers during localization were not excluded.

FIG. 30 shows the mean localization errors against the proportion of APs removed at targets. Some received APs of each target were randomly removed to evaluate the influence of AP reduction due to wall partitioning or crowds of people. As shown, Wi-Dist and GB+FL marginally rely on the number of received APs. This is because the multiple users’ Wi-Fi samples reduce the effect of sparse AP deployment. To the contrary, FL relies on the APs to differentiate the RPs and therefore its estimation error increases as more APs are pruned.

FIG. 31 shows that the location estimation errors against the number of Wi-Fi samples at each target in PA localization. All the algorithms improve with more Wi-Fi samples. This is because as the number of Wi-Fi samples increases, noise from the random sampling can be reduced. Compared with GB+FL and FL, Wi-Dist achieves higher localization accuracy because it further jointly considers the measurement noise in the optimization formulation and reduces the uncertainty. However, increasing the number of Wi-Fi samples means that one may need to wait for more samples before final estimation. Accordingly, a balance may be made between accuracy and latency depending on application scenarios.

FIG. 32 shows the location errors against the survey grid size. As the minimum grid size is five meters, lines or rows of RPs are removed to form grid size with multiples of five. As shown, when the grid size increases, the accuracy of the three algorithms decreases. Though less labor-intensive, larger survey grid size may more easily lead to dispersed nearest neighbors under large signal noise. Therefore, traditional algorithms like FL may not accurately differentiate these RPs. Under different survey density, Wi-Dist and GB+FL achieve more accurate location estimations with the constraints of peer-to-peer distances. However, the rigid graphs of targets in GB+FL still suffers from pairwise distance measurement noise. By fusing signal uncertainty and distance bounds, Wi-Dist achieves higher estimation accuracy under different grid sizes.

FIG. 33 and FIG. 34 show the overall performance of Wi-Dist at different scenarios (INS and PA at baseline parameters) in HKIA. Large indoor open space often leads to high uncertainty in Wi-Fi signals and disperse nearest neighbors in signal space. Furthermore, the temporal and spatial distance measurement also contains large noise under the crowded scenarios. Compared with other state-of-the-art algorithms, Wi-Dist significantly reduces the estimation errors in HKIA. With distance constraints and joint optimization, Wi-Dist mitigates the effect of disperse nearest neighbors.

Compared with the airport, the campus atrium is smaller with more building partitions, which may influence the peer-distance measurement accuracy. Performances of  Wi-Dist (INS and PA) on HKUST campus are shown in Figure FIG. 35 and FIG. 36 respectively. Wi-Dist may achieve a higher localization accuracy than the other methods. As the results in HKUST are qualitatively similar to those in HKIA, for brevity the experimental results are not repeated herein.

3.2.2 Simulation

To evaluate more comprehensively the performance of Wi-Dist in large-scale indoor environment with many users, Wi-Dist was simulated for the scenarios as mentioned in Section 3.2. In this section, discussed first is the simulation setup (Section 3.2.2.1) , followed by the results for dead reckoning and peer-assisted localization (Sections 3.2.2.2 and 3.2.2.3) .

3.2.2.1 Simulation Setup

Wi-Fi signal strength was simulated. In the signal model, the RSSI Φ (dBm) from Wi-Fi AP at a distance D can be simulated as

where measurement noise is distributed as 

 Unless otherwise stated, one may use the following as our baseline parameters: the transmission power Φ^TX＝25 dBm, the path loss exponent α＝4.0, reference path loss L⁰＝37.7 dB, reference distance D⁰＝1 m, 200 m × 80 m survey site with 5 m grid size； Wi-Fi signal noise σ_db＝6 dB； 10 APs are uniformly distributed in the survey area； a target takes a Wi-Fi sample every 3 seconds.

3.2.2.2 Dead Reckoning

For dead reckoning, random way-point mobility model with resting was used, and the 7 most recent Wi-Fi records were used for INS fusion. The step count error rate was distributed as 

 where σ_r＝20％, and the stride length error follows 

 where σ_l＝0.2 m. Additional walking displacement error was assumed to follow 

 where σ_w＝2 m.

FIG. 37 shows the localization accuracy against the step count errors. Clearly, the performance of SMC and Wi-Dist degrades with larger step count error. SMC locates the user based on the particle filter, which sequentially considers the Wi-Fi and INS  measurements. Therefore, when step count accuracy degrades, the displacement error increases and the particles become spatially sparse, making it difficult for SMC to converge to correct locations. To the contrary, Wi-Dist localizes the target more accurately because the joint consideration of Wi-Fi fingerprints and distance bounds of multiple periods reduces the influence of measurement uncertainty.

FIG. 38 shows the localization accuracy against the walking displacement errors. We can see that as the displacement error increases, the overall location accuracy decreases. Localization error in SMC increases because the particles converge slowly given large distance errors and noisy Wi-Fi measurement. Different from SMC, Wi-Dist achieves more accurate results because it utilizes the distance bounds instead of actual distance measurement. By constraining the target estimation within the intersection of these bounds, Wi-Dist may be more robust to distance uncertainty.

FIG. 39 plots the localization errors versus the signal noise in Wi-Fi measurement (Equation (4) ) . As shown, the performance of both SMC and Wi-Dist degrades when the random signal noise increases. This is because larger signal noise makes it more difficult to differentiate the fingerprints. Different from SMC, Wi-Dist considers signal uncertainty through the expected signal difference. By minimizing the signal difference within constraints of distance bounds, Wi-Dist reduces the effect of disperse nearest neighbors and obtains better estimation results.

3.2.2.3 Peer-Assisted Localization

Assumed is a noisy peer-assisted distance error 

 σ_m ＝ 3.5 m； neighborhood detection range is 15 m； four peers together initiate a peer-assisted localization； and 90 users are randomly distributed in the survey site.

FIG. 40 shows the localization errors versus the number of users. As shown, more peer assistance provides more distance constraints over the involved users and improves the localization accuracy. Different from GB+FL, Wi-Dist shows less dependency on user connectivity. This is because Wi-Dist considers the measurement uncertainty in the optimization and jointly constrains all the users. Therefore, it does not have to involve many users to achieve high localization accuracy.

FIG. 41 shows the localization accuracy against the peer distance errors. Gaussian noise is added to the inter-device distance measurement as an assumption. When the peer distance error is small, both algorithms achieve high accuracy given only Wi-Fi measurement noise in fingerprints. As distance error further increases, both algorithms  degrade in localization accuracy. GB+FL constructs a rigid graph to constrain relative positions of different users. However, the graph shape deforms under large distance measurement errors. Wi-Dist, in contrast, shows more robustness by using joint optimization based on fingerprints and distance bounds. Without assuming a rigid graph, Wi-Dist can achieve more robust localization estimation.

3.3 Problem Formulation and Complexity

Table 1: Major symbols in the problem formulation.

3.3.1 Preliminaries

In an offline mode, a site survey is conducted with a total of Q reference points (RPs) . Let r_q be the 2-D position of RP q, and R be a 2×Q matrix indicating the RP positions, i.e.,

R＝[r₁, r₂, …, r_Q] .            (5)

Let 

 be the index set of the Wi-Fi access points (APs) that cover the site, i.e., 

At each RP, time samples of Wi-Fi RSSI readings are collected. Due to the random nature of radio signals, multiple samples are collected in order to reduce the uncertainty in the signal measurements.

Denote the RSSI at RP q from AP l at time t as 

 with S being the total number of samples collected. Denote the average RSS readings from AP l, 

 at RP q as 

 and the unbiased estimate of the variance of the RSS time samples for AP l at RP q as 

 Then for each RP, the unbiased estimates for the mean RSSI and its corresponding standard deviation at RP q are computed as:

Then the Wi-Fi RSSI vector at r_q is

where, by definition, 

 if AP l is not detected at RP q.

In an online mode, let V be the set consisting of the indexes of the M target nodes (or simply targets) to be localized in the site, i.e., V＝ {1, 2, …, M} , and each of their 2-D locations to be estimated is denoted as 

 It should be noted that the targets to be estimated can be either spatial or temporal. Let X be an M×2 matrix of all these points, i.e.,

For each of the targets (spatial or temporal) , let 

 be the RSSI value at target location 

 for Wi-Fi AP l, 

 Similar to the RP RSSI vector, we define the target m’s sampled RSSI vector as

where, by definition, 

 if AP l is not detected at target m. Given a target m, let L_m be the set of its neighbors having a distance measurement. Let δ_mn be the distance (spatial or temporal) between targets 

 and 

 for any m, n∈V, i.e.,

Based on statistical analysis of distance (spatial or temporal) , one may obtain a distance bound with a high confidence level. Given the distance measurement interval, one may denote 

 as the lower bound of the measurement and 

 as the upper bound. For each Wi-Fi target, W_m stores the distance bounds, i.e., 

Given the M targets to be localized in V, each of them contains the following information in the Wi-Dist problem:

3.3.2 Problem Formulation

The RP positions R are used to estimate the location of the target. Let ω_mq be the weight assigned to RP q to locate m, so that

where the weights ω_mq, 

 satisfy

Let W be an M×Q matrix of ω_mq, r_q∈R, i.e.,

Then the positions of all the targets in V given W are given by

X＝WR^T,             (15)

The distance between two targets in Equation (10) satisfies bound constraints, i.e., 

 or equivalently, 

Given the above, one may present the following the objective function for Wi-Dist. First, a metric to evaluate the difference between the target Wi-Fi samples and the stored fingerprints under measurement noise may be introduced.

Accordingly, fingerprint noise at each RP may be considered. Define J_mq as the shared APs between Wi-Fi measurement point m and RP q (0<|J_mq|≤L) . Given a target’s Wi-Fi RSSI 

 (constant) from AP l∈J_mq, the expected signal difference between RP q and the target m’s RSSI in AP l is derived as:

By definition, if either 

 or 

 (or both) , Δ_l (F_m, Y_q) ＝0. Thus, the total expected signal difference between the RP q and the target m’s RSSI vector is given by

If |J_mq|＝0 (e.g. no shared APs between the target m and RP q) , then by definition Γ (F_m, Y_q) ＝∞, i.e., RP q is essentially excluded from the later optimization formulation.

Using Equation (18) , one may present the following the objective function for Wi-Dist. To jointly measure the overall difference of all targets with the stored signal map, one may find the weights which minimize all the targets’ weighted sum of expected signal difference as:

which jointly considers the signal difference and the physical distance constraints.

To summarize, a matrix W may be created so as to satisfy

Objective: Equation (19)

subject to: Constraints (10) , (13) , (15) and (16) .          (20)

3.3.3 Problem Hardness

In this section, the problem given by Formulation (20) is presented and its hardness is studied. It should be noted that a relaxation to solve it by semi-definite programming is also described.

Formulation (20) can be generalized into the following problem:

Definition 1 Given the targets with RSSI measurements and the distance information between them, is there a set of locations in the fingerprint database such that the total difference between the measured RSSI vectors and the stored signal map is minimized while their relative locations satisfy the measured distance bounds？

To prove the hardness in Definition 1, the subset sum problem (SSP) is introduced, which may be stated as follows:

Definition 2 Given a set A of integer numbers and an integer number a, does there exist a subset of A such that the sum of its elements is equal to a？

In reality, solving the problem in Formulation (20) may be challenging. Accordingly, one may prove that it is computationally hard by using a reduction from subset sum problem (SSP) .

Theorem 1 There is no efficient algorithm that solves the problem given by Definition 1 unless P＝NP.

The proof may be briefly described as follows. Suppose a polynomial-time algorithm that takes as input the distances between different targets as well as fingerprint measurement points to recover their original positions. Therefore, one may minimize the overall sum of target signal differences with the fingerprint map to obtain the candidate locations, and then find among the candidate locations, the locations that satisfy the corresponding distance bounds.

Accordingly, an algorithm can be used to solve the SSP by applying it to an instance of the problem. After reaching its polynomial time bound, the algorithm will either have returned a solution or not. In the first case, one may check if the solution with pairwise distances returned is consistent with the distance bounds. Similarly, in the SSP one may check the sum of elements in polynomial time and accept if and only if the check succeeds. In the second case, the instance may be rejected. For both cases, the correct answer for SSP may be returned. Since SSP is already NP-hard, the problem is as hard as the SSP. Thus, the problem in Definition 1 is NP-hard.

3.4 Wi-Dist: SDP-based Location Optimization

As the Wi-Dist problem is NP-hard, Semi-Definite Programming (SDP) relaxation may be used for a solution.

Given the distance bounds, semi-definite relaxation to relax the distance constraints may be applied. Let e_mn be an M×1 column vector where the m-th element is 1 and n-th element is -1. The physical distance between node m and n can be therefore represented as

Denote an M×M matrix Y for internal transformation, i.e.,

Y＝XX^T.               (22)

Finally the distance bound can be rewritten as

Based on the distance bound constraints in Equation (23) , Formulation (20) may be rewritten into

Objective: Equation (19)

subject to: Constraints (13) , (15) , (22) and (23) .           (24)

As shown, Constraint (23) is nonconvex due to 

 Given a symmetric matrix A, let 

 represent that A is a positive semidefinite matrix. One can then relax this problem into a convex one by replacing the nonconvex equality constraint, Y-XX^T＝0 in Constraint (22) , with a convex positive semi-definite constraint, i.e.,

Constraint (25) is a nonlinear constraint, which can be further transformed into a linear matrix inequality. Then it can be solved efficiently by a convex optimization solver. The transformation is through a Schur complement:

Definition 3 Let H be a matrix partitioned in four blocks, consisting of four matrices B, E, C and D, i.e.,

where B and D are symmetric and nonsingular. The Schur complement of D in H, is defined as

S＝B-ED^-1C.               (27)

If 

 then 

 [6] . Thus, by using Schur complement, Constraint (25) may be rewritten as a matrix form, i.e.,

Then Formulation (24) may then be transformed into an SDP problem:

Objective: Equation (19)

subject to: Constraints (13) , (15) , (22) , (23) and (28) .      (29)

Accordingly, the formulation above may be directly applied in peer-assisted localization. For dead-reckoning based localization, m as the time stamp may be taken. Finally, the computational complexity of the solution may be analyzed. Given Q RPs and L APs, the complexity of signal difference calculation is 

 Given M temporal or spatial target measurements (usually M is small) , the computation of SDP relaxation is bounded by 

 Using some commercial SDP solver this problem can be solved efficiently. Further computational reduction can be achieved by AP filtering and RP cluster mapping.

FIG. 42 shows a process 1700 associated with the fusing noisy fingerprints with distance bounds technique, in accordance with various embodiments. In 1710, a computing system (e.g. server 106 as shown in FIG. 1) may populate a location fingerprint data store for reference point devices within an area within which a device is to be located based on time samples of received signal strength indicators at an access point device for the reference point devices. For example, populating the location fingerprint data store may include storing only a mean and a variance of the time samples of the received signal strength indicators for a respective reference point device. In 1720, the computing device may receive distance information for the device based on an RSSI vector of the device at the access point device. For example, the distance information may include distance information received at various time intervals. In another example, the distance information may include distance information for the device is based on determining a current estimated position of the device to a previously estimated position of the device.

In 1730, the computing device may determine an upper distance bound and a lower distance bound of a location of the device based on the distance information and the location information stored in the location fingerprint data store. In 1740, the computing device may determine a metric to evaluate a difference between the target signals and those stored in the location fingerprint data store. For example, determining the metric may include determining a fingerprint noise value for each of the reference point devices. In addition, determining the metric may also include determining a respective weight associated with each of the reference point devices. In 1750, the computing device may generate relaxation  data representing a semi-definite programming relaxation based on the metric using the upper distance bound and the lower distance bound of the location as constraints on the generating. Accordingly, in 1760, the device may be located based on the relaxation data.

For simplicity of explanation, the processes described herein are depicted and described as a series of acts. It is to be understood and appreciated that the subject innovation is not limited by the acts illustrated and/or by the order of acts. For example, acts can occur in various orders and/or concurrently, and with other acts not presented or described herein. Furthermore, not all illustrated acts may be required to implement the methodologies in accordance with the disclosed subject matter. In addition, those skilled in the art will understand and appreciate that the methodologies could alternatively be represented as a series of interrelated states via a state diagram or events. Additionally, it should be further appreciated that the methodologies disclosed hereinafter and throughout this specification are capable of being stored on an article of manufacture to facilitate transporting and transferring such methodologies to computers.

As it is employed in the subject specification, the term “processor” can refer to substantially any computing processing unit or device comprising, but not limited to, single or multi core processors, parallel platforms, an integrated circuit, an application specific integrated circuit (ASIC) , a digital signal processor (DSP) , a field programmable gate array (FPGA) , a programmable logic controller (PLC) , a complex programmable logic device (CPLD) , a discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions and/or processes described herein.

In order to provide a context for the various aspects of the disclosed subject matter, FIG. 43, and the following discussion, are intended to provide a brief, general description of a suitable environment in which the various aspects of the disclosed subject matter can be implemented, e.g., various processes described herein. While the subject matter has been described above in the general context of computer-executable instructions of a computer program that runs on a computer and/or computers, those skilled in the art will recognize that the subject innovation also can be implemented in combination with other program modules. Generally, program modules include routines, programs, components, data structures, etc. that perform particular tasks and/or implement particular abstract data types.

Moreover, those skilled in the art will appreciate that the inventive systems can be practiced with other computer system configurations, including single-processor or multiprocessor computer systems, mini-computing devices, mainframe computers, as well as  personal computers, hand-held computing devices (e.g., PDA, phone, watch) , microprocessor-based or programmable consumer or industrial electronics, and the like. The illustrated aspects can also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network； however, some if not all aspects of the subject disclosure can be practiced on stand-alone computers. In a distributed computing environment, program modules can be located in both local and remote memory storage devices.

With reference to FIG. 43, a block diagram of a computing system 1900 operable to execute the disclosed systems and methods is illustrated, in accordance with an embodiment. Computer 1912 includes a processing unit 1914, a system memory 1916, and a system bus 1918. System bus 1918 couples system components including, but not limited to, system memory 1916 to processing unit 1914. Processing unit 1914 can be any of various available processors. Dual microprocessors and other multiprocessor architectures also can be employed as processing unit 1914.

System bus 1918 can be any of several types of bus structure (s) including a memory bus or a memory controller, a peripheral bus or an external bus, and/or a local bus using any variety of available bus architectures including, but not limited to, Industrial Standard Architecture (ISA) , Micro-Channel Architecture (MSA) , Extended ISA (EISA) , Intelligent Drive Electronics (IDE) , VESA Local Bus (VLB) , Peripheral Component Interconnect (PCI) , Card Bus, Universal Serial Bus (USB) , Advanced Graphics Port (AGP) , Personal Computer Memory Card International Association bus (PCMCIA) , Firewire (IEEE 1194) , and Small Computer Systems Interface (SCSI) .

System memory 1916 includes volatile memory 1920 and nonvolatile memory 1922. A basic input/output system (BIOS) , containing routines to transfer information between elements within computer 1912, such as during start-up, can be stored in nonvolatile memory 1922. By way of illustration, and not limitation, nonvolatile memory 1922 can include ROM, PROM, EPROM, EEPROM, or flash memory. Volatile memory 1920 includes RAM, which acts as external cache memory. By way of illustration and not limitation, RAM is available in many forms such as SRAM, dynamic RAM (DRAM) , synchronous DRAM (SDRAM) , double data rate SDRAM (DDR SDRAM) , enhanced SDRAM (ESDRAM) , Synchlink DRAM (SLDRAM) , Rambus direct RAM (RDRAM) , direct Rambus dynamic RAM (DRDRAM) , and Rambus dynamic RAM (RDRAM) .

Computer 1912 can also include removable/non-removable, volatile/non-volatile computer storage media, networked attached storage (NAS) , e.g., SAN storage, etc. 

It is to be appreciated that FIG. 43 describes software that acts as an intermediary between users and computer resources described in suitable operating environment 1900. Such software includes an operating system 1928. Operating system 1928, which can be stored on disk storage 1924, acts to control and allocate resources of computer 1912. System applications 1930 take advantage of the management of resources by operating system 1928 through program modules 1932 and program data 1934 stored either in system memory 1916 or on disk storage 1924. It is to be appreciated that the disclosed subject matter can be implemented with various operating systems or combinations of operating systems.

A user, client, etc. can enter commands or information into computer 1912 through input device (s) 1936. Input devices 1936 include, but are not limited to, a pointing device such as a mouse, trackball, stylus, touch pad, keyboard, microphone, joystick, game pad, satellite dish, scanner, TV tuner card, digital camera, digital video camera, web camera, and the like. These and other input devices connect to processing unit 1914 through system bus 1918 via interface port (s) 1938. Interface port (s) 1938 include, for example, a serial port, a parallel port, a game port, and a universal serial bus (USB) . Output device (s) 1940 use some of the same type of ports as input device (s) 1936.

Thus, for example, a USB port can be used to provide input to computer 1912 and to output information from computer 1912 to an output device 1940. Output adapter 1942 is provided to illustrate that there are some output devices 1940 like monitors, speakers, and printers, among other output devices 1940, which use special adapters. Output adapters 1942 include, by way of illustration and not limitation, video and sound cards that provide means of connection between output device 1940 and system bus 1918. It should be noted that other devices and/or systems of devices provide both input and output capabilities such as remote computer (s) 1944.

For purposes of brevity, only a memory storage device 1946 is illustrated with remote computer (s) 1944. Remote computer (s) 1944 is logically connected to computer 1912 through a network interface 1948 and then physically connected via communication connection 1950. Network interface 1948 encompasses wire and/or wireless communication networks such as local-area networks (LAN) and wide-area networks (WAN) .

Communication connection (s) 1950 refer (s) to hardware/software employed to connect network interface 1948 to bus 1918. While communication connection 1950 is shown for illustrative clarity inside computer 1912, it can also be external to computer 1912. The hardware/software for connection to network interface 1948 can include, for example,  internal and external technologies such as modems, including regular telephone grade modems, cable modems and DSL modems, ISDN adapters, and Ethernet cards.

Reference throughout this specification to “one embodiment, ” or “an embodiment, ” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment. Thus, the appearances of the phrase “in one embodiment, ” or “in an embodiment, ” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.

As utilized herein, terms “component, ” “system, ” “interface, ” and the like are intended to refer to a computer-related entity, hardware, software (e.g., in execution) , and/or firmware. For example, a component can be a processor, a process running on a processor, an object, an executable, a program, a storage device, and/or a computer. By way of illustration, an application running on a server and the server can be a component. One or more components can reside within a process, and a component can be localized on one computer and/or distributed between two or more computers.

Further, these components can execute from various computer readable media having various data structures stored thereon. The components can communicate via local and/or remote processes such as in accordance with a signal having one or more data packets (e.g., data from one component interacting with another component in a local system, distributed system, and/or across a network, e.g., the Internet, a local area network, a wide area network, a cloud based infrastructure, a cloud based computing system, etc. with other systems via the signal) .

The above description of illustrated embodiments of the subject disclosure, including what is described in the Abstract, is not intended to be exhaustive or to limit the disclosed embodiments to the precise forms disclosed. While specific embodiments and examples are described herein for illustrative purposes, various modifications are possible that are considered within the scope of such embodiments and examples, as those skilled in the relevant art can recognize.

Claims (20)

1. A method, comprising:

   identifying, by a system comprising a processor, wireless access point devices within an area；

   determining a received signal strength indicator (RSSI) of a device to be located；

   for each respective wireless access point device of the wireless access point devices, determining:

   respective reference point devices each having a respective RSSI, with respect to the respective wireless access point device, that is similar to the RSSI of the device, and

   respective contour data representing a respective contour that maps distances of the respective reference point devices from the respective wireless access point device； and

   determining a location of the device based on a juncture determined from the respective contour data of the respective wireless access point devices.
2. The method of claim 1, wherein the determining the respective reference point devices comprises retrieving the respective RSSI of each of the respective reference point devices from a location fingerprint data store.
3. The method of claim 1, wherein the determining the respective reference point devices comprises determining that the respective RSSI of each of the respective reference point devices is within a statistical tolerance of the RSSI of the device.
4. The method of claim 1, wherein the determining the respective reference point devices comprises filtering the respective reference point devices based on a respective weighting associated with each of the respective reference point devices.
5. The method of claim 4, wherein the respective weighting associated with each of the respective reference point devices is based on the respective RSSI of each of the respective reference point devices.
6. The method of claim 1, further comprising:

   identifying the device to be located as an identified type of device； and

   calibrating the RSSI of the device to be located based on the identified type of device.
7. The method of claim 1, wherein the determining the respective contour data comprises minimizing the respective contour with a linear programming formulation.
8. A system, comprising:

   a memory to store instructions； and

   a processor, coupled to the memory, that executes or facilitates execution of the instructions to at least:

   identify wireless access point devices within an area；

   determine a received signal strength indicator (RSSI) of a device to be located；

   determine, for each respective wireless access point device of the wireless access point devices, respective reference point devices each having a respective RSSI, with respect to the respective wireless access point device, that is similar to the RSSI of the device；

   determine, for each respective wireless access point device of the wireless access point devices, respective contour data representing a respective contour that maps distances of the respective reference point devices from the respective wireless access point device； and

   determine a location of the device based on a juncture determined from the respective contour data of the respective wireless access point devices.
9. The system of claim 8, wherein the processor further executes or facilitates the execution of the instructions to retrieve the respective RSSI of each of the respective reference point devices from a location fingerprint data store.
10. The system of claim 8, wherein the respective reference point devices are determined based on the respective RSSI of each of the respective reference point devices being determined to be within a statistical tolerance of the RSSI of the device.
11. The system of claim 8, wherein the processor further executes or facilitates the execution of the instructions to filter the respective reference point devices based on a respective weight associated with each of the respective reference point devices.
12. A method, comprising:

    populating, by a server comprising a processor, a location fingerprint data store for reference point devices within an area within which a device is to be located based on time samples of received signal strength indicators at an access point device for the reference point devices；

    receiving distance information for the device based on an RSSI vector of the device at the access point device；

    determining an upper distance bound and a lower distance bound of a location of the device based on the distance information and location information stored in the location fingerprint data store；

    determining a metric to evaluate a difference between the distance information and location information stored in the location fingerprint data store；

    generating relaxation data representing a semi-definite programming relaxation based on the metric using the upper distance bound and the lower distance bound of the location as constraints on the generating； and

    locating the device based on the relaxation data.
13. The method of claim 12, wherein populating the location fingerprint data store comprises storing only a mean and a variance of the time samples of the received signal strength indicators for a respective reference point device.
14. The method of claim 12, wherein the determining the metric comprises determining a fingerprint noise value for each of the reference point devices.
15. The method of claim 12, wherein the determining the metric comprises determining a respective weight associated with each of the reference point devices.
16. The method of claim 12, wherein the distance information for the device comprises distance information received at various time intervals.
17. The method of claim 12, wherein the distance information for the device is based on determining a current estimated position of the device to a previously estimated position of the device.
18. A system, comprising:

    a memory to store instructions； and

    a processor, coupled to the memory, that executes or facilitates execution of the instructions to at least:

    populate a location fingerprint data store for reference point devices within an area within which a device is to be located based on time samples of received signal strength indicators at an access point device for the reference point devices；

    receive distance information for the device based on an RSSI vector of the device at the access point device；

    determine an upper distance bound and a lower distance bound of a location of the device based on the distance information and the location information stored in the location fingerprint data store；

    determine a metric to evaluate a difference between the distance information and location information stored in the location fingerprint data store；

    generate relaxation data representing a semi-definite programming relaxation based on the metric using the upper distance bound and the lower distance bound of the location as constraints on the generating； and

    locate the device based on the relaxation data.
19. The system of claim 18, wherein the processor populates the location fingerprint data store by storing only a mean and a variance of the time samples of the received signal strength indicators for a respective reference point device.
20. The system of claim 18, wherein the processor determines the metric based on determining a fingerprint noise value for each of the reference point devices.

Images