1.

Introduction

Nowadays, with the rapid development of wireless sensor network and physical networking technology, demands for location-based services gradually present a significant growth trend.^1–3 In the field of positioning, global positioning system (GPS) is well known for its wide coverage and low cost of application. GPS has found an increasingly wide utilization in many situations, such as vehicle navigation, map service, and so on. For outdoor environment, GPS has provided satisfactory services; however, it has low accuracy in indoor positioning.⁴ GPS is still far from a perfect system in the field of positioning when it comes to a situation that indoor environment for radio signals from a satellite will be blocked by tall buildings, causing big positioning error. To meet the increasing need of indoor positioning service, wi-fi, bluetooth, radio frequency identification (RFID), and camera-based positioning systems have been developed to complement GPS. All positioning systems mentioned above can provide a position precision from tens of centimeters to several meters and some of them have already been used in indoor environment. However, due to the disadvantages of high cost, low positioning accuracy, electromagnetic interference, and other factors, the schemes above are not ideal candidates.⁵ Those solutions of indoor positioning have the following disadvantages: (1) to install these systems, extra device should be added to an indoor environment, which increases the cost and complexity of operation and control. (2) In some RF-inappropriate environments, such as an underground mine, radio-based indoor positioning systems do not work at all. (3) The uneven spatial distribution of wireless signal leads to an intense volatility at a same location, which results in a reduction of positioning accuracy. (4) These radio-based positioning systems will produce the electromagnetic interference to the indoor electronic device such as an MRI scanner in a hospital, so some particular places cannot allow these systems to work. (5) The confidentiality of radio-based communication system is usually not high, which may lead to a location information leakage.

Visible light communication (VLC)-based positioning is a new solution of indoor positioning, which has the advantages of high positioning, no electromagnetic interference, fewer extra modules, good communication confidentiality, and realization of integration of lighting and communication. Positioning systems based on VLC can be divided into many formats: (1) photodiode-based (PD-based), (2) image sensor-based,^6,7 and (3) solar cell-based.⁸ As an image sensor-based positioning system usually needs to use an image processing technique, which sets a great demand on system performance and solar cell based is not often used, the simplicity, reliability, and low cost of a PD-based positioning system show wide application in indoor positioning field. For example, Hsu et al.⁹ demonstrated a $3\times 3$ imaging MIMO VLC system using white light-emitting diodes (LEDs) and low-cost PIN PDs, which can achieve 1 Gbps data rate over 1-m free-space transmission distance. In PD-based systems, the receiver collects optical signal from signal sources to estimate the distance between itself and the signal sources using a series of methods of received signal strength (RSS),^10,11 angle of arrival (AOA),¹² time of arrival (TOA),¹³ time difference of arrival (TDOA),^14,15 and so on. Among these methods introduced, TOA and TDOA are immune to noise, and the AOA measures the distance by the angle of received signal, whereas this is difficult to achieve in reality for the layout of transmitters, and the receiving range of a PD brings a dramatic effect on the AOA measured, which results in a big error in positioning accuracy. Instead, the RSS detects the distance only according to the RSS, which can reduce the complexity of the circuit of transmitters while ensuring the localization accuracy of the premise. At the same time, for a receiver, it is easy to measure the signal strength using an AD converter. Hence, RSS is studied deeply. For example, Yang et al.,¹⁶ proposed an indoor positioning system using single transmitter and multiple receivers, the device can find its location using RSS and the relative position of optical receivers, the average positioning error was reported to be 0.65 cm. Jung et al.¹⁷ defined received signal strength ratio (RSSR) between received signals, three equations could be obtained using the distance ratios, which is a function of RSSR, the target can be located by solving the equations. The methods above both achieve satisfied precision; however, they fail to give the height information.

Three-dimensional indoor positioning has been done by some predecessors. For example, Hou et al.¹⁸ used only an LED lamp with RSS and AOA algorithm to achieve 3-D positioning, and its positioning error is 10.2 cm. In this article, the positioning accuracy is high, but the hybrid algorithm is used for positioning, which is complex in calculation. Yasir et al.¹⁹ used the light sensor and accelerometer of the smart phone to measure the light intensity and locate the smart phone combined with the low complexity algorithm, and the error $<25\mathrm{cm}$ is achieved. This method needs to add some additional devices, which increases the cost. Lim²⁰ proposed a maximum likelihood approach for the positioning system and enhanced the positioning performance by employing an iterative maximum likelihood approach by adopting the least square solution as an initial guess, and the accuracy is not high. Wu et al.²¹ built a simplified 3-D fingerprint database in the condition of linear light-intensity attenuation model and combined fingerprint database method with the iterative algorithm to achieve 3-D positioning whose error is 4.1 cm in $X–Y$ plane, and the $z$ direction error is 5.4 cm. The method achieves satisfied precision, but this method needs to build a fingerprint database first. So far, the results of 3-D positioning are not satisfactory.

To actualize the indoor positioning using visible light, the problem that should be solved first is the interference of optical communication. The introduction of a multiple access technique is necessary. In consideration of the possibility of many LEDs existing in an indoor environment at the same time, the frequency bands will be divided into different sub channels which have different bandwidth when using the frequency division multiple access resulting in the difficulty of filter design. As for the time division multiple access, it will be difficult to control the transmitters for the communication time slot, which will be short when there are too many LEDs. The code-division multiple access (CDMA) modulation can separate the signal overlapping both in time domain and frequency domain, and the spread spectrum technology in CDMA can also reduce the intersymbol interference caused by the presence of multipath effect indoor. Therefore, CDMA can improve communication quality and increase system stability. In this article, CDMA is used to modulate ID information, which is transmitted from different LEDs. The CDMA technique is not described in detail in this article, if readers are interested in CDMA technique, you can refer to our previous article.^22–24

In view of the fact that the existing 3-D indoor positioning is not effective, we propose a 3-D high-precision indoor positioning strategy using Tabu search^25,26 for 3-D visible light indoor positioning. Tabu search is a powerful global optimization algorithm, and the 3-D indoor positioning can be transformed into an optimal solution problem. Therefore, in the 3-D indoor positioning, the optimal receiver coordinate can be obtained by the Tabu search algorithm and this is the first time the Tabu search algorithm is applied to visible light positioning. The algorithm restricts the search process falling into local optimization using Tabu strategy to avoid roundabout search. And the algorithm adds amnesty criterion to get the appropriate positioning coordinate, so the amnesty criterion ensures the effectiveness and diversity of the process in searching for optimal positioning coordinate. When the fitness value satisfies the condition, the optimal coordinate is obtained. Compared with existing 3-D positioning system, it has higher accuracy and does not need additional devices. The results show that while using the Tabu search algorithm for 3-D indoor positioning, the maximum error is 5.88 cm and the mean error is 0.79 cm.

The rest of this article is arranged as follows: Sec. 2 introduces the system model of indoor visible light positioning, proposes the Tabu search algorithm, and shows how to use the Tabu search algorithm for 3-D indoor positioning. Section 3 shows the simulation and experimental results. Section 4 draws the conclusion of this article.

2.

System Principle and Positioning Algorithm

2.1.

Indoor Wireless Optical Channel

The indoor visible light positioning model is shown in Fig. 1. Four LEDs are installed at the ceiling of the room, and the receiver is located at a certain height of the room. Each LED sends localized ID information, which is modulated in CDMA, and the receiver converts the optical signal into a certain size electric signal according to the conversion efficiency of photoelectric detector (PD). In this article, LED is a Lambertian light source, so line-of-sight channel gain of this visible light indoor positioning system can be given by²⁷

Eq. (1)

$$H{(0)}_{\mathrm{LOS}}=\{\begin{array}{ll}\frac{(m+1)A_r}{2\pi d^2}{\cos }^m(\theta )\cos (\psi )T_s(\psi )G(\psi ),& 0\le \psi \le \mathrm{FOV}\\ 0,& \psi \ge \mathrm{FOV}\end{array},$$

where $A_r$ is the effective area of the PD. $d$ is the distance between the LED and the receiver. $\theta$ is the irradiant angle relative to the vertical axis of the LED. $\psi$ is the incident angle relative to the receiving axis. $T_s(\psi )$ is the gain of optical filter, and $G(\psi )$ is the gain of optical concentrator. FOV is the field of view of the receiver. $m$ indicates the order of Lambert’s luminous intensity, which can be given by the following equation:²⁸

Eq. (2)

$$m=-\frac{\ln 2}{\ln [\cos ({\theta }_{1/2})]},$$

where ${\theta }_{1/2}$ is the half-power angle of the transmitter (LED).

Fig. 1

Indoor visible light positioning system.

The following discussion is about $0\le \psi \le \mathrm{FOV}$. The received optical power $P_r$ can be represented as

Eq. (3)

$$P_r=H{(0)}_{\mathrm{LOS}}·P_t=\frac{(m+1)A_r}{2\pi d^2}{\cos }^m(\theta )\cos (\psi )T_s(\psi )G(\psi )P_t,$$

where $P_t$ is the average transmitted optical power.

In the room model, the coordinate of LED is ($x_t,y_t$, and $z_t$, and the coordinate of receiver coordinate is $x_r,y_r$, $z_r$). Thus, the irradiant angle $\theta$ can be represented as²⁹

Eq. (4)

$$\cos (\theta )=\frac{z_t-z_r}{{[{(x_t-x_r)}^2+{(y_t-y_r)}^2+{(z_t-z_r)}^2]}^{\frac{1}{2}}}.$$

Since it is assumed that the plane at which the receiver is located is parallel to the ceiling, the incident angle $\psi$ is equal to the irradiant angle $\theta$. $\cos (\psi )=\cos (\theta )$. Equation (3) can be expressed as the following equation:

Eq. (5)

$$P_r=\frac{(m+1)A_r}{2\pi }{T}_s(\psi )G(\psi )\frac{{(z_t-z_r)}^{m+1}}{{[{(x_t-x_r)}^2+{(y_t-y_r)}^2+{(z_t-z_r)}^2]}^{\frac{m+3}{2}}}{P}_t.$$

We can also simplify Eq. (5) to

Eq. (6)

$$P_r=R\frac{{(z_t-z_r)}^{m+1}}{{[{(x_t-x_r)}^2+{(y_t-y_r)}^2+{(z_t-z_r)}^2]}^{\frac{m+3}{2}}}{P}_t,$$

where

Eq. (7)

$$R=\frac{(m+1)A_r}{2\pi }{T}_s(\psi )G(\psi ),$$

$R$ is a constant obtained in the VLC-positioning system. The distance between the LED and the receiver $d$ can be expressed as

Eq. (8)

$$d={[{(x_t-x_r)}^2+{(y_t-y_r)}^2+{(z_t-z_r)}^2]}^{\frac{1}{2}},$$

$d$ can eventually be represented as

Eq. (9)

$$d={\left[\frac{R{(z_t-z_r)}^{m+1}{P}_t}{P_r}\right]}^{\frac{1}{m+3}}.$$

In the VLC system, the total variance of the system channel noise ${\sigma }_{\text{noise}}^2$ obeys the Gauss distribution, which is the sum of shot noise and thermal noise³⁰

Eq. (10)

$${\sigma }_{\text{noise}}^2={\sigma }_{\text{shot}}^2+{\sigma }_{\text{thermal}}^2,$$

${\sigma }_{\text{shot}}^2$ is caused by the optical power including the effective signal strength and the lighting environment, and ${\sigma }_{\text{thermal}}^2$ is caused by random motion of electrons. The signal-to-noise ratio of the VLC positioning system can be expressed as

Eq. (11)

$$\mathrm{SNR}=10{\log }_{10}\left(\frac{P_r}{{\sigma }_{\text{noise}}^2}\right).$$

2.2.

Three-Dimensional Positioning Algorithm Based on Tabu Search

First of all, we are going to introduce the Tabu search algorithm. Its essence is to search the solution space according to a certain rule until it searches for the approximate optimal solution or the optimal solution, and it belongs to the global optimization algorithm. In the application of 3-D indoor positioning, the solution space is positioning coordinates, which is in the room. During the search process, one solution produces a certain number of neighbor solutions according to a specific equation. Candidate solution is the best solution selected from neighbor solutions according to fitness value. The Tabu list is a container used to store the taboo object. The taboo object is an element placed in the Tabu list, and the element is the positioning coordinates in the application of 3-D indoor positioning. The taboo object in Tabu list cannot be searched again until the taboo is lifted. The Tabu list simulates human memory mechanism, so it prevents search from being trapped into local optimization to explore more search space. The taboo length is the maximum number of taboo objects stored in the Tabu list. When the number of taboo objects exceeds the taboo length, the taboo object, which got into Tabu list first should be removed before storing a new taboo object. The amnesty criterion is that the positioning coordinate of the receiver is output directly when the fitness value satisfies certain condition.

Four LEDs installed at the ceiling of the room send localized ID information. Different ID information modulated in CDMA technology and then is received by PD. When the received optical power is detected by PD, the best positioning coordinate can be obtained using the Tabu search algorithm.

• Step 1. Initializing the current estimated location $x_{\text{now}}=(x_e,y_e,z_e)=(0,0,0)$, and the current best location $x_{\text{best}}=(x_b,y_b,z_b)=(\mathrm{0,0},0)$. Setting upper bound $x_u=4$ and lower bound $x_l=0$, which is used in equation producing a certain number of neighbor locations. Setting taboo length $L=13$, attenuation factor $\text{scale}=1$, and maximum number of iteration $G_{\max }=2000$. Emptying the Tabu list. Then go to step 2.

• Step 2. From Eq. (9), we learn that the distance between the LED and the receiver can be expressed as

  Eq. (12)

  $$d_e^{(i)}={\left[\frac{R{(z_t-z_e)}^{m+1}{P}_t}{P_r^{(i)}}\right]}^{\frac{1}{m+3}},$$
  where $z_t$ is the height of LED and also the height of the room. $d_e^{(i)}$ is the distance between the receiver and LED $(i)$ $(i=\mathrm{1,2},\mathrm{3,4})$. $P_r^{(i)}$ is the received optical power detected by PD.

  The coordinate of $\mathrm{LED}(i)$ is $x_{\mathrm{LED}(i)}=[x^{(i)},y^{(i)},z_t],(i=\mathrm{1,2},\mathrm{3,4})$. The distance between the current estimated location $x_{\mathrm{now}}$ and $\mathrm{LED}(i)$ can be represented as

  Eq. (13)

  $$d^{(i)}=\sqrt{\{{[x_e-x^{(i)}]}^2+{[y_e-y^{(i)}]}^2+{(z_e-z_t)}^2\}}.$$
  $\mathrm{\Delta }(i)$ is defined as

  Eq. (14)

  $$\mathrm{\Delta }(i)={[d^{(i)}-d_e^{(i)}]}^2$$
  So, we get the fitness value

  Eq. (15)

  $$\text{fit}={\sum }_{i=1}^{i=4}\mathrm{\Delta }(i).$$
  If $\mathrm{fit}<1\times {10}^{-5}$, then we output the current estimated location $x_{\text{now}}$ as the final location coordinate. If $\mathrm{fit}\ge 1\times {10}^{-5}$, then go to step 3. At the same time judging if the number of iterations is maximal, and if the number of iterations is maximal, go back to step 1.

• Step 3. We know that the current estimated location is $x_{\mathrm{now}}=(x_e,y_e,z_e)$, and we use $x_{\text{now}}$ to generate neighbor locations $x_{\text{near}(j)}=[x_n^{(j)},y_n^{(j)},z_n^{(j)}]$, $(j=\mathrm{1,2},3,\dots ,20)$. In this step, it is necessary to update the value of   scale

  Eq. (16)

  $${\text{scale}}_{\text{next}}={\text{scale}}_{\text{last}}*0.998.$$
  That is, the next scale value is 0.998 times the scale value in the last iteration loop.

  So, we get $x_{\mathrm{near}(j)}$ through this equation

  Eq. (17)

  $$\{\begin{array}{c}{x}_n^{(j)}=x_e+\text{rand}*\text{scale}*(xu-xl)\\ y_n^{(j)}=y_e+\text{rand}*\text{scale}*(xu-xl),\\ z_n^{(j)}=z_e+\text{rand}*\text{scale}*(xu-xl)\end{array}$$
  rand is a random value in the range of [$-\mathrm{1,1}$]. First, we calculate the fitness value of 20 neighbor locations ${\mathrm{fit}}_{\text{near}}$, then from 20 neighbor locations we select the one with the minimum ${\mathrm{fit}}_{\mathrm{near}}$ as the candidate location $x_{\text{candidate}}$. And we calculate the fitness value of the candidate location ${\mathrm{fit}}_{\text{candidate}}$. Then, go to step 4.

• Step 4. First, we calculate the fitness value of the current best location ${\text{fit}}_{\text{best}}$. If ${\mathrm{fit}}_{\text{candidate}}<{\mathrm{fit}}_{\text{best}}$, then we make $x_{\text{best}}=x_{\text{candidate}},x_{\text{now}}=x_{\text{candidate}}$, and add the candidate location $x_{\text{candidate}}$ into Tabu list. If the number of taboo objects exceeds the taboo length, remove the taboo object, which got into Tabu list first, and then go back to step 2. If ${\mathrm{fit}}_{\text{candidate}}\ge {\mathrm{fit}}_{\text{best}}$, then go to step 5.

• Step 5. First, we judge whether the candidate location is in Tabu list. If the candidate location is in the Tabu list, the current estimated location $x_{\text{now}}$ remains unchanged, and then go back to step 2. If the candidate location is not in the Tabu list, make $x_{\text{now}}=x_{\text{candidate}}$, and add the candidate location $x_{\text{candidate}}$ into Tabu list. If the number of taboo objects exceeds the taboo length, remove the taboo object, which got into Tabu list first, and then go back to step 2.

The framework of the proposed the Tabu search algorithm for 3-D positioning is shown in Fig. 2.

Fig. 2

Framework of the Tabu search algorithm for 3-D positioning.

3.

Simulation and Analysis

3.2.

Result and Discussions

To estimate the performance of the Tabu search algorithm in 3-D indoor positioning, in this section, a multipoint positioning test is adopted and the positioning is performed at different heights. As shown in Fig. 3, the resolution of the real tested position point is 0.5 m, so there are 25 real tested position points in every plane, which are represented by “×.” And the position point calculated by Tabu search is represented by “$\mathrm{\Delta }$”. In this test, positioning tests are performed at 10 different heights of the plane. The height was set to 0.2, 0.4, 0.6, 0.8, 1, 1.2, 1.4, 1.6, 1.8, and 2 m, respectively, as shown in Figs. 3(a)–3(f).

Fig. 3

Distribution of the real position point and its TS estimated position point: (a)–(j) is the positioning result of 0.2, 0.4, 0.6, 0.8, 1, 1.2, 1.4, 1.6, 1.8, and 2 m, respectively.

The result shows that the 3-D positioning is good, and the real position is very close to the position estimated by the Tabu search algorithm. To assess the performance of a positioning system more accurately and directly, we conduct further quantitative analysis.

The positioning error is defined as the linear distance between the real position and the estimated position. When the positioning error is calculated, the 3-D error map of different height is obtained, as shown in Fig. 4. The abscissa axis of Fig. 5 shows the height of Z-axis, and the vertical axis represents the average error between 25 tested point and its estimated point in different heights.

Fig. 4

Three-dimensional error of different heights: (a)–(j) is the 3-D error of 0.2, 0.4, 0.6, 0.8, 1, 1.2, 1.4, 1.6, 1.8, and 2 m, respectively.

Fig. 5

Mean error of different heights.

As we can see from Fig. 4, when the height is 0.2 m, the maximum error is 0.96 cm and the average error is 0.60 cm; when the height is 0.4 m, the maximum error is 1.20 cm and the average error is 0.55 cm; when the height is 0.6 m, the maximum error is 0.87 cm and the average error is 0.52 cm; when the height is 0.8 m, the maximum error is 0.88 cm and the average error is 0.55 cm; when the height is 1 m, the maximum error is 1.28 cm and the average error is 0.55 cm; when the height is 1.2 m, the maximum error is 1.45 cm and the average error is 0.62 cm; when the height is 1.4 m, the maximum error is 1.79 cm and the average error is 0.81 cm; when the height is 1.6 m, the maximum error is 1.53 cm and the average error is 0.74 cm; when the height is 1.8 m, the maximum error is 3.18 cm and the average error is 1.17 cm; when the height is 2 m, the maximum error is 5.88 cm and the average error is 1.83 cm; by analyzing the above data we can know when the height is low, the error of different heights is basically the same; when the height rises to a certain height, the error significantly increased with an increase in the height. It is because when the height is high, the irradiant angle $\theta$ of LED and the incident angle $\psi$ of PD will increase, and when they increase to a certain extent, the luminous intensity of LED is weakened, and the optical power received by PD will be reduced, which leads to the increase in the error of the received optical power. Therefore, when the height is high, the 3-D error will increase significantly. Figure 5 is the line chart for the average error between 25 tested points and its estimated point in different heights. It can be seen that the error will increase significantly when the height is higher.

Figure 6 is the histogram of error between 250 tested positioning points and its TS estimated positioning point in multipoint positioning test. The maximum error is 5.88 cm, and the average error is 0.79 cm, and most of the positioning errors are below 1 cm. Figure 7. is the cumulative distribution function (CDF) curves of position errors. From Fig. 7, we can see that 95.2% positioning errors are below 1.791cm. The results show that the effect of the Tabu search algorithm for 3-D positioning is good, the average error can reach mm level.

Fig. 6

Histogram of position errors.

Fig. 7

The CDF curves of position errors.

3.3.

Extended Simulation and Result Analysis

To evaluate the performance of the Tabu search algorithm in real-time positioning, an extended simulation experiment of trajectory tracking is carried out. The system parameters of the trajectory tracking simulation are just the same as the parameters shown in Sec. 3.1. First, we generate a random curve. Then, we track the random trajectory with 101 positioning points.

As shown in Fig. 8, the black line represents the random trajectory, and the red “*” represents the positioning tracking of the trajectory. To better display the tracking effect, Figs. 9 and 10 show the results in a horizontal view and vertical view, respectively. We can see that the tracking effect is good.

Fig. 8

3-D position in trajectory tracking.

Fig. 9

The horizontal positioning result of trajectory tracking.

Fig. 10

The vertical positioning result of trajectory tracking.

To directly perform the result of 3-D positioning, the histogram of positioning error and the CDF curves of position error in trajectory tracking are shown in Figs. 11 and 12, respectively. As shown in Fig. 11, most of the positioning errors in trajectory tracking are below 1 cm, and with an increase in the height of the trajectory, the positioning error is larger than 2 cm, which is consistent with the analysis in Sec. 3.2. From Fig. 12, we can see that 95.05% positioning errors in trajectory tracking are below 1.428 cm. It can be concluded from the above results that using the Tabu search algorithm for trajectory tracking effect is good and further proved that the Tabu search algorithm for indoor 3-D positioning is good.

Fig. 11

Histogram of position error in trajectory tracking.

Fig. 12

The CDF curves of position error in trajectory tracking.

4.

Conclusion

In this work, a 3-D high-precision indoor positioning strategy using Tabu search is proposed. With the advantage of the global optimization of the Tabu search algorithm, high-precision 3-D indoor positioning can be achieved. It is the first time that the Tabu search algorithm is applied to visible light positioning, which is innovative. Each LED sends localized ID information, and when the receiver PD detects optical signals with ID information from different LEDs, the Tabu search algorithm is used to locate the PD. The experiment results show that the positioning effect is good, which is superior to the existing indoor 3-D positioning.

In the dimension of $3\mathrm{m}\times 3\mathrm{m}\times 4\mathrm{m}$, static multipoint positioning test was carried out first. The data show that the maximum error is 5.88 cm, and the average error is 0.79 cm in 250 tested positioning points. Most of the positioning errors are $<1\mathrm{cm}$. Among them, 95.2% of the positioning errors are below 1.791 cm. Then, the dynamic trajectory tracking was done next. The data show that the vast majority of the positioning errors are $<1\mathrm{cm}$, and 95.05% of the positioning errors are below 1.428 cm. Both static multipoint positioning test and dynamic trajectory tracking experiment show that the Tabu search algorithm has a good effect in 3-D positioning. The 3-D indoor positioning based on the Tabu search algorithm has potential application value in various indoor positioning scenes.