TY - GEN
T1 - A dual-token-based fault tolerant mutual exclusion algorithm for MANETs
AU - Wu, Weigang
AU - Cao, Jiannong
AU - Raynal, Michel
PY - 2007/12/1
Y1 - 2007/12/1
N2 - Most existing mutual exclusion algorithms for mobile ad hoc networks (MANETs) adopt a token-based approach. In traditional wired networks, timeout-based mechanisms are commonly used to detect token losses. However, in MANETs, it is difficult to set a proper timeout value due to the network dynamics. In this paper, we propose a dual-token-based mutual exclusion algorithm, which can tolerate token losses without using timeout. Two tokens are concurrently circulated in the system to monitor each other by using sequence numbers. If one token is lost, the other token can detect the loss and regenerate a new token. Simulations have been carried out to evaluate the effectiveness and performance of the proposed algorithm in comparison with the timeout-based approach. The results show that the timeout-based algorithm may falsely claim the loss of a token, thus cannot guarantee the correctness of mutual exclusion algorithms. On the contrary, our proposed algorithm can avoid false detection of token losses and satisfy all the correctness requirements of mutual exclusion, though it costs a bit more messages and longer time.
AB - Most existing mutual exclusion algorithms for mobile ad hoc networks (MANETs) adopt a token-based approach. In traditional wired networks, timeout-based mechanisms are commonly used to detect token losses. However, in MANETs, it is difficult to set a proper timeout value due to the network dynamics. In this paper, we propose a dual-token-based mutual exclusion algorithm, which can tolerate token losses without using timeout. Two tokens are concurrently circulated in the system to monitor each other by using sequence numbers. If one token is lost, the other token can detect the loss and regenerate a new token. Simulations have been carried out to evaluate the effectiveness and performance of the proposed algorithm in comparison with the timeout-based approach. The results show that the timeout-based algorithm may falsely claim the loss of a token, thus cannot guarantee the correctness of mutual exclusion algorithms. On the contrary, our proposed algorithm can avoid false detection of token losses and satisfy all the correctness requirements of mutual exclusion, though it costs a bit more messages and longer time.
KW - Distributed algorithm
KW - MANET
KW - Mobile computing
KW - Mutual exclusion
KW - Token loss
UR - http://www.scopus.com/inward/record.url?scp=38449106401&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
SN - 9783540770237
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 572
EP - 583
BT - Mobile Ad-hoc and Sensor Networks - Third International Conference, MSN 2007, Proceedings
T2 - 3rd International Conference on Mobile Ad-hoc and Sensor Networks, MSN 2007
Y2 - 12 December 2007 through 14 December 2007
ER -