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{array}{cc}& \mathrm{\Delta }X=\text{GDOP}·\mathrm{\Delta }\rho ,\end{array}$$

(1)

where $\mathrm{\Delta }\rho$ and $\mathrm{\Delta }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 $\theta ={({\theta }_{\mathrm{1}},{\theta }_{\mathrm{2}},\dots \hspace{0.17em}{\theta }_L)}^T$ and L indicates the number of unknown parameters. The FIM can be represented as

$$\begin{array}{cc}& {\mathrm{\hspace{0.17em}\hspace{0.17em}}J}_{\theta }=E_{\theta }\left\{\left(\frac{\partial \log }{\partial \theta }f\left(\mathrm{\Lambda }\hspace{0.17em}|\hspace{0.17em}\theta \right)\right){\left(\frac{\partial \log }{\partial \theta }f\left(\mathrm{\Lambda }\hspace{0.17em}|\hspace{0.17em}\theta \right)\right)}^T\right\}.\end{array}$$

(2)

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

$$\begin{array}{l}f\left(\mathrm{\Lambda }\hspace{0.17em}|\hspace{0.17em}\theta \right)\\ \hspace{1em}=\frac{\mathrm{1}}{{\left(\mathrm{2}\pi \right)}^{p/\mathrm{2}}{\left|Q\right|}^{\mathrm{1}/\mathrm{2}}}\exp \left(-\frac{{\left(\mathrm{\Lambda }-\mu \left(\theta \right)\right)}^T{Q}^{-\mathrm{1}}\left(\mathrm{\Lambda }-\mu \left(\theta \right)\right)}{\mathrm{2}}\right),\end{array}$$

(3)

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

$$\begin{array}{cc}& J_{\theta }={\left(\frac{\partial \mu \left(\theta \right)}{\partial {\theta }^T}\right)}^T{Q}^{-\mathrm{1}}\left(\frac{\partial \mu \left(\theta \right)}{\partial {\theta }^T}\right).\end{array}$$

(4)

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

$$\begin{array}{cc}& J_{\theta }^{-1}={\left(H^T{Q}^{-1}H\right)}^{-\mathrm{1}}.\end{array}$$

(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)\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,N;N\ge 3)$ , the mobile device's coordinates are $\mathrm{\Psi }={(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{array}{cc}& r_i=\sqrt{{\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}}+{\epsilon }_i,\end{array}$$

(6)

where ${\epsilon }_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{array}{cc}& H=\frac{\partial \mu \left(\theta \right)}{\partial {\theta }^T}=\left[\begin{array}{ccc}\frac{x-x_{\mathrm{1}}}{r_{\mathrm{1}}}& \frac{y-y_{\mathrm{1}}}{r_{\mathrm{1}}}& \mathrm{1}\\ \frac{x-x_{\mathrm{2}}}{r_{\mathrm{2}}}& \frac{y-y_{\mathrm{2}}}{r_{\mathrm{2}}}& \mathrm{1}\\ \begin{array}{c}⋮\\ \frac{x-x_N}{r_N}\end{array}& \begin{array}{c}⋮\\ \frac{y-y_N}{r_N}\end{array}& \begin{array}{c}⋮\\ \mathrm{1}\end{array}\end{array}\right].\end{array}$$

(7)

The covariance matrix Q can be represented as

$$\begin{array}{cc}& Q={\sigma }_R^{\mathrm{2}}\left[\begin{array}{ccc}\mathrm{1}& \mathrm{0}& \begin{array}{cc}\mathrm{0}& \mathrm{0}\end{array}\\ \mathrm{0}& \mathrm{1}& \begin{array}{cc}\mathrm{0}& \mathrm{0}\end{array}\\ \begin{array}{c}\mathrm{0}\\ \mathrm{0}\end{array}& \begin{array}{c}\mathrm{0}\\ \mathrm{0}\end{array}& \begin{array}{c}\begin{array}{cc}\mathrm{1}& \mathrm{0}\end{array}\\ \begin{array}{cc}\mathrm{0}& \mathrm{1}\end{array}\end{array}\end{array}\right].\end{array}$$

(8)

Here, ${\sigma }_R$ represents the root mean square measurement error. It will keep consistent to all nodes. Submitting matrix H and matrix Q into (5), ${J_{\theta }}^{-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{array}{cc}& \text{GDOP}=\sqrt{\frac{E\left(\mathrm{\Delta }{x}^{\mathrm{2}}\right)+E\left(\mathrm{\Delta }{y}^{\mathrm{2}}\right)}{E\left(\mathrm{\Delta }{R}^{\mathrm{2}}\right)}}=\frac{\sqrt{{\sigma }_x^{\mathrm{2}}+{\sigma }_y^{\mathrm{2}}}}{{\sigma }_R}.\end{array}$$

(9)

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

$$\begin{array}{cc}& \text{GDOP}=\sqrt{\text{trace}{(H^T·H)}^{-\mathrm{1}}}.\end{array}$$

(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-\mathrm{1}}^i$ ; the relationship between the two matrixes is

$$\begin{array}{cc}& H_m^T{H}_m={H_{m-\mathrm{1}}^i}^T{H}_{m-\mathrm{1}}^i+h_i^T{h}_i.\end{array}$$

(11)

Assume that $h_i$ is the observation matrix of the ith node and ${{(H}_m^T{H}_m)}^{-\mathrm{1}}$ equals $G_m$ . According to the Sherman-Morrison formulation [31],

$$\begin{array}{l}{\mathrm{\hspace{0.17em}\hspace{0.17em}}G}_m^i={\left({H_{m-\mathrm{1}}^i}^T{H}_{m-\mathrm{1}}^i\right)}^{-\mathrm{1}}={\left(H_m^T{H}_m-h_i^T{h}_i\right)}^{-\mathrm{1}}\\ \hspace{1em}\hspace{1em}=G_m+G_m{h}_i^T{\left(\mathrm{1}-h_i{G}_m{h}_i^T\right)}^{-\mathrm{1}}{h}_i{G}_m,\end{array}$$

(12)

where $(1-h_i{G}_m{h}_i^T)$ is a scalar which is recorded as ${\lambda }_{mi}$ . Squaring the GDOP expression we can obtain the following:

$$\begin{array}{l}{{\text{GDOP}}_{m-\mathrm{1}}^i}^{\mathrm{2}}=\text{trace}{G}_{m-\mathrm{1}}^i\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\text{GDOP}}_m^2+\text{trace}\left(\frac{G_m{h}_i^T{h}_i{G}_m}{{\lambda }_{mi}}\right).\end{array}$$

(13)

The equation above can also be expressed as

$$\begin{array}{cc}& {{\text{GDOP}}_{m-\mathrm{1}}^i}^{\mathrm{2}}-{\text{GDOP}}_m^{\mathrm{2}}=\text{trace}\left(\frac{G_m{h}_i^T{h}_i{G}_m}{{\lambda }_{mi}}\right).\end{array}$$

(14)

Let $\text{trace}\hspace{0.17em}\hspace{0.17em}(G_m{h}_i^T{h}_i{G}_m/{\lambda }_{mi})=\mathrm{\Delta }{G}_i$ ; $\mathrm{\Delta }{G}_i$ represents the variation by removing the ith nodes. A bigger $\mathrm{\Delta }{G}_i$ indicates a larger contribution to ${\text{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
	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 $\phi =\mathrm{1.5}$ . There is practical significance for the GANS algorithm only when the ${\text{GDOP}}_m$ is above the threshold. Afterwards, the $\mathrm{\Delta }{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 $\mathrm{\phi }=\mathit{1.5}$ ;

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

   Else go to Step 5;

Step  3. Calculate and sort the $\mathrm{\Delta }{\mathrm{G}}_i$ of each node;

Step  4. Compare the $\mathrm{\Delta }{\mathrm{G}}_i$ with threshold $\delta =\mathit{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  $\mathrm{\Delta }{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 $\mathrm{\Delta }{G}_i$ will not produce a big influence on the positioning accuracy. The anchor nodes whose $\mathrm{\Delta }{G}_i$ is smaller than the threshold δ will be removed. If all of the $\mathrm{\Delta }{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 $\mathrm{\Delta }{G}_i$ of each node is calculated at fixed time interval. According to the $\mathrm{\Delta }{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 ${\text{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 $\phi =1.5$ . The GANS algorithm will be used only when the ${\text{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 ${\text{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 $\mathrm{\Delta }{G}_i$ and the abrupt change of GDOP value will be deeply researched.