PROCEDIMIENTO Y SISTEMA PARA LA RESOLUCION DE PROBLEMAS DE OPTIMIZACION MEDIANTE REDES DE DISPOSITIVOS MOVILES.

Procedimiento y sistema para la resolución de problemas de optimización mediante redes de dispositivos móviles que consiste en el aprovechamiento de la capacidad de computación de los dispositivos móviles y la comunicación mediante el estándar Bluetooth{reg} para la transferencia de datos en un entorno distribuido donde todos los dispositivos cooperan para la resolución de problemas complejos.

El procedimiento de la invención que se plantea consiste en ejecutar algoritmos bioinspirados en dispositivos móviles que se comunican mediante la tecnología Bluetooth{reg}. Cada dispositivo se comunica con los demás sin la intervención de ningún servidor central que gestione todo el proceso, o bien, en una arquitectura cliente - servidor (o maestro - esclavo) en donde el servidor es una computadora central que ejecutará un determinado algoritmo de optimización mientras que los clientes (los dispositivos móviles) ejecutarán algoritmos bioinspirados de forma independiente.

PROCEDIMIENTO Y SISTEMA PARA LA RESOLUCIÓN DE PROBLEMAS DE

OPTIMIZACIÓN MEDIANTE REDES DE DISPOSITIVOS MÓVILES

DESCRIPCIÓN

5

Es un objeto de la presente invención un procedimiento y un sistema para el aprovechamiento

de la capacidad de computación de los dispositivos móviles y la comunicación mediante el

estándar Bluetooth® para la transferencia de datos en un entorno distribuido donde todos los

dispositivos cooperan para la resolución de problemas complejos. El procedimiento de la

1 O invención que se plantea consiste en ejecutar algoritmos bioinspirados en dispositivos móviles

que se comunican mediante tecnología inalámbrica, preferentemente Bluetooth® o similar.

Cada dispositivo se comunica con los demás sin la intervención de ningún servidor central

que gestione todo el proceso, o bien, en una arquitectura cliente -servidor (o maestro -

esclavo) en donde el servidor es una computadora central que ejecutará un determinado

15 algoritmo BnB (Branch and Bound, ramificación y poda) mientras que los clientes (los

dispositivos móviles) ejecutarán algoritmos bioinspirados de forma independiente.

ESTADO DE LA TÉCNICA ANTERIOR

2 O Bajo el término de algoritmos bioinspirados se engloba a un amplio conjunto de técnicas de

resolución de problemas de optimización complejos basadas en la emulación de los procesos

naturales de la biología. Entre las técnicas bioinspiradas se encuentran por ejemplo los

algoritmos evolutivos, las redes neuronales, los sistemas de lógica difusa y las colonias de

hormigas entre otros. Estos algoritmos son llamados así porque se inspiran en procesos

2 5 biológicos y algunos de ellos, en concreto los algoritmos evolutivos, particularmente en su

base genético-molecular. Se ha demostrado que, en problemas de optimización, estas técnicas

alcanzan soluciones óptimas (o cercanas a las óptimas) con un coste computacional aceptable

que es muchas veces menos que el que consumen otras muchas técnicas de resolución de

problemas de optimización.

30

Por otra parte, las técnicas de Ramificación y Poda (BnB, por sus siglas en inglés Branch and

Bound) son ampliamente utilizadas en la resolución de problemas de optimización. Muy

básicamente, estas técnicas realizan una enumeración parcial del espacio de soluciones

basándose en la generación de un árbol de expansión implícito. Inicialmente, se considera un

3 5 nodo que representa el espacio de soluciones completo y que, sucesivamente, es ramificado en

otros nodos que representan particiones del espacio de búsqueda original. Adicionalmente, se

utilizan cotas para podar aquellas ramas del árbol que no conducen a la solución óptima,

reduciendo considerablemente el espacio de búsqueda.

Básicamente en un algoritmo de Ramificación y Poda se realizan tres etapas. La primera de

ellas, denominada Selección, se encarga de extraer un nodo de entre el conjunto de nodos

5 vivos. La forma de escogerlo varía dependiendo directamente de la estrategia de búsqueda que

decidamos para el algoritmo. En la segunda etapa, la Ramificación, se construyen los posibles

nodos hijos del nodo seleccionado en el paso anterior. Por último se realiza la tercera etapa, la

Poda, en la que se eliminan algunos nodos creados en la etapa anterior. Esto contribuye a

disminuir en lo posible el espacio de búsqueda y así atenuar la complejidad de estos

1 O algoritmos basados en la exploración de un árbol de posibilidades. Aquellos nodos no

podados pasan a formar parte del conjunto de nodos vivos, y se comienza de nuevo por el

proceso de selección. El algoritmo finaliza cuando no quedan más nodos por explorar.

Para cada nodo del árbol dispondremos de una función de coste que nos estime el valor

15 óptimo de la solución si continuáramos por ese camino. De esta manera, si la cota que se

obtiene para un nodo, que por su propia construcción deberá ser mejor que la solución real (a

lo sumo, igual que ella) , es peor que una solución ya obtenida por otra rama, podemos podar

esa rama pues no es interesante seguir por ella. Evidentemente no podremos realizar ninguna

poda hasta que hayamos encontrado alguna solución. Por supuesto, las funciones de coste han

2 O de ser monótonas respecto a la profundidad del árbol, es decir, si consideramos por ejemplo

un problema de minimización, entonces si h es una función de coste entonces h (n) <= h (n')

para todo n' nodo descendiente den.

2 5 Recientemente, los firmantes de la invención aquí descrita han especificado en su artículo

("On the Hybridization of Memetic Algorithms With Branch-and-Bound Techniques", IEEE

Transactions on Systems, Man, and Cybernetics, Part B 37 (1) : 77-83, 2007) un modelo

híbrido paralelizable entre estas una técnica de BnB y un algoritmo bioinspirado

(concretamente un algoritmo genético AG) que ha resultado ser exitoso en la resolución de

3 O problemas de optimización. Este modelo o procedimiento de cómputo considera dos formas

diferentes de abordar los problemas de optimización combinatoria que no son excluyentes y

pueden trabajar juntas para resolver un problema determinado. La integración entre los dos

algoritmos se lleva a cabo mediante una fase de comunicación en la que el AG envía su mejor

solución al BnB y viceversa, el BnB envía al AG un conjunto de soluciones parciales

3 5 prometedoras convertidas en soluciones completas mediante técnicas ávidas. El BnB usa la

solución recibida para realizar el proceso de poda en la cola de nodos vivos, eliminando los

problemas parciales cuya cota superior sea inferior a la solución hallada por el AG. El BnB

O

5

O

inyecta información de las regiones más prometedoras del árbol de búsqueda en la población del AG, de forma que siempre haya una población heterogénea en las generaciones del AG.

Por otro lado, Bluetooth® es una tecnología de comunicación inalámbrica que define una plataforma estandarizada en la que destaca el bajo consumo y bajo coste de sus elementos, facilitando una comunicación sin cables entre dispositivos móviles. Se incluye dentro de la especificación de esta tecnología tanto los detalles de cómo se ha de llevar a cabo el enlace de comunicación entre los dispositivos, como los detalles de la capa de aplicación por la que se podrá explotar las funcionalidades de estas comunicaciones. Bluetooth® opera en el rango de radiofrecuencia de los 2.4GHz (2.400-2.4835 GHz) que no requiere licencia de uso en ningún lugar del mundo. Se guarda una banda de 2 MHz en el comienzo y 3.5 MHz final del rango para cumplir con las regulaciones de todos los países.

La tecnología de comunicaciones Bluetooth® hace posible la transmisión de voz y datos entre diferentes dispositivos mediante un enlace de radiofrecuencia. Estos dispositivos deben llevar integrado hardware específico para dar soporte a esta tecnología. Entre los dispositivos más comunes encontramos teléfonos móviles, computadoras de mano (Palm, Pocket PC) , cámaras digitales, ordenadores portátiles e impresoras.

EXPLICACIÓN DE LA INVENCIÓN

El problema técnico objetivo que soluciona la presente invención es el incremento de la velocidad de cómputo en la resolución de problemas de optimización en la asignación de recursos, aprovechando de forma distribuida una pluralidad de elementos móviles, en donde todos los dispositivos cooperan en dicha resolución. En la presente invención se entiende por dispositivo móvil tanto PDAs, como teléfonos móviles, ordenadores portátiles, Smartphone, o cualquier dispositivo móvil con capacidad de comunicación inalámbrica vía Bluetooth®.

Más concretamente, en un primer aspecto de la invención, el procedimiento y sistema para la resolución de problemas de optimización mediante redes de dispositivos móviles, objeto de la presente invención, se intercambia información, a través de tecnología Bluetooth® o de otra tecnología inalámbrica como WiFi o similar, de algoritmos bioinspirados o algoritmos adaptados a la resolución de un proceso específico, ejecutados en dispositivos móviles. Este procedimiento consiste, esencialmente, en ejecutar un algoritmo bioinspirado en cada uno de los dispositivos móviles de la estructura. Todos los algoritmos se dedican a resolver la misma instancia del problema con el objeto de compartir información. La comunicación entre estos dispositivos se realiza mediante transferencia de candidatos a las soluciones de un problema,

vía tecnología Bluetooth, de los dispositivos móviles que actúan como esclavos al dispositivo

móvil que actúa como maestro,...

12

1. Procedimiento para la resolución de problemas de optimización mediante redes de

5 dispositivos móviles mediante el incremento de la velocidad de cómputo en la resolución de

problemas de optimización en la asignación de recursos. aprovechando de forma distribuida

una pluralidad de dispositivos móviles, en donde todos los dispositivos cooperan en la

resolución de una instancia o variable del problema de optimización que se caracteriza porque

(a) comprende al menos una red de dispositi vos móviles para cada instancia o variable de un

10 problema de optimización a resolver, (b) donde cada uno de los dispositivos móviles de la red

implementa de forma independi ente un algoritmo de optimización dedicado a la resolución de

una única instancia o variable del problema de optimización, (e) de tal fonna que cuando un

dispositivo móvil de la red actuando en modo cliente o esclavo se encuentra dentro del radio

de alcance de otro dispositivo actuando en modo servidor o maestro se establece una

15 comunicación entre ambos dispositivos (d) mediante transferencia de candidatos a soluciones

(obtenidas por los algoritmos ejecutados en cada uno de los dichos dispositivos móviles) para

la instancia o variable que mediante la red de dispositivos móvi les se trata de resolver en el

contexto del problema de optimización en cuestión.

20 2. Procedimi ento de acuerdo con la reivindicación anterior que se caracteriza porque

un mismo dispositivo móvil de la red pueden adoptar el rol (o funcionar en modo) de (a)

cliente o esclavo, en cuyo caso el dispositivo tomará la iniciativa en las comunicaciones

realizando la búsq ueda de dispositivos y servicios y se conectará a algún dispositivo o servicio

que esté resolviendo la instancia o variable actual en viando individuos O candidatos a

25 soluciones al dispositivo o servicio con el que el dispositivo cliente conecte; o de (b) servidor

O maestro, donde el dispositivo queda a la escucha para que un dispositivo cliente se pueda

conectar a él y le transmita individuos o candidatos a soluciones; pudiendo el mismo

dispositivo adoptar (e) ambos roles simultáneamente, en cuyo caso el dispositivo podrá tanto

tomar la iniciativa en las comunicaciones (modo O rol cliente) como quedar escuchando

3 O conexiones (modo o rol servidor) .

3. Procedimiento de acuerdo con cualquiera de las rei vindicaciones anteriores que se

caracteriza porque el algoritmo de optimización es un algoritmo bioinspirado o bien un

algoritmo de ramificación y poda.

35

4, -Procedimiento de acuerdo con la reivindicación anterior que se caracteriza porque el algoritmo bioinspirado es un algoritmo genético.

5. Procedi miento de acuerdo con la reivindicación que se caracteriza porque la comunicación entre los dispositivos se realiza de forma sincrona o asíncrona.

.

6. Procedimiento de acuerdo con las reivindicaciones anteriores que se caracteriza porque puede existir más de una piconet involucrada en el esquema global de res~lución dando lugar a subestructuras que se comunican mediante dispositivos esclavos comunes a las piconets entre las cuales se establece la comunicación.

7. Procedimiento de acuerdo con cualquiera de las reivindicaciones anteriores que se caracteriza porque comprende además al menos un dispositivo que consiste en un servidor o computador central que implementa un algoritmo de optimización dedicado a la resolución de una única instancia o variable del problema de optimización, pudiendo dicho computador central adoptar los roles de (a) servidor o maestro, donde el dispositivo queda a la escucha para que un dispositivo cliente se pueda conectar a él y le transmita individuos o candidatos a soluciones; o de (b) cliente o esclavo, en cuyo caso el dispositivo tomará la iniciativa en las comunicaciones realizando la búsqueda de dispositivos y servicios, y se conectará a algún dispositivo o servicio que esté resolviendo la instancia o variable actual enviando individuos o candidatos a soluciones al dispositivo o servicio con el que el dispositivo cliente conecte;

pudiendo el mismo dispositivo adoptar (e) ambos roles simultáneamente, en cuyo caso el dispositivo podrá tanto quedar escuchando conexiones (modo o rol servidor) como tomar la iniciativa en las comunicaciones (modo o rol cliente) .

8, -Procedimiento de acuerdo con la reivindicación anterior caracterizado porque (a)

tanto el computador central como cada uno de los dispositivos móviles de la red implementan de forma independiente un algoritmo de optimización dedicado a la resolución de una única instancia o variable del problema de optimización, (b) de tal forma que cuando un dispositivo móvil de la red actuando en modo cliente o esclavo se encuentra dentro del radio de alcance del computador central actuando en modo servidor o maestro se establece una comunicación entre ambos dispositivos Ce) mediante transferencia de candidatos a soluciones (para la instancia o variable que mediante la red de dispositivos móviles se trata de resolver en el contexto del problema de optimización en cuestión) desde el dispositivo móvil hacia el computador central y desde el computador central a cada uno de los dispositivos móviles con el fin de mejorar la búsqueda de soluciones de forma independiente en cada uno de ellos.

3.

9. Procedimiento de acuerdo con cua1quiera de las reivindicaciones 7 u 8 que se caracteriza porque el algoritmo de optimización que implementa cada uno de los dispositivos

AS solicitud F.Efectlva 18/07/2013

14

móviles es un algoritmo bioinspirado y el algoritmo de optimización que implementa el computador central es un algoritmo de ramificación y poda.

5 10. Procedimiento de acuerdo con la reivindicación anterior que se caracteriza porque el algoritmo de optimización que implementa cada unO de los dispositivos móviles es un algoritmo genético.

10 15 II.~ Sistema para la reso lución de problemas de optimización mediante redes de dispositivos móviles que comprende medios para implementar el procedimiento de las reivindicaciones I a 10 que se caracteriza porque cada dispositivo móvil comprende, al menos, dos subsistemas que se lanzan en hebras independientes y donde estos subsistemas cooperan entre sí y realizan labores claramente diferenciadas: el subsi stema de ejecución del algoritmo de optimización cuya función es la de instanciar un problema y ejecutar su resolución; y el subsistema de comunicaciones, el cual desacopla la ejecución del algoritmo del proceso de comunicaciones, que se reali za de forma independiente.

2 O 12.~ Sistema de acuerdo con la rei vi ndicación anterior que se caracteriza porque el subsistema de comunicaciones se compone de dos módulos principales que realizan las labores de cliente uno y de servidor el otro, ambos utilizan el protocolo SPP para comunicarse; y donde para adquirir el ro] de cliente, tendrá que estar activo el módulo de cliente, para adquirir el rol de servidor, tendrá que estar activo el módulo de servidor y para adquirir el rol P2P cliente/servidor, tendrán que estar activos ambos módulos.

25