# Algorithm of Underground Personnel Positioning Based on Improved Monte Carlo

Authors: Bin Wu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In order to improve the positioning accuracy of underground targets, especially the positioning accuracy of moving targets, an improved weighted Monte Carlo positioning algorithm is proposed. In the sampling initialization stage, the beacon node gradually constructs the sampling area according to the RSSI size and combines the Monte Carlo method to further narrow the range and improve the sampling success rate. In the filtering stage, refer to the sampling area at time and further improve the sample quality att−1 after two filterings. In the recollection stage, cooperate with invalid sample sets to reduce the number of recollections and weigh the final samples to improve the positioning accuracy of the nodes to be tested.


---

## Body

## 1. Introduction

The positioning of underground personnel in coal mines is essential to safe production. Therefore, the research of underground personnel positioning is also one of the research hotspots of the mine safety monitoring network [1–3].There are many existing underground personnel positioning systems, which are roughly divided into two types: infrastructure-based positioning and wireless sensor-based positioning [4, 5]. Infrastructure-based positioning usually installs auxiliary positioning hardware facilities in environments such as underground roadways, car yards, and substations and realizes positioning through receiving equipment that personnel carry with them. Although this positioning technology has high accuracy, the application cost is too expensive to be applied in an unknown environment, and the transmitter is based on a wired network [6, 7].Among the researches on personnel positioning based on WSNs, one type of research is based on track estimation algorithms [8]. This type of algorithm determines the position of the underground personnel based on parameters such as the number of steps, the length of the steps, and the course of the walking. However, these parameters are uncertain and random, leading to large errors in the estimated personnel position. In practice, in order to ensure the safety of underground operators, it is required to fully implement personnel positioning within the entire underground environment. Operators take a vehicle or cage to go down to the underground parking lot and then take a monkey car to reach the working surface. Therefore, the personnel do not walk down the well. The trajectory calculation algorithm cannot locate the personnel when they use the vehicle to move, resulting in the incomplete positioning system of the entire underground personnel.The Monte Carlo [9] positioning method is currently a more popular positioning method for unknown node movement. When the Monte Carlo method solves the problem, it connects with a certain probability model or random process and calculates the statistical characteristics of the problem parameters through observation or sampling test and finally gives an approximate solution [10, 11].The Monte Carlo Localization (MCL) method was originally applied to the mobile robot localization proposed by Frank et al. [12]. Robot MCL is a positioning method based on Bayesian filtering and combining the characteristics of robot movement and perception. It uses weighted sampling values to represent the robot’s state distribution and determines the position of the robot through repeated predictions and updates.The positioning of WSN mobile nodes is more complicated than robot positioning, but its positioning methods can be used for reference. Hu and Evans applied the MCL of robot positioning to the positioning of mobile nodes in WSNs, using nonranging methods, using a sample set with weights to estimate the posterior probability density distribution, and positioning the mobile nodes [13]. In UAV positioning, Wang et al. proposed an improved Monte Carlo method to improve positioning accuracy by eliminating position deviations [14]. Chen et al. proposed an adaptive Monte Carlo location method based on fusion posture estimation [15]. Some researchers have also studied the use of spectrum sensing technology in radio systems in mobile networks [16–18].


## 2. Basic Principles of MCL

The idea of MCL positioning is to budget the position at timet based on the position at time t-1. The MCL process is mainly divided into the prediction phase, the filtering phase, the resampling phase, and the importance sampling phase. The algorithm steps are as follows [19, 20].


### 2.1. Predict the Position at Timet

Assuming that the maximum moving speed of the node isvmax, then at time t, the unknown node may be located in a circular area with the position at time t−1 as the center of lt−1 and the radius of vmax, as shown in Figure 1.Figure 1
Location area at timet.N location samples are randomly collected in the area where the unknown node is located to form a sample setL=lt1,lt2,⋯,ltN, where lti represents the possible ith location of the node at time t.Assuming that the moving speed of the unknown node satisfies a uniform distribution in the upper0,vmax, the probability that the position of the unknown node at time t is estimated from the position at time t−1 also obeys the uniform distribution. As shown in the formula,
(1)plt∣lt−1=1πvmax2,dlt,lt−1<vmax,0,else.Among them,dlt,lt−1 represents the Euclidean distance between lt and lt−1, and plt∣lt−1 represents the posterior probability. It can be seen from formula (1) that as the node vmax increases, the circular area becomes larger and larger, the position range at time t becomes larger and larger, and the posterior probability becomes smaller and smaller.


### 2.2. Filtering Stage

In the filtering stage, the unknown node judges and screens possible locations based on the observation values received at timet, filters out invalid sample points in the sampling area, and improves the accuracy of the sample. The method of sample filtering is based on whether the broadcast of the beacon node can be received within the communication range of the beacon node and filter out the sample locations that have not received the broadcast.SupposeS is the set of beacon nodes with one-hop distance that unknown nodes can communicate, T is the set of beacon nodes with two-hop distances, and Rc is the communication radius of the node. Then, the filter condition of sampling sample lti is
(2)filterlti=∀s∈S,dlti,s≤Rc∩∀t∈T,Rc<dlti,t≤2Rc,1≤i≤N,where dlti,s,dlti,t represents the Euclidean distance between the sample lti and the beacon node s and t. If ∃s∈S,dlti,s>Rc at time t, it means that at position lti, the node cannot listen to the broadcast of a one-hop beacon node and then filter out such a position. If ∃t∈T,dlti,t>2Rc or dlti,t≤Rc, it means that at position lti, the node cannot receive the broadcast of the two-hop beacon node, and lti is filtered out from L.The condition of sample filtering is to use one-hop and two-hop beacon nodes. The reason why three-hop or more beacon nodes are not used is to reduce the communication overhead and calculation amount of the network.


### 2.3. Sample Resampling

After filtering, the unqualified sample positions are filtered out; then, the number of samples required by the algorithm may not reachN, and samples need to be resampled to make up for the deficiency. In the sample resampling stage, repeat 2.1 and 2.2 until the number of samples N that meets the requirements is collected or the maximum number of sampling times is reached.


### 2.4. Importance Sampling Stage

In the final sample set, since it cannot be directly sampled from the posterior distribution, it is necessary to sample the importance of the sample set. Generally, the average value of all samples is taken as the position of the unknown node at timet.Although the MCL method does not require distance measurement hardware, the calculation method is simple, and it is highly adaptable. It can even realize the positioning of mobile nodes when the beacon nodes are sparse. However, the success rate is low and the sampling process is repetitive, which leads to an increase in node calculations, causing greater energy waste. If the WSN nodes of mine tunnels work with high-frequency sampling, the energy consumption will be faster and the network life will be greatly shortened, which is unbearable. Therefore, the MCL method cannot be directly applied in practice [21, 22].


## 2.1. Predict the Position at Timet

Assuming that the maximum moving speed of the node isvmax, then at time t, the unknown node may be located in a circular area with the position at time t−1 as the center of lt−1 and the radius of vmax, as shown in Figure 1.Figure 1
Location area at timet.N location samples are randomly collected in the area where the unknown node is located to form a sample setL=lt1,lt2,⋯,ltN, where lti represents the possible ith location of the node at time t.Assuming that the moving speed of the unknown node satisfies a uniform distribution in the upper0,vmax, the probability that the position of the unknown node at time t is estimated from the position at time t−1 also obeys the uniform distribution. As shown in the formula,
(1)plt∣lt−1=1πvmax2,dlt,lt−1<vmax,0,else.Among them,dlt,lt−1 represents the Euclidean distance between lt and lt−1, and plt∣lt−1 represents the posterior probability. It can be seen from formula (1) that as the node vmax increases, the circular area becomes larger and larger, the position range at time t becomes larger and larger, and the posterior probability becomes smaller and smaller.


## 2.2. Filtering Stage

In the filtering stage, the unknown node judges and screens possible locations based on the observation values received at timet, filters out invalid sample points in the sampling area, and improves the accuracy of the sample. The method of sample filtering is based on whether the broadcast of the beacon node can be received within the communication range of the beacon node and filter out the sample locations that have not received the broadcast.SupposeS is the set of beacon nodes with one-hop distance that unknown nodes can communicate, T is the set of beacon nodes with two-hop distances, and Rc is the communication radius of the node. Then, the filter condition of sampling sample lti is
(2)filterlti=∀s∈S,dlti,s≤Rc∩∀t∈T,Rc<dlti,t≤2Rc,1≤i≤N,where dlti,s,dlti,t represents the Euclidean distance between the sample lti and the beacon node s and t. If ∃s∈S,dlti,s>Rc at time t, it means that at position lti, the node cannot listen to the broadcast of a one-hop beacon node and then filter out such a position. If ∃t∈T,dlti,t>2Rc or dlti,t≤Rc, it means that at position lti, the node cannot receive the broadcast of the two-hop beacon node, and lti is filtered out from L.The condition of sample filtering is to use one-hop and two-hop beacon nodes. The reason why three-hop or more beacon nodes are not used is to reduce the communication overhead and calculation amount of the network.


## 2.3. Sample Resampling

After filtering, the unqualified sample positions are filtered out; then, the number of samples required by the algorithm may not reachN, and samples need to be resampled to make up for the deficiency. In the sample resampling stage, repeat 2.1 and 2.2 until the number of samples N that meets the requirements is collected or the maximum number of sampling times is reached.


## 2.4. Importance Sampling Stage

In the final sample set, since it cannot be directly sampled from the posterior distribution, it is necessary to sample the importance of the sample set. Generally, the average value of all samples is taken as the position of the unknown node at timet.Although the MCL method does not require distance measurement hardware, the calculation method is simple, and it is highly adaptable. It can even realize the positioning of mobile nodes when the beacon nodes are sparse. However, the success rate is low and the sampling process is repetitive, which leads to an increase in node calculations, causing greater energy waste. If the WSN nodes of mine tunnels work with high-frequency sampling, the energy consumption will be faster and the network life will be greatly shortened, which is unbearable. Therefore, the MCL method cannot be directly applied in practice [21, 22].


## 3. Mobile Positioning Based on Improved MCL

Many researchers have proposed improved algorithms for MCL, including Baggio and Langendoen who proposed the MCB algorithm based on the MCL method [10]. The algorithm limits the sample location area to the sample box by defining the beacon box and the sample box, which reduces the sampling range and improves the success rate of sampling samples. But when the probability of sampling samples distributed in beacon boxes is relatively small, the success rate of sampling is very low. Qiao improved on the basis of MCB and proposed the MCCB algorithm [23] based on the center of mass to further improve the positioning accuracy. Dil et al. proposed a high-precision MCL algorithm [24] by using the distance between measurement nodes in the filtering stage of the MCL method.The literature shows that the existing improved methods based on MCL have achieved good positioning results, but these improved algorithms cannot be directly applied to the positioning of moving targets in coal mines, because the improvement method mostly assumes that the application scenario is an open area or evenly distributed beacon nodes or the moving range of moving targets is not limited and so on. In fact, the underground structure is complex, the roadway is narrow and long, and the range of personnel activities is limited. Most of the underground personnel are walking along the direction of the roadway, and the beacon nodes are deployed on both sides of the road wall. Therefore, a personnel positioning algorithm suitable for underground WSNs needs to be studied urgently.


### 3.1. IMCL Algorithm Description

By referring to the MCL algorithm, this article establishes the location sampling area of the mobile node according to the Received Signal Strength Indication (RSSI) received by the node. In order to facilitate the analysis, this article takes the horizontal roadway as the research object and abstracts the horizontal roadway into a two-dimensional plane; that is, the coordinate system is two-dimensional.U stands for underground personnel. Generally speaking, when U receives the RSSI of at least 3 beacon nodes, it can be positioned. The RSSI value between nodes is averaged after three measurements. The RSSI value of each node is different, which also determines that their influence on the location of the unknown node U is different. Suppose that at time T the unknown node U sends a broadcast to the surroundings and listens to feedback from multiple beacon nodes. U will sort the received RSSI values from large to small and select the beacon node A1,A2,A3 corresponding to the largest three values as a positioning reference. The larger the RSSI, the closer the distance. Therefore, A1, A2, and A3 are also the three beacon nodes closest to U, assuming that they are all within the range of one or two hops of U.


#### 3.1.1. Initialization

Assume thatRSSIi,j and di,j, respectively, represent the RSSI that node i receives from node j and the distance between the two nodes. For the beacon node A1, if RSSIA1,U>RSSIA1,A2>RSSIA1,A3, it means that U is the closest to A1, A2 is the second, and A3 is the farthest. Since U is in the underground roadway, its possible location area should be the overlap between the circle with the center of circle A1 and the radius of dA1,A2 and the roadway space. As shown in Figure 2, the gray part is the sampling area determined by A1, denoted as R1.Figure 2
Sampling area determined byA1.For the beacon nodeA2, if RSSIA2,U>RSSIA2,A1>RSSIA2,A3, it means that U is the closest to A2, A1 is the second, and A3 is the farthest. The unknown node U should be in the overlapping part of R1 with the circle centered at A2 and radius dA2,A1. As shown in Figure 3, the gray part is the sampling area jointly determined by A1 and A2, denoted as R2.Figure 3
Sampling area determined byA1,A2.For the beacon nodeA3, if RSSIA3,A2>RSSIA3,A1>RSSIA3,U, it means that A2 is the closest to A3, A1 is the second, and U is the farthest. The unknown node U should be located in the overlapping part of R2 and the outer side of the circle with the center of A3 and the radius of dA3,A1. As shown in Figure 4, the gray part is the sampling area jointly determined by A1, A2, and A3, denoted as R3.Figure 4
Sampling area determined byA1,A2,A3.Then,R3 is expressed as
(3)x−xA12+y−yA12≤dA1,A22,x−xA22+y−yA22≤dA1,A22,x−xA32+y−yA32≥dA1,A32,yA2≤y≤yA1.Suppose the coordinates of the four vertices ofR3 are A1, A2, A3, and A4, which can be solved according to formula (3).According to the MCL method, the position of the unknown nodeU at time t is a circle with position lt−1 at time t−1 as the center and radius vmax, denoted as R4; then, R3∩R4 is taken as the sampling area of U at time t, as shown in Figure 5.Figure 5
Initial sampling area.Since the gray part is an irregular figure, the bounding rectangle is taken as the initial sampling area. LetM and Q be the diagonal vertices of the rectangle, and the coordinates are Mxmax,ymax and Qxmin,ymin. M and Q coordinates satisfy
(4)xmin=maxminxa,xb,xc,xd,xt−1−vmax,ymin=maxminya,yb,yc,yd,yt−1−vmax,xmax=minmaxxa,xb,xc,xd,xt−1+vmax,ymax=minmaxya,yb,yc,yd,yt−1+vmax.Among them,xt−1,yt−1 represents the position coordinates of the node at t−1. The initial sampling area is a rectangular area with M and Q as diagonal fixed points.


#### 3.1.2. Prediction Stage

Randomly selectN sample points in the initial sampling area, and the moving speed of U obeys a uniform distribution on [0, vmax]. At time t, the probability of the position of U in the sampling area also obeys the uniform distribution:
(5)plt∣lt−1=1xmax−xminymax−ymin,xmin≤X≤xmax∩ymin≤Y≤ymax,0,other.In order to reflect the contribution of the beacon node to the positioning and to avoid the influence of low-quality samples on the positioning accuracy, each sample is weighted. Att=0, the weight of the sample is w0i=1/N,1≤i≤N.


#### 3.1.3. Filtering Stage

Filter theN sample points according to formula (6) to remove invalid samples:
(6)filterlti=∀s∈Sj,j−1Rc≤dlti,s≤jRc.Among them,Sj represents the set of j-hop beacon nodes, and Rc represents the node communication radius. Assume that the filtered sample set is Lt and the invalid sample set is It. When the sample meets the filter condition Lt, it will be kept, and if it does not meet the filter condition, it will be removed to It.In order to further improve the quality of the sample and improve the accuracy of positioning, another sample filtering is performed fromLt. Since the position of the unknown node at time t is determined based on the position at time t−1, when Lt is filtered again, the sample set Lt−1 at time t−1 is used to determine whether the sample meets the condition, and when the sample that does not meet the condition, remove from Lt and save it to the invalid sample set.Take any samplelti from Lt, if there is a sample lt−1j in Lt−1 such that dlti,lt−1j≤vmax, then keep lti in Lt; otherwise, remove it from Lt.The specific filter conditions are(7)filter′lti=∃lt−1i∈Lt−1,dlti,lt−1j≤vmax.Combining formulas (6) and (7), the condition for filtering the originally collected N samples is
(8)filterlti=∀s∈Sj,j−1Rc≤dlti,s≤jRc∩∃lt−1j∈Lt−1,dlti,lt−1j≤vmax.Because the quality of the filtered samples is different, the weights are differentiated. The beacon node closest to the unknown node has the greatest power to determine the positioning result, so the weight of the sample is set to the reciprocal of the distance to the nearest beacon node as the weight coefficient,wti=1/dAi,lti, where Ai represents the beacon closest to the unknown node. For nodes, the smaller dAi,lti, the greater the weight and the greater the influence of the sample position.


#### 3.1.4. Retake Stage

After the filtering stage, the number of remaining samples may not reachN, and resampling is required. In order to improve the success rate of the resampling stage, during the resampling, the sampled sample is compared with the elements in It, and if it is in the set, it is discarded and resampled. After recollection, repeat prediction and filtering until the number of samples meets the requirements or reaches the maximum number of samples.


#### 3.1.5. Location Estimate

Assuming that the final number of samples that meet the requirements isNum, the weights of the samples are normalized:
(9)wti=wti∑i=1Numwti.Then, the position of the moving target at timet is shown in formula (10), where xti,yti is the coordinate of the ith sample at time t:
(10)xt=∑i=1Numwtixti,yt=∑i=1Numwtiyti.


### 3.2. IMCL Algorithm Steps

The basic steps of the underground personnel positioning algorithm based on improved Monte Carlo are as Algorithm1.Algorithm 1:
Algorithm based on improved Monte Carlo.Step 1. The mobile node listens to the beacon node broadcast and selects the beacon node corresponding to the maximum 3 RSSI as the positioning node.Step 2. The selected beacon node constructs the possible location area of the mobile node one by one according to the RSSI size.Step 3. Take the intersection of the MCL sampling area and the location area in Step 2, which is the final sampling area of the algorithm.Step 4. SelectN samples at random and initialize the sample weights.Step 5. Filter samples and update sample weights.Step 6. Determine whether the number of remaining samples is sufficient or whether the maximum sampling times are reached. If yes, continue; otherwise, go to Step 4.Step 7. Normalize the weight of the sample and calculate the coordinates of the mobile node.


## 3.1. IMCL Algorithm Description

By referring to the MCL algorithm, this article establishes the location sampling area of the mobile node according to the Received Signal Strength Indication (RSSI) received by the node. In order to facilitate the analysis, this article takes the horizontal roadway as the research object and abstracts the horizontal roadway into a two-dimensional plane; that is, the coordinate system is two-dimensional.U stands for underground personnel. Generally speaking, when U receives the RSSI of at least 3 beacon nodes, it can be positioned. The RSSI value between nodes is averaged after three measurements. The RSSI value of each node is different, which also determines that their influence on the location of the unknown node U is different. Suppose that at time T the unknown node U sends a broadcast to the surroundings and listens to feedback from multiple beacon nodes. U will sort the received RSSI values from large to small and select the beacon node A1,A2,A3 corresponding to the largest three values as a positioning reference. The larger the RSSI, the closer the distance. Therefore, A1, A2, and A3 are also the three beacon nodes closest to U, assuming that they are all within the range of one or two hops of U.


### 3.1.1. Initialization

Assume thatRSSIi,j and di,j, respectively, represent the RSSI that node i receives from node j and the distance between the two nodes. For the beacon node A1, if RSSIA1,U>RSSIA1,A2>RSSIA1,A3, it means that U is the closest to A1, A2 is the second, and A3 is the farthest. Since U is in the underground roadway, its possible location area should be the overlap between the circle with the center of circle A1 and the radius of dA1,A2 and the roadway space. As shown in Figure 2, the gray part is the sampling area determined by A1, denoted as R1.Figure 2
Sampling area determined byA1.For the beacon nodeA2, if RSSIA2,U>RSSIA2,A1>RSSIA2,A3, it means that U is the closest to A2, A1 is the second, and A3 is the farthest. The unknown node U should be in the overlapping part of R1 with the circle centered at A2 and radius dA2,A1. As shown in Figure 3, the gray part is the sampling area jointly determined by A1 and A2, denoted as R2.Figure 3
Sampling area determined byA1,A2.For the beacon nodeA3, if RSSIA3,A2>RSSIA3,A1>RSSIA3,U, it means that A2 is the closest to A3, A1 is the second, and U is the farthest. The unknown node U should be located in the overlapping part of R2 and the outer side of the circle with the center of A3 and the radius of dA3,A1. As shown in Figure 4, the gray part is the sampling area jointly determined by A1, A2, and A3, denoted as R3.Figure 4
Sampling area determined byA1,A2,A3.Then,R3 is expressed as
(3)x−xA12+y−yA12≤dA1,A22,x−xA22+y−yA22≤dA1,A22,x−xA32+y−yA32≥dA1,A32,yA2≤y≤yA1.Suppose the coordinates of the four vertices ofR3 are A1, A2, A3, and A4, which can be solved according to formula (3).According to the MCL method, the position of the unknown nodeU at time t is a circle with position lt−1 at time t−1 as the center and radius vmax, denoted as R4; then, R3∩R4 is taken as the sampling area of U at time t, as shown in Figure 5.Figure 5
Initial sampling area.Since the gray part is an irregular figure, the bounding rectangle is taken as the initial sampling area. LetM and Q be the diagonal vertices of the rectangle, and the coordinates are Mxmax,ymax and Qxmin,ymin. M and Q coordinates satisfy
(4)xmin=maxminxa,xb,xc,xd,xt−1−vmax,ymin=maxminya,yb,yc,yd,yt−1−vmax,xmax=minmaxxa,xb,xc,xd,xt−1+vmax,ymax=minmaxya,yb,yc,yd,yt−1+vmax.Among them,xt−1,yt−1 represents the position coordinates of the node at t−1. The initial sampling area is a rectangular area with M and Q as diagonal fixed points.


### 3.1.2. Prediction Stage

Randomly selectN sample points in the initial sampling area, and the moving speed of U obeys a uniform distribution on [0, vmax]. At time t, the probability of the position of U in the sampling area also obeys the uniform distribution:
(5)plt∣lt−1=1xmax−xminymax−ymin,xmin≤X≤xmax∩ymin≤Y≤ymax,0,other.In order to reflect the contribution of the beacon node to the positioning and to avoid the influence of low-quality samples on the positioning accuracy, each sample is weighted. Att=0, the weight of the sample is w0i=1/N,1≤i≤N.


### 3.1.3. Filtering Stage

Filter theN sample points according to formula (6) to remove invalid samples:
(6)filterlti=∀s∈Sj,j−1Rc≤dlti,s≤jRc.Among them,Sj represents the set of j-hop beacon nodes, and Rc represents the node communication radius. Assume that the filtered sample set is Lt and the invalid sample set is It. When the sample meets the filter condition Lt, it will be kept, and if it does not meet the filter condition, it will be removed to It.In order to further improve the quality of the sample and improve the accuracy of positioning, another sample filtering is performed fromLt. Since the position of the unknown node at time t is determined based on the position at time t−1, when Lt is filtered again, the sample set Lt−1 at time t−1 is used to determine whether the sample meets the condition, and when the sample that does not meet the condition, remove from Lt and save it to the invalid sample set.Take any samplelti from Lt, if there is a sample lt−1j in Lt−1 such that dlti,lt−1j≤vmax, then keep lti in Lt; otherwise, remove it from Lt.The specific filter conditions are(7)filter′lti=∃lt−1i∈Lt−1,dlti,lt−1j≤vmax.Combining formulas (6) and (7), the condition for filtering the originally collected N samples is
(8)filterlti=∀s∈Sj,j−1Rc≤dlti,s≤jRc∩∃lt−1j∈Lt−1,dlti,lt−1j≤vmax.Because the quality of the filtered samples is different, the weights are differentiated. The beacon node closest to the unknown node has the greatest power to determine the positioning result, so the weight of the sample is set to the reciprocal of the distance to the nearest beacon node as the weight coefficient,wti=1/dAi,lti, where Ai represents the beacon closest to the unknown node. For nodes, the smaller dAi,lti, the greater the weight and the greater the influence of the sample position.


### 3.1.4. Retake Stage

After the filtering stage, the number of remaining samples may not reachN, and resampling is required. In order to improve the success rate of the resampling stage, during the resampling, the sampled sample is compared with the elements in It, and if it is in the set, it is discarded and resampled. After recollection, repeat prediction and filtering until the number of samples meets the requirements or reaches the maximum number of samples.


### 3.1.5. Location Estimate

Assuming that the final number of samples that meet the requirements isNum, the weights of the samples are normalized:
(9)wti=wti∑i=1Numwti.Then, the position of the moving target at timet is shown in formula (10), where xti,yti is the coordinate of the ith sample at time t:
(10)xt=∑i=1Numwtixti,yt=∑i=1Numwtiyti.


## 3.1.1. Initialization

Assume thatRSSIi,j and di,j, respectively, represent the RSSI that node i receives from node j and the distance between the two nodes. For the beacon node A1, if RSSIA1,U>RSSIA1,A2>RSSIA1,A3, it means that U is the closest to A1, A2 is the second, and A3 is the farthest. Since U is in the underground roadway, its possible location area should be the overlap between the circle with the center of circle A1 and the radius of dA1,A2 and the roadway space. As shown in Figure 2, the gray part is the sampling area determined by A1, denoted as R1.Figure 2
Sampling area determined byA1.For the beacon nodeA2, if RSSIA2,U>RSSIA2,A1>RSSIA2,A3, it means that U is the closest to A2, A1 is the second, and A3 is the farthest. The unknown node U should be in the overlapping part of R1 with the circle centered at A2 and radius dA2,A1. As shown in Figure 3, the gray part is the sampling area jointly determined by A1 and A2, denoted as R2.Figure 3
Sampling area determined byA1,A2.For the beacon nodeA3, if RSSIA3,A2>RSSIA3,A1>RSSIA3,U, it means that A2 is the closest to A3, A1 is the second, and U is the farthest. The unknown node U should be located in the overlapping part of R2 and the outer side of the circle with the center of A3 and the radius of dA3,A1. As shown in Figure 4, the gray part is the sampling area jointly determined by A1, A2, and A3, denoted as R3.Figure 4
Sampling area determined byA1,A2,A3.Then,R3 is expressed as
(3)x−xA12+y−yA12≤dA1,A22,x−xA22+y−yA22≤dA1,A22,x−xA32+y−yA32≥dA1,A32,yA2≤y≤yA1.Suppose the coordinates of the four vertices ofR3 are A1, A2, A3, and A4, which can be solved according to formula (3).According to the MCL method, the position of the unknown nodeU at time t is a circle with position lt−1 at time t−1 as the center and radius vmax, denoted as R4; then, R3∩R4 is taken as the sampling area of U at time t, as shown in Figure 5.Figure 5
Initial sampling area.Since the gray part is an irregular figure, the bounding rectangle is taken as the initial sampling area. LetM and Q be the diagonal vertices of the rectangle, and the coordinates are Mxmax,ymax and Qxmin,ymin. M and Q coordinates satisfy
(4)xmin=maxminxa,xb,xc,xd,xt−1−vmax,ymin=maxminya,yb,yc,yd,yt−1−vmax,xmax=minmaxxa,xb,xc,xd,xt−1+vmax,ymax=minmaxya,yb,yc,yd,yt−1+vmax.Among them,xt−1,yt−1 represents the position coordinates of the node at t−1. The initial sampling area is a rectangular area with M and Q as diagonal fixed points.


## 3.1.2. Prediction Stage

Randomly selectN sample points in the initial sampling area, and the moving speed of U obeys a uniform distribution on [0, vmax]. At time t, the probability of the position of U in the sampling area also obeys the uniform distribution:
(5)plt∣lt−1=1xmax−xminymax−ymin,xmin≤X≤xmax∩ymin≤Y≤ymax,0,other.In order to reflect the contribution of the beacon node to the positioning and to avoid the influence of low-quality samples on the positioning accuracy, each sample is weighted. Att=0, the weight of the sample is w0i=1/N,1≤i≤N.


## 3.1.3. Filtering Stage

Filter theN sample points according to formula (6) to remove invalid samples:
(6)filterlti=∀s∈Sj,j−1Rc≤dlti,s≤jRc.Among them,Sj represents the set of j-hop beacon nodes, and Rc represents the node communication radius. Assume that the filtered sample set is Lt and the invalid sample set is It. When the sample meets the filter condition Lt, it will be kept, and if it does not meet the filter condition, it will be removed to It.In order to further improve the quality of the sample and improve the accuracy of positioning, another sample filtering is performed fromLt. Since the position of the unknown node at time t is determined based on the position at time t−1, when Lt is filtered again, the sample set Lt−1 at time t−1 is used to determine whether the sample meets the condition, and when the sample that does not meet the condition, remove from Lt and save it to the invalid sample set.Take any samplelti from Lt, if there is a sample lt−1j in Lt−1 such that dlti,lt−1j≤vmax, then keep lti in Lt; otherwise, remove it from Lt.The specific filter conditions are(7)filter′lti=∃lt−1i∈Lt−1,dlti,lt−1j≤vmax.Combining formulas (6) and (7), the condition for filtering the originally collected N samples is
(8)filterlti=∀s∈Sj,j−1Rc≤dlti,s≤jRc∩∃lt−1j∈Lt−1,dlti,lt−1j≤vmax.Because the quality of the filtered samples is different, the weights are differentiated. The beacon node closest to the unknown node has the greatest power to determine the positioning result, so the weight of the sample is set to the reciprocal of the distance to the nearest beacon node as the weight coefficient,wti=1/dAi,lti, where Ai represents the beacon closest to the unknown node. For nodes, the smaller dAi,lti, the greater the weight and the greater the influence of the sample position.


## 3.1.4. Retake Stage

After the filtering stage, the number of remaining samples may not reachN, and resampling is required. In order to improve the success rate of the resampling stage, during the resampling, the sampled sample is compared with the elements in It, and if it is in the set, it is discarded and resampled. After recollection, repeat prediction and filtering until the number of samples meets the requirements or reaches the maximum number of samples.


## 3.1.5. Location Estimate

Assuming that the final number of samples that meet the requirements isNum, the weights of the samples are normalized:
(9)wti=wti∑i=1Numwti.Then, the position of the moving target at timet is shown in formula (10), where xti,yti is the coordinate of the ith sample at time t:
(10)xt=∑i=1Numwtixti,yt=∑i=1Numwtiyti.


## 3.2. IMCL Algorithm Steps

The basic steps of the underground personnel positioning algorithm based on improved Monte Carlo are as Algorithm1.Algorithm 1:
Algorithm based on improved Monte Carlo.Step 1. The mobile node listens to the beacon node broadcast and selects the beacon node corresponding to the maximum 3 RSSI as the positioning node.Step 2. The selected beacon node constructs the possible location area of the mobile node one by one according to the RSSI size.Step 3. Take the intersection of the MCL sampling area and the location area in Step 2, which is the final sampling area of the algorithm.Step 4. SelectN samples at random and initialize the sample weights.Step 5. Filter samples and update sample weights.Step 6. Determine whether the number of remaining samples is sufficient or whether the maximum sampling times are reached. If yes, continue; otherwise, go to Step 4.Step 7. Normalize the weight of the sample and calculate the coordinates of the mobile node.


## 4. Experimental and Simulation

In order to verify the superiority of the IMCL algorithm, this article has done a lot of experiments and compared it with the MCL algorithm, MCB algorithm, and MCCB algorithm through MATLAB simulation software. The experimental data are the test data of the actual operation base of the actual mine.In order to effectively simulate the real roadway environment, the simulation area is set as a long and narrow area of500m×5m. Unknown nodes are randomly deployed in the simulation area, and beacon nodes are nonuniformly cross-deployed on both sides of the area with known coordinates. Suppose the communication radius of the node is Rc=5m, the maximum moving speed of the node is vmax=5m/s, the minimum moving speed is vmin=0m/s, the number of samples is N=50, and the maximum number of samples is Num=500.The pros and cons of the algorithm are evaluated by positioning error, that is,(11)σ=x−xtrue2+y−ytrue2Rc.


### 4.1. The Effect of Node Moving Speed on Positioning

Through experiments, it is found that the maximum speed of the mobile node changes from5m/s to 25m/s, and the changes in the positioning errors of the four algorithms are shown in Figure 6.Figure 6
Positioning error of differentvmax.Experiments show that with the increase invmax, the positioning errors of the four positioning algorithms IMCL, MCL, MCB, and MCCB all gradually increase. As vmax increases, the sample sampling area in the algorithm will also become larger, and invalid samples will also increase, resulting in larger positioning errors. At the same time, Figure 6 shows that the error curve does not increase linearly. Because the moving speed of the target node under test becomes larger and the activity range of the node per unit time becomes larger, more beacon node communications can be obtained, and the impossible position samples can be filtered out more effectively, thereby improving positioning accuracy and reducing errors. The error of the MCL method is the largest, mainly because the sampling area is not limited, and it becomes larger as vmax increases, the number of sampling is increasing, and the positioning accuracy is low. The MCB and MCCB algorithms limit the sampling area in a relatively small beacon box, which improves the sampling success rate and reduces positioning errors. The IMCL algorithm further limits the initial sampling area to the most likely range based on the influence of the beacon node and combines the sample weight to improve the positioning accuracy with the lowest error.


### 4.2. The Effect of Node Moving Speed on Sampling Times

The number of sampling also affects the positioning accuracy. Experiments show that with the change of nodevmax, the sampling times of MCL increase, and the sampling times of the other three types decrease, as shown in Figure 7. For the MCL method, when the node vmax is relatively small, the sampling range is relatively small, the sampling success rate is relatively high, and the sampling times are relatively small; as vmax increases, the sampling area becomes larger, the sampling success rate is low, and the sampling times increase. In MCB and MCCB, with the increase in vmax, the beacon node box becomes smaller, the sampling success rate is high, and the sampling frequency is reduced. The sampling area of IMCL is constructed using the influence of beacon nodes and MCL sampling, which improves the sampling efficiency and success rate, and the number of samplings is relatively small.Figure 7
The sampling times of differentvmax.


### 4.3. The Effect of Beacon Node Density on Positioning

The beacon node density is defined as the number of beacon nodes within one-hop distance of the node to be tested. As the density of beacon nodes increases, the more observation information the node to be tested receives, and the filtered samples are closer to the posterior probability distribution, which improves the positioning accuracy.The experimental results are shown in Figure8. As the density of beacon nodes increases, the positioning errors of the four algorithms have decreased to varying degrees, but the downward trend is gradually flattened. The positioning accuracy of MCB and MCCB is closely related to the density of beacon nodes. The greater the density, the smaller the box of the beacon node and the smaller the positioning error. MCCB is based on the center of mass MCB, so its positioning error is lower than MCB. IMCL is based on the positioning of the nearest beacon node. The greater the density of beacon nodes, the smaller the distance between the unknown node and the nearest beacon node, the greater the signal strength, the more accurate the distance calculation, and the higher the positioning accuracy.Figure 8
Positioning error under different beacon node densities.


### 4.4. The Effect of Beacon Node Density on Sampling Times

The experimental results are shown in Figure9. The sampling times of each algorithm decrease with the increase of the beacon node density. Because of the increase in the density of beacon nodes, the more observation information obtained by the sample, more samples will be retained in the filtering stage, the higher the success rate, and the fewer sampling times, so the changing trend of the sampling times of the four algorithms is roughly the same. Although the sampling times decrease with the increase of the beacon node density, the sampling times of the MCL algorithm are relatively the largest. Similar to the same vmax, the sampling area of MCL is fixed, while the sampling areas of the other three algorithms are relatively small. Therefore, when sampling randomly, the probability of success is relatively large, and the number of sampling is naturally relatively low. The sampling area of the MCCB algorithm is reduced on the basis of the MCB, so the sampling times of the MCCB are less than the sampling times of the MCB. The initial sampling area of IMCL is closer to the actual location of the unknown node. As the density of beacon nodes increases, more samples are drawn that meet the filtering conditions, and the number of samples is less.Figure 9
Comparison of sampling times of different beacon node densities.


### 4.5. The Effect of Roadway Width on Positioning Error and Sampling Times

During the experiment, we changed the width of the roadway network while keepingvmax unchanged and repeated the experiment to observe changes in positioning errors and sampling times.Figure10 shows that as the width changes from 5 m to 10 m, the positioning errors of various algorithms gradually become larger. Since the beacon nodes are cross-deployed on both sides of the area, the increase of the width causes the longitudinal distance between the beacon nodes to increase, the area of the same length increases, and the number of one-hop or two-hop beacon nodes decreases. The information is less, and the positioning error is large.Figure 10
Positioning error under different roadway widths.Figure11 shows the trend of sampling times of various algorithms under different widths of the simulation area. According to the above analysis, the increase of the width leads to the decrease of one-hop or two-hop beacon nodes. In the filtering stage, relatively more samples are filtered out, and the number of sampling increases.Figure 11
Sampling times under different roadway width.


## 4.1. The Effect of Node Moving Speed on Positioning

Through experiments, it is found that the maximum speed of the mobile node changes from5m/s to 25m/s, and the changes in the positioning errors of the four algorithms are shown in Figure 6.Figure 6
Positioning error of differentvmax.Experiments show that with the increase invmax, the positioning errors of the four positioning algorithms IMCL, MCL, MCB, and MCCB all gradually increase. As vmax increases, the sample sampling area in the algorithm will also become larger, and invalid samples will also increase, resulting in larger positioning errors. At the same time, Figure 6 shows that the error curve does not increase linearly. Because the moving speed of the target node under test becomes larger and the activity range of the node per unit time becomes larger, more beacon node communications can be obtained, and the impossible position samples can be filtered out more effectively, thereby improving positioning accuracy and reducing errors. The error of the MCL method is the largest, mainly because the sampling area is not limited, and it becomes larger as vmax increases, the number of sampling is increasing, and the positioning accuracy is low. The MCB and MCCB algorithms limit the sampling area in a relatively small beacon box, which improves the sampling success rate and reduces positioning errors. The IMCL algorithm further limits the initial sampling area to the most likely range based on the influence of the beacon node and combines the sample weight to improve the positioning accuracy with the lowest error.


## 4.2. The Effect of Node Moving Speed on Sampling Times

The number of sampling also affects the positioning accuracy. Experiments show that with the change of nodevmax, the sampling times of MCL increase, and the sampling times of the other three types decrease, as shown in Figure 7. For the MCL method, when the node vmax is relatively small, the sampling range is relatively small, the sampling success rate is relatively high, and the sampling times are relatively small; as vmax increases, the sampling area becomes larger, the sampling success rate is low, and the sampling times increase. In MCB and MCCB, with the increase in vmax, the beacon node box becomes smaller, the sampling success rate is high, and the sampling frequency is reduced. The sampling area of IMCL is constructed using the influence of beacon nodes and MCL sampling, which improves the sampling efficiency and success rate, and the number of samplings is relatively small.Figure 7
The sampling times of differentvmax.


## 4.3. The Effect of Beacon Node Density on Positioning

The beacon node density is defined as the number of beacon nodes within one-hop distance of the node to be tested. As the density of beacon nodes increases, the more observation information the node to be tested receives, and the filtered samples are closer to the posterior probability distribution, which improves the positioning accuracy.The experimental results are shown in Figure8. As the density of beacon nodes increases, the positioning errors of the four algorithms have decreased to varying degrees, but the downward trend is gradually flattened. The positioning accuracy of MCB and MCCB is closely related to the density of beacon nodes. The greater the density, the smaller the box of the beacon node and the smaller the positioning error. MCCB is based on the center of mass MCB, so its positioning error is lower than MCB. IMCL is based on the positioning of the nearest beacon node. The greater the density of beacon nodes, the smaller the distance between the unknown node and the nearest beacon node, the greater the signal strength, the more accurate the distance calculation, and the higher the positioning accuracy.Figure 8
Positioning error under different beacon node densities.


## 4.4. The Effect of Beacon Node Density on Sampling Times

The experimental results are shown in Figure9. The sampling times of each algorithm decrease with the increase of the beacon node density. Because of the increase in the density of beacon nodes, the more observation information obtained by the sample, more samples will be retained in the filtering stage, the higher the success rate, and the fewer sampling times, so the changing trend of the sampling times of the four algorithms is roughly the same. Although the sampling times decrease with the increase of the beacon node density, the sampling times of the MCL algorithm are relatively the largest. Similar to the same vmax, the sampling area of MCL is fixed, while the sampling areas of the other three algorithms are relatively small. Therefore, when sampling randomly, the probability of success is relatively large, and the number of sampling is naturally relatively low. The sampling area of the MCCB algorithm is reduced on the basis of the MCB, so the sampling times of the MCCB are less than the sampling times of the MCB. The initial sampling area of IMCL is closer to the actual location of the unknown node. As the density of beacon nodes increases, more samples are drawn that meet the filtering conditions, and the number of samples is less.Figure 9
Comparison of sampling times of different beacon node densities.


## 4.5. The Effect of Roadway Width on Positioning Error and Sampling Times

During the experiment, we changed the width of the roadway network while keepingvmax unchanged and repeated the experiment to observe changes in positioning errors and sampling times.Figure10 shows that as the width changes from 5 m to 10 m, the positioning errors of various algorithms gradually become larger. Since the beacon nodes are cross-deployed on both sides of the area, the increase of the width causes the longitudinal distance between the beacon nodes to increase, the area of the same length increases, and the number of one-hop or two-hop beacon nodes decreases. The information is less, and the positioning error is large.Figure 10
Positioning error under different roadway widths.Figure11 shows the trend of sampling times of various algorithms under different widths of the simulation area. According to the above analysis, the increase of the width leads to the decrease of one-hop or two-hop beacon nodes. In the filtering stage, relatively more samples are filtered out, and the number of sampling increases.Figure 11
Sampling times under different roadway width.


## 5. Conclusions

According to the size of RSSI received by the beacon node and combined with MCL sampling, IMCL establishes the sampling area where unknown nodes are most likely to appear, reduces the sampling range of MCL, and improves the sample sampling success rate. The algorithm performs two filtering and screening in the sample filtering stage to retain high-quality samples; in the recollection stage, it uses invalid sample sets to match sampling to reduce the number of recollections and reduce energy consumption. The final sample is weighted to reflect the influence of the sample on the location of unknown nodes and improve the positioning accuracy. Experimental simulations show that under different moving speeds, different beacon node densities, and different roadway widths, the positioning accuracy of this algorithm is higher than other algorithms, and the sampling times are the least.



---

*Source: 5547944-2021-03-31.xml*