Enrutamiento robusto con flujos eléctricos

Enrutamiento robusto con flujos eléctricos


En el mundo de las redes, existen modelos que pueden explicar las observaciones en una variedad de aplicaciones. Esto incluye tareas simples como calcular el camino más corto, que tiene aplicaciones obvias en las redes de enrutamiento, pero también tiene aplicaciones en biología, por ejemplo, donde el moho mucilaginoso Physarum puede encontrar los caminos más cortos en los laberintos. Otro ejemplo es la paradoja de Braess, la observación de que agregar recursos a una red puede tener un efecto contrario al esperado, que se manifiesta no solo en las redes de carreteras sino también en los sistemas mecánicos y eléctricos. Por ejemplo, construir una nueva carretera puede aumentar la congestión del tráfico o agregar una nueva conexión en un circuito puede aumentar el voltaje. Este tipo de conexiones entre circuitos eléctricos y otros tipos de redes se han aprovechado para diversas tareas, como B. dividir redes y dirigir flujos.

En «Enrutamiento robusto mediante flujos eléctricos», que recibió el premio al mejor artículo en SIGSPATIAL 2021, presentamos otra aplicación interesante de los flujos eléctricos en el contexto del enrutamiento de la red de carreteras. En particular, usamos ideas de flujos eléctricos para el problema de construir múltiples rutas alternativas entre una fuente dada y un destino dado. Las rutas alternativas son importantes para muchos casos de uso, incluida la búsqueda de rutas que mejor se adapten a las preferencias del usuario y para enrutamiento robusto, B. Enrutamiento que garantiza encontrar una buena ruta en los atascos de tráfico. Además, también describimos cómo se pueden modelar rápidamente los flujos eléctricos en las redes viales.

Enfoques existentes para el enrutamiento alternativo
El cálculo de rutas alternativas en las redes viales es un área de investigación relativamente nueva, y la mayoría de las técnicas se basan en una de dos plantillas principales: la procedimientos criminales y el método de meseta. En el primer caso, las rutas alternativas se calculan iterativamente ejecutando un algoritmo de ruta más corta y luego, en ejecuciones posteriores, agregando una penalización a los segmentos ya incluidos en las rutas más cortas calculadas para fomentar una mayor exploración. En este último, se construyen simultáneamente dos árboles de ruta más corta, uno desde el origen y otro desde el destino, que se utilizan para identificar secuencias de tramos de carretera comunes a ambos árboles. Cada una de estas secuencias comunes (p. ej., que se espera que sean carreteras arteriales principales) se trata como un punto de visita en ruta desde el origen hasta el destino, generando potencialmente una ruta alternativa. Se sabe que el método de penalización brinda resultados de alta calidad (es decir, tiempo de viaje promedio, diversidad y solidez del conjunto de rutas alternativas devueltas), pero en la práctica es muy lento, mientras que el método de meseta es mucho más rápido pero conduce a soluciones de menor calidad.

Una ruta alternativa: flujos eléctricos
Nuestro enfoque es diferente y supone que un problema de enrutamiento en una red de carreteras es en muchos aspectos análogo al flujo de corriente eléctrica a través de una red resistiva. Aunque la corriente eléctrica viaja por muchos caminos diferentes, es más débil en los caminos de mayor resistencia y más fuerte en los caminos de menor resistencia, en igualdad de condiciones.

Consideramos la red de carreteras como un diagrama, donde las intersecciones son nodos y las carreteras son bordes. Luego, nuestro método modela el gráfico como un circuito eléctrico reemplazando los bordes con resistencias cuyas resistencias corresponden al tiempo de viaje de la carretera y luego conectando una batería al origen y al destino, lo que genera corriente eléctrica entre esos dos puntos. En esta analogía, la resistencia modela cuánto tiempo consume atravesar un segmento. En este sentido, los tramos largos y congestionados presentan altas resistencias. Intuitivamente, el flujo de corriente eléctrica se distribuye por toda la red, pero se concentra en las rutas de menor resistencia que corresponden a las rutas más rápidas. Al identificar las principales rutas de flujo, podemos construir un conjunto viable de alternativas desde el origen hasta el destino.

Ejemplo de cómo construimos el circuito correspondiente a la red de carreteras. La corriente se puede dividir en tres corrientes, I1, I2 y I3; cada uno de los cuales corresponde a un camino alternativo viable de Fremont a San Rafael.

Para calcular el flujo eléctrico, usamos las leyes de Kirchhoff y Ohm, que establecen respectivamente: 1) La suma algebraica de las corrientes en cada intersección es igual a cero, lo que significa que el tráfico que ingresa a una intersección también sale de ella (por ejemplo, si tres automóviles ingresan a una intersección desde una calle y otro automóvil ingresa a la misma intersección desde otra calle, un total de cuatro automóviles deben salir de la intersección); y 2) la corriente es directamente proporcional a la diferencia de voltaje entre los puntos finales. Si escribimos las ecuaciones resultantes, terminamos con un sistema lineal con norte ecuaciones sobre norte Variables correspondientes a los potenciales (es decir, voltaje) en cada intersección. Aunque el voltaje no tiene una analogía directa con las redes de carreteras, se puede utilizar para calcular el flujo de corriente eléctrica y así encontrar rutas alternativas como se describe anteriormente.

Para encontrar la corriente electrica I (o flujo) en cualquier cable, podemos usar la ley de Kirchhoff y la ley de Ohm para obtener un sistema lineal de ecuaciones en términos de voltajes (o potenciales). v. Esto da un sistema lineal con tres ecuaciones (que representan la ley de Kirchhoff) y tres incógnitas (voltajes en cada intersección).

Entonces, el cálculo se reduce a calcular los valores de las variables de este sistema lineal, que involucra una matriz muy especial llamada matriz laplaciana. Tales matrices tienen muchas propiedades útiles, p. B. son simétricos y escaso – El número de entradas distintas de cero fuera de la diagonal es igual al doble del número de aristas. Aunque existen muchos solucionadores de tiempo casi lineales para tales sistemas de ecuaciones lineales, todavía son demasiado lentos para responder rápidamente a las solicitudes de enrutamiento de baja latencia. Por lo tanto, desarrollamos un nuevo algoritmo que resuelve estos sistemas lineales mucho más rápido para el caso especial de las redes de carreteras.1.

Cálculo rápido de flujo eléctrico
La primera parte clave de este nuevo algoritmo implica la eliminación gaussiana, que es quizás el método más conocido para resolver sistemas lineales. Cuando se realiza en una matriz de Laplace, que es equivalente a una red resistiva, es equivalente a la transformada Y-Δ, que reduce el número de nodos conservando los voltajes. El único inconveniente es que el número de aristas puede aumentar, lo que hace que el sistema lineal sea aún más lento de resolver. Por ejemplo, si se elimina un nodo con 10 enlaces con la transformada Y-Δ, ¡el sistema terminaría con 35 enlaces nuevos!

La transformación Y-Δ nos permite eliminar el enlace del medio y reemplazarlo con tres enlaces (Ra, RB y RC) entre norte1, norte2 y norte3. (Imagen de Wikipedia)

Sin embargo, si uno puede identificar partes de la red que están conectadas con el resto a través de muy pocos nodos (llamemos a estas conexiones cuellos de botella) y elimine todo lo demás al salir de los nodos del cuello de botella, los nuevos bordes formados al final se encontrarán solo entre los nodos del cuello de botella. Siempre que el número de nodos de cuello de botella sea mucho menor que el número de nodos eliminados con Y-Δ, que es el caso de las redes de carreteras, ya que los nodos de cuello de botella, como puentes y túneles, son mucho más raros que los cruces normales, esto conducirá a un gran reducción neta (por ejemplo, ~100x) en el tamaño del gráfico. Afortunadamente, la identificación de tales cuellos de botella en las redes viales se puede hacer simplemente dividiendo dicha red. Aplicando la transformada Y-Δ a todos los nodos excepto a los cuellos de botella2el resultado es un gráfico mucho más pequeño para el cual las tensiones se pueden resolver más rápido.

Pero, ¿qué pasa con el cálculo de los flujos en el resto de la red que no consiste en nodos de cuello de botella? Una propiedad útil de los flujos eléctricos es que una vez que se conocen los voltajes en los nodos de cuello de botella, se puede calcular fácilmente el flujo eléctrico para el resto de la red. El flujo eléctrico dentro de una parte de la red depende únicamente del voltaje de los nodos de cuello de botella que separan esa parte del resto de la red. De hecho, es posible precalcular una matriz pequeña para que se pueda recuperar el flujo eléctrico mediante una sola multiplicación matriz-vector, que es una operación muy rápida que se puede realizar en paralelo.

Considere la red vial conceptual impuesta en Staten Island (Izquierda), por lo que el cálculo directo del flujo eléctrico sería lento. Los puentes (nodos rojos) son los puntos de cuello de botella, y podemos eliminar toda la red de carreteras dentro de la isla aplicando repetidamente la eliminación gaussiana (o transformada Y-Δ). La red resultante (centrar) es un gráfico mucho más pequeño que permite un cálculo más rápido. Los potenciales dentro de la parte eliminada son siempre una combinación lineal fija de los nodos de cuello de botella (A la derecha).

Una vez que tenemos una solución que proporciona el flujo de corriente en nuestra red modelo, podemos observar las rutas con el flujo de corriente más alto y generarlas como rutas alternativas para la red de carreteras.

Resultados
Aquí hay algunos resultados que representan las alternativas calculadas por el algoritmo anterior.

Encontré varias alternativas para el Área de la Bahía. Los diferentes colores corresponden a diferentes rutas desde el punto de partida (icono rojo hacia abajo) hasta el destino (icono azul hacia arriba).

Conclusión
En este artículo describimos un enfoque novedoso para calcular rutas alternativas en redes viales. Fundamentalmente diferente de las principales técnicas utilizadas en décadas de investigación en esta área, nuestro enfoque ofrece rutas alternativas de alta calidad en las redes viales al examinar el problema a través de la lente de los circuitos eléctricos. Este es un enfoque que puede resultar muy útil en sistemas prácticos y esperamos que estimule más investigaciones sobre el cálculo de rutas alternativas y problemas relacionados. Los lectores interesados ​​pueden encontrar una discusión detallada de este trabajo en nuestra grabación de la conferencia SIGSPATIAL 2021.

Gracias
Agradecemos a nuestros colaboradores Lisa Fawcett, Sreenivas Gollapudi, Ravi Kumar, Andrew Tomkins y Ameya Velingker de Google Research.


1Nuestras técnicas funcionan para cualquier red que se pueda dividir en componentes más pequeños eliminando algunos nodos.
2 Realizar una transformación Y-Δ individualmente para cada nodo será demasiado lento. En su lugar, eliminamos grupos enteros de nodos aprovechando las propiedades algebraicas de la transformada Y-Δ.

Related post

Mantente borracho para seguir con vida en este divertido juego de zombis de realidad virtual

Mantente borracho para seguir con vida en este divertido…

El hecho de que el mundo se esté acabando no significa que no puedas divertirte. Gran parte de la población mundial…
Cómo funcionan las canalizaciones de datos con almacenes

Cómo funcionan las canalizaciones de datos con almacenes

Las empresas a menudo reciben datos de diferentes fuentes. Los datos pueden ser datos estructurados, semiestructurados o incluso no estructurados, como…
Micropartículas con sentimiento

Micropartículas con sentimiento

23 de mayo de 2022 (Noticias de Nanowerk) La superficie de un coral es rugosa. Su esqueleto duro está poblado de…

Leave a Reply

Tu dirección de correo electrónico no será publicada.