Back to SIGMOBILE Main Page
Comments Contact Us Search and Site Map
Executive Committee
Annual Meetings
Annual Reports
SIGMOBILE Publications
Sponsored Conferences
Sponsored Workshop
In-Cooperation Events
Requesting Sponsorship
Distinguished Service
Outstanding Contribution
MobiCom Best Student Paper
SIGMOBILE Membership
Online Application

Abstracts of Selected Ph.D. Theses in the Area of Mobile Computing Awarded in 1997

Resource Allocation in Multi-Service Wireless Access Networks

Erik Anderlind

Royal Institute of Technology, Stockholm, Sweden
October 1997

Wireless Access Networks offer an alternative method for connecting subscribers to the global telecommunication networks. They will become widespread only if they can provide an attractive set of communication services at competitive prices and quality. Fundamental to achieving these goals is how the scarce radio frequency is managed. We evaluate a few alternative resource management principles and highlight some key design issues for such networks. The emphasis is on providing services that require certain minimum performance guarantees in order to be useful.

High quality communication services and efficient resource management is only possible if the resource requirements of different services can be adequately described. We propose a framework for expressing wireless communication services in terms upon which radio resource management algorithms can operate. A price/priority component can be used to prioritize between different services.

A comparison is made between fixed (FCA) and dynamic (DCA) channel allocation for multi-service TDMA networks. We show that if access networks should be capable of offering high peak-rate services, i.e., requiring more than a few percent of the available frequency spectrum, dynamic channel allocation techniques seem an imperative design component.

Applications that can adapt to varying service levels enable a higher resource uti- lization. The resulting admission control problem is formulated as a flexible knapsack problem. A few simple service pricing models illustrate some tradeoffs involved in defining and pricing new services.

Distributed quality-based power control has previously been shown to achieve substantial quality and capacity gains over a constant transmitter power scheme. We compare two classes of quality based power control, differentiated by the rate of the feed-back information. A slow power control is preferable when the radio environment changes fast or coding and interleaving can be used to compensate for multi-path fading degradations. A fast scheme is preferred when communication links are established for only short periods, such as when providing bursty data services, and for slowly moving terminals. A new technique is also developed to decrease the transmitter power dynamic range when using fast step-wise quality based power control.

We demonstrate that with a suitable set of channel selection and channel access procedures, services for moderately bursty data users can be provided without unduly degrading the quality of real-time services. This is possible without splitting of the available frequency resource between different user classes. A novel method is developed to "prepare" channels for rapid channel reassignments.

Further, a traffic model for WWW and distributed file system access over wireless links is derived, based on an analysis of the TCP/IP protocol suite.

Location Management Techniques and Teletraffic Modeling for Large Wireless Communications Networks

Derek Lam

Stanford University, CA, USA
November 1997

A wireless communications network maintains per-user information about each subscriber in user profiles that are stored in databases connected to the signaling network. When a person makes a call, the network must perform a location lookup to obtain the callee's current location from a copy of the user profile. When a user moves from one region to another, the network must modify information in the user profile to track the person's new location. This dissertation addresses the location management problem - the efficient retrieval and maintenance of location information in user profiles - for large wireless communications networks. Location management standards in cellular mobile systems, IS-41 and GSM, are limited to geographical phone numbers, i.e. users cannot maintain the same phone numbers if they have relocated or changed service providers. A lifelong permanent phone number is a highly attractive feature that has been proposed for future wireless communications services. This dissertation presents two location management techniques, HIerarchical ProfilE Replication (HIPER) and Hierarchical Online Parametric ProfilE Replication (HOPPER), that were developed for supporting lifelong numbering in a scalable and efficient manner.

Research into a modeling framework for realistic performance evaluation of location management techniques in wireless networks is lacking. Since user calling and mobility patterns are not well understood, performance studies in the literature have used over-simplified models that incompletely characterize user behavior. A realistic teletraffic modeling framework for large wireless communications networks based on actual call traffic traces, vehicle and airplane traffic data, and government transportation surveys, is presented. Large scale network simulations, based on the teletraffic and mobility research, are presented to compare the performance between HIPER, HOPPER, and other proposed location management techniques. The simulation results show that both HIPER and HOPPER have better location lookup performance than the current location management standard modified for lifelong numbering. Particularly, HOPPER has the best lookup performance, requiring 23% fewer database lookups compared to the modified location management standard. HOPPER also incurs the lowest total database access and network signaling loads while requiring 57% more memory than the modified location management standard.

Real-Time Video Transmission and Multimedia Services over Wireless Networks

Hang Liu

University of Pennsylvania, Philadelphia, PA, USA
October 1997

Next-generation wireless networks will support not only voice and data services but also video applications. This dissertation focuses on real-time video transmission and multimedia services over wireless networks. Specifically, three related and important issues, error control, source rate control and synchronization control, are studied.

We begin by investigating the relationship between the quality of H.263 coded video transmission and error control using forward error correction (FEC). It is shown that H.263 coded bitstreams are very vulnerable to transmission errors. After observing that traditional FEC schemes are not efficient in nonstationary wireless communications environments, we first present a modified type-II hybrid automatic repeat request (ARQ) scheme. Then, in order to take advantage of both type-I and type-II hybrid ARQ schemes, we develop a concatenated hybrid ARQ scheme. An analytical framework based on a multi-state Markov chain channel model is also developed to evaluate the performance of the hybrid ARQ schemes. It is demonstrated that the hybrid ARQ schemes can significantly improve video transmission quality. Hybrid ARQ schemes adapt to the varying channel conditions by retransmitting erroneous packets, this results in variable effective data rates for current PCS networks. An adaptive source rate control (ASRC) protocol is proposed and studied. We demonstrate that the ASRC scheme can work together with the hybrid ARQ error control scheme to achieve efficient transmission of real-time video with low delay and high reliability.

Finally, we propose and study the approach of employing a large delay bound for the hybrid ARQ error control module of the transmission system to effectively correct transmission errors and an adaptive synchronization scheme at the application layer of the receiver to maintain synchronization and keep end-to-end delays low. We also design an adaptive synchronization protocol. It is shown that the synchronization protocol yields good performance. Low transmission error rates, low end-to-end delays and good synchronization are feasible when error control, source rate control and synchronization control are jointly considered and properly designed.

Adaptive Equalization and Receiver Diversity for Indoor Wireless Data Communications

Yumin Lee

Stanford University, CA, USA
September 1997

The full dissertation is available here
Multipath propagation is one of the most challenging problems encountered in a wireless data communication link. It causes signal fading, delay spread, and Doppler spread, and can greatly impair the performance of a data communication system. Multipath mitigation techniques such as adaptive decision-feedback equalization (DFE) and receiver diversity are thus required for low-error-rate, high-speed wireless data communications. This dissertation examines these techniques for indoor wireless data communications. Receiver diversity is known to be an effective way of coping with signal fading. However, indoor wireless radio channels exhibit frequency-selective fading which introduces inter-symbol interference (ISI), therefore receiver diversity alone cannot yield satisfactory performance, and more sophisticated signal processing techniques are often required. Adaptive equalization, on the other hand, is known to be an effective measure against ISI. However, adaptive equalization alone cannot mitigate the effect of signal fading. Integration of diversity and adaptive equalization is therefore desirable for communication systems such as indoor wireless data networks which operate in a delay-spread multipath fading environment.

In this dissertation, the effects of multipath propagation and their impact on a data communication system are first discussed. A flexible baseband model is developed for indoor wireless communication channels. The adaptive DFE is then treated alone as an approach for mitigating the effect of delay spread. Algorithms for updating the DFE filter coefficients are discussed. These algorithms are classified as channel-estimation-based adaptation (CEBA) and direct-adaptation (DA). While they have been compared previously in the literature, in this dissertation new results regarding their relative performance are obtained using computer simulations that are realistic for wireless communications. Furthermore, an improved training method referred to as "synthetic training" is developed and shown to be very effective in improving the performance of the DA DFE. A numerical technique known as "regularization" is also applied to improve the performance of the channel-estimation-based fractionally-spaced DFE.

Sampling instant and decision delay optimization, which are crucial to the performance of the adaptive DFE, are also investigated for the adaptive DFE. In this dissertation, the sampling instant is obtained via a two-step approach from the over-samples of the received signal. The decision delay is next optimized using the a priori approach or the a posteriori approach. The a priori approach is evaluated using previously proposed as well as new, ad hoc optimization metrics. The a posteriori approach, on the other hand, is first demonstrated using an "ideal" technique which is not realizable. A realizable a posteriori optimization technique, referred to as the multiple decision delay DFE (MDDDFE), is later developed, and shown to achieve a performance that is very close to the ideal technique.

Paralleling the discussion on the adaptive DFE, receiver diversity is also presented alone as a mitigation technique against signal fading. Computer simulation is used to show that, when used alone, receiver diversity can also significantly improve the performance of a wireless data communication system. The performance improvements achieved by receiver diversity and adaptive DFE are, however, due to different reasons. It is therefore very desirable to integrate these two techniques.

The integration of combining and selection diversity with the adaptive DFE is discussed in detail in this dissertation. The maximal ratio combining DFE (MRCDFE) is a technique for introducing combining diversity into adaptive DFE, while the selection diversity DFE (SDDFE) is a technique for incorporating selection diversity into adaptive DFE. For the MRCDFE, the branch DFE filter coefficients are jointly optimized using extensions of the CEBA and DA algorithms. Regularization can also be applied to improve the performance of the fractionally-spaced MRCDFE. While the MRCDFE is not new, we obtained new results regarding the relative performance of the CEBA and DA MRCDFE's, which are consistent with the results we presented for the single-branch case. For the SDDFE, we developed a new selection rule which is referred to as the maximum a posteriori probability (MAP) selection rule. This rule is proved to be optimal, in the MAP sense, for a SDDFE. Based on the MAP selection rule, two new selection metrics are derived and evaluated. Simulation results show that both the MRCDFE and MAP SDDFE greatly outperform the unequalized diversity receiver and adaptive DFE without receiver diversity. Furthermore, the new MAP selection metrics significantly outperform conventional metrics for the SDDFE, and achieve a performance that is only slightly inferior to the MRCDFE. Since the branch DFE filter coefficients are independently optimized for the SDDFE, it is computationally simpler than the MRCDFE. Adaptive MAP SDDFE is, therefore, an attractive approach for simultaneously mitigating the impact of signal fading, delay spread, and small amount of Doppler spread.

An Architecture For A Future Wireless ATM Network

Bora Aydin Akyol

Stanford University
June 1997

The full dissertation is available here
Communicating without being attached to a tether is appealing to many subscribers of wireless communication services that exist today. This dissertation describes an architecture for a Wireless Asynchronous Transfer Mode (ATM) network that will expand the range of services and the amount of resources available to wireless users in the future.

Existing ATM networks are designed to support wireline users with fixed locations; consequently, current ATM protocols do not implement Registration, Handoff, Connection Setup and Rerouting functions that are required to support wireless users. Registration and Connection Setup are required to locate a user during information delivery. Handoff provides true mobility to wireless users and allows them to move beyond the coverage of a single wireless access point. Rerouting is required to maintain connectivity to the network during a handoff event.

Overlay and Migratory Signaling are developed in this dissertation to implement registration, connection setup and handoff functions in an ATM network context to support mobility of wireless users. Overlay Signaling uses switched ATM connections to encapsulate mobility related signaling messages between wireless-aware interworking nodes at the edges of the backbone ATM network and does not require any changes to the existing ATM protocols. Overlay Signaling utilizes a cell forwarding based approach to reroute user connections during a handoff. Cell forwarding allows Overlay Signaling to maintain compatibility with the existing ATM protocols. Migratory Signaling defines a new ATM signaling protocol that remains backward compatible with existing ATM protocols while supporting wireless users. Migratory Signaling uses the Nearest Common Node Rerouting (NCNR) algorithm to reroute user connections during a handoff. NCNR is a new rerouting algorithm developed in this dissertation and is based on the partial re-establishment of existing user connections.

Our wireless ATM architecture provides wireless access to a backbone ATM network. In order to be compatible with the backbone ATM network, the wireless access points need to support multiple traffic types with different priorities and quality of service requirements. Dynamic Resource Allocating Multiple Access (DRAMA), developed in this dissertation, is a medium access control and resource allocation protocol that supports multiple users, multiple connections per user and service priorities and is fully compatible with existing ATM protocols.

Supporting Connection Mobility in Wireless Networks

Ramachandran Ramjee
University of Massachusetts, Amherst, MA, USA
May 1997

The full dissertation is available here
A multimedia connection in a wireless network typically utilizes three important network resources: wireless link resources, wired link resources and network server resources. When the users participating in the connection are mobile, these resources must be reallocated as the users move in a manner so that the connection is not disrupted. This dissertation contributes a set of algorithms for supporting connection mobility through efficient and, in certain cases, optimal use of these network resources.

In the first part of this thesis, we examine various techniques for allocating wireless channel resources to connections. We define three important practical problems in channel allocation faced by network engineers. We then derive new and optimal admission control policies for each of these problems. We further show that the optimal policies provide significant performance gains over other previously proposed policies. We also develop computationally-efficient algorithms for deploying these optimal policies in real-time at the base-stations.

In the second part of this thesis, we examine ways of rerouting the connections of mobile users so that the wired link resources are utilized efficiently. We propose, implement, and experimentally and analytically evaluate the performance of several connection rerouting schemes. Our study shows that one of our schemes is particularly well suited for performing connection rerouting. This scheme operates in two phases: a real-time phase where a reroute operation is executed without causing any disruption to user traffic, and a non-real-time phase where more efficient reroutes are effected.

In the third and final part of this thesis, we examine ways of efficiently utilizing the computational resources in the network. We study policies for migrating user agents, which act as proxies for mobile users, as users move. We show that two simple threshold policies that we propose, a Count policy which limits the number of agents in each server and a Distance policy which gives preference to migration of agents that are farther away from their users, deliver excellent performance across a wide range of system parameters and configurations.

SEER: Predictive File Hoarding for Disconnected Mobile Operation

Geoffrey H. Kuenning

UCLA, Los Angeles, CA, USA
January 1997

The full dissertation is available here
Because of the limited storage space available on portable computers, disconnected mobile users must restrict their work to a subset of the files available on their network. The list of files needed to accomplish useful work is large, non-intuitive, and constantly changing. Selecting a subset by hand is difficult, time-consuming, and error-prone, suggesting that an automated solution is desirable.

Our thesis is that it is possible and practical to automate the process of choosing files to be stored on a portable computer. To validate this thesis, we conducted a preliminary study in a live business environment, which demonstrated that the approach was feasible.

We then developed a new metric, semantic distance, that quantifies the relationships among files, so that the group of files needed to work on a particular project can be identified. Using this metric, we built an automated system named SEER, which dynamically analyzes user behavior to identify the files needed for various projects, predicts the projects on which the user will be working, and then arranges to store the files necessary for these projects on the portable computer.

After building the system, we developed new metrics to characterize the behavior of automated hoarding systems, and deployed SEER among a small group of users. To our knowledge, ours is the first quantitative study of a hoarding system that has been done anywhere. The results of the study showed that SEER performed superbly, usually requiring only about a third of the hoard space needed by previous algorithms, and generally performing within a few percent of optimality. In live usage, SEER nearly always hoards 100% of the files needed by the user.

Real-Time Visual Communications Over Narrowband Wireless Radio Networks

Paramvir Bahl

University of Massachusetts, Amherst, MA, USA

The general problem of providing simultaneous support for voice, data, and digital video over narrowband wireless radio networks is studied. Emphasis is placed on developing solutions for real-time digital video communications. The approach followed is one of targeting critical components of the proposed system, evaluating existing strategies for dealing with problems within these components, and developing new robust solutions where necessary.

At the application layer, the performance of currently popular video compression standards when used in transmission over typical radio channels is evaluated. With the help of several examples it is shown that these algorithms perform poorly in error-prone and bandwidth-limited environments. Pre-processing video before compression in the form of wavelet and pyramidal multi-resolution decomposition is shown to perform well but is deemed unattractive due to the complexity and the power hungry nature of these algorithms. A novel spatial decomposition scheme, called the region-segmentation technique, is proposed. This pre-processing technique has the property of rendering the video bitstream "network friendly";. The practical implication is the improvement in perceived connection quality because of bounded error propagation, reduced delay latency, better error concealment, and increased temporal resolution in the presence of path loss, shadowing, and fading.

At the network layer, the characteristics of the joint source-channel region-segmented (or subband) video coder are exploited to develop a novel bandwidth reservation and allocation strategy. It is shown that near-optimum utilization of reserved bandwidth for variable bit rate (VBR) video is possible through a novel connection-level intra-frame statistical multiplexing technique. From the system's perspective, a novel resource distribution scheme, called Priority Sharing with Restrictions (PSR), which partitions the available bandwidth amongst the different traffic classes is developed. While being bandwidth efficient this strategy provides tunable blocking probability for each traffic class, protection against overloading from other classes, and quality-of-service (QoS) guarantees for digital video. The delicate task of partitioning the bandwidth when the exact mix of traffic classes or other detailed traffic descriptors are unknown is accomplished by developing an efficient and practical algorithm called the Smart Allocate Algorithm, which uses traffic parameters consisting only of aggregate average traffic load and the total available bandwidth. In addition to being insensitive to statistical assumptions this algorithm minimizes the maximum blocking probability for multi-rate multimedia connections.

At the transport and data link layers a new reservation-random time division multiplexing-based wireless medium access control protocol called ARMAP (Adaptive Reservation Multiple Access Protocol) is developed. Visual communication in ARMAP is supported through a combination of static and dynamic reservations. Static reservations guarantee at least a minimal visual quality while dynamic reservations provide enhanced picture quality. The regularity in the video packet generation process is exploited in the protocol to provide contention free channel access to on-going video connections. A novel adaptive reservation-slot generation algorithm ensures optimal bandwidth usage and optimal power consumption by the wireless device. The combination of resource reservation, and timely transmission of video packets ensures QoS guarantee for real-time video connections. Furthermore, it is shown that ARMAP performs well when used for transmission of voice and data traffic as well.

Exhaustive statistical characterization that provides valuable insights into the traffic generation process for VBR video is carried out. It is shown that for inter-frame coded video the arrival bit rate distribution changes with different capture, compression, and transmission rates. From a pool of previously proposed asymptotic distributions, the five most popular distributions are examined and the ones that best describe VBR compressed video, classified by compression scheme, application type, and frame rate, are determined. It is established that no single distribution is best suited to describe all video traffic, and a three dimensional matrix is offered, where each dimension represents a different video classification aspect and each entry of the matrix the distribution type that best fits the given combination of the aspects. Even though different video sequences are best described by different distributions, there is an inherent underlying similarity between these distributions. With this observation a useful analytical result for determining the overall system capacity of wireless multimedia networks and for determining the partitioning/allocation point in bandwidth partitioning strategies is developed.

The ACM Special Interest Group on Mobility of Systems, Users, Data and Computing