5

1. REDES MVILES AD HOC

En el presente captulo se introducen las nociones bsicas sobre las redes mviles ad hoc.
En primer lugar, se hace la distincin entre los dos modos de operacin de las redes
inalmbricas, el modo infraestructura y el modo ad hoc. Luego, se presenta una definicin
sobre las MANET y se describen algunas de sus caractersticas y aplicaciones. Finalmente,
se exponen las diferentes topologas y los esquemas de enrutamiento diseados para este
tipo de redes.

1.1 REDES INALMBRICAS

Las redes inalmbricas pueden dividirse en dos categoras: las redes inalmbricas basadas
en infraestructura preestablecida y las redes ad hoc.

1.1.1 Modo infraestructura.

Las redes inalmbricas basadas en infraestructura

preestablecida se basan en conexiones de un salto a una red que emplea el cableado, como
Internet o una estacin base. Entre las redes inalmbricas actuales basadas en el modo
infraestructura se encuentran: las redes celulares, wireless LAN y los sistemas satelitales.

Figura 1.

Combinacin de cable y wireless LAN.

Fuente: LANSECURE. Lansecure individuelle Lsungen fr Ihr Unternehmen. [En lnea]

Colonia, Alemania: Lansecure-Ihr kompetenter Service- Partner, 23 Dic. 2004.
<[Link] [consulta: 2 Sep: 2005].

1.1.2 Modo ad hoc. En las redes que funcionan bajo el modo ad hoc los nodos se pueden
mover de forma libre y no dependen de un control central establecido. Un nodo puede
establecer un enlace inalmbrico con otro nodo, si este se encuentra dentro de su rango de
transmisin. De lo contrario, debe existir una ruta formada por nodos intermediarios que
faciliten la transmisin de los datos o la informacin. En este tipo de redes, la movilidad es
un factor determinante para el diseo de los algoritmos de control de la red.

Figura 2.
Fuente: Ibid.

Wireless LAN comunicacin punto a punto.

1.2 DEFINICIN

Una red mvil ad hoc (MANET) es una red inalmbrica formada por nodos mviles que se
interconectan entre s a travs de enlaces inalmbricos de comunicacin, los cuales pueden
ser de uno o de mltiples saltos. Estas redes se establecen sin una infraestructura
predefinida y no requieren de un control centralizado.
La forma bsica como opera una red mvil ad hoc se ilustra mediante la Figura 3. El nodo
A se puede comunicar directamente a travs de un solo salto con el nodo B, el nodo C y el
nodo D. Para que A pueda comunicarse con el nodo E, el nodo C debe actuar como
intermediario entre A y E, transmitiendo la informacin entre ellos.

Por lo tanto la

comunicacin entre los nodos A y E se basa en una comunicacin de mltiples saltos.

Figura 3.

Ejemplo de una red mvil ad hoc.

1.3 HISTORIA

La idea original de las MANET tuvo origen a principios de los aos 70. En ese entonces
las MANET eran conocidas como redes de radio-paquete llamadas PRNET (Packet Radio
Networks). La agencia conocida como Defense Advanced Research Projects Agency
(DARPA), se encarg de dar patrocinio a las MANET originales. En los aos 80, el
proyecto militar conocido como SURAN (Survivable Radio Systems) realiz una
implementacin mejorada de las redes ad hoc.

El progreso en el desarrollo de la microelectrnica, la computacin distribuida, los diseos

y la manufactura de circuitos VLSI y la criptografa, entre otros, ha brindado la posibilidad
de integrar dispositivos de nodos y de redes en una nica unidad denominada Nodo ad
hoc. Una red ad hoc es la interconexin inalmbrica de estos nodos. En 1994, DARPA
inici un programa conocido como GloMo (Global Mobile Information Systems) el cual fue
diseado para brindar a usuarios mviles con dispositivos inalmbricos, los mismos
beneficios de conectividad que provee Internet, en cualquier lugar y en cualquier momento.
En 1997, se estableci un grupo de trabajo (WG) sobre MANET perteneciente a la IETF.
Una de las importantes tareas que tiene este grupo de trabajo es la estandarizacin de
protocolos de enrutamiento para las redes mviles ad hoc.

Hoy en da los dispositivos inalmbricos son cada vez ms pequeos, menos costosos y
ms modernos, por lo tanto se busca mantener su conectividad a bajos precios. Una posible
forma de lograrlo es mediante el establecimiento de las redes mviles ad hoc. Por esta
razn, el foco de atencin de los estudios actuales es el de reunir diferentes esquemas para
el control de las MANET y adems presentar un estndar nico para las aplicaciones
futuras que hagan uso de estas redes.

1.4 CARACTERSTICAS

El propsito de las redes mviles ad hoc es el de apoyar operaciones robustas y eficientes,

incorporando un enrutamiento funcional en los nodos mviles. Debido a que las MANET
se pueden construir espontneamente sin necesidad de una infraestructura existente, estas
redes presentan restricciones especiales que se deben considerar para el diseo de
soluciones. A continuacin se describen algunas caractersticas:
1.4.1 Topologa dinmica. Debido a que los nodos de una red mvil ad hoc son libres de
moverse arbitrariamente, la topologa de la red (la cual es tpicamente multi-hop) puede
cambiar rpida y aleatoriamente en tiempos impredecibles. Este comportamiento dinmico
dificulta el establecimiento de la conectividad en la red, la cual se debe mantener para
permitir que los servicios de comunicacin operen sin interrupciones. Este aspecto es de
gran influencia para el diseo de los protocolos de enrutamiento.
1.4.2 Operacin en forma distribuida. El trmino distribuido hace referencia a que en
una MANET, normalmente los nodos tienen un conocimiento local sobre su entorno. Es
decir, cada nodo slo conoce la informacin sobre los nodos vecinos que se encuentran
dentro de su radio de transmisin y no tiene un conocimiento global de la red.

1.4.3 Ancho de banda limitado. El ancho de banda disponible en MANET es menor,

comparado con el ancho de banda disponible en las redes de infraestructura preestablecida.

1.4.4 Fluctuacin de los enlaces. El efecto de una alta rata de error de bits, es decir, la
transmisin de informacin errada, es ms significativo en una red mvil ad hoc de
mltiples saltos, ya que el agregado de todos los errores en los enlaces afecta
significativamente la calidad de la informacin recibida.

10

1.4.5 Operacin de energa limitada. Los nodos en una MANET requieren de una batera
para obtener la energa que asegure su funcionamiento. Por lo tanto la energa es uno de los
recursos que se busca optimizar con el fin de limitar el consumo de la potencia.

1.5 APLICACIONES

Las MANET constituyen una tecnologa ideal para el establecimiento instantneo de la

comunicacin entre nodos que son mviles y en lugares en donde no es posible construir un
backbone de comunicaciones debido a inconvenientes econmicos o a la falta de tiempo
para la construccin de la infraestructura requerida. Esta tecnologa es especialmente til en
escenarios que requieren de estrategias rpidas y eficientes de comunicacin como son las
operaciones militares o las operaciones de rescate en caso por ejemplo de incendios,
terremotos o inundaciones. Las MANET tambin se pueden emplear para extender la
cobertura de las redes inalmbricas actuales.

Figura 4.

Ejemplo de una red ad hoc aplicada en situaciones militares.

Fuente: WALI Moutie, KAHOUL Houssan. Wireless Ad Hoc Networking. [pdf]

Francia : Universit de Versailles Saint-Quentin-en-Yvelines, revisado 6 Feb. 2003.

11

<[Link]

[Consulta:

Abr: 2005].

Las redes ad hoc se pueden formar utilizando diversas tecnologas o protocolos existentes
que permiten el establecimiento de las comunicaciones inalmbricas. Actualmente
Bluetooth, las redes inalmbricas de rea personal (wireless personal area networks, PAN),
IEEE802.11, las redes inalmbricas de rea local, HIPERLAN/2 y las redes IHDN (inhouse digital networks), son estndares de comunicacin con capacidad ad hoc.

1.6 TOPOLOGAS

La topologa de una red mvil ad hoc juega un papel muy importante en el desempeo de
los algoritmos de control empleados en la red para los propsitos de sincronizacin de las
transmisiones, el enrutamiento y para realizar broadcasting.
En las MANET se pueden distinguir dos tipos de topologas fundamentales: la topologa
plana y la topologa jerrquica.

1.6.1 Topologa plana. En este tipo de topologa la red no presenta jerarquas y todos los
nodos presentan funciones iguales en cuanto al enrutamiento. Las topologas planas en las
redes ad hoc funcionan adecuadamente cuando las redes son de un tamao relativamente
pequeo. En este caso el enrutamiento se puede llevar a cabo de una manera ptima y el
consumo de potencia es bajo. Sin embargo, una topologa plana no es escalable a medida
que las redes se hacen ms grandes. En este tipo de topologas la tabla de enrutamiento es
proporcional al nmero total de nodos presentes en la red. Por lo tanto, si las redes se hacen
ms grandes las transmisiones requerirn un mayor ancho de banda y las tablas de
enrutamiento se tendrn que intercambiar con mayor frecuencia entre los nodos, con el fin
de mantener la informacin sobre el enrutamiento actualizada a medida que ocurren
cambios topolgicos en la red.

12

Figura 5.

Arquitectura plana.

1.6.2 Topologa jerrquica. Debido a que el propsito de las MANET es el de manejar un

gran nmero de nodos, una topologa plana no resulta tan ptima a la hora de crear
esquemas de enrutamiento apropiados y asegurar la escalabilidad.
Por esta razn se implementa una arquitectura jerrquica la cual divide la red en conjuntos
de nodos en los cuales cada nodo tiene conocimiento de sus vecinos. A estos conjuntos de
nodos se les conoce como clusters. El establecimiento de una topologa jerrquica en
MANET reduce significativamente las tablas de enrutamiento ya que un nodo slo necesita
tener conocimiento de la informacin sobre el enrutamiento de su propio cluster y no de la
red completa. Es decir, este tipo de topologa facilita el manejo del trfico de la red ya que
permite el enrutamiento al nivel interior del cluster (intracluster) y al nivel exterior del
cluster (intercluster). La idea es que al crear clusters de nodos en cada uno se seleccione un
nodo que acte como lder de su cluster. A este nodo se le conoce como clusterhead. Los
clusterheads son nodos que tienen la responsabilidad de transmitir los paquetes de todos los
nodos que se encuentren dentro de su cluster, a travs de la red. En la Figura 6 se presenta
el esquema de una topologa jerrquica.

13

Figura 6.

Forma de llevar a cabo el enrutamiento en una topologa jerrquica.

La asignacin de nodos mviles a los clusters debe ser un proceso dinmico el cual se debe
adaptar a la movilidad de los nodos. Por consiguiente, es necesario disear un algoritmo de
clustering que defina los criterios necesarios para construir los clusters.

1.7 ESQUEMAS DE ENRUTAMIENTO

En las redes mviles ad hoc los esquemas de enrutamiento se clasifican en cuatro grupos
importantes: flooding, enrutamiento proactivo, enrutamiento reactivo y enrutamiento
hbrido.

1.7.1 Flooding. Es un proceso distribuido en el cual un nodo transmite un paquete de

informacin a todos sus vecinos y estos a su vez transmiten el paquete a sus vecinos
respectivos, permitiendo que el paquete se propague por toda la red. Este tipo de
enrutamiento no requiere conocimiento sobre la topologa de la red. Los paquetes se
transmiten por broadcast a todos los destinos con la expectativa de que alcancen
eventualmente su destino final. Bajo condiciones de poco trfico, flooding es un mtodo

14

robusto. Sin embargo, genera una excesiva cantidad de trfico en redes grandes ya que no
se toma en cuenta el conocimiento sobre la topologa de la red. Adems es difcil lograr
confiabilidad con el flooding cuando la topologa es altamente dinmica. Este esquema de
enrutamiento tambin desperdicia una gran porcin del ancho de banda disponible.

1.7.2 Enrutamiento proactivo. La idea del enrutamiento proactivo es la de distribuir la

informacin peridicamente a travs de la red con el objetivo de calcular previamente todos
los caminos posibles. Cuando ocurre un cambio en la red, las actualizaciones se propagan
por la red con el fin de mantener las tablas de enrutamiento actualizadas. Por lo tanto, se
hace una evaluacin continua de las rutas entre los nodos. Sin embargo, se pueden generar
sobrecargas en la red afectando la utilizacin del ancho de banda, el throughput y el uso de
la energa. En una topologa esttica este esquema de enrutamiento puede funcionar de
manera adecuada. Sin embargo, en redes grandes y altamente dinmicas no presenta un
buen manejo de la escalabilidad.

1.7.3 Enrutamiento reactivo. Se basa en obtener los caminos entre los nodos evaluando la
ruta cada vez que sea necesario. Cuando un nodo necesita encontrar una ruta a un nodo
destino debe iniciar un proceso de descubrimiento de ruta. Una vez se halla la ruta
adecuada, esta se mantiene hasta que el destino se vuelve inaccesible o la ruta ya no es
requerida. Esto limita el nmero total de destinos para el cual la informacin del
enrutamiento se mantiene y por consiguiente se reduce el tamao de las tablas de
enrutamiento. Sin embargo, en este esquema la calidad de las rutas es menor en
comparacin con el enrutamiento proactivo y existe un retardo significativo durante el
proceso de descubrimiento de rutas.

1.7.4 Enrutamiento hbrido.

Este esquema, tambin conocido como enrutamiento

jerrquico, es el ms conveniente para el desarrollo de algoritmos de enrutamiento

eficientes en MANET ya que se ha observado que logra niveles adecuados de desempeo
en redes de gran tamao.
Para que se pueda llevar a cabo el enrutamiento hbrido, se debe establecer en la red una
topologa jerrquica en donde se formen clusters de manera dinmica. En el enrutamiento

15

hbrido se lleva a cabo de forma simultnea el enrutamiento intracluster e intercluster. El

enrutamiento proactivo se aplica para la comunicacin a nivel del cluster y el enrutamiento
reactivo se utiliza para la comunicacin entre los diferentes clusters.

16

2. CLUSTERING

En el captulo 1, se plante la necesidad de establecer una topologa jerrquica en las

MANET con el fin de mejorar su desempeo. Para lograr este objetivo es necesario disear
algoritmos de clustering que permitan organizar dinmicamente una

MANET en

particiones conocidas como clusters.

En este captulo se presenta un estudio sobre los algoritmos de clustering diseados hasta el
momento para MANET y se introducen algunos conceptos necesarios para la comprensin
de este tema como son la teora de grafos, los conjuntos dominantes y los papeles que
cumple cada nodo en una MANET organizada mediante clusters.

2.1 DEFINICIN

Clustering es un procedimiento en el cual se clasifican datos en diferentes grupos, segn

una medida de similitud determinada. A los diferentes grupos obtenidos se les conoce como
clusters. Los procesos de clustering realizan una particin sobre un gran conjunto de datos
llevndolos a componentes ms pequeas.
La labor de agrupar nodos en clusters de acuerdo a un criterio especfico, es similar a lo que
se realiza usualmente en el marco de trabajo del anlisis de datos. La clasificacin de datos
se prctica en muchas disciplinas del mbito cientfico.

Es importante sealar la diferencia entre la clasificacin de datos supervisada y la

clasificacin de datos no supervisada:

17

Clasificacin de datos supervisada.

En la clasificacin de datos supervisada, se

conoce de antemano los valores de la membresa o la pertenencia de un conjunto de

objetos a los diferentes grupos establecidos. Lo que se busca es desarrollar mecanismos
adecuados para clasificar nuevos objetos de acuerdo a los datos que ya se encuentran
clasificados.

Clasificacin de datos no supervisada. En la clasificacin de datos no supervisada, el

valor de la membresa que tienen los objetos en los distintos grupos no se conoce
previamente. Por lo tanto, los grupos se forman de acuerdo a un criterio que determina
el grado de similitud entre los objetos. Los objetos con alto grado de similitud
establecen un mismo grupo. Se debe tratar que los objetos pertenecientes a distintos
grupos sean en lo posible, lo ms diferentes entre s. La clasificacin de datos no
supervisada se conoce tambin como clustering.

Los procesos de clustering se emplean para el anlisis y la clasificacin de patrones, en la

exploracin de datos (data mining), la recuperacin de documentos y la segmentacin de
imgenes. 1

En el caso de las MANET, una manera fcil de abordar el mantenimiento de estas redes es
mediante un proceso de clustering. Los algoritmos que agrupan los nodos en una red mvil
ad hoc corresponden precisamente a los algoritmos de clasificacin de datos no
supervisados ya que la pertenencia de los nodos a los grupos, no se encuentra definida
previamente. Al conjunto de nodos que forman un grupo se le conoce como cluster y este
se forma mediante un conjunto de nodos que satisfacen una propiedad especfica. Esto se
ilustra en la Figura 7.

CASTRILLON, Jernimo; GIRALDO, Daniel; PEA Jorge, Aprendizaje por refuerzo en espacios

continuos para la evasin de obstculos en un robot mvil. Medelln, 2004. 300 p. Tesis de Grado (Ingeniero
Electrnico). UPB. Facultad de Ingeniera Elctrica y Electrnica.

18

Figura 7.

Ejemplo de una red agrupada en clusters.

2.2 ALGORITMOS DINMICOS DE CLUSTERING

En una MANET no se puede lograr la disposicin de clusters de forma offline como sucede
en las redes con infraestructura preestablecida. Por lo tanto, se han desarrollado
recientemente algoritmos de clustering dinmicos que tienen en cuenta el carcter dinmico
de un sistema. La dinmica de un sistema depende de los objetos o de los clusters. De
acuerdo a esto, se pueden presentar cuatro escenarios.2

Objetos estticos y una estructura de clusters esttica.

Objetos estticos y una estructura de clusters dinmica.

Objetos dinmicos y una estructura de clusters esttica.

Objetos dinmicos y una estructura de clusters dinmica.

HABETHA, J. y WALKE, B. Fuzzy rule-based mobility and load management for self-organizing wireless

networks. En: International Journal of Wireless Information Networks. Holanda. Vol. 9, No.2. (Abr, 2002); p.
119.

19

Para el anlisis de datos dinmicos se estudian los tres ltimos escenarios. El cuarto
escenario es el que aborda el problema de clustering en redes mviles ad hoc.

2.3
IMPORTANCIA DE LA IMPLEMENTACIN DE PROCESOS DE
CLUSTERING EN MANET

Una MANET se organiza dinmicamente en clusters para mantener una topologa efectiva,
relativamente estable y para mejorar su desempeo.

2.3.1 Funcin de los algoritmos de clustering. Los algoritmos de clustering se encargan

de presentarle al algoritmo de enrutamiento una topologa lgica de la red. El algoritmo de
clustering tambin acepta una realimentacin del algoritmo de enrutamiento con el fin de
ajustar la topologa lgica presentada3. En la figura 8 se puede apreciar esta relacin.

Figura 8.

Relacin entre el algoritmo de clustering y el protocolo de enrutamiento en

MANET

MCDONALD, A.B. y ZNATI, T.F. A mobility-based framework for adaptive clustering in wireless Ad Hoc

networks. En: IEEE Journal on Selected Areas in Communications. New York, USA. Vol. 17. (Ago, 1999); p.
1466.

20

Mtricas utilizadas en los algoritmos de clustering. El establecimiento de clusters en

MANET presenta varias ventajas para la capa de acceso al medio (MAC) y para la capa
de red.
Para el caso de la capa MAC, los procesos de clustering mejoran el desempeo de
algunas mtricas que se describen a continuacin:

- Reuso del espacio (spatial reuse).

Esta mtrica establece el nmero de

conexiones permitidas en una regin dada. Una red organizada mediante clusters
promueve el re-uso del espacio y por lo tanto se mejora la capacidad del sistema.

- Distribucin del ancho de banda. Entre los usuarios disponibles, la distribucin

del ancho de banda debe ser proporcional a las caractersticas de trfico de cada uno
de los usuarios. Efectuar clustering mejora esta propiedad ya que se disminuye el
trfico de la red.

- Throughput. Se refiere a la fraccin de la capacidad del canal empleado en la

transmisin de datos. El establecimiento de clusters mejora el desempeo de esta
mtrica.

- La escalabilidad. Es la habilidad que tiene la capa MAC de mantener un buen

desempeo de la red cuando sus factores limitantes como el trfico o la movilidad se
incrementan debido a un crecimiento en el nmero de usuarios. La necesidad de
almacenar los detalles completos del enrutamiento en una gran topologa de red,
tiene consecuencias en la escalabilidad. La jerarqua plana adoptada por muchos de
los protocolos de enrutamiento en MANET, no es capaz de soportar la funcin de
enrutamiento de manera eficiente. Este hecho se debe a que las tablas de
enrutamiento crecen de forma significativa si cada nodo tiene una vista completa de
la topologa de la red. Una de las razones principales por las cuales se proponen
algoritmos de clustering en redes mviles ad hoc, es para manejar las consecuencias

21

de la escalabilidad. Efectuar clustering permite que una red ad hoc de gran tamao
sea escalable mediante la implementacin de una topologa jerrquica en la red.

Por otro lado, el establecimiento de clusters permite mejorar el desempeo de la capa de

red ya que el enrutamiento se optimiza mediante la reduccin de las tablas de enrutamiento
y la disminucin del nmero de transmisiones necesarias durante el envo de las
actualizaciones, al ocurrir un cambio topolgico en la red.
Al implementar un proceso de clustering en MANET, la distribucin de la informacin
topolgica de la red se simplifica ya que el nmero de nodos de un cluster es menor al
nmero total de nodos presentes en la red. Por lo tanto, cada nodo slo debe almacenar una
fraccin de la informacin total de la red referente al enrutamiento. Aparte de lograr que
una red de gran tamao parezca ms pequea, los procesos de clustering logran que una
topologa altamente dinmica parezca menos dinmica.4 Este hecho minimiza la prdida de
los enlaces y la de los paquetes.

2.3.2 Formacin de clusters en las redes mviles ad hoc.

En la mayora de los

algoritmos de clustering propuestos se establecen tres tipos de nodos:

Clusterheads

Nodos Gateway

Nodos ordinarios

Clusterheads. La funcin principal de un clusterhead es la de calcular las rutas para

mensajes de larga distancia y enviar paquetes entre los clusters. Un paquete proveniente
de un nodo es transmitido en primera instancia a su clusterhead respectivo. Si el
destinatario se encuentra localizado en el mismo cluster, el clusterhead simplemente le
entrega el paquete al nodo destino. Si el destinatario del paquete se encuentra localizado
en un cluster diferente, el clusterhead enva el paquete a travs del backbone formado
por los clusterheads de la red, hasta ser recibido por el clusterhead del nodo destino.
Este clusterhead se encarga de remitir el paquete al destinatario respectivo.

Ibid., p. 1466.

22

El concepto de clusterheads es anlogo al concepto de estaciones base en las redes

celulares actuales. Tanto los clusterheads como las estaciones base actan como
coordinadores locales que facilitan la disponibilidad del canal y realizan un control del
consumo de la potencia. Sin embargo, la diferencia entre un clusterhead y una estacin
base convencional radica principalmente en que los clusterheads no tienen
implementado un hardware especial, son seleccionados entre el conjunto de nodos
presentes en la red y presentan un comportamiento dinmico y mvil. Por esta razn el
proceso de seleccin de los clusterheads debe considerar para dicho papel, aquellos
nodos con alto grado de estabilidad relativa con el fin de evitar la frecuente
reconfiguracin de los clusterheads en la red.
Nodos gateway. Los nodos gateway son aquellos nodos que no son clusterheads y se
encuentran localizados en la periferia de un cluster. Este tipo de nodos se llaman
gateways porque son capaces de escuchar las transmisiones de un nodo que pertenece a
un cluster distinto del suyo. Para que esto ocurra, un nodo gateway debe tener por lo
menos un nodo vecino que sea miembro de otro cluster diferente.
Nodos ordinarios. Los nodos ordinarios son los miembros de un cluster que no son
adyacentes a ningn otro cluster.
En la Figura 9 se puede apreciar los papeles de cada uno de los nodos descritos
anteriormente, en una red ad hoc dividida en clusters.

23

Figura 9.

Estructura de una red ad hoc formada por clusters.

Para establecer un backbone de comunicacin en una red mvil ad hoc, los clusterheads
se conectan directamente entre s o por medio de nodos gateway. El backbone permite
simplificar funciones tales como el acceso al canal, la utilizacin del ancho de banda y
el control sobre el consumo de la potencia. En la figura 10 se aprecia una MANET
dividida en clusters y el backbone de comunicacin formado por los clusterheads.

Figura 10.

Backbone formado en una MANET.

2.3.3 Propiedades deseables en un algoritmo de clustering.

Las siguientes son

propiedades deseables que debe cumplir un algoritmo de clustering:

- El algoritmo debe ejecutarse en tiempo real.

- Un buen algoritmo de clustering debe preservar su estructura el mayor tiempo posible
mientras los nodos se mueven. Por lo tanto, los clusters formados deben presentar una
estabilidad mnima para que la configuracin de la red no cambie drsticamente.

- Se debe evitar que el conjunto de clusterheads seleccionados cambie con mucha

regularidad. El frecuente clculo de los clusterheads y el frecuente intercambio de
informacin entre los nodos de la red hacen que el procesamiento computacional sea
excesivo.

24

- Se debe balancear el nmero de clusterheads de la red. Un nmero pequeo de

clusterheads implica una sobrecarga para estos ya que sus clusters respectivos tendrn un
gran nmero de nodos. Sin embargo, un nmero grande de clusterheads hace que el nmero
de saltos para que un paquete pueda ser transportado desde el origen hasta el destino, sea
muy grande dado que el paquete debe atravesar un gran nmero de clusterheads. Esto
implica una gran latencia en la red, un mayor consumo de batera y un mayor
procesamiento de informacin en cada nodo.

- El tamao de los clusters no debe ser tan grande como para sobrecargar a los clusterheads
ni tan pequeo como para que los clusterheads se mantengan desocupados durante la
mayor parte del tiempo.

- El algoritmo debe ser distribuido, es decir se debe llevar a cabo de una forma no
centralizada.

- A todos los nodos de la red se les debe asignar un cluster.

- El algoritmo debe funcionar sin un set de entrenamiento preestablecido.

- Es deseable que el algoritmo sea adaptativo para que los nodos puedan reaccionar frente a
los cambios topolgicos de la red.

2.4 TEORA DE GRAFOS5

ROSEN,

Kenneth H. Matemtica discreta y sus aplicaciones. 5ed. Madrid: Mcgraw-Hill, 2004. p.

(Laboratorios AT&T, Middletown, Nueva Jersey, USA).

25

La teora de grafos constituye un elemento de estudio en reas como matemticas y

ciencias computacionales. Usualmente las redes mviles ad hoc se representan mediante
grafos. A continuacin se introducirn algunos conceptos fundamentales de la teora de
grafos.
2.4.1

Conceptos preliminares.

Los grafos son estructuras discretas que constan de

vrtices y de aristas las cuales conectan entre s los vrtices. Se representan comnmente
por medio de un conjunto de puntos correspondientes a los vrtices o a los nodos, los cuales
se unen por medio de lneas correspondientes a las aristas o a los enlaces. En la figura 11 se
puede apreciar un grafo con 5 vrtices y 6 aristas. Segn la aplicacin, los grafos pueden
ser dirigidos o no dirigidos.

Figura 11.

Ejemplo de un grafo con 5 vrtices y 6 aristas.

Grafos dirigidos. Un grafo dirigido denotado G = (V, E) consta de un conjunto V de

vrtices y de un conjunto E de aristas que son pares ordenados de elementos de V. E es un

conjunto de enlaces dirigidos que se denotan por medio de flechas. Una red informtica con
lneas telefnicas unidireccionales se puede representar mediante este tipo de grafos.

26

Grafo dirigido.

Figura 12.

Grafos no dirigidos. Un grafo no dirigido se denota por G y consiste en un par

ordenado G= (V,E), donde V corresponde a un conjunto de vrtices o de nodos y E

corresponde a un conjunto de pares no ordenados de elementos distintos de V. A estos
pares se les llama aristas. A los vrtices que pertenecen a un enlace se les llama ends o
endpoints del enlace. Las redes informticas con lneas bidireccionales se pueden
representar mediante los grafos no dirigidos.

Figura 13.

Grafo no dirigido.

Una MANET puede ser representada mediante un grafo no dirigido G = (V,E) donde, V
corresponde al conjunto de nodos mviles inalmbricos y E corresponde al conjunto de
enlaces entre estos nodos asumiendo que todos tienen el mismo rango de transmisin R.
Dos nodos se consideran vecinos si y solo si la distancia geogrfica entre ellos es menor a
R. Los nodos se comunican mediante enlaces bidireccionales.

27

Vecindario. Dos vrtices u y v de un grafo no dirigido G son adyacentes (o vecinos) en

G, si {u,v} es una arista de G, es decir si existe un enlace entre ellos dos. Si e = {u, v} se
dice que la arista e conecta a u y a v. En la figura 11 los vrtices 2 y 3 son adyacentes. El
conjunto de vecinos, denominado vecindario abierto NG(v) para un vrtice v en un grafo G,
comprende todos los vrtices adyacentes a v pero no incluye a v. Por otro lado, un
vecindario cerrado denotado como NG[v], se presenta cuando v es incluido dentro del
conjunto de vecinos.
En las redes ad hoc, el vecindario correspondiente a un nodo v se define como:

N[v] =

v'V , v' v

{v'| dist ( v, v' ) < tx range }

Ec. 1. Definicin de vecindario cerrado

donde txrange corresponde al rango de transmisin del vrtice v.

Distancia y dimetro. En un grafo no dirigido G = (V, E) las distancia entre dos nodos,

u y v, denotada por d (u,v), corresponde al nmero de enlaces que unidos forman el camino
ms corto entre esos dos nodos. El dimetro de un grafo no dirigido G se define como:
diam(G) = max { d(u, v) : u, v V }
Ec. 2. Dimetro en un grafo no dirigido

Por lo tanto el dimetro de un grafo es la mxima distancia entre cualquier par de nodos.
Cuando cada nodo dentro de un cluster se encuentra a un salto de los otros nodos, se dice
que cada cluster es de dimetro 1.

Subgrafos. Hay casos en que slo se requiere parte de un grafo para dar solucin a un

problema en particular. Cuando un grafo representa una red en su totalidad, se pueden

eliminar algunos vrtices salvo los que son de inters particular, y se pueden suprimir todas

28

las aristas que son incidentes con algunos de los vrtices descartados. Al grafo ms
pequeo que se obtiene se le conoce como subgrafo del grafo original. El subgrafo de un
grafo G es un grafo en el cual los conjuntos de vrtices y enlaces pertenecen tambin a G.
La definicin formal de subgrafo se describe a continuacin:

Definicin. Un subgrafo de un grafo G = (V, E) es un grafo H = (W, F) con W V y F E.

Figura 14.

Figura 15.

Grafo G.

Subgrafo de G.

Un subgrafo H de un grafo G corresponde a un grafo inducido si para cada par de vrtices x

y y de H, xy es un enlace de H si y solo si xy es un enlace de G. Por lo tanto, H es un grafo
inducido de G, si contiene casi todos los enlaces que aparecen en G para un mismo
conjunto de vrtices dado.

29

Caminos. Un camino es una secuencia de aristas que comienza en un vrtice del grafo

y recorre ciertas aristas del grafo siempre conectando pares de vrtices adyacentes. Un
camino es simple si no contiene la misma arista ms de una vez.

Definicin: Sea n un entero no negativo y sea G un grafo no dirigido. Un camino de

longitud n del vrtice u al vrtice v en G, es una secuencia de n aristas a1, a2,, an de G
tal que f(a1) = {x0, x1}, f(a2) = {x1,x2}, , f(an) = {xn-1, xn}, donde x0 = u y xn = v.
Para un grafo simple este camino se denota por su secuencia de vrtices x0, x1, , xn.

En la figura 14 a, c, b, d es un camino simple de longitud 3 formado por las aristas

{a,c},{c,b} y {b, d}. El camino d, c, a, b, d, c tiene longitud 4 pero no es simple ya que
contiene dos veces la arista {d, c}.

2.4.2 Conjuntos dominantes. Casi todas las tcnicas de clustering para las redes mviles
ad hoc se basan en el concepto de conjuntos dominantes. Los algoritmos de clustering
distribuidos se disean para encontrar conjuntos dominantes de pequeo tamao.
El objetivo de encontrar conjuntos dominantes es que los miembros de este conjunto sean
los clusterheads. El problema de encontrar un conjunto mnimo dominante se plantea en el
contexto de las redes de comunicaciones, con el fin de encontrar un mnimo nmero de
transmisores que permitan que las dems estaciones estn en el rango de alcance de al
menos uno de los transmisores seleccionados. Sin embargo la labor de encontrar un
conjunto mnimo dominante es un problema de tipo NP-hard, es decir, un problema en el
cual no existe solucin conocida en tiempo polinomial. Dado que en una red ad hoc es muy
complicado obtener el conocimiento completo sobre la topologa de la red, se plantean
diversas heursticas que tratan de encontrar un conjunto mnimo dominante en un nmero
polinomial de pasos.
Un conjunto dominante de un grafo G = (V,E) se define como un subconjunto de vrtices S
V, donde cada vrtice v V se encuentra en S, o es adyacente a un vrtice perteneciente
a S. Se dice que un vrtice perteneciente a S se domina a s mismo y a los vrtices que se
encuentren adyacentes a l. Esta restriccin impuesta al conjunto dominante puede asegurar

30

que los clusterheads se encuentren relativamente cerca uno del otro, posibilitando as el
enrutamiento de paquetes entre los clusters. En la Figura 16 el conjunto de nodos
dominantes corresponde a los puntos negros.

Figura 16.

Conjunto de nodos dominantes.

Fuente: CHEN, Y. P.; LIESTMAN, A. L. y LIU, J. Clustering Algorithms for Ad Hoc

Wireless Networks. [pdf]. CA, USA: Nova Science Publishers, revisado 2004.
<[Link] [Consulta: 5 Ago: 2005].

Un conjunto dominante puede ser a su vez independiente, conexo o dbilmente conexo:

- Conjuntos dominantes independientes. Un conjunto dominante independiente consiste

en una coleccin de vrtices en la cual dos vrtices no pueden ser adyacentes, es decir no
pueden estar conectados por un enlace. Muchas tcnicas de clustering como Lowest-ID
heuristic, Highest-degree heuristic y DMAC, las cuales se describirn posteriormente en el
captulo, establecen conjuntos dominantes independientes en las redes mviles ad hoc. Sin
embargo, la formacin de conjuntos dominantes independientes puede causar un efecto en
las redes conocido como la reaccin en cadena (chain reaction) ante los cambios
topolgicos. Esto sucede cuando al presentarse adyacencia entre dos clusterheads, uno de
los dos clusterheads debe renunciar a su papel ya que la condicin de independencia en los
conjuntos dominantes impone que no deben haber dos clusterheads que sean vecinos. Lo
anterior puede originar que se propaguen a travs de toda la red, otros cambios en la
configuracin de los clusterheads.

31

- Conjuntos dominantes conexos. Un conjunto dominante conexo (CDS: connected

dominating set) se presenta cuando el subgrafo inducido por el conjunto dominante est
conectado. Un conjunto dominante conexo ayuda a mejorar el enrutamiento en una red ad
hoc. Sin embargo la restriccin de conectividad origina un nmero de clusters
relativamente grande. Los conjuntos dominantes conexos se pueden formar por medio de
clusterheads y por medio de nodos gateway.

En la figura 17 se ilustra un conjunto

dominante conexo correspondiente a los puntos negros unidos por las lneas oscuras.

Figura 17.

Conjunto dominante conexo.

Fuente: Ibid.

- Conjuntos dominantes dbilmente conexos. El nmero de clusters en una red se puede

reducir relajando la condicin de conectividad. Para ello se introduce el concepto de
conjunto dominante dbilmente conexo (WCDS: weakly connected dominating set). El
subgrafo dbilmente conexo inducido por un conjunto dominante S corresponde al grafo G
= (V, E) en el cual cada arista en E tiene al menos un punto de terminacin en S. El
conjunto S es un conjunto dominante dbilmente conexo de G si S es dominante y G se
encuentra conectado6.

Varios autores sugieren que el concepto de los conjuntos dominantes dbilmente conexos,
es el ms adecuado para ser aplicado a las redes mviles ad hoc ya que se establecen un
menor nmero de clusters.
6

ALZOUBI, K.M.; PENG-JUN, W. y FRIEDER, O. Weakly-connected dominating sets and sparse spanners

in wireless ad hoc networks. En: International Conference on Distributed Computing Systems (23:2003)
Proceedings. Providence, Rhode Island, USA: IEEE, 2003. p. 96.

32

En la Figura 18 los vrtices 1 y 2 forman el conjunto dominante dbilmente conexo y las

aristas negras conforman el subgrafo inducido dbilmente conexo.

Figura 18.

Conjunto dominante dbilmente conexo y subgrafo inducido dbilmente

conexo.

Fuente: Ibid., p.96.

2.5. DESCRIPCIN DE ALGUNAS TCNICAS DE CLUSTERING

En esta seccin se describe el funcionamiento de ocho tcnicas de clustering planteadas en

diversos trabajos: Lowest-ID7, Highest-degree8, k-CONID9, (, t)10, Max-Min11,
MobDhop12, DMAC13 y WCA14 .
7

CHATTERJEE, M.; DAS, S.K. y TURGUT, D. WCA: A Weighted clustering algorithm for mobile ad hoc

networks. En: Cluster Computing. Tucson, USA. Vol. 5. (2002); p.193.

8

Ibid., p.193.

NOCETTI, F.G.; GONZALEZ, J.S. y STOJMENOVIC, I. Connectivity Based k-hop clustering in

wireless networks. En: Telecommunication Systems. Holanda. Vol. 22, N.o 1-4. (2003); p. 205.
10

11

MCDONALD y ZNATI, Op. Cit, p. 1466.

AMIS, A.D.; PRAKASH, R. ; VUONG, T.H.P. y HUYNH, D.T. Max-Min D-Cluster Formation in

Wireless Ad Hoc Networks. En: Conference on Computer Communications (INFOCOM). Proceedings. TelAviv, Israel: IEEE, 2000. Vol 1. p.32.

33

2.5.1. Lowest-ID y Highest-degree, Los algoritmos conocidos como Lowest-ID y Highestdegree son dos de los primeros algoritmos ms populares que se disearon para la
formacin de clusters en redes ad hoc. Muchos de los trabajos sobre clustering que se
plantean actualmente toman estos dos algoritmos como referencia para evaluar el
desempeo de los algoritmos diseados. Tanto Lowest-ID como Highest-degree se basan en
los conjuntos dominantes independientes. Ambos algoritmos utilizan pesos y se dice que
son localizados ya que cada nodo solo necesita conocer la informacin de los vecinos que
se encuentran a una distancia de un salto. A continuacin se describe el funcionamiento de
cada uno:

Lowest-ID. A cada nodo perteneciente a la red se le asigna un identificador denotado

como ID. Cada nodo realiza un broadcast de su ID a sus vecinos directos y luego compara
su propio ID con el de sus vecinos. Un nodo decide convertirse en clusterhead si tiene el
menor ID entre los IDs de sus vecinos. Un nodo que se puede comunicar con dos o ms
clusterheads se convierte en un nodo gateway. De lo contrario el nodo simplemente es un
nodo ordinario. En la figura 19 se ilustra una red a la que se le aplica el algoritmo de
Lowest-ID. Se puede observar que no hay clusterheads (cuadrados negros) directamente
conectados ya que el algoritmo establece un conjunto dominante independiente. Los nodos
ordinarios corresponden a los crculos blancos y los nodos gateway a los crculos negros.

12

SEAH, W.K.G. Mobility-based d-hop clustering algorithm for mobile ad hoc networks. En: Wireless

Communications and Networking Conference. Atlanta, Georgia, USA: IEEE, 2004. Vol. 4, No 21-25. p.
2359.
13

BASAGNI, S. Distributed clustering for ad hoc networks. En: Int. Symp. On Parallel Architectures,

Algorithms, and Networks. Proceedings. Fremantle, Australia : 1999. p. 310.

14

CHATTERJEE, DAS y TURGUT, Op. Cit., p. 193.

34

Figura 19.

Ejemplo de formacin de clusters mediante Lowest-ID.

Fuente: GERLA, M. y TSAI, J. Multicluster, mobile, multimedia radio network. En:

Wireless networks. Hingham, MA, USA. Vol 1. (Mar, 1995); p. 255.

Highest-degree. Este algoritmo tambin es conocido como Highest-connectivity. Se

basa precisamente en la conectividad que tiene un nodo con sus vecinos directos. Cada
nodo hace un broadcast peridico del estado de su conectividad a todos sus vecinos. Un
nodo decide convertirse en clusterhead o en nodo ordinario, comparando el grado de
conectividad de sus vecinos con el suyo. Si un nodo tiene el valor ms grande de
conectividad en un vecindario es elegido como clusterhead.

Lowest-ID y Highest-degree presentan algunas desventajas que tienen que ver con la
configuracin de clusters inestables. En el caso de Lowest-ID, un nodo que sea altamente
mvil y tenga el menor ID entre sus vecinos puede ser elegido como clusterhead. Esto
puede ocasionar una frecuente reconfiguracin de la red y cambios de clusterheads no
deseables, lo cual produce un excesivo intercambio de informacin entre los nodos. Esto se
puede minimizar seleccionando un clusterhead que se mantenga en un mismo cluster por
un largo tiempo.

35

2.5.2 k-hop CONID. La tcnica de clustering k-CONID (k-hop connectivity ID) combina
dos algoritmos de clustering, Lowest-ID y Highest-degree, en uno solo. Para realizar la
seleccin de los clusterheads se considera como primer criterio la conectividad y como
segundo criterio el ID de valor ms pequeo. Cuando se utiliza solamente la conectividad
de los nodos como criterio de seleccin de clusterheads, se originan muchos empates entre
los nodos. Por otro lado usar solamente el criterio del ID de valor ms pequeo genera ms
clusters de los requeridos. El propsito de k-CONID es el de minimizar el nmero de
clusters formados en la red y de esta manera obtener conjuntos dominantes de menor
tamao. En el algoritmo de k-CONID los clusters se forman mediante la seleccin de un
clusterhead y todos los nodos que se encuentren a una distancia de k-saltos de este. Por lo
tanto, los vecinos de un nodo se pueden localizar a una distancia de al menos k-saltos.

A cada nodo en la red se le asigna un par conocido como prioridad del clusterhead y
denotado como did = (d, ID). El valor de d equivale a la conectividad d de un nodo y el
valor ID es el identificador del nodo. Un nodo es elegido como clusterhead si posee el
valor ms grande de conectividad. En caso de igual conectividad, la prioridad que tiene un
nodo para convertirse en clusterhead depende de si tiene el ID ms pequeo. Un nodo
realiza un broadcast de su decisin tomada respecto a su estado cuando todos sus vecinos
de k-saltos que tengan prioridades de clusterhead de valor ms grande, lo hayan hecho.

El algoritmo funciona de la siguiente manera:

Inicialmente, los nodos con los valores de prioridad de clusterhead ms grandes

entre sus vecinos de k-saltos, deciden crear clusters en los cuales sern clusterheads.
Estos nodos realizan un broadcast de su decisin a sus vecinos de k-saltos.

Un nodo puede decidir formar parte de un cluster en el cual el clusterhead es su

vecino de k-saltos con el valor ms grande de did, y realiza un broadcast
manifestando su decisin. Sin embargo, tambin puede ocurrir que todos los
vecinos de un nodo con el valor de did ms grande ya hayan realizado un broadcast

36

manifestando su decisin y ninguno se haya declarado clusterhead. En este caso el

nodo decide crear su propio cluster y su did se convierte en el ID de su cluster.

A pesar de que cada nodo solo determina su pertenencia a un solo cluster, los
clusters se pueden superponer. Esto significa que un nodo puede llegar a pertenecer
a todos los clusters en los cuales su clusterhead se encuentre a k-saltos de distancia
del nodo. Los nodos que pertenecen a ms de un solo cluster se convierten en nodos
gateway.

2.5.3 (, t) cluster framework. El algoritmo de clustering (, t) utiliza un modelo de

probabilidad para determinar la disponibilidad de los caminos entre los nodos de una red ad
hoc. (, t) es un algoritmo distribuido asincrnico en el cual los nodos se organizan en
clusters de una forma dinmica. Los autores de (, t) pretenden dar con esta tcnica de
clustering, soporte a un esquema de enrutamiento hbrido y adaptativo el cual pueda
desempearse de una manera ms ptima cuando las ratas de movilidad sean bajas y de una
manera ms eficiente cuando las ratas de movilidad sean altas. El propsito de formar
clusters de acuerdo a la movilidad de los nodos, es el de balancear de manera adaptativa el
enrutamiento proactivo y reactivo.

En el algoritmo de (, t) los caminos se evalan mediante dos parmetros del sistema, y t.

establece un lmite inferior a la probabilidad de que en un cluster dado, un camino se
mantendr disponible por un tiempo t. La funcin de es la de controlar la estabilidad del
cluster mientras que la funcin de t es la de controlar el tamao de un cluster, dado un
cierto nivel de estabilidad.

Esta tcnica de clustering establece un criterio denominado criterio (, t), para formar
clusters de nodos en un red ad hoc. El criterio (, t) se satisface si existe por lo menos una
probabilidad durante un periodo de tiempo t de que los caminos internos de un cluster se
encuentren disponibles para que los nodos de un mismo cluster sean mutuamente
alcanzables. Debido a que la disponibilidad de los caminos es un proceso aleatorio, la

37

movilidad de los nodos que se encuentren en un cierto camino determina el grado de

disponibilidad que este camino pueda presentar. Por lo tanto el algoritmo de clustering (,
t) predice la movilidad de un nodo con el fin de organizar la red en clusters. El algoritmo
est diseado para tomar acciones apropiadas ante cambios topolgicos ya que un cambio
topolgico requiere que los nodos reevalen el criterio (, t).

Las acciones tomadas por el algoritmo de clustering (, t) dependen de la informacin

brindada por los protocolos de la capa de red y de la capa de interfaz de red. A cada nodo
de la red se le asigna un nmero identificador del cluster CID (cluster identifier number).
Cada nodo hace uso a su vez de un timer conocido como timer el cual determina el
mximo tiempo t para el cual un nodo puede garantizar la disponibilidad de un camino a
cada cluster destino con una probabilidad mayor o igual a .

La documentacin que se presenta sobre (, t) expone el pseudo cdigo para cinco eventos
que pueden producir cambios topolgicos en las MANET organizadas mediante clusters.
Estos eventos se describen a continuacin:
-

Activacin de un nodo: Cuando un nodo de la red se activa, inicializa su CID a un

valor predefinido para indicar que no se encuentra unido a un cluster. El propsito de un

nodo activado es el de descubrir nodos adyacentes y unirse a su cluster. Para ello el nodo
activado identifica primero los CIDs de sus vecinos y luego evala la disponibilidad del
enlace asociada con cada vecino de acuerdo a la informacin obtenida sobre la movilidad.
Los vecinos le transmiten al nodo activado la informacin topolgica completa sobre el
cluster y este determina si todos los nodos en ese cluster presentan disponibilidad (, t). El
nodo se une al cluster si este cumple con el criterio (, t). Un nodo activado establece su
membresa a un cluster, igualando el valor de su CID al valor del CID del cluster al cual se
va a unir. De esta forma el protocolo de enrutamiento adiciona automticamente el nodo
activado a las tablas de enrutamiento de los otros miembros del cluster para convertirlo en
un nuevo destino.

38

Un nodo activado que sea incapaz de unirse a un cluster, forma su propio cluster y su
timer se ajusta al valor del parmetro t del sistema con el fin de tratar nuevamente de unirse
a un cluster.

Activacin de un enlace: Cuando un nodo se encuentra dentro de un cluster y

detecta la activacin de un enlace, la topologa del cluster simplemente se actualiza. Por

otro lado, cuando un nodo que an no se ha unido a un cluster detecta la activacin de un
enlace, este intenta unirse a un cluster de nuevo. Para ello, el nodo reset su CID ponindolo
en un estado que indica que no se encuentra unido a un cluster.

Falla de un enlace: Si un nodo detecta la falla de un enlace debe determinar si ha

perdido caminos (, t) con respecto a los destinos en el cluster. Si un destino se ha vuelto

inaccesible, el nodo lo elimina de su tabla de enrutamiento y no lo sigue teniendo en cuenta
para el clculo de los caminos (, t). Por otro lado, un nodo abandona voluntariamente su
cluster cuando detecta que los nodos de ste permanecen conectados pero no se encuentran
disponibles para l segn el criterio (, t).

Expiracin del timer: Cuando se expira el timer las acciones que toma un nodo

son las mismas que cuando detecta la falla de un enlace o la desactivacin de un nodo. La
nica diferencia es que la expiracin del timer permite que un nodo que an no pertenece
a un cluster, intente de nuevo unirse a uno.

Desactivacin de un nodo: Este evento puede ser causado por la desactivacin

voluntaria de un nodo, una falla imprevista, la desconexin de un cluster o el abandono

voluntario de un nodo de su cluster. En general, un nodo desactivado no se encuentra
disponible para los nodos restantes de un cluster.

La tcnica de clustering (, t) caracteriza la probabilidad de disponibilidad de un enlace o

de un camino en funcin del modelo de movilidad conocido como random walk. Un enlace
se considera como un enlace activo entre dos nodos mviles en un tiempo t1+t0 (t1>t0) si en

39

el tiempo t0 existe un enlace activo entre ellos. De acuerdo a Sivavakeesar15, la tcnica de

clustering (, t) posee una ambigedad en cuanto a que tan grande debe ser t1 y adems no
considera los eventos que puedan suceder en el intervalo t1+t0. Si este intervalo dura poco,
los clusters formados no resultan ser tan efectivos. Si este intervalo es muy grande, el
algoritmo toma mucho tiempo para converger.

2.5.4 Max-min.

En muchos trabajos realizados sobre clustering, la seleccin del

clusterhead se hace de forma que ningn nodo pueda estar a ms de un salto de su propio
clusterhead. La gran desventaja sugerida por Amis16 de que los nodos se encuentren a un
salto de su clusterhead, es que esto genera un gran nmero de clusterheads en la red
causando un problema de congestin. Por lo tanto, en la heurstica planteada como MaxMin los clusters se construyen de forma que los nodos se puedan encontrar a d saltos de su
propio clusterhead. El objetivo principal de Max-Min es que se seleccionen mltiples
lderes en una red ad hoc que contenga cientos de nodos y que con los clusterheads
seleccionados se forme un conjunto dominante mnimo de d saltos.

En esta heurstica, d se define como el mximo nmero de saltos al cual se puede encontrar
un nodo lejos del clusterhead ms cercano (d 1). D es un valor que se le asigna a la
heurstica permitiendo de esta forma el control sobre el nmero de clusterheads a ser
elegidos. Los nodos participan en el algoritmo de seleccin del clusterhead en base a su ID.

La heurstica de Max-Min se ejecuta por un nmero de 2d rondas en las cuales se

intercambia la informacin entre los nodos de la red. Durante su ejecucin se llevan a cabo
cuatro etapas:

1. Intercambio de los ids ms grandes.

2. Intercambio de los ids ms pequeos.
15

SIVAVAKEESAR, S. y PAVLOU, G. A Prediction-Based Clustering Algorithm to achieve Quality of

Service in Multihop Ad Hoc Networks. En: Proc. of the London Communications Symposium (LCS).
Londres, UK. (Sep, 2002); p. 157.
16

AMIS, PRAKASH, VUONG y HUYNH. Op. Cit., p.32.

40

3. Seleccin de los clusterheads.

4. Conexin de los clusters formados.

Cada nodo posee dos arreglos denominados WINNER y SENDER. El primer arreglo
corresponde al ID del nodo ganador para una ronda en particular. El segundo arreglo hace
referencia al nodo que envi el id ganador para esa ronda particular. Una vez se selecciona
el clusterhead, SENDER ayuda a determinar el camino de regreso ms corto desde un nodo
hacia el clusterhead.

Al comienzo del algoritmo cada nodo tiene un valor de WINNER igual a su propio ID. El
algoritmo inicia 2d rondas de flooding. De esta forma se lleva a cabo el intercambio de ids
entre los nodos. En las primeras d rondas se realiza un procedimiento denominado
Floodmax y en las segundas d rondas se realiza un procedimiento denominado Floodmin.
Cada uno de los nodos de la red almacena el valor de WINNER para cada ronda de
flooding. Durante el procedimiento de Floodmax cada nodo realiza un broadcast de su
valor de WINNER a todos los vecinos que se encuentren a un salto. Por cada ronda d de
Floodmax un nodo determina el nuevo valor para su arreglo WINNER como el valor ms
grande entre los WINNER recibidos y su propio valor de WINNER. El procedimiento de
Floodmin procede a Floodmax y comienza con los valores que existen en cada nodo
despus de las primeras d rondas de Floodmax. Para este caso, en cada ronda d un nodo
selecciona como su nuevo valor de WINNER al valor ms pequeo entre los valores
recibidos de WINNER y su propio valor. Floodmin permite que los nodos con ids ms
pequeos se tomen en cuenta.

El criterio de seleccin del clusterhead se basa en las entradas almacenadas en cada nodo
despus de las 2d rondas de flooding. Este criterio sigue tres reglas:

1. Un nodo se puede declarar a s mismo como clusterhead si despus de las 2d rondas

de flooding a recibido su id original. Si esta regla no se cumple se sigue la segunda
regla.
2. Cada nodo debe buscar lo que se denomina node pairs. Un node pair se define

41

como el valor del id que haya resultado como WINNER al menos una vez en las
primeras d rondas de Floodmax y tambin en las segundas d rondas de Floodmin.
Una vez un nodo detecta todos los node pairs, escoge el node pair de mnimo valor
como clusterhead. Por lo tanto, el nodo con el id de mnimo valor que aparezca en
las dos etapas de flooding, es escogido como clusterhead. Si un nodo no identifica
ningn node pair se sigue la tercera regla.
3. En este caso un nodo selecciona el nodo con el mximo valor de id de las primeras
d rondas de flooding como su clusterhead.

Los nodos gateway son seleccionados porque tienen la tarea de comunicar a sus
clusterheads cuales nodos son miembros de su cluster. Para esto, cada nodo realiza un
broadcast informando a sus vecinos el clusterhead que ha seleccionado. Un nodo
determina si es un nodo gateway, si tiene nodos vecinos con diferente seleccin de
clusterhead. Despus de que un nodo ha identificado que es un nodo gateway, le enva a su
clusterhead informacin sobre el valor de su id y sobre quienes son todos sus nodos
gateway vecinos y los clusterhead asociados a estos nodos. El arreglo SENDER es usado
para decidir quien es el prximo al que se le enva el contenido de esta informacin. De esta
manera un clusterhead puede crear una base de datos sobre cada uno de los nodos de su
cluster. Esta heurstica maximiza el nmero de nodos gateway con el fin de crear un
backbone formado por mltiples caminos entre clusterheads vecinos. De esta forma se
puede facilitar el trfico de la red.
Seah17 argumenta que a pesar de que Max-Min permite control y flexibilidad en la
determinacin de la densidad de los clusterheads, esta implementacin no tiene en cuenta el
patrn de movilidad de los nodos. Tener en cuenta los patrones de movilidad de los nodos
puede mejorar la estabilidad de los clusters formados. Por otro lado, una gran desventaja

17

SEAH, Op. Cit., p. 2359.

42

de Max-Min es que es ineficiente porque involucra procesos de flooding para la seleccin

de los clusterheads18.

En la figura 20 se muestra una red ad hoc en donde los nodos se agrupan de acuerdo al
algoritmo de clustering Max-Min.

Figura 20.

Formacin de clusters en una red de 25 nodos con d = 3.

Fuente: AMIS, PRAKASH, VUONG y HUYNH. Op. Cit., p.32.

2.5.5 MobDhop. Los autores proponen un algoritmo de clustering que divide la red ad hoc
en clusters de d saltos en base a una mtrica de movilidad. El algoritmo de clustering
distribuido es llamado MobDhop. El propsito de este esquema es formar clusters estables
con el fin de establecer en la red una arquitectura para el enrutamiento.
El objetivo de formar clusters de d saltos es el de hacer que el dimetro de los clusters sea
ms flexible. MobDhop se basa en la mtrica de movilidad presentada por Basu19 y el
dimetro de los clusters se adapta de acuerdo a la movilidad de los nodos. Al igual que
18

BAO, L. y GARCIA-LUNA-ACEVES, J.J. Topology management in ad hoc networks. En: International

symposium on mobile ad hoc networking & computing. (4 : 2003) Proceedings. Annapolis, MD, USA: ACM,
2003. Vol.9. p.129.
19

BASU, P.; KHAN, N. y LITTLE, T.D.C. A mobility based metric for clustering in mobile ad hoc networks.

En: International Conference on Distributed Computing Systems. (21:2001) Proceedings. Phoenix,

Arizona, USA: IEEE Computer Society, 2001. p. 413.

43

Max-Min, MobDhop se basa en el mtodo de d-clustering, en el cual los nodos

pertenecientes a un cluster se pueden encontrar a d saltos del clusterhead.

MobDHop busca que el intercambio de informacin sea mnimo durante la formacin de

clusters y durante los cambios de clusterheads. Este algoritmo de clustering asume que
cada nodo puede medir la potencia de las seales que recibe. De esta forma, un nodo puede
determinar la cercana con sus nodos vecinos. En el algoritmo, dos nodos se consideran
cercanos, si las seales recibidas por ellos tienen un valor grande de potencia.

El algoritmo de MobDhop requiere del clculo de cinco trminos: la distancia estimada

entre nodos, la movilidad relativa entre nodos, la variacin de la distancia estimada a travs
del tiempo, la estabilidad local, y la distancia media estimada. Estos trminos se describen
a continuacin:

La distancia estimada entre el nodo A y el nodo B est dada por:

E[DAB] =

k
PR

Ec. 3. distancia estimada entre 2 nodos

donde k es una constante y PR es la potencia de la seal.

La movilidad relativa se determina midiendo la potencia de la seal de paquetes

sucesivos. Esta medida corresponde a la diferencia entre la distancia estimada de un
nodo con respecto a otro en dos instantes de tiempo sucesivos. Este parmetro
indica si dos nodos se alejan el uno del otro o si se aproximan entre s.

La distancia fsica entre dos nodos no es una medida precisa de la cercana entre
ellos. Si a un nodo se le gasta la batera, transmite paquetes a una potencia baja y
por lo tanto se considera como un nodo distanciado de un vecino que se puede
encontrar fsicamente cerca de l. Por lo tanto, en vez de calcular la distancia fsica
entre dos nodos se calcula la variacin de las distancias estimadas entre ellos. Esta

44

mtrica presenta una medida de la fluctuacin de la potencia de la seal recibida. La

potencia de la seal recibida se puede medir mediante mensajes peridicos de Hello
los cuales son proporcionados por el algoritmo de enrutamiento.

La estabilidad local representa el grado de estabilidad de un nodo respecto a sus

vecinos. Cuando un nodo ingresa en la red puede convertirse en clusterhead, en
nodo ordinario o en nodo gateway. La estabilidad local se calcula con el fin de
seleccionar algunos nodos como clusterhead. Un nodo puede volverse clusterhead
si es el nodo ms estable de su vecindario. Por lo tanto el clusterhead ser el nodo
con el menor valor de estabilidad local entre sus vecinos.

La distancia media estimada indica la distancia media de cada vecino al clusterhead

seleccionado en el cluster.

MobDhop se ejecuta en tres etapas:

Etapa de descubrimiento: Inicialmente MobDhop forma clusters de dos saltos que

no se sobreponen entre s. Al comienzo cada nodo realiza un broadcast de mensajes de

Hello en el que se incluye el valor de la estabilidad local de cada nodo, el cual es

inicializado como infinito al principio del proceso. Cada nodo calcula la distancia
estimada a sus vecinos midiendo la potencia de la seal de los mensajes de Hello
recibidos. Luego de recibir por lo menos dos mensajes de Hello, un nodo calcula su
movilidad relativa respecto a sus vecinos. Tras un periodo de descubrimiento en el cual
los nodos adquieren un conocimiento completo de sus vecindarios, cada nodo calcula el
valor de su estabilidad local y lo transmite mediante un broadcast. Esto se realiza con el
fin de que cada nodo compare su valor de estabilidad local con la de sus vecinos. El
nodo que tenga el menor valor de estabilidad local entre sus vecinos es elegido como
clusterhead. El valor de estabilidad local del clusterhead se convierte en el valor de la

estabilidad grupal. Luego el clusterhead realiza el clculo de la distancia media

estimada respecto a sus vecinos de un salto.

45

- Etapa de fusin: Los clusters de dos saltos establecidos en la etapa de descubrimiento

son expandidos mediante un proceso de fusin. El proceso de fusin puede ser iniciado
por un nodo que an no es miembro de algn cluster, el cual hace una peticin para
poder unirse a sus clusters vecinos. Este proceso tambin se puede llevar a cabo cuando
dos nodos gateway que son vecinos hacen la peticin de fusionar sus clusters
respectivos.

Etapa de mantenimiento: La etapa de mantenimiento de los clusters se lleva a cabo

cuando ocurre un cambio topolgico en la red. Un cambio topolgico puede ocurrir

cuando un nodo ingresa en la red. Este nodo comienza un proceso de fusin calculando
la movilidad relativa estimada y la variacin de la distancia a travs del tiempo con
cada vecino. El nodo selecciona el vecino con el menor valor de variacin de distancia a
travs del tiempo, para unirse a su cluster. Otro caso que genera un cambio topolgico,
es cuando un clusterhead abandona la red. En este caso, sus nodos vecinos ms
inmediatos comienzan el proceso de descubrimiento para que un nuevo clusterhead
pueda ser seleccionado. Sin embargo, los miembros de un cluster que se encuentren por
lo menos a dos saltos de su viejo clusterhead pueden decidir unirse a un cluster vecino
si logran fusionarse a l.

2.5.6 DMAC. El autor de este algoritmo de clustering, Stefano Basagni, presenta dos

tcnicas de formacin de clusters: el primero consiste en un algoritmo de clustering

distribuido DCA (distributed clustering algorithm) y el segundo se trata de un algoritmo de
clustering distribuido que se adapta a la movilidad DMAC (distributed mobility-adaptive
clustering). El algoritmo DCA es ms apropiado para redes ad hoc que presentan baja

movilidad, es decir redes que son casi-estticas. DMAC en cambio, es un algoritmo ms

conveniente para lidiar con redes que presentan un alto grado de movilidad.
DMAC es un algoritmo distribuido que agrupa a los nodos de una red mvil ad hoc en
clusters conformados por un clusterhead y unos nodos ordinarios. Los clusterheads se

seleccionan de acuerdo a un criterio basado en pesos que depende de parmetros de

movilidad relacionados con cada nodo.

46

DMAC busca contrarrestar una desventaja que presentan muchos algoritmos de clustering.

Muchas tcnicas de clustering asumen comnmente que durante el tiempo de inicio del
algoritmo los nodos no se mueven mientras se lleva a cabo el proceso de formacin de
clusters. La mayora de los algoritmos de clustering eliminan la suposicin sobre la

inmovilidad de los nodos, slo despus de que la red se haya dividido en clusters. Luego,
tratan de preservar la topologa del cluster teniendo en cuenta la movilidad de los nodos. En
aplicaciones reales de las redes ad hoc, esta suposicin no se puede realizar ya que no se
puede pronosticar el comportamiento de los nodos ante su propia movilidad. Por lo tanto
una caracterstica importante de DMAC es que tiene en cuenta el movimiento de los nodos
inclusive durante el tiempo inicial del proceso de clustering. DMAC presenta adems
adaptabilidad respecto a los cambios topolgicos de la red. Estos cambios pueden deberse a
la movilidad de los nodos, o a la aparicin o desaparicin de un nodo en la red.

Durante la ejecucin del algoritmo se asume que cada nodo tiene un peso (un nmero real
0) y un ID (identificador nico de cada nodo) asociado. El peso de cada nodo representa los
parmetros de movilidad. Un nodo determina su propio papel en la red, ya sea para
convertirse en clusterhead o para ser un nodo ordinario. Para ello, el nodo se basa en el
conocimiento de los vecinos que se encuentren a un salto de s mismo. Un nodo puede
convertirse en clusterhead si tiene el peso de mayor valor entre sus vecinos. Si este no es el
caso, el nodo se une a un clusterhead vecino.

El autor de DMAC define tres propiedades importantes que debe cumplir un algoritmo de
clustering:

1. Cada uno de los nodos ordinarios debe tener por lo menos un clusterhead como
vecino.
2. Cada nodo ordinario debe afiliarse con el clusterhead vecino de mayor peso.
3. Dos clusterheads no pueden ser vecinos.

47

Todos los nodos que ejecutan el algoritmo de DMAC tienen conocimiento de su propio ID
y el valor de su propio peso as como el ID se sus vecinos y el valor del peso de sus
vecinos. A excepcin de la fase inicial del algoritmo, DMAC es un algoritmo basado en el
envo de mensajes. Dos tipos de mensajes son empleados: Cuando un nodo quiere unirse a
un cluster enva un mensaje denominado JOIN y si decide convertirse en clusterhead enva
un mensaje denominado CH. Un nodo decide su propio papel en la red una vez sus vecinos
de mayor peso lo han decidido.

Durante la ejecucin de DMAC se llevan a cabo cinco procedimientos en cada nodo, los
cuales son:
1. Rutina de inicializacin para el proceso de formacin de clusters.
2. Procedimiento por falla de un enlace.
3. Procedimiento para el establecimiento de un nuevo enlace.
4. Procedimiento tras la recepcin de un mensaje CH.
5. Procedimiento tras la recepcin de un mensaje JOIN.

Todos los nodos empiezan la ejecucin del algoritmo mediante la rutina de inicio. Los
nodos con el mayor peso entre sus vecinos envan un mensaje CH. Los nodos restantes
simplemente esperan a recibir un mensaje. Luego, un nodo realiza uno de dos posibles
procedimientos dependiendo del mensaje que reciba, un mensaje tipo CH o uno tipo JOIN.
Al recibir un mensaje CH, un nodo chequea si se afilia o no al clusterhead que le envi este
mensaje. Por otro lado, cuando un clusterhead recibe un mensaje JOIN verifica si el nodo
que le manda este mensaje se va a unir a su cluster o a otro diferente. Si un nodo ordinario
recibe un mensaje JOIN de su propio clusterhead, significa que ese clusterhead ha
renunciado a su papel.

La adaptabilidad de este algoritmo se hace posible ya que se permite que cada nodo
reaccione ante la falla de un enlace o ante la presencia de un nuevo enlace con otro nodo. Si
falla un enlace entre un clusterhead y uno de sus miembros del cluster, la membresa del
nodo en el cluster se remueve y este nodo debe determinar un nuevo papel. Cuando un
nodo detecta la presencia de un nuevo vecino, se realiza el procedimiento para establecer

48

un nuevo enlace entre estos dos nodos. En este caso, el nodo que detecta el nuevo enlace
determina si el nuevo vecino es clusterhead y si tiene un peso mayor al de su propio
clusterhead. Si esto sucede, el nodo se une al nuevo vecino. Si el nodo que detecta el nuevo

enlace es un clusterhead, este deber renunciar a su papel si el nuevo clusterhead tiene un

peso mayor al suyo.

Figura 21.

Formacin de clusters en una red ad hoc empleando DMAC.

Fuente: PREHOFER, C. y BETTSTETTER, C. Self organization in communication networks: Principles

and design paradigms. En: IEEE Communications Magazine. Dallas, Texas, USA. Vol 43. Issue 7. (Jul,
2005); p. 78.

En la figura 21 los crculos corresponden a nodos ordinarios y los cuadrados son los
clusterheads. Los nodos del mismo color pertenecen a un mismo cluster.

49

De acuerdo a Bettstetter20 en comparacin con otros algoritmos de clustering, DMAC

presenta menor complejidad. El algoritmo puede reaccionar de forma rpida ante los
cambios topolgicos porque cada nodo solo necesita tener conocimiento sobre los vecinos
que se encuentran a un salto de s mismo.

2.5.7 WCA.

WCA (Weighted Clustering Algorithm) es un algoritmo de clustering

distribuido basado en valores de pesos. Este algoritmo selecciona los clusterheads

considerando aspectos relacionados con la eficiencia de las componentes funcionales del
sistema. Por lo tanto, con el fin de optimizar el consumo de la batera, el balanceo de la
carga y las funciones de la capa MAC, un nodo es escogido como clusterhead de acuerdo a
los siguientes aspectos:

1. El nmero de nodos que un solo clusterhead puede manejar (balanceo de carga).

2. La movilidad.
3. La potencia de la transmisin.
4. El consumo de la batera.

WCA es un algoritmo no peridico y se ejecuta el menor nmero de veces posibles con el

fin de evitar congestin en la comunicacin. Por esta razn, el proceso de seleccin de los
clusterheads slo se realiza cuando ocurre un cambio topolgico debido a la movilidad de

los nodos y cuando el conjunto dominante establecido es incapaz de cubrir todos los nodos
de la red. Para asegurar que los clusterheads no se sobrecarguen, se establece un lmite
predefinido el cual especifica el nmero de nodos que cada clusterhead puede manejar
idealmente. Este parmetro corresponde a .
En WCA se eligen los clusterheads de acuerdo al valor del peso asociado a cada nodo. El
peso asociado a un nodo v est definido por:

20

BETTSTETTER, C. The Cluster Density of a Distributed Clustering Algorithm in Ad Hoc Networks. En:

International Conference on Communications. Proceedings. Paris, France: IEEE, 2004.

50

Wv = w1v + w2Dv + w3Mv + w4Pv

Ec. 4. Frmula para calcular Wv

El nodo con el mnimo peso es elegido como clusterhead. Los factores de peso se
seleccionan de forma que w1 + w2 + w3 + w4 = 1. Adicionalmente, dos clusterheads no
pueden ser vecinos inmediatos.
Los parmetros del peso asociado a cada nodo se explican a continuacin:

Mv: Es la medida de la movilidad. Se calcula de acuerdo a la siguiente frmula:

Mv =

1 T
2
2
(X t X t 1 ) + (Yt Yt 1 )
T t =1
Ec. 5. Frmula para calcular Mv

De donde (Xt, Yt) y (Xt-1, Yt-1) corresponden a las coordenadas del nodo v en el
tiempo t y (t-1) respectivamente. Lo que se calcula es la suma de las velocidades
promedio para cada nodo despus de un tiempo T. Es deseable que un clusterhead
presente poca movilidad.

v: Se define como el grado de diferencia de un nodo. Para encontrar este valor se

calcula primero el grado de un nodo. Para un nodo v el grado corresponde a dv. Este
parmetro se calcula como la suma de los vecinos de v, los cuales deben cumplir
con la condicin de estar dentro de su rango de transmisin. La frmula matemtica
para el clculo de dv es:

dv =| N(v)| =

v 'V , v ' V

{dist ( v, v' ) < tx range }

Ec. 6. Frmula para calcular el grado dv

51

donde N(v) es el vecindario del nodo v. v se calcula con el objetivo de asegurar el

balanceo de la carga. Para un nodo v, v est dado por:
v = |dv |
Ec. 7. Frmula para calcular el grado v

Este parmetro permite que el desempeo de las tareas asociadas a la capa MAC
sea ms eficiente ya que es deseable que un clusterhead maneje una cantidad
razonable de nodos en su cluster.

Dv: Se define como la suma de las distancias desde un nodo dado hasta todos sus

vecinos. Se calcula como:

Dv =

{dist ( v, v' )}

v 'N ( v )

Ec. 8. Frmula para calcular Dv

Dv se encuentra relacionado con el consumo de la energa. Este factor es importante
ya que se puede lograr el establecimiento de una mejor conexin entre el

clusterhead y sus vecinos cuando las distancias son ms cortas entre s. Esto se debe
principalmente a que a mayores distancias, la seal de comunicacin se va
atenuando. Por lo tanto, las comunicaciones de larga distancia requieren ms
energa.

Pv: Corresponde al tiempo acumulado que lleva un nodo siendo clusterhead. Este
parmetro es una medida de la batera que ha sido consumida. Un clusterhead
consume ms batera que un nodo ordinario ya que tiene responsabilidades extras.

El algoritmo de seleccin del clusterhead se termina una vez todos los nodos decidan su
papel, ya sea como clusterheads o como miembros de un clusterhead. Cuando un nodo

52

queda elegido como clusterhead no se le permite a l ni a sus vecinos participar ms en el

algoritmo de seleccin.

53

3 AMBIENTE DE SIMULACIN

En este capitulo se presenta una descripcin de unas caractersticas preliminares para el

desarrollo del ambiente de simulacin. Primero se presentan los conceptos bsicos de
modelos de movilidad y se profundiza en los ms relevantes para el trabajo realizado. Se
explican tambin las seales de beaconing y su funcin. Por ultimo se aclara el concepto de
algoritmos centralizados y distribuidos.

3.1 MODELOS DE MOVILIDAD

En todas las investigaciones hechas acerca de las redes ad hoc se busca incrementar la
eficiencia de la red pero con el mnimo overhead posible.
Se puede pensar que con una adecuada topologa de la red el proceso de enrutamiento de
los paquetes puede mejorar categricamente, ya que por muy bueno que sea determinado
protocolo de enrutamiento si la topologa de dicha red es muy poco eficiente se creara un
cuello de botella.
Para que los nodos tengan una topologa que le permita mayor eficiencia estos deben tener
cierta informacin acerca de sus vecinos, es decir, los nodos cercanos a su ubicacin y
teniendo en cuenta que la red que se analiza es una red mvil entonces se puede decir que la
topologa de la red esta cambiando constantemente.

La caracterizacin de la movilidad de los nodos de la red no solo es importante para un

futuro proceso de enrutamiento, sino tambin para generar situaciones de movimiento

54

aleatorio y para esto se debe tener en cuenta que se puede considerar movimientos de nodos
individuales y grupos de nodos.

Ahora considerando la importancia de la movilidad de los nodos en las investigaciones de

las redes mviles ad hoc se presentan los patrones de movilidad que van desde los
totalmente aleatorios hasta los altamente predecibles y se clasifican en 3 patrones:
Deterministcos (movimiento altamente predecible), Semi-deterministicos (movimiento no
tan predecible como el anterior) y aleatorio.
La clasificacin se muestra en la figura 22 21

Figura 22.

Esquema de modelos de movilidad.

Para las redes ad hoc el patrn de movilidad mas comnmente usado es el aleatorio, por lo
tanto se va a hacer nfasis en este tipo de movimiento Browniano.

3.1.1 Patrones de movilidad aleatorios. Cuando se considera un movimiento aleatorio

como el mostrado en la figura 23 se puede observar que su movimiento futuro es totalmente
independiente de su posicin en el pasado y esta aleatoriedad hace que el movimiento sea
impredecible.

21

CAMP, T.; BOLENG, J. y DAVIES, V. A survey of mobility models for ad hoc network research. En:

Wireless Communications of Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking:
o

Research, Trends and Applications. Michigan, USA. Vol. 2, N. 5. (2002); p. 483.

55

Figura 23.

Un nodo con movimiento aleatorio.

Esta caracterstica de alta aleatoriedad e independencia en el movimiento de los nodos es

muy importante para la simulacin completa de un protocolo para redes ad hoc (como se
haba mencionado anteriormente), pues es imperativo el uso de un modelo de movilidad
que represente sin errores (o con un error aceptable) la movilidad de los nodos que
eventualmente utilizaran el protocolo establecido. Solo en este tipo de escenarios es posible
determinar si el protocolo propuesto va a ser til cuando sea implementado o no.
Un modelo de movilidad debe ser una representacin lo mas real posible de los
movimientos de los nodos de la simulacin, es decir, deben ocurrir cambios en la velocidad
y en la direccin con espacios de tiempo razonables, no seria una situacin deseable que los
nodos viajaran en lnea recta a velocidades constantes durante todo el transcurso de la
simulacin porque los nodos reales no viajaran de manera tan estricta.
Los dos primeros modelos de movilidad presentados a continuacin son los ms utilizados
por los investigadores, por lo tanto se profundizar ms en ellos.
Los diferentes tipos de modelos de movilidad son:

1. Random walk mobitily model (incluyendo sus derivaciones):

Un modelo de

movilidad simple basado en direcciones y velocidades aleatorias

2. Random waypoint mobility model: Un modelo que incluye tiempos de parada entre
cambios en el destino y la velocidad

56

3. Random direction mobility model: Un modelo que fuerza a los nodos a viajar hasta
el limite del rea de simulacin antes de cambiar su direccin y velocidad
4. A boundless simulation area mobility model: un modelo que convierte un rea de
simulacin 2D en un rea de simulacin toroidal
5. Gauss-Markov mobility model: Un modelo que usa el cambio de un parmetro para
variar el grado de aleatoriedad en los patrones de movilidad
6. Una versin probabilstica del modelo de movilidad Random Walk: un modelo que
utiliza un grupo de probabilidades para determinar la prxima posicin de un nodo
7. City Section Mobility model: Un rea de simulacin que representa las calles en una
ciudad

Random walk. El modelo de movilidad Random Walk fue diseado con el objetivo

de imitar los movimientos errticos que presentan muchas entidades de la naturaleza los
cuales se mueven de una forma impredecible. En este modelo de movilidad, un nodo
mvil se mueve de su posicin actual a una nueva posicin escogiendo de manera
aleatoria una direccin y una velocidad. La nueva velocidad se escoge a partir de unos
rangos predefinidos [vmin, vmax] y la nueva direccin se escoge a partir del rango
[0,2]. El movimiento de cada nodo en Random Walk ocurre ya sea a un intervalo
constante de tiempo t o a una distancia constante viajada d. Tras esto se calcula una
nueva direccin y una nueva velocidad. Si un nodo mvil alcanza una barrera de la
simulacin, rebota en la barrera con un ngulo determinado por la direccin que lleva
en ese momento.

El modelo de movilidad Random Walk es muy utilizado y a veces se le conoce tambin

como Brownian Motion. El modelo se puede simplificar asignando el mismo valor de
velocidad a todos los nodos mviles de la simulacin.

Una desventaja de este modelo es que los nodos pueden presentar movimientos no
reales como paros repentinos y giros muy finos. Esto se debe a que el modelo de
movilidad no tiene memoria ya que no retiene el conocimiento de valores pasados sobre

57

la velocidad o la direccin. Tanto la velocidad como la direccin de un nodo mvil son

independientes de su velocidad y direccin pasados.
Random Waypoint. El modelo de movilidad Random Waypoint incluye tiempos de
pausa entre los cambios de direccin y/o velocidad.
Un nodo empieza ubicado en un punto durante cierto periodo de tiempo (un tiempo de
pausa). Una vez este tiempo se termina, el nodo escoge una ubicacin aleatoria en el
rea de simulacin y una velocidad que esta uniformemente distribuida entre [minspeed,
maxspeed].

Luego, el nodo viaja en la direccin de la nueva ubicacin escogida y a la velocidad

seleccionada. Cuando el nodo llega a su posicin destino, para durante un tiempo
especfico antes de empezar el proceso nuevamente.

Figura 24.

Patrn de viaje de un nodo usando el modelo de movilidad Random

Waypoint.
Fuente: Ibid., p. 483.

La Figura 24 muestra un ejemplo del patrn de movimiento de un nodo usando el modelo

de movilidad Random Waypoint, empezando en una posicin escogida aleatoriamente entre
(133, 180) y la velocidad del nodo se escoge entre 0 y 10m/s.

58

Se puede observar que el patrn de movimiento del modelo de movilidad Random

Waypoint es similar al de Random Walk si el tiempo de parada fuera cero.

El modelo de movilidad Random Waypoint es comnmente usado para evaluar los
parmetros de las redes ad hoc.

Como se mencion anteriormente estos dos tipos de modelos de movilidad fueron

implementados con el fin de recrear un ambiente de simulacin que permitiera observar el
comportamiento de la red, pero durante este proceso se lleg a la conclusin que era
necesario implementar otro tipo de algoritmo de movilidad que permitiera que los nodos se
movieran en grupos.
Esto es preciso hacerlo debido a que se pretende observar como son las caractersticas de
conectividad entre los nodos y como se comportan cuando conforman clusters, estos grupos
de nodos pueden llegar a interpretarse como supernodos, es decir, conjuntos de nodos
que se ven como una entidad nica.

De la misma forma que existen modelos de movilidad para nodos individuales, tambin se
pueden encontrar algoritmos que permiten simular situaciones donde la decisin del
movimiento de los nodos depende no slo de un nodo en particular, sino tambin de los
otros nodos que conforman el grupo donde este se encuentra.
A continuacin se mencionan cinco modelos de movilidad grupal, de los cuales solo se
profundizar en el ltimo ya que fue el utilizado para la simulacin del movimiento de los
nodos de la red.
1. Exponential Correlated Random Mobility Model: Es un modelo de movilidad grupal que
utiliza una funcin para crear movimientos.
2. Column Mobility Model: Es un modelo de movilidad grupal en el cual los grupos de
nodos forman una lnea y se mueven uniformemente en una direccin en particular
3. Nomadic Community Mobility Model: Es un modelo de movilidad en el cual los grupos
de nodos se mueven juntos de una direccin a otra.
4. Pursue Mobility Model: Es un modelo de movilidad grupal en el cual un grupo de nodos
siguen un punto especfico.

59

5. Reference Point Group Mobility Model: Es un modelo de movilidad grupal donde los
movimientos de los grupos se basan en el camino recorrido por un centro lgico.
Reference Point Group Mobility Model. Este modelo de movilidad simula el
movimiento aleatorio de un grupo de nodos teniendo en cuenta que cada uno de los
nodos que conforman este grupo tiene un movimiento aleatorio individual.
El movimiento de cada uno de los grupos se basa en el camino recorrido anteriormente
por un punto llamado centro lgico.
El centro lgico es usado para calcular el movimiento del grupo teniendo en cuenta un
vector de movimiento G-M.
El centro de movimiento del grupo caracteriza completamente el movimiento de los
nodos correspondientes a su grupo, incluyendo su direccin y velocidad.
Cada uno de los nodos se mueve aleatoriamente dentro de sus propios puntos de
referencia predefinidos y estos movimientos dependen del movimiento del grupo
entero.
Los puntos de referencia individuales se mueven desde un tiempo t a t+1 y sus
posiciones son actualizadas de acuerdo al centro lgico del grupo.
Una vez son actualizados, los puntos de referencia RP(t+1) son calculados y se
combinan con un vector de movimiento aleatorio R-M, para representar el movimiento
aleatorio de cada nodo respecto a su punto de referencia individual.

60

Figura 25.

Movimiento de 3 nodos usando el modelo RPGM.

Fuente: Ibid., p. 483.

En la figura 25 se observa que existen en el tiempo t tres puntos negros que representan
puntos de referencia, RP(t), para tres nodos.
Como se muestra, el modelo RPGM usa un vector de movimiento de grupo G-M que
puede ser escogido aleatoriamente o predefinido y se usa con el fin de calcular los
nuevos puntos de referencia RP(t+1) para cada nodo en el tiempo t+1.
La nueva posicin de cada nodo se calcula asumiendo un vector aleatorio de
movimiento, R-M, con el nuevo punto de referencia escogido.
La longitud de R-M est distribuida entre 0 y 2, y est centrada en RP(t+1).

61

Figura 26.

Patrn de viaje de un grupo de 3 nodos usando el modelo RPGM.

Fuente: Ibid., p. 483.

Figura 27.

Patrn de viaje de 5 grupos usando el modelo RPGM.

Fuente: Ibid., p. 483.

Los patrones de movimiento usando el modelo RPGM se muestran en las figuras 26 y 27.
La figura 26 ilustra 3 nodos movindose juntos en un grupo, mientras que la figura 27
ilustra 5 grupos movindose con diferente nmero de nodos. Los movimientos ilustrados

62

anteriormente, es decir, los de centro lgico por grupo y los movimientos aleatorios de cada
nodo individual en un grupo, son implementados usando el modelo de movilidad Random

Waypoint.
Sin embargo, una diferencia respecto a Random Waypoint, es que los nodos individuales no
usan tiempos de pausa mientras el grupo se est moviendo. Los tiempos de pausa son
usados nicamente cuando los puntos de referencia del grupo alcanzan la posicin final,
como consecuencia todos los nodos del grupo paran en ese instante.
El modelo RPGM fue el modelo de movilidad seleccionado para llevar a cabo la simulacin
de procesos de clustering en MANET. En el numeral 4.1 se describe la implementacin de
este algoritmo de movilidad en Matlab.

3.2 SEALES DE BEACONING Y CONECTIVIDAD

Es necesario empezar definiendo una seal de beacon, debido a la propuesta de crear un

algoritmo de clustering basado en dichas seales.
En redes inalmbricas una seal de beacon es una transmisin continua de pequeos
paquetes (beacons) desde el access point (el punto de acceso o la estacin base) que
adviertan su presencia. Las unidades mviles detectan los beacons e intentan establecer una
comunicacin inalmbrica.22
Para el caso que se estudia no existe un access point o una estacin base que se encuentre
fija en un punto determinado, sino que todos los dispositivos mviles, es decir, los nodos,
son pequeas estaciones bases mviles que pueden generar y recibir seales de beaconing
con el objetivo de determinar cuales de los nodos de la red se encuentran a su alrededor y
con cuales de ellos puede establecer una comunicacin que sea efectiva y que pueda tener
un tiempo de duracin que permita una comunicacin real.

22

THE FREE DICTIONARY. Beaconing. [En lnea] Huntingdon Valley, PA, USA: Farlex Inc, revisado 1

Mayo, 2006. <[Link] [Consulta: Ene 25 :2006]

63

Este concepto (seales de beaconing) figura en el estndar 802.11 (Wireless LAN Medium

Access Control (MAC) and Physical Layer Specifications), en el cual se presentan las
especificaciones de la capa fsica y el control de acceso al medio para redes LAN que
utilizan como medio fsico para transporte de datos e informacin un sistema inalmbrico.
En este estndar las seales de beaconing o beacon frames son usadas para lograr
sincronizacin con los procesos de autenticacin.
Debido a que de la conectividad que se genere entre los nodos se puede establecer no solo
con quien puede estar relacionado determinado nodo, sino tambin el papel que cada uno
de ellos pueda desempear en un cluster especfico, y que esta conectividad se basa en la
cantidad de seales de beaconing que un nodo pueda recibir de otro que este transmitiendo
en ese instante, es necesario que se determine como y/o cuales van a ser las restricciones
para este tipo de mtrica, ya que debe establecerse un porcentaje mnimo de seales de

beacon recibidas por un nodo para que este pueda entablar una comunicacin con otro
nodo.
Es importante anotar que en este tipo de mtrica (la conectividad de los nodos) no es
necesario conocer la posicin geogrfica de cada uno los nodos, pues la nica medida de
distancia que se debe suministrar es el radio de transmisin de cada uno de ellos y no la
distancia que los separa entre si, con lo cual no seria necesario utilizar equipos de
posicionamiento como GPS.

3.3 ALGORITMOS DISTRIBUIDOS Y CENTRALIZADOS

Para determinar la naturaleza del algoritmo que se va a emplear o a implementar en

determinada simulacin, en nuestro caso el movimiento de los nodos de una red mvil ad

hoc no solo es importante establecer los patrones y modelos de movilidad entre otras
caractersticas del algoritmo, tambin es indispensable saber si ste va a ser distribuido o
centralizado, y para ello se definen ambos conceptos.

64

A nivel general los sistemas distribuidos son sistemas que funcionan sobre un conjunto de
maquinas que no contienen memoria, y que los usuarios los ven como un sistema nico,
tambin se puede definir como un conjunto de entidades que se comunican entre ellos a
travs de mensajes, los cuales son enviados sobre vas de comunicacin.
Los sistemas distribuidos mviles son una clase especial de los sistemas distribuidos donde
las entidades se mueven en un espacio fsico, con conexin/ desconexin del sistema sin
dejar de ser parte de el y continuar participando en las actividades computacionales
globales.
Las caractersticas de los sistemas distribuidos son23:
-

Uso de un sistema de comunicacin

Ausencia de memoria comn

Sincronizacin del trabajo

Ausencia de un estado global perceptible por un observador

Comunicacin a travs de mensajes

Cuando se habla de un algoritmo centralizado se entiende que existe una entidad global o
un coordinador que tiene toda la informacin topolgica y el conocimiento de la red y esta
habilitado no solo para tomar todas las decisiones referentes al enrutamiento de los
paquetes en ella, sino tambin para determinar la comunicacin entre los nodos de la red.

Teniendo claro ahora ambos tipos de algoritmo se puede decir que en el caso de las redes
mviles ad hoc es necesario tener un algoritmo distribuido, pues este permite mayor
flexibilidad y se ajusta a las condiciones de la red, permitindole movilidad y una
comunicacin eficiente.

23

Los Algoritmos Distribuidos. [pgina html] <[Link]

[Consulta: Dic 18:2005]

65

4. SIMULACIN

En el captulo 2, se revisaron las caractersticas de los procesos de clustering para redes

mviles ad hoc y se presentaron algunos algoritmos de clustering diseados hasta el
momento. En este captulo se presenta una detallada explicacin del algoritmo de clustering
diseado e implementado en Matlab durante la ejecucin del presente trabajo. Primero, se
presentan los criterios de diseo, los parmetros y, las diferentes etapas del algoritmo de

clustering desarrollado. Luego, se describe el ambiente de simulacin en el cual se

desarroll el trabajo, detallando consideraciones expuestas en el Captulo 3 como el
algoritmo de movilidad empleado y la metodologa para simular la comunicacin de los
usuarios mviles por medio de mensajes de beaconing.
El algoritmo propuesto se divide en tres etapas, que corresponden a:
4.1 Movilidad de los nodos en la red
4.2 Seales de beaconing
4.3 Algoritmo de clustering
A continuacin se explica cada una de estas etapas.

4.1 MODELO DE MOVILIDAD

Cuando se realizan simulaciones de redes de telecomunicaciones, es necesario crear un

ambiente de simulacin que cumpla con ciertas condiciones que permitan recrear algunas
caractersticas reales.

66

Para verificar el buen desempeo del algoritmo de clustering diseado, se caracteriza el

movimiento de los nodos mediante el modelo de movilidad estudiado en el Captulo 2
como Reference point group mobility model.
En la simulacin realizada, se le inicializa a cada nodo de la red una velocidad y una
direccin determinada. Cada uno de ellos durante un tiempo especfico tiene una direccin
y una velocidad que se genera aleatoriamente en el modelo de movilidad. Cuando este
tiempo se termina, el algoritmo de movilidad asigna nuevamente a cada uno de los nodos
una velocidad y una direccin de forma aleatoria.

El algoritmo contempla un rea de simulacin comprendido entre un xmax y un ymax., y unas

velocidades vmax y vmin, entre las cuales se le define a cada nodo la velocidad a la que se
mueve en un instante determinado. Estos parmetros son modificables de acuerdo a las
necesidades que se presenten. Las simulaciones se realizan con un rea de 200 x 200, y con
unos rangos de velocidad entre 0.5 y 1.

Teniendo en cuenta que el modelo de movilidad empleado es grupal, las condiciones de

movimiento para cada grupo se asignan de manera independiente El movimiento de los
grupos se determina por una matriz de 10 movimientos para cada grupo. La idea es que los
miembros de un mismo grupo se muevan apuntando a una misma posicin final pero con
diferentes ngulos y velocidades.
Los parmetros a considerar en el modelo de movilidad son: direccin de movimiento
(ngulo), velocidad, posicin inicial y posicin final.
En las ecuaciones 9 y 10 se expresa la forma de calcular la posicin en x y en y para un
nodo u.

X fin (u ) = X grupos ( grupo(u ), movimiento(u )) + radio _ grupal * cos(angulo )

Ec. 9. Clculo de la posicin en la coordenada x para un nodo u

Y fin (u ) = Ygrupos ( grupo(u ), movimiento(u )) + radio _ grupal * sin( angulo)

Ec. 10. Clculo de la posicin en la coordenada y para un nodo u

67

Donde:
X fin (u ) y Y fin (u ) son las posiciones finales del nodo u.
X grupos ( grupo(u ), movimiento(u )) y Ygrupos ( grupo(u ), movimiento(u )) son las matrices de
movimiento de los nodos de un grupo.
radio_grupal es el radio que maneja cada grupo para determinar el rea de movimiento de
los nodos del grupo.

En la figura 28, hay 4 grupos: dos de 5 nodos y dos de 10 nodos.

Figura 28.

Modelo de movilidad grupal.

4.2 SEALES DE BEACONING

La funcin del algoritmo de beaconing es simular la comunicacin entre los nodos de la

red. Esto lo hace teniendo en cuenta varios parmetros como:

68

La frecuencia de beacons: Se define como el nmero de mensajes que se transmiten

en un segundo.

Tiempo de transmisin de los beacons: Es el tiempo de transmisin de un solo

beacon. En el caso de la simulacin realizada, es el tiempo que se tarda en
transmitir 40 bytes a 1 Mbps.

Tiempo de propagacin de los beacons: Es el tiempo que tarda en propagarse los

mensajes en un medio determinado. En el caso especfico de la simulacin
realizada, este tiempo depende de la velocidad de la luz porque se toman
condiciones ideales de propagacin en el medio.

Tiempo de recepcin de los beacons: Es el tiempo de transmisin de un beacon

sumado al tiempo de propagacin.

Se establece un lmite para el nmero mximo de mensajes de beacon que se pueden

transmitir y/o recibir para facilitar los anlisis posteriores de la simulacin. Adems se
tienen en cuenta las posibles colisiones que se puedan presentar en la comunicacin.
Para ello se chequean dos situaciones:

1. Cuando un nodo recibe mensajes provenientes de dos o ms fuentes diferentes a la

vez.
2. Cuando dos o mas nodos vecinos entre s transmiten simultneamente.

Es importante anotar que los nodos que estn en capacidad de recibir un beacon de otro
nodo, se deben encontrar dentro del radio de transmisin del nodo que enva el mensaje.

69

Figura 29.

Conectividad entre los nodos.

4.3 ALGORITMO DE CLUSTERING

4.3.1 Preliminares. Se propone un algoritmo de clustering distribuido para una red mvil
ad hoc. En el algoritmo de clustering se crean grupos de nodos formados por un
clusterhead y los nodos ordinarios que lo integran, los cuales deben estar a un solo salto de
su clusterhead. Se debe cumplir que cada cluster en la red tenga un slo clusterhead y que
cada nodo se adhiera nicamente a uno de ellos. Un nodo debe determinar si cumple con
las condiciones necesarias para ser clusterhead o si se vuelve miembro de un cluster.
En la figura 30 se ilustran clusters formados en una MANET mediante el algoritmo de
clustering propuesto en el presente trabajo. Los nodos representados mediante un cuadrado
de color son los clusterheads y los nodos representados mediante un crculo de color son
los miembros de los clusters.

70

Figura 30.

Clusters.

En la mayora de los algoritmos de clustering propuestos hasta el momento, los vecinos de

un nodo se han considerado como aquellos que se encuentran dentro de su radio de
transmisin. Sin embargo, para conocer el radio de transmisin se debe calcular primero la
distancia euclidiana entre cada par de nodos de la red. Esto sugiere que en muchas tcnicas
de clustering, se asume el conocimiento sobre la posicin de los nodos mediante un
servicio de localizacin apropiado, como por ejemplo un GPS. Sin embargo, en muchas
situaciones de la vida real no siempre se tendr a disposicin esta informacin. Por la razn
anterior, se presenta la opcin de que la vecindad en un algoritmo de clustering, se
determine por medio de la cantidad de mensajes de comunicacin que un nodo recibe. Por
lo tanto, los nodos que se comunican constantemente entre s son considerados vecinos.
Esto quiere decir que dos nodos A y B pueden encontrarse a una distancia fsica muy
cercana entre s pero si no se comunican, no son considerados vecinos.

En el algoritmo de clustering implementado se ensayan por separado, los dos criterios para
determinar la vecindad entre los nodos. De esta forma, se realiza el estudio del desempeo
de un algoritmo de clustering en el cual los vecinos de un nodo se determinan primero por

71

medio del radio de transmisin y luego por la cantidad de mensajes de beaconing que
recibe un nodo de los otros.

Determinacin de la vecindad por medio del radio de transmisin. Cuando se

determina la vecindad entre dos nodos, se calcula en primera instancia la distancia

euclidiana entre ellos. Para el caso bidimensional esta distancia est dada por:

D(u) =

(x x u )2 + ( y y u )2

Ec. 11. Distancia euclidiana entre los nodos

donde:
x es la posicin de los nodos en la red en el eje x
xu es la posicin del nodo u en el eje x
y es la posicin de los nodos en la red en el eje y
yu es la posicin del nodo u en el eje y

Los nodos que cumplen con la siguiente condicin se encuentran dentro del rango de
transmisin de un nodo u:

Vecinos = D(u) <radio & D(u) >0

Ec. 12. Condicin de vecindario de los nodos

Determinacin de la vecindad por medio de mensajes de beaconing. Los nodos que

reciban un nmero de seales de beacons mayor a un porcentaje determinado por el nmero

mximo de beacons que se transmiten o reciben en un rango de tiempo, se pueden
considerar vecinos ya que existe conectividad entre ellos.

En la simulacin realizada, se tom como criterio para establecer la vecindad entre los
nodos, una conectividad mayor o igual al 40% del nmero mximo de mensajes de

72

beaconing que se pueden transmitir o recibir, este nmero es un parmetro que se define en

la simulacin.
Esta eleccin (40%) se basa en un criterio arbitrario, pensando que la conectividad fuera un
poco menor al 50% para que la rigidez a la hora de determinar la conectividad entre los
nodos no fuera muy alta.

4.3.2 Procedimiento para calcular los clusterheads. El procedimiento para calcular los
clusterheads en el algoritmo de clustering diseado est basado en la metodologa seguida

por WCA, una de las tcnicas de clustering presentadas en el captulo 3. Al igual que WCA,
el algoritmo planteado se basa en una mtrica que asigna pesos a varios parmetros de la
red. Sin embargo, en WCA se tienen en cuenta diversas variables como la distancia entre los
usuarios, la movilidad, el consumo de la batera, entre otros, en cambio en el algoritmo de
clustering diseado se consideran tan slo dos parmetros principales con los cuales se

decide que tan apto es un nodo para ser clusterhead. Estos parmetros se explican con ms
detalle a continuacin:

Movilidad. Con el fin de evitar que la topologa de la red cambie frecuentemente, es

deseable que los nodos seleccionados como clusterheads presenten un comportamiento

estable. De esta manera, los clusters formados sern menos variables y tendrn una mayor
duracin. Un nodo que presente baja movilidad, es un nodo con un comportamiento estable
ya que no se mueve rpidamente permitiendo que la configuracin de los clusters en la red
no cambie dramticamente.
La movilidad para un nodo u se calcula:

1
M u = v dt
T 0
Ec. 13. Frmula para calcular la movilidad de un nodo u

Esto representa la sumatoria de las velocidades de un nodo durante un periodo de tiempo T

73

Nmero de vecinos. Un nodo que presenta gran cercana en trminos de distancia con

varios nodos, presenta un mayor nmero de vecinos. Esto significa que es accesible para
muchos nodos de la red, lo cual lo hace apropiado para convertirse en un lder o
clusterhead.

Nmero de mensajes de beaconing recibidos.

Es deseable que un clusterhead

mantenga un alto nivel de comunicacin con sus vecinos. Por lo tanto, un nodo que recibe
muchos mensajes de beaconing de sus vecinos mantiene una alta conectividad con ellos lo
cual lo hace apropiado para convertirse en clusterhead.

A diferencia de WCA en donde el nodo con mnimo peso queda elegido como clusterhead,
en el algoritmo diseado, el nodo con mayor peso entre sus vecinos es el que queda
seleccionado para desempear este papel. Por lo tanto, el peso de cada nodo u se calcula de
la siguiente forma:

Caso 1: Algoritmo de clustering basado en el radio de transmisin. En este caso

se le asignan pesos al nmero de vecinos que tiene cada nodo y al valor de

movilidad que presenta cada uno de ellos.

Wu = w1Vu + w2

1
Mu

Ec. 14. Frmula para calcular el peso total del nodo u

donde,

Vu es el nmero total de vecinos que tiene el nodo u en un ndice de tiempo.

Mu es la movilidad del nodo u. Este trmino se invierte en la expresin presentada
para calcular Wu, ya que un clusterhead debe ser un nodo con poca movilidad.

w1 y w2 son los pesos asignados a cada factor. Se debe cumplir que

w1 + w2 = 1.

74

Caso 2: Algoritmo de clustering basado en mensajes de Beaconing. En este caso

se le asignan pesos a la suma total de los mensajes de beaconing que recibe un nodo
en un rango de tiempo dado y al valor de movilidad que presenta cada uno de ellos.

Wu = w1Bu + w2

1
Mu

Ec. 15. Frmula para calcular el peso total del nodo u

donde,

Bu es el nmero total de beacons que recibe el nodo u en un ndice de tiempo.

Mu es la movilidad del nodo u.
w1 y w2 son los pesos asignados a cada factor.

4.3.3 Preliminares para la formacin de los clusters. El algoritmo de clustering se bas

en la tcnica presentada en el captulo 3, conocida como DMAC, para la formacin de los

clusters. Al igual que en DMAC, en el algoritmo de clustering planteado cada nodo tiene un
peso asociado y un nmero de identificacin (ID), el cual es un nmero entero mayor a cero
y cuando el nodo es un clusterhead su ID se convierte en el ID del cluster que forman l y
sus vecinos. Para indicar el estado de un nodo y la pertenencia a un cluster, se utiliza una
matriz denominada Estado_cluster, esta matriz tiene tantas columnas como nodos haya en
la red y presenta dos filas: la primera fila indica el estado de cada nodo y la segunda indica
el ID del cluster al cual pertenece este nodo. Los mensajes Join y los mensajes CH que se
manejan en DMAC se representan en la primera fila de la matriz Estado_cluster mediante
un 1 y un 2 respectivamente. En el algoritmo implementado se manejan cuatro posibles
estados para un nodo:

0: Nodo sin rol definido.

1: Nodo unido a un clusterhead y con rol de nodo ordinario en un cluster.
2: Nodo con rol de clusterhead.
-1: Nodo con rol cancelado.

75

En la figura 31, hay veinte nodos organizados en cuatro clusters. Cada nodo aparece con su
ID. Se observa que los nodos 1, 3, 9 y 13 son clusterheads.

Formacin de clusters en una red con 20 nodos.

Figura 31.

Dada la configuracin de la red de la figura 31, la matriz Estado_cluster toma los siguientes
valores:

ID

10 11 12 13 14 15 16 17 18 19 20

Roll

Cluster

13 13

13 13 13 13 13 13 13 13 13 13

Tabla 1. Matriz de estado cluster

4.3.4 Etapas del algoritmo de clustering. El algoritmo implementado presenta dos

etapas: la asignacin de roles y la cancelacin de roles.

Asignacin de roles. Cuando se inicia el algoritmo de clustering todos los nodos de la

red presentan un rol no definido y su estado se representa mediante un cero.

76

Cada uno de los nodos de la red realiza el procedimiento de asignacin de roles al

comenzar el algoritmo de clustering y cuando se hace necesario asignar de nuevo el papel
de un nodo al cual le ha sido cancelado su rol. La condicin para que un nodo pueda
participar en el proceso de asignacin de roles es que su rol en la matriz Estado_cluster sea
cero.

En esta etapa se determinan primero los vecinos de un nodo. Cada nodo conoce los pesos y
los IDs de sus nodos vecinos. Si un nodo tiene el mximo peso entre sus vecinos y ningn
vecino se ha declarado clusterhead (dos clusterheads no pueden ser vecinos) entonces el
nodo se declara clusterhead de sus vecinos. Para ello coloca su rol en la matriz
Estado_cluster en 2. Para que un nodo u se una a un clusterhead se deben cumplir dos
condiciones simultneamente:

1. Entre los vecinos de un nodo u deben existir uno o ms nodos que

previamente se hayan declarado clusterheads.
2. El peso mximo entre todos los vecinos de un nodo u que tengan rol de

clusterheads debe ser mayor al peso del nodo u.

Cuando un nodo u se une a un clusterhead, coloca su rol en la matriz Estado_cluster en 1 y

su ID igual al ID del clusterhead al cual se une para indicar su pertenencia a ese cluster. Un
nodo que ya ha definido su rol no participa ms en el procedimiento de asignacin de roles.

Ejemplo de Asignacin de roles. En el siguiente ejemplo se ilustra el proceso de

asignacin de roles. La simulacin se lleva a cabo para 15 nodos cada uno con un
radio de transmisin de 70.7 y un delta_CH de 4. En la figura 32 se puede apreciar
cada nodo con su peso asociado. Al iniciar la simulacin los nodos no tienen un rol
definido y se identifican mediante un crculo azul. Como an no se han asignado los
pesos estos son cero. En el segundo ciclo de tiempo, figura 33 se observa que los
nodos con mayor peso entre sus vecinos quedan seleccionados como clusterheads.
A partir del ciclo de tiempo 3 se puede observar en las figuras 34 y 35 que los nodos
se van uniendo al clusterhead vecino en orden descendente de peso. Los miembros

77

de un cluster se identifican mediante un crculo del mismo color que su clusterhead

respectivo. En la figura 35 se observa que la red queda totalmente organizada en

clusters de nodos. Una vez completado el proceso de asignacin de roles para cada
nodo de la red, se forman en total cinco clusters: un cluster con cinco miembros, un

cluster con tres miembros, tres clusters con dos miembros y un cluster con un solo
miembro, el cual se trata simplemente de un solo clusterhead.

Figura 32.

Inicializacin.

78

Figura 33.

Figura 34.

Asignacin de clusterheads.

Formacin de clusters.

79

Figura 35.

Establecimiento de los clusters.

Cancelacin de roles. En la cancelacin de roles se verifica si un nodo cumple con las

condiciones necesarias para seguir manteniendo su rol como clusterhead o nodo ordinario y
en este caso, si puede seguir perteneciendo a un cluster determinado. Un nodo puede
participar en el procedimiento de cancelacin de roles si su rol en la matriz Estado_cluster
es 1 2. Al iniciar este procedimiento cada nodo determina sus vecinos. En caso de que un
nodo no cumpla ciertos criterios pierde el rol que tiene en ese instante y es necesario
asignarle un nuevo papel dentro de la red mediante el procedimiento de asignacin de roles.
Cuando se le cancela el rol a un nodo, se le asigna un -1 en la matriz Estado_cluster. Esto
se realiza con el fin de que en el prximo ciclo de tiempo, al iniciar el algoritmo de

clustering, su rol se vuelva cero con el fin de poder participar en el procedimiento de

asignacin de roles.

El proceso de cancelacin de roles tiene en cuenta posibles cambios topolgicos que se

presentan en la red, los cuales pueden causar la cancelacin del rol de un nodo:

80

1. Si un nodo es clusterhead
Un nodo con rol de clusterhead debe verificar si mantiene el peso mximo entre sus
vecinos que se hayan declarado clusterheads, por lo tanto, si un clusterhead tiene un vecino
que en el ltimo proceso de asignacin de roles se ha declarado clusterhead y presenta un
peso mayor, el clusterhead pierde su rol y consecuentemente su cluster se deshace.

2. Si un nodo se encuentra unido a un clusterhead

En este caso pueden presentarse alguna de las siguientes situaciones que causan la
cancelacin de roles:

2.1 Un clusterhead se convierte en vecino de un nodo que ya pertenece a un cluster. El

nodo decide cancelar su rol para luego unirse al nuevo clusterhead vecino, si el peso de este
supera el de su clusterhead actual.

2.2 Un clusterhead deja de ser vecino de un nodo que es miembro de su cluster. En este
caso el nodo cancela su rol ya que pierde la condicin de pertenencia a este clusterhead.

2.3 Un nodo comprueba que su clusterhead ha perdido su rol. En este caso el nodo debe
cancelar su propio rol porque su cluster ya no existe.

2.4 El peso de un nodo ordinario se vuelve mayor que el peso de su clusterhead actual.

En las figuras 36, 37, 38, 39 40 y 41 se pueden apreciar todos los casos excepto el 2.2. El
hecho de que un clusterhead que tiene un peso menor a algunos de los miembros de su

cluster, conserve su rol, se explica en el prximo numeral.

81

Figura 36.

Figura 37.

Situacin inicial.

Caso 2.4.

82

Figura 38.

Caso 1 y Caso 2.1.

Figura 39.

Caso 1 y Caso 2.1.

83

Figura 40.

Figura 41.

Formacin de un nuevo cluster.

Nueva topologa de la red.

84

4.3.5 Delta_CH. En el algoritmo de clustering diseado se propone una variable que

contribuye a las decisiones que se deben tomar cuando se compara el peso de un

clusterhead con el de sus vecinos que sean nodos ordinarios. Cuando un nodo ha sido
clusterhead durante varios ciclos de tiempo, puede suceder que en un momento dado uno
de sus miembros adquiera un peso mayor al suyo causando que el cluster se destruya
inmediatamente. Sin embargo, puede ocurrir que esto nada ms suceda por uno, dos o tres
ciclos de tiempo y luego el nodo que era clusterhead vuelva a tener el mayor peso entre sus
vecinos. Los pesos en cada ciclo varan con frecuencia y por ello no se justifica que un

cluster se destruya y luego se vuelva a formar por este motivo, ya que esta situacin causa
una gran variabilidad en la topologa de la red. Por esta razn, cuando se compara el peso
de un nodo que es clusterhead con el peso de uno de sus miembros durante el proceso de
cancelacin y asignacin de roles, se agrega una especie de histresis al peso del

clusterhead. Esta histresis es denominada delta de CH. Su funcin es darle una mayor
preferencia a aquellos nodos que son clusterheads, los cuales sufren pequeas fluctuaciones
en el valor de su peso que pueden causar la destruccin de su cluster. Slo cuando el peso
de un nodo ha alcanzado un valor lo suficientemente mayor que el de su clusterhead, puede
ocurrir un cambio topolgico en la red.

Un ejemplo de lo que sucede cuando el delta_CH tiene un valor de cero, es decir no se tiene
en cuenta esta histresis, se ilustra en las siguientes figuras. En la figura 42, se tiene un

cluster de color prpura conformado por un clusterhead y dos miembros. En el ciclo de

tiempo 8, uno de los nodos miembros del cluster adquiere un peso mayor al de su

clusterhead y cancela su rol. En la figura 43 se observa que el cluster de color prpura se

destruye y se forma un nuevo cluster de color azul. A partir del ciclo de tiempo 12, figura
45, el cluster azul queda completamente armado, sin embargo se observa que en el ciclo de
tiempo 16, figura 46, uno de los nodos miembros del cluster azul pierde su rol. Este nodo es
precisamente el que tena rol de clusterhead antes del ciclo de tiempo 12. En la figura 47,
este nodo vuelve a quedar seleccionado como clusterhead y en el ciclo de tiempo 20, figura
48, se observa que el cluster de color prpura se vuelve a formar nuevamente. Si se hubiera
tenido presente el delta_CH, el cluster de color prpura hubiera permanecido un mayor
tiempo y no se hubiera destruido y vuelto a formar, ya que en el momento en que se dio el

85

cambio, figura 43, la diferencia de pesos entre el clusterhead prpura, con un peso de 27.32
y el clusterhead azul, con un peso de 27.36, no era muy significativo.

Figura 42.

Paso 1.

Figura 43.

Paso 2.

86

Figura 44.

Paso 3.

Figura 45.

Paso 4.

87

Figura 46.

Paso 5

Figura 47.

Paso 6.

88

Figura 48.

Paso 7.

4.3.6 Tiempos de la simulacin. Cada una de las diferentes etapas del algoritmo se lleva
a cabo en distintos tiempos durante la simulacin. La simulacin que se propone es DES

(Discrete Event Simulation) ya que se utilizan eventos para describir acciones que se llevan
a cabo en un momento determinado. Cada uno de estos eventos se ejecuta en un instante
que incide puntualmente en una escala temporal. Otra caracterstica importante es que el
tiempo de simulacin vara de forma irregular, es decir no fluye continuamente ya que el
contador que lo determina no avanza de manera constante. Este es el caso del tiempo de

beaconing en la simulacin realizada. En la simulacin que se presenta las variables que

determinan la ocurrencia de cada evento en el tiempo son:

ndice de tiempo. Es el tiempo que sincroniza los tiempos de los distintos eventos en el
algoritmo, adems determina el tiempo en el que se almacenan los datos.

Movilidad.
-

tmov: Tiempo en el cual se ejecuta el algoritmo de movilidad de los nodos.

dtmov: Delta de tiempo de movimiento. Es el valor que se le incrementa al

tmov cada vez que se ejecuta el algoritmo de movilidad de los nodos.

Seales de Beaconing.

89

tb: Es el tiempo de la simulacin en el que se da la transmisin de los

beacons entre los nodos.

dtb: Delta de tiempo de beaconing. Es el valor que se le incrementa al tb

cada vez que se ejecuta el algoritmo de envo de seales de beaconing.

Clustering.
-

tcluster: Tiempo en el cual se realiza el proceso de clustering. En la

simulacin el algoritmo de clustering se lleva a cabo una vez se haya
ejecutado la parte de la movilidad y del envo de seales de beaconing, con
el fin de poder obtener los valores necesarios para calcular el peso de cada
nodo.

dtcluster: Delta de tiempo de clustering. Es el valor que se le incrementa al

tcluster cada vez que se ejecuta el proceso de clustering.

Graficacin.
-

tgraf: Tiempo en el cual se realizan las grficas de la simulacin.

dtgraf: Delta de tiempo de graficacin. Es el valor que se le incrementa al

tgraf cada vez que se ejecuta la parte de la graficacin.

En la figura 49 se observa que la movilidad determinada por el tmov y el envo de las

seales de beaconing de acuerdo con tbeacon son los primeros eventos que se realizan en la
simulacin, en estas etapas se realiza el movimiento de todos los nodos comprendidos en la
red, adems se inicia la comunicacin entre ellos por medio de las seales de beaconing las
cuales se transmiten peridicamente y de manera muy frecuente. Despus de cierto tiempo
en el cual se permite que la red se establezca se inicia la graficacin con el parmetro tgraf
permitiendo la visualizacin del comportamiento de los nodos de la simulacin y la fase de

clustering que permite que se ejecuten las etapas del algoritmo discutidas anteriormente en
4.3.4. En el algoritmo diseado se establecieron ciertos valores de tiempo que se
consideraron apropiados para llevar a cabo las simulaciones, estos se pueden observar en la
figura 49, adems es necesario aclarar que ninguno de los eventos se efecta
simultneamente.

90

Figura 49.

Tiempos manejados para la ocurrencia de los eventos en el algoritmo.

91

5. RESULTADOS

En este captulo, se presentan los resultados estadsticos obtenidos a partir de la simulacin

del algoritmo de clustering diseado. Se presentan los resultados obtenidos tanto para el
caso en el cual la vecindad entre los nodos se determina por medio del radio de transmisin
como para cuando la vecindad se determina mediante la recepcin de mensajes de

beaconing. Se realiza un anlisis sobre los resultados y se establece una comparacin entre
los dos mtodos empleados para determinar la vecindad entre los nodos. Las medidas
estadsticas utilizadas, se encuentran relacionadas con la duracin media de los clusters, el
tamao promedio de los clusters, la variabilidad del tamao de los clusters y el nmero de

clusters formados, entre otros.

5.1. EXPERIMENTOS Y PRUEBAS

Con el fin de evaluar el desempeo del algoritmo diseado, se llevaron a cabo dos
experimentos y por cada uno de ellos se realizaron 64 pruebas. A continuacin se presentan
las caractersticas comunes de cada una de las pruebas realizadas en cada experimento:

Experimento 1

Forma de
hallar los
vecinos de
un nodo

Por medio
del radio del
transmisin

Pesos
Clculo de pesos
w1
Wu = w1Vu + w2

1
Mu

w2

0.5 0.5

rea de
simulacin
por prueba
(m)

Tiempo
mximo de
simulacin
por prueba
(s)

Nmero de
nodos

200 x 200

8000

30

Tabla 2. Tabla de caractersticas Experimento 1

92

Experimento 2

Forma de
hallar los
vecinos de
un nodo

Por medio
de las
seales de
Beaconing

Pesos
Clculo de pesos
w1
Wu = w1Bu + w2

1
Mu

w2

0.5 0.5

rea de
simulacin
por prueba
(m)

Tiempo
mximo de
simulacin
por prueba
(s)

Nmero de
nodos

200 x 200

8000

30

Tabla 3. Tabla de caractersticas Experimento 2

Pruebas. Las variables que varan entre cada una de las pruebas son el delta de CH
y el radio de transmisin. En una sola prueba se tiene un valor de delta de CH y de
radio de transmisin determinado. El radio de transmisin toma valores de 10, 20,
30, 40, 50, 60, 70 y 80. Para cada uno de los radios de transmisin el delta de CH
toma valores de 0, 1, 2, 3, 4, 5, 6, 7. Como resultado de estas combinaciones se
realizan en total 64 pruebas por cada experimento.

5.2 OBTENCIN DE LOS RESULTADOS ESTADSTICOS

Mediante la matriz Estado_cluster se obtuvieron los datos necesarios para poder graficar los
resultados estadsticos de la simulacin que se presentan en este captulo. A continuacin se
describen los diferentes pasos que se siguen para obtener los resultados estadsticos que
evalan el desempeo del algoritmo de clustering diseado:

5.2.1 Matriz M_estadisticas. El primer paso que se realiza para la adquisicin de datos es
crear una matriz denominada M_estadisticas la cual va almacenando el valor de la matriz
Estado_cluster durante cada ndice de tiempo de la simulacin. Por lo tanto, el ndice de

93

tiempo que maneja la matriz M_estadisticas se incrementa en 1 cada vez que el algoritmo
ingresa a la etapa de clustering. De esta forma, durante el tiempo de simulacin, se
almacena toda la historia del proceso de clustering la cual incluye cuando los nodos
cancelan su rol, asignan su rol, se declaran clusterheads o nodos ordinarios, y se forman los

clusters.
En las tablas 4, 5 y 6 se presenta la notacin de la matriz M_estadisticas. Se puede observar
por ejemplo que en el ndice de tiempo 8 el nodo 4, el nodo 16 y el nodo 30 se declaran

clusterheads (rol = 2) y los dems nodos no han declarado su rol todava (rol = 0). En el
ndice de tiempo 16, se observa que varios nodos se van uniendo a estos clusterheads (rol =
1) y que el nodo 11 tambin se declara clusterhead. En el ndice de tiempo 21, se aprecia
que cada uno de los nodos ya ha establecido su rol y que se han formado en total 4 clusters
en la red.

ID

10

11

12

13

14

15

16

17

18

19

20

Roll

Cluster

16

21 22 23 24 25

26

27

28 29

30

Roll

Cluster

30

ID

Tabla 4. M_estadisticas en el ndice de tiempo 8

ID

10

11

12

13

14

15

16

17

18

19

20

Roll

Cluster

11

16

16

16

16

16

21 22 23 24 25

26

27

28 29

30

Roll

Cluster

16 16 16

30

30

30 30

30

ID

Tabla 5. M_estadisticas en el ndice de tiempo 16

94

ID

10

11

12

13

14

15

16

17

18

19

20

Roll

Cluster

11

11

16

11

11

16

16

16

16

16

21 22 23 24 25

26

27

28 29

30

11 16 16 16 11

30

30

30 30

30

ID
Roll
Cluster

Tabla 6. M_estadisticas en el ndice de tiempo 21

5.2.2 Matriz Clusters_cell. Al observar la matriz M_estadisticas presentada en el

ejemplo anterior, se puede apreciar que el cluster 4, en el ndice de tiempo 8, tiene un slo
miembro que es precisamente el nodo 4 declarado como clusterhead. Luego en el ndice de
tiempo 16, este cluster est conformado por 9 nodos: 1 clusterhead y 8 miembros. En el
ndice de tiempo 21, este mismo cluster ya tiene 10 miembros: 1 clusterhead y 9 miembros.
Si se realiza este anlisis por cada cluster que se forma en la red durante el tiempo total de
la simulacin, se puede determinar el comportamiento de cada uno de los clusters en cuanto
a su duracin, variabilidad y al nmero de nodos que lo conforman, es decir su tamao.
Para obtener estadsticas respecto a este comportamiento, se cre una matriz tipo cell array
denominada Clusters_cell con el fin de extraer la informacin contenida en M_estadisticas
respecto a cada cluster durante el tiempo total de simulacin.
El objetivo de Clusters_cell es almacenar en cada celda el nmero de nodos pertenecientes
a un cluster desde el principio de su formacin hasta que se desarma. Esto se visualiza
mejor mediante el siguiente ejemplo. En el mismo ensayo en el que se obtuvo la matriz
M_estadisticas presentada en el ejemplo anterior, se obtuvo tambin la siguiente matriz
Clusters_cell que se visualiza en Matlab de la siguiente forma:

95

>> Clusters_cell =

Columns 1 through 4

[1x42 double]

[1x34 double] [1x42 double] [1x10 double]

Column 5

[1x29 double]

Una celda de Clusters_cell corresponde a un vector como se muestra a continuacin para la

celda nmero 3:

Clusters_cell{3} = [1

10

1]

El valor de cada posicin de este vector corresponde al nmero de nodos pertenecientes a

un cluster en un ndice de tiempo. En este ejemplo, Clusters_cell{3}hace referencia al
comportamiento del cluster formado por el clusterhead 16 y sus miembros. La informacin
contenida en el vector se puede interpretar de la siguiente forma: Como en M_estadisticas
el nodo 16 se declara clusterhead en el ndice de tiempo 8, el cluster slo tiene un miembro
inicialmente. Esta situacin corresponde a la primera posicin del vector Clusters_cell{3}
en donde aparece un 1. Es de notar que este valor siempre figura al inicio de cada una de las
celdas de la matriz Clusters_cell ya que un cluster se crea siempre a partir de un

clusterhead. En el ndice de tiempo 16 de M_estadisticas hay 8 nodos que pertenecen al

cluster, esto corresponde a la posicin 9 del vector Clusters_cell{3}. Luego en el ndice de
tiempo 21 (posicin 14 del vector Clusters_cell{3}), hay 9 nodos en el cluster. Se puede
notar que el cluster al final pierde todos sus miembros y que el clusterhead permanece
como nico miembro durante varios ndices de tiempo.

96

Se puede apreciar que Clusters_cell aporta informacin acerca del comportamiento de cada

cluster formado en la red. Como cada celda corresponde a un vector, por cada una se puede
calcular su media, su varianza y su longitud la cual se relaciona con la duracin del cluster.
Esto se hace simplemente con las funciones mean( ), var( ) y length( ) de Matlab. Como
este procedimiento se realiza para cada celda se pueden obtener los siguientes vectores:

DuracinCluster: Es un vector que contiene en cada posicin, el valor de la

duracin de cada cluster formado en la red, durante el tiempo total de la
simulacin.

Media: Es un vector que contiene en cada posicin, el valor promedio del

nmero de miembros de cada cluster formado en la red, durante el tiempo total
de la simulacin.

Varianza: Es un vector que contiene en cada posicin, el valor de la

variabilidad del nmero de miembros de cada cluster formado en la red, durante
el tiempo total de la simulacin.

Es importante notar que M_estadisticas, Clusters_cell, DuracionCluster, Media y Varianza

se obtienen a partir de una sola prueba en donde se asigna un valor determinado al delta de
CH y al radio de transmisin.

5.2.3 Recopilacin de la informacin para cada experimento. Por cada experimento se

recopilaron los resultados de todas las pruebas realizadas con diferentes valores de delta de
CH y de radios de transmisin. A continuacin se explican las matrices donde se reunieron
los resultados de cada una de las pruebas realizadas:

N_mean_dur_matriz, N_mean_media_matriz y N_mean_var_matriz

Una vez obtenidos los vectores DuracionCluster, Media y Varianza se saca el valor medio
de cada uno y este valor se va almacenando por cada prueba en las siguientes matrices
respectivamente:

97

N_mean_dur_matriz: Matriz que almacena el valor de la duracin media de los

clusters.

N_mean_media_matriz: Matriz que almacena el valor medio del nmero promedio

de miembros de los clusters, lo cual se puede entender tambin como el tamao promedio
de los clusters.

N_mean_var_matriz: Matriz que almacena el valor de la variabilidad media del

tamao de los clusters.

En los experimentos realizados, N_mean_dur_matriz se visualiza de la siguiente forma:

>> N_mean_dur_matriz =

[51.6088 108.1341 94.8906 116.2635 103.0326 107.4152 121.4925 116.4652

21.1862 61.9883 85.7884 92.4873 87.0021 87.1688 82.6139 76.6484
14.4630 43.0934 76.9450 87.7910 78.7096 78.6980 79.1201 85.5722
14.5416 32.8472 63.7477 82.1424 85.5527 79.1294 89.6845 81.2537
12.5410 32.9609 40.7683 70.9131 84.3752 82.0930 91.3835 94.5222
13.2297 25.4080 42.3671 49.8361 86.0508 76.6515 90.1456 96.7830
12.0860 24.7152 34.8709 51.0952 68.3260 92.4778 75.4238 94.3838
13.1081 27.8659 32.0702 49.7465 57.4760 83.6130 84.6039 96.6421]

Esta matriz en particular es la obtenida en el experimento 1. Cada columna de

N_mean_dur_matriz corresponde a un valor de delta de CH determinado y cada fila

corresponde a un valor de radio de transmisin determinado. Como el delta de CH se vara
desde 0 hasta 7, esta matriz tiene 8 columnas. Asimismo, como el radio de transmisin se
vara desde 10 hasta 80 con pasos de 10, N_mean_dur_matriz tiene 8 filas. En la fila 1
columna 1, el valor de 51.6088 es la duracin media de los clusters cuando el delta de CH

98

es 0 y el radio de transmisin es 10. Todos los valores en esta columna corresponden a un

delta de CH de valor 0 pero con diferente radio de transmisin, y todos los elementos de la
fila corresponden a un radio de 10 pero con diferente valor de delta de CH. De esta forma
tambin se observa que el valor en la fila 8 columna 8, corresponde a la duracin media de
los clusters cuando el delta de CH es 7 y el radio de transmisin es 80.
Para N_mean_media_matriz y N_mean_var_matriz se hace el mismo anlisis.

Numero_clusters_matriz

El nmero de clusters formados por cada experimento se obtuvo calculando la longitud de

la matriz Clusters_cell. Cada valor se va almacenando en Numero_clusters_matriz de la
misma forma como se hace para N_mean_dur_matriz.

Clusters_mas_5_matriz y Clusters_mas_10_matriz

Estas matrices almacenan los clusters con ms de 5 usuarios y 10 usuarios respectivamente.

5.3 EXPERIMENTO 1. RESULTADOS DE LA SIMULACIN DEL ALGORITMO

BASADO EN EL RADIO DE TRANSMISIN

Duracin media de los clusters

99

Figura 50.

Duracin media del tamao de los clusters (radio).

Para una mejor comprensin de la figura 50, se presentan las vistas bidimensionales de esta
figura:

Figura 51.

Vista bidimensional de Duracin media del tamao de los clusters (radio):

Duracin media del tamao de los clusters vs Radio de transmisin

100

Figura 52.

Vista bidimensional de Duracin media del tamao de los clusters (radio):

Duracin media del tamao de los clusters vs Delta de CH

En las figuras 50, 51 y 52 se pueden realizar las siguientes apreciaciones:

Para un radio determinado, al aumentar el delta de CH se aumenta la duracin media de los

clusters. El mayor crecimiento en la duracin media de los clusters se presenta cuando el

delta de CH pasa de tomar un valor de 0 a un valor de 1, para cada uno de los radios de
transmisin. Por lo tanto cuando se incluye el delta de CH, as sea que tome un valor
pequeo, se mejora notablemente la duracin media de los clusters permitiendo que estos
se comporten de una forma ms estable.
Por otro lado, para un delta_CH determinado la duracin media de los clusters es mayor
cuando el radio de transmisin toma el menor valor el cual corresponde a 10. A medida en
que se aumenta el radio de 20 a 80 la duracin media disminuye levemente y oscila entre
valores ms pequeos cuando el delta de CH es ms pequeo y valores ms grandes cuando
el delta de CH es mayor. A medida en que el radio aumenta, se observa que cuando un

cluster se deshace el algoritmo demora ms tiempo en volver a formar otro cluster de

nuevo. Por lo tanto, se paga un mayor precio en la formacin de los clusters ante los
cambios topolgicos de la red.

101

El hecho de que la duracin media de los clusters presente un valor grande cuando el radio
de transmisin de los clusters toma el valor ms pequeo, es debido a que se generan una
gran cantidad de clusters de pequeo tamao conformados muchas veces por un solo

clusterhead o por dos o tres nodos ms. A pesar de que estos clusters no son de gran
tamao, son muy numerosos y como el radio es tan pequeo pueden durar bastante. Sin
embargo, la formacin de muchos clusters de poco tamao no es algo deseable ya que se
pierde el objetivo de simplificar la topologa de la red. Por esta razn se hace necesario
analizar tambin el nmero total de clusters formados.

Tamao promedio de los Clusters

Figura 53.

Tamao promedio de los clusters (radio).

Para un delta_CH determinado al aumentar el radio de transmisin de 10 a 80 aumenta el

tamao medio que tienen los clusters. Por lo tanto cuando el radio es mayor los clusters
tienen un mayor nmero de miembros. Cuando el radio es pequeo los miembros de los

clusters son uno o dos nodos y el clusterhead.

Por otra parte, para un radio determinado se aprecia que al aumentar el valor del delta_CH
el tamao promedio que tienen los clusters disminuye. Este hecho se relaciona con la

102

grfica anterior teniendo en cuenta que a medida que aumenta el delta_CH aumenta la
duracin media de los clusters.
El hecho anterior se puede explicar de la siguiente forma: Cuando se tienen radios
pequeos, los clusters son de menor tamao y un cambio topolgico no har que el
algoritmo de clustering se demore tanto en reconstruir los clusters nuevamente. En cambio,
cuando se tienen radios muy grandes, los clusters son de gran tamao y si de repente se
destruyen, el algoritmo de clustering se demora un largo tiempo en volver a formar un

cluster de nuevo. Por esta razn el tamao promedio de los clusters es menor cuando el
delta de CH aumenta ya que este factor logra que los clusters se comporten de una manera
ms estable y no sean tan vulnerables a los cambios topolgicos.

Variabilidad del tamao de los clusters.

Figura 54.

Variabilidad del tamao de los clusters (radio).

En la figura 54, se puede apreciar que para un delta_CH determinado, a medida en que se
aumenta el radio, la variabilidad del tamao de los clusters es mayor.
Cuando los radios de transmisin son grandes se pueden formar 2 o 3 clusters durante toda
la simulacin cada uno con un nmero diferente de usuarios pero que varan entre 5 y 15
por cada cluster. Por esta razn se presenta una mayor variabilidad en su tamao.

103

En la figura, se observa tambin que generalmente cuando el delta_CH es mayor, para un

radio determinado, la variabilidad del tamao de los clusters disminuye y por lo tanto los

clusters son ms estables.

Nmero de clusters formados

Figura 55.

Nmero de clusters formados (radio).

Para una mejor comprensin de la figura 55, se presentan las vistas bidimensionales de esta
figura:

104

Figura 56.

Vista bidimensional de Nmero de clusters formados(radio): Nmero de

clusters formados vs Radio de transmisin

Figura 57.

Vista bidimensional de Nmero de clusters formados(radio): Nmero de

clusters formados vs Delta de CH

En las figuras 55, 56 y 57 se pueden realizar las siguientes apreciaciones:

Para un delta_CH determinado a medida en que se aumenta el radio de transmisin
disminuye el nmero de clusters formados. Esto se espera ya que a medida que el radio de

105

transmisin de un nodo es mayor, este puede abarcar un rea ms grande y por lo tanto el
nmero de clusters formados es menor. Esto se relaciona con lo observado en la figura 55,
donde se aprecia que el tamao de los clusters es mayor a medida que crece el radio de
transmisin.

Por otro lado, para un radio de transmisin determinado, se observa que en general a
medida en que se aumenta el delta_CH el nmero de clusters formados se hace menor. La
disminucin en el nmero de clusters formados es muy notable cuando el delta_CH pasa de
tener un valor diferente de 0. Por lo tanto, se puede concluir que el delta de CH mejora el
desempeo del algoritmo de clustering ya que permite que el nmero de clusters formados
sea menor. Esto conlleva a que los clusters sean ms estables debido a que permanecen por
ms tiempo y los cambios topolgicos son menos frecuentes.

Porcentaje del nmero de clusters formados con ms de 5 usuarios respecto al

nmero de clusters formados

Figura 58.

Porcentaje del nmero de cluster formados con ms de 5 usuarios respecto al

nmero de clusters formados (radio).

106

En la grfica se puede observar que a mayor radio de transmisin, los clusters formados
tienen un mayor nmero de usuarios y por lo tanto presentan un mayor tamao. Se puede
apreciar tambin, que el delta_CH no es un factor determinante para esta medida, ya que el
nmero de clusters formados con ms de 5 usuarios presenta un mismo valor para un radio
determinado con diferentes deltas_CH. Por lo tanto, se puede concluir que el delta_CH
puede contribuir a la estabilidad de los clusters pero el hecho de que un cluster sea de
mayor tamao depende del radio de transmisin ya que a medida en que se abarca una
mayor rea, se forman clusters de mayor tamao.

Porcentaje del nmero de clusters formados con ms de 10 usuarios respecto al

nmero de clusters formados

Figura 59.

porcentaje del nmero de clusters formados con ms de 10 usuarios respecto

al nmero de clusters formado (radio).

En esta grfica, se observa un comportamiento similar al de la grfica anterior. A medida

en que aumenta el radio de transmisin, el nmero de clusters formados con ms de 10
usuarios es mayor. Sin embargo, la gran diferencia con la grfica anterior radica en que la
medida de los clusters con ms de 10 usuarios es slo representativa para los radios de
transmisin ms grandes y no para los radios de transmisin medianos (30 y 40), como s
suceda en el caso anterior.

107

5.4 EXPERIMENTO 2. RESULTADOS DE LA SIMULACIN DEL ALGORITMO

BASADO EN SEALES DE BEACONING

Duracin media de los clusters.

Radio vs deltaCH vs Nmeandur

120
100

Nmeandur

80
60
40
20
0
0
20
40
60
80
Radio

Figura 60.

deltaCH

Duracin media de los clusters (Seales de beaconing).

Para una mejor comprensin de la figura 60, se presentan las vistas bidimensionales de esta
figura:

108

Figura 61.

Vista bidimensional de Duracin media del tamao de los clusters

(beaconing): Duracin media del tamao de los clusters vs Radio de transmisin

Figura 62.

Vista bidimensional de Duracin media del tamao de los clusters

(beaconing): Duracin media del tamao de los clusters vs Delta de CH

En las figuras 60, 61 y 62 se pueden realizar las siguientes observaciones:

109

La media de la duracin de los clusters permanece relativamente estable y tendiendo a ser

muy pequea cuando se tienen radios grandes y que adems la presencia del delta_CH
puede llegar a afectar un poco la estadstica en este punto pero la variacin no es muy
significativa.
Cuando se analiza el comportamiento de la grfica respecto al radio de transmisin se
puede observar que la media de la duracin es mucho mayor cuando los radios de
transmisin son ms pequeos y que se incrementa ante el aumento del delta_CH. De estas
observaciones se puede deducir que la variable delta_CH en este caso es til debido a que a
medida en que esta aumenta, la media de la duracin de los clusters tambin lo hace,
aunque es importante anotar que este gran aporte que se obtiene del delta_CH slo es
altamente apreciable cuando se cuentan con radios de transmisin pequeos. Esto se debe a
que cuando un nodo transmite con un radio de transmisin de pequea magnitud, es muy
probable que no tenga nodos vecinos a su alrededor y si los tiene se pueden generar
colisiones que no permiten que se establezca ningn tipo de comunicacin. De esta forma
un nodo que se declara clusterhead y es el nico integrante de su cluster, puede permanecer
as durante un tiempo prolongado. Esta situacin se hace an ms verdica cuando se
aumenta el delta_CH ya que aunque llegue otro nodo y logre llegar a unirse a l como nodo
ordinario es difcil que lo sobrepase en peso y le gane la posicin de clusterhead dentro del

cluster.
Por otro lado, cuando se tiene un radio de transmisin de beacons grande la cantidad de
nodos que alcanzan a unirse a un solo cluster es muy grande, tanto que en algunos periodos
de simulacin slo se forma un nico cluster, el cual contiene todos los nodos de la red.
Cuando esto sucede la comunicacin entre los nodos no presenta tantos inconvenientes
como cuando el radio de transmisin es pequeo y es mucho ms probable que un nodo que
hasta el momento hubiera sido un nodo ordinario perteneciente o no a determinado cluster
sobrepase el peso de algn clusterhead actual.

Tamao promedio de los clusters.

110

Radio vs deltaCH vs Nmeanmedia

Nmeanmedia

1
8
6

80
60

40

2
0

deltaCH

Figura 63.

20
0

Radio

Tamao promedio de los clusters (Seales de beaconing).

Al observar la grfica 63, se observa una clara relacin con lo mencionado en la grfica
anterior, ya que se puede ver que a medida que aumenta el radio de transmisin aumenta el
tamao del cluster, debido a que un determinado clusterhead tiene un mayor rango de
cobertura y puede abarcar a muchos ms nodos en su cluster, mientras que cuando tienen
un radio muy pequeo lo mas probable es que el cluster tenga un tamao pequeo porque el
nico nodo que conforma el cluster es l mismo.
Es importante anotar que en esta grfica no se ve tan claramente la influencia del delta_CH
y esto es debido a que su nica funcin consiste en darle apoyo a un nodo que actualmente
se desempea como clusterhead, pero no tiene nada que ver con la cantidad de nodos que
se encuentren en una red.
De la grfica tambin se puede apreciar que la medida del tamao de los clusters es
inversamente proporcional a la duracin de los mismos, pues a medida que estos van
hacindose ms grandes su duracin es menor.

111

Variabilidad del tamao de los clusters.

Radio vs deltaCH vs Nmeanvar

12

Nmeanvar

10
8
6
4
2
0
8
6

80
60

40

2
deltaCH

Figura 64.

20
0

Radio

Variabilidad del tamao de los clusters.

Cuando se analiza la variabilidad del tamao de los clusters es indispensable referirse a las
dos grficas anteriormente analizadas, ya que estas (y en especial la anterior) estn
directamente relacionadas con el tamao de los clusters.
Cuando se tiene un cluster muy pequeo (en el peor de los casos su nico integrante es el

clusterhead) su variabilidad no tiende a ser mucha debido a que tiene un radio de

transmisin muy pequeo y su comunicacin con los dems nodos de la red puede llegar a
ser muy defectuosa por los problemas mencionados anteriormente de colisiones y corto
radio de transmisin, y por lo tanto su tamao permanece constante por mucho tiempo.
Mientras que si se tiene un cluster formado por muchos nodos (en el peor de los casos
todos), se deduce que el radio de transmisin es suficientemente grande, y por esta razn no
se presentan tantas colisiones en la comunicacin entre los nodos. Cuando un cluster es de
gran tamao tiende a presentar mucha actividad debido al cambio constante de informacin
y estado de los nodos que lo conforman, y a que los nodos se unen o salen del cluster
variando su tamao sin que este se destruya por completo.

112

Cabe anotar que al igual que en el caso anterior, el delta_CH no es una variable muy
relevante, pues no se observa un comportamiento definido ni cambios que puedan llamarse
peridicos o que describan algn tipo de comportamiento.

Nmero de clusters formados.

Radio vs deltaCH vs Nmero clusters

6000

Numero clusters

5000
4000
3000
2000
1000
0
20

8
6

40
4

60

2
80

Radio

Figura 65.

deltaCH

Nmero de clusters formados (Seales de beaconing).

Para una mejor comprensin de la figura 65, se presentan las vistas bidimensionales de esta
figura:

113

Figura 66.

Vista bidimensional de Nmero de clusters formados(beaconing): Nmero

de clusters formados vs Radio de transmisin

Figura 67.

Vista bidimensional de Nmero de clusters formados(beaconing): Nmero

de clusters formados vs Delta de CH

En las figuras 65, 66 y 67 se pueden realizar las siguientes observaciones:

114

Cuando se tienen radios muy pequeos y deltas_CH pequeos hay una gran cantidad
determinada de clusters creados. En el radio especfico de 20, se observa un pico en la
grfica que representa un alto nmero de formacin de clusters, esto sucede debido a que
como se est trabajando en ese momento con un radio muy pequeo se forman muchos

clusters (con el clusterhead como nico nodo) y la comunicacin entre los nodos es muy
mala debido a las colisiones.
Por otro lado, a medida en que aumenta el radio de transmisin de los beacons y el
delta_CH, el nmero de clusters formados tiende a decrecer.

Porcentaje del nmero de clusters formados con ms de 5 usuarios respecto al

nmero de clusters total

Radio vs deltaCH vs [Link] mas de 5/[Link]

0.4

Clusters mas 5

0.3

0.2

0.1

0
8
6

80
60

40

2
deltaCH

Figura 68.

20
0

Radio

Porcentaje del nmero de clusters formados con ms de 5 usuarios respecto

al nmero de clusters total (Seales de beaconing).

En esta grfica podemos observar los clusters formados por un nmero de usuarios mayor a
5, esto es importante determinarlo debido a que en una situacin real no es muy
conveniente que se tengan clusters de pocos nodos porque se puede perder la conexin con
ellos muy fcilmente.

115

En esta grfica podemos observar que independiente del delta_CH que se maneje en
cualquiera de los puntos de la simulacin (este parmetro presenta en este caso un
comportamiento aleatorio que no es determinante), a medida que aumenta el radio de
transmisin aumentan tambin el nmero de clusters formados por ms de 5 nodos. Esto
sucede gracias a que la comunicacin entre los nodos en estas instancias es mucho mejor
que cuando los radios son pequeos, donde se observa un aumento pobre del nmero de

clusters formados que cumplen con la condicin establecida.

Porcentaje del nmero de clusters formados con ms de 10 usuarios respecto al

nmero de clusters total

Radio vs deltaCH vs [Link] mas de 10/[Link]

Clusters mas 10

0.2

0.15

0.1

0.05

0
8
6

80
60

40

2
deltaCH

Figura 69.

20
0

Radio

Porcentaje del nmero de clusters formados con ms de 10 usuarios respecto

al nmero de clusters total (Seales de beaconing).

En esta grfica se pone una condicin ms estricta que en la anterior porque slo se tienen
en cuenta los clusters que tengan ms de 10 nodos en su cluster.
Las ventajas de este tipo de condiciones son las explicadas anteriormente, y el
comportamiento de la grfica es similar, pero se puede observar muy claramente y en

116

comparacin con la grfica anterior que el conteo de los clusters se hace a partir de radios
ms o menos grandes.

117

6. CONCLUSIONES

Durante el proceso de implementacin de los algoritmos de movilidad, se concluy que el

modelo que mejor simula el comportamiento de las redes mviles ad hoc en la vida real es
el Reference Point Group Mobility Model ya que la comunicacin en la cotidianidad se
establece entre grupos de usuarios. El algoritmo de clustering puede ser ms estable en la
simulacin si se consideran en el modelo de movilidad la formacin de grupos.

De las diferentes tcnicas de clustering estudiadas, se determin que la ms apropiada para

la eleccin de los clusterheads era WCA debido a que variando los pesos se podra
involucrar el concepto de conectividad por beaconing. Para la estructura del algoritmo de

clustering se determin que DMAC presenta una filosofa de formacin de clusters muy
prctica porque propone claramente los pasos a seguir en el proceso de la formacin de un

cluster teniendo en cuenta la seleccin de los clusterheads y los diferentes casos que se
pueden presentar durante su tiempo de vida.

Mediante la comparacin de las estadsticas que conciernen a la duracin media de los

clusters y al nmero de clusters formados, se concluye que el desempeo del algoritmo de

clustering basado en la distancia euclidiana entre los nodos es mejor que el que est basado
en seales de beaconing. Esto se debe a que cuando el algoritmo se basa en la distancia
entre los nodos, la duracin media de los clusters es mayor y el nmero de clusters
formados es menor. Esto indica que los clusters son ms estables debido a que permanecen
por ms tiempo y los cambios topolgicos son menos frecuentes.

El delta de CH result ser un parmetro determinante en los resultados de la simulacin del

algoritmo de clustering basado en el radio de transmisin de los nodos, ya que las

estadsticas mejoraban notablemente cuando se inclua este parmetro en las simulaciones
realizadas. El delta de CH es un aporte novedoso para el diseo de los algoritmos de

clustering basados en la asignacin de pesos a los nodos. Los resultados muestran que este
parmetro permite que los clusters se comporten de una forma ms estable durante el

118

tiempo de simulacin. Esto se debe a que los clusterheads logran mantener su rol como
lderes durante tiempos ms largos.

Contrario al caso del algoritmo de clustering basado en el radio de transmisin de los

nodos, cuando se analizan los resultados obtenidos con el algoritmo de clustering basado

en seales de beaconing respecto al tamao de los clusters y a su variabilidad, se puede

comprobar que el delta de CH en este caso no mejora significativamente las caractersticas
que conciernen a la formacin de los clusters ni su eficiencia dentro de la red. Esto es
debido a que la mtrica utilizada en este caso es la conectividad y esta requiere que la
comunicacin est libre de colisiones.

Se comprob que un algoritmo de clustering para redes mviles ad hoc depende en gran
medida del radio de transmisin asignado a los nodos, tanto para el algoritmo basado en la
distancia euclidiana entre los nodos como para el que se basa en las seales de beaconing.

Se mostr que cuando el radio de transmisin de los clusters en una red mvil ad hoc es
demasiado pequeo, muchos nodos presentan el papel de clusterhead, lo que genera un
mayor trfico de informacin. Esto hace que no se cumpla de forma ptima el objetivo de
un proceso de clustering el cual consiste en simplificar la topologa y disminuir la
congestin de la red.

Cuando se tienen radios de transmisin pequeos el algoritmo de clustering no se demora

tanto en reconstruir los clusters nuevamente ante un cambio topolgico. En cambio, cuando
se tienen radios muy grandes el algoritmo de clustering se demora un largo tiempo en
volver a formar un cluster de nuevo, lo que resulta desventajoso.

Se mostr que la variabilidad del tamao de los clusters presenta una gran dependencia
respecto al radio de transmisin que se tenga establecido. Si el radio es muy grande los

clusters tienden a interactuar ms entre s ya que los nodos pueden presentar un mayor
nmero de vecinos. Esto hace que aumente la variabilidad de los clusters formados.

119

A pesar de que se concluy que la mtrica basada en seales de beaconing no tiene un

desempeo superior al actualmente demostrado en las redes mviles ad hoc que se basan en
la posicin y la distancia de los nodos, se observ que es una medida que permite suprimir
los equipos de localizacin, lo cual es importante a la hora de implementar este tipo de
redes. Esto se debe a que no siempre se tiene disponibilidad de un servicio de localizacin
apropiado en todos los espacios posibles.

A diferencia de otras tcnicas de clustering diseadas, el algoritmo de clustering que se

propone basado en seales de beaconing, simula de manera ms apropiada las condiciones
reales en las que se podra implementar la comunicacin entre los nodos o usuarios en una
red mvil ad hoc. Un aspecto importante que tiene en cuenta el algoritmo de clustering
basado en seales de beaconing, es que la comunicacin entre dos o ms usuarios es buena
cuando la calidad y la cantidad de informacin que se recibe es igual o aproximadamente
igual a la calidad y la cantidad de informacin que se transmite, con el mnimo de errores o
colisiones posibles.

Uno de los mayores problemas que se presentaron en la realizacin del trabajo, ms

especficamente en la simulacin, fue la carencia de un equipo que soportara jornadas de
simulacin ms largas y con un mayor nmero de nodos, por lo tanto los resultados se
limitaron a la capacidad computacional disponible.

El algoritmo de clustering desarrollado en el presente trabajo de grado, se adapta

dinmicamente a la topologa variable de la red, su estructura presenta capacidad de
cmputo en tiempo real y opera en forma distribuida.

120

7. TRABAJOS FUTUROS Y SUGERENCIAS

Las autoras consideran que pueden resultar interesantes como futuros trabajos de grado
o de investigacin las siguientes ideas:

Implementar el algoritmo de clustering presentado en una plataforma de simulacin

de redes como NS-2 que permita evaluar otras caractersticas del algoritmo.

Utilizar el algoritmo de clustering, para la implementacin de esquemas de

enrutamiento hbrido.

Explorar otro tipo de parmetros que puedan hacer ms eficiente el desempeo del

algoritmo de clustering presentado.

Implementar otros modelos de movilidad para el algoritmo de clustering diseado y

comparar su desempeo en la red.