Sage Journals: Discover world-class research

Abstract

Indoor localization system using receive signal strength indicator from wireless access point has attracted lots of attention recently. Geometric method is one of the most widely used spatial graph algorithms to locate object in an indoor environment, but it does not achieve good results when it is applied to a limited amount of valid data, especially when using the trilateration method. On the other hand, localization based on fingerprint can achieve high accuracy but need to pay heavy manual labor for fingerprint database establishment. In this article, we propose a bilateral greed iteration localization method based on greedy algorithm in order to use all of the effective anchor points. Comparing to trilateration, fingerprint, and maximum-likelihood method, the bilateral greed iteration method improves the localization accuracy and reduces complexity of localization process. The method proposed, coupled with measurements in a real indoor environment, demonstrates its feasibility and suitability, since it outperforms trilateration and maximum-likelihood receive signal strength indicator–based indoor location methods without using any radio map information nor a complicated algorithm. Extensive experiment results in a Wi-Fi coverage office environment indicate that the proposed bilateral greed iteration method reduces the localization error, 63.55%, 9.93%, and 47.85%, compared to trilateration, fingerprint, and maximum-likelihood method, respectively.

Keywords

Indoor localization Wi-Fi greedy algorithm trilateration K-NN

Introduction

Nowadays, the availability of the Mobile Terminal (MT) location information in a wireless network system has led to the demand of location-based services (LBSs).¹ Wide adoption of the Global Positioning System in mobile devices, combined with cellular networks, have practically solved the problem of outdoor localization and opened a new market. It is expected that in the near future, we will witness similar trends for indoor scenarios where people spend more than 70% of their lives. However, satellite or cellular signals are sharply degraded or may fail completely in indoor environment where radio signals are interrupted by shadowing effects.² Multifarious methodologies and approaches have been proposed to deal with these problems, such as ultra-wide band (UWB),³ radio frequency identification (RFID),⁴ wireless sensor network (WSN),⁵ Bluetooth,⁶ and wireless local area network (WLAN).⁷ Among all of the indoor location technologies, Wi-Fi-based indoor location systems have attracted a lot of attention because Wi-Fi has become a standard infrastructure in most buildings, such as airports, hospital, office buildings, and commercial centers. And as a common personal item, smartphones are now all able to receive and identify the Wi-Fi signals. Because of this, Wi-Fi location is a low-cost, widespread, and easy obtained indoor location method.^8,9

The received signal strength indicator (RSSI) has been utilized for Wi-Fi location estimation with the advantage of the absence of extra hardware for implementation.¹⁰ Typically, there are two techniques of algorithms for RSSI positioning.¹¹ The first technique is defined as position-related categories, which are also called fingerprint methods.¹² The main idea is using information of survey RSSI values. It depends on sample location coordinates to generate radio frequency (RF) map which is called fingerprint map for training and labeling databases after the classifier, by matching algorithms, such as K-Nearest Neighbor (K-NN),^13,14 machine-learning-based schemes,¹⁵ Bayesian strategy,¹⁶ neural networks,¹⁷ and data mining based on clustering¹⁸ to estimate MT positions by calculating Euclidean distance between the fingerprint database system and the real-time RSSI values.¹⁹ It can provide a certain accuracy localization; however, building and updating the fingerprint database are expensive and laborious. The other technique is defined as geometric-related categories, which utilizes the empirical path loss models for distance estimation. After that, a trilateration or maximum-likelihood algorithm is performed for position estimation. The trilateration and maximum-likelihood positioning methods use three or more anchor points (APs) to calculate distance using time differences in signal receptions or signal strength, which are then used to estimate the location of the user.²⁰

However, RSSI is influenced by many parameters, and establishing an appropriate RF propagation loss model is very difficult. As a result, the trilateration and maximum-likelihood-model-based positioning methods are less accurate than the fingerprinting positioning method. Not only that, the situation of trilateration localization based on three circles is diverse, including the position of the three circles and the number of their intersection. Nevertheless, we propose a bilateral greed iteration (BGI) localization method based on greedy algorithm in order to improve the localization accuracy and reduce complexity of localization process. Generally, the basic trilateration model requires three APs to achieve the position estimate of the MT. But it is difficult to find the solution of simultaneous equations. Even if the equation is overdetermined, the probability of solving the equation is still very low. On the other hand, the amount of AP which can be detected by MT is more than three in the real indoor environment. In order to obtain a better positioning accuracy, how to use all the RSSI of these APs and reduce calculating complexity become very important. The BGI based on greedy algorithm we proposed can make full use of these APs step by step to get the better positioning result. Meanwhile, the BGI is a lower complexity algorithm than K-NN which can relieve the use of MT computational resource, so it can dynamically estimate the models that preferably fit the propagation environment present between the MT and each AP by using only the RSSI values obtained at that precise instant.

Related work

RSSI and distance

Let us assume that there is an IEEE 802.11 wireless network in the indoor environment in which we want to implement a localization system. Our aim is to estimate the location of an MT within the Wi-Fi network. This MT can measure RSSI values from all APs in range. At time instants of $t_{1}, t_{2}, \dots, t_{N}$ , the MT measures RSSI values from each of the M APs in range and $P_{R_{i}} (t_{j})$ indicates the RSSI value measured by the MT at time $t_{j}$ from the $A P_{i}$ . In a precisely given instant and place, the RSSI values obtained by a device in a wireless network depend on a large number of unpredictable factors. Specifically, in an IEEE 802.11 network, small changes in position or direction may result in dramatic differences in RSSI. It is clear that one of the factors influencing RSSI values obtained by a wireless device is the distance between emitter and receiver, as this distance causes an attenuation in RSSI values. This makes it impossible to convert the measured received power into a radio wave propagation path by a certain model without errors. Therefore, some amendments need to be introduced in the indoor localization model. In power-based ranging, RSSI is mapped into the distance from the transmitter by the prevalent Log-normal Distance Path Loss (LDPL) model^21,22

$P (d) [dBm] = P (d_{0}) [dBm] - 10 nlo g_{10} (\frac{d}{d_{0}}) + X_{σ}$ (1)

where $P (d)$ denotes the measured path loss at distance d. $P (d_{0})$ is the average path loss at reference point $d_{0}$ , and n is the path loss exponent.²³ $X_{σ}$ is the obstacle affect consisting of walls, people and interlayers. The true distance is

$d = d_{0} \times 10^{- \frac{P (d) - P (d_{0}) - X_{σ}}{10 n}}$ (2)

But how to calculate the value of $X_{σ}$ is a significant problem in setting up the signal propagation model in the indoor environment, which uses the Wi-Fi-based indoor positioning system. User can detect a very huge variation of RSSI from an AP if the user gets into a room or turns a corner causing the radio be shaded by doors and walls. A predefined $X_{σ}$ cannot fulfill the demand. This problem causes the majority of position estimation error. We will do specialized experiment in the following chapters to confirm n and $X_{σ}$ in our indoor environment.

Trilateration

Trilateration is a method of calculating the position of MT from the distance between the known positions of three APs and the MT. There are three APs which the MT can communicate with as shown in Figure 1. The principle behind trilateration positioning is to trace out a circle using a line represented by the distance $(d_{i}, i = 1, 2, 3)$ between the AP (coordinate $((x_{i}, y_{i}), where i = 1, 2, 3)$ and the $MT (x, y)$ , and a center point represented by the AP. The circumference of the circle represents the pseudo-range of the equivalent signal strength of a certain AP. The MT may locate at any point on the circumference of the circle. In general, these two distance circles are intercrossed at two points, producing two solutions to the location estimate of the MT. To resolve the ambiguity of the two solutions, a third distance circle, resulting from the distance measurement at the third AP, is required. The simultaneous equation is as follows

${\begin{matrix} \sqrt{{(x - x_{1})}^{2} + {(y - y_{1})}^{2}} = d_{1} \\ \sqrt{{(x - x_{2})}^{2} + {(y - y_{2})}^{2}} = d_{2} \\ \sqrt{{(x - x_{3})}^{2} + {(y - y_{3})}^{2}} = d_{3} \end{matrix}$ (3)

Figure 1.

Illustration of trilateration.

To confirm the localization of MT, with coordinates (x, y), it only needs two equations. But because of nonlinear characteristic, we need the third equation to solve the ambiguous solution problem. Then we can obtain the coordinates of the MT

$\begin{array}{l} [\begin{matrix} x \\ y \end{matrix}] = {[\begin{matrix} 2 (x_{1} - x_{2}) & 2 (y_{1} - y_{2}) \\ 2 (x_{1} - x_{3}) & 2 (y_{1} - y_{3}) \end{matrix}]}^{- 1} \\ \times [\begin{matrix} x_{1}^{2} - x_{2}^{2} + y_{1}^{2} - y_{2}^{2} + d_{2}^{2} - d_{1}^{2} \\ x_{1}^{2} - x_{3}^{2} + y_{1}^{2} - y_{3}^{2} + d_{3}^{2} - d_{1}^{2} \end{matrix}] \end{array}$ (4)

Figure 1 shows the ideal situation in which the three circles can intersect at one point. Usually, due to measurement error in the real indoor environment, the localization of three circles is divided into three cases, intersect with each two circles, intersect but not each two circles, and no intersection, which is shown in Figure 2.

Figure 2.

Three intersecting situations for three circles in the real environment: (a) intersect with each two circles, (b) intersect but not each two circles, and (c) no intersection.

There is no solution of equation (3) in the case as shown in Figure 2. Even if the equation is overdetermined (the number of equations is more than the unknown solution), the probability of solving the equation is still very low. The usual method is considering equation (3) as matrix form

$HX = B$ (5)

where

$H = [\begin{matrix} x_{2} - x_{1} & y_{2} - y_{1} \\ x_{3} - x_{1} & y_{3} - y_{1} \end{matrix}]$ (6)

$B = \frac{1}{2} [\begin{matrix} (d_{1}^{2} - d_{2}^{2}) + (x_{2}^{2} + y_{2}^{2}) - (x_{1}^{2} + y_{1}^{2}) \\ (d_{1}^{2} - d_{3}^{2}) + (x_{3}^{2} + y_{3}^{2}) - (x_{1}^{2} + y_{1}^{2}) \end{matrix}]$ (7)

The solution of equation (5) is obtained by the least square method

$X = {(H^{T} H)}^{- 1} H^{T} B$ (8)

A certain optimization algorithms have been done based on equation (8), for instance, a Wi-Fi-based weighted screening method (WSM) is proposed to improve the localization accuracy in trilateration.²⁰ A signal tendency index (STI) based on Procrustes analysis is presented to match standardized fingerprints in Zou et al.¹² But the position of more circles and the number of their intersection are not considering completely, which is a puzzle without doubt. We propose the BGI localization method using greedy algorithm, which only needs two circles at each calculation, to avoid complication of three or more circles.

BGI localization

The basic concept of the BGI method is based on greedy algorithm which makes the locally optimal choice at each bilateral positioning process. We summarize the BGI algorithm for the two-dimensional (2D) plan localization problem as follows:

Step 1. Let $C_{1}, C_{2}, \dots, C_{i}, \dots, C_{N}$ represent the circles, respectively, N is the number of APs.

Step 2. Give $r_{i}$ as the radius of $C_{i}$ , and it means the measurement distance between $A P_{i}$ and MT, $(x, y)$ as the true coordinates of MT.

Step 3. Do the first bilateral measurement of BGI. Determine two circles $C_{i}$ and $C_{i + 1}$ to figure out the position point $M_{1}$ of MT in maximum probability, and the coordinate of $M_{1}$ is $(x_{M 1}, y_{M 1})$ . There are four different position relationships between $C_{i}$ and $C_{i + 1}$ .

Step 4. Do the second bilateral measurement of BGI. Determine the third circle $C_{i + 2}$ , and figure out $M_{2} (x_{M 2}, y_{M 2})$ via $M_{1}$ and $C_{i + 2}$ .

Step 5. Go on doing the BGI until the optimal $M_{i} (x_{Mi}, y_{Mi})$ is found out.

Step 6. Stop.

In the BGI algorithm, it only needs to distinguish four different position relationships between $C_{i}$ and $C_{i + 1}$ instead of figuring out equation (3) in classic trilateration method. The four cases in step 3 of BGI algorithm are separation, tangency, intersection, and containing.

Separation

In a separation case, the algorithm sets a line $l_{i}^{i + 1}$ connecting two points, $A P_{i}$ and $A P_{i + 1}$ , which are the centers of circles $C_{i}$ and $C_{i + 1}$ as shown in Figure 3. Coordinates $(x_{i}, y_{i})$ and $(x_{i + 1}, y_{i + 1})$ are presented of two APs, $A P_{i}$ and $A P_{i + 1}$ , which are mentioned before. We can obtain the equation expression of $l_{i}^{i + 1}$

$\frac{y - y_{i}}{y_{i + 1} - y_{i}} = \frac{x - x_{i}}{x_{i + 1} - x_{i}}$ (9)

where $y_{i + 1} \neq y_{i}$ , $x_{i + 1} \neq x_{i}$ . The intersections of $l_{i}^{i + 1}$ and $C_{i}, C_{i + 1}$ are $P_{A 1}$ and $P_{A 2}$ , respectively. The radiuses of these two circles are $r_{i}$ and $r_{i + 1}$ as giving in step 2. Coordinate of $P_{A 1}$ can be figured out by equation (9) and expression of $C_{i}$

${\begin{matrix} \frac{y - y_{i}}{y_{i + 1} - y_{i}} = \frac{x - x_{i}}{x_{i + 1} - x_{i}} \\ {(x - x_{i})}^{2} + {(y - y_{i})}^{2} = r_{i}^{2} \end{matrix}$ (10)

However, there is an ambiguous solution $P'_{A 1}$ . Before identifying optimal solution, we first figure out $P_{A 2}$ coordinate by the equation

${\begin{matrix} \frac{y - y_{i}}{y_{i + 1} - y_{i}} = \frac{x - x_{i}}{x_{i + 1} - x_{i}} \\ {(x - x_{i + 1})}^{2} + {(y - y_{i + 1})}^{2} = r_{i + 1}^{2} \end{matrix}$ (11)

Figure 3.

Two circles are separated without intersection.

It also has an ambiguous solution $P'_{A 2}$ . $P_{A 1}$ and $P_{A 2}$ are screened out through calculating the minimum distance between circles $C_{i}$ and $C_{i + 1}$

${\begin{matrix} P_{A 1} (x, y) \\ P_{A 2} (x, y) \end{matrix} = \arg \min_{(P_{A 1}, P_{A 2})} {\begin{matrix} \sqrt{{({x^{'}}_{A 1} - x_{A 2})}^{2} + {({y^{'}}_{A 1} - y_{A 2})}^{2}} \\ \sqrt{{({x^{'}}_{A 1} - {x^{'}}_{A 2})}^{2} + {({y^{'}}_{A 1} - {y^{'}}_{A 2})}^{2}} \\ \sqrt{{(x_{A 1} - x_{A 2})}^{2} + {(y_{A 1} - y_{A 2})}^{2}} \\ \sqrt{{(x_{A 1} - {x^{'}}_{A 2})}^{2} + {(y_{A 1} - {y^{'}}_{A 2})}^{2}} \end{matrix}$ (12)

After acquiring the coordinates of $P_{A 1}$ and $P_{A 2}$ , the target point $M_{1} (x_{M 1}, y_{M 1})$ of MT can be averaged out to obtain at the first BGI

${\begin{matrix} x_{M 1} = \frac{x_{A 1} + x_{A 2}}{2} \\ y_{M 1} = \frac{y_{A 1} + y_{A 2}}{2} \end{matrix}$ (13)

Tangency

There is only one intersection between $C_{i}$ and $C_{i + 1}$ when they are tangent, and the point of tangency is $M_{1}$ as shown in Figure 4. The line connecting two circle centers is $l_{i}^{i + 1}$ and the expression is similar to equation (9). It also has two ambiguous intersections $P'_{A 1}$ and $P'_{A 2}$ between $l_{i}^{i + 1}$ , which crosses $M_{1}$ , and two circles. Combining expression of $l_{i}^{i + 1}$ and $C_{i}$ , we can obtain equation (10). Similarly, equation (11) can be obtained by combining $l_{i}^{i + 1}$ and $C_{i + 1}$ . There are two solutions in both equations (10) and (11)

$S_{(13)} = {\begin{matrix} P'_{A 1} (x'_{A 1}, y'_{A 1}) \\ M_{1} (x_{M 1}, y_{M 1}) \end{matrix}$ (14)

$S_{(14)} = {\begin{matrix} P'_{A 2} (x'_{A 2}, y'_{A 2}) \\ M_{1} (x_{M 1}, y_{M 1}) \end{matrix}$ (15)

Comparing equations (14) and (15), the equal one $M_{1}$ is the target point of MT at the first BGI.

Figure 4.

Two circles are tangent with one intersection.

Intersection

There are two intersections ( $P_{A 1}$ and $P_{A 2}$ ) between $C_{i}$ and $C_{i + 1}$ when they are intersectant. As shown in Figure 5, $r_{i}$ and $r_{i + 1}$ are the radiuses of $C_{i}$ and $C_{i + 1}$ , respectively. Line segment $A P_{i} A P_{i + 1}$ and $P_{A 1} P_{A 2}$ were intersected at point $M_{1}$ , which is the first BGI point we should solve out. Two parallel lines of y-axis, $A P_{i} A$ and $M_{1} B$ , and another parallel line of x-axis, $AA P_{i + 1}$ , are intersecting at points A and B, respectively. We assume that d is the length of line segment $A P_{i} A P_{i + 1}$ , $k_{1}$ is the slope of line $A P_{i} A P_{i + 1}$ , so then

$d = \sqrt{{(x_{i} - x_{i + 1})}^{2} + {(y_{i} - y_{i + 1})}^{2}}$ (16)

$k_{1} = \frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}}$ (17)

where $y_{i + 1} \neq y_{i}$ , $x_{i + 1} \neq x_{i}$ , and

${(P_{A 1} M_{1})}^{2} = r_{i}^{2} - {(A P_{i} M_{1})}^{2}$ (18)

${(P_{A 1} M_{1})}^{2} = r_{i + 1}^{2} - {(M_{1} A P_{i + 1})}^{2}$

$= r_{i + 1}^{2} - {(A P_{i} A P_{i + 1} - A P_{i} M_{1})}^{2}$

$= r_{i + 1}^{2} - {(d - A P_{i} M_{1})}^{2}$

$= r_{i + 1}^{2} - d^{2} - {(A P_{i} M_{1})}^{2} + 2 dA P_{i} M_{1}$ (19)

Figure 5.

Two circles are intersectant with two intersections.

Then the following expression can be obtained via

$A P_{i} M_{1} = \frac{r_{i}^{2} - r_{i + 1}^{2} + d^{2}}{2 d}$

$\Rightarrow \frac{A P_{i} M_{1}}{d} = \frac{r_{i}^{2} - r_{i + 1}^{2} + d^{2}}{2 d^{2}}$ (20)

In the right-angled triangle $Δ A P_{i} AA P_{i + 1}$

$\frac{AB}{AA P_{i + 1}} = \frac{A P_{i} M_{1}}{A P_{i} A P_{i + 1}}$

$\Rightarrow \frac{x_{M 1} - x_{i}}{x_{i + 1} - x_{i}} = \frac{A P_{i} M_{1}}{d}$

$\Rightarrow x_{M 1} = x_{i} + \frac{A P_{i} M_{1}}{d} (x_{i + 1} - x_{i})$

$= x_{i} + \frac{r_{i}^{2} - r_{i + 1}^{2} + d^{2}}{2 d^{2}} (x_{i + 1} - x_{i})$ (21)

According to the slope of line $A P_{i} A P_{i + 1}$

$k_{1} = \frac{y_{M 1} - y_{i}}{x_{M 1} - x_{i}}$

$\Rightarrow y_{M 1} = y_{i} + k_{1} (x_{M 1} - x_{i})$

$= y_{i} + \frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}} (x_{M 1} - x_{i})$ (22)

At this point, the coordinate of $M_{1}$ is solved out and it is the target position of MT at the first BGI.

Containing

It is similar between the containing case and separation case (see Figure 6). Line $l_{i}^{i + 1}$ passes through points $P'_{A 1}$ , $A P_{i}$ , $P'_{A 2}$ , $A P_{i + 1}$ , $P_{A 2}$ , $M_{1}$ , and $P_{A 1}$ sequentially, and its expression is shown in equation (9).

Figure 6.

Two circles are containing without intersection.

The coordinates of $P_{A 1}$ , $P_{A 2}, P'_{A 1}$ , and $P'_{A 2}$ are calculated by equations (10) and (11). Formula (12) is used to filter out $P_{A 1}$ and $P_{A 2}$ as the nearest points between circles $C_{i}$ and $C_{i + 1}$ . $M_{1}$ is the midpoint of line segment $P_{A 1} P_{A 2}$ and is solved by equation (13).

After confirming the position of $M_{1}$ through two circles in the above four different cases, the second positioning point $M_{2}$ should be solved out using the AP $A P_{i + 2}$ and the third circle $C_{i + 2}$ with radius $r_{i + 2}$ . A straight line $l_{i + 1}^{i + 2}$ is drawn passing through points $M_{1}$ and $A P_{i + 2}$ , which also has two intersections ( $P_{A 3} and P'_{A 3}$ ) with $C_{i + 2}$ , as shown in Figure 7. The coordinates of $P_{A 3} and P'_{A 3}$ can be solved out by

${\begin{matrix} \frac{y - y_{M 1}}{y_{i + 2} - y_{M 1}} = \frac{x - x_{M 1}}{x_{i + 2} - x_{M 1}} \\ {(x - x_{i + 2})}^{2} + {(y - y_{i + 2})}^{2} = r_{i + 2}^{2} \end{matrix}$ (23)

where the two equations are the expressions of $l_{i + 1}^{i + 2}$ and $C_{i + 2}$ . $P_{A 3}$ is screened out through calculating the minimum length between line segment $M_{1} P_{A 3}$ and $M_{1} P'_{A 3}$

$P_{A 3} (x, y) = \arg min_{(x, y)} {\begin{matrix} \sqrt{{(x_{M 1} - x_{A 3})}^{2} + {(y_{M 1} - y_{A 3})}^{2}} \\ \sqrt{{(x_{M 1} - x'_{A 3})}^{2} + {(y_{M 1} - y'_{A 3})}^{2}} \end{matrix}$ (24)

Figure 7.

Confirm the second localization point $M_{2}$ using BGI.

The middle point $M_{2} (x_{M 2}, y_{M 2})$ of line segment $M_{1} P_{A 3}$ is calculated by

${\begin{matrix} x_{M 2} = \frac{x_{M 1} + x_{A 3}}{2} \\ y_{M 2} = \frac{y_{M 1} + y_{A 3}}{2} \end{matrix}$ (25)

which is the localization of MT at the second BGI.

$M_{3}$ , $M_{4}$ , $M_{5}$ , and so on, will be sought out in the next phase in the way of seeking $M 2$ . In the proposed BGI algorithm, a threshold of RSSI value should be set ahead of time, greater than −90 dBm, for instance. If there are N APs which can be detected via RSSI value greater than the threshold by MT, it will do BGI calculation N – 1 times, and N – 1 $M_{i}$ localization points will be estimated out. Our experiments in the real indoor environment will screen out the optimal value of N in the next section.

Experimental results and discussion

In this section, an experiment is provided to demonstrate the effectiveness of the BGI localization algorithm proposed in this article. We had the experiment in Room 402 of Electronic and Information College, Northwestern Polytechnical University. The room is a typical office environment, including tables, chairs, personal computers, and students. For achieving the real indoor environment, we do all our experiments on weekdays. The target system for our experiments is a wireless LAN using the IEEE802.11b (Wi-Fi) standard. The system is composed by eight TL-WDR5620 access points produced by TP-LINK Technologies, equipped with four external omnidirectional antennas. All presented measurements are taken on 2.4 GHz center frequency. The RSSI value is gathered with a Thunderobot laptop using an TP-LINK wireless network adapter and WirelessMon software. Before testing the BGI algorithm, we first set up the relationship model between RSSI value and distance in the experiment room.

Environmental parameter

The variable quantity n in expression (1) is influenced by indoor environment and test devices. We built a measurement model as shown in Figure 8 to confirm the value of n in Room 402. Figure 8 shows the experiment environment Room 402 with the dimensions of 8 m × 11.6 m. Three concentric circles $C^{1}, C^{2}, and C^{3}$ take one AP as the center, 1, 2, and 3 m as radius, respectively. There are four sampling points in the north, east, south, and west directions on each circle. As shown in Figure 8, there are 12 sampling points totally: $P_{N}^{1}, P_{E}^{1}, P_{S}^{1}, P_{W}^{1}$ on $C^{1}$ , $P_{N}^{2}, P_{E}^{2}, P_{S}^{2}, P_{W}^{2}$ on $C^{2}$ , and $P_{N}^{3}, P_{E}^{3}, P_{S}^{3}, P_{W}^{3}$ on $C^{3}$ . Circle $C^{1}$ is the unit circle and the radius is $d_{0}$ of expression (1).

Figure 8.

The key parameter measurement model of experiment environment.

We began the test at sampling point $P_{N}^{1}$ . The laptop was placed at $P_{N}^{1}$ and then rotated to north, east, south, and west directions. At each direction, RSSI value was sampled each second and continued for 3 min. There are 180 sampling times at $P_{N}^{1}$ directing north, and it is similar to the other directions. The mean RSSI value of each direction at 12 sampling points is shown in Table 1. It also shows the mean RSSI value of each point.

Table 1.

RSSI value (dBm) of four directions at 12 sampling points.

	$P_{N}^{1}$	$P_{E}^{1}$	$P_{S}^{1}$	$P_{W}^{1}$	$P_{N}^{2}$	$P_{E}^{2}$	$P_{S}^{2}$	$P_{W}^{2}$	$P_{N}^{3}$	$P_{E}^{3}$	$P_{S}^{3}$	$P_{W}^{3}$
North	19.33	20.06	23.79	19.98	31.47	25.38	29.38	31.84	37.34	36.54	40.99	34.17
East	18.47	21.37	25.71	22.69	30.47	28.62	25.68	36.16	38.45	32.78	39.36	39.83
South	19.87	22.67	23.17	18.82	33.71	26.22	24.8	32	34.21	35.46	41.28	37.78
West	22.73	26.98	24.25	20.11	31.23	29.78	28.26	32.84	35.12	31.34	38.57	34.46
Mean value	20.1	22.77	24.23	20.4	31.72	27.5	27.03	33.21	36.28	34.03	40.05	36.56

RSSI: receive signal strength indicator.

According to the sampling data above, $P (d_{0})$ , $P (d_{1})$ , and $P (d_{2})$ in equation (1) of range 1, 2, and 3 m can be figured out

${\begin{matrix} P (d_{0}) = \frac{(- 20.1) + (- 22.77) + (- 24.23) + (- 20.4)}{4} = - 21.875 \\ P (d_{1}) = \frac{(- 31.72) + (- 27.5) + (- 27.03) + (- 33.21)}{4} = - 29.865 \\ P (d_{2}) = \frac{(- 36.28) + (- 34.03) + (- 40.05) + (- 36.56)}{4} = - 36.73 \end{matrix}$

and then we can obtain the following equation on the basis of equation (1):

${\begin{matrix} - 29.865 = - 21.875 - 10 nlo g_{10} (\frac{2}{1}) + X_{σ} \\ - 36.73 = - 21.875 - 10 nlo g_{10} (\frac{3}{1}) + X_{σ} \end{matrix}$ (26)

We can calculate out n = 3.9 and $X_{σ} = 3.75 dBm$ from equation (26), and equation (2) in the measurement environment is

$d = d_{0} \times 10^{- \frac{P (d) - P (d_{0}) - 3.75}{10 \times 3.9}}$ (27)

Test and results

In this section, we discuss the measurement results conducted to establish the effectiveness of BGI method as well as a conventional trilateration method that was used for the localization test in the evaluation as comparison, and the test steps are as follows:

Step 1. Let $C_{1}, C_{2}, \dots, C_{i}, \dots, C_{N}$ represent the circles, respectively; N is the number of APs.

Step 2. Give $r_{i}$ as the radius of $C_{i}$ , and it means the measurement distance between $A P_{i}$ and MT, $(x, y)$ as the true coordinates of MT.

Step 3. Determine two circles $C_{i}$ and $C_{i + 1}$ to figure out the position point $M_{1}$ of MT in maximum probability, and the coordinate of $M_{1}$ is $(x_{M 1}, y_{M 1})$ . There are four different position relationships between $C_{i}$ and $C_{i + 1}$ .

Step 4. Compute $\sqrt{{(x - x_{M 1})}^{2} + {(y - y_{M 1})}^{2}} = ε_{1}$ .

Step 5. Determine the third circle $C_{i + 2}$ , and figure out $M_{2} (x_{M 2}, y_{M 2})$ via $M_{1}$ and $C_{i + 2}$ .

Step 6. Compute $\sqrt{{(x - x_{M 2})}^{2} + {(y - y_{M 2})}^{2}} = ε_{2}$ .

Step 7. Repeat steps 5 and 6, calculate $ε_{3}, \dots, ε_{i}, \dots, ε_{N}$ . $ε_{\min} = \min {ε_{1}, ε_{2}, \dots, ε_{i}, \dots, ε_{N}}$ .

Step 8. Calculate error $ε_{T}$ of trilateration method, and compare $ε_{\min}$ and $ε_{T}$ .

Step 9. Stop.

In Room 402, there are eight APs and four test points arranged for the experiment. The distribution and coordinates of these points are shown in Figure 9. All the APs are dispersedly fixed in the room.

Figure 9.

The distribution of APs and test points.

At test point 1 (T1), we gathered RSSI from APs from four different directions using the same laptop. RSSI value collection at each direction last 5 min and the acquisition frequency is once per second. After taking the mean, the measurement distance between each AP and T1 is calculated via equation (16). The RSSI and distance are shown in Table 2.

Table 2.

The RSSI (dBm) and distance (m) between T1 and APs.

	AP1	AP2	AP3	AP4	AP5	AP6	AP7	AP8
North	37.48	40.49	36.44	57.44	44.49	30.45	47.58	46.58
East	31.26	30.68	34.68	52.89	47.87	24.78	44.36	47.73
South	35.45	34.21	35.85	51.14	41.25	28.24	42.46	48.26
West	29.58	38.36	40.34	49.62	41.76	27.46	43.37	50.88
Mean value	33.4425	35.935	36.8275	52.7725	43.8425	27.7325	44.4425	48.3625
Distance	2.47	2.86	3.02	7.73	4.56	1.76	4.46	5.62

RSSI: receive signal strength indicator; APs: anchor points.

After figuring out the distance, we first confirm circles $C_{1}$ and $C_{2}$ with center at AP1 and AP2 and radius equal to 2.47 and 2.86 m as shown in Figure 10. The coordinate of $M_{1}$ can be obtained by equations (21) and (22), and the result is 2.67, 1.69. Distance error between $M_{1}$ and true localization of T1 is received by step 4

$ε_{1} = \sqrt{{(4 - 2.67)}^{2} + {(3 - 1.69)}^{2}} = 1.87 m$ (28)

Figure 10.

The estimated localization ( $M_{1}$ ) of T1 utilizing AP1 and AP2.

Then, we estimate localization $M_{2}$ utilizing $M_{1}$ and AP3 according to equations (23) to (25). Just as the method, we also get estimation localization $M_{3}$ , $M_{4}$ , $M_{5}$ , $M_{6}$ , and $M_{7}$ as shown in Figures 11 to 13. The error of each estimation localization is calculated out after getting the coordinate of these points.

Figure 11.

The estimated localization ( $M_{2}$ ) of T1 utilizing $M_{1}$ and AP3, and the estimated localization ( $M_{3}$ ) of T1 utilizing $M_{2}$ and AP4.

Figure 12.

The estimated localization ( $M_{4}$ ) of T1 utilizing $M_{3}$ and AP4, and the estimated localization ( $M_{5}$ ) of T1 utilizing $M_{4}$ and AP5.

Figure 13.

The estimated localization ( $M_{6}$ ) of T1 utilizing $M_{5}$ and AP7, and the estimated localization ( $M_{7}$ ) of T1 utilizing $M_{6}$ and AP8.

The measurement results of T2, T3, and T4 are obtained with the same steps and methods as T1. If RSSI of AP is too weak, less than −90 dBm in general, for the MT to detect, it will be out of locating action. Therefore, all the APs assigned are effective to the test points, and the minimum RSSI is −55.9675 dBm in the measurement room. The mean RSSI values of eight APs at four test points are shown in Table 3, and the corresponding distances, calculated by formula (27), between APs and test points are shown in Table 4. One location point is confirmed by the first two APs; the follow-up location point is interrelated with the rest of six APs. Hence, the number of location point is seven determined by eight APs. The final location points of four test points in Room 402 are shown in Figure 14.

Table 3.

The mean RSSI (dBm) of eight APs at four test points.

	AP1	AP2	AP3	AP4	AP5	AP6	AP7	AP8
T1	33.4425	35.935	36.8275	52.7725	43.8425	27.7325	44.4425	48.3625
T2	45.19	24.105	27.8775	45.46	51.375	47.855	46.3825	44.9325
T3	34.705	29.3975	43.37	55.9675	32.775	31.59	42.4825	47.665
T4	51.555	43.0475	42.21	45.5375	53.9425	46.6375	24.2925	28.1775

RSSI: receive signal strength indicator; APs: anchor points.

Table 4.

The distance (m) between eight APs and four test points.

	AP1	AP2	AP3	AP4	AP5	AP6	AP7	AP8
T1	2.47	2.86	3.02	7.73	4.56	1.76	4.46	5.62
T2	4.94	1.42	1.78	5.02	7.12	5.79	5.3	4.87
T3	2.66	1.95	4.44	9.34	2.37	2.21	4.21	5.72
T4	7.2	4.36	4.15	5.05	8.29	5.38	1.44	1.81

APs: anchor points.

Figure 14.

Location points of four test points.

At the same time, the trilateration method, fingerprint method using K-NN algorithm, and maximum-likelihood method are also used at all test points as a comparison. In the trilateration method, three circles of trilateration are very critical with regard to each test point. The three APs we choose are not only the nearest to the test point but also surrounding the test point on the plane. The correlations of APs used for locating test points and each test point are (T1, AP1, AP2, AP6), (T2, AP2, AP3, AP4), (T3, AP1, AP2, AP6), and (T4, AP3, AP7, AP8). For each test point, the coordinate of one location point using trilateration method, and seven location points using BGI method are shown in Table 5. In order to achieve the fingerprint method, the testing room is divided into about 96 grids, and each grid is about 100 cm long and 97 cm wide. In the center of the grid, RSSI value was sampled each second and also continued for 3 min. The mean value of 180 RSSI values is the fingerprint data at each grid. Therefore, the whole fingerprint database consists of 96 RSSI mean values. It takes about 5 h to build this database. In the localization phase, K-NN (K = 8) algorithm is applied to match the MT position. Maximum-likelihood source localization algorithm is also used to compare with BGI method.

Table 5.

The measurement coordinates of location points.

	Trilateration	M1	M2	M3	M4	M5	M6	M7
T1	(3.28, 3.07)	(2.67, 1.69)	(3.6, 1.85)	(3.22, 1.9)	(3.02, 2.24)	(3.5, 3)	(3.66, 3.22)	(4.05, 3.4)
T2	(5.79, 2.3)	(6.14, 2.27)	(5.94, 2.24)	(5.8, 2.26)	(5.93, 2.16)	(6.42, 1.49)	(6.42, 1.6)	(6.57, 1.81)
T3	(3.27, 3.14)	(3.53, 1.84)	(3.33, 1.81)	(2.28, 1.93)	(1.82, 3.11)	(2.03, 3.4)	(2.63, 3.88)	(3.33, 4.1)
T4	(7.8, 6.49)	(8.33, 2.64)	(9.97, 2.92)	(9.57, 4.4)	(9.08, 4.52)	(8.94, 4.74)	(8.25, 5.38)	(8.07, 5.29)

The location error will be acquired by comparing the real coordinate and measurement coordinate. All errors are shown in Figure 15. For each test point, the error using trilateration method is $ε_{T 1} = 0.72 m$ , $ε_{T 2} = 1.31 m$ , and $ε_{T 3} = 1.39 m$ , $ε_{T 4} = 1.5 m$ ; error using fingerprint method is $ε_{F 1} = 0.35 m$ , $ε_{F 2} = 0.52 m$ , $ε_{F 3} = 0.65 m$ , and $ε_{F 4} = 0.35 m$ ; and error using maximum-likelihood method is $ε_{M 1} = 0.53 m$ , $ε_{M 2} = 0.67 m$ , $ε_{M 3} = 1.11 m$ , and $ε_{M 4} = 1.36 m$ . We can see that the location error has a decreasing trend along with the number of AP increased using BGI method; the minimum error is $ε_{\min 1} = 0.4 m$ , $ε_{\min 2} = 0.43 m$ , $ε_{\min 3} = 0.52 m$ , and $ε_{\min 4} = 0.3 m$ . The positioning accuracy is improved 44.4%, 67.2%, 62.6%, and 80% compared to trilateration method; −14.3%, 17.3%, 20%, and 16.7% compared to fingerprint method; and 24.5%, 35.8%, 53.2%, and 77.9% compared to maximum-likelihood method. The positioning accuracy of BGI method is significantly improved than trilateration and maximum-likelihood method. Although more works and more complex algorithm have to be done, the localization error of fingerprint method is even worse than the BGI we proposed. For measurement data of four test points, the standard deviation estimates are also changed using different number of APs as shown in Figure 16. In trilateration, fingerprint, and maximum-likelihood methods, the standard deviations are 0.35, 0.15, and 0.38, respectively; however, the minimum value is 0.09 using the BGI method. In the case of more than eight APs, the proposed BGI method is more stable and steady than the other three methods.

Figure 15.

Location error of BGI, trilateration, fingerprint, and maximum-likelihood method: (a) the error of three methods at T1, (b) the error of three methods at T2, (c) the error of three methods at T3, and (d) the error of three methods at T4.

Figure 16.

Standard deviations of four test points using trilateration method and BGI method.

Conclusion

In this article, we propose a BGI localization method based on greedy algorithm that achieves centimeter-level accuracy for indoor localization. The proposed BGI fully utilizes all effective APs in indoor Wi-Fi systems to improve the positioning accuracy. In the beginning of BGI, we analyzed four situations about the relationship of two circles. Four test points are adopted in the real indoor environment to examine the effectiveness of the BGI method. Comparing the traditional trilateration, fingerprint, and maximum-likelihood methods, the positioning accuracy using BGI method is enhanced 63.55%, 9.93%, and 47.85%, averagely. The trilateration method is relatively easy to implement; however, the localization accuracy is obviously lower than the BGI method. In the fingerprint method, the experiment room is divided into 96 grids, and data collection has already been cumbersome enough. Nevertheless, the localization accuracy is even worse than BGI. As can be seen, the method of BGI finds a balance point between the accuracy and the complexity. The structure of the algorithm makes it especially suitable for real indoor office environment.

Footnotes

Handling Editor: Paolo Barsocchi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This work is supported by the National Natural Science Foundation of China under Grant No. 61401360.

References

Küpper

Location-based services. Chichester: Wiley, 2005.

Yassin

Nasser

Awad

et al . Recent advances in indoor localization: a survey on theoretical approaches and applications. IEEE Commun Surv Tut 2017; 19: 1327–1346.

Monica

Ferrari

UWB-based localization in large indoor scenarios: optimized placement of anchor nodes. IEEE T Aero Elec Sys 2015; 51(2): 987–999.

Huang

C-H

Lee

et al . Real-time RFID indoor positioning system based on Kalman-filter drift removal and Heron-bilateration location estimation. IEEE T Instrum Meas 2015; 64(3): 728–739.

Yang

Luo

C-M.

Fuzzy adaptive Kalman filter for indoor mobile target positioning with INS/WSN integrated method. J Cent South Univ 2015; 22: 1324−1333.

Ren

Energy-efficient indoor localization of smart hand-held devices using Bluetooth. IEEE Access 2015; 3: 1450–1461.

Kim

Shin

Chon

et al . Smartphone-based Wi-Fi tracking system exploiting the RSS peak to overcome the RSS variance problem. Pervasive Mob Comput 2013; 9(3): 406–420.

Kang

Han

SmartPDR: smartphone-based pedestrian dead reckoning for indoor localization. IEEE Sens J 2015; 15(5): 2906–2916.

Nagpal

Rashidzadeh

. Indoor positioning using magnetic compass and accelerometer of smartphones. In: Proceedings of the 2013 international conference on selected topics in mobile and wireless networking (MoWNeT’13), Montreal, QC, Canada, 19–21 August 2013, pp.140–145. New York: IEEE.

10.

Choi

Chon

Kim

et al . Enhancing WiFi-fingerprinting accuracy using RSS calibration in dual-band environments. Pervasive Mob Comput 2016; 30: 45–57.

11.

Dardari

Closas

Djuric

PM.

Indoor tracking: theory, methods, and technologies. IEEE T Veh Technol 2015; 64(4): 1263–1278.

12.

Zou

Huang

et al . A robust indoor positioning system based on the Procrustes analysis and weighted extreme learning machine. IEEE T Wirel Commun 2016; 15(2): 1252–1266.

13.

Torteeka

Xiu

. Indoor positioning based on Wi-Fi fingerprint technique using fuzzy K-nearest neighbor. In: Proceedings of the 2014 11th international Bhurban conference on applied sciences and technology (IBCAST), Islamabad, Pakistan, 14–18 January 2014. New York: IEEE.

14.

Xie

Wang

Nallanathan

et al . An improved K-nearest-neighbor indoor localization method based on spearman distance. IEEE Signal Proc Let 2016; 23(3): 351–355.

15.

Figuera

Rojo-Alvarez

Wilby

et al . Advanced support vector machines for 802.11 indoor location. Signal Process 2012; 92: 2126–2136.

16.

Iglesias

Bernardos

Casar

. A Bayesian strategy to enhance the performance of indoor localization systems. In: Molina

Corredera

JRC

Pérez

MFC

et al . (eds) User-centric technologies and applications, vol. 94 (Advances in intelligent and soft computing). Berlin; Heidelberg: Springer, 2011, pp.79–92.

17.

Nerguizian

Despins

Affes

Geolocation in mines with an impulse response fingerprinting technique and neural networks. IEEE T Wirel Commun 2006; 5: 603–611.

18.

Mengual

Marban

Eibe

Clustering-based location in wireless networks. Expert Syst Appl 2010; 37: 6165–6175.

19.

Torteeka

Chundi

20.

Liu

H-H

W-H

Tseng

C-C

et al . A WiFi-based weighted screening method for indoor positioning systems. Wireless Pers Commun 2014; 79: 611–627.

21.

Rappaport

TS.

Characterization of UHF multipath radio channels in factory buildings. IEEE T Antenn Propag 1989; 37: 1058–1069.

22.

Mazuelas

Bahillo

Lorenzo

et al . Robust indoor positioning provided by real-time RSSI values in unmodified WLAN networks. IEEE J Sel Top Signa 2009; 3(5): 821–831.

23.