Target Positioning with GDOP Assisted Nodes Selection Algorithm in Wireless Sensor Networks

Abstract

In wireless sensor networks (WSN), the geometric distribution of anchor nodes has a significant influence on the positioning accuracy. Geometric dilution of precision (GDOP) can be used to measure the positioning precision of the localization system. In order to select the optimal node combination, traditional algorithms based on GDOP need to spend much time on calculating every possible combination of nodes. This paper proposes GDOP assisted nodes selection (GANS) algorithm to calculate GDOP value of the current geometric distribution. Sensor node's contribution to the overall GDOP value is adopted as the evaluation criteria. The nodes whose contribution value is greater than the threshold will be selected. The anchor nodes subset, which participates in the positioning, will be real-time determined. Simulation results show that the GANS algorithm can effectively reduce the energy consumption of the system, while the positioning accuracy has no obvious loss. Meanwhile, computational complexity is also obviously decreased.

1. Introduction

In GPS-denied environments, such as office and commercial building, wireless sensor network (WSN) is getting increasing attention for target localization and tracking [1–3]. Relying on a large number of sensor nodes which have the ability of communication and computation, WSN can complete specified tasks independently under different environmental conditions.

Generally, it is assumed that some sensor nodes undertake the tasks via information sharing and cooperation [4, 5]. However, in most situations, only a few sensor nodes need to take part in a specific activity. For instance, a moving target may enter into the monitoring scope of ten sensor nodes, but three of them are enough to attain localization task simultaneously. Furthermore, the physical constraints, such as energy and sensing ability of WSN, should also be considered. Therefore, it is necessary to determine how many and which sensor nodes should participate in the cognitive task so as to minimize information redundancy and energy consumption while still providing the necessary accuracy [6–8]. The performance of nodes selection algorithm will directly affect the quality of services provided by the WSN. Undoubtedly, the environmental factors have great influence on nodes selection strategy.

For WSN localization, series of indices, such as root mean square error, cumulative probability distribution, and mean variance of the error, have been raised to evaluate the performance of different algorithms [1, 2]. Some researchers also introduce the environment factors into the evaluation of algorithms. One important concept is the geometric dilution of precision (GDOP) [5, 9–12]. GDOP is defined as the ratio between the error of ranging measurement and that of localization. Since it can separate the geometry factor out of the localization error, GDOP shows superior property for WSN application.

In this paper, we introduce GDOP into nodes selection strategy to enhance the performance of the positioning system. For deployed nodes, the GDOPs of their combination are calculated at certain time intervals. Considering that lower GDOP indicates better position precision, the nodes’ combination which has the lowest GDOP is selected to take part in target localization. With this selective method, the energy consumption and information redundancy can be reduced effectively, and the positioning accuracy is guaranteed.

This paper is organized as follows. In Section 2, we summarize the related work. Section 3 states our proposed algorithm and models. In Section 4, simulation experiments are conducted on the nodes selection strategy proposed, while necessary analysis is given. Finally, Section 5 concludes the paper.

2. Related Works

WSN is always deployed in large scale and complex environment, where the lifetime of sensor nodes is severely curtailed by the limited battery power. One line of research in sensor network lifetime management has examined sensor selection techniques, in which applications judiciously choose which sensors’ data should be retrieved [6–8, 13, 14].

The problem of node selection for distributed sensor networks has begun to receive much attention [2–4, 6–8, 13–16]. Cardei and Du [14] analyzed the sensitivity of the WSN and pointed out that the energy consumed by “active” nodes is 100-fold as that of the “sleep” ones. Therefore, switching the nodes between “active” and “sleep” state by proper strategy would be an efficient method for enhancing energy efficiency. The authors organized the sensors into a maximal number of disjoint sets, which could be activated successively to prolong the lifetime of the network. However, defects still exist in data acquisition quality and efficiency. Bian et al. [6] converted the nodes selection problem into a compromise whose target was to select a set of nodes with the minimum energy consumption and maximal utility. Before that, the authors proposed a framework wherein the application could specify the utility of measuring data (nearly) concurrently at each set of sensors.

Some researchers began to consider introducing the target state and trajectory information to optimize the algorithm. Kaplan [3] investigated the global node selection (GNS) method. The coordinates of all nodes are used to determine whether they should participate in the collaborative coprocessing. The GNS algorithm could get the filtered minimum RMSE. However, this method is only appropriate for smaller network because the broadcast of sensor nodes’ location information made a large amount of data communication. On this basis, Kaplan [16] proposed autonomous node selection (ANS) algorithm to improve the GNS algorithm. The knowledge of the target is used to determine whether a sensor node should actively collect measurements. Combining the a priori information with controlling transmission range, it was conducive for energy efficiency, while the accuracy could be guaranteed at the same time. Zhang and Cao [4] proposed combining motion state with target trajectory for estimation. Multinode cooperative dynamic transfer tree was put forward to detect the target tracking and its surrounding area. Adjusting the nodes dynamically, the generated nodes tree had lower energy consumption and higher information content. However, the data fusion of the root node and the calculation of new nodes would consume considerable energy.

Through collaboration of sensor nodes, the target area can be monitored more comprehensively and accurately. Chen et al. [7] proposed a grid-based nodes selection method based on coverage controlling method. The coverage of the sensors was represented by a number of sample points, that is, the intersection points of the established grid. A simple approximation algorithm and a linear programming method were employed to select as few sensors as possible to cover all sample points. The algorithm adopts the distributed method to disperse the nodes’ computing load and the signal transmission overhead was reduced. However, as the density of grid nodes changed, the monitoring performance of the network would change greatly. Xing et al. [13] proposed a Cover Configuration Protocol (CCP) which divided the nodes into “sleep” state, “listen” state, and “active” state. This proposed protocol can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. A geometric analysis of the relationship was made between coverage and connectivity. Then, CCP was integrated with SPAN to provide both coverage and connectivity guarantees.

For navigation and tracking systems, GDOP has been widely used as a performance metric. Since high localization accuracy always requires accurate distance measurement and good geometric relationship between the target and the sensor nodes, it is necessary to analyze GDOP in determining the performance of a positioning system. Levanon [9] took the lead in giving the theory expression of GDOP in 2D environment. The theoretic minimum value of GDOP was also calculated and derived to be $2 / \sqrt{N}$ when there were N nodes in the network. On this basis, Sharp et al. [10] proposed a simpler method under different geometric distributions. In order to solve the contradiction between the distance measuring range and the positioning error, Sharp et al. [11] simplified the expression of GDOP for TOA (time-of-arrival) model. The expression was constructed as a function of nodes density and measuring range, which was more conducive for real-time calculation. Instead of fixed deployment, the analysis was carried on statistical data. Chu et al. [12] raised the GDOP assisted location estimation (GOLE) algorithm. GDOP was used to eliminate the effect of the geometry factors on the precision of positioning system. The LS method was used to get the initial estimated position of the mobile device. By calculating the GDOP value, the coordinates of virtual nodes were acquired and transferred so that they could be used as the new input of the LS method. This method was only applicable for small networks due to the high complexity of the algorithm.

Generally, researchers mainly aimed at a relatively simple analytical expression without complex numerical calculation. However, disadvantages such as large amount of calculation still exist. In this paper, we propose a GDOP assisted nodes selection algorithm (GANS). The algorithm can complete the nodes selection task without losing much accuracy. At the same time, the energy will be saved and the communication traffic will be reduced.

3. GDOP Assisted Nodes Selection Algorithm

3.1. Geometric Dilution of Precision

Researchers have proposed a series of evaluation mechanisms to evaluate the positioning system and algorithm. As a typical index, the Cramer-Rao lower bound [5] (CRLB) serves as a benchmark of the non-Bayesian estimator. It is impossible to get an unbiased estimator of which the variance is less than CRLB. This characteristic makes CRLB a natural standard to compare the performance of unbiased estimator [17]. Meanwhile, the positioning algorithm can also be evaluated by the root mean square error (RMSE) and the cumulative probability distribution [18]. However, it is quite necessary to separate the statistical error from geometric error of the factors.

In WSN, distance measurement is the central step of localization algorithm. Distance information obtained TOA or RSSI inevitably contains a certain measurement error [19–22]. In the indoor environment, due to the block wall and indoor display, non-line-of-sight error inevitably exists. Unlike the random error, the mean of the error is a positive value. At the same, the mean of the random error is always zero. Hence, the obtained distance measurement will have a positive error, which makes the measurement greater than the actual distance. As is shown in Figure 1, the solid line shows the true distance between the mobile device and anchor node, while the dotted line represents the measurement distance. The gap between them is the ranging error quite sensibly. AN1 and AN2 represent the anchor nodes and the rectangle at the center represents the mobile device. d is regarded as the Euclidean distance between AN1 and AN2.

Figure 1

Geometric distribution's influence on positioning accuracy.

The shaded region in Figure 1 represents the possible area in which the position results may occur. This region can also be regarded as the position error range. With the same measurement error variation, the accuracy of the position results is some different for the two cases above. The scenario, which has a more scattered nodes distribution, obviously has a better positioning accuracy, because when the node distribution is more dispersed, the positioning results will appear in a region which is smaller. Hence, the geometric factor has a significant influence on the positioning result. GDOP is defined as the ratio between ranging error and position error, and a smaller GDOP value indicates a higher accuracy [23]. GDOP can be represented as

\begin{matrix} Δ X = GDOP \cdot Δ ρ, \end{matrix}

(1)

where $Δ ρ$ and $Δ X$ represent the ranging error and the positioning error, respectively. Compared with the ranging radius, the ranging error is quite small. Therefore, the position error range can be seen as a parallelogram. As a parallelogram, the position error range's acreage equals the product of the bottom edge multiplied by the height. The height is equivalent to the ranging error which is relatively fixed. But the length of the bottom edge will increase when the nodes approach. It is clear that the distance between AN1 and AN2 is larger and the position error range is smaller. But Figure 1(b) gives the situation that the GDOP value is bigger and the position error range is also bigger. The situation is similar to the above analysis when more nodes exist. If measurement error keeps constant, the GDOP value of the mobile device's location will become the main factor that limits the system's positioning precision [24, 25].

3.2. The Computational Formula of GDOP in WSN

3.2.1. The Cramer-Rao Lower Bound

The Cramer-Rao lower bound (CRLB) is widely used in parameter estimation. It can provide a lower limitation for the variance of any unbiased estimator. The expression of CRLB can be derived from the inverse matrix of the Fisher information metric (FIM) [26, 27]. It is assumed that the vector needs to be estimated as $θ = {(θ_{1}, θ_{2}, \dots θ_{L})}^{T}$ and L indicates the number of unknown parameters. The FIM can be represented as

\begin{matrix} J_{θ} = E_{θ} {(\frac{\partial \log}{\partial θ} f (Λ | θ)) {(\frac{\partial \log}{\partial θ} f (Λ | θ))}^{T}} . \end{matrix}

(2)

The parameter $J_{θ}$ represents a $L \times L$ metric. $f (Λ | θ)$ are the joint density functions of vector Λ. Λ is the measurement conditions vector of θ. When $f (Λ | θ)$ obey a P-dimensional Gaussian distribution,

\begin{array}{l} f (Λ | θ) \\ = \frac{1}{{(2 π)}^{p / 2} {| Q |}^{1 / 2}} \exp (- \frac{{(Λ - μ (θ))}^{T} Q^{- 1} (Λ - μ (θ))}{2}), \end{array}

(3)

where $μ (θ)$ is the expectation of Λ, while Q represents a covariance matrix independent of θ. We can get $J_{θ}$ through submitting (3) into (2):

\begin{matrix} J_{θ} = {(\frac{\partial μ (θ)}{\partial θ^{T}})}^{T} Q^{- 1} (\frac{\partial μ (θ)}{\partial θ^{T}}) . \end{matrix}

(4)

Let matrix $H = \partial μ (θ) / \partial θ^{T}$ ; the CRLB can be expressed as

\begin{matrix} J_{θ}^{- 1} = {(H^{T} Q^{- 1} H)}^{- 1} . \end{matrix}

(5)

3.2.2. The Expression of GDOP

In the WSN, assuming that the location of the ith anchor node is $(x_{i}, y_{i}) (i = 1,2, \dots, N; N \geq 3)$ , the mobile device's coordinates are $Ψ = {(x, y)}^{T}$ . In order to make a thorough analysis of sensor nodes’ geometric distribution influence on positioning accuracy, the measurement error will not be discussed in this paper. The distance between ith anchor node and the mobile device is

\begin{matrix} r_{i} = \sqrt{{(x - x_{i})}^{2} + {(y - y_{i})}^{2}} + ε_{i}, \end{matrix}

(6)

where $ε_{i}$ represents the measurement error in the equation above. It obeys zero mean Gaussian distribution in the line-of-sight (LOS) environments. The observation matrix from the mobile device to the ith anchor is

\begin{matrix} H = \frac{\partial μ (θ)}{\partial θ^{T}} = [\begin{bmatrix} \frac{x - x_{1}}{r_{1}} & \frac{y - y_{1}}{r_{1}} & 1 \\ \frac{x - x_{2}}{r_{2}} & \frac{y - y_{2}}{r_{2}} & 1 \\ \begin{matrix} ⋮ \\ \frac{x - x_{N}}{r_{N}} \end{matrix} & \begin{matrix} ⋮ \\ \frac{y - y_{N}}{r_{N}} \end{matrix} & \begin{matrix} ⋮ \\ 1 \end{matrix} \end{bmatrix}] . \end{matrix}

(7)

The covariance matrix Q can be represented as

\begin{matrix} Q = σ_{R}^{2} [\begin{bmatrix} 1 & 0 & \begin{matrix} 0 & 0 \end{matrix} \\ 0 & 1 & \begin{matrix} 0 & 0 \end{matrix} \\ \begin{matrix} 0 \\ 0 \end{matrix} & \begin{matrix} 0 \\ 0 \end{matrix} & \begin{matrix} \begin{matrix} 1 & 0 \end{matrix} \\ \begin{matrix} 0 & 1 \end{matrix} \end{matrix} \end{bmatrix}] . \end{matrix}

(8)

Here, $σ_{R}$ represents the root mean square measurement error. It will keep consistent to all nodes. Submitting matrix H and matrix Q into (5), ${J_{θ}}^{- 1}$ is derived. The fundamental formula of GDOP is defined in terms of the expectations of the squares of the position (x and y coordinates) errors and the ranging error. Its value is determined by

\begin{matrix} GDOP = \sqrt{\frac{E (Δ x^{2}) + E (Δ y^{2})}{E (Δ R^{2})}} = \frac{\sqrt{σ_{x}^{2} + σ_{y}^{2}}}{σ_{R}} . \end{matrix}

(9)

In the LOS environment, the measurement error obeys zero mean Gaussian distribution, so the covariance matrix can be expressed as $Q = σ_{R}^{2} I$ , among which I represents the identity matrix. The expression can be obtained based on the theory of CRLB:

\begin{matrix} GDOP = \sqrt{trace {(H^{T} \cdot H)}^{- 1}} . \end{matrix}

(10)

Involving matrix inversion and matrix multiplication, the computational complexity will be greatly increased when the dimensions of matrix H grow up [28].

Nodes are deployed in the 100 × 100 area, and the GDOP distribution maps are shown in Figures 2 and 3. It is clear that the GDOP inside the regular N-side polygon is quite smaller than that outside the regular N-side polygon. Furthermore, the smallest GDOP value $2 / \sqrt{N}$ can be obtained when the mobile device located at the center of the polygon. As shown in Figures 2 and 3, when there are four nodes, the GDOP value of the central region is 1.02. This value approaches the minimum theoretic value. When there are three nodes, the GDOP value of the central region is 1.19 and approaches the minimum theoretic value 1.15 for the 3-AN case [29].

Figure 2

Equipotential line of GDOP distribution when there are three anchor nodes.

Figure 3

Equipotential line of GDOP distribution for four nodes.

3.3. GDOP Assisted Nodes Selection Algorithm

The traditional GDOP-based nodes selection algorithms usually calculate all the GDOP values of different combinations. The combination which has the smallest GDOP value will be selected to participate in the positioning. However, the computational complexity of this conception is too high that it is not suitable for practical application. In order to reduce the computational complexity, researchers have raised some methods such as neural networks, support vector machine, and genetic algorithm [30]. These methods can effectively reduce the computational complexity in different extent.

Theoretically, the more the nodes participate in the calculation, the lower the GDOP value of the combination will be, which represents a higher positioning accuracy. Our proposed GANS algorithm calculates the GDOP variation of different times. Through this method, we can obtain an anchor nodes subset which has the optimal GDOP value. Quite a few matrix inversions and matrix multiplication are avoided with GANS algorithm. Therefore, the GANS algorithm has a great advantage on direct nodes selection methods in terms of computational complexity.

Assume that $H_{m}$ is the observation matrix of m nodes. If the ith node is removed from the m nodes, the observation matrix of these $m - 1$ nodes will change to $H_{m - 1}^{i}$ ; the relationship between the two matrixes is

\begin{matrix} H_{m}^{T} H_{m} = {H_{m - 1}^{i}}^{T} H_{m - 1}^{i} + h_{i}^{T} h_{i} . \end{matrix}

(11)

Assume that $h_{i}$ is the observation matrix of the ith node and ${{(H}_{m}^{T} H_{m})}^{- 1}$ equals $G_{m}$ . According to the Sherman-Morrison formulation [31],

\begin{array}{l} G_{m}^{i} = {({H_{m - 1}^{i}}^{T} H_{m - 1}^{i})}^{- 1} = {(H_{m}^{T} H_{m} - h_{i}^{T} h_{i})}^{- 1} \\ = G_{m} + G_{m} h_{i}^{T} {(1 - h_{i} G_{m} h_{i}^{T})}^{- 1} h_{i} G_{m}, \end{array}

(12)

where $(1 - h_{i} G_{m} h_{i}^{T})$ is a scalar which is recorded as $λ_{m i}$ . Squaring the GDOP expression we can obtain the following:

\begin{array}{l} {GDOP}_{m - 1}^{i}^{2} = trace G_{m - 1}^{i} \\ = {GDOP}_{m}^{2} + trace (\frac{G_{m} h_{i}^{T} h_{i} G_{m}}{λ_{m i}}) . \end{array}

(13)

The equation above can also be expressed as

\begin{matrix} {GDOP}_{m - 1}^{i}^{2} - {GDOP}_{m}^{2} = trace (\frac{G_{m} h_{i}^{T} h_{i} G_{m}}{λ_{m i}}) . \end{matrix}

(14)

Let $trace (G_{m} h_{i}^{T} h_{i} G_{m} / λ_{m i}) = Δ G_{i}$ ; $Δ G_{i}$ represents the variation by removing the ith nodes. A bigger $Δ G_{i}$ indicates a larger contribution to ${GDOP}_{m}$ . If the ith anchor node is removed in the nodes selection process, the GDOP value will have a dramatic change and bring a big influence upon the positioning accuracy. Therefore, in the GANS algorithm, the subset with bigger contribution is seen as the one which has the optimal geometric distribution. Then, it will be used as the output of the GANS algorithm instead of using all the anchor nodes.

As we know, matrix multiplication and inversion require a lot of computation time. In the traditional GDOP-based nodes selection algorithm, n nodes will be selected from m anchor nodes. In order to select a subset which has the smallest GDOP, matrix multiplication and inversion should be executed for $C_{m}^{n}$ times. In the GANS algorithm, only 1 time matrix inversion and $5 \times m + 1$ times matrix multiplication are needed. Therefore, the computational complexity will be greatly reduced. The computational complexity is shown in Table 1 when $n = 4$ . It can be seen that the GANS algorithm has an obvious advantage. If there are more sensor nodes, the advantage will be greater.

Table 1

Comparison of computational complexity between traditional algorithm and GANS algorithm.

Total number of selected nodes	Traditional algorithm		GANS algorithm
Total number of selected nodes	Matrix inversion	Matrix multiplication	Matrix inversion	Matrix multiplication
8	70	70	1	41
9	126	126	1	46
10	210	210	1	51
11	330	330	1	56
12	495	495	1	61

3.4. Algorithm Design Process

The algorithm's design process is shown in Algorithm 1. When the mobile device locates in the scenario, the observation matrix of all nodes will be obtained firstly and the GDOP value of current position will be computed. The GDOP obtained will be compared with the threshold $φ = 1.5$ . There is practical significance for the GANS algorithm only when the ${GDOP}_{m}$ is above the threshold. Afterwards, the $Δ G_{i}$ of each node will be calculated and sorted.

Algorithm 1: Formal description of GANS algorithm.

GANS Algorithm:

Step 1. Calculate the current GDOP value;

Step 2. Compare the GDOP with threshold $φ = 1.5$ ;

If GDOP is larger than φ, go to Step 3;

Else go to Step 5;

Step 3. Calculate and sort the $Δ G_{i}$ of each node;

Step 4. Compare the $Δ G_{i}$ with threshold $δ = 0.2$ ;

If larger than δ, it should be kept to participate in positioning operations;

If smaller than δ, it will be screened out;

Step 5. Positioning with the LS method.

In order to reduce the communication traffic and the energy consumption, some certain nodes need to be removed from the positioning nodes set. As expounded in Section 3.3, the nodes which have weak influence on the positioning accuracy will be the key point focused on by the proposed algorithm. If the contribution $Δ G_{i}$ of the ith anchor node is less than the threshold δ, the node's contribution to the existing geometric distribution will be considered to be quite limited. According to the empirical value of trial and error and repeated experiments, the threshold δ is set to be 0.2. This could insure that the $Δ G_{i}$ will not produce a big influence on the positioning accuracy. The anchor nodes whose $Δ G_{i}$ is smaller than the threshold δ will be removed. If all of the $Δ G_{i}$ are bigger than δ, all of the anchor nodes will participate in the positioning operation.

In this way, the number of the nodes participating in the localization calculation will be reduced. The computational complexity, communication, and energy consumption will all be reduced as a positive result.

4. Simulation Analysis and Verification

The WSN tracking area is set to be 100 m × 100 m, and the nodes are randomly distributed within a certain scope. As shown in Figure 4, three kinds of node distribution region are considered: (1) 50 * 80 region; (2) 100 * 100 region; (3) 50 * 50 region.

Figure 4

Three different nodes distributions and motion trail.

GDOP curves under three different node distributions are shown in Figure 5. When the nodes’ distribution obeys the first distribution, trajectory is not surrounded by the nodes and the node distribution is relatively dispersed. According to the previous discussion, the GDOP value will become larger when the trajectory is not surrounded by the nodes. In the region $[0 < x < 18]$ , the trajectory goes beyond the coverage of the nodes, the nodes’ geometry variation relative to the trajectory became worse. Hence, the GDOP value of this time is quite large. As a comparison, when the nodes’ distribution obeys the second distribution or the third distribution, the GDOP value is relatively small. In the third nodes distribution, the trajectory has been surrounded since the early step. So its GDOP value is the most ideal one. In the region $[19 < x < 50]$ , the trajectory is surrounded in all three nodes’ distribution. Hence, the smallest value of GDOP of the three nodes’ distribution occurs in this time period. After the time point when $x = 50$ , the trajectory begins to go beyond the nodes’ surrounding in the first and third nodes’ distribution. As the trajectory goes further, the GDOP value will increase rapidly. Because the angle between the trajectory and the third nodes’ distribution is larger than the first nodes distribution, the GDOP value of the third distribution is larger than the first distributions. The second distribution is somehow different, because the trajectory is still surrounded by its nodes after the time point when $x = 50$ . Hence, its GDOP is still reasonably ideal. On the whole, GDOP value will become worse when the nodes’ distribution is relatively concentrated and deviated from the possible trajectory range.

Figure 5

GDOP curves under different node distributions.

Therefore, when the GDOP value varies in comparatively ideal interval, it is necessary to make sure that the anchor nodes throughout the region cover the whole area as large as possible. The area should be covered as much as possible where the mobile device possibly occurs.

Since the WSN is often used in dangerous environment such as industrial environment or in the military field, sensor nodes in such an environment cannot guarantee that the target area can be completely covered. Therefore, the first case mentioned above is closer to the actual situation. In the GANS algorithm validation, the first kind of nodes distribution is selected. Ten anchor nodes are deployed in a $[0 < x < 50, 20 < y < 100]$ region. We assume that mobile device moves in 2D planes and the sampling frequency is 100 Hz. That is, the sampling times are set to be 100 times, while the sample period is 1s. The LS method is used in this paper to fulfill the positioning task, which guarantees quadratic sum of the difference between the measured distance and the estimated distance. In the TOA based location system, the ranging errors could be quite small in line-of-sight (LOS) environment. Because the non-line-of-sight (NLOS) ranging error is not within the discussed scope of this paper, the ranging error during the simulation process is set to be 5%. Based on the current ranging technology, the measurement noise is set as $R = 4$ m².

The target's tracking trajectories with and without GANS algorithm are shown in Figure 6. Mobile device begins to move at (0, 0); then $Δ G_{i}$ of each node is calculated at fixed time interval. According to the $Δ G_{i}$ , all of the anchor nodes will be sorted. Proper nodes will be selected to participate in positioning operations. At some certain moments, the ${GDOP}_{m}$ of all the nodes is not large enough. Few nodes will be removed even though the GANS algorithm is used. For this situation, another threshold is set as $φ = 1.5$ . The GANS algorithm will be used only when the ${GDOP}_{m}$ is above the threshold φ. Since the matrix multiplication and inversion will take up most of the operation time in calculating GDOP, the computation speed of mobile device is limited. In order to minimize the algorithm's running time, time interval is set as 10 seconds. It means that the ${GDOP}_{m}$ will be calculated at each interval of 10 s to decide whether to use the GANS algorithm or not.

Figure 6

Target tracking trajectory.

Figure 7 shows the number of nodes participating in the localization for both cases at different time. It can be seen that, most of the time, the number of nodes participating in the localization is less than 10. It is visible that the GANS node selection algorithm has a remarkably practical effect. As described in literature [4], the “unactivated” nodes will stay in “sleep” state and the “active” state will consume 100 times of energy than “sleep” state. Combined with the simulation results in Figure 4, the GANS node selection algorithm will save about 44.56% of the energy in this scenario.

Figure 7

Number of nodes in different time to participate in orientation.

Figure 8 shows the error curves in both cases. The positioning accuracy will have some inevitable loss because of the reduction of the number of nodes involved in the location calculation. This is just a result of the utilization of GANS algorithm. According to the simulation result, the positioning error without GANS algorithm is 2.145 m. Correspondingly, the positioning error with the GANS algorithm is 2.237 m. The loss in accuracy is not so obvious.

Figure 8

Positioning error curve.

The comparison of computational complexity between traditional nodes selection algorithm and the GANS nodes selection algorithm is shown in Figure 9.

Figure 9

Comparison of computational complexity.

As mentioned above, matrix multiplication and inversion will take up most of the operation time. Therefore, the execution time of these two kinds of complex operation is used to characterize the computational complexity of the algorithm. Since the principles of these two kinds of algorithm are not the same, the number of nodes selected by the GANS algorithm in each time will be used as the selected target numbers of the direct selection algorithm. It can be seen from the simulation result that the GANS algorithm has an obvious advantage in decreasing the computational complexity except for a few moments.

Figure 10 shows the case when the mobile device exactly passes through the node set including three sensor nodes. These nodes’ coordinates are (30, 25), (37, 25), and (55, 30), respectively, corresponding to the curve absence. When the mobile device passes through the node exactly, it is unable to get the observation vector H. Therefore, the GDOP value cannot be acquired through computation at this point. Under certain conditions, GDOP values may also change abruptly on the numerical value. This condition should be avoided for practical application.

Figure 10

GDOP curve with the mobile device passing through the node set exactly.

5. Conclusion

Aiming at node selection problem in wireless sensor networks with geometric constraint thought, we propose a GDOP assisted nodes selection algorithm. The GANS algorithm maintains the positioning accuracy when the system's energy consumption is effectively reduced. Simulation experiment is carried out in order to verify the effectiveness of our proposed algorithm. Results show that the algorithm has good positioning performance and lower computational complexity, which is superior to the traditional node selection algorithm based on GDOP. The GANS algorithm can be used in wireless sensor network for positioning and tracking moving targets. Since the mobile device's speed is relatively low, the false alarm and underreporting situation are not taken into consideration in the paper. In the following research, the influence of node's specific location on $Δ G_{i}$ and the abrupt change of GDOP value will be deeply researched.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This paper is supported by the National Natural Science Foundation of China (no. 61273078), the China Postdoctoral Science Foundation (no. 2012M511164), the Chinese Universities Scientific Foundation (N130404023), and the Liaoning Doctoral Startup Foundation (no. 20121004).

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

2-s2.0-0037086890

10.1016/S1389-1286(01)00302-4

Kulkarni

R. V.

Forster

Venayagamoorthy

G. K.

Computational intelligence in wireless sensor networks: a survey

Communications Surveys & Tutorials 2011 13 1 68 96

Kaplan

L. M.

Global node selection for localization in a distributed sensor network

IEEE Transactions on Aerospace and Electronic Systems 2006 42 1 113 135

2-s2.0-33644906112

10.1109/TAES.2006.1603409

Zhang

Cao

DCTC: dynamic convoy tree-based collaboration for target tracking in sensor networks

IEEE Transactions on Wireless Communications 2004 3 5 1689 1701

2-s2.0-7544235797

10.1109/TWC.2004.833443

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

Bian

Kempe

Govindan

Utility-based sensor selection

Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN ′06)

April 2006

11 18

2-s2.0-34247341818

10.1145/1127777.1127783

Chen

Tzeng

N.-F.

Grid-based approach for working node selection in wireless sensor networks

Proceedings of the IEEE International Conference on Communications

June 2004

3673 3678

2-s2.0-4143081625

Yin

Zhou

Algorithm for energy-aware sensing node selection in wireless sensor networks

Computer Engineering 2008 11 article 003

Levanon

Lowest GDOP in 2-D scenarios

IEE Proceedings: Radar, Sonar and Navigation 2000 147 3 149 155

2-s2.0-0033704277

10.1049/ip-rsn:20000322

10.

Sharp

Guo

Y. J.

GDOP analysis for positioning system design

IEEE Transactions on Vehicular Technology 2009 58 7 3371 3382

2-s2.0-69549105982

10.1109/TVT.2009.2017270

11.

Sharp

Hedley

On the GDOP and accuracy for indoor positioning

IEEE Transactions on Aerospace and Electronic Systems 2012 48 3 2032 2051

2-s2.0-84863926833

10.1109/TAES.2012.6237577

12.

Chu

L.-C.

Tseng

P.-H.

Feng

K.-T.

GDOP-assisted location estimation algorithms inwireless location systems

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM ′08)

December 2008

New Orleans, La, USA

5404 5408

2-s2.0-67249160795

10.1109/GLOCOM.2008.ECP.1032

13.

Xing

G. L.

Wang

X. R.

Zhang

Y. F.

Integrated coverage and connectivity configuration for energy conservation in sensor networks

ACM Transactions on Sensor Networks 2005 1 1 36 72

14.

Cardei

D.-Z.

Improving wireless sensor network lifetime through power aware organization

Wireless Networks 2005 11 3 333 340

2-s2.0-24044520078

10.1007/s11276-005-6615-6

15.

Stine

J. A.

De Veciana

Improving energy efficiency of centrally controlled wireless data networks

Wireless Networks 2002 8 6 681 700

2-s2.0-0036847412

10.1023/A:1020379326558

16.

Kaplan

L. M.

Local node selection for localization in a distributed sensor network

IEEE Transactions on Aerospace and Electronic Systems 2006 42 1 136 146

2-s2.0-33644891309

10.1109/TAES.2006.1603410

17.

Miao

Juntti

M. J.

Positioning for NLOS propagation: algorithm derivations and Cramer-Rao bounds

IEEE Transactions on Vehicular Technology 2007 56 5 2568 2580

2-s2.0-35448940215

10.1109/TVT.2007.899948

18.

Guo

Y. J.

Anchor global position accuracy enhancement based on data fusion

IEEE Transactions on Vehicular Technology 2009 58 3 1616 1623

2-s2.0-60449096341

10.1109/TVT.2008.928636

19.

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

20.

Venkatraman

Caffery

Jr.

Hybrid TOA/AOA techniques for mobile location in non-line-of-sight environments

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′04)

March 2004

274 278

2-s2.0-4544340503

21.

Montillet

J.-P.

Rabbachin

Cheong

Oppermann

UWB location and tracking for wireless embedded networks

Signal Processing 2006 86 9 2153 2171

2-s2.0-33745743462

10.1016/j.sigpro.2005.07.042

22.

Geng

Pahlavan

Modeling indoor TOA ranging error for body mounted sensors

Proceedings of the IEEE 23rd International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC ′12)

September 2012

Sydney, Australia

682 686

2-s2.0-84871953616

10.1109/PIMRC.2012.6362871

23.

Chen

P. C.

A non-line-of-sight error mitigation algorithm in location

Proceedings of the IEEE Wireless Communications and Networking Conference

1999

316 320

24.

Phatak

M. S.

Recursive method for optimum GPS satellite selection

IEEE Transactions on Aerospace and Electronic Systems 2001 37 2 751 754

2-s2.0-0035300551

10.1109/7.937488

25.

Yang

C.-Y.

Chen

B.-S.

Liao

F.-K.

Mobile location estimation using fuzzy-based IMM and data fusion

IEEE Transactions on Mobile Computing 2010 9 10 1424 1436

2-s2.0-77956041043

10.1109/TMC.2010.105

26.

Kobayashi

Cramér-Rao lower bound for geolocation in non-line-of-sight environment

Proceedings of the IEEE International Conference on Acoustic, Speech, and Signal Processing

May 2002

III/2473 III/2476

2-s2.0-0036296713

27.

Holotyak

Voloshynovskiy

Rolim

Prudyus

Improved solution of Cramer-Rao lower bound for TOA/RSS localization

Proceedings of the 11th International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET ′12)

February 2012

Slavs'ke Lviv Oblast, Ukraine

292 294

2-s2.0-84861364946

28.

Liu

Geometry influence on GDOP in TOA and AOA positioning systems

Proceedings of the 2nd International Conference on Networks Security, Wireless Communications and Trusted Computing (NSWCTC ′10)

April 2010

Wuhan, China

58 61

2-s2.0-77954398860

10.1109/NSWCTC.2010.150

29.

Deng

L.-J.

GDOP performance analysis of cellular location system

Journal of Southwest Jiaotong University 2005 40 2 184 188

2-s2.0-19044384368

30.

C.-H.

V.-W.

Genetic programming for the approximation of GPS GDOP

Proceedings of the International Conference on Machine Learning and Cybernetics (ICMLC ′10)

July 2010

Qingdao, China

2944 2949

2-s2.0-78149321711

10.1109/ICMLC.2010.5580757

31.

Cong

Abidat

A. I.

Tan

Z.-Z.

Analysis and simulation of the GDOP of satellite navigation

Acta Electronica Sinica 2006 34 12 2204 2208

2-s2.0-33847334296