En la computación distribuida y la teoría de grafos geométricos , la incrustación codiciosa es un proceso de asignación de coordenadas a los nodos de una red de telecomunicaciones para permitir que el enrutamiento geográfico codicioso se utilice para enrutar mensajes dentro de la red. Aunque se ha propuesto la incrustación codiciosa para su uso en redes de sensores inalámbricos , en las que los nodos ya tienen posiciones en el espacio físico, estas posiciones existentes pueden diferir de las posiciones que les dan la incrustación codiciosa, que en algunos casos pueden ser puntos en un espacio virtual de una dimensión superior, o en una geometría no euclidiana . En este sentido, la incrustación codiciosa puede verse como una forma dedibujo de gráfico , en el que un gráfico abstracto (la red de comunicaciones) está incrustado en un espacio geométrico.
La idea de realizar un enrutamiento geográfico usando coordenadas en un espacio virtual, en lugar de usar coordenadas físicas, se debe a Rao et al. [1] Desarrollos posteriores han demostrado que cada red tiene una incrustación codiciosa con coordenadas de vértice sucintas en el plano hiperbólico , que ciertos gráficos, incluidos los gráficos poliédricos, tienen incrustaciones codiciosas en el plano euclidiano y que los gráficos de disco unitario tienen incrustaciones codiciosas en espacios euclidianos de dimensiones moderadas con factores de estiramiento bajos.
Definiciones
En el enrutamiento codicioso, un mensaje desde un nodo de origen sa un nodo de destino t viaja a su destino mediante una secuencia de pasos a través de nodos intermedios, cada uno de los cuales pasa el mensaje a un nodo vecino que está más cerca de t . Si el mensaje llega a un nodo intermedio x que no tiene un vecino más cercano a t , entonces no puede avanzar y el proceso de enrutamiento codicioso falla. Una incrustación codiciosa es una incrustación del gráfico dado con la propiedad de que una falla de este tipo es imposible. Por lo tanto, se puede caracterizar como una incrustación del gráfico con la propiedad de que para cada dos nodos x y t , existe un vecino y de x tal que d ( x , t )> d ( y , t ), donde d denota la distancia en el espacio incrustado. [2]
Gráficos sin incrustaciones codiciosas
No todos los gráficos tienen una incrustación codiciosa en el plano euclidiano ; un contraejemplo simple lo da la estrella K 1,6 , un árbol con un nudo interno y seis hojas. [2] Siempre que este gráfico está incrustado en el plano, dos de sus hojas deben formar un ángulo de 60 grados o menos, de lo cual se deduce que al menos una de estas dos hojas no tiene un vecino más cercano a la otra. hoja.
En los espacios euclidianos de dimensiones más altas, más gráficos pueden tener incrustaciones codiciosas; por ejemplo, K 1,6 tiene una incrustación codiciosa en el espacio euclidiano tridimensional, en el que el nodo interno de la estrella está en el origen y las hojas están a una unidad de distancia a lo largo de cada eje de coordenadas. Sin embargo, para cada espacio euclidiano de dimensión fija, hay gráficos que no se pueden incrustar codiciosamente: siempre que el número n es mayor que el número de besos del espacio, el gráfico K 1, n no tiene incrustaciones codiciosas. [3]
Incrustaciones hiperbólicas y sucintas
A diferencia del caso del plano euclidiano, cada red tiene una incrustación codiciosa en el plano hiperbólico . La prueba original de este resultado, por Robert Kleinberg , requería que las posiciones de los nodos se especificaran con alta precisión, [4] pero posteriormente se demostró que, al usar una descomposición de ruta pesada de un árbol de expansión de la red, es posible representar cada nodo de forma sucinta, utilizando sólo un número logarítmico de bits por punto. [3] En contraste, existen gráficos que tienen incrustaciones codiciosas en el plano euclidiano, pero para las cuales dicha incrustación requiere un número polinomial de bits para las coordenadas cartesianas de cada punto. [5] [6]
Clases especiales de gráficos
Árboles
La clase de árboles que admiten incrustaciones codiciosas en el plano euclidiano ha sido completamente caracterizada, y se puede encontrar una incrustación codiciosa de un árbol en el tiempo lineal cuando existe. [7]
Para gráficos más generales, algunos algoritmos de incrustación codiciosos como el de Kleinberg [4] comienzan por encontrar un árbol de expansión del gráfico dado y luego construyen una incrustación codiciosa del árbol de expansión. El resultado es necesariamente también una incrustación codiciosa de todo el gráfico. Sin embargo, existen gráficos que tienen una incrustación codiciosa en el plano euclidiano, pero para los que ningún árbol de expansión tiene una incrustación codiciosa. [8]
Gráficos planos
¿Todos los gráficos poliédricos tienen una incrustación codiciosa plana con caras convexas?
Papadimitriou y Ratajczak (2005) harvtxt error: múltiples objetivos (2 ×): CITEREF Papadimitriou Ratajczak2005 ( ayuda ) conjeturaron que cada gráfico poliédrico (un gráfico plano conectado a 3 vértices , o equivalentemente por el teorema de Steinitz el gráfico de un poliedro convexo ) tiene una codicia incrustado en el plano euclidiano. [9] Al explotar las propiedades de los gráficos de cactus , Leighton y Moitra (2010) probaron la conjetura; [8] [10] las incrustaciones codiciosas de estos gráficos se pueden definir de forma sucinta, con muchos bits logarítmicamente por coordenada. [11] Sin embargo, las incrustaciones codiciosas construidas de acuerdo con esta prueba no son necesariamente incrustaciones planas, ya que pueden incluir cruces entre pares de bordes. Para gráficos planos máximos , en los que cada cara es un triángulo, se puede encontrar una incrustación plana codiciosa aplicando el lema de Knaster-Kuratowski-Mazurkiewicz a una versión ponderada de un algoritmo de incrustación en línea recta de Schnyder. [12] [13] La fuerte conjetura de Papadimitriou-Ratajczak , de que cada grafo poliédrico tiene una incrustación codiciosa plana en la que todas las caras son convexas, sigue sin probarse. [14]
Gráficos de disco unitario
Las redes de sensores inalámbricos que son el objetivo de codiciosos algoritmos de incrustación se modelan con frecuencia como gráficos de disco unitario , gráficos en los que cada nodo se representa como un disco unitario y cada borde corresponde a un par de discos con una intersección no vacía. Para esta clase especial de gráficos, es posible encontrar incrustaciones codiciosas sucintas en un espacio euclidiano de dimensión polilogarítmica, con la propiedad adicional de que las distancias en el gráfico se aproximan con precisión por distancias en la incrustación, de modo que los caminos seguidos por rutas codiciosas son corto. [15]
Referencias
- ^ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H .; Shenker, Scott ; Stoica, Ion (2003), "Enrutamiento geográfico sin información de ubicación", Proc. Noveno ACM Mobile Computing and Networking (MobiCom) , págs. 96–108, doi : 10.1145 / 938985.938996.
- ^ a b Papadimitriou, Christos H .; Ratajczak, David (2005), "Sobre una conjetura relacionada con el enrutamiento geométrico", Informática teórica , 344 (1): 3-14, doi : 10.1016 / j.tcs.2005.06.022 , MR 2178923.
- ^ a b Eppstein, D .; Goodrich, MT (2011), "Enrutamiento geométrico codicioso sucinto usando geometría hiperbólica", IEEE Transactions on Computers , 60 (11): 1571-1580, doi : 10.1109 / TC.2010.257.
- ^ a b Kleinberg, R. (2007), "Enrutamiento geográfico utilizando espacio hiperbólico", Proc. 26a Conferencia Internacional de Comunicaciones Informáticas del IEEE (INFOCOM 2007) , págs. 1902-1909, doi : 10.1109 / INFCOM.2007.221.
- ^ Cao, Lei; Strelzoff, A .; Sun, JZ (2009), "Sobre la concisión del enrutamiento codicioso geométrico en el plano euclidiano", Décimo Simposio Internacional sobre Sistemas Pervasivos, Algoritmos y Redes (ISPAN 2009) , págs. 326–331, doi : 10.1109 / I-SPAN.2009.20.
- ^ Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio (2010), "Los dibujos codiciosos sucintos no siempre existen", Dibujo gráfico: 17º Simposio Internacional, GD 2009, Chicago, IL, EE. UU., 22-25 de septiembre de 2009, Artículos revisados , Lecture Notes in Computer Science, 5849 , págs. 171–182, doi : 10.1007 / 978-3-642-11805-0_17.
- ^ Nöllenburg, Martin; Prutkin, Roman (2013), "Dibujos ávidos euclidianos de árboles", Proc. 21o Simposio Europeo sobre Algoritmos (ESA 2013) , arXiv : 1306.5224 , Bibcode : 2013arXiv1306.5224N.
- ^ a b Leighton, Tom ; Moitra, Ankur (2010), "Algunos resultados sobre incrustaciones codiciosas en espacios métricos", Geometría discreta y computacional , 44 (3): 686–705, doi : 10.1007 / s00454-009-9227-6 , MR 2679063.
- ^ Papadimitriou, Christos H .; Ratajczak, David (2005), "Sobre una conjetura relacionada con el enrutamiento geométrico", Informática teórica , 344 (1): 3-14, doi : 10.1016 / j.tcs.2005.06.022 , MR 2178923.
- ^ Ver también Angelini, Patrizio; Frati, Fabrizio; Grilli, Luca (2010), "Un algoritmo para construir dibujos codiciosos de triangulaciones", Journal of Graph Algorithms and Applications , 14 (1): 19–51, doi : 10.7155 / jgaa.00197 , MR 2595019.
- ^ Goodrich, Michael T .; Strash, Darren (2009), "Enrutamiento geométrico codicioso sucinto en el plano euclidiano", Algoritmos y computación: 20º Simposio Internacional, ISAAC 2009, Honolulu, Hawaii, EE. UU., 16-18 de diciembre de 2009, Actas , Notas de conferencias en Ciencias de la Computación, 5878 , Berlín: Springer, págs. 781–791, arXiv : 0812.3893 , doi : 10.1007 / 978-3-642-10631-6_79 , MR 2792775.
- ^ Schnyder, Walter (1990), "Incrustación de gráficos planos en la cuadrícula", Proc. 1er Simposio ACM / SIAM sobre algoritmos discretos (SODA) , págs. 138–148.
- ^ Dhandapani, Raghavan (2010), "Greedy drawings of triangulations", Discrete and Computational Geometry , 43 (2): 375–392, doi : 10.1007 / s00454-009-9235-6 , MR 2579703. Ver también
- ^ Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz (2016), "Sobre dibujos de acordes crecientes y de aproximación propia de gráficos planos conectados en 3", Journal of Computational Geometry , 7 (1): 47–69, arXiv : 1409.0315 , doi : 10.20382 / jocg.v7i1a3 , MR 3463906.
- ^ Flury, R .; Pemmaraju, SV; Wattenhofer, R. (2009), "Enrutamiento codicioso con tramo limitado", IEEE INFOCOM 2009 , págs. 1737–1745, doi : 10.1109 / INFCOM.2009.5062093.