| 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. |
