Grid-Based Improved Maximum Likelihood Estimation for Dynamic Localization of Mobile Robots

Abstract

The dynamic localization is a kind of technology by which the mobile robot tries to localize the position by itself. According to the dynamic localization failure of mobile robots in indoor network blind areas, an autonomous-dynamic localization system which dynamically chooses beacon node and establishes grids is proposed in this paper. This method applies received signal strength indication (RSSI) for distance measurement. Furthermore, the proposed grid-based improved maximum likelihood estimation (GIMLE) fulfills the localization. Finally, the localization error correction is implemented by Kalman filter. The approach combines the classical Kalman filter with the other localization algorithms. The purpose is to smooth and optimize the results of the algorithms, in order to improve the localization accuracy. In particular, in network blind spots, the Kalman filter provides better performance than the other algorithms listed in the paper. Experimental results show the accuracy, adaptivity, and robustness of the dynamic self-localization of mobile robots.

1. Introduction

Dynamic localization of the mobile robot is the frontier research area in wireless sensor networks (WSNs). WSNs could fulfill dynamic ad hoc networking in the situation of partial damaged nodes and provide consecutive environmental information and changing trend data for the robot in a disaster rescue system, so as to ensure the perception and rescue capability of the robot.

The mobile robot regards itself as the active node, dynamically senses network environment nearby, and achieves self-localization in WSNs. Because of its widespread application prospect, it has become the most advanced research field in the world. The literature [1], which studies less environmental information scene, utilizes global positioning algorithm to form multiple hypotheses problem of robot position, presents a kind of unified framework, and obtains a group of only state of robots based on map structure and measurement information among robots; the algorithm maximizes the estimated position of a group of robots which could only gain hypotheses, and it is proved to help the nonpositioning robots overcome differences. The document [2], which studies the situation that the map of nonstatic environment is too simple and lacks information, proposes a robust position tracking method for mobile robots. The algorithm uses the nondamaged window sample and completes the robustness estimation in the condition of badly damaged observation. Through the comparison with all particles, sample particles comprise plenty of undamaged sets and give the weight values. Nonlinear constrained least-squares optimization is used to correct the errors. The document [3], which studies the phenomenon that RSSI positioning system is seriously affected by obstacles, proposes an improved localization algorithm that can divide the network area into relatively small grids, and maximum likelihood estimation is utilized to calculate the probability density of each grid location. In order to inspect the errors caused by obstacles, the algorithm introduces Min/Max method and specifies boundaries of positioning estimation area. The positioning errors can be corrected by compensating RSSI value. The document [4] studies various factors that interfere with range measurement and proposes a Chirp Spread Spectrum (CSS) based mobile robot localization method. The algorithm implements the range measurement between mobile robot and CSS beacon node according to the flight time of the radio signals; based on the distance data obtained, robot localization is realized by trilateration estimation. Range measurement noise is smoothed by extended Kalman filter (EKF); meanwhile the proportional factor is introduced to handle ranging bias. The method needs to compute the complex proportional factor and be very difficult to calculate. The literature [5] researches position errors during the motion of mobile robots and proposes a new localization algorithm using gyroscope and Kalman filter; the method uses physical constrained parameters provided by general constrained optimization technique. The additional state variables are utilized to improve the state observability, the nonapproximated Kalman filter design is applied for improving the accuracy, and the odometry errors are effectively compensated. Document [6] studies the output-noise covariance matrix in mobile robot localization algorithm and proposes the usage of laser range finder for Kalman filter localization algorithm. The method represents an environment with line segments; then the extended Kalman filter algorithm (EKF) is used to realize positioning. Furthermore, the covariance of the observed environment lines including the output-noise covariance matrix of the EKF, estimation of the covariance of the line parameters based on classic least squares (LSQ), is less computationally complex and more efficient than the orthogonal LSQ. The literature [7] research performance analysis of NLOS scenario proposes the CRLB algorithm in two NLOS situations; the method is suitable for all the noise distribution. The literature [8] provides the solution of the robot body survival and adaptation ability, which is suitable for robot control station in disaster rescue system. To improve the overall performance of the system is of great significance.

The literatures [1, 2, 6] all need to include environmental information map beforehand in order to assist robot of self-localization; adaptability is poor for unknown environment. The literatures [3, 4, 7] study localization scenario of the non-line-of-sight, but they cannot be applied to the network environment with insufficient beacon nodes. In order to ensure the effectiveness of trilateration estimation, literature [4] needs at least three beacon nodes for localization, which are unable to adapt to network blind spots without enough beacon nodes. The paper [5] ignores the influence factors of temperature for the gyroscope; the experimental results need further research. The paper [8] only puts forward design principles of human-machine interaction and does not give specific sense methods for robot.

For large errors and high calculation cost of grid-based maximum likelihood estimation (GMLE), beacon nodes are dynamically selected to improve the grid space in this paper; then for the special case like network blind areas, Kalman filtered grid-based improved maximum likelihood estimation (KGIMLE) is proposed, which carries out dynamic self-localization of the mobile robot. The simulation and experimental results show that the proposed algorithm can effectively reduce the measurement noise and positioning error, especially in the poor node deployment of network blind areas; adaptability and robustness of the positioning results are ensured.

2. RSSI Range Measurement Model

Since wireless signal strength emitted periodically by wireless sensor is decreasing while the propagation distance increases, under the premise of the known transmitted and received signal strength, the signal strength loss is converted into a distance through the mathematical model, in order to estimate the distance between the sending node and the receiving node.

According to various practical application environments, RSSI range measurement shows different features, especially in the dense deployment of WSNs; the complex problems such as reflection and multipath propagation emerge endlessly. In the process of simulation, the following empirical formula is used [9]:

\begin{matrix} P_{t} (d) = P_{0} (d_{0}) - 10 η \log_{10} (\frac{d}{d_{0}}) + X_{σ}, \end{matrix}

(1)

in which

P_{0} (d_{0})

is the reference signal strength of distance

d_{0}

away from the transmitter; η is the signal propagation path fading coefficient, which is corresponding with a specific environment;

X_{σ}

is the normal distribution of random variable caused by shading effect.

According to the experiment requirement, $P_{0} (d_{0})$ is set to −41.1 dBm; the value of η is 3; $d_{0}$ is 1 m; $X_{σ}$ is Gaussian white noise distribution of the random noise with mean value 0 and variance 4.

As shown in Figure 1, with the increase of RSSI transmission distance, signal intensity weakens. The smooth curve is the ideal RSSI measurement values that are not affected by the environment noise and errors of impedance of hardware. In the ideal case, the RSSI ranging error is 0, and the measuring distance and real distance are perfectly matched. But the truth coefficient is affected by the outside world and their own equipment; there is a big measurement error; the irregular curve in the figure shows the scenario that the RSSI measurements are irregular fluctuations under the condition of nonoptimization. And all the values are negative. Because of the distance of 1 m, the signal intensity has been negative already.

Figure 1

Relationship between original RSSI and distance.

Besides the range measurement of RSSI, there are many other wireless signals with radio frequency of 2.4 GHz, such as TOA [10, 11], Wi-Fi, and Bluetooth, which can be utilized in the buildings as an alternative of GPS positioning. Considering the weakness of the ranging information of RSSI, literature [12, 13] has further discussion on the range-free issues. The connectivity topology of wireless sensor networks provides the crucial information of localization. The connection link constrains the node position aside from the link and the estimated position information can be achieved.

3. Grid-Based Improved Maximum Likelihood Estimation

3.1. Algorithm Improvement

Among the node localization algorithms in WSNs, one of the most precise algorithms is maximum likelihood estimation (MLE). There are more application technologies in view of MLE, among the more famous methods; [3] divides network area into several grids, calculates the probability value of each grid, and implements MLE.

The proposed GIMLE algorithm in this paper has improved [3] in three points. Firstly, GIMLE has been applied to the self-localization of mobile robots successfully instead of static node positioning. Secondly, the grid area is dynamically changed based on the position of mobile robots in each sampling time. Last but not least, compared with the network diameter 50 m~150 m in [3], the grid area is reasonably smaller since the effective communication radius of robots is limited. Furthermore, due to the limited grid area, the size of the grid unit is accurate to 0.01 m².

This paper is aimed at the moving trajectory of the mobile robot, because of instantaneous stationary at each sampling time; the mobile robot can be seen as static unknown nodes, and, then, MLE algorithm is established based on the grid probability value. The algorithm looks forward the position information of the beacon node, which is nearest to the mobile robot at a certain time interval point, as the center coordinates, and divides WSNs area around the robot into $R \times R m_{2}$ squares; R is effective communication radius for the robot. It chooses a square as the basic shape of network area division, aimed at achieving seamless connection across cell boundaries easily for computing. The coordinate for the center of a square is that

\begin{matrix} θ_{i j} = {Node}_{k} ∣ d_{{node}_{k}} = \min (d_{{node}_{1}}, d_{{node}_{2}}, \dots, d_{{node}_{n}}), \end{matrix}

(2)

in which

θ_{i j}

is the square center around the robot,

{Node}_{k}

is the beacon node, which is closest to the robot, and

d_{{node}_{k}}

is the shortest estimated distance among detected n beacon nodes to robot.

Since the research area of this paper is focused on indoor localization of mobile robots, the room space is limited compared with the range threshold 15 m of radio frequency signal. The situation of connection failure between the robot and beacon nodes is very rare, while the robot is moving inside the building and the deployment of beacon nodes is prearranged. Even though the connection failure can be caused by physical damage or limited power, Kalman filter algorithm which is suitable for network blind spots in latter section is applicable to handle this scenario.

The actual square area is based on WSNs environment; once the robot moves to the network boundary, the boundary is used as the actual rectangular boundary. In order to improve the positioning precision, 0.01 m² is for the unit and the rectangular area is divided into several grid units. The probability distribution function (PDF) of each grid is calculated separately. Finally, MLE algorithm selects the maximum PDF value of grid centroids as the estimated location coordinates:

\begin{matrix} \hat{θ} = \underset{θ_{i j} \in X}{\arg \max} \overset{m}{\prod_{k = 1}} p (x_{k} ∣ θ_{i j}), \end{matrix}

(3)

in which the grid area X is divided into 0.01 m² square;

θ_{i j}

is the square centroid around the robot.

p (x_{k} ∣ θ_{i j})

is the PDF value of each grid centroid

θ_{i j}

to the kth node coordinate among m beacon nodes.

In the grid area centered by the beacon node nearest to the mobile robot, each grid has its own independent centroid point coordinates. Due to the fact that the robot is moving, the grid area around the robot has been dynamically changed. Combined with robot coordinates and function relation between the communication radiuses of robot with the outside world, the grid centroid coordinate is determined. With the robot coordinate, the network area covered by a specific communication radius can be identified. 0.01 m² is as a unit; the area can be divided into fixed matrix rows and columns of the grid; any ith row and jth column cell of the matrix can be located. Then, the centroid coordinate $ξ_{i j}$ of the grid unit can be identified:

\begin{array}{l} ξ_{i j} = [\min (b_{x} - R, 0) + 0.1 i + 0.05, \\ \min (b_{y} - R, 0) + 0.1 j + 0.05], \end{array}

(4)

in which i and j are the horizontal and vertical axis direction subscript of the square center in the grid area.

b_{x}

and

b_{y}

are the actual horizontal and vertical coordinate of the beacon node closest to the robot.

The probability distribution function is the method of probability theory and applies to the probability rule of random errors. There are different probability distribution forms according to the different random variable types. The distribution function value is the real number of greater than or equal to zero and less than or equal to 1. The distribution function is the right continuous function of monotonic non-decreasing property; the negative infinity is 0; the positive infinity is 1. In this paper, the noise mathematical model of range measurement is Gaussian white noise. The probability distribution function is that

\begin{matrix} p (r_{i j}^{k} ∣ ξ_{i j}) = \frac{1}{\sqrt{2 π} σ} e^{- ({(r_{i j}^{k} - μ)}^{2} / {2 σ}^{2})}, \end{matrix}

(5)

in which

r_{i j}^{k}

is the difference of RSSI value between the grid unit

ξ_{i j}

and the robot received from kth beacon node, μ is the mean value of Gaussian white noise,

σ^{2}

is the variance, and

\begin{matrix} r_{i j}^{k} = P_{t} (d_{i j}^{k}) - {rssi}_{robot}^{k}, \end{matrix}

(6)

in which $d_{i j}^{k}$ is the distance between the grid unit $ξ_{i j}$ and kth beacon node. $P_{t} (d_{i j}^{k})$ is the RSSI value defined by (1). ${rssi}_{robot}^{k}$ is the RSSI value between the robot and kth beacon node. In simulation experiment, the RSSI value is obtained by (1). In CC2530-based experiment, the RSSI value is achieved from received signal of kth beacon node.

The reason for Gaussian distribution used in (5) is that the RSSI values come from (1), which obeys Gaussian distribution.

3.2. Model Analysis

Figure 2 depicts the process of location estimation algorithm. The robot first collects coordinate information of surrounding beacon nodes in the network environment and measures estimated distances between the robot and beacon nodes. Centered on the beacon node closest to the robot, the algorithm establishes a fixed radius length of grid area. The unit is 0.01 m². Then, from the first cell to the last cell, the probability of becoming estimation location of the robot for each cell centroid is calculated. The method is that it measures the probability distribution function between cells and each beacon node, multiplies function value together, and obtains the final probability distribution density of the cell. Finally, MLE algorithm selects the cell centroid with the maximum probability distribution density as the estimated coordinates of the robot.

Figure 2

Grid-based maximum likelihood estimation.

There are two kinds of arrows in the figure, dashed and solid. The solid arrows display that the robot can receive RSSI from beacon nodes. In the meantime, the dashed arrows show that each grid unit, which is an alternative to estimated location of the robot, can simulate the RSSI values of beacon nodes.

As shown in the figure, due to the distance measurement noise and environmental factors, there is often a deviation between the actual location of the robot and estimated position; it makes up the positioning error. The positioning error reduction can be realized through various means. In this paper, the research idea is very new. In order to minimize the possible area of robot in the process of positioning, a grid area centered by the sensor is built up around the actual location of the robot, as an estimation range of the robot position. By limiting the area of search calculation, on the one hand, the positioning accuracy is improved and the range of the positioning error offset is reduced; on the other hand, the computation cost, the computing burden of sensor processor, and the energy consumption are reduced.

The deployment of beacon nodes in WSNs is randomness. Particularly in disaster situations, the destructive factors such as fire, earthquake, and explosion are easy to cause the physical failure and position change of sensor nodes. WSNs may be mutations, have to rebuild the network, and build a new network topology structure. In this paper, the symmetry problem, which means the probability distribution densities may be the same, is avoided mostly for GIMLE algorithm; the effectiveness and robustness of the algorithm are ensured.

When the mobile robot moves to the middle of the network area with symmetry nodes deployment, the localization result of GMLE shown in Figure 3, there is error between the estimated and true position of the robot. After many experiments, the uncertainty of the error is confirmed. Therefore, under the condition of the absolute symmetry nodes deployment, positioning result of GMLE is not failed due to environmental constraints.

Figure 3

Grid-based maximum likelihood estimation in symmetry nodes deployment.

As a result of the existence of ranging error between sensor nodes and the effects of environmental noise, GMLE algorithm can realize the robustness in the symmetry of the network environment. When there is a distance measurement noise, the probability distribution density of the grid has the characteristics of being asymmetric. When the robot moves to the symmetry center position of the network, the 5 m radius square of the grid area around the robot is selected. Each cell in Figure 1 represents the corresponding coordinates of the grid area. The cell value is the probability distribution density of the grid. As shown in Figure 4, the values of probability distribution density emerge as an irregular change phenomenon. This is caused by ranging error according to the random change of Gaussian white noise. Because of the randomness of noise, the probability distribution density is random. Furthermore, the distribution area of probability distribution density is concentrated; GMLE algorithm can rapidly converge to estimate position assuringly.

Figure 4

Asymmetry of probability distribution value of grid with measurement noise.

Under the ideal condition of removing the range measurement and the surrounding environment noise disturbance factors, GMLE algorithm appears symmetry effect, as shown in Figure 5. In the coordinate system of the fixed area, the probability distribution density of the grid is uniform distribution with the characteristics of centrosymmetry; the maximum likelihood values of probability distribution density appear in the adjacent square area at the same time. Since there is no single value, the localization algorithm has the position deviation. As long as there is no noise, symmetry phenomenon has been around. But, in the real environment, ranging error and environmental noise are inevitable; similar situation will not appear.

Figure 5

Symmetry of probability distribution value of grid without measurement noise.

4. Kalman Filtering Algorithm Suitable for Network Blind Spots

When the mobile robot moves in WSNs environment with plenty of beacon nodes, GIMLE algorithm can provide high-precision positioning with small error. However, when the mobile robot moves into the WSNs with poor beacon nodes, the localization result of GIMLE algorithm will be serious distortion; the entire estimated positions even lead to grave deviation from the true locations. Therefore, this paper proposes Kalman filtering algorithm in view of the network blind area; the algorithm can fulfill localization in the case of smaller error.

4.1. Improved Classical Kalman Filter

Kalman filtering fusion is a kind of progressive iteration of the state and parameter estimation method, according to the measurement error, carries out the state correction, and continuously approximates to the real data. Based on the principle of Kalman filtering algorithm, combined with calculation results of the other positioning algorithm, this paper puts forward the classic Kalman recursive filtering algorithm under the condition of linear trajectory of mobile robot.

This paper modifies the sensor ranging observation equation of the mobile robot; the calculation results of any existing localization algorithm, as the measurement data, can be led directly to the observation equation, which reduces the complexity of the mathematical model and computational costs. The Kalman filter positioning algorithm is improved from an independent localization to a joint optimization one; the complex discrete state equation is improved to be a simple linear state equation, and it is one of the main contributions of this paper. Robot measurement equation can be expressed as

\begin{matrix} Z_{k} = {Point}_{k}, \end{matrix}

(7)

in which

Z_{k} \in R^{m}

is the interval measurement vector of the kth sampling time of the sensor carried by the robot;

{Point}_{k}

is the positioning coordinates results of the kth sampling time of the other localization algorithm, such as GIMLE.

Because the prediction coordinate ${\hat{X}}_{k / k}$ of the mobile robot's actual coordinate $X_{k / k}$ can be calculated by $Z_{k}$ and ${\hat{X}}_{k + 1 / k}$ , ${\hat{X}}_{k / k}$ and new measurement $Z_{k + 1}$ can together predict the next moment coordinate; this makes iterative recursive filtering algorithm. The state equation which makes the prediction of $k + 1$ th moment by kth moment is that

\begin{matrix} {\hat{X}}_{k + 1 / k} = {A \hat{X}}_{k / k} + B_{k} u_{k}, \end{matrix}

(8)

in which A is the state transition matrix

[1, v; 0,1]

, v is the velocity of robots in either horizontal or vertical direction,

B_{k}

is the control weighted matrix 1 in either horizontal or vertical direction,

u_{k}

is a control signal, and

\begin{matrix} {\hat{X}}_{k / k} = {[\begin{bmatrix} X_{k / k} & d t \end{bmatrix}]}^{T}, \end{matrix}

(9)

in which

X_{k / k}

is the horizontal or vertical coordinate of robots;

d t

is the unit of time of the robot moving.

When the new measurement localization data $Z_{k}$ arrives,

\begin{matrix} {\hat{X}}_{k + 1 / k + 1} = {\hat{X}}_{k + 1 / k} + K_{k + 1} (Z_{k + 1} - H_{k + 1} {\hat{X}}_{k + 1 / k}), \end{matrix}

(10)

in which

K_{k + 1}

is the filter gain,

H_{k + 1}

is the parameter matrices of the observation equation,

K_{k + 1}

is given by the principle of minimum variance, and

\begin{matrix} K_{k + 1} = P_{k + 1 / k} H_{k + 1}^{T} {(H_{k + 1} P_{k + 1 / k} H_{k + 1}^{T} + R)}^{- 1}, \end{matrix}

(11)

in which R is the Gaussian white noise covariance of measurement; the prediction error variance matrix of

P_{k + 1 / k}

is that

\begin{matrix} P_{k + 1 / k} = {A P}_{k / k} A^{T} + Q, \end{matrix}

(12)

in which $P_{k / k}$ is constant $[1,1; 1,1]$ for both horizontal and vertical coordinates.

The error variance matrix ${\hat{X}}_{k + 1 / k + 1}$ predicted by $P_{k + 1 / k + 1}$ is that

\begin{matrix} P_{k + 1 / k + 1} = P_{k + 1 / k} - K_{k + 1} H_{k + 1} P_{k + 1 / k} . \end{matrix}

(13)

Currently the algorithm applied in the field of mobile robot localization technology is difficult to realize the effective localization of WSNs environment; there is often serious localization deviation in cases of special network. For that, this improved Kalman filtering algorithm increases the mechanism of predictive control and effectively avoids the phenomenon of large errors; the optimization results of localization are close to the real state and parameter values constantly. The control equations are that

\begin{matrix} u_{k + 1 / k} = {\begin{cases} u_{k} - p, & {\hat{X}}_{k + 1 / k + 1} > {\hat{X}}_{k + 1 / k}, \\ u_{k}, & {\hat{X}}_{k + 1 / k + 1} = {\hat{X}}_{k + 1 / k}, \\ u_{k} + p, & {\hat{X}}_{k + 1 / k + 1} < {\hat{X}}_{k + 1 / k}, \end{cases} \\ {\hat{X}}_{k + 1 / k + 1} = {\begin{cases} {\hat{X}}_{k + 1 / k} + s, & {\hat{X}}_{k + 1 / k + 1} > {\hat{X}}_{k + 1 / k} + s, \\ {\hat{X}}_{k + 1 / k} - s, & {\hat{X}}_{k + 1 / k + 1} < {\hat{X}}_{k + 1 / k} - s, \end{cases} \\ s = v \cdot d t, \end{matrix}

(14)

in which

u_{k + 1 / k}

is the iterative control signal; p is the control precision 0.001; s is the unit step length of the mobile robot. If there is still a serious distortion when the robot localization coordinates are processed by classical Kalman filter iteration, the coordinate volatility can be decreased as far as possible and is controlled within a certain accuracy. Once the coordinates seriously run away from effective range, the iteration data is forced to stay within a reasonable range.

In order to reflect that the proposed GIMLE algorithm has better location performance, three localization algorithms which can also run in network blind area are introduced in which Kalman filter improved maximum likelihood estimation algorithm (KIMLE) makes a reasonable improvement of classical MLE algorithm and combines with Kalman filter to realize the localization of blind area. Kalman filter optimizing RSSI ranging and Kalman filter improved maximum likelihood estimation algorithm (KRKIMLE) are based on KIMLE algorithm, plus the process of the Kalman filter optimization of RSSI ranging information, and further improve the positioning accuracy. Kalman filter grid-based improved maximum likelihood estimation algorithm (KGIMLE) is a reasonable complement to GIMLE algorithm and enhances the smoothing effect of the positioning data.

4.2. Virtual Beacon Nodes in Network Blind Area

Due to random deployment of beacon nodes in WSNs, or the environment destructive disasters that destroyed part of beacon nodes, the network blind area comes into being. This paper proposes a virtual beacon node method; the determination of the virtual node coordinates is combined with the improved classical Kalman filter, to ensure the rationality of the algorithm.

When the mobile robot moves to network blind area, as a result of a terrible shortage of the reference beacon nodes, the necessary number of nodes for GIMLE algorithm cannot be met. At this point, the output results of the mathematical model often have dozens of meters of positioning errors, form severe localization deviation, and cause the failure of the whole positioning process. So in the special cases of less than three beacon nodes, with the reference of the optimal coordinate data generated by the improved classical Kalman filter, the enough number of the virtual beacon nodes is produced for GIMLE. Then, the mathematical model of GIMLE algorithm is used to realize localization in absolute network blind area environment. The generation algorithm of virtual nodes is that

\begin{matrix} {VirtureNode}_{k + 1} = {Node}_{k} + RandStep, \end{matrix}

(15)

in which

{Node}_{k}

is the known beacon node coordinates around the mobile robot; RandStep is the Gaussian white noise, whose mean value is 0 and variance is the square of robot step length.

When the estimated distances from the mobile robot to three beacon nodes are known, GIMLE algorithm is initialized. Among the beacon nodes, 1 or 2 can be the virtual node created by Kalman filtering algorithm.

For the absolute network blind spots without any beacon node, this paper also proposes a compensation algorithm and ensures that the algorithm can run smoothly in any network environment. The idea is to make full use of the improved classical Kalman filter to produce optimal coordinates; the virtual positioning coordinates of the mobile robot are randomly generated; then, the coordinates are assumed to be the data of observation equations for the localization algorithm of the mobile robot and imported into the classical Kalman filter in order to be smoothed and optimized.

5. Dynamic Localization Experiment of Mobile Robot as an Active Node

5.1. Simulation Experiment and Result Analysis

In the indoor environment, the mobile robot is set to complete a sampling every $0.5 s$ and lasts for 20 seconds. The mobile robot crosses $50 m \times 50 m$ WSNs monitoring area with random deployment at a speed of $50 m / s$ . The range threshold of radio frequency signal is 15 m.

When the numbers of beacon nodes are different in random deployment, Figure 6 analyzes the statistical information of beacon node number dynamically detected by the mobile robot. In the area of 16 nodes deployed, the robot detects two beacon nodes at four sampling times, detects three beacon nodes at 13 sampling times, and detects more than four beacon nodes at 24 sampling times. With reduction of the node density, the robot has more sampling times to detect network blind area with fewer than three beacon nodes. For example, in the 14-node area, there are four sampling times to detect a beacon node and five sampling times to detect two beacon nodes. In the 12-node area, two beacon nodes are detected up to 26 times. In the 8-node area, 0 beacon nodes are detected at 16 times, a beacon node is detected at 11 times, two beacon nodes are detected at 16 times, and there are no three beacon nodes cases.

Figure 6

The graph of beacon node amount of robot dynamic detection.

In the WSNs localization algorithm, MLE algorithm with better localization accuracy and stronger environment adaptability becomes an important standard of advantages and disadvantages of various localization algorithms. However, MLE algorithm has strict requirement of beacon node number in the surrounding environment; it cannot be less than three beacon nodes. Otherwise, MLE algorithm will fail due to insufficient data. In this paper, the research area of WSNs environment is scarcity of beacon nodes in all experimental environments; network blind area with less than three beacon nodes appears at different degrees. Therefore, this paper treats KIMLE algorithm with stronger robustness as the main measurement to evaluate the other algorithms. The other algorithms are compared with KIMLE algorithm and draw the relevant conclusions of the localization performance.

Figure 7 compares RMSE estimate errors of various kinds of Kalman filtering algorithms in different network blind areas. In the 16-node area, node density is higher; the network blind area is limited to two beacon nodes. The proposed KIMLE algorithm can still run properly, providing a better positioning accuracy. The estimated errors of KIMLE algorithm are slightly higher, but KRKIMLE algorithm is close to optimal estimation. The errors of KGIMLE algorithm are higher. With the further reduction of the node density, the errors of KIMLE algorithm are increasing. When there is an absolute network blind area with 0 beacon nodes, the errors of KRKIMLE algorithm are significantly higher than those of that without distance optimization. The reason is that in the mechanism of Kalman filtering algorithm, the estimated distance of the virtual node is not from the measured data and cannot be effectively smoothed and optimized. With the decrease of the detected beacon node number, the probability density mathematical model of GIMLE algorithm is failing. Although it still can continually output position estimation, the error has been far from the actual location. KGIMLE algorithm comes into the best condition; however, it becomes the most accurate Kalman filtering algorithm among others.

Figure 7

The graph of RMSE of Kalman filter algorithm in blind network.

KIMLE and KRKIMLE are proposed methods in the published paper [14]. Since the algorithms are also verified in a similar scenario, network blind spots, it is reasonable to compare the proposed algorithms with them.

In the area of 8 beacon nodes randomly deployed, Figure 8 describes the scenario that the mobile robot moves through the absolute network blind area and takes sampling information. When the robot starts, only one beacon node can be detected, then enters the absolute network blind spots, and gradually establishes information communication with 2 beacon nodes. In this period, there are 11 sampling times without any beacon node information detected. Only a beacon node's information is detected at 15 sampling times; two beacon nodes are detected up to 15 times. The whole process does not meet the requirement of the normal localization algorithm which needs at least three beacon nodes’ information.

Figure 8

The graph of path and samples of mobile robot in absolute blind network.

Figure 9 is expounded in the error cumulative distribution of the Kalman filtering algorithm in the absolute network blind area. The figure shows that KGIMLE algorithm provides relatively accurate location information with the help of virtual node information. KIMLE algorithm can also be close to the optimal location estimation. Only the errors of KRKIMLE algorithm are bigger.

Figure 9

Cumulative distribution probability of Kalman filter algorithm errors in absolute blind network.

Figure 10 compares the positioning errors of the Kalman filtering algorithms in the absolute network blind area. All the algorithms after Kalman filtering can keep the smoothing estimation information of the localization and have almost no obvious fluctuation. Furthermore, the initial stage can provide a better location performance. However, with the increase of cumulative error, the gap between algorithms begins to widen. KRKIMLE algorithm has the largest errors. The rest of the algorithms can control the errors in small range. Through the absolute network blind area, KGIMLE algorithm works best.

Figure 10

Location estimation error of Kalman filter algorithm in absolute blind network.

Figure 11 describes the role of virtual beacon node to significantly reduce positioning errors in the absolute network blind area. Because of the constraint of the MLE mathematical model, when the number of beacon nodes is less than three, the localization algorithm will not be able to start. The mathematical model must use virtual beacon nodes to reach the minimum requirement. Therefore, in the absolute network blind area environment discussed in this paper, the algorithms need to rely on the virtual beacon nodes to complete localization. This paper only discusses the error comparison between GIMLE and KGIMLE algorithms which can fulfill the localization in absolute network blind area. With the aid of virtual beacon node information, KGIMLE algorithm can keep positioning error smooth and manageable. Because of beacon nodes scarcity, GIMLE algorithm produces obvious position estimation errors, fluctuates in a big range, and cannot effectively localize.

Figure 11

Location estimation error of algorithm based on virtual beacon nodes in absolute blind network.

5.2. Self-Localization Experiment in Grid-Based Deployment

The experimental environment is the $1020 cm \times 630 cm$ laboratory room. Indoor personnel are many; tables and chairs are positioned around the walls; instrument and wireless equipment are relatively abundant; the superposition and interaction effect of various signals is obvious. Considering the actual application situation, CC2530 beacon nodes are hanging on the grid area of the ceiling in advance. The particular location of the ground, which will be reached by the self-localization node, has been marked. In order to avoid the serious effect of the ground reflection, CC2530 self-localization node selects the high level of 50 cm from the ground to collect measurement data. The vertical distance between self-localization node and beacon node is 112 cm. CC2530 self-localization node collects the receiving signal strength information from beacon nodes at each scheduled sample point. The measurements of the same beacon node are averaged, in order to keep the unique data of each beacon node. Then, all the data are imported to the computing device to complete the position estimation.

(1) Four Beacon Nodes’ Localization Experiment. In practice, the room usually deploys 4 beacon nodes. This experiment designs the scenario of 4 beacon nodes deployed with grid topology, as shown in Figure 12.

Figure 12

The graph of 4 anchors’ localization “○” is the beacon nodes with the plenty power energy; “—“ is the actual path passed by self-localization node; “☆” is the estimated path by KGIMLE algorithm.

Figure 13 describes the error cumulative distribution of Kalman filtering algorithm in the scene of 4 beacon nodes. Due to obtaining enough location information of beacon nodes by MLE algorithm, the localization effect is good. The proposed KGIMLE algorithm also shows good positioning effect; the trend of the error cumulative distribution is almost exactly the same as MLE algorithm.

Figure 13

Cumulative distribution probability of Kalman filter algorithm errors in 4 anchors’ scenario.

Figure 14 compares the positioning errors among the algorithms. At each sampling point, KGIMLE and MLE algorithm are very close. Even at individual sampling point, KGIMLE algorithm shows better positioning error.

Figure 14

Location estimation error of Kalman filter algorithm in 4 anchors’ scenario.

(2) Localization Experiment with 3 Beacon Nodes. With the application environment of sparse beacon nodes, this experiment designs the scenario of 3 beacon nodes deployed with grid topology. Figure 15 shows the positioning performance of KGIMLE algorithm.

Figure 15

The graph of 3 anchors’ localization.

Figure 16 expounds the trend of error cumulative distribution of each algorithm in the scene of 3 beacon nodes. Although, compared with KIMLE algorithm, the errors of KGIMLE algorithm increase slightly, it is far better than the trend of error cumulative distribution of KRKIMLE algorithm.

Figure 16

Cumulative distribution probability of Kalman filter algorithm errors in 3 anchors’ scenario.

Figure 17 compares the trend of positioning errors of the various algorithms. As shown in the figure, the position error of KGIMLE and KIMLE algorithm is almost the same in each sample point. Moreover, at each sampling point, they are better than KRKIMLE algorithm.

Figure 17

Location estimation error of Kalman filter algorithm in 3 anchors’ scenario.

(3) Localization Experiment with 2 Beacon Nodes. According to the network blind area in the disaster relief system, with the failure of a large number of beacon nodes caused by the high intensity damage factors, this experiment designs a special scenario with 2 beacon nodes deployed with grid topology. Figure 18 shows the positioning effect of KGIMLE algorithm.

Figure 18

The graph of 2 anchors’ localization.

Figure 19 describes the error cumulative distribution of Kalman filtering algorithm in the network blind area. With the virtual node produced by the Kalman filter, KGIMLE algorithm has good performance of the localization accuracy. In most of the time, it is better than KIMLE and KRKIMLE algorithms.

Figure 19

Cumulative distribution probability of Kalman filter algorithm errors in 2 anchors’ scenario.

Figure 20 compares the position error of the Kalman filtering algorithms in each sample point. KGIMLE algorithm achieves the best positioning accuracy in almost all sampling points. It meets the design requirement in this paper.

Figure 20

Location estimation error of Kalman filter algorithm in 2 anchors’ scenario.

5.3. Localization Experiment of Mobile Robot Based on Grid Deployment

The experimental environment is absolutely the same as the self-localization experimental environment. In indoor beacon node deployment as shown in Figure 21(a), the number of people is many, and activities are intensive. Figure 21(b) shows the CC2530 coordinator connected to the computer via a serial port; the handle of the remote control robot uses wireless communication module connected to the computer, realizing remote wireless communication with a robot. Figure 21(c) shows the scene in which the Voyager II automatic mobile robot carrying CC2530 coordinator implements indoor dynamic localization. Although the moving path in the laboratory has been planning for the mobile robot in advance, in actual execution of the operators, subject to the conditions of their proficiency in control of the handle, under the condition of wireless communication, uncertainty of the response to the control instruction by the mobile robot, and other factors, the practical trajectory of the robot cannot be completely the same as the desired trajectory. Furthermore, the robot's movement speed is affected by factors such as turning and escapes and cannot be constant. Colligating the above constraints, therefore, the actual localization algorithm is designed. From the time of receiving the first signal strength information, every 5-signal strength data into a set, as a sampling point of the positioning algorithm, calculates the range measurement data. The final set of data can increase the range measurement data according to actual circumstances. Each group of data is classified according to different beacon nodes. The signal strength information of the same beacon node calculates mean value. The redundant information of data fusion is implemented.

Figure 21

(a) Grid deployment of anchors. (b) Link among coordinator, remote control, and taptop. (c) Mobile robot.

(1) Localization Experiment of Mobile Robot in 4 Beacon Nodes’ Environment. Under the condition of 4 beacon nodes deployed with grid topology in the room, the beacon node number, which is dynamically detected by the robot, is shown in Figure 22(a). Due to the influence of complex noise environment in the room, the majority of the sampling points detect only three beacon nodes. However, it fully meets the localization requirement of MLE algorithm. Therefore, three algorithms all show good positioning effect. The actual positioning effect is shown in Figures 22(b)–22(d).

Figure 22

Four anchors’ localization of robot. (a) Dynamically detected beacons. (b) Estimated path of KIMLE. (c) Estimated path of KRKIMLE. (d) Estimated path of KGIMLE “○” is the beacon nodes with the plenty power energy; “—“ is the actual path passed by self-localization node; “☆” is the estimated path by KGIMLE algorithm.

(2) Localization Experiment of Mobile Robot in 3 Beacon Nodes’ Environment. In the scenario of 3 beacon nodes deployed with grid topology, the number of beacon nodes detected by mobile robot is reduced significantly; a large number of network blind area phenomena appear, as shown in Figure 23(a). Because the Kalman filter algorithm provides the virtual nodes and positioning optimization, three positioning algorithms complete the localization estimation very well. In particular, the path estimation of KGIMLE algorithm is smooth and accurate, as shown in Figure 23(d).

Figure 23

Three anchors’ localization of robot. (a) Dynamically detected beacons. (b) Estimated path of KIMLE. (c) Estimated path of KRKIMLE. (d) Estimated path of KGIMLE.

(3) Localization Experiment of Mobile Robot in 2 Beacon Nodes’ Environment. In the special scenario of two beacon nodes deployed with grid topology, KRKIMLE algorithm is the only one to have a bigger estimated position deviation. Other localization algorithms perform well. Among them, KGIMLE algorithm is excellent to fulfill the localization estimation; the estimated and scheduled path overlap completely; it reaches the design requirements, as shown in Figure 24(d).

Figure 24

Two anchors’ localization of robot. (a) Dynamically detected beacons. (b) Estimated path of KIMLE. (c) Estimated path of KRKIMLE. (d) Estimated path of KGIMLE.

6. Conclusion

This paper addresses the complex indoor WSNs environment, especially focusing on the solution of the network blind area, which is produced in the process of the random deployment of beacon nodes. A class of Kalman filtering algorithm which is suitable for the network blind area is redesigned here. Through the repeated and extensive experiments, the positioning method shows the low cost, robustness, and simple implementation and can be extended for disaster relief system of the real environment.

Footnotes

Conflict of Interests

The authors declare that they have no conflict of interests regarding the publication of this paper.

References

Bhuvanagiri

Krishna

K. M.

Motion in ambiguity: coordinated active global localization for multiple robots

Robotics and Autonomous Systems 2010 58 4 399 424

2-s2.0-77549086856

10.1016/j.robot.2009.09.006

Lee

J.-S.

Chung

W. K.

Robust mobile robot localization in highly non-static environments

Autonomous Robots 2010 29 1 1 16

2-s2.0-77950062043

10.1007/s10514-010-9184-1

Kong

Kwon

Park

Robust localization over obstructed interferences for inbuilding wireless applications

IEEE Transactions on Consumer Electronics 2009 55 1 105 111

Cho

Kim

S. W.

Mobile robot localization using biased chirp-spread-spectrum ranging

IEEE Transactions on Industrial Electronics 2010 57 8 2826 2835

2-s2.0-77954573733

10.1109/TIE.2009.2036633

Myung

Lee

H.-K.

Choi

Bang

Mobile robot localization with gyroscope and constrained kalman filter

International Journal of Control, Automation and Systems 2010 8 3 667 676

2-s2.0-77953819153

10.1007/s12555-010-0321-6

Teslić

Škrjanc

Klančar

Using a LRF sensor in the Kalman-filtering-based localization of a mobile robot

ISA Transactions 2010 49 1 145 153

2-s2.0-72249085375

10.1016/j.isatra.2009.09.009

Huang

J. Y.

Wan

The CRLB for WSNs location estimation in NLOS environments

Proceedings of the International Conference on Communications, Circuits and Systems (ICCCAS '10)

July 2010

Chengdu, China

83 86

2-s2.0-78249246811

10.1109/ICCCAS.2010.5582044

Wang

Design and implementation of the control station system of a shape-shifting search and rescue robot

Robot 2011 33 2 202 207

2-s2.0-79955664469

10.3724/SP.J.1218.2011.00202

Wang

Tian

Meng

M. Q.-H.

Dual-modal indoor mobile localization system based on prediction algorithm

Proceedings of the IEEE International Conference on Information and Automation (ICIA '09)

June 2009

Zhuhai, Macau

236 241

2-s2.0-70449622969

10.1109/ICINFA.2009.5204928

10.

Geng

Deng

Pahlavan

Modeling the effect of human body on toa ranging for indoor human tracking with wrist mounted sensor

Proceedings of the 16th International Symposium on Wireless Personal Multimedia Communications (WPMC'13)

June 2013

Atlantic City, NJ, USA

11.

Geng

Pahlavan

Modeling indoor TOA ranging error for body mounted sensors

Proceedings of the IEEE 23nd International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC'12)

September 2012

Sydney, Australia

12.

Liu

Chen

Lou

Neural network based mobile phone localization using Bluetooth connectivity

Neural Computing and Applications 2013 23 667 675

2-s2.0-84860189264

10.1007/s00521-012-0950-1

13.

Qin

A dynamic neural network approach for solving nonlinear inequalities defined on a graph and its application to distributed, routing-free, range-free localization of WSNs

Neurocomputing 2013 117 72 80

14.

C.-D.

Feng

Zhang

Y.-Z.

Dynamic localization of mobile robot based on asynchronous Kalman filter

Journal of Northeastern University 2013 34 3 312 316