DIMACS Workshop on Pervasive Networking

May 21, 2001
DIMACS Center, Rutgers University, Piscataway, NJ

Organizers:

Badri Nath, Rutgers University, badri@cs.rutgers.edu

Deborah Estrin, University of California at Los Angeles, destrin@cs.ucla.edu

Abstracts:

1.

Bluetooth Vs. 802.11b: State-Of-The-Art And Future Trends

Pravin Bhagwat, ReefEdge Networks

The promise of untethered computing in the workplace is becoming
a reality.  IEEE 802.11b, the 11Mbps wireless LAN standard, has
finally arrived, and early market response has been positive. 
As the WLAN market takes off, Bluetooth, another emerging standard
for short-range wireless networking, is also gathering force.
Several vendors have demonstrated Bluetooth products, including
cordless headsets, PCMCIA cards, and LAN access points.  Both
standards are competing for the same airwaves, but are they also
chasing the same market?  Will Bluetooth and 802.11b compliment
each other, or will one technology eventually displace the other?



2.

Distributed Query Planning In A Sensor Network

Philippe Bonnet, Chang Choi, Cornell University
Daniel Mosse, University of Pittsburgh

Large collections of sensors with computation and multi-hop
communications capabilities form the underlying computing
infrastructure for a new generation of area monitoring applications.
These applications rely on filtering, correlation and aggregation
queries to access sensor data regardless of the physical organization
of the underlying sensor network.  Because each sensor disposes of 
a finite amount of energy provided by its batteries and because
it has been shown that the energy cost of sending data is orders
of magnitude higher than the cost of processing data locally, 
queries over a sensor network are best executed in a distributed
manner, within the sensor network.

In this talk, we will briefly review the data model and the query
language we have proposed for expressing queries over sensor
networks.  We will then show that classical distributed query
processing techniques are challenged in this new environment and 
we will introduce an architecture for distributed query processing 
within a sensor network.  We will detail the recent progresses we 
have made concerning two aspects of distributed query processing
namely a sensor node index structure that can be used to route
query fragments without flooding the network and hierarchical
scheduling algorthims for planning distributed query execution
given delay constraints.



3.

PARO:  Power-Aware Routing In Mobile Ad Hoc Networks

Andrew T. Campbell, Columbia University
Javier Gomez, IBM Research

Due to the fact that mobile ad hoc nodes have a critical need
to preserve battery power, MANET routing protocols need to 
consider power saving techniques during operations.  In this
talk we will discuss PARO, a Power-Aware Routing Optimization
protocol that minimizes the transmission power necessary to
forward packets between wireless devices.  Using PARO, intermediate
nodes can forward packets between source-destination pairs thus
reducing the aggregate transmission power consumed by wireless 
devices.  An important property of PARO is that it outperforms
traditional broadcast-based routing protocols due to its
power efficient point-to-point on-demand nature.  The protocol
is designed to operate as a stand-alone multihop routing
protocol for local-area wireless networks (e.g., single-hop
home networks, single-hop sensor networks, WLANS, etc.)
and as a power-aware enhancement for routing in wide-area
MANETs.



4.

Scalable And Adaptive Power Management For Multihop Ad Hoc
Networks

Benjie Chen, Kyle Jamieson, Hari Balakrishnan, Robert Morris, MIT

We present Span, a distributed coordination technique for multi-hop
ad hoc wireless networks that reduces energy consumption
without significantly diminishing the capacity or connectivity of
the network.  Span builds on the observation that when a region of 
a shared-channel network has a sufficient density of nodes, only
a small number of them need be on at any time to forward traffic
for active connections.  This provides a way to save energy and 
increase system lifetime by turning off "redundant" nodes, without
substantially altering the overall transit capacity of the network.

Span is a distributed, randomized algorithm where nodes make local
decisions on whether to sleep, or to join the forwarding backbone
as a coordinator.  Each node adapts to its local topology, basing
its decision on an estimate of how many of its neighbors will 
benefit  from it being awake, and the amount of energy available
to it.  We give a randomized algorithm where coordinators rotate
with time, demonstrating how localized node decisions lead to a 
connected, capacity-preserving global topology.  For example,
for a practical range of node densities, our simulations show
that the system lifetime with Span is more than a factor of two
better than without,  while maintaining the forwarding capacity
of the original network.  Span integrates nicely with 802.11--
when run in conjuction with the 802.11 power saving mode, Span
improves both communication latency and capacity without much
degradation in system lifetime.



5.

Autoconfiguration, Registration And Mobility Management For
Pervasive Computing

Subir Das and Anthonly Mcauley, Telcordia Technologies, Inc.
Archan Misra, IBM T.J. Watson
Sajal K. Das, University of Texas at Arlington

In the vision of pervasive computing, users will exchange information
and control their environments from anywhere using various wireline/
wireless networks and computing devices.  We believe that current
protocols, such as DHCP, PPP and Mobile IP, must be enhanced to
support pervasivenetwork access.

In particular, this presentation identifies three fundamental 
functions: autoconfiguration, registration, and mobility
management, that need such enhancements.  Realizing that the IP
autoconfiguration capabilities must be extended to configure routers
and large dynamic networks, we first describe our autoconfiguration
solution based on the Dynamic Configuration and Distribution (DCDP).
Secondly, we discuss why providing user-specific services over a
common infrastructure needs a uniform registration protocol, independent
of the mobility and configuration mechanisms.  We present an initial
version of the Basic User Registration Protocol (BURP), which 
provides secure client-network registration and interfaces to
AAA protocols such as Diamter.  Finally, we discuss the Dynamic
Mobility Agent (DMA) architecture, which provides a hierarchical
and scalable mobility management framework.  The DMA approach
allows individual users to customize their own mobility-related
features, such as paging, fast handoffs and QoS support, over a 
common access infrastructure and to select multiple globalbinding
protocols as appropriate.



6.

Prediction-Based Monitoring In Sensor Networks

Samir Goel, Tomasz Imielinski, Rutgers University

In this paper we discuss the problem of monitoring data
sensed in large sensor networks.  A sensor typically runs a
better having a limited lifetime.  In order to increase the
lifetime of a sensor it is important that the mechanisms used
in monitoring them be energy-efficient.  In this paper, we 
propose a new paradigm called Prediction-based monitoring
for energy-efficient monitoring.  We show that the paradigm
can be visualized as a watching of a "sensor movie" and that
concepts from MPEG may be applied to it.  We have implemented
the proposed algorithms in a testbed of Rene motes[Motes].
Experimental results show that the proposed solutions help
to significantly cut-down the number of data transmissions,
considerabley increasing sensor lifetimes, and thereby, the 
lifetime of the networks formed from these sensors.


7.

Challenges In Geographic Routing:
Sparse Networks, Radio Obstacles, and Traffic Provisioning

Brad Karp, ICSI, Berkeley, California

Greedy Perimeter Stateless Routing (GPSR) has been shown to scale well
for networks of numerous rapidly moving routers, by virtue of its
small state storage requirements at routers, low routing protocol
overhead, and the robustness with which it delivers applications'
packets.  The use of geographic information in packet forwarding
decisions is central to these properties.  We identify three challenges
in the advancement of such geographic routing systems:  sparse
topologies, where greedy forwarding is possible more rarely than
on dense ones; radio-attenuating obstacles, that introduce
non-uniformity in radio ranges; and traffic engineering for these
non-hierarchical routing systems.  Using simulation, we describe
the role of network density in the performance of geographic routing
schemes, and show that GPSR performs well on sparse networks.  We 
describe the difficulties presented by non-uniform radion ranges.
Finally, we harness the correlation between geography and capacity
in wireless networks to propose a "geographic" approach to traffic
engineering that increases the capacity of a geographically routed
network by "spatially" distributing flows.



8.

Compiler Support For Power And Energy Management

Uli Kremer, Rutgers University

Effective power and energy management is important to prolong
batter life and to reduce heat dissipation.  Developing compile-time
techniques for application specific power and energy management is
an exciting challenge.  In this talk, I will discuss several possible
optimization techniques, with an emphasis on remote task execution.
Experiments to support the benefit  analysis were performed on SKIFF,
a StrongARM based single board system developed at Compaq's Cambridge
Research Lan (CRL).  An addition, we report performance numbers on
Compaq's iPAQ handheld PC.



9.

Hierarchical Power-Aware Routing In Sensor Networks

Qun Li, Javed Aslam, Daniela Rus
Department of Computer Science, Dartmouth College

This paper discusses online power-aware routing in large sensor
networks.  We seek to optimize the lifetime of the network.  We
develop an approximation algorithm called max-min zP_min that has
a good empirical competitive ratio.  To ensure scalability, we
introduce a hierarchical algorithm, which is called zone-based
routing.



10.

Connection Establishment In The Bluetooth System

Ivana Maric, WINLAB, Rutgers University

Any communication between hosts in the Bluetooth system is preceded by a
connection establishment procedure comprising two steps.  The first step,
referred to as Inquiry, enables hosts to learn about other hosts in their
range.  Inquiry can be omitted when not needed.  The second step in
which a host synchronizes and starts communication with the intended
host is called Page.  The complexity of the connection establishment
procedure stems from the fact that hosts use different hopping sequences
before a connection is established.  The set-up delay is also affected
by the requirement of low-power consumption and the possible connections
that hosts may already have.  The delay introduced by the procedure may
impose constraints on applications such as ad hoc networking and LAN
access.

In this paper, the connection establishment procedure in the Bluetooth
system is modeled.  The analytical results on mean page duration are
derived for paging modes defined by the Bluetooth  Specification.  In
a channel with packet errors, we derive analytical results for the average
page duration as a function of the length of a page scan interval.

Analytical and simulation results show the range of values for the average
page duration between two hosts.



11.

Communication Support For Location-Centric Collaborative
Signal Processing In Sensor Networks

P. Ramanathan, K.-C. Wang, K.K. Saluja, T. Clouqueur
University of Wisconsin-Madison

Smart, low-cost devices, containing multiple sensors integrated
with short-range wireless communication and significant embedded
processing capabilities are expected to be a technological reality
in the near future.  These devices can be deployed in large numbers
to form a wireless ad hoc network with significant compute capabilities
to carry out mission-critical taskes such as monitoring, detection,
and tracking of threats in the deployed area.  In such networks,
each device by itself may not be able to provide useful information
without collaboration with other devices.  At the same time, due to
the large ad hoc nature of these networks, it is a formidable 
challenge for a programmer to develop efficient distributed
algorithms and implementations without a simple, but flexible,
programming model.

This paper descibes an approach called location-centric computing
for addressing this challenge.  The proposed approach is based on
the observation that distributed computations in sensor networks
typically require tight collaboration among devices in a certain
geographic area and not among an arbitrarily specified set of 
devices.  The paper describes a set of communication primitives
well-suited for such location-centric distributed computing.  
The paper also compares the number of messages required for an
example collaborative signal processing application, namely
target tracking, in the proposed approach with that required
in other well-known approaches in literature.  The comparison
shows that the proposed approach is better in terms of number
of messages required for this application.



12.

Cooperative Computing:  A Computing Model For Large Networks
Of Embedded Systems

Phillip Stanley-Marbell, Cristian Borcea, Kiran Nagaraja,
Liviu Iftode, Rutgers University

To benefit from the aggregated computing resources deployed in
large networks of embedded systems, new computing models and
system architectures must be employed, which will necessarily
be different from the traditional distributed computing models.

Presented is a model and architecture for distributed computing over
large scale ad-hoc networks of embedded systems.  In Cooperative
Computing, applications execute on a set of nodes identified by their
properties, and are responsible for the discovery of these nodes in
the network.  The system architecture we propose to implement this
model is called Smart Messages.  Smart messages are comprised of code
and data and execute on each hop in their path through the network.
Nodes support the execution of smart messages by providing a virtual
machine and a name-based memory region called the Tag Space.

We believe the Cooperative Computing and Smart Messages can provide
an adequate programmable infrastructure for pervasive networks of
embedded systems such as sensor networks and computational fabrics.
We are currently prototyping this architecture using uCsimm
microcontrollers, uCLinux, Sun Microsystem's KVM virtual machine
and Bluetooth wireless networking.



13.

Automatic Configuration Management In Dynamic Short-Lived Networks

Raj Rajagopalan, Telcordia Technologies

Today's network management techniques are designed for long-term
usage of networks and while this approach is acceptable for networks
in general, it is quite inadequate in some common network scenarios
where the network exists for a very small period of time.  Such
networks are quire common in the military in forward-deployed networks
in combat or rescue situations as well as in the civilian sector,
examples being disaster areas, trade shows, touring groups, 
and sporting events.  We call networks with a defined lifetime
"Rapid Response Networks" or "Disposable Networks" and argue that
radically new management techniques are needed for success in
mission-critical tasks in such arenas.  We propose that reseach
needs to be done on the question of what would we do for the 
specified span of time.  This turns out to be fertile ground with
many open questions, some that can be solved quickly and others
that need concerted and collaborative effort.  This is joint work
with Badri Nath, Nick Maxemchuk, Muthu Muthukrishnan and Fred
Roberts.  We will also briefly review some of the lessons learned
in creating new tools for configuration management in an ongoing
project at Telcordia Technologies that focuses on automating
security policy management.




.




.




.




.




.




.




.




.



.




.




.




.

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage