Técnicas de agrupamiento para redes móviles ad hoc
DOI:
https://doi.org/10.17533/udea.redin.19022Palabras clave:
redes móviles ad hoc, MANET, agrupamiento (clustering), clusterheadResumen
Los métodos de agrupamiento permiten que las MANET (redes móviles ad hoc) presenten un mejor desempeño en cuanto a la rapidez de conexión, el enrutamiento y el manejo de la topología. En este trabajo se presenta una revisión sobre las técnicas de agrupamiento para MANET. Se introducen algunos temas preliminares que forman la base para el desarrollo de los algoritmos de agrupamiento, tales como: la topología de la red, el enrutamiento, la teoría de grafos y los algoritmos de movilidad. Adicionalmente, se describen algunas de las técnicas de agrupamiento más conocidas como Lowest-ID heuristic, Highest degree heuristic, DMAC (distributed mobility-adaptive clustering), WCA (weighted clustering algorithm), entre otros. El propósito central es ilustrar los conceptos principales respecto a las técnicas de agrupamiento en MANET.
Descargas
Citas
Y. Fernandess, D. Malkhi. “K-clustering in wireless ad hoc networks”. Proceedings of the second ACM inter-national workshop on Principles of Mobile Computing. 2002. pp. 31-37. DOI: https://doi.org/10.1145/584490.584497
J.P. Grady, A. McDonald. “State of the Art: Ad Hoc Networking”. M-Zones State of the Art Paper, SOA paper 05/03. 2003.
S. Sivavakeesar, G. Pavlou. “A Prediction-Based Cluste-ring Algorithm to achieve Quality of Service in Mulithop Ad Hoc Networks”. Proc. of the London Communications Symposium (LCS). 2002. pp. 157-160.
B. An, S. Papavassiliou. “A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks”. International Journal of Network Management. Vol. 11. 2001. pp. 387-395. DOI: https://doi.org/10.1002/nem.415
C. Prehofer, C. Bettstetter. “Self organization in com-munication networks: Principles and design paradigms”. IEEE Communications Magazine. Vol. 43. Issue 7. 2005. pp. 78-85. DOI: https://doi.org/10.1109/MCOM.2005.1470824
Y. P. Chen, A. L. Liestman, J. Liu. Ad Hoc and Sensor Networks, Wireless Networks and Mobile Computing. Clustering Algorithms for Ad hoc Wireless Networks. Vol. 2. Chapter 7: Nova Science Publishers, Hauppage NY, 2004. pp. 145-164.
J. Wu, J. Cao. “Connected k-hop clustering in ad hoc networks”. ICPP. 2005. pp 373-380.
I. Chatzigiannakis, S. Nikoletseas. “Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hoc mobile networks”. Mobile Networks and Applications. Vol. 9. 2004. pp. 319-332. DOI: https://doi.org/10.1023/B:MONE.0000031591.74793.52
M. Frodigh, P. Johansson, P. Larsson. “Wireless Ad Hoc Networking--The Art of Networking without a Net-work”. Ericsson Review. Vol. 77. 2000. pp. 248-263.
P. Krishna, N.H. Vaidya, M. Chatterjee, D.K. Pradhan. “A cluster-based approach for routing in dynamic net-works”. ACM SIGCOMM Computer Communication Review. 1997. pp. 49-65. DOI: https://doi.org/10.1145/263876.263885
S. Srivastava, R. K. Ghosh. “Cluster based routing using a k-tree core backbone for mobile ad hoc networks”. Proceedings of the 6th international workshop on discrete algorithms and methods for mobile computing and communications. 2002. pp. 14-23. DOI: https://doi.org/10.1145/570810.570813
Y.P. Chen, A. L. Liestman. “A zonal algorithm for clustering ad hoc networks”. International Journal of Foundations of Computer Science. Vol.14. 2003. pp. 305-322. DOI: https://doi.org/10.1142/S0129054103001741
Y. Yi, M. Gerla, T. J. Kwon. “Efficient flooding in ad hoc networks: a comparative performance study”. Proc. of the IEEE International Conference on Communications (ICC). Vol. 2. 2003. pp. 1059-1063.
S. Sesay, Z. Yang, J. He. “A survey on mobile ad hoc wireless network”. Information Technology Journal. Vol. 3. 2004. pp. 168-175. DOI: https://doi.org/10.3923/itj.2004.168.175
A. B. McDonald, T. F. Znati. “A mobility-based framework for adaptive clustering in wireless Ad Hoc networks”. IEEE Journal on Selected Areas in Communications. Vol. 17. 1999. pp. 1466-1487. DOI: https://doi.org/10.1109/49.780353
R. Rajaraman. “Topology control and routing in ad hoc networks: a survey”. SIGACT News, Vol. 33. 2002. pp. 60-73. DOI: https://doi.org/10.1145/564585.564602
V. Kawadia, P. R. Kumar. “Power control and clustering in ad hoc networks”. INFOCOM 2003, Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. Vol.1. 2003. pp. 459-469.
L. Bao, J.J. Garcia-Luna-Aceves. “Topology management in ad hoc networks”. Proceedings of the 4th ACM international symposium on mobile ad hoc networking & computing. Vol. 9. 2003. pp. 129-140. DOI: https://doi.org/10.1145/778415.778432
L. Wang and S. Olariu. “Cluster maintenance in mobile ad-hoc networks”. Cluster Computing. Vol. 8. 2005. pp. 111-118. DOI: https://doi.org/10.1007/s10586-005-6176-6
T. C. Hou, T. J. Tsai. “An Access-Based Clustering Protocol for Multihop Wireless Ad Hoc Networks”. IEEE J. Selected Areas Comm. Vol. 19. 2001. pp. 1201-1210. DOI: https://doi.org/10.1109/49.932689
I. Er and W. Seah. “Mobility-based d-hop clustering algorithm for mobile ad hoc networks”. IEEE Wireless Communications and Networking Conference. Vol. 4. 2004. pp. 2359-2364.
G. Lugano. “Clustering for hierarchical routing”. 2003.[Online]. Available: http://www.cs.helsinki.fi/u/floreen/adhoc/lugano.pdf. Consultado julio de 2006.
R. Purtoosi, H. Taheri, A. Mohammadi, F. Foroozan. “A light-weight contention-based clustering algorithm for wireless ad hoc networks,” Computer and Information Technology (CIT ’04). 2004. pp. 627-632. DOI: https://doi.org/10.1109/CIT.2005.14
W. Lou, J. Wu. “An enhanced message exchange mechanism in cluster-based mobile ad hoc networks”. ISPA. 2004. pp. 223-232. DOI: https://doi.org/10.1007/978-3-540-30566-8_28
M. Gerla, J. Tsai. “Multicluster, mobile, multimedia radio network”. Wireless networks. Vol 1. 1995. pp. 255-265. DOI: https://doi.org/10.1007/BF01200845
C.R. Lin, M. Gerla. “Adaptive clustering for mobile wireless networks”. IEEE Journal of Selected Areas in Communications. Vol. 15. 1997. pp. 1265-1275. DOI: https://doi.org/10.1109/49.622910
G. Chen, F. Nocetti, J. Gonzalez, and I. Stojmenovic, “Connectivity based k-hop clustering in wireless networ-ks”. Proceedings of the 35th Annual Hawaii International Conference on System Sciences. Vol. 7. 2002. pp. 188.3.
M. Marathe, H. Breu, H. Ravi, and D. Rosenkrantz. “Simple heuristics for unit disk graphs”. 1995. [Online]. Available: http://citeseer.ist.psu.edu/marathe95simple.html. Consultado Julio de 2006.
B. Clark, C. J. Colbourn, and D. S. Johnson. “Unit disk graphs”. Discrete Mathematics. Vol. 86. 1990. pp. 165-177. DOI: https://doi.org/10.1016/0012-365X(90)90358-O
K. M. Alzoubi, P.-J. Wan, and O. Frieder. “Weakly-con-nected dominating sets and sparse spanners in wireless ad hoc networks”. Proceedings of the 23rd International Conference on Distributed Computing Systems. 2003. pp. 96-104.
J.N. Al-Karaki, A.E. Kamal, R. Ul-Mustafa. “On the optimal clustering in mobile adhoc networks”. First IEEE Consumer Communications and Networking Conference (CCNC). 2004. pp. 71-76.
A. Ephremides, J.E. Wieselthier, D.J. Baker. “A design concept for reliable mobile radio networks with frequen-cy hoping signaling”. Proc. IEEE 75. 1987. pp. 56-73. DOI: https://doi.org/10.1109/PROC.1987.13705
A. Parekh. “Selecting routers in ad hoc wireless net-works”. Proceedings of the SBT/IEEE International Telecommunications Symposium. 1994.
S. Basagni. “Distributed clustering for ad hoc networks”. Proc. ISPAN’99 Int. Symp. On Parallel Architectures, Algorithms, and Networks. 1999. pp. 310-315.
Y. P. Chen, A. L. Liestman. “Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks”. Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing. 2002. pp. 165-172. DOI: https://doi.org/10.1145/513800.513821
D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, A. Srinivasan. “Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons”. Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms, (SODA). 2003. pp. 717-724.
J. Habetha, B. Walke. “Fuzzy rule-based mobility and load management for self-organizing wireless networks”. International Journal of Wireless Information Networks. Vol. 9. 2002. pp. 119-140. DOI: https://doi.org/10.1023/A:1015355817270
I., Hwang, C. Liu, C. Wang. “Link stability based clustering and routing in ad-hoc wireless networks using fuzzy ser theory”. International Journal of Wireless Information Networks. Vol. 9. 2002. pp. 201-212.
A.D. Amis, R. Prakash, T.H.P Vuong, D.T. Huynh. “Max-Min D-Cluster Formation in Wireless Ad Hoc Networks”. Proceedings of IEEE Conference on Computer Communications (INFOCOM). Vol. 1. 2000. pp. 32-41.
M. Chatterjee, S. K. Das, D. Turgut. “WCA: A Weighted clustering algorithm for mobile ad hoc networks”. Cluster Computing. Vol. 5. 2002. pp. 193-204. DOI: https://doi.org/10.1023/A:1013941929408
A. B. McDonald, T. F. Znati. “Design and Simulation of a Distributed Dynamic Clustering Algorithm for Multimode Routing in Wireless Ad Hoc Networks”. SIMULATION. Vol. 78. 2002. pp. 408-422. DOI: https://doi.org/10.1177/0037549702078007579
A. Gopalan, S. Dwivedi, T. Znati, B. McDonald. “On the Implementation and Performance of the (α, t) Protocol on Linux”. SIMULATION. Vol. 81. 2005. pp. 413-424. DOI: https://doi.org/10.1177/0037549705056252
P. Basu, N. Khan, T. D. C. Little. “A mobility based metric for clustering in mobile ad hoc networks”. Proceedings of the 21st International Conference on Distributed Computing Systems. 2001. pp. 413.
D. Turgut, S.K. Das, R. Elmasri, B. Turgut. “Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach”. Global Telecommunications Conference, IEEE. Vol. 1. 2002. pp. 62-66.
D. Turgut, B. Turgut, R. Elmasri, T. V. Le. “Optimizing clustering algorithm in mobile ad hoc networks using simulated annealing”. Wireless Communications and Networking, IEEE. Vol. 3. 2003. pp.1492-1497.
C. Ji, Y. Zhang, S. Gao, P. Yuan, Z. Li. “Particle swarm optimization for mobile ad hoc networks clustering”. IEEE International Conference on Networking, Sensing and Control. Vol. 1. 2004. pp. 372-375.
C. Bettstetter. “The Cluster Density of a Distributed Clustering Algorithm in Ad Hoc Networks”. Proc. IEEE Intern. Conf. on Communications (ICC). Vol. 7. 2004. pp. 4336-4340.
C.-C. Chiang, H.-K. Wu, W. Liu, M. Gerla. “Routing in clustered multihop, mobile wireless networks with fading channel”. IEEE Singapore International Conference on Networks (SICON). 1997. pp. 197-211.
Y. -X. Wang, F. S. Bao. “An Entropy-based Weighted Clustering Algorithm and Its Optimization for Ad Hoc Networks”. 2006. [Online]. Available: http://forrest.bao.googlepages.com/WCA_ETS.pdf. Consultado diciembre de 2006. DOI: https://doi.org/10.1109/WIMOB.2007.4390850
K. Robinson, D. Turgut, M. Chatterjee. “An entropy-ba-sed clustering in mobile ad hoc networks”. Proceedings of the 2006 IEEE International Conference on Networking, Sensing and Control (ICNSC). 2006. pp. 1-5. DOI: https://doi.org/10.1109/ICNSC.2006.1673108
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Los artículos disponibles en la Revista Facultad de Ingeniería, Universidad de Antioquia están bajo la licencia Creative Commons Attribution BY-NC-SA 4.0.
Eres libre de:
Compartir — copiar y redistribuir el material en cualquier medio o formato
Adaptar : remezclar, transformar y construir sobre el material.
Bajo los siguientes términos:
Reconocimiento : debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o su uso.
No comercial : no puede utilizar el material con fines comerciales .
Compartir igual : si remezcla, transforma o construye a partir del material, debe distribuir sus contribuciones bajo la misma licencia que el original.
El material publicado por la revista puede ser distribuido, copiado y exhibido por terceros si se dan los respectivos créditos a la revista, sin ningún costo. No se puede obtener ningún beneficio comercial y las obras derivadas tienen que estar bajo los mismos términos de licencia que el trabajo original.
Twitter