Keywords

1 Introduction

The recent decade witnesses a high demand for Location Based Services (LBS) in outdoor environments as well as indoor environments. LBS can be involved in several and critical systems in our daily life such as: Emergency services, healthcare, retailing, manufacturing, logistics and many other industries. Indoor positioning systems (IPS) gained in importance after the Global Positioning System (GPS) fails in determining a location accurately inside buildings (known as indoor environments) because the GPS receiver could not be in line-of-sight with the satellites. A lot of researches have been conducted to find other techniques to enable the LBS to provide its services in a closed environment. Although Wireless Local Area Network (WLAN) technology is a valuable technology to be used for IPS due to its low cost and simple configuration, achieving high accuracy still needs more investigation because the WLAN’s has two main weaknesses. These weaknesses are multipath influenced by presence of obstacles and signal strength fluctuation during the day time [1, 2].

This research presents new adapted WLAN-based IPS model and this model is able to estimate the location of mobile device in dynamic environment accurately, and this paper organized as follows: Sect. 1 presents a brief background which covers the Fingerprinting method and the path loss model. Section 2 discusses some of the related work, while in Sect. 3 the proposed model is introduced. Section 4 presents and discusses the experimental results followed by a conclusion and suggestions for future work.

2 Background

Location System, Geolocation System, Positioning System, and Localization System are alternative expressions to the same system [2–4]. This system has the ability to determine the current position/location of a specific object, mobile device, in a specific environment.

The need for positioning system is not new. Historically the ancient people built their own positioning system for navigation and the old positioning systems mainly depend on the location of the stars. The astronomical tables give the location of specific stars in the sky throughout the year. People in the recent days also have the same need as the ancient people but for many purposes beside navigation purpose.

The Global Positioning System (GPS) is a satellite navigation system that is able to provide the location of the GPS receiver device as tuple of Longitude and Latitude. The GPS receiver must be in line-of-sight with the satellite. The GPS was developed in 1973 for military use, but it has been allowed freely for civilian use but with a degraded performance [5]. Widespread use of the GPS shows that LBS has become a significant part of people’s daily life [4]. LBS can be defined as services that integrate the mobile user’s location with other information in order to provide valuable information to the user [6]. These services vary according to the characteristics of its targeted users such as; Military to track/determine target location; Civil defense to determine the appeal location; Marketing to help possible customers; Healthcare to find the current location of a doctor for emergency cases; and in Management to follow up the employee’s location or location of objects.

2.1 Indoor Positioning Methods and Techniques

After the failure of GPS in determining the location in the indoor environments, a lot of researches have been conducted to find other methods or techniques to enable LBS systems to provide its services in such an environment. These methods can be divided into three general categories [2, 3, 7–9]: Proximity; Triangulation; and Scene Analysis. Figure 1 gives a clearer and closer view of the WLAN-based indoor localization techniques.

Fig. 1.
figure 1

WLAN-based localization techniques

Full size image

Proximity. Proximity is also known as connectivity based. The position of mobile device is determined by the coverage area of the transmitter (access point in WLAN case) – it is fixed in a known position and has limited range [2, 8]. The proximity method has a wide range of distance errors.

Triangulation. Triangulation method uses the triangles’ geometric properties of the radio frequency to locate the current location of the mobile device. It has two approaches: distance-based and direction-based. The distance-based (Lateration) approach converts the measurement of the propagation-time of the received signal into distance to estimate the mobile device location, as shown in Fig. 2 Triangulation Techniques: (a) Lateration (b) Angulation, where the Time of Arrival (ToA) has been used in [10] and the Round Trip Time (RTT) has been used in [3]; or based on converting the measurement of the receive signal strength (RSS) into distance such as in [11, 12]. On the other hand, the direction-based (angulation) approach estimates the location based on the angle of the received signal [2, 8] as shown in Fig. 2 Triangulation Techniques: (a) Lateration (b) Angulation.

Fig. 2.
figure 2

Triangulation Techniques: (a) Lateration (b) Angulation

Full size image

Triangulation became a very rich research area since the radio frequency has a wide range of technologies such as: Radio Frequency Identification (RFID); Infrared Radiation (IR); Ultra Wide Band (UWB); Wireless LAN (WLAN); Ultrasound; and Bluetooth. The efficiency of these radio technologies have been examined, and the performance of these technologies have been measured by many metrics such as: Accuracy (location error), and Cost [2–4, 8, 9]. These researches show that WLAN can provide highly accurate results with minimal cost because this technology is already used in most of the companies and institutions.

Scene Analysis. Scene analysis has an alternative name like Radio Frequency (RF) analysis or Fingerprinting. It uses the pattern recognition techniques which combines RF with location information, e.g. coordinates or label, from the environment to obtain the real position of a mobile device. Scene analysis techniques include topological analyses, or advanced techniques such as hierarchical fuzzy inference algorithms [2, 8]. However fingerprinting is the most accurate method, its accuracy declines when an environmental change occurs [2, 3, 7]. Fingerprinting will be explained in the next section.

2.2 Fingerprinting

Fingerprinting method can be defined as “Location fingerprinting which refers to techniques that match the fingerprint of some characteristic of a signal that is location dependent” [3]. Fingerprinting takes its place as the most famous method for IPS because it can provide accurate localization result, with some level of variation according to the used algorithm. Figure 3 shows the Fingerprinting method’s scheme and process flow.

Fig. 3.
figure 3

Fingerprinting method’s scheme

Full size image

Fingerprinting Offline Phase. The offline phase is considered as the initialization phase. In this phase each site location (L i ) in the desired environment will be surveyed to measure the RSS for all the available access points – APs- \( (S_{i} ) \).

The location coordinates (or label) and its respective measured APs’ RSS values will be used to create the site’s radio map (RM) instances.

$$ S_{i} = \left\{ {rss_{i1} , rss_{i2} , \ldots , rss_{in} } \right\} $$
(1)

where rss ij refers to the signal strength of access point A j in the location L i . This means that the radio map can be expressed as:

$$ RM = \{ T_{1} ,T_{2} , \ldots ,T_{m} \} $$
(2)

where T i is a tuple of (S i , L i ) and m is the number of instances in the \( RM \).

Fingerprinting Online Phase. The online phase is also known as run-time or positioning phase. In this phase the current location (L c ) of a mobile device, laptop or smartphone, is required to be determined based on the current measurement set of RSS (S c ).

$$ S_{c} = \left\{ {rss_{c1} , rss_{c2} , \ldots , rss_{cn} } \right\} $$
(3)

The process is done by searching the \( {\text{RM}} \) for the best matching of the signal strength part (Si) of the stored tuples (Si, Li). The matching process can be performed by searching for the most similar signal pattern in RM, Euclidian Distance (4) used to measure the similarity between two patterns. The less distance is the most similar pattern and vice versa.

$$ d_{ci} (S_{c} , S_{i} ) = \sqrt[2]{{\mathop \sum \limits_{j = 1}^{n} \left( { S_{cj} - S_{ij} } \right)^{2} }} $$
(4)

where d ci is the distance between two RSS sets \( S_{c}\ {\text{and}}\ S_{i} \).

The location coordinates or label (L c ) of the selected RM’s instance, with the minimum Euclidian Distance, will be considered as the current location coordinates or label of that mobile device.

$$ L_{c} (d_{ci} ) = arg min\left\{ { d_{ci} \left( {S_{c} , S_{i} } \right) \forall S_{i} \in RM} \right\} \} $$
(5)

Fingerprint Drawbacks. Although fingerprinting is the most valuable IPS’ method due to its accurate location detection, its accuracy level dramatically decline in the case of environmental change occurrence [2, 3, 7, 9]. That change means the RM, bulky and time consuming process in offline phase, become outdated and it must be recreated again to include the effects of that environmental change in the scene analysis. The environmental change can be; adding/moving furniture, add/removing partition, adding/removing access points, and environmental expanding horizontally/ vertically.

Fingerprint’s Matching Algorithms. There are two different approaches of algorithms which can be used to search for the best fingerprint matching; Deterministic and Probabilistic [2–4, 8, 9]. The probabilistic approach uses probability methods, such as Naïve Bayesian, to compute the probability characteristics of the RM instances to find the best match fingerprint to determine the current location of the mobile device. A lot of researches have been conducted in this area such as [13, 14]. On the other hand, the deterministic approach used scalar values such, as the mean and non-probabilistic methods to estimate the current location of the mobile device. A lot of researchers used K-Nearest-Neighbor (KNN) [15]; Artificial Neural Networks (NN) [16–18]; and Support Vector Machine (SVM) [17, 18], to estimate the current location of the mobile device as a deterministic method [7, 19, 20]. The deterministic approach is well established and has less computational cost since it does not require big RM as the probabilistic approach [21].

KNN is a simple and powerful classifier, widely used in indoor localization systems based on fingerprinting approach due to its high localization accuracy [15, 16, 22]. NN-based IPS is a high non-linear mapping between S i and L i . However NN-based IPS is limited by its slow convergence and easy trapping into local minimum. In addition, the NN model will fail when an environmental change occurs [23, 24]. In this research paper KNN and NN have been used in order to examine the accuracy of the proposed model.

2.3 WLAN Signal Propagation Path Loss Models

In order to get an accurate localization result, the predicted fingerprints must be as close to the real RSS values as possible. Goldsmith A. in [25] classifies the propagation models into two classes: deterministic and empirical. The prior one considers high complexity approach and it needs very precise information about the environment [7]. The first deterministic model was proposed by Hae-Won, S. and Noh-Hoon, M. [26] in 1999, but the most known deterministic model was proposed by Athanasiadou, G.E. et al. [27] in 2000.

On the other hand the first empirical path loss model appeared at the end of 1980 s [28]. A lot of researches have been conducted to enhance the RSS prediction in the empirical model such as [28–35]. Mardeni, R. and Solahuddin, Y. in [28] define the empirical path loss model as the experimental mathematical formulation which predicts radio wave propagation based on limited but essential parameters such as frequency, path loss exponent, distance, and physical blockings. Due to its lower computational cost and simple to design [7], the empirical study was selected to be our RSS prediction model. In the next section the most valuable four path loss propagation models will be provided.

One-Slope Model. One-slope model (OSM) [35] (1992) is the most commonly used path loss model, the RSS value decreases exponentially with the distance d, distance in meter, between the transceivers.

$$ PL(d) = PL(d_{0} ) + 10n\;\log \left( {\frac{d}{{d_{0} }}} \right) $$
(6)

where the PL(d 0) is the free space propagation loss at reference distance\( d_{0} \), typically 1 meter, and n is the slope factor (power decay index) which becomes 2 for free space and 6.5 for obstructed space [33, 35]. The term free space means that the receiver can be in line-of-sight (LOS) with the transmitter.

Log-Normal Shadowing Model. The Log-Normal Shadowing Model is an extension of the One-Slope Model proposed in [35] (1992). Here, the effects of random shadowing due to varying levels of clutters are taken into account. The average path loss between a transmitter and its receiver is expressed as Eq. (7)

$$ PL(d) = PL(d_{0} ) + 10n\;\log \left( {\frac{d}{{d_{0} }}} \right) + X $$
(7)

where X is a zero-mean Gaussian distributed random variable proposed by Seidel, S.Y. and T.S. Rappaport in [35], to replace all the possible attenuation factors. However, using zero-mean random variable will make a big difference between the RSS values; thus, more attention for the attenuation factors will bring more systematic RSS prediction.

Multi-Wall Model. In addition of the free space path loss, Multi-Wall Model (MWM) [33] (2001) considers the penetration parameters such as the wall and floor attenuation factors Eq. (8).

$$ PL(d) = PL(d_{0} ) + 10n\;\log \left( {\frac{d}{{d_{0} }}} \right) + \mathop \sum \limits_{i = 1}^{I} \mathop \sum \limits_{k = 1}^{{k_{wi} }} L_{wik} + \mathop \sum \limits_{j = 1}^{J} \mathop \sum \limits_{k = 1}^{{k_{fj} }} L_{fjk} $$
(8)

where L wik is considered the attenuation factor of all types of wall and L fik is the attenuation factor of all types of floors, and I and J are the number of wall types and the number of floor respectively.

As evolution of MWM, COST231 MWM assumes that all walls have the same properties such as the material and thickness and the entire floor also have the same properties, Eq. (9).

$$ PL(d) = PL(d_{0} ) + 10n\;\log \left( {\frac{d}{{d_{0} }}} \right) + \mathop \sum \nolimits WAF + \mathop \sum \nolimits FAF $$
(9)

where WAF and FAF represent the wall attenuation factor and the floor attenuation factor respectively.

A combination between the MWM [33] and the zero-mean Gaussian distributed random variable, proposed in [35], will be used in this work as in the following equation Eq. (10):

$$ PL(d) = PL(d_{0} ) + 10n\;\log \left( {\frac{d}{{d_{0} }}} \right) + \mathop \sum \nolimits WAF + X $$
(10)

3 Related Works

A lot of researches have been conducted in order to overcome the environmental change occurrence; these researches can be divided into two based on their approaches. The first approach uses extra hardware such as feedback devices or sensors, example of this approach can be found in [36–41]. On the other hand the second approach tries to use the signal propagation path loss model and such researches can be found in [22, 42–46]. This research falls under the second approach so the later related work will be discussed briefly in this section.

In 2000, Microsoft’s researchers, Bahl, P. and Padmanabhan, N., proposed RADAR [22]. RADAR is considered the base of the WLAN fingerprinting IPS. RADAR operates by applying the basic concept of fingerprinting methods. It records and processes the WLAN’ RSS of a UTP broadcast message from a mobile user collected by three fixed position stations, to determine the mobile user’s location. RADAR also combines the RSS empirical measurements with signal propagation modeling Eq. (11), to fill the missing cells in the offline fingerprint measurement to provide more accurate localization.

$$ PL(d) = PL(d_{0} ) + 10n\;\log \left( d \right) + \left\{ {\begin{array}{*{20}c} {nw*WAF\quad \quad nw < C} \\ {C*WAF\quad \quad nw \ge C} \\ \end{array} } \right. $$
(11)

where n indicates the rate at which the path loss increases with distance, PL(d) is the signal power at some reference distance d 0 and d is the transmitter-receiver (T-R) separation distance. C is the maximum number of obstructions (walls) up to which the attenuation factor makes a difference, nw is the number of obstructions (walls) between the transmitter and the receiver, and WAF is the wall attenuation factor. RADAR’s experimental testbed is a floor of an area of 980 m2, and includes more than 50 rooms. The experimental result shows the validity of using the WLAN’s signals in the indoor positioning systems with distance error between 2 m to 3 m. However, from our point of view RADAR has some defect; the first one, it works on determining the mobile user location at the room level. That means the distance error measurement is not consistent with experimental testbed since the distance error relays the average of the distance differences by meter and the location unit here is 3 m2, which is the room size in the experimental testbed; the second one, RADAR builds an offline fingerprint database which become outdated database because the RSS can fluctuate and environment change may occur; the last one, it uses signal propagation model to fill the missed RSS reading in the offline fingerprint database. It means if RSS value is constant in a specific point x on distance d, while in reality measuring the RSS value in a specific point x on distance d many times will show different values each time.

Liu et al. [43], in 2011, provided IPS based on combining the fingerprinting method and path loss models for multi floor environment, because most of the WLAN-based IPS did not consider the multi floor environment. Selected samples per floor have been selected to create the radio map and in the online phase the floor number is localized based on searching the radio map. After determining the floor, the mobile device location is determined by triangulation methods based on the APs location, estimated by the path loss model in Eq. (12).

$$ PL(d) = PL(d_{0} ) + 10n\;\log \left( d \right) + OAF $$
(12)

where OAF is all the obstacles which include walls and partitioning plates. The experimental result of the proposed solution shows that the floor positioning is highly accurate close to 100% and point localization precision is close to 1.6 m, with 5 m distance between each point. Although a high accurate result is important in floor positioning, in any fingerprinting systems the main drawback is that a database is usually required to rebuild for accurate localization if environmental change occurred.

In 2013, Narzullaev, A. et al. [44], proposed algorithm to handle the extensive and time-consuming RSS calibration process in designing the radio map for the indoor localization systems. The proposed algorithm combines the concept of the reference point (feedback point) and the one-slope- model (OSM), Eq. (12), pass loss signal prediction model (8) to get time-efficient calibration process. It starts by calibrating the RSS of the available APs by the feedback points, then it estimates the location of the APs with the strongest RSS based on the distance between the prediction point and it closes the feedback point where the RSS can be predicted by using OSM. However, the experiment results show the efficiency of the proposed algorithm in reducing the RSS calibration time without reducing the location prediction accuracy. From the author point of view, the proposed solution has few drawbacks. Firstly, it increases the cost of indoor positioning system by using a feedback point. Secondly, the algorithm increases the computational complexity by searching for the strongest APs and determining its locations. Thirdly, it uses the OSM model which assumes ideal wireless media which will not fluctuate nor attenuate due to many known and unknown reasons.

4 The Proposed Model

The proposed model consists of two modules the Room Localizer (RLOC) and Environment Descriptor (EDEC). RLOC is considered the main part of the model because its task is to determine the current location of the mobile device. RLOC contains the Radio Map Generator (RMG) and the Location Detector (LD). EDEC is a simple information store, this information describes the environment’s layout and the used access points and its locations as shown in Fig. 4. RMG work is based on the information on EDEC to create RM and then the LD will be invoked to determine the mobile device location based on the generated RM. The RSS value will be computed based on Eq. (20).

Fig. 4.
figure 4

Environment description

Full size image

In case of NN usage it will be built and trained based on the created RM. The architecture of the NN will be n input neurons, (2n + 1) hidden neurons, and 1 output neuron. And in case of KNN usage the nearest five neighbors will be considered. In the positioning stage, RLOC will get the RSS tuple from the mobile device and pass this tuple to the LD model to provide room label as the current location of the mobile device.

5 Experiments & Result Discussion

5.1 Determining Test-Bed Environment

The eastern side on the third floor of the Menara Razak building, Universiti Teknolgi Malaysia (UTM) Kuala Lumpur, has been selected as testbed environment. This testbed has been gridded into 1 m x 1 m cell size as shown in Fig. 5. The dimension of the selected area is 370 m2, and this area contains blocked area which means that there are around 300 different points are available for calibrations.

Fig. 5.
figure 5

Gridding the selected environment

Full size image

5.2 Manual Radio Map (RM) Creation

In order to calibrate the RSS values from the existing three CSICO WAP4410 N APs, WifiScanner application has been developed in two different platforms; Android OS 4.2 and MS Windows. WifiScanner has been configured to capture one WLAN beacon frame per second, and for each point in the environment grid it configured to capture ten different beacon frames. After fixing the APs locations, two rounds of the RSS collection have been conducted, and about ten hours were spent for each round. In order to create RM, each point is represented by the mean value of its RSS values and labeled by the point coordinate and the room number is then stored in CSV file. The final RM size is 1070 instances. This RM will be used in two different tasks: firstly to examine the accuracy for fingerprinting algorithms such as KNN and NN; secondly to use it as testing set in order to evaluate the proposed adaptive model.

5.3 Examining the Accuracy of Fingerprinting Algorithms

This experiment has been conducted in order to compare the accuracy, for room level, of the KNN and the NN. The calibrated RM, 1070 instances, has been used in this experiment and it has been partitioned into 70% and 30% as training set and testing set respectively. The accuracy of the KNN by counting the majority of 5 neighbors was 93%, on the second hand the architecture of NN, with 3 input neurons; 7 hidden neurons; and 1 output neurons, achieved 94% as a regression value and 80% as accuracy. The number of hidden neurons in NN has been selected firstly to be double the input neurons, and then the approach of trial and error showed that 7 hidden neurons is the best one. Table 1 summarized this experiment.

Table 1. KNN & NN accuracy based the structure
Full size table

The results came in this manner due to the small difference in RSS in each point, so that NN shows high regression between the input and the output but with high 0.2 as MSE. On the other hand KNN can distinguish between these too closed RSS values by simple technique as Euclidian Distance. Hence, KNN will be adopted as localization algorithm for the proposed model.

5.4 Predicted Radio Map for Indoor Positioning

This experiment has been conducted to prove the efficiency of the predicted radio map in the indoor positioning process. In this experiment the MWM path loss model and the shadowing zero-mean random variable, Eq. (10), will be adopted to build the radio map for the selected testbed environment as shown in Fig. 6. In order to generate an accurate dynamic RM based on the adopted model, the different parameters of the model must be determined carefully. Different experiment has been conducted to determine the proper value of these parameters as follow: Firstly, the distance (d) determined based on the APs in EDEC. Secondly, the path loss at 1 m distance PL(d 0) has been found experimentally equals to -34 dBm for the used APs. Thirdly, the power decay index (n) has been determined to equal -2.1 dBm because the selected environment is simple structure environment. Fourthly, the wall attenuation (WAF) factor equals to -2 dBm as measured in [3333], as it has been proven experimentally. - Finally, random shadowing factor (X) is a random integer in [-3, 3].

Fig. 6.
figure 6

Site radio map grid

Full size image

In order to examine the efficiency of the proposed adapted model KNN algorithm, with K=5, has been used to estimate the room label for testing set based. The testing set consists of 34 in from the calibrated RM where as stars shown in Fig. 6, these points represent the rooms’ centers and the main corridor. The selected testing set consists of 986 instances. Then the mean RSS value of each point has been computed to produce a more reliable testing set with 34 instances. The experimental result shows high localization accuracy as shown in Table 2. This high accuracy occurs due to the accurate determination of the adopted path loss model parameters.

Table 2. Whole testing set vs averaged testing set
Full size table

6 Conclusion

The last few years showed a sharp increase in the mobile phone market and as a result there is a sharp growth in the demand for pervasive computing in indoor environment to achieve the benefits of the Location Based Services (LBS). Based on the mobile user location, LBS can provide different types of services such as tracking or navigation in important areas such as Healthcare; Civil defense; Marketing; and Management. Currently, WLAN technology is considered as one of the best choices for indoor positioning for many reasons such as low cost, simple infrastructure and high accuracy. Although the WLAN fingerprinting method is the most accurate positioning method its accuracy declines sharply when environmental change occurs. In addition recalibrating the fingerprinting Radio Map is a time consuming process. This paper provides a novel adapted indoor positioning model which is able to adapt the RM using the path loss signal propagation models to overcome the effects of the occurrence of environmental changes. The experimental results show that the proposed adapted model is highly efficient in solving the mentioned problem in dynamically changing environments.