Density- and Asymmetry-adaptive Wireless Network (DAWN)

DARPA GloMo Phase II project
BBN Technologies (A Division of GTE)

DAWN is a research project being conducted at GTE Internetworking (BBN Technologies) and sponsored by DARPA Information Technology Office as part of the Global Mobile Information Systems (GloMo) program.

In tactical mobile wireless networks, the confluence or dispersion of troops causes continual and rapid changes in network density, while the heterogeneity of network elements induces link asymmetry. Variations in density and asymmetry pose several problems in network connectivity, routing scalability, jammer vulnerability, and real-time multimedia transport -- problems that are not addressed by existing systems. For instance, in the illustration here, an "attacking" posture (far left) is characterized by high density and a "defensive" one by low density. The differing capabilities of transceivers in soldiers, vehicles, aircraft induce asymmetric links. Protocols must be adaptive to density changes and accommodate link asymmetry and unidirectionality.

As part of this project, we shall develop a modular set of density- and asymmetry adaptive wireless networking (DAWN) mechanisms that will provide flexible, survivable, and scalable solutions for such problems. The DAWN system will build upon and complement BBN's existing Multimedia Support for Mobile Wireless Networks (MMWN), and extend its ability to operate under a wide range of network densities and link asymmetries . The combined MMWN/DAWN system will be of significant benefit in heterogeneous and dynamic wireless networks, particularly in the tactical arena. The DAWN modules are also designed to be integratable into other GloMo systems that need density and asymmetry adaptation. The integrated MMWN/DAWN architecture is illustrated below.

There are four inter-related, but separable mechanisms that are being developed:

The DAWN autonomous topology control mechanism computes values for parameters, such as node transmission power and antenna direction to create and adaptively maintain the network topology that best meets application quality-of-service requirements.
In order to enable routing to scale to high densities and provide application-specific tradeoffs, a versatile density-adaptive routing algorithm will be designed using a variation of the link-state routing approach.
Active mechanisms for jammer evasion will be designed, whereby nodes may cooperatively detect a jammer's location and take evasive action, while maintaining network connectivity.
Finally, we plan to extend the MMWN algorithms to accommodate asymmetric and unidirectional links, in particular, enable separate uplink and downlink affiliations, and enable asymmetric virtual circuits.
The DAWN modules will be implemented using the C++ Protocol Toolkit (CPT), developed by Rooftop Communications, and can be used as a simulation system to study the performance using network modelling, or in real-life using a testbed consisting of Wings routers (Rooftop) and Utilicom Longranger radios.

Details of the modules

People involved

Viewgraphs describing the project

Technology transfer

Related publications

Details of the modules

1. Autonomous topology control.

In most environments, and especially in tactical military environments, it is of paramount importance that the communication network be connected at all times. When the network infrastructure consists of mobile switches, the connection survivability (i.e., the probability of retaining a connection between representative pairs of nodes) is a non-trivial function of the switch locations, terrain, transmission and reception capabilities. Left uncontrolled, the network may experience frequent degradation in connection survivability -- periods in which user communication in the network may be seriously compromised.

Of equal importance is the need to keep the node degree (i.e., the number of nodes that are "neighbors" of this node) as small as possible, in order to reduce interference. Left uncontrolled, the network may experience a severe degradation in network capacity, thereby making it unsuitable for carrying real-time multimedia traffic.

The two desired goals -- connection survivability and node degree -- are contradictory in nature, and hence, optimizing both simultaneously is difficult. Rather, we need to reduce node degrees as much as possible without making the network disconnected. This is a challenging task that requires that node parameters such as transmit power and antenna direction be controlled on a per-node basis to achieve the network topology. Further, such control must be done autonomously since the time-to-react is very small, must be done in a de-centralized fashion for fault-tolerance, and must be efficient and simple to implement.

In the first phase of the development of the Autonomous Topology Control (ATC) module, we are focusing on decentralized algorithms that attempt to keep the network biconnected (i.e., with at least two edge disjoint paths between any pair of nodes) by using the smallest possible transmit power for each node. We are developing two algorithms, each of which has a different approach to the way in which "global coordination" of transmit power changes is done. The two approaches have different tradeoffs between simplicity, control overhead and effectiveness and are targeted for different application and network environments.

From a more general perspective, it is not only important whether the network is connected, but also how the network is connected. The latter is important because in order to meet service requirements for applications, there are constraints on what the network topology can be. In the second phase of the ATC development, we plan to implement decentralized algorithms that, given requirements for end-to-end hops, multiple-path redundancy, interference ceilings, etc., will control in real-time a node's transmission power, and if possible, transmission direction to create a topology with the desired parameters.The constraints are derived from service requirements such as end-to-end delay requirements (for number of hops). While the details of this derivation will not be the primary focus of our effort, we hope to outline methodology, based on simulation results, that will enable a network operator to specify these constraints.

2. Density-adaptive routing

Changes in density induced by mobility have two major implications for routing.

The routing overhead is a non-trivial function of density. The routing overhead of traditional routing approaches such as distance-vector and link-state routing in a mobile environment is proportional to the number of connectivity changes (link up/downs) that happen due to mobility. Our simulation results have shown that the frequency of connectivity changes first increases and then decreases with increasing density. Thus, routing must be density-adaptive so that routing is efficient over a range of network densities.
Requirements of routing vary with density. Different tradeoffs between overhead and performance are appropriate at different density levels. At one extreme, we may have such high densities that all nodes are within one hop of each other in which case there is simply no need for routing information dissemination, and a routing protocol will only consume precious bandwidth. At the other extreme, a sparsely connected network with a large diameter requires a sophisticated routing scheme since path optimality becomes important. Since a separate routing protocol for each density level is clearly impractical, we need a density-adaptive routing algorithm.

Our solution to density-adaptive multipoint routing is based on novel "nearsighted" link-state algorithm In nearsighted link-state routing, the propagation of event-driven link state updates is restricted to nodes within r hops of the originator. This limits the message overhead in response to connectivity changes. Each node thus knows the up-to-date connectivity of the region within a radius of r hops from itself and can do shortest-path routing within this region, in particular, to the ``boundary'' of the region. In turn, a node at this boundary will have its own region of sight which enables it to route a further r hops from itself, and so on. For routing across boundaries, a number of different schemes are possible, each with its own tradeoffs. We are currently investigating 4 schemes -- GPS position assists, sink-tree generation, exploratory packets and periodic timer frequency-control for integration with nearsighted link-state routing.

3. Jammer Evasion

In a mobile wireless network such as a tactical network, one can expect both fluctuating network density and the presence of ill-behaved nodes. The density of an area within the network may change frequently and unpredictably as nodes move into and out of that area in response to tactical operations. Nodes may malfunction (e.g., transmission power sticks at a high level) or may actively seek to disrupt communications. Thus, in a tactical network, interference may result not only from suboptimal assignment of multiple access parameters and power levels due to changes in network density, but also from jamming caused by both benign (but damaged) and hostile nodes. Therefore, conventional power control and multiple access techniques that successfully reduce interference in benign and relatively stable environments may not be sufficient in tactical networks. We intend to focus on the problem of minimizing transmission interference in tactical wireless networks, exploring passive techniques for interference reduction as well as active techniques for jammer evasion.

We propose to explore a number of active techniques for reducing interference in networks with fluctuating densities and jamming sources. Specifically, we will investigate means for detecting interference (directly at a receiving node and indirectly at a transmitting node), for determining the cause of perceived interference (e.g., an increase in the number of nodes in a given vicinity or an isolated jammer), and for altering the environment (e.g., changing codewords, antenna direction, or even location) to reduce the interference. The efficacy of these techniques will depend on the capabilities of the radios on which they are implemented; not all techniques will be appropriate for all radios. We expect that many of the approaches we investigate will make use of heuristics for detecting interference, determining its cause, and taking corrective action. Moreover, we expect that stochastic approaches to alleviating interference (e.g., randomly selecting a new frequency set for frequency hopping or making a small movement in a random direction) will reduce interference in both benign environments with fluctuating network density as well as hostile environments populated by jammers. Such stochastic actions not only help to separate transmissions but also are not predictable, and hence a jammer cannot respond rapidly to exploit the new situation.

We will assess the relative performance of the various techniques will be evaluated through simulation. The use of a simulator enables us to experiment with a wide variety of network topologies, traffic patterns, jamming sources, and interference reduction algorithms. The results will be a set of techniques to reduce interference, how and when to use them effectively, and a comparative analysis of their performance.

4. Asymmetry/Unidirectionality Accommodation

In a heterogeneous network, the diverse power and transceiver capabilities of the nodes may result in asymmetry in transmission and reception. Asymmetric links are likely to be common in future military networks where the transmission powers of network elements may range from very low (mobile sensors), to medium (soldiers carrying battery packs), to high (battle tanks and vehicles), to very high (control towers drawing power from the main supply). The anticipated digital battlefield communication environment is likely to include diverse technologies such as satellite-based personal communications systems (PCS), direct broadcast systems, unmanned airborne vehicle relays, terrerstrial PCS, etc. -- a veritable recipe for asymmetry. A special case of an asymmetric link is a unidirectional link, on which only one-way communication is possible. For instance, a link between a satellite and a satellite-dish equipped receiver, or a link between a mobile wireless sensor and a control tower are typically unidirectional.

Our work on asymmetry/unidirectionality accommodation is in three parts:

Asymmetric Virtual Circuits. In most current systems, virtual circuits use the reverse of the data path for virtual circuit control information. If the forward path has one or more unidirectional links, then this reverse path would not exist. We are extending the MMWN dynamic multipoint virtual circuit mechanisms so that the control information such as the ``accept'' messages will not have to return on the reverse of the established data path. Instead, the virtual circuits will use separate paths for forward data flow and reverse control flow.

Neighbor discovery and routing with unidirectional links. In order to be able to set up virtual circuits in a unidirectional environment, the generation of routes must accommodate unidirectional links. Current link-state protocols send outgoing links or bidirectional links in their link-state updates. In our solution, link-state routing will maintain separate neighbor relationships to handle incoming and outgoing transmissions. Nodes will provide, in their link-state updates, the set of incoming rather than outgoing links.

Asymmetric endpoint (cell) affiliations. The primary challenge in establishing an asymmetric affiliation is to enable an endpoint to discover and select a switch for downlink communications without being able to communicate directly with that switch. In order to accomplish this, we shall design novel algorithms that use a multihop handshake instead of the traditional single-hop handshake to enable asymmetric affiliation in the face of node mobility.

People Involved

The BBN DAWN team has four people whose collective expertise on network layer protocols and packet-radio networking is unique.

Jack Dietz

Regina Hain

Ram Ramanathan (P.I)

Martha Steenstrup

Jack Dietz is a software engineer with over 3 years' experience in the design and implementation of software systems. Prior to DAWN, Jack designed and implemented large parts of the External Route Intrusion Detection System (ERIDS), including the expert system for scoring BGP message veracity. He received his Master's in Computer Science from the University of California, San Diego in 1997, with a thesis on a virtual circuit based adaptive bandwidth management scheme. He is presently modelling, simulating and evaluating key parts of the MMWN/DAWN system.

Regina Rosales-Hain is a senior engineer with over 8 years experience in implementing network protocols. She has designed and implemented key parts of the BBN T-10 Internet Router, the Inter-Domain Policy Routing (IDPR) system, and was the lead software engineer for the MMWN project. Possessing a versatile skill set, Regina is equally at home with tasks ranging from distributed algorithm implemention to testbed assembly and troubleshooting - making her a perfect match for DAWN. Regina has a B.S from Princeton University, and an M.S. from Boston University. Regina is the lead software engineer for DAWN.

Ram Ramanathan is a division scientist at BBN and the prinicpal investigator for DAWN. His background is in the design and implementation of network and medium access layer protocols for both wireline and wireless packet radio networks. He has about 8 years' experience, most of it at BBN where he worked on the IDPR and Nimrod Internet routing systems, and on MMWN, all DARPA projects. He has over 10 publications in reputed journals and conferences, and has won the outstanding publication awards at IEEE Infocom and ACM Sigcomm conferences. Ram has a Ph.D from the University of Delaware. He is the lead designer for the Autonomous Topology Control, Routing, and Asymmetric affiliation mechanisms.

Martha Steenstrup is a principal scientist at BBN. She has been the principal investigator for four DARPA-funded projects including IDPR (inter-domain policy routing), Nimrod (routing in large, heterogeneous, and dynamic internetworks), MMWN (support for real-time, distributed, multimedia applications in mobile wireless networks), and robust, efficient algorithms for self-structuring large
networks. She has also worked on the DARPA SURAN program. Martha is the author of one book and several publications in the field of networking and is the editor of Computer Communications Review and on the Program Committee of ACM Mobicom, ACM Sigcomm, and IEEE Infocom conference. Martha holds a Ph.D. from the University of Massachusetts at Amherst. She is the lead designer for the Jammer Evasion and the Asymmetric VC mechanisms.

Technology Transfer

The DAWN team is working with a number of other groups within and outside of GloMo to help in the transfer of MMWN/DAWN technology to the battlefield and commercial arena. A brief summary is given below.

As part of another GloMo phase II effort, BBN is teamed with ITT Aerospace, Clemson University and TechnoSciences Inc. to build an All-Informed Voice support over the Handheld Multimedia Terminals (HMTs). Specifically, we are working on using the MMWN elastic virtual circuits for providing voice support. Future evolution of this network would require solutions to the density and asymmetry problems, which could be provided by DAWN. Along with University of Texas, Dallas, BBN is working on a project entitled "A Generic Control Channel mechanism for Mobile Multi-hop Networks", another GloMo phase II project, in which we are adapting the Time Spreading Multiple Access (TSMA) protocol to work as a control channel mechanism within the MMWN/DAWN system. BBN is the technical lead on a team composed of several organizations working on the On-Board Switch (OBS) project. The topology control and asymmetry handling mechanisms are directly applicable to the problem of crosslink management in the OBS system. The DAWN and OBS teams have been working together on a technology transfer path for this.