[up]

Scheduling in the ANTS Challenge Problem using Distributed, Soft Graph Coloring

(The approach described below deals only with the constraints arising from the radar heads - that only one per sensor unit can scan at any given time. It does not deal with the constraints on communication.)

This approach to the scheduling aspect of the challenge problem can be summarized as follows: virtual resources, comprised of three physical radar heads and each capable of tracking a target, are defined; the physical radar constraints are lifted to mutual exclusion constraints on the virtual resources; the virtual resources are scheduled by assigning time slots in a cyclic schedule, so that mutually exclusive resources activate in different time slots.

In this formulation, scheduling is isomorphic to graph coloring, where the virtual resources correspond to nodes in a graph, mutual exclusion constraints correspond to edges, and timeslots correspond to colors. Details follow.

First, an initialization phase is performed:

Analyze geometry to identify best scanning combinations
Constraint 1 requires targets be scanned simultaneously by, preferably, three radar heads. So we analyze the geometry of the sensor network and identify contiguous regions that are best scanned by the same three radar heads (where "best" is determined by the radar heads' sensitivity equation relating distance and angle to signal strength). For example, with six sensor units placed at the corners of a regular hexagon, the scan regions form the pattern shown to the right. Note that the three heads corresponding to any given region are necessarily on different sensor units and so can all be scanned simultaneously.
Define virtual resources representing triangulators
A virtual resource is defined to represent each scanning region identified by the geometry analysis. Each virtual resource is comprised of three radar heads and is capable of triangulating a single target; i.e., each virtual resource is capable of accomplishing a tracking task.
Compute the constraints on the collection of virtual resources
Each virtual resource is comprised of three physical radar heads. For any two virtual resources, a mutual exclusion constraint exists if any of the radar heads making up one of the virtual resources is on the same sensor unit as any of the radar heads making up the second virtual resource, due to Constraint 2. Two virtual resources are said to be neighbors if there exists a mutual exclusion constraint between them.
Assign virtual resources to scheduling agents
Each virtual resource is assigned to one scheduling agent that is resident on a computational device. Each scheduling agent is responsible for determining the actions of its virtual resources.

Then several simultaneous, ongoing processes are started:

Iteratively schedule
The scheduling agents continually communicate with their neighbors and attempt to improve their own schedules: specifically, they attempt to ensure that mutually exclusive resources are not scheduled to scan at the same time.
Continuously execute schedules
The resources continuously execute their scheduling agents' current schedules. To accomplish this, an action scheduled for a virtual resource is decomposed into actions for each of its component resources (radar heads).
Resolve conflicts at physical resource level
It is likely that two mutually exclusive virtual resources are at least temporarily scheduled for simultaneous scanning. In such a case, when the virtual resource schedules are decomposed into actions for radar heads, at least one radar unit will end up with requests to scan two or more of its heads simultaneously. Since it can scan only one at a time, it prioritizes the requests based on the targets' estimated positions.

Scheduling using Graph Coloring

In the form outlined above, scheduling virtual resources can be mapped onto graph coloring:

In graph coloring, a commonly used characteristic of a graph is its chromatic number which is the fewest number of colors required to color the graph so that no two nodes of the same color are connected by an edge. If we try to color a graph with fewer colors, we inevitably end up with conflicts (i.e., nodes of the same color connected by an edge): the equivalent situation in the scheduling problem occurs when the revisit period is too short compared with the dwell time.

More generally, the number of colors compared with the chromatic number gives a measure of the difficulty of the coloring problem: if the number of colors is less than or greater than the chromatic number, the coloring problem is over constrained or under constrained, respectively. If the number of colors is equal to the chromatic number, the coloring is critically constrained.

In summary, we can cast the scheduling of the virtual resources as a graph coloring problem, but that certainly does not mean that we can consider the problem solved! Graph coloring is just as difficult computationally as scheduling. Moreover, we still must achieve the coloring in a scalable, decentralized, robust manner. Nevertheless, viewing the problem as graph coloring does provide a useful, comparatively simple framework and we can exploit this in assessing the performance of a scheduler. This is detailed in the section on soft graph coloring.

Assessment of Performance

Most of our experiments to date have been conducted using a simulator of the challenge problem provided by Rome Lab. The results of two typical experiments are shown below.

A histogram of the errors in the estimates is shown below. The r.m.s. error was 3.09 feet. Other statistics of interest are: average radar head power usage was 27% and the average number of messages sent per node per second was 0.9. These values are close to or better than the goals that have been established for the challenge problem.

Animation of Tracking

The system in action can be viewed as an AVI animation.

Further Information

Our presentation from the autumn 2000 ANTS meeting has similar material, plus a little bit extra.