An energy-balanced multi-sensor scheduling scheme for collaborative target tracking in wireless sensor networks

Abstract

Improving tracking quality and extending network lifespan are two main objects for target tracking, which are usually contradictory due to limited energy of sensor nodes in wireless sensor networks. This article incorporates this contradiction into a problem of multi-objective optimization in tracking networks where multiple sensor nodes are scheduled for collaborative target tracking by adopting the unscented Kalman filter algorithm. We propose an effective scheme to extend the lifespan of wireless sensor networks while guaranteeing preset tracking quality. More specifically, with regard to practical circumstances, we perform analysis on the target detection probability, as well as residual energy of sensor nodes, when selecting a suitable set of candidate sensor nodes. Then, we put forward a novel energy-balanced sensor nodes scheduling algorithm, Greedy Balance Replace Heuristic Algorithm, to select a near-optimal task sensor set from the candidate sensor node set to balance tracking quality and network lifetime. In addition, we also design an efficient multi-sensor node collaborative method to track a single target and to timely report its state to the remote end. From simulation results, it is demonstrated that the proposed node scheduling scheme can not only maintain the preset tracking accuracy but also extend network lifespan with a low computation complexity.

Introduction

Wireless sensor networks (WSNs) have long been recognized as an important information-gathering approach for many applications, such as environmental monitoring, security surveillance, and industry control.^1–4 WSNs are ordinarily composed of a large number of tiny low-cost, energy-limited, and sensing range-limited sensor nodes. Typically, it is necessary to charge these nodes periodically since they are battery powered. Therefore, network lifetime is considered as an important issue in WSNs. ⁵

Tracking a moving target in a sensing field is one of the major surveillance applications of WSNs, which has received much attention in recent years. In target tracking, some sensor nodes are informed to wake up when a moving target under surveillance is discovered, then they detect the moving target and report its state. In terms of the existence of interferences in sensor readings and restrictions on power supply and communication competence, it is a challenge to develop an energy-efficient and accurate target-tracking technique in WSNs. In other words, improving tracking quality and extending network lifetime are two conflicting requirements. In practical circumstances, with limited battery power, not all sensor nodes contribute equally for tracking target. If only a selected sensor node set tracks the target, plenty of energy would be substantially saved. However, the decrease in task nodes consequently results in the decline of tracking quality. Thus, how to select appropriate task nodes at each timestep is of critical importance both for extending network lifespan and guaranteeing tracking quality.

In previous work, Xiao et al. ⁶ used a single sensor node to track a moving target. Bhuiyan et al. ⁷ partitioned the surveillance field into many non-overlapping local areas called “face.” When a target moves across a face, its moving tracking will be computed and predicted by a neighbor sensor node. Different from the single sensor node tracking system, multiple sensor node collaborative network employs a local fusion center to collect data from nearby nodes and to conduct estimation on target state.^8,9 Obviously, the robustness of tracking accuracy will be improved in this network but with excessive energy consumption. In massive literatures,^10–12 a lot of attempts are given to resolve this contradiction between tracking accuracy and network lifespan. For example, Xiao et al. ⁶ proposed an energy-efficient adaptive sensor scheduling approach which jointly selects task sensor nodes and determines their associated sampling intervals according to the predicted tracking accuracy and energy cost.

Including above works, many works^13–16 have addressed energy-efficiency issues. In recent years, some literatures have proposed a number of energy-balanced multi-node scheduling schemes. By these schemes, the selected nodes can make residual energy of the network distribute evenly, which avoids the premature death of some nodes and thus extends network lifespan. Liu et al. ¹⁷ proposed an energy-balanced scheduling scheme which minimizes the weighted sum of energy consumption and energy difference among cluster nodes. Nevertheless, this scheduling algorithm still merely considers the energy balance on some task nodes rather than the remaining energy of each task node in tracking network. Hu et al. ¹⁸ proposed an improved energy-balanced model in their work. They use the energy-balanced criterion to select the cluster head (CH) and the cluster member (CM) to extend network lifespan. However, this work reckons without the ratio of energy consumption and current residue energy when selecting the CH. Additionally, the computation complexity of the proposed active nodes selection algorithms in Hu et al. ¹⁸ is a little high.

In this article, we put forward an energy-balanced multi-sensor scheduling scheme for collaborative target tracking in WSNs. Specifically, considering constraints of WSNs of less energy, insufficient computational capability, and high measurement error rates, we use the following mechanisms to efficiently carry out tracking tasks: (1) a decentralized unscented Kalman Filter (UKF) algorithm for fusing measurement results at the CH; (2) an efficient mechanism for selection of task sensor nodes that balances network lifespan and tracking quality. Unlike the work by Hu et al., ¹⁸ which chooses task cluster nodes and the CH successively, we choose the task cluster nodes and the CH simultaneously; (3) a mechanism that adopts a low computational burden evaluation function method to solve the multi-objective optimization problem; and (4) a mechanism that enables the remote end to timely acquire the state of the target. Figure 1 presents the tracking mechanisms briefly.

Figure 1.

Schematic illustration of the proposed tracking mechanisms.

This article focuses on extending network lifespan by dynamically activating a minimal number of task sensor nodes while guaranteeing the pre-defined tracking accuracy. Its main contributions are as follows:

• Taking into account the probability of target detected by sensor nodes when selecting suitable candidate nodes due to the inaccuracy of the predicted next target position.

• Adopting the ratio of energy consumption and current residue energy as one of the criteria when selecting the CH. This effectively avoids premature death of the chosen CH.

• Putting forward an effective sensor node scheduling algorithm with low computation complexity, Greedy Balance Replace Heuristic Algorithm (GBRHA), to select a suitable set of task nodes.

• Designing an efficient multiple sensor node collaborative method to track target and to timely report its state.

The rest of this article is structured as follows. In section “Problem formulation and system models,” we formulate the tracking problem and discuss main system models. Section “UKF algorithm for WSN target tracking” introduces UKF algorithm. Section “Energy-balance criterion” briefly presents the definition of energy-balance criterion. The proposed scheme of energy-balanced multiple sensor node collaborative scheduling is detailed in section “Multiple sensor node collaborative scheduling method.” Section “Greedy balance replace heuristic algorithm” describes the proposed GBRHA. The performances of the proposed methods are investigated and evaluated in section “Simulation result and evaluation.” Finally, section “Conclusion and future work” gives some conclusions to this article.

Problem formulation and system models

Problem formulation and tracking overview

As shown in Figure 2, a number of sensor nodes randomly and unevenly locate in a local area. A given surveillance area R is deployed with N cheap and low-power sensor nodes $S=\{s_1,s_2,\dots ,s_N\}$ . Each of the sensor nodes is equipped with an ultrasonic distance sensor, as well as a low-cost passive infrared (PIR) sensor. In order that all sensor nodes that sense the same target can communicate with each other, their communication radii are set twice of their sensing radii. Moreover, some special sink nodes are placed in fixed positions due to the limited communication radius and remaining energy of ordinary sensor nodes. They act as the base stations to collect the current target state sent by the CH, and then timely report to the remote headquarter. Thus, we assume that the sink nodes are all equipped with unlimited power and have a communication range which is far greater than that of ordinary nodes. The positions and the number of the sink nodes should be set according to the sink node distribution, the shape and size of the monitoring region, and the communication radius of ordinary node, in order that the communication range of each sensor node places at least one sink node. Meanwhile, the locations of all sensor nodes and sink nodes are known by each other after the initialization of network. Location information can be obtained by on-board GPS receiver. Without loss of generality, the target and all sensor nodes are assumed to locate in a two-dimensional (2D) area in this article. Thus, we formulate the target-tracking problem with a 2D model.

Figure 2.

Target-tracking scene in WSN.

All sensor nodes are initially set in sleep mode. When a target moves along a curve path in the surveillance area, only some of sensor nodes along this path will be woken up. Then, they measure the distances between target and themselves, and report the measurements to the CH which serves as the local fusion center. In general situations, to ensure the preset tracking accuracy and to save energy, only a few sensor nodes need to be waken up. When the CH receives reports from other task sensor nodes, it will fuse these data with its own data to obtain a better estimate of target state and then submit it to the remote end via a sink node. Table 1 summarizes some key symbols and their notations.

Table 1.

Key symbols and notations.

Symbol	Notation	Symbol	Notation	Symbol	Notation
$\mathbf{x}$	Target state vector	$z_i$	Measurement of $s_i$	$\mathbf{o}(i)$	Position vector of $s_i$
$\mathbf{c}$	Position vector of target	$\mathbf{w}$	Process noise vector	∇	Sampling time interval
$\mathbf{Q}$	Covariance matrix of $\mathbf{w}$	ℑ	Target	r	Detection radius
$v_i$	Observation noise of $s_i$	$d(s_i,\Im )$	Distance between $s_i$ and T	$r_u$	Uncertainty distance
${\mathrm{\Omega }}_k$	Task node set	$L_k$	Candidate cluster node set	${\mathrm{\Gamma }}_k$	Candidate node set
$h_i$	Measurement model of $s_i$	$\mathbf{z}$	Measurement vector	$\mathbf{v}$	Observation noise vector
${\Lambda }_L$	Number of $L_k$	${\mathrm{\Delta }}_k$	Number of ${\mathrm{\Gamma }}_k$	$N_{\min }$	Least task sensor number
$N_k$	Number of ${\mathrm{\Omega }}_k$	$E_{\mathrm{sp}}$	Sensing and processing cost	$\rho (s_i)$	Probability of T sensed by $s_i$
$E_{\mathrm{con}}(\mathrm{ch})$	Total energy cost of CH	$E_r$	Receiving cost	$E_{\mathrm{con}}(i)$	Total energy cost of CM $s_i$
$E_t$	Transmission cost	$E_{\mathrm{total}}$	Total energy cost of cluster	$\mathbf{R}$	Covariance matrix of $\mathbf{v}$
${\mathbf{P}}^{\mathrm{xx}}$	Error covariance of state	${\mathbf{P}}^{\mathrm{xz}}$	Cross covariance matrix	${\mathbf{P}}^{\mathrm{zz}}$	Innovation covariance matrix
$\stackrel{\wedge }{\mathbf{x}}$	Predicted $\mathbf{x}$	$\hat{\mathbf{P}}$	Predicted covariance matrix	$T_{\mathrm{NL}}$	Lifespan of network
$E_{\mathrm{rem}}(i)$	Remaining energy of $s_i$	${\mathrm{\Phi }}_0$	Preset threshold of $\mathrm{\Phi }$	$e_0$	Lowest work energy of node
$B_e$	Energy-balance metric	$E_{\mathrm{avg}}$	Average remaining energy	$\eta$	Residue energy ratio
$\mathbf{f}$	Solution vector of equation (29)	$\hslash$	Evaluation function	$\mathrm{\Phi }$	Trace of covariance matrix

Target motion and detection model

In this article, we consider a single target-tracking problem. A four-dimensional vector, $\mathbf{x}(k)=[x(k),v_x(k),y(k),v_y(k){]}^T$ , denotes the state of target at timestep k, which includes the position vector $\mathbf{c}(k)=[x(k),y(k){]}^T$ and the velocity vector $\mathbf{j}(k)=[v_x(k),v_y(k){]}^T$ . $\mathbf{o}(i)=[s_x(i),s_y(i){]}^T$ is the position of sensor nodes $s_i$ . In terms of the target motion, we use a simple linear model to represent the moving target with the discrete time dynamic state equation. More complex models require a priori knowledge, often unavailable in most situations, hence it is not considered in this article

$$x(k)=f(x(k-1))+w(k)=Ax(k-1)+w(k)$$ (1)

where the process noise $\mathbf{w}(k)$ is the zero-mean white Gaussian random vector with covariance matrix $\mathbf{Q}$ , and $\mathbf{A}$ is the state transition matrix

$$Q=q\left[\begin{array}{cccc}{\nabla }^3/3& {\nabla }^2/2& 0& 0\\ {\nabla }^2/2& \nabla & 0& 0\\ 0& 0& {\nabla }^3/3& {\nabla }^2/2\\ 0& 0& {\nabla }^2/2& \nabla \end{array}\right]$$ (2)

$$\mathbf{A}=\left[\begin{array}{cccc}1\hfill & \nabla \hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 1\hfill & \nabla \hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 1\hfill \end{array}\right]$$ (3)

In the above equations, ∇ is the sampling time interval between two successive timesteps. In this article, we assume that the ∇ is a constant, and q is a known scalar that represents the intensity of the process noise. ¹⁹

In terms of the target measurement model, we adopt the mode in Liu et al. ²⁰ Suppose that all sensor nodes have the same sensing ability and the detection region of a sensor node is the circular area with a known radius r. When the distance between sensor $s_i$ and target ℑ, $d(s_i,\Im )$ , is less than r, the target could be detected. In this work, the candidate cluster nodes will be selected considering the predicted position of target, which we will described later. However, the predicted next position of target is not always very accurate. The node that closes to the predicted position of target may detect the target with a high probability at next timestep. So, we take into account the probability of the target detected by a sensor node when selecting the task cluster nodes. Then, the probability of target ℑ detected by sensor node $s_i$ is

$$\rho (s_i)=\{\begin{array}{cc}1,\hfill & \mathrm{d}({\mathrm{s}}_i,\Im )\le \mathrm{r}-r_u\hfill \\ \multicolumn{1}{c}{e^{-\lambda a^{\beta }}}& \mathrm{r}-{\mathrm{r}}_u\mathrm{d}({\mathrm{s}}_i,\Im )\le \mathrm{r}+{\mathrm{r}}_u\hfill \\ \multicolumn{1}{c}{0}& \mathrm{d}({\mathrm{s}}_i,\Im )>r+r_u\hfill \end{array}$$ (4)

where $r_u$ ( $r>r_u$ ) is the uncertainty measurement distance of sensor node $s_i$ , $a=\mathrm{d}({\mathbf{s}}_i,\Im )-(r-r_u)$ , and $\lambda$ and $\beta$ are measurement parameters dependent on sensor type. If node $s_i$ is selected as the CM or CH, $\rho (s_i)$ should be greater than the preset threshold ${\rho }_0$ . To be clear, the probability of target sensed by node $s_i$ , $\rho (s_i)$ , is only taken into account in CMs and CH selection phases to acquire a better tracking cluster. Once a sensor node is activated as a CM or CH, we deem that its measurements are accurate and reliable everywhere in its sensing range. The set of task nodes to track the target at timestep k, ${\mathrm{\Omega }}_k$ , is a subset of ${\mathrm{\Gamma }}_k$ which denotes the set of all candidate nodes that possibly detects the target. The mathematical expression of ${\mathrm{\Gamma }}_k$ is given by

$${\mathrm{\Gamma }}_k\subseteq \{s_i;||\mathbf{o}(i)-\mathbf{c}(k)||\le r+r_u,1\le i\le \mathrm{N}\}$$ (5)

See Figure 3 for an example that uses the model of target detected probability to select candidate nodes.

Figure 3.

An example of detection model. For any sensor node $s_i$ , if $\rho (s_i)>{\rho }_0$ , then $s_i\in {\mathrm{\Gamma }}_k$ .

If sensor $s_i$ is used to detect target ℑ at timestep k, the measurement $z_i(k)$ is given by

$$z_i(\mathrm{k})=h_i(\mathbf{x}(k))+v_i(k)$$ (6)

where $h_i(\mathbf{x}(k))=\sqrt{{(s_x(i)-x(k))}^2+{(s_y(i)-y(k))}^2}$ is the distance between sensor node $s_i$ and target ℑ at the kth timestep, and $v_i(k)$ are the observation noise of sensor node $s_i$ at the kth timestep. In detail, $v_i$ is an independent and identically distributed (i.i.d.) Gaussian random variable with zero mean and identical ${\sigma }^2$ for each sensor.

When the target ℑ moves in the sensing field, ${\mathrm{\Omega }}_k$ will vary with the timestep k. Let $N_k$ be the number of ${\mathrm{\Omega }}_k$ . Then, the sensor measurements at the kth timestep can be indicated in a vector form

$$\begin{array}{c}\multicolumn{1}{c}{{\mathbf{z}}_k=\mathbf{h}(X(k))+\mathbf{v}(k)}\\ =\left[\begin{array}{c}{h}_1(\mathbf{x}(k))\hfill \\ \multicolumn{1}{c}{h_2(\mathbf{x}(k))}\\ \multicolumn{1}{c}{⋮}\\ \multicolumn{1}{c}{h_{N_k}(\mathbf{x}(k))}\end{array}\right]+\left[\begin{array}{c}{v}_1(k)\hfill \\ \multicolumn{1}{c}{v_2(k)}\\ \multicolumn{1}{c}{⋮}\\ \multicolumn{1}{c}{v_{N_k}(k)}\end{array}\right]\hfill \end{array}$$ (7)

The covariance matrix of $\mathbf{v}(k)$ is given by

$$\mathbf{R}(k)=\mathrm{diag}({\sigma }^2,\dots ,{\sigma }^2{)}_{N_k\times N_k}$$ (8)

Energy consumption model

Energy consumption is considered as tracking cost and the energy consumption of non-task nodes which will fall asleep is negligible in this article. There are many aspects that will consume energy for task nodes during tracking the target, such as target sensing, data processing, and data communication. However, data communication consumes most of energy among them. The energy model used in this article is similar to the one used in the work of Bhardwaj and Chandrakasan. ²¹

Suppose that a sensor node $s_i$ is selected as the task sensor node. The energy cost of node $s_i$ for target sensing and data processing is $E_{\mathrm{sp}}$ , regarded as a constant in our work. For data communication, the energy consumed to transmit $b_c$ bits to a distance $r_{\mathrm{ij}}$ from sensor node $s_i$ to sensor node $s_j$ is $E_t(i,j)=(e_t+e_d{r}_{\mathrm{ij}}^{\theta })b_c$ , where $e_t$ and $e_d$ are decided by the transmitter, and $\theta$ depends on the channel characteristics, assumed to be time-invariant; the energy cost in receiving data by sensor node $s_i$ from its CH is $E_r(i)=e_r{b}_c$ , where $e_r$ is decided by receiver installed in sensor node $s_j$ .

Hence, the total energy consumption of a CM, $s_i$ , at each timestep is

$$E_{\mathrm{con}}(i)=E_t(i,\mathrm{ch})+E_{\mathrm{sp}}$$ (9)

Meanwhile, the total energy cost of current CH is

$$E_{\mathrm{con}}(\mathrm{ch})=E_r(\mathrm{ch})*N_k+E_{\mathrm{sp}}+E_t(\mathrm{ch},\mathrm{bs})+E_t(\mathrm{ch},\mathrm{ch}\_\mathrm{n})$$ (10)

In equation (10), the first term on the right stands for the receiving energy cost of current CH, which receives data both from the last CH and its cluster nodes; $E_{\mathrm{sp}}$ is the energy consumption for fusing, sensing, and processing. It is deemed to a constant for all nodes in this article; $E_t(\mathrm{ch},\mathrm{bs})$ is the energy consumption from current CH to the nearest base station; $E_t(\mathrm{ch},\mathrm{ch}\_\mathrm{n})$ is the energy expenditure for transmitting the target estimate results from the current CH to the next CH.

Therefore, the total energy consumed at timestep k is given by

$$E_{\mathrm{total}}=\sum _{i\in {\mathrm{\Omega }}_k,i\ne \mathrm{ch}}{E}_{\mathrm{con}}(i)+E_{\mathrm{con}}(\mathrm{ch})$$ (11)

UKF algorithm for WSN target tracking

Each task node will measure the distance between the target and itself, after it is activated to be a task node. When the preset time is up, they send their measurements to their CH which will perform UKF algorithm to fuse different measurements. In section “Target motion and detection model,” we put forward a linear target motion model and a nonlinear measurement model both with Gaussian noise distribution. We choose UKF to fuse different measurements and estimate the target state due to its superior performance in nonlinear systems with Gaussian noise. ²² The extended Kalman filter (EKF) is also widely used in target tracking, but it is less accurate and harder to implement than UKF when the target moves in a curved path. ²³ Moreover, although particle filter (PF) is applied widely, the PF has a higher computation complexity and does not outperform UKF for nonlinear models with Gaussian noise. ²⁴ The UKF algorithm is described as follows.

At timestep k, given the initial parameter $0\le {\omega }_0<1$ , we can obtain

$${\omega }_j=(1-{\omega }_0)/2n_x$$ (12)

$${\mathbf{c}}^{(j)}=\sqrt{\frac{n_x}{1-{\omega }_0}}{\mathbf{r}}^{(j)},j=1,2,\dots ,n_x$$ (13)

where $n_x$ is the dimensions of state vector and ${\mathbf{r}}^{(j)}$ is the unit vector of jth dimension. First, with the last estimate results, ${\mathbf{P}}^{\mathrm{xx}}(k-1|k-1)$ and $\mathbf{x}(k-1|k-1)$ , we have

$$\stackrel{\wedge }{\mathbf{x}}(k|k-1)=\mathbf{Ax}(k-1|k-1)$$ (14)

$$\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{xx}}}(k|k-1)=\mathbf{A}{\mathbf{P}}^{\mathrm{xx}}(k-1|k-1){\mathbf{A}}^T+\mathbf{Q}$$ (15)

$$\mathbf{D}(k|k-1)=\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{xx}}}(k|k-1{)}^{1/2}$$ (16)

where $\stackrel{\wedge }{\mathbf{x}}(k|k-1)$ and $\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{xx}}}(k|k-1)$ represent the predicted target state and the predicted error covariance of the target state, respectively. Then, the predicted observations are calculated by

$${\chi }^j(k|k-1)=\stackrel{\wedge }{\mathbf{x}}(k|k-1)+\mathbf{D}(k|k-1){\mathbf{c}}^j,j=0,\dots ,2n_x$$ (17)

$$\stackrel{\wedge }{\mathbf{z}}(k|k-1)=\sum _{j=0}^{2n_x}{\omega }_j\mathbf{h}({\chi }^{(j)}(k|k-1))$$ (18)

The innovation covariance is

$$\begin{array}{c}\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{zz}}}(k|k-1)=\sum _{j=0}^{2n_x}{\omega }_j[\mathbf{h}({\chi }^{(j)}(k|k-1))-\stackrel{\wedge }{\mathbf{z}}(k|k-1)]\hfill \\ \multicolumn{1}{c}{*{[\mathbf{h}({\chi }^{(j)}(k|k-1))-\stackrel{\wedge }{\mathbf{z}}(k|k-1)]}^T+\mathbf{R}}\end{array}$$ (19)

and the cross covariance matrix is determined by

$$\begin{array}{c}\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{xz}}}(k|k-1)=\sum _{j=0}^{2n_x}{\omega }_j[f({\chi }^{(j)}(k|k-1))-\stackrel{\wedge }{\mathbf{x}}(k|k-1)]\hfill \\ \multicolumn{1}{c}{*{[\mathbf{h}({\chi }^{(j)}(k|k-1))-\stackrel{\wedge }{\mathbf{z}}(k|k-1)]}^T}\end{array}$$ (20)

Finally, according to the above equations, the update can be performed using the normal Kalman filter equations

$${\mathbf{K}}_k\stackrel{\mathrm{\Delta }}{=}\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{xz}}}(k|k-1)\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{zz}}}(k|k-1{)}^{-1}$$ (21)

$$\mathbf{x}(k|k)=\stackrel{\wedge }{\mathbf{x}}(k|k-1)+{\mathbf{K}}_k({\mathbf{z}}^0(k)-\stackrel{\wedge }{\mathbf{z}}(k|k-1))$$ (22)

$${\mathbf{P}}^{\mathrm{xx}}(k|k)=\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{xz}}}(k|k-1)-{\mathbf{K}}_k\stackrel{\wedge }{{\mathbf{P}}^{\mathrm{xz}}}(k|k-1)({\mathbf{K}}_k{)}^T$$ (23)

where $\mathbf{x}(k|k)$ and ${\mathbf{P}}^{\mathrm{xx}}(k|k)$ , respectively, denote the estimated current target state and the estimated current error covariance of the target state.

According to Xiao et al., ⁶ the trace of the estimated target state covariance matrix, ${\mathrm{\Phi }}_k$ , denotes the mean squared error (MSE) of the updated state. It can be used to estimate the tracking performance at timestep k

$${\mathrm{\Phi }}_k=\mathrm{trace}\{{\mathbf{P}}^{\mathrm{xx}}(k|k)\}$$ (24)

Clearly, the smaller the ${\mathrm{\Phi }}_k$ , the better the tracking performance. Thus, a threshold ${\mathrm{\Phi }}_0$ is preset as the maximum value that we can accept. If ${\mathrm{\Phi }}_k$ is less than ${\mathrm{\Phi }}_0$ , the tracking accuracy meets our demands. If not, it is deemed to be unsatisfied. From the proof in Hu et al., ¹⁸ we can know that the tracking accuracy of the UKF is improved when $N_k$ increases. In this article, we set the least number of task sensor nodes, $N_{\min }$ , to ensure the track performance ${\mathrm{\Phi }}_k<{\mathrm{\Phi }}_0$ .

Energy-balance criterion

WSNs are characterized by limited on-board energy supply. Therefore, it is important to make the whole network leave residual energy as much as possible with a uniform distribution. Otherwise, the sensor nodes with less energy may yet continue to perform tracking tasks leading to their energy depletion and even the failure of whole network. Note that this network paralysis may still happen in the presence of some sufficient energy nodes. This uneven energy depletion phenomenon is called “energy hole.” ²⁵

The term energy balance in this article adopts the definition in Hu et al. ¹⁸ The standard deviation of the sensor node set energy distribution can be conveniently adopted as an indicator to evaluate the degree of energy balance. Thus, the smaller energy-balance metric implies the more even distribution of energy. Then, it may not occur in situation where some of the nodes are disabled for energy depletion but others still have a lot of energy remained. This means the run time of nodes with low energy will be prolonged as the energy-balance metric of the network reduces, which further extends the network lifespan by increasing the number of efficient task nodes.

Definition 1. Energy-balance standard. Take $\{e_j;1\le j\le N\}$ as the remaining energy of N candidate sensing nodes at a timestep. The mathematic formulation of energy-balance standard $B_e$ is given by

$$B_e=\sqrt{\frac{1}{N}\sum _{j=1}^N{(e_j-\overline{e})}^2}\overline{e}=\frac{1}{N}\sum _{j=1}^N{e}_j$$ (25)

Multiple sensor node collaborative scheduling method

Description of target-tracking process

All sensor nodes except boundary nodes are initially set in sleep mode. For each of the boundary nodes, its passive infrared (PIR) sensor is off but periodically turns it on. Once a target appears in the monitor region boundary, the first node that finds the target will start tracking task. It will obtain the measurements and predict the next target state. Then, the next task sensor nodes are selected and activated to form a cluster (including the CH). Note that the problems of boundary detection and recovery of the lost target are out of the scope of this article and it is assumed that there is no transmission delay and packet loss in the process of tracking.

At kth tracking step, the PIR sensor of a node will be turned on whenever the sensor node is activated by the last CH. When the PIR sensor makes a positive detection, the node will turn on the distance-measuring sensor to measure the distance between the target and itself. Figure 4 describes the necessary operations during each tracking step. We assume that each sensor node can compute and store data locally, as well as replying with data packets locally.

Figure 4.

Operations during a timestep.

In general, the selected CMs (not the CH) will perform the following tasks:

1. Once receiving the activated signal from the last CH, the nodes will keep on executing the target detection task.

2. When the detecting time exceeds the preset time interval, these nodes will forward their current measurements to the CH after a random-delayed time with the conflict detect mechanism, CSMA/CA.

3. Once sending the measurements successfully, they will shut down their sensors and turn into sleep mode again to save energy until awakened in next time.

As for the CH, which acts as the scheduler of the cluster, it needs to perform the following works:

1. As soon as receiving the estimate results from the last CH, it will also keep on executing the task of target detection.

2. When the preset time interval is up, it begins to receive the measurements from its cluster nodes, and then carries out UKF algorithm to fuse different measurements with its own measurements. If the CH could not sense the target, it will fuse different measurements without its own data.

3. The CH selects appropriate cluster nodes and a new CH for next cluster based on the energy-balanced metric, and then passes the target estimate results to the new CH.

4. After reporting the current target estimate results to the nearest sink, it also closes its sensors and put in sleep state until awakened in next time.

There is a problem that we are about to solve: how does the CH obtain the current energy distributions of nodes within its sensing range when it selects the next task cluster nodes and CH. In order to resolve this problem, several following issues must be formulated.

1. Only task nodes will consume energy. The non-task nodes will stay asleep during the tracking and their energy should be negligible.

2. The measurement data packet that a CM sends to its CH contains distance-measurement and its current residual energy with time label.

3. When the CH transmits the estimated state of the target and its covariance matrix to the closest sink, the residue energy distribution information of current cluster will also be sent with them.

4. After receiving data packets from a CH, the sinks will update current residue energy of each node and send the residue energy distribution information of all sensor nodes to the next CH. This CH, upon receiving the information, will update the energy distribution of all sensor nodes according to the time label.

Selection of CH

Tracking performance strongly depends on which sensor node acts as the CH, since the energy consumption of each cluster node is dependent with the communication distance between itself and CH. Thus, the optimal CH must be selected from a given set of task cluster nodes. The key issue of CH selection is to seek an appropriate criterion. One criterion to select the CH is to obtain the node with the least whole energy consumption $E_{\mathrm{total}}$ at the current timestep. However, $E_{\mathrm{total}}$ may not even be sufficient to support the system, resulting in the network crash.

For solving the above problem on the system level, we choose both the average remaining energy $E_{\mathrm{avg}}$ and the energy-balance metric $B_e$ as the guideline to judge the optimal CH. ²⁶ Denote ${\mathrm{\Omega }}_k$ and $s_{j^{*}}$ as the task sensor node set and the selected CH from the ${\mathrm{\Omega }}_k$ at timestep k, respectively. Since the positions of all sensor nodes are known in advance, the predicted total energy consumption of each cluster node and the CH can be established on the basis of equations (9) and (10). In addition, the current remaining energy of each node, $E_{\mathrm{rem}}$ , is stored in current CH’s memory according to section “Description of target-tracking process.” Therefore, the average residue energy of task cluster nodes after tracking the target can be calculated as

$$E_{\mathrm{avg}}(j^{*})=\frac{1}{{\mathrm{\Delta }}_k}\sum _{i=1}^{{\mathrm{\Delta }}_k}(E_{\mathrm{rem}}(i)-E_{\mathrm{con}}(i))$$ (26)

where the ${\mathrm{\Delta }}_k$ is the cardinality of candidate sensor node set, ${\mathrm{\Gamma }}_k$ , at timestep k. Note that if node $s_i\in {\mathrm{\Gamma }}_k$ and $s_i\notin {\mathrm{\Omega }}_k$ , then $E_{\mathrm{con}}(i)=0$ . The energy-balance metric $B_e$ can be expressed as

$$\begin{array}{c}{B}_e(j^{*})=\sqrt{\frac{1}{{\mathrm{\Delta }}_k}\sum _{i=1}^{{\mathrm{\Delta }}_k}(E_{\mathrm{rem}}(i)-E_{\mathrm{con}}(i)-E_{\mathrm{avg}}(j^{*}){)}^2}\hfill \\ \multicolumn{1}{c}{=\sqrt{\frac{1}{{\mathrm{\Delta }}_k}\sum _{i=1}^{{\mathrm{\Delta }}_k}(E_{\mathrm{rem}}(i)-E_{\mathrm{con}}(i){)}^2-{E_{\mathrm{avg}}}^2(j^{*})}}\end{array}$$ (27)

According to section “Energy consumption model,” the energy consumption of the task cluster nodes is related to the distance. Thus, when other nodes are selected to act as the CH, the energy consumption of the network changes, and so does the energy balance of the network.

Moreover, to avoid selecting a low-energy node as the CH, we take advantage of the residue energy ratio

$$\eta (i)=E_{\mathrm{con}}(i)/E_{\mathrm{rem}}(i)$$ (28)

to characterize node $s_i$ . Clearly, $\eta (i)$ should belong to (0,1). Particularly, the corresponding $\eta (i)$ must be less thana preset threshold ${\eta }_0$ if the node $s_i$ is selected as the CH. The reason is that a low-energy node will die quickly after it acts as the CH which consumes more energy than the CM. For example, suppose that $E_{\mathrm{con}}(\mathrm{ch})=0.5$ J, $e_0=0.12$ J, and $E_{\mathrm{rem}}(i)=0.6$ J. If node $s_i$ is selected as the CH in current timestep, then its remaining energy is 0.1 J after this tracking. The node $s_i$ is believed dead since its remaining energy is not enough to work well as a cluster node in next tracking ( $0.1\mathrm{J}<0.12\mathrm{J}$ ). However, if this node is selected as a CM instead of a CH, it will consume 0.12 J during current timestep and then it could work well as a CM four times in next tracking.

The smaller energy-balance metric implies a longer lifetime of the network given a total amount of energy, and the higher total energy implies a longer lifetime of the network given an energy balance. ¹⁸ Thus, in order to extend the lifetime of tracking network, we should maximize the average remaining energy $E_{\mathrm{avg}}(j^{*})$ and minimize the energy-balance metric $B_e(j^{*})$ , which can be formulated as a double-objective function optimization problem

$$\{\begin{array}{c}\max {\mathrm{E}}_{\mathrm{avg}}(j^{*})\hfill \\ \multicolumn{1}{c}{\min {\mathrm{B}}_e(j^{*})}\\ \multicolumn{1}{c}{\begin{array}{c}s.t.\eta (j^{*})\le {\eta }_0\hfill \\ \multicolumn{1}{c}{j*\in {\mathrm{\Omega }}_k}\end{array}}\end{array}$$ (29)

We adopt the evaluation function method based on the weighted sum of squares to solve this multi-objective optimization problem since its low calculation load. A detailed formulation about the method is be presented in section “Evaluation function method.”

Selection of task nodes

In this section, our goal is to find a suitable node subset from the predicted candidate sensing node set ${\mathrm{\Gamma }}_k$ to maximize the average residual energy and to minimize the standard deviation of the residual energy. If the number of ${\mathrm{\Gamma }}_k$ , ${\mathrm{\Delta }}_k$ , is greater than $N_{\min }$ (the least number to ensure the tracking accuracy), then $N_{\min }$ optimal task nodes will be chosen from ${\mathrm{\Gamma }}_k$ to form a task cluster. However, if it is less than $N_{\min }$ , the preset threshold should be decreased to ${\rho }_1$ from ${\rho }_0$ to get more candidate sensing nodes. If it remains below $N_{\min }$ , all suitable candidate nodes in ${\mathrm{\Gamma }}_k$ will be selected.

We could formulate the problem of task node subset selection based on energy balance at timestep k as follows.

Given:

• A candidate sensor node set ${\mathrm{\Gamma }}_k=\{s_i;1\le i\le {\mathrm{\Delta }}_k\}$ .

• Their current energy set $E_c=\{E_{\mathrm{rem}}(i);s_i\in {\mathrm{\Gamma }}_k\}$ .

Find:

• The optimal sensor node subset ${\mathrm{\Omega }}_k$ which consists of $N_k$ sensor nodes.

Limitation:

• If $s_i\in {\mathrm{\Omega }}_k$ , then $E_{\mathrm{rem}}(i)$ should be above a threshold value $e_0$ to ensure that it can operate properly and ${\rho }_{s_i}$ should be above the preset value.

• The subset should fulfill the condition that $E_{\mathrm{avg}}$ is as large as possible, while the $B_e$ is the smallest among all possible choices.

As shown in above descriptions, we know that both $E_{\mathrm{avg}}$ and $B_e$ depend on which nodes are selected. Therefore, the optimizing problem is a subset selection problem, as well as a binary linear problem. Hu et al. ¹⁸ have proved the problem is an NP-hard problem by reducing it into the maximum independent set (MIS) problem, a well-known NP-hard problem. ²⁷ Most existing methods are too complex to be implemented on resource-limited sensor nodes. For example, if we adopt the exhaustive search method to find $N_k$ suitable nodes from ${\mathrm{\Delta }}_k$ candidate nodes, then there will be $C_{{\mathrm{\Delta }}_k}^{N_k}=\frac{{\mathrm{\Delta }}_k!}{N_k!({\mathrm{\Delta }}_k-N_k)!}$ kinds of different results. Obviously, the $C_{{\mathrm{\Delta }}_k}^{N_k}$ will increase rapidly with the number of ${\mathrm{\Delta }}_k$ . Hence, it is necessary to find a polynomial time heuristic method to solve the problem. In our work, we put forward a greedy heuristic algorithm to solve this optimizing problem described in section “Greedy balance replace heuristic algorithm.”

Evaluation function method

Marler and Arora ²⁸ conducted a comprehensive discussion about the weighted sum method for multi-objective optimization. The basic idea of this method is that the multi-objective programming problem is transformed into the single-objective programming problem, which is constructed by each objective function of the multi-objective programming problem. Following this method, we divide equation (29) into two single objective optimization problems. The maximum average remaining energy sub-optimization problem can be formulated as

$$\{\begin{array}{c}\min -E_{\mathrm{avg}}(j^{*})\hfill \\ \multicolumn{1}{c}{s.t.\eta (j^{*})\le {\eta }_0}\\ \multicolumn{1}{c}{j^{*}\in {\mathrm{\Omega }}_k}\end{array}$$ (30)

and the minimum energy-balance metric sub-optimization problem can be formulation as

$$\{\begin{array}{c}\min {\mathrm{B}}_e(j^{*})\hfill \\ \multicolumn{1}{c}{s.t.\eta (j^{*})\le {\eta }_0}\\ \multicolumn{1}{c}{j^{*}\in {\mathrm{\Omega }}_k}\end{array}$$ (31)

Denote $j_1^{*}$ and $E_{\mathrm{avg}}(j_1^{*})$ as the optimal solution of equation (30) and $j_2^{*}$ and $B_e(j_2^{*})$ as the optimal solution of equation (31). Generally speaking, $j_1^{*}$ is not the same as $j_2^{*}$ . Hence, the vector ${\mathbf{f}}_0=[E_{\mathrm{avg}}(j_1^{*}),B_e(j_2^{*})]$ , which consists of the sub-optimal solution $E_{\mathrm{avg}}(j_1^{*})$ and the sub-optimal solution $B_e(j_2^{*})$ , does not belong to the image set of the double-objective programming problems. Then, the weighted sum of squares is used to construct an evaluation function. However, the average remaining energy and the energy-balance metric are two different physical quantities, so we need to normalize them first. The normalized weighted sum of squares is given by

$$\begin{array}{c}\multicolumn{1}{c}{\hslash (j)=\hslash (\mathbf{f}(j))=\lambda \frac{B_e(j)-B_e(j_2^{*})}{B_e(\max )-B_e(j_2^{*})}}\\ +(1-\lambda )\frac{-E_{\mathrm{avg}}(j)+E_{\mathrm{avg}}(j_1^{*})}{E_{\mathrm{avg}}(j_1^{*})-E_{\mathrm{avg}}(\min )}\hfill \end{array}$$ (32)

where $\mathbf{f}(j)=[-E_{\mathrm{avg}}(j),B_e(j)]$ , $\lambda \in (0,1)$ weights the $B_e$ priority and $B_e(\max )=\max \{B_e(j);{\eta }_j\le {\eta }_0,j\in {\mathrm{\Omega }}_k\}$ ; $E_{\mathrm{avg}}(\min )=\min \{E_{\mathrm{avg}}(j);{\eta }_j\le {\eta }_0,j\in {\mathrm{\Omega }}_k\}$ . Then, our goal is to find a solution $j_0$ to minimize the evaluation function. We can acquire the whole near-optimal solution by means of solving the single-objective programming problem

$$\{\begin{array}{c}min\hslash (j)\hfill \\ \multicolumn{1}{c}{s.t.\eta (j)\le {\eta }_0}\\ \multicolumn{1}{c}{j\in {\mathrm{\Omega }}_k}\end{array}$$ (33)

As shown above, we have described the process of using the evaluation function method to solve the double-objective optimization problem in detail. Now, we need to discuss the relationship between the solution of equation (33) and the solution of equation (29).

Definition 2. Relationship of vector. Supposing there are two vectors $\mathbf{x}=[x_1,x_2,\dots ,x_n]$ and $\mathbf{y}=[y_1,y_2,\dots ,y_n]$ ,

• if $x_i=y_i(i=1,2,\dots ,n)$ , then $\mathbf{x}=\mathbf{y}$ ;

• if $x_i<y_i(i=1,2,\dots ,n)$ , then $\mathbf{x}<\mathbf{y}$ ;

• if $x_i\le y_i(i=1,2,\dots ,n)$ , but there are at least one $i_0$ that satisfies $x_{i_0}<y_{i_0}$ , then $\mathbf{x}\le \mathbf{y}$ .

Definition 3. Efficient solution. Suppose $x^{*}\in {\mathrm{\Omega }}_k$ and ${\eta }_{x^{*}}\le {\eta }_0$ , where ${\mathrm{\Omega }}_k$ is the set of cluster nodes at timestep k. If the circumstance that at least one $x\in {\mathrm{\Omega }}_k$ satisfies $\mathbf{f}(x)\le \mathbf{f}(x^{*})$ does not exist, then $x^{*}$ is the efficient solution of the multi-objective programming problems.

Denote $R_e^{*}$ as the whole efficient solutions of the multi-objective programming problems. The intuition behind the term efficient solution is that there does not exist other solutions which are better than it. A simple example is shown in Figure 5. Therein, $\mathbf{f}(x)=[f_1(x),f_2(x)]$ , point a and point b are the optimal solutions of $f_1(x)$ and $f_2(x)$ , respectively. Hence, the set of efficient solution is $R_e^{*}$ = [a,b].

Figure 5.

A schematic drawing of efficient solution.

Definition 4. Strictly monotone increasing function. For $\forall {\mathbf{f}}_1,{\mathbf{f}}_2\in R^n$ , n is the dimension of $\mathbf{f}$ , if $h({\mathbf{f}}_1)<h({\mathbf{f}}_2)$ always holds when ${\mathbf{f}}_1\le {\mathbf{f}}_2$ , then $h(\mathbf{f})$ is described as the strictly monotone increasing function of $\mathbf{f}$ .

According to the above two definitions, the relationship between the solution of the single-objective programming problem after conversion and the multi-objective programming problem are described in Theorem 1. ²⁸

Theorem 1. If $\hslash (\mathbf{f}(j))$ is the strictly monotone increasing function of $\mathbf{f}(j)$ , where $j\in {\mathrm{\Omega }}_k$ and ${\eta }_j\le {\eta }_0$ , then the optimal solution of the single-objective programming problem after conversion is the efficient solution of the multi-objective programming problem.

Now, we will prove that the optimal solution of equation (33) is the efficient solution of equation (29) in the light of Theorem 1. The proof is as follows.

Proof 1. Given $\mathbf{f}(i_1)=[-E_{\mathrm{avg}}(i_1),B_e(i_1)]\le \mathbf{f}(i_2)=[-E_{\mathrm{avg}}(i_2),B_e(i_2)]$ , where $i_1$ and $i_2$ are two candidate nodes of the CH. Then, we can obtain three kinds of cases on the basis of Definition 2

• Case 1: $-E_{\mathrm{avg}}(i_1)<-E_{\mathrm{avg}}(i_2)$ , $B_e(i_1)<B_e(i_2)$ ;

• Case 2: $-E_{\mathrm{avg}}(i_1)\le -E_{\mathrm{avg}}(i_2)$ , $B_e(i_1)<B_e(i_2)$ ;

• Case 3: $-E_{\mathrm{avg}}(i_1)<-E_{\mathrm{avg}}(i_2)$ , $B_e(i_1)\le B_e(i_2)$ .

Denote $E_{\mathrm{avg}}(j_1^{*})$ and $B_e(j_2^{*})$ as the optimal solution of equations (30) and (31), respectively. According to equation (32), we can know that the inequality $\hslash (\mathbf{f}(i_1))<\hslash (\mathbf{f}(i_2))$ always holds. Then, the function $\hslash (\mathbf{f}(\mathbf{x}))$ is the strictly monotone increasing function of $\mathbf{f}(\mathbf{x})$ on the basis of Definition 4. Therefore, the optimal solution of equation (33) is the efficient solution of the equation (29).

Greedy balance replace heuristic algorithm

In our work, we propose a novel sensor scheduling algorithm, Greedy Balance Replace Heuristic Algorithm (GBRHA), to select a near-optimal task sensor subset from the candidate sensing node set. What we need to emphasize is that the CH is also selected by GBRHA, since the selection of task node set is accompanied by the selection of CH. The selection criterion takes into account both the energy balance and the average residue energy of WSN. The goal of GBRHA is to construct a suitable cluster which not only extends the network lifespan but also provides certain tracking quality guarantee.

GBRHA is described in detail in Algorithm 1 and Algorithm 2. Given the task node set, we can obtain the CH by means of Algorithm 1 with the computational complexity $O({\Lambda }_L)$ . According to Algorithm 2, we invoke Algorithm 1 to get the CH and the corresponding evaluation function value after we select a task node set. In Algorithm 2, the computational complexity of step 1 and that from step 2 to step 12 are $O({\Lambda }_L\mathrm{lo}{g}^{{\Lambda }_L})$ and $O(({\Lambda }_L-N_{\min }{)}^2)$ , respectively. In summary, we can obtain that the computational complexity of the GBRHA is $O(({\Lambda }_L-N_{\min }{)}^2)$ .

Algorithm 1 Optimal cluster head selection-based energy balance
Input: The task node set $\ell$ with their energy value, and the candidate node set $L_k$ with their energy value.
Output: The optimal CH, J, the corresponding evaluation function value $\hslash (J)$ and predicted residue energy set of $\ell$ , $E_{\mathrm{re}}$ .
1: function $[J,\hslash (J),E_{\mathrm{re}}]=\mathrm{CH}\_\mathrm{elect}$ ( $\ell$ , ${\mathrm{\Gamma }}_k$ )
2:  $n\leftarrow \mathrm{length}(\ell )$
3: for $i=1\to n$ do
4:  Find the nearest sink to the current CH $s_i$ .
5:  According to equations (9) and (10), calculate the predicted energy consume of each task node.
6:  Compute the average and standard deviation of the predicted residue energy of the ${\mathrm{\Gamma }}_k$ , obtaining $E_{\mathrm{avg}}(i)$ , $\mathrm{Be}(i)$ , respectively.
7:  Calculate the $\eta (i)$ , according to equation (28).
8: end for
9:  $B{e}_{\min }\leftarrow \min (\{\mathrm{Be}(i),i=1,2,\dots ,n\})$ .
10:  $\mathrm{Eav}{g}_{\max }\leftarrow \max (\{E_{\mathrm{avg}}(i),i=1,2,\dots ,n\})$ .
11: for $j=1\to n$ do
12:  if $\eta (j)<{\eta }_0$ then calculate the $\hslash (j)$ , according to the equation (32).
13:  else
14:    ${\hslash }_j=100$ .
15:  end if
16: end for
17:  $\hslash (J)\leftarrow \min (\{\hslash (j),j=1,2,\dots ,n\})$ .
18: Thus, the optimal CH is J and corresponding predicted residue energy set of $\ell$ is $E_{\mathrm{re}}$ .
19: end function

Algorithm 2 Greedy balance replace heuristic algorithm (GBRHA)
Input: A set of candidate nodes, ${\mathrm{\Gamma }}_k$ and their residue energy set $E_c$ at timestep k.
Output: A set of task nodes ${\mathrm{\Omega }}_k$ and a cluster head node $s_{j^{*}}$ .
1: $L_k\leftarrow \{s_i;s_i\in {\mathrm{\Gamma }}_k,{\rho }_{s_i}>{\rho }_0,E_{\mathrm{rem}}(i)>e_0\}$ .
2: if the number of $L_k$ , ${\Lambda }_k$ , satisfies ${\Lambda }_k\le N_{\min }$ then
3:  $L_k\leftarrow \{s_i;s_i\in {\mathrm{\Gamma }}_k,{\rho }_{s_i}>{\rho }_1,E_{\mathrm{rem}}(i)>e_0\}$ .
4: end if
5: Sort $L_k$ nodes according to the residual energy in the ascending order, and get $L_a$ .
6: if the number of $L_a$ , ${\Lambda }_L$ , is still less than or equal to $N_{\min }$ then
7: Execute the function $\mathrm{CH}\_\mathrm{elect}(L_a,L_a)$ (Algorithm 1), then get the cluster head J.
8: ${\mathrm{\Omega }}_k\leftarrow L_a,s_{j^{*}}\leftarrow J$ .
9: else
10: Select the $N_{\min }$ highest-energy nodes from the $L_a$ as the set of task nodes, ${\ell }_1$ .
11:  $\ell \leftarrow {\ell }_1$
12: for i=1 $\to {\Lambda }_k-N_{\min }+1$ do
13:  Execute the function $\mathrm{CH}\_\mathrm{elect}(\ell ,L_a)$ , then obtain the cluster head $\mathrm{ch}(i)$ , the evaluation function value ${\hslash }_i$ and the corresponding predicted residue energy set of $\ell$ , $E_{\mathrm{re}}$ .
14:  Replace the task node which has the smallest predicted residue energy with the non-task node which has the most residue energy, then get ${\ell }_{i+1}$ .
15:  Update the next task node set, $\ell \leftarrow {\ell }_{i+1}$ .
16: end for
17:  ${\hslash }_j\leftarrow \min (\{{\hslash }_i,i=1,2,\dots ,{\Lambda }_k-N_{\min }+1\})$ .
18:  ${\mathrm{\Omega }}_k\leftarrow {\ell }_j$ , $s_{j^{*}}\leftarrow \mathrm{ch}(j)$ .
19: end if

Simulation result and evaluation

In this section, we evaluate the proposed mechanisms and compare them with the state-of-the-art algorithms. To evaluate and analyze the performances of the proposed algorithms, the software MATLAB is used to simulate the tracking scene.

Network lifespan

Before reporting the evaluation results, we first define network lifespan used to evaluate tracking performance. The network lifespan defined in the literature ²⁹ is the operation time till the first sensor depletes its energy reserves. Meanwhile, Hu et al. ²⁶ defined network lifespan as a continuous time interval during which the tracking performance is above the preset value.

Since energy consumptions on different sensor nodes vary significantly, some nodes may deplete their energy rapidly. Also, the sensor nodes are deployed randomly distributed over the sensing region, and the case that the number of task nodes is less than $N_{\min }$ may frequently happen. Thus, in these situations, the above definitions may be inappropriate. Instead, the term of network lifespan in this work specialized at target tracking in WSNs is defined by considering the above circumstances.

Definition 5. Network lifespan. Network lifespan of target tracking in WSN, $T_{\mathrm{NL}}$ , is the continuous time interval during which one of the following two conditions should be satisfied:

• Number of task sensor nodes at each timestep is greater than or equal to $N_{\min }$ ;

• Ratio of the task sensor node number $N_k$ to the candidate sensor node number ${\mathrm{\Delta }}_k$ is over the preset threshold ${\delta }_0$ .

The mathematic formulation of the above definition is

$${\mathrm{T}}_{\mathrm{NL}}=\underset{k}{max}\{k|N_k\ge N_{\min }||\frac{N_k}{{\mathrm{\Delta }}_k}\ge {\delta }_0\}$$ (34)

Simulation setup

Table 2 summarizes the system parameters and their settings. In our simulation, we consider the tracking scene shown in Figure 2. The monitored sensor network area is 100 m×100 m with coordinates from (0,100) to (0,100). It is covered by $N=100$ sensing range-limited and randomly distributed sensor nodes, and the initial energy of each node is 0.2 J. In this article, a single target that appears in a known location moves at a curve path. For each tracking action, the tracking process is sampled at $K=20$ discrete timesteps. The position coordinates of sinks are placed separately at (25,25), (25,75), (75,25), and (75,75) with infinite energy. A simulation scene is shown in Figure 6.

Table 2.

System parameters and settings.

Parameter	Symbol	Setting
Number of sensor nodes	N	100
Sensor sensing radius	r	15
Uncertainty measurement distance	$r_u$	2
Detection probability threshold	${\rho }_0$ , ${\rho }_1$	0.6,0.2
Parameter for node detection	$\beta$	0.5
Parameter for node detection	$\lambda$	0.5
Parameter for network lifespan	${\delta }_0$	0.6
Parameter for the receiving energy	$e_r$	$1.35\times {10}^{-4}$ J/bit
Parameter for the transmitting energy	$e_t$	$4.5\times {10}^{-5}$ J/bit
Parameter for the transmitting energy	$e_d$	$1.0\times {10}^{-8}$ J/bit
Parameter for the transmitting energy	$\theta$	2
Parameter for the processing energy	$e_{\mathrm{sp}}$	$8.0\times {10}^{-7}$ J/bit
Sampling time interval	∇	0.2 s
Standard deviation of observation noise	$\sigma$	$\sqrt{2}$
Data for transmitting and receiving	$b_c$	48 bits
Energy ratio threshold	${\eta }_0$	0.6
Lowest operation energy of sensor node	$e_0$	0.015 J
Least task sensor number	$N_{\min }$	4

Figure 6.

A simulation scene used in our work.

Impact of weight coefficient $\lambda$

From equation (32), weight coefficient $\lambda$ is used to weight the normalized $B_e$ and the normalized $E_{\mathrm{avg}}$ . Thus, it has a great influence on the selection of task cluster nodes and their CH, as well as on the network lifespan. Figure 7 shows the impacts of $\lambda$ on the lifespan of tracking network. The average network lifespan here is indicated by the average repetition times of tracking actions after running for 100 times experiments. It can be found that as $\lambda$ increases to a certain value (in the experiment, it is 0.65), the average network lifespan tends to rise. However, as $\lambda$ increases to a greater value, the average network lifespan tends to reduce. The reasons for this phenomenon are that as $\lambda$ increases, the energy-balance metric of network $B_e$ becomes more and more important in the weighted sum of squares $\hslash (j)$ , and then, the energy distribution of network becomes more and more balanced, resulting in a longer lifetime of the node with less energy. Nevertheless, as $\lambda$ goes on increasing, the average remaining energy $E_{\mathrm{avg}}$ is considered less and less on selecting the CM and CH. Then, the energy consumption of network at each timestep becomes increasing, leading to the death of tracking network. Therefore, $\lambda$ should be set to a suitable value. In the following simulations, we set $\lambda =0.65$ .

Figure 7.

Average network lifespan for $\lambda =[0.05-0.95]$ , after running for 100 times.

Amount of data exchange

From our collaborative scheduling method, the ordinary cluster nodes do not need to communicate with its neighbor nodes and the sink, which could significantly reduce the amount of data exchanged during a timestep. Katragadda et al. ³⁰ proposed two consensus-based distributed tracking algorithms for nonlinear systems, namely, the extended information consensus filter (EICF) and the extended information weighted consensus filter (EIWCF). Figure 8 shows that the amount of data exchanged in our scheduling method is far less than that in EICF and EIWCF. In this article, we select the least task cluster nodes to track the target and, in general, $N_k$ is a fixed value (in this experiment, it is 4). Thus, the received data packets during a timestep is also a fixed value. For EICF and EIWCF, data packets exchange constantly among nodes and all their neighbors, which results in a heavy communication burden to the WSN. Hence, the amount of data exchanged in this article is greatly reduced compared with that in EICF and EIWCF.

Figure 8.

Amount of data exchanged of different methods during a tracking.

Evaluation results and analysis of GBRHA

In order to evaluate the performance of GBRHA, we first compare GBRHA with the existing Optimal Cooperation Scheduling Algorithm (OCSA). ²⁵ Shi et al. ²⁵ proposed the OCSA for sensor scheduling, based on the energy-efficient criterion with complexity given by $O(({\Lambda }_L-N_{\min }{)}^2)$ . Both OCSA and GBRHA adopt the greedy algorithm to deal with the sensor scheduling problem. However, the base criterion of OCSA is to minimize the transmission energy at each timestep, while the base criterion of GBRHA is to maximize the residue energy and minimize residue energy variations (energy balanced). That is, the reason why we choose OCSA to compare with GBRHA.

Moreover, Hu et al. ¹⁸ put forward many heuristic algorithms to tackle the sensor node scheduling problem for target tracking in WSNs based on energy balance. According to Hu et al., ¹⁸ RHA and EHA are the most reasonable and effective ones among the proposed algorithms, whose computation complexities are $O({\Lambda }_L^2)$ and $O({\Lambda }_L^2\log {\Lambda }_L)$ , respectively. Hence, we will also compare our method with RHA and EHA.

Tracking error

After executing 100 calculations, several figures about the average tracking performance are obtained. Figure 9 shows the real tracking trajectories of maneuvering target under four algorithms. Figures 10 and 11 show the tracking quality of GBRHA, OCSA, RHA, and EHA. The tracking quality is measured by the error that is indicated by the Euler distances between true target location and estimated target location at each timestep. From Figures 10 and 11, it can be seen that GBRHA has the best performance in this metric and RHA, EHA are second to GBRHA, while the performance of OCSA is the worst. Besides, in the actual situation, we usually have no idea of true target location. Therefore, according to section “UKF algorithm for WSN target tracking,” the trace of the estimated target state covariance matrix, ${\mathrm{\Phi }}_k$ , can also be used to show the tracking performance. As shown in Figure 12, the tracking performance of OCSA, RHA, and EHA indicated by ${\mathrm{\Phi }}_k$ are almost the same, but OCSA is the worst yet. In addition, since the nodes within the range of the target becomes less at the last several timesteps as shown in Figure 6, the performance of tracking accuracy of GBRHA, RHA, and EHA becomes worse from timestep 16 to timestep 20 which can be seen from Figure 12.

Figure 9.

Tracking trajectories of the target under different scheduling algorithms.

Figure 10.

Tracking error under different scheduling algorithms at each timestep.

Figure 11.

Tracking error performance under different scheduling algorithms in a tracking action.

Figure 12.

Tracking accuracy performance under different scheduling algorithms in a tracking.

Compared with OCSA, GBRHA chooses the nodes which make the whole network more energy-balanced to perform tracking tasks at each timestep, so the selected nodes will be balanced dispersion. However, OCSA chooses the nodes close to the predicted position of target in order to minimize current transmission energy consumption. As for RHA and EHA, they are similarly based on energy-balanced metric and their target error performance is a little worse than GBRHA, but their computation complexity is larger than that of GBRHA. However, as we all know, the WSN consists of a large number of low-cost sensor nodes with limiting computing power. Thus, the target-tracking algorithm we pursue not only has a preferable performance but also a lower computation complexity.

In this article, we use UKF instead of EKF to fuse different measurement and estimate the target state under GBRHA scheduling algorithm. Figure 13 compares the tracking performance between UKF and EKF under GBRHA scheduling algorithm. We can find that UKF outperforms both the first-order EKF and the second-order EKF in tracking accuracy without computing the Jacobian or Hessian matrices.

Figure 13.

Tracking accuracy performance of different estimation algorithms under GBRHA in a tracking. EKF and EKF2 denote the performance of first-order EKF and second-order EKF under GBRHA scheduling algorithm, respectively

Lifespan of tracking network

In order to compare the energy consumption of each tracking action and network lifespan under the four algorithms, repetitive tracking actions are carried out until the network is dead according to Definition 5. As shown in Figures 14 and 15, the mean energy consumption of one tracking action in GBRHA is slightly more than that in OCSA, but the network lifespan of GBRHA, indicated by the average repetition times of tracking actions after many experiments, is longer than that of OCSA. Compared with RHA and EHA, GBRHA is provided with almost the same outstanding performance in mean energy consumption of tracking action and network lifespan. Figure 16 shows the lowest normalized residue energy of the current cluster nodes after each timestep under different scheduling algorithms, given the same initial energy. The variance of the lowest residue energy distribution could stand for the balance of energy consumption. Our approach is better than other approaches in balancing the whole network energy consumption.

Figure 14.

Ratio of energy consumption in each tracking times under different scheduling algorithms.

Figure 15.

Mean energy consumption at each tracking and network lifespan under different scheduling algorithms.

Figure 16.

Lowest normalized residual energy distribution during a tracking action and its variance under different scheduling algorithms.

To be specific, when the initial energy of each sensor node is 0.2 J, the mean energy consumption of the whole network at each tracking action is 0.65415 J in OCSA and slightly less than that in GBRHA, 0.66545 J. It is because that OCSA is based on the energy-efficient criterion whose aim is to minimize the energy consumption at each timestep. In contrast, to get a longer network lifespan, GBRHA may select nodes at the expense of more energy consumption. From Figure 15, we can obtain that the network lifespan of GBRHA is 13.03 which is longer than that of OCSA, 10. This is due to the fact that the energy consumption of the whole network is effectively balanced when using GBRHA, as shown in Figure 16. In terms of comparison among GBRHA, RHA, and EHA, although their performance is almost similar, GBRHA with a lower computation complexity( $O(({\Lambda }_L-N_{\min }{)}^2)$ ) is more suitable than RHA ( $O({\Lambda }_L^2)$ ) and EHA ( $O({\Lambda }_L^2\log {\Lambda }_L)$ ) for the target tracking in WSNs.

Conclusion and future work

In this article, we only consider a cluster-based single target-tracking scene where the cluster will dynamically change along with the moving target. At each timestep, some sensor nodes will be activated to compose a new cluster and other sensor nodes will stay asleep to save energy. An effective heuristic polynomial time algorithm is proposed to select the task node subset (cluster). We adopt an energy-balanced criterion to select the CH and other cluster nodes. Then, the energy-balance criterion is further formulated as a nonlinear multi-objective optimization problem solved by evaluation function method. Extensive simulations demonstrate that the proposed sensor scheduling schemes can not only maintain the preset tracking accuracy but also extend network lifespan with a lower computation complexity. In this article, we have not considered a specific Medium Access Control (MAC) protocol aimed at target-tracking scene in WSNs and only discuss the situation of a single moving target. Moreover, some problems such as boundary detection, losses of data packets, and recovery of the lost target are assumed out of the scope of this article. Therefore, these problems need to be discussed in the future.