Energy-Efficient Node Selection for Target Tracking in Wireless Sensor Networks

Abstract

Saving energy while preserving accuracy is of paramount importance to target tracking in wireless sensor networks. This paper presents an energy-efficient selection of cooperative nodes. In the proposed method, the target detection probability is estimated by single-node processing based on particle filter. Then, an objective function for collaborative target tracking in wireless sensor networks is constructed according to the information utility and the remaining energy of sensor nodes. With this understanding, a dynamic node selection scheme based on genetic algorithms is proposed, which can optimize the tradeoff between the accuracy of tracking and the energy cost of nodes. Simulations demonstrate its superior performance in estimating the target location and saving sensor nodes energy.

1. Introduction

Target tracking in wireless sensor networks has received more and more attention in recent years [1, 2]. The accuracy of localization and saving energy are always two critical issues because of the limited power and wireless bandwidth of sensor nodes. Dynamic node clustering algorithms [3] usually used for collaborative target tracking in wireless sensor networks are an effective way to solve the previous problems, in which sensor node selection is a crucial step. There are lots of studies concerning this issue [4]. In [5], the authors present the concept of information utility and propose an information-driven approach to select a leader sensor node which performs the target sensing. A generalization of nearest neighborhood method is introduced in [6], which selects only the sensor closest to the predicted position of the target. In [7], the leader sensor is selected by maximizing the mutual information. In [8], the authors use an entropy-based sensor node selection heuristic algorithm to select the suboptimal additional sensor subset. In [9], an unscented Kalman filter framework is established to select optimal subset from a set of sensor nodes in order to maximize the information utility. In [10], sensor selection problem is solved for target tracking using convex optimization followed by a greedy local search. A distributed algorithm can be found in [11], which activates each sensor with a probability according to its neighbor sensors' behaviors. However, all of these works focus on maximizing the accuracy of localization and insufficiently address on the energy of nodes. Also, there are other node selection schemes taking into account the energy cost of nodes. In [12], the authors present a node selection optimization based on genetic algorithm and simulated annealing to minimize the communication energy consumption. A node selection algorithm combining node energy consumption with information utility is proposed in [13]. Nevertheless, the two approaches neglect the influences of the remaining energy of nodes on node selection. Besides, a greedy heuristic method is developed to solve the problem of node selection in order to maximize residual energy of selected nodes [14]. However, this study barely involves the issues concerning collaborative target tracking.

In this paper, we propose a node selection scheme which gives full consideration to both the information utility and the remaining energy of nodes. The former is responsible for the quality of tracking whilst, the latter determines the longevity of sensor nodes. The goal of the proposed scheme is to select the optimal set of sensors in order to achieve a good balance between the accuracy of localization and the energy cost of sensor nodes. We employ a disk model to describe the sensing region of a sensor node. The main contributions of the proposed scheme are summarized as follows. For one thing, each sensor node, respectively, implements the target sensing by computing the detection probability, whereas the optimal set of sensors performs target tracking by integrating partial estimations. For another, the node selection is formalized as an optimization problem and solved by genetic algorithms.

The remainder is organized as follows. We briefly introduce the distributed dynamic system model in Section 2. The node selection scheme for cooperative target tracking in wireless sensor networks is provided in Section 3. The experimental simulations are carried out in Section 4. Section 5 gives conclusions.

2. System Model

Each node in wireless sensor networks separately implements the target tracking based on particle filter [15]. In this paper, the motion model of the target and the sensing model of sensor nodes are denoted by

$$\begin{array}{cc}& {\mathbf{x}}_t=\mathrm{\Phi }{\mathbf{x}}_{t-\mathrm{1}}+\mathrm{\Gamma }{\mathbf{u}}_t,\\ {\mathbf{z}}_t=\arctan \left(\frac{y_t-y_j}{x_t-x_j}\right)+{\mathbf{v}}_t,\end{array}$$

(1)

where the state vector ${\mathbf{x}}_t$ = $(x_t,y_t,v_t^x,v_t^y{)}^T$ , ( $x_t$ , $y_t$ ), and ( $v_t^x$ , $v_t^y$ ), respectively, represent the location coordinates and velocities, and

$$\begin{array}{cc}& \mathrm{\Phi }=\left[\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \mathrm{\Delta }t& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{\Delta }t\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right],\hspace{1em}\hspace{1em}\mathrm{\Gamma }=\left[\begin{array}{cc}\frac{\mathrm{1}}{\mathrm{2}}\mathrm{\Delta }{t}^{\mathrm{2}}& \mathrm{0}\\ \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}\mathrm{\Delta }{t}^{\mathrm{2}}\\ \mathrm{\Delta }t& \mathrm{0}\\ \mathrm{0}& \mathrm{\Delta }t\end{array}\right].\end{array}$$

(2)

In addition, ${\mathbf{z}}_t$ is the measurement, ( $x_i$ , $y_j$ ) are the coordinates of sensor node j, ${\mathbf{u}}_t$ and ${\mathbf{v}}_t$ are zero mean Gaussian white noises, and the variances of them are ${\sigma }_u^{\mathrm{2}}=\left[\begin{array}{cc}{\sigma }_x^{\mathrm{2}}& \mathrm{0}\\ \mathrm{0}& {\sigma }_y^{\mathrm{2}}\end{array}\right]$ and ${\sigma }_v^{\mathrm{2}}$ .

3. Proposed Node Selection Scheme

For a given sensor node j, its state vector at time t is labeled as ${\mathbf{x}}_t^j$ . Let $\{{\mathbf{x}}_t^{j(i)},{\omega }_t^{j(i)}{\}}_{i=\mathrm{1}}^N$ be a particle set, where ${\mathbf{x}}_t^{j(i)}$ is a sample of ${\mathbf{x}}_t^j$ with weight ${\omega }_t^{j(i)}$ , N is the number of particles. The probability that the sensor nodej can detect the target is

$$\begin{array}{cc}& P_j={\sum }_{i=\mathrm{1}}^N{\omega }_t^{j\left(i\right)}\delta \left({\mathbf{x}}_t^{j\left(i\right)},D_j\right),\end{array}$$

(3)

where $D_j$ denotes the sensing region of j, and $\delta \hspace{0.17em}({\mathbf{x}}_t^{j(i)},D_j)$ is 1 if ${\mathbf{x}}_t^{j(i)}$ belongs to $D_j$ and 0 otherwise. A small number of sensor nodes providing the most informative measurements should be chosen as the candidate nodes at each time step. The operation includes two steps. Firstly, sensor nodes which can detect the target are awoken, and the other nodes remain in the sleeping mode to save energy. Then, only if the probability of target detection, $P_j$ , exceeds a predefined threshold ε, the node j will become a candidate to participate in the target tracking process. Thus, the set of candidate nodes is denoted as

$$\begin{array}{cc}& S_t=\{j\mid P_j>\epsilon ,\text{dis}(j,{\widehat{\mathit{x}}}_t)<r_s\},\end{array}$$

(4)

where ${\widehat{\mathit{x}}}_t$ is the estimated target state at time t, $\text{dis}(j,{\widehat{\mathit{x}}}_t)$ is the distance between the node j and ${\widehat{\mathit{x}}}_t$ , and $r_s$ is the sensing radius.

For cooperative target tracking in wireless sensor networks, the key problem is to form a dynamic cluster and properly select the cluster head (CH) and the cluster members during the tracking process. CH consumes more energy than the cluster members because of the heavier processing and communication cost. At the beginning, the sensor that detects the target with the highest probability is selected as CH. Assume that the cluster head at time $t-1$ is ${\text{CH}}_{t-\mathrm{1}}$ . Considering the substantial energy cost and the nonuniformity of the remaining energy of nodes, ${\text{CH}}_t$ is selected referring to the following rule. If ${\text{CH}}_{t-\mathrm{1}}$ is still a candidate node at time t, it will continue the tracking and node selection process, otherwise, it will hand off the tracking information to another candidate node, that is, the new cluster head ${\text{CH}}_t$ , which meets the demands of having both the greatest target detection probability and remaining energy. So, the cluster head selection at time t can be expressed as

$$\begin{array}{l}\text{C}{\text{H}}_t\\ =\{\begin{array}{ll}{\text{CH}}_{t-\mathrm{1}},\hfill & {\text{CH}}_{t-\mathrm{1}}\in S_t\hfill \\ \left\{j\mid \text{dis}\left(j,{\text{CH}}_{t-\mathrm{1}}\right)<r_c,\hspace{0.17em}\hspace{0.17em}\arg \hspace{0.17em}\max \left(P_j,E_j\right)\right\},\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\text{otherwise},\hfill \end{array}\end{array}$$

(5)

where $E_j$ is the remaining energy of node j, and $r_c$ is the communication radius.

To implement optimal selection of the cluster members, we first define the cost and utility functions. The energy cost of each sensor node is usually determined by sensing, processing, and communication cost which are denoted by $e_s$ , $e_p$ , and $e_c$ , respectively. Moreover, CH consumes extra energy because of selecting cluster members and controlling the tracking. It should be noticed that two elements, the remaining energy and the energy cost of the set of sensors, have a dramatic impact on sensor node lifetime. Thus, we select the best subset of cluster members by using two strategies: (1) minimizing the energy costs of nodes in the case of the desirable accuracy of localization; (2) maximizing the remaining energy of selected nodes so that energy is consumed in a uniform way among sensors during target tracking. Owing to the previous factors, the cost function of $S_t$ is defined as the ratio between the total energy cost and the remaining energy of the set of sensor nodes as

$$\begin{array}{cc}& {\phi }_{\text{cost}}\left(S_t\right)=\frac{{\sum }_{j\in S_t}^{}[e_s\left(j\right)+e_p\left(j\right)+e_c\left(j\right)]}{{\sum }_{j\in S_t}^{}[E_j-e_s\left(j\right)-e_p\left(j\right)-e_c\left(j\right)]}.\end{array}$$

(6)

As is well known, the posterior density at time t according to particle filter can be approximated as

$$\begin{array}{cc}& p\left({\mathit{x}}_t^j\mid {\mathit{z}}_t^j\right)\approx {\sum }_{i=\mathrm{1}}^N{\omega }_t^{j\left(i\right)}\delta ({\mathit{x}}_t^j-{\mathit{x}}_t^{j\left(i\right)}).\end{array}$$

(7)

Then, the utility function can be defined as the negative entropy and used to quantify the contribution to localization accuracy made by $S_t$ , that is,

$$\begin{array}{cc}& {\phi }_{\text{utility}}\left(S_t\right)=\int p\left({\mathit{x}}_t^j\mid {\mathit{z}}_t^j\right)\log p\left({\mathit{x}}_t^j\mid {\mathit{z}}_t^j\right)d{\mathit{x}}_t^j.\end{array}$$

(8)

Obviously, the greater the utility function is, the more certain node measurements are. Substituting (7) into (8), we have

$$\begin{array}{cc}& {\phi }_{\text{utility}}\left(S_t\right)\approx {\sum }_{i=i}^N{\omega }_t^{j\left(i\right)}\log {\omega }_t^{j\left(i\right)}.\end{array}$$

(9)

As discussed earlier, our goal is to select the optimal set of sensor nodes from candidate nodes to obtain a precise estimation of the target location while minimizing the energy cost. Combining the utility and cost functions, we establish the objective function as below:

$$\begin{array}{cc}& f\left({\phi }_{\text{utility}},{\phi }_{\text{cost}}\right)=\alpha {\phi }_{\text{utility}}\left(S_t\right)-\left(\mathrm{1}-\alpha \right){\phi }_{\text{cost}}\left(S_t\right),\end{array}$$

(10)

where α is the relative weight of the utility and cost functions, which decides which of two factors is determinant when choosing sensor nodes. Apparently, the objective function increases with the increase of the utility function; however, it decreases with the increase of the cost function. Under this circumstance, cluster members selection can be mapped into a maximum optimization problem.

When the density of sensor nodes is high, the size of $S_t$ is big in general. As a result, we need to adopt an effective method to select proper sensor nodes form $S_t$ as cluster member. Assume that $S_t$ includes n candidate nodes. $S_t$ can be represented by a set of binary codes as follows:

$$\begin{array}{cc}& \left(c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_j,\dots ,c_n\right),\hspace{1em}{c}_j\in \left\{\mathrm{0,1}\right\},\end{array}$$

(11)

where $c_j$ corresponds to the state of the jth candidate node, and the digit 1 indicates the candidate node that will be selected or vice versa. Then, we choose the objective function described in (10) as the fitness function and apply genetic algorithms (GAs) to select sensor nodes and form the optimal set of sensors

$$\begin{array}{cc}& C_t=\{c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_j,\dots ,c_n\mid \arg \hspace{0.17em}\max f({\phi }_{\text{utility}},{\phi }_{\text{cost}})\}.\end{array}$$

(12)

From the foregoing, the procedure of collaborative target tracking at time t is summarized as follows.

Step 1.

${\text{CH}}_{t-\mathrm{1}}$ estimates the target detection probability using (3) and determines ${\text{CH}}_t$ by (5).

Step 2.

${\text{CH}}_{t-\mathrm{1}}$ relays the state estimation and the information of candidate nodes to ${\text{CH}}_t$ .

Step 3.

${\text{CH}}_t$ selects the cluster members using (12) to participate in the tracking process.

Step 4.

${\text{CH}}_t$ approximates the estimated target state as the average of all partial estimations. Consider

$$\begin{array}{cc}& {\widehat{\mathbf{x}}}_t=\frac{\mathrm{1}}{M}{\sum }_{j=\mathrm{1}}^M{\widehat{\mathbf{x}}}_t^j,\end{array}$$

(13)

where M is the number of the selected sensor nodes, and ${\widehat{\mathbf{x}}}_t^j$ indicates the estimated target state of sensor node j, which is expressed as

$$\begin{array}{cc}& {\widehat{\mathbf{x}}}_t^j={\sum }_{i=\mathrm{1}}^N{\mathbf{x}}_t^{j\left(i\right)}{\omega }_t^{j\left(i\right)}.\end{array}$$

(14)

4. Experimental Results

We built up a simulation platform by Matlab to evaluate the proposed node selection scheme for target tracking. The sensor network includes 300 nodes in a two-dimensional plane, which are randomly deployed within 200 m × 200 m area. A target crosses the area from the start point (10, 20) with the initial speed (2, 1.5). The simulation includes 20 steps, and the time step $\mathrm{\Delta }t=4$ . The detailed parameters of simulation platform are as follows: ${\sigma }_x={\sigma }_y={\sigma }_n=0.05$ , $N=200$ , $r_s=15$ , $r_c=40$ , $\epsilon =0.6$ , $e_s=e_p=1$ , $e_c=3$ , and the initial energy of each node $E_{\mathrm{0}}=300$ . As nodes are deployed at a low level of density a limited number of nodes can detect the target at each time step. In view of the fact, we choose the size of the population used in GA as 20. Besides, we set the rate of crossover as 0.8, the rate of mutation as 0.2, and the number of generations as 50.

Figure 1 shows a simulation example from $t=1$ to $t=20$ , which illustrates the estimated trajectory versus the real trajectory and the node selection process for a random sensor placement. CH and cluster members are continually readjusted with the movement of the target in order to fulfill the collaborative tracking. The “*” in Figure 1 denotes the real trajectory of the target, which is generated based on the motion model. The “+” denotes the estimated trajectory, which is calculated according to (13). The detailed information, such as the target location, CH, and the number of its corresponding cluster members can be found in Table 1. From Figure 1 and Table 1, we can see that the estimated error is desirable. Furthermore, the number of the selected sensor nodes for target tracking is four at most, which implies that the size of the optimal set is small.

Table 1

Target tracking information.

t	$(x_t,y_t)$	( ${\widehat{x}}_t,{\widehat{y}}_t$ )	CH	M
1	(18, 26)	(17.6217, 25.6456)	(17, 28)	2
2	(27, 33)	(26.0577, 31.9914)	(17, 28)	3
3	(36, 39)	(35.6505, 38.8437)	(27, 29)	1
4	(44, 45)	(43.8646, 45.5720)	(34, 46)	3
5	(53, 52)	(52.1104, 51.5526)	(48, 50)	4
6	(61, 59)	(60.3184, 58.3473)	(48, 50)	2
7	(68, 66)	(68.1944, 64.9387)	(62, 67)	3
8	(76, 73)	(75.4908, 71.5971)	(62, 67)	3
9	(84, 80)	(83.2363, 78.0939)	(80, 84)	1
10	(92, 87)	(92.9009, 86.4478)	(80, 84)	3
11	(100, 94)	(101.3065, 94.1722)	(90, 88)	4
12	(108, 101)	(108.3575, 100.9523)	(96, 97)	3
13	(117, 108)	(117.2726, 107.6548)	(110, 111)	4
14	(124, 114)	(125.1523, 114.4936)	(121, 102)	3
15	(131, 122)	(132.5662, 121.8624)	(132, 115)	3
16	(138, 129)	(138.5787, 129.0603)	(141, 125)	2
17	(145, 136)	(145.5991, 136.2938)	(141, 125)	2
18	(152, 142)	(152.8151, 143.6729)	(150, 143)	2
19	(159, 150)	(159.5356, 149.1288)	(150, 143)	1
20	(166, 156)	(165.9980, 156.2919)	(164, 158)	2

Figure 1

Target trajectories and node selection of the proposed method under $\alpha =0.8$ (“•” denotes cluster member, and “■” denotes CH).

To illustrate node selection for target tracking, we take the fifth time step for an example and observe it further. Simulation shows that the target is detected by eight sensor nodes at this time step. For each node, its location, target detection probability, and the remaining energy are listed in Table 2. Only the sensor node whose corresponding probability exceeds 0.6 becomes a candidate. From Table 2, we can find that six nodes satisfy the requirement, which implies that the set of candidate nodes $S_{\mathrm{5}}$ is $\{2,3,4,5,6,8\}$ . As pointed out previously, the optimal set of sensors $C_5$ can be obtained according to GA. It should be noted that the cost function depends not only on the energy cost but also on the remaining energy. The sensor nodes with less remaining energy lead to a relatively minor fitness, which cannot meet the demand of node selection. Therefore, $C_{\mathrm{5}}$ is finally designated as $\{2,4,5,6\}$ , which only includes four sensor nodes as depicted in Table 1. It means that node 3 and node 8 can detect the target with a high probability, but they fail to be cluster members because of the less remaining energy.

Table 2

Information of sensor nodes.

Node lable	$(x_j,y_j)$	$P_j$	Remaining energy
1	(38, 58)	0.2593	271
2	(53, 46)	1	173
3	(39, 47)	0.8910	58
4	(48, 44)	1	184
5	(39, 59)	0.7482	245
6	(48, 50)	1	205
7	(46, 36)	0.0070	227
8	(54, 37)	0.6739	133

In order to validate the superiority of the proposed scheme, we defined three different schemes similar to [16], described as follows, to select sensor nodes.

• (1)

A scheme. This is a naive approach for node selection which chooses only the node nearest to the estimated position of the target.

(2)

B scheme. This scheme selects all the nodes which can detect the target as cluster members.

(3)

C scheme. In this scheme, all nodes whose target detection probability exceeds ε are enabled to participate in the target tracking.

The accuracy of localization and energy efficiency of node selection are evaluated, respectively, using the root mean squared error (RMSE) and the energy cost. We compare the proposed scheme with these schemes, and the comparison is on the basis of results averaged over 50 independent runs, as described in Table 3. As we can see, comparing B scheme and C scheme with the proposed scheme, the difference of the tracking error of each scheme slightly decreases as the number of deployed sensor nodes increases from 300 to 500. On the contrary, the difference of the energy cost stands out more clearly, and the incremental energy costs of B scheme and C scheme greatly outnumber that of the proposed scheme. Besides, the tracking error of A scheme is far greater than those of B scheme, C scheme, and the proposed scheme. Note that A scheme is fragile due to the premature collapse of excessively used nodes. Moreover, the tracking error of C scheme approximates that of B scheme, and both of them surmount the proposed scheme. Conversely, the energy costs of the two schemes greatly exceed our scheme, and the difference increases as the density of sensor nodes increases.

Table 3

Performance comparison of four schemes.

No. of nodes	Performance	Proposed scheme			A scheme	B scheme	C scheme
		α = 0.8	α = 0.6	α = 0.4
300	RMSE	1.1416	1.3431	1.5621	3.4172	0.9377	0.9854
	Energy cost	1865	1780	1608	631	3614	2077
500	RMSE	0.9738	1.1843	1.3467	3.0953	0.8059	0.8273
	Energy cost	1938	1835	1673	647	4103	2322

From the pervious comparison, it is obvious that the proposed scheme and C scheme are more feasible than the two others because of the balanced performance. Next, we further evaluate the performance differences by analyzing the two schemes. The target trajectories and node selection of C scheme are shown in Figure 2, which are got under the same simulation conditions as Figure 1. On comparison, there exist some apparent differences between them in CH and the number of cluster members. From Table 3, the proposed scheme reduces the energy cost varying from 10% to 28% in contrast with C scheme; meanwhile, the tracking error is a little higher. Therefore, it can be concluded that the proposed scheme performs better.

Figure 2

Target trajectories and node selection of C scheme.

In addition, for the proposed scheme, the influence of parameter α and the number of deployed nodes on node selection is also analyzed through choosing different values. There are two things we can learn from simulation results. Firstly, the energy cost tends to increase, but the tracking error decreases as α becomes greater. The main reason for this is that the information utility is the primary consideration in node selection when α is bigger, and the tracking accuracy is improved at the expenses of energy cost. Secondly, the performance of the proposed scheme will become prominent along with the increase of the node density.

5. Conclusions

Aiming to the conflict between the accuracy of localization and the energy cost for collaborative target tracking in wireless sensor networks, a new node selection scheme is presented within the framework of particle filter. The primary goal is to balance the tradeoff between the accuracy of target localization and the energy cost of sensor nodes. We formalize the problem of node selection as an optimization problem and solve it through GA. We evaluate the proposed scheme by comparing it with several methods and examining the influence of different parameters on the process of node selection. The experimental results show that the proposed scheme is efficient to achieve energy saving and at the same time preserve a tolerable tracking error.