{'fraction_non_alphanumeric': 0.0258328346299621, 'fraction_numerical': 0.007879513265509674, 'mean_word_length': 5.056478405315614, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Research on Underground Location Algorithm Based on Random Forest and Environmental Factor Compensation

: Aiming at the problems of poor location accuracy caused by the harsh and complex underground environment, long strip roadway, limited wireless transmission and sparse anchor nodes, an underground location algorithm based on Random Forest and environmental factors compensation is proposed. Firstly, the network model of underground wireless access point (AP) and tunnel environment are analyzed, and the fingerprint location algorithm is constructed. Meanwhile, the Received Signal Strength (RSS) is analyzed by Kalman Filter algorithm in the offline sampling and real-time positioning stage. In the real-time positioning stage, random forest algorithm and signal intensity ratio compensation algorithm are used to optimize the situation that the location error fluctuates greatly in the near area. Meanwhile, the target speed constraint condition is introduced to reduce the error caused by environmental factors. The experimental results show that the algorithm proposed in this paper solves the problem of insufficient location accuracy and large fluctuation affected by environment when the anchor nodes are sparse. The average location accuracy reaches three meters, which can satisfy the application of underground rescue, activity track playback, disaster monitoring and positioning, and has high application value in complex underground environment.


Introduction and problem statement
Safety has always been a hot issue and coal accounts for 70% in the energy structure. It is estimated that this situation will continue for the next 20 years. In 2018, 224 accidents and 333 deaths occurred in the coal mines of China, including 2 major accidents with 34 deaths. The death rate per million tons of coal mines is 0.093, and the overall safety situation is developing well. In the safety production and management of coal mine, it is very important to master the number of underground personnel, activity trajectory, precise location distribution and disaster location monitoring in real time [1]. At the same time, timely and accurate rescue depends on high-precision positioning system in the event of accidents [2]. Therefore, the research on underground location algorithm is very important at present [3].
The active area of workers and locomotives are mainly working face and roadway. Compared with the transmission of wireless radio frequency signal on the ground, the underground wireless transmission environment is more complex [4]. At present, the location technology mainly includes Bluetooth, Radio Frequency Identification (RFID), Wi-Fi, ZigBee, Ultra-Wide Band (UWB) and ultrasonic [5]. However, the location algorithm is mainly based on ranging algorithm and non-ranging algorithm [6]. For example, angle-of-Arrival (AOA), Time of Arrival (TOA), Time Difference of Arrival (TDOA) [7] and Received Signal Strength Indicator (RSSI) [8] are ranging algorithm; DV-Hop [9], APIT and MDS-MAP are non-ranging algorithm [10]. The underground positioning in coal mine is different from the ground positioning, because GPS cannot play a role in underground, and the underground environment is complex and variable. Thus, the application of positioning algorithm in underground mine is more difficult [11]. Compared with other networks, Wi-Fi [12] network has the advantages of strong signal, wide bandwidth and fast transmission rate. In the underground coal mine, the WLAN (Wireless Local Area Networks) basically covers roadways and working faces, without additional network laying and installation equipment. It can speed up positioning response by adjusting the speed of data transmission in real time, which greatly meets the needs of personnel. It is an inevitable trend for the development of wireless networks in the future that it cannot only meet the needs of personnel positioning, but also transmit real-time voice and image [13]. Wang Dongdong proposed an AP planning method suitable for underground mine by studying the propagation loss law of electromagnetic wave in coal mine roadway, which satisfies the coverage of mobile terminal under WLAN communication system of digital mine [14]. By studying the long strip characteristics of roadways, Yang Cheng et al. proposed a neural network interpolation algorithm based on WLAN region division and a location algorithm based on signal strength weight index [15]. Compared with the traditional algorithm, the calculation complexity and accuracy are improved. By establishing dual WiFi channel and signal transmission and reception timing mode, Sun Jiping et al. proposed TOA underground target location method based on time error suppression [16]. Wu Jingran et al. proposed an improved fingerprint location algorithm, and combined with pedestrian track estimation (PDR) algorithm to achieve the location of underground personnel [17]. By analyzing the transmission loss model of roadways and using the method of dynamic acquisition of path fading index, Han Dongsheng et al. proposed a weighted centroid location algorithm based on RSSI [18]. Cui Lizhen used Kernel function method and particle filter algorithm to locate the underground target, and realized the tracking and positioning of static and dynamic target [19].
However, the limited underground radio wave transmission and multi-path effect, many air medium factors, as well as high humidity and gas concentration, which have a great impact on the attenuation of radio signals. Although many scholars have done a lot of work, there are still some shortcomings as follows 1) Some scholars directly use radio transmission model for positioning, which has large error and cannot be applied in coal mine. 2) There is noise in the process of wireless transmission in the tunnel, and the unprocessed transmission signal cannot be directly used for location calculation.
3) There are all kinds of moving targets in coal mine, such as locomotive and miner. Because of its stable running speed, most scholars do not pay attention to this information and make use of it, resulting in the lack of positioning accuracy. 4) The existing fingerprint location algorithms are inefficient, and usually do not consider the actual AP distribution of roadway and off-line sampling point interval on the positioning accuracy. Therefore, this paper proposes a new underground location algorithm based on random forest and environmental factors compensation. It aims to solve the problem of insufficient location accuracy and large fluctuation affected by environment when the anchor nodes are sparse, and provide a reference for the application of high-precision location in the future.

Overall problem solution approach
In view of the current situation of underground location, any single positioning algorithm cannot meet the requirements of application. In recent years, fingerprint location algorithm has been widely used in indoor location, which aims to solve the signal attenuation and multipath effect. Fingerprint location algorithm is divided into offline sampling stage and real-time positioning stage. In the real-time positioning stage, the newly collected data need to be compared with fingerprint database. Random forest is a fast and accurate classification algorithm, which improves the efficiency of fingerprint location. Considering that the adjacent AP is located in the same roadway environment, that is, its attenuation factor is the same and the information of roadway moving target is included in the acquisition, the signal intensity ratio compensation model and speed constraint model are proposed respectively to further optimize the positioning accuracy.
The overall solution is as follows: Step1: Kalman filter algorithm is used to filter the signal when receiving the signal.
Step2: The fingerprint location algorithm is introduced, and the fingerprint database of RSS and location information is established by offline sampling.
Step3: The coordinates of unknown nodes are given by random forest algorithm.
Step4: The signal intensity ratio compensation model is introduced into the algorithm to optimize the positioning results.
Step5: The speed constraint model is introduced into the algorithm, and the results are modified periodically to improve the positioning accuracy.

Organizational structure of this paper
This paper mainly studies the high-precision positioning algorithm under the condition of transmission limitation, multipath effect and signal attenuation. The first chapter introduces the research background, positioning algorithm, research status, existing problems, the goal of realization and the solution adopted in this paper. The second chapter gives the research ideas and structure of this paper. The third chapter describes the theoretical basis of Kalman filter and random forest and gives the location model. In the fourth chapter, the signal intensity ratio compensation and speed constraint algorithm are proposed to optimize the positioning results and the theoretical model is given. In the fifth chapter, the influence of off-line sampling interval on positioning accuracy is analyzed, and the optimization of fingerprint location, signal intensity ratio compensation and speed constraint is carried out. In the sixth chapter, the conclusion is given and the possible expansion in the future work is prospected.

Analysis of Underground AP network and roadway environment 3.1.1 Bridge networking model based on multi-AP
Underground roadways are usually several kilometers long. There are T-shaped, L-shaped, cross-shaped intersections, and the multi-AP bridge network model is adopted as shown in Figure 1. The problems of handover between AP, redundant AP and network security should also be taken into account when laying down WLAN in underground mine.

Roadway environment analysis
1) The underground roadway and working face are narrow and long tunnel-like enclosed limited space with fixed height and width of the roadway, variable length and irregular shape. The environmental characteristics can be summarized as follows: The roadway is a long strip with limited radio transmission, usually up to several kilometers long and only a few meters wide.
2) Both sides of the roadway are coal and rock structure, belonging to light dense medium, and the roof and floor have different degrees of concave and convex, electromagnetic wave refraction and reflection are serious. 3) There are many factors of air medium in coal mine roadway, such as high humidity and gas concentration, which have great influence on radio signal attenuation.
The signal received by WiFi terminal is generally a composite wave after multiple reflection, scattering and diffraction from multiple paths and directions. The multipath transmission model of multi-AP network in roadway is shown in Figure 2.

2 Kalman filter algorithm
Through the analysis in Section 2.1, there is noise in the signal received by STA. In this paper, the noise is filtered by Kalman filtering algorithm [20]. The received signal is treated as a discrete system without control variables. It can be described by the following two formulas: . In practical systems, the process-excited noise covariance Q and the observed noise covariance R may change with each iteration, and they are assumed to be constant.
Firstly, the process model of the system is used to predict the next state of the system. Suppose that the current system state is k , according to the system model, it can be predicted the state based on the previous state of the system: is the best result of the previous state. The covariance is the corresponding covariance of ( | 1) is the corresponding covariance of ( 1| 1) x k k − − . Combining the predicted value with the measured value, the optimal estimation of the current state ( | ) x k k is obtained: () Kg k is the Kalman Gain of the current moment: Update covariance ( | ) x k k in the update state k : Where, I is the Matrix of 1, where the value is 1.
Sampling is carried out at a distance of 15 m from the access point, sampling once per second for 50s. The filtering results are shown in Figure 3. 1) Fingerprint training stage: A database of the relationship between the position of sampling points (fingerprints) and the corresponding signal intensity is established. The sampling points are set according to a certain interval distance in the area to be detected. The signal intensity measured at each sampling point and its corresponding position information is saved in the database to form a fingerprint database.
2) Real-time location stage: When a worker or device moves to a certain location, the portable WiFi terminal on his body calculates the terminal position by comparing the matching algorithm with the information in the fingerprint database according to the signal strength measured in real time.
In this paper, the random forest algorithm is used in the prediction and classification of real-time positioning stage [21] [22], which is a combination classification algorithm of integrated learning. Based on the construction of Bagging integration, the random attribute selection is further introduced in the training process of decision tree, and bootstrap is used to put back the original data set. Several samples are extracted and trained with weak classifier-decision tree, and then these decision trees are grouped together to get the final classification or prediction results by voting as shown in Figure 4. Step3: Models combination Because the n decision trees are random in the selection of training set and feature, the n decision trees are independent of each other, and the importance of each decision tree is equal. Therefore, when they are combined, they can be considered to have the same weight.
Step4: Model verification The verification of the model needs a verification set. When selecting the training set from the original samples, some samples have not been selected at one time. In feature selection, some features may not be used, and the unused samples can be selected from the original sample set as the verification set. The idea of fingerprint location algorithm based on random forest: Firstly, the sampled signal is processed by Kalman filter to form fingerprint database; the feature data of the current positioning target is obtained in real time, which is processed by Kalman filter and then predicted by random forest; finally, the location information of unknown nodes is obtained. The algorithm model is shown in Figure 5.

Signal intensity ratio compensation algorithms (WIFI-RFFL-SIR)
In order to reduce the influence of narrow space of roadway on radio frequency signal propagation, it is assumed that the roadway environment of adjacent AP is the same, that is, its attenuation factor is the same. In this paper, a signal intensity ratio compensation algorithm is proposed to further optimize the positioning results.
Let R be the ratio of d1 and d2, and then: It can be obtained that:

Velocity-constrained localization algorithm (WIFI-RFFL-SIR-VC)
The target of underground positioning is usually moving miners and locomotives, and the speed parameters of moving targets can be used as constraints. The normal walking speed of underground people is generally less than p v , and the speed of locomotives is less than c v . Meanwhile, AP position coordinate correction is introduced, that is, that error correction will be carried out every time when an AP passes through to reduce the accumulated error. Ding Enjie et al. presented the relationship between RSS and communication distance [8]. It can be seen that within a certain distance, RSS and communication distance are almost linear. According to this characteristic, assuming the received signal strength value at the distance of AP 3m is , the speed constraint algorithm steps are as follows:

Experimental analysis
In order to verify the location performance of the algorithm, a location experiment is carried out in an air raid shelter as shown in Figure 6. The air-raid shelter is about 160 m long, 2.8 m wide and 3 m high. Other environmental parameters are similar to those of underground roadway. The length of the shelter is x axis, the width is y axis, and the center of the shelter at the entrance is coordinate origin. Assuming that the staff walk along the middle line of AP layout, that is, the y-coordinate of the terminal is always 0. The maximum speed of personnel moving is 3 m/s; there is no locomotive in the air-raid shelter, and the time interval of terminal reporting position is 1 second.    smaller and difficult to match random forest fingerprints. The positioning error increases gradually when the interval is more than 2 meters. Therefore, the interval between sampling points is set at 2m in the follow-up test, which can not only ensure the positioning error, but also reduce the workload of off-line sampling.

Experiment of fingerprint location in random forest (WIFI-RFFL)
There are three AP in the air-raid shelter, whose coordinates are AP1 (0, 1.4), AP2 (80, 1.4) and AP2 (160, 1.4) respectively, and the heights are 1.2 meters. If the sampling interval of fingerprint is 2 meters, the maximum positioning error can be predicted to be 1 meter. Workers walk around the shelter with WiFi based on wireless SOC chip GS1011. Based on WIFI-RFFL algorithm, the signal intensity of AP measured by WiFi terminal in real time is matched with fingerprint in database.

Figure 9
Location error of WIFI-RFFL algorithm As shown in Figure 9, due to the environmental factors in the air-raid shelter, such as diffraction, reflection and refraction, the positioning error of observation points between 30 -50 meters is very large, and the relationship between RSS and distance is verified. When the distance is more than 30 meters, the RSS value does not change significantly with the increase of distance, which leads to the increase of error. The average positioning error of WIFI-RFFL algorithm is 5 meters.

Experiments on signal intensity ratio compensation location algorithms (WIFI-RFFL-SIR)
The AP deployment is consistent with Section 5.2, where staff move around the shelter with WiFi based on wireless SOC chip GS1011. Based on WIFI-RFFL-SIR algorithm, the signal intensity of AP measured by WiFi terminal in real time is matched with fingerprint in database.

Experiments on velocity constrained compensation location algorithms (WIFI-RFFL-SIR-VC)
AP deployment is consistent with Section 5.2, where the staff move around the shelter with WiFi based on wireless SOC chip GS1011. Based on WIFI-RFFL-SIR-VC algorithm, the signal intensity of AP measured by WiFi terminal in real time is matched with fingerprint in database.

Figure 11
Location error of WIFI-RFFL-SIR-VC algorithm As shown in Figure 11, after the speed constraint, the influence of individual noise points on the average positioning error is weakened. At the same time, the terminal nodes are corrected when passing through AP. The overall positioning accuracy is high, and the average positioning accuracy is 3 meters.

Conclusions
In this paper, an underground localization algorithm based on random forest and environmental factors compensation is proposed for the complex environment of underground coal mine. It analyzes the underground AP network model and roadway environment, constructs a multi AP bridge networking model, introduces Kalman filter to weaken the impact of noise, and reduces the complexity of fingerprint matching algorithm. The proposed signal intensity ratio compensation algorithm and speed constrained optimization algorithm further improves the location accuracy, and eliminates the influence of noise points. Through all the experiments, the average location error is 3m, which satisfies the applications of underground rescue, activity track playback, disaster monitoring and positioning. However, due to the sparse AP, once the fault greatly affects the positioning accuracy, the blind spot location will be studied in the future.