OBTENCIÓN DE UN MODELO MATEMÁTICO PARA DETERMINAR LA PÉRDIDA DE INFORMACIÓN POR EFECTO DE LA MOVILIDAD EN REDES MANET

OBTENCIÓN DE UN MODELO MATEMÁTICO PARA DETERMINAR LA PÉRDIDA DE INFORMACIÓN POR EFECTO DE LA MOVILIDAD EN REDES MANET

A MATHEMATICAL MODEL TO ESTABLISH INFORMATION LOSSES CAUSED BY NODE-MOBILITY ON MANET NETWORKS

Jaime Andrés Vallejo Avellaneda¹,Jordi Orlando Rico Rodríguez¹,Danilo Alfonso López Sarmiento¹*

¹Universidad Distrital Francisco José de Caldas. Bogotá, Colombia.

*dalopezs@udistrital.edu.co

Recibido: 07/06/2012 - Aceptado: 09/08/2012

RESUMEN

En este artículo se realiza un estudio del efecto de la movilidad de nodos y subredes así como del tamaño de los paquetes sobre el protocolo de capa MAC, IEEE 802.11 utilizado por OPNET para las redes móviles Ad-Hoc. A partir de los resultados de las simulaciones de diferentes escenarios se obtiene un modelo matemático que permite predecir las pérdidas en una topología con subredes móviles para así reducir el tiempo de diseño e implementación de las mismas. Para ello se estudian los resultados de pérdidas de datos obtenidos en una topología con dos subredes móviles y se obtiene un modelo matemático que determina las pérdidas para el protocolo de enrutamiento utilizado.

Palabras clave: MANET, modelo, movilidad, OPNET, pérdidas.

ABSTRACT

This paper presents a detailed study about the effects of node (and sub-network) mobility, as well as packet size, on MAC protocol IEEE 802.11 (as used by OPNET for Ad-Hoc networks). A mathematical model is obtained based on simulation results representing different network scenarios. The model allows predicting packet losses over a mobile-sub-network topology so as to reduce the design and implementation time span. Data-loss-associated results are analyzed over a mobile two-sub-network topology, yielding the mathematical model that serves to estimate packet losses for a particular routing protocol.

Key words: MANET, model, mobility, OPNET, losses.

INTRODUCCIÓN

En la actualidad el uso de tecnologías inalámbricas que faciliten la comunicación es esencial y cada vez se ha buscado desarrollar más tecnologías que lo permitan. Una de ellas es la implementación de redes móviles Ad-Hoc, soportadas sobre el estándar IEEE 802.11 en el software de simulación OPNET.

Sin embargo, la calidad de estas se ve afectada por diferentes factores como lo son la velocidad con la cual se mueven los dispositivos o el tamaño de los paquetes que se está enviando.

Es por ello que se presenta la incomoda tarea de tener que simular cada red que se desea implementar para comprobar que no será un fracaso, lo cual además implica un gasto mayor de tiempo y no permite determinar el comportamiento de la red.

Para evitar esto, se plantea un modelo matemático que describe el comportamiento de las pérdidas en estas redes en base a la velocidad de desplazamiento de los nodos y el tamaño de los paquetes enviados por cada uno.

Este modelo es obtenido a partir de los resultados de pérdida de datos obtenidos de la simulación de una red con 9 casos diferentes. Para ello se utilizó el software de simulación de redes OPNET [1], debido a su gran capacidad para establecer distintos escenarios con diferentes patrones de movilidad y transmisión.

El artículo está organizado de la siguiente forma. Las secciones 2 y 3 presentan respectivamente el estado del arte y un breve marco teórico tanto del tema de MANET, así como el problema de movilidad dado en estas redes.

La sección 4 presenta el desarrollo de la propuesta o topología a simular a partir de la cual se obtendrá el modelo matemático y estará acompañada de los resultados obtenidos mediante las simulaciones.

Posteriormente en la sección 5 se realizará el análisis de estos resultados para el planteamiento del modelo y se da una posible aplicación en la sección 6, a partir de lo cual se obtienen las conclusiones respectivas.

ESTADO DEL ARTE

En los últimos años las redes inalámbricas han tomado gran fuerza en todo el mundo ya que se utilizan en cada vez más áreas de trabajo por su facilidad de acceso a la información de forma rápida y eficaz además que no requieren de ninguna estructura predeterminada. Sin embargo presentan problemas como los mencionados anteriormente.

El protocolo de capa MAC IEEE 802.11, diseñado principalmente para WLAN, sirvió de base para muchos de los avances en protocolos de la capa MAC para MANET. Es por esto que vale la pena estudiar su comportamiento ante distintos factores como los previamente mencionados.

Sin embargo muchos de los estudios [2, 3] se han hecho en torno a los factores que afectan el protocolo durante su funcionamiento más no sobre los parámetros que pueden configurarse por parte del usuario.

Con este artículo se pretende obtener un modelo matemático que permita determinar como se ve afectado el protocolo IEEEE 802.11 al variar cada uno de estos parámetros (movilidad y tamaño de paquetes).

MARCO TEÓRICO

Redes móviles Ad-Hoc (MANET)

Una red MANET es una extensión a las redes Mesh, debido a que es una red auto-configurable, compuesta por nodos inalámbricos móviles cuya comunicación se realiza de forma descentralizada.

Cada uno de los nodos puede moverse arbitrariamente en cualquier dirección y pueden ser teléfonos celulares, computadores portátiles, reproductores MP3, entre otros [4].

Este tipo de redes son útiles en zonas afectadas por desastres donde no existen infraestructuras de comunicación y en entornos militares donde la conexión debe mantenerse siempre a pesar de que uno de los nodos sea destruido y donde los dispositivos son parte de la red sólo durante una sesión de comunicación [5].

Unos de los temas más importantes, es el relacionado con el encaminamiento. Las redes MANET tienen dos tipos de protocolos para la entrega de paquetes conocidos como protocolos proactivos y reactivos.

Ad Hoc On-Demand Distance Vector Routing (AODV)

AODV es un protocolo reactivo el cual guarda tablas de enrutamiento en cada nodo para así evitar que se envíe información innecesaria. Además utiliza enlaces bidireccionales y almacena únicamente la información de los nodos que intervienen en la transmisión.

Las tablas de enrutamiento almacenan información sobre el nodo actual, el nodo siguiente, la métrica que existe al nodo destino y los números de secuencia para las rutas. A partir de esto se conoce el camino a seguir y de esta forma se reduce la sobrecarga.

Los números de secuencia son utilizados con el fin de descartar rutas viejas o inválidas y para evitar la formación de bucles [6].

Efecto de la movilidad

Para las redes que se basan en infraestructura, el punto de acceso es el que tiene la mayor influencia en la entrega de los datos al destino. Las estaciones tienen que compartir información a través del punto de acceso y por lo tanto, su posición hacia los demás no es tan importante. Por lo tanto, la movilidad de los nodos no tiene un efecto importante sobre el protocolo de capa MAC [7].

En el caso de redes MANET, los nodos móviles están en contacto directo unos con otros, ya que pueden ser emisor, receptor y el router. Por ello la movilidad tiene un impacto significativo en el desempeño de su entrega de datos [8].

Cuando el usuario del terminal móvil cambia su posición, puede cambiar la forma en la que se establece el enlace entre los nodos, definiendo nuevas rutas para alcanzar los puntos deseados [8]. Durante el intervalo de tiempo que dura el proceso, los paquetes destinados a un nodo y aquellos transmitidos por éste no pueden ser enrutados. Esto provoca pausas o latencias en la comunicación [9].

La velocidad de movimiento es fundamental dentro del manejo de las rutas por partes de los protocolos, la velocidad promedio de la red determina la movilidad de la red y provoca cambios continuos en la elección de rutas [9].

Efecto del tamaño de paquetes

El tamaño de los paquetes a enviar tiene una gran relevancia a la hora de implementar una red, debido a que al aumentar la cantidad que se envía, crece el Throughput, el cual es el número de paquetes recibidos por el nodo de destino, pero se debe tener presente que el PDR (relación entre los paquetes que llegan satisfactoriamente a su destino con el número total de paquetes transmitidos) aumenta hasta cierto punto a medida que se aumenta la cantidad de paquetes, pero llega un punto en el cual si se sigue incrementando esta cantidad, el PDR comienza a descender [10].

DESARROLLO DE LA PROPUESTA

La topología a simular esta basada en el artículo empirical study of mobility effect on IEEE 802.11 MAC protocol for mobile Ad-Hoc networks [8]. Esta consta de dos subredes similares [11] (Figura 1) compuestas por 7 nodos cada una (Figura 2), los cuales se mueven de tal forma que se van acercando con velocidad constante.

Uno de los nodos es estático y se encuentra ubicado en el centro de la subred. Este transmite a otro nodo estático en el centro de la segunda subred, mientras que los otros nodos dentro decada subred están en movimiento y transmiten datos al nodo central. Estos se encuentran a diferentes distancias del receptor.

Los nodos internos se encuentran en el rango de transmisión de 250m de unos a otros, es decir, cada subred permite a los nodos internos enviar paquetes dentro de la región de la subred. El rango de transmisión para el nodo estático es mayor que los otros debido al hecho de que este tendrá que comunicarse con su par situado en la segunda subred. En este caso el rango de transmisión es de 500m, la configuración general [12] de los equipos se muestra en la (Tabla 1).

Adicionalmente ésta topología contará con 9 escenarios diferente en los cuales se varía la velocidad de movimiento de los nodos y el tamaño de los paquetes que se enviarán.

Se manejarán tres velocidades diferentes y tres tamaños de paquetes diferentes cuyas combinaciones dan lugar a todos los posibles escenarios. Las velocidades trabajadas son 10m/s, 20m/s y 30m/s, mientras que los tamaños de paquetes utilizados son 4096bits, 8192bits y 12288bits. Cada una de las combinaciones se reúne en la (Tabla 2).

Cabe mencionar que se decidió implementar subredes por sus ventajas al ser utilizadas en MANET puesto que cada nodo se debe comportar como un router, manteniendo individualmente las rutas a otros nodos, por lo tanto, sí el número de nodos crece rápidamente, el número de rutas aumentará también impactando tanto en el tamaño de la tabla de encaminamiento como en la búsqueda del camino óptimo [13].

Los resultados de pérdida de paquetes para los distintos casos se aprecian en las figuras 3, 4 y 5.

ANÁLISIS DE RESULTADOS

A partir de los resultados obtenidos en la sección anterior se pretende obtener un modelo matemático que permita determinar el comportamiento de las pérdidas teniendo como parámetros de entrada la velocidad de desplazamiento de los nodos, el tamaño de los paquetes enviados y el tiempo en el cual se está transmitiendo.

Para lograr esto se obtiene inicialmente un modelo para cada una de las curvas obtenidas en simulación y posteriormente son comparados con el fin de determinar un patrón común entre ellos que facilite la obtención de un modelo general.

La obtención estos modelos se realiza mediante el uso de ecuaciones empíricas. Se acondicionan los datos obtenidos con el fin de aproximarlos a una línea recta y una vez logrado esto se determina la ecuación de la misma. Los valores de pendiente y punto de corte son finalmente remplazados en el modelo correspondiente.

Para curvas como las obtenidas el modelo más adecuado corresponde a la ecuación (1).

De acuerdo a este modelo, los nuevos ejes para cada curva se describen mediante la ecuación (2) y (3).

Una vez obtenida la línea recta con su ecuación correspondiente (y=Px+C) se procede a calcular los valores para el modelo de acuerdo a las ecuación (4), (5) y (6).

Los modelos obtenidos son los siguientes:

Paquetes de 4096 bits

Paquetes de 8192 bits

Paquetes de 12288 bits

Cada uno de los modelos obtenidos da como resultado una aproximación con un error inferior al 4%.

Es fácil apreciar que todos los modelos comparten el mismo numerador mientras que el denominador varía en cada caso, por lo cual será el término a estudiar.

Al comparar cada uno de los denominadores se puede apreciar que corresponden a ecuaciones de rectas (y=Px+C) en donde su pendiente (P) permanece muy similar frente a los cambios en velocidad, mientras que si se ve afectada por el cambio en el tamaño de los paquetes. Por lo tanto se analizará la forma en la que varia la pendiente en base a este valor.

Para esto se grafican los valores promedio de pendiente en los tres casos y se halla el modelo de este comportamiento (Figura 6).

Nuevamente se utilizo el modelo descrito mediante la ecuación (1) con el cual se obtiene el modelo descrito por ecuación (7).

Donde P corresponde al tamaño de los paquetes.

Volviendo a los nueve modelos anteriores, los puntos de corte en el denominador (C) no tienen ninguna relación aparente, lo cual indica que se ven afectados por los dos parámetros de entrada.

Para facilitar el análisis se realiza la gráfica de estos valores donde se decidió mantener constante la velocidad, modificando únicamente el tamaño de los paquetes enviados.

De acuerdo a la Figura 7 se aprecia la forma en la que varía este valor de acuerdo al tamaño de paquetes. Las tres curvas obtenidas son muy similares diferenciándose únicamente por el nivel que se suma a cada una de ellas el cual estaría dado entonces por la velocidad puesto que no hay más parámetros que puedan afectar.

Para asegurar que las curvas no se ven afectadas por el tamaño de los paquetes sino que tienen la misma forma, se debe verificar si cada uno de los puntos difiere únicamente por el nivel dado debido a la velocidad. Para esto se toman todos los puntos de corte de un solo tamaño de paquete y se analiza el aumento con respecto a la velocidad.

Paquetes de 4096 bits

Paquetes de 8192 bits

Paquetes de 12288 bits

Los valores obtenidos son muy cercanos indicando esto que el aumento es lineal, por lo cual se puede afirmar que las tres curvas tienen el mismo modelo.

Al igual que en los casos anteriores se toma la ecuación (1) por su cercanía a una línea recta y se obtiene un nuevo modelo descrito por la ecuación (8).

Donde P corresponde al tamaño de los paquetes. Cabe aclarar que este modelo tan solo establece la forma de las curvas presentadas en la Figura 7. El nivel que se suma a estas es debido a la velocidad y será de forma lineal, por lo cual su modelo será de la forma y=Px+C (Figura 8).

Y su ecuación se describe mediante la ecuación (9)

Donde V corresponde a la velocidad de desplazamiento de los nodos.

Con la ecuación (9) se procede a unir todo para obtener el modelo final (ecuación (1))

Donde

Para comprobar la efectividad de este método se verifican cada uno de los resultados obtenidos en la simulación.

Los resultados obtenidos se presentan en las figuras 9, 10 y 11.

Tamaño de paquetes = 4096 bits

Velocidad de desplazamiento = 30 m/s, Error = 3,9%

Tamaño de paquetes = 8192 bits

Tamaño de paquetes = 12288 bits

Velocidad de desplazamiento = 10 m/s, Error = 4,1%

Se puede apreciar que las aproximaciones obtenidas presentan un error inferior al 7%, con lo cual se pueden tomar como válidas.

APLICACIÓN

El gran beneficio del modelo obtenido se ve reflejado en la obtención de una curva estimada de las pérdidas en una red MANET que implemente subredes como las presentadas en el trabajo, ingresando los parámetros presentados a lo largo del artículo.

Esto permitirá reducir el tiempo de diseño de redes puesto que evitará tener que simular cada opción de velocidad de desplazamiento de nodos y tamaño de paquetes enviados.

CONCLUSIONES

Se ha podido apreciar que los distintos factores al momento de transmitir entre subredes inalámbricas móviles, como los tratados en el artículo, afectan a la red aumentando o disminuyendo la pérdida de datos transmitidos.

Este comportamiento se representó a través de un modelo matemático con el cual se pudo comprobar que al aumentar el tamaño de los paquetes enviados, aumenta de igual forma la cantidad de datos perdidos.

Sin embargo, los resultados varían a medida que los nodos se desplazan en la red. Si se proporciona una adecuada distancia de transmisión y una velocidad de desplazamiento de los nodos igualmente adecuada, las pérdidas se verán reducidas puesto que cada estación tardará menos en entrar en el rango de transmisión de otras.

No obstante el análisis realizado aplica únicamente para topologías que incluyan subredes móviles. Si se desea determinar el comportamiento de las pérdidas para un conjunto de nodos móviles sobre un escenario diferente, se debe realizar un análisis de los nuevos resultados obtenidos ya que el modelo matemático seguramente diferirá.

Referencias Bibliográficas

[1] L. Peterson, D. Bruce; Computer networks, a system approach, 3ra edición, 1999.

[2] S. Khurana, A. Kahol, A. Jayasumana; Effect of hidden Terminals on the performance of IEEE 802.11 MAC protocol, LCN ’ 98 proceedings, p.p: 12-20, 1998.

[3] R. Samir, R. Castañeda, J. Yan, R. Sengupta; Comparative performance evaluation of routing protocols for mobile, Ad hoc networks, In 7th Int. Conf. on Computer Communications and Networks (IC3N), p.p: 153–161, October 1998.

[4] S. Corson, J. Macker; Mobile Ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations, University of Maryland., Naval Research Laboratory. Enero, 1999.

[5] J. Rico, J. Vallejo; Comparación de protocolos de enrutamiento para redes MANET, Bogotá. Octubre, 2011.

[6] C. Perkins, E. Belding-Royer, S. Das; Ad hoc on-demand distance vector (AODV) routing, RFC 3561, Nokia Research Center, University of California, Santa Bárbara., University of Cincinatti, Julio, 2003.

[7] H. Jasani, N. Alaraje; Evaluating the performance of IEEE 802.11 network using RTS/CTS mechanism, in Electro/Information Technology. IEEE International Conference on. Chicago, 2007.

[8] J. Razfar, J; Empirical study of mobility effect on IEEE 802.11 MAC protocol for mobile Ad-hoc networks, California, 2010.

[9] P. Andino; Estudio comparativo de protocolos de ruteo en redes Ad hoc aplicado a redes móviles, 2011.

[10] Z. Ismail, R. Hassan; Effects of packet size on AODV routing protocol implementation in homogeneous and heterogeneous MANET, in IEEE Computational Intelligence, Modelling and Simulation (CIMSiM), Third International Conference on. Langkawi, 2011.

[11] J. López, J. Barceló, J. García-Vidal; Ventajas de usar subredes en una red Ad-hoc con nodos móviles, Departamento de Arquitectura de Computadores, Universidad Politécnica de Cataluña (UPC). XV Jornadas Telecom I+D, Noviembre, 2005.

[12] Computer networks simulation using OPNET Modeler, University of Tehran, ECE Department Computer Networks Course, Otoño, 2007.

[13] Tutorial OPNET Modeler, Departamento Académico de Sistema Digitales, México, Otoño 2005.