RSS-Fingerprint Dimensionality Reduction for Multiple Service Set Identifier-Based Indoor Positioning Systems

Abstract

Indoor positioning systems (IPS) have been recently adopted by many researchers for their broad applications in various Internet of Things (IoT) fields such as logistics, health, construction industries, and security. Received Signal Strength (RSS)-based fingerprinting approaches have been widely used for positioning inside buildings because they have a distinct advantage of low cost over other indoor positioning techniques. The signal power RSS is a function of the distance between the Mobile System (MS) and Access Point (AP), which varies due to the multipath propagation phenomenon and human body blockage. Furthermore, fingerprinting approaches have several disadvantages such as labor cost, diversity (in signals and environment), and computational cost. Eliminating redundancy by ruling out non-informative APs not only reduces the computation time, but also improves the performance of IPS. In this article, we propose a dimensionality reduction technique in a multiple service set identifier-based indoor positioning system with Multiple Service Set Identifiers (MSSIDs), which means that each AP can be configured to transmit N signals instead of one signal, to serve different kinds of clients simultaneously. Therefore, we investigated various kinds of approaches for the selection of informative APs such as spatial variance, strongest APs, and random selection. These approaches were tested using two clustering techniques including K-means and Fuzzy C-means. Performance evaluation was focused on two elements, the number of informative APs versus the accuracy of the proposed system. To assess the proposed system, real data was acquired from within the College of Engineering and Applied Sciences (CEAS) at the Western Michigan University (WMU) building. The results exhibit the superiority of fused Multiple Service Set Identifiers (MSSID) performance over the single SSID. Moreover, the results report that the proposed system achieves a positioning accuracy <0.85 m over 3000 m², with an accumulative density function (CDF) of 88% with a distance error of 2 m.

1. Introduction

A precise real-time indoor positioning system has recently attracted considerable attention from researchers due to location-aware services, which include patient location monitoring, mobile advertising, tag tracking, and robot guiding [1,2,3,4,5]. Unlike Global Positioning Systems (GPS), that require line of sight (LOS) transmission paths, indoor positioning faces many challenges due to changeable radio propagation environments inside the buildings [6]. Due to walls, celling, movement of people or furniture, and obstacles inside the buildings, indoor radio propagation is affected by multipath fading, shadowing, and delay distortion [7]. In addition to high-accuracy requirements, indoor position systems should also estimate the position of an object quickly with a light algorithm and low computational cost.

Many indoor positioning techniques have been promoted such as Wireless local Area Network (WLAN), Ultrasound, Lighting, Radio Frequency Identification (RFID), and Bluetooth. WLAN-based indoor positioning systems have been widely employed for IPS without additional cost because WLAN infrastructures are necessary in large buildings like airports, hospitals, universities, and museums. Positioning based on RSS can be divided into two models: signal propagation models, and fingerprint-based location models. The requirements of the first model for indoor propagation loss is relatively high, so this article focuses on the second model. Although the second model has been relatively mature, the WLAN-based fingerprinting technique can be considered as an important technique used to estimate the position of a target.

In general, fingerprinting-based positioning involves two phases: an offline and an online phase [8]. In the offline phase, the area of interest is divided into grid points, which are called reference points (RPs). Each RP_i is labeled by Cartesian coordinates (x_i,y_i). The MS at each RP_i collects the RSS readings from various APs, which are deployed in the Area of Interest (AOI). In the online phase, the MS records the RSS vector at an unknown location and pre-matches with the stored RM to determine the closest RPs to the MS by using Euclidian distance, which is the simplest method to estimate the position of MS.

Fortunately, Wi-Fi users are able to measure the RSS from various APs, which are deployed in the AOI. Therefore, location fingerprints are typically vectors of RSS of different APs, and the length of such vectors can be grown to include all the detectable APs in the AOI. Unfortunately, not all these APs can contribute positively to positioning, the majority of them are redundant. Therefore, including all these APs in the RSS vector results in superfluous computational costs, and in some cases, causes a deterioration in the accuracy [9]. Recently, most APs that are deployed in large buildings, use Multiple Service Set Identifier configurations, which means that each AP is configured to transmit N signals instead of one signal. MSSID is used in most buildings to advertise different WLANs where each WLAN has a different class of clients, and each class requires different keys, firewalls, privacy, and speeds [10]. This technique leads to increasing redundancy in the calculation process and a decrease in the accuracy of systems when each SSID is considered as a single AP [11].

In addition to the redundancy of APs, the accuracy of fingerprinting-based techniques is severely affected by the multipath issue and radio interference. Therefore, it is very important for any IPS designer to know the statistical properties of RSSI signals. Fluctuation in RSS signals due to the multipath phenomenon is an inherent issue in fingerprinting-based techniques. There are many solutions to mitigate the effect of a multipath issue in offline and online phases including the use of Kalman filter, averaging, and histograms [12,13,14]. The efforts in the online phase required many RSS time samples to be measured in the same position to reduce the effect of the multipath phenomenon. This kind of solution causes IPS to be slow and as such, is not appropriate for the tracking process.

The main contributions of this article include: (1) Study the characteristics of Multiple SSID signals in 2.4 GHz, which can be configured on the same AP. (2) Propose a new algorithm based on MSSIDs to reduce the effect of multi-path issues by fusing MSSIDs signals, and computational costs by selecting informative APs. (3) Study the effect of informative AP numbers in K-means and Fuzzy C-means clustering technique. (4) Compare the proposed system performance with state-of-the-art methods.

The rest of this article is arranged as follows: the related works are reviewed in Section 2. The fingerprinting technique is illustrated in Section 3. MSSID and the characteristics of MSSID signals are described in Section 4. The proposed system and measurement setup technique are illustrated in Section 5 and Section 6, respectively. Section 7 shows the results and the discussion. In Section 8, the conclusion and future work are discussed.

2. Related Work

In the literature of indoor positioning, there are various taxonomies. However, there is a common classification, which falls into two separate categories: Radio Frequency (RF)-based techniques, and non-RF-based techniques, which use another kind of sensors. WLAN, RFID, and Bluetooth are among the RF-based techniques. Audio, visual, ultra-sonic, Infra-Red (IR), laser sensors, and magnetic field are considered as non-RF-based methods [15,16,17,18]. In this article, we mainly focus on RF-based techniques.

Table 1. RF Position Techniques [19].

Technique	Advantage	Disadvantage
Cell of origin	Base stations are available and never move	Highly inaccurate
AoA	High accuracy	Requires additional hardware
ADoA	High accuracy	Requires additional hardware
ToA	High accuracy	Requires additional hardware synchronization issue
TDoA	High accuracy	Requires additional hardware synchronization issues
Fingerprinting- based location	High accuracy	Computational and labor costs

reports the main RF techniques that are utilized in indoor positioning.

Recently, many types of research have mainly focused on Wi-Fi fingerprint-based IPS challenges, such as collecting fingerprinting signals and how these signals are processed through IPS techniques [19]. Dimensionality reduction is also an important challenge and has been studied through different techniques.

Generally, there is a tradeoff between dimensionality reduction and the accuracy of classifiers [20]. In the online phase, the reduction of computational costs for Wi-Fi fingerprint-based IPS is very crucial in a real-time tracking system because large data require a long time to be processed. The roaming of a MS inside the building makes IPS unable to track the MS’s location inside the building. Therefore, working on designing a light algorithm with low computational cost makes IPS more feasible. In this section, we review key techniques for positioning, which are used in dimensionality reduction.

Fang et al. [21] proposed a new approach for a Wi-Fi-based location fingerprinting system. The proposed method transforms RSS signals into Principal Components (PCs) intelligently, such that the effect of all APs is considered. Instead of the selection of APs, the proposed technique replaces the RSS of APs by a subset of PCs to improve accuracy and reduce the computational cost as well. To evaluate the proposed system, a realistic WLAN environment was chosen to conduct the experimental work. The results exhibit that the mean distance error was eliminated by 33.75% and the complexity by 40%, as compared to traditional approaches.

Li et al. [22] proposed a novel technique for a WLAN-based location fingerprinting system. In the offline phase, the AOI was clustered into sub regions by fuzzy C-means and then the useful APs were selected to minimize the dimension of the fingerprint. In the online phase, the proposed system used a NN (Nearest Neighbor) method to choose subareas and to compute the coordinate of the target location by using relative distance fuzzy localization (RDFL) algorithms. The results showed the ability of the proposed system to reduce calculation time and improve positioning accuracy.

Jiang et al. [23] implemented a WLAN- fingerprinting-based localization method, which is based on selecting the important APs. The APs with the strongest RSS power were selected as the informative APs. The results showed that the proposed system exhibits superior performance as compared with traditional techniques.

Abusara et al. [24] modified a method, called Fast Orthogonal Search (FOS) method, to determine the singularity of RSS values, which are measured from various APs at each location point. In order to evaluate the modified FOS method, two important factors were taken into consideration, the amount of reduction, and the accuracy of IPS. The results with real RSS values measurement show that the modified FOS performance is better than the traditional FOS implementation.

Chen et al. [25] presented a novel algorithm, which is called a clustering and Decision Tree-based method (CaDet) for intelligent selection of APs in indoor positioning. CaDet is a union of information theory, clustering analysis, and a decision tree algorithm. By using machine-learning techniques, the results showed that CaDet is capable of selecting an informative small combination of APs to detect the user’s location with high accuracy, as compared with traditional techniques.

Kanaris et al. [26] proposed a novel technique for indoor localization based on the cooperation between IEEE802.11 infrastructure and Bluetooth Low Energy (BLE). BLE is used to confine the location of the user within a specific subarea that means coarse localization. A new K-Nearest Neighbors (K-NN) algorithm is utilized to estimate the final user’s location. Due to the use of a fragment of the initial fingerprint dataset, the results exhibit that the proposed system achieves fast positioning estimation and improves the accuracy of the proposed system as well.

Feng et al. [27] implemented a novel approach based on compressive sensing (CS) theory and selection APs to obtain high accuracy. The theory of CS is applicable for accurate IPS using RSS-based fingerprinting due to the location sparse nature on the map. There are two stages for finding the location of a user. The first stage is achieved by an Affinity propagation clustering method to reduce the computational cost and increase accuracy as well. In the second stage, fine positioning is applied by using the compressive sensing theory. Random and strongest APs selection were used in this article. The results show that the proposed system leads to robust enhancement in positioning accuracy and complexity over traditional fingerprinting techniques.

Sanchez et al. [28] proposed an indoor localization methodology based on data fusion and feature transformation. The methodology is formed by four phases: dataset building, feature fusion, feature transformation, and classification. Dataset consists of RSS from Wi-Fi AP, orientation from a compass, and simulated RSS from simulated Light Emitting Diode (LED) lamps. Principal Component is used to reduce dataset dimensionality and improve computational performance of system. The results exhibit that the proposed system considerably reduces overall computational cost and provides an acceptable location accuracy.

Lopez et al. [29] proposed a refinement cycle for an indoor positioning system based on dimensionality reduction techniques. Several dimensionality reduction techniques have been utilized to different datasets such as Principal Component Analysis (PCA), Linear Discrimination Analysis (LDA), and t-Stochastic Neighbor Embedding (t-SNE). Two different visualization methods are defined to obtain graphical information about the quality of the radio map in terms of overlapping areas and outliers. The proposed system is evaluated by two kinds of data: dataset, which is measured by the research group, and standard data. In general, the results show that there are some useful configurations which can be used to perform the refinement process.

3. Fingerprinting-Based Technique

Because of the unavailability of appropriate radio signal propagation models for indoor environments, fingerprinting-based location techniques became popular with RADAR [30]. RADAR is the first fingerprinting-based positioning system, which was developed by Microsoft. Fingerprinting is a scene analysis method in which location in the environment is associated with a unique signal parameter. In this article, RSS of different APs, which are deployed for network services, is used as feature location. In general, the fingerprinting-based technique is divided into two methods: probabilistic and deterministic methods [31]. In this article, the deterministic method is utilized because it does not require many RSS measurements [32]. This technique is performed into two phases:

• Offline phase: During this phase, the area of interest (AOI) is partitioned into grid points which are called reference points (RP). Each RP is labeled on the map by Cartesian coordinates (x_i, y_i). The RSS of various APs are recorded for a specific time period (KT), where K is an integer number which represents the number of samples that are taken at each RP, and T is a time period to record the value of RSS at RP. The fingerprint, ${\overline{\phi }}_{i,j},$ of RP_j is generated by taking the average of the RSS signal values from APi for KT period where, ${\overline{\mathsf{\psi }}}_{i,j}=\frac{1}{K}{\sum }_{a=1}^K{\mathsf{\psi }}_{i,j}\left(aT\right) | a=1, 2,\dots \dots , K$. Therefore, the radio map (RM) of the AOI is created by cardinality of the fingerprints, as shown in Equation (1):

  $$\mathsf{\psi }=\left[\begin{array}{ccc}\begin{array}{cc}\begin{array}{c}{\mathsf{\psi }}_{1,1}\\ {\mathsf{\psi }}_{2,1,}\end{array}& \begin{array}{c}{\mathsf{\psi }}_{1,2}\\ {\mathsf{\psi }}_{2,2}\end{array}\end{array}& \cdots & \begin{array}{c}{\mathsf{\psi }}_{1, \mathrm{M}}\\ {\mathsf{\psi }}_{2,\mathrm{M}}\end{array}\\ ⋮& \ddots & ⋮\\ \begin{array}{cc}{\mathsf{\psi }}_{\mathrm{L},1}& {\mathsf{\psi }}_{\mathrm{L},2}\end{array}& \cdots & {\mathsf{\psi }}_{\mathrm{L}, \mathrm{M}}\end{array}\right]$$

  (1)

  where, L and M represent a number of APs, and a number of RPs in the AOI, respectively.

Althogh the fingerprinting-based technique is an easy method to implement, this method has many challeges that should be considered when it is done practically. Establishing a site survey RM is normally a labor-intensive task. However, there are many methods for enhancing the efficiency of the offline phase. These methods are based on Compressive Sensing (CS) theory [27,33,34] to reconstruct the RM from a small number of RSS measuremnets instead of survying the entire AOI. Also, a divesity of MS arises an an important challenge for IPS designers. Most of the existing research assumes that the collecting of fingerprints of a radio map and online measurements are achieved in the same device. Practically, this assumption is not true because the training device, which is used to build the radio map during the offline phase, may be different from the positioning device used during the online phase. These result in different signal strength patterns across the devices, which could degrade the accuracy of the positioning system [35]. Hence, the problem of signal pattern variation across diverse devices should be considered when designing positioning systems.

• Online phase: In this phase, the MS at unknown location records V = (RSS₁, RSS₂, … RSS_L) from different APs in the AOI. This vector V is pre-matched with a RM which is created in the offline phase to determine the MS’s location. Figure 1 shows the two phases which are used to estimate MS’s location. The Euclidean distance between V and all RP vectors in the RM utilized to determine the estimated position, as shown in Equation (2):

$$Dj=\Vert V-{\phi }_j\Vert$$

(2)

The signal distance vector, D_j, is sorted in ascending order. The first K RPs, which have the smallest signal distance, are selected to determine the position of MS, $\widehat{p}=\frac{1}{K}{\sum }_{i=1}^K{p}_i$, where $p_i$ represents the positions of K RPs. The reciprocal of distance, D_j, can be utilized as weights to determine the MS’s location. This method is called weighted-KNN, where the estimated position, $\widehat{p}$, is computed as shown in Equation (3):

$$\widehat{p}=\frac{{\sum }_{i=1}^K\frac{1}{Di}{p}_i}{{\sum }_{i=1}^K\frac{1}{Di}}$$

(3)

4. Multiple Services Set Identifier (MSSIDs) Technique

In the past, a number of separated APs were required to present a multiple services network in a specific area to deploy for Wi-Fi users. Each AP advertises single SSID on a specific frequency channel. The raising number of APs in a particular area leads to a channel congestion issue. As a result, the Wi-Fi service will be inefficient.

Recently, most of the APs are configured to work with MSSID and feature simultaneously, as shown in Figure 2. MSSID services advertise various SSIDs within one AP instead of a group of separated APs [10]. This configuration is commonly used to advertise various networks for various kinds of users, where each kind of user requires different settings to each SSID, such as firewall, key, bandwidth, privacy, and security. MSSIDs’ technique uses the same frequency channel. In order to avoid a collision or frame loss, MSSIDs utilizes a Clear Channel Assessment (CCA) protocol [36]. This protocol is used to investigate the channel state and whether it is used by another SSID. The channel is utilized by another SSID when the channel is clear. Therefore, the probability that all SSID signals are affected by the fading issue will be low [11]. In this article, we use this benefit to mitigate the variation of RSS signals by using a fusion approach for MSSIDs’ signals.

4.1. Mathematical Model of MSSID

This research aims to reduce the calculation cost of the MSSID-based indoor positioning system and increase the performance of IPS as well. Accordingly, N RMs (Ψ₁, Ψ₂, …, and Ψ_N) are generated as in Equations (4)–(6):

$${ \mathsf{\Psi }}_1=\left[\begin{array}{ccc}\begin{array}{cc}\begin{array}{c}{\mathrm{SSID}}_{1,1,1}\\ {\mathrm{SSID}}_{2,1,1}\end{array}& \begin{array}{c}{\mathrm{SSID}}_{1,2,1}\\ {\mathrm{SSID}}_{2,2,1}\end{array}\end{array}& \cdots & \begin{array}{c}{\mathrm{SSID}}_{1,\mathrm{M},1}\\ {\mathrm{SSID}}_{2,\mathrm{M},1}\end{array}\\ ⋮& \ddots & ⋮\\ \begin{array}{cc}{\mathrm{SSID}}_{\mathrm{L},1,1}& {\mathrm{SSID}}_{\mathrm{L},2,1}\end{array}& \cdots & {\mathrm{SSID}}_{\mathrm{L},\mathrm{M},1}\end{array}\right]$$

(4)

$${ \mathsf{\Psi }}_2=\left[\begin{array}{ccc}\begin{array}{cc}\begin{array}{c}{\mathrm{SSID}}_{1,1,2}\\ {\mathrm{SSID}}_{2,1,2}\end{array}& \begin{array}{c}{\mathrm{SSID}}_{1,2,2}\\ {\mathrm{SSID}}_{2,2,2}\end{array}\end{array}& \cdots & \begin{array}{c}{\mathrm{SSID}}_{1,\mathrm{M},2}\\ {\mathrm{SSID}}_{2,\mathrm{M},2}\end{array}\\ ⋮& \ddots & ⋮\\ \begin{array}{cc}{\mathrm{SSID}}_{\mathrm{L},1,2}& {\mathrm{SSID}}_{\mathrm{L},2,2}\end{array}& \cdots & {\mathrm{SSID}}_{\mathrm{L},\mathrm{M},2}\end{array}\right]$$

(5)

$${\mathsf{\Psi }}_{\mathrm{N}}=\left[\begin{array}{ccc}\begin{array}{cc}\begin{array}{c}{\mathrm{SSID}}_{1,1,\mathrm{N}}\\ {\mathrm{SSID}}_{2,1,\mathrm{N}}\end{array}& \begin{array}{c}{\mathrm{SSID}}_{1,2,\mathrm{N}}\\ {\mathrm{SSID}}_{2,2,\mathrm{N}}\end{array}\end{array}& \cdots & \begin{array}{c}{\mathrm{SSID}}_{1,\mathrm{M},\mathrm{N}}\\ {\mathrm{SSID}}_{2,\mathrm{M},\mathrm{N}}\end{array}\\ ⋮& \ddots & ⋮\\ \begin{array}{cc}{\mathrm{SSID}}_{\mathrm{L},1,\mathrm{N}}& {\mathrm{SSID}}_{\mathrm{L},2,\mathrm{N}}\end{array}& \cdots & {\mathrm{SSID}}_{\mathrm{L},\mathrm{M},\mathrm{N}}\end{array}\right]$$

(6)

where, L and M represent a number of deployed APs, and a number of RPs in the AOI, respectively.

4.2. Time Samples of MSSID

RSS-based fingerprinting approaches have been widely used for indoor positioning. The behavior of RSS signals plays an important role in determining the characteristics and nature of location fingerprints, which are recorded in RM. The RSS is a function of the distance between AP and the user who receives this signal, and it is mainly affected by the multi-path issue [37]. 5000 RSS samples were taken at a specific location from AP with 5 SSIDs under the line-of-sight condition. The behavior of MSSID RSS at a specific location is shown in Figure 3, where 5 SSIDs (SSID₁, SSID₂, …, SSID₅) are configured on the same AP. Figure 3 clearly shows the effect of the multi-path issue on these signals.

4.3. Time and Spatial Correlation Coefficients of MSSIDs’ Signals

The behavior of N SSIDs’ signals on the same physical AP is nearly identical to the deployment of N individual APs. In order to investigate the independency of these signals and the similarity over the AOI,

Table 2. The time correlation coefficient between MSSIDs’ signals at a certain point.

SSID	SSID1	SSID2	SSID3	SSID4
SSID2	0.021	-	-	-
SSID3	0.000	0.013	-	-
SSID4	0.012	–0.01	0.045	-
SSID5	–0.012	0.007	0.029	0.012

and

Table 3. The spatial Correlation coefficient between MSSIDs’ signals over AOI.

SSID	SSID1	SSID2	SSID3	SSID4
SSID2	0.98	-	-	-
SSID3	0.95	0.98	-	-
SSID4	0.94	0.98	0.95	-
SSID5	0.97	0.96	0.97	0.94

illustrate the time correlation coefficients of SSIDs’ signals at a specific location, and the spatial correlation coefficients over the AOI, respectively. In Table 2, the time correlation coefficients are $\left|Cij\right|<0.05,$ meaning all these signals are independent and its behaviors are similar to the behavior of 5 separated APs.

Table 3 shows the spatial correlation coefficient over the AOI. We can see that these values over the AOI are close to 1, meaning that all SSIDs’ signals which are deployed on the same AP have a similar spatial power distribution. Furthermore, Figure 4 shows the heat map for two APs, each with three SSIDs in different locations on the AOI. From Figure 4 it can be seen that MSSIDs’ signals have the same fingerprinting on the map. Therefore, the use of MSSID signals leads to an increase in the redundancy of these signals and a degradation of the IPS’s performance.

4.4. Path Loss of MSSIDs RSS Signals

The RSS signal value decreases with distance, d, according to the function of the logarithm-distance path loss model [38]. Figure 5 shows the behavior of MSSIDs’ signals and the mean of these signals versus distance d. The behavior of the mean of MSSIDs is close to the path loss model with path loss exponent (n = 3.5). The fusion of MSSIDs’ signals by averaging them contributes to mitigating the effect of the multipath issue.

Table 4. The Standard Deviation of MSSID signals versus distance (m).

No. SSID	L1 = 2 m	L2 = 10 m	L3 = 20 m
SSID1	5.1	3	2.2
SSID2	5.5	2.8	2.4
SSID3	4.6	2.7	2.1
MSSIDs	2.6	1.5	1.4

illustrates that the standard deviation of the RSS signal decreases with distance d. In addition, the standard deviation of the mean of MSSIDs is less than individual signals of MSSIDs.

Most researchers consider each RSS signal to be transmitted from a certain single AP with a unique Media Access Control (MAC) address. MSSID signals have a unique MAC address for each one but they are transmitted from the same AP. This article fills in this gap by investigating the behavior of MSSID signals and designing a classifier based on these signals to improve the performance of IPS.

5. Computational Cost Reduction Methods

In an indoor location system, eliminating redundant APs not only reduces the computation time of fingerprinting processing, but also enhances the accuracy of IPS. The WLAN-based fingerprinting technique has built RM for the AOI, where each vector in the RM comes from measuring the RSS of multiple APs, which are deployed in the AOI. To provide wireless network services for large buildings, a large number of APs are equipped. Nevertheless, all these APs contribute positively to the positioning accuracy where the majority are redundant. Therefore, including all detected APs in fingerprinting vectors leads to a confusing IPS [22]. In addition, the resources, which are equipped on MS, limit even the IPS use of the server’s assistance to find the user’s location. There are many techniques to reduce the computational costs for an IPS.

5.1. AP Selection Methods

To ensure high Wi-Fi quality in most large buildings, a large number of APs are deployed. This large number, L, of APs is greater than what is required to perfectly achieve indoor positioning estimation. The use of all APs leads to excessive redundancy and possible biased estimation. Thus, choosing the informative APs as a subset of L is efficient for reducing computation time and increasing the accuracy of IPSs. In this article, various kinds of AP selections, such as strongest, random, and stable APs, are investigated.

5.1.1. Strongest APs

The benefit of selecting the highest power APs is to provide a high probability of coverage over time. In the online phase, the strongest technique is achieved by selecting K subset of L APs with the highest power readings from the online RSS vectors, where K < L. The K subset APs with the highest power readings is created by sorting the online RSS vectors in descending order, then choosing the top L subset APs [39]. Accordingly, the indices of fingerprints on the RM are sorted to determine the location of MS.

5.1.2. Fisher Criterion

In this technique, the statistical properties of RM fingerprints are exploited during the offline phase to choose the informative APs for positioning [40,41,42]. The time stabilization and spatial discrimination of each AP across RPs are computed and sorted in descending order. A score is assigned for each AP separately as Equation (7):

$${\zeta }^i=\frac{{\sum }_{j=1}^M{({\psi }_j^i-{\overline{\psi }}^i)}^2}{\frac{1}{T-1}{\sum }_{l=1}^T{\sum }_{j=1}^M{(r_j^i(t_l)-{\psi }_j^i)}^2}, i=1,2,\dots \dots ,L$$

(7)

where, ${\overline{\psi }}^i=\frac{1}{M}{\sum }_{j=1}^M{\psi }_j^i$, r represents an instantaneous vector at each RP, M represents a number of RPs in the RM, and T represents a number of time samples at each RP.

5.1.3. Random Combination

The above two methods select informative APs according to different criteria, but in this method, the selection of informative AP does not consider the behavior of APs in time or special domains. The random scheme selects K APs randomly of L APs, and RM is changed to indices of the RSS measured vector accordingly [43]. As a result, this method needs less computation complexity during the online phase, and it does not need a large number of RSS time samples.

5.1.4. Stable AP Method

This metric is based on the behavior of APs in a time domain. The APs with the highest time variance over the AOI are excluded. In the offline phase, K APs with low time variance over the AOI are selected from L APs. In the online phase, the measured vector, V, is sorted accordingly to determine the MS’s position. The stability of APs ${\zeta }^i$ can be calculated as shown in Equation (8):

$${\zeta }^i= \frac{1}{T-1}{\sum }_{l=1}^T{\sum }_{j=1}^M{(r_j^i(t_l)-{\psi }_j^i)}^2$$

(8)

In the literature, we can find other techniques for the selection of Aps, such as Bhattacharyya distance, Information Potential (IP), Information Gain (Info-Gain), Entropy Maximization, and Group Discrimination (GD) [22].

5.2. Clustering Techniques

The computational cost for determining a position is directly proportional to the number of RPs. Therefore, a coarse positioning is introduced in the online phase to confine the positioning process within a small area. The clustering process is achieved in an offline phase where the RPs of the AOI are classified into small groups which are named clusters. Each cluster has a representative which is called an exemplar to represent RPs subset of cluster in an online phase. In this article, K-means and fuzzy C-means are discussed in detail.

5.2.1. K-Means Clustering

In general, the K-means clustering method divides the AOI into subareas to confine the location process within a small area instead of an entire area [44]. Therefore, the computational cost is divided by K, where K represents the number of clusters. In this technique, the center point of a cluster is determined by minimizing the signal distance between exemplar C_j and the members of the same clusters. Given a set of input patterns, $X=\left(x_1,\dots ,x_j,\dots .,x_M\right), \mathrm{where} \mathrm{M} \mathrm{represents} \mathrm{number} \mathrm{of} \mathrm{FP}, \mathrm{and} x_{\mathrm{j}}=\left(x_{j1},\dots \dots ,x_{jL}\right)\in R^L$, we have C = (C₁,……., C_k) K ≤ M exemplars for AOI. By minimizing an objective function, J, in this case a squared error function, the objective function is given in Equation (9):

$$J={\displaystyle \sum }_{j=1}^K{\displaystyle \sum }_{i=1}^M\Vert r_i^j-C_j{\Vert }^2$$

(9)

where, $\Vert r_i^j-C_j\Vert$ represents a measured distance between data points $r_i^j$ and exemplar of cluster $C_j,$ it is an indicator of the distance of the n data points from their respective cluster centers. Figure 6 shows the distribution of FPs on K clusters C = (C₁, ……., C_k). The steps of K-means are summarized in Algorithm 1.

Algorithm 1. K-means clustering

Input:

Reference Points of Area of Interest (RM), K (number of clusters)

Output:

Exemplars vectors C = (C1, ……., Ck), each RP is designated to a certain cluster

Mechanism of K-means

1- Initialize K centroid points 2- Compute the distances between RPs and centroids. 3- Assign each RP to a cluster. 4- Compute the cluster centroid again when all RPs are assigned, 5- Repeat steps 2, 3, and 4 until there is no change for each cluster.

5.2.2. Fuzzy C-Means Clustering

Unlike the K-means clustering technique, the membership of each RP is not crisp in the fuzzy C-means clustering approach [45]. Fuzzy C-means clustering can be divided using AOI into K subsets as shown in Figure 7 with clustering centers C = (C₁, …, C_k) $ϵ R^M$ that verify the minimum cost function, which is a sum of the squared error between the RP’s fingerprint and the clustering center. Its formula is given in Equation (10) as follows:

$$J_m={\displaystyle \sum }_{i=1}^M{\displaystyle \sum }_{j=1}^K{u}_{ij}^m{d}_{ij }^2, 1\le m<\infty$$

(10)

where, m is greater than 1, and $u_{ij}$ is the degree of membership of RP_i in the cluster j, and ${\sum }_{i=1}^K{u}_{ij}=1$. The $d_{ij}=\Vert x_i-c_j{\Vert }^2$ represents the Euclidean distance between the PR_i fingerprint and the vector of cluster center C_j. The value of $u_{ij}$ is randomly chosen between (0–1). Fuzzy partition is achieved through an iterative optimization shown in Equation (10). In order to find $u_{ij}$ and C_j, the Equation (11) and Equation (12) should be applied:

$$u_{ij}=\frac{1}{{\sum }_{k=1}^K{\left(\frac{\Vert x_i-c_j\Vert }{\Vert x_i-c_k\Vert }\right)}^{\frac{2}{m-1}}}$$

(11)

$$c_j=\frac{{\sum }_{i=1}^M{u}_{ij}^m.x_i}{{\sum }_{i=1}^M{u}_{ij}^m}$$

(12)

The iteration will be stopped when $ma{x}_{ij}=\left(\left|u_{ij}{}^{\left(k+1\right)}-u_{ij}{}^{\left(k\right)}\right|\right)<\epsilon$, where ε is a criterion value which falls in between (0–1), and k is the iteration steps.

6. The Multiple SSID-Based Proposed System

In this article, we propose a dimensionality reduction technique in a multiple service set identifier-based indoor positioning system. The main contribution of this article is to reduce the effect of the multipath phenomenon by fusing the MSSID-based fingerprinting and computational cost as well. The proposed IPS framework is presented in the block diagram, as shown in Figure 8. We have two phases: the offline phase and the online phase. We can describe the steps on each phase as summarized in Algorithm 2.

In the offline phase, fusion is the first step in the proposed system where the vectors of MSSID are fused to reduce the effect of the multipath problem and computational costs as well. In the second step, AOI is clustered into small subareas to confine the location of users by specific region. A maximum spatial variance AP selection is applied on each cluster to find the best joint combination of APs at each cluster. Therefore, there is a certain combination of APs at each cluster, Pi for Ci is used in the online phase to verify minimum computational costs as well as distance error.

In the online phase, the clustering technique reduces the positioning process time where the fused vector V is pre-matched with q exemplars of clusters Ci to find the closed cluster. The suitable pattern of APs is chosen correspondingly with assigned cluster C_j. The final estimated position is calculated in the last stage by using the NN approach.

The robustness of the proposed MSSID-based IPS comes from utilizing a fingerprinting approach where most of the indoor positioning systems based on RSS signals used fingerprinting-based systems due to unpredictable behavior of the RSS in an indoor environment. Unlike traditional fingerprinting systems, which use a single SSID at each AP, the proposed system uses MSSIDs at each AP to mitigate the effect of the multipath issue, which is noticed in an indoor environment. Therefore, designing the proposed system with low dimensionality due to fusing MSSID RM and AP selection makes the proposed system more applicable on limited MS resources.

Algorithm 2. The algorithm of the proposed system.

Stage No. 1 (Fusion):

$\Psi =\frac{1}{N}{\displaystyle {\displaystyle \sum }_{i=1}^N}{\Psi }_i$

Stage No. 2 (Clustering):

Clustering $\Psi$ into small subset (Fuzzy C-Means, K-Means)

Stage No. 3 (AP Selection):

Selecting APs pattern for each cluster (Random, Strongest, Spatial Variance) ------------------------------------------------------------------------------------------- The proposed system Algorithm (ONLINE PHASE) Stage No. 1 (Fusion): $$V=\frac{1}{N}{\displaystyle \sum }_{i=1}^N{V}_i$$ Stage No. 2 (Clustering): Apply coarse Positioning by assigning closed cluster Stage No. 3 (AP selection): Choose appropriate AP pattern at assigned cluster. Stage No. 4 (position Estimation): Find final estimated position (xo,yo).

7. The Experiment

To validate the proposed system merits, we used real RSS data. This data was collected from CEAS and Waldo library at Western Michigan University to investigate the behavior of MSSID signals and validate the proposed system. All APs which are used in the AOI have worked with MSSIDs with an Industrial, Scientific, and Medical (ISM) band (2.4 GHz). The designated AOI at CEAS is a good environment to validate the proposed system because it has long corridors and classrooms with large study lounges. The AOI was divided into 117 RPs with a spacing of (2 m × 2 m) and a total area of 3000 m², as shown in Figure 9. Each RP was labeled by a Cartesian coordinate (x_i, y_i). The wireless Net View program was installed on a Toshiba Satellite laptop, which has an Intel wireless-N7260 adapter to record the vector of RSS values from various APs with a 1 sec period. Each RP was created from 200 RSS time samples from various directions (0°, 90°, 180°, and 270°) to mitigate the body presence. 100 different locations were chosen randomly on the AOI to evaluate the proposed system. At each selected location, 200 samples (20,000 TPs) were collected with different orientations to verify the validation of the proposed system.

8. Results and Discussion

In this section, the proposed system is investigated with two types of clustering techniques: K-means, and Fuzzy C-means.

8.1. K-Means Clustering Results

Figure 10 shows the performance of the proposed system when K-means clustering is applied for single SSID and multiple SSIDs. The outliers issue is clearly seen in the single SSID. Although the FPs come from averaging 200 RSS samples, the clustering of FPs with MSSIDs is more stable, and it is similar to the RPs’ spatial distribution. Figure 11a shows the CDF of distance error for MSSIDs as compared to a single SSID at q = 10 (number of clusters). It is clear that the performance of MSSIDs outperforms the behavior of a single SSID. Figure 11b shows the average error of MSSID and single SSID for various values of q. The mean of the distance error is increased slightly with the increasing number of clusters. The number of APs is 34 for both experiments, and all results are considered without APs reduction.

8.2. Selection of APs with K-Means

Three kinds of approaches to the selection of APs were conducted on each cluster at the same time: random, strongest, and maximum spatial variance. Figure 12 shows the CDF of error for the selected approaches with q = 20, and AP reduction is 50% (number of APs = 17). The maximum spatial variance exhibits superior performance as compared with the other selected APs approaches.

Furthermore, the performance of the maximum spatial variance with 17 APs (50% reduction) is similar to the performance of all APs (34 APs). This confirms previous work [11]. We found the redundancy of MSSID occurred when SSIDs were exploited in the same fingerprinting vectors.

Table 5. The mean distance error of the K-means-based proposed system versus a single SSID.

Selection Technique	Strongest APs 50% Reduction	Random APs 50% Reduction	Max. Spatial Var. 50% Reduction	Whole APs
Single SSID	1.33 m	1.6 m	1.14 m	1.08 m
Multiple SSIDs	1.11 m	1.36 m	0.9 m	0.86 m

summarizes the accuracy of the proposed system with various kinds of selection APs. The selection of informative APs leads to a reduction in computational cost of 50%, as well as the reduction that comes from the clustering technique. The performance of the K-means-based proposed system with various values of q (number of clusters) is illustrated in Figure 13. As we can see in the figure, the average error is decreased when the number of informative APs is increased. The maximum spatial variance selection AP exhibits a superior performance when compared to the strongest and random APs selection with various values of q (q = 10, and q = 20).

8.3. Fuzzy C-Means Results

The same methodology that is used with K-means is applied with the Fuzzy C-means method. Figure 14 shows the performance of Fuzzy C-means clustering, where Figure 14a shows the CDF of distance error for MSSIDs as compared to a single SSID at q = 10 (number of clusters), and the value of membership, which is issued by C-means, is (m = 1.8). It is clear that the performance of MSSIDs outperforms the behavior of a single SSID. Figure 14b shows the average distance error of MSSIDs and a single SSID for various values of q. From Figure 14b, we can see that the mean of error is increased slightly with the increasing number of clusters. The number of APs is also 34 APs for both experiments.

8.4. Selection of APs with Fuzzy C-Means

In this experiment, three types of selection APs approaches were also conducted on each cluster at the same time: random, strongest, and maximum spatial variance. Figure 15 shows the CDF of distance error for the selection approaches with q = 20, and AP reduction is 50% (number of APs = 17). The maximum spatial variance exhibits superior performance as compared with the other selected APs approaches. In addition, the performance of maximum spatial variance with 17 APs (50% reduction) is similar to the performance of all APs (34 APs).

Table 6. The distance error of the C-means-based proposed system versus a single SSID.

Selection Technique	Strongest APs 50% Reduction	Random APs 50% Reduction	Max. Spatial Var. 50% Reduction	Whole APs
Single SSID	1.32	1.51	1.06	1.01
Multiple SSIDs	1.1	1.25	0.84	0.82

summarizes the accuracy of the proposed C-means-based system with various kinds of selection APs.

Figure 16 shows the comparison between C-means and the proposed K-means-based system with maximum spatial variance selection AP. The C-means clustering-based system performance exhibits a slight improvement in accuracy. The reason is the average number of FPs at each cluster in C-means is more than the average number of FPs in K-means.

Figure 17 shows the compression between the proposed system and traditional technique that considers each SSID as a single AP. The superior performance of the proposed system with 17 SSID selection versus the traditional technique performance is clear. The MSSID-based technique selects 17 SSIDs (17 distinct APs), while the traditional technique selects 17 SSIDs, which means approximately 6 distinct APs (each AP transmits 3 SSIDs). The shortcoming of the traditional technique comes from exploiting the similar SSIDs in the same fingerprinting vector.

Table 7. The Calculation reduction of positioning process versus number of SSIDs.

No. SSIDs	Distance Error (m) Traditional (K-Means)	Distance Error (m) Proposed (C-Means)	Calculation Reduction %
10	1.1	1.07	17%
17	0.9	0.84	12%
22	0.87	0.84	10%
28	0.85	0.83	5%
34	0.86	0.82	0%

summarizes the percentage of calculation reduction versus the number of SSIDs when q = 20. Choosing informative APs leads to a reduction in computational costs as well as the reduction that comes from fusing and the clustering technique.

9. Conclusions and Future Work

Indoor localization is an active and noble research area for its numerous applications in various areas of our daily lives. Within indoor environments, tracking people and localizing objects have become a necessity and thus motivates many researchers to tackle the challenges of IPS. In this article, the dimensionality reduction of MSSID’s RM has been proposed. Reducing the computational cost of IPS is very important for real-time system applications because large data require a long time to be processed. The reduction comprises three parts: first, clustering AOI into subareas to confine the location process into a subset of RPs. Second, fusing N RM of MSSIDs to create a delegate RM, which is used to present N RM of MSSID in the positioning process. Third, the use of a maximum spatial variance to select the most informative APs. The proposed system is designed according to the behavior of MSSID signals in time and spatial domain. Fusing RM of MSSID mitigates the outlier’s issue, which is created due to the multi-path phenomenon. The results show that the fusion of N RM of MSSID in both phases mitigates the effect of the fading issue and minimizes the length of fingerprinting vectors by using the maximum spatial variance selection APs. In addition, the results exhibit the ability of maximum spatial variance selection APs technique to enhance the precision of IPS and reduce the computational costs as well. Light algorithm approaches such as the proposed system are feasible for real-time tracking because the positioning process requires only a few calculations in the online phase to find the location of MS.

Future work will include several tasks to extend the current proposed system. First, the behavior of the mean of MSSIDs signals is close to path loss, as shown in Figure 5, because averaging the MSSIDs’ signals contributes to mitigating the effect of the multipath issue. Accordingly, it might be possible to use the fused MSSIDs’ RSS-based path loss model to determine the user’s location. In this case, knowing the coordinates of APs in the AOI is sufficient to determine the user’s location without creating a radio map, which requires more time and labor costs.

Second, it can be very fruitful to investigate the use of the 2.4 GHz and 5 GHz bands simultaneously with MSSID that are deployed on the same AP to enhance the WLAN-based IPS. The coverage area of 5 GHz is smaller than 2.4 GHz [46]. Therefore, we can use 5GHz for coarse positioning and the 2.4 GHz for fine positioning.