1.

Introduction

Over the past few decades, global positioning system (GPS) has found enormous application scenarios, for example navigation systems in cars, ships, planes, and mobile devices, land surveying, mapping, etc. Positioning technology has provided and is bringing even more convenience to daily life. Recently, indoor positioning has become a growing research area as location-based service is becoming more and more important in many indoor environments, such as museums, shopping malls, warehouses, and factories. Commonly used for outdoor environments, the GPS system, however, has a substantially downgraded performance indoors, which originates from the significant power attenuation when a satellite signal passes through walls and ceilings. Therefore, many radio-wave-based approaches are proposed for indoor environments. Radio-frequency identification technology is considered as one candidate for indoor positioning systems.¹ Position estimates are made by analyzing the pattern of detected sensor tags and comparing the signal strength. In cellular systems, a wave propagation model can be utilized to perform location estimation.² Moreover, ultrawideband (UWB) positioning systems have been experimentally tested by employing comparators to detect the UWB pulse signal.³ As one option for getting Internet access, a wireless local area network may be used for positioning purposes as well with propagation modeling and fingerprint matching techniques.⁴ Research also shows that the bluetooth range detection method is able to achieve high accuracy with the latest version of bluetooth technology.⁵ All the positioning techniques mentioned above can deliver positioning accuracies from within several meters to as high as within tens of centimeters.⁶

Visible light communication (VLC) technology employs fluorescent lamps and light-emitting diodes (LED), the latter of which will be more commonly used in the future considering many of its advantages, such as high lighting efficacy, longer life expectation, and environmental friendliness. Compared to fluorescent lamps, LEDs are easier to modulate at very high speed, which makes it possible for them to function as transmitters for indoor environments.⁷

Indoor positioning making use of the VLC technology infrastructure can offer several advantages. First, communications using radio-wave approaches is more vulnerable to multipath effects than visible light, which means a higher positioning accuracy may be achieved with VLC technology; second, in some environments such as hospitals and airplanes, radio frequency (RF) radiation is hazardous or even forbidden, while VLC-based approaches can fit in perfectly since no RF interference will be generated by LEDs. Last but not least, services can be provided universally so long as lighting infrastructures exist, thus hardware cost is minimized.

In positioning systems based on VLC technology, light sources are reference points and an optical receiver is colocated with the target for most of the cases. VLC positioning techniques, depending on the mathematical models they are associated with, can be categorized as follows: lateration, angulation, scene analysis, and proximity.

Systems based on lateration approaches estimate the distance between the transmitter and receiver. Distances are measured in several different ways such as time-of-arrival (TOA), time-difference-of-arrival (TDOA), and received signal strength (RSS). There is no positioning technique based on TOA measurements so far because it requires perfect synchronization between the transmitter and receiver, making the system unreasonably complicated. TDOA algorithms namely make use of measurements created by the time difference of several arriving signals. For example, the phase difference of signals can be utilized to derive TDOA information.⁸ RSS algorithms are widely investigated due to their simplicity in making position estimates, as shown in Refs. 9 and 10. Although most of the systems adopt time division multiaccess as a solution of channel multiaccess, an asynchronous system was proposed by Zhang and Kavehrad,¹¹ simplifying the system design.

Angulation is another approach to realize positioning, which always needs an image sensor to obtain angle-of-arrival information. Colored LEDs can be used to help the image sensor distinguish different light sources. The idea was experimentally tested and enabled accurate position control of a robot.¹²

Scene analysis is a method that collects fingerprints related to every position and maintains a database of these. By matching the target’s online measurements with fingerprints stored in database, position estimates are obtained. Using RSS information as fingerprints, scene analysis systems are capable of delivering a positioning accuracy around 1 cm.¹³

The principle of a proximity-based system is very straightforward. It relies on a grid made up of many reference points, each of which has a known position. When a mobile target receives a signal from a single-reference point, it is estimated that the target is colocated with the reference point. A hybrid positioning system with lighting LEDs and an ad-hoc wireless network infrastructure was proposed by Lee and Kavehrad.^14,15 Two methods based on noncarrier and a 4-MHz carrier were tested and results showed that with the help of the carrier technique, the system can have a working range up to 77-m long. Table 1 shows the comparison of the current indoor positioning systems mentioned above.^6,16

Table 1

Comparison of current indoor positioning systems.6,16

This paper presents an iteration algorithm to realize three-dimensional (3-D) indoor positioning and related filtering techniques. The algorithm makes use of RSS information and a trilateration technique and estimates the user’s position when he or she walks with the receivers in hand. Section 2 discusses the system configuration of the proposed system. The proposed algorithm, which realizes 3-D positioning, is then detailed in Sec. 3. Section 4 introduces filtering techniques and summarizes their realization. Results are presented in Sec. 5 followed by the related discussion. Finally, conclusions are addressed in Sec. 6.

2.

System Configuration

2.1.

System Design

Figure 1 depicts the proposed system configuration for a typical indoor environment. The room has dimensions of 6 m by 6 m, with a height of 4.2 m. There are four LED bulbs located on the ceiling, each of which acts as a single-optical transmitter. There is no limitation on the size of the room, and more LED bulbs are needed to satisfy the illumination and positioning requirements when in a larger place. Only three LEDs are enough to obtain the estimation, although four is proposed in the system for common utilization. Lighting bulbs are installed as a square, and this design will not change the basic configuration for an LED illumination system. Also, more LEDs can increase the measurement accuracy. Every bulb has a unique code assigned to it through which they can be distinguished. The LEDs are modulated in an on-off keying (OOK) format. The receiver is installed on a mobile device, and it moves to any height between 1 and 1.4 m, as shown in Fig. 1.

Fig. 1

System configuration with four transmitters and one receiver.

The optical links in the system are considered as line-of-sight links, thus the channel gain can be estimated by considering only the channel DC gain in the propagation path,¹⁷ which is

Eq. (1)

$$H(0)=\{\begin{array}{ll}\frac{m+1}{2\pi d^2}·A·{\cos }^m(\varphi )·T_s(\psi )·g(\psi )·\cos (\psi ),& 0\le \psi \le {\mathrm{\Psi }}_{\mathrm{c}}\\ 0,& \psi >{\mathrm{\Psi }}_{\mathrm{c}}\end{array},$$

where $A$ is physical area of the detector, $\psi$ is the angle of incidence with respect to the receiver axis, $T_s(\psi )$ is the transmission of the optical filter, and $g(\psi )$ is the concentrator gain, which for a compound parabolic concentrator is¹⁷

Eq. (2)

$$g(\psi )=\{\begin{array}{ll}\frac{n^2}{{\sin }^2({\mathrm{\Psi }}_{\mathrm{c}})},& 0\le \psi \le {\mathrm{\Psi }}_{\mathrm{c}}\\ 0,& \psi >{\mathrm{\Psi }}_{\mathrm{c}}\end{array},$$

where $n$ is the refraction index, ${\mathrm{\Psi }}_{\mathrm{c}}$ is the concentrator field-of-view semiangle, $\varphi$ is the angle of irradiance with respect to the transmitter perpendicular axis, and $d$ is the distance between the transmitter and receiver. The Lambertian order $m$ in Eq. (1) is given by $m=-\ln 2/\ln (\cos {\mathrm{\Phi }}_{1/2})$, where ${\mathrm{\Phi }}_{1/2}$ is the half power angle of the LED. The received optical power is given by $P_{\mathrm{r}}=H(0)·P_{\mathrm{t}}$, where $P_{\mathrm{t}}$ represents the transmitted power of the LED bulb.

2.2.

Channel Access Method

As the receiver should be able to obtain information from all four LED transmitters, the channel multiaccess problem has to be addressed. In this paper, an asynchronous protocol, called a basic framed slotted ALOHA (BFSA),¹¹ is employed. The BFSA protocol defines a frame structure composed of a fixed number of time slots. Suppose there are $l$ transmitters competing for $L$ slots. Each transmitter randomly selects a slot in the length of a frame to transmit data. This implies that $L\ge l$ must be satisfied.

Figure 2 demonstrates the working principle of BFSA in the case of $l=4$, shown within the frame structure of LED Bulb 1 and given no synchronization among transmitters. If each transmitter occupies a slot different from others as shown in Fig. 2(a), the transmission is defined as a success since the receiver can separate signals without any interference. If two or more transmitters select the same time slot, interference will happen and the receiver will not be able to distinguish signals emitted from different transmitters, which is considered to be a failure. As shown in Fig. 2(b), conflict happens within slot $i$ as Bulb 1 and Bulb 2 are both occupying it, leading to a transmission failure.

Fig. 2

Basic framed slotted ALOHA protocol (a) a successful transmission and (b) a transmission failure since two transmitters select the same slot.

For BSFA protocol without synchronization, the probability of successful transmission $P_{\mathrm{S}}$ given $l=4$ is shown in Fig. 3. $L=400$ is chosen to ensure on average the transmission will have a success rate of 97%.

Fig. 3

Probability of successful transmission versus number of slots per frame.

Identifications assigned to different LED bulbs are coded with a length of 128 bits, with 8 bits as the beginning flag, another 8 bits as the ending flag and a segment of 16-bits cyclic redundancy check to ensure the transmission reliability. As there are 400 slots and the sampling period is 0.05 s, the required transmission rate is

Eq. (3)

$$400\times (128+8+8+16)\mathrm{bit}/0.05\mathrm{s}=1.28\mathrm{Mbps},$$

which can be easily achieved using current LED devices.

3.

3-D Positioning Algorithm

Each of the LED bulbs in the system is modulated in OOK format, with a unique code related to its 3-D coordinates, which can be expressed as $(X^{(i)},Y^{(i)},Z^{(i)})$, $i=1$, 2, 3, 4 for the four LEDs. The following process is proposed to make the LEDs’ installation location as precise as possible: after Cartesian coordinates are set for the room and LEDs are installed in their predecided positions, measure the LEDs’ coordinates again and update them in the database. This process will largely decrease the LEDs’ installation errors but will not completely remove them, therefore, installation deviations are still taken into consideration in this paper. For each transmission, suppose $P_{\mathrm{t}}$ is the difference in the transmitted power between logic 0 s and 1 s, then $P_{\mathrm{t}}$ equals to 2 W as shown in Table 2, i.e., the modulation depth is 12.5%.

Table 2

Parameters of the system.

Denote $P_{\mathrm{r}}^{(i)}$ ($i=1$, 2, 3, 4) as the power difference in the received signals,. Then considering the optical channel with a DC gain in Eq. (1), their relationship is given as

The transmitter’s and receiver’s parameters are shown in Table 3, which can be applied to simplify Eq. (4) as

Table 3

Parameters of the transmitter and receiver.

As shown in Fig. 4, every group of measurements with respect to three LEDs leads to one trilateration estimation and one horizontal position estimate of the receiver is obtained. Since there are four LED bulbs involved, $C(\mathrm{4,3})=4$ estimations will be made and the final horizontal position estimate is defined as the average of these four estimations.

Fig. 4

Trilateration estimation.

After the horizontal position estimate of the receiver $(\widehat{x},\widehat{y})$ is obtained, the horizontal distances can be expressed as

Combining Eq. (10) with Eqs. (7) and (8), the estimated height is obtained as a solution of

By solving the above equation, at most two positive ${\widehat{h}}^{(i)}$ are obtained within a reasonable vertical range. In case there are two solutions, the one closer to $h_0$ is selected. Finally, the $z$-coordinate is

This iteration algorithm is applied based on the principle of trilateration so that the receiver is in the intersection region of the three circles as shown in Fig. 4. The difference between the presumed height and the actual one only has an influence on the radius of those circles, which means the intersection region may shrink or expand, while the region’s center remains almost unaffected. The estimation error comes from the nonuniformity of the noisy received signals, resulting in differing increases or decreases of the radii of the circles. However, as the receiver will not have significant vertical movement in a short sampling period, the algorithm holds valid. Regarding this, by increasing the sampling frequency, the vertical movement distance will decrease and will contribute to improving the positioning accuracy. The proposed algorithm is summarized as a flow diagram in Fig. 5.

Fig. 5

Flow diagram of three-dimensional (3-D) algorithm.

4.

Filtering Technology for Tracking

After measuring the receiver’s coordinates as mentioned in Sec. 3, two filters are applied to the system to realize real-time tracking of the target. A Kalman filter and sequential importance resampling (SIR) particle filter are employed in this paper. The noise model is the Gaussian white noise model, because the main sources of noise are thermal noise and the shot noise of the receiver.¹⁸

4.1.

Kalman Filter

A Kalman filter is a well-known technique and is now commonly used in positioning systems.¹⁹ It is an optimal solution of a Bayes filter based on the assumption that the posterior density is Gaussian. The principle of a Kalman filter is shown in Fig. 6.

Fig. 6

Principle of Kalman filter.

A Kalman filter includes two processes, namely prediction and correction. During the prediction phase, the current state is predicted as ${\widehat{s}}_k^{-}$ based on the last state ${\widehat{s}}_{k-1}$ and the input $u_k$, and a current covariance $P_k^{-}$ is predicted based on the covariance of the previous state $P_{k-1}$. There are three steps in the correction phase to modify these predictions: first, Kalman gain $K_k$ is computed from $P_k^{-}$, which can be considered as a weight between the prediction and measurement; second, state estimation ${\widehat{s}}_k$ is obtained using ${\widehat{s}}_k^{-}$, $K_k$ and measurement $m_k$; finally, error covariance $P_k$ is updated with $P_k^{-}$ and $K_k$. This recursive process continues and helps improve the accuracy over raw measurements.

In the proposed 3-D system, the $z$-component of the receiver’s position is independent of horizontal components; therefore, this filter process is separated into a horizontal phase and vertical phase. A Kalman filter is applied to the horizontal estimation first, following which the filtered result is used to obtain the $z$-coordinate. The detailed algorithm for the proposed system is as follows:

• 1. Initialize the Kalman filter based on the first horizontal measurement from the LED positioning algorithm in Sec. 3.

• 2. Make a prediction on the current state vector ${\widehat{s}}_k^{-}$, which is composed as position $({\widehat{x}}_k^{-},{\widehat{y}}_k^{-})$. This prediction is based on the previous position $({\widehat{x}}_{k-1},{\widehat{y}}_{k-1})$ and the velocity of the last state, after which the prediction on the covariance $P_k^{-}$ is made. The velocity is obtained by calculating the distance between the two most recent positions and is then divided by the sampling time.

• 3. Obtain the measurement value $(\widehat{x},\widehat{y})$ from Sec. 3.

• 4. Update the position estimate to $({\widehat{x}}_k,{\widehat{y}}_k)$ and covariance $P_k$ with the measurement value.

• 5. Substitute $({\widehat{x}}_k,{\widehat{y}}_k)$ back into the 3-D algorithm to obtain ${\widehat{r}}_k$.

• 6. Calculate ${\widehat{h}}_k$ and ${\widehat{z}}_k$.

Figure 7 shows the flow diagram of the Kalman filter in the proposed system. One drawback of the Kalman filter is that it assumes that the object state follows a Gaussian distribution. This approximation offers a poor estimate of variables which are not Gaussian. Another limitation is that the Kalman filter is only applicable to a linear process. Both limitations can be overcome with a particle filter, which is detailed in Sec. 4.2.

Fig. 7

Flow diagram of Kalman filter in proposed system.

4.2.

Particle Filters

An SIR particle filter is a Monte Carlo method which approximates the real posterior distribution with a set of weighted samples.²⁰ These samples propagate through the probabilistic model and provide estimates of the next state. The process is as follows. First, $N$ particles are generated by initializing state $s_0^i$ from $p(s_0)$ with equal weight $w_0^i=1/N$, $i=\mathrm{1,2},\dots ,N$. Second, $s_k^i$ is calculated from $s_{k-1}^i$ with a transition probability $p(s_k^i|s_{k-1}^i)$. Then, the weight $w_k^i$ is obtained by considering the measurement value $m_k$, previous state $s_{k-1}^i$, current states $s_k^i$ and previous weight $w_{k-1}^i$:

Eq. (13)

$$w_k^i=w_{k-1}^i\frac{p(m_k|s_k^i)p(s_k^i|s_{k-1}^i)}{p(s_k^i|s_{k-1}^i,m_k)}.$$

New calculated weights $w_k^i$ are normalized once obtained. Finally, the estimate of the current state can be expressed as

Eq. (14)

$${\widehat{s}}_k=\sum _{i=1}^N{w}_k^i·s_k^i.$$

One disadvantage of a particle filter in practice is that the weight of some particles will keep increasing during the iteration process in such a way that they will have significantly larger weights over all the other particles. This can lead to the so-called degeneracy problem, which can be overcome by a resampling process. Resampling resets the weight of $N$ particles to the initial value, which is $1/N$. Resampling effectively deals with the degeneracy problem, making the operation of a particle filter more stable.

In the proposed system, a particle filter is implemented according to the following steps:

• 1. Initialize $N$ particles $(x_0^i,y_0^i)$ with the weight $w_0^i$ equal to $1/N$.

• 2. Calculate $(x_k^i,y_k^i)$ from $(x_{k-1}^i,y_{k-1}^i)$, based on the stored step length and movement direction.

• 3. Take real-time measurement $(\widehat{x},\widehat{y})$ and update weight $w_k^i$:

  Eq. (15)

  $$w_k^i=w_{k-1}^i·\exp \{-[{(\widehat{x}-x_k^i)}^2+{(\widehat{y}-y_k^i)}^2]/{\sigma }^2\}.$$

• 4. Evaluate $1/\sum _{i=1}^N{(w_k^i)}^2$, if it is larger than a predetermined threshold, resample it by setting $w_k^i=1/N$.

• 5. Estimate the target position:

  Eq. (16)

  $$({\widehat{x}}_k,{\widehat{y}}_k)=\sum _{i=1}^N(w_k^i·x_k^i,w_k^i·y_k^i).$$

• 6. Update the step length for each particle.

• 7. Substitute $({\widehat{x}}_k,{\widehat{y}}_k)$ back into the 3-D algorithm to obtain ${\widehat{r}}_k$.

• 8. Calculate ${\widehat{h}}_k$ and ${\widehat{z}}_k$.

The flow diagram of the particle filter in proposed system is depicted in Fig. 8.

Fig. 8

Flow diagram of particle filter in proposed system.

5.

Results and Discussion

Inside the $6\times 6\times 4.2{\mathrm{m}}^3$ room model, a pseudo-Poisson path is generated with 262 samples, by assuming the mobile device moves across the room. This is defined as a real path, shown in Fig. 9 colored in black. Raw measurement values are represented by the red dots, with deviations reflecting measurement errors. The results of Kalman and particle filters are also shown in the figure in green and blue, respectively.

Fig. 9

3-D positioning results.

To demonstrate the results more clearly, horizontal and vertical views are plotted separately, as shown in Figs. 10 and 11. Root-mean-square (RMS) errors of the raw measurement, Kalman and particle filters are quantitatively shown in Table 4. In Fig. 10(b), the raw measurements are deviated from the real path with an RMS value of 0.068 m. After Kalman and particle filters are applied, the deviation drops as shown in Figs. 10(c) and 10(d), down to 0.057 and 0.054 m, respectively.

Fig. 10

Horizontal components of location estimates (a) real path, (b) raw measurement, (c) measured path after Kalman filter, and (d) measured path after particle filter.

Fig. 11

Vertical component of location estimates (a) real path and measurements, (b) real path and Kalman-filtered path, and (c) real path and particle-filtered path.

Table 4

Root-mean-square error of the 3-D system and filtering.

As for the vertical part, Fig. 11(a) shows that the raw measurements distribute around the real path and the RMS error is 0.083 m. Kalman and particle filters slightly improve the precision. As shown in Figs. 11(b) and 11(c), the estimates after filtering are closer to the real path, with RMS errors of 0.077 and 0.073 m, respectively. For the vertical estimation, the measurements are more precise in the center region than at both ends of the path as shown in Fig. 11. When the receiver is close to the center of the room, light intensities are more uniform with respect to different LED bulbs, contributing to a higher accuracy. The vertical positioning accuracy can be improved by employing the LED bulbs’ layout with a more uniform light intensity distribution. When performing 3-D positioning, an overall accuracy of 0.107 m can be achieved by raw measurements, while Kalman and particle filters improve the accuracy to 0.096 and 0.090 m, as shown in Table 4.

Figure 12 depicts the 3-D positioning results when there is a large deviation in the measurement, and the performance of the Kalman and particle filters in this situation.

Fig. 12

3-D positioning result of the path with large deviation (circled dot).

Figures 13 and 14 show the horizontal and vertical components separately, with the RMS error shown in Table 5. The circled red spot circled shows where the large deviation happens. This is usually referred to as a “wild value” in sensor systems. When the Kalman filter is applied, the path starts to diverge after the large deviation. It takes several steps before the path converges. However, the path after applying the particle filter is almost unaffected, as shown in Fig. 13(c). The horizontal RMS error decreases from 0.116 m in raw measurement to 0.084 m after applying the Kalman filter and to 0.053 m after applying the particle filter.

Fig. 13

Horizontal component of positioning system with large deviation (a) raw measurement, (b) measured path after Kalman filter, and (c) measured path after particle filter.

Fig. 14

Vertical component of the positioning system with large deviation. (a) Real path versus measurement values. (b) Real path versus Kalman-filtered path. (c) Real path versus particle-filtered path.

Table 5

Root-mean-square error of the 3-D system and filtering with large deviation.

In Fig. 14, with respect to the vertical component of position estimates, Kalman and particle filters help to decrease the RMS error from 0.086 to 0.079 m and 0.074 m, respectively.

The overall positioning accuracy based on raw measurements in the presence of a large deviation is 0.143 m, while the Kalman filter can bring it down to 0.115 m; with the help of particle filter, it can be further reduced to 0.091 m.

6.

Conclusions

This paper proposed a 3-D positioning algorithm based on RSS information and a trilateration technique. BFSA protocol is applied as the channel access method to simplify the system configuration, bringing down the overall cost. For a mobile device with a designed optical receiver in a room, an overall positioning accuracy in the order of several to tens of centimeters can be expected. To achieve even higher accuracies, two filtering techniques are investigated. After Kalman and particle filters are applied, the accuracy can be improved to 0.096 and 0.090 m, respectively. The latter helps the system perform more stably by enhancing the immunity to large deviations.