ENRUTAMIENTO BASADO EN EL ALGORITMO DE DIJKSTRA PARA UNA RED DE RADIO COGNITIVA(Routing based on Dijkstra’s algorithm to a cognitive radio network)

Luis

Description

Resumen
En este artículo se presentan los resultados de la evaluación de un protocolo de enrutamiento para una red de radio cognitiva, basado en el algoritmo de Dijkstra, en el que los nodos buscan el camino más óptimo, dependiendo de los pesos de cada ruta o enlace. Para el desarrollo se uso Network Simulator 2 (NS2). En esta herramienta se implementa el protocolo, se genera el tráfi co y se simula la movilidad de los nodos de la red de radio cognitiva.
Abstract
This paper presents the results of the evaluation of a routing protocol for cognitive radio network, based on Dijkstra’s algorithm, in which nodes seek the most optimal way, depending on the weights of each path or link. For development, we used Network Simulator 2 (NS2). This tool implements the protocol
the traffi c is generated
and simulates the mobility of the nodes of the network of cognitive radio.

Sujets

• Algoritmo de Dijkstra
• Throughput
• Dijkstra's algorithm
• Cognitive radio

Informations

• Publié par: erevistas
• Publié le: 01 janvier 2011
• Nombre de lectures: 414
• Langue: Español

Extrait

con-ciencias
Enrutamiento basado en el algoritmo
de Dijkstra para una red de radio cognitiva
Routing based on Dijkstra’s algorithm to a cognitive radio network

LUIS F. PEDRAZA
Ingeniero electrónico, magíster en Ciencias de la Información y las Comunica-
ciones. Docente e investigador de la Universidad Distrital Francisco José de Cal-
das. Bogotá, Colombia. [e-mail]
DANILO LÓPEZ
Ingeniero electrónico, magíster en Teleinformática. Docente e investigador de la
Universidad Distrital Francisco José de Caldas. Bogotá, Colombia. dalopezs@
udistrital.edu.co
OCTAVIO SALCEDO
Ingeniero en sistemas, magister en Ciencias de la Información y las Comunica-
ciones, estudiante de Doctorado. Docente de la Universidad Distrital Francisco
José de Caldas. Bogotá, Colombia. [e-mail]
Clasificación del artículo: Investigación (Conciencias)
Fecha de recepción: 4 de junio de 2011 Fecha de aceptación: 29 de agosto de 2011
Palabras clave: Algoritmo de Dijkstra, redes de radio cognitiva, throughput.
Key words: Dijkstra’s algorithm, cognitive radio networks, throughput.
menta el protocolo, se genera el tráÞ co y se si-
RESUMEN
mula la movilidad de los nodos de la red de radio
cognitiva.
En este artículo se presentan los resultados de la
evaluación de un protocolo de enrutamiento para
una red de radio cognitiva, basado en el algoritmo ABSTRACT
de Dijkstra, en el que los nodos buscan el cami-
no más óptimo, dependiendo de los pesos de cada This paper presents the results of the evaluation
ruta o enlace. Para el desarrollo se uso Network of a routing protocol for cognitive radio network,
Simulator 2 (NS2). En esta herramienta se imple- based on Dijkstra’s algorithm, in which nodes
enrutamiento basado en el algoritmo de dijkstra para una rTecnura Vol. 15 No. 30 pp. 94 - 100 Julio - Diciembred de radio cognitiva e de 2011 93
LUIS F. PEDRAZA / DANILO LÓPEZ / OCTAVIO SALCEDOcon-ciencias
seek the most optimal way, depending on the implements the protocol; the trafÞ c is generated
weights of each path or link. For development, and simulates the mobility of the nodes of the net-
we used Network Simulator 2 (NS2). This tool work of cognitive radio.
* * *
1. INTRODUCCIÓN 2. ESTADO DEL ARTE
El rápido crecimiento de las redes inalámbricas Numerosos esfuerzos han sido realizados en la
y las comunicaciones móviles han limitado la deÞ nición de las directrices y las limitaciones
disponibilidad de las bandas del espectro por la operativas del diseño de las redes de radio cog-
creciente demanda [1]. En un informe recien- nitiva (CRNs). Un primer escenario se centra en
te de la Comisión Federal de Comunicaciones que las transmisiones de radio cognitiva (CR) no
(FCC) se muestra que la mayoría del espectro deben degradar notablemente la calidad del usua-
asignado no es completamente utilizado por los rio primario (PU). Esto se puede lograr adaptan-
usuarios licenciados o primarios, brindando la do la potencia de transmisión de los usuarios de
posibilidad de reutilizar estas bandas de fre- CR. Un Segundo escenario propone que los usua-
cuencias libres en un instante de tiempo (hue- rios de CR deben interrumpir inmediatamente la
cos espectrales), dando origen a la red de ra- transmisión cada vez que un PU activo es detec-
dio cognitiva que es deÞ nida por la FCC como tado. Esto requiere un frecuente monitoreo de las
una radio que puede cambiar los parámetros del actividades de los PU.
transmisor basado en la interacción con el en-
torno en que éste opera [2]. En redes cognitivas las interferencias son ß uc-
tuantes en términos de frecuencia y localización.
El objetivo de la red de radio cognitiva es op- La mayoría de los estudios se han enfocado en la
timizar el uso del espectro reutilizando huecos capa física y en la MAC; sin embargo, las inves-
espectrales sin interferir a los usuarios prima- tigaciones en enrutamiento de radio cognitiva son
rios. Para cumplir este Þ n los protocolos de limitadas [1].
enrutamiento juegan un papel muy importante
ya que basados en los parámetros de calidad de Por otro lado, otras investigaciones se centran en
servicio permiten determinar cuál es el mejor la importancia de algoritmos de enrutamiento, tal
camino para enrutar la información, lo que se como: en [3] en donde se describe el diseño de
reß eja en la eÞ ciencia de la red, pues es elegi- métricas de enrutamiento y analiza los diferentes
da la mejor ruta y los costos se minimizan. Por protocolos de [4,5], presenta algo-
tanto, a continuación se describe el estado del ritmos basados en la interferencia [6], muestra un
arte de los protocolos de enrutamiento en radio algoritmo adecuado para CRN en canales inalám-
cognitiva basados en el algoritmo de Dijkstra, bricos con desvanecimiento [7] y [8], desarrolla y
después se detalla el desarrollo del algoritmo de evalúa algoritmos utilizando el camino más corto.
Dijkstra en el protocolo de enrutamiento, luego Otros trabajos [4,7,9] se basan en la infraestructu-
se implementa el escenario de simulación, y se ra centralizada. También son propuestos, algorit-
muestran sus resultados, y Þ nalmente, algunas mos basados en demanda de modo reactivo para
conclusiones se presentan al respecto. seleccionar rutas y canales [10,11,12]. En [13]
94 Tecnura Vol. 15 No.30 Julio - Diciembre de 2011con-ciencias
el protocolo ROPCORN (Routing Protocol for la detección de los parámetros de la capa red, ana-
Cognitive Radio Ad Hoc Networks) incorpora dos lizando los resultados detectados y adaptándose a
métricas de enrutamiento basadas en el costo de la capa física de la tecnología usada para lograr
disponibilidad del espectro y en la estimación de una óptima calidad de servicio (QoS).
carga. Las metas del ROPCORN son maximizar
el rendimiento y minimizar la latencia de men- En CRN el usuario de CR escoge la ruta con el
sajes, mientras también se minimiza los demás peso de trayectoria óptimo de acuerdo con el tipo
recursos consumidos tales como memoria, red y de servicio utilizado. Por ejemplo, el sistema
capacidad. debe evitar el envío de paquetes a través de en-
laces que tienen una baja capacidad, ya que sería
Entre los protocolos de enrutamiento basados una limitante para poder brindar un servicio como
en el algoritmo de Dijkstra está SDCR (smallest la transmisión de video en tiempo real.
delay cognitive routing) [1], que utiliza este al-
goritmo para encontrar la menor ruta de retraso Adicional al peso de la trayectoria, es usado el ni-
de transmisión. En [14] la información de enruta- vel de utilización de la ruta, que es un parámetro
miento es optimizada para preservar la batería de que muestra qué tan activo es el enlace disponible,
los dispositivos, mientras se mantiene una calidad es decir, la cantidad de carga de tráÞ co existente
de señal aceptable. De la misma manera, ha sido en el enlace y la cantidad futura de carga capaz de
analizado un protocolo de estimación probabilís- soportar de acuerdo con la topología de la red, el
tica que mejora el throughput al compararse con servicio y la tecnología utilizada. Por medio del
el tradicional algoritmo de Dijkstra [15]. enrutamiento se debe evitar enlaces con un alto
nivel de utilización y desviar el tráÞ co a los enla-
El algoritmo ROPCORN tiene en cuenta una es- ces de menor uso [17].
trategia de ruta óptima, la cual se basa en protoco-
los de enrutamiento tradicionales como Dijkstra Por lo anterior, los protocolos de enrutamiento
para calcular la ruta más corta teniendo en cuenta tradicionales en las redes inalámbricas, como el
el menor costo. vector distancia y el Path Vector, presentan pro-
blemas en redes cognitivas debido a que por su
Otro protocolo aplicado en CRN y que se funda- simplicidad no asimilan los cambios topológicos
menta en el algoritmo de Dijkstra es IPSAG (IP de forma adecuada. Por el contrario, los protoco-
Spectrum Aware Geographic) [16]. Este protoco- los basados en Link state proporcionan una me-
lo de enrutamiento reúne más posibilidades para jor información a los nodos del estado de la red
lograr en tiempo real en CRN. El ayudando a una mejor toma de decisiones en la
IPSAG ofrece ß exibilidad en los saltos, inter- ruta, utilizando parámetros como la capacidad de
cambiando información en tiempo real con sus enlace y el retardo, y no en el número de saltos o
vecinos. La adaptación al usuario de CR es muy la distancia [18].
dinámica y cuenta con ventajas geográÞ cas de en-
rutamiento en un nodo de red de alto throughput. Dijkstra elije la ruta más corta de las posibles op-
ciones, lo que conlleva a expandirse mejor, ya que
En redes cognitivas la capa de red es adaptable a cada enrutador calcula las trayectorias de manera
los cambios del medio inalámbrico y a los diferen- independiente, por tanto, es m