Minimizando la frecuencia de consultas para limitar el potencial de congestión de entidades en movimiento en un tiempo objetivo fijo
Autores: Evans, William; Kirkpatrick, David
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Minimizando la frecuencia de consultas para limitar el potencial de congestión de entidades en movimiento en un tiempo objetivo fijo
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Entidades
Invasión
Incertidumbre
Congestión
Consultas de ubicación
Costo de consulta
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 24
Citaciones: Sin citaciones
Consideremos una colección de entidades que se mueven continuamente con velocidad limitada, pero de otra manera impredecible, en algún espacio de baja dimensión. Dos de estas entidades se entrometen una en la otra en un tiempo fijo si su separación es menor que un umbral especificado. El entrometimiento, de preocupación en muchos contextos como la evasión de colisiones, puede ser inevitable. Sin embargo, las dificultades asociadas se ven agravadas si hay incertidumbre sobre la ubicación precisa de las entidades, lo que da lugar a posibles entrometimientos y, más generalmente, a posibles congestiones dentro de la colección completa. Adoptamos un modelo en el que las entidades pueden ser consultadas por su ubicación actual (a un costo) y la región de incertidumbre asociada con una entidad crece en proporción al tiempo desde que esa entidad fue consultada por última vez. El objetivo es mantener una baja congestión potencial, medida en términos del grafo de intersección (dinámico) de las regiones de incertidumbre, en momentos especificados (posiblemente) usando el costo de consulta más bajo posible. Trabajos anteriores en el mismo modelo de incertidumbre abordaron el problema de minimizar el potencial de congestión utilizando consultas de ubicación de alguna frecuencia limitada. Se demostró que es posible diseñar esquemas de consulta que son -competitivos, en términos del potencial de congestión en el peor caso, con otros esquemas de consulta, incluso clarividentes (que explotan el conocimiento de las trayectorias de todas las entidades), sujetos al mismo límite de frecuencia de consulta. En este documento, iniciamos el tratamiento de un problema más general con el objetivo de optimización complementario: minimizar el, medido como el recíproco del tiempo mínimo entre consultas (granularidad), garantizando al mismo tiempo un límite fijo en el potencial de congestión en un tiempo objetivo específico. Este objetivo complementario requiere esquemas y análisis bastante diferentes. Sin embargo, nuestros resultados se asemejan a los de los documentos anteriores, específicamente a límites competitivos ajustados en la frecuencia de consulta requerida.
Descripción
Consideremos una colección de entidades que se mueven continuamente con velocidad limitada, pero de otra manera impredecible, en algún espacio de baja dimensión. Dos de estas entidades se entrometen una en la otra en un tiempo fijo si su separación es menor que un umbral especificado. El entrometimiento, de preocupación en muchos contextos como la evasión de colisiones, puede ser inevitable. Sin embargo, las dificultades asociadas se ven agravadas si hay incertidumbre sobre la ubicación precisa de las entidades, lo que da lugar a posibles entrometimientos y, más generalmente, a posibles congestiones dentro de la colección completa. Adoptamos un modelo en el que las entidades pueden ser consultadas por su ubicación actual (a un costo) y la región de incertidumbre asociada con una entidad crece en proporción al tiempo desde que esa entidad fue consultada por última vez. El objetivo es mantener una baja congestión potencial, medida en términos del grafo de intersección (dinámico) de las regiones de incertidumbre, en momentos especificados (posiblemente) usando el costo de consulta más bajo posible. Trabajos anteriores en el mismo modelo de incertidumbre abordaron el problema de minimizar el potencial de congestión utilizando consultas de ubicación de alguna frecuencia limitada. Se demostró que es posible diseñar esquemas de consulta que son -competitivos, en términos del potencial de congestión en el peor caso, con otros esquemas de consulta, incluso clarividentes (que explotan el conocimiento de las trayectorias de todas las entidades), sujetos al mismo límite de frecuencia de consulta. En este documento, iniciamos el tratamiento de un problema más general con el objetivo de optimización complementario: minimizar el, medido como el recíproco del tiempo mínimo entre consultas (granularidad), garantizando al mismo tiempo un límite fijo en el potencial de congestión en un tiempo objetivo específico. Este objetivo complementario requiere esquemas y análisis bastante diferentes. Sin embargo, nuestros resultados se asemejan a los de los documentos anteriores, específicamente a límites competitivos ajustados en la frecuencia de consulta requerida.