Multitarget tracking in sensor networks via efficient information-theoretic sensor selection

Abstract

In networks composed of moving robots or static sensing nodes, multitarget tracking is critical and fundamental for high-level applications, such as scene analysis or event detection. However, tracking multiple targets in the sensor network is challenging for two reasons: multisensor multitarget fusion itself is difficult and dynamic sensor scheduling is necessary to balance the tracking accuracy and energy consumption of the sensor network. In this article, we present a novel information-theoretic sensor selection method for multitarget tracking via the multi-Bernoulli filter. The sensor selection is based on the multi-Bernoulli filtering and a collection of subselection problems for individual target to avoid the combinatorial optimization. A subselection problem for each target is investigated under the framework of partially observed Markov decision process, and we propose to solve it by maximizing the information gain of the probability hypothesis density. Simulation results validate the effectiveness and efficiency of our method for multitarget tracking in sensor networks.

Introduction

Sensor networks composed of moving robots or static sensing nodes have emerged as an interesting issue in various applications, such as military defense, scene analysis, and so forth. ^{1 –3} Multisensor multitarget tracking, as one of the most critical low-level techniques, is difficult in twofold: multisensor fusion approach for multitarget tracking is challenging due to data association uncertainty including sensor noise, false alarm, and miss detection ⁴ ; on the other hand, sensor scheduling is required to balance the tracking accuracy and energy consumption of the sensor network. ^5,6

Recent advance in random finite set (RFS)-based Bayesian framework has been an unified solution for multisensor multitarget tracking in conjunction with sensor management. It provides the probability hypothesis density (PHD), ⁷ cardinalized PHD (CPHD), ⁸ and multi-Bernoulli filter that can be easily implemented for multisensor multitarget tracking other than conventional approach joint probabilistic data association and multiple hypothesis tracking. On the other hand, given the multitarget posterior in filter recursion, sensor scheduling for multitarget tracking can be modeled as a partially observed Markov decision process (POMDP) ⁹ via finite set statistics (FISST). ¹⁰

In the literature, different objective functions were proposed for the POMDP-based sensor management, for example, the Kullback–Leibler discrimination, ⁹ posterior expected number of targets, ¹¹ the Rényi divergence ^,12 and the posterior cardinality. ¹³ However, no matter what objective function is used, POMDP-based sensor management is essentially a global combinatorial optimization problem that is extremely challenging especially when the sensor network is quite large, unless only one sensor is selected in use as illustrated in the study by Gostar et al. ¹⁴ A spatial nonmaximum suppression heuristics has been proposed recently to alleviate this issue, ¹⁵ whereas it suffers from a tuning parameter of the suppress gate. Ma et al. ¹⁶ proposed a suboptimal solution of the POMDP-based sensor control which is not suitable for sensor selection problem.

In this article, we consider the efficient sensor selection problem for multitarget tracking in sensor networks. The aim of this article is to select fewer sensors that still guarantee multitarget tracking performance. We adopt the sequential multi-Bernoulli filter as a centralized fusion scheme for multisensor multitarget tracking. ¹⁷ An efficient sensor selection approach is proposed via the decomposition of the global POMDP using individual Bernoulli components obtained from multi-Bernoulli filter. We name this framework as the decomposed POMDP. We propose to maximize the information gain between prior and posterior PHD function as an objective function for the decomposed POMDP. Numerical simulation results validate the efficiency and effectiveness of our approach.

The reminder of this article is organized as follows. “Bayesian multisensor multitarget tracking” section includes the multitarget tracking problem formulation in sensor networks, RFS-based Bayesian filtering, and the sequential multi-Bernoulli filter. In “Information-theoretic sensor selection approach” section, we propose the information-theoretic sensor selection approach based on the decomposed POMDP and present sensor selection algorithm in sequential Monte Carlo (SMC) implementation. “Simulation” section provides simulation results that verify the proposed approach.

Bayesian multisensor multitarget tracking

Problem formulation

Our approach addresses the general problem of multitarget tracking in sensor networks. A sensor network is composed of sensors with known locations available to sensing target in its field of view (FoV). All the sensing data need to be transmitted to the fusion center for information fusion in a centralized manner. We assume the sensor network is homogeneous which means that sensors are of the same type.

Without loss of generality, we consider a two-dimensional coordinate tracking scene with range and bearing sensors as a particular interest. Typically, the FoV for a range and bearing sensor is given by [−φ₀, +φ₀] × [0, d₀] in polar coordinate. Figure 1 illustrates the tracking scenario in a range and bearing sensor network with φ₀ = π/2. Notice that our approach can also handle the moving sensors scenario.

Figure 1.

Multitarget tracking in a range and bearing sensor network. Only four sensors can detect targets. Target 1 can be detected by two sensors.

As shown in Figure 1, only a small percentage of sensors can perceive targets while most sensors observe only clutter which is redundant for tracking. To alleviate communication bandwidth and computational cost, sensor selection is essential to choose a sensor subset that provides sufficient and minimal information for tracking purpose.

Assume that target motion model is the nearly constant velocity model ¹⁸ given by

$x_k=F{x}_{k-1}+G{v}_k$

1

where $x_k=[p_{x,k},v_{x,k},p_{y,k},v_{y,k}{]}^T$ ; $p_{x,k},p_{y,k},v_{x,k},v_{y,k}$ are position and velocity, respectively, along the x, y coordinate. $F=I_2\otimes \left[\begin{array}{cc}1& \Delta \\ 0& 1\end{array}\right]$ ; $G=I_2\otimes \left[\begin{array}{c}{\Delta }^2/2\\ \Delta \end{array}\right]$ . I₂ is 2 × 2 identity matrix, ⊗ is Kronecker product, Δ is the sampling period, and $v_k\sim \mathcal{N}(0,Q_k)$ is a 2 × 1 Gaussian noise.

Assume there are m sensors available in the sensor network, target with state x _k generates observation $z_k^l$ in sensor l(l = 1, ⋯, m) and the measurement model is given by

$z_k^l=h^l(x_k)+w^l$

2

where w^l is zero mean Gaussian noise $\mathcal{N}(w^l;0,R^l)$ and h^l(x _k ) is dependent on the position of the lth sensor $s_l={\left[x_l\cdot y_l\right]}^T$ and given by

$h^l(x_k)=\left[\begin{array}{c}\Vert p_k-s_l\Vert \\ \text{arctan}\frac{y_l-p_{y,k}}{x_l-p_{x,k}}\end{array}\right]$

3

where $\Vert p_k-s_l\Vert =\sqrt{{(x_l-p_{x,k})}^2+{(y_l-p_{y,k})}^2}$ . Measurement noise w^l is composed of range noise $w_d^l$ and bearing noise $w_{\phi }^l$ . The standard derivation of $w_d^l$ and $w_{\phi }^l$ are ${\mathit{\sigma }}_d^l$ and ${\mathit{\sigma }}_{\phi }^l$ , respectively, and $R^l=\text{diag}\left(\left[{\left({\mathit{\sigma }}_d^l\right)}^2,{\left({\mathit{\sigma }}_{\phi }^l\right)}^2\right]\right)$ .

RFS-based Bayesian filtering

Recently, the RFS-based Bayesian filtering offers an elegant solution to multitarget tracking that outperforms traditional vector representation. With different assumptions of the RFS form, the PHD, CPHD, and multi-Bernoulli filter are derived and widely used. Here, we give a brief description of the RFS-based Bayesian filtering framework. Let X_k and Z_k denote the multitarget state set and a sensor observation set with cardinalities N_k and W_k, respectively

$X_k=\left\{x_{k\mathrm{,1}},\cdots ,x_{k,N_k}\right\}$

4

$Z_k=\left\{z_{k\mathrm{,1}},\cdots ,z_{k,W_k}\right\}$

5

At time k, the prediction of the multitarget state RFS is X_k = S_k ∪ Γ_k, in which S_k is the RFS for persisting targets and Γ_k is the RFS for new born targets. The RFS for current measurements is Z_k = Θ_k ∪ K_k, in which Θ_k is for target-generated measurements and K_k is for clutter, respectively. Then, the RFS-based Bayesian recursion is given as follows

$f_{k|k-1}(X|Z_{1:k-1})={\displaystyle \int }{f}_{k|k-1}(X|X\text{'})f_{k-1}(X\text{'}|Z_{1:k-1})\delta X\text{'}$

6

$f_k(X|Z_{1:k})=\frac{f_k(Z_k|X)f_{k|k-1}(X|Z_{1:k-1})}{{\displaystyle \int }{f}_k(Z_k|X)f_{k|k-1}(X|Z_{1:k-1})\delta X}$

7

which represent the prediction and update process. Notice that the RFS-based Bayesian recursion is given by set integrals that solved via FISST ¹⁰ and thus results in different filters.

Sequential multi-Bernoulli filter

Assume that each target is modeled as a single Bernoulli set, r^(j) and p^(j) represent the existence probability and distribution of the jth Bernoulli set Ξ^(j), respectively, and then the multitarget state is a multi-Bernoulli RFS $\Xi ={\cup }_{j=1}^M{\Xi }^{(j)}$ , where M is the number of the Bernoulli sets. The PHD is propagated recursively in the multi-Bernoulli filter as approximations of the full posterior f(X|Z), ¹⁰ which is referred as “density” for short in the following content.

Due to the fact that the multi-Bernoulli filter is favorable for direct multitarget state extraction, we present the sequential multi-Bernoulli filter here as the multisensor fusion approach for multitarget tracking. ¹⁷ We first give the original “single-senor version” multi-Bernoulli filter and then present how the “multisensor version” works for better understanding. Remark that the state extraction convenience of the multi-Bernoulli filter is the key to the decomposed POMDP sensor selection in the following content.

Prediction: At time k, given the posterior multitarget density ${\pi }_k=\{(r_k^{(j)},p_k^{(j)}{)\}}_{j=1}^{M_k}$ , and the new births density ${\pi }_{\Gamma ,k+1}=\{(r_{\Gamma ,k+1}^{(j)},p_{\Gamma ,k+1}^{(j)}{)\}}_{j=1}^{M_{\Gamma ,k+1}}$ , then the predicted density is given by

${\pi }_{k+1|k}=\{(r_{k+1|k}^{(j)},p_{k+1|k}^{(j)}{)\}}_{j=1}^{M_k}\cup {\{(r_{\Gamma ,k+1}^{(j)},p_{\Gamma ,k+1}^{(j)})\}}_{j=1}^{M_{\Gamma ,k+1}}$

8

where for survival targets

$r_{k+1|k}^{(j)}=r_k^{(j)}\cdot 〈p_k^{(j)},p_{S,k}〉$

9

$p_{k+1|k}^{(j)}(x)=〈f_{k+1|k}(x|\cdot ),p_k^{(j)}{p}_{S,k}〉/〈p_k^{(j)},p_{S,k}〉$

10

and for new born targets, $r_{\Gamma ,k+1}^{(j)}\text{\hspace{0.17em}and\hspace{0.17em}}{p}_{\Gamma ,k+1}^{(j)}(x)$ are prior existence probability and distribution of birth model.

Update: At time k + 1, given the predicted multitarget density ${\pi }_{k+1|k}=\{(r_{k+1|k}^{(j)},p_{k+1|k}^{(j)}{)\}}_{j=1}^{M_{k+1|k}}$ , then the updated density is composed of legacy tracks and measurement-updated tracks

${\pi }_{k+1}=\{(r_{L,k+1}^{(j)},p_{L,k+1}^{(j)}{)\}}_{j=1}^{M_{k+1|k}}\cup {\{(r_{\mathcal{U},k+1}(z),p_{\mathcal{U},k+1}(\cdot |z))\}}_{z\in Z_k}$

11

where

$r_{L,k+1}^{(j)}=r_{k+1|k}^{(j)}\frac{1-〈p_{k+1|k}^{(j)},p_{D,k+1}〉}{1-r_{k+1|k}^{(j)}〈p_{k+1|k}^{(j)},p_{D,k+1}〉}$

12

$p_{L,k+1}^{(j)}(x)=p_{k+1|k}^{(j)}(x)\frac{1-p_{D,k+1}(x)}{1-〈p_{k+1|k}^{(j)},p_{D,k+1}〉}$

13

$r_{\mathcal{U},k+1}\left(z\right)=\frac{\sum _{j=1}^{M_{k+1|k}}\frac{r_{k+1|k}^{(j)}\left(1-r_{k+1|k}^{(j)}\right)〈p_{k+1|k}^{(j)},{\psi }_{k+1,z}〉}{{\left(1-r_{k+1|k}^{(j)}〈p_{k+1|k}^{\left(j\right)},p_{D,k+1}〉\right)}^2}}{{\kappa }_{k+1}\left(z\right)+\sum _{j=1}^{M_{k+1|k}}\frac{r_{k+1|k}^{\left(j\right)}〈p_{k+1|k}^{(j)},{\psi }_{k+1,z}〉}{1-r_{k+1|k}^{(j)}〈p_{k+1|k}^{(j)},p_{D,k+1}〉}}$

14

$p_{\mathcal{U},k+1}(z)=\frac{\sum _{M_{k+1|k}}^{j=1}\frac{r_{k+1|k}^{(j)}}{1-r_{k+1|k}^{(j)}}{p}_{k+1|k}^{(j)}(x){\psi }_{k+1,z}(x)}{\sum _{M_{k+1|k}}^{j=1}\frac{r_{k+1|k}^{(j)}}{1-r_{k+1|k}^{(j)}}〈p_{k+1|k}^{(j)},{\psi }_{k+1,z}〉}$

15

${\psi }_{k+1,z}(x)=g_{k+1}(z|x)p_{D,k+1}(x)$

16

p_S(⋅) and p_D(⋅) are probability of target survival and sensor detection, respectively. The inner product 〈⋅, ⋅〉 is defined on two real-valued functions β and γ by $〈\beta ,\mathit{\gamma }〉={\displaystyle \int }\beta (x)\mathit{\gamma }(x)\text{d}x$ .

Given the “single-senor version” multi-Bernoulli filter, we adopt sequential update fusion as a centralized scheme given in algorithm 1. In the prediction process of the sequential multi-Bernoulli filer, it predicts target state given dynamic model for the first sensor, and for any other sensors, it performs pseudopredict which treats the posterior from pervious time step as the prior right now. Then, the observations from each sensor are applied to update target state recursively. The SMC implementation details can be found in the study by Ma et al. ¹⁵ We refer the readers to the study by Ma et al. ¹⁷ for other alternative centralized schemes, such as parallel update and random update. Besides, the consensus approach can be applied in a distributed manner. ¹⁹

Information-theoretic sensor selection approach

In this section, we first illustrate global sensor selection in the framework of a POMDP in “POMDP-based global sensor selection” section. By incorporating multi-Bernoulli density into the global sensor selection, we propose a decomposed sensor selection approach for multitarget tracking in “Decomposed POMDP” section. “Information-theoretic objective function” section provides maximizing expected Rényi divergence between prior and posterior PHD as the objective function for proposed subselection scheme.

POMDP-based global sensor selection

A POMDP models an agent decision process in which the system dynamics are determined by a Markov decision process, but the agent cannot directly observe the underlying state. The POMDP framework has been used for planning under uncertainty in different applications, especially for robot navigation. Sensor management can be carried out in the framework of a POMDP which includes three key elements ¹² :

an information state represented by the multi-object posterior distribution;

an action belonging to a set of admissible actions; and

a reward function associated with different action.

We begin with the notations of using a POMDP as the solution for global sensor selection. At time k, let ${\mathcal{S}}_k\in {\Omega }_k$ denote selected sensor set, where Ω_k is the set of all possible sensor selection combinations. Define $\mathcal{D}(\mathcal{U},f,Z)$ as the objective function dependent on sensor set U, multitarget posterior f, and the associated measurement set Z if sensor set U was applied to selection.

At time k, the aim of sensor selection is to find the sensor subset S_k that maximizes/minimizes the statistical expectation of predefined objective function $\mathcal{D}(\mathcal{U},f,Z)$

${\mathcal{S}}_k=\text{arg}\underset{\mathcal{U}\in {\Omega }_k}{\text{max}(\text{min})}E[\mathcal{D}(\mathcal{U},f_{k-1}(X_{k-1}|Z_{0:k-1},{\mathcal{S}}_{0:k-1}),Z_k(\mathcal{U}))]$

17

where $f_{k-1}(X_{k-1}|Z_{0:k-1},{\mathcal{S}}_{0:k-1})$ represents the multitarget posterior after applying sensor selection sequence ${\mathcal{S}}_0,\cdots ,{\mathcal{S}}_{k-1}$ . Notice that the general formulation of POMDP is a p-step future decision process, whereas, in this article, we only consider a one-step future decision described as equation (17) for convenience.

Even though sensor selection issue can be described as a POMDP given by equation (17), it is still intractable to achieve the global optima of defined objective function since searching all possible sensor combinations is an NP-hard combinatorial optimization problem. ^20,21 Several heuristic techniques have been proposed to search for approximation of global optima. ^6,22,23 However, these methods are still time-consuming due to the nature of combinatorial searching and consequently difficult to perform real-time sensor selection for tracking. Hence, we propose a decomposed sensor selection method in the following which is computationally tractable and convenient to implement by taking advantage of the multi-Bernoulli filtering.

Decomposed POMDP

As mentioned in “Sequential multi-Bernoulli filter” section, multi-Bernoulli filter propagates multitarget density as approximation of multitarget full posterior to make Bayesian recursion tractable. ⁷ Hence, it is reasonable to substitute the multitarget posterior with multitarget density in equation (17), and we obtain

${\mathcal{S}}_k=\text{arg}\underset{\mathcal{U}\in {\Omega }_k}{\text{max}(\text{min})}E[\mathcal{D}(\mathcal{U},{\pi }_{k-1}(X_{k-1}|Z_{0:k-1},{\mathcal{S}}_{0:k-1}),Z_k(\mathcal{U}))]$

18

where ${\pi }_{k-1}(X_{k-1}|Z_{0:k-1},{\mathcal{S}}_{0:k-1})=\{(r_{k-1}^{(j)},p_{k-1}^{(j)}{)\}}_{j=1}^{M_{k-1}}$ in multi-Bernoulli filter. Given the multitarget density in multi-Bernoulli filter, we can obtain individual target density ${\pi }^j=\{(r^{(j)},p^{(j)})\}$ from the multitarget density and propose an efficient sensor selection approach based on the decomposed POMDP, that is, select sensors with respect to individual target and then merge into the total selection set given as follows

${\mathcal{S}}_k^{(j)}=\text{arg}\underset{\mathcal{U}\in {\Omega }_k}{\text{max}(\text{min})}E[\mathcal{D}(\mathcal{U},{\pi }_{k-1}^j(X_{k-1}|Z_{0:k-1},{\mathcal{S}}_{0:k-1}),Z_k(\mathcal{U}))]$

19

and

${\mathcal{S}}_k={\cup }_{j=1}^{M_k}{\mathcal{S}}_k^{(j)}$

20

where ${\pi }_{k-1}^j(X_{k-1}|Z_{0:k-1},{\mathcal{S}}_{0:k-1})=\{(r_{k-1}^{(j)},p_{k-1}^{(j)})\}$ and ${\mathcal{S}}_k^{(j)}$ is the selected sensor set with respect to the density of target j. Notice that this decomposition is straightforward since the state extraction is direct in the multi-Bernoulli filter, and this accounts for the choice of the multi-Bernoulli filter.

Remark that the decomposed POMDP-based sensor selection given by equations (19) and (20) selects sensors with respect to subgoals dependent on individual target density instead of a global goal dependent on multitarget density as described in equation (18). However, for any two selection subsets ${\mathcal{S}}_k^{(i)}$ and ${\mathcal{S}}_k^{(j)}$ (i ≠ j), sensors may be selected repeatedly if targets i and j come across.

To alleviate communication bandwidth and computational cost, ${\mathcal{S}}_k^{(j)}$ should contain the minimum number of sensors to track each individual target. In this article, ${\mathcal{S}}_k^{(j)}$ is set to be singleton since one range and bearing sensor is adequate to resolve a target. Therefore, the computation complexity of our decomposed sensor selection approach is $\mathcal{O}(M\cdot m)$ which is much smaller than $\mathcal{O}{(2}^m)$ by searching all sensor selection combinations in large-scale sensor network. Regarding less informative sensor type that requires q sensors to resolve a target, the computation complexity of the decomposed sensor selection increases to $\mathcal{O}\left(M\cdot \left(\begin{array}{c}m\\ q\end{array}\right)\right)$ with $\left(\begin{array}{c}m\\ q\end{array}\right)=\frac{m!}{q!(m-q)!}$ . Existing searching heuristics ⁶ can be applied in searching ${\mathcal{S}}_k^{(j)}$ to further reduce the computational cost.

Information-theoretic objective function

As mentioned above, the objective function plays a crucial role in POMDP-based sensor selection problem. Information theoretic method is a typical objective function for sensor scheduling. Here, we propose to maximize the information gain of PHD as the subgoal of decomposed sensor selection, which is the product of existence probability and state distribution given in the study by Mahler ¹⁰ as follows

${\mathit{\pi }}_k^{(j)}=r_k^{(j)}\cdot p_k^{(j)}$

21

for Bernoulli set $\{r_k^{(j)},p_k^{(j)}\}$ . Notice that the density is the product of a scalar and a probability distribution. The Rényi divergence, also known as alpha divergence, measures the information gain between any two probability densities. Hence, the objective function for target j with respect to sensor l is given as follows

${\mathcal{D}}_{k+1}^{(j),l}=\frac{r_{k+1}^{(j),l}}{r_{k+1|k}^{(j)}}{\mathcal{R}}^l(p_{k+1}^{(j),l}||p_{k+1|k}^{(j)})$

22

where ${\mathcal{R}}^l(p_{k+1}^{(j),l}||p_{k+1|k}^{(j)})$ is the Rényi divergence between the prior and posterior distribution of target j denoted by ${\mathcal{R}}^{(j),l}$ for short. Given the Bayesian recursion, ${\mathcal{R}}^{(j),l}$ is given in the study by Ristic and Vo ¹² as follows

${\mathcal{R}}^{(j),l}=\frac{1}{\alpha -1}\text{log}\frac{{\displaystyle \int }{[g_{k+1}^l(z|x_{k+1}^{(j)})]}^{\alpha }{p}_{k+1|k}^{(j)}(x)d{x}_{k+1}^{(j)}}{{[p(z|Z_k)]}^{\alpha }}$

23

where $p(z|Z_k)={\displaystyle \int }{g}_{k+1}^l(z|x_{k+1}^{(j)})p_{k+1|k}^{(j)}(x)d{x}_{k+1}^{(j)}$ and α is a parameter that determines how much we emphasize the tails of two density in the metric. The Rényi divergence becomes the Kullback–Leibler discrimination and Hellinger affinity, respectively, when α → 1 and α = 0.5. ²⁴ To compute the expectation of equation (22), we only generate one future measurement z for sensor l based on the predicted state assuming no clutter and unity detection rate as illustrated in the study by Gia Hoang and Vo ¹³ and $r_{k+1}^{(j),l}=r_{\mathcal{U},k+1}^{(j),l}(z)$ for unity detection rate.

To introduce the SMC implementation of the objective function, we assume that at time k, the predicted multitarget density ${\pi }_{k+1|k}=\{r_{k+1|k}^{(j)},p_{k+1|k}^{(j)}{\}}_{j=1}^{M_{k+1|k}}$ is given in SMC form where $p_{k+1|k}^{(j)}(x)={\displaystyle {\sum }_{i=1}^{L_{k+1|k}^{(j)}}}{\omega }_{i,k+1|k}^{(j)}\cdot {\delta }_{x_{i,k+1|k}^{(j)}}(x)$ . Substitute SMC form of $p_{k+1|k}^{(j)}(x)$ into equation (23), then we obtain

$E[{\mathcal{D}}_{k+1}^{(j),l}]=\frac{r_{\mathcal{U},k+1}^{(j),l}(z)}{(\alpha -1)r_{k+1|k}^{(j)}}\text{log}\frac{{\displaystyle {\sum }_{i=1}^{L_{k+1|k}^{(j)}}{\omega }_{i,k+1|k}^{\left(j\right)}{[g_{k+1}^l(z|x_{k+1}^{(j)})]}^{\alpha }}}{[{\displaystyle {\sum }_{i=1}^{L_{k+1|k}^{(j)}}{\omega }_{i,k+1|k}^{(j)}{g}_{k+1}^l(z|x_{k+1}^{(j)}{)]}^{\alpha }}}$

24

Remark that equation (24) is the same with the “individual hypothesis information gain” in the study by Ma et al., ¹⁵ whereas the underlying rationale of sensor selection is different. In the study by Ma et al., ¹⁵ noninformative sensors are eliminated by spatial suppression while redundant sensors are selected for update. On the other hand, the decomposed POMDP-based approach only selects minimal number of sensors for tracking. Therefore, the decomposed POMDP-based sensor selection is more general and suitable for large-scale sensor networks.

Assume the sensor network contains m candidate sensors with fixed and known position s ^l (l = 1, ⋯, m), then algorithm 2 provides the SMC implementation of sensor selection by maximizing proposed objective function. At each time step, given the prior individual target state, we predict the measurement for each sensor and then compute the expected information gain $E[{\mathcal{D}}_{k+1}^{(j),l}]$ given by equation (24). Hence, we can select a subset for each individual target that contains more information, then these subsets are merged together to form the overall sensor selection set. The unique() function eliminates repeatedly chosen sensor afterwards in order to ensure each sensor will only be update once during information fusion process.

Simulation

In this section, we present numerical results for a multitarget tracking scenario in sensor networks, in which 9 × 9 sensors laid out uniformly over a square of size (−1000 m, 1000 m) × (−1000 m, 1000 m) divided into 200 × 200 m² blocks. There are unknown and time-varying number of targets observed in clutter while range and bearing measurements from each sensor are available.

The FoV of each node is (−π, 0) × (0, 300 m) with clutter uniformly distributed over this interval. The clutter rate of each sensor node is λ^c = 5 per scan. The probability of detection is modeled by

$p_D^l(x_k)=\{\begin{array}{cc}0.99& \Vert p_k-s_l\Vert \le R_1\\ 0.99-c\Vert p_k-s_l\Vert & R_1<\Vert p_k-s_l\Vert \le R_2\\ 0& \Vert p_k-s_l\Vert >R_2\end{array}$

25

with R₁ = 100 m, R₂ = 300 m, and c = 0.002 m⁻¹. The covariance of measurement noise for sensor l at time k is $R_k^l=\text{diag}([({\mathit{\sigma }}_{d,k}^l{)}^2,({\mathit{\sigma }}_{\phi ,k}^l{)}^2])$ , where

${\mathit{\sigma }}_{d,k}^l={\mathit{\sigma }}_0+{\beta }_d{\Vert p_k-s_l\Vert }^2$

${\mathit{\sigma }}_{\phi ,k}^l={\mathit{\sigma }}_1+{\beta }_{\phi }\Vert p_k-s_l\Vert$

with σ₀ = 1 m, β_d = 5 × 10⁻⁵ m⁻¹, σ₁ = π/180 rad, and β_φ = 10⁻⁵ rad ⋅ m⁻¹.

Targets can appear or disappear in the scene at any time and survival probability p_S = 0.95 for each existing target. New born targets appear spontaneously according to ${\mathit{\gamma }}_k=0.2\mathcal{N}(\cdot ;\overline{x},Q)$ . The tracker, composed of decomposed sensor selection and multisensor multi-Bernoulli filter, runs for 50 scans with sampling period Δ = 1 s. Each target moves according to the constant velocity model given by equation (1). The standard derivation of process noise is σ_v = 1 m/s for both v_x,k and v_y,k. Three targets are presented as illustrated in Figure 2. The coverage of the sensor network is shown in Figure 3.

Figure 2.

Target tracks. Start/stop positions for each track are shown with •/+.

Figure 3.

The yellow area represents the FoV of each sensing node. FoV: field of view.

Birth parameters for the multi-Bernoulli filter are prior locations with ${\overline{x}}_1=[200\text{\hspace{0.17em}m};-10\text{\hspace{0.17em}m/s};600\text{\hspace{0.17em}m};-20\text{\hspace{0.17em}m/s}{]}^T$ , ${\overline{x}}_2=[-300\text{\hspace{0.17em}m};15\text{\hspace{0.17em}m/s};200\text{\hspace{0.17em}m};-10\text{\hspace{0.17em}m/s}{]}^T$ , and ${\overline{x}}_3=[-850\text{\hspace{0.17em}m};25\text{\hspace{0.17em}m/s};-450\text{\hspace{0.17em}m};5\text{\hspace{0.17em}m/s}{]}^T$ , respectively, for each location, and Q = diag([(50 m, 2 m/s, 50 m, 2 m/s)]²) is identical for all three locations. L_min = 300 and L_max = 500 are the minimum and maximum particle number of each Bernoulli set for track maintenance.

We first illustrate the decomposed sensor selection and multisensor multitarget tracking procedure. Three consecutive tracking frames in one run are presented in Figure 4. All three figures contain more than three sensors selected while there are only three real targets. This is because, in multi-Bernoulli filter sets, Bernoulli filter sets for existing targets only occupies part of all Bernoulli sets. There are birth sets for new born targets and legacy sets for temporally undetected targets as well. As shown in Figure 4, there are always selected sensors standing by for birth sets. Besides, the legacy sets account for that the multi-Bernoulli filter lost target 1 in Figure 4(b) and picked it up later as shown in Figure 4(c).

Figure 4.

Consecutive tracking frames. Blue and red dots, respectively, stand for sensors that targets fall off and in sensor’s FoV, blue line and ∘ for target track and current position, W for selected sensor, and red ∗ for target estimation. FoV: field of view. (a) Time k = 22. (b) Time k = 23. (c) Time k = 24.

Since the nearest neighboring strategy has been widely used in sensor selection, we implement minimum expected distance as another objective function for comparison. Moreover, we also compare the two spatial nonmaximum suppression selection method described in the study by Ma et al. ¹⁵ with gate ε = 500 m, referred as “sum HIG” suppression and “individual HIG” suppression, respectively. It is intuitive for this scenario that to select the proper sensor with respect to a target should choose the nearest sensor that target falls in its FoV.

The optimal subpattern assignment (OSPA) metric, composed of location error and cardinality error, is adopted for multitarget tracking performance evaluation. ²⁵ The OSPA metric can be computed efficiently using the Hungarian method for optimal point assignment between two point patterns. We refer the readers of “Information-theoretic sensor selection approach” section in the study by Schuhmacher et al. ²⁵ for equations and parameter explanations of the OSPA metric.

Figure 5 shows the OSPA distance (c = 300 m, p = 1) comparison from 500 Monte Carlo runs. It is obvious that the proposed tracker with maximizing the expected information gain of PHD has similar performance with “individual HIG” suppression approach, which outweighs nearest neighboring strategy and “sum HIG” suppression. Our decomposed selection with maximizing the PHD can choose proper sensors to perform effective multitarget tracking. However, the nearest neighboring strategy ignores sensor’s FoV and may choose sensors cannot observe targets instead. With respect to the suppression method, the performance of both “sum HIG” and “individual HIG” relies on the tuning of parameter gate ε. In this case, ε = 500 m makes the “sum HIG” suppression cannot select enough sensors and leads to inferior tracking performance.

Figure 5.

Comparison of OSPA distance. OSPA: optimal subpattern assignment.

The comparison concerning total particle number and computation time from 500 Monte Carlo runs is demonstrated in Figure 6. Both trackers were implemented in MATLAB R2012a on a computer with an Intel Core E5500 CPU and 2 GB of RAM. It is clear that the computation time of both trackers is acceptable for an actual fusion center to perform centralized multisensor multitarget tracking in real time. Nevertheless, the “individual HIG” suppression method with ε = 500 m is slower since redundant sensors are selected in use for multisensor sequential update. The sample size of nearest neighboring strategy and “sum HIG” suppression is much larger because “ghost” particles are maintained in multisensor multi-Bernoulli filter when sensors that cannot observe targets are selected frequently. On the other hand, maximizing the PHD and “individual HIG” suppression can eliminate “ghost” particles quickly by selecting proper sensors.

Figure 6.

Comparison of sample size and computation time.

To summarize, suppression gate ε is critical for the suppression selection method. If the suppression gate ε is not set properly, the spatial nonmaximum suppression selection method may leads to very poor tracking performance or selecting too much sensors. On the other hand, the proposed information-theoretic sensor selection approach based on decomposed POMDP can provide sufficient and minimal information for multitarget tracking.

Conclusion

This article outlines a novel suboptimal sensor selection approach for individual target to avoid combinatorial search over all sensor combinations by global POMDP decomposition. The multisensor multitarget tracking is performed using the sequential multi-Bernoulli filter in SMC implementation. The implementation of proposed decomposed sensor selection is based on maximizing the information gain of the PHD. Simulation results demonstrate that the proposed approach is capable of effective multitarget tracking via efficient sensor selection.

There are some potential extensions of this work. For example, the performance of our approach needs to be further evaluated compared with searching for global optima method, which requires further research on heuristic searching techniques. Besides, for practical sensor network that is composed of heterogeneous sensors of different types, the selection ${\mathcal{S}}_k^{(j)}$ for each target should be dynamically determined with respect to available sensor type.