A Token Based Protocol for Mutual Exclusion in Mobile Ad Hoc Networks
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Resource sharing is a major advantage of distributed computing. However,a distributed computing system may have some physical or virtual resource that maybe accessible by a single process at a time. The mutual exclusion issue is to ensurethat no more than one process at a time is allowed to access some shared resource. The article proposes a token-based mutual exclusion algorithm for the clustered mobile ad hoc networks (MANETs). The mechanism that is adapted to handle token passing at the inter-cluster level is different from that at the intra-cluster level. It makes ouralgorithm message efficient and thus suitable for MANETs. In the interest of efficiency,we implemented a centralized token passing scheme at the intra-cluster level. Thecentralized schemes are inherently failure prone. Thus, we have presented an intracluster token passing scheme that is able to tolerate a failure. In order to enhancereliability, we applied a distributed token circulation scheme at the inter-cluster level. More importantly, the message complexity of the proposed algorithm is independent ofN, which is the total number of nodes in the system. Also, under a heavy load, it turnsout to be inversely proportional to n, which is the (average) number of nodes per each cluster. We substantiated our claim with the correctness proof, complexity analysis, and simulation results. In the end, we present a simple approach to make our protocol fault tolerant.
Abstract
Resource sharing is a major advantage of distributed computing. However,a distributed computing system may have some physical or virtual resource that maybe accessible by a single process at a time. The mutual exclusion issue is to ensurethat no more than one process at a time is allowed to access some shared resource. The article proposes a token-based mutual exclusion algorithm for the clustered mobile ad hoc networks (MANETs). The mechanism that is adapted to handle token passing at the inter-cluster level is different from that at the intra-cluster level. It makes ouralgorithm message efficient and thus suitable for MANETs. In the interest of efficiency,we implemented a centralized token passing scheme at the intra-cluster level. Thecentralized schemes are inherently failure prone. Thus, we have presented an intracluster token passing scheme that is able to tolerate a failure. In order to enhancereliability, we applied a distributed token circulation scheme at the inter-cluster level. More importantly, the message complexity of the proposed algorithm is independent ofN, which is the total number of nodes in the system. Also, under a heavy load, it turnsout to be inversely proportional to n, which is the (average) number of nodes per each cluster. We substantiated our claim with the correctness proof, complexity analysis, and simulation results. In the end, we present a simple approach to make our protocol fault tolerant.
참고문헌 (16)
- A. Kshemkalyani, "Distributed Computing: Principles, Algorithms, and Systems", pp.327~336 (2008), Cambridge University Press
- P. Saxena, "A Survey of Permission-based Mutual Exclusion Algorithms", Journal of Computer Standards and Interface, 25(2), pp.159~181 (2003)
- B. Badrinath, "Designing Distributed Algorithms for Mobile Computing Networks", Computer Communications, 19, pp.309~320 (1996)
- R. Ghosh, "On Restructuring Distributed Algorithms for Mobile Computing", IWDC 2002, LNCS, 2571, pp.224~233 (2002)
- M. Bertier, "Distributed Mutual Exclusion Algorithms for Grid Applications:A Hierarchical Approach", Journal of Parallel and Distributed Computing, 66(1), pp.128~144 (2006)
- H. Taheri, "A Hybrid Token-based Distributed Mutual Exclusion Algorithm using Wraparound Two-Dimensional Array Logical Topology", Information Processing Letters, 111(17), pp.841~847 (2011)
- P. Neamatollahi, "Info-based Approach in Distributed Mutual Exclusion Algorithms", Journal of Parallel and Distributed Computing, 72(5), pp.650~665 (2012)
- L. Rodrigues, "A Robust Permission-based Hierarchical Distributed k-Mutual Exclusion Algorithm", IEEE 12th International Symposium on Parallel and Distributed Computing (ISPDC), pp.151~158 (2013)
- M. Benchaiba, "Distributed Mutual Exclusion Algorithms in Mobile Ad Hoc Networks : An Overview", ACM SIGOPS Operating Systems Review, 38(1), pp.74~89 (2004)
- B. Sharma, "DMX in MANETs: Major Research Trends Since 2004", Int. Conf. on Advances in Computing and Artificial Intelligence, ACAI’11, pp.50~55 (2004)
- H. Hartenstein, "A Tutorial Survey on Vehicular Ad Hoc Networks", IEEE Communications Magazine, pp.164~171 (2008)
- V. Kumar, "An Efficient Algorithm for Mutual Exclusion using Queue Migration in Computer Networks", IEEE Trans. Knowledge and Data Engineering, 3(3), pp.380~384 (1991)
- P. Chaudhury, "An O(√n)Distributed Mutual Exclusion Algorithm using Queue Migration", Journal of Universal Computer Science, 12(2), pp.142~159 (2006)
- R. Baldoni, "A Distributed Mutual Exclusion Algorithm for Mobile Ad Hoc Networks", 7th IEEE Symposium on Computer and communications (ISCC’02), pp.539~545 (2002)
- S. Tamhane, "A Token Based Distributed Algorithm for Supporting Mutual Exclusion in Opportunistic Networks", Pervasive and Mobile Computing, 8(5), pp.795~809 (2012)
- W. Wu, "A Dual-token-based Fault Tolerant Mutual Exclusion Algorithm for MANETs", LNCS, 4864, pp.572~583 (2007)