informÁtico - upbbga.edu.co · informatica y computacion - siic 2007 en el mes de septiembre se...

FACULTAD DE INGENÍERIA INFORMÁTICA Seminario Internacional de Informática y Computación Septiembre 19 – 21 de 2007

BOLETIN

INFORMÁTICO

�Editorial

� Nuevos grupos de Trabajo en Programación

� Mecanismos de Metaprogramación en JAVA.

� De los Datos al Conocimiento

� El problema del Longest Common Subsequence: Extensiones y Algoritmos

� Estado del Arte de las WSN

Año 1 - Boletín No. 2 Octubre – Noviembre de 2007 Facultad de Ingeniería Informática


SEMINARIO INTERNACIONAL DE

INFORMATICA Y COMPUTACION - SIIC 2007

En el mes de septiembre se llevó a cabo el primer “Seminario Taller Análisis de Secuencias Genómicas”, en el cual se

trabajaron las diferentes herramientas informáticas (software) que se usan a nivel mundial para hacer análisis de genomas (de

cualquier especie viva) y que han sido utilizadas en el estudio de las variaciones en los genes de las diferentes especies y que

han permitido detectar similitudes entre diferentes organismos vivientes, lo mismo que para determinar ciertas enfermedades;

los participantes en este taller aprendieron a manejar aplicaciones informáticas que están como punta de lanza en el desarrollo

de la Bioinformática.

Además, se realizó el primer “Seminario Internacional de Informática y Computación” en la Universidad Pontificia

Bolivariana en la cual se dieron a conocer los avances en estas disciplinas, los temas tratados fueron: Seguridad Informática,

Gestión de Tecnologías, Bioinformática, Ingeniería de Software y Bases de Datos, Computación de Alto Rendimiento.

Contamos con ponentes de Venezuela y de España, tocando temas como: desarrollos computacionales aplicados a los

genomas y seguridad informática, para estos temas contamos con el coordinador en el área de servicio de la Red

Iberoamericana de Bioinformática el doctor Raúl Isea (Venezuela) y en el área de criptografía tuvimos al autor de varios

libros sobre Aplicaciones Criptográficas el Doctor Jorge Ramió (España),quien es el coordinador y fundador de la Red

Iberoamericana de Criptografía y Seguridad de la Información – CRIPTORED, en el área de la computación forense

contamos con la presencia de una autoridad a nivel latinoamericano en esta área como es el doctor Jeimy Cano (Colombia).

Como parte adicional a los ponentes anteriores se contó con toda una serie de conferencistas que enriquecieron al auditorio

con los temas tratados, esto fortalece nuestra facultad para fomentar en los estudiantes y asistentes el interés por el desarrollo

Computacional y de la Informática.

Cabe destacar la valiosa participación y colaboración de los docentes y estudiantes de nuestra Facultad, ya que sus valiosos

aportes permitieron que éste evento se convierta en un espacio fundamental de innovación y actualización en el área de la

Ingeniería Informática.

Wilson Castaño Galviz, MSc

Docente Facultad de Ingeniería Informática


NUEVOS SEMILLERO DE

PROGRAMACIÓN

El semillero de Construcción de Software y Bases de Datos, abre un nuevo espacio de investigación en el área de

Programación. Con este nuevo grupo se busca que aquellos estudiantes con motivación para trabajar más a fondo en el área

de la programación, mejoren sus habilidades, intercambien ideas, estudien diferentes estrategias de la algoritmia, investiguen

sobre lenguajes novedosos y desarrollen mejores aplicaciones.

Temas como la programación estructurada, programación orientada a objetos, lenguajes para comunicaciones móviles,

desarrollo de juegos, desarrollo en ambientes gráficos, herramientas para el desarrollo de la programación, estrategias

algorítmicas de desarrollo, entre otros forman parte de los tópicos a estudiar. Se realizarán algunas actividades de fogueo

como maratones de programación para estimular la competencia y proyectar el grupo.

Se invita a todos los miembros de la comunidad universitaria con interés en estos temas a que se vinculen a este nuevo grupo

y compartan sus conocimientos, se propiciarán jornadas de teoría y práctica. Este grupo estará abierto a los estudiantes de

todas las carreras de la universidad, lo cual amplía los horizontes de aplicación de los temas estudiados y redundará en un

mayor nivel académico.

Quienes estén interesados podrán contactarse con la Ingeniera Diana Teresa Gómez Forero, docente de la Facultad de

Ingeniería Informática ([email protected]). Inicialmente se planean reuniones para los Miércoles de 6 a 8 pm en la

sala de Informática ubicada en el edificio F salón 203(F203), iniciando el próximo 24 de Octubre.

Si le gusta la programación de computadores, nos gustaría contar con su participación en este grupo.

Diana Teresa Gómez Forero, Msc

Docente Facultad de Ingeniería Informática


MECANISMOS DE METAPROGRAMACIÓN EN

JAVA APLICADOS AL DISEÑO E IMPLEMENTACIÓN DE COMPONENTES WEB

Milton Jesús Vera Contreras

Grupo de Investigación GIDIS

Universidad Francisco de Paula Santander

[email protected]

[email protected]

Abstract. This document proposes an architecture for applications Web based on components that use reflection.

The reflection is the capacity of a program in execution to look at itself and its environment and to change what does

depending on which observes. First the problem that originates the necessity of meta-programming mechanisms is

described, secondly a arhitecture based on components which they use reflection is explained, soon expose the

concepts of meta-programming in Java language to explain the implementation of the components and finally a case

of study like example.

1 Introducción

En la sociedad del conocimiento el objetivo del software ya no es el procesamiento automático de datos sino la comunicación

de conocimiento entre las personas que lo usan. Dicho conocimiento está encapsulado en los objetos, los cuales se hacen

visibles gracias a las interfaces gráficas y en general, las interfaces humano-máquina. La persistencia de dichos objetos es

indispensable y se consigue con las tecnologías de bases de datos relacionales y orientadas a objetos. El conocimiento

encapsulado por los objetos del software es cambiante y tanto la visualización como la persistencia de dichos cambios se

logran mediante el procesamiento o lógica del negocio.

La arquitectura del software es la manera como se organizan estos tres elementos, visualización, persistencia y

procesamiento, los cuales comparten la misma representación conceptual de los objetos del dominio del sistema real. En la

actualidad, lo más común es que estos tres elementos estén distribuidos físicamente y su arquitectura consiste en componentes

reutilizables y portables, permitiendo que la industria del software funcione de manera similar a la industria automotriz,

donde un producto final se obtiene rápidamente a través del ensamble de componentes genéricos y/o especializados, y de la

misma forma puede personalizarse y extenderse fácilmente. Las aplicaciones Web son el principal ejemplo de software

distribuido y en la mayoría de los casos su arquitectura está basada en componentes, como las aplicaciones basadas en

tecnologías J2EE. Las aplicaciones Web J2EE pueden ser tan sencillas o complejas como se desee y requiera, desde simples

archivos JSP con marcas HTML y scriptlets Java, hasta aplicaciones robustas que aprovechan al máximo las especificaciones

de los Java Beans y de las librerías de etiquetas personalizadas (Tag Library).


Por lo general las aplicaciones Web mezclan código HTML y código Java en las páginas JSP, lo cual reduce la reutilización y

complica las tareas de diseño gráfico. Igualmente los Java Beans mezclan código SQL para recuperar la información

almacenada en bases de datos relacionales y repiten patrones de código para convertir datos relacionales en objetos.

El presente trabajo propone una arquitectura para desarrollar aplicaciones Web que evita estas situaciones. La propuesta es

aprovechar las características de reflexión del lenguaje Java, la portabilidad del lenguaje XML y la versatilidad del lenguaje

XSL. Con estas tecnologías se implementan dos componentes genéricos que permiten, en primer lugar, separar por completo

los Java Beans del código que recupera y modifica objetos persistentes y en segundo lugar, independizar las tareas de diseño

gráfico del resto del desarrollo de software.

Primero se describe la arquitectura, seguidamente se especifica el diseño e implementación de cada uno de los componentes y

finalmente se explica el uso de la arquitectura y los componentes en una aplicación específica. Antes de la implementación se

realiza una descripción de la API Java-Reflect e introspección, el mecanismo de metaprogramación empleado.

2 Especificación de la Arquitectura Propuesta

La arquitectura que se propone persigue como objetivo principal centrar la importancia de un proyecto de aplicación Web en

el modelado e implementación del sistema real, independiente de lo mecanismos para visualización y persistencia. Para esto

se requiere conseguir:

• Separar el desarrollo de la interfaz gráfica de usuario GUI del resto del desarrollo del proyecto.

• Aislar los detalles de implementación requeridos para la persistencia de objetos.

• Separar los detalles de seguridad, historial, control de navegación y transacciones en entornos Web.

Inicialmente estos objetivos pueden conseguirse fácilmente siguiendo el patrón arquitectónico Modelo Vista Control (M.V.C.

Model View Control), lo cual en J2EE se implementa mediante páginas JSP y HTML, Servlets y Java Beans. Sin embargo no

existe una total independencia de los mecanismos de visualización y persistencia lo que puede apreciarse en las siguientes

situaciones:

• La implementación de la vista con páginas JSP mezcla el lenguaje HTML con el lenguaje JAVA. Pueden tenerse

diseñadores gráficos muy buenos que carecen de conocimiento de tecnologías JAVA y recíprocamente pueden tenerse

expertos en páginas JSP con regular desempeño en el diseño gráfico. Esto ocasiona inconvenientes si se desea

implementar en paralelo y de manera separada la interfaz gráfica con el resto del proyecto. Igualmente cambios en la

apariencia visual del software, suelen requerir de los expertos en JSP. Esto no solo se presenta con tecnologías JAVA,

sino también ocurre en tecnologías como PHP y ASP, donde incluso es más evidente.

• Independientemente de la tecnología empleada (JAVA, PHP, ASP, etc.) es común encontrar repetidamente líneas de

código similares para la recuperación, inserción, modificación y eliminación de objetos persistentes. Por ejemplo, el

fragmento de código que recupera el listado de deudores de una empresa resulta similar al fragmento de código que

recupera el listado de cursos asignados a un profesor, a pesar de ser objetos muy diferentes.


La primera situación contrasta con el primer objetivo propuesto y una buena alternativa es emplear el lenguaje XML, el cual

funciona como una vista conceptual previa a la visualización. Para esto es necesario un componente capaz de generar

fragmentos XML a partir de los objetos y reglas de visualización que transformen dichos fragmentos XML en formatos

sencillos y agradables para el usuario.

Para la segunda situación y, consecuentemente, el segundo objetivo, lo ideal es que exista un componente capaz de efectuar

las operaciones de persistencia sobre cualquier objeto.

El tercer objetivo se alcanza encapsulando en componentes genéricos el control del entorno Web, lo cual en la mayoría de los

casos es soportado por las plataformas existentes.

Con lo expuesto es evidente que la arquitectura que se busca debe estar basada en componentes y esto, entre otras ventajas,

permitirá su implementación en cualquier tecnología. Además, es necesario que los componentes puedan mirar al interior de

los objetos “looking inside object”[1],[2],[5],[7] lo que se consigue usando metaprogramación con mecanismos como

reflexión y genericidad. En éste orden de ideas se propone la arquitectura de la figura 1.

Fig 1. Arquitectura Propuesta (Elaborado en Visual Paradigm Community Edition)

2.1 Capa de Presentación

Esta capa tiene como única función ofrecer al usuario una interfaz gráfica agradable y sencilla. Cubre aspectos de diseño

gráfico como la diagramación, apariencia de colores y fuentes, navegación y control de restricciones de envío de información.

Por lo general las tecnologías empleadas son HTML, Java Script, Componentes de Animación como Macromedia Flash, entre

otros[4],[6]. Puesto que se quiere independizar ésta capa, se añade la tecnología XSLT, que permitirá convertir las vistas

conceptuales proporcionadas en XML por la capa Web a cualquier tecnología de visualización requerida. Es fundamental que

las tecnologías se empleen de acuerdo a los estándares puesto que la visualización final depende de un navegador que es un

componente no controlado por los desarrolladores.

2.2 Capa de Persistencia

La función principal de ésta capa es administrar la persistencia de los objetos. Incluye las funciones de representación,

almacenamiento, recuperación e integridad. El único trabajo requerido en ésta capa es el diseño e implementación de un


modelo persistente. La implementación se consigue con manejadores de bases de datos relacionales, aunque lo ideal sería una

manejador orientado a objetos. En ocasiones se puede emplear persistencia basada en XML en lugar de persistencia

relacional, por lo general cuando el volumen de objetos es considerablemente pequeño. El diseño del modelo persistente debe

derivar del modelo de clases que usa la capa Web.

2.2 Capa Web

Esta es la capa más compleja pues concentra la lógica del negocio. De manera general, ésta capa solicita a la capa de

persistencia los objetos necesarios para satisfacer un requerimiento del usuario final. Se asumen dos tipos de requerimientos:

consulta de objetos o manipulación de objetos. Cuando el requerimiento es de consulta, la capa Web debe proporcionar una

vista XML de los objetos devueltos por la capa de persistencia y regresar dicha vista a la capa de presentación. Cuando el

requerimiento implica la manipulación de objetos, estos pueden tener encapsulada la lógica de negocios que es independiente

de la persistencia, con lo cual la capa Web debe invocar dicha funcionalidad sobre los objetos. Es posible que la manipulación

de los objetos implique hacer que nuevos objetos se hagan persistentes, que objetos persistentes dejen de serlo o modifiquen

su estado. En estos casos la capa Web debe solicitar a la capa de persistencia que se efectúen tales cambios. Es posible que se

encapsule lógica de negocios como procedimientos almacenados en la base de datos, en tal caso, dichos procedimientos

deben ser invocados por la capa Web. Además de las tareas de lógica de negocio, representación XML y persistencia, la capa

Web debe proporcionar funcionalidades relacionadas con el control de seguridad, navegación y transacciones. La

complejidad de ésta capa se puede separar en componentes:

• Componente del Negocio, implementados como clases del negocio según el modelo conceptual.

• Componente ORM (Object Relational Mapping), encargado de interactuar con la capa de persistencia.

• Componente XMLConverter, que genera fragmentos XML a partir de objetos del negocio.

• Componente de Invocación (TagLibrary) que ocultan el código de acceso a los componentes anteriores.

• Componente Web, que controla los aspectos de seguridad, navegación y transacción.

• Componente de Visualización XSL (físicamente en ésta capa, lógicamente en la capa de presentación).

La comunicación entre las capas realiza mediante el protocolo HTTP y Web Services. La figura 2 muestra un diagrama de

secuencias como escenario general de consulta bajo la arquitectura, el cual se describe a continuación:


Fig 2. Diagrama de Secuencia para Escenario de Consulta (Elaborado en Visual Paradigm Community Edition)

El usuario interactúa con el navegador demandando alguna funcionalidad. Puede hacerlo con un click sobre algún vínculo, o

pulsando el botón enviar de un formulario. (1). El navegador crea un paquete HTTP y envía la petición al servidor Web que

se encarga de crear una instancia de la página JSP solicitada (2). La página JSP instancia una marca de invocación de

persistencia ORMInvoquer (3) y le solicita obtener uno o varios objetos persistentes (4). El objeto ORMInvoquer instancia un

objeto ORM (5) y le delega la petición del JSP (6). El objeto ORM instancia un Bean (7). El objeto ORM solicita información

persistente (8). La capa de persistencia le regresa al ORM la información solicitada (9). El objeto ORM altera el Bean

instanciado con la información persistente (10). El objeto ORM regresa el resultado de la petición al ORMInvoquer (11). El

objeto ORMInvoquer regresa el resultado de la petición al JSP (12). La página JSP instancia una marca de invocación de

conversión XML, XMLInvoquer (13) y le solicita crear un fragmento XML a partir de los Bean existentes en la sesión. (14)

El objeto XMLInvoquer instancia un objeto XMLConverter (15) y le delega la petición del JSP (16) El objeto XMLConverter

solicita información a los Beans existentes en la sesión (17). Los Beans regresan la información al XmlConverter (18). El

objeto XMLConverter regresa el resultado al XMLInvoquer (19). El objeto XMLInvoquer regresa el resultado de la petición

al JSP(20). El JSP regresa un documento XML bien formado al navegador (21). El navegador interactúa con el servidor Web

solicitando las reglas de transformación XSLT (22). El navegador solicita al XSLT realizar la transformación de fragmentos

XML (23). El XSLT regresa el resultado de la transformación al navegador (24). El navegador muestra el resultado al

Usuario. (25)

Bajo esta arquitectura existen JSP dedicados sólo a consulta y otros dedicados sólo a modificación. Los últimos delegan la

generación de la vista a los primeros. El escenario anterior corresponde a la funcionalidad de consulta. En caso de requerirse

modificaciones a los objetos persistentes, los pasos correspondientes a la generación de la vista XML (paso 13) se omiten y la

página JSP delega (forward) a otra página la respuesta visual.


3 Metaprogramación en Java

La primera idea de metaprogramación aparece cuando Von Neumann propone guardar las instrucciones y los datos juntos en

la misma memoria [7]-[9]. Esto origina la hipótesis “Si las instrucciones procesan los datos que están en la memoria, un

programa podría tratar las instrucciones de otro programa o las propias como datos, es decir, un programa que computa otro

programa”. El estudio de ésta hipótesis origina el término metaprogramación, el cual, de manera general se considera una

disciplina que consiste en escribir programas que representan y manipulan otros programas o así mismos. Originalmente esto

fue trabajo limitado a la inteligencia artificial y actualmente ha permeado muchas áreas. A continuación se resumen los

principales conceptos empleados y luego se exponen los mecanismos que Java proporciona para implementarlos.

3.1 Hipótesis de Smith

La hipótesis inicialmente propuesta respecto a la máquina de Neumann aparece generalizada a sistemas inteligentes por Brian

Cantwell Smith en “Reflection and Semantics in a Procedural Language” de la siguiente manera: “Del mismo modo que un

proceso computacional puede ser construido para razonar sobre un mundo externo en virtud de la inclusión de un proceso

intérprete que manipule formalmente representaciones de ese mundo, también así puede hacerse a un proceso computacional

razonar sobre sí mismos (u otro proceso computacional) en virtud de la inclusión de un proceso intérprete que manipule

formalmente representaciones de sus propias operaciones y estructuras”[7].

3.2 Concepto de reflexión

La hipótesis de Smith origina el término “reflection” y sobre su traducción al español, origen y semántica hay mucha

discusión. Pattie Maes propone las siguientes ideas [9] que ayudan a aclarar el significado y que son ilustradas por las figuras

3 y 4:

Un sistema computacional es algo que razona y actúa sobre una parte del mundo llamada el dominio.

Si un sistema computacional y su dominio están vinculados de modo que un cambio en uno provoca un efecto sobre el otro,

se dice que el sistema computacional está causalmente conectado.

Un meta-sistema es un sistema computacional que tiene como dominio otro sistema computacional, llamado su sistema-

objeto, que podría ser el mismo.

Reflexión es el proceso de razonar y/o actuar sobre si mismo.

Un sistema reflexivo es un meta-sistema causalmente conectado a si mismo (su sistema-objeto es él mismo).

Fig 3. Representación de Meta Sistema

Fig 4. Representación de Sistema Reflexivo


3.3 Clasificación de reflexión

Existen diversos criterios de clasificación. El más importante es el efecto y origina los términos introspección e intercesión

[7],[9]. Ambos son formas de reflexión siendo el primero el empleado en éste trabajo.

Introspección es la capacidad que tiene un sistema computacional para observar y razonar sobre su estado.

Intercesión es la capacidad que de un sistema computacional para modificar su propio estado o alterar su propia

interpretación.

Otra clasificación que se realiza es entre estructural y de comportamiento. En la primera sólo interesa la estructura (métodos,

propiedades, tipos), mientras que en la segunda interesa la semántica (operaciones).

3.4 Introspección en Java

Muchos lenguajes de programación han aparecido como resultado de estudios de metaprogramación y otros lenguajes han

incorporado estos conceptos. Java es uno de los lenguajes que desde sus inicios utiliza introspección dado su carácter de

máquina virtual y la necesidad de la portabilidad. El paquete java.lang.reflect ofrece una colección de interfaces y clases que

permiten al programador observar sus programas e incluso invocar dinámicamente métodos que en tiempo de compilación

desconoce. Las figuras 5 y 6 muestran diagramas de clases para éste paquete que permite realizar operaciones como obtener

el nombre de la clase de un objeto, obtener un metaobjeto que describe la clase de un objeto base, conocer las propiedades y

métodos declarados con sus tipos de datos, modificadores y parámetros, invocar constructores y métodos dinámicamente, lo

cual en cierto sentido va más allá de la introspección al permitir alterar el estado del sistema base [2].

Fig 5. Diagrama de Interfaces de tipos paquete java.lang.reflect. (www.java-sun.com)


Fig 6. Diagrama de Clases de miembros de clase y paquete java.lang.reflect. (www.java-sun.com)

4 Diseño e Implementación de los Componentes

Uno de los dos problemas planteados es el de duplicidad de patrones de código. Los componentes más importantes para la

solución de éste problema son ORM y XMLConverter, que además reducen sustancialmente el trabajo de los programadores

puesto que, al emplear metaprogramación, consiguen generalizar los algoritmos de acceso a la persistencia y generación de

GUI. El otro problema es la mezcla de código HTML y Java. Para esto se propone usar XML como lenguaje conceptual que

comunique la capa de presentación con la capa Web, etiquetas personalizadas que encapsulen el acceso a los componentes

ORM y XMLConverter y XSL como lenguaje para transformar la vista conceptual XML en alguna vista de usuario como

HTML.

4.1 Componente ORM

Las operaciones de persistencia de objetos resultan ser siempre: hacer un objeto persistente (insert), modificar el estado de

objetos persistentes (update), destruir objetos persistentes (delete) y obtener objetos persistentes (get y/o load). Estas

operaciones pueden soportarse con bases de datos relacionales, bases de datos orientadas a objetos, archivos XML, etc.

Cuando una aplicación requiere de objetos persistentes lo ideal es que los solicite a un componente especializado. Puesto que

lo más común es que la persistencia se implemente con bases de datos relacionales, es necesario mapear los registros a

objetos. Se define entonces una interfaz llamada ORM, que son las siglas de Object Relational Mapping, pero su

funcionalidad no es estrictamente el mapeo de registros a objetos sino que puede tenerse cualquier otra fuente de persistencia,

como por ejemplo, archivos XML. La figura 7 muestra el diagrama de clases con la interfaz ORM y una clase que

implementa dicha interfaz para persistencia en bases de datos relacionales usando la API JDBC. Si en lugar de una base de

datos relacional se tiene una base de datos orientada a objetos, se debe proporcionar una implementación diferente pero

manteniendo la misma interface, lo cual brinda portabilidad.


Fig 7. Diagrama de clases componente ORM. (Elaborado en Visual Paradigm Community Edition)

La interfaz ofrece métodos get y load que se encargan de recuperar objetos desde la fuente persistente según cumplan con las

condiciones especificadas en los parámetros. También proporciona un único método para hacer persistente un objeto y/o

actualizarlo. Finalmente proporciona varios métodos para eliminar uno o varios objetos persistentes.

La implementación que se proporciona de la interfaz ORM usa las características de reflexión proporcionadas por el lenguaje

Java. En lenguajes que no soportan ésta característica, debería estudiarse algún mecanismo que permita simularla o conseguir

resultados similares. Inicialmente se propone que toda clase que describa objetos del dominio del sistema real, debe

proporcionar un constructor sin parámetros, declarar sus propiedades private o protected y proporcionar métodos de acceso a

dichas propiedades. Los métodos de acceso deben comenzar su nombre por el verbo inglés get (obtener) y debe seguirse por

el nombre de la propiedad. El tipo de dato de retorno de un método de acceso debe ser el compatible con el tipo de dato de la

propiedad a la cual se accede. Un método de acceso no debe recibir parámetros. Por ejemplo, para una propiedad “int

estatura”, el método de acceso debe tener la signatura “public int getEstatura(){return this.estatura;}”. Además debe

proporcionar métodos para modificar dichas propiedades. Los métodos de modificación deben comenzar su nombre por el

verbo inglés set (establecer) y debe seguirse por el nombre de la propiedad. El tipo de dato de retorno de un método de

modificación es void, no debe retornar valor. Un método de modificación debe recibir un único parámetro cuyo tipo de dato

debe ser compatible con el tipo de dato de la propiedad que modifica. Por ejemplo, para una propiedad “int estatura”, el

método de modificación debe tener la signatura “public void setEstatura(int estatura){this.estatura = estatura;}”. A una clase

con estas características se le conoce como un POJO "Plain Old Java Object". De ésta forma, el componente ORM invoca los

métodos cuyo nombre inicie con get y/o set según lo requiera para obtener objetos o modificarlos, independientemente de la

fuente de persistencia.

Para usar el componente es suficiente con instanciarlo e invocar sus métodos. Para evitar que los JSP requieran de código

Java para usar el componente, se proporciona un juego de etiquetas personalizadas, una por cada método de la interfaz.

Dichas etiquetas sirven para invocar desde una página JSP un método de ORM, de manera transparente en lo que corresponde

a la codificación. Estas etiquetas conforman el componente ORMInvoquer.


4.2 Componente XMLConverter

La arquitectura pretende que la capa Web se olvide por completo de la visualización. Para esto, se usa el lenguaje XML como

mecanismo para proporcionar vistas conceptuales cuyo aspecto gráfico final epende del navegador y de las reglas de

visualización. Puesto que la información a visualizar está encapsulada en objetos, es necesario un componente capaz de

generar fragmentos XML a partir de los objetos. Se propone una interfaz muy sencilla: 1- generar una vista simple de un

objeto que muestra sólo sus propiedades sin incluir las relaciones con otros objetos y 2- generar la vista completa de un objeto

que muestra la vista simple del objeto y la de los objetos con los que se relaciona. En la implementación del componente se

presume que las relaciones entre objetos usan las interfaces Collection e Iterator y que puede accederse a las propiedades y

relaciones mediante métodos “get”. De éste modo, usando reflexión, cuando se encuentra un método “get” se verifica el tipo

de dato de retorno, si es un tipo primitivo, un Wrapper o un String, se crea una marca con igual nombre que la propiedad a la

cual accede el método. Cuando el tipo de dato es un objeto, se obtiene recursivamente la representación XML simple de dicho

objeto. Cuando el tipo de dato es un Iterator o un Collection, se obtiene recursivamente la representación XML simple de

cada uno de los objetos contenidos en dicha estructura. Si la vista XML que se requiere es simple, se omiten los métodos

“get” cuyo retorno no es primitivo, wrapper o String.

La figura 8 muestra el diagrama de clases correspondiente. De la misma manera que en la persistencia, se proporciona un

componente con un juego de etiquetas personalizadas que permiten ocultar el código que usa el componente XMLConverter.

Estas etiquetas conforman el componente XMLInvoquer.

Fig 8. Diagrama de clases componente XML (Elaborado en Visual Paradigm Community Edition)

4.3 Componentes Invoquer

El uso de etiquetas en páginas JSP permite encapsular patrones de código requeridos para generar fragmentos HTML o

procesar objetos[3]. Puesto que se usa XML como una vista conceptual, las etiquetas pretenden que una página JSP contenga

sólo marcas. En éste sentido, se tienen una o varias marcas por cada método que ofrecen las interfaces de los dos

componentes ya descritos. El diseño de éstas marcas también contempló aspectos de navegación y concurrencia de usuarios

pero se omiten los detalles ya que no es tema central de éste documento estudiar la tecnología asociada a las Tag Library.

4.4 Componente XSL y XSLT

La visualización de un documento XML dependen del dispositivo y de las reglas de visualización. El lenguaje XSL ofrece

múltiples alternativas de conversión a formatos que van desde el HTML hasta el SWF, incluyendo formatos como el WML,

PDF, XLS, entre otros. El lenguaje XSL es declarativo y requiere de un procesador que ejecute las declaraciones de

conversión de formato. Un programa de procesamiento XSLT lee el documento XML conformando un árbol. Las hojas XSL

son un conjunto de reglas escritas en XML que establecen patrones de etiquetas sobre las cuales debe aplicarse una acción de

formateo o de transformación. Cuando el procesador XSLT encuentra un elemento xml, lo convierte en un nodo y va

conformando el árbol original del documento. Paralelamente, el procesador conforma el árbol de transformación leyendo el


documento XSL. Cuando en el árbol XSL aparece una regla de transformación, el programa XSLT busca en el árbol original

XML un nodo que concuerde con el patrón de la regla y la aplica generando un nuevo nodo que va conformando el árbol del

documento transformado. Las reglas de transformación se conocen como plantillas “templates”. Cada elemento XML puede

tener una plantilla de transformación, sólo es obligatorio que exista una plantilla para el nodo raíz. Una plantilla XSL es un

nodo XML dentro de un documento XSL, cuyo contenido indica qué se debe hacer con el contenido de un nodo cuando éste

encaje con el patrón de la plantilla. El qué hacer con el contenido de un nodo pueden ser instrucciones de transformación, de

procesamiento o de formateo. Las plantillas se pueden definir usando la marca <xsl:template match=condicion> o la marca

<xsl:template name=nombre>. La primera forma se emplea a manera de disparo automático durante el procesamiento XSLT

y la segunda puede invocarse de modo similar a un procedimiento.

La lectura de las reglas XSL y la transformación XSLT puede dejarse al cliente o realizarse en el servidor. La mayoría de los

navegadores incluyen un procesador XSLT por lo que en aplicaciones Web es recomendable descargar esta tarea a los

clientes. La visualización puede hacerse directamente en las páginas JSP pero esto implica que los programadores de

aplicaciones Web tengan que realizar tareas de diseño gráfico y de programación en el cliente como JavaScript y SWF Flash

Macromedia. El uso de XML en la capa Web y XSL en la capa del cliente permite que diseñadores gráficos expertos diseñen

la interfaz gráfica en editores profesionales en paralelo con los programadores de páginas JSP, quienes sólo saben marcas y

conocen el dominio de la aplicación.

La estructura del lenguaje XSL permite reutilizar plantillas y realizar plantillas genéricas que visualicen de la misma manera

conjuntos de nodos XML diferentes, como por ejemplo la visualización de tablas, vínculos, árboles, capas, entre otros. Los

elementos de reutilización de XSL más destacados son xsl:import y xsl:call-template, los cuales permiten agrupar conjuntos

de plantillas XSL como un componente donde la interfaz resulta ser la especificación DOM (Document Object Model) de la

W3C. Además, XPATH funciona como un lenguaje de consulta a nodos XML que en cierto sentido permite

metaprogramación en ese nivel, lo cual sigue reduciendo el trabajo de los programadores.

5 PIAGEV un Caso de Estudio

En el año 2003 se terminó el proyecto PIAGEV, Portal Institucional para el AutoAprendizaje y Gestión de la Enseñanza

Virtual, una plataforma elearning integrada al Sistema de Información Académico de la Universidad Francisco de Paula

Santander. Inicialmente PIAGEV se implementó usando Servlets, XML y XSL, pero esto dificultaba su mantenimiento y

modificación lo que llevó a utilizar JSP en el año 2006. Inicialmente se usaron marcas personalizadas para encapsular

patrones de código, las cuales incluían en su implementación pequeños usos de la API Java-Reflect. De aquí se origina el

problema propuesto y dado que en paralelo el Grupo de Investigación GIDIS realiza estudios sobre metaprogramación y en

particular reflection, se planteó la propuesta de experimentar la introducción de éstos mecanismos en la formulación de

arquitecturas dinámicas de software. La figura 9 muestra un diagrama de despliegue de PIAGEV usando los componentes

propuestos. Es posible encontrar información adicional en el sitio Web del proyecto PIAGEV y del grupo de investigación

GIDIS.


Fig 9. Diagrama de despliegue PIAGEV (Elaborado en Visual Paradigm Community Edition)

6 Conclusiones

El mecanismo de reflection proporcionado por Java ofrece la posibilidad de implementar componentes genéricos que, durante

la ejecución miren dentro de los objetos y adapten a estos su comportamiento.

En aplicaciones Web con arquitecturas basadas en MVC, incorporar reflection permite separar realmente el Modelo de la

Vista mediante un componente que puede generar vistas conceptuales XML (preferiblemente) o vistas reales HTML de los

objetos que inspecciona.

Las operaciones tradicionales de persistencia que toda aplicación Web requiere pueden ocultarse en un único componente

capaz de mapear objetos a registros en plataformas relacionales siempre que los metadatos relacionales sean equivalentes a

los metadatos de los objetos. El uso de componentes permite concentrar el esfuerzo durante el desarrollo en las etapas de

análisis y diseño que permitan implementaciones rápidas similares al ensamble de autos en la industria automotriz.

La metaprogramación como objeto de estudio además de ser un tema de gran interés en la actualidad origina diversos matices

adicionales de investigación como las arquitecturas dinámicas de software que usan metaprogramación para conseguir su

dinamismo.

Agradecimientos

Doctor Wladimir Rodriguez, Universidad de los Andes Merida Venezuela, por la revisión del primer borrador de éste artículo

durante la asignatura Desarrollo de Aplicaciones Empresariales en la Maestría en Computación. Ingeniero Oscar Alberto

Gallardo Perez, Universidad Francisco de Paula Santander Cúcuta, por su apoyo y colaboración.

Referencias

[1] Forman Ira R. y Forman Nate. Java Reflection in Action. (2005).

[2] Haapakorpi Mikam, Meta Programming In Java, (2006).

[3] Hanna Phil, JSP Reference, McGrawHill 2005.

[4] Johnson Mark, Designing Enterprise Applications Addison Wesley (2005).

[5] Maes Pattie, Concepts and Experiments in Computational Reflection OOPSLA (1987).

[6] Rodriguez Wladimir, Apuntes Maestría en Computación, Universidad de los Andes Mérida Venezuela 2006.

[7] Ortín Soler Francisco, Diseño de Máquinas abstractas basadas en Reflectividad Computacional (1999)

[8] Ortín Soler Francisco, Diseño de un Sistema de Persistencia Implícita mediante Reflectividad Computacional. (2000)

[9] Tanter Erik, Más allá de la orientación al objeto Reflexión, metaprogramación y programación por aspectos.


DE LOS DATOS AL

CONOCIMIENTO

La Evolución Digital Inteligente.

Por: Jaime Alonso Parra Giraldo.

Ingeniería de sistemas - Universidad Simón Bolívar

INTRODUCCIÓN

La minería de datos1 a dado lugar a una paulatina sustitución del análisis de datos dirigido a la verificación por un enfoque de

análisis dirigido al descubrimiento del conocimiento. La principal diferencia entre ambos se encuentra en que en el último se

descubre información sin necesidad de formular previamente una hipótesis.

La aplicación automatizada de algoritmos de minería de datos permite detectar fácilmente patrones en los datos, razón por la

cual esta técnica es mucho más eficiente que el análisis dirigido a la verificación cuando se intenta explorar datos procedentes

de repositorios de gran tamaño y complejidad elevada.

Dichas técnicas emergentes se encuentran en continua evolución como resultado de la colaboración entre campos de

investigación tales como: bases de datos, reconocimiento de patrones, inteligencia artificial, sistemas expertos, estadística,

visualización, recuperación de información y computación de altas prestaciones.

Las técnicas de Data Mining (Minería de Datos) son el resultado de un largo proceso de investigación y desarrollo de

productos. Esta evolución comenzó cuando los datos de negocios fueron almacenados por primera vez en computadoras, y

continuó con mejoras en el acceso a los datos, y más recientemente con tecnologías generadas para permitir a los usuarios

navegar a través de los datos en tiempo real. Data Mining toma este proceso de evolución más allá del acceso y navegación

retrospectiva de los datos, hacia la entrega de información prospectiva y proactiva. La Minería de Datos está lista para su

aplicación en la comunidad de negocios porque está soportado por tres tecnologías que ya están suficientemente maduras:

� Recolección masiva de datos

� Potentes computadoras con multiprocesadores

� Algoritmos de Data Mining

Para introducirnos en la comprensión del Descubrimiento de Conocimiento y entender la importancia de la Minería de Datos

dentro del mismo, analizaremos el siguiente enfoque que nos dará una visión mas clara para así entender el presente artículo:

Que es la Minería de Datos?

1 Minería de datos es la traducción al español de las palabras en inglés Data Mining.


• Reconocer el valor implícito en la gran cantidad de datos almacenados en los sistemas de información de las

organizaciones.

• Los datos dejan de ser un “producto inerte” para convertirse en materia prima que necesita ser procesada, para así

obtener un “producto valioso” como lo es el conocimiento.

• El conocimiento se convierte en una herramienta útil e importante para la toma de decisiones en el área de cualquier

empresa, sobre la cual se han obtenido los datos.

Luego de analizar el anterior enfoque, estudiaremos el Descubrimiento de Conocimiento, dividido en tres partes:

1. Explicar el origen o descubrimiento del conocimiento.

Se puede decir que actualmente las organizaciones luchan por mantener un alto grado de competitividad y para lograr esto

juega un papel muy importante la información que éstas manejan; pero más allá de la información que posean, la clave está

en la estructura y la sistematización de la misma en procura de convertirla en conocimiento.

Como la finalidad de las empresas es mejorar sus resultados cumpliendo sus objetivos organizacionales, la información que

éstas poseen en sí no representa ninguna ventaja, en cambio si se aplica la sistematización necesaria aplicando las tecnologías

adecuadas de KDD (Descubrimiento de Conocimiento) entonces se generará un valor agregado para la organización como es

el conocimiento útil para la toma de decisiones.

Según el modelo de Newman (1997) :

Sostiene que el control y monitorización de los procesos solo produce datos, pero el análisis de dichos datos realizado con

técnicas estadísticas o de minería de datos y su contextualización es lo que proporciona información.

Cuando finalmente, la información es interpretada, esta se transforma en conocimiento útil.

De lo anterior podemos deducir que si deseamos obtener un valor agregado como lo es el conocimiento, se debe aplicar

alguna técnica o herramienta capaz de obtener información útil a partir de datos almacenados.

2. Diferenciar el tipo de conocimiento que se utiliza o genera.

Es importante reconocer el impacto que tienen las tecnologías de la información y comunicación en las organizaciones al

igual que la gestión del conocimiento que se aplica en las mismas buscando mejorar cada vez mas los resultados obtenidos.


Entonces, para alcanzar el mejoramiento de los resultados, las organizaciones aplican técnicas o utilizan herramientas

informáticas para la gestión del conocimiento que responde a enfoques y organizaciones diferentes.

Por lo tanto puede decirse que no existe una única combinación de técnicas y herramientas, ni una metodología exclusiva para

lograr con éxito el proceso de gestión del conocimiento, pero es importante resaltar que técnicas como la minería de datos se

han convertido en un aliado de la gestión del conocimiento a la hora de analizar la información que ya tienen las empresas en

sus bases de datos.

Para definir la palabra conocimiento, existen conceptos muy parecidos que dificultan su entendimiento. Por lo tanto

podríamos decir que conocimiento no es lo mismo que datos, ni lo mismo que información. Entonces los datos son los

elementos base de la pirámide del conocimiento y al conjunto de datos organizados y analizados en un contexto determinado

lo denominamos información.

Es de aclarar que recopilar los datos, organizarlos e incluso analizarlos es algo que puede hacer el software informático, pero

yo considero que al conocimiento (desde el punto de vista humano) de momento no llegan los computadores, por que en sí el

conocimiento es identificar, estructurar y utilizar la información para obtener un resultado, aplicando la intuición y sabiduría

propia de la persona. La capacidad de interpretar esos datos es lo que provoca que la información se convierta en

conocimiento.

3. Describir la función que cumple la minería de datos como fuente de descubrimiento y generación de

conocimiento para las futuras tomas de decisiones en las empresas.

Cuando se utiliza la minería de datos en un determinado proyecto, el proceso que se está realizando es una “extracción no

trivial de información implícita, previamente desconocida a partir de los datos”, a nivel del cocimiento explícito,, con el fin

de descubrir patrones, relaciones, reglas, asociaciones, tendencias etc., que deberemos interiorizar, para luego exteriorizarlo

en la toma de decisiones.

Es de resaltar que la forma de analizar los datos por parte de la minería de datos es bastante parecida, independientemente de

la técnica que utilicemos y destacando que cada proceso de minería de datos es un caso diferente, podremos adaptar y

modificar estos pasos según las propias características del proyecto en el que nos encontremos inmersos:

• Selección y procesado de los datos:

Por lo general los datos que residen en una base de datos no se encuentran en el formato mas adecuado para nuestro

algoritmos, por lo que será necesario realizar diferentes operaciones sobre ellos. Por ejemplo podemos realizar un filtrado de

valores incorrectos (inadecuados), o un muestreo de la población total de los datos para así trabajar con un número reducido

de datos, este muestreo puede ser aleatorio o establecer que cumplan unas características determinadas, también se puede

reducir el número de valores a través de técnicas de redondeo, clustering (agrupación) etc.


• Selección de características:

Una vez determinada la población sobre la que vamos a realizar nuestra investigación nos encontraremos con que el número

de datos a trabajar es muy amplio, así que aplicamos una selección de características de los datos, es decir determinaremos

aquellas variables que nos interesan, con el fin de simplificar los datos y realizar el proceso de la forma mas sencilla posible.

Se pueden utilizar diferentes técnicas estadísticas o métodos gráficos que nos permitan observar las relaciones existentes entre

las variables.

• Uso de un algoritmo de extracción de conocimiento:

En esta parte aplicaremos la técnica de minería de datos que hayamos determinado anteriormente, para obtener un modelo de

conocimiento con los patrones de comportamiento y las reglas de asociación entre las variables.

• Interpretación y evaluación de los resultados:

Se analizan y verifican si los resultados obtenidos son coherentes y se comparan con los obtenidos por los análisis estadísticos

y de visualización gráfica; luego se determina si son novedosos y si aportan un nuevo conocimiento que puedan inferir en las

decisiones de la organización.

En el caso de que los resultados obtenidos difieran, se debe elegir aquel que mas se ajuste. En el caso de que ningún

resultado satisfaga las expectativas se debe iniciar de nuevo el proceso.

• Consideraciones:

→ El manejo de grandes volúmenes de información, exigen de una arquitectura robusta en velocidad, procesamiento y

almacenamiento de la información.

→ Antes de emprender la aplicación de un proceso de minería de datos se debe analizar de forma clara, precisa y concreta

cuales son nuestros objetivos, que datos se van a explorar y cuáles son los patrones o conocimientos que deseamos

generar.

→ Antes de transmitir el tipo de conocimiento descubierto hay que verificar, interpretar e interiorizar los resultado

obtenidos, ya que de todas formas para la toma de decisiones importantes, los lideres de las organizaciones no desean

correr riesgos, aunque es de considerar hoy en día que las diferentes técnicas de inteligencia artificial están madurando

cada vez mas y se están combinando con herramientas KDD que van embebidas en software de gran importancia, para así

generar aplicaciones inteligentes, confiables y eficientes.

BIBLIOGRAFÍA

HERNÁNDEZ, José – RAMÍREZ, María – FERRI, Cesar. Introducción a la Minería de Datos. Editorial Prentice Hall.

Madrid 2004.

EDELSTEIN, Herbert. Two Crows Corporation [on line]. “Introducción to Data Mining and Knowledge Discovery, Third

Edition”. [Maryland U.S.A] 1999. Disponible desde internet: URL:http://www.twocrows.com/booklet.htm.

STATSOFT, Inc. Data Mining Techniques. [on line]. [Tulsa Oklahoma U.S.A]. Disponible en

internet:<URL:http://www.statsoft.com/textbook/stdatmin.html>.

THEARLING, Kurt. An Introduction to Data Mining. [on line]. Disponible en internet: <URL:

www.thearling.com/text/dmwhite/dmwhite.htm>.


EL PROBLEMA DEL LONGEST COMMON

SUBSEQUENCE: EXTENSIONES Y

ALGORITMOS

Wilson Soto * wesotof @unal.edu.co

Yoan Pinzón *

[email protected]

Abstract—This survey summarize the problem Longest Common Subsequence (LCS), some his differents extensions and some his differents algorithms techniques that given solution to the problem. A table of classification chronological for author is included, with his respective complexity of time and space of the solution. The final show some applications of LCS, the works to developing to future and conclusions after the production of the survey. Resumen—El estado del arte resume el problema del Longest Common Subsequence (LCS), algunas de sus diferentes extensiones y algunas de las diferentes técnicas de algoritmos que dan solución al problema. Se incluye una tabla de clasificación cronológica por autor, que contiene la respectiva complejidad de tiempo y espacio de la solución. Al final se muestran algunas de las aplicaciones del LCS, los trabajos a desarrollar a futuro y las conclusiones después de la elaboración del estado del arte.

Términos generales

Algoritmos, Secuencia, String.

Palabras Clave

Alineamiento, Distancia, Frontera, Longest Common Subsequence, Puntos Dominantes, Similitud.

* Universidad Nacional de Colombia (Grupo ALGOS – UN), Bogotá.

I. INTRODUCCIÓN

El Longest Common Subsequence es una de las derivaciones del paradigma del string matching, el approximate

string matching, que simplemente es una comparación exacta de cadenas que permite errores.

El problema del Longest Common Subsequence (LCS) o en español la secuencia común más larga es uno de los

modelos computacionales más usados, pues sirve como medida de similitud entre un conjunto de secuencias por

medio de su longitud, que se muestra a través de los símbolos que contiene.

Las aplicaciones que tiene el longest common subsequence son entre otras la compresión de datos, reconocimiento

sintáctico de patrones, procesamiento XML, recuperación WEB, comparación de archivos y bioinformática [36].

El artículo busca dar una clasificación de los algoritmos desarrollados para dar solución a las extensiones del longest

common subsequence desde el punto de vista de las técnicas más comúnmente usadas. Un mapa conceptual que


puede resumir la idea básica de este estado del arte se ve en la Figura 1. Por ello se presenta en la sección II los

conceptos básicos y la notación necesaria para entender los problemas. La sección III explica las técnicas usadas

para dar solución a los problemas, incluyendo los algoritmos y estudios que se han desarrollado para las diferentes

extensiones que aquí se mencionan asociadas al problema del longest common subsequence. La sección IV pretende

dar una visión práctica de donde aparece el problema e intenta descubrir las posibles aplicaciones y sobre todo un

campo de investigación. La sección V muestra las necesidades de investigación que son actualmente requeridas y en

las que se puede desarrollar un estudio más profundo.

II. EL PROBLEMA DEL LONGEST COMMON SUBSEQUENCE

A. Conceptos

Las siguientes definiciones son necesarias para entender este articulo:

La distancia entre dos strings x y y es el mínimo costo de operaciones para transformar x en y. El costo de una

secuencia de operaciones es la suma de los costos de las operaciones individuales.

Alineamiento significa insertar espacios tal que letras iguales se alineen con espacios y evitando que estos se

alineen, pero aceptándolos al comienzo o final del string (Ver Figura 1).

G C A T - A T T -

- C A T G - T T G

Figura 1: Alineamiento

Dado un alineamiento se calcula una medida de similitud, esta medida tiene tres posibilidades:

De letra-letra, error letra-letra y letra-espacio(o viceversa).

Los tipos de alineamiento se resumen en [16]. Algunos de los algoritmos de alineamiento más conocidos son:

Needleman y Wunsch (1970), SW (Smith & Waterman, 1981), FASTA (1988) y BLAST (1990) que son

relacionados en [9] y [12]. La similitud de secuencias tiene diversas aplicaciones, entre otras ensamblaje de

fragmentos, agrupamientos, minería, comparación de genomas, análisis fitogénetico, homologías1 funcionales y

estructurales. Entre las medidas de similitud se encuentran la distancia de Hamming, La distancia de Levenshtein, la

distancia de Episodio y el Longest Common Subsequence. El Longest Common Subsequence permite únicamente

inserciones y eliminaciones, todas de costo 1. El nombre de esta distancia refiere a que esta medida representa la

longitud más larga de acoplamiento entre los caracteres que pueden estar entre dos strings, teniendo en cuenta el

orden de las letras, caracteres o símbolos.

1 proteínas que tienen un origen evolutivo común


Figura 1. Mapa conceptual del problema del

longest common subsequence

B. Definición

La siguiente es la notación formal usada :

Σ = Conjunto de elementos llamados símbolos, caracteres o letras. Por ejemplo Σ = {A, C, G, T}.

String o palabra = Secuencia finita de símbolos que pertenece a un alfabeto. Función s de {1,...,n} sobre Σ.

s = a1a2 ... an donde ai = s(i) ∈ Σ.

ε = Un string sin ningún símbolo o carácter.

Σn = Conjunto de strings o palabras de longitud n. Por ejemplo Σ 3 = {LAS, ESS, FGR, DED}.

Σ* = Conjunto de strings sobre Σ. Por ejemplo Σ* = {ACT, TAC, TAG, ACGT, CT, AG, ACTG, GG, AA, ε}.

|s| = Longitud de un string s. Por ejemplo s = AGCATT, |s| = 6 o si s = ε, |s| = 0.

Prefijo de s = string v tal que s = vt para ciertos t ∈ Σ*.

Sufijo de s = string v tal que s = tv para ciertos t ∈ Σ*.

k = Máximo error permitido. k ∈ R.

d = Σ* x Σ* → R es un función de distancia.

Inserción = Insertar un carácter en un string. Por ejemplo la operación de inserción sobre el string s = TCA

adicionando la letra G, es s’ = TCGA.

Eliminación = Eliminar un carácter de un string. Por ejemplo la operación de eliminación sobre el string s = TCGA

eliminando una letra, es s’ = TGA.

Sustitución = Reemplazar una letra en un string. Por ejemplo la operación de sustitución sobre el string s = AATC

reemplazando una letra por otra, es s’ = ATTC.

Con lo anterior, la definición del problema del LCS consiste en:

Dado Σ y las secuencias S1, S2 ∈ Σ*,|S1| = n y |S2| = m (m ≤ n), LCS(S1, S2) es una secuencia W tal que:


1. ∀i, 1 ≤ i ≤ |W| - 1,

∃j, j’: 1≤ j < j’ ≤ | S1 |, ∃k, k’: 1 ≤ k ≤ k’ ≤ | S2 | tal que

W[i] = S1[j] = S2[k], y

W[i+1] = S1[j’] = S2[k’];

2. ∃ W’ ∈ Σ* : (1) y |W’| > |W|

S2 es una subsecuencia de S1 si esta puede ser obtenida desde S1 removiendo algunos de estos símbolos.

Dado S un conjunto de secuencias, S es una secuencia común de S si esta es una subsecuencia de cada secuencia en

S.

El problema del longest common subsequence (LCS) se resume como: sean dos palabras w y s. Se dice que s es

una subsecuencia de w cuando se puede obtener s a partir de w borrando algunas letras (posiblemente todas o

ninguna) [18], [20] y [38]. Ejemplo:

Dadas las secuencias S1 y S2:

S1= 1 0 0 2 3 2 1 1 0 2 2 2 3 3 1 0 0 1

S2= 0 1 1 1 3 3 3 0 2 1 2 1 1 0 1 2 1

Algunas de las subsecuencias comunes de S1 y S2 son:

sc1= 1 3 2 1 2 1

sc2= 0 1 1 3 3 1

sc3= 0 1 1 0 2 2 1 0 1

sc4= 1 0 2 2 1 1 0 2 1

Las subsecuencias comunes más largas son sc3 y sc4 de los dos strings dados y la longitud es |LCS(S1, S2)| = 9.

C. Complejidad del problema

EL LCS es un problema que puede ser resuelto en tiempo polinomial con programación dinámica para dos strings, o

para algún número fijo de strings, pero este se convierte en un problema “NP-Hard” en general para un número

arbitrario k de strings. En [24] muestra un capítulo completo a la complejidad del algoritmo y la relación con la

teoría NP, que se resume a un problema de maximización siguiente: "Dado un lenguaje finito no vacío X, encontrar

una subsecuencia común de X de longitud máxima”. Algunos trabajos ya han estudiado el tema como [3] y [10], que

tratan el tema con soluciones heurísticas que dan solución a la subsecuencia común más larga en tiempo polinomial.


D. Extensiones

1. All Longest Common Subsequence

El problema del all longest common subsequence (ALCS) consiste en buscar todas las subsecuencias comunes más

largas entre X y algún substring de Y.

Los estudios completos sobre los límites en tiempo de ejecución sobre todos los algoritmos que generan all longest

common subsequence distintos y all longest common subsequence embebidos (posiciones en ambos strings para los

cuales los caracteres del LCS correspondan) se encuentran [1], [25], [26], [27] y [29].

Una de las variaciones presentadas en este tipo de extensión del longest common subsequence es el all semi-local

longest common subsequence [42], donde cada string es comparado contra todos los sufijos del otro string.

2. Length Longest Common Subsequence

La longitud de un longest common subsequence (LLCS) de dos o más strings es una útil medida de su similitud, que

se usa para saber tanto sea posible acerca de la longitud esperada de un par de strings aleatorios. La estimación de

esta longitud esperada promueve algunos problemas de interés combinatorio que son estudiados en [20], [21] y [41].

En [32] algunos de los algoritmos desarrollados para solucionar esta extensión del longest common subsequence

tiene que ver con técnicas de programación dinámica, naive recursive (recursión ingenua) y programación dinámica

con recursión. Otras investigaciones como en [34] y [35] proponen una solución basada en tipos de algoritmos de

paralelismo aplicados a modelos de procesamiento.

3. Constrained Longest Common Subsequence

Dados los strings S1, S2 y P, el problema constrained longest common subsequence (CLCS) para S1 y S2 con respecto

a P es buscar un longest common subsequence LCS de S1 y S2 tal que P es una subsecuencia de este LCS.

En los trabajos [4],[22],[39] y [40] relacionados con el estudio de este tipo de extensión del longest common

subsequence, mencionan el concepto de grafo de edición, este surge a partir de la solución del longest common

subsequence de la matriz de programación dinámica (Ver Figura 2). El grafo de edición es un grafo en el que se

presentan las celdas como nodos y los vértices como las operaciones, con un tamaño de (n+1)(m+1) puntos (i, j) para

0 ≤ i ≤ n, y 0 ≤ j ≤ m como vértices. El peso de los arcos corresponde al costo de las operaciones, inserción (i-1, j),

eliminación (i, j-1) y operaciones de igualación o reemplazo (i-1, j-1). La distancia de edición entre los dos strings es

la ruta más corta desde el vértice [0, 0] (esquina superior izquierda de la matriz) al vértice [m, n] (esquina inferior

derecha de la matriz). Para el ejemplo, la distancia es 5 y el LCS(x, z) = “ACDBC” (Ver Figura 3).

4. Shortest Common Supersequence

El problema del shortest common supersequence (SCS) consiste en buscar para un conjunto dado de strings P, el

más pequeño string el cual es una supersecuencia de cada string de P.


Dadas dos secuencias u y v, la secuencia u es una supersecuencia de v si v es una subsecuencia de u. Si u ∈ Σ* es

una supersecuencia común de v1,...,vn si, para cada i = 1,...,l, secuencia u es una supersecuencia de vi. Entonces u es

una supersecuencia de longitud mínima si u es una supersecuencia común de longitud mínima posible [19].

Aunque este problema es dual con el problema del longest common subsequence, muy pocos algoritmos han sido

desarrollados, autores como Itoga en 1981 y Fraser e Irving en 1995 han tratado el problema, en [43] y [44] también

se aborda este tipo de extensión.

A C D Y B A C

0 0 0 0 0 0 0 0A 0 1 1 1 1 1 1 1C 0 1 2 2 2 2 2 2D 0 1 2 3 3 3 3 3R 0 1 2 3 3 3 3 3B 0 1 2 3 3 4 4 4C 0 1 2 3 3 4 4 5

A C D Y B A C

A

C

D

R

B

C

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1 1 1 1 1 1 10

1

1

1

1

1

1

0

1

1

1

0

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

0

1

1

1

1

1

1

0

1

1

1

0

Figura 2. Matriz de programación dinámica y grafo de edición asociado para x = “ACDYBAC” y z = “ACDRBC”

A C D Y B A C

A C D R B C

Figura 3. Longest common subsequence entre

x = “ACDYBAC” y z = “ACDRBC”

5. Longest Common Increasing Subsequence

Un problema similar al LCS es el problema de Longest Increasing Subsequence (en castellano, Subsecuencia

Creciente Más Larga), el cual consiste en, dada una permutación P de los números 1,2,...,n, encontrar el largo

máximo que puede tener una subsecuencia de P que sea creciente. Por ejemplo, si P = (6,2,8,5,7,4,1,9,3) entonces

una LIS (también la única) es R = (2,5,7,9). Un problema de LIS se reduce a uno de tipo LCS. Para ello,

interpretamos una permutación R = (R1,R2,...,Rn) sobre los números 1,2,...,n como la palabra R1R2...Rn. Es fácil ver

que una LIS entre P y Q corresponde a una LCS entre P y Q = (1,2,...,n). Esta variante es ampliamente estudiada en


[14] y [15], además mencionan una extensión de particular del longest common increasing subsequence, el LCWIS

(longest common weakly-increasing subsequence) que considera, un limite y no subsecuencias estrictamente

incrementales.

6. Exemplar Longest Common Subsequence

Es una generalización del problema del longest common subsequence, donde las secuencias de entrada son sobre la

unión de dos conjuntos disyuntos de símbolos, un conjunto de símbolos obligatorios y un conjunto de símbolos

opcional. Esta extensión tiene una acercamiento heurístico el cual es básicamente una restricción al problema de

alineamiento de un string.

El Exemplar Longest Common Subsequence es un conjunto S de secuencias sobre un alfabeto Ao U Am, donde Ao es

el conjunto de símbolos opcionales y Am es el conjunto de símbolos obligatorios. El conjunto Ao y el conjunto Am son

disyuntos, la salida es un secuencia común más larga de todas las secuencias en S y conteniendo todos los símbolos

obligatorios [10]. Algunas de las versiones del Exemplar longest common subsequence se ven en la Tabla I.

Tabla I

Versiones del ELCS

Nombre ProblemaOcurrencias de

símbolos mandatorios

Ocurrencias de símbolos opcionales

ELCS(1,<=1) exactamente 1 a lo sumo 1ELCS(1) exactamente 1 sin restricciónELCS(>=1,<=1) al menos 1 a lo sumo 1ELCS(>=1) al menos 1 sin restricción

7. Otras variantes del Longest Common Subsequence

Estas variantes son relacionadas en [30], introduciendo la noción de gap-constrains en LCS. Esta extensión del

longest common subsequence ofrece la posibilidad de manipular gap-constraints entre las igualdades consecutivas

en medio de las secuencias y además provee la herramienta de manipular problemas de búsqueda donde no todas las

posiciones de este sean importantes. Las siguientes son las definiciones de otras variantes del longest common

subsequence:

Dado un string X[1..n] = X[1] X[2] ... X[n] y una subsecuencia S[1..r] = S[1] S[2] ...S[r] de X, se define una

secuencia de correspondencia de X y S, C(X, S) = C[1] C[2]...C[r] si es una secuencia estrictamente incremental de

enteros tomando desde [1, n] tal que S[i] = X[C[i]] para todo 1≤ i ≤ r.

Dado X y una de sus subsecuencias S, C(X, S) puede no ser única.

El LCS con espacio fijo (FIG), se define como buscar la subsecuencia común fija espaciada (fixed gapped) de

máxima longitud entre dos strings X y Y, si existe una secuencia de correspondencia fija espaciada CFG(k) (X, S) y


CFG(k) (Y, S). Una secuencia de correspondencia fija espaciada de un string X de longitud n y una subsecuencia S de

longitud r, con respecto a un entero dado K, se da, si y solo si tiene C[i] - C[i-1] <= K + 1 para todo 2 ≤ i ≤ r.

El LCS con espacio elástico (ELAG), se define como buscar la subsecuencia común elástica espaciada (elastic

gapped) de máxima longitud entre dos strings X y Y, si existe una secuencia de correspondencia elástica espaciada

CFG(k) (X, S) y CFG(k) (Y, S). Una secuencia de correspondencia elástica de un string X de longitud n y una

subsecuencia S de longitud r, con respecto a enteros dados K1 y K2, K2 > K1, se da, si y solo si se tiene K1 < C[i] -

C[i-1] ≤ K2 + 1 para todo 2 ≤ i ≤ r.

El LCS con espacio rígido fijo (RIFIG), se define como buscar la subsecuencia común dados dos strings X[1..n] =

X[1] X[2] ... k[n] y Y[1..n] = Y[1] Y[2] ... Y[n] y un entero K y una subsecuencia común S[1..r] = S[1] S[2] ... S[r] de

X y Y, si existe una secuencia de correspondencia espaciada fija CFG(k) (X, S) y CFG(k) (Y, S) tal que para todo 2 ≤ i ≤

r.

El LCS con espacio rígido elástico (RELAG), se define como buscar la subsecuencia común dados dos strings

X[1..n] = X[1] X[2] ... X[n] y Y[1..n] = Y[1] Y[2] ... Y[n] y un entero K y una subsecuencia común S[1..r] = S[1] S[2]

... S[r] de X y Y, si existe una secuencia de correspondencia espaciada fija CFG(k) (X, S) y CFG(k) (Y, S) tal que para

todo 2 ≤ i ≤ r.

III. TÉCNICAS DE SOLUCIÓN Y ALGORITMOS

La clasificación mostrada en la Tabla II, reúne los algoritmos realizados para dar solución al problema del LCS y sus

extensiones, relacionando las técnicas usadas.

Las técnicas usadas están basadas en la división realizada en [33], las cuales son: Programación Dinámica (peor caso

y caso promedio), Autómatas Finitos, Filtramiento y Paralelismo de Bits (basado en autómata y programación

dinámica). Los algoritmos que dan solución al longest common subsequence son tomados de [2] y [20] y los

algoritmos relacionados a dar solución a las extensiones son tomados de las referencias en las que se encuentra la

definición de cada extensión.

1. Programación dinámica

En la programación dinámica, la solución propuesta usa un algoritmo que construye una matriz D[0..m, 0..n] donde,

Di,j representa el LCS para x1..i y z1..j. Cada celda es calculada según los vecinos superior, izquierdo, superior

izquierdo de la celda. La matriz D es calculada de la siguiente manera (Ver Figura 5):

Di, j = 0 si i =0 o j = 0

Di, j = D[i-1, j-1] + 1si xi = zj

Di, j = max{D[i-1, j], D[i,j-1]}si xi ≠ zj


Y la distancia de edición es la celda D(m, n).

Por ejemplo: Los strings x = “CTACTAATA” y z = “ATCGTT”

C T A C T A A T A

0 0 0 0 0 0 0 0 0

A 0 0 0 1 1 1 1 1 1 1T 0 0 1 1 1 2 2 2 2 2

C 0 1 1 1 2 2 2 2 2 2G 0 1 1 1 2 2 2 2 2 2T 0 1 2 2 2 3 3 3 3 3

T 0 1 2 2 2 3 3 3 4 4

Figura 5. Matriz de Programación dinámica

|LCS(x, t)| = D(6, 9) = 4, para determinar la subsecuencia común más larga entre las cadenas dadas se utiliza los

conceptos de frontera y puntos dominantes [8]. La frontera no es más que la delimitación de los números similares

dentro de la matriz, como se ve en la figura las líneas gruesas y los puntos dominantes son las esquinas de esas

fronteras. Para saber cual es la subsecuencia común más larga se recorre desde la esquina de la frontera inferior

derecha buscando las esquinas o puntos dominantes que están a la izquierda y por encima al punto dominante

anterior. En el ejemplo, empezamos con 4 ([T,T] posición [6,8]) luego pasamos a la frontera 3 ([T,T] posición [5,5])

luego a la 2 ([C,C] posición [3,4]) y por último a 1 que puede ser ([T,T] posición [2,2]) o (A,A posición [1,3]).

Entonces el LCS(x, t) = “ACTT” o “TCTT”.

El algoritmo que genera la matriz de programación dinámica es el siguiente:

Algoritmo 1 DP

LCS(a, b) {m=|a|, n=|b|}

for i ← 0 to m do D[i, 0] ← 0

for j ← 0 to n do k[0,j] ← 0

for i ← 1 to m do

for j ← 1 to n do

if ai = bj then L[i,j] ← L[i-1,j-1] + 1

else

if D[i,j-1] > D[i-1,j] then

D[i,j] ← D[i,j-1]

else D[i,j] ← D[i-1,j]


endfor

endfor

En este tipo de técnica de solución se puede determinar la distancia de edición y las subsecuencias comunes y en

consecuencia la más larga, el algoritmo que construye la matriz tiene complejidad en tiempo de ejecución de O(nm)

y el espacio requerido es O(m). El algoritmo de búsqueda de texto de Hirschberg toma un tiempo de ejecución O(nl

+ n log s) y espacio O(d + n) basado en los puntos dominantes [2] y [29].

Un ejemplo de solución dentro de este tipo de técnica es el algoritmo de solución del ALCS (all longest common

subsequence) se encuentra el mencionado en [26], con tiempo de ejecución de O(m) y espacio O(m):

Algoritmo 2 ALCS – DP

LCS(a,b) {m=|a|, n=|b|}

for j ← 0 to n do

for i ← 0 to m do

if i = 0 or j = 0 then D[i, j] 1

else

D[i, j] ← 0

if ai = bj then D[i, j] ← D[i - 1, j - 1]

else

if L[i - 1, j] = L[i, j] then

D[i, j] ← D[i, j] + D[i - 1, j] endif

if L[i, j - 1] = L[i, j] then

D[i, j] ← D[i, j] + D[i, j - 1] endif

if L[i - 1, j - 1] = L[i, j] then

D[i, j] ← D[i, j] - D[i - 1, j - 1] endif

endif

endif

endfor

endfor


Una de la extensiones de esta técnica es la técnica Sparse dynamic programming (programación dinámica esparcida)

que se estudia en [6], y básicamente es una técnica diseñada para el mejoramiento de algoritmos en el análisis de

secuencias, que funciona dado un conjunto de recurrencias de programación dinámica para calcular la matriz. Se usa

un conjunto esparcido de las entradas a la matriz que son de importancia, proporcionando la ventaja de producir

algoritmos que tienen tiempo de ejecución dependiente sobre el tamaño del conjunto esparcido mejor que sobre el

tamaño de la matriz de programación dinámica.

2. Autómata Finito

Un autómata finito es una máquina finita de estados donde para cada par de estados y símbolos de entrada, hay una y

solo una transición para un nuevo estado, además es determinista si las transiciones son conocidas y dados algunos

datos de entrada, se sabe que transición realizará la máquina .

El grafo de edición sobre un string S, es un autómata finito determinista que tiene la capacidad de reconocer todos

los substrings de S. Un autómata de sufijos no determinista reconoce algún sufijo para un string S (Ver Figura 6).

Ahora consideremos el anterior autómata con errores, donde cada fila denota el número de errores visto (la primera

fila cero, la segunda fila uno, etc.). Cada columna representa la igualación a un prefijo de patrón. Las flechas

horizontales representan la igualación a un carácter, todas las otras flechas incrementan el número de errores, al

moverse a la próxima fila, las flechas verticales insertan un nuevo carácter en el patrón y las flechas diagonales

representan el reemplazo o eliminación de un carácter del patrón. La flecha inicial que hace un bucle sobre el primer

nodo, indica una igualación para iniciar en cualquier parte en el texto (Ver Figura 7).


Tabla II

Complejidad de algoritmos para solucionar el Longest Common Subsequence y sus extensiones

TÉCNICA AÑO TIEMPO ESPACIO AUTOR

PD 1974 O(mn) O(mn) Wagner - FisherPD 1975 O(mn) O(n) Hirschberg

PD 1977 O((n+R) log n) O(R+n) Hunt - Szymanski

PD 1977 O(Ln + n log n) O(Ln) Hirschberg

PD 1977 O(L(m - L)log n) O((m - L)² + n) HirschbergPD 1980 O(n max{1, m/log n}) O(n²/log n) Masek - PatersonPD 1982 O(n(m - L)) O(m²) Nakatsu - Kambayashi - YajimaPD 1984 O(Lm log(n/L) + Lm) O(Lm) Hsu DuPD 1985 O(Em) O(E min{m, E}) UkkonenPD 1986 O(kn) O(n) Landau - VishkinPD 1986 O(n + m log n + D log (mn/D)) O(R+n) ApostolicoPD 1987 O(n(m - L)) O(n) Kumar - RaganPD 1987 O(Lm + n) O(D + n) Apostolico - GuerraPD 1990 O(n(m - L)) O(n) Wu - Manber - Myers - MillerPD 1990 O(n + min{D, Lm}) O(D + n) Chin - PoonPD 1992 O(n(m - L)) O(n) Apostolico- Browne - GuerraPD 1992 O(Lm) O(n) Apostolico- Browne - GuerraPD 1992 O(n + D log log min{D, mn/D}) O(D + m) Eppstein - Galil - Giancarlo - GiuseppeA 1996 O(mn/log n) O(n) Wu - Manber - Myers

A 1995 O(min(3m, m(2mt)k, (k+2)m-k(k+1)!)) t numero estados Melichar

F 1999 O(kn log(m)/w) - Baeza Yates - NavarroF 1990 O(n log |ΣP| + pm) - Grossi - LuccioPB - NFA 1996 O( k(m - k)/w n) peor caso O( k² / w n) promedio - Baeza Yates - NavarroPB - PD 1994 O(nm/log(δ) / w) - WrightPB - PD 1999 O( m/w n)peor caso O( k / w n)promedio - MyersPD 2006 O(R log log n + n) θ(max{R, n}) Iliopoulos - RahmanPD 2002 O(2mn) O(mn) KunklePD 2003 O(mn) O(m) GreenbergA 2006 O(mn/log(m+n)) O(m+n) TiskinPD 1992 - - SankoffPD 2005 O(L[patrón]* n²m²) O(L[patrón]*nm) Abdullah - OmerPD 2005 O(k(mL + R) + n) O(Rk) DeorowiczPD 2006 O(pR log log n + n) θ(max{R, n}) Iliopoulos - RahmanPD 1975 O(mn) O(m+n) Hirschberg

PD 2002 O(2mn) - KunklePD 2002 O(mn) - KunklePD 2002 O(mn) θ(mn) KunklePB 1993 O(m+n+1) O(m+n) Mi - RahmanPD 2004 O(mn) O(mn) Yang - Huang - ChaoPD 2005 O((m + nl ) log log δ + Sort (m)) O(m) Brodal - Kaligosi - Katriel - Kutz

LCWIS PD 2005 O(m + n log n) para alfabeto de 2 y 3 letras - Brodal - Kaligosi - Katriel - KutzELCS A 2006 - - Bonizzoni - Della Vedova - Dondi - Fertin - Vialette SCS PD 1995 O(k) - DnacikFIG PD 2006 O(n² + R log log n) θ(R) Iliopoulos - Rahman

ELAG PD 2006 O(n² + R log log n) θ(max(R,n)) Iliopoulos - RahmanRELAG PD 2006 O(n² + R(k2 + k1)) θ(n²) Iliopoulos - RahmanRLCS PD 2006 O(n²) θ(n²) Iliopoulos - RahmanRIFIG PD 2006 O(n²) θ(n²) Iliopoulos - Rahman

LCIS

LLCS

ALCS

CLCS

LCS

δ = tamaño del alfabeto;

A = Autómata Finito No Determinista;

ALCS = All Longest Common Subsequence;

CLCS = Constrained Longest Common Subsequence;

D = Número de puntos dominantes;

E = distancia de edición (E = m + n - 2L);

ELAG = LCS Elastic Gap;

ELCS =Exemplar Longest Common Subsequence;


F = Filtramiento;

FIG = LCS Fixed Gap;

k = Número de errores;

l = Longitud del LCIS/LCWIS;

L = Longitud del longest common subsequence;

LCS = Longest Common Subsequence;

LCIS = Longest Common Increasing Subsequence;

LCWIS = Longest Common Weakly-Increasing (or non decreasing) Subsequences;

LLCS = Length Longest Common Subsequence;

m = L(S1) (m <= n); n = L(S2);

p = longitud del tercer string el cual aplica la restricción;

PB = Paralelismo de Bits;

PD = Programación Dinámica;

R = Numero de igualaciones;

RELAG = LCS Rigid Elastic Gap;

RIFIG = LCS Rigid Fixed Gap;

RLCS = LCS Rigid Gap;

SCS = Shorthest Common Supersequence;

Sort = Tiempo de orden de cada secuencia de entrada; t = min(m + 1, s);

w = longitud de palabra del computador en bits.

0 1 2 3 4 5 6

F I N I T O

Figura 6. Autómata finito no determinista que busca

exactamente “finito”

F I N I T O

F I N I T O

0 1 2 3 4 5 6

0 1 2 3 4 5 6

0 1 2 3 4 5 6

F I N I T O

ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ

ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ

ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ

ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ ΣΣΣΣ

εεεε εεεε εεεε εεεε εεεε εεεε

εεεε εεεε εεεε εεεε εεεε εεεε

Figura 7. Autómata no finito determinista que busca el

texto “finito” con 2 errores


En [36] se reseña un análisis del autor Melichar de 1995, que mejora la complejidad de espacio y tiempo de

preprocesamiento del autómata a la siguiente expresión:

O(min(3m, m(2mt)k, (k+2)m-k(k+1)!)) donde t = min(m+1,σ)

donde t es el empleo de tiempo en m número de estados.

Una de las extensiones del problema del longest common subsequence que usa esta técnica es la exemplar longest

common subsequence (ELCS)[10] y en [41] se usa un DAG (grafo acíclico directo) que es un autómata finito

determinista que da solución a la extensión all longest common subsequence (ALCS).

3. Filtramiento

Filtramiento o filtración, son algoritmos que filtran el texto, rápidamente descartando áreas de texto las cuales no

generan igualaciones, o mejor, buscan potenciales igualaciones y luego aplican un algoritmo secuencial para revisar

cada candidato. Estos algoritmos están enfocados al caso promedio, y son de mayor funcionalidad en los algoritmos

que no realizan toda la inspección de los caracteres del string, que es el concepto del approximate string matching.

Esta técnica envuelve dos etapas de proceso. La primera etapa preselecciona un conjunto de posiciones en el texto

que son potencialmente similares al patrón. La segunda etapa verifica cada posición potencial usando un método

exacto de rechazo potencial de igualaciones con k errores. La preselección utiliza usualmente O(n+p) tiempo, donde

n es el coeficiente mas pequeño de los algoritmos de preprocesamiento patrón - texto y p es el número potencial de

igualaciones buscadas en la primera etapa del algoritmo. Algunos de las derivaciones de este tipo técnica son la

filtración por tuplas (si un patrón aproximadamente iguala un substring del texto, entonces ellos comparten al menos

una l-tupla para un l suficientemente grande) y filtración por composición (si un patrón aproximadamente iguala un

substring de un texto, entonces ellos tienen composiciones de letras similares). Es de importancia que la complejidad

de los algoritmos desarrollados en este tipo de técnica dependan críticamente de la tasa de r/p, donde r es el número

real de igualaciones con k errores y p es el número potencial de igualaciones buscados en la primera etapa del

algoritmo. Entre mas grande la taza, mas pequeña es la ejecución de la segunda etapa de filtración del algoritmo. La

filtración es útil, para grandes niveles de error donde las áreas de texto a verificar cubren casi todo el texto. La

verificación puede ser hecha en una forma jerárquica [36], este concepto puede ser visto en la Figura 8, en la cual se

desea buscar el patrón “ACTGACAA” con cuatro errores en cualquier texto. Si se divide el patrón en cuatro

subpatrones con algún error, cualquiera de estos puede ser buscado en el texto. Puede verificarse la búsqueda del

patrón completo en un texto desde las hojas hasta la raíz (patrón).


A C T G A C A A

A C T G A C A A

A C T G A C A A

Figura 8. Verificación jerárquica

4. Paralelismo de bits

Son algoritmos basados en el trabajo de paralelismo del computador sobre los bits. Se usan sobre los autómatas

finitos no deterministas y la matriz de programación dinámica, que dan solución al problema del longest common

subsequence [36].

Este funciona específicamente con el número de bits de la palabra del computador. Las actuales arquitecturas

funcionan con palabras de 32 o 64 bits de procesamiento, lo que es muy importante en la práctica. Este valor es

comúnmente representado como ω. Por ello las operaciones usadas en este tipo de técnica están basadas en las

operaciones con los bits, que son: conjunción, disyunción inclusiva, disyunción exclusiva, negación y

desplazamiento o corrimiento .

Los algoritmos desarrollados en paralelismo de bits buscan un patrón en un texto simulando la operación de un

autómata no determinista y muchos de estos pueden verse como implementaciones de un autómata determinista,

pues el uso de esta técnica convierte los autómatas no deterministas a deterministas con la ventaja de ser mas simple,

mas rápido y fácil de extender para manipular patrones complejos, pero con la principal desventaja de la limitación

impuesta con el tamaño de palabra del computador.

Unos de los algoritmos desarrollados en es tipo de técnica son el BPD (Bit-Paralellism Diagonals) que es basado

sobre un autómata finito no determinista con el paralelismo de bits por las diagonales cuya complejidad es O( km /

ω n) y el BPR (Bit-Paralellism Rows) que esta basado también sobre un autómata finito no determinista pero con

paralelismo de bits por filas con una complejidad de O( m/ ω kn).

Uno de los mejoramientos en los algoritmos de paralelismo de bits [17] es O(mn log(γ) / ω) en el peor caso y O(n)

caso promedio.

IV. APLICACIONES PRÁCTICAS

Muchos de los estudios relacionados con la solución del problema del longest common subsequence han mostrado la

implementación y posterior experimentación del algoritmo propuesto como en [11], desde las primeras

investigaciones como [23], hasta modificaciones en el uso de un sistema para permitir patrones de subsecuencias

además como patrones de substrings en nodos y acelerar el tiempo de computación [3], pero su verdadero uso en


aplicaciones prácticas es diverso, entre las más importantes a mencionar son: la búsqueda de patrones en secuencias

biológicas, búsqueda y recuperación de texto, comparación de archivos y detección de virus e intrusos.

Análisis de secuencias biológicas : El análisis de secuencias biológicas es de suma importancia pues se puede

determinar la evolución de las especies, la cual es dada por la variación genética de los organismos, es decir de sus

genes, y por consiguiente las proteínas que los forman. Esas evoluciones de las proteínas están clasificadas en tres

formas que son la mutación, duplicación y barajado de dominios. Entonces, la comparación de secuencias

(nucleótidos y/o aminoácidos) es una forma de descubrir que partes de las secuencias son más importantes (están

más conservadas), predecir la estructura de las proteínas o la función de las proteínas. Algunos de los trabajos

relacionados se encuentran en [37] y [45].

Búsqueda y recuperación de texto : La necesidad de descubrir y reconocer variantes formas de strings como por

ejemplo variantes de la ortografía, errores ortográficos y diferentes transliteraciones incrementan la dificultan en

recuperación de información y la búsqueda aproximada de texto en la que se encuentra el longest common

subsequence ayudan a solucionar este problema. La recuperación de texto consiste en buscar la información de

mayor importancia en una recopilación de texto, teniendo en cuenta que la tarea básica es la igualdad de strings, y la

búsqueda de patrones de texto permite acceder a zonas de interés donde se encuentra la mayor cantidad de

información. Un ejemplo importante en este tipo de aplicación, son los buscadores WEB.

Uno de los estudios interesantes en este tipo de aplicación esta en [7], donde se analiza la búsqueda sobre texto

comprimido. Otro estudio importante en el área esta en [5], que consiste en la compresión de texto usando strings

comunes largos en un archivo de texto, implementado el algoritmo de string matching de Karp y Rabin(1987).

Comparación de archivos : Poder determinar las diferencias entre dos archivos de texto y determinar las

modificaciones realizadas. El resultado de estas comparaciones son típicamente mostradas al usuario, pero también

pueden ser usadas para lograr tareas en redes, sistemas de archivos y control de revisión. El programa diff2 tiene un

algoritmo capaz de solucionar el problema del longest common subsequence, el

cual busca las líneas que no cambian entre los archivos. La eficiencia práctica del algoritmo es porque este se fija en

las igualaciones esenciales de los archivos, lo que hace que se reduzca a la subsecuencia común mas larga para

algún par de

segmentos iniciales de los dos archivos [28].

Detección de intrusos y virus : La aplicación del longest common subsequence en la detección de intrusos forma

parte de la categoría de detección de intrusos llamado de uso impropio usando pattern matching. Este tipo de

categoría refiere a intrusiones que siguen un patrón bien definido de ataques que explotan la debilidad en un sistema

2 desarrollado en 1970 sobre el sistema operativo Unix en los laboratorios AT&T Bell. El primer prototipo apareció en 1976 por James Hunt


y software de aplicación. Esta técnica representa el conocimiento acerca del comportamiento malo o inaceptable y

busca detectarlos directamente, en contraste a la categoría de detección de intrusos de anomalía. En la categoría de

detección de intrusos de uso impropio las firmas de intrusión son usualmente especificadas como una secuencia de

eventos y condiciones que conducen a forzar una entrada. Algunos patrones en escenarios de ataques tienden a

extraer virus de archivos infectados. Se considera de entrada un flujo de eventos para ser igualado contra el patrón

(firma de intrusión). Una de las desventajas de este acercamiento es que este mira únicamente las vulnerabilidades

conocidas y por consiguiente no funciona en posteriores intrusiones desconocidas. El marco completo de la

aplicación del longest common subsequence en la detección de intrusos y virus se puede observar en [33].

V. TRABAJOS A FUTURO

Actualmente los estudios relacionados con el LCS se dirigen a reducir la complejidad de tiempo de ejecución y de

espacio por medio de algoritmos y diversas técnicas con el fin de llegar a resultados más eficientes y mejores, donde

el problema tiene aplicaciones prácticas.

Además el empleo de otras técnicas para solucionar el problema del longest common subsequence como algoritmos

de aprendizaje [13] y otras donde se basan en solución de extensiones del problema, como en [16] basado en una

técnica de solución del shortest common supersequence, son investigaciones que están abiertas. Otros de los trabajos

a futuro para el desarrollo de soluciones del problema, comprenden, el análisis sobre el poder de algoritmos no

basados en la comparación, como los algoritmos basados en bits. Reducción de trabajo para búsqueda de texto como

por ejemplo búsqueda múltiple de strings con más comprobaciones

y algoritmos óptimos no dependientes del texto de entrada.

En general la dirección de las investigaciones a futuro están en la combinación de una heurística y un algoritmo

longest common subsequence exacto.

Lo que se busca es que las dos fases podrían ser ortogonales en el sentido que el trabajo hecho durante el

preprocesamiento pueda ser completamente utilizado en el algoritmo exacto.

VI. CONCLUSIONES

Según la tabla presentada en este estado del arte y que resume la agrupación de algunos de los algoritmos que dan

solución al problema del longest common subsequence y sus extensiones, se puede concluir que hay varias

investigaciones por realizar en el área, como por ejemplo utilizar técnicas para desarrollar algoritmos en las que

posiblemente no se han estudiado.

La intención no era reproducir textualmente los análisis de la solución y los algoritmos, la idea era agrupar la

mayoría de estos y principalmente lograr una clasificación según las técnicas comunes con algunas de las


extensiones encontradas. Así la finalidad era mostrar una visión general del problema y profundizar en el

entendimiento del mismo. Pero determinar cual es el mejor de los algoritmos que dan solución al problema del

longest common subsequence no es correcto, pues las mismas investigaciones crean ambientes de experimentación

propios, lo que lleva a la conclusión que dependiendo de la aplicación práctica se debe recurrir a la solución más

apropiada.

REFERENCIAS

[1] Alves C. E. R.; Caceres E. N.;Song S. W. (2003),A BSP/CGM algorithm for the all-substrings longest common

subsequence problem, in Parallel & 2003. Proceedings. International Distributed Processing Symposium, ed.,'IPDPS

'03: Proceedings of the 17th International Symposium on Parallel and Distributed Processing', IEEE Computer

Society, Washington, DC, USA, pp. 57-64.

[2] Apostolico Alberto (1997),String editing and longest common subsequences, in 'Handbook of formal languages,

linear modeling: background and application', Springer-Verlag New York, Inc., New York, NY, USA, pp. 361--398.

[3] Arikawa Setsuo; Hirao Masahiro; Hoshino Hiromasa; Shinohara Ayumi; Takeda Masayuki (2003), 'A práctical

algorithm to find the best subsequences patterns', Theoretical Computer Science 292(2), 465-479.

[4] Arslan Abdullah N.; Egecioglu Omer (2005), 'Algorithms for the Constrained Longest Common Subsequence

Problems', International Journal of Foundations of Computer Science 16, 1099-1109.

[5] Avendaño Perez Carlos; Feregrino Uribe Claudia; Navarro Badino Gonzalo (2004),'Búsqueda Aproximada

Directamente En Texto Comprimido', Technical report, Instituto Nacional de Astrofísica, Óptica y Electrónica

(INAOE), México.

[6] Baker B. S.; Giancarlo R. (1998),Longest Common Subsequence from Fragments via Sparse Dynamic

Programming, in G. Bilardi; G. F. Italiano; A. Pietracaprina; G. Pucci, ed.,'Proceedings of the6th Annual European

Symposium on Algorithms', Springer-Verlag, Berlin, Venice, Italy, pp. 79--90.

[7] Bentley J. ; Mcilroy D. (1999),Data Compression using Long Common Strings, in 'Data Compression

Conference', pp. 287--295.

[8] Bergroth Lasse; Hakonen Harri; Raita Timo (2000),A Survey of Longest Common Subsequence Algorithms, in

'SPIRE 2000: Seventh International Symposium on String Processing Information Retrieval (SPIRE'00)', IEEE

Computer Society, Washington, DC, USA, pp. 39-48.

[9] Bergroth Lasse; Hakonen Harri; Raita Timo (1998),New Approximation Algorithms for Longest Common

Subsequences, in 'String Processing and Information Retrieval'.

[10] Bonizzoni Paola; Della Vedova Gianluca; Dondi Riccardo; Fertin Guillaume; Vialette Stephane

(2006),Exemplar Longest Common Subsequence, in 'Proc. of 2nd International Workshop on Bioinformatics

Research and Applications (IWBRA 2006)', pp. 791-798.

[11] Bonizzoni Paola; Della Vedova Gianluca; Mauri Giancarlo (2001), 'Experimenting an Approximation

Algorithm for the LCS', Discrete Mathemathics 110(1), 13-24.


[12] Booth Hilary S.; MacNamara Shevarl F.; Nielsen Ole M.; Wilson Susan R (2003), 'An Iterative Approach to the

Longest Common Subsequence', Methodology and Computing in Applied Probability 6(4), 401-421.

[13] Breimer E.; Goldberg M.; Lim D. (2000),A learning algorithm for the longest common subsequence problem, in

'2nd Algorithm Engineering and Experiments', pp. 147--156.

[14] Brodal Gerth Stølting; Kaligosi Kanela; Katriel Irit; Kutz Martin, Faster Algorithms for Computing Longest

Common Increasing Subsequences, in 'Proceedings Combinatorial Pattern Matching, 17th Annual Symposium',

CPM 2006, Springer-Verlag, Barcelona, España. pp. 330-341.

[15] Chao Kun-Mao; Huang Chien-Pin; Yang I-Hsuan, A fast algorithm for computing a longest common increasing

subsequence. Information Processing Letters 93. 2005. pp. 249-253.

[16] Charras C.; Lecroq T.; Pehoushek J.D. (1998),A Very Fast String Matching Algorithm For Small Alphabets

And Long Patterns, in M. Farach-Colton, ed.,'Proceedings of the 9th Annual Symposium on Combinatorial Pattern

Matching', Springer-Verlag, Berlin, Piscataway, NJ, pp. 55--64.

[17] Crochemore Maxime; Iliopoulos Costas S.; Navarro Gonzalo; Pinzon Yoan J.; Salinger Alejandro (2001), Bit-

parallel (δ, γ)-Matching and Suffix Automata, inProc. 10th Intl. Symp. On String Processing and Information

Retrieval (SPIRE’03), LNCS 2857, 2003.

[18] Crochemore Maxime; Thierry Lecroq (2003), The Computer Science and Engineering Handbook, CRC Press,

Inc., Boca Raton, FL, USA, chapter 8 Pattern Matching and Text Compression Algorithms, pp. 1-49.

[19] Dancik Vladimir (1995),Common Subsequences and Supersequences and Their expected Length, in

'Combinatorial Pattern Matching', pp. 55-63.

[20] Dancik Vladimir (1994),'Expected Length of Longest Common Subsequences', PhD thesis, University of

Warwick, UK.

[21] Dancik Vladimir; Paterson Michael S. (1994),Longest Common Subsequences, in 'Proceedings of the 19th

International Symposium on Mathematical Foundations of Computer Science', Springer-Verlag Berlin, London, UK,

pp. 127-142.

[22] Deorowicz Sebastian (2005),'Fast algorithm for constrained longest common subsequence problem', Technical

report, Silesian University of Technology, Poland.

[23] Dowling Geoff,; May Patrick (1980).’Approximate String Matching’,Communications of the ACM vol 12 n. 4.

381-402.

[24] Francois Nicolas (2005),'Alignement, sequence consensus, recherche de similarites : complexite et

approximabilite', PhD thesis, Universite Montpellier II, France.

[25] Greenberg Ronald I. (2003), 'Bounds on the Number of Longest Common Subsequences', The Computing

Research Repository cs.DM/0301030, 1-13.

[26] Greenberg Ronald I. (2003), 'Computing the Number of Longest Common Subsequences', The Computing

Research Repository cs.DS/0301034, 1-3.


[27] Greenberg Ronald I. (2002),'Fast and Simple Computation of All Longest Common Subsequences', Technical

report, Loyola University, USA.

[28] Heckel P. (1978), 'A technique for isolating differences between files'. Communications of the ACM 21(4), 264-

268.

[29] Hirschberg D. S. (1975), 'A Linear Space Algorithm for Computing Maximal Common Subsequences',

Communications of the ACM 18, 341-343.

[30] Iliopoulos Costas S.; Rahman M. Sohel (2006), New efficient algorithms for LCS and constrained LCS

problem, In Proceedings of the 3rd Workshop on Algorithms and Complexity in Durham (ACiD), Durham, UK,

September 2007.

[31] Iliopoulos Costas S.; Rahman M. Sohel (2006),Algorithms for Computing Variants of the Longest Common

Subsequence Problem (Extended Abstract), in 'International Symposium on Algorithms and Computation ISAAC',

pp. 399-408.

[32] Kunkle Daniel (2002),'Empirical Complexities of Longest Common Subsequence Algorithms', Technical report,

Rochester Institute of Technology, NY, USA.

[33] Kumar S.; Spafford E. (1994), 'A pattern-matching model for intrusion detection. In Proc. National Computer

Security Conference, pp. 11-21.

[34] Lin Hua ; Lu Mi (1991),An Optimal Algorithm for the Longest Common Subsequence Problem, in 'Proceedings

of the Third IEEE Symposium on Parallel and Distributed Processing', pp. 630-639.

[35] Lu Mi; Rahman C.S. (1993),A Partition Approach to Find the Length of the Longest Common Subsequence, in

'6th International Conference on VLSI Design', IEEE, , pp. 31 - 36.

[36] Navarro Gonzalo (2001), 'A Guided Tour To Approximate String Matching', ACM Computing Surveys 33(1),

31--88.

[37] Ning Kang; Ng Hoong Kee; Wai Leong Hon (2006),Finding Patterns in Biological Sequences by Longest

Common Subsequences and Shortest Common Subsequences, in 'Sixth IEEE Symposium on BioInformatics and

BioEngineering (BIBE)'.

[38] Rick Claus (1994),'New Algorithms for the Longest Common Subsequence Problem'(85123-CS), Technical

report, University of Bonn, Germany.

[39] Sankoff David (1972), 'Matching Sequences under Deletion/Insertion Constraints', National Academy of

Sciences of the USA 69, 4-6.

[40] Singh Virdi Sabegh; Wang Hong; Walker Robert A. (2006),Solving The Longest Common Subsequence (LCS)

Problem Using The Associative Asc Processor With Reconfigurable 2d Mesh, in 'International Conference on

Parallel and Distributed Computing and Systems (PDCS 2006)'.

[41] Steele J. M. (1982), 'Long common subsequences and the proximity of two random strings', SIAM Journal on

Applied Mathematics 14(4), 731--737.


[42] Tiskin Alexander (2006),All semi-local longest common subsequences in subquadratic time, in 'Computer

Science Symposium in Russia'.

[43] Tronicek Zdenek (2001),'Searching subsequences', PhD thesis, Czech Technical University, Prague, Czech

Republic.

[44] Tronicek Zdenek (1999),Problems Related to Subsequences and Supersequences, in 'String Processing and

Information Retrieval Symposium SPIRE / International Workshop on Groupware CRIWG', pp. 199-205.

[45] Wei Liu; Ling Chen (2006),A Parallel Algorithm for Solving LCS of Multiple Biosequences, in 'Fifth

International Conference on Machine Learning and Cybernetics', 2006.


ESTADO DEL ARTE DE LAS

REDES DE SENSORES

INALAMBRICOS

EDISON JOSUE DIAZ CASADIEGO JESÚS GUALDRON FLOREZ1

1Los autores son estudiantes de la especialización en Seguridad Informática, Facultad de Ingeniería Informática de la Universidad Pontificia Bolivariana Seccional Bucaramanga.

E. Díaz, Ing. de Sistemas, e-mail: [email protected] J. Gualdrón, Ing. Electrónico, e-mail: [email protected]

Resumen: Este artículo presenta el estado del arte de las redes de sensores inalámbricos, una nueva tecnología desarrollada a partir de sensores capaces de detectar y transformar fenómenos físicos como temperatura y movimiento en datos funcionales. Estos sensores se enlazan entre sí de forma inalámbrica, formando redes inteligentes con utilidades que van desde la investigación científica hasta el uso militar. Se presentan en este documento los antecedentes, una descripción del funcionamiento, arquitectura, métodos de comunicación y protocolos usados; se listan algunas aplicaciones prácticas, ideales y actualmente comerciales de las mismas y se muestra un ejemplo de estas redes. Palabras Claves: Redes, Sensores, Inalámbricos, MOTEs Abstract: The current article describes the state of the art of Wireless Sensors Networks, which is a new technology developed out of sensors capable of detecting and transforming physical phenomena such as temperature and movement, into functional data. These sensors are linked together via wireless, creating as a result smart networks that have features ranging from scientific research to military usage. This document shows the antecedents, a description of its functioning, architecture, communication methods and protocols in use. Additionally, some practical, idealistic and current commercial applications are listed, along with an example of these networks. Key Words: Network, Sensors, Wireless, MOTEs.

1. INTRODUCCIÓN

El crecimiento abrumador de las nuevas tecnologías, especialmente aquellas relacionadas con el mercado de las

comunicaciones personales, han obligado una rápida caída de los precios de dispositivos inalámbricos y mejoras

sustanciales en la calidad de los mismos. Al mismo tiempo, los costos vinculados a la instalación, mantenimiento,

adecuaciones y actualización de cableados han aumentado, generando un ambiente propicio para el surgimiento de

desarrollos de vanguardia como las redes de sensores inalámbricos (o Wireless Sensor Networks).

Una red de sensores inalámbricos (o WSN) consiste en una serie de nodos encargados de realizar labores de

detección, computación y comunicación. Dichos elementos conectados entre sí de forma inalámbrica, han venido


siendo desarrollados para campos específicos como la vigilancia de espacios abiertos y cerrados, monitoreo de

museos, seguridad perimetral, seguimiento de objetos y detección de intrusos, entre otros.

Durante los últimos 50 años se han venido diseñando nuevas aplicaciones e innovaciones en el uso de la telemetría a

través de señales de radio; de esta forma fueron creados sistemas inalámbricos punto a punto como algunos “modems

capaces de transmitir paquetes de datos a través de una habitación usando interfaces RS-232 en ambos lados” [1].

El desarrollo de los sistemas microelectromecánicos (MEMS) permitió el nacimiento de nuevos sensores que

proveían soluciones para aplicaciones específicas [2], tal como el diseño de air bag para autos gracias a

acelerómetros fabricados a partir de MEMS, o nuevas impresoras de chorro de tinta que usan cabezotes de impresión

fabricados con técnicas MEMS. Otras aplicaciones iniciales iban desde sensores basados en MEMS que teóricamente

podían detectar 400 especies de gases y enviar inalambricamente su concentración en partes por millón (ppb), hasta

la transmisión de temperatura superficial de las cubiertas de barcos militares.

El primer sensor inalámbrico totalmente integrado y disponible comercialmente, fue anunciado por la empresa

Computational Systems Inc99 (http://www.compsys.com), a finales de 1998. CSI desarrolla sensores para controlar

el estado de maquinaria usada para labores críticas, que deben estar bajo el constante monitoreo de parámetros como

temperatura y vibración.

Gracias al hecho de ser sensores remotos, estos dispositivos son llamados MOTES y pueden eventualmente tener el

tamaño de un grano de arena y contener increíblemente sensores, circuitos computacionales, tecnología de

comunicaciones inalámbricas bidireccionales y suministro de energía; todo gracias al adelanto en el uso del silicio y

en las técnicas de fabricación de microcomponentes. [4]

Elementos como la cantidad de nodos y la actividad de los sensores, afectan directamente la calidad y cubrimiento

que se puede esperar de las WSN, influyendo así en el mejor desempeño y funcionalidad de los mismos. Existen

además otras variables que condicionan el rendimiento de los sensores como el tamaño, el diseño y el gasto de

energía. Específicamente este último ítem congrega gran cantidad de investigaciones en redes de sensores, las cuales

tienen como fin el balancear la calidad de la protección y el consumo de energía, de dichos dispositivos uni-

funcionales.

2. CARACTERÍSTICAS ESPECÍFICAS DE LAS WSN

Aunque las redes de sensores comparten muchas características de los conceptos de redes Ad hoc, hay múltiples

diferencias y retos especiales que las distinguen entre ellas, entre esas:


Aplicación específica: Gracias a la gran cantidad de tecnologías de detección, computación y comunicación que

pueden ser combinadas para desarrollar aplicaciones, existe una gran gama de posibilidades para el uso de WSN.

Esto hace que sea improbable que exista una solución única para todos los problemas, lo cual genera así redes para

aplicaciones determinadas.

Interacción con el ambiente: Las características mismas de los sensores obligan que las redes interactúen con su

ambiente, lo que hace que su tráfico típico sea muy diferente a otras formas de redes manejadas por humanos. El

ejemplo habitual de esta cualidad se visualiza al revisar las tasas de transferencia de datos, a través de largos periodos

de tiempo en el que se mantienen ratas muy bajas permanentemente, pero que se disparan cuando algo pasa en el

ambiente (eventos como cambios climáticos drásticos ilustran esto).

Escala: Potencialmente, las WSN contendrán una mayor cantidad de nodos (miles) que las redes ad hoc actuales, esto

implica soluciones diferentes que tengan la posibilidad de ser escalables.

Energía: Comparada con muchas formas de redes ad hoc, la alimentación de energía debe ser baja y por lo tanto su

consumo es un elemento determinante. La mayoría de los sensores contienen fuentes de energía no recargables y la

necesidad de prolongar su tiempo de vida tiene un impacto profundo en la arquitectura de red y del sistema en sí.

Calidad de Servicio: Las WSN tendrán diferentes conceptos de Calidad de Servicio, por lo tanto no está claramente

definido el servicio de una red. En algunos casos el envío ocasional de algún paquete será un servicio más que

eficiente, en otros, existirán requisitos mucho más altos de confiabilidad. Teniendo en cuenta que no es una métrica

suficiente la tasa de entrega, sino la cantidad y calidad de información que puede ser extraída de los objetos

observados, indicadores como la cantidad de energía necesaria para obtener la información en cuestión aparecen

como elementos importantes en la definición del QoS.

Centralización de datos: La importancia de un nodo en particular de una red es reducida frente a las redes

tradicionales (arquitectura cliente-servidor), lo que hace que el centro de la red no sea un nodo en sí, sino la

información que pueda(n) tomar algún(os) nodo(s) en particular. El paradigma entonces cambia, de una arquitectura

centralizada en un nodo principal, hacia una arquitectura basada en datos centrales.

Simplicidad: Teniendo en cuenta que los nodos son pequeños y deben tener un consumo bajo de energía, el software

operativo y aplicativo de los sensores debe ser muy simple comparado frente a los computadores actuales. Esta

simplicidad requiere romper con las reglas convencionales de enlace entre software de redes.


3. NANOTECNOLOGÍA Y DISPOSITIVOS MEMS

El inicio de la nanotecnología se dio hace mas de 40 años cuando fueron realizados los primeros estudios por Von

Neuman, pero solo hasta el año 1959 cuando el premio nobel de física Richard Feynman en su discurso titulado “Al

fondo hay espacio de sobra”, se hizo referencia a las grandes oportunidades que aportaban el estudio de la

nanociencia y la nanotecnologia.

El concepto de nanociencia se asocia al estudio de las propiedades de los objetos y fenómenos a escala nanométrica

permitiendo la manipulación de las estructuras moleculares y de sus átomos. La nanotecnología se ocupa de la

manipulación “controlada” y producción de objetos, materiales, instrumentos, estructuras y sistemas a dicha escala, a

partir del reordenamiento de sus átomos y moléculas. [4]

La aplicación de la nanotecnología al desarrollo de nuevos dispositivos electrónicos, permitió desarrollar la

micromecanización, que esta definida por Francisco Ferrero como “la tecnología que permite integrar sobre un

mismo sustrato de silicio tanto la parte electrónica como los sensores, actuadores y también diversos elementos

mecánicos” [5]. Los sistemas integrados desarrollados con la anterior tecnología son denominados MEMS (Micro-

Electro-Mechanical Systems).

Las ventajas más representativas de los sistemas MEMS son: Sistemas electromecánicos en un solo chip, producción

en masa, múltiples campos de aplicación, tamaño reducido y bajos costos.

Algunos de los campos en los que son usados dispositivos MEMS son la biotecnología (biochips para la detección de

sustancias peligrosas, etc.), comunicaciones (RF-MEMS, etc.) y automotriz (airbag, sensor de lluvia, etc.), lo que

demuestra la importancia a futuro de estos mecanismos, mucho más teniendo en cuenta el bajo precio que pueden

llegar a tener gracias a la producción en masa.

4. ARQUITECTURA DE NODOS Y DE REDES INALÁMBRICAS

Arquitectura de nodos

Una red de sensores inalámbrica, esta compuesta de numerosos nodos independientes. Los nodos sensores son

unidades capaces de medir, procesar, controlar, almacenar en memoria y comunicarse de forma inalámbrica.

La arquitectura de un nodo es completamente dependiente del propósito de la aplicación. Pero se puede generalizar la

arquitectura como se muestra en la Figura 1. Cada nodo consta de un transductor, acondicionador de señal,


adquisición de datos, comunicación, memoria y batería. Estos nodos tienen restricciones principalmente de energía,

memoria y capacidad de cómputo.

Figura 1. Arquitectura de un Nodo

• Transductor: Según DLI Engineering Corporation, un transductor es un dispositivo que “convierte un tipo de

energía como vibración o sonido en un tipo diferente de energía generalmente una corriente eléctrica o un

voltaje“ [6], en caso que las señales de salida estén dadas en magnitudes eléctricas, estos elementos son

llamados sensores. En las redes inalámbricas encontramos diferentes tipos de sensores que son utilizados de

acuerdo a la necesidad de su aplicación y que se clasifican según el tipo de magnitud física a detectar.

• Acondicionador de Señal: Los circuitos de acondicionamiento de la señal de entrada se encargan de la

amplificación, filtrado, linealización, diferenciación, integración, comparación con límites de la señal y otras,

obteniendo a su salida una señal analógica lista para su posterior etapa (Digitalización).

• Adquisición de Datos: Etapa encargada de digitalizar la señal, y de gestionar la comunicación del elemento

sensor con el procesador de datos.

• Unidad de Procesamiento: Es el componente que interpreta y procesa los datos para transmitirlos a otra

estación, también gestiona el almacenamiento de datos en la memoria.

Arquitectura de una red inalámbrica de sensores (WSN)

Figura 2. Tomada de Wireless Sensor Network. M. Soledad Escolar Diaz [7]

Los elementos que componen una WSN son:


• Nodos Sensor: son procesadores de radio que toman los datos del sensor a través de sus puertas de datos y

envían la información a la estación base.

• Puerto de Enlace: Son los puntos de interconexión entre la red de sensores y una red TCP/IP a la cual surtirá

de información.

• Estación Base: Es un repositorio de datos, el cual puede ser un computador o un sistema completo.

• Red Inalámbrica: Como tal, usualmente se basa en el estándar 802.15.4 (ZigBee).

Dos tipos de arquitectura son utilizadas en las WSN: la arquitectura centralizada y la distribuida.

Arquitectura centralizada:

Figura 3. Topología de Arquitectura Centralizada

En la figura 3 se muestra la topología de una arquitectura centralizada, en donde todos los nodos transmiten al puerto

de enlace y pueden presentar un problema fundamental; el cuello de botella, además si todas las unidades transmiten

al tiempo hay una alta probabilidad de fallo haciendo la red ineficiente, desperdiciando energía (un recurso que es

limitado en este tipo de redes) y haciendo disminuir el tiempo de vida útil de la red.

Arquitectura Distribuida:

Esta arquitectura (de tipo intrínseca) tiende a una computación distribuida, que es aquella en la que los nodos

sensores se comunican sólo con otros sensores dentro de un vecindario; además en el cluster, los nodos cooperan y

ejecutan algoritmos distribuidos para obtener una única respuesta global que el cluster principal se encargará de

comunicar a la estación base.

Figura 4. Topología de Arquitectura Distribuida


5. PROTOCOLOS DE COMUNICACIONES EN LAS WSN

Muchos de los aspectos presentes en las pilas de protocolos de las redes de computadores más usadas (como el

TCP/IP) se presentan con cambios mínimos o cambios sustanciales en las capas de comunicaciones de las WSN.

Algunos de los aspectos más sobresalientes y los trabajos desarrollados sobre las mismas son:

Capa Física: El principal dilema de la capa física frente a las trasmisiones típicas de radio, es como transmitir con la

mayor eficiencia de energía posible. Alrededor de este tema se ha trabajado relativamente poco en el desarrollo de

protocolos ajustados a las necesidades de las WSN. Algunos investigadores como Wang, Cho, Sodini y

Chandrakasan [8] han realizado trabajos sobre manejo eficiente de energía, otros como Gao y Hunerberg [9] han

profundizado en consideración de aspectos de hardware para CDMA en nodos sensores, entre otros.

MAC: La capa de Acceso al Medio es y ha sido una las áreas de mayor investigación para WNS, la principal

preocupación en su mayoría ha sido como lograr que los sensores puedan permanecer inactivos el mayor tiempo

posible, sin poder comunicarse, pero alargando el tiempo de vida de sus baterías, lo que ha llevado a que se trate con

mucha frecuencia algunos aspectos de TDMA. En esta aspecto se han elaborado artículos con investigaciones como

PicoRadio MAC [10], S-MAC [11], SMACS [12] y STEM [13].

Link Layer: El trabajo sobre la capa de Enlace ha sido mucho menor que el de la MAC, y es de resaltar el trabajo de

Yogesh Sankarasubramaniam y otros investigadores del Georgia Institute of Technology sobre eficiencia en el gasto

de energía, basada en la optimización del tamaño de paquetes en WSN [14], adicionalmente sobresale el trabajo

sobre FEC y la variación de nivel de transmisión en la energía gastada por bit, desarrollado por investigadores de

MIT como Eugene Shih [15].

Conceptos de Direccionamiento: Se han propuesto métodos diferentes a los conocidos en redes normales para el

direccionamiento de WSN, entre algunos de ellos encontramos el uso de direcciones MAC codificadas asignadas de

forma distribuidas en redes de sensores [16], el uso de direccionamiento basado en la posición geográfica del sensor

o direccionamiento basado en el tipo de información a procesar y comunicar.

Sincronización de tiempos: Este tema es muy importante en redes distribuidas como las WSN, ya que se requiere que

todos los miembros estén sincronizados para asegurar la correcta observación y monitoreo de eventos, muy a la

filosofía del protocolo NTP. Trabajos como “sincronización ligera de tiempo para redes de sensores” [17]

profundizan sobre el tema.

Localización: la ubicación de nodos sensores por la misma red, como los sistemas coordinados de redes de sensores,

es una de las áreas más populares en investigación. Algunos mecanismos van desde el control de indicadores de


fuerza de la señal, tiempo de llegada, diferencias en los mismos hasta el ángulo de llegada. Se destacan trabajos como

los del uso de métodos probabilísticos para la localización en WSN [18] y consideraciones de energía para

localización [19].

Capa de Red: Además de MAC y control de topología, esta capa es seguramente la que ha tenido mayor interés en

investigaciones, algunas de las cuales se enfocan principalmente en la búsqueda de soluciones de escalabilidad,

eficiencia en el gasto de energía y centralización de datos.

Capa de Transporte: La definición de servicios adecuados para las WSN, niveles de dependencia y QoS han obtenido

poca consideración hasta el momento. Sobresalen los trabajos de Stann y Heideman sobre RMST [20].

6. IEEE 1451 Y SENSORES SMART

En 1993 la IEEE y el Instituto Nacional de Estandares y Tecnología NIST, comenzaron a trabajar en la creación de

un estandar para Redes de Sensores SMART, con el objetivo de facilitar a los diferentes fabricantes, la producción de

este tipo de dispositivos y la forma como se conectaban estos a las redes. Según la definición de Randy Frank [21] un

sensor SMART es “un sensor que provee funciones extras más allá de aquellas necesarias para generar una correcta

representación de la cantidad detectada”. El estándar IEEE 1451 fue presentado en la Sensors Expo en Philadelphia,

en Octubre de 2001, y definió que las funciones deseable para los sensores incluyen: “fácil instalación, auto

identificación, auto diagnostico, establecimiento de tiempos de alerta para la comunicación con otros nodos, algunas

funciones de software y DSP (Digital Signal Processing), y protocolos de control estándar e interfaces” [22].

Las redes de sensores inalámbricos cumplen con todos los requerimientos anteriores, por lo que son también

consideradas como redes de sensores SMART, y se rigen –en parte- por el estándar IEEE 1451.

7. SISTEMAS OPERATIVOS

Adicional a los problemas generados en cuanto a la estandarización de protocolos de comunicación para WSN, el

desarrollo de un sistema operativo que permita el fácil establecimiento de canales de comunicación entre nodos, se

presenta como otro factor de complejidad en estas nuevas infraestructuras. Actualmente plataformas como TinyOS,

MANTIS, SOS y Contiki, han liderado este aparte, siendo el primero, Tiny MicroThreading Operating System,

(desarrollado por la universidad de Berkeley), el más eficiente hasta el momento.


8. PROBLEMAS Y DESVENTAJAS

A partir del estado del arte encontrado, se pueden dislumbrar problemas y desventajas de las Redes de Sensores

Inalámbricos.

Con relación a las redes cableadas, las redes móviles Ad hoc presentan cambios de topología frecuentes e

impredecibles debido a la movilidad de sus estaciones. Estas características generan problemas tales como topología

dinámica, necesidad de recursos de ancho de banda, cobertura de red limitada, batería limitada, recursos

computacionales limitados y seguridad reducida.

Al tratarse de información transmitida con un enlace radio, su accesibilidad hace necesaria la implementación de un

mecanismo de seguridad que proteja al sistema de posibles ataques. Para conseguir este objetivo, se han desarrollado

diferentes estándares, generalmente para ser implementados en sistemas de relativamente alta complejidad, como los

protocolos IEEE 802.11 y Bluetooth. Aunque haciendo uso de estos estándares se pueden diseñar redes de sensores

relativamente seguras, hay aplicaciones cuya simplicidad y bajo costo no permiten la implementación de estos

estándares.

Los algoritmos criptográficos y los protocolos de seguridad más conocidos no son fáciles de implementar en sistemas

cuya potencia computacional es muy limitada, por otro lado con el objetivo de mantener costos no altos, se utilizan

módulos de radiofrecuencia de bajo precio y además unidireccionales.

En WSN el procesamiento en la red dificulta el despliegue de los mecanismos de seguridad punto a punto, debido a

que los nodos intermedios necesitan acceso directo al contenido del mensaje.

9. APLICACIONES Y SISTEMAS COMERCIALES DISPONIBLES

Las redes de sensores tienen una amplia variedad de aplicaciones: monitorización de un hábitat (determinar la

población y comportamiento de animales y plantas), monitorización del medio ambiente, observación del suelo o

agua, el mantenimiento de ciertas condiciones físicas (temperatura, luz), control de parámetros en la agricultura,

detección de incendios, terremotos o inundaciones, sensorización de edificios “inteligentes”, control de tráfico,

asistencia militar o civil, control de inventario, control médico, detección acústica, cadenas de montaje, etc.

Según Soledad Escolar, existen aplicaciones completas y complejas que usan WSN y que son usadas comercialmente

como los Crossbow Berkey Motes y los Microstrain’s X-Link Measurement System. [7]


La primera es uno de los dispositivos de redes de sensores inalámbricos más versátiles en el mercado para propósitos

de prototipado. Las tres familias de MOTEs –llamadas MICA, MICA2 y MICA2-DOT- desarrollaron nodos con 5

sensores instalados, los cuales miden temperatura, luz, acústica, aceleración-sísmica y magnetismo, y fueron

diseñados para redes de vigilancia para personal y vehículos. Tienen como características físicas bajo consumo de

energía y pequeño tamaño, lo que permite que sean colocados prácticamente en cualquier lugar, además cada nodo

sensor en la red puede funcionar como una estación base lo que permite que la red se pueda autoconfigurar y posea

capacidades de enrutamiento multi-hop. Opera en una frecuencia en banda ISM (Industrial, Scientific, and Medical

Band) de 916 o 433 Mhz, con velocidades de transmisión de 40 Kbps y alcance de 30 a 100 pies. Cada nodo tiene un

procesador microcontrolador de bajo poder con velocidad de 4 Mhz, memoria flash de 128 Kb, SRAM y EEPROM

de 4 Kb y Sistema Operativo Tiny-OS (Sistema Operativo Distribuido desarrollado por UC Berkeley en NES-C).

Otras empresas que se dedican a brindar soluciones para la industria son:

• XSILOGY Solutions, compañía que provee WSN para aplicaciones comerciales: organización de inventario de

tanques, sistemas de distribución de flujos, edificios comerciales, monitorización medioambiental, defensa del

hogar, etc. (http://www.xsilogy.com/home/main/index.html )

• ENSCO investiga con WSN para aplicaciones meteorológicas (http://www.in-q-tel.com/tech/dd.html)

• EMBER provee soluciones con WSN para automatización industrial, edificios inteligentes.

(http://www.ember.com)

• SOFTLINX desarrolla productos de seguridad perimetral basada en sensores. (http://www.soflinx.com)

• XYZ integra redes de sensores inalámbricas pare el control de entornos en el interior de edificios

(http://www.cbe.berkeley.edu/research/briefs-wirelessxyz.htm)

10. CONCLUSIONES

Las redes de sensores inalámbricos tienen una importancia relevante entre las redes en general. La necesidad de

minimizar tanto el tamaño como el gasto de energía de sus nodos las hacen muy diferentes de las redes ad hoc

normales, más aún las aplicaciones específicas para las que deben ser diseñadas ponen en tela de juicio los

paradigmas, métodos, protocolos y esquemas sobre los que nuestras redes han sido concebidas.

Como todo tema de investigación moderno, quedan sobre la mesa muchas preocupaciones que deberán ser resueltas

para llevar a buena marcha el uso masivo de una tecnología tan potente y con tanta proyección como las WSN.

Aspectos como la seguridad de la información transmitida entre redes inalámbricas como estas, el cifrado de los

datos, la revisión de vulnerabilidades, el monitoreo de las mismas por personas no autorizadas y las formas como

deben protegerse saltan a la vista para aquellos preocupados por la seguridad informática, sin embargo todos estos


temas deben tener en cuenta como elemento central el gasto de energía, con el fin de tener no solo redes inteligentes

y seguras, sino además redes funcionales e independientes.

BIBLIOGRAFIA

[1] ALLGOOD, Glenn O., MANGES, Wayne W., SMITH, Stephen F. It's Time for Sensors to Go Wireless; Part 1:

Technological Underpinnings. [Online] Sensors Magazine. Abril 1, 1999. Disponible en www: <

http://www.sensorsmag.com/articles/0499/0499_10/main.shtml >

[2] PICRAUX, S.T. and MCWHORTER Peter. The Broad Sweep of Integrated Microsystems. In: IEEE Spectrum.

Vol. 24, Nro. 33 (Diciembre 1998).

[3] HOFFMAN, Thomas. Smart Dust. [Online] Computer World Magazine. Marzo 24, 2003. Disponible en www:

<http://www.computerworld.com/mobiletopics/mobile/story/0,10801,79572,00.html>

[4] BLANCO, Verónica y ARANDA, Eva. Estudio de las tendencias y estado del arte en el desarrollo de dispositivos

en miniatura y su aplicación en entornos inteligentes. Cataluña, 2006, 129 p. Trabajo de Grado (Ingeniera Técnica de

Telecomunicación). Universidad Politécnica de Cataluña. Escuela Técnica Superior de Castelldefels.

[5] FERRERO, Francisco. Curso de Instrumentación Electrónica - Lección 9. [Online] Universidad de Oviedo, 2006,

13 p. Escuela Politécnica Superior de Ingeniería de Gijón. Disponible en www: <

http://www2.ate.uniovi.es/13996/Lecciones/Leccion09.pdf>

[6] DLI Engineering Corporation. Introduction to Machine Vibration Online Text Book. [Online]. 2004. Disponible

en www: < http://www.dliengineering.com/vibman-spanish/transductor1.htm >

[7] ESCOLAR, Soledad. Wireless Sensor Networks. [Online] Universidad Carlos III de Madrid. 2006. Disponible

en www: < http://www.arcos.inf.uc3m.es/~sescolar/index_files/presentacion/wsn.pdf >

[8] WANG, Andrew, CHO, SeongHwan, SODINI, Charles y CHANDRAKASAN, Anantha. Energy Efficient

Modulation and MAC for Asymmetric RF Microsensor Systems. En: International Symposium on Low Power

Electronics and Design (ISLPED ’01), páginas 96-99. Agosto 2001.

[9] GAO, Reid y HUNERBERG, Peter. CDMA-based wireless data transmitter for embedded sensors. En: Proc. 18th

IEEE Instrumentation and Measurement Technology Conference. Budapest, Hungria, volumen 3, páginas 1778-

1783. 2001.


[10] ZHONG, Lizhi, SHAH, Rahul, GUO, Chunlong y RABAEY, Jan. An Ultra-Low Power and Distributed Access

Protocol for Broadband Wireless Sensor Networks. En: IEEE Broadband Wireless Summit, Las Vegas, NV, Mayo

2001.

[11] YE, Wei, HEIDEMANN, John y ESTRIN, Deborah. An energy-efficient MAC protocol for wireless sensor

networks. En: Proc. IEEE Infocom, 2002.

[12] SOHRABI, Katayoun, GAO, Jay, AILAWADHI, Vishal y POTTIE, Gregory. Protocols for self-organization of

a wireless sensor network. En: 37th Allerton Conference on Communication, Computing and Control, Allerton,

September 1999.

[13] SCHURGERS, Curt, TSIATSIS, Vlasios, GANERIWAL, Saurabh y SRIVASTAVA, Mani. Optimizing Sensor

Networks in the Energy-Latency-Density Design Space. En: IEEE Transactions on Mobile Computing, Vol. 1, No. 1,

Pág. 70-80. Enero 2002.

[14] SANKARASUBRAMANIAM, Yore, AKYILDIZ, Irw, y MCLAUGHLIN, Serg. Energy Efficiency Based

Packet Size Optimization in Wireless Sensor Networks. En: Proc. 1st IEEE Intl. Workshop on Sensor Network

Protocols and Applications (SNPA), Anchorage, AK, Mayo 2003.

[15] SHIH, Eugene, CALHOUN, Benton, CHO, SeongHwan y CHANDRAKASAN, Anantha. Energy-Efficient

Link Layer for Wireless Microsensor Networks. En: Proc. Workshop on VLSI 2001 (WVLSI ’01), Abril 2001.

[16] SCHURGERS, Curt, KULKARNI, Gautam y SRIVASTAVA, Mani. Distributed Assignment of Encoded MAC

Addresses in Sensor Networks. En: Proc. Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc’01),

Long Beach, CA, Octubre 2001.

[17] VAN GREUNEN, Jana y RABAEY, Jan. Lightweight Time Synchronization for Sensor Networks. En: Proc.

2nd ACM Intl. Workshop on Wireless Sensor Networks and Applications (WSNA), San Diego, CA, Septiembre

2003.

[18] RAMADURAI, Vaidyanathan y SICHITIU, Mihail. Localization in Wireless Sensor Networks: A Probabilistic

Approach. En: Proc. 2003 Intl. Conf. on Wireless Networks (ICWN), pág. 300–305, Las Vegas, NV, Junio 2003.


[19] ZOU, Yi y CHAKRABARTY, Krishnendu. Target Localization Based on Energy Considerations in Distributed

Sensor Networks. En: Proc. 1st IEEE Intl. Workshop on Sensor Network Protocols and Applications (SNPA),

Anchorage, AK, Mayo 2003.

[20] STANN, Fred y HEIDEMANN, John. RMST: Reliable Data Transport in Sensor Networks. En: Proc. 1st IEEE

Intl.Workshop on Sensor Network Protocols and Applications (SNPA), Anchorage, AK, Mayo 2003.

[21] FRANK, Randy. Understanding Smart Sensors. 2da Ed., Artech House, Norwood, MA, 2000. 389 pág. ISBN

978-0890063118.

[22] IEEE 1451, A Standard Smart Transducer Interface [online], Sensors Expo, Philadelphia, Oct. 2001. Disponible

en www: <http://ieee1451.nist.gov/Workshop_04Oct01/1451_overview.pdf>

informÁtico - upbbga.edu.co · informatica y computacion - siic 2007 en el mes de septiembre se...

Documents