Skip to main content

7th Annual Int. Conf. Mobile Computing and Networking 2001 Papers Sorted by key

KEYNOTE ADDRESS

The Future Mobile Internet - A Network for all Generations
Krishan Sabnani, Networking Research Vice President, Bell Labs, NJ, USA.
Abstract:
In this talk, I will present a vision of the future mobile Internet. I will also identify key technology changes and research challenges that must be overcome as we migrate towards this vision. The future mobile Internet will be based on a data-centric model, and will evolve to support not only traditional wireline applications adapted for wireless use, but also applications that add high value for mobile users. Air interfaces and networks will not be bound by "generations" - a mixture of current 2G, emerging 3G, and perhaps most prominently, high speed interfaces such as 802.11b and Bluetooth will make up these networks.

Dense broadband access networks and high-speed backbones will have a profound effect on mobile networks. The proliferation and rapid deployment of wireless LANs will make high-speed data access ubiquitous. This combination will enable new network architectures comprising many small base stations connected by a broadband network. With increasing acceptance and usage of wireless communication, the number of different device types will increase, some to serve as general-purpose devices, and others optimized for a specific application.

Such an environment raises several research challenges. First, mobility between network types must be supported. This affects authentication, addressing, and routing. Second, services must be available in a consistent manner across networks and devices. This affects service architectures and end-to-end protocols. Third, content must be available across the many new devices. This dictates the need for efficient content adaptation. Finally, performance will be critical and must account for network hot-spots. This will lead to new research on content distribution.

Paper Authors Title Abstract
3 Uwe Kubach (University of Stuttgart), Kurt Rothermel (University of Stuttgart) Exploiting Location Information for Infostation-Based Hoarding With the increasing popularity of mobile computing devices, the need to access information in mobile environments has grown rapidly. Since the information has to be accessed over wireless networks, mobile information systems often have to deal with problems like low bandwidth, high delay, and frequent disconnections. Information hoarding is a method that tries to overcome these problems by transferring information, which the user will probably need, in advance. The hoarding mechanism that we describe in this paper exploits the location dependence of the information access, which is often found in mobile information systems. Our simulation results show that it is beneficial to do so and that we achieve higher hit ratios than with a caching mechanism.
26 Vincent Lau (University of Hong Kong), Yu-Kwong Kwok (The University of Hong Kong) Design and Analysis of a New Approach to MultipleBurst Admission Control for CDMA2000 On the verge of realizing truly ubiquitous access to high quality data (e.g., media, financial, etc.), an efficient {\em burst admission control} algorithm is crucial in the 3rd generation wireless communication systems based on wideband CDMA standards. In this paper, we propose and analyze the performance of a novel burst admission technique, called the {\em multiple- burst admission--spatial dimension} algorithm (MBA-SD) to judiciously allocate the previous channels in wideband CDMA systems to burst requests. The major contributions of the present paper are the novel formulation of the problem as an integer programming problem and the derivation of an optimal algorithm for scheduling the burst requests. Both the forward link and the reverse link burst requests are considered and the system is simulated by dynamic simulations which takes into account of the user mobility, power control and soft handoff. We found that significant performance improvement, in terms of data user capacity, coverage, and admission and outage probabilities, could be achieved by our scheme compared to the existing burst assignment algorithms.
52 Michael Ritter (Metricom, Inc.), Robert Friday (Metricom, Inc.), William San Filippo (Metricom, Inc.), Rodrigo Garces (Metricom, Inc.) Mobile Connectivity in the Ricochet MicroCellular Data Network (MCDN) System We describe the protocols implemented in the Ricochet MCDN system to provide continuous connectivity to mobile users travelling up to 70 mph. The MCDN system is a mesh-based system of microcells that are connected wirelessly to an interspersed mesh of wired access points (WAPs) which cover approximately 12 square miles on average. The average microcell density is approximately 5-6 per square mile, with 4-8 overlapping cells at each point. Since the system is entirely packet-based, there are no cell hand-off negotiations requried, however, when travelling through the mesh of microcells at a high rate of speed, the mobile unit must acquire new cells fast enough to ensure continuous connectivity. The system must also know how to route packets to the mobile unit as it drops old cells and acquires new ones. This paper discusses the acquisition, registration, and routing protocols that make this possible and reviews performance data of typical mobile users.
66 Wenye Wang (Georgia Institute of Technology), Ian Akyildiz (Georgia Institute of Technology) A Cost-Efficient Signaling Protocol for Mobility Application Part (MAP) in IMT-2000 Systems Efficient signaling protocol for mobility application part (MAP) is essential to support mobility when the mobile terminals roam between different networks in next generation wireless systems such as IMT-2000. In this paper, a new signaling protocol is proposed to reduce the overhead caused by mobility management, alleviating network load and consumption of network resources. Moreover, the new protocol effectively reduces the latency of call delivery and call loss rate due to crossing wireless systems with different standards and signaling protocols. Instead of performing location registration when a mobile user arrives at the new system, the mobile user is required to update its location information prior to its reaching the boundary of two systems. Results in this study demonstrate that the new protocol yields significant benefits in terms of reducing signaling costs, delays, and call loss rates.
70 Ya Xu (University of Southern California), John Heidemann (USC/Information Sciences Institute), Deborah Estrin (UCLA) Geography-informed Energy Conservation for Ad Hoc Routing We introduce a geographical adaptive fidelity(GAF) algorithm that reduces energy consumption in ad hoc wireless networks.GAF conserves energy by identifying nodes that are equivalent from a routing perspective and turning off unnecessary nodes, keeping a constant level of routing fidelity. GAF moderates this policy using application- and system-level information; nodes that source or sink data remain on and intermediate nodes monitor and balance energy use. GAF is independent of the underlying ad hoc routing protocol; we simulate GAF over unmodified AODV and DSR. Analysis and simulation studies of GAF show that it can consume 40% to 60% less energy than an unmodified ad hoc routing protocol. Moreover, simulations of GAF suggest that network lifetime increases proportionally to node density; in one example, a four-fold increase in node density leads to network lifetime increase for 3 to 6 times (depending on the mobility pattern). More generally, GAF is an example of adaptive fidelity, a technique proposed for extending the lifetime of self-configuring systems by exploiting redundancy to conserve energy while maintaining application fidelity.
107 Minkyong Kim (University of Michigan), Brian Noble (University of Michigan) Mobile Network Estimation Mobile systems must adapt their behavior to changing network conditions. To do this, they must accurately estimate available network capacity. Producing quality estimates is challenging because network observations are noisy, particularly in mobile, ad hoc networks. Current systems depend on simple, exponentially weighted moving average (EWMA) filters. These filters are either able to detect true changes quickly or to mask observed noise and transients, but cannot do both. In this paper, we present four filters designed to react quickly to persistent changes while tolerating transient noise. Such filters are agile when possible, but stable when necessary, adapting their behavior to prevailing conditions. These filters are evaluated in a variety of networking situations, including persistent and transient change, congestion, and topology changes. We find that one filter, based on techniques from statistical process control, provides performance superior to the other three. Compared to two EWMA filters, one agile and the other stable, it is able to offer the agility of the former in four of five scenarios and the stability of the latter in three of four scenarios.
109 Mani Srivastava (UCLA), Richard Muntz (University of California, Los Angeles), Miodrag Potkonjak (University of California, Los Angeles) Smart Kindergarten: Sensor-based Wireless Networks for Smart Developmental Problem-solving Environments (Challenge Paper) Despite enormous progress in networking and computing technologies, their application has remained restricted to conventional person-to-person and person-to-computer communication. However, continual reduction in cost and form factor is now making it possible to imbed networking - even wireless networking - and computing capabilities not just in our PCs and laptops but also other objects. Further, a marriage of these ever tinier and cheaper processors and wireless network interfaces with emerging micro-sensors based on MEMS technology is allowing cheap sensing, processing, and communication capabilities to be unobtrusively embedded in familiar physical objects. The result is an emerging paradigm shift where the primary role of information technology would be to enhance or assist in person to physical world communication via familiar physical objects with embedded (a) micro-sensors to react to external stimuli, and (b) wireless networking and computing engines for tetherless communication with compute servers and other networked embedded objects. In this paper we present the application of sensor-based wireless networks to a Smart Kindergarten that we are developing to target developmental problem-solving environments for early childhood education. This is a natural application as young children learn by exploring and interacting with objects such as toys in their environment. Our envisioned system would enhance the education process by providing a childhood learning environment that is individualized to each child, adapts to the context, coordinates activities of multiple children, and allows continual unobtrusive evaluation of the learning process by the teacher. This would be done by wirelessly-networked, sensor-enhanced toys and other classroom objects with back-end middleware services and database techniques. We explore wireless networking, middleware, and data management technologies for realizing this application, and describe challenges arising from ad hoc distributed structure, unreliable sensing, large scale/density, and novel sensor data types that are characteristic of such deeply instrumented environments with inter-networked physical objects.
112 Andras Farago (University of Texas at Dallas), Violet R. Syrotiuk (University of Texas at Dallas) MERIT: A Unified Framework for Routing Protocol Assessment in Mobile Ad Hoc Networks MERIT is a framework to assess routing protocols in mobile ad hoc networks (manets). It is based on the concept of shortest mobile path (SMP) in a mobile graph. As a standard measure for routing protocols in a manet, the MERIT framework proposes the mean ratio of the cost of the actually used route to the cost of the optimal mobile path, under the same history of link metrics in the changing network topology. This MEan Real vs. Ideal cosT (MERIT) ratio is unifying in that it provides a measure that allows a protocol to be assessed independently of other protocols, within its own framework. We show that there is an efficient algorithm to solve the underlying SMP problem for important cases, making the approach practically feasible. We also investigate generalizations and extensions within the MERIT framework.
116 Qun Li (Dartmouth College), Javed Aslam (Dartmouth College), Daniela Rus (Dartmouth College) Online Power-aware Routing in Wireless Ad-hoc Networks This paper discusses online power-aware routing in large wireless ad-hoc networks. We seek to optimize the lifetime of the network. We show that online power-aware routing does not have a constant competitive ratio to the off-line optimal algorithm. We develop an approximation algorithm called $max$-$min$ $zP_\\\\\\\\\\\\\\{min\\\\\\\\\\\\\\}$ that has a good empirical competitive ratio. To ensure scalability, we introduce a second online algorithm for power-aware routing. This hierarchical algorithm is called zone-based routing. Our experiments show that its performance is close to optimal. This paper would like to be considered for best student paper award.
124 Seapahn Meguerdichian (University of California, Los Angeles), Farinaz Koushanfar (University of California, Los Angeles), Gang Qu (University of Maryland), Miodrag Potkonjak (University of California, Los Angeles) Exposure In Wireless Ad-hoc Sensor Networks Wireless ad-hoc sensor networks will provide one of the miss-ing connections between the Internet and the physical world. Calculation of exposure is one of fundamental problem in wireless sensor networks. Exposure is a measure of how well an object in a sensor network can be observed over a period of time as it moves along an arbitrary path with arbitrary velocities. In addition to this informal definition, we formally define exposure and study its properties. We have developed an effi-cient and effective algorithm for exposure calculation in sen-sor networks for any given distribution of sensors, sensor and intensity models, and characteristic of the network. The algorithm provides an unbounded level of accuracy as a function of run time. Furthermore, we study the relationship between location discovery, deployment, and exposure. We define and solve several combinatorial optimization problems related to exposure using integer linear programming. Fi-nally, we study the scaling behavior of exposure and the de-veloped algorithm for its calculation using statistical tech-niques.
165 Krisztian Flautner (University of Michigan), Steve Reinhardt (University of Michigan), Trevor Mudge (University of Michigan) Automatic Performance-Setting for Dynamic Voltage Scaling The emphasis on processors that are both low-power and high-performance has resulted in the incorporation of dynamic voltage scaling into processor designs. This feature allows one to make fine granularity trade-offs between power use and performance, provided there is a mechanism in the OS to control that trade-off. In this paper, we describe a novel software approach to automatically controlling dynamic performance and voltage scaling to optimize energy use. Our mechanism is implemented in the Linux kernel and requires no modification of user programs. Unlike previous automated approaches, our method works equally well with irregular and multiprogrammed workloads. Moreover, it has the ability to ensure that the quality of interactive performance is within user specified parameters. Our experiments show that as a result of our algorithm, processor energy savings of as much as 75% can be achieved with only a minimal impact on the user experience.
169 Sandeep Gupta (Arizona State University), Loren Schwiebert (Wayne State University), Jennifer Weinmann (Wayne State University), Ayad Salhieh (Wayne State University), Manish Kochal (Wayne State University) Research Challenges in Wireless Networks of Biomedical Sensors Implanted biomedical devices have the potential to revolutionize medicine. emphSmart sensors, which are obtained by combining sensing materials with integrated circuitry, are being considered for several biomedical applications such as a retina prosthesis. These devices require the capability to communicate with an external diagnostic computer system via a wireless interface. The limited power and computational capabilities of smart sensor based biological implants present research challenges in several aspects of wireless networking due to the need for having a bio-compatible, fault-tolerant, energy-efficient, and scalable design. Further, embedding these sensors in humans add additional requirements. For example, the wireless networking solutions should be ultra-safe and reliable, work trouble-free in different geographical locations (although implants are not expected to move; they shouldn't restrict movements of their human host), and require minimal maintenance. This necessitates application-specific solutions which are vastly different from traditional solutions. In this paper, we describe the challenges for wireless networking of human-embedded smart sensor arrays and our preliminary approach for wireless networking of a retina prosthesis. Our aim is to motivate vigorous research in this area by illustrating the need for more application-specific and novel approaches toward developing wireless networking solutions for human-embeddable smart sensors.
181 Jinyang Li (Massachusettes Institute of Technology), Charles Blake (Massachusettes Institute of Technology), Douglas S. J. De Couto (Massachusettes Institute of Technology), Hu Imm Lee (Massachusettes Institute of Technology), Robert Morris (Massachusettes Institute of Technology) Capacity of Ad Hoc Wireless Networks Early simulation experience with wireless ad hoc networks suggests that their capacity can be surprisingly low, due to the requirement that nodes forward each others' packets. The actual capacity is a function of the total number of nodes in the network, the traffic patterns, and the detailed local radio interactions. This paper examines these factors alone and in combination, using simulation and analysis from first principles. The results include both general scaling relationships and specific constants helpful in understanding ad hoc simulations and in guiding deployment of ad hoc systems. The most significant result of this work is that the traffic pattern is the deciding factor in whether an ad hoc network's per node capacity will scale with the number of nodes in the net. If most communication is localized, the total network bandwidth available to each node stays roughly constant regardless of total network size. Non-local patterns, on the other hand, result in a decrease in per node bandwidth as the total number of nodes grows. Thus the question ``Are large ad hoc networks feasible?'' boils down to a question about the likely locality of communication in such networks.
185 Johan Pouwelse (Delft University of Technology), Koen Langendoen (Delft University of Technology), Henk Sips (Delft University of Technology) Dynamic Voltage Scaling on a Low-Power Microprocessor Power consumption is the limiting factor for the functionality of future wearable devices. Since interactive applications like wireless information access generate bursts of activities, it is important to match the performance of the wearable device accordingly. This paper describes a system with a microprocessor whose speed can be varied (frequency scaling) as well as its input voltage. Voltage scaling is important for reducing power consumption to very low values when operating at low speeds. Measurements show that the energy per instruction at minimal speed (59 MHz) is 1/5 of the energy required at full speed (251 MHz). The frequency and voltage can be scaled dynamically from user space in only 140 mu s. This allows power-aware applications to quickly adjust the performance level of the processor whenever the workload changes. Experiments with an H.263 video benchmark show that the power-aware decoder outperforms a static fixed-frequency policy as well as a dynamic interval-based scheduler.
186 Nissanka Priyantha (MIT), Allen Miu (MIT), Hari Balakrishnan (MIT), Seth Teller (MIT) The Cricket Compass for Context-Aware Mobile Applications The ability to determine the orientation of a device is of fundamental importance in context-aware and location-dependent mobile computing. By analogy to an ordinary compass, knowledge of orientation through a ``software compass'' attached to a mobile device enhances various applications, including efficient way-finding and navigation, directional service discovery, and ``augmented-reality'' displays. Using fixed active beacons and passive position sensors, we show how to estimate the orientation of a mobile device to within a few degrees, using differences in distance estimates from a beacon to each sensor on the compass. There are two essential pieces to this capability. First, we show how to arrange three or more receivers precisely, a few centimeters apart on the compass, so that the differential arrival time of an ultrasonic carrier can be precisely estimated for any pair of receivers to within the required sub-centimeter accuracy. Second, given a set of fixed, active position beacons whose locations are known, we describe an algorithm that combines several carrier arrival times to produce a robust estimate of the rigid orientation of the mobile compass. Our physical sensor configuration involves five passive ultrasonic receivers, each 0.8cm in diameter, arrayed in a ``V'' shape several centimeters across. Using multiple beacons distributed throughout a building, each broadcasting coupled 418MHz RF packet data and a 40KHz ultrasound carrier, we demonstrate that our techniques determine compass orientation to within 3 degrees when the true angle lies between plus or minus 30 degrees, and to within 5 degrees when the true angle lies between plus or minus 40 degrees, with respect to a fixed beacon.
197 Benjie Chen (MIT), Kyle Jamieson (MIT), Hari Balakrishnan (MIT), Robert Morris (MIT) Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks This paper presents "Span," a distributed coordination technique for multi-hop ad hoc wireless networks that saves battery power 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, then 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, balancing two important factors. First 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. Second, each node bases its decision on 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, for the same forwarding capacity of the network. Span integrates nicely with 802.11---when run in conjunction with the 802.11 power saving mode, Span improves both communication latency and capacity without much degration in system lifetime.
200 Paul Castro (University of California, Los Angeles), Benjamin Greenstein (University of California, Los Angeles), Richard Muntz (University of California, Los Angeles), Maria Papadopouli (Columbia University) Locating Application Data Across Service Discovery Domains The bulk of proposed pervasive computing devices such as PDAs and cellular telephones operate as thin clients within a larger infrastructure. To access services within their local environment, these devices participate in a service discovery protocol which involves a master directory that registers all services available in the local environment. These directories typically are isolated from each other. Devices that move across service discovery domains have no access to information outside their current local domain. In this paper we propose an application-level protocol called VIA that enables data sharing among discovery domains. Each directory maintains a table of active links to other directories that share related information. A set of linked directories forms a data cluster that can be queried by devices for information. The data cluster is distributed, self-organizing, responsive to data mobility, and robust to failures. Using application-defined data schemas, clusters organize themselves into a hierarchy for efficient querying and network resource usage. Through analysis and simulation we describe the behavior of VIA under different workloads and show that the protocol overhead for both maintaining a cluster and handling failures grows slowly with the number of gateways. * THIS IS A STUDENT PAPER *
207 Vikram Kanodia (Rice University), Chengzhi Li (Rice University), Ashutosh Sabharwal (Rice University), Bahareh Sadeghi (Rice University), Edward W. Knightly (Rice University) Distributed Multi-Hop Scheduling and Medium Access with Delay and Throughput Constraints Providing quality of service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling, a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority back-off schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termed multi-hop coordination so that downstream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of overhearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.
211 Ramachandran Ramjee (Bell Labs, Lucent Technologies), Li Li (Cornell University), Thomas La Porta (Lucent Technologies), Sneha Kasera (Lucent Technologies) IP Paging Service for Mobile Hosts In wireless networks, mobile hosts must update the network with their current location in order to get packets delivered. Paging facilitates efficient power management at the mobile host by allowing the host to update the network less frequently at the cost of providing the network with only approximate location information. The network determines the exact location of a mobile host through paging before delivering packets destined to the mobile host. In this paper, we propose the concept of paging as an IP service. IP paging enables a common infrastructure and protocol to support the different wireless interfaces such as CDMA, GPRS, wireless LAN, avoiding the duplication of several application layer paging implementations and the inter-operability issues that exists today. We present the design, implementation, and detailed qualitative and quantitative evaluation, using measurements and simulation, of three IP-based paging protocols for mobile hosts.
214 Tom Goff (University of Maryland Baltimore County), Nael Abu-Ghazaleh (State University of New York, Binghamton), Dhananjay Phatak (University of Maryland Baltimore County), Ridvan Kahvecioglu (State University of New York at Binghamton) Preemptive Route Maintenance in Ad Hoc Networks Existing on-demand ad-hoc routing algorithms initiate route discovery only AFTER a path breaks, incurring a significant cost in detecting the disconnection and establishing a new route. In this work, we investigate adding preemptive route maintenance to on-demand ad-hoc routing algorithms. More specifically, when a path is likely to be broken, a warning is sent to the source indicating the likelihood of a disconnection. The source can then initiate path discovery early, potentially avoiding the disconnection altogether. A path is considered likely to break when the received packet power becomes close to the minimum detectable power (other approaches are possible). Care must be taken to avoid initiating false route warnings due to fluctuations in received power caused by fading, multipath effects and other transient phenomena. Experiments demonstrate that adding preemptive route selection and maintenance to DSR and AODV (on-demand ad hoc routing protocols) significantly reduces the number of broken paths, with a small increase in the number of control packets generated. Packet latency and jitter are also reduced. Pro-active route selection and maintenance is general and can be used with other routing algorithms and optimizations to them.
218 Saverio Mascolo (Politecnico di Bari),Claudio Casetti (Politecnico di Torino), Mario Gerla (University of California, Los Angeles), Medy Sanadidi (University of California, Los Angeles), Ren Wang (University of California, Los Angeles) TCP Westwood: End-to-End Bandwidth Estimation for Efficient Transport over Wired and Wireless Networks TCP Westwood (TCPW) is a sender-side modification of the TCP congestion window algorithm that improves upon the performance of TCP Reno in wireline as well as wireless networks. The improvement is most significant in wireless networks with lossy links, since TCP Westwood relies on end-to-end bandwidth estimation to discriminate the cause of packet loss (congestion or wireless channel effect) which is a major problem in TCP Reno. An important distinguishing feature of TCP Westwood with respect to previous wireless TCP extensions is that it does not require inspection and/or interception of TCP packets at intermediate (proxy) nodes. Rather, it fully complies with the end-to-end TCP design principle. The key innovative idea is to continuously measure at the TCP source the rate of the connection by monitoring the rate of returning ACKs. The estimate is then used to compute congestion window and slow start threshold after a congestion episode, that is, after three duplicate acknowledgments or after a timeout. The rationale of this strategy is simple: in contrast with TCP Reno, which "blindly" halves the congestion window after three duplicate ACKs, TCP Westwood attempts to select a slow start threshold and a congestion window which are consistent with the effective bandwidth used at the time congestion is experienced. We call this mechanism faster recovery. The proposed mechanism is particularly effective over wireless links where sporadic losses due to radio channel problems are often misinterpreted as a symptom of congestion by current TCP schemes and thus lead to an unnecessary window reduction. Experimental studies reveal improvements in throughput and performance, as well as in fairness. In addition, friendliness with TCP Reno was observed in a set of experiments showing that TCP Reno connections are not starved by new coming TCPW connections. Most importantly, TCPW is extremely effective in mixed wired and wireless networks where throughput improvements of up to 550% are observed. Finally, TCPW performs almost as well as localized link layer approaches such as the popular Snoop scheme, without incurring the O/H of a specialized link layer protocol.
236 Andreas Savvides (University of California, Los Angeles), Chih-Chien Han (University of California, Los Angeles), Mani Srivastava (UCLA) Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors Wireless communication systems have become increasingly common because of advances in radio and embedded system technologies. In recent years, a new class of applications that networks these wireless devices together is evolving. A representative of this class that has received considerable attention from the research community is the wireless sensor network. Such a sensor networks consist of numerous tetherless devices that are released into the environment and organize themselves in an ad-hoc fashion. The goal of the network is to perform a monitoring task, and knowledge the physical location of the individual nodes is therefore essential. Not only is this information needed for the sensor network to report the location where events take place, it also assists in group-querying or routing traffic to a designated geographic destination and provides information on physical network coverage. However, equipping every node with a GPS receiver is not always feasible due to possible obstructions in the path of the satellite signals or energy limitations in the nodes. In this paper, we present a novel location discovery approach, which we call AHLoS (Ad-Hoc Localization System), for wireless sensor networks. Only a small fraction of the nodes start with knowledge of their location and the others dynamically estimate their positions via a distributed algorithm. Furthermore, our algorithm utilizes a new iterative multi-lateration technique, such that all nodes that meet some simple connectivity requirements are eventually able to determine their position. We have analyzed the operation of AHLoS, designed a new testbed of wireless sensor nodes and verified the behavior of our distributed localization technique. The results obtained from the testbed are then incorporated in a simulation platform to perform scalability tests and evaluate the effects of error propagation.
257 Andrew Huang (Stanford University), Benjamin Ling (Stanford University), John Barton (Hewlett-Packard Laboratories), Armando Fox (Standford University) Making Computers Disappear: Appliance Data Services Digital appliances designed to simplify everyday tasks are readily available to end consumers. For example, mobile users can retrieve Web content using handheld devices since content retrieval is well-supported by infrastructure services such as transformational proxies. However, the same type of support is lacking for input-centric devices, those that create content and allow users to share content. This lack of infrastructural support makes input-centric devices hard to use and less useful. The Appliance Data Services project seeks to explore a vision of an appliance computing world where users move data seamlessly among various devices. Based on this vision, we formulate three principles that guide the design of an architecture that helps realize this vision: bring devices to the forefront, minimize the number of device features, and place functionality in the network infrastructure. We evaluate our implementation of the ADS architecture based on these principles, and build applications using the ADS framework to evaluate the ease with which appliance computing applications can be built using the framework. We find that it is relatively simple to build and extend applications on ADS that make using digital devices easier, and results in the devices themselves becoming more useful.
259 Eugene Shih (Massachusetts Institute of Technology), SeongHwan Cho (Massachusetts Institute of Technology), Nathan Ickes (Massachusetts Institute of Technology), Rex Min (Massachusetts Institute of Technology), Amit Sinha (Massachusetts Institute of Technology), Alice Wang (Massachusetts Institute of Technology), Anantha Chandrakasan (Massachusetts of Institute Technology) Physical-Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks The potential for collaborative, robust networks of microsensors has attracted a great deal of research attention. For the most part, this is due to the compelling applications that will be enabled once wireless microsensor networks are in place; location-sensing [Priyantha00], environmental sensing [Kahn99], medical monitoring and similar applications are all gaining interest. For network researchers, however, wireless microsensor networks pose numerous design challenges. For example, due to the size of these networks, one challenge is to devise an efficient method to access the sensor data from nodes in the network. For applications requiring long-term, robust sensing, such as military reconnaissance, an even more important challenge is to design wireless sensor networks that have long system lifetimes and fault tolerance. This challenge is especially difficult due to the energy-constrained nature of the devices. In order to design networks that have extremely long lifetimes, we propose a physical-layer driven approach to designing protocols and algorithms for such networks. We first present a hardware model for our wireless sensor node and then introduce the design of physical-layer aware protocols, algorithms, and applications that minimize energy consumption of the system. Our approach can be used at different levels of the hierarchy to take advantage of the underlying hardware. Furthermore, we also attempt to reduce energy consumption through algorithm and protocol techniques that deal with the non-idealities of the underlying hardware.
268 Lichun Bao (University of California, Santa Cruz), J. J. Garcia-Luna-Aceves (University of California, Santa Cruz) A New Approach to Channel Access Scheduling for Ad Hoc Networks We propose a novel contention resolution algorithm applicable to ad hoc networks. According to this algorithm, a network node uses the identifiers of its neighbors one and two hops away to elect deterministically one or multiple winners for channel access in each contention context (e.g., a time slot). Collision-free channel access protocols are presented based on this approach. Except for time slot synchronization and occasional neighbor updates when the two-hop neighborhood changes, these protocols dedicate the scarce bandwidth completely to data communications, without the contention phases or the periodic schedule broadcasts commonly adopted in other channel access protocols. The protocols are shown to be fair and capable of achieving maximum utilization of the channel bandwidth. The delay and throughput characteristics of the contention resolution algorithm are analyzed, and the performance of the three new channel access protocols is studied by simulations.
275 Alec Woo (University of California, Berkeley), David Culler (UC Berkeley) A Transmission Control Scheme for Media Access in Sensor Networks 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 the 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 traffic.
276 Bill N. Schilit (Fuji-Xerox Palo Alto Laboratory), Jonathan Trevor (Fuji-Xerox Palo Alto Laboratory), David M. Hilbert (Fuji-Xerox Palo Alto Laboratory), Tzu Khiau Koh (Xerox Singapore Software Center) m-Links: An Infrastructure for Very Small Internet Devices In this paper we describe the Mobile Link (m-Links) infrastructure for utilizing existing World Wide Web content and services on wireless phones and other very small Internet terminals. Very small devices, typically with 3-20 lines of text, provide portability and other functionality while sacrificing usability as Internet terminals. In order to provide access on such limited hardware we propose a small device web navigation model that is more appropriate than the desktop computers web browsing model. We introduce a middleware proxy, the Navigation Engine, to facilitate the navigation model by concisely displaying the Webs link (i.e., URL) structure. Because not all Web information is appropriately "linked," the Navigation Engine incorporates data-detectors to extract bits of useful information such as phone numbers and addresses. In order to maximize program-data composibility, multiple network-based services (similar to browser plug-ins) are keyed to a links attributes such as its MIME type. We have built this system with an emphasis on user extensibility and we describe the design and implementation as well as a basic set of middleware services that we have found to be particularly important.
278 Nikita Borisov (University of California, Berkeley), Ian Goldberg (Zero Knowledge Systems), David Wagner (University of California, Berkeley) Intercepting Mobile Communications: The Insecurity of 802.11 The 802.11 standard for wireless networks includes a Wired Equivalent Privacy (WEP) protocol, used to protect link-layer communications from eavesdropping and other attacks. We have discovered several serious security flaws in the protocol, stemming from misapplication of cryptographic primitives. The flaws lead to a number of practical attacks that demonstrate that WEP fails to achieve its security goals. In this paper, we discuss in detail each of the flaws, the underlying security principle violations, and the ensuing attacks.
279 Victor Wen (University Of California, Berkeley), Adrian Perrig (University of California, Berkeley), Robert Szewczyk (University of California, Berkeley) SPINS: Security Suite for Sensor Networks 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 uTesla. 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. uTesla 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.
286 Gavin Holland (Texas A&M University), Nitin Vaidya (Texas A&M University), Paramvir ("Victor") Bahl (Microsoft Research) A Rate-Adaptive MAC Protocol For Wireless Networks Wireless local area networks are becoming increasingly popular, due, in part, to the recent availability of devices capable of communicating at high data rates. These high rates are made possible, in part, through new modulation techniques that dramatically increase bandwidth efficiency. However, the appropriate modulation scheme is a function of the channel conditions. Consequently, wireless devices often support multiple data rates utilizing multiple modulation schemes, and provide users the ability to manually choose the desired rate. A rate adaption mechanism may also be employed, which automatically selects the rate that gives the optimum throughput for the channel conditions. Although rate adaption techniques for cellular wireless networks have been studied at length, few have been proposed for wireless local area networks. This paper presents one such mechanism: a rate adaptive MAC protocol based on the RTS/CTS protocol, called the Receiver-Based AutoRate (RBAR) protocol. In RBAR, the rate adaption mechanism is located on the receiver, instead of on the sender (as is the case in current devices like the WaveLAN~II. This configuration is better because it allows the rate adaption mechanism to acquire channel quality information directly from the receiver's hardware, resulting in more efficient channel quality estimation. Simulation results of an implementation of RBAR into IEEE~802.11 show that this arrangement performs well.