Distributed coordination in mobile wireless environments.

摘要

Mobile computing is a branch of distributed computing, but mobile networks have fundamentally different characteristics from traditional wired networks in aspects of communication, mobility and resource constraints. These characteristics make the development of distributed algorithms much more difficult. In this thesis, we investigate the challenging issues in designing algorithms for solving distributed computing problems in mobile wireless networks. We focus on two distributed coordination problems: the consensus problem and the mutual exclusion problem.;The consensus problem arises in many distributed computing applications, such as atomic commitment, atomic broadcast, and file replication. So far, little work has been reported on achieving consensus in mobile environments. This thesis makes the following original contributions in this field.;First, we develop a general technique named "Look-Ahead" to speed up the execution of consensus protocols by making use of future messages. Second, we improve message efficiency and scalability of consensus protocols for mobile ad hoc networks (MANETs) using a hierarchy imposed on the mobile hosts. By clustering the mobile hosts into clusters, a two-layer hierarchy is established. Then, the messages from and to the hosts in the same cluster are merged/unmerged by the clusterhead in order to reduce the message cost and improve the scalability. Based on different ways for clustering hosts, we propose two hierarchical protocols. The third contribution to the consensus problem is the design of an eventual leader protocol for "dynamic" infrastructured mobile networks, where the number of participating hosts can change arbitrarily as time passes and an unbounded number of hosts can join or leave the system at any time. The proposed eventual leader protocol can be used to design consensus protocols for dynamic infrastructured mobile networks.;Another coordination problem addressed in this thesis is mutual exclusion (MUTEX), one of typical coordination problems. We propose the first permission-based MUTEX algorithm for MANETs. Based on the "look ahead" technique, which enforces the MUTEX only among the hosts that are currently competing for CS, we propose a message efficient MUTEX algorithm for MANETs. The algorithm can also tolerate link and host failures by using timeout-based fault tolerance mechanisms.