Sensor Mobility Control for Multitarget Tracking in Mobile Sensor Networks

Abstract

In emerging tracking systems using mobile wireless sensor networks, sensor mobility management is essential for balancing the tracking performance and costs under limited network resources and sensor movements. This paper considers the sensor mobility control problem for multitarget tracking (MTT), in which multiple mobile sensors are dynamically grouped and moved to track multiple targets and collaborate within each sensor group via track data fusion. A novel sensor mobility control framework for the mobile sensor network-based MTT is proposed. It is formulated as a constrained optimization problem that aims to maximize the overall tracking performance for all targets while conserving network energy and providing tracking coverage guarantee. The optimization problem is relaxed as a convex programming problem for computational tractability and its solution is implemented in a distributed manner. The newly proposed sensor mobility control scheme, implemented on the basis of iterative subgradient search, is shown via computer simulation to have better performance over the static sensor network-based MTT.

1. Introduction

Target tracking is one of the key enabling techniques of wireless sensor networks in a variety of applications including security and surveillance, traffic management, wild animals tracking, and environmental monitoring [1–8]. In some applications, such as warehouse management and security, mobile sensors would be more efficient and flexible than fixed ones [9–11]. The use of a few mobile sensors would be sufficient for monitoring an area of interest and the deployment of a large number of static sensor nodes is no longer needed. We will consider in this paper tracking multiple targets using a network of wireless sensors that are mobile.

The use of mobile sensor network introduces new challenges in obtaining satisfactory performance for multitarget tracking (MTT). Among them, we will focus on the problem of sensor mobility control that arises mainly due to the mobility and the autonomous nature of sensors. For example, a sensor node may choose to move towards a certain target so as to attain target signal measurements with higher signal-to-noise ratio (SNR) and improve the tracking accuracy. However, this decision could enlarge the distances between the sensor and other targets and, as a result, degrade the overall MTT performance. On the other hand, several sensors may track the same target and, to enhance performance, it would be desirable to fuse their target signal measurements. The usefulness of this technique is nevertheless complicated by the fact that, in some applications, the number of targets that can be simultaneously tracked by a mobile sensor is limited due to, for example, the insufficient on-board resources for computation, sensing, and communications. Therefore, an efficient sensor mobility control scheme that can optimally schedule the movement of the mobile sensors and allocate them for tracking different targets would be crucial for MTT with mobile sensor networks.

We will develop in this paper a novel sensor mobility control framework for a mobile sensor network-based MTT system, where each sensor node is able to measure the time of arrival (TOA) and the direction of arrival (DOA) of the target signals. Obtaining both TOA and DOA measurements ensures that each mobile sensor can determine the target location individually, as compared to the systems where only range or angle measurements are available. The proposed sensor mobility control scheme jointly specifies the moving trajectories of the mobile sensors and forms groups of sensors for tracking different targets in an optimum manner. The sensor movement scheduling impacts the MTT tracking performance by changing the relative locations of the targets with respect to the sensors and thus affecting the noise level of the target TOA and DOA measurements. The sensor allocation enables the application of data fusion techniques to obtain improved target trajectory estimation. The combined effect of the above two functions of the developed sensor mobility control scheme is to maximize the MTT performance.

The development of the sensor mobility control scheme is nontrivial. The underlying reason is that the sensor allocation is indeed a multidimensional integer programming problem and finding the solution is still an open problem. In the existing literature, greedy algorithms, heuristic searching, divide-and-conquer method, or grid-based exhaustive searching was most widely tried. However, these algorithms have very high computational complexity, which hinders their practical applications. Moreover, some techniques, such as the greedy and heuristic searching, may not always yield the globally optimal solution (i.e., they suffer from local convergence). In this paper, the primal-dual approach and the subgradient searching algorithm are applied to solve for the optimal sensor movement and sensor allocation in the sensor mobility control for MTT with mobile sensors. The proposed solution can be realized in a centralized or distributed manner and its complexity increases linearly with the number of mobile nodes and targets, which makes it attractive for practical deployment.

The rest of the paper is organized as follows. Section 2 surveys the literature related to our work and highlights the contributions of this paper. Section 3 presents in detail the considered mobile sensor network-based MTT system and Section 4 formulates the sensor mobility control as an optimization problem. Iterative solution for the sensor mobility control problem on the basis of the subgradient searching technique is developed in Section 5 and its distributed implementation is given in Section 6. Section 7 illustrates the performance of the proposed sensor mobility control scheme using computer simulations. We conclude our work in Section 8.

2. Related Work

Target tracking with wireless sensor networks is a classic problem that has been extensively studied in the literature. In particular, in single target tracking, significant efforts have been spent on grouping and scheduling stationary sensors for achieving the optimum tracking performance [12–16]. For the more general case where there exist more than one target of interest, the problem of sensor allocation has also been investigated under various optimization criteria and several centralized sensor allocation schemes have been proposed [17–22].

Relatively less attention has been paid to the problem of sensor mobility control that consists of sensor movement scheduling and sensor allocation for target tracking with mobile sensor networks. Within the single target tracking framework, the sensor movement scheduling was considered in [23, 24]. More specifically, in [23], the authors studied the range-only tracking and proposed a centralized sensor movement scheduling method for minimizing the trace of the covariance matrix of the target position estimate, or, equivalently, the localization mean square error (MSE). The minimization problem was solved using the modified Gauss-Seidel and linear programming relaxations. This work, nevertheless, did not take into account the sensor allocation aspect. Reference [24] determines the sensor movement by partitioning the field of interest into grids of equal area and performing grid-based exhaustive search. The associated computational complexity can be prohibitive when the region to be monitored is large. References [25, 26] considered the adaptive flocking of static sensors with limited sensing range (LSR) and the grouping of mobile sensors for tracking a single maneuvering target via the Kalman-consensus filter (KCF). The sensor grouping was based on the metric of Fisher information. For the MTT scenario, [1] proposed a greedy algorithm for sensor allocation and sensor movement scheduling to minimize the capturing time for target tracking. Reference [27] investigated collaborative prediction among mobile sensors with limited communication connectivity for improving the prediction of spatial-temporal physical phenomena using truncated measurements. The sensor navigation scheme was established via solving an optimization problem that aims at minimizing the prediction variance.

This paper is a significant extension of the authors’ previous work [28], where accurate target identification and the use of static sensor networks were assumed. We will consider the MTT problem with mobile sensor networks here and we continue to assume perfect data association as in [28]. Our work differs greatly from other literatures in the following aspects. Firstly, we propose a generic framework for sensor mobility control in an MTT system where a sensor node is allowed to track multiple targets simultaneously and each target can be tracked by several sensor nodes, thus enabling data fusion for improved performance. Secondly, the sensor movement scheduling and the sensor allocation within the sensor mobility control are determined jointly for obtaining the optimum tracking performance under practical system constraints. Finally, we apply the linear programming relaxation and the subgradient searching technique to solve for the desired sensor mobility control scheme.

3. System Model

We consider tracking multiple moving targets with a network of wireless mobile sensors. It is assumed that the sensor nodes have sufficient sensing and wireless communication capabilities so that they are able to keep monitoring the whole region of interest and maintain their intersensor communication connections. The sensor node positions are known from the use of network self-calibration techniques such as the one in [29] or built-in GPS units. We further assume that the mobile sensor nodes can move freely within the monitored area.

Each sensor node is allowed to track either a single target or multiple targets, and it can collaborate with other sensors through track fusion to estimate the position of the same target with better accuracy. The mobility of the sensor nodes together with their freedom to select the targets to track give rise to the problem of sensor mobility control investigated in this work. In particular, we will consider the problem of joint sensor allocation and sensor movement scheduling for attaining optimal MTT performance. The distributed implementation of the proposed solution to the above problem will also be presented.

Within the mobile sensor network, each sensor node is configured by a multilayer target tracking system, which was originally developed for wireless local positioning system for remote mobile monitoring [28]. It consists of five functional modules intertwined in a hierarchical manner with each module focusing on one designated task [28, 30]. They are termed as the sensing, the sensor mobility control, the target measurement collection, the MTT, and the information relay modules. The MTT task during each sampling interval is performed as follows. The sensing module at a sensor detects the targets by measuring the received SNRs. The sensor mobility control module dynamically decides which targets to track and the location the sensor node should move to. Upon the arrival at the new position, the target measurement collection module is triggered to obtain target position-related measurements, namely, the time of arrivals (TOAs) and the direction of arrivals (DOAs) of the target signals. Afterward, the tracking and fusion module steps in, where a tracking algorithm, a Kalman filter (KF) in this paper, is executed to fuse the measurements from a target possibly collected by a number of sensor nodes to update the estimates of the target motion parameters such as its position and velocity as in [1]. The function of the information relay module is to pass on necessary information to other sensor nodes if the current node quits the tracking of specific targets. The above multilayer tracking system will be further elaborated in Table 1.

Table 1

Distributed implementation of the proposed sensor mobility control scheme.

At time t:  ${\left\{{\widehat{\mathit{u}}}_j\left(t-\mathrm{1}\mid t-\mathrm{1}\right),{\mathit{Y}}_j\left(t-\mathrm{1}\mid t-\mathrm{1}\right)\right\}}_{j=\mathrm{1}}^{N_t}$ have been obtained by the mobile sensor network.
Sensing module
Each sensor detects targets based on the received SNR
Sensor mobility control module
Initialization
At $k=\mathrm{0}$ , for sensor i, $i=\mathrm{1},\dots ,N_s$
(i) Initialize with $a_{ij}^{(\mathrm{0})}(t)=\mathrm{0}$ , $j=\mathrm{1},\dots ,N_t$ , $l_i^{(\mathrm{0})}=\mathrm{0}$ , $m_i^{(\mathrm{0})}=\mathrm{0}$ , ${\sigma }_j^{(\mathrm{0})}=\mathrm{0},\mathrm{\hspace{0.17em}\hspace{0.17em}}j=\mathrm{1},\dots ,N_t$ , and ${\mathit{s}}_i^{(\mathrm{0})}(t)={\mathit{s}}_i(t-\mathrm{1})$
(ii) Predict ${\mathbf{Y}}_j\left(t\mid t-\mathrm{1}\right)$ from (4a)
Iteration:    do $k\to k+\mathrm{1}$
For sensor i,
(i) Compute and broadcast CRLB matrices ${\widehat{\mathit{M}}}_{ij}\left(t\mid t-\mathrm{1}\right)$ as a function of the sensor locations ${\mathit{s}}_i^{(k)}(t)$           and the target location estimates given by ${\widehat{\mathit{u}}}_j\left(t\mid t-\mathrm{1}\right)={\mathit{A}}_j\left(t\right)\hspace{0.17em}{\widehat{\mathit{u}}}_j\left(t-\mathrm{1}\mid t-\mathrm{1}\right)$ , $j=\mathrm{1},\dots ,N_t$ ;
(ii) Compute $c_{ij}$ , $\mathrm{\Gamma }$ , $\mathrm{\Lambda }$ , and ${\varphi }_{ij}$ for Case 1 or $p_{ij}$ , $\tilde{\mathrm{\Gamma }}$ , $\tilde{\mathrm{\Lambda }}$ , and ${\psi }_{ij}$ for Case 3;
(iii) Compute $\{a_{ij}^{(k+\mathrm{1})}(t)\}$ , $l_i^{(k+\mathrm{1})}$ , $m_i^{(k+\mathrm{1})}$ , and $\{{\sigma }_j^{(k+\mathrm{1})}\}$ using (15a), (15b), (15c), (15d), and (15e) for Case 1 or          using (22a), (22b), (22c), (22d), (22e), and (22f) for Case 3;
(iv) Broadcast $\{a_{ij}^{(k+\mathrm{1})}(t)\}$ and ${\mathit{s}}_i^{(k+\mathrm{1})}(t)$ to other nodes for both Cases 1 and 3;
End for sensor i
End k at $k=K$ when ${{\displaystyle \sum }}_j\mathrm{‍}|a_{ij}^{(K)}(t)-a_{ij}^{(K-\mathrm{1})}(t)|\le {ϵ}_{\text{th}}$ or $K=K_{\max }$ ;
Decision
Generate sensor allocation decisions $a_{ij}^{\mathrm{*}}(t)=\text{round\hspace{0.17em}}(a_{ij}^{(K)}(t))$ , $i=\mathrm{1},\dots ,N_s,\mathrm{\hspace{0.17em}\hspace{0.17em}}j=\mathrm{1},\dots ,N_t$ , and form       the sensor groups $S_j(t)=\{\forall i:a_{ij}^{\mathrm{*}}(t)=\mathrm{1}\}$ , $\forall j\in [\mathrm{1},N_t]$ .
Measurement collection module
For sensor i, collect the TOA and DOA measurements $({\tau }_{ij}(t),{\theta }_{ij}(t))$ from the allocated target j with          $a_{ij}^{\mathrm{*}}(t)=\mathrm{1}$ , and compute the position estimates ${\mathbf{z}}_{ij}(t)=[{\tilde{x}}_{ij}(t),{\tilde{y}}_{ij}(t){]}^T$ using (2a) and (2b).
Track fusion module
Update the target state vector estimates and the associated covariance matrices ${\widehat{\mathbf{y}}}_j\left(t\mid t\right)$ and ${\mathbf{Y}}_j\left(t\mid t\right)$ ,           $j=\mathrm{1},\dots ,N_t$ , using the information form of the KF given in (4a), (4b), (4c), and (4d).

In the rest of this section, we will present the Kalman filtering algorithm adopted in the tracking and fusion module. The purpose is to introduce the relating symbols and notations in order to facilitate the development of the distributed sensor mobility control scheme in the next section.

3.1. Kalman Tracking

Suppose that the mobile sensor network has $N_s$ sensor nodes and there are in total $N_t$ targets, where $N_t\ge \mathrm{1}$ . We will focus on the 2D tracking scenario for ease of the presentation. The extension to the more general 3D case would be straightforward. The state vector of target j, $j=\mathrm{1},\dots ,N_t$ , at time index t is ${\mathbf{u}}_j(t)=[x_j(t),y_j(t),{\dot{x}}_j(t),{\dot{y}}_j(t){]}^T$ , where $[x_j(t),y_j(t){]}^t$ and $[{\dot{x}}_j(t),{\dot{y}}_j(t){]}^T$ are the target position and velocity at time index t. The temporal evolution of the target state vector is modeled as the following first-order discrete-time Markov process:

$$\begin{array}{cc}& {\mathbf{u}}_j\left(t\right)={\mathbf{A}}_j\left(t\right){\mathbf{u}}_j\left(t-\mathrm{1}\right)+{\mathbf{C}}_j\left(t\right){\mathbf{v}}_j\left(t\right),\end{array}$$

(1)

where ${\mathbf{A}}_j(t)$ is the transition matrix and ${\mathbf{v}}_j(t)$ is the Gaussian system noise with zero mean and covariance ${\mathbf{Q}}_j(t)$ .

Let $S_j(t)$ be the set of sensor nodes whose sensor mobility control modules decide that they would collaboratively track target j at time index t. Suppose that sensor i belongs to $S_j(t)$ . Therefore, its sensing module extracts the TOA and DOA from the signals of the jth target. We will denote them as $r_{ij}(t)$ and ${\theta }_{ij}(t)$ . The target position at time index t, ${\mathit{z}}_{ij}(t)=[{\tilde{x}}_{ij}(t),{\tilde{y}}_{ij}(t){]}^T$ , can be estimated at sensor i using

$$\begin{array}{cc}& {\tilde{x}}_{ij}\left(t\right)=s_{x,i}\left(t\right)+r_{ij}\left(t\right)\cos \left({\theta }_{ij}\left(t\right)\right),\end{array}$$

(2a)

$$\begin{array}{cc}& {\tilde{y}}_{ij}\left(t\right)=s_{y,i}\left(t\right)+r_{ij}\left(t\right)\sin \left({\theta }_{ij}\left(t\right)\right),\end{array}$$

(2b)

where ${\mathbf{s}}_i(t)=[s_{x,i}(t),s_{y,i}(t){]}^T$ is the position of sensor i at time index t that is determined by the sensor mobility control module. The above transformation has been shown to be unbiased and consistent under some mild conditions that can be satisfied in many practical scenarios [30, 31]. The measurement vector ${\mathit{z}}_{ij}(t)$ is related to the target state vector ${\mathbf{u}}_j(t)$ via

$$\begin{array}{cc}& {\mathbf{z}}_{ij}\left(t\right)={\mathbf{H}}_{ij}\left(t\right){\mathbf{u}}_j\left(t\right)+{\mathbf{w}}_{ij}\left(t\right),\end{array}$$

(3)

where ${\mathbf{H}}_{ij}(t)=[{\mathbf{I}}_{\mathrm{2}\times \mathrm{2}},{\mathbf{O}}_{\mathrm{2}\times \mathrm{2}}]$ and ${\mathbf{w}}_{ij}(t)$ is the measurement noise independent of the system noise ${\mathbf{v}}_j(t)$ . The linearity in the target motion model (1) as well as the measurement model (3) enables the direct application of the classic KF in track fusion. It is worthwhile to point out that, when the target position-related measurements are nonlinearly related to the target state vector such as in bearing-only tracking (BOT), the proposed sensor mobility control scheme is still applicable, as long as we convert the nonlinear measurement equation into a linear one using first-order Taylor series expansion. This is equivalent to the utilization of the extended Kalman filter (EKF) but cautions must be taken because the EKF has potential of introducing unmodeled errors [30].

In the target motion model (1), the process noise ${\mathbf{v}}_j(t)$ has a covariance matrix ${\mathbf{Q}}_j(t)$ that is typically assumed to be time invariant and known a priori. On the other hand, the measurement noise ${\mathbf{w}}_{ij}(t)$ , despite its zero mean and Gaussianity, has a covariance matrix ${\mathbf{R}}_{ij}(t)$ that is time varying. This is mainly because it is dependent on the received SNR as well as the relative positions of the target and the mobile sensor node. Out of the unbiasedness and efficiency of the transformations (2a) and (2b), we choose the Cramer-Rao Lower Bound (CRLB) of the measurement noise as the functional form for ${\mathbf{R}}_{ij}(t)$ in the development of the sensor mobility control scheme. In fact, the CRLB of ${\mathbf{R}}_{ij}(t)$ , denoted as ${\mathbf{M}}_{ij}(t)$ , has been derived in [32].

After obtaining the current measurement vector ${\mathbf{z}}_{ij}(t)$ , Kalman filtering is performed to update the estimate of the target state vector. We will summarize the necessary processing for the completeness of this paper. Let ${\widehat{\mathbf{u}}}_j(t-\mathrm{1}\mid t-\mathrm{1})$ be the a priori state estimate for target j at time index $t-\mathrm{1}$ and ${\widehat{\mathbf{u}}}_j(t\mid t)$ the a posteriori state estimate at time index t. Correspondingly, their error covariance matrices are ${\mathbf{P}}_j(t-\mathrm{1}\mid t-\mathrm{1})$ and ${\mathbf{P}}_j(t\mid t)$ , respectively. We adopt an information form of KF for track fusion in order to facilitate the development of the sensor mobility control scheme. The state vector estimate ${\widehat{\mathbf{u}}}_j(t\mid t)$ and its error covariance matrix ${\mathbf{P}}_j(t\mid t)$ are transformed into the information state vector ${\widehat{\mathbf{y}}}_j(t\mid t)={\mathbf{P}}_j^{-\mathrm{1}}(t\mid t){\widehat{\mathbf{u}}}_j(t\mid t)$ and the information matrix ${\mathbf{Y}}_j(t\mid t)={\mathbf{P}}_j^{-\mathrm{1}}(t\mid t)$ . Obtaining ${\widehat{\mathbf{y}}}_j(t\mid t)$ and ${\mathbf{Y}}_j(t\mid t)$ requires evaluating the following in sequence [30, 33]:

$$\begin{array}{l}\text{prediction:}\hspace{0.17em}\\ \hspace{1em}{\mathbf{Y}}_j^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}={\mathbf{A}}_j\left(t\right){\mathbf{Y}}_j^{-\mathrm{1}}\left(t-\mathrm{1}\mid t-\mathrm{1}\right){\mathbf{A}}_j^T\left(t\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\mathbf{C}}_j\left(t\right){\mathbf{Q}}_j\left(t\right){\mathbf{C}}_j^T\left(t\right),\end{array}$$

(4a)

$$\begin{array}{l}{\widehat{\mathbf{y}}}_j\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}={\mathbf{Y}}_j\left(t\mid t-\mathrm{1}\right){\mathbf{A}}_j\left(t\right){\mathbf{Y}}_j^{-\mathrm{1}}\left(t-\mathrm{1}\mid t-\mathrm{1}\right){\widehat{\mathbf{y}}}_j\left(t-\mathrm{1}\mid t-\mathrm{1}\right),\end{array}$$

(4b)

$$\begin{array}{l}\text{updating:}\hspace{0.17em}\\ \hspace{1em}{\mathbf{Y}}_j\left(t\mid t\right)={\mathbf{Y}}_j\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\sum _{i\in S_j\left(t\right)}^{}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\right){\mathbf{H}}_{ij}\left(t\right),\end{array}$$

(4c)

$$\begin{array}{ll}& {\widehat{\mathbf{y}}}_j\left(t\mid t\right)={\widehat{\mathbf{y}}}_j\left(t\mid t-\mathrm{1}\right)+\sum _{i\in S_j\left(t\right)}^{}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\right){\mathbf{z}}_{ij}\left(t\right),\end{array}$$

(4d)

where ${\mathbf{M}}_{ij}(t)$ is the CRLB of the measurement vector ${\mathbf{z}}_{ij}(t)$ at sensor i. The information form of KF has the same estimation accuracy as its conventional counterpart but it provides computational advantages for multisensor data fusion [33]. This is evident from (4c) and (4d) where the sensor measurements contribute in an additive manner, and, as such, the distributed implementation of the information form of KF follows naturally.

The task of the sensor mobility control scheme is to determine $S_j(t)$ , $j=\mathrm{1},\dots ,N_t$ , as well as the sensor positions ${\mathbf{s}}_i(t)$ , $i=\mathrm{1},\dots ,N_s$ , so as to obtain the optimal tracking accuracy for the $N_t$ targets (the sensor positions would affect ${\mathbf{M}}_{ij}(t)$ as discussed in [32]).

4. Problem Formulation for Sensor Mobility Control

This section aims to formulate the optimization problem for sensor mobility control that allocates the sensors for tracking targets and moves the sensors to designated positions. The goal is to estimate the target state vectors with the optimal accuracy using the information form of the KF in (4a), (4b), (4c), and (4d).

We select the mutual information of the target state vector ${\mathbf{u}}_j(t)$ , denoted by $I[{\mathbf{u}}_j(t);{\mathit{z}}_j(t)]$ , as the basis for generating the objective function. $I[{\mathit{u}}_j(t);{\mathit{z}}_j(t)]$ evaluates the reduction of uncertainty in ${\mathbf{u}}_j(t)$ due to the utilization of the sensor measurements from target j up to time index t that are collected in ${\mathbf{z}}_j(t)$ . Mathematically, we have

$$\begin{array}{cc}& I\left[{\mathbf{u}}_j\left(t\right);{\mathit{z}}_j\left(t\right)\right]=H\left[{\mathbf{u}}_j\left(t\right)\right]-H\left[{\mathbf{u}}_j\left(t\right)\mid {\mathbf{z}}_j\left(t\right)\right],\end{array}$$

(5)

where $H[{\mathbf{u}}_j(t)]$ is the prior uncertainty depending on the target motion only and $H[{\mathbf{u}}_j(t)\mid {\mathbf{z}}_j(t)]$ is the remaining uncertainty after the data ${\mathbf{z}}_j(t)$ has been obtained. It has been shown in [28] that

$$\begin{array}{l}H\left[{\mathbf{u}}_j\left(t\right)\mid {\mathbf{z}}_j\left(t\right)\right]\triangleq E\left\{-\log p\left({\mathbf{u}}_j\left(t\right)\mid {\mathbf{z}}_j\left(t\right)\right)\right\}\\ =A-\frac{\mathrm{1}}{\mathrm{2}}\log \left|{\mathbf{Y}}_j\left(t\mid t\right)\right|,\end{array}$$

(6)

where $p({\mathbf{u}}_j(t)\mid {\mathbf{z}}_j(t))$ is the probability density function (PDF) of ${\mathbf{u}}_j(t)$ given the sensor measurements up to time index t, A is a constant, and $\left|·\right|$ indicates the matrix determinant. From (4d), ${\mathbf{Y}}_j(t\mid t)$ is the information matrix of the KF output ${\widehat{\mathbf{y}}}_j(t\mid t)$ . The determinant of the inverse ${\mathbf{Y}}_j^{-\mathrm{1}}(t\mid t)$ is a measure related to the volume of confidence ellipsoid for the target state estimate ${\widehat{\mathbf{y}}}_j(t\mid t)$ [30].

Note that the $N_t$ targets move independently and we then sum (5) over $j=\mathrm{1,2},\dots ,N_t$ to produce the desired objective function to be maximized for sensor mobility control. In other words, the sensor mobility control achieves the optimal tracking accuracy for all targets by reducing to the maximum level the uncertainty in the target state vectors at time index t. Again from (4d), we have that the value of the objective function would depend on $S_j(t)$ as well as ${\mathbf{M}}_{ij}(t)$ , which corresponds to the allocation of sensors for tracking target j and the positions of sensors at time index t. They have to be optimized jointly. Putting (4d) into (5) and noting that the prior uncertainty $H[{\mathbf{u}}_j(t)]$ relates to the target motion solely, we can express the obtained objective function as

$$\begin{array}{l}\underset{\{S_j\left(t\right),{\mathbf{s}}_i\left(t\right)\}}{\max }\tilde{J}\left(t\right)=\sum _{j=\mathrm{1}}^{N_t}‍\log |\phantom{\sum _{i\in S_j\left(t\right)}^{}{\mathbf{H}}_{ij}^T\left(t\right)}{\mathbf{P}}_j^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}+\sum _{i\in S_j\left(t\right)}^{}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\right){\mathbf{H}}_{ij}\left(t\right)|.\end{array}$$

(7)

In fact, the derivation of (7) can be found in [28]. It is important to point out that the objective function $\tilde{J}(t)$ actually needs to be maximized before time index t to obtain the optimal performance at time index t. This imposes difficulty in evaluating the CRLB of the sensor measurement ${\mathbf{M}}_{ij}(t)$ because the true target state vector at time index t remains unavailable. To address this issue, we will replace ${\mathbf{M}}_{ij}(t)$ with its predicted version ${\mathbf{M}}_{ij}(t\mid t-\mathrm{1})$ that has the same functional form as ${\mathbf{M}}_{ij}(t)$ , except that the target state vector at time index t is substituted by its prediction ${\widehat{\mathbf{u}}}_j(t\mid t-\mathrm{1})={\mathbf{Y}}_j^{-\mathrm{1}}(t\mid t-\mathrm{1}){\widehat{\mathit{y}}}_j(t\mid t-\mathrm{1})$ which can be obtained from (4a) and (4b) at time index $t-\mathrm{1}$ .

By introducing the binary allocation variables $a_{ij}(t)\in \{\mathrm{0,1}\}$ , where $i=\mathrm{1},\dots ,N_s$ and $j=\mathrm{1},\dots ,N_t$ , we can transform the objective function in (7) that is dependent on the sensor allocation $S_j(t)$ into the following equivalent member assignment problem:

$$\begin{array}{l}\underset{\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\}}{\max }\tilde{J}\left(t\right)\\ \hspace{1em}=\sum _{j=\mathrm{1}}^{N_t}‍\log |\phantom{\sum _{i=\mathrm{1}}^{N_s}‍}{\mathbf{P}}_j^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right){\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right){\mathbf{H}}_{ij}\left(t\right)|.\end{array}$$

(8)

In (8), $a_{ij}(t)$ takes the value $\mathrm{1}$ if $i\in S_j(t)$ and $\mathrm{0}$ otherwise. Besides, we have substituted the unknown sensor measurement CRLB ${\mathbf{M}}_{ij}(t)$ with its predicted version ${\mathbf{M}}_{ij}(t\mid t-\mathrm{1})$ .

We proceed to incorporate practical constraints on the variables to be optimized in (8), namely, $a_{ij}(t)$ and ${\mathbf{s}}_i(t)$ , to accomplish the formulation of the optimization problem for sensor mobility control. In particular, firstly, to avoid losing the tracking of any target, it is required that each target is tracked by at least one mobile sensor node. That is, ${\sum }_{i=\mathrm{1}}^{N_s}‍a_{ij}(t)\ge \mathrm{1}$ for $j=\mathrm{1},\dots ,N_t$ . Secondly, although each mobile sensor node is allowed to track more than one target at the same time, the total number of targets being simultaneously tracked should not be over ${\lambda }_i$ , due to the limitation on the processing capability, memory size, and/or energy supply. Mathematically, we have ${\sum }_{j=\mathrm{1}}^{N_t}‍a_{ij}(t)\le {\lambda }_i$ for $i=\mathrm{1},\dots ,N_s$ . The combination of the above two constraints yields four scenarios of practical interest. More specifically, they are

Case 1.

${\sum }_{i=\mathrm{1}}^{N_s}‍a_{ij}(t)=\mathrm{1}$ for $j=\mathrm{1},\dots ,N_t$ and ${\sum }_{j=\mathrm{1}}^{N_t}‍a_{ij}(t)\le \mathrm{1}$ for $i=\mathrm{1},\dots ,N_s$ ;

Case 2.

${\sum }_{i=\mathrm{1}}^{N_s}‍a_{ij}(t)=\mathrm{1}$ for $j=\mathrm{1},\dots ,N_t$ and $\mathrm{1}\le {\sum }_{j=\mathrm{1}}^{N_t}‍a_{ij}(t)\le {\lambda }_i$ for $i=\mathrm{1},\dots ,N_s$ ;

Case 3.

${\sum }_{i=\mathrm{1}}^{N_s}‍a_{ij}(t)>\mathrm{1}$ for $j=\mathrm{1},\dots ,N_t$ and $\mathrm{1}\le {\sum }_{j=\mathrm{1}}^{N_t}‍a_{ij}(t)\le {\lambda }_i$ for $i=\mathrm{1},\dots ,N_s$ ;

Case 4.

${\sum }_{i=\mathrm{1}}^{N_s}‍a_{ij}(t)>\mathrm{1}$ for $j=\mathrm{1},\dots ,N_t$ and ${\sum }_{j=\mathrm{1}}^{N_t}‍a_{ij}(t)\le \mathrm{1}$ for $i=\mathrm{1},\dots ,N_s$ .

In Case 1, also the simplest case, one target is allowed to be tracked by one sensor node only while one sensor node can track at most one target at a time. Case 2 differs from Case 1 in that each sensor node is able to track more than one target simultaneously. In Case 3, each target is tracked by more than one sensor nodes and each sensor is tracking more than one target. In contrast to Case 3, in Case 4, a sensor node can track one target at most.

Combining any of the four constraints with the objective function in (8) would yield the corresponding optimization problem for the sensor mobility control in a particular network setting of interest. Essentially, no matter which scenario is selected, we will obtain a nonlinear combinatorial optimization problem. A number of solutions have been proposed in the literature such as [34, 35]. However, there are two major disadvantages in these algorithms that hinder their application to the sensor mobility control problem considered in this paper. They have (1) high computational complexity and (2) centralized processing nature. Those observations motivate us to develop in the next two sections distributed solutions with relatively lower complexity to the sensor mobility control problem.

5. Iterative Solutions for Sensor Mobility Control

We will present the solutions for the sensor mobility control problem formulated in the previous section that reduces maximally the summed uncertainty of the target state vectors ${\mathbf{u}}_j(t)$ by jointly optimizing the sensor allocation variables $a_{ij}(t)$ and the sensor positions ${\mathbf{s}}_i(t)$ at time index t (see (8)). In particular, the solutions to the optimization problems with constraints on $a_{ij}(t)$ being from Cases 1 and 3 are presented in detail. The sensor mobility control solutions for Cases 2 and 4 can be established in a similar manner and they are described briefly.

5.1. Sensor Mobility Control for Case 1

The corresponding optimization problem for sensor mobility control in this case is

$$\begin{array}{l}\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}\tilde{J}\left(t\right)=\sum _{j=\mathrm{1}}^{N_t}‍\log |{\mathbf{P}}_j^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\phantom{\sum _{i=\mathrm{1}}^{N_s}‍}\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right){\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\phantom{\sum _{i=\mathrm{1}}^{N_s}‍}\times \left(t\mid t-\mathrm{1}\right){\mathbf{H}}_{ij}\left(t\right)|\\ \text{s}.\text{t}.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)=\mathrm{1}\hspace{1em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}j=\mathrm{1},\dots ,N_t,\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\le \mathrm{1},\hspace{1em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}i=\mathrm{1},\dots ,N_s,\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}\hspace{1em}}\hspace{1em}\hspace{1em}{a}_{ij}\left(t\right)\in \left\{\mathrm{0,1}\right\}.\end{array}$$

(9)

The above problem is NP-hard mainly due to the binary nature of $a_{ij}(t)$ [34]. Enumerating all the feasible solutions is unacceptable as the number of solutions is the factorial of the problem dimension.

To solve the maximization problem (9) efficiently, we first apply the linear programming (LP) relaxation and relax $a_{ij}(t)\in \{\mathrm{0,1}\}$ as $\mathrm{0}\le a_{ij}(t)\le \mathrm{1}$ . Moreover, we simplify the objective function by substituting the constraints from Case 1 and obtain

$$\begin{array}{l}\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}\tilde{J}\left(t\right)=-\sum _{i=\mathrm{1}}^{N_s}‍\hspace{0.17em}\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)c_{ij}\left(t\right)\\ \text{s}.\text{t}.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)=\mathrm{1}\hspace{1em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}j=\mathrm{1},\dots ,N_t,\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}}\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\le \mathrm{1},\hspace{1em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}i=\mathrm{1},\dots ,N_s,\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}}\phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{0}\le a_{ij}\left(t\right)\le \mathrm{1},\end{array}$$

(10)

where $c_{ij}(t)=\log |{\mathbf{P}}_j^{-\mathrm{1}}(t\mid t-\mathrm{1})+{\mathbf{H}}_{ij}^T(t){\mathbf{M}}_{ij}^{-\mathrm{1}}(t\mid t-\mathrm{1}){\mathbf{H}}_{ij}(t)|$ .

We will develop an iterative solution to (10) by combining the primal dual formulation with the projection subgradient searching technique. Subgradient searching offers greater simplicity and better robustness over commonly used algorithms such as the interior-point technique or the Newton's method [36, 37]. In addition, the implementation of the subgradient method requires much less memory, which makes it attractable for mobile sensor network applications.

The algorithm development begins with deriving the Karush-Kuhn-Tucker (KKT) conditions for the optimal solutions to (10). It can be shown by following the same approach in [28] that the optimization problem (10) is convex with differentiable objective and constraint functions, which guarantees the global convergence and the optimality of the subgradient searching method when it is used to solve (10). As a result, the Slater's condition is satisfied. The associated Lagrangian is

$$\begin{array}{l}L\left(a_{ij}\left(t\right),l_i,{\sigma }_j,{\mathbf{s}}_i\left(t\right)\right)=\tilde{J}\left(t\right)+\sum _{i=\mathrm{1}}^{N_s}‍l_i\left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)-\mathrm{1}\right)\\ +\sum _{j=\mathrm{1}}^{N_t}‍{\sigma }_j\left(\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)-\mathrm{1}\right),\end{array}$$

(11)

where $l_i$ and ${\sigma }_j$ are the Lagrange multipliers and their dependency on the time index t is suppressed for simplicity of the presentation. The Lagrange dual problem can be written as

$$\begin{array}{cc}& g\left(l_i,{\sigma }_j\right)=\underset{\mathrm{0}\le a_{ij}\left(t\right)\le \mathrm{1}}{\mathrm{\hspace{0.17em}\hspace{0.17em}}\inf \mathrm{\hspace{0.17em}\hspace{0.17em}}}L\left(a_{ij}\left(t\right),l_i,{\sigma }_j,{\mathbf{s}}_i\left(t\right)\right),\end{array}$$

(12)

where $l_i\ge \mathrm{0}$ , $i=\mathrm{1},\dots ,N_s$ and $j=\mathrm{1},\dots ,N_t$ . The optimal solutions to the primal and dual problems are

$$\begin{array}{cc}& a_{ij}^{*}\left(t\right),{\mathbf{s}}_i^{*}\left(t\right)=\mathrm{\hspace{0.17em}\hspace{0.17em}}\min \hspace{0.17em}L\left(a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right),l_i^{*},{\sigma }_j^{*}\right),\end{array}$$

(13)

where $a_{ij}^{*}(t)$ , ${\mathbf{s}}_i^{*}(t)$ , and $(l_i^{*},{\sigma }_j^{*})$ are the primal and dual optimal solutions with zero duality gap.

The KKT conditions for $a_{ij}^{*}(t),{\mathbf{s}}_i^{*}(t)$ , and $(l_i^{*},{\sigma }_j^{*})$ are

$$\begin{array}{l}-c_{ij}^{*}\left(t\right)+l_i^{*}+{\sigma }_j^{*}=\mathrm{0},\hspace{1em}i=\mathrm{1},\dots ,N_s,\hspace{0.17em}j=\mathrm{1},\dots ,N_t,\\ \sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{*}\left(t\right)\mathrm{Tr}[\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}{\varphi }_{ij}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \frac{{\partial \mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{x,i}}{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{\times \hspace{0.17em}{\mathbf{H}}_{ij}\left(t\right)\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}]|}_{{\mathbf{s}}_i^{*}\left(t\right)}=\mathrm{0},\hspace{1em}i=\mathrm{1},\dots ,N_s,\\ \sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{*}\left(t\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{Tr}[\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}{\varphi }_{ij}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \frac{{\partial \mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{y,i}}{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{\times \hspace{0.17em}{\mathbf{H}}_{ij}\left(t\right)\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}]|}_{{\mathbf{s}}_i^{*}\left(t\right)}=\mathrm{0},\hspace{1em}i=\mathrm{1},\dots ,N_s,\\ \phantom{hhhhhhhhhhhhhh}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{*}\left(t\right)\le \mathrm{1},\hspace{1em}i=\mathrm{1},\dots ,N_s,\\ \phantom{hhhhhhhhhhhhhhhhhhhh}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{l}_i^{*}\ge \mathrm{0},\hspace{1em}i=\mathrm{1},\dots ,N_s,\\ \phantom{hhhhhh}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{l}_i^{*}\left(\sum _{i=\mathrm{1}}^{N_t}‍a_{ij}^{*}\left(t\right)-\mathrm{1}\right)=\mathrm{0},\hspace{1em}\mathrm{\hspace{0.17em}\hspace{0.17em}}i=\mathrm{1},\dots ,N_s,\\ \phantom{hhhhhhhhhhhhhh}\hspace{0.17em}\hspace{0.17em}\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}^{*}\left(t\right)=\mathrm{1},\hspace{1em}j=\mathrm{1},\dots ,N_t,\end{array}$$

(14)

where ${\varphi }_{ij}^{-\mathrm{1}}=|{\mathbf{P}}_j^{-\mathrm{1}}(t\mid t-\mathrm{1})+{\mathbf{H}}_{ij}^T(t){\mathbf{M}}_{ij}^{-\mathrm{1}}(t\mid t-\mathrm{1}){\mathbf{H}}_{ij}(t){|}_{{\mathbf{s}}_i^{*}(t)}$ and $c_{ij}^{*}(t)$ is $c_{ij}(t)$ evaluated at the optimal sensor positions ${\mathbf{s}}_i^{*}(t)$ . It is very hard to find the optimal values $a_{ij}^{*}(t)$ and ${\mathbf{s}}_i^{*}(t)$ in closed form from the KKT conditions. Therefore, an iterative searching algorithm, the subgradient searching technique presented below, is resorted to produce the desired solution for sensor mobility control.

5.1.1. Subgradient Searching

Let $[·{]}_{\mathrm{0}}^{\mathrm{1}}$ denote the projection of a scalar onto $[\mathrm{0,1}]$ and let $[·{]}_{+}$ be the projection of a scalar onto $[\mathrm{0},+\infty ]$ . The optimal values $a_{ij}^{*}(t)$ and Lagrange multipliers $l_i^{*}$ and ${\sigma }_j^{*}$ can be obtained using the following iterative projection subgradient searching with a small step size α:

$$\begin{array}{l}{a}_{ij}^{\left(k+\mathrm{1}\right)}\left(t\right)=[\phantom{\sum }\phantom{{c_{ij}\left(t\right)|}_{{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}}{a}_{ij}^{\left(k\right)}\left(t\right)\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\alpha ({c_{ij}\left(t\right)|}_{{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{-l_i^{\left(k\right)}-{\sigma }_j^{\left(k\right)}\phantom{{c_{ij}\left(t\right)|}_{{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}})\phantom{\sum }]}_0^1,\end{array}$$

(15a)

$$\begin{array}{ll}& s_{x,i}^{\left(k+\mathrm{1}\right)}\left(t\right)=s_{x,i}^{\left(k\right)}\left(t\right)-{\alpha \mathrm{\Gamma }|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(15b)

$$\begin{array}{ll}& s_{y,i}^{\left(k+\mathrm{1}\right)}\left(t\right)={s_{y,i}^{\left(k\right)}\left(t\right)-\alpha \mathrm{\Lambda }|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(15c)

$$\begin{array}{ll}& l_i^{\left(k+\mathrm{1}\right)}={\left[l_i^{\left(k\right)}+\alpha \left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{\left(k\right)}\left(t\right)-\mathrm{1}\right)\right]}_{+},\end{array}$$

(15d)

$$\begin{array}{ll}& {\sigma }_j^{\left(k+\mathrm{1}\right)}={\sigma }_j^{\left(k\right)}+\alpha \left(\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}^{\left(k\right)}\left(t\right)-\mathrm{1}\right),\end{array}$$

(15e)

where $a_{ij}^{(k)}(t)$ , $l_i^{(k)}$ , and ${\sigma }_j^{(k)}$ represent the values of $a_{ij}(t)$ , $l_i$ , and ${\sigma }_j$ in the kth iteration, ${\mathbf{s}}_i^{(k)}(t)$ is the position of sensor i in the kth iteration, and

$$\begin{array}{l}\mathrm{\Gamma }=\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\mathrm{Tr}[\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}{\varphi }_{ij}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\times \frac{{\partial \mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{x,i}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\times \hspace{0.17em}{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right){\mathbf{H}}_{ij}\left(t\right)\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}],\\ \mathrm{\Lambda }=\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\mathrm{Tr}[\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}{\varphi }_{ij}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\times \frac{{\partial \mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{y,i}}{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\times \hspace{0.17em}{\mathbf{M}}_{ij}\left(t\right)\phantom{\frac{{\partial \mathbf{M}}_{ij}}{\partial s_{x,i}}}].\end{array}$$

(16)

5.2. Sensor Mobility Control for Case 2

For Case 2, the associated sensor mobility control problem is, after the application of the LP relaxation on the sensor allocation variables $a_{ij}(t)$ ,

$$\begin{array}{l}\underset{\left\{a_{ij}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}\tilde{J}\left(t\right)=-\sum _{i=\mathrm{1}}^{N_s}‍\hspace{0.17em}\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)c_{ij}\left(t\right)\\ \text{s}.\text{t}.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)=\mathrm{1}\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}j=\mathrm{1},\dots ,N_t,\\ \phantom{\underset{\left\{a_{ij}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}}\mathrm{1}\le \sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\le {\lambda }_i,\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}i=\mathrm{1},\dots ,N_s,\\ \phantom{\underset{\left\{a_{ij}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}}\phantom{\underset{\left\{a_{ij}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i\left(t\right)\right\}}{\min }\hspace{1em}}\phantom{\hspace{1em}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\le a_{ij}\left(t\right)\le \mathrm{1},\end{array}$$

(17)

where $c_{ij}(t)$ is defined under (10). The corresponding Lagrangian is

$$\begin{array}{l}L\left(a_{ij}\left(t\right),l_i,m_i,{\sigma }_j,{\mathbf{s}}_i\left(t\right)\right)\\ \hspace{1em}\hspace{1em}=\tilde{J}\left(t\right)+\sum _{i=\mathrm{1}}^{N_s}‍l_i\left(\mathrm{1}-\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\sum _{i=\mathrm{1}}^{N_s}‍m_i\left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)-{\lambda }_i\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\sum _{j=\mathrm{1}}^{N_t}‍{\sigma }_j\left(\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)-\mathrm{1}\right),\end{array}$$

(18)

where $l_i$ , $m_i$ , and ${\sigma }_j$ are the Lagrange multipliers.

Following the same steps used to derive the sensor mobility control scheme for Case 1 (see (12)–((15a), (15b), (15c), (15d), and (15e))), we have that the iterative subgradient searching-based sensor mobility control technique for Case 2 is

$$\begin{array}{l}{a}_{ij}^{\left(k+\mathrm{1}\right)}\left(t\right)\\ \hspace{1em}=[a_{ij}^{\left(k\right)}\left(t\right)+\alpha ({c_{ij}|}_{{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}{+l_i^{\left(k\right)}-m_i^{\left(k\right)}-{\sigma }_j^{\left(k\right)}\phantom{\phantom{{c_{ij}|}_{{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}}})]}_0^1,\end{array}$$

(19a)

$$\begin{array}{ll}& s_{x,i}^{\left(k+\mathrm{1}\right)}\left(t\right)={s_{x,i}^{\left(k\right)}\left(t\right)-\alpha \mathrm{\Gamma }|}_{a_{ij}^{\left(k\right)}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(19b)

$$\begin{array}{ll}& s_{y,i}^{\left(k+\mathrm{1}\right)}\left(t\right)={s_{y,i}^{\left(k\right)}\left(t\right)-\alpha \mathrm{\Lambda }|}_{a_{ij}^{\left(k\right)}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(19c)

$$\begin{array}{ll}& l_i^{\left(k+\mathrm{1}\right)}={\left[l_i^{\left(k\right)}+\alpha \left(\mathrm{1}-\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{\left(k\right)}\left(t\right)\right)\right]}_{+},\end{array}$$

(19d)

$$\begin{array}{ll}& m_i^{\left(k+\mathrm{1}\right)}={\left[m_i^{\left(k\right)}+\alpha \left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{\left(k\right)}\left(t\right)-{\lambda }_i\right)\right]}_{+},\end{array}$$

(19e)

$$\begin{array}{ll}& {\sigma }_j^{\left(k+\mathrm{1}\right)}={\sigma }_j^{\left(k\right)}+\alpha \left(\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}^{\left(k\right)}\left(t\right)-\mathrm{1}\right),\end{array}$$

(19f)

where α is the step size, $a_{ij}^{(k)}(t)$ , $l_i^{(k)}$ , $m_i^{(k)}$ , and ${\sigma }_j^{(k)}$ are the values of $a_{ij}(t)$ , $l_i$ , $m_i$ , and ${\sigma }_j$ in the kth iteration, ${\mathbf{s}}_i^{(k)}(t)$ is the position of sensor i in the kth iteration, and $\mathrm{\Gamma }$ and $\mathrm{\Lambda }$ are given under (15a), (15b), (15c), (15d), and (15e).

5.3. Sensor Mobility Control for Case 3

We consider in this subsection the sensor mobility control under the constraints from Case 3. In this scenario, each sensor can track multiple targets and each target is tracked by more than one sensor. Track fusion using the information form of the KF in (4a), (4b), (4c), and (4d) is applied to explore jointly the measurements from the sensors tracking the same target.

The optimization problem for sensor mobility control in this case can be written as, after using (8), the constraints from Case 3 and the LP relaxation that transforms $a_{ij}(t)\in \{\mathrm{0,1}\}$ into $\mathrm{0}\le a_{ij}(t)\le \mathrm{1}$ ,

$$\begin{array}{l}\underset{\{a_{ij}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i\left(t\right)\}}{\max }\hspace{1em}\tilde{J}\left(t\right)=\sum _{j=\mathrm{1}}^{N_t}‍\log |\phantom{\sum _{i=\mathrm{1}}^{N_s}‍}{\mathbf{P}}_j^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \phantom{\text{hhhhhhhhhhhhhhhhhhh}}+\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right){\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\\ \phantom{hhhhhhhhhhhhhhhhhhhhh}\times \left(t\mid t-\mathrm{1}\right){\mathbf{H}}_{ij}\left(t\right)\phantom{\sum _{i=\mathrm{1}}^{N_s}‍}|\\ \text{s}.\text{t}.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{1}\le \sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\le {\lambda }_i,\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}i=\mathrm{1},\dots ,N_s,\\ \phantom{hhhhh}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)>\mathrm{1},\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}j=\mathrm{1},\dots ,N_t,\\ \phantom{\text{hhhhhhhhhhhhhhhhhhhh}}\hspace{0.17em}\hspace{1em}\le a_{ij}\left(t\right)\le \mathrm{1}.\end{array}$$

(20)

This is essentially a nonlinear convex optimization problem. The associated Lagrangian is

$$\begin{array}{l}L\left(a_{ij}\left(t\right),l_i,{\sigma }_j,m_i,{\mathbf{s}}_i\left(t\right)\right)\\ \hspace{1em}\hspace{1em}=\tilde{J}\left(t\right)+\sum _{i=\mathrm{1}}^{N_s}‍l_i\left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)-{\lambda }_i\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\sum _{j=\mathrm{1}}^{N_t}‍{\sigma }_j\left(\mathrm{1}-\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\sum _{i=\mathrm{1}}^{N_s}‍m_i\left(\mathrm{1}-\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\right).\end{array}$$

(21)

By applying the primal-dual formulation and the subgradient searching approach similar to those described in Section 5.1, we obtain the iterative solution for sensor mobility control for Case 3, which is given as

$$\begin{array}{l}{a}_{ij}^{\left(k+\mathrm{1}\right)}\left(t\right)\\ \hspace{1em}=[a_{ij}^{\left(k\right)}\left(t\right)+\alpha ({p_{ij}|}_{a_{ij}^{\left(k\right)}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{-l_i^{\left(k\right)}+{\sigma }_j^{\left(k\right)}+m_i^k\phantom{{p_{ij}|}_{a_{ij}^{\left(k\right)}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}}\phantom{\sum })]}_0^1,\end{array}$$

(22a)

$$\begin{array}{ll}& s_{x,i}^{\left(k+\mathrm{1}\right)}=s_{x,i}^{\left(k\right)}-{\alpha \tilde{\mathrm{\Gamma }}|}_{a_{ij}^{\left(k\right)}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(22b)

$$\begin{array}{ll}& s_{y,i}^{\left(k+\mathrm{1}\right)}=s_{y,i}^{\left(k\right)}-{\alpha \tilde{\mathrm{\Lambda }}|}_{a_{ij}^{\left(k\right)}\left(t\right),\mathrm{\hspace{0.17em}\hspace{0.17em}}{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(22c)

$$\begin{array}{ll}& l_i^{\left(k+\mathrm{1}\right)}={\left[l_i^{\left(k\right)}+\alpha \left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{\left(k\right)}\left(t\right)-{\lambda }_i\right)\right]}_{+},\end{array}$$

(22d)

$$\begin{array}{ll}& {\sigma }_j^{\left(k+\mathrm{1}\right)}={\left[{\sigma }_j^{\left(k\right)}+\alpha \left(\mathrm{1}-\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}^{\left(k\right)}\left(t\right)\right)\right]}_{+},\end{array}$$

(22e)

$$\begin{array}{ll}& m_i^{\left(k+\mathrm{1}\right)}={\left[m_i^{\left(k\right)}+\alpha \left(\mathrm{1}-\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{\left(k\right)}\left(t\right)\right)\right]}_{+},\end{array}$$

(22f)

where

$$\begin{array}{l}{p_{ij}|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t\left)\right]}\\ \hspace{1em}=\mathrm{Tr}[\phantom{{{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)}{\mathbf{H}}_{ij}^T\left(t\right)}{{\psi }_{ij}|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)}{\mathbf{H}}_{ij}^T\left(t\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times {{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)}{\mathbf{H}}_{ij}^T\left(t\right)],\\ \tilde{\mathrm{\Gamma }}=\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\mathrm{Tr}[\phantom{\frac{\partial {\mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{x,i}}}{\psi }_{ij}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \phantom{hhhhhhhhhhh}\times \frac{\partial {\mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{x,i}}\\ \phantom{hhhhhhhhhhh}\times \hspace{0.17em}{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right){\mathbf{H}}_{ij}\left(t\right)\phantom{\frac{\partial {\mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{x,i}}}],\\ \tilde{\mathrm{\Lambda }}=\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\mathrm{Tr}[\phantom{\frac{\partial {\mathbf{M}}_{ij}}{\partial s_{y,i}}}{\psi }_{ij}{\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\\ \phantom{\text{hhhhhhhhhh}}\times \frac{\partial {\mathbf{M}}_{ij}\left(t\mid t-\mathrm{1}\right)}{\partial s_{y,i}}\\ \phantom{\text{hhhhhhhhhh}}\times \hspace{0.17em}{\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right){\mathbf{H}}_{ij}\left(t\right)\phantom{\frac{\partial {\mathbf{M}}_{ij}}{\partial s_{x,i}}}],\\ {\psi }_{ij}^{-\mathrm{1}}=|{\mathbf{P}}_j^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)+\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right){\mathbf{H}}_{ij}^T\\ \hspace{1em}\times \left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right){\mathbf{H}}_{ij}\left(t\right)\phantom{\sum _{i=\mathrm{1}}^{N_s}‍}|.\end{array}$$

(23)

5.4. Sensor Mobility Control for Case 4

Different from Case 3, in Case 4, each target is tracked by more than one mobile sensor but the number of targets simultaneously monitored by any sensor is at most one. This requires that the number of mobile sensors is larger than the number of targets. Under this condition, the sensor mobility control problem becomes

$$\begin{array}{l}\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}\tilde{J}\left(t\right)=\log |{\mathbf{P}}_j^{-\mathrm{1}}\left(t\mid t-\mathrm{1}\right)\phantom{\sum _{j=\mathrm{1}}^{N_t}‍}\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right){\mathbf{H}}_{ij}^T\left(t\right){\mathbf{M}}_{ij}^{-\mathrm{1}}\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\phantom{\sum _{i=\mathrm{1}}^{N_s}‍}\times \left(t\mid t-\mathrm{1}\right){\mathbf{M}}_{ij}\left(t\right)|\\ \text{s}.\text{t}.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)>\mathrm{1}\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}j=\mathrm{1},\dots ,N_t,\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)\le \mathrm{1},\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}i=\mathrm{1},\dots ,N_s,\\ \phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\phantom{\underset{\left\{a_{ij}\left(t\right),{\mathbf{s}}_i\left(t\right)\right\}}{\max }\hspace{1em}}\hspace{1em}\hspace{1em}\mathrm{0}\le a_{ij}\left(t\right)\le \mathrm{1},\end{array}$$

(24)

where the LP relaxation on the sensor allocation variables $a_{ij}(t)$ has been applied. The associated Lagrangian of the above optimization problem is

$$\begin{array}{l}L\left(a_{ij}\left(t\right),l_i,{\sigma }_i,{\mathbf{s}}_i\left(t\right)\right)=\tilde{J}\left(t\right)+\sum _{i=\mathrm{1}}^{N_s}‍l_i\left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}\left(t\right)-\mathrm{1}\right)\\ +\sum _{j=\mathrm{1}}^{N_t}‍{\sigma }_j\left(\mathrm{1}-\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}\left(t\right)\right).\end{array}$$

(25)

The corresponding iterative sensor mobility control solution can be shown to be, through the utilization of primal-dual formulation and the subgradient searching with step size α,

$$\begin{array}{l}{a}_{ij}^{\left(k+\mathrm{1}\right)}\left(t\right)=[\phantom{{p_{ij}|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}}{a}_{ij}^{\left(k\right)}\left(t\right)\\ \hspace{0.5em}+\alpha ({p_{ij}|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}\\ \hspace{1em}\hspace{1em}\hspace{1em}{-l_i^{\left(k\right)}+{\sigma }_j^{\left(k\right)}\phantom{{p_{ij}|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T}})]}_0^1,\end{array}$$

(26a)

$$\begin{array}{ll}& s_{x,i}^{\left(k+\mathrm{1}\right)}=s_{x,i}^{\left(k\right)}-{\alpha \tilde{\mathrm{\Gamma }}|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(26b)

$$\begin{array}{ll}& s_{y,i}^{\left(k+\mathrm{1}\right)}=s_{y,i}^{\left(k\right)}-{\alpha \tilde{\mathrm{\Lambda }}|}_{a_{ij}^{\left(k\right)}\left(t\right),{\mathbf{s}}_i^{\left(k\right)}\left(t\right)=\left[s_{x,i}^{\left(k\right)}\right(t),s_{y,i}^{\left(k\right)}(t){]}^T},\end{array}$$

(26c)

$$\begin{array}{ll}& l_i^{\left(k+\mathrm{1}\right)}={\left[l_i^{\left(k\right)}+\alpha \left(\sum _{j=\mathrm{1}}^{N_t}‍a_{ij}^{\left(k\right)}\left(t\right)-\mathrm{1}\right)\right]}_{+},\end{array}$$

(26d)

$$\begin{array}{ll}& {\sigma }_j^{\left(k+\mathrm{1}\right)}={\left[{\sigma }_j^{\left(k\right)}+\alpha \hspace{0.17em}\left(\mathrm{1}-\sum _{i=\mathrm{1}}^{N_s}‍a_{ij}^{\left(k\right)}\left(t\right)\right)\right]}_{+}.\end{array}$$

(26e)

The definitions of $p_{ij}$ , $\tilde{\mathrm{\Gamma }}$ , and $\tilde{\mathrm{\Lambda }}$ can be found in (23).

6. Distributed Sensor Mobility Control

This section addresses several important aspects in implementing in a distributed manner the iterative sensor mobility control scheme developed in the previous section. The first aspect is on the stopping criterion for terminating the iteration within the proposed sensor mobility scheme. We note that the objective functions are all differentiable. Hence, the subgradient searching algorithm is guaranteed theoretically to converge to the optimal values, that is, ${\lim }_{k\to \infty }{a}_{ij}^{(k)}(t)=a_{ij}^{*}(t)$ , $i=\mathrm{1},\dots ,N_s$ , $j=\mathrm{1},\dots ,N_t$ , given that the step size α is sufficiently small [36, 37]. However, we may have limited processing time in real-time applications and not all $a_{ij}(t)$ may be able to synchronously reach their optimal values. Therefore, in practical implementations, we will terminate the iterations as follows. The iteration should be stopped at the Kth iteration for sensor i when the difference ${\sum }_j‍|a_{ij}^{(K)}(t)-a_{ij}^{(K-\mathrm{1})}(t)|$ falls below a small threshold ${ϵ}_{\text{th}}$ or when a maximum number of iterations $K_{\max }$ have been reached. The final value of $a_{ij}^{(k)}(t)$ , if it is fractional, is rounded to $\mathrm{0}$ or $\mathrm{1}$ and it will be considered as the sensor allocation decision at time t.

The second aspect arises from the distributed realization of the iterations in ((15a), (15b), (15c), (15d), and (15e)), ((19a), (19b), (19c), (19d), (19e), and (19f)), ((22a), (22b), (22c), (22d), (22e), and (22f)), and ((26a), (26b), (26c), (26d), and (26e)). Careful examination of (15a), (15b), (15c), (15d), and (15e) reveals that, at sensor i, the updating of the sensor allocation variables $a_{ij}^{(k)}(t)$ , $j=\mathrm{1},\dots ,N_t$ , and the Lagrange multiplier $l_i^{(k)}$ can be fulfilled locally. However, refining ${\sigma }_j^{(k)}$ requires the knowledge of the sensor allocation variables from all the sensors. This can be addressed by exchanging the latest sensor allocation variables among the mobile sensors after each iteration. Similar mechanism is needed when implementing ((19a), (19b), (19c), (19d), (19e), and (19f)), ((22a), (22b), (22c), (22d), (22e), and (22f)), and ((26a), (26b), (26c), (26d), and (26e)) to update ${\sigma }_j^{(k)}$ . Moreover, in ((22a), (22b), (22c), (22d), (22e), and (22f)) and ((26a), (26b), (26c), (26d), and (26e)), the computation of $p_{ij}$ requires the availability of all the mobile sensor positions ${\mathbf{s}}_i^{(k)}(t)$ to compute the CRLB matrix ${\mathbf{M}}_{ij}(t\mid t-\mathrm{1})$ . As a result, this information needs to be exchanged among the mobile sensors as well.

We summarize in Table 1 the computation steps for realizing the iterative sensor mobility control scheme given in ((15a), (15b), (15c), (15d), and (15e)) and ((22a), (22b), (22c), (22d), (22e), and (22f)). The implementation of ((19a), (19b), (19c), (19d), (19e), and (19f)) and ((26a), (26b), (26c), (26d), and (26e)) follows in a straightforward manner. The implementation can be considered distributed because, except for the exchange of information on sensor positions and sensor allocation variables, major computations needed for the sensor mobility control scheme are indeed executed distributively at mobile sensors.

7. Simulation Results

Computer simulations are conducted to demonstrate the impacts of applying the proposed iterative sensor mobility control scheme on the MTT accuracy. In the simulations, the mobile sensors assume that the motion of any target follows the same first-order Markov process given in (1), where the matrices ${\mathbf{A}}_j(t)$ and ${\mathbf{C}}_j(t)$ , $j=\mathrm{1},\dots ,N_t$ , are equal to

$$\begin{array}{cc}& {\mathbf{A}}_j\left(t\right)=\left(\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \mathrm{\Delta }t& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{\Delta }t\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right),\hspace{1em}\hspace{1em}{\mathbf{C}}_j\left(t\right)=\left(\begin{array}{cc}\mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}\\ \mathrm{\Delta }t& \mathrm{0}\\ \mathrm{0}& \mathrm{\Delta }t\end{array}\right).\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}\end{array}$$

(27)

The system noise ${\mathbf{v}}_j(t)$ is a zero-mean Gaussian random vector with covariance matrix ${\delta }_v^{\mathrm{2}}{\mathbf{I}}_{\mathrm{2}\times \mathrm{2}}$ . We set ${\delta }_v^{\mathrm{2}}=\mathrm{0.05}\hspace{0.17em}{\text{m}}^{\mathrm{2}}/{\text{s}}^{\mathrm{2}}$ and the sampling interval $\mathrm{\Delta }t=\mathrm{1}$  s in the simulations.

Each mobile sensor is also assumed to have the same target TOA and DOA measurement model. Specifically, the mobile sensor is equipped with a linear array of 4 antennas and it extracts the TOA and DOA of a target from the signal received in the line of sight (LOS) path. The received signal power follows the path loss model with the attenuation proportional to $r_{ij}^{-n}(t)$ , where $r_{ij}(t)=c{\tau }_{ij}(t)$ is the true target-sensor distance at time index t, c is the signal propagation speed, ${\tau }_{ij}(t)$ is the true TOA, and $n=\mathrm{2}$ . The effective signal bandwidth is $\mathrm{10}\hspace{0.17em}$ MHz. In the subgradient searching, step size α is $\mathrm{0.1}$ and the stopping criteria are ${ϵ}_{\text{th}}=\mathrm{0.0001}$ and $K_{\max }=\mathrm{500}$ .

The received target signals are corrupted at the mobile sensors by the additive white Gaussian noise (AWGN). Under the above settings, the CRLBs of the TOA and DOA from target j jointly measured at sensor i, denoted by ${\mathbf{C}}_{\tau }^{ij}(t)$ and ${\mathbf{C}}_{\theta }^{ij}(t)$ , can be expressed as ${\mathbf{C}}_{\tau }^{ij}(t)=K_{\mathrm{1}}/{\gamma }_{ij}(t)$ and ${\mathbf{C}}_{\theta }^{ij}(t)=K_{\mathrm{2}}/{\gamma }_{ij}(t){\sin }^{\mathrm{2}}{\theta }_{ij}(t)$ , where $K_{\mathrm{1}}$ and $K_{\mathrm{2}}$ are constants dependent on the signal effective bandwidth and wavelength of the target signal, the number of antennas, and the antenna separation [32]. ${\gamma }_{ij}(t)$ is the received SNR at sensor i for target j at time index t and ${\theta }_{ij}(t)$ is the true target DOA. The measured TOA and DOA are fused using (2a) and (2b) to obtain the target position estimate, where the estimation error ${\mathbf{w}}_{ij}(t)$ is also zero-mean and has a covariance matrix ${\mathbf{M}}_{ij}(t)$ related to ${\mathbf{C}}_{\tau }^{ij}(t)$ and ${\mathbf{C}}_{\theta }^{ij}(t)$ . The explicit form for ${\mathbf{M}}_{ij}(t)$ is given in [32].

Thanks to the mobility of sensor nodes, it is not necessary to deploy many sensors in order to achieve the effective monitoring of an area of interest. Hence, in the simulations, we will consider only 4 sensors deployed in a square with an edge length of 140. We will investigate the performance of the sensor mobility control schemes developed for MTT Cases 1 and 3 (see Section 4). In particular, in Case 1, the number of moving targets is set to 4, and each target can be tracked by only one mobile sensor and each sensor is allowed to track one target only. On the other hand, for Case 3, we also set the number of moving targets to 4, but, in this case, each target is tracked by more than one sensor and each sensor is able to track more than one yet no more than two targets at the same time (i.e., ${\lambda }_i=\mathrm{2}$ ,   $i=\mathrm{1,2},\dots ,\mathrm{4}$ ).

Performance results from simulation of the sensor mobility control scheme for MTT Case 1 are shown in Figures 1–3. Specifically, Figure 1 plots the true and estimated trajectories of four targets in consideration for a particular ensemble run. The target trajectory estimates, obtained via the KF in (4a), (4b), (4c), and (4d) augmented with the iterative sensor mobility control scheme for Case 1, match the true ones closely. Figure 2 shows the corresponding movement of mobile sensors during the whole tracking process. Figure 3 illustrates the index of the target tracked by each sensor as function of time. As we can observe from Figures 1–3, due to the fact that, in this ensemble run, the sensor initial positions are near to those of the targets, each sensor follows the motion of the target initially closest to the sensor most of the time. This is somewhat expected, as the sensor mobility control schemes aim at optimizing the overall MTT performance and this is achieved in this case with each target being tracked by the sensor near to it, which would generally result in improved target position estimate.

Figure 1

(a) True target trajectories and initial positions of mobile sensors for investigating the performance of the sensor mobility control scheme for MTT Case 1. (b) Estimated target trajectories using the proposed sensor mobility control scheme and the KF in (4a), (4b), (4c), and (4d). Star symbol: target 1; circle symbol: target 2; dotted line: target 3; plus symbol: target 4; square symbol: initial positions of mobile sensors.

Figure 2

Movement of mobile sensors under the proposed sensor mobility control scheme for MTT Case 1.

Figure 3

Temporal evolution of sensor allocation variables under the proposed sensor mobility control scheme for MTT Case 1.

Figures 4–6 give the simulation results for the sensor mobility control scheme developed for MTT Case 3, where Figure 4 shows the true and estimated target trajectories in a certain ensemble run, while Figures 5 and 6 illustrate the sensor movements and the targets allocated to each sensor for tracking. Different from the previous simulation, in this experiment, sensors 1 and 4 are not close to any targets at the beginning of the tracking process. Besides, the mobile sensors are allowed to track at most two targets simultaneously in this case. The above two factors greatly complicate the dynamics of the target allocation, as indicated in Figure 6. Examining carefully Figures 4–6 together reveals that sensor 3 follows the motion of target 1 and sensor 2 tends to move closer to targets 3 and 4 and keep tracking them, since they are deployed near to one another in the initial stage. This observation is similar to the one obtained from Figures 1–3. But in contrast to sensors 2 and 3, the trajectory of sensor 4 does not appear to follow the motion of any particular target, except that, at the end of the tracking process, it starts moving near to target 3. Despite the diverse movements of the mobile sensors, all the four sensors are tracking the maximum allowable number of targets most of the time during the whole tracking process. This indicates that the proposed sensor mobility control scheme attempts to improve the target tracking accuracy by increasing the number of measurements on the position of each target, which is expected.

Figure 4

(a) True target trajectories and initial positions of mobile sensors for investigating the performance of the sensor mobility control scheme for MTT Case 3. (b) Estimated target trajectories using the proposed sensor mobility control scheme and the KF in (4a), (4b), (4c), and (4d). Star symbol: target 1; circle symbol: target 2; dotted line: target 3; plus symbol: target 4; square symbol: initial positions of mobile sensors.

Figure 5

Movement of mobile sensors under the proposed sensor mobility control scheme for MTT Case 3.

Figure 6

Temporal evolution of sensor allocation variables under the proposed sensor mobility control scheme for MTT Case 3.

To quantify the tracking performance, Monte Carlo simulations of 500 ensemble runs are performed and the cumulative distribution function (CDF) of the localization error for each target is plotted for investigation. This metric illustrates how likely a location estimate would have an error less than a prespecified value. We compare the localization error CDF for two techniques, namely, the mobile WSN-based MTT and the static WSN-based MTT. The simulation setup is the same as the ones used to generate Figures 1–3. The difference is that we consider here 4–10 targets randomly moving in the area of interest and the measurement noise is generated independently for each ensemble run. Overall CDF curves are shown in Figure 7. The minimum mean square error (MMSE) of locating all targets is shown in Figure 8. It can be observed that the use of mobile sensor networks offers significant tracking accuracy improvement over the case where static sensor networks are deployed.

Figure 7

Overall CDF in terms of location error.

Figure 8

Overall MMSE of targets (Log scale).

8. Conclusions

In this paper, the problem of sensor mobility control for a multisensor multitarget tracking system was investigated. We designed a new sensor mobility control scheme that jointly optimizes the sensor movement and allocation for maximizing the tracking performance for all targets under practical system constraints. A generic optimization framework for sensor mobility control was developed and solved using projection subgradient searching. The newly proposed sensor mobility control algorithm can be implemented in a distributed fashion with the complexity being linear with the number of sensor nodes and targets.

In future works, we plan to improve the proposed sensor mobility control scheme by taking into account more practical aspects including but not limited to potential loss of network connectivity and sensing coverage due to sensor movements. Energy efficiency is also an interesting topic that considers reducing the amount of energy consumption needed in sensor movements.