The full dissertation is available here
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.

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

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

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.

The full dissertation is available here
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.

The full dissertation is available here
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.

The full dissertation is available here
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.

The full dissertation is available here
Computer hardware continues to shrink in size and increase in 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 personal systems. Currently, another physical change is underway, placing computational 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 fundamental improvement offered by wearable computing is an increased sense of user context.

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 ``first-person'' viewpoint of the user's environment. By exploiting models recovered by these systems, interfaces are created which require minimal directed action or attention by the user. In addition, more traditional applications are augmented by the contextual information recovered by these systems.

To investigate these issues, I provide perceptually sensible tools for recovering and modeling user context in a mobile, everyday environment. These tools include a downward-facing, camera-based system for establishing the location of the user; a tag-based object recognition system for augmented reality; and several on-body gesture recognition systems to identify various user tasks in constrained environments.

To address the practicality of contextually-aware wearable computers, issues of power recovery, heat dissipation, and weight distribution are examined. In addition, I have encouraged a community of wearable computer users at the Media Lab through design, management, and support of hardware and software infrastructure. 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.

The full dissertation is available here
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 resources.

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.

The full dissertation is available here
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.

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.