Abstracts for Pravin P. Varaiya

The EECS Research Summary for 2003

WTRP: Wireless Token Ring Protocol

Mustafa Ergen, Duke Lee, Ruchira Datta, Anuj Puri1, and Raja Sengupta2
(Professor Pravin P. Varaiya)
CALTRAIN and (ONR) N00014-00-1-061

Wireless token ring protocol (WTRP) is a medium access control (MAC) protocol for wireless networks. The MAC protocol, through which mobile stations can share a common broadcast channel, is essential in wireless networks. In an IEEE 802.11 network, the contention among stations is not homogeneous due to the existence of hidden terminals, partially connected network topology, and random access. Consequently, quality of service (QoS) is not provided. WTRP supports guaranteed QoS in terms of bounded latency and reserved bandwidth, which are crucial real-time constraints of the applications. WTRP is efficient in the sense that it reduces the number of retransmissions due to collisions. It is fair in the sense that each station uses the channel for an equal amount of time. The stations take turns transmitting and are forced to give up the right to transmit after transmitting for a specified amount of time. It is a distributed protocol that supports many topologies since not all stations need to be connected to each other or to a central station. WTRP is robust against single node failure. WTRP recovers gracefully from multiple simultaneous faults. WTRP has applications to inter-access point coordination in ITS DSRC, safety-critical vehicle-to-vehicle networking, home networking, and provides extensions to sensor networks and Mobile IP.

1Postdoctoral Researcher

More information (http://www.eecs.berkeley.edu/ergen) or

Send mail to the author : (ergen@eecs.berkeley.edu)

Multihop Routing Extension to the IEEE 802.11 Wireless LAN Standard

Mustafa Ergen
(Professor Pravin P. Varaiya)
National Semiconductor and Office of Naval Research

Wireless communications have rapidly evolved in the recent decade. Increasing desire to provide connectivity for mobile computers and communication devices is firing an interest in wireless networks. Future communications will employ high speed wireless systems in the local area, low-speed wireless systems in the wide area, and utilize high capacity wired media in the metropolitan environment.

In order to achieve the goal of offering broadband communication services and providing universal connectivity to mobile users, the standards for wireless local area networks (WLANs) are designed and an approach to interconnect these WLANs to the existing wired LANs and wide area wireless network are developed. Study group 802.11 was formed under an IEEE project to recommend an international standard for WLANs. The scope of the 802.11 study group is to develop MAC and physical layer standards for wireless connectivity within a local area. IEEE adopted the first standard [1] in 1997 and revised it in 1999.

Although IEEE 802.11 can be extended to a multihop architecture, currently, it is implemented for a single hop architecture. Building a large number of access points (APs), for example, in a metropolitan area with a dense population, has a high cost. In fact, there are other kinds of networks, namely, packet radio or ad hoc networks, in which no APs are needed. One of the advantages of these networks is low cost because no infrastructure is needed and the networks can be deployed instantly. However, these ad hoc networks may be limited to specialized applications, such as battlefields and traveling groups, due to the vulnerability of paths with many possible mobile stations. Nevertheless, this vulnerability can be greatly reduced if the number of wireless hops can be limited and the station mobility is not high.

This project is concerned with a proposal to give mobile stations forward information when they are neither the initial transmitter nor the final receiver.

M. Ergen and A. Puri, "MEWLANA-Mobile IP Enriched Wireless Local Area Network Architecture," IEEE Vehicular Technology Soc., Vancouver, Canada, September 2002.

More information (http://www.eecs.berkeley.edu/~ergen) or

Send mail to the author : (ergen@eecs.berkeley.edu)

PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks

Sinem Coleri
(Professor Pravin P. Varaiya)
Office of Naval Research

We propose a novel channel access scheme that exploits the application-specific characteristics of sensor networks to meet their power, real-time deadline, fairness, and congestion control requirements. The primary characteristic of the sensor network is that the destination of all the data packets in the network is a central data collector. This central data collector, which is usually denoted as an access point, has unlimited power, whereas sensor nodes have one-battery power for remaining alive for several years. Our protocol PEDAMACS uses the access point to directly synchronize and schedule all the nodes in the network by increasing its transmission power. After learning the topology information, which includes the neighbor and the next hop to reach the access point, of all the nodes in the network in topology learning and topology collection phases, the access point explicitly schedules the node transmissions and announces this schedule to all the nodes. Assuming that the nodes generate packets periodically at the same rate, we described the goal of the scheduling algorithm to be minimizing the time necessary for all the packets to reach an access point where each node has exactly one packet at the beginning. After proving the NP-completeness of the problem, we developed a polynomial time algorithm that can guarantee an upper bound on the maximum delay experienced by the packets, which is proportional to the number of the nodes in the network. Simulations performed in TOSSIM, which is a simulation environment for TinyOS, show the efficiency of the proposed scheme compared to the conventional random access scheme in terms of power and delay.

More information (http://www.eecs.berkeley.edu/~csinem) or

Send mail to the author : (csinem@eecs.berkeley.edu)

Constrained Optimization Routing and Its Applications

Zhanfeng Jia
(Professor Pravin P. Varaiya)
(DARPA) IPTO N66001-00-C-8062

The study of the constraint optimization routing (COR) problem is motivated by recent research efforts on the QoS routing problem of the communication network. QoS routing leads to a series of problems including link state advertisement, path selection, admission control, path setup, and path maintenance. The COR problem focuses on finding a path through the network that satisfies the QoS requirements. Conventional routing protocols characterize network links by a single metric, such as hop count. Routing protocols like RIP or OSPF find the shortest path based on this metric. For routing that supports QoS requirements, the link model must include multiple parameters such as bandwidth, cost, delay, delay jitter, loss probability, and so on. Routing protocols then become more complicated because they must find paths that satisfy multiple constraints.

The COR problem has many applications in a variety of areas such as management of transportation systems, decision-making, and mission planning. For example, in the Mixed Initiative Control for Automa-teams (MICA) Project, the unmanned aerial vehicles, or UAVs, want to destroy valuable targets subject to possible attacks from these targets, limited fuel, and other obstacles. This path planning problem can be easily abstracted as a COR problem with constraints of hazard, path length, etc.

A latest research effort is to build a dynamic routing algorithm with traffic engineering (DRATE) framework under the structure of the COR problem. In this framework, flows come and are routed one by one with specific link metric sets. These link metric sets are calculated based on dynamic flow information in real time, such that traffic engineering objectives are achieved. The key techniques are (1) to map the traffic engineering objectives appropriately into link metric sets, and (2) to integrate multiple objectives and fit the COR structure.

Send mail to the author : (jia@eecs.berkeley.edu)