Resumen

Una consulta de vecino más cercano en rango (RNN, por sus siglas en inglés) en una red espacial encuentra los objetos más cercanos a cada punto en la región de consulta. La naturaleza esencial de la consulta RNN es significativa en los servicios basados en la ubicación (LBS, por sus siglas en inglés), donde las consultas con conciencia de la ubicación y regiones de consulta como las consultas RNN se utilizan con frecuencia debido al problema de privacidad de la ubicación y la imprecisión de las técnicas de posicionamiento asociadas. Los estudios existentes se centran en reducir los costos de computación en el lado del servidor mientras procesan las consultas RNN. También consideran consultas instantáneas que se evalúan una vez y se terminan, en contraposición a las consultas en movimiento que requieren una actualización constante de sus resultados. Sin embargo, se ha prestado poca atención a la evaluación de consultas RNN en movimiento en redes espaciales dirigidas y dinámicas donde cada borde está dirigido y su peso cambia de acuerdo con las condiciones de tráfico. En este documento, proponemos un algoritmo eficiente llamado MORAN que evalúa consultas de vecino más cercano en rango en movimiento (MRNN) en redes espaciales dirigidas y dinámicas. Los resultados de una simulación realizada utilizando mapas de carreteras de la vida real indican que MORAN es más efectivo que un método competitivo basado en un enfoque de ejecución compartida.

• Materias:Algoritmo dinámico Redes Inalámbricas Redes de Comunicación Sistema de colas Teoría de juegos
• Subjects:Dynamic Algorithm Wireless Networks Communication networks Queuing systems Game theory
• Palabras claves:Rango vecino más próximo; Consulta; Red espacial; Servicios basados en la localización; Consultas en movimiento; Redes espaciales dinámicas.
• Keywords:Range nearest neighbor; Query; Spatial network; Location-based services; Moving queries; Dynamic spatial networks