We propose two distributed algorithms to maintain respectively the minimum weight spanning tree (MST) based multi-cast tree and the shortest path (SPST) multi-cast tree in a given ad hoc network for a given multi-cast group; our algorithms are fault tolerant (reliable) in the sense that the algorithms can detect occasional link failures and/or new link creations in the network (due to mobility of the hosts) and can readjust the multi-cast tree. Our approach is to use the paradigm of self-stabilization in distributed fault tolerance. We provide time complexity analysis of the algorithms in terms of the number of rounds needed for the algorithm to stabilize after a topology change, where a round is defined as a period of time in which each node in the system receives beacon messages from all its neighbors. In any ad hoc network, the participating nodes periodically transmit beacon messages for message transmission as well as to maintain the knowledge of the local topology at the node; as a result the nodes get the information about its neighbor nodes synchronously (at specific time intervals). Thus, the paradigm to analyze the complexity of the self-stabilizing algorithms in the context of ad hoc networks is very different from the traditional concept of adversary oracle used in proving the convergence and correctness of self-stabilizing distributed algorithms in general. (C) 2002 Published by Elsevier Science (USA). References: 15
展开▼
