DocumentCode :
1664432
Title :
Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks
Author :
Goddard, Wayne ; Hedetniemi, Stephen T. ; Jacobs, David P. ; Srimani, Pradip K.
Author_Institution :
Dept. of Comput. Sci., Clemson Univ., SC, USA
fYear :
2003
Abstract :
We propose two distributed algorithms to maintain, respectively, a maximal matching and a maximal independent set in a given ad hoc network; 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 global predicates. 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 their 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 an adversary daemon used in proving the convergence and correctness of self-stabilizing distributed algorithms in general.
Keywords :
ad hoc networks; computational complexity; distributed algorithms; fault tolerant computing; graph theory; multicast protocols; set theory; ad hoc networks; beacon messages; distributed algorithms; fault tolerant algorithms; global predicates; link creations; link failures; maximal independent sets; maximal matching; multicast protocol; self-stabilizing protocols; time complexity analysis; topology change; Ad hoc networks; Algorithm design and analysis; Change detection algorithms; Convergence; Distributed algorithms; Fault detection; Fault tolerance; Maintenance; Network topology; Protocols;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium, 2003. Proceedings. International
ISSN :
1530-2075
Print_ISBN :
0-7695-1926-1
Type :
conf
DOI :
10.1109/IPDPS.2003.1213302
Filename :
1213302
Link To Document :
بازگشت