Recibido: lunes, 13 agosto 2007

---

---

¿Radiocontrol? (*)

 

Robert Leese

Smith Institute for Industrial Mathematics and System Engineering

University of Oxford

e-mail: Esta dirección de correo electrónico está protegida contra los robots de spam, necesita tener Javascript activado para poder verla

página web: http://www2.maths.ox.ac.uk/~leese

 

 

Un poco de historia

 

 

Hertz ni siquiera vivió para ver el impacto total de su trabajo, aunque  su nombre es recordado en las unidades de frecuencia; posteriormente su familia recibió reconocimiento, cuando su sobrino Gustav Hertz (1887-1975) ganó el Premio Nobel de Física en 1925.

 

Marconi ciertamente se dio cuenta de las posibilidades de la nueva tecnología. En septiembre de 1899, generó un considerable entusiasmo al equipar buques para que enviaran informes sobre el progreso de la carrera de yates de la copa América. En 1901 consiguió enviar una señal a través del Atlántico. Estas primeras transmisiones fueron de código Morse y no de voz, pero las de voz llegaron a su debido tiempo.

 

Marconi continuó obteniendo nuevos records de distancia, culminando con el envío de un mensaje de Inglaterra a Australia en 1918. Pudo recorrer distancias tan largas aprovechando la manera en que las ondas de radio se propagan en la zona superior de la atmósfera y  “curvándolas” sobre la superficie de la Tierra. Pero, por favor, no hablemos de enviar mensajes a través de las “ondas del aire”: las ondas de radio son parte del espectro electromagnético, ¡y no se necesita aire ni ninguna otra cosa para transportarlas!

 

La mayoría de las primeras aplicaciones se centraron en la navegación, y posteriormente en la aviación, una vez que los vuelos de pasajeros llegaron a ser habituales. Sin embargo, no pasó mucho tiempo hasta que se descubrieron sus posibilidades para el ocio y el entretenimiento. En 1916, David Sarnaff, un empleado de la American Marconi Company, sugirió una “caja de música radiofónica” en términos fácilmente reconocibles:

 

...Este dispositivo debe estar preparado para recibir varias longitudes de onda con  el movimiento de un interruptor o al presionar un botón. La caja de música radiofónica puede estar dotada de amplificadores y un altavoz telefónico, todo lo cual puede ser elegantemente montado en una caja.

 

La radio se puso en funcionamiento, y rápidamente llegó a ser indispensable.

 

 

Un poco de física

 

Miremos algo más de cerca el espectro electromagnético.

 

Las ondas electromagnéticas tienen una frecuencia f (medida en hercios, normalmente abreviados como Hz) y una longitud de onda λ. La ecuación que las relaciona es

 

c=fλ ,

 

donde c es la velocidad de la luz, aproximadamente 3×10⁸ ms^-1. Puesto que c es constante, las bajas frecuencias corresponden a longitudes de onda largas y viceversa. Si disponemos el espectro de tal manera que las bajas frecuencias estén en la parte inferior, entonces la luz visible se encuentra, aproximadamente, en la mitad: por encima se localizan los rayos ultravioleta, rayos X y rayos gamma; por debajo están los infrarrojos, las microondas y las ondas de radio (Figura 1).

 

Frecuencia (Hz)
1021		Rayos γ Rayos X
1018		Ultravioleta
1015		Visible
1012		Infrarrojo
109		Microondas
106		Ondas de radio
Figura 1. Un cuadro esquemático del espectro electromagnético.

Estas ondas, siendo muy diferentes, se usan para diferentes propósitos. Después de todo, ¡sería bastante peligroso intentar enviarnos mensajes unos a otros mediante rayos gamma! Sin embargo, todas ellas se describen mediante la misma teoría matemática, desarrollada en el siglo XIX por James Clerk Maxwell y otros.

 

Las ondas usadas para la comunicación son aquellas que están por debajo de la luz visible en el espectro. No sólo las que los libros de texto llaman ondas de radio, sino también las microondas y las infrarrojas: en otras palabras, todas aquellas con longitud de onda mayor que 10⁶ m o, equivalentemente, con una frecuencia más baja que 3×10¹⁴ Hz. Las longitudes de onda útiles más largas se hallan en torno a los 10.000 metros, ¡lo que significa que el espectro utilizable cubre alrededor de diez órdenes de magnitud!

 

Las longitudes de onda particulares son adecuadas para aplicaciones particulares. Grosso modo, las longitudes de onda largas son mejores para las aplicaciones que requieren transmisión a larga distancia. Por esta razón, las aplicaciones de las ondas infrarrojas son actualmente bastante limitadas, aunque una muy importante, en tanto que nos hace la vida más fácil, es el mando a distancia de los aparatos de televisión. Las microondas se usan principalmente para transmisiones punto a punto, en las que la radio es una eficiente alternativa a la colocación de un alambre o cable entre dos puntos. Las frecuencias más bajas, correspondientes a las ondas de radio “tradicionales”, se usan en las emisiones de radio y televisión, en la navegación por mar y aire, meteorología, llamadas por “busca”, teléfonos móviles, y otros usos privados.

 

¿Cómo transportan las ondas de radio la voz, las imágenes de televisión, y otros datos? Técnicamente, la información está “modulada” sobre una onda “portadora”. La portadora es una onda “seno” pura, con frecuencia y amplitud fijas. La modulación origina cambios insignificantes en algunas propiedades de la onda, dependiendo de la información que se desee transmitir. Por ejemplo, en ondas de radio largas o medias (llamadas normalmente AM, por Amplitud Modulada) se usan fluctuaciones en la amplitud, y las ondas portadoras son de unos pocos cientos de kilohercios (kHz); la radio FM (Frecuencia Modulada) usa fluctuaciones de la frecuencia, y ondas portadoras de alrededor de 100 megahercios (MHz).

 

Los matemáticos prefieren pensar en términos de la llamada descomposición de Fourier de la señal de radio, que indica cómo la señal de radio es una mezcla de diferentes frecuencias. Una onda no modulada tiene una única frecuencia, a saber, la de la portadora, pero cualquier combinación de modulaciones provocará que la señal se “extienda” ligeramente alrededor de la frecuencia portadora. En otras palabras, en realidad la información se transmite sobre un pequeño rango de frecuencias, que origina un “canal” de radio.  Podemos pensar en el canal como en una tubería; su anchura se denomina “ancho de banda”. Las tuberías anchas pueden llevar más información que las estrechas. El mensaje puede ser transmitido usando un ancho de banda de 4-5 kHz; La radio AM en el Reino Unido tiene un ancho de banda de 9 kHz; La radio FM tiene un ancho de banda de 50 kHz (y, correspondientemente, obtenemos una calidad de sonido superior); los canales de televisión (analógicos) son mucho más anchos, de 5MHz, ya que el video contiene más información que el audio.

 

 

Un poco de política

 

No hay suficientes canales para acomodar en el espectro a muchos usuarios simultáneamente dándoles su propio canal. Ya en 1925, Herbert Hoover, entonces Secretario de Comercio de los EEUU, se interesó por el problema de la disponibilidad del espectro (¡y todavía no se había inventado la televisión!). Afortunadamente, fue pesimista. Los avances en los equipos de radio han supuesto que ahora podamos usar frecuencias más altas que aquellas que estaban disponibles en los años 20, y usarlas más eficazmente. Sin embargo, a finales de los años 90, incluso los más optimistas reconocerían que en la actualidad el espectro está sumamente congestionado.

 

La congestión del espectro implica que es cada vez más difícil evitar la interferencia de radio causada cuando dos personas, geográficamente cercanas, intentan usar el mismo canal para diferentes propósitos. Podemos además tener interferencias causadas por señales “desbordadas” de canales adyacentes, aunque generalmente esto no llega a ser un problema. Después de la invención de la radio se entendió rápidamente que la cooperación internacional era necesaria para ayudar a reducir las interferencias. La primera conferencia sobre la regulación del espectro se celebró en Berlín en 1903. La regulación del espectro es ahora una actividad crucial en todo el mundo, coordinada internacionalmente por la Unión Internacional de Telecomunicaciones, con sede en Ginebra.

 

La Agencia de Radiocomunicaciones, una agencia ejecutiva del Departamento de Comercio e Industria, vela por los intereses del Reino Unido. Su sitio web[1] proporciona una buena panorámica de las múltiples cuestiones involucradas en el manejo del espectro.

 

 

Un poco de matemáticas

 

Ya hemos tenido suficiente  historia, física y  política. ¿Cómo pueden ayudar las matemáticas? La noción crucial es la de canal de radio. No estamos interesados en una gama continua de frecuencias, sino en un sistema discreto de canales a intervalos regularmente espaciados. Por lo tanto, para hacer una descripción matemática usaremos matemática discreta, donde las técnicas son muy diferentes de las que se usan en la matemática continua.

 

El problema de decidir qué canales de radio usar en diferentes sitios se denomina el problema de la asignación de canales. Una posible descripción matemática es la siguiente. Se trata de construir un “grafo” (nada que ver con los grafos que tienen pares de ejes) con un “nodo” para cada transmisor de radio, y uniendo dos nodos con un “segmento” si los dos transmisores correspondientes se interferirían en caso de tener asignados el mismo canal. Ahora hemos de asignar canales a cada nodo de tal manera que cualquier nodo “adyacente”, esto es, unido por un segmento a él, obtenga un canal diferente. Así no habrá interferencias. Para conservar el espectro queremos, además, usar tan pocos canales diferentes como sea posible.

 

Matemáticamente, este es el famoso problema de colorear un grafo (si pensamos que los canales se representan por diferentes colores). Necesitamos colorear cada nodo en el grafo de tal manera que dos nodos unidos por un segmento tengan diferente color, usando el menor número de colores posible. Un problema para el cual el número mínimo de colores es 4 se muestra en la Figura 2.

 

La coloración de grafos ha sido un problema que ha tenido una larga y, a menudo, controvertida historia, en gran parte motivada por las dificultades para probar el teorema de colorear mapas, que establece  que en el caso especial en el que los segmentos nunca se crucen sólo se requieren cuatro colores. Sin embargo, en el problema de asignación de canales, este caso especial no es, en general, aplicable.

 

 

Un poco de informática

 

¿Cuán duro es el problema de colorar gráficos? Respuesta: muy duro, ya que se necesita mucho tiempo para que el ordenador nos dé una solución. La cuestión de clasificar problemas en relación con el tiempo que precisamos para resolverlos es relativamente reciente, simultánea con el desarrollo de la informática como disciplina académica. Podemos pensar en problemas que son resueltos por diferentes métodos, o algoritmos, implementados en la práctica mediante programas de ordenador.

 

Figura 3. Las variaciones de n6 y 2n con n.

El tiempo de ejecución, T, de un algoritmo depende generalmente del tamaño del problema que estamos intentando resolver. Para asignar canales, el tamaño de un problema puede ser medido por el número de transmisores, digamos n. Entonces T es una función de n, que escribimos T(n). Para excluir cualquier ambigüedad causada por las variaciones en la velocidad intrínseca de los procesadores de los ordenadores, T(n) mide el número de pasos en el cálculo, no el tiempo que realmente transcurre. Estamos interesados en conocer el incremento de T(n) a medida que n crece. Nos gustaría llevar la asignación de canales al menos a unos pocos cientos de transmisores.

 

El problema del coloreado de grafos es duro porque todos los algoritmos conocidos precisan de un tiempo al menos exponencial en n, lo que significa que T(n) crece como αⁿ para alguna constante α. Son malas noticias. Por contra, un algoritmo polinómico de tiempo T(n), que crece como n^k para alguna constante k, se consideraría una buena noticia.

 

Como ilustración, supongamos que comparamos las funciones n⁶ (polinómica) y 2ⁿ (exponencial) para n entre 2 y 50. En la Figura 3 se muestran ambas funciones, usando una escala logarítmica. Hasta n=29 el algoritmo polinómico es más lento, pero más allá de este punto la situación cambia. Supongamos que tuviéramos un ordenador que pudiera llevar a cabo 10⁹ pasos por segundo, y que estamos dispuestos a esperar un día entero para que se complete el cálculo (esto supone un ordenador rápido y una enorme paciencia por nuestra parte). Entonces el algoritmo polinómico podría tratar con problemas hasta n=210; el algoritmo exponencial sólo llegaría hasta n=46. Si queremos tratar con n=250, que todavía sería un problema modesto de asignación de canales, el algoritmo polinómico necesitaría un poco menos de 3 días, ¡y el algoritmo exponencial más de 10⁵⁸ años! Es interesante efectuar una comparación con la edad del Universo, que son aproximadamente 10⁹ años, para percatarse de por qué el hecho de que todos los algoritmos para coloreado de grafos sean exponenciales es tan mala noticia.

 

De hecho, no se ha probado de forma concluyente que no sea posible encontrar un algoritmo polinómico para el coloreado de grafos (o para una multitud de problemas similares). Puede ocurrir que todavía nadie haya sido suficientemente ingenioso para encontrarlo, pero mientras tanto se ha tratado de resolver la situación de la mejor manera. El nombre técnico para esta importante cuestión abierta, probablemente la más importante de la informática teórica, es problema P/NP. Para más información véase Ordenadores e intratabilidad, por M.R. Garey y D.S. Johnson (Freeman, 1979).

 

 

Ejemplos de asignación de  canales

 

Las implicaciones prácticas para la asignación de canales son que no podemos garantizar de forma absoluta la minimización del espectro utilizado. Pero en muchos casos es posible mostrar que  las asignaciones obtenidas en tiempo polinómico están cerca de ser óptimas, en el sentido de que utilizan sólo unos pocos canales más que el mínimo absoluto, aun cuando ese valor sea desconocido.

 

Otro rayo de esperanza es que, aunque no haya algoritmos con tiempos polinómicos sobre la totalidad de los problemas de colorear grafos, quizás la historia sea diferente cuando restringimos nuestra atención a los problemas que surgen de la asignación de canales. Los grafos resultantes están de alguna manera determinados por las leyes físicas que gobiernan la propagación de las señales de radio, aunque todavía no se entiende exactamente cuál es el vínculo, o cómo explotarlo eficazmente en el diseño de algoritmos.

 

Figura 4. Un problema de asignación de canales sobre una estructura celular, con las restricciones descritas en el texto.

Como ejemplo de lo que puede suceder en determinados casos, supongamos que el grafo corresponde a una disposición regular de los transmisores, de tal manera que cada uno de ellos está  en el centro de una “celda” hexagonal (Figura 4). La distancia entre transmisores vecinos se define como 1 unidad. Supongamos que, para evitar interferencias, los canales asignados a los transmisores a distancia menor o igual que 3 unidades deben ser diferentes, y también que los canales asignados a transmisores a distancia estrictamente menor que 2 unidades deben estar separados al menos 2 (esta última condición es un ingrediente añadido, para controlar el  “desborde” de interferencias entre canales adyacentes). Entonces el mínimo número de canales es 12, como se muestra en la Figura 4. Intenta:

 

• convencerte a ti mismo de que estas condiciones se satisfacen;
• encontrar el patrón de la asignación (la región rosa debería ayudar);
• convencerte a ti mismo de que el patrón podría repetirse indefinidamente;
• mostrar que no pueden usarse menos de 12 canales (de nuevo, la región rosa es la clave).

 

Hasta ahora no hemos mencionado la forma en que la asignación puede cambiar con el tiempo, pero muchos sistemas de radio modernos son altamente dinámicos. Así, mientras  la  Radio 1 de la BBC transmite en el mismo canal un día tras otro, quizás moviéndose cada pocos años y sólo después de muchos avisos, los teléfonos móviles, por ejemplo, son asignados a un nuevo canal cada vez que se hace una llamada. El canal escogido es generalmente diferente cada vez. El cálculo de una asignación dinámica óptima está todavía peor entendido que en los sistemas fijos.

 

Algunos sistemas reparten canales en bandas, reservadas para transmisores particulares. Las bandas se construyen con el fin de que no haya nunca interferencias. Estos canales actúan como líneas telefónicas convencionales; si todos están ocupados, se bloquea la llamada. La probabilidad de bloqueo viene dada por la famosa fórmula de Erlang (véase Ruteo de llamadas en redes  telefónicas, por R. Gibbens y S. Turner, en el número 2 de PASS Maths).

 

Otras estrategias permiten una asignación mucho más flexible, pero necesitan comprobaciones regulares para evitar interferencias. Para una demostración “en vivo” de asignación dinámica de canales usando una técnica llamada aprendizaje de refuerzo, prueba la simulación Java escrita por Satinder Singh, de la Universidad de Colorado.

 

 

Lecturas relacionadas

 

Hedy Lamarr[2]

 

Los militares necesitan cambiar constantemente las frecuencias de sus transmisiones para evitar que el enemigo las intercepte. Hedy Lamarr, una actriz de cine de los años 30 y 40, inventó un método de  “frequency-hopping” que mantuvo atareada a la oposición y se utiliza actualmente en las transferencias inalámbricas de datos entre ordenadores.