Resumen— Actualmente los servicios sobre redes MANET

(Mobile Ad Hoc Networks) gozan de gran popularidad, y los servicios multimedia como puedan ser las aplicaciones de transmisión de vídeo en tiempo real son cada vez más demandados. Así, es necesario proveer de calidad de servicio (QoS) extremo a extremo sobre este tipo de redes, a pesar de que supone un gran reto debido a las efímeras estructuras que poseen. MM-DSR (Multipath Multimedia Dynamic Source Routing) es un protocolo de encaminamiento multicamino basado en DSR que trabaja junto con un algoritmo de capa cruzada “cross-layer” capaz de proveer de calidad de servicio para múltiples fuentes de vídeo sobre redes ad hoc IEEE 802.11b. Los puntos débiles del sistema que utiliza el protocolo estándar DSR y la especificación 802.11b se han analizado, y el trabajo realizado se ha enfocado para mejorar la tasa neta de datos recibidos y la calidad percibida por el usuario final. El rendimiento de aplicaciones de flujos de vídeo “video-streaming” se ha mejorado bajo condiciones de alta carga de tráfico sobre redes móviles ad hoc.

Palabras clave— MANETs, protocolo de encaminamiento

multicamino preparado para QoS, provisión de QoS extremo a extremo.

I. INTRODUCCIÓN NA red móvil ad hoc (MANET) es una red de comunicaciones formada espontáneamente por un

conjunto de dispositivos móviles inalámbricos que son capaces de comunicarse entre sí siguiendo una similitud a las redes peer-to-peer (P2P), sin la necesidad de una infraestructura de red fija o gestión administrativa centralizada.

Además, debido a que el alcance de transmisión de los dispositivos inalámbricos es limitado, pueden llegar a ser necesarios nodos intermedios para transferir datos de un nodo

Este documento de investigación está soportado por el proyecto español SECONNET (CICYT-TSI2005-07293-C02-01), beca CONACYT (México), Fundación Carolina (España), PROMEP-UAQ (México), beca Alban E05D052898MX y beca UPC Recerca.

V. Carrascal está trabajando sobre QoS en redes ad hoc en la Universidad Politécnica de Cataluña (UPC), C/ Jordi Girona 1-3 08034, Barcelona (vcarrascal@entel.upc.edu)

G. Díaz es profesor de la Facultad de Informática de la Universidad Autónoma de Querétaro (UAQ) y está trabajando sobre diseños de capas cruzadas para redes ad hoc en la UPC (gdiaz@entel.upc.edu)

A. Zavala está trabajando sobre el modelado y la evaluación de QoS en redes móviles en la UPC (azavala@entel.upc.edu)

M. Aguilar es profesora titular del Departamento de Ingeniería Telemática de la ETSETB en la UPC (maguilar@entel.upc.edu)

a otro a través de la red. Por ello, en una red ad hoc cada nodo puede operar como fuente, destino o encaminador.

Los nodos móviles son libres para moverse arbitrariamente, produciendo frecuentes cambios en la topología de la red. Además, las variaciones en el canal radio y las limitaciones de energía de los nodos pueden producir frecuentes cambios en la topología y en la conectividad. Consecuentemente, las MANET deben adaptarse dinámicamente para ser capaces de mantener las conexiones activas a pesar de estos cambios.

Estas redes son principalmente útiles en aplicaciones militares y otras de carácter táctico, como rescates de emergencia o misiones de exploración. Por otro lado, en aplicaciones comerciales (p.ej. conferencias, cursos de enseñanza, visitas a museos, turismo en ciudades, aplicaciones peer to peer, e-gaming, etc) es donde realmente hay una necesidad para servicios de comunicación ubicua. El hecho de poder ofrecer ciertos niveles de calidad de servicio (QoS) en redes MANET sigue siendo un tema abierto para la comunidad investigadora, y supone un reto muy interesante dadas las dificultades que conlleva.

Específicamente, los servicios de tiempo real necesitan especial atención debido a que la naturaleza dinámica de estas redes hace difícil aplicar una gestión tradicional de QoS, aunque pueden utilizarse algunas técnicas basadas en IntServ y DiffServ.

Dado que la provisión de QoS no depende de una única capa de red sino de un esfuerzo coordinado desde todas las capas, se hace necesario desarrollar soluciones dinámicas basadas en una aproximación de capa cruzada “cross-layer” que tenga en cuenta las diferentes especificaciones de las redes ad hoc. Una arquitectura apropiada para ofrecer QoS en redes ad hoc debe asegurar la cooperación entre todos los componentes relacionados con la provisión de QoS (por ej.: señalización, encaminamiento y mecanismos de acceso al medio (MAC, Medium Access Control). Nuestro trabajo está centrado básicamente en ofrecer ciertos niveles de QoS a aplicaciones de vídeo en tiempo real sobre redes MANET, tratando de mejorar el rendimiento en situaciones multiusuario con altas cargas de tráfico en la red.

El resto del artículo está organizado de la forma siguiente: en el apartado II se comentan brevemente las diferentes propuestas de encaminamiento multicamino que existen en la actualidad. En el apartado III se explica el funcionamiento de MM-DSR y las métricas usadas. Seguidamente, en el apartado IV se explican los diferentes esquemas multicamino utilizados en este trabajo. Finalmente, en el apartado V se muestran las

V. Carrascal, Student IEEE, G. Díaz, Student IEEE, A. Zavala, Student IEEE, M. Aguilar

MM-DSR: Encaminamiento multicamino con QoS para múltiples fuentes multimedia sobre

redes móviles ad hoc

U

448 IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 6, OCTOBER 2007

simulaciones realizadas y los resultados obtenidos y en el VI se comentan las conclusiones y las líneas futuras para seguir desarrollando este protocolo.

II. ENCAMINAMIENTO MULTICAMINO Actualmente existen varias propuestas de protocolos de

encaminamiento que explotan la diversidad de caminos sobre redes ad hoc. Muchas de estas modificaciones son extensiones de protocolos de encaminamiento monocamino, como son AODV (Ad hoc On-Demand Distance Vector) o DSR (Dynamic Source Routing). En general, los algoritmos de encaminamiento ad hoc tienen la habilidad de descubrir más de un camino, si es que existe. Esto se debe principalmente a la característica de amplia difusión “broadcast” de los interfaces inalámbricos y a los mecanismos de inundación usados para el descubrimiento de caminos. Los protocolos de encaminamiento monocamino de redes ad hoc activan y mantienen un único camino para la transmisión de datos entre emisor y receptor, usualmente el camino más corto o el que optimiza otra métrica o conjunto de métricas.

Dentro de estos protocolo los de mayor interés son los capaces de encontrar todos los posibles caminos entre los nodos fuente y destino. Múltiples caminos entre emisor y receptor pueden fortalecer la conexión permitiendo una rápida recuperación del camino en caso de fallo. La diversidad de caminos también hace posible gestionar aplicaciones que requieran unos recursos mínimos que no pueden ser provistos por un único camino (p.ej. ancho de banda), transmitiendo datos a través de varios caminos simultáneamente desde la fuente al destino. Además, el encaminamiento multicamino puede activar mecanismos de equilibrado de carga, lo cual es una característica importante para aplicaciones multimedia sobre MANET, donde los recursos son muy limitados. De esta manera, las aplicaciones pueden obtener mejor capacidad de transferencia, así como disminuir el retardo extremo a extremo.

Las técnicas de encaminamiento multicamino y de equilibrado de carga se benefician de la existencia de múltiples descriptores de flujos de vídeo en redes ad hoc, haciendo posible otorgar ciertos niveles de QoS y reforzando la seguridad de la transmisión [1]. Sin embargo, el mantenimiento de múltiples caminos entre dos nodos comunicándose extremo a extremo consume más recursos de red y del nodo, lo cual puede llegar a ser un problema crítico en entornos MANET. Propuestas que usan encaminamiento multicamino y balanceo de carga pueden ser [1], [3], [4], [10], pero muchas de ellas sólo están focalizadas en un único parámetro (p.ej. ancho de banda o retardo). Nuestro algoritmo tiene en cuenta varios parámetros de calidad de servicio y heurísticamente busca un conjunto de caminos que puedan proveer del nivel de QoS requerido por el usuario de una manera flexible y dinámica.

III. PROTOCOLO MM-DSR En esta sección presentamos un protocolo dotado de un

algoritmo capaz de proporcionar QoS a aplicaciones de flujo de vídeo “video-streaming” sobre redes ad hoc. MM-

DSR.11b (Multipath Multimedia Dynamic Source Routing based on IEEE 802.11b networks) está basado en el protocolo reactivo DSR (Dynamic Source Routing) para redes ad hoc. En este trabajo se ha desarrollado la versión sobre redes de la especificación IEEE 802.11b. El vídeo se distribuye usando los protocolos RTP/RTCP (Real Time Protocol/Real Time Control Protocol) sobre UDP (User Datagram Protocol) como protocolos de transporte. Cada cuadro de vídeo se transporta en uno o varios paquetes RTP (dependiendo del tamaño del cuadro puede ser necesario fragmentarlo en varios paquetes). En ningún caso se transmite más de un cuadro en un paquete RTP.

En primer lugar, tenemos los requerimientos del cliente que especifican los parámetros de QoS y los valores necesarios de diversos parámetros para conseguir la calidad de imagen requerida. Estos parámetros de QoS son el ancho de banda mínimo esperado (BWMIN), el porcentaje máximo de pérdidas de datos (pMAX), el retardo máximo (dMAX) y la variación del retardo máxima (delay jitter, (jMAX):

{ } ( )_ , , , 1MIN MAX MAX MAXuser req BW p d j≡ Adicionalmente, es conveniente tener en cuenta la

naturaleza altamente dinámica de las MANET (movilidad de nodos, variaciones de los canales radio de los nodos, energía limitada). Con este objetivo, es necesario definir algunos parámetros de QoS adicionales. Dichos parámetros no pueden ser negociados ya que no están relacionados a ningún usuario específico, sino a la red móvil ad hoc. De esta manera, se han definido dos nuevos parámetros: métrica de fiabilidad (Reliability Metric, RM) y métrica de movilidad (Mobility Metric, MM). La RM de cada camino da una idea de la probabilidad de error de transmisión de un paquete por ese camino.

De una manera similar, la métrica de movilidad (MM) total de un camino se calcula en cada iteración del algoritmo desde la métrica de movilidad agregada relativa, definida en [2]. La idea bajo esta métrica es la de seleccionar los caminos más estables (basándonos en la movilidad de los nodos) los cuales deberán ser escogidos preferentemente frente a los caminos más inestables. Éste es un indicador más adecuado respecto a la movilidad relativa que fijarnos única y exclusivamente en la distancia pura o el ancho de banda, debido a las características especiales del entorno de las redes ad hoc.

Como se sugiere en [3], asumimos que la topología de la red se mantiene sin cambios entre dos iteraciones sucesivas del algoritmo para poder alcanzar una solución consistente. Hemos considerado, tras muchas simulaciones en diferentes tipos de escenarios, que una frecuencia de 10 segundos para la iteración del algoritmo es un valor adecuado, para las características de movilidad y la distancia de transmisión de los nodos en una red ad hoc.

A. Paquetes de control Para poder llevar a cabo un control total sobre el estado de la red ad hoc en la que se están transmitiendo los flujos de vídeo, se han creado dos tipos de paquetes o mensajes que son procesados por los nodos según sea necesario. Existen dos tipos:

CARRASCAL FRÍAS et al.: MM-DSR: MULTIPATH QOS 449

• Mensajes sonda (Probe Messages, PM) • Mensajes hola (Hello Messages, HM)

Los PM se envían únicamente entre fuente y destino respecto de la transmisión de flujo de vídeo, y sólo se envían una vez por cada iteración del algoritmo. Los HM se transmiten entre nodos vecinos de la red, independientemente de si son nodos fuente o destino o simples nodos intermedios. No es requisito imprescindible que formen parte de uno de los múltiples caminos hallados por MM-DSR. A continuación se explican en detalle estos dos tipos de paquetes. 1) Mensajes sonda

Justo al inicio de la iteración del algoritmo, se envían mensajes sonda (Probe Messages, PM) desde la fuente al destino a través de todos los D caminos descubiertos por el algoritmo de encaminamiento multicamino que incluye MM-DSR. Estos caminos se almacenan en la caché al inicio de la comunicación. Los PM recogen información de la red que permite la estimación de seis parámetros para cada camino k y cada iteración del algoritmo i: porcentaje de pérdidas (pi

k), retardo (di

k), ancho de banda disponible extremo a extremo (BWei

k), variación del retardo “delay jitter” (dik), métrica de

fiabilidad “Reliability Metric” (RMik), y métrica de movilidad

“Mobility Metric” (MMik). Estas métricas de calidad

deservicio caracterizan el estado del camino k en la iteración i del algoritmo sobre cada uno de los D caminos disponibles, y se representa como sigue:

( ) { , , , , , } 2i i i i i i ik k k k k k kpath BWe p d j RM MM≡

siendo BWeik el ancho de banda mínimo residual encontrado a

lo largo de todos los nodos en esa ruta. Todos estos valores se recogen por MM-DSR y se actualizan en el PM en cada uno de los nodos intermedios. Una vez que se llega al destino estos valores son procesados convenientemente para enviarlos al nodo origen. Se genera un mensaje respuesta al mensaje sonda (Probe Message Reply, PMR) que lleva la información necesaria para que en el origen se puedan establecer calificaciones a cada uno de los caminos descubiertos por MM-DSR, y así poderlos ordenar y seleccionar de mayor a menor calificación. Los caminos que obtengan la mayor calificación serán los usados para el encaminamiento de los paquetes usando técnicas multicamino. El número de caminos a escoger dependerá del esquema multicamino que estemos usando. Tras numerosas pruebas, hemos constatado que no tiene sentido usar un número de caminos mayor a 3 en técnicas multicamino para vídeo en tiempo real sobre redes ad hoc, ya que la ganancia que se obtiene en términos de Calidad de Servicio no justifica el incremento de tráfico de control generado para gestionar un gran número de caminos para una conexión. 2) Mensajes hola Los mensajes hola se utilizan exclusivamente para el cálculo de dos parámetros creados para el algoritmo: la métrica de fiabilidad (RMi

k) y la métrica de movilidad, (MMik). Estos

mensajes se envían una vez por segundo entre nodos vecinos, con tal de obtener un continuo seguimiento de la potencia de

señal recibida por los mismos. Su funcionamiento consiste en que un nodo envía un mensaje hola a todos sus vecinos una vez por segundo. A continuación, cada uno de estos nodos vecinos calcula la SINR o señal/interferenciaa más relación de potencia de ruido “Signal to Interference plus Noise Power Ratio” percibida debido a la recepción de este mensaje. Al estar trabajando en un entorno de simulación, tuvimos también que simular el ruido del canal. Finalmente se optó por añadir un ruido fijo a la señal recibida en función de la velocidad de transmisión de los nodos, como se indica en [9]. Tanto el valor de la potencia recibida por el nodo vecino, como el valor de la SINR se almacenan en un mensaje respuesta hola (Hello Message Reply, HMR) que se envía de nuevo al nodo origen del paquete hola. En el origen se utilizarán esos dos valores para el cálculo de RMi

k y MMik como se verá en los apartados

III-C y III-D respectivamente.

B. Obtención de ikp , i

kd y ikj

A continuación se explica la forma de obtener los valores de pérdidas, retardo y de variación de retardo (pi

k, , dik,, ji

k) para cada ruta k en cada iteración i del algoritmo. Con la información recogida de los mensajes sonda, el destino inserta en el paquete respuesta al mensaje sonda (Probe Message Reply) valores muestra para las pérdidas pk

i_sample, retardo dk

i_sample y de variación de retardo jki_sample para cada camino k,

y lo envía hacia el nodo fuente, como muestra la Fig. 1. Como este paquete generado en el destino es muy importante para mantener en buenas condiciones las transmisiones de flujo de vídeo, se ha decidido enviar una copia del mensaje sonda respuesta por cada uno de los k caminos descubiertos, de tal manera que se puedan tener más posibilidades de recibir esta información en la fuente. Cabe mencionar que dado el reducido tamaño de este paquete y la baja frecuencia a la que se envía (una vez por iteración) la sobrecarga en la que se incurre es despreciable.

Fig. 1: Envío de mensajes sonda.

Con estos valores de muestra, el nodo fuente calcula pik, di

k y ji

k aplicando un filtro EWMA (Exponentially Weighted Moving Average) para cada uno de ellos con un valor bajo de coeficiente α, para así tener más en cuenta el histórico de valores frente a los instantáneos. Se ha escogido un valor α = 0,125, para permitir evolucionar a EWMA de una manera suave.

( )( ) ( )( )

1 _

1 _

1 _

1

1 3

1

i i i samplek k k

i i i samplek k k

i i i samplek k k

p p p

d d d

j j j

α α

α α

α α

−

−

−

= − ⋅ + ⋅

= − ⋅ + ⋅

= − ⋅ + ⋅

450 IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 6, OCTOBER 2007

donde pki-1, dk

i-1 y jki-1 son los valores calculados en la iteración

previa. Más adelante se aplicarán unas calificaciones a cada camino dependiendo de los valores obtenidos en estos parámetros.

C. Métrica de fiabilidad, ikRM

Proponemos calcular una medida de rendimiento de la totalidad de cada camino a partir de una medida de la SINR entre nodos vecinos consecutivos del camino. Para cada iteración i del algoritmo y cada camino k obtenemos los valores SINRj

k,i de cada nodo j respecto al nodo j-1, en el camino de bajada desde la fuente al destino, y asignamos unas calificaciones xj

k,i para cada nodo j de acuerdo a ciertos valores o rangos heurísticos, de la forma siguiente:

( )

, ,

, ,

, ,

, ,

25dB, buen enlace, 3

15dB < 25dB, 2

10dB < 15dB, 1

< 10dB, enlace malo, 0 4

k i k ij j

k i k ij j

k i k ij j

k i k ij j

If SINR x

If SINR x

If SINR x

If SINR x

≥ =

≤ =

≤ =

=

Calculamos la calificación media del camino entero k a partir de la media geométrica de todas las calificaciones parciales xj

k,i de cada nodo j del camino k. Lki se corresponde con el

número de enlaces de cada camino k. De esta manera, asignamos unos valores heurísticos en forma de notas a la métrica de fiabilidad RMk

i para cada uno de los k caminos disponibles, de manera que cuanto mayor sea RMk

i mejor es el camino k en cuanto a la fiabilidad:

( )

,

1

,

1

,

1

,

1

( ) 2, 3

1,5 ( ) 2, 2

1 ( ) 1,5, 1

( ) 1, 0 5

iki

k

iki

k

iki

k

iki

k

j Lk i iL

j kj

j Lk i iL

j kj

j Lk i iL

j kj

j Lk i iL

j kj

If x RM

If x RM

If x RM

If x RM

=

=

=

=

=

=

=

=

> =∏

< ≤ =∏

< ≤ =∏

≤ =∏

D. Métrica de movilidad, ikMM

Cada nodo X detecta la energía de la señal recibida RxPγY→X respecto a su vecino Y (el cual pertenece a uno de los caminos descubiertos de fuente a destino) de sucesivas transmisiones de paquetes (mensajes periódicos tipo “Hello”). Entonces, el nodo X calcula la métrica de movilidad relativa respecto a Y,MX

rel,i(Y). Una vez que este valor se ha devuelto al nodo origen del mensaje hola, cada nota local se calcula así:

( )

( )

,0 1

2

10 1

var

Pr10 log 6Pr

mi rel iX X j j

iY XiY X

M M Y

RxERx

=

→−→

⎡ ⎤= =⎣ ⎦

⎡ ⎤⎛ ⎞⎢ ⎥= ⋅⎜ ⎟⎢ ⎥⎝ ⎠⎣ ⎦

Un valor bajo para Mxi significa que el nodo X es

relativamente menos móvil respecto a sus m vecinos, mientras que un valor alto indica que el nodo X es mucho más móvil que sus vecinos. Un camino cuyos nodos tengan una movilidad relativa agregada más baja será escogido antes frente a otros caminos cuyos nodos presenten un valor alto de movilidad. Entonces, el nodo X almacena cada valor para cada uno de sus Y nodos vecinos. Así, la próxima vez que un mensaje sonda llegue a este nodo X, añadirá este valor actual de la nota de la métrica de movilidad a la nota global de la métrica de movilidad de cada camino (MMk

i) de la siguiente manera: para cada camino k obtenemos los valores MX

i de cada nodo X perteneciente al camino de los mensajes sonda usando (6). Después de esto, asignamos notas de acuerdo a ciertos rangos heurísticos, como sigue:

( )

,

,

,

,

0,02, muy poco movimiento, 3

0,02 < 0,08, baja movilidad, 2

10dB < 0,5, alta movilidad, 1

0,5, muy alta movilidad, 0 7

i k iX j

i k iX j

i k iX j

i k iX j

If M MM

If M MM

If M MM

If M MM

< =

≤ =

≤ =

≥ =

Finalmente, sumamos todas las calificaciones parciales de

todos los Lki nodos del camino entero k. Seguidamente

obtenemos el valor medio de MMki dividiendo por el número

total de saltos en el camino, obteniendo así una medida de la movilidad de este camino k, MMk

i.

( ),

1 8

ikj L

k ij

jik i

k

MMMM

L

=

=∑

=

E. Salidas del algoritmo

Al inicio del servicio, un CAC (Call Admission Control) se ejecuta para consultar si se puede admitir la nueva conexión protegiendo las sesiones que actualmente están en curso. Podemos saber el ancho de banda que ha quedado disponible respecto a la iteración previa del algoritmo, denominado BWa

i-

1. El ancho de banda mínimo requerido para transmitir el flujo de vídeo actual (BWMAX_stream) es la tasa de pico de la totalidad del flujo. Nótese que el ancho de banda requerido para transmitir flujos de vídeo sobre MANET debe ser bajo, debido a los limitados recursos disponibles. Es más, los usuarios se mueven mucho y sus dispositivos son pequeños y con baterías de baja capacidad. Consecuentemente, usuarios que suelen requerir altos niveles de calidad, pueden llegar a verse afectados fácilmente por este tipo de circunstancias. Para proceder con el servicio, debemos comprobar si BWMAX_stream

CARRASCAL FRÍAS et al.: MM-DSR: MULTIPATH QOS 451

no excede el ancho de banda disponible BWai-1 y satisface el

ancho de banda requerido por el cliente BWMIN:

( )1_ 9i

MIN MAX stream aBW BW BW −≤ ≤

El ancho de banda que queda disponible para la siguiente iteración es:

( )1_ 10i i

a a MAX streamBW BW BW−= − Obviamente, el ancho de banda disponible se actualiza cada

vez que una conexión se corta o termina. A partir de (2) seleccionamos el conjunto de caminos válidos para la iteración actual i, denominada PathSeti, que satisface los requerimientos del cliente expresados en (1):

( )( ) ( ) ( )

( )

If _

11

ik ek MIN

k MAX k MAX k MAX

i

path state BW BW

p p d d j j

include path k in PathSet

⇔ ≥ ∩

∩ ≤ ∩ ≤ ∩ ≤ ⇒

⇒

Cabe remarcar que encontrar un camino óptimo puede llegar a ser un problema sin solución si implica dos o más métricas aditivas (p.ej. retardo, coste) [4]. Aquí esto no es un problema debido a las características de las aplicaciones de vídeo en tiempo real. Éstas son suficientemente flexibles como para que el retardo inicial no sea un impedimento muy severo, siempre y cuando la variación del retardo se mantenga estable. Un esquema de encaminamiento multicamino equilibrará la carga entre varios caminos. Así, nuestro algoritmo aplica estos esquemas y ayudará a minimizar las pérdidas y a mantener estable la variación del retardo.

El PathSeti se ordena dependiendo de la relación entre los requisitos del cliente (1) y las métricas de QoS de cada uno de los D caminos disponibles del protocolo encaminador MM-DSR (2). El algoritmo califica cada camino k según el ancho de banda (MBWk

i), variación del retardo (Mjki), retardo (Mdk

i), y pérdidas (Mpk

i), calculadas con (12). Consideramos una calificación máxima de dos para el camino k cuando el ancho de banda disponible (BWek

i)excede en un 20% el ancho de banda requerido por el usuario (BWmin), así usamos 1,2 en (12). Si BWek

i está cerca de BWmin , la nota es 1. Finalmente, si BWek

i es BWmin, la nota es 0. De la misma manera, en (12) tenemos una ecuación común para calcular los valores para vk

i, que corresponde a Mpk

i , Mdki, Mjk

i respectivamente. Estos valores son las notas correspondientes a cada camino k: probabilidad de pérdidas, retardo, y variación del retardo. vMAX se corresponde con los requisitos del cliente para los parámetros expresados en (1). Es decir, vMAX equivale a pMAX , dMAX, jMAX respectivamente.

El algoritmo también considera las métricas de confianza (RMk

i) y movilidad (MMki), calculadas sobre cada camino k

durante cada iteración i, para ordenar los D caminos disponibles. Los valores de RMk

i se han asignado heurísticamente a cada camino k como se muestra en (6). Dan una medida de la calidad media del enlace junto con la estabilidad del mismo. La MMk

i expresada en (7) mide la movilidad agregada relativa del camino, dando una idea de la movilidad de los nodos respecto a sus vecinos en cada camino k.

( )

> 1,2 2 < 1,2 1

= 0

< 0,4 20,4 0,8 1 12

> 0,8 0

ik MIN

i iMIN k MIN k

ik MIN

ik MAX

i iMAX k MAX k

ik MAX

BWe BWIf BW BWe BW MBW

BWe BW

v vIf v v v Mv

v v

⎛ ⎞∗ ⎛ ⎞⎜ ⎟ ⎜ ⎟≤ ∗ ⇒ =⎜ ⎟ ⎜ ⎟

⎜ ⎟⎜ ⎟ ⎝ ⎠⎝ ⎠⎛ ⎞∗ ⎛ ⎞⎜ ⎟ ⎜ ⎟∗ ≤ ≤ ∗ ⇒ =⎜ ⎟ ⎜ ⎟

⎜ ⎟⎜ ⎟∗ ⎝ ⎠⎝ ⎠

Una vez que el conjunto de caminos válidos PathSeti (que cumplen los requisitos del cliente) para la iteración actual i se ha establecido (11), el algoritmo ordena estos caminos de acuerdo a las siguientes reglas:

• El PathSeti se ordena según la suma RMki + MMk

i decrece, para cada camino k. Así, hemos considerado primero las métricas de fiabilidad y movilidad para ordenar los caminos.

• Si hay coincidencias tenemos en cuenta la nota obtenida por el parámetro del ancho de banda disponible, MBWk

i, de mayor a menor. • Si continuamos con coincidencias, se considera la

suma Mpki + Mjk

i según va decreciendo. En este caso hemos tenido en cuenta la probabilidad de pérdidas y la variación del retardo.

• Finalmente, si siguen existiendo coincidencias, se tiene en cuenta la nota referente al retardo de transmisión asociado a los caminos, Mdk

i. Es ahora cuando se seleccionan los N primeros caminos del conjunto de caminos ordenados PathSeti, donde N se corresponde con el número de caminos simultáneos que se desean utilizar entre fuente y destino.

IV. ESQUEMAS MULTICAMINO Una vez explicado el algoritmo que define los diferentes

esquemas de transmisión sobre los cuales trabaja nuestro encaminamiento multicamino, vamos a explicar los diferentes tipos de flujos de vídeo que maneja el esquema. El vídeo transmitido en nuestra arquitectura es MPEG-2 sin audio. El sistema envía flujos de vídeo que pueden tener diferentes calidades. Estos flujos MPEG-2 se han codificado a partir de una secuencia de vídeo original de mayor calidad.

El flujo de vídeo MPEG-2 está formado por GoPs (Group of Pictures) que mantienen una estructura de cuadros (frames) dada. Existen tres tipos de cuadros:

• Cuadros I: el principal en la estructura MPEG-2. Son los encargados de llevar la información más relevante de las imágenes, codificando redundancia espacial. Sólo existe un cuadro I por cada GoP.

• Cuadros P: codifican redundancia temporal y sólo llevan información relativa a las diferencias respecto al último cuadro I. Su tamaño es un 20% respecto al tamaño medio de un cuadro I.

• Cuadros B: también codifican redundancia temporal y sólo llevan información relativa a las diferencias respecto al último cuadro P. Su tamaño es un 10\%

452 IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 6, OCTOBER 2007

respecto al tamaño medio de los cuadros I. Son menos importantes que los cuadros P para el proceso de decodificación de la secuencia de vídeo.

Existen ciertas estructuras de GoP que son más estándares que otras, de las que una de ellas la "IBBPBBPBBPBBPBB", que es la estructura utilizada para codificar el vídeo original usado en las simulaciones. A continuación se explica la forma en la que el sistema distribuye cada uno de estos cuadros en función de su relevancia y del número de caminos utilizados en el esquema multicamino.

Fig. 2: Esquemas multicamino hasta N=3.

Para cada esquema multicamino el sistema es capaz de enviar diferentes flujos formados por varias combinaciones de los cuadros anteriormente comentados (2). Los flujos principales están compuestos sólo por cuadros tipo I, que son la única clase de flujos que pueden ser autodecodificados. Al ser los flujos más importantes, los enviamos por el mejor camino obtenido por el algoritmo en la última iteración. El objetivo principal es el de proteger estos cuadros I otorgándoles alta prioridad, debido a su influencia directa en la calidad que finalmente recibirá el usuario. Los otros flujos (formados por cuadros tipo P y B) son flujos que no pueden ser autodecodificados por sí mismos ya que necesitan el soporte de los cuadros I. Los cuadros P y B mejoran la calidad del vídeo de la secuencia decodificada en el lado del receptor. En la Fig. 2 se observa el tipo de cuadros que componen cada flujo. Estos tres esquemas están diseñados de tal manera que siempre se envían los cuadros más importantes a través de los mejores caminos.

La Fig. 2 muestra la estructura de colas usadas, tanto las que usan colas con prioridades (PQ, Priority Queue) como las FIFO (First In First Out) para N=1,2,3 caminos. Si sólo hay un camino disponible (N=1) el tráfico se organiza usando una PQ para transmitir el tráfico de control (p.ej. datos de encaminamiento), el flujo de vídeo y datos BE (Best Effort). Si seleccionamos dos caminos, el flujo I_frames y el tráfico de control se envían a través del mejor camino, mientras que los flujos B_frames, P_frames y BE por el peor camino. Si disponemos de más caminos, los siguientes flujos de vídeo mejorados se transmiten a través de los caminos ordenados por el algoritmo. Debido a la naturaleza dinámica de las redes ad hoc, es posible que en algunos casos no haya suficientes caminos diferentes para aplicar el esquema multicamino con el que estemos trabajando entre fuente y destino. En estos casos, deberemos aplicar el esquema multicamino equivalente al número de caminos que se hayan encontrado.

A. Modificaciones en la cola del interfaz de red Por defecto, en las colas de los interfaces de red compatibles

con la especificación IEEE 802.11b, no se da ningún tipo de prioridad a ningún paquete de datos respecto a otros de la misma clase, pero sí a los paquetes de control y/o señalización. En MM-DSR se han realizado unas modificaciones en cuanto a la forma en que se tratan los paquetes en la cola del interfaz. Se dispone de cuatro colas físicamente separadas en las que se van insertando paquetes en función de su prioridad. Así, teniendo la cola IFQ 0 como la más prioritaria (IFQ, InterFace Queue) y la cola IFQ 3 como la menos prioritaria, tendremos estos tipos de paquete en cada cola:

• Cola IFQ 0: encaminamiento MM-DSR (RREQ (Route Request), RREP (Route Reply)...), mensajes

• sonda, mensajes hola. • Cola IFQ 1: paquetes de prioridad 1. • Cola IFQ 2: paquetes de prioridad 2. • Cola IFQ 3: paquetes de prioridad 3.

Fig. 3: Esquema de las colas del interfaz de red.

Teniendo esta estructura de colas, se utiliza un programador de tareas “scheduler” prioritario de tal manera que se sirven primero los paquetes que haya disponibles en la cola 0, seguidamente los de la cola 1, etc. Así, sólo se servirán paquetes de la cola 3 en el momento en que estén vacías las otras tres colas. En el caso que nos ocupa, los paquetes de prioridad 1 se han hecho corresponder con los cuadros tipo I, los de prioridad 2 con los cuadros tipo P y los de prioridad 3 con los cuadros tipo B. Así se otorga la prioridad más baja a los cuadros tipo B al ser los menos importantes de cara a la decodificación y a la calidad de vídeo final. Se ha de pensar siempre que se estará trabajando sobre un entorno multiusuario, es decir, que en cada una de estas colas se dispondrán de paquetes que corresponderán a más de un usuario, con lo cual es fundamental otorgar máxima prioridad a aquellos cuadros que son imprescindibles para la reproducción de vídeo y que son los que más contribuyen a la percepción de la calidad del vídeo por parte del usuario. De esta manera, evitamos inundar las colas por las cuales pasarán los paquetes tipo I y P con multitud de paquetes menos importantes tipo B, ya que como se ha visto en el apartado anterior, debido a la estructura del GoP, el número de paquetes tipo B es muy superior al tipo I y P.

CARRASCAL FRÍAS et al.: MM-DSR: MULTIPATH QOS 453

V. SIMULACIONES Y RESULTADOS

En este apartado analizamos las simulaciones realizadas y los resultados obtenidos. Se ha trabajado con el simulador Network Simulator 2 (ns-2 v2.27) [5], debido a su versatilidad y a la posibilidad de añadir módulos creados a medida, ya que es de código abierto. Se ha realizado una implementación del protocolo MM-DSR tomando como base su homónima ya incluida del protocolo DSR en ns-2.

El escenario en que se han llevado a cabo estas simulaciones consiste en 30 nodos dispuestos aleatoriamente en un área de 400x400 metros. Se dispone de 5 fuentes de vídeo, mientras que paralelamente a estas transmisiones, se crean unas conexiones CBR sobre UDP de prioridad 3 entre los mismos nodos fuente y destino. De esta manera se intenta comprobar el rendimiento del sistema propuesto en condiciones de alta carga en la red. Éstas son las características principales de las simulaciones que se han realizado:

TABLA I PARÁMETROS DE LAS SIMULACIONES

Área 400x400 m Número de nodos 30 V. máx. de los nodos 10 m/s Rango de transmisión 120 m Patrón de movimiento Random Waypoint Especificación MAC IEEE 802.11b Ancho de banda nominal 11 Mbps Tiempo de simulación 100 s Codificación de vídeo MPEG-2 VBR Tasa del flujo de vídeo 150 Kbps Protocolo de transporte RTP/RTCP/UDP Tamaño máximo del paquete 1500 bytes Número de fuentes 5 Esquema multicamino N=3 Tamaño de las colas 50 paquetes Tráfico interferente CBR 2 Mbps Ruido del canal -92 dBm

Para comprobar el rendimiento del protocolo MM-DSR, se ha comparado con el protocolo DSR observando el porcentaje de pérdidas de paquetes sufridas en los destinos y la calidad percibida por el usuario en cuanto al vídeo recibido. Esta calidad la cuantificamos mediante la obtención de la PSNR, el valor pico de la relación señal-ruido (Peak to Signal Noise Ratio) entre el vídeo original y el transmitido. Para la obtención de estos valores de la PSNR, se ha utilizado la herramienta vidpsnr [8] que permite calcular la PSNR entre dos vídeos. En este caso se ha comparado el vídeo original con cada uno de los vídeos recibidos por cada uno de los nodos destino, una vez que las simulaciones han concluido.

Fig. 4: Porcentaje de pérdidas por tipo de marco I, P, B, usando DSR original.

Fig. 5: Porcentaje de pérdidas por tipo de marco I, P, B, usando MM-DSR.

Fig. 6: PSNR de cada flujo, DSR vs MM-DSR.

En la Fig. 4 se puede observar el alto porcentaje de pérdidas

sufrido por cada uno de los flujos al usar el protocolo DSR en el escenario creado. Esta alta tasa de pérdidas se debe al hecho de que todos los cuadros de cada uno de los flujos se transmiten a través del mismo camino entre fuente y destino, y

454 IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 6, OCTOBER 2007

a través de las mismas colas físicas en cada uno de los interfaces de red intermedios. Estos cuadros deberán compartir espacio en estas colas con los paquetes UDP correspondientes al tráfico interferente, provocando pérdidas tanto por desbordamiento de las colas como por colisión de acceso al medio como consecuencia de compartir todos los paquetes el mismo camino.

En la Fig. 5 se observa una disminución de las pérdidas percibidas por cada uno de los 5 nodos destino al usar el protocolo MM-DSR. La disminución se debe al equilibrio de carga llevado a cabo en los interfaces de red intermedios de cada uno de los caminos y al uso de la técnica multicamino, enviando los paquetes más importantes por los mejores caminos disponibles. Los cuadros I no sufren pérdidas en el escenario MM-DSR, pues tienen mayor prioridad que los cuadros P, B al ser atendidos por el programador de tareas PQ (ver Fig. 3) de cada nodo. Además, se transmiten por el mejor camino disponible que ha encontrado el algoritmo de encaminamiento (el más fiable, estable, con mayor BW y menores pérdidas y retardos).

Finalmente, en la Fig. 6 se comprueba la mejora en la calidad percibida por el usuario mediante la obtención de la PSNR. Se puede observar que se obtiene un aumento de unos 15 dB para cada uno de los flujos transmitidos en la simulación.

VI. CONCLUSIONES Y LÍNEAS FUTURAS En este artículo se ha podido comprobar que el uso de MM-

DSR.11b mejora la recepción de vídeo sobre altas condiciones de carga en una red ad hoc. El uso de técnicas multicamino combinado con un sistema basado en notas para escoger los mejores caminos de entre todos los disponibles, junto con el hecho de otorgar distintas prioridades a los paquetes de datos de cara a su gestión, tanto en las colas del interfaz de red como en el encaminamiento hasta el destino, ha contribuido a mejorar el rendimiento global del sistema. Cabe notar que esta mejora se consigue incluso bajo condiciones de alta carga de tráfico en la red, al usar los nodos más eficientemente los recursos disponibles.

Se está evaluando la posibilidad de incluir dinamismo en MM-DSR.11b en cuanto a los umbrales relacionados en la calificación de los caminos, así como hacer variable la frecuencia de iteración del algoritmo en función del estado de la red. De esta manera, al disponer de condiciones de red cambiantes, también se variarían las condiciones de trabajo de MM-DSR con el objetivo de disminuir el tráfico de sobrecarga creado por los paquetes de control. También se podrían otorgar diferentes prioridades a los cuadros de un mismo tipo en función de la relevancia del papel que cumplan en el momento de la decodificación del vídeo.

Por otro lado, también es interesante evaluar el rendimiento del sistema junto con la especificación MAC IEEE 802.11e, la cual está enfocada a ofrecer calidad de servicio. Actualmente existen algunas propuestas [6], [7], que comunican la capa de enlace IEEE 802.11e con la de red. Utilizan un programador de tareas scheduler basado en ventana de contención que permite gestionar 4 colas con diferente prioridad.

VII. REFERENCIAS

[1] S. Mao, Y. Thomas Hou, X. Cheng, H. D. Sherali, S. F. Midkiff, “Multipath Routing for Multiple Description Video in Wireless Ad Hoc Networks”, Proceedings of IEEE INFOCOM Volume 1, 13-17 March 2005 Page(s):740 - 750 vol. 1. ISBN: 0-7803-8968-9.

[2] P. Basu, N. Khan, T. D. C. Little, “A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks”, in proceedings of 21st International Conference on Distributed Computing Systems Workshop (ICDCSW '01), pp. 413-418, 2001. ISBN: 0-7695-1080-9.

[3] S. Chakrabarti, A. Mishra, “Quality of service for wireless mobile Ad Hoc networks,” Wireless Communications and Mobile Computing, John Wiley \& Sons, vol. 4, 2004, pp. 129–153. ISSN: 1530-8669.

[4] T. Bheemarjuna, I. Karthigeyan, B. S. Manoj, C. Siva, “Quality of Service provisioning in Ad Hoc wireless networks: A survey of issues and solutions”, Ad Hoc Networks, Elsevier, 2004. pp. 100-105. doi:10.1016/j.adhoc.2004.04.008,1570-8705.

[5] The Network Simulator - ns-2, http://www.isi.edu/nsnam/ns/ [6] C.T. Calafate, P. Manzoni, M.P. Malumbres, “On the interaction

between IEEE 802.11e and routing protocols in Mobile Ad-hoc Networks", 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2005, pp. 110-117. ISBN: 0-7695-2280-7

[7] L. Gannoune, S. Robert, "Dynamic Tuning of the contention window minimum (CWmin) for enhanced service differentiation in IEEE 802.11 wireless ad-hoc networks" , 2004, ISBN: 0-7803-8523-3.

[8] vidprofile 0.80. http://vidprofile.berlios.de/setup.html [9] Wu Xiuchao wuxiucha@comp.nus.edu.sg . Simulate 802.11b Channel

with NS2. SOC, NUS. Disponible en: http://www.comp.nus.edu.sg/wuxiucha/research/reactive/report/80211ChannelinNS2_new.pdf

[10] Xuefei Li, Laurie Cuthbert, "Multipath QoS Routing of supporting Diffserv in Mobile Ad Hoc Networks", Proceedings of SNPD/SAWN'05. pp. 308-313. ISBN:0-7695-2294-7.

VIII. BIOGRAFÍAS

Víctor Carrascal Frías (M’2004) nació en Barcelona (España) en 1978. Recibió el título de Ingeniero Superior de Telecomunicaciones por la UPC en 2003.

Durante el periodo 2002-2004 estuvo colaborando en Tradia en el departamento de Telecontrol realizando desarrollos y demostraciones de las capacidades de transmisión de datos sobre IP de las redes TETRA. Asimismo, llevó a cabo diversos proyectos de telecontrol para el departamento de Medio Ambiente (METEOCAT). En 2004 se incorporó al Departamento de Ingeniería

Telemática de la UPC (http://www-entel.upc.es), investigando en el Grupo de Servicios Telemáticos en el apartado de "Servicios Multimedia Distribuidos con Calidad de Servicio" SERTEL (http://sertel.upc.es).

Está interesado en la investigación de QoS sobre flujos de vídeo en redes IP, protocolos generales de QoS, especialmente los protocolos de enrutamiento sobre redes ad-hoc incluyendo los de control de transferencia. Es miembro del IEEE desde 2004. Actualmente está trabajando sobre una serie de implementaciones para el simulador NS2 para el desarrollo de un algoritmo cross-layer para ofrecer cierta QoS para aplicaciones multimedia sobre redes adhoc. Ha realizado una implementación del protocolo RTP/RTCP para NS2 y está trabajando en el desarrollo de una modificación óptima del protocolo DSR (Dynamic Source Routing) para entornos multicamino.

CARRASCAL FRÍAS et al.: MM-DSR: MULTIPATH QOS 455

Guillermo Díaz Delgado (M’2000, S’2003) nació en Querétaro, México. Es Ingeniero en Sistemas Electrónicos por el Instituto Tecnológico y de Estudios Superiores de Monterrey, México y Maestro en Ciencias por la Universidad Laval, Québec, Canadá.

Ha prestado sus servicios como ingeniero en varias compañías y ha sido docente e investigador en diversas instituciones públicas y privadas. Desde 1991 es profesor de la Facultad de Informática de la Universidad Autónoma de Querétaro (UAQ). De 2000 a 2002 dirigió la Coordinación General de

Servicios Académicos de la UAQ. Es miembro del IEEE, la IEEE Communications Society, la IEEE Computer Society, y Miembro Fundador de la Sección Querétaro del IEEE. Además es miembro de las Asociaciones Ex-A-Tec de Querétaro, Monterrey y Barcelona.

Desde octubre de 2003 estudia el Doctorado en Ingeniería Telemática en la Universidad Politécnica de Cataluña (UPC), como becario del Programa de Mejoramiento del Profesorado (PROMEP-UAQ), del programa CONACYT-UPC y de la Fundación Carolina. Sus intereses incluyen el modelado y evaluación de prestaciones, las redes ad hoc y de sensores, el diseño cross-layer, la gestión de la QoS, los servicios multimedia en redes IP, y la asignación óptima de recursos.

Aída Zavala Ayala nació en la Ciudad de México en 1978. Finalizó la carrera de Ingeniería en Telecomunicaciones en la Universidad Nacional Autónoma de México (UNAM), México, en el año 2004.

Ha trabajado en la industria privada como ingeniera y en el año 2005 comenzó sus estudios de doctorado en Ingeniería Telemática en la Universidad Politécnica de Cataluña (UPC), Barcelona, becada por el programa ALBAN (Programa de becas de estudio de alto nivel dirigido a América Latina).

Pertenece a la línea de investigación “Servicios Telemáticos” y entre sus intereses de investigación se encuentran el modelado y la evaluación de calidad de servicio (QoS) en redes móviles (redes ad-hoc, redes de satélites) para servicios multimedia.

Mónica Aguilar Igartua es Ingeniera de Telecomunicaciones desde Septiembre 1995 y Doctora Ingeniera de Telecomunicación desde Enero de 2000, ambos títulos obtenidos en la Universidad Politécnica de Cataluña (UPC), Barcelona, España.

Actualmente, trabaja en gestión de la QoS a nivel de servicio, en particular en mecanismos para calcular parámetros SLA (Service Level Agreements) a nivel de usuario. Sus intereses de investigación también incluyen modelado y evaluación de prestaciones de redes de alta

velocidad, así como de servidores multimedia y de flujos de audio/vídeo. Su actividad de investigación más reciente se centra en la provisión y gestión de la QoS sobre redes móviles ad hoc (MANET). Es profesora titular del Departamento de Ingeniería Telemática en la ETSETB.

En 1995, se incorporó al "Grupo de Diseño y Evaluación de Redes y Sistemas de Alta Velocidad, y en 2001 se incorporó al Grupo de investigación de Servicios Telemáticos (SerTel) del Departamento de Ingeniería Telemática de la UPC.

456 IEEE LATIN AMERICA TRANSACTIONS, VOL. 5, NO. 6, OCTOBER 2007