Medir distancia al emisor WiFi.

La idea es sencilla, mides la potencia de la señal de varias estaciones cuya posición conoces, con la potencia calculas la distancia a cada estación y a partir de ahí con geometría básica calculas tu posición. Parece fácil, hasta que lo intentas y vas viendo como todo se complica.

Como estación vamos a usar un emisor WiFi, eso nos permitirá realizar pruebas fácilmente ya que podemos usar cualquier router WiFi como estación y como receptor cualquier móvil. Vamos a empezar por lo mas sencillo, medir la distancia a un solo nodo cuya localización conocemos. En nuestro receptor podemos ver la potencia. ¿Como convertimos la potencia en distancia?. Las malas noticias es que no es lineal. Las buenas es que hay fórmula (Free-space path loss) para hacerlo de manera aproximada

dB = 20log₁₀(d) + 20log₁₀(f) + K

K varia segun las unidades de medida de la distancia d y la frecuencia f, siendo:

K = 92.45 si d está en km y f en Ghz
K = -87.55 si d está en m y f en Khz
K = -27.55 si d está en m y f en Mhz
K = 32.45 si d está en km y f en Mhz

Lo que nos interesa son metros y Mhz. Como frecuencia de la seña WiFi se puede usar siempre 2400 Mhz sin temer cometer un gran error (aunque ya hay algunas redes que operan a otras frecuencias como 5 Ghz)

Aunque no es del todo exacta en muchas aplicaciones usan directamente esta formula para calcular la distancia. En el receptor podemos conocer la atenuación (dB), la frecuencia (f) y la constante (K). Ahora podemos resolver la distancia (d).

dB – (20log₁₀(f) + K) = 20log₁₀(d)

Cómo ni f ni K van a variar en nuestro caso vamos a remplazarlos por una constante C

dB – C = 20log₁₀(d)

Despejando d

d = 10^((dB – C)/20)

Si queremos ser mas exactos no basta con leer la potencia de señal que se recibe en el receptor ya que la formula esta expresada en decibelios (dB) y la potencia de la señal WiFi nos la devuelve el sistema en decibelios-miliwatio (dBm). Que aunque aparentan ser lo mismo no lo son. Los dB son una medida relativa de potencia entre dos valores (en este caso serian la potencia de emisión del nodo WiFi y la potencia percibida en el receptor). Sin embargo los dBm indican un valor de potencia expresado en relación a 1 mW. Que para los que no estamos acostumbrados a este campo todo esto nos suena a chino y lo único que queremos saber es: ¿Como se convierte de una unidad a la otra?. Pues no es tan sencillo porque cada unidad mide cosas diferentes. Voy a tratar de explicarlo para este caso y perdonarme si meto mucho la pata, ya os digo que no es un tema que domine. Los dB serian la diferencia de potencia entre la señal original y el punto donde estas recibiéndola y se calcula como:

dB = 10log₁₀(P/P0)

Siendo P la potencia medida y P0 la emitida o de referencia. Necesitamos obtener esas dos potencias. Para ello podemos usar los dBm, que son los dB medidos tomando como potencia de referencia 1mW por lo que la formula queda:

dBm = 10 log₁₀(P/1mW)

Podemos calcular P en mW fácilmente.

P = 10 ^ (dBm/10)

¿Pero de donde sacamos P0?. Los que esperéis complicados cálculos siento decepcionaros. La forma de calcular P0 (de forma aproximada) es acercarse lo más posible al emisor y medir la potencia en dBm, despejar la formula anterior y usar ese valor como P0.

Con todo esto podemos calcular el valor en dB de la atenuación de la señal. Así que ahora podemos volver a la primera formula para calcular la distancia.

En javascript

function dBm2dB(dBm0, dBm){
  var P0 = Math.pow(10, dBm0/10);
  var P = Math.pow(10, dBm/10);
  var dB = 10 * Math.log10(P/P0);
  return dB;
}

function fspl(dB,f,K){
  var logF = 20*Math.log10(f) + K;
  var d = Math.pow(10, (Math.abs(dB) - logF)/20);
  return d;
}

//ejmeplo
fspl(dBm2dB(-29, -58), 2400, -27.55)*10;

¿Que tal resultado da? Pues por alguna extraña metedura de pata que no logro localizar necesito multiplicar el resultado por 100 para que las cifras tengan sentido. La aproximación es buena pero no lo suficiente, incluso sin moverse los valores de la señal varían mucho. Como sistema de localización, la potencia de la señal WiFi deja mucho que desear

Derivada numérica y gradiente

Derivada

La derivada df de una función f es otra función que expresa la tasa de cambio de f. Por ejemplo si tenemos una función que calcula la velocidad en el punto X y calculamos su derivada tendremos una función que calcula la aceleración (cambio de la velocidad) en el punto X. Otra forma de entenderla es como la pendiente en un punto. Si calculamos la derivada de la función fitness en un punto tendremos una función que nos dice cuánto varía y si aumenta o disminuye. Es decir nos da una pista clara de en qué sentido hay que moverse para aumentar o disminuir el valor de la función.

Esto también quiere decir que si la pendiente es 0 ya estás en un máximo o en un mínimo. Si calculas todos los puntos donde la derivada es 0 seguro que uno de ellos es el máximo o el mínimo que estás buscando. Desgraciadamente en muchos casos no es sencillo hallar esos puntos.

Siendo una herramienta tan útil vamos a ver cómo calcularlo. A muchos os sonará de haberlo estudiado y haber tenido que memorizar un montón de derivadas y luego aprender reglas de derivación (por partes, cambio de variables,…) Incluso puede que tener pesadillas con ellas. Pero los ordenadores no saben hacer ese tipo de derivadas. Con ellos hay que recurrir derivadas numéricas que son mucho más simples.

df(x) = f(x+h) – f(x-h) / 2*h

¿Cuanto es h? Lo ideal es que sea una cantidad lo más pequeña posible. Pero ojo con cantidades muy pequeñas y la precisión numérica de los lenguajes de programación que puede dar sorpresa. Cómo se puede ver en el código más abajo yo he fijado el valor por defecto a 0,001.

this.epsilon = epsilon || 0.001;

this.diff = function(x, f){
  return (f(x+this.epsilon)-f(x-this.epsilon))/(this.epsilon*2);
}

Para ir más allá de la primera derivada también hay fórmulas para calcularla numéricamente que son más exactas que el método que vamos a usar nosotros pero en este caso me ha parecido más interesante el siguiente método.

Tenemos una función diff(x,f) que calcula la derivada de f en el punto x. Si hacemos diff(3,diff(3,f)) calcularíamos la segunda derivada de la función f en el punto 3. Para la tercera tendríamos que hacer diff(3,diff(3,diff(3,f))). Para las siguientes derivadas creo que ya habéis entendido como funciona.

En lugar de escribir todas las funciones una detrás de otra en una larga cadena vamos a usar una función que lo haga por nosotros. Siendo el parámetro n el número de derivada que calculará.

this.diffN = function(n, x, f){
  if(n == 1)
    return this.diff(x,f);
  else
    return this.diffN(n-1, x, function(x){return that.diff(x,f)});
}

Gradiente

Ya hemos visto como funciona la derivada para una función f(x) en un punto A, ahora os estaréis preguntando «¿Cómo funciona la derivada para una función con más variables como f(x1, x2)?» ¿A qué os he leído la mente?. Esta vez el punto donde se calcula tiene dos coordenadas [A,B]. Se calculan dos derivadas respecto de x1 y respecto de x2. Lo de «respecto» significa que solo se va a calcular modificando esa varíable, la otra será estática.

df(x1,x2)/dx1 = f(x1-h,x2)-f(x1+h,x2)/2*h

Es decir dejamos el resto de las «equis» inalteradas.

El gradiente es el cálculo de la derivada respecto a «cada equis». Es decir que

G = [df(x1,x2)/dx1, df(x1,x2)/dx2];

Podemos calcular el segundo, tercer,…. gradiente calculando la correspondiente derivada.

Nuestra función para calcular el gradiente usando la función anterior para calcular la derivada numérica queda así:

this.gradN = function(n, x, f){
  G = [];
  for(var i = 0; i < x.length; ++i){
    var auxX = x.slice(0);
    var fdx = function(x){auxX[i] = x; return f(auxX);}
    G.push(this.diffN(n, auxX[i], fdx));
  }
  return G;
}

Para que el uso sea más intuitivo vamos a hacer una versión del primer gradiente sin el parámetro n (n=1)

this.grad = function(x, f){
return this.gradN(1,x,f);
}

Puedes ver todo el código en este repositorio de github.

Condición de parada

Si ya hemos elegido nuestro algoritmo favorito y la función fitness que vamos a usar, lanzamos nuestro programa y surge un problema ¿Cuando páramos?.

Lo fácil sería decir que cuando alcancemos el resultado deseado, pero eso no es siempre posible o al menos no en un tiempo que sea razonable. Así que tendremos que quedarnos con una buena aproximación. ¿Pero cual es una buen aproximación? Hay veces que lo sabemos, sabemos que resultado nos tiene que dar al función fitness para que la solución sea suficiente para nosotros. ¿Pero que pasa si no sabemos cuando ha llegado al máximo o al mínimo de la misma?. Con las metaheurísticas siempre nos quedaremos con la duda. No podemos saber si hemos encontrado el punto optimo o nos hemos quedados atrapados en un máximo/mínimo local. Todo dependerá de nuestras necesidades y conocimiento del espacio de búsqueda.

Para reducir este problema hay que intentar explorar lo máximo posible el espacio de búsqueda. El punto optimo puede esconderse en cualquier rincón que nos dejemos sin mirar. Pero claro si estamos usando una metaheurística es porque no conocemos el espacio de búsqueda y es muy grande como para que lo exploremos.

Una de las condiciones más usadas en el caso de desconocimiento total es fijar de antemano un número de iteracciones. Es útil cuando tenemos un tiempo o recursos limitados para calcular la solución. Sin embargo puede darse el caso de que el tiempo no sea tan limitante, aunque tampoco nos apetezca tener al algoritmo iterando durante varias veces la vida del universo. En ese caso se puede fijar un umbral de «mejora». De tal manera que si durante un número determinado de iteracciones el resultado no ha mejorado la solución por encima de ese umbral se para la ejecución ya que se considera que el tiempo invertido no compensa la mejora obtenida.

Por último la que me atrevería a decir que es la condición más usada pero que ningún libro habla de ella. Ir mostrando datos en pantalla y que el usuario decida cuando terminar la ejecución. Puede parecer una solución «poco inteligente» pero durante las pruebas de un algoritmo para ver qué tal se comporta con un problema o viendo si se puede afinar su configuración puede ahorrar mucho de tiempo.

De todas formas muchas veces nos obsesionamos con encontrar el resultado optimo y en la vida real muchas veces basta con una aproximación que ni siquiera sea muy buena.

Descenso del gradiente

Si hay una metaheurística de ascender montañas tiene que haber otra de bajarlas. El descenso del gradiente se basa en usar el gradiente de guía para encontrar el mínimo de una función. El gradiente indica la pendiente máxima en un punto y hacia donde tenemos que dirigirnos para ascender (a favor del gradiente) o descender (en contra del gradiente). Sabiendo eso solo hay que moverse en la dirección indicada por el gradiente. ¿Cuanto? Ahí está el problema. Si el paso es muy grande podrías pasarte el mínimo y si es muy corto puedes acabar dando un gran número de pasos. Cómo lo de dar un gran número de pasos solo es un problema cuando lo haces con papel y lápiz y los ordenadores no se cansan de caminar (siendo cada paso una iteración del algoritmo) es preferible el segundo caso. Cada vez que se llega a un nuevo punto se calcula el gradiente en ese punto y se avanza en esa nueva dirección.

Supongamos que aún con nuestras precauciones de dar pasitos pequeños nos pasamos del mínimo. ¿Cómo podemos saberlo?. En la imagen de debajo se puede ver un ejemplo. Primero empezamos a «rebotar» de un lado a otro de la función, mientras el valor decrezca vamos bien. El problema surge si el valor aumenta (en la imagen el paso del punto f al g) . En ese caso hemos de volver al punto anterior, reducir el tamaño del paso y seguir probando hasta que se obtenga un valor fitness menor.

descensoGradienateProblema

Lo ideal sería llegar a un punto donde la pendiente sea 0 (eso indica que es un máximo o un mínimo). Pero en la practica no siempre es posible y al final hemos de depender de las condiciones habituales, llegar a una solución lo suficientemente próxima a la ideal, alcanzar cierto numero de iteraciones o llegar a un tamaño de paso tan pequeño que no merezca la pena continuar.

Ya hemos visto como calcular de forma numérica la derivada y el gradiente. Ahora hemos de aplicar ese conocimiento para calcular el gradiente de la función fitness. Como el descenso del gradiente esta pensado para minimizar, hemos de elegir una función fitness que a menor valor mejor resultado.

Cada nueva coordenada seria la antigua coordenada menos el valor de la derivada de la funcion para esa coordenada multiplicado por el tamaño del paso Kstep.

cordX = cordX – (Kstep * dF/dx)

O lo que es lo mismo en código:

var grad = diff.grad(cords, this.model.calculateFitness);
for(var i = 0; i < this.parameters.dimensions; ++i){
  cords[i] -= this.parameters.step*grad[i];
}

Si el nuevo valor de fitness es menor adoptamos esas coordenadas como nueva solución, si es mayor reducimos el tamaño del paso y volvemos a probar:

if(newFitness < this.fitness){
this.cords = newCords;
this.fitness = newFitness;
} else {
this.parameters.step *= this.parameters.reduceStep;
}

El código completo puede verse aqui.

Imagen integral

La imagen integral es una técnica para acelerar el calculo de operaciones que incluyan la suma del valor de los pixeles de un área. Para calcular la imagen integral hay que reemplazar cada píxel por la suma de todos pixeles contenidos en un rectángulo cuya esquina superior izquierda es el vértice 0,0 de la imagen . Y cuya esquina inferior derecha es el propio pixel.

Veamoslo con un ejemplo, partimos de una imagen de 4×4 con lo siguientes pixeles:

1	1	1	1
2	2	2	2
3	3	3	3
4	4	4	4

La forma más intuitiva de verlos es como un proceso en dos iteraciones. en la primera se suman todas las celdas de cada fila de izquierda a derecha:

1	1+1=2	2+1=3	3+1=4
2	2+2=4	4+2=6	6+2=8
3	3+3=6	6+3=9	9+3=12
4	4+4=8	8+4=12	12+4=16

1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

Luego sumamos las columnas de arriba hacia abajo:

1	2	3	4
2+1=3	4+2=6	6+3=9	8+4=12
3+3=6	6+6=12	9+9=18	12+12=24
4+6=10	8+12=20	12+18=30	16++24=40

El resultado:

1	2	3	4
3	6	9	12
6	12	18	24
10	20	30	40

Vale, tenemos una imagen con la suma de los valores de los pixeles. ¿Para qué nos sirve?. Para obtener con solo cuatro operaciones el total de la suma de de todos los pixeles de cualquier rectángulo de la imagen. Su uso es muy sencillo. Tomamos las cuatro esquinas A-B-C-D. El valor del pixel D en la imagen integral es el valor del área desde la esquina superior izquierda hasta el punto D. Le restamos el valor del área C (valor del punto C en la imagen integral) y el valor del área B (valor del punto B en la imagen integral). El problema es que ahora hemos restado una parte dos veces, por fortuna esa parte corresponde con el valor del área de A (seguro que ya sabes lo que va en estos paréntesis) solo hay que sumarlo. En resumen:

Valor del área ABCD = D – C – B + A

ABCD	BD	BD	4
CD	D	D	12
CD	D	D	24
10	20	30	40

¿Para qué sirve esto?. Se usa generalmente cuando tenemos algoritmos de ventana deslizante que necesitan calcular el valor de la suma del área comprendida por la ventana. Por ejemplo que necesiten el valor medio de un área o algún otro valor estadístico. No es necesario que lo que se sume sea el valor del pixel puede ser su cuadrado o simplemente 0 y 1 si es blanco o negro.

Es una herramienta útil para reducir los cálculos de distintos algoritmos, sobre todo de los que usan ventana deslizante.

Ventana deslizante y pirámide de imágenes

Se llama venta deslizante a seleccionar un rectángulo dentro de la imagen (la ventana) aplicar sobre él un conjunto de operaciones y luego desplazar (deslizar) la ventana un pixel y repetir el proceso, cuando llega al final de la linea se vuelve al principio y se baja una fila de pixels. Con un ejemplo se ve fácilmente, siendo los cuadros rojos la ventana seleccionada.

*	*	*	*
*	*	*	*
*	*	*	*
*	*	*	*

*	*	*	*
*	*	*	*
*	*	*	*
*	*	*	*

*	*	*	*
*	*	*	*
*	*	*	*
*	*	*	*

*	*	*	*
*	*	*	*
*	*	*	*
*	*	*	*

Se usa principalmente para la búsqueda de características. O para aplicar algoritmos que solo tiene en cuenta la vecindad. La convolución seria un ejemplo.

Es habitual su uso con una pirámide de imágenes que no es más que usar la misma imagen pero escalandola en cada paso para reducir su tamaño. Se usa cuando el algoritmo que se aplica en la ventana deslizante es dependiente de la escala, por ejemplo un histograma no lo es, pero un detector de caras si que lo es (no se lo mismo que la ventana abarque toda la cara que que abarque solo media cara). Cada iteración de la pirámide la imagen se reduce en un porcentaje pequeño y sobre la imagen resultante se aplica la ventana deslizante.

Una explicación más visual, con una reducción del 50% (generalmente es más pequeña)

8×8

*	*	*	*	*	*	*	*
*	*	*	*	*	*	*	*
*	*	*	*	*	*	*	*
*	*	*	*	*	*	*	*
*	*	*	*	*	*	*	*
*	*	*	*	*	*	*	*
*	*	*	*	*	*	*	*
*	*	*	*	*	*	*	*

4×4

*	*	*	*
*	*	*	*
*	*	*	*
*	*	*	*

2×2

*	*
*	*

Estos algoritmos suelen ser buenos candidatos a ser optimizados usando una o varias imágenes integrales.

Regresión Lineal en Arduino

La regresión lineal es útil cuando tenemos dos variables relacionadas linealmente o cuya relación se puede aproximar a la ecuación de un línea. La forma habitual de verlo es como una nube de puntos donde se calcula una recta que minimiza la distancia a todos los puntos. Se puede ver un ejemplo extraído de la wikipedia debajo:

De Sewaqu – Trabajo propio, Dominio público, Enlace

Nosotros vamos a usarlo para calcular de forma automática la relación entre dos variables, siempre y cuando esta sea lineal. Al final del proceso obtenemos la ecuación de una recta en la forma:

y = mx + b

Para ello se parte de una muestra de valores (x, y). Estos valores no deben de coincidir exactamente con la recta (serian los puntos azules de la imagen).

Las formulas para calcular lo parámetros:

m = σ²(x,y) / σ²(x)

b = µ(y) – m * µ(x)

Siendo σ²(x,y) la covarianza, σ²(x) la varianza y µ(x) la media

El mayor problema que hay en el caso de un arduino es que no hay memoria para guardar todas las muestras así que hemos de encontrar una forma de ir calculando estos valores estadísticos sin guardar todo el histórico de datos, de forma incremental. La solución la encontré aquí. Así no hace falta guardar todos os valores, esto ademas permite que el algoritmo este siempre aprendiendo, aunque lo veremos más adelante.

También podemos calcular la correlación entre variables. Contra más cercano a a 1 o -1 mejor ya que indica una alta correlación entre ambas variables, sin embargo si es cercano a 0 indica una nula correlación.

r = σ²(x,y) / (σ(x) * σ(y))

Siendo r la correlación y σ(x) la desviación estándar, igual a √σ²(x).

Al final los cálculos en C para el arduino de m y b quedan en:


meanX = meanX + ((x-meanX)/n);
meanX2 = meanX2 + (((x*x)-meanX2)/n);
varX = meanX2 - (meanX*meanX);

meanY = meanY + ((y-meanY)/n);
meanY2 = meanY2 + (((y*y)-meanY2)/n);
varY = meanY2 - (meanY*meanY);

meanXY = meanXY + (((x*y)-meanXY)/n);

covarXY = meanXY - (meanX*meanY);

m = covarXY / varX;
b = meanY-(m*meanX);

Y para la correlación:

double stdX = sqrt(varX);
double stdY = sqrt(varY);
double stdXstdY = stdX*stdY;
double correlation;

if(stdXstdY == 0){
  correlation = 1;
} else {
  correlation = covarXY / stdXstdY;
}

Limites

En la vida real lo más probable es que no nos interese aplicar la regresión lineal a todos los posibles valores de la función solo a los que están contenidos entre dos punto para ello se fijan los limites en los que la linea esta definida en el constructor.

LinearRegression lr = LinearRegression(0,100);

Fijar el valor de N

Una de las ventajas de este algoritmo es que es capaz de ir recalculando su valor de manera dinámica según se añaden más datos. El problema es que según crece n los nuevos datos cambian la media cada vez menos. Si por ejemplo tratamos con un valor que cambia con el tiempo y queremos que la recta se vaya adaptando debemos fijar el valor de n de tal forma que lo permita. Lo complicado esta en acertar con ese valor, si es muy bajo sera muy sensible al ruido y si es muy alto necesitara mucho tiempo para adaptarse a los nuevo valores.

En este caso se puede hacer con la función fixN

lr.fixN(100);

Regresión lineal segmentada

El principal problema de la regresión lineal es que es lineal. ¿Y si necesitamos que se adapte a una distribución que no sea una linea?. Se puede conseguir algo más de flexibilidad definiendo varias lineas de regresión. Podemos dividir una distribución de puntos en varios tramos y en cada tramo calcular su linea de regresión, así en lugar de una solo linea tenemos un conjunto de ellas, para ello podemos usar lo limites que se le pasa en el constructor


LinearRegression lr = LinearRegression(0,20);

LinearRegression lr = LinearRegression(0,40);

LinearRegression lr = LinearRegression(0,60);

LinearRegression lr = LinearRegression(0,80);

LinearRegression lr = LinearRegression(0,100);

Ejemplo


#include 

LinearRegression lr = LinearRegression(0,100);

void setup() {
  lr.learn(1,3);
  lr.learn(2,4);
  lr.learn(3,5);
  lr.learn(4,6);
  lr.learn(5,7);
  lr.learn(6,8);

  Serial.begin(9600);

}

void loop() {
  Serial.print("Result: ");
  Serial.println(lr.calculate(6));

  Serial.print("Correlation: ");
  Serial.println(lr.correlation());

  Serial.print("Values: ");

  lr.getValues(values);
  Serial.print("Y = ");
  Serial.print(values[0]);
  Serial.print("*X + ");
  Serial.println(values[1]);

  delay(2000);
}

La librería esta disponible en github

Función Fitness

La función fitness suele ser una de las partes que menos trata se habla de metaheurística. Sin embargo es de las partes más importantes, si no directamente la más. Una mala heurística puede darte una mala aproximación. Pero una mala función fitness puede darte una solución completamente acertada para un problema que no es el que tú quieres resolver.

Es mportante tener en cuenta que las metaheurísticas no resuelven el problema que tu quieres, sino el que la función fitness describe. Suena como algo obvio pero causa más quebraderos de cabeza de lo que parece. Para empezar hay veces en las que no es sencillo valorar las soluciones. Por ejemplo con problemas de combinatoria, sobre todo si hay restricciones entre los elementos, puede ser complicado decir si una solución parcial es mejor que otra y más difícil aún estimar cuánto mejor. Valorar incorrectamente estas soluciones puede causar que el algoritmo «se desvíe de su camino» o incluso que haya soluciones incorrectas con valores mejores que las correcta.

Otro problema surge cuando hay que valorar soluciones que no son válidas, por ejemplo soluciones que matemáticamente tienen sentido pero son irrealizables en la práctica. En principio lo lógico puede parecer considerarlas inválidas y no continuar por ese camino, sin embargo puede ser necesario para llegar a explorar otra zona donde si son válidas.

Rendimiento

También influye en el rendimiento del algoritmo ya que el cálculo del fitness suele ser la parte más costosa de cada iteración. Cualquier optimización de la misma repercute beneficiosamente en el tiempo que cuesta realizar cada iteración.

Precisamente por eso cabe plantearse el empezar con una versión simplificada sin las restricciones más costosas o con menos resolución y según avance el algoritmo pasar a otra más precisa y completa. Como siempre estas optimizaciones no deben afectar al «relieve» del espacio de búsqueda. En las metaheurísticas con una fase de búsqueda global y otra local también puede ser interesante usar funciones menos precisas en la búsqueda global para ahorrar tiempo.

Minimizar, maximizar, optimizar

Algunos algoritmos funcionan buscando el máximo, otros el mínimo. El resultado de la función de fitness debe de adaptarse a ello. En el caso de que tengamos una función de fitness pensada para un tipo y queramos transformarla en el otro, la forma más simple es calcular el valor máximo que puede tomar la función fitness en el espacio de búsqueda (si no es posible conocerlo exactamente habrá que estimarlo) y restarle el valor de la función fitness en ese punto. Es decir a partir de una función de fitness F la nueva función fitness será:

f'(x) = fmax – f(x)

En resumen el resultado de la función fitness aporta la información a la metaheurística para funcionar. Si la función fitness no «dibuja un mapa» adecuado para la búsqueda da igual que metaheurística se use, no va a funcionar correctamente.

Generando números pseudoaleatorios y realmente aleatorios en Arduino

Números pseudoaletorios, función random()

Primero vamos a ver como generar números pseudoaleatorios usando la función random() de Arduino. Su uso es muy sencillo primero, normalmente en la función setup, se fija la semilla del generador usando la función randomSeed() y un valor que se le pasa como parámetro y luego se invoca a la función random() usadon una de sus dos versiones:

random(max)
random(min, max)

La primera calcula un valor entre 0 y max, la segunda entre min y max.

La semilla fijada en radomSeed() se usa para generar una secuencia de números pseudoaleatorios. A diferencia de los números aleatorios, que son distintos cada vez, los pseudoaletaorios son siempre los mismos. Cada semilla genera una secuencia única de números aleatorios que es siempre la misma. Por lo que si queremos que cada vez que reiniciemos la placa la secuencia de números sea diferente, tenemos que establecer la semilla con un valor que cambie cada vez. Hay varias opciones:

Tener un valor almacenado en la memoria EEPROM e incrementarlo en cada vez que se inicie el programa y usarlo como semilla.
Usar la función micros() que devuelve el número de microsegundos desde que el software se inicio.
El más habitual es usar el valor de de un puerto analógico donde no haya nada conectado.

El problema de usar estos tres métodos es que el primero es predecible y los otros dos no son realmente buenas fuentes de aleatoriedad. Sin embargo para la mayoría de los casos (que no se requieran números realmente aleatorios por seguridad) pueden ser suficientes.

Un ejemplo de uso:

long randNumber;

void setup() {
  Serial.begin(9600);  
  randomSeed(analogRead(0));
}

void loop() {
  //devuelve un número entre 0 y 300  
  randNumber = random(300);
  Serial.println(randNumber);

  //devuelve un número entre 10 y 200
  randNumber = random(10, 20);
  Serial.println(randNumber);

  delay(2000);
}

Generar números realmente aleatorios con un trozo de cable y analogRead

Si buscas una manera de generar números realmente aleatorios con Arduino se suele aconsejar recurrir a leer el valor de un puerto analógico que no este conectado a nada. El problema es que realmente los valores obtenidos no son aleatorios. Suelen oscilar en torno a un valor sin alejarse demasiado de él. Es decir si el valor leído es el 150 los más probable es que el siguiente número sea cercano, es más probable que sea el 151 que el 3. Cómo generador de números aleatorios no solo no es ninguna maravilla, es que es en muchos casos peor que el generador de números pseudoaleatorios de random()

Hay montajes electrónicos que producen valores aleatorios a partir del ruido que sufren sus componentes, pero suelen ser complicados. (Además ya no sería con un Arduino y tengo que justificar que el articulo este en la sección de «Arduino»)

Volviendo a nuestra idea de leer valores del puerto analógico vemos que el problema es que los números que devuelven oscilan entorno a un valor, esto se debe a que lo que leemos es el ruido en el puerto analógico, el ruido actúa como función aleatoria, pero este ruido tienen una característica especial, que explicada breve y mal es: «A más fuerte sea el ruido menos probable es que ocurra». Por lo tanto variaciones grandes del valor del puerto analógico son poco probables. Sin embargo hay una parte muy pequeña de este valor que si que se ve sometida a variaciones, la parte más pequeña del valor del puerto y por tanto la que más fácilmente varia, el bit de menor peso. Vamos a tomar solo ese bit y con ocho de ellos componer un byte. Ese byte debería ser aleatorio.

Para obtener el bit de menor peso podemos usar el siguiente código:

analogRead(analogInput)%2

Veamos el ejemplo para obtener un byte leyendo el puerto 8 veces:

byte randomAnalog(int analogInput){
  byte rnd = 0;
  for(int i = 0; i <; 8; i++){
    int aux = analogRead(analogInput)%2 << i; 
    rnd += aux;
    delay(10);
  }
  return rnd;
}

El delay(10) lo añadí por que sin ninguna espera analogRead me devolvía el mismo valor varias veces.

¿Pero donde esta el cable? Os preguntareis. Para aumentar el ruido, nada mejor que conectar un cable suelto en el puerto que se va a leer, contra más largo y retorcido esté mejor.

Combinar varias fuentes

Si te fías poco de este sistema puedes usar dos fuentes, o más, de aleatoriedad obteniendo bytes de dos puertos analógicos distintos y luego combinándolos con un xor.

byte r0 = randomAnalog(A0);
byte r1 = randomAnalog(A1);

byte r = r1 ^ r0;

Puede encontrar el código en el repositorio de github de ArduTips.

Un problema que pueden tener estos sistemas es que generalmente cuando hablamos de números aleatorios nos referimos a que producen produce el bit 0 y el bit 1 con un 50% de probabilidades (lo que se denomina un sistema justo), pero en este caso no podemos estar seguros de que sea así, sin embargo hay una manera de convertir cualquier sistema aleatorio a justo se puede leer aquí.

Puedes ver la explicación en vídeo de como generar números pseudoaleatorios en mi canal de youtube:

También esta disponible el vídeo de como generar números aleatorios:

Cifrado seguro en Arduino

Parece imposible cifrar de forma segura en un arduino con una potencia de cálculo equiparable a la de un despertador. Pero eso es porque siempre que se habla de cifrado se acaba hablando de complicados algoritmos matemáticos, sin embargo se puede lograr un cifrado perfectamente seguro usando operaciones matemáticas más simples. Os presento la forma de cifrado más simple.

Cifrar:

Ci = Mi xor Ki

Descifrar:

Mi = Ci xor Ki

Una simple operación xor de un byte del mensaje M con un byte de la contraseña de cifrado K. Os estaréis preguntando que si es tan seguro por qué no lo usamos en lugar de complicados algoritmos. Bueno tiene una pega, la contraseña ha de ser completamente aleatoria (o en su defecto lo más aleatoria posible) y ambos han de tener la misma longitud. Este sistema se conoce como libreta de un solo uso. Su nombre no es caprichoso, usar la misma contraseña de cifrado más de una vez para cifrar otro mensaje compromete la seguridad del sistema.

//Cifrar
C[i] = M[i] ^ K[i+j]; // j es el punto del cuaderno usado hasta la fecha.

//Descifrar
M[i] = C[i] ^ K[i+j]; // j es el punto del cuaderno usado hasta la fecha.

El problema de generar la larguísima "libreta" para cifrar lo dejo en vuestras manos. Podéis usar un generador en cualquier lenguaje, comprar números aleatorios, escribir en papelitos un montón de números tirarlos a aire y apuntarlos según se recogen...hay infinitas posibilidades y contra menos predecible sea el sistema usado, mejor. De hecho esa es su principal vulnerabilidad que la secuencia usada sea predecible.

Con esa larga secuencia de bytes usados para cifrar ya conseguida. El siguiente paso es cifrar lo que se quiera enviar. Para ello se toma un byte de datos y un byte de la "libreta", se realiza un xor entre ambos y listo. Es sencillo y el coste computacional es mínimo. Los byte de la libreta siempre se cogen de forma secuencial sin nunca repetirlos pase lo que pase.

Por supuesto todos los dispositivos que participan en la conversación tienen que tener una copia de la contraseña. Que se les ha tenido que "entregar" de forma segura (conectadolos con un cable o con una tarjeta SD) eso significa que el acceso físico a uno de estos dispositivos compromete la seguridad del cifrado (como con casi todos los sistemas). También es necesario incluir en el mensaje un numero de secuencia que indique a partir de que punto de la "libreta" usar para descifrar.

Para intentar agotar la "libreta" lo más tarde posible hay que procurar no cifrar datos innecesarios. Por otro lado, en algunos casos es necesario cifrar algún tipo de contador para votar ataques de repetición. Es posible que en algunos casos necesitemos "libretas" grandes por lo que habrá que ampliar la capacidad de almacenamiento del dispositivo por ejemplo montando un lector de tarjetas microSD con eso podemos tener espacio para una "libreta" que nos dure siglos y sale más barato que recurrir a otro tipo de soluciones.

En caso de terminar con la "libreta" hay que evitar reutilizarla. Podemos hacer un truco para tratar de alargar su utilidad. Aunque este truco no nos asegura que el cifrado vuelva a ser completamente seguro. El truco consiste en aplicar dos tipos de operaciones a la clave:

Intercambiar posiciones de los caracteres
A cada carácter aplicarle rotaciones de bits, negaciones o xor. Mejor si se combinan varias de ellas.

Es buena idea no realizar exactamente las mismas operaciones en cada carácter si no variarlas siguiendo un patrón lo mas grande posible carácter. Estás operaciones han de conocerse por todos los dispositivos que participan en la comunicación ya que si no obtendrán "libretas" distintas.

Con eso la libreta obtenida no es segura ni mucho menos, y lo correcto seria cambiarla, pero es mejor opción que reutilizarla directamente. Como ventaja está de nuestra parte que este tipo de dispositivos suelen transferir pocos datos así que hasta que el atacante consiga una cantidad suficiente de datos como para descifrar nuestros mensajaes puede tardar mucho tiempo. Del orden de semanas, meses o años.