A Kriged Fingerprinting for Wireless Body Area Network Indoor Localization

Abstract

The accurate and efficient localization of a person equipped with wireless body area network (WBAN) is still a major issue in surveillance systems. Localization mechanisms using signal strength suffer from inaccuracy but those especially based on fingerprints are likely more accurate for indoor environment and some related mechanisms have been proposed. However, a simple and accurate mechanism is still unavailable for indoor environment except those using ultra wideband technology which is not yet implemented in all existing devices. This paper proposes a new mechanism based on fingerprinting for WBAN indoor localization named Kriged Fingerprinting. From the recorded data, this proposed model generates a huge unsaved database used to estimate the mobile node. It is a hybridism of fingerprinting, particle swarm optimization (PSO) and kriging. The fingerprinting method operates into two phases: the first is the training phase that serves to build a radio map in a database and the second phase is a matching phase. PSO is used as a matching algorithm and when a particle gets to an unrecorded location, the kriging mechanism is used to interpolate its locations values. In comparison with some works done for indoor localization mechanisms and based on fingerprinting, our proposal outperforms all in terms of accuracy: the mobile node is localized with a mean error value of 0.906 m. Hence, the kriging method brings more improvement in localization based on fingerprinting.

1 Introduction

The localization problem for mobile node [1] is becoming more and more an interesting topic because of a widespread increase in deployment of mobile systems and applications [2] that are getting part of our daily life. These systems and applications can be public or private. This interest increases much more for the wireless body area networks (WBANs) applications as the persons equipped with WBAN need to be localized for their assistance [3].

So far, few works [4, 5] specific to WBAN in general and particularly to single WBAN localization have been done and some others using fingerprints [6, 7] have been performed, focusing on the localization problem for wireless sensor network (WSN). The WBAN presents some specificities: for healthcare applications, data conveyed are sensitive and the energy consumption is another parameter to take into account. In addition, the localization accuracy for a single WBANed person is very important in an emergency case so as to act at appropriate moment [8]. In this paper our work focuses on the single WBAN indoor localization aiming to achieve a high accuracy and our proposed solution is based on centralized architecture as illustrated in Fig. 1, to overcome the energy consumption limitations for the sensors. Therefore, locating a patient returns to locating a WBAN coordinator.

Fig. 1

Localization model in elders home

We propose a new approach for WBAN indoor localization using a combination of Fingerprinting [9], PSO [10, 11] and Kriging [12, 13]. PSO is chosen instead of other matching algorithms such as Nearest Neighbor because of its simplicity and efficiency especially in solving continuous problem. Kriging method finds its interest in helping to interpolate non-fingerprinted points values where PSO particles can be located at any moment. Thus, with a minimum error, it generates other data without being big space consumer.

Our approach provides three main contributions: it first intends to achieve good accuracy, then aims to overcome the problem related to the fact that a mobile node must stop moving while it is collecting Received Signal Strength (RSSs) from access points and finally, it is designed to be specific to indoor WBAN field. The results are encouraging because the actual mobile location is within a circle of average radius of less than one meter and centered at the estimated location, i.e. the average error is less than one meter.

The rest of this paper is organized as follows: Sect. 2 presents works led on indoor localization using fingerprinting, Sect. 3 details our approach and Sect. 4 gives parameters used for experimentation and the test bed description. Section 5 presents results and discusses them before concluding and giving future work in Sect. 7.

2 Related Works

Even if the localization problem of a mobile node in outdoor environment has been efficiently resolved by using global positioning system (GPS) [14], localization in indoor environment is still challenging in terms of accuracy. Some related works using RSS fingerprints have been proposed with varied methodologies [4]; these include the work [6] that proposes an alternative mechanism based on fingerprinting and intends to use a minimum number of anchor nodes. In addition, the indoor area is thought as a matrix consisting of rows and columns and the location of the mobile node is presented as a cell in this matrix. The k-nearest neighbor (knn) [15] in the matching algorithm most used. Mechanisms based on fingerprinting are more accurate for indoor localization but the radio map requires a regular maintenance for recalibration. In [16] authors proposed a new concept known as the asynchronous interval labelling that intends to solve the problem by generating users place labels with the mobile accelerometer. However, authors in [7] studied and proposed a mobile phone system based, the SurroundSense, which tries to get good accuracy by using ambient fingerprints built with acoustic, optical, emotional and weather attributes. The localization accuracy can also depends on the site size: if this latter is wide and the anchor nodes do not cover the whole site, the accuracy is worst. Authors in [5] have proposed a distributed location estimation method to solve the problem: the location space and the input signal are divided into clusters according to the visible access points. Unfortunately, the accuracy for indoor localization based on range measurements from RSS is also affected by the Non-Line-Of-Sight (NLOS) conditions i.e. scattering and reflections at different objects and the fingerprinting mechanism can be the solution [4]. In [8] there is proposed a localization method for a grid environment. Although positioning in indoor environment is still an important issue for existing systems, using UWB technology allows to achieve a better accuracy indoor as UWB signal has the ability to go through objects such as walls [17] what is demonstrated in [18] where achieved accuracy is at nearest centimeter. However, all devices do not use this technology yet especially if one wants to use access points this would lead to new infrastructure what means the increase of the cost. Therefore, in our experiments we chose to use existing access points in NLOS conditions to maximize the quality of the model.

3 Proposed Approach

In this paper a combined localization mechanism using Fingerprinting, PSO and Kriging in the purpose of increasing the localization accuracy is proposed. Our proposed mechanism requires two phases: training phase and localization phase. During the training phase, a RSSs fingerprinting database is elaborated based on a set of test points.

As for the second phase, PSO is used as a matching algorithm in which each particle compares the RSSs received from the mobile device with the RSSs stored in the database and corresponding to the current particles position. If this position is not fingerprinted, corresponding RSS values are estimated using Kriging method. The distance between the particles location and each recorded location in the database is computed using the five closest locations values to interpolate the current particles location. The position where a particles fitness value is less than or equal to a threshold value, the fitness optimal value (FOV), or is the smallest of others at the end of algorithm, corresponds to the mobile devices location. Figure 2 is a flow diagram that illustrates all the localization process.

Fig. 2

Kriged fingerprinting flow diagram

3.1 Fingerprinting

As mentioned before, Fingerprinting consists of two phases: a training phase and a localization phase. In a training phase a mobile device moves through the environment recording the RSSs from a group of access points in their radio coverage range and its current location. For our approach, the device’s current location is always one of the grids points. Hence, the radio scan is considered as a measurement, the physical position where the measurement is performed as a location and the recording of the signal strength as a reading. To build a radio map of a room, a mobile device, a coordinator of the WBAN, takes a series of measurements in multiple locations of the room. Each measurement is composed of several readings, one for each radio source in range. Once the training phase is complete, the localization phase can be launched: a client can estimate its location by performing a measurement and feeding it to a localization algorithm (PSO + Kriging), which estimates the clients location based on the similarity of the signal strength signatures between the testing and the training points.

3.2 PSO

PSO is a population based iterative parallel search algorithm that originally models the way crowds of individuals like fish or birds moving towards an objective. It is a population-based stochastic approach to solve continuous and discrete optimization problems [10]. PSO consists of a population (or a swarm) of $s$ particles each of which represents a potential solution. The particles explore an $n$-dimensional solution space while minimizing or maximizing, according to the problem form, the objective function $f$ commonly called $fitness$. The fitness of a particle close to the global solution is lower (in the case of minimization) or higher (maximization) than the one that is farther [11]. In our case, the objective function is to minimize the diversion between the RSSs fingerprinted or estimated and RSSs captured by the mobile device. At instant $t$, each particle $i$ occupies a position $X_{id}$ and moves with a velocity $v_{id}, 1 \le i \le s$ and $1 \le d \le n$, where $s$ stands for the particles number and $n$ the space dimension. Each particle has a memory to store $pbest_{id}$, the position where it had the best fitness, and $gbest_d$, the best position found so far among all particles or in its neighborhood if it is defined. If neighborhood is defined like in our case, $pbest_{id}$ is the best position among the neighbors of each particle. At each iteration $k$, velocity $v_{id}$ and position $X_{id}$ of each particle are updated using Eqs. 1 and 2.

$$\begin{aligned}&\displaystyle v_{id}(k+1) = \chi * \left( \underbrace{\omega * v_{id}(k)}_{A} +\,\underbrace{c_{1} * rand_{1} * (pbest_{id} - X_{id})}_{B} \right. \nonumber \\&\displaystyle \left. \quad +\,\underbrace{c_{2} * rand_{2} * (gbest_{id} - X_{id})}_{C}\right) \end{aligned}$$

(1)

$$\begin{aligned}&\displaystyle X_{id}(k+1) = X_{id}(k) + v_{id}(k+1) \end{aligned}$$

(2)

where $rand_1$ and $rand_2$ are random numbers uniformly distributed between 0 and 1, $\omega$ an inertial weight and $c_1$ (cognitive parameter) and $c_2$ (social parameter) the acceleration coefficients. $\chi$ is the constriction factor. By using the constriction factor, the amplitude of the particles oscillation decreases, resulting in its convergence over time [19]. Apart from the value given by Eq. 3 [19],

$$\begin{aligned} \chi = \frac{2}{|2-\varphi -\sqrt{\varphi ^2 - 4 \varphi }|} \end{aligned}$$

(3)

where $\varphi = c_1 + c_2, \varphi \le 4$.

We found suitable to use a dynamic value of $\chi$ given by Eq. 4:

$$\begin{aligned} \chi = \frac{1}{1-it} \end{aligned}$$

(4)

where $it$ is current iteration.

• A corresponds to the physical component of the movement and the $\omega$ parameter controls the current movement influence on the future movement. This component influences the particles trend to follow the current direction.

• B corresponds to the cognitive component of the movement led by the $c_1$ parameter. Its influence is that the particle tends to move towards the best position it had occupied before.

• C corresponds to the social component of the movement led by the $c_2$ parameter. This component makes the particle to move to the best position found in its neighborhood or in all the search space. Since its introduction in [9], PSO has been much modified to be adapted to many different environments [20]. Many versions of PSO have been proposed and applied to solve optimization problems in diverse fields [21]. The Algorithm 1 illustrates the PSO version used in this paper.

3.3 Kriging

The kriging method [12, 13] is a spatial prediction mechanism used to estimate a value at a given location using observed values at surrounding locations. The spatial interpolation is an estimation problem modeled by the Eq. 5:

$$\begin{aligned} F(X_0)=\sum _{i=1}^{m} \omega _i \times F(X_i) \end{aligned}$$

(5)

where $X_0$ is a location where the $F(X_0)$ value is unknown, $X_i$ is one of $m$ surrounding locations where $F(X_i)$ values are known and $\omega _i$ are weight coefficients.

Given the Eq. 5, the kriging method consists of calculating the unbiased weight coefficients $\omega _i$ using the semivariogram modeled by the Eq. 7. These weights are unbiased by applying the condition set by Eq. 6.

$$\begin{aligned} \sum _{i=1}^{n} \omega _i = 1 \end{aligned}$$

(6)

$$\begin{aligned} \gamma (d) = \frac{1}{2n(d)}\left( \sum _{i=1}^{n(d)}(v(X_i)-v(Y_i))^2\right) \end{aligned}$$

(7)

where $n(d)$ is a number of location pairs $(X_i,Y_i)$ of distance $d$ and $v(X_i)$ is the value at the location $X_i$. In other words, possible combinations by two of all locations are done to measure the distance between them and a matrix of distances is set. For each distance $d$, all location pairs of that distance are counted and their number gives $n(d)$ Practically, the exponential model is used to compute the variogram following Eq. 8.

$$\begin{aligned} \lambda (d;a,s,r) = \left\{ \begin{array}{ll} 0, &{} \quad d = 0\\ a + (s - a) \times \left( 1 - e^(\frac{-1.5 \times d}{r})\right) , &{} \quad d > 0 \end{array} \right. \end{aligned}$$

(8)

where $a$ is a nugget, $s$ is a sill, $r$ is a range of the exponential model and $d$ the distance.

Figure 3 illustrates the exponential variogram fit with visible values of nugget, sill and range.

Fig. 3

Exponential variogram fit

Using the Eq. 8, we build a square matrix of distances from all pairs of involved points, calculate its semivariogram and then turn it into a data covariance matrix as follows:

$$\begin{aligned} K = [s - 0.5 \times \lambda (d(X_i, X_j))]_{ij}, \end{aligned}$$

(9)

$i=1 \ldots n; j=1 \ldots n$

Thus, we obtain the kriging system with unbiased condition as follows:

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c} K &{} 1 \\ 1 &{} 0 \end{array} \right] \times \left[ \begin{array}{c} \omega \\ \mu \end{array} \right] = \left[ \begin{array}{c} \lambda ^* \\ 1 \end{array} \right] \end{aligned}$$

(10)

With $\mu$ the Lagrange parameter, $\lambda ^*$ is solution to the semivariogram expression given by Eq. 11 and $\omega$ is a vector of kringing coefficients.

$$\begin{aligned} \gamma ^* = \left[ s - \lambda (d(X_1, X_0)),\ldots , s - \lambda \left( d(X_n, X_0)\right) \right] \end{aligned}$$

(11)

where $d(X_i, X_j)$ stands for the distance between two point locations with $i,j<n$ and $n$ the number of all point locations. Hence, we solve the system given by Eq. 12 to find the coefficients $\omega = (\omega _1, \ldots , \omega _n)^T$.

$$\begin{aligned} \left[ \begin{array}{c} \omega \\ \mu \end{array} \right] = \left[ \begin{array}{c@{\quad }c} K &{} 1 \\ 1 &{} 0 \end{array} \right] ^{-1} \times \left[ \begin{array}{c} \lambda ^* \\ 1 \end{array} \right] \end{aligned}$$

(12)

where $1$ beside $K$ is a vector of the same length as the matrix $K$.

4 Experimental Setup

4.1 Usage Context and Test Bed Description

In a real scenario case, we assumed that a patient equipped with a WBAN for blood pressure, heartbeat or other physiological indicator is at home dealing with his daily life activities but needs to be monitored by a remote station over network connection for any critical situation. It is then necessary to send patients location with physiological data to know whether the emergency warning indicator is due to an accident or an environmental effect of the place where he is located so as to initiate a prompt action whenever necessary [8]. Thereby, we developed a centralized algorithm that processes data from mobile device of the patient to determine its location. We led experimental analysis in a room of the Laboratory of Electronics and Information Technologies (LETI) that we divided into square cells of 1.5 m of side and covered by five access points as shown in Fig. 4.

Fig. 4

Experiment test bed view

The tests have been performed on a laptop Dell core2 duo, CPU T6670 @ 2.2 GH with Windows7 32 bits and installed memory of 4 GB. The inSSIDer [22] which is a Wi-Fi network scanner application for Microsoft Windows and Apple OS X developed by MetaGeek was used to collect data while the processing has been carried out with Matlab.

4.2 Experimental Parameters

During the fingerprinting training phase, each grid point is recorded with RSSs from five access points collected during 10 seconds and saved in database as a matrix: $P_k =(a_{i,j}), 1\le i\le 6, 1\le j\le 7, 1\le k\le 24$. It was noted at most 6 RSS different values during those 10 s. Each row of the matrix represents different RSS values from one access point with their average at the end except the 6th which represents the grid point coordinates and collector devices location as illustrated below:

$$\begin{aligned} P_4 = \left( \begin{array}{lllllll} 57 &{}\quad 59 &{}\quad 54 &{}\quad 53 &{}\quad 52 &{}\quad 52 &{}\quad 55.50 \\ 77 &{}\quad 77 &{}\quad 74 &{}\quad 74 &{}\quad 74 &{}\quad 73 &{}\quad 74.83 \\ 88 &{}\quad 88 &{}\quad 88 &{}\quad 82 &{}\quad 82 &{}\quad 80 &{}\quad 84.66 \\ 83 &{}\quad 83 &{}\quad 79 &{}\quad 79 &{}\quad 79 &{}\quad 81 &{}\quad 80.66 \\ 85 &{}\quad 85 &{}\quad 85 &{}\quad 85 &{}\quad 85 &{}\quad 90 &{}\quad 85.83 \\ 6 &{}\quad 1.5 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \end{array} \right) \end{aligned}$$

Therefore, our database is modeled like: $FP= {P_1, P_2, \ldots P_n}$ with n the number of points recorded. In localization phase using PSO, particles are initialized with fingerprinted points locations and each particle evaluates the fitness function modeled as the Root Mean Square Error (RMSE) following Eq. 13:

$$\begin{aligned} f=\sqrt{\frac{1}{N} \sum \nolimits _{i=1}^{N} (\hat{x}_i - x_i)^2} \end{aligned}$$

(13)

where $N=5$, is the number of access points, $\hat{x}_i$ is the RSS value of access point $i$ for current particles location and $x_i$ is a corresponding RSS received from a mobile device. All parameters used for PSO are set in Table 1.

Table 1 PSO parameters

Where $NbrPrt$ is the number of particles and $NbrPrtNeigh$ is the number of the particles in each neighborhood.

If the particles location is not recorded, the Kriging mechanism is used to interpolate it using the five closest recorded points values. As the kriging method requires a semivariogram model, we studied our database distribution using Eq. 7 and found that it can fit with the exponential model with $a=0, s=27.24$ and $r=6.48$, on one hand (Fig. 5).

Fig. 5

Empirical versus exponential variogram fit

On the other hand, the signal strength can be modeled theoretically as follows [23]:

$$\begin{aligned} RSS (dBm) = A-10 \times n \times \log _{10} (d) \end{aligned}$$

(14)

We empirically found that $A=-40\,\hbox {dB}$ and $n=1.2$ model well our database distribution. In fact, as shown in Table 2, RSS measurements from an access point at different distances have been made and for each distance the RSS variation during 10 s was recorded with their average.

Table 2 RSS variation according to the range

From Eq. 14, values in Table 3 were generated by varying the value of $n$.

Table 3 Theoretical variation of n

Figure 6 encompasses data from Tables 2 and 3 and illustrates the variation and the suitable value of $n$.

Fig. 6

Theoretical and empirical variation of n

Hence, the Eq. 14 becomes as follows:

$$\begin{aligned} RSS (dBm) = -40-12 \times n \times \log _10 (d) \end{aligned}$$

(15)

Therefore we used the dynamic part of the Eq. 15 to fit the semivariogram and the Eq. 16 becomes:

$$\begin{aligned} K' = \left[ s - 6 \times \log _{10} (d(X_i, X_j)) \times \lambda (d(X_i, X_j))\right] _{ij}, \end{aligned}$$

(16)

$i=1 \dots n; j=1 \dots n$

Note that the values of $A$ and $n$ are specific to our experiments; in other words, these values depend on the environment and have to be calculated.

5 Results and Discussion

As our approach includes PSO that works with random values, tests have been performed three times and the results are reported in Table 4.

Table 4 Test error collection

Table 4 shows the mean error values of our proposal in comparison with the fingerprinting mechanism using k-nearest neighbor as matching technique. The fingerprinting utilizes for each point of the grid the average of RSS values received during the 10 s of training phase. The test has been done on 12 point locations of the grid with other 12 non-recorded points so as to balance the efficiency of our proposal and all those locations cover the whole experimental room. The overall mean error for our approach is about 0.9069 against 1.4240 for fingerprinting.

Moreover, the accuracy evaluation of our approach has been extended to comparison of its mean error values with those obtained in other related works as illustrated in Table 5. We notice that our approach outperforms all fingerprinting based mechanisms for indoor localization.

Table 5 Mean error values of localization mechanisms

6 Paper Contribution

Our approach aims firstly to increase the indoor localization accuracy so that a mobile node in a fingerprinted room can be localized with a minimum error value. Secondly, in some proposed fingerprinting localization methods, the mobile node has to stop moving for a given time, the time used in offline phase to collect signal strength from all access points in range. However, our proposal is instantaneous and the mobile node can still moving while receiving and sending RSS what is suitable to an unaware subject during the localization phase: the localization algorithm is running in background. In a real case, a patient equipped with a sensor does not need to know when it is sensing, receiving or sending data. Finally, the interpolation method (kriging) avoid to build a huge fingerprinting database and helps estimate the RSSs in a non-fingerprinted point. But, the more the fingerprinted points are close each other, the higher the localization accuracy will be.

7 Conclusion and Future work

In this paper we proposed a new approach for indoor WBAN localization regarding to the case of a single person. A related centralized algorithm has been proposed intending to overcome the energy consumption issue. Our proposed approach shows good performances relating to localization accuracy and the use of kriging method reduces the memory space consumption. In future, we forecast to extend it so that it can be applied to a group of WBANs such as in retirement home where elders need to be assisted. Furthermore, we plan to set up a cooperative mechanism between WBAN coordinators.