CPSC 434/534: Topics in Networked Systems, Spring 2017 : Course Info

Home  –  Overview  –  Schedule  –  Readings  –  Resources

Vision and driving applications

Abstract: Ubiquitous computing is the method of enhancing computer use by making many computers available throughout the physical environment, but making them effectively invisible to the user. Since we started this work at Xerox PARC in 1988, a number of researchers around the world have begun to work in the ubiquitous computing framework. This paper explains what is new and different about the computer science in ubiquitous computing. It starts with a brief overview of ubiquitous computing, and then elaborates through a series of examples drawn from various subdisciplines of computer science: hardware components (e.g. chips), network protocols, interaction substrates (e.g. software for screens and pens), applications, privacy, and computational methods. Ubiquitous computing offers a framework for new and exciting research across the spectrum of computer science.

Three issues: wireless networking, mobility, and portability.

Abstract: A confusing array of new wireless 搖ntethered?communications services, for voice and data, in real-time or delayed, interactive or one-way, in-building or out-of-doors, are rapidly becoming available. In this paper, we argue that despite the widely varying issues of engineering that span the creation of these diverse wireless services, the unique underlying aspect is that they must be able to adapt to a constantly changing environment brought on by mobility. Mobile systems must be able to detect their transmission environment and exploit knowledge about its current situation, so-called 搒ituation awareness,?to improve the quality of communications. Handoff in cellular phone systems is one example of detection and reaction to the environment.

Mobility requires adaptability. By this we mean that systems must be location and situation-aware, and must take advantage of this information to dynamically configure themselves in a distributed fashion.

Abstract: This paper is an answer to the question: "What is unique and conceptually different about mobile computing?" The paper begins by describing a set of constraints intrinsic to mobile computing, and examining the impact of these constraints on the design of distributed systems. Next, it summarizes the key results of the Coda and Odyssey systems. Finally, it describes the research opportunities in five important topics relevant to mobile computing: caching metrics, semantic callbacks and validators, resource revocation, analysis of adaptation, and global estimation from local observations.

Abstract: Nomadic computing and communications is upon us. We are all nomads, but we lack the systems support to assist us in our various forms of mobility. In this paper, we discuss the vision of nomadicity, its technical challenges, and approaches to the resolution of these challenges. One of the key characteristics of this paradigm shift in the way we deal with the information is that we face dramatic and sudden changes in connectivity and latency. Our systems must be ``nomadically-enabled'' in that mechanisms must be developed that deal with such changes in a natural and transparent fashion. Currently, this is not the case in that our systems typically treat such changes as exceptions or failures; this is unacceptable. Moreover, the industry is producing ``piece parts'' that are populating our desktops, briefcases and belt-hooks, but that do not interoperate with each other, in general. We require innovative and system wide solutions to overcome these problems. Such are the issues we address in this paper.

Abstract: This paper summarizes the results of the BARWAN project, which focused on enabling truly useful mobile networking across an extremely wide variety of real-world networks and mobile devices. We present the overall architecture, summarize key results, and discuss four broad lessons learned along the way. The architecture enables seamless roaming in a single logical overlay network composed of many heterogeneous (mostly wireless) physical networks, and provides significantly better TCP performance for these networks. It also provides complex scalable and highly available services to enable powerful capabilities across a very wide range of mobile devices, and mechanisms for automated discovery and configuration of localized services. Four broad themes arose from the project: 1) the power of dynamic adaptation as a generic solution to heterogeneity, 2) the importance of cross-layer information, such as the exploitation of TCP semantics in the link layer, 3) the use of agents in the infrastructure to enable new abilities and to hide new problems from legacy servers and protocol stacks, and 4) the importance of soft state for such agents for simplicity, ease of fault recovery, and scalability.

Abstract: Networked sensors-those that coordinate amongst themselves to achieve a larger sensing task-will revolutionize information gathering and processing both in urban environments and in inhospitable terrain. The sheer numbers of these sensors and the expected dynamics in these environments present unique challenges in the design of unattended autonomous sensor networks. These challenges lead us to hypothesize that sensor network coordination applications may need to be structured differently from traditional network applications. In particular, we believe that localized algorithms (in which simple local node behavior achieves a desired global objective) may be necessary for sensor network coordination. In this paper, we describe localized algorithms, and then discuss directed diffusion, a simple communication model for describing localized algorithms.

Abstract: As new fabrication and integration technologies reduce the cost and size of micro-sensors and wireless interfaces, it becomes feasible to deploy densely distributed wireless networks of sensors and actuators. These systems promise to revolutionize biological, earth, and environmental monitoring applications, providing data at granularities unrealizable by other means. In addition to the challenges of miniaturization, new system architectures and new network algorithms must be developed to transform the vast quantity of raw sensor data into a manageable stream of high-level data. To address this, we propose a tiered system architecture in which data collected at numerous, inexpensive sensor nodes is altered by local processing on its way through to larger, more capable and more expensive nodes. We briefly describe Habitat monitoring as our motivating application and introduce initial system building blocks designed to support this application. The remainder of the paper presents details of our

Experimental platform.

Abstract: This article addresses the challenges and opportunities of instrumenting the physical world with pervasive networks of sensor-rich, embedded computation. The authors present a taxonomy of emerging systems and outline the enabling technological developments.

Comment: related with Weiss's vision.

Abstract: In future smart environments, wireless sensor networks will play a key role in sensing, collecting, and disseminating information about environmental phenomena. Sensing applications represent a new paradigm for network operation, one that has different goals from more traditional wireless networks. This paper examines this emerging field to classify wireless micro-sensor networks according to different communication functions, data delivery models, and network dynamics. This taxonomy will aid in defining appropriate communication infrastructures for different sensor network application sub-spaces, allowing network designers to choose the protocol architecture that best matches the goals of their application. In addition, this taxonomy will enable new sensor network models to be defined for use in further research in this area.

Radio Propagations and Signal Modulation

Abstract: The dynamic and lossy nature of wireless communication poses major challenges to reliable, self-organizing multihop networks. These non-ideal characteristics are more problematic with the primitive, low-power radio transceivers found in sensor networks, and raise new issues that routing protocols must address. Link connectivity statistics should be captured dynamically through an efficient yet adaptive link estimator and routing decisions should exploit such connectivity statistics to achieve reliability. Link status and routing information must be maintained in a neighborhood table with constant space regardless of cell density. We study and evaluate link estimator, neighborhood table management, and reliable routing protocol techniques. We focus on a many-to-one, periodic data collection workload. We narrow the design space through evaluations on large-scale, high-level simulations to 50-node, in-depth empirical experiments. The most effective solution uses a simple time averaged EWMA estimator, frequency based table management, and cost-based routing.

Media Access Control

Abstract: In recent years, a wide variety of mobile computing devices has emerged, including portables, palmtops, and personal digit al assistants. Providing adequate network connectivity for these devices will require a new generation of wireless LAN technology. In this paper we study media access protocols for a single channel wireless LAN being developed at Xerox Corporation抯 Palo Alto Research Center. We start with the MACA media access protocol first proposed by Karn [9] and later refined by Biba [3] which uses an RTSCTS- DATA packet exchange and binary exponential backoff. Using packet-level simulations, we examine various performance and design issues in such protocols, Our analysis leads to a new protocol, MACAW, which uses an RTS-CTSDS- DATA-ACK message exchange and includes a significantly different backoff algorithm.

Comments: used in 802.11. extend MACA.

Abstract: We study the problem of media access control in the novel regime of sensor networks, where unique application behavior and tight constraints in computation power, storage, energy resources, and radio technology have shaped this design space to be very different from that found in traditional mobile computing regime. Media access control in sensor networks must not only be energy efficient but should also allow fair bandwidth allocation to the infrastructure for all nodes in a multihop network. We propose an adaptive rate control mechanism aiming to support these two goals and find that such a scheme is most effective in achieving our fairness goal while being energy efficient for both low and high duty cycle of network tracking.

COMMENT: 1) The network tends to operate as a collective structure, rather than supporting many independent point-to-point flows. Traffic tends to be variable and highly correlated. 2) The data that a networked sensor generates for each sample, such as a temperature value, is relatively small and, given the low bandwidth of the radio, data packets are kept small with a typical size around tens of bytes.

Abstract: This paper proposes S-MAC, a medium-access control (MAC) protocol designed for wireless sensor networks. Wireless sensor networks use battery-operated computing and sensing devices. A network of these devices will collaborate for a common application such as environmental monitoring. We expect sensor networks to be deployed in an ad hoc fashion, with individual nodes remaining largely inactive for long periods of time, but then becoming suddenly active when something is detected. These characteristics of sensor networks and applications motivate a MAC that is different from traditional wireless MACs such as IEEE 802.11 in almost every way: energy conservation and self-configuration are primary goals, while per-node fairness and latency are less important. S-MAC uses three novel techniques to reduce energy consumption and support self-configuration. To reduce energy consumption in listening to an idle channel, nodes periodically sleep. Neighboring nodes form virtual clusters to auto-synchronize on sleep schedules. Inspired by PAMAS, S-MAC also sets the radio to sleep during transmissions of other nodes. Unlike PAMAS, it only uses in-channel signaling. Finally, S-MAC applies message passing to reduce contention latency for sensor-network applications that require store-and-forward processing as data move through the network. We evaluate our implementation of S-MAC over a sample sensor node, the Mote, developed at University of California, Berkeley. The experiment results show that, on a source node, an 802.11 like MAC consumes 2? times more energy than S-MAC for traffic load with messages sent every 1?0s.

Comment: divide into frames. use virtual clustering.

Abstract: In this paper we describe T-MAC, a contention-based Medium Access Control protocol for wireless sensor networks. Applications for these networks have some characteristics (low message rate, insensitivity to latency) that can be exploited to reduce energy consumption by introducing an active/sleep duty cycle. To handle load variations in time and location T-MAC introduces an adaptive duty cycle in a novel way: by dynamically ending the active part of it. This reduces the amount of energy wasted on idle listening, in which nodes wait for potentially incoming messages, while still maintaining a reasonable throughput. We discuss the design of T-MAC, and provide a head-to- head comparison with classic CSMA (no duty cycle) and S-MAC ( xed duty cycle) through extensive simulations. Under homogeneous load, T-MAC and S-MAC achieve similar reductions in energy consumption (up to 98 %) compared to CSMA. In a sample scenario with variable load, however, T-MAC outperforms S-MAC by a factor of 5. Preliminary energy-consumption measurements provide insight into the internal workings of the T-MAC protocol.

Comment: improvement over the above S-MAC protocol by adapting the duration of the active part.

Abstract: Capacity improvement is one of the principal challenges in wireless networking. We present a link-layer protocol called Slotted Seeded Channel Hopping, or SSCH, that increases the capacity of an IEEE 802.11 network by utilizing frequency diversity. SSCH can be implemented in software over an IEEE 802.11-compliant wireless card. Each node using SSCH switches across channels in such a manner that nodes desiring to communicate overlap, while disjoint communications mostly do not overlap, and hence do not interfere with each other. To achieve this, SSCH uses a novel scheme for distributed rendezvous and synchronization. Simulation results show that SSCH significantly increases network capacity in several multi-hop and single-hop wireless networking scenarios.

Comment: see the talk by Nitin Vaidya on multiple-channel wireless networks.

Wireless Communication Environments

Capacity of Wireless Networks

Location Management

IP Mobility

Mobile IP
Micro Mobility
End-to-end Mobility

Routing in Wireless Networks: Ad Hoc Routing Protocols

Topology Control

Cooperative cell-based strategies have been recently proposed as a technique for extending the lifetime of wireless ad hoc networks, while only slightly impacting network performance. The effectiveness of this approach depends heavily on the node density: the higher it is, the more consistent energy savings can potentially be achieved. However, no general analyses of network lifetime have been done either for a base network (one without any energy conservation technique) or for one using cooperative energy conservation strategies. In this paper, we investigate the lifetime/density tradeoff under the hypothesis that nodes are distributed uniformly at random in a given region, and that the traffic is evenly distributed across the network. We also analyze the case where the node density is just sufficient to ensure that the network is connected with high probability. This analysis, which is supported by the results of extensive simulations, shows that even in this low density scenario, cell-based strategies can significantly extend network lifetime.

"Lifetime Analysis of a Sensor Network with Hybrid Automata Modelling," Sinem Coleri, Mustafa Ergen and T. John Koo, University of California, Berkeley. WSNA 2002.

Incentive Compatible Routing (and some other incentive papers)

Routing in Wireless Networks: Geographic Routing


Geographic Routing without Location Information

Broadcast in Wireless Networks

Transport Protocols

Mobile File Systems

OS Design

Abstract: Technological progress in integrated, low-power, CMOS communication devices and sensors makes a rich design space of
networked sensors viable. They can be deeply embedded in the physical world and spread throughout our environment like smart dust. The missing elements are an overall system architecture and a methodology for systematic advance. To this end, we identify key requirements, develop a small device that is representative of the class, design a tiny event-driven operating system, and show that it provides support for efficient modularity and concurrency-intensive operation. Our operating system fits in 178 bytes of memory, propagates events in the time it takes to copy 1.25 bytes of memory, context switches in the time it takes to copy 6 bytes of memory and supports two level scheduling. The analysis lays a groundwork for future architectural advances.

Comments: 1) Small physical size and low power consumption; 2) Concurrency-intensive operation; 3) Limited Physical Parallelism and Controller Hierarchy; and 4) Diversity in Design and Usage.

Service Discovery

Application Adaptation

Mobility: Coordinated, Controlled Mobility

Target Mobility: Tracking and Navigation

Software Mobility: Mobile Agents

Process Mobility: Process Migration

User Mobility

Cross Layer Design

In Network Processing and Aggregation

Topology Control: Coverage

Clock Synchronization


As sensor networks edge closer towards wide-spread deployment, security issues become a central concern. So far, the main research focus has been on making sensor networks feasible and useful, and less emphasis was placed on security. We design a suite of security building blocks that are optimized for resource-constrained environments and wireless communication. SPINS has two secure building blocks: SNEP and TESLA. SNEP provides the following important baseline security primitives: Data confidentiality, two-party data authentication, and data freshness. A particularly hard problem is to provide efficient broadcast authentication, which is an important mechanism for sensor networks. TESLA is a new protocol which provides authenticated broadcast for severely resource-constrained environments. We implemented the above protocols, and show that they are practical even on minimalistic hardware: The performance of the protocol suite easily matches the data rate of our network. Additionally, we demonstrate that the suite can be used for building higher level protocols.

Copyright (c) 2000-2017 Y.R. Yang, Department of Computer Science, Yale University