|
Time/Utility Function Case Studies:
The AWACS Surveillance Tracking System
Applying Time/Utility
Functions and Utility Accrual Scheduling to Association
This project’s goal was to
improve the tracker’s – and hence the surveillance mission’s
– performance by enabling the tracker to do a better job of
selecting the most useful subset of incoming data that it
could feasibly process. Our approach to achieving that goal
was to employ a computing system (in this case, operating
system) scheduling facility instead of mechanisms internal
to the tracker as extant AWACS surveillance trackers do.
This led to the experimental
tracker being multithreaded, including a separate thread per
data association (i.e., per cluster). The association
algorithms are the most computationally demanding ones, and
were encapsulated in an object that was extracted from the
rest of the tracker. This object can be – and has been – run
on other nodes in a distributed tracking system. Moreover,
there is provision in the tracker to select the association
server to be used on a cluster-by-cluster basis. For brevity
and clarity, here we consider only the association threads
and make the simplifying assumption that each cluster has
only a single track.
To improve handling of
overloads, we used time/utility functions to dynamically
apply resources to the right tracks at the right times. The tracker
dynamically applies computational resources to threads to
adapt to changes in physical environment - e.g., tracks and
sensor reports, updated operator preferences, modified
mission goals, and changes in processing capability
(overloads, failures). During overload, data processing
order is based on relative thread utility.
The AWACS sensor properties imply a general utility function
for the association computation. The
radar antenna rotates with a 10S period.
That
suggests the association utility function has a “critical
time” at the 10S period length, at least two distinct
non-zero utilities before the critical time, and a third
distinct, lower, utility after the critical time. See Figure
1.
Figure 1:
Next, we determined the thread
time/utility function shapes.
Prior to the critical time,
processing a sensor report for one of these tracks in under
five seconds (half the sweep period) would provide better
data for the corresponding report from the out-of-phase
sensor, so the utility decreases with time. In this project,
the utility function had to decrease linearly, due to an
implementation artifact in our experimental system – the OS
(OSF/RI’s MK7.3A) time/utility function scheduling algorithm
allowed only one critical time. The slope was arrived at
empirically (we are currently devising and documenting a
methodology to facilitate this).
After the critical time, the
utility is zero, because newer sensor data has probably
arrived. If the processing load in one sensor sweep period
is so heavy that it couldn’t be completed,
probably the load will be about same in next period, so
there will be no capacity to also process data from the
previous sweep. A tracker that could process older as well
as current data would be significantly more complex, and
probably delay the track update.
That established the
time/utility function shape for the tracker’s association
threads, as shown in Figure 2.
Figure 2:
Three QoS metrics that could
quantify track processing were chosen that fit the project’s
scope:
 |
Quality – 0 to 7
The traditional measure of the amount of recent sensor data
incorporated in a track record; it is incremented or
decremented after each radar scan |
|
Accuracy – high or low
A measure of the uncertainty of the estimate of a track’s
position and velocity; it is derived from traditional Kalman
filter processing |
|
Importance – high or low
The traditional operator-identified importance based on
geography, threat, and other characteristics |
Tracker domain experts’
preferences in terms of track QoS metrics imply the thread
utility values:
|
Don’t drop tracks, because
they are expensive to re-create |
|
User-identified “important”
tracks receive preference |
|
User-identified “important”
geographic regions receive preference |
|
Maneuvering tracks need to be
updated more frequently than non-maneuvering tracks |
|
Potentially high threat tracks
receive preference |
|
High speed tracks receive
preference |
|
Tracks with poor state
estimates receive preference |
The initial utility U1
of an association for a track report was derived from track
QoS metrics by gedanken experiments - the project system
designers interacting with tracker domain experts. These
interactions required considerable time and thought, because
previously, tracker domain experts didn’t have incentives to
use their knowledge to understand and express behavioral
options in the face of dynamic uncertainties (i.e.,
gracefully handling overloads) that plague current trackers.
Figure 3 illustrates the resulting relative initial
utilities for the twelve cases using the three QoS metrics.
Figure 3:
The association (and other)
threads are scheduled based on their utility functions.
For the association threads,
the tracking application selects the established utility
function from the OS scheduler’s library of shapes. The
tracking application does a look-up in the utility U1
table for each association thread before calling the OS
scheduler. A utility-based processor-scheduling policy in
the OS schedules threads according to a heuristic that
attempts to maximize total accrued (summed) utility.
The MK7.3A [ref] real-time OS
(based on a merger of the Mach 3 [ref] and Alpha [Clark
et al. 93] OS's) includes a scheduling framework that
allows arbitrary scheduling policies to be plugged in. This
allowed the project to evaluate the tracker's performance
using three different scheduling policies: FIFO, a common
policy in non-real-time systems; fixed priority, the most
common policy in conventional real-time computing systems;
and a (Locke's) time/utility function policy.
The time/utility
function-based scheduling policy performed better than FIFO
and priority policies; one example is shown in Figure 4.
Figure 4:
This project's AWACS tracker
showed that the time/utility function model can provide
significant cost-effective improvements in dynamic systems
requiring resource management adaptivity in the face of
overloads (a common case in the systems of interest to us).
This experimental project
produced an adaptive, distributed surveillance tracker that
was directly driven by application-level QoS metrics.
Time/utility functions encouraged domain experts to use
their knowledge to understand and express behavioral options
in the face of dynamic uncertainties (i.e., gracefully
handling overloads) that plague current trackers.
The utility model used only three of many possible tracker
metrics to achieve significant tracker performance.
The tracker was demonstrated
to USAF AWACS operators and tracker designers at Boeing, and
received strong supportive feedback, including about its QoS
metrics and its behavior under overload.
We also implemented the AWACS
tracker using the Real-Time Specification for Java (RTSJ)
[ref] Reference Implementation [ref]. Performance results of
the RTSJ RI based tracker were similar to those of the
original C++ based one, as illustrated in Figure 5.
Figure 5:
References
Clark et al. 99
Raymond Clark, E. Douglas Jensen, Arkady
Kanevsky, John Maurer, Paul Wallace, Thomas Wheeler, Yun
Zhang, Douglas Wells, Tom Lawrence, and Pat Hurley,
An Adaptive, Distributed Airborne Tracking System
("Process the Right Tracks at the Right Time"), Proc. Workshop on Parallel and Distributed
Real-Time Systems, 1999, IEEE.
 Add to Favorites
 Print Page
Download a PDF copy of this page
|
