Self-stabilization protocols, and distributed protocols in mobile ad hoc networks.

摘要

A distributed network is a set of nodes (processors) connected together by either physical or logical links. Distributed systems differ from centralized systems in a number of essential aspects. The most important one is that in a distributed system, each node lacks the knowledge of the global state of the system. A mobile ad hoc network is an important type of distributed network. It is a self-configuring network of mobile routers (and associated hosts) connected by wireless links---the union of which form an arbitrary topology. The routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Fault tolerance is the property of a computer system to continue operation at an acceptable quality, despite the unexpected occurrence of hardware or software failures. For providing various network services, such as broadcasting, multicasting and routing, fault-tolerant and adaptive protocols are highly desired.; The basic idea of the first half of this dissertation is that a distributed system, including mobile ad hoc network, may be started in an arbitrary global configuration, but after a finite interval the system reaches a correct global configuration, called a legitimate configuration. Many services for a distributed system involve maintaining a global predicate over the entire network by using local information at each participating node. One approach to achieving this is self-stabilization. The self-stabilizing property allows a system to start in any configuration, and still be guaranteed to converge to a legitimate configuration in a finite amount of time and remain so thereafter.; In this dissertation, we provide: an anonymous fast algorithm for finding a 1-maximal independent set in a tree that uses constant space at each node; and a self-stabilizing algorithm for finding 1-maximal matchings in trees and cycles whose lengths are not divisible by 3. A 1-maximal set is a maximal set with the additional property that one cannot increase the cardinality of the set by removing one node and adding more nodes.; We also study distributed and adaptive protocols, which achieve fault-tolerance in mobile ad hoc networks. In this dissertation, we provide: an adaptive distributed algorithm for routing using a d-hop connected d-hop dominating set.; The Gossiping problem is based in initialized network. Each node has knowledge of a global clock. The total time of data transmissions of the network is divided into time-slots. In this dissertation, we provide: an efficient distributed protocol for online gossiping problem for mobile networks and fault-tolerant networks. We analyze these protocols and bound their complexity.