DIMACS Workshop on Pervasive Networking

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

Badri Nath, Rutgers University, badri@cs.rutgers.edu
Deborah Estrin, University of California at Los Angeles, destrin@cs.ucla.edu
Presented under the auspices of the Special Focus on Next Generation Networks Technologies and Applications.



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
Contacting the Center
Document last modified on May 29, 2001.