Self-Stabilizing Token Passing for Mobile Ad Hoc Networks

J. Kiniwa (Japan)


self-stabilizing protocol, token passing, mutual exclusion,ad hoc network, dynamic BFS trees


This paper presents a new method of self-stabilizing token passing for mutual exclusion in mobile ad hoc networks. Since link failures may frequently occur in the environ ment, it is desirable to recover from such failures by it self. So we seek a self-stabilizing solution tolerating par titioning failures. A dynamic BFS tree rooted at a token process is constructed and plays a role in monitoring par titioning failures. If a partitioned component has not had any token, a token will be regenerated by timeout mecha nism. Otherwise, the tree rooted at a token will eliminate temporary tokens. For servicing a request, another kind of dynamic BFS tree rooted at each request is concurrently constructed. By using fair composition technique, tolerat ing partitioning failures can be achieved in self-stabilizing token passing. Finally, some properties of our method and stabilization time are investigated.

Important Links:

Go Back