[REDES DE TELECOMUNICACIONES] Lab 9: Ahorro de energía

PMAC: An adaptive energy-efficient MAC protocol for Wireless Sensor Networks

Tao Zheng, School of Computer Science, University of Oklahoma
Norman, Oklahoma 73019–6151
Email: tao@ou.edu

Sridhar Radhakrishnan †, School of Computer Science, University of Oklahoma
Norman, Oklahoma 73019–6151
Email: sridhar@ou.edu

Venkatesh Sarangan, Computer Science Department, Oklahoma State University
Stillwater, Oklahoma 74078
Email: saranga@cs.okstate.edu

Para esta entrada se realizará un resumen de un paper sobre ahorro de energía en redes.

1. Introducción

Las redes inalámbricas sensoriales son nuevos tipos de redes ad-hoc de propósito especial. Tienen numerosas aplicaciones en varios campos como el monitoreo de hábitats, seguimiento de objetivos, seguridad del hogar, etc. estas redes son desplegadas en forma ad-hoc, compartiendo el mismo medio de comunicación. Los nodos son operados con baterías y se dejan desatendidos. Por lo tanto, el ahorro de energía es un tema crítico en las redes de sensores inalámbricas. Muchos esfuerzos de investigación en los últimos años se han centrado en el desarrollo de planes de ahorro de energía para redes de sensores inalámbricas.

El protocolo MAC es requerido en redes sensoriales para coordinar el acceso a los medios compartidos. Diseñar protocolos MAC eficientes es una de las formas para prolongar la vida útil de la red.

SMAC es un protocolo MAC diseñado para redes sensoriales. Obliga a los nodos a funcionar a un ciclo de trabajo bajo al poner los nodos en sueño periódico en lugar de escucha inactiva. Aunque SMAC tiene mayor ahorro de energía que 802.11, no se adapta al tráfico de red, ya que usa un ciclo de trabajo fijo para todos los nodos.

El protocolo MAC de Tiempo límite (TMAC) mejora el SMAC con un ciclo de trabajo adaptativo. Si no hay actividad durante un tiempo TA en un nodo dado, este se duerme. Tal adaptación libera la aplicación de la carga de selección de un ciclo de trabajo apropiado. TMAC tiene el mismo rendimiento que SMAC bajo cargas de tráfico constante, pero ahorra más energía en un marco de trabajo variable.

El problema con esa política de conservación de energía agresiva es que si los nodos se van rápido a dormir, incrementa la latencia y disminuye el throughput.

En el paper se propone un protocolo MAC llamado Pattern-MAC (PMAC) para redes sensoriales que adaptativamente determina el tiempo de dormir/despertar para un nodo basado en su propio tráfico y el de sus vecinos.

2. Descripción de PMAC

PMAC es un protocolo de tiempo en lapsos como SMAC. En SMAC un nodo puede mantenerse despierto por un determinado tiempo dentro de un lapso de tiempo e irse a dormir despues de eso, mientras que en PMAC puede mantenerse dormido o despierto durante un lapso de tiempo.

A. Lógica tras PMAC

La escucha inactiva es una de las principales fuentes de pérdida de energía. Los protocolos MAC para ahorrar energía tratan de minimizar el tamaño de el periodo de escucha. En SMAC los nodos tienen que despertar aunque no exista tráfico, desperdiciando energía. EN TMAC, los nodos tienen que despertar al comienzo de cada de cada período de tiempo durante un tiempo TA, incluso cuando no hay tráfico en la red. En PMAC, un nodo obtiene informacion de su actividad basado en la actividad de sus vecinos a travez de patrones. A partir de esto, un nodo puede ponerse a dormir durante largos períodos de tiempo para varios marcos de tiempo cuando no hay tráfico. De esta manera se trata de lograr que PMAC intente ahorrar más energía que SMAC y TMAC sin comprometer el rendimiento.

B. Patrones vs Tiempos

Un patrón de dormir/despertar es una cadena de bits indicando el plan tentativo para dormir/despertar para un nodo sobre varios lapsos de tiempo. Un bit 1 indica que el nodo se mantendrá despierto durante un lapso de tiempo, mientras que un bit 0 indica que el nodo dormirá.

3. Detalles del protocolo

El patrón del nodo altera los tiempos de dormir y despertar. Para generar un buen throughput sin comprometer el ahorro de energía es importante que el patrón generado se adapte al tráfico de red.

A. Generación de patrones

Siendo Pj una cadena de bits representando el patrón de un nodo j. Este patrón es asociado al nodo j sobre N lapsos de tiempo. Llamaremos a esta secuencia como un período. Si Pj es menor a N, entonces el patrón se repite durante el tiempo restante. por ejemplo si Pj es = 1 y N = 5, entonces el plan tentativo para el nodo j sobre los siguientes 5 lapsos de tiempo será 01010.

B. Cambio de patrones

El patrón generado es solo un plan tentativo. En PMAC, el verdadero plan de dormir/despertar es derivado basado sobre el propio patrón del nodo y de los patrones de los vecinos.

Nuevos patrones son generados para los períodos subsecuentes, son transmitidos por los nodos al final del período actual.

Para acomodar este cambio de patrones, el tiempo es dividido en supero marcos de tiempo (STF). Cada STF consiste de dos sub-marcos.

El primero es llamado Marco de Tiempo de Patrón de Repetición (PRTF). El PRTF en turno es dividido en diferentes lapsos de tiempo de duración TR. PRTF es la secuencia de N lapsos mientras todos los sensores se mantienen despiertos. Este lapso especial es usado para aumentar la velocidad de comunicación.

El segundo sub-marco es llamado Marco de Tiempo de Cambio de Patrón (PETF) durante el cual, los nuevos patrones se intercambian entre vecinos, se divide entre varios lapsos de duración TE. El patrón es cíclicamente repetido durante el PRTF el cual cada lapso de tiempo tiene un bit asignado.

4. Discusión cualitativa

A. Adaptabilidad a condiciones de tráfico

El número de bits 0 en los nuevos patrones crece exponencialmente cuando la carga de tráfico es ligera. Esto significa que los nodos pueden caer en largo sueño rápidamente sobre cargas ligeras. De esta manera se logra un mayor ahorro de energía. Si cualquier información es detectada, se agregará un 1 a la cadena, lo que permite que el nodo despierte rápidamente cuando la carga de trafico llega.

B. Ahorro de energía mediante localización

Solo aquellos nodos involucrados en la comunicación despertarán rápidamente, el resto se mantendrán dormidos.

C. Ahorro de energia mediante escucha inactiva

Se ha descrito como PMAC ahorra energía permitiendo a los nodos quedarse dormidos si no hay comunicación entre ellos. Esto reduce la energía gastada debido a la escucha inactiva de los periodos de dormir/despertar de SMAC. PMAC también introduce una escucha inactiva adicional. Esto ocurre cuando en el patrón hay dos lapsos de tiempo consecutivos donde el nodo se despierta, pero en el segundo no hay comunicación.

D. Tiempo de sincronización

Puesto que el tiempo está en lapsos, algún nivel de sincronización entre nodos es necesario. Como sea, como solo grandes escalas están involucradas, no hay problemas de reloj. Los lapsos PETF envían un paquete SYNC para advertir a los nuevos nodos a ajustar sus relojes.

5. Conclusiones

En este trabajo se propone un nuevo protocolo MAC, llamado PMAC, donde se determinan de forma adaptativa los tiempos de sueño de activación de los nodos. Los tiempos se deciden con base al propio tráfico del nodo y la de sus vecinos. Los resultados experimentales muestran que en comparación con SMAC, PMAC logra un mayor ahorro de energía bajo cargas ligeras, y un mayor rendimiento bajo cargas de tráfico más pesados​​.

El rendimiento mejorado de PMAC sugiere que el 'intercambio de patrones' es un marco prometedor para la mejora de la eficiencia energética de los protocolos MAC utilizados en redes sensoriales. Actualmente se está llevando a cabo un análisis comparativo de la PMAC propuesta con otros protocolos adaptativos MAC como TMAC y DMAC para la transferencia de datos de velocidad binaria variable. También se tiene para llevar a cabo un análisis detallado de PMAC bajo diversos tipos de tráfico, tales como la radiodifusión, convergecast y punto a punto. Se cree que PMAC se puede mejorar con mecanismos de tiempo de espera a lo largo de las líneas de TMAC, y de ese modo lograr un rendimiento aún mejor.

Se está desarrollando un mejor patrón y planes de generación de horarios para mejorar la eficiencia energética y la latencia de transferencia de datos de PMAC.

Crítica:

Al parecer, es un protocolo que aunque está en desarrollo, tiene buenas oportunidades para sobresarlir entre los sugeridos (SMAC, TMAC, etc.). Los resultados muestran que realmente hay un consumo menor de energía y aumento de rendimiento bajo ciertas condiciones.

Para condiciones de poca carga se muestra que hay un ahorro de energía mayor. Para condiciones donde la carga de tráfico es mayor, hay un aumento de rendimiento con un consumo moderado.

El paper menciona varias veces que el protocolo se basa en patrones de vecinos generados, esto significa que los primeros nodos generan un patrón poco adaptado, que tal vez no signifique gran cosa, pero si a gran escala.

Referencia:
https://perso.ens-lyon.fr/eric.fleury/CPS/ART/Projet/pmac/01420161.pdf

[CÓMPUTO UBICUO] Lab 9: Recomendaciones en evaluación de usabilidad

Como se ha hecho antes, en esta entrada daré unas recomendaciones a los equipos en base a sus presentaciones de evaluación de usabilidad.

Alarma Inteligente:

A mi parecer usan diseños que van acorde a su proyecto, interfaces sencillas con pocos controles. En cuanto a lo del sistema de apagado, creo que una alarma inteligente debe estar 24/7 sin interrupción salvo cuando la llave correcta es introducida, entonces funcionaría de forma pasiva. Otra cosa es que el usuario debe de poder activar la alarma de forma remota para el rastreo GPS (recordemos los robos a mano armada). Para esto funciones de envió de datos deben activarse cada cierto tiempo definido por el usuario, o bien cuando suceda un evento sospechoso (forcejeo de cerraduras, vidrios rotos, etc).

Computadora inteligente:

La mayoría del software tiene un mini tutorial de uso que solo aparece al primer inicio, sería bueno agregar algo así, sería mejor si este mini tutorial funcionara de la forma en que ustedes lo plantean (reconocimiento facial, control por voz, etc) y que sea accesible por un comando de voz si el usuario necesita más de una vez para familiarizarse.

Oficina inteligente:

Su proyecto, en cuestión de usabilidad, es muy simple pero eficiente, los usuarios solo necesitan su tag para acceder a las funcionalidades de la oficina. Como se los decía uno de los usuarios, traten de poner el lector en una posición visible y llamativa. Podrían implementar un panel de configuración, donde los usuarios se identifican con su tag y les permite configurar las opciones que den.

Recordatorio inteligente:

Me parece que hacen muy buen uso de las interfaces propuestas. Como mencionan, es mejor usar un lenguaje mas familiar para los usuarios. También sería bueno hacer un pequeño recorrido sobre las funciones al inicio de la aplicación solo la primera vez que se accede.

Galería inteligente:

Deberían aprovechar aún más las posibilidades que plantean. Pueden hacer un sistema que reconoce un número de personas frente a la obra y automáticamente inicie la descripción o algo así, y que diferencie cuando hay una persona o varias. Para una persona el sistema podría activarse cuando alguien está a una distancia moderada, si la persona se acerca más entonces activar las narraciones de la obra o algo así. Dentro de lo que cabe, me parece un estupendo proyecto.

Despertador inteligente:

Pues su manejo de usabilidad es muy bueno, el usuario no necesita apagar la alarma, solo despertarse. ¿Han pensado si el usuario vuelve a acostarse después de la alarma? Creo que sería una buena idea poner una especie de rango de tiempo en que no hay nadie en la cama.

Casa inteligente:

Pues parece una interfaz móvil con buena usabilidad, pero al estar en un ambiente ubicuo, creo que se podrían usar otro tipo de llaves electrónicas como los RFID tags o algo así.

CarFxP:

Todo está muy bien, solo que hay que buscar una forma en que los usuarios se sientan seguros.

[TEORÍA DE LA INFORMACIÓN] Codificación Adaptativa

Para esta semana se encargó realizar un algoritmo de codificación adaptativa basado en la codificación Huffman.

Realicé unas modificaciones a la tarea anterior para hacerlo lo más adaptativo posible.

Anteriormente procesaba todo el texto en una sola iteración y generaba una tabla de frecuencias de caracteres. Después generaba una lista de nodos y al final generaba un árbol.

Ahora he cambiado ciertas cosas en el código, no proceso el texto de la misma manera, sino que ahora lo divido en palabras de N caracteres y cada una las proceso por separado, genero los nodos para esa palabra y por cada palabra modifico un árbol con los nuevos nodos.


Al correr el programa, se genera y se imprime la lista de palabras de N caracteres, despues se corren los algoritmos, finalmente se imprime el texto original junto con el texto decodificado. Tambien se imprimen los datos de la corrida del programa.

Pensé que generar varios arboles optimizaría un poco el tiempo puesto que se procesan más rápido y la codificación se genera con mayor velocidad, una vez generada el arbol se mantendrá constante, a diferencia de la versión anterior, que una vez procesado el texto generaba el arbol de forma recursiva y con tiempos ligeramente más elevados.

El código es el siguiente:
Realmente es algo demasiado sencillo pero cumple con las especificaciones:

• No hay un calculo de las frecuencias en un principio (solo se calcula frecuencias de caracteres por cada palabra generada).
• No hay conocimiento de la distribución de símbolos.

Algo que destaca es que dependiendo de el valor de N el algoritmo se comportará distinto, se puede observar que para pocas letras no hay eficiencia, llegando a compresiones que generan archivos mayores al original.

Para hacer unas pruebas, usé un archivo de texto con 10000 caracteres aproximadamente, se puede ver como en un principio hay dificultades, pero se estabiliza.

Como se puede ver, a medida que la cantidad de caracteres por palabra generada aumenta, el radio de compresión disminuye.

El tiempo que tarda en procesar cada palabra generada también disminuye, se puede ver que aproximadamente 10 caracteres por palabra es lo más óptimo para el texto que seleccioné.

Comparado con la implementación normal estos fueron los resultados:

Para los radios de compresión, la implementación anterior es constante.

Los tiempos son muy variables. Depende de la computadora.

Mi conclusión es que se puede mejorar el algoritmo, puesto que bajo ciertas circunstancias tiene un nivel de compresión ligeramente mejor, y sus tiempos son buenos comparados con la implementación normal, el algoritmo hace demasiado uso de recursiones y excepciones para generar la codificación, y cada recursión significa menos eficiencia, y las excepciones son una mala práctica, combinarlas es algo que mejor se debe evitar. 

Así que lo mejor que se puede hacer para mejorar el rendimiento es buscar una alternativa. A nivel compresión seguiría teniendo la misma eficiencia, a nivel de tiempo podría mejorar.

[REDES DE TELECOMUNICACIONES] Lab 7: Resumen de mecanismos de control de congestión

Hop-by-hop Congestion Control over a Wireless Multi-hop Network

Yung Yi and Sanjay Shakkottai    

Link al paper: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp&arnumber=1354675

Este paper se enfoca en el control de congestión sobre redes multisalto inalámbricas. Una restricción importante en las redes inalámbricas surge debido a la capa de Control de Acceso a Medios (MAC). Muchas MAC's inalámbricas usan una estrategia de división de tiempo para acceso de canal, donde, en cualquier punto del espacio, el canal físico puede accederse por un simple usuario en cada instante.

En el paper se habla del desarrollo de un mecanismo de control de congestión de "salto por salto" con esa restricción de las MAC's siendo impuesta en la forma de una restricción de acceso a canal.

1. Introducción

Se considera el problema de congestión sobre redes multisalto inalámbricas. Los nodos están radio-equipados y se comunican vía broadcasting. Las vías de comunicación entre nodos que no están en el rango de radio están establecidas por nodos intermedios actuando como relevadores para transmitir la información hacia atrás o adelante.

Los años pasados, el problema de control de congestión ha recibido atención, tanto en el contexto de Internet como en redes locales. La mayor parte de esta investigación está enfocada en el modelado, análisis, desarrollo de algoritmo de esquemas extremo-a-extremo y la adaptación de esos esquemas redes ad-hoc.

Los esquemas de salto a salto requieren tener mantenimiento de estado por flujo en nodos intermedios, que son los que general problemas de escalabilidad. Como sea, en una red inalámbrica, el número de flujos por nodo es mas pequeño que en el Internet.Normalmente las redes inalámbricas tienen colas de flujo por nodo.

2. Principales aportes

Los principales aportes en el paper son:

Desarrollo de algoritmos de control de congestión proporcionales (tanto para esquemas salto-a-salto como extremo-a-extremo) aprovechando la restricción MAC siendo impuesta a los canales de acceso.

Se considera la evolución de esos algoritmos en la presencia de propagación de delay. Se demuestra analíticamente el efecto de propagación espacial, derivando explícitamente la reducción de la sobrecarga de buffer bajo el esquema salto-a-salto para un árbol de redes.

3. Modelo del sistema

Se considera una red con un set de "L" links, un set de "V" vértices y "cl" será la capacidad finita de un link "l" para "l" ∈ "L". Cada vértice corresponde a una secuencia ordenada de links "l" ∈ "L", y se denota "R" como un set de posibles sesiones. Así, se modela un link inalámbrico entre cualquiera de 2 nodos en la red para tener una capacidad finita positiva.

En la realidad, los canales inalámbricos son de tiempo variable, cada uno con un promedio de capacidad que dependerá del esquema de la capa física. En el paper se modela con links de capacidad constante, aún así este modelo es muy acertado.

A todo esto, hay 2 tipos de restricciones impuestas, llamadas "Restricción de link" y "Restricción de tiempo".

La restricción de link corresponde al hecho de que la suma de promedios de tiempo de todas las sesiones no es mayor a "cl", la capacidad del link "l".

La restricción de tiempo significa que a cualquier momento de tiempo, solo puede haber una instancia de comunicación en un nodo dado.

Se ilustra un ejemplo de 3 sesiones S1, S2 y S3, cada una de ellas atravesando 2 links. "xi" es el promedio de datos para i = 1,2,3. Se observa que la restricción de tiempo es impuesta en cada nodo en la red.

4. Algoritmo salto-a-salto distribuido

En esta sección se desarrolla un algoritmo para el control de congestión. Primero se observó que el controlador de congestión en la fuente de cada sesión reacciona basado en la suma de la congestión de cada nodo. En lugar de pasar el feedback hacia abajo como en un esquema extremo-a-extremo, se puede prever un esquema donde cada nodo pasa una suma parcial hacia arriba. En otras palabras, cada nodo agrega su costo de congestión recibido de los nodos bajos.

En la siguiente figura es ilustra el algoritmo:

La idea básica es que cada nodo en el camino de la sesión opere su propio algoritmo de congestión. En el algoritmo, se puede sumar todos los costos de congestionamiento sobre la sesión. Así que cada nodo opera (por flujo) un controlador basado en la congestión percibida debido a los nodos bajos, y determinan el radio máximo que pueden transmitir.

Heurísticamente, las pruebas de convergencia son válidas incluso cuando un limite es usado debido al radio de transmisión de datos dentro de la red es gobernado por la fuente.

5. Propagación espacial

Ahora se deriva el tamaño de buffer de pico con el controlador de extremo-a-extremo, así como el controlador salto-a-salto.

Se considera la evolución de estos algoritmos en la presencia de la propagación de delay. Analíticamente se muestra el efecto de la propagación espacial, derivando la reducción de la sobrecarga del buffer pico sobre un esquema salto-a-salto.

Se asume que los links intermedios están bien provisionados, asi que si ocurre un congestionamiento, solo ocurrirá en el punto de acceso común para todos los flujos.

6. Resultados de simulación


Se presentan resultados de simulaciones que comparan el algoritmo salto-a-salto con extremo-a-extremo. Se muestra que hay un pico de carga que decrece con el algoritmo de salto-a-salto.

Se usó una topología de N = 5 y L = 5, osea, una red de 5 saltos y 5 sesiones. Cada nodo con capacidad 40, Por lo que hay un equilibrio de 20 bajo la restricción de tiempo. El delay del salto es de 4 unidades, la propagación de delay es D = 20 unidades.

En la grafica 5 se muestra los radios de control, en la 6 se muestra como el pico decrementa para el esquema de salto-a-salto cuando inician los congestionamientos, a diferencia de el esquema extremo-a-extremo que aumenta.

7. Conclusiones

Por lo visto en el paper, se ve que realmente hay una mejora con respecto a los esquemas extremo-a-extremo, sin embargo estos resultados, aunque positivos, muestran mejoras solo en ambientes inalámbricos, pero puede mejorarse para funcionar en otros ambientes.

Se menciona que se busca la implementación sobre la Internet, pero aún está en fase de experimentación.

[VISIÓN COMPUTACIONAL] Lab 7: Detección de agujeros

Para este laboratorio se encargó detectar agujeros mediante el método del histograma lateral. Para esto tomé una fotografía de una caja de cartón a la que le hice 3 agujeros.

Ahora lo que hice es binarizar la imagen con un margen de 70, osea que cualquier RGB menor a 70 se hace negro y el resto blanco, y finalmente invierto la imagen para obtener picos mayores.

Ahora recorro la imagen y genero los histogramas, para eso, guardé una imagen con los histogramas horizontal y vertical sobrepuestos y una con solo los picos mayores.

Esta imagen muestra los histogramas sobre la imagen y pinté los puntos donde se cruzan en verde, que es donde probablemente haya un agujero.

Después, con los histogramas guardados en una lista, los recorrí en busca de los picos mayores, y guardando su posición para pintarlos en la imagen original.

El resultado es el siguiente:

De esta manera ahora guardo solo un punto por cada posible agujero.

El código es el siguiente:
Liga al proyecto:
github.com/victoralex911/vision-computacional

[CÓMPUTO UBICUO] Lab 8: Técnicas de estudio de usabilidad para sistemas de cómputo ubicuo

User-centered Evaluations of Ubicomp Applications

Jean Scholtz1, Larry Arnstein2, Miryung Kim2, Tim Kindberg3, & Sunny Consolvo4

1National Institute of Standards and Technology, 100 Bureau Drive, Gaithersburg, MD 20899

jean.scholtz@nist.gov

2Department of Computer Science & Engineering, University of Washington, Box 352350 Seattle, WA 98195-2350

{larrya, miryung}@cs.washington.edu

3Hewlett-Packard Laboratories, 1501 Page Mill Road, MS 1138, Palo Alto, CA, 94304-1126

timothy@hpl.hp.com

4Intel Research Seattle, 1100 NE 45th St, 6th Floor; Seattle, WA 98105

sunny@intel-research.net 

Link: http://intel-research.net/Publications/Seattle/062120021256_55.pdf

En el paper se discute cómo el evaluar las aplicaciones de cómputo ubicuo presentan algunos retos en investigación sobre aquellos asociados a las aplicaciones tradicionales como lo son las de escritorio y las móviles.

1. Propiedades de las aplicaciones de cómputo ubicuo e implicaciones para evaluacion.

Se proponen varias propiedades que son características de la computación ubicua. A partir de eso se pensó en los aspectos que podrian tener implicación para evaluación.

Las características fueron:

Integración física: Kindberg y Fox usan ese término para describir el uso de sensores o actuadores para unir un sistema a entidades físicas. Como lo son objetos que vemos día con día y que no están asociados con alguna funcionalidad eléctrica como: papeles, tazas, mochilas, etc.

Esta abarca el uso de tecnologías de cómputo ubicuo en actividades como experimentos de laboratorio o visitas a un muséo.

Interoperabilidad espontanea: Los sistemas tradicionales como los sistemas de escritorio funcionan con una configuración de manera que cuando se agrega nuevo hardware/software requieren de alguna actualización o cambio en la configuración.

En la computación ubicua se busca eliminar eso, estos estan en constante cambio, los usuarios y los dispositivos dejan el sistema continuamente, el sistema no puede apagarse, y el usuario espera que el sistema esté disponible una vez que se entra en el cuarto, edificio, etc.

Por eso se le llama interoperabilidad espontanea, ya que se adapta al cambio de forma pasiva, cambiando circuunstancias sin entretener al usuario.

Con estas características se elabora la lista de aspectos que puedan tener implicacones para evaluar.

• Intercalación: Un aspecto de la integración física es que las aplicaciones ubicuas están diseñadas para intercalar las actividades del usuario que no estén relacionadas con dispositivos como computadoras. Para que las aplicaciones ubicuas sean utiles, no debe haber interrupciones en estas actividades.

• Diseño de interacción: Es importante evitar interacciones con ratón o teclado. Esto es porque interactuar con ciertas actividades via habla, gestos o manipulaciones fisicas de objetos son más apropiadas. Algunas mediciones deberian ser: que tan natural es la interacción, que tan robusto es el reconocimiento de interacciones para ser usable, grado de soporte para usuarios novatos y expertos. Estas evaluaciones toman lugar a menudo en ambientes colaborativos, así que es necesario capturar y sincronizar multiples interacciones.

• Interferencias de contexto y actividad: Algunos sistemas ubicuos utilizan la información proporcionada por los sensores y actuadores para hacer inferencias acerca de lo que el usuario está haciendo, su posición, y qué acciones serían útiles para el usuario. Los evaluadores deben medir la precisión de las inferencias y la adecuación de las acciones resultantes adoptadas por el sistema. También deben evaluar lo fácil que es para el usuario para deshacer las acciones deseadas.

• Límites de Responsabilidad: Puede ser difícil para el usuario para determinar lo que la aplicación ubicua puede hacer y la división de responsabilidades entre el usuario y la aplicación. Esto es particularmente cierto ya que los usuarios se mueven entre diferentes entornos ubicuos. Por ejemplo, un usuario puede preguntarse si la "habitación inteligente" localizará automáticamente sus diapositivas sobre la base de la agenda, o si tiene que llevar físicamente sus diapositivas. Las evaluaciones de los limites deben recoger casos en que hay algo que el usuario espera que suceda pero no es así.

• Seguridad y privacidad: Las cuestiones de privacidad y la confianza se producen cuando los usuarios interactúan con los ambientes ubicuos inalámbricos, sobre todo cuando no estan familiarizados con los ambientes ubicuos. Los evaluadores deben determinar si el usuario entiende lo que los registros quedan atrás (si existen) después de que deja el ambiente ubicuo. Si se guarda la información, el usuario tiene que entender que va a tener acceso a esa información y cómo se va a utilizar.Los investigadores necesitan explorar diferentes formas de transmitir la seguridad y la privacidad de la información a los usuarios, el nivel de transmisión de datos que necesitan ser aprobados explícitamente por los usuarios, y qué niveles se de datos acordó implícitamente utilizar en la aplicación. Las evaluaciones de la seguridad y la privacidad deben consistir en datos cuantitativos y valoraciones subjetivas por parte de los usuarios del sistema. Calificaciones cuantitativas pueden identificar incidentes en los que los usuarios se niegan a permitir o intentan prohibir el sistema de obtención de datos. Calificaciones subjetivas pueden pedir a los usuarios lo cómodos que se sienten con el sistema, cómo y dónde se creen se están utilizando los datos del sistema y de que tan ciertas son sus respuestas.

2. Trabajo previo en la evaluación de aplicaciones ubicuas

Classroom 2000: Prepara un áula de aprendizaje equipada con tecnologíaque captura y organiza lecturas en forma que puede ser facilmente accesada en otro momento. Su evaluacion fue de 2 etapas: en su primer prototipo fue evaluada en una escala pequeña sin un control de grupos, despues tuvo una segunda evaluacion, esta vez sumativa con un sistema más robusto que involucraba 60 clases en distintas instituciones.

Su evaluación fué la más extendida hasta ahora reportada. Tomó 18 meses y el uso de varios prototipos en 60 cursos de licenciatura y posgrado y una variedad de universidades. Se usaron grupos de control. Los evaluadores reunieron estadisticas cuantitativas de uso, datos cualitativos del impacto de aprendizaje. Estos datos proporcionaron una visión global de como los instrumentos del aula alteraron la experiencia de clases, así como la forma en que modificba el comortamiento de los estudiantes fuera de clase.

Tivoli: Es un capturador de reuniones. Fué evaluado en 60 reuniones acerca de la propiedad intelectual en Xerox PARC sobre un periodo de 2 años. La informacion fue obtenida de varias formas: grabaciones en video, entrevistas, logs, etc.

3. Viendo a futuro.

Las aplicaciones ubicuas implican mucho más que "computacion". Puesto a que están situadas en entornos fisicos y cambian la forma en que las personas interactuan con estos entronos.

Los casos de estudio ilustran las propiedades de la computacion ubicua que identifican las necesidades de un conjunto nuevo de medidas de evaluación. Muestran algunas de las dificultades que se plantean en la práctica.

Hay una necesidad de desarrollar tecnicas de evaluación que incluyan captura de datos y metodos de análisis para direccionar las propiedades de la computacion ubicua a un ciclo de diseño mas temprano.

[VISIÓN COMPUTACIONAL] Detección de agujeros

Para esta entrada de clase se encargó realizar la detección de todos los agujeros en la imagen. Utilizaré la misma imagen que utilicé en el laboratorio.

En sí solo guardo las posiciones donde hay un cruce de picos. En la imagen anterior hay en total 9 cruces.

Eso fue lo de laboratorio, pero ahora toca juzgar si el cruce se trata de un agujero. Utilicé mi BFS de entregas anteriores para el llenado del agujero. Para esto, mi BFS está preparado para recibir 3 parámetros: la coordenada donde se inicia el llenado, la imagen y el color de llenado. Lo único que hago es ignorar el color de fondo. En este caso al binarizar la imagen e invertirle el color, obtengo un fondo negro.

El resultado es el siguiente:

Y en terminal imprime el área ocupada en la imagen y el porcentaje que representa.

Finalmente hice la prueba con una imagen de Google:

Y su salida en terminal:

El código:
La liga al proyecto:
https://github.com/victoralex911/vision-computacional

[VISIÓN COMPUTACIONAL] Lab 6: Elipses (y Círculos)

En este laboratorio se busca detectar círculos y elipses dentro de una imagen con varias figuras. Según lo descrito en las diapositivas se busca lo siguiente:

• Detectar e identificar todos los elipses/círculos.
• Rellenar cada uno de un color distinto.
• Etiquetar y marcar su centro.
• Imprimir un listado de sus áreas y el porcentaje de la imagen que ocupan.

Para eso utilicé ésta imagen hecha con Sketchpad:

Ya que en el proceso la tengo que convertir en blanco y negro decidí hacerlo de una vez.

Ahora en mi código eliminé la función para detectar círculos y dejé la de elipses como única función, ya que teóricamente un círculo es un elipse con radios iguales. Debido a que los círculos no son perfectos, simplemente agregué un margen que indica que es y que no es un círculo.

La imagen final queda de esta manera:

Y finalmente imprime los porcentajes y áreas ocupadas por cada elipse:

Código:
Liga del proyecto:
https://github.com/victoralex911/vision-computacional

[REDES DE TELECOMUNICACIONES] Lab 6: Generación de tráfico y medidas de desempeño

Para esta semana se encargó realizar generación de tráfico con el NS-2 y medir el desempeño de estas.

Para esto yo utilicé mi topología anterior y guardé el tráfico generado en un archivo de extensión tr.

Este genera un archivo como el que sigue:
Ahora hay que parsear el archivo tr, para obtener la latencia. Lo que se hace es calcular la diferencia de tiempos entre paquetes recibidos y perdidos.

El archivo resultante es el siguiente:
Y al graficar en Gnuplot esto es lo resultante:

Para calcular el throughput se hace un contador que suma los bytes que van pasando cada que se recibe un paquete.

Su archivo de datos resultante es:

Y su gráfica es:

[CÓMPUTO UBICUO] Lab 7: Técnicas de localización en interiores y/o exteriores. Resumen de paper.

Scout: Outdoor Localization Using Active RFID Technology

Xin Huang, Ramakrishna Janaswamy, Aura Ganz

Department of Electrical and Computer Engineering

University of Massachusetts Amherst, MA 01003

{xhuang; janaswamy; ganz}@ecs.umass.edu

Liga al paper: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp&arnumber=4374381

La localización hoy en día es esencial, sin embargo, utilizar los métodos clasicos como el uso de GPS o derivados, son metodos no muy buenos a la hora de buscar objetos pequeños de poder limitado. En el paper se presenta una tecnología llamada "Scout", un sistema de localización sencillo y facil de usar. Utiliza sistemas RFID activos y algoritmos probabilisticos de localización. Se investiga el rendimiento de dependencia en un numero de sistemas y parametros ambientales.

1. Introducción:
Las comunicaciones inalámbricas, computadoras portátiles y sensores inteligentes, son cada vez más populares en la vida diaria y suponen un plus a la computación ubicua y espacios inteligentes donde los objetos fisicos se comunican con los usuarios.

Se busca desarrollar sistemas que puedan ser utilisados en distintos escenarios como seguimiento vehicular, manejo de desastres, educación, espacios de información, etc. El paper se enfoca en la localización fuera donde se propone la tecnología Scout, que provee una solución efectiva y de bajo costo para hacer seguimiento de un gran número de objetos pequeños.

En estos días se utiliza tecnologías como GPS o posicionamiento celular con técnicas como triangulación, o usando otras tecnologías como "angulo de llegada" (AOA), "tiempo de llegada" (TOA), etc. Sin embargo, debido a su gran tamaño y sus costos no tan accesibles, ademas de el gasto de energía que tienen, no son buenos sistemas para el uso que se desea dar.

La tecnología RFID es barata y utiliza poca energía, además de que son de tamaño pequeño. Debido a su potencial, son un candidato perfecto para convertirse en candidato para la localización en masas.

2. Systema Scout:
El sistema Scout utiliza sistemas RFID de largo alcance, similar al sistema Mantis, que opera a 433MHz dando un rango de 500 metros.

2.1 Layout de red:

El sistema consiste en 3 niveles:

• Servidores
• Lectores RFID
• Tags RFID

Los Tags RFID son de 2 tipos, de objeto y de referencia, los tags de objeto son ID's unicos para cada cosa que se está siguiendo. LOa tags de referencia sirven para calibrar parametros ambientales, tambien poseen un ID único. Una vez activadas, los tags emitirán una señal periodicamente con sus ID's.

Los lectores RFID son parte escencial del uncionamiento; Toda el área está cubierta por lectores RFID conectados en red. Los lectores reciben información del ID de los tags, así como su RSSI, por lo que pueden medir la intensidad de señal. Al estar conectados en red se puede triangular la posición de un objeto con su tag.

Los servidores están conectados de tal forma que al menos un tag puede alcanzar un servidor.

El sistema Scout funciona de la siguiente manera:

Una vez iniciado, los lectores empezarán a detectar señal RSSI de los RFID tags. Si están localizados en un rango de lectura, el lector recolecará su información y la enviará a los servidores. Los servidores estimarán la posición utilizando algoritmos de localización provabilística.

2.2 Esquema de localización probabilistica:

El algoritmo propuesto estima la localización de los objetos basado en la información dada por el RSSI de los tags de los objetos y tambien por los tags de referencia de los provistas por los lectores. Sin embargo, ocurren ciertos errores asociados con la propagación RF. Esto hace a que ciertos factores causen variaciones aleatorias en la señal recibida. Esto hace imposible crear una relacion determinista entre la señal RSSI y la distancia de propagación.

EL algoritmo de Scout es robusto a este tipo de errores causados por variaciones en la propagación. Se adapta a las condiciones ambientales para funcionar con los siguientes pasos:

• Se calibra los parametros de propagación usando los tags de referencia.
• Se estima la distancia entre el objeto y los lectores basado en el modelo probabilistico anteriormente descrito.
• Se aplica una interface Bayesiana para determinar la localización.

EL algoritmo se basa en las siguientes suposiciones:

1. Cualquier objeto localizado en el area puede ser detectado por al menos tres lectores RFID.
2. Los lectores tienen posición conocida y constantemente se calibran.
3. Hay un tag de referencia por cada lector, y su localización es conocida.
4. EL poder de transmisión de todos los tags es idéntica.

3. Simulación:

En esta sección se evalua el rendimiento del esquema propuesto, primero se desarrolla una medida de desempeño para añadir presición. Despues se ilustra los resultados visuales que representan las areas resultantes estimadas para multiples objetos. Finalmente se investiga el desempeño de dependencia del esquema sobre el número de parametros ambientales, algoritmos, sistemas, etc.

Se denotó la medida como Error de Distancia Media (AED). La entrada del algoritmo es un estimado del área que está compuesta por varias celdas en grid.

AED es el error entre el objeto y los puntos grid dentro del área estimada. Refleja la presición del algoritmo, entre mas pequeño sea el número, mejor presición.

Para visuaizar, se utilizó MATLAB, se simuló una detección básica. Se consideraron factores ambientales representados por variables aleatorias Gaussianas.

4. Conclusión:

En el paper se presenta una solución para sistemas de localización abiertos basados en tags RFID activos. Así como una aproximación del algoritmo probabilístico para localización usando solo señal RSSI.

Se presentan varias simulaciones donde se toman en cuenta las variables que da el entorno. Así como otras variables agregadas como ruido aleatorio, recursividad, etc.

Se llega a la conclusión de que el sistema es viable para ser un candidato de bajo costo y efectivo para ser candidato para la localización de objetos abierta.

[VISIÓN COMPUTACIONAL] Detección de elipses

Para esta semana se encargó realizar detección de elipses. Utilicé una versión modificada de la forma en que detecto círculos. La imagen que utilicé es la siguiente:

Básicamente hago lo mismo salvo la parte donde busco áreas en base a radios. Ahora busco dos puntos dentro de los bordes que corresponden al punto más lejano y al más cercano.

Después de esto comparo las coordenadas del punto de menor distancia con las coordenadas del centro, con esta comparación obtengo la posición del elipse y así sabré como repintarlos.

Ahora puedo asignar los puntos "x" y "y" de pintado, sumando y restando las distancias máxima y mínima dependiendo de la posición del elipse, generando un elipse fantasma sobre el posible elipse.

Finalmente comparo el área ocupada por el elipse fantasma y el posible elipse, y mediante porcentajes de error decido si se trata de un elipse o si es otra figura.

La imagen final quedará así:

Donde se etiqueta a los elipses encontrados, además se marca con "*" en color rojo los puntos donde se pinta el elipse fantasma y en color rosa los puntos de los radios.

Código:

Liga al proyecto:
https://github.com/victoralex911/vision-computacional

[TEORÍA DE LA INFORMACIÓN] Fundamentos de compresión - Codificación Huffman

Para esta tarea se encargó realizar un programa que al introducirle una cadena de texto genere una codificación Huffman.

David Huffman propuso un método estadístico que permitía asignar un código binario a cada caracter  La longitud de cada código no es idéntica para todos los caracteres: se asignan códigos cortos a los caracteres utilizados con más frecuencia, mientras que los caracteres menos frecuentes reciben códigos binarios más largos.

El algoritmo es simple:

1. Se recorre la cadena de texto y se hace una tabla de frecuencias para cada caracter.
2. Creamos un nodo por cada caracter, éste tendrá 2 valores, el caracter y la frecuencia.
3. Ordenamos de forma ascendente con respecto a las frecuencias y se toman los dos nodos con frecuencias menores.
4. Se agrega un nodo padre para los 2 nodos anteriores y su peso es la suma de frecuencias de ambos. Se agrega a la lista de nodos en su posición correspondiente y se eliminan los nodos hijos.
5. Se repite el proceso hasta que quede un solo nodo en la lista.

El gif de ejemplo de wikipedia:

Y el código es el siguiente:

Y su salida es la siguiente:

Pero ahora realizaré un par de experimentos; será el análisis del peor y el típico caso. Para ésto generaré un par de archivos de texto con las siguientes características.

• El peor caso, es donde existe la misma cantidad de frecuencias para cada caracter.
• El típico caso es donde las frecuencias son generadas aleatoriamente.

Analicé el tamaño original VS el tiempo que tarda, el resultado es el siguiente:

En teoría el tiempo del peor caso es menor puesto que todas sus frecuencias son iguales.

En cambio se puede ver que las compresiones son muy similares, siendo apenas un poco menor la del caso típico.

Finalmente comparo el radio de compresión, puesto que en el peor caso siempre hay frecuencias de caracteres fijos, parece mantener un radio constante.