Initial application (Revision 3: August 5, 1998, afternoon)

This page describes our initial application and now reflects the comments from both AlphaTech and Lockheed-Martin. This initial application will be demonstrated in Fall, 1998.

Contents

• Application goals
• Application scenario
• Application demo
• Application components
  • Hypothesis tracker
  • Observation delivery
  • Queries
  • GPS
  • Other components

Application goals

The goal of the initial application is to demonstrate three of the key technologies from the proposal.

• The network-routing algorithms, which allow two wireless machines to communicate with each other even if (1) they are not in direct transmission range (intermediate wireless machines are used as routers) or (2) they are moving (routing tables are continuously updated to reflect current machine locations).

• The mobile-agent infrastructure, which allows the rapid development of robust and efficient network applications.

• The information-clustering algorithms, which automatically discover and create graphical representations of the relationships among text documents (e.g., one document discusses the same subject as a second document).

Application scenario

The application provides operational support to military counter-intelligence teams. First we provide some basic background on military counter-intelligence, and then we describe the application itself.

In general, counter-intelligence teams attempt to discover any hidden enemy activity (i.e., guerrillas or terrorists) in an area that is under the control of friendly forces. For example, suppose the enemy is driven out of a small city but leaves behind guerrillas to hamper friendly forces. Counter-intelligence teams would attempt to identify and seize the guerrillas and their weapons. Alternatively, suppose that the first democratic elections in fifty years are about to be held in a Central American country. Supporters of the old dictatorship have hired a terrorist group to disrupt the election, and the interim government has invited in the U.S. military to ensure a peaceful election. Counter-intelligence teams would attempt to identify and arrest the terrorists.

We will use the election scenario for our demo. As a more specific example of the election scenario, suppose that Natasha, a known terrorist who works for the MMBG (Many Many Bad Guys) organization, was spotted entering the country and has been traced to the country's largest city. She is expected to meet with supporters of the old regime and other members of her own group to plan one or more bombing attacks on election sites. The counter-intelligence mission is to set up surveillance on Natasha, identify her associates (most importantly the unknown Boris, the ringleader of the old-regime supporters), and then make the necessary searches, arrests and weapons seizures as election day approaches. In addition to the specific task of surveiling Natasha and her associates, the counter-intelligence teams would also set up checkpoints and observation posts throughout the city, and conduct interviews with local citizens and arrested terrorists to obtain additional information.

We assume that (1) each counter-intelligence team member has a wireless computer, (2) each team member is assigned to a field-deployed command center such as a observation post (or simply a jeep if a team has been sent in to make an arrest), and (3) all teams report to a single headquarters that is coordinating all counter-intelligence activity in the city. One of the main tasks of the field-deployed command center is to provide a network connection between the team members and headquarters. In the real world, the field-deployed command center might have a satellite uplink, and could be arbitrary far away from headquarters. In the demo, however, which will take place at Dartmouth College, we will not be able to use satellite uplinks. Instead the field-deployed command unit must be within range of some gateway machine that is connected to the wired Dartmouth network. Depending on which wireless hardware is used, the field-deployed command unit must within either 300 feet or half a mile of the gateway machine (in other words, within 300 feet or half a mile of some Dartmouth building).

Our application provides a subset of the support that these counter-intelligence teams need. Specifically, the application has three main tasks:

• Maintain network connectivity among team members (and between team members and headquarters) even if team members are moving rapidly or are spread out across a wide area (such that network packets must be routed through the computers of multiple team members before they can reach the final destination). The wireless-routing algorithms will be used to maintain this network connectivity.

• Allow team members to send observations of suspicious activity to a central tracker and SALUTE relational database. The tracker, which is oriented towards vehicles, mathematically determines which vehicle observations are most likely the same vehicle.

• Allow team members to make queries against the tracker, the SALUTE database, a black-gray-white database that contains suspected and known terrorists, old-regime supporters and new-regime supporters, and one or more document collections that contain text documents relevant to the current situation and environment (such as news feeds and descriptions of the local culture). The interview teams in particular will make queries against these databases as new information comes to light during an interview; the results will be used to redirect that interview or subsequent interviews. At the same time, aside from the observations sent to the tracker and SALUTE database, we do not expect to add new information to the databases during the demo. The basic reason is that adding new information to the black-gray-white or textual databases does not demonstrate anything more than sending a new observation to the tracker. Thus, for this initial demo, we are applying our programming time elsewhere. One possible exception is that, if time allows, the black-gray-white database will include photographs. Then the counter-intelligence teams could take pictures in the field and send them to the database. These pictures will add a nice additional visual component to the demo. Since our digital-camera software does not run under Unix (which is the operating system on all the laptops in the demo), the pictures will be simulated (e.g., taken ahead of time and stored on the laptops for use during the demo). Also, if time allows, we will replicate each database across multiple machines. Then the application could use RPI's network sensing techniques and Dartmouth's planning algorithms to decide which machines can answer the query the quickest. The information-clustering algorithms will be used to present the query results.

Application demo

The Digital RoamAbout cards have an outside range of approximately 300 feet and an effective bandwidth of 1.0 Mbs. The MetriCom radio modems have an outside range of approximately half a mile and an effective bandwidth of 30-50Kbs. Finally, the GPS units are inexpensive units that do not perform differential GPS. We hope to do differential GPS ourselves (with a stationary laptop at a known location) so that we can correct the GPS positions of the objects in the audience's map display; we will not correct the GPS positions of the objects on the soldier's map displays (which, with only one stationary laptop, would be a more complex coordination task than we are prepared to tackle in this initial demo).

We will divide the demo into three distinct phases:

Phase one	:	A team with laptops and Harvard's long-range wireless hardware sets itself up at observations posts across the Dartmouth campus and makes observations of "suspicious" moving vehicles; these observations will be sent to the tracker and the SALUTE database. To demonstrate the fusion capabilities of the tracker, there will have to be several "suspicious" vehicles, so the team members will be told that all vehicles (bicycles, cars, trucks, and so on) of a certain color are automatically suspicious. In addition, there will be two marked vehicles, driven by Dartmouth teams members, that will also be considered suspicious. These two vehicles will carry GPS units (and laptops of their own) so that their exact positions can be compared with the hypothesis tracker's results. There will probably be four vehicle observers distributed around town. Thus we will need seven MetriCom radio modems, one for each of the observers, one for each of the two marked cars, and one on a gateway machine that provides a connection between the laptop cloud and the main network. Currently we do not have any MetriCom radio modems. Dartmouth will order them immediately. This phase of the demo demonstrates the static adaptivity of the network-routing algorithms, i.e., network connectivity is automatically established among laptops that have been carried to arbitrary locations. This phase of the demo also demonstrates the tracker, which is interesting even though it is not part of the proposal. Note that for this initial demo, we are setting aside most security issues. In particular, we are assuming that (1) there will be no physical attacks on the wireless network (e.g., jamming), (2) no laptops will fall into enemy hands, and (3) the entire network from soldier to headquarters is "owned" and controlled by the United States military (e.g., local pre-existing networks are not used to connect the soldiers to their headquarters). At the same time, note that D'Agents includes several security mechanisms (encryption, digital signatures, etc.) that will be immediately useful in later versions of the demo.
Phase two	:	A team with laptops and Dartmouth's short-range wireless hardware is sent to arrest (or follow) a subject. Both the arrest team and the subject will be on foot. Therefore, we will use Dartmouth's short-range hardware so that the network topology will change rapidly as the arrest team and subject move around the campus. With Harvard's long-range hardware, the network topology would change slowly if at all. (An alternative approach for getting rapid topology changes would be to use Harvard's long-range hardware and have both the arrest team and the subject in cars. We feel strongly, however, that is too dangerous for undergraduate drivers in a campus environment.) At some point during this phase, the team will split into two subteams. The subteams then will follow paths that (1) take them out of network contact with each other (e.g., the subteams might go around a large building in opposite directions) and (2) later bring them back into network contact. As the subject moves, the arrest team will continually send back position information, as well as short descriptions of what the subject is doing. These descriptions will be formatted as SALUTE records and will likely be scripted in advance. There will probably be six members of the arrest team, which means that we will need eight RoamAbout cards, one for each of the team members, one in a gateway machine, and one in a machine placed between the gateway and the wireless cloud (so that the wireless cloud as a whole is always in range of either the gateway or the intermediary -- one could view these two machines together as simulating a long-range link). This phase of the demo demonstrates the dynamic adaptivity of the network-routing algorithms, i.e., network connectivity is maintained even though the laptops are moving continuously, and when network connectively cannot be maintained due to some transmission obstruction such as a building, connectively is re-established quickly as soon as the team has moved past the obstruction. As before we are setting aside most security issues.
Phase three	:	An interview team makes queries against the tracker and the available databases. We plan to have four databases: SALUTE, white-gray-black, and two collections of text documents, specifically news feeds and cultural information. Not all of the databases will be located at Thayer. At least one will be in the computer science department, and (hopefully) at least one will be at Harvard. This phase of the demo demonstrates the information-clustering software and, more than the other phases, the underlying mobile-agent infrastructure. In particular, it will demonstrate that a mobile agent can (1) conserve bandwidth and (2) continue with its retrieval task even if its home laptop is temporarily disabled or disconnected from the network, simply by moving from the home laptop to the databases.

Depending on hardware availability and other logistics, we will have teams at one or more of the other institutions, such as RPI, Harvard or Illinois. It is likely, however, that sufficient hardware will not be available.

The audience will be in a Thayer class room. We will start with an overview of the demo and its three phases. Then we will have the live demo of each phase in the same order as listed above. Before and after the live demo of each phase, we will give a more detailed description of the demonstrated technical achievements. We will conclude with an overview of next year's plans.

The audience will see (1) a map that has the locations and tracks of all team members and observed vehicles, (2) the GUI display for one of the team members, (3) a non-geographical "map" that shows where the agents are during each phase of the demo (e.g., machine, arrival time, departure time), and (4) other displays that show technical details of specific subsystems (such as a throughput and latency graph for the wireless routing software). The map will be dynamic, e.g., it will be a real-time display of the locations and tracks of team members and vehicles. All audience displays will be projected onto a large screen (we have sufficient screen space and projectors). The geographical and agent maps be projected during the entire demo; each technical display will be projected only during the associated demo phase.

Application components

The application, shown in the figure below, can be divided into four main components.

• Hypothesis tracker (component 2). The hypothesis tracker is an existing system that will serve as a sample data repository for the demo application. The hypothesis tracker accepts observations from field units; these observations contain a vehicle description, location, heading and speed (e.g, a large truck heading west at approximately 50 miles per hour at GPS position ...). The hypothesis tracker uses several statistical techniques to make an "educated guess" as to which observations correspond to the same vehicle. Observations corresponding to the same vehicle make up a track.

  The observations are structured as SALUTE records. The tracker stores each received observation in a SALUTE relational database, and each time that it constructs a new set of tracks, it will add the tracks to the database, replacing the previous set of tracks. The database will have two fields not present in the SALUTE definition: (1) a flag that indicates whether the entry is an observation or a track, and (2) for tracks only, a list of observation indices that specify which observations make up the tracks. The SALUTE database is used to answer queries about the current tactical situation. (The queries will be specified via an graphical interface and transformed into SQL behind the scenes. For example, the soldier might click a position on the map and then click on "Tell me what is near this position". This query would be turned into an SQL query against the tracks in the SALUTE database.) Typically, the database would be used for standing queries (e.g., continually tell a soldier what vehicles are near their position), but only the simplest standing-query functionality will be ready in time for the initial demo.

  In the initial version of the demo, the hypothesis tracker will run at some fixed, central location. In a later version, the hypothesis tracker itself will be able to move to the most advantageous network location (e.g., the network location that minimizes the average latency between itself and the current set of observers).

  The hypothesis tracker is not one of the key technologies that are being developed as part of the MURI project (although it is under active development at Dartmouth). It is simply a useful "glue" component for the rest of the application.

• Observation delivery (component 1). Observations must be delivered from mobile team members to the hypothesis tracker (and its SALUTE relational database). Since field units will typically have an unreliable wireless link into the network, multiple copies of the same observation must be sent along multiple network paths to ensure timely delivery. For this initial version of the demo, we will will use a simple, randomized replication strategy. For later versions, we will use different replication strategies for different network environments and for different priority messages. (Attaching priorities to the observations is important, but is beyond the scope of the initial version.) To allow rapid introduction of replication new strategies into the system, observation delivery is performed by mobile agents, i.e., each observation is carried by a mobile agent that can decide ``on-the-fly'' which network path to follow and when and where to replicate itself.

  The main difficulty here is that the current D'Agents system is based around high-level languages such as Tcl and Java, which are too slow to allow the most efficient low-level routing. These languages are sufficient for our prototype application, however.

  This component relies on the mobile-agent infrastructure and, most importantly, the wireless packet-routing software from Harvard and Dartmouth. In addition, Illinois has developed several flow-control algorithms, as well as an algorithm for dynamically changing the transmission power of each wireless node (to minimize interference while still ensuring connectively). We will probably run out of time, however, before we can integrate the Illinois algorithms into the initial prototype; instead these algorithms will be used in the next prototype.

• Queries (component 3). Team members can make queries against the hypothesis tracker and the various databases. In the most general case, a team member will send an agent to the hypothesis tracker (and its associated SALUTE database) to identify which objects are near her current position (or headed towards her, or headed towards her with a certain expected interception time, or ...). Then the agent will move on to the black-gray-white and textual databases to find any information relating to those objects. (For this initial demo, the team member will be able to select a query type and specify parameters, but the databases that should be visited for each query type will be hardwired.) Once the agent has the results, it returns to the team member's laptop and presents those results.

  In a more specific case, interview teams will be making queries against just the black-gray-white and textual databases as new information comes to light during the interviews.

  As part of the result presentation, the text documents are automatically clustered into related groups so that the user can browse the documents easily. The tracks themselves will be displayed on a map so that the user can visualize the current positions of the objects of interest.

  Finally, the same routing techniques that were used for observation delivery will be used here to ensure timely delivery of the query and the query results.

  The advantage of mobile agents in the query component is twofold: (1) the agent can continue its task even if the field unit disconnects from the network, and (2) the agent minimizes the amount of intermediate results that are transferred across the typically low-bandwidth network that connects the field unit to the central network. To fully demonstrate the first advantage, at least one query must be made from a laptop that then disconnects from the network for some reason, and this query must be time critical. When the laptop reconnects, the query results are available immediately, since the mobile agent continued its task while the laptop was disconnected.

  The exact queries that will be performed as part of the demo are unclear. We need to talk more with AlphaTech and Lockheed-Martin. Right now the Dartmouth demo team is programming "building-block" query agents, each one performing queries against a single specific databases. These "building-block" query agents can be combined to perform more complex queries against multiple databases.

• GPS units (component 4). All field units are equipped with GPS units. The field unit's current position, taken from the GPS unit, will be automatically included in the observations and in the queries.

  We currently have eight GPS units. We need five more for the scenario discussed above (i.e., four GPS units for vehicle observers, two GPS units for the marked vehicles, one GPS unit for the stationary laptop, and six GPS units for the arrest team). Dartmouth will order five more GPS units immediately.

• Other components (not shown).

  P.R. Kumar at the University of Illinois is developing a simulation testbed for ad-hoc networks, and Gul Agha at the University of Illinois has developed a Java-based mobile-agent system that uses the actor model. This mobile-agent system includes several abstractions (such as synchronization, itineraries, resource-management constructs and various communication mechanisms) that will be useful to a mobile-agent programmer. It is unlikely that this mobile-agent system can be integrated with D'Agents before fall.

  In addition, Dartmouth and RPI have developed several network-sensing and planing algorithms that an agent can use to decide which copy of a database to visit, which database to visit first, and so on. If time allows, these algorithms will be included in a limited way in the query part of the demo.

Application figure