Location algorithm based on fingerprint has been applied to underground tunnel of coal mines. However, obvious and un-ignorable errors will occur if reference locations are selected sparsely when detecting unknown points, which may make it difficult for locating people in coal mines. Hence, an underground location algorithm based on convex sets of Received Signal Strength Indication (RSSI) is proposed in this paper. Many reference location points are deployed at the experimental tunnel every 5m both 2 sides as depicted in Fig. (5) shows, then a reference location can be randomly selected. Firstly, calculate the Euclidean distance between unknown points and reference locations in a fingerprint database established by using RSSI value that de-noised by the Kalman filter algorithm. Secondly, select several reference locations that mostly match with unknown points, construct a convex. Finally, take the coordinates of centroid of the convex as the coordinates of the unknown points. The simulation experiments indicate that the proposed algorithm locates unknown points with higher accuracy than the traditional one based on fingerprint.
Open Peer Review Details | |||
---|---|---|---|
Manuscript submitted on 13-01-2015 |
Original Manuscript | An Improved Underground Location Algorithm Based on Convex Sets of RSSI |
Underground environment of coal mines is very complex. Coal miners are often threatened by accidents [1C. Lizhen, and Y. Quan, "Design and implementation based on the Zig Bee adaptive communications in the mine gas monitoring system", Min. Safety Environ., vol. 39, pp. 19-21, 2012.
[http://dx.doi.org/10.1109/TCE.2010.5606278] ] from roof collapse, explosion, flooding, fire etc., which make it critical for escaping and rescuing to accurately locate coal miners underground. Many researchers have performed a lot experiments on underground location techniques. Owing to the fact that wireless network can be constructed and maintained easily and low-cost, especially its stubborn features that make it stick to efficient work though accidents happened, location techniques based on WiFi [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.] have been widely used in the underground environments of coal mines.
The techniques based on the time of arrival (TOA), the time difference of arrival (TDOA), the angle of arrival (AOA), or the received signal strength indication (RSSI) have been adopted in main location methods. The first three techniques require high quality hardware, while the last one is low-cost, easy to implement and little special requirements on hardware. The algorithm based on fingerprint [3W. Ding, M. Juan, and Z. Yixuan, "Fingerprint localization algorithm based on RSS space-time processing", App. Res. Comp., vol. 29, pp. 4726-4728, 2012.] adopts RSSI to locate unknown points. However, the RSSI is affected greatly by the factors like movements of people and equipment, changes of temperature [4W. Yang, H. Liusheng, and X. Mingjun, "A wireless sensor network node localization algorithm based on RSSI calibration", Small Microcomp. Syst., vol. 30, pp. 59-62, 2009., 5W. Fubao, S. Long, and R. Fengyuan, "Self-positioning system and algorithm in wireless sensor networks", J. Softw., vol. 16, pp. 1148-1157, 2005.] etc. The fingerprint algorithm locates unknown points with un-ignorable errors especially when reference locations are selected sparsely.
To handle this problem, we propose an underground tunnel location algorithm based on convex sets of RSSI. Firstly, calculate the Euclidean distance between unknown points and reference locations in a fingerprint database established by using RSSI value that de-noised by the Kalman filter algorithm. Secondly, select several reference locations that mostly match with unknown points, construct a convex. Finally, take the coordinates of centroid of the convex as the coordinates of the unknown points. We have implemented our algorithm on the smart phone whose OS is Android [6Y. Fan, and Z. Dongdong, "WiFi positioning based on the Android platform", Elec. Meas. Tech., vol. 35, pp. 116-119, 2012.], the simulation experiments indicate that the proposed algorithm locates unknown points with higher accuracy than the traditional one based on fingerprint.
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), Ri is the signal strength vector of the ith reference location., represent the signal strength of the kth base station measured at the ith reference location. is the vector of the unknown point to be located., T (t1, t2, tn), tk, (k ϵ (1, n)) represents the signal strength of the kth base station measured at the unknown point. l (Ri, 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: 20th 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 O1, O2, O3 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:
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 ith reference location. can be calculated according to formula (2).
(2) |
In formula (2), Max (l (Ri, T)) represents the maximum Euclidean distance between the unknown point and reference location candidates. The greater value of MSRi, the farther the distance between the unknown point and the reference location.
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), MFRi is the matching factor of the ith 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 MSRi, 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), u1 + u2 +...,un = 1, n is the total number of the candidates. (x, y) is the coordinate of the measured point. (xi, yi) is the coordinate of the ith candidate. ui is the relative impact factor of the ith candidate, it can be calculated by formula (5).
(5) |
Consider random processes X(n) and Y(n) such that
where Wn and Nn are independent Gaussian random processes and independent of X. Clearly, Xn is a Markov process which together with the observations Yn 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 n) .
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 (m3). 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.
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.].
In this paper, we translate the problem of underground locating into the problem of the optimization of RSSI convex sets. Different from other algorithms, we choose reference locations for unknown points according to matching score. During calculating the coordinates of unknown points, we use the relative impact factors to enlarge the influence from the reference locations near to the unknown points. The results of evaluations show that our algorithm located unknown points with higher accuracy.
No conflict of interest exits in the submission of this manuscript. This manuscript is approved by all authors for publication. I would like to declare on behalf of my co-authors that the work described was original research that has not been published previously, not under consideration for publication elsewhere, in whole or in part.
This work is supported by the Provincial Key Technologies R & D Program of Henan under Grant No. 142402210435 and Open Fund Project of Henan Higher Key Discipline Laboratory of Mine Information under Grant No. KZ2012-03.
[1] | C. Lizhen, and Y. Quan, "Design and implementation based on the Zig Bee adaptive communications in the mine gas monitoring system", Min. Safety Environ., vol. 39, pp. 19-21, 2012. [http://dx.doi.org/10.1109/TCE.2010.5606278] |
[2] | L. Xiaowen, Z. Xiujun, and H. Lina, "Research on underground location algorithm based on WI-FI", J. Transducer Technol., vol. 26, pp. 854-858, 2012. |
[3] | W. Ding, M. Juan, and Z. Yixuan, "Fingerprint localization algorithm based on RSS space-time processing", App. Res. Comp., vol. 29, pp. 4726-4728, 2012. |
[4] | W. Yang, H. Liusheng, and X. Mingjun, "A wireless sensor network node localization algorithm based on RSSI calibration", Small Microcomp. Syst., vol. 30, pp. 59-62, 2009. |
[5] | W. Fubao, S. Long, and R. Fengyuan, "Self-positioning system and algorithm in wireless sensor networks", J. Softw., vol. 16, pp. 1148-1157, 2005. |
[6] | Y. Fan, and Z. Dongdong, "WiFi positioning based on the Android platform", Elec. Meas. Tech., vol. 35, pp. 116-119, 2012. |
[7] | L. Henghui, and L. Xingchuan, "Comparison of WiFi location based on triangle and location fingerprint recognition algorithm", Mobile Commun., vol. 34, pp. 72-76, 2010. |
[8] | L. Lun, D. Enjie, and H. Lina, "An improved coal mine fingerprint matching localization algorithm", J. Sens. Technol., vol. 34, pp. 72-76, 2010. |
[9] | B. 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] |
[10] | A. 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] |
[11] | G. 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] |
[12] | P. Li, “Wireless Sensor Network Technology”, Metall. Press: Ind., 2011. |
[13] | C. Min, W. Jun, and L. Junhua, “Principles and Practice of Wireless Sensor Networks”, Chemistry, Press: Ind., 2011. |
[14] | "L. El Ghaoui, “Convex position estimation in wireless sensor networks", In: 20th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, 2001, pp. 1655-1663 |
[15] | S. 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. |
[16] | J. 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] |
[17] | S. Dawei, and H. Jilan, "Discussion on the key technology of coal mine personnel positioning system", Coal Mine Machine., vol. 9, pp. 82-84, 2010. |