Given the special underground geographic model, the algorithm based on location fingerprints [2L. Xiaowen, Z. Xiujun, and H. Lina, "Research on underground location algorithm based on WI-FI", J. Transducer Technol., vol. 26, pp. 854-858, 2012.] locates with higher accuracy than the algorithm based on trilateration survey [7L. Henghui, and L. Xingchuan, "Comparison of WiFi location based on triangle and location fingerprint recognition algorithm", Mobile Commun., vol. 34, pp. 72-76, 2010.].

In geometry, trilateration is the process of determining absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In three-dimensional geometry, when it is known that a point lies on the surfaces of three spheres, then the centres of the three spheres along with their radii provide sufficient information to narrow the possible locations down to no more than two (unless the centres lie on a straight line).

While Fingerprint algorithm locates with two phases: offline training phase and online locating phase [8L. Lun, D. Enjie, and H. Lina, "An improved coal mine fingerprint matching localization algorithm", J. Sens. Technol., vol. 34, pp. 72-76, 2010., 9B. Li, I. Quader, and A. Dempster, "On outdoor positioning with Wi-Fi", J. Glob. Position. Syst., vol. 7, pp. 18-26, 2008.
[http://dx.doi.org/10.5081/jgps.7.1.18] ]. Fig. (1) shows the details of these two phases.

Fig. (1) Location frame of the fingerprint algorithm.

In offline training phase, it firstly chooses reference locations, measures the RSSI values from different communication base stations. Then, it calculates the measured values with Kalman filter, stores the results with related reference locations and MAC addresses of base stations into a fingerprint database. It repeats all the above steps till all the reference locations have been measured.

In online locating phase, it firstly measures the RSSI and related MAC address of a communication base station at the location to be located. Then, it matches the location with the reference locations in fingerprint database by the Nearest Neighbour algorithm [10A. Kushki, K.N. Plataniotis, and A.N. Venetsanopoulos, "Kernel-Based positioning in wireless local area networks", IEEE Trans. Mobile Comput., vol. 6, pp. 689-705, 2007.
[http://dx.doi.org/10.1109/TMC.2007.1017] , 11G. Sinan, "A survey on wireless position estimation", Wirel. Pers. Commun., vol. 44, pp. 263-282, 2008.
[http://dx.doi.org/10.1007/s11277-007-9375-z] ] (NN). It uses Euclidean distance formula to calculate the distance between the location to be located and its neighbors. Formula (1) is the Euclidean distance formula. It takes the location of the nearest neighbor as the location of the one to be located.

(1)

In formula (1), R_i is the signal strength vector of the i^th reference location., represent the signal strength of the k^th base station measured at the i^th reference location. is the vector of the unknown point to be located., T (t₁, t₂, t_n), t_k, (k ϵ (1, n)) represents the signal strength of the k^th base station measured at the unknown point. l (R_i, T) represents the Euclidean distance between the unknown point and the reference location.

Doherty et al. proposed a location algorithm based on convex optimization [12P. Li, “Wireless Sensor Network Technology”, Metall. Press: Ind., 2011.-14"L. El Ghaoui, “Convex position estimation in wireless sensor networks", In: 20^th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, 2001, pp. 1655-1663 ]. They take the communication connection between nodes as a geometric constraint. Hence take the whole communication network as a convex set. They found that the location problem could be translated into a convex optimization problem. They can locate an object according to the global optimal solution of convex optimization problem.

As shown in Fig. (2), according to the communication between unknown nodes and reference locations (labelled by O₁, O₂, O₃ separately algorithm) and nodes in wireless range, we take advantage of the proximity and nodes joint information to regard the network as convex model so as to transmit the location problem to convex optimization problem. Finally, we can calculate unknown node position in the area (the slash shadow area in the figure) by LP or SDP. So we can get a rectangular area, with regard to the centroid of the rectangle as the unknown node location.

Fig. (2) Convex optimization location algorithm.

Kalman filter is commonly used in inertial navigation systems for signal filtering. This section presents an overview of the basic Kalman filter. KF output is calculated using state space representation of the input and various other parameters. Process noise covariance matrix and measurement noise covariance matrix are the main two parameters that affect the output of KF. There are several variants of the KF based on the way the values of and are estimated. In the basic KF fixed values of and are considered to filter the signal by assuming that the process noise and measurement noise characteristics are statistically known. The de-noising process using Kalman filter has two stages:

1. The first stage predicts the current state and the error covariance based on previous state estimate.
2. The second stage corrects the previous predicted values using the present measured value.

When locating in coal mines, if reference locations are selected sparsely, NN algorithm locates with obvious errors. To locate with higher accuracy, we propose an algorithm based on convex sets of RSSI to locate coal miners underground. The algorithm uniformly selects reference locations for the location to be located. It calculates the mass centre of the convex sets defined by the selected candidates, takes the location of the mass centre as the one to be located. Alg. (1) shows the model of the proposed algorithm.

Step 1: Select reference candidates

Taking the location to be located as an unknown point, the algorithm firstly measures the strength of the RSSI signals from different base stations at the unknown point.

Then, it calculates the distance between the unknown points and each reference location in a fingerprint database. It takes the first m reference locations which are the nearest m locations to the unknown points. The algorithm uses Euclidean distance formula to calculate the distance between the unknown points and reference locations.

Actually, the algorithm takes the distance between the signal strength of the unknown point and that of a reference location as the distance between these two points. The smaller the distance is, the more the two point match. Here, we use matching score to describe the distance between two point, take as the matching score between the unknown point and the i^th reference location. can be calculated according to formula (2).

(2)

In formula (2), Max (l (R_i, T)) represents the maximum Euclidean distance between the unknown point and reference location candidates. The greater value of MS_Ri, the farther the distance between the unknown point and the reference location.

Algorithm I: pseudo code of the proposed algorithm.

Step 2: Calculate coordinate

The candidates near to the unknown point affect location the most. However, if more and more base stations are involved, the candidates far from the unknown point will affect locating increasingly, which may degrade the location accuracy. To avoid this case, we use matching factor to control the effect from different candidates, describe it as MF. MF can be calculated according to formula (3).

(3)

In formula (3), MF_Ri is the matching factor of the i^th candidate. k (k ϵ (1, 0)) represents the impact index. The candidates near to the unknown point increasingly affect location with the decrease of k. If k = 0, the greatest effect of the location, namely the value of MS_Ri, while all candidates affect locating uniformly if k = 1. In this paper, 0.5 is enough for k to degrade the effect from the candidates far from the unknown point while increasing the effect from the candidate near to the point.

Due to that reference candidates are selected uniformly, the unknown point is located in the convex set which is composed of all reference location candidates. In general, different weighting functions could have been used, but the idea is the same, to weight reference coordinates depending on how similar the signals are. According to the natures of convex sets, we can calculate the coordinates of the unknown point by the formula (4).

(4)

In the formula (4), ^{u₁ + u₂ +...,u_n = 1}, n is the total number of the candidates. (x, y) is the coordinate of the measured point. (x_i, y_i) is the coordinate of the i^th candidate. ^u_i is the relative impact factor of the i^th candidate, it can be calculated by formula (5).

(5)

Consider random processes X(n) and Y(n) such that

where W_n and N_n are independent Gaussian random processes and independent of X. Clearly, X_n is a Markov process which together with the observations Y_n form a Hidden Markov process.

Fig. (3) Signal strength figure before filtering.

The problem of obtaining the best estimate of X from the observations Y requires one to estimate the conditional probabilities p(X _n|Y ⁿ) .

Fig. (4) Signal strength figure after Kalman filtering.

Underground environment of coal mines is very complex and bad for wireless communication. Communication signals will be transferred with noises especially when people and equipment are moving, which degrade location accuracy heavily. To handle this problem, the Kalman filter algorithm [15S. Jiping, and L. Chenxin, "Mine TOA positioning method based on Kalman filter and fingerprint location", J. China Univ. Mining, vol. 43, pp. 1117-1123, 2014., 16J. Yim, C. Park, and J. Joo, "Extended Kalman Filter for wireless LAN based indoor positioning", Decis. Support Syst., vol. 45, pp. 960-971, 2008.
[http://dx.doi.org/10.1016/j.dss.2008.03.004] ] is to be applied to filter out noise hidden in the signals we measured.

We measure strength of signals in the environment to simulate coal mines. Figs. (3 and 4) respectively show the signal strength before and after de-noised by Kalman filter algorithm. It can be obviously found that the signal strength which is filtered by Kalman has been strengthened compared with the original one. Compared with Fig. (3), much more points’ RSSI is smaller than -66.5. We consider the mean of the signal strengths de-noised as the signal strength in this paper.

We firstly evaluate the algorithm in a simulation environment constructed on Matlab platform. Given the communication radius which is configured to be 100, we randomly distribute 100 nodes in a 500×3 area.

We also evaluate our algorithm in an experimental tunnel in air raid shelter of Henan Polytechnic University, which is completely similar to underground tunnels.

The tunnel is 130*2.5 *3 (m³). A lot of WiFi hotspots are deployed in the experimental tunnel. Many reference location points are deployed at the tunnel every 5m both 2 sides as the following Fig. (5) shows, then a reference location can be randomly selected.

Fig. (5) Schematic of simulation location points.

Fig. (6) describes the final results that locate unknown points with our algorithm and the one based on fingerprint respectively.

Fig. (6) Locating errors with different reference locations density.

It can be obviously found that locating errors of these two algorithms decreased with the diversity of reference locations increasing. While our algorithm locates with higher accuracy than the one based on fingerprint when the diversity of reference locations is lower than 20.

Due to the underground tunnel has the characteristic of a single linear. In order to verify the performance of our algorithm, we also evaluate our algorithm in the experimental tunnel introduced above. The points to be located mostly deviate from the middle line of the tunnel, which is similar to the distribution of people's movements in underground tunnels. The final positions of unknown points separately by our algorithm and fingerprint algorithm are depicted in Fig. (7).

Fig. (7) The coordinates calculated by the two algorithm.

In Fig. (7), real locations of unknown points are labelled by A1-A8 with hollow triangles. Locations calculated by our algorithm and fingerprint algorithm are labelled by B1-B8 with Hollow Square, C1-C8 with hollow circular. The details of the former 5 points are described in Table 1. Table 1 also shows the errors of the two algorithms when locating those unknown points.

Table 1
Details of points and errors of the two algorithms.

Fig. (8) The coordinates calculated by the two algorithm.

Next, we can depict the results in Table 1 into changing curves as shown in Fig. (8). It is obvious that our algorithm locates unknown points with less error than fingerprint algorithm. The minimum error of our algorithm is about 1m, while the maximum is about 2.5m. The accuracy of our algorithm is acceptable since the real underground tunnel of coal mines is about more than several hundred meters long [17S. Dawei, and H. Jilan, "Discussion on the key technology of coal mine personnel positioning system", Coal Mine Machine., vol. 9, pp. 82-84, 2010.].