of Selected Ph.D. Theses in the Area of Mobile Computing
Awarded in 1999
Adaptable and Mobile-Aware Distributed Objects
(in English with an extended abstract in French)
INRIA & University Pierre et Marie Curie
The full dissertation is
Mobile computing faces a number of inherent limitations,
such as disconnection and reconnection in a different
network environment, unreliable or slow wireless communication,
and limited hardware resources. A mobile computing system
strives to hide these limitations from the user. It
adapts to environment changes in order to take advantage
of all currently-available resources. It protects against
data becoming unavailable by keeping a local replica
of remote data.
We describe here the Cadmium system and its support
for adaptation and replication. Cadmium lets both the
system and applications be aware of changes, thanks
to environment monitoring and events. A set of flexible
mechanisms let them adapt dynamically to these changes.
Cadmium provides a distributed object and reference
mechanism, Cd SSP Chains, whereby a reference retains
its meaning across disconnection. A flexible binding
mechanism makes it possible to redirect a reference
to some "best" location, under application control.
For instance a reference to a migrated object is redirected
to its new location; a reference to a replicated object
is redirected to the most available copy.
Replicated shared data raises issues of access, consistency,
and update conflicts. Since there is no universally-optimal
solution to these issues, Cadmium lets the application
control the management of distributed data, thanks to
loadable strategy modules. Each object or set of objects
can be provided with its own strategies. An object's
strategies may be changed on the fly. This allows an
application to adapt whenever required and to select
the best form of adaptation over time.
Improving the Real-Time Performance of a Wireless
Local Area Network
Rusty O. Baldwin
Virginia Polytechnic Institute and State University
This research considers the transmission of real-time
data within a wireless local area network (WLAN). Exact
and approximate analytic network evaluation techniques
are examined. The suitability of using a given technique
in a particular situation is discussed. Simulation models
are developed to study the performance of our protocol
RT-MAC (real-time medium access control). RT-MAC is
a novel, simple, and elegant MAC protocol for use in
transmitting real-time data in point to point ad hoc
WLAN. Our enhancement of IEEE 802.11, RT-MAC, achieves
dramatic reductions in mean delay, missed deadlines,
and packet collisions by selectively discarding packets
and sharing station state information. For example,
in a 50 station network with a normalized offered load
of 0.7, mean delay is reduced from more than 14 seconds
to less than 45 ms, late packets are reduced from 76%
to less than 1%, and packet collisions are reduced from
36% to less than 1%. Stations using RT-MAC are interoperable
with stations using IEEE 802.11. In networks with both
RT-MAC and IEEE 802.11 stations, significant performance
improvements were seen even when more than half of the
stations in the network were not RT-MAC stations.
The effect of the wireless channel and its impact on
the ability of a WLAN to meet packet deadlines is evaluated.
It is found that, in some cases, other factors such
as the number of stations in the network and the offered
load are more significant than the condition of the
Regression models are developed from simulation data
to predict network behavior in terms of throughput,
mean delay, missed deadline ratio, and collision ratio.
Telemetry, avionics, and packetized voice traffic models
The applicability of this research is not limited to
real-time wireless networks. Indeed, the collision reduction
algorithm of RT-MAC is independent of the data being
transported. Furthermore, RT-MAC would perform equally
well in wired networks. Incorporating the results of
this research into existing protocols will result in
immediate and dramatic improvements in network performance.
Resource Allocation Algorithms for Multi-Class Wireless Networks
Bracha M. Epstein
New York, NY
The full dissertation is
In this thesis, we examine the multi-class admission control problem in a mobile wireless environment. Users originate in a particular cell and may migrate over the period of the call to other cells in the network. Each traffic class in the network has its own quality of service (QoS) requirements which include both call and handoff dropping probabilities and a call blocking probability profile and its own properties including call length, mobility characteristics, and bandwidth requirements. We introduce two sets of QoS performance measures which are used to evaluate performance. They require that users of each traffic class are not dropped during service with appropriate probability and that different traffic classes are blocked based on a pre-determined profile.
We explore three different approaches, the first of which is static and the others of which are dynamic, to solve the problem.
The first algorithm is a static reservation-based approach. It is a multi-dimensional generalization of the trunk reservation algorithm. It reserves a fixed number of basic bandwidth units (BBUs) for each traffic type and does not adapt to changes in trafffic composition or load. At low loads, it performs similarly to the complete sharing (CS) algorithm which maximizes throughput. It also improves over the complete partitioning (CP) algorithm. At high loads it outperforms both the CS and CP algorithms.
The second approach is based on a one-step prediction mechanism. Decisions are made autonomously in each cell based on the current occupancy levels of the different traffic classes in each of the home and neighboring cells. The algorithm family contains several diffeerent variants which we analyze. The algorithms provide guarantees on the maximum probability of being dropped on handoff independent of load or traffic composition.
The third approach is a completely distributed measurement based algorithm. Partitions in each cell are periodically updated based on measurements of the call and handoff statistics in the cell to conform to the pre-specified requirements. New and handoff partitions are adjusted independently leading to both improvement in performance and algorithm simplicity.
Simulation results and analysis and comparison to other algorithms where appropriate are used as performance benchmarks.
QoS Guarantees in Wireless/Mobile Networks
The University of Michigan
Ann Arbor, Michigan, USA
The full dissertation is
Recent years have witnessed a tremendous growth of research
and development to provide mobile users a means of ``seamless''
communication through wireless media. This dissertation
examines how to provide diverse Quality-of-Service (QoS)
to mobile users generating/receiving heterogeneous traffic.
It addresses QoS at two different levels: (1) packet-level
QoS such as packet delivery delay, throughput, and error
performance; and (2) connection-level QoS associated
with connection setup and management.
To provide packet-level QoS, we develop a unified architecture
for wireless LANs. We first define a polling-based medium
access control (MAC) protocol for uplink accesses. Then,
we address resource reservation, packet scheduling,
connection-admission control, and how to handle location-dependent
channel errors. With the proposed protocols, the delivery
delays of real-time packets are bounded at the cost
of some packet losses depending on the channel condition
while allowing mobiles to have loss-free and fair accesses
for transmitting non-real-time traffic.
We also develop an uplink code-division multiple access
(CDMA) system with various packet-level QoS provisioning
for wide-area cellular networks. Based on a transmission-rate
request MAC protocol, we address the issues of resource
reservation, packet scheduling, and connection-admission
control. To satisfy the pre-defined error-performance
requirements for each traffic class, we use a concatenated
RS/convolutional code, and develop a new scheme for
allocating mobiles appropriate power levels.
For connection-level QoS, we propose predictive, adaptive
bandwidth reservation for hand-offs and admission control
for newly-requested connections so as to keep the hand-off
dropping probability below a pre-specified target assuming
that each connection requires a certain amount of bandwidth.
Our schemes utilize history-based mobility estimation
to predict user mobility. For the purpose of comparison,
we also consider five other existing schemes. Through
detailed simulations of various scenarios, we show the
superiority of the proposed schemes to the other schemes.
Finally, we propose a unified architecture for wireless
bandwidth management utilizing the concept of adaptive
QoS. The allocated throughput to each connection is
adapted depending on time-varying channel conditions
and user mobility, where a connection's acceptable throughput
range as well as adaptation constraints are specified
during the admission control phase. The BS allocates
bandwidth to each connection so as to maximize the service
provider's aggregate reward. The proposed adaptive and
non-adaptive schemes are compared to demonstrate the
advantages of the adaptive scheme.
Routing Protocol and Medium Access Protocol for
Mobile Ad Hoc Networks
Polytechnic University, NY, USA
The full dissertation is
This dissertation deals with two major topics of mobile
ad hoc networks - routing protocol and medium access
protocol. A new routing protocol for ad hoc networks,
called Zone-Based Hierarchical Link State Routing (ZHLS),
is proposed. In this protocol, the network is divided
into non-overlapping zones. Each node only knows the
node connectivity within its zone and the zone connectivity
of the whole network. The link state routing is performed
on two levels: local node and global zone levels. This
hierarchical characteristic reduces the communication
overhead and the storage requirement of routing information
in large networks. But unlike other hierarchical protocols,
there are no cluster heads in this protocol. The zone
level topological information is distributed to all
nodes. This "peer-to-peer" manner mitigates traffic
bottleneck, avoids single point of failure and simplifies
mobility management. Simulation results confirm that
the communication overhead of the proposed protocol
is smaller than that of a flat one. The results also
assert that the zone level topology is relatively stable.
So, ZHLS provides a bandwidth efficient approach to
accommodate the changing topology in mobile ad hoc networks.
In ZHLS, a node has to keep track of its physical location
continuously in order to determine its affiliated zone.
A new spread spectrum-based synchronization and geolocation
method is presented. By using a spread spectrum technique,
delays of processing handshaking messages and of switching
transceivers from receiving mode to sending mode will
not incur any inaccuracy.
A new set of medium access protocols for mobile ad
hoc networks, called MACA/C-T and MACA/R-T, is presented.
The new protocols distinguish from the others by combining
the capabilities of Multiple Access with Collision Avoidance
protocol and those of spread spectrum protocols. The
Request-to-Send and Clear-to-Send message dialogue avoids
the "hidden terminal" and the "exposed terminal" problems.
The Request-to-Send and Negative-Clear-to-Send message
dialogue and the Clear-to-Send timer mechanism are introduced
to speed up the retransmission. The assignment of unique
spreading spectrum channel to each user prevents any
disruption on any ongoing transmission by an intruder.
A mathematical analysis confirms that MACA/C-T and MACA/R-T
achieve a high channel throughput even in dense networks.
Wearable Computing and Contextual Awareness
Thad Eugene Starner
Massachusetts Institute of Technology
Cambridge, MA, USA
The full dissertation is
Computer hardware continues to shrink in size and
capability. This trend has allowed the prevailing
concept of a
computer to evolve from the mainframe to the
minicomputer to the
desktop. Just as the physical hardware changes, so
does the use of
the technology, tending towards more interactive and
Currently, another physical change is underway, placing
power on the user's body. These wearable machines
encourage new applications
that were formerly infeasible and, correspondingly,
will result in new
usage patterns. This thesis suggests that the
offered by wearable computing is an increased sense of
I hypothesize that on-body systems can sense the user's
context with little or no assistance from environmental
infrastructure. These body-centered systems that
``see'' as the user
sees and ``hear'' as the user hears, provide a unique
viewpoint of the user's environment. By exploiting
recovered by these systems, interfaces are created
minimal directed action or attention by the user.
more traditional applications are augmented by the
information recovered by these systems.
To investigate these issues, I provide perceptually
sensible tools for
recovering and modeling user context in a mobile,
environment. These tools include a downward-facing,
system for establishing the location of the user;
a tag-based object
recognition system for augmented reality; and several
recognition systems to identify various user tasks in
To address the practicality of contextually-aware
computers, issues of power recovery, heat dissipation,
distribution are examined. In addition, I have
encouraged a community
of wearable computer users at the Media Lab through
management, and support of hardware and software
This unique community provides a heightened awareness
of the use and
social issues of wearable computing. As much as
possible, the lessons
from this experience will be conveyed in the thesis.
Load Sharing as a Power Management Strategy for
University of London, U.K.
The full dissertation is
Load sharing has traditionally been used to improve
system performance in distributed networks by transferring
jobs from heavily loaded hosts to idle or lightly loaded
hosts. Performance is improved by distributing workload
more evenly among hosts, thus better utilising system
This thesis investigates the use of load sharing for
a different purpose, that is as a power management strategy
for mobile computers. Since mobile computers operate
on limited battery power, which is a scarce resource,
and there is unlikely to be a vast improvement in battery
capacity in the near future, it is vital that power
utilisation is managed efficiently and economically.
The power management strategy proposed in this thesis
is based on the concept of load sharing. The strategy
attempts to reduce power consumption by the CPU, which
is one of the components consuming a substantial amount
of power, by off-loading computations from a mobile
computer to a fixed host. A load sharing algorithm which
selects suitable jobs for remote execution is proposed.
When designing the algorithm, the inherent limitation
of wireless networks must be taken into account. For
example, low bandwidth means that communications delays
are no longer negligible; sending and receiving messages
must also be considered carefully as transmitting and
receiving also consume a substantial amount of power.
Consequently, when performing load sharing on wireless
networks, more constraints have to be dealt with compared
to when performing load sharing on fixed networks. In
addition to reducing power consumption, transferring
jobs for remote execution also gives users access to
faster machines, thus improving response time.
This study identifies the conditions and factors which
make job transfer a viable option. The results obtained
show that under suitable conditions, load sharing can
extend battery lifetime significantly. Since stability
is an important concern when designing load sharing
algorithms, this issue is also addressed by this study.
Cambridge University, U.K.
The full dissertation is
A context-aware computing system is one that can deduce
the state of its surroundings using input from sensors
and can change its behaviour accordingly. Context-aware
devices might personalise themselves to their current
user, alter their functionality based on where they
were being used, or take advantage of nearby computing
and communications resources.
Location-aware systems, whose behaviour is determined
by the positions of objects in the environment, represent
a practical subset of the context-aware computing paradigm,
and several systems of this nature have already been
demonstrated. The location sensors used by those systems,
however, report the positions of objects to only a room-scale
granularity, limiting the extent to which devices and
applications can adapt to their surroundings. Sensor
technologies that can provide more detailed information
about the locations of objects must therefore be investigated.
This dissertation describes a new ultrasonic location
sensor, which may be deployed in indoor environments
such as offices and homes. The sensor can provide fine-grain,
three-dimensional position and orientation information,
and its characteristics are well suited to the demands
of location-aware computing - the sensor is simple,
low-powered and unobtrusive. Furthermore, the location
system is scalable, in both the number of objects that
it can track and the volume within which they may be
monitored. A thorough assessment of the sensor's performance
is presented in the dissertation, so that location-aware
applications can be tailored to its properties.
Subsequently, a software architecture that can efficiently
distribute fine-grain location information to applications
is described. The software system provides support for
the types of query that will be made frequently by location-aware
applications, such as those concerning the spatial relationships
between objects and their proximity to one another.
The dissertation concludes by examining the use of the
ultrasonic location sensor and software architecture
to implement a set of novel location-aware applications.
Designing Adaptive Environment-Aware Applications
for Mobile Computing
Rutgers University, New Brunswick, NJ, U.S.A.
The full dissertation
is available here
Mobile computing represents a shift in the distributed
systems paradigm. The potential of decoupled and disconnected
operation, location-dependent computation and communication,
and powerful portable computing devices gives rise to
opportunities for new patterns of distributed computation
that require a revised view of distributed systems.
However, factors such as weak network connectivity,
energy constraints, and mobility itself raise new concerns
regarding the security, reliability, and even correctness
of a mobile computing system.
In this dissertation, we complement recent research
in mobile computing by addressing the problem from the
viewpoint of building a mobile computing application.
It is our hypothesis that a mobile computing application
must be made aware of mobility not only to better utilize
constrained resources, but also to provide enhanced
mobility related functionality. Towards this end, the
application must adapt in response to the changing mobile
environment. Unfortunately, the wide variety of environmental
situations that mobile computing presents makes it difficult
to build an application that optimally handles all situations.
This makes it imperative to consider structuring alternatives
for both mobile computing applications, and the underlying
run-time system on which they depend.
We first consider the problem of exposing an application
to the effects of mobility. We present a novel architecture
for managing and reporting changes in the mobile environment
to an application. In this architecture, an environmental
change is modeled as an asynchronous event that can
be handled at the level of abstraction that an application
deems appropriate. Our prototype implementation serves
as a reference, documenting the issues that must be
considered when designing the underlying run-time for
adaptive mobile computing applications.
Second, we propose an application architecture that
balances the trade-off between hiding and exposing mobility
awareness. Basic application functionality in this architecture,
is cleanly decoupled from adaptiveness, allowing the
application to evolve independently of any particular
environmental situation. We describe our experience
in realizing this architecture, and conclude that it
forms a powerful basis not only for building new mobility
aware applications, but also to incorporate mobility
aware adaptiveness into legacy applications and middle-ware.