Positioning of Wireless Sensor Network under Emergency Communication Environment

2.1 Kalman filter

Invented in the 1960s, the Kalman filter mainly estimates the state of the current moment with the minimum mean square error (MMSE) through recursion of the estimate of the previous moment and the observation of the current moment. A typical Kalman filter can be implemented in two steps: estimation and verification. The estimation calculates the a priori value of the current state by the time update equation:

$\hat{X}_{k}^{\text{-}}=A\hat{X}_{k-1}^{{}}+B\hat{U}_{k-1}^{{}}$          (1)

$P_{k}^{\text{-}}=AP_{k-1}^{{}}{{A}^{T}}+Q$             (2)

The verification calculates the posterior estimation of the improved current state by the measurement update equation:

$K_{k}^{{}}=P_{k}^{-}{{H}^{T}}{{\left( HP_{k}^{-}{{H}^{T}}+R \right)}^{-1}}$             (3)

$\hat{X}_{k}^{{}}=\hat{X}_{k}^{\text{-}}+K\left( {{Z}_{k}}-H\hat{X}_{k}^{\text{-}} \right)$               (4)

$P_{k}^{{}}=\left( I-{{K}_{k}}H \right)P_{k}^{\text{-}}$        (5)

2.2 Improved multi-hop collaborative positioning algorithm

1.jpg

Figure 1. The workflow of the improved algorithm

Sawides et al. [22] proposed a multi-hop multilateral collaborative algorithm based on the AHLoS algorithm. Their algorithm iteratively refines the positioning results with Kalman filter, curbs the accumulation of error to a certain extent, and improves the accuracy of node positioning. Moreover, the sufficient conditions are provided for judging whether a node could join the multilateral collaboration. However, the algorithm faces a certain degree of positioning divergence, and requires strong computing power to complete the complex calculations.

To further improve the accuracy and efficiency of the algorithm, this paper proposes an improved multi-hop collaborative positioning algorithm that narrows the initial value range of the Kalman filter. The narrowing weakens the positioning divergence, and improves the effects of subsequent filtering and positioning. The improved algorithm consists of four steps (Figure 1).

Step 1. Generation of collaborative subtrees

The collaborative subtree is composed of several unknown nodes and anchor nodes. Each unknown node has a unique position. The positions of unknown nodes are solved by the equation set of each collaborative subtree, including n unknown variables and at least n equations. Before solving these equations, the uniqueness of node position must be confirmed to prevent incorrect positioning. The subtrees of different structures need to meet different structural requirements for the uniqueness of the position.

(1) Requirements of single-hop multilateral collaboration

In single-hop setting, the basic requirement for an unknown node to have a unique position on a two-dimensional (2D) plane is that it must fall within the range of three noncollinear anchor nodes. There are more than one potential positions, if the anchor nodes are on the same straight line, and if the node configuration is symmetric.

(2) Requirements of multi-hop multilateral collaboration

A set of similar criteria are adopted to judge whether a node within n hops has a unique position. Starting from an unknown node, it is tested whether the node has at least three neighbors with temporarily unique positions. If the node has three neighbors that do not know whether its position is unique, recursive calls will be conducted at each neighbor to determine whether its position is unique. To ensure that each node has at least one link, every node as an independent reference is marked as “used”. This prevents other nodes from reusing the node as an independent reference in subsequent recursive calls. In each step, each unknown node must use at least one reference point, which is not collinear with other reference points.

Step 2. Initial estimation of node position

The initial estimation of node position is to obtain the x and y coordinates of each unknown node by ranging. Figure 2 explains how to derive the range of x coordinate of unknown node C from the coordinates of two anchors nodes A and B. Let a be the distance between an unknown node and anchor node A. Then, the x coordinate of unknown node C falls between x_A−a and x_A+a. Similarly, the shortest path length of the x coordinate of unknown node C is b+c, because anchor node B is two hops away from unknown node C. Therefore, the x coordinate of unknown node C relative to anchor node B is bounded by x_B−(b+c) and x_B+(b+c). On this basis, the x coordinate of unknown node C relative to anchor nodes A and B is bounded by x_B+(b+c) and x_A−a, respectively. This operation needs to be performed from the leftmost and rightmost of each anchor node to obtain the x coordinate of each unknown node.

The same operation is performed to obtain the y coordinate of each unknown node. Then, the bounds of the node on the x and y coordinates are merged to obtain the bounding box of the node. To build the bounding box, the positions of all anchor nodes need to be forwarded to every unknown node along the minimum weight paths. The forwarding direction is the same as the routing of distance vector. The only difference is that the weight is measured distance rather than hop count. The initial position of each unknown node is assumed to be in the center of its bounding box. To obtain a set of good initial estimates, the anchor nodes are arranged on the perimeter of the WSN.

2.jpg

Figure 2. The sketch map of initial estimation of node position

Step 3. Optimization of initial node positions

In the traditional multi-hop collaborative algorithm, the accuracy of node positioning is optimized without initial estimation of node positions. The quality of initial estimations directly bears on the accuracy and efficiency of the positioning results. To avoid positioning divergence, this paper improves computing efficiency and reduces calculation cost by narrowing the range of initial estimation.

3.jpg

Figure 3. The narrowing of initial value range of Kalman filter

As shown in Figure 3, the initial value of conventional Kalman filter is obtained by solving the coordinates of the centroid PRQS of the box formed by the distances between anchor nodes and unknown node. To narrow the search range of initial value, two circles centering on the anchor node are drawn with the distances from the unknown node to the two anchor nodes as the radius, respectively. Then, the coordinates of the centroid of the intersection between the two circles, that is, those of the midpoint of the connecting line between M and N, as the initial value of Kalman filter. In this way, the initial value problem of Kalman filter becomes the geometric problem of finding the centroid coordinates of the intersection. The coordinates M(x_M,y_M) and N(x_N,y_N) of the intersection points M and N can be solved by:

$\left\{ \begin{align}  & {{\left( x-{{x}_{B}} \right)}^{2}}+{{\left( y-{{y}_{B}} \right)}^{2}}={{\left( b+c \right)}^{2}} \\  & {{\left( x-{{x}_{A}} \right)}^{2}}+{{\left( y-{{y}_{A}} \right)}^{2}}={{a}^{2}} \\ \end{align} \right.$          (6)

Then, the initial value of Kalman filter can be obtained by:

$\left\{ \begin{align}  & {{x}_{{{C}^{'}}}}=\frac{{{x}_{M}}+{{x}_{N}}}{2} \\  & {{y}_{{{C}^{'}}}}=\frac{{{y}_{M}}+{{y}_{N}}}{2} \\ \end{align} \right.$        (7)

Step 4. Solving the accurate node positions

Referring to the multi-hop multilateral collaborative positioning algorithm, the LS estimation is selected to solve the initial position of each unknown node accurately. There are two possible computing models for the accurate positioning: centralized computing or distributed computing.

(1) Centralized computing of node position

The positions of unknown nodes are estimated at one central point, using the collaborative subtree and the initial position estimation. A definite set of equations is set up according to the specific structure of the collaborative tree, and then solved by nonlinear optimization. The nonlinear optimization of a multi-hop network containing five-node subtrees can be expressed as:

$\begin{align}  & {{f}_{2,3}}={{R}_{2,3}}-\sqrt{{{\left( {{x}_{2}}-e{{x}_{3}} \right)}^{2}}+{{\left( {{y}_{2}}-e{{y}_{3}} \right)}^{2}}} \\  & {{f}_{3,5}}={{R}_{3,5}}-\sqrt{{{\left( e{{x}_{3}}-{{x}_{5}} \right)}^{2}}+{{\left( e{{y}_{3}}-{{y}_{5}} \right)}^{2}}} \\  & {{f}_{4,3}}={{R}_{4,3}}-\sqrt{{{\left( e{{x}_{4}}-e{{x}_{3}} \right)}^{2}}+{{\left( e{{y}_{4}}-e{{y}_{3}} \right)}^{2}}} \\  & {{f}_{4,5}}={{R}_{4,5}}-\sqrt{{{\left( e{{x}_{4}}-{{x}_{5}} \right)}^{2}}+{{\left( e{{y}_{4}}+{{y}_{5}} \right)}^{2}}} \\  & {{f}_{4,1}}={{R}_{4,1}}-\sqrt{{{\left( e{{x}_{4}}-{{x}_{1}} \right)}^{2}}+{{\left( e{{y}_{4}}-{{y}_{1}} \right)}^{2}}} \\ \end{align}$          (8)

where, R_i,j is the measured distance between two nodes; the value under the square root is the estimated distance; f_i,j is the residual between the measured and estimated distances. The objective function is the minimize the mean squared error (MSE) of all equations:

$F\left( {{x}_{3}},{{y}_{3}},{{x}_{4}},{{y}_{4}} \right)=\min \sum{f_{i,j}^{2}}$       (9)

(2) Distributed computing of node position

Distributed computing takes place across the entire network. Each unknown node is responsible for estimating its own position through local computing and communication with neighbors. This strategy is basically the same as using a distributed Kalman filter, except for three minor differences:

First, the Kalman filtering is performed on the edge of a collaborative subtree. Each node executes single-hop multiple transforms based on its measured distance and the position information from its neighbors. Second, decentralized Kalman filter is replaced with an approximation that does not exchange covariance information. The calculation cost and energy are saved, because of the reduced communication and simplified computation. Third, calculation is driven by the ad-hoc network protocol.

The distributed computing of node position adheres to the following principles: After the first two steps, each node in the collaborative subtree has estimated its position. Since most unknown nodes are not directly connected to anchors, they take the initial estimates of their neighbors as reference points to estimate their positions. Once an unknown node calculates a new estimate, it will propagate the new estimate to its neighbors, which will update their own position estimates based on that estimate. This process will be repeated from node to node across the network until all nodes reach the preset convergence gradient.

The distributed computing process is illustrated in Figure 4. The first node 4 estimates its position with anchors 1 and 5 and node 3 as reference points. Once node 4 propagates its new estimate, node 3 will re-estimate its own position based on the new estimate, in the light of the distances to anchors 2 and 5. Finally, node 4 will make a better estimation based on the new estimate from node 3.

4.jpg

Figure 4. The process of distributed computing

If the above process goes out of control, the position of unknown node will converge to the local minimum, resulting in incorrect estimates. This is mainly attributable to the collaborative subtree with multiple unknown nodes. If two adjacent unknown nodes A and B calculate and propagate their new estimates right after receiving the new estimate from the other party, the two nodes will update their position estimates faster than the other nodes in the subtree. However, this introduces local oscillation to the computing process. Despite the fast convergence to the final estimate, the convergence is not consistent with the global gradient, making the estimates incorrect.

To prevent the problem, the polygon on each node will be executed in a consistent order among all unknown nodes of the subtree, until the polygons of all unknown nodes on the subtree converge to the preset threshold. The sequential execution of the polygons establishes a gradient on each node relative to the global topological constraint, enabling the nodes to compute the global optimal value locally.