A Comprehensive review of self-stabilization algorithm and its applications in wireless networks

Majlesi Journal of Telecommunication Devices

مقاله 2، دوره 10، شماره 4، اسفند 2021، صفحه 147-158   

نوع مقاله: Articles

نویسندگان

zargham heidari^{* 1}؛ hamed Gorginpour²؛ Mahdi Shahparasti³

¹Faculty member of Islamic Azad University

²Assistant Professor Department of Electrical Engineering Persian Gulf University, Bushehr, Iran

³Assistant Professor, Islamic Azad University, East Tehran Branch, Tehran ,Iran

چکیده

Distributed computing is a field of the vast computer science that deals with distributed systems. These systems have a significant role in computing with high efficiency. One of the important cases with a great role in distributed systems is ​​the self-stabilizing concept. One of the new algorithms with a critical role in engineering and computer science is self-stabilization algorithm. This algorithm is known as a lightweight and convenient property relative to other classic solutions and methods of fault tolerance in obtaining fault tolerance (FT). Moreover, in terms of time and space, the art of this algorithm is that it needs less time and space. These features have made the self-stabilization algorithm highly promising for use in distributed systems that are equipped with low computing and low memory processes. Wireless sensor networks (WSNs) include many sensor nodes that can receive, collect, process and transfer data. These networks are widely used in industrial, military, and civilian uses like industrial facility management, power / engine sources monitoring, target routing, care, healthcare management, and geographic information analysis, and so on. The paper, comprehensively, discussed this algorithm and its uses in wireless networks.

کلیدواژه‌ها

Self-stabilization algorithm؛ FT؛ convergence؛ wireless networks؛ self-stabilizing time

مراجع

[1] Edsger W. Dijkstra., “Self-stabilization in spite of distributed control.” , Technical

Report EWD 391, University of Texas, 1973. Published in 1982 as Selected Writings on Computing: A Personal Perspective, Springer-Verlag, OPT.

[2] Gerard Tel, “Introduction to Distributed Algorithms” , 2nd ed., Cambridge University

Press, 2001.

[3] Shlomi Dolev, “Self-Stabilization” , MIT Press, 2000.

[4] Sebastien Tixeuil, “Toward Self-Stabilizing Large-Scale Systems”, Habilitation à

diriger des recherches, Universite Paris Sud - Paris XI, 2006. 4

[5] Chi-Hung Tzeng, Jehn-Ruey Jiang, and Shing-Tsaan Huang, ”Size-independent self-stabilizing asynchronous phase synchronization in general graphs”, Journal of Information Science and Engineering, 26(4):1307–1322, 2010

[6] Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry, “Computing shortest, fastest, and foremost journeys in dynamic networks”, International Journal of Foundations of Computer Science, 14(2):267–285, 2003

[7] Jeffrey O. Kephart and David M. Chess, “The vision of autonomic computing” ,Computer, 36(1):41-50, 2003

(8] Markus C. Huebscher and Julie A. McCann. “A survey of autonomic computing:Degrees, models, and applications.” , ACM Computing Surveys, 40(3):1–28, 2008.

[9] Ted Richard Herman, “ Adaptivity through distributed convergence” , Ph.D. thesis,University of Texas at Austin, 1992.

[10] Ajoy K. Datta, Eugene Outley, Visalakshi Thiagarajan, and Mitchell Flatebo,” Stabilization of the x.25 connection management protocol” , International Conference on Computing and Information (ICCI), pages 1637-1654, 1994

[11] Yu Chen, Ajoy K. Datta, and Sebastien Tixeuil, “Stabilizing inter-domain routing in the internet”, Journal of High Speed Networks, 14(1):21-37, 2005

[12] Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider., “Memory requirements for silent stabilization.”, Acta Informatica, 36(6):447--462, 1999

[13] Sukumar Ghosh., “Distributed Systems: An Algorithmic Approach.”, 2nd ed., Chapman& Hall/CRC, 2014

[14] Shlomi Dolev, Amos Israeli, and Shlomo Moran., “Self-stabilization of dynamic systems assuming only Read/Write atomicity.”, Distributed Computing, 7(1):3–16, 1993

[15] Alain Cournier, Ajoy K. Datta, Franck Petit, and Vincent Villain., “Snap stabilizing PIF algorithm in arbitrary networks. “, Proc. of the 22nd International Conference on Distributed Computing Systems (ICDCS), pages 199–206, 2002.

[16] Alain Bui, Ajoy K. Datta, Franck Petit, and Vincent Villain., “ State-optimal snap-stabilizing PIF in tree networks.”, Anish Arora, Ed., Workshop on Self-stabilizing Systems, pages 78–85, IEEE Computer Society, 1999

[17] Ted Richard Herman., “ Adaptivity through distributed convergence.” , Ph.D. thesis, University of Texas at Austin, 1992.

[18] Colette Johnen., “ Memory efficient, self-stabilizing algorithm to construct BFS spanning trees.” , James E. Burns and Hagit Attiya, Eds., Proc. of the 16th Annual ACM Symposium on Principles of Distributed Computing, page 288, 1997

[19] Mohamed G. Gouda and Nicholas J. Multari., “ Stabilizing communica tion protocols.”, IEEE Transactions on Computers, 40(4):448-458, 1991

[20] Yehuda Afek and Anat Bremler-Barr., “ Self-stabilizing unidirectional network algorithms by power supply.”, Chicago Journal of Theoretical Computer Science, 1998.

[21] Edsger W. Dijkstra., “ Self-stabilizing systems in spite of distributed control.”, Communications of the ACM, 17(11):643–644, 1974.

[22] Mohamed G. Gouda and Ted Herman., “ Stabilizing unison.”, Information Processing Letters, 35(4):171-175, 1990

[23] Alain Cournier, Ajoy K. Datta, Stephane Devismes, Franck Petit, and Vincent Villain., “ The expressive power of snap-stabilization.”, Theoretical Computer Science, 626:40–66, 2016

[24] Shmuel Katz and Kenneth J. Perry., “ Self-stabilizing extensions for message-passing systems.”, Distributed Computing, 7(1):17–26, 1993

[25] Lelia Blin, Maria Potop-Butucaru, Stephane Rovedakis, and Sebastien Tixeuil., “Loop-free super-stabilizing spanning tree construction.” ,In Proc. of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 50–64, Springer LNCS 6366, 2010

[26] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.”, Distributed Computing, 7(1):61-66, 1993

[27] Alain Bui, Ajoy K. Datta, Franck Petit, and Vincent Villain., “ Optimal PIF in tree networks.”, The 2nd International Meeting on Distributed Data and Structures 2 (WDAS), pages 1-16, 1999. 8, 47

[28] Alain Cournier, Swan Dubois, Anissa Lamani, Franck Petit, and Vincent Villain., “The snap-stabilizing message forwarding algorithm on tree topologies.”, Theoretical Computer Science, 496:89–112, 2013

[29] Bertrand Ducourthial and Sebastien Tixeuil., “ Self-stabilization with r-operators.” ,Distributed Computing, 14(3):147-162, 2001

[30] Jorge A. Cobb and Mohamed G. Gouda., “ Stabilization of routing in directed networks.”,The 5th International Workshop on Self-Stabilizing Systems (WSS), pages 51–66, Springer LNCS 2194, Springer Berlin Heidelberg, 2001

[31] Ajoy K. Datta, Shivashankar Gurumurthy, Franck Petit, and Vincent Villain., “Self-stabilizing network orientation algorithms in arbitrary rooted networks.” ,Studia Informatica Universalis, 1(1):1-22, 2001

[32] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.” , Distributed Computing, 7(1):61-66, 1993

[33] Shing-Tsaan Huang, Tzong-Jye Liu, and Su-Shen Hung., “ Asynchronous phase synchronization in uniform unidirectional rings.”, IEEE Transactions on Parallel and Distributed Systems, 15(4):378–384, 2004

[34] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.” , Distributed Computing, 7(1):61–66, 1993

[35] Carole Delporte-Gallet, Stephane Devismes, and Hugues Fauconnier., “Stabilizing leader election in partial synchronous systems with crash failures.”, Journal of Paralla! and Distributed Computing, 70(1):45–58, 2010

[36] Toshimitsu Masuzawa and Hirotsugu Kakugawa., “ Self-stabilization in spite of frequent changes of networks: Case study of mutual exclusion on dynamic rings.” ,In Ted Herman and Sebastien Tixeuil, Eds., Self-Stabilizing Systems, 7th International Symposium, (SSS), Proceedings, volume 3764 of Lecture Notes in Computer Science, pages 183–197, Springer, Barcelona, Spain, October 26–27, 2005

[37] Lelia Blin and Sebastien Tixeuil., “ Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative.”, Distributed Computing, 31(2):139-166, 2018

[38] Pranay Chaudhuri and Hussein Thompson., “ Improved self-stabilizing algorithms for 1(2, 1)-labeling tree net urks.”, Mathematics in Computer Science, 5(1):27–39, 2011

[39] Volker Turau and Sven Köhler., “ A distributed algorithm for minimum distance-k domination in trees.” , Journal of Graph Algorithms and Applications, 19(1):223–242

[40] Ajoy K. Datta, Stephane Devismes, Lawrence L. Larmore, and Vincent Villain., “ Self-stabilizing weak leader election in anonymous trees using constant memory per edge.”, Parallel Processing Letters, 27(2):1-18, 2017

[41] Sukumar Ghosh and Mehmet Hakan Karaata., “ A self-stabilizing algorithm for coloring planar graphs.”, Distributed Computing, 7(1):55-59, 1993

[42] Ji-Cherng Lin and Ming-Yi Chiu., “ A fault-containing self-stabilizing algorithm for 6-coloring planar graphs.”, Journal of Information Science and Engineering, 26(1):163-181, 2010

[43] Ajoy K. Datta, Colette Johnen, Franck Petit, and Vincent Villain., “ Self-stabilizing depth-first token circulation in arbitrary rooted networks.”,Distributed Computing, 13(4):207–218, 2000

[44] Stephane Devismes, Swan Dubois, and Franck Petit., “ Introduction to Distributed Self-Stabilizing Algorithms.”, Karine Altisen,Copyright © 2019 by Morgan & Claypool

[45] Rahul C. Shah and Jan M. Rabaey., “ Energy aware routing for low energy ad hoc sensor networks.”, IEEE Wireless Communications and Networking Conference (WCNC), March 2002

[46 ] F. Wang, J. Liu., “ Networked wireless sensor data collection: issues, challenges, and approaches.” , Commun. Surv. Tutor. IEEE 13 (4) (2011) 673 -687

[47] J.Y. Chang, P.H. Ju., “ An efficient cluster-based power saving scheme for wireless sensor networks.” ,EURASIP J. Wirel. Commun. Netw. 2012 (1) (2012) 1-10

[ 48 ] D. Li, K.D. Wong, Y.H. Hu, A.M. Sayeed., “ Detection, classification, and tracking of targets, Signal.”, Proc. Mag. IEEE 19(2)(2002) 17-29

[ 49 ] Y. Durmus, A. Ozgovde, C. Ersoy., “ Distributed and online fair resource management in video surveillance sensor networks.”, Mobile Comput. IEEE Transac. 11 (5) (2012) 835-848.

[ 50 ] H. Modares, R. Salleh, A. Moravejosharieh., “ Overview of security is sues in wireless sensor networks.” ,Third International Conference on Computational Intelligence, Modelling and Simulation (CIMSIM), 2011, IEEE, 2011, September, pp. 308-311

[ 51 ] P.N. Reddy, P.I. Basarkod, S.S. Manvi., “ Wireless sensor network based fire monitoring and extinguishing system in real time environment.”, Int. J. Adv. Netw. Appl. 3 (02) (2011) 1070-1075.

[ 52 ] Gokou Herve Fabrice Diedie :, Boko Aka', Michel Babric., “Self-stabilising hybrid connectivity control protocol for WSNS.”, IET Journal , 2018,July.

[ 53 ] Baccour, N., Koubầa, A., Noda. C., et al., “Radio link quality estimation in low-power wireless networks” (Springer International Publishing, London, 2013)

[ 54 ] Bas, C.U.. Ergen, S.C., “Spatio-temporal characteristics of link quality in wireless sensor networks.”,Proc. IEEE Wireless Communications and Networking Conf. (WCNC), Shanghai, China, April 2012, pp. 1152–1157

[ 55 ]Jalel Ben-Othman, Karim Bessaoud, Alain Bui and Laurence Pilard., “ Self-stabilizing algorithm for energy saving in Wireless Sensor Networks.”, IEEE Conference proce, pp.68-73,2011

[ 56 ] Jalel Ben-Othman, Karim Bessaoud, Alain Bui and Laurence Pilard.,” An energy-efficient QoS routing for