Indoor Geofencing Based on Sensorless Motion Sensing and Fingerprint Self-Updating

Abstract

Indoor location is definitively a key feature with immense value especial for geofencing. The received signal strength (RSS) fingerprinting based methodology is widely adopted to determine his/her proximity to that particular region. Its dynamic nature and maintain overhead remain a primary challenge. In this paper, we propose a hybrid electronic geofence approach that combines self-updating RSS fingerprints based localization and Channel State Information (CSI) motion detection. Multidimensional matching and filtering principle achieves fingerprints self-updating and improves the localization accuracy. CSI-based speed estimation reduces localization frequency and overhead. Our extensive real-world experiment results show that the proposed indoor geofencing method works well for more than 30 days without manual Wi-Fi fingerprints updating.

1 Introduction

Electronic Security Systems are increasingly applied and deployed in many mobile IoT scenarios [5, 26], e.g., mobile phone experience center, museum, library, and factory. They leverage optical fiber probe, infrared detection, geomagnetism detection and closed-circuit television methods [10] to protect individual or public safety and security. However, these solutions have many drawbacks. Optical fiber probe is appropriate for outdoor scenario due to its large locating errors, i.e., about 20 m [40]. Thermal imagery and geomagnetism detection solutions are vulnerable to heat sources or electromagnetic interference. Video based solutions suffer from illumination changes, large pose variations, and partial or full occlusions. Fortunately, location based services provide another supplementary scheme, Geofence [15] for indoor scenario. Geofence is a virtual perimeter for a real-world geographic area. It could be dynamically generated as in a radius around a point location, or be a predefined set of boundaries. Hence, Geofence is extensively used in children care [28], burglar alarm [2], and location based communication. Due to the wide deployment and availability of Wi-Fi infrastructure, Wi-Fi based electronic Geofence solutions have much advantages than other radio signal based solutions and becomes one of the most attractive techniques for electronic Geofence solution. Note that due to the complex and fluctuating indoor environments, it is hardly to calculate the Wi-Fi signal by a general formula. Hence, most indoor Geofence solutions leverage fingerprint based solution instead. The working principle of a typical fingerprint-based Geofence approach consists of two stages: site survey and fingerprint matching. In the former phase, a set of Radio Signal Strength (RSS) values from multiple Access Points (APs) are measured and recorded as the fingerprint for each location and labelled with “safe” or “alert”. A fingerprint database is accordingly constructed, in which the fingerprint-location relationship is stored. To verify wether a user or a device is in the legal zone, the Geofence algorithm searches current RSS measurements in the fingerprint database to find a matched location. Another emergent localization solutions leverage channel state information (CSI). CSI is a crucial parameter for Multi-user MIMO communication in next generation networking collaboration. However, although it contains richer information and the average accuracy is better than RSS, CSI are not suitable for this scenario due to the highly de-correlation property. If exploiting CSI, the fingerprint database must collect fingerprints every 6.25 cm under 2.4 GHz. That is a a extremely laborious project. Since the Geofence solution we mentioned in the following paragraphs is based on LBS, we will revisit the Wi-Fi fingerprint-based localization solutions and seek for the feasibility to perform accurate and robust indoor Geofence without increasing costs. We conduct extensive experiments and discover following limitations of Wi-Fi fingerprint-based Geofence:

• 1. Different locations sometimes have the same RSS fingerprinting, resulting in incorrect mappings between locations and fingerprints. The reason behind is that single channel RSS is an one-dimensional fingerprints with little anti-collision ability. Only one channel of RSS fingerprints cannot provide good uniqueness for localization.

• 2. There would be many RSS measurements in the same location. It is mainly caused by the signal fluctuation and human body blocking. For example, the obstacles near the receiver may weaken the received signal strength by about 10dB. Moreover, multi-path effect can result in frequency selective fading across the wireless channel.

• 3. APs have diverse spatial resolutions on the fingerprints of locations with different distances to AP. Since the value of RSS is inversely proportional to the distance from AP, the distribution is not uniform. Intuitively, the RSS nearby the AP has more resolution.

• 4. RSS measurements may experience a large delay due to hardware and software limitations of commodity wireless devices. In other words, latest measured RSS values could be the result of a scan performed several seconds ago. Since the user may be continuously moving, this RSS measurement would be expired for current localization query.

To address these problems, we design a new M ulti D imen-sional F ingerprint based scheme, namely MDF, for location based mobile device management (MDM) restriction. Compared to existing RSS based fingerprint, MDF involves more information about wireless signals to generate a more concrete fingerprint. In particular, we improve the localization accuracy from three perspectives. First, we weight each AP’s reporting and make the APs with better resolutions with more weights in the fingerprint matching. Second, we introduce multidimensional information, including RSS, transmission power, channel state, and body effect, to form the distribution of fingerprints for each location, to suppress the ambient interference. Third, we propose multi-dimensional matching principles to leverage above information and achieve fingerprints self-updating. Finally, we propose to leverage CSI standing wave property in indoor environment to trigger multi-dimensional fingerprint collection, which can significantly alleviate the wireless channel hopping overhead. Our contribution are summarized as follows:

• 1. We leverage the distribution of multidimensional information to generate fingerprints for distinct locations. Compared with single channel RSS approaches, the proposed fingerprint contains sufficient spatial information about the location of interests, enabling a high accurate indoor Geofence. In addition, it is also highly resilient to the interference and ambient change.

• 2. We propose a novel indoor geofence scheme, MDF, to realize lightweight, real-time and accurate indoor location based MDM restriction. We comprehensively consider the main factors that affect the localization accuracy, such as the AP discrimination, object’s moving speed, hardware and environment variance, and signal fading or shielding from the human body. MDF can detect the environmental variance and the movement state of device, which achieve the variable localization frequency and automagically fingerprints updating to improve the localization accuracy and reduce system maintenance overhead. In addition, we point out that the CSI means the 2-D standing wave property in rich multi-path environment from Clark model. This discovery theoretically guarantees that CSI variance can be leveraged to indicate device’s movement.

• 3. We implement MDF with commodity devices, which load comprised channel switching program and conduct extensive experiments in typical cyber-physical services. The extensive experiments show that our approach is with high localization accuracy and resilient to the ambient change.

2 Related work

As aforementioned reasons, electronic Geofence is a beneficial complement for other indoor security systems, especially in low-level-light and dynamic environments. Here, we merely introduce localization solutions. Current indoor localization approaches fall into two categories: fingerprint-based and modeling-based. Fingerprints [48] are utilized to assist positioning, and the most widely used one is Wi-Fi signal. In indoor environment, fingerprint based methods (e.g., Radar [7], Horus [47], SurroundSense [6], PinLoc [36]), first collect fingerprint of Wi-Fi signal (or cellular, or FM, or other sensors such as light) in advance at known locations inside a building, and then identify the user’s location by matching the fingerprint of this user with the fingerprint stored in database. Dead-Reckoning is another stream of techniques (e.g., [18, 33]) proposed in the literature for localization.

The mostly used fingerprint is the RSS value. Yang et al. [45] propose a crowdsourcing based indoor localization, which exploits the possibility of automatically establishing the mapping between fingerprint set F and position set P. In our previous work [23], graph matching algorithm is used to achieve the automatic mapping in complex environment. Wu et al. [41] leverages smartphones to collect real-time RSS samples at mobile reference points and adapts the complete radio map by learning the relationship of RSS dependency between different locations. Acoustic ranging (AR) assisted Wi-Fi positioning was recently developed to provide distance estimation between two users (e.g., [29, 30]). These schemes leverage the accurate AR and are able to provide high localization accuracy using the mapping of fingerprints with some additional distance constraint. However, if the environment changes, they need update the fingerprint database artificially.

CSI has potential for accurate indoor localization since the CSI tool [19] has been released to public on off-the-shelf hardware. CSI is not a simple extension of RSS on physical subcarriers but it reveals totally different information on frequency selective fading process [46]. Sen et al. [35] proposed a rotation based indoor localization system that leveraging the human bodies’ strong fading to Line-of-Sight (LoS) components. Roy et al. [36] proposed a CSI fingerprint-based localization system which can achieve meter-level precise indoor point localization. Based on the strong position distinction property of CSI, Jiang et al. [24] proposed an Wi-Fi Management Frame Authentication framework. Besides the above device-based localization, Xi et al. [42] proposed an CSI-based device-free crowd density estimation system. There are also many RFID based tag authentication and localization systems [21, 22, 37]. However, the expensive infrastructures narrow the their application scenarios, which are mostly implemented in warehouse. Compared with these schemes, our scheme provides an accurate moving speed estimation of a single user in a complex indoor environment. However, due to the highly de-correlation property, if we need collect all the fingerprints in the legal zone, it is time consuming.

Recently, the popularity of Software Defined Radio (SDR) system brings more powerful approaches. ArrayTrack [44] uses an antenna array driven by SDR to provide accurate Angle-Of-Arrival (AoA) based indoor localization. On the other hand, Wi-See [4] and PinIt [39] simulate the antenna array by a moving antenna. The latest work WiTrack [3] implements frequency-modulated continuous-wave (FMCW) radar technology on SDR platform, and it achieves 3D device-free human tracking. Although SDR platform exhibits strong potential, the deployment cost and computation requirement are still too high for wide range deployment.

3 Observation on SDF-based fingerprints

Previous RSS fingerprint based localization solutions leverage a fixed single channel of multiple APs placed in different locations to acquire and record a mass of RSS values to generate the location fingerprints. In matching phase, users exploit the obtained RSS collected from the same channel of these APs to localize their positio. We name these type of solutions as Single Dimensional Fingerprint (SDF) scheme. In this section, we investigate the properties of classical SDF fingerprint based solutions and show their limits in enabling accurate localization.

3.1 The restriction of time coherence

Many existing fingerprinting approaches collect several RSS values on a single channel with in reasonable delay, and leverage the mean or median of RSS values as the location fingerprint. They can obtain sufficient packets to generate the numerical characteristics via improving packets sending rate. If utilizing packet tcpdump tools, the sending rate can rise to 300–500 packets per second (p/s). However, due to the channel time coherence, excessively improving packet rate has little help in the fingerprint generation process and are helplessness to localization accuracy.

Time coherence is an engineering concept to characterize the channel time diversity which is often defined to be time separation Δt when the time domain correlation function R(Δt) drops below a certain level. Clarke [13] has shown that the correlation function R(Δt) has an close form expression of

$$R({\varDelta} t)=J_{0}(2\pi f_{D} {\varDelta} t)$$

where J₀(⋅) is the 0-order 1^st-kind Bessel function and f_D is the equivalent maximum Doppler shift, respectively. In wireless transmitter-receiver system, which is a typical linearly time-varying system, the environment change or reflectors/obstacles movement can be equivalent to the receiver movement which causes Doppler shift. This kind of Doppler shift is referred to as equivalent Doppler shift. However, in indoor environments, the typical equivalent maximum Doppler shift f_D is about several hertz [32]. If we set the transmitting rate to 200 p/s, i.e., Δt = 0.005, the time diversity, or time correlation would be about 0.98. Since commercial NIC can only return integral RSS values, we can only obtain a large number of identical RSS values, which are meaninglessness. In fact, our actual tests have verified this phenomenon.

We leverage “iw” [1] command to implement packet monitoring and channel hopping. “iw” is a new nl80211 based Linux Command Line Interface (CLI) configuration utility for wireless devices. It supports all new drivers that have been added to the kernel recently. For instance, we can use command iw phy phy0 interface add mon0 type monitor to create a new interface mon0 to set phy0 into monitor mode. In addition, we can use command iw dev mon0 set freq f_c to switch the center frequency of mon0 to f_c MHz. These operations will only spend several milliseconds. In motion detection phase (see Fig. 2), the client keeps normal communication to APs and obtain CSIs from preambles. When the system detects object’s abnormal moving (see details in Section 4.2), the client’s NIC card will change to monitor mode and record all the packets heard from ambient APs. Table 1 lists the unpacked packets information using single channel (Channel 100 whose f_c = 5500 MHz). The table lists the packets information as follow, time stamp indicated by the Timing synchronization function,¹ channel center frequency, RSS value, the identifier of basic service set,² transmitter’s MAC (source) address, and receiver’s MAC (destination) address, respectively.

Table 1 A glance of unpacked frames

As shown in Table 1, SDF-based solutions expose two main drawbacks: 1) In training phase, we have no need to record such amount of RSS values in a single channel, whereas we should leverage this opportunity to obtain more abundant, and meaningful fingerprints; 2) In matching phase, since users cannot endure long waiting cycles to obtain a stable RSS numerical characteristics, e.g., mean or median, calculating the distance between collected samples average or median and the mean or median in fingerprint database would result some localization errors. Hence, we, in this paper, first propose to leverage multiple channel fingerprint to improve location accuracy (detailed in Section 4.1) and exploit sample hypothesis testing to verify users’ location. In this way, we can not merely leverage all the sampled RSS values, but also obtain the confidence of localization precision (detailed in Section 4.6).

3.2 Resolution diversity

Wireless devices, e.g., APs, have a discrimination capability when fingerprinting a specific location. This capability, however, is subject to inherent constraints of radio signal propagation.

Discrimination capability is referred to as the ability that an AP distinguishes a specific location when using its RSS observations as fingerprints. Ideally, following the propagation law of wireless signals, the RSS of a certain wireless signal decays logarithmically with its propagation distance d. In other words, an identical ΔRSS can imply a smaller distance change Δd at the location closer to the antenna of AP, or a larger Δd at the location far away from the AP’s antenna. As shown in Fig. 1, the RSS variance shows vast difference in different physical positions, depending on the specific distance d. Hence, using the RSS reading from a long-distance AP may cause a large error in the location estimation, while using those from near APs can conversely mitigate the error. In fact, such a RSS variance also indicates a diversity of AP resolution across different transmitter-receiver distances.

Fig. 1

AP resolution

3.3 Measurement latency

The measured RSS might become time-ineffective due to a long delay or latency, e.g being outdated for estimating the location. The long delay or latency might be caused by software and hardware restrictions when performing device scanning and discovery.

For example, commodity smartphones acquire WLAN information in a passive scanning mode, in which they listen to periodic beacons flying in all working channels sent from surrounding APs. In this mode, the time duration that a client stays on a channel is 100ms by default, which is specified by the 802.11 standard [17]. Consequently, the latency incurred in capturing the AP information is about 1100ms since there are 11 available channels in typical 2.4GHz Wi-Fi. In practice, it takes about $1\thicksim 1.5$ seconds to complete a scanning for typical commodity smartphones. Due to the beacon conflict and channel collision, the beacon interval of 100ms cannot be always guaranteed, potentially resulting in missing some APs during a scanning. However, existing smartphone OS may direct duplicate the information scanned a few seconds before from these missed APs to the scanning result, which is indeed out of date for supporting localization.

3.4 Environment variance

The propagation of wireless signals in indoor environments is extremely complex. The intensity of a radio signal at a given location usually varies with time for a number of reasons. In general, the received signal is composed of both a Line-Of-Sight (LOS) component and numerous delayed components with different ambient attenuations. In particular, the impact of the channel variation contributes significantly to the RSS value of received signals. This impact also greatly varies at different positions due to the scattering-rich nature of indoor environments. All the components combine to the ultimate received signal, either enlarging or diminishing its RSS depending on the relative phases of the delayed reflections. Moreover, the observable reflection is affected not only by the signal propagation across the environment, but also by the bandwidth of communications, especially in those bandwidth limited systems.

3.5 Hardware variance

Another challenging issue is the hardware variance. The hardware variance is derived from heterogenous device components, e.g., the Wi-Fi chip-set and antenna. A Wi-Fi fingerprint is usually generated via training phase, and then used in the real tracking. However, the devices used in training phase to generate fingerprints may differ from users used in matching phase. The differentiation between those device would obtain different RSS values even in the same conditions. In order to avoid the manufacturing error among different devices, a calibration component is necessary in both training phase and matching phase.

4 The MDF system

In this section, we will introduce a novel indoor geofence/ localization scheme, namely MDF, as shown in Fig. 2.

Fig. 2

The system flowchart

The working process of MDF consists of two phases: training phase and monitoring phase. The major output of training phase is a fingerprint database in which a multidimensional RSS fingerprint and its corresponding location are associated. The fingerprint database is further used in monitoring phase to process MDM requests and it should be automatic updating. We describe the training and monitoring phases in detail in coming subsections and give brief introduction as follows.

Training phase

The core task of training phase is to build the fingerprint database. We divide this task into 3 steps: (1) creating fingerprint space; (2) determining the weight of APs; (3) eliminating device differences.

Monitoring phase

Since channel-hopping decreases communication throughput significantly, MDF does not leverage multi-dimensional fingerprint to manage mobile device perpetually. When MDF obtains device’s location, it verifies whether it is in the legal area. If not, MDF would send alarm to users. Otherwise, MDF continues estimate the motion state of device leveraging CSI preamble (see detail in Section 4.2). Note the CSI feedback meets the requirement of 802.11ac/ax protocol, the CSI reply operation would not cause additional overhead. According the motion state and position offset, MDF will selectively trigger multidimensional RSS collection when the device may approach legal boundary. When a location query comes, MDF takes the multi-dimensional fingerprint as a keyword and searches the fingerprint database. The best matched item is viewed as the location estimation and sent back to users.

As shown in Fig. 2, MDF eliminates the diversity of different devices’ gain by module “Device Dependence Elimination” (see details in Section 4.3). Then it determines the weight of APs for each location in the training phase (see details in Section 4.4). After that, MDF leverages the weighted RSS fingerprints as the inputs to estimate the location (see details in Section 4.7). Furthermore, after we get a set of location data, we can predict the position by next autoregressive model (see details in Section 4.5).

The core components of MDF include the AP selection, delay cancellation, hypothesis test based fingerprint matching, robust location estimation, and object tracking. In MDF, we assume that N APs are deployed in the training and matching scenario. The mobile device can receive the RSS from those APs in multiple channels.

4.1 Multi-channel fingerprints

As aforementioned, due to time coherence property, increasing the sample rate in a single channel cannot improve localization precision. We propose a novel solution to leverage multiple dimensional RSS information to promote the accuracy. We utilize frequency diversity to rich the fingerprints, i.e., we employ multiple channel with different center frequency to generate multi-dimensional fingerprint to achieve high positioning accuracy. In the remain part of this subsection, we will illustrate multiple channel fingerprints are meaningful and briefly introduce how to synchronize the channel switching on different APs.

The frequency domain correlation function sounds like the time correlation function mentioned above. Denote the frequency interval to be Δf, hence the frequency correlation function R(Δf) can be characterized as

$${R}\left( {{{\varDelta}_{f}}} \right) = \int\limits_{0}^{\infty} {{S}\left( \tau \right)} {e^{-j 2 \pi {\varDelta}_{f} \tau} }$$

where S(τ), termed power delay profile, is a power delay profile function of receiving delay τ. Rappaport et al. [34] point that when the frequency interval is larger than 4 MHz in an indoor radio environment, the frequency domain correlation function drops below a certain level. Since different channels possess 20–40 MHz (802.11n/ac) bandwidth [32], the different channels would have low correlations which can be used to generate fingerprints. Our test has verified this inference as shown in Table 2. Besides changing the client’s NIC into monitor mode, MDF also leverages command iw dev mon0 set freq f_c to switch the communication channel (center frequency) to f_c. This operation will only spend several milliseconds. Hence client can obtain multiple-channel RSS fingerprints in sub-second.

Table 2 RSS values in different channels

Compared with Table 1, we can see that multiple channel RSS values provide much more information than single channel RSS. We will theoretically prove that MDF is more precise than SDF and give a channel selection approach in Section 5.

In the following part of this subsection, we will discuss another problem: select how many channels and how to select channels to generate and match multi-dimensional fingerprints. However, this is not a simple nor trivial issue. On one hand, if the channels are uncorrelated, more channels would result little error variance (we will discuss this topic in Section 5). On the other hand, since correlation does not possess transitivity property, some low correlated channels might make up a couple of high correlated channel pairs and they are helplessness for localization . It is up to channel selection. Fundamentally, it is determined by the environment and the user’s current location. Hence, in training phase, we record the RSS of all the channels, while in matching phase, we dynamic select RSS values collected from proper channels for localization. Our basic idea is: 1)Leverage multidimensional scaling (MDS) algorithm to acquire a quasi-global distance in place of correlation between different channels in order to avoid to set up high related channels; 2)Obtain as many channels as possible with as lower correlation as possible. The channel selection algorithm is list as follows and the correctness and the complexity of this algorithm will be discussed in Section 5:

• 1. Calculate the correlation coefficient ρ_ij between RSS values collected from channel i and j;

• 2. Calculate the local distance d_i,j = 1 − ρ_ij;

• 3. Leverage MDS algorithm to obtain global distance D_i,j = MDS(d_i,j);

• 4. Construct an undirected weighted graph G=(V,E) where the weight of edge $e_{\overline {v_{i}v_{j}}}=D_{i,j}$;

• 5. Solve the Maximum Clique Problem to find the largest clique S. Here S is the selected channels set.

In the end of this subsection, we briefly introduce our solution to implement channel switching synchronization. We adopt a simple yet robust client server synchronization protocol. For each channel, the AP stays for 100ms, and broadcast 20 customized Wi-Fi frame containing the current timestamp and the channel number of next hop. When a client enters the environment, it stay on an arbitrary channel and listen for the traffic. When the client hear the customized frame sent by localization AP, it will soon synchronize its local counter and hop to the next channel along with he AP.

4.2 CSI based motion detection

As previous section mentioned, in order to keep normal communication, multidimensional fingerprint collection can only be triggered when the device moves close to the safe boundary from inside. Leveraging CSI position de-correlation property, MDF can estimate device’s moving distance. However, we cannot leverage CSI to estimate device’s position directly, since CSI site-survey is extremely labour consuming and CSI fingerprint is much vulnerable to environment changes. Fortunately, we do not need to do this. According to Jakes’ Model, in rich multi-path indoor environment, the CSI correlation follows 0-order 1^st-kind Bessel function [13]. That means the CSI must form a 2-D standing wave filed (like vibrations of a drum membrane) [16]. Hence, we can estimate the moving distance from the counts of nodes and antinodes of the standing wave. As shown in Fig. 3, if the device keep stable, the CSI varies less than 4 units. In contrast, if the device moves at about 0.15 m/s.³ We draw the CSI amplitude in Fig. 4. We can see the CSI amplitude changes much more dramatically. Hence, MDF can easily distinguish whether the device is moving or not. However, it is hard to count the wave node, i.e., moving distance, in the map due to environment noise. As shown in Fig. 5, we binarize the figure using O’tus method [31]. We count the flip numbers to estimate the moving distance using the centering mean value (drop the min and max value) of distance D counted by all subcarriers as Eq. 1⁴

$$ D=\underset{2 \le i \le 29}{{\text{CE}}} \left\{ {{{c{N_{i}}} \over {{\lambda_{i}}}}} \right\} $$

(1)

where c, N_i, λ_i are the velocity of light, flip count and centering frequency of i-th subcarrier, respectively. Here, we do not leverage mean value directly to depress the impact of large deviation. We do not leverage median value as well since if so, the resolution will limited by the minimum CSI wavelength (0.052m@5.825GHz).

Fig. 3

The CSI variance without moving

Fig. 4

The CSI variance with moving

Fig. 5

The binarized picture of Fig. 4

4.3 Device dependence elimination

Since the device used in training phase may quite differ from the devices in matching phase, there will exist mismatch in RSS measurements obtained at the same physical location from the same AP in two phases. The mismatch comes from the difference of the devices’ receiver gains, which will reduce the fingerprint quality. In following paragraph, we will analyze the RSS fingerprint and eliminate the device dependence via relative RSS.

4.3.1 Fingerprint decomposition

In training phase, we leverage a mobile device M₀ to investigate the RSS at location L. In MDF, we can get RSS matrix

$${P^{M_{0}}}(L) = \left\{ {p_{i,j}^{M_{0}}(L)} \right\}{_{m \times n}}$$

where i and j indicate i-th (i = 1,2,⋯ ,m) AP and j-th (j = 1,2,⋯ ,n) channel, respectively. According to Friis transmission formula [14], we can decompose the measured RSS value $p_{i,j}^{M_{0}}(L)$ into

$$ {p_{i,j}^{M_{0}}(L)}=G^{M_{0}} +G_{i}+ p_{i}+ pl_{i,j}(L) $$

(2)

where $G^{M_{0}}$, G_i, p_i and pl_i,j(L) are the gain of receiver (M₀), the gain of transmitter (i-th AP), the transmitting power of i-th AP and the combination of path-loss and multi-path fading of j-th channel established by M₀ and i-th AP.⁵ Since the former three values are constants, the RSS fingerprint related to location L only depends on the last one. Note G_i and p_i shared parameters for different users. We only need eliminate $G^{M_{0}}$ to eradicate device dependence.

4.3.2 Device-dependence elimination

Based on Eq. 2, $G^{M_{0}}$, which is determined by user’s device, must be eliminated since different devices have different receiver gains. G_i and p_i can be treated as constants since each user would leverage the same AP to obtain RSS. pl_i,j(L) is the relevant value that indicates the position of user. Therefore, we leverage relative RSS [11] to avoid device-dependence.

We exploit the difference of the RSS obtained from the benchmark AP, say AP₀ (details in Section 4.4) and the ones from the others as the position profile, i.e.,

$$ DRSS(L) = \left\{ {dpl_{i,j}(L)} \right\}{_{\left( m-1 \right) \times n}} $$

where

$$ \begin{array}{@{}rcl@{}} {dpl_{i,j}(L)} &=& {pl_{i,j}^{M_{0}}(L)} -{pl_{0,j}^{M_{0}}(L)} \\ & \overset{(2)}{=} & G_{i}-G_{0}+ p_{i}-p_{0}+ pl_{i,j}(L) - pl_{0,j}(L) \end{array} $$

If we choose a group of appropriate G₀, p₀, G_i and p_i values, we can make G_i − G₀ + p_i − p₀ = 0. Therefore, we can get that

$$ dpl_{i,j}(L) =pl_{i,j}(L) - pl_{0,j}(L) $$

(3)

In this way, the device diversity (device gain $G^{M_{0}}$) would be eliminated. We leverage the difference between different APs as the fingerprint.

4.4 Benchmark AP selection

In order to achieve accurate localization, we need to select an AP with high quality RSS fingerprints as the benchmark AP. Otherwise the error will spread to the other APs via device dependence elimination. The fingerprint of Benchmark AP should meet two conditions: a good stability and a high degree of differentiation.

A good stability means that the RSS measurements in the same place always have the similar values. Since the heavy multi-path effects and the high dynamic environment, the RSS measurements are constantly changing. We introduce the variance $({\sigma _{i}^{j}})^{2}$ of RSS measurements from the AP j at the position l_i as the stability metric. Obviously, a small $({\sigma _{i}^{j}})^{2}$ indicates a stable fingerprint.

A high degree of differentiation means that the RSS measurements in different places will get a very different values. Given that APs have diverse spatial resolutions on the RSS fingerprints with different range, it is inappropriate to equally use the RSS readings from all APs for fingerprint training and location estimation. Intuitively, augmenting the contribution from more discriminative APs, while limiting or even eliminating the influence from those fluctuating and distant APs can improve the quality of RSS fingerprint. Toward this goal, we attempt to find a discrimination metric that complies with physical constraints of signal propagation and simultaneously stays robust to RSS fluctuations. Note that we need not think much about device diversity in this subsection because the discrimination metric is for only a single device.

To quantitatively differentiate each AP for a specific location, we define a discrimination factor by estimating the physical distance between the AP and this location by using the following Log-Distance Path Loss (LDPL) model [11]:

$$ P_{d}=P_{d_{0}}-10\gamma \log\left( \frac{d}{d_{0}}\right) $$

(4)

where $P_{d_{0}}$ denotes the received power at a reference distance d₀ (measured in meter), γ is the path loss exponent, and P_d is the RSS measured in decibel at a distance of d (d > d₀). Let $P^{\prime }$ be the derivative of P to d, we can get $P^{\prime }=-10 \frac {\gamma }{d}$. Utilizing implicit function derivation rule and discretization, we have

$$ {\varDelta} d \approx Ce^{-\frac{P_{d}}{10 \gamma}} {\varDelta} P $$

(5)

where $C=-\frac {d_{0}}{10\gamma }e^{\frac {P_{d_{0}}}{10\gamma }}$ is a constant for a certain AP. The P_d will decrease with d increasing. For the same ΔP, the Δd will increase. In other words, the RSS measured closer to a reference AP is more discrimination. Therefore, we prefer to select the RSS fingerprints of nearer APs as a location’s signature.

To this end, we will re-sort APs with an instantaneous score S_i as follows:

As shown in Fig. 1, the RSS from AP attenuates fast in a very narrow field while slowly else. We set the score of different APs by appraising both the stability and the distinguishability of the AP.

In general, a “good” AP should provide a stable RSS fingerprint and a high degree of differentiation. The quality score of AP^j at position l_i is defined as following:

$${S_{i}^{j}}=\frac{{H_{i}^{j}}}{({\sigma_{i}^{j}})^{2}}$$

where $({\sigma _{i}^{j}})^{2}$ is the j-th AP’s RSS variance of current position l_i and ${H_{i}^{j}}$ is a distinctness index of AP^j at position l_i. ${H_{i}^{j}}$ can be calculated by following steps:

• 1. Query all the RSS of l_i’s δ-neighbourhood $RS{S_{k}^{j}}$ where $P_{k} (k=1,2,\cdots ,N) \in \bigcup (l_{i}, \delta )$. δ is the action radius which defaults to “1”.

• 2. Solve the rate of change of RSS^j at position l_i. That is ${{H_{i}^{j}}}_{k}=\frac {\vert RS{S^{j}_{k}}-RS{S^{j}_{i}} \vert }{\vert | l_{k}l_{i}\vert |}(k=1,2,\cdots ,i-1,i+1,\cdots ,N)$.

• 3. Calculate the mean value of RSS change rate at position l_i. That is ${H^{j}_{i}}=\frac {\sum \limits _{1\le k \le N,k \neq i}{{H_{i}^{j}}}_{k}}{N-1}$.

Therefore, the benchmark AP (AP₀) at position l_i is set to $\arg \max \nolimits \limits _{j} {S_{i}^{j}}$

4.5 Delay mitigation

According to the 802.11 specification and our synchronization protocol, the receiver remains on a channel as long as 100 ms. Hence, a mobile device will take about 1$\sim$1.5 s for the commercial Android OS in one round of scanning.

To mitigate the impact of the delay, especially in the mobile scenario, we seek assistance from historical information of positions. Because we only need to predict future short-term (only 1-2 s) position, the device D’s motion can similarly be seen as a constant one in a short span of time, we can forecast the location L_t[i] at time slot t[i] by the latest two positions L_t[i− 1] and L_t[i− 2]. Because the orientation of D is the unit vector of $\overrightarrow {{L_{t\left [ {i - 2} \right ]}}{L_{t\left [ {i - 1} \right ]}}}$ and the velocity of D can be inferred by the norm of distance between L_t[i− 1] and L_t[i− 2]. If the movement vector (direction and velocity) is fixed, the position of the constant moving device D is determined. Obversely, calculating these two values are trivial and inefficient. To address this issue, we leverage second order autoregressive model to simplify calculations. In this model:

$$ L_{t[i]} = \beta \cdot \left[ {\begin{array}{*{20}{c}} 1 \\ {L_{t[i-1]}} \\ {L_{t[i-2]}} \end{array}} \right] $$

(6)

where β = [β₀,β₁,β₂] is a systemic parameter, and L_t, L_t− 1 and L_t− 2 are the positions in time slot t, t − 1 and t − 2, respectively. The systemic parameter β₁ and β₂ is the contribution of historical location to current location while β₀ denotes the estimation error. According to the historical location information L_t[1,2,⋯ ,i − 1], we can set an arbitrary vector, say [0,1/2,1/2] to β, and leverage standard least-squares method to estimate β [20]. Subsequently, we leverage the parameter β and historical location information L_t[i − 2] and L_t[i − 1] to estimate current location L_t[i].

As analyzed in Eq. 6, we should leverage the RSS values or rather estimated location to predict the user’s position. However, in most commercial scenarios, in order to maintain quality of service, devices will return the scanning results by duplicating information from last scan cycle if the RSS does not update. If we substituting the duplicated RSS to matching algorithm, we will obtain an incorrect location which will result a wrong prediction of the location. Unfortunately, the default record timestap would update when querying the RSS. In other words, we can not distinguish whether the RSS updates or are only duplicated from last scan cycle. Hence, we leverage Synchronization Function (TSF) timestamp [49] to record the receiving time of RSS. TSF provided by 802.11 MAC Management Function can help us solve this problem. TSF value is contained in the beacons transmitted by APs and would be not changed when querying. Hence we can clear distinguish whether the RSS updates.

4.6 Hypothesis testing based matching principles

As aforementioned in Section 3.1, we would leverage hypothesis testing, a statistical inference based localization solution to estimate the position of object. Probability based algorithms, e.g., Bayesian network [30], KL-divergence [38], and conditional random field [43], find the user’s location with the maximum likelihood. We do not employ above statistical inference solutions with following reasons: 1) Although Bayesian network or Bayesian inference can offer confidence interval [25], this type of solutions should calculate the priori probability of each event and only process single value but not a sequence of records; 2) KL-divergence like solutions can process all the records but cannot provide the confidence. Hence, in this paper, we propose to leverage hypothesis testing, which can utilize all the RSS record and offer a confidence coefficient.

In matching phase, after channel selection, user k can acquire his own RSS matrix $DPL^{k}_{i,j}(l^{\star })= \left \{ {dpl^{k}_{i,j}(l^{\star })} \right \}{_{\left (m-1 \right ) \times n}}$. The element dpl_i,j(l^⋆) can be expressed as

$$ dpl^{k}_{i,j}(l^{\star}) =pl^{k}_{i,j}(l^{\star}) - pl^{k}_{0,j}(l^{\star})+w^{k}_{i,j}-w^{k}_{0,j} $$

(7)

where $pl^{k}_{i,j}(l^{\star })$ is the power loss from AP i to user k’s location l^⋆ with central frequency f_j corresponding to channel j. Different from Eq. 3, since user k’s measuring error can not be eliminated through repeating measurements, we leverage $w^{k}_{i,j}$ to indicate user k’s RSS measuring error of j-th channel at i-th AP in Eq. 7.

According to Eqs. 3 and 7, we have

$$ \begin{array}{@{}rcl@{}} {\varDelta} dpl(i,j) \!&=&\! dpl^{k}_{i,j}(l^{\star}) - dpl_{i,j}(L)\\ &=&\! \left( pl^{k}_{i,j}(l^{\star}) - pl_{i,j}(L)\!\right) - \left( pl^{k}_{0,j}(l^{\star}) - pl_{0,j}(L)\! \right)\\ && + w^{k}_{i,j}-w^{k}_{0,j} \end{array} $$

If l = l^⋆, the first two component of Δdpl(i,j) are equal to zero and ${\varDelta } dpl(i,j)=w^{k}_{i,j}-w^{k}_{0,j}$. Hence, our basic idea is testing the following hypothesis,

• Null hypothesis $\mathcal {H}_{0}$: E(Δdlp) = 0 ⇔ l = l^⋆

• Alternative hypothesis $\mathcal {H}_{1}$: E(Δdlp)≠ 0 ⇔ l≠l^⋆

Only the proper location l^⋆ = l can accept the null hypothesis, and others l^⋆≠l would accept the alternative hypothesis.

Although Δdlp has a zero mean and finite variance, since we know nothing about the distribution of Δdlp, we cannot leverage standard hypothesis test directly. Fortunately, if the sample size ≥ 30⁶ the sum of Δdlp follows Gaussian distribution guaranteed by Lindeberg central limit theorem [9], i.e.,

$$\sum\limits_{i = 1}^{m - 1} {\sum\limits_{j = 1}^{n} {{\varDelta} dpl\left( {i,j} \right)} } \sim \mathcal{N}(0,{\sigma^{2}})$$

where σ² is the unknown variance. In single-channel fingerprint approach, although the packet sending rate of the device can be increased to 300 p/s or more, however, due to time coherence discussed in Section 3.1, in order to obtain sufficient quasi-unrelated RSS samples, users should stay in a place to wait for several seconds. When considering time-diversity, the time will last longer. That is impractical in a real scenarios. Fortunately, due to frequency diversity, leveraging multi-channel RSS records, MDF has much more valuable RSS information than SDF. Hence, MDF only need to spend a fraction of the time SDF would cost to collect RSS samples. For instance, if there are 5 unrelated channels available, we only need to spend 1/5 time to obtain sufficient RSS records than SDF.

We leverage t-test to test the null hypothesis. When null hypothesis is true, we have

$$ \mathfrak{t} = \frac{{\overline{{{\varDelta} {dpl}}} - {0}}}{{var({\varDelta} dpl)/\sqrt{(m - 1) \!\times\! n }}} \!\sim\! t((m - 1) \!\times\! n - 1) $$

(8)

where $\overline {{\varDelta } {dpl}}$ is the sample mean and var(Δdpl) is the sample standard deviation of the sample. The degrees of freedom used in t test are $\left (\left (m-1 \right )\times n -1\right )$. We can compare $\mathfrak {t}$ and $t_{\frac {\alpha }{2}}\left (\left (m-1 \right )\times n -1\right )$ (α is the significance level) to determine whether accept or reject the hypothesis, i.e., to determine whether the locations are matched or not.

For a given significant level α, say 0.05, the t-distribution of freedom degree $\left (\left (m-1 \right )\times n -1\right )$, say 29, the t-test threshold is t_0.025(29) = 2.0452.

Recall Eq. 8, the accept field should be

$$ \vert \mathfrak{t}\vert = \frac{{\vert\overline{{{\varDelta} {dpl}}} \vert \sqrt {(m-1) \times n }}}{{var({\varDelta} dpl)}} < t_{0.025}(29)=2.0452 $$

while the reject filed is $\vert \mathfrak {t}\vert \ge 2.0452$. In other word, if the result $\vert \mathfrak {t}\vert$ is less than 2.0452, we can say that the current location l^⋆ and the testing location l are identical under 95% confidence. Otherwise, we can say that the current location l^⋆ and the test location l are not the same location with significance level α = 0.05.

4.7 Robust estimation

Human body has a strong effect of electromagnetic energy absorption and reflection which can cause $5\sim 10$ dbm error. When a mobile device is placed at different positions near a human body, the RSS measurements may sharply change. The signal strength observed by a wireless receiver drops most significantly when there is an obstacle directly between it and the transmitter. Figure 6 presents an example of directional shadowing from real measurement. That is, if the moving direction in matching phase is different from training phase, the RSS fingerprint will be different at the same position.

Fig. 6

The body block effect

Fortunately, each location always receive multiple Wi-Fi signal from different APs. The strongest drop in signal strength is only from individual APs, called blocked AP, where the user is precisely at the line joining the AP and the phone. For most of APs, called unblocked AP, the the human body effect would not be significant.

Developing a good localization method that can accurately locate mobile user from “unblocked AP” by discerning “blocked AP”, is the motivation behind our work in MDF. Since unblocked APs is a majority, we introduce robust estimation to modify the conventional least squares method. Different from optimizing the sum of squared residuals, this is, ${\varSigma } r(P^{i}(s),P^{i}(\hat s))={\varSigma }(P^{i}(s)-P^{i}(\hat s))^{2}$, where Pⁱ(s) and $P^{i}(\hat s)$ are the RSS from current location and estimated location, respectively. Robust estimations employs a shaped residual function as

$$F= {\varSigma} s(P^{i}(s) P^{i}(\hat s))$$

where

$$s = \left\{ {\begin{array}{*{20}{c}} {\alpha {r^{2}}}&{\left| r \right| < \tau } \\ {\ln \left( {1 + 2\alpha \tau \left( {\left| r \right| - \tau } \right)} \right) + \alpha {\tau^{2}}}&{otherwise} \end{array}} \right.$$

α and τ are parameters to be configured. The former controls the height of the residual evaluation function while the latter impacts its width. In the SISR estimator, setting a small τ can lead to more accurate localization results, but will also increase the risk of falling into an incorrect local minimum. On the other hand, a more permissive τ reduces the venture at the cost of localization accuracy. SISR will degrade into Least-squares estimator when $\tau \to \infty$.

4.8 Automatic fingerprint update

Fingerprint-based localization methods are blamed for laborious site survey and mutable environment. In this subsection, we propose an automatic RSS update approach to keep a long-term effective fingerprint which can significantly reduce the re-fingerprinted frequency.

In fact, the environment would be gentle but continued changing, which results the RSS in the same location would consequently change. In conventional method, the fingerprints need to be re-investigated which will be a major expenditure of time and effort. Our approach can automatic update the RSS fingerprint. Fortunately, the changing rate is not big, and we will harvest sufficient valid fingerprint before fingerprint compromises by employing crowdsourcing.

The basic idea of RSS update is also based on t-distribution testing. Assuming there are r valid RSS different record of AP i channel j corresponding to location l, say $<{\varDelta } dpl^{\prime 1}_{i,j}(L),{\varDelta } dpl^{\prime 2}_{i,j}(L),\cdots ,{\varDelta } dpl^{\prime r}_{i,j}(L),>$, they should also follow t-distribution. Then the updated Δdpl should be

$$ {\varDelta} dpl_{new}=\overline{{\varDelta} dpl^{\prime}} -\text{sgn} (\overline{{\varDelta} dpl^{\prime}}) \frac{\varepsilon_{r} \times s^{\prime}}{\sqrt r} $$

where $\overline {{\varDelta } dpl^{\prime }}$, $s^{\prime }$ and sgn(⋅) are the the mean, the standard variance of valid RSS different record and signum function, respectively. ε_r is a small positive parameter associated to sample size r, that depicts the maximum difference between sample mean and expectation. By the weak law of large numbers, we have a qualitative result $\lim \limits _{r \to \infty } {\varepsilon _r} = 0$. However, if we need to depict the deviation quantitatively, it should leverage Sanov’s Theorem [12] to analyze the relationship between deviation and sample size. Assuming the noise in each channel is i.i.d and follows zero-mean Gaussian distribution $\mathcal {N}(0,\sigma ^2_N)$, according to Sanov’s Theorem, the probability of deviation |η|≥ ε_r, i.e., the deviation is bigger than ε_r, is

$$ P(\vert\eta \vert \ge \varepsilon_{r}) \approx 2^{-rD(P_{s}\|P_{t})}= 2^{-r{\frac{{\varepsilon_{r}^{2}}}{{\sigma^{2}_{N}}}}} $$

where D(P_s∥P_t) is the KL divergence between the sample distribution P_s and the theoretical distribution P_t of noise. If we set the significance level to be 0.002, i.e., P(|η|≥ ε_r)= 0.002, we can obtain $\varepsilon _r=\frac {3\sigma _N}{\sqrt {r}}$. In our actual experiment, since the valid RSS count r may change in different time, in order to simplify the calculation, ε_r is approximated as a piecewise-constant as follows:

$${\varepsilon_{r}} = \left\{ {\begin{array}{*{20}{c}} {0.1}&{r \leqslant 10} \\ {0.05}&{10 < r \leqslant 30} \\ 0&{r > 30} \end{array}} \right.$$

5 Discussion

In this section, we will give theoretical proof that MDF is superior to SDF and discuss why channel selection algorithm works. Assume we select s channels to estimate the user’s position $\mathbb {P}$ and each estimated position is $\widehat {\mathbb {P}} _i= \mathbb {P}+\varepsilon _i(i=1, 2, \cdots , s)$. Without loss of generality, we can assume the error ε_i follows zero mean Gaussian distribution $\varepsilon _i \sim \mathcal {N}(0,\sigma ^2)$. Note that σ² is the same with SDF based localization error variance. In MDF, the final localization result $\widehat {\mathbb {P}}$ can be expressed as a linear combination of $\widehat {\mathbb {P}} _i$ as Eq. 9.

$$ \begin{array}{@{}rcl@{}} \widehat{\mathbb{P}} &=& \sum\limits_{i = 1}^{L} {{\lambda_{i}}\widehat {\mathbb{P}}_{i}} \\ s.t.&& \left\{ {\begin{array}{*{20}{c}} {\sum\limits_{i = 1}^{s} {{\lambda_{i}} = 1} } \\ {{\lambda_{i}} \ge 0} \end{array}} \right. \end{array} $$

(9)

where λ_i is i-th unknown coefficient.

The MDF based localization error variance $\sigma ^2_{MDF}$ can be calculated as

$$ \begin{array}{@{}rcl@{}} \sigma^{2}_{MDF} & =& E\left( \widehat{\mathbb{P}}-{\mathbb{P}} \right)^{2} \\ & \overset{(9)}{{ = }} & E{\left( {\sum\limits_{i = 1}^{L} {{\lambda_{i}}\left( {\mathbb{P} + {\varepsilon_{i}}} \right)} - \mathbb{P}{\text{ }}} \right)^{2}} \\ &\overset{(a)}{\leqslant}& E \left( {\sum\limits_{i = 1}^{L} {{\lambda_{i}}^{2}} }{\sum\limits_{i = 1}^{L} {{\varepsilon_{i}}^{2}} } \right) \\ &\overset{(b)}{\leqslant}& E \left( {\sum\limits_{i = 1}^{L} {{\varepsilon_{i}}^{2}} } \right) \\ &\overset{(c)}{=}& \sigma^{2} \end{array} $$

The inequalities (a)and (b) leverage Cauchy inequality and Jensen inequality, respectively. The last equation (c) comes from the definition of variance. The equation (a) holds iff. $\frac {\lambda _i}{\varepsilon _i}$ is a constant and the equation (b) holds iff. λ_i = 1 while the others λ_{1,2,⋯ ,i− 1,i+ 1,⋯ ,s} = 0.

From this inequality, we prove that the localization error variance of MDF is always smaller than the localization error variance of SDF. As shown in Fig. 7, We evaluate the error estimations of SDF and MDF by simulation. We can see the error of MDF (denote by red points) is more concentrated than SDF (denote by blue points). More precisely, both the probability mass functions of SDF (Fig. 8) and MDF (Fig. 9) follow the Gaussian distribution approximately. The variance of SDF is significantly greater than the variance of MDF. In addition, we verify the excellent performance of MDF in evaluation section (see detail in Section 6.2).

Fig. 7

The error of SDF and MDF estimation

Fig. 8

The probability mass function of SDF error

Fig. 9

The probability mass function of MDF error

Furthermore, if the estimation error ε_i are independent to each other, we can get a better conclusion that $\sigma ^2_{MDF}=\frac {\sigma ^2}{s}$. Although independence is a harsh condition in reality, there is a perfect property that no correlation is equivalent to independence for Gaussian variables. In other words, we should select uncorrelated channel to estimate the user’s position. As we discussed in Section 4.1, different channel has low correlation due to large frequency interval. This is the reason that the localization accuracy of MDF is much better than the localization accuracy of SDF and why we should select channels but not employ all the available channels.

In the following part of this subsection, we will discuss the correctness and complexity of channel selection algorithm shown in Section 4.1. As discussed in that section, in order to improve localization accuracy, we should leverage as many weak correlated channel as possible. Since correlation coefficients can only describe the correlation between two sequence, we utilize distance instead and leverage multidimensional scaling to process these distances. An MDS algorithm aims to place each channel in high dimensional space such that the between-channel distances are preserved as well as possible. In this way, we can obtain a quasi-global distance to avoid make up a pair of channels with high correlation.

The next challenge is how to select as many channels as possible that makes the average quasi-global distance as large as possible. We can convert this problem into the Maximum Clique Problem in a weighted undirect graph. Although the Maximum Clique Problem [8] is an NP-hard problem, since the number of vertex is very limited (we only record less than 10 channels due to channel switching overhead limitation), we can quickly compute the selected channels from brute-force approach, e.g., deep first search.

The last part of this section will discuss the time complexity of MDF. Firstly, in motion detection phase, Otsu’s method would spend most of the time, whose time complexity is O(N_pix) where N_pix is the number of pixel in the finger. In our experiment, we block our CSI data into a 200 × 30 pixel picture, and merely spend several millisecond. If we leverage OpenCV library function, the time overhead would decease to sub-millisecond. In position matching phase, for a certain fingerprint, MDF would calculate the Δdpl for each channel of each AP, and compare the hypothesis function with the t-value. Hence, the time complexity is O(N_AN_C) + O(1) = O(N_AN_C). Since there are N_P position candidates, the total time complexity is O(N_PN_AN_C). In fingerprint updating phase, since we leverage piecewise-constant for simplification and approximation, the time complexity is O(N_AN_C) for current position. Hence, the overall time complexity is O(N_pix) + O(N_PN_AN_C). In our experiments, the time overhead is about sub-second, and MDF can achieve real-time indoor geofencing.

6 Evaluation

In this section, we will test the parameters in MDF and evaluate the performance of MDF. In each experiment, we randomly select a number of points to estimate the location using MDF. We record the reported coordinates of each test. The difference between the estimated location and ground truth, measured in meter, is the localization error, which indicates the accuracy of MDF.

As aforementioned, ambient changes incur a significant impact on the performance of RSS-based localization. We investigate the impact of three ambient changes, i.e., the deployment height, number of APs, and the number of used channels for localization. We then compare MDF and two classical state-of-the-art RSS based localization approaches, RADAR and Horus, in terms of localization accuracy. We also investigate performance of MDF in the office, classroom and lobby scenarios. Finally, we check the robustness of MDF in an indoor area with complex ambient settings.

6.1 System setup and deployment

We design and implement a prototype MDF system based on our customized APs, which are developed based on Intel ATOM-based mini PCs. We adopt a commercial Intel 5300 wireless NIC as the transmission component. However, in order to implement channel switching, we leverage the newest Ubuntu 18.04 to enable “iw” CLI. This type of APs has a single-core 1.6Ghz ATOM CPU, 4GB RAM and 8GB SSD hard drive. The Wi-Fi monitor mode is activated to enable the channel/power scanning functionality as aforementioned. In specific, We adopt a simple yet robust client server synchronization protocol. For each channel, the AP stays for 100ms, and broadcast 20 customized Wi-Fi frame containing the current timestamp and the channel number of next hop. When a client enters the environment, it stay on an arbitrary channel and listen for the traffic. When the client hear the customized frame sent by localization AP, it will soon synchronize its local counter and hop to the next channel along with the AP.

In our experiments, we use a laptop as the client receiver. We set the wireless card of the laptop in the monitor mode to enable the channel scanning. The scanning range is from Channel 100 to Channel 165, i.e., from 5.5Ghz to 5.8Ghz. In each channel, the AP varies its TX power from 8dbm to 15dbm during the scanning. As shown in Fig. 10, different channels have different RSS values. Compared with time domain, frequency domain has more diversity which can be leveraged as multi-dimensional fingerprints with low correlation.

Fig. 10

MDF under 5 GHz

6.2 MDF vs. SDF

In this subsection, we will demonstrate the performance between SDF and MDF in a typical application scenario, a part of indoor exhibiting hall, including a 117m² office as shown in Fig. 21. The test scenario is placed within a certain area of an imaginary grid, which splits the 12 × 9 rectangular area into 12 × 8 equal areas. In training phase, we investigate the multi-dimensional RSS fingerprint of each grid intersections, while in matching phase, we collect both single-dimensional and multi-dimensional RSS values at each testing points labelled with triangle. The estimated position calculated through both SDF and MDF RSS fingerprints are drawn with square and circle, and we leverage lowercase d and capital D to indicate locating error of SDF and MDF solution, respectively. In addition, to verify the locating robust performance, we sample some fingerprints at un-investigate positions, e.g., (9,1.5) (9,5,5), and (6.5,7) to estimate the position using training data. We can see that MDF has overwhelming strengths (about 0.6m locating error) than SDF solution (about 3m locating error).

6.3 Deployment height

We investigate the impact of deployment height. In practice, an AP is usually deployed in three typical heights, i.e., on the ceiling, furniture, and ground. In our experiment, the height of our APs is set as 3.5m, 1.6m, and 0.3m, respectively. We denote them as the top, middle, and ground. The CDF of localization is shown in Fig. 11. From the result, we find that the middle pattern provides the highest localization accuracy. The accuracy is lowest in the ceiling pattern. Generally, this result supports our analysis on the impact of the AP’s positions and blocking effect of human body. For the middle pattern based deployment, the distance between the AP and the object is usually smaller than that in the top pattern, i.e., the d in Eq. 4, indicating a higher AP’s resolution. This helps to increase the discrimination capability of AP. In addition, the light and other devices deployed on the ceiling may pose strong interference to the Wi-Fi signal, which also degrades the localization accuracy.

Fig. 11

Impact of different altitudes

6.4 The impacts of number of APs

We vary the number of APs used in our experiments, ranging from 3 to 6, and plot the localization accuracy in Fig. 12 It is obviously that the more the APs, the higher the localization accuracy. A very intuitive reason is that introducing more APs is helpful to reduce the probability of fingerprintcollision, which happens when one fingerprint is mapped to multiple locations. Due the complex multipath effect, this phenomenon is very common for RSS-only fingerprint since the RSS value is one-dimensional and prone to be same at different locations in indoor environments. Increasing the number of APs tends to enhancing the discrimination capability such that more distinct fingerprints can be generated.

Fig. 12

Impact of different number of APS

On the other hand, the blocking effect from the human body can also be alleviated by introduce more APs. In this case, the methods with good anti-breakdown ability [27], e.g., the SISR method used in MDF, can provide high accurate estimation. In theory, if the ratio of the RSS readings from blocked APs is not larger than 25%, the estimation can remain accurate.

6.5 The impacts in different scenarios

Similarly, using more channels also improve the localization accuracy. In our prototype, we use 5GHz as the operating spectrum. It is worth to note that in the IEEE 802.11 specification, there are 42 channels designated in the 5 GHz spectrum, spaced by 5 MHz. The channels involved in our prototype are No. 100, 108, 128, 140, 149, 153, and 165 channels, with their center frequency as 5500 MHz, 5540 Mhz, 5640 MHz, 5700 MHz, 5745 MHz, and 5825 MHz. We increase the number of channels from 3 to 7, which are selected by channel selection algorithm shown in Section 4.1. We examine the CDF of localization error, as shown in Fig. 13. Indeed, the accuracy mainly depends on the number of incoherent channels. The more incoherent channels we use, the higher the accuracy, which is proved in Section 5. We can see we may reach the point of diminishing returns when the channel numbers increase to 5. That is because although we introduce more channels, the channel correlations are rolling up as well. The experiment result well supports our theoretical analysis. Thus, it is promising to reduce the expectation of error by using more APs in practice.

Fig. 13

Impact of different channels

6.6 Comparison with RSS-only approaches

We compare the localization accuracy of MDF to that of two state-of-the-art RSS-only approaches, namely RADAR and Horus. The experiments are conducted in the office, classroom, and lobby scenario, and the results are shown in Figs. 14, 15, and 16. We can find that MDF outperforms RSS-only approaches in all scenarios, achieving a localization error of < 0.7 m in average. Note that in the office scenario, the localization accuracy when using Horus approaches that of MDF. This is because Horus uses the distribution of the RSS values as the fingerprint, which demonstrates good resilience to dramatic environmental changes. In the lobby scenario, the localization accuracy of MDF is much higher than other two approaches. This is because MDF tackles the problem of outdated data in the location-fingerprint matching by adopting the second order auto regression model to predict the location of object. This result also indicates that the RSS-only fingerprint is vulnerable to the mobility of objects or devices.

Fig. 14

CDF of locating accuracy in classroom

Fig. 15

CDF of locating accuracy in office

Fig. 16

CDF of locating accuracy in lobby

6.7 Comparison among variant MDFs

We check the localization accuracy of using variant MDFs, including the MDF only(MDF), AP weight-based MDF(WP+), robust estimation localization MDF(SISR + ), and the MDF combining all measurements (ALL). The experiments are conducted in three scenarios and the results are plotted in Figs. 17, 18, 19. The involvement of WP and adoption of SISR significantly improves the localization accuracy, i.e., reducing the error by approximately half. In addition, the result indicates that the weight-based mechanism and robust estimation mechanism can collaboratively improve the localization accuracy. It is worth to note that the improvement from adopting WP and SISR is not the same. In the classroom scenario, the WP + MDF performs better than SISR + MDF. This is because that the layout of classroom is commonly regular, and the ambient changes smoothly. In contrast, SISR + MDF shows a better accuracy than WP+MDF in the office scenario. This result shows that the SISR+MDF is capable of mitigating the impact of the complex environment, blocking effect by human body, or insufficient number of APs.

Fig. 17

Location error in classroom

Fig. 18

Location error in office

Fig. 19

Location error in lobby

6.8 The performance of CSI based motion detection

In this subsection, we will evaluate the motion detection performance. Since CSI cannot estimate direction, we only test the distance precision of our solution in different scenarios. In this experiment, we move the device apart from its original position 5m with different packet sending rate. We evaluate the impacts of packet rate and the scenarios with 20 times for each group. As shown in Fig. 20, the accuracy among three scenarios are acceptable, the max error is less than 0.25 m, i.e., 5%. We can see that for the scenario with richer multi-path, the smaller of average error. That is because more multi-path will generate more stable standing wave filed. That means it can work well in complex scenarios. In addition, we can see that the packet sending rate with 50 packets/s and 100 packets/s have little impacts on the estimation error. That means the CSI sample rate can lower down.

Fig. 20

The performance of CSI based motion detection

6.9 Localization in complex indoor environment

We focus on the tracking error in the indoor environment. We deploy our prototype in an 12 m × 9 m room. The left part of this room is with many partition boards, desks, chairs, and other stuff. The right part of this room is indeed a small meeting room. Thus, the left part is much more complex than the right part in this room. We than ask a volunteer to move randomly in this room. The room is site-surveyed using MDF in advance. We plot the location of a volunteer estimated by MDF and the real one in Fig. 21. In this figure, small pink triangles represent the real positions of volunteers, i.e., the ground truth. The red circles represent the results of using multidimensional fingerprint estimation. For example, at a certain time, a volunteer is at the position of (11,3). If the estimated location by MDF is (11,3), the error is 0. The results clearly show the influence from indoor environments. Since the left part is more complex, the tracking error, i.e. < 0.7 m in average, is larger than that in right part i.e. < 0.32 m in average. However, MDF still works reliably in complex indoor environments, enabling a high accurate location estimation. The maximum localization error is not larger than 2.1 m, and the average error is smaller than 1 m.

Fig. 21

The location error in complex indoor environment

6.10 MDF with/without self-update

In this subsection, we evaluate the impact of self-update mechanism, we can see the proposed mechanism can efficiently improve the long-term localization accuracy. As shown in Fig. 22, we can see that with our self-update mechanism, the average localization/geofence precision can maintain about 1m after 10 days, while the average precision error of contrast group without self-update mechanism will rise to about 3 m. This experiment soundly illustrate that the effect of our self-update mechanism. Furthermore, after 1 month, the error using our approach merely increase 1 m, while that error without self-update mechanism climbs to 6 m. Note that the experiment scenario is a 12 × 9 rectangular area. That means the fingerprint database without self-update mechanism is invalid thoroughly while our solution can still work.

Fig. 22

The impact of fingerprint self-update mechanism

7 Conclusion

In this work, we propose MDF, an automatic and continuous Wi-Fi fingerprints self-updating service for electronic Geofence that exploits the static power of mobile devices. The combination of RSS, transmission power and channel information significantly improves the localization/Geofence accuracy and reduces system maintenance overhead. We prototype MDF and conduct experiments in typical buildings. Experimental results from 30 days across 6 months demonstrate that MDF effectively accommodates the RSS deviations caused by environmental dynamics. Using the automagical updating fingerprints, MDF provides 2x improvement in localization/Geofence accuracy for long-term running Geofence service.