Adaptive Mobile Sensor Positioning for Multi-Static Target Tracking-4rV.pdf

I. INTRODUCTION

Adaptive Mobile Sensor

Positioning for Multi-Static

Target Tracking

Recent improvements in battery, microcontroller,

and sensor technologies have resulted in the

development of autonomous vehicles that are

inexpensive, dependable, and simple to operate.

Unmanned air vehicles (UAVs) have well-known

defense applications and are useful in many civilian

applications as well, such as border and coast patrol,

fire perimeter monitoring, search and rescue, etc.

UAVs are particularly well suited for situations that

are too dangerous for direct human monitoring. While

a single autonomous UAV can provide information

that is otherwise unattainable, cooperation among

a team of UAVs can dramatically improve sensing

performance [1—5]. The mobility of each UAV within

the team can be exploited to adaptively reconfigure

the sensing array in response to the environment and

the actions of the object being sensed [6—8]. It is this

additional degree of freedom we wish to exploit in a

multistatic radar tracking scenario.

Using mobile and controllable sensing platforms

is a relatively new area of research, but has attracted

considerable attention in the generic sensor network

literature. This type of problem is sometimes referred

to as sensor management. The majority of work in

sensor management for target tracking assumes one of

four practical observation models: range only [9, 10],

bearing only [11, 12], range/bearing [2, 13], and

more recently, range/range-rate/bearing [14]. These

observation models are common due to the prevalent

use of directional laser and radar sensors. However,

small UAVs may have a difficult time making accurate

bearing measurements given their limited aperture

and the fact that they are much more sensitive to

wind-blown disturbances. Moreover, power constraints

on small UAVs limit the range and strength of their

radar transmissions.

Other papers have focused on static sensors

that are capable of toggling between active and

resting states [15—19] or arranging the scheduling

and reporting of measurments in an optimal manner

[20, 21]. The placement of static sensor nodes for

tracking in an underwater scenario is investigated in

[3], [22], [23]. The advantages of mobile sensors are

studied in [6], [24], where sensors are constrained to

remain in small groups that retain observability of the

target states. The motion and geometric formation

effects of these groups on tracking performance are

then investigated. In [25], the optimal positions of

a set of UAVs in a tracking scenario are determined

based on the Cramer-Rao bound (CRB). These results

provide insight into the relationship between the

angular distribution of the UAV team and target

state estimation using range, range-rate, and bearing

measurements. However, the results are derived

under the assumption that the accuracy of the UAV

measurements are constant, and not a function

PENGCHENG ZHAN

DAVID W. CASBEER

Brigham Young University

A. LEE SWINDLEHURST, Fellow, IEEE

University of California at Irvine

Unmanned air vehicles (UAVs) are playing an increasingly

prominent role in both military and civilian applications. We

focus here on the use of multiple UAV agents in a target tracking

application where performance is improved by exploiting

each agent’s maneuverability. Local time-delay and Doppler

measurements made at each UAV are used as inputs to an

extended Kalman filter (EKF) which tracks the target’s position

and velocity. Two simple metrics are defined to quantify the

accuracy of the tracking algorithm, and heading feedback to

the UAVs is used to minimize the metric and improve tracking

performance. A simplified version of one of the algorithms that

reduces computational complexity is also presented. Simulations

demonstrate the significant improvement that results when

the UAV sensors are allowed to be optimally positioned during

tracking.

Manuscript received June 20, 2007; revised March 31, 2008;

released for publication September 2, 2008.

IEEE Log No. T-AES/46/1/935931.

Refereeing of this contribution was handled by W. Koch.

This work was supported by the U.S. National Science Foundation

under Information Technology Research Grant CCF-0428004.

Authors’ current addresses: P. Zhan, ArrayComm LLC, San Jose,

CA; D. Casbeer, Dept. of Electrical and Computer Engineering,

Brigham Young University, 459 Clyde Building, Provo, UT 84602,

E-mail: (casbeer@byu.edu); A. L. Swindlehurst, Dept. of Electrical

Engineering and Computer Science, University of California at

Irvine, Irvine, CA.

0018-9251/10/$26.00 ° 2010 IEEE

120

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. 46, NO. 1 JANUARY 2010

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:53:34 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

of the relative position of the UAVs and the target.

In addition the solution proposed in [25] provides an

optimal set of UAV positions, but no path planning for

the UAVs or any guarantees that it is possible for the

dynamically constrained UAVs to reach the resulting

positions in the allotted time.

In this work, we assume a multistatic radar

scenario in which a transmitter, either airborne or on

the ground, illuminates a target with a radar signal.

A team of UAVs receives the target reflection, and

each UAV makes a local time-delay and Doppler

measurement. These measurements are then sent

to a centralized processor or base which uses this

collected data set to track the target’s position and

velocity. Based on the calculated accuracy of the

tracking algorithm, the base determines trajectories

for the UAV team in order to optimize performance

and sends heading commands to the UAVs to

best position them for the next measurement. The

maneuverability of the UAVs provides the base with

the ability to improve tracking performance through

the tunable parameters in the tracking algorithm.

We present two general optimization algorithms

for the problem, and a closed-form solution that

is considerably simpler to implement but performs

essentially as well as the optimal approaches in many

situations.

The format of the paper is as follows: In

Section II we describe the problem setup, the

assumed dynamic models, and relevant aspects

of the extended Kalman filter (EKF). The issue

of range-dependent measurement accuracy is also

addressed. In Section IIIA and IIIB, two algorithms

for determining the optimal UAV heading angles

based on the EKF updates are presented. A more

computationally efficient approach is described in

Section IIIC, based on heuristic observations of one of

the algorithms in simple scenarios. Simulation results

are presented in Section IV, and some conclusions are

drawninSectionV.

Fig. 1. Multiple UAVs tracking single target.

The UAVs are assumed to be capable of velocity

and altitude hold with an autopilot such as the one

described in [26]. Therefore, for simplicity, we

consider only a two-dimensional scenario. We define

the position of the base station as the origin for our

( x , y ) coordinate system where x and y correspond to

the cardinal directions East and North, respectively.

Let x , y , V x ,and V y represent, respectively, the position

of the target and the components of the target velocity

vector in the ( x , y ) directions. Similarly, let x i and y i

denote the position of the i th UAV, and assume that

each UAV is flying at the same constant speed V ,with

heading angle Ã i measured counterclockwise from

the x axis. According to [27] and after appropriate

scaling, the time-delay and Doppler measurements can

be written as

¿ i = 1

Μ p

x 2 + y 2 +

( x¡x i ) 2 +( y¡y i ) 2

(1)

f i = 1

V x x + V y y

V p

x 2 + y 2 +

(2)

( x¡x i ) 2 +( y¡y i ) 2

where

¡V sin Ã i )( y¡y i ) :

In the above equation, c and ¸ stand for the speed of

light and the wavelength of the signal, respectively.

The problem we address in this paper is how

the mobility of the UAV receivers can be exploited

to improve the system’s tracking performance. In

our solution to this problem, the time-delay and

Doppler estimates collected by the UAV team are

uploaded to the base and used as measurement

updates in an EKF tracking the target. Simultaneously

optimal heading commands for each UAV are

calculated at the base station and then transmitted to

the agents. The precise optimality criteria used for

computing the heading commands is presented in

Section III.

¡V cos Ã i )( x¡x i )+( V y

II. BACKGROUND AND SYSTEM DEFINITION

A. Problem Statement

As illustrated in Fig. 1, we consider a multistatic

radar problem in which a set of N UAVs receives the

signal reflected by an airborne target illuminated by a

base transmitter. We assume that the UAVs are able to

form time delay ( ¿ i ) and Doppler ( f i )estimatesbased

on these signals, 1 and transmit these measurements

back to the base.

B. UAV Receivers and Measurement Error

1 Another viable model would be to use the time difference

of arrival rather than time delay. Using this model the control

algorithms developed later would remain unchanged since the

observation Jacobians with respect to target parameters are identical

under both models.

The accuracy of the UAV measurements is a

function of the transmitted radar signal, the signal

strength, the length of the propagation path from

transmitter to receiver, and so on. To quantify the

ZHAN ET AL.: ADAPTIVE MOBILE SENSOR POSITIONING FOR MULTI-STATIC TARGET TRACKING

121

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:53:34 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

V p =( V x

We represent the target state vector at time k as

x k =[ xyV x V y ] T , and define the vector h k ( x k )by

arranging the time-delay and Doppler equations from

each UAV as

h k ( x k )=[ ¿ 1

¢¢¢¿ N

f 1

¢¢¢f N ] T

Fig. 2. Bistatic radar scenario.

where, as described earlier, N is the number of UAV

receivers. Using a linear discrete-time system and an

additive noise observation model, the system is then

written as

time-delay and Doppler measurement accuracy for

UAV i , we use the CRB as derived by [28]:

x k = A k x k¡ 1 + ! k¡ 1

(6)

¶·

= 2 E r

N 0

E r

E r + N 0

! 2 !t

!t t 2

CRB

¡ 1

(3)

z k = h k ( x k )+ º k

(7)

where

where A k is the state transition matrix, ! k¡ 1

! 2 = 1

2 ¼

¡1 ! 2 jS ( j! ) j 2 d!

»N ( 0 , R k ) are, respectively, the

process and measurement noise. Both are assumed

here to be uncorrelated Gaussian random vectors.

As with the standard Kalman filter, the EKF

can be divided into two stages: the time update and

measurement update steps. With the time update, we

propagate the target’s state estimate and prediction

covariance matrix as

¡1 u ˜ s ( u ) @ ˜ s ¤ ( u )

!t =Im

@u du

¡1 u 2 j ˜ s ( u ) j 2 du

! i =2 ¼f i

˜ s ( u )and S ( j! ) are, respectively, the complex envelope

of the transmitted signal and its Fourier transform,

Im represents the imaginary part of its argument, E r

is the average received signal power, and N 0 = 2isthe

spectral density of the white bandpass Gaussian noise

from the receiver on each UAV. Inverting (3) yields

the following explicit expression for the CRB:

t 2 =

k = A k x k¡ 1

(8)

k = A k P k¡ 1 A k + Q k¡ 1 :

(9)

Once we have the measurements from the sensors, we

update our estimate as

x k = x

k + K k ( z k

¡ h k ( x

k ))

(10)

N 0 ( E r + N 0 )

2 E r [ ! 2 t 2 ¡ ( !t ) 2 ]

t 2 ¡!t

¡!t ! 2

CRB i =

: (4)

P k =( I ¡ K k H k ) P

(11)

where

The accuracy of the second step, finding the

position and velocity estimates for the target from the

time-delay and Doppler estimates, are quantified in

the next section by the EKF. This is done through the

Jacobian H k (defined subsequently) which maps the

accuracy of the time-delay and Doppler estimates to

the position and velocity of the target.

We use the standard bistatic radar equation [29]

to model the received signal power E r [30] based on

the geometry of the bistatic radar scenario depicted in

Fig. 2:

K k = P

k H k ( H k P

k H k + R k ) ¡ 1 : (12)

In the above equations, H k =( @ h k =@ x ) T is a function

of the UAVs’ positions and headings.

The basic idea of this paper is to reduce the size

of the estimation error by updating the heading of the

UAVs, and hence H k . In essence, we are applying an

outer control loop around the Kalman filter.

D. System Dynamics

E r = E t G t G r ¸ 2 ¾ b

(4 ¼ ) 3 R b R i

(5)

The approach presented in the next section is

general enough to accommodate any particular model

for A k , Q k ,or R k . In the simulation studies presented

later, we assume a simple constant velocity target

model described by the state transition matrix

where E t is the transmit power; G t , G r are antenna

gains at the base station and UAV side, respectively;

¸ is the wavelength of the transmitted radio signal;

and ¾ b is the radar cross section (RCS) of the target.

4 10 ¢ t

C. Extended Kalman Filter

A k =

01 0 ¢ t

00 1 0

(13)

The need for the EKF is apparent from the

nonlinear measurement equations in (1) and (2).

00 0 1

122

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. 46, NO. 1 JANUARY 2010

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:53:34 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

N ( 0 , Q k¡ 1 )and º k

where ¢ t is the time interval between samples. We

also use a simple white process noise model:

nonlinearities are accounted for through the Jacobian

H k in the EKF.

Q k =diag( ¾ x , ¾ y , ¾ V x , ¾ V y ) :

(14)

III. HEADING ALGORITHMS

The definition of the measurement noise model

is more critical to the problem at hand, since it will

be a function of the UAV positions. Assuming that,

given the current target state, the time-delay and

Doppler estimates at each UAV are independent from

the estimates made by the rest of the UAV team,

the expression for the CRB derived above can be

used to find the elements of the measurement noise

covariance. For 1 ·i·N ,

In this section we present two algorithms for

finding the optimal UAV heading commands from

the EKF. In the first algorithm, the headings are

chosen to minimize the weighted trace of the EKF

prediction error covariance matrix one step into

the future. In the second, UAV headings are found

that maximize the amount of new information

provided by the measurements at the next step. A

heuristic simplification of the second algorithm is also

presented that leads to a closed-form solution to the

problem and considerable computational savings.

CRB i (1,1) j = i

2 ¼ CRB i (1,2) j = i + N

R k ( i , j )= E ( º i º

j )=

A. Error Covariance Minimization

e l s e w h e r e :

When N<i· 2 N ,

The motivation underlying the approach presented

here is simply to fly the UAVs in directions at

time t = k such that the estimation error at time

t = k +1 is made as small as possible. To this end,

we minimize the weighted trace of the one-step

prediction covariance P

2 ¼

CRB i¡N (2,2) j = i

R k ( i , j )= E ( º i º ¤

2 ¼ CRB i¡N (2,1) j = i¡N

k +1 [34]. In practical scenarios,

the UAV dynamics limit the rate at which its heading

may change. Therefore, for each step we restrict the

UAVs’ position to an arc defined by the previous

heading. Mathematically, the idea is to find the vector

of heading commands ª k =[ Ã 1, k :::Ã N , k ] T as follows:

e l s e w h e r e :

We assume the ability of the base to pass a

heading command Ã i , k to UAV i .Assumingan

instantaneous response to heading commands, the

UAVs will fly in a straight line with a velocity V

and heading Ã i during each time interval. The inertial

position of the UAV i at time k can be approximated

ª k =argmin

ª k

tr( W k P

k +1 )

(17)

jÃ i , k

¡Ã i , k¡ 1

j·C

i =1 :::N

x i , k = x i , k¡ 1 + V cos( Ã i , k ) ¢ t

(15)

where W k is a positive semidefinite weighting matrix

and C is the upper bound on the turning rate of the

UAVs.

Replacing P

y i , k = y i , k¡ 1 + V sin( Ã i , k ) ¢ t : (16)

This approximation will be valid as long as the new

heading commands are not too different from the

UAV’s current heading, and the time steps are short

enough.

It is known that due to the geometry of a bistatic

radar system, the bistatic radar ambiguity function,

which is an indicator for how well position and

velocity can be determined from the received

waveform, is a nonlinear function of the transmitter,

receiver, and target positions [31—33]. In our system,

each UAV calculates only the time-delay and Doppler

information from the received waveform that is

possible to calculate under the assumption that the

received signal can be unambiguously associated with

the target being tracked. The time-delay and Doppler

measurements are then passed to the base station for

processing; the nonlinearities arising in the bistatic

radar ambiguity function are encountered at this step

when the velocity and position estimates are extracted

from the measured time delay and Doppler. These

k +1 in (17) with the expressions in (9)

and (11) yields

k H k ] ¡ 1 A k +1 + W k Q k ) :

(18)

Since the dependence of the cost function on the UAV

headings is not explicit, it is useful to examine the

optimization problem in slightly more detail. Equation

(17) depends on the heading angles through H k and

R k in (18), which in turn depend on the positions

of the UAVs at time k , which are a function of their

positions at time k¡ 1 and the heading angles chosen

at time k¡ 1 (as described by the model in (15) and

(16)). Thus, when we minimize (17) with respect to

ª k , we are minimizing it with respect to the headings

chosen at time k¡ 1 after the measurement at time

k¡ 1, which headings are also the ones in force at

time k before measurement k is taken.

When the number of UAVs is not too large, a

finite grid search can be used to optimize the cost

k ) ¡ 1 + H k R

¡ 1

ZHAN ET AL.: ADAPTIVE MOBILE SENSOR POSITIONING FOR MULTI-STATIC TARGET TRACKING

123

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:53:34 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

j )=

tr( W k A k +1 [( P

function. For higher dimensional problems, we

employ a Quasi-Newton approach to minimize (18).

At each iteration the heading is updated by ª m +1 =

ª m

the covariance measurement update in (11), yielding

k =( P

k )

¡ 1 + H k R

k H k

(20)

¡ m and g m are the Hessian matrix

and gradient vector of the cost function evaluated at

ª m . Due to the complexity involved in calculating the

Hessian matrix, the Quasi-Newton approach uses an

estimate of the Hessian based on the gradient vector.

The gradient with respect to the heading of the i th

UAV at time k is given by

@ tr( W k P

¡ S

¡ m g m ,where S

where P ¡ 1

is the information matrix at step k .The

k H k represents the increase in information

provided by the UAVs, assuming that their headings

are chosen to yield H k . If the UAVs provided no

new information at step k ,then H k R ¡ k H k =0,and

the information matrix would be equal to its value

after k¡ 1steps: P ¡ k =( P ¡

¡ 1

k ) ¡ 1 . The idea, then, is to

k +1 )

W k A k +1 B ¡ 1 @ B

k H k ismaximizedinsome

sense. This approach makes sense intuitively: one can

think of this as choosing a set of vectors H k that lie as

much as possible in the eigenvector space of R ¡ 1

¡ 1

= ¡ tr

@Ã i , k B ¡ 1 A k +1

@Ã i , k

where

(19)

k with

the largest eigenvalues (or, equivalently, in the space

of eigenvectors of R k with the smallest eigenvalues).

In other words, we try to position the UAVs so that

the new information that they provide is corrupted the

least by the measurement “noise.” Since H k enters into

this term quadratically, an analysis of the impact of

the UAV headings is much simpler. As discussed in

the next section, this allows for the development of an

efficient algorithm for computing the optimal heading

commands.

Under the maximizing information increase (MII)

approach, the heading commands are found by solving

B =( P

k )

¡ 1 + H k R

¡ 1

k H k

@ B

@Ã i , k

= @ H k

@ H k

@Ã i , k R

k H k +

@Ã i , k R

k H k

¡ H k R

¡ 1

@Ã i , k R

k H k :

The problem boils down to calculating @ H k =@Ã i , k and

@ R k =@Ã i , k ,where H k is 2 N£ 4and R k is 2 N£ 2 N .

Minimizing the cost function (17) over the correct

control variable will work generally for any adaptive

sensor network. The weighting matrix W k is helpful

in that is can be used to place importance on specific

variables of interest. In our problem the magnitude for

position values was much greater than the velocity,

and by adjusting the elements of W k ,wewereableto

place suitable errors on each of these terms.

ª k =argmax

ª k

det( H k R

¡ 1

k H k )

(21)

jÃ i , k

¡Ã i , k¡ 1

j·C

i =1 :::N:

Assuming that the measurement errors across the

UAVs are uncorrelated, and after regrouping the

time-delay and Doppler equation vector as h k ( x k )=

[ ¿ 1 f 1

B. Maximizing Information Increase

¢¢¢¿ N f N ] T , the covariance matrix R k will have

a block diagonal structure. Each block along the

diagonal is denoted by R i k , which is equivalent to the

CRB matrix discussed in Section IIB. More algebraic

manipulation leads to the following equality:

We investigate here an alternative approach

derived from examining an expression for the Fisher

information matrix (or inverse covariance matrix).

Our motivation is to find an algorithm for determining

the UAV headings that is computationally simpler to

implement than the error covariance minimization

(ECM) method of the previous section. As we will

see, the UAV heading parameters enter into the

information matrix update in a much simpler way

that lends itself more easily to approximation. A

closed-form solution based on such an approximation

is presented in the next section. A computationally

efficient optimization method was found in [9]

for a similar application that used the trace of the

covariance matrix, but it was for a much simpler

measurement model than assumed here.

Rather than optimizing over the information matrix

itself, in our approach we choose the UAV headings

so that the increase in information provided by the

UAVs at the new locations is maximized [2, 35]. More

precisely, note that the information matrix update can

be found by applying the matrix inversion lemma to

' k = H k R

k H k =

H i k ( R i k ) ¡ 1 H i k

(22)

i =1

H k =[ H 1 k ::: H N k ] :

The submatrices, H i k , which constitute the

measurement gradient matrix, H k , are defined in (34)

of the Appendix.

By maximizing the new information (21), the

sensors will position themselves such that the next

measurement contains the most information possible.

Notice that this cost metric does not necessarily try to

gain new information that is less known to the system.

It simply tries to find the measurements with the

most information. This metric is perhaps not optimal,

but as shown in the results section, it yields good

performance results. Again because of the simple form

the cost function (21), it allows a closed-form solution

which is presented in the following section.

124

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. 46, NO. 1 JANUARY 2010

AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:53:34 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.

¡ 1

term H k R

choose H k so that H k R

¡ 1

@ R k

¡ 1

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: