×

Mutual exclusion in MANETs using quorum agreements. (English) Zbl 1382.68033

Summary: The quorum agreement has been used in static distributed systems for numerous applications like mutual exclusion, distributed commit, and replication. The article proposes a framework to use quorum agreement in mobile ad hoc networks. The correctness proof, complexity analysis, and simulation measurements have also been presented.

MSC:

68M14 Distributed systems
68M12 Network protocols

Software:

Vivaldi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kshemkalyani AD, Singhal M (2008) Distributed computing: principles, algorithms, and systems. Cambridge University Press, NY, pp 327-336 · Zbl 1151.68004 · doi:10.1017/CBO9780511805318
[2] Benchaiba M et al (2004) Distributed mutual exclusion algorithms in mobile ad hoc networks: an overview. ACM SIGOPS Oper Syst Rev 38(1):74-89 · doi:10.1145/974104.974111
[3] Sharma B, et al. (2011) DMX in MANETs: major research trends since 2004. ACM ACAI’11, pp 50-55
[4] Park VD, Corson MS (1997) A highly adaptive distributed routing algorithm for mobile wireless networks. IEEE INFOCOM’97, pp 1405-1413
[5] Barbara D, Garcia-Molina H (1986) Mutual exclusion in partitioned distributed systems. Distrib Comput 1(2):119-132 · doi:10.1007/BF01786230
[6] Junqueira F, Marzullo K (2005) Coterie availability in sites. In: 19th international symposium on distributed computing DISC’05, LNCS, 3724:3-17 · Zbl 1171.68376
[7] Mizuno M, Neilsen ML, Rao R (1991) A token based distributed mutual exclusion algorithm based on quorum agreements. In: 11th international conference on distributed computing systems, pp 361-368
[8] Okabe A et al (2000) Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley, Chichester · Zbl 0946.68144 · doi:10.1002/9780470317013
[9] Shamos MI, Hoey D (1975) Closest-point problems. In: 16th Annu IEEE Sympos Found Comput Sci, pp 151-162
[10] Bentley JL, Ottmann TA (1979) Algorithms for reporting and counting geometric intersections. IEEE Trans Comput 28(9):643-647 · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[11] Fortune SJ (1987) A sweepline algorithm for Voronoi diagrams. Algorithmica 2:153-174 · Zbl 0642.68079 · doi:10.1007/BF01840357
[12] Steenstrup, M.; Perkins, CE (ed.), Cluster based networks, Chapter 4 (2001), Boston
[13] Perkins CE, Belding-Royer EM, Das S (2003) Ad hoc on demand distance vector (AODV) routing. RFC 3561
[14] Naor M, Wieder U (2003) Scalable and dynamic quorum systems. In: ACM PODC, pp 114-122 · Zbl 1321.68090
[15] Ratnasamy S, et al. (2001) A scalable content-addressable network. ACM SIGCOMM, pp 161-172
[16] Ghiasi S, Srivastava A, Yang X, Sarrafzadeh M (2002) Optimal energy aware clustering in sensor networks. Sensors 2(7):258-269 · doi:10.3390/s20700258
[17] Jardosh A, Belding-Royer E, Almeroth K, Suri S (2003) Towards realistic mobility models for mobile ad hoc networks. In: ACM annual international conference on mobile computing and networking, MobiCom’03, pp 217-229
[18] de Berg M, van Kreveld M, Overmars M, Schwarzkopf O (2000) Computational geometry: algorithms and applications. Springer, Berlin · Zbl 0939.68134 · doi:10.1007/978-3-662-04245-8
[19] Shamos M, Preparata F (1985) Computational geometry. Springer, Berlin · Zbl 0575.68059
[20] Cao M, Hadjicostis C (2003) Distributed algorithms for Voronoi diagrams and applications in ad-hoc networks. In: Technical report, UILU-ENG-03-2222-DC-210-UIUC, Coordinated Science Laboratory · Zbl 0414.68074
[21] Thorup M, Zwick U (2001) Compact routing schemes. In: ACM symposium on parallelism in algorithms and architectures, SPAA’01, pp 1-10 · Zbl 0642.68079
[22] Honiden S, Houle M, Sommer C (2009) Balancing graph voronoi diagrams. In: 6th IEEE international symposium on Voronoi diagrams, pp 183-191 · Zbl 0642.68079
[23] Dang H, Wu H (2009) Mobility models for delay-tolerant mobile networks. In: 3rd IEEE international conference on sensor technologies and applications, SENSORCOMM ‘09, pp 55-60
[24] Doci A, Samakovitis G, Raju V (2009) Impact of mobility in ad hoc protocol design. In: 2009 WRI world congress on computer science and information engineering, 1:38-43
[25] Ghosh J, Ngo H, Qiao C (2006) Mobility profile based routing within intermittently connected mobile ad hoc networks (ICMAN). In: ACM international conference on wireless communications and mobile computing, IWCMC’06, Vancouver, British Columbia, Canada, pp 551-556
[26] Kim M, Kotz D, Kim S (2006) Extracting a mobility model from real user traces. In: 25th IEEE INFOCOM, pp 1-13
[27] Lee J-K, Hou JC (2006) Modeling steady-state and transient behaviors of user mobility: formulation, analysis, and application. ACM MobiHoc’06, pp 85-96 · Zbl 1151.68318
[28] Liu G, Maguire G Jr (1995) A predictive mobility management algorithm for wireless mobile computing and communications. In: IEEE international conference on universal personal communications (ICUPC’95), Tokyo, Japan, pp 268-272
[29] Marlevi A, Danne A, Liu G (1994) Method and apparatus for detecting and predicting of mobile terminals. In: Ericsson patent No. 027500-969
[30] Prasad PS, Agrawal P (2010) Movement prediction in wireless networks using mobility traces. In: 7th IEEE consumer communications and networking conference (CCNC), pp 1-5
[31] Resta G, Santi P (2008) WiQoSM: an integrated QoS-aware mobility and user behavior model for wireless data networks. IEEE Trans Mobile Comput 7(2):187-198 · doi:10.1109/TMC.2007.70728
[32] Su J, Chin A, Popivanova A, Goel A, de Lara E (2004) User mobility for opportunistic ad-hoc networking. In: 6th IEEE workshop on mobile computing systems and applications (WMCSA), Lake District, England, pp 41-50
[33] Tuduce C, Gross T (2005) A mobility model based on WLAN traces and its validation. In: 24th annual joint conference of the IEEE computer and communications societies, INFCOM, 1:664-674
[34] Erbas F, Garcia J-E, Jobmann K (2004) Position-based QoS routing in mobile ad hoc networks: problem statement and a novel approach. In: 23rd IEEE international performance computing and communication conference, pp 619-624
[35] Punde J, Pissinou N, Makki K (2003) On quality of service routing in ad-hoc networks. In: Proceedings of the 28th annual IEEE international conference on local computer networks (LCN’03), pp 276-278
[36] Chen I-R, Verma N (2003) Simulation study of a class of autonomous host-centric mobility prediction algorithms for wireless cellular and ad hoc networks. In: 36th Annual Simulation Symposium (ANSS’03), pp. 65-72
[37] Vetriselvi V, Parthasarathi R (2007) Trace based mobility model for ad hoc networks. In: 3rd IEEE international conference on wireless and mobile computing, networking and communications (WiMob’07), pp 1-8
[38] Dabek F, Cox R, Kaashoek F, Morris R (2004) Vivaldi: a decentralized network coordinate system. In: ACM conference on applications, technologies, architectures, and protocols for computer communications, SIGCOMM’04, Portland, Oregon, USA. pp 15-26
[39] Das S, Nandan A, Parker M, Pau G, Gerla M (2005) Grido—an architecture for a grid-based overlay network. In: 2nd IEEE international conference on quality of service in heterogeneous wired/wireless networks (QShine’05), pp 8-27 · Zbl 1131.68017
[40] Ng TSE, Zhang H (2002) Predicting Internet network distance with coordinates-based approaches. IEEE INFOCOM, pp 170-179 · Zbl 0378.68027
[41] Zhuo C, Kai L, Jun Z (2006) A novel location-based routing algorithm for mobile ad hoc networks. In: IEEE international conference on wireless communications, networking and mobile computing, WiCOM’06, pp 1-4
[42] Al-Karaki J, Kamal A (2008) Efficient virtual-backbone routing in mobile ad hoc networks. Comput Netw Int J Comput Telecommun Netw 52(2):327-350 · Zbl 1131.68017
[43] Suzuki I, Kasami T (1985) A distributed mutual exclusion algorithm. ACM Trans Comput Syst 3(4):344-349 · doi:10.1145/6110.214406
[44] Raynal M (1991) A simple taxonomy for distributed mutual exclusion algorithms. ACM SIGOPS 25(2):47-50 · doi:10.1145/122120.122123
[45] Raymond K (1989) A tree-based algorithm for distributed mutual exclusion. ACM Trans Comput Syst 7(1):61-77 · doi:10.1145/58564.59295
[46] Trehel M, Naimi M (1987) A distributed algorithm for mutual exclusion based on data structures and fault tolerance. In: 6th IEEE international conference on computers and communications, pp 35-39 · Zbl 0378.68027
[47] Lamport L (1978) Time, clocks, and the ordering of events in a distributed system. Commun ACM 21(7):558-565 · Zbl 0378.68027 · doi:10.1145/359545.359563
[48] Ricart G, Agrawala AK (1981) An optimal algorithm for mutual exclusion in computer networks. Commun ACM 24(1):9-17 · doi:10.1145/358527.358537
[49] Maekawa M (1985) A √N algorithm for mutual exclusion in decentralized systems. ACM Trans Comput Syst 3(2):145-159 · doi:10.1145/214438.214445
[50] Makki K et al (2000) Using logical rings to solve the distributed mutual exclusion problem with fault tolerance issues. J Supercomput 16(1-2):117-132 · doi:10.1023/A:1008137614672
[51] Eugster P et al (2003) The many faces of publish/subscribe. ACM Comput Surv 35(2):114-131 · doi:10.1145/857076.857078
[52] Wang G et al (2005) Sensor relocation in mobile sensor networks. IEEE INFOCOM 4:2302-2312
[53] Pei Y (2009) Hopping sensor relocation in rugged terrains. In: The 2009 IEEE/RSJ international conference on intelligent robots and systems, pp 3856-3861
[54] Jiang J-R (1996) A framework for fault-tolerant distributed mutual exclusion and replica control using grid structures. In: 8th international conference on parallel and distributed systems, pp 311-315
[55] Chinara S, Rath SK (2009) A survey on one-hop clustering algorithms in mobile ad hoc networks. J Netw Syst Manage 17(1-2):183-207 · doi:10.1007/s10922-009-9123-7
[56] Choi W, Woo M (2006) A distributed weighted clustering algorithm for mobile ad hoc networks. In: Advanced international conference on telecommunications and international conference on internet and web applications and services (AICT/ICIW), pp 7378
[57] Janakiraman TN, Thilak AS (2011) Design and analysis of SD_DWCA—a mobility based clustering of homogeneous MANETs. Int J Comput Netw Commun (IJCNC) 3(3):94-111 · doi:10.5121/ijcnc.2011.3307
[58] Konstantopoulos C, Gavalas D, Pantziou G (2008) Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction. Comput Netw 52(9):1797-1824 · Zbl 1151.68318 · doi:10.1016/j.comnet.2008.01.018
[59] Xing Z, Gruenwald L, Phang KK (2008) A robust clustering algorithm for mobile ad hoc networks. In: Pierre S (ed) Handbook of research on next generation networks and ubiquitous computing, pp 1-18
[60] Yu JY, Chong PHJ (2005) A survey of clustering schemes for mobile ad hoc networks. IEEE Commun Surv Tutor First Q 7(1):32-48 · doi:10.1109/COMST.2005.1423333
[61] Chatterjee M, Das SK, Turgut D (2002) WCA: a weighted clustering algorithm for mobile ad hoc networks. Clust Comput 5(2):193-204 · doi:10.1023/A:1013941929408
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.